1219820Sjeff/*- 2219820Sjeff * Copyright (c) 2010 Isilon Systems, Inc. 3219820Sjeff * Copyright (c) 2010 iX Systems, Inc. 4219820Sjeff * Copyright (c) 2010 Panasas, Inc. 5271127Shselasky * Copyright (c) 2013, 2014 Mellanox Technologies, Ltd. 6219820Sjeff * All rights reserved. 7219820Sjeff * 8219820Sjeff * Redistribution and use in source and binary forms, with or without 9219820Sjeff * modification, are permitted provided that the following conditions 10219820Sjeff * are met: 11219820Sjeff * 1. Redistributions of source code must retain the above copyright 12219820Sjeff * notice unmodified, this list of conditions, and the following 13219820Sjeff * disclaimer. 14219820Sjeff * 2. Redistributions in binary form must reproduce the above copyright 15219820Sjeff * notice, this list of conditions and the following disclaimer in the 16219820Sjeff * documentation and/or other materials provided with the distribution. 17219820Sjeff * 18219820Sjeff * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 19219820Sjeff * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 20219820Sjeff * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 21219820Sjeff * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 22219820Sjeff * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 23219820Sjeff * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24219820Sjeff * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25219820Sjeff * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26219820Sjeff * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 27219820Sjeff * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28219820Sjeff */ 29219820Sjeff 30219820Sjeff#include <sys/param.h> 31219820Sjeff#include <sys/systm.h> 32219820Sjeff#include <sys/malloc.h> 33219820Sjeff#include <sys/kernel.h> 34219820Sjeff#include <sys/sysctl.h> 35219820Sjeff#include <sys/lock.h> 36219820Sjeff#include <sys/mutex.h> 37219820Sjeff 38219820Sjeff#include <machine/stdarg.h> 39219820Sjeff 40219820Sjeff#include <linux/bitops.h> 41219820Sjeff#include <linux/kobject.h> 42219820Sjeff#include <linux/slab.h> 43219820Sjeff#include <linux/idr.h> 44219820Sjeff#include <linux/err.h> 45219820Sjeff 46219820Sjeff/* 47219820Sjeff * IDR Implementation. 48219820Sjeff * 49219820Sjeff * This is quick and dirty and not as re-entrant as the linux version 50219820Sjeff * however it should be fairly fast. It is basically a radix tree with 51219820Sjeff * a builtin bitmap for allocation. 52219820Sjeff */ 53227293Sedstatic MALLOC_DEFINE(M_IDR, "idr", "Linux IDR compat"); 54219820Sjeff 55219820Sjeffstatic inline int 56219820Sjeffidr_max(struct idr *idr) 57219820Sjeff{ 58219820Sjeff return (1 << (idr->layers * IDR_BITS)) - 1; 59219820Sjeff} 60219820Sjeff 61219820Sjeffstatic inline int 62219820Sjeffidr_pos(int id, int layer) 63219820Sjeff{ 64219820Sjeff return (id >> (IDR_BITS * layer)) & IDR_MASK; 65219820Sjeff} 66219820Sjeff 67219820Sjeffvoid 68219820Sjeffidr_init(struct idr *idr) 69219820Sjeff{ 70219820Sjeff bzero(idr, sizeof(*idr)); 71219820Sjeff mtx_init(&idr->lock, "idr", NULL, MTX_DEF); 72219820Sjeff} 73219820Sjeff 74219820Sjeff/* Only frees cached pages. */ 75219820Sjeffvoid 76219820Sjeffidr_destroy(struct idr *idr) 77219820Sjeff{ 78219820Sjeff struct idr_layer *il, *iln; 79219820Sjeff 80277139Shselasky idr_remove_all(idr); 81219820Sjeff mtx_lock(&idr->lock); 82219820Sjeff for (il = idr->free; il != NULL; il = iln) { 83219820Sjeff iln = il->ary[0]; 84219820Sjeff free(il, M_IDR); 85219820Sjeff } 86219820Sjeff mtx_unlock(&idr->lock); 87219820Sjeff} 88219820Sjeff 89219820Sjeffstatic void 90219820Sjeffidr_remove_layer(struct idr_layer *il, int layer) 91219820Sjeff{ 92219820Sjeff int i; 93219820Sjeff 94219820Sjeff if (il == NULL) 95219820Sjeff return; 96219820Sjeff if (layer == 0) { 97219820Sjeff free(il, M_IDR); 98219820Sjeff return; 99219820Sjeff } 100219820Sjeff for (i = 0; i < IDR_SIZE; i++) 101219820Sjeff if (il->ary[i]) 102219820Sjeff idr_remove_layer(il->ary[i], layer - 1); 103219820Sjeff} 104219820Sjeff 105219820Sjeffvoid 106219820Sjeffidr_remove_all(struct idr *idr) 107219820Sjeff{ 108219820Sjeff 109219820Sjeff mtx_lock(&idr->lock); 110219820Sjeff idr_remove_layer(idr->top, idr->layers - 1); 111219820Sjeff idr->top = NULL; 112219820Sjeff idr->layers = 0; 113219820Sjeff mtx_unlock(&idr->lock); 114219820Sjeff} 115219820Sjeff 116219820Sjeffvoid 117219820Sjeffidr_remove(struct idr *idr, int id) 118219820Sjeff{ 119219820Sjeff struct idr_layer *il; 120219820Sjeff int layer; 121219820Sjeff int idx; 122219820Sjeff 123219820Sjeff id &= MAX_ID_MASK; 124219820Sjeff mtx_lock(&idr->lock); 125219820Sjeff il = idr->top; 126219820Sjeff layer = idr->layers - 1; 127219820Sjeff if (il == NULL || id > idr_max(idr)) { 128219820Sjeff mtx_unlock(&idr->lock); 129219820Sjeff return; 130219820Sjeff } 131219820Sjeff /* 132219820Sjeff * Walk down the tree to this item setting bitmaps along the way 133219820Sjeff * as we know at least one item will be free along this path. 134219820Sjeff */ 135219820Sjeff while (layer && il) { 136219820Sjeff idx = idr_pos(id, layer); 137219820Sjeff il->bitmap |= 1 << idx; 138219820Sjeff il = il->ary[idx]; 139219820Sjeff layer--; 140219820Sjeff } 141219820Sjeff idx = id & IDR_MASK; 142219820Sjeff /* 143219820Sjeff * At this point we've set free space bitmaps up the whole tree. 144219820Sjeff * We could make this non-fatal and unwind but linux dumps a stack 145219820Sjeff * and a warning so I don't think it's necessary. 146219820Sjeff */ 147219820Sjeff if (il == NULL || (il->bitmap & (1 << idx)) != 0) 148219820Sjeff panic("idr_remove: Item %d not allocated (%p, %p)\n", 149219820Sjeff id, idr, il); 150219820Sjeff il->ary[idx] = NULL; 151219820Sjeff il->bitmap |= 1 << idx; 152219820Sjeff mtx_unlock(&idr->lock); 153219820Sjeff return; 154219820Sjeff} 155219820Sjeff 156219820Sjeffvoid * 157219820Sjeffidr_replace(struct idr *idr, void *ptr, int id) 158219820Sjeff{ 159219820Sjeff struct idr_layer *il; 160219820Sjeff void *res; 161219820Sjeff int layer; 162219820Sjeff int idx; 163219820Sjeff 164219820Sjeff res = ERR_PTR(-EINVAL); 165219820Sjeff id &= MAX_ID_MASK; 166219820Sjeff mtx_lock(&idr->lock); 167219820Sjeff il = idr->top; 168219820Sjeff layer = idr->layers - 1; 169219820Sjeff if (il == NULL || id > idr_max(idr)) 170219820Sjeff goto out; 171219820Sjeff while (layer && il) { 172219820Sjeff il = il->ary[idr_pos(id, layer)]; 173219820Sjeff layer--; 174219820Sjeff } 175219820Sjeff idx = id & IDR_MASK; 176219820Sjeff /* 177219820Sjeff * Replace still returns an error if the item was not allocated. 178219820Sjeff */ 179219820Sjeff if (il != NULL && (il->bitmap & (1 << idx)) != 0) { 180219820Sjeff res = il->ary[idx]; 181219820Sjeff il->ary[idx] = ptr; 182219820Sjeff } 183219820Sjeffout: 184219820Sjeff mtx_unlock(&idr->lock); 185219820Sjeff return (res); 186219820Sjeff} 187219820Sjeff 188283675Smarkjstatic inline void * 189283675Smarkjidr_find_locked(struct idr *idr, int id) 190219820Sjeff{ 191219820Sjeff struct idr_layer *il; 192219820Sjeff void *res; 193219820Sjeff int layer; 194219820Sjeff 195283675Smarkj mtx_assert(&idr->lock, MA_OWNED); 196283675Smarkj 197283675Smarkj id &= MAX_ID_MASK; 198219820Sjeff res = NULL; 199219820Sjeff il = idr->top; 200219820Sjeff layer = idr->layers - 1; 201219820Sjeff if (il == NULL || id > idr_max(idr)) 202283675Smarkj return (NULL); 203219820Sjeff while (layer && il) { 204219820Sjeff il = il->ary[idr_pos(id, layer)]; 205219820Sjeff layer--; 206219820Sjeff } 207219820Sjeff if (il != NULL) 208219820Sjeff res = il->ary[id & IDR_MASK]; 209283675Smarkj return (res); 210283675Smarkj} 211283675Smarkj 212283675Smarkjvoid * 213283675Smarkjidr_find(struct idr *idr, int id) 214283675Smarkj{ 215283675Smarkj void *res; 216283675Smarkj 217283675Smarkj mtx_lock(&idr->lock); 218283675Smarkj res = idr_find_locked(idr, id); 219219820Sjeff mtx_unlock(&idr->lock); 220219820Sjeff return (res); 221219820Sjeff} 222219820Sjeff 223219820Sjeffint 224219820Sjeffidr_pre_get(struct idr *idr, gfp_t gfp_mask) 225219820Sjeff{ 226219820Sjeff struct idr_layer *il, *iln; 227219820Sjeff struct idr_layer *head; 228219820Sjeff int need; 229219820Sjeff 230219820Sjeff mtx_lock(&idr->lock); 231219820Sjeff for (;;) { 232219820Sjeff need = idr->layers + 1; 233219820Sjeff for (il = idr->free; il != NULL; il = il->ary[0]) 234219820Sjeff need--; 235219820Sjeff mtx_unlock(&idr->lock); 236219820Sjeff if (need == 0) 237219820Sjeff break; 238219820Sjeff for (head = NULL; need; need--) { 239219820Sjeff iln = malloc(sizeof(*il), M_IDR, M_ZERO | gfp_mask); 240219820Sjeff if (iln == NULL) 241219820Sjeff break; 242219820Sjeff bitmap_fill(&iln->bitmap, IDR_SIZE); 243219820Sjeff if (head != NULL) { 244219820Sjeff il->ary[0] = iln; 245219820Sjeff il = iln; 246219820Sjeff } else 247219820Sjeff head = il = iln; 248219820Sjeff } 249219820Sjeff if (head == NULL) 250219820Sjeff return (0); 251219820Sjeff mtx_lock(&idr->lock); 252219820Sjeff il->ary[0] = idr->free; 253219820Sjeff idr->free = head; 254219820Sjeff } 255219820Sjeff return (1); 256219820Sjeff} 257219820Sjeff 258219820Sjeffstatic inline struct idr_layer * 259219820Sjeffidr_get(struct idr *idr) 260219820Sjeff{ 261219820Sjeff struct idr_layer *il; 262219820Sjeff 263219820Sjeff il = idr->free; 264219820Sjeff if (il) { 265219820Sjeff idr->free = il->ary[0]; 266219820Sjeff il->ary[0] = NULL; 267219820Sjeff return (il); 268219820Sjeff } 269219820Sjeff il = malloc(sizeof(*il), M_IDR, M_ZERO | M_NOWAIT); 270302926Smarkj if (il != NULL) 271302926Smarkj bitmap_fill(&il->bitmap, IDR_SIZE); 272219820Sjeff return (il); 273219820Sjeff} 274219820Sjeff 275219820Sjeff/* 276219820Sjeff * Could be implemented as get_new_above(idr, ptr, 0, idp) but written 277219820Sjeff * first for simplicity sake. 278219820Sjeff */ 279219820Sjeffint 280219820Sjeffidr_get_new(struct idr *idr, void *ptr, int *idp) 281219820Sjeff{ 282219820Sjeff struct idr_layer *stack[MAX_LEVEL]; 283219820Sjeff struct idr_layer *il; 284219820Sjeff int error; 285219820Sjeff int layer; 286219820Sjeff int idx; 287219820Sjeff int id; 288219820Sjeff 289219820Sjeff error = -EAGAIN; 290219820Sjeff mtx_lock(&idr->lock); 291219820Sjeff /* 292219820Sjeff * Expand the tree until there is free space. 293219820Sjeff */ 294219820Sjeff if (idr->top == NULL || idr->top->bitmap == 0) { 295219820Sjeff if (idr->layers == MAX_LEVEL + 1) { 296219820Sjeff error = -ENOSPC; 297219820Sjeff goto out; 298219820Sjeff } 299219820Sjeff il = idr_get(idr); 300219820Sjeff if (il == NULL) 301219820Sjeff goto out; 302219820Sjeff il->ary[0] = idr->top; 303219820Sjeff if (idr->top) 304219820Sjeff il->bitmap &= ~1; 305219820Sjeff idr->top = il; 306219820Sjeff idr->layers++; 307219820Sjeff } 308219820Sjeff il = idr->top; 309219820Sjeff id = 0; 310219820Sjeff /* 311219820Sjeff * Walk the tree following free bitmaps, record our path. 312219820Sjeff */ 313219820Sjeff for (layer = idr->layers - 1;; layer--) { 314219820Sjeff stack[layer] = il; 315219820Sjeff idx = ffsl(il->bitmap); 316219820Sjeff if (idx == 0) 317219820Sjeff panic("idr_get_new: Invalid leaf state (%p, %p)\n", 318219820Sjeff idr, il); 319219820Sjeff idx--; 320219820Sjeff id |= idx << (layer * IDR_BITS); 321219820Sjeff if (layer == 0) 322219820Sjeff break; 323219820Sjeff if (il->ary[idx] == NULL) { 324219820Sjeff il->ary[idx] = idr_get(idr); 325219820Sjeff if (il->ary[idx] == NULL) 326219820Sjeff goto out; 327219820Sjeff } 328219820Sjeff il = il->ary[idx]; 329219820Sjeff } 330219820Sjeff /* 331219820Sjeff * Allocate the leaf to the consumer. 332219820Sjeff */ 333219820Sjeff il->bitmap &= ~(1 << idx); 334219820Sjeff il->ary[idx] = ptr; 335219820Sjeff *idp = id; 336219820Sjeff /* 337219820Sjeff * Clear bitmaps potentially up to the root. 338219820Sjeff */ 339219820Sjeff while (il->bitmap == 0 && ++layer < idr->layers) { 340219820Sjeff il = stack[layer]; 341219820Sjeff il->bitmap &= ~(1 << idr_pos(id, layer)); 342219820Sjeff } 343219820Sjeff error = 0; 344219820Sjeffout: 345219820Sjeff#ifdef INVARIANTS 346283675Smarkj if (error == 0 && idr_find_locked(idr, id) != ptr) { 347219820Sjeff panic("idr_get_new: Failed for idr %p, id %d, ptr %p\n", 348219820Sjeff idr, id, ptr); 349219820Sjeff } 350219820Sjeff#endif 351283675Smarkj mtx_unlock(&idr->lock); 352219820Sjeff return (error); 353219820Sjeff} 354219820Sjeff 355219820Sjeffint 356219820Sjeffidr_get_new_above(struct idr *idr, void *ptr, int starting_id, int *idp) 357219820Sjeff{ 358219820Sjeff struct idr_layer *stack[MAX_LEVEL]; 359219820Sjeff struct idr_layer *il; 360219820Sjeff int error; 361219820Sjeff int layer; 362219820Sjeff int idx, sidx; 363219820Sjeff int id; 364219820Sjeff 365219820Sjeff error = -EAGAIN; 366219820Sjeff mtx_lock(&idr->lock); 367219820Sjeff /* 368219820Sjeff * Compute the layers required to support starting_id and the mask 369219820Sjeff * at the top layer. 370219820Sjeff */ 371219820Sjeffrestart: 372219820Sjeff idx = starting_id; 373219820Sjeff layer = 0; 374219820Sjeff while (idx & ~IDR_MASK) { 375219820Sjeff layer++; 376219820Sjeff idx >>= IDR_BITS; 377219820Sjeff } 378219820Sjeff if (layer == MAX_LEVEL + 1) { 379219820Sjeff error = -ENOSPC; 380219820Sjeff goto out; 381219820Sjeff } 382219820Sjeff /* 383219820Sjeff * Expand the tree until there is free space at or beyond starting_id. 384219820Sjeff */ 385219820Sjeff while (idr->layers <= layer || 386219820Sjeff idr->top->bitmap < (1 << idr_pos(starting_id, idr->layers - 1))) { 387219820Sjeff if (idr->layers == MAX_LEVEL + 1) { 388219820Sjeff error = -ENOSPC; 389219820Sjeff goto out; 390219820Sjeff } 391219820Sjeff il = idr_get(idr); 392219820Sjeff if (il == NULL) 393219820Sjeff goto out; 394219820Sjeff il->ary[0] = idr->top; 395219820Sjeff if (idr->top && idr->top->bitmap == 0) 396219820Sjeff il->bitmap &= ~1; 397219820Sjeff idr->top = il; 398219820Sjeff idr->layers++; 399219820Sjeff } 400219820Sjeff il = idr->top; 401219820Sjeff id = 0; 402219820Sjeff /* 403219820Sjeff * Walk the tree following free bitmaps, record our path. 404219820Sjeff */ 405219820Sjeff for (layer = idr->layers - 1;; layer--) { 406219820Sjeff stack[layer] = il; 407219820Sjeff sidx = idr_pos(starting_id, layer); 408219820Sjeff /* Returns index numbered from 0 or size if none exists. */ 409219820Sjeff idx = find_next_bit(&il->bitmap, IDR_SIZE, sidx); 410219820Sjeff if (idx == IDR_SIZE && sidx == 0) 411219820Sjeff panic("idr_get_new: Invalid leaf state (%p, %p)\n", 412219820Sjeff idr, il); 413219820Sjeff /* 414219820Sjeff * We may have walked a path where there was a free bit but 415219820Sjeff * it was lower than what we wanted. Restart the search with 416219820Sjeff * a larger starting id. id contains the progress we made so 417219820Sjeff * far. Search the leaf one above this level. This may 418219820Sjeff * restart as many as MAX_LEVEL times but that is expected 419219820Sjeff * to be rare. 420219820Sjeff */ 421219820Sjeff if (idx == IDR_SIZE) { 422284530Snp starting_id = id + (1 << ((layer + 1) * IDR_BITS)); 423219820Sjeff goto restart; 424219820Sjeff } 425219820Sjeff if (idx > sidx) 426219820Sjeff starting_id = 0; /* Search the whole subtree. */ 427219820Sjeff id |= idx << (layer * IDR_BITS); 428219820Sjeff if (layer == 0) 429219820Sjeff break; 430219820Sjeff if (il->ary[idx] == NULL) { 431219820Sjeff il->ary[idx] = idr_get(idr); 432219820Sjeff if (il->ary[idx] == NULL) 433219820Sjeff goto out; 434219820Sjeff } 435219820Sjeff il = il->ary[idx]; 436219820Sjeff } 437219820Sjeff /* 438219820Sjeff * Allocate the leaf to the consumer. 439219820Sjeff */ 440219820Sjeff il->bitmap &= ~(1 << idx); 441219820Sjeff il->ary[idx] = ptr; 442219820Sjeff *idp = id; 443219820Sjeff /* 444219820Sjeff * Clear bitmaps potentially up to the root. 445219820Sjeff */ 446219820Sjeff while (il->bitmap == 0 && ++layer < idr->layers) { 447219820Sjeff il = stack[layer]; 448219820Sjeff il->bitmap &= ~(1 << idr_pos(id, layer)); 449219820Sjeff } 450219820Sjeff error = 0; 451219820Sjeffout: 452219820Sjeff#ifdef INVARIANTS 453283675Smarkj if (error == 0 && idr_find_locked(idr, id) != ptr) { 454219820Sjeff panic("idr_get_new_above: Failed for idr %p, id %d, ptr %p\n", 455219820Sjeff idr, id, ptr); 456219820Sjeff } 457219820Sjeff#endif 458283675Smarkj mtx_unlock(&idr->lock); 459219820Sjeff return (error); 460219820Sjeff} 461