開始系統(tǒng)的學(xué)習(xí)linux內(nèi)核了,手頭的參考書是<<深入理解linux內(nèi)核>>第三版,里面是基于2.6.11版來講解的,所以我這里的筆記也是基于這個(gè)版本.我的目的是將該書中我覺得講的不太詳細(xì)或者可以展開討論理解的地方寫出來供別人參考.計(jì)劃三個(gè)月內(nèi)精讀完該書,爭取每周更新約三次筆記.
其它的參考資料還有:
<<深入理解計(jì)算機(jī)系統(tǒng)>>
<<linux內(nèi)核情景分析>>上冊(cè)
<<Linux內(nèi)核設(shè)計(jì)與實(shí)現(xiàn)>>
<<Linux內(nèi)核完全剖析>>
<<UNIX操作系統(tǒng)設(shè)計(jì)>>
這幾本書都是看到相關(guān)部分時(shí)拿出來的參考資料,閱讀還是以<<深入理解linux內(nèi)核>>為主展開.
==================分割線=====================
熟悉unix的人都知道,進(jìn)程號(hào)也就是pid實(shí)際上是整型的數(shù)據(jù),每次創(chuàng)建一個(gè)新的進(jìn)程就返回一個(gè)id號(hào),這個(gè)id號(hào)一直遞增,直到最大的時(shí)候開始"回繞",也就是從0開始尋找當(dāng)前最小的可用的pid.
linux內(nèi)核中,采用位圖來實(shí)現(xiàn)pid的分配與釋放.簡單的說,就是分配一個(gè)與系統(tǒng)最大pid數(shù)目相同大小的位圖,每次分配了一個(gè)pid,就將位圖中的相應(yīng)位置置1;釋放則置0;回繞的時(shí)候則從0開始繼續(xù)前面的查找,如果遍歷了整個(gè)位圖都找不到,那么返回-1.
我將內(nèi)核中相關(guān)部分的代碼提取出來寫了一個(gè)簡單的demo:
#include <stdio.h>
/* max pid, equal to 2^15=32768 */
#define PID_MAX_DEFAULT 0x8000
/* page size = 2^12 = 4K */
#define PAGE_SHIFT 12
#define PAGE_SIZE (1UL << PAGE_SHIFT)
#define BITS_PER_BYTE 8
#define BITS_PER_PAGE (PAGE_SIZE * BITS_PER_BYTE)
#define BITS_PER_PAGE_MASK (BITS_PER_PAGE - 1)
typedef struct pidmap
{
unsigned int nr_free;
char page[PID_MAX_DEFAULT];
} pidmap_t;
static pidmap_t pidmap = { PID_MAX_DEFAULT, {'0'} };
static int last_pid = -1;
static int test_and_set_bit(int offset, void *addr)
{
unsigned long mask = 1UL << (offset & (sizeof(unsigned long) * BITS_PER_BYTE - 1));
unsigned long *p = ((unsigned long*)addr) + (offset >> (sizeof(unsigned long) + 1));
unsigned long old = *p;
*p = old | mask;
return (old & mask) != 0;
}
static void clear_bit(int offset, void *addr)
{
unsigned long mask = 1UL << (offset & (sizeof(unsigned long) * BITS_PER_BYTE - 1));
unsigned long *p = ((unsigned long*)addr) + (offset >> (sizeof(unsigned long) + 1));
unsigned long old = *p;
*p = old & ~mask;
}
static int find_next_zero_bit(void *addr, int size, int offset)
{
unsigned long *p;
unsigned long mask;
while (offset < size)
{
p = ((unsigned long*)addr) + (offset >> (sizeof(unsigned long) + 1));
mask = 1UL << (offset & (sizeof(unsigned long) * BITS_PER_BYTE - 1));
if ((~(*p) & mask))
{
break;
}
++offset;
}
return offset;
}
static int alloc_pidmap()
{
int pid = last_pid + 1;
int offset = pid & BITS_PER_PAGE_MASK;
if (!pidmap.nr_free)
{
return -1;
}
offset = find_next_zero_bit(&pidmap.page, BITS_PER_PAGE, offset);
if (BITS_PER_PAGE != offset && !test_and_set_bit(offset, &pidmap.page))
{
--pidmap.nr_free;
last_pid = offset;
return offset;
}
return -1;
}
static void free_pidmap(int pid)
{
int offset = pid & BITS_PER_PAGE_MASK;
pidmap.nr_free++;
clear_bit(offset, &pidmap.page);
}
int main()
{
int i;
for (i = 0; i < PID_MAX_DEFAULT + 100; ++i)
{
printf("pid = %d\n", alloc_pidmap());
if (!(i % 100))
{
// 到整百時(shí)釋放一次pid,看回繞的時(shí)候是不是都是使用整百的pid
free_pidmap(i);
}
}
return 0;
}
說明幾點(diǎn):
1) 內(nèi)核中對(duì)應(yīng)的代碼在pid.c和bitops.h文件中.
2) 這里的幾個(gè)位操作函數(shù)實(shí)現(xiàn)linux內(nèi)核中基于不同的CPU架構(gòu)分別都做了優(yōu)化,有的用到了匯編,我這里使用純C語言完成這幾個(gè)函數(shù).但是我想,不論是C還是匯編,這里隱含的算法思想都是一樣的(見下面提到的第四點(diǎn)),在算法確定了之后,再針對(duì)可以優(yōu)化的地方去做優(yōu)化.
3) 代碼里面還做了一些簡化,內(nèi)核中pidmap對(duì)象可能是數(shù)組,但是這里的實(shí)現(xiàn)只有一個(gè)pidmap對(duì)象.
4) "位圖"是非常常見的數(shù)據(jù)結(jié)構(gòu),一般適用于如下的場(chǎng)景:
首先,需要分配/釋放的數(shù)據(jù)是整型相關(guān)的;其次,它們是連續(xù)的,從0開始的;最后,它們的狀態(tài)只有兩種:分配或者空閑.回頭看看pid的這個(gè)場(chǎng)景,滿足了使用位圖的情況.在其它的一些書籍中,比如<<編程珠璣>>,也提到了位圖算法,它那里的場(chǎng)景與這里類似.
5) 位操作我還不是很熟悉,寫這幾個(gè)位操作算法費(fèi)了不少功夫.