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

   1 #include "threads/malloc.h"
   2 #include <debug.h>
   3 #include <list.h>
   4 #include <round.h>
   5 #include <stdint.h>
   6 #include <stdio.h>
   7 #include <string.h>
   8 #include "threads/mmu.h"
   9 #include "threads/palloc.h"
  10 #include "threads/synch.h"
  11
  12 /* A simple implementation of malloc().
  13
  14    The size of each request, in bytes, is rounded up to a power
  15    of 2 and assigned to the "descriptor" that manages blocks of
  16    that size.  The descriptor keeps a list of free blocks.  If
  17    the free list is nonempty, one of its blocks is used to
  18    satisfy the request.
  19
  20    Otherwise, a new page of memory, called an "arena", is
  21    obtained from the page allocator (if none is available,
  22    malloc() returns a null pointer).  The new arena is divided
  23    into blocks, all of which are added to the descriptor's free
  24    list.  Then we return one of the new blocks.
  25
  26    When we free a block, we add it to its descriptor's free list.
  27    But if the arena that the block was in now has no in-use
  28    blocks, we remove all of the arena's blocks from the free list
  29    and give the arena back to the page allocator.
  30
  31    We can't handle blocks bigger than 2 kB using this scheme,
  32    because they're too big to fit in a single page with a
  33    descriptor.  We handle those by allocating contiguous pages
  34    with the page allocator and sticking the allocation size at
  35    the beginning of the allocated block's arena header. */
  36
  37 /* Descriptor. */
  38 struct desc
  39   {
  40     size_t block_size;          /* Size of each element in bytes. */
  41     size_t blocks_per_arena;    /* Number of blocks in an arena. */
  42     struct list free_list;      /* List of free blocks. */
  43     struct lock lock;           /* Lock. */
  44   };
  45
  46 /* Magic number for detecting arena corruption. */
  47 #define ARENA_MAGIC 0x9a548eed
  48
  49 /* Arena. */
  50 struct arena
  51   {
  52     unsigned magic;             /* Always set to ARENA_MAGIC. */
  53     struct desc *desc;          /* Owning descriptor, null for big block. */
  54     size_t free_cnt;            /* Free blocks; pages in big block. */
  55   };
  56
  57 /* Free block. */
  58 struct block
  59   {
  60     list_elem free_elem;        /* Free list element. */
  61   };
  62
  63 /* Our set of descriptors. */
  64 static struct desc descs[10];   /* Descriptors. */
  65 static size_t desc_cnt;         /* Number of descriptors. */
  66
  67 static struct arena *block_to_arena (struct block *);
  68 static struct block *arena_to_block (struct arena *, size_t idx);
  69
  70 /* Initializes the malloc() descriptors. */
  71 void
  72 malloc_init (void)
  73 {
  74   size_t block_size;
  75
  76   for (block_size = 16; block_size < PGSIZE / 2; block_size *= 2)
  77     {
  78       struct desc *d = &descs[desc_cnt++];
  79       ASSERT (desc_cnt <= sizeof descs / sizeof *descs);
  80       d->block_size = block_size;
  81       d->blocks_per_arena = (PGSIZE - sizeof (struct arena)) / block_size;
  82       list_init (&d->free_list);
  83       lock_init (&d->lock, "malloc");
  84     }
  85 }
  86
  87 /* Obtains and returns a new block of at least SIZE bytes.
  88    Returns a null pointer if memory is not available. */
  89 void *
  90 malloc (size_t size)
  91 {
  92   struct desc *d;
  93   struct block *b;
  94   struct arena *a;
  95
  96   /* A null pointer satisfies a request for 0 bytes. */
  97   if (size == 0)
  98     return NULL;
  99
 100   /* Find the smallest descriptor that satisfies a SIZE-byte
 101      request. */
 102   for (d = descs; d < descs + desc_cnt; d++)
 103     if (d->block_size >= size)
 104       break;
 105   if (d == descs + desc_cnt)
 106     {
 107       /* SIZE is too big for any descriptor.
 108          Allocate enough pages to hold SIZE plus an arena. */
 109       size_t page_cnt = DIV_ROUND_UP (size + sizeof *a, PGSIZE);
 110       a = palloc_get_multiple (0, page_cnt);
 111       if (a == NULL)
 112         return NULL;
 113
 114       /* Initialize the arena to indicate a big block of PAGE_CNT
 115          pages, and return it. */
 116       a->magic = ARENA_MAGIC;
 117       a->desc = NULL;
 118       a->free_cnt = page_cnt;
 119       return a + 1;
 120     }
 121
 122   lock_acquire (&d->lock);
 123
 124   /* If the free list is empty, create a new arena. */
 125   if (list_empty (&d->free_list))
 126     {
 127       size_t i;
 128
 129       /* Allocate a page. */
 130       a = palloc_get_page (0);
 131       if (a == NULL)
 132         {
 133           lock_release (&d->lock);
 134           return NULL;
 135         }
 136
 137       /* Initialize arena and add its blocks to the free list. */
 138       a->magic = ARENA_MAGIC;
 139       a->desc = d;
 140       a->free_cnt = d->blocks_per_arena;
 141       for (i = 0; i < d->blocks_per_arena; i++)
 142         {
 143           struct block *b = arena_to_block (a, i);
 144           list_push_back (&d->free_list, &b->free_elem);
 145         }
 146     }
 147
 148   /* Get a block from free list and return it. */
 149   b = list_entry (list_pop_front (&d->free_list), struct block, free_elem);
 150   a = block_to_arena (b);
 151   a->free_cnt--;
 152   lock_release (&d->lock);
 153   return b;
 154 }
 155
 156 /* Allocates and return A times B bytes initialized to zeroes.
 157    Returns a null pointer if memory is not available. */
 158 void *
 159 calloc (size_t a, size_t b)
 160 {
 161   void *p;
 162   size_t size;
 163
 164   /* Calculate block size. */
 165   size = a * b;
 166   if (size < a || size < b)
 167     return NULL;
 168
 169   /* Allocate and zero memory. */
 170   p = malloc (size);
 171   if (p != NULL)
 172     memset (p, 0, size);
 173
 174   return p;
 175 }
 176
 177 /* Frees block P, which must have been previously allocated with
 178    malloc() or calloc(). */
 179 void
 180 free (void *p)
 181 {
 182   struct block *b;
 183   struct arena *a;
 184   struct desc *d;
 185
 186   if (p == NULL)
 187     return;
 188
 189   b = p;
 190   a = block_to_arena (b);
 191   d = a->desc;
 192
 193   if (d == NULL)
 194     {
 195       /* It's a big block.  Free its pages. */
 196       palloc_free_multiple (a, a->free_cnt);
 197       return;
 198     }
 199
 200 #ifndef NDEBUG
 201   memset (b, 0xcd, d->block_size);
 202 #endif
 203
 204   lock_acquire (&d->lock);
 205
 206   /* Add block to free list. */
 207   list_push_front (&d->free_list, &b->free_elem);
 208
 209   /* If the arena is now entirely unused, free it. */
 210   if (++a->free_cnt >= d->blocks_per_arena)
 211     {
 212       size_t i;
 213
 214       ASSERT (a->free_cnt == d->blocks_per_arena);
 215       for (i = 0; i < d->blocks_per_arena; i++)
 216         {
 217           struct block *b = arena_to_block (a, i);
 218           list_remove (&b->free_elem);
 219         }
 220       palloc_free_page (a);
 221     }
 222
 223   lock_release (&d->lock);
 224 }
 225 \f
 226 /* Returns the arena that block B is inside. */
 227 static struct arena *
 228 block_to_arena (struct block *b)
 229 {
 230   struct arena *a = pg_round_down (b);
 231   ASSERT (a != NULL);
 232   ASSERT (a->magic == ARENA_MAGIC);
 233   return a;
 234 }
 235
 236 /* Returns the (IDX - 1)'th block within arena A. */
 237 static struct block *
 238 arena_to_block (struct arena *a, size_t idx)
 239 {
 240   ASSERT (a != NULL);
 241   ASSERT (a->magic == ARENA_MAGIC);
 242   ASSERT (idx < a->desc->blocks_per_arena);
 243   return (struct block *) ((uint8_t *) a
 244                            + sizeof *a
 245                            + idx * a->desc->block_size);
 246 }