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;
78 if (LNET_NIDNET(start_nid) != LNET_NIDNET(end_nid) ||
79 LNET_NIDADDR(start_nid) > LNET_NIDADDR(end_nid))
84 CERROR("cannot allocate lu_nid_range of size %zu bytes\n",
89 /* if we are loading from save, use on disk id num */
91 if (nm_range_tree->nmrt_range_highest_id < range_id)
92 nm_range_tree->nmrt_range_highest_id = range_id;
93 range->rn_id = range_id;
95 nm_range_tree->nmrt_range_highest_id++;
96 range->rn_id = nm_range_tree->nmrt_range_highest_id;
98 range->rn_nodemap = nodemap;
99 interval_set(&range->rn_node, start_nid, end_nid);
100 INIT_LIST_HEAD(&range->rn_list);
106 * find the exact range
108 * \param start_nid starting nid
109 * \param end_nid ending nid
110 * \retval matching range or NULL
112 struct lu_nid_range *range_find(struct nodemap_range_tree *nm_range_tree,
113 lnet_nid_t start_nid, lnet_nid_t end_nid)
115 struct lu_nid_range *range = NULL;
116 struct interval_node *interval = NULL;
117 struct interval_node_extent ext = {
122 interval = interval_find(nm_range_tree->nmrt_range_interval_root, &ext);
124 if (interval != NULL)
125 range = container_of(interval, struct lu_nid_range,
134 void range_destroy(struct lu_nid_range *range)
136 LASSERT(list_empty(&range->rn_list) == 0);
137 LASSERT(interval_is_intree(&range->rn_node) == 0);
143 * insert an nid range into the interval tree
145 * \param range range to insetr
146 * \retval 0 on success
148 * This function checks that the given nid range
149 * does not overlap so that each nid can belong
150 * to exactly one range
152 int range_insert(struct nodemap_range_tree *nm_range_tree,
153 struct lu_nid_range *range)
155 struct interval_node_extent ext =
156 range->rn_node.in_extent;
158 if (interval_is_overlapped(nm_range_tree->nmrt_range_interval_root,
162 interval_insert(&range->rn_node,
163 &nm_range_tree->nmrt_range_interval_root);
169 * delete a range from the interval tree and any
170 * associated nodemap references
172 * \param range range to remove
174 void range_delete(struct nodemap_range_tree *nm_range_tree,
175 struct lu_nid_range *range)
177 if (range == NULL || interval_is_intree(&range->rn_node) == 0)
179 list_del(&range->rn_list);
180 interval_erase(&range->rn_node,
181 &nm_range_tree->nmrt_range_interval_root);
182 range_destroy(range);
186 * search the interval tree for an nid within a range
188 * \param nid nid to search for
190 struct lu_nid_range *range_search(struct nodemap_range_tree *nm_range_tree,
193 struct lu_nid_range *ret = NULL;
194 struct interval_node_extent ext = {
199 interval_search(nm_range_tree->nmrt_range_interval_root, &ext,