---
# System prepended metadata

title: 「你所不知道的C語言：記憶體管理、對齊及硬體特性」 筆記
tags: [System Software, Computer Science]

---

---
title: 「你所不知道的C語言：記憶體管理、對齊及硬體特性」 筆記
tags: Computer Science,System Software
description: 2019.08.15
---
「你所不知道的C語言：記憶體管理、對齊及硬體特性」 筆記
===
###### 2019.08.15 *Copyright © 2019 by srhuang*

![](https://i.imgur.com/1lMjXUR.png)

[影片](https://youtu.be/v2Lj7lI_7ig)
[講義](http://hackfoldr.org/dykc/https%253A%252F%252Fhackmd.io%252Fs%252FBkuMDQ9K7)
Original by [jserv](http://wiki.csie.ncku.edu.tw/User/jserv)

---

## 背景知識
* C99/C11 規格書：https://youtu.be/v2Lj7lI_7ig?t=75
    * 指標大小。
    * 指標轉型：C 語言不保證你可以安全地轉換 void * 為任意型態後，再轉換回原本的型態。
    * void * 存在的目的就是為了強迫使用者使用 顯式轉型 或是 強制轉型，以避免 Undeined behavior 產生。
* 複習函式呼叫篇：https://youtu.be/v2Lj7lI_7ig?t=434
    * malloc/free 的記憶體配置。

## 你可能沒想過的 Memory
* Memory Hierarchy：https://youtu.be/v2Lj7lI_7ig?t=705
* What a C programmer should know about memory：https://youtu.be/v2Lj7lI_7ig?t=868
    * What every programmer should know about memory 的重點整理
    * Understanding virtual memory：https://youtu.be/v2Lj7lI_7ig?t=1158
        * 現代銀行和虛擬記憶體兩者高度相似。
        * overcommiting。
        * 在使用 malloc 要檢查返回值。
        * OOM Killer。
    * Understanding stack allocation：https://youtu.be/v2Lj7lI_7ig?t=1590
        * alloca：在 stack 中配置空間，以達到自動釋放空間的能力。並非標準使用。
        * VLA (variable-length arrays)：執行時期在知道 array 大小，實作也是在 stack 裡面。
            * linux kernel 明文規定不准使用 VLA，因為有安全性疑慮。
    * Slab allocator：https://youtu.be/v2Lj7lI_7ig?t=2018
        * 最早是在 solaris(sunos) 上發展。
        * Linux Slub。
        * 目的是去善用 cache memory。
        * ![](https://i.imgur.com/LbbJA9E.png)

        * 避免碎片化和記憶體浪費。
    * Demand paging：https://youtu.be/v2Lj7lI_7ig?t=2258
        * Linux系統提供一系列的記憶體管理API。
        * mlock：禁止被 swapped out (向 OS 提出需求，OS 不一定會理)。
        * madvise：提供管道告訴系統page管理方式。不是標準。
            * Kernel Samepage Merging (KSM) for virtualization。
        * lazy loading：allocate記憶體先給位址。等到process要存取的時候OS就會發現存取到沒摸過的記憶體，於是就產生page fault，這時候才去處理page分配的問題。
    * copy-on-write：https://youtu.be/v2Lj7lI_7ig?t=3260
        * mmap：把檔案映射到記憶體。
        * 如果有多個呼叫者（callers）同時請求相同資源（如記憶體或磁碟上的資料儲存），他們會共同取得相同的指標指向相同的資源，直到某個呼叫者試圖修改資源的內容時，系統才會真正複製一份專用副本（private copy）給該呼叫者。
* 補充資料：https://youtu.be/v2Lj7lI_7ig?t=3447
    * 現代處理器設計: Cache 原理和實際影響
    * Cache 原理和實際影響: 進行 CPU caches 中文重點提示並且重現對應的實驗。
    * 針對多執行緒環境設計的 Memory allocator
    * rpmalloc 探討：可以在多執行緒的環境下有更好的表現。

## 重新看 Heap
* 簡介：https://youtu.be/v2Lj7lI_7ig?t=3681
    * memory pool。

## data alignment
* data object：https://youtu.be/v2Lj7lI_7ig?t=3828
    * 有兩個特性：value and storage location。
* data alignment：https://youtu.be/v2Lj7lI_7ig?t=3869
    * misaligned data 有可能導致兩次的 fetch。
* #pragma pack：https://youtu.be/v2Lj7lI_7ig?t=4332
    * 給 GCC 編譯器看的。
    * #pragma pack：https://blog.gtwang.org/programming/c-language-pragma-pack-tutorial-and-examples/
    * #pragma pack 這個預處理指令，它可以指定 C 語言編譯器在處理記憶體對齊時，所使用的記憶體封裝長度，單位為位元組（byte）。
    * padding：對於 struct 做補齊資料以符合 alignment。
    * #pragma pack (pop)：還原。
* malloc alignment：https://youtu.be/v2Lj7lI_7ig?t=4771
* Unaligned memory access
    * unaligned_get32 函式的實作：https://youtu.be/v2Lj7lI_7ig?t=4909
    * Linux kernel: unaligned memory access：https://youtu.be/v2Lj7lI_7ig?t=5197
    * Interleaved Pixel Lookup for Embedded Computer Vision：https://youtu.be/v2Lj7lI_7ig?t=5405

## glibc 的 malloc/free 實作
* Deterministic Memory Allocation for Mission-Critical Linux：https://youtu.be/v2Lj7lI_7ig?t=5579
    * QB50：歐盟衛星計畫。
    * ARRC 前瞻火箭。
    * Real-time System：設計即時作業系統的首要目標不是高的吞吐量，而是保證任務在特定時間內完成。
    * Memory allocator：scale up and stable.
    * Heap operations are in conflict with the main demand of real-time systems.
    * Structure-aware allocator.
    * Memory pool with reference counter.
    * How to measure allocators? Using ACDC.
    * Allocators：
        * PTMalloc (glibc)
        * TCMalloc (google)
        * jeMalloc (FB)
        * DMalloc
* Memory request size：https://youtu.be/v2Lj7lI_7ig?t=7166
    * 小request(<= 64 bytes)：cache locality，保留一系列固定大小區塊的list以利迅速回收再使用。
    * 大request(>= 512 bytes)：使用best-fit的策略。其他有 First-fit。
    * 極大的request(>= 128KB by default)：直接使用mmap()，讓memory management解決。
        * mmap：把檔案對映到記憶體。
* arena and thread：https://youtu.be/v2Lj7lI_7ig?t=7447
    * arena即為malloc從系統取得的連續記憶體區域，分為main arena與thread arena兩種。
* malloc 流程：https://youtu.be/v2Lj7lI_7ig?t=7737
    * 調整malloc size : 加上overhead並對齊。
* free 流程：https://youtu.be/v2Lj7lI_7ig?t=7992
    * 檢查pointer位址、alignment、flag等等，以確認是可free的memory。
* mallinfo() example：https://youtu.be/v2Lj7lI_7ig?t=8241

## 案例分析: concurrent-ll
* concurrent-ll：https://youtu.be/v2Lj7lI_7ig?t=8420
    * lock free 可以降低沒有必要的等待。
    * 測試程式會使用多個 Threads 並且 random 執行 add/delete。
    * compare-and-swap(CAS) is an atomic operation.
    * intptr_t：Integer types capable of holding object pointers.
* aligned_alloc：https://youtu.be/v2Lj7lI_7ig?t=9305
    * posix_memalign

## 總結：https://youtu.be/v2Lj7lI_7ig?t=9661