[Linux Kernel] Allocate memory buffer whose starting address is aligned with the specific memory size

撰寫裝置驅動程式時, 常常會因為硬體需求, 需配置一塊記憶體空間用來映射至硬體的I/O或記憶體空間, 且此已配置記憶體空間的起始位址往往都必須對齊某一固定大小的記憶體。舉例來說，欲配置4906位元的記憶體空間，且起始位址需對齊16位元。底下為C語言範例程式。

void *memory_align(unsigned int size, unsigned int aligned_size)

{

    void *ptr;



    unsigned int mask = ~(aligned_size -1);



    if((ptr = malloc(sizeof(size + (aligned_size - 1)))) == NULL) {

        perror("memory allocation failed");

        return NULL;

    }



    ptr = (void *) ((unsigned int) (ptr + (aligned_size - 1)) & mask);



    return ptr;

}

unsigned int mask = ~(aligned_size -1);

此mask變數為位元遮罩, 假設aligned_size=16, 則mask=0xFFFFFFF0。

ptr = malloc(sizeof(size + (aligned_size - 1)))

由於我們欲讓所配置的記憶體起始位址對齊aligned_size, 所以需向系統配置size+(aligned_size - 1)大小的記憶體空間。

ptr = (void *) ((unsigned int) (ptr + (aligned_size - 1)) & mask);

把所配置的記憶體起始位址加上(aligned_size - 1)，然後跟mask變數做位元遮罩，如此便能取得正確的記憶體起始位址。

下圖為詳細範例計算

範例程式下載

Google大神開始對Linux Kernel Source貢獻了

Linux 2.6.35有Google大神的程式碼了!! (跪拜0rz......)
其主要提升網路封包處理速度
詳見: Linux 2.6.35 Includes Speedy Google Code, Less Bloat

簡介Linux Block I/O Layer (三) - I/O Path

此系列文章最後講解Block I/O Layer I/O Path運作原理。圖一為I/O Path簡易圖，檔案系統核心經由submit_bio函式將該bio交給Block I/O Layer的generic_make_request和__generic_make_request函式，緊接著呼叫__make_request_fn callback函式 (對應至__make_request())，此函式主要目的用來檢查此bio是否可以跟尚未處理的request結構的bio成員結合在一起 (merge)，如果不行的話，則另外配置一個新的request結構並將其bio安插至該reqeust結構，再將該request交給I/O Scheduler，最後Block I/O Layer經由request_fn() callback function將待處理的request交給SCSI子系統。


                               圖一、Block I/O Layer之I/O Path簡易圖


下圖二為Linux Block I/O Layer核心I/O Path示意圖，此圖以ReiserFS為例，此圖對每個函式有詳細的解釋，所以在此不再解釋，請參照圖二。


                               圖二、Block I/O Layer之I/O Path


【Reference】
1. Linux Device Driver, third edition
2. Linux Kernel Source 2.6.31
3. Request-based Device-mapper multipath and Dynamic load balancing
4. Understanding the Linux Kernel, Third Edition - Chapter 14. Block Device Drivers

簡介Linux Block I/O Layer (二) - 探討BIO (Block I/O) and Request 結構

上一篇文章簡單介紹page, bio和request結構的定位，本篇文章著重於探討bio與request結構是如何串起來的。底下將分別介紹reqeust queue、request、bio與bio_vec等資料結構。首先，下圖展示這四個資料結構的關係。



Request Queue
Request Queue用來將待處理的request串成一個雙向的鏈結串列，此結構 (struct request_queue)定義在include/linux/blkdev.h檔頭檔。

Request
一個request資料結構，即表示一次block I/O傳輸請求。結構裡的queuelist便是將整個request串起來的成員，bio成員代表該request所欲傳輸block I/O個數，buffer成員代表當前資料傳輸的buffer區塊。request資料結構裡還有許多其它成員，詳見include/linux/blkdev.h標頭檔。

