DRAM页映射到BANK中的两种形式

July 4th, 2015 by JasonLe's Tech 3,927 views

在之前的一篇博文上,我分析了DRAM的物理结构与从bank中存取数据的方式。这里我继续这个话题,并引入一种新式的内存存取数据的方式:Permutation-based Page Interleaving。

当CPU发送物理内存地址给内存的时候需要首先发送给memory controller,然后由memory controller将其翻译成内存地址,也就是以DIMM Rank Chip Bank为单位的地址形式,如下图所示:20150421162433 我们知道CPU对Memory的读写要经过cache,在这里可以认为CPU与cache是一体的,读到了cache也就等于被CPU使用。传统的memory与cache的关系是多路并联、单路并联,也就是说一系列的内存物理地址,被分割成了tag段,每个tag段内的每个内存地址映射到不同cache line中。

cache-related

也就是说不同tag段的相同set index会被映射到同一个cache line中,而最后的block offset正是cache line的大小,也就是说这个物理地址中的内容放到cache line中正是cache line的大小,然后我们将这个位数变化一下,就是传统物理地址对应三个部分,page index,bank index,page offset。而其中bank index的信息是具体的硬件实现(硬件生产商不会对外公布这种参数),一般我们使用软件的方式来测试bank位!

这里的page不是我们常规意义上的物理页,而是第一个图中以bank 与row组成的一行称为page。

下面我们来做一个推定:比如tag值不同,后面set index,block offset两个字段相同的两个物理地址,必定映射同一个cache line。转换到下面的DRAM的页模式,set index相同,那么bank index一定相同,也就是说两个数据处于同一个bank中,又因为tag不同,那么page index不同,意味着不属于同一个row,而每个bank只有一个row buffer,这样必然导致L3(CPU最后一级cache)无法命中,导致 L3 cache conflict miss!

举例:

double x[T], y[T], sum;
for(i = 0; i < T; i++);
     sum += x[i] * y[i];

若x[0] 和y[0] 的距离是L3 cache 大小的倍数,必然会导致读取x[i],y[i]发生L3 cache conflict miss!CPU不得不每次讲L3 cache清空,读取新的数据,这样必然大大增加了数据访问的延迟!

为了避免这种情况工程师提出了一种新的内存page交叉访问方式Permutation-based Page Interleaving Scheme,首先我们看这个算法如何降低了 L3 cache conflict miss。

permutation

 

他在传统物理地址对应的banks存取上,使用tag的一些位与bank index做异或运算,这样就可以大大降低内存页交叉访问带来的L3 conflict miss,不同tag的相同bank index会被映射到不同的bank中!

DRAM

而我们知道每个bank都有一个row buffer,只要我们保证程序局部性存取的数据在不同row buffer中,这样就意味着row buffer的数据可以长时间存在,不同频繁的清空,当需要这些数据,直接从row buffer中读取到memory controller就可以了。而程序的局部性并没有被破坏,仍然存在在一个DRAM page!

DRAM_bank

 

这两种方式长时间存在于DRAM交叉存取bank中,有时候我们在测试Bank位会遇到这两种方式,因此我们必须使用特定工具去检测决定bank位的index,如过检测bank index非常多,就要考虑是否是XOR交叉存取方式了!

 

 

论文:http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=898056

进程控制踩过的坑

July 1st, 2015 by JasonLe's Tech 906 views

1. fork()与vfork()非常相似,但是使用场景有一些不同,vfork()主要用来创建子进程,然后执行exec()一个新的程序,不会发生COW(fork()出来的子进程exec()会产生COW,所以vfork()更加快速),vfork()可以保证子进程先运行,调用exec()、exit之后才会被调度,如果子进程依赖父进程产生一些动作的话,可能产生死锁

2. vfork()在父进程空间中运行,这个导致子进程可以修改父进程的值!

