開始系統的學習linux內核了,手頭的參考書是<<深入理解linux內核>>第三版,里面是基于2.6.11版來講解的,所以我這里的筆記也是基于這個版本.我的目的是將該書中我覺得講的不太詳細或者可以展開討論理解的地方寫出來供別人參考.計劃三個月內精讀完該書,爭取每周更新約三次筆記.
其它的參考資料還有:
<<深入理解計算機系統>>
<<linux內核情景分析>>上冊
<<Linux內核設計與實現>>
<<Linux內核完全剖析>>
<<UNIX操作系統設計>>
這幾本書都是看到相關部分時拿出來的參考資料,閱讀還是以<<深入理解linux內核>>為主展開.
==================分割線=====================
熟悉unix的人都知道,進程號也就是pid實際上是整型的數據,每次創建一個新的進程就返回一個id號,這個id號一直遞增,直到最大的時候開始"回繞",也就是從0開始尋找當前最小的可用的pid.
linux內核中,采用位圖來實現pid的分配與釋放.簡單的說,就是分配一個與系統最大pid數目相同大小的位圖,每次分配了一個pid,就將位圖中的相應位置置1;釋放則置0;回繞的時候則從0開始繼續前面的查找,如果遍歷了整個位圖都找不到,那么返回-1.
我將內核中相關部分的代碼提取出來寫了一個簡單的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))
{
// 到整百時釋放一次pid,看回繞的時候是不是都是使用整百的pid
free_pidmap(i);
}
}
return 0;
}
說明幾點:
1) 內核中對應的代碼在pid.c和bitops.h文件中.
2) 這里的幾個位操作函數實現linux內核中基于不同的CPU架構分別都做了優化,有的用到了匯編,我這里使用純C語言完成這幾個函數.但是我想,不論是C還是匯編,這里隱含的算法思想都是一樣的(見下面提到的第四點),在算法確定了之后,再針對可以優化的地方去做優化.
3) 代碼里面還做了一些簡化,內核中pidmap對象可能是數組,但是這里的實現只有一個pidmap對象.
4) "位圖"是非常常見的數據結構,一般適用于如下的場景:
首先,需要分配/釋放的數據是整型相關的;其次,它們是連續的,從0開始的;最后,它們的狀態只有兩種:分配或者空閑.回頭看看pid的這個場景,滿足了使用位圖的情況.在其它的一些書籍中,比如<<編程珠璣>>,也提到了位圖算法,它那里的場景與這里類似.
5) 位操作我還不是很熟悉,寫這幾個位操作算法費了不少功夫.