llvm dev - Jun 2017 - [cfe-dev] RFC: ODR checker for Clang and LLD

Is the entry in your ODR table 64-bit? Sean mentioned that this is a
birthday paradox situation, but I don't think we need that large hash
values, as our aim is not to avoid any collisions. Small number of
collisions is okay as it just slightly increases false negatives. I think
it can even be 16-bit if space saving is important. If we choose 16-bit
hash, the probability that an ODR violation is not detected is 1/65536,
which is still quite low.

On Wed, Jun 14, 2017 at 1:41 PM, Peter Collingbourne via cfe-dev <
cfe-dev at lists.llvm.org> wrote:
>
>
> On Wed, Jun 14, 2017 at 12:47 PM, David Blaikie <dblaikie at
gmail.com>
> wrote:
>
>>
>>
>> On Tue, Jun 13, 2017, 11:30 PM Peter Collingbourne <peter at
pcc.me.uk>
>> wrote:
>>
>>> On Tue, Jun 13, 2017 at 11:06 PM, David Blaikie <dblaikie at
gmail.com>
>>> wrote:
>>>
>>>>
>>>>
>>>> On Tue, Jun 13, 2017 at 10:05 PM Peter Collingbourne <peter
at pcc.me.uk>
>>>> wrote:
>>>>
>>>>> On Tue, Jun 13, 2017 at 8:48 PM, David Blaikie <dblaikie
at gmail.com>
>>>>> wrote:
>>>>>
>>>>>>
>>>>>>
>>>>>> On Tue, Jun 13, 2017 at 8:43 PM Peter Collingbourne
<peter at pcc.me.uk>
>>>>>> wrote:
>>>>>>
>>>>>>> On Tue, Jun 13, 2017 at 7:54 PM, David Blaikie
<dblaikie at gmail.com>
>>>>>>> wrote:
>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> On Tue, Jun 13, 2017 at 6:34 PM Peter
Collingbourne via cfe-dev <
>>>>>>>> cfe-dev at lists.llvm.org> wrote:
>>>>>>>>
>>>>>>>>> On Wed, Jun 7, 2017 at 11:28 PM, Peter
Collingbourne <
>>>>>>>>> peter at pcc.me.uk> wrote:
>>>>>>>>>
>>>>>>>>>> On Wed, Jun 7, 2017 at 8:06 PM, Sean
Silva <chisophugis at gmail.com
>>>>>>>>>> > wrote:
>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> On Wed, Jun 7, 2017 at 4:31 PM,
Peter Collingbourne <
>>>>>>>>>>> peter at pcc.me.uk> wrote:
>>>>>>>>>>>
>>>>>>>>>>>> On Wed, Jun 7, 2017 at 12:17
AM, Sean Silva <
>>>>>>>>>>>> chisophugis at gmail.com>
wrote:
>>>>>>>>>>>>
>>>>>>>>>>>>> Very nice and simple
implementation!
>>>>>>>>>>>>>
>>>>>>>>>>>>> Do you have any statistics
on how large these odr tables are
>>>>>>>>>>>>> compared to other object
file data? I assume that if these tables contain
>>>>>>>>>>>>> full mangled symbol names,
they could end up being very large and may want
>>>>>>>>>>>>> to share the symbol name
strings with the overall string table in the .o
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Looking at Chromium's
object files it looks like the total size
>>>>>>>>>>>> of the odrtabs is about 50% of
the total size of the object files, which
>>>>>>>>>>>> isn't great. The current
implementation only looks at records, so I imagine
>>>>>>>>>>>> that it would be hard to share
any of the strings that I'm currently
>>>>>>>>>>>> creating. (I guess it's
possible that some types will have a mangled vtable
>>>>>>>>>>>> name in the string table, so we
may be able to share a little that way.)
>>>>>>>>>>>> Note however that this was
without debug info.
>>>>>>>>>>>>
>>>>>>>>>>>> One option for reducing size
would be to
>>>>>>>>>>>> 1) store hashes of ODR names in
ODR tables, per Rui's
>>>>>>>>>>>> suggestion (alongside a
reference to the name itself in the string table)
>>>>>>>>>>>> 2) compress the string table
for the ODR names with a standard
>>>>>>>>>>>> compression algorithm like
gzip.
>>>>>>>>>>>> This wouldn't seem to
affect link time performance much because
>>>>>>>>>>>> I think we should only need to
look at the strings if we see a ODR name
>>>>>>>>>>>> hash match together with an ODR
hash mismatch, which would mean an ODR
>>>>>>>>>>>> violation with a high
probability (i.e. unless there was an ODR name hash
>>>>>>>>>>>> collision, we have found an ODR
violation). If we don't expect a lot of
>>>>>>>>>>>> sharing with regular string
tables (see below), it seems even more
>>>>>>>>>>>> reasonable.
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Neat observation!
>>>>>>>>>>>
>>>>>>>>>>> FWIW, it is a birthday problem type
situation though, so for a
>>>>>>>>>>> 32-bit hash, we would expect a
collision in about 1 in 2^16 distinct hashes
>>>>>>>>>>> (and 2^16 seems pretty easy to hit
in a large project). So 64-bit hashes
>>>>>>>>>>> might be preferable.
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Oh right, good point, using a 64-bit
hash does seem like a good
>>>>>>>>>> idea here.
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>> Also, do you have any numbers
on the performance of your
>>>>>>>>>>>>> initial implementation?
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> I measured the link time for
chromium's unit_tests (the largest
>>>>>>>>>>>> single binary in chromium) at
5.05s without ODR checks and 6.61s with ODR
>>>>>>>>>>>> checks. So about 30% overhead,
but in absolute terms it doesn't seem too
>>>>>>>>>>>> bad. So I think this may be
acceptable for an initial implementation, but
>>>>>>>>>>>> it certainly seems worth trying
to do better.
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> I know that things aren't
currently apples-to-apples, but how
>>>>>>>>>>> does that compare to gold?
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> I will measure it.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> For that unit_tests binary I measured the
overhead at about 5
>>>>>>>>> seconds (average of 10 runs). That is with
debug info, of course.
>>>>>>>>>
>>>>>>>>> W.r.t. LLD and having it always on by
default (and hence making it
>>>>>>>>>>>>> as fast as possible), it
seems like right now you are implementing the
>>>>>>>>>>>>> checking process with a
hash table. That's simple and fine for a first
>>>>>>>>>>>>> implementation, but
it's probably worth mentioning in a comment the problem
>>>>>>>>>>>>> of checking the tables, at
least from the linker's perspective, does fit
>>>>>>>>>>>>> into a map-reduce pattern
and could be easily parallelized if needed. E.g.
>>>>>>>>>>>>> a parallel sort to coalesce
all entries for symbols of the same name
>>>>>>>>>>>>> followed by a parallel
forEach to check each bucket with the same symbol
>>>>>>>>>>>>> name (roughly speaking).
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Right, that's one approach.
I was thinking of a simpler
>>>>>>>>>>>> approach where at compile time
we sort ODR names by hash and partition them
>>>>>>>>>>>> using (say) the upper bits of
the hash, so that at link time we can have N
>>>>>>>>>>>> threads each building a hash
table for a specific partition.
>>>>>>>>>>>>
>>>>>>>>>>>> And of course this work can be
started right after symbol
>>>>>>>>>>>> resolution finishes and
parallelised with the rest of the work done by the
>>>>>>>>>>>> linker.
>>>>>>>>>>>>
>>>>>>>>>>>> Even better than doing it
faster is just doing less work.
>>>>>>>>>>>>> There's a lot of work
that the linker is already doing that may be reusable
>>>>>>>>>>>>> for the ODR checking.
>>>>>>>>>>>>> E.g.
>>>>>>>>>>>>> - maybe we could get the
coalescing step as a byproduct of our
>>>>>>>>>>>>> existing string deduping,
which we are generally doing anyway.
>>>>>>>>>>>>> - we are already coalescing
symbol names for the symbol table.
>>>>>>>>>>>>> If the ODR table is keyed
off of symbols in the binary that we are
>>>>>>>>>>>>> inserting into the symbol
table, then I think we could do the entire ODR
>>>>>>>>>>>>> check with no extra
"string" work on LLD's part.
>>>>>>>>>>>>>
>>>>>>>>>>>>> I see Rui already mentioned
some of this in
>>>>>>>>>>>>>
https://bugs.chromium.org/p/chromium/issues/detail?id=726
>>>>>>>>>>>>> 071#c4.
>>>>>>>>>>>>> You mentioned that not
everything is necessarily directly
>>>>>>>>>>>>> keyed on a symbol (such as
types), but I think that it would really
>>>>>>>>>>>>> simplify things if the
check was done as such. Do you have any idea exactly
>>>>>>>>>>>>> how much of the things that
we want to check are not keyed on symbols? If
>>>>>>>>>>>>> most things are keyed on
symbols, for the things we are not we can just
>>>>>>>>>>>>> emit extra symbols prefixed
by __clang_odr_check_ or whatever.
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Since the current
implementation only works with records there
>>>>>>>>>>>> is basically zero overlap right
now between ODR names and symbols. I
>>>>>>>>>>>> suppose that I could estimate
the amount of function overlap in a
>>>>>>>>>>>> hypothetical implementation
that computes ODR hashes of functions by
>>>>>>>>>>>> comparing the number of *_odr
functions after clang has finished IRgen with
>>>>>>>>>>>> the number after optimization
finishes. This of course would be strictly
>>>>>>>>>>>> more than functions + types.
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Wouldn't any function or symbol
using the record type have the
>>>>>>>>>>> type name somewhere in it? If we
used an offset+length encoding (instead of
>>>>>>>>>>> offset + NUL termination) we might
be able to reuse it then (at some cost
>>>>>>>>>>> in finding the reference).
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> That may be possible with some work in
the string table builder.
>>>>>>>>>> But at that point of course we're
not dealing with regular symbols any
>>>>>>>>>> more. I guess we could have two ODR
tables per object file: an array of
>>>>>>>>>> (ODR hash, location) tuples for ODR
names that correspond to symbol table
>>>>>>>>>> symbols (i.e. Rui's proposal on the
chromium bug), and an array of (ODR
>>>>>>>>>> name, ODR hash, location) tuples for
all other ODR names. I guess if we
>>>>>>>>>> wanted a "low overhead" mode
we could just omit the second table or put
>>>>>>>>>> fewer symbols in it.
>>>>>>>>>>
>>>>>>>>>> With debug info surely there is some
sort of string representing
>>>>>>>>>>> the record name or something like
that, no?
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Not the record name on its own (they do
appear but a bit
>>>>>>>>>> awkwardly -- each namespace component
is stored in a separate string), but
>>>>>>>>>> if the record has at least one member
function the mangled type name will
>>>>>>>>>> appear somewhere in .debug_str, so we
could in principle reuse that with
>>>>>>>>>> the offset/length trick.
>>>>>>>>>>
>>>>>>>>>> I guess we may have to have our
"low-overhead" user-facing
>>>>>>>>>>> behavior be a bit more nuanced.
E.g.:
>>>>>>>>>>> 1. does this feature bloat object
files significantly
>>>>>>>>>>> 2. does this feature slow down link
times significantly
>>>>>>>>>>>
>>>>>>>>>>> Intuitively, it seems like we
should be able to get 1. when
>>>>>>>>>>> debug info happens to be enabled
(not sure about split dwarf?) and possibly
>>>>>>>>>>> in all cases at the cost of
complexity. We may be able to get 2. in all
>>>>>>>>>>> cases with proper design.
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> I think that would be my rough
assessment as well. I think we
>>>>>>>>>> have a good shot at 1 for all cases
with some of the ideas that have been
>>>>>>>>>> mentioned already. If we can avoid
creating dependencies on DWARF I think
>>>>>>>>>> that would be ideal -- I'd ideally
like this to work for COFF as well,
>>>>>>>>>> where you'd typically expect to
find CodeView in object files. If I were to
>>>>>>>>>> try this I think the first thing that I
would try is hash/compression
>>>>>>>>>> combined with the two ODR tables (no
reuse for non-symbol ODR names to
>>>>>>>>>> start with, as compression may be
enough on its own).
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> I developed a second prototype which uses
hash/compression with no
>>>>>>>>> attempt to reuse. It is available here:
https://github.com/pcc/l
>>>>>>>>> lvm-project/tree/odr-checker2
>>>>>>>>>
>>>>>>>>> For Chromium the object file size overhead
was 536566007 bytes, or
>>>>>>>>> in relative terms about 25%, or about 4%
with debug info. I measured perf
>>>>>>>>> overhead for unit_tests at about 6%, but
after I moved the checker onto
>>>>>>>>> another thread, the overhead disappeared
into the noise.
>>>>>>>>>
>>>>>>>>
>>>>>>>> Still seems like quite a big increase.
>>>>>>>>
>>>>>>>> Any chance of compression?
>>>>>>>>
>>>>>>>
>>>>>>> That was with compression -- the implementation
compresses the parts
>>>>>>> of the ODR table that aren't hashes (aside from
the header and the Clang
>>>>>>> version, which is a small fixed cost), as well as
the string table. The
>>>>>>> hashes were left uncompressed because they are in
the critical path of the
>>>>>>> linker and because I imagine that they wouldn't
really be that compressible.
>>>>>>>
>>>>>>
>>>>>> I'd be a bit surprised if they weren't
especially compressible -
>>>>>>
>>>>>
>>>>> Maybe I'm wrong, but my intuition about compression is
that it works
>>>>> best when the data contains repeated patterns. If we use a
hash function
>>>>> with good dispersion then I'd expect each hash to have
little in common
>>>>> with other hashes.
>>>>>
>>>>>
>>>>>> and how much of the size increase is the compressed
data V the
>>>>>> uncompressed data?
>>>>>>
>>>>>
>>>>> The ratio was roughly 60% compressed data to 40%
uncompressed data.
>>>>>
>>>>>
>>>>>> Is it still in the hot path when parallelized?
>>>>>>
>>>>>
>>>>> Not right now according to my benchmarking, but
decompression could
>>>>> push it into the critical path if it ends up taking longer
than the rest of
>>>>> the work done by the linker after symbol resolution. On the
same machine
>>>>> that I used for benchmarking, gunzip'ing 200MB of
/dev/urandom (which is
>>>>> roughly what I'd expect the hashes to look like) takes
around 1.1s, i.e. a
>>>>> not insignificant fraction of lld's runtime.
>>>>>
>>>>>
>>>>>> So I think the remaining gains would either be through
limiting the
>>>>>>> number of ODR table entries, or through reuse of
data.
>>>>>>>
>>>>>>> Limiting might be something to explore -- one
possibility is that we
>>>>>>> could limit the ODR table entries to the
declarations that are "used" by a
>>>>>>> particular translation unit (it appears that Clang
tracks something like
>>>>>>> that in Decl::Used/Decl::Referenced, but I'm
not sure if that is exactly
>>>>>>> what we need -- I think we would basically need to
test for reference
>>>>>>> reachability from the functions/globals that are
IRgen'd).
>>>>>>>
>>>>>>
>>>>>> Currently it has every type and function that is in the
AST? Yeah,
>>>>>> that's a lot - perhaps it should be more like the
things that go in the
>>>>>> DWARF? (though would need to add some cases there -
since the DWARF logic
>>>>>> already relies on the ODR to not emit duplicates in
some cases)
>>>>>>
>>>>>
>>>>> Just every record declaration -- Clang only supports ODR
hashes for
>>>>> record declarations right now. I understand that function
declarations
>>>>> (including function bodies) are still works in progress.
>>>>>
>>>>> I think it should indeed just be roughly the things that go
in the
>>>>> DWARF. I think that at one point I observed that every
record declaration,
>>>>> even unused ones, were going into the DWARF, but I might
have been mistaken
>>>>> because I can no longer reproduce that. I'll take a
closer look to see if I
>>>>> can reuse what logic presumably already exists for DWARF.
>>>>>
>>>>> In terms of reuse, it seems that of the 536566007 bytes of
>>>>>>> overhead, 319309579 were the compressed part of the
ODR tables. So even if
>>>>>>> we achieved 100% sharing,
>>>>>>>
>>>>>>
>>>>>> 100% sharing? You mean if all the data were compressed,
and assuming
>>>>>> the hashes were compressible at the same ratio as the
other data?
>>>>>>
>>>>>
>>>>> Sorry, I mean if 100% of the data in the compressed part of
the ODR
>>>>> table could be eliminated by reusing data stored elsewhere
(e.g. in the
>>>>> object file string table or in the DWARF).
>>>>>
>>>>> with the current scheme I think that our minimum achievable
overhead
>>>>>>> would be ~15% (no debug info) or ~2% (with debug
info).
>>>>>>>
>>>>>>>
>>>>>>>> Could this go into .dwo files with Fission and
be checked by dwp
>>>>>>>> instead, perhaps?
>>>>>>>>
>>>>>>>
>>>>>>> I think it could also work that way, yes.
>>>>>>>
>>>>>>> I'm reasonably happy with these figures, at
least for a first
>>>>>>>>> implementation. We may be able to do even
better for file size with reuse,
>>>>>>>>> but I'd leave that for version 2.
>>>>>>>>>
>>>>>>>>
>>>>>>>> What's the story with compatibility between
versions, then? Is
>>>>>>>> there a version header?
>>>>>>>>
>>>>>>>
>>>>>>> Yes, the header contains a version number.
>>>>>>>
>>>>>>>
>>>>>>>> Will old formats be supported by lld
indefinitely? Not at all?
>>>>>>>>
>>>>>>>
>>>>>>> I think we should drop support for old formats when
we introduce a
>>>>>>> new format. My understanding is that the ODR hash
can change whenever Clang
>>>>>>> changes (the implementation only performs ODR
checking if all ODR tables
>>>>>>> were produced by the same revision of Clang), so
there wouldn't seem to be
>>>>>>> a huge benefit in keeping support for old formats
around.
>>>>>>>
>>>>>>
>>>>>> I imagine it's possible people aren't
necessarily going to rev lld in
>>>>>> exact lock-step with clang, but I could be wrong.
(certainly binutils ld or
>>>>>> gold aren't released/kept in lock-step with GCC,
for example)
>>>>>>
>>>>>
>>>>> That's certainly possible, but I'd say that the bar
for dropping
>>>>> backwards compatibility is lower because ODR tables are not
required for
>>>>> correctness. We could keep compatibility with the last
version or so if it
>>>>> isn't too burdensome, or otherwise print a warning.
>>>>>
>>>>
>>>> They aren't required for correctness, but upgrading your
compiler or
>>>> linker then silently losing ODR checking would be bad (or even
not silently
>>>> losing it, but having no choice but to rev both to keep the
functionality &
>>>> hold the ODR-cleanliness bar) - it's the sort of thing
where if you lost
>>>> the checking, then gained it back again later, the regression
cleanup would
>>>> be annoying/an impediment to using the feature.
>>>>
>>>
>>> Makes sense I guess. I'd be fine with a policy where the Nth
open source
>>> release should be able to read ODR tables produced by the N-1th and
>>> possibly the N-2th release.
>>>
>>
>> Still strikes me as a bit awkward - wonder how that compared to other
>> (similar or different) linker features.
>>
>
> I think the most similar existing feature is .gdb_index. They have already
> gone through a few format revisions:
> https://sourceware.org/gdb/onlinedocs/gdb/Index-Section-Format.html
> and have deprecated/removed support for older formats.
>
> Because the requirements for ODR tables are simpler than those for
> .gdb_index, I'd expect us to converge on a final format sooner, so in
> practice the window of compatibility would end up being longer than a year.
>
> Peter
>
>
>>
>>> Any idea what Daniel Jasper & co have been working on WRT ODR
checking &
>>>> how this feature integrates or doesn't with their work? I
imagine they
>>>> might be working on something more like a Clang Tooling style
approach, but
>>>> I'm not sure.
>>>>
>>>
>>> I'm not aware of any work like that, only of Richard
Trieu's efforts for
>>> modules that I'm piggybacking on.
>>>
>>
>> +Djasper - perhaps you could provide some context on other odr
detection
>> efforts?
>>
>>
>>> Peter
>>>
>>>>
>>>> - Dave
>>>>
>>>>
>>>>>
>>>>> Peter
>>>>>
>>>>>>
>>>>>>
>>>>>>>
>>>>>>> Peter
>>>>>>>
>>>>>>>>
>>>>>>>> - Dave
>>>>>>>>
>>>>>>>>
>>>>>>>>>
>>>>>>>>> Peter
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Peter
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> -- Sean Silva
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>> The issue of retaining the
ODR check for functions even if
>>>>>>>>>>>>> they get inlined may
inherently pose an extra cost that can't be folded
>>>>>>>>>>>>> into existing work the
linker is doing, so there might be a reason for
>>>>>>>>>>>>> clang to have a default
mode that has practically no linking overhead and
>>>>>>>>>>>>> one that does more thorough
checking but imposes extra linking overhead.
>>>>>>>>>>>>> Think something like a
crazy boost library with thousands of functions that
>>>>>>>>>>>>> get inlined away, but have
gigantic mangled names and so precisely are the
>>>>>>>>>>>>> ones that are going to
impose extra cost on the linker. Simply due to the
>>>>>>>>>>>>> extra volume of strings
that the linker would need to look at, I don't
>>>>>>>>>>>>> think there's a way to
include checking of all inlined function "for free"
>>>>>>>>>>>>> at the linker level using
the symbol approach.
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>> I guess those inlined functions
would still have those symbol
>>>>>>>>>>>>> names in debug info (I
think?), so piggybacking on the string deduplication
>>>>>>>>>>>>> we're already doing
might make it possible to fold away the work in that
>>>>>>>>>>>>> case (but then again, would
still impose extra cost with split dwarf...).
>>>>>>>>>>>>>
>>>>>>>>>>>>> Anyway, let's wait to
see what the actual performance numbers
>>>>>>>>>>>>> are.
>>>>>>>>>>>>>
>>>>>>>>>>>>> -- Sean Silva
>>>>>>>>>>>>>
>>>>>>>>>>>>> On Tue, Jun 6, 2017 at
10:40 PM, Peter Collingbourne via
>>>>>>>>>>>>> cfe-dev <cfe-dev at
lists.llvm.org> wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>>> Hi all,
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> I'd like to propose
an ODR checker feature for Clang and LLD.
>>>>>>>>>>>>>> The feature would be
similar to gold's --detect-odr-violations feature, but
>>>>>>>>>>>>>> better: we can rely on
integration with clang to avoid relying on debug
>>>>>>>>>>>>>> info and to perform
more precise matching.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> The basic idea is that
we use clang's ability to create ODR
>>>>>>>>>>>>>> hashes for
declarations. ODR hashes are computed using all information
>>>>>>>>>>>>>> about a declaration
that is ODR-relevant. If the flag
>>>>>>>>>>>>>> -fdetect-odr-violations
is passed, Clang will store the ODR hashes in a
>>>>>>>>>>>>>> so-called ODR table in
each object file. Each ODR table will contain a
>>>>>>>>>>>>>> mapping from mangled
declaration names to ODR hashes. At link time, the
>>>>>>>>>>>>>> linker will read the
ODR table and report any mismatches.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> To make this work:
>>>>>>>>>>>>>> - LLVM will be extended
with the ability to represent ODR
>>>>>>>>>>>>>> tables in the IR and
emit them to object files
>>>>>>>>>>>>>> - Clang will be
extended with the ability to emit ODR tables
>>>>>>>>>>>>>> using ODR hashes
>>>>>>>>>>>>>> - LLD will be extended
to read ODR tables from object files
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> I have implemented a
prototype of this feature. It is
>>>>>>>>>>>>>> available here:
https://github.com/pcc/l
>>>>>>>>>>>>>>
lvm-project/tree/odr-checker and some results from applying
>>>>>>>>>>>>>> it to chromium are
here: crbug.com/726071
>>>>>>>>>>>>>> As you can see it did
indeed find a number of real ODR
>>>>>>>>>>>>>> violations in Chromium,
including some that wouldn't be detectable using
>>>>>>>>>>>>>> debug info.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> If you're
interested in what the format of the ODR table
>>>>>>>>>>>>>> would look like, that
prototype shows pretty much what I had in mind, but I
>>>>>>>>>>>>>> expect many other
aspects of the implementation to change as it is
>>>>>>>>>>>>>> upstreamed.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Thanks,
>>>>>>>>>>>>>> --
>>>>>>>>>>>>>> --
>>>>>>>>>>>>>> Peter
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
_______________________________________________
>>>>>>>>>>>>>> cfe-dev mailing list
>>>>>>>>>>>>>> cfe-dev at
lists.llvm.org
>>>>>>>>>>>>>>
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> --
>>>>>>>>>>>> --
>>>>>>>>>>>> Peter
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> --
>>>>>>>>>> --
>>>>>>>>>> Peter
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> --
>>>>>>>>> --
>>>>>>>>> Peter
>>>>>>>>>
_______________________________________________
>>>>>>>>> cfe-dev mailing list
>>>>>>>>> cfe-dev at lists.llvm.org
>>>>>>>>>
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> --
>>>>>>> Peter
>>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> --
>>>>> Peter
>>>>>
>>>>
>>>
>>>
>>> --
>>> --
>>> Peter
>>>
>>
>
>
> --
> --
> Peter
>
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170614/275102ab/attachment-0001.html>

On Wed, Jun 14, 2017 at 6:01 PM Rui Ueyama <ruiu at google.com> wrote:
> Is the entry in your ODR table 64-bit? Sean mentioned that this is a
> birthday paradox situation, but I don't think we need that large hash
> values, as our aim is not to avoid any collisions. Small number of
> collisions is okay as it just slightly increases false negatives. I think
> it can even be 16-bit if space saving is important. If we choose 16-bit
> hash, the probability that an ODR violation is not detected is 1/65536,
> which is still quite low.
>
If I'm understanding this correctly, it's the opposite though -
colliding
hashes will produce false positives, right? (ODR violations will be
detected where none exist in the code) Perhaps I'm misunderstanding.

>
> On Wed, Jun 14, 2017 at 1:41 PM, Peter Collingbourne via cfe-dev <
> cfe-dev at lists.llvm.org> wrote:
>
>>
>>
>> On Wed, Jun 14, 2017 at 12:47 PM, David Blaikie <dblaikie at
gmail.com>
>> wrote:
>>
>>>
>>>
>>> On Tue, Jun 13, 2017, 11:30 PM Peter Collingbourne <peter at
pcc.me.uk>
>>> wrote:
>>>
>>>> On Tue, Jun 13, 2017 at 11:06 PM, David Blaikie <dblaikie at
gmail.com>
>>>> wrote:
>>>>
>>>>>
>>>>>
>>>>> On Tue, Jun 13, 2017 at 10:05 PM Peter Collingbourne
<peter at pcc.me.uk>
>>>>> wrote:
>>>>>
>>>>>> On Tue, Jun 13, 2017 at 8:48 PM, David Blaikie
<dblaikie at gmail.com>
>>>>>> wrote:
>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> On Tue, Jun 13, 2017 at 8:43 PM Peter Collingbourne
<peter at pcc.me.uk>
>>>>>>> wrote:
>>>>>>>
>>>>>>>> On Tue, Jun 13, 2017 at 7:54 PM, David Blaikie
<dblaikie at gmail.com>
>>>>>>>> wrote:
>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> On Tue, Jun 13, 2017 at 6:34 PM Peter
Collingbourne via cfe-dev <
>>>>>>>>> cfe-dev at lists.llvm.org> wrote:
>>>>>>>>>
>>>>>>>>>> On Wed, Jun 7, 2017 at 11:28 PM, Peter
Collingbourne <
>>>>>>>>>> peter at pcc.me.uk> wrote:
>>>>>>>>>>
>>>>>>>>>>> On Wed, Jun 7, 2017 at 8:06 PM,
Sean Silva <
>>>>>>>>>>> chisophugis at gmail.com> wrote:
>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> On Wed, Jun 7, 2017 at 4:31 PM,
Peter Collingbourne <
>>>>>>>>>>>> peter at pcc.me.uk> wrote:
>>>>>>>>>>>>
>>>>>>>>>>>>> On Wed, Jun 7, 2017 at
12:17 AM, Sean Silva <
>>>>>>>>>>>>> chisophugis at
gmail.com> wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>>> Very nice and simple
implementation!
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Do you have any
statistics on how large these odr tables are
>>>>>>>>>>>>>> compared to other
object file data? I assume that if these tables contain
>>>>>>>>>>>>>> full mangled symbol
names, they could end up being very large and may want
>>>>>>>>>>>>>> to share the symbol
name strings with the overall string table in the .o
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> Looking at Chromium's
object files it looks like the total
>>>>>>>>>>>>> size of the odrtabs is
about 50% of the total size of the object files,
>>>>>>>>>>>>> which isn't great. The
current implementation only looks at records, so I
>>>>>>>>>>>>> imagine that it would be
hard to share any of the strings that I'm
>>>>>>>>>>>>> currently creating. (I
guess it's possible that some types will have a
>>>>>>>>>>>>> mangled vtable name in the
string table, so we may be able to share a
>>>>>>>>>>>>> little that way.) Note
however that this was without debug info.
>>>>>>>>>>>>>
>>>>>>>>>>>>> One option for reducing
size would be to
>>>>>>>>>>>>> 1) store hashes of ODR
names in ODR tables, per Rui's
>>>>>>>>>>>>> suggestion (alongside a
reference to the name itself in the string table)
>>>>>>>>>>>>> 2) compress the string
table for the ODR names with a standard
>>>>>>>>>>>>> compression algorithm like
gzip.
>>>>>>>>>>>>> This wouldn't seem to
affect link time performance much
>>>>>>>>>>>>> because I think we should
only need to look at the strings if we see a ODR
>>>>>>>>>>>>> name hash match together
with an ODR hash mismatch, which would mean an ODR
>>>>>>>>>>>>> violation with a high
probability (i.e. unless there was an ODR name hash
>>>>>>>>>>>>> collision, we have found an
ODR violation). If we don't expect a lot of
>>>>>>>>>>>>> sharing with regular string
tables (see below), it seems even more
>>>>>>>>>>>>> reasonable.
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Neat observation!
>>>>>>>>>>>>
>>>>>>>>>>>> FWIW, it is a birthday problem
type situation though, so for a
>>>>>>>>>>>> 32-bit hash, we would expect a
collision in about 1 in 2^16 distinct hashes
>>>>>>>>>>>> (and 2^16 seems pretty easy to
hit in a large project). So 64-bit hashes
>>>>>>>>>>>> might be preferable.
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Oh right, good point, using a
64-bit hash does seem like a good
>>>>>>>>>>> idea here.
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>> Also, do you have any
numbers on the performance of your
>>>>>>>>>>>>>> initial implementation?
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> I measured the link time
for chromium's unit_tests (the
>>>>>>>>>>>>> largest single binary in
chromium) at 5.05s without ODR checks and 6.61s
>>>>>>>>>>>>> with ODR checks. So about
30% overhead, but in absolute terms it doesn't
>>>>>>>>>>>>> seem too bad. So I think
this may be acceptable for an initial
>>>>>>>>>>>>> implementation, but it
certainly seems worth trying to do better.
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> I know that things aren't
currently apples-to-apples, but how
>>>>>>>>>>>> does that compare to gold?
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> I will measure it.
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> For that unit_tests binary I measured
the overhead at about 5
>>>>>>>>>> seconds (average of 10 runs). That is
with debug info, of course.
>>>>>>>>>>
>>>>>>>>>> W.r.t. LLD and having it always on by
default (and hence making
>>>>>>>>>>>>>> it as fast as
possible), it seems like right now you are implementing the
>>>>>>>>>>>>>> checking process with a
hash table. That's simple and fine for a first
>>>>>>>>>>>>>> implementation, but
it's probably worth mentioning in a comment the problem
>>>>>>>>>>>>>> of checking the tables,
at least from the linker's perspective, does fit
>>>>>>>>>>>>>> into a map-reduce
pattern and could be easily parallelized if needed. E.g.
>>>>>>>>>>>>>> a parallel sort to
coalesce all entries for symbols of the same name
>>>>>>>>>>>>>> followed by a parallel
forEach to check each bucket with the same symbol
>>>>>>>>>>>>>> name (roughly
speaking).
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> Right, that's one
approach. I was thinking of a simpler
>>>>>>>>>>>>> approach where at compile
time we sort ODR names by hash and partition them
>>>>>>>>>>>>> using (say) the upper bits
of the hash, so that at link time we can have N
>>>>>>>>>>>>> threads each building a
hash table for a specific partition.
>>>>>>>>>>>>>
>>>>>>>>>>>>> And of course this work can
be started right after symbol
>>>>>>>>>>>>> resolution finishes and
parallelised with the rest of the work done by the
>>>>>>>>>>>>> linker.
>>>>>>>>>>>>>
>>>>>>>>>>>>> Even better than doing it
faster is just doing less work.
>>>>>>>>>>>>>> There's a lot of
work that the linker is already doing that may be reusable
>>>>>>>>>>>>>> for the ODR checking.
>>>>>>>>>>>>>> E.g.
>>>>>>>>>>>>>> - maybe we could get
the coalescing step as a byproduct of
>>>>>>>>>>>>>> our existing string
deduping, which we are generally doing anyway.
>>>>>>>>>>>>>> - we are already
coalescing symbol names for the symbol
>>>>>>>>>>>>>> table. If the ODR table
is keyed off of symbols in the binary that we are
>>>>>>>>>>>>>> inserting into the
symbol table, then I think we could do the entire ODR
>>>>>>>>>>>>>> check with no extra
"string" work on LLD's part.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> I see Rui already
mentioned some of this in
>>>>>>>>>>>>>>
https://bugs.chromium.org/p/chromium/issues/detail?id=726071#c4
>>>>>>>>>>>>>> .
>>>>>>>>>>>>>> You mentioned that not
everything is necessarily directly
>>>>>>>>>>>>>> keyed on a symbol (such
as types), but I think that it would really
>>>>>>>>>>>>>> simplify things if the
check was done as such. Do you have any idea exactly
>>>>>>>>>>>>>> how much of the things
that we want to check are not keyed on symbols? If
>>>>>>>>>>>>>> most things are keyed
on symbols, for the things we are not we can just
>>>>>>>>>>>>>> emit extra symbols
prefixed by __clang_odr_check_ or whatever.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> Since the current
implementation only works with records there
>>>>>>>>>>>>> is basically zero overlap
right now between ODR names and symbols. I
>>>>>>>>>>>>> suppose that I could
estimate the amount of function overlap in a
>>>>>>>>>>>>> hypothetical implementation
that computes ODR hashes of functions by
>>>>>>>>>>>>> comparing the number of
*_odr functions after clang has finished IRgen with
>>>>>>>>>>>>> the number after
optimization finishes. This of course would be strictly
>>>>>>>>>>>>> more than functions +
types.
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Wouldn't any function or
symbol using the record type have the
>>>>>>>>>>>> type name somewhere in it? If
we used an offset+length encoding (instead of
>>>>>>>>>>>> offset + NUL termination) we
might be able to reuse it then (at some cost
>>>>>>>>>>>> in finding the reference).
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> That may be possible with some work
in the string table builder.
>>>>>>>>>>> But at that point of course
we're not dealing with regular symbols any
>>>>>>>>>>> more. I guess we could have two ODR
tables per object file: an array of
>>>>>>>>>>> (ODR hash, location) tuples for ODR
names that correspond to symbol table
>>>>>>>>>>> symbols (i.e. Rui's proposal on
the chromium bug), and an array of (ODR
>>>>>>>>>>> name, ODR hash, location) tuples
for all other ODR names. I guess if we
>>>>>>>>>>> wanted a "low overhead"
mode we could just omit the second table or put
>>>>>>>>>>> fewer symbols in it.
>>>>>>>>>>>
>>>>>>>>>>> With debug info surely there is
some sort of string representing
>>>>>>>>>>>> the record name or something
like that, no?
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Not the record name on its own
(they do appear but a bit
>>>>>>>>>>> awkwardly -- each namespace
component is stored in a separate string), but
>>>>>>>>>>> if the record has at least one
member function the mangled type name will
>>>>>>>>>>> appear somewhere in .debug_str, so
we could in principle reuse that with
>>>>>>>>>>> the offset/length trick.
>>>>>>>>>>>
>>>>>>>>>>> I guess we may have to have our
"low-overhead" user-facing
>>>>>>>>>>>> behavior be a bit more nuanced.
E.g.:
>>>>>>>>>>>> 1. does this feature bloat
object files significantly
>>>>>>>>>>>> 2. does this feature slow down
link times significantly
>>>>>>>>>>>>
>>>>>>>>>>>> Intuitively, it seems like we
should be able to get 1. when
>>>>>>>>>>>> debug info happens to be
enabled (not sure about split dwarf?) and possibly
>>>>>>>>>>>> in all cases at the cost of
complexity. We may be able to get 2. in all
>>>>>>>>>>>> cases with proper design.
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> I think that would be my rough
assessment as well. I think we
>>>>>>>>>>> have a good shot at 1 for all cases
with some of the ideas that have been
>>>>>>>>>>> mentioned already. If we can avoid
creating dependencies on DWARF I think
>>>>>>>>>>> that would be ideal -- I'd
ideally like this to work for COFF as well,
>>>>>>>>>>> where you'd typically expect to
find CodeView in object files. If I were to
>>>>>>>>>>> try this I think the first thing
that I would try is hash/compression
>>>>>>>>>>> combined with the two ODR tables
(no reuse for non-symbol ODR names to
>>>>>>>>>>> start with, as compression may be
enough on its own).
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> I developed a second prototype which
uses hash/compression with
>>>>>>>>>> no attempt to reuse. It is available
here:
>>>>>>>>>>
https://github.com/pcc/llvm-project/tree/odr-checker2
>>>>>>>>>>
>>>>>>>>>> For Chromium the object file size
overhead was 536566007 bytes,
>>>>>>>>>> or in relative terms about 25%, or
about 4% with debug info. I measured
>>>>>>>>>> perf overhead for unit_tests at about
6%, but after I moved the checker
>>>>>>>>>> onto another thread, the overhead
disappeared into the noise.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Still seems like quite a big increase.
>>>>>>>>>
>>>>>>>>> Any chance of compression?
>>>>>>>>>
>>>>>>>>
>>>>>>>> That was with compression -- the implementation
compresses the
>>>>>>>> parts of the ODR table that aren't hashes
(aside from the header and the
>>>>>>>> Clang version, which is a small fixed cost), as
well as the string table.
>>>>>>>> The hashes were left uncompressed because they
are in the critical path of
>>>>>>>> the linker and because I imagine that they
wouldn't really be that
>>>>>>>> compressible.
>>>>>>>>
>>>>>>>
>>>>>>> I'd be a bit surprised if they weren't
especially compressible -
>>>>>>>
>>>>>>
>>>>>> Maybe I'm wrong, but my intuition about compression
is that it works
>>>>>> best when the data contains repeated patterns. If we
use a hash function
>>>>>> with good dispersion then I'd expect each hash to
have little in common
>>>>>> with other hashes.
>>>>>>
>>>>>>
>>>>>>> and how much of the size increase is the compressed
data V the
>>>>>>> uncompressed data?
>>>>>>>
>>>>>>
>>>>>> The ratio was roughly 60% compressed data to 40%
uncompressed data.
>>>>>>
>>>>>>
>>>>>>> Is it still in the hot path when parallelized?
>>>>>>>
>>>>>>
>>>>>> Not right now according to my benchmarking, but
decompression could
>>>>>> push it into the critical path if it ends up taking
longer than the rest of
>>>>>> the work done by the linker after symbol resolution. On
the same machine
>>>>>> that I used for benchmarking, gunzip'ing 200MB of
/dev/urandom (which is
>>>>>> roughly what I'd expect the hashes to look like)
takes around 1.1s, i.e. a
>>>>>> not insignificant fraction of lld's runtime.
>>>>>>
>>>>>>
>>>>>>> So I think the remaining gains would either be
through limiting the
>>>>>>>> number of ODR table entries, or through reuse
of data.
>>>>>>>>
>>>>>>>> Limiting might be something to explore -- one
possibility is that
>>>>>>>> we could limit the ODR table entries to the
declarations that are "used" by
>>>>>>>> a particular translation unit (it appears that
Clang tracks something like
>>>>>>>> that in Decl::Used/Decl::Referenced, but
I'm not sure if that is exactly
>>>>>>>> what we need -- I think we would basically need
to test for reference
>>>>>>>> reachability from the functions/globals that
are IRgen'd).
>>>>>>>>
>>>>>>>
>>>>>>> Currently it has every type and function that is in
the AST? Yeah,
>>>>>>> that's a lot - perhaps it should be more like
the things that go in the
>>>>>>> DWARF? (though would need to add some cases there -
since the DWARF logic
>>>>>>> already relies on the ODR to not emit duplicates in
some cases)
>>>>>>>
>>>>>>
>>>>>> Just every record declaration -- Clang only supports
ODR hashes for
>>>>>> record declarations right now. I understand that
function declarations
>>>>>> (including function bodies) are still works in
progress.
>>>>>>
>>>>>> I think it should indeed just be roughly the things
that go in the
>>>>>> DWARF. I think that at one point I observed that every
record declaration,
>>>>>> even unused ones, were going into the DWARF, but I
might have been mistaken
>>>>>> because I can no longer reproduce that. I'll take a
closer look to see if I
>>>>>> can reuse what logic presumably already exists for
DWARF.
>>>>>>
>>>>>> In terms of reuse, it seems that of the 536566007 bytes
of
>>>>>>>> overhead, 319309579 were the compressed part of
the ODR tables. So even if
>>>>>>>> we achieved 100% sharing,
>>>>>>>>
>>>>>>>
>>>>>>> 100% sharing? You mean if all the data were
compressed, and assuming
>>>>>>> the hashes were compressible at the same ratio as
the other data?
>>>>>>>
>>>>>>
>>>>>> Sorry, I mean if 100% of the data in the compressed
part of the ODR
>>>>>> table could be eliminated by reusing data stored
elsewhere (e.g. in the
>>>>>> object file string table or in the DWARF).
>>>>>>
>>>>>> with the current scheme I think that our minimum
achievable overhead
>>>>>>>> would be ~15% (no debug info) or ~2% (with
debug info).
>>>>>>>>
>>>>>>>>
>>>>>>>>> Could this go into .dwo files with Fission
and be checked by dwp
>>>>>>>>> instead, perhaps?
>>>>>>>>>
>>>>>>>>
>>>>>>>> I think it could also work that way, yes.
>>>>>>>>
>>>>>>>> I'm reasonably happy with these figures, at
least for a first
>>>>>>>>>> implementation. We may be able to do
even better for file size with reuse,
>>>>>>>>>> but I'd leave that for version 2.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> What's the story with compatibility
between versions, then? Is
>>>>>>>>> there a version header?
>>>>>>>>>
>>>>>>>>
>>>>>>>> Yes, the header contains a version number.
>>>>>>>>
>>>>>>>>
>>>>>>>>> Will old formats be supported by lld
indefinitely? Not at all?
>>>>>>>>>
>>>>>>>>
>>>>>>>> I think we should drop support for old formats
when we introduce a
>>>>>>>> new format. My understanding is that the ODR
hash can change whenever Clang
>>>>>>>> changes (the implementation only performs ODR
checking if all ODR tables
>>>>>>>> were produced by the same revision of Clang),
so there wouldn't seem to be
>>>>>>>> a huge benefit in keeping support for old
formats around.
>>>>>>>>
>>>>>>>
>>>>>>> I imagine it's possible people aren't
necessarily going to rev lld
>>>>>>> in exact lock-step with clang, but I could be
wrong. (certainly binutils ld
>>>>>>> or gold aren't released/kept in lock-step with
GCC, for example)
>>>>>>>
>>>>>>
>>>>>> That's certainly possible, but I'd say that the
bar for dropping
>>>>>> backwards compatibility is lower because ODR tables are
not required for
>>>>>> correctness. We could keep compatibility with the last
version or so if it
>>>>>> isn't too burdensome, or otherwise print a warning.
>>>>>>
>>>>>
>>>>> They aren't required for correctness, but upgrading
your compiler or
>>>>> linker then silently losing ODR checking would be bad (or
even not silently
>>>>> losing it, but having no choice but to rev both to keep the
functionality &
>>>>> hold the ODR-cleanliness bar) - it's the sort of thing
where if you lost
>>>>> the checking, then gained it back again later, the
regression cleanup would
>>>>> be annoying/an impediment to using the feature.
>>>>>
>>>>
>>>> Makes sense I guess. I'd be fine with a policy where the
Nth open
>>>> source release should be able to read ODR tables produced by
the N-1th and
>>>> possibly the N-2th release.
>>>>
>>>
>>> Still strikes me as a bit awkward - wonder how that compared to
other
>>> (similar or different) linker features.
>>>
>>
>> I think the most similar existing feature is .gdb_index. They have
>> already gone through a few format revisions:
>> https://sourceware.org/gdb/onlinedocs/gdb/Index-Section-Format.html
>> and have deprecated/removed support for older formats.
>>
>> Because the requirements for ODR tables are simpler than those for
>> .gdb_index, I'd expect us to converge on a final format sooner, so
in
>> practice the window of compatibility would end up being longer than a
year.
>>
>> Peter
>>
>>
>>>
>>>> Any idea what Daniel Jasper & co have been working on WRT
ODR checking
>>>>> & how this feature integrates or doesn't with their
work? I imagine they
>>>>> might be working on something more like a Clang Tooling
style approach, but
>>>>> I'm not sure.
>>>>>
>>>>
>>>> I'm not aware of any work like that, only of Richard
Trieu's efforts
>>>> for modules that I'm piggybacking on.
>>>>
>>>
>>> +Djasper - perhaps you could provide some context on other odr
detection
>>> efforts?
>>>
>>>
>>>> Peter
>>>>
>>>>>
>>>>> - Dave
>>>>>
>>>>>
>>>>>>
>>>>>> Peter
>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>>
>>>>>>>> Peter
>>>>>>>>
>>>>>>>>>
>>>>>>>>> - Dave
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Peter
>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Peter
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> -- Sean Silva
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>> The issue of retaining
the ODR check for functions even if
>>>>>>>>>>>>>> they get inlined may
inherently pose an extra cost that can't be folded
>>>>>>>>>>>>>> into existing work the
linker is doing, so there might be a reason for
>>>>>>>>>>>>>> clang to have a default
mode that has practically no linking overhead and
>>>>>>>>>>>>>> one that does more
thorough checking but imposes extra linking overhead.
>>>>>>>>>>>>>> Think something like a
crazy boost library with thousands of functions that
>>>>>>>>>>>>>> get inlined away, but
have gigantic mangled names and so precisely are the
>>>>>>>>>>>>>> ones that are going to
impose extra cost on the linker. Simply due to the
>>>>>>>>>>>>>> extra volume of strings
that the linker would need to look at, I don't
>>>>>>>>>>>>>> think there's a way
to include checking of all inlined function "for free"
>>>>>>>>>>>>>> at the linker level
using the symbol approach.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>> I guess those inlined
functions would still have those symbol
>>>>>>>>>>>>>> names in debug info (I
think?), so piggybacking on the string deduplication
>>>>>>>>>>>>>> we're already doing
might make it possible to fold away the work in that
>>>>>>>>>>>>>> case (but then again,
would still impose extra cost with split dwarf...).
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Anyway, let's wait
to see what the actual performance numbers
>>>>>>>>>>>>>> are.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> -- Sean Silva
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> On Tue, Jun 6, 2017 at
10:40 PM, Peter Collingbourne via
>>>>>>>>>>>>>> cfe-dev <cfe-dev at
lists.llvm.org> wrote:
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Hi all,
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> I'd like to
propose an ODR checker feature for Clang and
>>>>>>>>>>>>>>> LLD. The feature
would be similar to gold's --detect-odr-violations
>>>>>>>>>>>>>>> feature, but
better: we can rely on integration with clang to avoid relying
>>>>>>>>>>>>>>> on debug info and
to perform more precise matching.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> The basic idea is
that we use clang's ability to create ODR
>>>>>>>>>>>>>>> hashes for
declarations. ODR hashes are computed using all information
>>>>>>>>>>>>>>> about a declaration
that is ODR-relevant. If the flag
>>>>>>>>>>>>>>>
-fdetect-odr-violations is passed, Clang will store the ODR hashes in a
>>>>>>>>>>>>>>> so-called ODR table
in each object file. Each ODR table will contain a
>>>>>>>>>>>>>>> mapping from
mangled declaration names to ODR hashes. At link time, the
>>>>>>>>>>>>>>> linker will read
the ODR table and report any mismatches.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> To make this work:
>>>>>>>>>>>>>>> - LLVM will be
extended with the ability to represent ODR
>>>>>>>>>>>>>>> tables in the IR
and emit them to object files
>>>>>>>>>>>>>>> - Clang will be
extended with the ability to emit ODR tables
>>>>>>>>>>>>>>> using ODR hashes
>>>>>>>>>>>>>>> - LLD will be
extended to read ODR tables from object files
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> I have implemented
a prototype of this feature. It is
>>>>>>>>>>>>>>> available here:
>>>>>>>>>>>>>>>
https://github.com/pcc/llvm-project/tree/odr-checker and
>>>>>>>>>>>>>>> some results from
applying it to chromium are here:
>>>>>>>>>>>>>>> crbug.com/726071
>>>>>>>>>>>>>>> As you can see it
did indeed find a number of real ODR
>>>>>>>>>>>>>>> violations in
Chromium, including some that wouldn't be detectable using
>>>>>>>>>>>>>>> debug info.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> If you're
interested in what the format of the ODR table
>>>>>>>>>>>>>>> would look like,
that prototype shows pretty much what I had in mind, but I
>>>>>>>>>>>>>>> expect many other
aspects of the implementation to change as it is
>>>>>>>>>>>>>>> upstreamed.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Thanks,
>>>>>>>>>>>>>>> --
>>>>>>>>>>>>>>> --
>>>>>>>>>>>>>>> Peter
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
_______________________________________________
>>>>>>>>>>>>>>> cfe-dev mailing
list
>>>>>>>>>>>>>>> cfe-dev at
lists.llvm.org
>>>>>>>>>>>>>>>
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> --
>>>>>>>>>>>>> --
>>>>>>>>>>>>> Peter
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> --
>>>>>>>>>>> --
>>>>>>>>>>> Peter
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> --
>>>>>>>>>> --
>>>>>>>>>> Peter
>>>>>>>>>>
_______________________________________________
>>>>>>>>>> cfe-dev mailing list
>>>>>>>>>> cfe-dev at lists.llvm.org
>>>>>>>>>>
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> --
>>>>>>>> --
>>>>>>>> Peter
>>>>>>>>
>>>>>>>
>>>>>>
>>>>>>
>>>>>> --
>>>>>> --
>>>>>> Peter
>>>>>>
>>>>>
>>>>
>>>>
>>>> --
>>>> --
>>>> Peter
>>>>
>>>
>>
>>
>> --
>> --
>> Peter
>>
>> _______________________________________________
>> cfe-dev mailing list
>> cfe-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170615/c9b83956/attachment-0001.html>

On Wed, Jun 14, 2017 at 6:00 PM, Rui Ueyama <ruiu at google.com> wrote:
> Is the entry in your ODR table 64-bit? Sean mentioned that this is a
> birthday paradox situation, but I don't think we need that large hash
> values, as our aim is not to avoid any collisions. Small number of
> collisions is okay as it just slightly increases false negatives. I think
> it can even be 16-bit if space saving is important. If we choose 16-bit
> hash, the probability that an ODR violation is not detected is 1/65536,
> which is still quite low.
>
I'm not too concerned about the false negative rate by switching to a
shorter hash. Both the name hash and the ODR hash would have to match in
order for there to be a false negative. So even with a 16-bit hash the
probability would in fact be something like 1 in 2^(32 + 16).

The birthday paradox issue around using shorter hashes is that if we see a
name hash collision, we need to decompress the compressed part of the ODR
table in both object files. This is necessary both in order to perform a
string comparison to check that the collision was indeed the result of an
ODR violation and to report the error (because the declaration names and
locations are stored in the compressed part). So if the total number of
declarations is large enough we could end up having to perform a
significant amount of decompression. So there's a tradeoff between space
and time.

That said, it would probably be worth measuring what that tradeoff is in
practice.

Peter

> On Wed, Jun 14, 2017 at 1:41 PM, Peter Collingbourne via cfe-dev <
> cfe-dev at lists.llvm.org> wrote:
>
>>
>>
>> On Wed, Jun 14, 2017 at 12:47 PM, David Blaikie <dblaikie at
gmail.com>
>> wrote:
>>
>>>
>>>
>>> On Tue, Jun 13, 2017, 11:30 PM Peter Collingbourne <peter at
pcc.me.uk>
>>> wrote:
>>>
>>>> On Tue, Jun 13, 2017 at 11:06 PM, David Blaikie <dblaikie at
gmail.com>
>>>> wrote:
>>>>
>>>>>
>>>>>
>>>>> On Tue, Jun 13, 2017 at 10:05 PM Peter Collingbourne
<peter at pcc.me.uk>
>>>>> wrote:
>>>>>
>>>>>> On Tue, Jun 13, 2017 at 8:48 PM, David Blaikie
<dblaikie at gmail.com>
>>>>>> wrote:
>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> On Tue, Jun 13, 2017 at 8:43 PM Peter Collingbourne
<peter at pcc.me.uk>
>>>>>>> wrote:
>>>>>>>
>>>>>>>> On Tue, Jun 13, 2017 at 7:54 PM, David Blaikie
<dblaikie at gmail.com>
>>>>>>>> wrote:
>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> On Tue, Jun 13, 2017 at 6:34 PM Peter
Collingbourne via cfe-dev <
>>>>>>>>> cfe-dev at lists.llvm.org> wrote:
>>>>>>>>>
>>>>>>>>>> On Wed, Jun 7, 2017 at 11:28 PM, Peter
Collingbourne <
>>>>>>>>>> peter at pcc.me.uk> wrote:
>>>>>>>>>>
>>>>>>>>>>> On Wed, Jun 7, 2017 at 8:06 PM,
Sean Silva <
>>>>>>>>>>> chisophugis at gmail.com> wrote:
>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> On Wed, Jun 7, 2017 at 4:31 PM,
Peter Collingbourne <
>>>>>>>>>>>> peter at pcc.me.uk> wrote:
>>>>>>>>>>>>
>>>>>>>>>>>>> On Wed, Jun 7, 2017 at
12:17 AM, Sean Silva <
>>>>>>>>>>>>> chisophugis at
gmail.com> wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>>> Very nice and simple
implementation!
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Do you have any
statistics on how large these odr tables are
>>>>>>>>>>>>>> compared to other
object file data? I assume that if these tables contain
>>>>>>>>>>>>>> full mangled symbol
names, they could end up being very large and may want
>>>>>>>>>>>>>> to share the symbol
name strings with the overall string table in the .o
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> Looking at Chromium's
object files it looks like the total
>>>>>>>>>>>>> size of the odrtabs is
about 50% of the total size of the object files,
>>>>>>>>>>>>> which isn't great. The
current implementation only looks at records, so I
>>>>>>>>>>>>> imagine that it would be
hard to share any of the strings that I'm
>>>>>>>>>>>>> currently creating. (I
guess it's possible that some types will have a
>>>>>>>>>>>>> mangled vtable name in the
string table, so we may be able to share a
>>>>>>>>>>>>> little that way.) Note
however that this was without debug info.
>>>>>>>>>>>>>
>>>>>>>>>>>>> One option for reducing
size would be to
>>>>>>>>>>>>> 1) store hashes of ODR
names in ODR tables, per Rui's
>>>>>>>>>>>>> suggestion (alongside a
reference to the name itself in the string table)
>>>>>>>>>>>>> 2) compress the string
table for the ODR names with a standard
>>>>>>>>>>>>> compression algorithm like
gzip.
>>>>>>>>>>>>> This wouldn't seem to
affect link time performance much
>>>>>>>>>>>>> because I think we should
only need to look at the strings if we see a ODR
>>>>>>>>>>>>> name hash match together
with an ODR hash mismatch, which would mean an ODR
>>>>>>>>>>>>> violation with a high
probability (i.e. unless there was an ODR name hash
>>>>>>>>>>>>> collision, we have found an
ODR violation). If we don't expect a lot of
>>>>>>>>>>>>> sharing with regular string
tables (see below), it seems even more
>>>>>>>>>>>>> reasonable.
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Neat observation!
>>>>>>>>>>>>
>>>>>>>>>>>> FWIW, it is a birthday problem
type situation though, so for a
>>>>>>>>>>>> 32-bit hash, we would expect a
collision in about 1 in 2^16 distinct hashes
>>>>>>>>>>>> (and 2^16 seems pretty easy to
hit in a large project). So 64-bit hashes
>>>>>>>>>>>> might be preferable.
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Oh right, good point, using a
64-bit hash does seem like a good
>>>>>>>>>>> idea here.
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>> Also, do you have any
numbers on the performance of your
>>>>>>>>>>>>>> initial implementation?
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> I measured the link time
for chromium's unit_tests (the
>>>>>>>>>>>>> largest single binary in
chromium) at 5.05s without ODR checks and 6.61s
>>>>>>>>>>>>> with ODR checks. So about
30% overhead, but in absolute terms it doesn't
>>>>>>>>>>>>> seem too bad. So I think
this may be acceptable for an initial
>>>>>>>>>>>>> implementation, but it
certainly seems worth trying to do better.
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> I know that things aren't
currently apples-to-apples, but how
>>>>>>>>>>>> does that compare to gold?
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> I will measure it.
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> For that unit_tests binary I measured
the overhead at about 5
>>>>>>>>>> seconds (average of 10 runs). That is
with debug info, of course.
>>>>>>>>>>
>>>>>>>>>> W.r.t. LLD and having it always on by
default (and hence making
>>>>>>>>>>>>>> it as fast as
possible), it seems like right now you are implementing the
>>>>>>>>>>>>>> checking process with a
hash table. That's simple and fine for a first
>>>>>>>>>>>>>> implementation, but
it's probably worth mentioning in a comment the problem
>>>>>>>>>>>>>> of checking the tables,
at least from the linker's perspective, does fit
>>>>>>>>>>>>>> into a map-reduce
pattern and could be easily parallelized if needed. E.g.
>>>>>>>>>>>>>> a parallel sort to
coalesce all entries for symbols of the same name
>>>>>>>>>>>>>> followed by a parallel
forEach to check each bucket with the same symbol
>>>>>>>>>>>>>> name (roughly
speaking).
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> Right, that's one
approach. I was thinking of a simpler
>>>>>>>>>>>>> approach where at compile
time we sort ODR names by hash and partition them
>>>>>>>>>>>>> using (say) the upper bits
of the hash, so that at link time we can have N
>>>>>>>>>>>>> threads each building a
hash table for a specific partition.
>>>>>>>>>>>>>
>>>>>>>>>>>>> And of course this work can
be started right after symbol
>>>>>>>>>>>>> resolution finishes and
parallelised with the rest of the work done by the
>>>>>>>>>>>>> linker.
>>>>>>>>>>>>>
>>>>>>>>>>>>> Even better than doing it
faster is just doing less work.
>>>>>>>>>>>>>> There's a lot of
work that the linker is already doing that may be reusable
>>>>>>>>>>>>>> for the ODR checking.
>>>>>>>>>>>>>> E.g.
>>>>>>>>>>>>>> - maybe we could get
the coalescing step as a byproduct of
>>>>>>>>>>>>>> our existing string
deduping, which we are generally doing anyway.
>>>>>>>>>>>>>> - we are already
coalescing symbol names for the symbol
>>>>>>>>>>>>>> table. If the ODR table
is keyed off of symbols in the binary that we are
>>>>>>>>>>>>>> inserting into the
symbol table, then I think we could do the entire ODR
>>>>>>>>>>>>>> check with no extra
"string" work on LLD's part.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> I see Rui already
mentioned some of this in
>>>>>>>>>>>>>>
https://bugs.chromium.org/p/chromium/issues/detail?id=726
>>>>>>>>>>>>>> 071#c4.
>>>>>>>>>>>>>> You mentioned that not
everything is necessarily directly
>>>>>>>>>>>>>> keyed on a symbol (such
as types), but I think that it would really
>>>>>>>>>>>>>> simplify things if the
check was done as such. Do you have any idea exactly
>>>>>>>>>>>>>> how much of the things
that we want to check are not keyed on symbols? If
>>>>>>>>>>>>>> most things are keyed
on symbols, for the things we are not we can just
>>>>>>>>>>>>>> emit extra symbols
prefixed by __clang_odr_check_ or whatever.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> Since the current
implementation only works with records there
>>>>>>>>>>>>> is basically zero overlap
right now between ODR names and symbols. I
>>>>>>>>>>>>> suppose that I could
estimate the amount of function overlap in a
>>>>>>>>>>>>> hypothetical implementation
that computes ODR hashes of functions by
>>>>>>>>>>>>> comparing the number of
*_odr functions after clang has finished IRgen with
>>>>>>>>>>>>> the number after
optimization finishes. This of course would be strictly
>>>>>>>>>>>>> more than functions +
types.
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Wouldn't any function or
symbol using the record type have the
>>>>>>>>>>>> type name somewhere in it? If
we used an offset+length encoding (instead of
>>>>>>>>>>>> offset + NUL termination) we
might be able to reuse it then (at some cost
>>>>>>>>>>>> in finding the reference).
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> That may be possible with some work
in the string table builder.
>>>>>>>>>>> But at that point of course
we're not dealing with regular symbols any
>>>>>>>>>>> more. I guess we could have two ODR
tables per object file: an array of
>>>>>>>>>>> (ODR hash, location) tuples for ODR
names that correspond to symbol table
>>>>>>>>>>> symbols (i.e. Rui's proposal on
the chromium bug), and an array of (ODR
>>>>>>>>>>> name, ODR hash, location) tuples
for all other ODR names. I guess if we
>>>>>>>>>>> wanted a "low overhead"
mode we could just omit the second table or put
>>>>>>>>>>> fewer symbols in it.
>>>>>>>>>>>
>>>>>>>>>>> With debug info surely there is
some sort of string representing
>>>>>>>>>>>> the record name or something
like that, no?
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Not the record name on its own
(they do appear but a bit
>>>>>>>>>>> awkwardly -- each namespace
component is stored in a separate string), but
>>>>>>>>>>> if the record has at least one
member function the mangled type name will
>>>>>>>>>>> appear somewhere in .debug_str, so
we could in principle reuse that with
>>>>>>>>>>> the offset/length trick.
>>>>>>>>>>>
>>>>>>>>>>> I guess we may have to have our
"low-overhead" user-facing
>>>>>>>>>>>> behavior be a bit more nuanced.
E.g.:
>>>>>>>>>>>> 1. does this feature bloat
object files significantly
>>>>>>>>>>>> 2. does this feature slow down
link times significantly
>>>>>>>>>>>>
>>>>>>>>>>>> Intuitively, it seems like we
should be able to get 1. when
>>>>>>>>>>>> debug info happens to be
enabled (not sure about split dwarf?) and possibly
>>>>>>>>>>>> in all cases at the cost of
complexity. We may be able to get 2. in all
>>>>>>>>>>>> cases with proper design.
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> I think that would be my rough
assessment as well. I think we
>>>>>>>>>>> have a good shot at 1 for all cases
with some of the ideas that have been
>>>>>>>>>>> mentioned already. If we can avoid
creating dependencies on DWARF I think
>>>>>>>>>>> that would be ideal -- I'd
ideally like this to work for COFF as well,
>>>>>>>>>>> where you'd typically expect to
find CodeView in object files. If I were to
>>>>>>>>>>> try this I think the first thing
that I would try is hash/compression
>>>>>>>>>>> combined with the two ODR tables
(no reuse for non-symbol ODR names to
>>>>>>>>>>> start with, as compression may be
enough on its own).
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> I developed a second prototype which
uses hash/compression with
>>>>>>>>>> no attempt to reuse. It is available
here:
>>>>>>>>>>
https://github.com/pcc/llvm-project/tree/odr-checker2
>>>>>>>>>>
>>>>>>>>>> For Chromium the object file size
overhead was 536566007 bytes,
>>>>>>>>>> or in relative terms about 25%, or
about 4% with debug info. I measured
>>>>>>>>>> perf overhead for unit_tests at about
6%, but after I moved the checker
>>>>>>>>>> onto another thread, the overhead
disappeared into the noise.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Still seems like quite a big increase.
>>>>>>>>>
>>>>>>>>> Any chance of compression?
>>>>>>>>>
>>>>>>>>
>>>>>>>> That was with compression -- the implementation
compresses the
>>>>>>>> parts of the ODR table that aren't hashes
(aside from the header and the
>>>>>>>> Clang version, which is a small fixed cost), as
well as the string table.
>>>>>>>> The hashes were left uncompressed because they
are in the critical path of
>>>>>>>> the linker and because I imagine that they
wouldn't really be that
>>>>>>>> compressible.
>>>>>>>>
>>>>>>>
>>>>>>> I'd be a bit surprised if they weren't
especially compressible -
>>>>>>>
>>>>>>
>>>>>> Maybe I'm wrong, but my intuition about compression
is that it works
>>>>>> best when the data contains repeated patterns. If we
use a hash function
>>>>>> with good dispersion then I'd expect each hash to
have little in common
>>>>>> with other hashes.
>>>>>>
>>>>>>
>>>>>>> and how much of the size increase is the compressed
data V the
>>>>>>> uncompressed data?
>>>>>>>
>>>>>>
>>>>>> The ratio was roughly 60% compressed data to 40%
uncompressed data.
>>>>>>
>>>>>>
>>>>>>> Is it still in the hot path when parallelized?
>>>>>>>
>>>>>>
>>>>>> Not right now according to my benchmarking, but
decompression could
>>>>>> push it into the critical path if it ends up taking
longer than the rest of
>>>>>> the work done by the linker after symbol resolution. On
the same machine
>>>>>> that I used for benchmarking, gunzip'ing 200MB of
/dev/urandom (which is
>>>>>> roughly what I'd expect the hashes to look like)
takes around 1.1s, i.e. a
>>>>>> not insignificant fraction of lld's runtime.
>>>>>>
>>>>>>
>>>>>>> So I think the remaining gains would either be
through limiting the
>>>>>>>> number of ODR table entries, or through reuse
of data.
>>>>>>>>
>>>>>>>> Limiting might be something to explore -- one
possibility is that
>>>>>>>> we could limit the ODR table entries to the
declarations that are "used" by
>>>>>>>> a particular translation unit (it appears that
Clang tracks something like
>>>>>>>> that in Decl::Used/Decl::Referenced, but
I'm not sure if that is exactly
>>>>>>>> what we need -- I think we would basically need
to test for reference
>>>>>>>> reachability from the functions/globals that
are IRgen'd).
>>>>>>>>
>>>>>>>
>>>>>>> Currently it has every type and function that is in
the AST? Yeah,
>>>>>>> that's a lot - perhaps it should be more like
the things that go in the
>>>>>>> DWARF? (though would need to add some cases there -
since the DWARF logic
>>>>>>> already relies on the ODR to not emit duplicates in
some cases)
>>>>>>>
>>>>>>
>>>>>> Just every record declaration -- Clang only supports
ODR hashes for
>>>>>> record declarations right now. I understand that
function declarations
>>>>>> (including function bodies) are still works in
progress.
>>>>>>
>>>>>> I think it should indeed just be roughly the things
that go in the
>>>>>> DWARF. I think that at one point I observed that every
record declaration,
>>>>>> even unused ones, were going into the DWARF, but I
might have been mistaken
>>>>>> because I can no longer reproduce that. I'll take a
closer look to see if I
>>>>>> can reuse what logic presumably already exists for
DWARF.
>>>>>>
>>>>>> In terms of reuse, it seems that of the 536566007 bytes
of
>>>>>>>> overhead, 319309579 were the compressed part of
the ODR tables. So even if
>>>>>>>> we achieved 100% sharing,
>>>>>>>>
>>>>>>>
>>>>>>> 100% sharing? You mean if all the data were
compressed, and assuming
>>>>>>> the hashes were compressible at the same ratio as
the other data?
>>>>>>>
>>>>>>
>>>>>> Sorry, I mean if 100% of the data in the compressed
part of the ODR
>>>>>> table could be eliminated by reusing data stored
elsewhere (e.g. in the
>>>>>> object file string table or in the DWARF).
>>>>>>
>>>>>> with the current scheme I think that our minimum
achievable overhead
>>>>>>>> would be ~15% (no debug info) or ~2% (with
debug info).
>>>>>>>>
>>>>>>>>
>>>>>>>>> Could this go into .dwo files with Fission
and be checked by dwp
>>>>>>>>> instead, perhaps?
>>>>>>>>>
>>>>>>>>
>>>>>>>> I think it could also work that way, yes.
>>>>>>>>
>>>>>>>> I'm reasonably happy with these figures, at
least for a first
>>>>>>>>>> implementation. We may be able to do
even better for file size with reuse,
>>>>>>>>>> but I'd leave that for version 2.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> What's the story with compatibility
between versions, then? Is
>>>>>>>>> there a version header?
>>>>>>>>>
>>>>>>>>
>>>>>>>> Yes, the header contains a version number.
>>>>>>>>
>>>>>>>>
>>>>>>>>> Will old formats be supported by lld
indefinitely? Not at all?
>>>>>>>>>
>>>>>>>>
>>>>>>>> I think we should drop support for old formats
when we introduce a
>>>>>>>> new format. My understanding is that the ODR
hash can change whenever Clang
>>>>>>>> changes (the implementation only performs ODR
checking if all ODR tables
>>>>>>>> were produced by the same revision of Clang),
so there wouldn't seem to be
>>>>>>>> a huge benefit in keeping support for old
formats around.
>>>>>>>>
>>>>>>>
>>>>>>> I imagine it's possible people aren't
necessarily going to rev lld
>>>>>>> in exact lock-step with clang, but I could be
wrong. (certainly binutils ld
>>>>>>> or gold aren't released/kept in lock-step with
GCC, for example)
>>>>>>>
>>>>>>
>>>>>> That's certainly possible, but I'd say that the
bar for dropping
>>>>>> backwards compatibility is lower because ODR tables are
not required for
>>>>>> correctness. We could keep compatibility with the last
version or so if it
>>>>>> isn't too burdensome, or otherwise print a warning.
>>>>>>
>>>>>
>>>>> They aren't required for correctness, but upgrading
your compiler or
>>>>> linker then silently losing ODR checking would be bad (or
even not silently
>>>>> losing it, but having no choice but to rev both to keep the
functionality &
>>>>> hold the ODR-cleanliness bar) - it's the sort of thing
where if you lost
>>>>> the checking, then gained it back again later, the
regression cleanup would
>>>>> be annoying/an impediment to using the feature.
>>>>>
>>>>
>>>> Makes sense I guess. I'd be fine with a policy where the
Nth open
>>>> source release should be able to read ODR tables produced by
the N-1th and
>>>> possibly the N-2th release.
>>>>
>>>
>>> Still strikes me as a bit awkward - wonder how that compared to
other
>>> (similar or different) linker features.
>>>
>>
>> I think the most similar existing feature is .gdb_index. They have
>> already gone through a few format revisions:
>> https://sourceware.org/gdb/onlinedocs/gdb/Index-Section-Format.html
>> and have deprecated/removed support for older formats.
>>
>> Because the requirements for ODR tables are simpler than those for
>> .gdb_index, I'd expect us to converge on a final format sooner, so
in
>> practice the window of compatibility would end up being longer than a
year.
>>
>> Peter
>>
>>
>>>
>>>> Any idea what Daniel Jasper & co have been working on WRT
ODR checking
>>>>> & how this feature integrates or doesn't with their
work? I imagine they
>>>>> might be working on something more like a Clang Tooling
style approach, but
>>>>> I'm not sure.
>>>>>
>>>>
>>>> I'm not aware of any work like that, only of Richard
Trieu's efforts
>>>> for modules that I'm piggybacking on.
>>>>
>>>
>>> +Djasper - perhaps you could provide some context on other odr
detection
>>> efforts?
>>>
>>>
>>>> Peter
>>>>
>>>>>
>>>>> - Dave
>>>>>
>>>>>
>>>>>>
>>>>>> Peter
>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>>
>>>>>>>> Peter
>>>>>>>>
>>>>>>>>>
>>>>>>>>> - Dave
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Peter
>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Peter
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> -- Sean Silva
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>> The issue of retaining
the ODR check for functions even if
>>>>>>>>>>>>>> they get inlined may
inherently pose an extra cost that can't be folded
>>>>>>>>>>>>>> into existing work the
linker is doing, so there might be a reason for
>>>>>>>>>>>>>> clang to have a default
mode that has practically no linking overhead and
>>>>>>>>>>>>>> one that does more
thorough checking but imposes extra linking overhead.
>>>>>>>>>>>>>> Think something like a
crazy boost library with thousands of functions that
>>>>>>>>>>>>>> get inlined away, but
have gigantic mangled names and so precisely are the
>>>>>>>>>>>>>> ones that are going to
impose extra cost on the linker. Simply due to the
>>>>>>>>>>>>>> extra volume of strings
that the linker would need to look at, I don't
>>>>>>>>>>>>>> think there's a way
to include checking of all inlined function "for free"
>>>>>>>>>>>>>> at the linker level
using the symbol approach.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>> I guess those inlined
functions would still have those symbol
>>>>>>>>>>>>>> names in debug info (I
think?), so piggybacking on the string deduplication
>>>>>>>>>>>>>> we're already doing
might make it possible to fold away the work in that
>>>>>>>>>>>>>> case (but then again,
would still impose extra cost with split dwarf...).
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Anyway, let's wait
to see what the actual performance numbers
>>>>>>>>>>>>>> are.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> -- Sean Silva
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> On Tue, Jun 6, 2017 at
10:40 PM, Peter Collingbourne via
>>>>>>>>>>>>>> cfe-dev <cfe-dev at
lists.llvm.org> wrote:
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Hi all,
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> I'd like to
propose an ODR checker feature for Clang and
>>>>>>>>>>>>>>> LLD. The feature
would be similar to gold's --detect-odr-violations
>>>>>>>>>>>>>>> feature, but
better: we can rely on integration with clang to avoid relying
>>>>>>>>>>>>>>> on debug info and
to perform more precise matching.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> The basic idea is
that we use clang's ability to create ODR
>>>>>>>>>>>>>>> hashes for
declarations. ODR hashes are computed using all information
>>>>>>>>>>>>>>> about a declaration
that is ODR-relevant. If the flag
>>>>>>>>>>>>>>>
-fdetect-odr-violations is passed, Clang will store the ODR hashes in a
>>>>>>>>>>>>>>> so-called ODR table
in each object file. Each ODR table will contain a
>>>>>>>>>>>>>>> mapping from
mangled declaration names to ODR hashes. At link time, the
>>>>>>>>>>>>>>> linker will read
the ODR table and report any mismatches.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> To make this work:
>>>>>>>>>>>>>>> - LLVM will be
extended with the ability to represent ODR
>>>>>>>>>>>>>>> tables in the IR
and emit them to object files
>>>>>>>>>>>>>>> - Clang will be
extended with the ability to emit ODR tables
>>>>>>>>>>>>>>> using ODR hashes
>>>>>>>>>>>>>>> - LLD will be
extended to read ODR tables from object files
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> I have implemented
a prototype of this feature. It is
>>>>>>>>>>>>>>> available here:
https://github.com/pcc/l
>>>>>>>>>>>>>>>
lvm-project/tree/odr-checker and some results from applying
>>>>>>>>>>>>>>> it to chromium are
here: crbug.com/726071
>>>>>>>>>>>>>>> As you can see it
did indeed find a number of real ODR
>>>>>>>>>>>>>>> violations in
Chromium, including some that wouldn't be detectable using
>>>>>>>>>>>>>>> debug info.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> If you're
interested in what the format of the ODR table
>>>>>>>>>>>>>>> would look like,
that prototype shows pretty much what I had in mind, but I
>>>>>>>>>>>>>>> expect many other
aspects of the implementation to change as it is
>>>>>>>>>>>>>>> upstreamed.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Thanks,
>>>>>>>>>>>>>>> --
>>>>>>>>>>>>>>> --
>>>>>>>>>>>>>>> Peter
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
_______________________________________________
>>>>>>>>>>>>>>> cfe-dev mailing
list
>>>>>>>>>>>>>>> cfe-dev at
lists.llvm.org
>>>>>>>>>>>>>>>
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> --
>>>>>>>>>>>>> --
>>>>>>>>>>>>> Peter
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> --
>>>>>>>>>>> --
>>>>>>>>>>> Peter
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> --
>>>>>>>>>> --
>>>>>>>>>> Peter
>>>>>>>>>>
_______________________________________________
>>>>>>>>>> cfe-dev mailing list
>>>>>>>>>> cfe-dev at lists.llvm.org
>>>>>>>>>>
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> --
>>>>>>>> --
>>>>>>>> Peter
>>>>>>>>
>>>>>>>
>>>>>>
>>>>>>
>>>>>> --
>>>>>> --
>>>>>> Peter
>>>>>>
>>>>>
>>>>
>>>>
>>>> --
>>>> --
>>>> Peter
>>>>
>>>
>>
>>
>> --
>> --
>> Peter
>>
>> _______________________________________________
>> cfe-dev mailing list
>> cfe-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>>
>>
>

-- 
-- 
Peter
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170614/23f5c0c2/attachment.html>

I think you are right -- I always confuse false positives with false
negatives. What I wanted to say is collisions increase a chance that an ODR
violation is not detected.

On Wed, Jun 14, 2017 at 6:15 PM, David Blaikie <dblaikie at gmail.com>
wrote:
>
>
> On Wed, Jun 14, 2017 at 6:01 PM Rui Ueyama <ruiu at google.com>
wrote:
>
>> Is the entry in your ODR table 64-bit? Sean mentioned that this is a
>> birthday paradox situation, but I don't think we need that large
hash
>> values, as our aim is not to avoid any collisions. Small number of
>> collisions is okay as it just slightly increases false negatives. I
think
>> it can even be 16-bit if space saving is important. If we choose 16-bit
>> hash, the probability that an ODR violation is not detected is 1/65536,
>> which is still quite low.
>>
>
> If I'm understanding this correctly, it's the opposite though -
colliding
> hashes will produce false positives, right? (ODR violations will be
> detected where none exist in the code) Perhaps I'm misunderstanding.
>
>
>>
>> On Wed, Jun 14, 2017 at 1:41 PM, Peter Collingbourne via cfe-dev <
>> cfe-dev at lists.llvm.org> wrote:
>>
>>>
>>>
>>> On Wed, Jun 14, 2017 at 12:47 PM, David Blaikie <dblaikie at
gmail.com>
>>> wrote:
>>>
>>>>
>>>>
>>>> On Tue, Jun 13, 2017, 11:30 PM Peter Collingbourne <peter at
pcc.me.uk>
>>>> wrote:
>>>>
>>>>> On Tue, Jun 13, 2017 at 11:06 PM, David Blaikie
<dblaikie at gmail.com>
>>>>> wrote:
>>>>>
>>>>>>
>>>>>>
>>>>>> On Tue, Jun 13, 2017 at 10:05 PM Peter Collingbourne
<peter at pcc.me.uk>
>>>>>> wrote:
>>>>>>
>>>>>>> On Tue, Jun 13, 2017 at 8:48 PM, David Blaikie
<dblaikie at gmail.com>
>>>>>>> wrote:
>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> On Tue, Jun 13, 2017 at 8:43 PM Peter
Collingbourne <
>>>>>>>> peter at pcc.me.uk> wrote:
>>>>>>>>
>>>>>>>>> On Tue, Jun 13, 2017 at 7:54 PM, David
Blaikie <dblaikie at gmail.com
>>>>>>>>> > wrote:
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> On Tue, Jun 13, 2017 at 6:34 PM Peter
Collingbourne via cfe-dev <
>>>>>>>>>> cfe-dev at lists.llvm.org> wrote:
>>>>>>>>>>
>>>>>>>>>>> On Wed, Jun 7, 2017 at 11:28 PM,
Peter Collingbourne <
>>>>>>>>>>> peter at pcc.me.uk> wrote:
>>>>>>>>>>>
>>>>>>>>>>>> On Wed, Jun 7, 2017 at 8:06 PM,
Sean Silva <
>>>>>>>>>>>> chisophugis at gmail.com>
wrote:
>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> On Wed, Jun 7, 2017 at 4:31
PM, Peter Collingbourne <
>>>>>>>>>>>>> peter at pcc.me.uk>
wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>>> On Wed, Jun 7, 2017 at
12:17 AM, Sean Silva <
>>>>>>>>>>>>>> chisophugis at
gmail.com> wrote:
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Very nice and
simple implementation!
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Do you have any
statistics on how large these odr tables are
>>>>>>>>>>>>>>> compared to other
object file data? I assume that if these tables contain
>>>>>>>>>>>>>>> full mangled symbol
names, they could end up being very large and may want
>>>>>>>>>>>>>>> to share the symbol
name strings with the overall string table in the .o
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Looking at
Chromium's object files it looks like the total
>>>>>>>>>>>>>> size of the odrtabs is
about 50% of the total size of the object files,
>>>>>>>>>>>>>> which isn't great.
The current implementation only looks at records, so I
>>>>>>>>>>>>>> imagine that it would
be hard to share any of the strings that I'm
>>>>>>>>>>>>>> currently creating. (I
guess it's possible that some types will have a
>>>>>>>>>>>>>> mangled vtable name in
the string table, so we may be able to share a
>>>>>>>>>>>>>> little that way.) Note
however that this was without debug info.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> One option for reducing
size would be to
>>>>>>>>>>>>>> 1) store hashes of ODR
names in ODR tables, per Rui's
>>>>>>>>>>>>>> suggestion (alongside a
reference to the name itself in the string table)
>>>>>>>>>>>>>> 2) compress the string
table for the ODR names with a
>>>>>>>>>>>>>> standard compression
algorithm like gzip.
>>>>>>>>>>>>>> This wouldn't seem
to affect link time performance much
>>>>>>>>>>>>>> because I think we
should only need to look at the strings if we see a ODR
>>>>>>>>>>>>>> name hash match
together with an ODR hash mismatch, which would mean an ODR
>>>>>>>>>>>>>> violation with a high
probability (i.e. unless there was an ODR name hash
>>>>>>>>>>>>>> collision, we have
found an ODR violation). If we don't expect a lot of
>>>>>>>>>>>>>> sharing with regular
string tables (see below), it seems even more
>>>>>>>>>>>>>> reasonable.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> Neat observation!
>>>>>>>>>>>>>
>>>>>>>>>>>>> FWIW, it is a birthday
problem type situation though, so for a
>>>>>>>>>>>>> 32-bit hash, we would
expect a collision in about 1 in 2^16 distinct hashes
>>>>>>>>>>>>> (and 2^16 seems pretty easy
to hit in a large project). So 64-bit hashes
>>>>>>>>>>>>> might be preferable.
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Oh right, good point, using a
64-bit hash does seem like a good
>>>>>>>>>>>> idea here.
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>> Also, do you have any
numbers on the performance of your
>>>>>>>>>>>>>>> initial
implementation?
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> I measured the link
time for chromium's unit_tests (the
>>>>>>>>>>>>>> largest single binary
in chromium) at 5.05s without ODR checks and 6.61s
>>>>>>>>>>>>>> with ODR checks. So
about 30% overhead, but in absolute terms it doesn't
>>>>>>>>>>>>>> seem too bad. So I
think this may be acceptable for an initial
>>>>>>>>>>>>>> implementation, but it
certainly seems worth trying to do better.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> I know that things
aren't currently apples-to-apples, but how
>>>>>>>>>>>>> does that compare to gold?
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> I will measure it.
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> For that unit_tests binary I
measured the overhead at about 5
>>>>>>>>>>> seconds (average of 10 runs). That
is with debug info, of course.
>>>>>>>>>>>
>>>>>>>>>>> W.r.t. LLD and having it always on
by default (and hence making
>>>>>>>>>>>>>>> it as fast as
possible), it seems like right now you are implementing the
>>>>>>>>>>>>>>> checking process
with a hash table. That's simple and fine for a first
>>>>>>>>>>>>>>> implementation, but
it's probably worth mentioning in a comment the problem
>>>>>>>>>>>>>>> of checking the
tables, at least from the linker's perspective, does fit
>>>>>>>>>>>>>>> into a map-reduce
pattern and could be easily parallelized if needed. E.g.
>>>>>>>>>>>>>>> a parallel sort to
coalesce all entries for symbols of the same name
>>>>>>>>>>>>>>> followed by a
parallel forEach to check each bucket with the same symbol
>>>>>>>>>>>>>>> name (roughly
speaking).
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Right, that's one
approach. I was thinking of a simpler
>>>>>>>>>>>>>> approach where at
compile time we sort ODR names by hash and partition them
>>>>>>>>>>>>>> using (say) the upper
bits of the hash, so that at link time we can have N
>>>>>>>>>>>>>> threads each building a
hash table for a specific partition.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> And of course this work
can be started right after symbol
>>>>>>>>>>>>>> resolution finishes and
parallelised with the rest of the work done by the
>>>>>>>>>>>>>> linker.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Even better than doing
it faster is just doing less work.
>>>>>>>>>>>>>>> There's a lot
of work that the linker is already doing that may be reusable
>>>>>>>>>>>>>>> for the ODR
checking.
>>>>>>>>>>>>>>> E.g.
>>>>>>>>>>>>>>> - maybe we could
get the coalescing step as a byproduct of
>>>>>>>>>>>>>>> our existing string
deduping, which we are generally doing anyway.
>>>>>>>>>>>>>>> - we are already
coalescing symbol names for the symbol
>>>>>>>>>>>>>>> table. If the ODR
table is keyed off of symbols in the binary that we are
>>>>>>>>>>>>>>> inserting into the
symbol table, then I think we could do the entire ODR
>>>>>>>>>>>>>>> check with no extra
"string" work on LLD's part.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> I see Rui already
mentioned some of this in
>>>>>>>>>>>>>>>
https://bugs.chromium.org/p/chromium/issues/detail?id>>>>>>>>>>>>>>>
726071#c4.
>>>>>>>>>>>>>>> You mentioned that
not everything is necessarily directly
>>>>>>>>>>>>>>> keyed on a symbol
(such as types), but I think that it would really
>>>>>>>>>>>>>>> simplify things if
the check was done as such. Do you have any idea exactly
>>>>>>>>>>>>>>> how much of the
things that we want to check are not keyed on symbols? If
>>>>>>>>>>>>>>> most things are
keyed on symbols, for the things we are not we can just
>>>>>>>>>>>>>>> emit extra symbols
prefixed by __clang_odr_check_ or whatever.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Since the current
implementation only works with records
>>>>>>>>>>>>>> there is basically zero
overlap right now between ODR names and symbols. I
>>>>>>>>>>>>>> suppose that I could
estimate the amount of function overlap in a
>>>>>>>>>>>>>> hypothetical
implementation that computes ODR hashes of functions by
>>>>>>>>>>>>>> comparing the number of
*_odr functions after clang has finished IRgen with
>>>>>>>>>>>>>> the number after
optimization finishes. This of course would be strictly
>>>>>>>>>>>>>> more than functions +
types.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> Wouldn't any function
or symbol using the record type have the
>>>>>>>>>>>>> type name somewhere in it?
If we used an offset+length encoding (instead of
>>>>>>>>>>>>> offset + NUL termination)
we might be able to reuse it then (at some cost
>>>>>>>>>>>>> in finding the reference).
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> That may be possible with some
work in the string table
>>>>>>>>>>>> builder. But at that point of
course we're not dealing with regular symbols
>>>>>>>>>>>> any more. I guess we could have
two ODR tables per object file: an array of
>>>>>>>>>>>> (ODR hash, location) tuples for
ODR names that correspond to symbol table
>>>>>>>>>>>> symbols (i.e. Rui's
proposal on the chromium bug), and an array of (ODR
>>>>>>>>>>>> name, ODR hash, location)
tuples for all other ODR names. I guess if we
>>>>>>>>>>>> wanted a "low
overhead" mode we could just omit the second table or put
>>>>>>>>>>>> fewer symbols in it.
>>>>>>>>>>>>
>>>>>>>>>>>> With debug info surely there is
some sort of string
>>>>>>>>>>>>> representing the record
name or something like that, no?
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Not the record name on its own
(they do appear but a bit
>>>>>>>>>>>> awkwardly -- each namespace
component is stored in a separate string), but
>>>>>>>>>>>> if the record has at least one
member function the mangled type name will
>>>>>>>>>>>> appear somewhere in .debug_str,
so we could in principle reuse that with
>>>>>>>>>>>> the offset/length trick.
>>>>>>>>>>>>
>>>>>>>>>>>> I guess we may have to have our
"low-overhead" user-facing
>>>>>>>>>>>>> behavior be a bit more
nuanced. E.g.:
>>>>>>>>>>>>> 1. does this feature bloat
object files significantly
>>>>>>>>>>>>> 2. does this feature slow
down link times significantly
>>>>>>>>>>>>>
>>>>>>>>>>>>> Intuitively, it seems like
we should be able to get 1. when
>>>>>>>>>>>>> debug info happens to be
enabled (not sure about split dwarf?) and possibly
>>>>>>>>>>>>> in all cases at the cost of
complexity. We may be able to get 2. in all
>>>>>>>>>>>>> cases with proper design.
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> I think that would be my rough
assessment as well. I think we
>>>>>>>>>>>> have a good shot at 1 for all
cases with some of the ideas that have been
>>>>>>>>>>>> mentioned already. If we can
avoid creating dependencies on DWARF I think
>>>>>>>>>>>> that would be ideal -- I'd
ideally like this to work for COFF as well,
>>>>>>>>>>>> where you'd typically
expect to find CodeView in object files. If I were to
>>>>>>>>>>>> try this I think the first
thing that I would try is hash/compression
>>>>>>>>>>>> combined with the two ODR
tables (no reuse for non-symbol ODR names to
>>>>>>>>>>>> start with, as compression may
be enough on its own).
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> I developed a second prototype
which uses hash/compression with
>>>>>>>>>>> no attempt to reuse. It is
available here:
>>>>>>>>>>>
https://github.com/pcc/llvm-project/tree/odr-checker2
>>>>>>>>>>>
>>>>>>>>>>> For Chromium the object file size
overhead was 536566007 bytes,
>>>>>>>>>>> or in relative terms about 25%, or
about 4% with debug info. I measured
>>>>>>>>>>> perf overhead for unit_tests at
about 6%, but after I moved the checker
>>>>>>>>>>> onto another thread, the overhead
disappeared into the noise.
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Still seems like quite a big increase.
>>>>>>>>>>
>>>>>>>>>> Any chance of compression?
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> That was with compression -- the
implementation compresses the
>>>>>>>>> parts of the ODR table that aren't
hashes (aside from the header and the
>>>>>>>>> Clang version, which is a small fixed
cost), as well as the string table.
>>>>>>>>> The hashes were left uncompressed because
they are in the critical path of
>>>>>>>>> the linker and because I imagine that they
wouldn't really be that
>>>>>>>>> compressible.
>>>>>>>>>
>>>>>>>>
>>>>>>>> I'd be a bit surprised if they weren't
especially compressible -
>>>>>>>>
>>>>>>>
>>>>>>> Maybe I'm wrong, but my intuition about
compression is that it works
>>>>>>> best when the data contains repeated patterns. If
we use a hash function
>>>>>>> with good dispersion then I'd expect each hash
to have little in common
>>>>>>> with other hashes.
>>>>>>>
>>>>>>>
>>>>>>>> and how much of the size increase is the
compressed data V the
>>>>>>>> uncompressed data?
>>>>>>>>
>>>>>>>
>>>>>>> The ratio was roughly 60% compressed data to 40%
uncompressed data.
>>>>>>>
>>>>>>>
>>>>>>>> Is it still in the hot path when parallelized?
>>>>>>>>
>>>>>>>
>>>>>>> Not right now according to my benchmarking, but
decompression could
>>>>>>> push it into the critical path if it ends up taking
longer than the rest of
>>>>>>> the work done by the linker after symbol
resolution. On the same machine
>>>>>>> that I used for benchmarking, gunzip'ing 200MB
of /dev/urandom (which is
>>>>>>> roughly what I'd expect the hashes to look
like) takes around 1.1s, i.e. a
>>>>>>> not insignificant fraction of lld's runtime.
>>>>>>>
>>>>>>>
>>>>>>>> So I think the remaining gains would either be
through limiting the
>>>>>>>>> number of ODR table entries, or through
reuse of data.
>>>>>>>>>
>>>>>>>>> Limiting might be something to explore --
one possibility is that
>>>>>>>>> we could limit the ODR table entries to the
declarations that are "used" by
>>>>>>>>> a particular translation unit (it appears
that Clang tracks something like
>>>>>>>>> that in Decl::Used/Decl::Referenced, but
I'm not sure if that is exactly
>>>>>>>>> what we need -- I think we would basically
need to test for reference
>>>>>>>>> reachability from the functions/globals
that are IRgen'd).
>>>>>>>>>
>>>>>>>>
>>>>>>>> Currently it has every type and function that
is in the AST? Yeah,
>>>>>>>> that's a lot - perhaps it should be more
like the things that go in the
>>>>>>>> DWARF? (though would need to add some cases
there - since the DWARF logic
>>>>>>>> already relies on the ODR to not emit
duplicates in some cases)
>>>>>>>>
>>>>>>>
>>>>>>> Just every record declaration -- Clang only
supports ODR hashes for
>>>>>>> record declarations right now. I understand that
function declarations
>>>>>>> (including function bodies) are still works in
progress.
>>>>>>>
>>>>>>> I think it should indeed just be roughly the things
that go in the
>>>>>>> DWARF. I think that at one point I observed that
every record declaration,
>>>>>>> even unused ones, were going into the DWARF, but I
might have been mistaken
>>>>>>> because I can no longer reproduce that. I'll
take a closer look to see if I
>>>>>>> can reuse what logic presumably already exists for
DWARF.
>>>>>>>
>>>>>>> In terms of reuse, it seems that of the 536566007
bytes of
>>>>>>>>> overhead, 319309579 were the compressed
part of the ODR tables. So even if
>>>>>>>>> we achieved 100% sharing,
>>>>>>>>>
>>>>>>>>
>>>>>>>> 100% sharing? You mean if all the data were
compressed, and
>>>>>>>> assuming the hashes were compressible at the
same ratio as the other data?
>>>>>>>>
>>>>>>>
>>>>>>> Sorry, I mean if 100% of the data in the compressed
part of the ODR
>>>>>>> table could be eliminated by reusing data stored
elsewhere (e.g. in the
>>>>>>> object file string table or in the DWARF).
>>>>>>>
>>>>>>> with the current scheme I think that our minimum
achievable overhead
>>>>>>>>> would be ~15% (no debug info) or ~2% (with
debug info).
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>> Could this go into .dwo files with
Fission and be checked by dwp
>>>>>>>>>> instead, perhaps?
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> I think it could also work that way, yes.
>>>>>>>>>
>>>>>>>>> I'm reasonably happy with these
figures, at least for a first
>>>>>>>>>>> implementation. We may be able to
do even better for file size with reuse,
>>>>>>>>>>> but I'd leave that for version
2.
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> What's the story with compatibility
between versions, then? Is
>>>>>>>>>> there a version header?
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Yes, the header contains a version number.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>> Will old formats be supported by lld
indefinitely? Not at all?
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> I think we should drop support for old
formats when we introduce a
>>>>>>>>> new format. My understanding is that the
ODR hash can change whenever Clang
>>>>>>>>> changes (the implementation only performs
ODR checking if all ODR tables
>>>>>>>>> were produced by the same revision of
Clang), so there wouldn't seem to be
>>>>>>>>> a huge benefit in keeping support for old
formats around.
>>>>>>>>>
>>>>>>>>
>>>>>>>> I imagine it's possible people aren't
necessarily going to rev lld
>>>>>>>> in exact lock-step with clang, but I could be
wrong. (certainly binutils ld
>>>>>>>> or gold aren't released/kept in lock-step
with GCC, for example)
>>>>>>>>
>>>>>>>
>>>>>>> That's certainly possible, but I'd say that
the bar for dropping
>>>>>>> backwards compatibility is lower because ODR tables
are not required for
>>>>>>> correctness. We could keep compatibility with the
last version or so if it
>>>>>>> isn't too burdensome, or otherwise print a
warning.
>>>>>>>
>>>>>>
>>>>>> They aren't required for correctness, but upgrading
your compiler or
>>>>>> linker then silently losing ODR checking would be bad
(or even not silently
>>>>>> losing it, but having no choice but to rev both to keep
the functionality &
>>>>>> hold the ODR-cleanliness bar) - it's the sort of
thing where if you lost
>>>>>> the checking, then gained it back again later, the
regression cleanup would
>>>>>> be annoying/an impediment to using the feature.
>>>>>>
>>>>>
>>>>> Makes sense I guess. I'd be fine with a policy where
the Nth open
>>>>> source release should be able to read ODR tables produced
by the N-1th and
>>>>> possibly the N-2th release.
>>>>>
>>>>
>>>> Still strikes me as a bit awkward - wonder how that compared to
other
>>>> (similar or different) linker features.
>>>>
>>>
>>> I think the most similar existing feature is .gdb_index. They have
>>> already gone through a few format revisions:
>>> https://sourceware.org/gdb/onlinedocs/gdb/Index-Section-Format.html
>>> and have deprecated/removed support for older formats.
>>>
>>> Because the requirements for ODR tables are simpler than those for
>>> .gdb_index, I'd expect us to converge on a final format sooner,
so in
>>> practice the window of compatibility would end up being longer than
a year.
>>>
>>> Peter
>>>
>>>
>>>>
>>>>> Any idea what Daniel Jasper & co have been working on
WRT ODR checking
>>>>>> & how this feature integrates or doesn't with
their work? I imagine they
>>>>>> might be working on something more like a Clang Tooling
style approach, but
>>>>>> I'm not sure.
>>>>>>
>>>>>
>>>>> I'm not aware of any work like that, only of Richard
Trieu's efforts
>>>>> for modules that I'm piggybacking on.
>>>>>
>>>>
>>>> +Djasper - perhaps you could provide some context on other odr
>>>> detection efforts?
>>>>
>>>>
>>>>> Peter
>>>>>
>>>>>>
>>>>>> - Dave
>>>>>>
>>>>>>
>>>>>>>
>>>>>>> Peter
>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>>
>>>>>>>>> Peter
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> - Dave
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Peter
>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Peter
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> -- Sean Silva
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> The issue of
retaining the ODR check for functions even if
>>>>>>>>>>>>>>> they get inlined
may inherently pose an extra cost that can't be folded
>>>>>>>>>>>>>>> into existing work
the linker is doing, so there might be a reason for
>>>>>>>>>>>>>>> clang to have a
default mode that has practically no linking overhead and
>>>>>>>>>>>>>>> one that does more
thorough checking but imposes extra linking overhead.
>>>>>>>>>>>>>>> Think something
like a crazy boost library with thousands of functions that
>>>>>>>>>>>>>>> get inlined away,
but have gigantic mangled names and so precisely are the
>>>>>>>>>>>>>>> ones that are going
to impose extra cost on the linker. Simply due to the
>>>>>>>>>>>>>>> extra volume of
strings that the linker would need to look at, I don't
>>>>>>>>>>>>>>> think there's a
way to include checking of all inlined function "for free"
>>>>>>>>>>>>>>> at the linker level
using the symbol approach.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>> I guess those inlined
functions would still have those symbol
>>>>>>>>>>>>>>> names in debug info
(I think?), so piggybacking on the string deduplication
>>>>>>>>>>>>>>> we're already
doing might make it possible to fold away the work in that
>>>>>>>>>>>>>>> case (but then
again, would still impose extra cost with split dwarf...).
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Anyway, let's
wait to see what the actual performance
>>>>>>>>>>>>>>> numbers are.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> -- Sean Silva
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> On Tue, Jun 6, 2017
at 10:40 PM, Peter Collingbourne via
>>>>>>>>>>>>>>> cfe-dev <cfe-dev
at lists.llvm.org> wrote:
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> Hi all,
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> I'd like to
propose an ODR checker feature for Clang and
>>>>>>>>>>>>>>>> LLD. The
feature would be similar to gold's --detect-odr-violations
>>>>>>>>>>>>>>>> feature, but
better: we can rely on integration with clang to avoid relying
>>>>>>>>>>>>>>>> on debug info
and to perform more precise matching.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> The basic idea
is that we use clang's ability to create ODR
>>>>>>>>>>>>>>>> hashes for
declarations. ODR hashes are computed using all information
>>>>>>>>>>>>>>>> about a
declaration that is ODR-relevant. If the flag
>>>>>>>>>>>>>>>>
-fdetect-odr-violations is passed, Clang will store the ODR hashes in a
>>>>>>>>>>>>>>>> so-called ODR
table in each object file. Each ODR table will contain a
>>>>>>>>>>>>>>>> mapping from
mangled declaration names to ODR hashes. At link time, the
>>>>>>>>>>>>>>>> linker will
read the ODR table and report any mismatches.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> To make this
work:
>>>>>>>>>>>>>>>> - LLVM will be
extended with the ability to represent ODR
>>>>>>>>>>>>>>>> tables in the
IR and emit them to object files
>>>>>>>>>>>>>>>> - Clang will be
extended with the ability to emit ODR
>>>>>>>>>>>>>>>> tables using
ODR hashes
>>>>>>>>>>>>>>>> - LLD will be
extended to read ODR tables from object files
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> I have
implemented a prototype of this feature. It is
>>>>>>>>>>>>>>>> available here:
https://github.com/pcc/
>>>>>>>>>>>>>>>>
llvm-project/tree/odr-checker and some results from
>>>>>>>>>>>>>>>> applying it to
chromium are here: crbug.com/726071
>>>>>>>>>>>>>>>> As you can see
it did indeed find a number of real ODR
>>>>>>>>>>>>>>>> violations in
Chromium, including some that wouldn't be detectable using
>>>>>>>>>>>>>>>> debug info.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> If you're
interested in what the format of the ODR table
>>>>>>>>>>>>>>>> would look
like, that prototype shows pretty much what I had in mind, but I
>>>>>>>>>>>>>>>> expect many
other aspects of the implementation to change as it is
>>>>>>>>>>>>>>>> upstreamed.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> Thanks,
>>>>>>>>>>>>>>>> --
>>>>>>>>>>>>>>>> --
>>>>>>>>>>>>>>>> Peter
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
_______________________________________________
>>>>>>>>>>>>>>>> cfe-dev mailing
list
>>>>>>>>>>>>>>>> cfe-dev at
lists.llvm.org
>>>>>>>>>>>>>>>>
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> --
>>>>>>>>>>>>>> --
>>>>>>>>>>>>>> Peter
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> --
>>>>>>>>>>>> --
>>>>>>>>>>>> Peter
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> --
>>>>>>>>>>> --
>>>>>>>>>>> Peter
>>>>>>>>>>>
_______________________________________________
>>>>>>>>>>> cfe-dev mailing list
>>>>>>>>>>> cfe-dev at lists.llvm.org
>>>>>>>>>>>
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> --
>>>>>>>>> --
>>>>>>>>> Peter
>>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> --
>>>>>>> Peter
>>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> --
>>>>> Peter
>>>>>
>>>>
>>>
>>>
>>> --
>>> --
>>> Peter
>>>
>>> _______________________________________________
>>> cfe-dev mailing list
>>> cfe-dev at lists.llvm.org
>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>>>
>>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170614/5f838e07/attachment-0001.html>

On Wed, Jun 14, 2017 at 6:15 PM, David Blaikie <dblaikie at gmail.com>
wrote:
>
>
> On Wed, Jun 14, 2017 at 6:01 PM Rui Ueyama <ruiu at google.com>
wrote:
>
>> Is the entry in your ODR table 64-bit? Sean mentioned that this is a
>> birthday paradox situation, but I don't think we need that large
hash
>> values, as our aim is not to avoid any collisions. Small number of
>> collisions is okay as it just slightly increases false negatives. I
think
>> it can even be 16-bit if space saving is important. If we choose 16-bit
>> hash, the probability that an ODR violation is not detected is 1/65536,
>> which is still quite low.
>>
>
> If I'm understanding this correctly, it's the opposite though -
colliding
> hashes will produce false positives, right? (ODR violations will be
> detected where none exist in the code) Perhaps I'm misunderstanding.
>
Colliding hashes should not result in false positives because they will
cause the checker to decompress both ODR tables and perform a string
comparison of the full demangled ODR names.

Peter
>
>
>>
>> On Wed, Jun 14, 2017 at 1:41 PM, Peter Collingbourne via cfe-dev <
>> cfe-dev at lists.llvm.org> wrote:
>>
>>>
>>>
>>> On Wed, Jun 14, 2017 at 12:47 PM, David Blaikie <dblaikie at
gmail.com>
>>> wrote:
>>>
>>>>
>>>>
>>>> On Tue, Jun 13, 2017, 11:30 PM Peter Collingbourne <peter at
pcc.me.uk>
>>>> wrote:
>>>>
>>>>> On Tue, Jun 13, 2017 at 11:06 PM, David Blaikie
<dblaikie at gmail.com>
>>>>> wrote:
>>>>>
>>>>>>
>>>>>>
>>>>>> On Tue, Jun 13, 2017 at 10:05 PM Peter Collingbourne
<peter at pcc.me.uk>
>>>>>> wrote:
>>>>>>
>>>>>>> On Tue, Jun 13, 2017 at 8:48 PM, David Blaikie
<dblaikie at gmail.com>
>>>>>>> wrote:
>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> On Tue, Jun 13, 2017 at 8:43 PM Peter
Collingbourne <
>>>>>>>> peter at pcc.me.uk> wrote:
>>>>>>>>
>>>>>>>>> On Tue, Jun 13, 2017 at 7:54 PM, David
Blaikie <dblaikie at gmail.com
>>>>>>>>> > wrote:
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> On Tue, Jun 13, 2017 at 6:34 PM Peter
Collingbourne via cfe-dev <
>>>>>>>>>> cfe-dev at lists.llvm.org> wrote:
>>>>>>>>>>
>>>>>>>>>>> On Wed, Jun 7, 2017 at 11:28 PM,
Peter Collingbourne <
>>>>>>>>>>> peter at pcc.me.uk> wrote:
>>>>>>>>>>>
>>>>>>>>>>>> On Wed, Jun 7, 2017 at 8:06 PM,
Sean Silva <
>>>>>>>>>>>> chisophugis at gmail.com>
wrote:
>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> On Wed, Jun 7, 2017 at 4:31
PM, Peter Collingbourne <
>>>>>>>>>>>>> peter at pcc.me.uk>
wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>>> On Wed, Jun 7, 2017 at
12:17 AM, Sean Silva <
>>>>>>>>>>>>>> chisophugis at
gmail.com> wrote:
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Very nice and
simple implementation!
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Do you have any
statistics on how large these odr tables are
>>>>>>>>>>>>>>> compared to other
object file data? I assume that if these tables contain
>>>>>>>>>>>>>>> full mangled symbol
names, they could end up being very large and may want
>>>>>>>>>>>>>>> to share the symbol
name strings with the overall string table in the .o
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Looking at
Chromium's object files it looks like the total
>>>>>>>>>>>>>> size of the odrtabs is
about 50% of the total size of the object files,
>>>>>>>>>>>>>> which isn't great.
The current implementation only looks at records, so I
>>>>>>>>>>>>>> imagine that it would
be hard to share any of the strings that I'm
>>>>>>>>>>>>>> currently creating. (I
guess it's possible that some types will have a
>>>>>>>>>>>>>> mangled vtable name in
the string table, so we may be able to share a
>>>>>>>>>>>>>> little that way.) Note
however that this was without debug info.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> One option for reducing
size would be to
>>>>>>>>>>>>>> 1) store hashes of ODR
names in ODR tables, per Rui's
>>>>>>>>>>>>>> suggestion (alongside a
reference to the name itself in the string table)
>>>>>>>>>>>>>> 2) compress the string
table for the ODR names with a
>>>>>>>>>>>>>> standard compression
algorithm like gzip.
>>>>>>>>>>>>>> This wouldn't seem
to affect link time performance much
>>>>>>>>>>>>>> because I think we
should only need to look at the strings if we see a ODR
>>>>>>>>>>>>>> name hash match
together with an ODR hash mismatch, which would mean an ODR
>>>>>>>>>>>>>> violation with a high
probability (i.e. unless there was an ODR name hash
>>>>>>>>>>>>>> collision, we have
found an ODR violation). If we don't expect a lot of
>>>>>>>>>>>>>> sharing with regular
string tables (see below), it seems even more
>>>>>>>>>>>>>> reasonable.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> Neat observation!
>>>>>>>>>>>>>
>>>>>>>>>>>>> FWIW, it is a birthday
problem type situation though, so for a
>>>>>>>>>>>>> 32-bit hash, we would
expect a collision in about 1 in 2^16 distinct hashes
>>>>>>>>>>>>> (and 2^16 seems pretty easy
to hit in a large project). So 64-bit hashes
>>>>>>>>>>>>> might be preferable.
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Oh right, good point, using a
64-bit hash does seem like a good
>>>>>>>>>>>> idea here.
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>> Also, do you have any
numbers on the performance of your
>>>>>>>>>>>>>>> initial
implementation?
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> I measured the link
time for chromium's unit_tests (the
>>>>>>>>>>>>>> largest single binary
in chromium) at 5.05s without ODR checks and 6.61s
>>>>>>>>>>>>>> with ODR checks. So
about 30% overhead, but in absolute terms it doesn't
>>>>>>>>>>>>>> seem too bad. So I
think this may be acceptable for an initial
>>>>>>>>>>>>>> implementation, but it
certainly seems worth trying to do better.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> I know that things
aren't currently apples-to-apples, but how
>>>>>>>>>>>>> does that compare to gold?
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> I will measure it.
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> For that unit_tests binary I
measured the overhead at about 5
>>>>>>>>>>> seconds (average of 10 runs). That
is with debug info, of course.
>>>>>>>>>>>
>>>>>>>>>>> W.r.t. LLD and having it always on
by default (and hence making
>>>>>>>>>>>>>>> it as fast as
possible), it seems like right now you are implementing the
>>>>>>>>>>>>>>> checking process
with a hash table. That's simple and fine for a first
>>>>>>>>>>>>>>> implementation, but
it's probably worth mentioning in a comment the problem
>>>>>>>>>>>>>>> of checking the
tables, at least from the linker's perspective, does fit
>>>>>>>>>>>>>>> into a map-reduce
pattern and could be easily parallelized if needed. E.g.
>>>>>>>>>>>>>>> a parallel sort to
coalesce all entries for symbols of the same name
>>>>>>>>>>>>>>> followed by a
parallel forEach to check each bucket with the same symbol
>>>>>>>>>>>>>>> name (roughly
speaking).
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Right, that's one
approach. I was thinking of a simpler
>>>>>>>>>>>>>> approach where at
compile time we sort ODR names by hash and partition them
>>>>>>>>>>>>>> using (say) the upper
bits of the hash, so that at link time we can have N
>>>>>>>>>>>>>> threads each building a
hash table for a specific partition.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> And of course this work
can be started right after symbol
>>>>>>>>>>>>>> resolution finishes and
parallelised with the rest of the work done by the
>>>>>>>>>>>>>> linker.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Even better than doing
it faster is just doing less work.
>>>>>>>>>>>>>>> There's a lot
of work that the linker is already doing that may be reusable
>>>>>>>>>>>>>>> for the ODR
checking.
>>>>>>>>>>>>>>> E.g.
>>>>>>>>>>>>>>> - maybe we could
get the coalescing step as a byproduct of
>>>>>>>>>>>>>>> our existing string
deduping, which we are generally doing anyway.
>>>>>>>>>>>>>>> - we are already
coalescing symbol names for the symbol
>>>>>>>>>>>>>>> table. If the ODR
table is keyed off of symbols in the binary that we are
>>>>>>>>>>>>>>> inserting into the
symbol table, then I think we could do the entire ODR
>>>>>>>>>>>>>>> check with no extra
"string" work on LLD's part.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> I see Rui already
mentioned some of this in
>>>>>>>>>>>>>>>
https://bugs.chromium.org/p/chromium/issues/detail?id>>>>>>>>>>>>>>>
726071#c4.
>>>>>>>>>>>>>>> You mentioned that
not everything is necessarily directly
>>>>>>>>>>>>>>> keyed on a symbol
(such as types), but I think that it would really
>>>>>>>>>>>>>>> simplify things if
the check was done as such. Do you have any idea exactly
>>>>>>>>>>>>>>> how much of the
things that we want to check are not keyed on symbols? If
>>>>>>>>>>>>>>> most things are
keyed on symbols, for the things we are not we can just
>>>>>>>>>>>>>>> emit extra symbols
prefixed by __clang_odr_check_ or whatever.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Since the current
implementation only works with records
>>>>>>>>>>>>>> there is basically zero
overlap right now between ODR names and symbols. I
>>>>>>>>>>>>>> suppose that I could
estimate the amount of function overlap in a
>>>>>>>>>>>>>> hypothetical
implementation that computes ODR hashes of functions by
>>>>>>>>>>>>>> comparing the number of
*_odr functions after clang has finished IRgen with
>>>>>>>>>>>>>> the number after
optimization finishes. This of course would be strictly
>>>>>>>>>>>>>> more than functions +
types.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> Wouldn't any function
or symbol using the record type have the
>>>>>>>>>>>>> type name somewhere in it?
If we used an offset+length encoding (instead of
>>>>>>>>>>>>> offset + NUL termination)
we might be able to reuse it then (at some cost
>>>>>>>>>>>>> in finding the reference).
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> That may be possible with some
work in the string table
>>>>>>>>>>>> builder. But at that point of
course we're not dealing with regular symbols
>>>>>>>>>>>> any more. I guess we could have
two ODR tables per object file: an array of
>>>>>>>>>>>> (ODR hash, location) tuples for
ODR names that correspond to symbol table
>>>>>>>>>>>> symbols (i.e. Rui's
proposal on the chromium bug), and an array of (ODR
>>>>>>>>>>>> name, ODR hash, location)
tuples for all other ODR names. I guess if we
>>>>>>>>>>>> wanted a "low
overhead" mode we could just omit the second table or put
>>>>>>>>>>>> fewer symbols in it.
>>>>>>>>>>>>
>>>>>>>>>>>> With debug info surely there is
some sort of string
>>>>>>>>>>>>> representing the record
name or something like that, no?
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Not the record name on its own
(they do appear but a bit
>>>>>>>>>>>> awkwardly -- each namespace
component is stored in a separate string), but
>>>>>>>>>>>> if the record has at least one
member function the mangled type name will
>>>>>>>>>>>> appear somewhere in .debug_str,
so we could in principle reuse that with
>>>>>>>>>>>> the offset/length trick.
>>>>>>>>>>>>
>>>>>>>>>>>> I guess we may have to have our
"low-overhead" user-facing
>>>>>>>>>>>>> behavior be a bit more
nuanced. E.g.:
>>>>>>>>>>>>> 1. does this feature bloat
object files significantly
>>>>>>>>>>>>> 2. does this feature slow
down link times significantly
>>>>>>>>>>>>>
>>>>>>>>>>>>> Intuitively, it seems like
we should be able to get 1. when
>>>>>>>>>>>>> debug info happens to be
enabled (not sure about split dwarf?) and possibly
>>>>>>>>>>>>> in all cases at the cost of
complexity. We may be able to get 2. in all
>>>>>>>>>>>>> cases with proper design.
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> I think that would be my rough
assessment as well. I think we
>>>>>>>>>>>> have a good shot at 1 for all
cases with some of the ideas that have been
>>>>>>>>>>>> mentioned already. If we can
avoid creating dependencies on DWARF I think
>>>>>>>>>>>> that would be ideal -- I'd
ideally like this to work for COFF as well,
>>>>>>>>>>>> where you'd typically
expect to find CodeView in object files. If I were to
>>>>>>>>>>>> try this I think the first
thing that I would try is hash/compression
>>>>>>>>>>>> combined with the two ODR
tables (no reuse for non-symbol ODR names to
>>>>>>>>>>>> start with, as compression may
be enough on its own).
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> I developed a second prototype
which uses hash/compression with
>>>>>>>>>>> no attempt to reuse. It is
available here:
>>>>>>>>>>>
https://github.com/pcc/llvm-project/tree/odr-checker2
>>>>>>>>>>>
>>>>>>>>>>> For Chromium the object file size
overhead was 536566007 bytes,
>>>>>>>>>>> or in relative terms about 25%, or
about 4% with debug info. I measured
>>>>>>>>>>> perf overhead for unit_tests at
about 6%, but after I moved the checker
>>>>>>>>>>> onto another thread, the overhead
disappeared into the noise.
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Still seems like quite a big increase.
>>>>>>>>>>
>>>>>>>>>> Any chance of compression?
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> That was with compression -- the
implementation compresses the
>>>>>>>>> parts of the ODR table that aren't
hashes (aside from the header and the
>>>>>>>>> Clang version, which is a small fixed
cost), as well as the string table.
>>>>>>>>> The hashes were left uncompressed because
they are in the critical path of
>>>>>>>>> the linker and because I imagine that they
wouldn't really be that
>>>>>>>>> compressible.
>>>>>>>>>
>>>>>>>>
>>>>>>>> I'd be a bit surprised if they weren't
especially compressible -
>>>>>>>>
>>>>>>>
>>>>>>> Maybe I'm wrong, but my intuition about
compression is that it works
>>>>>>> best when the data contains repeated patterns. If
we use a hash function
>>>>>>> with good dispersion then I'd expect each hash
to have little in common
>>>>>>> with other hashes.
>>>>>>>
>>>>>>>
>>>>>>>> and how much of the size increase is the
compressed data V the
>>>>>>>> uncompressed data?
>>>>>>>>
>>>>>>>
>>>>>>> The ratio was roughly 60% compressed data to 40%
uncompressed data.
>>>>>>>
>>>>>>>
>>>>>>>> Is it still in the hot path when parallelized?
>>>>>>>>
>>>>>>>
>>>>>>> Not right now according to my benchmarking, but
decompression could
>>>>>>> push it into the critical path if it ends up taking
longer than the rest of
>>>>>>> the work done by the linker after symbol
resolution. On the same machine
>>>>>>> that I used for benchmarking, gunzip'ing 200MB
of /dev/urandom (which is
>>>>>>> roughly what I'd expect the hashes to look
like) takes around 1.1s, i.e. a
>>>>>>> not insignificant fraction of lld's runtime.
>>>>>>>
>>>>>>>
>>>>>>>> So I think the remaining gains would either be
through limiting the
>>>>>>>>> number of ODR table entries, or through
reuse of data.
>>>>>>>>>
>>>>>>>>> Limiting might be something to explore --
one possibility is that
>>>>>>>>> we could limit the ODR table entries to the
declarations that are "used" by
>>>>>>>>> a particular translation unit (it appears
that Clang tracks something like
>>>>>>>>> that in Decl::Used/Decl::Referenced, but
I'm not sure if that is exactly
>>>>>>>>> what we need -- I think we would basically
need to test for reference
>>>>>>>>> reachability from the functions/globals
that are IRgen'd).
>>>>>>>>>
>>>>>>>>
>>>>>>>> Currently it has every type and function that
is in the AST? Yeah,
>>>>>>>> that's a lot - perhaps it should be more
like the things that go in the
>>>>>>>> DWARF? (though would need to add some cases
there - since the DWARF logic
>>>>>>>> already relies on the ODR to not emit
duplicates in some cases)
>>>>>>>>
>>>>>>>
>>>>>>> Just every record declaration -- Clang only
supports ODR hashes for
>>>>>>> record declarations right now. I understand that
function declarations
>>>>>>> (including function bodies) are still works in
progress.
>>>>>>>
>>>>>>> I think it should indeed just be roughly the things
that go in the
>>>>>>> DWARF. I think that at one point I observed that
every record declaration,
>>>>>>> even unused ones, were going into the DWARF, but I
might have been mistaken
>>>>>>> because I can no longer reproduce that. I'll
take a closer look to see if I
>>>>>>> can reuse what logic presumably already exists for
DWARF.
>>>>>>>
>>>>>>> In terms of reuse, it seems that of the 536566007
bytes of
>>>>>>>>> overhead, 319309579 were the compressed
part of the ODR tables. So even if
>>>>>>>>> we achieved 100% sharing,
>>>>>>>>>
>>>>>>>>
>>>>>>>> 100% sharing? You mean if all the data were
compressed, and
>>>>>>>> assuming the hashes were compressible at the
same ratio as the other data?
>>>>>>>>
>>>>>>>
>>>>>>> Sorry, I mean if 100% of the data in the compressed
part of the ODR
>>>>>>> table could be eliminated by reusing data stored
elsewhere (e.g. in the
>>>>>>> object file string table or in the DWARF).
>>>>>>>
>>>>>>> with the current scheme I think that our minimum
achievable overhead
>>>>>>>>> would be ~15% (no debug info) or ~2% (with
debug info).
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>> Could this go into .dwo files with
Fission and be checked by dwp
>>>>>>>>>> instead, perhaps?
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> I think it could also work that way, yes.
>>>>>>>>>
>>>>>>>>> I'm reasonably happy with these
figures, at least for a first
>>>>>>>>>>> implementation. We may be able to
do even better for file size with reuse,
>>>>>>>>>>> but I'd leave that for version
2.
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> What's the story with compatibility
between versions, then? Is
>>>>>>>>>> there a version header?
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Yes, the header contains a version number.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>> Will old formats be supported by lld
indefinitely? Not at all?
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> I think we should drop support for old
formats when we introduce a
>>>>>>>>> new format. My understanding is that the
ODR hash can change whenever Clang
>>>>>>>>> changes (the implementation only performs
ODR checking if all ODR tables
>>>>>>>>> were produced by the same revision of
Clang), so there wouldn't seem to be
>>>>>>>>> a huge benefit in keeping support for old
formats around.
>>>>>>>>>
>>>>>>>>
>>>>>>>> I imagine it's possible people aren't
necessarily going to rev lld
>>>>>>>> in exact lock-step with clang, but I could be
wrong. (certainly binutils ld
>>>>>>>> or gold aren't released/kept in lock-step
with GCC, for example)
>>>>>>>>
>>>>>>>
>>>>>>> That's certainly possible, but I'd say that
the bar for dropping
>>>>>>> backwards compatibility is lower because ODR tables
are not required for
>>>>>>> correctness. We could keep compatibility with the
last version or so if it
>>>>>>> isn't too burdensome, or otherwise print a
warning.
>>>>>>>
>>>>>>
>>>>>> They aren't required for correctness, but upgrading
your compiler or
>>>>>> linker then silently losing ODR checking would be bad
(or even not silently
>>>>>> losing it, but having no choice but to rev both to keep
the functionality &
>>>>>> hold the ODR-cleanliness bar) - it's the sort of
thing where if you lost
>>>>>> the checking, then gained it back again later, the
regression cleanup would
>>>>>> be annoying/an impediment to using the feature.
>>>>>>
>>>>>
>>>>> Makes sense I guess. I'd be fine with a policy where
the Nth open
>>>>> source release should be able to read ODR tables produced
by the N-1th and
>>>>> possibly the N-2th release.
>>>>>
>>>>
>>>> Still strikes me as a bit awkward - wonder how that compared to
other
>>>> (similar or different) linker features.
>>>>
>>>
>>> I think the most similar existing feature is .gdb_index. They have
>>> already gone through a few format revisions:
>>> https://sourceware.org/gdb/onlinedocs/gdb/Index-Section-Format.html
>>> and have deprecated/removed support for older formats.
>>>
>>> Because the requirements for ODR tables are simpler than those for
>>> .gdb_index, I'd expect us to converge on a final format sooner,
so in
>>> practice the window of compatibility would end up being longer than
a year.
>>>
>>> Peter
>>>
>>>
>>>>
>>>>> Any idea what Daniel Jasper & co have been working on
WRT ODR checking
>>>>>> & how this feature integrates or doesn't with
their work? I imagine they
>>>>>> might be working on something more like a Clang Tooling
style approach, but
>>>>>> I'm not sure.
>>>>>>
>>>>>
>>>>> I'm not aware of any work like that, only of Richard
Trieu's efforts
>>>>> for modules that I'm piggybacking on.
>>>>>
>>>>
>>>> +Djasper - perhaps you could provide some context on other odr
>>>> detection efforts?
>>>>
>>>>
>>>>> Peter
>>>>>
>>>>>>
>>>>>> - Dave
>>>>>>
>>>>>>
>>>>>>>
>>>>>>> Peter
>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>>
>>>>>>>>> Peter
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> - Dave
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Peter
>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Peter
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> -- Sean Silva
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> The issue of
retaining the ODR check for functions even if
>>>>>>>>>>>>>>> they get inlined
may inherently pose an extra cost that can't be folded
>>>>>>>>>>>>>>> into existing work
the linker is doing, so there might be a reason for
>>>>>>>>>>>>>>> clang to have a
default mode that has practically no linking overhead and
>>>>>>>>>>>>>>> one that does more
thorough checking but imposes extra linking overhead.
>>>>>>>>>>>>>>> Think something
like a crazy boost library with thousands of functions that
>>>>>>>>>>>>>>> get inlined away,
but have gigantic mangled names and so precisely are the
>>>>>>>>>>>>>>> ones that are going
to impose extra cost on the linker. Simply due to the
>>>>>>>>>>>>>>> extra volume of
strings that the linker would need to look at, I don't
>>>>>>>>>>>>>>> think there's a
way to include checking of all inlined function "for free"
>>>>>>>>>>>>>>> at the linker level
using the symbol approach.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>> I guess those inlined
functions would still have those symbol
>>>>>>>>>>>>>>> names in debug info
(I think?), so piggybacking on the string deduplication
>>>>>>>>>>>>>>> we're already
doing might make it possible to fold away the work in that
>>>>>>>>>>>>>>> case (but then
again, would still impose extra cost with split dwarf...).
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Anyway, let's
wait to see what the actual performance
>>>>>>>>>>>>>>> numbers are.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> -- Sean Silva
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> On Tue, Jun 6, 2017
at 10:40 PM, Peter Collingbourne via
>>>>>>>>>>>>>>> cfe-dev <cfe-dev
at lists.llvm.org> wrote:
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> Hi all,
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> I'd like to
propose an ODR checker feature for Clang and
>>>>>>>>>>>>>>>> LLD. The
feature would be similar to gold's --detect-odr-violations
>>>>>>>>>>>>>>>> feature, but
better: we can rely on integration with clang to avoid relying
>>>>>>>>>>>>>>>> on debug info
and to perform more precise matching.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> The basic idea
is that we use clang's ability to create ODR
>>>>>>>>>>>>>>>> hashes for
declarations. ODR hashes are computed using all information
>>>>>>>>>>>>>>>> about a
declaration that is ODR-relevant. If the flag
>>>>>>>>>>>>>>>>
-fdetect-odr-violations is passed, Clang will store the ODR hashes in a
>>>>>>>>>>>>>>>> so-called ODR
table in each object file. Each ODR table will contain a
>>>>>>>>>>>>>>>> mapping from
mangled declaration names to ODR hashes. At link time, the
>>>>>>>>>>>>>>>> linker will
read the ODR table and report any mismatches.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> To make this
work:
>>>>>>>>>>>>>>>> - LLVM will be
extended with the ability to represent ODR
>>>>>>>>>>>>>>>> tables in the
IR and emit them to object files
>>>>>>>>>>>>>>>> - Clang will be
extended with the ability to emit ODR
>>>>>>>>>>>>>>>> tables using
ODR hashes
>>>>>>>>>>>>>>>> - LLD will be
extended to read ODR tables from object files
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> I have
implemented a prototype of this feature. It is
>>>>>>>>>>>>>>>> available here:
https://github.com/pcc/
>>>>>>>>>>>>>>>>
llvm-project/tree/odr-checker and some results from
>>>>>>>>>>>>>>>> applying it to
chromium are here: crbug.com/726071
>>>>>>>>>>>>>>>> As you can see
it did indeed find a number of real ODR
>>>>>>>>>>>>>>>> violations in
Chromium, including some that wouldn't be detectable using
>>>>>>>>>>>>>>>> debug info.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> If you're
interested in what the format of the ODR table
>>>>>>>>>>>>>>>> would look
like, that prototype shows pretty much what I had in mind, but I
>>>>>>>>>>>>>>>> expect many
other aspects of the implementation to change as it is
>>>>>>>>>>>>>>>> upstreamed.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> Thanks,
>>>>>>>>>>>>>>>> --
>>>>>>>>>>>>>>>> --
>>>>>>>>>>>>>>>> Peter
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
_______________________________________________
>>>>>>>>>>>>>>>> cfe-dev mailing
list
>>>>>>>>>>>>>>>> cfe-dev at
lists.llvm.org
>>>>>>>>>>>>>>>>
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> --
>>>>>>>>>>>>>> --
>>>>>>>>>>>>>> Peter
>>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> --
>>>>>>>>>>>> --
>>>>>>>>>>>> Peter
>>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> --
>>>>>>>>>>> --
>>>>>>>>>>> Peter
>>>>>>>>>>>
_______________________________________________
>>>>>>>>>>> cfe-dev mailing list
>>>>>>>>>>> cfe-dev at lists.llvm.org
>>>>>>>>>>>
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> --
>>>>>>>>> --
>>>>>>>>> Peter
>>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> --
>>>>>>> Peter
>>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> --
>>>>> Peter
>>>>>
>>>>
>>>
>>>
>>> --
>>> --
>>> Peter
>>>
>>> _______________________________________________
>>> cfe-dev mailing list
>>> cfe-dev at lists.llvm.org
>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>>>
>>>
>>

-- 
-- 
Peter
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170614/24bcf8aa/attachment.html>