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)
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 nm_range_tree->nmrt_range_highest_id++;
90 range->rn_id = nm_range_tree->nmrt_range_highest_id;
91 range->rn_nodemap = nodemap;
92 interval_set(&range->rn_node, start_nid, end_nid);
93 INIT_LIST_HEAD(&range->rn_list);
99 * find the exact range
101 * \param start_nid starting nid
102 * \param end_nid ending nid
103 * \retval matching range or NULL
105 struct lu_nid_range *range_find(struct nodemap_range_tree *nm_range_tree,
106 lnet_nid_t start_nid, lnet_nid_t end_nid)
108 struct lu_nid_range *range = NULL;
109 struct interval_node *interval = NULL;
110 struct interval_node_extent ext = {
115 interval = interval_find(nm_range_tree->nmrt_range_interval_root, &ext);
117 if (interval != NULL)
118 range = container_of(interval, struct lu_nid_range,
127 void range_destroy(struct lu_nid_range *range)
129 LASSERT(list_empty(&range->rn_list) == 0);
130 LASSERT(interval_is_intree(&range->rn_node) == 0);
136 * insert an nid range into the interval tree
138 * \param range range to insetr
139 * \retval 0 on success
141 * This function checks that the given nid range
142 * does not overlap so that each nid can belong
143 * to exactly one range
145 int range_insert(struct nodemap_range_tree *nm_range_tree,
146 struct lu_nid_range *range)
148 struct interval_node_extent ext =
149 range->rn_node.in_extent;
151 if (interval_is_overlapped(nm_range_tree->nmrt_range_interval_root,
155 interval_insert(&range->rn_node,
156 &nm_range_tree->nmrt_range_interval_root);
162 * delete a range from the interval tree and any
163 * associated nodemap references
165 * \param range range to remove
167 void range_delete(struct nodemap_range_tree *nm_range_tree,
168 struct lu_nid_range *range)
170 if (range == NULL || interval_is_intree(&range->rn_node) == 0)
172 list_del(&range->rn_list);
173 interval_erase(&range->rn_node,
174 &nm_range_tree->nmrt_range_interval_root);
175 range_destroy(range);
179 * search the interval tree for an nid within a range
181 * \param nid nid to search for
183 struct lu_nid_range *range_search(struct nodemap_range_tree *nm_range_tree,
186 struct lu_nid_range *ret = NULL;
187 struct interval_node_extent ext = {
192 interval_search(nm_range_tree->nmrt_range_interval_root, &ext,