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 /* Obtains and returns a new block of at least SIZE bytes.
 157    Panics if memory is not available.  It is unacceptable for the
 158    kernel to panic in normal operation, so this function should
 159    only be used during kernel initialization. */
 160 void *
 161 malloc_or_panic (size_t size)
 162 {
 163   void *p = malloc (size);
 164   if (p == NULL && size > 0)
 165     PANIC ("memory exhausted");
 166   return p;
 167 }
 168
 169 /* Allocates and return A times B bytes initialized to zeroes.
 170    Returns a null pointer if memory is not available. */
 171 void *
 172 calloc (size_t a, size_t b)
 173 {
 174   void *p;
 175   size_t size;
 176
 177   /* Calculate block size and make sure it fits in size_t. */
 178   size = a * b;
 179   if (size < a || size < b)
 180     return NULL;
 181
 182   /* Allocate and zero memory. */
 183   p = malloc (size);
 184   if (p != NULL)
 185     memset (p, 0, size);
 186
 187   return p;
 188 }
 189
 190 /* Allocates and return A times B bytes initialized to zeroes.
 191    Panics if memory is not available.  It is unacceptable for the
 192    kernel to panic in normal operation, so this function should
 193    only be used during kernel initialization. */
 194 void *
 195 calloc_or_panic (size_t a, size_t b)
 196 {
 197   void *p = calloc (a, b);
 198   if (p == NULL && a > 0 && b > 0)
 199     PANIC ("memory exhausted");
 200   return p;
 201 }
 202
 203 /* Frees block P, which must have been previously allocated with
 204    malloc() or calloc(). */
 205 void
 206 free (void *p)
 207 {
 208   struct block *b;
 209   struct arena *a;
 210   struct desc *d;
 211
 212   if (p == NULL)
 213     return;
 214
 215   b = p;
 216   a = block_to_arena (b);
 217   d = a->desc;
 218
 219   if (d == NULL)
 220     {
 221       /* It's a big block.  Free its pages. */
 222       palloc_free_multiple (a, a->free_cnt);
 223       return;
 224     }
 225
 226 #ifndef NDEBUG
 227   memset (b, 0xcc, d->block_size);
 228 #endif
 229
 230   lock_acquire (&d->lock);
 231
 232   /* Add block to free list. */
 233   list_push_front (&d->free_list, &b->free_elem);
 234
 235   /* If the arena is now entirely unused, free it. */
 236   if (++a->free_cnt >= d->blocks_per_arena)
 237     {
 238       size_t i;
 239
 240       ASSERT (a->free_cnt == d->blocks_per_arena);
 241       for (i = 0; i < d->blocks_per_arena; i++)
 242         {
 243           struct block *b = arena_to_block (a, i);
 244           list_remove (&b->free_elem);
 245         }
 246       palloc_free_page (a);
 247     }
 248
 249   lock_release (&d->lock);
 250 }
 251 \f
 252 /* Returns the arena that block B is inside. */
 253 static struct arena *
 254 block_to_arena (struct block *b)
 255 {
 256   struct arena *a = pg_round_down (b);
 257
 258   /* Check that the arena is valid. */
 259   ASSERT (a != NULL);
 260   ASSERT (a->magic == ARENA_MAGIC);
 261
 262   /* Check that the block is properly aligned for the arena. */
 263   ASSERT (a->desc == NULL
 264           || (pg_ofs (b) - sizeof *a) % a->desc->block_size == 0);
 265   ASSERT (a->desc != NULL || pg_ofs (b) == sizeof *a);
 266
 267   return a;
 268 }
 269
 270 /* Returns the (IDX - 1)'th block within arena A. */
 271 static struct block *
 272 arena_to_block (struct arena *a, size_t idx)
 273 {
 274   ASSERT (a != NULL);
 275   ASSERT (a->magic == ARENA_MAGIC);
 276   ASSERT (idx < a->desc->blocks_per_arena);
 277   return (struct block *) ((uint8_t *) a
 278                            + sizeof *a
 279                            + idx * a->desc->block_size);
 280 }