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
  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         /* if we are loading from save, use on disk id num */
  90         if (range_id != 0) {
  91                 if (nm_range_tree->nmrt_range_highest_id < range_id)
  92                         nm_range_tree->nmrt_range_highest_id = range_id;
  93                 range->rn_id = range_id;
  94         } else {
  95                 nm_range_tree->nmrt_range_highest_id++;
  96                 range->rn_id = nm_range_tree->nmrt_range_highest_id;
  97         }
  98         range->rn_nodemap = nodemap;
  99         interval_set(&range->rn_node, start_nid, end_nid);
 100         INIT_LIST_HEAD(&range->rn_list);
 101
 102         return range;
 103 }
 104
 105 /*
 106  * find the exact range
 107  *
 108  * \param       start_nid               starting nid
 109  * \param       end_nid                 ending nid
 110  * \retval      matching range or NULL
 111  */
 112 struct lu_nid_range *range_find(struct nodemap_range_tree *nm_range_tree,
 113                                 lnet_nid_t start_nid, lnet_nid_t end_nid)
 114 {
 115         struct lu_nid_range             *range = NULL;
 116         struct interval_node            *interval = NULL;
 117         struct interval_node_extent     ext = {
 118                 .start  = start_nid,
 119                 .end    = end_nid
 120         };
 121
 122         interval = interval_find(nm_range_tree->nmrt_range_interval_root, &ext);
 123
 124         if (interval != NULL)
 125                 range = container_of(interval, struct lu_nid_range,
 126                                      rn_node);
 127
 128         return range;
 129 }
 130
 131 /*
 132  * range destructor
 133  */
 134 void range_destroy(struct lu_nid_range *range)
 135 {
 136         LASSERT(list_empty(&range->rn_list) == 0);
 137         LASSERT(interval_is_intree(&range->rn_node) == 0);
 138
 139         OBD_FREE_PTR(range);
 140 }
 141
 142 /*
 143  * insert an nid range into the interval tree
 144  *
 145  * \param       range           range to insetr
 146  * \retval      0 on success
 147  *
 148  * This function checks that the given nid range
 149  * does not overlap so that each nid can belong
 150  * to exactly one range
 151  */
 152 int range_insert(struct nodemap_range_tree *nm_range_tree,
 153                  struct lu_nid_range *range)
 154 {
 155         struct interval_node_extent ext =
 156                         range->rn_node.in_extent;
 157
 158         if (interval_is_overlapped(nm_range_tree->nmrt_range_interval_root,
 159                                    &ext) != 0)
 160                 return -EEXIST;
 161
 162         interval_insert(&range->rn_node,
 163                         &nm_range_tree->nmrt_range_interval_root);
 164
 165         return 0;
 166 }
 167
 168 /*
 169  * delete a range from the interval tree and any
 170  * associated nodemap references
 171  *
 172  * \param       range           range to remove
 173  */
 174 void range_delete(struct nodemap_range_tree *nm_range_tree,
 175                   struct lu_nid_range *range)
 176 {
 177         if (range == NULL || interval_is_intree(&range->rn_node) == 0)
 178                 return;
 179         list_del(&range->rn_list);
 180         interval_erase(&range->rn_node,
 181                        &nm_range_tree->nmrt_range_interval_root);
 182         range_destroy(range);
 183 }
 184
 185 /*
 186  * search the interval tree for an nid within a range
 187  *
 188  * \param       nid             nid to search for
 189  */
 190 struct lu_nid_range *range_search(struct nodemap_range_tree *nm_range_tree,
 191                                   lnet_nid_t nid)
 192 {
 193         struct lu_nid_range             *ret = NULL;
 194         struct interval_node_extent     ext = {
 195                 .start  = nid,
 196                 .end    = nid
 197         };
 198
 199         interval_search(nm_range_tree->nmrt_range_interval_root, &ext,
 200                         range_cb, &ret);
 201
 202         return ret;
 203 }