Linux内核中流量控制(21)

本文档的Copyleft归yfydz所有，使用GPL发布，可以自由拷贝，转载，转载时请保持文档的完整性，严禁用于任何商业用途。
msn: [e-mail]
来源：http://yfydz.cublog.cn

7.12 route

route分类是根据数据包的路由信息进行分类的, 路由信息中会带tclassid参数用于分类, 代码在net/sched/cls_route.c中定义, 只支持IPV4。

7.12.1 数据结构和过滤器操作结构

// route 快速映射结构, 相当于分类结果的cache
struct route4_fastmap
{
 struct route4_filter *filter;
 u32   id;
 int   iif;
};

// route头结构
struct route4_head
{
// 16个快速映射结构
 struct route4_fastmap fastmap[16];
// 257个bucket链表
 struct route4_bucket *table[256+1];
};
struct route4_bucket
{
 /* 16 FROM buckets + 16 IIF buckets + 1 wildcard bucket */
 struct route4_filter *ht[16+16+1];
};

// route过滤器结构
struct route4_filter
{
// 链表中的下一项
 struct route4_filter *next;
// ID
 u32   id;
// 网卡索引号
 int   iif;
// 分类结构
 struct tcf_result res;
// TCF扩展
 struct tcf_exts  exts;
// 句柄
 u32   handle;
// 所在的bucket
 struct route4_bucket *bkt;
};
#define ROUTE4_FAILURE ((struct route4_filter*)(-1L))
static struct tcf_ext_map route_ext_map = {
 .police = TCA_ROUTE4_POLICE,
 .action = TCA_ROUTE4_ACT
};

static struct tcf_ext_map tcindex_ext_map = {
 .police = TCA_TCINDEX_POLICE,
 .action = TCA_TCINDEX_ACT
};
 
// 分类操作结构
static struct tcf_proto_ops cls_route4_ops = {
 .next  = NULL,
 .kind  = "route",
 .classify = route4_classify,
 .init  = route4_init,
 .destroy = route4_destroy,
 .get  = route4_get,
 .put  = route4_put,
 .change  = route4_change,
 .delete  = route4_delete,
 .walk  = route4_walk,
 .dump  = route4_dump,
 .owner  = THIS_MODULE,
};

7.12.2 一些哈希函数

// 快速映射表位置哈希
static __inline__ int route4_fastmap_hash(u32 id, int iif)
{
// 取ID的低4位, 结果在0~15之间
 return id&0xF;
}

// 进入方向路由哈希
static __inline__ int route4_hash_to(u32 id)
{
// 取ID的低8位, 结果在0~255之间
 return id&0xFF;
}

// 来源方向路由哈希
static __inline__ int route4_hash_from(u32 id)
{
// 取ID的16~19位, 结果在0~15之间
 return (id>>16)&0xF;
}
// 网卡索引号哈希
static __inline__ int route4_hash_iif(int iif)
{
// 取网卡索引号的16~19位再加16, 结果在16~31之间
 return 16 + ((iif>>16)&0xF);
}

// 外卡哈希, 返回外卡哈希表号:32
static __inline__ int route4_hash_wild(void)
{
 return 32;
}

// 插入哈希, 从哈希表中删除时计算
static inline u32 to_hash(u32 id)
{
// 取低8位
 u32 h = id&0xFF;
// 第15位为1的话哈希值增加256
 if (id&0x8000)
  h += 256;
// 结果范围应该是0~511
 return h;
}

// 来源哈希, 插入哈希表时计算
static inline u32 from_hash(u32 id)
{
// 高16位清零
 id &= 0xFFFF;
// 低16位全1的话返回32, 外卡值
 if (id == 0xFFFF)
  return 32;
// 如果第15位为0
 if (!(id & 0x8000)) {
// 超过255的话返回256
  if (id > 255)
   return 256;
// 否则返回低4位, 范围为0~15
  return id&0xF;
 }
// 第15位为1
// 返回低4位加16, 范围为16~31
 return 16 + (id&0xF);
}

