linux-kernel - Re: [PATCH v2] blk-throttle: simplify logic by token bucket algorithm

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, 16 Oct 2013 11:53:44 -0400
From:	Tejun Heo <tj@...nel.org>
To:	Vivek Goyal <vgoyal@...hat.com>
Cc:	Hong zhi guo <honkiko@...il.com>, Jens Axboe <axboe@...nel.dk>,
	cgroups@...r.kernel.org, linux-kernel@...r.kernel.org,
	Hong Zhiguo <zhiguohong@...cent.com>
Subject: Re: [PATCH v2] blk-throttle: simplify logic by token bucket algorithm

Hello,

On Wed, Oct 16, 2013 at 10:14:06AM -0400, Vivek Goyal wrote:
> - First of all, if you think that a group is entitiled for tokens even
>   when it is not doing IO, then why are you truncating the tokens after
>   dispatch of a BIO.
> 
> - Second in general it does not seem right that a group is entitiled to
>   tokens even when no IO is happening or group is not backlogged. That
>   would mean a group will not do IO for 10 hours and then be entitiled
>   to those tokens suddenly after 10 hours with a huge burst.
> 
> So I think you also agree that a group should not be entitiled to
> tokens when group is not backlogged and that's why you seem to be
> truncating extra tokens after dispatch of a BIO. If that's the case,
> then even for first BIO, ideally a group should not be given tokens
> for idle time.

Without going into details, having token reserve is an important part
of token based implementation.  The large the reserve could be
debatable but that's what provides "smoothing" of allocation.  e.g. if
you trim bucket as soon as the queue becomes empty, a queue with
sequential access pattern can easily get disadvantaged.  Another way
to look at it is to consider as though the IO has been issued some
time before than actual and waited for the token - it is the same to
external observers.

So, while how large the reserve should be is definitely debatable,
bucket scheduling *needs* idle reserve.

Thanks.

-- 
tejun
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/