路由表（Fib Table）
数据结构：
在整个策略性路由的框架里，路由表是最重要的的数据结构，我们在上面以及对路由表的概念和结构进行了清楚的说明。Linux里通过下面这些主要的数据结构进行实现的。
| 主要的数据结构 |
作用 |
位置 |
| struct fib_table |
路由表 |
ip_fib.h 116 |
| struct fn_hash |
路由表的哈希数据 |
fib_hash.c 104 |
| struct fn_zone |
zone域 |
fib_hash.c 85 |
| struct fib_node |
路由节点 |
fib_hash.c 68 |
| struct fib_info |
路由信息 |
ip_fib.h 57 |
| struct fib_result |
路由结果 |
ip_fib.h 86 |
数据结构之间的主要关系如下。路由表由路由表号以及路由表的操作函数指针还有表数据组成。这里需要注意的是，路由表结构里并不直接定义zone域，而是通过一个数据指针指向fn_hash。只有当zone里有数据才会连接到fn_zone_list里。
系统的所有的路由表由数组变量*fib_tables[RT_TABLE_MAX+1]维护，其中系统定义RT_TABLE_MAX为254，也就是说系统最大的路由表为255张，所有的路由表的操作都是对这个数组进行的。。同时系统还定义了三长路由表*local_table; *main_table。
路由表的操作：
Linux策略路由代码的主要部分是对路由表的操作。对于路由表的操作，物理操作是直观的和易于理解的。对于表的操作不外乎就是添加、删除、更新等的操作。还有一种操作，是所谓的语义操作，语义操作主要是指诸如计算下一条的地址，把节点转换为路由项，寻找指定信息的路由等。
1、物理操作(operation)：
路由表的物理操作主要包括如下这些函数：
| 路由标操作 |
实现函数 |
位置 |
| 新建路由表 |
|
|
| 删除路由表 |
|
|
| 搜索路由 |
fn_hash_lookup |
fib_hash.c 269 |
| 插入路由到路由表 |
fn_hash_insert |
fib_hash.c 341 |
| 删除路由表的路由 |
fn_hash_delete
fn_hash_dump
|
fib_hash.c 433
fib_hash.c 614 |
| 更新路由表的路由 |
fn_hash_flush |
fib_hash.c 729 |
| 显示路由表的路由信息 |
fn_hash_get_info |
fib_hash.c 750 |
| 选择默认路由 |
fn_hash_select_default |
fib_hash.c 842 |
2、语义操作(semantics operation)：
语义操作并不涉及路由表整体框架的理解，而且，函数名也是不言自明的，所以请大家参考fib_semantics.c。
3、接口(front end)
对于路由表接口的理解，关键在于理解那里有
IP
首先是路由表于IP层的接口。路由在目前linux的意义上来说，最主要的还是IP层的路由，所以和IP层的的接口是最主要的接口。和ip层的衔接主要是向IP层提供寻找路由、路由控制、寻找指定ip的接口。
Fil_lookup
ip_rt_ioctl fib_frontend.c 286;" f
ip_dev_find 145 |
Inet
路由表还必须提供配置接口，即用户直接操作路由的接口，例如增加和删除一条路由。当然在策略性路由里，还有规则的添加和删除。
inet_rtm_delroute 351
inet_rtm_newroute 366
inet_check_attr 335 |
proc
在/proc/net/route里显示路由信息。
fib_get_procinfo
4、网络设备（net dev event）
路由是和硬件关联的，当网络设备启动或关闭的时候，必须通知路由表的管理程序，更新路由表的信息。
fib_disable_ip 567
fib_inetaddr_event 575
fib_netdev_event |
5、内部维护（ magic）
上面我们提到，本地路由表（local table）的维护是由系统自动进行的。也就是说当用户为硬件设置IP地址等的时候，系统自动在本地路由表里添加本地接口地址以及广播地址。
fib_magic 417
fib_add_ifaddr 459
fib_del_ifaddr 498 |
Rule
1、数据结构
规则在fib_rules.c的52行里定义为 struct fib_rule。而RPDB里所有的路由是保存在101行的变量fib_rules里的，注意这个变量很关键，它掌管着所有的规则，规则的添加和删除都是对这个变量进行的。
2、系统定义规则：
fib_rules被定义以后被赋予了三条默认的规则：默认规则，本地规则以及主规则。
u 本地规则local_rule
94 static struct fib_rule local_rule = {
r_next: &main_rule, /*下一条规则是主规则*/
r_clntref: ATOMIC_INIT(2),
r_table: RT_TABLE_LOCAL, /*指向本地路由表*/
r_action: RTN_UNICAST, /*动作是返回路由*/
};
u 主规则main_rule
86 static struct fib_rule main_rule = {
r_next: &default_rule,/*下一条规则是默认规则*/
r_clntref: ATOMIC_INIT(2),
r_preference: 0x7FFE, /*默认规则的优先级32766*/
r_table: RT_TABLE_MAIN, /*指向主路由表*/
r_action: RTN_UNICAST, /*动作是返回路由*/
};
u 默认规则default rule
79 static struct fib_rule default_rule = {
r_clntref: ATOMIC_INIT(2),
r_preference: 0x7FFF,/*默认规则的优先级32767*/
r_table: RT_TABLE_DEFAULT,/*指默认路由表*/
r_action: RTN_UNICAST,/*动作是返回路由*/
}; |
规则链的链头指向本地规则。
RPDB的中心函数fib_lookup
现在到了讨论RPDB的实现的的中心函数fib_lookup了。RPDB通过提供接口函数fib_lookup，作为寻找路由的入口点，在这里有必要详细讨论这个函数，下面是源代码：，
310 int fib_lookup(const struct rt_key *key, struct fib_result *res)
311 {
312 int err;
313 struct fib_rule *r, *policy;
314 struct fib_table *tb;
315
316 u32 daddr = key->dst;
317 u32 saddr = key->src;
318
321 read_lock(&fib_rules_lock);
322 for (r = fib_rules; r; r=r->r_next) {/*扫描规则链fib_rules里的每一条规则直到匹配为止*/
323 if (((saddr^r->r_src) & r->r_srcmask) ||
324 ((daddr^r->r_dst) & r->r_dstmask) ||
325 #ifdef CONFIG_IP_ROUTE_TOS
326 (r->r_tos && r->r_tos != key->tos) ||
327 #endif
328 #ifdef CONFIG_IP_ROUTE_FWMARK
329 (r->r_fwmark && r->r_fwmark != key->fwmark) ||
330 #endif
331 (r->r_ifindex && r->r_ifindex != key->iif))
332 continue;/*以上为判断规则是否匹配，如果不匹配则扫描下一条规则，否则继续*/
335 switch (r->r_action) {/*好了，开始处理动作了*/
336 case RTN_UNICAST:/*没有设置动作*/
337 case RTN_NAT: /*动作nat ADDRESS*/
338 policy = r;
339 break;
340 case RTN_UNREACHABLE: /*动作unreachable*/
341 read_unlock(&fib_rules_lock);
342 return -ENETUNREACH;
343 default:
344 case RTN_BLACKHOLE:/* 动作reject */
345 read_unlock(&fib_rules_lock);
346 return -EINVAL;
347 case RTN_PROHIBIT:/* 动作prohibit */
348 read_unlock(&fib_rules_lock);
349 return -EACCES;
350 }
351 /*选择路由表*/
352 if ((tb = fib_get_table(r->r_table)) == NULL)
353 continue;
/*在路由表里寻找指定的路由*/
354 err = tb->tb_lookup(tb, key, res);
355 if (err == 0) {/*命中目标*/
356 res->r = policy;
357 if (policy)
358 atomic_inc(&policy->r_clntref);
359 read_unlock(&fib_rules_lock);
360 return 0;
361 }
362 if (err < 0 && err != -EAGAIN) {/*路由失败*/
363 read_unlock(&fib_rules_lock);
364 return err;
365 }
366 }
368 read_unlock(&fib_rules_lock);
369 return -ENETUNREACH;
370 } |
上面的这段代码的思路是非常的清晰的。首先程序从优先级高到低扫描所有的规则，如果规则匹配，处理该规则的动作。如果是普通的路由寻址或者是nat地址转换的换，首先从规则得到路由表，然后对该路由表进行操作。这样RPDB终于清晰的显现出来了。
