2005年12月09日

发信人: dfbb (赵无忌), 信区: Linux
标  题: LINUX下的设备驱动程序
发信站: BBS 水木清华站 (Sat Dec 13 15:54:36 1997)
  
发信人: olly (剑胆琴心), 信区: Linux
标  题: LINUX下的设备驱动程序
发信站: BBS 水木清华站 (Sat Jun 28 14:00:08 1997)
 
 
     以下是本人毕业论文的一部分,是关于Linux下设备驱动程序的编写的。
请各位同志们指正。
 
三、UNIX系统下的设备驱动程序
3.1、UNIX下设备驱动程序的基本结构
在UNIX系统里,对用户程序而言,设备驱动程序隐藏了设备的具体细节,
对各种不同设备提供了一致的接口,一般来说是把设备映射为一个特殊的设备文
件,用户程序可以象对其它文件一样对此设备文件进行操作。UNIX对硬件设备
支持两个标准接口:块特别设备文件和字符特别设备文件,通过块(字符)特别
设备文件存取的设备称为块(字符)设备或具有块(字符)设备接口。
块设备接口仅支持面向块的I/O操作,所有I/O操作都通过在内核地址空间
中的I/O缓冲区进行,它可以支持几乎任意长度和任意位置上的I/O请求,即提
供随机存取的功能。
字符设备接口支持面向字符的I/O操作,它不经过系统的快速缓存,所以它
们负责管理自己的缓冲区结构。字符设备接口只支持顺序存取的功能,一般不能
进行任意长度的I/O请求,而是限制I/O请求的长度必须是设备要求的基本块长
的倍数。显然,本程序所驱动的串行卡只能提供顺序存取的功能,属于是字符设
备,因此后面的讨论在两种设备有所区别时都只涉及字符型设备接口。
设备由一个主设备号和一个次设备号标识。主设备号唯一标识了设备类型,
即设备驱动程序类型,它是块设备表或字符设备表中设备表项的索引。次设备号
仅由设备驱动程序解释,一般用于识别在若干可能的硬件设备中,I/O请求所涉
及到的那个设备。
设备驱动程序可以分为三个主要组成部分:
(1) 自动配置和初始化子程序,负责检测所要驱动的硬件设备是否存在和是否
能正常工作。如果该设备正常,则对这个设备及其相关的、设备驱动程序
需要的软件状态进行初始化。这部分驱动程序仅在初始化的时候被调用一
次。
(2) 服务于I/O请求的子程序,又称为驱动程序的上半部分。调用这部分是由
于系统调用的结果。这部分程序在执行的时候,系统仍认为是和进行调用
的进程属于同一个进程,只是由用户态变成了核心态,具有进行此系统调
用的用户程序的运行环境,因此可以在其中调用sleep()等与进程运行环
境有关的函数。
(3) 中断服务子程序,又称为驱动程序的下半部分。在UNIX系统中,并不是
直接从中断向量表中调用设备驱动程序的中断服务子程序,而是由UNIX
系统来接收硬件中断,再由系统调用中断服务子程序。中断可以产生在任
何一个进程运行的时候,因此在中断服务程序被调用的时候,不能依赖于
任何进程的状态,也就不能调用任何与进程运行环境有关的函数。因为设
备驱动程序一般支持同一类型的若干设备,所以一般在系统调用中断服务
子程序的时候,都带有一个或多个参数,以唯一标识请求服务的设备。
在系统内部,I/O设备的存取通过一组固定的入口点来进行,这组入口点是
由每个设备的设备驱动程序提供的。一般来说,字符型设备驱动程序能够提供如
下几个入口点:
(1) open入口点。打开设备准备I/O操作。对字符特别设备文件进行打开操
作,都会调用设备的open入口点。open子程序必须对将要进行的I/O
操作做好必要的准备工作,如清除缓冲区等。如果设备是独占的,即同一
时刻只能有一个程序访问此设备,则open子程序必须设置一些标志以表
示设备处于忙状态。
(2) close入口点。关闭一个设备。当最后一次使用设备终结后,调用close
子程序。独占设备必须标记设备可再次使用。
(3) read入口点。从设备上读数据。对于有缓冲区的I/O操作,一般是从缓
冲区里读数据。对字符特别设备文件进行读操作将调用read子程序。
(4) write入口点。往设备上写数据。对于有缓冲区的I/O操作,一般是把数
据写入缓冲区里。对字符特别设备文件进行写操作将调用write子程序。
(5) ioctl入口点。执行读、写之外的操作。
(6) select入口点。检查设备,看数据是否可读或设备是否可用于写数据。
select系统调用在检查与设备特别文件相关的文件描述符时使用select入口点。
如果设备驱动程序没有提供上述入口点中的某一个,系统会用缺省的子程序
来代替。对于不同的系统,也还有一些其它的入口点。
 
3.2、LINUX系统下的设备驱动程序
具体到LINUX系统里,设备驱动程序所提供的这组入口点由一个结构来向系
统进行说明,此结构定义为:
#include <linux/fs.h>
struct file_operations {
        int (*lseek)(struct inode *inode,struct file *filp,
                off_t off,int pos);
        int (*read)(struct inode *inode,struct file *filp,
                char *buf, int count);
        int (*write)(struct inode *inode,struct file *filp,
                char *buf,int count);
        int (*readdir)(struct inode *inode,struct file *filp,
                struct dirent *dirent,int count);
        int (*select)(struct inode *inode,struct file *filp,
                int sel_type,select_table *wait);
        int (*ioctl) (struct inode *inode,struct file *filp,
                unsigned int cmd,unsigned int arg);
        int (*mmap) (void);
 
        int (*open) (struct inode *inode, struct file *filp);
        void (*release) (struct inode *inode, struct file *filp);
        int (*fsync) (struct inode *inode, struct file *filp);
};
其中,struct inode提供了关于特别设备文件/dev/driver(假设此设备名
为driver)的信息,它的定义为:
#include <linux/fs.h>
struct inode {
        dev_t           i_dev;
        unsigned long   i_ino;  /* Inode number */
        umode_t         i_mode; /* Mode of the file */
        nlink_t         i_nlink;
        uid_t           i_uid;
        gid_t           i_gid;
        dev_t           i_rdev;  /* Device major and minor numbers*/
        off_t           i_size;
        time_t          i_atime;
        time_t          i_mtime;
        time_t          i_ctime;
        unsigned long   i_blksize;
        unsigned long   i_blocks;
        struct inode_operations * i_op;
      struct super_block * i_sb;
        struct wait_queue * i_wait;
        struct file_lock * i_flock;
        struct vm_area_struct * i_mmap;
        struct inode * i_next, * i_prev;
        struct inode * i_hash_next, * i_hash_prev;
        struct inode * i_bound_to, * i_bound_by;
        unsigned short i_count;
        unsigned short i_flags;  /* Mount flags (see fs.h) */
        unsigned char i_lock;
        unsigned char i_dirt;
        unsigned char i_pipe;
        unsigned char i_mount;
        unsigned char i_seek;
        unsigned char i_update;
        union {
                struct pipe_inode_info pipe_i;
                struct minix_inode_info minix_i;
                struct ext_inode_info ext_i;
                struct msdos_inode_info msdos_i;
                struct iso_inode_info isofs_i;
                struct nfs_inode_info nfs_i;
        } u;
};
 
struct file主要用于与文件系统对应的设备驱动程序使用。当然,其它设
备驱动程序也可以使用它。它提供关于被打开的文件的信息,定义为:
#include <linux/fs.h>
struct file {
        mode_t f_mode;
        dev_t f_rdev;             /* needed for /dev/tty */
        off_t f_pos;              /* Curr. posn in file */
        unsigned short f_flags;   /* The flags arg passed to open */
        unsigned short f_count;   /* Number of opens on this file */
        unsigned short f_reada;
        struct inode *f_inode;    /* pointer to the inode struct */
        struct file_operations *f_op;/* pointer to the fops struct*/
};
 
在结构file_operations里,指出了设备驱动程序所提供的入口点位置,分
别是:
(1) lseek,移动文件指针的位置,显然只能用于可以随机存取的设备。
(2) read,进行读操作,参数buf为存放读取结果的缓冲区,count为所要
读取的数据长度。返回值为负表示读取操作发生错误,否则返回实际读取
的字节数。对于字符型,要求读取的字节数和返回的实际读取字节数都必
须是inode->i_blksize的的倍数。
(3) write,进行写操作,与read类似。
(4) readdir,取得下一个目录入口点,只有与文件系统相关的设备驱动程序
才使用。
(5) selec,进行选择操作,如果驱动程序没有提供select入口,select操
作将会认为设备已经准备好进行任何的I/O操作。
(6) ioctl,进行读、写以外的其它操作,参数cmd为自定义的的命令。
(7) mmap,用于把设备的内容映射到地址空间,一般只有块设备驱动程序使
用。
(8) open,打开设备准备进行I/O操作。返回0表示打开成功,返回负数表
示失败。如果驱动程序没有提供open入口,则只要/dev/driver文件存
在就认为打开成功。
(9) release,即close操作。
设备驱动程序所提供的入口点,在设备驱动程序初始化的时候向系统进行登
记,以便系统在适当的时候调用。LINUX系统里,通过调用register_chrdev
向系统注册字符型设备驱动程序。register_chrdev定义为:
 #include <linux/fs.h>
 #include <linux/errno.h>
 int register_chrdev(unsigned int major, const char *name,
             struct file_operations *fops);
其中,major是为设备驱动程序向系统申请的主设备号,如果为0则系统为此
驱动程序动态地分配一个主设备号。name是设备名。fops就是前面所说的对各个
调用的入口点的说明。此函数返回0表示成功。返回-EINVAL表示申请的主设备号
非法,一般来说是主设备号大于系统所允许的最大设备号。返回-EBUSY表示所申
请的主设备号正在被其它设备驱动程序使用。如果是动态分配主设备号成功,此
函数将返回所分配的主设备号。如果register_chrdev操作成功,设备名就会出
现在/proc/devices文件里。
初始化部分一般还负责给设备驱动程序申请系统资源,包括内存、中断、时
钟、I/O端口等,这些资源也可以在open子程序或别的地方申请。在这些资源不
用的时候,应该释放它们,以利于资源的共享。
在UNIX系统里,对中断的处理是属于系统核心的部分,因此如果设备与系
统之间以中断方式进行数据交换的话,就必须把该设备的驱动程序作为系统核心
的一部分。设备驱动程序通过调用request_irq函数来申请中断,通过free_irq
来释放中断。它们的定义为:
#include <linux/sched.h>
int request_irq(unsigned int irq,
                void (*handler)(int irq,void dev_id,struct pt_regs *regs),
                unsigned long flags,
                const char *device,
                void *dev_id);
