Linking Linux kernel with LLD

At this point I’m able to link Linux kernel with LLD and objcopy doen’t give me any errors.

The versions are:

Linux 4.10.0-rc5 (+ applied the patch from my previous message)
LLD 5.0.0 (GitHub - llvm-mirror/lld: Project moved to: https://github.com/llvm/llvm-project db83a5cc3968b3aac1dbe3270190bd3282862e74) (+ applied D28612)
GNU objcopy (GNU Binutils) 2.27

The problem is that the resulting kernel doesn’t boot. Does anybody have any suggestions on how to debug it or any guesses what did go wrong while linking?

Regards,
Dmitry

At this point I’m able to link Linux kernel with LLD and objcopy doen’t give me any errors.

The versions are:

Linux 4.10.0-rc5 (+ applied the patch from my previous message)
LLD 5.0.0 (GitHub - llvm-mirror/lld: Project moved to: https://github.com/llvm/llvm-project db83a5cc3968b3aac1dbe3270190bd3282862e74) (+ applied D28612)
GNU objcopy (GNU Binutils) 2.27

The problem is that the resulting kernel doesn’t boot. Does anybody have any suggestions on how to debug it or any guesses what did go wrong while linking?

Regards,
Dmitry

It should not boot atm, I believe.
I mentioned earlier, LLD currently generates wrong output for scripts like:

.rodata : {
 *(.rodata)
 *(.rodata.*)
 . = ALIGN(16);
 video_cards = .;
 *(.videocards)
 video_cards_end = .;​

That is sample from kernel realmode script. We produce wrong values for video_cards/video_cards_end.

Reduced sample is D29217, and thread with possible patch for that is D27415 which is under discussions now.

(Though there are also probably can be other issues, but that one is obvious atm).

I have a question also. You added -m elf_i386 to workaround emulation conflict issue in LLD, do you know

does output produced by BFD boot fine after that change ?

George.

I have a question also. You added -m elf_i386 to workaround emulation conflict issue in LLD, do you know
does output produced by BFD boot fine after that change ?
Doesn’t seem to affect BFD at all.

I have a question also. You added -m elf_i386 to workaround emulation conflict issue in LLD, do you know

does output produced by BFD boot fine after that change ?
Doesn’t seem to affect BFD at all.

Thanks !

​George.

I am unknown to all the stuff happening in and around LLVM, as i am interested in the project but had not time to dig in, yet. Just reading here and there a bit. But i wanted to share my 2 cents on the Lexer topic. I have written multiple lexer/parser for private purpose and recently one for our product to compile Mathematical expressions into an internal format for evaluation.

So far i usually write a Lexer which does the tokenizing on very basic rules. What is a number, what is a single symbolor a whole Identifier, and what to skip(like spaces). Each token has metadata like relative offset to the previous one. A Parser on top uses the lexer to process the Tokens. My approach of storing the relative offsets allows to regroup tokens to single symbols respecting whitespaces at a later time.

Let’s say we have(without quotes ofcourse)
“2 * 3”

The lexer always produces 3 tokens, 2 with the content and identification for a numeraical value(for 2 and 3) and one for an operator token. I can now either go for it and use these tokens to process as part of a mathematical evaluation or reconstruct the original stream. However this means that the stream below:

“(foo)”

is always lexed to 3 tokens (2 for the brackets and one for the identifier). The Parser then has the context on how to process these tokens.

My example has some drawbacks. By always splitting into the basic tokens and possibly regrouping you’ll need more rellocations for processing. And therefore losing performance. However i find this approach simple to test and write tests for.

The problem with the linker script grammar is that "foo *" and "foo*"
can't both tokenize to IDENTIFIER STAR, since in the context of a
wildcard expression they mean different things. It certainly can be
dealt with by making the tokens whitespace sensitive or doing post
processing, but it is certainly not a nice grammar.

Joerg

At this point I'm able to link Linux kernel with LLD and objcopy doen't
give me any errors.

The versions are:

Linux 4.10.0-rc5 (+ applied the patch from my previous message)
LLD 5.0.0 (GitHub - llvm-mirror/lld: Project moved to: https://github.com/llvm/llvm-project
db83a5cc3968b3aac1dbe3270190bd3282862e74) (+ applied D28612)
GNU objcopy (GNU Binutils) 2.27

The problem is that the resulting kernel doesn't boot. Does anybody have
any suggestions on how to debug it or any guesses what did go wrong while
linking?

Based on our experience getting FreeBSD working, we spent most time getting
the bootloader to accept the kernel.

To debug this, we mostly used two approaches:
- printf debugging in the bootloader (will require rebuilding the
bootloader multiple times)
- using objdump-like tools to look at the differences between a good (BFD
or gold linked) kernel and the failing (LLD-linked) kernel. (e.g. different
program header, different section contents in certain sections that the
bootloader looks at, etc.)

As far as the setup, I would recommend setting up qemu for actually running
the LLD-linked kernel and custom bootloader etc. because then you can have
a single script that rebuilds the bootloader and kernel and copies the
files to the VM. This reduces iteration time significantly.
Davide is the one that set that up and could probably provide more details,
but qemu docs might be good enough that you can set things up without much
effort (not sure though).

-- Sean Silva

At this point I'm able to link Linux kernel with LLD and objcopy doen't
give me any errors.

The versions are:

Linux 4.10.0-rc5 (+ applied the patch from my previous message)
LLD 5.0.0 (https://github.com/llvm-mirror/lld
db83a5cc3968b3aac1dbe3270190bd3282862e74) (+ applied D28612)
GNU objcopy (GNU Binutils) 2.27

The problem is that the resulting kernel doesn't boot. Does anybody have
any suggestions on how to debug it or any guesses what did go wrong while
linking?

As far as different things that can go wrong, some things to consider:

- LLD's output binary has the same (or similar) data as the BFD/gold output
binary. E.g. if the LLD binary is only half as big (or the PT_LOAD's that
the booloader looks at are half as bit), LLD might not be putting things
into the output or into the right output sections.

- The bootloader is looking for something in the dynamic symbol table, but
it isn't there. LLD might be resolving symbols differently.

- Section contents are different between LLD and BFD/gold. E.g. for freebsd
there is a "linker set" section which contains pointers to a bunch of
metadata structs that are needed. LLD was not relocating these correctly
because the symbols were not ending up in the output or something like that
(I forget exactly; Michael might remember better).

-- Sean Silva

As far as the setup, I would recommend setting up qemu for actually running the LLD-linked kernel and custom bootloader etc. because then you can have a single >script that rebuilds the bootloader and kernel and copies the files to the VM. This reduces iteration time significantly.

>As far as the setup, I would recommend setting up qemu for actually
running the LLD-linked kernel and custom bootloader etc. because then you
can have a single >script that rebuilds the bootloader and kernel and
copies the files to the VM. This reduces iteration time significantly.
>Davide is the one that set that up and could probably provide more
details, but qemu docs might be good enough that you can set things up
without much effort
>(not sure though).
>
>-- Sean Silva

By the way, yesterday I configured "smallest possible kernel", linked it
with BFD and launched under QEMU.
It is very small and takes a few seconds to build it from scratch for me,
used next article:
http://mgalgs.github.io/2015/05/16/how-to-build-a-custom-
linux-kernel-for-qemu-2015-edition.html

Now I am going to link it with LLD and check if it boots or now.
I think that should be fastest way - boot that little core and then enable
features
one by one or group by group and fix other things on the road.

My experience with linker bugs is that usually when things are mis-linked,
they are in the "core". E.g. startup code. So linking a small kernel may
not avoid as many bugs as you expect. For example, for FreeBSD, I don't
think we hit any issues in anything that could have been configured out.

-- Sean Silva

I have just checked it, the startup.elf and realmode.elf are fine. Only few changes are required for mainline kernel and one commit has to be reverted from lld and a few patches have to be applied.

The only step when I have used BFD is linking vmlinux. I have manually set LD variable in vmlinux_link() function. The vmlinux produced by lld doesn’t work yet. I will compare it to the one produced by GNU ld and try to figure out what is wrong (maybe you can suggest some useful objdump flags?)

Regards,
Dmitry

I have just checked it, the startup.elf and realmode.elf are fine. Only
few changes are required for mainline kernel and one commit has to be
reverted from lld and a few patches have to be applied.

The only step when I have used BFD is linking vmlinux. I have manually set
LD variable in vmlinux_link() function. The vmlinux produced by lld doesn't
work yet. I will compare it to the one produced by GNU ld and try to figure
out what is wrong (maybe you can suggest some useful objdump flags?)

With objdump I would recommend looking at program headers. In particular at
PT_LOAD's and the dynamic symbol table. Anything in the dynamic table is
also worth scrutinizing. One thing to keep an eye out for is
addresses/offsets that look "weird"; e.g. maybe the LLD version thinks a
symbol has address 0 or some insane value, vs BFD/gold which has a more
sane value.

Also, set up your system so that you rebuild/reinstall the bootloader too
so that you can add printf's in there to hone in on where the boot is going
wrong. The following workflow might be useful:

Step 1: add a printf to the bootloader to try to hone in on the exact place
where things are going wrong
Step 2: rebuild/reinstall/reboot the new bootloader with the LLD-linked
kernel
Step 3: boot and observe the print's (or maybe things crashed before
reaching your print, which is just as useful to know)
Step 4: think about what you observed in Step 3, then go to Step 1, using
these results to inform the next set of print's to add

With appropriate scripts (and a nice qemu setup), one iteration of this may
take 10 minutes (say). You may have to repeat it (say) 20 times to pinpoint
the exact place where things are going wrong (e.g. "the bootloader is
crashing in the memcpy for the second PT_LOAD" or "the boot is failing
because the bootloader is reading from a bogus address that it got from
this part of the binary"). That is 200 minutes which isn't too bad.

One thing to keep in mind is that this is not like debugging a race
condition or other nasty nondeterministic bug. This should be quite
deterministic so you just have to be systematic and keep narrowing down
until you find where things go wrong. It just requires determination.

Once narrowed-down, you should hopefully have a clear indication of where
to look in the binary and compare with gold/bfd and hopefully the
discrepancy is pretty clear. Then you "just" need to figure out why LLD
produces this result and what to change to avoid the problem.

One amazing tool if you are working with object files is "010 Editor"
010 Editor - Pro Text/Hex Editor | Edit 200+ Formats | Fast & Powerful | Reverse Engineering with a "binary template" for ELF
files. I think there is an ELF "binary template" for 010 Editor floating
around the net, but the best one is Michael's one that he has evolved over
the years (ask him for it). If you haven't done so already, I recommend
that you sit down at Michael's desk one day and work with him to debug one
of these nasty "what is wrong with this binary and why?" issues so you can
see him do his thing; he's amazingly good at it.

Also, if you need a quick refresher about this x86 boot stuff (to be
somewhat oriented about the environment in which all this stuff is
happening), you may want to skim:

-- Sean Silva

?>>Sean,
?>>

So as you noticed that linker script tokenization rule is not very trivial -- it is context sensitive. The current lexer is extremely >>simple and almost always works well. Improving "almost always" to "perfect" is not high priority because we have many more >>high priority things, but I'm fine if someone improves it. If you are interested, please take it. Or maybe I'll take a look at it. It >>shouldn't be hard. It's probably just a half day work.

Yeah. To be clear, I wasn't saying that this was high priority. Since I'm complaining so much about it maybe I should take a look >this weekend :)?

?>>As far as I know, the grammar is LL(1), so it needs only one push-back buffer. Handling INCLUDE directive can be a bit tricky >>though.
?>>

Maybe we should rename ScriptParserBase ScriptLexer.

That sounds like a good idea.

-- Sean Silva

Just in case, patch implementing this ideas is D29576. Works fine.

Imho looks fine either, except part that switches lexer modes. Probably I can impove it somehow if overall
direction is ok.

George.

I have just checked it, the startup.elf and realmode.elf are fine. Only few changes are required for mainline kernel and one >commit has to be reverted from lld and a few patches have to be applied.

The only step when I have used BFD is linking vmlinux. I have manually set LD variable in vmlinux_link() function. The vmlinux >produced by lld doesn’t work yet. I will compare it to the one produced by GNU ld and try to figure out what is wrong (maybe >you can suggest some useful objdump flags?)

Regards,
Dmitry

Just want to share latest results of investigation from my side.
I traced kernel linked with LLD to find where it fails.

LLD linked kernel starts execution and then I came up to protected_mode_jump​ function, which intention to jump to startup_64:
jmpl *%eax # Jump to the 32-bit entrypoint

(https://github.com/torvalds/linux/blob/5924bbecd0267d87c24110cbe2041b5075173a25/arch/x86/boot/pmjump.S#L76)

(https://github.com/torvalds/linux/blob/5924bbecd0267d87c24110cbe2041b5075173a25/arch/x86/kernel/head_64.S#L48)

It does not happen. Code executes right before jmpl and then fail on this call for me, so startup_64 never called.

startup_64 is a part of vmlinux binary. So as you said vmlinux has troubles and after doing readelf -a on LLD linked and bfd linked ones, I found that LLD outputs vmlinux as executable and bfd output is DSO. Had no chance to investigate why that happens, but pretty sure that is the not fine.

Invocation line for us does not contain -shared:

-m elf_x86_64
–script home/umb/linux_kernel/linux/linux/arch/x86/boot/compressed/vmlinux.lds
home/umb/linux_kernel/linux/linux/arch/x86/boot/compressed/head_64.o
home/umb/linux_kernel/linux/linux/arch/x86/boot/compressed/misc.o
home/umb/linux_kernel/linux/linux/arch/x86/boot/compressed/string.o
home/umb/linux_kernel/linux/linux/arch/x86/boot/compressed/cmdline.o
home/umb/linux_kernel/linux/linux/arch/x86/boot/compressed/error.o
home/umb/linux_kernel/linux/linux/arch/x86/boot/compressed/piggy.o
home/umb/linux_kernel/linux/linux/arch/x86/boot/compressed/cpuflags.o
-o vmlinux

George.

>I have just checked it, the startup.elf and realmode.elf are fine. Only
few changes are required for mainline kernel and one >commit has to be
reverted from lld and a few patches have to be applied.
>
>The only step when I have used BFD is linking vmlinux. I have manually
set LD variable in vmlinux_link() function. The vmlinux >produced by lld
doesn't work yet. I will compare it to the one produced by GNU ld and try
to figure out what is wrong (maybe >you can suggest some useful objdump
flags?)
>
>Regards,
>Dmitry

Just want to share latest results of investigation from my side.
I traced kernel linked with LLD to find where it fails.

LLD linked kernel starts execution and then I came up to
protected_mode_jump​ function, which intention to jump to startup_64:
    jmpl *%eax # Jump to the 32-bit entrypoint
(https://github.com/torvalds/linux/blob/5924bbecd0267d87c24110cbe2041b
5075173a25/arch/x86/boot/pmjump.S#L76)
(https://github.com/torvalds/linux/blob/5924bbecd0267d87c24110cbe2041b
5075173a25/arch/x86/kernel/head_64.S#L48)

It does not happen. Code executes right before jmpl and then fail on this
call for me, so startup_64 never called.

That address seems to come from here:
https://github.com/torvalds/linux/blob/5924bbecd0267d87c24110cbe2041b5075173a25/arch/x86/boot/pm.c#L124

protected_mode_jump(boot_params.hdr.code32_start,
   (u32)&boot_params + (ds() << 4));

That boot_params.hdr.code32_start field is probably either invalid (bad
reloc or something else causing the bootloader to calculate the wrong
address) or valid but the thing it thinks it is pointing to wasn't loaded
(missing PT_LOAD etc.).

Btw, how did you narrow it down to that specific instruction? That's pretty
handy.

startup_64 is a part of vmlinux binary. So as you said vmlinux has
troubles and after doing readelf -a on LLD linked and bfd linked ones, I
found that LLD outputs vmlinux as executable and bfd output is DSO. Had
no chance to investigate why that happens, but pretty sure that is the not
fine.

Invocation line for us does not contain -shared:

-m elf_x86_64
--script home/umb/linux_kernel/linux/linux/arch/x86/boot/
compressed/vmlinux.lds
home/umb/linux_kernel/linux/linux/arch/x86/boot/compressed/head_64.o
home/umb/linux_kernel/linux/linux/arch/x86/boot/compressed/misc.o
home/umb/linux_kernel/linux/linux/arch/x86/boot/compressed/string.o
home/umb/linux_kernel/linux/linux/arch/x86/boot/compressed/cmdline.o
home/umb/linux_kernel/linux/linux/arch/x86/boot/compressed/error.o
home/umb/linux_kernel/linux/linux/arch/x86/boot/compressed/piggy.o
home/umb/linux_kernel/linux/linux/arch/x86/boot/compressed/cpuflags.o
-o vmlinux

I think you can also get DSO with -pie I think, but I don't see that
either. This is quite mysterious. I also did a quick look at the linker
script and didn't see anything at first glance that would cause DSO output
(can linker scripts even control EType?). The bootloader might not even
look at the EType though.

-- Sean Silva

That address seems to come from >here: https://github.com/torvalds/linux/blob/5924bbecd0267d87c24110cbe2041b5075173a25/arch/x86/boot/pm.c#L124

protected_mode_jump(boot_params.hdr.code32_start,
  (u32)&boot_params + (ds() << 4));

That boot_params.hdr.code32_start field is probably either invalid (bad reloc or something else causing the bootloader to >calculate the wrong address) or valid but the thing it thinks it is pointing to wasn't loaded (missing PT_LOAD etc.).

boot_params.hdr.code32_start field is valid :slight_smile: It is 0x100000, like expected (btw thanks for those links on info how kernel boots, they were pretty useful). I checked it is valid using trace:

void go_to_protected_mode(void)
{
if (boot_params.hdr.code32_start == 0x100000)
  puts("go_to_protected_mode 1\n");
else
  puts("go_to_protected_mode 2\n");
while (1) {};

I had to use infinite loop here, because QEMU does not crash for me, but do domething what looks like reboot and clears all my traces output. Infinite loop helps to see traces text, if placed before dead point.

Btw, how did you narrow it down to that specific instruction? That's pretty handy.

I used very simple approach, did not know how to do that properly :), so inserted infinite loops in asm code:
foo:
jmp foo

And watched for behavior of QEMU. If it just hanged that was fine, I knew I am inside my loop, if QEMU rebooted, I knew it crashed at point I was looking for. So tracing bfd linked kernel and using documentation I found that startup_64 ?is next destination POI, and found that this instruction is the last before QEMU reboots for me.

I think you can also get DSO with -pie I think, but I don't see that either. This is quite mysterious. I also did a quick look at the >linker script and didn't see anything at first glance that would cause DSO output (can linker scripts even control EType?). The >bootloader might not even look at the EType though.

-- Sean Silva

I think best way would be to look at what is invocation for BFD here. I am pretty sure -shared/-pie flag is just lost because of some configuration issue, probably it checks that we are running bfd may be. Just a guess.

George.

I think you can also get DSO with -pie I think, but I don’t see that either. This is quite mysterious. I also did a quick look at the >>linker script and didn’t see anything at first glance that would cause DSO output (can linker scripts even control EType?). The >>bootloader might not even look at the EType though.

>That address seems to come from >here: https://github.com/
torvalds/linux/blob/5924bbecd0267d87c24110cbe2041b
5075173a25/arch/x86/boot/pm.c#L124
>
>```
>protected_mode_jump(boot_params.hdr.code32_start,
> (u32)&boot_params + (ds() << 4));
>```
>
>That boot_params.hdr.code32_start field is probably either invalid (bad
reloc or something else causing the bootloader to >calculate the wrong
address) or valid but the thing it thinks it is pointing to wasn't loaded
(missing PT_LOAD etc.).

boot_params.hdr.code32_start field is valid :slight_smile: It is 0x100000, like
expected

Then I suspect that that segment isn't being loaded. Is there a PT_LOAD
that covers that address? Is the bootloader loading it?

(btw thanks for those links on info how kernel boots, they were pretty
useful).

I'm glad you found it useful! Those articles are amazing.

I checked it is valid using trace:

void go_to_protected_mode(void)
{
if (boot_params.hdr.code32_start == 0x100000)
  puts("go_to_protected_mode 1\n");
else
  puts("go_to_protected_mode 2\n");
while (1) {};

I had to use infinite loop here, because QEMU does not crash for me, but
do domething what looks like reboot and clears all my traces output.
Infinite loop helps to see traces text, if placed before dead point.

>
>Btw, how did you narrow it down to that specific instruction? That's
pretty handy.

I used very simple approach, did not know how to do that properly :), so inserted
infinite loops in asm code:
foo:
jmp foo

I suspected something like this :slight_smile: I've had to do that in the past. btw if
you are ever in a tight spot, a good thing to remember is EB FE (jmp -2)
which encodes an infinite loop on x86 (all modes, even 16bit I believe). It
is small so can easily be patched over most instruction using a hex editor
if necessary.

-- Sean Silva

Then I suspect that that segment isn’t being loaded. Is there a PT_LOAD that covers that address? Is the bootloader loading it?

I think you can also get DSO with -pie I think, but I don’t see that either. This is quite mysterious. I also did a quick look at the >linker script and didn’t see anything at first glance that would cause DSO output (can linker scripts even control EType?). The >bootloader might not even look at the EType though.