diff options
| -rw-r--r-- | 02-usart/Makefile.preamble | 2 | ||||
| -rw-r--r-- | 02-usart/include/arch/arm/arch.h | 3 | ||||
| -rw-r--r-- | 02-usart/include/arch/x86_64/arch.h | 6 | ||||
| -rw-r--r-- | 02-usart/include/mem.h | 23 | ||||
| -rw-r--r-- | 02-usart/src/mem.c | 195 | ||||
| -rw-r--r-- | 02-usart/tests/test_memory.c | 251 |
6 files changed, 463 insertions, 17 deletions
diff --git a/02-usart/Makefile.preamble b/02-usart/Makefile.preamble index 486bd67..f6e1370 100644 --- a/02-usart/Makefile.preamble +++ b/02-usart/Makefile.preamble @@ -6,7 +6,7 @@ CFLAGS?=$(OPT) -mcpu=cortex-m4 -mthumb -g -lgcc -static -nostartfiles -Iinclude LD_FLAGS?=-T linker/linker_script.ld -nostdlib --cref -Map linker/main.map -static TEST_PREFIX=x86_64-pc-linux-gnu- -TEST_CFLAGS=-Iinclude -Iinclude/arch/x86_64 -Itest_harness -g3 -ggdb +TEST_CFLAGS=-Iinclude -Iinclude/arch/x86_64 -Itest_harness -g3 -ggdb -DFOR_TESTING -Wall all: _$(PREFIX)_obs/main.elf diff --git a/02-usart/include/arch/arm/arch.h b/02-usart/include/arch/arm/arch.h index 569ca77..f140c97 100644 --- a/02-usart/include/arch/arm/arch.h +++ b/02-usart/include/arch/arm/arch.h @@ -33,4 +33,7 @@ _Static_assert(sizeof(void*) == sizeof(uint32_t), "Pointers must be 32 bits"); #endif +extern uint32_t DATA_SEGMENT_START; +extern uint32_t DATA_SEGMENT_STOP; + #endif /* ARCH_H_ */ diff --git a/02-usart/include/arch/x86_64/arch.h b/02-usart/include/arch/x86_64/arch.h index 258214e..accc449 100644 --- a/02-usart/include/arch/x86_64/arch.h +++ b/02-usart/include/arch/x86_64/arch.h @@ -24,4 +24,10 @@ #define SYSTEM_CONFIG_BLOCK_BASE (load_fake_scb__()) #define NVIC_BASE (load_fake_nvic__()) +// Pretend there's a data segement at the start of SRAM1 for more accurate +// testing. +#define GHOST_DATA_SEGMENT_SIZE 1234 +#define DATA_SEGMENT_START SRAM1_BASE +#define DATA_SEGMENT_STOP (SRAM1_BASE + GHOST_DATA_SEGMENT_SIZE) + #endif /* ARCH_H_ */ diff --git a/02-usart/include/mem.h b/02-usart/include/mem.h index aa4ce12..f376e7d 100644 --- a/02-usart/include/mem.h +++ b/02-usart/include/mem.h @@ -1,4 +1,27 @@ #ifndef MEM_H_ #define MEM_H_ +#include "arch.h" +#include <stddef.h> + +#define MAX_HEAP_SIZE \ + ((16384 - (DATA_SEGMENT_STOP - DATA_SEGMENT_START)) / 4 * 4) + +/* allocates memory on the head, which is stored in sram2 */ +void* halloc(size_t n); + +/* Frees the memory allocated by halloc. */ +void hfree(void* mem); + +#ifdef FOR_TESTING + +void* debug_halloc_get_next_ptr(void* ptr); + +void* debug_halloc_get_prev_ptr(void* ptr); + +int debug_halloc_assert_consistency(char* error, size_t len); + +#endif + + #endif diff --git a/02-usart/src/mem.c b/02-usart/src/mem.c index 65d8b60..0cb9ee4 100644 --- a/02-usart/src/mem.c +++ b/02-usart/src/mem.c @@ -3,8 +3,8 @@ #include "common.h" #ifdef ARCH_STM32L4 -// Provide a definition for memset() - +/* Provide a definition for memset() when not provided for the + * microcontroller. */ void* memset(void* dest, int c, size_t n) { uint8_t c8 = (uint8_t) c; @@ -18,13 +18,188 @@ void* memset(void* dest, int c, size_t n) return dest; } +#else + +void* memset(void* dest, int c, size_t n); + #endif -// void memcpy_(void* dest, const void* src, size_t len) -// { -// uint8_t* dest_ = (uint8_t*) dest; -// uint8_t* src_ = (uint8_t*) src; -// -// while ((len--) > 0) -// *(dest_ ++) = *(src_ ++); -// } +typedef uint16_t halloc_off_t; + +// The sizes will count the number of WORDS allocated. +// Since there's a max size of 16k, only 12 bits will be +// needed for this. +typedef struct HALLOC_NODE { + union { + uint32_t header; + struct { + bool used:1; /* Is this memory in use. */ + /* Number of words allocated. Does not include the header. */ + uint16_t size:15; + halloc_off_t prev; /* The location of the last block (in WORDS from offest) */ + } PACKED; + }; + + uint8_t mem[]; /* The memory to use. */ +} halloc_node_t; + +halloc_node_t* halloc_start; + +#define halloc_node_next(cur) \ + ((halloc_node_t*)(((uint8_t*)(cur)) + (((cur)->size + 1) * 4))) + +#define halloc_node_prev(cur) halloc_node_at_off(cur->prev) + +#define halloc_node_at_off(offset) \ + ((halloc_node_t*)(((uint8_t*) halloc_start) + (offset) * 4)) + +#define halloc_node_get_off(node) \ + (((uint32_t)(((uint8_t*)(node)) - ((uint8_t*)(halloc_start)))) / 4) + +#define size_for(n) \ + (((n) / 4) + ((n) % 4 != 0)) + +void* halloc(size_t size) +{ + if (!halloc_start) { + halloc_start = (halloc_node_t*) DATA_SEGMENT_STOP; + memset(halloc_start, 0, sizeof(halloc_node_t)); + halloc_start->size = (MAX_HEAP_SIZE / 4) - 1; + } + + size_t realsz = size_for(size); /* Clip the size to the nearest word. */ + halloc_off_t offset = 0; + while (offset < (MAX_HEAP_SIZE / 4)) { + halloc_node_t* cur = halloc_node_at_off(offset); + + if (!cur->used && (cur->size >= realsz)) { + cur->used = true; + size_t orig_size = cur->size; + cur->size = realsz; + + if (orig_size > realsz) { + /* This halloc node needs to split into two blocks. */ + halloc_node_t* next = halloc_node_next(cur); + next->used = 0; + next->size = orig_size - realsz - sizeof(halloc_node_t) / 4; + next->prev = offset; + + halloc_node_t* nextnext = halloc_node_next(next); + if (halloc_node_get_off(nextnext) < (MAX_HEAP_SIZE / 4)) { + nextnext->prev = halloc_node_get_off(next); + } + } + + return (void*) cur->mem; + } + + offset += (sizeof(halloc_node_t) / 4) + cur->size; + } + + return NULL; +} + +/* Joins this node with the previous and next nodes if they're free. */ +static void coalesce(halloc_node_t* cur) +{ + if (cur->used) return; + + halloc_node_t* next = halloc_node_next(cur); + if (!next->used) { + cur->size += next->size + sizeof(halloc_node_t) / 4; + } + + if (cur != halloc_start) { + coalesce(halloc_node_prev(cur)); + } +} + +void hfree(void* mem) +{ + /* TODO this should be a critical section. */ + if (!mem) { + /* Consistent with C, freeing a NULL pointer does nothing. */ + return; + } + + halloc_node_t* header = ((halloc_node_t*) mem) - 1; + + if (!header->used) { +#ifdef FOR_TESTING + assert(header->used); +#endif + return; // TODO make this fail on ARM. + } + + header->used = 0; + coalesce(header); +} + +#ifdef FOR_TESTING + +#include <stdio.h> + +void* debug_halloc_get_next_ptr(void* ptr) +{ + halloc_node_t* node = ptr - sizeof(halloc_node_t); + halloc_node_t* next = halloc_node_next(node); + + return next->mem; +} + +void* debug_halloc_get_prev_ptr(void* ptr) +{ + halloc_node_t* node = ptr - sizeof(halloc_node_t); + halloc_node_t* prev = halloc_node_prev(node); + + return prev->mem; +} + +/* Tests that we can walk up and down the allocated blocks and that they + * are properly aligned. */ +int debug_halloc_assert_consistency(char* error, size_t len) +{ + halloc_node_t* cur = halloc_node_at_off(0); + size_t total_size = 0; + size_t offset = 0; + size_t loop_check = 0; + + while(1) { + total_size += cur->size + 1; + + halloc_node_t* next = halloc_node_next(cur); + if (next == DATA_SEGMENT_STOP + MAX_HEAP_SIZE) { + break; + } else if (next > (void*)(DATA_SEGMENT_STOP + MAX_HEAP_SIZE)){ + snprintf( + error, len, "Next node points is out of bounds. %p vs max of %p\n", + next, + (void*)(DATA_SEGMENT_STOP + MAX_HEAP_SIZE)); + return 1; + } + cur = next; + } + + if (total_size * 4 != MAX_HEAP_SIZE) { + snprintf( + error, len, "Total recorded size is inconsistent. %d vs %d\n", + total_size * 4, MAX_HEAP_SIZE); + return 1; + } + + while (loop_check < 10000) { + halloc_node_t* prev = halloc_node_prev(cur); + + if (prev == halloc_start) { + return 0; + } + + cur = prev; + ++ loop_check; + } + + snprintf(error, len, "Loop check failed.\n"); + return 1; +} + +#endif diff --git a/02-usart/tests/test_memory.c b/02-usart/tests/test_memory.c index e62877a..e68977a 100644 --- a/02-usart/tests/test_memory.c +++ b/02-usart/tests/test_memory.c @@ -1,12 +1,251 @@ +#ifndef FOR_TESTING +#define FOR_TESTING +#endif + +#include <stdlib.h> + +#include "arch.h" #include "test_harness.c" -#include "memory.h" +#include "common.h" +#include "mem.h" + +extern uint32_t* halloc_start; +static void wipeout_halloc() +{ + memset(halloc_start, 0, 1024); + halloc_start = NULL; +} + +struct TEST_STRUCT { + uint32_t array[3]; +}; + +struct TEST_STRUCT2 { + uint32_t array[10]; +}; + + +static struct TEST_STRUCT* new_test_struct() +{ + struct TEST_STRUCT* ret = halloc(sizeof(struct TEST_STRUCT)); + + ret->array[0] = 1; + ret->array[1] = 2; + ret->array[2] = 3; + + return ret; +} + +static struct TEST_STRUCT2* new_test_struct2() +{ + struct TEST_STRUCT2* ret = halloc(sizeof(struct TEST_STRUCT2)); + + for (int i = 0; i < 10; ++ i) { + ret->array[i] = i; + } + + return ret; +} + +#define ASSERT_CHAIN(t1, t2) \ + ASSERT_EQ(V(t1) + sizeof(*t1) + 4, V(t2)) + +TEST(memory, halloc) +{ + +#define V(x) ((void*)(x)) + struct TEST_STRUCT* test1 = new_test_struct(); + struct TEST_STRUCT2* test2 = new_test_struct2(); + struct TEST_STRUCT* test3 = new_test_struct(); + struct TEST_STRUCT2* test4 = new_test_struct2(); + struct TEST_STRUCT2* test5 = new_test_struct2(); + + ASSERT_TRUE(V(test1) != V(test2)); + ASSERT_TRUE(V(test2) != V(test3)); + ASSERT_TRUE(V(test3) != V(test1)); + ASSERT_TRUE(V(test2) != V(test5)); + ASSERT_TRUE(V(test4) != V(test5)); + + ASSERT_CHAIN(test1, test2); + ASSERT_CHAIN(test2, test3); + ASSERT_CHAIN(test3, test4); + ASSERT_CHAIN(test4, test5); + + wipeout_halloc(); +} + +struct UNEVEN_STRUCT { + uint8_t arr[5]; +}; + +struct UNEVEN_STRUCT* new_uneven_struct() +{ + struct UNEVEN_STRUCT* ret = halloc(sizeof(struct UNEVEN_STRUCT)); + + ret->arr[0] = 1; + ret->arr[1] = 2; + ret->arr[2] = 3; + ret->arr[3] = 4; + ret->arr[4] = 5; -TEST(memory, memcpy) + return ret; +} + +#define size_for(n) \ + (((n) / 4) + ((n) % 4 != 0)) + +TEST(memory, uneven_halloc) { - const char* from = "Hello"; - char to[16]; + struct UNEVEN_STRUCT* test1 = new_uneven_struct(); + struct UNEVEN_STRUCT* test2 = new_uneven_struct(); + + ASSERT_EQ(V(test1) + 12, test2); + + wipeout_halloc(); +} + +TEST(memory, halloc_free) +{ + struct TEST_STRUCT* test1 = new_test_struct(); + struct TEST_STRUCT2* test2 = new_test_struct2(); + struct TEST_STRUCT* test3 = new_test_struct(); + struct TEST_STRUCT2* test4 = new_test_struct2(); + struct TEST_STRUCT2* test5 = new_test_struct2(); + + hfree(test2); + hfree(test4); + hfree(test3); + hfree(test1); + hfree(test5); + + ASSERT_EQ((*halloc_start >> 1) * 4, MAX_HEAP_SIZE - 4); + + test1 = new_test_struct(); + test2 = new_test_struct2(); + test3 = new_test_struct(); + test4 = new_test_struct2(); + test5 = new_test_struct2(); + + hfree(test1); + hfree(test3); + hfree(test2); + hfree(test4); + hfree(test5); + + ASSERT_EQ((*halloc_start >> 1) * 4, MAX_HEAP_SIZE - 4); + + test1 = new_test_struct(); + test2 = new_test_struct2(); + test3 = new_test_struct(); + test4 = new_test_struct2(); + test5 = new_test_struct2(); + + hfree(test4); + hfree(test3); + hfree(test1); + hfree(test2); + hfree(test5); + + ASSERT_EQ((*halloc_start >> 1) * 4, MAX_HEAP_SIZE - 4); + + wipeout_halloc(); +} + +TEST(memory, halloc_free_alloc2) +{ + struct TEST_STRUCT2* test1 = new_test_struct2(); + struct TEST_STRUCT2* test2 = new_test_struct2(); + + hfree(test1); + + struct TEST_STRUCT* test3 = new_test_struct(); + struct TEST_STRUCT* test4 = new_test_struct(); + + ASSERT_EQ(debug_halloc_get_next_ptr(test3), V(test4)); + + ASSERT_EQ( + // There should be a free block after test4. + debug_halloc_get_next_ptr(debug_halloc_get_next_ptr(test4)), + V(test2)); + + ASSERT_EQ( + // There should be a free block after test4. + debug_halloc_get_prev_ptr(debug_halloc_get_prev_ptr(test2)), + V(test4)); + + char buf[1024]; + if (debug_halloc_assert_consistency(buf, 1024)) { + fprintf(stderr, "Consistency check failed.\n"); + fprintf(stderr, buf); + ASSERT_TRUE(false); + } + + return 0; +} + +TEST(memory, consistency_stress) +{ + if (halloc_start) { + wipeout_halloc(); + } + + int i; + void* allocd[500] = { 0 }; + char buf[1024]; + + for (i = 0; i < 500; ++ i) { + size_t nalloc = rand() % 20; + allocd[i] = halloc(nalloc); + + ASSERT_TRUE(allocd[i]); + size_t idx = rand() % 500; + + hfree(allocd[idx]); + allocd[idx] = NULL; + + idx = rand() % 500; + hfree(allocd[idx]); + allocd[idx] = NULL; + + if (debug_halloc_assert_consistency(buf, 1024)) { + fprintf(stderr, "Consistency check failed. (At index %d) nalloc=%lu\n", i, nalloc); + fprintf(stderr, buf); + ASSERT_TRUE(false); + } + } + + for(i = 0; i < 500; ++ i) { + hfree(allocd[i]); + } + + if (debug_halloc_assert_consistency(buf, 1024)) { + fprintf(stderr, "Consistency check failed. (Final)\n"); + fprintf(stderr, buf); + ASSERT_TRUE(false); + } + ASSERT_EQ((*halloc_start >> 1) * 4, MAX_HEAP_SIZE - 4); +} + +TEST(memory, halloc_free_alloc) +{ + new_test_struct(); + struct TEST_STRUCT2* test2 = new_test_struct2(); + new_test_struct(); + struct TEST_STRUCT2* test4 = new_test_struct2(); + new_test_struct2(); + + hfree(test4); + + struct TEST_STRUCT2* test6 = new_test_struct2(); + + // test_6 should have been allocated in test_4's spot. + ASSERT_EQ(test6, test4); - memcpy(to, from, 6); + hfree(test2); + struct TEST_STRUCT* test7 = new_test_struct(); + struct TEST_STRUCT* test8 = new_test_struct(); - ASSERT_EQ_STR(to, from); + // Test 2 was large enough to accomodate 3 smaller structs. + ASSERT_EQ(V(test7), V(test2)); + ASSERT_EQ(V(test8), V(test2) + sizeof(*test7) + 4); } |