tcpip stack(2) -- L3 send and receve

1. 数据传输的数据结构

在BSD Socket层使用struct msghdr保存数据。在INET Socket层以下使用struct sk_buff保存数据，这个结构被整个网络协议栈使用，如MAC或其他L2链路协议，三层IP，四层TCP或UDP等。并且其中的成员变量在结构从一层向另一层传递时解析本层的数据头。

2. 网络层数据收发

   a.发送数据

 raw_sendmsg
     |
     |- ip_router_output_flow 根据saddr和daddr在rt_hash_table中查找路由表。
     |                        如果没有找到则查找fib，并__mkroute_output创建struct rtable。将rtable加入rt_hash_table
     |                        neigh_create:根据rtable->dst_entry创建struct neigh邻居,设置定时操作neigh_timer_handler,
     |                        arp_constructor设置arp处理函数
     |
     |- ip_append_data   将大数据分片,创建struct sk_buffer,并将其加入struct sk->sk_write_queue
     |
     |- ip_push_pending_frames
           |
           |- ip_finish_skb  构造ip头
           |
           |- ip_send_skb
                 |
                 |- ip_local_output--> dst_output-->ip_output (__mkroute_output中指定rth->dst.output=ip_output)
                      |
                      |- ip_finish_output      如果在hh_cache中找到daddr信息则将数据传到driver
                     |                                   否则调用struct dst_entry->neighbour->output (neigh_resolve_output)
                     |- neigh_resolve_output
                           |
                           |- neigh_event_send  更改邻居状态为NUD_INCOMPLETE,neigh_timer_handler将发送arp请求(arp_solicit)
                          |     ......
                          |- apr_rev -> neigh_update      接收arp报文,更新邻居系统
                                |
                                |- neigh_resolve_output
                                     |
                                     |- neigh_hh_init     更新hh_cache
                                     |
                                     |- dev_hard_header   初始化以太网报文头
                                     |
                                     |- dev_queue_xmit 数据发送至硬件抽象层(neigh->ops->queue_xmit)
                                           |
                                           |- dev->netdev_ops->ndo_start_xmit  驱动数据发送函数

        b.发送数据
 |- netif_rx              驱动创建skb后调用此函数，函数skb加入struct softnet_data->input_pkt_queue中，之后出发软中断
 |  ......
 |- net_rx_action         数据接收软中断
     |
     |- process_backlog
           |- __skb_dequeue  从softnet_data->input_pkt_queue接收数据
           |
           |- __netif_receive_skb  调用struct packet_type->func(inet_init是注册ip_packet_type)
                 |
                 |- ip_rcv   解析ip头
                 |
                 |- ip_rcv_finish
                     |
                     |- ip_route_input_common    查找路由表，如果没有则加入fib和rt_hash_table
                     |
                     |- ip_local_deliver                 (struct dst_entry->input)
                         |
                         |- ip_local_deliver_finish
                         |      |
                         |      |- raw_v4_input     将skb加入struct sock->sk_receive_queue
                         |
                         |- 如果数据不是raw类型，则进入L4处理函数struct net_protocol->handler

tcpip stack(1) -- init

1. socket_init()建立vfsmount文件系统
static struct vfsmount *sock_mnt __read_mostly;
static int __init sock_init(void)
{
    skb_init(); //为socket buffer创建高速缓存
    init_inodecache(); //为struct sock_alloc创建高速缓存

    //创建已安装文件系统
    register_filesystem(&sock_fs_type);
    sock_mnt = kern_mount(&sock_fs_type);
}

static struct file_system_type sock_fs_type = {
    .name = "sockfs",
    .mount = sockfs_mount,
    .kill_sb = kill_anon_super,
};

static struct file_system_type *file_systems;
int register_filesystem(struct file_system_type * fs)
{
    struct file_system_type ** p;
    /*将sock_fs_type注册到全局的file_systems中*/
    p = find_filesystem(fs->name, strlen(fs->name));
    if(p)
        return error;
    else
        *p = fs;
}

函数kern_mount()将调用vfs_kern_mount()创建vfsmount
struct vfsmount *
vfs_kern_mount(struct file_system_type *type, int flags, const char *name, void *data)
{
    struct vfsmount *mnt;
    struct dentry *root;

    mnt = alloc_vfsmnt(name); //从高速缓存中获取vsfmount结构
    root = mount_fs(type, flags, name, data);

    //建立vfsmount与dentry的对应关系
    mnt->mnt_root = root;
    mnt->mnt_sb = root->d_sb;
    mnt->mnt_mountpoint = mnt->mnt_root;
    mnt->mnt_parent = mnt;
    return mnt;
}

