src/util/sparse_array.c

   1 /*
   2  * Copyright © 2019 Intel Corporation
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  21  * IN THE SOFTWARE.
  22  */
  23
  24 #include "sparse_array.h"
  25
  26 struct util_sparse_array_node {
  27    uint32_t level;
  28    uint32_t _pad;
  29    uint64_t max_idx;
  30 };
  31
  32 void
  33 util_sparse_array_init(struct util_sparse_array *arr,
  34                        size_t elem_size, size_t node_size)
  35 {
  36    memset(arr, 0, sizeof(*arr));
  37    arr->elem_size = elem_size;
  38    arr->node_size_log2 = util_logbase2_64(node_size);
  39    assert(node_size >= 2 && node_size == (1ull << arr->node_size_log2));
  40 }
  41
  42 static inline void *
  43 _util_sparse_array_node_data(struct util_sparse_array_node *node)
  44 {
  45    return node + 1;
  46 }
  47
  48 static inline void
  49 _util_sparse_array_node_finish(struct util_sparse_array *arr,
  50                                struct util_sparse_array_node *node)
  51 {
  52    if (node->level > 0) {
  53       struct util_sparse_array_node **children =
  54          _util_sparse_array_node_data(node);
  55       size_t node_size = 1ull << arr->node_size_log2;
  56       for (size_t i = 0; i < node_size; i++) {
  57          if (children[i] != NULL)
  58             _util_sparse_array_node_finish(arr, children[i]);
  59       }
  60    }
  61
  62    free(node);
  63 }
  64
  65 void
  66 util_sparse_array_finish(struct util_sparse_array *arr)
  67 {
  68    if (arr->root)
  69       _util_sparse_array_node_finish(arr, arr->root);
  70 }
  71
  72 static inline struct util_sparse_array_node *
  73 _util_sparse_array_alloc_node(struct util_sparse_array *arr,
  74                               unsigned level)
  75 {
  76    size_t size = sizeof(struct util_sparse_array_node);
  77    if (level == 0) {
  78       size += arr->elem_size << arr->node_size_log2;
  79    } else {
  80       size += sizeof(struct util_sparse_array_node *) << arr->node_size_log2;
  81    }
  82
  83    struct util_sparse_array_node *node = calloc(1, size);
  84    node->level = level;
  85
  86    return node;
  87 }
  88
  89 static inline struct util_sparse_array_node *
  90 _util_sparse_array_set_or_free_node(struct util_sparse_array_node **node_ptr,
  91                                     struct util_sparse_array_node *cmp_node,
  92                                     struct util_sparse_array_node *node)
  93 {
  94    struct util_sparse_array_node *prev_node =
  95       p_atomic_cmpxchg(node_ptr, cmp_node, node);
  96
  97    if (prev_node != cmp_node) {
  98       /* We lost the race.  Free this one and return the one that was already
  99        * allocated.
 100        */
 101       free(node);
 102       return prev_node;
 103    } else {
 104       return node;
 105    }
 106 }
 107
 108 void *
 109 util_sparse_array_get(struct util_sparse_array *arr, uint64_t idx)
 110 {
 111    struct util_sparse_array_node *root = p_atomic_read(&arr->root);
 112    if (unlikely(root == NULL)) {
 113       unsigned root_level = 0;
 114       uint64_t idx_iter = idx >> arr->node_size_log2;
 115       while (idx_iter) {
 116          idx_iter >>= arr->node_size_log2;
 117          root_level++;
 118       }
 119       struct util_sparse_array_node *new_root =
 120          _util_sparse_array_alloc_node(arr, root_level);
 121       root = _util_sparse_array_set_or_free_node(&arr->root, NULL, new_root);
 122    }
 123
 124    while (1) {
 125       uint64_t root_idx = idx >> (root->level * arr->node_size_log2);
 126       if (likely(root_idx < (1ull << arr->node_size_log2)))
 127          break;
 128
 129       /* In this case, we have a root but its level is low enough that the
 130        * requested index is out-of-bounds.
 131        */
 132       struct util_sparse_array_node *new_root =
 133          _util_sparse_array_alloc_node(arr, root->level + 1);
 134
 135       struct util_sparse_array_node **new_root_children =
 136          _util_sparse_array_node_data(new_root);
 137       new_root_children[0] = root;
 138
 139       /* We only add one at a time instead of the whole tree because it's
 140        * easier to ensure correctness of both the tree building and the
 141        * clean-up path.  Because we're only adding one node we never have to
 142        * worry about trying to free multiple things without freeing the old
 143        * things.
 144        */
 145       root = _util_sparse_array_set_or_free_node(&arr->root, root, new_root);
 146    }
 147
 148    struct util_sparse_array_node *node = root;
 149    while (node->level > 0) {
 150       uint64_t child_idx = (idx >> (node->level * arr->node_size_log2)) &
 151                            ((1ull << arr->node_size_log2) - 1);
 152
 153       struct util_sparse_array_node **children =
 154          _util_sparse_array_node_data(node);
 155       struct util_sparse_array_node *child =
 156          p_atomic_read(&children[child_idx]);
 157
 158       if (unlikely(child == NULL)) {
 159          child = _util_sparse_array_alloc_node(arr, node->level - 1);
 160          child = _util_sparse_array_set_or_free_node(&children[child_idx],
 161                                                      NULL, child);
 162       }
 163
 164       node = child;
 165    }
 166
 167    uint64_t elem_idx = idx & ((1ull << arr->node_size_log2) - 1);
 168    return (void *)((char *)_util_sparse_array_node_data(node) +
 169                    (elem_idx * arr->elem_size));
 170 }
 171
 172 static void
 173 validate_node_level(struct util_sparse_array *arr,
 174                     struct util_sparse_array_node *node,
 175                     unsigned level)
 176 {
 177    assert(node->level == level);
 178
 179    if (node->level > 0) {
 180       struct util_sparse_array_node **children =
 181          _util_sparse_array_node_data(node);
 182       size_t node_size = 1ull << arr->node_size_log2;
 183       for (size_t i = 0; i < node_size; i++) {
 184          if (children[i] != NULL)
 185             validate_node_level(arr, children[i], level - 1);
 186       }
 187    }
 188 }
 189
 190 void
 191 util_sparse_array_validate(struct util_sparse_array *arr)
 192 {
 193    validate_node_level(arr, arr->root, arr->root->level);
 194 }
 195
 196 void
 197 util_sparse_array_free_list_init(struct util_sparse_array_free_list *fl,
 198                                  struct util_sparse_array *arr,
 199                                  uint32_t sentinel,
 200                                  uint32_t next_offset)
 201 {
 202    fl->head = sentinel;
 203    fl->arr = arr;
 204    fl->sentinel = sentinel;
 205    fl->next_offset = next_offset;
 206 }
 207
 208 static uint64_t
 209 free_list_head(uint64_t old, uint32_t next)
 210 {
 211    return ((old & 0xffffffff00000000ull) + 0x100000000ull) | next;
 212 }
 213
 214 void
 215 util_sparse_array_free_list_push(struct util_sparse_array_free_list *fl,
 216                                  uint32_t *items, unsigned num_items)
 217 {
 218    assert(num_items > 0);
 219    assert(items[0] != fl->sentinel);
 220    void *last_elem = util_sparse_array_get(fl->arr, items[0]);
 221    uint32_t *last_next = (uint32_t *)((char *)last_elem + fl->next_offset);
 222    for (unsigned i = 1; i < num_items; i++) {
 223       *last_next = items[i];
 224       assert(items[i] != fl->sentinel);
 225       last_elem = util_sparse_array_get(fl->arr, items[i]);
 226       last_next = (uint32_t *)((char *)last_elem + fl->next_offset);
 227    }
 228
 229    uint64_t current_head, old_head;
 230    old_head = p_atomic_read(&fl->head);
 231    do {
 232       current_head = old_head;
 233       *last_next = current_head; /* Index is the bottom 32 bits */
 234       uint64_t new_head = free_list_head(current_head, items[0]);
 235       old_head = p_atomic_cmpxchg(&fl->head, current_head, new_head);
 236    } while (old_head != current_head);
 237 }
 238
 239 uint32_t
 240 util_sparse_array_free_list_pop_idx(struct util_sparse_array_free_list *fl)
 241 {
 242    uint64_t current_head;
 243
 244    current_head = p_atomic_read(&fl->head);
 245    while (1) {
 246       if ((uint32_t)current_head == fl->sentinel)
 247          return fl->sentinel;
 248
 249       uint32_t head_idx = current_head; /* Index is the bottom 32 bits */
 250       void *head_elem = util_sparse_array_get(fl->arr, head_idx);
 251       uint32_t *head_next = (uint32_t *)((char *)head_elem + fl->next_offset);
 252       uint32_t new_head = free_list_head(current_head, *head_next);
 253       uint64_t old_head = p_atomic_cmpxchg(&fl->head, current_head, new_head);
 254       if (old_head == current_head)
 255          return head_idx;
 256       current_head = old_head;
 257    }
 258 }
 259
 260 void *
 261 util_sparse_array_free_list_pop_elem(struct util_sparse_array_free_list *fl)
 262 {
 263    uint64_t current_head;
 264
 265    current_head = p_atomic_read(&fl->head);
 266    while (1) {
 267       if ((uint32_t)current_head == fl->sentinel)
 268          return NULL;
 269
 270       uint32_t head_idx = current_head; /* Index is the bottom 32 bits */
 271       void *head_elem = util_sparse_array_get(fl->arr, head_idx);
 272       uint32_t *head_next = (uint32_t *)((char *)head_elem + fl->next_offset);
 273       uint32_t new_head = free_list_head(current_head, *head_next);
 274       uint64_t old_head = p_atomic_cmpxchg(&fl->head, current_head, new_head);
 275       if (old_head == current_head)
 276          return head_elem;
 277       current_head = old_head;
 278    }
 279 }