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 /*
  44  * callback for iterating over the interval tree
  45  *
  46  * \param       n               interval_node matched
  47  * \param       data            void pointer for return
  48  *
  49  * This function stops after a single match. There should be
  50  * no intervals containing multiple ranges
  51  */
  52 static enum interval_iter range_cb(struct interval_node *n, void *data)
  53 {
  54         struct lu_nid_range     *range = container_of(n, struct lu_nid_range,
  55                                                       rn_node);
  56         struct lu_nid_range     **ret;
  57
  58         ret = data;
  59         *ret = range;
  60
  61         return INTERVAL_ITER_STOP;
  62 }
  63
  64 /*
  65  * range constructor
  66  *
  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
  71  */
  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, unsigned range_id)
  75 {
  76         struct lu_nid_range *range;
  77         int rc;
  78
  79         if (LNET_NIDNET(start_nid) != LNET_NIDNET(end_nid) ||
  80             LNET_NIDADDR(start_nid) > LNET_NIDADDR(end_nid))
  81                 return NULL;
  82
  83         OBD_ALLOC_PTR(range);
  84         if (range == NULL) {
  85                 CERROR("cannot allocate lu_nid_range of size %zu bytes\n",
  86                        sizeof(*range));
  87                 return NULL;
  88         }
  89
  90         /* if we are loading from save, use on disk id num */
  91         if (range_id != 0) {
  92                 if (nm_range_tree->nmrt_range_highest_id < range_id)
  93                         nm_range_tree->nmrt_range_highest_id = range_id;
  94                 range->rn_id = range_id;
  95         } else {
  96                 nm_range_tree->nmrt_range_highest_id++;
  97                 range->rn_id = nm_range_tree->nmrt_range_highest_id;
  98         }
  99         range->rn_nodemap = nodemap;
 100
 101         rc = interval_set(&range->rn_node, start_nid, end_nid);
 102         if (rc < 0) {
 103                 OBD_FREE_PTR(range);
 104                 return NULL;
 105         }
 106
 107         INIT_LIST_HEAD(&range->rn_list);
 108
 109         return range;
 110 }
 111
 112 /*
 113  * find the exact range
 114  *
 115  * \param       start_nid               starting nid
 116  * \param       end_nid                 ending nid
 117  * \retval      matching range or NULL
 118  */
 119 struct lu_nid_range *range_find(struct nodemap_range_tree *nm_range_tree,
 120                                 lnet_nid_t start_nid, lnet_nid_t end_nid)
 121 {
 122         struct lu_nid_range             *range = NULL;
 123         struct interval_node            *interval = NULL;
 124         struct interval_node_extent     ext = {
 125                 .start  = start_nid,
 126                 .end    = end_nid
 127         };
 128
 129         interval = interval_find(nm_range_tree->nmrt_range_interval_root, &ext);
 130
 131         if (interval != NULL)
 132                 range = container_of(interval, struct lu_nid_range,
 133                                      rn_node);
 134
 135         return range;
 136 }
 137
 138 /*
 139  * range destructor
 140  */
 141 void range_destroy(struct lu_nid_range *range)
 142 {
 143         LASSERT(list_empty(&range->rn_list) == 0);
 144         LASSERT(interval_is_intree(&range->rn_node) == 0);
 145
 146         OBD_FREE_PTR(range);
 147 }
 148
 149 /*
 150  * insert an nid range into the interval tree
 151  *
 152  * \param       range           range to insetr
 153  * \retval      0 on success
 154  *
 155  * This function checks that the given nid range
 156  * does not overlap so that each nid can belong
 157  * to exactly one range
 158  */
 159 int range_insert(struct nodemap_range_tree *nm_range_tree,
 160                  struct lu_nid_range *range)
 161 {
 162         struct interval_node_extent ext =
 163                         range->rn_node.in_extent;
 164
 165         if (interval_is_overlapped(nm_range_tree->nmrt_range_interval_root,
 166                                    &ext) != 0)
 167                 return -EEXIST;
 168
 169         interval_insert(&range->rn_node,
 170                         &nm_range_tree->nmrt_range_interval_root);
 171
 172         return 0;
 173 }
 174
 175 /*
 176  * delete a range from the interval tree and any
 177  * associated nodemap references
 178  *
 179  * \param       range           range to remove
 180  */
 181 void range_delete(struct nodemap_range_tree *nm_range_tree,
 182                   struct lu_nid_range *range)
 183 {
 184         if (range == NULL || interval_is_intree(&range->rn_node) == 0)
 185                 return;
 186         list_del(&range->rn_list);
 187         interval_erase(&range->rn_node,
 188                        &nm_range_tree->nmrt_range_interval_root);
 189         range_destroy(range);
 190 }
 191
 192 /*
 193  * search the interval tree for an nid within a range
 194  *
 195  * \param       nid             nid to search for
 196  */
 197 struct lu_nid_range *range_search(struct nodemap_range_tree *nm_range_tree,
 198                                   lnet_nid_t nid)
 199 {
 200         struct lu_nid_range             *ret = NULL;
 201         struct interval_node_extent     ext = {
 202                 .start  = nid,
 203                 .end    = nid
 204         };
 205
 206         interval_search(nm_range_tree->nmrt_range_interval_root, &ext,
 207                         range_cb, &ret);
 208
 209         return ret;
 210 }