3.6版本以前的路由緩存
緩存無處不在。現代計算機系統中，Cache是CPU與記憶體間存在一種容量較小但速度很高的存儲器，用來存放
CPU
剛使用過或最近使用的資料。路由緩存就是基于這種思想的軟體實作。核心查詢FIB前，固定先查詢cache中的記錄，如果cache命中(hit)，那就直接用就好了，不必查詢FIB。如果沒有命中(miss), 就回過頭來查詢FIB，最終将結果儲存到cache，以便下次不再需要需要查詢FIB。
緩存是精确比對的, 每一條緩存表項記錄了比對的源位址和目的位址、接收發送的
dev
，以及與核心鄰居系統(L2層)的聯系(
negghbour
)
FIB
中存儲的也就是路由資訊，它常常是範圍比對的，比如像
ip route 1.2.3.0/24 dev eth0
這樣的網段路由
看上去的确可能能提高性能! 隻要cache命中率足夠高。要獲得高的cache命中率有以下兩個途徑：1. 存儲更多的表項; 2.存儲更容易命中的表項
緩存中存放的表項越多，那麼目标封包與表項比對的可能性越大。但是cache又不能無限制地增大，cache本身占用記憶體是一回事，更重要的是越多的表項會導緻查詢cache本身變慢。使用cache的目的是為了加速，如果不能加速，那就沒用了！
核心為了避免cache表項過多，核心還會在一定時機下清除過期的表項。有兩個這樣的時機，其一是添加新的表項時，如果沖突鍊的表項過多，就删除一條已有的表項；其二是核心會啟動一個專門的定時器周期性地老化一些表項.
獲得更高的cache命中率的第二個途徑是存儲更容易命中的表項，什麼是更容易命中的呢？ 那就是真正有效的封包。遺憾的是，核心一點也不聰明：隻要輸入路由系統的封包不來離譜，它就會生成新的緩存表項。壞人正好可以利用這一點，不停地向主機發送垃圾封包，核心是以會不停地重新整理cache。這樣每個skb都會先在cache表中進行搜尋，再查詢FIB表，最後再建立新的cache表項，插入到cache表。這個過程中還會涉及為每一個新建立的cache表項綁定鄰居，這又要查詢一次
ARP
表。
要知道，一台主機上的路由表項可能有很多，特别是對于網絡交換裝置，由OSPF**BGP等路由協定動态下發的表項有上萬條是很正常的事。而鄰居節點卻不可能達到這個數量。對于轉發或者本機發送的skb來說，路由系統能幫它們找到下一跳鄰居**就足夠了。
總結起來就是，3.6版本以前的這種路由緩存在skb位址穩定時的确可能提高性能。但這種根據skb内容決定的性能卻是不可預測和不穩定的。
3.6版本以後的下一跳緩存
正如前面所說，3.6版本移除了FIB查找前的路由緩存。這意味着每一個接收發送的skb現在都必須要進行FIB查找了。這樣的好處是現在查找路由的代價變得穩定(consistent)了。
路由緩存完全消失了嗎? 并沒有！在3.6以後的版本, 你還可以在核心代碼中看到dst_entry。這是因為，3.6版本實際上是将FIB查找緩存到了下一跳(fib_nh)結構上，也就是下一跳緩存
········什麼需要緩存下一跳呢？ 我們可以先來看下沒有下一跳緩存的情況。以轉發過程為例，相關的僞代碼如下：
FORWARD:
fib_result = fib_lookup(skb)
dst_entry = alloc_dst_entry(fib_result)
skb->dst = dst_entry;
skb->dst.output(skb)
nexthop = rt_nexthop(skb->dst, ip_hdr(skb)->daddr)
neigh = ipv4_neigh_lookup(dev, nexthop)
dst_neigh_output(neigh,skb)
release_dst_entry(skb->dst) 核心利用FIB查詢的結果申請dst_entry, 并設定到skb上，然後在發送過程中找到下一跳位址，繼而查找到鄰居結構(查詢ARP)，然後鄰居系統将封包發送出去，最後釋放dst_entry。
下一跳緩存的作用就是盡量減少最初和最後的申請釋放dst_entry，它将dst_entry緩存在下一跳結構(fib_nh)上。這和之前的路由緩存有什麼差別嗎？ 很大的差別！之前的路由緩存是以源IP和目的IP為KEY，有千萬種可能性，而現在是和下一跳綁定在一起，一台裝置沒有那麼多下一跳的可能。這就是下一跳緩存的意義！
early demux
early demux
是在skb接收方向的加速方案。如前面所說，在取消了FIB查詢前的路由緩存後，每個skb應該都需要查詢FIB。而early demux是基于一種思想：如果一個skb是本機某個應用程式的套接字需要的，那麼我們可以将路由的結果緩存在核心套接字結構上，這樣下次同樣的封包(四元組)到達後，我們可以在FIB查詢前就将封包送出給上層，也就是提前分流(early demux)。但是 對于非面向連結的socket等 就不友好了！
ip_route_input_slow 分析：
/*
* NOTE. We drop all the packets that has local source
* addresses, because every properly looped back packet
* must have correct destination already attached by output routine.
*
* Such approach solves two big problems:
* 1. Not simplex devices are handled properly.
* 2. IP spoofing attempts are filtered with 100% of guarantee.
* called with rcu_read_lock()
*/
static int ip_route_input_slow(struct sk_buff *skb, __be32 daddr, __be32 saddr,
u8 tos, struct net_device *dev)
{
struct fib_result res;
struct in_device *in_dev = __in_dev_get_rcu(dev);//這裡要使用輸入網絡裝置dev，增加引用計數
struct ip_tunnel_info *tun_info;
struct flowi4 fl4;
unsigned int flags = 0;
u32 itag = 0;
struct rtable *rth;
int err = -EINVAL;
struct net *net = dev_net(dev);
bool do_cache;
/* IP on this device is disabled. */
if (!in_dev)
goto out;
/* Check for the most weird martians, which can be not detected
by fib_lookup.
*/
tun_info = skb_tunnel_info(skb);
if (tun_info && !(tun_info->mode & IP_TUNNEL_INFO_TX))
fl4.flowi4_tun_key.tun_id = tun_info->key.tun_id;
else
fl4.flowi4_tun_key.tun_id = 0;
skb_dst_drop(skb);
if (ipv4_is_multicast(saddr) || ipv4_is_lbcast(saddr))
goto martian_source;
debug_v4route("%s-->begin to slow looking\n",__FUNCTION__);
res.fi = NULL;
res.table = NULL;
if (ipv4_is_lbcast(daddr) || (saddr == 0 && daddr == 0))
goto brd_input;
/* Accept zero addresses only to limited broadcast;
* I even do not know to fix it or not. Waiting for complains :-)
*/
if (ipv4_is_zeronet(saddr))
goto martian_source;
if (ipv4_is_zeronet(daddr))
goto martian_destination;
/* Following code try to avoid calling IN_DEV_NET_ROUTE_LOCALNET(),
* and call it once if daddr or/and saddr are loopback addresses
*/
if (ipv4_is_loopback(daddr)) {
if (!IN_DEV_NET_ROUTE_LOCALNET(in_dev, net))
goto martian_destination;
} else if (ipv4_is_loopback(saddr)) {
if (!IN_DEV_NET_ROUTE_LOCALNET(in_dev, net))
goto martian_source;
}
/*
* Now we are ready to route packet.
*/
fl4.flowi4_oif = 0;
fl4.flowi4_iif = l3mdev_fib_oif_rcu(dev);
fl4.flowi4_mark = skb->mark;
fl4.flowi4_tos = tos;
fl4.flowi4_scope = RT_SCOPE_UNIVERSE;
fl4.flowi4_flags = 0;
fl4.daddr = daddr;
fl4.saddr = saddr;
err = fib_lookup(net, &fl4, &res, 0);
pr_err("dev_name:%s src:%pI4-->dst:%pI4 mark:%d fib_loopup[err%d res.type:%d]\n",
in_dev->dev->name,&saddr, &daddr, skb->mark, err, res.type);
if (err != 0) {
if (!IN_DEV_FORWARD(in_dev))
err = -EHOSTUNREACH;
goto no_route;pr_err
}
// /*根據查找到的路由類型，分類處理 廣播處理*/
if (res.type == RTN_BROADCAST)
goto brd_input;
if (res.type == RTN_LOCAL) {
/*如果是發給本機的包，則驗證原位址是否合法*/
err = fib_validate_source(skb, saddr, daddr, tos,
0, dev, in_dev, &itag);
/*對于RTN_LOCAL類型或者RTN_BROADCAST類型的路由表項，如果反向路由查找失敗，
也認定源位址為非法位址，在函數ip_handle_martian_source中遞增in_martian_src計*/
pr_err("dev_name:%s src:%pI4-->dst:%pI4 mark:%d fib_validate_source[err:%d ]\n",
in_dev->dev->name,&saddr, &daddr, skb->mark, err);
if (err < 0)
goto martian_source;
goto local_input;
}
if (!IN_DEV_FORWARD(in_dev)) {
err = -EHOSTUNREACH;
goto no_route;
}
if (res.type != RTN_UNICAST)
goto martian_destination;
/*當查到的路由類型是指向遠端的主機，把此路由加入cache中*/
err = ip_mkroute_input(skb, &res, &fl4, in_dev, daddr, saddr, tos);
out: return err;
brd_input:/*當目的位址是廣播位址，或查到的路由類型是廣播類型*/
/*封包的目的位址為廣播位址；或者源位址和目的位址同時為全0；
或者fib查詢的結果為RTN_BROADCAST類型路由，如果接收裝置的廣播轉發開關開啟，
有函數ip_mkroute_input建立路由緩存，但是其僅遞增了in_slow_tot計數*/
if (skb->protocol != htons(ETH_P_IP))
goto e_inval;
if (!ipv4_is_zeronet(saddr)) {
err = fib_validate_source(skb, saddr, 0, tos, 0, dev,
in_dev, &itag);
if (err < 0)
goto martian_source;
}
flags |= RTCF_BROADCAST;
res.type = RTN_BROADCAST;
RT_CACHE_STAT_INC(in_brd);
local_input:/*當查找到的路由指向本機時*/
do_cache = false;
if (res.fi) {
if (!itag) {
rth = rcu_dereference(FIB_RES_NH(res).nh_rth_input);
if (rt_cache_valid(rth)) {
skb_dst_set_noref(skb, &rth->dst);
err = 0;
goto out;
}
do_cache = true;
}
}
rth = rt_dst_alloc(net->loopback_dev, flags | RTCF_LOCAL, res.type,
IN_DEV_CONF_GET(in_dev, NOPOLICY), false, do_cache);
/* rth->dst.input= ip_local_deliver; ----->路由查找結束後會調用此函數把封包送給上層處理*/
if (!rth)
goto e_nobufs;
rth->dst.output= ip_rt_bug;
#ifdef CONFIG_IP_ROUTE_CLASSID
rth->dst.tclassid = itag;
#endif
rth->rt_is_input = 1;
if (res.table)
rth->rt_table_id = res.table->tb_id;
RT_CACHE_STAT_INC(in_slow_tot);//統計路由cache配置設定次數
if (res.type == RTN_UNREACHABLE) {// no route
rth->dst.input= ip_error;/*PS：沒有查找到路由的時候也會向緩存中添加一條不可達路由項*/
rth->dst.error= -err;
rth->rt_flags &= ~RTCF_LOCAL;
}
if (do_cache) {//需要執行緩存操作 do_cache ,函數rt_cache_route來實作
if (unlikely(!rt_cache_route(&FIB_RES_NH(res), rth))) {
rth->dst.flags |= DST_NOCACHE;
rt_add_uncached_list(rth);//如果緩存失敗，将路由項添加到uncached_list連結清單
}
}
skb_dst_set(skb, &rth->dst);
err = 0;
goto out;
no_route:
/*沒有查找到路由的時候，向緩存中添加一條不可達路由項*/
//統計fib查詢失敗次數，以及路由下一跳裝置轉發未啟用
RT_CACHE_STAT_INC(in_no_route);
res.type = RTN_UNREACHABLE;
res.fi = NULL;
res.table = NULL;
goto local_input;
/*
*Do not cache martian addresses: they should be logged (RFC1812)如果封包的目的位址為0；或者為回環位址
但是接收裝置不允許回環位址（可通過PROC檔案配置，例如eth0配置檔案：
/proc/sys/net/ipv4/conf/eth0/route_localnet）。
或者，查詢fib表的結果得到的路由類型不等于RTN_BROADCAST、RTN_LOCAL和RTN_UNICAST中的任何一個，
認為此封包的目的位址為非法位址。增加in_martian_dst計數。
*/
martian_destination:
RT_CACHE_STAT_INC(in_martian_dst);
#ifdef CONFIG_IP_ROUTE_VERBOSE
if (IN_DEV_LOG_MARTIANS(in_dev))
net_warn_ratelimited("martian destination %pI4 from %pI4, dev %s\n",
&daddr, &saddr, dev->name);
#endif
e_inval:
err = -EINVAL;
goto out;
e_nobufs:
err = -ENOBUFS;
goto out;
/*在查找路由時，如果封包的源位址為多點傳播位址，或者全F的廣播位址，或者源位址為0。
或者目的位址不是回環位址，但是源位址為回環位址，并且接收裝置沒有開啟接收開關，
認定封包的源位址為非法位址。
對于RTN_LOCAL類型或者RTN_BROADCAST類型的路由表項，如果反向路由查找失敗，
也認定源位址為非法位址，在函數ip_handle_martian_source中遞增in_martian_src計*/
martian_source:
ip_handle_martian_source(dev, in_dev, skb, daddr, saddr);
goto out;
} /* called in rcu_read_lock() section */
static int __mkroute_input(struct sk_buff *skb,
const struct fib_result *res,
struct in_device *in_dev,
__be32 daddr, __be32 saddr, u32 tos)
{
struct fib_nh_exception *fnhe;
struct rtable *rth;
int err;
struct in_device *out_dev;
bool do_cache;
u32 itag = 0;
/* get a working reference to the output device */
out_dev = __in_dev_get_rcu(FIB_RES_DEV(*res));;//擷取輸出封包的網絡裝置
if (!out_dev) {
net_crit_ratelimited("Bug in ip_route_input_slow(). Please report.\n");
return -EINVAL;
}
//路由合法性檢查，在調用該函數前，已經找到一條從saddr->daddr的路由項，
//需要進行判斷daddr->saddr反向路由是否存在，否則認為它是非法的
err = fib_validate_source(skb, saddr, daddr, tos, FIB_RES_OIF(*res),
in_dev->dev, in_dev, &itag);
if (err < 0) {
ip_handle_martian_source(in_dev->dev, in_dev, skb, daddr,
saddr);
goto cleanup;
}
do_cache = res->fi && !itag;
if (out_dev == in_dev && err && IN_DEV_TX_REDIRECTS(out_dev) &&
skb->protocol == htons(ETH_P_IP) &&
(IN_DEV_SHARED_MEDIA(out_dev) ||
inet_addr_onlink(out_dev, saddr, FIB_RES_GW(*res))))
IPCB(skb)->flags |= IPSKB_DOREDIRECT;
if (skb->protocol != htons(ETH_P_IP)) {//如果不是ip 比如arp
/* Not IP (i.e. ARP). Do not create route, if it is
* invalid for proxy arp. DNAT routes are always valid.
*
* Proxy arp feature have been extended to allow, ARP
* replies back to the same interface, to support
* Private VLAN switch technologies. See arp.c.
*/// arp 封包的處理 也會涉及到路由處理
if (out_dev == in_dev &&
IN_DEV_PROXY_ARP_PVLAN(in_dev) == 0) {
err = -EINVAL;
goto cleanup;
}
}
// 查找 fl4->daddr 是否存在 fib_nh_exception
fnhe = find_exception(&FIB_RES_NH(*res), daddr);
if (do_cache) {
if (fnhe) {
rth = rcu_dereference(fnhe->fnhe_rth_input);
if (rth && rth->dst.expires &&
time_after(jiffies, rth->dst.expires)) {//檢驗是否過期等
ip_del_fnhe(&FIB_RES_NH(*res), daddr);
fnhe = NULL;
} else { // 如果有 且沒過期可以使用，直接使用其綁定的路由緩存
goto rt_cache;
}
}
rth = rcu_dereference(FIB_RES_NH(*res).nh_rth_input);
rt_cache:
if (rt_cache_valid(rth)) { // 如果有，直接使用其綁定的路由緩存
skb_dst_set_noref(skb, &rth->dst);
goto out;
}
}
//建立新的路由緩存項
rth = rt_dst_alloc(out_dev->dev, 0, res->type,
IN_DEV_CONF_GET(in_dev, NOPOLICY),
IN_DEV_CONF_GET(out_dev, NOXFRM), do_cache);
if (!rth) {
err = -ENOBUFS;
goto cleanup;
}
rth->rt_is_input = 1;
if (res->table)
rth->rt_table_id = res->table->tb_id;
RT_CACHE_STAT_INC(in_slow_tot);//統計路由cache配置設定次數
//so RT_CACHE_STAT_INC(in_slow_mc) 統計多點傳播路由cache配置設定次數
rth->dst.input = ip_forward;
//對于轉發路由，由函數rt_set_nexthop處理路由緩存
rt_set_nexthop(rth, daddr, res, fnhe, res->fi, res->type, itag);
if (lwtunnel_output_redirect(rth->dst.lwtstate)) {
rth->dst.lwtstate->orig_output = rth->dst.output;
rth->dst.output = lwtunnel_output;
}
if (lwtunnel_input_redirect(rth->dst.lwtstate)) {
rth->dst.lwtstate->orig_input = rth->dst.input;
rth->dst.input = lwtunnel_input;
}
//設定更新skb的dst 路由資訊
skb_dst_set(skb, &rth->dst);
out:
err = 0;
cleanup:
return err;
} 在緩存路由項時，如果緩存成功（cmpxchg），并且原有緩存值不為空，将原有路由緩存值添加到uncached_list鍊
static bool rt_cache_route(struct fib_nh *nh, struct rtable *rt)
{
struct rtable *orig, *prev, **p;
bool ret = true;
if (rt_is_input_route(rt)) {
p = (struct rtable **)&nh->nh_rth_input;
} else {
p = (struct rtable **)raw_cpu_ptr(nh->nh_pcpu_rth_output);
}
orig = *p;
/*在緩存路由項時，如果緩存成功（cmpxchg），并且原有緩存值不為空，并執行釋放操作（有延遲）。
否者，如果緩存操作失敗，傳回錯誤
*/
prev = cmpxchg(p, orig, rt);
if (prev == orig) {
if (orig)
rt_free(orig);
} else
ret = false;
return ret;
} 對于轉發路由，由函數rt_set_nexthop處理路由緩存。
static void rt_set_nexthop(struct rtable *rt, __be32 daddr,
const struct fib_result *res,
struct fib_nh_exception *fnhe,
struct fib_info *fi, u16 type, u32 itag)
{
bool cached = false;
if (fi) {
struct fib_nh *nh = &FIB_RES_NH(*res);
if (nh->nh_gw && nh->nh_scope == RT_SCOPE_LINK) {
rt->rt_gateway = nh->nh_gw;
rt->rt_uses_gateway = 1;
}
dst_init_metrics(&rt->dst, fi->fib_metrics->metrics, true);
if (fi->fib_metrics != &dst_default_metrics) {
rt->dst._metrics |= DST_METRICS_REFCOUNTED;
atomic_inc(&fi->fib_metrics->refcnt);
}
#ifdef CONFIG_IP_ROUTE_CLASSID
rt->dst.tclassid = nh->nh_tclassid;
#endif
rt->dst.lwtstate = lwtstate_get(nh->nh_lwtstate);
/*如果fnhe有值，由函數rt_bind_exception處理，并進行路由緩存；否則，如果do_cache為真，
由之前介紹的函數rt_cache_route進行緩存操作。最後如果路由緩存操作失敗的話，
将路由項連結到uncached_list連結清單上*/
if (unlikely(fnhe))
cached = rt_bind_exception(rt, fnhe, daddr);
else if (!(rt->dst.flags & DST_NOCACHE))
cached = rt_cache_route(nh, rt);
if (unlikely(!cached)) {
/* Routes we intend to cache in nexthop exception or
* FIB nexthop have the DST_NOCACHE bit clear.
* However, if we are unsuccessful at storing this
* route into the cache we really need to set it.
*/
rt->dst.flags |= DST_NOCACHE;
if (!rt->rt_gateway)
rt->rt_gateway = daddr;
rt_add_uncached_list(rt);
}
} else {
//如果fib_info結構變量fi為空（沒有路由緩存位置），不進行路由緩存，直接加入uncached_list連結清單
rt_add_uncached_list(rt);
}
#ifdef CONFIG_IP_ROUTE_CLASSID
#ifdef CONFIG_IP_MULTIPLE_TABLES
set_class_tag(rt, res->tclassid);
#endif
set_class_tag(rt, itag);
#endif
} 在函數rt_bind_exception中，沒有使用rt_cache_route函數中的cmpxchg指令。而是由rcu_dereference和rcu_assign_pointer進行類似的路由緩存操作，之後，如果原有緩存不為空，對其進行釋放。
static bool rt_bind_exception(struct rtable *rt, struct fib_nh_exception *fnhe,
__be32 daddr)
{
bool ret = false;
spin_lock_bh(&fnhe_lock);
/*在函數rt_bind_exception中，沒有使用rt_cache_route函數中的cmpxchg指令。
而是由rcu_dereference和rcu_assign_pointer進行類似的路由緩存操作，
之後，如果原有緩存不為空，對其進行釋放。
如果緩存操作未執行，将由以上的調用函數rt_set_nexthop将路由緩存項添加到uncached_list連結清單。
*/
if (daddr == fnhe->fnhe_daddr) {
struct rtable __rcu **porig;
struct rtable *orig;
int genid = fnhe_genid(dev_net(rt->dst.dev));
if (rt_is_input_route(rt))
porig = &fnhe->fnhe_rth_input;
else
porig = &fnhe->fnhe_rth_output;
orig = rcu_dereference(*porig);
if (fnhe->fnhe_genid != genid) {
fnhe->fnhe_genid = genid;
fnhe->fnhe_gw = 0;
fnhe->fnhe_pmtu = 0;
fnhe->fnhe_expires = 0;
fnhe_flush_routes(fnhe);
orig = NULL;
}
fill_route_from_fnhe(rt, fnhe);
if (!rt->rt_gateway)
rt->rt_gateway = daddr;
if (!(rt->dst.flags & DST_NOCACHE)) {
rcu_assign_pointer(*porig, rt);
if (orig)
rt_free(orig);
ret = true;
}
fnhe->fnhe_stamp = jiffies;
}
spin_unlock_bh(&fnhe_lock);
return ret;
} View Code
uncached_list連結清單删除
//當釋放路由緩存時， 檢測其是否在uncached_list連結清單中，為真将其從連結清單中删除
static void ipv4_dst_destroy(struct dst_entry *dst)
{
struct dst_metrics *p = (struct dst_metrics *)DST_METRICS_PTR(dst);
struct rtable *rt = (struct rtable *) dst;
if (p != &dst_default_metrics && atomic_dec_and_test(&p->refcnt))
kfree(p);
if (!list_empty(&rt->rt_uncached)) {
struct uncached_list *ul = rt->rt_uncached_list;
spin_lock_bh(&ul->lock);
list_del(&rt->rt_uncached);
spin_unlock_bh(&ul->lock);
}
} 當系統登出一個網絡裝置時，周遊所有的uncached_list連結清單上的路由緩存項，如果其路由裝置等于要登出的裝置，将裝置更換為黑洞裝置blackhole_netdev，路由到此裝置的封包都将被丢棄。
/*當系統登出一個網絡裝置時，周遊所有的uncached_list連結清單上的路由緩存項，
如果其路由裝置等于要登出的裝置，将裝置更換為黑洞裝置blackhole_netdev，
路由到此裝置的封包都将被丢棄。*/
void rt_flush_dev(struct net_device *dev)
{
struct net *net = dev_net(dev);
struct rtable *rt;
int cpu;
for_each_possible_cpu(cpu) {
struct uncached_list *ul = &per_cpu(rt_uncached_list, cpu);
spin_lock_bh(&ul->lock);
list_for_each_entry(rt, &ul->head, rt_uncached) {
if (rt->dst.dev != dev)
continue;
rt->dst.dev = net->loopback_dev;== blackhole_netdev
dev_hold(rt->dst.dev);
dev_put(dev);
}
spin_unlock_bh(&ul->lock);
}
}