linux_idr.c revision 271127
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 mtx_lock(&idr->lock); 81 for (il = idr->free; il != NULL; il = iln) { 82 iln = il->ary[0]; 83 free(il, M_IDR); 84 } 85 mtx_unlock(&idr->lock); 86} 87 88static void 89idr_remove_layer(struct idr_layer *il, int layer) 90{ 91 int i; 92 93 if (il == NULL) 94 return; 95 if (layer == 0) { 96 free(il, M_IDR); 97 return; 98 } 99 for (i = 0; i < IDR_SIZE; i++) 100 if (il->ary[i]) 101 idr_remove_layer(il->ary[i], layer - 1); 102} 103 104void 105idr_remove_all(struct idr *idr) 106{ 107 108 mtx_lock(&idr->lock); 109 idr_remove_layer(idr->top, idr->layers - 1); 110 idr->top = NULL; 111 idr->layers = 0; 112 mtx_unlock(&idr->lock); 113} 114 115void 116idr_remove(struct idr *idr, int id) 117{ 118 struct idr_layer *il; 119 int layer; 120 int idx; 121 122 id &= MAX_ID_MASK; 123 mtx_lock(&idr->lock); 124 il = idr->top; 125 layer = idr->layers - 1; 126 if (il == NULL || id > idr_max(idr)) { 127 mtx_unlock(&idr->lock); 128 return; 129 } 130 /* 131 * Walk down the tree to this item setting bitmaps along the way 132 * as we know at least one item will be free along this path. 133 */ 134 while (layer && il) { 135 idx = idr_pos(id, layer); 136 il->bitmap |= 1 << idx; 137 il = il->ary[idx]; 138 layer--; 139 } 140 idx = id & IDR_MASK; 141 /* 142 * At this point we've set free space bitmaps up the whole tree. 143 * We could make this non-fatal and unwind but linux dumps a stack 144 * and a warning so I don't think it's necessary. 145 */ 146 if (il == NULL || (il->bitmap & (1 << idx)) != 0) 147 panic("idr_remove: Item %d not allocated (%p, %p)\n", 148 id, idr, il); 149 il->ary[idx] = NULL; 150 il->bitmap |= 1 << idx; 151 mtx_unlock(&idr->lock); 152 return; 153} 154 155void * 156idr_replace(struct idr *idr, void *ptr, int id) 157{ 158 struct idr_layer *il; 159 void *res; 160 int layer; 161 int idx; 162 163 res = ERR_PTR(-EINVAL); 164 id &= MAX_ID_MASK; 165 mtx_lock(&idr->lock); 166 il = idr->top; 167 layer = idr->layers - 1; 168 if (il == NULL || id > idr_max(idr)) 169 goto out; 170 while (layer && il) { 171 il = il->ary[idr_pos(id, layer)]; 172 layer--; 173 } 174 idx = id & IDR_MASK; 175 /* 176 * Replace still returns an error if the item was not allocated. 177 */ 178 if (il != NULL && (il->bitmap & (1 << idx)) != 0) { 179 res = il->ary[idx]; 180 il->ary[idx] = ptr; 181 } 182out: 183 mtx_unlock(&idr->lock); 184 return (res); 185} 186 187void * 188idr_find(struct idr *idr, int id) 189{ 190 struct idr_layer *il; 191 void *res; 192 int layer; 193 194 res = NULL; 195 id &= MAX_ID_MASK; 196 mtx_lock(&idr->lock); 197 il = idr->top; 198 layer = idr->layers - 1; 199 if (il == NULL || id > idr_max(idr)) 200 goto out; 201 while (layer && il) { 202 il = il->ary[idr_pos(id, layer)]; 203 layer--; 204 } 205 if (il != NULL) 206 res = il->ary[id & IDR_MASK]; 207out: 208 mtx_unlock(&idr->lock); 209 return (res); 210} 211 212int 213idr_pre_get(struct idr *idr, gfp_t gfp_mask) 214{ 215 struct idr_layer *il, *iln; 216 struct idr_layer *head; 217 int need; 218 219 mtx_lock(&idr->lock); 220 for (;;) { 221 need = idr->layers + 1; 222 for (il = idr->free; il != NULL; il = il->ary[0]) 223 need--; 224 mtx_unlock(&idr->lock); 225 if (need == 0) 226 break; 227 for (head = NULL; need; need--) { 228 iln = malloc(sizeof(*il), M_IDR, M_ZERO | gfp_mask); 229 if (iln == NULL) 230 break; 231 bitmap_fill(&iln->bitmap, IDR_SIZE); 232 if (head != NULL) { 233 il->ary[0] = iln; 234 il = iln; 235 } else 236 head = il = iln; 237 } 238 if (head == NULL) 239 return (0); 240 mtx_lock(&idr->lock); 241 il->ary[0] = idr->free; 242 idr->free = head; 243 } 244 return (1); 245} 246 247static inline struct idr_layer * 248idr_get(struct idr *idr) 249{ 250 struct idr_layer *il; 251 252 il = idr->free; 253 if (il) { 254 idr->free = il->ary[0]; 255 il->ary[0] = NULL; 256 return (il); 257 } 258 il = malloc(sizeof(*il), M_IDR, M_ZERO | M_NOWAIT); 259 bitmap_fill(&il->bitmap, IDR_SIZE); 260 return (il); 261} 262 263/* 264 * Could be implemented as get_new_above(idr, ptr, 0, idp) but written 265 * first for simplicity sake. 266 */ 267int 268idr_get_new(struct idr *idr, void *ptr, int *idp) 269{ 270 struct idr_layer *stack[MAX_LEVEL]; 271 struct idr_layer *il; 272 int error; 273 int layer; 274 int idx; 275 int id; 276 277 error = -EAGAIN; 278 mtx_lock(&idr->lock); 279 /* 280 * Expand the tree until there is free space. 281 */ 282 if (idr->top == NULL || idr->top->bitmap == 0) { 283 if (idr->layers == MAX_LEVEL + 1) { 284 error = -ENOSPC; 285 goto out; 286 } 287 il = idr_get(idr); 288 if (il == NULL) 289 goto out; 290 il->ary[0] = idr->top; 291 if (idr->top) 292 il->bitmap &= ~1; 293 idr->top = il; 294 idr->layers++; 295 } 296 il = idr->top; 297 id = 0; 298 /* 299 * Walk the tree following free bitmaps, record our path. 300 */ 301 for (layer = idr->layers - 1;; layer--) { 302 stack[layer] = il; 303 idx = ffsl(il->bitmap); 304 if (idx == 0) 305 panic("idr_get_new: Invalid leaf state (%p, %p)\n", 306 idr, il); 307 idx--; 308 id |= idx << (layer * IDR_BITS); 309 if (layer == 0) 310 break; 311 if (il->ary[idx] == NULL) { 312 il->ary[idx] = idr_get(idr); 313 if (il->ary[idx] == NULL) 314 goto out; 315 } 316 il = il->ary[idx]; 317 } 318 /* 319 * Allocate the leaf to the consumer. 320 */ 321 il->bitmap &= ~(1 << idx); 322 il->ary[idx] = ptr; 323 *idp = id; 324 /* 325 * Clear bitmaps potentially up to the root. 326 */ 327 while (il->bitmap == 0 && ++layer < idr->layers) { 328 il = stack[layer]; 329 il->bitmap &= ~(1 << idr_pos(id, layer)); 330 } 331 error = 0; 332out: 333 mtx_unlock(&idr->lock); 334#ifdef INVARIANTS 335 if (error == 0 && idr_find(idr, id) != ptr) { 336 panic("idr_get_new: Failed for idr %p, id %d, ptr %p\n", 337 idr, id, ptr); 338 } 339#endif 340 return (error); 341} 342 343int 344idr_get_new_above(struct idr *idr, void *ptr, int starting_id, int *idp) 345{ 346 struct idr_layer *stack[MAX_LEVEL]; 347 struct idr_layer *il; 348 int error; 349 int layer; 350 int idx, sidx; 351 int id; 352 353 error = -EAGAIN; 354 mtx_lock(&idr->lock); 355 /* 356 * Compute the layers required to support starting_id and the mask 357 * at the top layer. 358 */ 359restart: 360 idx = starting_id; 361 layer = 0; 362 while (idx & ~IDR_MASK) { 363 layer++; 364 idx >>= IDR_BITS; 365 } 366 if (layer == MAX_LEVEL + 1) { 367 error = -ENOSPC; 368 goto out; 369 } 370 /* 371 * Expand the tree until there is free space at or beyond starting_id. 372 */ 373 while (idr->layers <= layer || 374 idr->top->bitmap < (1 << idr_pos(starting_id, idr->layers - 1))) { 375 if (idr->layers == MAX_LEVEL + 1) { 376 error = -ENOSPC; 377 goto out; 378 } 379 il = idr_get(idr); 380 if (il == NULL) 381 goto out; 382 il->ary[0] = idr->top; 383 if (idr->top && idr->top->bitmap == 0) 384 il->bitmap &= ~1; 385 idr->top = il; 386 idr->layers++; 387 } 388 il = idr->top; 389 id = 0; 390 /* 391 * Walk the tree following free bitmaps, record our path. 392 */ 393 for (layer = idr->layers - 1;; layer--) { 394 stack[layer] = il; 395 sidx = idr_pos(starting_id, layer); 396 /* Returns index numbered from 0 or size if none exists. */ 397 idx = find_next_bit(&il->bitmap, IDR_SIZE, sidx); 398 if (idx == IDR_SIZE && sidx == 0) 399 panic("idr_get_new: Invalid leaf state (%p, %p)\n", 400 idr, il); 401 /* 402 * We may have walked a path where there was a free bit but 403 * it was lower than what we wanted. Restart the search with 404 * a larger starting id. id contains the progress we made so 405 * far. Search the leaf one above this level. This may 406 * restart as many as MAX_LEVEL times but that is expected 407 * to be rare. 408 */ 409 if (idx == IDR_SIZE) { 410 starting_id = id + (1 << (layer+1 * IDR_BITS)); 411 goto restart; 412 } 413 if (idx > sidx) 414 starting_id = 0; /* Search the whole subtree. */ 415 id |= idx << (layer * IDR_BITS); 416 if (layer == 0) 417 break; 418 if (il->ary[idx] == NULL) { 419 il->ary[idx] = idr_get(idr); 420 if (il->ary[idx] == NULL) 421 goto out; 422 } 423 il = il->ary[idx]; 424 } 425 /* 426 * Allocate the leaf to the consumer. 427 */ 428 il->bitmap &= ~(1 << idx); 429 il->ary[idx] = ptr; 430 *idp = id; 431 /* 432 * Clear bitmaps potentially up to the root. 433 */ 434 while (il->bitmap == 0 && ++layer < idr->layers) { 435 il = stack[layer]; 436 il->bitmap &= ~(1 << idr_pos(id, layer)); 437 } 438 error = 0; 439out: 440 mtx_unlock(&idr->lock); 441#ifdef INVARIANTS 442 if (error == 0 && idr_find(idr, id) != ptr) { 443 panic("idr_get_new_above: Failed for idr %p, id %d, ptr %p\n", 444 idr, id, ptr); 445 } 446#endif 447 return (error); 448} 449