fs/btrfs/ulist.c

   1 /*
   2  * Copyright (C) 2011 STRATO AG
   3  * written by Arne Jansen <sensille@gmx.net>
   4  * Distributed under the GNU GPL license version 2.
   5  */
   6
   7 #include <linux/slab.h>
   8 #include <linux/export.h>
   9 #include "ulist.h"
  10
  11 /*
  12  * ulist is a generic data structure to hold a collection of unique u64
  13  * values. The only operations it supports is adding to the list and
  14  * enumerating it.
  15  * It is possible to store an auxiliary value along with the key.
  16  *
  17  * The implementation is preliminary and can probably be sped up
  18  * significantly. A first step would be to store the values in an rbtree
  19  * as soon as ULIST_SIZE is exceeded.
  20  *
  21  * A sample usage for ulists is the enumeration of directed graphs without
  22  * visiting a node twice. The pseudo-code could look like this:
  23  *
  24  * ulist = ulist_alloc();
  25  * ulist_add(ulist, root);
  26  * ULIST_ITER_INIT(&uiter);
  27  *
  28  * while ((elem = ulist_next(ulist, &uiter)) {
  29  *      for (all child nodes n in elem)
  30  *              ulist_add(ulist, n);
  31  *      do something useful with the node;
  32  * }
  33  * ulist_free(ulist);
  34  *
  35  * This assumes the graph nodes are adressable by u64. This stems from the
  36  * usage for tree enumeration in btrfs, where the logical addresses are
  37  * 64 bit.
  38  *
  39  * It is also useful for tree enumeration which could be done elegantly
  40  * recursively, but is not possible due to kernel stack limitations. The
  41  * loop would be similar to the above.
  42  */
  43
  44 /**
  45  * ulist_init - freshly initialize a ulist
  46  * @ulist:      the ulist to initialize
  47  *
  48  * Note: don't use this function to init an already used ulist, use
  49  * ulist_reinit instead.
  50  */
  51 void ulist_init(struct ulist *ulist)
  52 {
  53         ulist->nnodes = 0;
  54         ulist->nodes = ulist->int_nodes;
  55         ulist->nodes_alloced = ULIST_SIZE;
  56         ulist->root = RB_ROOT;
  57 }
  58 EXPORT_SYMBOL(ulist_init);
  59
  60 /**
  61  * ulist_fini - free up additionally allocated memory for the ulist
  62  * @ulist:      the ulist from which to free the additional memory
  63  *
  64  * This is useful in cases where the base 'struct ulist' has been statically
  65  * allocated.
  66  */
  67 void ulist_fini(struct ulist *ulist)
  68 {
  69         /*
  70          * The first ULIST_SIZE elements are stored inline in struct ulist.
  71          * Only if more elements are alocated they need to be freed.
  72          */
  73         if (ulist->nodes_alloced > ULIST_SIZE)
  74                 kfree(ulist->nodes);
  75         ulist->nodes_alloced = 0;       /* in case ulist_fini is called twice */
  76         ulist->root = RB_ROOT;
  77 }
  78 EXPORT_SYMBOL(ulist_fini);
  79
  80 /**
  81  * ulist_reinit - prepare a ulist for reuse
  82  * @ulist:      ulist to be reused
  83  *
  84  * Free up all additional memory allocated for the list elements and reinit
  85  * the ulist.
  86  */
  87 void ulist_reinit(struct ulist *ulist)
  88 {
  89         ulist_fini(ulist);
  90         ulist_init(ulist);
  91 }
  92 EXPORT_SYMBOL(ulist_reinit);
  93
  94 /**
  95  * ulist_alloc - dynamically allocate a ulist
  96  * @gfp_mask:   allocation flags to for base allocation
  97  *
  98  * The allocated ulist will be returned in an initialized state.
  99  */
 100 struct ulist *ulist_alloc(gfp_t gfp_mask)
 101 {
 102         struct ulist *ulist = kmalloc(sizeof(*ulist), gfp_mask);
 103
 104         if (!ulist)
 105                 return NULL;
 106
 107         ulist_init(ulist);
 108
 109         return ulist;
 110 }
 111 EXPORT_SYMBOL(ulist_alloc);
 112
 113 /**
 114  * ulist_free - free dynamically allocated ulist
 115  * @ulist:      ulist to free
 116  *
 117  * It is not necessary to call ulist_fini before.
 118  */
 119 void ulist_free(struct ulist *ulist)
 120 {
 121         if (!ulist)
 122                 return;
 123         ulist_fini(ulist);
 124         kfree(ulist);
 125 }
 126 EXPORT_SYMBOL(ulist_free);
 127
 128 static struct ulist_node *ulist_rbtree_search(struct ulist *ulist, u64 val)
 129 {
 130         struct rb_node *n = ulist->root.rb_node;
 131         struct ulist_node *u = NULL;
 132
 133         while (n) {
 134                 u = rb_entry(n, struct ulist_node, rb_node);
 135                 if (u->val < val)
 136                         n = n->rb_right;
 137                 else if (u->val > val)
 138                         n = n->rb_left;
 139                 else
 140                         return u;
 141         }
 142         return NULL;
 143 }
 144
 145 static int ulist_rbtree_insert(struct ulist *ulist, struct ulist_node *ins)
 146 {
 147         struct rb_node **p = &ulist->root.rb_node;
 148         struct rb_node *parent = NULL;
 149         struct ulist_node *cur = NULL;
 150
 151         while (*p) {
 152                 parent = *p;
 153                 cur = rb_entry(parent, struct ulist_node, rb_node);
 154
 155                 if (cur->val < ins->val)
 156                         p = &(*p)->rb_right;
 157                 else if (cur->val > ins->val)
 158                         p = &(*p)->rb_left;
 159                 else
 160                         return -EEXIST;
 161         }
 162         rb_link_node(&ins->rb_node, parent, p);
 163         rb_insert_color(&ins->rb_node, &ulist->root);
 164         return 0;
 165 }
 166
 167 /**
 168  * ulist_add - add an element to the ulist
 169  * @ulist:      ulist to add the element to
 170  * @val:        value to add to ulist
 171  * @aux:        auxiliary value to store along with val
 172  * @gfp_mask:   flags to use for allocation
 173  *
 174  * Note: locking must be provided by the caller. In case of rwlocks write
 175  *       locking is needed
 176  *
 177  * Add an element to a ulist. The @val will only be added if it doesn't
 178  * already exist. If it is added, the auxiliary value @aux is stored along with
 179  * it. In case @val already exists in the ulist, @aux is ignored, even if
 180  * it differs from the already stored value.
 181  *
 182  * ulist_add returns 0 if @val already exists in ulist and 1 if @val has been
 183  * inserted.
 184  * In case of allocation failure -ENOMEM is returned and the ulist stays
 185  * unaltered.
 186  */
 187 int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask)
 188 {
 189         return ulist_add_merge(ulist, val, aux, NULL, gfp_mask);
 190 }
 191
 192 int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux,
 193                     u64 *old_aux, gfp_t gfp_mask)
 194 {
 195         int ret = 0;
 196         struct ulist_node *node = NULL;
 197         node = ulist_rbtree_search(ulist, val);
 198         if (node) {
 199                 if (old_aux)
 200                         *old_aux = node->aux;
 201                 return 0;
 202         }
 203
 204         if (ulist->nnodes >= ulist->nodes_alloced) {
 205                 u64 new_alloced = ulist->nodes_alloced + 128;
 206                 struct ulist_node *new_nodes;
 207                 void *old = NULL;
 208                 int i;
 209
 210                 for (i = 0; i < ulist->nnodes; i++)
 211                         rb_erase(&ulist->nodes[i].rb_node, &ulist->root);
 212
 213                 /*
 214                  * if nodes_alloced == ULIST_SIZE no memory has been allocated
 215                  * yet, so pass NULL to krealloc
 216                  */
 217                 if (ulist->nodes_alloced > ULIST_SIZE)
 218                         old = ulist->nodes;
 219
 220                 new_nodes = krealloc(old, sizeof(*new_nodes) * new_alloced,
 221                                      gfp_mask);
 222                 if (!new_nodes)
 223                         return -ENOMEM;
 224
 225                 if (!old)
 226                         memcpy(new_nodes, ulist->int_nodes,
 227                                sizeof(ulist->int_nodes));
 228
 229                 ulist->nodes = new_nodes;
 230                 ulist->nodes_alloced = new_alloced;
 231
 232                 /*
 233                  * krealloc actually uses memcpy, which does not copy rb_node
 234                  * pointers, so we have to do it ourselves.  Otherwise we may
 235                  * be bitten by crashes.
 236                  */
 237                 for (i = 0; i < ulist->nnodes; i++) {
 238                         ret = ulist_rbtree_insert(ulist, &ulist->nodes[i]);
 239                         if (ret < 0)
 240                                 return ret;
 241                 }
 242         }
 243         ulist->nodes[ulist->nnodes].val = val;
 244         ulist->nodes[ulist->nnodes].aux = aux;
 245         ret = ulist_rbtree_insert(ulist, &ulist->nodes[ulist->nnodes]);
 246         BUG_ON(ret);
 247         ++ulist->nnodes;
 248
 249         return 1;
 250 }
 251 EXPORT_SYMBOL(ulist_add);
 252
 253 /**
 254  * ulist_next - iterate ulist
 255  * @ulist:      ulist to iterate
 256  * @uiter:      iterator variable, initialized with ULIST_ITER_INIT(&iterator)
 257  *
 258  * Note: locking must be provided by the caller. In case of rwlocks only read
 259  *       locking is needed
 260  *
 261  * This function is used to iterate an ulist.
 262  * It returns the next element from the ulist or %NULL when the
 263  * end is reached. No guarantee is made with respect to the order in which
 264  * the elements are returned. They might neither be returned in order of
 265  * addition nor in ascending order.
 266  * It is allowed to call ulist_add during an enumeration. Newly added items
 267  * are guaranteed to show up in the running enumeration.
 268  */
 269 struct ulist_node *ulist_next(struct ulist *ulist, struct ulist_iterator *uiter)
 270 {
 271         if (ulist->nnodes == 0)
 272                 return NULL;
 273         if (uiter->i < 0 || uiter->i >= ulist->nnodes)
 274                 return NULL;
 275
 276         return &ulist->nodes[uiter->i++];
 277 }
 278 EXPORT_SYMBOL(ulist_next);