[原理分析]linux内核中的链表原理实践[3]

浏览数：25 / 时间：2015年06月20日

摘要：

本文的第[一，二]系列主题虽然是链表操作，内容还是指针的操作，本文通过链表实例来阐述下指针操作。不仅仅涉及到数据节点指针，也还涉及到函数指针，最后还涉及基于指针的函数体优化。

正文：

本文主要阐述链表中的节点删除操作，并且在删除过程中使用回调函数。回调函数本身也很简单，就是判断当前节点中数据的奇性或者偶性，来判断是否删除该数据节点。

#include "stdafx.h"
#include <memory>

typedef struct node{
	int value;
	node* next;
}node;

typedef bool (* condValid) (node* stu);

bool pickEven(node* n)
{
	if((n->value) % 2 == 0)
		return true;
	return false;
}

bool pickOdd(node* n)
{
	if((n->value) % 2 == 1)
		return true;
	return false;
}

node* addNode(node* head, int value)
{
	if(head != NULL)
	{
		node* n = new node();
		n->value = value;
		n->next = head->next;
		head->next = n;
	}else{
		head = new node();
		head->next = NULL;
		head->value = value;
	}
	return head;
}

node* delNode(node* head,  condValid validRemove)
{
	node* prev;
	node* cur;

	for(prev = NULL, cur = head; cur; ){
		node* const next = cur->next;
		if(validRemove(cur)){
			if(prev){
				prev->next = next;
			}else{
				head = next;
			}
			free(cur);
		}else{
			prev = cur;
		}
		cur = next;
	}
	return head;
}


void showList(node* head)
{
	for(;head; head=head->next)
		printf("%d ", head->value);
	printf("\n");
}

void testAdd()
{
	node* head = NULL;
	head = addNode(head, 2);
	head = addNode(head, 3);
	head = addNode(head, 5);
	head = addNode(head, 6);

	showList(head); //it should show 2, 6, 5, 3;
}

void testDel()
{
	node* head = NULL;

	head = addNode(head, 2);
	head = addNode(head, 3);
	head = addNode(head, 5);
	head = addNode(head, 6);

	showList(head); //it should show 2, 6, 5, 3;
	node* head1 = delNode(head,pickEven);
	printf("after delNode using isEvenSel:\n");
	showList(head1); //it should show 5, 3;

	node* head2 = delNode(head1, pickOdd);
	printf("after delNode using isOddSel:\n");
	showList(head2); //it shoud show nothing.
}

int _tmain(int argc, _TCHAR* argv[])
{
	//testAdd();
	testDel();

	getchar();
	return 0;
}</span>

上面的delNode函数需要注意的是在for语句中：1.for(prev = NULL, cur= head; cur; ){后面并没有马上跟上常见的cur=cur->next；2. 在循环内部一开始就采用将cur->next保存下来；1和2的原因都在于cur当前节点可能在循环中被删除。上述的delNode的唯一不足在于，每次需要返回head节点；如何做到不用返回变更后的head值呢？很直接的我们会想到指针。于是，我们将head的地址作为参数传入，具体的代码如下：

void delNode2(node** head,  condValid validRemove)
{
	node** cur;
	node* entry;

	for(cur=head;*cur; ){
		entry = *cur;
		if(validRemove(entry)){
			*cur = entry->next;
			free(entry);
		}else{
			cur = &entry->next;
		}
	}
}

void testDel2()
{
	node* head = NULL;

	head = addNode(head, 2);
	head = addNode(head, 3);
	head = addNode(head, 5);
	head = addNode(head, 6);
	
	showList(head); //it should show 2, 6, 5, 3;
	delNode2(&head,pickOdd);   
	showList(head); //it should shoe 2, 6;
}

上述代码的关键在于*cur = entry->next是覆盖，而cur=&entry->next则是移动，具体的流程可以参照下图：

上图有四个数据节点：a1, a2, a3, a4；假设我们要删除其中的a1和a3，在每个步骤中所导致的cur的*cur的变化过程。

下面我们再来看个基于指针的优化，所摘的代码来源于linux2.6早期版本的网络部分，此处不需要理解代码背后的网络原理，只需要就代码论代码就可以说明白其中所包含的优化原理，那么首先来看下面的示例代码（linux中原代码的简化实现）：

for (ptype = ptype_base; ptype != NULL; ptype = ptype->next)
  {		
if ((ptype->type == type || ptype->type == htons(ETH_P_ALL)) && (!ptype->dev || ptype->dev==skb->dev)){
        struct sk_buff *skb2;
        skb2=skb_clone(skb, GFP_ATOMIC);
        if(skb2)
            ptype ->func(skb2, skb->dev, ptype);
    }
}
kfree_skb(skb, FREE_WRITE);

光从代码的表面可以理解，其主要的目的是遍历某个链表，找出其中满足条件的节点进行深度拷贝(skb_clone)，将拷贝后的节点作相应的处理，最后再将原始节点skb释放掉；上述代码的主要问题在于skb_clone操作是非常费时的，那有没有办法可以减少clone操作次数呢？可以利用的就是skb，假设这里要拷贝10次，那么最后一次就可以认为是不必要的，可以直接利用skb，因为反正不用白不用，马上skb就会被kfree_skb函数销毁；即使用了，因为skb不会再用作拷贝的原型(最后一次)，所以直接利用skb进行ptype->func()操作是合理的。问题是如何免除最后一次的skb2拷贝，直接用skb来实现ptype->func()操作呢？参考linux社区中内核黑客的解决方案：通过增加额外的局部变量，实现延迟type->func()的处理。

修改1：增加用于暂存ptype的局部变量：pt_prev = NULL;

修改2：对for循环中的if语句进行相应的修改：

if(pt_prev)
{
        struct sk_buff *skb2;
        skb2=skb_clone(skb, GFP_ATOMIC);
        if(skb2)
            pt_prev ->func(skb2, skb->dev,pt_prev);
}
pt_prev = ptype;

修改3：在退出for循环后，处理掉最后的一个ptype：

<span style="font-size:14px;">if(pt_prev)
	pt_prev->func(skb, skb->dev, pt_prev);
else
	kfree_skb(skb, FREE_WRITE);</span>

整合上述的代码修改，最后可以得到：

pt_prev = NULL;
for (ptype = ptype_base; ptype != NULL; ptype = ptype->next)
{		
if ((ptype->type == type || ptype->type == htons(ETH_P_ALL)) && (!ptype->dev || ptype->dev==skb->dev))
{
      if(pt_prev) 
{
<span style="white-space:pre">	</span>struct sk_buff *skb2;
       skb2=skb_clone(skb, GFP_ATOMIC);
        if(skb2)
           	pt_prev ->func(skb2, skb->dev, pt_prev);
}
pt_prev = ptype;
}
}//end of loop;

if(pt_prev)
	pt_prev->func(skb, skb->dev, pt_prev);
else
kfree_skb(skb, FREE_WRITE);

启发：

1. 上述代码中展示一种延迟处理的代码技巧，虽然扣出性能，但是程序的实现复杂度提升，代码不容易读懂；

2. 由于操作系统优化的需要，linux实现中肯定包含很多上述的代码优化措施，作为学习者需要有一定的代码简化能力和思考追问能力；

参考资料：

http://coolshell.cn/articles/8990.html

http://coolshell.cn/articles/9859.html