diff options
Diffstat (limited to 'tests/deckard/contrib/libfaketime/src')
| -rw-r--r-- | tests/deckard/contrib/libfaketime/src/Makefile | 118 | ||||
| -rw-r--r-- | tests/deckard/contrib/libfaketime/src/Makefile.OSX | 75 | ||||
| -rw-r--r-- | tests/deckard/contrib/libfaketime/src/faketime.c | 385 | ||||
| -rw-r--r-- | tests/deckard/contrib/libfaketime/src/faketime_common.h | 61 | ||||
| -rw-r--r-- | tests/deckard/contrib/libfaketime/src/libfaketime.c | 2646 | ||||
| -rw-r--r-- | tests/deckard/contrib/libfaketime/src/libfaketime.map | 21 | ||||
| -rw-r--r-- | tests/deckard/contrib/libfaketime/src/sunos_endian.h | 12 | ||||
| -rw-r--r-- | tests/deckard/contrib/libfaketime/src/time_ops.h | 104 | ||||
| -rw-r--r-- | tests/deckard/contrib/libfaketime/src/timeprivacy | 270 | ||||
| -rw-r--r-- | tests/deckard/contrib/libfaketime/src/uthash.h | 1208 |
10 files changed, 4900 insertions, 0 deletions
diff --git a/tests/deckard/contrib/libfaketime/src/Makefile b/tests/deckard/contrib/libfaketime/src/Makefile new file mode 100644 index 0000000..e2f047a --- /dev/null +++ b/tests/deckard/contrib/libfaketime/src/Makefile @@ -0,0 +1,118 @@ +# +# Notes: +# +# * Compilation Defines: +# +# FAKE_STAT +# - Enables time faking also for files' timestamps. +# +# NO_ATFILE +# - Disables support for the fstatat() group of functions +# +# PTHREAD_SINGLETHREADED_TIME +# - Define this if you want to single-thread time() ... there ARE +# possible caching side-effects in a multithreaded environment +# without this, but the performance impact may require you to +# try it unsynchronized. +# +# FAKE_INTERNAL_CALLS +# - Also intercept libc internal __functions, e.g. not just time(), +# but also __time(). Enhances compatibility with applications +# that make use of low-level system calls, such as Java Virtual +# Machines. +# +# FAKE_SLEEP +# - Also intercept sleep(), nanosleep(), usleep(), alarm(), [p]poll() +# +# FAKE_TIMERS +# - Also intercept timer_settime() and timer_gettime() +# +# FAKE_PTHREAD +# - Intercept pthread_cond_timedwait +# +# MULTI_ARCH +# - If MULTI_ARCH is set, the faketime wrapper program will put a literal +# $LIB into the LD_PRELOAD environment variable it creates, which makes +# ld automatically choose the correct library version to use for the +# target binary. Use for Linux platforms with Multi-Arch support only! +# +# * Compilation addition: second libMT target added for building the pthread- +# enabled library as a separate library +# +# * Compilation switch change: previous versions compiled using '-nostartfiles' +# This is no longer the case since there is a 'startup' constructor for the library +# which is used to activate the start-at times when specified. This also initializes +# the dynamic disabling of the FAKE_STAT calls. +# +# By default, libfaketime will be compiled for your system's default architecture. +# To build 32-bit libraries and binaries, add -m32 to CFLAGS and LDFLAGS. +# +# Change PREFIX to where you want libfaketime (libraries and wrapper binary) installed. +# LIBDIRNAME is relative to PREFIX. The default is to install into $PREFIX/lib/faketime, +# but you can set LIBDIRNAME to, e.g., /lib64 if you want to install it elsewhere. +# LIBDIRNAME has been introduced to support MultiLib systems. Please do not change the +# default value on MultiArch systems. +# +# For testing in the current directory without installation, try make PREFIX= LIBDIRNAME='.' + +CC ?= gcc +INSTALL ?= install + +PREFIX ?= /usr/local +LIBDIRNAME ?= /lib/faketime +PLATFORM ?=$(shell uname) + +CFLAGS += -std=gnu99 -Wall -Wextra -Werror -Wno-nonnull-compare -DFAKE_PTHREAD -DFAKE_STAT -DFAKE_SLEEP -DFAKE_TIMERS -DFAKE_INTERNAL_CALLS -fPIC -DPREFIX='"'$(PREFIX)'"' -DLIBDIRNAME='"'$(LIBDIRNAME)'"' +ifeq ($(PLATFORM),SunOS) +CFLAGS += -D__EXTENSIONS__ -D_XOPEN_SOURCE=600 +endif + +LIB_LDFLAGS += -shared + +LDFLAGS += -lpthread +ifneq ($(PLATFORM),SunOS) +LDFLAGS += -Wl,--version-script=libfaketime.map +endif + +LDADD += -ldl -lm -lrt +BIN_LDFLAGS += -lrt + +SRC = libfaketime.c +LIBS_OBJ = libfaketime.o libfaketimeMT.o +BINS = faketime + +SONAME = 1 +LIBS = libfaketime.so.${SONAME} libfaketimeMT.so.${SONAME} + +all: ${LIBS} ${BINS} + +libfaketimeMT.o: EXTRA_FLAGS := -DPTHREAD_SINGLETHREADED_TIME + +${LIBS_OBJ}: libfaketime.c + ${CC} -o $@ -c ${CFLAGS} ${CPPFLAGS} ${EXTRA_FLAGS} $< + +%.so.${SONAME}: %.o libfaketime.map + ${CC} -o $@ -Wl,-soname,$@ ${LDFLAGS} ${LIB_LDFLAGS} $< ${LDADD} + +${BINS}: faketime.c + ${CC} -o $@ ${CFLAGS} ${CPPFLAGS} ${EXTRA_FLAGS} $< ${LDFLAGS} ${BIN_LDFLAGS} + +clean: + @rm -f ${LIBS_OBJ} ${LIBS} ${BINS} + +distclean: clean + @echo + +install: ${LIBS} ${BINS} + @echo + @echo "Copying the faketime libraries to ${DESTDIR}${PREFIX}${LIBDIRNAME} and the faketime wrapper script to ${DESTDIR}${PREFIX}/bin ..." + $(INSTALL) -dm0755 "${DESTDIR}${PREFIX}${LIBDIRNAME}/" + $(INSTALL) -m0644 ${LIBS} "${DESTDIR}${PREFIX}${LIBDIRNAME}/" + $(INSTALL) -Dm0755 faketime "${DESTDIR}${PREFIX}/bin/faketime" + +uninstall: + for f in ${LIBS}; do rm -f "${DESTDIR}${PREFIX}${LIBDIRNAME}/$$f"; done + rmdir "${DESTDIR}${PREFIX}${LIBDIRNAME}" + rm -f "${DESTDIR}${PREFIX}/bin/faketime" + +.PHONY: all clean distclean install uninstall diff --git a/tests/deckard/contrib/libfaketime/src/Makefile.OSX b/tests/deckard/contrib/libfaketime/src/Makefile.OSX new file mode 100644 index 0000000..683ad04 --- /dev/null +++ b/tests/deckard/contrib/libfaketime/src/Makefile.OSX @@ -0,0 +1,75 @@ +# +# Notes: +# +# * Compilation Defines: +# +# FAKE_STAT +# - Enables time faking also for files' timestamps. +# +# NO_ATFILE +# - Disables support for the fstatat() group of functions +# +# PTHREAD +# - Define this to enable multithreading support. +# +# PTHREAD_SINGLETHREADED_TIME +# - Define this if you want to single-thread time() ... there ARE +# possible caching side-effects in a multithreaded environment +# without this, but the performance impact may require you to +# try it unsynchronized. +# +# FAKE_SLEEP +# - Also intercept sleep(), nanosleep(), usleep(), alarm(), [p]poll() +# +# * Compilation addition: second libMT target added for building the pthread- +# enabled library as a separate library +# +# * Compilation switch change: previous versions compiled using '-nostartfiles' +# This is no longer the case since there is a 'startup' constructor for the library +# which is used to activate the start-at times when specified. This also initializes +# the dynamic disabling of the FAKE_STAT calls. +# +# By default, libfaketime will be compiled for your system's default architecture. +# To build for a different architecture, add -arch flags to CFLAGS and LDFLAGS. +# +# default to clang to support thread local variables +CC ?= clang +INSTALL ?= install + +PREFIX ?= /usr/local + +CFLAGS += -DFAKE_SLEEP -DFAKE_INTERNAL_CALLS -DPREFIX='"'${PREFIX}'"' +LIB_LDFLAGS += -dynamiclib -current_version 0.9.7 -compatibility_version 0.7 + +SONAME = 1 +LIBS = libfaketime.${SONAME}.dylib +BINS = faketime + +all: ${LIBS} ${BINS} + +libfaketime.${SONAME}.dylib: libfaketime.c + ${CC} -o $@ ${CFLAGS} ${LDFLAGS} ${LIB_LDFLAGS} -install_name ${PREFIX}/lib/faketime/$@ $< + +faketime: faketime.c + ${CC} -o $@ ${CFLAGS} ${LDFLAGS} $< + +clean: + @rm -f ${OBJ} ${LIBS} ${BINS} + +distclean: clean + @echo + +install: ${LIBS} ${BINS} + @echo + @echo "Copying the faketime libraries to ${DESTDIR}${PREFIX}/lib/faketime and the faketime wrapper script to ${DESTDIR}${PREFIX}/bin ..." + $(INSTALL) -dm0755 "${DESTDIR}${PREFIX}/lib/faketime/" + $(INSTALL) -m0644 ${LIBS} "${DESTDIR}${PREFIX}/lib/faketime/" + $(INSTALL) -dm0755 "${DESTDIR}${PREFIX}/bin" + $(INSTALL) -m0755 faketime "${DESTDIR}${PREFIX}/bin/faketime" + +uninstall: + for f in ${LIBS}; do rm -f "${DESTDIR}${PREFIX}/lib/faketime/$$f"; done + rmdir "${DESTDIR}${PREFIX}/lib/faketime" + rm -f "${DESTDIR}${PREFIX}/bin/faketime" + +.PHONY: all clean distclean install uninstall diff --git a/tests/deckard/contrib/libfaketime/src/faketime.c b/tests/deckard/contrib/libfaketime/src/faketime.c new file mode 100644 index 0000000..037d749 --- /dev/null +++ b/tests/deckard/contrib/libfaketime/src/faketime.c @@ -0,0 +1,385 @@ +/* + * libfaketime wrapper command + * + * This file is part of libfaketime, version 0.9.7 + * + * libfaketime is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License v2 as published by the + * Free Software Foundation. + * + * libfaketime is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License v2 along + * with the libfaketime; if not, write to the Free Software Foundation, + * Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * Converted from shell script by Balint Reczey with the following credits + * and comments: + * + * Thanks to Daniel Kahn Gillmor for improvement suggestions. + + * This wrapper exposes only a small subset of the libfaketime functionality. + * Please see libfaketime's README file and man page for more details. + + * Acknowledgment: Parts of the functionality of this wrapper have been + * inspired by Matthias Urlichs' datefudge 1.14. + + * Compile time configuration: Path where the libfaketime libraries can be found + * on Linux/UNIX + * + */ + +#include <stdio.h> +#include <unistd.h> +#include <stdlib.h> +#include <stdbool.h> +#include <stdint.h> +#include <string.h> +#include <time.h> +#include <fcntl.h> +#include <sys/stat.h> +#include <sys/types.h> +#include <sys/wait.h> +#include <sys/mman.h> +#include <semaphore.h> + +#include "faketime_common.h" + +const char version[] = "0.9.7"; + +#ifdef __APPLE__ +static const char *date_cmd = "gdate"; +#else +static const char *date_cmd = "date"; +#endif + +#define PATH_BUFSIZE 4096 + +/* semaphore and shared memory names */ +char sem_name[PATH_BUFSIZE] = {0}, shm_name[PATH_BUFSIZE] = {0}; + +void usage(const char *name) +{ + printf("\n" + "Usage: %s [switches] <timestamp> <program with arguments>\n" + "\n" + "This will run the specified 'program' with the given 'arguments'.\n" + "The program will be tricked into seeing the given 'timestamp' as its starting date and time.\n" + "The clock will continue to run from this timestamp. Please see the manpage (man faketime)\n" + "for advanced options, such as stopping the wall clock and make it run faster or slower.\n" + "\n" + "The optional switches are:\n" + " -m : Use the multi-threaded version of libfaketime\n" + " -f : Use the advanced timestamp specification format (see manpage)\n" + " --exclude-monotonic : Prevent monotonic clock from drifting (not the raw monotonic one)\n" + "\n" + "Examples:\n" + "%s 'last friday 5 pm' /bin/date\n" + "%s '2008-12-24 08:15:42' /bin/date\n" + "%s -f '+2,5y x10,0' /bin/bash -c 'date; while true; do echo $SECONDS ; sleep 1 ; done'\n" + "%s -f '+2,5y x0,50' /bin/bash -c 'date; while true; do echo $SECONDS ; sleep 1 ; done'\n" + "%s -f '+2,5y i2,0' /bin/bash -c 'date; while true; do date; sleep 1 ; done'\n" + "In this single case all spawned processes will use the same global clock\n" + "without restarting it at the start of each process.\n\n" + "(Please note that it depends on your locale settings whether . or , has to be used for fractions)\n" + "\n", name, name, name, name, name, name); +} + +/** Clean up shared objects */ +static void cleanup_shobjs() +{ + if (-1 == sem_unlink(sem_name)) + { + perror("sem_unlink"); + } + if (-1 == shm_unlink(shm_name)) + { + perror("shm_unlink"); + } +} + +int main (int argc, char **argv) +{ + pid_t child_pid; + int curr_opt = 1; + bool use_mt = false, use_direct = false; + long offset; + + while(curr_opt < argc) + { + if (0 == strcmp(argv[curr_opt], "-m")) + { + use_mt = true; + curr_opt++; + continue; + } + else if (0 == strcmp(argv[curr_opt], "-f")) + { + use_direct = true; + curr_opt++; + continue; + } + else if (0 == strcmp(argv[curr_opt], "--exclude-monotonic")) + { + setenv("DONT_FAKE_MONOTONIC", "1", true); + curr_opt++; + continue; + } + else if ((0 == strcmp(argv[curr_opt], "-v")) || + (0 == strcmp(argv[curr_opt], "--version"))) + { + printf("\n%s: Version %s\n" + "For usage information please use '%s --help'.\n", + argv[0], version, argv[0]); + exit(EXIT_SUCCESS); + } + else if ((0 == strcmp(argv[curr_opt], "-h")) || + (0 == strcmp(argv[curr_opt], "-?")) || + (0 == strcmp(argv[curr_opt], "--help"))) + { + usage(argv[0]); + exit(EXIT_SUCCESS); + } + else + { + /* we parsed all options */ + break; + } + } + + /* we need at least a timestamp string and a command to run */ + if (argc - curr_opt < 2) + { + usage(argv[0]); + exit(EXIT_FAILURE); + } + + if (!use_direct) + { + // TODO get seconds + int pfds[2]; + (void) (pipe(pfds) + 1); + int ret = EXIT_SUCCESS; + + if (0 == (child_pid = fork())) + { + close(1); /* close normal stdout */ + (void) (dup(pfds[1]) + 1); /* make stdout same as pfds[1] */ + close(pfds[0]); /* we don't need this */ + if (EXIT_SUCCESS != execlp(date_cmd, date_cmd, "-d", argv[curr_opt], "+%s",(char *) NULL)) + { + perror("Running (g)date failed"); + exit(EXIT_FAILURE); + } + } + else + { + char buf[256] = {0}; /* e will have way less than 256 digits */ + close(pfds[1]); /* we won't write to this */ + (void) (read(pfds[0], buf, 256) + 1); + waitpid(child_pid, &ret, 0); + if (ret != EXIT_SUCCESS) + { + printf("Error: Timestamp to fake not recognized, please re-try with a " + "different timestamp.\n"); + exit(EXIT_FAILURE); + } + offset = atol(buf) - time(NULL); + ret = snprintf(buf, sizeof(buf), "%s%ld", (offset >= 0)?"+":"", offset); + setenv("FAKETIME", buf, true); + close(pfds[0]); /* finished reading */ + } + } + else + { + /* simply pass format string along */ + setenv("FAKETIME", argv[curr_opt], true); + } + int keepalive_fds[2]; + (void) (pipe(keepalive_fds) + 1); + + /* we just consumed the timestamp option */ + curr_opt++; + + { + /* create semaphores and shared memory */ + int shm_fd; + sem_t *sem; + struct ft_shared_s *ft_shared; + char shared_objs[PATH_BUFSIZE * 2 + 1]; + + /* + * Casting of getpid() return value to long needed to make GCC on SmartOS + * happy, since getpid's return value's type on SmartOS is long. Since + * getpid's return value's type is int on most other systems, and that + * sizeof(long) always >= sizeof(int), this works on all platforms without + * the need for crazy #ifdefs. + */ + snprintf(sem_name, PATH_BUFSIZE -1 ,"/faketime_sem_%ld", (long)getpid()); + snprintf(shm_name, PATH_BUFSIZE -1 ,"/faketime_shm_%ld", (long)getpid()); + + if (SEM_FAILED == (sem = sem_open(sem_name, O_CREAT|O_EXCL, S_IWUSR|S_IRUSR, 1))) + { + perror("sem_open"); + exit(EXIT_FAILURE); + } + + /* create shm */ + if (-1 == (shm_fd = shm_open(shm_name, O_CREAT|O_EXCL|O_RDWR, S_IWUSR|S_IRUSR))) + { + perror("shm_open"); + if (-1 == sem_unlink(argv[2])) + { + perror("sem_unlink"); + } + exit(EXIT_FAILURE); + } + + /* set shm size */ + if (-1 == ftruncate(shm_fd, sizeof(uint64_t))) + { + perror("ftruncate"); + cleanup_shobjs(); + exit(EXIT_FAILURE); + } + + /* map shm */ + if (MAP_FAILED == (ft_shared = mmap(NULL, sizeof(struct ft_shared_s), PROT_READ|PROT_WRITE, + MAP_SHARED, shm_fd, 0))) + { + perror("mmap"); + cleanup_shobjs(); + exit(EXIT_FAILURE); + } + + if (sem_wait(sem) == -1) + { + perror("sem_wait"); + cleanup_shobjs(); + exit(EXIT_FAILURE); + } + + /* init elapsed time ticks to zero */ + ft_shared->ticks = 0; + ft_shared->file_idx = 0; + ft_shared->start_time.real.tv_sec = 0; + ft_shared->start_time.real.tv_nsec = -1; + ft_shared->start_time.mon.tv_sec = 0; + ft_shared->start_time.mon.tv_nsec = -1; + ft_shared->start_time.mon_raw.tv_sec = 0; + ft_shared->start_time.mon_raw.tv_nsec = -1; + + if (-1 == munmap(ft_shared, (sizeof(struct ft_shared_s)))) + { + perror("munmap"); + cleanup_shobjs(); + exit(EXIT_FAILURE); + } + + if (sem_post(sem) == -1) + { + perror("semop"); + cleanup_shobjs(); + exit(EXIT_FAILURE); + } + + snprintf(shared_objs, sizeof(shared_objs), "%s %s", sem_name, shm_name); + setenv("FAKETIME_SHARED", shared_objs, true); + sem_close(sem); + } + + { + char *ftpl_path; +#ifdef __APPLE__ + ftpl_path = PREFIX "/libfaketime.1.dylib"; + FILE *check; + check = fopen(ftpl_path, "ro"); + if (check == NULL) + { + ftpl_path = PREFIX "/lib/faketime/libfaketime.1.dylib"; + } + else + { + fclose(check); + } + setenv("DYLD_INSERT_LIBRARIES", ftpl_path, true); + setenv("DYLD_FORCE_FLAT_NAMESPACE", "1", true); +#else + { + char *ld_preload_new, *ld_preload = getenv("LD_PRELOAD"); + size_t len; + if (use_mt) + { + /* + * on MultiArch platforms, such as Debian, we put a literal $LIB into LD_PRELOAD. + */ +#ifndef MULTI_ARCH + ftpl_path = PREFIX LIBDIRNAME "/libfaketimeMT.so.1"; +#else + ftpl_path = PREFIX "/$LIB/faketime/libfaketimeMT.so.1"; +#endif + } + else + { +#ifndef MULTI_ARCH + ftpl_path = PREFIX LIBDIRNAME "/libfaketime.so.1"; +#else + ftpl_path = PREFIX "/$LIB/faketime/libfaketime.so.1"; +#endif + } + len = ((ld_preload)?strlen(ld_preload) + 1: 0) + 1 + strlen(ftpl_path); + ld_preload_new = malloc(len); + snprintf(ld_preload_new, len ,"%s%s%s", (ld_preload)?ld_preload:"", + (ld_preload)?":":"", ftpl_path); + setenv("LD_PRELOAD", ld_preload_new, true); + free(ld_preload_new); + } +#endif + } + + /* run command and clean up shared objects */ + if (0 == (child_pid = fork())) + { + close(keepalive_fds[0]); /* only parent needs to read this */ + if (EXIT_SUCCESS != execvp(argv[curr_opt], &argv[curr_opt])) + { + perror("Running specified command failed"); + exit(EXIT_FAILURE); + } + } + else + { + int ret; + char buf; + close(keepalive_fds[1]); /* only children need keep this open */ + waitpid(child_pid, &ret, 0); + (void) (read(keepalive_fds[0], &buf, 1) + 1); /* reads 0B when all children exit */ + cleanup_shobjs(); + if (WIFSIGNALED(ret)) + { + fprintf(stderr, "Caught %s\n", strsignal(WTERMSIG(ret))); + exit(EXIT_FAILURE); + } + exit(WEXITSTATUS(ret)); + } + + return EXIT_SUCCESS; +} + +/* + * Editor modelines + * + * Local variables: + * c-basic-offset: 2 + * tab-width: 2 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=2 tabstop=2 expandtab: + * :indentSize=2:tabSize=2:noTabs=true: + */ + +/* eof */ diff --git a/tests/deckard/contrib/libfaketime/src/faketime_common.h b/tests/deckard/contrib/libfaketime/src/faketime_common.h new file mode 100644 index 0000000..9fda6a7 --- /dev/null +++ b/tests/deckard/contrib/libfaketime/src/faketime_common.h @@ -0,0 +1,61 @@ +/* + * Faketime's common definitions + * + * Copyright 2013 Balint Reczey <balint@balintreczey.hu> + * + * This file is part of the libfaketime. + * + * libfaketime is free software; you can redistribute it and/or modify it under + * the terms of the GNU General Public License v2 as published by the Free + * Software Foundation. + * + * libfaketime is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License v2 along + * with libfaketime; if not, write to the Free Software Foundation, Inc., + * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef FAKETIME_COMMON_H +#define FAKETIME_COMMON_H + +#include <stdint.h> + +struct system_time_s +{ + /* System time according to CLOCK_REALTIME */ + struct timespec real; + /* System time according to CLOCK_MONOTONIC */ + struct timespec mon; + /* System time according to CLOCK_MONOTONIC_RAW */ + struct timespec mon_raw; +#ifdef CLOCK_BOOTTIME + /* System time according to CLOCK_BOOTTIME */ + struct timespec boot; +#endif +}; + +/* Data shared among faketime-spawned processes */ +struct ft_shared_s +{ + /* + * When advancing time linearly with each time(), etc. call, the calls are + * counted here */ + uint64_t ticks; + /* Index of timstamp to be loaded from file */ + uint64_t file_idx; + /* System time Faketime started at */ + struct system_time_s start_time; +}; + +/* These are all needed in order to properly build on OSX */ +#ifdef __APPLE__ +#include <mach/clock.h> +#include <mach/mach_host.h> +#include <mach/mach_port.h> +#endif + +#endif diff --git a/tests/deckard/contrib/libfaketime/src/libfaketime.c b/tests/deckard/contrib/libfaketime/src/libfaketime.c new file mode 100644 index 0000000..5823701 --- /dev/null +++ b/tests/deckard/contrib/libfaketime/src/libfaketime.c @@ -0,0 +1,2646 @@ +/* + * This file is part of libfaketime, version 0.9.7 + * + * libfaketime is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License v2 as published by the + * Free Software Foundation. + * + * libfaketime is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License v2 along + * with the libfaketime; if not, write to the Free Software Foundation, + * Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +/* + * ======================================================================= + * Global settings, includes, and macros === HEAD + * ======================================================================= + */ + +#define _GNU_SOURCE /* required to get RTLD_NEXT defined */ + +#include <stdio.h> +#include <stdlib.h> +#include <stdint.h> +#include <stdbool.h> +#include <unistd.h> +#include <fcntl.h> +#include <poll.h> +#include <time.h> +#include <math.h> +#include <errno.h> +#include <string.h> +#include <semaphore.h> +#include <sys/mman.h> +#include <sys/stat.h> +#include <sys/types.h> +#include <netinet/in.h> +#include <limits.h> + +#include "uthash.h" + +#include "time_ops.h" +#include "faketime_common.h" + + +/* pthread-handling contributed by David North, TDI in version 0.7 */ +#if defined PTHREAD_SINGLETHREADED_TIME || defined FAKE_PTHREAD +#include <pthread.h> +#endif + +#include <sys/timeb.h> +#include <dlfcn.h> + +#define BUFFERLEN 256 + +#ifndef __APPLE__ +extern char *__progname; +#ifdef __sun +#include "sunos_endian.h" +#else +#include <endian.h> +#endif +#else +/* endianness related macros */ +#ifndef OSSwapHostToBigInt64 +#define OSSwapHostToBigInt64(x) ((uint64_t)(x)) +#endif +#define htobe64(x) OSSwapHostToBigInt64(x) +#ifndef OSSwapHostToLittleInt64 +#define OSSwapHostToLittleInt64(x) OSSwapInt64(x) +#endif +#define htole64(x) OSSwapHostToLittleInt64(x) +#ifndef OSSwapBigToHostInt64 +#define OSSwapBigToHostInt64(x) ((uint64_t)(x)) +#endif +#define be64toh(x) OSSwapBigToHostInt64(x) +#ifndef OSSwapLittleToHostInt64 +#define OSSwapLittleToHostInt64(x) OSSwapInt64(x) +#endif +#define le64toh(x) OSSwapLittleToHostInt64(x) + +/* clock_gettime() and related clock definitions are missing on __APPLE__ */ +#ifndef CLOCK_REALTIME +/* from GNU C Library time.h */ +/* Identifier for system-wide realtime clock. ( == 1) */ +#define CLOCK_REALTIME CALENDAR_CLOCK +/* Monotonic system-wide clock. (== 0) */ +#define CLOCK_MONOTONIC SYSTEM_CLOCK +/* High-resolution timer from the CPU. */ +#define CLOCK_PROCESS_CPUTIME_ID 2 +/* Thread-specific CPU-time clock. */ +#define CLOCK_THREAD_CPUTIME_ID 3 +/* Monotonic system-wide clock, not adjusted for frequency scaling. */ +#define CLOCK_MONOTONIC_RAW 4 +typedef int clockid_t; +#include <mach/clock.h> +#include <mach/mach.h> +#endif +#endif + +/* some systems lack raw clock */ +#ifndef CLOCK_MONOTONIC_RAW +#define CLOCK_MONOTONIC_RAW (CLOCK_MONOTONIC + 1) +#endif + +/* + * Per thread variable, which we turn on inside real_* calls to avoid modifying + * time multiple times of for the whole process to prevent faking time + */ +static __thread bool dont_fake = false; + +/* Wrapper for function calls, which we want to return system time */ +#define DONT_FAKE_TIME(call) \ + { \ + bool dont_fake_orig = dont_fake; \ + if (!dont_fake) \ + { \ + dont_fake = true; \ + } \ + call; \ + dont_fake = dont_fake_orig; \ + } while (0) + +/* pointers to real (not faked) functions */ +static int (*real_stat) (int, const char *, struct stat *); +static int (*real_fstat) (int, int, struct stat *); +static int (*real_fstatat) (int, int, const char *, struct stat *, int); +static int (*real_lstat) (int, const char *, struct stat *); +static int (*real_stat64) (int, const char *, struct stat64 *); +static int (*real_fstat64) (int, int , struct stat64 *); +static int (*real_fstatat64) (int, int , const char *, struct stat64 *, int); +static int (*real_lstat64) (int, const char *, struct stat64 *); +static time_t (*real_time) (time_t *); +static int (*real_ftime) (struct timeb *); +static int (*real_gettimeofday) (struct timeval *, void *); +static int (*real_clock_gettime) (clockid_t clk_id, struct timespec *tp); +#ifdef FAKE_INTERNAL_CALLS +static int (*real___ftime) (struct timeb *); +static int (*real___gettimeofday) (struct timeval *, void *); +static int (*real___clock_gettime) (clockid_t clk_id, struct timespec *tp); +#endif +#ifdef FAKE_PTHREAD +static int (*real_pthread_cond_timedwait_225) (pthread_cond_t *, pthread_mutex_t*, struct timespec *); +static int (*real_pthread_cond_timedwait_232) (pthread_cond_t *, pthread_mutex_t*, struct timespec *); +static int (*real_pthread_cond_init_232) (pthread_cond_t *restrict, const pthread_condattr_t *restrict); +static int (*real_pthread_cond_destroy_232) (pthread_cond_t *); +#endif + +#ifndef __APPLEOSX__ +#ifdef FAKE_TIMERS +static int (*real_timer_settime_22) (int timerid, int flags, const struct itimerspec *new_value, + struct itimerspec * old_value); +static int (*real_timer_settime_233) (timer_t timerid, int flags, + const struct itimerspec *new_value, + struct itimerspec * old_value); +static int (*real_timer_gettime_22) (int timerid, + struct itimerspec *curr_value); +static int (*real_timer_gettime_233) (timer_t timerid, + struct itimerspec *curr_value); +#endif +#endif +#ifdef FAKE_SLEEP +static int (*real_nanosleep) (const struct timespec *req, struct timespec *rem); +static int (*real_usleep) (useconds_t usec); +static unsigned int (*real_sleep) (unsigned int seconds); +static unsigned int (*real_alarm) (unsigned int seconds); +static int (*real_poll) (struct pollfd *, nfds_t, int); +static int (*real_ppoll) (struct pollfd *, nfds_t, const struct timespec *, const sigset_t *); +static int (*real_select) (int nfds, fd_set *restrict readfds, + fd_set *restrict writefds, + fd_set *restrict errorfds, + struct timeval *restrict timeout); +static int (*real_sem_timedwait) (sem_t*, const struct timespec*); +#endif +#ifdef __APPLEOSX__ +static int (*real_clock_get_time) (clock_serv_t clock_serv, mach_timespec_t *cur_timeclockid_t); +static int apple_clock_gettime (clockid_t clk_id, struct timespec *tp); +static clock_serv_t clock_serv_real; +#endif + +static int initialized = 0; + +/* prototypes */ +static int fake_gettimeofday(struct timeval *tv); +static int fake_clock_gettime(clockid_t clk_id, struct timespec *tp); + +/** Semaphore protecting shared data */ +static sem_t *shared_sem = NULL; + +/** Data shared among faketime-spawned processes */ +static struct ft_shared_s *ft_shared = NULL; + +/** Storage format for timestamps written to file. Big endian.*/ +struct saved_timestamp +{ + int64_t sec; + uint64_t nsec; +}; + +static inline void timespec_from_saved (struct timespec *tp, + struct saved_timestamp *saved) +{ + /* read as big endian */ + tp->tv_sec = be64toh(saved->sec); + tp->tv_nsec = be64toh(saved->nsec); +} + +/** Saved timestamps */ +static struct saved_timestamp *stss = NULL; +static size_t infile_size; +static bool infile_set = false; + +/** File fd to save timestamps to */ +static int outfile = -1; + +static bool limited_faking = false; +static long callcounter = 0; +static long ft_start_after_secs = -1; +static long ft_stop_after_secs = -1; +static long ft_start_after_ncalls = -1; +static long ft_stop_after_ncalls = -1; + +static bool spawnsupport = false; +static int spawned = 0; +static char ft_spawn_target[1024]; +static long ft_spawn_secs = -1; +static long ft_spawn_ncalls = -1; + +static int fake_monotonic_clock = 1; +static int cache_enabled = 1; +static int cache_duration = 10; /* cache fake time input for 10 seconds */ + +/* + * Static timespec to store our startup time, followed by a load-time library + * initialization declaration. + */ +#ifndef CLOCK_BOOTTIME +static struct system_time_s ftpl_starttime = {{0, -1}, {0, -1}, {0, -1}}; +#else +static struct system_time_s ftpl_starttime = {{0, -1}, {0, -1}, {0, -1}, {0, -1}}; +#endif + +static char user_faked_time_fmt[BUFSIZ] = {0}; + +/* User supplied base time to fake */ +static struct timespec user_faked_time_timespec = {0, -1}; +/* User supplied base time is set */ +static bool user_faked_time_set = false; +static char user_faked_time_saved[BUFFERLEN] = {0}; + +/* Fractional user offset provided through FAKETIME env. var.*/ +static struct timespec user_offset = {0, -1}; +/* Speed up or slow down clock */ +static double user_rate = 1.0; +static bool user_rate_set = false; +static struct timespec user_per_tick_inc = {0, -1}; +static bool user_per_tick_inc_set = false; + +enum ft_mode_t {FT_FREEZE, FT_START_AT, FT_NOOP} ft_mode = FT_FREEZE; + +/* Time to fake is not provided through FAKETIME env. var. */ +static bool parse_config_file = true; + +static void ft_cleanup (void) __attribute__ ((destructor)); +static void ftpl_init (void) __attribute__ ((constructor)); + + +/* + * ======================================================================= + * Shared memory related functions === SHM + * ======================================================================= + */ + +static void ft_shm_init (void) +{ + int ticks_shm_fd; + char sem_name[256], shm_name[256], *ft_shared_env = getenv("FAKETIME_SHARED"); + + if (ft_shared_env != NULL) + { + if (sscanf(ft_shared_env, "%255s %255s", sem_name, shm_name) < 2) + { + printf("Error parsing semaphore name and shared memory id from string: %s", ft_shared_env); + exit(1); + } + + if (SEM_FAILED == (shared_sem = sem_open(sem_name, 0))) + { + perror("sem_open"); + exit(1); + } + + if (-1 == (ticks_shm_fd = shm_open(shm_name, O_CREAT|O_RDWR, S_IWUSR|S_IRUSR))) + { + perror("shm_open"); + exit(1); + } + + if (MAP_FAILED == (ft_shared = mmap(NULL, sizeof(struct ft_shared_s), PROT_READ|PROT_WRITE, + MAP_SHARED, ticks_shm_fd, 0))) + { + perror("mmap"); + exit(1); + } + } +} + +static void ft_cleanup (void) +{ + /* detach from shared memory */ + if (ft_shared != NULL) + { + munmap(ft_shared, sizeof(uint64_t)); + } + if (stss != NULL) + { + munmap(stss, infile_size); + } + if (shared_sem != NULL) + { + sem_close(shared_sem); + } +} + + +/* + * ======================================================================= + * Internal time retrieval === INTTIME + * ======================================================================= + */ + +/* Get system time from system for all clocks */ +static void system_time_from_system (struct system_time_s * systime) +{ +#ifdef __APPLEOSX__ + /* from http://stackoverflow.com/questions/5167269/clock-gettime-alternative-in-mac-os-x */ + clock_serv_t cclock; + mach_timespec_t mts; + host_get_clock_service(mach_host_self(), CALENDAR_CLOCK, &clock_serv_real); + (*real_clock_get_time)(clock_serv_real, &mts); + systime->real.tv_sec = mts.tv_sec; + systime->real.tv_nsec = mts.tv_nsec; + host_get_clock_service(mach_host_self(), SYSTEM_CLOCK, &cclock); + (*real_clock_get_time)(cclock, &mts); + mach_port_deallocate(mach_task_self(), cclock); + systime->mon.tv_sec = mts.tv_sec; + systime->mon.tv_nsec = mts.tv_nsec; + systime->mon_raw.tv_sec = mts.tv_sec; + systime->mon_raw.tv_nsec = mts.tv_nsec; +#else + DONT_FAKE_TIME((*real_clock_gettime)(CLOCK_REALTIME, &systime->real)) + ; + DONT_FAKE_TIME((*real_clock_gettime)(CLOCK_MONOTONIC, &systime->mon)) + ; + DONT_FAKE_TIME((*real_clock_gettime)(CLOCK_MONOTONIC_RAW, &systime->mon_raw)) + ; +#ifdef CLOCK_BOOTTIME + DONT_FAKE_TIME((*real_clock_gettime)(CLOCK_BOOTTIME, &systime->boot)) + ; +#endif +#endif +} + +static void next_time(struct timespec *tp, struct timespec *ticklen) +{ + if (shared_sem != NULL) + { + struct timespec inc; + /* lock */ + if (sem_wait(shared_sem) == -1) + { + perror("sem_wait"); + exit(1); + } + /* calculate and update elapsed time */ + timespecmul(ticklen, ft_shared->ticks, &inc); + timespecadd(&user_faked_time_timespec, &inc, tp); + (ft_shared->ticks)++; + /* unlock */ + if (sem_post(shared_sem) == -1) + { + perror("sem_post"); + exit(1); + } + } +} + + +/* + * ======================================================================= + * Saving & loading time === SAVE + * ======================================================================= + */ + +static void save_time(struct timespec *tp) +{ + if ((shared_sem != NULL) && (outfile != -1)) + { + struct saved_timestamp time_write; + ssize_t written; + size_t n = 0; + + time_write.sec = htobe64(tp->tv_sec); + time_write.nsec = htobe64(tp->tv_nsec); + + /* lock */ + if (sem_wait(shared_sem) == -1) + { + perror("sem_wait"); + exit(1); + } + + lseek(outfile, 0, SEEK_END); + do + { + written = write(outfile, &(((char*)&time_write)[n]), sizeof(time_write) - n); + } + while (((written == -1) && (errno == EINTR)) || + (sizeof(time_write) < (n += written))); + + if ((written == -1) || (n < sizeof(time_write))) + { + perror("Saving timestamp to file failed"); + } + + /* unlock */ + if (sem_post(shared_sem) == -1) + { + perror("sem_post"); + exit(1); + } + } +} + +/* + * Provide faked time from file. + * @return time is set from filen + */ +static bool load_time(struct timespec *tp) +{ + bool ret = false; + if ((shared_sem != NULL) && (infile_set)) + { + /* lock */ + if (sem_wait(shared_sem) == -1) + { + perror("sem_wait"); + exit(1); + } + + if ((sizeof(stss[0]) * (ft_shared->file_idx + 1)) > infile_size) + { + /* we are out of timstamps to replay, return to faking time by rules + * using last timestamp from file as the user provided timestamp */ + timespec_from_saved(&user_faked_time_timespec, &stss[(infile_size / sizeof(stss[0])) - 1 ]); + + if (ft_shared->ticks == 0) + { + /* we set shared memory to stop using infile */ + ft_shared->ticks = 1; + system_time_from_system(&ftpl_starttime); + ft_shared->start_time = ftpl_starttime; + } + else + { + ftpl_starttime = ft_shared->start_time; + } + + munmap(stss, infile_size); + infile_set = false; + } + else + { + timespec_from_saved(tp, &stss[ft_shared->file_idx]); + ft_shared->file_idx++; + ret = true; + } + + /* unlock */ + if (sem_post(shared_sem) == -1) + { + perror("sem_post"); + exit(1); + } + } + return ret; +} + + +/* + * ======================================================================= + * Faked system functions: file related === FAKE(FILE) + * ======================================================================= + */ + +#ifdef FAKE_STAT + +#ifndef NO_ATFILE +#ifndef _ATFILE_SOURCE +#define _ATFILE_SOURCE +#endif +#include <fcntl.h> /* Definition of AT_* constants */ +#endif + +#include <sys/stat.h> + +static int fake_stat_disabled = 0; + +#define FAKE_STRUCT_STAT_TIME(which) { \ + struct timespec t = {buf->st_##which##time, \ + buf->st_##which##timensec}; \ + fake_clock_gettime(CLOCK_REALTIME, &t); \ + buf->st_##which##time = t.tv_sec; \ + buf->st_##which##timensec = t.tv_nsec; \ + } while (0) + +static inline void fake_statbuf (struct stat *buf) { +#ifndef st_atime + FAKE_STRUCT_STAT_TIME(c); + FAKE_STRUCT_STAT_TIME(a); + FAKE_STRUCT_STAT_TIME(m); +#else + fake_clock_gettime(CLOCK_REALTIME, &buf->st_ctim); + fake_clock_gettime(CLOCK_REALTIME, &buf->st_atim); + fake_clock_gettime(CLOCK_REALTIME, &buf->st_mtim); +#endif +} + +static inline void fake_stat64buf (struct stat64 *buf) { +#ifndef st_atime + FAKE_STRUCT_STAT_TIME(c); + FAKE_STRUCT_STAT_TIME(a); + FAKE_STRUCT_STAT_TIME(m); +#else + fake_clock_gettime(CLOCK_REALTIME, &buf->st_ctim); + fake_clock_gettime(CLOCK_REALTIME, &buf->st_atim); + fake_clock_gettime(CLOCK_REALTIME, &buf->st_mtim); +#endif +} + +/* Contributed by Philipp Hachtmann in version 0.6 */ +int __xstat (int ver, const char *path, struct stat *buf) +{ + if (!initialized) + { + ftpl_init(); + } + if (NULL == real_stat) + { /* dlsym() failed */ +#ifdef DEBUG + (void) fprintf(stderr, "faketime problem: original stat() not found.\n"); +#endif + return -1; /* propagate error to caller */ + } + + int result; + DONT_FAKE_TIME(result = real_stat(ver, path, buf)); + if (result == -1) + { + return -1; + } + + if (buf != NULL) + { + if (!fake_stat_disabled) + { + fake_statbuf(buf); + } + } + + return result; +} + +/* Contributed by Philipp Hachtmann in version 0.6 */ +int __fxstat (int ver, int fildes, struct stat *buf) +{ + if (!initialized) + { + ftpl_init(); + } + if (NULL == real_fstat) + { /* dlsym() failed */ +#ifdef DEBUG + (void) fprintf(stderr, "faketime problem: original fstat() not found.\n"); +#endif + return -1; /* propagate error to caller */ + } + + int result; + DONT_FAKE_TIME(result = real_fstat(ver, fildes, buf)); + if (result == -1) + { + return -1; + } + + if (buf != NULL) + { + if (!fake_stat_disabled) + { + fake_statbuf(buf); + } + } + return result; +} + +/* Added in v0.8 as suggested by Daniel Kahn Gillmor */ +#ifndef NO_ATFILE +int __fxstatat(int ver, int fildes, const char *filename, struct stat *buf, int flag) +{ + if (!initialized) + { + ftpl_init(); + } + if (NULL == real_fstatat) + { /* dlsym() failed */ +#ifdef DEBUG + (void) fprintf(stderr, "faketime problem: original fstatat() not found.\n"); +#endif + return -1; /* propagate error to caller */ + } + + int result; + DONT_FAKE_TIME(result = real_fstatat(ver, fildes, filename, buf, flag)); + if (result == -1) + { + return -1; + } + + if (buf != NULL) + { + if (!fake_stat_disabled) + { + fake_statbuf(buf); + } + } + return result; +} +#endif + +/* Contributed by Philipp Hachtmann in version 0.6 */ +int __lxstat (int ver, const char *path, struct stat *buf) +{ + if (!initialized) + { + ftpl_init(); + } + if (NULL == real_lstat) + { /* dlsym() failed */ +#ifdef DEBUG + (void) fprintf(stderr, "faketime problem: original lstat() not found.\n"); +#endif + return -1; /* propagate error to caller */ + } + + int result; + DONT_FAKE_TIME(result = real_lstat(ver, path, buf)); + if (result == -1) + { + return -1; + } + + if (buf != NULL) + { + if (!fake_stat_disabled) + { + fake_statbuf(buf); + } + } + return result; +} + +/* Contributed by Philipp Hachtmann in version 0.6 */ +int __xstat64 (int ver, const char *path, struct stat64 *buf) +{ + if (!initialized) + { + ftpl_init(); + } + if (NULL == real_stat64) + { /* dlsym() failed */ +#ifdef DEBUG + (void) fprintf(stderr, "faketime problem: original stat() not found.\n"); +#endif + return -1; /* propagate error to caller */ + } + + int result; + DONT_FAKE_TIME(result = real_stat64(ver, path, buf)); + if (result == -1) + { + return -1; + } + + if (buf != NULL) + { + if (!fake_stat_disabled) + { + fake_stat64buf(buf); + } + } + return result; +} + +/* Contributed by Philipp Hachtmann in version 0.6 */ +int __fxstat64 (int ver, int fildes, struct stat64 *buf) +{ + if (!initialized) + { + ftpl_init(); + } + if (NULL == real_fstat64) + { /* dlsym() failed */ +#ifdef DEBUG + (void) fprintf(stderr, "faketime problem: original fstat() not found.\n"); +#endif + return -1; /* propagate error to caller */ + } + + int result; + DONT_FAKE_TIME(result = real_fstat64(ver, fildes, buf)); + if (result == -1) + { + return -1; + } + + if (buf != NULL) + { + if (!fake_stat_disabled) + { + fake_stat64buf(buf); + } + } + return result; +} + +/* Added in v0.8 as suggested by Daniel Kahn Gillmor */ +#ifndef NO_ATFILE +int __fxstatat64 (int ver, int fildes, const char *filename, struct stat64 *buf, int flag) +{ + if (!initialized) + { + ftpl_init(); + } + if (NULL == real_fstatat64) + { /* dlsym() failed */ +#ifdef DEBUG + (void) fprintf(stderr, "faketime problem: original fstatat64() not found.\n"); +#endif + return -1; /* propagate error to caller */ + } + + int result; + DONT_FAKE_TIME(result = real_fstatat64(ver, fildes, filename, buf, flag)); + if (result == -1) + { + return -1; + } + + if (buf != NULL) + { + if (!fake_stat_disabled) + { + fake_stat64buf(buf); + } + } + return result; +} +#endif + +/* Contributed by Philipp Hachtmann in version 0.6 */ +int __lxstat64 (int ver, const char *path, struct stat64 *buf) +{ + if (!initialized) + { + ftpl_init(); + } + if (NULL == real_lstat64) + { /* dlsym() failed */ +#ifdef DEBUG + (void) fprintf(stderr, "faketime problem: original lstat() not found.\n"); +#endif + return -1; /* propagate error to caller */ + } + + int result; + DONT_FAKE_TIME(result = real_lstat64(ver, path, buf)); + if (result == -1) + { + return -1; + } + + if (buf != NULL) + { + if (!fake_stat_disabled) + { + fake_stat64buf(buf); + } + } + return result; +} +#endif + +/* + * ======================================================================= + * Faked system functions: sleep/alarm/poll/timer related === FAKE(SLEEP) + * ======================================================================= + * Contributed by Balint Reczey in v0.9.5 + */ + +#ifdef FAKE_SLEEP +/* + * Faked nanosleep() + */ +int nanosleep(const struct timespec *req, struct timespec *rem) +{ + int result; + struct timespec real_req; + + if (!initialized) + { + ftpl_init(); + } + if (real_nanosleep == NULL) + { + return -1; + } + if (req != NULL) + { + if (user_rate_set && !dont_fake) + { + timespecmul(req, 1.0 / user_rate, &real_req); + } + else + { + real_req = *req; + } + } + else + { + return -1; + } + + DONT_FAKE_TIME(result = (*real_nanosleep)(&real_req, rem)); + if (result == -1) + { + return result; + } + + /* fake returned parts */ + if ((rem != NULL) && ((rem->tv_sec != 0) || (rem->tv_nsec != 0))) + { + if (user_rate_set && !dont_fake) + { + timespecmul(rem, user_rate, rem); + } + } + /* return the result to the caller */ + return result; +} + +/* + * Faked usleep() + */ +int usleep(useconds_t usec) +{ + int result; + + if (!initialized) + { + ftpl_init(); + } + if (user_rate_set && !dont_fake) + { + struct timespec real_req; + + if (real_nanosleep == NULL) + { + /* fall back to usleep() */ + if (real_usleep == NULL) + { + return -1; + } + DONT_FAKE_TIME(result = (*real_usleep)((1.0 / user_rate) * usec)); + return result; + } + + real_req.tv_sec = usec / 1000000; + real_req.tv_nsec = (usec % 1000000) * 1000; + timespecmul(&real_req, 1.0 / user_rate, &real_req); + DONT_FAKE_TIME(result = (*real_nanosleep)(&real_req, NULL)); + } + else + { + DONT_FAKE_TIME(result = (*real_usleep)(usec)); + } + return result; +} + +/* + * Faked sleep() + */ +unsigned int sleep(unsigned int seconds) +{ + if (!initialized) + { + ftpl_init(); + } + if (user_rate_set && !dont_fake) + { + if (real_nanosleep == NULL) + { + /* fall back to sleep */ + unsigned int ret; + if (real_sleep == NULL) + { + return 0; + } + DONT_FAKE_TIME(ret = (*real_sleep)((1.0 / user_rate) * seconds)); + return (user_rate_set && !dont_fake)?(user_rate * ret):ret; + } + else + { + int result; + struct timespec real_req = {seconds, 0}, rem; + timespecmul(&real_req, 1.0 / user_rate, &real_req); + DONT_FAKE_TIME(result = (*real_nanosleep)(&real_req, &rem)); + if (result == -1) + { + return 0; + } + + /* fake returned parts */ + if ((rem.tv_sec != 0) || (rem.tv_nsec != 0)) + { + timespecmul(&rem, user_rate, &rem); + } + /* return the result to the caller */ + return rem.tv_sec; + } + } + else + { + /* no need to fake anything */ + unsigned int ret; + DONT_FAKE_TIME(ret = (*real_sleep)(seconds)); + return ret; + } +} + +/* + * Faked alarm() + * @note due to rounding alarm(2) with faketime -f '+0 x7' won't wait 2/7 + * wall clock seconds but 0 seconds + */ +unsigned int alarm(unsigned int seconds) +{ + unsigned int ret; + unsigned int seconds_real = (user_rate_set && !dont_fake)?((1.0 / user_rate) * seconds):seconds; + + if (!initialized) + { + ftpl_init(); + } + if (real_alarm == NULL) + { + return -1; + } + + DONT_FAKE_TIME(ret = (*real_alarm)(seconds_real)); + return (user_rate_set && !dont_fake)?(user_rate * ret):ret; +} + +/* + * Faked ppoll() + */ +int ppoll(struct pollfd *fds, nfds_t nfds, + const struct timespec *timeout_ts, const sigset_t *sigmask) +{ + struct timespec real_timeout, *real_timeout_pt; + int ret; + + if (!initialized) + { + ftpl_init(); + } + if (real_ppoll == NULL) + { + return -1; + } + if (timeout_ts != NULL) + { + if (user_rate_set && !dont_fake && (timeout_ts->tv_sec > 0)) + { + timespecmul(timeout_ts, 1.0 / user_rate, &real_timeout); + real_timeout_pt = &real_timeout; + } + else + { + /* cast away constness */ + real_timeout_pt = (struct timespec *)timeout_ts; + } + } + else + { + real_timeout_pt = NULL; + } + + DONT_FAKE_TIME(ret = (*real_ppoll)(fds, nfds, real_timeout_pt, sigmask)); + return ret; +} + +/* + * Faked poll() + */ +int poll(struct pollfd *fds, nfds_t nfds, int timeout) +{ + int ret, timeout_real = (user_rate_set && !dont_fake && (timeout > 0))?(timeout / user_rate):timeout; + + if (!initialized) + { + ftpl_init(); + } + if (real_poll == NULL) + { + return -1; + } + + DONT_FAKE_TIME(ret = (*real_poll)(fds, nfds, timeout_real)); + return ret; +} + +/* + * Faked select() + */ +int select(int nfds, fd_set *readfds, + fd_set *writefds, + fd_set *errorfds, + struct timeval *timeout) +{ + int ret; + struct timeval timeout_real; + + if (!initialized) + { + ftpl_init(); + } + + if (real_select == NULL) + { + return -1; + } + + if (timeout != NULL) + { + if (user_rate_set && !dont_fake && (timeout->tv_sec > 0 || timeout->tv_usec > 0)) + { + struct timespec ts; + + ts.tv_sec = timeout->tv_sec; + ts.tv_nsec = timeout->tv_usec * 1000; + + timespecmul(&ts, 1.0 / user_rate, &ts); + + timeout_real.tv_sec = ts.tv_sec; + timeout_real.tv_usec = ts.tv_nsec / 1000; + } + else + { + timeout_real.tv_sec = timeout->tv_sec; + timeout_real.tv_usec = timeout->tv_usec; + } + } + + DONT_FAKE_TIME(ret = (*real_select)(nfds, readfds, writefds, errorfds, timeout == NULL ? timeout : &timeout_real)); + return ret; +} + +int sem_timedwait(sem_t *sem, const struct timespec *abs_timeout) +{ + int result; + struct timespec real_abs_timeout, *real_abs_timeout_pt; + + /* sanity check */ + if (abs_timeout == NULL) + { + return -1; + } + + if (NULL == real_sem_timedwait) + { /* dlsym() failed */ +#ifdef DEBUG + (void) fprintf(stderr, "faketime problem: original sem_timedwait() not found.\n"); +#endif + return -1; /* propagate error to caller */ + } + + if (!dont_fake) + { + struct timespec tdiff, timeadj; + + timespecsub(abs_timeout, &user_faked_time_timespec, &tdiff); + + if (user_rate_set) + { + timespecmul(&tdiff, user_rate, &timeadj); + } + else + { + timeadj = tdiff; + } + timespecadd(&ftpl_starttime.real, &timeadj, &real_abs_timeout); + real_abs_timeout_pt = &real_abs_timeout; + } + else + { + /* cast away constness */ + real_abs_timeout_pt = (struct timespec *)abs_timeout; + } + + DONT_FAKE_TIME(result = (*real_sem_timedwait)(sem, real_abs_timeout_pt)); + return result; +} +#endif + +#ifndef __APPLE__ +#ifdef FAKE_TIMERS + +/* timer related functions and structures */ +typedef union { + int int_member; + timer_t timer_t_member; +} timer_t_or_int; + +/* + * Faketime's function implementation's compatibility mode + */ +typedef enum {FT_COMPAT_GLIBC_2_2, FT_COMPAT_GLIBC_2_3_3} ft_lib_compat_timer; + + +/* + * Faked timer_settime() + * Does not affect timer speed when stepping clock with each time() call. + */ +static int +timer_settime_common(timer_t_or_int timerid, int flags, + const struct itimerspec *new_value, + struct itimerspec *old_value, ft_lib_compat_timer compat) +{ + int result; + struct itimerspec new_real; + struct itimerspec *new_real_pt = &new_real; + + if (!initialized) + { + ftpl_init(); + } + if (new_value == NULL) + { + new_real_pt = NULL; + } + else if (dont_fake) + { + /* cast away constness*/ + new_real_pt = (struct itimerspec *)new_value; + } + else + { + /* set it_value */ + if ((new_value->it_value.tv_sec != 0) || + (new_value->it_value.tv_nsec != 0)) + { + if (flags & TIMER_ABSTIME) + { + struct timespec tdiff, timeadj; + timespecsub(&new_value->it_value, &user_faked_time_timespec, &timeadj); + if (user_rate_set) + { + timespecmul(&timeadj, 1.0/user_rate, &tdiff); + } + else + { + tdiff = timeadj; + } + /* only CLOCK_REALTIME is handled */ + timespecadd(&ftpl_starttime.real, &tdiff, &new_real.it_value); + } + else + { + if (user_rate_set) + { + timespecmul(&new_value->it_value, 1.0/user_rate, &new_real.it_value); + } + else + { + new_real.it_value = new_value->it_value; + } + } + } + else + { + new_real.it_value = new_value->it_value; + } + /* set it_interval */ + if (user_rate_set && ((new_value->it_interval.tv_sec != 0) || + (new_value->it_interval.tv_nsec != 0))) + { + timespecmul(&new_value->it_interval, 1.0/user_rate, &new_real.it_interval); + } + else + { + new_real.it_interval = new_value->it_interval; + } + } + + switch (compat) + { + case FT_COMPAT_GLIBC_2_2: + DONT_FAKE_TIME(result = (*real_timer_settime_22)(timerid.int_member, flags, + new_real_pt, old_value)); + break; + case FT_COMPAT_GLIBC_2_3_3: + DONT_FAKE_TIME(result = (*real_timer_settime_233)(timerid.timer_t_member, + flags, new_real_pt, old_value)); + break; + default: + result = -1; + break; + } + + if (result == -1) + { + return result; + } + + /* fake returned parts */ + if ((old_value != NULL) && !dont_fake) + { + if ((old_value->it_value.tv_sec != 0) || + (old_value->it_value.tv_nsec != 0)) + { + result = fake_clock_gettime(CLOCK_REALTIME, &old_value->it_value); + } + if (user_rate_set && ((old_value->it_interval.tv_sec != 0) || + (old_value->it_interval.tv_nsec != 0))) + { + timespecmul(&old_value->it_interval, user_rate, &old_value->it_interval); + } + } + + /* return the result to the caller */ + return result; +} + +/* + * Faked timer_settime() compatible with implementation in GLIBC 2.2 + */ +int timer_settime_22(int timerid, int flags, + const struct itimerspec *new_value, + struct itimerspec *old_value) +{ + if (!initialized) + { + ftpl_init(); + } + if (real_timer_settime_22 == NULL) + { + return -1; + } + else + { + return (timer_settime_common((timer_t_or_int)timerid, flags, new_value, old_value, + FT_COMPAT_GLIBC_2_2)); + } +} + +/* + * Faked timer_settime() compatible with implementation in GLIBC 2.3.3 + */ +int timer_settime_233(timer_t timerid, int flags, + const struct itimerspec *new_value, + struct itimerspec *old_value) +{ + if (!initialized) + { + ftpl_init(); + } + if (real_timer_settime_233 == NULL) + { + return -1; + } + else + { + return (timer_settime_common((timer_t_or_int)timerid, flags, new_value, old_value, + FT_COMPAT_GLIBC_2_3_3)); + } +} + +/* + * Faked timer_gettime() + * Does not affect timer speed when stepping clock with each time() call. + */ +int timer_gettime_common(timer_t_or_int timerid, struct itimerspec *curr_value, ft_lib_compat_timer compat) +{ + int result; + + if (!initialized) + { + ftpl_init(); + } + if (real_timer_gettime_233 == NULL) + { + return -1; + } + + switch (compat) + { + case FT_COMPAT_GLIBC_2_2: + DONT_FAKE_TIME(result = (*real_timer_gettime_22)(timerid.int_member, curr_value)); + break; + case FT_COMPAT_GLIBC_2_3_3: + DONT_FAKE_TIME(result = (*real_timer_gettime_233)(timerid.timer_t_member, curr_value)); + break; + default: + result = -1; + break; + } + + if (result == -1) + { + return result; + } + + /* fake returned parts */ + if (curr_value != NULL) + { + if (user_rate_set && !dont_fake) + { + timespecmul(&curr_value->it_interval, user_rate, &curr_value->it_interval); + timespecmul(&curr_value->it_value, user_rate, &curr_value->it_value); + } + } + /* return the result to the caller */ + return result; +} + +/* + * Faked timer_gettime() compatible with implementation in GLIBC 2.2 + */ +int timer_gettime_22(timer_t timerid, struct itimerspec *curr_value) +{ + if (!initialized) + { + ftpl_init(); + } + if (real_timer_gettime_22 == NULL) + { + return -1; + } + else + { + return (timer_gettime_common((timer_t_or_int)timerid, curr_value, + FT_COMPAT_GLIBC_2_2)); + } +} + +/* + * Faked timer_gettime() compatible with implementation in GLIBC 2.3.3 + */ +int timer_gettime_233(timer_t timerid, struct itimerspec *curr_value) +{ + if (!initialized) + { + ftpl_init(); + } + if (real_timer_gettime_233 == NULL) + { + return -1; + } + else + { + return (timer_gettime_common((timer_t_or_int)timerid, curr_value, + FT_COMPAT_GLIBC_2_3_3)); + } +} + +__asm__(".symver timer_gettime_22, timer_gettime@GLIBC_2.2"); +__asm__(".symver timer_gettime_233, timer_gettime@@GLIBC_2.3.3"); +__asm__(".symver timer_settime_22, timer_settime@GLIBC_2.2"); +__asm__(".symver timer_settime_233, timer_settime@@GLIBC_2.3.3"); + +#endif +#endif + + +/* + * ======================================================================= + * Faked system functions: basic time functions === FAKE(TIME) + * ======================================================================= + */ + +/* + * time() implementation using clock_gettime() + * @note Does not check for EFAULT, see man 2 time + */ +time_t time(time_t *time_tptr) +{ + struct timespec tp; + time_t result; + + if (!initialized) + { + ftpl_init(); + } + DONT_FAKE_TIME(result = (*real_clock_gettime)(CLOCK_REALTIME, &tp)); + if (result == -1) return -1; + + /* pass the real current time to our faking version, overwriting it */ + (void)fake_clock_gettime(CLOCK_REALTIME, &tp); + + if (time_tptr != NULL) + { + *time_tptr = tp.tv_sec; + } + return tp.tv_sec; +} + +int ftime(struct timeb *tb) +{ + struct timespec tp; + int result; + + if (!initialized) + { + ftpl_init(); + } + /* sanity check */ + if (tb == NULL) + return 0; /* ftime() always returns 0, see manpage */ + + /* Check whether we've got a pointer to the real ftime() function yet */ + if (NULL == real_ftime) + { /* dlsym() failed */ +#ifdef DEBUG + (void) fprintf(stderr, "faketime problem: original ftime() not found.\n"); +#endif + return 0; /* propagate error to caller */ + } + + /* initialize our TZ result with the real current time */ + DONT_FAKE_TIME(result = (*real_ftime)(tb)); + if (result == -1) + { + return result; + } + + DONT_FAKE_TIME(result = (*real_clock_gettime)(CLOCK_REALTIME, &tp)); + if (result == -1) return -1; + + /* pass the real current time to our faking version, overwriting it */ + (void)fake_clock_gettime(CLOCK_REALTIME, &tp); + + tb->time = tp.tv_sec; + tb->millitm = tp.tv_nsec / 1000000; + + /* return the result to the caller */ + return result; /* will always be 0 (see manpage) */ +} + +int gettimeofday(struct timeval *tv, void *tz) +{ + int result; + + if (!initialized) + { + ftpl_init(); + } + /* sanity check */ + if (tv == NULL) + { + return -1; + } + + /* Check whether we've got a pointer to the real ftime() function yet */ + if (NULL == real_gettimeofday) + { /* dlsym() failed */ +#ifdef DEBUG + (void) fprintf(stderr, "faketime problem: original gettimeofday() not found.\n"); +#endif + return -1; /* propagate error to caller */ + } + + /* initialize our result with the real current time */ + DONT_FAKE_TIME(result = (*real_gettimeofday)(tv, tz)); + if (result == -1) return result; /* original function failed */ + + /* pass the real current time to our faking version, overwriting it */ + result = fake_gettimeofday(tv); + + /* return the result to the caller */ + return result; +} + +int clock_gettime(clockid_t clk_id, struct timespec *tp) +{ + int result; + + if (!initialized) + { + ftpl_init(); + } + /* sanity check */ + if (tp == NULL) + { + return -1; + } + + if (NULL == real_clock_gettime) + { /* dlsym() failed */ +#ifdef DEBUG + (void) fprintf(stderr, "faketime problem: original clock_gettime() not found.\n"); +#endif + return -1; /* propagate error to caller */ + } + + /* initialize our result with the real current time */ + DONT_FAKE_TIME(result = (*real_clock_gettime)(clk_id, tp)); + if (result == -1) return result; /* original function failed */ + + /* pass the real current time to our faking version, overwriting it */ + if (fake_monotonic_clock || (clk_id != CLOCK_MONOTONIC && clk_id != CLOCK_MONOTONIC_RAW +#ifdef CLOCK_MONOTONIC_COARSE + && clk_id != CLOCK_MONOTONIC_COARSE +#endif +#ifdef CLOCK_BOOTTIME + && clk_id != CLOCK_BOOTTIME +#endif + )) + { + result = fake_clock_gettime(clk_id, tp); + } + + /* return the result to the caller */ + return result; +} + + +/* + * ======================================================================= + * Parsing the user's faketime requests === PARSE + * ======================================================================= + */ + +static void parse_ft_string(const char *user_faked_time) +{ + struct tm user_faked_time_tm; + char * tmp_time_fmt; + + if (!strncmp(user_faked_time, user_faked_time_saved, BUFFERLEN)) + { + /* No change */ + return; + } + + /* check whether the user gave us an absolute time to fake */ + switch (user_faked_time[0]) + { + + default: /* Try and interpret this as a specified time */ + if (ft_mode != FT_NOOP) ft_mode = FT_FREEZE; + user_faked_time_tm.tm_isdst = -1; + if (NULL != strptime(user_faked_time, user_faked_time_fmt, &user_faked_time_tm)) + { + user_faked_time_timespec.tv_sec = mktime(&user_faked_time_tm); + user_faked_time_timespec.tv_nsec = 0; + user_faked_time_set = true; + } + else + { + perror("Failed to parse FAKETIME timestamp"); + fprintf(stderr, "Please check specification %s with format %s\n", user_faked_time, user_faked_time_fmt); + exit(EXIT_FAILURE); + } + break; + + case '+': + case '-': /* User-specified offset */ + if (ft_mode != FT_NOOP) ft_mode = FT_START_AT; + /* fractional time offsets contributed by Karl Chen in v0.8 */ + double frac_offset = atof(user_faked_time); + + /* offset is in seconds by default, but the string may contain + * multipliers... + */ + if (strchr(user_faked_time, 'm') != NULL) frac_offset *= 60; + else if (strchr(user_faked_time, 'h') != NULL) frac_offset *= 60 * 60; + else if (strchr(user_faked_time, 'd') != NULL) frac_offset *= 60 * 60 * 24; + else if (strchr(user_faked_time, 'y') != NULL) frac_offset *= 60 * 60 * 24 * 365; + + user_offset.tv_sec = floor(frac_offset); + user_offset.tv_nsec = (frac_offset - user_offset.tv_sec) * SEC_TO_nSEC; + timespecadd(&ftpl_starttime.real, &user_offset, &user_faked_time_timespec); + goto parse_modifiers; + break; + + /* Contributed by David North, TDI in version 0.7 */ + case '@': /* Specific time, but clock along relative to that starttime */ + ft_mode = FT_START_AT; + user_faked_time_tm.tm_isdst = -1; + (void) strptime(&user_faked_time[1], user_faked_time_fmt, &user_faked_time_tm); + + user_faked_time_timespec.tv_sec = mktime(&user_faked_time_tm); + user_faked_time_timespec.tv_nsec = 0; + + /* Reset starttime */ + system_time_from_system(&ftpl_starttime); + goto parse_modifiers; + break; + + case 'i': + case 'x': /* Only modifiers are passed, don't fall back to strptime */ +parse_modifiers: + /* Speed-up / slow-down contributed by Karl Chen in v0.8 */ + if (strchr(user_faked_time, 'x') != NULL) + { + user_rate = atof(strchr(user_faked_time, 'x')+1); + user_rate_set = true; + } + else if (NULL != (tmp_time_fmt = strchr(user_faked_time, 'i'))) + { + double tick_inc = atof(tmp_time_fmt + 1); + /* increment time with every time() call*/ + user_per_tick_inc.tv_sec = floor(tick_inc); + user_per_tick_inc.tv_nsec = (tick_inc - user_per_tick_inc.tv_sec) * SEC_TO_nSEC ; + user_per_tick_inc_set = true; + } + break; + } // end of switch + + strncpy(user_faked_time_saved, user_faked_time, BUFFERLEN-1); + user_faked_time_saved[BUFFERLEN-1] = 0; +#ifdef DEBUG + fprintf(stderr, "new FAKETIME: %s\n", user_faked_time_saved); +#endif +} + + +/* + * ======================================================================= + * Initialization === INIT + * ======================================================================= + */ + +static void ftpl_init(void) +{ + char *tmp_env; + bool dont_fake_final; + +#ifdef __APPLE__ + const char *progname = getprogname(); +#else + const char *progname = __progname; +#endif + + /* Look up all real_* functions. NULL will mark missing ones. */ + real_stat = dlsym(RTLD_NEXT, "__xstat"); + real_fstat = dlsym(RTLD_NEXT, "__fxstat"); + real_fstatat = dlsym(RTLD_NEXT, "__fxstatat"); + real_lstat = dlsym(RTLD_NEXT, "__lxstat"); + real_stat64 = dlsym(RTLD_NEXT,"__xstat64"); + real_fstat64 = dlsym(RTLD_NEXT, "__fxstat64"); + real_fstatat64 = dlsym(RTLD_NEXT, "__fxstatat64"); + real_lstat64 = dlsym(RTLD_NEXT, "__lxstat64"); + real_time = dlsym(RTLD_NEXT, "time"); + real_ftime = dlsym(RTLD_NEXT, "ftime"); +#if defined(__alpha__) && defined(__GLIBC__) + real_gettimeofday = dlvsym(RTLD_NEXT, "gettimeofday", "GLIBC_2.1"); +#else + real_gettimeofday = dlsym(RTLD_NEXT, "gettimeofday"); +#endif +#ifdef FAKE_SLEEP + real_nanosleep = dlsym(RTLD_NEXT, "nanosleep"); + real_usleep = dlsym(RTLD_NEXT, "usleep"); + real_sleep = dlsym(RTLD_NEXT, "sleep"); + real_alarm = dlsym(RTLD_NEXT, "alarm"); + real_poll = dlsym(RTLD_NEXT, "poll"); + real_ppoll = dlsym(RTLD_NEXT, "ppoll"); + real_select = dlsym(RTLD_NEXT, "select"); + real_sem_timedwait = dlsym(RTLD_NEXT, "sem_timedwait"); +#endif +#ifdef FAKE_INTERNAL_CALLS + real___ftime = dlsym(RTLD_NEXT, "__ftime"); +# if defined(__alpha__) && defined(__GLIBC__) + real___gettimeofday = dlvsym(RTLD_NEXT, "__gettimeofday", "GLIBC_2.1"); +# else + real___gettimeofday = dlsym(RTLD_NEXT, "__gettimeofday"); +# endif + real___clock_gettime = dlsym(RTLD_NEXT, "__clock_gettime"); +#endif +#ifdef FAKE_PTHREAD + +#ifdef __GLIBC__ + real_pthread_cond_timedwait_225 = dlvsym(RTLD_NEXT, "pthread_cond_timedwait", "GLIBC_2.2.5"); + + real_pthread_cond_timedwait_232 = dlvsym(RTLD_NEXT, "pthread_cond_timedwait", "GLIBC_2.3.2"); + real_pthread_cond_init_232 = dlvsym(RTLD_NEXT, "pthread_cond_init", "GLIBC_2.3.2"); + real_pthread_cond_destroy_232 = dlvsym(RTLD_NEXT, "pthread_cond_destroy", "GLIBC_2.3.2"); +#endif + + if (NULL == real_pthread_cond_timedwait_232) + { + real_pthread_cond_timedwait_232 = dlsym(RTLD_NEXT, "pthread_cond_timedwait"); + } + if (NULL == real_pthread_cond_init_232) + { + real_pthread_cond_init_232 = dlsym(RTLD_NEXT, "pthread_cond_init"); + } + if (NULL == real_pthread_cond_destroy_232) + { + real_pthread_cond_destroy_232 = dlsym(RTLD_NEXT, "pthread_cond_destroy"); + } +#endif +#ifdef __APPLEOSX__ + real_clock_get_time = dlsym(RTLD_NEXT, "clock_get_time"); + real_clock_gettime = apple_clock_gettime; +#else + real_clock_gettime = dlsym(RTLD_NEXT, "__clock_gettime"); + if (NULL == real_clock_gettime) + { + real_clock_gettime = dlsym(RTLD_NEXT, "clock_gettime"); + } +#ifdef FAKE_TIMERS +#if defined(__sun) + real_timer_gettime_233 = dlsym(RTLD_NEXT, "timer_gettime"); + real_timer_settime_233 = dlsym(RTLD_NEXT, "timer_settime"); +#else +#ifdef __GLIBC__ + real_timer_settime_22 = dlvsym(RTLD_NEXT, "timer_settime","GLIBC_2.2"); + real_timer_settime_233 = dlvsym(RTLD_NEXT, "timer_settime","GLIBC_2.3.3"); +#endif + if (NULL == real_timer_settime_233) + { + real_timer_settime_233 = dlsym(RTLD_NEXT, "timer_settime"); + } +#ifdef __GLIBC__ + real_timer_gettime_22 = dlvsym(RTLD_NEXT, "timer_gettime","GLIBC_2.2"); + real_timer_gettime_233 = dlvsym(RTLD_NEXT, "timer_gettime","GLIBC_2.3.3"); +#endif + if (NULL == real_timer_gettime_233) + { + real_timer_gettime_233 = dlsym(RTLD_NEXT, "timer_gettime"); + } +#endif +#endif +#endif + + dont_fake = true; // Do not fake times during initialization + dont_fake_final = false; + initialized = 1; + + ft_shm_init(); +#ifdef FAKE_STAT + if (getenv("NO_FAKE_STAT")!=NULL) + { + fake_stat_disabled = 1; //Note that this is NOT re-checked + } +#endif + + if ((tmp_env = getenv("FAKETIME_CACHE_DURATION")) != NULL) + { + cache_duration = atoi(tmp_env); + } + if ((tmp_env = getenv("FAKETIME_NO_CACHE")) != NULL) + { + if (0 == strcmp(tmp_env, "1")) + { + cache_enabled = 0; + } + } + if ((tmp_env = getenv("DONT_FAKE_MONOTONIC")) != NULL) + { + if (0 == strcmp(tmp_env, "1")) + { + fake_monotonic_clock = 0; + } + } + /* Check whether we actually should be faking the returned timestamp. */ + + /* We can prevent faking time for specified commands */ + if ((tmp_env = getenv("FAKETIME_SKIP_CMDS")) != NULL) + { + char *skip_cmd, *saveptr, *tmpvar; + /* Don't mess with the env variable directly. */ + tmpvar = strdup(tmp_env); + if (tmpvar != NULL) + { + skip_cmd = strtok_r(tmpvar, ",", &saveptr); + while (skip_cmd != NULL) + { + if (0 == strcmp(progname, skip_cmd)) + { + ft_mode = FT_NOOP; + dont_fake_final = true; + break; + } + skip_cmd = strtok_r(NULL, ",", &saveptr); + } + free(tmpvar); + tmpvar = NULL; + } + else + { + fprintf(stderr, "Error: Could not copy the environment variable value.\n"); + exit(EXIT_FAILURE); + } + } + + /* We can limit faking time to specified commands */ + if ((tmp_env = getenv("FAKETIME_ONLY_CMDS")) != NULL) + { + char *only_cmd, *saveptr, *tmpvar; + bool cmd_matched = false; + + if (getenv("FAKETIME_SKIP_CMDS") != NULL) + { + fprintf(stderr, "Error: Both FAKETIME_SKIP_CMDS and FAKETIME_ONLY_CMDS can't be set.\n"); + exit(EXIT_FAILURE); + } + + /* Don't mess with the env variable directly. */ + tmpvar = strdup(tmp_env); + if (tmpvar != NULL) { + only_cmd = strtok_r(tmpvar, ",", &saveptr); + while (only_cmd != NULL) + { + if (0 == strcmp(progname, only_cmd)) + { + cmd_matched = true; + break; + } + only_cmd = strtok_r(NULL, ",", &saveptr); + } + + if (!cmd_matched) + { + ft_mode = FT_NOOP; + dont_fake_final = true; + } + free(tmpvar); + } else { + fprintf(stderr, "Error: Could not copy the environment variable value.\n"); + exit(EXIT_FAILURE); + } + } + + if ((tmp_env = getenv("FAKETIME_START_AFTER_SECONDS")) != NULL) + { + ft_start_after_secs = atol(tmp_env); + limited_faking = true; + } + if ((tmp_env = getenv("FAKETIME_STOP_AFTER_SECONDS")) != NULL) + { + ft_stop_after_secs = atol(tmp_env); + limited_faking = true; + } + if ((tmp_env = getenv("FAKETIME_START_AFTER_NUMCALLS")) != NULL) + { + ft_start_after_ncalls = atol(tmp_env); + limited_faking = true; + } + if ((tmp_env = getenv("FAKETIME_STOP_AFTER_NUMCALLS")) != NULL) + { + ft_stop_after_ncalls = atol(tmp_env); + limited_faking = true; + } + + /* check whether we should spawn an external command */ + if ((tmp_env = getenv("FAKETIME_SPAWN_TARGET")) != NULL) + { + spawnsupport = true; + (void) strncpy(ft_spawn_target, getenv("FAKETIME_SPAWN_TARGET"), sizeof(ft_spawn_target) - 1); + ft_spawn_target[sizeof(ft_spawn_target) - 1] = 0; + if ((tmp_env = getenv("FAKETIME_SPAWN_SECONDS")) != NULL) + { + ft_spawn_secs = atol(tmp_env); + } + if ((tmp_env = getenv("FAKETIME_SPAWN_NUMCALLS")) != NULL) + { + ft_spawn_ncalls = atol(tmp_env); + } + } + + if ((tmp_env = getenv("FAKETIME_SAVE_FILE")) != NULL) + { + if (-1 == (outfile = open(tmp_env, O_RDWR | O_APPEND | O_CLOEXEC | O_CREAT, + S_IWUSR | S_IRUSR))) + { + perror("Opening file for saving timestamps failed"); + exit(EXIT_FAILURE); + } + } + + /* load file only if reading timstamps from it is not finished yet */ + if ((tmp_env = getenv("FAKETIME_LOAD_FILE")) != NULL) + { + int infile = -1; + struct stat sb; + if (-1 == (infile = open(tmp_env, O_RDONLY|O_CLOEXEC))) + { + perror("Opening file for loading timestamps failed"); + exit(EXIT_FAILURE); + } + + fstat(infile, &sb); + if (sizeof(stss[0]) > (infile_size = sb.st_size)) + { + printf("There are no timestamps in the provided file to load timestamps from"); + exit(EXIT_FAILURE); + } + + if ((infile_size % sizeof(stss[0])) != 0) + { + printf("File size is not multiple of timestamp size. It is probably damaged."); + exit(EXIT_FAILURE); + } + + stss = mmap(NULL, infile_size, PROT_READ, MAP_SHARED, infile, 0); + if (stss == MAP_FAILED) + { + perror("Mapping file for loading timestamps failed"); + exit(EXIT_FAILURE); + } + infile_set = true; + } + + tmp_env = getenv("FAKETIME_FMT"); + if (tmp_env == NULL) + { + strcpy(user_faked_time_fmt, "%Y-%m-%d %T"); + } + else + { + strncpy(user_faked_time_fmt, tmp_env, BUFSIZ - 1); + user_faked_time_fmt[BUFSIZ - 1] = 0; + } + + if (shared_sem != 0) + { + if (sem_wait(shared_sem) == -1) + { + perror("sem_wait"); + exit(1); + } + if (ft_shared->start_time.real.tv_nsec == -1) + { + /* set up global start time */ + system_time_from_system(&ftpl_starttime); + ft_shared->start_time = ftpl_starttime; + } + else + { + /** get preset start time */ + ftpl_starttime = ft_shared->start_time; + } + if (sem_post(shared_sem) == -1) + { + perror("sem_post"); + exit(1); + } + } + else + { + system_time_from_system(&ftpl_starttime); + } + /* fake time supplied as environment variable? */ + if (NULL != (tmp_env = getenv("FAKETIME"))) + { + parse_config_file = false; + parse_ft_string(tmp_env); + } + + dont_fake = dont_fake_final; +} + + +/* + * ======================================================================= + * Helper functions === HELPER + * ======================================================================= + */ + +static void remove_trailing_eols(char *line) +{ + char *endp = line + strlen(line); + /* + * erase the last char if it's a newline + * or carriage return, and back up. + * keep doing this, but don't back up + * past the beginning of the string. + */ +# define is_eolchar(c) ((c) == '\n' || (c) == '\r') + while (endp > line && is_eolchar(endp[-1])) + { + *--endp = '\0'; + } +} + + +/* + * ======================================================================= + * Implementation of faked functions === FAKE(FAKE) + * ======================================================================= + */ + +#ifdef PTHREAD_SINGLETHREADED_TIME +static void pthread_cleanup_mutex_lock(void *data) +{ + pthread_mutex_t *mutex = data; + pthread_mutex_unlock(mutex); +} +#endif + +int fake_clock_gettime(clockid_t clk_id, struct timespec *tp) +{ + /* variables used for caching, introduced in version 0.6 */ + static time_t last_data_fetch = 0; /* not fetched previously at first call */ + static int cache_expired = 1; /* considered expired at first call */ + + if (dont_fake) return 0; + /* Per process timers are only sped up or slowed down */ + if ((clk_id == CLOCK_PROCESS_CPUTIME_ID ) || (clk_id == CLOCK_THREAD_CPUTIME_ID)) + { + if (user_rate_set) + { + timespecmul(tp, user_rate, tp); + } + return 0; + } + + /* Sanity check by Karl Chan since v0.8 */ + if (tp == NULL) return -1; + +#ifdef PTHREAD_SINGLETHREADED_TIME + static pthread_mutex_t time_mutex=PTHREAD_MUTEX_INITIALIZER; + pthread_mutex_lock(&time_mutex); + pthread_cleanup_push(pthread_cleanup_mutex_lock, &time_mutex); +#endif + + if ((limited_faking && + ((ft_start_after_ncalls != -1) || (ft_stop_after_ncalls != -1))) || + (spawnsupport && ft_spawn_ncalls)) + { + if (callcounter < LONG_MAX) callcounter++; + } + + if (limited_faking || spawnsupport) + { + struct timespec tmp_ts; + /* For debugging, output #seconds and #calls */ + switch (clk_id) + { + case CLOCK_REALTIME: +#ifdef CLOCK_REALTIME_COARSE + case CLOCK_REALTIME_COARSE: +#endif + timespecsub(tp, &ftpl_starttime.real, &tmp_ts); + break; + case CLOCK_MONOTONIC: +#ifdef CLOCK_MONOTONIC_COARSE + case CLOCK_MONOTONIC_COARSE: +#endif + timespecsub(tp, &ftpl_starttime.mon, &tmp_ts); + break; + case CLOCK_MONOTONIC_RAW: + timespecsub(tp, &ftpl_starttime.mon_raw, &tmp_ts); + break; +#ifdef CLOCK_BOOTTIME + case CLOCK_BOOTTIME: + timespecsub(tp, &ftpl_starttime.boot, &tmp_ts); + break; +#endif + default: + timespecsub(tp, &ftpl_starttime.real, &tmp_ts); + break; + } + + if (limited_faking) + { + /* Check whether we actually should be faking the returned timestamp. */ + /* fprintf(stderr, "(libfaketime limits -> runtime: %lu, callcounter: %lu\n", (*time_tptr - ftpl_starttime), callcounter); */ + if ((ft_start_after_secs != -1) && (tmp_ts.tv_sec < ft_start_after_secs)) return 0; + if ((ft_stop_after_secs != -1) && (tmp_ts.tv_sec >= ft_stop_after_secs)) return 0; + if ((ft_start_after_ncalls != -1) && (callcounter < ft_start_after_ncalls)) return 0; + if ((ft_stop_after_ncalls != -1) && (callcounter >= ft_stop_after_ncalls)) return 0; + /* fprintf(stderr, "(libfaketime limits -> runtime: %lu, callcounter: %lu continues\n", (*time_tptr - ftpl_starttime), callcounter); */ + } + + if (spawnsupport) + { + /* check whether we should spawn an external command */ + if (spawned == 0) + { /* exec external command once only */ + if (((tmp_ts.tv_sec == ft_spawn_secs) || (callcounter == ft_spawn_ncalls)) && (spawned == 0)) + { + spawned = 1; + (void) (system(ft_spawn_target) + 1); + } + } + } + } + + if (last_data_fetch > 0) + { + if ((tp->tv_sec - last_data_fetch) > cache_duration) + { + cache_expired = 1; + } + else + { + cache_expired = 0; + } + } + + if (cache_enabled == 0) + { + cache_expired = 1; + } + + if (cache_expired == 1) + { + static char user_faked_time[BUFFERLEN]; /* changed to static for caching in v0.6 */ + /* initialize with default or env. variable */ + char *tmp_env; + + /* Can be enabled for testing ... + fprintf(stderr, "***************++ Cache expired ++**************\n"); + */ + + if (NULL != (tmp_env = getenv("FAKETIME"))) + { + strncpy(user_faked_time, tmp_env, BUFFERLEN - 1); + user_faked_time[BUFFERLEN - 1] = 0; + } + else + { + snprintf(user_faked_time, BUFFERLEN, "+0"); + } + + last_data_fetch = tp->tv_sec; + /* fake time supplied as environment variable? */ + if (parse_config_file) + { + char custom_filename[BUFSIZ]; + char filename[BUFSIZ]; + FILE *faketimerc; + /* check whether there's a .faketimerc in the user's home directory, or + * a system-wide /etc/faketimerc present. + * The /etc/faketimerc handling has been contributed by David Burley, + * Jacob Moorman, and Wayne Davison of SourceForge, Inc. in version 0.6 */ + (void) snprintf(custom_filename, BUFSIZ, "%s", getenv("FAKETIME_TIMESTAMP_FILE")); + (void) snprintf(filename, BUFSIZ, "%s/.faketimerc", getenv("HOME")); + if ((faketimerc = fopen(custom_filename, "rt")) != NULL || + (faketimerc = fopen(filename, "rt")) != NULL || + (faketimerc = fopen("/etc/faketimerc", "rt")) != NULL) + { + char line[BUFFERLEN]; + while(fgets(line, BUFFERLEN, faketimerc) != NULL) + { + if ((strlen(line) > 1) && (line[0] != ' ') && + (line[0] != '#') && (line[0] != ';')) + { + remove_trailing_eols(line); + strncpy(user_faked_time, line, BUFFERLEN-1); + user_faked_time[BUFFERLEN-1] = 0; + break; + } + } + fclose(faketimerc); + } + } /* read fake time from file */ + parse_ft_string(user_faked_time); + } /* cache had expired */ + + if (infile_set) + { + if (load_time(tp)) + { + return 0; + } + } + + /* check whether the user gave us an absolute time to fake */ + switch (ft_mode) + { + case FT_FREEZE: /* a specified time */ + if (user_faked_time_set) + { + *tp = user_faked_time_timespec; + } + break; + + case FT_START_AT: /* User-specified offset */ + if (user_per_tick_inc_set) + { + /* increment time with every time() call*/ + next_time(tp, &user_per_tick_inc); + } + else + { + /* Speed-up / slow-down contributed by Karl Chen in v0.8 */ + struct timespec tdiff, timeadj; + switch (clk_id) + { + case CLOCK_REALTIME: +#ifdef CLOCK_REALTIME_COARSE + case CLOCK_REALTIME_COARSE: +#endif + timespecsub(tp, &ftpl_starttime.real, &tdiff); + break; + case CLOCK_MONOTONIC: +#ifdef CLOCK_MONOTONIC_COARSE + case CLOCK_MONOTONIC_COARSE: +#endif + timespecsub(tp, &ftpl_starttime.mon, &tdiff); + break; + case CLOCK_MONOTONIC_RAW: + timespecsub(tp, &ftpl_starttime.mon_raw, &tdiff); + break; +#ifdef CLOCK_BOOTTIME + case CLOCK_BOOTTIME: + timespecsub(tp, &ftpl_starttime.boot, &tdiff); + break; +#endif + default: + timespecsub(tp, &ftpl_starttime.real, &tdiff); + break; + } // end of switch (clk_id) + if (user_rate_set) + { + timespecmul(&tdiff, user_rate, &timeadj); + } + else + { + timeadj = tdiff; + } + timespecadd(&user_faked_time_timespec, &timeadj, tp); + } + break; + + default: + return -1; + } // end of switch(ft_mode) + +#ifdef PTHREAD_SINGLETHREADED_TIME + pthread_cleanup_pop(1); +#endif + save_time(tp); + return 0; +} + +int fake_gettimeofday(struct timeval *tv) +{ + struct timespec ts; + int ret; + ts.tv_sec = tv->tv_sec; + ts.tv_nsec = tv->tv_usec * 1000 + ftpl_starttime.real.tv_nsec % 1000; + + ret = fake_clock_gettime(CLOCK_REALTIME, &ts); + tv->tv_sec = ts.tv_sec; + tv->tv_usec =ts.tv_nsec / 1000; + + return ret; +} + + +/* + * ======================================================================= + * Faked system functions: Apple Mac OS X specific === FAKE(OSX) + * ======================================================================= + */ + +#ifdef __APPLEOSX__ +/* + * clock_gettime implementation for __APPLE__ + * @note It always behave like being called with CLOCK_REALTIME. + */ +static int apple_clock_gettime(clockid_t clk_id, struct timespec *tp) +{ + int result; + mach_timespec_t cur_timeclockid_t; + (void) clk_id; /* unused */ + + if (NULL == real_clock_get_time) + { /* dlsym() failed */ +#ifdef DEBUG + (void) fprintf(stderr, "faketime problem: original clock_get_time() not found.\n"); +#endif + return -1; /* propagate error to caller */ + } + + DONT_FAKE_TIME(result = (*real_clock_get_time)(clock_serv_real, &cur_timeclockid_t)); + tp->tv_sec = cur_timeclockid_t.tv_sec; + tp->tv_nsec = cur_timeclockid_t.tv_nsec; + return result; +} + +int clock_get_time(clock_serv_t clock_serv, mach_timespec_t *cur_timeclockid_t) +{ + int result; + struct timespec ts; + + /* + * Initialize our result with the real current time from CALENDAR_CLOCK. + * This is a bit of cheating, but we don't keep track of obtained clock + * services. + */ + DONT_FAKE_TIME(result = (*real_clock_gettime)(CLOCK_REALTIME, &ts)); + if (result == -1) return result; /* original function failed */ + + /* pass the real current time to our faking version, overwriting it */ + result = fake_clock_gettime(CLOCK_REALTIME, &ts); + cur_timeclockid_t->tv_sec = ts.tv_sec; + cur_timeclockid_t->tv_nsec = ts.tv_nsec; + + /* return the result to the caller */ + return result; +} +#endif + + +/* + * ======================================================================= + * Faked system-internal functions === FAKE(INT) + * ======================================================================= + */ + +#ifdef FAKE_INTERNAL_CALLS +int __gettimeofday(struct timeval *tv, void *tz) +{ + int result; + + /* sanity check */ + if (tv == NULL) + { + return -1; + } + + /* Check whether we've got a pointer to the real ftime() function yet */ + if (NULL == real___gettimeofday) + { /* dlsym() failed */ +#ifdef DEBUG + (void) fprintf(stderr, "faketime problem: original __gettimeofday() not found.\n"); +#endif + return -1; /* propagate error to caller */ + } + + /* initialize our result with the real current time */ + DONT_FAKE_TIME(result = (*real___gettimeofday)(tv, tz)); + if (result == -1) return result; /* original function failed */ + + /* pass the real current time to our faking version, overwriting it */ + result = fake_gettimeofday(tv); + + /* return the result to the caller */ + return result; +} + +int __clock_gettime(clockid_t clk_id, struct timespec *tp) +{ + int result; + + /* sanity check */ + if (tp == NULL) + { + return -1; + } + + if (NULL == real___clock_gettime) + { /* dlsym() failed */ +#ifdef DEBUG + (void) fprintf(stderr, "faketime problem: original __clock_gettime() not found.\n"); +#endif + return -1; /* propagate error to caller */ + } + + /* initialize our result with the real current time */ + DONT_FAKE_TIME(result = (*real___clock_gettime)(clk_id, tp)); + if (result == -1) return result; /* original function failed */ + + /* pass the real current time to our faking version, overwriting it */ + if (fake_monotonic_clock || (clk_id != CLOCK_MONOTONIC && clk_id != CLOCK_MONOTONIC_RAW +#ifdef CLOCK_MONOTONIC_COARSE + && clk_id != CLOCK_MONOTONIC_COARSE +#endif +#ifdef CLOCK_BOOTTIME + && clk_id != CLOCK_BOOTTIME +#endif + )) + + { + result = fake_clock_gettime(clk_id, tp); + } + + /* return the result to the caller */ + return result; +} + +time_t __time(time_t *time_tptr) +{ + struct timespec tp; + time_t result; + + DONT_FAKE_TIME(result = (*real_clock_gettime)(CLOCK_REALTIME, &tp)); + if (result == -1) return -1; + + /* pass the real current time to our faking version, overwriting it */ + (void)fake_clock_gettime(CLOCK_REALTIME, &tp); + + if (time_tptr != NULL) + { + *time_tptr = tp.tv_sec; + } + return tp.tv_sec; +} + +int __ftime(struct timeb *tb) +{ + struct timespec tp; + int result; + + /* sanity check */ + if (tb == NULL) + return 0; /* ftime() always returns 0, see manpage */ + + /* Check whether we've got a pointer to the real ftime() function yet */ + if (NULL == real___ftime) + { /* dlsym() failed */ +#ifdef DEBUG + (void) fprintf(stderr, "faketime problem: original ftime() not found.\n"); +#endif + return 0; /* propagate error to caller */ + } + + /* initialize our TZ result with the real current time */ + DONT_FAKE_TIME(result = (*real___ftime)(tb)); + if (result == -1) + { + return result; + } + + DONT_FAKE_TIME(result = (*real_clock_gettime)(CLOCK_REALTIME, &tp)); + if (result == -1) return -1; + + /* pass the real current time to our faking version, overwriting it */ + (void)fake_clock_gettime(CLOCK_REALTIME, &tp); + + tb->time = tp.tv_sec; + tb->millitm = tp.tv_nsec / 1000000; + + /* return the result to the caller */ + return result; /* will always be 0 (see manpage) */ +} + +#endif + +/* + * ======================================================================= + * Faked pthread_cond_timedwait === FAKE(pthread) + * ======================================================================= + */ + +/* pthread_cond_timedwait + + The specified absolute time in pthread_cond_timedwait is directly + passed to the kernel via the futex syscall. The kernel, however, + does not know about the fake time. In 99.9% of cases, the time + until this function should wait is calculated by an application + relatively to the current time, which has been faked in the + application. Hence, we should convert the waiting time back to real + time. + + pthread_cond_timedwait in GLIBC_2_2_5 only supports + CLOCK_REALTIME. Since the init and destroy functions are not + redefined for GLIBC_2_2_5, a corresponding cond will never be + added to monotonic_conds and hence the correct branch will + always be taken. +*/ + + +#ifdef FAKE_PTHREAD + +typedef enum {FT_COMPAT_GLIBC_2_2_5, FT_COMPAT_GLIBC_2_3_2} ft_lib_compat_pthread; + +struct pthread_cond_monotonic { + pthread_cond_t *ptr; + UT_hash_handle hh; +}; + +static struct pthread_cond_monotonic *monotonic_conds = NULL; + +int pthread_cond_init_232(pthread_cond_t *restrict cond, const pthread_condattr_t *restrict attr) +{ + clockid_t clock_id; + int result; + + result = real_pthread_cond_init_232(cond, attr); + + if (result != 0 || attr == NULL) + return result; + + pthread_condattr_getclock(attr, &clock_id); + + if (clock_id == CLOCK_MONOTONIC) { + struct pthread_cond_monotonic *e = (struct pthread_cond_monotonic*)malloc(sizeof(struct pthread_cond_monotonic)); + e->ptr = cond; + HASH_ADD_PTR(monotonic_conds, ptr, e); + } + + return result; +} + +int pthread_cond_destroy_232(pthread_cond_t *cond) +{ + struct pthread_cond_monotonic* e; + HASH_FIND_PTR(monotonic_conds, &cond, e); + if (e) { + HASH_DEL(monotonic_conds, e); + free(e); + } + + return real_pthread_cond_destroy_232(cond); +} + +int pthread_cond_timedwait_common(pthread_cond_t *cond, pthread_mutex_t *mutex, const struct timespec *abstime, ft_lib_compat_pthread compat) +{ + struct timespec tp, tdiff_actual, realtime, faketime; + struct timespec *tf = NULL; + struct pthread_cond_monotonic* e; + char *tmp_env; + int wait_ms; + clockid_t clk_id; + int result = 0; + + if (abstime != NULL) + { + HASH_FIND_PTR(monotonic_conds, &cond, e); + if (e != NULL) + clk_id = CLOCK_MONOTONIC; + else + clk_id = CLOCK_REALTIME; + + DONT_FAKE_TIME(result = (*real_clock_gettime)(clk_id, &realtime)); + if (result == -1) + { + return EINVAL; + } + faketime = realtime; + (void)fake_clock_gettime(clk_id, &faketime); + + if ((tmp_env = getenv("FAKETIME_WAIT_MS")) != NULL) + { + wait_ms = atol(tmp_env); + DONT_FAKE_TIME(result = (*real_clock_gettime)(clk_id, &realtime)); + if (result == -1) + { + return EINVAL; + } + + tdiff_actual.tv_sec = wait_ms / 1000; + tdiff_actual.tv_nsec = (wait_ms % 1000) * 1000000; + timespecadd(&realtime, &tdiff_actual, &tp); + + tf = &tp; + } + else + { + timespecsub(abstime, &faketime, &tp); + if (user_rate_set) + { + timespecmul(&tp, 1.0 / user_rate, &tdiff_actual); + } + else + { + tdiff_actual = tp; + } + } + + /* For CLOCK_MONOTONIC, pthread_cond_timedwait uses clock_gettime + internally to calculate the appropriate duration for the + waiting time. This already uses the faked functions, hence, the + fake time needs to be passed to pthread_cond_timedwait for + CLOCK_MONOTONIC. */ + if(clk_id == CLOCK_MONOTONIC) + timespecadd(&faketime, &tdiff_actual, &tp); + else + timespecadd(&realtime, &tdiff_actual, &tp); + + tf = &tp; + } + + switch (compat) { + case FT_COMPAT_GLIBC_2_3_2: + result = real_pthread_cond_timedwait_232(cond, mutex, tf); + break; + case FT_COMPAT_GLIBC_2_2_5: + result = real_pthread_cond_timedwait_225(cond, mutex, tf); + break; + } + return result; +} + +int pthread_cond_timedwait_225(pthread_cond_t *cond, pthread_mutex_t *mutex, const struct timespec *abstime) +{ + return pthread_cond_timedwait_common(cond, mutex, abstime, FT_COMPAT_GLIBC_2_2_5); +} + +int pthread_cond_timedwait_232(pthread_cond_t *cond, pthread_mutex_t *mutex, const struct timespec *abstime) +{ + return pthread_cond_timedwait_common(cond, mutex, abstime, FT_COMPAT_GLIBC_2_3_2); +} + +__asm__(".symver pthread_cond_timedwait_225, pthread_cond_timedwait@GLIBC_2.2.5"); +__asm__(".symver pthread_cond_timedwait_232, pthread_cond_timedwait@@GLIBC_2.3.2"); +__asm__(".symver pthread_cond_init_232, pthread_cond_init@@GLIBC_2.3.2"); +__asm__(".symver pthread_cond_destroy_232, pthread_cond_destroy@@GLIBC_2.3.2"); + +#endif + + +/* + * Editor modelines + * + * Local variables: + * c-basic-offset: 2 + * tab-width: 2 + * indent-tabs-mode: nil + * End: + * + * vi: set shiftwidth=2 tabstop=2 expandtab: + * :indentSize=2:tabSize=2:noTabs=true: + */ + +/* eof */ diff --git a/tests/deckard/contrib/libfaketime/src/libfaketime.map b/tests/deckard/contrib/libfaketime/src/libfaketime.map new file mode 100644 index 0000000..eb873e7 --- /dev/null +++ b/tests/deckard/contrib/libfaketime/src/libfaketime.map @@ -0,0 +1,21 @@ +GLIBC_2.2 { + global: + + timer_gettime; timer_settime; + local: timer_settime_*; timer_gettime_*; +}; + +GLIBC_2.3.3 { + # Changed timer_t. + timer_gettime; timer_settime; +} GLIBC_2.2; + +GLIBC_2.2.5 { + global: pthread_cond_timedwait; + local: pthread_cond_timedwait_*; pthread_cond_init_*; pthread_cond_destroy*; +}; + +GLIBC_2.3.2 { + pthread_cond_timedwait; pthread_cond_init; pthread_cond_destroy; +} GLIBC_2.2.5; + diff --git a/tests/deckard/contrib/libfaketime/src/sunos_endian.h b/tests/deckard/contrib/libfaketime/src/sunos_endian.h new file mode 100644 index 0000000..b15996a --- /dev/null +++ b/tests/deckard/contrib/libfaketime/src/sunos_endian.h @@ -0,0 +1,12 @@ + +#ifndef SUN_OS_ENDIAN_H +#define SUN_OS_ENDIAN_H + +#include <sys/byteorder.h> + +#define htobe64(x) BE_64(x) +#define be64toh(x) BE_64(x) +#define htole64(x) LE_64(x) +#define le64toh(x) LE_64(x) + +#endif /* SUN_OS_ENDIAN_H */
\ No newline at end of file diff --git a/tests/deckard/contrib/libfaketime/src/time_ops.h b/tests/deckard/contrib/libfaketime/src/time_ops.h new file mode 100644 index 0000000..59ab1ee --- /dev/null +++ b/tests/deckard/contrib/libfaketime/src/time_ops.h @@ -0,0 +1,104 @@ +/* + * Time operation macros based on sys/time.h + * Copyright 2013 Balint Reczey <balint@balintreczey.hu> + * + * This file is part of libfaketime. + * + * libfaketime is free software; you can redistribute it and/or modify it under + * the terms of the GNU General Public License v2 as published by the Free + * Software Foundation. + * + * libfaketime is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License v2 along + * with libfaketime; if not, write to the Free Software Foundation, Inc., + * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#ifndef TIME_OPS_H +#define TIME_OPS_H +#include <time.h> + +#define SEC_TO_uSEC 1000000 +#define SEC_TO_nSEC 1000000000 + +/* Convenience macros for operations on timevals. + NOTE: `timercmp' does not work for >= or <=. */ +#define timerisset2(tvp, prefix) ((tvp)->tv_sec || (tvp)->tv_##prefix##sec) +#define timerclear2(tvp, prefix) ((tvp)->tv_sec = (tvp)->tv_##prefix##sec = 0) +#define timercmp2(a, b, CMP, prefix) \ + (((a)->tv_sec == (b)->tv_sec) ? \ + ((a)->tv_##prefix##sec CMP (b)->tv_##prefix##sec) : \ + ((a)->tv_sec CMP (b)->tv_sec)) +#define timeradd2(a, b, result, prefix) \ + do \ + { \ + (result)->tv_sec = (a)->tv_sec + (b)->tv_sec; \ + (result)->tv_##prefix##sec = (a)->tv_##prefix##sec + \ + (b)->tv_##prefix##sec; \ + if ((result)->tv_##prefix##sec >= SEC_TO_##prefix##SEC) \ + { \ + ++(result)->tv_sec; \ + (result)->tv_##prefix##sec -= SEC_TO_##prefix##SEC; \ + } \ + } while (0) +#define timersub2(a, b, result, prefix) \ + do \ + { \ + (result)->tv_sec = (a)->tv_sec - (b)->tv_sec; \ + (result)->tv_##prefix##sec = (a)->tv_##prefix##sec - \ + (b)->tv_##prefix##sec; \ + if ((result)->tv_##prefix##sec < 0) \ + { \ + --(result)->tv_sec; \ + (result)->tv_##prefix##sec += SEC_TO_##prefix##SEC; \ + } \ + } while (0) +#define timermul2(tvp, c, result, prefix) \ + do \ + { \ + long long tmp_time; \ + tmp_time = (c) * ((tvp)->tv_sec * SEC_TO_##prefix##SEC + \ + (tvp)->tv_##prefix##sec); \ + (result)->tv_##prefix##sec = tmp_time % SEC_TO_##prefix##SEC; \ + (result)->tv_sec = (tmp_time - (result)->tv_##prefix##sec) / \ + SEC_TO_##prefix##SEC; \ + if ((result)->tv_##prefix##sec < 0) \ + { \ + (result)->tv_##prefix##sec += SEC_TO_##prefix##SEC; \ + (result)->tv_sec -= 1; \ + } \ + } while (0) + +/* ops for microsecs */ +#ifndef timerisset +#define timerisset(tvp) timerisset2(tvp,u) +#endif +#ifndef timerclear +#define timerclear(tvp) timerclear2(tvp, u) +#endif +#ifndef timercmp +#define timercmp(a, b, CMP) timercmp2(a, b, CMP, u) +#endif +#ifndef timeradd +#define timeradd(a, b, result) timeradd2(a, b, result, u) +#endif +#ifndef timersub +#define timersub(a, b, result) timersub2(a, b, result, u) +#endif +#ifndef timersub +#define timermul(a, c, result) timermul2(a, c, result, u) +#endif + +/* ops for nanosecs */ +#define timespecisset(tvp) timerisset2(tvp,n) +#define timespecclear(tvp) timerclear2(tvp, n) +#define timespeccmp(a, b, CMP) timercmp2(a, b, CMP, n) +#define timespecadd(a, b, result) timeradd2(a, b, result, n) +#define timespecsub(a, b, result) timersub2(a, b, result, n) +#define timespecmul(a, c, result) timermul2(a, c, result, n) + +#endif diff --git a/tests/deckard/contrib/libfaketime/src/timeprivacy b/tests/deckard/contrib/libfaketime/src/timeprivacy new file mode 100644 index 0000000..5fd6fd7 --- /dev/null +++ b/tests/deckard/contrib/libfaketime/src/timeprivacy @@ -0,0 +1,270 @@ +#!/bin/bash + +## Copyright (c) 2013, adrelanos at riseup dot net +## 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 COPYRIGHT HOLDERS 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 COPYRIGHT OWNER 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. + +#set -x + +SCRIPTNAME="$(basename $0)" + +usage() { + echo "$SCRIPTNAME + +Usage: $SCRIPTNAME [-h help] [-d day] [-m month] [-y year] [-i increment in seconds (0-60)] [-r random increment in seconds (0-60)] [-f history folder] +Example: $SCRIPTNAME -d 30 -m 12 -y 2013 -i 10 -f /tmp/$SCRIPTNAMEtest + sudo $SCRIPTNAME -d 30 -m 12 -y 2013 -r -f /tmp/$SCRIPTNAMEtest" +} + +_randomincrement="none" +_increment="none" + +while [ -n "$1" ]; do + case "$1" in + -h) + usage + exit 0 + ;; + -d) + _day="$2" + shift + ;; + -m) + _month="$2" + shift + ;; + -y) + _year="$2" + shift + ;; + -i) + _increment="$2" + shift + ;; + -r) + _randomincrement="$2" + shift + ;; + -f) + TIMEDIR="$2" + shift + ;; + *) + command="$(which $1)" + ## From now on the complete to-be wrapped command + its args + ## are stored in $@, which will expand like we want it for + ## handling quoted arguments with whitespaces in it, etc. + break + esac + shift +done + +if [ -z "$_day" ]; then + _day="$(date +"%d")" +fi + +if [ -z "$_month" ]; then + _month="$(date +"%m")" +fi + +if [ -z "$_year" ]; then + _year="$(date +"%Y")" +fi + +if [ "$_randomincrement" = "none" ] && [ "$_increment" = "none" ]; then + _increment="1" +fi + +if [ "$_randomincrement" = "none" ]; then + if [ -z "$_increment" ]; then + _increment="1" + fi +elif [ "$_increment" = "none" ]; then + if [ "$_randomincrement" = "" ]; then + echo "randomincrement must be a positive number." + exit 1 + else + ## random number between 1 and $_randomincrement + random_number="$(( 0+($(od -An -N2 -i /dev/random) )%($_randomincrement-0+1) ))" + _increment="$random_number" + fi +else + echo "You can not combine -r and -i." + exit 1 +fi + +if [ -z "$TIMEDIR" ]; then + TIMEDIR=~/.timeprivacy +fi + +nodigits="$(echo $_increment | sed 's/[[:digit:]]//g')" +if [ ! -z "$nodigits" ]; then + echo "increment is not a digit." + exit 1 +fi + +nodigits="$(echo $_year | sed 's/[[:digit:]]//g')" +if [ ! -z "$nodigits" ]; then + echo "_day is not a digit." + exit 1 +fi + +nodigits="$(echo $_year | sed 's/[[:digit:]]//g')" +if [ ! -z "$nodigits" ]; then + echo "year is not a digit." + exit 1 +fi + +nodigits="$(echo $_month | sed 's/[[:digit:]]//g')" +if [ ! -z "$nodigits" ]; then + echo "month is not a digit." + exit 1 +fi + +nodigits="$(echo $_day | sed 's/[[:digit:]]//g')" +if [ ! -z "$nodigits" ]; then + echo "day is not a digit." + exit 1 +fi + +nodigits="$(echo $_increment | sed 's/[[:digit:]]//g')" +if [ ! -z "$nodigits" ]; then + echo "increment is not a digit." + exit 1 +fi + +SECONDS_FILE="$TIMEDIR/seconds_file" +MINUTES_FILE="$TIMEDIR/minutes_file" +HOURS_FILE="$TIMEDIR/hours_file" + +#DAYS_FILE="$TIMEDIR/days_file" +#MONTHS_FILE="$TIMEDIR/months_file" +#YEARS_FILE="$TIMEDIR/years_file" + +#true "TIMEDIR: $TIMEDIR" +#true "year: $_year" +#true "month: $_month" +#true "day: $_day" +#true "_randomincrement: $_randomincrement" +#true "_increment: $_increment" + +read_date_file() { + if [ ! -d "$TIMEDIR" ]; then + mkdir -p "$TIMEDIR" + fi + + if [ ! -f "$SECONDS_FILE" ]; then + echo "0" > "$SECONDS_FILE" + fi + + if [ ! -f "$MINUTES_FILE" ]; then + echo "0" > "$MINUTES_FILE" + fi + + if [ ! -f "$HOURS_FILE" ]; then + echo "0" > "$HOURS_FILE" + fi + + #if [ ! -f "$DAYS_FILE" ]; then + #echo "1" > "$DAYS_FILE" + #fi + + #if [ ! -f "$MONTHS_FILE" ]; then + #echo "1" > "$MONTHS_FILE" + #fi + + #if [ ! -f "$YEARS_FILE" ]; then + #echo "2013" > "$YEARS_FILE" + #fi + + SECONDS="$(cat "$SECONDS_FILE")" + MINUTES="$(cat "$MINUTES_FILE")" + HOURS="$(cat "$HOURS_FILE")" + + if [ -z "$SECONDS" ]; then + SECONDS="0" + fi + + if [ -z "$MINUTES" ]; then + MINUTES="0" + fi + + if [ -z "$HOURS" ]; then + HOURS="0" + fi + + local nodigits="$(echo $SECONDS | sed 's/[[:digit:]]//g')" + if [ ! -z "$nodigits" ]; then + SECONDS="0" + fi + + local nodigits="$(echo $MINUTES | sed 's/[[:digit:]]//g')" + if [ ! -z "$nodigits" ]; then + MINUTES="0" + fi + + local nodigits="$(echo $HOURS | sed 's/[[:digit:]]//g')" + if [ ! -z "$nodigits" ]; then + HOURS="0" + fi + + SECONDS="$(expr "$SECONDS" + "$_increment")" || true + if [ "$SECONDS" -ge "60" ]; then + SECONDS="0" + + MINUTES="$(expr "$MINUTES" + "1")" || true + if [ "$MINUTES" -ge "60" ]; then + MINUTES="0" + + HOURS="$(expr "$HOURS" + "1")" || true + if [ "$HOURS" -ge "24" ]; then + HOURS="0" + fi + echo "$HOURS" > "$HOURS_FILE" + + fi + echo "$MINUTES" > "$MINUTES_FILE" + + fi + + echo "$SECONDS" > "$SECONDS_FILE" + + #echo "$HOURS $MINUTES $SECONDS" +} + +need_new_date() { + ## Testing + #while [ 1 ]; do + # read_date_file + #done + + read_date_file + + ## Testing + #echo "faketime '$_year-$_month-$_day $HOURS:$MINUTES:$SECONDS' /bin/date" + #faketime "$_year-$_month-$_day $HOURS:$MINUTES:$SECONDS" /bin/date + + echo "$_year-$_month-$_day $HOURS:$MINUTES:$SECONDS" +} + +need_new_date + diff --git a/tests/deckard/contrib/libfaketime/src/uthash.h b/tests/deckard/contrib/libfaketime/src/uthash.h new file mode 100644 index 0000000..7e64cac --- /dev/null +++ b/tests/deckard/contrib/libfaketime/src/uthash.h @@ -0,0 +1,1208 @@ +/* +Copyright (c) 2003-2017, Troy D. Hanson http://troydhanson.github.com/uthash/ +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 COPYRIGHT OWNER +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. +*/ + +#ifndef UTHASH_H +#define UTHASH_H + +#define UTHASH_VERSION 2.0.2 + +#include <string.h> /* memcmp, memset, strlen */ +#include <stddef.h> /* ptrdiff_t */ +#include <stdlib.h> /* exit */ + +/* These macros use decltype or the earlier __typeof GNU extension. + As decltype is only available in newer compilers (VS2010 or gcc 4.3+ + when compiling c++ source) this code uses whatever method is needed + or, for VS2008 where neither is available, uses casting workarounds. */ +#if !defined(DECLTYPE) && !defined(NO_DECLTYPE) +#if defined(_MSC_VER) /* MS compiler */ +#if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ +#define DECLTYPE(x) (decltype(x)) +#else /* VS2008 or older (or VS2010 in C mode) */ +#define NO_DECLTYPE +#endif +#elif defined(__BORLANDC__) || defined(__ICCARM__) || defined(__LCC__) || defined(__WATCOMC__) +#define NO_DECLTYPE +#else /* GNU, Sun and other compilers */ +#define DECLTYPE(x) (__typeof(x)) +#endif +#endif + +#ifdef NO_DECLTYPE +#define DECLTYPE(x) +#define DECLTYPE_ASSIGN(dst,src) \ +do { \ + char **_da_dst = (char**)(&(dst)); \ + *_da_dst = (char*)(src); \ +} while (0) +#else +#define DECLTYPE_ASSIGN(dst,src) \ +do { \ + (dst) = DECLTYPE(dst)(src); \ +} while (0) +#endif + +/* a number of the hash function use uint32_t which isn't defined on Pre VS2010 */ +#if defined(_WIN32) +#if defined(_MSC_VER) && _MSC_VER >= 1600 +#include <stdint.h> +#elif defined(__WATCOMC__) || defined(__MINGW32__) || defined(__CYGWIN__) +#include <stdint.h> +#else +typedef unsigned int uint32_t; +typedef unsigned char uint8_t; +#endif +#elif defined(__GNUC__) && !defined(__VXWORKS__) +#include <stdint.h> +#else +typedef unsigned int uint32_t; +typedef unsigned char uint8_t; +#endif + +#ifndef uthash_malloc +#define uthash_malloc(sz) malloc(sz) /* malloc fcn */ +#endif +#ifndef uthash_free +#define uthash_free(ptr,sz) free(ptr) /* free fcn */ +#endif +#ifndef uthash_bzero +#define uthash_bzero(a,n) memset(a,'\0',n) +#endif +#ifndef uthash_memcmp +#define uthash_memcmp(a,b,n) memcmp(a,b,n) +#endif +#ifndef uthash_strlen +#define uthash_strlen(s) strlen(s) +#endif + +#ifndef uthash_noexpand_fyi +#define uthash_noexpand_fyi(tbl) /* can be defined to log noexpand */ +#endif +#ifndef uthash_expand_fyi +#define uthash_expand_fyi(tbl) /* can be defined to log expands */ +#endif + +#ifndef HASH_NONFATAL_OOM +#define HASH_NONFATAL_OOM 0 +#endif + +#if HASH_NONFATAL_OOM +/* malloc failures can be recovered from */ + +#ifndef uthash_nonfatal_oom +#define uthash_nonfatal_oom(obj) do {} while (0) /* non-fatal OOM error */ +#endif + +#define HASH_RECORD_OOM(oomed) do { (oomed) = 1; } while (0) +#define IF_HASH_NONFATAL_OOM(x) x + +#else +/* malloc failures result in lost memory, hash tables are unusable */ + +#ifndef uthash_fatal +#define uthash_fatal(msg) exit(-1) /* fatal OOM error */ +#endif + +#define HASH_RECORD_OOM(oomed) uthash_fatal("out of memory") +#define IF_HASH_NONFATAL_OOM(x) + +#endif + +/* initial number of buckets */ +#define HASH_INITIAL_NUM_BUCKETS 32U /* initial number of buckets */ +#define HASH_INITIAL_NUM_BUCKETS_LOG2 5U /* lg2 of initial number of buckets */ +#define HASH_BKT_CAPACITY_THRESH 10U /* expand when bucket count reaches */ + +/* calculate the element whose hash handle address is hhp */ +#define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho))) +/* calculate the hash handle from element address elp */ +#define HH_FROM_ELMT(tbl,elp) ((UT_hash_handle *)(((char*)(elp)) + ((tbl)->hho))) + +#define HASH_ROLLBACK_BKT(hh, head, itemptrhh) \ +do { \ + struct UT_hash_handle *_hd_hh_item = (itemptrhh); \ + unsigned _hd_bkt; \ + HASH_TO_BKT(_hd_hh_item->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \ + (head)->hh.tbl->buckets[_hd_bkt].count++; \ + _hd_hh_item->hh_next = NULL; \ + _hd_hh_item->hh_prev = NULL; \ +} while (0) + +#define HASH_VALUE(keyptr,keylen,hashv) \ +do { \ + HASH_FCN(keyptr, keylen, hashv); \ +} while (0) + +#define HASH_FIND_BYHASHVALUE(hh,head,keyptr,keylen,hashval,out) \ +do { \ + (out) = NULL; \ + if (head) { \ + unsigned _hf_bkt; \ + HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _hf_bkt); \ + if (HASH_BLOOM_TEST((head)->hh.tbl, hashval) != 0) { \ + HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], keyptr, keylen, hashval, out); \ + } \ + } \ +} while (0) + +#define HASH_FIND(hh,head,keyptr,keylen,out) \ +do { \ + unsigned _hf_hashv; \ + HASH_VALUE(keyptr, keylen, _hf_hashv); \ + HASH_FIND_BYHASHVALUE(hh, head, keyptr, keylen, _hf_hashv, out); \ +} while (0) + +#ifdef HASH_BLOOM +#define HASH_BLOOM_BITLEN (1UL << HASH_BLOOM) +#define HASH_BLOOM_BYTELEN (HASH_BLOOM_BITLEN/8UL) + (((HASH_BLOOM_BITLEN%8UL)!=0UL) ? 1UL : 0UL) +#define HASH_BLOOM_MAKE(tbl,oomed) \ +do { \ + (tbl)->bloom_nbits = HASH_BLOOM; \ + (tbl)->bloom_bv = (uint8_t*)uthash_malloc(HASH_BLOOM_BYTELEN); \ + if (!(tbl)->bloom_bv) { \ + HASH_RECORD_OOM(oomed); \ + } else { \ + uthash_bzero((tbl)->bloom_bv, HASH_BLOOM_BYTELEN); \ + (tbl)->bloom_sig = HASH_BLOOM_SIGNATURE; \ + } \ +} while (0) + +#define HASH_BLOOM_FREE(tbl) \ +do { \ + uthash_free((tbl)->bloom_bv, HASH_BLOOM_BYTELEN); \ +} while (0) + +#define HASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8U] |= (1U << ((idx)%8U))) +#define HASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8U] & (1U << ((idx)%8U))) + +#define HASH_BLOOM_ADD(tbl,hashv) \ + HASH_BLOOM_BITSET((tbl)->bloom_bv, ((hashv) & (uint32_t)((1UL << (tbl)->bloom_nbits) - 1U))) + +#define HASH_BLOOM_TEST(tbl,hashv) \ + HASH_BLOOM_BITTEST((tbl)->bloom_bv, ((hashv) & (uint32_t)((1UL << (tbl)->bloom_nbits) - 1U))) + +#else +#define HASH_BLOOM_MAKE(tbl,oomed) +#define HASH_BLOOM_FREE(tbl) +#define HASH_BLOOM_ADD(tbl,hashv) +#define HASH_BLOOM_TEST(tbl,hashv) (1) +#define HASH_BLOOM_BYTELEN 0U +#endif + +#define HASH_MAKE_TABLE(hh,head,oomed) \ +do { \ + (head)->hh.tbl = (UT_hash_table*)uthash_malloc(sizeof(UT_hash_table)); \ + if (!(head)->hh.tbl) { \ + HASH_RECORD_OOM(oomed); \ + } else { \ + uthash_bzero((head)->hh.tbl, sizeof(UT_hash_table)); \ + (head)->hh.tbl->tail = &((head)->hh); \ + (head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS; \ + (head)->hh.tbl->log2_num_buckets = HASH_INITIAL_NUM_BUCKETS_LOG2; \ + (head)->hh.tbl->hho = (char*)(&(head)->hh) - (char*)(head); \ + (head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_malloc( \ + HASH_INITIAL_NUM_BUCKETS * sizeof(struct UT_hash_bucket)); \ + (head)->hh.tbl->signature = HASH_SIGNATURE; \ + if (!(head)->hh.tbl->buckets) { \ + HASH_RECORD_OOM(oomed); \ + uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ + } else { \ + uthash_bzero((head)->hh.tbl->buckets, \ + HASH_INITIAL_NUM_BUCKETS * sizeof(struct UT_hash_bucket)); \ + HASH_BLOOM_MAKE((head)->hh.tbl, oomed); \ + IF_HASH_NONFATAL_OOM( \ + if (oomed) { \ + uthash_free((head)->hh.tbl->buckets, \ + HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ + uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ + } \ + ) \ + } \ + } \ +} while (0) + +#define HASH_REPLACE_BYHASHVALUE_INORDER(hh,head,fieldname,keylen_in,hashval,add,replaced,cmpfcn) \ +do { \ + (replaced) = NULL; \ + HASH_FIND_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, replaced); \ + if (replaced) { \ + HASH_DELETE(hh, head, replaced); \ + } \ + HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, &((add)->fieldname), keylen_in, hashval, add, cmpfcn); \ +} while (0) + +#define HASH_REPLACE_BYHASHVALUE(hh,head,fieldname,keylen_in,hashval,add,replaced) \ +do { \ + (replaced) = NULL; \ + HASH_FIND_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, replaced); \ + if (replaced) { \ + HASH_DELETE(hh, head, replaced); \ + } \ + HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, add); \ +} while (0) + +#define HASH_REPLACE(hh,head,fieldname,keylen_in,add,replaced) \ +do { \ + unsigned _hr_hashv; \ + HASH_VALUE(&((add)->fieldname), keylen_in, _hr_hashv); \ + HASH_REPLACE_BYHASHVALUE(hh, head, fieldname, keylen_in, _hr_hashv, add, replaced); \ +} while (0) + +#define HASH_REPLACE_INORDER(hh,head,fieldname,keylen_in,add,replaced,cmpfcn) \ +do { \ + unsigned _hr_hashv; \ + HASH_VALUE(&((add)->fieldname), keylen_in, _hr_hashv); \ + HASH_REPLACE_BYHASHVALUE_INORDER(hh, head, fieldname, keylen_in, _hr_hashv, add, replaced, cmpfcn); \ +} while (0) + +#define HASH_APPEND_LIST(hh, head, add) \ +do { \ + (add)->hh.next = NULL; \ + (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail); \ + (head)->hh.tbl->tail->next = (add); \ + (head)->hh.tbl->tail = &((add)->hh); \ +} while (0) + +#define HASH_AKBI_INNER_LOOP(hh,head,add,cmpfcn) \ +do { \ + do { \ + if (cmpfcn(DECLTYPE(head)(_hs_iter), add) > 0) { \ + break; \ + } \ + } while ((_hs_iter = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->next)); \ +} while (0) + +#ifdef NO_DECLTYPE +#undef HASH_AKBI_INNER_LOOP +#define HASH_AKBI_INNER_LOOP(hh,head,add,cmpfcn) \ +do { \ + char *_hs_saved_head = (char*)(head); \ + do { \ + DECLTYPE_ASSIGN(head, _hs_iter); \ + if (cmpfcn(head, add) > 0) { \ + DECLTYPE_ASSIGN(head, _hs_saved_head); \ + break; \ + } \ + DECLTYPE_ASSIGN(head, _hs_saved_head); \ + } while ((_hs_iter = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->next)); \ +} while (0) +#endif + +#if HASH_NONFATAL_OOM + +#define HASH_ADD_TO_TABLE(hh,head,keyptr,keylen_in,hashval,add,oomed) \ +do { \ + if (!(oomed)) { \ + unsigned _ha_bkt; \ + (head)->hh.tbl->num_items++; \ + HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _ha_bkt); \ + HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt], hh, &(add)->hh, oomed); \ + if (oomed) { \ + HASH_ROLLBACK_BKT(hh, head, &(add)->hh); \ + HASH_DELETE_HH(hh, head, &(add)->hh); \ + (add)->hh.tbl = NULL; \ + uthash_nonfatal_oom(add); \ + } else { \ + HASH_BLOOM_ADD((head)->hh.tbl, hashval); \ + HASH_EMIT_KEY(hh, head, keyptr, keylen_in); \ + } \ + } else { \ + (add)->hh.tbl = NULL; \ + uthash_nonfatal_oom(add); \ + } \ +} while (0) + +#else + +#define HASH_ADD_TO_TABLE(hh,head,keyptr,keylen_in,hashval,add,oomed) \ +do { \ + unsigned _ha_bkt; \ + (head)->hh.tbl->num_items++; \ + HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _ha_bkt); \ + HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt], hh, &(add)->hh, oomed); \ + HASH_BLOOM_ADD((head)->hh.tbl, hashval); \ + HASH_EMIT_KEY(hh, head, keyptr, keylen_in); \ +} while (0) + +#endif + + +#define HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh,head,keyptr,keylen_in,hashval,add,cmpfcn) \ +do { \ + IF_HASH_NONFATAL_OOM( int _ha_oomed = 0; ) \ + (add)->hh.hashv = (hashval); \ + (add)->hh.key = (char*) (keyptr); \ + (add)->hh.keylen = (unsigned) (keylen_in); \ + if (!(head)) { \ + (add)->hh.next = NULL; \ + (add)->hh.prev = NULL; \ + HASH_MAKE_TABLE(hh, add, _ha_oomed); \ + IF_HASH_NONFATAL_OOM( if (!_ha_oomed) { ) \ + (head) = (add); \ + IF_HASH_NONFATAL_OOM( } ) \ + } else { \ + void *_hs_iter = (head); \ + (add)->hh.tbl = (head)->hh.tbl; \ + HASH_AKBI_INNER_LOOP(hh, head, add, cmpfcn); \ + if (_hs_iter) { \ + (add)->hh.next = _hs_iter; \ + if (((add)->hh.prev = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->prev)) { \ + HH_FROM_ELMT((head)->hh.tbl, (add)->hh.prev)->next = (add); \ + } else { \ + (head) = (add); \ + } \ + HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->prev = (add); \ + } else { \ + HASH_APPEND_LIST(hh, head, add); \ + } \ + } \ + HASH_ADD_TO_TABLE(hh, head, keyptr, keylen_in, hashval, add, _ha_oomed); \ + HASH_FSCK(hh, head, "HASH_ADD_KEYPTR_BYHASHVALUE_INORDER"); \ +} while (0) + +#define HASH_ADD_KEYPTR_INORDER(hh,head,keyptr,keylen_in,add,cmpfcn) \ +do { \ + unsigned _hs_hashv; \ + HASH_VALUE(keyptr, keylen_in, _hs_hashv); \ + HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, keyptr, keylen_in, _hs_hashv, add, cmpfcn); \ +} while (0) + +#define HASH_ADD_BYHASHVALUE_INORDER(hh,head,fieldname,keylen_in,hashval,add,cmpfcn) \ + HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, &((add)->fieldname), keylen_in, hashval, add, cmpfcn) + +#define HASH_ADD_INORDER(hh,head,fieldname,keylen_in,add,cmpfcn) \ + HASH_ADD_KEYPTR_INORDER(hh, head, &((add)->fieldname), keylen_in, add, cmpfcn) + +#define HASH_ADD_KEYPTR_BYHASHVALUE(hh,head,keyptr,keylen_in,hashval,add) \ +do { \ + IF_HASH_NONFATAL_OOM( int _ha_oomed = 0; ) \ + (add)->hh.hashv = (hashval); \ + (add)->hh.key = (char*) (keyptr); \ + (add)->hh.keylen = (unsigned) (keylen_in); \ + if (!(head)) { \ + (add)->hh.next = NULL; \ + (add)->hh.prev = NULL; \ + HASH_MAKE_TABLE(hh, add, _ha_oomed); \ + IF_HASH_NONFATAL_OOM( if (!_ha_oomed) { ) \ + (head) = (add); \ + IF_HASH_NONFATAL_OOM( } ) \ + } else { \ + (add)->hh.tbl = (head)->hh.tbl; \ + HASH_APPEND_LIST(hh, head, add); \ + } \ + HASH_ADD_TO_TABLE(hh, head, keyptr, keylen_in, hashval, add, _ha_oomed); \ + HASH_FSCK(hh, head, "HASH_ADD_KEYPTR_BYHASHVALUE"); \ +} while (0) + +#define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) \ +do { \ + unsigned _ha_hashv; \ + HASH_VALUE(keyptr, keylen_in, _ha_hashv); \ + HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, keyptr, keylen_in, _ha_hashv, add); \ +} while (0) + +#define HASH_ADD_BYHASHVALUE(hh,head,fieldname,keylen_in,hashval,add) \ + HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, add) + +#define HASH_ADD(hh,head,fieldname,keylen_in,add) \ + HASH_ADD_KEYPTR(hh, head, &((add)->fieldname), keylen_in, add) + +#define HASH_TO_BKT(hashv,num_bkts,bkt) \ +do { \ + bkt = ((hashv) & ((num_bkts) - 1U)); \ +} while (0) + +/* delete "delptr" from the hash table. + * "the usual" patch-up process for the app-order doubly-linked-list. + * The use of _hd_hh_del below deserves special explanation. + * These used to be expressed using (delptr) but that led to a bug + * if someone used the same symbol for the head and deletee, like + * HASH_DELETE(hh,users,users); + * We want that to work, but by changing the head (users) below + * we were forfeiting our ability to further refer to the deletee (users) + * in the patch-up process. Solution: use scratch space to + * copy the deletee pointer, then the latter references are via that + * scratch pointer rather than through the repointed (users) symbol. + */ +#define HASH_DELETE(hh,head,delptr) \ + HASH_DELETE_HH(hh, head, &(delptr)->hh) + +#define HASH_DELETE_HH(hh,head,delptrhh) \ +do { \ + struct UT_hash_handle *_hd_hh_del = (delptrhh); \ + if ((_hd_hh_del->prev == NULL) && (_hd_hh_del->next == NULL)) { \ + HASH_BLOOM_FREE((head)->hh.tbl); \ + uthash_free((head)->hh.tbl->buckets, \ + (head)->hh.tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ + uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ + (head) = NULL; \ + } else { \ + unsigned _hd_bkt; \ + if (_hd_hh_del == (head)->hh.tbl->tail) { \ + (head)->hh.tbl->tail = HH_FROM_ELMT((head)->hh.tbl, _hd_hh_del->prev); \ + } \ + if (_hd_hh_del->prev != NULL) { \ + HH_FROM_ELMT((head)->hh.tbl, _hd_hh_del->prev)->next = _hd_hh_del->next; \ + } else { \ + DECLTYPE_ASSIGN(head, _hd_hh_del->next); \ + } \ + if (_hd_hh_del->next != NULL) { \ + HH_FROM_ELMT((head)->hh.tbl, _hd_hh_del->next)->prev = _hd_hh_del->prev; \ + } \ + HASH_TO_BKT(_hd_hh_del->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \ + HASH_DEL_IN_BKT((head)->hh.tbl->buckets[_hd_bkt], _hd_hh_del); \ + (head)->hh.tbl->num_items--; \ + } \ + HASH_FSCK(hh, head, "HASH_DELETE_HH"); \ +} while (0) + +/* convenience forms of HASH_FIND/HASH_ADD/HASH_DEL */ +#define HASH_FIND_STR(head,findstr,out) \ + HASH_FIND(hh,head,findstr,(unsigned)uthash_strlen(findstr),out) +#define HASH_ADD_STR(head,strfield,add) \ + HASH_ADD(hh,head,strfield[0],(unsigned)uthash_strlen(add->strfield),add) +#define HASH_REPLACE_STR(head,strfield,add,replaced) \ + HASH_REPLACE(hh,head,strfield[0],(unsigned)uthash_strlen(add->strfield),add,replaced) +#define HASH_FIND_INT(head,findint,out) \ + HASH_FIND(hh,head,findint,sizeof(int),out) +#define HASH_ADD_INT(head,intfield,add) \ + HASH_ADD(hh,head,intfield,sizeof(int),add) +#define HASH_REPLACE_INT(head,intfield,add,replaced) \ + HASH_REPLACE(hh,head,intfield,sizeof(int),add,replaced) +#define HASH_FIND_PTR(head,findptr,out) \ + HASH_FIND(hh,head,findptr,sizeof(void *),out) +#define HASH_ADD_PTR(head,ptrfield,add) \ + HASH_ADD(hh,head,ptrfield,sizeof(void *),add) +#define HASH_REPLACE_PTR(head,ptrfield,add,replaced) \ + HASH_REPLACE(hh,head,ptrfield,sizeof(void *),add,replaced) +#define HASH_DEL(head,delptr) \ + HASH_DELETE(hh,head,delptr) + +/* HASH_FSCK checks hash integrity on every add/delete when HASH_DEBUG is defined. + * This is for uthash developer only; it compiles away if HASH_DEBUG isn't defined. + */ +#ifdef HASH_DEBUG +#define HASH_OOPS(...) do { fprintf(stderr,__VA_ARGS__); exit(-1); } while (0) +#define HASH_FSCK(hh,head,where) \ +do { \ + struct UT_hash_handle *_thh; \ + if (head) { \ + unsigned _bkt_i; \ + unsigned _count = 0; \ + char *_prev; \ + for (_bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; ++_bkt_i) { \ + unsigned _bkt_count = 0; \ + _thh = (head)->hh.tbl->buckets[_bkt_i].hh_head; \ + _prev = NULL; \ + while (_thh) { \ + if (_prev != (char*)(_thh->hh_prev)) { \ + HASH_OOPS("%s: invalid hh_prev %p, actual %p\n", \ + (where), (void*)_thh->hh_prev, (void*)_prev); \ + } \ + _bkt_count++; \ + _prev = (char*)(_thh); \ + _thh = _thh->hh_next; \ + } \ + _count += _bkt_count; \ + if ((head)->hh.tbl->buckets[_bkt_i].count != _bkt_count) { \ + HASH_OOPS("%s: invalid bucket count %u, actual %u\n", \ + (where), (head)->hh.tbl->buckets[_bkt_i].count, _bkt_count); \ + } \ + } \ + if (_count != (head)->hh.tbl->num_items) { \ + HASH_OOPS("%s: invalid hh item count %u, actual %u\n", \ + (where), (head)->hh.tbl->num_items, _count); \ + } \ + _count = 0; \ + _prev = NULL; \ + _thh = &(head)->hh; \ + while (_thh) { \ + _count++; \ + if (_prev != (char*)_thh->prev) { \ + HASH_OOPS("%s: invalid prev %p, actual %p\n", \ + (where), (void*)_thh->prev, (void*)_prev); \ + } \ + _prev = (char*)ELMT_FROM_HH((head)->hh.tbl, _thh); \ + _thh = (_thh->next ? HH_FROM_ELMT((head)->hh.tbl, _thh->next) : NULL); \ + } \ + if (_count != (head)->hh.tbl->num_items) { \ + HASH_OOPS("%s: invalid app item count %u, actual %u\n", \ + (where), (head)->hh.tbl->num_items, _count); \ + } \ + } \ +} while (0) +#else +#define HASH_FSCK(hh,head,where) +#endif + +/* When compiled with -DHASH_EMIT_KEYS, length-prefixed keys are emitted to + * the descriptor to which this macro is defined for tuning the hash function. + * The app can #include <unistd.h> to get the prototype for write(2). */ +#ifdef HASH_EMIT_KEYS +#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) \ +do { \ + unsigned _klen = fieldlen; \ + write(HASH_EMIT_KEYS, &_klen, sizeof(_klen)); \ + write(HASH_EMIT_KEYS, keyptr, (unsigned long)fieldlen); \ +} while (0) +#else +#define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) +#endif + +/* default to Jenkin's hash unless overridden e.g. DHASH_FUNCTION=HASH_SAX */ +#ifdef HASH_FUNCTION +#define HASH_FCN HASH_FUNCTION +#else +#define HASH_FCN HASH_JEN +#endif + +/* The Bernstein hash function, used in Perl prior to v5.6. Note (x<<5+x)=x*33. */ +#define HASH_BER(key,keylen,hashv) \ +do { \ + unsigned _hb_keylen = (unsigned)keylen; \ + const unsigned char *_hb_key = (const unsigned char*)(key); \ + (hashv) = 0; \ + while (_hb_keylen-- != 0U) { \ + (hashv) = (((hashv) << 5) + (hashv)) + *_hb_key++; \ + } \ +} while (0) + + +/* SAX/FNV/OAT/JEN hash functions are macro variants of those listed at + * http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx */ +#define HASH_SAX(key,keylen,hashv) \ +do { \ + unsigned _sx_i; \ + const unsigned char *_hs_key = (const unsigned char*)(key); \ + hashv = 0; \ + for (_sx_i=0; _sx_i < keylen; _sx_i++) { \ + hashv ^= (hashv << 5) + (hashv >> 2) + _hs_key[_sx_i]; \ + } \ +} while (0) +/* FNV-1a variation */ +#define HASH_FNV(key,keylen,hashv) \ +do { \ + unsigned _fn_i; \ + const unsigned char *_hf_key = (const unsigned char*)(key); \ + (hashv) = 2166136261U; \ + for (_fn_i=0; _fn_i < keylen; _fn_i++) { \ + hashv = hashv ^ _hf_key[_fn_i]; \ + hashv = hashv * 16777619U; \ + } \ +} while (0) + +#define HASH_OAT(key,keylen,hashv) \ +do { \ + unsigned _ho_i; \ + const unsigned char *_ho_key=(const unsigned char*)(key); \ + hashv = 0; \ + for(_ho_i=0; _ho_i < keylen; _ho_i++) { \ + hashv += _ho_key[_ho_i]; \ + hashv += (hashv << 10); \ + hashv ^= (hashv >> 6); \ + } \ + hashv += (hashv << 3); \ + hashv ^= (hashv >> 11); \ + hashv += (hashv << 15); \ +} while (0) + +#define HASH_JEN_MIX(a,b,c) \ +do { \ + a -= b; a -= c; a ^= ( c >> 13 ); \ + b -= c; b -= a; b ^= ( a << 8 ); \ + c -= a; c -= b; c ^= ( b >> 13 ); \ + a -= b; a -= c; a ^= ( c >> 12 ); \ + b -= c; b -= a; b ^= ( a << 16 ); \ + c -= a; c -= b; c ^= ( b >> 5 ); \ + a -= b; a -= c; a ^= ( c >> 3 ); \ + b -= c; b -= a; b ^= ( a << 10 ); \ + c -= a; c -= b; c ^= ( b >> 15 ); \ +} while (0) + +#define HASH_JEN(key,keylen,hashv) \ +do { \ + unsigned _hj_i,_hj_j,_hj_k; \ + unsigned const char *_hj_key=(unsigned const char*)(key); \ + hashv = 0xfeedbeefu; \ + _hj_i = _hj_j = 0x9e3779b9u; \ + _hj_k = (unsigned)(keylen); \ + while (_hj_k >= 12U) { \ + _hj_i += (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 ) \ + + ( (unsigned)_hj_key[2] << 16 ) \ + + ( (unsigned)_hj_key[3] << 24 ) ); \ + _hj_j += (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 ) \ + + ( (unsigned)_hj_key[6] << 16 ) \ + + ( (unsigned)_hj_key[7] << 24 ) ); \ + hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 ) \ + + ( (unsigned)_hj_key[10] << 16 ) \ + + ( (unsigned)_hj_key[11] << 24 ) ); \ + \ + HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ + \ + _hj_key += 12; \ + _hj_k -= 12U; \ + } \ + hashv += (unsigned)(keylen); \ + switch ( _hj_k ) { \ + case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); /* FALLTHROUGH */ \ + case 10: hashv += ( (unsigned)_hj_key[9] << 16 ); /* FALLTHROUGH */ \ + case 9: hashv += ( (unsigned)_hj_key[8] << 8 ); /* FALLTHROUGH */ \ + case 8: _hj_j += ( (unsigned)_hj_key[7] << 24 ); /* FALLTHROUGH */ \ + case 7: _hj_j += ( (unsigned)_hj_key[6] << 16 ); /* FALLTHROUGH */ \ + case 6: _hj_j += ( (unsigned)_hj_key[5] << 8 ); /* FALLTHROUGH */ \ + case 5: _hj_j += _hj_key[4]; /* FALLTHROUGH */ \ + case 4: _hj_i += ( (unsigned)_hj_key[3] << 24 ); /* FALLTHROUGH */ \ + case 3: _hj_i += ( (unsigned)_hj_key[2] << 16 ); /* FALLTHROUGH */ \ + case 2: _hj_i += ( (unsigned)_hj_key[1] << 8 ); /* FALLTHROUGH */ \ + case 1: _hj_i += _hj_key[0]; \ + } \ + HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ +} while (0) + +/* The Paul Hsieh hash function */ +#undef get16bits +#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \ + || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__) +#define get16bits(d) (*((const uint16_t *) (d))) +#endif + +#if !defined (get16bits) +#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \ + +(uint32_t)(((const uint8_t *)(d))[0]) ) +#endif +#define HASH_SFH(key,keylen,hashv) \ +do { \ + unsigned const char *_sfh_key=(unsigned const char*)(key); \ + uint32_t _sfh_tmp, _sfh_len = (uint32_t)keylen; \ + \ + unsigned _sfh_rem = _sfh_len & 3U; \ + _sfh_len >>= 2; \ + hashv = 0xcafebabeu; \ + \ + /* Main loop */ \ + for (;_sfh_len > 0U; _sfh_len--) { \ + hashv += get16bits (_sfh_key); \ + _sfh_tmp = ((uint32_t)(get16bits (_sfh_key+2)) << 11) ^ hashv; \ + hashv = (hashv << 16) ^ _sfh_tmp; \ + _sfh_key += 2U*sizeof (uint16_t); \ + hashv += hashv >> 11; \ + } \ + \ + /* Handle end cases */ \ + switch (_sfh_rem) { \ + case 3: hashv += get16bits (_sfh_key); \ + hashv ^= hashv << 16; \ + hashv ^= (uint32_t)(_sfh_key[sizeof (uint16_t)]) << 18; \ + hashv += hashv >> 11; \ + break; \ + case 2: hashv += get16bits (_sfh_key); \ + hashv ^= hashv << 11; \ + hashv += hashv >> 17; \ + break; \ + case 1: hashv += *_sfh_key; \ + hashv ^= hashv << 10; \ + hashv += hashv >> 1; \ + } \ + \ + /* Force "avalanching" of final 127 bits */ \ + hashv ^= hashv << 3; \ + hashv += hashv >> 5; \ + hashv ^= hashv << 4; \ + hashv += hashv >> 17; \ + hashv ^= hashv << 25; \ + hashv += hashv >> 6; \ +} while (0) + +#ifdef HASH_USING_NO_STRICT_ALIASING +/* The MurmurHash exploits some CPU's (x86,x86_64) tolerance for unaligned reads. + * For other types of CPU's (e.g. Sparc) an unaligned read causes a bus error. + * MurmurHash uses the faster approach only on CPU's where we know it's safe. + * + * Note the preprocessor built-in defines can be emitted using: + * + * gcc -m64 -dM -E - < /dev/null (on gcc) + * cc -## a.c (where a.c is a simple test file) (Sun Studio) + */ +#if (defined(__i386__) || defined(__x86_64__) || defined(_M_IX86)) +#define MUR_GETBLOCK(p,i) p[i] +#else /* non intel */ +#define MUR_PLUS0_ALIGNED(p) (((unsigned long)p & 3UL) == 0UL) +#define MUR_PLUS1_ALIGNED(p) (((unsigned long)p & 3UL) == 1UL) +#define MUR_PLUS2_ALIGNED(p) (((unsigned long)p & 3UL) == 2UL) +#define MUR_PLUS3_ALIGNED(p) (((unsigned long)p & 3UL) == 3UL) +#define WP(p) ((uint32_t*)((unsigned long)(p) & ~3UL)) +#if (defined(__BIG_ENDIAN__) || defined(SPARC) || defined(__ppc__) || defined(__ppc64__)) +#define MUR_THREE_ONE(p) ((((*WP(p))&0x00ffffff) << 8) | (((*(WP(p)+1))&0xff000000) >> 24)) +#define MUR_TWO_TWO(p) ((((*WP(p))&0x0000ffff) <<16) | (((*(WP(p)+1))&0xffff0000) >> 16)) +#define MUR_ONE_THREE(p) ((((*WP(p))&0x000000ff) <<24) | (((*(WP(p)+1))&0xffffff00) >> 8)) +#else /* assume little endian non-intel */ +#define MUR_THREE_ONE(p) ((((*WP(p))&0xffffff00) >> 8) | (((*(WP(p)+1))&0x000000ff) << 24)) +#define MUR_TWO_TWO(p) ((((*WP(p))&0xffff0000) >>16) | (((*(WP(p)+1))&0x0000ffff) << 16)) +#define MUR_ONE_THREE(p) ((((*WP(p))&0xff000000) >>24) | (((*(WP(p)+1))&0x00ffffff) << 8)) +#endif +#define MUR_GETBLOCK(p,i) (MUR_PLUS0_ALIGNED(p) ? ((p)[i]) : \ + (MUR_PLUS1_ALIGNED(p) ? MUR_THREE_ONE(p) : \ + (MUR_PLUS2_ALIGNED(p) ? MUR_TWO_TWO(p) : \ + MUR_ONE_THREE(p)))) +#endif +#define MUR_ROTL32(x,r) (((x) << (r)) | ((x) >> (32 - (r)))) +#define MUR_FMIX(_h) \ +do { \ + _h ^= _h >> 16; \ + _h *= 0x85ebca6bu; \ + _h ^= _h >> 13; \ + _h *= 0xc2b2ae35u; \ + _h ^= _h >> 16; \ +} while (0) + +#define HASH_MUR(key,keylen,hashv) \ +do { \ + const uint8_t *_mur_data = (const uint8_t*)(key); \ + const int _mur_nblocks = (int)(keylen) / 4; \ + uint32_t _mur_h1 = 0xf88D5353u; \ + uint32_t _mur_c1 = 0xcc9e2d51u; \ + uint32_t _mur_c2 = 0x1b873593u; \ + uint32_t _mur_k1 = 0; \ + const uint8_t *_mur_tail; \ + const uint32_t *_mur_blocks = (const uint32_t*)(_mur_data+(_mur_nblocks*4)); \ + int _mur_i; \ + for (_mur_i = -_mur_nblocks; _mur_i != 0; _mur_i++) { \ + _mur_k1 = MUR_GETBLOCK(_mur_blocks,_mur_i); \ + _mur_k1 *= _mur_c1; \ + _mur_k1 = MUR_ROTL32(_mur_k1,15); \ + _mur_k1 *= _mur_c2; \ + \ + _mur_h1 ^= _mur_k1; \ + _mur_h1 = MUR_ROTL32(_mur_h1,13); \ + _mur_h1 = (_mur_h1*5U) + 0xe6546b64u; \ + } \ + _mur_tail = (const uint8_t*)(_mur_data + (_mur_nblocks*4)); \ + _mur_k1=0; \ + switch ((keylen) & 3U) { \ + case 0: break; \ + case 3: _mur_k1 ^= (uint32_t)_mur_tail[2] << 16; /* FALLTHROUGH */ \ + case 2: _mur_k1 ^= (uint32_t)_mur_tail[1] << 8; /* FALLTHROUGH */ \ + case 1: _mur_k1 ^= (uint32_t)_mur_tail[0]; \ + _mur_k1 *= _mur_c1; \ + _mur_k1 = MUR_ROTL32(_mur_k1,15); \ + _mur_k1 *= _mur_c2; \ + _mur_h1 ^= _mur_k1; \ + } \ + _mur_h1 ^= (uint32_t)(keylen); \ + MUR_FMIX(_mur_h1); \ + hashv = _mur_h1; \ +} while (0) +#endif /* HASH_USING_NO_STRICT_ALIASING */ + +/* iterate over items in a known bucket to find desired item */ +#define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,hashval,out) \ +do { \ + if ((head).hh_head != NULL) { \ + DECLTYPE_ASSIGN(out, ELMT_FROM_HH(tbl, (head).hh_head)); \ + } else { \ + (out) = NULL; \ + } \ + while ((out) != NULL) { \ + if ((out)->hh.hashv == (hashval) && (out)->hh.keylen == (keylen_in)) { \ + if (uthash_memcmp((out)->hh.key, keyptr, keylen_in) == 0) { \ + break; \ + } \ + } \ + if ((out)->hh.hh_next != NULL) { \ + DECLTYPE_ASSIGN(out, ELMT_FROM_HH(tbl, (out)->hh.hh_next)); \ + } else { \ + (out) = NULL; \ + } \ + } \ +} while (0) + +/* add an item to a bucket */ +#define HASH_ADD_TO_BKT(head,hh,addhh,oomed) \ +do { \ + UT_hash_bucket *_ha_head = &(head); \ + _ha_head->count++; \ + (addhh)->hh_next = _ha_head->hh_head; \ + (addhh)->hh_prev = NULL; \ + if (_ha_head->hh_head != NULL) { \ + _ha_head->hh_head->hh_prev = (addhh); \ + } \ + _ha_head->hh_head = (addhh); \ + if ((_ha_head->count >= ((_ha_head->expand_mult + 1U) * HASH_BKT_CAPACITY_THRESH)) \ + && !(addhh)->tbl->noexpand) { \ + HASH_EXPAND_BUCKETS(addhh,(addhh)->tbl, oomed); \ + IF_HASH_NONFATAL_OOM( \ + if (oomed) { \ + HASH_DEL_IN_BKT(head,addhh); \ + } \ + ) \ + } \ +} while (0) + +/* remove an item from a given bucket */ +#define HASH_DEL_IN_BKT(head,delhh) \ +do { \ + UT_hash_bucket *_hd_head = &(head); \ + _hd_head->count--; \ + if (_hd_head->hh_head == (delhh)) { \ + _hd_head->hh_head = (delhh)->hh_next; \ + } \ + if ((delhh)->hh_prev) { \ + (delhh)->hh_prev->hh_next = (delhh)->hh_next; \ + } \ + if ((delhh)->hh_next) { \ + (delhh)->hh_next->hh_prev = (delhh)->hh_prev; \ + } \ +} while (0) + +/* Bucket expansion has the effect of doubling the number of buckets + * and redistributing the items into the new buckets. Ideally the + * items will distribute more or less evenly into the new buckets + * (the extent to which this is true is a measure of the quality of + * the hash function as it applies to the key domain). + * + * With the items distributed into more buckets, the chain length + * (item count) in each bucket is reduced. Thus by expanding buckets + * the hash keeps a bound on the chain length. This bounded chain + * length is the essence of how a hash provides constant time lookup. + * + * The calculation of tbl->ideal_chain_maxlen below deserves some + * explanation. First, keep in mind that we're calculating the ideal + * maximum chain length based on the *new* (doubled) bucket count. + * In fractions this is just n/b (n=number of items,b=new num buckets). + * Since the ideal chain length is an integer, we want to calculate + * ceil(n/b). We don't depend on floating point arithmetic in this + * hash, so to calculate ceil(n/b) with integers we could write + * + * ceil(n/b) = (n/b) + ((n%b)?1:0) + * + * and in fact a previous version of this hash did just that. + * But now we have improved things a bit by recognizing that b is + * always a power of two. We keep its base 2 log handy (call it lb), + * so now we can write this with a bit shift and logical AND: + * + * ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0) + * + */ +#define HASH_EXPAND_BUCKETS(hh,tbl,oomed) \ +do { \ + unsigned _he_bkt; \ + unsigned _he_bkt_i; \ + struct UT_hash_handle *_he_thh, *_he_hh_nxt; \ + UT_hash_bucket *_he_new_buckets, *_he_newbkt; \ + _he_new_buckets = (UT_hash_bucket*)uthash_malloc( \ + 2UL * (tbl)->num_buckets * sizeof(struct UT_hash_bucket)); \ + if (!_he_new_buckets) { \ + HASH_RECORD_OOM(oomed); \ + } else { \ + uthash_bzero(_he_new_buckets, \ + 2UL * (tbl)->num_buckets * sizeof(struct UT_hash_bucket)); \ + (tbl)->ideal_chain_maxlen = \ + ((tbl)->num_items >> ((tbl)->log2_num_buckets+1U)) + \ + ((((tbl)->num_items & (((tbl)->num_buckets*2U)-1U)) != 0U) ? 1U : 0U); \ + (tbl)->nonideal_items = 0; \ + for (_he_bkt_i = 0; _he_bkt_i < (tbl)->num_buckets; _he_bkt_i++) { \ + _he_thh = (tbl)->buckets[ _he_bkt_i ].hh_head; \ + while (_he_thh != NULL) { \ + _he_hh_nxt = _he_thh->hh_next; \ + HASH_TO_BKT(_he_thh->hashv, (tbl)->num_buckets * 2U, _he_bkt); \ + _he_newbkt = &(_he_new_buckets[_he_bkt]); \ + if (++(_he_newbkt->count) > (tbl)->ideal_chain_maxlen) { \ + (tbl)->nonideal_items++; \ + _he_newbkt->expand_mult = _he_newbkt->count / (tbl)->ideal_chain_maxlen; \ + } \ + _he_thh->hh_prev = NULL; \ + _he_thh->hh_next = _he_newbkt->hh_head; \ + if (_he_newbkt->hh_head != NULL) { \ + _he_newbkt->hh_head->hh_prev = _he_thh; \ + } \ + _he_newbkt->hh_head = _he_thh; \ + _he_thh = _he_hh_nxt; \ + } \ + } \ + uthash_free((tbl)->buckets, (tbl)->num_buckets * sizeof(struct UT_hash_bucket)); \ + (tbl)->num_buckets *= 2U; \ + (tbl)->log2_num_buckets++; \ + (tbl)->buckets = _he_new_buckets; \ + (tbl)->ineff_expands = ((tbl)->nonideal_items > ((tbl)->num_items >> 1)) ? \ + ((tbl)->ineff_expands+1U) : 0U; \ + if ((tbl)->ineff_expands > 1U) { \ + (tbl)->noexpand = 1; \ + uthash_noexpand_fyi(tbl); \ + } \ + uthash_expand_fyi(tbl); \ + } \ +} while (0) + + +/* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */ +/* Note that HASH_SORT assumes the hash handle name to be hh. + * HASH_SRT was added to allow the hash handle name to be passed in. */ +#define HASH_SORT(head,cmpfcn) HASH_SRT(hh,head,cmpfcn) +#define HASH_SRT(hh,head,cmpfcn) \ +do { \ + unsigned _hs_i; \ + unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize; \ + struct UT_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail; \ + if (head != NULL) { \ + _hs_insize = 1; \ + _hs_looping = 1; \ + _hs_list = &((head)->hh); \ + while (_hs_looping != 0U) { \ + _hs_p = _hs_list; \ + _hs_list = NULL; \ + _hs_tail = NULL; \ + _hs_nmerges = 0; \ + while (_hs_p != NULL) { \ + _hs_nmerges++; \ + _hs_q = _hs_p; \ + _hs_psize = 0; \ + for (_hs_i = 0; _hs_i < _hs_insize; ++_hs_i) { \ + _hs_psize++; \ + _hs_q = ((_hs_q->next != NULL) ? \ + HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL); \ + if (_hs_q == NULL) { \ + break; \ + } \ + } \ + _hs_qsize = _hs_insize; \ + while ((_hs_psize != 0U) || ((_hs_qsize != 0U) && (_hs_q != NULL))) { \ + if (_hs_psize == 0U) { \ + _hs_e = _hs_q; \ + _hs_q = ((_hs_q->next != NULL) ? \ + HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL); \ + _hs_qsize--; \ + } else if ((_hs_qsize == 0U) || (_hs_q == NULL)) { \ + _hs_e = _hs_p; \ + if (_hs_p != NULL) { \ + _hs_p = ((_hs_p->next != NULL) ? \ + HH_FROM_ELMT((head)->hh.tbl, _hs_p->next) : NULL); \ + } \ + _hs_psize--; \ + } else if ((cmpfcn( \ + DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl, _hs_p)), \ + DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl, _hs_q)) \ + )) <= 0) { \ + _hs_e = _hs_p; \ + if (_hs_p != NULL) { \ + _hs_p = ((_hs_p->next != NULL) ? \ + HH_FROM_ELMT((head)->hh.tbl, _hs_p->next) : NULL); \ + } \ + _hs_psize--; \ + } else { \ + _hs_e = _hs_q; \ + _hs_q = ((_hs_q->next != NULL) ? \ + HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL); \ + _hs_qsize--; \ + } \ + if ( _hs_tail != NULL ) { \ + _hs_tail->next = ((_hs_e != NULL) ? \ + ELMT_FROM_HH((head)->hh.tbl, _hs_e) : NULL); \ + } else { \ + _hs_list = _hs_e; \ + } \ + if (_hs_e != NULL) { \ + _hs_e->prev = ((_hs_tail != NULL) ? \ + ELMT_FROM_HH((head)->hh.tbl, _hs_tail) : NULL); \ + } \ + _hs_tail = _hs_e; \ + } \ + _hs_p = _hs_q; \ + } \ + if (_hs_tail != NULL) { \ + _hs_tail->next = NULL; \ + } \ + if (_hs_nmerges <= 1U) { \ + _hs_looping = 0; \ + (head)->hh.tbl->tail = _hs_tail; \ + DECLTYPE_ASSIGN(head, ELMT_FROM_HH((head)->hh.tbl, _hs_list)); \ + } \ + _hs_insize *= 2U; \ + } \ + HASH_FSCK(hh, head, "HASH_SRT"); \ + } \ +} while (0) + +/* This function selects items from one hash into another hash. + * The end result is that the selected items have dual presence + * in both hashes. There is no copy of the items made; rather + * they are added into the new hash through a secondary hash + * hash handle that must be present in the structure. */ +#define HASH_SELECT(hh_dst, dst, hh_src, src, cond) \ +do { \ + unsigned _src_bkt, _dst_bkt; \ + void *_last_elt = NULL, *_elt; \ + UT_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL; \ + ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst)); \ + if ((src) != NULL) { \ + for (_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) { \ + for (_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head; \ + _src_hh != NULL; \ + _src_hh = _src_hh->hh_next) { \ + _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh); \ + if (cond(_elt)) { \ + IF_HASH_NONFATAL_OOM( int _hs_oomed = 0; ) \ + _dst_hh = (UT_hash_handle*)(((char*)_elt) + _dst_hho); \ + _dst_hh->key = _src_hh->key; \ + _dst_hh->keylen = _src_hh->keylen; \ + _dst_hh->hashv = _src_hh->hashv; \ + _dst_hh->prev = _last_elt; \ + _dst_hh->next = NULL; \ + if (_last_elt_hh != NULL) { \ + _last_elt_hh->next = _elt; \ + } \ + if ((dst) == NULL) { \ + DECLTYPE_ASSIGN(dst, _elt); \ + HASH_MAKE_TABLE(hh_dst, dst, _hs_oomed); \ + IF_HASH_NONFATAL_OOM( \ + if (_hs_oomed) { \ + uthash_nonfatal_oom(_elt); \ + (dst) = NULL; \ + continue; \ + } \ + ) \ + } else { \ + _dst_hh->tbl = (dst)->hh_dst.tbl; \ + } \ + HASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt); \ + HASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt], hh_dst, _dst_hh, _hs_oomed); \ + (dst)->hh_dst.tbl->num_items++; \ + IF_HASH_NONFATAL_OOM( \ + if (_hs_oomed) { \ + HASH_ROLLBACK_BKT(hh_dst, dst, _dst_hh); \ + HASH_DELETE_HH(hh_dst, dst, _dst_hh); \ + _dst_hh->tbl = NULL; \ + uthash_nonfatal_oom(_elt); \ + continue; \ + } \ + ) \ + HASH_BLOOM_ADD(_dst_hh->tbl, _dst_hh->hashv); \ + _last_elt = _elt; \ + _last_elt_hh = _dst_hh; \ + } \ + } \ + } \ + } \ + HASH_FSCK(hh_dst, dst, "HASH_SELECT"); \ +} while (0) + +#define HASH_CLEAR(hh,head) \ +do { \ + if ((head) != NULL) { \ + HASH_BLOOM_FREE((head)->hh.tbl); \ + uthash_free((head)->hh.tbl->buckets, \ + (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket)); \ + uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ + (head) = NULL; \ + } \ +} while (0) + +#define HASH_OVERHEAD(hh,head) \ + (((head) != NULL) ? ( \ + (size_t)(((head)->hh.tbl->num_items * sizeof(UT_hash_handle)) + \ + ((head)->hh.tbl->num_buckets * sizeof(UT_hash_bucket)) + \ + sizeof(UT_hash_table) + \ + (HASH_BLOOM_BYTELEN))) : 0U) + +#ifdef NO_DECLTYPE +#define HASH_ITER(hh,head,el,tmp) \ +for(((el)=(head)), ((*(char**)(&(tmp)))=(char*)((head!=NULL)?(head)->hh.next:NULL)); \ + (el) != NULL; ((el)=(tmp)), ((*(char**)(&(tmp)))=(char*)((tmp!=NULL)?(tmp)->hh.next:NULL))) +#else +#define HASH_ITER(hh,head,el,tmp) \ +for(((el)=(head)), ((tmp)=DECLTYPE(el)((head!=NULL)?(head)->hh.next:NULL)); \ + (el) != NULL; ((el)=(tmp)), ((tmp)=DECLTYPE(el)((tmp!=NULL)?(tmp)->hh.next:NULL))) +#endif + +/* obtain a count of items in the hash */ +#define HASH_COUNT(head) HASH_CNT(hh,head) +#define HASH_CNT(hh,head) ((head != NULL)?((head)->hh.tbl->num_items):0U) + +typedef struct UT_hash_bucket { + struct UT_hash_handle *hh_head; + unsigned count; + + /* expand_mult is normally set to 0. In this situation, the max chain length + * threshold is enforced at its default value, HASH_BKT_CAPACITY_THRESH. (If + * the bucket's chain exceeds this length, bucket expansion is triggered). + * However, setting expand_mult to a non-zero value delays bucket expansion + * (that would be triggered by additions to this particular bucket) + * until its chain length reaches a *multiple* of HASH_BKT_CAPACITY_THRESH. + * (The multiplier is simply expand_mult+1). The whole idea of this + * multiplier is to reduce bucket expansions, since they are expensive, in + * situations where we know that a particular bucket tends to be overused. + * It is better to let its chain length grow to a longer yet-still-bounded + * value, than to do an O(n) bucket expansion too often. + */ + unsigned expand_mult; + +} UT_hash_bucket; + +/* random signature used only to find hash tables in external analysis */ +#define HASH_SIGNATURE 0xa0111fe1u +#define HASH_BLOOM_SIGNATURE 0xb12220f2u + +typedef struct UT_hash_table { + UT_hash_bucket *buckets; + unsigned num_buckets, log2_num_buckets; + unsigned num_items; + struct UT_hash_handle *tail; /* tail hh in app order, for fast append */ + ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */ + + /* in an ideal situation (all buckets used equally), no bucket would have + * more than ceil(#items/#buckets) items. that's the ideal chain length. */ + unsigned ideal_chain_maxlen; + + /* nonideal_items is the number of items in the hash whose chain position + * exceeds the ideal chain maxlen. these items pay the penalty for an uneven + * hash distribution; reaching them in a chain traversal takes >ideal steps */ + unsigned nonideal_items; + + /* ineffective expands occur when a bucket doubling was performed, but + * afterward, more than half the items in the hash had nonideal chain + * positions. If this happens on two consecutive expansions we inhibit any + * further expansion, as it's not helping; this happens when the hash + * function isn't a good fit for the key domain. When expansion is inhibited + * the hash will still work, albeit no longer in constant time. */ + unsigned ineff_expands, noexpand; + + uint32_t signature; /* used only to find hash tables in external analysis */ +#ifdef HASH_BLOOM + uint32_t bloom_sig; /* used only to test bloom exists in external analysis */ + uint8_t *bloom_bv; + uint8_t bloom_nbits; +#endif + +} UT_hash_table; + +typedef struct UT_hash_handle { + struct UT_hash_table *tbl; + void *prev; /* prev element in app order */ + void *next; /* next element in app order */ + struct UT_hash_handle *hh_prev; /* previous hh in bucket order */ + struct UT_hash_handle *hh_next; /* next hh in bucket order */ + void *key; /* ptr to enclosing struct's key */ + unsigned keylen; /* enclosing struct's key len */ + unsigned hashv; /* result of hash-fcn(key) */ +} UT_hash_handle; + +#endif /* UTHASH_H */ |