1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/xpcom/tests/TestPLDHash.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,145 @@
1.4 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* vim:set ts=2 sw=2 sts=2 et cindent: */
1.6 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#include <stdio.h>
1.11 +#include "pldhash.h"
1.12 +
1.13 +// pldhash is very widely used and so any basic bugs in it are likely to be
1.14 +// exposed through normal usage. Therefore, this test currently focusses on
1.15 +// extreme cases relating to maximum table capacity and potential overflows,
1.16 +// which are unlikely to be hit during normal execution.
1.17 +
1.18 +namespace TestPLDHash {
1.19 +
1.20 +static bool test_pldhash_Init_capacity_ok()
1.21 +{
1.22 + // Try the largest allowed capacity. With PL_DHASH_MAX_SIZE==1<<26, this
1.23 + // will allocate 0.5GB of entry store on 32-bit platforms and 1GB on 64-bit
1.24 + // platforms.
1.25 + PLDHashTable t;
1.26 + bool ok = PL_DHashTableInit(&t, PL_DHashGetStubOps(), nullptr,
1.27 + sizeof(PLDHashEntryStub), PL_DHASH_MAX_SIZE,
1.28 + mozilla::fallible_t());
1.29 + if (ok)
1.30 + PL_DHashTableFinish(&t);
1.31 +
1.32 + return ok;
1.33 +}
1.34 +
1.35 +static bool test_pldhash_Init_capacity_too_large()
1.36 +{
1.37 + // Try the smallest too-large capacity.
1.38 + PLDHashTable t;
1.39 + bool ok = PL_DHashTableInit(&t, PL_DHashGetStubOps(), nullptr,
1.40 + sizeof(PLDHashEntryStub), PL_DHASH_MAX_SIZE + 1,
1.41 + mozilla::fallible_t());
1.42 + // Don't call PL_DHashTableDestroy(), it's not safe after Init failure.
1.43 +
1.44 + return !ok; // expected to fail
1.45 +}
1.46 +
1.47 +static bool test_pldhash_Init_overflow()
1.48 +{
1.49 + // Try an acceptable capacity, but one whose byte size overflows uint32_t.
1.50 + //
1.51 + // Ideally we'd also try a large-but-ok capacity that almost but doesn't
1.52 + // quite overflow, but that would result in allocating just under 4GB of
1.53 + // entry storage. That's very likely to fail on 32-bit platforms, so such a
1.54 + // test wouldn't be reliable.
1.55 +
1.56 + struct OneKBEntry {
1.57 + PLDHashEntryHdr hdr;
1.58 + char buf[1024 - sizeof(PLDHashEntryHdr)];
1.59 + };
1.60 +
1.61 + // |nullptr| for |ops| is ok because it's unused due to the failure.
1.62 + PLDHashTable t;
1.63 + bool ok = PL_DHashTableInit(&t, /* ops = */nullptr, nullptr,
1.64 + sizeof(OneKBEntry), PL_DHASH_MAX_SIZE,
1.65 + mozilla::fallible_t());
1.66 +
1.67 + return !ok; // expected to fail
1.68 +}
1.69 +
1.70 +// See bug 931062, we skip this test on Android due to OOM.
1.71 +#ifndef MOZ_WIDGET_ANDROID
1.72 +// We insert the integers 0.., so this is has function is (a) as simple as
1.73 +// possible, and (b) collision-free. Both of which are good, because we want
1.74 +// this test to be as fast as possible.
1.75 +static PLDHashNumber
1.76 +hash(PLDHashTable *table, const void *key)
1.77 +{
1.78 + return (PLDHashNumber)(size_t)key;
1.79 +}
1.80 +
1.81 +static bool test_pldhash_grow_to_max_capacity()
1.82 +{
1.83 + static const PLDHashTableOps ops = {
1.84 + PL_DHashAllocTable,
1.85 + PL_DHashFreeTable,
1.86 + hash,
1.87 + PL_DHashMatchEntryStub,
1.88 + PL_DHashMoveEntryStub,
1.89 + PL_DHashClearEntryStub,
1.90 + PL_DHashFinalizeStub,
1.91 + nullptr
1.92 + };
1.93 +
1.94 + PLDHashTable t;
1.95 + bool ok = PL_DHashTableInit(&t, &ops, nullptr, sizeof(PLDHashEntryStub), 256,
1.96 + mozilla::fallible_t());
1.97 + if (!ok)
1.98 + return false;
1.99 +
1.100 + // Keep inserting elements until failure occurs because the table is full.
1.101 + size_t numInserted = 0;
1.102 + while (true) {
1.103 + if (!PL_DHashTableOperate(&t, (const void*)numInserted, PL_DHASH_ADD)) {
1.104 + break;
1.105 + }
1.106 + numInserted++;
1.107 + }
1.108 +
1.109 + // We stop when the element count is 96.875% of PL_DHASH_MAX_SIZE (see
1.110 + // MaxLoadOnGrowthFailure()).
1.111 + return numInserted == PL_DHASH_MAX_SIZE - (PL_DHASH_MAX_SIZE >> 5);
1.112 +}
1.113 +#endif
1.114 +
1.115 +//----
1.116 +
1.117 +typedef bool (*TestFunc)();
1.118 +#define DECL_TEST(name) { #name, name }
1.119 +
1.120 +static const struct Test {
1.121 + const char* name;
1.122 + TestFunc func;
1.123 +} tests[] = {
1.124 + DECL_TEST(test_pldhash_Init_capacity_ok),
1.125 + DECL_TEST(test_pldhash_Init_capacity_too_large),
1.126 + DECL_TEST(test_pldhash_Init_overflow),
1.127 +// See bug 931062, we skip this test on Android due to OOM.
1.128 +#ifndef MOZ_WIDGET_ANDROID
1.129 + DECL_TEST(test_pldhash_grow_to_max_capacity),
1.130 +#endif
1.131 + { nullptr, nullptr }
1.132 +};
1.133 +
1.134 +} // namespace TestPLDHash
1.135 +
1.136 +using namespace TestPLDHash;
1.137 +
1.138 +int main(int argc, char *argv[])
1.139 +{
1.140 + bool success = true;
1.141 + for (const Test* t = tests; t->name != nullptr; ++t) {
1.142 + bool test_result = t->func();
1.143 + printf("%25s : %s\n", t->name, test_result ? "SUCCESS" : "FAILURE");
1.144 + if (!test_result)
1.145 + success = false;
1.146 + }
1.147 + return success ? 0 : -1;
1.148 +}