7.12.3 初始化

// 空函数
static int route4_init(struct tcf_proto *tp)
{
 return 0;
}
 
7.12.4 分类

// 分类结果处理宏
#define ROUTE4_APPLY_RESULT()     \
{        \
// 要返回的分类结果
 *res = f->res;      \
 if (tcf_exts_is_available(&f->exts)) {   \
// 执行TCF扩展操作
  int r = tcf_exts_exec(skb, &f->exts, res); \
  if (r < 0) {     \
// 操作失败, 不需要将结果进cache, 继续循环
   dont_cache = 1;    \
   continue;    \
  }      \
  return r;     \
 } else if (!dont_cache)     \
// 将结果进cache,
  route4_set_fastmap(head, id, iif, f);  \
 return 0;      \
}

static int route4_classify(struct sk_buff *skb, struct tcf_proto *tp,
      struct tcf_result *res)
{
// route头节点
 struct route4_head *head = (struct route4_head*)tp->root;
 struct dst_entry *dst;
 struct route4_bucket *b;
 struct route4_filter *f;
 u32 id, h;
 int iif, dont_cache = 0;

// 如果数据包路由项为空, 分类失败
 if ((dst = skb->dst) == NULL)
  goto failure;
// 类别ID
 id = dst->tclassid;
// 如果头节点空, 用老方法分类
 if (head == NULL)
  goto old_method;
// 网卡索引号
 iif = ((struct rtable*)dst)->fl.iif;
// 根据ID和网卡索引号计算快速映射哈希值
 h = route4_fastmap_hash(id, iif);
// 如果快速映射表中元素和此ID和网卡匹配, 而且过滤结构有效
 if (id == head->fastmap[h].id &&
     iif == head->fastmap[h].iif &&
     (f = head->fastmap[h].filter) != NULL) {
// 如果是错误分类, 返回失败
  if (f == ROUTE4_FAILURE)
   goto failure;
// 否则返回分类结构, 分类成功
  *res = f->res;
  return 0;
 }
// 单独根据ID计算路由to哈希值
 h = route4_hash_to(id);
restart:
// 如果该哈希值对应的表有效
 if ((b = head->table[h]) != NULL) {
// 根据ID哈希, 遍历合适的链表
  for (f = b->ht[route4_hash_from(id)]; f; f = f->next)
// 如果ID匹配, 成功返回
   if (f->id == id)
    ROUTE4_APPLY_RESULT();
// 根据网卡索引哈希, 遍历合适链表
  for (f = b->ht[route4_hash_iif(iif)]; f; f = f->next)
// 如果网卡索引匹配, 成功返回
   if (f->iif == iif)
    ROUTE4_APPLY_RESULT();
// 还没找到, 如果外卡链表存在的话, 也成功返回
  for (f = b->ht[route4_hash_wild()]; f; f = f->next)
   ROUTE4_APPLY_RESULT();
 }
// 哈希值对应的表为空的情况
// 如果哈希值太小, 更新其值后重新查找
 if (h < 256) {
  h = 256;
  id &= ~0xFFFF;
  goto restart;
 }
// 否则分类失败
// 如果需要保存在cache中, 将ID和网卡索引号保存到快速索引表中
 if (!dont_cache)
  route4_set_fastmap(head, id, iif, ROUTE4_FAILURE);
failure:
 return -1;
old_method:
// 老分类方法
// 如果ID有效, 而且ID高16位为0或高16位和handle的高16位相同
 if (id && (TC_H_MAJ(id) == 0 ||
     !(TC_H_MAJ(id^tp->q->handle)))) {
// 将ID作为类别ID返回
  res->classid = id;
  res->class = 0;
  return 0;
 }
 return -1;
}
 
7.12.5 释放
 
