commit ab0a5e34b758bb026ecb3d99b2c6c6819db9e9bd
parent 84d735c2b36ffea65a2e1f28a2f62abe7ae66af6
Author: Yersa Nordman <finwo@pm.me>
Date: Wed, 17 Jun 2020 11:35:19 +0200
Based malloc on sbrk now
Diffstat:
10 files changed, 164 insertions(+), 286 deletions(-)
diff --git a/Makefile b/Makefile
@@ -2,12 +2,13 @@ TARGET ?= wasm32
include arch/$(TARGET)/config.mk
-SRC=$(shell find -L arch/$(TARGET)/src -type f -name *.c)
-SRC+=$(shell find -L src -type f -name *.c)
+SRC=$(shell find -L arch/$(TARGET)/src -type f -name \*.c)
+SRC+=$(shell find -L src -type f -name \*.c)
OBJ=$(SRC:.c=.o)
libmatter.a: $(OBJ)
- $(AR) -cvq libmatter.a $(OBJ)
+ rm -f $@
+ $(AR) -cvq $@ $(OBJ)
%.o: %.c
$(LLE) -Ofast -S $(CFLAGS) -nostdinc -fno-builtin -Iinclude -Iarch/$(TARGET)/include -c $< -o $(@:.o=.ll)
diff --git a/arch/wasm32/src/malloc/malloc.c b/arch/wasm32/src/malloc/malloc.c
@@ -1,105 +0,0 @@
-#ifndef _MALLOC_C_
-#define _MALLOC_C_
-
-#include <malloc.h>
-#include <stddef.h>
-#include <string.h>
-
-extern unsigned char __heap_base;
-
-unsigned char *bump_pointer = &__heap_base;
-
-unsigned char *heap_start = &__heap_base;
-unsigned char *heap_end = &__heap_base;
-unsigned int isize = sizeof(unsigned int);
-unsigned int hsize = (2 * sizeof(unsigned int));
-
-// TODO: realloc
-// TODO: free
-
-void * malloc(size_t n) {
- unsigned char *r = heap_start;
-
- unsigned int *size = NULL;
- unsigned int *used = NULL;
-
- // Loop through known blocks
- while(r < heap_end) {
- size = (void*)r;
- used = (void*)(r+isize);
-
- // In-use = skip
- if (*used) {
- r += *size;
- continue;
- }
-
- // Too small = skip
- if ((*size) < (n + hsize)) {
- r += *size;
- continue;
- }
-
- // Take this block
- *used = n;
- return (void*)(r + hsize);
- }
-
- // Something went wrong
- if (r < heap_end) {
- return NULL;
- }
-
- // Build a new block
- size = (void*)r;
- used = (void*)(r+isize);
- *size = n + hsize;
- *used = n;
- heap_end = r + n + hsize;
- return (void*)(r + hsize);
-}
-
-void free(void *p) {
- unsigned int *used = p - isize;
- *used = 0;
-}
-
-void *calloc(size_t num, size_t nsize)
-{
- size_t size;
- void *block;
- if (!num || !nsize)
- return NULL;
- size = num * nsize;
- /* check mul overflow */
- if (nsize != size / num)
- return NULL;
- block = malloc(size);
- if (!block)
- return NULL;
- memset(block, 0, size);
- return block;
-}
-
-void *realloc(void *block, size_t size)
-{
- void *ret;
- size_t original_size = (size_t)(((char*)block) - hsize);
-
- if (!block || !size)
- return malloc(size);
-
- if (size <= (size_t)(((char*)block) - hsize)) {
- return block;
- }
-
- ret = malloc(size);
- if (ret) {
- memcpy(ret, block, original_size);
- free(block);
- }
-
- return ret;
-}
-
-#endif // _MALLOC_C_
diff --git a/arch/wasm32/src/unistd/brk.c b/arch/wasm32/src/unistd/brk.c
@@ -0,0 +1,20 @@
+#ifndef _UNISTD_BRK_C_
+#define _UNISTD_BRK_C_
+
+#include <unistd.h>
+
+extern unsigned char __heap_base;
+void *break_pointer = &__heap_base;
+
+int brk(void *addr) {
+ break_pointer = addr;
+ return 0;
+}
+
+void * sbrk(ssize_t increment) {
+ void *ret = break_pointer;
+ break_pointer += increment;
+ return ret;
+}
+
+#endif // _UNISTD_BRK_C_
diff --git a/include/limits.h b/include/limits.h
@@ -1,86 +0,0 @@
-#ifndef _LIMITS_H_
-#define _LIMITS_H_
-
-#ifndef __SCHAR_MAX__
-#define __SCHAR_MAX__ 0x7f
-#endif
-#ifndef __SHRT_MAX__
-#define __SHRT_MAX__ 0x7fff
-#endif
-#ifndef __INT_MAX__
-#define __INT_MAX__ 0x7fffffff
-#endif
-#ifndef __LONG_MAX__
-#if __WORDSIZE == 64
-#define __LONG_MAX__ 0x7fffffffffffffffL
-#else
-#define __LONG_MAX__ 0x7fffffffL
-#endif
-#endif
-
-#define CHAR_BIT 8
-
-#define SCHAR_MIN (-1 - SCHAR_MAX)
-#define SCHAR_MAX (__SCHAR_MAX__)
-#define UCHAR_MAX (SCHAR_MAX * 2 + 1)
-
-#ifdef __CHAR_UNSIGNED__
-#undef CHAR_MIN
-#define CHAR_MIN 0
-#undef CHAR_MAX
-#define CHAR_MAX UCHAR_MAX
-#else
-#undef CHAR_MIN
-#define CHAR_MIN SCHAR_MIN
-#undef CHAR_MAX
-#define CHAR_MAX SCHAR_MAX
-#endif
-
-#define SHRT_MIN (-1 - SHRT_MAX)
-#define SHRT_MAX (__SHRT_MAX__)
-#define USHRT_MAX (SHRT_MAX * 2 + 1)
-
-#define INT_MIN (-1 - INT_MAX)
-#define INT_MAX (__INT_MAX__)
-#define UINT_MAX (INT_MAX * 2U + 1)
-
-#define LONG_MIN (-1L - LONG_MAX)
-#define LONG_MAX (__LONG_MAX__)
-#define ULONG_MAX (LONG_MAX * 2UL + 1)
-
-#define LLONG_MAX 0x7fffffffffffffffLL
-#define LLONG_MIN (-1LL - LLONG_MAX)
-
-/* Maximum value an `unsigned long long int' can hold. (Minimum is 0.) */
-#define ULLONG_MAX (~0ULL)
-
-#define SSIZE_MIN LONG_MIN
-#define SSIZE_MAX LONG_MAX
-
-#define PASS_MAX 256
-
-#define NR_OPEN 1024
-
-#define NGROUPS_MAX 32 /* supplemental group IDs are available */
-#define ARG_MAX 131072 /* # bytes of args + environ for exec() */
-#define CHILD_MAX 999 /* no limit :-) */
-#define OPEN_MAX 256 /* # open files a process may have */
-#define LINK_MAX 127 /* # links a file may have */
-#define MAX_CANON 255 /* size of the canonical input queue */
-#define MAX_INPUT 255 /* size of the type-ahead buffer */
-#define NAME_MAX 255 /* # chars in a file name */
-#define PATH_MAX 4095 /* # chars in a path name */
-#define PIPE_BUF 4096 /* # bytes in atomic write to a pipe */
-
-#define RTSIG_MAX 32
-
-#define LINE_MAX 2048
-
-#define _POSIX_PATH_MAX PATH_MAX
-#define MB_LEN_MAX 16
-
-#ifdef _XOPEN_SOURCE
-#define IOV_MAX 1024
-#endif
-
-#endif // _LIMITS_H_
diff --git a/include/malloc.h b/include/malloc.h
@@ -3,7 +3,9 @@
#include <stddef.h>
-void * malloc(size_t n);
+void *malloc(size_t n);
void free(void *p);
+void *realloc(void *ptr, size_t size);
+void *calloc(size_t nelem, size_t elsize);
#endif // _MALLOC_H_
diff --git a/include/stddef.h b/include/stddef.h
@@ -8,5 +8,6 @@
#endif
typedef unsigned long size_t;
+typedef signed long ssize_t;
#endif // _STDDEF_H_
diff --git a/include/stdint.h b/include/stdint.h
@@ -1,89 +0,0 @@
-#ifndef _STDINT_H_
-#define _STDINT_H_
-
-#include <limits.h>
-
-/* (u)int8_t */
-#if (UINT_MAX == 0xffU)
- typedef unsigned int uint8_t;
- typedef signed int int8_t;
-#elif (USHRT_MAX == 0xffU)
- typedef unsigned short uint8_t;
- typedef signed short int8_t;
-#elif (UCHAR_MAX == 0xffU)
- typedef unsigned char uint8_t;
- typedef signed char int8_t;
-#endif
-
-/* (u)int16_t */
-#if (UINT_MAX == 0xffffU)
- typedef unsigned int uint16_t;
- typedef signed int int16_t;
-#elif (USHRT_MAX == 0xffffU)
- typedef unsigned short uint16_t;
- typedef signed short int16_t;
-#endif
-
-/* (u)int32_t */
-#if (ULONG_MAX == 0xffffffffUL)
- typedef unsigned long uint32_t;
- typedef signed long int32_t;
-#elif (UINT_MAX == 0xffffffffUL)
- typedef unsigned int uint32_t;
- typedef signed int int32_t;
-#elif (USHRT_MAX == 0xffffffffUL)
- typedef unsigned short uint32_t;
- typedef signed short int32_t;
-#endif
-
-/* (u)int64_t */
-#if (ULLONG_MAX == 0xffffffffffffffffULL)
- typedef unsigned long long uint64_t;
- typedef signed long long int64_t;
-#elif (ULONG_MAX == 0xffffffffffffffffULL)
- typedef unsigned long uint64_t;
- typedef signed long int64_t;
-#elif (UINT_MAX == 0xffffffffffffffffULL)
- typedef unsigned int uint64_t;
- typedef signed int int64_t;
-#elif (USHRT_MAX == 0xffffffffffffffffULL)
- typedef unsigned short uint64_t;
- typedef signed short int64_t;
-#endif
-
-/* The ISO C99 standard specifies that in C++ implementations these
- should only be defined if explicitly requested. */
-#if !defined __cplusplus || defined __STDC_CONSTANT_MACROS
-
-/* Signed. */
-# define INT8_C(c) c
-# define INT16_C(c) c
-# define INT32_C(c) c
-# if __WORDSIZE == 64
-# define INT64_C(c) c ## L
-# else
-# define INT64_C(c) c ## LL
-# endif
-
-/* Unsigned. */
-# define UINT8_C(c) c
-# define UINT16_C(c) c
-# define UINT32_C(c) c ## U
-# if __WORDSIZE == 64
-# define UINT64_C(c) c ## UL
-# else
-# define UINT64_C(c) c ## ULL
-# endif
-
-/* Maximal type. */
-# if __WORDSIZE == 64
-# define INTMAX_C(c) c ## L
-# define UINTMAX_C(c) c ## UL
-# else
-# define INTMAX_C(c) c ## LL
-# define UINTMAX_C(c) c ## ULL
-# endif
-
-#endif /* C++ && constant macros */
-
-#endif // _STDINT_H_
diff --git a/include/string.h b/include/string.h
@@ -4,7 +4,7 @@
#include <stddef.h>
int memcmp (const void *str1, const void *str2, int count);
-void * memcpy (void *dest, const void *src, size_t len);
-void * memset (void *dest, int val, size_t len);
+void *memcpy (void *dest, const void *src, size_t len);
+void *memset (void *dest, int val, size_t len);
#endif // _STRING_H_
diff --git a/include/unistd.h b/include/unistd.h
@@ -0,0 +1,9 @@
+#ifndef _UNISTD_H_
+#define _UNISTD_H_
+
+#include <stddef.h>
+
+int brk(void *addr);
+void *sbrk(ssize_t increment);
+
+#endif // _UNISTD_H_
diff --git a/src/malloc/malloc.c b/src/malloc/malloc.c
@@ -0,0 +1,125 @@
+#ifndef _MALLOC_C_
+#define _MALLOC_C_
+
+#include <malloc.h>
+#include <string.h>
+#include <unistd.h>
+
+// Implementation copied from https://danluu.com/malloc-tutorial/
+
+struct block_meta {
+ size_t size;
+ struct block_meta *next;
+ int free;
+};
+
+#define META_SIZE sizeof(struct block_meta)
+
+void *global_base = NULL;
+
+struct block_meta *find_free_block(struct block_meta **last, size_t size) {
+ struct block_meta *current = global_base;
+ while (current && !(current->free && current->size >= size)) {
+ *last = current;
+ current = current->next;
+ }
+ return current;
+}
+
+struct block_meta *request_space(struct block_meta* last, size_t size) {
+ struct block_meta *block;
+ block = sbrk(0);
+ void *request = sbrk(size + META_SIZE);
+ // assert((void*)block == request); // Not thread safe.
+ if (request == (void*) -1) {
+ return NULL; // sbrk failed.
+ }
+
+ if (last) { // NULL on first request.
+ last->next = block;
+ }
+ block->size = size;
+ block->next = NULL;
+ block->free = 0;
+ return block;
+}
+
+
+void *malloc(size_t size) {
+ struct block_meta *block;
+ // TODO: align size?
+
+ if (size <= 0) {
+ return NULL;
+ }
+
+ if (!global_base) { // First call.
+ block = request_space(NULL, size);
+ if (!block) {
+ return NULL;
+ }
+ global_base = block;
+ } else {
+ struct block_meta *last = global_base;
+ block = find_free_block(&last, size);
+ if (!block) { // Failed to find free block.
+ block = request_space(last, size);
+ if (!block) {
+ return NULL;
+ }
+ } else { // Found free block
+ // TODO: consider splitting block here.
+ block->free = 0;
+ }
+ }
+
+ return(block+1);
+}
+
+struct block_meta *get_block_ptr(void *ptr) {
+ return (struct block_meta*)ptr - 1;
+}
+
+void free(void *ptr) {
+ if (!ptr) {
+ return;
+ }
+
+ // TODO: consider merging blocks once splitting blocks is implemented.
+ struct block_meta* block_ptr = get_block_ptr(ptr);
+ // assert(block_ptr->free == 0);
+ block_ptr->free = 1;
+}
+
+void *realloc(void *ptr, size_t size) {
+ if (!ptr) {
+ // NULL ptr. realloc should act like malloc.
+ return malloc(size);
+ }
+
+ struct block_meta* block_ptr = get_block_ptr(ptr);
+ if (block_ptr->size >= size) {
+ // We have enough space. Could free some once we implement split.
+ return ptr;
+ }
+
+ // Need to really realloc. Malloc new space and free old space.
+ // Then copy old data to new space.
+ void *new_ptr;
+ new_ptr = malloc(size);
+ if (!new_ptr) {
+ return NULL; // TODO: set errno on failure.
+ }
+ memcpy(new_ptr, ptr, block_ptr->size);
+ free(ptr);
+ return new_ptr;
+}
+
+void *calloc(size_t nelem, size_t elsize) {
+ size_t size = nelem * elsize; // TODO: check for overflow.
+ void *ptr = malloc(size);
+ memset(ptr, 0, size);
+ return ptr;
+}
+
+#endif // _MALLOC_C_
