Added some C11 atomic operations

Mainly to be used in spinlocks etc.

7 files changed, 295 insertions, 1 deletions

diff --git a/Makefile b/Makefile
index 9e1b5d3..2a388e8 100644
--- a/Makefile
+++ b/Makefile
@@ -1,7 +1,7 @@
 DO		!= echo > deps.mk
 
 # this could be done better
-DEBUGFLAGS	!= [ $(DEBUG) ] && echo "-O0 -ggdb3 -DDEBUG" || echo "-flto -O2"
+DEBUGFLAGS	!= [ $(RELEASE) ] && echo "-flto -O2" || echo "-O0 -ggdb3 -DDEBUG"
 CFLAGS		= -fno-pie -ffreestanding -nostdlib -std=c17 -Wall -Wextra
 DEPFLAGS	= -MT $@ -MMD -MP -MF $@.d
 
diff --git a/TODO.txt b/TODO.txt
index 29252d0..3691a68 100644
--- a/TODO.txt
+++ b/TODO.txt
@@ -18,3 +18,5 @@ init from vmem when jumping to vmem
 + should probably come up with some kind of general error handling scheme?
 
 + Fix unmap/map_vmem when called from virtual memory
+
++ Investigate GCC/Clang builtin atomic operations?
diff --git a/arch/riscv/include/lock.h b/arch/riscv/include/lock.h
new file mode 100644
index 0000000..4f71344
--- /dev/null
+++ b/arch/riscv/include/lock.h
@@ -0,0 +1 @@
+#define optional_pause()
diff --git a/arch/riscv/kernel/main.c b/arch/riscv/kernel/main.c
index 207b0bc..aaf828c 100644
--- a/arch/riscv/kernel/main.c
+++ b/arch/riscv/kernel/main.c
@@ -2,6 +2,7 @@
 #include <apos/init.h>
 #include <apos/vmem.h>
 #include <apos/mem.h>
+#include <apos/lock.h>
 
 #ifdef DEBUG
 
