[ELF] Fix two null pointer dereferences related to SHF_LINK_ORDER with --gc-sections

[MaskRay]

Summary

Fixes the lld side problem of PR43147.

If st_link(A)=B, and A has the SHF_LINK_ORDER flag, we may dereference
a null pointer if B is garbage collected.

The added test section-metadata.s also tests -r to improve -r + SHF_LINK_ORDER coverage.

[grimar]

Two questions:

1. Why it is not a error? As far I understood after reading comments for PR, this is what bfd would do?

(https://bugs.llvm.org/show_bug.cgi?id=43147#c8)

2. Should we instead disable GC for that case maybe?

[peter.smith]

This will definitely avoid a crash but I'm not sure if a program that can trigger the crash is well defined under garbage collection. For a section A with link order dependency on section B, with A live and B not live, there is a requirement to order section B with respect to the address of section A, and we can't know what the address is if B has been garbage collected. Making an arbitrary choice for the address will work for cases where removing B means that the order of A doesn't matter, however if the order of A does matter then we could get a run-time error.

I personally favour an error message, but I suppose a warning that the linker has made an arbitrary choice, or disabled garbage collection, could also work.

[MaskRay]

In D67754#1675049, @grimar wrote:

Two questions:

1. Why it is not a error? As far I understood after reading comments for PR, this is what bfd would do?

(https://bugs.llvm.org/show_bug.cgi?id=43147#c8)

I agree an error is the way to go. I had started to work on this patch before I read Peter's comment...

2. Should we instead disable GC for that case maybe?

Yes. I highly suspect the sanitizer has a bug. Whether or not it is a real bug, @manojgupta has to use --no-gc-sections.

I personally favour an error message, but I suppose a warning that the linker has made an arbitrary choice, or disabled garbage collection, could also work.

I thought ld.bfd would accept such cases. It accepts section-metadata.s in this patch but rejects https://bugs.llvm.org/show_bug.cgi?id=43147#c8
After some experiments, I believe it just checks the linked-to section of the first input section. Given the intention of the error, I think it is likely a oversight that it is more permissive. I'll file a bug on its Bugzilla.

Abandoned. We should go with D67761.

ELF/OutputSections.cpp

void OutputSection::finalize() {
   if (flags & SHF_LINK_ORDER) {
     // We must preserve the link order dependency of sections with the
     // SHF_LINK_ORDER flag. The dependency is indicated by the sh_link field. We
     // need to translate the InputSection sh_link to the OutputSection sh_link,
     // all InputSections in the OutputSection have the same dependency.
     if (auto *ex = dyn_cast<ARMExidxSyntheticSection>(first))
       link = ex->getLinkOrderDep()->getParent()->sectionIndex;
     else if (auto *d = first->getLinkOrderDep())
-      link = d->getParent()->sectionIndex;
+      link = d->getParent() ? d->getParent()->sectionIndex : 0;
   }
 
   if (type == SHT_GROUP) {
     finalizeShtGroup(this, first);
     return;
   }
 
   if (!config->copyRelocs || (type != SHT_RELA && type != SHT_REL))

ELF/Writer.cpp

 
 static bool compareByFilePosition(InputSection *a, InputSection *b) {
   InputSection *la = a->getLinkOrderDep();
   InputSection *lb = b->getLinkOrderDep();
   OutputSection *aOut = la->getParent();
   OutputSection *bOut = lb->getParent();
 
   if (aOut != bOut)
-    return aOut->sectionIndex < bOut->sectionIndex;
+    return !aOut || (bOut && aOut->sectionIndex < bOut->sectionIndex);
   return la->outSecOff < lb->outSecOff;
 }
 
 template <class ELFT> void Writer<ELFT>::resolveShfLinkOrder() {
   for (OutputSection *sec : outputSections) {
     if (!(sec->flags & SHF_LINK_ORDER))
       continue;
 

test/ELF/section-metadata.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
+# RUN: ld.lld --gc-sections --print-gc-sections %t.o -o %t | FileCheck --check-prefix=PRINT %s --implicit-check-not {{.}}
+# RUN: llvm-readelf -x .foo %t | FileCheck --check-prefix=HEX-GC %s
+
+# PRINT: removing unused section {{.*}}:(.bar1)
+
+# HEX-GC: 0100
+
+# RUN: ld.lld -r %t.o -o %t1.o
+# RUN: llvm-readelf -x .foo %t1.o | FileCheck --check-prefix=HEX-R %s
+# HEX-R: 0001
+
+.globl _start
+_start:
+  call foo0
+  call foo1
+  call .bar0
+
+.section .bar0,"a",@progbits
+.section .bar1,"a",@progbits
+
+.section .foo,"ao",@progbits,.bar0,unique,0
+.globl foo0
+foo0:
+  .byte 0
+
+## In the gc case, .bar1 is collected. We assume the linked-to section is SHN_UNDEF, so this
+## .foo is placed before the previous one, when they are combined into the output
+## section.
+.section .foo,"ao",@progbits,.bar1,unique,1
+.globl foo1
+foo1:
+  .byte 1