#include <linux/slab.h>
#include <linux/notifier.h>
#include <linux/cpu.h>
-#include <linux/gfp.h>
#include <linux/string.h>
#include <linux/bitops.h>
#include <linux/rcupdate.h>
* ensure that the addition of a single element in the tree cannot fail. On
* success, return zero, with preemption disabled. On error, return -ENOMEM
* with preemption not disabled.
+ *
+ * To make use of this facility, the radix tree must be initialised without
+ * __GFP_WAIT being passed to INIT_RADIX_TREE().
*/
int radix_tree_preload(gfp_t gfp_mask)
{
}
EXPORT_SYMBOL(radix_tree_insert);
-/**
- * radix_tree_lookup_slot - lookup a slot in a radix tree
- * @root: radix tree root
- * @index: index key
- *
- * Returns: the slot corresponding to the position @index in the
- * radix tree @root. This is useful for update-if-exists operations.
- *
- * This function can be called under rcu_read_lock iff the slot is not
- * modified by radix_tree_replace_slot, otherwise it must be called
- * exclusive from other writers. Any dereference of the slot must be done
- * using radix_tree_deref_slot.
+/*
+ * is_slot == 1 : search for the slot.
+ * is_slot == 0 : search for the node.
*/
-void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
+static void *radix_tree_lookup_element(struct radix_tree_root *root,
+ unsigned long index, int is_slot)
{
unsigned int height, shift;
struct radix_tree_node *node, **slot;
- node = rcu_dereference(root->rnode);
+ node = rcu_dereference_raw(root->rnode);
if (node == NULL)
return NULL;
if (!radix_tree_is_indirect_ptr(node)) {
if (index > 0)
return NULL;
- return (void **)&root->rnode;
+ return is_slot ? (void *)&root->rnode : node;
}
node = radix_tree_indirect_to_ptr(node);
do {
slot = (struct radix_tree_node **)
(node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
- node = rcu_dereference(*slot);
+ node = rcu_dereference_raw(*slot);
if (node == NULL)
return NULL;
height--;
} while (height > 0);
- return (void **)slot;
+ return is_slot ? (void *)slot:node;
+}
+
+/**
+ * radix_tree_lookup_slot - lookup a slot in a radix tree
+ * @root: radix tree root
+ * @index: index key
+ *
+ * Returns: the slot corresponding to the position @index in the
+ * radix tree @root. This is useful for update-if-exists operations.
+ *
+ * This function can be called under rcu_read_lock iff the slot is not
+ * modified by radix_tree_replace_slot, otherwise it must be called
+ * exclusive from other writers. Any dereference of the slot must be done
+ * using radix_tree_deref_slot.
+ */
+void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
+{
+ return (void **)radix_tree_lookup_element(root, index, 1);
}
EXPORT_SYMBOL(radix_tree_lookup_slot);
*/
void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
{
- unsigned int height, shift;
- struct radix_tree_node *node, **slot;
-
- node = rcu_dereference(root->rnode);
- if (node == NULL)
- return NULL;
-
- if (!radix_tree_is_indirect_ptr(node)) {
- if (index > 0)
- return NULL;
- return node;
- }
- node = radix_tree_indirect_to_ptr(node);
-
- height = node->height;
- if (index > radix_tree_maxindex(height))
- return NULL;
-
- shift = (height-1) * RADIX_TREE_MAP_SHIFT;
-
- do {
- slot = (struct radix_tree_node **)
- (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
- node = rcu_dereference(*slot);
- if (node == NULL)
- return NULL;
-
- shift -= RADIX_TREE_MAP_SHIFT;
- height--;
- } while (height > 0);
-
- return node;
+ return radix_tree_lookup_element(root, index, 0);
}
EXPORT_SYMBOL(radix_tree_lookup);
}
EXPORT_SYMBOL(radix_tree_tag_clear);
-#ifndef __KERNEL__ /* Only the test harness uses this at present */
/**
* radix_tree_tag_get - get a tag on a radix tree node
* @root: radix tree root
*
* 0: tag not present or not set
* 1: tag set
+ *
+ * Note that the return value of this function may not be relied on, even if
+ * the RCU lock is held, unless tag modification and node deletion are excluded
+ * from concurrency.
*/
int radix_tree_tag_get(struct radix_tree_root *root,
unsigned long index, unsigned int tag)
if (!root_tag_get(root, tag))
return 0;
- node = rcu_dereference(root->rnode);
+ node = rcu_dereference_raw(root->rnode);
if (node == NULL)
return 0;
*/
if (!tag_get(node, tag, offset))
saw_unset_tag = 1;
- if (height == 1) {
- int ret = tag_get(node, tag, offset);
-
- BUG_ON(ret && saw_unset_tag);
- return !!ret;
- }
- node = rcu_dereference(node->slots[offset]);
+ if (height == 1)
+ return !!tag_get(node, tag, offset);
+ node = rcu_dereference_raw(node->slots[offset]);
shift -= RADIX_TREE_MAP_SHIFT;
height--;
}
}
EXPORT_SYMBOL(radix_tree_tag_get);
-#endif
/**
* radix_tree_next_hole - find the next hole (not-present entry)
*
* Returns: the index of the hole if found, otherwise returns an index
* outside of the set specified (in which case 'index - return >= max_scan'
- * will be true). In rare cases of wrap-around, LONG_MAX will be returned.
+ * will be true). In rare cases of wrap-around, ULONG_MAX will be returned.
*
* radix_tree_next_hole may be called under rcu_read_lock. However, like
* radix_tree_gang_lookup, this will not atomically search a snapshot of
if (!radix_tree_lookup(root, index))
break;
index--;
- if (index == LONG_MAX)
+ if (index == ULONG_MAX)
break;
}
}
shift -= RADIX_TREE_MAP_SHIFT;
- slot = rcu_dereference(slot->slots[i]);
+ slot = rcu_dereference_raw(slot->slots[i]);
if (slot == NULL)
goto out;
}
unsigned long cur_index = first_index;
unsigned int ret;
- node = rcu_dereference(root->rnode);
+ node = rcu_dereference_raw(root->rnode);
if (!node)
return 0;
slot = *(((void ***)results)[ret + i]);
if (!slot)
continue;
- results[ret + nr_found] = rcu_dereference(slot);
+ results[ret + nr_found] = rcu_dereference_raw(slot);
nr_found++;
}
ret += nr_found;
unsigned long cur_index = first_index;
unsigned int ret;
- node = rcu_dereference(root->rnode);
+ node = rcu_dereference_raw(root->rnode);
if (!node)
return 0;
}
}
shift -= RADIX_TREE_MAP_SHIFT;
- slot = rcu_dereference(slot->slots[i]);
+ slot = rcu_dereference_raw(slot->slots[i]);
if (slot == NULL)
break;
}
if (!root_tag_get(root, tag))
return 0;
- node = rcu_dereference(root->rnode);
+ node = rcu_dereference_raw(root->rnode);
if (!node)
return 0;
slot = *(((void ***)results)[ret + i]);
if (!slot)
continue;
- results[ret + nr_found] = rcu_dereference(slot);
+ results[ret + nr_found] = rcu_dereference_raw(slot);
nr_found++;
}
ret += nr_found;
if (!root_tag_get(root, tag))
return 0;
- node = rcu_dereference(root->rnode);
+ node = rcu_dereference_raw(root->rnode);
if (!node)
return 0;