BIO (Block I/O)
當block I/O layer上層 (可參考此篇文章的圖，Ex: 檔案系統或虛擬記憶體子系統)欲傳輸某一區塊時，該層便會產生一個bio結構並交由Block I/O Layer，Block I/O Layer將新請求的bio併入現有的request結構裡 (前提是該request結構裡的bio所欲傳輸的區塊磁區剛好跟新請求的bio所欲傳輸的區塊磁區相近，如此變能發揮更大的傳輸效益)，或者產生一個新的request結構並將此bio併入此request結構，此結構 (struct request_queue)定義在include/linux/bio.h標頭檔。

bio_vec (BIO Vector)
bio結構裡有一個稱為bi_io_vec一維陣列的成員，該陣列成員紀錄欲傳輸的資料緩衝區在記憶體何處。

【Reference】
1. Linux Device Driver, third edition
2. Linux Kernel Source 2.6.31
3. Request-based Device-mapper multipath and Dynamic load balancing
4. Understanding the Linux Kernel, Third Edition - Chapter 14. Block Device Drivers

簡介Linux Block I/O Layer (一) - Page, BIO (Block I/O) and Request 結構意義

Linux Block I/O Layer主要處理上層檔案系統的請求，進而將該請求往丟至低層的low-level device driver (例如: Linux SCSI Subsystem)，下圖展示出這三層的關係，由圖中可知檔案系統驅動程式主要以page結構來描述所欲存取的資料在哪裡, 接著檔案系統驅動程式將page結構轉換bio (Block I/O)，並經由submit_bio函式將該請求送至Block I/O Layer，該層主要任務便將bio結構轉換成request結構 (往後會有幾篇探討該層運作細節)，並將該request結構丟至low-level device driver，以上是簡單的介紹.



【Reference】
1. Linux Device Driver, third edition
2. Linux Kernel Source 2.6.31
3. Request-based Device-mapper multipath and Dynamic load balancing

Linux Kernel: container_of 巨集

Linux驅動程式裡很常看container_of巨集，其目的為何呢? 假設Linux驅動程式只知道某一結構成員的位址，該驅動程式便可使用container_of巨集，將已知某一結構成員的位址計算出該結構的起始位址，其原型如下:

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

#define container_of(ptr, type, member) ({ \
     const typeof( ((type *)0)->member ) *__mptr = (ptr); \
     (type *)( (char *)__mptr - offsetof(type,member) );})

假設有一結構定義如下，且我們只知道phone_num成員的位址，如此便能使用該巨集計算出該結構變數的起始位址:

/* The student structure definition */
typedef struct student {
     char name[16];
     int id;
     char addr[64];
     char phone_num[16];
}STUDENT, *STUDENT_PTR;

該結構記憶體配置圖如下所示:


Figure 1. 結構記憶體配置圖

範例程式碼:

Figure 2. 範例程式碼


以此結構為範例來看containter_of巨集的兩行程式碼:

◎ const typeof( ((type *)0)->member ) *__mptr = (ptr); ==> 得到phone_num的位址 (x+84) ，請參考Figure 1跟Figure 2。
◎ (type *)( (char *)__mptr - offsetof(type,member) ); → (type *)( (char *)__mptr - ((size_t) &((type *)0)->member) ); ==> 其中((size_t) &((type *)0)->member)這段敘述代表以零為起始位址算出member這個成員的相對位址，即為phone_num成員的相對位址，也就是84 (請參考Figure 1)。所以整個敘述變成 (x+84) - 84 = x ，如此便能取得該結構變數的起始位址。

範例程式

Linux Kernel: Lookaside Cache (前瞻快取)

驅動程式往往根據使用者請求一次又一次地配置相同記憶體大小的物件。為此，Linux核心提供此需求的機制 - Lookaside cache。而此機制稱為Slab Allocator。

以SCSI驅動程式為例，當使用者要讀寫硬碟資料時，會由區塊裝置驅動程式 (Block Device Driver)向SCSI層發出請求，SCSI層將此請求轉換成SCSI command的結構 (struct scsi_cmnd)，為了能快速配置與存取SCSI command，SCSI層驅動程式為每一個SCSI command結構配置lookaside cache。其用法如下:

