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 should allow to allocate at least one item */ 106 MPASS(mask > ((xa->flags & XA_FLAGS_ALLOC1) != 0 ? 1 : 0)); 107 108 /* mask can be any power of two value minus one */ 109 MPASS((mask & (mask + 1)) == 0); 110 111 *pindex = (xa->flags & XA_FLAGS_ALLOC1) != 0 ? 1 : 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 should allow to allocate at least one item */ 163 MPASS(mask > ((xa->flags & XA_FLAGS_ALLOC1) != 0 ? 1 : 0)); 164 165 /* mask can be any power of two value minus one */ 166 MPASS((mask & (mask + 1)) == 0); 167 168 *pnext_index = (xa->flags & XA_FLAGS_ALLOC1) != 0 ? 1 : 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 if (*pnext_index == 0 && (xa->flags & XA_FLAGS_ALLOC1) != 0) 181 (*pnext_index)++; 182 goto retry; 183 case -ENOMEM: 184 if (likely(gfp & M_WAITOK)) { 185 xa_vm_wait_locked(xa); 186 goto retry; 187 } 188 break; 189 default: 190 break; 191 } 192 *pindex = *pnext_index; 193 194 return (retval); 195 } 196 197 int 198 xa_alloc_cyclic(struct xarray *xa, uint32_t *pindex, void *ptr, uint32_t mask, 199 uint32_t *pnext_index, gfp_t gfp) 200 { 201 int retval; 202 203 xa_lock(xa); 204 retval = __xa_alloc_cyclic(xa, pindex, ptr, mask, pnext_index, gfp); 205 xa_unlock(xa); 206 207 return (retval); 208 } 209 210 /* 211 * This function tries to insert an element at the given index. The 212 * "gfp" argument basically decides of this function can sleep or not 213 * trying to allocate internal memory for its radix tree. The 214 * function returns an error code upon failure. Typical error codes 215 * are element exists (-EEXIST) or out of memory (-ENOMEM). 216 */ 217 int 218 __xa_insert(struct xarray *xa, uint32_t index, void *ptr, gfp_t gfp) 219 { 220 int retval; 221 222 XA_ASSERT_LOCKED(xa); 223 retry: 224 retval = radix_tree_insert(&xa->root, index, ptr); 225 226 switch (retval) { 227 case -ENOMEM: 228 if (likely(gfp & M_WAITOK)) { 229 xa_vm_wait_locked(xa); 230 goto retry; 231 } 232 break; 233 default: 234 break; 235 } 236 return (retval); 237 } 238 239 int 240 xa_insert(struct xarray *xa, uint32_t index, void *ptr, gfp_t gfp) 241 { 242 int retval; 243 244 xa_lock(xa); 245 retval = __xa_insert(xa, index, ptr, gfp); 246 xa_unlock(xa); 247 248 return (retval); 249 } 250 251 /* 252 * This function updates the element at the given index and returns a 253 * pointer to the old element. The "gfp" argument basically decides of 254 * this function can sleep or not trying to allocate internal memory 255 * for its radix tree. The function returns an XA_ERROR() pointer code 256 * upon failure. Code using this function must always check if the 257 * return value is an XA_ERROR() code before using the returned value. 258 */ 259 void * 260 __xa_store(struct xarray *xa, uint32_t index, void *ptr, gfp_t gfp) 261 { 262 int retval; 263 264 XA_ASSERT_LOCKED(xa); 265 retry: 266 retval = radix_tree_store(&xa->root, index, &ptr); 267 268 switch (retval) { 269 case 0: 270 break; 271 case -ENOMEM: 272 if (likely(gfp & M_WAITOK)) { 273 xa_vm_wait_locked(xa); 274 goto retry; 275 } 276 ptr = XA_ERROR(retval); 277 break; 278 default: 279 ptr = XA_ERROR(retval); 280 break; 281 } 282 return (ptr); 283 } 284 285 void * 286 xa_store(struct xarray *xa, uint32_t index, void *ptr, gfp_t gfp) 287 { 288 void *retval; 289 290 xa_lock(xa); 291 retval = __xa_store(xa, index, ptr, gfp); 292 xa_unlock(xa); 293 294 return (retval); 295 } 296 297 /* 298 * This function initialize an xarray structure. 299 */ 300 void 301 xa_init_flags(struct xarray *xa, uint32_t flags) 302 { 303 memset(xa, 0, sizeof(*xa)); 304 305 mtx_init(&xa->mtx, "lkpi-xarray", NULL, MTX_DEF | MTX_RECURSE); 306 xa->root.gfp_mask = GFP_NOWAIT; 307 xa->flags = flags; 308 } 309 310 /* 311 * This function destroys an xarray structure and all its internal 312 * memory and locks. 313 */ 314 void 315 xa_destroy(struct xarray *xa) 316 { 317 struct radix_tree_iter iter; 318 void **ppslot; 319 320 radix_tree_for_each_slot(ppslot, &xa->root, &iter, 0) 321 radix_tree_iter_delete(&xa->root, &iter, ppslot); 322 mtx_destroy(&xa->mtx); 323 } 324 325 /* 326 * This function checks if an xarray is empty or not. 327 * It returns true if empty, else false. 328 */ 329 bool 330 __xa_empty(struct xarray *xa) 331 { 332 struct radix_tree_iter iter = {}; 333 void **temp; 334 335 XA_ASSERT_LOCKED(xa); 336 337 return (!radix_tree_iter_find(&xa->root, &iter, &temp)); 338 } 339 340 bool 341 xa_empty(struct xarray *xa) 342 { 343 bool retval; 344 345 xa_lock(xa); 346 retval = __xa_empty(xa); 347 xa_unlock(xa); 348 349 return (retval); 350 } 351 352 /* 353 * This function returns the next valid xarray entry based on the 354 * index given by "pindex". The valued pointed to by "pindex" is 355 * updated before return. 356 */ 357 void * 358 __xa_next(struct xarray *xa, unsigned long *pindex, bool not_first) 359 { 360 struct radix_tree_iter iter = { .index = *pindex }; 361 void **ppslot; 362 void *retval; 363 bool found; 364 365 XA_ASSERT_LOCKED(xa); 366 367 if (not_first) { 368 /* advance to next index, if any */ 369 iter.index++; 370 if (iter.index == 0) 371 return (NULL); 372 } 373 374 found = radix_tree_iter_find(&xa->root, &iter, &ppslot); 375 if (likely(found)) { 376 retval = *ppslot; 377 *pindex = iter.index; 378 } else { 379 retval = NULL; 380 } 381 return (retval); 382 } 383 384 void * 385 xa_next(struct xarray *xa, unsigned long *pindex, bool not_first) 386 { 387 void *retval; 388 389 xa_lock(xa); 390 retval = __xa_next(xa, pindex, not_first); 391 xa_unlock(xa); 392 393 return (retval); 394 } 395