以前从来没有看过netfilter的代码。只是在几年前，曾经有个同事做过一个关于iptable的ppt。

当时，也没有搞明白，只是觉得iptable的命令繁杂的很。

现在，只给我这么短的时间，让我搞这个，感觉真是叫赶鸭子上架。

没办法，只能硬着头皮做起来。不过，动起手来发现 其实没有想象那么困难。

netfilter部分的代码，结构还是蛮清晰的。

一般来讲，我们用netfilter做两部分的工作，一个是 filter 一个是NAT。

filter 就是根据包的规则做过滤，像防火墙啦，负载或者流量控制啦。

NAT 就是地址转换。（实际上NAT是属于netfilter下面的 conntrack模块的一部分，但是NAT更有名一些啦）

netfilter做这个工作的方法就是在 5个点加钩子函数，于是，我们会看到每次提到netfilter都会看到的一幅图：

5个点分别是：

LOCAL_IN

LOCAL_OUT

PRE_ROUTING

FORWARD

POST_ROUTING

通过函数 nf_register_hook 就可以把注册一个处理函数到这5个点上的其中一个。

nf_register_hook函数的参数是这样一个结构：

struct nf_hook_ops

{

struct list_head list;  //将该结构插入到一个双向链表中

nf_hookfn *hook; //钩子函数

struct module *owner;

int pf;

int hooknum;   //代表插入到上述5个点的哪一个

int priority;  //优先级，插入到什么位置

};

优先级是这么定义的

enum nf_ip_hook_priorities {

NF_IP_PRI_FIRST = INT_MIN,

NF_IP_PRI_CONNTRACK_DEFRAG = -400,

NF_IP_PRI_RAW = -300,

NF_IP_PRI_SELINUX_FIRST = -225,

NF_IP_PRI_CONNTRACK = -200,

NF_IP_PRI_BRIDGE_SABOTAGE_FORWARD = -175,

NF_IP_PRI_MANGLE = -150,

NF_IP_PRI_NAT_DST = -100,

NF_IP_PRI_BRIDGE_SABOTAGE_LOCAL_OUT = -50,

NF_IP_PRI_FILTER = 0,

NF_IP_PRI_NAT_SRC = 100,

NF_IP_PRI_SELINUX_LAST = 225,

NF_IP_PRI_CONNTRACK_HELPER = INT_MAX - 2,

NF_IP_PRI_NAT_SEQ_ADJUST = INT_MAX - 1,

NF_IP_PRI_CONNTRACK_CONFIRM = INT_MAX,

NF_IP_PRI_LAST = INT_MAX,

};

当每次调用 nf_register_hook 注册一个 nf_hook_ops 到一个点（hooknum）上，

每个点都是一个双向链表，nf_register_hook会把nf_hook_ops 按照优先级

插入到相应的位置上。所以，在iptable里面把这5个点 叫做5个chain。

在filter，mangle 和nat中， nf_hook_ops里面的钩子函数, 又会去调用一个函数 ipt_do_table

相应的table里面包含很多规则，所以，将之称为table。

chain和table这两个名词，在我看iptable的时候，一度搞晕了。

其实看看源码就知道怎么回事了，非常清晰。

每个hook函数返回值为：

NF_ACCEPT: 继续按正常的协议栈流程处理。

NF_DROP: 丢弃包，中止协议栈的流程。

NF_STOLEN: 这个包已被缓存，中止协议栈的流程。

NF_QUEUE: 把包放到队列中(通常会把包转发到用户空间处理)。

NF_REPEAT: 再此调用这个钩子函数。

另外，要注意一个是 抛开mangle的部分不说，其实每条包的经过路径都是这样一个过程：

CONNTRACK -> DNAT -> FILTER -> SNAT -> CONNTRACK

上面是 netfilter总体结构的一个介绍，下次会重点介绍一下 conntrack部分

因为时间仓促可能有的东西理解的不正确，如果高手看到请指正，谢谢。

于是，看了看相关代码。

不过，一直没有找到 独立的项目，只得从 busybox 项目中， 把menuconfig的部分分离出来。

形成一个独立的小项目，以便移植到其他需要类似功能的项目中去。

有兴趣的朋友可以从 google code 的svn上 下载。

这是一个非常简单的menuconfig示例。

只需要执行 make menuconfig

进入菜单，选择相关项目，保存，就会输出两个项目：

.config 这个文件通常可以用于MAKEFILE处理用。

include/autoconf.h 这个可以直接在 c 代码里面使用。

理论上，这个配置还支持

make xconfig

make config

make gconfig

make oldconfig

make defconfig

等等，不过，我没有测试过。

回头我会简单介绍一下，代码的处理过程，和脚本的语法。

谢谢关注

意外发现一个比较好玩的东西 Protothreads

这是个什么东西呢？

文档上说，这是一个极轻量级的无栈线程库。

简单的说，就是在一个死循环 while(1){} 里面跑多个线程，但是，又不必为每个线程都分配一个栈。

