Source code
Revision control
Copy as Markdown
Other Tools
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
#include "PLDHashTable.h"
#include "gtest/gtest.h"
#include "mozilla/gtest/MozHelpers.h"
// This test mostly focuses on edge cases. But more coverage of normal
// operations wouldn't be a bad thing.
#ifdef XP_UNIX
# include <unistd.h>
# include <sys/types.h>
# include <sys/wait.h>
#endif
// We can test that certain operations cause expected aborts by forking
// and then checking that the child aborted in the expected way (i.e. via
// MOZ_CRASH). We skip this for the following configurations.
// - On Windows, because it doesn't have fork().
// - On non-DEBUG builds, because the crashes cause the crash reporter to pop
// up when running this test locally, which is surprising and annoying.
// - On ASAN builds, because ASAN alters the way a MOZ_CRASHing process
// terminates, which makes it harder to test if the right thing has occurred.
static void TestCrashyOperation(const char* label, void (*aCrashyOperation)()) {
#if defined(XP_UNIX) && defined(DEBUG) && !defined(MOZ_ASAN)
// We're about to trigger a crash. When it happens don't pause to allow GDB
// to be attached.
SAVE_GDB_SLEEP_LOCAL();
int pid = fork();
ASSERT_NE(pid, -1);
if (pid == 0) {
// Disable the crashreporter -- writing a crash dump in the child will
// prevent the parent from writing a subsequent dump. Crashes here are
// expected, so we don't want their stacks to show up in the log anyway.
mozilla::gtest::DisableCrashReporter();
// Child: perform the crashy operation.
FILE* stderr_dup = fdopen(dup(fileno(stderr)), "w");
// We don't want MOZ_CRASH from the crashy operation to print out its
// error message and stack-trace, which would be confusing and irrelevant.
fclose(stderr);
aCrashyOperation();
fprintf(stderr_dup, "TestCrashyOperation %s: didn't crash?!\n", label);
ASSERT_TRUE(false); // shouldn't reach here
}
// Parent: check that child crashed as expected.
int status;
ASSERT_NE(waitpid(pid, &status, 0), -1);
// The path taken here depends on the platform and configuration.
ASSERT_TRUE(WIFEXITED(status) || WTERMSIG(status));
if (WIFEXITED(status)) {
// This occurs if the ah_crap_handler() is run, i.e. we caught the crash.
// It returns the number of the caught signal.
int signum = WEXITSTATUS(status);
if (signum != SIGSEGV && signum != SIGBUS) {
fprintf(stderr, "TestCrashyOperation %s: 'exited' failure: %d\n", label,
signum);
ASSERT_TRUE(false);
}
} else if (WIFSIGNALED(status)) {
// This one occurs if we didn't catch the crash. The exit code is the
// number of the terminating signal.
int signum = WTERMSIG(status);
if (signum != SIGSEGV && signum != SIGBUS) {
fprintf(stderr, "TestCrashyOperation %s: 'signaled' failure: %d\n", label,
signum);
ASSERT_TRUE(false);
}
}
RESTORE_GDB_SLEEP_LOCAL();
#endif
}
static void InitCapacityOk_InitialLengthTooBig() {
PLDHashTable t(PLDHashTable::StubOps(), sizeof(PLDHashEntryStub),
PLDHashTable::kMaxInitialLength + 1);
}
static void InitCapacityOk_InitialEntryStoreTooBig() {
// Try the smallest disallowed power-of-two entry store size, which is 2^32
// bytes (which overflows to 0). (Note that the 2^23 *length* gets converted
// to a 2^24 *capacity*.)
PLDHashTable t(PLDHashTable::StubOps(), (uint32_t)1 << 8, (uint32_t)1 << 23);
}
static void InitCapacityOk_EntrySizeTooBig() {
// Try the smallest disallowed entry size, which is 256 bytes.
PLDHashTable t(PLDHashTable::StubOps(), 256);
}
TEST(PLDHashTableTest, InitCapacityOk)
{
// Try the largest allowed capacity. With kMaxCapacity==1<<26, this
// would allocate (if we added an element) 0.5GB of entry store on 32-bit
// platforms and 1GB on 64-bit platforms.
PLDHashTable t1(PLDHashTable::StubOps(), sizeof(PLDHashEntryStub),
PLDHashTable::kMaxInitialLength);
// Try the largest allowed power-of-two entry store size, which is 2^31 bytes
// (Note that the 2^23 *length* gets converted to a 2^24 *capacity*.)
PLDHashTable t2(PLDHashTable::StubOps(), (uint32_t)1 << 7, (uint32_t)1 << 23);
// Try a too-large capacity (which aborts).
TestCrashyOperation("length too big", InitCapacityOk_InitialLengthTooBig);
// Try a large capacity combined with a large entry size that when multiplied
// overflow (causing abort).
TestCrashyOperation("entry store too big",
InitCapacityOk_InitialEntryStoreTooBig);
// Try the largest allowed entry size.
PLDHashTable t3(PLDHashTable::StubOps(), 255);
// Try an overly large entry size.
TestCrashyOperation("entry size too big", InitCapacityOk_EntrySizeTooBig);
// Ideally we'd also try a large-but-ok capacity that almost but doesn't
// quite overflow, but that would result in allocating slightly less than 4
// GiB of entry storage. That would be very likely to fail on 32-bit
// platforms, so such a test wouldn't be reliable.
}
TEST(PLDHashTableTest, LazyStorage)
{
PLDHashTable t(PLDHashTable::StubOps(), sizeof(PLDHashEntryStub));
// PLDHashTable allocates entry storage lazily. Check that all the non-add
// operations work appropriately when the table is empty and the storage
// hasn't yet been allocated.
ASSERT_EQ(t.Capacity(), 0u);
ASSERT_EQ(t.EntrySize(), sizeof(PLDHashEntryStub));
ASSERT_EQ(t.EntryCount(), 0u);
ASSERT_EQ(t.Generation(), 0u);
ASSERT_TRUE(!t.Search((const void*)1));
// No result to check here, but call it to make sure it doesn't crash.
t.Remove((const void*)2);
for (auto iter = t.Iter(); !iter.Done(); iter.Next()) {
ASSERT_TRUE(false); // shouldn't hit this on an empty table
}
ASSERT_EQ(t.ShallowSizeOfExcludingThis(moz_malloc_size_of), 0u);
}
// A trivial hash function is good enough here. It's also super-fast for the
// GrowToMaxCapacity test because we insert the integers 0.., which means it's
// collision-free.
static PLDHashNumber TrivialHash(const void* key) {
return (PLDHashNumber)(size_t)key;
}
static void TrivialInitEntry(PLDHashEntryHdr* aEntry, const void* aKey) {
auto entry = static_cast<PLDHashEntryStub*>(aEntry);
entry->key = aKey;
}
static const PLDHashTableOps trivialOps = {
TrivialHash, PLDHashTable::MatchEntryStub, PLDHashTable::MoveEntryStub,
PLDHashTable::ClearEntryStub, TrivialInitEntry};
TEST(PLDHashTableTest, MoveSemantics)
{
PLDHashTable t1(&trivialOps, sizeof(PLDHashEntryStub));
t1.Add((const void*)88);
PLDHashTable t2(&trivialOps, sizeof(PLDHashEntryStub));
t2.Add((const void*)99);
#if defined(__clang__)
# pragma clang diagnostic push
# pragma clang diagnostic ignored "-Wself-move"
#endif
t1 = std::move(t1); // self-move
#if defined(__clang__)
# pragma clang diagnostic pop
#endif
t1 = std::move(t2); // empty overwritten with empty
PLDHashTable t3(&trivialOps, sizeof(PLDHashEntryStub));
PLDHashTable t4(&trivialOps, sizeof(PLDHashEntryStub));
t3.Add((const void*)88);
t3 = std::move(t4); // non-empty overwritten with empty
PLDHashTable t5(&trivialOps, sizeof(PLDHashEntryStub));
PLDHashTable t6(&trivialOps, sizeof(PLDHashEntryStub));
t6.Add((const void*)88);
t5 = std::move(t6); // empty overwritten with non-empty
PLDHashTable t7(&trivialOps, sizeof(PLDHashEntryStub));
PLDHashTable t8(std::move(t7)); // new table constructed with uninited
PLDHashTable t9(&trivialOps, sizeof(PLDHashEntryStub));
t9.Add((const void*)88);
PLDHashTable t10(std::move(t9)); // new table constructed with inited
}
TEST(PLDHashTableTest, Clear)
{
PLDHashTable t1(&trivialOps, sizeof(PLDHashEntryStub));
t1.Clear();
ASSERT_EQ(t1.EntryCount(), 0u);
t1.ClearAndPrepareForLength(100);
ASSERT_EQ(t1.EntryCount(), 0u);
t1.Add((const void*)77);
t1.Add((const void*)88);
t1.Add((const void*)99);
ASSERT_EQ(t1.EntryCount(), 3u);
t1.Clear();
ASSERT_EQ(t1.EntryCount(), 0u);
t1.Add((const void*)55);
t1.Add((const void*)66);
t1.Add((const void*)77);
t1.Add((const void*)88);
t1.Add((const void*)99);
ASSERT_EQ(t1.EntryCount(), 5u);
t1.ClearAndPrepareForLength(8192);
ASSERT_EQ(t1.EntryCount(), 0u);
}
TEST(PLDHashTableTest, Iterator)
{
PLDHashTable t(&trivialOps, sizeof(PLDHashEntryStub));
// Explicitly test the move constructor. We do this because, due to copy
// elision, compilers might optimize away move constructor calls for normal
// iterator use.
{
PLDHashTable::Iterator iter1(&t);
PLDHashTable::Iterator iter2(std::move(iter1));
}
// Iterate through the empty table.
for (PLDHashTable::Iterator iter(&t); !iter.Done(); iter.Next()) {
(void)iter.Get();
ASSERT_TRUE(false); // shouldn't hit this
}
// Add three entries.
t.Add((const void*)77);
t.Add((const void*)88);
t.Add((const void*)99);
// Check the iterator goes through each entry once.
bool saw77 = false, saw88 = false, saw99 = false;
int n = 0;
for (auto iter(t.Iter()); !iter.Done(); iter.Next()) {
auto entry = static_cast<PLDHashEntryStub*>(iter.Get());
if (entry->key == (const void*)77) {
saw77 = true;
}
if (entry->key == (const void*)88) {
saw88 = true;
}
if (entry->key == (const void*)99) {
saw99 = true;
}
n++;
}
ASSERT_TRUE(saw77 && saw88 && saw99 && n == 3);
t.Clear();
// First, we insert 64 items, which results in a capacity of 128, and a load
// factor of 50%.
for (intptr_t i = 0; i < 64; i++) {
t.Add((const void*)i);
}
ASSERT_EQ(t.EntryCount(), 64u);
ASSERT_EQ(t.Capacity(), 128u);
// The first removing iterator does no removing; capacity and entry count are
// unchanged.
for (PLDHashTable::Iterator iter(&t); !iter.Done(); iter.Next()) {
(void)iter.Get();
}
ASSERT_EQ(t.EntryCount(), 64u);
ASSERT_EQ(t.Capacity(), 128u);
// The second removing iterator removes 16 items. This reduces the load
// factor to 37.5% (48 / 128), which isn't low enough to shrink the table.
for (auto iter = t.Iter(); !iter.Done(); iter.Next()) {
auto entry = static_cast<PLDHashEntryStub*>(iter.Get());
if ((intptr_t)(entry->key) % 4 == 0) {
iter.Remove();
}
}
ASSERT_EQ(t.EntryCount(), 48u);
ASSERT_EQ(t.Capacity(), 128u);
// The third removing iterator removes another 16 items. This reduces
// the load factor to 25% (32 / 128), so the table is shrunk.
for (auto iter = t.Iter(); !iter.Done(); iter.Next()) {
auto entry = static_cast<PLDHashEntryStub*>(iter.Get());
if ((intptr_t)(entry->key) % 2 == 0) {
iter.Remove();
}
}
ASSERT_EQ(t.EntryCount(), 32u);
ASSERT_EQ(t.Capacity(), 64u);
// The fourth removing iterator removes all remaining items. This reduces
// the capacity to the minimum.
for (auto iter = t.Iter(); !iter.Done(); iter.Next()) {
iter.Remove();
}
ASSERT_EQ(t.EntryCount(), 0u);
ASSERT_EQ(t.Capacity(), unsigned(PLDHashTable::kMinCapacity));
}
TEST(PLDHashTableTest, WithEntryHandle)
{
PLDHashTable t(&trivialOps, sizeof(PLDHashEntryStub));
PLDHashEntryHdr* entry1 =
t.WithEntryHandle((const void*)88, [](auto entryHandle) {
EXPECT_FALSE(entryHandle);
bool initEntryCalled = false;
PLDHashEntryHdr* entry =
entryHandle.OrInsert([&initEntryCalled](PLDHashEntryHdr* entry) {
EXPECT_TRUE(entry);
TrivialInitEntry(entry, (const void*)88);
initEntryCalled = true;
});
EXPECT_TRUE(initEntryCalled);
EXPECT_EQ(entryHandle.Entry(), entry);
return entry;
});
ASSERT_TRUE(entry1);
ASSERT_EQ(t.EntryCount(), 1u);
PLDHashEntryHdr* entry2 =
t.WithEntryHandle((const void*)88, [](auto entryHandle) {
EXPECT_TRUE(entryHandle);
bool initEntryCalled = false;
PLDHashEntryHdr* entry =
entryHandle.OrInsert([&initEntryCalled](PLDHashEntryHdr* entry) {
EXPECT_TRUE(entry);
TrivialInitEntry(entry, (const void*)88);
initEntryCalled = true;
});
EXPECT_FALSE(initEntryCalled);
EXPECT_EQ(entryHandle.Entry(), entry);
return entry;
});
ASSERT_TRUE(entry2);
ASSERT_EQ(t.EntryCount(), 1u);
ASSERT_EQ(entry1, entry2);
}
// This test involves resizing a table repeatedly up to 512 MiB in size. On
// 32-bit platforms (Win32, Android) it sometimes OOMs, causing the test to
// platforms where OOM is much less likely.
//
// Also, it's slow, and so should always be last.
#ifdef HAVE_64BIT_BUILD
TEST(PLDHashTableTest, GrowToMaxCapacity)
{
// This is infallible.
PLDHashTable* t =
new PLDHashTable(&trivialOps, sizeof(PLDHashEntryStub), 128);
// Keep inserting elements until failure occurs because the table is full.
size_t numInserted = 0;
while (true) {
if (!t->Add((const void*)numInserted, mozilla::fallible)) {
break;
}
numInserted++;
}
// We stop when the element count is 96.875% of PLDHashTable::kMaxCapacity
// (see MaxLoadOnGrowthFailure()).
if (numInserted !=
PLDHashTable::kMaxCapacity - (PLDHashTable::kMaxCapacity >> 5)) {
delete t;
ASSERT_TRUE(false);
}
delete t;
}
#endif