1 #include "threads/malloc.h"
7 #include "threads/mmu.h"
8 #include "threads/palloc.h"
9 #include "threads/synch.h"
11 /* A simple implementation of malloc().
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
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.
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.
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
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. */
47 struct desc *desc; /* Owning descriptor. */
48 size_t free_cnt; /* Number of free blocks. */
54 list_elem free_elem; /* Free list element. */
57 /* Our set of descriptors. */
58 static struct desc descs[16]; /* Descriptors. */
59 static size_t desc_cnt; /* Number of descriptors. */
61 static struct arena *block_to_arena (struct block *);
62 static struct block *arena_to_block (struct arena *, size_t idx);
64 /* Initializes the malloc() descriptors. */
70 for (block_size = 16; block_size < PGSIZE; block_size *= 2)
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");
81 /* Obtains and returns a new block of at least SIZE bytes.
82 Returns a null pointer if memory is not available. */
90 /* A null pointer satisfies a request for 0 bytes. */
94 /* Find the smallest descriptor that satisfies a SIZE-byte
96 for (d = descs; d < descs + desc_cnt; d++)
97 if (size < d->block_size)
99 if (d == descs + desc_cnt)
101 printf ("malloc: %zu byte allocation too big\n", size);
105 lock_acquire (&d->lock);
107 /* If the free list is empty, create a new arena. */
108 if (list_empty (&d->free_list))
112 /* Allocate a page. */
116 lock_release (&d->lock);
120 /* Initialize arena and add its blocks to the free list. */
122 a->free_cnt = d->blocks_per_arena;
123 for (i = 0; i < d->blocks_per_arena; i++)
125 b = arena_to_block (a, i);
126 list_push_back (&d->free_list, &b->free_elem);
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);
134 lock_release (&d->lock);
138 /* Allocates and return A times B bytes initialized to zeroes.
139 Returns a null pointer if memory is not available. */
141 calloc (size_t a, size_t b)
146 /* Calculate block size. */
148 if (size < a || size < b)
151 /* Allocate and zero memory. */
159 /* Frees block P, which must have been previously allocated with
160 malloc() or calloc(). */
165 struct arena *a = block_to_arena (b);
166 struct desc *d = a->desc;
171 lock_acquire (&d->lock);
173 /* Add block to free list. */
174 list_push_front (&d->free_list, &b->free_elem);
176 /* If the arena is now entirely unused, free it. */
177 if (++a->free_cnt >= d->blocks_per_arena)
181 ASSERT (a->free_cnt == d->blocks_per_arena);
182 for (i = 0; i < d->blocks_per_arena; i++)
184 struct block *b = arena_to_block (a, i);
185 list_remove (&b->free_elem);
190 lock_release (&d->lock);
193 /* Returns the arena that block B is inside. */
194 static struct arena *
195 block_to_arena (struct block *b)
197 return pg_round_down (b);
200 /* Returns the (IDX - 1)'th block within arena A. */
201 static struct block *
202 arena_to_block (struct arena *a, size_t idx)
204 ASSERT (idx < a->desc->blocks_per_arena);
205 return (struct block *) ((uint8_t *) a
207 + idx * a->desc->block_size);