本 lab 程式碼已完成,但筆記大部分內容還在撰寫中
PS. 在閱讀過如何寫一個 Git Commit Message後深覺自己的 git message 根本在亂寫,本來想用 git rebase -i 來逐一修改,但考量只是作業的紀錄,決定留著作為紀念
開始前先來看看 writeup 內的 hint 最後一項
Start early! It is possible to write an efficient malloc package with a few pages of code. However, we can guarantee that it will be some of the most difficult and sophisticated code you have written so far in your career. So start early, and good luck!
看來這個 lab 會相當難搞啊XD
本 lab 需要自行撰寫一個 dynamic memory allocator,涵蓋 malloc
、 free
與 realloc
首先 dyamic memory allcator 有兩種主要的分類,由於作業題目要求使用 C 語言撰寫,因此 malloc lab 使用的是 Explicit allocator
free
等方程式來將配置的動態記憶體釋放影響 allocator 效能 (空間利用率及吞吐量) 的關鍵因素是 free block 的組織方式及動態記憶體配置的尋找方式
free block 的組織方式有以下三種
配置動態記憶體時的尋找方式有三種
malloc lab 會強制使用 32-bit 的函式庫進行編譯,如果缺少對應的函式庫,在 ubuntu (Debian) 中可以用以下方式取得
$ apt-get install gcc-multilib
基本上照著 CS:APP 第 9 章的範例稍作修改就能寫完這個部分,採用 implicit free list 來管理 free block,heap block 則採用皆有 header 與 footer 的格式,如下圖
Learn More →
最後的結果如下
Results for mm malloc:
trace valid util ops secs Kops
0 yes 99% 5694 0.007360 774
1 yes 99% 5848 0.007895 741
2 yes 99% 6648 0.013615 488
3 yes 100% 5380 0.009066 593
4 yes 66% 14400 0.000284 50794
5 yes 92% 4800 0.007785 617
6 yes 92% 4800 0.008416 570
7 yes 55% 12000 0.206528 58
8 yes 51% 24000 0.276396 87
9 yes 27% 14401 0.064584 223
10 yes 34% 14401 0.002457 5861
Total 74% 112372 0.604384 186
Perf index = 44 (util) + 12 (thru) = 57/100
Results for mm malloc:
trace valid util ops secs Kops
0 yes 99% 5694 0.007283 782
1 yes 100% 5848 0.007488 781
2 yes 99% 6648 0.012473 533
3 yes 100% 5380 0.009148 588
4 yes 99% 14400 0.000193 74496
5 yes 92% 4800 0.007895 608
6 yes 92% 4800 0.008242 582
7 yes 55% 12000 0.156152 77
8 yes 51% 24000 0.285498 84
9 yes 30% 14401 0.062039 232
10 yes 34% 14401 0.002285 6301
Total 77% 112372 0.558696 201
Perf index = 46 (util) + 13 (thru) = 60/100
無論用哪種 free block 組織的方式實作 allocator,都會發現評分後只能拿到及格分數,因此需要進一步優話 realloc 的效能
初始配置的空間大小會影響效率
int mm_init(void)
{
...
/* extend the empty heap size by 4kB */
if(extend_heap(4*WSIZE) == NULL)
return -1;
...
}
void *mm_malloc(size_t size)
{
...
/* no fit found, extend heap to place the block */
extendsize = MAX(asize, CHUNKSIZE);
if((bp = extend_heap(extendsize)) == NULL)
return NULL;
...
}
void *mm_realloc(void *ptr, size_t size)
{
char *new_bp;
size_t old_size = GET_SIZE(HDRP(ptr)) - 2*WSIZE; /* content size of the old block */
/* ignore spurious requests */
if(ptr == NULL && size == 0) {
return NULL;
}
/* if ptr is NULL, the call is equivalent to mm malloc(size) */
else if(ptr == NULL) {
return mm_malloc(size);
}
/* if size is equal to zero, the call is equivalent to mm free(ptr) */
else if(size == 0) {
mm_free(ptr);
return NULL;
}
if(size > old_size) { /* allocate a larger space */
/* allocate the new block */
if((new_bp = mm_malloc(size)) == NULL)
return NULL;
memcpy(new_bp, ptr, old_size);
mm_free(ptr); /* free the old block */
return (void *)new_bp;
}
else { /**/
size = ALIGN(size + 2*WSIZE);
old_size += 2*WSIZE;
if((old_size - size) >= (2*DSIZE)) {
/* shrink the block to size */
PUTW(HDRP(ptr), PACK(size, 1));
PUTW(FTRP(ptr), PACK(size, 1));
/* free the remainder block */
PUTW(HDRP(NEXT_BLKP(ptr)), PACK((old_size - size), 0));
PUTW(FTRP(NEXT_BLKP(ptr)), PACK((old_size - size), 0));
if((GET_NEXT(freelist_root)) == NULL) {
PUT_NEXT(freelist_root, NEXT_BLKP(ptr));
PUT_PREV(freelist_root, NEXT_BLKP(ptr));
PUT_NEXT(NEXT_BLKP(ptr), freelist_root);
PUT_PREV(NEXT_BLKP(ptr), freelist_root);
}
else {
PUT_PREV(GET_NEXT(freelist_root), ptr);
PUT_NEXT(ptr, GET_NEXT(freelist_root));
PUT_NEXT(freelist_root, ptr);
PUT_PREV(ptr, freelist_root);
}
return ptr;
}
else {
return ptr;
}
}
}
最簡單的實作方式,但空間利用率和效率都非常糟糕
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *ptr, size_t size)
{
char *new_bp;
size_t old_size = GET_SIZE(HDRP(ptr)) - 2*WSIZE; /* content size of the old block */
/* ignore spurious requests */
if(ptr == NULL && size == 0) {
return NULL;
}
/* if ptr is NULL, the call is equivalent to mm malloc(size) */
else if(ptr == NULL) {
return mm_malloc(size);
}
/* if size is equal to zero, the call is equivalent to mm free(ptr) */
else if(size == 0) {
mm_free(ptr);
return NULL;
}
#ifndef TEST_REALLOC
/* allocate the new block */
if((new_bp = mm_malloc(size)) == NULL)
return NULL;
/* The contents of the new block are same as the old ptr block
(up to the minimum of the old and new block sizes). */
if(old_size <= size) {
memcpy(new_bp, ptr, old_size);
}
else {
memcpy(new_bp, ptr, size);
}
mm_free(ptr); /* free the old block */
return (void *)new_bp;
#else
size_t prev_alloc = GET_ALLOC(HDRP(PREV_BLKP(ptr)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr)));
size_t prev_size = prev_alloc? 0 : GET_SIZE(HDRP(PREV_BLKP(ptr)));
size_t next_size = next_alloc? 0 : GET_SIZE(HDRP(NEXT_BLKP(ptr)));
/* use the whole block size instead of the content size */
size = ALIGN(size + 2*WSIZE);
old_size = GET_SIZE(HDRP(ptr));
if(size == old_size) {
return ptr;
}
/* realloc a smaller block */
if(size < old_size) {
if(prev_alloc && next_alloc) { /* both prev and next block are allocated */
if((old_size - size) < (2*DSIZE)) { /* use original block when size changes too small */
return ptr;
}
else { /* shrink the block */
PUTW(HDRP(ptr), PACK(size, 1));
PUTW(FTRP(ptr), PACK(size, 1));
/* re-insert the new block at the root of the list */
PUTW(HDRP(NEXT_BLKP(ptr)), PACK((old_size - size), 0));
PUTW(FTRP(NEXT_BLKP(ptr)), PACK((old_size - size), 0));
insert_root(NEXT_BLKP(ptr));
return ptr;
}
}
else {
if(!next_alloc) { /* shrink ptr and adjust next free block */
detach(NEXT_BLKP(ptr));
PUTW(HDRP(ptr), PACK(size, 1));
PUTW(FTRP(ptr), PACK(size, 1));
/* re-insert the new block at the root of the list */
PUTW(HDRP(NEXT_BLKP(ptr)), PACK((old_size + next_size - size), 0));
PUTW(FTRP(NEXT_BLKP(ptr)), PACK((old_size + next_size - size), 0));
insert_root(NEXT_BLKP(ptr));
return ptr;
}
else { /* only prev block is free */
detach(PREV_BLKP(ptr));
ptr = PREV_BLKP(ptr);
memmove(ptr, NEXT_BLKP(ptr), (size - 2*WSIZE));
PUTW(HDRP(ptr), PACK(size, 1));
PUTW(FTRP(ptr), PACK(size, 1));
/* re-insert the new block at the root of the list */
PUTW(HDRP(NEXT_BLKP(ptr)), PACK((prev_size + old_size - size), 0));
PUTW(FTRP(NEXT_BLKP(ptr)), PACK((prev_size + old_size - size), 0));
insert_root(NEXT_BLKP(ptr));
return ptr;
}
}
}
/* realloc a larger block */
else {
if(size > (old_size + prev_size + next_size)) { /* need to allocate a new block by malloc */
/* allocate the new block */
if((new_bp = mm_malloc(size)) == NULL)
return NULL;
memcpy(new_bp, ptr, (old_size - 2*WSIZE));
mm_free(ptr); /* free the old block */
return (void *)new_bp;
}
else {
if((old_size + next_size) >= size) { /* use ptr + next block */
detach(NEXT_BLKP(ptr));
if((old_size + next_size - size) >= (2*DSIZE)) {
PUTW(HDRP(ptr), PACK(size, 1));
PUTW(FTRP(ptr), PACK(size, 1));
/* re-insert the new block at the root of the list */
PUTW(HDRP(NEXT_BLKP(ptr)), PACK((old_size + next_size - size), 0));
PUTW(FTRP(NEXT_BLKP(ptr)), PACK((old_size + next_size - size), 0));
insert_root(NEXT_BLKP(ptr));
return ptr;
}
else { /* use whole ptr + next */
PUTW(HDRP(ptr), PACK((old_size + next_size), 1));
PUTW(FTRP(ptr), PACK((old_size + next_size), 1));
return ptr;
}
}
else if((prev_size + old_size) >= size) { /* use ptr + prev block */
detach(PREV_BLKP(ptr));
if((prev_size + old_size - size) >= (2*DSIZE)) {
ptr = PREV_BLKP(ptr);
memmove(ptr, NEXT_BLKP(ptr), (old_size - 2*WSIZE));
PUTW(HDRP(ptr), PACK(size, 1));
PUTW(FTRP(ptr), PACK(size, 1));
/* re-insert the new block at the root of the list */
PUTW(HDRP(NEXT_BLKP(ptr)), PACK((prev_size + old_size - size), 0));
PUTW(FTRP(NEXT_BLKP(ptr)), PACK((prev_size + old_size - size), 0));
insert_root(NEXT_BLKP(ptr));
return ptr;
}
else { /* use whole prev + ptr */
ptr = PREV_BLKP(ptr);
memcpy(ptr, NEXT_BLKP(ptr), (old_size - 2*WSIZE));
PUTW(HDRP(ptr), PACK((prev_size + old_size), 1));
PUTW(FTRP(ptr), PACK((prev_size + old_size), 1));
return ptr;
}
}
else { /* use prev + ptr + next block */
detach(PREV_BLKP(ptr));
detach(NEXT_BLKP(ptr));
if((prev_size + old_size + next_size - size) >= (2*DSIZE)) {
ptr = PREV_BLKP(ptr);
memcpy(ptr, NEXT_BLKP(ptr), (old_size - 2*WSIZE));
PUTW(HDRP(ptr), PACK(size, 1));
PUTW(FTRP(ptr), PACK(size, 1));
/* re-insert the new block at the root of the list */
PUTW(HDRP(NEXT_BLKP(ptr)), PACK((prev_size + old_size + next_size - size), 0));
PUTW(FTRP(NEXT_BLKP(ptr)), PACK((prev_size + old_size + next_size - size), 0));
insert_root(NEXT_BLKP(ptr));
return ptr;
}
else { /* use whole prev + ptr + next */
ptr = PREV_BLKP(ptr);
memcpy(ptr, NEXT_BLKP(ptr), (old_size - 2*WSIZE));
PUTW(HDRP(ptr), PACK((prev_size + old_size + next_size), 1));
PUTW(FTRP(ptr), PACK((prev_size + old_size + next_size), 1));
return ptr;
}
}
}
}
#endif
}
compiling a 32 bit binary on a 64 bit machine
97分來源
glibc 的 malloc/free 實作
csapp
contributed by < KYG-yaya573142 > H03: fibdrv 預期目標 撰寫適用於 Linux 核心層級的程式 學習 ktimer, copy_to_user 一類的核心 API 複習 C 語言 數值系統 和 bitwise operation 初探 Linux VFS
Oct 27, 2022github :::info 此筆記主要紀錄 CS:APP 作業 shell lab 的解題思路,由於是一步一腳印撰寫,並非寫完再事後筆記,因此會顯得比較雜亂 ::: :::info TODO: unlify the notation style for better readability
Dec 12, 20212020 Linux 核心設計 lab-0 fibdrv kcalc khttpd quiz2 quiz3 quiz4
Jul 28, 2020contributed by < KYG-yaya573142 > 第 3 週測驗題 測驗 1 XOR linked list 原理 XOR 運算特性為 $A \oplus A = 0$ $A \oplus 0 = A$
Jul 9, 2020or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up