From 7aadb1a2e7f4a8401693035a8d58d6dd4b670063 Mon Sep 17 00:00:00 2001 From: Lunaixsky Date: Tue, 10 Dec 2024 02:46:04 +0000 Subject: [PATCH] optimize the tests makefiles, add unit tests for btrie key allocator * add simple memory allocation monitor for checking leakage and usage --- lunaix-os/tests/includes/testing/memchk.h | 24 +++ lunaix-os/tests/shared/framework.c | 8 +- lunaix-os/tests/shared/makefile | 13 +- lunaix-os/tests/shared/memchk.c | 72 +++++++ lunaix-os/tests/shared/mkobj.mkinc | 3 + lunaix-os/tests/units/.gitignore | 1 + lunaix-os/tests/units/btrie/dut/btrie.c | 1 + lunaix-os/tests/units/btrie/makefile | 3 + lunaix-os/tests/units/btrie/test-alloc.c | 201 +++++++++++++++++++ lunaix-os/tests/units/btrie/tests.txt | 1 + lunaix-os/tests/units/device-tree/.gitignore | 3 +- lunaix-os/tests/units/device-tree/common.h | 1 - lunaix-os/tests/units/device-tree/makefile | 40 +--- lunaix-os/tests/units/makefile | 12 +- lunaix-os/tests/units/stubs/valloc.c | 45 ++++- lunaix-os/tests/units/units_build.mkinc | 24 +++ 16 files changed, 398 insertions(+), 54 deletions(-) create mode 100644 lunaix-os/tests/includes/testing/memchk.h create mode 100644 lunaix-os/tests/shared/memchk.c create mode 100644 lunaix-os/tests/shared/mkobj.mkinc create mode 100644 lunaix-os/tests/units/.gitignore create mode 120000 lunaix-os/tests/units/btrie/dut/btrie.c create mode 100644 lunaix-os/tests/units/btrie/makefile create mode 100644 lunaix-os/tests/units/btrie/test-alloc.c create mode 100644 lunaix-os/tests/units/btrie/tests.txt create mode 100644 lunaix-os/tests/units/units_build.mkinc diff --git a/lunaix-os/tests/includes/testing/memchk.h b/lunaix-os/tests/includes/testing/memchk.h new file mode 100644 index 0000000..77db92d --- /dev/null +++ b/lunaix-os/tests/includes/testing/memchk.h @@ -0,0 +1,24 @@ +#ifndef __COMMON_TEST_MEMCHK_H +#define __COMMON_TEST_MEMCHK_H + +struct valloc_stats +{ + unsigned long alloced; + unsigned long freed; + unsigned long nr_vfree_calls; + + unsigned int nr_valloc_calls; +}; + +extern struct valloc_stats valloc_stat; + +void +memchk_log_alloc(unsigned long addr, unsigned long size); + +void +memchk_log_free(unsigned long addr); + +void +memchk_print_stats(); + +#endif /* __COMMON_TEST_MEMCHK_H */ diff --git a/lunaix-os/tests/shared/framework.c b/lunaix-os/tests/shared/framework.c index ad1aebc..3c3f191 100644 --- a/lunaix-os/tests/shared/framework.c +++ b/lunaix-os/tests/shared/framework.c @@ -1,4 +1,5 @@ #include +#include #include struct test_context* __test_ctx; @@ -13,11 +14,14 @@ main(int argc, const char* argv[]) run_test(argc, argv); printf( - "All test done: %d passed, %d failed\n", + "All test done: %d passed, %d failed\n\n", __test_ctx->stats.total_passed, __test_ctx->stats.total_failed ); - printf("************\n\n"); + + memchk_print_stats(); + + printf("\n************\n\n"); exit(__test_ctx->stats.total_failed > 0); } diff --git a/lunaix-os/tests/shared/makefile b/lunaix-os/tests/shared/makefile index 0484be2..6d38283 100644 --- a/lunaix-os/tests/shared/makefile +++ b/lunaix-os/tests/shared/makefile @@ -9,12 +9,9 @@ CFLAGS += -idirafter $(lunaix-root)/includes \ -I $(test-root)/includes \ -Wno-discarded-qualifiers \ -Wno-scalar-storage-order \ - -g + -Werror \ + -g \ + -D__off_t_defined - -%.o: %.c - $(call status,CC,$(@F)) - @$(CC) $(CFLAGS) -c $< -o $@ - - -obj-shared := $(test-shared-root)/framework.o +obj-shared := $(test-shared-root)/framework.o \ + $(test-shared-root)/memchk.o diff --git a/lunaix-os/tests/shared/memchk.c b/lunaix-os/tests/shared/memchk.c new file mode 100644 index 0000000..b695201 --- /dev/null +++ b/lunaix-os/tests/shared/memchk.c @@ -0,0 +1,72 @@ +#include +#include + +#include + +extern void *malloc(size_t); +extern void *calloc(size_t, size_t); +extern void free(void*); + +struct valloc_stats valloc_stat = { }; +static DEFINE_LLIST(records); + +struct addr_record { + struct llist_header link; + unsigned long addr; + unsigned long size; +}; + +void +memchk_log_alloc(unsigned long addr, unsigned long size) +{ + valloc_stat.alloced += size; + valloc_stat.nr_valloc_calls++; + + struct addr_record *record; + + record = malloc(sizeof(struct addr_record)); + record->addr = addr; + record->size = size; + + llist_append(&records, &record->link); +} + +void +memchk_log_free(unsigned long addr) +{ + valloc_stat.nr_vfree_calls++; + + struct addr_record *pos, *n; + llist_for_each(pos, n, &records, link) + { + if (pos->addr == addr) { + valloc_stat.freed += pos->size; + llist_delete(&pos->link); + + free(pos); + return; + } + } + + printf("[\x1b[33;49mWARN\x1b[0m] freeing undefined pointer: 0x%lx\n", addr); +} + + +void +memchk_print_stats() +{ + long leaked; + + leaked = valloc_stat.alloced - valloc_stat.freed; + printf("valloc() statistics:\n"); + printf(" allocated: %lu bytes\n", valloc_stat.alloced); + printf(" freed: %lu bytes\n", valloc_stat.freed); + printf(" leaked: %lu bytes\n", leaked); + printf(" vfree_call: %u times\n", valloc_stat.nr_vfree_calls); + printf(" valloc_call: %u times\n", valloc_stat.nr_valloc_calls); + + if (leaked) + { + printf("[\x1b[33;49mWARN\x1b[0m] memory leakage detected\n"); + } +} \ No newline at end of file diff --git a/lunaix-os/tests/shared/mkobj.mkinc b/lunaix-os/tests/shared/mkobj.mkinc new file mode 100644 index 0000000..edbc75f --- /dev/null +++ b/lunaix-os/tests/shared/mkobj.mkinc @@ -0,0 +1,3 @@ +%.o: %.c + $(call status,CC,$(@F)) + @$(CC) $(CFLAGS) -c $< -o $@ diff --git a/lunaix-os/tests/units/.gitignore b/lunaix-os/tests/units/.gitignore new file mode 100644 index 0000000..70105d4 --- /dev/null +++ b/lunaix-os/tests/units/.gitignore @@ -0,0 +1 @@ +**.test \ No newline at end of file diff --git a/lunaix-os/tests/units/btrie/dut/btrie.c b/lunaix-os/tests/units/btrie/dut/btrie.c new file mode 120000 index 0000000..3abae1b --- /dev/null +++ b/lunaix-os/tests/units/btrie/dut/btrie.c @@ -0,0 +1 @@ +../../../../kernel/ds/btrie.c \ No newline at end of file diff --git a/lunaix-os/tests/units/btrie/makefile b/lunaix-os/tests/units/btrie/makefile new file mode 100644 index 0000000..7a4f83b --- /dev/null +++ b/lunaix-os/tests/units/btrie/makefile @@ -0,0 +1,3 @@ +obj-dut := dut/btrie.o + +include units_build.mkinc \ No newline at end of file diff --git a/lunaix-os/tests/units/btrie/test-alloc.c b/lunaix-os/tests/units/btrie/test-alloc.c new file mode 100644 index 0000000..cad32c9 --- /dev/null +++ b/lunaix-os/tests/units/btrie/test-alloc.c @@ -0,0 +1,201 @@ +#include +#include +#include +#include + +#define WIDTH 8 + +static void no_inline +__alloc_simple() +{ + struct btrie tree; + struct btrie_node *root; + btrie_init(&tree, ilog2(WIDTH)); + + expect_ulong(btrie_map(&tree, 0, 100, (void*)1), 0); + expect_ulong(btrie_map(&tree, 0, 100, (void*)2), 1); + expect_ulong(btrie_map(&tree, 0, 100, (void*)3), 2); + expect_ulong(btrie_map(&tree, 0, 100, (void*)4), 3); + + root = tree.btrie_root; + expect_notnull(root->children); + expect_int(root->children_cnt, 4); + + for (int i = 0; i < 4; i++) + { + expect_notnull(root->children[i]); + expect_int(root->children[i]->index, i); + expect_ulong((ptr_t)root->children[i]->data, i + 1); + } + + for (int i = 4; i < WIDTH; i++) + { + expect_null(root->children[i]); + } + + btrie_release(&tree); +} + +static void no_inline +__alloc_edge() +{ + struct btrie tree; + struct btrie_node *root; + btrie_init(&tree, ilog2(WIDTH)); + + expect_ulong(btrie_map(&tree, 7, 100, (void*)1), 7); + expect_ulong(btrie_map(&tree, 7, 100, (void*)2), 8); + expect_ulong(btrie_map(&tree, 7, 100, (void*)3), 9); + expect_ulong(btrie_map(&tree, 7, 100, (void*)4), 10); + + root = tree.btrie_root; + expect_notnull(root->children); + expect_int(root->children_cnt, 2); + + expect_notnull(root->children[7]); + expect_int(root->children[7]->index, 7); + expect_ulong((ptr_t)root->children[7]->data, 1); + + expect_notnull(root->children[1]); + root = root->children[1]; + + for (int i = 0; i < 3; i++) + { + expect_notnull(root->children[i]); + expect_int(root->children[i]->index, i); + expect_ulong((ptr_t)root->children[i]->data, i + 2); + } + + btrie_release(&tree); +} + +static void no_inline +__alloc_narrow() +{ + struct btrie tree; + struct btrie_node *root; + btrie_init(&tree, ilog2(WIDTH)); + + expect_ulong(btrie_map(&tree, 4, 7, (void*)1), 4); + expect_ulong(btrie_map(&tree, 4, 7, (void*)2), 5); + expect_ulong(btrie_map(&tree, 4, 7, (void*)3), 6); + expect_ulong(btrie_map(&tree, 4, 7, (void*)4), -1); + + root = tree.btrie_root; + expect_notnull(root->children); + expect_int(root->children_cnt, 3); + + for (int i = 0; i < 4; ++i) + { + expect_null(root->children[i]); + } + + for (int i = 4, j = 1; i < WIDTH - 1; ++i, ++j) + { + expect_notnull(root->children[i]); + expect_int(root->children[i]->index, i); + expect_ulong((ptr_t)root->children[i]->data, j); + } + + btrie_release(&tree); +} + +static void no_inline +__alloc_narrow_partial() +{ + struct btrie tree; + struct btrie_node *root; + btrie_init(&tree, ilog2(WIDTH)); + + expect_ulong(btrie_map(&tree, 15, 17, (void*)1), 15); + expect_ulong(btrie_map(&tree, 15, 17, (void*)2), 16); + expect_ulong(btrie_map(&tree, 15, 17, (void*)3), -1); + + root = tree.btrie_root; + expect_notnull(root->children); + expect_int(root->children_cnt, 2); + + // check left subtree + + root = root->children[1]; + expect_notnull(root); + expect_int(root->children_cnt, 1); + + int i = 0; + for (; i < WIDTH - 1; ++i) + { + expect_null(root->children[i]); + } + + // i = WIDTH - 1 + expect_notnull(root->children[i]); + expect_int(root->children[i]->index, i); + expect_ulong((ptr_t)root->children[i]->data, 1); + + // check right subtree + + root = tree.btrie_root; + root = root->children[2]; + expect_notnull(root); + expect_int(root->children_cnt, 1); + + i = 0; + expect_notnull(root->children[i]); + expect_int(root->children[i]->index, i); + expect_ulong((ptr_t)root->children[i]->data, 2); + + for (i++; i < WIDTH; ++i) + { + expect_null(root->children[i]); + } + + btrie_release(&tree); +} + +static void no_inline +__alloc_dense() +{ + int mis_alloc = 0; + struct btrie tree; + btrie_init(&tree, ilog2(WIDTH)); + + for (size_t i = 0; i < 1000; i++) + { + if (btrie_map(&tree, 0, 1001, (void*)i+1) == -1UL) + { + mis_alloc++; + } + } + + expect_int(mis_alloc, 0); + btrie_release(&tree); +} + +static void no_inline +__alloc_retrive() +{ + struct btrie tree; + struct btrie_node *root; + btrie_init(&tree, ilog2(WIDTH)); + + expect_ulong(btrie_map(&tree, 4, 7, (void*)1), 4); + expect_ulong(btrie_map(&tree, 4, 7, (void*)2), 5); + expect_ulong(btrie_map(&tree, 4, 7, (void*)3), 6); + + expect_ulong(__ptr(btrie_get(&tree, 6)), 3); + expect_ulong(__ptr(btrie_get(&tree, 5)), 2); + expect_ulong(__ptr(btrie_get(&tree, 4)), 1); + + btrie_release(&tree); +} + +void +run_test(int argc, const char* argv[]) +{ + testcase("simple_alloc", __alloc_simple()); + testcase("simple_edge", __alloc_edge()); + testcase("simple_narrow", __alloc_narrow()); + testcase("narrow_partial", __alloc_narrow_partial()); + testcase("alloc_dense", __alloc_dense()); + testcase("alloc_get", __alloc_retrive()); +} \ No newline at end of file diff --git a/lunaix-os/tests/units/btrie/tests.txt b/lunaix-os/tests/units/btrie/tests.txt new file mode 100644 index 0000000..a85a68a --- /dev/null +++ b/lunaix-os/tests/units/btrie/tests.txt @@ -0,0 +1 @@ +alloc diff --git a/lunaix-os/tests/units/device-tree/.gitignore b/lunaix-os/tests/units/device-tree/.gitignore index 06e925a..662a34e 100644 --- a/lunaix-os/tests/units/device-tree/.gitignore +++ b/lunaix-os/tests/units/device-tree/.gitignore @@ -1,3 +1,2 @@ test -*.dtb -*.test \ No newline at end of file +*.dtb \ No newline at end of file diff --git a/lunaix-os/tests/units/device-tree/common.h b/lunaix-os/tests/units/device-tree/common.h index 94c2370..0eeb508 100644 --- a/lunaix-os/tests/units/device-tree/common.h +++ b/lunaix-os/tests/units/device-tree/common.h @@ -1,7 +1,6 @@ #ifndef __DTTEST_COMMON_H #define __DTTEST_COMMON_H -#define __off_t_defined #include "dut/devtree.h" #include diff --git a/lunaix-os/tests/units/device-tree/makefile b/lunaix-os/tests/units/device-tree/makefile index 4d9d530..c88c2f6 100644 --- a/lunaix-os/tests/units/device-tree/makefile +++ b/lunaix-os/tests/units/device-tree/makefile @@ -1,38 +1,18 @@ -include test_build.mkinc +obj-dut := dut/dt_interrupt.o \ + dut/dt.o \ + dut/dtspec.o \ + dut/changeling.o -tests := $(shell cat tests.txt) - -obj = dut/dt_interrupt.o \ - dut/dt.o \ - dut/dtspec.o \ - dut/changeling.o \ - -dtbs := $(addprefix samples/,$(addsuffix .dtb,$(tests))) - -tests := $(addsuffix .test,$(tests)) -run_tests := $(addprefix run.,$(tests)) +BIN_DEPS += load.%.o +CFLAGS += -DCONFIG_USE_DEVICETREE +.PRECIOUS: %.dtb %.dtb: %.dts $(call status,DTC,$^) @dtc -q -I dts -O dtb $^ -o $@ -.PHONY: all run clean - -load.%.o:: load.c +load.%.o: load.c samples/%.dtb $(call status,CC,$@) - @$(CC) $(CFLAGS) -DTEST_DTBFILE=\"samples/$*.dtb\" -c $^ -o $@ - -%.test: $(obj-shared) $(obj-stubs) $(obj) test-%.o load.%.o - $(call status,LD,$@) - @$(CC) $^ -o $@ - -run.%.test: %.test - $(call status,RUN,$^) - @./$^ - -all: $(dtbs) $(tests) - -run: $(dtbs) $(tests) $(run_tests) + @$(CC) $(CFLAGS) -DTEST_DTBFILE=\"samples/$*.dtb\" -c $< -o $@ -clean: - @rm -f *.o $(obj) $(test) $(dtbs) \ No newline at end of file +include units_build.mkinc \ No newline at end of file diff --git a/lunaix-os/tests/units/makefile b/lunaix-os/tests/units/makefile index 66cf8ab..866c718 100644 --- a/lunaix-os/tests/units/makefile +++ b/lunaix-os/tests/units/makefile @@ -1,8 +1,12 @@ LUNAIX_ROOT ?= $(shell realpath ../../) -include test_build.mkinc +include $(LUNAIX_ROOT)/tests/shared/makefile +include $(LUNAIX_ROOT)/tests/shared/mkobj.mkinc -__test-dir := device-tree +MAKEFLAGS += --no-print-directory +CFLAGS += -isystem $(unit-test-root)/stubs/includes + +__test-dir := device-tree btrie test-dir := $(addprefix test-,$(__test-dir)) obj-stubs := @@ -11,7 +15,9 @@ obj-tmp := include stubs/makefile obj-stubs += $(addprefix $(unit-test-root)/stubs/,$(obj-tmp)) -export obj-stubs LUNAIX_ROOT +BIN_DEPS := $(obj-stubs) $(obj-shared) + +export BIN_DEPS CFLAGS LUNAIX_ROOT test-%: $(call status,MK,$*) @$(MAKE) $(MKFLAGS) -C $* $(_ACT) -I $(CURDIR) diff --git a/lunaix-os/tests/units/stubs/valloc.c b/lunaix-os/tests/units/stubs/valloc.c index 0d02922..c8897e2 100644 --- a/lunaix-os/tests/units/stubs/valloc.c +++ b/lunaix-os/tests/units/stubs/valloc.c @@ -1,56 +1,85 @@ #include +#include #include extern void *malloc(size_t); extern void *calloc(size_t, size_t); extern void free(void*); +static inline void* +_my_malloc(size_t size) +{ + void* ptr; + + ptr = malloc(size); + memchk_log_alloc((unsigned long)ptr, size); + + return ptr; +} + +static inline void* +_my_calloc(size_t size, int n) +{ + void* ptr; + + ptr = calloc(size, n); + memchk_log_alloc((unsigned long)ptr, size * n); + + return ptr; +} + +static inline void +_my_free(void* addr) +{ + memchk_log_free((unsigned long)addr); +} + void* valloc(unsigned int size) { - return malloc(size); + return _my_malloc(size); } void* vzalloc(unsigned int size) { - return calloc(size, 1); + return _my_calloc(size, 1); } void* vcalloc(unsigned int size, unsigned int count) { - return calloc(size, count); + return _my_calloc(size, count); } void vfree(void* ptr) { - free(ptr); + _my_free(ptr); } void vfree_safe(void* ptr) { - if (ptr) free(ptr); + if (ptr) _my_free(ptr); } void* valloc_dma(unsigned int size) { - return malloc(size); + return _my_malloc(size); } void* vzalloc_dma(unsigned int size) { - return calloc(size, 1); + return _my_calloc(size, 1); } void vfree_dma(void* ptr) { - free(ptr); + _my_free(ptr); } void diff --git a/lunaix-os/tests/units/units_build.mkinc b/lunaix-os/tests/units/units_build.mkinc new file mode 100644 index 0000000..29b64ad --- /dev/null +++ b/lunaix-os/tests/units/units_build.mkinc @@ -0,0 +1,24 @@ +include $(LUNAIX_ROOT)/tests/shared/mkobj.mkinc +include $(LUNAIX_ROOT)/makeinc/utils.mkinc + +tests := $(addsuffix .test,$(shell cat tests.txt)) +run_tests := $(addprefix run.,$(tests)) + +BIN_DEPS += $(obj-dut) + +.PHONY: all run clean + +%.test: $(BIN_DEPS) test-%.o + $(call status,LD,$@) + @$(CC) $^ -o $@ + +run.%.test: %.test + $(call status,RUN,$^) + @./$^ + +all: $(tests) + +run: $(tests) $(run_tests) + +clean: + @rm -f *.o $(tests) $(obj-dut) $(TO_CLEAN) \ No newline at end of file -- 2.27.0