allow regions to have reserved areas

+ A reserved area is an area at the start of the region that should not
  be used unless explicitly asked for, for example null pages.

  As such, a small correction to my previous commit message: There's no
  danger in not locking req_mem() etc, as a null page will only be
  allocated when explicitly asked for.

10 files changed, 151 insertions, 111 deletions

diff --git a/arch/riscv64/conf/init.c b/arch/riscv64/conf/init.c
index 03fdc64..c4e8064 100644
--- a/arch/riscv64/conf/init.c
+++ b/arch/riscv64/conf/init.c
@@ -273,7 +273,7 @@ static void sys_sleep()
 
 #define CSR_TIME "0xc01"
 #define csr_read(csr, \
-	         res) __asm__ volatile ("csrr %0, " csr : "=r" (res) :: "memory")
+		 res) __asm__ volatile ("csrr %0, " csr : "=r" (res) :: "memory")
 
 #define CSR_CYCLE "0xc00"
 
diff --git a/include/kmi/atomic.h b/include/kmi/atomic.h
index 76d50e4..88ffdfa 100644
--- a/include/kmi/atomic.h
+++ b/include/kmi/atomic.h
@@ -404,7 +404,7 @@ typedef _Atomic __UINTMAX_TYPE__ atomic_uintmax_t;
  */
 #define atomic_compare_exchange_weak(obj, val, des)                            \
 	atomic_compare_exchange_weak_explicit(obj, val, des, __ATOMIC_SEQ_CST, \
-	                                      __ATOMIC_SEQ_CST)
+					      __ATOMIC_SEQ_CST)
 
 /**
  * Explicit atomic in-place addition.
diff --git a/include/kmi/regions.h b/include/kmi/regions.h
index 1d96f00..e612543 100644
--- a/include/kmi/regions.h
+++ b/include/kmi/regions.h
@@ -54,6 +54,17 @@ void destroy_mem_nodes();
 
 /** Root of memory region. */
 struct mem_region_root {
+	/** How many pages are reserved, i.e. will never be allocated by \ref
+	 * alloc_region(), they have to explicitly be requested for by
+	 * \ref alloc_fixed_region(). */
+	size_t reserved;
+
+	/** Helper for reserved calculations. */
+	vm_t start;
+
+	/** Currently unused. */
+	vm_t end;
+
 	/** Sp-tree of free regions. */
 	struct sp_root free_regions;
 
@@ -99,10 +110,14 @@ struct mem_region {
  * @param r Memory region root to initialize.
  * @param start Start of memory arena.
  * @param arena_size Size of memory arena.
+ * @param reserved Size of reserved area. The reserved area will never be
+ * allocated from with \ref alloc_region(), the user has to explicitly ask to
+ * use that region.
  * @return \ref OK on success.
  * \todo Document error codes when I actually implement them properly.
  */
-stat_t init_region(struct mem_region_root *r, vm_t start, size_t arena_size);
+stat_t init_region(struct mem_region_root *r, vm_t start, size_t arena_size,
+                   size_t reserved);
 
 /**
  * Destroy memory region subsystem instance.
@@ -211,6 +226,7 @@ struct mem_region *find_closest_used_region(struct mem_region_root *r,
 
 /**
  * Find best region that fulfills requested parameters.
+ * Respects the reserved region of \p r.
  *
  * @param r Memory region root.
  * @param size Size of free region.
diff --git a/include/kmi/uapi.h b/include/kmi/uapi.h
index 65a4d93..350285f 100644
--- a/include/kmi/uapi.h
+++ b/include/kmi/uapi.h
@@ -50,11 +50,11 @@ typedef void (*sys_t)(struct tcb *t, long, long, long, long, long);
  */
 #define SYSCALL_DECLARE0(name)         \
 	void sys_##name(struct tcb *t, \
-	                sys_arg_t a,   \
-	                sys_arg_t b,   \
-	                sys_arg_t c,   \
-	                sys_arg_t d,   \
-	                sys_arg_t e);
+			sys_arg_t a,   \
+			sys_arg_t b,   \
+			sys_arg_t c,   \
+			sys_arg_t d,   \
+			sys_arg_t e);
 
 /**
  * Helper macro for declaring syscalls with one argument.
@@ -64,8 +64,8 @@ typedef void (*sys_t)(struct tcb *t, long, long, long, long, long);
  */
 #define SYSCALL_DECLARE1(name, a)                                \
 	void sys_##name(struct tcb *t, sys_arg_t a, sys_arg_t b, \
