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 80219820Sjeff mtx_lock(&idr->lock); 81219820Sjeff for (il = idr->free; il != NULL; il = iln) { 82219820Sjeff iln = il->ary[0]; 83219820Sjeff free(il, M_IDR); 84219820Sjeff } 85219820Sjeff mtx_unlock(&idr->lock); 86219820Sjeff} 87219820Sjeff 88219820Sjeffstatic void 89219820Sjeffidr_remove_layer(struct idr_layer *il, int layer) 90219820Sjeff{ 91219820Sjeff int i; 92219820Sjeff 93219820Sjeff if (il == NULL) 94219820Sjeff return; 95219820Sjeff if (layer == 0) { 96219820Sjeff free(il, M_IDR); 97219820Sjeff return; 98219820Sjeff } 99219820Sjeff for (i = 0; i < IDR_SIZE; i++) 100219820Sjeff if (il->ary[i]) 101219820Sjeff idr_remove_layer(il->ary[i], layer - 1); 102219820Sjeff} 103219820Sjeff 104219820Sjeffvoid 105219820Sjeffidr_remove_all(struct idr *idr) 106219820Sjeff{ 107219820Sjeff 108219820Sjeff mtx_lock(&idr->lock); 109219820Sjeff idr_remove_layer(idr->top, idr->layers - 1); 110219820Sjeff idr->top = NULL; 111219820Sjeff idr->layers = 0; 112219820Sjeff mtx_unlock(&idr->lock); 113219820Sjeff} 114219820Sjeff 115219820Sjeffvoid 116219820Sjeffidr_remove(struct idr *idr, int id) 117219820Sjeff{ 118219820Sjeff struct idr_layer *il; 119219820Sjeff int layer; 120219820Sjeff int idx; 121219820Sjeff 122219820Sjeff id &= MAX_ID_MASK; 123219820Sjeff mtx_lock(&idr->lock); 124219820Sjeff il = idr->top; 125219820Sjeff layer = idr->layers - 1; 126219820Sjeff if (il == NULL || id > idr_max(idr)) { 127219820Sjeff mtx_unlock(&idr->lock); 128219820Sjeff return; 129219820Sjeff } 130219820Sjeff /* 131219820Sjeff * Walk down the tree to this item setting bitmaps along the way 132219820Sjeff * as we know at least one item will be free along this path. 133219820Sjeff */ 134219820Sjeff while (layer && il) { 135219820Sjeff idx = idr_pos(id, layer); 136219820Sjeff il->bitmap |= 1 << idx; 137219820Sjeff il = il->ary[idx]; 138219820Sjeff layer--; 139219820Sjeff } 140219820Sjeff idx = id & IDR_MASK; 141219820Sjeff /* 142219820Sjeff * At this point we've set free space bitmaps up the whole tree. 143219820Sjeff * We could make this non-fatal and unwind but linux dumps a stack 144219820Sjeff * and a warning so I don't think it's necessary. 145219820Sjeff */ 146219820Sjeff if (il == NULL || (il->bitmap & (1 << idx)) != 0) 147219820Sjeff panic("idr_remove: Item %d not allocated (%p, %p)\n", 148219820Sjeff id, idr, il); 149219820Sjeff il->ary[idx] = NULL; 150219820Sjeff il->bitmap |= 1 << idx; 151219820Sjeff mtx_unlock(&idr->lock); 152219820Sjeff return; 153219820Sjeff} 154219820Sjeff 155219820Sjeffvoid * 156219820Sjeffidr_replace(struct idr *idr, void *ptr, int id) 157219820Sjeff{ 158219820Sjeff struct idr_layer *il; 159219820Sjeff void *res; 160219820Sjeff int layer; 161219820Sjeff int idx; 162219820Sjeff 163219820Sjeff res = ERR_PTR(-EINVAL); 164219820Sjeff id &= MAX_ID_MASK; 165219820Sjeff mtx_lock(&idr->lock); 166219820Sjeff il = idr->top; 167219820Sjeff layer = idr->layers - 1; 168219820Sjeff if (il == NULL || id > idr_max(idr)) 169219820Sjeff goto out; 170219820Sjeff while (layer && il) { 171219820Sjeff il = il->ary[idr_pos(id, layer)]; 172219820Sjeff layer--; 173219820Sjeff } 174219820Sjeff idx = id & IDR_MASK; 175219820Sjeff /* 176219820Sjeff * Replace still returns an error if the item was not allocated. 177219820Sjeff */ 178219820Sjeff if (il != NULL && (il->bitmap & (1 << idx)) != 0) { 179219820Sjeff res = il->ary[idx]; 180219820Sjeff il->ary[idx] = ptr; 181219820Sjeff } 182219820Sjeffout: 183219820Sjeff mtx_unlock(&idr->lock); 184219820Sjeff return (res); 185219820Sjeff} 186219820Sjeff 187219820Sjeffvoid * 188219820Sjeffidr_find(struct idr *idr, int id) 189219820Sjeff{ 190219820Sjeff struct idr_layer *il; 191219820Sjeff void *res; 192219820Sjeff int layer; 193219820Sjeff 194219820Sjeff res = NULL; 195219820Sjeff id &= MAX_ID_MASK; 196219820Sjeff mtx_lock(&idr->lock); 197219820Sjeff il = idr->top; 198219820Sjeff layer = idr->layers - 1; 199219820Sjeff if (il == NULL || id > idr_max(idr)) 200219820Sjeff goto out; 201219820Sjeff while (layer && il) { 202219820Sjeff il = il->ary[idr_pos(id, layer)]; 203219820Sjeff layer--; 204219820Sjeff } 205219820Sjeff if (il != NULL) 206219820Sjeff res = il->ary[id & IDR_MASK]; 207219820Sjeffout: 208219820Sjeff mtx_unlock(&idr->lock); 209219820Sjeff return (res); 210219820Sjeff} 211219820Sjeff 212219820Sjeffint 213219820Sjeffidr_pre_get(struct idr *idr, gfp_t gfp_mask) 214219820Sjeff{ 215219820Sjeff struct idr_layer *il, *iln; 216219820Sjeff struct idr_layer *head; 217219820Sjeff int need; 218219820Sjeff 219219820Sjeff mtx_lock(&idr->lock); 220219820Sjeff for (;;) { 221219820Sjeff need = idr->layers + 1; 222219820Sjeff for (il = idr->free; il != NULL; il = il->ary[0]) 223219820Sjeff need--; 224219820Sjeff mtx_unlock(&idr->lock); 225219820Sjeff if (need == 0) 226219820Sjeff break; 227219820Sjeff for (head = NULL; need; need--) { 228219820Sjeff iln = malloc(sizeof(*il), M_IDR, M_ZERO | gfp_mask); 229219820Sjeff if (iln == NULL) 230219820Sjeff break; 231219820Sjeff bitmap_fill(&iln->bitmap, IDR_SIZE); 232219820Sjeff if (head != NULL) { 233219820Sjeff il->ary[0] = iln; 234219820Sjeff il = iln; 235219820Sjeff } else 236219820Sjeff head = il = iln; 237219820Sjeff } 238219820Sjeff if (head == NULL) 239219820Sjeff return (0); 240219820Sjeff mtx_lock(&idr->lock); 241219820Sjeff il->ary[0] = idr->free; 242219820Sjeff idr->free = head; 243219820Sjeff } 244219820Sjeff return (1); 245219820Sjeff} 246219820Sjeff 247219820Sjeffstatic inline struct idr_layer * 248219820Sjeffidr_get(struct idr *idr) 249219820Sjeff{ 250219820Sjeff struct idr_layer *il; 251219820Sjeff 252219820Sjeff il = idr->free; 253219820Sjeff if (il) { 254219820Sjeff idr->free = il->ary[0]; 255219820Sjeff il->ary[0] = NULL; 256219820Sjeff return (il); 257219820Sjeff } 258219820Sjeff il = malloc(sizeof(*il), M_IDR, M_ZERO | M_NOWAIT); 259219820Sjeff bitmap_fill(&il->bitmap, IDR_SIZE); 260219820Sjeff return (il); 261219820Sjeff} 262219820Sjeff 263219820Sjeff/* 264219820Sjeff * Could be implemented as get_new_above(idr, ptr, 0, idp) but written 265219820Sjeff * first for simplicity sake. 266219820Sjeff */ 267219820Sjeffint 268219820Sjeffidr_get_new(struct idr *idr, void *ptr, int *idp) 269219820Sjeff{ 270219820Sjeff struct idr_layer *stack[MAX_LEVEL]; 271219820Sjeff struct idr_layer *il; 272219820Sjeff int error; 273219820Sjeff int layer; 274219820Sjeff int idx; 275219820Sjeff int id; 276219820Sjeff 277219820Sjeff error = -EAGAIN; 278219820Sjeff mtx_lock(&idr->lock); 279219820Sjeff /* 280219820Sjeff * Expand the tree until there is free space. 281219820Sjeff */ 282219820Sjeff if (idr->top == NULL || idr->top->bitmap == 0) { 283219820Sjeff if (idr->layers == MAX_LEVEL + 1) { 284219820Sjeff error = -ENOSPC; 285219820Sjeff goto out; 286219820Sjeff } 287219820Sjeff il = idr_get(idr); 288219820Sjeff if (il == NULL) 289219820Sjeff goto out; 290219820Sjeff il->ary[0] = idr->top; 291219820Sjeff if (idr->top) 292219820Sjeff il->bitmap &= ~1; 293219820Sjeff idr->top = il; 294219820Sjeff idr->layers++; 295219820Sjeff } 296219820Sjeff il = idr->top; 297219820Sjeff id = 0; 298219820Sjeff /* 299219820Sjeff * Walk the tree following free bitmaps, record our path. 300219820Sjeff */ 301219820Sjeff for (layer = idr->layers - 1;; layer--) { 302219820Sjeff stack[layer] = il; 303219820Sjeff idx = ffsl(il->bitmap); 304219820Sjeff if (idx == 0) 305219820Sjeff panic("idr_get_new: Invalid leaf state (%p, %p)\n", 306219820Sjeff idr, il); 307219820Sjeff idx--; 308219820Sjeff id |= idx << (layer * IDR_BITS); 309219820Sjeff if (layer == 0) 310219820Sjeff break; 311219820Sjeff if (il->ary[idx] == NULL) { 312219820Sjeff il->ary[idx] = idr_get(idr); 313219820Sjeff if (il->ary[idx] == NULL) 314219820Sjeff goto out; 315219820Sjeff } 316219820Sjeff il = il->ary[idx]; 317219820Sjeff } 318219820Sjeff /* 319219820Sjeff * Allocate the leaf to the consumer. 320219820Sjeff */ 321219820Sjeff il->bitmap &= ~(1 << idx); 322219820Sjeff il->ary[idx] = ptr; 323219820Sjeff *idp = id; 324219820Sjeff /* 325219820Sjeff * Clear bitmaps potentially up to the root. 326219820Sjeff */ 327219820Sjeff while (il->bitmap == 0 && ++layer < idr->layers) { 328219820Sjeff il = stack[layer]; 329219820Sjeff il->bitmap &= ~(1 << idr_pos(id, layer)); 330219820Sjeff } 331219820Sjeff error = 0; 332219820Sjeffout: 333219820Sjeff mtx_unlock(&idr->lock); 334219820Sjeff#ifdef INVARIANTS 335219820Sjeff if (error == 0 && idr_find(idr, id) != ptr) { 336219820Sjeff panic("idr_get_new: Failed for idr %p, id %d, ptr %p\n", 337219820Sjeff idr, id, ptr); 338219820Sjeff } 339219820Sjeff#endif 340219820Sjeff return (error); 341219820Sjeff} 342219820Sjeff 343219820Sjeffint 344219820Sjeffidr_get_new_above(struct idr *idr, void *ptr, int starting_id, int *idp) 345219820Sjeff{ 346219820Sjeff struct idr_layer *stack[MAX_LEVEL]; 347219820Sjeff struct idr_layer *il; 348219820Sjeff int error; 349219820Sjeff int layer; 350219820Sjeff int idx, sidx; 351219820Sjeff int id; 352219820Sjeff 353219820Sjeff error = -EAGAIN; 354219820Sjeff mtx_lock(&idr->lock); 355219820Sjeff /* 356219820Sjeff * Compute the layers required to support starting_id and the mask 357219820Sjeff * at the top layer. 358219820Sjeff */ 359219820Sjeffrestart: 360219820Sjeff idx = starting_id; 361219820Sjeff layer = 0; 362219820Sjeff while (idx & ~IDR_MASK) { 363219820Sjeff layer++; 364219820Sjeff idx >>= IDR_BITS; 365219820Sjeff } 366219820Sjeff if (layer == MAX_LEVEL + 1) { 367219820Sjeff error = -ENOSPC; 368219820Sjeff goto out; 369219820Sjeff } 370219820Sjeff /* 371219820Sjeff * Expand the tree until there is free space at or beyond starting_id. 372219820Sjeff */ 373219820Sjeff while (idr->layers <= layer || 374219820Sjeff idr->top->bitmap < (1 << idr_pos(starting_id, idr->layers - 1))) { 375219820Sjeff if (idr->layers == MAX_LEVEL + 1) { 376219820Sjeff error = -ENOSPC; 377219820Sjeff goto out; 378219820Sjeff } 379219820Sjeff il = idr_get(idr); 380219820Sjeff if (il == NULL) 381219820Sjeff goto out; 382219820Sjeff il->ary[0] = idr->top; 383219820Sjeff if (idr->top && idr->top->bitmap == 0) 384219820Sjeff il->bitmap &= ~1; 385219820Sjeff idr->top = il; 386219820Sjeff idr->layers++; 387219820Sjeff } 388219820Sjeff il = idr->top; 389219820Sjeff id = 0; 390219820Sjeff /* 391219820Sjeff * Walk the tree following free bitmaps, record our path. 392219820Sjeff */ 393219820Sjeff for (layer = idr->layers - 1;; layer--) { 394219820Sjeff stack[layer] = il; 395219820Sjeff sidx = idr_pos(starting_id, layer); 396219820Sjeff /* Returns index numbered from 0 or size if none exists. */ 397219820Sjeff idx = find_next_bit(&il->bitmap, IDR_SIZE, sidx); 398219820Sjeff if (idx == IDR_SIZE && sidx == 0) 399219820Sjeff panic("idr_get_new: Invalid leaf state (%p, %p)\n", 400219820Sjeff idr, il); 401219820Sjeff /* 402219820Sjeff * We may have walked a path where there was a free bit but 403219820Sjeff * it was lower than what we wanted. Restart the search with 404219820Sjeff * a larger starting id. id contains the progress we made so 405219820Sjeff * far. Search the leaf one above this level. This may 406219820Sjeff * restart as many as MAX_LEVEL times but that is expected 407219820Sjeff * to be rare. 408219820Sjeff */ 409219820Sjeff if (idx == IDR_SIZE) { 410219820Sjeff starting_id = id + (1 << (layer+1 * IDR_BITS)); 411219820Sjeff goto restart; 412219820Sjeff } 413219820Sjeff if (idx > sidx) 414219820Sjeff starting_id = 0; /* Search the whole subtree. */ 415219820Sjeff id |= idx << (layer * IDR_BITS); 416219820Sjeff if (layer == 0) 417219820Sjeff break; 418219820Sjeff if (il->ary[idx] == NULL) { 419219820Sjeff il->ary[idx] = idr_get(idr); 420219820Sjeff if (il->ary[idx] == NULL) 421219820Sjeff goto out; 422219820Sjeff } 423219820Sjeff il = il->ary[idx]; 424219820Sjeff } 425219820Sjeff /* 426219820Sjeff * Allocate the leaf to the consumer. 427219820Sjeff */ 428219820Sjeff il->bitmap &= ~(1 << idx); 429219820Sjeff il->ary[idx] = ptr; 430219820Sjeff *idp = id; 431219820Sjeff /* 432219820Sjeff * Clear bitmaps potentially up to the root. 433219820Sjeff */ 434219820Sjeff while (il->bitmap == 0 && ++layer < idr->layers) { 435219820Sjeff il = stack[layer]; 436219820Sjeff il->bitmap &= ~(1 << idr_pos(id, layer)); 437219820Sjeff } 438219820Sjeff error = 0; 439219820Sjeffout: 440219820Sjeff mtx_unlock(&idr->lock); 441219820Sjeff#ifdef INVARIANTS 442219820Sjeff if (error == 0 && idr_find(idr, id) != ptr) { 443219820Sjeff panic("idr_get_new_above: Failed for idr %p, id %d, ptr %p\n", 444219820Sjeff idr, id, ptr); 445219820Sjeff } 446219820Sjeff#endif 447219820Sjeff return (error); 448219820Sjeff} 449