Index: uspace/lib/c/generic/elf/elf_load.c
===================================================================
--- uspace/lib/c/generic/elf/elf_load.c	(revision 0b0508283ddd2f79e0dcee257b44867abb882bdf)
+++ uspace/lib/c/generic/elf/elf_load.c	(revision 40abf56ae4263cdef7e6b8d2a4f5f794c32dedf3)
@@ -68,5 +68,5 @@
 	}
 
-	if (info->finfo.interp == NULL) {
+	if (info->finfo.dynamic == NULL) {
 		/* Statically linked program */
 		DPRINTF("Binary is statically linked.\n");
Index: uspace/lib/c/generic/fibril.c
===================================================================
--- uspace/lib/c/generic/fibril.c	(revision 0b0508283ddd2f79e0dcee257b44867abb882bdf)
+++ uspace/lib/c/generic/fibril.c	(revision 40abf56ae4263cdef7e6b8d2a4f5f794c32dedf3)
@@ -50,5 +50,5 @@
 #include "private/thread.h"
 #include "private/fibril.h"
-
+#include "private/libc.h"
 
 /**
@@ -85,10 +85,8 @@
 }
 
-/** Setup fibril information into TCB structure
- *
- */
-fibril_t *fibril_setup(void)
-{
-	tcb_t *tcb = tls_make();
+/** Allocate a fibril structure and TCB, but don't do anything else with it. */
+fibril_t *fibril_alloc(void)
+{
+	tcb_t *tcb = tls_make(__progsymbols.elfstart);
 	if (!tcb)
 		return NULL;
@@ -102,15 +100,18 @@
 	tcb->fibril_data = fibril;
 	fibril->tcb = tcb;
-
-	/*
-	 * We are called before __tcb_set(), so we need to use
-	 * futex_down/up() instead of futex_lock/unlock() that
-	 * may attempt to access TLS.
-	 */
-	futex_down(&fibril_futex);
-	list_append(&fibril->all_link, &fibril_list);
-	futex_up(&fibril_futex);
-
+	fibril->is_freeable = true;
+
+	fibril_setup(fibril);
 	return fibril;
+}
+
+/**
+ * Put the fibril into fibril_list.
+ */
+void fibril_setup(fibril_t *f)
+{
+	futex_lock(&fibril_futex);
+	list_append(&f->all_link, &fibril_list);
+	futex_unlock(&fibril_futex);
 }
 
@@ -122,6 +123,9 @@
 	if (!locked)
 		futex_unlock(&fibril_futex);
-	tls_free(fibril->tcb);
-	free(fibril);
+
+	if (fibril->is_freeable) {
+		tls_free(fibril->tcb);
+		free(fibril);
+	}
 }
 
@@ -239,5 +243,5 @@
 	fibril_t *fibril;
 
-	fibril = fibril_setup();
+	fibril = fibril_alloc();
 	if (fibril == NULL)
 		return 0;
@@ -248,5 +252,5 @@
 	    AS_AREA_READ | AS_AREA_WRITE | AS_AREA_CACHEABLE | AS_AREA_GUARD |
 	    AS_AREA_LATE_RESERVE, AS_AREA_UNPAGED);
-	if (fibril->stack == (void *) -1) {
+	if (fibril->stack == AS_MAP_FAILED) {
 		fibril_teardown(fibril, false);
 		return 0;
@@ -324,5 +328,8 @@
 fibril_t *fibril_self(void)
 {
-	return __tcb_get()->fibril_data;
+	assert(__tcb_is_set());
+	tcb_t *tcb = __tcb_get();
+	assert(tcb->fibril_data);
+	return tcb->fibril_data;
 }
 
Index: uspace/lib/c/generic/io/kio.c
===================================================================
--- uspace/lib/c/generic/io/kio.c	(revision 0b0508283ddd2f79e0dcee257b44867abb882bdf)
+++ uspace/lib/c/generic/io/kio.c	(revision 40abf56ae4263cdef7e6b8d2a4f5f794c32dedf3)
@@ -56,5 +56,6 @@
 errno_t kio_write(const void *buf, size_t size, size_t *nwritten)
 {
-	futex_lock(&kio_buffer.futex);
+	/* Using down/up instead of lock/unlock so we can print very early. */
+	futex_down(&kio_buffer.futex);
 
 	const char *s = buf;
@@ -82,5 +83,5 @@
 	}
 
-	futex_unlock(&kio_buffer.futex);
+	futex_up(&kio_buffer.futex);
 	if (nwritten)
 		*nwritten = size;
Index: uspace/lib/c/generic/libc.c
===================================================================
--- uspace/lib/c/generic/libc.c	(revision 0b0508283ddd2f79e0dcee257b44867abb882bdf)
+++ uspace/lib/c/generic/libc.c	(revision 40abf56ae4263cdef7e6b8d2a4f5f794c32dedf3)
@@ -63,13 +63,35 @@
 progsymbols_t __progsymbols;
 
-static bool env_setup = false;
+static bool env_setup;
+static fibril_t main_fibril;
 
 void __libc_main(void *pcb_ptr)
 {
+	assert(!__tcb_is_set());
+
+	__pcb = (pcb_t *) pcb_ptr;
+
+	if (__pcb) {
+		main_fibril.tcb = __pcb->tcb;
+	} else {
+		/*
+		 * Loaded by kernel, not the loader.
+		 * Kernel only supports loading fully static binaries,
+		 * so we can do basic initialization without worrying about
+		 * dynamic libraries.
+		 */
+
+		main_fibril.tcb = tls_make_initial(__progsymbols.elfstart);
+	}
+
+	assert(main_fibril.tcb);
+
+	/* Initialize the fibril. */
+	main_fibril.tcb->fibril_data = &main_fibril;
+	__tcb_set(main_fibril.tcb);
+	fibril_setup(&main_fibril);
+
 	/* Initialize user task run-time environment */
 	__malloc_init();
-
-	/* Save the PCB pointer */
-	__pcb = (pcb_t *) pcb_ptr;
 
 #ifdef CONFIG_RTLD
@@ -81,10 +103,4 @@
 	}
 #endif
-
-	fibril_t *fibril = fibril_setup();
-	if (fibril == NULL)
-		abort();
-
-	__tcb_set(fibril->tcb);
 
 	__async_server_init();
@@ -151,5 +167,4 @@
 		__stdio_done();
 		task_retval(status);
-		fibril_teardown(__tcb_get()->fibril_data, false);
 	}
 
Index: uspace/lib/c/generic/private/fibril.h
===================================================================
--- uspace/lib/c/generic/private/fibril.h	(revision 0b0508283ddd2f79e0dcee257b44867abb882bdf)
+++ uspace/lib/c/generic/private/fibril.h	(revision 40abf56ae4263cdef7e6b8d2a4f5f794c32dedf3)
@@ -55,4 +55,6 @@
 	atomic_t futex_locks;
 	bool is_writer : 1;
+	/* In some places, we use fibril structs that can't be freed. */
+	bool is_freeable : 1;
 };
 
@@ -64,5 +66,6 @@
 } fibril_switch_type_t;
 