-	                sys_arg_t c,                             \
-	                sys_arg_t d, sys_arg_t e);
+			sys_arg_t c,                             \
+			sys_arg_t d, sys_arg_t e);
 
 /**
  * Helper macro for declaring syscalls with two arguments.
@@ -76,8 +76,8 @@ typedef void (*sys_t)(struct tcb *t, long, long, long, long, long);
  */
 #define SYSCALL_DECLARE2(name, a, b)                             \
 	void sys_##name(struct tcb *t, sys_arg_t a, sys_arg_t b, \
-	                sys_arg_t c,                             \
-	                sys_arg_t d, sys_arg_t e);
+			sys_arg_t c,                             \
+			sys_arg_t d, sys_arg_t e);
 
 /**
  * Helper macro for declaring syscalls with three arguments.
@@ -89,8 +89,8 @@ typedef void (*sys_t)(struct tcb *t, long, long, long, long, long);
  */
 #define SYSCALL_DECLARE3(name, a, b, c)                          \
 	void sys_##name(struct tcb *t, sys_arg_t a, sys_arg_t b, \
-	                sys_arg_t c,                             \
-	                sys_arg_t d, sys_arg_t e);
+			sys_arg_t c,                             \
+			sys_arg_t d, sys_arg_t e);
 
 /**
  * Helper macro for declaring syscalls with four arguments.
@@ -103,8 +103,8 @@ typedef void (*sys_t)(struct tcb *t, long, long, long, long, long);
  */
 #define SYSCALL_DECLARE4(name, a, b, c, d)                       \
 	void sys_##name(struct tcb *t, sys_arg_t a, sys_arg_t b, \
-	                sys_arg_t c,                             \
-	                sys_arg_t d, sys_arg_t e);
+			sys_arg_t c,                             \
+			sys_arg_t d, sys_arg_t e);
 
 /**
  * Helper macro for declaring syscalls with five arguments.
@@ -118,8 +118,8 @@ typedef void (*sys_t)(struct tcb *t, long, long, long, long, long);
  */
 #define SYSCALL_DECLARE5(name, a, b, c, d, e)                    \
 	void sys_##name(struct tcb *t, sys_arg_t a, sys_arg_t b, \
-	                sys_arg_t c,                             \
-	                sys_arg_t d, sys_arg_t e);
+			sys_arg_t c,                             \
+			sys_arg_t d, sys_arg_t e);
 
 /**
  * Helper macro for defining syscall with zero arguments.
@@ -135,8 +135,8 @@ typedef void (*sys_t)(struct tcb *t, long, long, long, long, long);
 #define SYSCALL_DEFINE0(name)                                               \
 	static inline void __##name(struct tcb *t);                         \
 	void __noinline sys_##name(struct tcb *t, sys_arg_t a, sys_arg_t b, \
-	                           sys_arg_t c,                             \
-	                           sys_arg_t d, sys_arg_t e)                \
+				   sys_arg_t c,                             \
+				   sys_arg_t d, sys_arg_t e)                \
 	{                                                                   \
 		UNUSED(a);                                                  \
 		UNUSED(b);                                                  \
@@ -155,8 +155,8 @@ typedef void (*sys_t)(struct tcb *t, long, long, long, long, long);
 #define SYSCALL_DEFINE1(name)                                               \
 	static inline void __##name(struct tcb *, sys_arg_t);               \
 	void __noinline sys_##name(struct tcb *t, sys_arg_t a, sys_arg_t b, \
-	                           sys_arg_t c,                             \
-	                           sys_arg_t d, sys_arg_t e)                \
+				   sys_arg_t c,                             \
+				   sys_arg_t d, sys_arg_t e)                \
 	{                                                                   \
 		UNUSED(b);                                                  \
 		UNUSED(c);                                                  \
@@ -173,10 +173,10 @@ typedef void (*sys_t)(struct tcb *t, long, long, long, long, long);
  */
 #define SYSCALL_DEFINE2(name)                                               \
 	static inline void __##name(struct tcb *, sys_arg_t,                \
