信号处理的时机

June 4th, 2015 by JasonLe's Tech 721 views

Update 2015-6-6

我们知道1-32是最早就拥有的信号,之后又加入了33~64信号。编号为33-64的信号又称为实时信号。需要注意的是:这里的“实时”和实时操作系统中的“实时”没有任何联系,实时信号在处理速度上并不会比普通信号快,它们之间的区别就是:普通信号会对多次的同一个信号进行“合并”处理而实时信号会一一处理。这就要求我们在编写信号监听函数时,要捕获普通信号,必须时刻轮训监听,因为系统默认会丢弃同种类型的普通信号!

在用户态下,我们向一个进程发送信号,但是这个信号如何被处理呢?其实信号处理的时机就是从异常或中断恢复发生时处理,这里我们可以把中断理解为1)中断 2)system call 两个时机,这两个时机都会有从内核态->用户态切换的过程。

根据ULK中kernel返回用户态的流程图:

39693914

我们发现当kernel 从中断异常返回时,会检查USER_RPL决定返回 kernel 还是 userspace,当跳入到resume_userspace,也就意味着在返回用户空间时,检查_TIF_WORK_MASK 是否有信号,如果没有则返回restore_all,否则进入work_pending,其实这里就可以看到信号处理是一个异步的!

ret_from_exception:
    preempt_stop(CLBR_ANY)
ret_from_intr:
    GET_THREAD_INFO(%ebp)
#ifdef CONFIG_VM86
...
#else
    /*
     * We can be coming here from child spawned by kernel_thread().
     */
    movl PT_CS(%esp), %eax
    andl $SEGMENT_RPL_MASK, %eax
#endif
    cmpl $USER_RPL, %eax
    jb resume_kernel        # not returning to v8086 or userspace

ENTRY(resume_userspace)
    LOCKDEP_SYS_EXIT
    DISABLE_INTERRUPTS(CLBR_ANY)    # make sure we don't miss an interrupt
                    # setting need_resched or sigpending
                    # between sampling and the iret
    TRACE_IRQS_OFF
    movl TI_flags(%ebp), %ecx
    andl $_TIF_WORK_MASK, %ecx  # is there any work to be done on
                    # int/exception return?
    jne work_pending
    jmp restore_all
END(ret_from_exception)

