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 }