1. 首先，必須先配置一個快取物件導向，其函式: struct kmem_cache *
kmem_cache_create (const char *name, size_t size, size_t align,
unsigned long flags, void (*ctor)(void *))


    ◎ name: 此快取物件名稱，此名稱會出現在/proc/slabinfo。
    ◎ size: 物件大小。
    ◎ align: 對齊字元數大小，通常為零。
    ◎ flag: 配置物件的方式，詳見include/linux/slab.h。
    ◎ ctor: 建構子函式位址。當核心成功地配置物件後，便會呼叫此函式。

2. 接著，呼叫kmem_cache_alloc，配置每一個物件，其原型: void *kmem_cache_alloc(struct kmem_cache *cachep, gfp_t flags);

    ◎ cachep: kmem_cache_create回傳的位址。
    ◎ flags： 詳見kmalloc的flags參數。

3. 釋放記憶體:
void kmem_cache_free(struct kmem_cache *cachep, void *objp)
→ 釋放物件，但並未釋放快取。
void kmem_cache_destroy(struct kmem_cache *cachep) → 釋放快取。

範例 (取自Linux SCSI驅動程式):


【Reference】
1. Linux Device Driver, third edition
2. Linux Kernel Source 2.6.31

Linux Kernel: __init, __initdata屬性

在trace Linux核心原始碼很常看到__init和__initdata兩個屬性。其原型如下:

#define __init __section(.init.text) __cold notrace
#define __initdata __section(.init.data)

只要函數被定義__init屬性，代表此函數的所有內容被編譯器放置在.init.text節區。此節區代表該函數只會執行一次，此後就不會再執行，因此執行完該函數，核心會將該函數所佔記憶體空間釋放出來。__init屬性非常適合裝置驅動程式的init_module函數，其範例宣告如下:

static int __init dm_init(void); (from linux-source-2.6.31/drivers/md/dm.c)

利用objdump觀察dm_init函數被放置在哪個節區:

adrian@adrian-laptop:/usr/src/linux-source-2.6.31$ objdump -x drivers/md/built-in.o | grep md_init
00000000 l F .init.text 000000de md_init
00000000 l O .initcall4.init 00000004 __initcall_md_init4

__initdata屬性跟__init屬性的作用大同小異，唯一不同在於前者放置在.init.data節區。

範例:

static int (*_inits[])(void) __initdata = {
     local_init,
     dm_target_init,
     dm_linear_init,
     dm_stripe_init,
     dm_kcopyd_init,
     dm_interface_init,
};

利用objdump觀察_inits變數被放置在哪個節區:

adrian@adrian-laptop:/usr/src/linux-source-2.6.31$ objdump -x drivers/md/built-in.o | grep _inits
00000000 l O .init.data 00000018 _inits

問題來了，釋放記憶體的工作由核心的哪一函數負責呢? 答案是: free_initmem (arch/x86/mm/init.c)

【Reference】
FAQ/InitExitMacros
Linux Kernel Source 2.6.31

An Introduction to Linux Kernel Booting Sequence Part 3

上篇文章提到go_to_protected_mode函式最後會執行由組合語言所撰寫的函式protected_mode_jump，此函式工作如下:

函式呼叫原型:
protected_mode_jump(boot_params.hdr.code32_start, (u32)&boot_params + (ds() << 4));

其程式碼:

/*
* void protected_mode_jump(u32 entrypoint, u32 bootparams);
*/
GLOBAL(protected_mode_jump)
movl %edx, %esi # Pointer to boot_params table

xorl %ebx, %ebx
movw %cs, %bx
shll $4, %ebx
addl %ebx, 2f
jmp 1f # Short jump to serialize on 386/486
1:

movw $__BOOT_DS, %cx
movw $__BOOT_TSS, %di

### 設定x86之cr0暫存器的PE位元，如此便能進入proctected-mode
movl %cr0, %edx
orb $X86_CR0_PE, %dl # Protected mode
movl %edx, %cr0

