Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1292549 > unrolled thread

Re: futex(3) man page, final draft for pre-release review

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: futex(3) man page, final draft for pre-release review Darren Hart <dvhart@infradead.org> - 2015-12-15 22:20 +0100
    Re: futex(3) man page, final draft for pre-release review "Michael Kerrisk (man-pages)" <mtk.manpages@gmail.com> - 2015-12-16 17:00 +0100
      Re: futex(3) man page, final draft for pre-release review Torvald Riegel <triegel@redhat.com> - 2015-12-18 12:20 +0100
        Re: futex(3) man page, final draft for pre-release review Jonathan Wakely <jwakely@redhat.com> - 2015-12-18 16:40 +0100
        Re: futex(3) man page, final draft for pre-release review "Michael Kerrisk (man-pages)" <mtk.manpages@gmail.com> - 2015-12-19 08:00 +0100
    Re: futex(3) man page, final draft for pre-release review Torvald Riegel <triegel@redhat.com> - 2015-12-18 12:30 +0100
      Re: futex(3) man page, final draft for pre-release review "Michael Kerrisk (man-pages)" <mtk.manpages@gmail.com> - 2015-12-19 08:00 +0100

#1292549 — Re: futex(3) man page, final draft for pre-release review

On Tue, Dec 15, 2015 at 02:43:50PM +0100, Michael Kerrisk (man-pages) wrote:
> Hello all,
> 
> After much too long a time, the revised futex man page *will*
> go out in the next man pages release (it has been merged
> into master).
> 
> There are various places where the page could still be improved,
> but it is much better (and more than 5 times longer) than the
> existing page.
> 
> The rendered version of the page is shown below, so that people
> can make any final comments/suggestions for improvements
> before the release (but of course I'll also take any
> improvements after release as well). The page source is
> available from the Git repo 
> (http://git.kernel.org/cgit/docs/man-pages/man-pages.git).
> 
> As I mention above, there are various places where the page
> could still be better, so the rendered text below is annotated
> with some FIXMEs, in case anyone wants to address these before
> release.
> 
> Thanks
> 
> Michael

Fantastic! A few comments below.

...

> 
>        When executing a futex operation that requests to block a thread,
>        the kernel will block only if the futex word has the  value  that
>        the  calling  thread  supplied  (as  one  of the arguments of the
>        futex() call) as the expected value of the futex word.  The load‐
>        ing  of the futex word's value, the comparison of that value with
>        the expected value, and the actual blocking  will  happen  atomi‐
> 
> FIXME: for next line, it would be good to have an explanation of
> "totally ordered" somewhere around here.
> 
>        cally  and totally ordered with respect to concurrently executing

Totally ordered with respect futex operations refers to semantics of the
ACQUIRE/RELEASE operations and how they impact ordering of memory reads and
writes. The kernel futex operations are protected by spinlocks, which ensure
that that all operations are serialized with respect to one another.

This is a lot to attempt to define in this document. Perhaps a reference to
linux/Documentation/memory-barriers.txt as a footnote would be sufficient? Or
perhaps for this manual, "serialized" would be sufficient, with a footnote
regarding "totally ordered" and a pointer to the memory-barrier documentation?

>        futex operations on the same futex word.  Thus, the futex word is
>        used to connect the synchronization in user space with the imple‐
>        mentation of blocking by the kernel.  Analogously  to  an  atomic
>        compare-and-exchange  operation  that  potentially changes shared
>        memory, blocking via a futex is an atomic compare-and-block oper‐
>        ation.

...

>    Futex operations
>        The futex_op argument consists of two parts: a command that spec‐
>        ifies  the  operation to be performed, bit-wise ORed with zero or
>        or more options that modify the behaviour of the operation.   The
>        options that may be included in futex_op are as follows:

...

> 
>        FUTEX_CLOCK_REALTIME (since Linux 2.6.28)
>               This   option   bit   can   be   employed  only  with  the
>               FUTEX_WAIT_BITSET and FUTEX_WAIT_REQUEUE_PI operations.

That caught me by surprise, but it's true. We reject FUTEX_WAIT |
FUTEX_CLOCK_REALTIME, even though FUTEX_WAIT treated as FUTEX_WAIT_BITSET with
val3=FUTEX_BITSET_MATCH_ANY.

Thomas, this looks like an oversight to me - do you recall if we intentionally
disallow FUTEX_CLOCK_REALTIME with FUTEX_WAIT?

>               If this option is set, the kernel  treats  timeout  as  an
>               absolute time based on CLOCK_REALTIME.
> 
>               If  this  option  is not set, the kernel treats timeout as
>               relative time, measured against the CLOCK_MONOTONIC clock.

...

>    Priority-inheritance futexes

...

>        *  If  the lock is owned and there are threads contending for the
>           lock, then the FUTEX_WAITERS bit shall be  set  in  the  futex
>           word's value; in other words, this value is:
> 
>               FUTEX_WAITERS | TID
> 
> 
>           (Note that is invalid for a PI futex word to have no owner and

                      ^ it

>           FUTEX_WAITERS set.)
...

>        FUTEX_TRYLOCK_PI (since Linux 2.6.18)
>               This operation tries to acquire the futex at uaddr.  It is
>               invoked when a user-space atomic acquire did  not  succeed
>               because the futex word was not 0.
> 
> 
> FIXME(Next sentence) The wording "The trylock in kernel" below 
> needs clarification. Suggestions?
> 
>               The trylock in kernel might succeed because the futex word

The lock acquisition might succeed in the kernel because the futex word

>               contains     stale     state     (FUTEX_WAITERS     and/or
>               FUTEX_OWNER_DIED).   This can happen when the owner of the
>               futex died.  User space cannot handle this condition in  a
>               race-free  manner,  but  the  kernel  can  fix this up and
>               acquire the futex.
> 
>               The uaddr2, val, timeout, and val3 arguments are ignored.

...

>    EXAMPLE
> 
> FIXME I think it would be helpful here to say a few more words about
>       the difference(s) between FUTEX_LOCK_PI and FUTEX_TRYLOCK_PI.
>       Can someone propose something?

Hrm. It seems pretty straightforward to me. I guess I'm too close to it. What
about it seems unclear and needs clarification?

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

[toc] | [next] | [standalone]

#1293066

Hello Darren,

On 12/15/2015 10:18 PM, Darren Hart wrote:
> On Tue, Dec 15, 2015 at 02:43:50PM +0100, Michael Kerrisk (man-pages) wrote:

[...]

>>        When executing a futex operation that requests to block a thread,
>>        the kernel will block only if the futex word has the  value  that
>>        the  calling  thread  supplied  (as  one  of the arguments of the
>>        futex() call) as the expected value of the futex word.  The load‐
>>        ing  of the futex word's value, the comparison of that value with
>>        the expected value, and the actual blocking  will  happen  atomi‐
>>
>> FIXME: for next line, it would be good to have an explanation of
>> "totally ordered" somewhere around here.
>>
>>        cally  and totally ordered with respect to concurrently executing
> 
> Totally ordered with respect futex operations refers to semantics of the
> ACQUIRE/RELEASE operations and how they impact ordering of memory reads and
> writes. The kernel futex operations are protected by spinlocks, which ensure
> that that all operations are serialized with respect to one another.
> 
> This is a lot to attempt to define in this document. Perhaps a reference to
> linux/Documentation/memory-barriers.txt as a footnote would be sufficient? Or
> perhaps for this manual, "serialized" would be sufficient, with a footnote
> regarding "totally ordered" and a pointer to the memory-barrier documentation?

I think I'll just settle for writing serialized in the man page, and be 
done with it :-).

