Skip to contentSkip to conversation

implementing Futex

DISCUSSION Michael Schnell 4 participants 16 messages Aug 13, 2009 – Aug 31, 2009 2 messages not in the archive

lore
Share & tools
lore
#0 lore raw

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 ?

Quoted 1 line

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

#1 lore raw
Quoted 2 lines · Michael Schnell

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.

Quoted 10 lines

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.

Quoted 6 lines

"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.

Quoted 2 lines

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.

Quoted 6 lines

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 <><
#2 lore raw
Quoted 7 lines · Arnd Bergmann
Quoted 2 lines · Michael Schnell

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 <><
#3 lore raw
In reply to Arnd Bergmann
Quoted 3 lines · Arnd Bergmann

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

#4 lore raw
Quoted 3 lines · Michael Schnell

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

Quoted 3 lines

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 <><
#5 lore raw
Quoted 7 lines · Arnd Bergmann
Quoted 3 lines · Michael Schnell

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

Quoted 7 lines
Quoted 3 lines

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

#6 lore raw
In reply to Arnd Bergmann
Quoted 7 lines · Arnd Bergmann
Quoted 2 lines · Michael Schnell

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.

Quoted 10 lines

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.

Quoted 3 lines

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.)

Quoted 4 lines
Quoted 2 lines

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".

Quoted 4 lines

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

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): [email protected]

#9 lore raw
Quoted 3 lines · Arnd Bergmann

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.

Quoted 4 lines
Quoted 2 lines

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

#10 lore raw
In reply to a message not in the archive
Quoted 3 lines · Arnd Bergmann

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

#11 lore raw
In reply to Arnd Bergmann

Arnd Bergmann wrote:,

Quoted 9 lines
Quoted 6 lines

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

#12 lore raw
Quoted 8 lines · Michael Schnell

Arnd Bergmann wrote:,

Quoted 7 lines
Quoted 6 lines

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" ?

Quoted 4 lines
Quoted 2 lines

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 :(

Quoted 3 lines

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 <><
#13 lore raw
Quoted 9 lines · Arnd Bergmann

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

#14 lore raw
Quoted 11 lines · Michael Schnell
Quoted 9 lines · Arnd Bergmann

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.

Quoted 3 lines

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

Quoted 1 line

Is there any viable use for this ?

glibc heavily uses it for the pthreads implementation.

Quoted 1 line

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

Adding documentation, yes.

	Arnd <><
#15 lore raw
Quoted 19 lines · Arnd Bergmann
Quoted 5 lines · Michael Schnell
Quoted 4 lines · Arnd Bergmann

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.

Quoted 8 lines
Quoted 5 lines

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

Quoted 7 lines
Quoted 1 line

Is there any viable use for this ?

glibc heavily uses it for the pthreads implementation.

Quoted 1 line

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.

Signature · 3 lines
Darren Hart
IBM Linux Technology Center
Real-Time Linux Team
#16 lore raw
In reply to Arnd Bergmann
Quoted 7 lines · Arnd Bergmann
Quoted 2 lines · Michael Schnell

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

#17 lore raw

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