边跑边读LINUX KERNEL

hatname

2年前的读内核日记
start_kernel
第一部分 总体
1。start_kernel
       核心从/arch/kernel/head.s跳转出来后，进入init/main.c，的start-kernel函数。该函数初始化核心数据结构，页表等等，到时候在说吧。
    进入start-kernel的第一件事情就是,lock_kernel.本来流浪想跳过这些代码的阅读,不过发现里面MIMI还是很多,便写了两句.
lock_kernel和unlock_kernel。
    这两个家伙的作用是在smp上。锁住所有内核数据结构访问。对于单cpu来说他们什么也不干。
    lock_kernel的实现是使用spin_lock实现的。参数是global变量 kernel_flag ,2.6的核心增加了内核抢占机制,所以代码有点复杂，不过可以先不看抢占的东西，直接看自旋锁的实现。spin_lock的主要内容是spin_lock_string这个宏.
#define spin_lock_string
    "
1:        "
    "lock ; decb %0
        "
    "js 2f
"
    LOCK_SECTION_START("")
    "2:        "
    "rep;nop
        "
    "cmpb $0,%0
        "
    "jle 2b
        "
    "jmp 1b
"
    LOCK_SECTION_END
    结合unlock_kernel的spin_unlock_string来看.可以知道解锁的时候并不是象信号量一样把kernel_flag++,而是让kernel_flag=1;
#define spin_unlock_string
    "movb $1,%0"
        :"=m" (lock->lock) : : "memory"
spin_lock_string特点
    1.使用x86指令前缀lock从硬件上锁定总线.
    2.使用gcc的.subsection和.previous,把部分代码放到其他段中去.(流浪还不知道为什么要这样做).为了让菜鸟难过?
“The actual implementation of spin_lock is more complicated. The code at label 2, which is executed only if the spin lock is busy, is included in an auxiliary section so that in the most frequent case (free spin lock) the hardware cache is not filled with code that won't be executed. In our discussion, we omit these optimization details.”
    3."lock ; decb %0
        " 和"js 2f
