This is an archive of the discontinued LLVM Phabricator instance.

[libc] Implement `hsearch` related facilities.
Needs ReviewPublic

Authored by SchrodingerZhu on Oct 18 2022, 10:35 PM.

Details

Summary

This patch add hsearch(_r), hdestroy(_r), hcreate(_r) to libc. In the same time, ACTION, ENTRY and struct hsearch_data
are introduced via the newly added header search.h.

The hashtable backend is swisstable. In short, this table is an open-addressing table but it looks up multiple 2nd-level hash in a
large machine word per probe. This enables faster lookup speed, especially for those platforms with SIMD registers. This implementation
is a combined effort of abseil's version and hashbrown's version. The structure mainly follows the latter one while the recent optimization
for aarch64 from abseil is adopt.

The 2nd-level hash is generated from the highest 7-bit of the hashword, thus the hash function is expected to encode the information using the
whole word and it should have a good avalanche effect. To fulfill the condition, a rewrite of wyhash in c++ is introduced.

By now, the random seed of the hashtable is only utilizes limited random source. This is because using system entropy pool can introduce other errors and
getrandom is not portable while hsearch is within the POSIX standard.

MUSL and Glibc seems to disagree with the ERRNO setting behavior. POSIX.1-2001 only states possible error for non-reentrant version. This implementation currently choose to follow the glibc's behavior.

The swisstable header contains more features than required ones. One reason is that the table can be used for future extension. The other is that glibc and musl
also disagrees on whether the table can be resized. The swisstable is designed to provide template parameters to control whether DELETE or RESIZE are supported, and using constexpr branches to optimize the situtations when some features are disabled.

Diff Detail

Event Timeline

Herald added projects: Restricted Project, Restricted Project. · View Herald TranscriptOct 18 2022, 10:35 PM
SchrodingerZhu requested review of this revision.Oct 18 2022, 10:35 PM

Add some questions in my own review.

libc/src/__support/swisstable.h
113

__builtin_mul_overflow seems to be generally available among LLVM and GNU toolchains but not MSVC's. I am not sure current support plan. Is it better to provide a wrapper?

422

There seems to be no wrapper of __builtin_memcpy_inline so I use inline_memcpy instead. will this be a stable interface?

libc/test/src/__support/swisstable/group_test.cpp
1

This line was wrongly added

Hi,
Thanks for the patch. Some of us are busy with others things for the next few weeks so the review is going to be slow. To make turn-around times faster, split this patch into multiple small patches with clear explanation of how they all fit in to the larger scheme of things.
Thanks,
Siva Chandra

@sivachandra Hi, I have splitted this mono patch into a series of smaller patches and submitted to the system.