从prev,next到list , 再到list rcu

以前自己写程序，都是自己些prev , next指针来构造成链表。难免出错，需要调试半天。从2.4开始，内核增加了list.h，这个库实现了很好的循环双向链表的功能。自己也就习惯了用list_add , list_del , list_for_each...一系列函数。使用list库的好处显而易见，不用自己操作链表指针，也不用自己些添加，删除 , 直接用很方便，加上list_entry结合，简直用的很爽，另外一个就是用了list后，减少了代码函数。

常见的list操作如何所示 :

int look_func( xxx )
{
lock section

list_for_each( pnew , phead ){
h_p = list_entry( pnew , struct xxx , member_name );
.....

}

unlock section
}

int add_func( xxxx )
{

new = kmalloc( xxx );
pnew = &(new->list);

lock section

list_add( pnew , phead );

unlock section
}

int del_func( xxxx )
{
lock section

list_del( pold );

unlock section

old = list_entry( pold , struct xxx , member );
kfree( old );

}

此处的锁由调用的点决定，在网络处理中，一般使用spin_lock , rw_lock .

从2.6内核开始，确切的说是从2.5内核开始，加入了rcu锁。 自然list.h也加入了对rcu的支持

上面的代码也就可以演变成如下:

int look_func( xxx )
{
rcu_lock( );

list_for_each_rcu( pnew , phead ){
h_p = list_entry( pnew , struct xxx , member_name );
.....

}

rcu_unlock();
}

int add_func( xxxx )
{

new = kmalloc( xxx );
pnew = &(new->list);

old lock section

list_add_rcu( pnew , phead );

old unlock section
}

int del_free( void * arg )
{
kfree( arg ); //feel free to free the memory
}

int del_func( xxxx )
{
lock section

list_del_rcu( pold );

unlock section

old = list_entry( pold , struct xxx , member );
call_rcu( xxx , del_free , old ); //注册回掉函数del_free

}

在rcu版本中， old lock的锁是否需要取决于add函数和del函数是否会同时运行，如果绝对串行，old lock func就可以不需要。
rcu的引入，是的look_func中没有锁，rcu_lock()也仅仅是关闭内核的抢占功能。rcu的最基本的原理就是在一个没有任何内核running_routine再会对这会数据引用的时候，去释放他。当然这个要求任何其他地方不能有指针指向这会数据，如果有这样的需求，就需要加入传统的refcnt机制了。

从2.6内核开始，很大部分代码就开始想rcu版本改动了，但是rcu并不是适合所有地方的。 就想rwlock一样，并不适合任何数据结构。使用rcu有两个前提：(1) 读的次数大大大于写的次数 (2)读端对数据的新旧并不敏感。

由于工作上还是停留在2.4内核，所以一直没有使用rcu机制，这次也是第一次尝试，如果有错误，欢迎指出。

内核的用户态驱动程序议论

目前,kenrel maillist在讨论一个user space driver的patch .这个patch的目的是减少写驱动程序时候的内核代码,在用户态实现驱动的功能代码。但是，该机制并没有使驱动程序的内核代码完全消息。 一个驱动程序还是需要在内核注册一个小的module来进行,pci注册， irq handler注册。

struct uio_info {
char *name;
char *version;
struct uio_mem mem[MAX_UIO_MAPS];
long irq;
unsigned long irq_flags;
void *priv;
irqreturn_t (*handler)(int irq, struct uio_info *dev_info);
int (*mmap)(struct uio_info *info, struct vm_area_struct *vma);
int (*open)(struct uio_info *info, struct inode *inode);
int (*release)(struct uio_info *info, struct inode *inode);
/* Internal stuff omitted */
};

name: 设备名称
version: 驱动版本
irq 中断号
irq_flags 中断一些标志信息
open , release分别为文件的对应操作函数
handler 为终端操作函数

struct uio_mem {

unsigned long addr;

unsigned long size;

int memtype;

void __iomem *internal_addr;

/* ... */
};

uio_info 的mmap函数将uio_mem 对应的内核，或者设备的内存信息映射到用户态内存空间。这样，内核和用户态就能够进行数据交互。

以上结构是一个驱动程序的信息， 使用者需要使用如下函数注册/注销。(如果是pci设备，还需要自行注册pci设备).
int uio_register_device(struct device *parent, struct uio_info *info);
void uio_unregister_device(struct uio_info *info);

