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