字符串切割问题求解

June 30th, 2015 by JasonLe's Tech 726 views

我在做Leetecode的一道题时,遇到了一道切割字符串求解回文字符串的题目,题目大意如下:

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

这个时候我们需要使用DFS算法,进行深搜,但是这个里我们需要注意的一个问题是,每个字符只能用一次,而且不能使用拼接的方式,需要直接从string s中截取子字符串,所以我们使用s.substr(start,count)的方式。这个不同于之前的combinationSum的题目,需要有一个中间target保存。我们只需要传入下面几个参数即可,使用step来标示当前指向s的开头index,i为结束index。

void DFS(string &s,vector<vector<string>> &result,vector<string> &path,int step){
		if(step>=s.size()){
			result.push_back(path);
			return;
		}
		for(auto i = step;i<s.size();i++){
			if(is_palindrome(s,step,i)){
				path.push_back(s.substr(step,i-step+1));
				DFS(s,result,path,i+1);
				path.pop_back();
			}
		}
	}

	bool is_palindrome(string &s,int start,int end){
		while(start < end){
			if(s[start]!=s[end])
				return false;
			start++;
			end--;
		}
		return true;
	}
};

一个长度为n 的字符串,有n-1 个地方可以砍断,每个地方可断可不断,因此复杂度为O(2^(n-1))

 

https://leetcode.com/problems/palindrome-partitioning/

memtest86+与BadRAM使用

June 28th, 2015 by JasonLe's Tech 835 views

一般情况下,DRAM的损坏是永久性的损坏,这个时候我们有三种方式解决这个问题:

  1. 买新的内存条
  2. 在kernel启动时加入mem参数,限制当前mem的使用,比如当前内存2GB,在800M地方,内存存在永久故障区域,那么我们可以在kernel的启动参数加入mem=780M,这样就可以限制当前内核分配800M的内存区域而触发MCE。但是这个也有一个明显的缺点:因为这个坏点导致大部分内存无法使用
  3. 在kernel启动加入badram 0x01000000,0xfffffffc即可。

我们这里使用第三种方式来绕过当前的内存坏块,而达到省钱的目的!badram 第一个参数 是出错的物理基地址,第二个参数是mask,来用标示这个掩码。当我们使用memtest86+测试出当前的出错内存物理地址,然后将这个错误地址加入到kernel 参数中即可。

其中memtest86+是一款离线内存检测工具,可以检测内存中的坏页。

下面我们来实验一下,比如当前系统没有出现内存坏块,那么使用iomem参看当前物理内存地址的分布:

00000000-00000fff : reserved
00001000-0009f3ff : System RAM
0009f400-0009ffff : reserved
000a0000-000bffff : PCI Bus 0000:00
000c0000-000dffff : PCI Bus 0000:00
  000c0000-000c7fff : Video ROM
  000cc000-000cd7ff : Adapter ROM
000e0000-000effff : pnp 00:08
000f0000-000fffff : reserved
  000f0000-000fffff : System ROM
00100000-7f6dffff : System RAM
  01000000-017b9cc4 : Kernel code
  017b9cc5-01d1e8ff : Kernel data
  01e86000-01fc8fff : Kernel bss
....

当我们在grub中加入badram 0x01000000,0xfffffffc参数,也就意味着Kernel代码区的地址出现错误,而且错误大小是2bit,这个时候我们重新启动,再查看当前系统物理内存分布,我们会发现:

01000000-010003ff : RAM buffer
01000400-7f6dffff : System RAM
  02000000-027b9cc4 : Kernel code
  027b9cc5-02d1e8ff : Kernel data

kernel 的代码段避过了问题内存区域,我们查看__pa(x)最终调用__phys_addr_nodebug,而其中phys_base则是在real_mode下面被调用。

static inline unsigned long __phys_addr_nodebug(unsigned long x)
{
    unsigned long y = x - __START_KERNEL_map;

    /* use the carry flag to determine if x was < __START_KERNEL_map */
    x = y + ((x > y) ? phys_base : (__START_KERNEL_map - PAGE_OFFSET));

    return x;
}

22996709_13505212884HWu

Real-mode code 在X+0x8000开始,X就是badram传入的offset!

 

 

参考:

http://ubuntuforums.org/archive/index.php/t-1689890.html

http://ubuntuforums.org/showthread.php?t=2278744

https://help.ubuntu.com/community/BadRAM#BADRAM_setting_in_Grub2

http://blog.chinaunix.net/uid-22996709-id-3376998.html

如何杀死一个内核线程

June 23rd, 2015 by JasonLe's Tech 824 views

