From 1d2a6f21294f8390b683e4e097cb49210ed832d1 Mon Sep 17 00:00:00 2001 From: johannst Date: Fri, 26 Mar 2021 23:17:46 +0100 Subject: Added dyn allocator + syscall wrappers + minor fixes. --- lib/src/alloc.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/src/fmt.c | 6 ++-- lib/src/syscalls.c | 22 ++++++++++++++ 3 files changed, 112 insertions(+), 3 deletions(-) create mode 100644 lib/src/alloc.c create mode 100644 lib/src/syscalls.c (limited to 'lib/src') diff --git a/lib/src/alloc.c b/lib/src/alloc.c new file mode 100644 index 0000000..8b05d9e --- /dev/null +++ b/lib/src/alloc.c @@ -0,0 +1,87 @@ +// Copyright (c) 2021 Johannes Stoelp + +#include +#include + +#include + +// Extremely simple and non-thread safe implementation of a dynamic +// memory allocator. Which will greatly suffer under fragmentation as +// we neither use splitting nor coalesce free blocks. It uses +// first-fit and always traverses the block list from the beginning. +// +// Bottom line, this allocator can be optimized in so many ways but it +// doesn't really matter for the purpose of this studies and therefore +// the allocator is implemented in the most naive way. + +// Allocation block descriptor. +struct BlockDescriptor { + unsigned mFree; + unsigned mSize; + struct BlockDescriptor* mNext; +}; + +// Global Allocator. + +// Size of available memory to the allocator. +enum { MEMORY_SIZE = 1 * 1024 * 1024 }; +// Memory for the allocator (statically reserved in the `.bss` section). +uint8_t gMemory[MEMORY_SIZE]; + +// Top index into `gMemory` to indicate next free memory. +unsigned gMemoryTop; + +// List of allocated blocks (free + used). +struct BlockDescriptor* gHead; + +// Request free memory from `gMemory` and advance the `gMemoryTop` index. +static void* brk(unsigned size) { + ERROR_ON(gMemoryTop + size >= MEMORY_SIZE, "Allocator OOM!"); + const unsigned old_top = gMemoryTop; + gMemoryTop += size; + return (void*)(gMemory + old_top); +} + +// Allocate memory chunk of `size` and return pointer to the chunk. +void* alloc(unsigned size) { + struct BlockDescriptor* current = 0; + + // Check if we have a free block in the list of allocated blocks + // that matches the requested size. + current = gHead; + while (current) { + if (current->mFree && current->mSize < size) { + current->mFree = 0; + return (void*)(current + 1); + }; + current = current->mNext; + } + + // Compute real allocation size: Payload + BlockDescriptor. + unsigned real_size = size + sizeof(struct BlockDescriptor); + + // No free block found in the list of blocks, allocate new block. + current = brk(real_size); + + // Initialize new block. + current->mFree = 0; + current->mSize = size; + current->mNext = 0; + + // Insert new block at the beginning of the list of blocks. + if (gHead != 0) { + current->mNext = gHead; + } + gHead = current; + + return (void*)(current + 1); +} + +void dealloc(void* ptr) { + // Get descriptor block. + struct BlockDescriptor* current = (struct BlockDescriptor*)ptr - 1; + + // Mark block as free. + ERROR_ON(current->mFree, "Tried to de-alloc free block!"); + current->mFree = 1; +} diff --git a/lib/src/fmt.c b/lib/src/fmt.c index be1ca3a..b0840de 100644 --- a/lib/src/fmt.c +++ b/lib/src/fmt.c @@ -11,7 +11,7 @@ static const char* num2dec(char* buf, unsigned long len, unsigned long long num) } while (num > 0 && pbuf != buf) { - char d = (num % 10) + '0'; + char d = (char)(num % 10) + '0'; *(--pbuf) = d; num /= 10; } @@ -28,7 +28,7 @@ static const char* num2hex(char* buf, unsigned long len, unsigned long long num) while (num > 0 && pbuf != buf) { char d = (num & 0xf); - *(--pbuf) = d + (d > 9 ? 'a' - 10 : '0'); + *(--pbuf) = (char)(d + (d > 9 ? 'a' - 10 : '0')); num >>= 4; } return pbuf; @@ -73,7 +73,7 @@ int vfmt(char* buf, unsigned long len, const char* fmt, va_list ap) { val *= -1; put('-'); } - const char* ptr = num2dec(scratch, sizeof(scratch), val); + const char* ptr = num2dec(scratch, sizeof(scratch), (unsigned long)val); puts(ptr); } break; case 'x': { diff --git a/lib/src/syscalls.c b/lib/src/syscalls.c new file mode 100644 index 0000000..d6ac1a5 --- /dev/null +++ b/lib/src/syscalls.c @@ -0,0 +1,22 @@ +// Copyright (c) 2021 Johannes Stoelp + +#include // __NR_* +#include +#include + +int open(const char* path, int flags) { + return syscall2(__NR_open, path, flags); +} + +ssize_t read(int fd, void* buf, size_t count) { + return syscall3(__NR_read, fd, buf, count); +} + +off_t lseek(int fd, off_t offset, int whence) { + return syscall3(__NR_lseek, fd, offset, whence); +} + +void _exit(int status) { + syscall1(__NR_exit, status); + __builtin_unreachable(); +} -- cgit v1.2.3 From 9b4b10a31954c00813a7cbf9411d30bc84eccea8 Mon Sep 17 00:00:00 2001 From: johannst Date: Sat, 17 Apr 2021 23:38:23 +0200 Subject: add memset --- lib/src/common.c | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+) create mode 100644 lib/src/common.c (limited to 'lib/src') diff --git a/lib/src/common.c b/lib/src/common.c new file mode 100644 index 0000000..2d122f5 --- /dev/null +++ b/lib/src/common.c @@ -0,0 +1,18 @@ +// Copyright (c) 2021 Johannes Stoelp + +#include + +#if !defined(__linux__) || !defined(__x86_64__) +# error "Only supported on linux(x86_64)!" +#endif + +void* memset(void* s, int c, size_t n) { + asm volatile( + "cld" + "\n" + "rep stosb" + : "+D"(s), "+c"(n) + : "a"(c) + : "memory"); + return s; +} -- cgit v1.2.3 From 26088bf37ef85681cf2158fdff82233b1b0c9bfd Mon Sep 17 00:00:00 2001 From: johannst Date: Sat, 17 Apr 2021 23:41:17 +0200 Subject: added close,access,write,pread,mmap,munmap syscalls + syscall ret handler --- lib/src/syscalls.c | 48 ++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 44 insertions(+), 4 deletions(-) (limited to 'lib/src') diff --git a/lib/src/syscalls.c b/lib/src/syscalls.c index d6ac1a5..074fced 100644 --- a/lib/src/syscalls.c +++ b/lib/src/syscalls.c @@ -4,16 +4,56 @@ #include #include +// Storage for `dynld_errno`. +int dynld_errno; + +// Convert return value to errno/ret. +static long syscall_ret(unsigned long ret) { + if (ret > (unsigned long)-4096ul) { + dynld_errno = -ret; + return -1; + } + return ret; +} + int open(const char* path, int flags) { - return syscall2(__NR_open, path, flags); + long ret = syscall2(__NR_open, path, flags); + return syscall_ret(ret); +} + +int close(int fd) { + long ret = syscall1(__NR_close, fd); + return syscall_ret(ret); +} + +int access(const char* path, int mode) { + long ret = syscall2(__NR_access, path, mode); + return syscall_ret(ret); +} + +ssize_t write(int fd, const void* buf, size_t count) { + long ret = syscall3(__NR_write, fd, buf, count); + return syscall_ret(ret); } ssize_t read(int fd, void* buf, size_t count) { - return syscall3(__NR_read, fd, buf, count); + long ret = syscall3(__NR_read, fd, buf, count); + return syscall_ret(ret); +} + +ssize_t pread(int fd, void* buf, size_t count, off_t offset) { + long ret = syscall4(__NR_read, fd, buf, count, offset); + return syscall_ret(ret); +} + +void* mmap(void* addr, size_t length, int prot, int flags, int fd, off_t offset) { + long ret = syscall6(__NR_mmap, addr, length, prot, flags, fd, offset); + return (void*)syscall_ret(ret); } -off_t lseek(int fd, off_t offset, int whence) { - return syscall3(__NR_lseek, fd, offset, whence); +int munmap(void* addr, size_t length) { + long ret = syscall2(__NR_munmap, addr, length); + return syscall_ret(ret); } void _exit(int status) { -- cgit v1.2.3 From 1bcaa7aceefad99c7bda9cb7bf6fcc5b48b53a75 Mon Sep 17 00:00:00 2001 From: johannst Date: Sat, 17 Apr 2021 23:41:52 +0200 Subject: fmt: add support for %c --- lib/src/fmt.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) (limited to 'lib/src') diff --git a/lib/src/fmt.c b/lib/src/fmt.c index b0840de..56d95ed 100644 --- a/lib/src/fmt.c +++ b/lib/src/fmt.c @@ -11,7 +11,7 @@ static const char* num2dec(char* buf, unsigned long len, unsigned long long num) } while (num > 0 && pbuf != buf) { - char d = (char)(num % 10) + '0'; + char d = (char)(num % 10) + '0'; *(--pbuf) = d; num /= 10; } @@ -81,6 +81,10 @@ int vfmt(char* buf, unsigned long len, const char* fmt, va_list ap) { const char* ptr = num2hex(scratch, sizeof(scratch), val); puts(ptr); } break; + case 'c': { + char c = va_arg(ap, int); // By C standard, value passed to varg smaller than `sizeof(int)` will be converted to int. + put(c); + } break; case 's': { const char* ptr = va_arg(ap, const char*); puts(ptr); -- cgit v1.2.3 From b3f93e87f773c0e9099f256c78c1485fd7ce1dce Mon Sep 17 00:00:00 2001 From: johannst Date: Sat, 17 Apr 2021 23:42:18 +0200 Subject: io: make use of write syscall wrapper --- lib/src/io.c | 11 +++++------ 1 file changed, 5 insertions(+), 6 deletions(-) (limited to 'lib/src') diff --git a/lib/src/io.c b/lib/src/io.c index b5e0dc5..5194042 100644 --- a/lib/src/io.c +++ b/lib/src/io.c @@ -1,10 +1,9 @@ // Copyright (c) 2020 Johannes Stoelp -#include #include +#include #include - -#include +#include // `pfmt` uses fixed-size buffer on the stack for formating the message // (for simplicity and since we don't impl buffered I/O). @@ -21,14 +20,14 @@ static int vdfmt(int fd, const char* fmt, va_list ap) { int ret = vfmt(buf, sizeof(buf), fmt, ap); if (ret > MAX_PRINTF_LEN - 1) { - syscall3(__NR_write, fd, buf, MAX_PRINTF_LEN - 1); + write(fd, buf, MAX_PRINTF_LEN - 1); static const char warn[] = "\npfmt: Message truncated, max length can be configured by defining MAX_PRINTF_LEN\n"; - syscall3(__NR_write, FD_STDERR, warn, sizeof(warn)); + write(FD_STDERR, warn, sizeof(warn)); return MAX_PRINTF_LEN - 1; } - syscall3(__NR_write, fd, buf, ret); + write(fd, buf, ret); return ret; } -- cgit v1.2.3 From 3155439c1a96f1964aaee799b008331d0b362db3 Mon Sep 17 00:00:00 2001 From: johannst Date: Mon, 19 Apr 2021 21:50:29 +0200 Subject: added tests for fmt() char, long nums --- lib/src/fmt.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/src') diff --git a/lib/src/fmt.c b/lib/src/fmt.c index 56d95ed..24ddd98 100644 --- a/lib/src/fmt.c +++ b/lib/src/fmt.c @@ -51,7 +51,7 @@ int vfmt(char* buf, unsigned long len, const char* fmt, va_list ap) { put(*s++); \ } - char scratch[16]; + char scratch[32]; int l_cnt = 0; while (*fmt) { -- cgit v1.2.3 From 1df4dfdcdbbaef7e5b32c5c0bfadec02b3ccd6f0 Mon Sep 17 00:00:00 2001 From: johannst Date: Tue, 20 Apr 2021 22:05:13 +0200 Subject: added memcpy + tests for memcpy/memset --- lib/src/common.c | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) (limited to 'lib/src') diff --git a/lib/src/common.c b/lib/src/common.c index 2d122f5..dd806bf 100644 --- a/lib/src/common.c +++ b/lib/src/common.c @@ -16,3 +16,23 @@ void* memset(void* s, int c, size_t n) { : "memory"); return s; } + +void* memcpy(void* d, const void* s, size_t n) { + // When `d` points into `[s, s+n[` we would override `s` while copying into `d`. + // |------------|--------| + // s d s+n + // -> We don't support. + // + // When `d` points into `]s-n, s[` it is destructive for `s` but all data + // from `s` are copied into `d`. The user gets what he asks for. + // -> Supported. + ERROR_ON(s <= d && d < (void*)((unsigned char*)s + n), "memcpy: Unsupported overlap!"); + asm volatile( + "cld" + "\n" + "rep movsb" + : "+D"(d), "+S"(s), "+c"(n) + : + : "memory"); + return d; +} -- cgit v1.2.3