>>        futex operations on the same futex word.  Thus, the futex word is
>>        used to connect the synchronization in user space with the imple‐
>>        mentation of blocking by the kernel.  Analogously  to  an  atomic
>>        compare-and-exchange  operation  that  potentially changes shared
>>        memory, blocking via a futex is an atomic compare-and-block oper‐
>>        ation.
> 
> ...
> 
>>    Futex operations
>>        The futex_op argument consists of two parts: a command that spec‐
>>        ifies  the  operation to be performed, bit-wise ORed with zero or
>>        or more options that modify the behaviour of the operation.   The
>>        options that may be included in futex_op are as follows:
> 
> ...
> 
>>
>>        FUTEX_CLOCK_REALTIME (since Linux 2.6.28)
>>               This   option   bit   can   be   employed  only  with  the
>>               FUTEX_WAIT_BITSET and FUTEX_WAIT_REQUEUE_PI operations.
> 
> That caught me by surprise, but it's true. We reject FUTEX_WAIT |
> FUTEX_CLOCK_REALTIME, even though FUTEX_WAIT treated as FUTEX_WAIT_BITSET with
> val3=FUTEX_BITSET_MATCH_ANY.

You uncover all sorts of interesting stuff when you document APIs ;-).

> 
> Thomas, this looks like an oversight to me - do you recall if we intentionally
> disallow FUTEX_CLOCK_REALTIME with FUTEX_WAIT?
> 
>>               If this option is set, the kernel  treats  timeout  as  an
>>               absolute time based on CLOCK_REALTIME.
>>
>>               If  this  option  is not set, the kernel treats timeout as
>>               relative time, measured against the CLOCK_MONOTONIC clock.
> 
> ...
> 
>>    Priority-inheritance futexes
> 
> ...
> 
>>        *  If  the lock is owned and there are threads contending for the
>>           lock, then the FUTEX_WAITERS bit shall be  set  in  the  futex
>>           word's value; in other words, this value is:
>>
>>               FUTEX_WAITERS | TID
>>
>>
>>           (Note that is invalid for a PI futex word to have no owner and
> 
>                       ^ it
> 
>>           FUTEX_WAITERS set.)
> ...
> 
>>        FUTEX_TRYLOCK_PI (since Linux 2.6.18)
>>               This operation tries to acquire the futex at uaddr.  It is
>>               invoked when a user-space atomic acquire did  not  succeed
>>               because the futex word was not 0.
>>
>>
>> FIXME(Next sentence) The wording "The trylock in kernel" below 
>> needs clarification. Suggestions?
>>
>>               The trylock in kernel might succeed because the futex word
> 
> The lock acquisition might succeed in the kernel because the futex word

