LU-11085 nodemap: switch interval tree to in-kernel impl.

Switch nodemap_range to use the in-kernel interval tree.
This has the same functionality, though often in a different form.

Signed-off-by: Mr NeilBrown <neilb@suse.de>
Change-Id: I7bf119bf8cd8f14dc66deb2736c2c97562bb0743
Reviewed-on: https://review.whamcloud.com/39724
Tested-by: jenkins <devops@whamcloud.com>
Tested-by: Maloo <maloo@whamcloud.com>
Reviewed-by: James Simmons <jsimmons@infradead.org>
Reviewed-by: Andreas Dilger <adilger@whamcloud.com>
Reviewed-by: Oleg Drokin <green@whamcloud.com>

diff --git a/libcfs/include/libcfs/libcfs.h b/libcfs/include/libcfs/libcfs.h
index 9ef72e4..5fa92df 100644 (file)
--- a/libcfs/include/libcfs/libcfs.h
+++ b/libcfs/include/libcfs/libcfs.h
@@ -128,4 +128,14 @@ do {                                                                       \
 /* atomic-context safe vfree */
 void libcfs_vfree_atomic(const void *addr);
 
 /* atomic-context safe vfree */
 void libcfs_vfree_atomic(const void *addr);
 

+/* interval tree */
+
+#ifdef HAVE_INTERVAL_TREE_CACHED
+#define interval_tree_root rb_root_cached
+#define INTERVAL_TREE_ROOT RB_ROOT_CACHED
+#else
+#define interval_tree_root rb_root
+#define INTERVAL_TREE_ROOT RB_ROOT
+#endif /* HAVE_INTERVAL_TREE_CACHED */
+

 #endif /* _LIBCFS_LIBCFS_H_ */
 #endif /* _LIBCFS_LIBCFS_H_ */

diff --git a/lustre/autoconf/lustre-core.m4 b/lustre/autoconf/lustre-core.m4
index 7eeefa8..09e256a 100644 (file)
--- a/lustre/autoconf/lustre-core.m4
+++ b/lustre/autoconf/lustre-core.m4
@@ -1989,6 +1989,33 @@ bi_bdev, [
 ]) # LC_BI_BDEV
 
 #
 ]) # LC_BI_BDEV
 
 #

+# LC_INTERVAL_TREE_CACHED
+#
+# 4.14 f808c13fd3738948e10196496959871130612b61
+# switched INTERVAL_TREE_DEFINE to use cached RB_Trees.
+#
+AC_DEFUN([LC_INTERVAL_TREE_CACHED], [
+tmp_flags="$EXTRA_KCFLAGS"
+EXTRA_KCFLAGS="-Werror"
+LB_CHECK_COMPILE([if interval_trees use rb_tree_cached],
+itree_cached, [
+       #include <linux/interval_tree_generic.h>
+       struct foo { struct rb_node rb; int last; int a,b;};
+       #define START(n) ((n)->a)
+       #define LAST(n) ((n)->b)
+       struct rb_root_cached tree;
+       INTERVAL_TREE_DEFINE(struct foo, rb, int, last,
+               START, LAST, , foo);
+],[
+       foo_insert(NULL, &tree);
+],[
+       AC_DEFINE(HAVE_INTERVAL_TREE_CACHED, 1,
+               [interval trees use rb_tree_cached])
+])
+EXTRA_KCFLAGS="$tmp_flags"
+]) # LC_INTERVAL_TREE_CACHED
+
+#

 # LC_IS_ENCRYPTED
 #
 # 4.14 introduced IS_ENCRYPTED and S_ENCRYPTED
 # LC_IS_ENCRYPTED
 #
 # 4.14 introduced IS_ENCRYPTED and S_ENCRYPTED


