[问题求助][img]http://linux.chinaunix.net/bbs/images/default/src_jh.gif[/img]hashlimit模块实现分析 [复制链接]

免责声明：有些地方没有仔细看，如有错误，不负责任，欢迎指正http://upload.bbs.csuboy.com/Mon_1004/126_6837_07b5498b08dbc4a.gif[/img]外贸

好久不发贴子了，来骗点积分。

1、引言
一直用tc来做流控，偶然发现Netfil.ter有一个名为hashlimit的东东，是基于TBF（令牌.桶算法）的简单的流量控制的。例如：           建材


QUOTE:iptables -A .INPUT -p tc.p --dport 22 -m hashlimit --hashlimit-name foo --hashlimit 100/sec --hashlimit-bu.rst 10 --hashlimit-mode srcip -j ACCEP.T
iptables -A INPUT -.p tc.p --dport 22 -j DROP.


TBF算法.还是比较简单的，著名的《计算机网络》一书中.有算法介绍，这里就不重复了。注意的是，TBF可以是基于字节，也可.以是基于数据包数量的。hashlimit使用了后者。.

--hashlimit-name .foo. ：取个名，反映在proc中；[成人用品]
--ha.s.hlimit 100/sec：每秒的数据包小于或等于XXX；.
--hashlim.it.-burst 10 ：每秒允许的突发；.

都是“每秒”，究竟是谁的.每秒呢？主要就是看hashlimit-.mo.de srcip(hash模式)，也就是限制的标的取哪一个，可以是四种：源地址、目的地址、源端口、目的端口；[成人用品]
以源地址为例，如果规则中增加了-s 192.168.0.0/24，那.么只有来源地址.符合这个的进入-m hashlimit，hash模.式为源地址，意味着将每个来源地址都做为一个限制标的！！.
--h.ashlimit 100/sec：每秒的数据包小于或等于.XXX；
准确点就.是192.168.0.0/2.4上的每一个主机每秒……域名

要实现TBF，有几个.基本的要素：投资
1、桶最大的令牌数；c.redit_cap    外汇
2、可.发放的令牌数.，它是根据单位时间定时刷新的；credit    外汇
3、令牌的消耗.，每通过一个包，消耗.多少个令牌。cost域名

基本关系是：
每过一个包，都要进行c.redit -= cost，直至credi.t <=0，即没有可供分配的令牌了——超限溢出；              乙肝
定时刷新credit，但是总量不得超过.credit_c.ap。电脑

2、实现
废话少说，来看代码。

static int

hashlimit_match(.const st.ruct sk_buff *skb,(广告)

                const struct net_device. *in,..

         .       const struct net_de.vice *out,电脑

           .     const void *.matchinfo,            杀毒

   .      .       int offset,(        游戏          )

        .        in.t *hotdrop).