static void route4_destroy(struct tcf_proto *tp)
{
// 将根节点换出来准备释放
 struct route4_head *head = xchg(&tp->root, NULL);
 int h1, h2;
// 如果根节点空, 直接返回
 if (head == NULL)
  return;
// 遍历257个表
 for (h1=0; h1<=256; h1++) {
  struct route4_bucket *b;
// 如果链表头非空
  if ((b = head->table[h1]) != NULL) {
// 遍历bucket结构的33个filter链表
   for (h2=0; h2<=32; h2++) {
    struct route4_filter *f;
// 遍历每个链表
    while ((f = b->ht[h2]) != NULL) {
// 断开节点
     b->ht[h2] = f->next;
// 删除filter
     route4_delete_filter(tp, f);
    }
   }
// 释放bucket
   kfree(b);
  }
 }
// 释放根节点
 kfree(head);
}

static inline void
route4_delete_filter(struct tcf_proto *tp, struct route4_filter *f)
{
// 解除绑定
 tcf_unbind_filter(tp, &f->res);
// 释放TCF扩展结构
 tcf_exts_destroy(tp, &f->exts);
// 释放过滤器空间
 kfree(f);
}

7.12.6 获取

// 根据handle查找route4_filter结构
static unsigned long route4_get(struct tcf_proto *tp, u32 handle)
{
// 根节点
 struct route4_head *head = (struct route4_head*)tp->root;
 struct route4_bucket *b;
 struct route4_filter *f;
 unsigned h1, h2;

// 根节点空的话返回0
 if (!head)
  return 0;
// 根据handle计算哈希值
 h1 = to_hash(handle);
// 超过256的话返回0
 if (h1 > 256)
  return 0;
// 根据handle的高16位计算哈希找bucket
 h2 = from_hash(handle>>16);
// 超过32的话返回0
 if (h2 > 32)
  return 0;
// 如果bucket非空
 if ((b = head->table[h1]) != NULL) {
// 遍历链表
  for (f = b->ht[h2]; f; f = f->next)
// 查找handle匹配的filter节点返回
   if (f->handle == handle)
    return (unsigned long)f;
 }
 return 0;
}
 
7.12.7 放下
// 空函数
static void route4_put(struct tcf_proto *tp, unsigned long f)
{
}

7.12.8 修改