void free_irq(unsigned int irq, void *dev_id);
参数irq表示所要申请的硬件中断号。handler为向系统登记的中断处理子
程序,中断产生时由系统来调用,调用时所带参数irq为中断号,dev_id为申
请时告诉系统的设备标识,regs为中断发生时寄存器内容。device为设备名,
将会出现在/proc/interrupts文件里。flag是申请时的选项,它决定中断处理
程序的一些特性,其中最重要的是中断处理程序是快速处理程序(flag里设置
了SA_INTERRUPT)还是慢速处理程序(不设置SA_INTERRUPT),快速处理程序
运行时,所有中断都被屏蔽,而慢速处理程序运行时,除了正在处理的中断外,
其它中断都没有被屏蔽。在LINUX系统中,中断可以被不同的中断处理程序共享,
这要求每一个共享此中断的处理程序在申请中断时在flags里设置SA_SHIRQ,
这些处理程序之间以dev_id来区分。如果中断由某个处理程序独占,则dev_id
可以为NULL。request_irq返回0表示成功,返回-INVAL表示irq>15或
handler==NULL,返回-EBUSY表示中断已经被占用且不能共享。
作为系统核心的一部分,设备驱动程序在申请和释放内存时不是调用malloc
和free,而代之以调用kmalloc和kfree,它们被定义为:
#include <linux/kernel.h>
void * kmalloc(unsigned int len, int priority);
void kfree(void * obj);
参数len为希望申请的字节数,obj为要释放的内存指针。priority为分配内存操
作的优先级,即在没有足够空闲内存时如何操作,一般用GFP_KERNEL。
与中断和内存不同,使用一个没有申请的I/O端口不会使CPU产生异常,也
就不会导致诸如“segmentation fault"一类的错误发生。任何进程都可以访问
任何一个I/O端口。此时系统无法保证对I/O端口的操作不会发生冲突,甚至会
因此而使系统崩溃。因此,在使用I/O端口前,也应该检查此I/O端口是否已有
别的程序在使用,若没有,再把此端口标记为正在使用,在使用完以后释放它。
这样需要用到如下几个函数:
int check_region(unsigned int from, unsigned int extent);
void request_region(unsigned int from, unsigned int extent,
                    const char *name);
void release_region(unsigned int from, unsigned int extent);
调用这些函数时的参数为:from表示所申请的I/O端口的起始地址;
extent为所要申请的从from开始的端口数;name为设备名,将会出现在
/proc/ioports文件里。check_region返回0表示I/O端口空闲,否则为正在
被使用。
在申请了I/O端口之后,就可以如下几个函数来访问I/O端口:
#include <asm/io.h>
inline unsigned int inb(unsigned short port);
inline unsigned int inb_p(unsigned short port);
inline void outb(char value, unsigned short port);
inline void outb_p(char value, unsigned short port);
其中inb_p和outb_p插入了一定的延时以适应某些慢的I/O端口。
在设备驱动程序里,一般都需要用到计时机制。在LINUX系统中,时钟是由
系统接管,设备驱动程序可以向系统申请时钟。与时钟有关的系统调用有:
#include <asm/param.h>
#include <linux/timer.h>
void add_timer(struct timer_list * timer);
int  del_timer(struct timer_list * timer);
inline void init_timer(struct timer_list * timer);
struct timer_list的定义为:
struct timer_list {
               struct timer_list *next;
               struct timer_list *prev;
               unsigned long expires;
               unsigned long data;
               void (*function)(unsigned long d);
       };
其中expires是要执行function的时间。系统核心有一个全局变量JIFFIES
表示当前时间,一般在调用add_timer时jiffies=JIFFIES+num,表示在num个
系统最小时间间隔后执行function。系统最小时间间隔与所用的硬件平台有关,
在核心里定义了常数HZ表示一秒内最小时间间隔的数目,则num*HZ表示num
秒。系统计时到预定时间就调用function,并把此子程序从定时队列里删除,
因此如果想要每隔一定时间间隔执行一次的话,就必须在function里再一次调
用add_timer。function的参数d即为timer里面的data项。
在设备驱动程序里,还可能会用到如下的一些系统函数:
#include <asm/system.h>
#define cli() __asm__ __volatile__ ("cli"::)
#define sti() __asm__ __volatile__ ("sti"::)
这两个函数负责打开和关闭中断允许。
#include <asm/segment.h>
void memcpy_fromfs(void * to,const void * from,unsigned long n);
void memcpy_tofs(void * to,const void * from,unsigned long n);
在用户程序调用read 、write时,因为进程的运行状态由用户态变为核心
态,地址空间也变为核心地址空间。而read、write中参数buf是指向用户程
序的私有地址空间的,所以不能直接访问,必须通过上述两个系统函数来访问用
户程序的私有地址空间。memcpy_fromfs由用户程序地址空间往核心地址空间
复制,memcpy_tofs则反之。参数to为复制的目的指针,from为源指针,n
为要复制的字节数。
在设备驱动程序里,可以调用printk来打印一些调试信息,用法与printf
类似。printk打印的信息不仅出现在屏幕上,同时还记录在文件syslog里。
 
3.3、LINUX系统下的具体实现
在LINUX里,除了直接修改系统核心的源代码,把设备驱动程序加进核心里
以外,还可以把设备驱动程序作为可加载的模块,由系统管理员动态地加载它,
使之成为核心地一部分。也可以由系统管理员把已加载地模块动态地卸载下来。
LINUX中,模块可以用C语言编写,用gcc编译成目标文件(不进行链接,作
为*.o文件存在),为此需要在gcc命令行里加上-c的参数。在编译时,还应该在
gcc的命令行里加上这样的参数:-D__KERNEL__ -DMODULE。由于在不链接时,
gcc只允许一个输入文件,因此一个模块的所有部分都必须在一个文件里实现。
编译好的模块*.o放在/lib/modules/xxxx/misc下(xxxx表示核心版本,如
在核心版本为2.0.30时应该为/lib/modules/2.0.30/misc),然后用depmod -a
使此模块成为可加载模块。模块用insmod命令加载,用rmmod命令来卸载,并可
以用lsmod命令来查看所有已加载的模块的状态。
编写模块程序的时候,必须提供两个函数,一个是int init_module(void),
供insmod在加载此模块的时候自动调用,负责进行设备驱动程序的初始化工作。
init_module返回0以表示初始化成功,返回负数表示失败。另一个函数是void
cleanup_module (void),在模块被卸载时调用,负责进行设备驱动程序的清除
工作。
在成功的向系统注册了设备驱动程序后(调用register_chrdev成功后),
就可以用mknod命令来把设备映射为一个特别文件,其它程序使用这个设备的时
候,只要对此特别文件进行操作就行了。
 
 
附录:参考文献
 
1、 《UNIX操作系统设计与实现》
 陈华瑛、李建国主编
 电子工业出版社出版
2、  《Linux Kernel Hacker’s Guide》
 作者:Michael K. Johnson
3、 《Kernel Jorn》
 作者:Alessandro Rubini & Georg Zezchwitz
 连载于《Linux Journal》1996年36期
4、 Linux核心源代码(核心版本2.0.30)
5、 Linux-HOWTO
 

 
沧海一声笑
滔滔两岸潮
浮沉随浪只记今朝
来!共进一杯
让我们歌〖笑傲江湖〗到通宵!!!
 
※ 来源:·BBS 水木清华站 bbs.net.tsinghua.edu.cn·[FROM: ie0.ie.ac.cn]
 

本文转自中文Linux论坛

2005年12月06日

关于setuid的分析(6)

IEEE Std 1003.1™, 2004 Edition

Standard for Information Technology —
Portable Operating System Interface (POSIX)

System Interfaces   中对setuid()的论述。。。

NAME

    setuid—set user ID

SYNOPSIS

    #include

    int setuid(uid_t uid);

DESCRIPTION

    If the process has appropriate privileges, setuid( ) shall set the real user ID,
    effective user ID, and the saved set-user-ID of the calling process to uid.

    If the process does not have appropriate privileges, but uid is equal to the real user
    ID or the saved set-user-ID, setuid( ) shall set the effective user ID to uid; the real
    user ID and saved set-user-ID shall remain unchanged.

    The setuid( ) function shall not affect the supplementary group list in any way.

RETURN VALUE

    Upon successful completion, 0 shall be returned. Otherwise, ?1 shall be returned and
    errno set to indicate the error.

ERRORS

    The setuid( ) function shall fail, return ?1, and set errno to the corresponding value
    if one or more of the following are true:

    [EINVAL]    The value of the uid argument is invalid and not supported by the
                implementation.

    [EPERM]     The process does not have appropriate privileges and uid does not match the
                real user ID or the saved set-user-ID.

EXAMPLES

    None.

APPLICATION USAGE

    None.

