kern/include/arena.h

   1 /* Copyright (c) 2016 Google Inc
   2  * Barret Rhoden <brho@cs.berkeley.edu>
   3  * See LICENSE for details.
   4  *
   5  * Arena resource allocator, based on Bonwick and Adams's "Magazines and Vmem:
   6  * Extending the Slab Allocator to Many CPUs and Arbitrary Resources". */
   7
   8 #pragma once
   9
  10 #include <sys/queue.h>
  11 #include <atomic.h>
  12 #include <rbtree.h>
  13 #include <hash_helper.h>
  14
  15 /* Boundary tags track segments.  All segments, regardless of allocation status,
  16  * are on the all_segs list.  BTs are on other lists, depending on their status.
  17  * There is a list of unused BTs (those not in use by the arena), lists of free
  18  * segments (the power-of-two lists in the array), and lists of allocated BTs in
  19  * the hash table.
  20  *
  21  * BTs also track 'spans', which are contig segments that were allocated from a
  22  * source arena.  SPANS are never merged with adjacent BTs, and they come before
  23  * the ALLOC BTs that track the segments inside the span.  An entire span is
  24  * returned to its source when all of its entries are freed (policy, up for
  25  * debate/modification).  Spans are not on a free, unused, or hash list. */
  26 typedef enum {
  27         BTAG_FREE,
  28         BTAG_ALLOC,
  29         BTAG_SPAN,
  30 } btag_status_t;
  31
  32 struct btag {
  33         struct rb_node                          all_link;       /* connects all non-free BTs */
  34         BSD_LIST_ENTRY(btag)            misc_link;      /* freelist, unused, or hash */
  35         uintptr_t                                       start;
  36         size_t                                          size;
  37         btag_status_t                           status;
  38 };
  39 BSD_LIST_HEAD(btag_list, btag);
  40
  41 /* 64 is the most powers of two we can express with 64 bits. */
  42 #define ARENA_NR_FREE_LISTS             64
  43 #define ARENA_NAME_SZ                   32
  44
  45 /* The arena maintains an in-order list of all segments, allocated or otherwise.
  46  * All free segments are on one of the free_segs[] lists.  There is one list for
  47  * each power-of-two we can allocate. */
  48 struct arena {
  49         spinlock_t                                      lock;
  50         uint8_t                                         import_scale;
  51         bool                                            is_base;
  52         size_t                                          quantum;
  53         size_t                                          qcache_max;
  54         struct kmem_cache                       *qcaches;
  55         struct rb_root                          all_segs;               /* BTs, using all_link */
  56         struct btag_list                        unused_btags;   /* BTs, using misc_link */
  57         struct btag_list                        *alloc_hash;    /* BTs, using misc_link */
  58         struct hash_helper                      hh;
  59         void *(*afunc)(struct arena *, size_t, int);
  60         void (*ffunc)(struct arena *, void *, size_t);
  61         struct arena                            *source;
  62         size_t                                          amt_total_segs; /* Does not include qcache */
  63         size_t                                          amt_alloc_segs;
  64         size_t                                          nr_allocs_ever;
  65         uintptr_t                                       last_nextfit_alloc;
  66         struct btag_list                        free_segs[ARENA_NR_FREE_LISTS];
  67         struct btag_list                        static_hash[HASH_INIT_SZ];
  68
  69         /* Accounting */
  70         char                                            name[ARENA_NAME_SZ];
  71         TAILQ_ENTRY(arena)                      next;
  72 };
  73
  74 /* Arena allocation styles, or'd with MEM_FLAGS */
  75 #define ARENA_BESTFIT                   0x100
  76 #define ARENA_INSTANTFIT                0x200
  77 #define ARENA_NEXTFIT                   0x400
  78 #define ARENA_ALLOC_STYLES (ARENA_BESTFIT | ARENA_INSTANTFIT | ARENA_NEXTFIT)
  79
  80 /* Creates an area, with initial segment [@base, @base + @size).  Allocs are in
  81  * units of @quantum.  If @source is provided, the arena will alloc new segments
  82  * from @source, calling @afunc to alloc and @ffunc to free.  Uses a slab
  83  * allocator for allocations up to @qcache_max (0 = no caching). */
  84 struct arena *arena_create(char *name, void *base, size_t size, size_t quantum,
  85                            void *(*afunc)(struct arena *, size_t, int),
  86                            void (*ffunc)(struct arena *, void *, size_t),
  87                            struct arena *source, size_t qcache_max, int flags);
  88 /* Adds segment [@base, @base + @size) to @arena. */
  89 void *arena_add(struct arena *arena, void *base, size_t size, int flags);
  90 void arena_destroy(struct arena *arena);
  91
  92 void *arena_alloc(struct arena *arena, size_t size, int flags);
  93 void arena_free(struct arena *arena, void *addr, size_t size);
  94 void *arena_xalloc(struct arena *arena, size_t size, size_t align, size_t phase,
  95                    size_t nocross, void *minaddr, void *maxaddr, int flags);
  96 void arena_xfree(struct arena *arena, void *addr, size_t size);
  97
  98 size_t arena_amt_free(struct arena *arena);
  99 size_t arena_amt_total(struct arena *arena);
 100
 101 /* Low-level memory allocator intefaces */
 102 extern struct arena *base_arena;
 103 extern struct arena *kpages_arena;
 104 struct arena *arena_builder(void *pgaddr, char *name, size_t quantum,
 105                             void *(*afunc)(struct arena *, size_t, int),
 106                             void (*ffunc)(struct arena *, void *, size_t),
 107                             struct arena *source, size_t qcache_max);
 108 /* Allocate directly from the nearest base allocator.  Used by other mm code.
 109  * Pass in your closest arena (such as your source) to help us find a base. */
 110 void *base_alloc(struct arena *guess, size_t size, int flags);
 111 void *base_zalloc(struct arena *guess, size_t size, int flags);
 112 void base_free(struct arena *guess, void *addr, size_t size);