Linux Audio

Check our new training course

Loading...
v3.1
   1/*
   2 * 2002-10-18  written by Jim Houston jim.houston@ccur.com
   3 *	Copyright (C) 2002 by Concurrent Computer Corporation
   4 *	Distributed under the GNU GPL license version 2.
   5 *
   6 * Modified by George Anzinger to reuse immediately and to use
   7 * find bit instructions.  Also removed _irq on spinlocks.
   8 *
   9 * Modified by Nadia Derbey to make it RCU safe.
  10 *
  11 * Small id to pointer translation service.
  12 *
  13 * It uses a radix tree like structure as a sparse array indexed
  14 * by the id to obtain the pointer.  The bitmap makes allocating
  15 * a new id quick.
  16 *
  17 * You call it to allocate an id (an int) an associate with that id a
  18 * pointer or what ever, we treat it as a (void *).  You can pass this
  19 * id to a user for him to pass back at a later time.  You then pass
  20 * that id to this code and it returns your pointer.
  21
  22 * You can release ids at any time. When all ids are released, most of
  23 * the memory is returned (we keep IDR_FREE_MAX) in a local pool so we
  24 * don't need to go to the memory "store" during an id allocate, just
  25 * so you don't need to be too concerned about locking and conflicts
  26 * with the slab allocator.
  27 */
  28
  29#ifndef TEST                        // to test in user space...
  30#include <linux/slab.h>
  31#include <linux/init.h>
  32#include <linux/module.h>
  33#endif
  34#include <linux/err.h>
  35#include <linux/string.h>
  36#include <linux/idr.h>
 
  37#include <linux/spinlock.h>
 
  38
  39static struct kmem_cache *idr_layer_cache;
  40static DEFINE_SPINLOCK(simple_ida_lock);
  41
  42static struct idr_layer *get_from_free_list(struct idr *idp)
  43{
  44	struct idr_layer *p;
  45	unsigned long flags;
  46
  47	spin_lock_irqsave(&idp->lock, flags);
  48	if ((p = idp->id_free)) {
  49		idp->id_free = p->ary[0];
  50		idp->id_free_cnt--;
  51		p->ary[0] = NULL;
  52	}
  53	spin_unlock_irqrestore(&idp->lock, flags);
  54	return(p);
  55}
  56
  57static void idr_layer_rcu_free(struct rcu_head *head)
  58{
  59	struct idr_layer *layer;
  60
  61	layer = container_of(head, struct idr_layer, rcu_head);
  62	kmem_cache_free(idr_layer_cache, layer);
  63}
  64
  65static inline void free_layer(struct idr_layer *p)
  66{
  67	call_rcu(&p->rcu_head, idr_layer_rcu_free);
  68}
  69
  70/* only called when idp->lock is held */
  71static void __move_to_free_list(struct idr *idp, struct idr_layer *p)
  72{
  73	p->ary[0] = idp->id_free;
  74	idp->id_free = p;
  75	idp->id_free_cnt++;
  76}
  77
  78static void move_to_free_list(struct idr *idp, struct idr_layer *p)
  79{
  80	unsigned long flags;
 
 
  81
  82	/*
  83	 * Depends on the return element being zeroed.
  84	 */
  85	spin_lock_irqsave(&idp->lock, flags);
  86	__move_to_free_list(idp, p);
  87	spin_unlock_irqrestore(&idp->lock, flags);
  88}
  89
  90static void idr_mark_full(struct idr_layer **pa, int id)
  91{
  92	struct idr_layer *p = pa[0];
  93	int l = 0;
  94
  95	__set_bit(id & IDR_MASK, &p->bitmap);
  96	/*
  97	 * If this layer is full mark the bit in the layer above to
  98	 * show that this part of the radix tree is full.  This may
  99	 * complete the layer above and require walking up the radix
 100	 * tree.
 101	 */
 102	while (p->bitmap == IDR_FULL) {
 103		if (!(p = pa[++l]))
 104			break;
 105		id = id >> IDR_BITS;
 106		__set_bit((id & IDR_MASK), &p->bitmap);
 107	}
 108}
 
 109
 110/**
 111 * idr_pre_get - reserve resources for idr allocation
 112 * @idp:	idr handle
 113 * @gfp_mask:	memory allocation flags
 114 *
 115 * This function should be called prior to calling the idr_get_new* functions.
 116 * It preallocates enough memory to satisfy the worst possible allocation. The
 117 * caller should pass in GFP_KERNEL if possible.  This of course requires that
 118 * no spinning locks be held.
 119 *
 120 * If the system is REALLY out of memory this function returns %0,
 121 * otherwise %1.
 122 */
 123int idr_pre_get(struct idr *idp, gfp_t gfp_mask)
 124{
 125	while (idp->id_free_cnt < IDR_FREE_MAX) {
 126		struct idr_layer *new;
 127		new = kmem_cache_zalloc(idr_layer_cache, gfp_mask);
 128		if (new == NULL)
 129			return (0);
 130		move_to_free_list(idp, new);
 131	}
 132	return 1;
 133}
 134EXPORT_SYMBOL(idr_pre_get);
 135
 136static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa)
 137{
 138	int n, m, sh;
 139	struct idr_layer *p, *new;
 140	int l, id, oid;
 141	unsigned long bm;
 142
 143	id = *starting_id;
 144 restart:
 145	p = idp->top;
 146	l = idp->layers;
 147	pa[l--] = NULL;
 148	while (1) {
 149		/*
 150		 * We run around this while until we reach the leaf node...
 151		 */
 152		n = (id >> (IDR_BITS*l)) & IDR_MASK;
 153		bm = ~p->bitmap;
 154		m = find_next_bit(&bm, IDR_SIZE, n);
 155		if (m == IDR_SIZE) {
 156			/* no space available go back to previous layer. */
 157			l++;
 158			oid = id;
 159			id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;
 160
 161			/* if already at the top layer, we need to grow */
 162			if (id >= 1 << (idp->layers * IDR_BITS)) {
 163				*starting_id = id;
 164				return IDR_NEED_TO_GROW;
 165			}
 166			p = pa[l];
 167			BUG_ON(!p);
 168
 169			/* If we need to go up one layer, continue the
 170			 * loop; otherwise, restart from the top.
 171			 */
 172			sh = IDR_BITS * (l + 1);
 173			if (oid >> sh == id >> sh)
 174				continue;
 175			else
 176				goto restart;
 177		}
 178		if (m != n) {
 179			sh = IDR_BITS*l;
 180			id = ((id >> sh) ^ n ^ m) << sh;
 181		}
 182		if ((id >= MAX_ID_BIT) || (id < 0))
 183			return IDR_NOMORE_SPACE;
 184		if (l == 0)
 185			break;
 186		/*
 187		 * Create the layer below if it is missing.
 188		 */
 189		if (!p->ary[m]) {
 190			new = get_from_free_list(idp);
 191			if (!new)
 192				return -1;
 193			new->layer = l-1;
 194			rcu_assign_pointer(p->ary[m], new);
 195			p->count++;
 196		}
 197		pa[l--] = p;
 198		p = p->ary[m];
 199	}
 200
 201	pa[l] = p;
 202	return id;
 203}
 204
 205static int idr_get_empty_slot(struct idr *idp, int starting_id,
 206			      struct idr_layer **pa)
 207{
 208	struct idr_layer *p, *new;
 209	int layers, v, id;
 210	unsigned long flags;
 211
 212	id = starting_id;
 213build_up:
 214	p = idp->top;
 215	layers = idp->layers;
 216	if (unlikely(!p)) {
 217		if (!(p = get_from_free_list(idp)))
 218			return -1;
 219		p->layer = 0;
 220		layers = 1;
 221	}
 222	/*
 223	 * Add a new layer to the top of the tree if the requested
 224	 * id is larger than the currently allocated space.
 225	 */
 226	while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) {
 227		layers++;
 228		if (!p->count) {
 229			/* special case: if the tree is currently empty,
 230			 * then we grow the tree by moving the top node
 231			 * upwards.
 232			 */
 233			p->layer++;
 234			continue;
 235		}
 236		if (!(new = get_from_free_list(idp))) {
 237			/*
 238			 * The allocation failed.  If we built part of
 239			 * the structure tear it down.
 240			 */
 241			spin_lock_irqsave(&idp->lock, flags);
 242			for (new = p; p && p != idp->top; new = p) {
 243				p = p->ary[0];
 244				new->ary[0] = NULL;
 245				new->bitmap = new->count = 0;
 246				__move_to_free_list(idp, new);
 247			}
 248			spin_unlock_irqrestore(&idp->lock, flags);
 249			return -1;
 250		}
 251		new->ary[0] = p;
 252		new->count = 1;
 253		new->layer = layers-1;
 254		if (p->bitmap == IDR_FULL)
 255			__set_bit(0, &new->bitmap);
 256		p = new;
 257	}
 258	rcu_assign_pointer(idp->top, p);
 259	idp->layers = layers;
 260	v = sub_alloc(idp, &id, pa);
 261	if (v == IDR_NEED_TO_GROW)
 262		goto build_up;
 263	return(v);
 264}
 265
 266static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id)
 267{
 268	struct idr_layer *pa[MAX_LEVEL];
 269	int id;
 270
 271	id = idr_get_empty_slot(idp, starting_id, pa);
 272	if (id >= 0) {
 273		/*
 274		 * Successfully found an empty slot.  Install the user
 275		 * pointer and mark the slot full.
 276		 */
 277		rcu_assign_pointer(pa[0]->ary[id & IDR_MASK],
 278				(struct idr_layer *)ptr);
 279		pa[0]->count++;
 280		idr_mark_full(pa, id);
 281	}
 282
 283	return id;
 284}
 
 285
 286/**
 287 * idr_get_new_above - allocate new idr entry above or equal to a start id
 288 * @idp: idr handle
 289 * @ptr: pointer you want associated with the id
 290 * @starting_id: id to start search at
 291 * @id: pointer to the allocated handle
 292 *
 293 * This is the allocate id function.  It should be called with any
 294 * required locks.
 295 *
 296 * If allocation from IDR's private freelist fails, idr_get_new_above() will
 297 * return %-EAGAIN.  The caller should retry the idr_pre_get() call to refill
 298 * IDR's preallocation and then retry the idr_get_new_above() call.
 299 *
 300 * If the idr is full idr_get_new_above() will return %-ENOSPC.
 301 *
 302 * @id returns a value in the range @starting_id ... %0x7fffffff
 303 */
 304int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id)
 305{
 306	int rv;
 307
 308	rv = idr_get_new_above_int(idp, ptr, starting_id);
 309	/*
 310	 * This is a cheap hack until the IDR code can be fixed to
 311	 * return proper error values.
 312	 */
 313	if (rv < 0)
 314		return _idr_rc_to_errno(rv);
 315	*id = rv;
 316	return 0;
 317}
 318EXPORT_SYMBOL(idr_get_new_above);
 319
 320/**
 321 * idr_get_new - allocate new idr entry
 322 * @idp: idr handle
 323 * @ptr: pointer you want associated with the id
 324 * @id: pointer to the allocated handle
 325 *
 326 * If allocation from IDR's private freelist fails, idr_get_new_above() will
 327 * return %-EAGAIN.  The caller should retry the idr_pre_get() call to refill
 328 * IDR's preallocation and then retry the idr_get_new_above() call.
 
 
 329 *
 330 * If the idr is full idr_get_new_above() will return %-ENOSPC.
 
 
 
 331 *
 332 * @id returns a value in the range %0 ... %0x7fffffff
 
 333 */
 334int idr_get_new(struct idr *idp, void *ptr, int *id)
 335{
 336	int rv;
 
 337
 338	rv = idr_get_new_above_int(idp, ptr, 0);
 339	/*
 340	 * This is a cheap hack until the IDR code can be fixed to
 341	 * return proper error values.
 342	 */
 343	if (rv < 0)
 344		return _idr_rc_to_errno(rv);
 345	*id = rv;
 346	return 0;
 347}
 348EXPORT_SYMBOL(idr_get_new);
 349
 350static void idr_remove_warning(int id)
 351{
 352	printk(KERN_WARNING
 353		"idr_remove called for id=%d which is not allocated.\n", id);
 354	dump_stack();
 355}
 356
 357static void sub_remove(struct idr *idp, int shift, int id)
 358{
 359	struct idr_layer *p = idp->top;
 360	struct idr_layer **pa[MAX_LEVEL];
 361	struct idr_layer ***paa = &pa[0];
 362	struct idr_layer *to_free;
 363	int n;
 364
 365	*paa = NULL;
 366	*++paa = &idp->top;
 367
 368	while ((shift > 0) && p) {
 369		n = (id >> shift) & IDR_MASK;
 370		__clear_bit(n, &p->bitmap);
 371		*++paa = &p->ary[n];
 372		p = p->ary[n];
 373		shift -= IDR_BITS;
 374	}
 375	n = id & IDR_MASK;
 376	if (likely(p != NULL && test_bit(n, &p->bitmap))){
 377		__clear_bit(n, &p->bitmap);
 378		rcu_assign_pointer(p->ary[n], NULL);
 379		to_free = NULL;
 380		while(*paa && ! --((**paa)->count)){
 381			if (to_free)
 382				free_layer(to_free);
 383			to_free = **paa;
 384			**paa-- = NULL;
 385		}
 386		if (!*paa)
 387			idp->layers = 0;
 388		if (to_free)
 389			free_layer(to_free);
 390	} else
 391		idr_remove_warning(id);
 392}
 393
 394/**
 395 * idr_remove - remove the given id and free its slot
 396 * @idp: idr handle
 397 * @id: unique key
 398 */
 399void idr_remove(struct idr *idp, int id)
 400{
 401	struct idr_layer *p;
 402	struct idr_layer *to_free;
 403
 404	/* Mask off upper bits we don't use for the search. */
 405	id &= MAX_ID_MASK;
 406
 407	sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);
 408	if (idp->top && idp->top->count == 1 && (idp->layers > 1) &&
 409	    idp->top->ary[0]) {
 410		/*
 411		 * Single child at leftmost slot: we can shrink the tree.
 412		 * This level is not needed anymore since when layers are
 413		 * inserted, they are inserted at the top of the existing
 414		 * tree.
 415		 */
 416		to_free = idp->top;
 417		p = idp->top->ary[0];
 418		rcu_assign_pointer(idp->top, p);
 419		--idp->layers;
 420		to_free->bitmap = to_free->count = 0;
 421		free_layer(to_free);
 422	}
 423	while (idp->id_free_cnt >= IDR_FREE_MAX) {
 424		p = get_from_free_list(idp);
 425		/*
 426		 * Note: we don't call the rcu callback here, since the only
 427		 * layers that fall into the freelist are those that have been
 428		 * preallocated.
 429		 */
 430		kmem_cache_free(idr_layer_cache, p);
 431	}
 432	return;
 433}
 434EXPORT_SYMBOL(idr_remove);
 435
 436/**
 437 * idr_remove_all - remove all ids from the given idr tree
 438 * @idp: idr handle
 
 439 *
 440 * idr_destroy() only frees up unused, cached idp_layers, but this
 441 * function will remove all id mappings and leave all idp_layers
 442 * unused.
 443 *
 444 * A typical clean-up sequence for objects stored in an idr tree will
 445 * use idr_for_each() to free all objects, if necessay, then
 446 * idr_remove_all() to remove all ids, and idr_destroy() to free
 447 * up the cached idr_layers.
 448 */
 449void idr_remove_all(struct idr *idp)
 450{
 451	int n, id, max;
 452	int bt_mask;
 453	struct idr_layer *p;
 454	struct idr_layer *pa[MAX_LEVEL];
 455	struct idr_layer **paa = &pa[0];
 456
 457	n = idp->layers * IDR_BITS;
 458	p = idp->top;
 459	rcu_assign_pointer(idp->top, NULL);
 460	max = 1 << n;
 461
 462	id = 0;
 463	while (id < max) {
 464		while (n > IDR_BITS && p) {
 465			n -= IDR_BITS;
 466			*paa++ = p;
 467			p = p->ary[(id >> n) & IDR_MASK];
 468		}
 469
 470		bt_mask = id;
 471		id += 1 << n;
 472		/* Get the highest bit that the above add changed from 0->1. */
 473		while (n < fls(id ^ bt_mask)) {
 474			if (p)
 475				free_layer(p);
 476			n += IDR_BITS;
 477			p = *--paa;
 478		}
 479	}
 480	idp->layers = 0;
 481}
 482EXPORT_SYMBOL(idr_remove_all);
 483
 484/**
 485 * idr_destroy - release all cached layers within an idr tree
 486 * @idp: idr handle
 487 */
 488void idr_destroy(struct idr *idp)
 489{
 490	while (idp->id_free_cnt) {
 491		struct idr_layer *p = get_from_free_list(idp);
 492		kmem_cache_free(idr_layer_cache, p);
 493	}
 494}
 495EXPORT_SYMBOL(idr_destroy);
 496
 497/**
 498 * idr_find - return pointer for given id
 499 * @idp: idr handle
 500 * @id: lookup key
 501 *
 502 * Return the pointer given the id it has been registered with.  A %NULL
 503 * return indicates that @id is not valid or you passed %NULL in
 504 * idr_get_new().
 505 *
 506 * This function can be called under rcu_read_lock(), given that the leaf
 507 * pointers lifetimes are correctly managed.
 
 
 508 */
 509void *idr_find(struct idr *idp, int id)
 510{
 511	int n;
 512	struct idr_layer *p;
 513
 514	p = rcu_dereference_raw(idp->top);
 515	if (!p)
 516		return NULL;
 517	n = (p->layer+1) * IDR_BITS;
 518
 519	/* Mask off upper bits we don't use for the search. */
 520	id &= MAX_ID_MASK;
 521
 522	if (id >= (1 << n))
 523		return NULL;
 524	BUG_ON(n == 0);
 525
 526	while (n > 0 && p) {
 527		n -= IDR_BITS;
 528		BUG_ON(n != p->layer*IDR_BITS);
 529		p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
 530	}
 531	return((void *)p);
 532}
 533EXPORT_SYMBOL(idr_find);
 534
 535/**
 536 * idr_for_each - iterate through all stored pointers
 537 * @idp: idr handle
 538 * @fn: function to be called for each pointer
 539 * @data: data passed back to callback function
 540 *
 541 * Iterate over the pointers registered with the given idr.  The
 542 * callback function will be called for each pointer currently
 543 * registered, passing the id, the pointer and the data pointer passed
 544 * to this function.  It is not safe to modify the idr tree while in
 545 * the callback, so functions such as idr_get_new and idr_remove are
 546 * not allowed.
 547 *
 548 * We check the return of @fn each time. If it returns anything other
 549 * than %0, we break out and return that value.
 550 *
 551 * The caller must serialize idr_for_each() vs idr_get_new() and idr_remove().
 552 */
 553int idr_for_each(struct idr *idp,
 554		 int (*fn)(int id, void *p, void *data), void *data)
 555{
 556	int n, id, max, error = 0;
 557	struct idr_layer *p;
 558	struct idr_layer *pa[MAX_LEVEL];
 559	struct idr_layer **paa = &pa[0];
 560
 561	n = idp->layers * IDR_BITS;
 562	p = rcu_dereference_raw(idp->top);
 563	max = 1 << n;
 564
 565	id = 0;
 566	while (id < max) {
 567		while (n > 0 && p) {
 568			n -= IDR_BITS;
 569			*paa++ = p;
 570			p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
 571		}
 572
 573		if (p) {
 574			error = fn(id, (void *)p, data);
 575			if (error)
 576				break;
 577		}
 578
 579		id += 1 << n;
 580		while (n < fls(id)) {
 581			n += IDR_BITS;
 582			p = *--paa;
 583		}
 584	}
 585
 586	return error;
 587}
 588EXPORT_SYMBOL(idr_for_each);
 589
 590/**
 591 * idr_get_next - lookup next object of id to given id.
 592 * @idp: idr handle
 593 * @nextidp:  pointer to lookup key
 594 *
 595 * Returns pointer to registered object with id, which is next number to
 596 * given id. After being looked up, *@nextidp will be updated for the next
 597 * iteration.
 598 */
 599
 600void *idr_get_next(struct idr *idp, int *nextidp)
 601{
 602	struct idr_layer *p, *pa[MAX_LEVEL];
 603	struct idr_layer **paa = &pa[0];
 604	int id = *nextidp;
 605	int n, max;
 606
 607	/* find first ent */
 608	n = idp->layers * IDR_BITS;
 609	max = 1 << n;
 610	p = rcu_dereference_raw(idp->top);
 611	if (!p)
 
 
 
 
 
 
 
 
 612		return NULL;
 613
 614	while (id < max) {
 615		while (n > 0 && p) {
 616			n -= IDR_BITS;
 617			*paa++ = p;
 618			p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
 619		}
 620
 621		if (p) {
 622			*nextidp = id;
 623			return p;
 624		}
 
 
 
 
 
 
 
 
 
 
 625
 626		id += 1 << n;
 627		while (n < fls(id)) {
 628			n += IDR_BITS;
 629			p = *--paa;
 630		}
 631	}
 632	return NULL;
 633}
 634EXPORT_SYMBOL(idr_get_next);
 635
 636
 637/**
 638 * idr_replace - replace pointer for given id
 639 * @idp: idr handle
 640 * @ptr: pointer you want associated with the id
 641 * @id: lookup key
 642 *
 643 * Replace the pointer registered with an id and return the old value.
 644 * A %-ENOENT return indicates that @id was not found.
 645 * A %-EINVAL return indicates that @id was not within valid constraints.
 
 646 *
 647 * The caller must serialize with writers.
 
 648 */
 649void *idr_replace(struct idr *idp, void *ptr, int id)
 650{
 651	int n;
 652	struct idr_layer *p, *old_p;
 653
 654	p = idp->top;
 655	if (!p)
 656		return ERR_PTR(-EINVAL);
 657
 658	n = (p->layer+1) * IDR_BITS;
 659
 660	id &= MAX_ID_MASK;
 661
 662	if (id >= (1 << n))
 663		return ERR_PTR(-EINVAL);
 664
 665	n -= IDR_BITS;
 666	while ((n > 0) && p) {
 667		p = p->ary[(id >> n) & IDR_MASK];
 668		n -= IDR_BITS;
 669	}
 670
 671	n = id & IDR_MASK;
 672	if (unlikely(p == NULL || !test_bit(n, &p->bitmap)))
 673		return ERR_PTR(-ENOENT);
 674
 675	old_p = p->ary[n];
 676	rcu_assign_pointer(p->ary[n], ptr);
 677
 678	return old_p;
 679}
 680EXPORT_SYMBOL(idr_replace);
 681
 682void __init idr_init_cache(void)
 683{
 684	idr_layer_cache = kmem_cache_create("idr_layer_cache",
 685				sizeof(struct idr_layer), 0, SLAB_PANIC, NULL);
 686}
 687
 688/**
 689 * idr_init - initialize idr handle
 690 * @idp:	idr handle
 691 *
 692 * This function is use to set up the handle (@idp) that you will pass
 693 * to the rest of the functions.
 694 */
 695void idr_init(struct idr *idp)
 696{
 697	memset(idp, 0, sizeof(struct idr));
 698	spin_lock_init(&idp->lock);
 699}
 700EXPORT_SYMBOL(idr_init);
 701
 702
 703/**
 704 * DOC: IDA description
 705 * IDA - IDR based ID allocator
 706 *
 707 * This is id allocator without id -> pointer translation.  Memory
 708 * usage is much lower than full blown idr because each id only
 709 * occupies a bit.  ida uses a custom leaf node which contains
 710 * IDA_BITMAP_BITS slots.
 
 
 
 
 
 
 
 
 
 
 711 *
 712 * 2007-04-25  written by Tejun Heo <htejun@gmail.com>
 
 713 */
 714
 715static void free_bitmap(struct ida *ida, struct ida_bitmap *bitmap)
 716{
 717	unsigned long flags;
 718
 719	if (!ida->free_bitmap) {
 720		spin_lock_irqsave(&ida->idr.lock, flags);
 721		if (!ida->free_bitmap) {
 722			ida->free_bitmap = bitmap;
 723			bitmap = NULL;
 724		}
 725		spin_unlock_irqrestore(&ida->idr.lock, flags);
 726	}
 727
 728	kfree(bitmap);
 729}
 730
 731/**
 732 * ida_pre_get - reserve resources for ida allocation
 733 * @ida:	ida handle
 734 * @gfp_mask:	memory allocation flag
 735 *
 736 * This function should be called prior to locking and calling the
 737 * following function.  It preallocates enough memory to satisfy the
 738 * worst possible allocation.
 739 *
 740 * If the system is REALLY out of memory this function returns %0,
 741 * otherwise %1.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 742 */
 743int ida_pre_get(struct ida *ida, gfp_t gfp_mask)
 744{
 745	/* allocate idr_layers */
 746	if (!idr_pre_get(&ida->idr, gfp_mask))
 747		return 0;
 748
 749	/* allocate free_bitmap */
 750	if (!ida->free_bitmap) {
 751		struct ida_bitmap *bitmap;
 752
 753		bitmap = kmalloc(sizeof(struct ida_bitmap), gfp_mask);
 754		if (!bitmap)
 755			return 0;
 756
 757		free_bitmap(ida, bitmap);
 758	}
 759
 760	return 1;
 761}
 762EXPORT_SYMBOL(ida_pre_get);
 763
 764/**
 765 * ida_get_new_above - allocate new ID above or equal to a start id
 766 * @ida:	ida handle
 767 * @starting_id: id to start search at
 768 * @p_id:	pointer to the allocated handle
 769 *
 770 * Allocate new ID above or equal to @ida.  It should be called with
 771 * any required locks.
 772 *
 773 * If memory is required, it will return %-EAGAIN, you should unlock
 774 * and go back to the ida_pre_get() call.  If the ida is full, it will
 775 * return %-ENOSPC.
 776 *
 777 * @p_id returns a value in the range @starting_id ... %0x7fffffff.
 778 */
 779int ida_get_new_above(struct ida *ida, int starting_id, int *p_id)
 
 780{
 781	struct idr_layer *pa[MAX_LEVEL];
 782	struct ida_bitmap *bitmap;
 783	unsigned long flags;
 784	int idr_id = starting_id / IDA_BITMAP_BITS;
 785	int offset = starting_id % IDA_BITMAP_BITS;
 786	int t, id;
 787
 788 restart:
 789	/* get vacant slot */
 790	t = idr_get_empty_slot(&ida->idr, idr_id, pa);
 791	if (t < 0)
 792		return _idr_rc_to_errno(t);
 793
 794	if (t * IDA_BITMAP_BITS >= MAX_ID_BIT)
 795		return -ENOSPC;
 796
 797	if (t != idr_id)
 798		offset = 0;
 799	idr_id = t;
 800
 801	/* if bitmap isn't there, create a new one */
 802	bitmap = (void *)pa[0]->ary[idr_id & IDR_MASK];
 803	if (!bitmap) {
 804		spin_lock_irqsave(&ida->idr.lock, flags);
 805		bitmap = ida->free_bitmap;
 806		ida->free_bitmap = NULL;
 807		spin_unlock_irqrestore(&ida->idr.lock, flags);
 808
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 809		if (!bitmap)
 810			return -EAGAIN;
 811
 812		memset(bitmap, 0, sizeof(struct ida_bitmap));
 813		rcu_assign_pointer(pa[0]->ary[idr_id & IDR_MASK],
 814				(void *)bitmap);
 815		pa[0]->count++;
 816	}
 817
 818	/* lookup for empty slot */
 819	t = find_next_zero_bit(bitmap->bitmap, IDA_BITMAP_BITS, offset);
 820	if (t == IDA_BITMAP_BITS) {
 821		/* no empty slot after offset, continue to the next chunk */
 822		idr_id++;
 823		offset = 0;
 824		goto restart;
 825	}
 826
 827	id = idr_id * IDA_BITMAP_BITS + t;
 828	if (id >= MAX_ID_BIT)
 829		return -ENOSPC;
 830
 831	__set_bit(t, bitmap->bitmap);
 832	if (++bitmap->nr_busy == IDA_BITMAP_BITS)
 833		idr_mark_full(pa, idr_id);
 834
 835	*p_id = id;
 836
 837	/* Each leaf node can handle nearly a thousand slots and the
 838	 * whole idea of ida is to have small memory foot print.
 839	 * Throw away extra resources one by one after each successful
 840	 * allocation.
 841	 */
 842	if (ida->idr.id_free_cnt || ida->free_bitmap) {
 843		struct idr_layer *p = get_from_free_list(&ida->idr);
 844		if (p)
 845			kmem_cache_free(idr_layer_cache, p);
 846	}
 847
 848	return 0;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 849}
 850EXPORT_SYMBOL(ida_get_new_above);
 851
 852/**
 853 * ida_get_new - allocate new ID
 854 * @ida:	idr handle
 855 * @p_id:	pointer to the allocated handle
 856 *
 857 * Allocate new ID.  It should be called with any required locks.
 858 *
 859 * If memory is required, it will return %-EAGAIN, you should unlock
 860 * and go back to the idr_pre_get() call.  If the idr is full, it will
 861 * return %-ENOSPC.
 862 *
 863 * @id returns a value in the range %0 ... %0x7fffffff.
 864 */
 865int ida_get_new(struct ida *ida, int *p_id)
 866{
 867	return ida_get_new_above(ida, 0, p_id);
 868}
 869EXPORT_SYMBOL(ida_get_new);
 870
 871/**
 872 * ida_remove - remove the given ID
 873 * @ida:	ida handle
 874 * @id:		ID to free
 875 */
 876void ida_remove(struct ida *ida, int id)
 877{
 878	struct idr_layer *p = ida->idr.top;
 879	int shift = (ida->idr.layers - 1) * IDR_BITS;
 880	int idr_id = id / IDA_BITMAP_BITS;
 881	int offset = id % IDA_BITMAP_BITS;
 882	int n;
 883	struct ida_bitmap *bitmap;
 
 884
 885	/* clear full bits while looking up the leaf idr_layer */
 886	while ((shift > 0) && p) {
 887		n = (idr_id >> shift) & IDR_MASK;
 888		__clear_bit(n, &p->bitmap);
 889		p = p->ary[n];
 890		shift -= IDR_BITS;
 891	}
 892
 893	if (p == NULL)
 894		goto err;
 895
 896	n = idr_id & IDR_MASK;
 897	__clear_bit(n, &p->bitmap);
 898
 899	bitmap = (void *)p->ary[n];
 900	if (!test_bit(offset, bitmap->bitmap))
 901		goto err;
 902
 903	/* update bitmap and remove it if empty */
 904	__clear_bit(offset, bitmap->bitmap);
 905	if (--bitmap->nr_busy == 0) {
 906		__set_bit(n, &p->bitmap);	/* to please idr_remove() */
 907		idr_remove(&ida->idr, idr_id);
 908		free_bitmap(ida, bitmap);
 
 
 
 
 
 
 
 
 
 
 909	}
 910
 911	return;
 912
 913 err:
 914	printk(KERN_WARNING
 915	       "ida_remove called for id=%d which is not allocated.\n", id);
 916}
 917EXPORT_SYMBOL(ida_remove);
 918
 919/**
 920 * ida_destroy - release all cached layers within an ida tree
 921 * @ida:		ida handle
 
 
 
 
 
 
 
 
 922 */
 923void ida_destroy(struct ida *ida)
 924{
 925	idr_destroy(&ida->idr);
 926	kfree(ida->free_bitmap);
 927}
 928EXPORT_SYMBOL(ida_destroy);
 929
 930/**
 931 * ida_simple_get - get a new id.
 932 * @ida: the (initialized) ida.
 933 * @start: the minimum id (inclusive, < 0x8000000)
 934 * @end: the maximum id (exclusive, < 0x8000000 or 0)
 935 * @gfp_mask: memory allocation flags
 936 *
 937 * Allocates an id in the range start <= id < end, or returns -ENOSPC.
 938 * On memory allocation failure, returns -ENOMEM.
 939 *
 940 * Use ida_simple_remove() to get rid of an id.
 941 */
 942int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
 943		   gfp_t gfp_mask)
 944{
 945	int ret, id;
 946	unsigned int max;
 947
 948	BUG_ON((int)start < 0);
 949	BUG_ON((int)end < 0);
 950
 951	if (end == 0)
 952		max = 0x80000000;
 953	else {
 954		BUG_ON(end < start);
 955		max = end - 1;
 956	}
 957
 958again:
 959	if (!ida_pre_get(ida, gfp_mask))
 960		return -ENOMEM;
 961
 962	spin_lock(&simple_ida_lock);
 963	ret = ida_get_new_above(ida, start, &id);
 964	if (!ret) {
 965		if (id > max) {
 966			ida_remove(ida, id);
 967			ret = -ENOSPC;
 968		} else {
 969			ret = id;
 970		}
 971	}
 972	spin_unlock(&simple_ida_lock);
 973
 974	if (unlikely(ret == -EAGAIN))
 975		goto again;
 976
 977	return ret;
 978}
 979EXPORT_SYMBOL(ida_simple_get);
 980
 981/**
 982 * ida_simple_remove - remove an allocated id.
 983 * @ida: the (initialized) ida.
 984 * @id: the id returned by ida_simple_get.
 985 */
 986void ida_simple_remove(struct ida *ida, unsigned int id)
 987{
 988	BUG_ON((int)id < 0);
 989	spin_lock(&simple_ida_lock);
 990	ida_remove(ida, id);
 991	spin_unlock(&simple_ida_lock);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 992}
 993EXPORT_SYMBOL(ida_simple_remove);
 994
 995/**
 996 * ida_init - initialize ida handle
 997 * @ida:	ida handle
 998 *
 999 * This function is use to set up the handle (@ida) that you will pass
1000 * to the rest of the functions.
1001 */
1002void ida_init(struct ida *ida)
1003{
1004	memset(ida, 0, sizeof(struct ida));
1005	idr_init(&ida->idr);
1006
 
 
 
 
 
 
1007}
1008EXPORT_SYMBOL(ida_init);
v6.8
  1// SPDX-License-Identifier: GPL-2.0-only
  2#include <linux/bitmap.h>
  3#include <linux/bug.h>
  4#include <linux/export.h>
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  5#include <linux/idr.h>
  6#include <linux/slab.h>
  7#include <linux/spinlock.h>
  8#include <linux/xarray.h>
  9
 10/**
 11 * idr_alloc_u32() - Allocate an ID.
 12 * @idr: IDR handle.
 13 * @ptr: Pointer to be associated with the new ID.
 14 * @nextid: Pointer to an ID.
 15 * @max: The maximum ID to allocate (inclusive).
 16 * @gfp: Memory allocation flags.
 17 *
 18 * Allocates an unused ID in the range specified by @nextid and @max.
 19 * Note that @max is inclusive whereas the @end parameter to idr_alloc()
 20 * is exclusive.  The new ID is assigned to @nextid before the pointer
 21 * is inserted into the IDR, so if @nextid points into the object pointed
 22 * to by @ptr, a concurrent lookup will not find an uninitialised ID.
 23 *
 24 * The caller should provide their own locking to ensure that two
 25 * concurrent modifications to the IDR are not possible.  Read-only
 26 * accesses to the IDR may be done under the RCU read lock or may
 27 * exclude simultaneous writers.
 28 *
 29 * Return: 0 if an ID was allocated, -ENOMEM if memory allocation failed,
 30 * or -ENOSPC if no free IDs could be found.  If an error occurred,
 31 * @nextid is unchanged.
 32 */
 33int idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid,
 34			unsigned long max, gfp_t gfp)
 35{
 36	struct radix_tree_iter iter;
 37	void __rcu **slot;
 38	unsigned int base = idr->idr_base;
 39	unsigned int id = *nextid;
 40
 41	if (WARN_ON_ONCE(!(idr->idr_rt.xa_flags & ROOT_IS_IDR)))
 42		idr->idr_rt.xa_flags |= IDR_RT_MARKER;
 43
 44	id = (id < base) ? 0 : id - base;
 45	radix_tree_iter_init(&iter, id);
 46	slot = idr_get_free(&idr->idr_rt, &iter, gfp, max - base);
 47	if (IS_ERR(slot))
 48		return PTR_ERR(slot);
 49
 50	*nextid = iter.index + base;
 51	/* there is a memory barrier inside radix_tree_iter_replace() */
 52	radix_tree_iter_replace(&idr->idr_rt, &iter, slot, ptr);
 53	radix_tree_iter_tag_clear(&idr->idr_rt, &iter, IDR_FREE);
 54
 55	return 0;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 56}
 57EXPORT_SYMBOL_GPL(idr_alloc_u32);
 58
 59/**
 60 * idr_alloc() - Allocate an ID.
 61 * @idr: IDR handle.
 62 * @ptr: Pointer to be associated with the new ID.
 63 * @start: The minimum ID (inclusive).
 64 * @end: The maximum ID (exclusive).
 65 * @gfp: Memory allocation flags.
 66 *
 67 * Allocates an unused ID in the range specified by @start and @end.  If
 68 * @end is <= 0, it is treated as one larger than %INT_MAX.  This allows
 69 * callers to use @start + N as @end as long as N is within integer range.
 70 *
 71 * The caller should provide their own locking to ensure that two
 72 * concurrent modifications to the IDR are not possible.  Read-only
 73 * accesses to the IDR may be done under the RCU read lock or may
 74 * exclude simultaneous writers.
 75 *
 76 * Return: The newly allocated ID, -ENOMEM if memory allocation failed,
 77 * or -ENOSPC if no free IDs could be found.
 78 */
 79int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp)
 
 
 
 
 
 
 80{
 81	u32 id = start;
 82	int ret;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 83
 84	if (WARN_ON_ONCE(start < 0))
 85		return -EINVAL;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 86
 87	ret = idr_alloc_u32(idr, ptr, &id, end > 0 ? end - 1 : INT_MAX, gfp);
 88	if (ret)
 89		return ret;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 90
 91	return id;
 92}
 93EXPORT_SYMBOL_GPL(idr_alloc);
 94
 95/**
 96 * idr_alloc_cyclic() - Allocate an ID cyclically.
 97 * @idr: IDR handle.
 98 * @ptr: Pointer to be associated with the new ID.
 99 * @start: The minimum ID (inclusive).
100 * @end: The maximum ID (exclusive).
101 * @gfp: Memory allocation flags.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
102 *
103 * Allocates an unused ID in the range specified by @start and @end.  If
104 * @end is <= 0, it is treated as one larger than %INT_MAX.  This allows
105 * callers to use @start + N as @end as long as N is within integer range.
106 * The search for an unused ID will start at the last ID allocated and will
107 * wrap around to @start if no free IDs are found before reaching @end.
108 *
109 * The caller should provide their own locking to ensure that two
110 * concurrent modifications to the IDR are not possible.  Read-only
111 * accesses to the IDR may be done under the RCU read lock or may
112 * exclude simultaneous writers.
113 *
114 * Return: The newly allocated ID, -ENOMEM if memory allocation failed,
115 * or -ENOSPC if no free IDs could be found.
116 */
117int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp)
118{
119	u32 id = idr->idr_next;
120	int err, max = end > 0 ? end - 1 : INT_MAX;
121
122	if ((int)id < start)
123		id = start;
 
 
 
 
 
 
 
 
 
124
125	err = idr_alloc_u32(idr, ptr, &id, max, gfp);
126	if ((err == -ENOSPC) && (id > start)) {
127		id = start;
128		err = idr_alloc_u32(idr, ptr, &id, max, gfp);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
129	}
130	if (err)
131		return err;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
132
133	idr->idr_next = id + 1;
134	return id;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
135}
136EXPORT_SYMBOL(idr_alloc_cyclic);
137
138/**
139 * idr_remove() - Remove an ID from the IDR.
140 * @idr: IDR handle.
141 * @id: Pointer ID.
142 *
143 * Removes this ID from the IDR.  If the ID was not previously in the IDR,
144 * this function returns %NULL.
145 *
146 * Since this function modifies the IDR, the caller should provide their
147 * own locking to ensure that concurrent modification of the same IDR is
148 * not possible.
149 *
150 * Return: The pointer formerly associated with this ID.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
151 */
152void *idr_remove(struct idr *idr, unsigned long id)
153{
154	return radix_tree_delete_item(&idr->idr_rt, id - idr->idr_base, NULL);
 
 
 
155}
156EXPORT_SYMBOL_GPL(idr_remove);
157
158/**
159 * idr_find() - Return pointer for given ID.
160 * @idr: IDR handle.
161 * @id: Pointer ID.
162 *
163 * Looks up the pointer associated with this ID.  A %NULL pointer may
164 * indicate that @id is not allocated or that the %NULL pointer was
165 * associated with this ID.
166 *
167 * This function can be called under rcu_read_lock(), given that the leaf
168 * pointers lifetimes are correctly managed.
169 *
170 * Return: The pointer associated with this ID.
171 */
172void *idr_find(const struct idr *idr, unsigned long id)
173{
174	return radix_tree_lookup(&idr->idr_rt, id - idr->idr_base);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
175}
176EXPORT_SYMBOL_GPL(idr_find);
177
178/**
179 * idr_for_each() - Iterate through all stored pointers.
180 * @idr: IDR handle.
181 * @fn: Function to be called for each pointer.
182 * @data: Data passed to callback function.
183 *
184 * The callback function will be called for each entry in @idr, passing
185 * the ID, the entry and @data.
186 *
187 * If @fn returns anything other than %0, the iteration stops and that
188 * value is returned from this function.
189 *
190 * idr_for_each() can be called concurrently with idr_alloc() and
191 * idr_remove() if protected by RCU.  Newly added entries may not be
192 * seen and deleted entries may be seen, but adding and removing entries
193 * will not cause other entries to be skipped, nor spurious ones to be seen.
194 */
195int idr_for_each(const struct idr *idr,
196		int (*fn)(int id, void *p, void *data), void *data)
197{
198	struct radix_tree_iter iter;
199	void __rcu **slot;
200	int base = idr->idr_base;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
201
202	radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, 0) {
203		int ret;
204		unsigned long id = iter.index + base;
 
 
205
206		if (WARN_ON_ONCE(id > INT_MAX))
207			break;
208		ret = fn(id, rcu_dereference_raw(*slot), data);
209		if (ret)
210			return ret;
211	}
212
213	return 0;
214}
215EXPORT_SYMBOL(idr_for_each);
216
217/**
218 * idr_get_next_ul() - Find next populated entry.
219 * @idr: IDR handle.
220 * @nextid: Pointer to an ID.
221 *
222 * Returns the next populated entry in the tree with an ID greater than
223 * or equal to the value pointed to by @nextid.  On exit, @nextid is updated
224 * to the ID of the found value.  To use in a loop, the value pointed to by
225 * nextid must be incremented by the user.
226 */
227void *idr_get_next_ul(struct idr *idr, unsigned long *nextid)
228{
229	struct radix_tree_iter iter;
230	void __rcu **slot;
231	void *entry = NULL;
232	unsigned long base = idr->idr_base;
233	unsigned long id = *nextid;
234
235	id = (id < base) ? 0 : id - base;
236	radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, id) {
237		entry = rcu_dereference_raw(*slot);
238		if (!entry)
239			continue;
240		if (!xa_is_internal(entry))
241			break;
242		if (slot != &idr->idr_rt.xa_head && !xa_is_retry(entry))
243			break;
244		slot = radix_tree_iter_retry(&iter);
245	}
246	if (!slot)
247		return NULL;
248
249	*nextid = iter.index + base;
250	return entry;
251}
252EXPORT_SYMBOL(idr_get_next_ul);
 
 
253
254/**
255 * idr_get_next() - Find next populated entry.
256 * @idr: IDR handle.
257 * @nextid: Pointer to an ID.
258 *
259 * Returns the next populated entry in the tree with an ID greater than
260 * or equal to the value pointed to by @nextid.  On exit, @nextid is updated
261 * to the ID of the found value.  To use in a loop, the value pointed to by
262 * nextid must be incremented by the user.
263 */
264void *idr_get_next(struct idr *idr, int *nextid)
265{
266	unsigned long id = *nextid;
267	void *entry = idr_get_next_ul(idr, &id);
268
269	if (WARN_ON_ONCE(id > INT_MAX))
270		return NULL;
271	*nextid = id;
272	return entry;
 
 
 
273}
274EXPORT_SYMBOL(idr_get_next);
275
 