Already did some rewording here which I think makes things better.

>>               contains     stale     state     (FUTEX_WAITERS     and/or
>>               FUTEX_OWNER_DIED).   This can happen when the owner of the
>>               futex died.  User space cannot handle this condition in  a
>>               race-free  manner,  but  the  kernel  can  fix this up and
>>               acquire the futex.
>>
>>               The uaddr2, val, timeout, and val3 arguments are ignored.
> 
> ...
> 
>>    EXAMPLE
>>
>> FIXME I think it would be helpful here to say a few more words about
>>       the difference(s) between FUTEX_LOCK_PI and FUTEX_TRYLOCK_PI.
>>       Can someone propose something?
> 
> Hrm. It seems pretty straightforward to me. I guess I'm too close to it. What
> about it seems unclear and needs clarification?

On reflection, I agree that the difference is perhaps well-enough explained.

Thanks for the comments, Darren.

Cheers,

Michael


-- 
Michael Kerrisk
Linux man-pages maintainer; http://www.kernel.org/doc/man-pages/
Linux/UNIX System Programming Training: http://man7.org/training/
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1294675

On Wed, 2015-12-16 at 16:54 +0100, Michael Kerrisk (man-pages) wrote:
> Hello Darren,
> 
> On 12/15/2015 10:18 PM, Darren Hart wrote:
> > On Tue, Dec 15, 2015 at 02:43:50PM +0100, Michael Kerrisk (man-pages) wrote:
> 
> [...]
> 
> >>        When executing a futex operation that requests to block a thread,
> >>        the kernel will block only if the futex word has the  value  that
> >>        the  calling  thread  supplied  (as  one  of the arguments of the
> >>        futex() call) as the expected value of the futex word.  The load‐
> >>        ing  of the futex word's value, the comparison of that value with
> >>        the expected value, and the actual blocking  will  happen  atomi‐
> >>
> >> FIXME: for next line, it would be good to have an explanation of
> >> "totally ordered" somewhere around here.
> >>
> >>        cally  and totally ordered with respect to concurrently executing
> > 
> > Totally ordered with respect futex operations refers to semantics of the
> > ACQUIRE/RELEASE operations and how they impact ordering of memory reads and
> > writes. The kernel futex operations are protected by spinlocks, which ensure
> > that that all operations are serialized with respect to one another.
> > 
> > This is a lot to attempt to define in this document. Perhaps a reference to
> > linux/Documentation/memory-barriers.txt as a footnote would be sufficient? Or
> > perhaps for this manual, "serialized" would be sufficient, with a footnote
> > regarding "totally ordered" and a pointer to the memory-barrier documentation?
> 
> I think I'll just settle for writing serialized in the man page, and be 
> done with it :-).

