Try   HackMD

2023q1 Homework5 (quiz5)

contributed by < Korin777 >

測驗題目

測驗一

運作原理

pool_malloc

透過 get_loc_to_place 從 memory pool 的 free block 中配置記憶體給使用者

  1. 配置記憶體的大小會根據 32 bits 或 64 bits 進行 round up
  2. free block 大小要大於等於所需的 size + header_size 確保釋放時有足夠的空間存放 metadata
  3. 因為配置的記憶體空間是從 free block 的頭開始，所以要更新 free block 的位置並重新儲存 metadata

pool_free

釋放配置的記憶體

  1. 透過 get_loc_to_free 找出可能可以 merge 的 free block，因為 free block 的 list 根據 address 從低到高串聯，所以我們只要根據目前釋放的記憶體位置往前或往後找即可
  2. 查看目前釋放的 block 是否跟上一步找到的 free block 相鄰，是的話將兩者合併
  3. 合併後原本與 free block 相鄰的 free block 也可能可以合併，因此要在次檢查

改進

測試程式時可以發現如果將 memory pool 的記憶體配置完後，在去釋放這些記憶體，然後再去配置記憶體時會無法獲得可用的記憶體空間，以下為實作上可改進的地方

pool_malloc

  • 配置空間時並未記錄配置空間大小，且沒有減少 pool_free_space
  • 配置記憶體時，free block 不一定為 current
  • In-use block 只配置了 _size + word_size 的空間，我認為應該要配置_size + header_size的空間，因為當這個 block 釋放為 free block 時，假設我們 _size 只配置了 8 bytes ， In-use block 就只有 16 bytes 而放不下 metadata ， 這時 prev block pointer 會動到別的 block 的記憶體

pool_free

  • 釋放記憶體時，若沒有進行 merge ，這個 free block 不會跟其他 free block 接在一起
  • free block 合併時未檢查 next 或 prev 是否為 NULL

get_loc_to_free

  • tmp_pt 應為 current 的值而非地址，若是後者(即 &current) 此時 tmp_block->prev 會相當於 ((block_t *)&current)->prev 但我們應該是要 current->prev

get_loc_to_place

  • 原本的實作並不會把整個 free_block 配置出去，但只要確保不只存在一個 free_block ，我們就能把整個 free_block 的記憶體配置出去

測驗二

結構體

  1. metadata_t : 紀錄配置的 memroy block 的資訊

    • size : 配置的記憶體大小
    • free : memroy block 是否被釋放，可用來偵測 double free
    • *next、*prev : 連接前後相鄰的 memory block

  2. rbnode_t : 用來放被釋放的 memroy block ， 相同大小的 memory block 會放在同一個 node

    • size、free、*next、*prev : node 的 metadata
    • key : 放在這個 node 的 memory block 大小
    • **tab_values : 放 memory block ，預設可以放 256 個，透過 resize_tab_values 增加
    • size_tab : memory block 可放的總數
    • n_active : 已放的 memory block 數量
    • color : node 的顏色
    • *left、*right : node 的 child

  3. malloc_t : 可用的記憶體空間

    • *root_rbtree : 用來放被釋放 memroy block 的紅黑樹根節點
    • last_node : 最新被配置的 memory block
    • *end_in_page : 目前配置到的記憶體地址，也就是下一次配置記憶體會從這裡開始
    • *first_block : 最一開始可以使用到的記憶體地址，也就是可用的記憶體最低地址
    • page_size : 一個 page 的大小，在我的電腦上為 4096 bytes
    • mutex : 確保只有一個執行續能配置及釋放記憶體的 lock
    • page_remaining : 尚未被配置的記憶體空間大小