3. 之前在C/S模型下Server 中fork()的健壮性中说过,fork()产生的子进程退出后,发送SIGCHLD信号,如果不及时使用wait方式处理的话,会产生僵尸进程。反过来,如果父进程先停止,那么子进程退出时,会向init进程发送SIGCHLD信号。

4. wait()与waitpid()都可以接受终止子进程发送的信号,wait()是waitpid()的简化版本,wait()返回任意一个终止子进程的状态,waitpid()可以接受特定子进程的信号。

5. 按照之前第3条所叙述的,我们可以利用这个init领养子进程规则让init管理孤儿进程,这里有一个技巧:fork()两次!

int main(void)
{
        pid_t pid;
        if ((pid = fork()) < 0) {
             err_sys("fork error");
        } else if (pid == 0) { /* first child */
             if ((pid = fork()) < 0)
                  err_sys("fork error");
             else if (pid > 0)
                  exit(0); /* parent from second fork == first child */
//这个exit(0)退出的就是第一次fork()出来的子进程,也是第二次fork()的
//父进程,当这个进程退出后,也就意味着第二次fork()出来的子进程变成
//孤儿进程,直接由init接管!
/*
* We’re the second child; our parent becomes init as soon
* as our real parent calls exit() in the statement above.
* Here’s where we’d continue executing, knowing that when
* we’re done, init will reap our status.
*/
//下面这段是第二次fork()出来子进程执行的代码段
            sleep(2);//必须保证第二次fork()出来的父进程先退出!
            printf("second child, parent pid = %ld\n", (long)getppid());
            exit(0);
        }
        if (waitpid(pid, NULL, 0) != pid) /* wait for first child */
            err_sys("waitpid error");
/*
* We’re the parent (the original process); we continue executing,
* knowing that we’re not the parent of the second child.
*/
        exit(0);
}

这个代码设计的很精巧,开始我没有看懂,仔细分析才可以。

6. 对于某些父子进程拥有竞争条件的代码,必须要使用信号机制或者管道机制实现父子进程同步,其中TELL_WAIT(),TELL_PARENT(),WAIT_PARENT(),TELL_CHILD(pid),WAIT_CHILD()可以使用不同的机制定义,从而实现父子进程的有序执行!

     TELL_WAIT(); /* set things up for TELL_xxx & WAIT_xxx */
     if ((pid = fork()) < 0) {
      err_sys("fork error");
     } else if (pid == 0) { /* child */
     /* child does whatever is necessary ... */
     TELL_PARENT(getppid()); /* tell parent we’re done */
     WAIT_PARENT(); /* and wait for parent */
     /* and the child continues on its way ... */
     exit(0);
     }
    /* parent does whatever is necessary ... */
    TELL_CHILD(pid); /* tell child we’re done */
    WAIT_CHILD(); /* and wait for child */
    /* and the parent continues on its way ... */
    exit(0);

7. 使用信号机制来实现父子进程同步的话,可以自定义SIGUSR1,SIGUSR2的方式,在main()开始部位,设置中断处理函数,函数修改一个全局volatile sig_atomic类型的变量sigflag,然后在等待函数中,轮训挂起等待信号,直至进程处理信号,跳出这个循环:

while (sigflag == 0)
       sigsuspend(&zeromask); /* and wait for parent */
sigflag = 0;

8.使用pipe,可以在等待函数中读管道,在通知函数中写管道,达到父子进程的同步!

void TELL_PARENT(pid_t pid)
{
    if (write(pfd2[1], "c", 1) != 1)
        err_sys("write error");
}
void WAIT_PARENT(void)
{
    char c;
    if (read(pfd1[0], &c, 1) != 1)
        err_sys("read error");
    if (c != ’p’)
        err_quit("WAIT_PARENT: incorrect data");
}

 

 

参考:
APUE P185,P270,P402

字符串切割问题求解

June 30th, 2015 by JasonLe's Tech 791 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 925 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 941 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