因为为每个线程都分配一个栈空间还要分配一个数据结构，太耗费内存了。

所以，它特别适合在内存受限的嵌入式系统里面用。

比如，一个小嵌入式系统，要支持网络协议，还要支持客户的命令，而根本就没有一个操作系统。

你就可以用 Protothreads 来做一个简单的线程调度。

就好像有了个小操作系统。而其代价又是如此之小。不单没有什么调度算法的cpu开销。

内存方面为每个线程也只需要多花两个字节。

还支持信号量操作，而且不用汇编，只用c语言和一些宏定义。

哇，简直太幸福啦！

这么酷的玩意是怎么搞的呢？

其实，说起来也不麻烦，他提供了一些宏，我读了一些，展开来大致就相当于下面这种形式：

while(1){

switch(s) {

case 0:...

case x:...

case y: ...

}

}

从下面几个宏的定义就能看出来了：

#define     LC_INIT(s)   s = 0;
#define     LC_RESUME(s)   switch(s) { case 0:
#define     LC_SET(s)   s = __LINE__; case __LINE__:
#define     LC_END(s)   }   

不过，这样做显然也是有一些代价的，

第一，使用局部变量要极为小心，（文档建议不要用）

很简单，没有栈啊，局部变量放哪里（这个解释不严密，具体看看实现就清楚了）？

第二，当调用函数时，没多调用一层就要多加一个变量，记录执行到这个函数的位置。

以便下次进入时，能找到合适的位置。

不过，不管怎么讲，这还是很好玩的一个“线程”库，如果手上碰巧碰到一个内存极少的硬件可以用下。

如果需要内存不小于512就要根据相应算法找到所需的bin。查找空闲内存块。因为这里的内存块大小并不相同，所以要比较大小。如果大于所需内存太多（多过一个最小块的大小）就不能用了。

如果上面步骤没有找到内存，就到last_remainder里面去找，如果last_remainder里面的够大。就在上面分配。
如果还没有找到就全局搜索，寻找 best fitting chunk。这时还没有找到的话，就在top上面分配，如果top上面的大小不够，则调用malloc_extend_top函数向系统申请更多的内存扩充top。如果还申请不到足够的内存，就只能返回空指针了。

- free
free的算法比较简单，当free一块内存时，就把这个malloc_chunk块挂到相应的bin中，不过在挂之前，要先看看邻接的内存块是否空闲，如果空闲则正好合并成大块，这样可以减少内存碎片的问题。
另外，如果当前释放的内存被合并到top上面，会检查一下top有多大，如果非常大了（uboot定义为128k），就通过函数malloc_trim还给系统。

- malloc_extend_top

malloc本身并没有内存，所有的内存都是通过malloc_extend_top函数分配给top, 然后再给malloc函数去分配的。所以，本身malloc_extend_top函数很简单，不过要注意几个事情，一个是向内存申请通常是以一页（4k)为单位申请；另外，每次向系统申请的内存通常来说应当连续，如果不连续说明还有别的程序再想系统申请内存，这时不能把分到的内存直接扩充到top上。

好了，最近看的dlmalloc的部分基本上写完了。

其实，代码本身比较细，很多东西一下子看不清楚，所以难免有理解错的地方。

写下来有个好处，回头如果需要不必重新看起。

读了dlmalloc后，自己在其基础上面写了个非常简单的malloc。

实现一个简单的malloc功能：

只有一个链表，所有free的内存块都挂在上面，

分配的时候，先从这个链表里面找 first-fit，就是只要够大就用，如果非常大就分割一下。

如果链表不够，就调用malloc_extend_top申请新内存。

跑了一下感觉还不错，其实在uboot这种简单应用场景下面这样简单的东西也够用啦。

dlmalloc有两个重要的数据结构，一个是 chunk, 另一个是bin。

chunk就是分配内存的数据块，定义如下：
struct malloc_chunk
{
  INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
  INTERNAL_SIZE_T size;      /* Size in bytes, including overhead. */
  struct malloc_chunk* fd;   /* double links -- used only if free. */
  struct malloc_chunk* bk;
};
这是malloc_chunk的数据结构，不过要注意，一块malloc_chunk可不是只有这么大。
一块malloc_chunk的大小是8byte的倍数。
举个例子：
如果申请一块4byte的内存，只是实际会分配出16byte。
其中，头8byte存放 prev_size和size，然后是4个byte的内存，最后还有4个byte是为了8byte对其的pad。
如下图：

=================
   prev_size [4byte]
   size         [4byte]
  -------------------
   data        [4byte]
  -------------------
   pad         [4byte]
=================

这样我们可以看到，fd和bk在分配出去的时候并不存在，只是在空闲时可用，构成一个双向链表。
当malloc_chunk被free时，就会插入一个双向链表中，留作以后分配，用得就是fd和bk。