free

  • 首先會去檢查記憶體是否在以配置的記憶體範圍內及 metadata_t->free 來看是否合法，再來會用 metadata_t->free 偵測 double free
  • 接下來 try_fusion 藉由 metadata_t->prev、metadata_t->next、metadata_t->free 來合併相鄰的 free block ，被合併的 block 會從該 rbnode_t 中移除，若移除後 rbnode_t 沒任何 memory block 就將該 rbnode_t 從紅黑樹中移除
  • 最後會去釋放記憶體，分為兩種情況 :
    1. 釋放的 memory block 為最新配置的 memory block : 這時可以直接透過 change_break 來更新 malloc_t ， 若 malloc_t->page_remaining 大於一個 page 就可以透過 brk 來真正釋放我們用 sbrk 配置的記憶體
    2. 其他情況 : 此時就要將 memory block 放到紅黑樹的 rbnode_t 中 ， 若不存在該 memory block 大小 的 rbnode_t， 就插入新的 rbnode_t 到紅黑樹中， malloc 會透過紅黑樹來使用已配置但現為 free block 的記憶體

malloc

  • 首先會透過 ALIGN_BYTES 讓配置的記憶體位置以 16-bytes 對齊(64-bits 系統下)
  • 接著透過 search_freed_block 去紅黑數找已配置但現為 free block 的記憶體，來重用記憶體空間，因為紅黑數為二元搜尋樹，可以發現 find_best 透過這個性質來找出不小於所需 size 的 rbnode_t 來達到 best-fit 的策略
    • 若有找到 rbnode_t ，就透過 split_block 就將其中一個 free block 移除，因為 free block 空間可能遠高於所需的空間，所以當 free block 剩餘的空間扣掉所需的空間後，仍能放 maclloc 所配置的最小記憶體 SIZE_DEFAULT_BLOCK + META_SIZE ，就將它分割成兩塊，一塊給使用者使用 (in-use block) 而另一塊會重新插入紅黑樹中 (free block)

    在程式碼中 split_block 要分割的判斷是 node->size > size + sizeof(size_t) && node->size - size > sizeof(rbnode_t) + SIZE_DEFAULT_BLOCK 跟我的想法不同，我認為剩餘的空間扣掉所需的空間後只要不小於最小能配置的記憶體空間，分割出來的 free block 就有機會被重用

    • 若沒有找到 rbnode_t ， 就透過 get_heap 來配置記憶體空間
      • 若可用的記憶體空間不足時就透過 sbrk 來真正配置不小於 size 的 n 倍 pagesize 空間
      • 若可用的空間充足就從目前配置到的記憶體地址 end_in_page 配置新的 in-use block 並與前一個 block 相連，在更新 malloc_t
  • 最後透過 GET_PAYLOAD 回傳使用者實際能使用的記憶體地址
Last changed by 
 
Korin777
0
518

Read more

2023q1 Homework7 (ktcp)

contributed by &lt; Korin777 &gt; 開發環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 39 bits physical, 48 bits virtual Byte Order: Little Endian

May 8, 2023
2023q1 Homework4 (quiz4)

contributed by &lt; Korin777 &gt; 測驗題目 測驗三 RB_LOG2_MAX_NODES node_t 的大小為 sizeof(void*) * 4 所以 node 最多有 $$\frac{1 &lt;&lt; (sizeof(void ) &lt;&lt; 3)} {(sizeof(void) * 4)}$$ 取 log2 可以得到 RB_LOG2_MAX_MEM_BYTES - log2(sizeof(void*)*2) - 1，若 sizeof(void*) == 8 就會是 RB_LOG2_MAX_MEM_BYTES - 4 - 1 tree_insert 這裡透過 path 來記錄插入節點的所有祖先節點，所以節點不須記錄自己的親代節點也能在插入後向上修復紅黑數，遇到黑色節點就可以停下，因為只有紅色節點可能會違反規則

Apr 8, 2023
2023q1 Homework3 (quiz3)

contributed by &lt; Korin777 &gt; 測驗四 int ceil_log2(uint32_t x) { uint32_t r, shift; x--; r = (x &gt; 0xFFFF) &lt;&lt; 4; x &gt;&gt;= r;

Mar 15, 2023
2023q1 Homework2 (quiz2)

contributed by &lt; Korin777 &gt; 測驗三 size_t swar_count_utf8(const char *buf, size_t len) { const uint64_t *qword = (const uint64_t *) buf; const uint64_t *end = qword + len &gt;&gt; 3; size_t count = 0; for (; qword != end; qword++) {

Mar 15, 2023
Read more from Korin777
Published on HackMD