{

   .    . struct ipt_hashlimit_info *r = 教育

                ((struct ip.t_hashlimit_info *)matchinfo)->u..master;教育

        struct .ipt_hashlimit_htabl.e *hinfo = r->hinfo;            杀毒

        unsigned long .now = jiffi.es;.

        struct. dsthash_ent .*dh;(        游戏          )

      .  struct dstha.sh_dst dst;.



        /* 根据hash. mode和当前.包，构建dst结构 */    健康

.     .  memset(&dst, 0, sizeof(dst));    美容

        if (hinfo-.>cfg.mode & IPT_HA.SHLIMIT_HASH_DIP)                //目的IP.

    .            dst.dst_ip = skb->nh.iph-.>daddr;<性病>

        if (hinfo->cfg.mode & IPT_HASHLIMIT_HASH_.SIP)             .   //源IP           建材

                dst.src_ip = sk.b->nh.iph->saddr.;.

        if (hinfo->cfg.mode & IPT_HASHLIMIT_HASH_DPT        .        /./端口.

        .    ||hinfo->cfg.mode & IPT_HASHLIMIT._HASH_SPT) {    美容

             .   u_int16_t .ports[2];.

        .        if (get_ports(skb, offset,. ports)) {(广告)

                  .      /* We've been asked to examine this pac.ket, and we             电子

               .            can't.  Hence, no choice .but to drop. */.

                  .      *hotdro.p = 1;域名

        .                return 0.;外贸

         .       }             电子

           .     if (hin.fo->cfg.mode & IPT_HASHLIMIT_HASH_SPT).

                        dst.src_port = p.orts[0.];.

     .           if (hinfo->cfg.mode & IPT_HASHLIMIT_HASH_D.PT).

                        ds.t..dst_port = ports[1];投资

        }
复制代码
这段代码根据has.h模块，取出数据包相应的元素。struct dsthash_dst是hash表使用的结.构。电影
        spin_lock_.bh(&hinfo->lock);                                //.查找.hash表.

        dh = __dsthash_fi.nd(hinfo, &dst).;[成人用品]
复制代码
查看has.h表中，是否有与dst一匹备的节点，之所以叫.hashlimit，就是因为每一个元素（例如以来源地址每一个IP），都被存放在hash表中（一个来源地址占据一.个hash节点）。教育

        if (!.dh) {域名

  .              dh = __dsthash_alloc_init(hin.fo, &dst);           .     //未命中，分配新的接点，并增加至hash 表.



      .     .     if (!dh) {.

             .          . /* enomem... don't match == DROP */    美容

                .        if (net_ratel.imit())健康

                               . prin.tk(KERN_ERR "%s: ENOMEM\n", __FUNCTION__).;             电子

                        spin.._unlock_bh(&hinfo->lock);外贸

    .           .         return 0;电脑

      .          }.

.               .

                /./构建结点成员服务器

                dh->expires = jiff.ies + m.secs_to_ji.ffies(hinfo->cfg.expire);        //定时器健康



                d.h.->rateinfo.prev = jiffies;                                        //最后修改时间定.为当前时间    外汇

                dh->rateinfo.credit = user2credits.(hinfo->cfg.avg *           .      //初始化令.牌           女人

   .                                                     hinfo->cfg.burst);        //初始化令牌桶大.小，在令牌没.有被消耗前，两者是相同的.

                dh->rateinfo.c.redit_cap = user2credits(hinfo-.>cfg.avg * .

                                    .                    hinfo->cf.g.burst);外贸

           .     dh->rateinfo.cost = user2credits(hi.nfo->cfg.avg);                //初始化当前.包的开销，每过一个包递减.



      .          spin_unlock_bh(.&hinfo->lock);--- 印刷

            .    return 1;学习

        }
复制代码
如果不在hash表中，则分配.新的节点，插入hash表.，然后初始化节点成员dh。代码很简单，但是关键是对这些东东的计算，后文分析：电脑
            .    dh->rateinfo.credit = us.er2credits(hinfo->cf.g.avg *                 //初始化令牌          婚庆

    .          .                                  .        hinfo->cfg.burst);        //初始化令牌桶大小，在令牌没有被消耗前，两者是相同的电脑

                dh->rate.info.credit_cap = use.r2credits(hinfo->cfg.avg * (        游戏          )

                   .                          .           hinfo->cfg.burst);.

                dh->rat.einfo.cost = user2credits.(hinfo->cfg.avg);           .     //初始化当前包的开销，每过一个包递.
复制代码
因为.前面已经return 1了，接下来是hash命中的情.况了：域名
   .     /* 更新超时时间戳 */           女人

  .      dh->expires = now + msecs_t.o_jiffies(hinfo->cfg.expire);--------------彩票



        /* 重新计算.令牌 */(        游戏          )

        rateinfo_reca.lc(dh, now.);外贸

  .      if (dh->rateinfo.cr.edit >= dh->rateinfo.cost) {                                //如果还.有令牌.

   .             /* W.e're underlimit. */.

     .           dh->rateinfo.credit -= dh->rateinfo.cost;   .                     .//减去当前包消耗掉的令牌，通过.

                spin_unl.ock_bh(.&hinfo->lock);虚拟主机

                retur.n 1;.

        }
复制代码
这段代码意思是，周期性地.刷新令牌，并且判断是否还有可供分配的令牌。对于每经过一个包，都会.递减令牌数。直接.
d.h->rateinfo.credit .< dh->rateinfo.cost    外汇
这也就意味.着没有可供分配令牌了。所以，最后retur.n 0；--- 印刷

代码结.构非常简单，与TBF算法一模一样，关键是两个地方，一个是初始化时，对于令牌的分配。另一个是得新计算令牌数函.数rateinfo_recalc()           建材

需要重点理解的是令牌刷新的时间周期.，虽然用户态使用了秒、分、小时……不过内核是使用的jiffy。在.初始计算的时候，user2.credits() 函数被调用：.
               . dh->rateinfo.credit = user2credits(hinfo->cfg..avg * 外贸

          .              .                                hinfo->cfg.burst);.

    .            dh->rateinfo.credit_cap = user2credit.s(hinfo->cfg.avg * 学习

                              .     .                     hinfo->cfg.burst);

   .             dh->rateinfo..cost = user2credits(hinfo->cfg.avg);          婚庆
复制代码
注意到的，cost比前者差了一个burst倍。举个例子，如果初始允许突发包是.10个。那么credit.可能是3200，而cost 320，相差10倍。这也意味着，在cre..dit不被更新的情况下（在一个jiffy周期之内），超过被允许的突发值后，令牌就用完了。投资

来看user2cre.dits的实现：          婚庆
/* Precision saver. *./           女人

static inline u_in.t32_t<性病>

user.2cr.edits(u_int32_t user).

{

   .   .  /* If multiplying would overflow... */服务器

        if. (user > 0xF.FFFFFFF / (HZ*CREDITS_PER_JIFFY)).

.       .        /* Divide first. */<性病>

                return (user / IPT_HASHLIMIT_SCALE) * HZ * C.R.EDITS_PER._JIFFY;



        return (user * HZ * CREDITS_PE.R_JIFFY) /. IPT_HASHLIMIT_SCALE;.

}
复制代码
CREDITS_PER_JIFFY宏表示的是每个jiffy要产生的令牌数.，乘以HZ，则表示为每.秒。之所以要除以IPT_H.ASHLIMIT_SCALE，是因为在iptables获取.值的时候，有一个反向操作(难道不想让用户态传递的时候，这个值过大，需要转换一下？？？)：.
*val. = I.PT_DSTLIMIT_SCALE * mult / r;健康
复制代码

