bsd/sys/mcache.h

   1 /*
   2  * Copyright (c) 2006-2017 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 #ifndef _SYS_MCACHE_H
  29 #define _SYS_MCACHE_H
  30
  31 #ifdef KERNEL_PRIVATE
  32
  33 #ifdef  __cplusplus
  34 extern "C" {
  35 #endif
  36
  37 #include <sys/types.h>
  38 #include <sys/queue.h>
  39 #include <mach/boolean.h>
  40 #include <mach/branch_predicates.h>
  41 #include <kern/locks.h>
  42 #include <libkern/OSAtomic.h>
  43
  44 #ifdef ASSERT
  45 #undef ASSERT
  46 #endif
  47
  48 #ifdef VERIFY
  49 #undef VERIFY
  50 #endif
  51
  52 /*
  53  * Unlike VERIFY(), ASSERT() is evaluated only in DEBUG/DEVELOPMENT build.
  54  */
  55 #define VERIFY(EX)      \
  56         ((void)(__probable((EX)) || assfail(#EX, __FILE__, __LINE__)))
  57 #if (DEBUG || DEVELOPMENT)
  58 #define ASSERT(EX)      VERIFY(EX)
  59 #else
  60 #define ASSERT(EX)      ((void)0)
  61 #endif
  62
  63 /*
  64  * Compile time assert; this should be on its own someday.
  65  */
  66 #define _CASSERT(x)     _Static_assert(x, "compile-time assertion failed")
  67
  68 /*
  69  * Atomic macros; these should be on their own someday.
  70  */
  71 #define atomic_add_16_ov(a, n)                                          \
  72         ((u_int16_t) OSAddAtomic16(n, (volatile SInt16 *)a))
  73
  74 #define atomic_add_16(a, n)                                             \
  75         ((void) atomic_add_16_ov(a, n))
  76
  77 #define atomic_add_32_ov(a, n)                                          \
  78         ((u_int32_t) OSAddAtomic(n, (volatile SInt32 *)a))
  79
  80 #define atomic_add_32(a, n)                                             \
  81         ((void) atomic_add_32_ov(a, n))
  82
  83 #define atomic_add_64_ov(a, n)                                          \
  84         ((u_int64_t) OSAddAtomic64(n, (volatile SInt64 *)a))
  85
  86 #define atomic_add_64(a, n)                                             \
  87         ((void) atomic_add_64_ov(a, n))
  88
  89 #define atomic_test_set_32(a, o, n)                                     \
  90         OSCompareAndSwap(o, n, (volatile UInt32 *)a)
  91
  92 #define atomic_set_32(a, n) do {                                        \
  93         while (!atomic_test_set_32(a, *a, n))                           \
  94                 ;                                                       \
  95 } while (0)
  96
  97 #define atomic_test_set_64(a, o, n)                                     \
  98         OSCompareAndSwap64(o, n, (volatile UInt64 *)a)
  99
 100 #define atomic_set_64(a, n) do {                                        \
 101         while (!atomic_test_set_64(a, *a, n))                           \
 102                 ;                                                       \
 103 } while (0)
 104
 105 #if defined(__LP64__)
 106 #define atomic_get_64(n, a) do {                                        \
 107         (n) = *(a);                                                     \
 108 } while (0)
 109 #else
 110 #define atomic_get_64(n, a) do {                                        \
 111         (n) = atomic_add_64_ov(a, 0);                                   \
 112 } while (0)
 113 #endif /* __LP64__ */
 114
 115 #define atomic_test_set_ptr(a, o, n)                                    \
 116         OSCompareAndSwapPtr(o, n, (void * volatile *)a)
 117
 118 #define atomic_set_ptr(a, n) do {                                       \
 119         while (!atomic_test_set_ptr(a, *a, n))                          \
 120                 ;                                                       \
 121 } while (0)
 122
 123 #define atomic_or_8_ov(a, n)                                            \
 124         ((u_int8_t) OSBitOrAtomic8(n, (volatile UInt8 *)a))
 125
 126 #define atomic_or_8(a, n)                                               \
 127         ((void) atomic_or_8_ov(a, n))
 128
 129 #define atomic_bitset_8(a, n)                                           \
 130         atomic_or_8(a, n)
 131
 132 #define atomic_or_16_ov(a, n)                                           \
 133         ((u_int16_t) OSBitOrAtomic16(n, (volatile UInt16 *)a))
 134
 135 #define atomic_or_16(a, n)                                              \
 136         ((void) atomic_or_16_ov(a, n))
 137
 138 #define atomic_bitset_16(a, n)                                          \
 139         atomic_or_16(a, n)
 140
 141 #define atomic_or_32_ov(a, n)                                           \
 142         ((u_int32_t) OSBitOrAtomic(n, (volatile UInt32 *)a))
 143
 144 #define atomic_or_32(a, n)                                              \
 145         ((void) atomic_or_32_ov(a, n))
 146
 147 #define atomic_bitset_32(a, n)                                          \
 148         atomic_or_32(a, n)
 149
 150 #define atomic_bitset_32_ov(a, n)                                       \
 151         atomic_or_32_ov(a, n)
 152
 153 #define atomic_and_8_ov(a, n)                                           \
 154         ((u_int8_t) OSBitAndAtomic8(n, (volatile UInt8 *)a))
 155
 156 #define atomic_and_8(a, n)                                              \
 157         ((void) atomic_and_8_ov(a, n))
 158
 159 #define atomic_bitclear_8(a, n)                                         \
 160         atomic_and_8(a, ~(n))
 161
 162 #define atomic_and_16_ov(a, n)                                          \
 163         ((u_int16_t) OSBitAndAtomic16(n, (volatile UInt16 *)a))
 164
 165 #define atomic_and_16(a, n)                                             \
 166         ((void) atomic_and_16_ov(a, n))
 167
 168 #define atomic_bitclear_16(a, n)                                        \
 169         atomic_and_16(a, ~(n))
 170
 171 #define atomic_and_32_ov(a, n)                                          \
 172         ((u_int32_t) OSBitAndAtomic(n, (volatile UInt32 *)a))
 173
 174 #define atomic_and_32(a, n)                                             \
 175         ((void) atomic_and_32_ov(a, n))
 176
 177 #define atomic_bitclear_32(a, n)                                        \
 178         atomic_and_32(a, ~(n))
 179
 180 #define membar_sync     OSMemoryBarrier
 181
 182 /*
 183  * Use CPU_CACHE_LINE_SIZE instead of MAX_CPU_CACHE_LINE_SIZE, unless
 184  * wasting space is of no concern.
 185  */
 186 #define MAX_CPU_CACHE_LINE_SIZE 128
 187 #define CPU_CACHE_LINE_SIZE     mcache_cache_line_size()
 188
 189 #ifndef IS_P2ALIGNED
 190 #define IS_P2ALIGNED(v, a) \
 191         ((((uintptr_t)(v)) & ((uintptr_t)(a) - 1)) == 0)
 192 #endif /* IS_P2ALIGNED */
 193
 194 #ifndef P2ROUNDUP
 195 #define P2ROUNDUP(x, align) \
 196         (-(-((uintptr_t)(x)) & -((uintptr_t)align)))
 197 #endif /* P2ROUNDUP */
 198
 199 #ifndef P2ROUNDDOWN
 200 #define P2ROUNDDOWN(x, align) \
 201         (((uintptr_t)(x)) & ~((uintptr_t)(align) - 1))
 202 #endif /* P2ROUNDDOWN */
 203
 204 #ifndef P2ALIGN
 205 #define P2ALIGN(x, align) \
 206         ((uintptr_t)(x) & -((uintptr_t)(align)))
 207 #endif /* P2ALIGN */
 208
 209 #define MCACHE_FREE_PATTERN             0xdeadbeefdeadbeefULL
 210 #define MCACHE_UNINITIALIZED_PATTERN    0xbaddcafebaddcafeULL
 211
 212 /*
 213  * mcache allocation request flags.
 214  *
 215  * MCR_NOSLEEP and MCR_FAILOK are mutually exclusive.  The latter is used
 216  * by the mbuf allocator to handle the implementation of several caches that
 217  * involve multiple layers of mcache.  It implies a best effort blocking
 218  * allocation request; if the request cannot be satisfied, the caller will
 219  * be blocked until further notice, similar to MCR_SLEEP, except that upon
 220  * a wake up it will return immediately to the caller regardless of whether
 221  * the request can been fulfilled.
 222  *
 223  * MCR_TRYHARD implies a non-blocking allocation request, regardless of
 224  * whether MCR_NOSLEEP is set.  It informs the allocator that the request
 225  * should not cause the calling thread to block, and that it must have
 226  * exhausted all possible schemes to fulfill the request, including doing
 227  * reclaims and/or purges, before returning to the caller.
 228  *
 229  * Regular mcache clients should only use MCR_SLEEP or MCR_NOSLEEP.
 230  */
 231 #define MCR_SLEEP       0x0000          /* same as M_WAITOK */
 232 #define MCR_NOSLEEP     0x0001          /* same as M_NOWAIT */
 233 #define MCR_FAILOK      0x0100          /* private, for internal use only */
 234 #define MCR_TRYHARD     0x0200          /* private, for internal use only */
 235 #define MCR_USR1        0x1000          /* private, for internal use only */
 236
 237 #define MCR_NONBLOCKING (MCR_NOSLEEP | MCR_FAILOK | MCR_TRYHARD)
 238
 239 /*
 240  * Generic one-way linked list element structure.  This is used to handle
 241  * mcache_alloc_ext() requests in order to chain the allocated objects
 242  * together before returning them to the caller.
 243  */
 244 typedef struct mcache_obj {
 245         struct mcache_obj       *obj_next;
 246 } mcache_obj_t;
 247
 248 typedef struct mcache_bkt {
 249         void            *bkt_next;      /* next bucket in list */
 250         void            *bkt_obj[1];    /* one or more objects */
 251 } mcache_bkt_t;
 252
 253 typedef struct mcache_bktlist {
 254         mcache_bkt_t    *bl_list;       /* bucket list */
 255         u_int32_t       bl_total;       /* number of buckets */
 256         u_int32_t       bl_min;         /* min since last update */
 257         u_int32_t       bl_reaplimit;   /* max reapable buckets */
 258         u_int64_t       bl_alloc;       /* allocations from this list */
 259 } mcache_bktlist_t;
 260
 261 typedef struct mcache_bkttype {
 262         int             bt_bktsize;     /* bucket size (number of elements) */
 263         size_t          bt_minbuf;      /* all smaller buffers qualify */
 264         size_t          bt_maxbuf;      /* no larger bfufers qualify */
 265         struct mcache   *bt_cache;      /* bucket cache */
 266 } mcache_bkttype_t;
 267
 268 typedef struct mcache_cpu {
 269         decl_lck_mtx_data(, cc_lock);
 270         mcache_bkt_t    *cc_filled;     /* the currently filled bucket */
 271         mcache_bkt_t    *cc_pfilled;    /* the previously filled bucket */
 272         u_int64_t       cc_alloc;       /* allocations from this cpu */
 273         u_int64_t       cc_free;        /* frees to this cpu */
 274         int             cc_objs;        /* number of objects in filled bkt */
 275         int             cc_pobjs;       /* number of objects in previous bkt */
 276         int             cc_bktsize;     /* number of elements in a full bkt */
 277 } __attribute__((aligned(MAX_CPU_CACHE_LINE_SIZE))) mcache_cpu_t;
 278
 279 typedef unsigned int (*mcache_allocfn_t)(void *, mcache_obj_t ***,
 280     unsigned int, int);
 281 typedef void (*mcache_freefn_t)(void *, mcache_obj_t *, boolean_t);
 282 typedef void (*mcache_auditfn_t)(void *, mcache_obj_t *, boolean_t);
 283 typedef void (*mcache_logfn_t)(u_int32_t, mcache_obj_t *, boolean_t);
 284 typedef void (*mcache_notifyfn_t)(void *, u_int32_t);
 285
 286 typedef struct mcache {
 287         /*
 288          * Cache properties
 289          */
 290         LIST_ENTRY(mcache) mc_list;     /* cache linkage */
 291         char            mc_name[32];    /* cache name */
 292         struct zone     *mc_slab_zone;  /* backend zone allocator */
 293         mcache_allocfn_t mc_slab_alloc; /* slab layer allocate callback */
 294         mcache_freefn_t mc_slab_free;   /* slab layer free callback */
 295         mcache_auditfn_t mc_slab_audit; /* slab layer audit callback */
 296         mcache_logfn_t mc_slab_log;     /* slab layer log callback */
 297         mcache_notifyfn_t mc_slab_notify; /* slab layer notify callback */
 298         void            *mc_private;    /* opaque arg to callbacks */
 299         size_t          mc_bufsize;     /* object size */
 300         size_t          mc_align;       /* object alignment */
 301         u_int32_t       mc_flags;       /* cache creation flags */
 302         u_int32_t       mc_purge_cnt;   /* # of purges requested by slab */
 303         u_int32_t       mc_enable_cnt;  /* # of reenables due to purges */
 304         u_int32_t       mc_waiter_cnt;  /* # of slab layer waiters */
 305         u_int32_t       mc_wretry_cnt;  /* # of wait retries */
 306         u_int32_t       mc_nwretry_cnt; /* # of no-wait retry attempts */
 307         u_int32_t       mc_nwfail_cnt;  /* # of no-wait retries that failed */
 308         decl_lck_mtx_data(, mc_sync_lock); /* protects purges and reenables */
 309         lck_attr_t      *mc_sync_lock_attr;
 310         lck_grp_t       *mc_sync_lock_grp;
 311         lck_grp_attr_t  *mc_sync_lock_grp_attr;
 312         /*
 313          * Keep CPU and buckets layers lock statistics separate.
 314          */
 315         lck_attr_t      *mc_cpu_lock_attr;
 316         lck_grp_t       *mc_cpu_lock_grp;
 317         lck_grp_attr_t  *mc_cpu_lock_grp_attr;
 318
 319         /*
 320          * Bucket layer common to all CPUs
 321          */
 322         decl_lck_mtx_data(, mc_bkt_lock);
 323         lck_attr_t      *mc_bkt_lock_attr;
 324         lck_grp_t       *mc_bkt_lock_grp;
 325         lck_grp_attr_t  *mc_bkt_lock_grp_attr;
 326         mcache_bkttype_t *cache_bkttype;        /* bucket type */
 327         mcache_bktlist_t mc_full;               /* full buckets */
 328         mcache_bktlist_t mc_empty;              /* empty buckets */
 329         size_t          mc_chunksize;           /* bufsize + alignment */
 330         u_int32_t       mc_bkt_contention;      /* lock contention count */
 331         u_int32_t       mc_bkt_contention_prev; /* previous snapshot */
 332
 333         /*
 334          * Per-CPU layer, aligned at cache line boundary
 335          */
 336         mcache_cpu_t    mc_cpu[1]
 337             __attribute__((aligned(MAX_CPU_CACHE_LINE_SIZE)));
 338 } mcache_t;
 339
 340 #define MCACHE_ALIGN    8       /* default guaranteed alignment */
 341
 342 /* Valid values for mc_flags */
 343 #define MCF_VERIFY      0x00000001      /* enable verification */
 344 #define MCF_TRACE       0x00000002      /* enable transaction auditing */
 345 #define MCF_NOCPUCACHE  0x00000010      /* disable CPU layer caching */
 346 #define MCF_NOLEAKLOG   0x00000100      /* disable leak logging */
 347 #define MCF_EXPLEAKLOG  0x00000200      /* expose leak info to user space */
 348
 349 #define MCF_DEBUG       (MCF_VERIFY | MCF_TRACE)
 350 #define MCF_FLAGS_MASK  \
 351         (MCF_DEBUG | MCF_NOCPUCACHE | MCF_NOLEAKLOG | MCF_EXPLEAKLOG)
 352
 353 /* Valid values for notify callback */
 354 #define MCN_RETRYALLOC  0x00000001      /* Allocation should be retried */
 355
 356 #define MCACHE_STACK_DEPTH 16
 357
 358 #define MCA_TRN_MAX     2               /* Number of transactions to record */
 359
 360 typedef struct mcache_audit {
 361         struct mcache_audit *mca_next;  /* next audit struct */
 362         void            *mca_addr;      /* address of buffer */
 363         mcache_t        *mca_cache;     /* parent cache of the buffer */
 364         size_t          mca_contents_size; /* size of saved contents */
 365         void            *mca_contents;  /* user-specific saved contents */
 366         void            *mca_uptr;      /* user-specific pointer */
 367         uint32_t        mca_uflags;     /* user-specific flags */
 368         uint32_t        mca_next_trn;
 369         struct mca_trn {
 370                 struct thread   *mca_thread;    /* thread doing transaction */
 371                 uint32_t        mca_tstamp;
 372                 uint16_t        mca_depth;
 373                 void            *mca_stack[MCACHE_STACK_DEPTH];
 374         } mca_trns[MCA_TRN_MAX];
 375 } mcache_audit_t;
 376
 377 __private_extern__ int assfail(const char *, const char *, int);
 378 __private_extern__ void mcache_init(void);
 379 __private_extern__ unsigned int mcache_getflags(void);
 380 __private_extern__ unsigned int mcache_cache_line_size(void);
 381 __private_extern__ mcache_t *mcache_create(const char *, size_t,
 382     size_t, u_int32_t, int);
 383 __private_extern__ void *mcache_alloc(mcache_t *, int);
 384 __private_extern__ void mcache_free(mcache_t *, void *);
 385 __private_extern__ mcache_t *mcache_create_ext(const char *, size_t,
 386     mcache_allocfn_t, mcache_freefn_t, mcache_auditfn_t, mcache_logfn_t,
 387     mcache_notifyfn_t, void *, u_int32_t, int);
 388 __private_extern__ void mcache_destroy(mcache_t *);
 389 __private_extern__ unsigned int mcache_alloc_ext(mcache_t *, mcache_obj_t **,
 390     unsigned int, int);
 391 __private_extern__ void mcache_free_ext(mcache_t *, mcache_obj_t *);
 392 __private_extern__ void mcache_reap(void);
 393 __private_extern__ void mcache_reap_now(mcache_t *, boolean_t);
 394 __private_extern__ boolean_t mcache_purge_cache(mcache_t *, boolean_t);
 395 __private_extern__ void mcache_waiter_inc(mcache_t *);
 396 __private_extern__ void mcache_waiter_dec(mcache_t *);
 397 __private_extern__ boolean_t mcache_bkt_isempty(mcache_t *);
 398
 399 __private_extern__ void mcache_buffer_log(mcache_audit_t *, void *, mcache_t *,
 400     struct timeval *);
 401 __private_extern__ void mcache_set_pattern(u_int64_t, void *, size_t);
 402 __private_extern__ void *mcache_verify_pattern(u_int64_t, void *, size_t);
 403 __private_extern__ void *mcache_verify_set_pattern(u_int64_t, u_int64_t,
 404     void *, size_t);
 405 __private_extern__ void mcache_audit_free_verify(mcache_audit_t *,
 406     void *, size_t, size_t);
 407 __private_extern__ void mcache_audit_free_verify_set(mcache_audit_t *,
 408     void *, size_t, size_t);
 409 __private_extern__ char *mcache_dump_mca(mcache_audit_t *);
 410 __private_extern__ void mcache_audit_panic(mcache_audit_t *, void *, size_t,
 411     int64_t, int64_t);
 412
 413 extern int32_t total_sbmb_cnt;
 414 extern int32_t total_sbmb_cnt_floor;
 415 extern int32_t total_sbmb_cnt_peak;
 416 extern int64_t sbmb_limreached;
 417 extern mcache_t *mcache_audit_cache;
 418
 419 #ifdef  __cplusplus
 420 }
 421 #endif
 422
 423 #endif /* KERNEL_PRIVATE */
 424
 425 #endif /* _SYS_MCACHE_H */