diff options
Diffstat (limited to 'lib/libc')
32 files changed, 1033 insertions, 383 deletions
diff --git a/lib/libc/Makefile b/lib/libc/Makefile index 2f8865c..e9f14f4 100644 --- a/lib/libc/Makefile +++ b/lib/libc/Makefile @@ -26,6 +26,7 @@ LIBC_ARCH=${MACHINE_CPUARCH} LIB=c SHLIB_MAJOR= 7 SHLIB_LDSCRIPT=libc.ldscript +SHLIB_LDSCRIPT_LINKS=libxnet.so WARNS?= 2 CFLAGS+=-I${LIBC_SRCTOP}/include -I${LIBC_SRCTOP}/../../include CFLAGS+=-I${LIBC_SRCTOP}/${LIBC_ARCH} diff --git a/lib/libc/arm/sys/__vdso_gettc.c b/lib/libc/arm/sys/__vdso_gettc.c index d75d866..1f43e72 100644 --- a/lib/libc/arm/sys/__vdso_gettc.c +++ b/lib/libc/arm/sys/__vdso_gettc.c @@ -34,8 +34,10 @@ __FBSDID("$FreeBSD$"); #include <sys/time.h> #include <sys/vdso.h> #include <machine/cpufunc.h> +#include <machine/acle-compat.h> #include "libc_private.h" +#if __ARM_ARCH >= 6 static inline uint64_t cp15_cntvct_get(void) { @@ -53,6 +55,7 @@ cp15_cntpct_get(void) __asm __volatile("mrrc\tp15, 0, %Q0, %R0, c14" : "=r" (reg)); return (reg); } +#endif #pragma weak __vdso_gettc u_int @@ -60,6 +63,7 @@ __vdso_gettc(const struct vdso_timehands *th) { uint64_t val; +#if __ARM_ARCH >= 6 /* * Userspace gettimeofday() is only enabled on ARMv7 CPUs, but * libc is compiled for ARMv6. Due to clang issues, .arch @@ -67,6 +71,9 @@ __vdso_gettc(const struct vdso_timehands *th) */ __asm __volatile(".word\t0xf57ff06f" : : : "memory"); /* isb */ val = th->th_physical == 0 ? cp15_cntvct_get() : cp15_cntpct_get(); +#else + val = 0; +#endif return (val); } diff --git a/lib/libc/gen/getpeereid.c b/lib/libc/gen/getpeereid.c index 5ecb243..cedaee6 100644 --- a/lib/libc/gen/getpeereid.c +++ b/lib/libc/gen/getpeereid.c @@ -27,6 +27,7 @@ #include <sys/cdefs.h> __FBSDID("$FreeBSD$"); +#include "namespace.h" #include <sys/param.h> #include <sys/socket.h> #include <sys/ucred.h> @@ -34,6 +35,7 @@ __FBSDID("$FreeBSD$"); #include <errno.h> #include <unistd.h> +#include "un-namespace.h" int getpeereid(int s, uid_t *euid, gid_t *egid) @@ -43,7 +45,7 @@ getpeereid(int s, uid_t *euid, gid_t *egid) int error; xuclen = sizeof(xuc); - error = getsockopt(s, 0, LOCAL_PEERCRED, &xuc, &xuclen); + error = _getsockopt(s, 0, LOCAL_PEERCRED, &xuc, &xuclen); if (error != 0) return (error); if (xuc.cr_version != XUCRED_VERSION) diff --git a/lib/libc/gen/lockf.c b/lib/libc/gen/lockf.c index 2c567ba..c64a347 100644 --- a/lib/libc/gen/lockf.c +++ b/lib/libc/gen/lockf.c @@ -36,6 +36,7 @@ __FBSDID("$FreeBSD$"); #include <fcntl.h> #include <unistd.h> #include "un-namespace.h" +#include "libc_private.h" int lockf(int filedes, int function, off_t size) @@ -62,9 +63,12 @@ lockf(int filedes, int function, off_t size) break; case F_TEST: fl.l_type = F_WRLCK; - if (_fcntl(filedes, F_GETLK, &fl) == -1) + if (((int (*)(int, int, ...)) + __libc_interposing[INTERPOS_fcntl])(filedes, F_GETLK, &fl) + == -1) return (-1); - if (fl.l_type == F_UNLCK || (fl.l_sysid == 0 && fl.l_pid == getpid())) + if (fl.l_type == F_UNLCK || (fl.l_sysid == 0 && + fl.l_pid == getpid())) return (0); errno = EAGAIN; return (-1); @@ -75,5 +79,6 @@ lockf(int filedes, int function, off_t size) /* NOTREACHED */ } - return (_fcntl(filedes, cmd, &fl)); + return (((int (*)(int, int, ...)) + __libc_interposing[INTERPOS_fcntl])(filedes, cmd, &fl)); } diff --git a/lib/libc/gen/nlist.c b/lib/libc/gen/nlist.c index e93f89b..80784dd 100644 --- a/lib/libc/gen/nlist.c +++ b/lib/libc/gen/nlist.c @@ -47,8 +47,8 @@ __FBSDID("$FreeBSD$"); #include <unistd.h> #include "un-namespace.h" -/* There is no a.out support on arm64 */ -#ifndef __aarch64__ +/* i386 is the only current FreeBSD architecture that used a.out format. */ +#ifdef __i386__ #define _NLIST_DO_AOUT #endif #define _NLIST_DO_ELF diff --git a/lib/libc/gen/sysconf.c b/lib/libc/gen/sysconf.c index be3d4af..71f2321 100644 --- a/lib/libc/gen/sysconf.c +++ b/lib/libc/gen/sysconf.c @@ -36,6 +36,7 @@ static char sccsid[] = "@(#)sysconf.c 8.2 (Berkeley) 3/20/94"; #include <sys/cdefs.h> __FBSDID("$FreeBSD$"); +#include "namespace.h" #include <sys/param.h> #include <sys/time.h> #include <sys/sysctl.h> @@ -49,6 +50,7 @@ __FBSDID("$FreeBSD$"); #include <pthread.h> /* we just need the limits */ #include <time.h> #include <unistd.h> +#include "un-namespace.h" #include "../stdlib/atexit.h" #include "tzfile.h" /* from ../../../contrib/tzcode/stdtime */ @@ -575,10 +577,10 @@ yesno: case _SC_IPV6: #if _POSIX_IPV6 == 0 sverrno = errno; - value = socket(PF_INET6, SOCK_DGRAM, 0); + value = _socket(PF_INET6, SOCK_DGRAM, 0); errno = sverrno; if (value >= 0) { - close(value); + _close(value); return (200112L); } else return (0); diff --git a/lib/libc/iconv/citrus_mmap.c b/lib/libc/iconv/citrus_mmap.c index f8e96d1..83dd70b 100644 --- a/lib/libc/iconv/citrus_mmap.c +++ b/lib/libc/iconv/citrus_mmap.c @@ -27,6 +27,7 @@ * SUCH DAMAGE. */ +#include "namespace.h" #include <sys/cdefs.h> #include <sys/mman.h> #include <sys/types.h> @@ -40,6 +41,7 @@ #include <stdlib.h> #include <string.h> #include <unistd.h> +#include "un-namespace.h" #include "citrus_namespace.h" #include "citrus_region.h" @@ -57,10 +59,10 @@ _citrus_map_file(struct _citrus_region * __restrict r, _region_init(r, NULL, 0); - if ((fd = open(path, O_RDONLY | O_CLOEXEC)) == -1) + if ((fd = _open(path, O_RDONLY | O_CLOEXEC)) == -1) return (errno); - if (fstat(fd, &st) == -1) { + if (_fstat(fd, &st) == -1) { ret = errno; goto error; } @@ -78,7 +80,7 @@ _citrus_map_file(struct _citrus_region * __restrict r, _region_init(r, head, (size_t)st.st_size); error: - (void)close(fd); + (void)_close(fd); return (ret); } diff --git a/lib/libc/net/getaddrinfo.3 b/lib/libc/net/getaddrinfo.3 index 69601e6..7380428 100644 --- a/lib/libc/net/getaddrinfo.3 +++ b/lib/libc/net/getaddrinfo.3 @@ -18,7 +18,7 @@ .\" .\" $FreeBSD$ .\" -.Dd December 19, 2015 +.Dd December 21, 2015 .Dt GETADDRINFO 3 .Os .Sh NAME @@ -79,7 +79,7 @@ as defined by .Bd -literal struct addrinfo { int ai_flags; /* input flags */ - int ai_family; /* protocol family for socket */ + int ai_family; /* address family for socket */ int ai_socktype; /* socket type */ int ai_protocol; /* protocol for socket */ socklen_t ai_addrlen; /* length of socket-address */ @@ -95,12 +95,12 @@ The caller can supply the following structure elements in .Fa hints : .Bl -tag -width "ai_socktypeXX" .It Fa ai_family -The protocol family that should be used. +The address family that should be used. When .Fa ai_family is set to -.Dv PF_UNSPEC , -it means the caller will accept any protocol family supported by the +.Dv AF_UNSPEC , +it means the caller will accept any address family supported by the operating system. .It Fa ai_socktype Denotes the type of socket that is wanted: @@ -268,7 +268,7 @@ behaves as if the caller provided a with .Fa ai_family set to -.Dv PF_UNSPEC +.Dv AF_UNSPEC and all other elements set to zero or .Dv NULL . .Pp @@ -380,7 +380,7 @@ int s; const char *cause = NULL; memset(&hints, 0, sizeof(hints)); -hints.ai_family = PF_UNSPEC; +hints.ai_family = AF_UNSPEC; hints.ai_socktype = SOCK_STREAM; error = getaddrinfo("www.kame.net", "http", &hints, &res0); if (error) { @@ -423,7 +423,7 @@ int nsock; const char *cause = NULL; memset(&hints, 0, sizeof(hints)); -hints.ai_family = PF_UNSPEC; +hints.ai_family = AF_UNSPEC; hints.ai_socktype = SOCK_STREAM; hints.ai_flags = AI_PASSIVE; error = getaddrinfo(NULL, "http", &hints, &res0); diff --git a/lib/libc/net/getaddrinfo.c b/lib/libc/net/getaddrinfo.c index ed1a388..e2eb1a0 100644 --- a/lib/libc/net/getaddrinfo.c +++ b/lib/libc/net/getaddrinfo.c @@ -2164,7 +2164,11 @@ getanswer(const querybuf *answer, int anslen, const char *qname, int qtype, return sentinel.ai_next; } - RES_SET_H_ERRNO(res, NO_RECOVERY); + /* + * We could have walked a CNAME chain, but the ultimate target + * may not have what we looked for. + */ + RES_SET_H_ERRNO(res, ntohs(hp->ancount) > 0 ? NO_DATA : NO_RECOVERY); return NULL; } @@ -2341,6 +2345,7 @@ _dns_getaddrinfo(void *rv, void *cb_data, va_list ap) if (sentinel.ai_next == NULL) switch (res->res_h_errno) { case HOST_NOT_FOUND: + case NO_DATA: return NS_NOTFOUND; case TRY_AGAIN: return NS_TRYAGAIN; diff --git a/lib/libc/net/gethostbynis.c b/lib/libc/net/gethostbynis.c index c0d5177..6bafdb1 100644 --- a/lib/libc/net/gethostbynis.c +++ b/lib/libc/net/gethostbynis.c @@ -198,61 +198,6 @@ _gethostbynisaddr_r(const void *addr, socklen_t len, int af, } #endif /* YP */ -/* XXX _gethostbynisname/_gethostbynisaddr only used by getipnodeby*() */ -struct hostent * -_gethostbynisname(const char *name, int af) -{ -#ifdef YP - struct hostent *he; - struct hostent_data *hed; - u_long oresopt; - int error; - res_state statp; - - statp = __res_state(); - if ((he = __hostent_init()) == NULL || - (hed = __hostent_data_init()) == NULL) { - RES_SET_H_ERRNO(statp, NETDB_INTERNAL); - return (NULL); - } - - oresopt = statp->options; - statp->options &= ~RES_USE_INET6; - error = _gethostbynisname_r(name, af, he, hed); - statp->options = oresopt; - return (error == 0) ? he : NULL; -#else - return (NULL); -#endif -} - -struct hostent * -_gethostbynisaddr(const void *addr, socklen_t len, int af) -{ -#ifdef YP - struct hostent *he; - struct hostent_data *hed; - u_long oresopt; - int error; - res_state statp; - - statp = __res_state(); - if ((he = __hostent_init()) == NULL || - (hed = __hostent_data_init()) == NULL) { - RES_SET_H_ERRNO(statp, NETDB_INTERNAL); - return (NULL); - } - - oresopt = statp->options; - statp->options &= ~RES_USE_INET6; - error = _gethostbynisaddr_r(addr, len, af, he, hed); - statp->options = oresopt; - return (error == 0) ? he : NULL; -#else - return (NULL); -#endif -} - int _nis_gethostbyname(void *rval, void *cb_data, va_list ap) { diff --git a/lib/libc/net/map_v4v6.c b/lib/libc/net/map_v4v6.c index 09b035b..327d6b4 100644 --- a/lib/libc/net/map_v4v6.c +++ b/lib/libc/net/map_v4v6.c @@ -78,19 +78,11 @@ typedef union { void _map_v4v6_address(const char *src, char *dst) { - u_char *p = (u_char *)dst; - char tmp[NS_INADDRSZ]; - int i; - - /* Stash a temporary copy so our caller can update in place. */ - memcpy(tmp, src, NS_INADDRSZ); + /* Our caller may update in place. */ + memmove(&dst[12], src, NS_INADDRSZ); /* Mark this ipv6 addr as a mapped ipv4. */ - for (i = 0; i < 10; i++) - *p++ = 0x00; - *p++ = 0xff; - *p++ = 0xff; - /* Retrieve the saved copy and we're done. */ - memcpy((void*)p, tmp, NS_INADDRSZ); + memset(&dst[10], 0xff, 2); + memset(&dst[0], 0, 10); } void diff --git a/lib/libc/net/name6.c b/lib/libc/net/name6.c index 89effe6..51e2da15 100644 --- a/lib/libc/net/name6.c +++ b/lib/libc/net/name6.c @@ -794,10 +794,9 @@ match_addrselectpolicy(struct sockaddr *addr, struct policyhead *head) memset(&key, 0, sizeof(key)); key.sin6_family = AF_INET6; key.sin6_len = sizeof(key); - key.sin6_addr.s6_addr[10] = 0xff; - key.sin6_addr.s6_addr[11] = 0xff; - memcpy(&key.sin6_addr.s6_addr[12], - &((struct sockaddr_in *)addr)->sin_addr, 4); + _map_v4v6_address( + (char *)&((struct sockaddr_in *)addr)->sin_addr, + (char *)&key.sin6_addr); break; default: return(NULL); diff --git a/lib/libc/net/netdb_private.h b/lib/libc/net/netdb_private.h index 0eedb3c..8ab2247 100644 --- a/lib/libc/net/netdb_private.h +++ b/lib/libc/net/netdb_private.h @@ -133,8 +133,6 @@ void _endhostdnsent(void); void _endhosthtent(struct hostent_data *); void _endnetdnsent(void); void _endnethtent(struct netent_data *); -struct hostent *_gethostbynisaddr(const void *, socklen_t, int); -struct hostent *_gethostbynisname(const char *, int); void _map_v4v6_address(const char *, char *); void _map_v4v6_hostent(struct hostent *, char **, char *); void _sethostdnsent(int); diff --git a/lib/libc/net/rcmdsh.c b/lib/libc/net/rcmdsh.c index f30ad14..13278df 100644 --- a/lib/libc/net/rcmdsh.c +++ b/lib/libc/net/rcmdsh.c @@ -36,6 +36,7 @@ #include <sys/cdefs.h> __FBSDID("$FreeBSD$"); +#include "namespace.h" #include <sys/types.h> #include <sys/socket.h> #include <sys/wait.h> @@ -48,6 +49,7 @@ __FBSDID("$FreeBSD$"); #include <stdio.h> #include <string.h> #include <unistd.h> +#include "un-namespace.h" /* * This is a replacement rcmd() function that uses the rsh(1) @@ -99,7 +101,7 @@ rcmdsh(char **ahost, int rport, const char *locuser, const char *remuser, } /* Get a socketpair we'll use for stdin and stdout. */ - if (socketpair(AF_UNIX, SOCK_STREAM, PF_UNSPEC, sp) == -1) { + if (_socketpair(AF_UNIX, SOCK_STREAM, PF_UNSPEC, sp) == -1) { perror("rcmdsh: socketpair"); return (-1); } @@ -112,8 +114,8 @@ rcmdsh(char **ahost, int rport, const char *locuser, const char *remuser, /* * Child. We use sp[1] to be stdin/stdout, and close sp[0]. */ - (void)close(sp[0]); - if (dup2(sp[1], 0) == -1 || dup2(0, 1) == -1) { + (void)_close(sp[0]); + if (_dup2(sp[1], 0) == -1 || _dup2(0, 1) == -1) { perror("rcmdsh: dup2 failed"); _exit(255); } @@ -156,9 +158,9 @@ rcmdsh(char **ahost, int rport, const char *locuser, const char *remuser, _exit(255); } else { /* Parent. close sp[1], return sp[0]. */ - (void)close(sp[1]); + (void)_close(sp[1]); /* Reap child. */ - (void)wait(NULL); + (void)_waitpid(cpid, NULL, 0); return (sp[0]); } /* NOTREACHED */ diff --git a/lib/libc/stdio/findfp.c b/lib/libc/stdio/findfp.c index b8bb5af..6a68958 100644 --- a/lib/libc/stdio/findfp.c +++ b/lib/libc/stdio/findfp.c @@ -41,6 +41,7 @@ __FBSDID("$FreeBSD$"); #include <unistd.h> #include <stdio.h> #include <stdlib.h> +#include <stdint.h> #include <string.h> #include <spinlock.h> @@ -96,11 +97,22 @@ moreglue(int n) struct glue *g; static FILE empty = { ._fl_mutex = PTHREAD_MUTEX_INITIALIZER }; FILE *p; + size_t align; - g = (struct glue *)malloc(sizeof(*g) + ALIGNBYTES + n * sizeof(FILE)); + /* + * FILE has a mbstate_t variable. This variable tries to be int64_t + * aligned through its definition. int64_t may be larger than void *, + * which is the size traditionally used for ALIGNBYTES. So, use our own + * rounding instead of the MI ALIGN macros. If for some reason + * ALIGNBYTES is larger than int64_t, respect that too. There appears to + * be no portable way to ask for FILE's alignment requirements other + * than just knowing here. + */ + align = MAX(ALIGNBYTES, sizeof(int64_t)); + g = (struct glue *)malloc(sizeof(*g) + align + n * sizeof(FILE)); if (g == NULL) return (NULL); - p = (FILE *)ALIGN(g + 1); + p = (FILE *)roundup((uintptr_t)(g + 1), align); g->next = NULL; g->niobs = n; g->iobs = p; diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc index 7cee03a..3c6ba17 100644 --- a/lib/libc/stdlib/Makefile.inc +++ b/lib/libc/stdlib/Makefile.inc @@ -6,7 +6,8 @@ MISRCS+=_Exit.c a64l.c abort.c abs.c atexit.c atof.c atoi.c atol.c atoll.c \ bsearch.c div.c exit.c getenv.c getopt.c getopt_long.c \ - getsubopt.c hcreate.c heapsort.c heapsort_b.c imaxabs.c imaxdiv.c \ + getsubopt.c hcreate.c hcreate_r.c hdestroy_r.c heapsort.c heapsort_b.c \ + hsearch_r.c imaxabs.c imaxdiv.c \ insque.c l64a.c labs.c ldiv.c llabs.c lldiv.c lsearch.c \ merge.c mergesort_b.c ptsname.c qsort.c qsort_r.c quick_exit.c \ radixsort.c rand.c \ diff --git a/lib/libc/stdlib/hcreate.3 b/lib/libc/stdlib/hcreate.3 index 2161f92..5709157 100644 --- a/lib/libc/stdlib/hcreate.3 +++ b/lib/libc/stdlib/hcreate.3 @@ -28,7 +28,7 @@ .\" .\" $FreeBSD$ .\" -.Dd July 21, 2014 +.Dd December 26, 2015 .Dt HCREATE 3 .Os .Sh NAME @@ -76,8 +76,8 @@ The .Fa nel argument is an estimate of the maximum number of entries that the table should contain. -This number may be adjusted upward by the -algorithm in order to obtain certain mathematically favorable circumstances. +As this implementation resizes the hash table dynamically, +this argument is ignored. .Pp The .Fn hdestroy @@ -274,8 +274,6 @@ functions will fail if: .Bl -tag -width Er .It Bq Er ENOMEM Insufficient memory is available. -.It Bq Er EINVAL -A table already exists. .El .Pp The diff --git a/lib/libc/stdlib/hcreate.c b/lib/libc/stdlib/hcreate.c index b3be9b4..2d5d943 100644 --- a/lib/libc/stdlib/hcreate.c +++ b/lib/libc/stdlib/hcreate.c @@ -1,9 +1,6 @@ -/* $NetBSD: hcreate.c,v 1.7 2011/09/14 23:33:51 christos Exp $ */ - -/* - * Copyright (c) 2001 Christopher G. Demetriou - * All rights reserved. - * +/*- + * Copyright (c) 2015 Nuxi, https://nuxi.nl/ + * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: @@ -12,207 +9,65 @@ * 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. 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. - * - * <<Id: LICENSE,v 1.2 2000/06/14 15:57:33 cgd Exp>> - */ - -/* - * hcreate() / hsearch() / hdestroy() * - * SysV/XPG4 hash table functions. - * - * Implementation done based on NetBSD manual page and Solaris manual page, - * plus my own personal experience about how they're supposed to work. - * - * I tried to look at Knuth (as cited by the Solaris manual page), but - * nobody had a copy in the office, so... + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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> -#if 0 -#if defined(LIBC_SCCS) && !defined(lint) -__RCSID("$NetBSD: hcreate.c,v 1.8 2011/09/17 16:54:39 christos Exp $"); -#endif /* LIBC_SCCS and not lint */ -#endif __FBSDID("$FreeBSD$"); -#include <sys/types.h> -#include <sys/queue.h> -#include <errno.h> #include <search.h> -#include <stdlib.h> -#include <string.h> +#include <stdbool.h> +#include <stddef.h> /* - * DO NOT MAKE THIS STRUCTURE LARGER THAN 32 BYTES (4 ptrs on 64-bit - * ptr machine) without adjusting MAX_BUCKETS_LG2 below. + * Thread unsafe interface: use a single process-wide hash table and + * forward calls to *_r() functions. */ -struct internal_entry { - SLIST_ENTRY(internal_entry) link; - ENTRY ent; -}; -SLIST_HEAD(internal_head, internal_entry); - -#define MIN_BUCKETS_LG2 4 -#define MIN_BUCKETS (1 << MIN_BUCKETS_LG2) -/* - * max * sizeof internal_entry must fit into size_t. - * assumes internal_entry is <= 32 (2^5) bytes. - */ -#define MAX_BUCKETS_LG2 (sizeof (size_t) * 8 - 1 - 5) -#define MAX_BUCKETS ((size_t)1 << MAX_BUCKETS_LG2) - -/* Default hash function, from db/hash/hash_func.c */ -extern u_int32_t (*__default_hash)(const void *, size_t); - -static struct hsearch_data htable; +static struct hsearch_data global_hashtable; +static bool global_hashtable_initialized = false; int hcreate(size_t nel) { - /* Make sure this is not called when a table already exists. */ - if (htable.table != NULL) { - errno = EINVAL; - return 0; - } - return hcreate_r(nel, &htable); -} - -int -hcreate_r(size_t nel, struct hsearch_data *head) -{ - struct internal_head *table; - size_t idx; - unsigned int p2; - void *p; - - /* If nel is too small, make it min sized. */ - if (nel < MIN_BUCKETS) - nel = MIN_BUCKETS; - - /* If it is too large, cap it. */ - if (nel > MAX_BUCKETS) - nel = MAX_BUCKETS; - - /* If it is not a power of two in size, round up. */ - if ((nel & (nel - 1)) != 0) { - for (p2 = 0; nel != 0; p2++) - nel >>= 1; - nel = 1 << p2; - } - - /* Allocate the table. */ - head->size = nel; - head->filled = 0; - p = malloc(nel * sizeof table[0]); - if (p == NULL) { - errno = ENOMEM; - return 0; - } - head->table = p; - table = p; - - /* Initialize it. */ - for (idx = 0; idx < nel; idx++) - SLIST_INIT(&table[idx]); - - return 1; + return (1); } void hdestroy(void) { - hdestroy_r(&htable); -} - -void -hdestroy_r(struct hsearch_data *head) -{ - struct internal_entry *ie; - size_t idx; - void *p; - struct internal_head *table; - - if (head == NULL) - return; - - p = head->table; - head->table = NULL; - table = p; - for (idx = 0; idx < head->size; idx++) { - while (!SLIST_EMPTY(&table[idx])) { - ie = SLIST_FIRST(&table[idx]); - SLIST_REMOVE_HEAD(&table[idx], link); - free(ie); - } + /* Destroy global hash table if present. */ + if (global_hashtable_initialized) { + hdestroy_r(&global_hashtable); + global_hashtable_initialized = false; } - free(table); } ENTRY * hsearch(ENTRY item, ACTION action) { - ENTRY *ep; - (void)hsearch_r(item, action, &ep, &htable); - return ep; -} - -int -hsearch_r(ENTRY item, ACTION action, ENTRY **itemp, struct hsearch_data *head) -{ - struct internal_head *table, *chain; - struct internal_entry *ie; - uint32_t hashval; - size_t len; - void *p; - - p = head->table; - table = p; + ENTRY *retval; - len = strlen(item.key); - hashval = (*__default_hash)(item.key, len); - - chain = &table[hashval & (head->size - 1)]; - ie = SLIST_FIRST(chain); - while (ie != NULL) { - if (strcmp(ie->ent.key, item.key) == 0) - break; - ie = SLIST_NEXT(ie, link); - } - - if (ie != NULL) { - *itemp = &ie->ent; - return 1; - } else if (action == FIND) { - *itemp = NULL; - errno = ESRCH; - return 1; + /* Create global hash table if needed. */ + if (!global_hashtable_initialized) { + if (hcreate_r(0, &global_hashtable) == 0) + return (NULL); + global_hashtable_initialized = true; } - - ie = malloc(sizeof *ie); - if (ie == NULL) - return 0; - ie->ent.key = item.key; - ie->ent.data = item.data; - - SLIST_INSERT_HEAD(chain, ie, link); - *itemp = &ie->ent; - head->filled++; - return 1; + if (hsearch_r(item, action, &retval, &global_hashtable) == 0) + return (NULL); + return (retval); } diff --git a/lib/libc/stdlib/hcreate_r.c b/lib/libc/stdlib/hcreate_r.c new file mode 100644 index 0000000..83e322a --- /dev/null +++ b/lib/libc/stdlib/hcreate_r.c @@ -0,0 +1,63 @@ +/*- + * Copyright (c) 2015 Nuxi, https://nuxi.nl/ + * + * 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 AUTHOR 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 AUTHOR 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> +__FBSDID("$FreeBSD$"); + +#include <search.h> +#include <stdlib.h> + +#include "hsearch.h" + +int +hcreate_r(size_t nel, struct hsearch_data *htab) +{ + struct __hsearch *hsearch; + + /* + * Allocate a hash table object. Ignore the provided hint and start + * off with a table of sixteen entries. In most cases this hint is + * just a wild guess. Resizing the table dynamically if the use + * increases a threshold does not affect the worst-case running time. + */ + hsearch = malloc(sizeof(*hsearch)); + if (hsearch == NULL) + return 0; + hsearch->entries = calloc(16, sizeof(ENTRY)); + if (hsearch->entries == NULL) { + free(hsearch); + return 0; + } + + /* + * Pick a random initialization for the FNV-1a hashing. This makes it + * hard to come up with a fixed set of keys to force hash collisions. + */ + arc4random_buf(&hsearch->offset_basis, sizeof(hsearch->offset_basis)); + hsearch->index_mask = 0xf; + hsearch->entries_used = 0; + htab->__hsearch = hsearch; + return 1; +} diff --git a/lib/libc/stdlib/hdestroy_r.c b/lib/libc/stdlib/hdestroy_r.c new file mode 100644 index 0000000..890bd085 --- /dev/null +++ b/lib/libc/stdlib/hdestroy_r.c @@ -0,0 +1,43 @@ +/*- + * Copyright (c) 2015 Nuxi, https://nuxi.nl/ + * + * 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 AUTHOR 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 AUTHOR 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> +__FBSDID("$FreeBSD$"); + +#include <search.h> +#include <stdlib.h> + +#include "hsearch.h" + +void +hdestroy_r(struct hsearch_data *htab) +{ + struct __hsearch *hsearch; + + /* Free hash table object and its entries. */ + hsearch = htab->__hsearch; + free(hsearch->entries); + free(hsearch); +} diff --git a/lib/libc/stdlib/hsearch.h b/lib/libc/stdlib/hsearch.h new file mode 100644 index 0000000..649933d --- /dev/null +++ b/lib/libc/stdlib/hsearch.h @@ -0,0 +1,40 @@ +/*- + * Copyright (c) 2015 Nuxi, https://nuxi.nl/ + * + * 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 AUTHOR 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 AUTHOR 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. + * + * $FreeBSD$ + */ + +#ifndef HSEARCH_H +#define HSEARCH_H + +#include <search.h> + +struct __hsearch { + size_t offset_basis; /* Initial value for FNV-1a hashing. */ + size_t index_mask; /* Bitmask for indexing the table. */ + size_t entries_used; /* Number of entries currently used. */ + ENTRY *entries; /* Hash table entries. */ +}; + +#endif diff --git a/lib/libc/stdlib/hsearch_r.c b/lib/libc/stdlib/hsearch_r.c new file mode 100644 index 0000000..2fb5991 --- /dev/null +++ b/lib/libc/stdlib/hsearch_r.c @@ -0,0 +1,150 @@ +/*- + * Copyright (c) 2015 Nuxi, https://nuxi.nl/ + * + * 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 AUTHOR 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 AUTHOR 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> +__FBSDID("$FreeBSD$"); + +#include <errno.h> +#include <limits.h> +#include <search.h> +#include <stdint.h> +#include <stdlib.h> +#include <string.h> + +#include "hsearch.h" + +/* + * Look up an unused entry in the hash table for a given hash. For this + * implementation we use quadratic probing. Quadratic probing has the + * advantage of preventing primary clustering. + */ +static ENTRY * +hsearch_lookup_free(struct __hsearch *hsearch, size_t hash) +{ + size_t index, i; + + for (index = hash, i = 0;; index += ++i) { + ENTRY *entry = &hsearch->entries[index & hsearch->index_mask]; + if (entry->key == NULL) + return (entry); + } +} + +/* + * Computes an FNV-1a hash of the key. Depending on the pointer size, this + * either uses the 32- or 64-bit FNV prime. + */ +static size_t +hsearch_hash(size_t offset_basis, const char *str) +{ + size_t hash; + + hash = offset_basis; + while (*str != '\0') { + hash ^= (uint8_t)*str++; + if (sizeof(size_t) * CHAR_BIT <= 32) + hash *= UINT32_C(16777619); + else + hash *= UINT64_C(1099511628211); + } + return (hash); +} + +int +hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab) +{ + struct __hsearch *hsearch; + ENTRY *entry, *old_entries, *new_entries; + size_t hash, index, i, old_hash, old_count, new_count; + + hsearch = htab->__hsearch; + hash = hsearch_hash(hsearch->offset_basis, item.key); + + /* + * Search the hash table for an existing entry for this key. + * Stop searching if we run into an unused hash table entry. + */ + for (index = hash, i = 0;; index += ++i) { + entry = &hsearch->entries[index & hsearch->index_mask]; + if (entry->key == NULL) + break; + if (strcmp(entry->key, item.key) == 0) { + *retval = entry; + return (1); + } + } + + /* Only perform the insertion if action is set to ENTER. */ + if (action == FIND) { + errno = ESRCH; + return (0); + } + + if (hsearch->entries_used * 2 >= hsearch->index_mask) { + /* Preserve the old hash table entries. */ + old_count = hsearch->index_mask + 1; + old_entries = hsearch->entries; + + /* + * Allocate and install a new table if insertion would + * yield a hash table that is more than 50% used. By + * using 50% as a threshold, a lookup will only take up + * to two steps on average. + */ + new_count = (hsearch->index_mask + 1) * 2; + new_entries = calloc(new_count, sizeof(ENTRY)); + if (new_entries == NULL) + return (0); + hsearch->entries = new_entries; + hsearch->index_mask = new_count - 1; + + /* Copy over the entries from the old table to the new table. */ + for (i = 0; i < old_count; ++i) { + entry = &old_entries[i]; + if (entry->key != NULL) { + old_hash = hsearch_hash(hsearch->offset_basis, + entry->key); + *hsearch_lookup_free(hsearch, old_hash) = + *entry; + } + } + + /* Destroy the old hash table entries. */ + free(old_entries); + + /* + * Perform a new lookup for a free table entry, so that + * we insert the entry into the new hash table. + */ + hsearch = htab->__hsearch; + entry = hsearch_lookup_free(hsearch, hash); + } + + /* Insert the new entry into the hash table. */ + *entry = item; + ++hsearch->entries_used; + *retval = entry; + return (1); +} diff --git a/lib/libc/stdlib/tdelete.c b/lib/libc/stdlib/tdelete.c index bef187e..7799f35 100644 --- a/lib/libc/stdlib/tdelete.c +++ b/lib/libc/stdlib/tdelete.c @@ -1,72 +1,213 @@ -/* $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */ - -/* - * Tree search generalized from Knuth (6.2.2) Algorithm T just like - * the AT&T man page says. +/*- + * Copyright (c) 2015 Nuxi, https://nuxi.nl/ * - * The node_t structure is for internal use only, lint doesn't grok it. + * 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. * - * Written by reading the System V Interface Definition, not the code. - * - * Totally public domain. + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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> -#if 0 -#if defined(LIBC_SCCS) && !defined(lint) -__RCSID("$NetBSD: tdelete.c,v 1.6 2012/06/25 22:32:45 abs Exp $"); -#endif /* LIBC_SCCS and not lint */ -#endif __FBSDID("$FreeBSD$"); -#define _SEARCH_PRIVATE +#define _SEARCH_PRIVATE #include <search.h> +#include <stdbool.h> #include <stdlib.h> +#include "tsearch_path.h" /* - * find a node with given key - * - * vkey: key to be found - * vrootp: address of the root of the tree - * compar: function to carry out node comparisons - */ + * Makes a step to the left along the binary search tree. This step is + * also saved, so it can be replayed while rebalancing. +*/ +#define GO_LEFT() do { \ + if ((*leaf)->balance == 0 || \ + ((*leaf)->balance < 0 && (*leaf)->rlink->balance == 0)) { \ + /* \ + * If we reach a node that is balanced, or has a child \ + * in the opposite direction that is balanced, we know \ + * that we won't need to perform any rotations above \ + * this point. In this case rotations are always \ + * capable of keeping the subtree in balance. Make \ + * this the base node and reset the path. \ + */ \ + base = leaf; \ + path_init(&path); \ + } \ + path_taking_left(&path); \ + leaf = &(*leaf)->llink; \ +} while (0) + +/* Makes a step to the right along the binary search tree. */ +#define GO_RIGHT() do { \ + if ((*leaf)->balance == 0 || \ + ((*leaf)->balance > 0 && (*leaf)->llink->balance == 0)) { \ + base = leaf; \ + path_init(&path); \ + } \ + result = &(*leaf)->key; \ + path_taking_right(&path); \ + leaf = &(*leaf)->rlink; \ +} while (0) + void * -tdelete(const void * __restrict vkey, void ** __restrict vrootp, +tdelete(const void *restrict key, void **restrict rootp, int (*compar)(const void *, const void *)) { - node_t **rootp = (node_t **)vrootp; - node_t *p, *q, *r; + struct path path; + node_t *root, **base, **leaf, *old, **n, *x, *y, *z; + void *result; int cmp; - if (rootp == NULL || (p = *rootp) == NULL) - return NULL; + /* POSIX requires that tdelete() returns NULL if rootp is NULL. */ + if (rootp == NULL) + return (NULL); + root = *rootp; + + /* + * Find the leaf that needs to be removed. Return if we cannot + * find an existing entry. Keep track of the path that is taken + * to get to the node, as we will need it to adjust the + * balances. + */ + result = (void *)1; + path_init(&path); + base = &root; + leaf = &root; + for (;;) { + if (*leaf == NULL) + return (NULL); + cmp = compar(key, (*leaf)->key); + if (cmp < 0) { + result = &(*leaf)->key; + GO_LEFT(); + } else if (cmp > 0) { + result = &(*leaf)->key; + GO_RIGHT(); + } else { + break; + } + } - while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) { - p = *rootp; - rootp = (cmp < 0) ? - &(*rootp)->llink : /* follow llink branch */ - &(*rootp)->rlink; /* follow rlink branch */ - if (*rootp == NULL) - return NULL; /* key not found */ + /* Found a matching key in the tree. Remove the node. */ + if ((*leaf)->llink == NULL) { + /* Node has no left children. Replace by its right subtree. */ + old = *leaf; + *leaf = old->rlink; + free(old); + } else { + /* + * Node has left children. Replace this node's key by + * its predecessor's and remove that node instead. + */ + void **keyp = &(*leaf)->key; + GO_LEFT(); + while ((*leaf)->rlink != NULL) + GO_RIGHT(); + old = *leaf; + *keyp = old->key; + *leaf = old->llink; + free(old); } - r = (*rootp)->rlink; /* D1: */ - if ((q = (*rootp)->llink) == NULL) /* Left NULL? */ - q = r; - else if (r != NULL) { /* Right link is NULL? */ - if (r->llink == NULL) { /* D2: Find successor */ - r->llink = q; - q = r; - } else { /* D3: Find NULL link */ - for (q = r->llink; q->llink != NULL; q = r->llink) - r = q; - r->llink = q->rlink; - q->llink = (*rootp)->llink; - q->rlink = (*rootp)->rlink; + + /* + * Walk along the same path a second time and adjust the + * balances. Though this code looks similar to the rebalancing + * performed in tsearch(), it is not identical. We now also need + * to consider the case of outward imbalance in the right-right + * and left-left case that only exists when deleting. Hence the + * duplication of code. + */ + for (n = base; n != leaf;) { + if (path_took_left(&path)) { + x = *n; + if (x->balance < 0) { + y = x->rlink; + if (y->balance > 0) { + /* Right-left case. */ + z = y->llink; + x->rlink = z->llink; + z->llink = x; + y->llink = z->rlink; + z->rlink = y; + *n = z; + + x->balance = z->balance < 0 ? 1 : 0; + y->balance = z->balance > 0 ? -1 : 0; + z->balance = 0; + } else { + /* Right-right case. */ + x->rlink = y->llink; + y->llink = x; + *n = y; + + if (y->balance < 0) { + x->balance = 0; + y->balance = 0; + } else { + x->balance = -1; + y->balance = 1; + } + } + } else { + --x->balance; + } + n = &x->llink; + } else { + x = *n; + if (x->balance > 0) { + y = x->llink; + if (y->balance < 0) { + /* Left-right case. */ + z = y->rlink; + y->rlink = z->llink; + z->llink = y; + x->llink = z->rlink; + z->rlink = x; + *n = z; + + x->balance = z->balance > 0 ? -1 : 0; + y->balance = z->balance < 0 ? 1 : 0; + z->balance = 0; + } else { + /* Left-left case. */ + x->llink = y->rlink; + y->rlink = x; + *n = y; + + if (y->balance > 0) { + x->balance = 0; + y->balance = 0; + } else { + x->balance = 1; + y->balance = -1; + } + } + } else { + ++x->balance; + } + n = &x->rlink; } } - if (p != *rootp) - free(*rootp); /* D4: Free node */ - *rootp = q; /* link parent to new node */ - return p; + + /* Return the parent of the old entry. */ + *rootp = root; + return (result); } diff --git a/lib/libc/stdlib/tsearch.3 b/lib/libc/stdlib/tsearch.3 index 7a204d0..2205f7e 100644 --- a/lib/libc/stdlib/tsearch.3 +++ b/lib/libc/stdlib/tsearch.3 @@ -27,7 +27,7 @@ .\" OpenBSD: tsearch.3,v 1.2 1998/06/21 22:13:49 millert Exp .\" $FreeBSD$ .\" -.Dd June 15, 1997 +.Dd December 6, 2015 .Dt TSEARCH 3 .Os .Sh NAME @@ -50,8 +50,12 @@ The .Fn tsearch , and .Fn twalk -functions manage binary search trees based on algorithms T and D -from Knuth (6.2.2). +functions manage binary search trees. +This implementation uses a balanced AVL tree, +which due to its strong theoretical limit on the height of the tree has +the advantage of calling the comparison function relatively +infrequently. +.Pp The comparison function passed in by the user has the same style of return values as .Xr strcmp 3 . diff --git a/lib/libc/stdlib/tsearch.c b/lib/libc/stdlib/tsearch.c index 16bbf7c..b96a275 100644 --- a/lib/libc/stdlib/tsearch.c +++ b/lib/libc/stdlib/tsearch.c @@ -1,55 +1,200 @@ -/* $NetBSD: tsearch.c,v 1.7 2012/06/25 22:32:45 abs Exp $ */ - -/* - * Tree search generalized from Knuth (6.2.2) Algorithm T just like - * the AT&T man page says. - * - * The node_t structure is for internal use only, lint doesn't grok it. +/*- + * Copyright (c) 2015 Nuxi, https://nuxi.nl/ * - * Written by reading the System V Interface Definition, not the code. + * 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. * - * Totally public domain. + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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> -#if 0 -#if defined(LIBC_SCCS) && !defined(lint) -__RCSID("$NetBSD: tsearch.c,v 1.7 2012/06/25 22:32:45 abs Exp $"); -#endif /* LIBC_SCCS and not lint */ -#endif __FBSDID("$FreeBSD$"); -#define _SEARCH_PRIVATE +#define _SEARCH_PRIVATE #include <search.h> #include <stdlib.h> -/* find or insert datum into search tree */ +#include "tsearch_path.h" + void * -tsearch(const void *vkey, void **vrootp, +tsearch(const void *key, void **rootp, int (*compar)(const void *, const void *)) { - node_t *q; - node_t **rootp = (node_t **)vrootp; + struct path path; + node_t *root, **base, **leaf, *result, *n, *x, *y, *z; + int cmp; + /* POSIX requires that tsearch() returns NULL if rootp is NULL. */ if (rootp == NULL) - return NULL; + return (NULL); + root = *rootp; - while (*rootp != NULL) { /* Knuth's T1: */ - int r; + /* + * Find the leaf where the new key needs to be inserted. Return + * if we've found an existing entry. Keep track of the path that + * is taken to get to the node, as we will need it to adjust the + * balances. + */ + path_init(&path); + base = &root; + leaf = &root; + while (*leaf != NULL) { + if ((*leaf)->balance != 0) { + /* + * If we reach a node that has a non-zero + * balance on the way, we know that we won't + * need to perform any rotations above this + * point. In this case rotations are always + * capable of keeping the subtree in balance. + * Make this the base node and reset the path. + */ + base = leaf; + path_init(&path); + } + cmp = compar(key, (*leaf)->key); + if (cmp < 0) { + path_taking_left(&path); + leaf = &(*leaf)->llink; + } else if (cmp > 0) { + path_taking_right(&path); + leaf = &(*leaf)->rlink; + } else { + return (&(*leaf)->key); + } + } - if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ - return *rootp; /* we found it! */ + /* Did not find a matching key in the tree. Insert a new node. */ + result = *leaf = malloc(sizeof(**leaf)); + if (result == NULL) + return (NULL); + result->key = (void *)key; + result->llink = NULL; + result->rlink = NULL; + result->balance = 0; - rootp = (r < 0) ? - &(*rootp)->llink : /* T3: follow left branch */ - &(*rootp)->rlink; /* T4: follow right branch */ + /* + * Walk along the same path a second time and adjust the + * balances. Except for the first node, all of these nodes must + * have a balance of zero, meaning that these nodes will not get + * out of balance. + */ + for (n = *base; n != *leaf;) { + if (path_took_left(&path)) { + n->balance += 1; + n = n->llink; + } else { + n->balance -= 1; + n = n->rlink; + } } - q = malloc(sizeof(node_t)); /* T5: key not found */ - if (q != 0) { /* make new node */ - *rootp = q; /* link new node to old */ - q->key = __DECONST(void *, vkey);/* initialize new node */ - q->llink = q->rlink = NULL; + /* + * Adjusting the balances may have pushed the balance of the + * base node out of range. Perform a rotation to bring the + * balance back in range. + */ + x = *base; + if (x->balance > 1) { + y = x->llink; + if (y->balance < 0) { + /* + * Left-right case. + * + * x + * / \ z + * y D / \ + * / \ --> y x + * A z /| |\ + * / \ A B C D + * B C + */ + z = y->rlink; + y->rlink = z->llink; + z->llink = y; + x->llink = z->rlink; + z->rlink = x; + *base = z; + + x->balance = z->balance > 0 ? -1 : 0; + y->balance = z->balance < 0 ? 1 : 0; + z->balance = 0; + } else { + /* + * Left-left case. + * + * x y + * / \ / \ + * y C --> A x + * / \ / \ + * A B B C + */ + x->llink = y->rlink; + y->rlink = x; + *base = y; + + x->balance = 0; + y->balance = 0; + } + } else if (x->balance < -1) { + y = x->rlink; + if (y->balance > 0) { + /* + * Right-left case. + * + * x + * / \ z + * A y / \ + * / \ --> x y + * z D /| |\ + * / \ A B C D + * B C + */ + node_t *z = y->llink; + x->rlink = z->llink; + z->llink = x; + y->llink = z->rlink; + z->rlink = y; + *base = z; + + x->balance = z->balance < 0 ? 1 : 0; + y->balance = z->balance > 0 ? -1 : 0; + z->balance = 0; + } else { + /* + * Right-right case. + * + * x y + * / \ / \ + * A y --> x C + * / \ / \ + * B C A B + */ + x->rlink = y->llink; + y->llink = x; + *base = y; + + x->balance = 0; + y->balance = 0; + } } - return q; + + /* Return the new entry. */ + *rootp = root; + return (&result->key); } diff --git a/lib/libc/stdlib/tsearch_path.h b/lib/libc/stdlib/tsearch_path.h new file mode 100644 index 0000000..934c91f --- /dev/null +++ b/lib/libc/stdlib/tsearch_path.h @@ -0,0 +1,97 @@ +/*- + * Copyright (c) 2015 Nuxi, https://nuxi.nl/ + * + * 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 AUTHOR 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 AUTHOR 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. + * + * $FreeBSD$ + */ + +#ifndef TSEARCH_PATH_H +#define TSEARCH_PATH_H + +#include <limits.h> +#include <stdbool.h> +#include <stdint.h> + +/* + * Bookkeeping for storing a path in a balanced binary search tree from + * the root to a leaf node. + * + * For an AVL tree we know that its maximum height of a tree is bounded + * by approximately 1.44 * log2(n) - 0.328. Given that the number of + * entries of the tree is constrained by the size of the address space, + * two uintptr_t's provide sufficient space to store the path from the + * root to any leaf. + */ +struct path { + uintptr_t steps[2]; + unsigned int nsteps; +}; + +/* Initializes the path structure with a zero-length path. */ +static inline void +path_init(struct path *p) +{ + + p->nsteps = 0; +} + +#define STEPS_BIT (sizeof(uintptr_t) * CHAR_BIT) + +/* Pushes a step to the left to the end of the path. */ +static inline void +path_taking_left(struct path *p) +{ + + p->steps[p->nsteps / STEPS_BIT] |= + (uintptr_t)1 << (p->nsteps % STEPS_BIT); + ++p->nsteps; +} + +/* Pushes a step to the right to the end of the path. */ +static inline void +path_taking_right(struct path *p) +{ + + p->steps[p->nsteps / STEPS_BIT] &= + ~((uintptr_t)1 << (p->nsteps % STEPS_BIT)); + ++p->nsteps; +} + +/* + * Pops the first step from the path and returns whether it was a step + * to the left. + */ +static inline bool +path_took_left(struct path *p) +{ + bool result; + + result = p->steps[0] & 0x1; + p->steps[0] = (p->steps[0] >> 1) | (p->steps[1] << (STEPS_BIT - 1)); + p->steps[1] >>= 1; + return (result); +} + +#undef STEPS_BIT + +#endif diff --git a/lib/libc/sys/clock_gettime.2 b/lib/libc/sys/clock_gettime.2 index 583cc8f..e77b1e8 100644 --- a/lib/libc/sys/clock_gettime.2 +++ b/lib/libc/sys/clock_gettime.2 @@ -29,7 +29,7 @@ .\" .\" $FreeBSD$ .\" -.Dd December 29, 2009 +.Dd December 27, 2015 .Dt CLOCK_GETTIME 2 .Os .Sh NAME @@ -134,12 +134,10 @@ The following error codes may be set in .It Bq Er EINVAL The .Fa clock_id +or +.Fa timespec argument was not a valid value. -.It Bq Er EFAULT -The -.Fa *tp -argument address referenced invalid memory. .It Bq Er EPERM A user other than the super-user attempted to set the time. .El diff --git a/lib/libc/sys/gettimeofday.2 b/lib/libc/sys/gettimeofday.2 index 23cc059..86b6b1a 100644 --- a/lib/libc/sys/gettimeofday.2 +++ b/lib/libc/sys/gettimeofday.2 @@ -28,7 +28,7 @@ .\" @(#)gettimeofday.2 8.2 (Berkeley) 5/26/95 .\" $FreeBSD$ .\" -.Dd May 26, 1995 +.Dd December 27, 2015 .Dt GETTIMEOFDAY 2 .Os .Sh NAME @@ -110,8 +110,10 @@ system call even when the system is secure. The following error codes may be set in .Va errno : .Bl -tag -width Er -.It Bq Er EFAULT -An argument address referenced invalid memory. +.It Bq Er EINVAL +The supplied +.Fa timeval +value is invalid. .It Bq Er EPERM A user other than the super-user attempted to set the time. .El diff --git a/lib/libc/tests/resolv/Makefile b/lib/libc/tests/resolv/Makefile index 4e4e62be..4fb43d8 100644 --- a/lib/libc/tests/resolv/Makefile +++ b/lib/libc/tests/resolv/Makefile @@ -6,7 +6,6 @@ BINDIR= ${TESTSDIR} FILES+= mach ATF_TESTS_C+= resolv_test -#TEST_METADATA.resolv_test= timeout="1800" # Note: this test relies on being dynamically linked. You will get a # spurious PASS for a statically linked test. diff --git a/lib/libc/tests/resolv/resolv_test.c b/lib/libc/tests/resolv/resolv_test.c index 5c53569..74e89b1 100644 --- a/lib/libc/tests/resolv/resolv_test.c +++ b/lib/libc/tests/resolv/resolv_test.c @@ -289,21 +289,31 @@ do { \ ATF_REQUIRE(run_tests(_hostlist_file, method) == 0); \ } while(0) -ATF_TC_WITHOUT_HEAD(getaddrinfo_test); +ATF_TC(getaddrinfo_test); +ATF_TC_HEAD(getaddrinfo_test, tc) { + atf_tc_set_md_var(tc, "timeout", "450"); +} ATF_TC_BODY(getaddrinfo_test, tc) { RUN_TESTS(tc, METHOD_GETADDRINFO); } -ATF_TC_WITHOUT_HEAD(gethostby_test); +ATF_TC(gethostby_test); +ATF_TC_HEAD(gethostby_test, tc) { + atf_tc_set_md_var(tc, "timeout", "450"); +} ATF_TC_BODY(gethostby_test, tc) { RUN_TESTS(tc, METHOD_GETHOSTBY); } -ATF_TC_WITHOUT_HEAD(getipnodeby_test); +ATF_TC(getipnodeby_test); +ATF_TC_HEAD(getipnodeby_test, tc) { + + atf_tc_set_md_var(tc, "timeout", "450"); +} ATF_TC_BODY(getipnodeby_test, tc) { diff --git a/lib/libc/tests/stdlib/Makefile b/lib/libc/tests/stdlib/Makefile index 4bc1354..87e84c5 100644 --- a/lib/libc/tests/stdlib/Makefile +++ b/lib/libc/tests/stdlib/Makefile @@ -3,6 +3,7 @@ ATF_TESTS_C+= heapsort_test ATF_TESTS_C+= mergesort_test ATF_TESTS_C+= qsort_test +ATF_TESTS_C+= tsearch_test # TODO: t_getenv_thread, t_mi_vector_hash NETBSD_ATF_TESTS_C+= abs_test diff --git a/lib/libc/tests/stdlib/tsearch_test.c b/lib/libc/tests/stdlib/tsearch_test.c new file mode 100644 index 0000000..b08fd94 --- /dev/null +++ b/lib/libc/tests/stdlib/tsearch_test.c @@ -0,0 +1,131 @@ +/*- + * Copyright (c) 2015 Nuxi, https://nuxi.nl/ + * + * 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 AUTHOR 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 AUTHOR 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> +__FBSDID("$FreeBSD$"); + +#include <atf-c.h> +#define _SEARCH_PRIVATE +#include <search.h> +#include <stdbool.h> +#include <stdlib.h> + +/* Validates the integrity of an AVL tree. */ +static inline unsigned int +tnode_assert(const node_t *n) +{ + unsigned int height_left, height_right; + int balance; + + if (n == NULL) + return 0; + height_left = tnode_assert(n->llink); + height_right = tnode_assert(n->rlink); + balance = (int)height_left - (int)height_right; + ATF_CHECK(balance >= -1); + ATF_CHECK(balance <= 1); + ATF_CHECK_EQ(balance, n->balance); + return (height_left > height_right ? height_left : height_right) + 1; +} + +static int +compar(const void *a, const void *b) +{ + + return *(int *)a - *(int *)b; +} + +ATF_TC_WITHOUT_HEAD(tsearch_test); +ATF_TC_BODY(tsearch_test, tc) +{ + /* + * Run the test below in a deterministic fashion to prevent this + * test from potentially flapping. We assume that this provides + * enough coverage. + */ +#if 0 + unsigned short random_state[3]; + arc4random_buf(random_state, sizeof(random_state)); +#else + unsigned short random_state[3] = { 26554, 13330, 3246 }; +#endif + +#define NKEYS 1000 + /* Create 1000 possible keys. */ + int keys[NKEYS]; + for (int i = 0; i < NKEYS; ++i) + keys[i] = i; + + /* Apply random operations on a binary tree and check the results. */ + void *root = NULL; + bool present[NKEYS] = {}; + for (int i = 0; i < NKEYS * 10; ++i) { + int key = nrand48(random_state) % NKEYS; + switch (nrand48(random_state) % 3) { + case 0: /* tdelete(). */ + if (present[key]) { + ATF_CHECK(tdelete(&key, &root, compar) != NULL); + present[key] = false; + } else { + ATF_CHECK_EQ(NULL, + tdelete(&key, &root, compar)); + } + break; + case 1: /* tfind(). */ + if (present[key]) { + ATF_CHECK_EQ(&keys[key], + *(int **)tfind(&key, &root, compar)); + } else { + ATF_CHECK_EQ(NULL, tfind(&key, &root, compar)); + } + break; + case 2: /* tsearch(). */ + if (present[key]) { + ATF_CHECK_EQ(&keys[key], + *(int **)tsearch(&key, &root, compar)); + } else { + ATF_CHECK_EQ(&keys[key], *(int **)tsearch( + &keys[key], &root, compar)); + present[key] = true; + } + break; + } + tnode_assert(root); + } + + /* Remove all entries from the tree. */ + for (int key = 0; key < NKEYS; ++key) + if (present[key]) + ATF_CHECK(tdelete(&key, &root, compar) != NULL); + ATF_CHECK_EQ(NULL, root); +} + +ATF_TP_ADD_TCS(tp) +{ + + ATF_TP_ADD_TC(tp, tsearch_test); + + return (atf_no_error()); +} |