-extern fibril_t *fibril_setup(void);
+extern fibril_t *fibril_alloc(void);
+extern void fibril_setup(fibril_t *);
 extern void fibril_teardown(fibril_t *f, bool locked);
 extern int fibril_switch(fibril_switch_type_t stype);
Index: uspace/lib/c/generic/rtld/module.c
===================================================================
--- uspace/lib/c/generic/rtld/module.c	(revision 0b0508283ddd2f79e0dcee257b44867abb882bdf)
+++ uspace/lib/c/generic/rtld/module.c	(revision 40abf56ae4263cdef7e6b8d2a4f5f794c32dedf3)
@@ -368,4 +368,6 @@
 	 * be correct, "zero" offset (i.e. the total size) must be aligned
 	 * to the strictest alignment present.
+	 * Note that the padding is actually in front of the TLS data,
+	 * not after it.
 	 */
 	rtld->tls_size = ALIGN_UP(rtld->tls_size, rtld->tls_align);
Index: uspace/lib/c/generic/thread.c
===================================================================
--- uspace/lib/c/generic/thread.c	(revision 0b0508283ddd2f79e0dcee257b44867abb882bdf)
+++ uspace/lib/c/generic/thread.c	(revision 40abf56ae4263cdef7e6b8d2a4f5f794c32dedf3)
@@ -58,11 +58,12 @@
 void __thread_main(uspace_arg_t *uarg)
 {
-	fibril_t *fibril = fibril_setup();
-	if (fibril == NULL)
-		thread_exit(0);
+	assert(!__tcb_is_set());
+
+	fibril_t *fibril = uarg->uspace_thread_arg;
+	assert(fibril);
 
 	__tcb_set(fibril->tcb);
 
-	uarg->uspace_thread_function(uarg->uspace_thread_arg);
+	uarg->uspace_thread_function(fibril->arg);
 	/*
 	 * XXX: we cannot free the userspace stack while running on it
@@ -95,8 +96,13 @@
     thread_id_t *tid)
 {
-	uspace_arg_t *uarg =
-	    (uspace_arg_t *) malloc(sizeof(uspace_arg_t));
+	uspace_arg_t *uarg = calloc(1, sizeof(uspace_arg_t));
 	if (!uarg)
 		return ENOMEM;
+
+	fibril_t *fibril = fibril_alloc();
+	if (!fibril) {
+		free(uarg);
+		return ENOMEM;
+	}
 
 	size_t stack_size = stack_size_get();
@@ -105,4 +111,5 @@
 	    AS_AREA_LATE_RESERVE, AS_AREA_UNPAGED);
 	if (stack == AS_MAP_FAILED) {
+		fibril_teardown(fibril, false);
 		free(uarg);
 		return ENOMEM;
@@ -112,9 +119,10 @@
 	malloc_enable_multithreaded();
 
+	fibril->arg = arg;
 	uarg->uspace_entry = (void *) FADDR(__thread_entry);
 	uarg->uspace_stack = stack;
 	uarg->uspace_stack_size = stack_size;
 	uarg->uspace_thread_function = function;
-	uarg->uspace_thread_arg = arg;
+	uarg->uspace_thread_arg = fibril;
 	uarg->uspace_uarg = uarg;
 
Index: uspace/lib/c/generic/tls.c
===================================================================
--- uspace/lib/c/generic/tls.c	(revision 0b0508283ddd2f79e0dcee257b44867abb882bdf)
+++ uspace/lib/c/generic/tls.c	(revision 40abf56ae4263cdef7e6b8d2a4f5f794c32dedf3)
@@ -44,10 +44,13 @@
 #include <macros.h>
 #include <elf/elf.h>
+#include <as.h>
+
+#include <libarch/config.h>
+
+#ifdef CONFIG_RTLD
+#include <rtld/rtld.h>
+#endif
 
 #include "private/libc.h"
-
-#ifdef CONFIG_RTLD
-#include <rtld/rtld.h>
-#endif
 
 #if !defined(CONFIG_TLS_VARIANT_1) && !defined(CONFIG_TLS_VARIANT_2)
@@ -55,4 +58,19 @@
 #endif
 
+static ptrdiff_t _tcb_data_offset(void)
+{
+	const elf_segment_header_t *tls =
+	    elf_get_phdr(__progsymbols.elfstart, PT_TLS);
+
+	size_t tls_align = tls ? tls->p_align : 1;
+
+#ifdef CONFIG_TLS_VARIANT_1
+	return ALIGN_UP((ptrdiff_t) sizeof(tcb_t), tls_align);
+#else
+	size_t tls_size = tls ? tls->p_memsz : 0;
+	return -ALIGN_UP((ptrdiff_t) tls_size, max(tls_align, _Alignof(tcb_t)));
+#endif
+}
+
 /** Get address of static TLS block */
 void *tls_get(void)
@@ -61,16 +79,78 @@
 	assert(runtime_env == NULL);
 #endif
-
-	const elf_segment_header_t *tls =
-	    elf_get_phdr(__progsymbols.elfstart, PT_TLS);
-
-	if (tls == NULL)
-		return NULL;
-
-#ifdef CONFIG_TLS_VARIANT_1
-	return (uint8_t *)__tcb_get() + ALIGN_UP(sizeof(tcb_t), tls->p_align);
-#else /* CONFIG_TLS_VARIANT_2 */
-	return (uint8_t *)__tcb_get() - ALIGN_UP(tls->p_memsz, tls->p_align);
-#endif
+	return (uint8_t *)__tcb_get() + _tcb_data_offset();
+}
+
+static tcb_t *tls_make_generic(const void *elf, void *(*alloc)(size_t, size_t))
+{
+	assert(!elf_get_phdr(elf, PT_DYNAMIC));
+#ifdef CONFIG_RTLD
+	assert(runtime_env == NULL);
+#endif
+
+	const elf_segment_header_t *tls = elf_get_phdr(elf, PT_TLS);
+	size_t tls_size = tls ? tls->p_memsz : 0;
+	size_t tls_align = tls ? tls->p_align : 1;
+
+	/*
+	 * We don't currently support alignment this big,
+	 * and neither should we need to.
+	 */
+	assert(tls_align <= PAGE_SIZE);
+
+#ifdef CONFIG_TLS_VARIANT_1
+	size_t alloc_size =
+	    ALIGN_UP(sizeof(tcb_t), tls_align) + tls_size;
+#else
+	size_t alloc_size =
+	    ALIGN_UP(tls_size, max(tls_align, _Alignof(tcb_t))) + sizeof(tcb_t);
+#endif
+
+	void *area = alloc(max(tls_align, _Alignof(tcb_t)), alloc_size);
+	if (!area)
+		return NULL;
+
+#ifdef CONFIG_TLS_VARIANT_1
+	tcb_t *tcb = area;
+	uint8_t *data = (uint8_t *)tcb + _tcb_data_offset();
+	memset(tcb, 0, sizeof(*tcb));
+#else
+	uint8_t *data = area;
+	tcb_t *tcb = (tcb_t *) (data - _tcb_data_offset());
+	memset(tcb, 0, sizeof(tcb_t));
+	tcb->self = tcb;
+#endif
+
+	if (!tls)
+		return tcb;
+
+	uintptr_t bias = elf_get_bias(elf);
+
+	/* Copy thread local data from the initialization image. */
+	memcpy(data, (void *)(tls->p_vaddr + bias), tls->p_filesz);
+	/* Zero out the thread local uninitialized data. */
+	memset(data + tls->p_filesz, 0, tls->p_memsz - tls->p_filesz);
+
+	return tcb;
+}
+
+static void *early_alloc(size_t align, size_t alloc_size)
+{
+	assert(align <= PAGE_SIZE);
+	alloc_size = ALIGN_UP(alloc_size, PAGE_SIZE);
+
+	void *area = as_area_create(AS_AREA_ANY, alloc_size,
+	    AS_AREA_READ | AS_AREA_WRITE | AS_AREA_CACHEABLE, AS_AREA_UNPAGED);
+	if (area == AS_MAP_FAILED)
+		return NULL;
+	return area;
+}
+
+/** Same as tls_make(), but uses as_area_create() instead of memalign().
+ *  Only used in __libc_main() if the program was created by the kernel.
+ */
+tcb_t *tls_make_initial(const void *elf)
+{
+	return tls_make_generic(elf, early_alloc);
 }
 
