The Tor Browser / file comparison
comparison: xpcom/tests/TestPLDHash.cpp
xpcom/tests/TestPLDHash.cpp
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
equal
deleted
inserted
replaced
| -1:000000000000 | 0:cf904912eae7 |
|---|---|
| 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_SIZE==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), PL_DHASH_MAX_SIZE, | |
| 25 mozilla::fallible_t()); | |
| 26 if (ok) | |
| 27 PL_DHashTableFinish(&t); | |
| 28 | |
| 29 return ok; | |
| 30 } | |
| 31 | |
| 32 static bool test_pldhash_Init_capacity_too_large() | |
| 33 { | |
| 34 // Try the smallest too-large capacity. | |
| 35 PLDHashTable t; | |
| 36 bool ok = PL_DHashTableInit(&t, PL_DHashGetStubOps(), nullptr, | |
| 37 sizeof(PLDHashEntryStub), PL_DHASH_MAX_SIZE + 1, | |
| 38 mozilla::fallible_t()); | |
| 39 // Don't call PL_DHashTableDestroy(), it's not safe after Init failure. | |
| 40 | |
| 41 return !ok; // expected to fail | |
| 42 } | |
| 43 | |
| 44 static bool test_pldhash_Init_overflow() | |
| 45 { | |
| 46 // Try an acceptable capacity, but one whose byte size overflows uint32_t. | |
| 47 // | |
| 48 // Ideally we'd also try a large-but-ok capacity that almost but doesn't | |
| 49 // quite overflow, but that would result in allocating just under 4GB of | |
| 50 // entry storage. That's very likely to fail on 32-bit platforms, so such a | |
| 51 // test wouldn't be reliable. | |
| 52 | |
| 53 struct OneKBEntry { | |
| 54 PLDHashEntryHdr hdr; | |
| 55 char buf[1024 - sizeof(PLDHashEntryHdr)]; | |
| 56 }; | |
| 57 | |
| 58 // |nullptr| for |ops| is ok because it's unused due to the failure. | |
| 59 PLDHashTable t; | |
| 60 bool ok = PL_DHashTableInit(&t, /* ops = */nullptr, nullptr, | |
| 61 sizeof(OneKBEntry), PL_DHASH_MAX_SIZE, | |
| 62 mozilla::fallible_t()); | |
| 63 | |
| 64 return !ok; // expected to fail | |
| 65 } | |
| 66 | |
| 67 // See bug 931062, we skip this test on Android due to OOM. | |
| 68 #ifndef MOZ_WIDGET_ANDROID | |
| 69 // We insert the integers 0.., so this is has function is (a) as simple as | |
| 70 // possible, and (b) collision-free. Both of which are good, because we want | |
| 71 // this test to be as fast as possible. | |
| 72 static PLDHashNumber | |
| 73 hash(PLDHashTable *table, const void *key) | |
| 74 { | |
| 75 return (PLDHashNumber)(size_t)key; | |
| 76 } | |
| 77 | |
| 78 static bool test_pldhash_grow_to_max_capacity() | |
| 79 { | |
| 80 static const PLDHashTableOps ops = { | |
| 81 PL_DHashAllocTable, | |
| 82 PL_DHashFreeTable, | |
| 83 hash, | |
| 84 PL_DHashMatchEntryStub, | |
| 85 PL_DHashMoveEntryStub, | |
| 86 PL_DHashClearEntryStub, | |
| 87 PL_DHashFinalizeStub, | |
| 88 nullptr | |
| 89 }; | |
| 90 | |
| 91 PLDHashTable t; | |
| 92 bool ok = PL_DHashTableInit(&t, &ops, nullptr, sizeof(PLDHashEntryStub), 256, | |
| 93 mozilla::fallible_t()); | |
| 94 if (!ok) | |
| 95 return false; | |
| 96 | |
| 97 // Keep inserting elements until failure occurs because the table is full. | |
| 98 size_t numInserted = 0; | |
| 99 while (true) { | |
| 100 if (!PL_DHashTableOperate(&t, (const void*)numInserted, PL_DHASH_ADD)) { | |
| 101 break; | |
| 102 } | |
| 103 numInserted++; | |
| 104 } | |
| 105 | |
| 106 // We stop when the element count is 96.875% of PL_DHASH_MAX_SIZE (see | |
| 107 // MaxLoadOnGrowthFailure()). | |
| 108 return numInserted == PL_DHASH_MAX_SIZE - (PL_DHASH_MAX_SIZE >> 5); | |
| 109 } | |
| 110 #endif | |
| 111 | |
| 112 //---- | |
| 113 | |
| 114 typedef bool (*TestFunc)(); | |
| 115 #define DECL_TEST(name) { #name, name } | |
| 116 | |
| 117 static const struct Test { | |
| 118 const char* name; | |
| 119 TestFunc func; | |
| 120 } tests[] = { | |
| 121 DECL_TEST(test_pldhash_Init_capacity_ok), | |
| 122 DECL_TEST(test_pldhash_Init_capacity_too_large), | |
| 123 DECL_TEST(test_pldhash_Init_overflow), | |
| 124 // See bug 931062, we skip this test on Android due to OOM. | |
| 125 #ifndef MOZ_WIDGET_ANDROID | |
| 126 DECL_TEST(test_pldhash_grow_to_max_capacity), | |
| 127 #endif | |
| 128 { nullptr, nullptr } | |
| 129 }; | |
| 130 | |
| 131 } // namespace TestPLDHash | |
| 132 | |
| 133 using namespace TestPLDHash; | |
| 134 | |
| 135 int main(int argc, char *argv[]) | |
| 136 { | |
| 137 bool success = true; | |
| 138 for (const Test* t = tests; t->name != nullptr; ++t) { | |
| 139 bool test_result = t->func(); | |
| 140 printf("%25s : %s\n", t->name, test_result ? "SUCCESS" : "FAILURE"); | |
| 141 if (!test_result) | |
| 142 success = false; | |
| 143 } | |
| 144 return success ? 0 : -1; | |
| 145 } |
