4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License version 2 only,
8 * as published by the Free Software Foundation.
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License version 2 for more details (a copy is included
14 * in the LICENSE file that accompanied this code).
16 * You should have received a copy of the GNU General Public License
17 * version 2 along with this program; If not, see
18 * http://www.gnu.org/licenses/gpl-2.0.html
23 * Copyright (C) 2013, Trustees of Indiana University
24 * Author: Joshua Walgenbach <jjw@iu.edu>
27 #include <interval_tree.h>
28 #include <lustre_net.h>
29 #include "nodemap_internal.h"
34 * To classify clients when they connect, build a global range tree
35 * containing all admin defined ranges. Incoming clients can then be
36 * classified into their nodemaps, and the lu_nodemap structure will be
37 * set in the export structure for the connecting client. Pointers to
38 * the lu_nid_range nodes will be added to linked links within the
39 * lu_nodemap structure for reporting purposes. Access to range tree should be
40 * controlled to prevent read access during update operations.
44 * callback for iterating over the interval tree
46 * \param n interval_node matched
47 * \param data void pointer for return
49 * This function stops after a single match. There should be
50 * no intervals containing multiple ranges
52 static enum interval_iter range_cb(struct interval_node *n, void *data)
54 struct lu_nid_range *range = container_of(n, struct lu_nid_range,
56 struct lu_nid_range **ret;
61 return INTERVAL_ITER_STOP;
67 * \param min starting nid of the range
68 * \param max ending nid of the range
69 * \param nodemap nodemap that contains this range
70 * \retval lu_nid_range on success, NULL on failure
72 struct lu_nid_range *range_create(struct nodemap_range_tree *nm_range_tree,
73 lnet_nid_t start_nid, lnet_nid_t end_nid,
74 struct lu_nodemap *nodemap, unsigned range_id)
76 struct lu_nid_range *range;
79 if (LNET_NIDNET(start_nid) != LNET_NIDNET(end_nid) ||
80 LNET_NIDADDR(start_nid) > LNET_NIDADDR(end_nid))
85 CERROR("cannot allocate lu_nid_range of size %zu bytes\n",
90 /* if we are loading from save, use on disk id num */
92 if (nm_range_tree->nmrt_range_highest_id < range_id)
93 nm_range_tree->nmrt_range_highest_id = range_id;
94 range->rn_id = range_id;
96 nm_range_tree->nmrt_range_highest_id++;
97 range->rn_id = nm_range_tree->nmrt_range_highest_id;
99 range->rn_nodemap = nodemap;
101 rc = interval_set(&range->rn_node, start_nid, end_nid);
107 INIT_LIST_HEAD(&range->rn_list);
113 * find the exact range
115 * \param start_nid starting nid
116 * \param end_nid ending nid
117 * \retval matching range or NULL
119 struct lu_nid_range *range_find(struct nodemap_range_tree *nm_range_tree,
120 lnet_nid_t start_nid, lnet_nid_t end_nid)
122 struct lu_nid_range *range = NULL;
123 struct interval_node *interval = NULL;
124 struct interval_node_extent ext = {
129 interval = interval_find(nm_range_tree->nmrt_range_interval_root, &ext);
131 if (interval != NULL)
132 range = container_of(interval, struct lu_nid_range,
141 void range_destroy(struct lu_nid_range *range)
143 LASSERT(list_empty(&range->rn_list) == 0);
144 LASSERT(interval_is_intree(&range->rn_node) == 0);
150 * insert an nid range into the interval tree
152 * \param range range to insetr
153 * \retval 0 on success
155 * This function checks that the given nid range
156 * does not overlap so that each nid can belong
157 * to exactly one range
159 int range_insert(struct nodemap_range_tree *nm_range_tree,
160 struct lu_nid_range *range)
162 struct interval_node_extent ext =
163 range->rn_node.in_extent;
165 if (interval_is_overlapped(nm_range_tree->nmrt_range_interval_root,
169 interval_insert(&range->rn_node,
170 &nm_range_tree->nmrt_range_interval_root);
176 * delete a range from the interval tree and any
177 * associated nodemap references
179 * \param range range to remove
181 void range_delete(struct nodemap_range_tree *nm_range_tree,
182 struct lu_nid_range *range)
184 if (range == NULL || interval_is_intree(&range->rn_node) == 0)
186 list_del(&range->rn_list);
187 interval_erase(&range->rn_node,
188 &nm_range_tree->nmrt_range_interval_root);
189 range_destroy(range);
193 * search the interval tree for an nid within a range
195 * \param nid nid to search for
197 struct lu_nid_range *range_search(struct nodemap_range_tree *nm_range_tree,
200 struct lu_nid_range *ret = NULL;
201 struct interval_node_extent ext = {
206 interval_search(nm_range_tree->nmrt_range_interval_root, &ext,