Paths
| Differential D43264
[WebAssembly] Add explicit symbol table ClosedPublic Authored by sbc100 on Feb 13 2018, 3:51 PM.
Details Summary This change modified lld to in response the llvm change which Based on patches by Nicholas Wilson: The primary difference that we see in the test output is that See: https://github.com/WebAssembly/tool-conventions/issues/38
Diff Detail
Event TimelineHerald added subscribers: llvm-commits, sunfish, aheejin and 4 others. · View Herald TranscriptFeb 13 2018, 3:51 PM Comment Actions Could you explain what you meant by "a more explicit symbol table"? This is fairly large change, so it isn't very easy to get the gist of it. Comment Actions This is indeed a large change. I added a little more to the description. @ncw has been working on these changes as two seperate partss (actual 4 parts, 2 in llvm and 2 on lld). I decided to merge them into single commit in each repo. Essentially, for the relocatable output (llc output and lld -r output) we using an explicit symbol table rather than trying to module the entire thing using wasm's import/export/global concepts. We get several advantages when doing this:
Some downside:
The original bug: https://github.com/WebAssembly/tool-conventions/issues/38 Comment Actions We are hoping this will be the last major change before we try push WebAssembly out of experimental on the llvm side. After that things should settle down (somewhat).
Comment Actions All looks good, thanks for integrating with the Symbols.h changes!
This revision is now accepted and ready to land.Feb 14 2018, 5:14 AM Comment Actions Honestly I don't think I understand what InputGlobal class is doing and what's that for. The comment says that InputGlobal represents a single Wasm Global, and for that purpose, we do have symbol class right? That I can't understand that part of code doesn't necessarily mean that that's wrong, but it is a signal that something isn't quite right. Comment Actions Maybe I can explain a little better. This change introduces this new concept of a first class wasm "global" which can be named by "GlobalSymbol". This is distinct from data objects which are names via "DataSymbol". For now, llvm is only using one actual such wasm global (the one it used for stack pointer manipulation via the __stack_pointer symbol). For parity with Functions and Data objects we want to allow a many-to-one mapping between symbols and the things symbols point to. This is mostly for supporting aliases. This means you can have several names (Symbols) pointing to a given InputFunction, InputGlobal, or InputSegment (segments can have even more names pointing to them because symbols can point to offsets within a segment). However, as you point out, it is strange that InputGlobal is not really an InputChunk, in that it is not copied into place with memcpy + relocations like the other two subtypes. We can fix that in a followup CL, either by having it use memcpy for its tiny region, or my breaking the inheritance hierarchy. Comment Actions It sounds like InputGlobal is a symbol. Is this correct? (I know that you guys want to fix this later in a follow-up patch, but I cannot say LGTM to the code that I don't understand how it works...)
Comment Actions
It represents a wasm global that could have an initial value. Several symbols could point to a given global. For example __stack_pointer and __stack_pointer_alias could both point to global 0, and in this case we would only want to write a single global to the final output and have both those symbols resolve to the same value when used in relocations.
Comment Actions What is the relationship between Wasm Global and Wasm Symbol? In most object file formats, global/local is an attribute of a symbol, so when you say "global" it implies that it is a symbol. So I was thinking of symbols when you wrote "wasm global". But it sounds like that's different in wasm. Comment Actions Sorry, I can see why its confusing. The concept of a wasm global is different to the concept of a symbol (which can have local or global binding). We now have three symbols types which can name data, functions or wasm globals. I the ELF world the first two would be called STT_OBJECT and STT_FUNC. This new type has no ELF equivalent since its a wasm specific concept. So far the only use for this symbol type is the stack pointer but we see future uses (for example for tls access and possibly via intrinsics or assembly). Comment Actions So, InputFunction is a function, InputSegment is a data segment, and what is "wasm global" for? It sounds like it is more like data than a function, but I wonder how "wasm global" is different from regular data section. Comment Actions
Wasm has these first class things called globals that live outside the address space: The can only be accessed via special get_global and set_gobal instructions. Comment Actions
It's basically a special type of data section; what makes it special is that it's accessed more like a register than a memory region. The InputGlobal object represents the allocation of the memory/storage for the symbol, and contains the region of memory to be copied into the output binary with the initial value of the data. You're right, it's very similar to a data symbol. The InputGlobal has really the same role for a GlobalSymbol as an InputSection does for a DataSymbol. // Will be stored in ordinary memory, addressable down to individual bytes.
// Creates a 12-byte data section (InputSegment), holding its initial value, which
// the data Symbol points to as its definition.
std::tuple<int,int,int> global_variable = {1,2,3};
// Will create a 4-byte section, but using a "Wasm global". Not addressable down
// to individual bytes, it's like a register. Can't take address-of, can only assign
// and read from the storage. Requests the WebAssembly virtual machine to
// allocate a thread-local register. Constrained to be of register type (int32/float32/
// int64/float64) so the size of an InputGlobal is always a 4- or 8-byte section.
//
// Unlike x86 registers, you can have have as many as you want, they are storage
// slots allocated at program startup, just like ordinary sections are mapped to
// RAM. (NB The WebAssembly interpreter will spill the globals to RAM if the "real"
// CPU doesn't have enough spare registers to use for the Wasm globals). So it's like
// data, in that these are variables with a value, but the mechanics of the storage
// slots are different. There's no analogue in ELF, because x86 has a fixed number of
// registers, and the binary doesn't have to ask for them to be created.
//
// The 4-byte section containing the initial value is represented by an InputGlobal,
// which the Wasm-global symbol points to as its definition. It's written out in a
// different place in the final Wasm object, since it has distinct semantics.
//
// NB. This attribute isn't actually implemented in the C frontend ("Wasm globals"
// are only accessible via intrinsics). Conceptually these are just variables though.
int __attribute__((wasm_global)) wasm_global = 123;Comment Actions I read the documentation of wasm to understand its model better. Here is my observation (some of them are very obvious to you guys though)
It looks more and more like global variables are just symbols with indices. Do you agree? I believe it can naturally be modeled as a symbol. That makes me wonder what the current DefinedGlobal represents. Is this a symbol that lives in the linear memory or global variable? Comment Actions In the old code we used DefinedGlobal to meant global data in linear memory. In the new code that got renamed to DefinedData and a new type of entity called DefinedGlobal was added for wasm globals. Its a shame it has the same name in the new code, but I think it makes sense. To make this even more complicated to follow, we previously modeled data symbols as wasm globals... i.e. we use the wasm globals in the object format to store the addresses in linear memory of data symbols. A little confusing, and one reason why we are making this change to have a more explicit symbol table. We could simply store the wasm global data in the DefinedGlobal itself, rather then having it point to an InputGlobal. I think the problem there is when more than one symbol aliases the same global. But, we don't have the case yet so perhaps we can push that down the line a little. Let me see if I can simplify things. Comment Actions
What is your concern on aliasing? In general, symbols can have aliases (by just pointing to the same offset in the same section). We don't do anything special about it in other file formats, and it just works fine -- we don't need to find if a symbol has aliases or not to generate a correct output. I'm wondering if there's some wasm-specific concern about it. Comment Actions
I'm not sure it would be simpler to put the definition (initialiser) for the symbol in the symbol itself. As you say, it's conceptually wrong because it doesn't work with aliases (unused in this case, but it demonstates the model wouldn't be right); secondly it breaks the link between defined symbols and their "chunk" containing the initializer; and thirdly, worst, prevents unifying the handling of globals/data (eg with comdat for globals, then symbols could then be initialized in the same way for all types). I think we should aim to have globals work in the same way in LLD as data/function symbols, to keep the mental model simple, rather than arbitrarily constraing them with different resolution semantics (eg coding up a way of defining global symbols that doesn't allow aliases).
And an initializer! That's what distinguishes a defined global from an imported/undefined one, in the same way that the initializer (bss or data section) does for a data symbol, or the function body does for a function symbol.
DefinedGlobal is a symbol representing storage that's only accessible via its global index, rather than via a linear memory address. "Defined" means the Wasm file allocates that storage, rather than importing the storage from another DSO. We definitely need the distinction between defined and undefined for globals. The key takeaway is that a global is a storage/memory slot that can be allocated by a binary, just like a data symbol in ELF, it's only the addressing model that's different (via index rather than RAM address). Thanks for looking into this! Comment Actions
An initializer can just be a member of a symbol, no? Global variables look very similar to imported functions. There's no "body" of imported symbols, and therefore there's no chunk that represents imported function body, even though imported symbols are "defined" (as opposed to "undefined" symbols that have to be resolved until the end of linking). Symbols doesn't have to have chunks, and that's not actually odd. Comment Actions Aliasing works because of InputSection/InputChunk, which allows multiple symbols to reference the same chunk of memory, without having the section or body duplicated in the output. If you get rid of InputGlobal, you'll have aliasing issues, because the output will duplicate the global, causing it to be allocated storage twice - just like if a data section aliased by two symbols would chew up double the RAM if the symbols weren't able to share the InputSection. Plus the semantics would be wrong because writes to one alias should be visible by reads to the other. Comment Actions
I don't think you need to use InputChunk to address the issue. You can just maintain the indices of globals the linker has already emitted so that it doesn't assign different indices to two Globals that originally had the same index, for example. There may be easier way of doing it than that. Comment Actions
By that logic, you wouldn't need InputSection at if all in the ELF linker. You just put the body of each symbol on the symbols, rather than allowing multiple symbols to defence the same section.
Globals are really more like data symbols. An int variable would have a 4-byte section asking the ELF interpreter to allocate 4 bytes of ram. A wasm global I32 has its own section in the wasm file, asking for a 4byte register-backed region to be allocated. Do we have a different understanding of "imported"? An imported function is definitely undefined from a wasm and a linking point of view - both in ELF and warm, the function symbols with no body are undefined and the linker is looking for a definition against which to reduce any calls. Comment Actions
That's true, I admit. But you haven't done that for functions (even though it would be equally possible to get rid of InputSection or InputFunction in the same way). I just thinks it really helps comprehension if all the symbol clases are implemented in the same way, rather than differing in ad-hoc ways. Wanting DefinedFunction to work like DefinedGlobal is similar to wanting the wasm Symbol class to match the ELF symbol class. I don't want to argue though - I'll go with your preference as the code owners, now I've (hopefully) explained my reasoning. Comment Actions
I don't know if I understand what you wrote correctly. In ELF, you need both symbols and sections in the linker. One section can have multiple symbols at its various offsets, and some of them are aliases (e.g. two symbols can point to the same location in the same section).
Well, that runtime allocates some memory at runtime doesn't necessarily mean that that has to be represented as Chunk. At least to me the use of Chunk in this patch to represent Globals is very odd and is not an intended use of Chunk. Chunk is designed to represent sections or something like that, and Globals is different.
By imported, I mean symbols in DSO (DLL) files. In ELF, it's SharedSymbol. In COFF, It's DLLImported symbol. They are considered "defined" because they are already resolved, but the actual code is not given until load-time. Comment Actions I see about "imported", thanks! I hadn't realized that terminology in DSOs, my mistake. In wasm "imported" really is undefined. Maybe we could compromise on keeping InputGlobal, but renaming it and making it not derive from InputChunk. That would almost compile as-is in fact, and I think maybe you've right that would be cleaner. MarkLive would have to gain support for it, but that's only a few lines of code actually. I could try that tomorrow, or Sam could try now? Comment Actions
I've been trying to do this this evening but its fairly entangled. I will try again tomorrow, perhaps with a preparatory change to precede it. Comment Actions
Sorry Sam, somehow this didn't catch my eye in my inbox -I realise now we might have been working on the same cleanup :( Oh well, don't worry if you go a different direction to what I did in D43391. I can't really chat this evening - not that I'd be much help anyway! If you and Rui can come up with a solution that works for InputGlobal - go ahead and merge! I'll take any solution, I'm only arguing for changes at the moment that are fairly close to how these patches are currently, to so that we don't end up with another big refactor on our hands before we can merge what we've got so far. Do you have any thoughts at this point on how you think InputGlobal should fit into the hierarchy, eg like the comment in D43391? Comment Actions It also didn't feel right to have InputGlobal to inherit from InputChunk. For me the Chunks are really for the non-synthetic sections. That is the ones construct using memory copied from the input files + relocations. I think of the global section as being a sythentic section (indeed it is right now). So I guess I agree with ruiu here. But don't worry, I'm sure we can find a solution...we will get this thing landed soon one way or another :) Comment Actions It looks OK still. It's familiar, in that I tried a similar refactor (making InputGlobal not inherit InputChunk), and I can see you've faced the same problems. I think it works, just some comments about consistency below.
sbc100 marked 10 inline comments as done. Comment Actions
sbc100 marked 7 inline comments as done. Comment Actions
sbc100 marked an inline comment as done. Comment Actions
Comment Actions wabt change is ready to go: https://github.com/WebAssembly/wabt/pull/769 Any more feedback on this? Comment Actions LGTM There are a few things that hasn't been addressed, but we can address them later if we still want to do that.
Comment Actions I fixed the DefinedData constructor args. The rest we can follow up with. Thanks for all the reviewing! Closed by commit rL325861: [WebAssembly] Add explicit symbol table (authored by sbc). · Explain WhyFeb 22 2018, 9:12 PM This revision was automatically updated to reflect the committed changes.
Revision Contents
Diff 135593 lld/trunk/test/wasm/alias.ll
lld/trunk/test/wasm/archive.ll
lld/trunk/test/wasm/data-layout.ll
lld/trunk/test/wasm/init-fini.ll
lld/trunk/test/wasm/locals-duplicate.test
lld/trunk/test/wasm/many-functions.ll
lld/trunk/test/wasm/relocatable.ll
lld/trunk/test/wasm/signature-mismatch-weak.ll
lld/trunk/test/wasm/signature-mismatch.ll
lld/trunk/test/wasm/stack-pointer.ll
lld/trunk/test/wasm/weak-alias.ll
lld/trunk/wasm/Driver.cpp
lld/trunk/wasm/InputChunks.h
lld/trunk/wasm/InputChunks.cpp
lld/trunk/wasm/InputFiles.h
lld/trunk/wasm/InputFiles.cpp
lld/trunk/wasm/InputGlobal.h
lld/trunk/wasm/MarkLive.cpp
lld/trunk/wasm/OutputSegment.h
lld/trunk/wasm/SymbolTable.h
lld/trunk/wasm/SymbolTable.cpp
lld/trunk/wasm/Symbols.h
lld/trunk/wasm/Symbols.cpp
lld/trunk/wasm/Writer.cpp
lld/trunk/wasm/WriterUtils.h
lld/trunk/wasm/WriterUtils.cpp
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||