I'd prefer if you'd not just use "serialized" :)  Eventually, I'd prefer
if we can explain the semantics for the user in terms of the terminology
and semantics of the memory model of the programming language that users
will likely use to call futex ops (ie, C11 / C++11).

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

[toc] | [prev] | [next] | [standalone]

#1294968

On 18/12/15 12:11 +0100, Torvald Riegel wrote:
>On Wed, 2015-12-16 at 16:54 +0100, Michael Kerrisk (man-pages) wrote:
>> Hello Darren,
>>
>> On 12/15/2015 10:18 PM, Darren Hart wrote:
>> > On Tue, Dec 15, 2015 at 02:43:50PM +0100, Michael Kerrisk (man-pages) wrote:
>>
>> [...]
>>
>> >>        When executing a futex operation that requests to block a thread,
>> >>        the kernel will block only if the futex word has the  value  that
>> >>        the  calling  thread  supplied  (as  one  of the arguments of the
>> >>        futex() call) as the expected value of the futex word.  The load‐
>> >>        ing  of the futex word's value, the comparison of that value with
>> >>        the expected value, and the actual blocking  will  happen  atomi‐
>> >>
>> >> FIXME: for next line, it would be good to have an explanation of
>> >> "totally ordered" somewhere around here.
>> >>
>> >>        cally  and totally ordered with respect to concurrently executing
>> >
>> > Totally ordered with respect futex operations refers to semantics of the
>> > ACQUIRE/RELEASE operations and how they impact ordering of memory reads and
>> > writes. The kernel futex operations are protected by spinlocks, which ensure
>> > that that all operations are serialized with respect to one another.
>> >
>> > This is a lot to attempt to define in this document. Perhaps a reference to
>> > linux/Documentation/memory-barriers.txt as a footnote would be sufficient? Or
>> > perhaps for this manual, "serialized" would be sufficient, with a footnote
>> > regarding "totally ordered" and a pointer to the memory-barrier documentation?
>>
>> I think I'll just settle for writing serialized in the man page, and be
>> done with it :-).
>
>I'd prefer if you'd not just use "serialized" :)  Eventually, I'd prefer
>if we can explain the semantics for the user in terms of the terminology
>and semantics of the memory model of the programming language that users
>will likely use to call futex ops (ie, C11 / C++11).

FWIW a couple of uses of "serialized" were replaced in the C++11 final
draft due to comments pointing out that term is not defined in the
standard, see http://wg21.link/lwg1494 and http://wg21.link/lwg1504

That's not quite the same, because an ISO standard is supposed to
define all terms it uses, even for something like "serialized" where
the meaning is commonly understood by those in the field.

