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  * 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 */