创建dentry对象
struct dentry *
mount_fs(struct file_system_type *type, int flags, const char *name, void *data)
{
    struct dentry *root;
    struct super_block *sb;

    root = type->mount(type, flags, name, data); //调用sock_fs_type中的sockfs_mount()
    sb = root->d_sb;

    return root;
}
sockfs_mount()将调用mount_pseudo()
static const struct super_operations sockfs_ops = {
    .alloc_inode = sock_alloc_inode,
    .destroy_inode = sock_destroy_inode,
    .statfs = simple_statfs,
};
static const struct dentry_operations sockfs_dentry_operations = {
    .d_dname = sockfs_dname,
};
struct dentry *mount_pseudo(struct file_system_type *fs_type, char *name,
const struct super_operations *ops,
const struct dentry_operations *dops, unsigned long magic)
{
    struct super_block *s = sget(fs_type, NULL, set_anon_super, NULL);
    //创建super block并注册到全局super_blocks中
    struct dentry *dentry;
    struct inode *root;

    root = new_inode(s); //创建inode对象
    dentry = d_alloc(NULL, &d_name); //创建dentry对象

    //将创建的3个对象建立联系
    ……
    return dentry;
}
初始化完成后：sock_mnt->vfsmount->dentry->inode->superblock
2. inet_init()网络网络层初始化
static int __init inet_init(void)
{
    proto_register(/*tcp, udp, raw*/); //将inet socket结构proto注册到proto_list中

    sock_register(&inet_family_ops); //将协议族net_proto_family注册到net_families中

    inet_add_protocol(/*tcp, udp, icmp*/);
    //将协议处理接口结构net_protocol注册到inet_protos中

    //建立inetsw链表与inetsw_array数组的对应关系
    for (r = &inetsw[0]; r < &inetsw[SOCK_MAX]; ++r)
        INIT_LIST_HEAD(r);
    for (q = inetsw_array; q < &inetsw_array[INETSW_ARRAY_LEN]; ++q)
        inet_register_protosw(q);
    ……
}
Socket基本结构：

3. socket()
SYSCALL_DEFINE3(socket, int, family, int, type, int, protocol)
{
    struct socket *sock;
    /*调用sock_alloc创建struct socket_alloc，其中包含struct socket和struct inode;
     调用sock->create()-------->inet_create()创建struct sock
    */
    retval = sock_create(family, type, protocol, &sock);
    //创建文件描述符struct file，将file指针放入fd数组中
    retval = sock_map_fd(sock,flags&(O_CLOEXEC|O_NONBLOCK));
    return retval;
}
结构如图：
                                             struct socket_alloc
                                                    |-------------|
                                                    |  socket    |------>sock
                                                    |-------------|
                                 |----dentry->|   inode    |------------>
      Struct file->path-|                   |-------------|                  Super_block
                                 |----fsmount->dentry->inode------>

用户进程通过文件描述符就可以找到INET socket。BSD socket层从已注册的INET proto_ops结构中调用INET层socket支持例程来执行工作。例如，一个ipv4的BSD socket建立请求，将用到下层的INET socket的建立函数。为了不把BSD socket与tcpip的特定信息搞混，INET socket层使用它自己的数据结构struct sock，它与BSD socket结构相连。Sock结构的协议操作指针也在初始化时建立，它依赖于被请求的协议。如果请求时TCP，那么sock结构的协议操作指针将指向TCP连接所必须的TCP协议操作集。
4. net_dev_ini ()网络设备抽象层初始化
static int __init net_dev_init(void)
{
    //Initialise the packet receive queues.
    for (i = 0; i < NR_CPUS; i++) {
        struct softnet_data *queue; queue = &per_cpu(softnet_data, i);
        skb_queue_head_init(&queue->input_pkt_queue);

        queue->throttle = 0;
        queue->cng_level = 0;
        queue->avg_blog = 10; /* arbitrary non-zero */
        queue->completion_queue = NULL;
        INIT_LIST_HEAD(&queue->poll_list);
        set_bit(__LINK_STATE_START, &queue->backlog_dev.state);
        queue->backlog_dev.weight = weight_p;
        queue->backlog_dev.poll = process_backlog;
        atomic_set(&queue->backlog_dev.refcnt, 1);
    }

    open_softirq(NET_TX_SOFTIRQ, net_tx_action, NULL);
    open_softirq(NET_RX_SOFTIRQ, net_rx_action, NULL);
}
为每个CPU创建一个struct softnet_data的队列，表示要交给此CPU处理的数据包。并注册网络相关的软中断。
网络设备抽象层通过struct net_device调用指定的device driver与设备通信。
5. device driver initialize
用insmod加载驱动模块时，内核会默认执行模块中的module_init()函数
static int __init xxx_init_module (void)
{
    return pci_register_driver(&xxx_pci_driver);
}
module_init(xxx_init_module);

