內核版本：3.4.39

Linux路由子系統(tǒng)代碼量雖說不是很多，但是難度還是有的，最近在分析路由子系統(tǒng)這一塊，對它的框架有了基本的了解，如果要想掌握的話估計還得再花點時間閱讀代碼,先把框架記錄下來。路由子系統(tǒng)可以劃分為三個子部分，路由緩存，路由策略和路由表，前兩者已經(jīng)總結過了，今天再總結下路由表。路由表和其它模塊類似，都有初始化、添加、刪除、查詢等操作，要說區(qū)別吧，可能是數(shù)據(jù)結構組織不一樣，不同的數(shù)據(jù)結構需要不同的算法。

看《深入理解Linux網(wǎng)絡技術內幕》這本書路由子模塊這一部分，它介紹的路由表是基于hash表來組織，但是新版本的內核這一塊已經(jīng)改成lpc-trie樹來組織，lpc-trie樹，網(wǎng)上簡稱字典樹，lpc表示path compression(路徑壓縮), level compression(平面壓縮),路由表的添加、刪除、查找都是基于該樹實現(xiàn)，具體的實現(xiàn)還是蠻復雜的，先看下它的組織圖：

上圖左邊部分fib_table_hash就表示路由表hash數(shù)組，hash值就是路由表ID，每個路由表都由一個fib_table結構體表示，這個結構體尾部存放一個占位指針，用來指向路由trie樹，樹種由很多中間節(jié)點和葉子節(jié)點，中間節(jié)點的結構體為tnode，葉子節(jié)點為leaf, 無論是中間節(jié)點還是葉子節(jié)點，都含有一個key值，該值即為ipv4地址，同一條路徑上的節(jié)點擁有相同的前綴，比如1.1.1.1和1.1.1.2，leaf_info包含了子網(wǎng)掩碼長度，fib_alias包含了路由項里面的tos等信息，fib_alias指向fib_info，這里面也包含了路由信息，fib_nh用來保存下一跳網(wǎng)關信息，可以看到，一個路由項由多個數(shù)據(jù)結構組成，之所以用這么多結構體而不是用一個超大的結構體是因為路由里面很多信息是可以共用的，比如說相同的下一跳等等，考慮到大型骨干路由器路由表項可以達到數(shù)萬到數(shù)以百萬，如果每個路由項都要一個大結構體的話，估計內存有點緊張，不如將路由項分割成多個塊，相同的塊可以共享，有一點需要注意，每個路由項都有一個唯一的fib_alias結構體。

路由表初始化流程就是申請緩存、注冊netlink消息處理函數(shù)：

路由初始化主要函數(shù)是ip_fib_init():

