implementing Futex

implementing Futex

[Michael Schnell]

Hi experts,

I am planning to implement a Futex on the upcoming MMU-enabled NIOS
architecture.

I do know that the pure user-space part of the Futex is done in gLibC,
so that pthread_mutex...() automatically uses Futex, if same is
available in the underlying arch, and use some system call it it is not.
But for my first tests, I will not recompile gLibC but I do have a
working (on x86) Futex user code implementation, inspired by Ulrich
Drepper: "Futexes Are Tricky".

One of the tasks is to provide the appropriate atomic user-space
operations for the Futex implementation. I was able to successfully do
this for the x86 user space code and we have been discussing, how to do
 this with other archs.

Now in the Kernel code in "linux-2.6/arch/x86/include/asm/futex.h" there
are two different implementations for some atomic operations for the  Futex:

"futex_atomic_op_inuser()"    and
"futex_atomic_cmpxhg__inatomic()"


"futex_atomic_op_inuser()" seemingly accesses user space data while
being run in Kernel space (doing the .section __ex_table trick).

Questions:

Is this correct ?

In a non-SMP environment do we need to use really atomic code here, or
does futex_atomic_op_inuser() run with interrupt disabled, anyway?

When we are doing futex_atomic_op_inuser(), is this Kernel code running
in system mode so that we can disable the interrupt do protect the
atomic code in a non-SMP System ?

>From reading the code (futex_atomic_op_inuser() seems only to be called
once (in futex.c) ), it seems that futex_atomic_op_inuser() is not
really used at all. It seems that it'd only called for futex_wake, and
here the "Operation" is derived from the last parameter of the system
call, which the man page says is ignored.  So, are all the operations
implemented there really necessary or just "nice to have" ?


I see that futex_atomic_cmpxhg__inatomic() really is used by futex.c

"futex_atomic_cmpxhg__inatomic()" accesses the Futex without doing the
user-space-access-trick, so here, the MMU seems to be in User mode
configuration. So how does the Kernel use it ? (in the CPU's "user mode"
or "System mode", with interrupts enabled or disabled (protected against
concurrent SMP accesses by a spinlock) )

Any pointers ?

Thanks for all answers,
-Michael

Re: implementing Futex

[Arnd Bergmann]

On Thursday 13 August 2009, Michael Schnell wrote:
> I am planning to implement a Futex on the upcoming MMU-enabled NIOS
> architecture.

Ah, I'm always interested in new architectures. Are you already using
all the asm-generic header files that we have in 2.6.31? Please tell
me if you find problems with those.

> One of the tasks is to provide the appropriate atomic user-space
> operations for the Futex implementation. I was able to successfully do
> this for the x86 user space code and we have been discussing, how to do
>  this with other archs.
> 
> Now in the Kernel code in "linux-2.6/arch/x86/include/asm/futex.h" there
> are two different implementations for some atomic operations for the  Futex:
> 
> "futex_atomic_op_inuser()"    and
> "futex_atomic_cmpxhg__inatomic()"

Common trap. Just don't look at any x86 code when implementing
a new architecture. The code isn't necessarily bad, but much of
it has either too much compatibility crap for old interfaces, or
it optimizes some functionality much more than you'd care for.

In case of futex, look at how arch/sh does it. As Mike Frysinger
mentioned in http://lkml.org/lkml/2009/7/3/70 , the asm-generic
version is currently lacking functionality and we should use
the sh version for new stuff. 

Feel free to submit a patch that implements the operations correctly
for non-SMP architectures in include/asm-generic/futex.h.

> "futex_atomic_op_inuser()" seemingly accesses user space data while
> being run in Kernel space (doing the .section __ex_table trick).
> 
> Questions:
> 
> Is this correct ?

yes.
 
> In a non-SMP environment do we need to use really atomic code here, or
> does futex_atomic_op_inuser() run with interrupt disabled, anyway?

The sh version just disables interrupts to get atomicity.

