Module Name: src
Committed By: riastradh
Date: Sun Jul 30 09:22:02 UTC 2023
Modified Files:
src/distrib/sets/lists/debug: mi
src/distrib/sets/lists/tests: mi
src/tests/libexec/ld.elf_so: Makefile
Added Files:
src/tests/libexec/ld.elf_so: t_hash.c
Log Message:
ld.elf_so: Add some known-answer tests for hash functions.
Make sure the testing mechanism detects the traditional overflow bug.
To generate a diff of this commit:
cvs rdiff -u -r1.408 -r1.409 src/distrib/sets/lists/debug/mi
cvs rdiff -u -r1.1279 -r1.1280 src/distrib/sets/lists/tests/mi
cvs rdiff -u -r1.20 -r1.21 src/tests/libexec/ld.elf_so/Makefile
cvs rdiff -u -r0 -r1.1 src/tests/libexec/ld.elf_so/t_hash.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/distrib/sets/lists/debug/mi
diff -u src/distrib/sets/lists/debug/mi:1.408 src/distrib/sets/lists/debug/mi:1.409
--- src/distrib/sets/lists/debug/mi:1.408 Sat Jul 29 12:16:34 2023
+++ src/distrib/sets/lists/debug/mi Sun Jul 30 09:22:02 2023
@@ -1,4 +1,4 @@
-# $NetBSD: mi,v 1.408 2023/07/29 12:16:34 christos Exp $
+# $NetBSD: mi,v 1.409 2023/07/30 09:22:02 riastradh Exp $
./etc/mtree/set.debug comp-sys-root
./usr/lib comp-sys-usr compatdir
./usr/lib/i18n/libBIG5_g.a comp-c-debuglib debuglib,compatfile
@@ -2408,8 +2408,9 @@
./usr/libdata/debug/usr/tests/libexec/ld.elf_so/t_dlerror-false.debug tests-libexec-debug debug,atf,pic,compattestfile
./usr/libdata/debug/usr/tests/libexec/ld.elf_so/t_dlinfo.debug tests-libexec-debug debug,atf,pic,compattestfile
./usr/libdata/debug/usr/tests/libexec/ld.elf_so/t_dlvsym.debug tests-libexec-debug debug,atf,pic,compattestfile
-./usr/libdata/debug/usr/tests/libexec/ld.elf_so/t_rtld_r_debug.debug tests-libexec-debug debug,atf,pic,compattestfile
+./usr/libdata/debug/usr/tests/libexec/ld.elf_so/t_hash.debug tests-libexec-debug debug,atf,pic,compattestfile
./usr/libdata/debug/usr/tests/libexec/ld.elf_so/t_ifunc.debug tests-libexec-debug debug,atf,pic,compattestfile
+./usr/libdata/debug/usr/tests/libexec/ld.elf_so/t_rtld_r_debug.debug tests-libexec-debug debug,atf,pic,compattestfile
./usr/libdata/debug/usr/tests/libexec/ld.elf_so/t_tls_extern.debug tests-libexec-debug debug,atf,pic,compattestfile
./usr/libdata/debug/usr/tests/net/bpf/t_bpf.debug tests-net-debug debug,atf,rump
./usr/libdata/debug/usr/tests/net/bpf/t_div-by-zero.debug tests-net-debug debug,atf,rump
Index: src/distrib/sets/lists/tests/mi
diff -u src/distrib/sets/lists/tests/mi:1.1279 src/distrib/sets/lists/tests/mi:1.1280
--- src/distrib/sets/lists/tests/mi:1.1279 Sat Jul 29 12:16:34 2023
+++ src/distrib/sets/lists/tests/mi Sun Jul 30 09:22:02 2023
@@ -1,4 +1,4 @@
-# $NetBSD: mi,v 1.1279 2023/07/29 12:16:34 christos Exp $
+# $NetBSD: mi,v 1.1280 2023/07/30 09:22:02 riastradh Exp $
#
# Note: don't delete entries from here - mark them as "obsolete" instead.
#
@@ -4177,6 +4177,7 @@
./usr/tests/libexec/ld.elf_so/t_dlerror-false tests-libexec-tests compattestfile,atf,pic
./usr/tests/libexec/ld.elf_so/t_dlinfo tests-libexec-tests compattestfile,atf,pic
./usr/tests/libexec/ld.elf_so/t_dlvsym tests-libexec-tests compattestfile,atf,pic
+./usr/tests/libexec/ld.elf_so/t_hash tests-libexec-tests compattestfile,atf,pic
./usr/tests/libexec/ld.elf_so/t_ifunc tests-libexec-tests compattestfile,atf,pic
./usr/tests/libexec/ld.elf_so/t_rtld_r_debug tests-libexec-tests compattestfile,atf,pic
./usr/tests/libexec/ld.elf_so/t_thread_local_dtor tests-libexec-tests compattestfile,atf,pic
Index: src/tests/libexec/ld.elf_so/Makefile
diff -u src/tests/libexec/ld.elf_so/Makefile:1.20 src/tests/libexec/ld.elf_so/Makefile:1.21
--- src/tests/libexec/ld.elf_so/Makefile:1.20 Sat Jun 3 21:31:47 2023
+++ src/tests/libexec/ld.elf_so/Makefile Sun Jul 30 09:22:02 2023
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile,v 1.20 2023/06/03 21:31:47 lukem Exp $
+# $NetBSD: Makefile,v 1.21 2023/07/30 09:22:02 riastradh Exp $
#
NOMAN= # defined
@@ -30,6 +30,12 @@ TESTSDIR= ${TESTSBASE}/libexec/ld.elf_so
TESTS_C+= t_dlerror-cleared t_dlerror-false t_dlinfo t_dlvsym t_ifunc
TESTS_C+= t_rtld_r_debug
TESTS_C+= t_tls_extern
+TESTS_C+= t_hash
+
+.PATH: ${NETBSDSRCDIR}/libexec/ld.elf_so
+SRCS.t_hash+= t_hash.c
+SRCS.t_hash+= hash.c
+CPPFLAGS.t_hash.c+= -I${NETBSDSRCDIR}/libexec/ld.elf_so
COPTS.t_rtld_r_debug.c += ${CC_WNO_MAYBE_UNINITIALIZED}
Added files:
Index: src/tests/libexec/ld.elf_so/t_hash.c
diff -u /dev/null src/tests/libexec/ld.elf_so/t_hash.c:1.1
--- /dev/null Sun Jul 30 09:22:03 2023
+++ src/tests/libexec/ld.elf_so/t_hash.c Sun Jul 30 09:22:02 2023
@@ -0,0 +1,218 @@
+/* $NetBSD: t_hash.c,v 1.1 2023/07/30 09:22:02 riastradh Exp $ */
+
+/*-
+ * Copyright (c) 2023 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <sys/cdefs.h>
+
+#include <atf-c.h>
+#include <stdint.h>
+
+#include "hash.h"
+
+/* known-answer tests */
+struct kat {
+ const char *in;
+ unsigned long long out;
+};
+
+/*
+ * From the SysV spec, with uint64_t instead of unsigned long to
+ * illustrate the problem on all systems, not just LP64 ones.
+ *
+ * https://www.sco.com/developers/devspecs/gabi41.pdf#page=95
+ */
+static uint64_t
+sysv_broken_hash(const char *name)
+{
+ uint64_t h = 0, g;
+
+ while (*name) {
+ h = (h << 4) + *name++;
+ if ((g = h & 0xf0000000) != 0)
+ h ^= g >> 24;
+ h &= ~g;
+ }
+
+ return h;
+}
+
+ATF_TC(sysv);
+ATF_TC_HEAD(sysv, tc)
+{
+ atf_tc_set_md_var(tc, "descr", "SysV hash (32-bit)");
+}
+ATF_TC_BODY(sysv, tc)
+{
+ static const struct kat kat[] = {
+ { "", 0x00000000 },
+ { "a", 0x00000061 },
+ { "aa", 0x00000671 },
+ { "aaa", 0x00006771 },
+ { "aaaa", 0x00067771 },
+ { "aaaaa", 0x00677771 },
+ { "aaaaaa", 0x06777771 },
+ { "aaaaaaa", 0x07777711 },
+ { "aaaaaaaa", 0x07777101 },
+ { "aaaaaaaaa", 0x07771001 },
+ { "ab", 0x00000672 },
+ { "abc", 0x00006783 },
+ { "abcd", 0x00067894 },
+ { "abcde", 0x006789a5 },
+ { "abcdef", 0x06789ab6 },
+ { "abcdefg", 0x0789aba7 },
+ { "abcdefgh", 0x089abaa8 },
+ { "abcdefghi", 0x09abaa69 },
+ /* https://maskray.me/blog/2023-04-12-elf-hash-function */
+ { "Z", 0x0000005a },
+ { "ZZ", 0x000005fa },
+ { "ZZZ", 0x00005ffa },
+ { "ZZZZ", 0x0005fffa },
+ { "ZZZZZ", 0x005ffffa },
+ { "ZZZZZW", 0x05fffff7 },
+ { "ZZZZZW9", 0x0ffffff9 },
+ { "ZZZZZW9p", 0x00000000 },
+ { "pneumonoultramicroscopicsilicovolcanoconiosis",
+ 0x051706b3 },
+ };
+ unsigned i;
+
+ for (i = 0; i < __arraycount(kat); i++) {
+ unsigned long long h = _rtld_sysv_hash(kat[i].in);
+
+ ATF_CHECK_EQ_MSG(h, kat[i].out,
+ "[%u] _rtld_hash_sysv(\"%s\") = 0x%08llx != 0x%08llx",
+ i, kat[i].in, h, kat[i].out);
+ }
+}
+
+ATF_TC(sysv_broken);
+ATF_TC_HEAD(sysv_broken, tc)
+{
+ atf_tc_set_md_var(tc, "descr",
+ "SysV hash (broken with 64-bit unsigned long)");
+}
+ATF_TC_BODY(sysv_broken, tc)
+{
+ static const struct kat kat[] = {
+ { "", 0x00000000 },
+ { "a", 0x00000061 },
+ { "aa", 0x00000671 },
+ { "aaa", 0x00006771 },
+ { "aaaa", 0x00067771 },
+ { "aaaaa", 0x00677771 },
+ { "aaaaaa", 0x06777771 },
+ { "aaaaaaa", 0x07777711 },
+ { "aaaaaaaa", 0x07777101 },
+ { "aaaaaaaaa", 0x07771001 },
+ { "ab", 0x00000672 },
+ { "abc", 0x00006783 },
+ { "abcd", 0x00067894 },
+ { "abcde", 0x006789a5 },
+ { "abcdef", 0x06789ab6 },
+ { "abcdefg", 0x0789aba7 },
+ { "abcdefgh", 0x089abaa8 },
+ { "abcdefghi", 0x09abaa69 },
+ /* https://maskray.me/blog/2023-04-12-elf-hash-function */
+ { "Z", 0x0000005a },
+ { "ZZ", 0x000005fa },
+ { "ZZZ", 0x00005ffa },
+ { "ZZZZ", 0x0005fffa },
+ { "ZZZZZ", 0x005ffffa },
+ { "ZZZZZW", 0x05fffff7 },
+ { "ZZZZZW9", 0x0ffffff9 },
+ { "ZZZZZW9p", 0x100000000 },
+ { "pneumonoultramicroscopicsilicovolcanoconiosis",
+ 0x051706b3 },
+ };
+ unsigned i;
+
+ for (i = 0; i < __arraycount(kat); i++) {
+ unsigned long long h = sysv_broken_hash(kat[i].in);
+
+ ATF_CHECK_EQ_MSG(h, kat[i].out,
+ "[%u] sysv_broken_hash(\"%s\") = 0x%08llx != 0x%08llx",
+ i, kat[i].in, h, kat[i].out);
+ }
+}
+
+ATF_TC(gnu);
+ATF_TC_HEAD(gnu, tc)
+{
+ atf_tc_set_md_var(tc, "descr", "GNU hash (djb2)");
+}
+ATF_TC_BODY(gnu, tc)
+{
+ static const struct kat kat[] = {
+ { """", 0x00001505 },
+ { "a", 0x0002b606 },
+ { "aa", 0x00597727 },
+ { "aaa", 0x0b885c68 },
+ { "aaaa", 0x7c93e9c9 },
+ { "aaaaa", 0x0f11234a },
+ { "aaaaaa", 0xf1358ceb },
+ { "aaaaaaa", 0x17e72aac },
+ { "aaaaaaaa", 0x14cc808d },
+ { "aaaaaaaaa", 0xae5c928e },
+ { "ab", 0x00597728 },
+ { "abc", 0x0b885c8b },
+ { "abcd", 0x7c93ee4f },
+ { "abcde", 0x0f11b894 },
+ { "abcdef", 0xf148cb7a },
+ { "abcdefg", 0x1a623b21 },
+ { "abcdefgh", 0x66a99fa9 },
+ { "abcdefghi", 0x3bdd9532 },
+ { "Z", 0x0002b5ff },
+ { "ZZ", 0x00597639 },
+ { "ZZZ", 0x0b883db3 },
+ { "ZZZZ", 0x7c8ff46d },
+ { "ZZZZZ", 0x0e8e8267 },
+ { "ZZZZZW", 0xe05ecf9e },
+ { "ZZZZZW9", 0xec38c397 },
+ { "ZZZZZW9p", 0x735136e7 },
+ { "pneumonoultramicroscopicsilicovolcanoconiosis",
+ 0xee6245b5 },
+ };
+ unsigned i;
+
+ for (i = 0; i < __arraycount(kat); i++) {
+ unsigned long long h = _rtld_gnu_hash(kat[i].in);
+
+ ATF_CHECK_EQ_MSG(h, kat[i].out,
+ "[%u] _rtld_gnu_hash(\"%s\") = 0x%08llx != 0x%08llx",
+ i, kat[i].in, h, kat[i].out);
+ }
+}
+
+ATF_TP_ADD_TCS(tp)
+{
+
+ ATF_TP_ADD_TC(tp, gnu);
+ ATF_TP_ADD_TC(tp, sysv);
+ ATF_TP_ADD_TC(tp, sysv_broken);
+
+ return atf_no_error();
+}
