从用户态到内核态的切换

June 14th, 2015 by JasonLe's Tech 2,334 views

我们都知道用户态向内核态切换有三种方式:1:系统调用 2:中断  3:异常 。之前只是知道这个切换的原理,但是并没有仔细的从代码上面学习切换的过程。之前我学习了页表,但是内核页表与进程页表是割裂的,信号处理也是割裂的。这里我会结合用户态到内核态从代码进行分析。

这部分切换的函数是用汇编代码写的。详细路径存在于arch/x86/kernel/entry_32.S文件中。

内核栈

内核栈:在Linux中每个进程有两个栈,分别用于用户态和内核态的进程执行(类似于内核页表与用户页表),其中的内核栈就是用于内核态的栈,它和进程的thread_info结构一起放在两个连续的页框大小的空间内。

在kernel 源代码中使用C语言定义了一个联合结构thread_union 方便地表示一个进程的thread_info和内核栈(定义在定义在include/linux/sched.h)

union thread_union {
     struct thread_info thread_info;
     unsigned long stack[THREAD_SIZE/sizeof(long)];
};

结合一个图可以看的更加清楚,其中栈是从高地址向低地址生长的,其中esp寄存器是CPU栈指针,存放内核栈栈顶地址。从用户态刚切换到内核态时,进程的内核栈总是空的(非常类似于进程页表切换到内核态页表,惰性传值),此时esp指向这个栈的顶端。

在x86中调用int指令系统调用后会把用户栈的%esp的值及相关寄存器压入内核栈中,系统调用通过iret指令返回,在返回之前会从内核栈弹出用户栈的%esp和寄存器的状态,然后进行恢复。所以在进入内核态之前要保存进程的上下文,中断结束后恢复进程上下文,那靠的就是内核栈
Screenshot1
thread_info结构的定义如下

25 struct thread_info {
 26         struct task_struct      *task;          /* main task structure */
 27         struct exec_domain      *exec_domain;   /* execution domain */
 28         __u32                   flags;          /* low level flags */
 29         __u32                   status;         /* thread synchronous flags */
 30         __u32                   cpu;            /* current CPU */
 31         int                     saved_preempt_count;
 32         mm_segment_t            addr_limit;
 33         struct restart_block    restart_block;
 34         void __user             *sysenter_return;
 35 #ifdef CONFIG_X86_32
 36         unsigned long           previous_esp;   /* ESP of the previous stack in
 37                                                    case of nested (IRQ) stacks
 38                                                 */
 39         __u8                    supervisor_stack[0];
 40 #endif
 41         unsigned int            sig_on_uaccess_error:1;
 42         unsigned int            uaccess_err:1;  /* uaccess failed */
 43 };

内核栈保存用户态的esp,eip等寄存器的值,首先得知道内核栈的栈指针,那在进入内核态之前,通过TSS才能获得内核栈的栈指针。

TSS

TSS反映了CPU上的当前进程的特权级。linux为每一个cpu提供一个tss段,并且在tr寄存器中保存该段。在从用户态切换到内核态时,可以通过获取TSS段中的esp0来获取当前进程的内核栈 栈顶指针,从而可以保存用户态的cs,esp,eip等上下文。

注:linux中之所以为每一个cpu提供一个tss段,而不是为每个进程提供一个tss段,主要原因是tr寄存器永远指向它,在任务切换的适合不必切换tr寄存器,而且进程切换的时候只会切换新的esp0。结合scheduler()中的switch_to宏,next_p->thread.esp0装入对应于本地CPU的TSS的esp0字段(其实,任何由sysenter汇编指令产生的从用户态到内核态的特权级转换将把这个地址拷贝到esp寄存器中)。

内核代码中TSS结构的定义位于arch/x86/include/asm/processor.h文件。

其中主要的内容是:

  • 硬件状态结构:          x86_hw_tss(arch/x86/include/asm/processor.h)
  • IO权位图:     io_bitmap
  • 备用内核栈:        stack

linux的tss段中只使用esp0和iomap等字段,并不用它的其他字段来保存寄存器,在一个用户进程被中断进入内核态的时候,从tss中的硬件状态结构中取出esp0(即内核栈栈顶指针),然后切到esp0,其它的寄存器则保存在esp0指的内核栈上而不保存在tss中。

下面,我们看看INIT_TSS定义,其中init_stack是宏定义,指向内核栈 #define init_stack (init_thread_union.stack)

824 #define INIT_TSS  {                                                       \
825         .x86_tss = {                                                      \
826                 .sp0            = sizeof(init_stack) + (long)&init_stack, \
827                 .ss0            = __KERNEL_DS,                            \
828                 .ss1            = __KERNEL_CS,                            \
829                 .io_bitmap_base = INVALID_IO_BITMAP_OFFSET,               \
830          },                                                               \
831         .io_bitmap              = { [0 ... IO_BITMAP_LONGS] = ~0 },       \
832 }

