radix-tree: Store a pointer to the root in each node

Instead of having this mysterious private_data in each radix_tree_node,
store a pointer to the root, which can be useful for debugging.  This also
relieves the mm code from the duty of updating it.

Acked-by: Johannes Weiner <hannes@cmpxchg.org>
Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>

diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 2ba0c1f46c84bc858f3219c2c53bbe8091ef6df5..d250059bbfa41d14ea3bb82278f3d5fbb3339cb6 100644 (file)
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -96,7 +96,7 @@ struct radix_tree_node {
        unsigned char   count;          /* Total entry count */
        unsigned char   exceptional;    /* Exceptional entry count */
        struct radix_tree_node *parent;         /* Used when ascending tree */
-       void *private_data;                     /* For tree user */
+       struct radix_tree_root *root;           /* The tree we belong to */
        union {
                struct list_head private_list;  /* For tree user */
                struct rcu_head rcu_head;       /* Used when freeing node */

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 66c71312c381e8acac14bdaf94ecaff30ae320fb..dcb9a2329e65adc02406344c6f03fa297b8827f1 100644 (file)
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -374,6 +374,7 @@ static void ida_dump(struct ida *ida)
  */
 static struct radix_tree_node *
 radix_tree_node_alloc(gfp_t gfp_mask, struct radix_tree_node *parent,
+                       struct radix_tree_root *root,
                        unsigned int shift, unsigned int offset,
                        unsigned int count, unsigned int exceptional)
 {
@@ -419,11 +420,12 @@ radix_tree_node_alloc(gfp_t gfp_mask, struct radix_tree_node *parent,
 out:
        BUG_ON(radix_tree_is_internal_node(ret));
        if (ret) {
-               ret->parent = parent;
                ret->shift = shift;
                ret->offset = offset;
                ret->count = count;
                ret->exceptional = exceptional;
+               ret->parent = parent;
+               ret->root = root;
        }
        return ret;
 }
@@ -631,7 +633,7 @@ static int radix_tree_extend(struct radix_tree_root *root, gfp_t gfp,
 
        do {
                struct radix_tree_node *node = radix_tree_node_alloc(gfp, NULL,
-                                                               shift, 0, 1, 0);
+                                                       root, shift, 0, 1, 0);
                if (!node)
                        return -ENOMEM;
 
@@ -828,7 +830,7 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
                shift -= RADIX_TREE_MAP_SHIFT;
                if (child == NULL) {
                        /* Have to add a child node.  */
-                       child = radix_tree_node_alloc(gfp, node, shift,
+                       child = radix_tree_node_alloc(gfp, node, root, shift,
                                                        offset, 0, 0);
                        if (!child)
                                return -ENOMEM;
@@ -1330,7 +1332,7 @@ int radix_tree_split(struct radix_tree_root *root, unsigned long index,
 
        for (;;) {
                if (node->shift > order) {
-                       child = radix_tree_node_alloc(gfp, node,
+                       child = radix_tree_node_alloc(gfp, node, root,
                                        node->shift - RADIX_TREE_MAP_SHIFT,
                                        offset, 0, 0);
                        if (!child)
@@ -2152,8 +2154,8 @@ void **idr_get_free(struct radix_tree_root *root,
                shift -= RADIX_TREE_MAP_SHIFT;
                if (child == NULL) {
                        /* Have to add a child node.  */
-                       child = radix_tree_node_alloc(gfp, node, shift, offset,
-                                                       0, 0);
+                       child = radix_tree_node_alloc(gfp, node, root, shift,
+                                                       offset, 0, 0);
                        if (!child)
                                return ERR_PTR(-ENOMEM);
                        all_tag_set(child, IDR_FREE);

diff --git a/mm/workingset.c b/mm/workingset.c
index abb58ffa3c64cb330d7e3d7aca7897aab0fea6a4..80c913c89f116af469fbd46bc46ad7149ed870ab 100644 (file)
--- a/mm/workingset.c
+++ b/mm/workingset.c
@@ -354,10 +354,8 @@ void workingset_update_node(struct radix_tree_node *node, void *private)
         * as node->private_list is protected by &mapping->tree_lock.
         */
        if (node->count && node->count == node->exceptional) {
-               if (list_empty(&node->private_list)) {
-                       node->private_data = mapping;
+               if (list_empty(&node->private_list))
                        list_lru_add(&shadow_nodes, &node->private_list);
-               }
        } else {
                if (!list_empty(&node->private_list))
                        list_lru_del(&shadow_nodes, &node->private_list);
@@ -435,7 +433,7 @@ static enum lru_status shadow_lru_isolate(struct list_head *item,
         */
 
        node = container_of(item, struct radix_tree_node, private_list);
-       mapping = node->private_data;
+       mapping = container_of(node->root, struct address_space, page_tree);
 
        /* Coming from the list, invert the lock order */
        if (!spin_trylock(&mapping->tree_lock)) {