// 增加和修改tc filter规则时调用
static int route4_change(struct tcf_proto *tp, unsigned long base,
         u32 handle,
         struct rtattr **tca,
         unsigned long *arg)
{
// 根节点
 struct route4_head *head = tp->root;
 struct route4_filter *f, *f1, **fp;
 struct route4_bucket *b;
// 输入的选项参数
 struct rtattr *opt = tca[TCA_OPTIONS-1];
 struct rtattr *tb[TCA_ROUTE4_MAX];
 unsigned int h, th;
 u32 old_handle = 0;
 int err;
// 选项参数空, 返回
 if (opt == NULL)
  return handle ? -EINVAL : 0;
// 解析选项参数, 结果保存到tb数组
 if (rtattr_parse_nested(tb, TCA_ROUTE4_MAX, opt) < 0)
  return -EINVAL;
// 过滤器参数非空, 是修改操作
 if ((f = (struct route4_filter*)*arg) != NULL) {
// 比较handle是否正确
  if (f->handle != handle && handle)
   return -EINVAL;
// 如果已经在某bucket的链表里, 保存handle
  if (f->bkt)
   old_handle = f->handle;
// 设置过滤器参数, 函数最后一个参数为0表示是修改
  err = route4_set_parms(tp, base, f, handle, head, tb,
   tca[TCA_RATE-1], 0);
// 操作失败, 返回错误
  if (err < 0)
   return err;
// 成功则跳转重新插入, 将f从原链表中断开的操作也在后面进行
  goto reinsert;
 }
// 过滤器参数空, 是新建操作
 err = -ENOBUFS;
 if (head == NULL) {
// 如果根节点为空, 分配更节点空间
  head = kzalloc(sizeof(struct route4_head), GFP_KERNEL);
  if (head == NULL)
   goto errout;
  tcf_tree_lock(tp);
// 将其作为tcf_proto的根参数指针
  tp->root = head;
  tcf_tree_unlock(tp);
 }
// 分配新的过滤器空间
 f = kzalloc(sizeof(struct route4_filter), GFP_KERNEL);
 if (f == NULL)
  goto errout;
// 设置过滤器参数, 函数最后一个参数为1表示是新建
 err = route4_set_parms(tp, base, f, handle, head, tb,
  tca[TCA_RATE-1], 1);
// 失败的话转失败处理
 if (err < 0)
  goto errout;
reinsert:
// 重新插入操作, 将过滤器f插入合适的bucket链表, 对于修改操作, 因为参数变了,
// 所以要重新插入到合适的bucket中
// 计算from哈希
 h = from_hash(f->handle >> 16);
// 遍历相应的哈希链表查找插入位置, 该链表是按handle值排序, 小的在前, 大的在后
 for (fp = &f->bkt->ht[h]; (f1=*fp) != NULL; fp = &f1->next)
  if (f->handle < f1->handle)
    break;
// 将新节点插入链表
 f->next = f1;
 tcf_tree_lock(tp);
 *fp = f;
// 如果handle发生了变化, 需要将该过滤器从原来的链表中断开
// 不过找哪个哈希表的过程确挺费解的
 if (old_handle && f->handle != old_handle) {
// 计算老handle的to哈希
  th = to_hash(old_handle);
// 计算老handle高16位的from哈希
  h = from_hash(old_handle >> 16);
// to哈希链表非空
  if ((b = head->table[th]) != NULL) {
// 遍历链表
   for (fp = &b->ht[h]; *fp; fp = &(*fp)->next) {
// 查找过滤器节点
    if (*fp == f) {
// 从链表中断开
     *fp = f->next;
     break;
    }
   }
  }
 }
 tcf_tree_unlock(tp);
// 复位快速映射数组, 全部清零
 route4_reset_fastmap(tp->q->dev, head, f->id);
// 返回f的地址
 *arg = (unsigned long)f;
 return 0;
errout:
 kfree(f);
 return err;
}