@@ -2470,6 +2497,7 @@ AC_DEFUN([LC_PROG_LINUX], [
        # 4.14
        LC_PAGEVEC_INIT_ONE_PARAM
        LC_BI_BDEV
        # 4.14
        LC_PAGEVEC_INIT_ONE_PARAM
        LC_BI_BDEV

+       LC_INTERVAL_TREE_CACHED

 
        # 4.17
        LC_VM_FAULT_T
 
        # 4.17
        LC_VM_FAULT_T

diff --git a/lustre/include/lustre_nodemap.h b/lustre/include/lustre_nodemap.h
index 199dc79..e8e8e41 100644 (file)
--- a/lustre/include/lustre_nodemap.h
+++ b/lustre/include/lustre_nodemap.h
@@ -178,8 +178,9 @@ struct lu_nodemap *nodemap_get_from_exp(struct obd_export *exp);
 void nodemap_putref(struct lu_nodemap *nodemap);
 
 #ifdef HAVE_SERVER_SUPPORT
 void nodemap_putref(struct lu_nodemap *nodemap);
 
 #ifdef HAVE_SERVER_SUPPORT

+

 struct nodemap_range_tree {
 struct nodemap_range_tree {

-       struct interval_node *nmrt_range_interval_root;
+       struct interval_tree_root nmrt_range_interval_root;

        unsigned int nmrt_range_highest_id;
 };
 
        unsigned int nmrt_range_highest_id;
 };
 

diff --git a/lustre/ptlrpc/nodemap_handler.c b/lustre/ptlrpc/nodemap_handler.c
index 44fc2f2..5fc80bf 100644 (file)
--- a/lustre/ptlrpc/nodemap_handler.c
+++ b/lustre/ptlrpc/nodemap_handler.c
@@ -1622,6 +1622,8 @@ struct nodemap_config *nodemap_config_alloc(void)
 
        init_rwsem(&config->nmc_range_tree_lock);
 
 
        init_rwsem(&config->nmc_range_tree_lock);
 

+       config->nmc_range_tree.nmrt_range_interval_root = INTERVAL_TREE_ROOT;
+

        return config;
 }
 EXPORT_SYMBOL(nodemap_config_alloc);
        return config;
 }
 EXPORT_SYMBOL(nodemap_config_alloc);

diff --git a/lustre/ptlrpc/nodemap_internal.h b/lustre/ptlrpc/nodemap_internal.h
index 4b8312e..96636ae 100644 (file)
--- a/lustre/ptlrpc/nodemap_internal.h
+++ b/lustre/ptlrpc/nodemap_internal.h
@@ -31,7 +31,7 @@
 #define _NODEMAP_INTERNAL_H
 
 #include <lustre_nodemap.h>
 #define _NODEMAP_INTERNAL_H
 
 #include <lustre_nodemap.h>

-#include <interval_tree.h>
+#include <linux/rbtree.h>

 
 #define DEFAULT_NODEMAP "default"
 
 
 #define DEFAULT_NODEMAP "default"
 


