michael@0: /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* vim:set ts=2 sw=2 sts=2 et cindent: */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include <stdio.h>
michael@0: #include "pldhash.h"
michael@0: 
michael@0: // pldhash is very widely used and so any basic bugs in it are likely to be
michael@0: // exposed through normal usage.  Therefore, this test currently focusses on
michael@0: // extreme cases relating to maximum table capacity and potential overflows,
michael@0: // which are unlikely to be hit during normal execution.
michael@0: 
michael@0: namespace TestPLDHash {
michael@0: 
michael@0: static bool test_pldhash_Init_capacity_ok()
michael@0: {
michael@0:   // Try the largest allowed capacity.  With PL_DHASH_MAX_SIZE==1<<26, this
michael@0:   // will allocate 0.5GB of entry store on 32-bit platforms and 1GB on 64-bit
michael@0:   // platforms.
michael@0:   PLDHashTable t;
michael@0:   bool ok = PL_DHashTableInit(&t, PL_DHashGetStubOps(), nullptr,
michael@0:                               sizeof(PLDHashEntryStub), PL_DHASH_MAX_SIZE,
michael@0:                               mozilla::fallible_t());
michael@0:   if (ok)
michael@0:     PL_DHashTableFinish(&t);
michael@0: 
michael@0:   return ok;
michael@0: }
michael@0: 
michael@0: static bool test_pldhash_Init_capacity_too_large()
michael@0: {
michael@0:   // Try the smallest too-large capacity.
michael@0:   PLDHashTable t;
michael@0:   bool ok = PL_DHashTableInit(&t, PL_DHashGetStubOps(), nullptr,
michael@0:                               sizeof(PLDHashEntryStub), PL_DHASH_MAX_SIZE + 1,
michael@0:                               mozilla::fallible_t());
michael@0:   // Don't call PL_DHashTableDestroy(), it's not safe after Init failure.
michael@0: 
michael@0:   return !ok;   // expected to fail
michael@0: }
michael@0: 
michael@0: static bool test_pldhash_Init_overflow()
michael@0: {
michael@0:   // Try an acceptable capacity, but one whose byte size overflows uint32_t.
michael@0:   //
michael@0:   // Ideally we'd also try a large-but-ok capacity that almost but doesn't
michael@0:   // quite overflow, but that would result in allocating just under 4GB of
michael@0:   // entry storage.  That's very likely to fail on 32-bit platforms, so such a
michael@0:   // test wouldn't be reliable.
michael@0: 
michael@0:   struct OneKBEntry {
michael@0:       PLDHashEntryHdr hdr;
michael@0:       char buf[1024 - sizeof(PLDHashEntryHdr)];
michael@0:   };
michael@0: 
michael@0:   // |nullptr| for |ops| is ok because it's unused due to the failure.
michael@0:   PLDHashTable t;
michael@0:   bool ok = PL_DHashTableInit(&t, /* ops = */nullptr, nullptr,
michael@0:                               sizeof(OneKBEntry), PL_DHASH_MAX_SIZE,
michael@0:                               mozilla::fallible_t());
michael@0: 
michael@0:   return !ok;   // expected to fail
michael@0: }
michael@0: 
michael@0: // See bug 931062, we skip this test on Android due to OOM.
michael@0: #ifndef MOZ_WIDGET_ANDROID
michael@0: // We insert the integers 0.., so this is has function is (a) as simple as
michael@0: // possible, and (b) collision-free.  Both of which are good, because we want
michael@0: // this test to be as fast as possible.
michael@0: static PLDHashNumber
michael@0: hash(PLDHashTable *table, const void *key)
michael@0: {
michael@0:   return (PLDHashNumber)(size_t)key;
michael@0: }
michael@0: 
michael@0: static bool test_pldhash_grow_to_max_capacity()
michael@0: {
michael@0:   static const PLDHashTableOps ops = {
michael@0:     PL_DHashAllocTable,
michael@0:     PL_DHashFreeTable,
michael@0:     hash,
michael@0:     PL_DHashMatchEntryStub,
michael@0:     PL_DHashMoveEntryStub,
michael@0:     PL_DHashClearEntryStub,
michael@0:     PL_DHashFinalizeStub,
michael@0:     nullptr
michael@0:   };
michael@0: 
michael@0:   PLDHashTable t;
michael@0:   bool ok = PL_DHashTableInit(&t, &ops, nullptr, sizeof(PLDHashEntryStub), 256,
michael@0:                               mozilla::fallible_t());
michael@0:   if (!ok)
michael@0:     return false;
michael@0: 
michael@0:   // Keep inserting elements until failure occurs because the table is full.
michael@0:   size_t numInserted = 0;
michael@0:   while (true) {
michael@0:     if (!PL_DHashTableOperate(&t, (const void*)numInserted, PL_DHASH_ADD)) {
michael@0:       break;
michael@0:     }
michael@0:     numInserted++;
michael@0:   }
michael@0: 
michael@0:   // We stop when the element count is 96.875% of PL_DHASH_MAX_SIZE (see
michael@0:   // MaxLoadOnGrowthFailure()).
michael@0:   return numInserted == PL_DHASH_MAX_SIZE - (PL_DHASH_MAX_SIZE >> 5);
michael@0: }
michael@0: #endif
michael@0: 
michael@0: //----
michael@0: 
michael@0: typedef bool (*TestFunc)();
michael@0: #define DECL_TEST(name) { #name, name }
michael@0: 
michael@0: static const struct Test {
michael@0:   const char* name;
michael@0:   TestFunc    func;
michael@0: } tests[] = {
michael@0:   DECL_TEST(test_pldhash_Init_capacity_ok),
michael@0:   DECL_TEST(test_pldhash_Init_capacity_too_large),
michael@0:   DECL_TEST(test_pldhash_Init_overflow),
michael@0: // See bug 931062, we skip this test on Android due to OOM.
michael@0: #ifndef MOZ_WIDGET_ANDROID
michael@0:   DECL_TEST(test_pldhash_grow_to_max_capacity),
michael@0: #endif
michael@0:   { nullptr, nullptr }
michael@0: };
michael@0: 
michael@0: } // namespace TestPLDHash
michael@0: 
michael@0: using namespace TestPLDHash;
michael@0: 
michael@0: int main(int argc, char *argv[])
michael@0: {
michael@0:   bool success = true;
michael@0:   for (const Test* t = tests; t->name != nullptr; ++t) {
michael@0:     bool test_result = t->func();
michael@0:     printf("%25s : %s\n", t->name, test_result ? "SUCCESS" : "FAILURE");
michael@0:     if (!test_result)
michael@0:       success = false;
michael@0:   }
michael@0:   return success ? 0 : -1;
michael@0: }