最重要的函数是rateinfo_recalc，它负责.在每个jiffy周期，产生新的令牌，以使游戏能够继续下去：.    外汇
static inline vo.id rateinfo_rec.alc(struct dsthash_ent *dh, unsigned. long now).

{

        dh->rateinfo.credit += (now. - xchg(&d.h->rateinfo.prev, now)) .

    .                             .       * CREDITS_PER_JIFFY;           鲜花

        if (dh->rateinfo.credit > dh->ra.teinfo.cr.edit_cap)    健康

                dh->rateinfo.credit = dh->r.ateinfo.credi.t_cap;             电子

}
复制代码
以前一个包至目前时间的jiffy的差值N，并乘上CREDITS_P.ER_JIFFY得到新的令牌数。并且，它最大不能超.过令牌桶的大小。              乙肝

3、一个现实的例子
假如设定以下参数：
每秒平均值：100/sec
允许突发：10；
每jiffy产生的令牌为3.2，即C.REDITS_PER_JIFFY = 32；服务器

那么可以计算出：credit = 3200,.cost. = 320；--------------彩票
如果每秒是100个包，因为每个包消耗320，则每秒共.需要的令牌数总计为320. * 100 + 320 * 10 = 32000 + 3200<性病>
因为CREDITS_PER_JIFFY为32，则每秒产生的令牌是32 * 1000. ，并.且，初始化时，cr.edit = 3200，总计32000 + 3200服务器
嘿嘿，刚刚好！！

[ 本帖最后由 独孤.九贱 于 2008-6-25 17:18 .编辑 ]    健康

期待《续》！

不错 支持

QUOTE:原帖由 独孤九贱 于 2008-6-25 17:00 发表
免责声明：有些地方没有仔细看，如有错误，不负责任，欢迎指正

