linux-kernel - Re: RSDL v0.31

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:	Fri, 23 Mar 2007 05:39:54 +0100
From:	Mike Galbraith <efault@....de>
To:	Con Kolivas <kernel@...ivas.org>
Cc:	Peter Zijlstra <a.p.zijlstra@...llo.nl>, Willy Tarreau <w@....eu>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Xavier Bestel <xavier.bestel@...e.fr>, Mark Lord <lkml@....ca>,
	Al Boldi <a1426z@...ab.com>, ck@....kolivas.org,
	Serge Belyshev <belyshev@...ni.sinp.msu.ru>,
	Ingo Molnar <mingo@...e.hu>, linux-kernel@...r.kernel.org,
	Nicholas Miell <nmiell@...cast.net>,
	Andrew Morton <akpm@...ux-foundation.org>
Subject: Re: RSDL v0.31

On Fri, 2007-03-23 at 09:50 +1100, Con Kolivas wrote:

> Now to figure out some meaningful cheap way of improving this accounting.

The accounting is easy iff tick resolution is good enough, the deadline
mechanism is harder.  I did the "quota follows task" thing, but nothing
good happens.  That just ensured that the deadline mechanism kicks in
constantly because tick theft is a fact of tick-based life.  A
reasonable fudge factor would help, but...

I see problems wrt with trying to implement the deadline mechanism.

As implemented, it can't identify who is doing the stealing (which
happens constantly, even if userland if 100% hog) because of tick
resolution accounting.  If you can't identify the culprit, you can't
enforce the quota, and quotas which are not enforced are, strictly
speaking, not quotas.  At tick time, you can only close the barn door
after the cow has been stolen, and the thief can theoretically visit
your barn an infinite number of times while you aren't watching the
door.  ("don't blink" scenarios, and tick is backward-assward blink)

You can count nanoseconds in schedule, and store the actual usage, but
then you still have the problem of inaccuracies in sched_clock() from
cross-cpu wakeup and migration.  Cross-cpu wakeups happen quite a lot.
If sched_clock() _were_ absolutely accurate, you wouldn't need the
runqueue deadline mechanism, because at slice tick time you can see
everything you will ever see without moving enforcement directly into
the most critical of paths.

IMHO, unless it can be demonstrated that timeslice theft is a problem
with a real-life scenario, you'd be better off dropping the queue
ticking.  Time slices are a deadline mechanism, and in practice the god
of randomness ensures that even fast movers do get caught often enough
to make ticking tasks sufficient.

(that was a very long-winded reply to one sentence because I spent a lot
of time looking into this very subject and came to the conclusion that
you can't get there from here.  fwiw, ymmv and all that of course;)

> Thanks again!

You're welcome.

	-Mike

-
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/