akaros/kern/include/slab.h
<<
>>
Prefs
   1/*
   2 * Copyright (c) 2009 The Regents of the University of California
   3 * Barret Rhoden <brho@cs.berkeley.edu>
   4 * Kevin Klues <klueska@cs.berkeley.edu>
   5 * See LICENSE for details.
   6 *
   7 * Slab allocator, based on the SunOS 5.4 allocator paper.
   8 *
   9 * There is a list of kmem_cache, which are the caches of objects of a given
  10 * size.  This list is sorted in order of size.  Each kmem_cache has three
  11 * lists of slabs: full, partial, and empty.
  12 *
  13 * For large objects, the kmem_slabs point to bufctls, which have the address
  14 * of their large buffers.  These slabs can consist of more than one contiguous
  15 * page.
  16 *
  17 * For small objects, the slabs do not use the bufctls.  Instead, they point to
  18 * the next free object in the slab.  The free objects themselves hold the
  19 * address of the next free item.  The slab structure is stored at the end of
  20 * the page.  There is only one page per slab.
  21 *
  22 * Be careful with source arenas and NOTOUCH.  If a cache's source arena is not
  23 * page-aligned memory, you need to set NOTOUCH.  Otherwise, for small objects,
  24 * a slab will be constructed that uses the source for a page of objects.
  25 */
  26
  27#pragma once
  28
  29#include <ros/common.h>
  30#include <arch/mmu.h>
  31#include <sys/queue.h>
  32#include <atomic.h>
  33#include <hash_helper.h>
  34#include <arena.h>
  35#include <trap.h>
  36
  37/* Back in the day, their cutoff for "large objects" was 512B, based on
  38 * measurements and on not wanting more than 1/8 of internal fragmentation. */
  39#define NUM_BUF_PER_SLAB 8
  40#define SLAB_LARGE_CUTOFF (PGSIZE / NUM_BUF_PER_SLAB)
  41
  42#define KMC_NAME_SZ             32
  43#define KMC_MAG_MIN_SZ          8
  44#define KMC_MAG_MAX_SZ          62      /* chosen for mag size and caching */
  45
  46/* Cache creation flags: */
  47#define KMC_NOTOUCH             0x0001  /* Can't use source/object's memory */
  48#define KMC_QCACHE              0x0002  /* Cache is an arena's qcache */
  49#define KMC_NOTRACE             0x0004  /* Do not trace allocations */
  50#define __KMC_USE_BUFCTL        0x1000  /* Internal use */
  51#define __KMC_TRACED            0x2000  /* Internal use */
  52#define __KMC_EVER_TRACED       0x3000  /* Internal use */
  53
  54struct kmem_magazine {
  55        SLIST_ENTRY(kmem_magazine)      link;
  56        unsigned int                    nr_rounds;
  57        void                            *rounds[KMC_MAG_MAX_SZ];
  58} __attribute__((aligned(ARCH_CL_SIZE)));
  59SLIST_HEAD(kmem_mag_slist, kmem_magazine);
  60
  61struct kmem_pcpu_cache {
  62        int8_t                          irq_state;
  63        unsigned int                    magsize;
  64        struct kmem_magazine            *loaded;
  65        struct kmem_magazine            *prev;
  66        size_t                          nr_allocs_ever;
  67} __attribute__((aligned(ARCH_CL_SIZE)));
  68
  69struct kmem_depot {
  70        spinlock_t                      lock;
  71        struct kmem_mag_slist           not_empty;
  72        struct kmem_mag_slist           empty;
  73        unsigned int                    magsize;
  74        unsigned int                    nr_empty;
  75        unsigned int                    nr_not_empty;
  76        unsigned int                    busy_count;
  77        uint64_t                        busy_start;
  78};
  79
  80struct kmem_slab;
  81
  82/* Control block for buffers for large-object slabs */
  83struct kmem_bufctl {
  84        SLIST_ENTRY(kmem_bufctl) link;
  85        void *buf_addr;
  86        struct kmem_slab *my_slab;
  87};
  88SLIST_HEAD(kmem_bufctl_slist, kmem_bufctl);
  89
  90/* Slabs contain the objects.  Can be either full, partial, or empty,
  91 * determined by checking the number of objects busy vs total.  For large
  92 * slabs, the bufctl list is used to find a free buffer.  For small, the void*
  93 * is used instead.*/
  94struct kmem_slab {
  95        TAILQ_ENTRY(kmem_slab) link;
  96        size_t num_busy_obj;
  97        size_t num_total_obj;
  98        void *source_obj;
  99        union {
 100                struct kmem_bufctl_slist bufctl_freelist;
 101                void *free_small_obj;
 102        };
 103};
 104TAILQ_HEAD(kmem_slab_list, kmem_slab);
 105
 106struct kmem_trace {
 107        void                            *obj;
 108        struct hlist_node               hash;
 109        size_t                          nr_pcs;
 110        uintptr_t                       pcs[MAX_BT_DEPTH];
 111        char                            str[60];
 112};
 113
 114struct kmem_trace_ht {
 115        spinlock_t                      lock;
 116        struct hash_helper              hh;
 117        struct hlist_head               *ht;
 118        struct hlist_head               static_ht[HASH_INIT_SZ];
 119};
 120
 121/* Actual cache */
 122struct kmem_cache {
 123        TAILQ_ENTRY(kmem_cache) all_kmc_link;
 124        struct kmem_pcpu_cache *pcpu_caches;
 125        struct kmem_depot depot;
 126        spinlock_t cache_lock;
 127        size_t obj_size;
 128        size_t import_amt;
 129        int align;
 130        int flags;
 131        struct arena *source;
 132        struct kmem_slab_list full_slab_list;
 133        struct kmem_slab_list partial_slab_list;
 134        struct kmem_slab_list empty_slab_list;
 135        int (*ctor)(void *obj, void *priv, int flags);
 136        void (*dtor)(void *obj, void *priv);
 137        void *priv;
 138        unsigned long nr_cur_alloc;
 139        unsigned long nr_direct_allocs_ever;
 140        struct hash_helper hh;
 141        struct kmem_bufctl_slist *alloc_hash;
 142        struct kmem_bufctl_slist static_hash[HASH_INIT_SZ];
 143        char name[KMC_NAME_SZ];
 144        TAILQ_ENTRY(kmem_cache) import_link;
 145        struct kmem_trace_ht trace_ht;
 146};
 147
 148extern struct kmem_cache_tailq all_kmem_caches;
 149
 150/* Cache management */
 151struct kmem_cache *kmem_cache_create(const char *name, size_t obj_size,
 152                                     int align, int flags,
 153                                     struct arena *source,
 154                                     int (*ctor)(void *, void *, int),
 155                                     void (*dtor)(void *, void *),
 156                                     void *priv);
 157void kmem_cache_destroy(struct kmem_cache *cp);
 158/* Front end: clients of caches use these */
 159void *kmem_cache_alloc(struct kmem_cache *cp, int flags);
 160void *kmem_cache_zalloc(struct kmem_cache *cp, int flags);
 161void kmem_cache_free(struct kmem_cache *cp, void *buf);
 162/* Back end: internal functions */
 163void kmem_cache_init(void);
 164void kmem_cache_reap(struct kmem_cache *cp);
 165unsigned int kmc_nr_pcpu_caches(void);
 166/* Low-level interface for creating/destroying; caller manages kc's memory */
 167void __kmem_cache_create(struct kmem_cache *kc, const char *name,
 168                         size_t obj_size, int align, int flags,
 169                         struct arena *source,
 170                         int (*ctor)(void *, void *, int),
 171                         void (*dtor)(void *, void *), void *priv);
 172void __kmem_cache_destroy(struct kmem_cache *cp);
 173
 174/* Tracing */
 175int kmem_trace_start(struct kmem_cache *kc);
 176void kmem_trace_stop(struct kmem_cache *kc);
 177struct sized_alloc *kmem_trace_print(struct kmem_cache *kc);
 178void kmem_trace_reset(struct kmem_cache *kc);
 179