这段代码意思是，周期性地刷新令牌，并且判断是否还有可供分配的令牌。对于每经过一个包，都会递减令牌数。直接
dh->rateinfo.credit < dh->rateinfo.cost
这也就意味着没有可供分配令牌了。所以，最后return 0；

代码结构非常简单，与TBF算法一模一样，关键是两个地方，一个是初始化时，对于令牌的分配。另一个是得新计算令牌数函数rateinfo_recalc()

需要重点理解的是令牌刷新的时间周期，虽然用户态使用了秒、分、小时……不过内核是使用的jiffy。在初始计算的时候，user2credits() 函数被调用：


我的理解：
1、关于hash的入口点，是 srcip:srcport:dstip:dstport的组合，经过特殊的算法，得到一个值，如果srcip,srcport,dstip,dstport中某个值没有指定，就使用0（端口）或者0.0.0.0（IP）
2、信元，它经过换算，折算成每个jiffy（计算机时钟的最小计时单位）折合多少信元
3、信元分配：
不是周期性的刷新，而是每个数据包到来的时候，进行计算，分配的方式是按照从上个数据包到这个数据包之间的时间间隔来分配信元，如果超过最大信元，就把超过部分溢出。
4、时钟的作用，目的是减少hash表的容量，因为有可能某个入口点有很长时间没有数据包了，因此需要把这个入口点从hash表中删除，以减少查找的时间（hash表越大，查找时间越长，因为它采用的是从前向后遍历的方式。）

/* Precision saver. */

static inline u_int32_t

user2credits(u_int32_t user)

{

        /* If multiplying would overflow... */

        if (user > 0xFFFFFFFF / (HZ*CREDITS_PER_JIFFY))

                /* Divide first. */

                return (user / IPT_HASHLIMIT_SCALE) * HZ * CREDITS_PER_JIFFY;



        return (user * HZ * CREDITS_PER_JIFFY) / IPT_HASHLIMIT_SCALE;

}
复制代码

分析一下就知道了，是防止计算溢出

实际结果都是一样的

比如求 a*b/c

如果a*b的结果溢出了，那么
a*b/c != a/c*b

QUOTE:原帖由 springwind426 于 2008-6-26 16:24 发表


我的理解：
1、关于hash的入口点，是 srcip:srcport:dstip:dstport的组合，经过特殊的算法，得到一个值，如果srcip,srcport,dstip,dstport中某个值没有指定，就使用0（端口）或者0.0.0.0（IP）
2、信元， ...



QUOTE:1、hash入口：
        if (hinfo->cfg.mode & IPT_HASHLIMIT_HASH_DIP)

                dst.dst_ip = skb->nh.iph->daddr;

        if (hinfo->cfg.mode & IPT_HASHLIMIT_HASH_SIP)

                dst.src_ip = skb->nh.iph->saddr;

        if (hinfo->cfg.mode & IPT_HASHLIMIT_HASH_DPT

            ||hinfo->cfg.mode & IPT_HASHLIMIT_HASH_SPT) {

                u_int16_t ports[2];

                if (get_ports(skb, offset, ports)) {

                        /* We've been asked to examine this packet, and we

                           can't.  Hence, no choice but to drop. */

                        *hotdrop = 1;

                        return 0;

                }

                if (hinfo->cfg.mode & IPT_HASHLIMIT_HASH_SPT)

                        dst.src_port = ports[0];

                if (hinfo->cfg.mode & IPT_HASHLIMIT_HASH_DPT)

                        dst.dst_port = ports[1];

        }
复制代码
因为主要讨论令牌桶算法，没有讨论hash表。这个是由用户指定的，可以是来源地址/目的地址/来源端口或目的端口，或者是它们的组合，hash算法，是内核通用的jhash_3words() 。



QUOTE:2、信元，它经过换算，折算成每个jiffy（计算机时钟的最小计时单位）折合多少信元

估计你说的信元，就是我说的令牌吧。



QUOTE:3、信元分配：
不是周期性的刷新，而是每个数据包到来的时候，进行计算，分配的方式是按照从上个数据包到这个数据包之间的时间间隔来分配信元，如果超过最大信元，就把超过部分溢出。

