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.A
42 static struct interval_node *range_interval_root;
43 static atomic_t range_highest_id;
45 void range_init_tree(void)
47 range_interval_root = NULL;
51 * callback for interating over the interval tree
53 * \param n interval_node matched
54 * \param data void pointer for return
56 * This dunction stops after a single match. There should be
57 * no intervals containing multiple ranges
59 static enum interval_iter range_cb(struct interval_node *n, void *data)
61 struct lu_nid_range *range = container_of(n, struct lu_nid_range,
63 struct lu_nid_range **ret;
68 return INTERVAL_ITER_STOP;
74 * \param min starting nid of the range
75 * \param max ending nid of the range
76 * \param nodemap nodemap that contains this range
77 * \retval lu_nid_range on success, NULL on failure
79 struct lu_nid_range *range_create(lnet_nid_t start_nid, lnet_nid_t end_nid,
80 struct lu_nodemap *nodemap)
82 struct lu_nid_range *range;
84 if (LNET_NIDNET(start_nid) != LNET_NIDNET(end_nid) ||
85 LNET_NIDADDR(start_nid) > LNET_NIDADDR(end_nid))
90 CERROR("cannot allocate lu_nid_range of size %zu bytes\n",
95 range->rn_id = atomic_inc_return(&range_highest_id);
96 range->rn_nodemap = nodemap;
97 interval_set(&range->rn_node, start_nid, end_nid);
98 INIT_LIST_HEAD(&range->rn_list);
104 * find the exact range
106 * \param start_nid starting nid
107 * \param end_nid ending nid
108 * \retval matching range or NULL
110 struct lu_nid_range *range_find(lnet_nid_t start_nid, lnet_nid_t end_nid)
112 struct lu_nid_range *range = NULL;
113 struct interval_node *interval = NULL;
114 struct interval_node_extent ext = {
119 interval = interval_find(range_interval_root, &ext);
121 if (interval != NULL)
122 range = container_of(interval, struct lu_nid_range,
131 void range_destroy(struct lu_nid_range *range)
133 LASSERT(list_empty(&range->rn_list) == 0);
134 LASSERT(interval_is_intree(&range->rn_node) == 0);
140 * insert an nid range into the interval tree
142 * \param range range to insetr
143 * \retval 0 on success
145 * This function checks that the given nid range
146 * does not overlap so that each nid can belong
147 * to exactly one range
149 int range_insert(struct lu_nid_range *range)
151 struct interval_node_extent ext =
152 range->rn_node.in_extent;
154 if (interval_is_overlapped(range_interval_root, &ext) != 0)
157 interval_insert(&range->rn_node, &range_interval_root);
163 * delete a range from the interval tree and any
164 * associated nodemap references
166 * \param range range to remove
168 void range_delete(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, &range_interval_root);
174 range_destroy(range);
178 * search the interval tree for an nid within a range
180 * \param nid nid to search for
182 struct lu_nid_range *range_search(lnet_nid_t nid)
184 struct lu_nid_range *ret = NULL;
185 struct interval_node_extent ext = {
190 interval_search(range_interval_root, &ext, range_cb, &ret);