netdev - Re: [PATCH] sch_htb.c consume the classes's tokens bellow the HTB_CAN

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Wed, 4 Nov 2009 17:16:42 +0800
From:	Changli Gao <xiaosuo@...il.com>
To:	Jarek Poplawski <jarkao2@...il.com>
Cc:	Jamal Hadi Salim <hadi@...erus.ca>, devik@....cz,
	netdev@...r.kernel.org
Subject: Re: [PATCH] sch_htb.c consume the classes's tokens bellow the 
	HTB_CAN_SEND level

On Wed, Nov 4, 2009 at 4:28 PM, Jarek Poplawski <jarkao2@...il.com> wrote:
>> >
>> > If it's really necessary you should present some test case fixed by
>> > your patch, I guess.
>> >
>> > In the meantime let's consider what could be broken:
>> > class 1:1 (parent) rate 10 packets/sec
>> > class 1:2 rate 5 packets/sec ceil 10 packets/sec
>> > class 1:3 rate 5 packets/sec ceil 10 packets/sec
>> >
>> > class 1:2 doesn't use all its rate, and sends every other second
>> >        (in even seconds)
>> > class 1:3 sends 10 packets during the first second, so with your
>> >        patch it will use its tokens for 2 seconds
>> > class 1:2 uses its rate in the second second..., so class 1:1
>> >        can't lend anything
>> > class 1:3 can only borrow, so it won't be able to send during
>> >        this second anything
>> >
>> > So, the effect would be class 1:3 sending every odd second 10 packets
>> > while every even second - nothing...
>>
>> class 1:3 can send, as its parent rate is 10, but class 1:2 only uses
>> half of it, and class 1:1 is still in HTB_CAN_SEND mode.
>>
>> The result is, hasn't any difference with or without my patch :
>> class 1:1 sends 10 packets in odd seconds, and 5 packets in even seconds.
>
> I guess you meant class 1:3.

You are right. :)

> and there is a difference: it sends 5
> packets in even seconds only if it manages to borrow from 1:1, but
> it's not _guaranteed_ at all. In this particular case it's quite
> probable class 1:2 will send 10 packets in even seconds instead, or
> with some finer borrowing control it could be: class 1:2 8 packets,
> class 1:3 2 packets, as well.

It is just correct. You focus on 1 second fairness, while I focus on 2
seconds fairness.

>
>> class 1:2 sends 5 packets in even seconds.
>> class 1:1 (parent) sends 10 packets in every second.
>>
>> Let's think this case in another way: which class sends packets in
>> even seconds first, class 1:2 or class 1:3.
>> With my patch, as 1:3 in HTB_MAY_BORROW mode, and 1:2 in HTB_CAN_SEND
>> mode, so 1:2 sends all its 5 packets first.
>> Without my patch, as 1:2 and 1:3 are both in HTB_CAN_SEND mode, the
>> sequence is undetermined. In other word, 1:2 and 1:3 are treated
>> fairly, and it isn't fair for 1:2, because 1:2 sends nothing in odd
>> seconds, and has no deficit in rate as 1:3.
>
> The token bucket (cl->buffer) is just to account distinctly when a
> class is entitled to send and when it actually does send within its
> rate. The fairness is controlled by classes itself with HTB_CAN_SEND
> state. Using this bucket to account for borrowed sending deprives us
> of this precise information. "The fairness" would be controlled by
> priorities of borrowing instead (see above).
>
The token bucket and ctoken bucket both use cl->mbuffer to control
rate granularities. If we don't account token bucket when the
corresponding class in HTB_MAY_BORROW mode, the cl->mbuffer will
become useless.


-- 
Regards，
Changli Gao(xiaosuo@...il.com)
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html