ltable.h
1 /* 2 * Copyright (c) 2016 Apple Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 */ 28 #ifdef XNU_KERNEL_PRIVATE 29 30 #include <kern/kern_types.h> 31 #include <machine/locks.h> 32 33 #if CONFIG_LTABLE_DEBUG 34 #define ltdbg(fmt, ...) \ 35 printf("LT[%s]: " fmt "\n", __func__, ## __VA_ARGS__) 36 #else 37 #define ltdbg(fmt, ...) do { } while (0) 38 #endif 39 40 #ifdef LTABLE_VERBOSE_DEBUG 41 #define ltdbg_v(fmt, ...) \ 42 printf("LT[v:%s]: " fmt "\n", __func__, ## __VA_ARGS__) 43 #else 44 #define ltdbg_v(fmt, ...) do { } while (0) 45 #endif 46 47 #define ltinfo(fmt, ...) \ 48 printf("LT[%s]: " fmt "\n", __func__, ## __VA_ARGS__) 49 50 #define lterr(fmt, ...) \ 51 printf("LT[%s] ERROR: " fmt "\n", __func__, ## __VA_ARGS__) 52 53 54 55 /* ---------------------------------------------------------------------- 56 * 57 * Lockless Link Table Interface 58 * 59 * ---------------------------------------------------------------------- */ 60 61 struct ltable_id { 62 union { 63 uint64_t id; 64 struct { 65 /* 66 * this bitfield is OK because we don't need to 67 * enforce a particular memory layout 68 */ 69 uint64_t idx:18, /* allows indexing up to 8MB of 32byte objects */ 70 generation:46; 71 }; 72 }; 73 }; 74 75 /* this _must_ match the idx bitfield definition in struct ltable_id */ 76 #define LT_IDX_MAX (0x3ffff) 77 78 extern vm_size_t g_lt_max_tbl_size; 79 80 81 struct lt_elem { 82 struct ltable_id lt_id; 83 uint32_t lt_bits; 84 uint32_t lt_next_idx; 85 }; 86 87 /* reference count bits should _always_ be the low-order bits */ 88 #define LT_BITS_REFCNT_MASK (0x1FFFFFFFU) 89 #define LT_BITS_REFCNT_SHIFT (0) 90 #define LT_BITS_REFCNT (LT_BITS_REFCNT_MASK << LT_BITS_REFCNT_SHIFT) 91 92 #define LT_BITS_TYPE_MASK (0x3U) 93 #define LT_BITS_TYPE_SHIFT (29) 94 #define LT_BITS_TYPE (LT_BITS_TYPE_MASK << LT_BITS_TYPE_SHIFT) 95 96 #define LT_BITS_VALID_MASK (0x1U) 97 #define LT_BITS_VALID_SHIFT (31) 98 #define LT_BITS_VALID (LT_BITS_VALID_MASK << LT_BITS_VALID_SHIFT) 99 100 #define lt_bits_refcnt(bits) \ 101 (((bits) >> LT_BITS_REFCNT_SHIFT) & LT_BITS_REFCNT_MASK) 102 103 #define lt_bits_type(bits) \ 104 (((bits) >> LT_BITS_TYPE_SHIFT) & LT_BITS_TYPE_MASK) 105 106 #define lt_bits_valid(bits) \ 107 ((bits) & LT_BITS_VALID) 108 109 enum lt_elem_type { 110 LT_FREE = 0, 111 LT_ELEM = 1, 112 LT_LINK = 2, 113 LT_RESERVED = 3, 114 }; 115 116 struct link_table; 117 typedef void (*ltable_poison_func)(struct link_table *, struct lt_elem *); 118 119 /* 120 * link_table structure 121 * 122 * A link table is a container for slabs of elements. Each slab is 'slab_sz' 123 * bytes and contains 'slab_sz/elem_sz' elements (of 'elem_sz' bytes each). 124 * These slabs allow the table to be broken up into potentially dis-contiguous 125 * VA space. On 32-bit platforms with large amounts of physical RAM, this is 126 * quite important. Keeping slabs like this slightly complicates retrieval of 127 * table elements, but not by much. 128 */ 129 struct link_table { 130 struct lt_elem **table; /* an array of 'slabs' of elements */ 131 struct lt_elem **next_free_slab; 132 struct ltable_id free_list __attribute__((aligned(8))); 133 134 uint32_t elem_sz; /* size of a table element (bytes) */ 135 uint32_t slab_shift; 136 uint32_t slab_msk; 137 uint32_t slab_elem; 138 uint32_t slab_sz; /* size of a table 'slab' object (bytes) */ 139 140 uint32_t nelem; 141 uint32_t used_elem; 142 zone_t slab_zone; 143 144 ltable_poison_func poison; 145 146 lck_mtx_t lock; 147 uint32_t state; 148 149 #if CONFIG_LTABLE_STATS 150 uint32_t nslabs; 151 152 uint64_t nallocs; 153 uint64_t nreallocs; 154 uint64_t npreposts; 155 int64_t nreservations; 156 uint64_t nreserved_releases; 157 uint64_t nspins; 158 159 uint64_t max_used; 160 uint64_t avg_used; 161 uint64_t max_reservations; 162 uint64_t avg_reservations; 163 #endif 164 } __attribute__((aligned(8))); 165 166 /** 167 * ltable_init: initialize a link table with given parameters 168 * 169 */ 170 extern void ltable_init(struct link_table *table, const char *name, 171 uint32_t max_tbl_elem, uint32_t elem_sz, 172 ltable_poison_func poison); 173 174 175 /** 176 * ltable_grow: grow a link table by adding another 'slab' of table elements 177 * 178 * Conditions: 179 * table mutex is unlocked 180 * calling thread can block 181 */ 182 extern void ltable_grow(struct link_table *table, uint32_t min_free); 183 184 185 /** 186 * ltable_alloc_elem: allocate one or more elements from a given table 187 * 188 * The returned element(s) will be of type 'type', but will remain invalid. 189 * 190 * If the caller has disabled preemption, then this function may (rarely) spin 191 * waiting either for another thread to either release 'nelem' table elements, 192 * or grow the table. 193 * 194 * If the caller can block, then this function may (rarely) block while 195 * the table grows to meet the demand for 'nelem' element(s). 196 */ 197 extern __attribute__((noinline)) 198 struct lt_elem *ltable_alloc_elem(struct link_table *table, int type, 199 int nelem, int nattempts); 200 201 202 #if DEVELOPMENT || DEBUG 203 /** 204 * ltable_nelem: returns how many elements are used in this 205 * table. 206 */ 207 extern 208 int ltable_nelem(struct link_table *table); 209 #endif 210 211 /** 212 * ltable_realloc_elem: convert a reserved element to a particular type 213 * 214 * This funciton is used to convert reserved elements (not yet marked valid) 215 * to the given 'type'. The generation of 'elem' is incremented, the element 216 * is disconnected from any list to which it belongs, and its type is set to 217 * 'type'. 218 */ 219 extern void ltable_realloc_elem(struct link_table *table, 220 struct lt_elem *elem, int type); 221 222 223 /** 224 * ltable_get_elem: get a reference to a table element identified by 'id' 225 * 226 * Returns a reference to the table element associated with the given 'id', or 227 * NULL if the 'id' was invalid or does not exist in 'table'. The caller is 228 * responsible to release the reference using ltable_put_elem(). 229 * 230 * NOTE: if the table element pointed to by 'id' is marked as invalid, 231 * this function will return NULL. 232 */ 233 extern struct lt_elem *ltable_get_elem(struct link_table *table, uint64_t id); 234 235 236 /** 237 * ltable_put_elem: release a reference to table element 238 * 239 * This function releases a reference taken on a table element via 240 * ltable_get_elem(). This function will release the element back to 'table' 241 * when the reference count goes to 0 AND the element has been marked as 242 * invalid. 243 */ 244 extern void ltable_put_elem(struct link_table *table, struct lt_elem *elem); 245 246 247 /** 248 * lt_elem_invalidate: mark 'elem' as invalid 249 * 250 * NOTE: this does _not_ get or put a reference on 'elem' 251 */ 252 extern void lt_elem_invalidate(struct lt_elem *elem); 253 254 255 /** 256 * lt_elem_mkvalid: mark 'elem' as valid 257 * 258 * NOTE: this does _not_ get or put a reference on 'elem' 259 */ 260 extern void lt_elem_mkvalid(struct lt_elem *elem); 261 262 263 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 264 * 265 * API: lt_elem_list_* 266 * 267 * Reuse the free list linkage member, 'lt_next_idx' of a link table element 268 * in a slightly more generic singly-linked list. All members of this list 269 * have been allocated from a table, but have not been made valid. 270 * 271 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ 272 273 /** 274 * lt_elem_list_link: link a child onto a parent 275 * 276 * Note that if 'parent' is the head of a list, this function will follow that 277 * list and attach 'child' to the end of it. In the simplest case, this 278 * results in: parent->child 279 * however this could also result in: parent->...->child 280 */ 281 extern int lt_elem_list_link(struct link_table *table, 282 struct lt_elem *parent, struct lt_elem *child); 283 284 285 /** 286 * lt_elem_list_first: obtain a pointer to the first element of a list. 287 * 288 * This function converts the head of a singly-linked list, 'id', into a real 289 * lt_elem object and returns a pointer to the object. 290 * 291 * It does _not_ take an extra reference on the object: the list implicitly 292 * holds that reference. 293 */ 294 extern struct lt_elem *lt_elem_list_first(struct link_table *table, uint64_t id); 295 296 297 /** 298 * lt_elem_list_next: return the item subsequent to 'elem' in a list 299 * 300 * Note that this will return NULL if 'elem' is actually the end of the list. 301 */ 302 extern struct lt_elem *lt_elem_list_next(struct link_table *table, 303 struct lt_elem *elem); 304 305 306 /** 307 * lt_elem_list_break: break a list in two around 'elem' 308 * 309 * This function will reset the next_idx field of 'elem' (making it the end of 310 * the list), and return the element subsequent to 'elem' in the list 311 * (which could be NULL) 312 */ 313 extern struct lt_elem *lt_elem_list_break(struct link_table *table, 314 struct lt_elem *elem); 315 316 317 /** 318 * lt_elem_list_pop: pop an item off the head of a list 319 * 320 * The list head is pointed to by '*id', the element corresponding to '*id' is 321 * returned by this function, and the new list head is returned in the in/out 322 * parameter, '*id'. The caller is responsible for the reference on the 323 * returned object. A realloc is done to reset the type of the object, but it 324 * is still left invalid. 325 */ 326 extern struct lt_elem *lt_elem_list_pop(struct link_table *table, 327 uint64_t *id, int type); 328 329 330 /** 331 * lt_elem_list_release: free an entire list of reserved elements 332 * 333 * All elements in the list whose first member is 'head' will be released back 334 * to 'table' as free elements. The 'type' parameter is used in development 335 * kernels to assert that all elements on the list are of the given type. 336 */ 337 extern int lt_elem_list_release(struct link_table *table, 338 struct lt_elem *head, 339 int __assert_only type); 340 341 static inline int 342 lt_elem_list_release_id(struct link_table *table, 343 uint64_t id, int type) 344 { 345 return lt_elem_list_release(table, lt_elem_list_first(table, id), type); 346 } 347 348 #endif /* XNU_KERNEL_PRIVATE */