pci_register_driver()注册设备驱动程序(struct pci_driver)
int __pci_register_driver(struct pci_driver *drv, struct module *owner,
const char *mod_name)
{
    /*将strcut pci_driver加到总线链表中，并执行.probe()初始化设备驱动 */
    driver_register(&drv->driver);

    /* 为驱动创建sysfs文件 */
    pci_create_newid_file(drv);
    pci_create_removeid_file(drv);
}
strcut pci_driver->probe()调用驱动初始化函数初始化struct net_device
static int __devinit xxx_init_one (struct pci_dev *pdev, const struct pci_device_id *ent)
{
    struct net_device *dev = NULL;
    xxx_init_board (pdev, &dev);
    /* 设备抽象层提供驱动操作函数 */
    dev->open = xxx_open;
    dev->hard_start_xmit =xxx_start_xmit;
    dev->poll = xxx_poll;
    dev->stop = xxx_close;
    dev->do_ioctl = netdev_ioctl;
}

study kernel(3) -- memory,vfs

一、 内存及内存管理
1. 内存地址
三种不同的地址：
1． 逻辑地址：每个逻辑地址都有一个段和偏移量组成，偏移量指明从段开始的地方到实际地址之间的距离。Linux中逻辑地址总是与线性地址一致。
2． 线性地址：虚拟地址。32位系统有4G的线性地址，64位系统有8G线性地址。
3． 物理地址：物理内存的实际地址。
地址转换关系：
逻辑地址通过分段单元转换为线性地址，之后再通过分页单元转换为物理地址。
2. 页
页：线性地址被分成固定长度为单位的组。页内部连续的线性地址被映射到连续的物理地址中。页既指一组线性地址，又指这组地址中的数据。Linux每一页有4KB容量。
页框：或物理页。一个页框包含一个页，因此页框长度与页长度一致。页可存放在任何一个物理页中。页框就是物理内存。
页表：保存线性地址和物理地址之间映射的页。
内核中用页述符struct page描述每一个页框的状态信息，所有的页描述符都保存在mem_map数组中。
struct page {
unsigned long flags; //描述页框状态
atomic_t _count; //页框的引用计数
atomic_t _mapcount; //页框中页表数目
void *virtual;; //页框的虚拟地址
……
}
转换关系如图：

3. 内存管理区

内核物理内存划分为不同的区，并用struct zone描述每个区。每个管理区的分配器可以在他的物理内存区域添加删除页框。

4. slab分配器
slab层把不同对象划分为高速缓存组，每个高速缓存被划分为多个slab，每个slabe由一个或多个连续的页框组成，页框中包含对象的数据结构。
如struct inode由inode_cachep高速缓存进行分配。这个高速缓存有一个或多个slab组成。每个slab包含尽可能多的struct indoe对象。当内核请求分配新的inode结构时，内核从部分满或空的slab返回一个指向已分配但未使用的结构的指针。当内核用完后，slab分配器把该对象标记为空闲。

Slab的使用：(struct task_struct)
a. 创建高速缓存
static struct kmem_cache *task_struct_cachep; //全局变量
void __init fork_init(unsigned long mempages) //内核初始化调用
{
    task_struct_cachep =
    kmem_cache_create("task_struct", sizeof(struct task_struct),
    ARCH_MIN_TASKALIGN,SLAB_PANIC|SLAB_NOTRACK, NULL);
}
b. 申请进程描述符
当创建子进程会有如下过程
fork()->sys_fork()->do_fork()->copy_process()->dup_task_struct()
static struct task_struct *dup_task_struct(struct task_struct *orig)
{
    struct task_struct *tsk;
    tsk = kmem_cache_alloc (task_struct_cachep, GFP_KERNEL);
                                            //从高速缓存中返回一个进程描述符的指针
    ……
}
c. 释放进程描述符
当进程被销毁时会有如下过程：
free_task()->free_task_struct()
即执行kmem_cache_free(task_struct_cachep, (tsk))，将tsk所指的进程描述符标记为空闲。
二、 进程地址空间
1. 进程虚拟内存的使用
Linux操作系统采用虚拟内存管理技术，使得每个进程都有各自互不干涉的进程地址空间。进程的可用32 位地址系统支持的全部4G 线性空间。进程的线性地址空间分成两部分：1. 从0x00000000 到 0xbfffffff 的线性地址，无论用户态还是内核态的进程都可以寻址。2. 从0xc0000000 到 0xffffffff 的线性地址，只有内核态的进程才能寻址。
对普通进程来讲，它都会涉及到5种不同的数据段。
1．代码段：代码段是用来存放可执行文件的操作指令，也就是说是它是可执行程序在内存种的镜像。代码段需要防止在运行时被非法修改，所以只准许读取操作，而不允许写入操作。
2．数据段：数据段用来存放可执行文件中已初始化全局变量，就是存放程序静态分配的变量和全局变量。可读可写。
3．BSS段：包含了程序中未初始化全局变量，在内存中 bss段全部置零。
4．堆：堆是用于存放进程运行中被动态分配的内存段，它大小并不固定，可动态扩张或缩减。当进程调用malloc等函数分配内存时，新分配的内存就被动态添加到堆上；当利用free等函数释放内存时，被释放的内存从堆中被剔除。
5. 栈：栈是用户存放程序临时创建的局部变量。除此以外在函数被调用时，其参数也会被压入发起调用的进程栈中，并且待到调用结束后，函数的返回值也回被存放回栈中。由于栈的先进先出特点，所以栈特别方便用来保存/恢复调用现场。从这个意义上将我们可以把堆栈看成一个临时数据寄存、交换的内存区。
2. 创建进程的地址空间
内核使用内存描述符struct mm_struct表示进程的地址空间。当创建新的进程时内核调用copy_mm()函数建立新进程的所有页表和内存描述符来创建进程的地址空间：
static int copy_mm(unsigned long clone_flags, struct task_struct * tsk)
{
    struct mm_struct * mm, *oldmm;
    oldmm = current->mm;

    if (clone_flags & CLONE_VM) { //线程使用父进程地址空间
        atomic_inc(&oldmm->mm_users);
        mm = oldmm;
        goto good_mm;
    }

    mm = dup_mm(tsk); //创建子进程地址空间
}