首先明确杀死一个进程与杀死一个kthread是不同的,杀死进程的时机是进程从内核态返回到用户态检查_TIF_SIGPENDING标志位,进一步进入到处理信号的函数进行处理杀死这个进程。

内核线程运行在整个内核之上,,如果不返回,则不可能检查信号,所以内核的线程实质上的停止与启动必须由线程本身状态决定,不允许随意杀死。如果这个线程正在持有某个全局锁时,强制杀死kthread会造成整个内核的死锁。所以目前kernel对于内核线程的停止主要依赖于线程内部的停止。

一种方式

发送信号,对于内核线程默认是对于信号是忽略的,所以我们要想停止一个线程必须在线程内部使用allow_signal(SIGKILL)方式,然后在内核线程代码的某个部位处理这个信号。所以发送信号的时机非常重要,如果当前kthread正在进行某些业务逻辑,那么发送SIGKILL无效。

另外一种方式

使用目前kernel提供工具函数int kthread_stop(struct task_struct *k) 用来对某个kthread进行停止。这个函数仅仅限于kthread_create()创建的内核线程,通过这个函数创建的内核线程都会被挂在kthreadd 内核线程树上。这种方式也可以被看作是一种发送信号的方式,但是这些函数已经被提供出来供编写者用来停止内核线程。线程内部必须显式的检查THREAD_SHOULD_STOP信号,从而使得线程return或者使用do_exit()退出线程[1]。否则无法停止内核线程。

当kthread_create()创建的内核线程时:

kthread_create
  -> kthread_create_on_node                              // in kthead.c
      -> adds your thread request to kthread_create_list
          -> wakes up the kthreadd_task

当唤醒kthreadd_task时,这个函数会运行kthreadd()。

pid = kernel_thread(kthreadd, NULL, CLONE_FS | CLONE_FILES);
...
kthreadd_task = find_task_by_pid_ns(pid, &init_pid_ns);

kthreadd()这个函数会调用kthread()函数。kthread()函数 调用用户定义的内核线程函数。

kthreadd                                                 // all in kthread.c
  -> create_kthread
      -> kernel_thread(kthread, your_kthread_create_info, ...)

kthread()函数会调用我们自己创建的内核线程函数,当需要停止的时候,检查KTHREAD_SHOULD_STOP位,当返回后会将ret值传递到do_exit(ret),这个也就是我们不用显示调用do_exit()的原因。

kthread
  -> initialization stuff
    -> schedule() // allows you to cancel the thread before it's actually started
      -> if (!should_stop)
          -> ret = your_thread_function()
            -> do_exit(ret)

注意:内核线程return时,默认调用do_exit(ret),如果直接使用do_exit()退出线程,那么必须保证task_struct不被释放否则当继续执行kthread_stop()会释放一个无效的task_struct,导致发生Oops。[4]

当需要停止目标内核线程,kernel会获取当前描述目标内核线程状态的结构体kthread,设置KTHREAD_SHOULD_STOP标示位,然后唤醒这个目标线程,当前进程调用wake_for_completion(&kthread->exited)睡眠,被唤醒的条件其实就是这个目标内核线程的task_struct 上的vfork_done完成,这个标志位在do_exit()中被设置。当前进程/内核线程等待目标内核线程结束的过程时不可中断的,直到目标内核线程退出,最后释放task_struct结构体,这样就可以安全的停止当前线程。

int kthread_stop(struct task_struct *k)
{
        struct kthread *kthread;
        int ret;

        trace_sched_kthread_stop(k);

        get_task_struct(k);
        kthread = to_live_kthread(k);
        if (kthread) {
            set_bit(KTHREAD_SHOULD_STOP, &kthread->flags);
            __kthread_unpark(k, kthread);
            wake_up_process(k);
            wait_for_completion(&kthread->exited);
        }
        ret = k->exit_code;
        put_task_struct(k);

        trace_sched_kthread_stop_ret(ret);
        return ret;
}

上面的代码必须确保task_struct有效,如果无效,调用这个函数会发生Oops。

在内核线程中的业务处理逻辑外使用kthread_should_stop()检查当前线程的KTHREAD_SHOULD_STOP标志位,如果被设置,退出循环,就要执行线程的退出操作。

do {
        //do business
} while(!kthread_should_stop());

[1] http://v4l.videotechnology.com/dwg/kernelthreads/kernelthreads.html
[2] http://lwn.net/Articles/65178/
[3] http://blog.csdn.net/chinayangbo2011/article/details/8923731

[4] http://stackoverflow.com/questions/10177641/proper-way-of-handling-threads-in-kernel

信号处理函数所踩过的坑

June 16th, 2015 by JasonLe's Tech 806 views

Update 2015-6-24

