开始系统的学习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) 位操作我还不是很熟悉,写这几个位操作算法费了不少功夫.