# Transition to 32-bit mode
.byte 0x66, 0xea # ljmpl opcode
2: .long in_pm32 # offset
.word __BOOT_CS # segment
ENDPROC(protected_mode_jump)

.code32
.section ".text32","ax"
GLOBAL(in_pm32)
# Set up data segments for flat 32-bit mode
movl %ecx, %ds
movl %ecx, %es
movl %ecx, %fs
movl %ecx, %gs
movl %ecx, %ss
# The 32-bit code sets up its own stack, but this way we do have
# a valid stack if some debugging hack wants to use it.
addl %ebx, %esp

# Set up TR to make Intel VT happy
ltr %di

# Clear registers to allow for future extensions to the
# 32-bit boot protocol
xorl %ecx, %ecx
xorl %edx, %edx
xorl %ebx, %ebx
xorl %ebp, %ebp
xorl %edi, %edi

# Set up LDTR to make Intel VT happy
lldt %cx

## 跳至code32_start的標籤
jmpl *%eax # Jump to the 32-bit entrypoint
ENDPROC(in_pm32)

至於code32_start在哪裡呢? 此標籤定義在arch/x86/boot/header.S，如下所示:

code32_start: # here loaders can put a different
# start address for 32-bit code.
.long 0x100000 # 0x100000 = default for big kernel

也就是說，核心已做完real-mode Linux程式碼該做的事情，並跳至protected-mode Linux程式碼的起始位址 (1MB)，請看下圖:



[Reference]
【The Kernel Boot Process】
【Linux Kernel Source 2.6.31】

An Introduction to Linux Kernel Booting Sequence Part 2

上篇文章Linux核心被載入記憶體並執行start_of_setup標籤(arch/x86/boot/header.S)，在start_of_setup標籤末段會執行由C語言撰寫的main函式 (arch/x86/boot/main.c)，此函式工作如下所示:

1. 複製開機標頭 (boot header) 至 zero page
2. 設定heap_end變數
3. 偵測記憶體layout
4. 設定鍵盤重複率 (Keyboard Repeat Rate)
5. 查詢MCA (Micro Channel Architecture) 資訊
6. 查詢Intel SpeedStep
7. 設定video模式
8. 進入protected-mode (go_to_protected_mode，arch/x86/boot/pm.c)

其中3-6項，經由BIOS呼叫 (intcall，arch/x86/boot/bioscall.S)，以便向BIOS取到相關的資訊。
main函式最後呼叫go_to_protected_mode函式，以便從real-mode轉換至protected-mode。

在真正進入protected-mode之前，有幾項工作必須先被執行，也就是go_to_protected_mode函式裡所做的事情，如下所示:

1. 設定A20位址線，如此便能存取超過1MB以後的資料 (因為在real-mode，只能存取1MB以下的資料)。

2. 設定idt (interrupt descriptor table)。在real-mode，interrupt vector table的起始位址是從記憶體零的位址開始算起。然而，在protected-mode，interrupt vector table是儲存於CPU的暫存器 (IDTR，Interrupt Descriptor Table Register)，因此轉換至protected-mode之前，必須先設定idt。

3. 設定gdt (global descriptor table)。由於，real-mode與proctected-mode位址轉換 (由邏輯位址 [logical address] 轉換成線性位址 [linear address])，詳見x86_memory_segmentation。因此轉換至protected-mode之前，必須先設定gdt，以便能正確地根據logical address轉換成linear address。

在go_to_protected_mode函式最後會執行由組合語言所撰寫的函式protected_mode_jump，此函式便是設定CPU為protected-mode，細節留到下回做進一步解釋。

【Reference】 The Kernel Boot Process

An Introduction to Linux Kernel Booting Sequence Part 1

此系列文章將著重於探討Linux x86核心開機過程,
其中, 假設BIOS跟Boot Loader (GRUB, for example) 運行正常, 且Boot Loader已將核心 (/boot/vmlinuz-2.6.31-16-generic) 載入記憶體並跳至載入記憶體之起始位置執行.

