>From c30e48c69b3390250f60b780c64ebeb2da2fcf75 Mon Sep 17 00:00:00 2001 From: NeilBrown Date: Sun, 28 Feb 2016 16:09:29 +1100 Subject: [PATCH] radix-tree: support locking of individual exception entries. The least significant bit of an exception entry is used as a lock flag. A caller can: - create a locked entry by simply adding an entry with this flag set - lock an existing entry with radix_tree_lookup_lock(). This may return NULL if the entry doesn't exists, or was deleted while waiting for the lock. It may return a non-exception entry if that is what is found. If it returns a locked entry then it has exclusive rights to delete the entry. - unlock an entry that is already locked. This will wake any waiters. These must all be called with the radix tree locked (i.e. a spinlock held). That spinlock is passed to radix_tree_lookup_lock() so that it can drop the lock while waiting. This is a "demonstration of concept". I haven't actually tested, only compiled. A possible use case is for the exception entries used by DAX. It is possible that some of the lookups can be optimised away in some cases by storing a slot pointer. I wanted to keep it reasonable simple until it was determined if it might be useful. Signed-off-by: NeilBrown Signed-off-by: Jan Kara --- include/linux/radix-tree.h | 5 +++ lib/radix-tree.c | 83 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 88 insertions(+) diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h index 450c12b546b7..92138d30b95d 100644 --- a/include/linux/radix-tree.h +++ b/include/linux/radix-tree.h @@ -308,6 +308,11 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root, int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag); unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item); +void *radix_tree_lookup_lock(struct radix_tree_root *root, unsigned long index, + wait_queue_head_t *wq, spinlock_t *lock); +void radix_tree_unlock(struct radix_tree_root *root, unsigned long index, + wait_queue_head_t *wq); + static inline void radix_tree_preload_end(void) { preempt_enable(); diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 37d4643ab5c0..a97231ab66f0 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -1500,3 +1500,86 @@ void __init radix_tree_init(void) radix_tree_init_maxindex(); hotcpu_notifier(radix_tree_callback, 0); } + +/* + * Exception entry locking + */ +static inline int slot_locked(void **v) +{ + unsigned long l = *(unsigned long *)v; + return l & 1; +} + +static inline void *lock_slot(void **v) +{ + unsigned long *l = (unsigned long *)v; + return (void*)(*l |= 1); +} + +static inline void * unlock_slot(void **v) +{ + unsigned long *l = (unsigned long *)v; + return (void*)(*l &= ~1UL); +} + +/** + * radix_tree_lookup_lock - lookup and lock exceptional entry if found + * @root: radix tree root + * @index: index key + * @wq: waitqueue to wait for exceptional entry lock + * @lock: spinlock protecting the radix tree + * + * Lookup @index in the radix tree @root and if there is an exceptional + * entry at that location, lock it. If entry at @index is not exceptional, + * we just return it. We use @wq as a wait queue to wait for exceptional + * entry lock to be released. @lock is a spinlock protecting the radix + * tree which we assume is locked when entering this function and released + * while waiting for the exceptional entry lock. + */ +void *radix_tree_lookup_lock(struct radix_tree_root *root, unsigned long index, + wait_queue_head_t *wq, spinlock_t *lock) +{ + void *ret, **slot; + DEFINE_WAIT(wait); + + for (;;) { + ret = __radix_tree_lookup(root, index, NULL, &slot); + if (!ret || !radix_tree_exceptional_entry(ret)) + return ret; + if (!slot_locked(slot)) + return lock_slot(slot); + prepare_to_wait(wq, &wait, TASK_UNINTERRUPTIBLE); + spin_unlock(lock); + schedule(); + finish_wait(wq, &wait); + spin_lock(lock); + } +} +EXPORT_SYMBOL(radix_tree_lookup_lock); + +/** + * radix_tree_unlock - unlock exceptional radix tree entry + * @root: radix tree root + * @index: index key + * @wq: waitqueue to wake waiters for exceptional entry lock + * + * Unlock exceptional entry at @index in a radix tree @root and wake up + * waiters for it waiting in wait queue @wq. We expect the radix tree is + * locked against concurrent modifications. + */ +void radix_tree_unlock(struct radix_tree_root *root, unsigned long index, + wait_queue_head_t *wq) +{ + void *ret, **slot; + + ret = __radix_tree_lookup(root, index, NULL, &slot); + if (WARN_ON_ONCE(!ret || !radix_tree_exceptional_entry(ret))) + return; + if (WARN_ON_ONCE(!slot_locked(slot))) + return; + unlock_slot(slot); + + if (waitqueue_active(wq)) + wake_up(wq); +} +EXPORT_SYMBOL(radix_tree_unlock); -- 2.6.2