---
tags: 你所不知道的 C 語言, 進階電腦系統理論與實作, NCKU Linux Kernel Internals, 作業系統
---

# 記憶體管理、未定義行為
contributed by <`RusselCK` >

###### tags: `RusselCK`

## [記憶體管理](https://hackmd.io/@sysprog/c-memory?type=view)

### alignment、pedding、pack

---

參照 [What a C programmer should know about memory](https://marek.vavrusa.com/memory/) ([簡記](http://wen00072.github.io/blog/2015/08/08/notes-what-a-c-programmer-should-know-about-memory/))

* Understanding virtual memory - the plot thickens
> The virtual memory allocator (VMA) may give you a memory it doesn’t have, all in a vain hope that you’re not going to use it. Just like banks today
:::info
1. 現代銀行和虛擬記憶體兩者高度相似
2. malloc 給 valid pointer不要太高興，等你要開始用的時候搞不好作業系統給個 OOM。簡單來說就是一張支票，能不能拿來開等到兌現才知道
:::

---

malloc 本來配置出來的記憶體位置就有做 alignment，根據 malloc 的 man page 裡提到 :
> The malloc() and calloc() functions return a pointer to the allocated memory, which is
suitably aligned for any built-in type.

實際上到底 malloc 做了怎樣的 data alignment，繼續翻閱 [The GNU C Library - Malloc Example](ftp://ftp.gnu.org/old-gnu/Manuals/glibc-2.2.3/html_node/libc_25.html)，裡面有特別提到 :
> In the GNU system, the address is always a multiple of eight on most systems, and a multiple of 16 on 64-bit systems.

這句我就有看懂，所以說在大多數系統下，malloc 會以 8 bytes 進行對齊；而在 64-bit 的系統下，malloc 則會以 16 bytes 進行對齊。

考慮以下 `unaligned_get32` 函式的實作: (假設硬體架構為 32-bits)

#include <stdint.h>
#include <stddef.h>
uint8_t unaligned_get8(void *src) {
    uintptr_t csrc = (uintptr_t) src;
    uint32_t v = *(uint32_t *) (csrc & 0xfffffffc);
    v = (v >> (((uint32_t) csrc & 0x3) * 8)) & 0x000000ff;
    return v;
}
uint32_t unaligned_get32(void *src) {
    uint32_t d = 0;
    uintptr_t csrc = (uintptr_t) src;
    for (int n = 0; n < 4; n++) {
        uint32_t v = unaligned_get8((void *) csrc);
        v = v << (n * 8);
        d = d | v;
        csrc++;
    }
    return d;
}

對應的 `unaligned_set32` 函式:

void unaligned_set8(void *dest, uint8_t value) {
    uintptr_t cdest = (uintptr_t) dest;
    uint32_t d = *(uint32_t *) (cdest & 0xfffffffc);
    uint32_t v = value;
    for (int n = 0; n < 4; n++) {
        uint32_t v = unaligned_get8((void *) csrc);
        v = v << (n * 8);
        d = d | v;
        csrc++;
    }
    return d;
}
void unaligned_set32(void *dest, uint32_t value) {
    uintptr_t cdest = (uintptr_t) dest;
    for (int n = 0; n < 4; n++) {
        unaligned_set8((void *) cdest, value & 0x000000ff);
        value = value >> 8;
        cdest++;
    }
}

---
**malloc流程**

* 調整 malloc size : 加上 overhead 並對齊，若 < 32 byte(64bit 最小 size，4 pointers)則補上
* 檢查 fastbin : 若對應 bin size 有符合 chunk 即 return chunk
* 檢查 smallbin : 若對應 bin size 有符合 chunk 即 return chunk
* 合併(consolidate) fastbin : (若 size 符合 large bin 或前項失敗)呼叫 malloc_consolidate 進行 fastbin 的合併(取消下一 chunk 的 PREV_INUSE)，並將合併的 bin 歸入 unsorted
* 處理 unsorted bin :
* 若 unsorted bin 中只有 last_remainder 且大小足夠，分割 last_remainder 並return chunk。剩下的空間則成為新的 last_remainder
* loop 每個 unsorted bin chunk，若大小剛好則 return，否則將此 chunk 放至對1應 size 的 bin 中。此過程直到 unsorted bin 為空或 loop 10000次為止
* 在 small / large bin 找 best fit，若成功則 return 分割的 chunk，剩下的放入 unsorted bin（成為 last_remainder）；若無，則繼續 loop unsorted bin，直到其為空
* 使用 top chunk : 分割 top chunk，若 size 不夠則合併 fastbin，若仍不夠則 system call

**free流程**

* 檢查 : 檢查 pointer 位址、alignment、flag 等等，以確認是可 free 的 memory
* 合併(consolidate)
* fastbin size : 不進行合併
* 其他 :
* 檢查前一 chunk，若未使用則合併
* 檢查後一 chunk，若是 top chunk 則整塊併入 top chunk，若否但未使用，則合併
* 將合併結果放入 unsorted bin

* ref : [allocation過程](http://brieflyx.me/2016/heap/glibc-heap/)
* **glibc malloc allocation informations**
* [mallinfo](http://man7.org/linux/man-pages/man3/mallinfo.3.html) - obtain memory allocation information
* [malloc_stats](http://man7.org/linux/man-pages/man3/malloc_stats.3.html) - print memory allocation statistics
* [malloc_info](http://man7.org/linux/man-pages/man3/malloc_info.3.html) - export malloc state to a stream

簡單測試 : malloc(40 * sizeof(int));

* mallinfo() [example](http://man7.org/linux/man-pages/man3/mallinfo.3.html#EXAMPLE)

   Total non-mmapped bytes (arena):       135168
   # of free chunks (ordblks):            1
   # of free fastbin blocks (smblks):     0
   # of mapped regions (hblks):           0
   Bytes in mapped regions (hblkhd):      0
   Max. total allocated space (usmblks):  0
   Free bytes held in fastbins (fsmblks): 0
   Total allocated space (uordblks):      176
   Total free space (fordblks):           134992
   Topmost releasable block (keepcost):   134992

---
## [未定義行為](https://hackmd.io/@sysprog/c-undefined-behavior?type=view)