Green shading in the line number column means the source is part of the translation unit, red means it is conditionally excluded. Highlighted line numbers link to the translation unit page. Highlighted macros link to the macro page.
1: /* 2: * include/linux/idr.h 3: * 4: * 2002-10-18 written by Jim Houston jim.houston@ccur.com 5: * Copyright (C) 2002 by Concurrent Computer Corporation 6: * Distributed under the GNU GPL license version 2. 7: * 8: * Small id to pointer translation service avoiding fixed sized 9: * tables. 10: */ 11: 12: #ifndef __IDR_H__ 13: #define __IDR_H__ 14: 15: #include <linux/types.h> 16: #include <linux/bitops.h> 17: #include <linux/init.h> 18: #include <linux/rcupdate.h> 19: 20: /* 21: * We want shallower trees and thus more bits covered at each layer. 8 22: * bits gives us large enough first layer for most use cases and maximum 23: * tree depth of 4. Each idr_layer is slightly larger than 2k on 64bit and 24: * 1k on 32bit. 25: */ 26: #define IDR_BITS 8 27: #define IDR_SIZE (1 << IDR_BITS) 28: #define IDR_MASK ((1 << IDR_BITS)-1) 29: 30: struct idr_layer { 31: int prefix; /* the ID prefix of this idr_layer */ 32: DECLARE_BITMAP(bitmap, IDR_SIZE); /* A zero bit means "space here" */ 33: struct idr_layer __rcu *ary[1<<IDR_BITS]; 34: int count; /* When zero, we can release it */ 35: int layer; /* distance from leaf */ 36: struct rcu_head rcu_head; 37: }; 38: 39: struct idr { 40: struct idr_layer __rcu *hint; /* the last layer allocated from */ 41: struct idr_layer __rcu *top; 42: struct idr_layer *id_free; 43: int layers; /* only valid w/o concurrent changes */ 44: int id_free_cnt; 45: int cur; /* current pos for cyclic allocation */ 46: spinlock_t lock; 47: }; 48: 49: #define IDR_INIT(name) \ 50: { \ 51: .lock = __SPIN_LOCK_UNLOCKED(name.lock), \ 52: } 53: #define DEFINE_IDR(name) struct idr name = IDR_INIT(name) 54: 55: /** 56: * DOC: idr sync 57: * idr synchronization (stolen from radix-tree.h) 58: * 59: * idr_find() is able to be called locklessly, using RCU. The caller must 60: * ensure calls to this function are made within rcu_read_lock() regions. 61: * Other readers (lock-free or otherwise) and modifications may be running 62: * concurrently. 63: * 64: * It is still required that the caller manage the synchronization and 65: * lifetimes of the items. So if RCU lock-free lookups are used, typically 66: * this would mean that the items have their own locks, or are amenable to 67: * lock-free access; and that the items are freed by RCU (or only freed after 68: * having been deleted from the idr tree *and* a synchronize_rcu() grace 69: * period). 70: */ 71: 72: /* 73: * This is what we export. 74: */ 75: 76: void *idr_find_slowpath(struct idr *idp, int id); 77: void idr_preload(gfp_t gfp_mask); 78: int idr_alloc(struct idr *idp, void *ptr, int start, int end, gfp_t gfp_mask); 79: int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask); 80: int idr_for_each(struct idr *idp, 81: int (*fn)(int id, void *p, void *data), void *data); 82: void *idr_get_next(struct idr *idp, int *nextid); 83: void *idr_replace(struct idr *idp, void *ptr, int id); 84: void idr_remove(struct idr *idp, int id); 85: void idr_free(struct idr *idp, int id); 86: void idr_destroy(struct idr *idp); 87: void idr_init(struct idr *idp); 88: 89: /** 90: * idr_preload_end - end preload section started with idr_preload() 91: * 92: * Each idr_preload() should be matched with an invocation of this 93: * function. See idr_preload() for details. 94: */ 95: static inline void idr_preload_end(void) 96: { 97: preempt_enable(); 98: } 99: 100: /** 101: * idr_find - return pointer for given id 102: * @idr: idr handle 103: * @id: lookup key 104: * 105: * Return the pointer given the id it has been registered with. A %NULL 106: * return indicates that @id is not valid or you passed %NULL in 107: * idr_get_new(). 108: * 109: * This function can be called under rcu_read_lock(), given that the leaf 110: * pointers lifetimes are correctly managed. 111: */ 112: static inline void *idr_find(struct idr *idr, int id) 113: { 114: struct idr_layer *hint = rcu_dereference_raw(idr->hint); 115: 116: if (hint && (id & ~IDR_MASK) == hint->prefix) 117: return rcu_dereference_raw(hint->ary[id & IDR_MASK]); 118: 119: return idr_find_slowpath(idr, id); 120: } 121: 122: /** 123: * idr_for_each_entry - iterate over an idr's elements of a given type 124: * @idp: idr handle 125: * @entry: the type * to use as cursor 126: * @id: id entry's key 127: * 128: * @entry and @id do not need to be initialized before the loop, and 129: * after normal terminatinon @entry is left with the value NULL. This 130: * is convenient for a "not found" value. 131: */ 132: #define idr_for_each_entry(idp, entry, id) \ 133: for (id = 0; ((entry) = idr_get_next(idp, &(id))) != NULL; ++id) 134: 135: /* 136: * Don't use the following functions. These exist only to suppress 137: * deprecated warnings on EXPORT_SYMBOL()s. 138: */ 139: int __idr_pre_get(struct idr *idp, gfp_t gfp_mask); 140: int __idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id); 141: void __idr_remove_all(struct idr *idp); 142: 143: /** 144: * idr_pre_get - reserve resources for idr allocation 145: * @idp: idr handle 146: * @gfp_mask: memory allocation flags 147: * 148: * Part of old alloc interface. This is going away. Use 149: * idr_preload[_end]() and idr_alloc() instead. 150: */ 151: static inline int __deprecated idr_pre_get(struct idr *idp, gfp_t gfp_mask) 152: { 153: return __idr_pre_get(idp, gfp_mask); 154: } 155: 156: /** 157: * idr_get_new_above - allocate new idr entry above or equal to a start id 158: * @idp: idr handle 159: * @ptr: pointer you want associated with the id 160: * @starting_id: id to start search at 161: * @id: pointer to the allocated handle 162: * 163: * Part of old alloc interface. This is going away. Use 164: * idr_preload[_end]() and idr_alloc() instead. 165: */ 166: static inline int __deprecated idr_get_new_above(struct idr *idp, void *ptr, 167: int starting_id, int *id) 168: { 169: return __idr_get_new_above(idp, ptr, starting_id, id); 170: } 171: 172: /** 173: * idr_get_new - allocate new idr entry 174: * @idp: idr handle 175: * @ptr: pointer you want associated with the id 176: * @id: pointer to the allocated handle 177: * 178: * Part of old alloc interface. This is going away. Use 179: * idr_preload[_end]() and idr_alloc() instead. 180: */ 181: static inline int __deprecated idr_get_new(struct idr *idp, void *ptr, int *id) 182: { 183: return __idr_get_new_above(idp, ptr, 0, id); 184: } 185: 186: /** 187: * idr_remove_all - remove all ids from the given idr tree 188: * @idp: idr handle 189: * 190: * If you're trying to destroy @idp, calling idr_destroy() is enough. 191: * This is going away. Don't use. 192: */ 193: static inline void __deprecated idr_remove_all(struct idr *idp) 194: { 195: __idr_remove_all(idp); 196: } 197: 198: /* 199: * IDA - IDR based id allocator, use when translation from id to 200: * pointer isn't necessary. 201: * 202: * IDA_BITMAP_LONGS is calculated to be one less to accommodate 203: * ida_bitmap->nr_busy so that the whole struct fits in 128 bytes. 204: */ 205: #define IDA_CHUNK_SIZE 128 /* 128 bytes per chunk */ 206: #define IDA_BITMAP_LONGS (IDA_CHUNK_SIZE / sizeof(long) - 1) 207: #define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8) 208: 209: struct ida_bitmap { 210: long nr_busy; 211: unsigned long bitmap[IDA_BITMAP_LONGS]; 212: }; 213: 214: struct ida { 215: struct idr idr; 216: struct ida_bitmap *free_bitmap; 217: }; 218: 219: #define IDA_INIT(name) { .idr = IDR_INIT((name).idr), .free_bitmap = NULL, } 220: #define DEFINE_IDA(name) struct ida name = IDA_INIT(name) 221: 222: int ida_pre_get(struct ida *ida, gfp_t gfp_mask); 223: int ida_get_new_above(struct ida *ida, int starting_id, int *p_id); 224: void ida_remove(struct ida *ida, int id); 225: void ida_destroy(struct ida *ida); 226: void ida_init(struct ida *ida); 227: 228: int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end, 229: gfp_t gfp_mask); 230: void ida_simple_remove(struct ida *ida, unsigned int id); 231: 232: /** 233: * ida_get_new - allocate new ID 234: * @ida: idr handle 235: * @p_id: pointer to the allocated handle 236: * 237: * Simple wrapper around ida_get_new_above() w/ @starting_id of zero. 238: */ 239: static inline int ida_get_new(struct ida *ida, int *p_id) 240: { 241: return ida_get_new_above(ida, 0, p_id); 242: } 243: 244: void __init idr_init_cache(void); 245: 246: #endif /* __IDR_H__ */ 247: