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

[fs/lustre-release.git] / lustre / ptlrpc / nodemap_range.c

diff --git a/lustre/ptlrpc/nodemap_range.c b/lustre/ptlrpc/nodemap_range.c
index 59371b1..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>
  */
 
-#include <interval_tree.h>
 #include <lustre_net.h>
 #include "nodemap_internal.h"
+#include <linux/interval_tree_generic.h>
 
 /*
  * Range trees
@@ -40,34 +40,11 @@
  * controlled to prevent read access during update operations.
  */
 
-static struct interval_node *range_interval_root;
-static atomic_t range_highest_id;
+#define START(node)    ((node)->rn_start)
+#define LAST(node)     ((node)->rn_end)
 
-void range_init_tree(void)
-{
-       range_interval_root = NULL;
-}
-
-/*
- * callback for interating over the interval tree
- *
- * \param      n               interval_node matched
- * \param      data            void pointer for return
- *
- * This dunction 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;
-
-       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
@@ -77,8 +54,9 @@ static enum interval_iter range_cb(struct interval_node *n, void *data)
  * \param      nodemap         nodemap that contains this range
  * \retval     lu_nid_range on success, NULL on failure
  */
-struct lu_nid_range *range_create(lnet_nid_t start_nid, lnet_nid_t end_nid,
-                                 struct lu_nodemap *nodemap)
+struct lu_nid_range *range_create(struct nodemap_range_tree *nm_range_tree,
+                                 lnet_nid_t start_nid, lnet_nid_t end_nid,
+                                 struct lu_nodemap *nodemap, unsigned range_id)
 {
        struct lu_nid_range *range;
 
@@ -93,9 +71,20 @@ struct lu_nid_range *range_create(lnet_nid_t start_nid, lnet_nid_t end_nid,
                return NULL;
        }
 
-       range->rn_id = atomic_inc_return(&range_highest_id);
+       /* if we are loading from save, use on disk id num */
+       if (range_id != 0) {
+               if (nm_range_tree->nmrt_range_highest_id < range_id)
+                       nm_range_tree->nmrt_range_highest_id = range_id;
+               range->rn_id = range_id;
+       } else {
+               nm_range_tree->nmrt_range_highest_id++;
+               range->rn_id = nm_range_tree->nmrt_range_highest_id;
+       }
        range->rn_nodemap = nodemap;
-       interval_set(&range->rn_node, start_nid, end_nid);
+
+       range->rn_start = start_nid;
+       range->rn_end = end_nid;
+
        INIT_LIST_HEAD(&range->rn_list);
 
        return range;
@@ -108,20 +97,16 @@ struct lu_nid_range *range_create(lnet_nid_t start_nid, lnet_nid_t end_nid,
  * \param      end_nid                 ending nid
  * \retval     matching range or NULL
  */
-struct lu_nid_range *range_find(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(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;
 }
@@ -132,7 +117,6 @@ struct lu_nid_range *range_find(lnet_nid_t start_nid, lnet_nid_t end_nid)
 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);
 }
@@ -147,15 +131,15 @@ void range_destroy(struct lu_nid_range *range)
  * does not overlap so that each nid can belong
  * to exactly one range
  */
-int range_insert(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(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;
 
-       interval_insert(&range->rn_node, &range_interval_root);
+       nm_range_insert(range, &nm_range_tree->nmrt_range_interval_root);
 
        return 0;
 }
@@ -166,12 +150,11 @@ int range_insert(struct lu_nid_range *range)
  *
  * \param      range           range to remove
  */
-void range_delete(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);
-       interval_erase(&range->rn_node, &range_interval_root);
+       nm_range_remove(range, &nm_range_tree->nmrt_range_interval_root);
        range_destroy(range);
 }
 
@@ -180,15 +163,9 @@ void range_delete(struct lu_nid_range *range)
  *
  * \param      nid             nid to search for
  */
-struct lu_nid_range *range_search(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(range_interval_root, &ext, range_cb, &ret);
-
-       return ret;
+       return nm_range_iter_first(
+               &nm_range_tree->nmrt_range_interval_root, nid, nid);
 }