内核栈栈顶指针、内核代码段、内核数据段赋值给TSS中的相应项。从而进程从用户态切换到内核态时,可以从TSS段中获取内核栈栈顶指针,进而保存进程上下文到内核栈中。

 

综上所述:

  • 读取tr寄存器,访问TSS段
  • 从TSS段中的esp0获取进程内核栈的栈顶指针
  • 由控制单元在内核栈中保存当前eflags,cs,ss,eip,esp寄存器的值。
  • 由SAVE_ALL保存其寄存器的值到内核栈
  • 把内核代码选择符写入CS寄存器,内核栈指针写入ESP寄存器,把内核入口点的线性地址写入EIP寄存器

此时,CPU已经切换到内核态,根据EIP中的值开始执行内核入口点的第一条指令。

 

参考:

http://guojing.me/linux-kernel-architecture/posts/process-switch/

内核线程与用户进程在信号处理上的区别

June 8th, 2015 by JasonLe's Tech 1,783 views

Update 2015-6-11

上一篇博客里面,我分析了信号在内核中处理的时机,发现对于内核线程没有类似于用户态程序信号处理的机制。后来我发邮件问了kthread的维护者Tetsuo Handa,他明确的给出了我内核线程没有类似于用户进程发送SIGSTOP将进程停止的机制。这个也就意味着我们要想让内核线程接收信号,并进行处理,必须在创建kernel thread代码中显式的允许某个信号。

进程对信号的响应

  1. 忽略信号:大部分信号可被忽略,除SIGSTOP和SIGKILL信号外(这是超级用户杀掉或停掉任意进程的手段)。
  2. 捕获信号:注册信号处理函数,它对产生的特定信号做处理。
  3. 让信号默认动作起作用:unix内核定义的默认动作,有5种情况:
    • a) 流产abort:终止进程并产生core文件。
    • b) 终止stop:终止进程但不生成core文件。
    • c) 忽略:忽略信号。
    • d) 挂起suspend:挂起进程。
    • e) 继续continue:若进程是挂起的,则resume进程,否则忽略此信号。

通常意义上来说内核线程对于信号是不处理的,如果想显式的让kernel thread支持信号,必须在内核线程中开启signal。编程框架类似于

static int thread_process(void *arg)
{
....
    allow_signal(SIGURG);
    allow_signal(SIGTERM);
    allow_signal(SIGKILL);
    allow_signal(SIGSTOP);
    allow_signal(SIGCONT);  
...
    for ( ; !remove_mod; ) {
        /* Avoid infinite loop */
        msleep(1000);
        if (signal_pending(current)) {
                siginfo_t info;
                unsigned long signr;
                signr = dequeue_signal_lock(current, &current->blocked, &info);
                switch(signr) {
                        case SIGSTOP:
                                printk(KERN_DEBUG "thread_process(): SIGSTOP received.\n");
                                set_current_state(TASK_STOPPED);
                                schedule();
                                break;
                        case SIGCONT:
                                printk(KERN_DEBUG "thread_process(): SIGCONT received.\n");
                                set_current_state (TASK_INTERRUPTIBLE);
                                schedule();
                                break;

                        case SIGKILL:
                                printk(KERN_DEBUG "thread_process(): SIGKILL received.\n");
                                break;
                        //      goto die;

                        case SIGHUP:
                                printk(KERN_DEBUG "thread_process(): SIGHUP received.\n");
                                break;
                        default:
                                printk(KERN_DEBUG "thread_process(): signal %ld received\n", signr);
                        }
        }
        schedule_timeout_interruptible(msecs_to_jiffies(1));
    }
    return 0;
}

在用户态下,我们只需要编写信号处理函数,然后使用signal(sig,handler)方式将信号处理函数与特定信号连接。向内核线程发信号与用户态进程发送信号都是发送某个特定特定pid号,比如19号信号是SIGSTOP,那么我们使用kill -19 pid即可。具体pid解释

创建内核线程,拥有两种方式1) kthread_create() 2) kernel_thread() 函数,虽然都是创建内核线程,但是二者在原理上不同。kthread_create() 创建的线程是挂在kthreadd()上面,kthread_create创建的内核线程有干净的上那上下文环境,适合于驱动模块或用户空间的程序创建内核线程使用,不会把某些内核信息暴露给用户程序。而kernel_thread()创建的线程来自于init进程。

所以我们推荐使用kthread_create()这种感觉方式创建内核线程,这种方式有利于模块的加载与卸载,有的时候kernel_thread创建的线程不容易卸载,只能通过reboot处理这种问题。

另外我们要非常注意内核线程的可重入性,在线程中使用函数必须保证函数是线程安全的,有些函数并不保证线程安全,如果我们在一个模块中修改全局变量,很有可能导致数据的不一致性,这里有必要要加锁。

 

参考:

http://www.spongeliu.com/165.html

http://blog.csdn.net/maimang1001/article/details/16906451

信号处理的时机

June 4th, 2015 by JasonLe's Tech 1,893 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 1,533 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 2,082 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中,只有进程的页表是时刻在更换的,而内核页表全局只有一份,所有进程共享内核页表!