@@ -79,8 +159,7 @@
  * @return Pointer to TCB.
  */
-tcb_t *tls_make(void)
-{
-	void *data;
-	tcb_t *tcb;
+tcb_t *tls_make(const void *elf)
+{
+	// TODO: Always use rtld.
 
 #ifdef CONFIG_RTLD
@@ -89,32 +168,5 @@
 #endif
 
-	const elf_segment_header_t *tls =
-	    elf_get_phdr(__progsymbols.elfstart, PT_TLS);
-	if (tls == NULL)
-		return NULL;
-
-	uintptr_t bias = elf_get_bias(__progsymbols.elfstart);
-	size_t align = max(tls->p_align, _Alignof(tcb_t));
-
-#ifdef CONFIG_TLS_VARIANT_1
-	tcb = tls_alloc_arch(
-	    ALIGN_UP(sizeof(tcb_t), align) + tls->p_memsz, align);
-	data = (void *) tcb + ALIGN_UP(sizeof(tcb_t), align);
-#else
-	tcb = tls_alloc_arch(
-	    ALIGN_UP(tls->p_memsz, align) + sizeof(tcb_t), align);
-	data = (void *) tcb - ALIGN_UP(tls->p_memsz, tls->p_align);
-#endif
-
-	/*
-	 * Copy thread local data from the initialization image.
-	 */
-	memcpy(data, (void *)(tls->p_vaddr + bias), tls->p_filesz);
-	/*
-	 * Zero out the thread local uninitialized data.
-	 */
-	memset(data + tls->p_filesz, 0, tls->p_memsz - tls->p_filesz);
-
-	return tcb;
+	return tls_make_generic(elf, memalign);
 }
 
Index: uspace/lib/c/include/loader/pcb.h
===================================================================
--- uspace/lib/c/include/loader/pcb.h	(revision 0b0508283ddd2f79e0dcee257b44867abb882bdf)
+++ uspace/lib/c/include/loader/pcb.h	(revision 40abf56ae4263cdef7e6b8d2a4f5f794c32dedf3)
@@ -37,4 +37,5 @@
 #define LIBC_PCB_H_
 
+#include <tls.h>
 
 typedef void (*entry_point_t)(void);
@@ -76,4 +77,7 @@
 	/** Pointer to dynamic linker state structure (rtld_t). */
 	void *rtld_runtime;
+
+	/** Thread local storage for the main thread. */
+	tcb_t *tcb;
 } pcb_t;
 