diff --git a/arch/riscv/mm.txt b/arch/riscv/mm.txt
new file mode 100644
index 0000000..fa06180
--- /dev/null
+++ b/arch/riscv/mm.txt
@@ -0,0 +1,83 @@
+Ideas for actually working virtual mappings:
+
+1. Define sensible memory areas, to start with for Sv39 and then that can
+probably be extended to Sv48 etc.
+
+Something like this for Sv39:
+
+Offset		| Size		| Purpose
+------------------------------------------------
+-242 GiB	| 256 GiB	| Userspace
+------------------------------------------------
+-246 GiB	| 4 GiB		| Direct mapping
+-254 GiB	| 8 GiB		| vmemmap
+-255 GiB	| 1 GiB		| Kernel IO
+-256 GiB	| 1 GiB		| Kernel
+
+Sv48:
+
+Offset		| Size		| Purpose
+------------------------------------------------
+-58368 GiB	| 65536 GiB	| Userspace
+------------------------------------------------
+-60416 GiB	| 2048 GiB	| Direct mapping
+-64512 GiB	| 4096 GiB	| vmemmap
+-65024 GiB	| 512 GiB	| Kernel IO
+-65536 GiB	| 512 GiB	| Kernel
+
+Note that tera/giga/etc pages have to be aligned to their corresponding size.
+This means that these areas will probably have to be mapped with 2M pages, which
+is fine but would've been cool to use top-level PTE's to keep context switch
+latencies down.
+
+(Note: Direct mapping can be something like
+ inline static __va(pm_t pa)
+ {
+	if (__dma_bottom >= pa || __dma_top <= pa)
+		remap_dma(pa);
+	return pa + __dma_bottom;
+ }
+ ...)
+
+PTE's can be kept in vmemmap, and the Direct mapping can overlap.
+
+2. Come up with a somewhat sensible virtual memory management system. Linux uses
+rb_trees, which might be a good idea, although I should figure out how to handle
+both acuiring and freeing them quickly.
+
+Maybe keep two separate trees, one for free and one for mapped regions? Free
+regions should be ordered by size, to quickly find the best suitable size.
+Used/mapped regions should be ordered by address, to quickly find the correct
+region.
+
+struct rb_free_node {
+	union {
+		size_t size;
+		vm_t address;
+	};
+
+	struct rb_free_node *pair;
+	struct rb_free_node *left;
+	struct rb_free_node *right;
+};
+
+struct rb_used_node {
+	vm_t address;
+	size_t size;
+
+	struct rb_used_node *left;
+	struct rb_used_node *right;
+};
+
+My idea: Have two trees made of rb_free_node, one ordered by size and one
+ordered by address, with the *pair pointer pointing to the corresponding node in
+the other tree.
+
+When allocating, search up the most suitable free area in the tree ordered by
+size, and do the required node modifications.
+(remove node completely, split area one or twice, mirror in other tree)
+
+When freeing, search up the address in the used area, after which insert it into
+the free trees and remove it from the used tree. After that, merge adjacent
+memory areas in the free trees? Could be done reasonably efficiently, should
+start up a test implementation, like with pmem.
diff --git a/include/apos/atomic.h b/include/apos/atomic.h
new file mode 100644
index 0000000..1b92100
--- /dev/null
+++ b/include/apos/atomic.h
@@ -0,0 +1,184 @@
+#ifndef ATOMIC_H
+#define ATOMIC_H
+
+#include <apos/utils.h> /* GLUE */
+
+typedef enum
+{
+	memory_order_relaxed = __ATOMIC_RELAXED,
+	memory_order_consume = __ATOMIC_CONSUME,
+	memory_order_acquire = __ATOMIC_ACQUIRE,
+	memory_order_release = __ATOMIC_RELEASE,
+	memory_order_acq_rel = __ATOMIC_ACQ_REL,
+	memory_order_seq_cst = __ATOMIC_SEQ_CST
+} memory_order;
+
+typedef _Atomic _Bool atomic_bool;
+typedef _Atomic char atomic_char;
+typedef _Atomic signed char atomic_schar;
+typedef _Atomic unsigned char atomic_uchar;
+typedef _Atomic short atomic_short;
+typedef _Atomic unsigned short atomic_ushort;
+typedef _Atomic int atomic_int;
+typedef _Atomic unsigned int atomic_uint;
+typedef _Atomic long atomic_long;
+typedef _Atomic unsigned long atomic_ulong;
+typedef _Atomic long long atomic_llong;
+typedef _Atomic unsigned long long atomic_ullong;
+typedef _Atomic __CHAR16_TYPE__ atomic_char16_t;
+typedef _Atomic __CHAR32_TYPE__ atomic_char32_t;
+typedef _Atomic __WCHAR_TYPE__ atomic_wchar_t;
+typedef _Atomic __INT_LEAST8_TYPE__ atomic_int_least8_t;
+typedef _Atomic __UINT_LEAST8_TYPE__ atomic_uint_least8_t;
+typedef _Atomic __INT_LEAST16_TYPE__ atomic_int_least16_t;
+typedef _Atomic __UINT_LEAST16_TYPE__ atomic_uint_least16_t;
+typedef _Atomic __INT_LEAST32_TYPE__ atomic_int_least32_t;
+typedef _Atomic __UINT_LEAST32_TYPE__ atomic_uint_least32_t;
+typedef _Atomic __INT_LEAST64_TYPE__ atomic_int_least64_t;
+typedef _Atomic __UINT_LEAST64_TYPE__ atomic_uint_least64_t;
+typedef _Atomic __INT_FAST8_TYPE__ atomic_int_fast8_t;
+typedef _Atomic __UINT_FAST8_TYPE__ atomic_uint_fast8_t;
+typedef _Atomic __INT_FAST16_TYPE__ atomic_int_fast16_t;
+typedef _Atomic __UINT_FAST16_TYPE__ atomic_uint_fast16_t;
+typedef _Atomic __INT_FAST32_TYPE__ atomic_int_fast32_t;
+typedef _Atomic __UINT_FAST32_TYPE__ atomic_uint_fast32_t;
+typedef _Atomic __INT_FAST64_TYPE__ atomic_int_fast64_t;
+typedef _Atomic __UINT_FAST64_TYPE__ atomic_uint_fast64_t;
+typedef _Atomic __INTPTR_TYPE__ atomic_intptr_t;
+typedef _Atomic __UINTPTR_TYPE__ atomic_uintptr_t;
+typedef _Atomic __SIZE_TYPE__ atomic_size_t;
+typedef _Atomic __PTRDIFF_TYPE__ atomic_ptrdiff_t;
+typedef _Atomic __INTMAX_TYPE__ atomic_intmax_t;
+typedef _Atomic __UINTMAX_TYPE__ atomic_uintmax_t;
+
+#define ATOMIC_VAR_INIT(VALUE) (VALUE)
+#define atomic_init(PTR, VAL)\
+	atomic_store_explicit(PTR, VAL, __ATOMIC_RELAXED)
+
+#define kill_dependency(y) (y)
+
+#if defined(__GNUC__)
+#define CMPLR_LOCK_FREE(x) GLUE(__GCC_ATOMIC_, x)##_LOCK_FREE
+#elif defined(__clang__)
+#define CMPLR_LOCK_FREE(x) GLUE(__CLANG_ATOMIC_, x)##_LOCK_FREE
+#endif
+
+#define ATOMIC_BOOL_LOCK_FREE CMPLR_LOCK_FREE(BOOL)
+#define ATOMIC_CHAR_LOCK_FREE CMPLR_LOCK_FREE(CHAR)
+#define ATOMIC_CHAR16_T_LOCK_FREE CMPLR_LOCK_FREE(CHAR16_T)
+#define ATOMIC_CHAR32_T_LOCK_FREE CMPLR_LOCK_FREE(CHAR32_T)
+#define ATOMIC_WCHAR_T_LOCK_FREE CMPLR_LOCK_FREE(WCHAR32_T)
+#define ATOMIC_SHORT_LOCK_FREE CMPLR_LOCK_FREE(SHORT)
+#define ATOMIC_INT_LOCK_FREE CMPLR_LOCK_FREE(INT)
+#define ATOMIC_LONG_LOCK_FREE CMPLR_LOCK_FREE(LONG)
+#define ATOMIC_LLONG_LOCK_FREE CMPLR_LOCK_FREE(LLONG)
+#define ATOMIC_POINTER_LOCK_FREE CMPLR_LOCK_FREE(POINTER)
+
+#if defined(__GNUC__)
+#define C11_ATOMIC(x) GLUE(__atomic_, x)
+#elif defined(__clang__)
+#define C11_ATOMIC(x) GLUE(__c11_atomic_, x)
+#endif
+
+/* no libc, so fences aren't used here (unless implemented, but I don't see that
+ * to be necessary)
+ *
+ * void atomic_thread_fence(memory_order);
+ * void atomic_signal_fence(memory_order);
+ */
+
+#define atomic_thread_fence(order) C11_ATOMIC(thread_fence)(order)
+#define atomic_signal_fence(order) C11_ATOMIC(signal_fence)(order)
+
+#if defined(__GNUC__)
+#define atomic_is_lock_free(obj) C11_ATOMIC(is_lock_free)(sizeof(*(obj)), (obj))
+#elif defined(__clang__)
+#define atomic_is_lock_free(obj) C11_ATOMIC(is_lock_free)(sizeof(*(obj)))
+#endif
+
+#if defined(__GNUC__)
+#define N_ATOMIC(x) GLUE(C11_ATOMIC(x), _n)
+#elif defined(__clang__)
+#define N_ATOMIC(x) C11_ATOMIC(x)
+#endif
+
+#define atomic_store_explicit(obj, val, mode)\
+	N_ATOMIC(store)(obj, val, mode)
+
+#define atomic_store(obj, val)\
+	atomic_store_explicit(obj, val, __ATOMIC_SEQ_CST);
+
+#define atomic_load_explicit(obj, mode)\
+	N_ATOMIC(load)(obj, mode)
+
+#define atomic_load(obj)\
+	atomic_load_explicit(obj, ATOMIC_SEQ_CST)
+
+#define atomic_exchange_explicit(obj, val, mode)\
+	N_ATOMIC(exchange)(obj, val, mode)
+
+#define atomic_exchange(obj, val)\
+	atomic_exchange_explicit(obj, val, __ATOMIC_SEQ_CST)
+
+#if defined(__GNUC__)
+#define atomic_compare_exchange_strong_explicit(obj, val, des, suc, fail)\
+	N_ATOMIC(compare_exchange)(obj, val, des, 0, suc, fail)
+#elif defined(__clang__)
+#define atomic_compare_exchange_strong_explicit(obj, val, des, suc, fail)\
+	N_ATOMIC(compare_exchange_strong)(obj, val, des, suc, fail)
+#endif
+
+#define atomic_compare_exchange_strong(obj, val, des)\
+	atomic_compare_exchange_strong_explicit\
+	(obj, val, des, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)
+
+#if defined(__GNUC__)
+#define atomic_compare_exchange_weak_explicit(obj, val, des, suc, fail)\
+	N_ATOMIC(compare_exchange)(obj, val, des, 1, suc, fail)
+#elif defined(__clang__)
+#define atomic_compare_exchange_weak_explicit(obj, val, des, suc, fail)\
+	N_ATOMIC(compare_exchange_weak)(obj, val, des, suc, fail)
+#endif
+
+#define atomic_compare_exchange_weak(obj, val, des)\
+	atomic_compare_exchange_weak_explicit\
+	(obj, val, des, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)
+
+#define atomic_fetch_add_explicit(obj, val, mode)\
+	C11_ATOMIC(fetch_add)(obj, val, mode)
+
+#define atomic_fetch_add(obj, val)\
+	atomic_fetch_add_explicit(obj, val, __ATOMIC_SEQ_CST)
+
+#define atomic_fetch_sub_explicit(obj, val, mode)\
+	C11_ATOMIC(fetch_sub)(obj, val, mode)
+
+#define atomic_fetch_sub(obj, val)\
+	atomic_fetch_sub_explicit(obj, val, __ATOMIC_SEQ_CST)
+
+#define atomic_fetch_and_explicit(obj, val, mode)\
+	C11_ATOMIC(fetch_and)(obj, val, mode)
+
+#define atomic_fetch_and(obj, val)\
+	atomic_fetch_and_explicit(obj, val, __ATOMIC_SEQ_CST)
+
+#define atomic_fetch_xor_explicit(obj, val, mode)\
+	C11_ATOMIC(fetch_xor)(obj, val, mode)
+
+#define atomic_fetch_xor(obj, val)\
+	atomic_fetch_xor_explicit(obj, val, __ATOMIC_SEQ_CST)
+
+#define atomic_fetch_or_explicit(obj, val, mode)\
+	C11_ATOMIC(fetch_or)(obj, val, mode)
+
+#define atomic_fetch_or(obj, val)\
+	atomic_fetch_or_explicit(obj, val, __ATOMIC_SEQ_CST)
+
+#define atomic_fetch_nand_explicit(obj, val, mode)\
+	C11_ATOMIC(fetch_nand)(obj, val, mode)
+
+#define atomic_fetch_nand(obj, val)\
+	atomic_fetch_nand_explicit(obj, val, __ATOMIC_SEQ_CST)
+
+/* skip atomic flags, probably not needed */
+#endif /* ATOMIC_H */
diff --git a/include/apos/lock.h b/include/apos/lock.h
new file mode 100644
index 0000000..b8983fa
--- /dev/null
+++ b/include/apos/lock.h
@@ -0,0 +1,23 @@
+#ifndef LOCK_H
+#define LOCK_H
+
+#include <apos/atomic.h>
+typedef atomic_int spinlock_t;
+
+#include <lock.h>
+
+static inline void spin_lock(spinlock_t *lck)
+{
+	do {
+		while (atomic_load_explicit(lck, memory_order_acquire))
+			optional_pause();
+
+	} while (atomic_exchange_explicit(lck, 1, memory_order_acq_rel));
+}
+
+static inline void spin_unlock(spinlock_t *lck)
+{
+	atomic_store_explicit(lck, 0, memory_order_release);
+}
+
+#endif /* LOCK_H */