> From reading the code (futex_atomic_op_inuser() seems only to be called
> once (in futex.c) ), it seems that futex_atomic_op_inuser() is not
> really used at all. It seems that it'd only called for futex_wake, and
> here the "Operation" is derived from the last parameter of the system
> call, which the man page says is ignored.  So, are all the operations
> implemented there really necessary or just "nice to have" ?

You misread futex_wake_op(). The operation comes from the second parameter
of the syscall, not the last one.

	Arnd <><

Re: implementing Futex

[Arnd Bergmann]

On Thursday 13 August 2009, Arnd Bergmann wrote:
> On Thursday 13 August 2009, Michael Schnell wrote:
> > I am planning to implement a Futex on the upcoming MMU-enabled NIOS
> > architecture.
> 
> Ah, I'm always interested in new architectures. Are you already using
> all the asm-generic header files that we have in 2.6.31? Please tell
> me if you find problems with those.

FWIW, I just had a look at git://sopc.et.ntust.edu.tw/git/linux-2.6.
Is that the one you are working on?

The code there is still based on 2.6.30, which does not yet have
all the new header file. When you (or someone else) do the port
to 2.6.31, please go through each header file and see if you can
change it to use the asm-generic version.

For most of the exported files, that will mean a user space ABI
change, so you need to rebuild your libc, but it will significantly
reduce the amount of (duplicate) code in the architecture tree.

	Arnd <><

Re: implementing Futex

[Michael Schnell]

Arnd Bergmann wrote:

>
> The sh version just disables interrupts to get atomicity.
>

Looking at the sh - code it seem that there is no real difference (but
the operation itself) between "futex_atomuic_op_inuser" and
"futex_atomic_cmp_inatomic".

Does that mean that both in fact do run in the same mode (I suppose
Kernel Mode and thus the CPU's "System Mode" rather than the CPU's "User
Mode".

With that - and supposing that as of Kernel 2.6.31 the sh code I see in
Kernel 2.6.30 is used in /asm/generic, I would be able to just use the
"generic" case for "implementing" a working Futex syscall for the NIOS).

This given, I could concentrate on the User part (pthread_mutex_XXX() in
glibc). What a nice option :)

-Michael

Re: implementing Futex

[Michael Schnell]

Arnd Bergmann wrote:
> On Thursday 13 August 2009, Michael Schnell wrote:
>> I am planning to implement a Futex on the upcoming MMU-enabled NIOS
>> architecture.
> 
> Ah, I'm always interested in new architectures. Are you already using
> all the asm-generic header files that we have in 2.6.31? Please tell
> me if you find problems with those.

Hi Arnd,
Thanks a lot for answering.

I've not really started coding, as I need to use the port of gcc 4,
Kernel, and libraries done by Montavista on behalf of Altera and going
to be managed by "uClinux-NIOS", currently in Taipei, Taiwan. The
releasing of the source code to "public domain" is expected within the
next few days and as of that I can start the project.

Currently I do my researches based on Kernel 2.6.30. I do suppose the
distribution will be upgraded to 2.6.31 soon.



> 
> Common trap. Just don't look at any x86 code when implementing
> a new architecture. The code isn't necessarily bad, but much of
> it has either too much compatibility crap for old interfaces, or
> it optimizes some functionality much more than you'd care for.
> 
> In case of futex, look at how arch/sh does it. As Mike Frysinger
> mentioned in http://lkml.org/lkml/2009/7/3/70 , the asm-generic
> version is currently lacking functionality and we should use
> the sh version for new stuff. 

OK, I'll take a look there.

> 
> Feel free to submit a patch that implements the operations correctly
> for non-SMP architectures in include/asm-generic/futex.h.

With NIOS this is not that obvious. At the moment we are discussing two
completely different ways to solve the problem of nonexistent atomic
operations.

A) do it like many other non-SMP archs do: in Kernel mode disable the
interrupt temporarily and in user mode (The hardware prevents disabling
interrupt here) use a common code page that holds the would-be atomic
code sequences and in Interrupt-exit code check the PC if we are in that
area and if necessary restart the atomic function.

