Fix undefined behavior in __hash_table
authorEric Fiselier <eric@efcs.ca>
Sat, 23 Jul 2016 20:36:55 +0000 (20:36 +0000)
committerEric Fiselier <eric@efcs.ca>
Sat, 23 Jul 2016 20:36:55 +0000 (20:36 +0000)
commit40492ba417e6cb3da99e8a6aafb80cde0186a96d
tree038827693b801a9a5846533a40b79739a9571d2f
parentbc7c2d020dd455c0b2382b251bea914331800637
Fix undefined behavior in __hash_table

Summary:
This patch attempts to fix the undefined behavior in __hash_table by changing the node pointer types used throughout. The pointer types are changed for raw pointers in the current ABI and for fancy pointers in ABI V2 (since the fancy pointer types may not be ABI compatible).

The UB in `__hash_table` arises because tree downcasts the embedded end node and then deferences that pointer. Currently there are 2 node types in __hash_table:

* `__hash_node_base` which contains the `__next_` pointer.
* `__hash_node` which contains `__hash_` and `__value_`.

Currently the bucket list, iterators, and `__next_` pointers store pointers to `__hash_node` even though they all need to store `__hash_node_base` pointers.
This patch makes that change by introducing a `__next_pointer` typedef which is a pointer to `__hash_node` in the current ABI and `__hash_node_base` afterwards.

One notable change is to the type of `__bucket_list` which used to be defined as `unique_ptr<__node_pointer[], ...>` and is now `unique_ptr<__next_pointer[], ...>` meaning that we now allocate and deallocate different types using a different allocator. I'm going to give this part of the change more thought since it may introduce compatibility issues.

This change is similar to D20786.

Reviewers: mclow.lists, EricWF

Subscribers: cfe-commits

Differential Revision: https://reviews.llvm.org/D20787

llvm-svn: 276533
libcxx/include/__config
libcxx/include/__debug
libcxx/include/__hash_table
libcxx/test/libcxx/test/config.py
libcxx/test/ubsan_blacklist.txt [deleted file]