我仍然保留我的看法，的确是周期性刷新。因为：
A、这是TBF本身要求令牌的产生应该在^T时间(三角形符号打不出来，用^代替)周期内。
B、从代码来看：
static inline void rateinfo_recalc(struct dsthash_ent *dh, unsigned long now)

{

        dh->rateinfo.credit += (now - xchg(&dh->rateinfo.prev, now))

                                        * CREDITS_PER_JIFFY;

        if (dh->rateinfo.credit > dh->rateinfo.credit_cap)

                dh->rateinfo.credit = dh->rateinfo.credit_cap;

}
复制代码
虽然表面上rateinfo_recalc是每个包进来都会被调用，但是事实上，令牌的递增credit  +=N是有条件也，也就是在时间周期jiffy变化后才会变，否则它是0，也就是说，在“同一个时间周期内，并不产生新的令牌。”



QUOTE:4、时钟的作用，目的是减少hash表的容量，因为有可能某个入口点有很长时间没有数据包了，因此需要把这个入口点从hash表中删除，以减少查找的时间（hash表越大，查找时间越长，因为它采用的是从前向后遍历的方式。）
hash表的节点是需要一些定时器来处理回收，超时等等东东，没有讨论hash表，因为它跟内核其它的hash表没有区别。呵呵。
欢迎讨论。

5、你5楼的回复没有看懂，user2credits()在计算的时候的确是有一个防止溢出的计算。但偶没有明白你的意思。

[ 本帖最后由 独孤九贱 于 2008-6-27 09:47 编辑 ]

我对周期性的理解是每隔一个固定的时间发生一次，如果要周期性的完成某个任务的话，我觉得必须用定时器来处理

而hashlimit并不是用定时器来分配信元，而是每个数据包来临的时候，重新计算一下该hashitem拥有的信元数，如果dt=0的话，它就不分配新的信元，否则，它就按照dt的值来分配新的信元，因为有个burst的原因，需要做削峰处理（我理解成溢出处理）。

#define MAX_CPJ (0xFFFFFFFF / (HZ*60*60*24))



/* Repeated shift and or gives us all 1s, final shift and add 1 gives

* us the power of 2 below the theoretical max, so GCC simply does a

* shift. */

#define _POW2_BELOW2(x) ((x)|((x)>>1))

#define _POW2_BELOW4(x) (_POW2_BELOW2(x)|_POW2_BELOW2((x)>>2))

#define _POW2_BELOW8(x) (_POW2_BELOW4(x)|_POW2_BELOW4((x)>>4))

#define _POW2_BELOW16(x) (_POW2_BELOW8(x)|_POW2_BELOW8((x)>>8))

#define _POW2_BELOW32(x) (_POW2_BELOW16(x)|_POW2_BELOW16((x)>>16))

#define POW2_BELOW32(x) ((_POW2_BELOW32(x)>>1) + 1)



#define CREDITS_PER_JIFFY POW2_BELOW32(MAX_CPJ)
复制代码
从这个算法可知，最小时钟单位折合的信元数是固定的，与用户设置无关

/* timings are in milliseconds. */

#define XT_HASHLIMIT_SCALE 10000

/* 1/10,000 sec period => max of 10,000/sec.  Min rate is then 429490

   seconds, or one every 59 hours. */
复制代码
XT_HASHLIMIT_SCALE 是定义的一个比值，是为了在换算的时候，得到一个合理的信元值

static

int parse_rate(const char *rate, u_int32_t *val)

{

        const char *delim;

        u_int32_t r;

        u_int32_t mult = 1;  /* Seconds by default. */



        delim = strchr(rate, '/');

        if (delim) {

                if (strlen(delim+1) == 0)

                        return 0;



                if (strncasecmp(delim+1, "second", strlen(delim+1)) == 0)

                        mult = 1;

                else if (strncasecmp(delim+1, "minute", strlen(delim+1)) == 0)

                        mult = 60;

                else if (strncasecmp(delim+1, "hour", strlen(delim+1)) == 0)

                        mult = 60*60;

                else if (strncasecmp(delim+1, "day", strlen(delim+1)) == 0)

                        mult = 24*60*60;

                else

                        return 0;

        }

        r = atoi(rate);

        if (!r)

                return 0;



        /* This would get mapped to infinite (1/day is minimum they

           can specify, so we're ok at that end). */

        if (r / mult > IPT_HASHLIMIT_SCALE)

                exit_error(PARAMETER_PROBLEM, "Rate too fast `%s'\n", rate);



        *val = IPT_HASHLIMIT_SCALE * mult / r;

        return 1;

}

