[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20171221120655.5929ec56@inria.fr>
Date: Thu, 21 Dec 2017 12:06:55 +0100
From: Jens Gustedt <jens.gustedt@...ia.fr>
To: musl@...ts.openwall.com
Subject: Re: [PATCH 1/8] (V2) a new lock algorithm with lock value
and CS counts in the same atomic int
Hello Rich,
On Wed, 20 Dec 2017 16:58:27 -0500, Rich Felker wrote:
> On Fri, Jun 16, 2017 at 09:11:35AM +0200, Jens Gustedt wrote:
> > A variant of this new lock algorithm has been presented at SAC'16,
> > see https://hal.inria.fr/hal-01304108. A full version of that paper
> > is available at https://hal.inria.fr/hal-01236734.
>
> Finally getting back to this, and trying to finish it in the current
> (1.1.19) release cycle...
great, I appreciate
since also for me this is half a year ago I have to wrap my head
around this and look into the details, again.
> When updating, can you trim down the proposed commit message a bit
> (or do you mind if I do so?) to focus on the change being made and
> the motivation without going into lots of speculation about related
> changes that could be made?
sure, I'll do that, the patches were clearly not supposed to be final
anyhow
> The context for this part changed slightly from commit
> c1e27367a9b26b9baac0f37a12349fc36567c8b6, but reversion of that patch
> could probably be merged with your patch since the old code is valid
> once the lock implementation is changed.
I'll look into that particular one.
> > void __lock(volatile int *l)
> > {
> > - if (libc.threads_minus_1)
> > - while (a_swap(l, 1)) __wait(l, l+1, 1, 1);
> > + if (!libc.threads_minus_1) return;
> > + /* fast path: INT_MIN for holding the lock, +1 to count
> > this
> > + thread in the critical section. */
>
> There seems to be some mixing of tabs and spaces here and in a few
> other lines. Tabs should be used for indentation levels, spaces (after
> any initial indent) to column-align. Generally musl style also has
> continuation comment lines begin with a * aligned with the * of the
> opening /* too.
Since I ran into similar comments before and I find it quite
frustrating and disruptive:
musl style is just not what my editor is tuned to, and I wouldn't
change that, just for musl.
Is there a tool (and command line arguments) that you could recommend,
and that one could just run before submitting any patches?
In my own projects I usually use astyle, which does a pretty good
job. Would you be able to release a list of astyle (or indent or
whatever) arguments that format code in a style accepted for musl?
> As long as you're including comments, which I think makes sense given
> that the algorithm is somewhat nontrivial, it might be nice to add a
> quick exposition on the states.
yes, very good idea
> As I understand them:
>
> - v==0 unlocked, no waiters
> - v>=0 unlocked, with v waiters contending
> - v<0 locked, with v-INT_MIN-1 waiters
sort of, see below
> One thing I don't recall understanding is why the lock owner is
> "included" in the waiter count, i.e. why v<0 indicates v-INT_MIN-1
> waiters rather than v-INT_MIN waiters. Is there some race it's
> avoiding?
yes.
The counter effectively is a congestion counter, not a wait counter,
that is it counts all threads that are inside the critical section.
This POV avoids a race around sending waiters to sleep: now that the
'int' of the futex contains all the state, if this would be a wait
count, waiters that want to go into sleep would have to change the
very state to which the sleep request is atomically bound.
As a consequence, under high congestion, many futex_wait calls could
fail because the 'int' changes too often. There is even potential for
some sort of ping-pong where threads hammer on the wait counter and
are never able to fall asleep because everybody is shouting their
"good night" - "good morning" messages in a loop.
Using the counter as a congestion counter avoids that. The fact that a
thread on the slow path wants to sleep doesn't change the state, and
thus the futex_wait calls have better chances to succeed. And at the
other end the unlock function can operate on that effectively, because
we can change the lock bit and the counter in one atomic operation.
If you are interested, in the paper that I mentioned is a proof that
such a system eventually calms down.
In summary, with a congestion count n we have at most 3xn changes to
the atomic state in total. With a wait count we have at least as much
with no upper bound.
> Overall I think it looks pretty much good to go, aside from minor
> style things. I'm open to your ideas on __futexwait, maybe just
> writing it inline here since it's only used in one place; while I
> don't like duplicating what __wait already does, __wait is mildly big
> and using your __futexwait version instead will probably offset the
> full size increase of the new lock (and maybe more) in programs that
> have no reason other than __lock to pull in __wait.
I'look into all of that, but I might need some days to do so.
Thanks
Jens
--
:: INRIA Nancy Grand Est ::: Camus ::::::: ICube/ICPS :::
:: ::::::::::::::: office Strasbourg : +33 368854536 ::
:: :::::::::::::::::::::: gsm France : +33 651400183 ::
:: ::::::::::::::: gsm international : +49 15737185122 ::
:: http://icube-icps.unistra.fr/index.php/Jens_Gustedt ::
Content of type "application/pgp-signature" skipped
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
