10 /* A simple implementation of malloc().
12 The size of each request, in bytes, is rounded up to a power
13 of 2 and assigned to the "descriptor" that manages blocks of
14 that size. The descriptor keeps a list of free blocks. If
15 the free list is nonempty, one of its blocks is used to
18 Otherwise, a new page of memory, called an "arena", is
19 obtained from the page allocator (if none is available,
20 malloc() returns a null pointer). The new arena is divided
21 into blocks, all of which are added to the descriptor's free
22 list. Then we return one of the new blocks.
24 When we free a block, we add it to its descriptor's free list.
25 But if the arena that the block was in now has no in-use
26 blocks, we remove all of the arena's blocks from the free list
27 and give the arena back to the page allocator.
29 Major limitation: the largest block that can be allocated is
30 PGSIZE / 2, or 2 kB. Use palloc_get() to allocate pages (4 kB
31 blocks). You're on your own if you need more memory than
37 size_t block_size; /* Size of each element in bytes. */
38 size_t blocks_per_arena; /* Number of blocks in an arena. */
39 struct list free_list; /* List of free blocks. */
40 struct lock lock; /* Lock. */
46 struct desc *desc; /* Owning descriptor. */
47 size_t free_cnt; /* Number of free blocks. */
53 list_elem free_elem; /* Free list element. */
56 /* Our set of descriptors. */
57 static struct desc descs[16]; /* Descriptors. */
58 static size_t desc_cnt; /* Number of descriptors. */
60 static struct arena *block_to_arena (struct block *);
61 static struct block *arena_to_block (struct arena *, size_t idx);
63 /* Initializes the malloc() descriptors. */
69 for (block_size = 16; block_size < PGSIZE; block_size *= 2)
71 struct desc *d = &descs[desc_cnt++];
72 ASSERT (desc_cnt <= sizeof descs / sizeof *descs);
73 d->block_size = block_size;
74 d->blocks_per_arena = (PGSIZE - sizeof (struct arena)) / block_size;
75 list_init (&d->free_list);
76 lock_init (&d->lock, "malloc");
80 /* Obtains and returns a new block of at least SIZE bytes.
81 Returns a null pointer if memory is not available. */
89 /* A null pointer satisfies a request for 0 bytes. */
93 /* Find the smallest descriptor that satisfies a SIZE-byte
95 for (d = descs; d < descs + desc_cnt; d++)
96 if (size < d->block_size)
98 if (d == descs + desc_cnt)
100 printk ("malloc: %zu byte allocation too big\n", size);
104 lock_acquire (&d->lock);
106 /* If the free list is empty, create a new arena. */
107 if (list_empty (&d->free_list))
111 /* Allocate a page. */
115 lock_release (&d->lock);
119 /* Initialize arena and add its blocks to the free list. */
121 a->free_cnt = d->blocks_per_arena;
122 for (i = 0; i < d->blocks_per_arena; i++)
124 b = arena_to_block (a, i);
125 list_push_back (&d->free_list, &b->free_elem);
129 /* Get a block from free list and return it. */
130 b = list_entry (list_pop_front (&d->free_list), struct block, free_elem);
131 a = block_to_arena (b);
133 lock_release (&d->lock);
137 /* Allocates and return A times B bytes initialized to zeroes.
138 Returns a null pointer if memory is not available. */
140 calloc (size_t a, size_t b)
145 /* Calculate block size. */
147 if (size < a || size < b)
150 /* Allocate and zero memory. */
158 /* Frees block P, which must have been previously allocated with
159 malloc() or calloc(). */
164 struct arena *a = block_to_arena (b);
165 struct desc *d = a->desc;
167 lock_acquire (&d->lock);
169 /* Add block to free list. */
170 list_push_front (&d->free_list, &b->free_elem);
172 /* If the arena is now entirely unused, free it. */
173 if (++a->free_cnt >= d->blocks_per_arena)
177 ASSERT (a->free_cnt == d->blocks_per_arena);
178 for (i = 0; i < d->blocks_per_arena; i++)
180 struct block *b = arena_to_block (a, i);
181 list_remove (&b->free_elem);
186 lock_release (&d->lock);
189 /* Returns the arena that block B is inside. */
190 static struct arena *
191 block_to_arena (struct block *b)
193 return pg_round_down (b);
196 /* Returns the (IDX - 1)'th block within arena A. */
197 static struct block *
198 arena_to_block (struct arena *a, size_t idx)
200 ASSERT (idx < a->desc->blocks_per_arena);
201 return (struct block *) ((uint8_t *) a
203 + idx * a->desc->block_size);