B) take advantage of the possibility to implement custom instructions
with the FPGA based processor. Unfortunately it's not possible to
directly implement atomic operations nor is it possible to temporarily
disable interrupt with a custom instruction. So out first idea is to do
a hardware FUTEX with a custom instruction that can be used in
user-space to protect the three-instruction sequences that would
implement the atomic code sequences.

(A) would be more "standard" and is a well-verified paradigm, (B) would
offer less overhead (i.e. no overhead to UNRELATED interrupts at all)
and later could be portable to an SMP Kernel.

As even with B I suppose we would need to use the disable interrupt
trick in Kernel modem, I need to understand which code sequences really
are used and in which mode they run (the CPUs "System mode" or "user
mode", interrupt disabled or enabled.)


>> In a non-SMP environment do we need to use really atomic code here, or
>> does futex_atomic_op_inuser() run with interrupt disabled, anyway?
> 
> The sh version just disables interrupts to get atomicity.

Do you think I am correct assuming that sh CPU like NIOS also has a
"System Mode" (interrupt disabling is allowed) and a "User Mode" (trying
to disable the interrupt generates an "Illegal Instruction" trap). If so
 in that code sequence are in "System Mode".

> 
> You misread futex_wake_op(). The operation comes from the second parameter
> of the syscall, not the last one.
> 


Ooops, thanks a lot for looking this up for me !

I'll take another look !

Thanks again,
-Michael

Re: implementing Futex

[Michael Schnell]

Arnd Bergmann wrote:

> It sounds like this would be an optional feature of the FPGA code,
> and therefore I'd still suggest implementing option A with a compile-time
> choice so you don't need to have it. 

Yep that is the plan.

If the custom instruction is not provided either the "common area" trick
is used or (worse of course) the pthread_mutex calls fall back to use an
OS based mutex instead of a FUTEX.


>>  If so
>>  in that code sequence we are in "System Mode".
> 
> Yes.


Great !

Thus supposedly, as of Kernel 2.6.31, We don't need modifications in the
Kernel at all for NIOS supporting FUTEX. Only the user land library
needs to be tweaked.

OK, if we decide to use the "Common Area for atomic functions" trick, we
do need to create same in the Kernel startup code and enhance interrupt
return code appropriately. But I suppose we can borrow most of this from
the  Blackfin or sh implementation.

-Michael

Re: implementing Futex

[Michael Schnell]

Arnd Bergmann wrote:
> Well, if you want to support SMP, you really need full atomic operations,
> the easiest way for that would be the load-locked / store conditional
> method used on most RISC machines.

I see. But unless Altera provides an enhancement to the NIOS2 design, we
are lost here.

-Michael

Re: implementing Futex

[Arnd Bergmann]

On Friday 14 August 2009, Michael Schnell wrote:
> Does that mean that both in fact do run in the same mode (I suppose
> Kernel Mode and thus the CPU's "System Mode" rather than the CPU's "User
> Mode".

yes

> With that - and supposing that as of Kernel 2.6.31 the sh code I see in
> Kernel 2.6.30 is used in /asm/generic, I would be able to just use the
> "generic" case for "implementing" a working Futex syscall for the NIOS).

Well, I haven't put that code into asm-generic/futex.h yet and it's
too late for 2.6.31, but it should get there eventually, if one of us
four submits a tested patch ;-).

In the meantime, I suggest you use a plain copy of the sh version.

	Arnd <><

Re: implementing Futex

[Michael Schnell]

Arnd Bergmann wrote:,
>> From reading the code (futex_atomic_op_inuser() seems only to be called
>> once (in futex.c) ), it seems that futex_atomic_op_inuser() is not
>> really used at all. It seems that it'd only called for futex_wake, and
>> here the "Operation" is derived from the last parameter of the system
>> call, which the man page says is ignored.  So, are all the operations
>> implemented there really necessary or just "nice to have" ?
>
> You misread futex_wake_op(). The operation comes from the second parameter
> of the syscall, not the last one.

Really ?

