[ELF] - Linkerscript: fixed non-determinism when handling MEMORY.

[grimar]

Summary

When findMemoryRegion do search to find a region for output section it
iterates over MemoryRegions which is DenseMap and so does not
guarantee iteration in insertion order. As a result selected region depends
on its name and not on its definition position
Testcase shows the issue, patch fixes it. Behavior after applying the patch
seems consistent with bfd.

[grimar]

• Improved testcase.
• Fixed using of destroyed object happened when doing Script->MemoryRegions[Alias] = Script->MemoryRegions[Name];, where MemoryRegions is MapVector. Right side returned reference to element of internal vector and it was resized and invalidated when called operator[] for left side assignment, so dead value was assigned finally.

[ruiu]

LGTM

ELF/LinkerScript.h

public:
   bool HasSectionsCommand = false;
   bool ErrorOnMissingSection = false;
 
   // List of section patterns specified with KEEP commands. They will
   // be kept even if they are unused and --gc-sections is specified.
   std::vector<InputSectionDescription *> KeptSections;
 
   // A map from memory region name to a memory region descriptor.
-  llvm::DenseMap<llvm::StringRef, MemoryRegion *> MemoryRegions;
+  llvm::MapVector<llvm::StringRef, MemoryRegion *> MemoryRegions;
 
   // A list of symbols referenced by the script.
   std::vector<llvm::StringRef> ReferencedSymbols;
 };
 
 extern LinkerScript *Script;
 
 } // end namespace elf
 } // end namespace lld
 
 #endif // LLD_ELF_LINKER_SCRIPT_H

ELF/ScriptParser.cpp

void ScriptParser::readRegionAlias() {
   expect(",");
   StringRef Name = next();
   expect(")");
 
   if (Script->MemoryRegions.count(Alias))
     setError("redefinition of memory region '" + Alias + "'");
   if (!Script->MemoryRegions.count(Name))
     setError("memory region '" + Name + "' is not defined");
-  Script->MemoryRegions[Alias] = Script->MemoryRegions[Name];
+  Script->MemoryRegions.insert({Alias, Script->MemoryRegions[Name]});
 }
 
 void ScriptParser::readSearchDir() {
   expect("(");
   StringRef Tok = next();
   if (!Config->Nostdlib)
     Config->SearchPaths.push_back(unquote(Tok));
   expect(")");

test/ELF/linkerscript/memory3.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: echo "MEMORY { ram2 (ax) : ORIGIN = 0x1000, LENGTH = 1K   \
+# RUN:                ram1 (ax) : ORIGIN = 0x4000, LENGTH = 1K } \
+# RUN: SECTIONS {}" > %t1.script
+# RUN: ld.lld -o %t1 --script %t1.script %t
+# RUN: llvm-objdump -section-headers %t1 | FileCheck %s
+
+# RUN: echo "MEMORY { ram1 (ax) : ORIGIN = 0x1000, LENGTH = 1K   \
+# RUN:                ram2 (ax) : ORIGIN = 0x4000, LENGTH = 1K } \
+# RUN: SECTIONS {}" > %t2.script
+# RUN: ld.lld -o %t2 --script %t2.script %t
+# RUN: llvm-objdump -section-headers %t2 | FileCheck %s
+
+## Check we place .text into first defined memory region with appropriate flags.
+# CHECK: Sections:
+# CHECK: Idx Name  Size      Address
+# CHECK:   0       00000000 0000000000000000
+# CHECK:   1 .text 00000001 0000000000001000
+  
+.section .text.foo,"ax",%progbits
+foo:
+  nop