Linux核心主要可以分為兩大部份: 1. 執行於CPU之real mode的核心程式碼 2. 執行於CPU之protected mode的核心程式碼. 然而這兩大部份被載入至不同的記憶體區段: 1. real mode核心程式碼載入至0-640KB的某一區間, 2. protected mode核心程式碼載入至1MB記憶體位址. 如下所示:



Figure 1. Linux kernel RAM content after loading the Linux kernel image into RAM


首先第一個被執行的Linux核心檔案為arch/x86/boot/header.S，此檔案由組合語言所撰寫，此檔案前512位元組 (其中有15個位元組為核心標頭) 為早期的核心開機磁區，但現今的boot loader直接跳過此512位元組。緊接著在512位元組之後，即為Linux核心執行的起始點，底下展示此起始點的兩行程式碼 (以Linux核心原始碼版本2.6.31為例)：

.byte 0xeb # short (2-byte) jump
.byte start_of_setup-1f

此兩行代表跳至start_of_setup標籤。".byte 0xeb" (arch/x86/boot/header.S:112)代表two-bytes jmp組合語言指令。".byte start_of_setup-1f" (arch/x86/boot/header.S:113)的"f"代表forward short jump，"start_of_setup-1"代表用"start_of_setup" (arch/x86/boot/header.S:241)標籤起始位址減去"1" (arch/x86/boot/header.S:114)標籤起始位址。

所以上述兩個位元組即代表： 以目前的位址向下跳至n個位元組 (即start_of_setup-1)，因此便能正確地跳至start_of_setup標籤。

範例 (以Ubuntu 9.10之2.6.31-16-generic核心為例)

此範例利用hexdump將Linux核心dump出來，並觀看其16進制碼用以對照上述之論述。

adrian@adrian-desktop:/boot$ hexdump vmlinuz-2.6.31-16-generic > ~/vmlinuz-2.6.31-16-generic-hexdump
adrian@adrian-desktop:/boot$ gvim ~/vmlinuz-2.6.31-16-generic-hexdump

其結果如下所示:

Figure 2. Hexdump from Linux Kernel

其中，0xAA55為Linux早期的核心開機磁區最後一個位元組(第512個位元組，arch/x86/boot/header.S:103)。0x62eb代表往下跳至62個位元組，即0x00000262位址。

本篇文章只介紹Linux之real-mode核心程式碼的entry point，往後會有陸陸續續的文章繼續探討。

【Reference】
The Kernel Boot Process

likely() and unlikely() macro in Linux kernel

Linux核心原始碼，經常出現兩個巨集：likely() and unlikely()，如下所示:

#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

重點就是__builtin_expect這個函式的意義。此函式用來告訴編譯器，哪些程式區段可做預測。
底下為__builtin_expect的原型:

long __builtin_expect(long EXP, long C)
此函式__builtin_expect有兩大重點:

1. __builtin_expect的回傳值即EXP這個判斷式。
2. __builtin_expect語意上，是期待(EXP == C)。

例子一:
if (__builtin_expect(x, 1))
    do_something();

此敘述告知編譯器，x變數期待是1 (上述重點2), 且由於x=1, 所以__builtin_expect回傳值便是1(上述重點1)，因此編譯器可以大膽預測do_something()一定會被執行到。因此便能將處理器的管線(Pipe Line)功能發揮的淋漓盡致。

例子二:
if (__builtin_expect(x, 0))
    do_something1();
else
    do_something2();

此敘述告知編譯器，x變數期待是0 (上述重點2), 且由於x=0, 所以__builtin_expect回傳值便是0(上述重點1)，因此編譯器可以大膽預測do_something2()一定會被執行到，而不是預測執行do_something1()。

總結likely()與unlikely()巨集:

if(likely(x)) {
    預測想要執行的原始碼
} else {
}

if(unlikely(x)) {
} else {
    預測想要執行的原始碼
}

[Reference]
1. FAQ/LikelyUnlikely
2. richliu's blog