void __init ip_fib_init(void) {//注冊netlink路由添加、刪除和dump命令處理函數(shù)rtnl_register(PF_INET, RTM_NEWROUTE, inet_rtm_newroute, NULL, NULL);rtnl_register(PF_INET, RTM_DELROUTE, inet_rtm_delroute, NULL, NULL);rtnl_register(PF_INET, RTM_GETROUTE, NULL, inet_dump_fib, NULL);//初始化路由表和路由緩存register_pernet_subsys(&fib_net_ops);//注冊通知鏈處理函數(shù)，監(jiān)聽系統(tǒng)其它模塊信息register_netdevice_notifier(&fib_netdev_notifier);register_inetaddr_notifier(&fib_inetaddr_notifier);//初始化路由用到的緩存池fib_trie_init(); }

當使用ip route add添加路由時會通過netlink將信息下發(fā)下來，然后調用路由系統(tǒng)注冊的netlink處理函數(shù)，這里是inet_rtm_newroute,該函數(shù)即對下發(fā)參數(shù)進行合理性檢查，檢查通過則添加到對應的trie路由樹中，沒指定路由表id的話，默認添加到main表。

fib_net_ops是個函數(shù)集，在子系統(tǒng)啟動的過程中會被調用：

static struct pernet_operations fib_net_ops = {.init = fib_net_init,.exit = fib_net_exit, };

fib_net_init是啟動過程中的處理函數(shù)，主要申請路由表緩存：

static int __net_init fib_net_init(struct net *net) {int error;//初始化路由緩存和策略error = ip_fib_net_init(net);if (error < 0)goto out;//創(chuàng)建netlinkerror = nl_fib_lookup_init(net);if (error < 0)goto out_nlfl;//初始化proc文件error = fib_proc_init(net);if (error < 0)goto out_proc; out:return error;out_proc:nl_fib_lookup_exit(net); out_nlfl:ip_fib_net_exit(net);goto out; }

?路由表緩存的申請是ip_fib_net_init函數(shù)：

//創(chuàng)建路由表緩存和默認策略或者默認路由表 static int __net_init ip_fib_net_init(struct net *net) {int err;size_t size = sizeof(struct hlist_head) * FIB_TABLE_HASHSZ;/* Avoid false sharing : Use at least a full cache line */size = max_t(size_t, size, L1_CACHE_BYTES);//創(chuàng)建路由表緩存，net->ipv4.fib_table_hash = kzalloc(size, GFP_KERNEL);if (net->ipv4.fib_table_hash == NULL)return -ENOMEM;//初始化策略路由和路由表err = fib4_rules_init(net);if (err < 0)goto fail;return 0;fail:kfree(net->ipv4.fib_table_hash);return err; }

上述就是路由表初始化的過程

看下路由表是怎么添加的，一般情況下應用層添加路由有兩種手段，一種是使用ip route添加，另一種是使用route添加，雖然都是添加路由，但是它倆和路由系統(tǒng)通信機制不一樣，前者使用netlink,后者使用ioctl。看下ip route的添加，當調用ip route命令的時候，該命令會將參數(shù)通過netlink傳遞給內核的netlink模塊，然后調用相應的事件處理函數(shù)，添加的時候調用的是inet_rtm_newroute：

//添加路由 static int inet_rtm_newroute(struct sk_buff *skb, struct nlmsghdr *nlh, void *arg) {struct net *net = sock_net(skb->sk);struct fib_config cfg;struct fib_table *tb;int err;//將用戶層配置信息轉換成fib_config內核可識別的信息err = rtm_to_fib_config(net, skb, nlh, &cfg);if (err < 0)goto errout;//如果指定ID的路由表存在則返回該表，不存在則新建tb = fib_new_table(net, cfg.fc_table);if (tb == NULL) {err = -ENOBUFS;goto errout;}//插入路由err = fib_table_insert(tb, &cfg); errout:return err; }

該函數(shù)首先是將應用層下發(fā)的信息轉換成一個標準的配置結構體里面，然后檢查指定的路由表是否存在，最終調用fib_table_insert來添加路由。

?ioctl添加基本上和netlink相同，除了通信機制的不同，但是對于路由表的操作都是相同的接口：

int ip_rt_ioctl(struct net *net, unsigned int cmd, void __user *arg) {struct fib_config cfg;struct rtentry rt;int err;switch (cmd) {//添加路由case SIOCADDRT: /* Add a route *///刪除路由case SIOCDELRT: /* Delete a route */if (!capable(CAP_NET_ADMIN))return -EPERM;//復制應用層數(shù)據(jù)if (copy_from_user(&rt, arg, sizeof(rt)))return -EFAULT;rtnl_lock();//將應用層數(shù)據(jù)轉換成路由子系統(tǒng)可識別的結構體err = rtentry_to_fib_config(net, cmd, &rt, &cfg);if (err == 0) {struct fib_table *tb;if (cmd == SIOCDELRT) {//刪除操作tb = fib_get_table(net, cfg.fc_table);if (tb)err = fib_table_delete(tb, &cfg);elseerr = -ESRCH;} else {//添加操作tb = fib_new_table(net, cfg.fc_table);if (tb)err = fib_table_insert(tb, &cfg);elseerr = -ENOBUFS;}/* allocated by rtentry_to_fib_config() */kfree(cfg.fc_mx);}rtnl_unlock();return err;}return -EINVAL; }

?可以看到添加操作都是調用fib_table_insert操作，該操作就是對trie路由樹進行添加和刪除處理。

初始化和配置看完了，看下查詢是怎么回事。

系統(tǒng)查詢路由通常由兩個地方，一個是收到報文的時候，另一個是發(fā)送報文的時候。?

當然查找路由不一定非要查詢路由表，首先是查找路由緩存，沒有命中的話則查詢策略路由，根據(jù)策略路由動作再來查詢路由表

從上圖可以看到，收發(fā)報文最終都是調用fib_table_lookup函數(shù)來查找路由表，這個函數(shù)就是在trie樹中查找匹配的路由項。查找流程還是蠻復雜的，應該說關于trie樹的操作都是有點難度，無論是插入還是查詢，這一塊我目前還沒有完全搞清楚，待后續(xù)有足夠的實力再來講一下trie樹的操作。有興趣的同學可以去參考下trie樹的一篇論文，路由表的實現(xiàn)是參考該論文的，鏈接放在參考目錄里。

?

參考目錄：

1. 《Linux Kernel Networking - ?Implementation and Theory》

2. 《深入理解Linux網(wǎng)絡技術內幕》

3.? 《Implementing a dynamic compressed trie》? ?https://pdfs.semanticscholar.org/e880/05c8801983758917bf6e647da97f1027c86b.pdf

?

總結

以上是生活随笔為你收集整理的tcp/ip 协议栈Linux内核源码分析八 路由子系统分析三 路由表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。