opened
xelxebar
username_0
Prior to this commit, the following object files built
non-deterministically:

* xed-ild-disp-l3.o,
* xed-ild-eosz.o, and
* xed-ild.o.

This breaks the ability to build the library reproducibly. The primary
source of non-determinism comes from Python dictionaries placing no
guarantees on the order of items returned from `list(dict)`.

A simple workaround is to use `sorted(dict.keys())` or
`sorted(dict.items())` etc. as appropriate. However,
`sorted(dict.values())` fails to work in the general case since
dictionary values may not be orderable. For sorted `dict.items()` the
following idiom suffices:

    [value from (key,value) in sorted(dict.items())]

which this patch uses to replace instances of `list(dict.values())` in
several places.

Tracking down the particular offending object files was relatively
straightforward:

1) Build the library twice, using separate kit directories,
2) Use `objcopy -D` to sanitize obvious non-determinism from the
   archives, and finally
3) Use `cmp` to find the differing files.

This turned up `libxed.a` as the offender. Given this is an object
*archive*, we need to extract its object files and find the problematic
ones:

    $ ar x --output out/A kit-A/lib/libked.a
    $ ar x --output out/B kit-B/lib/libked.a

Running `cmp` over these object files turned up the mismatches mentioned
above. The output of `cmp` also gives the offset of the first
mismatching bytes, and consulting `readelf -S` shows these offsets to be in
the `.text` sections, which tells us that the problem is in the code
generation itself rather than simply some ELF metadata.

A quick and dirty comparison of the disassembled code (via `objdump -d`)
makes it obvious that the problem comes from differing *orders* of the
code blocks for each symbol, i.e. the code generators are simply
outputting functions in a different order between runs.
Remove sources of non-determinism in library builds
issue
created
jeffli678
username_1
Could someone please review this PR and merge it if appropriate? This is very helpful for my work. Thanks in advance!
comment
created
markcharney
username_2
I'll take a look. thx
comment
created
markcharney
username_2
seems reasonable. I was able  to merge  this  to my current version (thankfully!). testing now
comment