Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <20140814222227.GN12888@brightrain.aerifal.cx>
Date: Thu, 14 Aug 2014 18:22:27 -0400
From: Rich Felker <dalias@...c.org>
To: musl@...ts.openwall.com
Subject: Re: My current understanding of cond var access restrictions

On Thu, Aug 14, 2014 at 10:47:24PM +0200, Jens Gustedt wrote:
> Am Donnerstag, den 14.08.2014, 14:23 -0400 schrieb Rich Felker:
> > On Thu, Aug 14, 2014 at 08:12:46PM +0200, Jens Gustedt wrote:
> > > I don't think they are too bad, actually. They help to distinguish two
> > > phases for a waiting thread. In the first, he has released the mutex
> > > and no signal or broadcast has been issued. A thread should never
> > > attempt to relock the mutex and/or return to user space during that
> > > phase.
> > > 
> > > And then the second phase after such a signal or broadcast, where any
> > > wakeup could be legitimate and in the worst case just be spurious.
> > 
> > Yes. Really the only reason I dislike sequence numbers is the
> > theoretical possibility of wrapping after 2<<32 signals. This would
> > require extreme scheduling delays to realize without a signal handler
> > intentionally preventing the waiter from making forward progress, so
> > it's unlikely to impact anything, but it still seems wrong.
> 
> Wrapping alone doesn't matter, waiters don't have just to do an
> equality test on the sequence counter.

They do, in the futex wait syscall. As soon as the mutex is unlocked,
they are formally a waiter, and must be releasable by signal or
broadcast. If a signal happens before the futex wait syscall is made,
or while the futex wait syscall is pending restart due to a signal
handler running, the waiter depends on the sequence number having
changed in order not to block in futex wait.

> So with the traditional int
> (and supposing that there is no UB because of the overflow) even
> negative values may occur with no harm. The thing that would do harm
> would be the waiter that is woken up *exactly* 2<<32 sequence points
> later and concludes that the world hasn't changed. Really hard to
> generate a test program for that bug :)

Actually I don't think it's hard at all. Just make a signal handler
that blocks reading from a pipe, and issue 2<<32 cv signals before
writing to the pipe.

> But why not give it a 64 bit integer then? It seems to me that
> __u.i[9] is unused, so with a shift of the whole crowd _c_seq could
> get two slots.

Because futex only uses 32-bit integers.

> Ah, and for the records for the discussion on mutex we had before,
> pthread_mutex_t also seems to have an empty slot, namely __u.__i[3],
> no? Or was it intended that _c_count be in that, and using __u.i[5]
> for it is a typo?

I'd have to look -- maybe there is an extra empty slot. I laid the
slots out so that the same indices would work on 32- and 64-bit archs,
but it might be possible to get more slots by making different 32- and
64-bit orderings.

Rich

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.