Archive for the ‘C/C++’ category

Recursing with STL

March 31st, 2015

最近使用装有节点值的vector容器的前序遍历与中序遍历去构造一颗Binary Tree。

我们都知道先序遍历的顺序是 :中-左-右,中序遍历的顺序是:左-中-右,后续遍历是左-右-中。

举例:

//         1
//        / \
//       2   5
//      / \   \
//     3   4   6

这棵树的先序遍历:1 2 3 4 5 6 中序遍历: 3 2 4 1 5 6 后续:3 4 2 6 5 1 。

众所周知,已知一个树的先序和中序,或者是中序和后续,便可以构造出一棵树,构造的思路是先序的第一个节点就是根,然后查找这个根在中序中的位置,中序遍历中根的位置的左边就是左子树,后面是右子树。然后递归进入到下一层:先序 2 3 4 中序 3 2 4 ,可以看出先序中2是根,然后查找中序2的位置,就得到 3 是 2 的左子树,4是2的右子树,依次recurse。

下面使用STL的方式构造这棵树:已知vector &preorder, vector &inorder是装有先序和中序的vector容器,使用递归就是设置出一个中间状态,对他进行分析,并且函数的参数必须是每次都可以用减小范围的。

STL中,我们都知道有vector::iterator方式来遍历vector元素值,获取这种iterator有两种方式:1)preorder.begin()获取vector中第一个元素的指针。2)begin(preorder),返回的也是vector第一个指针。他们都可以使用*得到值。

end()比较特殊,它返回的是最后元素的下一个元素,也就是一个越界的元素,直接引用会导致数组越界。

auto pos = find(preorder.begin(),preorder.end(),val) 查找当前val的的节点,返回当前val的指针。
distance(preorder.begin(),pos) 直接返回中开始到pos的距离,不包括pos。

//1 2 3 4 5 6
auto Pos = find(pre_order.begin(),pre_order.end(),4);
auto dis = distance(pre_order.begin(),Pos);
cout << dis << "\n";
cout << *next(pre_order.begin(),dis);

我们发现dis = 3,而next是从1开始的3个元素后的下一个元素,也就是val=4的指针。

我们在定义这种迭代器声明的时候,会发现函数参数非常长

TreeNode *buildTree(vector<int>::iterator inorder_first,vector<int>::iterator inorder_end,
		vector<int>::iterator postorder_first,vector<int>::iterator postorder_end)

我们可以使用模板编程极大地简化声明:

template<typename InputIterator>
TreeNode *buildTree(InputIterator inorder_first,InputIterator inorder_end,
		InputIterator postorder_first,InputIterator postorder_end)
{
	if(postorder_first==postorder_end)
		return NULL;
	if(inorder_first==inorder_end)
		return NULL;
	int val = *prev(postorder_end);
	TreeNode *root = new TreeNode(val);

	auto in_rootPos = find(inorder_first,inorder_end,val);
	auto left_size = distance(inorder_first,in_rootPos);

	root->left = buildTree(inorder_first,next(inorder_first,left_size),postorder_first,
		next(postorder_first,left_size));
	root->right = buildTree(next(inorder_first,left_size+1),inorder_end,next(postorder_first,left_size)
		,prev(postorder_end));

	return root;
}

上面的代码是后序遍历与中序遍历组合成一棵树,先序与中序也是类似的。

 

 

参考:
http://www.cplusplus.com/reference/iterator/begin/?kw=begin
http://www.cplusplus.com/reference/iterator/end/?kw=end
http://www.cplusplus.com/reference/iterator/InputIterator/

Coccinelle 使用

January 20th, 2015

Coccinelle是一个程序的匹配和转换引擎,它提供了语言SMPL(语义补丁语言)用于指定C代码所需的匹配和转换。Coccinelle 最初是用来帮助Linux的演变,支持更改库应用程序编程接口,比如重命名一个函数,增加一个依赖于上下文的函数参数或者重新组织一个数据结构。除此之外,Coccinelle页被人用来查找或者修复系统代码的bug。

项目地址:https://github.com/coccinelle/coccinelle

安装在这里不再赘述,这里要注意的是需要安装python的devel包,否则这个程序无法运行!

$git clone https://github.com/coccinelle/coccinelle
$git tag > git checkout -b build coccinelle-1.0.0-rc21
$apt-get install python2.6-dev libpycaml-ocaml-dev libmenhir-ocaml-dev menhir ocaml-native-compilers \
ocamlduce camlp4-extra ocaml-findlib pkg-config texlive-fonts-extra
$./configure --with-python --with-menhir
$make all
$apt-get remove coccinelle (prevent conflict)
$make install

安装完毕之后,我们可以定义脚本

@search@
identifier fn,call;
statement s1,s2;
expression E1,E2;
int fd;
position p;
constant C;
@@

