c_cpp/lib/klib/kalloc.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include "kalloc.h"
   5
   6 /* In kalloc, a *core* is a large chunk of contiguous memory. Each core is
   7  * associated with a master header, which keeps the size of the current core
   8  * and the pointer to next core. Kalloc allocates small *blocks* of memory from
   9  * the cores and organizes free memory blocks in a circular single-linked list.
  10  *
  11  * In the following diagram, "@" stands for the header of a free block (of type
  12  * header_t), "#" for the header of an allocated block (of type size_t), "-"
  13  * for free memory, and "+" for allocated memory.
  14  *
  15  * master        This region is core 1.          master           This region is core 2.
  16  *      |                                             |
  17  *      *@-------#++++++#++++++++++++@--------        *@----------#++++++++++++#+++++++@------------
  18  *       |                           |                 |                               |
  19  *       p=p->ptr->ptr->ptr->ptr     p->ptr            p->ptr->ptr                     p->ptr->ptr->ptr
  20  */
  21
  22 #define MIN_CORE_SIZE 0x80000
  23
  24 typedef struct header_t {
  25         size_t size;
  26         struct header_t *ptr;
  27 } header_t;
  28
  29 typedef struct {
  30         header_t base, *loop_head, *core_head; /* base is a zero-sized block always kept in the loop */
  31 } kmem_t;
  32
  33 static void panic(const char *s)
  34 {
  35         fprintf(stderr, "%s\n", s);
  36         abort();
  37 }
  38
  39 void *km_init(void)
  40 {
  41         return calloc(1, sizeof(kmem_t));
  42 }
  43
  44 void km_destroy(void *_km)
  45 {
  46         kmem_t *km = (kmem_t*)_km;
  47         header_t *p, *q;
  48         if (km == NULL) return;
  49         for (p = km->core_head; p != NULL;) {
  50                 q = p->ptr;
  51                 free(p);
  52                 p = q;
  53         }
  54         free(km);
  55 }
  56
  57 static header_t *morecore(kmem_t *km, size_t nu)
  58 {
  59         header_t *q;
  60         size_t bytes, *p;
  61         nu = (nu + 1 + (MIN_CORE_SIZE - 1)) / MIN_CORE_SIZE * MIN_CORE_SIZE; /* the first +1 for core header */
  62         bytes = nu * sizeof(header_t);
  63         q = (header_t*)malloc(bytes);
  64         if (!q) panic("[morecore] insufficient memory");
  65         q->ptr = km->core_head, q->size = nu, km->core_head = q;
  66         p = (size_t*)(q + 1);
  67         *p = nu - 1; /* the size of the free block; -1 because the first unit is used for the core header */
  68         kfree(km, p + 1); /* initialize the new "core"; NB: the core header is not looped. */
  69         return km->loop_head;
  70 }
  71
  72 void kfree(void *_km, void *ap) /* kfree() also adds a new core to the circular list */
  73 {
  74         header_t *p, *q;
  75         kmem_t *km = (kmem_t*)_km;
  76
  77         if (!ap) return;
  78         if (km == NULL) {
  79                 free(ap);
  80                 return;
  81         }
  82         p = (header_t*)((size_t*)ap - 1);
  83         p->size = *((size_t*)ap - 1);
  84         /* Find the pointer that points to the block to be freed. The following loop can stop on two conditions:
  85          *
  86          * a) "p>q && p<q->ptr": @------#++++++++#+++++++@-------    @---------------#+++++++@-------
  87          *    (can also be in    |      |                |        -> |                       |
  88          *     two cores)        q      p           q->ptr           q                  q->ptr
  89          *
  90          *                       @--------    #+++++++++@--------    @--------    @------------------
  91          *                       |            |         |         -> |            |
  92          *                       q            p    q->ptr            q       q->ptr
  93          *
  94          * b) "q>=q->ptr && (p>q || p<q->ptr)":  @-------#+++++   @--------#+++++++     @-------#+++++   @----------------
  95          *                                       |                |        |         -> |                |
  96          *                                  q->ptr                q        p       q->ptr                q
  97          *
  98          *                                       #+++++++@-----   #++++++++@-------     @-------------   #++++++++@-------
  99          *                                       |       |                 |         -> |                         |
 100          *                                       p  q->ptr                 q       q->ptr                         q
 101          */
 102         for (q = km->loop_head; !(p > q && p < q->ptr); q = q->ptr)
 103                 if (q >= q->ptr && (p > q || p < q->ptr)) break;
 104         if (p + p->size == q->ptr) { /* two adjacent blocks, merge p and q->ptr (the 2nd and 4th cases) */
 105                 p->size += q->ptr->size;
 106                 p->ptr = q->ptr->ptr;
 107         } else if (p + p->size > q->ptr && q->ptr >= p) {
 108                 panic("[kfree] The end of the allocated block enters a free block.");
 109         } else p->ptr = q->ptr; /* backup q->ptr */
 110
 111         if (q + q->size == p) { /* two adjacent blocks, merge q and p (the other two cases) */
 112                 q->size += p->size;
 113                 q->ptr = p->ptr;
 114                 km->loop_head = q;
 115         } else if (q + q->size > p && p >= q) {
 116                 panic("[kfree] The end of a free block enters the allocated block.");
 117         } else km->loop_head = p, q->ptr = p; /* in two cores, cannot be merged; create a new block in the list */
 118 }
 119
 120 void *kmalloc(void *_km, size_t n_bytes)
 121 {
 122         kmem_t *km = (kmem_t*)_km;
 123         size_t n_units;
 124         header_t *p, *q;
 125
 126         if (n_bytes == 0) return 0;
 127         if (km == NULL) return malloc(n_bytes);
 128         n_units = (n_bytes + sizeof(size_t) + sizeof(header_t) - 1) / sizeof(header_t) + 1;
 129
 130         if (!(q = km->loop_head)) /* the first time when kmalloc() is called, intialize it */
 131                 q = km->loop_head = km->base.ptr = &km->base;
 132         for (p = q->ptr;; q = p, p = p->ptr) { /* search for a suitable block */
 133                 if (p->size >= n_units) { /* p->size if the size of current block. This line means the current block is large enough. */
 134                         if (p->size == n_units) q->ptr = p->ptr; /* no need to split the block */
 135                         else { /* split the block. NB: memory is allocated at the end of the block! */
 136                                 p->size -= n_units; /* reduce the size of the free block */
 137                                 p += p->size; /* p points to the allocated block */
 138                                 *(size_t*)p = n_units; /* set the size */
 139                         }
 140                         km->loop_head = q; /* set the end of chain */
 141                         return (size_t*)p + 1;
 142                 }
 143                 if (p == km->loop_head) { /* then ask for more "cores" */
 144                         if ((p = morecore(km, n_units)) == 0) return 0;
 145                 }
 146         }
 147 }
 148
 149 void *kcalloc(void *_km, size_t count, size_t size)
 150 {
 151         kmem_t *km = (kmem_t*)_km;
 152         void *p;
 153         if (size == 0 || count == 0) return 0;
 154         if (km == NULL) return calloc(count, size);
 155         p = kmalloc(km, count * size);
 156         memset(p, 0, count * size);
 157         return p;
 158 }
 159
 160 void *krealloc(void *_km, void *ap, size_t n_bytes) // TODO: this can be made more efficient in principle
 161 {
 162         kmem_t *km = (kmem_t*)_km;
 163         size_t n_units, *p, *q;
 164
 165         if (n_bytes == 0) {
 166                 kfree(km, ap); return 0;
 167         }
 168         if (km == NULL) return realloc(ap, n_bytes);
 169         if (ap == NULL) return kmalloc(km, n_bytes);
 170         n_units = (n_bytes + sizeof(size_t) + sizeof(header_t) - 1) / sizeof(header_t);
 171         p = (size_t*)ap - 1;
 172         if (*p >= n_units) return ap; /* TODO: this prevents shrinking */
 173         q = (size_t*)kmalloc(km, n_bytes);
 174         memcpy(q, ap, (*p - 1) * sizeof(header_t));
 175         kfree(km, ap);
 176         return q;
 177 }
 178
 179 void km_stat(const void *_km, km_stat_t *s)
 180 {
 181         kmem_t *km = (kmem_t*)_km;
 182         header_t *p;
 183         memset(s, 0, sizeof(km_stat_t));
 184         if (km == NULL || km->loop_head == NULL) return;
 185         for (p = km->loop_head;; p = p->ptr) {
 186                 s->available += p->size * sizeof(header_t);
 187                 if (p->size != 0) ++s->n_blocks; /* &kmem_t::base is always one of the cores. It is zero-sized. */
 188                 if (p->ptr > p && p + p->size > p->ptr)
 189                         panic("[km_stat] The end of a free block enters another free block.");
 190                 if (p->ptr == km->loop_head) break;
 191         }
 192         for (p = km->core_head; p != NULL; p = p->ptr) {
 193                 size_t size = p->size * sizeof(header_t);
 194                 ++s->n_cores;
 195                 s->capacity += size;
 196                 s->largest = s->largest > size? s->largest : size;
 197         }
 198 }