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 <stdint.h>
   5 #include <stdio.h>
   6 #include <string.h>
   7 #include "threads/mmu.h"
   8 #include "threads/palloc.h"
   9 #include "threads/synch.h"
  10
  11 /* A simple implementation of malloc().
  12
  13    The size of each request, in bytes, is rounded up to a power
  14    of 2 and assigned to the "descriptor" that manages blocks of
  15    that size.  The descriptor keeps a list of free blocks.  If
  16    the free list is nonempty, one of its blocks is used to
  17    satisfy the request.
  18
  19    Otherwise, a new page of memory, called an "arena", is
  20    obtained from the page allocator (if none is available,
  21    malloc() returns a null pointer).  The new arena is divided
  22    into blocks, all of which are added to the descriptor's free
  23    list.  Then we return one of the new blocks.
  24
  25    When we free a block, we add it to its descriptor's free list.
  26    But if the arena that the block was in now has no in-use
  27    blocks, we remove all of the arena's blocks from the free list
  28    and give the arena back to the page allocator.
  29
  30    Major limitation: the largest block that can be allocated is
  31    PGSIZE / 2, or 2 kB.  Use palloc_get() to allocate pages (4 kB
  32    blocks).  You're on your own if you need more memory than
  33    that. */
  34
  35 /* Descriptor. */
  36 struct desc
  37   {
  38     size_t block_size;          /* Size of each element in bytes. */
  39     size_t blocks_per_arena;    /* Number of blocks in an arena. */
  40     struct list free_list;      /* List of free blocks. */
  41     struct lock lock;           /* Lock. */
  42   };
  43
  44 /* Arena. */
  45 struct arena
  46   {
  47     struct desc *desc;          /* Owning descriptor. */
  48     size_t free_cnt;            /* Number of free blocks. */
  49   };
  50
  51 /* Free block. */
  52 struct block
  53   {
  54     list_elem free_elem;        /* Free list element. */
  55   };
  56
  57 /* Our set of descriptors. */
  58 static struct desc descs[16];   /* Descriptors. */
  59 static size_t desc_cnt;         /* Number of descriptors. */
  60
  61 static struct arena *block_to_arena (struct block *);
  62 static struct block *arena_to_block (struct arena *, size_t idx);
  63
  64 /* Initializes the malloc() descriptors. */
  65 void
  66 malloc_init (void)
  67 {
  68   size_t block_size;
  69
  70   for (block_size = 16; block_size < PGSIZE; block_size *= 2)
  71     {
  72       struct desc *d = &descs[desc_cnt++];
  73       ASSERT (desc_cnt <= sizeof descs / sizeof *descs);
  74       d->block_size = block_size;
  75       d->blocks_per_arena = (PGSIZE - sizeof (struct arena)) / block_size;
  76       list_init (&d->free_list);
  77       lock_init (&d->lock, "malloc");
  78     }
  79 }
  80
  81 /* Obtains and returns a new block of at least SIZE bytes.
  82    Returns a null pointer if memory is not available. */
  83 void *
  84 malloc (size_t size)
  85 {
  86   struct desc *d;
  87   struct block *b;
  88   struct arena *a;
  89
  90   /* A null pointer satisfies a request for 0 bytes. */
  91   if (size == 0)
  92     return NULL;
  93
  94   /* Find the smallest descriptor that satisfies a SIZE-byte
  95      request. */
  96   for (d = descs; d < descs + desc_cnt; d++)
  97     if (size < d->block_size)
  98       break;
  99   if (d == descs + desc_cnt)
 100     {
 101       printf ("malloc: %zu byte allocation too big\n", size);
 102       return NULL;
 103     }
 104
 105   lock_acquire (&d->lock);
 106
 107   /* If the free list is empty, create a new arena. */
 108   if (list_empty (&d->free_list))
 109     {
 110       size_t i;
 111
 112       /* Allocate a page. */
 113       a = palloc_get (0);
 114       if (a == NULL)
 115         {
 116           lock_release (&d->lock);
 117           return NULL;
 118         }
 119
 120       /* Initialize arena and add its blocks to the free list. */
 121       a->desc = d;
 122       a->free_cnt = d->blocks_per_arena;
 123       for (i = 0; i < d->blocks_per_arena; i++)
 124         {
 125           b = arena_to_block (a, i);
 126           list_push_back (&d->free_list, &b->free_elem);
 127         }
 128     }
 129
 130   /* Get a block from free list and return it. */
 131   b = list_entry (list_pop_front (&d->free_list), struct block, free_elem);
 132   a = block_to_arena (b);
 133   a->free_cnt--;
 134   lock_release (&d->lock);
 135   return b;
 136 }
 137
 138 /* Allocates and return A times B bytes initialized to zeroes.
 139    Returns a null pointer if memory is not available. */
 140 void *
 141 calloc (size_t a, size_t b)
 142 {
 143   void *p;
 144   size_t size;
 145
 146   /* Calculate block size. */
 147   size = a * b;
 148   if (size < a || size < b)
 149     return NULL;
 150
 151   /* Allocate and zero memory. */
 152   p = malloc (size);
 153   if (p != NULL)
 154     memset (p, 0, size);
 155
 156   return p;
 157 }
 158
 159 /* Frees block P, which must have been previously allocated with
 160    malloc() or calloc(). */
 161 void
 162 free (void *p)
 163 {
 164   struct block *b = p;
 165   struct arena *a = block_to_arena (b);
 166   struct desc *d = a->desc;
 167
 168   if (p == NULL)
 169     return;
 170
 171   lock_acquire (&d->lock);
 172
 173   /* Add block to free list. */
 174   list_push_front (&d->free_list, &b->free_elem);
 175
 176   /* If the arena is now entirely unused, free it. */
 177   if (++a->free_cnt >= d->blocks_per_arena)
 178     {
 179       size_t i;
 180
 181       ASSERT (a->free_cnt == d->blocks_per_arena);
 182       for (i = 0; i < d->blocks_per_arena; i++)
 183         {
 184           struct block *b = arena_to_block (a, i);
 185           list_remove (&b->free_elem);
 186         }
 187       palloc_free (a);
 188     }
 189
 190   lock_release (&d->lock);
 191 }
 192 \f
 193 /* Returns the arena that block B is inside. */
 194 static struct arena *
 195 block_to_arena (struct block *b)
 196 {
 197   return pg_round_down (b);
 198 }
 199
 200 /* Returns the (IDX - 1)'th block within arena A. */
 201 static struct block *
 202 arena_to_block (struct arena *a, size_t idx)
 203 {
 204   ASSERT (idx < a->desc->blocks_per_arena);
 205   return (struct block *) ((uint8_t *) a
 206                            + sizeof *a
 207                            + idx * a->desc->block_size);
 208 }