<+...
* fd=open@p(...);
//  ...when != fn(<+...fd...+>);
  ...when !=fd=C
* if (fd<0||...){...}
...+>   

@script:python@
p << search.p;
@@

print "%s equal expression" % (p[0].line)

之后我们可以运行这个脚本,可以快速从代码中匹配。

$spatch -sp_file demos/simple.cocci demos/simple.c -o /tmp/new_simple.c

目前这个项目的问题是文档不是很完善,期待之后这个项目的发展。这个工具吸引人的地方在于可以智能的匹配譬如i++ <=> i=i+1这种形式。

目前我们可以更多的参考/usr/local/share/coccinelle/standard.iso

 

 

tools/vm/page-types.c 解析使用

December 9th, 2014

page-types.c这个代码位于kernel源码下的tool/vm/page-type.c

我们可以通过使用makefile编译这个程序,通过这个程序我们可以查找每个特定进程的page frame number  记住这个pfn只是一个index而已,我们如果想取得真实的物理地址需要使用pfn*page_size,当然这个是page frame 的物理起始地址。

这个程序是位于用户态,通过查找/proc/pid/pagemap 和 /proc/pid/maps来找到pfn的。

这个程序的功能比较强大,我们使用的仅仅是指定一个$./page-type -p pid

首先mian()中先要解析参数,然后通过parse_number()来获取用户输入的pid,然后我们知道当指定了一个pid,也就意味着我们打开一个正在运行的pid的maps

[root@localhost 13352]# ls
attr       clear_refs       cpuset   fd       limits    mountinfo   ns         oom_score_adj  root       stack   syscall
autogroup  cmdline          cwd      fdinfo   loginuid  mounts      numa_maps  pagemap        sched      stat    task
auxv       comm             environ  gid_map  maps      mountstats  oom_adj    personality    sessionid  statm   uid_map
cgroup     coredump_filter  exe      io       mem       net         oom_score  projid_map     smaps      status  wchan
00400000-00401000 r-xp 00000000 fd:02 4330673                            /home/lzz/mca-ras/src/tools/simple_process/simple_process
00600000-00601000 r--p 00000000 fd:02 4330673                            /home/lzz/mca-ras/src/tools/simple_process/simple_process
00601000-00602000 rw-p 00001000 fd:02 4330673                            /home/lzz/mca-ras/src/tools/simple_process/simple_process
019b8000-019d9000 rw-p 00000000 00:00 0                                  [heap]
33c1a00000-33c1a20000 r-xp 00000000 fd:01 2622088                        /usr/lib64/ld-2.18.so
33c1c1f000-33c1c20000 r--p 0001f000 fd:01 2622088                        /usr/lib64/ld-2.18.so
33c1c20000-33c1c21000 rw-p 00020000 fd:01 2622088                        /usr/lib64/ld-2.18.so
33c1c21000-33c1c22000 rw-p 00000000 00:00 0
33c1e00000-33c1fb4000 r-xp 00000000 fd:01 2622743                        /usr/lib64/libc-2.18.so
33c1fb4000-33c21b3000 ---p 001b4000 fd:01 2622743                        /usr/lib64/libc-2.18.so
33c21b3000-33c21b7000 r--p 001b3000 fd:01 2622743                        /usr/lib64/libc-2.18.so
33c21b7000-33c21b9000 rw-p 001b7000 fd:01 2622743                        /usr/lib64/libc-2.18.so
33c21b9000-33c21be000 rw-p 00000000 00:00 0
7f3fe081a000-7f3fe081d000 rw-p 00000000 00:00 0
7f3fe083c000-7f3fe083e000 rw-p 00000000 00:00 0
7fff87571000-7fff87592000 rw-p 00000000 00:00 0                          [stack]
7fff875fe000-7fff87600000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]

我们可以看到这个进程每个段,包括BSS CODE HEAP STACK等。然后哦page-types.c中的parse_pid读取这个表里面的信息。
关于这个表每个列的含义看这个http://stackoverflow.com/questions/1401359/understanding-linux-proc-id-maps

我们主要关注头两行,vm_start vm_end。这时我们要获取虚拟地址的page number:

pg_start[nr_vmas] = vm_start / page_size;
pg_end[nr_vmas] = vm_end / page_size;

至于这个page_size可以通过page_size = getpagesize();获取。这里我们要注意unsigned long的取值范围是0-2^64-1,-1也就是2^64-1

然后我们进入walk_task()函数,因为process可能会存在匿名映射,所以我们需要使用filebacked_path[i]判断文件地址。

进入walk_vma()后。
这时我们需要读取/proc/pid/pagemap,这个我们用常规打不开,所以我们只好通过vm index读取的方式获得pages和pfn的相关信息。

详细我们查看

http://stackoverflow.com/questions/17021214/decode-proc-pid-pagemap-entry
https://www.kernel.org/doc/Documentation/vm/pagemap.txt