In futex.c, I see

static int
futex_wake_op(u32 __user *uaddr1, int fshared, u32 __user *uaddr2,
	      int nr_wake, int nr_wake2, int op) {
  ..
 retry_private:
	op_ret = futex_atomic_op_inuser(op, uaddr2);
  ..
}
...
long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
		u32 __user *uaddr2, u32 val2, u32 val3) {	
  ..
  case   FUTEX_WAKE_OP:
		ret = futex_wake_op(uaddr, fshared, uaddr2,
                      val, val2, val3);
  ..
};
...
SYSCALL_DEFINE6(futex, u32 __user *, uaddr, int, op, u32, val,
		struct timespec __user *, utime, u32 __user *, uaddr2,
		u32, val3) {
  ..	
  return do_futex(uaddr, op, val, tp, uaddr2, val2, val3);
  ..
}

I don't see that the value in question is modified anywhere in that code.

What am I getting wrong ?

But I also don't see how this makes any sense.

-Michael

Re: implementing Futex

[Arnd Bergmann]

On Friday 14 August 2009, Michael Schnell wrote:
> Arnd Bergmann wrote:,
> >> From reading the code (futex_atomic_op_inuser() seems only to be called
> >> once (in futex.c) ), it seems that futex_atomic_op_inuser() is not
> >> really used at all. It seems that it'd only called for futex_wake, and
> >> here the "Operation" is derived from the last parameter of the system
> >> call, which the man page says is ignored.  So, are all the operations
> >> implemented there really necessary or just "nice to have" ?
> >
> > You misread futex_wake_op(). The operation comes from the second parameter
> > of the syscall, not the last one.
> 
> Really ?