struct mm_struct *dup_mm(struct task_struct *tsk)
{
    struct mm_struct *mm, *oldmm = current->mm;

    mm = allocate_mm(); //从slab中分配一个mm_struct
    memcpy(mm, oldmm, sizeof(*mm));

    mm_init(mm, tsk); //初始化结构体并为进程创建pgd和pte

    init_new_context(tsk, mm);

    dup_mm_exe_file(oldmm, mm);

    dup_mmap(mm, oldmm); //创建VMA
}
VMA指定地址空间内连续区间上的一个独立内存范围来代表多种类型的内存区域。VMA用struct vm_area_struct描述。
static int dup_mmap(struct mm_struct *mm, struct mm_struct *oldmm)
{
    struct vm_area_struct *mpnt, tmp；
    struct rb_node **rb_link, rb_parent；

    //扫描父进程的VMA链表
    for (mpnt = oldmm->mmap; mpnt; mpnt = mpnt->vm_next) {
        tmp = kmem_cache_alloc(vm_area_cachep, GFP_KERNEL);
        *tmp = *mpnt; //复制父进程VMA

        //将复制的VMA插入到子进程的VMA链表和红黑树中
        _vma_link_rb(mm, tmp, rb_link, rb_parent);
        rb_link = &tmp->vm_rb.rb_right;
        rb_parent = &tmp->vm_rb;
    }

        /*拷贝父进程所有vm_area_struct对应的页目录、页表。将父子进程中私
         有的、可写的页标记为只读的，以便这种页面能用写时复制机制进行处理
        */
        copy_page_range(mm, oldmm, mpnt);
}
虚拟地址、虚拟地址区域、内存描述符之间关系如图：

3. 缺页异常处理
内核中的函数直接获得动态内存，内核是操作系统中优先级最高的成分,可采用kmalloc/vmalloc分配连续和非连续线性区得到内存。
用户态进程调用malloc分配内存时，请求被认为是不紧迫的，因此，当用户态进程请求动态内存时，并没有立即获得实际的物理页框，而仅仅获得对一个新的VMA。这样，当用户进程真正向这些线性区写的时候，就会产生缺页异常，在缺页异常处理程序do_page_fault()中获得真正的物理内存。

三、 虚拟文件系统
虚拟文件系统(VFS)是一个内核软件层，用来处理与Unix标准文件系统相关的所有系统调用。它与驱动程序联系的更加紧密。其分层结构如图：

1. 主要数据结构
a. 超级块对象结构struct super_block
该结构保存了一个被安装在linux系统上的文件系统的信息。对于基于磁盘的文件系统，该结构一般和保存在磁盘上的"文件系统控制块"对应。也就是说如果是磁盘文件系统，该结构保存的磁盘文件系统的控制信息。
b. 索引节点对象结构struct inode
该结构中存储的是一个特定文件的一般信息，对于一个基于磁盘的文件系统，该结构对应磁盘上的文件数据控制块。每一个inode结构都对应一个inode节点号，这个节点号是唯一的，它也唯一标识一个文件系统中的文件。
c. 文件对象结构struct file
该结构中存储的是一个打开的文件和打开这个文件的进程间的交互信息。该结构保存在内核的内存区，在打开文件时被创建，关闭文件时被释放。
d. 目录项对象结构struct dentry
该结构存储的是目录实体和对应的文件的关联信息。
2. 各数据结构之间的关系
内核创建文件对象并返回文件描述符索引号给用户空间。文件对象引用目录项对象，后者引用索引节点对象。这两个对象都引用超级块对象。多个文件对象可以引用同一个目录项对象。一个目录项对象还可能引用另一个目录项对象。如图：

study kernel(2) -- sync, interrupt

