Whamcloud - gitweb
3a43b2f0d9a57086d77aed01405d3634c7d4b375
[fs/lustre-release.git] / lustre / ptlrpc / nodemap_range.c
1 /*
2  * GPL HEADER START
3  *
4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5  *
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.
9  *
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).
15  *
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
19  *
20  * GPL HEADER END
21  */
22 /*
23  * Copyright (C) 2013, Trustees of Indiana University
24  * Author: Joshua Walgenbach <jjw@iu.edu>
25  */
26
27 #include <interval_tree.h>
28 #include <lustre_net.h>
29 #include "nodemap_internal.h"
30
31 /*
32  * Range trees
33  *
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.
41  */
42
43 static struct interval_node *range_interval_root;
44 static atomic_t range_highest_id;
45
46 void range_init_tree(void)
47 {
48         range_interval_root = NULL;
49 }
50
51 /*
52  * callback for iterating over the interval tree
53  *
54  * \param       n               interval_node matched
55  * \param       data            void pointer for return
56  *
57  * This function stops after a single match. There should be
58  * no intervals containing multiple ranges
59  */
60 static enum interval_iter range_cb(struct interval_node *n, void *data)
61 {
62         struct lu_nid_range     *range = container_of(n, struct lu_nid_range,
63                                                       rn_node);
64         struct lu_nid_range     **ret;
65
66         ret = data;
67         *ret = range;
68
69         return INTERVAL_ITER_STOP;
70 }
71
72 /*
73  * range constructor
74  *
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
79  */
80 struct lu_nid_range *range_create(lnet_nid_t start_nid, lnet_nid_t end_nid,
81                                   struct lu_nodemap *nodemap)
82 {
83         struct lu_nid_range *range;
84
85         if (LNET_NIDNET(start_nid) != LNET_NIDNET(end_nid) ||
86             LNET_NIDADDR(start_nid) > LNET_NIDADDR(end_nid))
87                 return NULL;
88
89         OBD_ALLOC_PTR(range);
90         if (range == NULL) {
91                 CERROR("cannot allocate lu_nid_range of size %zu bytes\n",
92                        sizeof(*range));
93                 return NULL;
94         }
95
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);
100
101         return range;
102 }
103
104 /*
105  * find the exact range
106  *
107  * \param       start_nid               starting nid
108  * \param       end_nid                 ending nid
109  * \retval      matching range or NULL
110  */
111 struct lu_nid_range *range_find(lnet_nid_t start_nid, lnet_nid_t end_nid)
112 {
113         struct lu_nid_range             *range = NULL;
114         struct interval_node            *interval = NULL;
115         struct interval_node_extent     ext = {
116                 .start  = start_nid,
117                 .end    = end_nid
118         };
119
120         interval = interval_find(range_interval_root, &ext);
121
122         if (interval != NULL)
123                 range = container_of(interval, struct lu_nid_range,
124                                      rn_node);
125
126         return range;
127 }
128
129 /*
130  * range destructor
131  */
132 void range_destroy(struct lu_nid_range *range)
133 {
134         LASSERT(list_empty(&range->rn_list) == 0);
135         LASSERT(interval_is_intree(&range->rn_node) == 0);
136
137         OBD_FREE_PTR(range);
138 }
139
140 /*
141  * insert an nid range into the interval tree
142  *
143  * \param       range           range to insetr
144  * \retval      0 on success
145  *
146  * This function checks that the given nid range
147  * does not overlap so that each nid can belong
148  * to exactly one range
149  */
150 int range_insert(struct lu_nid_range *range)
151 {
152         struct interval_node_extent ext =
153                         range->rn_node.in_extent;
154
155         if (interval_is_overlapped(range_interval_root, &ext) != 0)
156                 return -EEXIST;
157
158         interval_insert(&range->rn_node, &range_interval_root);
159
160         return 0;
161 }
162
163 /*
164  * delete a range from the interval tree and any
165  * associated nodemap references
166  *
167  * \param       range           range to remove
168  */
169 void range_delete(struct lu_nid_range *range)
170 {
171         if (range == NULL || interval_is_intree(&range->rn_node) == 0)
172                 return;
173         list_del(&range->rn_list);
174         interval_erase(&range->rn_node, &range_interval_root);
175         range_destroy(range);
176 }
177
178 /*
179  * search the interval tree for an nid within a range
180  *
181  * \param       nid             nid to search for
182  */
183 struct lu_nid_range *range_search(lnet_nid_t nid)
184 {
185         struct lu_nid_range             *ret = NULL;
186         struct interval_node_extent     ext = {
187                 .start  = nid,
188                 .end    = nid
189         };
190
191         interval_search(range_interval_root, &ext, range_cb, &ret);
192
193         return ret;
194 }