#这段代码是iptables中的ipt_hashlimit.c中的，任务是把用户的设置换算一下，大致是每个包折合多少秒，为了在以后的计算中得到合理的值，不至于因为溢出而产生误差，此处先进行了换算，就是用IPT_HASHLIMIT_SCALE来处理，在user2credits函数中会换算回来的，最终结果是每个包折合成多少信元



----------



/* Precision saver. */

static inline u_int32_t

user2credits(u_int32_t user)

{

        /* If multiplying would overflow... */

        if (user > 0xFFFFFFFF / (HZ*CREDITS_PER_JIFFY))

                /* Divide first. */

                return (user / XT_HASHLIMIT_SCALE) * HZ * CREDITS_PER_JIFFY;



        return (user * HZ * CREDITS_PER_JIFFY) / XT_HASHLIMIT_SCALE;

}

#这个函数只是计算每个包折合的信元数，其中的条件判断只是为了防止溢出（整数运算）。



static inline void rateinfo_recalc(struct dsthash_ent *dh, unsigned long now)

{

        dh->rateinfo.credit += (now - dh->rateinfo.prev) * CREDITS_PER_JIFFY;

        if (dh->rateinfo.credit > dh->rateinfo.credit_cap)

                dh->rateinfo.credit = dh->rateinfo.credit_cap;

        dh->rateinfo.prev = now;

}

#这个函数是计算，一个包来临的时候，桶中应该有多少信元



--------

......

        if (!dh) {

                dh = dsthash_alloc_init(hinfo, &dst);

                if (!dh) {

                        spin_unlock_bh(&hinfo->lock);

                        goto hotdrop;

                }



                dh->expires = jiffies + msecs_to_jiffies(hinfo->cfg.expire);

                dh->rateinfo.prev = jiffies;

                dh->rateinfo.credit = user2credits(hinfo->cfg.avg *

                                                   hinfo->cfg.burst);

                dh->rateinfo.credit_cap = user2credits(hinfo->cfg.avg *

                                                       hinfo->cfg.burst);

                dh->rateinfo.cost = user2credits(hinfo->cfg.avg);

.....
复制代码
从这些代码可以看出，实际上user2credits函数计算的结果是每个包折合成多少信元。

然后，每个包来临的时候，先向令牌桶中添加固定的信元数（这个信元数仅与时间间隔有关，与所有的用户设置的速率无关），然后，再根据用户的设置，来进行溢出处理(burst)，最后，把桶中的信元数与每个包所需要的信元数进行比较，如果桶中的信元数多，就匹配，返回真，同时，将桶中的信元减去每个包折合的信元数。

[ 本帖最后由 springwind426 于 2008-6-27 13:07 编辑 ]

QUOTE:原帖由 springwind426 于 2008-6-27 12:57 发表
我对周期性的理解是每隔一个固定的时间发生一次，如果要周期性的完成某个任务的话，我觉得必须用定时器来处理

而hashlimit并不是用定时器来分配信元，而是每个数据包来临的时候，重新计算一下该hashitem拥有 ...


嘿嘿，差不多是一个意思，表述的角度不同！
因为我指的周期性，刚好就是是一个jiffy——其实也相当于定时器了。但是没有必要去新增一个定时器timer。每一次数据包进来，去验证上一次刷新时间和现在的差值，因为有可能是在同一个jiffy不刷新，也有可能间隔了很久很久，于是重新分配令牌，我也觉得比使用timer更好。

[ 本帖最后由 独孤九贱 于 2008-6-27 13:19 编辑 ]

哈哈， 我只知道用这个模块， 挺好用。

恩，呵呵。。不错，写的不错

[ 本帖最后由 ixp2xxx 于 2008-6-28 15:46 编辑 ]