From 0744eff6393f443004cd7031f4c61147fd5304db Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Mon, 18 May 2009 17:02:58 -0700 Subject: [PATCH] hash: Add unit test. --- tests/.gitignore | 1 + tests/automake.mk | 5 ++ tests/test-hash.c | 134 ++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 140 insertions(+) create mode 100644 tests/test-hash.c diff --git a/tests/.gitignore b/tests/.gitignore index 8ae4c738..11125035 100644 --- a/tests/.gitignore +++ b/tests/.gitignore @@ -3,6 +3,7 @@ /test-classifier /test-dhcp-client /test-flows +/test-hash /test-hmap /test-list /test-stp diff --git a/tests/automake.mk b/tests/automake.mk index dd208fc5..0508144f 100644 --- a/tests/automake.mk +++ b/tests/automake.mk @@ -9,6 +9,11 @@ tests_test_flows_SOURCES = tests/test-flows.c tests_test_flows_LDADD = lib/libopenvswitch.a dist_check_SCRIPTS = tests/test-flows.sh tests/flowgen.pl +TESTS += tests/test-hash +noinst_PROGRAMS += tests/test-hash +tests_test_hash_SOURCES = tests/test-hash.c +tests_test_hash_LDADD = lib/libopenvswitch.a + TESTS += tests/test-hmap noinst_PROGRAMS += tests/test-hmap tests_test_hmap_SOURCES = tests/test-hmap.c diff --git a/tests/test-hash.c b/tests/test-hash.c new file mode 100644 index 00000000..610fad41 --- /dev/null +++ b/tests/test-hash.c @@ -0,0 +1,134 @@ +/* Copyright (c) 2009 The Board of Trustees of The Leland Stanford Junior + * University + * + * We are making the OpenFlow specification and associated documentation + * (Software) available for public use and benefit with the expectation + * that others will use, modify and enhance the Software and contribute + * those enhancements back to the community. However, since we would + * like to make the Software available for broadest use, with as few + * restrictions as possible permission is hereby granted, free of + * charge, to any person obtaining a copy of this Software to deal in + * the Software under the copyrights without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + * + * The name and trademarks of copyright holder(s) may NOT be used in + * advertising or publicity pertaining to the Software or any + * derivatives without specific, written prior permission. + */ + +#include +#include +#include +#include +#include +#include "hash.h" + +#undef NDEBUG +#include + +static void +set_bit(uint32_t array[3], int bit) +{ + assert(bit >= 0 && bit <= 96); + memset(array, 0, sizeof(uint32_t) * 3); + if (bit < 96) { + array[bit / 32] = UINT32_C(1) << (bit % 32); + } +} + +int +main(void) +{ + int i, j; + + /* Check that all hash functions of with one 1-bit (or no 1-bits) set + * within a single 32-bit word have different values in all 11-bit + * consecutive runs. + * + * Given a random distribution, the probability of at least one collision + * in any set of 11 bits is approximately + * + * 1 - ((2**11 - 1)/2**11)**C(33,2) + * == 1 - (2047/2048)**528 + * =~ 0.22 + * + * There are 21 ways to pick 11 consecutive bits in a 32-bit word, so + * if we assumed independence then the chance of having no collisions in + * any of those 11-bit runs would be 0.22**21 =~ 1.5e-14. Obviously + * independence must be a bad assumption :-) + */ + for (i = 0; i <= 32; i++) { + uint32_t in1 = i < 32 ? UINT32_C(1) << i : 0; + for (j = i + 1; j <= 32; j++) { + uint32_t in2 = j < 32 ? UINT32_C(1) << j : 0; + uint32_t out1 = hash_words(&in1, 1, 0); + uint32_t out2 = hash_words(&in2, 1, 0); + const int min_unique = 11; + const uint32_t unique_mask = (UINT32_C(1) << min_unique) - 1; + int ofs; + for (ofs = 0; ofs < 32 - min_unique; ofs++) { + uint32_t bits1 = (out1 >> ofs) & unique_mask; + uint32_t bits2 = (out2 >> ofs) & unique_mask; + if (bits1 == bits2) { + printf("Partial collision:\n"); + printf("hash(%08"PRIx32") == %08"PRIx32"\n", in1, out1); + printf("hash(%08"PRIx32") == %08"PRIx32"\n", in2, out2); + printf("%d bits of output starting at bit %d " + "are both 0x%"PRIx32"\n", min_unique, ofs, bits1); + exit(1); + } + } + } + } + + /* Check that all hash functions of with one 1-bit (or no 1-bits) set + * within three 32-bit words have different values in their lowest 12 + * bits. + * + * Given a random distribution, the probability of at least one collision + * in 12 bits is approximately + * + * 1 - ((2**12 - 1)/2**12)**C(97,2) + * == 1 - (4095/4096)**4656 + * =~ 0.68 + * + * so we are doing pretty well to not have any collisions in 12 bits. + */ + for (i = 0; i <= 96; i++) { + for (j = i + 1; j <= 96; j++) { + uint32_t in1[3], in2[3]; + uint32_t out1, out2; + const int min_unique = 12; + const uint32_t unique_mask = (UINT32_C(1) << min_unique) - 1; + + set_bit(in1, i); + set_bit(in2, j); + out1 = hash_words(in1, 3, 0); + out2 = hash_words(in2, 3, 0); + if ((out1 & unique_mask) == (out2 & unique_mask)) { + printf("Partial collision:\n"); + printf("hash(1 << %d) == %08"PRIx32"\n", i, out1); + printf("hash(1 << %d) == %08"PRIx32"\n", j, out2); + printf("The low-order %d bits of output are both " + "0x%"PRIx32"\n", min_unique, out1 & unique_mask); + exit(1); + } + } + } + return 0; +} -- 2.30.2