C

C volatile Keyword

我們在開發 device driver 或是 embedded system applications 時很常用到 volatile 來宣告定義變數，藉此提示 compiler 此變數可能會被硬體或是 interrupt function 修改，因此當 compiler 進行 code optimization 時，要確保涉及到 volatile 變數的操作不會被更動到。（舉例來說，當 compiler 在進行分析時，發現此變數涉及的操作只有讀取但沒有寫入時，就有可能調整執行順序，以改善程式效能）。雖然這對開發者來說可能是很基本的知識，但我們最近還是踩到了小坑，因此這篇再一次的透過 C11 標準來複習 volatile 定義，並且說明可能會有的疑問。

C11 標準下的 volatile

首先，先從 C11 標準來了解 volatile 修飾字 (Linux Kernel Moving Ahead With Going From C89 To C11 Code)。

GCC malloc + memset Optimization

最近踩到 compiler optimization 的一個小坑，gcc5 版本以上，開啟 optimization level 2 時，會將 malloc + memeset 轉換成 calloc。看起來似乎蠻有道理的改善，卻因為我在進行客製化 malloc 時，沒有這注意到這點，導致最後程式執行的是 libc 的 calloc 而不是我的 wrap_malloc。

起因

使用 void *__wrap_malloc(size_t size) 將 malloc function 進行額外的處理 (How to wrap a system call (libc function) in Linux)，其中一段 code 為:

C extern keyword

最近在參與面試的時候，我方考了 extern 關鍵字，雖然這個關鍵字很常用，但是很少有應試者答的完整。因為自己也是韌體新手，因此就參照 ISO/IEC 9899:2011(C11) 的標準，把 extern 的定義和用法紀錄一下。

Declaration & Definition

在討論 extern 之前，先釐清 C 的 declaration 和 definition 差異性。在 C11: 6.7 Declarations 中有提到：

Declaration

A declaration specifies the interpretation and attributes of a set of identifiers.

Definition

A definition of an identifier is a declaration for that identifier that:

Implement Memory Allocator - Implicit Free List

前言

由前篇文章可以知道，使用 stack data structure 是最簡單的 memory allocator 入門寫法，但是卻會造成一些問題，例如不能任意順序 free 等。既然如此，我們就換成 list 來實作 memory allocator，解決使用 stack 實作的問題。

除了實作之外，也會討論到幾個實作 allocator 上遇到的問題，例如 sbrk，以及 minimum alignment。

Memory allocator 要素

在實作之前，先歸納一下 allocator 需求。 Computer Systems(book) 與 CS 4400 – Computer Systems 說明幾個 allocator 要素，包含：

1. Handling arbitrary request sequences
2. Aligning blocks (8 bytes on 32-bit and 16 bytes on 64-bit)
3. Not modifying allocated blocks (compaction is not allowed)
4. How does free know an allocated block’s size?
5. How is unallocated space represented?
6. How do we keep track of free blocks?
7. How do we choose an appropriate free block?

依照上列條件，可以知道 stack 形態的 allocator 其實並不能滿足基本 allocator 需求(例如：arbitrary request sequences)，因此後續在實作 implicit free list 的時候，也會根據上列來一一檢視是否有達成需求。

Implement Memory Allocator

前言

在很多程式語言都會看到 memory allocator，也可以看到陸續發表的 allocator 實作方式，例如 microsoft mimalloc。與其用看 source code 的方式來了解其原理，倒不如從基本學起，並且從實作過程中了解到為什麼他們要這樣設計 allocator。

原因

在程式開始執行時，我們可以預期會有兩塊 default memory space (system stack, heap) 分配，其中 system stack 負責存放 function return address 或是 local variable 等，而 processor 的 stack pointer 會指向 system stack 的初始位置(可能往下長或往上長)。另外的 heap 則是供 dynamic memory allocation 使用。

semaphore sem_post 在 glibc v2.0 v2.1 之比較

前言

在翻 futex man document 的時候，不小心看到 Linux Futex的设计与实现 這篇文章。文章中有提到在執行 sem_post 的時候，雖然沒有與其他 thread 競爭，還是會用到 fuxtex system call。當然文章中有提到原因，不過看了原因，覺得這看起來很明顯的效能問題，應該會被提出來並改進吧？後來翻了一下目前的 source code ，看到這個是 GLIBC_2_0 的版本（那篇文章也很久了，所以能想見當時的版本應該蠻舊的），而現在 GLIBC_2_1 就有把這部分改進，因此就來簡單記錄一下差異在哪裡吧～

Version

glibc 2.29

GLIBC_2_0 version

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int attribute_compat_text_section __old_sem_post (sem_t *sem)
{
  int *futex = (int *) sem;
  atomic_write_barrier ();
  (void) atomic_increment_val (futex);
  int err = lll_futex_wake(futex, 1, LLL_SHARED);
  if (__builtin_expect (err, 0) < 0)
    {
      __set_errno (-err);
      return -1;
    }
  return 0;
}

從 source code 可以看到，在將 sem value + 1 後，就直接使用 lll_futex_wake 呼叫 futex wake system call，其原因在文章內也有提到，是因為當 sem value 加 1 後，當時的機制並無法確認是否有其他 thread 正在 wait。