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)
  75 {
  76         struct lu_nid_range *range;
  77
  78         if (LNET_NIDNET(start_nid) != LNET_NIDNET(end_nid) ||
  79             LNET_NIDADDR(start_nid) > LNET_NIDADDR(end_nid))
  80                 return NULL;
  81
  82         OBD_ALLOC_PTR(range);
  83         if (range == NULL) {
  84                 CERROR("cannot allocate lu_nid_range of size %zu bytes\n",
  85                        sizeof(*range));
  86                 return NULL;
  87         }
  88
  89         nm_range_tree->nmrt_range_highest_id++;
  90         range->rn_id = nm_range_tree->nmrt_range_highest_id;
  91         range->rn_nodemap = nodemap;
  92         interval_set(&range->rn_node, start_nid, end_nid);
  93         INIT_LIST_HEAD(&range->rn_list);
  94
  95         return range;
  96 }
  97
  98 /*
  99  * find the exact range
 100  *
 101  * \param       start_nid               starting nid
 102  * \param       end_nid                 ending nid
 103  * \retval      matching range or NULL
 104  */
 105 struct lu_nid_range *range_find(struct nodemap_range_tree *nm_range_tree,
 106                                 lnet_nid_t start_nid, lnet_nid_t end_nid)
 107 {
 108         struct lu_nid_range             *range = NULL;
 109         struct interval_node            *interval = NULL;
 110         struct interval_node_extent     ext = {
 111                 .start  = start_nid,
 112                 .end    = end_nid
 113         };
 114
 115         interval = interval_find(nm_range_tree->nmrt_range_interval_root, &ext);
 116
 117         if (interval != NULL)
 118                 range = container_of(interval, struct lu_nid_range,
 119                                      rn_node);
 120
 121         return range;
 122 }
 123
 124 /*
 125  * range destructor
 126  */
 127 void range_destroy(struct lu_nid_range *range)
 128 {
 129         LASSERT(list_empty(&range->rn_list) == 0);
 130         LASSERT(interval_is_intree(&range->rn_node) == 0);
 131
 132         OBD_FREE_PTR(range);
 133 }
 134
 135 /*
 136  * insert an nid range into the interval tree
 137  *
 138  * \param       range           range to insetr
 139  * \retval      0 on success
 140  *
 141  * This function checks that the given nid range
 142  * does not overlap so that each nid can belong
 143  * to exactly one range
 144  */
 145 int range_insert(struct nodemap_range_tree *nm_range_tree,
 146                  struct lu_nid_range *range)
 147 {
 148         struct interval_node_extent ext =
 149                         range->rn_node.in_extent;
 150
 151         if (interval_is_overlapped(nm_range_tree->nmrt_range_interval_root,
 152                                    &ext) != 0)
 153                 return -EEXIST;
 154
 155         interval_insert(&range->rn_node,
 156                         &nm_range_tree->nmrt_range_interval_root);
 157
 158         return 0;
 159 }
 160
 161 /*
 162  * delete a range from the interval tree and any
 163  * associated nodemap references
 164  *
 165  * \param       range           range to remove
 166  */
 167 void range_delete(struct nodemap_range_tree *nm_range_tree,
 168                   struct lu_nid_range *range)
 169 {
 170         if (range == NULL || interval_is_intree(&range->rn_node) == 0)
 171                 return;
 172         list_del(&range->rn_list);
 173         interval_erase(&range->rn_node,
 174                        &nm_range_tree->nmrt_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(struct nodemap_range_tree *nm_range_tree,
 184                                   lnet_nid_t nid)
 185 {
 186         struct lu_nid_range             *ret = NULL;
 187         struct interval_node_extent     ext = {
 188                 .start  = nid,
 189                 .end    = nid
 190         };
 191
 192         interval_search(nm_range_tree->nmrt_range_interval_root, &ext,
 193                         range_cb, &ret);
 194
 195         return ret;
 196 }