};
#define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
-#define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)
+#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
+ RADIX_TREE_MAP_SHIFT))
-static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH] __read_mostly;
+/*
+ * The height_to_maxindex array needs to be one deeper than the maximum
+ * path as height 0 holds only 1 entry.
+ */
+static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly;
/*
* Radix tree node cache.
struct radix_tree_node *ret;
gfp_t gfp_mask = root_gfp_mask(root);
- ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
+ ret = kmem_cache_alloc(radix_tree_node_cachep,
+ set_migrateflags(gfp_mask, __GFP_RECLAIMABLE));
if (ret == NULL && !(gfp_mask & __GFP_WAIT)) {
struct radix_tree_preload *rtp;
rtp->nr--;
}
}
- BUG_ON(radix_tree_is_direct_ptr(ret));
+ BUG_ON(radix_tree_is_indirect_ptr(ret));
return ret;
}
rtp = &__get_cpu_var(radix_tree_preloads);
while (rtp->nr < ARRAY_SIZE(rtp->nodes)) {
preempt_enable();
- node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
+ node = kmem_cache_alloc(radix_tree_node_cachep,
+ set_migrateflags(gfp_mask, __GFP_RECLAIMABLE));
if (node == NULL)
goto out;
preempt_disable();
return -ENOMEM;
/* Increase the height. */
- node->slots[0] = radix_tree_direct_to_ptr(root->rnode);
+ node->slots[0] = radix_tree_indirect_to_ptr(root->rnode);
/* Propagate the aggregated tag info into the new root */
for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
newheight = root->height+1;
node->height = newheight;
node->count = 1;
+ node = radix_tree_ptr_to_indirect(node);
rcu_assign_pointer(root->rnode, node);
root->height = newheight;
} while (height > root->height);
int offset;
int error;
- BUG_ON(radix_tree_is_direct_ptr(item));
+ BUG_ON(radix_tree_is_indirect_ptr(item));
/* Make sure the tree is high enough. */
if (index > radix_tree_maxindex(root->height)) {
return error;
}
- slot = root->rnode;
+ slot = radix_tree_indirect_to_ptr(root->rnode);
+
height = root->height;
shift = (height-1) * RADIX_TREE_MAP_SHIFT;
rcu_assign_pointer(node->slots[offset], slot);
node->count++;
} else
- rcu_assign_pointer(root->rnode, slot);
+ rcu_assign_pointer(root->rnode,
+ radix_tree_ptr_to_indirect(slot));
}
/* Go a level down */
BUG_ON(tag_get(node, 0, offset));
BUG_ON(tag_get(node, 1, offset));
} else {
- rcu_assign_pointer(root->rnode, radix_tree_ptr_to_direct(item));
+ rcu_assign_pointer(root->rnode, item);
BUG_ON(root_tag_get(root, 0));
BUG_ON(root_tag_get(root, 1));
}
if (node == NULL)
return NULL;
- if (radix_tree_is_direct_ptr(node)) {
+ if (!radix_tree_is_indirect_ptr(node)) {
if (index > 0)
return NULL;
return (void **)&root->rnode;
}
+ node = radix_tree_indirect_to_ptr(node);
height = node->height;
if (index > radix_tree_maxindex(height))
if (node == NULL)
return NULL;
- if (radix_tree_is_direct_ptr(node)) {
+ if (!radix_tree_is_indirect_ptr(node)) {
if (index > 0)
return NULL;
- return radix_tree_direct_to_ptr(node);
+ return node;
}
+ node = radix_tree_indirect_to_ptr(node);
height = node->height;
if (index > radix_tree_maxindex(height))
height = root->height;
BUG_ON(index > radix_tree_maxindex(height));
- slot = root->rnode;
+ slot = radix_tree_indirect_to_ptr(root->rnode);
shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
while (height > 0) {
void *radix_tree_tag_clear(struct radix_tree_root *root,
unsigned long index, unsigned int tag)
{
- struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
+ /*
+ * The radix tree path needs to be one longer than the maximum path
+ * since the "list" is null terminated.
+ */
+ struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
struct radix_tree_node *slot = NULL;
unsigned int height, shift;
shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
pathp->node = NULL;
- slot = root->rnode;
+ slot = radix_tree_indirect_to_ptr(root->rnode);
while (height > 0) {
int offset;
if (node == NULL)
return 0;
- if (radix_tree_is_direct_ptr(node))
+ if (!radix_tree_is_indirect_ptr(node))
return (index == 0);
+ node = radix_tree_indirect_to_ptr(node);
height = node->height;
if (index > radix_tree_maxindex(height))
EXPORT_SYMBOL(radix_tree_tag_get);
#endif
+/**
+ * radix_tree_next_hole - find the next hole (not-present entry)
+ * @root: tree root
+ * @index: index key
+ * @max_scan: maximum range to search
+ *
+ * Search the set [index, min(index+max_scan-1, MAX_INDEX)] for the lowest
+ * indexed hole.
+ *
+ * Returns: the index of the hole if found, otherwise returns an index
+ * outside of the set specified (in which case 'return - index >= max_scan'
+ * will be true).
+ *
+ * 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 the
+ * tree at a single point in time. For example, if a hole is created at index
+ * 5, then subsequently a hole is created at index 10, radix_tree_next_hole
+ * covering both indexes may return 10 if called under rcu_read_lock.
+ */
+unsigned long radix_tree_next_hole(struct radix_tree_root *root,
+ unsigned long index, unsigned long max_scan)
+{
+ unsigned long i;
+
+ for (i = 0; i < max_scan; i++) {
+ if (!radix_tree_lookup(root, index))
+ break;
+ index++;
+ if (index == 0)
+ break;
+ }
+
+ return index;
+}
+EXPORT_SYMBOL(radix_tree_next_hole);
+
static unsigned int
__lookup(struct radix_tree_node *slot, void **results, unsigned long index,
unsigned int max_items, unsigned long *next_index)
if (!node)
return 0;
- if (radix_tree_is_direct_ptr(node)) {
+ if (!radix_tree_is_indirect_ptr(node)) {
if (first_index > 0)
return 0;
- node = radix_tree_direct_to_ptr(node);
- results[0] = rcu_dereference(node);
+ results[0] = node;
return 1;
}
+ node = radix_tree_indirect_to_ptr(node);
max_index = radix_tree_maxindex(node->height);
if (!node)
return 0;
- if (radix_tree_is_direct_ptr(node)) {
+ if (!radix_tree_is_indirect_ptr(node)) {
if (first_index > 0)
return 0;
- node = radix_tree_direct_to_ptr(node);
- results[0] = rcu_dereference(node);
+ results[0] = node;
return 1;
}
+ node = radix_tree_indirect_to_ptr(node);
max_index = radix_tree_maxindex(node->height);
static inline void radix_tree_shrink(struct radix_tree_root *root)
{
/* try to shrink tree height */
- while (root->height > 0 &&
- root->rnode->count == 1 &&
- root->rnode->slots[0]) {
+ while (root->height > 0) {
struct radix_tree_node *to_free = root->rnode;
void *newptr;
+ BUG_ON(!radix_tree_is_indirect_ptr(to_free));
+ to_free = radix_tree_indirect_to_ptr(to_free);
+
+ /*
+ * The candidate node has more than one child, or its child
+ * is not at the leftmost slot, we cannot shrink.
+ */
+ if (to_free->count != 1)
+ break;
+ if (!to_free->slots[0])
+ break;
+
/*
* We don't need rcu_assign_pointer(), since we are simply
* moving the node from one part of the tree to another. If
* one (root->rnode).
*/
newptr = to_free->slots[0];
- if (root->height == 1)
- newptr = radix_tree_ptr_to_direct(newptr);
+ if (root->height > 1)
+ newptr = radix_tree_ptr_to_indirect(newptr);
root->rnode = newptr;
root->height--;
/* must only free zeroed nodes into the slab */
*/
void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
{
- struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
+ /*
+ * The radix tree path needs to be one longer than the maximum path
+ * since the "list" is null terminated.
+ */
+ struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
struct radix_tree_node *slot = NULL;
struct radix_tree_node *to_free;
unsigned int height, shift;
goto out;
slot = root->rnode;
- if (height == 0 && root->rnode) {
- slot = radix_tree_direct_to_ptr(slot);
+ if (height == 0) {
root_tag_clear_all(root);
root->rnode = NULL;
goto out;
}
+ slot = radix_tree_indirect_to_ptr(slot);
shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
pathp->node = NULL;
radix_tree_node_free(to_free);
if (pathp->node->count) {
- if (pathp->node == root->rnode)
+ if (pathp->node ==
+ radix_tree_indirect_to_ptr(root->rnode))
radix_tree_shrink(root);
goto out;
}
{
radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
sizeof(struct radix_tree_node), 0,
- SLAB_PANIC, radix_tree_node_ctor, NULL);
+ SLAB_PANIC, radix_tree_node_ctor);
radix_tree_init_maxindex();
hotcpu_notifier(radix_tree_callback, 0);
}
git.samba.org / sfrench / cifs-2.6.git / blobdiff