-	                            sys_arg_t);                             \
+				    sys_arg_t);                             \
 	void __noinline sys_##name(struct tcb *t, sys_arg_t a, sys_arg_t b, \
-	                           sys_arg_t c,                             \
-	                           sys_arg_t d, sys_arg_t e)                \
+				   sys_arg_t c,                             \
+				   sys_arg_t d, sys_arg_t e)                \
 	{                                                                   \
 		UNUSED(c);                                                  \
 		UNUSED(d);                                                  \
@@ -192,11 +192,11 @@ typedef void (*sys_t)(struct tcb *t, long, long, long, long, long);
  */
 #define SYSCALL_DEFINE3(name)                                               \
 	static inline void __##name(struct tcb *, sys_arg_t,                \
-	                            sys_arg_t,                              \
-	                            sys_arg_t);                             \
+				    sys_arg_t,                              \
+				    sys_arg_t);                             \
 	void __noinline sys_##name(struct tcb *t, sys_arg_t a, sys_arg_t b, \
-	                           sys_arg_t c,                             \
-	                           sys_arg_t d, sys_arg_t e)                \
+				   sys_arg_t c,                             \
+				   sys_arg_t d, sys_arg_t e)                \
 	{                                                                   \
 		UNUSED(d);                                                  \
 		UNUSED(e);                                                  \
@@ -211,11 +211,11 @@ typedef void (*sys_t)(struct tcb *t, long, long, long, long, long);
  */
 #define SYSCALL_DEFINE4(name)                                               \
 	static inline void __##name(struct tcb *, sys_arg_t,                \
-	                            sys_arg_t, sys_arg_t,                   \
-	                            sys_arg_t);                             \
+				    sys_arg_t, sys_arg_t,                   \
+				    sys_arg_t);                             \
 	void __noinline sys_##name(struct tcb *t, sys_arg_t a, sys_arg_t b, \
-	                           sys_arg_t c,                             \
-	                           sys_arg_t d, sys_arg_t e)                \
+				   sys_arg_t c,                             \
+				   sys_arg_t d, sys_arg_t e)                \
 	{                                                                   \
 		UNUSED(e);                                                  \
 		__##name(t, a, b, c, d);                                    \
@@ -229,11 +229,11 @@ typedef void (*sys_t)(struct tcb *t, long, long, long, long, long);
  */
 #define SYSCALL_DEFINE5(name)                                               \
 	static inline void __##name(struct tcb *, sys_arg_t,                \
-	                            sys_arg_t, sys_arg_t,                   \
-	                            sys_arg_t, sys_arg_t);                  \
+				    sys_arg_t, sys_arg_t,                   \
+				    sys_arg_t, sys_arg_t);                  \
 	void __noinline sys_##name(struct tcb *t, sys_arg_t a, sys_arg_t b, \
-	                           sys_arg_t c,                             \
-	                           sys_arg_t d, sys_arg_t e)                \
+				   sys_arg_t c,                             \
+				   sys_arg_t d, sys_arg_t e)                \
 	{                                                                   \
 		__##name(t, a, b, c, d, e);                                 \
 	}                                                                   \
