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]

Message-ID: <20091104082808.GA6224@ff.dom.local>
Date:	Wed, 4 Nov 2009 08:28:08 +0000
From:	Jarek Poplawski <jarkao2@...il.com>
To:	Changli Gao <xiaosuo@...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 04, 2009 at 09:53:52AM +0800, Changli Gao wrote:
> On Wed, Nov 4, 2009 at 7:00 AM, Jarek Poplawski <jarkao2@...il.com> wrote:
> > On Tue, Nov 03, 2009 at 09:18:49PM +0800, Changli Gao wrote:
> >> On Tue, Nov 3, 2009 at 6:05 PM, Jarek Poplawski <jarkao2@...il.com> wrote:
> >> >
> >> > The ceil specification is controlled only by ctokens, which are always
> >> > updated, so no such risk.
> >> >
> >> Nevertheless, updating tokens is necessary too.
> >
> > 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, 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.

> 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).

Regards,
Jarek P.
--
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