最近在看APUE的信号章节,在这里我总结下进程信号处理中应该注意的一些坑。Unix中有很多的信号是可以被进程接管,然后跳到信号处理函数中。

1. 有两个信号是无法被接管或者被忽略的SIGKILL与SIGSTOP

2. SIGHUP 是要出现在远程ssh一台主机时,连接意外断开时,系统会向所有与这个终端相关的控制进程发送SIGHUP。

3. 在liunx中SIGIO与SIGPOLL相同,默认是终止这个进程。

4. SIGTERM可以由进程编写者定义,当收到这个信号那么,进程可以自行做退出操作的扫尾工作,然后退出程序。

5. signal与sigaction功能相似,但是signal在不同平台上实现不同,应该使用sigaction进程信号的接管。

6. 交互式进程后台运行时,shell会将后台进程设置为对于中断和退出信号的处理方式设置为忽略SIG_IGN。也就是说当向进程发送SIGINT时,捕捉这种类型的代码:

void sig_int(int), sig_quit(int);
if (signal(SIGINT, SIG_IGN) != SIG_IGN)
    signal(SIGINT, sig_int);
if (signal(SIGQUIT, SIG_IGN) != SIG_IGN)
    signal(SIGQUIT, sig_quit);

7. 当父进程fork()一个子进程,子进程将会继承父进程的信号处理函数,这种方式在早期fork()一个子进程后会把这个子进程信号处理函数复位到默认值,我们不必在代码中这么做:

int sig_int(); /* my signal handling function */
...
signal(SIGINT, sig_int); /* establish handler */
...
sig_int()
{
    signal(SIGINT, sig_int); /* reestablish handler for next time */
... /* process the signal ... */
}

8. 信号会发生在任何时刻,我们不能设置flag来使得进程进行忙等。下面这种代码在大多数情况下是正确的,但是如果信号发生在while()与pause()之间,会直接导致进程陷入睡眠,无法醒来。

int sig_int(); /* my signal handling function */
int sig_int_flag; /* set nonzero when signal occurs */
main()
{
     signal(SIGINT, sig_int); /* establish handler */
...
     while (sig_int_flag == 0)
            pause(); /* go to sleep, waiting for signal */
...
}
sig_int()
{
    signal(SIGINT, sig_int); /* reestablish handler for next time */
    sig_int_flag = 1; /* set flag for main loop to examine */
}

9. 被中断的syscall(通常是慢速系统调用:read,write,open()(如果open不返回,就意味着进程会被永久的阻塞) etc.)必须显式的处理出错返回,在linux中被中断的syscall,会重启这个syscall,但是在当次的调用中,会将errno设置为EINTR,所以我们要对这个EINTR进行处理。如下面的代码:

again:
if ((n = read(fd, buf, BUFFSIZE)) < 0) {
    if (errno == EINTR)
        goto again; /* just an interrupted system call */
    /* handle other errors */
}

10. 信号处理函数的可重入性。如果在信号处理函数中调用,会对进程主体的程序执行流造成破坏,产生Sigment fault。在内核中的实现,我发现为了实现进程处理函数在用户态执行,会将内核态的堆栈数据复制到用户空间的堆栈保存,返回用户空间,执行完sys_sigreturn() 再次陷入到内核,将正常程序的用户态堆栈硬件上下文拷贝到内核堆栈,并将之前备份在用户空间的堆栈还原到内核空间,完成这次中断处理函数。

不可重入性:(a) they are known to use static data structures, (b) they call malloc or free, or (c) they are part of the standard I/O library. Most implementations of the standard I/O library use global data structures in a nonreentrant way.

所以按照定义,为了保证函数是可重入的,需要做到一下几点:

  • 不在函数内部使用静态或者全局数据
  • 不返回静态或者全局数据,所有的数据都由函数调用者提供
  • 使用本地数据,或者通过制作全局数据的本地拷贝来保护全局数据
  •  如果必须访问全局数据,使用互斥锁来保护
  • 不调用不可重入函数

getpwnam()函数是非可重入函数,他在中断处理函数中使用的话,就会修改原来应用程序的数据,导致程序出错

#include "apue.h"
#include <pwd.h>
static void
my_alarm(int signo)
{
       struct passwd *rootptr;
       printf("in signal handler\n");
       if ((rootptr = getpwnam("root")) == NULL)
           err_sys("getpwnam(root) error");
        alarm(1);
}
int main(void)
{
       struct passwd *ptr;
       signal(SIGALRM, my_alarm);
       alarm(1);
       for ( ; ; ) {
           if ((ptr = getpwnam("sar")) == NULL)
               err_sys("getpwnam error");
           if (strcmp(ptr->pw_name, "sar") != 0)
               printf("return value corrupted!, pw_name = %s\n",ptr->pw_name);
       }
}

