Re: [RFC] unify semaphore implementations

Russell King
2005-04-28T22:40:05Z

On Thu, Apr 28, 2005 at 02:29:26PM -0400, Benjamin LaHaise wrote:
> Please review the following series of patches for unifying the
> semaphore implementation across all architectures (not posted as
> they're about 350K), as they have only been tested on x86-64. The
> code generated is functionally identical to the earlier i386
> variant, but since gcc has no way of taking condition codes as
> results, there are two additional instructions inserted from the
> use of generic atomic operations. All told the >6000 lines of code
> deleted makes for a much easier job for subsequent patches changing
> semaphore functionality. Cheers,

I'm not sure why we're doing this, apart from a desire to unify stuff.
What happened to efficiency and performance?

It is my understanding that the inline part of the semaphore
implementation was one of the critical areas - critical enough to
warrant coding it in assembly for some people.

So, I set about testing this implementation against the ARM
implementation. For this, I used this code:

void it(struct semaphore *sem, int *val)
{
down(sem);
*val = *val + 1;
up(sem);
}

which is a relatively simple test case.

The ARM assembly implementation for this gave:

str lr, [sp, #-4]!
@ down_op
mrs ip, cpsr @ local_irq_save
orr lr, ip, #128
msr cpsr_c, lr
ldr lr, [r0]
subs lr, lr, #1
str lr, [r0]
msr cpsr_c, ip @ local_irq_restore
movmi ip, r0
blmi __down_failed
ldr r3, [r1, #0]
add r3, r3, #1
str r3, [r1, #0]
@ up_op
mrs ip, cpsr @ local_irq_save
orr lr, ip, #128
msr cpsr_c, lr
ldr lr, [r0]
adds lr, lr, #1
str lr, [r0]
msr cpsr_c, ip @ local_irq_restore
movle ip, r0
blle __up_wakeup
ldr pc, [sp], #4

Stack: 1 location
Registers: 3 on top of the two arguments
Instructions: 23, 23 in the common execution path.

The atomic-op based implementation gave:

stmfd sp!, {r4, r5, lr}
mov r5, r1
mov r4, r0
mrs r2, cpsr @ local_irq_save
orr r1, r2, #128
msr cpsr_c, r1
ldr r3, [r0, #0]
sub r3, r3, #1
str r3, [r0, #0]
msr cpsr_c, r2 @ local_irq_restore
cmp r3, #0
blt .L8
.L4: ldr r3, [r5, #0]
add r3, r3, #1
str r3, [r5, #0]
mrs r2, cpsr @ local_irq_save
orr r1, r2, #128
msr cpsr_c, r1
ldr r3, [r4, #0]
add r3, r3, #1
str r3, [r4, #0]
msr cpsr_c, r2 @ local_irq_restore
cmp r3, #0
mov r0, r4
ldmgtfd sp!, {r4, r5, pc}
ldmfd sp!, {r4, r5, lr}
b up_wakeup
.L8: bl down_failed
b .L4

Stack: 3 locations
Registers: 5 on top of the two arguments
Instructions: 29, 27 in the common execution path.

So, Ben's implementation is more expensive in terms of stack usage,
register usage, and number of instructions.

Why is this? The answer is that gcc is unable to properly optimise
for ARM - I've no idea why. One such simple thing is that the
sequence:

blt .L8
.L4:
...
.L8: bl down_failed
b .L4

can be easily rewritten as:

bllt down_failed

Another reason for the extra code bloat is that GCC can't propagate
PSR flags between the sub/add instructions across a memory barrier
(which local_irq_restore is.)

This makes the ARM assembly code implementation superior to any unified
version, no matter how you look at it from efficiency or performance
points of view. The _only_ win is that of unification.

However, given that the kernel has bloated itself by 300K per stable
kernel series on ARM for the same functionality, I'd prefer to keep
my more efficient higher performance smaller code size semaphores
please.

--
Russell King
Linux kernel 2.6 ARM Linux - http://www.arm.linux.org.uk/
maintainer of: 2.6 Serial core