276/**
277 * idr_replace() - replace pointer for given ID.
278 * @idr: IDR handle.
279 * @ptr: New pointer to associate with the ID.
280 * @id: ID to change.
281 *
282 * Replace the pointer registered with an ID and return the old value.
283 * This function can be called under the RCU read lock concurrently with
284 * idr_alloc() and idr_remove() (as long as the ID being removed is not
285 * the one being replaced!).
286 *
287 * Returns: the old value on success.  %-ENOENT indicates that @id was not
288 * found.  %-EINVAL indicates that @ptr was not valid.
289 */
290void *idr_replace(struct idr *idr, void *ptr, unsigned long id)
291{
292	struct radix_tree_node *node;
293	void __rcu **slot = NULL;
294	void *entry;
 
 
 
 
 
 
 
295
296	id -= idr->idr_base;
 
297
298	entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot);
299	if (!slot || radix_tree_tag_get(&idr->idr_rt, id, IDR_FREE))
 
 
 
 
 
 
300		return ERR_PTR(-ENOENT);
301
302	__radix_tree_replace(&idr->idr_rt, node, slot, ptr);
 
303
304	return entry;
305}
306EXPORT_SYMBOL(idr_replace);
307
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
308/**
309 * DOC: IDA description
 
310 *
311 * The IDA is an ID allocator which does not provide the ability to
312 * associate an ID with a pointer.  As such, it only needs to store one
313 * bit per ID, and so is more space efficient than an IDR.  To use an IDA,
314 * define it using DEFINE_IDA() (or embed a &struct ida in a data structure,
315 * then initialise it using ida_init()).  To allocate a new ID, call
316 * ida_alloc(), ida_alloc_min(), ida_alloc_max() or ida_alloc_range().
317 * To free an ID, call ida_free().
318 *
319 * ida_destroy() can be used to dispose of an IDA without needing to
320 * free the individual IDs in it.  You can use ida_is_empty() to find
321 * out whether the IDA has any IDs currently allocated.
322 *
323 * The IDA handles its own locking.  It is safe to call any of the IDA
324 * functions without synchronisation in your code.
325 *
326 * IDs are currently limited to the range [0-INT_MAX].  If this is an awkward
327 * limitation, it should be quite straightforward to raise the maximum.
328 */
329
330/*
331 * Developer's notes:
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
332 *
333 * The IDA uses the functionality provided by the XArray to store bitmaps in
334 * each entry.  The XA_FREE_MARK is only cleared when all bits in the bitmap
335 * have been set.
336 *
337 * I considered telling the XArray that each slot is an order-10 node
338 * and indexing by bit number, but the XArray can't allow a single multi-index
339 * entry in the head, which would significantly increase memory consumption
340 * for the IDA.  So instead we divide the index by the number of bits in the
341 * leaf bitmap before doing a radix tree lookup.
342 *
343 * As an optimisation, if there are only a few low bits set in any given
344 * leaf, instead of allocating a 128-byte bitmap, we store the bits
345 * as a value entry.  Value entries never have the XA_FREE_MARK cleared
346 * because we can always convert them into a bitmap entry.
347 *
348 * It would be possible to optimise further; once we've run out of a
349 * single 128-byte bitmap, we currently switch to a 576-byte node, put
350 * the 128-byte bitmap in the first entry and then start allocating extra
351 * 128-byte entries.  We could instead use the 512 bytes of the node's
352 * data as a bitmap before moving to that scheme.  I do not believe this
353 * is a worthwhile optimisation; Rasmus Villemoes surveyed the current
354 * users of the IDA and almost none of them use more than 1024 entries.
355 * Those that do use more than the 8192 IDs that the 512 bytes would
356 * provide.
357 *
358 * The IDA always uses a lock to alloc/free.  If we add a 'test_bit'
359 * equivalent, it will still need locking.  Going to RCU lookup would require
360 * using RCU to free bitmaps, and that's not trivial without embedding an
361 * RCU head in the bitmap, which adds a 2-pointer overhead to each 128-byte
362 * bitmap, which is excessive.
363 */
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
364
365/**
366 * ida_alloc_range() - Allocate an unused ID.
367 * @ida: IDA handle.
368 * @min: Lowest ID to allocate.
369 * @max: Highest ID to allocate.
370 * @gfp: Memory allocation flags.
371 *
372 * Allocate an ID between @min and @max, inclusive.  The allocated ID will
373 * not exceed %INT_MAX, even if @max is larger.
374 *
375 * Context: Any context. It is safe to call this function without
376 * locking in your code.
377 * Return: The allocated ID, or %-ENOMEM if memory could not be allocated,
378 * or %-ENOSPC if there are no free IDs.
379 */
380int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max,
381			gfp_t gfp)
382{
383	XA_STATE(xas, &ida->xa, min / IDA_BITMAP_BITS);
384	unsigned bit = min % IDA_BITMAP_BITS;
385	unsigned long flags;
386	struct ida_bitmap *bitmap, *alloc = NULL;
 
 
 
 
 
 
 
 
387
388	if ((int)min < 0)
389		return -ENOSPC;
390
391	if ((int)max < 0)
392		max = INT_MAX;
 
 
 
 
 
 
 
 
 
393
394retry:
395	xas_lock_irqsave(&xas, flags);
396next:
397	bitmap = xas_find_marked(&xas, max / IDA_BITMAP_BITS, XA_FREE_MARK);
398	if (xas.xa_index > min / IDA_BITMAP_BITS)
399		bit = 0;
400	if (xas.xa_index * IDA_BITMAP_BITS + bit > max)
401		goto nospc;
402
403	if (xa_is_value(bitmap)) {
404		unsigned long tmp = xa_to_value(bitmap);
405
406		if (bit < BITS_PER_XA_VALUE) {
407			bit = find_next_zero_bit(&tmp, BITS_PER_XA_VALUE, bit);
408			if (xas.xa_index * IDA_BITMAP_BITS + bit > max)
409				goto nospc;
410			if (bit < BITS_PER_XA_VALUE) {
411				tmp |= 1UL << bit;
412				xas_store(&xas, xa_mk_value(tmp));
413				goto out;
414			}
415		}
416		bitmap = alloc;
417		if (!bitmap)
418			bitmap = kzalloc(sizeof(*bitmap), GFP_NOWAIT);
419		if (!bitmap)
420			goto alloc;
421		bitmap->bitmap[0] = tmp;
422		xas_store(&xas, bitmap);
423		if (xas_error(&xas)) {
424			bitmap->bitmap[0] = 0;
425			goto out;
426		}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
427	}
428
429	if (bitmap) {
430		bit = find_next_zero_bit(bitmap->bitmap, IDA_BITMAP_BITS, bit);
431		if (xas.xa_index * IDA_BITMAP_BITS + bit > max)
432			goto nospc;
433		if (bit == IDA_BITMAP_BITS)
434			goto next;
435
436		__set_bit(bit, bitmap->bitmap);
437		if (bitmap_full(bitmap->bitmap, IDA_BITMAP_BITS))
438			xas_clear_mark(&xas, XA_FREE_MARK);
439	} else {
440		if (bit < BITS_PER_XA_VALUE) {
441			bitmap = xa_mk_value(1UL << bit);
442		} else {
443			bitmap = alloc;
444			if (!bitmap)
445				bitmap = kzalloc(sizeof(*bitmap), GFP_NOWAIT);
446			if (!bitmap)
447				goto alloc;
448			__set_bit(bit, bitmap->bitmap);
449		}
450		xas_store(&xas, bitmap);
451	}
452out:
453	xas_unlock_irqrestore(&xas, flags);
454	if (xas_nomem(&xas, gfp)) {
455		xas.xa_index = min / IDA_BITMAP_BITS;
456		bit = min % IDA_BITMAP_BITS;
457		goto retry;
458	}
459	if (bitmap != alloc)
460		kfree(alloc);
461	if (xas_error(&xas))
462		return xas_error(&xas);
463	return xas.xa_index * IDA_BITMAP_BITS + bit;
464alloc:
465	xas_unlock_irqrestore(&xas, flags);
466	alloc = kzalloc(sizeof(*bitmap), gfp);
467	if (!alloc)
468		return -ENOMEM;
469	xas_set(&xas, min / IDA_BITMAP_BITS);
470	bit = min % IDA_BITMAP_BITS;
471	goto retry;
472nospc:
473	xas_unlock_irqrestore(&xas, flags);
474	kfree(alloc);
475	return -ENOSPC;
476}
477EXPORT_SYMBOL(ida_alloc_range);
478
479/**
480 * ida_free() - Release an allocated ID.
481 * @ida: IDA handle.
482 * @id: Previously allocated ID.
483 *
484 * Context: Any context. It is safe to call this function without
485 * locking in your code.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
486 */
487void ida_free(struct ida *ida, unsigned int id)
488{
489	XA_STATE(xas, &ida->xa, id / IDA_BITMAP_BITS);
490	unsigned bit = id % IDA_BITMAP_BITS;
 
 
 
491	struct ida_bitmap *bitmap;
492	unsigned long flags;
493
494	if ((int)id < 0)
495		return;
 
 
 
 
 
 
 
 
496
497	xas_lock_irqsave(&xas, flags);
498	bitmap = xas_load(&xas);
499
500	if (xa_is_value(bitmap)) {
501		unsigned long v = xa_to_value(bitmap);
502		if (bit >= BITS_PER_XA_VALUE)
503			goto err;
504		if (!(v & (1UL << bit)))
505			goto err;
506		v &= ~(1UL << bit);
507		if (!v)
508			goto delete;
509		xas_store(&xas, xa_mk_value(v));
510	} else {
511		if (!bitmap || !test_bit(bit, bitmap->bitmap))
512			goto err;
513		__clear_bit(bit, bitmap->bitmap);
514		xas_set_mark(&xas, XA_FREE_MARK);
515		if (bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) {
516			kfree(bitmap);
517delete:
518			xas_store(&xas, NULL);
519		}
520	}
521	xas_unlock_irqrestore(&xas, flags);
522	return;
 
523 err:
524	xas_unlock_irqrestore(&xas, flags);
525	WARN(1, "ida_free called for id=%d which is not allocated.\n", id);
526}
527EXPORT_SYMBOL(ida_free);
528
529/**
530 * ida_destroy() - Free all IDs.
531 * @ida: IDA handle.
532 *
533 * Calling this function frees all IDs and releases all resources used
534 * by an IDA.  When this call returns, the IDA is empty and can be reused
535 * or freed.  If the IDA is already empty, there is no need to call this
536 * function.
537 *
538 * Context: Any context. It is safe to call this function without
539 * locking in your code.
540 */
541void ida_destroy(struct ida *ida)
542{
543	XA_STATE(xas, &ida->xa, 0);
544	struct ida_bitmap *bitmap;
545	unsigned long flags;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
546
547	xas_lock_irqsave(&xas, flags);
548	xas_for_each(&xas, bitmap, ULONG_MAX) {
549		if (!xa_is_value(bitmap))
550			kfree(bitmap);
551		xas_store(&xas, NULL);
 
 
 
 
552	}
553	xas_unlock_irqrestore(&xas, flags);
 
 
 
 
 
554}
555EXPORT_SYMBOL(ida_destroy);
556
557#ifndef __KERNEL__
558extern void xa_dump_index(unsigned long index, unsigned int shift);
559#define IDA_CHUNK_SHIFT		ilog2(IDA_BITMAP_BITS)
560
561static void ida_dump_entry(void *entry, unsigned long index)
562{
563	unsigned long i;
564
565	if (!entry)
566		return;
567
568	if (xa_is_node(entry)) {
569		struct xa_node *node = xa_to_node(entry);
570		unsigned int shift = node->shift + IDA_CHUNK_SHIFT +
571			XA_CHUNK_SHIFT;
572
573		xa_dump_index(index * IDA_BITMAP_BITS, shift);
574		xa_dump_node(node);
575		for (i = 0; i < XA_CHUNK_SIZE; i++)
576			ida_dump_entry(node->slots[i],
577					index | (i << node->shift));
578	} else if (xa_is_value(entry)) {
579		xa_dump_index(index * IDA_BITMAP_BITS, ilog2(BITS_PER_LONG));
580		pr_cont("value: data %lx [%px]\n", xa_to_value(entry), entry);
581	} else {
582		struct ida_bitmap *bitmap = entry;
583
584		xa_dump_index(index * IDA_BITMAP_BITS, IDA_CHUNK_SHIFT);
585		pr_cont("bitmap: %p data", bitmap);
586		for (i = 0; i < IDA_BITMAP_LONGS; i++)
587			pr_cont(" %lx", bitmap->bitmap[i]);
588		pr_cont("\n");
589	}
590}
 
 
 
 
 
 
 
 
 
 
 
 
 
591
592static void ida_dump(struct ida *ida)
593{
594	struct xarray *xa = &ida->xa;
595	pr_debug("ida: %p node %p free %d\n", ida, xa->xa_head,
596				xa->xa_flags >> ROOT_TAG_SHIFT);
597	ida_dump_entry(xa->xa_head, 0);
598}
599#endif