Index: uspace/lib/c/include/tls.h
===================================================================
--- uspace/lib/c/include/tls.h	(revision 0b0508283ddd2f79e0dcee257b44867abb882bdf)
+++ uspace/lib/c/include/tls.h	(revision 40abf56ae4263cdef7e6b8d2a4f5f794c32dedf3)
@@ -69,5 +69,6 @@
 #define DTV_GN(dtv) (((uintptr_t *)(dtv))[0])
 
-extern tcb_t *tls_make(void);
+extern tcb_t *tls_make(const void *);
+extern tcb_t *tls_make_initial(const void *);
 extern tcb_t *tls_alloc_arch(size_t, size_t);
 extern void tls_free(tcb_t *);
Index: uspace/srv/loader/main.c
===================================================================
--- uspace/srv/loader/main.c	(revision 0b0508283ddd2f79e0dcee257b44867abb882bdf)
+++ uspace/srv/loader/main.c	(revision 40abf56ae4263cdef7e6b8d2a4f5f794c32dedf3)
@@ -62,4 +62,8 @@
 #include <vfs/inbox.h>
 
+#ifdef CONFIG_RTLD
+#include <rtld/rtld.h>
+#endif
+
 #define DPRINTF(...) ((void) 0)
 
@@ -296,4 +300,14 @@
 	DPRINTF("Loaded.\n");
 
+#ifdef CONFIG_RTLD
+	if (prog_info.env) {
+		pcb.tcb = rtld_tls_make(prog_info.env);
+	} else {
+		pcb.tcb = tls_make(prog_info.finfo.base);
+	}
+#else
+	pcb.tcb = tls_make(prog_info.finfo.base);
+#endif
+
 	elf_set_pcb(&prog_info, &pcb);
 
@@ -328,5 +342,8 @@
 	DPRINTF("Reply OK\n");
 	async_answer_0(req, EOK);
+
 	DPRINTF("Jump to entry point at %p\n", pcb.entry);
+
+	__tcb_reset();
 	entry_point_jmp(prog_info.finfo.entry, &pcb);
 
