lustre/ptlrpc/nodemap_range.c

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 /*
   4  * Copyright (C) 2013, Trustees of Indiana University
   5  *
   6  * Author: Joshua Walgenbach <jjw@iu.edu>
   7  */
   8
   9 #include <lustre_net.h>
  10 #include "nodemap_internal.h"
  11 #include <linux/interval_tree_generic.h>
  12
  13 /*
  14  * Range trees
  15  *
  16  * To classify clients when they connect, build a global range tree
  17  * containing all admin defined ranges. Incoming clients can then be
  18  * classified into their nodemaps, and the lu_nodemap structure will be
  19  * set in the export structure for the connecting client. Pointers to
  20  * the lu_nid_range nodes will be added to linked links within the
  21  * lu_nodemap structure for reporting purposes. Access to range tree should be
  22  * controlled to prevent read access during update operations.
  23  */
  24
  25 #define START(node)     (lnet_nid_to_nid4(&((node)->rn_start)))
  26 #define LAST(node)      (lnet_nid_to_nid4(&((node)->rn_end)))
  27
  28 INTERVAL_TREE_DEFINE(struct lu_nid_range, rn_rb, lnet_nid_t, rn_subtree_last,
  29                      START, LAST, static, nm_range)
  30
  31 static int __range_is_included(lnet_nid_t needle_start, lnet_nid_t needle_end,
  32                                struct lu_nid_range *haystack)
  33 {
  34         return LNET_NIDADDR(START(haystack)) <= LNET_NIDADDR(needle_start) &&
  35                LNET_NIDADDR(LAST(haystack)) >= LNET_NIDADDR(needle_end);
  36 }
  37
  38 static int range_is_included(struct lu_nid_range *needle,
  39                              struct lu_nid_range *haystack)
  40 {
  41         return __range_is_included(START(needle), LAST(needle), haystack);
  42 }
  43
  44 /*
  45  * range constructor
  46  *
  47  * \param       config          nodemap config - used to set range id
  48  * \param       start_nid       starting nid of the range
  49  * \param       end_nid         ending nid of the range
  50  * \param       netmask         network mask prefix length
  51  * \param       nodemap         nodemap that contains this range
  52  * \param       range_id        should be 0 unless loading from disk
  53  * \retval      lu_nid_range on success, NULL on failure
  54  */
  55 struct lu_nid_range *range_create(struct nodemap_config *config,
  56                                   const struct lnet_nid *start_nid,
  57                                   const struct lnet_nid *end_nid,
  58                                   u8 netmask, struct lu_nodemap *nodemap,
  59                                   unsigned int range_id)
  60 {
  61         struct nodemap_range_tree *nm_range_tree;
  62         struct lu_nid_range *range;
  63         LIST_HEAD(tmp_nidlist);
  64
  65         if (LNET_NID_NET(start_nid) != LNET_NID_NET(end_nid))
  66                 return NULL;
  67
  68         if (!netmask) {
  69                 lnet_nid_t nid4[2] = {
  70                         lnet_nid_to_nid4(start_nid),
  71                         lnet_nid_to_nid4(end_nid)
  72                 };
  73
  74                 if (LNET_NIDADDR(nid4[0]) > LNET_NIDADDR(nid4[1]))
  75                         return NULL;
  76         } else if (!nid_same(start_nid, end_nid)) {
  77                 /* A netmask is used with start_nid to form a nidmask. If the
  78                  * start_nid and end_nid differ then this indicates the
  79                  * specified range was malformed
  80                  */
  81                 return NULL;
  82         }
  83
  84         if (netmask) {
  85                 /* +4 for '/<prefix_length>' */
  86                 char nidstr[LNET_NIDSTR_SIZE + 4];
  87                 char net[LNET_NIDSTR_SIZE];
  88                 char *c;
  89                 int rc;
  90
  91                 if (netmask > 128) {
  92                         /* If the netmask is somehow more than three characters
  93                          * then the logic below could truncate it which could
  94                          * result in creating a valid netmask value from bad
  95                          * input.
  96                          * cfs_parse_nidlist() will check whether the netmask
  97                          * is valid for the address type
  98                          */
  99                         CERROR("Invalid netmask %u\n", netmask);
 100                         return NULL;
 101                 }
 102
 103                 /* nidstr = <addr>@<net> */
 104                 snprintf(nidstr, sizeof(nidstr), "%s",
 105                          libcfs_nidstr(start_nid));
 106
 107                 c = strchr(nidstr, '@');
 108                 if (!c) {
 109                         CERROR("Invalid nid %s for netmask\n",
 110                                libcfs_nidstr(start_nid));
 111                         return NULL;
 112                 }
 113
 114                 /* net = @<net> */
 115                 strscpy(net, c, sizeof(net));
 116
 117                 *c = '\0';
 118
 119                 /* nidstr = <addr>/<prefix_length> */
 120                 snprintf(c, sizeof(nidstr) - strlen(nidstr), "/%u", netmask);
 121
 122                 /* nidstr = <addr>/<prefix_length>@<net>
 123                  * (-1 to ensure room for null byte)
 124                  */
 125                 strncat(nidstr, net, sizeof(nidstr) - strlen(nidstr) - 1);
 126
 127                 rc = cfs_parse_nidlist(nidstr, strlen(nidstr), &tmp_nidlist);
 128                 if (rc) {
 129                         CERROR("Invalid nidmask %s rc = %d\n", nidstr, rc);
 130                         return NULL;
 131                 }
 132         }
 133
 134         OBD_ALLOC_PTR(range);
 135         if (range == NULL) {
 136                 CERROR("cannot allocate lu_nid_range of size %zu bytes\n",
 137                        sizeof(*range));
 138                 return NULL;
 139         }
 140
 141         /* if we are loading from save, use on disk id num */
 142         nm_range_tree = &config->nmc_range_tree;
 143         if (range_id != 0) {
 144                 if (nm_range_tree->nmrt_range_highest_id < range_id)
 145                         nm_range_tree->nmrt_range_highest_id = range_id;
 146                 range->rn_id = range_id;
 147         } else {
 148                 nm_range_tree->nmrt_range_highest_id++;
 149                 range->rn_id = nm_range_tree->nmrt_range_highest_id;
 150         }
 151         range->rn_nodemap = nodemap;
 152
 153         range->rn_netmask = netmask;
 154         range->rn_start = *start_nid;
 155         range->rn_end = *end_nid;
 156
 157         INIT_LIST_HEAD(&range->rn_list);
 158         INIT_LIST_HEAD(&range->rn_nidlist);
 159         if (!list_empty(&tmp_nidlist))
 160                 list_splice(&tmp_nidlist, &range->rn_nidlist);
 161         range->rn_subtree.nmrt_range_interval_root = INTERVAL_TREE_ROOT;
 162
 163         return range;
 164 }
 165
 166 /*
 167  * find the exact range
 168  *
 169  * \param       start_nid               starting nid
 170  * \param       end_nid                 ending nid
 171  * \retval      matching range or NULL
 172  */
 173 static
 174 struct lu_nid_range *__range_find(struct nodemap_range_tree *nm_range_tree,
 175                                   const struct lnet_nid *start_nid,
 176                                   const struct lnet_nid *end_nid)
 177 {
 178         struct lu_nid_range *range;
 179         lnet_nid_t nid4[2];
 180
 181         if (!nid_is_nid4(start_nid) || !nid_is_nid4(end_nid))
 182                 return NULL;
 183
 184         nid4[0] = lnet_nid_to_nid4(start_nid);
 185         nid4[1] = lnet_nid_to_nid4(end_nid);
 186
 187         range = nm_range_iter_first(&nm_range_tree->nmrt_range_interval_root,
 188                                     nid4[0], nid4[1]);
 189         while (range) {
 190                 if (nid_same(&range->rn_start, start_nid) &&
 191                     nid_same(&range->rn_end, end_nid))
 192                         break;
 193                 if (__range_is_included(nid4[0], nid4[1], range))
 194                         return __range_find(&range->rn_subtree,
 195                                             start_nid, end_nid);
 196                 range = nm_range_iter_next(range, nid4[0], nid4[1]);
 197         }
 198
 199         return range;
 200 }
 201
 202 struct lu_nid_range *range_find(struct nodemap_config *config,
 203                                 const struct lnet_nid *start_nid,
 204                                 const struct lnet_nid *end_nid,
 205                                 u8 netmask)
 206 {
 207         struct lu_nid_range *range = NULL;
 208
 209         if (!netmask) {
 210                 return __range_find(&config->nmc_range_tree,
 211                                     start_nid, end_nid);
 212         }
 213
 214         if (!list_empty(&config->nmc_netmask_setup)) {
 215                 struct lu_nid_range *range_temp;
 216                 u8 len;
 217
 218                 list_for_each_entry_safe(range, range_temp,
 219                                          &config->nmc_netmask_setup,
 220                                          rn_collect) {
 221                         len = cfs_nidmask_get_length(&range->rn_nidlist);
 222
 223                         if (cfs_match_nid(start_nid, &range->rn_nidlist) &&
 224                             netmask == len)
 225                                 return range;
 226                 }
 227         }
 228
 229         return NULL;
 230 }
 231
 232 /*
 233  * range destructor
 234  */
 235 void range_destroy(struct lu_nid_range *range)
 236 {
 237         LASSERT(list_empty(&range->rn_list) == 0);
 238         if (!list_empty(&range->rn_nidlist))
 239                 cfs_free_nidlist(&range->rn_nidlist);
 240
 241         OBD_FREE_PTR(range);
 242 }
 243
 244 /*
 245  * insert a nid range into the interval tree
 246  *
 247  * \param       range           range to insert
 248  * \retval      0 on success
 249  *
 250  * This function checks that the given nid range
 251  * does not overlap so that each nid can belong
 252  * to exactly one range
 253  */
 254 static int __range_insert(struct nodemap_range_tree *nm_range_tree,
 255                           struct lu_nid_range *range,
 256                           struct lu_nid_range **parent_range, bool dynamic)
 257 {
 258         struct lu_nid_range *found = NULL;
 259         int rc = 0;
 260
 261         found = nm_range_iter_first(&nm_range_tree->nmrt_range_interval_root,
 262                                     lnet_nid_to_nid4(&range->rn_start),
 263                                     lnet_nid_to_nid4(&range->rn_end));
 264         if (found) {
 265                 if (dynamic && range_is_included(range, found)) {
 266                         rc = __range_insert(&found->rn_subtree,
 267                                             range, parent_range, dynamic);
 268                         if (!rc) {
 269                                 if (parent_range && !*parent_range)
 270                                         *parent_range = found;
 271                         }
 272                 } else {
 273                         rc = -EEXIST;
 274                 }
 275                 GOTO(out_insert, rc);
 276         }
 277
 278         nm_range_insert(range,
 279                         &nm_range_tree->nmrt_range_interval_root);
 280
 281 out_insert:
 282         return rc;
 283 }
 284
 285 int range_insert(struct nodemap_config *config, struct lu_nid_range *range,
 286                  struct lu_nid_range **parent_range, bool dynamic)
 287 {
 288         int rc = 0;
 289
 290         if (!range->rn_netmask) {
 291                 rc = __range_insert(&config->nmc_range_tree,
 292                                     range, parent_range, dynamic);
 293         } else {
 294                 if (range_find(config, &range->rn_start, &range->rn_end,
 295                                range->rn_netmask))
 296                         return -EEXIST;
 297
 298                 list_add(&range->rn_collect, &config->nmc_netmask_setup);
 299         }
 300
 301         return rc;
 302 }
 303
 304 /*
 305  * delete a range from the interval tree and any
 306  * associated nodemap references
 307  *
 308  * \param       range           range to remove
 309  */
 310 static void __range_delete(struct nodemap_range_tree *nm_range_tree,
 311                            struct lu_nid_range *range)
 312 {
 313         struct lu_nid_range *found;
 314         lnet_nid_t nid4[2];
 315
 316         nid4[0] = lnet_nid_to_nid4(&range->rn_start);
 317         nid4[1] = lnet_nid_to_nid4(&range->rn_end);
 318
 319         found = nm_range_iter_first(&nm_range_tree->nmrt_range_interval_root,
 320                                     nid4[0], nid4[1]);
 321         while (found) {
 322                 if (nid_same(&found->rn_start, &range->rn_start) &&
 323                     nid_same(&found->rn_end, &range->rn_end))
 324                         break;
 325                 if (__range_is_included(nid4[0], nid4[1], found)) {
 326                         __range_delete(&found->rn_subtree, range);
 327                         return;
 328                 }
 329                 found = nm_range_iter_next(found, nid4[0], nid4[1]);
 330         }
 331
 332         if (found)
 333                 nm_range_remove(found,
 334                                 &nm_range_tree->nmrt_range_interval_root);
 335 }
 336
 337 void range_delete(struct nodemap_config *config, struct lu_nid_range *range)
 338 {
 339         list_del(&range->rn_list);
 340
 341         if (!range->rn_netmask)
 342                 __range_delete(&config->nmc_range_tree, range);
 343         else
 344                 list_del(&range->rn_collect);
 345
 346         range_destroy(range);
 347 }
 348
 349 /*
 350  * search the interval tree for a nid within a range
 351  *
 352  * \param       nid             nid to search for
 353  */
 354 static
 355 struct lu_nid_range *__range_search(struct nodemap_range_tree *nm_range_tree,
 356                                     struct lnet_nid *nid)
 357 {
 358         struct lu_nid_range *range, *subrange;
 359
 360         range = nm_range_iter_first(&nm_range_tree->nmrt_range_interval_root,
 361                                     lnet_nid_to_nid4(nid),
 362                                     lnet_nid_to_nid4(nid));
 363         if (range) {
 364                 subrange = __range_search(&range->rn_subtree, nid);
 365                 if (subrange)
 366                         range = subrange;
 367         }
 368
 369         return range;
 370 }
 371
 372 struct lu_nid_range *range_search(struct nodemap_config *config,
 373                                   struct lnet_nid *nid)
 374 {
 375         if (nid_is_nid4(nid)) {
 376                 return __range_search(&config->nmc_range_tree, nid);
 377         }
 378
 379         if (!list_empty(&config->nmc_netmask_setup)) {
 380                 struct lu_nid_range *range, *range_temp;
 381
 382                 list_for_each_entry_safe(range, range_temp,
 383                                          &config->nmc_netmask_setup,
 384                                          rn_collect) {
 385                         if (cfs_match_nid(nid, &range->rn_nidlist))
 386                                 return range;
 387                 }
 388         }
 389
 390         return NULL;
 391 }