// 设置过滤器参数
static int route4_set_parms(struct tcf_proto *tp, unsigned long base,
 struct route4_filter *f, u32 handle, struct route4_head *head,
 struct rtattr **tb, struct rtattr *est, int new)
{
 int err;
 u32 id = 0, to = 0, nhandle = 0x8000;
 struct route4_filter *fp;
 unsigned int h1;
 struct route4_bucket *b;
 struct tcf_exts e;
// TCF扩展验证
 err = tcf_exts_validate(tp, tb, est, &e, &route_ext_map);
 if (err < 0)
  return err;
 err = -EINVAL;
// 判断类别ID是否合法
 if (tb[TCA_ROUTE4_CLASSID-1])
  if (RTA_PAYLOAD(tb[TCA_ROUTE4_CLASSID-1]) < sizeof(u32))
   goto errout;
// 解析TO参数
 if (tb[TCA_ROUTE4_TO-1]) {
  if (new && handle & 0x8000)
   goto errout;
  if (RTA_PAYLOAD(tb[TCA_ROUTE4_TO-1]) < sizeof(u32))
   goto errout;
  to = *(u32*)RTA_DATA(tb[TCA_ROUTE4_TO-1]);
// TO参数不能超过255
  if (to > 0xFF)
   goto errout;
// 将TO参数作为nhandle的低0~8位
  nhandle = to;
 }
// 如果存在FROM参数
 if (tb[TCA_ROUTE4_FROM-1]) {
// 解析FROM参数
  if (tb[TCA_ROUTE4_IIF-1])
   goto errout;
  if (RTA_PAYLOAD(tb[TCA_ROUTE4_FROM-1]) < sizeof(u32))
   goto errout;
  id = *(u32*)RTA_DATA(tb[TCA_ROUTE4_FROM-1]);
// FROM参数也不能超过255
  if (id > 0xFF)
   goto errout;
// 将FROM参数作为nhandle的16~23位
  nhandle |= id << 16;
 } else if (tb[TCA_ROUTE4_IIF-1]) {
// 否则如果存在网卡参数
  if (RTA_PAYLOAD(tb[TCA_ROUTE4_IIF-1]) < sizeof(u32))
   goto errout;
  id = *(u32*)RTA_DATA(tb[TCA_ROUTE4_IIF-1]);
// 网卡参数不能超过0x7ffff
  if (id > 0x7FFF)
   goto errout;
// 将网卡参数作为nhandle的16~30位, 同时第15位置1
  nhandle |= (id | 0x8000) << 16;
 } else
// 否则nhandle高16位全1
  nhandle |= 0xFFFF << 16;
 if (handle && new) {
// 如果是新建而且handle非0
// 更新nhandle, 前面的计算全部费了
  nhandle |= handle & 0x7F00;
// 对于新建的filter, handle只能是在16~22位可以为1
  if (nhandle != handle)
   goto errout;
 }
// 计算新handle的to哈希
 h1 = to_hash(nhandle);
// 如果对应哈希值的bucket为空
 if ((b = head->table[h1]) == NULL) {
  err = -ENOBUFS;
// 分配bucket空间
  b = kzalloc(sizeof(struct route4_bucket), GFP_KERNEL);
  if (b == NULL)
   goto errout;
  tcf_tree_lock(tp);
// 赋值到bucket头数组
  head->table[h1] = b;
  tcf_tree_unlock(tp);
 } else {
// 否则计算高16位的from哈希
  unsigned int h2 = from_hash(nhandle >> 16);
  err = -EEXIST;
// 遍历bucket中相应的链表, 查找是否已经有相同的handle, 找到的话返回错误
  for (fp = b->ht[h2]; fp; fp = fp->next)
   if (fp->handle == f->handle)
    goto errout;
 }
 tcf_tree_lock(tp);
// 如果TO参数存在的话, ID取TO参数
 if (tb[TCA_ROUTE4_TO-1])
  f->id = to;

// 如果FROM参数存在的话, ID放到ID的高16位
 if (tb[TCA_ROUTE4_FROM-1])
  f->id = to | id<<16;
 else if (tb[TCA_ROUTE4_IIF-1])
  f->iif = id;
// 过滤器的新handle
 f->handle = nhandle;
// 过滤器所在的bucket
 f->bkt = b;
 tcf_tree_unlock(tp);
// 设置类别ID, 绑定过滤器
 if (tb[TCA_ROUTE4_CLASSID-1]) {
  f->res.classid = *(u32*)RTA_DATA(tb[TCA_ROUTE4_CLASSID-1]);
  tcf_bind_filter(tp, &f->res, base);
 }
// TCF扩展修改操作
 tcf_exts_change(tp, &f->exts, &e);
 return 0;
errout:
 tcf_exts_destroy(tp, &e);
 return err;
}
 
7.12.9 删除

static int route4_delete(struct tcf_proto *tp, unsigned long arg)
{
// 更节点
 struct route4_head *head = (struct route4_head*)tp->root;
// f是要删除的节点
 struct route4_filter **fp, *f = (struct route4_filter*)arg;
 unsigned h = 0;
 struct route4_bucket *b;
 int i;
// 根节点或要删除的节点为空, 参数错误
 if (!head || !f)
  return -EINVAL;
// 获取过滤器节点的handle和所在的bucket
 h = f->handle;
 b = f->bkt;
// 遍历该bucket的链表
 for (fp = &b->ht[from_hash(h>>16)]; *fp; fp = &(*fp)->next) {
// 查找f节点
  if (*fp == f) {
// 找到
   tcf_tree_lock(tp);
// 将该节点从链表中断开
   *fp = f->next;
   tcf_tree_unlock(tp);
// 复位快速映射表, 是将fastmap数组全部清零了, 好象是连坐一样
   route4_reset_fastmap(tp->q->dev, head, f->id);
// 释放该过滤器f
   route4_delete_filter(tp, f);
   /* Strip tree */
// 检查该f所在bucket是否已经空了
   for (i=0; i<=32; i++)
    if (b->ht[i])
     return 0;
   /* OK, session has no flows */
// 如果空了, 就准备删除该bucket
   tcf_tree_lock(tp);
// 哈希表头置空
   head->table[to_hash(h)] = NULL;
   tcf_tree_unlock(tp);
// 释放bucket
   kfree(b);
   return 0;
  }
 }
 return 0;
}

