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.
43 static struct interval_node *range_interval_root;
44 static atomic_t range_highest_id;
46 void range_init_tree(void)
48 range_interval_root = NULL;
52 * callback for iterating over the interval tree
54 * \param n interval_node matched
55 * \param data void pointer for return
57 * This function stops after a single match. There should be
58 * no intervals containing multiple ranges
60 static enum interval_iter range_cb(struct interval_node *n, void *data)
62 struct lu_nid_range *range = container_of(n, struct lu_nid_range,
64 struct lu_nid_range **ret;
69 return INTERVAL_ITER_STOP;
75 * \param min starting nid of the range
76 * \param max ending nid of the range
77 * \param nodemap nodemap that contains this range
78 * \retval lu_nid_range on success, NULL on failure
80 struct lu_nid_range *range_create(lnet_nid_t start_nid, lnet_nid_t end_nid,
81 struct lu_nodemap *nodemap)
83 struct lu_nid_range *range;
85 if (LNET_NIDNET(start_nid) != LNET_NIDNET(end_nid) ||
86 LNET_NIDADDR(start_nid) > LNET_NIDADDR(end_nid))
91 CERROR("cannot allocate lu_nid_range of size %zu bytes\n",
96 range->rn_id = atomic_inc_return(&range_highest_id);
97 range->rn_nodemap = nodemap;
98 interval_set(&range->rn_node, start_nid, end_nid);
99 INIT_LIST_HEAD(&range->rn_list);
105 * find the exact range
107 * \param start_nid starting nid
108 * \param end_nid ending nid
109 * \retval matching range or NULL
111 struct lu_nid_range *range_find(lnet_nid_t start_nid, lnet_nid_t end_nid)
113 struct lu_nid_range *range = NULL;
114 struct interval_node *interval = NULL;
115 struct interval_node_extent ext = {
120 interval = interval_find(range_interval_root, &ext);
122 if (interval != NULL)
123 range = container_of(interval, struct lu_nid_range,
132 void range_destroy(struct lu_nid_range *range)
134 LASSERT(list_empty(&range->rn_list) == 0);
135 LASSERT(interval_is_intree(&range->rn_node) == 0);
141 * insert an nid range into the interval tree
143 * \param range range to insetr
144 * \retval 0 on success
146 * This function checks that the given nid range
147 * does not overlap so that each nid can belong
148 * to exactly one range
150 int range_insert(struct lu_nid_range *range)
152 struct interval_node_extent ext =
153 range->rn_node.in_extent;
155 if (interval_is_overlapped(range_interval_root, &ext) != 0)
158 interval_insert(&range->rn_node, &range_interval_root);
164 * delete a range from the interval tree and any
165 * associated nodemap references
167 * \param range range to remove
169 void range_delete(struct lu_nid_range *range)
171 if (range == NULL || interval_is_intree(&range->rn_node) == 0)
173 list_del(&range->rn_list);
174 interval_erase(&range->rn_node, &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(lnet_nid_t nid)
185 struct lu_nid_range *ret = NULL;
186 struct interval_node_extent ext = {
191 interval_search(range_interval_root, &ext, range_cb, &ret);