三、 内核同步
1. 原子操作
linux提供了一系列C语言函数来实现内核中的原子操作，这些函数又分为两类，分别针对bit变量和整数变量进行原子操作。它们的共同点是在任何情况下都是原子的，内核代码可以安全的调用它们而不被中断，而且它们都依赖底层CPU的原子操作来实现-所有这些函数都是CPU架构相关的。其实现在atomic.h和bitops.h中
2. 禁止中断
CPU具备屏蔽中断和打开中断的功能，这项功能可以保证正在执行的内核控制路径不被中断处理程序所抢占，防止某些竞争条件的发生。Linux提供了local_irq_disable()/local_irq_enable()，local_irq_save()/local_irq_restone()来实现屏蔽/开启中断的功能。
另外，内核提供的另外一些函数隐含的调用了屏蔽中断的功能，如spin_lock_irq()。中断机制对于内核的正常运行是非常重要的，因为异步I/O，进程调度等很多重要操作都依赖于中断，而在屏蔽中断期间所有的中断都无法得到处理，而必须延迟到解除屏蔽以后。所以长时间的屏蔽中断是很危险的，有可能造成数据丢失乃至系统崩溃等后果。这就要求在屏蔽了中断之后，当前的内核控制路径应当尽快的执行完临界区的代码，然后解除对中断的屏蔽。尤其需要注意的是，屏蔽中断后的内核控制路径不能调用有可能引起阻塞的函数，因为这些函数会使进程睡眠，然后主动调用schedule()来放弃CPU。
3. 自旋锁
自旋锁在试图加锁的时候，如果当前锁已经处于锁定状态，加锁进程就进行"旋转"，用一个死循环测试锁的状态，直到成功的取得锁。自旋锁的这种特性避免了调用进程的挂起，用"旋转"来取代进程切换。而上下文切换需要一定时间，并且会使高速缓冲失效，对系统性能影响是很大的，所以自旋锁在多处理器环境中非常方便。当然，被自旋锁所保护的"临界代码"一般都比较短，否则就会浪费过多的CPU资源。
当一个内核控制路径与中断处理程序之间存在竞争条件时，需要使用中断安全版本的自旋锁spin_lock_irq()/spin_lock_irqsave()，这个函数首先禁止本地CPU上的中断，然后试图获得自旋锁，这样在执行临界区代码的时候，本地CPU不会被中断处理程序所抢占。同时，由于禁止的只是本地CPU上的中断，系统中其它CPU仍然可以对外部中断进程处理。
自旋锁是互斥的，同一时刻只能有一个内核控制路径拥有自旋锁。
4. 信号量
信号量为了解决多个内核控制路径竞争资源的问题，这些内核控制路径可能是单处理器系统中分时执行的控制路径，也可能是多处理器系统中的并行执行的控制路径。在试图获得信号量的时候，如果信号量繁忙，相应的内核控制路径会挂起，直到信号量被释放的时候控制路径才恢复运行。使用信号量的时候，先声明一个semaphore类型的对象，然后调用函数sema_init()来初始化它。要想获得信号量的掌握权，需要调用函数down_interruptible()/down()，此时如果信号量忙，调用进程被挂起，加入到信号量的等待队列中去；释放信号量的时候则调用up()函数，系统同时会唤醒正在等待信号量的进程，唤醒的顺序与等待的顺序是一致的。
注：中断上下文只能用自旋锁，而任务睡眠时只能使用信号量。
四、 中断
中断由硬件设备生成，再由中断控制器向处理器发送相应信号。处理器检测到此信号，便中断自己的当前工作转而处理中断。此后处理器会通知系统已经产生中断，操作系统就可以对这个中断进行适当的处理。
IRQs(Interrupt ReQuests)：外设引起的中断应该被称为中断请求。中断请求号和中断号中间有一定的映射关系。这个映射关系和平台有关。
1. 中断处理的层次
中断的嵌套会带来很多问题，在中断处理函数重屏蔽其他中断源可以解决防止中断嵌套，但是长时间地屏蔽中断会导致内核遗漏掉一些重要的中断。 因此，中断处理函数重中断的屏蔽时间应该越短越好。
中断处理函数应满足下面两个要求：
a. 代码量应越少越好，以便中断函数的快速执行。
b. 如果中断处理函数也可以并发，那么他们之间不得互相影响。
上述两个条件中，后者可以通过优化中断处理函数的设计和编码来实现，但想实现前者，则不那么容易。 但实际上，并非中断处理程序的所有工作的重要性都是相同的，通常来讲，一个中断服务程序可根据其是否需要马上处理而分为三个部分：
Critical actions:
这个部分必须要在中断发上后马上执行，否则将无法保证系统的稳定性或者数据操作的正确性。 例如，当网卡上有数据包到达后，内核必须马上将数据从网卡挪到内存中，如果这个动作没有在中断发生后马上执行，该数据可能会被后续接收到的数据覆盖。 在进行这个 critical actions 的时候，其他的中断必须被关掉。
Noncritical actions:
这些actions相比前面的critical actions重要性稍低，但是也应该尽快完成。 不同的是，它可以在打开其他中断的前提下进行，因此可能会被其他的中断所"中断"(受其他的中断影响)。
Deferrable actions:
Deferrable actions 的重要性比前两者都低，可以不用放在中断处理函数中进行。内核可以等到没什么事情的时候再处理它。
对中断处理函数的划分，并根据各个部分的不同的重要性，可以将中断函数拆成若干不同的片段，放在不同的上下文中执行， 很大程度上，在保证了系统事件完整性的前提下，防止了中断的嵌套。
2. 中断上半部
a) 中断的处理
struct irq_desc irq_desc[NR_IRQS] __cacheline_aligned_in_smp = {
[0 ... NR_IRQS-1] = {
.handle_irq = handle_bad_irq,
.depth = 1,
.lock = __RAW_SPIN_LOCK_UNLOCKED(irq_desc->lock),
}
};
中断处理函数do_IRQ()根据中断号被存放到irq_desc数组中；从irq_desc中，可以依据中断号，找到相应的中断处理程序。
struct irq_desc用于描述一个IRQ，其中：
handler_data: 指向一些与IRQ处理函数相关的数据。当中断发生时，handle_irq被调用。
action: 这个数据结构提供了当中断发生后需要执行的中断处理程序。
b) 中断处理程序的注册
static inline int __must_checkrequest_irq (unsigned int irq, irq_handler_t handler,
unsigned long flags, const char *name, void *dev)
{
return request_threaded_irq(irq, handler, NULL, flags, name, dev);
}