But I do like Torvald's suggestion to describe the semantics in
similar terms to C11, because that's the user-space model that
non-kernel folks (like me) are more likely to be familiar with.

Overall I like the new page a lot, I found it clear and readable. Nice
work.

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

[toc] | [prev] | [next] | [standalone]

#1295318

On 12/18/2015 12:11 PM, Torvald Riegel wrote:
> On Wed, 2015-12-16 at 16:54 +0100, Michael Kerrisk (man-pages) wrote:
>> Hello Darren,
>>
>> On 12/15/2015 10:18 PM, Darren Hart wrote:
>>> On Tue, Dec 15, 2015 at 02:43:50PM +0100, Michael Kerrisk (man-pages) wrote:
>>
>> [...]
>>
>>>>        When executing a futex operation that requests to block a thread,
>>>>        the kernel will block only if the futex word has the  value  that
>>>>        the  calling  thread  supplied  (as  one  of the arguments of the
>>>>        futex() call) as the expected value of the futex word.  The load‐
>>>>        ing  of the futex word's value, the comparison of that value with
>>>>        the expected value, and the actual blocking  will  happen  atomi‐
>>>>
>>>> FIXME: for next line, it would be good to have an explanation of
>>>> "totally ordered" somewhere around here.
>>>>
>>>>        cally  and totally ordered with respect to concurrently executing
>>>
>>> Totally ordered with respect futex operations refers to semantics of the
>>> ACQUIRE/RELEASE operations and how they impact ordering of memory reads and
>>> writes. The kernel futex operations are protected by spinlocks, which ensure
>>> that that all operations are serialized with respect to one another.
>>>
>>> This is a lot to attempt to define in this document. Perhaps a reference to
>>> linux/Documentation/memory-barriers.txt as a footnote would be sufficient? Or
>>> perhaps for this manual, "serialized" would be sufficient, with a footnote
>>> regarding "totally ordered" and a pointer to the memory-barrier documentation?
>>
>> I think I'll just settle for writing serialized in the man page, and be 
>> done with it :-).
> 
> I'd prefer if you'd not just use "serialized" :)  

Sigh :-). Okay--removed.

> Eventually, I'd prefer
> if we can explain the semantics for the user in terms of the terminology
> and semantics of the memory model of the programming language that users
> will likely use to call futex ops (ie, C11 / C++11).

And I'd be really happy to see such an explanation land in the page.

Cheers,

Michael



-- 
Michael Kerrisk
Linux man-pages maintainer; http://www.kernel.org/doc/man-pages/
Linux/UNIX System Programming Training: http://man7.org/training/
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1294692

On Tue, 2015-12-15 at 13:18 -0800, Darren Hart wrote:
> On Tue, Dec 15, 2015 at 02:43:50PM +0100, Michael Kerrisk (man-pages) wrote:
> > 
> >        When executing a futex operation that requests to block a thread,
> >        the kernel will block only if the futex word has the  value  that
> >        the  calling  thread  supplied  (as  one  of the arguments of the
> >        futex() call) as the expected value of the futex word.  The load‐
> >        ing  of the futex word's value, the comparison of that value with
> >        the expected value, and the actual blocking  will  happen  atomi‐
> > 
> > FIXME: for next line, it would be good to have an explanation of
> > "totally ordered" somewhere around here.
> > 
> >        cally  and totally ordered with respect to concurrently executing
> 
> Totally ordered with respect futex operations refers to semantics of the
> ACQUIRE/RELEASE operations and how they impact ordering of memory reads and
> writes. The kernel futex operations are protected by spinlocks, which ensure
> that that all operations are serialized with respect to one another.
> 
> This is a lot to attempt to define in this document. Perhaps a reference to
> linux/Documentation/memory-barriers.txt as a footnote would be sufficient? Or
> perhaps for this manual, "serialized" would be sufficient, with a footnote
> regarding "totally ordered" and a pointer to the memory-barrier documentation?

