1 /* Public domain. */ 2 3 #ifndef _LINUX_XARRAY_H 4 #define _LINUX_XARRAY_H 5 6 #include <linux/gfp.h> 7 8 #include <sys/tree.h> 9 10 #define XA_FLAGS_ALLOC (1 << 0) 11 #define XA_FLAGS_ALLOC1 (1 << 1) 12 #define XA_FLAGS_LOCK_IRQ (1 << 2) 13 14 /* 15 * lower bits of pointer are tagged: 16 * 00: pointer 17 * 01: value 18 * 10: internal 19 */ 20 struct xarray_entry { 21 SPLAY_ENTRY(xarray_entry) entry; 22 int id; 23 void *ptr; 24 }; 25 26 struct xarray { 27 gfp_t xa_flags; 28 struct mutex xa_lock; 29 SPLAY_HEAD(xarray_tree, xarray_entry) xa_tree; 30 }; 31 32 #define DEFINE_XARRAY_ALLOC(name) \ 33 struct xarray name = { \ 34 .xa_flags = XA_FLAGS_ALLOC, \ 35 .xa_lock = MUTEX_INITIALIZER(IPL_NONE), \ 36 .xa_tree = SPLAY_INITIALIZER(&name.xa_tree) \ 37 } 38 39 struct xarray_range { 40 uint32_t start; 41 uint32_t end; 42 }; 43 44 #define XA_LIMIT(_start, _end) (struct xarray_range){ _start, _end } 45 #define xa_limit_32b XA_LIMIT(0, UINT_MAX) 46 47 void xa_init_flags(struct xarray *, gfp_t); 48 void xa_destroy(struct xarray *); 49 int __xa_alloc(struct xarray *, u32 *, void *, struct xarray_range, gfp_t); 50 int __xa_alloc_cyclic(struct xarray *, u32 *, void *, struct xarray_range, 51 u32 *, gfp_t); 52 void *__xa_load(struct xarray *, unsigned long); 53 void *__xa_store(struct xarray *, unsigned long, void *, gfp_t); 54 void *__xa_erase(struct xarray *, unsigned long); 55 void *xa_get_next(struct xarray *, unsigned long *); 56 57 #define xa_for_each(xa, index, entry) \ 58 for (index = 0; ((entry) = xa_get_next(xa, &(index))) != NULL; index++) 59 60 #define xa_lock(_xa) do { \ 61 mtx_enter(&(_xa)->xa_lock); \ 62 } while (0) 63 64 #define xa_unlock(_xa) do { \ 65 mtx_leave(&(_xa)->xa_lock); \ 66 } while (0) 67 68 #define xa_lock_irq(_xa) do { \ 69 mtx_enter(&(_xa)->xa_lock); \ 70 } while (0) 71 72 #define xa_unlock_irq(_xa) do { \ 73 mtx_leave(&(_xa)->xa_lock); \ 74 } while (0) 75 76 #define xa_lock_irqsave(_xa, _flags) do { \ 77 _flags = 0; \ 78 mtx_enter(&(_xa)->xa_lock); \ 79 } while (0) 80 81 #define xa_unlock_irqrestore(_xa, _flags) do { \ 82 (void)(_flags); \ 83 mtx_leave(&(_xa)->xa_lock); \ 84 } while (0) 85 86 static inline void * 87 xa_mk_value(unsigned long v) 88 { 89 unsigned long r = (v << 1) | 1; 90 return (void *)r; 91 } 92 93 static inline bool 94 xa_is_value(const void *e) 95 { 96 unsigned long v = (unsigned long)e; 97 return v & 1; 98 } 99 100 static inline unsigned long 101 xa_to_value(const void *e) 102 { 103 unsigned long v = (unsigned long)e; 104 return v >> 1; 105 } 106 107 #define XA_ERROR(x) ((struct xa_node *)(((unsigned long)x << 2) | 2)) 108 109 static inline int 110 xa_err(const void *e) 111 { 112 long v = (long)e; 113 /* not tagged internal, not an errno */ 114 if ((v & 3) != 2) 115 return 0; 116 v >>= 2; 117 if (v >= -ELAST) 118 return v; 119 return 0; 120 } 121 122 static inline bool 123 xa_is_err(const void *e) 124 { 125 return xa_err(e) != 0; 126 } 127 128 static inline int 129 xa_alloc(struct xarray *xa, u32 *id, void *entry, struct xarray_range xr, 130 gfp_t gfp) 131 { 132 int r; 133 mtx_enter(&xa->xa_lock); 134 r = __xa_alloc(xa, id, entry, xr, gfp); 135 mtx_leave(&xa->xa_lock); 136 return r; 137 } 138 139 static inline void * 140 xa_load(struct xarray *xa, unsigned long index) 141 { 142 void *r; 143 r = __xa_load(xa, index); 144 return r; 145 } 146 147 148 static inline void * 149 xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp) 150 { 151 void *r; 152 mtx_enter(&xa->xa_lock); 153 r = __xa_store(xa, index, entry, gfp); 154 mtx_leave(&xa->xa_lock); 155 return r; 156 } 157 158 static inline void * 159 xa_erase(struct xarray *xa, unsigned long index) 160 { 161 void *r; 162 mtx_enter(&xa->xa_lock); 163 r = __xa_erase(xa, index); 164 mtx_leave(&xa->xa_lock); 165 return r; 166 } 167 168 static inline void * 169 xa_store_irq(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp) 170 { 171 void *r; 172 mtx_enter(&xa->xa_lock); 173 r = __xa_store(xa, index, entry, gfp); 174 mtx_leave(&xa->xa_lock); 175 return r; 176 } 177 178 static inline void * 179 xa_erase_irq(struct xarray *xa, unsigned long index) 180 { 181 void *r; 182 mtx_enter(&xa->xa_lock); 183 r = __xa_erase(xa, index); 184 mtx_leave(&xa->xa_lock); 185 return r; 186 } 187 188 static inline bool 189 xa_empty(const struct xarray *xa) 190 { 191 return SPLAY_EMPTY(&xa->xa_tree); 192 } 193 194 static inline void 195 xa_init(struct xarray *xa) 196 { 197 xa_init_flags(xa, 0); 198 } 199 200 #endif 201