@@ -58,7 +58,10 @@ struct lu_nid_range {
        /* list for nodemap */
        struct list_head         rn_list;
        /* nid interval tree */
        /* list for nodemap */
        struct list_head         rn_list;
        /* nid interval tree */

-       struct interval_node     rn_node;
+       lnet_nid_t               rn_start,
+                                rn_end,
+                                rn_subtree_last;
+       struct rb_node           rn_rb;

 };
 
 struct lu_idmap {
 };
 
 struct lu_idmap {

diff --git a/lustre/ptlrpc/nodemap_lproc.c b/lustre/ptlrpc/nodemap_lproc.c
index 87feff4..2539522 100644 (file)
--- a/lustre/ptlrpc/nodemap_lproc.c
+++ b/lustre/ptlrpc/nodemap_lproc.c
@@ -118,7 +118,6 @@ static int nodemap_ranges_show(struct seq_file *m, void *data)
 {
        struct lu_nodemap               *nodemap;
        struct lu_nid_range             *range;
 {
        struct lu_nodemap               *nodemap;
        struct lu_nid_range             *range;

-       struct interval_node_extent     ext;

        char                            start_nidstr[LNET_NIDSTR_SIZE];
        char                            end_nidstr[LNET_NIDSTR_SIZE];
        bool                            cont = false;
        char                            start_nidstr[LNET_NIDSTR_SIZE];
        char                            end_nidstr[LNET_NIDSTR_SIZE];
        bool                            cont = false;


@@ -140,9 +139,8 @@ static int nodemap_ranges_show(struct seq_file *m, void *data)
                if (cont)
                        seq_printf(m, ",\n");
                cont = 1;
                if (cont)
                        seq_printf(m, ",\n");
                cont = 1;

-               ext = range->rn_node.in_extent;
-               libcfs_nid2str_r(ext.start, start_nidstr, sizeof(start_nidstr));
-               libcfs_nid2str_r(ext.end, end_nidstr, sizeof(end_nidstr));
+               libcfs_nid2str_r(range->rn_start, start_nidstr, sizeof(start_nidstr));
+               libcfs_nid2str_r(range->rn_end, end_nidstr, sizeof(end_nidstr));

                seq_printf(m, " { id: %u, start_nid: %s, end_nid: %s }",
                           range->rn_id, start_nidstr, end_nidstr);
        }
                seq_printf(m, " { id: %u, start_nid: %s, end_nid: %s }",
                           range->rn_id, start_nidstr, end_nidstr);
        }

diff --git a/lustre/ptlrpc/nodemap_range.c b/lustre/ptlrpc/nodemap_range.c
index da7143f..ca08d11 100644 (file)
--- a/lustre/ptlrpc/nodemap_range.c
+++ b/lustre/ptlrpc/nodemap_range.c
@@ -24,9 +24,9 @@
  * Author: Joshua Walgenbach <jjw@iu.edu>
  */
 
  * Author: Joshua Walgenbach <jjw@iu.edu>
  */
 

-#include <interval_tree.h>

 #include <lustre_net.h>
 #include "nodemap_internal.h"
 #include <lustre_net.h>
 #include "nodemap_internal.h"

+#include <linux/interval_tree_generic.h>

 
 /*
  * Range trees
 
 /*
  * Range trees


@@ -40,26 +40,11 @@
  * controlled to prevent read access during update operations.
  */
 
  * controlled to prevent read access during update operations.
  */
 

-/*
- * callback for iterating over the interval tree
- *
- * \param      n               interval_node matched
- * \param      data            void pointer for return
- *
- * This function stops after a single match. There should be
- * no intervals containing multiple ranges
- */
-static enum interval_iter range_cb(struct interval_node *n, void *data)
-{
-       struct lu_nid_range     *range = container_of(n, struct lu_nid_range,
-                                                     rn_node);
-       struct lu_nid_range     **ret;
-
-       ret = data;
-       *ret = range;
+#define START(node)    ((node)->rn_start)
+#define LAST(node)     ((node)->rn_end)

 
 

-       return INTERVAL_ITER_STOP;
-}
+INTERVAL_TREE_DEFINE(struct lu_nid_range, rn_rb, lnet_nid_t, rn_subtree_last,
+                    START, LAST, static, nm_range)

 
 /*
  * range constructor
 
 /*
  * range constructor


@@ -74,7 +59,6 @@ struct lu_nid_range *range_create(struct nodemap_range_tree *nm_range_tree,
                                  struct lu_nodemap *nodemap, unsigned range_id)
 {
        struct lu_nid_range *range;
                                  struct lu_nodemap *nodemap, unsigned range_id)
 {
        struct lu_nid_range *range;

-       int rc;

 
        if (LNET_NIDNET(start_nid) != LNET_NIDNET(end_nid) ||
            LNET_NIDADDR(start_nid) > LNET_NIDADDR(end_nid))
 
        if (LNET_NIDNET(start_nid) != LNET_NIDNET(end_nid) ||
            LNET_NIDADDR(start_nid) > LNET_NIDADDR(end_nid))


@@ -98,11 +82,8 @@ struct lu_nid_range *range_create(struct nodemap_range_tree *nm_range_tree,
        }
        range->rn_nodemap = nodemap;
 
        }
        range->rn_nodemap = nodemap;
 

-       rc = interval_set(&range->rn_node, start_nid, end_nid);
-       if (rc < 0) {
-               OBD_FREE_PTR(range);
-               return NULL;
-       }
+       range->rn_start = start_nid;
+       range->rn_end = end_nid;

 
        INIT_LIST_HEAD(&range->rn_list);
 
 
        INIT_LIST_HEAD(&range->rn_list);
 


@@ -119,18 +100,13 @@ struct lu_nid_range *range_create(struct nodemap_range_tree *nm_range_tree,
 struct lu_nid_range *range_find(struct nodemap_range_tree *nm_range_tree,
                                lnet_nid_t start_nid, lnet_nid_t end_nid)
 {
 struct lu_nid_range *range_find(struct nodemap_range_tree *nm_range_tree,
                                lnet_nid_t start_nid, lnet_nid_t end_nid)
 {

-       struct lu_nid_range             *range = NULL;
-       struct interval_node            *interval = NULL;
-       struct interval_node_extent     ext = {
-               .start  = start_nid,
-               .end    = end_nid
-       };
-
-       interval = interval_find(nm_range_tree->nmrt_range_interval_root, &ext);
+       struct lu_nid_range *range;

 
 

-       if (interval != NULL)
-               range = container_of(interval, struct lu_nid_range,
-                                    rn_node);
+       range = nm_range_iter_first(
+               &nm_range_tree->nmrt_range_interval_root, start_nid, end_nid);
+       while (range &&
+              (range->rn_start != start_nid || range->rn_end != end_nid))
+               range = nm_range_iter_next(range, start_nid, end_nid);

 
        return range;
 }
 
        return range;
 }


@@ -141,7 +117,6 @@ struct lu_nid_range *range_find(struct nodemap_range_tree *nm_range_tree,
 void range_destroy(struct lu_nid_range *range)
 {
        LASSERT(list_empty(&range->rn_list) == 0);
 void range_destroy(struct lu_nid_range *range)
 {
        LASSERT(list_empty(&range->rn_list) == 0);

-       LASSERT(interval_is_intree(&range->rn_node) == 0);

 
        OBD_FREE_PTR(range);
 }
 
        OBD_FREE_PTR(range);
 }


@@ -159,15 +134,12 @@ void range_destroy(struct lu_nid_range *range)
 int range_insert(struct nodemap_range_tree *nm_range_tree,
                 struct lu_nid_range *range)
 {
 int range_insert(struct nodemap_range_tree *nm_range_tree,
                 struct lu_nid_range *range)
 {

-       struct interval_node_extent ext =
-                       range->rn_node.in_extent;
-
-       if (interval_is_overlapped(nm_range_tree->nmrt_range_interval_root,
-                                  &ext) != 0)
+       if (nm_range_iter_first(&nm_range_tree->nmrt_range_interval_root,
+                               range->rn_start,
+                               range->rn_end))

                return -EEXIST;
 
                return -EEXIST;
 

-       interval_insert(&range->rn_node,
-                       &nm_range_tree->nmrt_range_interval_root);
+       nm_range_insert(range, &nm_range_tree->nmrt_range_interval_root);

 
        return 0;
 }
 
        return 0;
 }


@@ -181,11 +153,8 @@ int range_insert(struct nodemap_range_tree *nm_range_tree,
 void range_delete(struct nodemap_range_tree *nm_range_tree,
                  struct lu_nid_range *range)
 {
 void range_delete(struct nodemap_range_tree *nm_range_tree,
                  struct lu_nid_range *range)
 {

-       if (range == NULL || interval_is_intree(&range->rn_node) == 0)
-               return;

        list_del(&range->rn_list);
        list_del(&range->rn_list);

-       interval_erase(&range->rn_node,
-                      &nm_range_tree->nmrt_range_interval_root);
+       nm_range_remove(range, &nm_range_tree->nmrt_range_interval_root);

        range_destroy(range);
 }
 
        range_destroy(range);
 }
 


@@ -197,14 +166,6 @@ void range_delete(struct nodemap_range_tree *nm_range_tree,
 struct lu_nid_range *range_search(struct nodemap_range_tree *nm_range_tree,
                                  lnet_nid_t nid)
 {
 struct lu_nid_range *range_search(struct nodemap_range_tree *nm_range_tree,
                                  lnet_nid_t nid)
 {

-       struct lu_nid_range             *ret = NULL;
-       struct interval_node_extent     ext = {
-               .start  = nid,
-               .end    = nid
-       };
-
-       interval_search(nm_range_tree->nmrt_range_interval_root, &ext,
-                       range_cb, &ret);
-
-       return ret;
+       return nm_range_iter_first(
+               &nm_range_tree->nmrt_range_interval_root, nid, nid);

 }
 }

diff --git a/lustre/ptlrpc/nodemap_storage.c b/lustre/ptlrpc/nodemap_storage.c
index 0cbafb7..ef559ca 100644 (file)
--- a/lustre/ptlrpc/nodemap_storage.c
+++ b/lustre/ptlrpc/nodemap_storage.c
@@ -1019,8 +1019,8 @@ struct dt_object *nodemap_save_config_cache(const struct lu_env *env,
                list_for_each_entry_safe(range, range_temp, &nodemap->nm_ranges,
                                         rn_list) {
                        lnet_nid_t nid[2] = {
                list_for_each_entry_safe(range, range_temp, &nodemap->nm_ranges,
                                         rn_list) {
                        lnet_nid_t nid[2] = {

-                               range->rn_node.in_extent.start,
-                               range->rn_node.in_extent.end
+                               range->rn_start,
+                               range->rn_end

                        };
                        nodemap_range_key_init(&nk, nodemap->nm_id,
                                               range->rn_id);
                        };
                        nodemap_range_key_init(&nk, nodemap->nm_id,
                                               range->rn_id);