Add build system scaffolding and libc headers

37 files changed, 1966 insertions, 0 deletions

diff --git a/lib/libc/stdlib/_Exit.c b/lib/libc/stdlib/_Exit.c
new file mode 100644
index 00000000..beb53e34
--- /dev/null
+++ b/lib/libc/stdlib/_Exit.c
@@ -0,0 +1,6 @@
+#include <unistd.h>
+
+_Noreturn void _Exit(int status)
+{
+	_exit(status);
+}
diff --git a/lib/libc/stdlib/__mb_cur_max.c b/lib/libc/stdlib/__mb_cur_max.c
new file mode 100644
index 00000000..2f8affa2
--- /dev/null
+++ b/lib/libc/stdlib/__mb_cur_max.c
@@ -0,0 +1,6 @@
+int __mb_cur_max(void)
+{
+	// TODO: if locale (c/utf8) will be implemented
+	// then return the correct value here if c then 1 else if utf8 then 4
+	return 1;
+}
diff --git a/lib/libc/stdlib/abort.c b/lib/libc/stdlib/abort.c
new file mode 100644
index 00000000..3d022e70
--- /dev/null
+++ b/lib/libc/stdlib/abort.c
@@ -0,0 +1,27 @@
+#include <atomic.h>
+#include <stdlib.h>
+#include <syscall.h>
+#include <asm-generic/signal.h>
+#include <thread.h>
+#include <threads.h>
+#include <unistd.h>
+#include <libc.h>
+
+int raise(int);
+
+_Noreturn void abort(void)
+{
+	struct sigaction sa;
+
+	raise(SIGABRT);
+
+	LIBC_LOCK(libc.lock.abort);
+	sa.sa_handler = SIG_DFL;
+
+	__syscall(rt_sigaction, SIGABRT, &sa, NULL, _NSIG / 8);
+	__syscall(tkill, thrd_current()->tid, SIGABRT);
+
+	// This point should never be reached
+	raise(SIGKILL);
+	_exit(127);
+}
diff --git a/lib/libc/stdlib/abs.c b/lib/libc/stdlib/abs.c
new file mode 100644
index 00000000..ac2bc605
--- /dev/null
+++ b/lib/libc/stdlib/abs.c
@@ -0,0 +1,4 @@
+int abs(int i)
+{
+	return (i < 0) ? -i : i;
+}
diff --git a/lib/libc/stdlib/aligned_alloc.c b/lib/libc/stdlib/aligned_alloc.c
new file mode 100644
index 00000000..f978dfa9
--- /dev/null
+++ b/lib/libc/stdlib/aligned_alloc.c
@@ -0,0 +1,39 @@
+#include <errno.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <sys/mman.h>
+#include <unistd.h>
+
+void *aligned_alloc(size_t alignment, size_t size)
+{
+	if (alignment == 0 || (alignment & (alignment - 1)) != 0) {
+		errno = EINVAL;
+		return NULL;
+	}
+
+	if (size % alignment != 0) {
+		errno = EINVAL;
+		return NULL;
+	}
+
+	if (size == 0) {
+		return NULL;
+	}
+
+	size_t total_size = size + alignment - 1 + sizeof(void *);
+
+	void *raw_ptr = malloc(total_size);
+	if (raw_ptr == NULL) {
+		errno = ENOMEM;
+		return NULL;
+	}
+
+	uintptr_t raw_addr = (uintptr_t)raw_ptr;
+	uintptr_t aligned_addr = (raw_addr + sizeof(void *) + alignment - 1) &
+				 ~(alignment - 1);
+
+	void **orig_ptr_slot = (void **)(aligned_addr - sizeof(void *));
+	*orig_ptr_slot = raw_ptr;
+
+	return (void *)aligned_addr;
+}
diff --git a/lib/libc/stdlib/atexit.c b/lib/libc/stdlib/atexit.c
new file mode 100644
index 00000000..6c84fd4a
--- /dev/null
+++ b/lib/libc/stdlib/atexit.c
@@ -0,0 +1,16 @@
+#include <stdlib.h>
+
+static void (*__atexit_fvec[32])(void) = { NULL };
+
+int atexit(void (*func)(void))
+{
+	for (int i = 0; i < 32; i++) {
+		if (__atexit_fvec[i] == NULL) {
+			__atexit_fvec[i] = func;
+			__atexit_fvec[i + 1] = NULL;
+			return 0;
+		}
+	}
+
+	return -1;
+}
diff --git a/lib/libc/stdlib/atof.c b/lib/libc/stdlib/atof.c
new file mode 100644
index 00000000..5f5fc91f
--- /dev/null
+++ b/lib/libc/stdlib/atof.c
@@ -0,0 +1,6 @@
+#include <stdlib.h>
+
+double atof(const char *str)
+{
+	return strtod(str, (char **)NULL);
+}
diff --git a/lib/libc/stdlib/atoi.c b/lib/libc/stdlib/atoi.c
new file mode 100644
index 00000000..97b663d1
--- /dev/null
+++ b/lib/libc/stdlib/atoi.c
@@ -0,0 +1,6 @@
+#include <stdlib.h>
+
+int atoi(const char *str)
+{
+	return (int)strtol(str, (char **)NULL, 10);
+}
diff --git a/lib/libc/stdlib/atol.c b/lib/libc/stdlib/atol.c
new file mode 100644
index 00000000..976f9997
--- /dev/null
+++ b/lib/libc/stdlib/atol.c
@@ -0,0 +1,6 @@
+#include <stdlib.h>
+
+long atol(const char *nptr)
+{
+	return strtol(nptr, (char **)NULL, 10);
+}
diff --git a/lib/libc/stdlib/atoll.c b/lib/libc/stdlib/atoll.c
new file mode 100644
index 00000000..bea1a031
--- /dev/null
+++ b/lib/libc/stdlib/atoll.c
@@ -0,0 +1,6 @@
+#include <stdlib.h>
+
+long long atoll(const char *nptr)
+{
+	return strtoll(nptr, (char **)NULL, 10);
+}
diff --git a/lib/libc/stdlib/bsearch.c b/lib/libc/stdlib/bsearch.c
new file mode 100644
index 00000000..a2793b0d
--- /dev/null
+++ b/lib/libc/stdlib/bsearch.c
@@ -0,0 +1,87 @@
+/*
+ * Copyright (c) 1990 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. [rescinded 22 July 1999]
+ * 4. 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.
+ */
+
+/*
+
+@deftypefn Supplemental void* bsearch (const void *@var{key}, @
+  const void *@var{base}, size_t @var{nmemb}, size_t @var{size}, @
+  int (*@var{compar})(const void *, const void *))
+
+Performs a search over an array of @var{nmemb} elements pointed to by
+@var{base} for a member that matches the object pointed to by @var{key}.
+The size of each member is specified by @var{size}.  The array contents
+should be sorted in ascending order according to the @var{compar}
+comparison function.  This routine should take two arguments pointing to
+the @var{key} and to an array member, in that order, and should return an
+integer less than, equal to, or greater than zero if the @var{key} object
+is respectively less than, matching, or greater than the array member.
+
+@end deftypefn
+
+*/
+
+#include <sys/types.h> /* size_t */
+#include <stdio.h>
+
+/*
+ * Perform a binary search.
+ *
+ * The code below is a bit sneaky.  After a comparison fails, we
+ * divide the work in half by moving either left or right. If lim
+ * is odd, moving left simply involves halving lim: e.g., when lim
+ * is 5 we look at item 2, so we change lim to 2 so that we will
+ * look at items 0 & 1.  If lim is even, the same applies.  If lim
+ * is odd, moving right again involes halving lim, this time moving
+ * the base up one item past p: e.g., when lim is 5 we change base
+ * to item 3 and make lim 2 so that we will look at items 3 and 4.
+ * If lim is even, however, we have to shrink it by one before
+ * halving: e.g., when lim is 4, we still looked at item 2, so we
+ * have to make lim 3, then halve, obtaining 1, so that we will only
+ * look at item 3.
+ */
+void *bsearch(const void *key, const void *base0, size_t nmemb, size_t size,
+	      int (*compar)(const void *, const void *))
+{
+	const char *base = (const char *)base0;
+	int lim, cmp;
+	const void *p;
+
+	for (lim = nmemb; lim != 0; lim >>= 1) {
+		p = base + (lim >> 1) * size;
+		cmp = (*compar)(key, p);
+		if (cmp == 0)
+			return (void *)p;
+		if (cmp > 0) { /* key > p: move right */
+			base = (const char *)p + size;
+			lim--;
+		} /* else move left */
+	}
+	return (NULL);
+}
diff --git a/lib/libc/stdlib/btowc.c b/lib/libc/stdlib/btowc.c
new file mode 100644
index 00000000..f16865b7
--- /dev/null
+++ b/lib/libc/stdlib/btowc.c
@@ -0,0 +1,18 @@
+#include <wchar.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#define CODEUNIT(c) (0xdfff & (signed char)(c))
+
+wint_t btowc(int c)
+{
+	if ((unsigned char)c < 128U) {
+		return c;
+	}
+
+	if (MB_CUR_MAX == 1 && c != EOF) {
+		return CODEUNIT(c);
+	}
+
+	return WEOF;
+}
diff --git a/lib/libc/stdlib/calloc.c b/lib/libc/stdlib/calloc.c
new file mode 100644
index 00000000..408eef5e
--- /dev/null
+++ b/lib/libc/stdlib/calloc.c
@@ -0,0 +1,25 @@
+#include <errno.h>
+#include <string.h>
+#include <stdlib.h>
+
+void *calloc(size_t nelem, size_t elsize)
+{
+	void *ptr;
+	size_t total;
+
+	if (nelem == 0 || elsize == 0) {
+		errno = EINVAL;
+		return NULL;
+	}
+
+	if (__builtin_mul_overflow(nelem, elsize, &total)) {
+		errno = ENOMEM;
+		return NULL;
+	}
+
+	if ((ptr = malloc(total)) != NULL) {
+		memset(ptr, 0, total);
+	}
+
+	return ptr;
+}
diff --git a/lib/libc/stdlib/div.c b/lib/libc/stdlib/div.c
new file mode 100644
index 00000000..cadc292e
--- /dev/null
+++ b/lib/libc/stdlib/div.c
@@ -0,0 +1,9 @@
+#include <stdlib.h>
+
+div_t div(int numer, int denom)
+{
+	div_t result;
+	result.quot = numer / denom;
+	result.rem = numer % denom;
+	return result;
+}
diff --git a/lib/libc/stdlib/exit.c b/lib/libc/stdlib/exit.c
new file mode 100644
index 00000000..34b8a0f2
--- /dev/null
+++ b/lib/libc/stdlib/exit.c
@@ -0,0 +1,69 @@
+#include <io.h>
+#include <libc.h>
+#include <unistd.h>
+#include <stdio.h>
+
+void (*__dummy_atexit_fvec)(void);
+weak_reference(__dummy_atexit_fvec, __atexit_fvec);
+
+void (*__dummy_stdio_cleanup)(void);
+weak_reference(__dummy_stdio_cleanup, __stdio_cleanup);
+
+static void __fclose(FILE *fp)
+{
+	if (fp == NULL) {
+		return;
+	}
+
+	if (fp->buf_len > 0) {
+		fflush(fp);
+	}
+
+	if (fp->fd > STDERR_FILENO) {
+		close(fp->fd);
+	}
+
+	if (fp->buf) {
+		free(fp->buf);
+	}
+
+	if (fp != stdout && fp != stderr && fp != stdin) {
+		free(fp);
+	}
+}
+
+static void __stdio_cleanup_impl(void)
+{
+	write(1, "HELLO\n", 6);
+	fflush(stdout);
+
+	if (stdout->next != NULL) {
+		FILE *cur = stdout->next;
+		while (cur) {
+			struct __FILE *next = cur->next;
+			__fclose(cur);
+			cur = next;
+		}
+	}
+}
+
+void exit(int status)
+{
+	void (*fptr)(void);
+
+	/* Only do stdio cleanup if it was referenced (meaning stdio was used)
+	 */
+	if (__stdio_cleanup) {
+		__stdio_cleanup_impl();
+	}
+
+	if (__atexit_fvec) {
+		fptr = __atexit_fvec;
+		while (fptr) {
+			fptr();
+			fptr++;
+		}
+	}
+
+	_exit(status);
+}
diff --git a/lib/libc/stdlib/free.c b/lib/libc/stdlib/free.c
new file mode 100644
index 00000000..40320dc7
--- /dev/null
+++ b/lib/libc/stdlib/free.c
@@ -0,0 +1,101 @@
+#include <libc.h>
+#include <sys/mman.h>
+#include <atomic.h>
+#include <malloc.h>
+#include <stdint.h>
+#include <stdbool.h>
+
+void free(void *ptr)
+{
+	if (ptr == NULL) {
+		return;
+	}
+
+	LIBC_LOCK(libc.lock.malloc);
+
+	struct page *p = __malloc_pvec;
+	int found_in_pages = 0;
+
+	while (p) {
+		if ((uintptr_t)ptr >= (uintptr_t)p->heap &&
+		    (uintptr_t)ptr < (uintptr_t)(p->heap + (p->block.size *
+							    p->block.count))) {
+			size_t offset = (uintptr_t)ptr - (uintptr_t)p->heap;
+			size_t index = offset / p->block.size;
+			size_t byte_index = index / 8;
+			size_t bit_index = index % 8;
+
+			LIBC_LOCK(p->lock);
+			if (p->bitmap[byte_index] & (1 << bit_index)) {
+				p->bitmap[byte_index] &= ~(1 << bit_index);
+				p->block.used--;
+				found_in_pages = 1;
+			}
+			LIBC_UNLOCK(p->lock);
+
+			if (found_in_pages && p->block.used == 0) {
+				if (p->prev)
+					p->prev->next = p->next;
+				if (p->next)
+					p->next->prev = p->prev;
+				if (p == __malloc_pvec)
+					__malloc_pvec = p->next;
+
+				munmap(p, (p->flags == PAGE_SMALL) ?
+						  SMALL_PAGE_SIZE :
+					  (p->flags == PAGE_MEDIUM) ?
+						  MEDIUM_PAGE_SIZE :
+						  LARGE_PAGE_SIZE);
+			}
+
+			LIBC_UNLOCK(libc.lock.malloc);
+			return;
+		}
+		p = p->next;
+	}
+
+	void **orig_ptr_slot = (void **)((uintptr_t)ptr - sizeof(void *));
+	void *potential_orig = *orig_ptr_slot;
+
+	p = __malloc_pvec;
+	while (p) {
+		if ((uintptr_t)potential_orig >= (uintptr_t)p->heap &&
+		    (uintptr_t)potential_orig <
+			    (uintptr_t)(p->heap +
+					(p->block.size * p->block.count))) {
+			size_t offset =
+				(uintptr_t)potential_orig - (uintptr_t)p->heap;
+			size_t index = offset / p->block.size;
+			size_t byte_index = index / 8;
+			size_t bit_index = index % 8;
+
+			LIBC_LOCK(p->lock);
+			if (p->bitmap[byte_index] & (1 << bit_index)) {
+				p->bitmap[byte_index] &= ~(1 << bit_index);
+				p->block.used--;
+			}
+			LIBC_UNLOCK(p->lock);
+
+			if (p->block.used == 0) {
+				if (p->prev)
+					p->prev->next = p->next;
+				if (p->next)
+					p->next->prev = p->prev;
+				if (p == __malloc_pvec)
+					__malloc_pvec = p->next;
+
+				munmap(p, (p->flags == PAGE_SMALL) ?
+						  SMALL_PAGE_SIZE :
+					  (p->flags == PAGE_MEDIUM) ?
+						  MEDIUM_PAGE_SIZE :
+						  LARGE_PAGE_SIZE);
+			}
+
+			LIBC_UNLOCK(libc.lock.malloc);
+			return;
+		}
+		p = p->next;
+	}
+
+	LIBC_UNLOCK(libc.lock.malloc);
+}
diff --git a/lib/libc/stdlib/getenv.c b/lib/libc/stdlib/getenv.c
new file mode 100644
index 00000000..deb2b5f7
--- /dev/null
+++ b/lib/libc/stdlib/getenv.c
@@ -0,0 +1,33 @@
+#include <libc.h>
+#include <stddef.h>
+#include <atomic.h>
+
+extern char **environ;
+
+char *getenv(const char *name)
+{
+	LIBC_LOCK(libc.lock.environ);
+
+	for (char **env = environ; *env; env++) {
+		char *eq = NULL;
+		for (char *p = *env; *p; p++) {
+			if (*p == '=') {
+				eq = p;
+				break;
+			}
+			if (name[p - *env] != *p) {
+				break;
+			}
+		}
+		if (eq && name[eq - *env] == '\0') {
+			LIBC_UNLOCK(libc.lock.environ);
+			return eq + 1;
+		}
+	}
+
+	LIBC_UNLOCK(libc.lock.environ);
+
+	return NULL;
+}
+
+weak_reference(getenv, secure_getenv);
diff --git a/lib/libc/stdlib/heapsort.c b/lib/libc/stdlib/heapsort.c
new file mode 100644
index 00000000..101720bb
--- /dev/null
+++ b/lib/libc/stdlib/heapsort.c
@@ -0,0 +1,191 @@
+/*-
+ * Copyright (c) 1991, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Ronnie Kon at Mindcraft Inc., Kevin Lew and Elmer Yglesias.
+ *
+ * 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.
+ * 4. 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.
+ */
+
+#include <stddef.h>
+#include <stdlib.h>
+
+/*
+ * Swap two areas of size number of bytes.  Although qsort(3) permits random
+ * blocks of memory to be sorted, sorting pointers is almost certainly the
+ * common case (and, were it not, could easily be made so).  Regardless, it
+ * isn't worth optimizing; the SWAP's get sped up by the cache, and pointer
+ * arithmetic gets lost in the time required for comparison function calls.
+ */
+#define SWAP(a, b, count, size, tmp) \
+	{                            \
+		count = size;        \
+		do {                 \
+			tmp = *a;    \
+			*a++ = *b;   \
+			*b++ = tmp;  \
+		} while (--count);   \
+	}
+
+/* Copy one block of size size to another. */
+#define COPY(a, b, count, size, tmp1, tmp2) \
+	{                                   \
+		count = size;               \
+		tmp1 = a;                   \
+		tmp2 = b;                   \
+		do {                        \
+			*tmp1++ = *tmp2++;  \
+		} while (--count);          \
+	}
+
+/*
+ * Build the list into a heap, where a heap is defined such that for
+ * the records K1 ... KN, Kj/2 >= Kj for 1 <= j/2 <= j <= N.
+ *
+ * There two cases.  If j == nmemb, select largest of Ki and Kj.  If
+ * j < nmemb, select largest of Ki, Kj and Kj+1.
+ */
+#define CREATE(initval, nmemb, par_i, child_i, par, child, size, count, tmp) \
+	{                                                                    \
+		for (par_i = initval; (child_i = par_i * 2) <= nmemb;        \
+		     par_i = child_i) {                                      \
+			child = base + child_i * size;                       \
+			if (child_i < nmemb &&                               \
+			    compar(child, child + size) < 0) {               \
+				child += size;                               \
+				++child_i;                                   \
+			}                                                    \
+			par = base + par_i * size;                           \
+			if (compar(child, par) <= 0)                         \
+				break;                                       \
+			SWAP(par, child, count, size, tmp);                  \
+		}                                                            \
+	}
+
+/*
+ * Select the top of the heap and 'heapify'.  Since by far the most expensive
+ * action is the call to the compar function, a considerable optimization
+ * in the average case can be achieved due to the fact that k, the displaced
+ * elememt, is ususally quite small, so it would be preferable to first
+ * heapify, always maintaining the invariant that the larger child is copied
+ * over its parent's record.
+ *
+ * Then, starting from the *bottom* of the heap, finding k's correct place,
+ * again maintianing the invariant.  As a result of the invariant no element
+ * is 'lost' when k is assigned its correct place in the heap.
+ *
+ * The time savings from this optimization are on the order of 15-20% for the
+ * average case. See Knuth, Vol. 3, page 158, problem 18.
+ *
+ * XXX Don't break the #define SELECT line, below.  Reiser cpp gets upset.
+ */
+#define SELECT(par_i, child_i, nmemb, par, child, size, k, count, tmp1, tmp2) \
+	{                                                                     \
+		for (par_i = 1; (child_i = par_i * 2) <= nmemb;               \
+		     par_i = child_i) {                                       \
+			child = base + child_i * size;                        \
+			if (child_i < nmemb &&                                \
+			    compar(child, child + size) < 0) {                \
+				child += size;                                \
+				++child_i;                                    \
+			}                                                     \
+			par = base + par_i * size;                            \
+			COPY(par, child, count, size, tmp1, tmp2);            \
+		}                                                             \
+		for (;;) {                                                    \
+			child_i = par_i;                                      \
+			par_i = child_i / 2;                                  \
+			child = base + child_i * size;                        \
+			par = base + par_i * size;                            \
+			if (child_i == 1 || compar(k, par) < 0) {             \
+				COPY(child, k, count, size, tmp1, tmp2);      \
+				break;                                        \
+			}                                                     \
+			COPY(child, par, count, size, tmp1, tmp2);            \
+		}                                                             \
+	}
+
+/*
+ * Heapsort -- Knuth, Vol. 3, page 145.  Runs in O (N lg N), both average
+ * and worst.  While heapsort is faster than the worst case of quicksort,
+ * the BSD quicksort does median selection so that the chance of finding
+ * a data set that will trigger the worst case is nonexistent.  Heapsort's
+ * only advantage over quicksort is that it requires little additional memory.
+ */
+int heapsort(void *vbase, size_t nmemb, size_t size,
+	     int (*compar)(const void *, const void *))
+{
+	size_t cnt;
+	size_t i;
+	size_t j;
+	size_t l;
+	char tmp;
+	char *tmp1;
+	char *tmp2;
+	char *base;
+	char *k;
+	char *p;
+	char *t;
+
+	if (nmemb <= 1) {
+		return (0);
+	}
+
+	if (!size) {
+		// errno = EINVAL;
+		return (-1);
+	}
+
+	if ((k = malloc(size)) == NULL) {
+		return (-1);
+	}
+
+	/*
+	 * Items are numbered from 1 to nmemb, so offset from size bytes
+	 * below the starting address.
+	 */
+	base = (char *)vbase - size;
+
+	for (l = nmemb / 2 + 1; --l;) {
+		CREATE(l, nmemb, i, j, t, p, size, cnt, tmp);
+	}
+
+	/*
+	 * For each element of the heap, save the largest element into its
+	 * final slot, save the displaced element (k), then recreate the
+	 * heap.
+	 */
+	while (nmemb > 1) {
+		COPY(k, base + nmemb * size, cnt, size, tmp1, tmp2);
+		COPY(base + nmemb * size, base + size, cnt, size, tmp1, tmp2);
+		--nmemb;
+		SELECT(i, j, nmemb, t, p, size, k, cnt, tmp1, tmp2);
+	}
+
+	free(k);
+
+	return (0);
+}
diff --git a/lib/libc/stdlib/heapsort_r.c b/lib/libc/stdlib/heapsort_r.c
new file mode 100644
index 00000000..645f63b0
--- /dev/null
+++ b/lib/libc/stdlib/heapsort_r.c
@@ -0,0 +1,191 @@
+/*-
+ * Copyright (c) 1991, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Ronnie Kon at Mindcraft Inc., Kevin Lew and Elmer Yglesias.
+ *
+ * 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.
+ * 4. 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.
+ */
+
+#include <stddef.h>
+#include <stdlib.h>
+
+/*
+ * Swap two areas of size number of bytes.  Although qsort(3) permits random
+ * blocks of memory to be sorted, sorting pointers is almost certainly the
+ * common case (and, were it not, could easily be made so).  Regardless, it
+ * isn't worth optimizing; the SWAP's get sped up by the cache, and pointer
+ * arithmetic gets lost in the time required for comparison function calls.
+ */
+#define SWAP(a, b, count, size, tmp) \
+	{                            \
+		count = size;        \
+		do {                 \
+			tmp = *a;    \
+			*a++ = *b;   \
+			*b++ = tmp;  \
+		} while (--count);   \
+	}
+
+/* Copy one block of size size to another. */
+#define COPY(a, b, count, size, tmp1, tmp2) \
+	{                                   \
+		count = size;               \
+		tmp1 = a;                   \
+		tmp2 = b;                   \
+		do {                        \
+			*tmp1++ = *tmp2++;  \
+		} while (--count);          \
+	}
+
+/*
+ * Build the list into a heap, where a heap is defined such that for
+ * the records K1 ... KN, Kj/2 >= Kj for 1 <= j/2 <= j <= N.
+ *
+ * There two cases.  If j == nmemb, select largest of Ki and Kj.  If
+ * j < nmemb, select largest of Ki, Kj and Kj+1.
+ */
+#define CREATE(initval, nmemb, par_i, child_i, par, child, size, count, tmp) \
+	{                                                                    \
+		for (par_i = initval; (child_i = par_i * 2) <= nmemb;        \
+		     par_i = child_i) {                                      \
+			child = base + child_i * size;                       \
+			if (child_i < nmemb &&                               \
+			    compar(thunk, child, child + size) < 0) {        \
+				child += size;                               \
+				++child_i;                                   \
+			}                                                    \
+			par = base + par_i * size;                           \
+			if (compar(thunk, child, par) <= 0)                  \
+				break;                                       \
+			SWAP(par, child, count, size, tmp);                  \
+		}                                                            \
+	}
+
+/*
+ * Select the top of the heap and 'heapify'.  Since by far the most expensive
+ * action is the call to the compar function, a considerable optimization
+ * in the average case can be achieved due to the fact that k, the displaced
+ * elememt, is ususally quite small, so it would be preferable to first
+ * heapify, always maintaining the invariant that the larger child is copied
+ * over its parent's record.
+ *
+ * Then, starting from the *bottom* of the heap, finding k's correct place,
+ * again maintianing the invariant.  As a result of the invariant no element
+ * is 'lost' when k is assigned its correct place in the heap.
+ *
+ * The time savings from this optimization are on the order of 15-20% for the
+ * average case. See Knuth, Vol. 3, page 158, problem 18.
+ *
+ * XXX Don't break the #define SELECT line, below.  Reiser cpp gets upset.
+ */
+#define SELECT(par_i, child_i, nmemb, par, child, size, k, count, tmp1, tmp2) \
+	{                                                                     \
+		for (par_i = 1; (child_i = par_i * 2) <= nmemb;               \
+		     par_i = child_i) {                                       \
+			child = base + child_i * size;                        \
+			if (child_i < nmemb &&                                \
+			    compar(thunk, child, child + size) < 0) {         \
+				child += size;                                \
+				++child_i;                                    \
+			}                                                     \
+			par = base + par_i * size;                            \
+			COPY(par, child, count, size, tmp1, tmp2);            \
+		}                                                             \
+		for (;;) {                                                    \
+			child_i = par_i;                                      \
+			par_i = child_i / 2;                                  \
+			child = base + child_i * size;                        \
+			par = base + par_i * size;                            \
+			if (child_i == 1 || compar(thunk, k, par) < 0) {      \
+				COPY(child, k, count, size, tmp1, tmp2);      \
+				break;                                        \
+			}                                                     \
+			COPY(child, par, count, size, tmp1, tmp2);            \
+		}                                                             \
+	}
+
+/*
+ * Heapsort -- Knuth, Vol. 3, page 145.  Runs in O (N lg N), both average
+ * and worst.  While heapsort is faster than the worst case of quicksort,
+ * the BSD quicksort does median selection so that the chance of finding
+ * a data set that will trigger the worst case is nonexistent.  Heapsort's
+ * only advantage over quicksort is that it requires little additional memory.
+ */
+int heapsort_r(void *vbase, size_t nmemb, size_t size, void *thunk,
+	       int (*compar)(void *, const void *, const void *))
+{
+	size_t cnt;
+	size_t i;
+	size_t j;
+	size_t l;
+	char tmp;
+	char *tmp1;
+	char *tmp2;
+	char *base;
+	char *k;
+	char *p;
+	char *t;
+
+	if (nmemb <= 1) {
+		return (0);
+	}
+
+	if (!size) {
+		// errno = EINVAL;
+		return (-1);
+	}
+
+	if ((k = malloc(size)) == NULL) {
+		return (-1);
+	}
+
+	/*
+	 * Items are numbered from 1 to nmemb, so offset from size bytes
+	 * below the starting address.
+	 */
+	base = (char *)vbase - size;
+
+	for (l = nmemb / 2 + 1; --l;) {
+		CREATE(l, nmemb, i, j, t, p, size, cnt, tmp);
+	}
+
+	/*
+	 * For each element of the heap, save the largest element into its
+	 * final slot, save the displaced element (k), then recreate the
+	 * heap.
+	 */
+	while (nmemb > 1) {
+		COPY(k, base + nmemb * size, cnt, size, tmp1, tmp2);
+		COPY(base + nmemb * size, base + size, cnt, size, tmp1, tmp2);
+		--nmemb;
+		SELECT(i, j, nmemb, t, p, size, k, cnt, tmp1, tmp2);
+	}
+
+	free(k);
+
+	return (0);
+}
diff --git a/lib/libc/stdlib/labs.c b/lib/libc/stdlib/labs.c
new file mode 100644
index 00000000..1413af3a
--- /dev/null
+++ b/lib/libc/stdlib/labs.c
@@ -0,0 +1,6 @@
+#include <stdlib.h>
+
+long labs(long i)
+{
+	return i < 0 ? -i : i;
+}
diff --git a/lib/libc/stdlib/ldiv.c b/lib/libc/stdlib/ldiv.c
new file mode 100644
index 00000000..9fc62b8d
--- /dev/null
+++ b/lib/libc/stdlib/ldiv.c
@@ -0,0 +1,9 @@
+#include <stdlib.h>
+
+ldiv_t ldiv(long numer, long denom)
+{
+	ldiv_t result;
+	result.quot = numer / denom;
+	result.rem = numer % denom;
+	return result;
+}
diff --git a/lib/libc/stdlib/llabs.c b/lib/libc/stdlib/llabs.c
new file mode 100644
index 00000000..1fadcb98
--- /dev/null
+++ b/lib/libc/stdlib/llabs.c
@@ -0,0 +1,6 @@
+#include <stdlib.h>
+
+long long llabs(long long i)
+{
+	return (i < 0 ? -i : i);
+}
diff --git a/lib/libc/stdlib/lldiv.c b/lib/libc/stdlib/lldiv.c
new file mode 100644
index 00000000..6df419b3
--- /dev/null
+++ b/lib/libc/stdlib/lldiv.c
@@ -0,0 +1,9 @@
+#include <stdlib.h>
+
+lldiv_t lldiv(long long numer, long long denom)
+{
+	lldiv_t result;
+	result.quot = numer / denom;
+	result.rem = numer % denom;
+	return result;
+}
diff --git a/lib/libc/stdlib/malloc.c b/lib/libc/stdlib/malloc.c
new file mode 100644
index 00000000..3d29e6a8
--- /dev/null
+++ b/lib/libc/stdlib/malloc.c
@@ -0,0 +1,181 @@
+#include <atomic.h>
+#include <features.h>
+#include <libc.h>
+#include <malloc.h>
+#include <linux/errno.h>
+#include <stdatomic.h>
+#include <stdint.h>
+#include <string.h>
+#include <sys/mman.h>
+#include <unistd.h>
+
+struct page *__malloc_pvec = NULL;
+
+static __inline uint32_t get_size_class(size_t size)
+{
+	uintptr_t minblock_count = (size + (16 - 1)) / 16;
+
+	if (size <= (16 * 64)) {
+		return (uint32_t)(minblock_count ? minblock_count : 1);
+	}
+
+	const uint32_t most_significant_bit =
+		(uint32_t)(63 - (int)__builtin_clzll(minblock_count));
+
+	const uint32_t subclass_bits =
+		(minblock_count >> (most_significant_bit - 2)) & 0x03;
+
+	return (uint32_t)((most_significant_bit << 2) + subclass_bits) + 41;
+}
+
+weak void *malloc(size_t size);
+
+void *malloc(size_t size)
+{
+	if (size == 0)
+		return NULL;
+
+	LIBC_LOCK(libc.lock.malloc);
+
+	uint32_t class_index = get_size_class(size);
+	if (class_index >=
+	    sizeof(global_size_class) / sizeof(global_size_class[0])) {
+		LIBC_UNLOCK(libc.lock.malloc);
+		return NULL;
+	}
+	const struct class *cls = &global_size_class[class_index];
+
+	struct page *p = __malloc_pvec;
+	while (p) {
+		if (p->flags == PAGE_SMALL && cls->size <= 16 * 64) {
+			LIBC_LOCK(p->lock);
+			if (p->block.used < p->block.count &&
+			    p->block.size == cls->size) {
+				for (uint32_t i = 0; i < p->block.count; i++) {
+					int byte_index = i / 8;
+					int bit_index = i % 8;
+					if (!(p->bitmap[byte_index] &
+					      (1 << bit_index))) {
+						p->bitmap[byte_index] |=
+							(1 << bit_index);
+						p->block.used++;
+						LIBC_UNLOCK(p->lock);
+						LIBC_UNLOCK(libc.lock.malloc);
+						if (p->heap == NULL)
+							return NULL;
+						return p->heap +
+						       (i * p->block.size);
+					}
+				}
+			}
+			LIBC_UNLOCK(p->lock);
+		} else if (p->flags == PAGE_MEDIUM && cls->size > 16 * 64 &&
+			   cls->size <= 16 * 8192) {
+			LIBC_LOCK(p->lock);
+			if (p->block.used < p->block.count &&
+			    p->block.size == cls->size) {
+				for (uint32_t i = 0; i < p->block.count; i++) {
+					int byte_index = i / 8;
+					int bit_index = i % 8;
+					if (!(p->bitmap[byte_index] &
+					      (1 << bit_index))) {
+						// Mark block as used
+						p->bitmap[byte_index] |=
+							(1 << bit_index);
+						p->block.used++;
+						LIBC_UNLOCK(p->lock);
+						LIBC_UNLOCK(libc.lock.malloc);
+						if (p->heap == NULL)
+							return NULL;
+						return p->heap +
+						       (i * p->block.size);
+					}
+				}
+			}
+			LIBC_UNLOCK(p->lock);
+		} else if (p->flags == PAGE_LARGE && cls->size > 16 * 8192) {
+			LIBC_LOCK(p->lock);
+			if (p->block.used < p->block.count &&
+			    p->block.size == cls->size) {
+				// Find free block
+				for (uint32_t i = 0; i < p->block.count; i++) {
+					int byte_index = i / 8;
+					int bit_index = i % 8;
+					if (!(p->bitmap[byte_index] &
+					      (1 << bit_index))) {
+						p->bitmap[byte_index] |=
+							(1 << bit_index);
+						p->block.used++;
+						LIBC_UNLOCK(p->lock);
+						LIBC_UNLOCK(libc.lock.malloc);
+
+						if (p->heap == NULL)
+							return NULL;
+						return p->heap +
+						       (i * p->block.size);
+					}
+				}
+			}
+			LIBC_UNLOCK(p->lock);
+		}
+		p = p->next;
+	}
+
+	size_t page_size;
+	enum { PAGE_TYPE_SMALL, PAGE_TYPE_MEDIUM, PAGE_TYPE_LARGE } page_type;
+
+	if (cls->size <= 16 * 64) {
+		page_size = SMALL_PAGE_SIZE;
+		page_type = PAGE_TYPE_SMALL;
+	} else if (cls->size <= 16 * 8192) {
+		page_size = MEDIUM_PAGE_SIZE;
+		page_type = PAGE_TYPE_MEDIUM;
+	} else {
+		page_size = LARGE_PAGE_SIZE;
+		page_type = PAGE_TYPE_LARGE;
+	}
+
+	size_t bitmap_size = (cls->count + 7) / 8;
+	void *mem = mmap(NULL, page_size, PROT_READ | PROT_WRITE,
+			 MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+
+	if (mem == MAP_FAILED) {
+		LIBC_UNLOCK(libc.lock.malloc);
+		return NULL;
+	}
+
+	struct page *new_page = (struct page *)mem;
+	new_page->flags = (page_type == PAGE_TYPE_SMALL)  ? PAGE_SMALL :
+			  (page_type == PAGE_TYPE_MEDIUM) ? PAGE_MEDIUM :
+							    PAGE_LARGE;
+
+	new_page->block.size = cls->size;
+	new_page->block.used = 0;
+	new_page->block.count = cls->count;
+	new_page->bitmap = (uint8_t *)mem + sizeof(struct page);
+	memset(new_page->bitmap, 0, bitmap_size);
+	new_page->heap = (uint8_t *)mem + sizeof(struct page) + bitmap_size;
+
+	if (new_page->heap == NULL || new_page->bitmap == NULL) {
+		munmap(mem, page_size);
+		LIBC_UNLOCK(libc.lock.malloc);
+		return NULL;
+	}
+	atomic_flag_clear(&new_page->lock);
+	new_page->next = __malloc_pvec;
+	new_page->prev = NULL;
+
+	if (__malloc_pvec) {
+		__malloc_pvec->prev = new_page;
+	}
+
+	__malloc_pvec = new_page;
+
+	// Mark the first block as used and return it
+	new_page->bitmap[0] |= 1;
+	new_page->block.used = 1;
+
+	LIBC_UNLOCK(libc.lock.malloc);
+
+	return new_page->heap;
+}
diff --git a/lib/libc/stdlib/posix_memalign.c b/lib/libc/stdlib/posix_memalign.c
new file mode 100644
index 00000000..a7cbd2a2
--- /dev/null
+++ b/lib/libc/stdlib/posix_memalign.c
@@ -0,0 +1,31 @@
+#include <errno.h>
+#include <stdlib.h>
+
+int posix_memalign(void **memptr, size_t alignment, size_t size)
+{
+	if (memptr == NULL) {
+		return EINVAL;
+	}
+
+	*memptr = NULL;
+
+	if (alignment < sizeof(void *) || alignment % sizeof(void *) != 0 ||
+	    (alignment & (alignment - 1)) != 0) {
+		return EINVAL;
+	}
+
+	if (size == 0) {
+		*memptr = NULL;
+		return 0;
+	}
+
+	size_t aligned_size = (size + alignment - 1) & ~(alignment - 1);
+
+	void *ptr = aligned_alloc(alignment, aligned_size);
+	if (ptr == NULL) {
+		return ENOMEM;
+	}
+
+	*memptr = ptr;
+	return 0;
+}
diff --git a/lib/libc/stdlib/putenv.c b/lib/libc/stdlib/putenv.c
new file mode 100644
index 00000000..b070cc4d
--- /dev/null
+++ b/lib/libc/stdlib/putenv.c
@@ -0,0 +1,17 @@
+#include <stdlib.h>
+#include <string.h>
+
+int putenv(char *string)
+{
+	const char *const name_end = strchr(string, '=');
+
+	if (name_end) {
+		char name[name_end - string + 1];
+		memcpy(name, string, name_end - string);
+		name[name_end - string] = '\0';
+		return setenv(name, name_end + 1, 1);
+	}
+
+	unsetenv(string);
+	return 0;
+}
diff --git a/lib/libc/stdlib/qsort.c b/lib/libc/stdlib/qsort.c
new file mode 100644
index 00000000..896c79a1
--- /dev/null
+++ b/lib/libc/stdlib/qsort.c
@@ -0,0 +1,12 @@
+#include <stdlib.h>
+
+static int wrapper(const void *a, const void *b, void *compar)
+{
+	return ((int (*)(const void *, const void *))compar)(a, b);
+}
+
+void qsort(void *base, size_t nel, size_t width,
+	   int (*compar)(const void *, const void *))
+{
+	qsort_r(base, nel, width, wrapper, compar);
+}
diff --git a/lib/libc/stdlib/qsort_r.c b/lib/libc/stdlib/qsort_r.c
new file mode 100644
index 00000000..2fc39a6f
--- /dev/null
+++ b/lib/libc/stdlib/qsort_r.c
@@ -0,0 +1,243 @@
+/* Copyright (C) 2011 by Lynn Ochs
+ *
+ * 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.
+ */
+
+/* Minor changes by Rich Felker for integration in musl, 2011-04-27. */
+
+/* Smoothsort, an adaptive variant of Heapsort.  Memory usage: O(1).
+   Run time: Worst case O(n log n), close to O(n) in the mostly-sorted case. */
+
+#define _BSD_SOURCE
+#include <stdlib.h>
+#include <string.h>
+
+#define ntz(x) __builtin_ctzl((x))
+
+typedef int (*cmpfun)(const void *, const void *, void *);
+
+static inline int pntz(size_t p[2])
+{
+	int r = ntz(p[0] - 1);
+	if (r != 0 ||
+	    (r = 8 * sizeof(size_t) + ntz(p[1])) != 8 * sizeof(size_t)) {
+		return r;
+	}
+	return 0;
+}
+
+static void cycle(size_t width, unsigned char *ar[], int n)
+{
+	unsigned char tmp[256];
+	size_t l;
+	int i;
+
+	if (n < 2) {
+		return;
+	}
+
+	ar[n] = tmp;
+	while (width) {
+		l = sizeof(tmp) < width ? sizeof(tmp) : width;
+		memcpy(ar[n], ar[0], l);
+		for (i = 0; i < n; i++) {
+			memcpy(ar[i], ar[i + 1], l);
+			ar[i] += l;
+		}
+		width -= l;
+	}
+	ar[n] = NULL;
+}
+
+/* shl() and shr() need n > 0 */
+static inline void shl(size_t p[2], int n)
+{
+	if (n >= 8 * sizeof(size_t)) {
+		n -= 8 * sizeof(size_t);
+		p[1] = p[0];
+		p[0] = 0;
+	}
+	p[1] <<= n;
+	p[1] |= (n < sizeof(size_t) * 8) ? p[0] >> (sizeof(size_t) * 8 - n) : 0;
+	p[0] <<= n;
+}
+
+static inline void shr(size_t p[2], int n)
+{
+	size_t bits = sizeof(size_t) * 8;
+
+	if (n >= 8 * sizeof(size_t)) {
+		n -= 8 * sizeof(size_t);
+		p[0] = p[1];
+		p[1] = 0;
+	}
+
+	p[0] >>= n;
+	p[0] |= (n > 0 && n < bits) ? p[1] << (bits - n) : 0;
+	p[1] >>= n;
+}
+
+static void sift(unsigned char *head, size_t width, cmpfun cmp, void *arg,
+		 int pshift, size_t lp[])
+{
+	unsigned char *rt, *lf;
+	unsigned char *ar[14 * sizeof(size_t) + 1];
+	int i = 1;
+
+	ar[0] = head;
+	while (pshift > 1) {
+		rt = head - width;
+		lf = head - width - lp[pshift - 2];
+
+		if (cmp(ar[0], lf, arg) >= 0 && cmp(ar[0], rt, arg) >= 0) {
+			break;
+		}
+		if (cmp(lf, rt, arg) >= 0) {
+			ar[i++] = lf;
+			head = lf;
+			pshift -= 1;
+		} else {
+			ar[i++] = rt;
+			head = rt;
+			pshift -= 2;
+		}
+	}
+	cycle(width, ar, i);
+}
+
+static void trinkle(unsigned char *head, size_t width, cmpfun cmp, void *arg,
+		    size_t pp[2], int pshift, int trusty, size_t lp[],
+		    int max_lp_index)
+{
+	unsigned char *stepson, *rt, *lf;
+	size_t p[2];
+	unsigned char *ar[14 * sizeof(size_t) + 1];
+	int i = 1;
+	int trail;
+
+	p[0] = pp[0];
+	p[1] = pp[1];
+
+	ar[0] = head;
+	while (p[0] != 1 || p[1] != 0) {
+		if (pshift < 0 || pshift > max_lp_index || pshift >= 64)
+			break;
+
+		stepson = head - lp[pshift];
+		if (cmp(stepson, ar[0], arg) <= 0) {
+			break;
+		}
+		if (!trusty && pshift > 1 && pshift - 2 >= 0 &&
+		    pshift - 2 <= max_lp_index) {
+			rt = head - width;
+			lf = head - width - lp[pshift - 2];
+			if (cmp(rt, stepson, arg) >= 0 ||
+			    cmp(lf, stepson, arg) >= 0) {
+				break;
+			}
+		}
+
+		ar[i++] = stepson;
+		head = stepson;
+		trail = pntz(p);
+		shr(p, trail);
+		pshift += trail;
+		trusty = 0;
+	}
+	if (!trusty) {
+		cycle(width, ar, i);
+		sift(head, width, cmp, arg, pshift, lp);
+	}
+}
+
+void qsort_r(void *base, size_t nel, size_t width, cmpfun cmp, void *arg)
+{
+	size_t lp[64];
+	size_t i, size = width * nel;
+	unsigned char *head, *high;
+	size_t p[2] = { 1, 0 };
+	int pshift = 1;
+	int trail;
+	int max_lp_index;
+
+	if (!size)
+		return;
+
+	head = base;
+	high = head + size - width;
+
+	/* Precompute Leonardo numbers, scaled by element width */
+	for (lp[0] = lp[1] = width, i = 2;
+	     (lp[i] = lp[i - 2] + lp[i - 1] + width) < size && i < 63; i++)
+		;
+	max_lp_index = i - 1;
+
+	while (head < high) {
+		if ((p[0] & 3) == 3) {
+			sift(head, width, cmp, arg, pshift, lp);
+			shr(p, 2);
+			pshift += 2;
+		} else {
+			if (pshift - 1 >= 0 && pshift - 1 <= max_lp_index &&
+			    lp[pshift - 1] >= high - head) {
+				trinkle(head, width, cmp, arg, p, pshift, 0, lp,
+					max_lp_index);
+			} else {
+				sift(head, width, cmp, arg, pshift, lp);
+			}
+
+			if (pshift == 1) {
+				shl(p, 1);
+				pshift = 0;
+			} else {
+				shl(p, pshift - 1);
+				pshift = 1;
+			}
+		}
+
+		p[0] |= 1;
+		head += width;
+	}
+
+	trinkle(head, width, cmp, arg, p, pshift, 0, lp, max_lp_index);
+
+	while (pshift != 1 || p[0] != 1 || p[1] != 0) {
+		if (pshift <= 1) {
+			trail = pntz(p);
+			shr(p, trail);
+			pshift += trail;
+		} else {
+			shl(p, 2);
+			pshift -= 2;
+			p[0] ^= 7;
+			shr(p, 1);
+			if (pshift >= 0 && pshift <= max_lp_index &&
+			    pshift < 64) {
+				trinkle(head - lp[pshift] - width, width, cmp,
+					arg, p, pshift + 1, 1, lp,
+					max_lp_index);
+			}
+			shl(p, 1);
+			p[0] |= 1;
+			trinkle(head - width, width, cmp, arg, p, pshift, 1, lp,
+				max_lp_index);
+		}
+		head -= width;
+	}
+}
diff --git a/lib/libc/stdlib/quick_exit.c b/lib/libc/stdlib/quick_exit.c
new file mode 100644
index 00000000..15587d17
--- /dev/null
+++ b/lib/libc/stdlib/quick_exit.c
@@ -0,0 +1,6 @@
+#include <stdlib.h>
+
+_Noreturn void quick_exit(int status)
+{
+	_Exit(status);
+}
diff --git a/lib/libc/stdlib/rand.c b/lib/libc/stdlib/rand.c
new file mode 100644
index 00000000..878aa0e2
--- /dev/null
+++ b/lib/libc/stdlib/rand.c
@@ -0,0 +1,182 @@
+/*  Written in 2018 by David Blackman and Sebastiano Vigna (vigna@acm.org)
+
+To the extent possible under law, the author has dedicated all copyright
+and related and neighboring rights to this software to the public domain
+worldwide.
+
+Permission to use, copy, modify, and/or distribute this software for any
+purpose with or without fee is hereby granted.
+
+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 <stdlib.h>
+#include <stdint.h>
+
+#define UINT64_C(c) ((uint64_t)(c##ULL))
+
+typedef struct {
+	uint64_t s[4];
+} xoshiro256_state;
+
+typedef struct {
+	uint64_t s[4];
+} erand48_state;
+
+static xoshiro256_state __xoshiro256_state;
+static erand48_state __erand48_state;
+
+/* This is xoshiro256** 1.0, one of our all-purpose, rock-solid
+   generators. It has excellent (sub-ns) speed, a state (256 bits) that is
+   large enough for any parallel application, and it passes all tests we
+   are aware of.
+
+   For generating just floating-point numbers, xoshiro256+ is even faster.
+
+   The state must be seeded so that it is not everywhere zero. If you have
+   a 64-bit seed, we suggest to seed a splitmix64 generator and use its
+   output to fill s. */
+
+static inline uint64_t rotl(const uint64_t x, int k)
+{
+	return (x << k) | (x >> (64 - k));
+}
+
+uint64_t xoshiro256_next(xoshiro256_state *st)
+{
+	const uint64_t result = rotl(st->s[1] * 5, 7) * 9;
+
+	const uint64_t t = st->s[1] << 17;
+
+	st->s[2] ^= st->s[0];
+	st->s[3] ^= st->s[1];
+	st->s[1] ^= st->s[2];
+	st->s[0] ^= st->s[3];
+
+	st->s[2] ^= t;
+
+	st->s[3] = rotl(st->s[3], 45);
+
+	return result;
+}
+
+/*  Written in 2015 by Sebastiano Vigna (vigna@acm.org)
+
+To the extent possible under law, the author has dedicated all copyright
+and related and neighboring rights to this software to the public domain
+worldwide. This software is distributed without any warranty.
+
+See <http://creativecommons.org/publicdomain/zero/1.0/>. */
+
+/* This is a fixed-increment version of Java 8's SplittableRandom generator
+   See http://dx.doi.org/10.1145/2714064.2660195 and
+   http://docs.oracle.com/javase/8/docs/api/java/util/SplittableRandom.html
+
+   It is a very fast generator passing BigCrush, and it can be useful if
+   for some reason you absolutely want 64 bits of state; otherwise, we
+   rather suggest to use a xoroshiro128+ (for moderately parallel
+   computations) or xorshift1024* (for massively parallel computations)
+   generator. */
+
+uint64_t splitmix64(uint64_t *x)
+{
+	uint64_t z = (*x += UINT64_C(0x9E3779B97F4A7C15));
+	z = (z ^ (z >> 30)) * UINT64_C(0xBF58476D1CE4E5B9);
+	z = (z ^ (z >> 27)) * UINT64_C(0x94D049BB133111EB);
+	return z ^ (z >> 31);
+}
+
+void srand(unsigned int seed)
+{
+	uint64_t z = (uint64_t)seed;
+	__xoshiro256_state.s[0] = splitmix64(&z);
+	__xoshiro256_state.s[1] = splitmix64(&z);
+	__xoshiro256_state.s[2] = splitmix64(&z);
+	__xoshiro256_state.s[3] = splitmix64(&z);
+}
+
+int rand(void)
+{
+	return (int)(xoshiro256_next(&__xoshiro256_state) & (uint64_t)RAND_MAX);
+}
+
+void srandom(unsigned seed)
+{
+	srand(seed);
+}
+
+long random(void)
+{
+	return (long)rand();
+}
+
+void srand48(long seedval)
+{
+	uint64_t z = (uint64_t)seedval;
+	__erand48_state.s[0] = splitmix64(&z);
+	__erand48_state.s[1] = splitmix64(&z);
+	__erand48_state.s[2] = splitmix64(&z);
+	__erand48_state.s[3] = splitmix64(&z);
+}
+
+double drand48(void)
+{
+	uint64_t v = xoshiro256_next((xoshiro256_state *)&__erand48_state);
+	return (double)(v >> 11) * (1.0 / 9007199254740992.0); // 53-bit
+							       // mantissa
+}
+
+long lrand48(void)
+{
+	uint64_t v = xoshiro256_next((xoshiro256_state *)&__erand48_state);
+	return (long)(v & 0x7FFFFFFF); // 31-bit
+}
+
+long mrand48(void)
+{
+	uint64_t v = xoshiro256_next((xoshiro256_state *)&__erand48_state);
+	return (long)(v & 0xFFFFFFFF); // 32-bit signed
+}
+
+double erand48(unsigned short xsubi[3])
+{
+	xoshiro256_state st = { 0 };
+	for (int i = 0; i < 3; i++)
+		st.s[i] = xsubi[i];
+	st.s[3] = 0xdeadbeef;
+	uint64_t v = xoshiro256_next(&st);
+	return (double)(v >> 11) * (1.0 / 9007199254740992.0);
+}
+
+long nrand48(unsigned short xsubi[3])
+{
+	xoshiro256_state st = { 0 };
+	for (int i = 0; i < 3; i++)
+		st.s[i] = xsubi[i];
+	st.s[3] = 0xdeadbeef;
+	uint64_t v = xoshiro256_next(&st);
+	return (long)(v & 0x7FFFFFFF);
+}
+
+long jrand48(unsigned short xsubi[3])
+{
+	xoshiro256_state st = { 0 };
+	for (int i = 0; i < 3; i++)
+		st.s[i] = xsubi[i];
+	st.s[3] = 0xdeadbeef;
+	uint64_t v = xoshiro256_next(&st);
+	return (long)(v & 0xFFFFFFFF);
+}
+
+unsigned short *seed48(unsigned short seed16v[3])
+{
+	for (int i = 0; i < 3; i++)
+		__erand48_state.s[i] = seed16v[i];
+	__erand48_state.s[3] = 0xdeadbeef;
+	return seed16v;
+}
diff --git a/lib/libc/stdlib/realloc.c b/lib/libc/stdlib/realloc.c
new file mode 100644
index 00000000..d90af70d
--- /dev/null
+++ b/lib/libc/stdlib/realloc.c
@@ -0,0 +1,47 @@
+#include <errno.h>
+#include <string.h>
+#include <atomic.h>
+#include <libc.h>
+#include <malloc.h>
+#include <linux/errno.h>
+#include <stdlib.h>
+
+void *realloc(void *ptr, size_t size)
+{
+	if (ptr == NULL) {
+		return malloc(size);
+	}
+	if (size == 0) {
+		free(ptr);
+		return NULL;
+	}
+
+	LIBC_LOCK(libc.lock.malloc);
+
+	struct page *p = __malloc_pvec;
+	while (p) {
+		if ((uintptr_t)ptr >= (uintptr_t)p->heap &&
+		    (uintptr_t)ptr < (uintptr_t)(p->heap + (p->block.size *
+							    p->block.count))) {
+			size_t old_size = p->block.size;
+			LIBC_UNLOCK(libc.lock.malloc);
+
+			if (size <= old_size) {
+				return ptr;
+			} else {
+				void *new_ptr = malloc(size);
+				if (new_ptr) {
+					memcpy(new_ptr, ptr, old_size);
+					free(ptr);
+				}
+				return new_ptr;
+			}
+		}
+		p = p->next;
+	}
+
+	LIBC_UNLOCK(libc.lock.malloc);
+
+	errno = EINVAL;
+	return NULL;
+}
diff --git a/lib/libc/stdlib/reallocarray.c b/lib/libc/stdlib/reallocarray.c
new file mode 100644
index 00000000..4dd1a6c8
--- /dev/null
+++ b/lib/libc/stdlib/reallocarray.c
@@ -0,0 +1,14 @@
+#include <stdlib.h>
+#include <errno.h>
+#include <linux/errno.h>
+#include <malloc.h>
+
+void *reallocarray(void *ptr, size_t nmemb, size_t size)
+{
+	size_t total = nmemb * size;
+	if (nmemb != 0 && total / nmemb != size) {
+		errno = ENOMEM;
+		return NULL;
+	}
+	return realloc(ptr, total);
+}
diff --git a/lib/libc/stdlib/setenv.c b/lib/libc/stdlib/setenv.c
new file mode 100644
index 00000000..1464fc1b
--- /dev/null
+++ b/lib/libc/stdlib/setenv.c
@@ -0,0 +1,58 @@
+#include <libc.h>
+#include <atomic.h>
+#include <stdlib.h>
+#include <string.h>
+
+extern char **environ;
+
+int setenv(const char *var, const char *value, int overwrite)
+{
+	char **env = environ;
+	size_t var_len = strlen(var);
+
+	for (; *env; env++) {
+		char *eq = strchr(*env, '=');
+		if (eq && ((size_t)(eq - *env) == var_len) &&
+		    !strncmp(*env, var, var_len)) {
+			if (overwrite) {
+				size_t value_len = strlen(value);
+				char *new_env =
+					malloc(var_len + 1 + value_len + 1);
+				if (!new_env)
+					return -1;
+				memcpy(new_env, var, var_len);
+				new_env[var_len] = '=';
+				memcpy(new_env + var_len + 1, value,
+				       value_len + 1);
+				*env = new_env;
+			}
+			return 0;
+		}
+	}
+
+	size_t env_count = 0;
+	while (environ[env_count])
+		env_count++;
+
+	char **new_envp = realloc(environ, (env_count + 2) * sizeof(char *));
+	if (!new_envp)
+		return -1;
+
+	size_t value_len = strlen(value);
+	char *new_var = malloc(var_len + 1 + value_len + 1);
+	if (!new_var)
+		return -1;
+
+	memcpy(new_var, var, var_len);
+	new_var[var_len] = '=';
+	memcpy(new_var + var_len + 1, value, value_len + 1);
+
+	new_envp[env_count] = new_var;
+	new_envp[env_count + 1] = NULL;
+	LIBC_LOCK(libc.lock.environ);
+	environ = new_envp;
+	LIBC_UNLOCK(libc.lock.environ);
+	libc.flags |= LIBC_ENVP_TOUCHED;
+
+	return 0;
+}
diff --git a/lib/libc/stdlib/strtox.c b/lib/libc/stdlib/strtox.c
new file mode 100644
index 00000000..9d72954a
--- /dev/null
+++ b/lib/libc/stdlib/strtox.c
@@ -0,0 +1,270 @@
+#include <ctype.h>
+#include <float.h>
+#include <errno.h>
+#include <strings.h>
+#include <limits.h>
+#include <math.h>
+#include <stdlib.h>
+
+static unsigned long long
+__scanint(const char *s, int base, unsigned long long lim, int *neg, char **end)
+{
+	unsigned long long res = 0;
+	int digit, any = 0;
+
+	while (isspace((unsigned char)*s))
+		s++;
+
+	*neg = 0;
+	if (*s == '+' || *s == '-') {
+		*neg = (*s == '-');
+		s++;
+	}
+
+	if ((base == 0 || base == 16) && s[0] == '0' &&
+	    (s[1] == 'x' || s[1] == 'X')) {
+		base = 16;
+		s += 2;
+	} else if (base == 0 && *s == '0') {
+		base = 8;
+		s++;
+	} else if (base == 0) {
+		base = 10;
+	}
+
+	for (; *s; s++) {
+		unsigned char c = *s;
+		if (isdigit(c))
+			digit = c - '0';
+		else if (isalpha(c))
+			digit = toupper(c) - 'A' + 10;
+		else
+			break;
+
+		if (digit >= base)
+			break;
+		if (res > (lim - digit) / base) {
+			errno = ERANGE;
+			res = lim;
+			any = 1;
+			while (1) {
+				if (isalnum((unsigned char)*++s) == 0)
+					break;
+			}
+			break;
+		}
+		res = res * base + digit;
+		any = 1;
+	}
+
+	if (end)
+		*end = (char *)(any ? s : s - 1);
+
+	return res;
+}
+
+static long double __scanfloat(const char *s, char **end)
+{
+	long double value = 0.0;
+	long double frac = 0.0;
+	long double sign = 1.0;
+	long double scale = 1.0;
+	int exp_sign = 1;
+	long exp_val = 0;
+	int got_digit = 0;
+
+	while (isspace((unsigned char)*s))
+		s++;
+
+	if (*s == '+' || *s == '-') {
+		if (*s == '-')
+			sign = -1.0;
+		s++;
+	}
+
+	if (strncasecmp(s, "inf", 3) == 0) {
+		s += 3;
+		if (strncasecmp(s, "inity", 5) == 0)
+			s += 5;
+		if (end)
+			*end = (char *)s;
+		return sign * INFINITY;
+	}
+	if (strncasecmp(s, "nan", 3) == 0) {
+		s += 3;
+		if (*s == '(') {
+			s++;
+			while (*s && *s != ')')
+				s++;
+			if (*s == ')')
+				s++;
+		}
+		if (end)
+			*end = (char *)s;
+		return NAN;
+	}
+
+	while (isdigit((unsigned char)*s)) {
+		value = value * 10.0 + (*s - '0');
+		s++;
+		got_digit = 1;
+	}
+
+	if (*s == '.') {
+		s++;
+		while (isdigit((unsigned char)*s)) {
+			value = value * 10.0 + (*s - '0');
+			scale *= 10.0;
+			s++;
+			got_digit = 1;
+		}
+	}
+
+	if (!got_digit) {
+		if (end)
+			*end = (char *)s;
+		return 0.0;
+	}
+
+	value = value / scale;
+
+	if (*s == 'e' || *s == 'E') {
+		const char *p = ++s;
+		if (*p == '+' || *p == '-') {
+			exp_sign = (*p == '-') ? -1 : 1;
+			p++;
+		}
+		while (isdigit((unsigned char)*p)) {
+			exp_val = exp_val * 10 + (*p - '0');
+			p++;
+		}
+		s = p;
+		value *= powl(10.0, exp_sign * exp_val);
+	}
+
+	if (end)
+		*end = (char *)s;
+
+	return sign * value;
+}
+
+long strtol(const char *restrict nptr, char **restrict endptr, int base)
+{
+	int neg;
+	unsigned long long lim;
+	unsigned long long v;
+
+	const char *p = nptr;
+	while (isspace((unsigned char)*p))
+		p++;
+	int is_neg = (*p == '-');
+	lim = is_neg ? (unsigned long long)LONG_MAX + 1ULL : LONG_MAX;
+
+	v = __scanint(nptr, base, lim, &neg, endptr);
+
+	if (neg)
+		return (v == lim) ? LONG_MIN : -(long)v;
+	else
+		return (v > LONG_MAX) ? (errno = ERANGE, LONG_MAX) : (long)v;
+}
+
+long long strtoll(const char *restrict nptr, char **restrict endptr, int base)
+{
+	int neg;
+	unsigned long long lim;
+	unsigned long long v;
+
+	const char *p = nptr;
+	while (isspace((unsigned char)*p))
+		p++;
+	int is_neg = (*p == '-');
+
+	lim = is_neg ? (unsigned long long)LLONG_MAX + 1ULL : LLONG_MAX;
+
+	v = __scanint(nptr, base, lim, &neg, endptr);
+
+	if (neg) {
+		if (v == lim)
+			return LLONG_MIN;
+		else
+			return -(long long)v;
+	} else {
+		if (v > LLONG_MAX) {
+			errno = ERANGE;
+			return LLONG_MAX;
+		} else
+			return (long long)v;
+	}
+}
+
+unsigned long strtoul(const char *restrict nptr, char **restrict endptr,
+		      int base)
+{
+	int neg;
+	unsigned long long v;
+
+	v = __scanint(nptr, base, ULONG_MAX, &neg, endptr);
+
+	if (neg) {
+		errno = EINVAL;
+		return 0;
+	}
+
+	if (v > ULONG_MAX) {
+		errno = ERANGE;
+		return ULONG_MAX;
+	}
+
+	return (unsigned long)v;
+}
+
+unsigned long long strtoull(const char *restrict nptr, char **restrict endptr,
+			    int base)
+{
+	int neg;
+	unsigned long long v;
+
+	v = __scanint(nptr, base, ULLONG_MAX, &neg, endptr);
+
+	if (neg) {
+		errno = EINVAL;
+		return 0;
+	}
+
+	if (v > ULLONG_MAX) {
+		errno = ERANGE;
+		return ULLONG_MAX;
+	}
+
+	return v;
+}
+
+float strtof(const char *restrict nptr, char **restrict endptr)
+{
+	long double val = __scanfloat(nptr, endptr);
+
+	if (val > FLT_MAX) {
+		errno = ERANGE;
+		return HUGE_VALF;
+	} else if (val < -FLT_MAX) {
+		errno = ERANGE;
+		return -HUGE_VALF;
+	}
+
+	return (float)val;
+}
+
+long double strtold(const char *restrict nptr, char **restrict endptr)
+{
+	long double val = __scanfloat(nptr, endptr);
+
+	if (val > LDBL_MAX) {
+		errno = ERANGE;
+		return LDBL_MAX;
+	} else if (val < -LDBL_MAX) {
+		errno = ERANGE;
+		return -LDBL_MAX;
+	}
+
+	return val;
+}
diff --git a/lib/libc/stdlib/system.c b/lib/libc/stdlib/system.c
new file mode 100644
index 00000000..4f560ce1
--- /dev/null
+++ b/lib/libc/stdlib/system.c
@@ -0,0 +1,7 @@
+#include <stdlib.h>
+
+int system(const char *command)
+{
+	// TODO
+	return 0;
+}
diff --git a/lib/libc/stdlib/unsetenv.c b/lib/libc/stdlib/unsetenv.c
new file mode 100644
index 00000000..4eb11d57
--- /dev/null
+++ b/lib/libc/stdlib/unsetenv.c
@@ -0,0 +1,13 @@
+#include <errno.h>
+#include <string.h>
+#include <stdlib.h>
+
+int unsetenv(const char *name)
+{
+	if (name == NULL || *name == '\0' || strchr(name, '=')) {
+		errno = EINVAL;
+		return -1;
+	}
+
+	return setenv(name, NULL, 1);
+}
diff --git a/lib/libc/stdlib/wctomb.c b/lib/libc/stdlib/wctomb.c
new file mode 100644
index 00000000..d971ffae
--- /dev/null
+++ b/lib/libc/stdlib/wctomb.c
@@ -0,0 +1,9 @@
+#include <stdlib.h>
+#include <wchar.h>
+
+int wctomb(char *s, wchar_t wc)
+{
+	if (s == NULL)
+		return 0;
+	return wcrtomb(s, wc, 0);
+}