Sorry, I misread the code as well, in a different way :(

> What am I getting wrong ?
> 
> But I also don't see how this makes any sense.

The man page says that the last parameter is ignored for op=FUTEX_WAKE,
which is correct. The code that you were looking at however is for
of=FUTEX_WAKE_OP, which is not documented as of manpages-3.22.

It was added by Jakub back in 2005, but if he wrote a documentation
for it, it never went into the man pages package. On a similar
note, Ingo also added other futex operations that are not documented
yet.

	Arnd <><

Re: implementing Futex

[Michael Schnell]

Arnd Bergmann wrote:
> The man page says that the last parameter is ignored for op=FUTEX_WAKE,
> which is correct. The code that you were looking at however is for
> of=FUTEX_WAKE_OP, which is not documented as of manpages-3.22.
> 
> It was added by Jakub back in 2005, but if he wrote a documentation
> for it, it never went into the man pages package. On a similar
> note, Ingo also added other futex operations that are not documented
> yet.
> 

Thus in any documented software, the quite complex stuff in
"futex_atomic_op_inuser", which is provided in several different
"futex.h" files for all those architectures *never* is used ?

Weired !

Is there any viable use for this ?

Would it not be appropriate either to do a documentation or to remove it ?

-Michael

Re: implementing Futex

[Arnd Bergmann]

On Friday 14 August 2009, Michael Schnell wrote:
> Arnd Bergmann wrote:
> > The man page says that the last parameter is ignored for op=FUTEX_WAKE,
> > which is correct. The code that you were looking at however is for
> > of=FUTEX_WAKE_OP, which is not documented as of manpages-3.22.
> > 
> > It was added by Jakub back in 2005, but if he wrote a documentation
> > for it, it never went into the man pages package. On a similar
> > note, Ingo also added other futex operations that are not documented
> > yet.
> > 
> 
> Thus in any documented software, the quite complex stuff in
> "futex_atomic_op_inuser", which is provided in several different
> "futex.h" files for all those architectures never is used ?

No, my point was that futex_atomic_op_inuser is indeed used
correctly, it's just not documented.
See http://lwn.net/Articles/148830/ for the initial posting

> Is there any viable use for this ?

glibc heavily uses it for the pthreads implementation.
 
> Would it not be appropriate either to do a documentation or to remove it ?

Adding documentation, yes.

	Arnd <><

Re: implementing Futex

[Michael Schnell]

Arnd Bergmann wrote:
> On Thursday 13 August 2009, Michael Schnell wrote:
>> I am planning to implement a Futex on the upcoming MMU-enabled NIOS
>> architecture.
> 
> Ah, I'm always interested in new architectures. Are you already using
> all the asm-generic header files that we have in 2.6.31? Please tell
> me if you find problems with those.

Thomas told me, that we'll have 2.6.31 very soon for mmu-NIOS
development, so we can use this as a basis for any appropriate work.

The recent discussion in lklm showed that a working Kernel code for
having non-SMP NIOS support the "futex" syscall is quite trivial and can
be borrowed from the "sh" implementation (simulating atomic code by
temporarily disabling the global interrupt). So we can concentrate on
the user land part.

While it seems, the hardware-Futex idea does not really hold, (e.g. as
signal handlers will dead-lock), I have a different solution in mind.

The Blackfin and other archs (supposedly sh) that - like NIOS - don't
feature atomic instructions, use a "common atomic area".

This area is prepared by the Kernel and holds functions for all
necessary would-be atomic functions in user-space and in Kernel space
(exchange, compare_and_exchange, add, sub, or, and, xor). The "atomic
area" is commonly accessible by all user land processes on the same
(virtual) address.

When the Kernel returns from interrupt, it checks if the PC had been in
the "atomic area" (which of course is quite unlikely) and if it is, it
checks if it is right within one of the functions (i.e. the result had
not been stored) and if yes, it resets the to-be restored PC to the
beginning of the appropriate function.

With an MMU, the area would be write-protected and executable and mapped
into the same location for any user land process. AFAIK, there are
standard means in the Kernel to allow for such a common code area (e.g.
used for fast system calls with some PC systems).

While this of course works (perfectly tested with Blackfin - though no
MMU there), I suppose we can achieve some improvements with FPGA
processors that allow for custom instructions to be executed in user-mode:

When using the "atomic area", the atomic functions can't be inlined, so
the cache usage is not perfect. The overhead in the ISR return code
should be as small as possible.

Moreover it should be possible to allow "hardware" (HDL-)  designers to
do additional improvements if they desire to take the pain in their designs.



So my suggestion is this:

With NIOS, doing a really good hardware design for atomic instructions
(i.e. load locked / store conditional) can't be done with user
instructions, as same can't do "normal" memory accesses through MMU and
cache. Such additional instructions would need to be provided by Altera
themselves (doable by an update of the Quartus software).

Thus, right now, the supposedly "best" way for a non-SMP but MMU enabled
NIOS-like FPGA-processor to provide some hardware support for atomicness
would be a custom instruction (say "lock 1") that disables the global
interrupt for the next three instructions by means of an additional
"custom ie" hardware flag.

Now atomic code could be like this:

 lock1
 ldw  r8, (r9)
 add  r7, r7, r8
 stw  r7, (r9)

or for compare_and_exchange
 lock1
 ldw  r8, (r9)
 bne  r7, r8, not_equal
 stw  r7, (r9)
not_equal:

Unfortunately, with NIOS, a custom  instruction can't access the global
interrupt bit of the processor, thus the designer would need to create a
gate for all possible hardware interrupt lines that are routed to the
processor (timing issues to be considered later...). This is not
possible with the standard design means (provided by< the
"SOPC-Builder") and would need a lot of additional HDL effort.

So would could add another variant of the custom instruction called
"lock 0". Same would reset the "custom ie" flag after reading it's state
into a register. With that the interrupt return code could very easily
detect the atomicness state without using an "atomic area".

Now atomic code could be like this:

 lock1
 ldw   r8, (r9)
 add   r7, r7, r8
 stw   r7, (r9)
 lock0 r0

or for compare_and_exchange
 lock1
 ldw  r8, (r9)
 bne  not_equal
 stw  r7, (r9)
not_equal:
 lock0 r0

The hardware designer could now either implement a hardware interrupt
disable (e.g. for three instructions) or just manage the flag by the
lock instruction variants without additional hardware implications.

The ISR return code now would do something like:

 lock0 r8

and when the flag  really had been set (which of course is very
unlikely) it would search backward from the return PC location (can be
in user space in user-space or in Kernel space) up to four instruction
words (32 bits each with the NIOS) to find the unique "lock1" code.

If it finds, that the store (on word address lock1 code + 3) has not yet
been executed, it sets the return to the address of the lock1 code to
have the complete sequence restarted. The very likely overhead to the
ISR is just two instructions: lock0 and conditional branch.

(If the hardware features the real interrupt disable using the "custom
ie" flag, of course the flag is _never_ set when the interrupt return
code is executed. Thus an improved hardware would not necessarily need a
modification in the Kernel configuration.)

I feel that this paradigm could provide excellent performance for user
and Kernel code, as well for Futex as for memory management library
code, minimal cache usage, very small ISR overhead, and minimal Kernel
footprint, and best extensibility for hardware designers.

Now my question is how - with an mmu-enabled NIOS - in the ISR return
code the user (or Kernel) space code near the return PC location can be
examination and whether the overhead to do that might be huge.

Thanks for any comments.

-Michael

Re: implementing Futex

[Mike Frysinger]

On Fri, Aug 14, 2009 at 07:44, Arnd Bergmann wrote:
> On Friday 14 August 2009, Michael Schnell wrote:
>> Does that mean that both in fact do run in the same mode (I suppose
>> Kernel Mode and thus the CPU's "System Mode" rather than the CPU's "User
>> Mode".
>
> yes
>
>> With that - and supposing that as of Kernel 2.6.31 the sh code I see in
>> Kernel 2.6.30 is used in /asm/generic, I would be able to just use the
>> "generic" case for "implementing" a working Futex syscall for the NIOS).
>
> Well, I haven't put that code into asm-generic/futex.h yet and it's
> too late for 2.6.31, but it should get there eventually, if one of us
> four submits a tested patch ;-).