RATIONALE

    The various behaviors of the setuid( ) and setgid( ) functions when called by
    non-privileged processes reflect the behavior of different historical implementations.
    For portability, it is recommended that new non-privileged applications use the
    seteuid( ) and setegid( ) functions instead.

    The saved set-user-ID capability allows a program to regain the effective user ID
    established at the last exec call. Similarly, the saved set-group-ID capability allows
    a program to regain the effective group ID established at the last exec call.
    These capabilities are derived from System V. Without them, a program might have to run
    as superuser in order to perform the same functions, because superuser can write on the
    user’s files. This is a problem because such a program can write on any user’s files,
    and so must be carefully written to emulate the permissions of the calling process
    properly. In System V, these capabilities have traditionally been implemented only via
    the setuid( ) and setgid( ) functions for non-privileged processes. The fact that the
    behavior of those functions was different for privileged processes made them difficult
    to use. The POSIX.1-1990 standard defined the setuid( ) function to behave differently
    for privileged and unprivileged users. When the caller had the appropriate privilege,
    the function set the calling process’ real user ID, effective user ID, and saved
    set-user ID on implementations that supported it. When the caller did not have the
    appropriate privilege, the function set only the effective user ID, subject to
    permission checks. The former use is generally needed for utilities like login and su,
    which are not conforming applications and thus outside the scope of IEEE Std
    1003.1-2001. These utilities wish to change the user ID irrevocably to a new value,
    generally that of an unprivileged user. The latter use is needed for conforming
    applications that are installed with the set-user-ID bit and need to perform operations
    using the real user ID.

    IEEE Std 1003.1-2001 augments the latter functionality with a mandatory feature named
    _POSIX_SAVED_IDS. This feature permits a set-user-ID application to switch its
    effective user ID back and forth between the values of its exec-time real user ID and
    effective user ID. Unfortunately, the POSIX.1-1990 standard did not permit a conforming
    application using this feature to work properly when it happened to be executed with
    the (implementation-defined) appropriate privilege. Furthermore, the application did
    not even have a means to tell whether it had this privilege. Since the saved
    set-user-ID feature is quite desirable for applications, as evidenced by the fact that
    NIST required it in FIPS 151-2, it has been mandated by IEEE Std 1003.1-2001. However,
    there are implementors who have been reluctant to support it given the limitation
    described above.

    The 4.3BSD system handles the problem by supporting separate functions: setuid( )
    (which always sets both the real and effective user IDs, like setuid( ) in IEEE Std
    1003.1-2001 for privileged users), and seteuid( ) (which always sets just the effective
    user ID, like setuid( ) in IEEE Std 1003.1-2001 for non-privileged users). This
    separation of functionality into distinct functions seems desirable. 4.3BSD does not
    support the saved set-user-ID feature. It supports similar functionality of switching
    the effective user ID back and forth via setreuid( ), which permits reversing the real
    and effective user IDs. This model seems less desirable than the saved set-user-ID
    because the real user ID changes as a side effect. The current 4.4BSD includes saved
    effective IDs and uses them for seteuid( ) and setegid( ) as described above. The
    setreuid( ) and setregid( ) functions will be deprecated or removed.

    The solution here is:

      . Require that all implementations support the functionality of the saved
        set-user-ID, which is set by the exec functions and by privileged calls to
        setuid( ).

      . Add the seteuid( ) and setegid( ) functions as portable alternatives to setuid( )
        and setgid( ) for non-privileged and privileged processes.

    Historical systems have provided two mechanisms for a set-user-ID process to change its
    effective user ID to be the same as its real user ID in such a way that it could return
    to the original effective user ID: the use of the setuid( ) function in the presence of
    a saved set-user-ID, or the use of the BSD setreuid( ) function, which was able to swap
    the real and effective user IDs. The changes included in IEEE Std 1003.1-2001 provide a
    new mechanism using seteuid( ) in conjunction with a saved set-user-ID. Thus, all
    implementations with the new seteuid( ) mechanism will have a saved set-user-ID for
    each process, and most of the behavior controlled by _POSIX_SAVED_IDS has been changed
    to agree with the case where the option was defined. The kill ( ) function is an
    exception. Implementors of the new seteuid( ) mechanism will generally be required to
    maintain compatibility with the older mechanisms previously supported by their systems. 

    However, compatibility with this use of setreuid( ) and with the _POSIX_SAVED_IDS
    behavior of kill ( ) is unfortunately complicated. If an implementation with a saved
    set-user-ID allows a process to use setreuid( ) to swap its real and effective user
    IDs, but were to leave the saved set-user-ID unmodified, the process would then have an
    effective user ID equal to the original real user ID, and both real and saved
    set-user-ID would be equal to the original effective user ID. In that state, the real
    user would be unable to kill the process, even though the effective user ID of the
    process matches that of the real user, if the kill ( ) behavior of _POSIX_SAVED_IDS
    was used. This is obviously not acceptable. The alternative choice, which is used in
    at least one implementation, is to change the saved set-user-ID to the effective user
    ID during most calls to setreuid( ). The standard developers considered that
    alternative to be less correct than the retention of the old behavior of kill ( ) in
    such systems. Current conforming applications shall accommodate either behavior from
    kill ( ), and there appears to be no strong reason for kill( ) to check the saved
    set-user-ID rather than the effective user ID.

FUTUREDIRECTIONS

    None.

SEE ALSO

    exec, getegid( ), geteuid( ), getgid( ), getuid( ), setegid( ), seteuid( ), setgid( ),
    setregid( ), setreuid( ), the Base Definitions volume of IEEE Std 1003.1-2001,
    <sys/types.h>, <unistd.h>

CHANGE HISTORY

    First released in Issue 1. Derived from Issue 1 of the SVID.

Issue 6

    In the SYNOPSIS, the optional include of the header is removed.
    The following new requirements on POSIX implementations derive from alignment with the
    Single UNIX Specification:

      . The requirement to include has been removed. Although
        was required for conforming implementations of previous POSIX specifications, it
        was not required for UNIX applications.

      . The functionality associated with _POSIX_SAVED_IDS is now mandatory. This is a FIPS
        requirement.

    The following changes were made to align with the IEEE P1003.1a draft standard:

      . The effects of setuid( ) in processes without appropriate privileges are changed.

      . A requirement that the supplementary group list is not affected is added.

关于setuid的分析(5)

Simson Garfinkel, Alan Schwartz, Gene Spafford 的 《Practical Unix & Internet Security》 一书中对这个问题的论述。。。

16.4 Tips on Writing SUID/SGID Programs

If you are writing programs that are SUID or SGID, you must take added precautions in your programming. An overwhelming number of Unix security problems have been caused by SUID/SGID programs. Consider the rules described in this section in addition to those in previous sections.

1."Don’t do it. Most of the time, it’s not necessary."

    Thanks to Patrick H. Wood and Stephen G. Kochan, Unix System Security (Hayden Books, 1985) for this insightful remark.

2.Avoid writing SUID shell scripts.

3.If you are using SUID to access a special set of files, don’t. Instead, create a special group for your files and make the program SGID to that group. If you must use SUID, create a special user for the purpose.

4.If your program needs to perform some functions as superuser, but generally does not require SUID permissions, consider putting the SUID part in a different program, and constructing a carefully controlled and monitored interface between the two.

5.If you need SUID or SGID permissions, use them for their intended purpose as early in the program as possible, and then revoke them by returning the effective, and real, UIDs and GIDs to those of the process that invoked the program.

6.If you have a program that absolutely must run as SUID, try to avoid equipping the program with a general-purpose interface that allows users to specify much in the way of commands or options.

7.Erase the execution environment, if at all possible, and start fresh. Many security problems have been caused because there was a significant difference between the environment in which the program was run by an attacker and the environment in which the program was developed.

8.If your program must spawn processes, use only the execve( ), execv( ), or execl( ) calls, and use them with great care. Avoid the execlp( ) and execvp( ) calls because they use the PATH environment variable to find an executable, and you might not run what you think you are running. Avoid system( ) and popen( ) at all costs.

9.If you must provide a shell escape, be sure to setgid(getgid( )) and setuid(getuid( )) before executing the user’s command and use them in the correct order! You must reset the group ID before you reset the user ID, or the call will fail.

10.In general, use the setuid( ) and setgid( ) functions and their friends to bracket the sections of your code that require superuser privileges. For example:

    /* setuid program is effectively superuser so it can open the master file */
    fd = open("/etc/masterfile",O_RDONLY);
    assert(seteuid(getuid(  )) == 0);                                               
    /* Give up superuser now, but we can get it back.*/
    assert(geteuid() == getuid(  ));/* Insure that the euid is what we expect. */
    if(fd<0) error_open(  );     /* Handle errors. */