如果返回是kernel的话,按照汇编代码与图示,要先禁中断,然后判断__preempt_count变量值,当出现中断嵌套这个值会+1,如果为0也就意味着当前系统没有出现中断的嵌套执行restore_all,否则然后查看X86_EFLAGS_IF是否是禁止屏蔽中断,如果屏蔽中断然后执行restore_all,否则调用preempt_schedule_irq,然后处理信号。直到__preempt_count==0,跳出这个循环。(Linux中的信号机制优先级是:高优先级中断->低优先级中断->软中断->信号->进程运行。

#ifdef CONFIG_PREEMPT
ENTRY(resume_kernel)
    DISABLE_INTERRUPTS(CLBR_ANY)
need_resched:
    cmpl $0,PER_CPU_VAR(__preempt_count)
    jnz restore_all
    testl $X86_EFLAGS_IF,PT_EFLAGS(%esp)    # interrupts off (exception path) ?
    jz restore_all
    call preempt_schedule_irq
    jmp need_resched
END(resume_kernel)
#endif
    CFI_ENDPROC
...

这里我们进入到work_pending函数段,系统会进行调度,work_resched是个循环,一直在调度schedule,直到跳出循环。在这个汇编的末尾,kernel会判断$USER_RPL 值决定是返回kernel space还是user space,如果返回user space才会调用do_notify_resume()函数,这个函数是处理信号,调用do_signal()的基础,这个也从侧面反映了内核空间没有信号处理机制

work_pending:
    testb $_TIF_NEED_RESCHED, %cl
    jz work_notifysig
work_resched:
...
work_notifysig:             # deal with pending signals and
                    # notify-resume requests
#ifdef CONFIG_VM86
...
#else
    movl %esp, %eax
#endif
    TRACE_IRQS_ON
    ENABLE_INTERRUPTS(CLBR_NONE)
    movb PT_CS(%esp), %bl
    andb $SEGMENT_RPL_MASK, %bl
    cmpb $USER_RPL, %bl
    jb resume_kernel
    xorl %edx, %edx
    call do_notify_resume
    jmp resume_userspace

我们进入到do_notify_resume()函数,这个函数会调用do_signal,它就是处理系统调用或者中断发生信号的核心函数,这个函数又依次处理信号(通过调用handle_signal())和建立用户态堆栈(通过调用setup_frame()或setup_rt_frame())。当进程又切换到用户态时,因为信号处理程序的起始地址被强制放进程序计数器中,因此开始执行信号处理程序。

__visible void
do_notify_resume(struct pt_regs *regs, void *unused, __u32 thread_info_flags)
{
...
    /* deal with pending signal delivery */
    if (thread_info_flags & _TIF_SIGPENDING)
        do_signal(regs);
...
}

当处理程序终止时,setup_frame()或setup_rt_frame()函数(这里的rt代表实时系统中的rt结构。)放在用户态堆栈中的返回代码就被执行。这个代码调用sigreturn()或rt_sigrenturn()系统调用,相应的服务例程把正常程序的用户态堆栈硬件上下文拷贝到内核堆栈,并把用户态堆栈恢复到它原来的状态(通过调用restore_sigcongtext()).当这个系统调用结束时,普通进程就因此能恢复自己的执行。

8294024f-f541-3b5f-b47e-3a476c65f50a

 

所以综上所述:

如果我们自定义一个信号处理函数,那么这个处理函数定义在用户空间,1. 在进入内核态时,内核态堆栈中保存了一个中断现场,也就是一个pt_regs结构,中断返回地址就保存在pt_regts中的pc中,因此我们这里只要把当前进程的pt_regs中pc设置为sa_handler,然后返回到用户态就开始从sa_handler处开始执行了。

2.当信号的用户态处理函数执行结束时,需要再次进入内核态,内核专门提供了一个系统调用sys_sigreturn()(还有一个sys_rt_sigreturn())

3.在构建临时堆栈环境时,内核会把最初的pt_regs上下文备份到临时堆栈中(位于用户态堆栈),当通过系统调用sys_sigreturn()再次进入内核时,内核从用户态空间还原出原始的pt_regs。最后正常返回。

stack2

这里我们要考虑一种情况,进程处于TASK_INTERRUPTIBLE状态,某个进程向他发送一个信号,这时kernel将这个进程立即设置为TASK_RUNNING状态,但是系统宾没有完成当前的服务例程,并返回EINTR错误码,我们可以测试这个错误码,并重行发送新的system call,还有一些错误码用来判断kernel是否重行执行system call。

 

参考:

ULK  P445~P446

http://wangyuxxx.iteye.com/blog/1703252

http://blog.csdn.net/ce123_zhouwei/article/details/8570616

Combination Sum 思路

June 1st, 2015 by JasonLe's Tech 641 views

最新刷leetcode的题目,发现了Combination Sum题目,这个题目分为I、II、III。难度层层递进,题目就是遍历vector容器,选择出符合target number的sum组合,这个题目的思路可以参考DFS通用解法。我们使用那个DFS模板,首先要构造dfs函数。

一般情况下,我们需要五个参数:结果,原始数据集,中间结果,当前指向的数据,满足target number的值:

void dfs(vector<vector<int>> &result,vector<int>& candidates,vector<int> path,int current,int target)

然后我们根据candidates中的数据集,深搜这个数据集的各种可能性,将达成target的path中间结果加入result,按照通用模版

void dfs(type &input, type &path, type &result, int cur or gap) {
              if (数据非法) return 0; // 终止条件
              if (cur == input.size()) { // 收敛条件
                  // if (gap == 0) {
                        将path 放入result
              }
              if (可以剪枝) return;
              for(...) { // 执行所有可能的扩展动作
                     执行动作,修改path
                     dfs(input, step + 1 or gap--, result);
                     恢复path
              }
}

第一步:收敛也就是target==0
第二步:使用for(),并在循环中剪枝 if(target-candidates[current]<0) return;
第三步:如果通过第二部,也就意味着这个current合格,可以将这个加入到path中,然后继续深度遍历。dfs(result,candidates,path,current,target-candidates[current]);这里的问题是candidates的数据是可重复的,可以多次使用。如果只使用一次的话,也就意味着我们需要sort(),然后需要将上个满足条件的值跳过,也就是II中的nums[i]==nums[i-1]比较Combination Sum II

void dfs(vector<vector<int>> &result,vector<int>& candidates,vector<int> path,int current,int target){
		if(!path.empty()&&target==0){
			result.push_back(path);
			return;
		}
		if(current<candidates.size()){
			int tmp = -1;//start from 0 and 1
			for(;current<candidates.size();current++){
				if(candidates[current]==tmp)
					continue;
				if(target-candidates[current]<0)
					return;

				tmp = candidates[current];
				path.push_back(candidates[current]);
				dfs(result,candidates,path,current+1,target-candidates[current]);
				path.pop_back();
			}
		}
	}

 

 

题目:

 

https://leetcode.com/problems/combination-sum/

https://leetcode.com/problems/combination-sum-ii/

https://leetcode.com/problems/combination-sum-iii/

内核页表和进程页表

May 28th, 2015 by JasonLe's Tech 904 views

最近在看vmalloc()分配代码,我们知道当通过alloc_page()分配出来page后,需要将这些分散的物理页框page映射到vmalloc区,这里我们就要修改内核页表,以前我学页表是把内核空间与用户空间割裂学习的,导致二者无法很好地衔接,这里我会把两个概念重新解释清楚。

下面代码映射到vmalloc区的关键就是map_vm_area()函数,

for (i = 0; i < area->nr_pages; i++) {
        struct page *page;

        if (node == NUMA_NO_NODE)
            page = alloc_page(alloc_mask);
        else
            page = alloc_pages_node(node, alloc_mask, order);
...
    }

    if (map_vm_area(area, prot, pages))
        goto fail;
    return area->addr;

拿IA32架构的虚拟地址来说,0~3GB属于用户空间,用户空间是由每个进程的task_struct.mm_struct.pgd的成员变量,这个指向的就是进程页表。而3G~4GB属于内核空间,这个页表是由内核页目录表管理,存放在主内核页全局目录init_mm.pgd(swapper_pg_dir)中

struct mm_struct init_mm = {
         .mm_rb          = RB_ROOT,
         .pgd            = swapper_pg_dir,
         .mm_users       = ATOMIC_INIT(2),
         .mm_count       = ATOMIC_INIT(1),
         .mmap_sem       = __RWSEM_INITIALIZER(init_mm.mmap_sem),
         .page_table_lock =  __SPIN_LOCK_UNLOCKED(init_mm.page_table_lock),
         .mmlist         = LIST_HEAD_INIT(init_mm.mmlist),
         INIT_MM_CONTEXT(init_mm)
};

进程切换切换的是进程页表:即将新进程的pgd(页目录)加载到CR3寄存器中。而内核页表是所有进程共享的,每个进程的“进程页表”中内核态地址相关的页表项都是“内核页表”的一个拷贝。

vmalloc区发生page fault

在vmalloc区发生page fault时,将“内核页表”同步到“进程页表”中。这部分区域对应的线性地址在内核使用vmalloc分配内存时,其实就已经分配了相应的物理内存,并做了相应的映射,建立了相应的页表项,但相关页表项仅写入了“内核页表”,并没有实时更新到“进程页表中”,内核在这里使用了“延迟更新”的策略,将“进程页表”真正更新推迟到第一次访问相关线性地址,发生page fault时,此时在page fault的处理流程中进行“进程页表”的更新。

所以linux中,只有进程的页表是时刻在更换的,而内核页表全局只有一份,所有进程共享内核页表!

物理内存管理:vmalloc()的设计实现

May 26th, 2015 by JasonLe's Tech 749 views

对于内核空间,根据不同的映射规则,可以将整个内核空间划分为四大部分:物理内存映射区、vmalloc区、永久内核映射区和固定映射的线性地址区域。这里我们只来谈谈vmalloc()的分配。首先我们来看一下之前的一个图:

phy_addr

vmalloc()区域是从VMALLOC_START开始,一直到VMALLOC_END结束,中间有PAGE_SIZE大小的guard_page作为保护,以防止防止非法的内存访问,内核中使用vm_struct结构来表示每个vmalloc区,也就是说,每次调用vmalloc()函数在内核中申请一段连续的内存后,都对应着一个vm_struct,kernel 中所有的vmalloc区组成一个链表,链表头指针为vmlist

static struct vm_struct *vmlist __initdata;

struct vm_struct {
    struct vm_struct    *next;
    void            *addr;
    unsigned long       size;
    unsigned long       flags;
    struct page     **pages;
    unsigned int        nr_pages;                                                                                                
    phys_addr_t     phys_addr;
    const void      *caller;
};

这里我们只介绍几个重要的字段:
next:所有的vm_struct结构组成一个vmlist链表,该字段指向下一个节点;
addr:代表这段子区域的起始地址;
size:表示区域的大小;
flags:表示该非连续内存区的类型,VM_ALLOC表示由vmalloc()映射的内存区,VM_MAP表示通过vmap()映射的内存区,VM_IOREMAP表示通过ioremap()将硬件设备的内存映射到内核的一段内存区;
pages:指针数组,该数组的成员是struct page*类型的指针,每个成员都关联一个映射到该虚拟内存区的物理页框;
nr_pages:pages数组中page结构的总数;
phys_addr:通常为0,当使用ioremap()映射一个硬件设备的物理内存时才填充此字段;
caller:表示一个返回地址;

 

vmalloc()的实现

vmalloc()内部封装了很多层函数,调用层次就是:vmalloc()-> __vmalloc_node_flags() -> __vmalloc_node() -> __vmalloc_node_range() ,通过这几层调用,就会向最终的__vmalloc_node_range()传入很多参数,GFP_KERNEL|__GFP_HIGHMEM表明内存管理子系统将从高端内存区(ZONE_HIGHMEM)中分配内存空间;NUMA_NO_NODE表示当前不是NUMA架构。

void *vmalloc(unsigned long size)
{
    return __vmalloc_node_flags(size, NUMA_NO_NODE,
                    GFP_KERNEL | __GFP_HIGHMEM);
}
static inline void *__vmalloc_node_flags(unsigned long size,                             
                    int node, gfp_t flags)
{
    return __vmalloc_node(size, 1, flags, PAGE_KERNEL,
                    node, __builtin_return_address(0));
}
static void *__vmalloc_node(unsigned long size, unsigned long align,                    
                gfp_t gfp_mask, pgprot_t prot,
                int node, const void *caller)
{
    return __vmalloc_node_range(size, align, VMALLOC_START, VMALLOC_END,
                gfp_mask, prot, node, caller);
}

这里我们进入真正分配vmalloc区域的函数__vmalloc_node_range(),我们只要关注第三个第四个参数,就是vm区域的开始地址与结束地址,__vmalloc_node_range()一开始会先修正一下size对齐,PAGE_ALIGN将size的大小修改成页大小的倍数。进行size合法性的检查,如果size为0,或者size所占页框数大于系统当前空闲的页框数(totalram_pages),将返回NULL,申请失败。

如果分配的内存区大小合法,__get_vm_area_node()中的alloc_vmap_area()将在整个非连续内存区中查找一个size大小的子内存区。该函数先遍历整个vmlist链表,依次比对每个vmalloc区,直到找到满足要求的子内存区结束。在这里面还做好了内核页表的映射等操作。

建立好了vm_struct 结构,下面就要分配使用__vmalloc_area_node()为这个vmalloc内存区分配真正的物理页。

void *__vmalloc_node_range(unsigned long size, unsigned long align,
            unsigned long start, unsigned long end, gfp_t gfp_mask,
            pgprot_t prot, int node, const void *caller)
{
    struct vm_struct *area;
    void *addr;
    unsigned long real_size = size;
                                                                                                                                 
    size = PAGE_ALIGN(size);
    if (!size || (size >> PAGE_SHIFT) > totalram_pages)
        goto fail;
    
    area = __get_vm_area_node(size, align, VM_ALLOC | VM_UNINITIALIZED,
                  start, end, node, gfp_mask, caller);
    if (!area)
        goto fail;
    
    addr = __vmalloc_area_node(area, gfp_mask, prot, node);
    if (!addr) 
        return NULL;
...    
    return addr;
....

__vmalloc_area_node()的实现

首先根据传入的vm_struct *area 获取要分配的物理页大小,这里的大小包括了guard_page,所以要在get_vm_area_size()减去这个PAGE_SIZE,翻译过来就是nr_pages = (area->size – PAGE_SIZE) >> PAGE_SHIFT;抹去低位,也就是要分配的page数,然后nr_pages * sizeof(struct page *)也就是真正的物理page大小。

根据这个array_size大小,我们可以判断要分配的是大于PAGE_SIZE还是小于PAGE_SIZE,大于的话就递归分配pages数组,小于的话,通过kmalloc_node()为pages数组分配一段连续的空间,这段空间位于内核空间的物理内存线性映射区。然后将分配好的page加入area,更新area中的pages。

static void *__vmalloc_area_node(struct vm_struct *area, gfp_t gfp_mask,
                 pgprot_t prot, int node)
{
    const int order = 0;
    struct page **pages;
    unsigned int nr_pages, array_size, i;
    const gfp_t nested_gfp = (gfp_mask & GFP_RECLAIM_MASK) | __GFP_ZERO;
    const gfp_t alloc_mask = gfp_mask | __GFP_NOWARN;                                                                            

    nr_pages = get_vm_area_size(area) >> PAGE_SHIFT;
    array_size = (nr_pages * sizeof(struct page *));

    area->nr_pages = nr_pages;
    /* Please note that the recursion is strictly bounded. */
    if (array_size > PAGE_SIZE) {
        pages = __vmalloc_node(array_size, 1, nested_gfp|__GFP_HIGHMEM,
                PAGE_KERNEL, node, area->caller);
        area->flags |= VM_VPAGES;
    } else {
        pages = kmalloc_node(array_size, nested_gfp, node);
    }
    area->pages = pages;

接下来通过一个循环为pages数组中的每个页面描述符分配真正的物理页框。page结构并不是代表一个具体的物理页框,只是用来描述物理页框的数据结构而已。如果node未指定物理内存所在节点,那么alloc_page()分配一个页框,并将该页框对应的页描述符指针赋值给page临时变量;否则通过alloc_pages_node()在指定的节点上分配物理页框。接着将刚刚分配的物理页框对应的页描述符赋值给pages数组的第i个元素。这里一旦某个物理页框分配失败则直接返回NULL,表示本次vmalloc()操作失败。

for (i = 0; i < area->nr_pages; i++) {
        struct page *page;

        if (node == NUMA_NO_NODE)
            page = alloc_page(alloc_mask);
        else
            page = alloc_pages_node(node, alloc_mask, order);

        if (unlikely(!page)) {
            /* Successfully allocated i pages, free them in __vunmap() */
            area->nr_pages = i;
            goto fail;
        }
        area->pages[i] = page;
        if (gfp_mask & __GFP_WAIT)
            cond_resched();
    }

    if (map_vm_area(area, prot, pages))
        goto fail;
    return area->addr;

fail:
    warn_alloc_failed(gfp_mask, order,
              "vmalloc: allocation failure, allocated %ld of %ld bytes\n",
              (area->nr_pages*PAGE_SIZE), area->size);
    vfree(area->addr);
    return NULL;
}

这里当kernel分配完page,并将信息输入到area中后,这些分散的页框并没有映射到area所代表的那个连续vmalloc区中。使用map_vm_area()将完成映射,它依次修改内核页表,将pages数组中的每个页框分别映射到连续的vmalloc区中。

 

map_vm_area()工作原理会在下一篇文章中说明!

[1] http://lxr.free-electrons.com/source/mm/vmalloc.c#L1557

Docker 使用

May 19th, 2015 by JasonLe's Tech 708 views

Update 2015-6-3

最近项目需要使用到docker进行live migration。之前接触过lxc,所以这时两款原理上相同的容器虚拟化产品。我是在fedora 20下使用这个产品,在fedora20的官方仓库中有一个重名的软件包docker,我们需要使用docker-io安装。

安装完成以后就可以通过systemctl 启动docker daemon

$ sudo systemctl start docker

如果想开机启动那么使用enable命令,当我们安装好docker以后,可以使用docker ps查看,在目前我使用的1.5版本docker。首先我先pull一个镜像:

[root@localhost contrib]# docker pull ubuntu:latest
[root@localhost contrib]# docker images
REPOSITORY          TAG                 IMAGE ID            CREATED             VIRTUAL SIZE
ubuntu              14.04.2             07f8e8c5e660        2 weeks ago         188.3 MB
ubuntu              latest              07f8e8c5e660        2 weeks ago         188.3 MB
ubuntu              trusty              07f8e8c5e660        2 weeks ago         188.3 MB
ubuntu              trusty-20150427     07f8e8c5e660        2 weeks ago         188.3 MB
ubuntu              14.04               07f8e8c5e660        2 weeks ago         188.3 MB
busybox             buildroot-2014.02   8c2e06607696        4 weeks ago         2.43 MB
busybox             latest              8c2e06607696        4 weeks ago         2.43 MB

pull完成以后,就可以通过docker images查看本机拥有的镜像,这时候我们使用docker run -d -t -i ubuntu /bin/sh可以启动镜像。

we’ve also passed in two flags: -t and -i. The -t flag assigns a pseudo-tty or terminal inside our new container and the -i flag allows us to make an interactive connection by grabbing the standard in (STDIN) of the container.

这时我们可以使用docker ps来查看本机启动的容器。

[root@localhost contrib]# docker ps
CONTAINER ID        IMAGE               COMMAND             CREATED             STATUS              PORTS               NAMES
f05df7249fea        ubuntu:14.04        "/bin/bash"         9 seconds ago       Up 6 seconds                            silly_hypatia

 

docker不同于lxc,主要使用一个64bit的id唯一标示一个容器,也是通过这个CONTAINER ID来标示,至于容器的停止,使用docker stop [CONTAINER ID] 或者是docker stop [NAMES]。删除一个镜像是docker rmi REPOSITORY:TAG即可,我们也可以使用别名机制来代替具体的CONTAINER ID。

[root@localhost contrib]# docker run -d -i -t --name busybox busybox:latest
3772693b1a82f996b296addf2f2ec00636535c81aa61730f66717d1311ae1b20
[root@localhost contrib]# docker stop busybox
busybox
[root@localhost contrib]# docker run -d -i -t --name busybox busybox:latest
FATA[0000] Error response from daemon: Conflict. The name "busybox" is already in use by container 3772693b1a82. You have to delete (or rename) that container to be able to reuse that name.
[root@localhost contrib]# docker run -d -i -t busybox:latest
5c331e6cddb00e134f39831ce1a6c5a9763c5ba60e1a41232503fce49fa17b09
[root@localhost contrib]# docker ps
CONTAINER ID        IMAGE                       COMMAND             CREATED             STATUS              PORTS               NAMES
5c331e6cddb0        busybox:buildroot-2014.02   "/bin/sh"           8 seconds ago       Up 6 seconds                            elated_meitner
f05df7249fea        ubuntu:14.04                "/bin/bash"         3 hours ago         Up 3 hours                              silly_hypatia

我们知道对于容器的动态迁移,利用pid进行C/R操作是十分有必要的,要想知道容器的pid,那么我们使用docker inspect busybox 查询当前容器的信息。我们看到这个容器的pid是768。

# docker inspect busybox
.....
"Path": "/bin/sh",
    "ProcessLabel": "",
    "ResolvConfPath": "/var/lib/docker/containers/f89a11d1cfe0037993dc4862ee218d59ccdcc4c7377fa4ed8946ed744226d8f6/resolv.conf",
    "RestartCount": 0,
    "State": {
        "Error": "",
        "ExitCode": 0,
        "FinishedAt": "0001-01-01T00:00:00Z",
        "OOMKilled": false,
        "Paused": false,
        "Pid": 768,
        "Restarting": false,
        "Running": true,
        "StartedAt": "2015-06-02T22:48:09.975364683Z"
    },
    "Volumes": {},
    "VolumesRW": {}
....

 

 

参考:

http://criu.org/Docker

http://docs.docker.com/userguide/dockerizing/