I'd strongly prefer to document the semantics for users here.  And I
don't think users use the kernel's memory model -- instead, if we assume
that most users will call futex ops from C or C++, then the best we have
is the C11 / C++11 memory model.  Therefore, if we want to expand that,
we should specify semantics in terms of as-if equivalence to C11 pseudo
code.  I had proposed that in the past but, IIRC, Michael didn't want to
add a C11 "dependency" in the semantics back then, at least for the
initial release.

Here's what I wrote back then (atomic_*_relaxed() is like C11
atomic_*(..., memory_order_relaxed), lock/unlock have normal C11 mutex
semantics):

========================

For example, we could say that futex_wait is, in terms of
synchronization semantics, *as if* we'd execute a piece of C11 code.
Here's a part of the docs for a glibc-internal futex wrapper that I'm
working on; this is futex_wait ... :

/* Atomically wrt other futex operations, this blocks iff the value at
   *FUTEX matches the expected value.  This is semantically equivalent to: 
     l = <get lock associated with futex> (FUTEX);
     wait_flag = <get wait_flag associated with futex> (FUTEX);
     lock (l);
     val = atomic_load_relaxed (FUTEX);
     if (val != expected) { unlock (l); return EAGAIN; }
     atomic_store_relaxed (wait_flag, 1);
     unlock (l);
     // Now block; can time out in futex_time_wait (see below)
     while (atomic_load_relaxed(wait_flag));

   Note that no guarantee of a happens-before relation between a woken
   futex_wait and a futex_wake is documented; however, this does not matter
   in practice because we have to consider spurious wake-ups (see below),
   and thus would not be able to reason which futex_wake woke us anyway.


... and this is futex_wake:

/* Atomically wrt other futex operations, this unblocks the specified
   number of processes, or all processes blocked on this futex if there are
   fewer than the specified number.  Semantically, this is equivalent to:
     l = <get lock associated with futex> (futex);
     lock (l);
     for (res = 0; processes_to_wake > 0; processes_to_wake--, res++) {
       if (<no process blocked on futex>) break;
       wf = <get wait_flag of a process blocked on futex> (futex);
       // No happens-before guarantee with woken futex_wait (see above)
       atomic_store_relaxed (wf, 0);
     }
     return res;

This allows a programmer to really infer the guarantees he/she can get
from a futex in terms of synchronization, without the docs having to use
prose to describe that.  This should also not constrain the kernel in
terms of how to implement it, because it is a conceptual as-if relation
(e.g., the kernel won't spin-wait the whole time, and we might want to
make this clear for the PI case).

Of course, there are several as-if representations we could use, and we
might want to be a bit more pseudo-code-ish to make this also easy to
understand for people not familiar with C11 (e.g., using mutex + condvar
with some relaxation of condvar guaranteees).

=========================

I will go through the discussion pointed out by Davidlohr next.

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

[toc] | [prev] | [next] | [standalone]

#1295319

On 12/18/2015 12:21 PM, Torvald Riegel wrote:
> On Tue, 2015-12-15 at 13:18 -0800, Darren Hart wrote:
>> On Tue, Dec 15, 2015 at 02:43:50PM +0100, Michael Kerrisk (man-pages) wrote:
>>>
>>>        When executing a futex operation that requests to block a thread,
>>>        the kernel will block only if the futex word has the  value  that
>>>        the  calling  thread  supplied  (as  one  of the arguments of the
>>>        futex() call) as the expected value of the futex word.  The load‐
>>>        ing  of the futex word's value, the comparison of that value with
>>>        the expected value, and the actual blocking  will  happen  atomi‐
>>>
>>> FIXME: for next line, it would be good to have an explanation of
>>> "totally ordered" somewhere around here.
>>>
>>>        cally  and totally ordered with respect to concurrently executing
>>
>> Totally ordered with respect futex operations refers to semantics of the
>> ACQUIRE/RELEASE operations and how they impact ordering of memory reads and
>> writes. The kernel futex operations are protected by spinlocks, which ensure
>> that that all operations are serialized with respect to one another.
>>
>> This is a lot to attempt to define in this document. Perhaps a reference to
>> linux/Documentation/memory-barriers.txt as a footnote would be sufficient? Or
>> perhaps for this manual, "serialized" would be sufficient, with a footnote
>> regarding "totally ordered" and a pointer to the memory-barrier documentation?
> 
> I'd strongly prefer to document the semantics for users here.  

Yes, please.

> And I
> don't think users use the kernel's memory model -- instead, if we assume
> that most users will call futex ops from C or C++, then the best we have
> is the C11 / C++11 memory model.  

Agreed.

> Therefore, if we want to expand that,

I think we should. And by we, I mean you ;-)

> we should specify semantics in terms of as-if equivalence to C11 pseudo
> code.  I had proposed that in the past but, IIRC, Michael didn't want to
> add a C11 "dependency" in the semantics back then, at least for the
> initial release.

I'd like to avoid it if possible, since many of us don't understand
all the details of those C11 semantics--and by us, I mean
me :-/. But maybe I'll be forced to educate myself better.

> Here's what I wrote back then (atomic_*_relaxed() is like C11
> atomic_*(..., memory_order_relaxed), lock/unlock have normal C11 mutex
> semantics):
> 
> ========================
> 
> For example, we could say that futex_wait is, in terms of
> synchronization semantics, *as if* we'd execute a piece of C11 code.
> Here's a part of the docs for a glibc-internal futex wrapper that I'm
> working on; this is futex_wait ... :
> 
> /* Atomically wrt other futex operations, this blocks iff the value at
>    *FUTEX matches the expected value.  This is semantically equivalent to: 
>      l = <get lock associated with futex> (FUTEX);
>      wait_flag = <get wait_flag associated with futex> (FUTEX);
>      lock (l);
>      val = atomic_load_relaxed (FUTEX);
>      if (val != expected) { unlock (l); return EAGAIN; }
>      atomic_store_relaxed (wait_flag, 1);
>      unlock (l);
>      // Now block; can time out in futex_time_wait (see below)
>      while (atomic_load_relaxed(wait_flag));
> 
>    Note that no guarantee of a happens-before relation between a woken
>    futex_wait and a futex_wake is documented; however, this does not matter
>    in practice because we have to consider spurious wake-ups (see below),
>    and thus would not be able to reason which futex_wake woke us anyway.
> 
> 
> ... and this is futex_wake:
> 
> /* Atomically wrt other futex operations, this unblocks the specified
>    number of processes, or all processes blocked on this futex if there are
>    fewer than the specified number.  Semantically, this is equivalent to:
>      l = <get lock associated with futex> (futex);
>      lock (l);
>      for (res = 0; processes_to_wake > 0; processes_to_wake--, res++) {
>        if (<no process blocked on futex>) break;
>        wf = <get wait_flag of a process blocked on futex> (futex);
>        // No happens-before guarantee with woken futex_wait (see above)
>        atomic_store_relaxed (wf, 0);
>      }
>      return res;
> 
> This allows a programmer to really infer the guarantees he/she can get
> from a futex in terms of synchronization, without the docs having to use
> prose to describe that.  This should also not constrain the kernel in
> terms of how to implement it, because it is a conceptual as-if relation
> (e.g., the kernel won't spin-wait the whole time, and we might want to
> make this clear for the PI case).
> 
> Of course, there are several as-if representations we could use, and we
> might want to be a bit more pseudo-code-ish to make this also easy to
> understand for people not familiar with C11 (e.g., using mutex + condvar
> with some relaxation of condvar guaranteees).

Okay -- I'm open to all of the above.

Cheers,

Michael



-- 
Michael Kerrisk
Linux man-pages maintainer; http://www.kernel.org/doc/man-pages/
Linux/UNIX System Programming Training: http://man7.org/training/
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web