diff --git a/include/kmi/unaligned.h b/include/kmi/unaligned.h
index fac5146..89f5894 100644
--- a/include/kmi/unaligned.h
+++ b/include/kmi/unaligned.h
@@ -20,15 +20,15 @@
  */
 #define get_unaligned(ptr)                         \
 	_Generic(*(ptr),                           \
-	         uint8_t: get_unaligned_uint8_t,   \
-	         uint16_t: get_unaligned_uint16_t, \
-	         uint32_t: get_unaligned_uint32_t, \
-	         uint64_t: get_unaligned_uint64_t, \
+		 uint8_t: get_unaligned_uint8_t,   \
+		 uint16_t: get_unaligned_uint16_t, \
+		 uint32_t: get_unaligned_uint32_t, \
+		 uint64_t: get_unaligned_uint64_t, \
                                                    \
-	         int8_t: get_unaligned_int8_t,     \
-	         int16_t: get_unaligned_int16_t,   \
-	         int32_t: get_unaligned_int32_t,   \
-	         int64_t: get_unaligned_int64_t)((void *)ptr)
+		 int8_t: get_unaligned_int8_t,     \
+		 int16_t: get_unaligned_int16_t,   \
+		 int32_t: get_unaligned_int32_t,   \
+		 int64_t: get_unaligned_int64_t)((void *)ptr)
 
 /**
  * Put unaligned value. Type of value is deduced from pointer type.
@@ -38,15 +38,15 @@
  */
 #define put_unaligned(val, ptr)                    \
 	_Generic(*(ptr),                           \
-	         uint8_t: put_unaligned_uint8_t,   \
-	         uint16_t: put_unaligned_uint16_t, \
-	         uint32_t: put_unaligned_uint32_t, \
-	         uint64_t: put_unaligned_uint64_t, \
+		 uint8_t: put_unaligned_uint8_t,   \
+		 uint16_t: put_unaligned_uint16_t, \
+		 uint32_t: put_unaligned_uint32_t, \
+		 uint64_t: put_unaligned_uint64_t, \
                                                    \
-	         int8_t: put_unaligned_int8_t,     \
-	         int16_t: put_unaligned_int16_t,   \
-	         int32_t: put_unaligned_int32_t,   \
-	         int64_t: put_unaligned_int64_t)(val, (void *)ptr)
+		 int8_t: put_unaligned_int8_t,     \
+		 int16_t: put_unaligned_int16_t,   \
+		 int32_t: put_unaligned_int32_t,   \
+		 int64_t: put_unaligned_int64_t)(val, (void *)ptr)
 
 /**
  * Helper macro for defining an unaligned value reader.
diff --git a/include/kmi/utils.h b/include/kmi/utils.h
index 62d32da..a37f4bb 100644
--- a/include/kmi/utils.h
+++ b/include/kmi/utils.h
@@ -251,18 +251,18 @@
  */
 #define align_down(x, y)                             \
 	_Generic((x), signed char                    \
-	         : align_down_c, signed short        \
-	         : align_down_s, signed int          \
-	         : align_down_i, signed long         \
-	         : align_down_l, signed long long    \
-	         : align_down_ll,                    \
+		 : align_down_c, signed short        \
+		 : align_down_s, signed int          \
+		 : align_down_i, signed long         \
+		 : align_down_l, signed long long    \
+		 : align_down_ll,                    \
                                                      \
-	         unsigned char                       \
-	         : align_down_uc, unsigned short     \
-	         : align_down_us, unsigned int       \
-	         : align_down_ui, unsigned long      \
-	         : align_down_ul, unsigned long long \
-	         : align_down_ull)((x), (y))
+		 unsigned char                       \
+		 : align_down_uc, unsigned short     \
+		 : align_down_us, unsigned int       \
+		 : align_down_ui, unsigned long      \
+		 : align_down_ul, unsigned long long \
+		 : align_down_ull)((x), (y))
 
 /**
  * Helper macro for defining type specific aligning.
@@ -385,18 +385,18 @@ DEFINE_ALIGN_DOWN(ull, unsigned long long);
  */
 #define align_up(x, y)                             \
 	_Generic((x), signed char                  \
-	         : align_up_c, signed short        \
-	         : align_up_s, signed int          \
-	         : align_up_i, signed long         \
-	         : align_up_l, signed long long    \
-	         : align_up_ll,                    \
+		 : align_up_c, signed short        \
+		 : align_up_s, signed int          \
+		 : align_up_i, signed long         \
+		 : align_up_l, signed long long    \
+		 : align_up_ll,                    \
                                                    \
-	         unsigned char                     \
-	         : align_up_uc, unsigned short     \
-	         : align_up_us, unsigned int       \
-	         : align_up_ui, unsigned long      \
-	         : align_up_ul, unsigned long long \
-	         : align_up_ull)((x), (y))
+		 unsigned char                     \
+		 : align_up_uc, unsigned short     \
+		 : align_up_us, unsigned int       \
+		 : align_up_ui, unsigned long      \
+		 : align_up_ul, unsigned long long \
+		 : align_up_ull)((x), (y))
 
 /**
  * Helper macro for defining type specific aligning.
@@ -515,18 +515,18 @@ DEFINE_ALIGN_UP(ull, unsigned long long);
  */
 #define is_aligned(x, y)                             \
 	_Generic((x), signed char                    \
-	         : is_aligned_c, signed short        \
-	         : is_aligned_s, signed int          \
-	         : is_aligned_i, signed long         \
-	         : is_aligned_l, signed long long    \
-	         : is_aligned_ll,                    \
+		 : is_aligned_c, signed short        \
+		 : is_aligned_s, signed int          \
+		 : is_aligned_i, signed long         \
+		 : is_aligned_l, signed long long    \
+		 : is_aligned_ll,                    \
                                                      \
-	         unsigned char                       \
-	         : is_aligned_uc, unsigned short     \
-	         : is_aligned_us, unsigned int       \
-	         : is_aligned_ui, unsigned long      \
-	         : is_aligned_ul, unsigned long long \
-	         : is_aligned_ll)((x), (y))
+		 unsigned char                       \
+		 : is_aligned_uc, unsigned short     \
+		 : is_aligned_us, unsigned int       \
+		 : is_aligned_ui, unsigned long      \
+		 : is_aligned_ul, unsigned long long \
+		 : is_aligned_ll)((x), (y))
 
 /**
  * Helper macro for defining type specific alignment checks.
diff --git a/src/debug.c b/src/debug.c
index 950f73b..d87588d 100644
--- a/src/debug.c
+++ b/src/debug.c
@@ -455,7 +455,7 @@ static size_t __print_sign(ssize_t value, size_t flags)
  * @return \see __integral_val().
  */
 #define __integral_len(value, base, flags) __integral_val((value), (base), \
