drivers/infiniband/hw/usnic/usnic_uiom_interval_tree.c

   1 /*
   2  * Copyright (c) 2014, Cisco Systems, Inc. All rights reserved.
   3  *
   4  * This program is free software; you may redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; version 2 of the License.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
   9  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  10  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  11  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  12  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  13  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  14  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  15  * SOFTWARE.
  16  *
  17  */
  18
  19 #include <linux/init.h>
  20 #include <linux/list.h>
  21 #include <linux/slab.h>
  22 #include <linux/list_sort.h>
  23
  24 #include <linux/interval_tree_generic.h>
  25 #include "usnic_uiom_interval_tree.h"
  26
  27 #define START(node) ((node)->start)
  28 #define LAST(node) ((node)->last)
  29
  30 #define MAKE_NODE(node, start, end, ref_cnt, flags, err, err_out)       \
  31                 do {                                                    \
  32                         node = usnic_uiom_interval_node_alloc(start,    \
  33                                         end, ref_cnt, flags);           \
  34                                 if (!node) {                            \
  35                                         err = -ENOMEM;                  \
  36                                         goto err_out;                   \
  37                                 }                                       \
  38                 } while (0)
  39
  40 #define MARK_FOR_ADD(node, list) (list_add_tail(&node->link, list))
  41
  42 #define MAKE_NODE_AND_APPEND(node, start, end, ref_cnt, flags, err,     \
  43                                 err_out, list)                          \
  44                                 do {                                    \
  45                                         MAKE_NODE(node, start, end,     \
  46                                                 ref_cnt, flags, err,    \
  47                                                 err_out);               \
  48                                         MARK_FOR_ADD(node, list);       \
  49                                 } while (0)
  50
  51 #define FLAGS_EQUAL(flags1, flags2, mask)                               \
  52                         (((flags1) & (mask)) == ((flags2) & (mask)))
  53
  54 static struct usnic_uiom_interval_node*
  55 usnic_uiom_interval_node_alloc(long int start, long int last, int ref_cnt,
  56                                 int flags)
  57 {
  58         struct usnic_uiom_interval_node *interval = kzalloc(sizeof(*interval),
  59                                                                 GFP_ATOMIC);
  60         if (!interval)
  61                 return NULL;
  62
  63         interval->start = start;
  64         interval->last = last;
  65         interval->flags = flags;
  66         interval->ref_cnt = ref_cnt;
  67
  68         return interval;
  69 }
  70
  71 static int interval_cmp(void *priv, struct list_head *a, struct list_head *b)
  72 {
  73         struct usnic_uiom_interval_node *node_a, *node_b;
  74
  75         node_a = list_entry(a, struct usnic_uiom_interval_node, link);
  76         node_b = list_entry(b, struct usnic_uiom_interval_node, link);
  77
  78         /* long to int */
  79         if (node_a->start < node_b->start)
  80                 return -1;
  81         else if (node_a->start > node_b->start)
  82                 return 1;
  83
  84         return 0;
  85 }
  86
  87 static void
  88 find_intervals_intersection_sorted(struct rb_root *root, unsigned long start,
  89                                         unsigned long last,
  90                                         struct list_head *list)
  91 {
  92         struct usnic_uiom_interval_node *node;
  93
  94         INIT_LIST_HEAD(list);
  95
  96         for (node = usnic_uiom_interval_tree_iter_first(root, start, last);
  97                 node;
  98                 node = usnic_uiom_interval_tree_iter_next(node, start, last))
  99                 list_add_tail(&node->link, list);
 100
 101         list_sort(NULL, list, interval_cmp);
 102 }
 103
 104 int usnic_uiom_get_intervals_diff(unsigned long start, unsigned long last,
 105                                         int flags, int flag_mask,
 106                                         struct rb_root *root,
 107                                         struct list_head *diff_set)
 108 {
 109         struct usnic_uiom_interval_node *interval, *tmp;
 110         int err = 0;
 111         long int pivot = start;
 112         LIST_HEAD(intersection_set);
 113
 114         INIT_LIST_HEAD(diff_set);
 115
 116         find_intervals_intersection_sorted(root, start, last,
 117                                                 &intersection_set);
 118
 119         list_for_each_entry(interval, &intersection_set, link) {
 120                 if (pivot < interval->start) {
 121                         MAKE_NODE_AND_APPEND(tmp, pivot, interval->start - 1,
 122                                                 1, flags, err, err_out,
 123                                                 diff_set);
 124                         pivot = interval->start;
 125                 }
 126
 127                 /*
 128                  * Invariant: Set [start, pivot] is either in diff_set or root,
 129                  * but not in both.
 130                  */
 131
 132                 if (pivot > interval->last) {
 133                         continue;
 134                 } else if (pivot <= interval->last &&
 135                                 FLAGS_EQUAL(interval->flags, flags,
 136                                 flag_mask)) {
 137                         pivot = interval->last + 1;
 138                 }
 139         }
 140
 141         if (pivot <= last)
 142                 MAKE_NODE_AND_APPEND(tmp, pivot, last, 1, flags, err, err_out,
 143                                         diff_set);
 144
 145         return 0;
 146
 147 err_out:
 148         list_for_each_entry_safe(interval, tmp, diff_set, link) {
 149                 list_del(&interval->link);
 150                 kfree(interval);
 151         }
 152
 153         return err;
 154 }
 155
 156 void usnic_uiom_put_interval_set(struct list_head *intervals)
 157 {
 158         struct usnic_uiom_interval_node *interval, *tmp;
 159         list_for_each_entry_safe(interval, tmp, intervals, link)
 160                 kfree(interval);
 161 }
 162
 163 int usnic_uiom_insert_interval(struct rb_root *root, unsigned long start,
 164                                 unsigned long last, int flags)
 165 {
 166         struct usnic_uiom_interval_node *interval, *tmp;
 167         unsigned long istart, ilast;
 168         int iref_cnt, iflags;
 169         unsigned long lpivot = start;
 170         int err = 0;
 171         LIST_HEAD(to_add);
 172         LIST_HEAD(intersection_set);
 173
 174         find_intervals_intersection_sorted(root, start, last,
 175                                                 &intersection_set);
 176
 177         list_for_each_entry(interval, &intersection_set, link) {
 178                 /*
 179                  * Invariant - lpivot is the left edge of next interval to be
 180                  * inserted
 181                  */
 182                 istart = interval->start;
 183                 ilast = interval->last;
 184                 iref_cnt = interval->ref_cnt;
 185                 iflags = interval->flags;
 186
 187                 if (istart < lpivot) {
 188                         MAKE_NODE_AND_APPEND(tmp, istart, lpivot - 1, iref_cnt,
 189                                                 iflags, err, err_out, &to_add);
 190                 } else if (istart > lpivot) {
 191                         MAKE_NODE_AND_APPEND(tmp, lpivot, istart - 1, 1, flags,
 192                                                 err, err_out, &to_add);
 193                         lpivot = istart;
 194                 } else {
 195                         lpivot = istart;
 196                 }
 197
 198                 if (ilast > last) {
 199                         MAKE_NODE_AND_APPEND(tmp, lpivot, last, iref_cnt + 1,
 200                                                 iflags | flags, err, err_out,
 201                                                 &to_add);
 202                         MAKE_NODE_AND_APPEND(tmp, last + 1, ilast, iref_cnt,
 203                                                 iflags, err, err_out, &to_add);
 204                 } else {
 205                         MAKE_NODE_AND_APPEND(tmp, lpivot, ilast, iref_cnt + 1,
 206                                                 iflags | flags, err, err_out,
 207                                                 &to_add);
 208                 }
 209
 210                 lpivot = ilast + 1;
 211         }
 212
 213         if (lpivot <= last)
 214                 MAKE_NODE_AND_APPEND(tmp, lpivot, last, 1, flags, err, err_out,
 215                                         &to_add);
 216
 217         list_for_each_entry_safe(interval, tmp, &intersection_set, link) {
 218                 usnic_uiom_interval_tree_remove(interval, root);
 219                 kfree(interval);
 220         }
 221
 222         list_for_each_entry(interval, &to_add, link)
 223                 usnic_uiom_interval_tree_insert(interval, root);
 224
 225         return 0;
 226
 227 err_out:
 228         list_for_each_entry_safe(interval, tmp, &to_add, link)
 229                 kfree(interval);
 230
 231         return err;
 232 }
 233
 234 void usnic_uiom_remove_interval(struct rb_root *root, unsigned long start,
 235                                 unsigned long last, struct list_head *removed)
 236 {
 237         struct usnic_uiom_interval_node *interval;
 238
 239         for (interval = usnic_uiom_interval_tree_iter_first(root, start, last);
 240                         interval;
 241                         interval = usnic_uiom_interval_tree_iter_next(interval,
 242                                                                         start,
 243                                                                         last)) {
 244                 if (--interval->ref_cnt == 0)
 245                         list_add_tail(&interval->link, removed);
 246         }
 247
 248         list_for_each_entry(interval, removed, link)
 249                 usnic_uiom_interval_tree_remove(interval, root);
 250 }
 251
 252 INTERVAL_TREE_DEFINE(struct usnic_uiom_interval_node, rb,
 253                         unsigned long, __subtree_last,
 254                         START, LAST, , usnic_uiom_interval_tree)