目前这个patch还处于讨论阶段,并且这种设备只是一个字符设备，还不能作为块设备，网络设备的驱动程序。但是Andrew Morton提到把驱动程序放到用户态这个方法对gpl来说并不是一个非常好的办法，应该鼓励内核的开源代码，而不是用户态的闭源代码。目前，该方案还处于讨论中。

读取数据方式

(1)贯穿读出式(Look Through)

cpu->cache->dram串联

(2)旁路读出式(Look Aside)
cache , dram并级，同时和cpu链接

数据写回方式

(1)写穿式(Write Through)
写dram ,写cache,同时写入

(2)回写式(Copy Back)

cpu只写cache , cache主动回写dram . 可能出现Cache中的数据得到更新而主存中的数据不变(数据陈旧)的情况。Cache 中设一标志地址及数据陈旧的信息，只有当Cache中的数据被再次更改时，才将原更新的数据写入主存相应的单元中，然后再接受再次更新的数据。这样保证了Cache和主存中的数据不致产生冲突。

参考: PC系统高速缓冲存储器Cache的原理,设计及实现 ,thanks.

待续 : linux如何使用cache

cpu-cache
1. cache是sram . 不需要动态刷新.因此速度快.
2. cpu,cache,外部dram之间关系。系统结构上存在两种。
a: cpu <-> cache <-> dram
b: cpu -- cache
| |
| |
--- dram
3. Cache在计算机存储系统中没有编配固定的地址 , 因此需要cam( Content Addressed Memory) .
4. cache中每个set和内存的对应关系有三种:
完全相联法 : 即内存中的数据可以存储在任何Cache框架中
直接映象法: 直接映象中内存会将数据存入的Cache框架地址“记住”，以后再次存储时就只能使用该框架
路组相联法: 先将Cache分成不同的组，每个组中放入不同的框架。内存数据的存储对于组来说是固定的. 而每个框架中的行又按照完全相联的方法。

待续。

* EXAMPLE
*
* int pos;
* struct ts_config *conf;
* struct ts_state state;
* const char *pattern = "chicken";
* const char *example = "We dance the funky chicken";
*
* conf = textsearch_prepare("kmp", pattern, strlen(pattern),
* GFP_KERNEL, TS_AUTOLOAD);
* if (IS_ERR(conf)) {
* err = PTR_ERR(conf);
* goto errout;
* }
*
* pos = textsearch_find_continuous(conf, &state, example, strlen(example));
* if (pos != UINT_MAX)
* panic("Oh my god, dancing chickens at %d\n", pos);
*
* textsearch_destroy(conf);
*

解析:
pattern是要查找的关键字
example是被查找的字符串

textsearch_prepare函数中的"kmp"是一种字符串匹配算法，linux还支持bm , fsm字符串匹配算法。
在每个关键字用于匹配前，都需要调用textsearch_prepare作一些初始化工作。真正的匹配动作在textsearch_find_continuous函数中完成。textsearch_destroy是对textsearch_prepare的反向作用。

这个库用起来很简单，但是里面确实好几套复杂的字符匹配算法.
在netfilter的x_tables中，就基于该库实现字符串匹配。

另外 skb_find_text函数也是基于该库的，并且是该库的第一个用户。

今天一个同事问我，br设备的mac地址到底是如何分配的。这里分析一下：

br_if.c

/* called under bridge lock */
int br_add_if(struct net_bridge *br, struct net_device *dev)
{
struct net_bridge_port *p;

if (dev->br_port != NULL)
return -EBUSY;

if (dev->flags & IFF_LOOPBACK || dev->type != ARPHRD_ETHER)
return -EINVAL;

if (dev->hard_start_xmit == br_dev_xmit)
return -ELOOP;

dev_hold(dev);
if ((p = new_nbp(br, dev)) == NULL) {
spin_unlock_bh(&br->lock);
dev_put(dev);
return -EXFULL;
}

dev_set_promiscuity(dev, 1);

br_stp_recalculate_bridge_id(br);

以前自己写的都是很简单功能组合而成的makefile , 稍微复杂一点的也都是找一个modify一下,很多makefile的高级功能都没有用起来。今天上网看见徐海兵http://xhbdahai.cublog.cn/花了近一年的时间将gnu make的info文档进行了翻译，真是佩服.

博客开播