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