linux_idr.c revision 302926
1/*- 2 * Copyright (c) 2010 Isilon Systems, Inc. 3 * Copyright (c) 2010 iX Systems, Inc. 4 * Copyright (c) 2010 Panasas, Inc. 5 * Copyright (c) 2013, 2014 Mellanox Technologies, Ltd. 6 * All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice unmodified, this list of conditions, and the following 13 * disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 */ 29 30#include <sys/param.h> 31#include <sys/systm.h> 32#include <sys/malloc.h> 33#include <sys/kernel.h> 34#include <sys/sysctl.h> 35#include <sys/lock.h> 36#include <sys/mutex.h> 37 38#include <machine/stdarg.h> 39 40#include <linux/bitops.h> 41#include <linux/kobject.h> 42#include <linux/slab.h> 43#include <linux/idr.h> 44#include <linux/err.h> 45 46/* 47 * IDR Implementation. 48 * 49 * This is quick and dirty and not as re-entrant as the linux version 50 * however it should be fairly fast. It is basically a radix tree with 51 * a builtin bitmap for allocation. 52 */ 53static MALLOC_DEFINE(M_IDR, "idr", "Linux IDR compat"); 54 55static inline int 56idr_max(struct idr *idr) 57{ 58 return (1 << (idr->layers * IDR_BITS)) - 1; 59} 60 61static inline int 62idr_pos(int id, int layer) 63{ 64 return (id >> (IDR_BITS * layer)) & IDR_MASK; 65} 66 67void 68idr_init(struct idr *idr) 69{ 70 bzero(idr, sizeof(*idr)); 71 mtx_init(&idr->lock, "idr", NULL, MTX_DEF); 72} 73 74/* Only frees cached pages. */ 75void 76idr_destroy(struct idr *idr) 77{ 78 struct idr_layer *il, *iln; 79 80 idr_remove_all(idr); 81 mtx_lock(&idr->lock); 82 for (il = idr->free; il != NULL; il = iln) { 83 iln = il->ary[0]; 84 free(il, M_IDR); 85 } 86 mtx_unlock(&idr->lock); 87} 88 89static void 90idr_remove_layer(struct idr_layer *il, int layer) 91{ 92 int i; 93 94 if (il == NULL) 95 return; 96 if (layer == 0) { 97 free(il, M_IDR); 98 return; 99 } 100 for (i = 0; i < IDR_SIZE; i++) 101 if (il->ary[i]) 102 idr_remove_layer(il->ary[i], layer - 1); 103} 104 105void 106idr_remove_all(struct idr *idr) 107{ 108 109 mtx_lock(&idr->lock); 110 idr_remove_layer(idr->top, idr->layers - 1); 111 idr->top = NULL; 112 idr->layers = 0; 113 mtx_unlock(&idr->lock); 114} 115 116void 117idr_remove(struct idr *idr, int id) 118{ 119 struct idr_layer *il; 120 int layer; 121 int idx; 122 123 id &= MAX_ID_MASK; 124 mtx_lock(&idr->lock); 125 il = idr->top; 126 layer = idr->layers - 1; 127 if (il == NULL || id > idr_max(idr)) { 128 mtx_unlock(&idr->lock); 129 return; 130 } 131 /* 132 * Walk down the tree to this item setting bitmaps along the way 133 * as we know at least one item will be free along this path. 134 */ 135 while (layer && il) { 136 idx = idr_pos(id, layer); 137 il->bitmap |= 1 << idx; 138 il = il->ary[idx]; 139 layer--; 140 } 141 idx = id & IDR_MASK; 142 /* 143 * At this point we've set free space bitmaps up the whole tree. 144 * We could make this non-fatal and unwind but linux dumps a stack 145 * and a warning so I don't think it's necessary. 146 */ 147 if (il == NULL || (il->bitmap & (1 << idx)) != 0) 148 panic("idr_remove: Item %d not allocated (%p, %p)\n", 149 id, idr, il); 150 il->ary[idx] = NULL; 151 il->bitmap |= 1 << idx; 152 mtx_unlock(&idr->lock); 153 return; 154} 155 156void * 157idr_replace(struct idr *idr, void *ptr, int id) 158{ 159 struct idr_layer *il; 160 void *res; 161 int layer; 162 int idx; 163 164 res = ERR_PTR(-EINVAL); 165 id &= MAX_ID_MASK; 166 mtx_lock(&idr->lock); 167 il = idr->top; 168 layer = idr->layers - 1; 169 if (il == NULL || id > idr_max(idr)) 170 goto out; 171 while (layer && il) { 172 il = il->ary[idr_pos(id, layer)]; 173 layer--; 174 } 175 idx = id & IDR_MASK; 176 /* 177 * Replace still returns an error if the item was not allocated. 178 */ 179 if (il != NULL && (il->bitmap & (1 << idx)) != 0) { 180 res = il->ary[idx]; 181 il->ary[idx] = ptr; 182 } 183out: 184 mtx_unlock(&idr->lock); 185 return (res); 186} 187 188static inline void * 189idr_find_locked(struct idr *idr, int id) 190{ 191 struct idr_layer *il; 192 void *res; 193 int layer; 194 195 mtx_assert(&idr->lock, MA_OWNED); 196 197 id &= MAX_ID_MASK; 198 res = NULL; 199 il = idr->top; 200 layer = idr->layers - 1; 201 if (il == NULL || id > idr_max(idr)) 202 return (NULL); 203 while (layer && il) { 204 il = il->ary[idr_pos(id, layer)]; 205 layer--; 206 } 207 if (il != NULL) 208 res = il->ary[id & IDR_MASK]; 209 return (res); 210} 211 212void * 213idr_find(struct idr *idr, int id) 214{ 215 void *res; 216 217 mtx_lock(&idr->lock); 218 res = idr_find_locked(idr, id); 219 mtx_unlock(&idr->lock); 220 return (res); 221} 222 223int 224idr_pre_get(struct idr *idr, gfp_t gfp_mask) 225{ 226 struct idr_layer *il, *iln; 227 struct idr_layer *head; 228 int need; 229 230 mtx_lock(&idr->lock); 231 for (;;) { 232 need = idr->layers + 1; 233 for (il = idr->free; il != NULL; il = il->ary[0]) 234 need--; 235 mtx_unlock(&idr->lock); 236 if (need == 0) 237 break; 238 for (head = NULL; need; need--) { 239 iln = malloc(sizeof(*il), M_IDR, M_ZERO | gfp_mask); 240 if (iln == NULL) 241 break; 242 bitmap_fill(&iln->bitmap, IDR_SIZE); 243 if (head != NULL) { 244 il->ary[0] = iln; 245 il = iln; 246 } else 247 head = il = iln; 248 } 249 if (head == NULL) 250 return (0); 251 mtx_lock(&idr->lock); 252 il->ary[0] = idr->free; 253 idr->free = head; 254 } 255 return (1); 256} 257 258static inline struct idr_layer * 259idr_get(struct idr *idr) 260{ 261 struct idr_layer *il; 262 263 il = idr->free; 264 if (il) { 265 idr->free = il->ary[0]; 266 il->ary[0] = NULL; 267 return (il); 268 } 269 il = malloc(sizeof(*il), M_IDR, M_ZERO | M_NOWAIT); 270 if (il != NULL) 271 bitmap_fill(&il->bitmap, IDR_SIZE); 272 return (il); 273} 274 275/* 276 * Could be implemented as get_new_above(idr, ptr, 0, idp) but written 277 * first for simplicity sake. 278 */ 279int 280idr_get_new(struct idr *idr, void *ptr, int *idp) 281{ 282 struct idr_layer *stack[MAX_LEVEL]; 283 struct idr_layer *il; 284 int error; 285 int layer; 286 int idx; 287 int id; 288 289 error = -EAGAIN; 290 mtx_lock(&idr->lock); 291 /* 292 * Expand the tree until there is free space. 293 */ 294 if (idr->top == NULL || idr->top->bitmap == 0) { 295 if (idr->layers == MAX_LEVEL + 1) { 296 error = -ENOSPC; 297 goto out; 298 } 299 il = idr_get(idr); 300 if (il == NULL) 301 goto out; 302 il->ary[0] = idr->top; 303 if (idr->top) 304 il->bitmap &= ~1; 305 idr->top = il; 306 idr->layers++; 307 } 308 il = idr->top; 309 id = 0; 310 /* 311 * Walk the tree following free bitmaps, record our path. 312 */ 313 for (layer = idr->layers - 1;; layer--) { 314 stack[layer] = il; 315 idx = ffsl(il->bitmap); 316 if (idx == 0) 317 panic("idr_get_new: Invalid leaf state (%p, %p)\n", 318 idr, il); 319 idx--; 320 id |= idx << (layer * IDR_BITS); 321 if (layer == 0) 322 break; 323 if (il->ary[idx] == NULL) { 324 il->ary[idx] = idr_get(idr); 325 if (il->ary[idx] == NULL) 326 goto out; 327 } 328 il = il->ary[idx]; 329 } 330 /* 331 * Allocate the leaf to the consumer. 332 */ 333 il->bitmap &= ~(1 << idx); 334 il->ary[idx] = ptr; 335 *idp = id; 336 /* 337 * Clear bitmaps potentially up to the root. 338 */ 339 while (il->bitmap == 0 && ++layer < idr->layers) { 340 il = stack[layer]; 341 il->bitmap &= ~(1 << idr_pos(id, layer)); 342 } 343 error = 0; 344out: 345#ifdef INVARIANTS 346 if (error == 0 && idr_find_locked(idr, id) != ptr) { 347 panic("idr_get_new: Failed for idr %p, id %d, ptr %p\n", 348 idr, id, ptr); 349 } 350#endif 351 mtx_unlock(&idr->lock); 352 return (error); 353} 354 355int 356idr_get_new_above(struct idr *idr, void *ptr, int starting_id, int *idp) 357{ 358 struct idr_layer *stack[MAX_LEVEL]; 359 struct idr_layer *il; 360 int error; 361 int layer; 362 int idx, sidx; 363 int id; 364 365 error = -EAGAIN; 366 mtx_lock(&idr->lock); 367 /* 368 * Compute the layers required to support starting_id and the mask 369 * at the top layer. 370 */ 371restart: 372 idx = starting_id; 373 layer = 0; 374 while (idx & ~IDR_MASK) { 375 layer++; 376 idx >>= IDR_BITS; 377 } 378 if (layer == MAX_LEVEL + 1) { 379 error = -ENOSPC; 380 goto out; 381 } 382 /* 383 * Expand the tree until there is free space at or beyond starting_id. 384 */ 385 while (idr->layers <= layer || 386 idr->top->bitmap < (1 << idr_pos(starting_id, idr->layers - 1))) { 387 if (idr->layers == MAX_LEVEL + 1) { 388 error = -ENOSPC; 389 goto out; 390 } 391 il = idr_get(idr); 392 if (il == NULL) 393 goto out; 394 il->ary[0] = idr->top; 395 if (idr->top && idr->top->bitmap == 0) 396 il->bitmap &= ~1; 397 idr->top = il; 398 idr->layers++; 399 } 400 il = idr->top; 401 id = 0; 402 /* 403 * Walk the tree following free bitmaps, record our path. 404 */ 405 for (layer = idr->layers - 1;; layer--) { 406 stack[layer] = il; 407 sidx = idr_pos(starting_id, layer); 408 /* Returns index numbered from 0 or size if none exists. */ 409 idx = find_next_bit(&il->bitmap, IDR_SIZE, sidx); 410 if (idx == IDR_SIZE && sidx == 0) 411 panic("idr_get_new: Invalid leaf state (%p, %p)\n", 412 idr, il); 413 /* 414 * We may have walked a path where there was a free bit but 415 * it was lower than what we wanted. Restart the search with 416 * a larger starting id. id contains the progress we made so 417 * far. Search the leaf one above this level. This may 418 * restart as many as MAX_LEVEL times but that is expected 419 * to be rare. 420 */ 421 if (idx == IDR_SIZE) { 422 starting_id = id + (1 << ((layer + 1) * IDR_BITS)); 423 goto restart; 424 } 425 if (idx > sidx) 426 starting_id = 0; /* Search the whole subtree. */ 427 id |= idx << (layer * IDR_BITS); 428 if (layer == 0) 429 break; 430 if (il->ary[idx] == NULL) { 431 il->ary[idx] = idr_get(idr); 432 if (il->ary[idx] == NULL) 433 goto out; 434 } 435 il = il->ary[idx]; 436 } 437 /* 438 * Allocate the leaf to the consumer. 439 */ 440 il->bitmap &= ~(1 << idx); 441 il->ary[idx] = ptr; 442 *idp = id; 443 /* 444 * Clear bitmaps potentially up to the root. 445 */ 446 while (il->bitmap == 0 && ++layer < idr->layers) { 447 il = stack[layer]; 448 il->bitmap &= ~(1 << idr_pos(id, layer)); 449 } 450 error = 0; 451out: 452#ifdef INVARIANTS 453 if (error == 0 && idr_find_locked(idr, id) != ptr) { 454 panic("idr_get_new_above: Failed for idr %p, id %d, ptr %p\n", 455 idr, id, ptr); 456 } 457#endif 458 mtx_unlock(&idr->lock); 459 return (error); 460} 461