well, that thread stalled because i posted a question wrt spinlock/irq
usage and didnt get a response ...
-mike

Re: [Nios2-dev] implementing Futex

[Michael Schnell]

After some more thoughts it's obvious that we should do the
return-PC-tweaking according to the "custom ie" flag in the ISR entry
code rather than in the Kernel exit code, as the exit will go to another
process than the one that was interrupted ans did set the flag. I don't
know if that is more difficult than using the exit code (as blackfin does).

-Michael

Re: implementing Futex

[Darren Hart]

Arnd Bergmann wrote:
> On Friday 14 August 2009, Michael Schnell wrote:
>> Arnd Bergmann wrote:
>>> The man page says that the last parameter is ignored for op=FUTEX_WAKE,
>>> which is correct. The code that you were looking at however is for
>>> of=FUTEX_WAKE_OP, which is not documented as of manpages-3.22.
>>>
>>> It was added by Jakub back in 2005, but if he wrote a documentation
>>> for it, it never went into the man pages package. On a similar
>>> note, Ingo also added other futex operations that are not documented
>>> yet.
>>>
>> Thus in any documented software, the quite complex stuff in
>> "futex_atomic_op_inuser", which is provided in several different
>> "futex.h" files for all those architectures never is used ?
> 
> No, my point was that futex_atomic_op_inuser is indeed used
> correctly, it's just not documented.
> See http://lwn.net/Articles/148830/ for the initial posting
> 
>> Is there any viable use for this ?
> 
> glibc heavily uses it for the pthreads implementation.
> 
>> Would it not be appropriate either to do a documentation or to remove it ?
> 
> Adding documentation, yes.

I also recently added two futex op codes which need to be added to the 
man page, but they are documented in Documentation/futex-requeue-pi.txt. 
   Documentation/pi-futex.txt documents the FUTEX_(UN)LOCK_PI opcodes 
which aren't in the man pages either.

-- 
Darren Hart
IBM Linux Technology Center
Real-Time Linux Team