7.12.10 遍历

static void route4_walk(struct tcf_proto *tp, struct tcf_walker *arg)
{
// 根节点
 struct route4_head *head = tp->root;
 unsigned h, h1;

// 根节点空的话设置停止标志
 if (head == NULL)
  arg->stop = 1;
// 设置了停止标志时直接返回
 if (arg->stop)
  return;
// 遍历257个bucket
 for (h = 0; h <= 256; h++) {
  struct route4_bucket *b = head->table[h];
// 如果该bucket非空
  if (b) {
// 遍历33个链表
   for (h1 = 0; h1 <= 32; h1++) {
    struct route4_filter *f;
// 遍历链表
    for (f = b->ht[h1]; f; f = f->next) {
// 检查是否是需要跳过的节点
     if (arg->count < arg->skip) {
      arg->count++;
      continue;
     }
// 执行单节点处理函数
     if (arg->fn(tp, (unsigned long)f, arg) < 0) {
// 失败的话设置停止标志, 返回
      arg->stop = 1;
      return;
     }
     arg->count++;
    }
   }
  }
 }
}
 
7.12.11 输出

static int route4_dump(struct tcf_proto *tp, unsigned long fh,
         struct sk_buff *skb, struct tcmsg *t)
{
// 要输出的route过滤器节点
 struct route4_filter *f = (struct route4_filter*)fh;
// skb数据包缓冲区定位
 unsigned char  *b = skb->tail;
 struct rtattr *rta;
 u32 id;
// 过滤器空, 返回
 if (f == NULL)
  return skb->len;
// 填写handle
 t->tcm_handle = f->handle;
// 结构定位
 rta = (struct rtattr*)b;
 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
// 输出ROUTE_TO
 if (!(f->handle&0x8000)) {
  id = f->id&0xFF;
  RTA_PUT(skb, TCA_ROUTE4_TO, sizeof(id), &id);
 }
 if (f->handle&0x80000000) {
// handle最高位为1
  if ((f->handle>>16) != 0xFFFF)
// handle高16非全1的话输出网卡索引号
   RTA_PUT(skb, TCA_ROUTE4_IIF, sizeof(f->iif), &f->iif);
 } else {
// handle最高位为0
// ID高16位是ROUTE_FROM
  id = f->id>>16;
  RTA_PUT(skb, TCA_ROUTE4_FROM, sizeof(id), &id);
 }
// 类别ID
 if (f->res.classid)
  RTA_PUT(skb, TCA_ROUTE4_CLASSID, 4, &f->res.classid);
// TCF扩展输出
 if (tcf_exts_dump(skb, &f->exts, &route_ext_map) < 0)
  goto rtattr_failure;
 rta->rta_len = skb->tail - b;
// TCF扩展统计
 if (tcf_exts_dump_stats(skb, &f->exts, &route_ext_map) < 0)
  goto rtattr_failure;
 return skb->len;
rtattr_failure:
 skb_trim(skb, b - skb->data);
 return -1;
}
 
7.13 小结

分类操作结构分析告一段落, 基本的特点就是对节点操作时都不直接操作, 而是先在链表中查找确认后才操作, 这也是sched各种代码的共同特征, 为什么不能直接操作呢? 难道是怕在get操作时获取的结构指针在后来操作时已经被删除了? 不过的确这些结构中不是所有都有引用计数的原子操作; 另外一点就是handle的取值, 每个操作结构所对应的handle各个位的定义是不同, 同时进行各种哈希操作也不同, 这些都需要注意, 不过在此不仔细比较各类型的handle的不同了, 有兴趣的自己去分析。

...... 待续 ......