Section garbage collection problem

[Denys Vlasenko <vda dot linux at googlemail dot com>]

Hi,

I need your advice.

I am implementing section garbage collection at build time
for Linux kernel, using ld --gc-sections.

I have a problem where ld is unable to discard
a lot of unused code. The description follows. It's long, sorry.

Linux kernel tries to improve performance by dynamically patching
its code at runtime. There are several tricks for that in kernel
and they are all using similar tricks with special sections.
I will describe it on the example of LOCK prefix.

If you boot SMP kernel on UP machine, kernel will replace
LOCK prefixes with NOPs.

In order to achieve this, each lock prefix's location is remembered
in section .smp_locks, like this:

#define LOCK_PREFIX \
               ".section .smp_locks,\"a\"\n"      \
               "     .quad 661f\n"                \
               ".previous\n"                      \
               "661: lock; "
...
static inline void clear_bit(int nr, volatile void *addr) {
        __asm__ __volatile__(
                LOCK_PREFIX
                "btrl %1,%0"
                :ADDR
                :"dIr" (nr));
}

This works with ordinary link, without --gc-sections.

In order for it to continue working when I use ld --gc-sections,
I need to instruct ld to not discard .smp_locks sections at link time
by changing kernel's link script:

-       *(.smp_locks)
+       KEEP(*(.smp_locks)) /* points to lock prefixes */

Otherwise, ld will discard .smp_locks sections, because
there is no references to them from anywhere.

This works, but after a bit of investigation I see that
a lot of unused functions are still not discarded.

Any function which has LOCK prefix in its body will not be discarded,
even if it is not used anywhere in the kernel, because ld will see
a reference from (not discarded) .smp_locks section into this function!

In the example above, any function with clear_bit() inline called
(possibly as part of another inline or macro, etc)
will have LOCK prefix in its body and will not be discarded.

I attempted to fix this problem by presenting ld with more
accurate information about section interdependencies.
First, I do NOT mark .smp_locks with KEEP().
Second, I insert an extra relocation at each LOCK prefix,
which points to corresponding .smp_locks section.
Third, I split one big .smp_locks into many small
.smp_locksXXXX sections, so that ld can discard those which are
unused. So:

-       *(.smp_locks)
+       *(.smp_locks*) /* points to lock prefixes */

Here the problem starts. I cannot generate unique .smp_locksXXXX
section name. I try to use line number and current time for that:

#define UNIQUE_SECTION_NAME2(n,l,t) #n "." #l "." t
#define UNIQUE_SECTION_NAME1(n,l,t) UNIQUE_SECTION_NAME2(n,l,t)
#define UNIQUE_SECTION_NAME(name)   UNIQUE_SECTION_NAME1(name,__LINE__,__TIME__)
#define REFERENCE(label) ".reloc ., R_X86_64_NONE, " #label
#define SMP_LOCKS        ".section " UNIQUE_SECTION_NAME(.smp_locks) ",\"a\""

SMP_LOCKS results in ".section .smp_locks.65.23:36:21,\"a\"".
LOCK_PREFIX define now looks like this:

#define LOCK_PREFIX \
                       SMP_LOCKS "\n"                  \
               "660:\n"                                \
               "       .quad 661f\n"                   \
               "       .previous\n"                    \
               "661:   "REFERENCE(660b) "\n"           \
               "       lock; "

This works, ld now sees which .smp_locks.NN.HH:MM:SS sections are referenced
by which .text.function_name sections. And it does not increase kernel's
size, because relocations of type R_xxxx_NONE do not use any space
in final kernel image.

But it works very marginally. Many (like 95%) of unused functions are still
not discarded! The root of a problem is inlines. Above mentioned inline:

static inline void clear_bit(int nr, volatile void *addr) {
        __asm__ __volatile__(
		LOCK_PREFIX
                "btrl %1,%0"
                :ADDR
                :"dIr" (nr));
}

will evaluate LOCK_PREFIX once, at the moment gcc encounters inline definition,
and create .smp_locks.NN.HH:MM:SS section with _same _name_ everywhere
it is called (within one .c file). IOW:

file.c
======
#include "bitops.h"
void f_used() { clear_bit(n, addr); }
void unused() { clear_bit(n, addr); }

In file.o, both clear_bit's will create ONE .smp_locks.65.23:36:21 section,
not TWO sections with different names!

And .text.unused will not be discarded by ld because of this chain of relocs:

... -> .text.f_used -> .smp_locks.65.23:36:21 -> .text.unused

I nned to fix it so that it looks like this:

... -> .text.f_used -> .smp_locks.AAAA -> .text.f_used
       .text.unused -> .smp_locks.BBBB -> .text.unused

And ld will throw .text.unused and .smp_locks.BBBB sections away.

How to achieve this?

I thin one way is to add support for assembler to have a special
section directive a-la

	.section_with_unique_sfx .smp_locks

which will produce section names like .smp_locks01983475928752857970.

It will practically assure that with
#define SMP_LOCKS        ".section_with_unique_sfx .smp_locks,\"a\""
each call to clear_bit will create new, unique .smp_locksXXXXX section.


What do you think about it? Will such patch to as be acceptable in principle?
Maybe you can think about better solution?

Thanks,
--
vda