而prev_size和size还有一个用处，就是通过这两个元素，可以找到与当前malloc_chunk块相邻的
的malloc_chunk块。
比如：有指针p指向一个malloc_chunk块： struct malloc_chunk * p = ...
这是通过 (struct malloc_chunk *)((char*)(p) + p->size) 和
(struct malloc_chunk *)((char*)(p) - p->prev_size)
就可以找到相邻内存。
这在合并内存的时候非常有用。

另外，要注意的是 size的最低一位是标记是否被用的状态。
因为malloc_chunk的大小是8byte的倍数。所以，低3位都为零，于是最低一位就当作一个标记位。
标记是否被分配。不过，奇怪的是，这个标记是将相邻前一块是否被用 （PREV_INUSE）而不是当前块。
这点一直让我蛮费解的。

关于chunk，这里一篇文章介绍的蛮详细的，还有些配图，很不错。

www.vtzone.org里面还有挺多介绍dlmalloc和内存管理方面的文章，值得读读。

chunk介绍完，就该介绍bin了。
所谓的bin其实就是一些双向链表，在初始化的时候，申请了128个双向链表。用以存放空闲的malloc_chunk。
这样，就可以快速的寻找的所需要的malloc_chunk。其中，前64个bin存放的是固定尺寸
（16byte-512byte以8byte递增）
的malloc_chunk。之后，有相应的映射算法。这是因为小于512byte的分配更频繁，这样做会有更好的效率。
在分配时，以最小块优先，最佳适合的顺序搜索可用的块。

其中注意两个特殊的bin是top和last_remainder。
top存放的是最新从系统获得到的内存，分配时先在其他链表中寻找，如果都没有才在top上面分配，
如果top的内存也不够分了，就从系统申请新的内存，还是放在top上面供分配。

last_remainder是指上次被切分的malloc_chunk，这大概是根据局部化特性，来提高分配的效率。

这样数据结构就大致介绍这么多，下一篇讲讲处理流程

这是作者写的说明 (中文)

u-boot用dlmalloc的版本是 2.6.6，应该算是比较老的吧，最新的是2.8.3。不过，对于u-boot来讲已经足够了。本身没有多少内存好分配的。也用不到mmap。

对于u-boot来说，就是先设定一块内存空间留给malloc分配。malloc分配时，先回寻找当前空闲的块。如果找不到就通过函数malloc_extend_top调用一个宏：MORECORE(直接调用sbrk函数，sbrk函数是unix的标准函数，在uboot里面自己写了一个非常简单的sbrk)，从系统（就是uboot了）申请一块内存。这时，uboot就从前面预留的内存空间中分配一块给malloc。

free的部分比较简单，当一块内存free的时候，先看看能不能跟前后空闲的内存块一起合并，这样就能避免内存的碎片问题。然后，把释放的内存按照大小插入的相应的链表中，以供下次分配用。

代码虽然不算很多，但是却挺不容易读懂的。
努力读了读，大致明白了基本的流程。

打算分几次记录一下。

下一篇

start.S， cache.S 两个文件基本可以参照现有文件，进行相应修改。

另外，配置ddr controller, flash初始化，串口都是必要工作。

还有就是pci和网口的驱动代码，还有环境变量的访问。

配置方面：
  要添加相应硬件的头文件xxx.h在 include/configs目录下， 该文件内容比较多，尽量参照意义已有类似硬件的模板。
 
Makefile中加入编译目标：
  xxx_config    :    unconfig
    @$(MKCONFIG) $(@:_config=) ARCH CPU BOARD VENDOR SOC

目录组织与硬件配置的关系可以参考如下：
   
header_file        ARCH    CPU            BOARD        VENDOR    SOC
smdk2410         arm     arm920t     smdk2410     NULL     s3c24x0

LIBBOARD = board/$(BOARDDIR)/lib$(BOARD).a
board/smdk2410/libsmdk2410.a

LIBS += cpu/$(CPU)/lib$(CPU).a
cpu/arm920t/libarm920t.a

LIBS += cpu/$(CPU)/$(SOC)/lib$(SOC).a
cpu/arm920t/s3c24x0/libs3c24x0.a

LIBS += lib_$(ARCH)/lib$(ARCH).a
lib_arm/libarm.a

如果，我们需要自己添加一个新命令，只要有实现函数 do_xxx，和命令声明U_BOOT_CMD(xxx, ...) 就可以了。

下面，我们介绍一下命令的配置方式。注意：最新的uboot命令配置方法发生变化，与以前不同。

首先，在头文件 smdk2410.h (该文件前面文章有介绍) 包含了所需的命令头文件
#include <config_cmd_default.h>

在 config_cmd_default.h 中定义了，所需要用到的命令，如：
#define CONFIG_CMD_MEMORY    /* md mm nm mw cp cmp crc base loop mtest */
（所以，autoconf.mk里，就会有 CONFIG_CMD_MEMORY=y ）

而在common/Makefile 下，有这样的定义：
COBJS-$(CONFIG_CMD_MEMORY) += cmd_mem.o

这样，当config_cmd_default.h里有了相应定义，就会把相应实现进行编译。
就可以获得相关命令的支持了。