Linux内核中流量控制(20)

yfydz

Linux内核中流量控制(20)
本文档的Copyleft归yfydz所有，使用GPL发布，可以自由拷贝，转载，转载时请保持文档的完整性，严禁用于任何商业用途。
msn:
yfydz_no1@hotmail.com
来源：
http://yfydz.cublog.cn
7.11 tcindex
tcindex是根据skb数据包中的tcindex参数对数据类型进行分类的, 而tcindex的值是在上层设置好的, 代码在net/sched/cls_tcindex.c中定义。
7.11.1 数据结构和过滤器操作结构
// tcindex过滤结果
struct tcindex_filter_result {
// 扩展结构
struct tcf_exts  exts;
// 分类结果
struct tcf_result res;
};
// tcindex过滤器
struct tcindex_filter {
// 关键字
u16 key;
// 过滤结果
struct tcindex_filter_result result;
// 链表下一项
struct tcindex_filter *next;
};
// tcindex数据结构
struct tcindex_data {
// 过滤结果, 完美哈希, 是数组形式
struct tcindex_filter_result *perfect; /* perfect hash; NULL if none */
// 不完美的哈希, 是链表形式
struct tcindex_filter **h; /* imperfect hash; only used if !perfect;
          NULL if unused */
// 关键字的掩码
u16 mask;  /* AND key with mask */
// 偏移数
int shift;  /* shift ANDed key to the right */
// 哈希表数量
int hash;  /* hash table size; 0 if undefined */
int alloc_hash;  /* allocated size */
int fall_through; /* 0: only classify if explicit match */
};

static struct tcf_ext_map tcindex_ext_map = {
.police = TCA_TCINDEX_POLICE,
.action = TCA_TCINDEX_ACT
};

// 操作结构
static struct tcf_proto_ops cls_tcindex_ops = {
.next  = NULL,
.kind  = "tcindex",
.classify = tcindex_classify,
.init  = tcindex_init,
.destroy = tcindex_destroy,
.get  = tcindex_get,
.put  = tcindex_put,
.change  = tcindex_change,
.delete  = tcindex_delete,
.walk  = tcindex_walk,
.dump  = tcindex_dump,
.owner  = THIS_MODULE,
};

7.11.2 初始化

static int tcindex_init(struct tcf_proto *tp)
{
struct tcindex_data *p;
DPRINTK("tcindex_init(tp %p)\n",tp);
// 分配tcindex数据结构空间
p = kzalloc(sizeof(struct tcindex_data),GFP_KERNEL);
if (!p)
  return -ENOMEM;
// 设置基本参数
p->mask = 0xffff;
p->hash = DEFAULT_HASH_SIZE; // 64
p->fall_through = 1;
// 将其作为TCF_PROTO的规则根节点
tp->root = p;
return 0;
}

7.11.3 分类
#define PRIV(tp) ((struct tcindex_data *) (tp)->root)
static int tcindex_classify(struct sk_buff *skb, struct tcf_proto *tp,
       struct tcf_result *res)
{
// TCF_PROTO结构过滤规则根节点即tcindex数据结构
struct tcindex_data *p = PRIV(tp);
struct tcindex_filter_result *f;
// 根据数据包的tcindex参数计算key: 先掩码掩, 再右移几位
int key = (skb->tc_index & p->mask) >> p->shift;
D2PRINTK("tcindex_classify(skb %p,tp %p,res %p),p %p\n",skb,tp,res,p);
// 根据key查找过滤结果
f = tcindex_lookup(p, key);
if (!f) {
  if (!p->fall_through)
   return -1;
  res->classid = TC_H_MAKE(TC_H_MAJ(tp->q->handle), key);
  res->class = 0;
  D2PRINTK("alg 0x%x\n",res->classid);
  return 0;
}
// 找到过滤结果, 赋值给分类结果
*res = f->res;
D2PRINTK("map 0x%x\n",res->classid);
// 执行TCF配置扩展
return tcf_exts_exec(skb, &f->exts, res);
}
// 根据key查找过滤结果
static struct tcindex_filter_result *
tcindex_lookup(struct tcindex_data *p, u16 key)
{
struct tcindex_filter *f;
if (p->perfect)
// 查找perfect数组的第key项
  return tcindex_filter_is_set(p->perfect + key) ?
   p->perfect + key : NULL;
else if (p->h) {
// 查找非perfect链表
  for (f = p->h[key % p->hash]; f; f = f->next)
   if (f->key == key)
    return &f->result;
}
return NULL;
}