request_threaded_irq首先从内核中获取了这个irq对应的irq_desc，然后创建结构体irqaction，设置action的handler, flags, name, dev_id。然后调用__setup_irq完成后续工作。
Flags标志：
SA_INTERRUPT：执行中断处理程序时屏蔽所有中断线。而默认没有这个标志时，除了正在运行的中断处理程序对应的中断线被屏蔽外，其他所有中断都是激活的。
SA_SAMPLE_RANDOM: 内核通过一系列的事件的相关信息来生成随机数,如果有这个标志，则调用rand_initialize_irq将IRQ添加到熵池所需的相关数据结构中。
SA_SHIRQ：可以在多个中断处理程序之间共享中断线。
3. 中断下半部
下半部的任务就是执行于中断处理密切相关但中断处理程序本身不执行的工作。提供如下几种机制：
c) 软中断
i. 注册软中断处理程序
软中断项：
struct softirq_action{
void (*action) (struct softirq_action *); //软中断处理程序
void *data;
}
软中断向量表：
static struct softirq_action softirq_vec[NR_SOFTIRQS];
函数open_softirq()通过软中断索引号注册软中断处理函数

ii. 触发/禁止软中断
函数raise_softirq()/raise_softirq_irqoff()通过软中断索引号修改软中断状态寄存器irq_stat

iii. 软中断守护线程函数do_softirq()核心部分代码：
void do_softirq(void){
struct softirq_action *h;
__u32 pending;

if (in_interrupt()) //处于中断上下文则返回
return;

pending = local_softirq_pending(); //查询软中断状态寄存器irq_stat判断事件是否发生
set_softirq_pending(0);
h = softirq_vec; //软中断向量表
do{
if (pending & 1) //事件发生则执行软中断处理程序
h->action(h);
h++;
pending >>= 1;
}while (pending);
}
d) tasklet
Tasklet为一个软中断，考虑到优先级问题，分别占用了软中断向量表中的0号和5号软中断。
i. 创建tasklet
struct tasklet_struct
{
struct tasklet_struct *next;
unsigned long state;
atomic_t count;
void (*func)(unsigned long);
unsigned long data;
};
调用DELCARE_TASKLET创建struct tasklet_struct结构体并注册tasklet处理程序。
调用tasklet_schedule()/tasklet_hi_schedule()将struct tasklet_struct加入tasklet向量表tasklet_vec/tasklet_hi_vec。
ii. tasklet注册软中断处理程序
在softirq_init()中调用注册tasklet软中断处理函数tasklet_action()/tasklet_hi_action()
static void tasklet_action(struct softirq_action *a){
struct tasklet_struct *list;

list = __this_cpu_read(tasklet_vec.head); //读取tasklet向量表

while (list) {
struct tasklet_struct *t = list;
list = list->next;
if (!atomic_read(&t->count))
t->func(t->data); //如果count为0则执行tasklet处理程序。
}
}
e) 软中断与tasklet的区别
软中断必须确保共享数据的安全，因为两个甚至更多相同类别的软中断有可能在不同的处理器上同步执行。而两个同类型的tasklet不能同时执行。

study kernel(1) -- process, schedule

