osfmk/kern/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 /**
 168  * ltable_bootstrap: bootstrap a link table
 169  *
 170  * Called once at system boot
 171  */
 172 extern void ltable_bootstrap(void);
 173
 174
 175 /**
 176  * ltable_init: initialize a link table with given parameters
 177  *
 178  */
 179 extern void ltable_init(struct link_table *table, const char *name,
 180     uint32_t max_tbl_elem, uint32_t elem_sz,
 181     ltable_poison_func poison);
 182
 183
 184 /**
 185  * ltable_grow: grow a link table by adding another 'slab' of table elements
 186  *
 187  * Conditions:
 188  *      table mutex is unlocked
 189  *      calling thread can block
 190  */
 191 extern void ltable_grow(struct link_table *table, uint32_t min_free);
 192
 193
 194 /**
 195  * ltable_alloc_elem: allocate one or more elements from a given table
 196  *
 197  * The returned element(s) will be of type 'type', but will remain invalid.
 198  *
 199  * If the caller has disabled preemption, then this function may (rarely) spin
 200  * waiting either for another thread to either release 'nelem' table elements,
 201  * or grow the table.
 202  *
 203  * If the caller can block, then this function may (rarely) block while
 204  * the table grows to meet the demand for 'nelem' element(s).
 205  */
 206 extern __attribute__((noinline))
 207 struct lt_elem *ltable_alloc_elem(struct link_table *table, int type,
 208     int nelem, int nattempts);
 209
 210
 211 #if DEVELOPMENT || DEBUG
 212 /**
 213  * ltable_nelem: returns how many elements are used in this
 214  * table.
 215  */
 216 extern
 217 int ltable_nelem(struct link_table *table);
 218 #endif
 219
 220 /**
 221  * ltable_realloc_elem: convert a reserved element to a particular type
 222  *
 223  * This funciton is used to convert reserved elements (not yet marked valid)
 224  * to the given 'type'. The generation of 'elem' is incremented, the element
 225  * is disconnected from any list to which it belongs, and its type is set to
 226  * 'type'.
 227  */
 228 extern void ltable_realloc_elem(struct link_table *table,
 229     struct lt_elem *elem, int type);
 230
 231
 232 /**
 233  * ltable_get_elem: get a reference to a table element identified by 'id'
 234  *
 235  * Returns a reference to the table element associated with the given 'id', or
 236  * NULL if the 'id' was invalid or does not exist in 'table'. The caller is
 237  * responsible to release the reference using ltable_put_elem().
 238  *
 239  * NOTE: if the table element pointed to by 'id' is marked as invalid,
 240  *       this function will return NULL.
 241  */
 242 extern struct lt_elem *ltable_get_elem(struct link_table *table, uint64_t id);
 243
 244
 245 /**
 246  * ltable_put_elem: release a reference to table element
 247  *
 248  * This function releases a reference taken on a table element via
 249  * ltable_get_elem(). This function will release the element back to 'table'
 250  * when the reference count goes to 0 AND the element has been marked as
 251  * invalid.
 252  */
 253 extern void ltable_put_elem(struct link_table *table, struct lt_elem *elem);
 254
 255
 256 /**
 257  * lt_elem_invalidate: mark 'elem' as invalid
 258  *
 259  * NOTE: this does _not_ get or put a reference on 'elem'
 260  */
 261 extern void lt_elem_invalidate(struct lt_elem *elem);
 262
 263
 264 /**
 265  * lt_elem_mkvalid: mark 'elem' as valid
 266  *
 267  * NOTE: this does _not_ get or put a reference on 'elem'
 268  */
 269 extern void lt_elem_mkvalid(struct lt_elem *elem);
 270
 271
 272 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
 273  *
 274  * API: lt_elem_list_*
 275  *
 276  * Reuse the free list linkage member, 'lt_next_idx' of a link table element
 277  * in a slightly more generic singly-linked list. All members of this list
 278  * have been allocated from a table, but have not been made valid.
 279  *
 280  * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 281
 282 /**
 283  * lt_elem_list_link: link a child onto a parent
 284  *
 285  * Note that if 'parent' is the head of a list, this function will follow that
 286  * list and attach 'child' to the end of it. In the simplest case, this
 287  * results in: parent->child
 288  * however this could also result in: parent->...->child
 289  */
 290 extern int lt_elem_list_link(struct link_table *table,
 291     struct lt_elem *parent, struct lt_elem *child);
 292
 293
 294 /**
 295  * lt_elem_list_first: obtain a pointer to the first element of a list.
 296  *
 297  * This function converts the head of a singly-linked list, 'id', into a real
 298  * lt_elem object and returns a pointer to the object.
 299  *
 300  * It does _not_ take an extra reference on the object: the list implicitly
 301  * holds that reference.
 302  */
 303 extern struct lt_elem *lt_elem_list_first(struct link_table *table, uint64_t id);
 304
 305
 306 /**
 307  * lt_elem_list_next: return the item subsequent to 'elem' in a list
 308  *
 309  * Note that this will return NULL if 'elem' is actually the end of the list.
 310  */
 311 extern struct lt_elem *lt_elem_list_next(struct link_table *table,
 312     struct lt_elem *elem);
 313
 314
 315 /**
 316  * lt_elem_list_break: break a list in two around 'elem'
 317  *
 318  * This function will reset the next_idx field of 'elem' (making it the end of
 319  * the list), and return the element subsequent to 'elem' in the list
 320  * (which could be NULL)
 321  */
 322 extern struct lt_elem *lt_elem_list_break(struct link_table *table,
 323     struct lt_elem *elem);
 324
 325
 326 /**
 327  * lt_elem_list_pop: pop an item off the head of a list
 328  *
 329  * The list head is pointed to by '*id', the element corresponding to '*id' is
 330  * returned by this function, and the new list head is returned in the in/out
 331  * parameter, '*id'.  The caller is responsible for the reference on the
 332  * returned object.  A realloc is done to reset the type of the object, but it
 333  * is still left invalid.
 334  */
 335 extern struct lt_elem *lt_elem_list_pop(struct link_table *table,
 336     uint64_t *id, int type);
 337
 338
 339 /**
 340  * lt_elem_list_release: free an entire list of reserved elements
 341  *
 342  * All elements in the list whose first member is 'head' will be released back
 343  * to 'table' as free elements. The 'type' parameter is used in development
 344  * kernels to assert that all elements on the list are of the given type.
 345  */
 346 extern int lt_elem_list_release(struct link_table *table,
 347     struct lt_elem *head,
 348     int __assert_only type);
 349
 350 static inline int
 351 lt_elem_list_release_id(struct link_table *table,
 352     uint64_t id, int type)
 353 {
 354         return lt_elem_list_release(table, lt_elem_list_first(table, id), type);
 355 }
 356
 357 #endif /* XNU_KERNEL_PRIVATE */