Not all versions of Unix allow you to switch UIDs in this way; moreover, the semantics of the various versions of setuid( ), seteuid( ), and setreuid( ) have been shown to vary between Unix flavors, and even be misimplemented. It’s also crucial both to check their return values and to separately test to ensure that the UIDs are as you expect them. Read Chen, Wagner, and Dean’s paper "Setuid Demystified" (http://www.cs.berkeley.edu/~daw/papers/setuid-usenix02.pdf) before you even think about writing code that tries to save and restore privileges.

11.If you must use pipes or subshells, be especially careful with the environment variables PATH and IFS. One approach is to erase these variables and set them to safe values. For example:

    putenv("PATH=/bin:/usr/bin:/usr/ucb");
    putenv("IFS= ");
Then, examine the environment to be certain that there is only one instance of the variable: the one you set. An attacker can run your code from another program that creates multiple instances of an environment variable. Without an explicit check, you may find the first instance, but not the others; such a situation could result in problems later on. In particular, step through the elements of the environment yourself rather than depending on the library getenv( ) function.

Another approach, simpler but more drastic, is to create an empty environment and fill it with only those variables that you know are OK. This environment can then be passed to execve( ):

    char *env[MAX_ENV];
    int mysetenv(const char *name, const char *value) {
            static char count = 0;
            char buff[255];
            if (count == MAX_ENV) return 0;
            if (!name || !value) return 0;
            if (snprintf(buff, sizeof(buff), "%s=%s", name, value) < 0) return 0;
            if (env[count] = strdup(buff)) {
                    count++;
                    return 1;
            }
            return 0;
    }

    …And then in the program…

    if (mysetenv("PATH", "/bin:/usr/bin") &&
    mysetenv("SHELL", "/bin/sh") &&
    mysetenv("TERM", "vt100") &&
    mysetenv("USER", getenv("USER")) &&
    mysetenv("LOGNAME", getenv("LOGNAME")) &&
    mysetenv("HOME", getenv("HOME"))) {
            execve(myprogram,NULL,env);
            perror(myprogram);
    } else {
            perror("Unable to establish safe environment");
    }

12.Use the full pathname for all files that you open. Do not make any assumptions about the current directory. (You can enforce this requirement by doing a chdir("/tmp/root/") as one of the first steps in your program, but be sure to check the return code!)

13.Consider statically linking your program. If a user can substitute a different module in a dynamic library, even carefully coded programs are vulnerable. (We have some serious misgivings about the trend in commercial systems towards completely shared, dynamic libraries.

14.Consider using perl -T or taintperl for your SUID programs and scripts. Perl’s tainting features often make Perl more suited than C to SUID programming. For example, taintperl insists that you set the PATH environment variable to a known "safe value" before calling system( ). The program also requires that you "untaint" any variable that is input from the user before using it (or any variable dependent on that variable) as an argument for opening a file.

15.However, note that you can still get yourself in a great deal of trouble with taintperl if you circumvent its checks or if you are careless in writing code. Also note that using taintperl introduces dependence on another large body of code working correctly: we suggest you skip using taintperl if you believe that you can code at least as well as Larry Wall.

    Hint: if you think you can, you are probably wrong.

关于setuid的分析(4)

copy from 雨丝风片

FreeBSD6.0 setuid()函数源代码分析。。。

int setuid(struct thread *td, struct setuid_args *uap)
                              |
                              |
            ————————————
            | struct proc *p = td->td_proc;    |
            | struct ucred *newcred, *oldcred; |
            | uid_t uid;                       |
            | struct uidinfo *uip;             |
            | int error;                       |
            ————————————
                              |
                              |
                 ————————-
                 | uid = uap->uid;       |
                 | newcred = crget();    |
                 | uip = uifind(uid);    |
                 | PROC_LOCK(p);         |
                 | oldcred = p->p_ucred; |
                 ————————-
                               |
                               |
     ———————————————————-
     | (uid != oldcred->cr_ruid &&                            |
     <  uid != oldcred->cr_uid  &&                             >
     |  (error = suser_cred(oldcred, SUSER_ALLOWJAIL)) != 0)? |
     ———————————————————-
     是否入参uid既不等于真实uid又不等于有效uid,当前进程还没
     有超级用户权限?
                          /                  \
                         / No                 \ Yes
                        /                      \
           —————————–        \
           | crcopy(newcred, oldcred); |         \
           —————————–          \
           用oldcred对newcred进行初始化              \
                        |                           \
                        |                            ——————–
           —————————–             | PROC_UNLOCK(p);  |
          < (uid != oldcred->cr_ruid)?  >            | uifree(uip);     |
           —————————–             | crfree(newcred); |
           入参uid不等于真实uid吗?                     | return(error);   |
                  /          \                       ——————–
                 / No         \ Yes                           |
                /              \                              |
               /     ——————————            |
              /      | change_ruid(newcred, uip); |            |
             /       | setsugid(p);               |            |
            /        ——————————            |
           /         将newcred的真实uid设为入参uid,              |
          /          设置当前进程的P_SUGID标志                    |
         /                   /                                 |
        /                 /                                    |
       /               /                                       |
——————————-                                |
< (uid != oldcred->cr_svuid)? >                                |
——————————-                                |
入参uid不等于saved uid吗?                                       |
              /        \                                      |
             / No       \ Yes                                 |
            /            \                                    |
           /        ——————————-            |
          /         | change_svuid(newcred, uid); |            |
         /          | setsugid(p);                |            |
        /           ——————————-            |
       /            将newcred的saved uid设为入参uid,            |
      /             设置当前进程的P_SUGID标志                     |
     /                  /                                      |
    /                /                                         |
   /              /                                            |
——————————                                 |
< (uid != oldcred->cr_uid)?  >                                 |
——————————                                 |
入参uid不等于有效uid吗?                                          |
       |         \                                            |
       | No       \ Yes                                       |
       |           \                                          |
       |            ——————————-            |
       |            | change_euid(newcred, uid);  |            |
       |            | setsugid(p);                |            |
       |            ——————————-            |
       |            将newcred的有效uid设为入参uid,               |
       |            设置当前进程的P_SUGID标志                     |
       |                        |                              |
       |                        |                              |
       |            ————————-                  |
       |            | p->p_ucred = newcred; |                  |
       |            | PROC_UNLOCK(p);       |                  |
       ————>| uifree(uip);          |                  |
                    | crfree(oldcred);      |                  |
                    | return(0);            |                 /
                    ————————-              /
                    将当前进程的u_cred结构体更改           /
                    为newcred,使前面的修改生效         /
                                \                /
                                  \           /
                                    \      /
                                     ——-
                                     | END |
                                     ——-

关于setuid的分析(3)

copy from 雨丝风片

Marshall Kirk McKusick, George V. Neville-Neil 的《The Design and Implementation of the FreeBSD Operating System》一书中对这个问题的论述。。。

3.7 User, Group, and Other Identifiers

每个FreeBSD进程的状态里都有一个UID和一组GID。一个进程的文件系统访问特权就是由它的UID和GIDs来定义的。通常,这些标识符都是新进程创建的时候从父进程那儿自动继承过来的。只有超级用户才能修改一个进程的真实UID或真实GID。这个方案在各种特权之间进行了严格的区分,确保除了超级用户之外的其它任何用户都无法获得特权。

每个文件都有三组许可bit,分别用于所有者、组以及其它用户的读、写或执行许可。这些许可bit将按如下顺序进行检查:
    1、如果文件的UID和进程的UID相同,则仅应用所有者的许可,不再检查组和其它用户的许可。
    2、如果UID不匹配,但文件的GID和进程的众多GID之一匹配,则仅引用组的许可,不再检查所有者和其它用户的许可。
    3、仅当进程UID和GID与文件的UID和GID都不匹配时,才会去检查其它用户的许可。如果这些许可不允许所请求的操作,该操作就会失败。

一个进程的UID和GIDs是从它的父进程那儿继承来的。当一个用户登录的时候,login程序会在执行exec系统调用运行用户的登录shell之前设置好UID和GIDs,因此,后续的所有进程都会继承到恰当的标识符。

我们经常会想赋予一个用户有限的额外特权。……为了解决这个问题,内核允许程序在运行过程中创建被赋予特权的程序。以不同的UID运行的程序被称为setuid程序,以一个额外的组特权运行的程序被称为setgid程序。当运行一个setuid程序的时候,进程的许可将被扩展以包括与程序相关联的UID的许可。该程序的UID就被称为进程的有效UID,而进程最初的UID则被称为真实UID。同样,执行一个setgid程序会把进程的许可扩展为程序的GID的许可,相应的也有有效GID和真实GID的定义。

系统可以通过setuid和setgid程序来提供对文件或服务的受控访问。当然,这样的程序必须仔细编写,以保证它们只具有一些有限的功能。

UID和GIDs是作为每个进程的状态的一部分来维护的。由于历史原因,GIDs被实现成了一个显著的GID(即有效GID)和一个GIDs的辅助数组,不过在逻辑上则被看作是一组GIDs。在FreeBSD中,那个显著的GID就是GIDs数组中的第一个条目。辅助数组的大小是固定的(FreeBSD中是16),不过可以通过重新编译内核来修改这个数值。

FreeBSD是通过把运行setgid程序的进程的辅组数组中的第0个元素设置成文件的属组来实现setgid功能的。之后就可以像普通进程那样对许可进行检查了。由于存在额外的组,setgid程序就能够比一个运行没有特殊权限的程序的用户进程访问更多的文件。为了避免在运行一个setgid程序的时候丢失与第0个数组元素中的组相关联的特权,login程序会在初始化用户的辅组数组的时候将第0个数组元素复制到第一个数组元素中。因此,当运行的setgid程序修改第0个元素的时候,用户不会丢失任何特权,因为曾经保存在第0个数组元素中的组仍然可以从第一个数组元素中得到。

setuid功能是通过把进程的有效UID从用户的数值修改为被运行的程序的数值来实现的。和setgid一样,保护机制此时将毫不变样地允许访问,同时也不会意识到程序正在运行setuid。由于一个进程在同一时刻只能有一个UID,在运行setuid的时候就可能会丢失某些特权。在加载新的有效UID的时候,之前的真实UID将会继续作为真实UID。不过真实UID是不会用于任何确认检查的。

一个setuid进程在运行过程中可能会想临时取消它的特殊权限。比如,它可能只在运行开始和结束的时候需要访问某个受限文件的特殊权限。在其余的运行时间中,它应当只具有真实用户的权限。在BSD的早期版本中,特权的回收是通过对真实的和有效的UID进行切换来完成的。由于只有有效UID被用于访问控制,这个方法既提供了所需的语义,又提供了一个隐藏特殊权限的地方。这个方法的缺点是很容易就混淆了真实的和有效的UID。

在FreeBSD中,使用了一个额外的标识符,即saved UID来记录setuid程序的身份。当一个程序被exec之后,它的有效UID会被拷贝到saved UID中。下表中的第1行表示了一个没有特权的程序,它的真实、有效以及saved UID都是真实用户的数值。第2行正在运行中的setuid程序,它的有效UID被设置成了具有相应特权的UID,而这个特权UID也会被拷贝到saved UID中。

Actions affecting the real, effective, and saved UIDs.
_________________________________________________________________
Action            Real    Effective    Saved

1.exec-normal     R       R            R
2.exec-setuid     R       S            S
3.seteuid(R)      R       R            S
4.seteuid(S)      R       S            S
5.seteuid(R)      R       R            S
6.exec-normal     R       R            R

Key:R-real user identifier; S-special-privilege user identifier
_________________________________________________________________

seteuid系统调用只会修改有效UID,而不会影响真实的或saved UID。seteuid系统调用被允许将有效UID修改为真实的或saved UID的数值。表中的第3行和第4行表示了一个setuid程序在一直保持正确的真实UID的同时是如何放弃和重新取回它的特殊权限的。第5行和第6行表示了一个setuid程序可以运行一个子进程而不赋予它特殊权限。首先,它会把它的有效UID设置成真实UID。然后,当exec那个子进程的时候,有效UID就会被拷贝到saved UID中,从此就会失去对特权UID的所有访问。

与此类似,也有一个saved GID机制,允许进程在真实GID和最初的有效GID之间进行切换。

关于setuid的分析(2)

copy from 雨丝风片

Uresh Vahalia 的《UNIX Internals:The New Frontiers》一书中对这个问题的论述。。。

p27

2.3.3 User Credentials

UID和GID这样的标识符会影响文件的所有权和访问许可,以及向其它进程发送信号的能力。这些属性统称为凭证。

每个进程都有两对ID ——真实的和有效的。当一个用户登录的时候,login程序会把两对ID设置成密码数据库(/etc/passwd文件,或某些如Sun Microsystems的NIS之类的分布式机制)中指定的UID和GID。当一个进程fork的时候,子进程将从父进程那儿继承它的凭证。

有效UID和有效GID印象文件的创建和访问。在创建文件的时候,内核将文件的所有者属性设置成创建进程的有效UID和有效GID。在访问文件的时候,内核使用进程的有效UID和GID来判断它是否能够访问该文件。真实UID和真实GID标识进程的真实所有者,会影响到发送信号的权限。对于一个没有超级用户权限的进程来说,仅当它的真实或有效UID于另一个进程的真实UID匹配时它才能向那个进程发送信号。

有三个系统调用可以改变凭证。如果一个进程调用exec执行一个安装为suid模式的程序,内核将把进程的有效UID修改成文件的所有者。同样,如果该程序安装为sgid模式,内核则会去修改调用进程的有效GID。UNIX提供这个特性是想赋予用户特殊的权限以完成一些特定的任务。

一个用户还可以通过调用setuid或setgid来改变它的凭证。超级用户可以通过这些系统调用改变真实的和有效的UID以及GID。普通用户则只能通过这些调用来把它们的有效UID或GID改回到真实的数值。

System V和BSD UNIX在处理凭证方面存在着一些差别。SVR3还维护了一个saved UID和saved GID,分别是在调用exec之前的有效UID和GID的数值。setuid和setgid系统调用还可以把有效ID恢复为保存的数值。4.3BSD不支持这一特性,它允许一个用户属于一个辅组(supplemental group)的集合(使用setgroups系统调用)。用户创建的文件将属于它的主组(primary group),而用户则既可以访问属于主组的文件,也可以访问属于辅组的文件。

SVR4整合了上述所有特性。它支持附组,也会在exec的时候维护saved UID和GID。

setuid程序的例子:passwd。

关于setuid的分析(1)

copy from 雨丝风片

近期准备把我能找到的关于setuid的相关资料整理一下,包括书籍、论文以及FreeBSD的源代码等。

就从Bach的书开始吧。。。

Maurice J.Bach 的《The Design of The UNIX Operating System》一书中对这个问题的论述。。。

p227

7.6 THE USER ID OF A PROCESS

内核会给每个进程关联两个和进程ID无关的用户ID,一个是真实用户ID,还有一个是有效用户ID或者称为setuid(set user ID)。真实用户ID用于标识由谁为正在运行的进程负责。有效用户ID用于为新创建的文件分配所有权、检查文件访问许可,还用于通过kill系统调用向其它进程发送信号时的许可检查。内核允许一个进程以调用exec一个setuid程序或者显式执行setuid系统调用的方式改变它的有效用户ID。

所谓setuid程序是指一个设置了许可模式字段中的setuid bit的可执行文件。当一个进程exec一个setuid程序的时候,内核会把进程表以及u区中的有效用户ID设置成该文件所有者的ID。为了区分这两个字段,我们把进程表中的那个字段称作保存用户ID。可以通过一个例子来演示这两个字段的区别。

setuid系统调用的语法是 setuid(uid) ,其中,uid是新的用户ID,该系统调用的结果取决于有效用户ID的当前值。如果调用进程的有效用户ID是超级用户,内核会把进程表以及u区中的真实和有效用户ID都设置成uid。如果调用进程的有效用户ID不是超级用户,仅当uid等于真实用户ID或保存用户ID时,内核才会把u区中的有效用户ID设置成uid。否则,该系统调用将返回错误。一般来说,一个进程会在fork系统调用期间从父进程那儿继承它的真实和有效用户ID,这些数值即使经过exec系统调用也会保持不变。

存储在u区中的有效用户ID是最近一次setuid系统调用或是exec一个setuid程序的结果;只有它会被用于文件访问许可。进程表中的保存用户ID使得一个进程可以通过执行setuid系统调用把有效用户ID设置成它的值,以此来恢复最初的有效用户ID。

setuid程序的例子:login,mkdir。

BSD radix树路由表的设计原理——表头、节点、条目

在这里写下我的关于BSD radix树路由表的设计原理的文章之前,首先要感谢一个人:xie_minix,http://blog.chinaunix.net/index.php?blogId=2681。在我刚开始接触BSD 的radix树路由表的时候,是xie_minix发表在 http://www.cnfreeos.org/bsdsrc/ 的文章给我指明了最初的方向。滴水之恩,涌泉相报。自受惠于xie_minix公开的成果之日起,在下就决定将日后的心得也如xie_minix一般公之于众,以期能给其他的爱好、钟情、研究、使用BSD的朋友们一些帮助。

当然,还有一个人也是需要感谢的,W.Richard Stevens,没有他的书,也就没有了这里写下的一切。

写这篇文章的时候使用的是FreeBSD5.1的代码,举例用的是IPv6地址。

如果您有机会读到我写在这里的东西,还望留下宝贵意见,以便我加以修改,方便以后来这里的朋友。万分感谢!

目录:1 BSD路由表的表头;  2 BSD路由表的节点:内部节点、叶子节点、根节点、重复键节点;  3 BSD路由表的条目。

BSD radix树路由表的设计原理

BSD路由表使用的是radix树,这种树的设计思想来自Donald R.Morrison于1968年提出的Patricia树(Practical  Algorithm To Retrieve Information Coded In Alphanumeric)。这是一种基于以二进制表示的键值的查找树,尤其适合于处理非常长的、可变长度的键值。Partricia的基本思想是构建一个二叉树,在每个节点中都存储有进行下一次的bit测试之前需要跳过的bit数目,以此来避免单路分支(即避免二叉树的某一段呈现只往左或者只往右生长的趋势)。因此,一般意义上的Patricia树由内部节点和外部节点组成,内部节点用于指示需要进行bit测试的位置,并依据bit测试结果决定查找操作的前进方向,而外部节点则用于存储键值,查找操作将于外部节点处终止。

BSD正是借用了Partricia树的思想来组织路由表,但考虑到路由表的特殊性,即需要存储掩码并实现最长匹配路由查找,于是对Partricia树进行了改造,形成了BSD的radix树。在BSD的radix树中的路由查找操作将分为三个步骤,第一个步骤即是Partricia查找,终结于某个叶子节点,判断该叶子节点是否与查找键相同。第二个步骤,如果找到的叶子节点与查找键无法匹配,则在这个叶子节点的重复键链表中寻找网络匹配的可能。第三个步骤,如果找到的叶子节点及其重复键与查找键不满足网络匹配条件,则向树顶回溯,继续寻找网络匹配的可能。

1 BSD路由表的表头

BSD路由表的头指针存放在rt_tables[]数组中,这是一个radix_node_head结构体类型的指针数组。在BSD的协议栈中,所有协议的路由表都是用radix树进行组织的,而这些radix树的头指针就都存放在rt_tables[]数组中,IPv6路由表的头指针只是其中之一,即下标为AF_INET6的数组元素。

radix_node_head结构体的内存布局如图1所示。rnh_treetop是指向路由表顶部节点的指针。在这个结构体中还定义了8个函数指针,分别指向路由表提供的8个操作函数。在这个结构体的尾部还有三个radix_node结构体,这就是radix树的初始三节点,它们的rn_flags字段将被设置成RNF_ROOT,表示这是radix树的根节点。这三个节点是在路由表初始化时生成的。
 

radix_node_head结构体


图1 BSD路由表的表头 – radix_node_head 结构体

路由表初始化完成后,这三个根节点的链接关系如图3所示。从这个图中我们可以看出,在三个根节点组成的数组rnh_nodes[3]中,第二个根节点作为路由表的顶部节点,由rnh_treetop指针指向,它将是对路由表的所有操作的开始处。此外,第一个根节点被初始化为顶部节点的左孩子,第三个根节点被初始化为顶部节点的右孩子,而这三个初始根节点的父指针都指向了中间的那个顶部节点。这实际上已经搭起了一个radix树的基本框架。如图2所示。


图2 仅含有3个根节点的radix树

在图2中,我们将中间的作为路由树顶的根节点用圆圈表示,因为它属于内部节点。而另外的两个根节点我们用方框表示,它们属于叶子节点。在本文档中将始终按照这一约定来图示内部节点和叶子节点。

2 BSD路由表的节点

BSD路由表的radix树实际上就是由一系列的内部节点和叶子节点组成的。内部节点位于树的中间位置,每个内部节点都会指定一个bit测试位置,即当从树的顶端开始向下查找,遇到这个内部节点时需要判断是0还是1的bit位置,接下来的查找将根据bit测试的结果来决定是向左走还是向右走。叶子节点位于树的边缘,用于存储路由表键值,即IP地址。

2.1 内部节点

前已述及,内部节点在radix树中用于表示一个bit测试位置。

内部节点和叶子节点使用的都是radix_node结构体,只是少数字段的定义有所不同。我们首先通过内部节点来查看一下radix_node结构体中的各个字段。在radix树中的3个根节点中,位于中间的那个顶端节点就是内部节点,因此我们的描述就以图3为例。

rn_mklist:这个指针指向的是一个radix_mask结构体链表。对于内部节点来说这个链表上的掩码都取自它的子树中的叶子节点所对应的掩码,但只有那些在做逻辑AND运算时能够把这个内部节点的测试bit变成0的掩码才能够加入到这个链表中,这类掩码的作用将在路由查找时的回溯过程中体现出来。对于叶子节点,如果它的掩码满足上述条件而被选入它的某一级父节点的掩码链表的话,那么它的rn_mklist指针就会指向这个掩码链表中对应于它自己的掩码的那个节点。

rn_parent:这是节点的父指针,从叶子节点一直向上指到树的顶端节点,而树的顶端节点的父指针是指向它自己的。路由查找时的回溯过程将沿父指针进行。

rn_bit:对于内部节点,这个值大于等于0,用于指示在这个内部节点处需要进行测试的bit位置。这个位置是从用于存储IP地址的socket地址结构体的起始位置开始计算的。对于叶子节点,这个值是一个负数,具体数值就是-1减去这个叶子节点所对应的掩码的索引值。而所谓掩码的索引值就是指这个掩码中第一次出现0的bit位置,这个位置也是从socket地址结构体的起始位置开始计算的。


图3 radix_node_head 结构体中三个初始根节点的链接关系

rn_bmask:这是一个1字节的掩码,其中只有一个bit为1。在实际的路由查找中,为了加快查找速度,就是使用这个字段直接对指定的字节进行bit测试,而不是指定bit进行测试。对于叶子节点,这个字段为0。

rn_flags:这个字段的可能取值一共有3个,RNF_NORMAL,表示这是一个含有常规路由的叶子节点;RNF_ROOT,表示这是一个位于radix_node_head结构体中的节点,即路由表中的三个根节点;RNF_ACTIVE,表示这条路由的状态是好的。

rn_Off:这是内部节点独有的字段,表示一个从socket地址结构体的起始位置开始计算的字节偏移量,用于指定在这个内部节点处需用rn_bmask进行单字节比较的字节偏移量。

rn_L:这是内部节点独有的字段,指向这个内部节点的左孩子。

rn_R:这是内部节点独有的字段,指向这个内部节点的右孩子。

2.2 叶子节点

叶子节点和内部节点的大部分字段都是一样的,只是最后三个字段的定义不一样。相同字段的定义已在前面的内部节点部分进行了描述,最后三个字段的定义如下。

rn_Key:这个字段就内存位置而言相当于内部节点中的rn_Off字段。这个字段用于指向存储着叶子节点键值(即IP地址)的socket地址结构体。

rn_Pfxlen: 这个字段就内存位置而言相当于内部节点中的rn_L字段。这个字段用于存储前缀长度。

rn_Dupedkey: 这个字段就内存位置而言相当于内部节点中的rn_R字段。当路由表中有重复键情况出现的时候,即有多个叶子节点的键值(IP地址)相同,这些叶子节点是以链表的形式挂接在树中的某个叶子节点下的,rn_Dupedkey即指向重复键链表中的下一个叶子节点。

在radix树中,左右两个根节点即属于叶子节点。

2.3 根节点

radix树中的根节点即是在图2和图3中给出的3个节点。这三个节点都被设置了RNF_ROOT标志,以表示它们是根节点。

中间的那个根节点是radix树的顶部节点,所有的路由查找操作都是从它开始的。我们可以看到,这个根节点的bit测试位置是64,也就是说,对于存储在socket地址结构体中的BSD地址而言,实际的BSD地址开始的第一个bit在结构体中的偏移量是64,整个radix树的bit比较算法就是从这第64 bit开始。前已述及,为了加快查找速度,实际的查找操作中使用的是字节偏移和字节掩码。因此,第64 bit对应的字节偏移就是8,而字节掩码就是二进制的1000 0000。

另外的两个根节点分列于树的最左端和最右端。我们可以看到,它们的rn_bit字段都小于0,表明这两个根节点属于叶子节点。事实上,它们一个对应的是全0键值,一个对应的是全1键值。

在路由查找操作中,任何时刻都不能返回根节点本身。如果查找操作定位到了根节点,将代之以返回空指针。

2.4 重复键节点

BSD路由表中的重复键节点是指路由树中键值(IP地址)完全相同的叶子节点。

这些重复键节点由各自的rn_Dupedkey指针串成一个链表,通过位于链表头部的叶子节点挂在路由树中。位于链表中的重复键节点是按照掩码的精确程度从高到低排列的,即位于链表头部的叶子节点的掩码最精确,对于掩码连续的情况而言也就是它的掩码最长。这样在路由查找的时候如果找到了这串重复键节点,就可以保证掩码最长的路由最先匹配。

3 BSD路由表的路由条目

如前所述,BSD路由表是由一系列的内部节点和叶子节点组织起来的,这是BSD路由表的逻辑结构。如果从内存布局来讲,BSD路由表中的路由条目则是通过rtentry结构体来存放的,我们前面提到的内部节点和外部节点实际上都是存放在这个结构体中的。rtentry结构体的组成如图4所示。

我们可以看到,在rtentry结构体的头部就是由两个radix_node结构体组成的数组rt_nodes[2]。在这个数组中,第一个元素是叶子节点,负责存储路由表键值,即IP地址,第二个元素是内部节点,负责完成树的连接。因此,就一般情况而言,每当往路由树中添加一条路由的时候,我们实际上添加的是两个节点,一个叶子节点和一个内部节点,只不过这两个节点的存储空间是我们事先用rtentry结构体分配好了的。虽然这两个节点在物理上是紧挨着的,但是由于后续路由条目的加入,它们之间就可能会插入一系列的内部节点,而这些内部节点又分别属于各自的rtentry结构体,并对应着各自的叶子节点。


图4 rtentry 结构体

在rtentry结构体的剩余部分中存储的是这条路由的接口、接口地址以及网关路由等关键信息。

BSD radix树路由表的设计原理——查找、添加、删除

copy from 雨丝风片

在第一部分介绍完BSD radix树路由表的表头、节点、条目等数据结构之后,本部分将集中介绍BSD radix树路由表的查找、添加和删除算法。

目录:4 BSD路由表的路由查找:寻叶、辨重、回溯;  5 BSD路由表的路由添加:寻叶求异、存异求同、普适提升;  6 BSD路由表的路由删除:独有一叶、父子同源无后继、父子同源有后继、父子异源无后继、父子异源有后继

4 BSD路由表的路由查找

前已述及,BSD路由表使用的是经BSD修改之后的Patricia树,也就是BSD radix树。在这种树中,内部节点用于指定需要对查找键进行测试的一系列bit位置,而外部节点则用于存储键值。为了适合路由表的需求,每个叶子节点都会有一个与之对应的掩码。内部节点可能有也可能没有对应的掩码,这取决于在它的子树中是否存在能够将它的测试bit逻辑AND成0的掩码。于是,根据这些特性,BSD路由表中的路由查找就分成了三个步骤,即找到叶子节点进行精确匹配、在重复键链表中进行网络匹配和通过回溯过程进行网络匹配。

4.1 第一步:寻叶

这一步实际上就是Patricia查找,即从路由表的顶部节点开始,根据所遇内部节点中指示的bit测试位置进行测试,根据该bit是0还是1来决定继续往右走还是往左走,直至到达一个叶子节点为止。

当radix_node结构体作为内部节点的时候,它的bit测试位置是由rn_bit字段来给出的。但是,仅仅是这样一个bit测试位置对于有多个字节的IP地址来说显然是不合适的,在查找的时候再去定位这个bit会影响查找效率,所以在添加这个内部节点的时候就会根据bit测试位置计算一个字节偏移量和相应的字节掩码,即rn_Off和rn_bmask字段。字节偏移量用于指定bit测试位置所在字节相对于socket地址结构体起始处的偏移量,而字节掩码则是一个8 bit的掩码,其中只有一个bit为1,在通过字节偏移量定位了字节之后,即可由字节掩码进行bit测试操作。
 


图5 路由查找的第一步:寻叶

举例而言,BSD路由表的局部如图5所示。图中位于最上方的标记有64的那个内部节点就是radix树的顶端根节点,即在初始化路由表时生成的三个根节点中的中间一个,64这个数字是BSD地址的第一个bit在socket地址结构体中的偏移量。由于所有的路由查找操作都要从树的顶端开始向下进行,所以不管查找哪条路由,都会从BSD地址的第一个bit开始进行比较。

假设我们现在需要在这个radix树中查找FE80::210:5CFF:FEC2:38E7这条路由。从树的顶端开始,根据沿途内部节点指定的bit进行测试。这条路由的第64 bit为1,向右。第65 bit为1,继续向右。第71 bit为0,向左。第128 bit为0,继续向左。第160 bit为1,向右。这时,将会遇到一个rn_bit字段为负值的节点,即叶子节点,于是查找操作将停止在此处。

接下来的操作就是比较找到的这个叶子节点与我们的查找键是否匹配。比较操作是以字节为单位进行的,参与比较的字节数将以叶子节点掩码的最后一个非0字节为限,即若在此范围内叶子节点与查找键相同则认为匹配,查找操作成功结束,否则认为不匹配,并记录下查找键与叶子节点键值第一次出现不同的字节位置。在返回查找结果时有一点需要注意,即在任何时候都不能返回根节点自身,如果在这一步找到的叶子节点是一个根节点,那么就必须返回它的重复键指针rn_dupedkey,而不是它自己。

第一步的查找路径在图5中用红色曲线进行了标识。

4.2 第二步:辨重

如果在第一步中找到的叶子节点与查找键不满足匹配的条件,则需要遍历这个叶子节点的重复键链表。由于重复键链表中的叶子节点与第一步中找到的叶子节点的键值(也就是IP地址)是完全相同的,只是掩码呈逐渐缩短的趋势,因此可能在重复键链表中存在网络匹配的可能。
重复键处理的过程如图6所示。
 


图6 路由查找的第二步:辨重

图6是在图5的基础上绘制的。对于图中所示的三个重复键节点,我们用绿色的长短表示了它们各自掩码的长短,可以看出,掩码是呈逐渐变短趋势的。

由于在第一步中我们已经确定了查找键和叶子节点键值第一次出现不同的字节位置,因此可以方便地换算出查找键和叶子节点键值第一次出现不同的bit位置。前已述及,在叶子节点的radix_node结构体中,rn_bit字段就是由叶子节点的掩码中第一次出现0的bit位置换算出来的。因此,在接下来的重复键处理中,我们只需要把查找键和叶子键值第一次出现不同的bit位置跟叶子节点的rn_bit字段进行比较就可以方便地确定某个重复键节点是否满足网络匹配的条件,而不需要进行实际的掩码操作。

如果在重复键链表中有某个叶子节点满足网络匹配条件,则向调用者返回这个叶子节点。否则查找操作将回到最初找到的那个叶子节点(也就是重复键链表上的第一个节点),准备开始向树顶回溯了。

第二步的查找路径在图6中依然用红色曲线进行标识,实际上是将图5中的红色曲线延伸至重复键链表中。

4.3 第三步:回溯

到目前为止,我们只是使用作为查找键的IP地址在radix树中根据内部节点指示的bit测试位置找到了某个叶子节点,并进行了重复键处理,仍然没有找到匹配的叶子节点。这并不能排除在radix树中还存在有其它可能满足网络匹配条件的叶子节点,因此就需要沿着来时的内部节点路径向树顶回溯,寻求网络匹配的可能。回溯过程如图7所示。
 


图7 路由查找的第三步:回溯

回溯过程在图7中用蓝色曲线标识,方向从下到上。我们可以看出,回溯过程是从第一步中找到的那个叶子节点处开始,沿着每个节点的父指针rn_parent向树顶前进,这实际上就是我们在第一步中从树顶找到叶子节点所经由的路径,因此才把这一步称为回溯。

回溯途中经过的是一系列的内部节点,对于每一个内部节点,将会判断它是否挂的有掩码链表,即它的rn_mklist字段是否为空。掩码链表在图7中用粉红色表示。没有掩码链表的内部节点将不予考虑,直接通过。如果某个内部节点挂的有掩码链表,那说明在它的子树中可能存在着网络匹配的可能,需要停下来做一下判断再决定是否继续回溯。

这里首先就遇到了一个问题,究竟什么样的内部节点才挂有掩码链表?这实际上就是要回答回溯的必要性和可行性,这和radix树的组织方式即路由添加时的设计方法有关。首先需要明确下面两个问题。

为什么要回溯?

在第一步“寻叶”中,我们根据查找键的一系列bit测试结果找到了一个叶子节点,具体找到哪个叶子节点完全取决于radix树当时的组织形态,但有一点是可以确定的,那就是这个叶子节点的键值在其起点之后的某个长度之内一定和我们的查找键是相同的。如果这个长度就是叶子键值的长度,那我们在第一步中就匹配成功了,否则我们就要在树中寻找满足以下三个条件的叶子节点:

    .它和我们在第一步中找到的叶子节点有共同部分;
    .它的掩码短于或等于它和第一步中的叶子节点的共同部分;
    .它的掩码短于或等于查找键和第一步中的叶子节点的共同部分。

如果radix树中存在这样的叶子节点,那么它就必然和我们的查找键满足网络匹配条件,因此,回溯的目的就是要找到这样的叶子节点,而且还要保证找到的是所有满足上述条件的叶子节点中掩码最长的那一个。

为什么可以回溯?

如果radix树中存在满足上述条件的叶子节点,那我们通过回溯算法就一定可以找到它,这是由radix树的路由添加算法决定的。在这里我们只需要明确一个事实,那就是对于一个测试bit为n的内部节点来说,它的子树中的所有子孙叶子节点的键值的第0到n-1 bit都是相同的。举例而言,如果一个内部节点的测试bit是71,那么它的子树中的所有子孙叶子节点的键值的第0到70共 71个bit的内容都是相同的。因此,如果这个内部节点的子树中有某个叶子节点的掩码短于或等于71的话,那它的键值事实上就是这个子树中所有路由的公共部分,而它本身也就成了这个子树中所有路由的普适路由。正是radix树中的这些普适路由组成了回溯查找时的候选路由的集合。

一个内部节点的掩码链表正是它的子树中所有普适路由的记录链表,而对于一条普适路由来说,则会将其挂在它所能作为普适路由的最大可能的子树的顶端内部节点的掩码链表中。

对于回溯过程中遇到的每一个掩码链表非空的内部节点,我们都需要遍历它的掩码链表,只要发现一个满足前述三个条件的节点,就表明我们对查找键的网络匹配已经成功,回溯过程结束。

5 BSD路由表的路由添加

在对路由查找中的回溯过程的描述中我们已经提到一个事实,即对于一个测试bit为n的内部节点来说,它的子树中的所有子孙叶子节点的键值的第0到n-1 bit都是相同的。这个事实就是由路由添加操作来保证的。路由添加操作可以分为寻叶求异、存异求同和普适提升三个阶段。

5.1 第一步:寻叶求异

向路由表中添加一条路由的目的就是为了以后来查找它,因此,为了确定新路由在路由表中的位置,首先就要对新键值执行查找操作,也就是我们在路由查找部分中描述的第一步:寻叶。这一步实现的是Patricia查找,即从树顶开始按照内部节点的指示对新键值进行一系列的bit测试,直到遇见一个叶子节点为止。

假设有如图8所示的一个路由表局部,这和描述路由查找时使用的实际上是一个图,图中叶子节点存储的键值是FE80::8210:0C00:7EC2:3800。现在假设我们要向路由表中添加FE80::8210:0:0:0/76这条路由,先对这个新键值执行Patricia查找,以实际IP地址的起始bit为第64 bit:第64 bit为1,向右;第71 bit为0,向左;第128 bit为1,向右;第144 bit为0,向左;第160 bit为0,继续向左。因此,这个查找将沿着图8中的红色曲线一直找到存放着FE80::8210:0C00:7EC2:3800键值的那个叶子节点。

找到这个叶子节点之后,就需要判断它的键值和新键值是否相等。如果相等,则表示出现了重复键的情况,将根据新路由的掩码长度将其挂接在该叶子节点的重复键链表中的适当位置。在我们的例子中,叶子节点的键值与新键值并不相等,于是就要记录下它们第一次出现不同的bit位置,这也就是“寻叶”之后的“求异”操作。

新键值FE80::8210:0:0:0和叶子节点键值FE80::8210:0C00:7EC2:3800的比较结果如图9所示。在这个图中,蓝色部分是用二进制表示的。我们可以看出,在现有radix的所有测试bit上,新键值和叶子节点键值都是相同的,因此才会找到这个叶子节点。但它们的键值实际并不相同,而这两个键值的第一个不同bit就是第148 bit。

图8 路由添加的第一步:寻叶求异——寻叶

确定了新键值和前面找到的那个叶子节点键值的第一个不同bit,实际上也就是确定了这两个键值的共同部分。这些信息将决定新路由在radix树中的位置,具体操作则可以归纳为路由添加的第二步:存异求同。

图9 路由添加的第一步:寻叶求异——求异

5.2 第二步:存异求同

首先,让我们结合例子再来回顾一下前面提到的那个事实:对于一个测试bit为n的内部节点来说,它的子树中的所有子孙叶子节点的键值的第0到n-1 bit都是相同的,参见图10,图中用不同颜色的圆环来抽象表示各个内部节点的子树。测试bit为64的那个内部节点的子树中的节点的前64个bit都是相同的,测试bit为71的那个内部节点的子树中的节点的前71个bit都是相同的,以此类推。这是从添加第一条路由开始就必须遵从的规则,显然,此时对新路由的添加也必须遵从于这一规则。

我们在第一步中已经计算出Patricia找到的叶子节点键值和新键值第一次出现不同的bit位置,即我们例子中的第148 bit。为了不违反上述事实,新键值就不能属于测试bit在第148 bit右边的内部节点的子树,而只能属于测试bit在第148 bit左边的内部节点的子树。因此,我们接下来的工作就是确定新键值究竟应该属于哪个内部节点的子树,而实现方法就是沿着来时的路径向树顶回溯,找到正好把第148 bit卡在中间的两个内部节点。注意,在这个回溯过程中是不可能有哪个内部节点的测试bit正好等于第148 bit的,因为如果那样的话,在第一步的Patricia查找中就不会走到存放着FE80::8210:0C00:7EC2:3800键值的那个叶子节点那儿了。

图10 路由添加的第二步:存异求同——求同

回溯过程是从前面找到的那个叶子节点处开始的,在图10中用蓝色曲线表示。首先遇到的是测试bit为160的内部节点,它的子树中从0到159 bit都是相同的。由于新路由和叶子节点键值的第一个不同bit是第148 bit,属于0到159 bit的范围,因此新路由不能属于它的子树,否则就会违反前述规则。继续向树顶回溯,这次遇到的是测试bit为144的内部节点,它的子树中从0到143 bit都是相同的,因此新路由至少要属于这个内部节点的子树才能遵从前述规则。

就我们的例子来说,此时已经可以确定新路由应该插入在测试bit为144和160的两个内部节点之间,这是因为对新路由的第64、71、128和144 bit进行测试的结果都和前述叶子节点相同,我们必须保证路由查找操作在第144 bit之后、第160 bit之前对第148 bit进行测试,这样才能找到我们新加的这条路由。我们在前面提到过,每当往radix树中新加一条路由时,实际上都需要插入两个节点,即一个内部节点和一个叶子节点,或者说,路由条目的添加是以rtentry结构体为单位的,新加的两个节点正是这个结构体中的两个radix_node[2]结构体数组。

我们先来看看新路由的内部节点。它的测试bit显然就是第148 bit,而它就将替代测试bit为第160 bit的内部节点作为测试bit 为144 bit的那个内部节点的新的左孩子,而测试bit为第160 bit的那个内部节点则将成为它的某个孩子。

我们再来看看新路由的叶子节点,它存储着FE80::8210:0:0:0这个键值,而它此时显然也是新路由的内部节点的某个孩子。为了确定新叶子和测试bit为第160 bit的那个内部节点的左右名分,我们只需要判断新键值在新路由的内部节点的测试bit上是0还是1。对于我们的例子,新键值在第148 bit上为0,因此新叶子将作为新内部节点的左孩子,而测试bit为第160 bit的内部节点则作为右孩子。我们之所以可以在这里直接根据新键值就做出左右划分,是因为我们已经确定测试bit为第160 bit的内部节点的子树中所有叶子的第148 bit都是相同的,而新键值和这些叶子的第148 bit都是不同的。插入新路由之后的radix树如图11所示。

图11路由添加的第二步:存异求同——插入

5.3 第三步:普适提升

在经过寻叶求异和按异求同两个步骤之后,路由添加的操作只能说是完成了一半。之所以这么说,是因为前面的操作对于只有键值没有掩码的Patricia树来说是够了,但对于作为路由表的radix树来说则还不行,因为路由查找操作是以最长匹配为原则的,在键值匹配失败的情况下我们还要去尝试网络匹配的可能,这也就是我们在路由查找部分描述的寻叶、辨重和回溯三个步骤。所以,在把新路由插入radix树之后,我们还要继续处理它的掩码,处理的结果可能会影响到新路由的某个父节点的掩码链表,关于掩码链表的使用可以参见路由查找部分的回溯步骤。

我们知道,所谓路由的最长匹配查找,就是用某个路由条目的掩码和查找键进行逻辑与,然后再把逻辑与的结果和路由条目的键值进行比较,如果相同,则说明满足网络匹配条件,而查找操作最后返回的就是满足上述条件的掩码最长的那条路由。现在,我们假设A是radix树中的最外层内部节点之一,它有B和C两个作为叶子节点的孩子,如图12所示。


图12 路由添加的第三步:普适提升——普适

在图12中用红色曲线给出了路由查找的第一步“寻叶”,这一步是只用查找键进行而与掩码无关的。我们假设叶子节点C的键值和查找键匹配失败,在重复键处理过程中也没有匹配成功,这时我们就需要继续寻找网络匹配的可能。前面已经提到,所谓网络匹配就是叶子节点和查找键的带掩码的比较,这实际上可以理解为用查找键和叶子掩码进行逻辑与之后的结果在树中再次进行查找,对于一个满足网络匹配条件的叶子节点来说,这样的查找必然就会找到它那儿。让我们再来看图12,要让这样的查找能够找到叶子节点B的条件之一就是B的掩码能够改变查找键在内部节点A处的行进方向,也就是说,B的掩码要能够把内部节点A的测试bit逻辑与成0,图中蓝色曲线表示的就是这种带掩码的查找过程。满足上述条件的路由B就称为节点A的子树中的普适路由。

图13 路由添加的第三步:普适提升——提升

显然,一条路由的掩码越短,它就越可能作为更大一些的子树中的普适路由。而所谓普适提升就是在每次新加入一条路由的时候,我们都需要确定它究竟最大能作为哪一层子树中的普适路由,确定子树之后,这条新路由的掩码就会记录在作为该子树的顶点的内部节点的掩码链表中。

结合我们在前面举的例子,在radix树中加入FE80::8210:0:0:0/76这条路由之后,我们就需要对其进行普适提升操作。这条路由的掩码是76 bit,也就是说,它的掩码中的第一个0 bit将出现在第140 bit,参见图9。普适提升的过程如图13所示。我们从新路由开始向树顶回溯,第一个遇到的是测试bit为第148 bit的内部节点,显然,新路由的掩码可以把它的测试bit与成0,因此,新路由可以作为它的子树中的普适路由。继续回溯,遇到的是测试bit为第144 bit的内部节点,同样,新路由也可以作为它的子树中的普适路由。下一个遇到的是测试bit为第128 bit的内部节点,这一次新路由的掩码就不能把这个内部节点的测试bit与成0了,因此,新路由最大只能作为测试bit为第144 bit的内部节点的子树中的普适路由,新路由的掩码将记录在它的掩码链表中。这条普适提升的行进路径在图13中用蓝色曲线表示,而内部节点的掩码链表在图中用粉色表示。

一个内部节点的掩码链表中将记录它的子树中的所有满足普适条件的掩码。链表上的节点是按照掩码从长到短的顺序排列的,每个链表节点都有一个指针指向它们各自对应的叶子节点,而叶子节点也有一个指针指向这个掩码链表节点。

在路由查找的回溯过程中,每当我们遇到掩码链表非空的内部节点的时候,就会遍历它的掩码链表,直接判断每个链表节点的掩码是否满足我们在描述路由查找的回溯步骤时列出的三个条件,一旦满足,我们就可以通过指针直接找到对应的叶子节点,而这样找到的第一个叶子节点就是我们要查找的最长匹配路由。

6 BSD路由表的路由删除

BSD路由表中的路由删除操作涉及的内容是和路由添加相对应的。在描述路由删除步骤之前,我们需要明确一个事实,在前面已经见过,路由条目的内存管理是以rtentry结构体为单位的,但radix树的操作却看不到这个结构体的存在,它只看得到一系列的内部节点和叶子节点。因此,同一个rtentry结构体内的两个radix_node结构体在该路由刚加入radix树的时候是直接相连的,但随着之后的操作,这两个radix_node结构体可能就相隔很远了。如图14所示。


图14 路由删除——rtentry结构体的逻辑分离

在图14中,左边的图用绿色表示刚加入radix树中的一对radix_node结构体,其中,内部节点的测试bit为第148 bit。右边的图表示在这之后又加入了一对radix_node结构体,用粉色表示,其中,内部节点的测试bit为第150 bit。我们可以看到,由于新路由的加入,属于同一个rtentry结构体的两个绿色的节点在逻辑上被分开了。在删除路由的时候,我们就必须对这种情况进行处理,把rtentry结构体作为一个整体从radix树中摘除,具体做法因被删除节点的位置的不同而不同。

6.1 独有一叶

一般情况下,一个rtentry结构体内的两个radix_node结构体将同时出现在radix树中,但有一个例外,那就是出现了重复键的情况。参见路由查找以及路由添加部分的描述,在添加路由的时候,如果遇到了重复键的情况,我们就会把新路由直接挂到重复键链表中的适当位置。注意,重复键链表中都是叶子节点,它们是作为一个链表挂在同一个内部节点下的。因此,作为重复键加入的路由条目中的内部节点部分是闲置不用的。

图15 路由删除——独有一叶

非重复键链表头节点的删除过程如图15所示。在图中我们用绿色表示准备删除的路由条目对应的叶子节点,而用虚线在这个叶子节点的旁边画了一个内部节点,表示它虽然在物理上存在着,但却没有使用,不是radix树的一部分。对于这种情况,我们只需要直接将指定路由叶子节点从树中摘除,并将rtentry结构体释放即可。

6.2 父子同源无后继

除了前一节中描述的“独有一叶”的情况之外,其余的路由删除就需要牵扯到内部节点的处理了。所谓“父子同源无后继”指的是被删除的叶子节点是重复键链表上的唯一节点,而且它和作为父节点的内部节点同属于一个rtentry结构体,此时也只需要直接把这两个节点从radix树中摘除即可,如图16所示,图中用绿色表示一对属于同一个rtentry结构体的叶子节点和内部节点。


图16 路由删除——父子同源无后继

6.3 父子同源有后继

所谓“父子同源有后继”指的是被删除的叶子节点位于重复键链表头部,在它之后还有其它的重复键节点。对于这种情况,我们就不能把内部节点一删了事,而需要用替补上来的那个重复键节点对应的闲置内部节点空间去把被删除的叶子节点对应的内部节点替换下来。如图17所示,图中分别用绿色和粉色表示两对属于同一个rtentry结构体的叶子节点和内部节点,其中,绿色表示将要删除的路由对应的两个节点。

图17 路由删除——父子同源有后继

我们可以看到,在图17中,除了用粉色的叶子节点替换掉绿色的叶子节点作为重复键链表上的第一个节点之外,还要用原来闲置的粉色内部节点空间去把绿色的内部节点从radix树中替换下来,以便将绿色的节点对应的rtentry结构体空间作为一个整体释放。注意,这里对内部节点的替换是完全拷贝,因此粉色内部节点将完全替代绿色内部节点在radix树组织结构中的作用。

6.4 父子异源无后继

所谓“父子异源无后继”是指被删除的叶子节点是重复键链表中的唯一节点,且它和它的父节点不属于同一个rtentry结构体,也就是说,和它同属一个rtentry结构体的内部节点空间肯定在radix树中其它的某个地方。在图18中,我们分别用绿色和粉色表示两对属于同一个rtentry结构体的叶子节点和内部节点,其中,绿色表示将要删除的路由条目对应的两个节点。

图18 路由删除——父子异源无后继

这里的删除过程是这样的:首先是把绿色的叶子节点和粉色的内部节点从radix树中摘除,使粉色的叶子节点作为绿色内部节点的左孩子,然后再用粉色内部节点的空间去把绿色内部节点从radix树中替换下来。

6.5 父子异源有后继
所谓“父子异源有后继”是指被删除路由的叶子节点后面还有重复键节点,而它的父节点和它不属于同一个rtentry结构体。在图19中,我们分别用绿色和粉色表示两对属于同一个rtentry结构体的叶子节点和内部节点,其中,绿色表示将要删除的路由对应的两个节点,而粉色则表示将要替补上来的重复键叶子节点及其闲置内部节点。

图19 路由删除——父子异源有后继

具体删除过程是这样的:首先是把绿色的叶子节点从radix树中摘除,将粉色的叶子节点替补成测试bit为第150 bit的内部节点的左孩子,然后再用本来闲置的粉色内部节点空间将绿色内部节点从radix树中替换下来。

FreeBSD读书笔记—4进程管理—4.1进程管理介绍

copy from 雨丝风片

从今天开始,准备在这里写下我的FreeBSD读书笔记。书,当然是Marshall Kirk McKusickGeorge V. Neville-Neil 的《The Design and Implementation of the FreeBSD Operating System》了。我不是按顺序读的,所以也就看到哪儿写到哪儿了,不过最终形成的笔记还是按章节来组织,一小节一篇,边读边完善吧。具体形式我打算先是翻译,然后再结合源代码进行补充注释。

希望有机会看到这些文字的朋友能留下您的宝贵意见,让我们共同为BSD的推广传播而努力。万分感谢!

《The Design and Implementation of the FreeBSD Operating System》

Part II: Processes

Chapter 4. Process Management

4.1. Introduction to Process Management

    。。。

Multiprogramming

    。。。

Scheduling

对进程进行公平调度是件难办的事,这取决于可执行程序的类型以及调度策略的目标。所有的程序都可以按照它们的计算总量以及I/O 总量来进行分类。调度策略一般都试图在资源利用和程序运行用时之间寻求平衡。对于FreeBSD 的默认调度程序,也就是所谓的分时调度程序而言,一个进程的优先级将根据各种各样的参数进行周期性的重复计算,这些参数包括它已经用了的CPU 时间、它目前占有的或是为了运行而请求的内存资源的数量,等等。有些任务在进程执行过程中需要更为精确的控制,我们称之为实时调度,对此我们必须保证进程在指定期限之前或是按照某种特定的顺序完成它们的计算结果。FreeBSD 内核在通常的分时进程所用的队列之外专门用了一个单独的队列来实现实时调度。FreeBSD 内核还为那些运行在空闲优先级的进程实现了一个队列。对于一个属于空闲优先级的进程来说,只有当实时或分时调度队列中都没有可运行的进程了,而它自己的空闲优先级又等于或大于所有其它的可运行的空闲优先级进程时,它才会得到运行。

FreeBSD 分时调度程序使用的是一种基于优先级的调度策略,相对于那些长时间运行的批处理任务而言,这种策略更倾向于交互式程序(interactive programs ),比如文本编辑器。交互式程序一般都会表现为短暂的爆发式计算之后就是一段时间的静默状态或是I/O 操作。调度策略最初会为每个进程分配一个高的执行优先级,而且允许该进程执行固定的时间片(time slice )。将时间片执行完毕之后,进程的优先级就会降低,不过那些主动放弃CPU 的进程(通常是由于它们正在进行I/O 操作的缘故)则可以保持它们的优先级。非激活的进程的优先级将会得到提升。于是,占用大量CPU 时间的任务很快就会降为低优先级,而通常处于静默状态的交互式任务却可以保持在高优先级,这样一来,当它们做好运行准备之后,就会抢占到那些长时间运行的低优先级任务的前面去。像在文本编辑器中查找一个字符串这样的交互式任务会在短时内达到计算量的限度,优先级会因此而降低,不过当再次回到非激活状态而用户又在琢磨结果的时候,它就会返回到高的优先级。

像编译大型应用程序这样的任务可能会分为许多个小步骤来完成,每个组成部分就是在这些步骤中以独立的进程进行编译的。没有哪个单独步骤的长度足以一直运行至它的优先级被降低的时候,所以编译过程将作为一个整体影响着交互式程序。为了检测和避免这个问题,子进程的调度优先级将被扩散回它的父进程。当一个新的子进程开始的时候,它首先是以其父进程的当前优先级运行的。于是,当负责协调编译过程的程序(一般来说就是make )启动许多个编译步骤的时候,它的优先级就会因为其子进程们大量占用CPU 的行为而降低。在这之后由make 启动的那些编译步骤就会运行在较低的优先级上,这就使得较高优先级的交互式程序能够优先运行。

系统还需要一种调度策略来处理由于没有足够的内存以维持所有想要运行的进程的执行上下文而导致的问题。这种调度策略的主要目的就是将颠簸(thrashing )减到最少—— 所谓颠簸是指因为内存太少,大部分时间都是在系统中处理page fault 和调度进程而不是在用户模式下执行应用程序代码的现象。

系统必须检测并消除颠簸。它通过观察空闲内存总量来检测颠簸。当系统中没有多少空闲的内存页面而又存在大量的新内存请求时,它就会认为自己已处于颠簸之中。系统通过将最近一次运行距当前时间最久的进程标记为不准运行来减小颠簸。这个标记将会让pageout daemon 把与这个进程相关的所有页面都转出到备份存储设备上。在绝大多数的架构上,内核还可以把被标记进程的用户结构体也转出到备份存储设备上。这些操作的结果就是把这个进程给交换出去(参见5.12 节)。由于阻塞这个进程而释放的内存就可以被分发给剩余的进程,一般来说这些进程此后就可以继续运行了。如果颠簸仍在继续,就需要进一步选择运行中的进程加以阻塞,直至内存足以让剩余的进程有效运行为止。最后,当足够多的进程完成运行并释放它们的内存之后,那些被阻塞的进程就可以恢复运行了。不过,即使系统中没有足够的内存,被阻塞的进程在大约20 秒之后也会被允许恢复运行。通常,颠簸情形会因此而重现,于是就得选择某个其它的进程加以阻塞(或者采取某种管理措施来降低负荷)。