summaryrefslogtreecommitdiff
path: root/compat
diff options
context:
space:
mode:
authorBen Woods <woodsb02@FreeBSD.org>2022-08-29 07:04:52 +0000
committerBen Woods <woodsb02@FreeBSD.org>2022-08-29 07:27:36 +0000
commit96dba636abec6d5451820add99300bda2ca6d86a (patch)
tree4ed81d7e264f23333e2f3943b849aa007ec484fa /compat
Import dhcpcd 9.4.1vendor/dhcpcd/9.4.1
Approved by: philip Differential Revision: https://reviews.freebsd.org/D36196
Diffstat (limited to 'compat')
-rw-r--r--compat/_strtoi.h97
-rw-r--r--compat/arc4random.c173
-rw-r--r--compat/arc4random.h16
-rw-r--r--compat/arc4random_uniform.c56
-rw-r--r--compat/arc4random_uniform.h23
-rw-r--r--compat/bitops.h188
-rw-r--r--compat/consttime_memequal.h28
-rw-r--r--compat/crypt/hmac.c191
-rw-r--r--compat/crypt/hmac.h40
-rw-r--r--compat/crypt/md5.c242
-rw-r--r--compat/crypt/md5.h33
-rw-r--r--compat/crypt/sha256.c303
-rw-r--r--compat/crypt/sha256.h46
-rw-r--r--compat/dprintf.c64
-rw-r--r--compat/dprintf.h43
-rw-r--r--compat/endian.h71
-rw-r--r--compat/pidfile.c271
-rw-r--r--compat/pidfile.h39
-rw-r--r--compat/queue.h175
-rw-r--r--compat/rb.c1346
-rw-r--r--compat/rbtree.h211
-rw-r--r--compat/reallocarray.c60
-rw-r--r--compat/reallocarray.h37
-rw-r--r--compat/setproctitle.c331
-rw-r--r--compat/setproctitle.h58
-rw-r--r--compat/strlcpy.c51
-rw-r--r--compat/strlcpy.h24
-rw-r--r--compat/strtoi.c68
-rw-r--r--compat/strtoi.h45
-rw-r--r--compat/strtou.c68
30 files changed, 4398 insertions, 0 deletions
diff --git a/compat/_strtoi.h b/compat/_strtoi.h
new file mode 100644
index 000000000000..fcbd18f9b344
--- /dev/null
+++ b/compat/_strtoi.h
@@ -0,0 +1,97 @@
+/* $NetBSD: _strtoi.h,v 1.1 2015/01/22 02:15:59 christos Exp $ */
+
+/*-
+ * Copyright (c) 1990, 1993
+ * The Regents of the University of California. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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.
+ *
+ * Original version ID:
+ * NetBSD: src/lib/libc/locale/_wcstoul.h,v 1.2 2003/08/07 16:43:03 agc Exp
+ *
+ * Created by Kamil Rytarowski, based on ID:
+ * NetBSD: src/common/lib/libc/stdlib/_strtoul.h,v 1.7 2013/05/17 12:55:56 joerg Exp
+ */
+
+#ifndef _STRTOI_H
+#define _STRTOI_H
+
+/*
+ * function template for strtoi and strtou
+ *
+ * parameters:
+ * _FUNCNAME : function name
+ * __TYPE : return and range limits type
+ * __WRAPPED : wrapped function, strtoimax or strtoumax
+ */
+
+__TYPE
+_FUNCNAME(const char * __restrict nptr, char ** __restrict endptr, int base,
+ __TYPE lo, __TYPE hi, int * rstatus)
+{
+ int serrno;
+ __TYPE im;
+ char *ep;
+ int rep;
+
+ /* endptr may be NULL */
+
+ if (endptr == NULL)
+ endptr = &ep;
+
+ if (rstatus == NULL)
+ rstatus = &rep;
+
+ serrno = errno;
+ errno = 0;
+
+ im = __WRAPPED(nptr, endptr, base);
+
+ *rstatus = errno;
+ errno = serrno;
+
+ if (*rstatus == 0) {
+ /* No digits were found */
+ if (nptr == *endptr)
+ *rstatus = ECANCELED;
+ /* There are further characters after number */
+ else if (**endptr != '\0')
+ *rstatus = ENOTSUP;
+ }
+
+ if (im < lo) {
+ if (*rstatus == 0)
+ *rstatus = ERANGE;
+ return lo;
+ }
+ if (im > hi) {
+ if (*rstatus == 0)
+ *rstatus = ERANGE;
+ return hi;
+ }
+
+ return im;
+}
+#endif
diff --git a/compat/arc4random.c b/compat/arc4random.c
new file mode 100644
index 000000000000..90098127c954
--- /dev/null
+++ b/compat/arc4random.c
@@ -0,0 +1,173 @@
+/*
+ * Arc4 random number generator for OpenBSD.
+ * Copyright 1996 David Mazieres <dm@lcs.mit.edu>.
+ *
+ * Modification and redistribution in source and binary forms is
+ * permitted provided that due credit is given to the author and the
+ * OpenBSD project by leaving this copyright notice intact.
+ */
+
+/*
+ * This code is derived from section 17.1 of Applied Cryptography,
+ * second edition, which describes a stream cipher allegedly
+ * compatible with RSA Labs "RC4" cipher (the actual description of
+ * which is a trade secret). The same algorithm is used as a stream
+ * cipher called "arcfour" in Tatu Ylonen's ssh package.
+ *
+ * Here the stream cipher has been modified always to include the time
+ * when initializing the state. That makes it impossible to
+ * regenerate the same random sequence twice, so this can't be used
+ * for encryption, but will generate good random numbers.
+ *
+ * RC4 is a registered trademark of RSA Laboratories.
+ */
+
+#include <sys/time.h>
+
+#include <fcntl.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+#include "arc4random.h"
+
+struct arc4_stream {
+ uint8_t i;
+ uint8_t j;
+ uint8_t s[256];
+ size_t count;
+ pid_t stir_pid;
+ int fd;
+};
+
+#define S(n) (n)
+#define S4(n) S(n), S(n + 1), S(n + 2), S(n + 3)
+#define S16(n) S4(n), S4(n + 4), S4(n + 8), S4(n + 12)
+#define S64(n) S16(n), S16(n + 16), S16(n + 32), S16(n + 48)
+#define S256 S64(0), S64(64), S64(128), S64(192)
+
+static struct arc4_stream rs = { .i = 0xff, .j = 0, .s = { S256 },
+ .count = 0, .stir_pid = 0, .fd = -1 };
+
+#undef S
+#undef S4
+#undef S16
+#undef S64
+#undef S256
+
+static void
+arc4_addrandom(struct arc4_stream *as, unsigned char *dat, int datlen)
+{
+ int n;
+ uint8_t si;
+
+ as->i--;
+ for (n = 0; n < 256; n++) {
+ as->i = (uint8_t)(as->i + 1);
+ si = as->s[as->i];
+ as->j = (uint8_t)(as->j + si + dat[n % datlen]);
+ as->s[as->i] = as->s[as->j];
+ as->s[as->j] = si;
+ }
+ as->j = as->i;
+}
+
+static uint8_t
+arc4_getbyte(struct arc4_stream *as)
+{
+ uint8_t si, sj;
+
+ as->i = (uint8_t)(as->i + 1);
+ si = as->s[as->i];
+ as->j = (uint8_t)(as->j + si);
+ sj = as->s[as->j];
+ as->s[as->i] = sj;
+ as->s[as->j] = si;
+ return (as->s[(si + sj) & 0xff]);
+}
+
+static uint32_t
+arc4_getword(struct arc4_stream *as)
+{
+ int val;
+
+ val = (int)((unsigned int)arc4_getbyte(as) << 24);
+ val |= arc4_getbyte(as) << 16;
+ val |= arc4_getbyte(as) << 8;
+ val |= arc4_getbyte(as);
+ return (uint32_t)val;
+}
+
+/* We don't care about any error on read, just use what we have
+ * on the stack. So mask off this GCC warning. */
+#pragma GCC diagnostic ignored "-Wunused-result"
+static void
+arc4_stir(struct arc4_stream *as)
+{
+ struct {
+ struct timeval tv;
+ unsigned int rnd[(128 - sizeof(struct timeval)) /
+ sizeof(unsigned int)];
+ } rdat;
+ size_t n;
+
+ gettimeofday(&rdat.tv, NULL);
+ if (as->fd == -1) {
+#ifndef O_CLOEXEC
+ int fd_opts;
+#endif
+
+ as->fd = open("/dev/urandom", O_RDONLY | O_NONBLOCK
+#ifdef O_CLOEXEC
+ | O_CLOEXEC
+#endif
+ );
+#ifndef O_CLOEXEC
+ if (as->fd != -1 &&
+ (fd_opts = fcntl(as->fd, F_GETFD)))
+ fcntl(as->fd, F_SETFD, fd_opts | FD_CLOEXEC);
+#endif
+ }
+
+ if (as->fd != -1) {
+ /* If there is an error reading, just use what is
+ * on the stack. */
+ /* coverity[check_return] */
+ (void)read(as->fd, rdat.rnd, sizeof(rdat.rnd));
+ }
+
+ /* fd < 0? Ah, what the heck. We'll just take
+ * whatever was on the stack... */
+ /* coverity[uninit_use_in_call] */
+ arc4_addrandom(as, (void *) &rdat, sizeof(rdat));
+
+ /*
+ * Throw away the first N words of output, as suggested in the
+ * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
+ * by Fluher, Mantin, and Shamir. (N = 256 in our case.)
+ */
+ for (n = 0; n < 256 * sizeof(uint32_t); n++)
+ arc4_getbyte(as);
+ as->count = 1600000;
+}
+
+static void
+arc4_stir_if_needed(struct arc4_stream *as)
+{
+ pid_t pid;
+
+ pid = getpid();
+ if (as->count <= sizeof(uint32_t) || as->stir_pid != pid) {
+ as->stir_pid = pid;
+ arc4_stir(as);
+ } else
+ as->count -= sizeof(uint32_t);
+}
+
+uint32_t
+arc4random()
+{
+
+ arc4_stir_if_needed(&rs);
+ return arc4_getword(&rs);
+}
diff --git a/compat/arc4random.h b/compat/arc4random.h
new file mode 100644
index 000000000000..a975fef3cd1b
--- /dev/null
+++ b/compat/arc4random.h
@@ -0,0 +1,16 @@
+/*
+ * Arc4 random number generator for OpenBSD.
+ * Copyright 1996 David Mazieres <dm@lcs.mit.edu>.
+ *
+ * Modification and redistribution in source and binary forms is
+ * permitted provided that due credit is given to the author and the
+ * OpenBSD project by leaving this copyright notice intact.
+ */
+
+#ifndef ARC4RANDOM_H
+#define ARC4RANDOM_H
+
+#include <stdint.h>
+
+uint32_t arc4random(void);
+#endif
diff --git a/compat/arc4random_uniform.c b/compat/arc4random_uniform.c
new file mode 100644
index 000000000000..0f1b7b296759
--- /dev/null
+++ b/compat/arc4random_uniform.c
@@ -0,0 +1,56 @@
+/*
+ * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <stdint.h>
+#include <stdlib.h>
+
+/* We need to include config.h so we pickup either the system arc4random
+ * or our compat one. */
+#include "config.h"
+
+/*
+ * Calculate a uniformly distributed random number less than upper_bound
+ * avoiding "modulo bias".
+ *
+ * Uniformity is achieved by generating new random numbers until the one
+ * returned is outside the range [0, 2**32 % upper_bound). This
+ * guarantees the selected random number will be inside
+ * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
+ * after reduction modulo upper_bound.
+ */
+uint32_t
+arc4random_uniform(uint32_t upper_bound)
+{
+ uint32_t r, min;
+
+ if (upper_bound < 2)
+ return 0;
+
+ /* 2**32 % x == (2**32 - x) % x */
+ min = -upper_bound % upper_bound;
+
+ /*
+ * This could theoretically loop forever but each retry has
+ * p > 0.5 (worst case, usually far better) of selecting a
+ * number inside the range we need, so it should rarely need
+ * to re-roll.
+ */
+ do
+ r = arc4random();
+ while (r < min);
+
+ return r % upper_bound;
+}
diff --git a/compat/arc4random_uniform.h b/compat/arc4random_uniform.h
new file mode 100644
index 000000000000..d7c0a35d4cba
--- /dev/null
+++ b/compat/arc4random_uniform.h
@@ -0,0 +1,23 @@
+/*
+ * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifndef ARC4RANDOM_UNIFORM_H
+#define ARC4RANDOM_UNIFORM_H
+
+#include <stdint.h>
+
+uint32_t arc4random_uniform(uint32_t);
+#endif
diff --git a/compat/bitops.h b/compat/bitops.h
new file mode 100644
index 000000000000..31979a20f458
--- /dev/null
+++ b/compat/bitops.h
@@ -0,0 +1,188 @@
+/* $NetBSD: bitops.h,v 1.11 2012/12/07 02:27:58 christos Exp $ */
+
+/*-
+ * Copyright (c) 2007, 2010 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to The NetBSD Foundation
+ * by Christos Zoulas and Joerg Sonnenberger.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef COMPAT_BITOPS_H
+#define COMPAT_BITOPS_H
+
+#include <stdint.h>
+#include "common.h"
+
+/*
+ * Find First Set functions
+ */
+#ifndef ffs32
+static inline int __unused
+ffs32(uint32_t _n)
+{
+ int _v;
+
+ if (!_n)
+ return 0;
+
+ _v = 1;
+ if ((_n & 0x0000FFFFU) == 0) {
+ _n >>= 16;
+ _v += 16;
+ }
+ if ((_n & 0x000000FFU) == 0) {
+ _n >>= 8;
+ _v += 8;
+ }
+ if ((_n & 0x0000000FU) == 0) {
+ _n >>= 4;
+ _v += 4;
+ }
+ if ((_n & 0x00000003U) == 0) {
+ _n >>= 2;
+ _v += 2;
+ }
+ if ((_n & 0x00000001U) == 0) {
+ //_n >>= 1;
+ _v += 1;
+ }
+ return _v;
+}
+#endif
+
+#ifndef ffs64
+static inline int __unused
+ffs64(uint64_t _n)
+{
+ int _v;
+
+ if (!_n)
+ return 0;
+
+ _v = 1;
+ if ((_n & 0x00000000FFFFFFFFULL) == 0) {
+ _n >>= 32;
+ _v += 32;
+ }
+ if ((_n & 0x000000000000FFFFULL) == 0) {
+ _n >>= 16;
+ _v += 16;
+ }
+ if ((_n & 0x00000000000000FFULL) == 0) {
+ _n >>= 8;
+ _v += 8;
+ }
+ if ((_n & 0x000000000000000FULL) == 0) {
+ _n >>= 4;
+ _v += 4;
+ }
+ if ((_n & 0x0000000000000003ULL) == 0) {
+ _n >>= 2;
+ _v += 2;
+ }
+ if ((_n & 0x0000000000000001ULL) == 0) {
+ //_n >>= 1;
+ _v += 1;
+ }
+ return _v;
+}
+#endif
+
+/*
+ * Find Last Set functions
+ */
+#ifndef fls32
+static __inline int __unused
+fls32(uint32_t _n)
+{
+ int _v;
+
+ if (!_n)
+ return 0;
+
+ _v = 32;
+ if ((_n & 0xFFFF0000U) == 0) {
+ _n <<= 16;
+ _v -= 16;
+ }
+ if ((_n & 0xFF000000U) == 0) {
+ _n <<= 8;
+ _v -= 8;
+ }
+ if ((_n & 0xF0000000U) == 0) {
+ _n <<= 4;
+ _v -= 4;
+ }
+ if ((_n & 0xC0000000U) == 0) {
+ _n <<= 2;
+ _v -= 2;
+ }
+ if ((_n & 0x80000000U) == 0) {
+ //_n <<= 1;
+ _v -= 1;
+ }
+ return _v;
+}
+#endif
+
+#ifndef fls64
+static int __unused
+fls64(uint64_t _n)
+{
+ int _v;
+
+ if (!_n)
+ return 0;
+
+ _v = 64;
+ if ((_n & 0xFFFFFFFF00000000ULL) == 0) {
+ _n <<= 32;
+ _v -= 32;
+ }
+ if ((_n & 0xFFFF000000000000ULL) == 0) {
+ _n <<= 16;
+ _v -= 16;
+ }
+ if ((_n & 0xFF00000000000000ULL) == 0) {
+ _n <<= 8;
+ _v -= 8;
+ }
+ if ((_n & 0xF000000000000000ULL) == 0) {
+ _n <<= 4;
+ _v -= 4;
+ }
+ if ((_n & 0xC000000000000000ULL) == 0) {
+ _n <<= 2;
+ _v -= 2;
+ }
+ if ((_n & 0x8000000000000000ULL) == 0) {
+ //_n <<= 1;
+ _v -= 1;
+ }
+ return _v;
+}
+#endif
+
+#endif /* COMPAT_BITOPS_H_ */
diff --git a/compat/consttime_memequal.h b/compat/consttime_memequal.h
new file mode 100644
index 000000000000..983064841075
--- /dev/null
+++ b/compat/consttime_memequal.h
@@ -0,0 +1,28 @@
+/*
+ * Written by Matthias Drochner <drochner@NetBSD.org>.
+ * Public domain.
+ */
+
+#ifndef CONSTTIME_MEMEQUAL_H
+#define CONSTTIME_MEMEQUAL_H
+inline static int
+consttime_memequal(const void *b1, const void *b2, size_t len)
+{
+ const unsigned char *c1 = b1, *c2 = b2;
+ unsigned int res = 0;
+
+ while (len--)
+ res |= *c1++ ^ *c2++;
+
+ /*
+ * Map 0 to 1 and [1, 256) to 0 using only constant-time
+ * arithmetic.
+ *
+ * This is not simply `!res' because although many CPUs support
+ * branchless conditional moves and many compilers will take
+ * advantage of them, certain compilers generate branches on
+ * certain CPUs for `!res'.
+ */
+ return (1 & ((res - 1) >> 8));
+}
+#endif /* CONSTTIME_MEMEQUAL_H */
diff --git a/compat/crypt/hmac.c b/compat/crypt/hmac.c
new file mode 100644
index 000000000000..55e331ffa021
--- /dev/null
+++ b/compat/crypt/hmac.c
@@ -0,0 +1,191 @@
+/* $NetBSD: hmac.c,v 1.5 2017/10/05 09:59:04 roy Exp $ */
+
+/*-
+ * Copyright (c) 2016 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to The NetBSD Foundation
+ * by Christos Zoulas.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <string.h>
+#include <stdlib.h>
+
+#include "config.h"
+
+#if defined(HAVE_MD5_H) && !defined(DEPGEN)
+#include <md5.h>
+#endif
+
+#ifdef SHA2_H
+# include SHA2_H
+#endif
+
+#ifndef __arraycount
+#define __arraycount(__x) (sizeof(__x) / sizeof(__x[0]))
+#endif
+
+#if 0
+#include <md2.h>
+#include <md4.h>
+#include <md5.h>
+#include <rmd160.h>
+#include <sha1.h>
+#include <sha2.h>
+#endif
+
+#ifndef MD5_BLOCK_LENGTH
+#define MD5_BLOCK_LENGTH 64
+#endif
+#ifndef SHA256_BLOCK_LENGTH
+#define SHA256_BLOCK_LENGTH 64
+#endif
+
+#define HMAC_SIZE 128
+#define HMAC_IPAD 0x36
+#define HMAC_OPAD 0x5C
+
+static const struct hmac {
+ const char *name;
+ size_t ctxsize;
+ size_t digsize;
+ size_t blocksize;
+ void (*init)(void *);
+ void (*update)(void *, const uint8_t *, unsigned int);
+ void (*final)(uint8_t *, void *);
+} hmacs[] = {
+#if 0
+ {
+ "md2", sizeof(MD2_CTX), MD2_DIGEST_LENGTH, MD2_BLOCK_LENGTH,
+ (void *)MD2Init, (void *)MD2Update, (void *)MD2Final,
+ },
+ {
+ "md4", sizeof(MD4_CTX), MD4_DIGEST_LENGTH, MD4_BLOCK_LENGTH,
+ (void *)MD4Init, (void *)MD4Update, (void *)MD4Final,
+ },
+#endif
+ {
+ "md5", sizeof(MD5_CTX), MD5_DIGEST_LENGTH, MD5_BLOCK_LENGTH,
+ (void *)MD5Init, (void *)MD5Update, (void *)MD5Final,
+ },
+#if 0
+ {
+ "rmd160", sizeof(RMD160_CTX), RMD160_DIGEST_LENGTH,
+ RMD160_BLOCK_LENGTH,
+ (void *)RMD160Init, (void *)RMD160Update, (void *)RMD160Final,
+ },
+ {
+ "sha1", sizeof(SHA1_CTX), SHA1_DIGEST_LENGTH, SHA1_BLOCK_LENGTH,
+ (void *)SHA1Init, (void *)SHA1Update, (void *)SHA1Final,
+ },
+ {
+ "sha224", sizeof(SHA224_CTX), SHA224_DIGEST_LENGTH,
+ SHA224_BLOCK_LENGTH,
+ (void *)SHA224_Init, (void *)SHA224_Update,
+ (void *)SHA224_Final,
+ },
+#endif
+ {
+ "sha256", sizeof(SHA256_CTX), SHA256_DIGEST_LENGTH,
+ SHA256_BLOCK_LENGTH,
+ (void *)SHA256_Init, (void *)SHA256_Update,
+ (void *)SHA256_Final,
+ },
+#if 0
+ {
+ "sha384", sizeof(SHA384_CTX), SHA384_DIGEST_LENGTH,
+ SHA384_BLOCK_LENGTH,
+ (void *)SHA384_Init, (void *)SHA384_Update,
+ (void *)SHA384_Final,
+ },
+ {
+ "sha512", sizeof(SHA512_CTX), SHA512_DIGEST_LENGTH,
+ SHA512_BLOCK_LENGTH,
+ (void *)SHA512_Init, (void *)SHA512_Update,
+ (void *)SHA512_Final,
+ },
+#endif
+};
+
+static const struct hmac *
+hmac_find(const char *name)
+{
+ for (size_t i = 0; i < __arraycount(hmacs); i++) {
+ if (strcmp(hmacs[i].name, name) != 0)
+ continue;
+ return &hmacs[i];
+ }
+ return NULL;
+}
+
+ssize_t
+hmac(const char *name,
+ const void *key, size_t klen,
+ const void *text, size_t tlen,
+ void *digest, size_t dlen)
+{
+ uint8_t ipad[HMAC_SIZE], opad[HMAC_SIZE], d[HMAC_SIZE];
+ const uint8_t *k = key;
+ const struct hmac *h;
+ uint64_t c[32];
+ void *p;
+
+ if ((h = hmac_find(name)) == NULL)
+ return -1;
+
+
+ if (klen > h->blocksize) {
+ (*h->init)(c);
+ (*h->update)(c, k, (unsigned int)klen);
+ (*h->final)(d, c);
+ k = (void *)d;
+ klen = h->digsize;
+ }
+
+ /* Form input and output pads for the digests */
+ for (size_t i = 0; i < sizeof(ipad); i++) {
+ ipad[i] = (i < klen ? k[i] : 0) ^ HMAC_IPAD;
+ opad[i] = (i < klen ? k[i] : 0) ^ HMAC_OPAD;
+ }
+
+ p = dlen >= h->digsize ? digest : d;
+ if (p != digest) {
+ memcpy(p, digest, dlen);
+ memset((char *)p + dlen, 0, h->digsize - dlen);
+ }
+ (*h->init)(c);
+ (*h->update)(c, ipad, (unsigned int)h->blocksize);
+ (*h->update)(c, text, (unsigned int)tlen);
+ (*h->final)(p, c);
+
+ (*h->init)(c);
+ (*h->update)(c, opad, (unsigned int)h->blocksize);
+ (*h->update)(c, digest, (unsigned int)h->digsize);
+ (*h->final)(p, c);
+
+ if (p != digest)
+ memcpy(digest, p, dlen);
+
+ return (ssize_t)h->digsize;
+}
diff --git a/compat/crypt/hmac.h b/compat/crypt/hmac.h
new file mode 100644
index 000000000000..af3f77adb025
--- /dev/null
+++ b/compat/crypt/hmac.h
@@ -0,0 +1,40 @@
+/* $NetBSD: hmac.c,v 1.5 2017/10/05 09:59:04 roy Exp $ */
+
+/*-
+ * Copyright (c) 2016 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to The NetBSD Foundation
+ * by Christos Zoulas.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef HMAC_H
+#define HMAC_H
+
+#include <sys/types.h>
+
+ssize_t hmac(const char *, const void *, size_t, const void *, size_t, void *,
+ size_t);
+
+#endif
diff --git a/compat/crypt/md5.c b/compat/crypt/md5.c
new file mode 100644
index 000000000000..dea2356de76d
--- /dev/null
+++ b/compat/crypt/md5.c
@@ -0,0 +1,242 @@
+/*
+ * This code implements the MD5 message-digest algorithm.
+ * The algorithm is due to Ron Rivest. This code was
+ * written by Colin Plumb in 1993, no copyright is claimed.
+ * This code is in the public domain; do with it what you wish.
+ *
+ * Equivalent code is available from RSA Data Security, Inc.
+ * This code has been tested against that, and is equivalent,
+ * except that you don't need to include two pages of legalese
+ * with every copy.
+ *
+ * To compute the message digest of a chunk of bytes, declare an
+ * MD5Context structure, pass it to MD5Init, call MD5Update as
+ * needed on buffers full of bytes, and then call MD5Final, which
+ * will fill a supplied 16-byte array with the digest.
+ */
+
+#include <sys/param.h>
+#include <inttypes.h>
+
+#include <string.h>
+
+#include "md5.h"
+
+#define PUT_64BIT_LE(cp, value) do { \
+ (cp)[7] = (uint8_t)((value) >> 56); \
+ (cp)[6] = (uint8_t)((value) >> 48); \
+ (cp)[5] = (uint8_t)((value) >> 40); \
+ (cp)[4] = (uint8_t)((value) >> 32); \
+ (cp)[3] = (uint8_t)((value) >> 24); \
+ (cp)[2] = (uint8_t)((value) >> 16); \
+ (cp)[1] = (uint8_t)((value) >> 8); \
+ (cp)[0] = (uint8_t)(value); } while (0)
+
+#define PUT_32BIT_LE(cp, value) do { \
+ (cp)[3] = (uint8_t)((value) >> 24); \
+ (cp)[2] = (uint8_t)((value) >> 16); \
+ (cp)[1] = (uint8_t)((value) >> 8); \
+ (cp)[0] = (uint8_t)(value); } while (0)
+
+static uint8_t PADDING[MD5_BLOCK_LENGTH] = {
+ 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
+};
+
+/*
+ * Start MD5 accumulation. Set bit count to 0 and buffer to mysterious
+ * initialization constants.
+ */
+void
+MD5Init(MD5_CTX *ctx)
+{
+ ctx->count = 0;
+ ctx->state[0] = 0x67452301;
+ ctx->state[1] = 0xefcdab89;
+ ctx->state[2] = 0x98badcfe;
+ ctx->state[3] = 0x10325476;
+}
+
+
+/* The four core functions - F1 is optimized somewhat */
+
+/* #define F1(x, y, z) (x & y | ~x & z) */
+#define F1(x, y, z) (z ^ (x & (y ^ z)))
+#define F2(x, y, z) F1(z, x, y)
+#define F3(x, y, z) (x ^ y ^ z)
+#define F4(x, y, z) (y ^ (x | ~z))
+
+/* This is the central step in the MD5 algorithm. */
+#define MD5STEP(f, w, x, y, z, data, s) \
+ ( w += f(x, y, z) + data, w = w<<s | w>>(32-s), w += x )
+
+/*
+ * The core of the MD5 algorithm, this alters an existing MD5 hash to
+ * reflect the addition of 16 longwords of new data. MD5Update blocks
+ * the data and converts bytes into longwords for this routine.
+ */
+static void
+MD5Transform(uint32_t state[4], const uint8_t block[MD5_BLOCK_LENGTH])
+{
+ uint32_t a, b, c, d, in[MD5_BLOCK_LENGTH / 4];
+
+#if BYTE_ORDER == LITTLE_ENDIAN
+ memcpy(in, block, sizeof(in));
+#else
+ for (a = 0; a < MD5_BLOCK_LENGTH / 4; a++) {
+ in[a] = (uint32_t)(
+ (uint32_t)(block[a * 4 + 0]) |
+ (uint32_t)(block[a * 4 + 1]) << 8 |
+ (uint32_t)(block[a * 4 + 2]) << 16 |
+ (uint32_t)(block[a * 4 + 3]) << 24);
+ }
+#endif
+
+ a = state[0];
+ b = state[1];
+ c = state[2];
+ d = state[3];
+
+ MD5STEP(F1, a, b, c, d, in[ 0] + 0xd76aa478, 7);
+ MD5STEP(F1, d, a, b, c, in[ 1] + 0xe8c7b756, 12);
+ MD5STEP(F1, c, d, a, b, in[ 2] + 0x242070db, 17);
+ MD5STEP(F1, b, c, d, a, in[ 3] + 0xc1bdceee, 22);
+ MD5STEP(F1, a, b, c, d, in[ 4] + 0xf57c0faf, 7);
+ MD5STEP(F1, d, a, b, c, in[ 5] + 0x4787c62a, 12);
+ MD5STEP(F1, c, d, a, b, in[ 6] + 0xa8304613, 17);
+ MD5STEP(F1, b, c, d, a, in[ 7] + 0xfd469501, 22);
+ MD5STEP(F1, a, b, c, d, in[ 8] + 0x698098d8, 7);
+ MD5STEP(F1, d, a, b, c, in[ 9] + 0x8b44f7af, 12);
+ MD5STEP(F1, c, d, a, b, in[10] + 0xffff5bb1, 17);
+ MD5STEP(F1, b, c, d, a, in[11] + 0x895cd7be, 22);
+ MD5STEP(F1, a, b, c, d, in[12] + 0x6b901122, 7);
+ MD5STEP(F1, d, a, b, c, in[13] + 0xfd987193, 12);
+ MD5STEP(F1, c, d, a, b, in[14] + 0xa679438e, 17);
+ MD5STEP(F1, b, c, d, a, in[15] + 0x49b40821, 22);
+
+ MD5STEP(F2, a, b, c, d, in[ 1] + 0xf61e2562, 5);
+ MD5STEP(F2, d, a, b, c, in[ 6] + 0xc040b340, 9);
+ MD5STEP(F2, c, d, a, b, in[11] + 0x265e5a51, 14);
+ MD5STEP(F2, b, c, d, a, in[ 0] + 0xe9b6c7aa, 20);
+ MD5STEP(F2, a, b, c, d, in[ 5] + 0xd62f105d, 5);
+ MD5STEP(F2, d, a, b, c, in[10] + 0x02441453, 9);
+ MD5STEP(F2, c, d, a, b, in[15] + 0xd8a1e681, 14);
+ MD5STEP(F2, b, c, d, a, in[ 4] + 0xe7d3fbc8, 20);
+ MD5STEP(F2, a, b, c, d, in[ 9] + 0x21e1cde6, 5);
+ MD5STEP(F2, d, a, b, c, in[14] + 0xc33707d6, 9);
+ MD5STEP(F2, c, d, a, b, in[ 3] + 0xf4d50d87, 14);
+ MD5STEP(F2, b, c, d, a, in[ 8] + 0x455a14ed, 20);
+ MD5STEP(F2, a, b, c, d, in[13] + 0xa9e3e905, 5);
+ MD5STEP(F2, d, a, b, c, in[ 2] + 0xfcefa3f8, 9);
+ MD5STEP(F2, c, d, a, b, in[ 7] + 0x676f02d9, 14);
+ MD5STEP(F2, b, c, d, a, in[12] + 0x8d2a4c8a, 20);
+
+ MD5STEP(F3, a, b, c, d, in[ 5] + 0xfffa3942, 4);
+ MD5STEP(F3, d, a, b, c, in[ 8] + 0x8771f681, 11);
+ MD5STEP(F3, c, d, a, b, in[11] + 0x6d9d6122, 16);
+ MD5STEP(F3, b, c, d, a, in[14] + 0xfde5380c, 23);
+ MD5STEP(F3, a, b, c, d, in[ 1] + 0xa4beea44, 4);
+ MD5STEP(F3, d, a, b, c, in[ 4] + 0x4bdecfa9, 11);
+ MD5STEP(F3, c, d, a, b, in[ 7] + 0xf6bb4b60, 16);
+ MD5STEP(F3, b, c, d, a, in[10] + 0xbebfbc70, 23);
+ MD5STEP(F3, a, b, c, d, in[13] + 0x289b7ec6, 4);
+ MD5STEP(F3, d, a, b, c, in[ 0] + 0xeaa127fa, 11);
+ MD5STEP(F3, c, d, a, b, in[ 3] + 0xd4ef3085, 16);
+ MD5STEP(F3, b, c, d, a, in[ 6] + 0x04881d05, 23);
+ MD5STEP(F3, a, b, c, d, in[ 9] + 0xd9d4d039, 4);
+ MD5STEP(F3, d, a, b, c, in[12] + 0xe6db99e5, 11);
+ MD5STEP(F3, c, d, a, b, in[15] + 0x1fa27cf8, 16);
+ MD5STEP(F3, b, c, d, a, in[2 ] + 0xc4ac5665, 23);
+
+ MD5STEP(F4, a, b, c, d, in[ 0] + 0xf4292244, 6);
+ MD5STEP(F4, d, a, b, c, in[7 ] + 0x432aff97, 10);
+ MD5STEP(F4, c, d, a, b, in[14] + 0xab9423a7, 15);
+ MD5STEP(F4, b, c, d, a, in[5 ] + 0xfc93a039, 21);
+ MD5STEP(F4, a, b, c, d, in[12] + 0x655b59c3, 6);
+ MD5STEP(F4, d, a, b, c, in[3 ] + 0x8f0ccc92, 10);
+ MD5STEP(F4, c, d, a, b, in[10] + 0xffeff47d, 15);
+ MD5STEP(F4, b, c, d, a, in[1 ] + 0x85845dd1, 21);
+ MD5STEP(F4, a, b, c, d, in[8 ] + 0x6fa87e4f, 6);
+ MD5STEP(F4, d, a, b, c, in[15] + 0xfe2ce6e0, 10);
+ MD5STEP(F4, c, d, a, b, in[6 ] + 0xa3014314, 15);
+ MD5STEP(F4, b, c, d, a, in[13] + 0x4e0811a1, 21);
+ MD5STEP(F4, a, b, c, d, in[4 ] + 0xf7537e82, 6);
+ MD5STEP(F4, d, a, b, c, in[11] + 0xbd3af235, 10);
+ MD5STEP(F4, c, d, a, b, in[2 ] + 0x2ad7d2bb, 15);
+ MD5STEP(F4, b, c, d, a, in[9 ] + 0xeb86d391, 21);
+
+ state[0] += a;
+ state[1] += b;
+ state[2] += c;
+ state[3] += d;
+}
+
+/*
+ * Update context to reflect the concatenation of another buffer full
+ * of bytes.
+ */
+void
+MD5Update(MD5_CTX *ctx, const unsigned char *input, size_t len)
+{
+ size_t have, need;
+
+ /* Check how many bytes we already have and how many more we need. */
+ have = (size_t)((ctx->count >> 3) & (MD5_BLOCK_LENGTH - 1));
+ need = MD5_BLOCK_LENGTH - have;
+
+ /* Update bitcount */
+ ctx->count += (uint64_t)len << 3;
+
+ if (len >= need) {
+ if (have != 0) {
+ memcpy(ctx->buffer + have, input, need);
+ MD5Transform(ctx->state, ctx->buffer);
+ input += need;
+ len -= need;
+ have = 0;
+ }
+
+ /* Process data in MD5_BLOCK_LENGTH-byte chunks. */
+ while (len >= MD5_BLOCK_LENGTH) {
+ MD5Transform(ctx->state, input);
+ input += MD5_BLOCK_LENGTH;
+ len -= MD5_BLOCK_LENGTH;
+ }
+ }
+
+ /* Handle any remaining bytes of data. */
+ if (len != 0)
+ memcpy(ctx->buffer + have, input, len);
+}
+
+/*
+ * Final wrapup - pad to 64-byte boundary with the bit pattern
+ * 1 0* (64-bit count of bits processed, MSB-first)
+ */
+void
+MD5Final(unsigned char digest[MD5_DIGEST_LENGTH], MD5_CTX *ctx)
+{
+ uint8_t count[8];
+ size_t padlen;
+ int i;
+
+ /* Convert count to 8 bytes in little endian order. */
+ PUT_64BIT_LE(count, ctx->count);
+
+ /* Pad out to 56 mod 64. */
+ padlen = MD5_BLOCK_LENGTH -
+ ((ctx->count >> 3) & (MD5_BLOCK_LENGTH - 1));
+ if (padlen < 1 + 8)
+ padlen += MD5_BLOCK_LENGTH;
+ MD5Update(ctx, PADDING, padlen - 8); /* padlen - 8 <= 64 */
+ MD5Update(ctx, count, 8);
+
+ if (digest != NULL) {
+ for (i = 0; i < 4; i++)
+ PUT_32BIT_LE(digest + i * 4, ctx->state[i]);
+ }
+ memset(ctx, 0, sizeof(*ctx)); /* in case it's sensitive */
+}
+
+
diff --git a/compat/crypt/md5.h b/compat/crypt/md5.h
new file mode 100644
index 000000000000..dd156163315c
--- /dev/null
+++ b/compat/crypt/md5.h
@@ -0,0 +1,33 @@
+/*
+ * This code implements the MD5 message-digest algorithm.
+ * The algorithm is due to Ron Rivest. This code was
+ * written by Colin Plumb in 1993, no copyright is claimed.
+ * This code is in the public domain; do with it what you wish.
+ *
+ * Equivalent code is available from RSA Data Security, Inc.
+ * This code has been tested against that, and is equivalent,
+ * except that you don't need to include two pages of legalese
+ * with every copy.
+ *
+ * To compute the message digest of a chunk of bytes, declare an
+ * MD5Context structure, pass it to MD5Init, call MD5Update as
+ * needed on buffers full of bytes, and then call MD5Final, which
+ * will fill a supplied 16-byte array with the digest.
+ */
+
+#ifndef MD5_H_
+#define MD5_H_
+
+#define MD5_DIGEST_LENGTH 16
+#define MD5_BLOCK_LENGTH 64ULL
+
+typedef struct MD5Context {
+ uint32_t state[4]; /* state (ABCD) */
+ uint64_t count; /* number of bits, modulo 2^64 (lsb first) */
+ unsigned char buffer[MD5_BLOCK_LENGTH]; /* input buffer */
+} MD5_CTX;
+
+void MD5Init(MD5_CTX *);
+void MD5Update(MD5_CTX *, const unsigned char *, size_t);
+void MD5Final(unsigned char[MD5_DIGEST_LENGTH], MD5_CTX *);
+#endif
diff --git a/compat/crypt/sha256.c b/compat/crypt/sha256.c
new file mode 100644
index 000000000000..73c43c037fa2
--- /dev/null
+++ b/compat/crypt/sha256.c
@@ -0,0 +1,303 @@
+/*-
+ * Copyright 2005 Colin Percival
+ * 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 AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <inttypes.h>
+
+#include <string.h>
+
+#ifdef __GLIBC__
+# include <endian.h>
+#endif
+#ifdef BSD
+# ifndef __QNX__
+# include <sys/endian.h>
+# endif
+#endif
+
+#include "config.h"
+#include "sha256.h"
+
+#if BYTE_ORDER == BIG_ENDIAN
+
+/* Copy a vector of big-endian uint32_t into a vector of bytes */
+#define be32enc_vect(dst, src, len) \
+ memcpy((void *)dst, (const void *)src, (size_t)len)
+
+/* Copy a vector of bytes into a vector of big-endian uint32_t */
+#define be32dec_vect(dst, src, len) \
+ memcpy((void *)dst, (const void *)src, (size_t)len)
+
+#else /* BYTE_ORDER != BIG_ENDIAN */
+
+/*
+ * Encode a length len/4 vector of (uint32_t) into a length len vector of
+ * (unsigned char) in big-endian form. Assumes len is a multiple of 4.
+ */
+static void
+be32enc_vect(unsigned char *dst, const uint32_t *src, size_t len)
+{
+ size_t i;
+
+ for (i = 0; i < len / 4; i++)
+ be32enc(dst + i * 4, src[i]);
+}
+
+/*
+ * Decode a big-endian length len vector of (unsigned char) into a length
+ * len/4 vector of (uint32_t). Assumes len is a multiple of 4.
+ */
+static void
+be32dec_vect(uint32_t *dst, const unsigned char *src, size_t len)
+{
+ size_t i;
+
+ for (i = 0; i < len / 4; i++)
+ dst[i] = be32dec(src + i * 4);
+}
+
+#endif /* BYTE_ORDER != BIG_ENDIAN */
+
+/* Elementary functions used by SHA256 */
+#define Ch(x, y, z) ((x & (y ^ z)) ^ z)
+#define Maj(x, y, z) ((x & (y | z)) | (y & z))
+#define SHR(x, n) (x >> n)
+#define ROTR(x, n) ((x >> n) | (x << (32 - n)))
+#define S0(x) (ROTR(x, 2) ^ ROTR(x, 13) ^ ROTR(x, 22))
+#define S1(x) (ROTR(x, 6) ^ ROTR(x, 11) ^ ROTR(x, 25))
+#define s0(x) (ROTR(x, 7) ^ ROTR(x, 18) ^ SHR(x, 3))
+#define s1(x) (ROTR(x, 17) ^ ROTR(x, 19) ^ SHR(x, 10))
+
+/* SHA256 round function */
+#define RND(a, b, c, d, e, f, g, h, k) \
+ t0 = h + S1(e) + Ch(e, f, g) + k; \
+ t1 = S0(a) + Maj(a, b, c); \
+ d += t0; \
+ h = t0 + t1;
+
+/* Adjusted round function for rotating state */
+#define RNDr(S, W, i, k) \
+ RND(S[(64 - i) % 8], S[(65 - i) % 8], \
+ S[(66 - i) % 8], S[(67 - i) % 8], \
+ S[(68 - i) % 8], S[(69 - i) % 8], \
+ S[(70 - i) % 8], S[(71 - i) % 8], \
+ W[i] + k)
+
+/*
+ * SHA256 block compression function. The 256-bit state is transformed via
+ * the 512-bit input block to produce a new state.
+ */
+static void
+SHA256_Transform(uint32_t * state, const unsigned char block[64])
+{
+ uint32_t W[64];
+ uint32_t S[8];
+ uint32_t t0, t1;
+ int i;
+
+ /* 1. Prepare message schedule W. */
+ be32dec_vect(W, block, 64);
+ for (i = 16; i < 64; i++)
+ W[i] = s1(W[i - 2]) + W[i - 7] + s0(W[i - 15]) + W[i - 16];
+
+ /* 2. Initialize working variables. */
+ memcpy(S, state, 32);
+
+ /* 3. Mix. */
+ RNDr(S, W, 0, 0x428a2f98);
+ RNDr(S, W, 1, 0x71374491);
+ RNDr(S, W, 2, 0xb5c0fbcf);
+ RNDr(S, W, 3, 0xe9b5dba5);
+ RNDr(S, W, 4, 0x3956c25b);
+ RNDr(S, W, 5, 0x59f111f1);
+ RNDr(S, W, 6, 0x923f82a4);
+ RNDr(S, W, 7, 0xab1c5ed5);
+ RNDr(S, W, 8, 0xd807aa98);
+ RNDr(S, W, 9, 0x12835b01);
+ RNDr(S, W, 10, 0x243185be);
+ RNDr(S, W, 11, 0x550c7dc3);
+ RNDr(S, W, 12, 0x72be5d74);
+ RNDr(S, W, 13, 0x80deb1fe);
+ RNDr(S, W, 14, 0x9bdc06a7);
+ RNDr(S, W, 15, 0xc19bf174);
+ RNDr(S, W, 16, 0xe49b69c1);
+ RNDr(S, W, 17, 0xefbe4786);
+ RNDr(S, W, 18, 0x0fc19dc6);
+ RNDr(S, W, 19, 0x240ca1cc);
+ RNDr(S, W, 20, 0x2de92c6f);
+ RNDr(S, W, 21, 0x4a7484aa);
+ RNDr(S, W, 22, 0x5cb0a9dc);
+ RNDr(S, W, 23, 0x76f988da);
+ RNDr(S, W, 24, 0x983e5152);
+ RNDr(S, W, 25, 0xa831c66d);
+ RNDr(S, W, 26, 0xb00327c8);
+ RNDr(S, W, 27, 0xbf597fc7);
+ RNDr(S, W, 28, 0xc6e00bf3);
+ RNDr(S, W, 29, 0xd5a79147);
+ RNDr(S, W, 30, 0x06ca6351);
+ RNDr(S, W, 31, 0x14292967);
+ RNDr(S, W, 32, 0x27b70a85);
+ RNDr(S, W, 33, 0x2e1b2138);
+ RNDr(S, W, 34, 0x4d2c6dfc);
+ RNDr(S, W, 35, 0x53380d13);
+ RNDr(S, W, 36, 0x650a7354);
+ RNDr(S, W, 37, 0x766a0abb);
+ RNDr(S, W, 38, 0x81c2c92e);
+ RNDr(S, W, 39, 0x92722c85);
+ RNDr(S, W, 40, 0xa2bfe8a1);
+ RNDr(S, W, 41, 0xa81a664b);
+ RNDr(S, W, 42, 0xc24b8b70);
+ RNDr(S, W, 43, 0xc76c51a3);
+ RNDr(S, W, 44, 0xd192e819);
+ RNDr(S, W, 45, 0xd6990624);
+ RNDr(S, W, 46, 0xf40e3585);
+ RNDr(S, W, 47, 0x106aa070);
+ RNDr(S, W, 48, 0x19a4c116);
+ RNDr(S, W, 49, 0x1e376c08);
+ RNDr(S, W, 50, 0x2748774c);
+ RNDr(S, W, 51, 0x34b0bcb5);
+ RNDr(S, W, 52, 0x391c0cb3);
+ RNDr(S, W, 53, 0x4ed8aa4a);
+ RNDr(S, W, 54, 0x5b9cca4f);
+ RNDr(S, W, 55, 0x682e6ff3);
+ RNDr(S, W, 56, 0x748f82ee);
+ RNDr(S, W, 57, 0x78a5636f);
+ RNDr(S, W, 58, 0x84c87814);
+ RNDr(S, W, 59, 0x8cc70208);
+ RNDr(S, W, 60, 0x90befffa);
+ RNDr(S, W, 61, 0xa4506ceb);
+ RNDr(S, W, 62, 0xbef9a3f7);
+ RNDr(S, W, 63, 0xc67178f2);
+
+ /* 4. Mix local working variables into global state */
+ for (i = 0; i < 8; i++)
+ state[i] += S[i];
+}
+
+static unsigned char PAD[64] = {
+ 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
+};
+
+/* Add padding and terminating bit-count. */
+static void
+SHA256_Pad(SHA256_CTX * ctx)
+{
+ unsigned char len[8];
+ uint32_t r, plen;
+
+ /*
+ * Convert length to a vector of bytes -- we do this now rather
+ * than later because the length will change after we pad.
+ */
+ be64enc(len, ctx->count);
+
+ /* Add 1--64 bytes so that the resulting length is 56 mod 64 */
+ r = (ctx->count >> 3) & 0x3f;
+ plen = (r < 56) ? (56 - r) : (120 - r);
+ SHA256_Update(ctx, PAD, (size_t)plen);
+
+ /* Add the terminating bit-count */
+ SHA256_Update(ctx, len, 8);
+}
+
+/* SHA-256 initialization. Begins a SHA-256 operation. */
+void
+SHA256_Init(SHA256_CTX * ctx)
+{
+
+ /* Zero bits processed so far */
+ ctx->count = 0;
+
+ /* Magic initialization constants */
+ ctx->state[0] = 0x6A09E667;
+ ctx->state[1] = 0xBB67AE85;
+ ctx->state[2] = 0x3C6EF372;
+ ctx->state[3] = 0xA54FF53A;
+ ctx->state[4] = 0x510E527F;
+ ctx->state[5] = 0x9B05688C;
+ ctx->state[6] = 0x1F83D9AB;
+ ctx->state[7] = 0x5BE0CD19;
+}
+
+/* Add bytes into the hash */
+void
+SHA256_Update(SHA256_CTX * ctx, const void *in, size_t len)
+{
+ uint64_t bitlen;
+ uint32_t r;
+ const unsigned char *src = in;
+
+ /* Number of bytes left in the buffer from previous updates */
+ r = (ctx->count >> 3) & 0x3f;
+
+ /* Convert the length into a number of bits */
+ bitlen = len << 3;
+
+ /* Update number of bits */
+ ctx->count += bitlen;
+
+ /* Handle the case where we don't need to perform any transforms */
+ if (len < 64 - r) {
+ memcpy(&ctx->buf[r], src, len);
+ return;
+ }
+
+ /* Finish the current block */
+ memcpy(&ctx->buf[r], src, 64 - r);
+ SHA256_Transform(ctx->state, ctx->buf);
+ src += 64 - r;
+ len -= 64 - r;
+
+ /* Perform complete blocks */
+ while (len >= 64) {
+ SHA256_Transform(ctx->state, src);
+ src += 64;
+ len -= 64;
+ }
+
+ /* Copy left over data into buffer */
+ memcpy(ctx->buf, src, len);
+}
+
+/*
+ * SHA-256 finalization. Pads the input data, exports the hash value,
+ * and clears the context state.
+ */
+void
+SHA256_Final(unsigned char digest[32], SHA256_CTX * ctx)
+{
+
+ /* Add padding */
+ SHA256_Pad(ctx);
+
+ /* Write the hash */
+ be32enc_vect(digest, ctx->state, 32);
+
+ /* Clear the context state */
+ memset((void *)ctx, 0, sizeof(*ctx));
+}
diff --git a/compat/crypt/sha256.h b/compat/crypt/sha256.h
new file mode 100644
index 000000000000..02a09f935b20
--- /dev/null
+++ b/compat/crypt/sha256.h
@@ -0,0 +1,46 @@
+/*-
+ * Copyright 2005 Colin Percival
+ * 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 AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+
+#ifndef SHA256_H_
+#define SHA256_H_
+
+#include <sys/types.h>
+
+#define SHA256_DIGEST_LENGTH 32
+
+typedef struct SHA256Context {
+ uint32_t state[8];
+ uint64_t count;
+ unsigned char buf[64];
+} SHA256_CTX;
+
+void SHA256_Init(SHA256_CTX *);
+void SHA256_Update(SHA256_CTX *, const void *, size_t);
+void SHA256_Final(unsigned char [32], SHA256_CTX *);
+
+#endif
diff --git a/compat/dprintf.c b/compat/dprintf.c
new file mode 100644
index 000000000000..2ef81ade814b
--- /dev/null
+++ b/compat/dprintf.c
@@ -0,0 +1,64 @@
+/*
+ * dhcpcd - DHCP client daemon
+ * Copyright (c) 2006-2017 Roy Marples <roy@marples.name>
+ * 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 AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdarg.h>
+#include <unistd.h>
+
+#include "dprintf.h"
+
+int
+vdprintf(int fd, const char * __restrict fmt, va_list va)
+{
+ int e;
+ FILE *fp;
+
+ if ((e = dup(fd)) == -1)
+ return -1;
+
+ if ((fp = fdopen(e, "a")) == NULL) {
+ close(e);
+ return -1;
+ }
+
+ e = vfprintf(fp, fmt, va);
+ fclose(fp);
+ return e;
+}
+
+int
+dprintf(int fd, const char * __restrict fmt, ...)
+{
+ int e;
+ va_list va;
+
+ va_start(va, fmt);
+ e = vdprintf(fd, fmt, va);
+ va_end(va);
+ return e;
+}
diff --git a/compat/dprintf.h b/compat/dprintf.h
new file mode 100644
index 000000000000..9defbcb835ff
--- /dev/null
+++ b/compat/dprintf.h
@@ -0,0 +1,43 @@
+/*
+ * dhcpcd - DHCP client daemon
+ * Copyright (c) 2006-2017 Roy Marples <roy@marples.name>
+ * 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 AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#ifndef DPRINTF_H
+#define DPRINTF_H
+
+#include <stdarg.h>
+
+#ifndef __printflike
+# if __GNUC__ > 2 || defined(__INTEL_COMPILER)
+# define __printflike(a, b) __attribute__((format(printf, a, b)))
+# else
+# define __printflike(a, b)
+# endif
+#endif
+
+__printflike(2, 0) int vdprintf(int, const char * __restrict, va_list);
+__printflike(2, 3) int dprintf(int, const char * __restrict, ...);
+#endif
diff --git a/compat/endian.h b/compat/endian.h
new file mode 100644
index 000000000000..8d01738bd242
--- /dev/null
+++ b/compat/endian.h
@@ -0,0 +1,71 @@
+/*
+ * dhcpcd - DHCP client daemon
+ * Copyright (c) 2006-2014 Roy Marples <roy@marples.name>
+ * 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 AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#ifndef ENDIAN_H
+#define ENDIAN_H
+
+#include <stdint.h>
+
+inline static void
+be32enc(uint8_t *buf, uint32_t u)
+{
+
+ buf[0] = (uint8_t)((u >> 24) & 0xff);
+ buf[1] = (uint8_t)((u >> 16) & 0xff);
+ buf[2] = (uint8_t)((u >> 8) & 0xff);
+ buf[3] = (uint8_t)(u & 0xff);
+}
+
+inline static void
+be64enc(uint8_t *buf, uint64_t u)
+{
+
+ be32enc(buf, (uint32_t)(u >> 32));
+ be32enc(buf + sizeof(uint32_t), (uint32_t)(u & 0xffffffffULL));
+}
+
+inline static uint16_t
+be16dec(const uint8_t *buf)
+{
+
+ return (uint16_t)(buf[0] << 8 | buf[1]);
+}
+
+inline static uint32_t
+be32dec(const uint8_t *buf)
+{
+
+ return (uint32_t)((uint32_t)be16dec(buf) << 16 | be16dec(buf + 2));
+}
+
+inline static uint64_t
+be64dec(const uint8_t *buf)
+{
+
+ return (uint64_t)((uint64_t)be32dec(buf) << 32 | be32dec(buf + 4));
+}
+#endif
diff --git a/compat/pidfile.c b/compat/pidfile.c
new file mode 100644
index 000000000000..9dfd9c468a7a
--- /dev/null
+++ b/compat/pidfile.c
@@ -0,0 +1,271 @@
+/* $NetBSD: pidfile.c,v 1.14 2016/04/12 20:40:43 roy Exp $ */
+
+/*-
+ * Copyright (c) 1999, 2016 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to The NetBSD Foundation
+ * by Jason R. Thorpe, Matthias Scheler, Julio Merino and Roy Marples.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <sys/param.h>
+
+#include <errno.h>
+#include <fcntl.h>
+#include <inttypes.h>
+#include <limits.h>
+#include <paths.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <unistd.h>
+
+#include <sys/file.h> /* for flock(2) */
+#include "config.h"
+#include "defs.h"
+
+static pid_t pidfile_pid;
+static char pidfile_path[PATH_MAX];
+static int pidfile_fd = -1;
+
+/* Closes pidfile resources.
+ *
+ * Returns 0 on success, otherwise -1. */
+static int
+pidfile_close(void)
+{
+ int error;
+
+ pidfile_pid = 0;
+ error = close(pidfile_fd);
+ pidfile_fd = -1;
+ pidfile_path[0] = '\0';
+ return error;
+}
+
+/* Truncate, close and unlink an existent pidfile,
+ * if and only if it was created by this process.
+ * The pidfile is truncated because we may have dropped permissions
+ * or entered a chroot and thus unable to unlink it.
+ *
+ * Returns 0 on truncation success, otherwise -1. */
+int
+pidfile_clean(void)
+{
+ int error;
+
+ if (pidfile_fd == -1) {
+ errno = EBADF;
+ return -1;
+ }
+
+ if (pidfile_pid != getpid())
+ error = EPERM;
+ else if (ftruncate(pidfile_fd, 0) == -1)
+ error = errno;
+ else {
+#ifndef HAVE_PLEDGE /* Avoid a pledge violating segfault. */
+ (void)unlink(pidfile_path);
+#endif
+ error = 0;
+ }
+
+ (void) pidfile_close();
+
+ if (error != 0) {
+ errno = error;
+ return -1;
+ }
+ return 0;
+}
+
+/* atexit shim for pidfile_clean */
+static void
+pidfile_cleanup(void)
+{
+
+ pidfile_clean();
+}
+
+/* Constructs a name for a pidfile in the default location (/var/run).
+ * If 'bname' is NULL, uses the name of the current program for the name of
+ * the pidfile.
+ *
+ * Returns 0 on success, otherwise -1. */
+static int
+pidfile_varrun_path(char *path, size_t len, const char *bname)
+{
+
+ if (bname == NULL)
+ bname = PACKAGE;
+
+ /* _PATH_VARRUN includes trailing / */
+ if ((size_t)snprintf(path, len, "%s%s.pid", _PATH_VARRUN, bname) >= len)
+ {
+ errno = ENAMETOOLONG;
+ return -1;
+ }
+ return 0;
+}
+
+/* Returns the process ID inside path on success, otherwise -1.
+ * If no path is given, use the last pidfile path, othewise the default one. */
+pid_t
+pidfile_read(const char *path)
+{
+ char dpath[PATH_MAX], buf[16], *eptr;
+ int fd, error;
+ ssize_t n;
+ pid_t pid;
+
+ if (path == NULL && pidfile_path[0] != '\0')
+ path = pidfile_path;
+ if (path == NULL || strchr(path, '/') == NULL) {
+ if (pidfile_varrun_path(dpath, sizeof(dpath), path) == -1)
+ return -1;
+ path = dpath;
+ }
+
+ if ((fd = open(path, O_RDONLY | O_NONBLOCK)) == -1)
+ return -1;
+ n = read(fd, buf, sizeof(buf) - 1);
+ error = errno;
+ (void) close(fd);
+ if (n == -1) {
+ errno = error;
+ return -1;
+ }
+ buf[n] = '\0';
+ pid = (pid_t)strtoi(buf, &eptr, 10, 1, INT_MAX, &error);
+ if (error && !(error == ENOTSUP && *eptr == '\n')) {
+ errno = error;
+ return -1;
+ }
+ return pid;
+}
+
+/* Locks the pidfile specified by path and writes the process pid to it.
+ * The new pidfile is "registered" in the global variables pidfile_fd,
+ * pidfile_path and pidfile_pid so that any further call to pidfile_lock(3)
+ * can check if we are recreating the same file or a new one.
+ *
+ * Returns 0 on success, otherwise the pid of the process who owns the
+ * lock if it can be read, otherwise -1. */
+pid_t
+pidfile_lock(const char *path)
+{
+ char dpath[PATH_MAX];
+ static bool registered_atexit = false;
+
+ /* Register for cleanup with atexit. */
+ if (!registered_atexit) {
+ if (atexit(pidfile_cleanup) == -1)
+ return -1;
+ registered_atexit = true;
+ }
+
+ if (path == NULL || strchr(path, '/') == NULL) {
+ if (pidfile_varrun_path(dpath, sizeof(dpath), path) == -1)
+ return -1;
+ path = dpath;
+ }
+
+ /* If path has changed (no good reason), clean up the old pidfile. */
+ if (pidfile_fd != -1 && strcmp(pidfile_path, path) != 0)
+ pidfile_clean();
+
+ if (pidfile_fd == -1) {
+ int fd, opts;
+
+ opts = O_WRONLY | O_CREAT | O_NONBLOCK;
+#ifdef O_CLOEXEC
+ opts |= O_CLOEXEC;
+#endif
+#ifdef O_EXLOCK
+ opts |= O_EXLOCK;
+#endif
+ if ((fd = open(path, opts, 0644)) == -1)
+ goto return_pid;
+#ifndef O_CLOEXEC
+ if ((opts = fcntl(fd, F_GETFD)) == -1 ||
+ fcntl(fd, F_SETFL, opts | FD_CLOEXEC) == -1)
+ {
+ int error = errno;
+
+ (void) close(fd);
+ errno = error;
+ return -1;
+ }
+#endif
+#ifndef O_EXLOCK
+ if (flock(fd, LOCK_EX | LOCK_NB) == -1) {
+ int error = errno;
+
+ (void) close(fd);
+ if (error != EAGAIN) {
+ errno = error;
+ return -1;
+ }
+ fd = -1;
+ }
+#endif
+
+return_pid:
+ if (fd == -1) {
+ pid_t pid;
+
+ if (errno == EAGAIN) {
+ /* The pidfile is locked, return the process ID
+ * it contains.
+ * If sucessful, set errno to EEXIST. */
+ if ((pid = pidfile_read(path)) != -1)
+ errno = EEXIST;
+ } else
+ pid = -1;
+
+ return pid;
+ }
+ pidfile_fd = fd;
+ strlcpy(pidfile_path, path, sizeof(pidfile_path));
+ }
+
+ pidfile_pid = getpid();
+
+ /* Truncate the file, as we could be re-writing it.
+ * Then write the process ID. */
+ if (ftruncate(pidfile_fd, 0) == -1 ||
+ lseek(pidfile_fd, 0, SEEK_SET) == -1 ||
+ dprintf(pidfile_fd, "%d\n", pidfile_pid) == -1)
+ {
+ int error = errno;
+
+ pidfile_cleanup();
+ errno = error;
+ return -1;
+ }
+
+ /* Hold the fd open to persist the lock. */
+ return 0;
+}
diff --git a/compat/pidfile.h b/compat/pidfile.h
new file mode 100644
index 000000000000..ed833e15232c
--- /dev/null
+++ b/compat/pidfile.h
@@ -0,0 +1,39 @@
+/*-
+ * Copyright (c) 1999, 2016 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to The NetBSD Foundation
+ * by Jason R. Thorpe, Matthias Scheler, Julio Merino and Roy Marples.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef PIDFILE_H
+#define PIDFILE_H
+
+#include <unistd.h>
+
+int pidfile_clean(void);
+pid_t pidfile_lock(const char *);
+pid_t pidfile_read(const char *);
+
+#endif
diff --git a/compat/queue.h b/compat/queue.h
new file mode 100644
index 000000000000..99ac6b9460ea
--- /dev/null
+++ b/compat/queue.h
@@ -0,0 +1,175 @@
+/* $NetBSD: queue.h,v 1.65 2013/12/25 17:19:34 christos Exp $ */
+
+/*
+ * Copyright (c) 1991, 1993
+ * The Regents of the University of California. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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.
+ *
+ * @(#)queue.h 8.5 (Berkeley) 8/20/94
+ */
+
+#ifndef COMPAT_QUEUE_H
+#define COMPAT_QUEUE_H
+
+/*
+ * Tail queue definitions.
+ */
+#ifndef TAILQ_END
+#define TAILQ_END(head) (NULL)
+#endif
+
+#ifndef TAILQ_HEAD
+#define _TAILQ_HEAD(name, type, qual) \
+struct name { \
+ qual type *tqh_first; /* first element */ \
+ qual type *qual *tqh_last; /* addr of last next element */ \
+}
+#define TAILQ_HEAD(name, type) _TAILQ_HEAD(name, struct type,)
+
+#define TAILQ_HEAD_INITIALIZER(head) \
+ { TAILQ_END(head), &(head).tqh_first }
+
+#define _TAILQ_ENTRY(type, qual) \
+struct { \
+ qual type *tqe_next; /* next element */ \
+ qual type *qual *tqe_prev; /* address of previous next element */\
+}
+#define TAILQ_ENTRY(type) _TAILQ_ENTRY(struct type,)
+#endif /* !TAILQ_HEAD */
+
+/*
+ * Tail queue access methods.
+ */
+#ifndef TAILQ_FIRST
+#define TAILQ_FIRST(head) ((head)->tqh_first)
+#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
+#define TAILQ_LAST(head, headname) \
+ (*(((struct headname *)((head)->tqh_last))->tqh_last))
+#define TAILQ_PREV(elm, headname, field) \
+ (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
+#define TAILQ_EMPTY(head) (TAILQ_FIRST(head) == TAILQ_END(head))
+#endif /* !TAILQ_FIRST */
+
+#ifndef TAILQ_FOREACH
+#define TAILQ_FOREACH(var, head, field) \
+ for ((var) = ((head)->tqh_first); \
+ (var) != TAILQ_END(head); \
+ (var) = ((var)->field.tqe_next))
+
+#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
+ for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));\
+ (var) != TAILQ_END(head); \
+ (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
+#endif /* !TAILQ_FOREACH */
+
+#ifndef TAILQ_INIT
+#define TAILQ_INIT(head) do { \
+ (head)->tqh_first = TAILQ_END(head); \
+ (head)->tqh_last = &(head)->tqh_first; \
+} while (/*CONSTCOND*/0)
+
+#define TAILQ_INSERT_HEAD(head, elm, field) do { \
+ if (((elm)->field.tqe_next = (head)->tqh_first) != TAILQ_END(head))\
+ (head)->tqh_first->field.tqe_prev = \
+ &(elm)->field.tqe_next; \
+ else \
+ (head)->tqh_last = &(elm)->field.tqe_next; \
+ (head)->tqh_first = (elm); \
+ (elm)->field.tqe_prev = &(head)->tqh_first; \
+} while (/*CONSTCOND*/0)
+
+#define TAILQ_INSERT_TAIL(head, elm, field) do { \
+ (elm)->field.tqe_next = TAILQ_END(head); \
+ (elm)->field.tqe_prev = (head)->tqh_last; \
+ *(head)->tqh_last = (elm); \
+ (head)->tqh_last = &(elm)->field.tqe_next; \
+} while (/*CONSTCOND*/0)
+
+#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
+ if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != \
+ TAILQ_END(head)) \
+ (elm)->field.tqe_next->field.tqe_prev = \
+ &(elm)->field.tqe_next; \
+ else \
+ (head)->tqh_last = &(elm)->field.tqe_next; \
+ (listelm)->field.tqe_next = (elm); \
+ (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
+} while (/*CONSTCOND*/0)
+
+#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
+ (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
+ (elm)->field.tqe_next = (listelm); \
+ *(listelm)->field.tqe_prev = (elm); \
+ (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
+} while (/*CONSTCOND*/0)
+
+#define TAILQ_REMOVE(head, elm, field) do { \
+ if (((elm)->field.tqe_next) != TAILQ_END(head)) \
+ (elm)->field.tqe_next->field.tqe_prev = \
+ (elm)->field.tqe_prev; \
+ else \
+ (head)->tqh_last = (elm)->field.tqe_prev; \
+ *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
+} while (/*CONSTCOND*/0)
+#endif /* !TAILQ_INIT */
+
+#ifndef TAILQ_REPLACE
+#define TAILQ_REPLACE(head, elm, elm2, field) do { \
+ if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != \
+ TAILQ_END(head)) \
+ (elm2)->field.tqe_next->field.tqe_prev = \
+ &(elm2)->field.tqe_next; \
+ else \
+ (head)->tqh_last = &(elm2)->field.tqe_next; \
+ (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \
+ *(elm2)->field.tqe_prev = (elm2); \
+} while (/*CONSTCOND*/0)
+#endif /* !TAILQ_REPLACE */
+
+#ifndef TAILQ_FOREACH_SAFE
+#define TAILQ_FOREACH_SAFE(var, head, field, next) \
+ for ((var) = TAILQ_FIRST(head); \
+ (var) != TAILQ_END(head) && \
+ ((next) = TAILQ_NEXT(var, field), 1); (var) = (next))
+
+#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, prev) \
+ for ((var) = TAILQ_LAST((head), headname); \
+ (var) != TAILQ_END(head) && \
+ ((prev) = TAILQ_PREV((var), headname, field), 1); (var) = (prev))
+#endif /* !TAILQ_FOREACH_SAFE */
+
+#ifndef TAILQ_CONCAT
+#define TAILQ_CONCAT(head1, head2, field) do { \
+ if (!TAILQ_EMPTY(head2)) { \
+ *(head1)->tqh_last = (head2)->tqh_first; \
+ (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
+ (head1)->tqh_last = (head2)->tqh_last; \
+ TAILQ_INIT((head2)); \
+ } \
+} while (/*CONSTCOND*/0)
+#endif /* !TAILQ_CONCAT */
+
+#endif /* !COMAPT_QUEUE_H */
diff --git a/compat/rb.c b/compat/rb.c
new file mode 100644
index 000000000000..3c0bed5f70d5
--- /dev/null
+++ b/compat/rb.c
@@ -0,0 +1,1346 @@
+/* $NetBSD: rb.c,v 1.14 2019/03/08 09:14:54 roy Exp $ */
+
+/*-
+ * Copyright (c) 2001 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to The NetBSD Foundation
+ * by Matt Thomas <matt@3am-software.com>.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include "common.h"
+
+#if !defined(_KERNEL) && !defined(_STANDALONE)
+#include <sys/types.h>
+#include <stddef.h>
+#include <assert.h>
+#include <stdbool.h>
+#ifdef RBDEBUG
+#define KASSERT(s) assert(s)
+#define __rbt_unused
+#else
+#define KASSERT(s) do { } while (/*CONSTCOND*/ 0)
+#define __rbt_unused __unused
+#endif
+__RCSID("$NetBSD: rb.c,v 1.14 2019/03/08 09:14:54 roy Exp $");
+#else
+#include <lib/libkern/libkern.h>
+__KERNEL_RCSID(0, "$NetBSD: rb.c,v 1.14 2019/03/08 09:14:54 roy Exp $");
+#ifndef DIAGNOSTIC
+#define __rbt_unused __unused
+#else
+#define __rbt_unused
+#endif
+#endif
+
+#ifdef _LIBC
+__weak_alias(rb_tree_init, _rb_tree_init)
+__weak_alias(rb_tree_find_node, _rb_tree_find_node)
+__weak_alias(rb_tree_find_node_geq, _rb_tree_find_node_geq)
+__weak_alias(rb_tree_find_node_leq, _rb_tree_find_node_leq)
+__weak_alias(rb_tree_insert_node, _rb_tree_insert_node)
+__weak_alias(rb_tree_remove_node, _rb_tree_remove_node)
+__weak_alias(rb_tree_iterate, _rb_tree_iterate)
+#ifdef RBDEBUG
+__weak_alias(rb_tree_check, _rb_tree_check)
+__weak_alias(rb_tree_depths, _rb_tree_depths)
+#endif
+
+#include "namespace.h"
+#endif
+
+#ifdef RBTEST
+#include "rbtree.h"
+#else
+#include <sys/rbtree.h>
+#endif
+
+static void rb_tree_insert_rebalance(struct rb_tree *, struct rb_node *);
+static void rb_tree_removal_rebalance(struct rb_tree *, struct rb_node *,
+ unsigned int);
+#ifdef RBDEBUG
+static const struct rb_node *rb_tree_iterate_const(const struct rb_tree *,
+ const struct rb_node *, const unsigned int);
+static bool rb_tree_check_node(const struct rb_tree *, const struct rb_node *,
+ const struct rb_node *, bool);
+#else
+#define rb_tree_check_node(a, b, c, d) true
+#endif
+
+#define RB_NODETOITEM(rbto, rbn) \
+ ((void *)((uintptr_t)(rbn) - (rbto)->rbto_node_offset))
+#define RB_ITEMTONODE(rbto, rbn) \
+ ((rb_node_t *)((uintptr_t)(rbn) + (rbto)->rbto_node_offset))
+
+#define RB_SENTINEL_NODE NULL
+
+void
+rb_tree_init(struct rb_tree *rbt, const rb_tree_ops_t *ops)
+{
+
+ rbt->rbt_ops = ops;
+ rbt->rbt_root = RB_SENTINEL_NODE;
+ RB_TAILQ_INIT(&rbt->rbt_nodes);
+#ifndef RBSMALL
+ rbt->rbt_minmax[RB_DIR_LEFT] = rbt->rbt_root; /* minimum node */
+ rbt->rbt_minmax[RB_DIR_RIGHT] = rbt->rbt_root; /* maximum node */
+#endif
+#ifdef RBSTATS
+ rbt->rbt_count = 0;
+ rbt->rbt_insertions = 0;
+ rbt->rbt_removals = 0;
+ rbt->rbt_insertion_rebalance_calls = 0;
+ rbt->rbt_insertion_rebalance_passes = 0;
+ rbt->rbt_removal_rebalance_calls = 0;
+ rbt->rbt_removal_rebalance_passes = 0;
+#endif
+}
+
+void *
+rb_tree_find_node(struct rb_tree *rbt, const void *key)
+{
+ const rb_tree_ops_t *rbto = rbt->rbt_ops;
+ rbto_compare_key_fn compare_key = rbto->rbto_compare_key;
+ struct rb_node *parent = rbt->rbt_root;
+
+ while (!RB_SENTINEL_P(parent)) {
+ void *pobj = RB_NODETOITEM(rbto, parent);
+ const signed int diff = (*compare_key)(rbto->rbto_context,
+ pobj, key);
+ if (diff == 0)
+ return pobj;
+ parent = parent->rb_nodes[diff < 0];
+ }
+
+ return NULL;
+}
+
+void *
+rb_tree_find_node_geq(struct rb_tree *rbt, const void *key)
+{
+ const rb_tree_ops_t *rbto = rbt->rbt_ops;
+ rbto_compare_key_fn compare_key = rbto->rbto_compare_key;
+ struct rb_node *parent = rbt->rbt_root, *last = NULL;
+
+ while (!RB_SENTINEL_P(parent)) {
+ void *pobj = RB_NODETOITEM(rbto, parent);
+ const signed int diff = (*compare_key)(rbto->rbto_context,
+ pobj, key);
+ if (diff == 0)
+ return pobj;
+ if (diff > 0)
+ last = parent;
+ parent = parent->rb_nodes[diff < 0];
+ }
+
+ return last == NULL ? NULL : RB_NODETOITEM(rbto, last);
+}
+
+void *
+rb_tree_find_node_leq(struct rb_tree *rbt, const void *key)
+{
+ const rb_tree_ops_t *rbto = rbt->rbt_ops;
+ rbto_compare_key_fn compare_key = rbto->rbto_compare_key;
+ struct rb_node *parent = rbt->rbt_root, *last = NULL;
+
+ while (!RB_SENTINEL_P(parent)) {
+ void *pobj = RB_NODETOITEM(rbto, parent);
+ const signed int diff = (*compare_key)(rbto->rbto_context,
+ pobj, key);
+ if (diff == 0)
+ return pobj;
+ if (diff < 0)
+ last = parent;
+ parent = parent->rb_nodes[diff < 0];
+ }
+
+ return last == NULL ? NULL : RB_NODETOITEM(rbto, last);
+}
+
+void *
+rb_tree_insert_node(struct rb_tree *rbt, void *object)
+{
+ const rb_tree_ops_t *rbto = rbt->rbt_ops;
+ rbto_compare_nodes_fn compare_nodes = rbto->rbto_compare_nodes;
+ struct rb_node *parent, *tmp, *self = RB_ITEMTONODE(rbto, object);
+ unsigned int position;
+ bool rebalance;
+
+ RBSTAT_INC(rbt->rbt_insertions);
+
+ tmp = rbt->rbt_root;
+ /*
+ * This is a hack. Because rbt->rbt_root is just a struct rb_node *,
+ * just like rb_node->rb_nodes[RB_DIR_LEFT], we can use this fact to
+ * avoid a lot of tests for root and know that even at root,
+ * updating RB_FATHER(rb_node)->rb_nodes[RB_POSITION(rb_node)] will
+ * update rbt->rbt_root.
+ */
+ parent = (struct rb_node *)(void *)&rbt->rbt_root;
+ position = RB_DIR_LEFT;
+
+ /*
+ * Find out where to place this new leaf.
+ */
+ while (!RB_SENTINEL_P(tmp)) {
+ void *tobj = RB_NODETOITEM(rbto, tmp);
+ const signed int diff = (*compare_nodes)(rbto->rbto_context,
+ tobj, object);
+ if (__predict_false(diff == 0)) {
+ /*
+ * Node already exists; return it.
+ */
+ return tobj;
+ }
+ parent = tmp;
+ position = (diff < 0);
+ tmp = parent->rb_nodes[position];
+ }
+
+#ifdef RBDEBUG
+ {
+ struct rb_node *prev = NULL, *next = NULL;
+
+ if (position == RB_DIR_RIGHT)
+ prev = parent;
+ else if (tmp != rbt->rbt_root)
+ next = parent;
+
+ /*
+ * Verify our sequential position
+ */
+ KASSERT(prev == NULL || !RB_SENTINEL_P(prev));
+ KASSERT(next == NULL || !RB_SENTINEL_P(next));
+ if (prev != NULL && next == NULL)
+ next = TAILQ_NEXT(prev, rb_link);
+ if (prev == NULL && next != NULL)
+ prev = TAILQ_PREV(next, rb_node_qh, rb_link);
+ KASSERT(prev == NULL || !RB_SENTINEL_P(prev));
+ KASSERT(next == NULL || !RB_SENTINEL_P(next));
+ KASSERT(prev == NULL || (*compare_nodes)(rbto->rbto_context,
+ RB_NODETOITEM(rbto, prev), RB_NODETOITEM(rbto, self)) < 0);
+ KASSERT(next == NULL || (*compare_nodes)(rbto->rbto_context,
+ RB_NODETOITEM(rbto, self), RB_NODETOITEM(rbto, next)) < 0);
+ }
+#endif
+
+ /*
+ * Initialize the node and insert as a leaf into the tree.
+ */
+ RB_SET_FATHER(self, parent);
+ RB_SET_POSITION(self, position);
+ if (__predict_false(parent == (struct rb_node *)(void *)&rbt->rbt_root)) {
+ RB_MARK_BLACK(self); /* root is always black */
+#ifndef RBSMALL
+ rbt->rbt_minmax[RB_DIR_LEFT] = self;
+ rbt->rbt_minmax[RB_DIR_RIGHT] = self;
+#endif
+ rebalance = false;
+ } else {
+ KASSERT(position == RB_DIR_LEFT || position == RB_DIR_RIGHT);
+#ifndef RBSMALL
+ /*
+ * Keep track of the minimum and maximum nodes. If our
+ * parent is a minmax node and we on their min/max side,
+ * we must be the new min/max node.
+ */
+ if (parent == rbt->rbt_minmax[position])
+ rbt->rbt_minmax[position] = self;
+#endif /* !RBSMALL */
+ /*
+ * All new nodes are colored red. We only need to rebalance
+ * if our parent is also red.
+ */
+ RB_MARK_RED(self);
+ rebalance = RB_RED_P(parent);
+ }
+ KASSERT(RB_SENTINEL_P(parent->rb_nodes[position]));
+ self->rb_left = parent->rb_nodes[position];
+ self->rb_right = parent->rb_nodes[position];
+ parent->rb_nodes[position] = self;
+ KASSERT(RB_CHILDLESS_P(self));
+
+ /*
+ * Insert the new node into a sorted list for easy sequential access
+ */
+ RBSTAT_INC(rbt->rbt_count);
+#ifdef RBDEBUG
+ if (RB_ROOT_P(rbt, self)) {
+ RB_TAILQ_INSERT_HEAD(&rbt->rbt_nodes, self, rb_link);
+ } else if (position == RB_DIR_LEFT) {
+ KASSERT((*compare_nodes)(rbto->rbto_context,
+ RB_NODETOITEM(rbto, self),
+ RB_NODETOITEM(rbto, RB_FATHER(self))) < 0);
+ RB_TAILQ_INSERT_BEFORE(RB_FATHER(self), self, rb_link);
+ } else {
+ KASSERT((*compare_nodes)(rbto->rbto_context,
+ RB_NODETOITEM(rbto, RB_FATHER(self)),
+ RB_NODETOITEM(rbto, self)) < 0);
+ RB_TAILQ_INSERT_AFTER(&rbt->rbt_nodes, RB_FATHER(self),
+ self, rb_link);
+ }
+#endif
+ KASSERT(rb_tree_check_node(rbt, self, NULL, !rebalance));
+
+ /*
+ * Rebalance tree after insertion
+ */
+ if (rebalance) {
+ rb_tree_insert_rebalance(rbt, self);
+ KASSERT(rb_tree_check_node(rbt, self, NULL, true));
+ }
+
+ /* Succesfully inserted, return our node pointer. */
+ return object;
+}
+
+/*
+ * Swap the location and colors of 'self' and its child @ which. The child
+ * can not be a sentinel node. This is our rotation function. However,
+ * since it preserves coloring, it great simplifies both insertion and
+ * removal since rotation almost always involves the exchanging of colors
+ * as a separate step.
+ */
+static void
+rb_tree_reparent_nodes(__rbt_unused struct rb_tree *rbt,
+ struct rb_node *old_father, const unsigned int which)
+{
+ const unsigned int other = which ^ RB_DIR_OTHER;
+ struct rb_node * const grandpa = RB_FATHER(old_father);
+ struct rb_node * const old_child = old_father->rb_nodes[which];
+ struct rb_node * const new_father = old_child;
+ struct rb_node * const new_child = old_father;
+
+ KASSERT(which == RB_DIR_LEFT || which == RB_DIR_RIGHT);
+
+ KASSERT(!RB_SENTINEL_P(old_child));
+ KASSERT(RB_FATHER(old_child) == old_father);
+
+ KASSERT(rb_tree_check_node(rbt, old_father, NULL, false));
+ KASSERT(rb_tree_check_node(rbt, old_child, NULL, false));
+ KASSERT(RB_ROOT_P(rbt, old_father) ||
+ rb_tree_check_node(rbt, grandpa, NULL, false));
+
+ /*
+ * Exchange descendant linkages.
+ */
+ grandpa->rb_nodes[RB_POSITION(old_father)] = new_father;
+ new_child->rb_nodes[which] = old_child->rb_nodes[other];
+ new_father->rb_nodes[other] = new_child;
+
+ /*
+ * Update ancestor linkages
+ */
+ RB_SET_FATHER(new_father, grandpa);
+ RB_SET_FATHER(new_child, new_father);
+
+ /*
+ * Exchange properties between new_father and new_child. The only
+ * change is that new_child's position is now on the other side.
+ */
+#if 0
+ {
+ struct rb_node tmp;
+ tmp.rb_info = 0;
+ RB_COPY_PROPERTIES(&tmp, old_child);
+ RB_COPY_PROPERTIES(new_father, old_father);
+ RB_COPY_PROPERTIES(new_child, &tmp);
+ }
+#else
+ RB_SWAP_PROPERTIES(new_father, new_child);
+#endif
+ RB_SET_POSITION(new_child, other);
+
+ /*
+ * Make sure to reparent the new child to ourself.
+ */
+ if (!RB_SENTINEL_P(new_child->rb_nodes[which])) {
+ RB_SET_FATHER(new_child->rb_nodes[which], new_child);
+ RB_SET_POSITION(new_child->rb_nodes[which], which);
+ }
+
+ KASSERT(rb_tree_check_node(rbt, new_father, NULL, false));
+ KASSERT(rb_tree_check_node(rbt, new_child, NULL, false));
+ KASSERT(RB_ROOT_P(rbt, new_father) ||
+ rb_tree_check_node(rbt, grandpa, NULL, false));
+}
+
+static void
+rb_tree_insert_rebalance(struct rb_tree *rbt, struct rb_node *self)
+{
+ struct rb_node * father = RB_FATHER(self);
+ struct rb_node * grandpa = RB_FATHER(father);
+ struct rb_node * uncle;
+ unsigned int which;
+ unsigned int other;
+
+ KASSERT(!RB_ROOT_P(rbt, self));
+ KASSERT(RB_RED_P(self));
+ KASSERT(RB_RED_P(father));
+ RBSTAT_INC(rbt->rbt_insertion_rebalance_calls);
+
+ for (;;) {
+ KASSERT(!RB_SENTINEL_P(self));
+
+ KASSERT(RB_RED_P(self));
+ KASSERT(RB_RED_P(father));
+ /*
+ * We are red and our parent is red, therefore we must have a
+ * grandfather and he must be black.
+ */
+ grandpa = RB_FATHER(father);
+ KASSERT(RB_BLACK_P(grandpa));
+ KASSERT(RB_DIR_RIGHT == 1 && RB_DIR_LEFT == 0);
+ which = (father == grandpa->rb_right);
+ other = which ^ RB_DIR_OTHER;
+ uncle = grandpa->rb_nodes[other];
+
+ if (RB_BLACK_P(uncle))
+ break;
+
+ RBSTAT_INC(rbt->rbt_insertion_rebalance_passes);
+ /*
+ * Case 1: our uncle is red
+ * Simply invert the colors of our parent and
+ * uncle and make our grandparent red. And
+ * then solve the problem up at his level.
+ */
+ RB_MARK_BLACK(uncle);
+ RB_MARK_BLACK(father);
+ if (__predict_false(RB_ROOT_P(rbt, grandpa))) {
+ /*
+ * If our grandpa is root, don't bother
+ * setting him to red, just return.
+ */
+ KASSERT(RB_BLACK_P(grandpa));
+ return;
+ }
+ RB_MARK_RED(grandpa);
+ self = grandpa;
+ father = RB_FATHER(self);
+ KASSERT(RB_RED_P(self));
+ if (RB_BLACK_P(father)) {
+ /*
+ * If our greatgrandpa is black, we're done.
+ */
+ KASSERT(RB_BLACK_P(rbt->rbt_root));
+ return;
+ }
+ }
+
+ KASSERT(!RB_ROOT_P(rbt, self));
+ KASSERT(RB_RED_P(self));
+ KASSERT(RB_RED_P(father));
+ KASSERT(RB_BLACK_P(uncle));
+ KASSERT(RB_BLACK_P(grandpa));
+ /*
+ * Case 2&3: our uncle is black.
+ */
+ if (self == father->rb_nodes[other]) {
+ /*
+ * Case 2: we are on the same side as our uncle
+ * Swap ourselves with our parent so this case
+ * becomes case 3. Basically our parent becomes our
+ * child.
+ */
+ rb_tree_reparent_nodes(rbt, father, other);
+ KASSERT(RB_FATHER(father) == self);
+ KASSERT(self->rb_nodes[which] == father);
+ KASSERT(RB_FATHER(self) == grandpa);
+ self = father;
+ father = RB_FATHER(self);
+ }
+ KASSERT(RB_RED_P(self) && RB_RED_P(father));
+ KASSERT(grandpa->rb_nodes[which] == father);
+ /*
+ * Case 3: we are opposite a child of a black uncle.
+ * Swap our parent and grandparent. Since our grandfather
+ * is black, our father will become black and our new sibling
+ * (former grandparent) will become red.
+ */
+ rb_tree_reparent_nodes(rbt, grandpa, which);
+ KASSERT(RB_FATHER(self) == father);
+ KASSERT(RB_FATHER(self)->rb_nodes[RB_POSITION(self) ^ RB_DIR_OTHER] == grandpa);
+ KASSERT(RB_RED_P(self));
+ KASSERT(RB_BLACK_P(father));
+ KASSERT(RB_RED_P(grandpa));
+
+ /*
+ * Final step: Set the root to black.
+ */
+ RB_MARK_BLACK(rbt->rbt_root);
+}
+
+static void
+rb_tree_prune_node(struct rb_tree *rbt, struct rb_node *self, bool rebalance)
+{
+ const unsigned int which = RB_POSITION(self);
+ struct rb_node *father = RB_FATHER(self);
+#ifndef RBSMALL
+ const bool was_root = RB_ROOT_P(rbt, self);
+#endif
+
+ KASSERT(rebalance || (RB_ROOT_P(rbt, self) || RB_RED_P(self)));
+ KASSERT(!rebalance || RB_BLACK_P(self));
+ KASSERT(RB_CHILDLESS_P(self));
+ KASSERT(rb_tree_check_node(rbt, self, NULL, false));
+
+ /*
+ * Since we are childless, we know that self->rb_left is pointing
+ * to the sentinel node.
+ */
+ father->rb_nodes[which] = self->rb_left;
+
+ /*
+ * Remove ourselves from the node list, decrement the count,
+ * and update min/max.
+ */
+ RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
+ RBSTAT_DEC(rbt->rbt_count);
+#ifndef RBSMALL
+ if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self)) {
+ rbt->rbt_minmax[RB_POSITION(self)] = father;
+ /*
+ * When removing the root, rbt->rbt_minmax[RB_DIR_LEFT] is
+ * updated automatically, but we also need to update
+ * rbt->rbt_minmax[RB_DIR_RIGHT];
+ */
+ if (__predict_false(was_root)) {
+ rbt->rbt_minmax[RB_DIR_RIGHT] = father;
+ }
+ }
+ RB_SET_FATHER(self, NULL);
+#endif
+
+ /*
+ * Rebalance if requested.
+ */
+ if (rebalance)
+ rb_tree_removal_rebalance(rbt, father, which);
+ KASSERT(was_root || rb_tree_check_node(rbt, father, NULL, true));
+}
+
+/*
+ * When deleting an interior node
+ */
+static void
+rb_tree_swap_prune_and_rebalance(struct rb_tree *rbt, struct rb_node *self,
+ struct rb_node *standin)
+{
+ const unsigned int standin_which = RB_POSITION(standin);
+ unsigned int standin_other = standin_which ^ RB_DIR_OTHER;
+ struct rb_node *standin_son;
+ struct rb_node *standin_father = RB_FATHER(standin);
+ bool rebalance = RB_BLACK_P(standin);
+
+ if (standin_father == self) {
+ /*
+ * As a child of self, any childen would be opposite of
+ * our parent.
+ */
+ KASSERT(RB_SENTINEL_P(standin->rb_nodes[standin_other]));
+ standin_son = standin->rb_nodes[standin_which];
+ } else {
+ /*
+ * Since we aren't a child of self, any childen would be
+ * on the same side as our parent.
+ */
+ KASSERT(RB_SENTINEL_P(standin->rb_nodes[standin_which]));
+ standin_son = standin->rb_nodes[standin_other];
+ }
+
+ /*
+ * the node we are removing must have two children.
+ */
+ KASSERT(RB_TWOCHILDREN_P(self));
+ /*
+ * If standin has a child, it must be red.
+ */
+ KASSERT(RB_SENTINEL_P(standin_son) || RB_RED_P(standin_son));
+
+ /*
+ * Verify things are sane.
+ */
+ KASSERT(rb_tree_check_node(rbt, self, NULL, false));
+ KASSERT(rb_tree_check_node(rbt, standin, NULL, false));
+
+ if (__predict_false(RB_RED_P(standin_son))) {
+ /*
+ * We know we have a red child so if we flip it to black
+ * we don't have to rebalance.
+ */
+ KASSERT(rb_tree_check_node(rbt, standin_son, NULL, true));
+ RB_MARK_BLACK(standin_son);
+ rebalance = false;
+
+ if (standin_father == self) {
+ KASSERT(RB_POSITION(standin_son) == standin_which);
+ } else {
+ KASSERT(RB_POSITION(standin_son) == standin_other);
+ /*
+ * Change the son's parentage to point to his grandpa.
+ */
+ RB_SET_FATHER(standin_son, standin_father);
+ RB_SET_POSITION(standin_son, standin_which);
+ }
+ }
+
+ if (standin_father == self) {
+ /*
+ * If we are about to delete the standin's father, then when
+ * we call rebalance, we need to use ourselves as our father.
+ * Otherwise remember our original father. Also, sincef we are
+ * our standin's father we only need to reparent the standin's
+ * brother.
+ *
+ * | R --> S |
+ * | Q S --> Q T |
+ * | t --> |
+ */
+ KASSERT(RB_SENTINEL_P(standin->rb_nodes[standin_other]));
+ KASSERT(!RB_SENTINEL_P(self->rb_nodes[standin_other]));
+ KASSERT(self->rb_nodes[standin_which] == standin);
+ /*
+ * Have our son/standin adopt his brother as his new son.
+ */
+ standin_father = standin;
+ } else {
+ /*
+ * | R --> S . |
+ * | / \ | T --> / \ | / |
+ * | ..... | S --> ..... | T |
+ *
+ * Sever standin's connection to his father.
+ */
+ standin_father->rb_nodes[standin_which] = standin_son;
+ /*
+ * Adopt the far son.
+ */
+ standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];
+ RB_SET_FATHER(standin->rb_nodes[standin_other], standin);
+ KASSERT(RB_POSITION(self->rb_nodes[standin_other]) == standin_other);
+ /*
+ * Use standin_other because we need to preserve standin_which
+ * for the removal_rebalance.
+ */
+ standin_other = standin_which;
+ }
+
+ /*
+ * Move the only remaining son to our standin. If our standin is our
+ * son, this will be the only son needed to be moved.
+ */
+ KASSERT(standin->rb_nodes[standin_other] != self->rb_nodes[standin_other]);
+ standin->rb_nodes[standin_other] = self->rb_nodes[standin_other];
+ RB_SET_FATHER(standin->rb_nodes[standin_other], standin);
+
+ /*
+ * Now copy the result of self to standin and then replace
+ * self with standin in the tree.
+ */
+ RB_COPY_PROPERTIES(standin, self);
+ RB_SET_FATHER(standin, RB_FATHER(self));
+ RB_FATHER(standin)->rb_nodes[RB_POSITION(standin)] = standin;
+
+ /*
+ * Remove ourselves from the node list, decrement the count,
+ * and update min/max.
+ */
+ RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
+ RBSTAT_DEC(rbt->rbt_count);
+#ifndef RBSMALL
+ if (__predict_false(rbt->rbt_minmax[RB_POSITION(self)] == self))
+ rbt->rbt_minmax[RB_POSITION(self)] = RB_FATHER(self);
+ RB_SET_FATHER(self, NULL);
+#endif
+
+ KASSERT(rb_tree_check_node(rbt, standin, NULL, false));
+ KASSERT(RB_FATHER_SENTINEL_P(standin)
+ || rb_tree_check_node(rbt, standin_father, NULL, false));
+ KASSERT(RB_LEFT_SENTINEL_P(standin)
+ || rb_tree_check_node(rbt, standin->rb_left, NULL, false));
+ KASSERT(RB_RIGHT_SENTINEL_P(standin)
+ || rb_tree_check_node(rbt, standin->rb_right, NULL, false));
+
+ if (!rebalance)
+ return;
+
+ rb_tree_removal_rebalance(rbt, standin_father, standin_which);
+ KASSERT(rb_tree_check_node(rbt, standin, NULL, true));
+}
+
+/*
+ * We could do this by doing
+ * rb_tree_node_swap(rbt, self, which);
+ * rb_tree_prune_node(rbt, self, false);
+ *
+ * But it's more efficient to just evalate and recolor the child.
+ */
+static void
+rb_tree_prune_blackred_branch(struct rb_tree *rbt, struct rb_node *self,
+ unsigned int which)
+{
+ struct rb_node *father = RB_FATHER(self);
+ struct rb_node *son = self->rb_nodes[which];
+#ifndef RBSMALL
+ const bool was_root = RB_ROOT_P(rbt, self);
+#endif
+
+ KASSERT(which == RB_DIR_LEFT || which == RB_DIR_RIGHT);
+ KASSERT(RB_BLACK_P(self) && RB_RED_P(son));
+ KASSERT(!RB_TWOCHILDREN_P(son));
+ KASSERT(RB_CHILDLESS_P(son));
+ KASSERT(rb_tree_check_node(rbt, self, NULL, false));
+ KASSERT(rb_tree_check_node(rbt, son, NULL, false));
+
+ /*
+ * Remove ourselves from the tree and give our former child our
+ * properties (position, color, root).
+ */
+ RB_COPY_PROPERTIES(son, self);
+ father->rb_nodes[RB_POSITION(son)] = son;
+ RB_SET_FATHER(son, father);
+
+ /*
+ * Remove ourselves from the node list, decrement the count,
+ * and update minmax.
+ */
+ RB_TAILQ_REMOVE(&rbt->rbt_nodes, self, rb_link);
+ RBSTAT_DEC(rbt->rbt_count);
+#ifndef RBSMALL
+ if (__predict_false(was_root)) {
+ KASSERT(rbt->rbt_minmax[which] == son);
+ rbt->rbt_minmax[which ^ RB_DIR_OTHER] = son;
+ } else if (rbt->rbt_minmax[RB_POSITION(self)] == self) {
+ rbt->rbt_minmax[RB_POSITION(self)] = son;
+ }
+ RB_SET_FATHER(self, NULL);
+#endif
+
+ KASSERT(was_root || rb_tree_check_node(rbt, father, NULL, true));
+ KASSERT(rb_tree_check_node(rbt, son, NULL, true));
+}
+
+void
+rb_tree_remove_node(struct rb_tree *rbt, void *object)
+{
+ const rb_tree_ops_t *rbto = rbt->rbt_ops;
+ struct rb_node *standin, *self = RB_ITEMTONODE(rbto, object);
+ unsigned int which;
+
+ KASSERT(!RB_SENTINEL_P(self));
+ RBSTAT_INC(rbt->rbt_removals);
+
+ /*
+ * In the following diagrams, we (the node to be removed) are S. Red
+ * nodes are lowercase. T could be either red or black.
+ *
+ * Remember the major axiom of the red-black tree: the number of
+ * black nodes from the root to each leaf is constant across all
+ * leaves, only the number of red nodes varies.
+ *
+ * Thus removing a red leaf doesn't require any other changes to a
+ * red-black tree. So if we must remove a node, attempt to rearrange
+ * the tree so we can remove a red node.
+ *
+ * The simpliest case is a childless red node or a childless root node:
+ *
+ * | T --> T | or | R --> * |
+ * | s --> * |
+ */
+ if (RB_CHILDLESS_P(self)) {
+ const bool rebalance = RB_BLACK_P(self) && !RB_ROOT_P(rbt, self);
+ rb_tree_prune_node(rbt, self, rebalance);
+ return;
+ }
+ KASSERT(!RB_CHILDLESS_P(self));
+ if (!RB_TWOCHILDREN_P(self)) {
+ /*
+ * The next simpliest case is the node we are deleting is
+ * black and has one red child.
+ *
+ * | T --> T --> T |
+ * | S --> R --> R |
+ * | r --> s --> * |
+ */
+ which = RB_LEFT_SENTINEL_P(self) ? RB_DIR_RIGHT : RB_DIR_LEFT;
+ KASSERT(RB_BLACK_P(self));
+ KASSERT(RB_RED_P(self->rb_nodes[which]));
+ KASSERT(RB_CHILDLESS_P(self->rb_nodes[which]));
+ rb_tree_prune_blackred_branch(rbt, self, which);
+ return;
+ }
+ KASSERT(RB_TWOCHILDREN_P(self));
+
+ /*
+ * We invert these because we prefer to remove from the inside of
+ * the tree.
+ */
+ which = RB_POSITION(self) ^ RB_DIR_OTHER;
+
+ /*
+ * Let's find the node closes to us opposite of our parent
+ * Now swap it with ourself, "prune" it, and rebalance, if needed.
+ */
+ standin = RB_ITEMTONODE(rbto, rb_tree_iterate(rbt, object, which));
+ rb_tree_swap_prune_and_rebalance(rbt, self, standin);
+}
+
+static void
+rb_tree_removal_rebalance(struct rb_tree *rbt, struct rb_node *parent,
+ unsigned int which)
+{
+ KASSERT(!RB_SENTINEL_P(parent));
+ KASSERT(RB_SENTINEL_P(parent->rb_nodes[which]));
+ KASSERT(which == RB_DIR_LEFT || which == RB_DIR_RIGHT);
+ RBSTAT_INC(rbt->rbt_removal_rebalance_calls);
+
+ while (RB_BLACK_P(parent->rb_nodes[which])) {
+ unsigned int other = which ^ RB_DIR_OTHER;
+ struct rb_node *brother = parent->rb_nodes[other];
+
+ RBSTAT_INC(rbt->rbt_removal_rebalance_passes);
+
+ KASSERT(!RB_SENTINEL_P(brother));
+ /*
+ * For cases 1, 2a, and 2b, our brother's children must
+ * be black and our father must be black
+ */
+ if (RB_BLACK_P(parent)
+ && RB_BLACK_P(brother->rb_left)
+ && RB_BLACK_P(brother->rb_right)) {
+ if (RB_RED_P(brother)) {
+ /*
+ * Case 1: Our brother is red, swap its
+ * position (and colors) with our parent.
+ * This should now be case 2b (unless C or E
+ * has a red child which is case 3; thus no
+ * explicit branch to case 2b).
+ *
+ * B -> D
+ * A d -> b E
+ * C E -> A C
+ */
+ KASSERT(RB_BLACK_P(parent));
+ rb_tree_reparent_nodes(rbt, parent, other);
+ brother = parent->rb_nodes[other];
+ KASSERT(!RB_SENTINEL_P(brother));
+ KASSERT(RB_RED_P(parent));
+ KASSERT(RB_BLACK_P(brother));
+ KASSERT(rb_tree_check_node(rbt, brother, NULL, false));
+ KASSERT(rb_tree_check_node(rbt, parent, NULL, false));
+ } else {
+ /*
+ * Both our parent and brother are black.
+ * Change our brother to red, advance up rank
+ * and go through the loop again.
+ *
+ * B -> *B
+ * *A D -> A d
+ * C E -> C E
+ */
+ RB_MARK_RED(brother);
+ KASSERT(RB_BLACK_P(brother->rb_left));
+ KASSERT(RB_BLACK_P(brother->rb_right));
+ if (RB_ROOT_P(rbt, parent))
+ return; /* root == parent == black */
+ KASSERT(rb_tree_check_node(rbt, brother, NULL, false));
+ KASSERT(rb_tree_check_node(rbt, parent, NULL, false));
+ which = RB_POSITION(parent);
+ parent = RB_FATHER(parent);
+ continue;
+ }
+ }
+ /*
+ * Avoid an else here so that case 2a above can hit either
+ * case 2b, 3, or 4.
+ */
+ if (RB_RED_P(parent)
+ && RB_BLACK_P(brother)
+ && RB_BLACK_P(brother->rb_left)
+ && RB_BLACK_P(brother->rb_right)) {
+ KASSERT(RB_RED_P(parent));
+ KASSERT(RB_BLACK_P(brother));
+ KASSERT(RB_BLACK_P(brother->rb_left));
+ KASSERT(RB_BLACK_P(brother->rb_right));
+ /*
+ * We are black, our father is red, our brother and
+ * both nephews are black. Simply invert/exchange the
+ * colors of our father and brother (to black and red
+ * respectively).
+ *
+ * | f --> F |
+ * | * B --> * b |
+ * | N N --> N N |
+ */
+ RB_MARK_BLACK(parent);
+ RB_MARK_RED(brother);
+ KASSERT(rb_tree_check_node(rbt, brother, NULL, true));
+ break; /* We're done! */
+ } else {
+ /*
+ * Our brother must be black and have at least one
+ * red child (it may have two).
+ */
+ KASSERT(RB_BLACK_P(brother));
+ KASSERT(RB_RED_P(brother->rb_nodes[which]) ||
+ RB_RED_P(brother->rb_nodes[other]));
+ if (RB_BLACK_P(brother->rb_nodes[other])) {
+ /*
+ * Case 3: our brother is black, our near
+ * nephew is red, and our far nephew is black.
+ * Swap our brother with our near nephew.
+ * This result in a tree that matches case 4.
+ * (Our father could be red or black).
+ *
+ * | F --> F |
+ * | x B --> x B |
+ * | n --> n |
+ */
+ KASSERT(RB_RED_P(brother->rb_nodes[which]));
+ rb_tree_reparent_nodes(rbt, brother, which);
+ KASSERT(RB_FATHER(brother) == parent->rb_nodes[other]);
+ brother = parent->rb_nodes[other];
+ KASSERT(RB_RED_P(brother->rb_nodes[other]));
+ }
+ /*
+ * Case 4: our brother is black and our far nephew
+ * is red. Swap our father and brother locations and
+ * change our far nephew to black. (these can be
+ * done in either order so we change the color first).
+ * The result is a valid red-black tree and is a
+ * terminal case. (again we don't care about the
+ * father's color)
+ *
+ * If the father is red, we will get a red-black-black
+ * tree:
+ * | f -> f --> b |
+ * | B -> B --> F N |
+ * | n -> N --> |
+ *
+ * If the father is black, we will get an all black
+ * tree:
+ * | F -> F --> B |
+ * | B -> B --> F N |
+ * | n -> N --> |
+ *
+ * If we had two red nephews, then after the swap,
+ * our former father would have a red grandson.
+ */
+ KASSERT(RB_BLACK_P(brother));
+ KASSERT(RB_RED_P(brother->rb_nodes[other]));
+ RB_MARK_BLACK(brother->rb_nodes[other]);
+ rb_tree_reparent_nodes(rbt, parent, other);
+ break; /* We're done! */
+ }
+ }
+ KASSERT(rb_tree_check_node(rbt, parent, NULL, true));
+}
+
+void *
+rb_tree_iterate(struct rb_tree *rbt, void *object, const unsigned int direction)
+{
+ const rb_tree_ops_t *rbto = rbt->rbt_ops;
+ const unsigned int other = direction ^ RB_DIR_OTHER;
+ struct rb_node *self;
+
+ KASSERT(direction == RB_DIR_LEFT || direction == RB_DIR_RIGHT);
+
+ if (object == NULL) {
+#ifndef RBSMALL
+ if (RB_SENTINEL_P(rbt->rbt_root))
+ return NULL;
+ return RB_NODETOITEM(rbto, rbt->rbt_minmax[direction]);
+#else
+ self = rbt->rbt_root;
+ if (RB_SENTINEL_P(self))
+ return NULL;
+ while (!RB_SENTINEL_P(self->rb_nodes[direction]))
+ self = self->rb_nodes[direction];
+ return RB_NODETOITEM(rbto, self);
+#endif /* !RBSMALL */
+ }
+ self = RB_ITEMTONODE(rbto, object);
+ KASSERT(!RB_SENTINEL_P(self));
+ /*
+ * We can't go any further in this direction. We proceed up in the
+ * opposite direction until our parent is in direction we want to go.
+ */
+ if (RB_SENTINEL_P(self->rb_nodes[direction])) {
+ while (!RB_ROOT_P(rbt, self)) {
+ if (other == RB_POSITION(self))
+ return RB_NODETOITEM(rbto, RB_FATHER(self));
+ self = RB_FATHER(self);
+ }
+ return NULL;
+ }
+
+ /*
+ * Advance down one in current direction and go down as far as possible
+ * in the opposite direction.
+ */
+ self = self->rb_nodes[direction];
+ KASSERT(!RB_SENTINEL_P(self));
+ while (!RB_SENTINEL_P(self->rb_nodes[other]))
+ self = self->rb_nodes[other];
+ return RB_NODETOITEM(rbto, self);
+}
+
+#ifdef RBDEBUG
+static const struct rb_node *
+rb_tree_iterate_const(const struct rb_tree *rbt, const struct rb_node *self,
+ const unsigned int direction)
+{
+ const unsigned int other = direction ^ RB_DIR_OTHER;
+ KASSERT(direction == RB_DIR_LEFT || direction == RB_DIR_RIGHT);
+
+ if (self == NULL) {
+#ifndef RBSMALL
+ if (RB_SENTINEL_P(rbt->rbt_root))
+ return NULL;
+ return rbt->rbt_minmax[direction];
+#else
+ self = rbt->rbt_root;
+ if (RB_SENTINEL_P(self))
+ return NULL;
+ while (!RB_SENTINEL_P(self->rb_nodes[direction]))
+ self = self->rb_nodes[direction];
+ return self;
+#endif /* !RBSMALL */
+ }
+ KASSERT(!RB_SENTINEL_P(self));
+ /*
+ * We can't go any further in this direction. We proceed up in the
+ * opposite direction until our parent is in direction we want to go.
+ */
+ if (RB_SENTINEL_P(self->rb_nodes[direction])) {
+ while (!RB_ROOT_P(rbt, self)) {
+ if (other == RB_POSITION(self))
+ return RB_FATHER(self);
+ self = RB_FATHER(self);
+ }
+ return NULL;
+ }
+
+ /*
+ * Advance down one in current direction and go down as far as possible
+ * in the opposite direction.
+ */
+ self = self->rb_nodes[direction];
+ KASSERT(!RB_SENTINEL_P(self));
+ while (!RB_SENTINEL_P(self->rb_nodes[other]))
+ self = self->rb_nodes[other];
+ return self;
+}
+
+static unsigned int
+rb_tree_count_black(const struct rb_node *self)
+{
+ unsigned int left, right;
+
+ if (RB_SENTINEL_P(self))
+ return 0;
+
+ left = rb_tree_count_black(self->rb_left);
+ right = rb_tree_count_black(self->rb_right);
+
+ KASSERT(left == right);
+
+ return left + RB_BLACK_P(self);
+}
+
+static bool
+rb_tree_check_node(const struct rb_tree *rbt, const struct rb_node *self,
+ const struct rb_node *prev, bool red_check)
+{
+ const rb_tree_ops_t *rbto = rbt->rbt_ops;
+ rbto_compare_nodes_fn compare_nodes = rbto->rbto_compare_nodes;
+
+ KASSERT(!RB_SENTINEL_P(self));
+ KASSERT(prev == NULL || (*compare_nodes)(rbto->rbto_context,
+ RB_NODETOITEM(rbto, prev), RB_NODETOITEM(rbto, self)) < 0);
+
+ /*
+ * Verify our relationship to our parent.
+ */
+ if (RB_ROOT_P(rbt, self)) {
+ KASSERT(self == rbt->rbt_root);
+ KASSERT(RB_POSITION(self) == RB_DIR_LEFT);
+ KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);
+ KASSERT(RB_FATHER(self) == (const struct rb_node *) &rbt->rbt_root);
+ } else {
+ int diff = (*compare_nodes)(rbto->rbto_context,
+ RB_NODETOITEM(rbto, self),
+ RB_NODETOITEM(rbto, RB_FATHER(self)));
+
+ KASSERT(self != rbt->rbt_root);
+ KASSERT(!RB_FATHER_SENTINEL_P(self));
+ if (RB_POSITION(self) == RB_DIR_LEFT) {
+ KASSERT(diff < 0);
+ KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_LEFT] == self);
+ } else {
+ KASSERT(diff > 0);
+ KASSERT(RB_FATHER(self)->rb_nodes[RB_DIR_RIGHT] == self);
+ }
+ }
+
+ /*
+ * Verify our position in the linked list against the tree itself.
+ */
+ {
+ const struct rb_node *prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);
+ const struct rb_node *next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);
+ KASSERT(prev0 == TAILQ_PREV(self, rb_node_qh, rb_link));
+ KASSERT(next0 == TAILQ_NEXT(self, rb_link));
+#ifndef RBSMALL
+ KASSERT(prev0 != NULL || self == rbt->rbt_minmax[RB_DIR_LEFT]);
+ KASSERT(next0 != NULL || self == rbt->rbt_minmax[RB_DIR_RIGHT]);
+#endif
+ }
+
+ /*
+ * The root must be black.
+ * There can never be two adjacent red nodes.
+ */
+ if (red_check) {
+ KASSERT(!RB_ROOT_P(rbt, self) || RB_BLACK_P(self));
+ (void) rb_tree_count_black(self);
+ if (RB_RED_P(self)) {
+ const struct rb_node *brother;
+ KASSERT(!RB_ROOT_P(rbt, self));
+ brother = RB_FATHER(self)->rb_nodes[RB_POSITION(self) ^ RB_DIR_OTHER];
+ KASSERT(RB_BLACK_P(RB_FATHER(self)));
+ /*
+ * I'm red and have no children, then I must either
+ * have no brother or my brother also be red and
+ * also have no children. (black count == 0)
+ */
+ KASSERT(!RB_CHILDLESS_P(self)
+ || RB_SENTINEL_P(brother)
+ || RB_RED_P(brother)
+ || RB_CHILDLESS_P(brother));
+ /*
+ * If I'm not childless, I must have two children
+ * and they must be both be black.
+ */
+ KASSERT(RB_CHILDLESS_P(self)
+ || (RB_TWOCHILDREN_P(self)
+ && RB_BLACK_P(self->rb_left)
+ && RB_BLACK_P(self->rb_right)));
+ /*
+ * If I'm not childless, thus I have black children,
+ * then my brother must either be black or have two
+ * black children.
+ */
+ KASSERT(RB_CHILDLESS_P(self)
+ || RB_BLACK_P(brother)
+ || (RB_TWOCHILDREN_P(brother)
+ && RB_BLACK_P(brother->rb_left)
+ && RB_BLACK_P(brother->rb_right)));
+ } else {
+ /*
+ * If I'm black and have one child, that child must
+ * be red and childless.
+ */
+ KASSERT(RB_CHILDLESS_P(self)
+ || RB_TWOCHILDREN_P(self)
+ || (!RB_LEFT_SENTINEL_P(self)
+ && RB_RIGHT_SENTINEL_P(self)
+ && RB_RED_P(self->rb_left)
+ && RB_CHILDLESS_P(self->rb_left))
+ || (!RB_RIGHT_SENTINEL_P(self)
+ && RB_LEFT_SENTINEL_P(self)
+ && RB_RED_P(self->rb_right)
+ && RB_CHILDLESS_P(self->rb_right)));
+
+ /*
+ * If I'm a childless black node and my parent is
+ * black, my 2nd closet relative away from my parent
+ * is either red or has a red parent or red children.
+ */
+ if (!RB_ROOT_P(rbt, self)
+ && RB_CHILDLESS_P(self)
+ && RB_BLACK_P(RB_FATHER(self))) {
+ const unsigned int which = RB_POSITION(self);
+ const unsigned int other = which ^ RB_DIR_OTHER;
+ const struct rb_node *relative0, *relative;
+
+ relative0 = rb_tree_iterate_const(rbt,
+ self, other);
+ KASSERT(relative0 != NULL);
+ relative = rb_tree_iterate_const(rbt,
+ relative0, other);
+ KASSERT(relative != NULL);
+ KASSERT(RB_SENTINEL_P(relative->rb_nodes[which]));
+#if 0
+ KASSERT(RB_RED_P(relative)
+ || RB_RED_P(relative->rb_left)
+ || RB_RED_P(relative->rb_right)
+ || RB_RED_P(RB_FATHER(relative)));
+#endif
+ }
+ }
+ /*
+ * A grandparent's children must be real nodes and not
+ * sentinels. First check out grandparent.
+ */
+ KASSERT(RB_ROOT_P(rbt, self)
+ || RB_ROOT_P(rbt, RB_FATHER(self))
+ || RB_TWOCHILDREN_P(RB_FATHER(RB_FATHER(self))));
+ /*
+ * If we are have grandchildren on our left, then
+ * we must have a child on our right.
+ */
+ KASSERT(RB_LEFT_SENTINEL_P(self)
+ || RB_CHILDLESS_P(self->rb_left)
+ || !RB_RIGHT_SENTINEL_P(self));
+ /*
+ * If we are have grandchildren on our right, then
+ * we must have a child on our left.
+ */
+ KASSERT(RB_RIGHT_SENTINEL_P(self)
+ || RB_CHILDLESS_P(self->rb_right)
+ || !RB_LEFT_SENTINEL_P(self));
+
+ /*
+ * If we have a child on the left and it doesn't have two
+ * children make sure we don't have great-great-grandchildren on
+ * the right.
+ */
+ KASSERT(RB_TWOCHILDREN_P(self->rb_left)
+ || RB_CHILDLESS_P(self->rb_right)
+ || RB_CHILDLESS_P(self->rb_right->rb_left)
+ || RB_CHILDLESS_P(self->rb_right->rb_left->rb_left)
+ || RB_CHILDLESS_P(self->rb_right->rb_left->rb_right)
+ || RB_CHILDLESS_P(self->rb_right->rb_right)
+ || RB_CHILDLESS_P(self->rb_right->rb_right->rb_left)
+ || RB_CHILDLESS_P(self->rb_right->rb_right->rb_right));
+
+ /*
+ * If we have a child on the right and it doesn't have two
+ * children make sure we don't have great-great-grandchildren on
+ * the left.
+ */
+ KASSERT(RB_TWOCHILDREN_P(self->rb_right)
+ || RB_CHILDLESS_P(self->rb_left)
+ || RB_CHILDLESS_P(self->rb_left->rb_left)
+ || RB_CHILDLESS_P(self->rb_left->rb_left->rb_left)
+ || RB_CHILDLESS_P(self->rb_left->rb_left->rb_right)
+ || RB_CHILDLESS_P(self->rb_left->rb_right)
+ || RB_CHILDLESS_P(self->rb_left->rb_right->rb_left)
+ || RB_CHILDLESS_P(self->rb_left->rb_right->rb_right));
+
+ /*
+ * If we are fully interior node, then our predecessors and
+ * successors must have no children in our direction.
+ */
+ if (RB_TWOCHILDREN_P(self)) {
+ const struct rb_node *prev0;
+ const struct rb_node *next0;
+
+ prev0 = rb_tree_iterate_const(rbt, self, RB_DIR_LEFT);
+ KASSERT(prev0 != NULL);
+ KASSERT(RB_RIGHT_SENTINEL_P(prev0));
+
+ next0 = rb_tree_iterate_const(rbt, self, RB_DIR_RIGHT);
+ KASSERT(next0 != NULL);
+ KASSERT(RB_LEFT_SENTINEL_P(next0));
+ }
+ }
+
+ return true;
+}
+
+void
+rb_tree_check(const struct rb_tree *rbt, bool red_check)
+{
+ const struct rb_node *self;
+ const struct rb_node *prev;
+#ifdef RBSTATS
+ unsigned int count = 0;
+#endif
+
+ KASSERT(rbt->rbt_root != NULL);
+ KASSERT(RB_LEFT_P(rbt->rbt_root));
+
+#if defined(RBSTATS) && !defined(RBSMALL)
+ KASSERT(rbt->rbt_count > 1
+ || rbt->rbt_minmax[RB_DIR_LEFT] == rbt->rbt_minmax[RB_DIR_RIGHT]);
+#endif
+
+ prev = NULL;
+ TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {
+ rb_tree_check_node(rbt, self, prev, false);
+#ifdef RBSTATS
+ count++;
+#endif
+ }
+#ifdef RBSTATS
+ KASSERT(rbt->rbt_count == count);
+#endif
+ if (red_check) {
+ KASSERT(RB_BLACK_P(rbt->rbt_root));
+ KASSERT(RB_SENTINEL_P(rbt->rbt_root)
+ || rb_tree_count_black(rbt->rbt_root));
+
+ /*
+ * The root must be black.
+ * There can never be two adjacent red nodes.
+ */
+ TAILQ_FOREACH(self, &rbt->rbt_nodes, rb_link) {
+ rb_tree_check_node(rbt, self, NULL, true);
+ }
+ }
+}
+#endif /* RBDEBUG */
+
+#ifdef RBSTATS
+static void
+rb_tree_mark_depth(const struct rb_tree *rbt, const struct rb_node *self,
+ size_t *depths, size_t depth)
+{
+ if (RB_SENTINEL_P(self))
+ return;
+
+ if (RB_TWOCHILDREN_P(self)) {
+ rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);
+ rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);
+ return;
+ }
+ depths[depth]++;
+ if (!RB_LEFT_SENTINEL_P(self)) {
+ rb_tree_mark_depth(rbt, self->rb_left, depths, depth + 1);
+ }
+ if (!RB_RIGHT_SENTINEL_P(self)) {
+ rb_tree_mark_depth(rbt, self->rb_right, depths, depth + 1);
+ }
+}
+
+void
+rb_tree_depths(const struct rb_tree *rbt, size_t *depths)
+{
+ rb_tree_mark_depth(rbt, rbt->rbt_root, depths, 1);
+}
+#endif /* RBSTATS */
diff --git a/compat/rbtree.h b/compat/rbtree.h
new file mode 100644
index 000000000000..656da22a108e
--- /dev/null
+++ b/compat/rbtree.h
@@ -0,0 +1,211 @@
+/* $NetBSD: rbtree.h,v 1.5 2019/03/07 14:39:21 roy Exp $ */
+
+/*-
+ * Copyright (c) 2001 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to The NetBSD Foundation
+ * by Matt Thomas <matt@3am-software.com>.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef _SYS_RBTREE_H_
+#define _SYS_RBTREE_H_
+
+#include "config.h"
+#include "common.h"
+
+#if defined(_KERNEL) || defined(_STANDALONE)
+#include <sys/types.h>
+#else
+#include <stdbool.h>
+#include <inttypes.h>
+#endif
+#ifdef HAVE_SYS_QUEUE_H
+#include <sys/queue.h>
+#else
+#include "queue.h"
+#endif
+#if !defined(__linux__) && !defined(__QNX__) && !defined(__sun)
+#include <sys/endian.h>
+#else
+#include "endian.h"
+#endif
+
+__BEGIN_DECLS
+
+typedef struct rb_node {
+ struct rb_node *rb_nodes[2];
+#define RB_DIR_LEFT 0
+#define RB_DIR_RIGHT 1
+#define RB_DIR_OTHER 1
+#define rb_left rb_nodes[RB_DIR_LEFT]
+#define rb_right rb_nodes[RB_DIR_RIGHT]
+
+ /*
+ * rb_info contains the two flags and the parent back pointer.
+ * We put the two flags in the low two bits since we know that
+ * rb_node will have an alignment of 4 or 8 bytes.
+ */
+ uintptr_t rb_info;
+#define RB_FLAG_POSITION (uintptr_t)0x2
+#define RB_FLAG_RED (uintptr_t)0x1
+#define RB_FLAG_MASK (RB_FLAG_POSITION|RB_FLAG_RED)
+#define RB_FATHER(rb) \
+ ((struct rb_node *)((rb)->rb_info & ~RB_FLAG_MASK))
+#define RB_SET_FATHER(rb, father) \
+ ((void)((rb)->rb_info = (uintptr_t)(father)|((rb)->rb_info & RB_FLAG_MASK)))
+
+#define RB_SENTINEL_P(rb) ((rb) == NULL)
+#define RB_LEFT_SENTINEL_P(rb) RB_SENTINEL_P((rb)->rb_left)
+#define RB_RIGHT_SENTINEL_P(rb) RB_SENTINEL_P((rb)->rb_right)
+#define RB_FATHER_SENTINEL_P(rb) RB_SENTINEL_P(RB_FATHER((rb)))
+#define RB_CHILDLESS_P(rb) \
+ (RB_SENTINEL_P(rb) || (RB_LEFT_SENTINEL_P(rb) && RB_RIGHT_SENTINEL_P(rb)))
+#define RB_TWOCHILDREN_P(rb) \
+ (!RB_SENTINEL_P(rb) && !RB_LEFT_SENTINEL_P(rb) && !RB_RIGHT_SENTINEL_P(rb))
+
+#define RB_POSITION(rb) \
+ (((rb)->rb_info & RB_FLAG_POSITION) ? RB_DIR_RIGHT : RB_DIR_LEFT)
+#define RB_RIGHT_P(rb) (RB_POSITION(rb) == RB_DIR_RIGHT)
+#define RB_LEFT_P(rb) (RB_POSITION(rb) == RB_DIR_LEFT)
+#define RB_RED_P(rb) (!RB_SENTINEL_P(rb) && ((rb)->rb_info & RB_FLAG_RED) != 0)
+#define RB_BLACK_P(rb) (RB_SENTINEL_P(rb) || ((rb)->rb_info & RB_FLAG_RED) == 0)
+#define RB_MARK_RED(rb) ((void)((rb)->rb_info |= RB_FLAG_RED))
+#define RB_MARK_BLACK(rb) ((void)((rb)->rb_info &= ~RB_FLAG_RED))
+#define RB_INVERT_COLOR(rb) ((void)((rb)->rb_info ^= RB_FLAG_RED))
+#define RB_ROOT_P(rbt, rb) ((rbt)->rbt_root == (rb))
+#define RB_SET_POSITION(rb, position) \
+ ((void)((position) ? ((rb)->rb_info |= RB_FLAG_POSITION) : \
+ ((rb)->rb_info &= ~RB_FLAG_POSITION)))
+#define RB_ZERO_PROPERTIES(rb) ((void)((rb)->rb_info &= ~RB_FLAG_MASK))
+#define RB_COPY_PROPERTIES(dst, src) \
+ ((void)((dst)->rb_info ^= ((dst)->rb_info ^ (src)->rb_info) & RB_FLAG_MASK))
+#define RB_SWAP_PROPERTIES(a, b) do { \
+ uintptr_t xorinfo = ((a)->rb_info ^ (b)->rb_info) & RB_FLAG_MASK; \
+ (a)->rb_info ^= xorinfo; \
+ (b)->rb_info ^= xorinfo; \
+ } while (/*CONSTCOND*/ 0)
+#ifdef RBDEBUG
+ TAILQ_ENTRY(rb_node) rb_link;
+#endif
+} rb_node_t;
+
+#define RB_TREE_MIN(T) rb_tree_iterate((T), NULL, RB_DIR_LEFT)
+#define RB_TREE_MAX(T) rb_tree_iterate((T), NULL, RB_DIR_RIGHT)
+#define RB_TREE_NEXT(T, N) rb_tree_iterate((T), (N), RB_DIR_RIGHT)
+#define RB_TREE_PREV(T, N) rb_tree_iterate((T), (N), RB_DIR_LEFT)
+#define RB_TREE_FOREACH(N, T) \
+ for ((N) = RB_TREE_MIN(T); (N); (N) = RB_TREE_NEXT((T), (N)))
+#define RB_TREE_FOREACH_REVERSE(N, T) \
+ for ((N) = RB_TREE_MAX(T); (N); (N) = RB_TREE_PREV((T), (N)))
+#define RB_TREE_FOREACH_SAFE(N, T, S) \
+ for ((N) = RB_TREE_MIN(T); \
+ (N) && ((S) = RB_TREE_NEXT((T), (N)), 1); \
+ (N) = (S))
+#define RB_TREE_FOREACH_REVERSE_SAFE(N, T, S) \
+ for ((N) = RB_TREE_MAX(T); \
+ (N) && ((S) = RB_TREE_PREV((T), (N)), 1); \
+ (N) = (S))
+
+#ifdef RBDEBUG
+TAILQ_HEAD(rb_node_qh, rb_node);
+
+#define RB_TAILQ_REMOVE(a, b, c) TAILQ_REMOVE(a, b, c)
+#define RB_TAILQ_INIT(a) TAILQ_INIT(a)
+#define RB_TAILQ_INSERT_HEAD(a, b, c) TAILQ_INSERT_HEAD(a, b, c)
+#define RB_TAILQ_INSERT_BEFORE(a, b, c) TAILQ_INSERT_BEFORE(a, b, c)
+#define RB_TAILQ_INSERT_AFTER(a, b, c, d) TAILQ_INSERT_AFTER(a, b, c, d)
+#else
+#define RB_TAILQ_REMOVE(a, b, c) do { } while (/*CONSTCOND*/0)
+#define RB_TAILQ_INIT(a) do { } while (/*CONSTCOND*/0)
+#define RB_TAILQ_INSERT_HEAD(a, b, c) do { } while (/*CONSTCOND*/0)
+#define RB_TAILQ_INSERT_BEFORE(a, b, c) do { } while (/*CONSTCOND*/0)
+#define RB_TAILQ_INSERT_AFTER(a, b, c, d) do { } while (/*CONSTCOND*/0)
+#endif /* RBDEBUG */
+
+/*
+ * rbto_compare_nodes_fn:
+ * return a positive value if the first node > the second node.
+ * return a negative value if the first node < the second node.
+ * return 0 if they are considered same.
+ *
+ * rbto_compare_key_fn:
+ * return a positive value if the node > the key.
+ * return a negative value if the node < the key.
+ * return 0 if they are considered same.
+ */
+
+typedef signed int (*rbto_compare_nodes_fn)(void *, const void *, const void *);
+typedef signed int (*rbto_compare_key_fn)(void *, const void *, const void *);
+
+typedef struct {
+ rbto_compare_nodes_fn rbto_compare_nodes;
+ rbto_compare_key_fn rbto_compare_key;
+ size_t rbto_node_offset;
+ void *rbto_context;
+} rb_tree_ops_t;
+
+typedef struct rb_tree {
+ struct rb_node *rbt_root;
+ const rb_tree_ops_t *rbt_ops;
+ struct rb_node *rbt_minmax[2];
+#ifdef RBDEBUG
+ struct rb_node_qh rbt_nodes;
+#endif
+#ifdef RBSTATS
+ unsigned int rbt_count;
+ unsigned int rbt_insertions;
+ unsigned int rbt_removals;
+ unsigned int rbt_insertion_rebalance_calls;
+ unsigned int rbt_insertion_rebalance_passes;
+ unsigned int rbt_removal_rebalance_calls;
+ unsigned int rbt_removal_rebalance_passes;
+#endif
+} rb_tree_t;
+
+#ifdef RBSTATS
+#define RBSTAT_INC(v) ((void)((v)++))
+#define RBSTAT_DEC(v) ((void)((v)--))
+#else
+#define RBSTAT_INC(v) do { } while (/*CONSTCOND*/0)
+#define RBSTAT_DEC(v) do { } while (/*CONSTCOND*/0)
+#endif
+
+void rb_tree_init(rb_tree_t *, const rb_tree_ops_t *);
+void * rb_tree_insert_node(rb_tree_t *, void *);
+void * rb_tree_find_node(rb_tree_t *, const void *);
+void * rb_tree_find_node_geq(rb_tree_t *, const void *);
+void * rb_tree_find_node_leq(rb_tree_t *, const void *);
+void rb_tree_remove_node(rb_tree_t *, void *);
+void * rb_tree_iterate(rb_tree_t *, void *, const unsigned int);
+#ifdef RBDEBUG
+void rb_tree_check(const rb_tree_t *, bool);
+#endif
+#ifdef RBSTATS
+void rb_tree_depths(const rb_tree_t *, size_t *);
+#endif
+
+__END_DECLS
+
+#endif /* _SYS_RBTREE_H_*/
diff --git a/compat/reallocarray.c b/compat/reallocarray.c
new file mode 100644
index 000000000000..9ff9c20b30fb
--- /dev/null
+++ b/compat/reallocarray.c
@@ -0,0 +1,60 @@
+/* $NetBSD: reallocarr.c,v 1.4 2015/08/20 20:08:04 joerg Exp $ */
+
+/*-
+ * Copyright (c) 2015 Joerg Sonnenberger <joerg@NetBSD.org>.
+ * 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 HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <errno.h>
+#include <limits.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+/*
+ * To be clear, this is NetBSD's more refined reallocarr(3) function
+ * made to look like OpenBSD's more useable reallocarray(3) interface.
+ */
+#include "reallocarray.h"
+
+#define SQRT_SIZE_MAX (((size_t)1) << (sizeof(size_t) * CHAR_BIT / 2))
+void *
+reallocarray(void *ptr, size_t n, size_t size)
+{
+
+ /*
+ * Try to avoid division here.
+ *
+ * It isn't possible to overflow during multiplication if neither
+ * operand uses any of the most significant half of the bits.
+ */
+ if ((n | size) >= SQRT_SIZE_MAX && n > SIZE_MAX / size) {
+ errno = EOVERFLOW;
+ return NULL;
+ }
+ return realloc(ptr, n * size);
+}
diff --git a/compat/reallocarray.h b/compat/reallocarray.h
new file mode 100644
index 000000000000..d855e7b259fb
--- /dev/null
+++ b/compat/reallocarray.h
@@ -0,0 +1,37 @@
+/* $NetBSD: reallocarr.c,v 1.4 2015/08/20 20:08:04 joerg Exp $ */
+
+/*-
+ * Copyright (c) 2015 Joerg Sonnenberger <joerg@NetBSD.org>.
+ * 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 HOLDERS 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 REALLOCARRAY_H
+#define REALLOCARRAY_H
+
+void *reallocarray(void *, size_t, size_t);
+
+#endif
diff --git a/compat/setproctitle.c b/compat/setproctitle.c
new file mode 100644
index 000000000000..8c03c3922c07
--- /dev/null
+++ b/compat/setproctitle.c
@@ -0,0 +1,331 @@
+/*
+ * Copyright © 2010 William Ahern
+ * Copyright © 2012-2013 Guillem Jover <guillem@hadrons.org>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to permit
+ * persons to whom the Software is furnished to do so, subject to the
+ * following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN
+ * NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+ * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
+ * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
+ * USE OR OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+#include <errno.h>
+#include <stddef.h>
+#include <stdarg.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <err.h>
+#include <unistd.h>
+#include <string.h>
+//#include "local-link.h"
+
+#include "config.h"
+
+static struct {
+ /* Original value. */
+ char *arg0;
+
+ /* Title space available. */
+ char *base, *end;
+
+ /* Pointer to original nul character within base. */
+ char *nul;
+
+ bool warned;
+ bool reset;
+ int error;
+
+ /* Our copy of args and environment to free. */
+ int argc;
+ char **argv;
+ char **tmp_environ;
+} SPT;
+
+
+static inline size_t
+spt_min(size_t a, size_t b)
+{
+ return a < b ? a : b;
+}
+
+/*
+ * For discussion on the portability of the various methods, see
+ * https://lists.freebsd.org/pipermail/freebsd-stable/2008-June/043136.html
+ */
+static int
+spt_clearenv(void)
+{
+#ifdef HAVE_CLEARENV
+ return clearenv();
+#else
+ SPT.tmp_environ = malloc(sizeof(*SPT.tmp_environ));
+ if (SPT.tmp_environ == NULL)
+ return errno;
+
+ SPT.tmp_environ[0] = NULL;
+ environ = SPT.tmp_environ;
+
+ return 0;
+#endif
+}
+
+static int
+spt_copyenv(int envc, char *envp[])
+{
+ char **envcopy;
+ char *eq;
+ size_t envsize;
+ int i, error;
+
+ if (environ != envp)
+ return 0;
+
+ /* Make a copy of the old environ array of pointers, in case
+ * clearenv() or setenv() is implemented to free the internal
+ * environ array, because we will need to access the old environ
+ * contents to make the new copy. */
+ envsize = (size_t)(envc + 1) * sizeof(char *);
+ envcopy = malloc(envsize);
+ if (envcopy == NULL)
+ return errno;
+ memcpy(envcopy, envp, envsize);
+
+ error = spt_clearenv();
+ if (error) {
+ environ = envp;
+ free(envcopy);
+ return error;
+ }
+
+ for (i = 0; envcopy[i]; i++) {
+ eq = strchr(envcopy[i], '=');
+ if (eq == NULL)
+ continue;
+
+ *eq = '\0';
+ if (setenv(envcopy[i], eq + 1, 1) < 0)
+ error = errno;
+ *eq = '=';
+
+ if (error) {
+#ifdef HAVE_CLEARENV
+ /* Because the old environ might not be available
+ * anymore we will make do with the shallow copy. */
+ environ = envcopy;
+#else
+ environ = envp;
+ free(envcopy);
+#endif
+ return error;
+ }
+ }
+
+ /* Dispose of the shallow copy, now that we've finished transfering
+ * the old environment. */
+ free(envcopy);
+
+ return 0;
+}
+
+static int
+spt_copyargs(int argc, char *argv[])
+{
+ char *tmp;
+ int i;
+
+ for (i = 1; i < argc || (i >= argc && argv[i]); i++) {
+ if (argv[i] == NULL)
+ continue;
+
+ tmp = strdup(argv[i]);
+ if (tmp == NULL)
+ return errno;
+
+ argv[i] = tmp;
+ }
+
+ return 0;
+}
+
+void
+setproctitle_init(int argc, char *argv[], char *envp[])
+{
+ char *base, *end, *nul, *tmp;
+ int i, envc, error;
+
+ /* Try to make sure we got called with main() arguments. */
+ if (argc < 0)
+ return;
+
+ base = argv[0];
+ if (base == NULL)
+ return;
+
+ nul = &base[strlen(base)];
+ end = nul + 1;
+
+ for (i = 0; i < argc || (i >= argc && argv[i]); i++) {
+ if (argv[i] == NULL || argv[i] != end)
+ continue;
+
+ end = argv[i] + strlen(argv[i]) + 1;
+ }
+
+ for (i = 0; envp[i]; i++) {
+ if (envp[i] != end)
+ continue;
+
+ end = envp[i] + strlen(envp[i]) + 1;
+ }
+ envc = i;
+
+ SPT.arg0 = strdup(argv[0]);
+ if (SPT.arg0 == NULL) {
+ SPT.error = errno;
+ return;
+ }
+
+ tmp = strdup(getprogname());
+ if (tmp == NULL) {
+ SPT.error = errno;
+ return;
+ }
+ setprogname(tmp);
+
+ error = spt_copyenv(envc, envp);
+ if (error) {
+ SPT.error = error;
+ return;
+ }
+
+ error = spt_copyargs(argc, argv);
+ if (error) {
+ SPT.error = error;
+ return;
+ }
+
+ SPT.argc = argc;
+ SPT.argv = argv;
+
+ SPT.nul = nul;
+ SPT.base = base;
+ SPT.end = end;
+}
+
+void
+setproctitle_fini(void)
+{
+ int i;
+
+ free(SPT.arg0);
+ SPT.arg0 = NULL;
+
+ for (i = 1; i < SPT.argc; i++) {
+ if (SPT.argv[i] != NULL)
+ free(SPT.argv[i]);
+ }
+ SPT.argc = 0;
+
+ free(SPT.tmp_environ);
+ SPT.tmp_environ = NULL;
+}
+
+#ifndef SPT_MAXTITLE
+#define SPT_MAXTITLE 255
+#endif
+
+__printflike(1, 2) static void
+setproctitle_impl(const char *fmt, ...)
+{
+ /* Use buffer in case argv[0] is passed. */
+ char buf[SPT_MAXTITLE + 1];
+ va_list ap;
+ char *nul;
+ int l;
+ size_t len, base_len;
+
+ if (SPT.base == NULL) {
+ if (!SPT.warned) {
+ warnx("setproctitle not initialized, please either call "
+ "setproctitle_init() or link against libbsd-ctor.");
+ SPT.warned = true;
+ }
+ return;
+ }
+
+ if (fmt) {
+ if (fmt[0] == '-') {
+ /* Skip program name prefix. */
+ fmt++;
+ len = 0;
+ } else {
+ /* Print program name heading for grep. */
+ l = snprintf(buf, sizeof(buf), "%s: ", getprogname());
+ if (l <= 0)
+ return;
+ len = (size_t)l;
+ }
+
+ va_start(ap, fmt);
+ l = vsnprintf(buf + len, sizeof(buf) - len, fmt, ap);
+ va_end(ap);
+ } else {
+ len = 0;
+ l = snprintf(buf, sizeof(buf), "%s", SPT.arg0);
+ }
+
+ if (l <= 0) {
+ SPT.error = errno;
+ return;
+ }
+ len += (size_t)l;
+
+ base_len = (size_t)(SPT.end - SPT.base);
+ if (!SPT.reset) {
+ memset(SPT.base, 0, base_len);
+ SPT.reset = true;
+ } else {
+ memset(SPT.base, 0, spt_min(sizeof(buf), base_len));
+ }
+
+ len = spt_min(len, spt_min(sizeof(buf), base_len) - 1);
+ memcpy(SPT.base, buf, len);
+ nul = &SPT.base[len];
+
+ if (nul < SPT.nul) {
+ *SPT.nul = '.';
+ } else if (nul == SPT.nul && &nul[1] < SPT.end) {
+ *SPT.nul = ' ';
+ *++nul = '\0';
+ }
+}
+libbsd_symver_default(setproctitle, setproctitle_impl, LIBBSD_0.5);
+
+/* The original function introduced in 0.2 was a stub, it only got implemented
+ * in 0.5, make the implementation available in the old version as an alias
+ * for code linking against that version, and change the default to use the
+ * new version, so that new code depends on the implemented version. */
+#ifdef HAVE_TYPEOF
+extern __typeof__(setproctitle_impl)
+setproctitle_stub
+ __attribute__((__alias__("setproctitle_impl")));
+#else
+void
+setproctitle_stub(const char *fmt, ...)
+ __attribute__((__alias__("setproctitle_impl")));
+#endif
+libbsd_symver_variant(setproctitle, setproctitle_stub, LIBBSD_0.2);
diff --git a/compat/setproctitle.h b/compat/setproctitle.h
new file mode 100644
index 000000000000..32dc56bdd38f
--- /dev/null
+++ b/compat/setproctitle.h
@@ -0,0 +1,58 @@
+/*
+ * Copyright © 2010 William Ahern
+ * Copyright © 2012-2013 Guillem Jover <guillem@hadrons.org>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to permit
+ * persons to whom the Software is furnished to do so, subject to the
+ * following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included
+ * in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
+ * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN
+ * NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
+ * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
+ * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
+ * USE OR OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+#ifndef SETPROCTITLE_H
+#define SETPROCTITLE_H
+
+#ifndef __printflike
+#if __GNUC__ > 2 || defined(__INTEL_COMPILER)
+#define __printflike(a, b) __attribute__((format(printf, a, b)))
+#else
+#define __printflike(a, b)
+#endif
+#endif /* !__printflike */
+
+/* WEXITSTATUS is defined in stdlib.h which defines free() */
+#ifdef WEXITSTATUS
+static inline const char *
+getprogname(void)
+{
+ return "dhcpcd";
+}
+static inline void
+setprogname(char *name)
+{
+ free(name);
+}
+#endif
+
+void setproctitle_init(int, char *[], char *[]);
+__printflike(1, 2) void setproctitle(const char *, ...);
+void setproctitle_fini(void);
+
+#define libbsd_symver_default(alias, symbol, version) \
+ extern __typeof(symbol) alias __attribute__((__alias__(#symbol)))
+
+#define libbsd_symver_variant(alias, symbol, version)
+#endif
diff --git a/compat/strlcpy.c b/compat/strlcpy.c
new file mode 100644
index 000000000000..1fb4a2f9615d
--- /dev/null
+++ b/compat/strlcpy.c
@@ -0,0 +1,51 @@
+/* $OpenBSD: strlcpy.c,v 1.15 2016/10/16 17:37:39 dtucker Exp $ */
+
+/*
+ * Copyright (c) 1998, 2015 Todd C. Miller <Todd.Miller@courtesan.com>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <sys/types.h>
+
+#include "strlcpy.h"
+
+/*
+ * Copy string src to buffer dst of size dsize. At most dsize-1
+ * chars will be copied. Always NUL terminates (unless dsize == 0).
+ * Returns strlen(src); if retval >= dsize, truncation occurred.
+ */
+size_t
+strlcpy(char *dst, const char *src, size_t dsize)
+{
+ const char *osrc = src;
+ size_t nleft = dsize;
+
+ /* Copy as many bytes as will fit. */
+ if (nleft != 0) {
+ while (--nleft != 0) {
+ if ((*dst++ = *src++) == '\0')
+ break;
+ }
+ }
+
+ /* Not enough room in dst, add NUL and traverse rest of src. */
+ if (nleft == 0) {
+ if (dsize != 0)
+ *dst = '\0'; /* NUL-terminate dst */
+ while (*src++)
+ ;
+ }
+
+ return (size_t)(src - osrc - 1); /* count does not include NUL */
+}
diff --git a/compat/strlcpy.h b/compat/strlcpy.h
new file mode 100644
index 000000000000..2131cdec305f
--- /dev/null
+++ b/compat/strlcpy.h
@@ -0,0 +1,24 @@
+/* $OpenBSD: strlcpy.c,v 1.15 2016/10/16 17:37:39 dtucker Exp $ */
+
+/*
+ * Copyright (c) 1998, 2015 Todd C. Miller <Todd.Miller@courtesan.com>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifndef STRLCPY_H
+#define STRLCPY_H
+
+size_t strlcpy(char *, const char *, size_t);
+
+#endif
diff --git a/compat/strtoi.c b/compat/strtoi.c
new file mode 100644
index 000000000000..567d86edde89
--- /dev/null
+++ b/compat/strtoi.c
@@ -0,0 +1,68 @@
+/* $NetBSD: strtoi.c,v 1.3 2019/11/28 12:33:23 roy Exp $ */
+
+/*-
+ * Copyright (c) 2005 The DragonFly Project. All rights reserved.
+ * Copyright (c) 2003 Citrus Project,
+ * 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 AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * Created by Kamil Rytarowski, based on ID:
+ * NetBSD: src/common/lib/libc/stdlib/strtoul.c,v 1.3 2008/08/20 19:58:34 oster Exp
+ */
+
+#if defined(HAVE_NBTOOL_CONFIG_H) && HAVE_NBTOOL_CONFIG_H
+#include "nbtool_config.h"
+#endif
+
+#ifdef _LIBC
+#include "namespace.h"
+#endif
+
+#if defined(_KERNEL)
+#include <sys/param.h>
+#include <sys/types.h>
+#include <lib/libkern/libkern.h>
+#elif defined(_STANDALONE)
+#include <sys/param.h>
+#include <sys/types.h>
+#include <lib/libkern/libkern.h>
+#include <lib/libsa/stand.h>
+#else
+#include <stddef.h>
+#include <assert.h>
+#include <errno.h>
+#include <inttypes.h>
+#endif
+
+#include "strtoi.h"
+
+#define _FUNCNAME strtoi
+#define __TYPE intmax_t
+#define __WRAPPED strtoimax
+
+#include "_strtoi.h"
+
+#ifdef _LIBC
+__weak_alias(strtoi, _strtoi)
+__weak_alias(strtoi_l, _strtoi_l)
+#endif
diff --git a/compat/strtoi.h b/compat/strtoi.h
new file mode 100644
index 000000000000..bd976fcf3ca3
--- /dev/null
+++ b/compat/strtoi.h
@@ -0,0 +1,45 @@
+/*-
+ * Copyright (c) 1990, 1993
+ * The Regents of the University of California. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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.
+ *
+ * Original version ID:
+ * NetBSD: src/lib/libc/locale/_wcstoul.h,v 1.2 2003/08/07 16:43:03 agc Exp
+ *
+ * Created by Kamil Rytarowski, based on ID:
+ * NetBSD: src/common/lib/libc/stdlib/_strtoul.h,v 1.7 2013/05/17 12:55:56 joerg Exp
+ */
+
+#ifndef STRTOI_H
+#define STRTOI_H
+
+#include <inttypes.h>
+
+intmax_t strtoi(const char * __restrict nptr, char ** __restrict endptr,
+ int base, intmax_t lo, intmax_t hi, int *rstatus);
+uintmax_t strtou(const char * __restrict nptr, char ** __restrict endptr,
+ int base, uintmax_t lo, uintmax_t hi, int *rstatus);
+#endif
diff --git a/compat/strtou.c b/compat/strtou.c
new file mode 100644
index 000000000000..f300dcc23817
--- /dev/null
+++ b/compat/strtou.c
@@ -0,0 +1,68 @@
+/* $NetBSD: strtou.c,v 1.3 2019/11/28 12:33:23 roy Exp $ */
+
+/*-
+ * Copyright (c) 2005 The DragonFly Project. All rights reserved.
+ * Copyright (c) 2003 Citrus Project,
+ * 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 AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * Created by Kamil Rytarowski, based on ID:
+ * NetBSD: src/common/lib/libc/stdlib/strtoul.c,v 1.3 2008/08/20 19:58:34 oster Exp
+ */
+
+#if defined(HAVE_NBTOOL_CONFIG_H) && HAVE_NBTOOL_CONFIG_H
+#include "nbtool_config.h"
+#endif
+
+#ifdef _LIBC
+#include "namespace.h"
+#endif
+
+#if defined(_KERNEL)
+#include <sys/param.h>
+#include <sys/types.h>
+#include <lib/libkern/libkern.h>
+#elif defined(_STANDALONE)
+#include <sys/param.h>
+#include <sys/types.h>
+#include <lib/libkern/libkern.h>
+#include <lib/libsa/stand.h>
+#else
+#include <stddef.h>
+#include <assert.h>
+#include <errno.h>
+#include <inttypes.h>
+#endif
+
+#include "strtoi.h"
+
+#define _FUNCNAME strtou
+#define __TYPE uintmax_t
+#define __WRAPPED strtoumax
+
+#include "_strtoi.h"
+
+#ifdef _LIBC
+__weak_alias(strtou, _strtou)
+__weak_alias(strtou_l, _strtou_l)
+#endif
generated by cgit v1.3 (git 2.53.0) at 2026-09-17 07:38:00 +0000