-	                                                  (flags), false)
+							  (flags), false)
 
 /**
  * Print integral value as string.
@@ -466,7 +466,7 @@ static size_t __print_sign(ssize_t value, size_t flags)
  * @return \see __integral_val().
  */
 #define __integral_print(value, base, flags) __integral_val((value), (base), \
-	                                                    (flags), true)
+							    (flags), true)
 
 /**
  * Print integral value.
diff --git a/src/dmem.c b/src/dmem.c
index 91ddb02..d21a9c5 100644
--- a/src/dmem.c
+++ b/src/dmem.c
@@ -24,8 +24,8 @@ stat_t init_devmem(pm_t ram_base, pm_t ram_top)
 	/* -1 being the effective highest address possible */
 	size_t post_pages = __pages(-1) - ram_pages - pre_pages;
 
-	init_region(&pre_ram, 0, pre_pages);
-	init_region(&post_ram, ram_top, post_pages);
+	init_region(&pre_ram, 0, pre_pages, 0);
+	init_region(&post_ram, ram_top, post_pages, 0);
 	return OK;
 }
 
diff --git a/src/regions.c b/src/regions.c
index ca99971..1aa318d 100644
--- a/src/regions.c
+++ b/src/regions.c
@@ -113,6 +113,8 @@ static struct mem_region *__insert_free_region(struct mem_region_root *r,
 		}
 
 		else if (start < t->start) {
+			/* note that blocks with smaller addresses go to the
+			 * left */
 			n = sp_left(n);
 			d = SP_LEFT;
 		}
@@ -165,7 +167,8 @@ static struct mem_region *__insert_used_region(struct mem_region_root *r,
 	return m;
 }
 