7.11.4 释放

static void tcindex_destroy(struct tcf_proto *tp)
{
// TCF_PROTO结构过滤规则根节点即tcindex数据结构
struct tcindex_data *p = PRIV(tp);
struct tcf_walker walker;
DPRINTK("tcindex_destroy(tp %p),p %p\n",tp,p);
// 初始化遍历结构
walker.count = 0;
walker.skip = 0;
// 释放一个元素
walker.fn = &tcindex_destroy_element;
// tcindex遍历删除每个元素
tcindex_walk(tp,&walker);
// 释放perfect数组
kfree(p->perfect);
// 释放非perfect节点
kfree(p->h);
// 释放tcindex数据结构
kfree(p);
tp->root = NULL;
}
static int tcindex_destroy_element(struct tcf_proto *tp,
    unsigned long arg, struct tcf_walker *walker)
{
// 释放tcindex过滤结果节点, 操作不加锁
return __tcindex_delete(tp, arg, 0);
}
static int
__tcindex_delete(struct tcf_proto *tp, unsigned long arg, int lock)
{
// TCF_PROTO结构过滤规则根节点即tcindex数据结构
struct tcindex_data *p = PRIV(tp);
// 过滤结果
struct tcindex_filter_result *r = (struct tcindex_filter_result *) arg;
struct tcindex_filter *f = NULL;
DPRINTK("tcindex_delete(tp %p,arg 0x%lx),p %p,f %p\n",tp,arg,p,f);
if (p->perfect) {
// perfect数组非空, r是perfect数组中的项
// 如果分类结果为空, 说明该过滤结果项非法
  if (!r->res.class)
   return -ENOENT;
} else {
// r是非perfect链表中的项, 在链表中查找
  int i;
  struct tcindex_filter **walk = NULL;
// 遍历HASH表数量
  for (i = 0; i hash; i++)
// 遍历链表
   for (walk = p->h+i; *walk; walk = &(*walk)->next)
// 查找过滤结果项
    if (&(*walk)->result == r)
     goto found;
// 没找到, 返回错误
  return -ENOENT;
found:
// 找到过滤结果节点, 从链表中断开
  f = *walk;
  if (lock)
   tcf_tree_lock(tp);
  *walk = f->next;
  if (lock)
   tcf_tree_unlock(tp);
}
// 解开和过滤器的绑定
tcf_unbind_filter(tp, &r->res);
// 释放TCF扩展
tcf_exts_destroy(tp, &r->exts);
// 释放过滤结果节点, 这是原来非perfect链表中的节点, 如果是perfect数组中的就无意义
kfree(f);
return 0;
}
7.11.5 获取
// 根据handle查找tcindex过滤结果结果
static unsigned long tcindex_get(struct tcf_proto *tp, u32 handle)
{
// TCF_PROTO结构过滤规则根节点即tcindex数据结构
struct tcindex_data *p = PRIV(tp);
struct tcindex_filter_result *r;
DPRINTK("tcindex_get(tp %p,handle 0x%08x)\n",tp,handle);
// 如果perfect数组非空, 但handle值超过分配的数组大小, 返回空
if (p->perfect && handle >= p->alloc_hash)
  return 0;
// 根据handle查找过滤结果结构
r = tcindex_lookup(p, handle);
return r && tcindex_filter_is_set(r) ? (unsigned long) r : 0UL;
}
7.11.6 放下
// 空函数
static void tcindex_put(struct tcf_proto *tp, unsigned long f)
{
DPRINTK("tcindex_put(tp %p,f 0x%lx)\n",tp,f);
}
7.11.7 修改
// 增加和修改tc filter规则时调用
static int
tcindex_change(struct tcf_proto *tp, unsigned long base, u32 handle,
        struct rtattr **tca, unsigned long *arg)
{
// 输入的选项参数
struct rtattr *opt = tca[TCA_OPTIONS-1];
struct rtattr *tb[TCA_TCINDEX_MAX];
// TCF_PROTO结构过滤规则根节点即tcindex数据结构
struct tcindex_data *p = PRIV(tp);
// 过滤结果
struct tcindex_filter_result *r = (struct tcindex_filter_result *) *arg;
DPRINTK("tcindex_change(tp %p,handle 0x%08x,tca %p,arg %p),opt %p,"
     "p %p,r %p,*arg 0x%lx\n",
     tp, handle, tca, arg, opt, p, r, arg ? *arg : 0L);
// 无参数, 返回
if (!opt)
  return 0;
// 解析输入参数
if (rtattr_parse_nested(tb, TCA_TCINDEX_MAX, opt)

static int
tcindex_set_parms(struct tcf_proto *tp, unsigned long base, u32 handle,
    struct tcindex_data *p, struct tcindex_filter_result *r,
    struct rtattr **tb, struct rtattr *est)
{
int err, balloc = 0;
struct tcindex_filter_result new_filter_result, *old_r = r;
// 结构用于更新, 如果在更新操作中出现错误, 可以不影响原来的参数
struct tcindex_filter_result cr;
struct tcindex_data cp;
struct tcindex_filter *f = NULL; /* make gcc behave */
struct tcf_exts e;
// TCF扩展参数合法性处理
err = tcf_exts_validate(tp, tb, est, &e, &tcindex_ext_map);
// 失败则返回
if (err
// 初始化各结构, 复制或清零
memcpy(&cp, p, sizeof(cp));
memset(&new_filter_result, 0, sizeof(new_filter_result));
if (old_r)
  memcpy(&cr, r, sizeof(cr));
else
  memset(&cr, 0, sizeof(cr));
err = -EINVAL;
// 解析tcindex的HASH表数
if (tb[TCA_TCINDEX_HASH-1]) {
  if (RTA_PAYLOAD(tb[TCA_TCINDEX_HASH-1])
// 解析tcindex的掩码
if (tb[TCA_TCINDEX_MASK-1]) {
  if (RTA_PAYLOAD(tb[TCA_TCINDEX_MASK-1])
// 解析偏移数
if (tb[TCA_TCINDEX_SHIFT-1]) {
  if (RTA_PAYLOAD(tb[TCA_TCINDEX_SHIFT-1])
err = -EBUSY;
/* Hash already allocated, make sure that we still meet the
  * requirements for the allocated hash.
  */
if (cp.perfect) {
// 如果perfect数组已经分配, 检查参数是否合法
  if (!valid_perfect_hash(&cp) ||
      cp.hash > cp.alloc_hash)
   goto errout;
} else
// 否则如果非perfect链表非空, 检查哈希数是否匹配
        if (cp.h && cp.hash != cp.alloc_hash)
  goto errout;
err = -EINVAL;
// 解析fall_through参数
if (tb[TCA_TCINDEX_FALL_THROUGH-1]) {
  if (RTA_PAYLOAD(tb[TCA_TCINDEX_FALL_THROUGH-1])
if (!cp.hash) {
// 没设置哈希数, 计算之
  /* Hash not specified, use perfect hash if the upper limit
   * of the hashing index is below the threshold.
   */
  if ((cp.mask >> cp.shift) > cp.shift)+1;
  else
   cp.hash = DEFAULT_HASH_SIZE;
}
// perfect数组和非perfect链表都没分配, 第一次操作, 给alloc_hash参数赋值
if (!cp.perfect && !cp.h)
  cp.alloc_hash = cp.hash;
/* Note: this could be as restrictive as if (handle & ~(mask >> shift))
  * but then, we'd fail handles that may become valid after some future
  * mask change. While this is extremely unlikely to ever matter,
  * the check below is safer (and also more backwards-compatible).
  */
// 检查handle值是否合法
if (cp.perfect || valid_perfect_hash(&cp))
  if (handle >= cp.alloc_hash)
   goto errout;
err = -ENOMEM;
if (!cp.perfect && !cp.h) {
// perfect数组或非perfect链表都是空的
  if (valid_perfect_hash(&cp)) {
// 分配hash个过滤结果结构的空间作为perfect数组
   cp.perfect = kcalloc(cp.hash, sizeof(*r), GFP_KERNEL);
   if (!cp.perfect)
    goto errout;
// perfect数组已分配标志
   balloc = 1;
  } else {
// 分配非perfect哈希表的表头数组, 共hash项
// sizeof(f)只是指针大小, 32位系统是4
   cp.h = kcalloc(cp.hash, sizeof(f), GFP_KERNEL);
   if (!cp.h)
    goto errout;
// 非perfect哈希链表头数组已分配标志
   balloc = 2;
  }
}
// 查找定位handle对于的过滤结果项
if (cp.perfect)
  r = cp.perfect + handle;
else
  r = tcindex_lookup(&cp, handle) ? : &new_filter_result;
if (r == &new_filter_result) {
// 表示r应该是非perfect链表中的新分配的节点
// 分配tcindex过滤器结构
  f = kzalloc(sizeof(*f), GFP_KERNEL);
  if (!f)
   goto errout_alloc;
  }
// 如果有类别ID项
if (tb[TCA_TCINDEX_CLASSID-1]) {
// 填写结果的类别ID
  cr.res.classid = *(u32 *) RTA_DATA(tb[TCA_TCINDEX_CLASSID-1]);
// 绑定过滤器
  tcf_bind_filter(tp, &cr.res, base);
  }
// TCF扩展结果修改
tcf_exts_change(tp, &cr.exts, &e);
tcf_tree_lock(tp);
// 过滤结果已经发生了变化, 老的过滤结果结构清零
if (old_r && old_r != r)
  memset(old_r, 0, sizeof(*old_r));
// 将新构造的过滤结果结构和tcindex数据结构拷贝回去, 也就是更新结构数据
// p中有新的perfect数组地址
memcpy(p, &cp, sizeof(cp));
memcpy(r, &cr, sizeof(cr));
if (r == &new_filter_result) {
// 新非pefect类别节点
  struct tcindex_filter **fp;
// 填写tcindex过滤器结构参数
  f->key = handle;
  f->result = new_filter_result;
  f->next = NULL;
// 将该结构插入到链表最后
  for (fp = p->h+(handle % p->hash); *fp; fp = &(*fp)->next)
   /* nothing */;
  *fp = f;
  }
tcf_tree_unlock(tp);
return 0;
// 失败处理
errout_alloc:
if (balloc == 1)
  kfree(cp.perfect);
else if (balloc == 2)
  kfree(cp.h);
errout:
tcf_exts_destroy(tp, &e);
return err;
}

7.11.8 删除
// 只是__tcindex_delete的包裹函数, 见前面分析
static int tcindex_delete(struct tcf_proto *tp, unsigned long arg)
{
// 加锁参数为1, 当节点从链表中断开时要加锁
return __tcindex_delete(tp, arg, 1);
}
7.11.9 遍历
static void tcindex_walk(struct tcf_proto *tp, struct tcf_walker *walker)
{
// TCF_PROTO结构过滤规则根节点即tcindex数据结构
struct tcindex_data *p = PRIV(tp);
struct tcindex_filter *f,*next;
int i;
DPRINTK("tcindex_walk(tp %p,walker %p),p %p\n",tp,walker,p);
if (p->perfect) {
// perfect数组非空,
// 遍历每一项
  for (i = 0; i hash; i++) {
// 如果该项分类结果类别非法, 跳过该项
   if (!p->perfect.res.class)
    continue;
// 比较是否是要跳过的项
   if (walker->count >= walker->skip) {
// 调用单节点操作函数
    if (walker->fn(tp,
        (unsigned long) (p->perfect+i), walker)
         stop = 1;
     return;
    }
   }
   walker->count++;
  }
}
// 如果没有非perfect链表, 返回
if (!p->h)
  return;
// 遍历所有非perfect链表
for (i = 0; i hash; i++) {
  for (f = p->h; f; f = next) {
   next = f->next;
// 比较是否是要跳过的项
   if (walker->count >= walker->skip) {
// 调用单节点操作函数
    if (walker->fn(tp,(unsigned long) &f->result,
        walker) stop = 1;
     return;
    }
   }
   walker->count++;
  }
}
}

7.11.10 输出
static int tcindex_dump(struct tcf_proto *tp, unsigned long fh,
    struct sk_buff *skb, struct tcmsg *t)
{
// TCF_PROTO结构过滤规则根节点即tcindex数据结构
struct tcindex_data *p = PRIV(tp);
// 要输出的过滤结果结构指针
struct tcindex_filter_result *r = (struct tcindex_filter_result *) fh;
// 数据包中的用于填写数据的缓冲区定位
unsigned char *b = skb->tail;
struct rtattr *rta;
DPRINTK("tcindex_dump(tp %p,fh 0x%lx,skb %p,t %p),p %p,r %p,b %p\n",
     tp,fh,skb,t,p,r,b);
DPRINTK("p->perfect %p p->h %p\n",p->perfect,p->h);
// 作为netlink属性结构指针
rta = (struct rtattr *) b;
RTA_PUT(skb,TCA_OPTIONS,0,NULL);
if (!fh) {
// 如果handle为0
//将handle设置为全1
  t->tcm_handle = ~0; /* whatever ... */
// 填写tcindex各种参数
// 哈希数量
  RTA_PUT(skb,TCA_TCINDEX_HASH,sizeof(p->hash),&p->hash);
// 掩码
  RTA_PUT(skb,TCA_TCINDEX_MASK,sizeof(p->mask),&p->mask);
// 偏移值
  RTA_PUT(skb,TCA_TCINDEX_SHIFT,sizeof(p->shift),&p->shift);
// fall_through
  RTA_PUT(skb,TCA_TCINDEX_FALL_THROUGH,sizeof(p->fall_through),
      &p->fall_through);
  rta->rta_len = skb->tail-b;
} else {
  if (p->perfect) {
// 如果perfect数组非空
// handle值就是r节点在perfect数组中的位置
   t->tcm_handle = r-p->perfect;
  } else {
// perfect数组空
   struct tcindex_filter *f;
   int i;
   t->tcm_handle = 0;
// 遍历非perfect链表, 找到result为r的过滤项, 将其key作为handle
   for (i = 0; !t->tcm_handle && i hash; i++) {
    for (f = p->h; !t->tcm_handle && f;
         f = f->next) {
     if (&f->result == r)
      t->tcm_handle = f->key;
    }
   }
  }
  DPRINTK("handle = %d\n",t->tcm_handle);
// 填充分类结果的类别
  if (r->res.class)
   RTA_PUT(skb, TCA_TCINDEX_CLASSID, 4, &r->res.classid);
// TCF扩展输出
  if (tcf_exts_dump(skb, &r->exts, &tcindex_ext_map) rta_len = skb->tail-b;
// TCF扩展输出统计结果
  if (tcf_exts_dump_stats(skb, &r->exts, &tcindex_ext_map) len;
rtattr_failure:
skb_trim(skb, b - skb->data);
return -1;
}

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

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/12313/showart_396260.html