一、 进程
1. 进程描述符
内核用进程描述符task_struct表示用户空间中进程的所有信息。
task_struct 定义如下：
struct task_struct {
volatile long state; //进程运行状态
struct thread_info; //线程描述符
struct mm_struct; //描述内存存储信息
struct tty_struct; //与进程相关的tty
struct fs_struct; //当前目录
struct signal_struct; //所接收的信号
......
};
其中，state用于表示进程当前的运行状态进程状态：
1． TASK_RUNNING：进程正在执行或是可执行的，调度器可将其加入运行队列(runqueue)。
2． TASK_INTERRUPTIBLE/TASK_UNINTERRUPTIBLE：进程由于某些原因（通常是状态不满足）而被阻塞，当条件满足后，则会重新变成TASK_RUNNING。不同的是， TASK_INTERRUPTIBLE，可以响应内核发出的信号；而TASK_UNITERRUPTIBLE不响应内核发出的信号。
3． EXIT_ZOMBIE：进程已经结束，但此时任占用内核栈、thread_info、task_struct，为了向父进程提供信息。当父进程调用了wait4()后，信息会被释放。
4． __TASK_STOPPED：进程停止运行。
2. 创建进程
fork()系统调用的功能是为当前进程创建一子进程。调用此函数时，系统将调用宏指令_syscall0，并做最终调用内核接口sys_fork()。
asmlinkage int sys_fork(struct pt_regs regs)
{
return do_fork(SIGCHLD, regs.esp, ®s, 0, NULL, NULL);
}
SIGCHLD是在定义的一个宏，它告诉do_fork()函数应创建一个子进程，即创建并初始化进程描述符task_struct以及他包含的其他结构。
3. 创建内核线程
Linux内核可以看作一个服务进程。内核需要多个执行流并行，为了防止可能的阻塞，多线程化是必要的。内核线程的调度由内核负责，一个内核线程处于阻塞状态时不影响其他的内核线程，因为其是调度的基本单位。
内核线程是由kernel_thread()函数在内核态下创建的:
int kernel_thread(int (*fn)(void *), void * arg, unsigned long flags)
{
struct pt_regs regs;
memset(®s, 0, sizeof(regs));
......
/* Ok, create the new process.. */
return do_fork(flags|CLONE_VM|CLONE_UNTRACED, 0, ®s, 0, NULL, NULL);
}
内核线程的创建本质上也是建立了一个task_struct。其中CLONE_VM标志表示，避免复制进程的页表。内核线程和调用的进程(current)具备相同的进程空间，因为调用者运行在进程的内核态，所以进程在内核态时共享内核空间。

二、 进程调度
4. 进程调度类型
Linux进程按照下面调度类型被调度：
SCHED_FIFO：先进先出的实时进程。如果没有其他可运行的更高优先级实时进程，该进程将一直占用CPU。
SCHED_RR：时间片轮转的实时进程。所有具有相同优先级的SCHED_RR实时进程公平分配CPU时间。
SCHED_NORMAL：普通的分时进程。
5. 普通进程调度
普通进程通过静态优先级nice值决定进程的基本时间片，nice值越小，静态优先级越高，进程获得的CPU时间更长。同时以nice值为基础并通过检查进程过去的情况设置优先级，既动态优先级。调度程序总是选择动态优先级高的进程投入运行。
Linux基于以动态优先级为基础的调度算法。内核为每个进程设置一个基本的优先级，但它允许调度程序根据需要来加减优先级，然后挑选优先级最高的进程投入运行。当进程时间片用完重新分配时间时，也会根据优先级值动态分配时间。
6. 实时进程调度
实时算法实现都是静态优先级，而不会设置动态优先级。这能保证优先级高的实时进程总能抢占优先级低的进程。
7. 更新时间片scheduler_tick()
void scheduler_tick(void)
{
struct task_struct *p = current;

if (p->array != rq->active) { //如果current->array没有指向runqueue，说
set_tsk_need_resched(p); 明进程已经过期但未被替换，则设置
goto out; need_resched字段以进行重新调度
}

/* current为SCHED_FIFO，进程不会被低优先级进程抢占，因此不更新时间片。
current为SCHED_RR，时间片将递减。若时间片用完，则重新计算时间片，设置need_resched字段，将进程加入runqueue尾部。
*/
if (rt_task(p)) {
if ((p->policy == SCHED_RR) && !--p->time_slice) {
p->time_slice = task_timeslice(p); //根据静态优先级计算时间片
set_tsk_need_resched(p);
requeue_task(p, rq->active);
}
goto out_unlock;
}
/* 更新普通进程时间片。若时间片用完，设置need_resched字段，根据动态优先级设置进程优先级，根据静态优先级设置时间片。若时间片未用完，则检查进程是否可继续占用CPU。
*/
if (!--p->time_slice) {
set_tsk_need_resched(p);
p->prio = effective_prio(p);
p->time_slice = task_timeslice(p);
} else {
......
}
}
8. 调度程序schedule()
调用schedule()函数分为直接调用和延迟调用。如果current进程因不能获得必要的资源要立即被阻塞，就直接调用schedule()；也可通过设置current的need_resched字段被设置，以延迟方式调用schedule()。由于总是在恢复用户态进程的执行前检查这个标志，所有schedule()将在不久之后的某个时间被调用。
asmlinkage void __sched schedule(void)
{
struct task_struct *prev, *next;
struct list_head *queue;
struct prio_array *array;
int idx;
struct rq *rq;
……
……
prev = current;
array = rq->active; //获取活动优先级队列
idx = sched_find_first_bit(array->bitmap); //通过优先级位图快速查找进程
queue = array->queue + idx;
next = list_entry(queue->next, struct task_struct, run_list); //返回进程描述符
if(prev != next)
context_switch(); //如果选中的进程不是当前进程则进行上下文切换
}
9. 用户抢占
内核即将返回用户空间时，如果need_resched标志被设置，会导致schedule()被调用，发生用户抢占。
10. 内核抢占
thread_info引入了preempt_count计数器。该计数器初始值为0，每当使用锁的 时候数值加1，释放锁的时候数值减1。当数值为0的时候，内核就可执行抢占。从中断返回内核空间的时候，内核会检查need_resched和preempt_count的值。如果need_resched被设置，并且preempt_count为0的话，这说明有一个更为重要的任务需要执行并且可以安全地抢占，此时调度程序就会调度(抢占当前进程)。如果preempt_count不为0，说明当前 任务持有锁，所以抢占是不安全的。这时，就会像通常那样直接从中断返回当前执行进程。 如果当前进程所持有的所有的锁都被释放了。那么preempt_count就会重新为0。此时，释放锁的代码会检查need_resched是否被设置。如果是的话，就会调用调度程序。