这段代码中的rootptr其实最后都是指向ptr,这就是造成不可重入的关键!我们使用getpwnam_r()函数便可以正常工作。

void sig_handler(int signo)
{
   struct passwd root_ptr;
   struct passwd *result;
   int s;
   char *buf;
   size_t bufsize;

   bufsize = sysconf(_SC_GETPW_R_SIZE_MAX);
   if(bufsize==-1)
      bufsize = 16384;

   buf = malloc(bufsize);
   if(buf==NULL){
      perror("malloc");
      exit(EXIT_FAILURE);
   }

   printf("in sig_handler\n");
   s = getpwnam_r("root",&root_ptr,buf,bufsize,&result);
   if(result == NULL){
      if(s==0)
          printf("Not found\n");
      else{
          // errno = s;
          perror("getpwnam_r");
      }
      exit(EXIT_FAILURE);
   }
   printf("pw_name = %s\n", root_ptr.pw_name);
   alarm(1);
}

11. SIGCHLD这个信号非常特殊,这个信号很多时候与系统的信号实现相关。在linux平台上 SIGCHLD与SIGCLD等同,这里查看C/S模型下Server 中fork()的健壮性文章,我们需要在父进程信号处理函数中调用pid = wait(&stat);实现对于子进程退出的等待。

void sig_zchild(int signo)
{
      pid_t pid;
      int stat;

      while ((pid = waitpid(-1, &stat, WNOHANG)) > 0)
           printf("child %d terminated\n", pid);
      return;
}

12. kill() 函数负责将信号发送给进程或者进程组,raise()是进程向自己发送信号。一个程序全局只能有一个alarm()函数,如果多次调用,那么alarm()登记的值被新值代替。pause()使得调用进程挂起直至捕捉到一个信号,只有执行了一个信号处理函数返回后,pause()才返回。

#include <signal.h>
#include <unistd.h>
static void
sig_alrm(int signo)
{
/* nothing to do, just return to wake up the pause */
}
unsigned int
sleep1(unsigned int seconds)
{
      if (signal(SIGALRM, sig_alrm) == SIG_ERR)
               return(seconds);
      alarm(seconds); /* start the timer */
      pause(); /* next caught signal wakes us up */
      return(alarm(0)); /* turn off timer, return unslept time */
}

这个函数看似正确,但是有一个竞争条件,如果alarm()后调用被阻塞,然后超时,pause()没有捕捉到信号,那么调用到pause()将永久挂起,这里我们要使用到longjmp() 与 setjmp() 可以使得信号处理函数返回到主函数中指定位置,在longjmp第二个参数设置返回值,在setjmp()中检查这个返回值。可以做到跨函数跳跃,类似于函数内部的goto。

所以使用alarm() pause() 慢速系统调用三者很有可能产生竞争,Linux中syscall是被中断后自启动的。

13. 使用sigprocmask() 可以用来屏蔽,或者取消屏蔽某个信号,但是如果在sigprocmask()之后调用sleep() 函数,程序进入睡眠,这个期间产生的某个屏蔽信号,他会被投递到这个进程,进行处理! APUE 10-11

14. 使用sigaction(int signum, const struct sigaction *act,struct sigaction *oldact)对于信号进行处理,struct sigaction下的成员变量sa_flags可以定义各种中断的动作,包括被中断的系统调用是否会重启(SA_INTERUPT)还有信号处理函数只执行一次后复位等(SA_RESETHAND)默认sigaction()函数不再重启被中断的系统调用。

 15. 使用int sigsuspend(const sigset_t *mask)函数可以挂起当前进程,但是当进程收到mask以外的信号并从中断处理函数返回,那么进程从这个函数返回!mask中的信号,进程会屏蔽掉[4]。

16. sleep() 函数与alarm()函数混用,实现需要依赖于具体实现。

17. SIGSTOP、SIGCONT不允许被接管,如果我们需要在SIGSTOP后自定义一些操作,那么我们可以自定义一个信号和信号处理函数。只要跳转到信号处理函数,那么就可以阻止进程访问错误内存地址,进而可以进行一些处理。

 

 

参考:

[1] http://www.cnblogs.com/mickole/p/3187770.html

[2] http://www.man7.org/linux/man-pages/man3/getpwnam.3.html

[3] http://blog.csdn.net/feiyinzilgd/article/details/5811157

[4] http://blog.sina.com.cn/s/blog_6af9566301013xp4.html

从用户态到内核态的切换

June 14th, 2015 by JasonLe's Tech 925 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/