pintos-os.org Git - pintos-anon/blob - src/threads/malloc.c

   1 #include "malloc.h"
   2 #include <stdint.h>
   3 #include "debug.h"
   4 #include "lib.h"
   5 #include "mmu.h"
   6 #include "palloc.h"
   7
   8 struct desc
   9   {
  10     size_t slot_size;           /* Size of each element in bytes. */
  11     struct slot *free_list;     /* Unused slots. */
  12     struct arena *arenas;       /* Arenas. */
  13   };
  14
  15 struct arena
  16   {
  17     struct desc *desc;          /* Owning descriptor. */
  18     struct arena *prev, *next;  /* Doubly linked list of arenas. */
  19   };
  20
  21 struct slot
  22   {
  23     struct slot *next;          /* Singly linked list of slots. */
  24   };
  25
  26 struct desc descs[16];
  27 size_t desc_cnt;
  28
  29 void
  30 malloc_init (void)
  31 {
  32   size_t slot_size;
  33
  34   for (slot_size = 16; slot_size < NBPG; slot_size *= 2)
  35     {
  36       struct desc *d = &descs[desc_cnt++];
  37       ASSERT (desc_cnt <= sizeof descs / sizeof *descs);
  38       d->slot_size = slot_size;
  39       d->free_list = NULL;
  40       d->arenas = NULL;
  41     }
  42 }
  43
  44 static struct arena *
  45 slot_to_arena (struct slot *s)
  46 {
  47   return (struct arena *) ((uint32_t) s & (NBPG - 1));
  48 }
  49
  50 static void *
  51 get_free_slot (struct desc *d)
  52 {
  53   void *block = d->free_list;
  54   ASSERT (block != NULL);
  55   d->free_list = d->free_list->next;
  56   return block;
  57 }
  58
  59 void *
  60 malloc (size_t size)
  61 {
  62   struct desc *d;
  63   struct arena *a;
  64   size_t ofs;
  65
  66   if (size == 0)
  67     return NULL;
  68
  69   for (d = descs; d < descs + desc_cnt; d++)
  70     if (size < d->slot_size)
  71       break;
  72   if (d == descs + desc_cnt)
  73     {
  74       printk ("can't malloc %zu byte object\n", size);
  75       return NULL;
  76     }
  77
  78   if (d->free_list != NULL)
  79     return get_free_slot (d);
  80
  81   a = palloc_get (0);
  82   if (a == NULL)
  83     return NULL;
  84
  85   a->desc = d;
  86   a->prev = NULL;
  87   a->next = d->arenas;
  88   if (d->arenas != NULL)
  89     d->arenas->prev = a;
  90   for (ofs = sizeof *a; ofs + d->slot_size <= NBPG; ofs += d->slot_size)
  91     {
  92       struct slot *s = (struct slot *) ((uint8_t *) a + ofs);
  93       s->next = d->free_list;
  94       d->free_list = s;
  95     }
  96
  97   return get_free_slot (d);
  98 }
  99
 100 void
 101 free (void *p)
 102 {
 103   struct slot *s = p;
 104   struct arena *a = slot_to_arena (s);
 105   struct desc *d = a->desc;
 106
 107   s->next = d->free_list;
 108   d->free_list = s;
 109 }