xpcom/tests/TestPLDHash.cpp

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim:set ts=2 sw=2 sts=2 et cindent: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include <stdio.h>
   8 #include "pldhash.h"
   9
  10 // pldhash is very widely used and so any basic bugs in it are likely to be
  11 // exposed through normal usage.  Therefore, this test currently focusses on
  12 // extreme cases relating to maximum table capacity and potential overflows,
  13 // which are unlikely to be hit during normal execution.
  14
  15 namespace TestPLDHash {
  16
  17 static bool test_pldhash_Init_capacity_ok()
  18 {
  19   // Try the largest allowed capacity.  With PL_DHASH_MAX_CAPACITY==1<<26, this
  20   // will allocate 0.5GB of entry store on 32-bit platforms and 1GB on 64-bit
  21   // platforms.
  22   PLDHashTable t;
  23   bool ok = PL_DHashTableInit(&t, PL_DHashGetStubOps(), nullptr,
  24                               sizeof(PLDHashEntryStub),
  25                               mozilla::fallible_t(),
  26                               PL_DHASH_MAX_INITIAL_LENGTH);
  27   if (ok)
  28     PL_DHashTableFinish(&t);
  29
  30   return ok;
  31 }
  32
  33 static bool test_pldhash_Init_capacity_too_large()
  34 {
  35   // Try the smallest too-large capacity.
  36   PLDHashTable t;
  37   bool ok = PL_DHashTableInit(&t, PL_DHashGetStubOps(), nullptr,
  38                               sizeof(PLDHashEntryStub),
  39                               mozilla::fallible_t(),
  40                               PL_DHASH_MAX_INITIAL_LENGTH + 1);
  41   // Don't call PL_DHashTableDestroy(), it's not safe after Init failure.
  42
  43   return !ok;   // expected to fail
  44 }
  45
  46 static bool test_pldhash_Init_overflow()
  47 {
  48   // Try an acceptable capacity, but one whose byte size overflows uint32_t.
  49   //
  50   // Ideally we'd also try a large-but-ok capacity that almost but doesn't
  51   // quite overflow, but that would result in allocating just under 4GB of
  52   // entry storage.  That's very likely to fail on 32-bit platforms, so such a
  53   // test wouldn't be reliable.
  54
  55   struct OneKBEntry {
  56       PLDHashEntryHdr hdr;
  57       char buf[1024 - sizeof(PLDHashEntryHdr)];
  58   };
  59
  60   // |nullptr| for |ops| is ok because it's unused due to the failure.
  61   PLDHashTable t;
  62   bool ok = PL_DHashTableInit(&t, /* ops = */nullptr, nullptr,
  63                               sizeof(OneKBEntry), mozilla::fallible_t(),
  64                               PL_DHASH_MAX_INITIAL_LENGTH);
  65
  66   return !ok;   // expected to fail
  67 }
  68
  69 // See bug 931062, we skip this test on Android due to OOM.
  70 #ifndef MOZ_WIDGET_ANDROID
  71 // We insert the integers 0.., so this is has function is (a) as simple as
  72 // possible, and (b) collision-free.  Both of which are good, because we want
  73 // this test to be as fast as possible.
  74 static PLDHashNumber
  75 hash(PLDHashTable *table, const void *key)
  76 {
  77   return (PLDHashNumber)(size_t)key;
  78 }
  79
  80 static bool test_pldhash_grow_to_max_capacity()
  81 {
  82   static const PLDHashTableOps ops = {
  83     PL_DHashAllocTable,
  84     PL_DHashFreeTable,
  85     hash,
  86     PL_DHashMatchEntryStub,
  87     PL_DHashMoveEntryStub,
  88     PL_DHashClearEntryStub,
  89     PL_DHashFinalizeStub,
  90     nullptr
  91   };
  92
  93   PLDHashTable t;
  94   bool ok = PL_DHashTableInit(&t, &ops, nullptr, sizeof(PLDHashEntryStub),
  95                               mozilla::fallible_t(), 128);
  96   if (!ok)
  97     return false;
  98
  99   // Keep inserting elements until failure occurs because the table is full.
 100   size_t numInserted = 0;
 101   while (true) {
 102     if (!PL_DHashTableAdd(&t, (const void*)numInserted)) {
 103       break;
 104     }
 105     numInserted++;
 106   }
 107
 108   // We stop when the element count is 96.875% of PL_DHASH_MAX_SIZE (see
 109   // MaxLoadOnGrowthFailure()).
 110   return numInserted == PL_DHASH_MAX_CAPACITY - (PL_DHASH_MAX_CAPACITY >> 5);
 111 }
 112 #endif
 113
 114 //----
 115
 116 typedef bool (*TestFunc)();
 117 #define DECL_TEST(name) { #name, name }
 118
 119 static const struct Test {
 120   const char* name;
 121   TestFunc    func;
 122 } tests[] = {
 123   DECL_TEST(test_pldhash_Init_capacity_ok),
 124   DECL_TEST(test_pldhash_Init_capacity_too_large),
 125   DECL_TEST(test_pldhash_Init_overflow),
 126 // See bug 931062, we skip this test on Android due to OOM.
 127 #ifndef MOZ_WIDGET_ANDROID
 128   DECL_TEST(test_pldhash_grow_to_max_capacity),
 129 #endif
 130   { nullptr, nullptr }
 131 };
 132
 133 } // namespace TestPLDHash
 134
 135 using namespace TestPLDHash;
 136
 137 int main(int argc, char *argv[])
 138 {
 139   bool success = true;
 140   for (const Test* t = tests; t->name != nullptr; ++t) {
 141     bool test_result = t->func();
 142     printf("%25s : %s\n", t->name, test_result ? "SUCCESS" : "FAILURE");
 143     if (!test_result)
 144       success = false;
 145   }
 146   return success ? 0 : -1;
 147 }