Module Name: src
Committed By: martin
Date: Tue Aug 1 17:03:54 UTC 2023
Modified Files:
src/distrib/sets/lists/debug [netbsd-10]: mi
src/distrib/sets/lists/tests [netbsd-10]: mi
src/libexec/ld.elf_so [netbsd-10]: Makefile reloc.c rtld.c rtld.h
symbol.c
src/tests/libexec/ld.elf_so [netbsd-10]: Makefile
Added Files:
src/libexec/ld.elf_so [netbsd-10]: hash.c hash.h
src/tests/libexec/ld.elf_so [netbsd-10]: t_hash.c
Log Message:
Pull up following revision(s) (requested by riastradh in ticket #300):
libexec/ld.elf_so/rtld.h: revision 1.145
libexec/ld.elf_so/symbol.c: revision 1.74
libexec/ld.elf_so/rtld.h: revision 1.147
libexec/ld.elf_so/symbol.c: revision 1.75
libexec/ld.elf_so/symbol.c: revision 1.76
tests/libexec/ld.elf_so/t_hash.c: revision 1.1
libexec/ld.elf_so/Makefile: revision 1.145
libexec/ld.elf_so/Makefile: revision 1.146
libexec/ld.elf_so/Makefile: revision 1.147
libexec/ld.elf_so/reloc.c: revision 1.118
distrib/sets/lists/tests/mi: revision 1.1280
libexec/ld.elf_so/rtld.c: revision 1.215
tests/libexec/ld.elf_so/Makefile: revision 1.21
libexec/ld.elf_so/hash.c: revision 1.1
libexec/ld.elf_so/hash.h: revision 1.1
distrib/sets/lists/debug/mi: revision 1.409
The SysV ABI specifies that the symbol hash function should return only 32
bits of hash. Unfortunately due to an implementation bug and the fact that
the return type is unsigned long which is 64 bits in LP64, this can fail
in some cases: "\xff\x0f\x0f\x0f\x0f\x0f\x12". See:
"https://maskray.me/blog/2023-04-12-elf-hash-function
>From Ed Maste @ FreeBSD:
https://cgit.freebsd.org/src/commit/?id=29e3a06510823edbb91667d21f530d3ec778116d
Need to write Unit Tests for this.
Oops wrong mask.
ld.elf_so: Split SRCS onto multiple lines.
Makes updates easier.
No functional change intended.
ld.elf_so: Sort SRCS.
No functional change intended.
ld.elf_so: Split hash functions into a separate file.
This way we can test them in isolation.
No functional change intended.
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.394.2.1 -r1.394.2.2 src/distrib/sets/lists/debug/mi
cvs rdiff -u -r1.1238.2.1 -r1.1238.2.2 src/distrib/sets/lists/tests/mi
cvs rdiff -u -r1.144 -r1.144.2.1 src/libexec/ld.elf_so/Makefile
cvs rdiff -u -r0 -r1.1.2.2 src/libexec/ld.elf_so/hash.c \
src/libexec/ld.elf_so/hash.h
cvs rdiff -u -r1.117 -r1.117.2.1 src/libexec/ld.elf_so/reloc.c
cvs rdiff -u -r1.212.2.2 -r1.212.2.3 src/libexec/ld.elf_so/rtld.c
cvs rdiff -u -r1.144.2.1 -r1.144.2.2 src/libexec/ld.elf_so/rtld.h
cvs rdiff -u -r1.73 -r1.73.8.1 src/libexec/ld.elf_so/symbol.c
cvs rdiff -u -r1.12.4.1 -r1.12.4.2 src/tests/libexec/ld.elf_so/Makefile
cvs rdiff -u -r0 -r1.1.2.2 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.394.2.1 src/distrib/sets/lists/debug/mi:1.394.2.2
--- src/distrib/sets/lists/debug/mi:1.394.2.1 Tue Aug 1 16:34:57 2023
+++ src/distrib/sets/lists/debug/mi Tue Aug 1 17:03:54 2023
@@ -1,4 +1,4 @@
-# $NetBSD: mi,v 1.394.2.1 2023/08/01 16:34:57 martin Exp $
+# $NetBSD: mi,v 1.394.2.2 2023/08/01 17:03:54 martin 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
@@ -2401,8 +2401,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.1238.2.1 src/distrib/sets/lists/tests/mi:1.1238.2.2
--- src/distrib/sets/lists/tests/mi:1.1238.2.1 Tue Aug 1 16:34:56 2023
+++ src/distrib/sets/lists/tests/mi Tue Aug 1 17:03:53 2023
@@ -1,4 +1,4 @@
-# $NetBSD: mi,v 1.1238.2.1 2023/08/01 16:34:56 martin Exp $
+# $NetBSD: mi,v 1.1238.2.2 2023/08/01 17:03:53 martin Exp $
#
# Note: don't delete entries from here - mark them as "obsolete" instead.
#
@@ -4093,6 +4093,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/libexec/ld.elf_so/Makefile
diff -u src/libexec/ld.elf_so/Makefile:1.144 src/libexec/ld.elf_so/Makefile:1.144.2.1
--- src/libexec/ld.elf_so/Makefile:1.144 Sat Dec 4 08:45:56 2021
+++ src/libexec/ld.elf_so/Makefile Tue Aug 1 17:03:53 2023
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile,v 1.144 2021/12/04 08:45:56 skrll Exp $
+# $NetBSD: Makefile,v 1.144.2.1 2023/08/01 17:03:53 martin Exp $
#
# NOTE: when changing ld.so, ensure that ldd still compiles.
#
@@ -72,9 +72,23 @@ PROG= ld.elf_so
CLIBOBJ!= cd ${NETBSDSRCDIR}/lib/libc && ${PRINTOBJDIR}
-SRCS+= rtld.c reloc.c symbol.c xmalloc.c xprintf.c debug.c \
- map_object.c load.c search.c headers.c paths.c expand.c \
- tls.c symver.c diagassert.c compat.c
+SRCS+= compat.c
+SRCS+= debug.c
+SRCS+= diagassert.c
+SRCS+= expand.c
+SRCS+= hash.c
+SRCS+= headers.c
+SRCS+= load.c
+SRCS+= map_object.c
+SRCS+= paths.c
+SRCS+= reloc.c
+SRCS+= rtld.c
+SRCS+= search.c
+SRCS+= symbol.c
+SRCS+= symver.c
+SRCS+= tls.c
+SRCS+= xmalloc.c
+SRCS+= xprintf.c
.if ${USE_FORT} == "yes"
.PATH.c: ${NETBSDSRCDIR}/lib/libc/misc
Index: src/libexec/ld.elf_so/reloc.c
diff -u src/libexec/ld.elf_so/reloc.c:1.117 src/libexec/ld.elf_so/reloc.c:1.117.2.1
--- src/libexec/ld.elf_so/reloc.c:1.117 Sat Dec 4 08:53:34 2021
+++ src/libexec/ld.elf_so/reloc.c Tue Aug 1 17:03:53 2023
@@ -1,4 +1,4 @@
-/* $NetBSD: reloc.c,v 1.117 2021/12/04 08:53:34 skrll Exp $ */
+/* $NetBSD: reloc.c,v 1.117.2.1 2023/08/01 17:03:53 martin Exp $ */
/*
* Copyright 1996 John D. Polstra.
@@ -39,7 +39,7 @@
#include <sys/cdefs.h>
#ifndef lint
-__RCSID("$NetBSD: reloc.c,v 1.117 2021/12/04 08:53:34 skrll Exp $");
+__RCSID("$NetBSD: reloc.c,v 1.117.2.1 2023/08/01 17:03:53 martin Exp $");
#endif /* not lint */
#include <err.h>
@@ -56,6 +56,7 @@ __RCSID("$NetBSD: reloc.c,v 1.117 2021/1
#include <dirent.h>
#include "debug.h"
+#include "hash.h"
#include "rtld.h"
#ifndef RTLD_INHIBIT_COPY_RELOCS
Index: src/libexec/ld.elf_so/rtld.c
diff -u src/libexec/ld.elf_so/rtld.c:1.212.2.2 src/libexec/ld.elf_so/rtld.c:1.212.2.3
--- src/libexec/ld.elf_so/rtld.c:1.212.2.2 Tue Aug 1 16:34:56 2023
+++ src/libexec/ld.elf_so/rtld.c Tue Aug 1 17:03:53 2023
@@ -1,4 +1,4 @@
-/* $NetBSD: rtld.c,v 1.212.2.2 2023/08/01 16:34:56 martin Exp $ */
+/* $NetBSD: rtld.c,v 1.212.2.3 2023/08/01 17:03:53 martin Exp $ */
/*
* Copyright 1996 John D. Polstra.
@@ -40,7 +40,7 @@
#include <sys/cdefs.h>
#ifndef lint
-__RCSID("$NetBSD: rtld.c,v 1.212.2.2 2023/08/01 16:34:56 martin Exp $");
+__RCSID("$NetBSD: rtld.c,v 1.212.2.3 2023/08/01 17:03:53 martin Exp $");
#endif /* not lint */
#include <sys/param.h>
@@ -60,7 +60,9 @@ __RCSID("$NetBSD: rtld.c,v 1.212.2.2 202
#include <ctype.h>
#include <dlfcn.h>
+
#include "debug.h"
+#include "hash.h"
#include "rtld.h"
#if !defined(lint)
Index: src/libexec/ld.elf_so/rtld.h
diff -u src/libexec/ld.elf_so/rtld.h:1.144.2.1 src/libexec/ld.elf_so/rtld.h:1.144.2.2
--- src/libexec/ld.elf_so/rtld.h:1.144.2.1 Tue Aug 1 16:34:56 2023
+++ src/libexec/ld.elf_so/rtld.h Tue Aug 1 17:03:53 2023
@@ -1,4 +1,4 @@
-/* $NetBSD: rtld.h,v 1.144.2.1 2023/08/01 16:34:56 martin Exp $ */
+/* $NetBSD: rtld.h,v 1.144.2.2 2023/08/01 17:03:53 martin Exp $ */
/*
* Copyright 1996 John D. Polstra.
@@ -442,8 +442,6 @@ void _rtld_call_ifunc(Obj_Entry *, sigse
Obj_Entry *_rtld_load_library(const char *, const Obj_Entry *, int);
/* symbol.c */
-unsigned long _rtld_sysv_hash(const char *);
-unsigned long _rtld_gnu_hash(const char *);
const Elf_Sym *_rtld_symlook_obj(const char *, Elf_Hash *,
const Obj_Entry *, u_int, const Ver_Entry *);
const Elf_Sym *_rtld_find_symdef(unsigned long, const Obj_Entry *,
Index: src/libexec/ld.elf_so/symbol.c
diff -u src/libexec/ld.elf_so/symbol.c:1.73 src/libexec/ld.elf_so/symbol.c:1.73.8.1
--- src/libexec/ld.elf_so/symbol.c:1.73 Sat Feb 29 18:45:20 2020
+++ src/libexec/ld.elf_so/symbol.c Tue Aug 1 17:03:53 2023
@@ -1,4 +1,4 @@
-/* $NetBSD: symbol.c,v 1.73 2020/02/29 18:45:20 kamil Exp $ */
+/* $NetBSD: symbol.c,v 1.73.8.1 2023/08/01 17:03:53 martin Exp $ */
/*
* Copyright 1996 John D. Polstra.
@@ -40,7 +40,7 @@
#include <sys/cdefs.h>
#ifndef lint
-__RCSID("$NetBSD: symbol.c,v 1.73 2020/02/29 18:45:20 kamil Exp $");
+__RCSID("$NetBSD: symbol.c,v 1.73.8.1 2023/08/01 17:03:53 martin Exp $");
#endif /* not lint */
#include <err.h>
@@ -57,6 +57,7 @@ __RCSID("$NetBSD: symbol.c,v 1.73 2020/0
#include <dirent.h>
#include "debug.h"
+#include "hash.h"
#include "rtld.h"
/*
@@ -80,45 +81,6 @@ _rtld_donelist_check(DoneList *dlp, cons
return false;
}
-/*
- * Hash function for symbol table lookup. Don't even think about changing
- * this. It is specified by the System V ABI.
- */
-unsigned long
-_rtld_sysv_hash(const char *name)
-{
- const unsigned char *p = (const unsigned char *) name;
- unsigned long h = 0;
- unsigned long g;
- unsigned long c;
-
- for (; __predict_true((c = *p) != '\0'); p++) {
- h <<= 4;
- h += c;
- if ((g = h & 0xf0000000) != 0) {
- h ^= g;
- h ^= g >> 24;
- }
- }
- return (h);
-}
-
-/*
- * Hash function for symbol table lookup. Don't even think about changing
- * this. It is specified by the GNU toolchain ABI.
- */
-unsigned long
-_rtld_gnu_hash(const char *name)
-{
- const unsigned char *p = (const unsigned char *) name;
- uint_fast32_t h = 5381;
- unsigned char c;
-
- for (c = *p; c != '\0'; c = *++p)
- h = h * 33 + c;
- return (unsigned long)h;
-}
-
const Elf_Sym *
_rtld_symlook_list(const char *name, Elf_Hash *hash, const Objlist *objlist,
const Obj_Entry **defobj_out, u_int flags, const Ver_Entry *ventry,
Index: src/tests/libexec/ld.elf_so/Makefile
diff -u src/tests/libexec/ld.elf_so/Makefile:1.12.4.1 src/tests/libexec/ld.elf_so/Makefile:1.12.4.2
--- src/tests/libexec/ld.elf_so/Makefile:1.12.4.1 Tue Aug 1 16:34:58 2023
+++ src/tests/libexec/ld.elf_so/Makefile Tue Aug 1 17:03:53 2023
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile,v 1.12.4.1 2023/08/01 16:34:58 martin Exp $
+# $NetBSD: Makefile,v 1.12.4.2 2023/08/01 17:03:53 martin 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 += ${${ACTIVE_CC} == "gcc" :? -Wno-maybe-uninitialized :}
Added files:
Index: src/libexec/ld.elf_so/hash.c
diff -u /dev/null src/libexec/ld.elf_so/hash.c:1.1.2.2
--- /dev/null Tue Aug 1 17:03:54 2023
+++ src/libexec/ld.elf_so/hash.c Tue Aug 1 17:03:53 2023
@@ -0,0 +1,81 @@
+/* $NetBSD: hash.c,v 1.1.2.2 2023/08/01 17:03:53 martin Exp $ */
+
+/*
+ * Copyright 1996 John D. Polstra.
+ * Copyright 1996 Matt Thomas <[email protected]>
+ * Copyright 2002 Charles M. Hannum <[email protected]>
+ * 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.
+ * 3. All advertising materials mentioning features or use of this software
+ * must display the following acknowledgement:
+ * This product includes software developed by John Polstra.
+ * 4. The name of the author may not be used to endorse or promote products
+ * derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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.
+ */
+
+/*
+ * Dynamic linker for ELF.
+ *
+ * John Polstra <[email protected]>.
+ */
+
+#include <sys/cdefs.h>
+#ifndef lint
+__RCSID("$NetBSD: hash.c,v 1.1.2.2 2023/08/01 17:03:53 martin Exp $");
+#endif /* not lint */
+
+#include <stdint.h>
+
+#include "hash.h"
+
+/*
+ * SysV hash function for symbol table lookup. It is a slightly optimized
+ * version of the hash specified by the System V ABI.
+ */
+Elf32_Word
+_rtld_sysv_hash(const char *name)
+{
+ const unsigned char *p = (const unsigned char *) name;
+ Elf32_Word h = 0;
+
+ while (__predict_true(*p != '\0')) {
+ h = (h << 4) + *p++;
+ h ^= (h >> 24) & 0xf0;
+ }
+ return (h & 0x0fffffff);
+}
+
+/*
+ * Hash function for symbol table lookup. Don't even think about changing
+ * this. It is specified by the GNU toolchain ABI.
+ */
+Elf32_Word
+_rtld_gnu_hash(const char *name)
+{
+ const unsigned char *p = (const unsigned char *) name;
+ uint_fast32_t h = 5381;
+ unsigned char c;
+
+ for (c = *p; c != '\0'; c = *++p)
+ h = h * 33 + c;
+ return (h & 0xffffffff);
+}
Index: src/libexec/ld.elf_so/hash.h
diff -u /dev/null src/libexec/ld.elf_so/hash.h:1.1.2.2
--- /dev/null Tue Aug 1 17:03:54 2023
+++ src/libexec/ld.elf_so/hash.h Tue Aug 1 17:03:53 2023
@@ -0,0 +1,42 @@
+/* $NetBSD: hash.h,v 1.1.2.2 2023/08/01 17:03:53 martin Exp $ */
+
+/*
+ * Copyright 1996 John D. Polstra.
+ * Copyright 1996 Matt Thomas <[email protected]>
+ * 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.
+ * 3. All advertising materials mentioning features or use of this software
+ * must display the following acknowledgement:
+ * This product includes software developed by John Polstra.
+ * 4. The name of the author may not be used to endorse or promote products
+ * derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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.
+ */
+
+#ifndef RTLD_HASH_H
+#define RTLD_HASH_H
+
+#include <sys/exec_elf.h>
+
+Elf32_Word _rtld_sysv_hash(const char *);
+Elf32_Word _rtld_gnu_hash(const char *);
+
+#endif /* RTLD_HASH_H */
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.2.2
--- /dev/null Tue Aug 1 17:03:54 2023
+++ src/tests/libexec/ld.elf_so/t_hash.c Tue Aug 1 17:03:53 2023
@@ -0,0 +1,218 @@
+/* $NetBSD: t_hash.c,v 1.1.2.2 2023/08/01 17:03:53 martin 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();
+}
