mbox

[0/2] Stable type ids

Message ID 20200612095917.2146-1-gprocida@google.com
Headers

Message

Giuliano Procida June 12, 2020, 9:59 a.m. UTC 
  Following up on
https://sourceware.org/pipermail/libabigail/2020q2/001973.html and
https://sourceware.org/pipermail/libabigail/2020q2/002308.html, this
patch series adds support for stable type ids in the form of a hash of
libabigail's internal type names.

The hash function used is 32-bit FNV-1a, resulting in 8 hex digit type
ids - shorter than the existing (default) counter-based ids. mjw's
suggestion could be accomodated as a third style.

Hash collisions are resolved by linear probing. Tests so far have only
found collisions caused by hashing identically-named distinct types.
If anonymous structs, unions and enums are given unique but stable
(internal) names, then the quality of this naming scheme will improve.

In general, it takes about 77k distinct names to reach a probability
of 0.5 of there being at least one collision.

https://en.wikipedia.org/wiki/Birthday_problem#Probability_table

FNV can accommodate other bit lengths.

http://www.isthe.com/chongo/tech/comp/fnv

Regards,
Giuliano.

Giuliano Procida (2):
  abg-writer: Add support for stable hash type ids.
  Add tests for abidw --type-id-style hash.

 doc/manuals/abidw.rst                         |  15 +-
 include/abg-writer.h                          |  10 ++
 src/abg-writer.cc                             |  95 ++++++++++++-
 tests/data/Makefile.am                        |   9 ++
 tests/data/test-read-dwarf/test0.hash.abi     |  70 ++++++++++
 tests/data/test-read-dwarf/test1.hash.abi     | 129 ++++++++++++++++++
 tests/data/test-read-dwarf/test2.so.hash.abi  |  79 +++++++++++
 tests/data/test-read-dwarf/test3.so.hash.abi  |  19 +++
 tests/data/test-read-dwarf/test4.so.hash.abi  |  23 ++++
 tests/data/test-read-dwarf/test5.o.hash.abi   |  13 ++
 tests/data/test-read-dwarf/test6.so.hash.abi  |  42 ++++++
 tests/data/test-read-dwarf/test7.so.hash.abi  |  77 +++++++++++
 .../test8-qualified-this-pointer.so.hash.abi  |  37 +++++
 tests/test-read-dwarf.cc                      | 107 ++++++++++++++-
 tools/abidw.cc                                |  20 ++-
 15 files changed, 728 insertions(+), 17 deletions(-)
 create mode 100644 tests/data/test-read-dwarf/test0.hash.abi
 create mode 100644 tests/data/test-read-dwarf/test1.hash.abi
 create mode 100644 tests/data/test-read-dwarf/test2.so.hash.abi
 create mode 100644 tests/data/test-read-dwarf/test3.so.hash.abi
 create mode 100644 tests/data/test-read-dwarf/test4.so.hash.abi
 create mode 100644 tests/data/test-read-dwarf/test5.o.hash.abi
 create mode 100644 tests/data/test-read-dwarf/test6.so.hash.abi
 create mode 100644 tests/data/test-read-dwarf/test7.so.hash.abi
 create mode 100644 tests/data/test-read-dwarf/test8-qualified-this-pointer.so.hash.abi