container_of()

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

#include <stdio.h> /* #define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );}) #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) */ struct test { int a; char *b; }; int main(int argc, char *argv[]) { //通过struct test成员b返回struct的入口地址 //container_of(&tmp.b, (struct test), b);    struct test tmp; struct test *ptmp; int offset; tmp.a = 10; printf("&tmp.a = %02x, &tmp.b = %02x\n", &tmp.a, &tmp.b); //定义一个 _mptr指针， 类型为struct test结构体中b成员的类型 //typeof 为获取（（（struct test＊）0）->b)的类型，此处此类型为char* const typeof(((struct test *)0)->b) *_mptr = &tmp.b; printf("_mptr = %02x\n", _mptr); //#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) //TYPE是某struct的类型 0是一个假想TYPE类型struct,MEMBER是该struct中的一个成员.  //由于该struct的基地址为0, MEMBER的地址就是该成员相对与struct头地址的偏移量. offset = (int)(&((struct test *)0)->b); printf("offset = %d\n", offset); //_mptr的地址减去MEMBER在该struct中的偏移量得到的地址, 再转换成type型指针. 该指针就是struct的入口地址了. ptmp = (struct test *)((char *)_mptr - offset); printf("tmp = %02x, ptmp = %02x\n", &tmp, ptmp); printf("ptmp->a = %d\n", ptmp->a); return 0; } 输出结果： $ ./a.out &tmp.a = bfffe6a0, &tmp.b = bfffe6a4 _mptr = bfffe6a4 offset = 4 tmp = bfffe6a0, ptmp = bfffe6a0 ptmp->a = 10

iptables command and rules

$ iptables [-t table] command [match] [target]



iptables有5个链：PREROUTING，INPUT，FORWARD，OUTPUT，POSTROUTING；4个表：filter,nat,magle,raw.

4个表的优先级由高到低为：raw->mangle->nat->filter.

[-t table] 选项允许使用标准表之外的任何表。表是包含仅处理特定类型信息包的规则和链的信息包过滤表。该选项不是必需的，如果未指定， 则 filter 用作缺省表。
filter：表用于一般的信息包过滤。包括链表：
          INPUT：主要与想要进入本机的封包有关；
          OUTPUT：主要与本机所要送出的封包有关；
          FORWARD： 用于转发，与nat table 相关性较高。
nat：主要在进行来源与目的之 IP 或 port 的转换，与 Linux 本机较无关，主要与 Linux 主机后的区域网路内电脑较有相关。包括链表：
          PREROUTING：在进行路由判断之前所要进行的规则(DNAT/REDIRECT)
          POSTROUTING：在进行路由判断之后所要进行的规则(SNAT/MASQUERADE)
          OUTPUT：与发送出去的封包有关。
mangle：该表包含一些规则来标记用于高级路由的信息包，该表包含 PREROUTING 和 OUTPUT 链。 

RAW表只使用在PREROUTING链和OUTPUT链上,因为优先级最高，从而可以对收到的数据包在连接跟踪前进行处理。一但用户使用了RAW 表,在某个链上,RAW表处理完后,将跳过NAT表和 ip_conntrack处理,即不再做地址转换和数据包的链接跟踪处理了.RAW表可以应用在那些不需要做nat的情况下，以提高性能。如大量访问的web服务器，可以让80端口不再让iptables做数据包的链接跟踪处理，以提高用户的访问速度。


各链表关系如下：