LGTM

Nice. Even if the probability of a failure for each relocation is very low, we have huge number of relocations. Apparently the latter overwhelms the former!

Thank you for doing this.

LGTM

It is a good idea to add a test to catch this though.

LGTM

LGTM

LGTM

OK, then moving just below

LGTM

LGTM

LGTM

I'm curious what kind of application you want to use this option for.

I believe that your benchmark is inappropriate and does not correctly capture correct performance characteristics of PLT entries of different sizes.

Although I understand that reporting an error is sometimes useful, are you sure that that's the behavior that users want? I wonder if we would end up adding --really-allow-undefined in the future to override this new behavior.

In D60765#1471332, @MaskRay wrote:

In D60765#1471271, @ruiu wrote:

By the way I think your finding that this struct can be 12 bytes long instead of 16 bytes long is pretty interesting. Previously, we found that making this struct as small as possible does matter in terms of performance perhaps due to memory locality. So, shaving off 4 bytes from this might make a noticeable difference in speed. Do you want to try? (If not I'll do that sometime in the future.)

I tested it https://reviews.llvm.org/differential/diff/195689/ Making SectionPiece 12 bytes has some negative impact on the performance (likely due to extra OutputSec packing/unpacking instructions). So it isn't worth to do that.

Before: 17.177 +- 0.133 seconds time elapsed ( +- 0.77% )
After: 17.279 +- 0.171 seconds time elapsed ( +- 0.99% )

LGTM

LGTM

LGTM

In D59780#1471032, @xiangzhangllvm wrote:

We are Ok with with the 2-PLT scheme.

I think I'd like **more opinions from others**.  **there are announcements but no design discussions**

Hi, Fangrui, the 2-PLT scheme has pass the ABI discussions, not H.J just made it by only himself.

**gives performance numbers demonstrating this second PLT scheme has indeed the cache-locality merit and is better than the alternative 24-byte PLT entry scheme**.

Yes, We really have not performance evidence, but this design is really more performance in theory, and this scheme has done years , and nothing went wrong.
The 24-bit plt is beautiful, but it is not the overwhelming reason to overthrow the big previous works.

By the way I think your finding that this struct can be 12 bytes long instead of 16 bytes long is pretty interesting. Previously, we found that making this struct as small as possible does matter in terms of performance perhaps due to memory locality. So, shaving off 4 bytes from this might make a noticeable difference in speed. Do you want to try? (If not I'll do that sometime in the future.)

No, the actual issue is that a non-empty PT_LOAD segment that starts with an empty symbol only section does not have a file offset that is congruent modulo the page size. As a result, the output is not a valid ELF.

Please commit this first.

In D60765#1471247, @MaskRay wrote:

Notice that {get,set}OutputOff don't race with accesses to InputOff/Hash/TailHash/Live. So the goal has achieved. Also with this scheme we don't sacrifice the bits of Hash -- Hash member still has the full 32 bits.

I get your idea now: splitting OutputOff to make space for Hash (to keep it 32 bits). However, the benchmark shows 31-bit Hash works just fine.

For a huge internal executable (1.6GiB clang -O3), Strings in StringTableBuilder::finalizeStringTable contains at most 310253 elements.
Every pair has a probability 2^(-31) of colliding. The expected number of pair-wise collisions is 2^(-31) * C(310253,2) ~= 22.41. Note, this number is pair-wise - if 5 elements hash to the same value, they count as C(5,2) collisions. Assume every but one bucket has at most 1 element, that bucket with collision has at most 7 elements => The degraded performance is nearly nothing.

So for simplicity, I prefer leaving OutputOff as is.

Changes to the linker script processor oftentimes has subtle implications and in order to review such change I have to stop and think. But for this patch I took too much time. Apologies for the delay.

IIUC, you are fixing an issue that a segment whose size is 0 doesn't have a file offset that is congruent modulo page size. Is this correct?

It doesn't race. Since OutputOffHi is not a bitfield, it takes a different memory location. Concurrent accesses to different memory locations don't race. I still don't understand the split of OutputOff. If you pack other members adjacent to OutputOffHi and read them, it may race with the write of OutputOffHi.

Committed as r358638.

Sorry, I though that I replied to this thread.

InputFile abstracts the concept of a file containing symbols. In each parse() function, we parse a symbol table and then insert symbols to the symbol table. parse() is part of a symbol resolution process step.

In D60765#1469826, @MaskRay wrote:

In D60765#1469825, @ruiu wrote:

The point of my last comment was that, with the new layout, accesses to OutputOffHi don't race with accesses to Live or Hash, as they are now in different non-integer-bitmap struct members.

I don't understand the split of uint64_t OutputOff -> uint8_t OutputOffHi+uint32_t OutputOffLo (40 bits).

uint32_t InputOff;

uint32_t Hash;
uint8_t Live : 1;
uint8_t TailShardId : 5;
uint8_t OutputOffHi;  // this may be written concurrently with the read of `Live` -> race

uint32_t OutputOffLo;

The point of my last comment was that, with the new layout, accesses to OutputOffHi don't race with accesses to Live or Hash, as they are now in different non-integer-bitmap struct members.

LGTM, please commit.

In D60765#1469717, @MaskRay wrote:

uint32_t Hash;
uint8_t Live : 1;
uint8_t TailShardId : 5;
uint8_t OutputOffHi;
uint32_t OutputOffLo;

Do you mean

// 16 bytes -> 12 bytes
uint32_t InputOff;

uint32_t Live : 1
uint32_t Hash : 18;
uint32_t TailShardId : 5;
uint32_t OutputOffHi : 8;

uint32_t OutputOffLo;

Looks fine.

LGTM

There should not be a fundamental reason for parallelForEach to not be reentrant, so we eventually want to fix it so that we can call the function without worrying the nested condition. For the time being, we should be able to detect the error condition more easily by adding the assertions.

The root cause of the problem here is that the API doesn't have enough rationale to choose a complex format than a simpler one, even though it was set just a few years ago and there's no historical burden to do so. I was repeatedly told that it is too late to change the ABI but that wasn't convincing (that's why the same topic came up many times in the thread) because no one said how much it is too late -- what thing is already done and if we redo it how long does it likely to take, etc. So, Carlos, thank you for giving some examples of the stuff that's already done to some programs.

This change seems fine as long as it doesn't cause any performance regression. Did you run lld with this change to see if the increase of hash collision doesn't have a negative impact?

This change seems correct, although it is a bit tricky and perhaps unnecessary to move . backwards in many linker scripts.

If you worry about the cost of assigning a boolean value to the thread-local variable, I'd think that's really cheap and negligible. This function is not called too casually, because distributing jobs to threads waiting in the thread pool is not cheap. Compared to that, these assignments are virtually nothing.

I will keep this patch for a day to give sbc100 to take a look.

Sorry, I missed this one.

LGTM

LGTM

• 80 columns

• address review comments
• simplify

This patch naturally changes the order how strings are placed in a merged string section. In addition to that, with this change, strings equal to or shorter than 4 bytes long are not merged. This is why.

I don't think you have to call std::stable_sort. Something like this should suffice.

This patches changes the order how input files are parsed. The other approach is to parse input files normally and then sort the list of object files so that crtend.o is at the end of the input list. I wonder if the latter is simpler. What do you think?

Yeah, if recent versions of clang and gcc are happy with the code, I wouldn't add the extra braces as Fangrui suggested. Thank you for your effort to fix warnings, though. It's important to keep our code warning-free.

• rebased

LGTM

• address review comment

• remove dead code

LGTM

LGTM

I will do that.

Overall looking good.

In D59780#1452530, @xiangzhangllvm wrote:

Hi MaskRay, I tested your idea by changing the patch:

diff --git a/ELF/Arch/X86_64.cpp b/ELF/Arch/X86_64.cpp
index 7d7cc00..14fb6b2 100644
--- a/ELF/Arch/X86_64.cpp
+++ b/ELF/Arch/X86_64.cpp
@@ -553,11 +553,11 @@ void IntelCET::writePlt(uint8_t *Buf, uint64_t GotPltEntryAddr,
                         unsigned RelOff) const {
   const uint8_t Inst[] = {
       0xf3, 0x0f, 0x1e, 0xfa,       // endbr64
-      0xff, 0x25, 0,    0,    0, 0, // jmpq *got(%rip)
-      0x66, 0x0f, 0x1f, 0x44, 0, 0, // nop
+      0xf2, 0xff, 0x25, 0,    0,    0, 0, // jmpq *got(%rip)
+      0x0f, 0x1f, 0x44, 0, 0, // nop
   };
   memcpy(Buf, Inst, sizeof(Inst));
-  write32le(Buf + 6, GotPltEntryAddr - PltEntryAddr - 10);
+  write32le(Buf + 7, GotPltEntryAddr - PltEntryAddr - 11);
 }

After that, GNU objdump can symbolize .plt.sec, it is really the BND prefix factor.

[xiangzh1@shliclel100 /export/users.shared/xiangzh1/LLVM_ORG/test]$ld.lld -e func1 t.o t1.so -o tout-new
[xiangzh1@shliclel100 /export/users.shared/xiangzh1/LLVM_ORG/test]$objdump -d tout-new

tout-new:     file format elf64-x86-64


Disassembly of section .text:

0000000000201000 <func1>:
  201000:       e8 3b 00 00 00          callq  201040 <func2@plt>
  201005:       e8 46 00 00 00          callq  201050 <func3@plt>
  20100a:       c3                      retq

Disassembly of section .plt:

0000000000201010 <.plt>:
  201010:       ff 35 f2 1f 00 00       pushq  0x1ff2(%rip)        # 203008 <_DYNAMIC+0x1008>
  201016:       ff 25 f4 1f 00 00       jmpq   *0x1ff4(%rip)        # 203010 <_DYNAMIC+0x1010>
  20101c:       0f 1f 40 00             nopl   0x0(%rax)
  201020:       f3 0f 1e fa             endbr64
  201024:       68 00 00 00 00          pushq  $0x0
  201029:       e9 e2 ff ff ff          jmpq   201010 <func1+0x10>
  20102e:       66 90                   xchg   %ax,%ax
  201030:       f3 0f 1e fa             endbr64
  201034:       68 01 00 00 00          pushq  $0x1
  201039:       e9 d2 ff ff ff          jmpq   201010 <func1+0x10>
  20103e:       66 90                   xchg   %ax,%ax

Disassembly of section .plt.sec:

0000000000201040 <func2@plt>:
  201040:       f3 0f 1e fa             endbr64
  201044:       f2 ff 25 cd 1f 00 00    bnd jmpq *0x1fcd(%rip)        # 203018 <func2>
  20104b:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)

0000000000201050 <func3@plt>:
  201050:       f3 0f 1e fa             endbr64
  201054:       f2 ff 25 c5 1f 00 00    bnd jmpq *0x1fc5(%rip)        # 203020 <func3>
  20105b:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)

But I think this is not the good reason to change the ABI, it is better to change the objdump tool's code to fit the new plt.
GCC have implemented this ABI for one year, It will be very hard to push the changing work.

LGTM

I'd write a comment explaining why we are handling debug sections in a special way, but that can be done later. Please submit. Thank you for doing this!

LGTM

In D59553#1459554, @avl wrote:

I thought that address 0 is a good candidate to represent an invalid address, as nullptr is usually represented by address 0. I wonder why we want to use UINT64_MAX-2 instead of 0.

using 0 in this case could lead to following problems :

1. on some platforms 0 is a valid address. i.e. image base starts from 0. In that case no way to differentiate valid address from invalid one just by checking for 0.