In malloc lab, we will implement our own versions of malloc, free, and realloc. This lab gives us a clear understanding of data layout and organization, and requires us to evaluate different trade-offs between space and time efficiency. When we finish this one, we really understand pointers! Source: Github-Link-Here
Source from Yansongsongsong
Firstly using a docker:
docker run -d -p 9912:22 --name shelllab yansongsongsong/csapp:malloclab
Then using vscode plugin remote ssh
ssh root@127.0.0.1 -p 9912
password: THEPASSWORDYOUCREATED
To compile the driver, type make to the shell.
To run the driver on a brief test trace, use the following command: ./mdriver -V -f traces/short1-bal.rep
The result is like:
1
2
3
| trace valid util ops secs Kops
0 yes 50% 12 0.000000 120000
Total 50% 12 0.000000 120000
|
Please note: It’s crucial to aim for maximizing the utility rate while minimizing time consumption.
After making your changes, validate with all the traces using: ./mdriver -t ./traces -V
This is a solution for explicit free list.
To further boost your scores, consider implementing a segregated list for optimization.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| typedef struct Block {
size_t size; // includes sizeof(block) and footer
struct Block *prev;
struct Block *next;
// size_t footer; // footer is an extra space out of block
// so the memory looks like:
// block payload = 0x200 footer
// 0x0 0x12 0x212 0x216
} Block;
#define FOOTER(ptr) \
((size_t *)((char *)(ptr) + BLOCK_SIZE(ptr) - sizeof(size_t)))
#define SIZE_OF_BLOCK sizeof(Block) + sizeof(size_t)
|
1
2
3
4
5
| // using lowest bit of size to show allocated or not
#define SET_ALLOCATED(b) ((b)->size |= 1)
#define SET_FREE(b) ((b)->size &= ~1)
#define IS_ALLOCATED(b) ((b)->size & 1)
#define BLOCK_SIZE(b) ((b)->size & ~1)
|
- We employ the First Fit strategy.
- Upon finding a sufficiently large block, we split it. The desired block is allocated, while the remainder rejoins the explicit list.
- If no suitable block is available, we expand the heap.
- The
free operation attempts to coalesce: We inspect both the preceding and succeeding blocks. If available, we unify them to form a larger free block. - The Boundary Tag plays a crucial role during this process.
There are four scenarios for realloc:
- If the realloc size is smaller, the block is downsized (via splitting).
- If the block being reallocated is the final block (excluding the epilogue), we can directly extend the heap.
- We may enlarge the block by merging it with the subsequent free block.
- If expansion is infeasible, a fresh block is allocated and the data copied over.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
| // head block, size = 0
Block head = {0, &head, &head};
size_t get_block_size(size_t size) {
// get the aligned block size from initial size
// eg: size = 10, then size = align(size + sizeof(block) + footer)
// = align(10 + 16 + 4) = 32
return (size + SIZE_OF_BLOCK + (ALIGNMENT - 1)) & ~(ALIGNMENT - 1);
}
void clear_block(Block *block) {
*FOOTER(block) = 0;
block->size = 0;
block->prev = NULL;
block->next = NULL;
}
void remove_from_list(Block *block) {
// remove block from list
block->prev->next = block->next;
block->next->prev = block->prev;
}
// insert block to explicit list, prev_block shows the position to insert
void insert_to_list(Block *block, Block *prev_block) {
block->prev = prev_block;
block->next = prev_block->next;
prev_block->next->prev = block;
prev_block->next = block;
}
// Split block, this will generate a free block.
void split_block(Block *block, size_t size, int from_allocated) {
Block *new_block = (Block *)((char *)block + size);
new_block->size = BLOCK_SIZE(block) - size;
*FOOTER(new_block) = BLOCK_SIZE(new_block);
SET_FREE(new_block);
block->size = size;
*FOOTER(block) = size;
if (from_allocated) {
// Case when block is allocated (mm_realloc)
// Insert new_block to the beginning of the list
insert_to_list(new_block, &head);
} else {
// Case when block is free (find_fit)
insert_to_list(new_block, block);
}
}
// find a fit in explicit list
Block *find_fit(size_t size) {
for (Block *block = head.next; block != &head; block = block->next) {
// all the block in list should not be allocated
assert(!IS_ALLOCATED(block));
if (BLOCK_SIZE(block) >= size) {
// Note that here block size and size all should be aligned
assert(block->size % ALIGNMENT == 0);
assert(size % ALIGNMENT == 0);
// If a free block is larger than request, split it
if (BLOCK_SIZE(block) > size + SIZE_OF_BLOCK) {
split_block(block, size, 0);
}
remove_from_list(block);
return block;
}
}
return NULL; // no suitable block
}
Block *coalesce(Block *block, int from_allocated) {
// coalesce, return the pointer of final block
Block *next_block = (Block *)((char *)block + BLOCK_SIZE(block));
size_t prev_block_size = *((size_t *)((char *)block - sizeof(size_t)));
Block *prev_block = (Block *)((char *)block - prev_block_size);
int prev_free = prev_block_size > 0 &&
(char *)prev_block != (char *)(&head) &&
!IS_ALLOCATED(prev_block) && prev_block->size != 0;
int next_free = (char *)next_block != (char *)(&head) &&
!IS_ALLOCATED(next_block) && next_block->size != 0;
if (prev_free && next_free) {
*FOOTER(prev_block) = 0;
prev_block->size += BLOCK_SIZE(block) + BLOCK_SIZE(next_block);
*FOOTER(prev_block) = BLOCK_SIZE(prev_block);
remove_from_list(next_block);
if (!from_allocated) {
remove_from_list(block);
}
clear_block(next_block);
clear_block(block);
return prev_block;
} else if (prev_free) {
*FOOTER(prev_block) = 0;
prev_block->size += BLOCK_SIZE(block);
*FOOTER(prev_block) = BLOCK_SIZE(prev_block);
if (!from_allocated) {
remove_from_list(block);
}
clear_block(block);
return prev_block;
} else if (next_free) {
*FOOTER(block) = 0;
block->size += BLOCK_SIZE(next_block);
*FOOTER(block) = BLOCK_SIZE(block);
remove_from_list(next_block);
clear_block(next_block);
return block;
} else {
return block;
}
}
void expand_heap(size_t size) {
// each time expand heap, the size should be bigger than a single block
assert(size > SIZE_OF_BLOCK);
// try coalesce all of the blocks in explict list
Block *coalesce_block = head.next;
while (coalesce_block != &head) {
assert(coalesce_block != NULL);
coalesce_block = coalesce(coalesce_block, 0);
coalesce_block = coalesce_block->next; // Go to next block after
}
// Get the last block (current epilogue)
// Note that only a size is needed, so we just sub sizeof(size_t)
Block *last_block = (Block *)((char *)mem_sbrk(0) - sizeof(size_t));
// Expand the heap
Block *block = (Block *)mem_sbrk(size);
if (block == (void *)-1) {
perror("Error expanding heap");
exit(1);
}
memset(block, 0, size); // make sure block here is empty
// If the last block was an epilogue, we overwrite it and adjust the size.
if (IS_ALLOCATED(last_block) && BLOCK_SIZE(last_block) == 0) {
block = last_block;
size += sizeof(size_t);
}
// Set the size of the new block (excluding the epilogue at the end)
block->size = size - sizeof(size_t);
*FOOTER(block) = BLOCK_SIZE(block);
insert_to_list(block, &head);
// Add a new epilogue block at the end
Block *epilogue = (Block *)((char *)block + BLOCK_SIZE(block));
epilogue->size = 0;
SET_ALLOCATED(epilogue);
}
/*
* mm_init - initialize the malloc package.
*/
int mm_init(void) {
// Clear all values in the blocks linked to the head.
for (Block *block = head.next; block != &head;) {
Block *temp = block;
block = block->next;
clear_block(temp);
}
// Reset the head block's pointers.
head.size = 0;
head.prev = &head;
head.next = &head;
// Add a prologue block, to avoid bug when coalescing the first block
Block *prologue = (Block *)mem_sbrk(ALIGN(sizeof(Block)));
prologue->size = ALIGN(sizeof(Block));
SET_ALLOCATED(prologue);
*FOOTER(prologue) = BLOCK_SIZE(prologue);
// Expand the heap.
expand_heap(EXPAND_HEAP_SIZE);
return 0;
}
/*
* mm_malloc - Allocate a block by incrementing the brk pointer.
* Always allocate a block whose size is a multiple of the alignment.
*/
void *mm_malloc(size_t size) {
size = get_block_size(size);
Block *block = find_fit(size);
if (!block) {
expand_heap(size > EXPAND_HEAP_SIZE ? size : EXPAND_HEAP_SIZE);
block = find_fit(size);
if (!block) {
return NULL;
}
}
SET_ALLOCATED(block);
return (void *)((char *)block + sizeof(Block)); // return data to user
}
/*
* mm_free - Freeing a block does nothing.
*/
void mm_free(void *ptr) {
if (!ptr) return; // null check
Block *block = (Block *)((char *)ptr - sizeof(Block));
SET_FREE(block);
Block *coalescedBlock = coalesce(block, 1);
if (coalescedBlock == block) {
insert_to_list(coalescedBlock, &head);
}
}
/*
* mm_realloc - Resizes the memory block point to by ptr to size bytes.
*/
void *mm_realloc(void *ptr, size_t size) {
if (!ptr) {
// case when ptr == nullptr, malloc a new one
return mm_malloc(size);
}
if (size == 0) {
// case when ptr is used and size==0, equal to free
mm_free(ptr);
return NULL;
}
Block *block = (Block *)((char *)ptr - sizeof(Block)); // get block
size_t realloc_block_size = get_block_size(size);
// for a allocated block, next and prev is meaning less
assert(IS_ALLOCATED(block));
block->next = NULL;
block->prev = NULL;
// Case 1: If realloc size is smaller, shrink the block, and the new block
// will be added to the explicit list. Note that at this time, block is
// already in use, so we do not need to remove it from explicit list
if (BLOCK_SIZE(block) > realloc_block_size + SIZE_OF_BLOCK) {
split_block(block, realloc_block_size, 1);
SET_ALLOCATED(block);
return ptr;
}
// Case 2: The block to be reallocated is the last block(not epilogue)
// At this time, we can directly expand the heap
Block *next_block = (Block *)((char *)block + BLOCK_SIZE(block));
Block *epilogue = (Block *)((char *)mem_sbrk(0) - sizeof(size_t));
if (next_block == epilogue) {
size_t extra_size = realloc_block_size - BLOCK_SIZE(block);
if (extra_size > SIZE_OF_BLOCK) {
// This is the last block. Simply expand heap.
expand_heap(realloc_block_size - BLOCK_SIZE(block));
// after we expand_heap, we add a block to the explicit list
// so we should remove it now.
remove_from_list(head.next);
block->size = realloc_block_size;
SET_ALLOCATED(block);
return ptr;
}
}
// Case 3: Attempt to extend the block by coalescing with the next free block
// Note: there is no need to coalesce the previous block, if we do so
// we need to memcpy, which is the same with mm_malloc (case 4)
int next_free = (char *)next_block != (char *)(&head) &&
!IS_ALLOCATED(next_block) && next_block->size != 0;
if (next_free) {
*FOOTER(block) = 0;
block->size += BLOCK_SIZE(next_block);
*FOOTER(block) = BLOCK_SIZE(block);
remove_from_list(next_block);
clear_block(next_block);
if (BLOCK_SIZE(block) > realloc_block_size + SIZE_OF_BLOCK) {
split_block(block, realloc_block_size, 1);
SET_ALLOCATED(block);
return ptr;
}
}
// Case 4: If the block can't be extended, allocate a new block
void *new_ptr = mm_malloc(size);
if (!new_ptr) {
return NULL;
}
memcpy(new_ptr, ptr, size);
mm_free(ptr);
return new_ptr;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| Results for mm malloc:
trace valid util ops secs Kops
0 yes 93% 5694 0.000656 8677
1 yes 94% 5848 0.000405 14429
2 yes 96% 6648 0.001274 5219
3 yes 97% 5380 0.000680 7913
4 yes 40% 14400 0.000499 28881
5 yes 90% 4800 0.003578 1342
6 yes 86% 4800 0.003834 1252
7 yes 53% 12000 0.019015 631
8 yes 47% 24000 0.019389 1238
9 yes 98% 14401 0.000452 31839
10 yes 45% 14401 0.001873 7688
Total 76% 112372 0.051655 2175
|