1 /*- 2 * Copyright (c) 2020 Mellanox Technologies, Ltd. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice unmodified, this list of conditions, and the following 10 * disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25 */ 26 27 #include <sys/cdefs.h> 28 #include <linux/xarray.h> 29 30 #include <vm/vm_pageout.h> 31 32 /* 33 * Linux' XArray allows to store a NULL pointer as a value. xa_load() would 34 * return NULL for both an unused index and an index set to NULL. But it 35 * impacts xa_alloc() which needs to find the next available index. 36 * 37 * However, our implementation relies on a radix tree (see `linux_radix.c`) 38 * which does not accept NULL pointers as values. I'm not sure this is a 39 * limitation or a feature, so to work around this, a NULL value is replaced by 40 * `NULL_VALUE`, an unlikely address, when we pass it to linux_radix. 41 */ 42 #define NULL_VALUE (void *)0x1 43 44 /* 45 * This function removes the element at the given index and returns 46 * the pointer to the removed element, if any. 47 */ 48 void * 49 __xa_erase(struct xarray *xa, uint32_t index) 50 { 51 void *retval; 52 53 XA_ASSERT_LOCKED(xa); 54 55 retval = radix_tree_delete(&xa->root, index); 56 if (retval == NULL_VALUE) 57 retval = NULL; 58 59 return (retval); 60 } 61 62 void * 63 xa_erase(struct xarray *xa, uint32_t index) 64 { 65 void *retval; 66 67 xa_lock(xa); 68 retval = __xa_erase(xa, index); 69 xa_unlock(xa); 70 71 return (retval); 72 } 73 74 /* 75 * This function returns the element pointer at the given index. A 76 * value of NULL is returned if the element does not exist. 77 */ 78 void * 79 xa_load(struct xarray *xa, uint32_t index) 80 { 81 void *retval; 82 83 xa_lock(xa); 84 retval = radix_tree_lookup(&xa->root, index); 85 xa_unlock(xa); 86 87 if (retval == NULL_VALUE) 88 retval = NULL; 89 90 return (retval); 91 } 92 93 /* 94 * This is an internal function used to sleep until more memory 95 * becomes available. 96 */ 97 static void 98 xa_vm_wait_locked(struct xarray *xa) 99 { 100 xa_unlock(xa); 101 vm_wait(NULL); 102 xa_lock(xa); 103 } 104 105 /* 106 * This function iterates the xarray until it finds a free slot where 107 * it can insert the element pointer to by "ptr". It starts at the 108 * index pointed to by "pindex" and updates this value at return. The 109 * "mask" argument defines the maximum index allowed, inclusivly, and 110 * must be a power of two minus one value. The "gfp" argument 111 * basically tells if we can wait for more memory to become available 112 * or not. This function returns zero upon success or a negative error 113 * code on failure. A typical error code is -ENOMEM which means either 114 * the xarray is full, or there was not enough internal memory 115 * available to complete the radix tree insertion. 116 */ 117 int 118 __xa_alloc(struct xarray *xa, uint32_t *pindex, void *ptr, uint32_t mask, gfp_t gfp) 119 { 120 int retval; 121 122 XA_ASSERT_LOCKED(xa); 123 124 /* mask should allow to allocate at least one item */ 125 MPASS(mask > ((xa->flags & XA_FLAGS_ALLOC1) != 0 ? 1 : 0)); 126 127 /* mask can be any power of two value minus one */ 128 MPASS((mask & (mask + 1)) == 0); 129 130 *pindex = (xa->flags & XA_FLAGS_ALLOC1) != 0 ? 1 : 0; 131 if (ptr == NULL) 132 ptr = NULL_VALUE; 133 retry: 134 retval = radix_tree_insert(&xa->root, *pindex, ptr); 135 136 switch (retval) { 137 case -EEXIST: 138 if (likely(*pindex != mask)) { 139 (*pindex)++; 140 goto retry; 141 } 142 retval = -ENOMEM; 143 break; 144 case -ENOMEM: 145 if (likely(gfp & M_WAITOK)) { 146 xa_vm_wait_locked(xa); 147 goto retry; 148 } 149 break; 150 default: 151 break; 152 } 153 return (retval); 154 } 155 156 int 157 xa_alloc(struct xarray *xa, uint32_t *pindex, void *ptr, uint32_t mask, gfp_t gfp) 158 { 159 int retval; 160 161 if (ptr == NULL) 162 ptr = NULL_VALUE; 163 164 xa_lock(xa); 165 retval = __xa_alloc(xa, pindex, ptr, mask, gfp); 166 xa_unlock(xa); 167 168 return (retval); 169 } 170 171 /* 172 * This function works the same like the "xa_alloc" function, except 173 * it wraps the next index value to zero when there are no entries 174 * left at the end of the xarray searching for a free slot from the 175 * beginning of the array. If the xarray is full -ENOMEM is returned. 176 */ 177 int 178 __xa_alloc_cyclic(struct xarray *xa, uint32_t *pindex, void *ptr, uint32_t mask, 179 uint32_t *pnext_index, gfp_t gfp) 180 { 181 int retval; 182 int timeout = 1; 183 184 XA_ASSERT_LOCKED(xa); 185 186 /* mask should allow to allocate at least one item */ 187 MPASS(mask > ((xa->flags & XA_FLAGS_ALLOC1) != 0 ? 1 : 0)); 188 189 /* mask can be any power of two value minus one */ 190 MPASS((mask & (mask + 1)) == 0); 191 192 *pnext_index = (xa->flags & XA_FLAGS_ALLOC1) != 0 ? 1 : 0; 193 if (ptr == NULL) 194 ptr = NULL_VALUE; 195 retry: 196 retval = radix_tree_insert(&xa->root, *pnext_index, ptr); 197 198 switch (retval) { 199 case -EEXIST: 200 if (unlikely(*pnext_index == mask) && !timeout--) { 201 retval = -ENOMEM; 202 break; 203 } 204 (*pnext_index)++; 205 (*pnext_index) &= mask; 206 if (*pnext_index == 0 && (xa->flags & XA_FLAGS_ALLOC1) != 0) 207 (*pnext_index)++; 208 goto retry; 209 case -ENOMEM: 210 if (likely(gfp & M_WAITOK)) { 211 xa_vm_wait_locked(xa); 212 goto retry; 213 } 214 break; 215 default: 216 break; 217 } 218 *pindex = *pnext_index; 219 220 return (retval); 221 } 222 223 int 224 xa_alloc_cyclic(struct xarray *xa, uint32_t *pindex, void *ptr, uint32_t mask, 225 uint32_t *pnext_index, gfp_t gfp) 226 { 227 int retval; 228 229 xa_lock(xa); 230 retval = __xa_alloc_cyclic(xa, pindex, ptr, mask, pnext_index, gfp); 231 xa_unlock(xa); 232 233 return (retval); 234 } 235 236 /* 237 * This function tries to insert an element at the given index. The 238 * "gfp" argument basically decides of this function can sleep or not 239 * trying to allocate internal memory for its radix tree. The 240 * function returns an error code upon failure. Typical error codes 241 * are element exists (-EEXIST) or out of memory (-ENOMEM). 242 */ 243 int 244 __xa_insert(struct xarray *xa, uint32_t index, void *ptr, gfp_t gfp) 245 { 246 int retval; 247 248 XA_ASSERT_LOCKED(xa); 249 if (ptr == NULL) 250 ptr = NULL_VALUE; 251 retry: 252 retval = radix_tree_insert(&xa->root, index, ptr); 253 254 switch (retval) { 255 case -ENOMEM: 256 if (likely(gfp & M_WAITOK)) { 257 xa_vm_wait_locked(xa); 258 goto retry; 259 } 260 break; 261 default: 262 break; 263 } 264 return (retval); 265 } 266 267 int 268 xa_insert(struct xarray *xa, uint32_t index, void *ptr, gfp_t gfp) 269 { 270 int retval; 271 272 xa_lock(xa); 273 retval = __xa_insert(xa, index, ptr, gfp); 274 xa_unlock(xa); 275 276 return (retval); 277 } 278 279 /* 280 * This function updates the element at the given index and returns a 281 * pointer to the old element. The "gfp" argument basically decides of 282 * this function can sleep or not trying to allocate internal memory 283 * for its radix tree. The function returns an XA_ERROR() pointer code 284 * upon failure. Code using this function must always check if the 285 * return value is an XA_ERROR() code before using the returned value. 286 */ 287 void * 288 __xa_store(struct xarray *xa, uint32_t index, void *ptr, gfp_t gfp) 289 { 290 int retval; 291 292 XA_ASSERT_LOCKED(xa); 293 if (ptr == NULL) 294 ptr = NULL_VALUE; 295 retry: 296 retval = radix_tree_store(&xa->root, index, &ptr); 297 298 switch (retval) { 299 case 0: 300 if (ptr == NULL_VALUE) 301 ptr = NULL; 302 break; 303 case -ENOMEM: 304 if (likely(gfp & M_WAITOK)) { 305 xa_vm_wait_locked(xa); 306 goto retry; 307 } 308 ptr = XA_ERROR(retval); 309 break; 310 default: 311 ptr = XA_ERROR(retval); 312 break; 313 } 314 return (ptr); 315 } 316 317 void * 318 xa_store(struct xarray *xa, uint32_t index, void *ptr, gfp_t gfp) 319 { 320 void *retval; 321 322 xa_lock(xa); 323 retval = __xa_store(xa, index, ptr, gfp); 324 xa_unlock(xa); 325 326 return (retval); 327 } 328 329 /* 330 * This function initialize an xarray structure. 331 */ 332 void 333 xa_init_flags(struct xarray *xa, uint32_t flags) 334 { 335 memset(xa, 0, sizeof(*xa)); 336 337 mtx_init(&xa->mtx, "lkpi-xarray", NULL, MTX_DEF | MTX_RECURSE); 338 xa->root.gfp_mask = GFP_NOWAIT; 339 xa->flags = flags; 340 } 341 342 /* 343 * This function destroys an xarray structure and all its internal 344 * memory and locks. 345 */ 346 void 347 xa_destroy(struct xarray *xa) 348 { 349 struct radix_tree_iter iter; 350 void **ppslot; 351 352 radix_tree_for_each_slot(ppslot, &xa->root, &iter, 0) 353 radix_tree_iter_delete(&xa->root, &iter, ppslot); 354 mtx_destroy(&xa->mtx); 355 } 356 357 /* 358 * This function checks if an xarray is empty or not. 359 * It returns true if empty, else false. 360 */ 361 bool 362 __xa_empty(struct xarray *xa) 363 { 364 struct radix_tree_iter iter = {}; 365 void **temp; 366 367 XA_ASSERT_LOCKED(xa); 368 369 return (!radix_tree_iter_find(&xa->root, &iter, &temp)); 370 } 371 372 bool 373 xa_empty(struct xarray *xa) 374 { 375 bool retval; 376 377 xa_lock(xa); 378 retval = __xa_empty(xa); 379 xa_unlock(xa); 380 381 return (retval); 382 } 383 384 /* 385 * This function returns the next valid xarray entry based on the 386 * index given by "pindex". The valued pointed to by "pindex" is 387 * updated before return. 388 */ 389 void * 390 __xa_next(struct xarray *xa, unsigned long *pindex, bool not_first) 391 { 392 struct radix_tree_iter iter = { .index = *pindex }; 393 void **ppslot; 394 void *retval; 395 bool found; 396 397 XA_ASSERT_LOCKED(xa); 398 399 if (not_first) { 400 /* advance to next index, if any */ 401 iter.index++; 402 if (iter.index == 0) 403 return (NULL); 404 } 405 406 found = radix_tree_iter_find(&xa->root, &iter, &ppslot); 407 if (likely(found)) { 408 retval = *ppslot; 409 if (retval == NULL_VALUE) 410 retval = NULL; 411 *pindex = iter.index; 412 } else { 413 retval = NULL; 414 } 415 return (retval); 416 } 417 418 void * 419 xa_next(struct xarray *xa, unsigned long *pindex, bool not_first) 420 { 421 void *retval; 422 423 xa_lock(xa); 424 retval = __xa_next(xa, pindex, not_first); 425 xa_unlock(xa); 426 427 return (retval); 428 } 429