关注

* Bits 0-54 page frame number (PFN) if present
* Bit 63 page present
下面就是通过编程的方式获取这个的0-54位。总的来所就是使用位操作:

#define PFN_MASK (((1LL)<<55)-1)  //意味着0-54位都为1
*phy=(buf&PFN_MASK)*page_size+vir%page_size

核心函数:

        for (i = 0; i < pages; i++) {
//          printf("%lx\n",buf[i]);
            pfn = pagemap_pfn(buf[i]);
            if (pfn) {
                printf("%lx", pfn);
                printf("\t0x%lx",pfn*page_size);
                walk_pfn(index + i, pfn, 1, buf[i]);
            }
        }

我们可以看到pfn只是一个index而已,真正的物理地址需要pfn*page_size的方式,后面的各种属性是通过读取/proc/kpageflags获得。结果如下:

/home/lzz/mca-ras/src/tools/simple_process/simple_process
93a12	0x93a12000	referenced,uptodate,lru,active,mmap,private

/home/lzz/mca-ras/src/tools/simple_process/simple_process
54d07	0x54d07000	uptodate,lru,active,mmap,anonymous,swapbacked

/home/lzz/mca-ras/src/tools/simple_process/simple_process
9aa43	0x9aa43000	uptodate,lru,active,mmap,anonymous,swapbacked

[heap]
91f74	0x91f74000	uptodate,lru,active,mmap,anonymous,swapbacked
60fb3	0x60fb3000	uptodate,lru,active,mmap,anonymous,swapbacked
...............

 

我们看到物理地址只是在后面添加了3个0,其实也就是12位,正好是一个4k page的页内offset。

Linux中的虚拟地址转换物理地址实现

November 26th, 2014

Linux使用一种4级页表机制,即页全局目录(Page Global Directory)、页上级目录(Page Upper Directory)、页中间目录(Page Middle Directory)和页表(Page Table)。在这种分页机制下.

一个完整的线性地址被分为五部分:页全局目录、页上级目录、页中间目录、页表和偏移量,但是对于每个部分所占的位数则是不定的,这跟系统所在的体系架构有关。

Linux分别采用pgd_t、pud_t 、pmd_t和pte_t四种数据结构来表示页全局目录项、页上级目录项、页中间目录项和页表项。这四种数据结构本质上都是无符号长整型,Linux为了更严格数据类型检查,将无符号长整型分别封装成四种不同的页表项。

static void get_pgtable_macro(void)
{
	printk("PAGE_OFFSET = 0x%lx\n", PAGE_OFFSET);
	printk("PGDIR_SHIFT = %d\n", PGDIR_SHIFT);
	printk("PUD_SHIFT = %d\n", PUD_SHIFT);
	printk("PMD_SHIFT = %d\n", PMD_SHIFT);
	printk("PAGE_SHIFT = %d\n", PAGE_SHIFT);

	printk("PTRS_PER_PGD = %d\n", PTRS_PER_PGD);
	printk("PTRS_PER_PUD = %d\n", PTRS_PER_PUD);
	printk("PTRS_PER_PMD = %d\n", PTRS_PER_PMD);
	printk("PTRS_PER_PTE = %d\n", PTRS_PER_PTE);

	printk("PAGE_MASK = 0x%lx\n", PAGE_MASK);
}

static unsigned long vaddr2paddr(unsigned long vaddr)
{
	pgd_t *pgd;
	pud_t *pud;
	pmd_t *pmd;
	pte_t *pte;
	unsigned long paddr = 0;
        unsigned long page_addr = 0;
	unsigned long page_offset = 0;

	pgd = pgd_offset(current->mm, vaddr);
	printk("pgd_val = 0x%lx\n", pgd_val(*pgd));
	printk("pgd_index = %lu\n", pgd_index(vaddr));
	if (pgd_none(*pgd)) {
		printk("not mapped in pgd\n");
		return -1;
	}

	pud = pud_offset(pgd, vaddr);
	printk("pud_val = 0x%lx\n", pud_val(*pud));
	if (pud_none(*pud)) {
		printk("not mapped in pud\n");
		return -1;
	}

	pmd = pmd_offset(pud, vaddr);
	printk("pmd_val = 0x%lx\n", pmd_val(*pmd));
	printk("pmd_index = %lu\n", pmd_index(vaddr));
	if (pmd_none(*pmd)) {
		printk("not mapped in pmd\n");
		return -1;
	}

	pte = pte_offset_kernel(pmd, vaddr);
	printk("pte_val = 0x%lx\n", pte_val(*pte));
	printk("pte_index = %lu\n", pte_index(vaddr));
	if (pte_none(*pte)) {
		printk("not mapped in pte\n");
		return -1;
	}

	//页框物理地址机制 | 偏移量
	page_addr = pte_val(*pte) & PAGE_MASK;
	page_offset = vaddr & ~PAGE_MASK;
	paddr = page_addr | page_offset;
	printk("page_addr = %lx, page_offset = %lx\n", page_addr, page_offset);
        printk("vaddr = %lx, paddr = %lx\n", vaddr, paddr);

	return paddr;
}