之间不需要原子操作,任何中断程序都会恢复cpu的flag-register.
spin_unlock_string的类C代码如下.
void spin_unlock(int &lock_flag)
{
    lock_flag=1;
}
spin_lock_string的类C代码如下.
void spin_lock(int &lock_flag)
{
       int flag;
lp1:
    flag=(--lock_flag      //仅这一句为原子操作!!!!
       if(flag){
              while(lock_flag
                     nop;
              }
              goto lp1;
       }
}
解读汇编代码spin_lock_string
    1.使用原子操作把lock_flag减1.(别看,decb就一条指令,它有三个过程,从内存读lock_flag,把lock_flag-=1,把lock_flag放回内存.这三个过程要求是原子的)
    2.如果第一步结果不小于0,退出spin_lock,
       3.如果第一步结果小于0.忙等待,直到lock_flag>0然后跳转到第一步.
第一次看代码,可能很难从spin_lock_string看出,spin_lock是如何退出的.关键在要搞明白gcc的.subsection和.previous把夹在其中的代码放到别的段.如下面的汇编.
.........
lp1: dec lock_flag
       js     other_seg_code
.subsection
other_seg_code:
       xor   eax,eax
       jmp lp2   
.previous
lp2:
       cmp eax,0;
..........
它实际等价如下的代码
代码段1
..........
lp1: dec lock_flag
       js     other_seg_code
lp2:
       cmp eax,0;
..........
代码段2
..........
other_seg_code:
       xor   eax,eax
       jmp lp2   
..........
有此可以看明白,"js 2f"后面的代码根本不是,"rep;nop"而是自旋锁返回时应该执行的代码
spin_lock通过.LOCK_SECTION_START,和LOCK_SECTION_END使用.subsection和.previous.
流浪狗有点不明白的是,为啥要 rep;nop呢,没有看懂,清预取指令流?
The pause assembly language instruction, which was introduced in the Pentium 4 model, is designed to optimize the execution of spin lock loops. By introducing a small delay, it speeds up the execution of code following the lock and reduces power consumption. The pause instruction is backward compatible with earlier models of Intel processors because it corresponds to the instructions rep;nop, which essentially do nothing.
2003-10-13-0:20:23太晚了,明天上班,不写啦!!!!
printk
       start_kernel里碰到的第二个东西是printk，这玩意对程序员来说最大的用处是调试，核心没有它也能转。不过里面涉及到信号量、等待队列，不妨进去看看。
    printk是个典型的生产者和消费者问题，生产者和消费者使用一个环形缓冲log_buf，log_buf本身是个数组，printk通过对下标使用index%=buf_len的方式实现环形缓冲寻址，仔细看代码会发现如果生产速度大于消费速度，生产者会覆盖旧的数据。也就是说printk可能打印不出完整信息，不过这种情况太难出现了：）下面是printk的基本程序结构.
1.     如果是第一次调用printk,初始化缓冲锁和控制台互斥量
2.     进入缓冲临界区,分析数据,把数据写到logbuf.
3.     尝试获得控制台互斥量,如果成功退出临界区,用release_console_sem唤起控制台,否则简单退出临界区.
release_console_sem:把数据送到所有活动的控制台.
   
printk虽然会覆盖旧的数据但还是要用锁，目的是为了在多SMP上多个printk的数据混淆在一起，比如两个cpu同时执行
printk("aaaaa");//cpu1
printk("bbbbb");//cpu2
结果可以是aaaaabbbbb或者bbbbbaaaaa但不应该是ababaabbabab之类混淆的数据。printk的结构说到这，下面通过printk看别的东西。
spin_lock_init，和unlock等价！！以后流浪将忽略spin-lock。
init_MUTEX，进去发现mutex用sem实现的。让sem初始为1（UNLOCK）或者0（LOCKED），
信号量和他们的函数
struct semaphore {
    atomic_t count;//sem的值
    int sleepers;//这个名字有点怪，因为它并不代表等待该信号量的进程数
    wait_queue_head_t wait;//等待队列
};
sema_init，初始化函数，初始sem的值，设置等待该sem的进程数为0，初始等待队列为空。
up和down程序好复杂，特别是__down看着都头大，还好understanding linux kernel里比较详细，凑合着看完。倒是能看明白，可惜想不出为什么这样写
刚才出去跑了两公里，终于想明白了__down的算法，YEAH！！！理解__down的关键在于理解sleepers到底是什么？以及semaphore.c开头的那段话。下面是流浪狗的理解
    0。每个进程进入__down都已经把sem->count减1。
   
    1。sleepers是指已经把sem->count减1的所有未成功获得sem的进程计数，而且如果它对sem->count的减法被抵消（别的进程通过sem->count+=1可抵消sleepers中的一个计数），则该进程不被计入sleepers。
    2。看代码，
        进入__down之前cur进程把sem->count减1（根据1的定义，应该把sleepers++了），
        使用spin_lock_irqsave进入临界区。把当前进程加到等待队列，如我所料把sleepers++，
        使用atomic_add_negative把属于sleepers计数的进程，除了当前进程全部赶出sleepers。方法是把sem->count+=sleepers-1，(这里似乎没有必要用原子操作？？)
        sem->count被加后，造成了只有当前进程请求sem的假象。如果count等于0则请求成功（当前进程对count减1，count结果为0）。按照1的定义sleepers设置为0，如果count小于0则请求失败，sleepers设置为1。
        退出临界区，调度。。。。。
    3。semaphore.c开头的那段话，说__down只关心sem->count在0附近的边界。仔细看代码会发现，sleepers最大值为2，然后通过加sem->count，减小sleepers。
同样的道理很容易理解其他几个函数了。
等待队列，在核心2。6里也比较复杂，不过下面的过程最好还是看明白。
    tsk->state = TASK_UNINTERRUPTIBLE;
    add_wait_queue_exclusive_locked(&sem->wait, &wait);
    schedule();
等待队列和信号量本身不难理解，可代码咋怎么繁人涅。
2003-10-15-23:58
又要睡觉了，明天写等待队列和调度把，刚才看了两扣扣调度，真够BT的。
关于等待队列linux使用了链表数据结构，不过linux使用有点特别，但是很多书都有描述。流浪狗就不多说了。等待队列每个元素的结构如下
struct __wait_queue {
    unsigned int flags;//表示当前进程是否可以执行?
#define WQ_FLAG_EXCLUSIVE   0x01
    struct task_struct * task;//当前进程,操作系统课程里的pcb
    wait_queue_func_t func;//唤醒函数指针,一般是默认的wake_function
    struct list_head task_list;//linux使用的链表部分
};
一般来说,每个等待队列里有多个停止的进程,在信号量的up操作里,最后会调用__wake_up_common唤醒一个进程,被唤醒的进程被添加到runqueue(可执行的进程队列)里,而不是马上执行.默认的唤醒函数调用try_to_wake_up完成这一功能,由于多cpu的关系,这个函数有点麻烦,乱阿,真不想看了.真想把它改写得简单点,不过现在还是忍吧,流浪吧,
每个up都只唤醒一个进程,每个down操作有可能唤醒一个进程.这在性能上是非常合理的.
Schedule,接下来看看调度吧,真是有趣,本来看的是printk函数结果内核同步和等待队列,调度都要看了.估计后面连进程切换也会看.不知道会游到那里.流浪好像看得越来越粗了,文档也写得更烂了.
Schedule过程大概如此(流浪省略了抢占)
1,如果当前进程有未结信号把当前进程保留在runqueue状态修改未可运行,否则把当前进程重runqueue里移除.
2,如果runqueue为空,next进程为idel,否则找到最适合运行的进程. Runqueue里好像把进程分为过期(时间片用完的进程),活动(时间片没有用完的进程)两种,如果活动为空则过期变为活动.
3,进行切换switch_tasks
<





&nbsp

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/7720/showart_37599.html