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 __FBSDID("$FreeBSD$"); 29 30 #include <linux/xarray.h> 31 32 #include <vm/vm_pageout.h> 33 34 /* 35 * This function removes the element at the given index and returns 36 * the pointer to the removed element, if any. 37 */ 38 void * 39 __xa_erase(struct xarray *xa, uint32_t index) 40 { 41 XA_ASSERT_LOCKED(xa); 42 43 return (radix_tree_delete(&xa->root, index)); 44 } 45 46 void * 47 xa_erase(struct xarray *xa, uint32_t index) 48 { 49 void *retval; 50 51 xa_lock(xa); 52 retval = __xa_erase(xa, index); 53 xa_unlock(xa); 54 55 return (retval); 56 } 57 58 /* 59 * This function returns the element pointer at the given index. A 60 * value of NULL is returned if the element does not exist. 61 */ 62 void * 63 xa_load(struct xarray *xa, uint32_t index) 64 { 65 void *retval; 66 67 xa_lock(xa); 68 retval = radix_tree_lookup(&xa->root, index); 69 xa_unlock(xa); 70 71 return (retval); 72 } 73 74 /* 75 * This is an internal function used to sleep until more memory 76 * becomes available. 77 */ 78 static void 79 xa_vm_wait_locked(struct xarray *xa) 80 { 81 xa_unlock(xa); 82 vm_wait(NULL); 83 xa_lock(xa); 84 } 85 86 /* 87 * This function iterates the xarray until it finds a free slot where 88 * it can insert the element pointer to by "ptr". It starts at the 89 * index pointed to by "pindex" and updates this value at return. The 90 * "mask" argument defines the maximum index allowed, inclusivly, and 91 * must be a power of two minus one value. The "gfp" argument 92 * basically tells if we can wait for more memory to become available 93 * or not. This function returns zero upon success or a negative error 94 * code on failure. A typical error code is -ENOMEM which means either 95 * the xarray is full, or there was not enough internal memory 96 * available to complete the radix tree insertion. 97 */ 98 int 99 __xa_alloc(struct xarray *xa, uint32_t *pindex, void *ptr, uint32_t mask, gfp_t gfp) 100 { 101 int retval; 102 103 XA_ASSERT_LOCKED(xa); 104 105 /* mask cannot be zero */ 106 MPASS(mask != 0); 107 108 /* mask can be any power of two value minus one */ 109 MPASS((mask & (mask + 1)) == 0); 110 111 *pindex = 0; 112 retry: 113 retval = radix_tree_insert(&xa->root, *pindex, ptr); 114 115 switch (retval) { 116 case -EEXIST: 117 if (likely(*pindex != mask)) { 118 (*pindex)++; 119 goto retry; 120 } 121 retval = -ENOMEM; 122 break; 123 case -ENOMEM: 124 if (likely(gfp & M_WAITOK)) { 125 xa_vm_wait_locked(xa); 126 goto retry; 127 } 128 break; 129 default: 130 break; 131 } 132 return (retval); 133 } 134 135 int 136 xa_alloc(struct xarray *xa, uint32_t *pindex, void *ptr, uint32_t mask, gfp_t gfp) 137 { 138 int retval; 139 140 xa_lock(xa); 141 retval = __xa_alloc(xa, pindex, ptr, mask, gfp); 142 xa_unlock(xa); 143 144 return (retval); 145 } 146 147 /* 148 * This function works the same like the "xa_alloc" function, except 149 * it wraps the next index value to zero when there are no entries 150 * left at the end of the xarray searching for a free slot from the 151 * beginning of the array. If the xarray is full -ENOMEM is returned. 152 */ 153 int 154 __xa_alloc_cyclic(struct xarray *xa, uint32_t *pindex, void *ptr, uint32_t mask, 155 uint32_t *pnext_index, gfp_t gfp) 156 { 157 int retval; 158 int timeout = 1; 159 160 XA_ASSERT_LOCKED(xa); 161 162 /* mask cannot be zero */ 163 MPASS(mask != 0); 164 165 /* mask can be any power of two value minus one */ 166 MPASS((mask & (mask + 1)) == 0); 167 168 *pnext_index = 0; 169 retry: 170 retval = radix_tree_insert(&xa->root, *pnext_index, ptr); 171 172 switch (retval) { 173 case -EEXIST: 174 if (unlikely(*pnext_index == mask) && !timeout--) { 175 retval = -ENOMEM; 176 break; 177 } 178 (*pnext_index)++; 179 (*pnext_index) &= mask; 180 goto retry; 181 case -ENOMEM: 182 if (likely(gfp & M_WAITOK)) { 183 xa_vm_wait_locked(xa); 184 goto retry; 185 } 186 break; 187 default: 188 break; 189 } 190 *pindex = *pnext_index; 191 192 return (retval); 193 } 194 195 int 196 xa_alloc_cyclic(struct xarray *xa, uint32_t *pindex, void *ptr, uint32_t mask, 197 uint32_t *pnext_index, gfp_t gfp) 198 { 199 int retval; 200 201 xa_lock(xa); 202 retval = __xa_alloc_cyclic(xa, pindex, ptr, mask, pnext_index, gfp); 203 xa_unlock(xa); 204 205 return (retval); 206 } 207 208 /* 209 * This function tries to insert an element at the given index. The 210 * "gfp" argument basically decides of this function can sleep or not 211 * trying to allocate internal memory for its radix tree. The 212 * function returns an error code upon failure. Typical error codes 213 * are element exists (-EEXIST) or out of memory (-ENOMEM). 214 */ 215 int 216 __xa_insert(struct xarray *xa, uint32_t index, void *ptr, gfp_t gfp) 217 { 218 int retval; 219 220 XA_ASSERT_LOCKED(xa); 221 retry: 222 retval = radix_tree_insert(&xa->root, index, ptr); 223 224 switch (retval) { 225 case -ENOMEM: 226 if (likely(gfp & M_WAITOK)) { 227 xa_vm_wait_locked(xa); 228 goto retry; 229 } 230 break; 231 default: 232 break; 233 } 234 return (retval); 235 } 236 237 int 238 xa_insert(struct xarray *xa, uint32_t index, void *ptr, gfp_t gfp) 239 { 240 int retval; 241 242 xa_lock(xa); 243 retval = __xa_insert(xa, index, ptr, gfp); 244 xa_unlock(xa); 245 246 return (retval); 247 } 248 249 /* 250 * This function updates the element at the given index and returns a 251 * pointer to the old element. The "gfp" argument basically decides of 252 * this function can sleep or not trying to allocate internal memory 253 * for its radix tree. The function returns an XA_ERROR() pointer code 254 * upon failure. Code using this function must always check if the 255 * return value is an XA_ERROR() code before using the returned value. 256 */ 257 void * 258 __xa_store(struct xarray *xa, uint32_t index, void *ptr, gfp_t gfp) 259 { 260 int retval; 261 262 XA_ASSERT_LOCKED(xa); 263 retry: 264 retval = radix_tree_store(&xa->root, index, &ptr); 265 266 switch (retval) { 267 case 0: 268 break; 269 case -ENOMEM: 270 if (likely(gfp & M_WAITOK)) { 271 xa_vm_wait_locked(xa); 272 goto retry; 273 } 274 ptr = XA_ERROR(retval); 275 break; 276 default: 277 ptr = XA_ERROR(retval); 278 break; 279 } 280 return (ptr); 281 } 282 283 void * 284 xa_store(struct xarray *xa, uint32_t index, void *ptr, gfp_t gfp) 285 { 286 void *retval; 287 288 xa_lock(xa); 289 retval = __xa_store(xa, index, ptr, gfp); 290 xa_unlock(xa); 291 292 return (retval); 293 } 294 295 /* 296 * This function initialize an xarray structure. 297 */ 298 void 299 xa_init_flags(struct xarray *xa, uint32_t flags) 300 { 301 memset(xa, 0, sizeof(*xa)); 302 303 mtx_init(&xa->mtx, "lkpi-xarray", NULL, MTX_DEF | MTX_RECURSE); 304 xa->root.gfp_mask = GFP_NOWAIT; 305 } 306 307 /* 308 * This function destroys an xarray structure and all its internal 309 * memory and locks. 310 */ 311 void 312 xa_destroy(struct xarray *xa) 313 { 314 struct radix_tree_iter iter; 315 void **ppslot; 316 317 radix_tree_for_each_slot(ppslot, &xa->root, &iter, 0) 318 radix_tree_iter_delete(&xa->root, &iter, ppslot); 319 mtx_destroy(&xa->mtx); 320 } 321 322 /* 323 * This function checks if an xarray is empty or not. 324 * It returns true if empty, else false. 325 */ 326 bool 327 __xa_empty(struct xarray *xa) 328 { 329 struct radix_tree_iter iter = {}; 330 void **temp; 331 332 XA_ASSERT_LOCKED(xa); 333 334 return (!radix_tree_iter_find(&xa->root, &iter, &temp)); 335 } 336 337 bool 338 xa_empty(struct xarray *xa) 339 { 340 bool retval; 341 342 xa_lock(xa); 343 retval = __xa_empty(xa); 344 xa_unlock(xa); 345 346 return (retval); 347 } 348 349 /* 350 * This function returns the next valid xarray entry based on the 351 * index given by "pindex". The valued pointed to by "pindex" is 352 * updated before return. 353 */ 354 void * 355 __xa_next(struct xarray *xa, unsigned long *pindex, bool not_first) 356 { 357 struct radix_tree_iter iter = { .index = *pindex }; 358 void **ppslot; 359 void *retval; 360 bool found; 361 362 XA_ASSERT_LOCKED(xa); 363 364 if (not_first) { 365 /* advance to next index, if any */ 366 iter.index++; 367 if (iter.index == 0) 368 return (NULL); 369 } 370 371 found = radix_tree_iter_find(&xa->root, &iter, &ppslot); 372 if (likely(found)) { 373 retval = *ppslot; 374 *pindex = iter.index; 375 } else { 376 retval = NULL; 377 } 378 return (retval); 379 } 380 381 void * 382 xa_next(struct xarray *xa, unsigned long *pindex, bool not_first) 383 { 384 void *retval; 385 386 xa_lock(xa); 387 retval = __xa_next(xa, pindex, not_first); 388 xa_unlock(xa); 389 390 return (retval); 391 } 392