Page MenuHomePhabricator

ELF: Add basic partition data structures and behaviours.
ClosedPublic

Authored by pcc on Apr 5 2019, 7:09 PM.

Details

Summary

This change causes us to read partition specifications from partition
specification sections and split output sections into partitions according
to their reachability from partition entry points.

This is only the first step towards a full implementation of partitions. Later
changes will add additional synthetic sections to each partition so that
they can be loaded independently.

Depends on D60242

Diff Detail

Repository
rL LLVM

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
pcc added inline comments.Apr 16 2019, 4:41 PM
lld/ELF/Driver.cpp
1396 ↗(On Diff #193996)

With fatal we can avoid needing to worry about what happens in case of overflow. Since I'd expect this error to be uncommon I don't think we need to provide a great experience here.

1648 ↗(On Diff #193996)

The file name is accessible in readSymbolPartitionSection via S->File if we wanted to print it there, though I'm not sure if it would be useful since a user hitting this limit would probably want to see the names of all partitions, not just the one that overflowed. I'd probably punt on giving a more useful error message here for now unless/until there's evidence that people are hitting this case frequently.

lld/ELF/SyntheticSections.cpp
3258 ↗(On Diff #193996)

Yes, I think that would be better, done. I'm not sure why I originally wrote it this way.

lld/ELF/SyntheticSections.h
1063 ↗(On Diff #193996)

We previously couldn't have inlined the body because it depended on the definition of Partitions below (and Partitions depends on the definition of Partition). But now that Partitions is a vector we can inline it.

grimar added inline comments.Apr 17 2019, 2:17 AM
lld/ELF/Driver.cpp
1387 ↗(On Diff #193996)

Ah, right.

1396 ↗(On Diff #193996)

Ok, but now after Partitions became a vector, I guess you can just remove this 254 limitation?

1648 ↗(On Diff #193996)

I meant you could report here errors from below like

"filename1: partitions cannot be used with the SECTIONS command"
"filename2: partitions cannot be used with the PHDRS command"

i.e.:

llvm::erase_if(InputSections, [](InputSectionBase *S) {
  if (S->Type == SHT_LLVM_SYMPART) {
    <report such errors here>

    readSymbolPartitionSection<ELFT>(S);
    return true;
   }

So that you'd be able to report the file names of the objects which have the SHT_LLVM_SYMPART sections.
Does it make sense?

pcc updated this revision to Diff 195664.Apr 17 2019, 7:49 PM
pcc marked 3 inline comments as done.
  • Adjust error message format
lld/ELF/Driver.cpp
1396 ↗(On Diff #193996)

The Partition fields in Symbol and InputSectionBase are 8 bits wide, so we can't remove the limitation without making the fields wider. I'm not sure if we should do that because I don't think we should devote too much space in these common data structures to this feature without a good reason (e.g. users need >254 partitions).

1648 ↗(On Diff #193996)

Makes sense now, but that means that we'd get the error even for files with SHT_LLVM_SYMPART sections that end up being ignored due to not being in dynsym. It would probably be better to print these errors in readSymbolPartitionSection once we know that we're going to create a partition.

I have no more comments/questions, thanks! (last suggestion/question is inlined)

lld/ELF/Driver.cpp
1396 ↗(On Diff #193996)

Ok, thanks for the explanation! Perhaps it worst to add this information to the documentation in D60242 then? It wasn't obvious for me where this limitation technically comes from.

MaskRay added inline comments.Apr 18 2019, 7:41 AM
lld/ELF/InputSection.h
78 ↗(On Diff #195664)

unsigned : 1;

lld/ELF/Writer.cpp
763 ↗(On Diff #195664)

The comment 8 bits may be elaborated a bit.

lld/test/ELF/partitions.s
4 ↗(On Diff #195664)

-symbols -> -dyn-syms?

e.g. llvm-readelf -S -dyn-syms %t

32 ↗(On Diff #195664)

Indent instructions?

MaskRay added inline comments.Apr 18 2019, 8:08 AM
lld/ELF/InputSection.cpp
1091 ↗(On Diff #195664)

This probably needs a comment.

lld/ELF/MarkLive.cpp
202 ↗(On Diff #195664)

minimum -> meet?

pcc updated this revision to Diff 198356.May 6 2019, 3:36 PM
pcc marked 9 inline comments as done.
  • Rebase
  • Address review comments
pcc added inline comments.May 6 2019, 3:36 PM
lld/ELF/Driver.cpp
1396 ↗(On Diff #193996)

I added a note to the documentation as well as a comment here.

lld/ELF/InputSection.cpp
1091 ↗(On Diff #195664)

Done. Also realised that I don't have a test for this code, so I added one.

lld/ELF/MarkLive.cpp
202 ↗(On Diff #195664)

Hmm, that's the correct set theoretical term, but "minimum" seems more intuitive to me. I decided to reword it as meet (i.e. the "minimum")

lld/test/ELF/partitions.s
4 ↗(On Diff #195664)

That would not be sufficient to test the property that we're interested in here because f[3-6] are not exported.

32 ↗(On Diff #195664)

I don't think we have a consistent style for whether or not to indent, so I left things as is.

MaskRay added inline comments.May 7 2019, 3:21 AM
lld/test/ELF/partitions.s
4 ↗(On Diff #195664)

Then use either llvm-readobj or llvm-readelf, but not -elf-output-style=GNU.

( llvm-readobj -elf-output-style=GNU has a peculiarity: it supports llvm-readobj specific options but not llvm-readelf options. In any case, I've done something to improve their compatibility.) If you decide to go with llvm-readelf, --long-option will be better than -long-option :)

pcc updated this revision to Diff 198490.May 7 2019, 9:30 AM
  • Switch to using llvm-readelf
pcc marked an inline comment as done.May 7 2019, 9:30 AM

This looks good to me, but I do not think I am a proper person to give a final accept.
Minor nits/suggestions are inline.

lld/ELF/Driver.cpp
101 ↗(On Diff #198490)

nit: I am not sure how much Partitions = {{}}; is readable,
so I would replace with Partitions = {Partition()};
Though IMO any of these lines looks probably a bit better than these two lines.

1419 ↗(On Diff #198490)

It seems to me this is an overoptimization for such place.

What do you think about the following?

Partition P = {PartName};
Sym->Partition = P.getNumber();
grimar added inline comments.May 13 2019, 1:41 AM
lld/ELF/Driver.cpp
1419 ↗(On Diff #198490)

Oops. My version was wrong. But anyways something like:

Partitions.push_back({PartName});
Sym->Partition = Partitions.back().getNumber();
pcc updated this revision to Diff 199324.May 13 2019, 1:41 PM
pcc marked an inline comment as done.
  • Use a one-liner to initialize Partitions
pcc marked 2 inline comments as done.May 13 2019, 1:42 PM
pcc added inline comments.
lld/ELF/Driver.cpp
101 ↗(On Diff #198490)

Partitions = {Partition()}; works for me.

1419 ↗(On Diff #198490)

Agreed that optimization isn't a consideration at all here.

I don't think your suggested code will continue to work once we start adding more fields (for synthetic sections etc.) to the Partition data structure, unless we add a constructor that takes a name. See: https://github.com/pcc/llvm-project/blob/d40cc2e48b560445c4c741cc72a8c6bab47fb2eb/lld/ELF/SyntheticSections.h#L1040

I think I'd argue that it is sightly clearer to let the object be default constructed here and then initialize the field by name.

ruiu added a comment.May 17 2019, 6:11 AM

Do you have another change for adding synthetic sections for partitioning? This change looks pretty straightforward to me, although I'd like to somehow continue using the term "Live" instead of Partition is zero" to explain liveness in code and comments, though.

lld/ELF/Driver.cpp
1378 ↗(On Diff #199324)

Could you add a brief comment as to what this Sym is? I think this is a "root" symbol for each partition.

1400 ↗(On Diff #199324)

I first thought that we may want to completely ban linker scripts when this feature is in use, but no, we can't do that, because on Linux libc.so is actually a linker script...

lld/ELF/InputSection.h
78 ↗(On Diff #199324)

It's not clear to me why you needed a one bit padding here.

although I'd like to somehow continue using the term "Live" instead of Partition is zero" to explain liveness in code and comments, though.

I think this is fine... After all all S->Live uses have been changed to S->isLive()

ruiu added a comment.May 20 2019, 12:10 AM

although I'd like to somehow continue using the term "Live" instead of Partition is zero" to explain liveness in code and comments, though.

I think this is fine... After all all S->Live uses have been changed to S->isLive()

Yeah, but killing it is S->Partition = 0 which isn't very intuitive.

pcc updated this revision to Diff 200852.May 22 2019, 5:47 PM
pcc marked 4 inline comments as done.
  • Address review comments
  • Rebase
pcc added a comment.May 22 2019, 5:49 PM

Do you have another change for adding synthetic sections for partitioning?

Yes, I was going to send it out once it was ready, but I'll try to send it out as soon as I can so you can see what it looks like. In the meantime you could look at https://github.com/pcc/llvm-project/tree/lld-part-symbols which is essentially the same code as I'm going to upstream.

This change looks pretty straightforward to me, although I'd like to somehow continue using the term "Live" instead of Partition is zero" to explain liveness in code and comments, though.

I added a couple of accessors markLive and markDead for the places where we were setting Partition directly before.

lld/ELF/Driver.cpp
1378 ↗(On Diff #199324)

Yes, pretty much. I've added a comment saying that this is the entry point symbol. Following the link above will lead to an explanation (once D60242 lands) of what an "entry point symbol" is.

1400 ↗(On Diff #199324)

Right.

lld/ELF/InputSection.h
78 ↗(On Diff #199324)

I added a comment explaining why.

Looks quite good to me. Some nits.

lld/ELF/Driver.cpp
1452 ↗(On Diff #200852)

Early continue doesn't seem to help readability here. How about

if (Part.Name == PartName) {
  Sym->Partition = Part.getNumber();
  return;
}
lld/ELF/SyntheticSections.h
42 ↗(On Diff #200852)

Is this-> redundant?

pcc marked 3 inline comments as done.May 23 2019, 2:48 PM
pcc added inline comments.
lld/ELF/SyntheticSections.h
42 ↗(On Diff #200852)

Yes, removed.

pcc updated this revision to Diff 201076.May 23 2019, 2:48 PM
pcc marked an inline comment as done.
  • Relax tests so that they continue to pass once a future change lands
  • Address review comments
pcc added a comment.May 23 2019, 2:59 PM
In D60353#1512977, @pcc wrote:

Do you have another change for adding synthetic sections for partitioning?

Yes, I was going to send it out once it was ready, but I'll try to send it out as soon as I can so you can see what it looks like. In the meantime you could look at https://github.com/pcc/llvm-project/tree/lld-part-symbols which is essentially the same code as I'm going to upstream.

I've now sent out D62350. The only remaining changes that I need to send out are the change to llvm-objcopy for extracting partitions, as well as a change to prevent the linker from sharing range extension thunks between partitions. That should be enough for a usable implementation of partitions.

MaskRay accepted this revision.May 23 2019, 8:35 PM

I think the code below perfectly abstracts out the deleted unsigned Live : 1;.

bool isLive() const { return Partition != 0; }
void markLive() { Partition = 1; }
void markDead() { Partition = 0; }

This looks quite good to me, but I am not the proper person to give a final accept.

This revision is now accepted and ready to land.May 23 2019, 8:35 PM
MaskRay added inline comments.May 23 2019, 10:27 PM
lld/ELF/Driver.cpp
1745 ↗(On Diff #201076)

Delete Target = getTarget();

This has been moved just below inferMachineType(). in a previous change.

MaskRay added inline comments.May 24 2019, 12:08 AM
lld/ELF/MarkLive.cpp
352 ↗(On Diff #201076)

I'm concerned with the performance.

Shall we just do one MarkLive<ELFT>().run(); with all roots and one MarkLive<ELFT>(1).moveToMain();?

Before, we have npart+1 runs of DFS, now we have just 2 DFS.

MaskRay added inline comments.May 24 2019, 12:14 AM
lld/ELF/MarkLive.cpp
352 ↗(On Diff #201076)

Or 1, if you can merge moveToMain() into run().

pcc updated this revision to Diff 201303.May 24 2019, 12:01 PM
pcc marked an inline comment as done.
  • Address review comments
pcc marked an inline comment as done.May 24 2019, 12:02 PM
pcc added inline comments.
lld/ELF/MarkLive.cpp
352 ↗(On Diff #201076)

I don't really see how that could lead to better performance, and the current approach is simpler anyway IMHO.

The important thing isn't how many runs of DFS we do but how many nodes we visit. With that approach we'd still be visiting the same number of nodes, just in a different order. In fact, it could lead to worse performance. Say we happen to visit a root for a loadable partition before visiting the roots of the main partition, and the loadable partition uses mostly the same code as the main partition. So we mark most of the main partition's code as belonging to the loadable partition. Now we move on to the main partition's roots. That will cause us to visit most of the main partition's code again to mark it as being in the main partition. With the current approach we would visit the main partition's code once and we don't visit it again while handling the loadable partition because of the code on lines 197-198. We only visit sections twice if code is used by multiple loadable partitions but not by the main partition, which is something that we'd need to do anyway.

MaskRay added inline comments.May 26 2019, 8:13 PM
lld/ELF/MarkLive.cpp
352 ↗(On Diff #201076)

You can still have if (Sec->Partition == 1 || Sec->Partition == Partition) code in that one single DFS.

The time complexity of one DFS is not just O(|edges of visited sections |), but O(|symbols| + |edges of visited sections|):

for (Symbol *S : Symtab->getSymbols())
  if (S->includeInDynsym() && S->Partition == Partition)
    markSymbol(S);
ruiu accepted this revision.May 28 2019, 7:15 AM

LGTM

lld/ELF/InputSection.h
78 ↗(On Diff #199324)

Why do you have to use a bitfield? Looks like you can use uint8_t instead.

pcc updated this revision to Diff 201722.May 28 2019, 11:09 AM
pcc marked 3 inline comments as done.
  • Address review comments
lld/ELF/InputSection.h
78 ↗(On Diff #199324)

Yeah, that works. For some reason I thought that the series of bitfields would consume sizeof(unsigned) bytes, but that doesn't appear to be the case.

lld/ELF/MarkLive.cpp
352 ↗(On Diff #201076)

You can still have if (Sec->Partition == 1 || Sec->Partition == Partition) code in that one single DFS.

It wouldn't help with the problem I mentioned. Here's a concrete example:

 A <- root of partition 2
 |
 B <- root of partition 1
/ \
C D

If we visit A first we mark A, B, C, D as partition 2. Then when we visit B we visit B, C, D again to mark them as partition 1. But if we visit B first we mark B, C, D as partition 1 and then when we visit A we only mark A as partition 2 and we don't visit B because we'd take the if (Sec->Partition == 1 || Sec->Partition == Partition) branch for the A -> B edge. So by visiting partitions in order we avoid visiting B, C, D twice by construction.

The time complexity of one DFS is not just O(|edges of visited sections |), but O(|symbols| + |edges of visited sections|)

That could easily be addressed with a single pass over the symbol table that groups symbols by partition. I'd still prefer not to do that though, since it seems like a premature optimization that wouldn't be worth the added complexity.

This revision was automatically updated to reflect the committed changes.