-stat_t init_region(struct mem_region_root *r, vm_t start, size_t arena_size)
+stat_t init_region(struct mem_region_root *r, vm_t start, size_t arena_size,
+                   size_t reserved)
 {
 	/* convert bytes to pages */
 	start = __page(start);
@@ -173,8 +176,11 @@ stat_t init_region(struct mem_region_root *r, vm_t start, size_t arena_size)
 	struct mem_region *m = get_mem_node();
 	m->start = start;
 	m->end = start + arena_size;
-	__insert_free_region(r, m);
 
+	r->reserved = __page(reserved);
+	r->start = m->start;
+	r->end = m->end;
+	__insert_free_region(r, m);
 	return OK;
 }
 
@@ -311,16 +317,45 @@ struct mem_region *find_free_region(struct mem_region_root *r, size_t size,
 	size_t offset = __page(po_align(__addr(size)));
 	struct mem_region *quick_best = 0;
 	struct sp_node *n = sp_root(&r->free_regions);
-	while (n) {
+
+	/* always go right, both to find a larger block and a higher
+	 * address (generally avoid going towards the NULL page) */
+	for (; n; n = sp_right(n)) {
 		struct mem_region *t = mem_container(n);
 		vm_t start = align_up(t->start, offset);
-
 		size_t qsize = t->end - t->start;
 
 		size_t bsize = 0;
 		if (t->end >= start)
 			bsize = t->end - start;
 
+		/* handle reserved region first */
+		if (start < r->start + r->reserved) {
+			/* we would have to map reserved pages, go to next node
+			 * if one exists */
+			if (sp_right(n))
+				continue;
+
+			/* we're the only free region left to check,
+			 * are we large enough to carve a chunk out of? */
+			size_t offset = r->reserved - t->start;
+			if (size < qsize - offset)
+				return quick_best;
+
+			/* we are, so let's set the alignment to match that at
+			 * least some parts of this block should be skipped */
+
+			/* try to use page order alignment if possible */
+			if (size <= bsize - offset) {
+				*align = start - t->start;
+				return t;
+			}
+
+			/* otherwise, carve out a block at the top of this node. */
+			*align = t->end - size;
+			return t;
+		}
+
 		if (!quick_best && size <= qsize)
 			quick_best = t;
 
@@ -328,8 +363,6 @@ struct mem_region *find_free_region(struct mem_region_root *r, size_t size,
 			*align = start - t->start;
 			return t;
 		}
-
-		n = sp_right(n);
 	}
 
 	return quick_best;
diff --git a/src/vmem.c b/src/vmem.c
index 52e7bd2..6fb5474 100644
--- a/src/vmem.c
+++ b/src/vmem.c
@@ -18,19 +18,10 @@ stat_t init_uvmem(struct tcb *t)
 {
 	t->uvmem.owner = t->tid;
 	t->uvmem.vmem = t->proc.vmem;
-
-	stat_t ret = OK;
-	if ((ret = init_region(&t->uvmem.region, UVMEM_START, UVMEM_END)))
-		return ret;
-
-	/* if a user really wants to use the first page for something, they'll
-	 * have to free it first, 'accepting' that no null-page is dangerous. */
-	size_t size = 0;
-	vm_t v = alloc_fixed_region(&t->uvmem.region,
-	                            UVMEM_START, BASE_PAGE_SIZE, &size,
-	                            MR_NONBACKED);
-	assert(v == UVMEM_START && size == BASE_PAGE_SIZE);
-	return OK;
+	/* reserve 64KiB (arbitrary number but should be large enough that
+	 * nobody accidentally indexes above NULL enough to find real memory) */
+	return init_region(&t->uvmem.region, UVMEM_START,
+	                   UVMEM_END - UVMEM_START, SZ_64K);
 }
 
 /**
@@ -132,8 +123,8 @@ static vm_t __clone_shared_region(struct tcb *d, struct tcb *s,
 	if (ERR_CODE(v))
 		return v;
 
-	stat_t res = clone_region(d->uvmem.vmem, s->uvmem.vmem, start, v, size,
-	                          flags);
+	stat_t res = clone_region(d->uvmem.vmem, s->uvmem.vmem,
+	                          start, v, size, flags);
 	if (res == OK)
 		return v;