通过代码我们发现线性地址寻值过程:pgd_t -> pud_t ->pmd_t ->  pte_t  

具体Dmesg打印信息:

dmesg.log

目前在X86_64环境下,虽然支持64位,但是系统实际上目前远远使用不了如此大的内存,真正使用的只有48位,即

0xffff000000000000

 

然后使用上面的宏函数进行移位操作,拼接出下一级的页表物理基地址。然后再和后面的pud,pmd,pte部分地址相加,得到下一级的物理基地址。直到最后拿到页框的物理地址与pte或,找到真实的物理地址。

参考:

arch/x86/include/asm/pgtable_64_types.h

 

C/S模型下Server 中fork()的健壮性

October 30th, 2014

C/S模型下Server 下编程非常依赖fork()子进程去处理具体的业务逻辑。 每当accept()接收到一个TCP连接时,主服务器进程就fork一个子服务器进程。子服务器进程调用相应的函数,通过client_fd(连接套接字)对客户端发来的网络请求进程处理;由于客户端的请求已被子服务进程处理,那么主服务器进程就什么也不做,通过sockfd(监听套接字)继续循环等待新的网络请求。

..........
while (1) {
	sin_size = sizeof(struct sockaddr_in);
	if ((client_fd = accept(sockfd, (struct sockaddr *)&remote_addr, &sin_size)) == -1) {
		my_error("accept", errno, __LINE__);
		continue;
	}

	if ((pid = fork()) == 0) {
		close(sockfd);
		process_client_request(client_fd);
		close(client_fd);
		exit(0);
	} else if (pid > 0)
		close(client_fd);
	else
		my_error("fork", errno, __LINE__);
}

每个文件都有一个引用计数,该引用计数表示当前系统内的所有进程打开该文件描述符的个数。套接字是一种特殊的文件,当然也有引用计数。 当fork执行后,由于子进程复制了父进程的资源,所以子进程也拥有这两个套接字描述符,则此时sockfd和client_fd的引用计数都为2。只有当子进程处理完客户请求时,client_fd的引用计数才由于close函数而变为0。 但是这里存在一个严重的问题:如果客户端意外退出,就会导致server子进程成为僵尸进程。我们设想如果server非常繁忙,就会导致system出现大量的zombie进程!system会应该耗尽系统资源而宕机! 这是因为

当一个子进程先于父进程结束运行时,它与其父进程之间的关联还会保持到父进程也正常地结束运行,或者父进程调用了wait才告终止。

子进程退出时,内核将子进程置为僵尸状态,它只保留最小的一些内核数据结构,以便父进程查询子进程的退出状态。

进程表中代表子进程的数据项是不会立刻释放的,虽然不再活跃了,可子进程还停留在系统里,因为它的退出码还需要保存起来以备父进程中后续的wait调用使用。

所以我们要处理zombie进程! 两种方式:

  • 调用wait或者waitpid函数查询子进程退出状态,此方法父进程会被挂起。
  • 如果不想让父进程挂起,可以在父进程中加入一条语句:signal(SIGCHLD,SIG_IGN);表示父进程忽略SIGCHLD信号,该信号是子进程退出的时候向父进程发送的。

当子进程终止时会给父进程发送SIGCHLD信号,因此我们可以利用信号处理函数捕获这个信号并对僵死进程进行处理。我们知道在父进程中调用wait函数可以防止先于父进程终止的子进程编程僵死进程

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

	pid = wait(&stat);
        printf("child %d terminated\n", pid);
	return;
}

修改服务器程序,在accept函数调用之前调用signal函数:

	if(listen(sockfd, BACKLOG) == -1) {

		printf("listen error!\n");
		exit(1);
	}

	if (signal(SIGCHLD, sig_zchild) == SIG_ERR) {
		printf("signal error!\n");
		exit(1);
	}

	while (1) {

		sin_size = sizeof(struct sockaddr_in);
		if ((client_fd = accept(sockfd, (struct sockaddr *)&remote_addr,
&sin_size)) == -1) {

			printf("accept error!\n");
			continue;
		}
		…… ……
	}//while

但是这个程序仍存在一个问题:当多个子进程同时退出时,会导致父进程无法同时处理SIGCHILD信号,导致有部分子进程zombie。

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

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

 return;
}

使用while可以等待SIGCHILD信号,直到处理完成! 信号在内核中也是存放在队列中!

 

 

参考:http://www.cnblogs.com/mickole/p/3187770.html