From f55fdfff5dede69e6674999fb02c1add513704f0 Mon Sep 17 00:00:00 2001 From: Mr NeilBrown Date: Tue, 25 Aug 2020 10:03:17 +1000 Subject: [PATCH] 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 Change-Id: I7bf119bf8cd8f14dc66deb2736c2c97562bb0743 Reviewed-on: https://review.whamcloud.com/39724 Tested-by: jenkins Tested-by: Maloo Reviewed-by: James Simmons Reviewed-by: Andreas Dilger Reviewed-by: Oleg Drokin --- libcfs/include/libcfs/libcfs.h | 10 +++++ lustre/autoconf/lustre-core.m4 | 28 ++++++++++++++ lustre/include/lustre_nodemap.h | 3 +- lustre/ptlrpc/nodemap_handler.c | 2 + lustre/ptlrpc/nodemap_internal.h | 7 +++- lustre/ptlrpc/nodemap_lproc.c | 6 +-- lustre/ptlrpc/nodemap_range.c | 79 ++++++++++------------------------------ lustre/ptlrpc/nodemap_storage.c | 4 +- 8 files changed, 71 insertions(+), 68 deletions(-) diff --git a/libcfs/include/libcfs/libcfs.h b/libcfs/include/libcfs/libcfs.h index 9ef72e4..5fa92df 100644 --- 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); +/* 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_ */ diff --git a/lustre/autoconf/lustre-core.m4 b/lustre/autoconf/lustre-core.m4 index 7eeefa8..09e256a 100644 --- a/lustre/autoconf/lustre-core.m4 +++ b/lustre/autoconf/lustre-core.m4 @@ -1989,6 +1989,33 @@ 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 + 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 @@ -2470,6 +2497,7 @@ AC_DEFUN([LC_PROG_LINUX], [ # 4.14 LC_PAGEVEC_INIT_ONE_PARAM LC_BI_BDEV + LC_INTERVAL_TREE_CACHED # 4.17 LC_VM_FAULT_T diff --git a/lustre/include/lustre_nodemap.h b/lustre/include/lustre_nodemap.h index 199dc79..e8e8e41 100644 --- 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 + 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; }; diff --git a/lustre/ptlrpc/nodemap_handler.c b/lustre/ptlrpc/nodemap_handler.c index 44fc2f2..5fc80bf 100644 --- 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); + config->nmc_range_tree.nmrt_range_interval_root = INTERVAL_TREE_ROOT; + 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 --- a/lustre/ptlrpc/nodemap_internal.h +++ b/lustre/ptlrpc/nodemap_internal.h @@ -31,7 +31,7 @@ #define _NODEMAP_INTERNAL_H #include -#include +#include #define DEFAULT_NODEMAP "default" @@ -58,7 +58,10 @@ struct lu_nid_range { /* 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 { diff --git a/lustre/ptlrpc/nodemap_lproc.c b/lustre/ptlrpc/nodemap_lproc.c index 87feff4..2539522 100644 --- 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 interval_node_extent ext; 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; - 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); } diff --git a/lustre/ptlrpc/nodemap_range.c b/lustre/ptlrpc/nodemap_range.c index da7143f..ca08d11 100644 --- a/lustre/ptlrpc/nodemap_range.c +++ b/lustre/ptlrpc/nodemap_range.c @@ -24,9 +24,9 @@ * Author: Joshua Walgenbach */ -#include #include #include "nodemap_internal.h" +#include /* * Range trees @@ -40,26 +40,11 @@ * 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 @@ -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; - int rc; 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; - 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); @@ -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 = 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; } @@ -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); - LASSERT(interval_is_intree(&range->rn_node) == 0); 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) { - 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; - 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; } @@ -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) { - if (range == NULL || interval_is_intree(&range->rn_node) == 0) - return; 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); } @@ -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 *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 --- 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] = { - 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); -- 1.8.3.1