1 /* 2 * include/linux/idr.h 3 * 4 * 2002-10-18 written by Jim Houston [email protected] 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/radix-tree.h> 16 #include <linux/gfp.h> 17 #include <linux/percpu.h> 18 19 struct idr { 20 struct radix_tree_root idr_rt; 21 unsigned int idr_base; 22 unsigned int idr_next; 23 }; 24 25 /* 26 * The IDR API does not expose the tagging functionality of the radix tree 27 * to users. Use tag 0 to track whether a node has free space below it. 28 */ 29 #define IDR_FREE 0 30 31 /* Set the IDR flag and the IDR_FREE tag */ 32 #define IDR_RT_MARKER (ROOT_IS_IDR | (__force gfp_t) \ 33 (1 << (ROOT_TAG_SHIFT + IDR_FREE))) 34 35 #define IDR_INIT_BASE(base) { \ 36 .idr_rt = RADIX_TREE_INIT(IDR_RT_MARKER), \ 37 .idr_base = (base), \ 38 .idr_next = 0, \ 39 } 40 41 /** 42 * IDR_INIT() - Initialise an IDR. 43 * 44 * A freshly-initialised IDR contains no IDs. 45 */ 46 #define IDR_INIT IDR_INIT_BASE(0) 47 48 /** 49 * DEFINE_IDR() - Define a statically-allocated IDR 50 * @name: Name of IDR 51 * 52 * An IDR defined using this macro is ready for use with no additional 53 * initialisation required. It contains no IDs. 54 */ 55 #define DEFINE_IDR(name) struct idr name = IDR_INIT 56 57 /** 58 * idr_get_cursor - Return the current position of the cyclic allocator 59 * @idr: idr handle 60 * 61 * The value returned is the value that will be next returned from 62 * idr_alloc_cyclic() if it is free (otherwise the search will start from 63 * this position). 64 */ 65 static inline unsigned int idr_get_cursor(const struct idr *idr) 66 { 67 return READ_ONCE(idr->idr_next); 68 } 69 70 /** 71 * idr_set_cursor - Set the current position of the cyclic allocator 72 * @idr: idr handle 73 * @val: new position 74 * 75 * The next call to idr_alloc_cyclic() will return @val if it is free 76 * (otherwise the search will start from this position). 77 */ 78 static inline void idr_set_cursor(struct idr *idr, unsigned int val) 79 { 80 WRITE_ONCE(idr->idr_next, val); 81 } 82 83 /** 84 * DOC: idr sync 85 * idr synchronization (stolen from radix-tree.h) 86 * 87 * idr_find() is able to be called locklessly, using RCU. The caller must 88 * ensure calls to this function are made within rcu_read_lock() regions. 89 * Other readers (lock-free or otherwise) and modifications may be running 90 * concurrently. 91 * 92 * It is still required that the caller manage the synchronization and 93 * lifetimes of the items. So if RCU lock-free lookups are used, typically 94 * this would mean that the items have their own locks, or are amenable to 95 * lock-free access; and that the items are freed by RCU (or only freed after 96 * having been deleted from the idr tree *and* a synchronize_rcu() grace 97 * period). 98 */ 99 100 void idr_preload(gfp_t gfp_mask); 101 102 int idr_alloc(struct idr *, void *ptr, int start, int end, gfp_t); 103 int __must_check idr_alloc_u32(struct idr *, void *ptr, u32 *id, 104 unsigned long max, gfp_t); 105 int idr_alloc_cyclic(struct idr *, void *ptr, int start, int end, gfp_t); 106 void *idr_remove(struct idr *, unsigned long id); 107 void *idr_find(const struct idr *, unsigned long id); 108 int idr_for_each(const struct idr *, 109 int (*fn)(int id, void *p, void *data), void *data); 110 void *idr_get_next(struct idr *, int *nextid); 111 void *idr_get_next_ul(struct idr *, unsigned long *nextid); 112 void *idr_replace(struct idr *, void *, unsigned long id); 113 void idr_destroy(struct idr *); 114 115 /** 116 * idr_init_base() - Initialise an IDR. 117 * @idr: IDR handle. 118 * @base: The base value for the IDR. 119 * 120 * This variation of idr_init() creates an IDR which will allocate IDs 121 * starting at %base. 122 */ 123 static inline void idr_init_base(struct idr *idr, int base) 124 { 125 INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER); 126 idr->idr_base = base; 127 idr->idr_next = 0; 128 } 129 130 /** 131 * idr_init() - Initialise an IDR. 132 * @idr: IDR handle. 133 * 134 * Initialise a dynamically allocated IDR. To initialise a 135 * statically allocated IDR, use DEFINE_IDR(). 136 */ 137 static inline void idr_init(struct idr *idr) 138 { 139 idr_init_base(idr, 0); 140 } 141 142 /** 143 * idr_is_empty() - Are there any IDs allocated? 144 * @idr: IDR handle. 145 * 146 * Return: %true if any IDs have been allocated from this IDR. 147 */ 148 static inline bool idr_is_empty(const struct idr *idr) 149 { 150 return radix_tree_empty(&idr->idr_rt) && 151 radix_tree_tagged(&idr->idr_rt, IDR_FREE); 152 } 153 154 /** 155 * idr_preload_end - end preload section started with idr_preload() 156 * 157 * Each idr_preload() should be matched with an invocation of this 158 * function. See idr_preload() for details. 159 */ 160 static inline void idr_preload_end(void) 161 { 162 preempt_enable(); 163 } 164 165 /** 166 * idr_for_each_entry() - Iterate over an IDR's elements of a given type. 167 * @idr: IDR handle. 168 * @entry: The type * to use as cursor 169 * @id: Entry ID. 170 * 171 * @entry and @id do not need to be initialized before the loop, and 172 * after normal termination @entry is left with the value NULL. This 173 * is convenient for a "not found" value. 174 */ 175 #define idr_for_each_entry(idr, entry, id) \ 176 for (id = 0; ((entry) = idr_get_next(idr, &(id))) != NULL; ++id) 177 178 /** 179 * idr_for_each_entry_ul() - Iterate over an IDR's elements of a given type. 180 * @idr: IDR handle. 181 * @entry: The type * to use as cursor. 182 * @id: Entry ID. 183 * 184 * @entry and @id do not need to be initialized before the loop, and 185 * after normal termination @entry is left with the value NULL. This 186 * is convenient for a "not found" value. 187 */ 188 #define idr_for_each_entry_ul(idr, entry, id) \ 189 for (id = 0; ((entry) = idr_get_next_ul(idr, &(id))) != NULL; ++id) 190 191 /** 192 * idr_for_each_entry_continue() - Continue iteration over an IDR's elements of a given type 193 * @idr: IDR handle. 194 * @entry: The type * to use as a cursor. 195 * @id: Entry ID. 196 * 197 * Continue to iterate over entries, continuing after the current position. 198 */ 199 #define idr_for_each_entry_continue(idr, entry, id) \ 200 for ((entry) = idr_get_next((idr), &(id)); \ 201 entry; \ 202 ++id, (entry) = idr_get_next((idr), &(id))) 203 204 /* 205 * IDA - IDR based id allocator, use when translation from id to 206 * pointer isn't necessary. 207 */ 208 #define IDA_CHUNK_SIZE 128 /* 128 bytes per chunk */ 209 #define IDA_BITMAP_LONGS (IDA_CHUNK_SIZE / sizeof(long)) 210 #define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8) 211 212 struct ida_bitmap { 213 unsigned long bitmap[IDA_BITMAP_LONGS]; 214 }; 215 216 DECLARE_PER_CPU(struct ida_bitmap *, ida_bitmap); 217 218 struct ida { 219 struct radix_tree_root ida_rt; 220 }; 221 222 #define IDA_INIT { \ 223 .ida_rt = RADIX_TREE_INIT(IDR_RT_MARKER | GFP_NOWAIT), \ 224 } 225 #define DEFINE_IDA(name) struct ida name = IDA_INIT 226 227 int ida_pre_get(struct ida *ida, gfp_t gfp_mask); 228 int ida_get_new_above(struct ida *ida, int starting_id, int *p_id); 229 void ida_remove(struct ida *ida, int id); 230 void ida_destroy(struct ida *ida); 231 232 int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end, 233 gfp_t gfp_mask); 234 void ida_simple_remove(struct ida *ida, unsigned int id); 235 236 static inline void ida_init(struct ida *ida) 237 { 238 INIT_RADIX_TREE(&ida->ida_rt, IDR_RT_MARKER | GFP_NOWAIT); 239 } 240 241 /** 242 * ida_get_new - allocate new ID 243 * @ida: idr handle 244 * @p_id: pointer to the allocated handle 245 * 246 * Simple wrapper around ida_get_new_above() w/ @starting_id of zero. 247 */ 248 static inline int ida_get_new(struct ida *ida, int *p_id) 249 { 250 return ida_get_new_above(ida, 0, p_id); 251 } 252 253 static inline bool ida_is_empty(const struct ida *ida) 254 { 255 return radix_tree_empty(&ida->ida_rt); 256 } 257 #endif /* __IDR_H__ */ 258