87
網絡子係統71_路由緩存垃圾回收
// 同步回收機製
// 返回值：
// 0，達到回收目標
// 1，沒有達到回收目標
// 注：ip_rt_gc_min_interval = HZ/2
// ip_rt_gc_timeout = RT_GC_TIMEOUT = 300HZ
// ip_rt_gc_elasticity = 8*(rt_hash_mask+1)(正常情況下)
// ip_rt_gc_elasticity = 1(當綁定緩存到鄰居子係統失敗時)
// 平衡點，gc目標數的動態調整：
// 1.當前緩存個數 < 安全閾值(安全範圍，試圖gc少緩存)
// 1.1 當前緩存個數 > 上次gc的平衡點(安全範圍內允許緩存增多)
// 1.1.1 新平衡點+=min((當前緩存個數-上次平衡點)/2 , buckets)
// 1.2.1 gc目標數=當前緩存個數-新平衡點
// 1.2.1.1 gc目標數 < 0
// 1.2.1.1.1 新平衡點+=gc目標數
// 2. 當前緩存個數 > 安全閾值(危險範圍，試圖gc多緩存)
// 2.1 gc目標數 = max((當前緩存個數-安全閾值)/2, buckets)(超過安全閾值的緩存一半將被gc)
// 2.2 新平衡點=當前緩存個數-gc目標數
// 3. gc目標數>0時，進行垃圾回收
// 注，安全閾值，每個bucket的衝突鏈中有8個bucket
// 回收過程：
// 1.令，遍曆所有bucket = 一個回收單位
// 2.如果一個回收單位釋放了gc目標數，調整expire
// 2.1 expire+=HZ/2，放寬到期時限
// 3.如果一個回收單位沒有釋放gc目標數
// 3.1 如果當前緩存個數 < 緩存允許的最小值，退出，下一次使用當前的expire作為時限
// 3.2 否則，隻有在用戶態，並且耗時<1 jiffes時，繼續回收。
// 回收時限確定：
// 1.expire, 回收單位的起始到期時限，每個bucket使用該時限作為起始時限
// 當前回收單位沒有完成gc目標數，下一個回收單位折半expire。
// 5.tmo，每個衝突鏈起始設置tmo=expire，當衝突鏈的一個節點不能被刪除時，
// tmo折半。
1.1 static int rt_garbage_collect(void)
{
//靜態變量
static unsigned long expire = RT_GC_TIMEOUT;
static unsigned long last_gc;
static int rover;
static int equilibrium;
struct rtable *rth, **rthp;
unsigned long now = jiffies;
int goal;
//回收速率限製
// 在ip_rt_gc_min_interval時間範圍內，如果緩存數量沒有超過最大值，則放棄回收
if (now - last_gc < ip_rt_gc_min_interval &&
atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size) {
RT_CACHE_STAT_INC(gc_ignored);
goto out;
}
//ipv4_dst_ops.entries保存當前緩存的個數
goal = atomic_read(&ipv4_dst_ops.entries) -
(ip_rt_gc_elasticity << rt_hash_log);//平均長度下，所有bucket的緩存個數
//當前緩存的個數沒有達到平均緩存個數
if (goal <= 0) {
if (equilibrium < ipv4_dst_ops.gc_thresh)
equilibrium = ipv4_dst_ops.gc_thresh;
//當前緩存的個數相對於上次平衡點的增長個數
goal = atomic_read(&ipv4_dst_ops.entries) - equilibrium;
//緩存個數增加
if (goal > 0) {
//在平均水平下，平衡點隨著緩存個數的增加而增加
equilibrium += min_t(unsigned int, goal / 2, rt_hash_mask + 1);
//新平衡點為剩餘緩存個數
goal = atomic_read(&ipv4_dst_ops.entries) - equilibrium;
}
//當前緩存個數超過平均緩存個數
} else {
//至少回收 number of buckets
goal = max_t(unsigned int, goal / 2, rt_hash_mask + 1);
//新平衡點為剩餘緩存個數
equilibrium = atomic_read(&ipv4_dst_ops.entries) - goal;
}
if (now - last_gc >= ip_rt_gc_min_interval)
last_gc = now;
//當前緩存總數小於平均值時，並且小於上次的平衡點
// 說明緩存個數開始遞減，則降低平衡點，不進行回收
if (goal <= 0) {
equilibrium += goal;
goto work_done;
}
do {
int i, k;
//rover記錄上次遍曆的bucket
for (i = rt_hash_mask, k = rover; i >= 0; i--) {
//tmo，bucket衝突鏈表內部使用的起始到期時限
//expire, bucket之間使用的起始到期時限
unsigned long tmo = expire;
k = (k + 1) & rt_hash_mask;
//這次應該遍曆的bucket
rthp = &rt_hash_table[k].chain;
spin_lock_bh(&rt_hash_table[k].lock);
while ((rth = *rthp) != NULL) {
//檢查緩存到期
if (!rt_may_expire(rth, tmo, expire)) {
//到期時間折半，使回收更加嚴格
tmo >>= 1;
rthp = &rth->u.rt_next;
continue;
}
*rthp = rth->u.rt_next;
rt_free(rth);
goal--;
}
spin_unlock_bh(&rt_hash_table[k].lock);
if (goal <= 0)
break;
}
rover = k;
if (goal <= 0)
goto work_done;
//到期時間已經足夠嚴格，依然沒有達到目標，放棄回收
if (expire == 0)
break;
//下一輪遍曆的到期時間折半，使到期時間更加嚴格
expire >>= 1;
if (atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size)
goto out;
} while (!in_softirq() && time_before_eq(jiffies, now));
if (atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size)
goto out;
return 1;
work_done:
expire += ip_rt_gc_min_interval;
if (expire > ip_rt_gc_timeout ||
atomic_read(&ipv4_dst_ops.entries) < ipv4_dst_ops.gc_thresh)
expire = ip_rt_gc_timeout;
out: return 0;
}
// 異步垃圾回收
// 垃圾回收定時器函數
// 函數主要任務：
// 1.計算此次gc處理的bucket數
// 2.從上次遍曆到的下一個bucket開始
// 2.1 如果dst到期時間為0，可以被釋放，從衝突鏈取下節點，釋放
// 2.2 該dst沒有到期，調整gc時限更加嚴格
// 3.重新激活gc定時器
// 注：ip_rt_gc_interval=60HZ
// 注：ip_rt_gc_timeout，ip_rt_gc_interval的關係
// 1.一個bucket至少在ip_rt_gc_timeout間隔gc一次
// 2.兩次異步gc的間隔為ip_rt_gc_interval(即定時器的到期間隔)
// 3.此次gc處理的bucket個數=(ip_rt_gc_interval*(rt_hash_mask+1))/ip_rt_gc_timeout
// 使路由緩存到期的事件：
// 1.主機接收到 ICMP UNREACHABLE 或 ICMP FRAGMENTATION NEEDED，設置為一段時間後(10min)過期。
// 2.鄰居項無法解析l3到l2的映射，目的ip不可達時，設置為立即過期。
// dst_entry->expires
// 默認情況下，路由緩存表項永遠不會過期，因此dst_entry->expires設置為0，當發生使路由緩存過期的事件時
// ，更新dst_entry->expires為緩存到期的時間戳。
2.1 static void rt_check_expire(unsigned long dummy)
{
static int rover;
int i = rover, t;
struct rtable *rth, **rthp;
unsigned long now = jiffies;
//計算可gc的bucket個數
for (t = ip_rt_gc_interval << rt_hash_log; t >= 0;
//gc定時器到期時間ip_rt_gc_timeout
t -= ip_rt_gc_timeout) {
unsigned long tmo = ip_rt_gc_timeout;
//rover記錄上次gc的bucket
i = (i + 1) & rt_hash_mask;
rthp = &rt_hash_table[i].chain;
spin_lock(&rt_hash_table[i].lock);
while ((rth = *rthp) != NULL) {
//dst->expires該dst將過期的時間戳
if (rth->u.dst.expires) {
//表示指定的過期還沒到
if (time_before_eq(now, rth->u.dst.expires)) {
//過期時限折半
tmo >>= 1;
rthp = &rth->u.rt_next;
continue;
}
//該dst還不能被釋放
} else if (!rt_may_expire(rth, tmo, ip_rt_gc_timeout)) {
tmo >>= 1;
rthp = &rth->u.rt_next;
continue;
}
//從bucket的衝突鏈取下，釋放
*rthp = rth->u.rt_next;
rt_free(rth);
}
spin_unlock(&rt_hash_table[i].lock);
//一步回收不超過1 jiffies
if (time_after(jiffies, now))
break;
}
rover = i;
//下次到期的時間
mod_timer(&rt_periodic_timer, now + ip_rt_gc_interval);
}
// 判斷緩存是否可以釋放
// 參數：
// tmo1，可快速清理的緩存使用的到期時限
// tmo2，高代價創建的緩存使用的到期時限
// tmo2 > tmo1
// 緩存釋放的條件：
// 1.引用計數=0
// 2.如果，緩存指定了到期時間，並且達到了到期時間，可清理
// 3.否則，可以快速清理，並且清理代價較低
// 可以快速清理的緩存項：
// 1.廣播多播地址
// 2.入口路由
// 3.衝突鏈表中，其後有緩存項
// 清理代價較高的緩存項：
// 1.重定向的的緩存項
3.1 static int rt_may_expire(struct rtable *rth, unsigned long tmo1, unsigned long tmo2)
{
unsigned long age;
int ret = 0;
if (atomic_read(&rth->u.dst.__refcnt))
goto out;
ret = 1;
if (rth->u.dst.expires &&
time_after_eq(jiffies, rth->u.dst.expires))
goto out;
age = jiffies - rth->u.dst.lastuse;
ret = 0;
if ((age <= tmo1 && !rt_fast_clean(rth)) ||
(age <= tmo2 && rt_valuable(rth)))
goto out;
ret = 1;
out: return ret;
}
最後更新：2017-04-03 14:53:50