Repository: tailix/libkernaux (language: python)

Issue:
Finish memory allocator



Discussion / hints:

Fix patch:
diff --git a/README.md b/README.md
index fb72c949..892547c2 100644
--- a/README.md
+++ b/README.md
@@ -54,6 +54,7 @@ zero). Work-in-progress APIs can change at any time.
   * [Framebuffer](/include/kernaux/framebuffer.h) (*planned*)
   * USB (*planned*)
 * Algorithms
+  * [Memory allocator](/include/kernaux/alloc.h) (*work in progress*)
   * [Simple command line parser](/include/kernaux/cmdline.h) (*non-breaking since* **0.2.0**)
     * [Example](/examples/cmdline.c)
   * [Page Frame Allocator](/include/kernaux/pfa.h) (*work in progress*)
@@ -66,7 +67,6 @@ zero). Work-in-progress APIs can change at any time.
 * Utilities
   * [Measurement units utils](/include/kernaux/units.h) (*work in progress*)
     * [Example: To human](/examples/units_human.c)
-  * [Memory allocator](/include/kernaux/alloc.h) (*work in progress*)
   * [Memory map](/include/kernaux/memmap.h.in) (*non-breaking since* **0.4.0**)
     * [Example](/examples/memmap.c)
   * [printf format parser](/include/kernaux/printf_fmt.h) (*work in progress*)
diff --git a/include/kernaux/alloc.h b/include/kernaux/alloc.h
index 825da163..8e5f6c37 100644
--- a/include/kernaux/alloc.h
+++ b/include/kernaux/alloc.h
@@ -5,25 +5,25 @@
 extern "C" {
 #endif
 
-#include <stdbool.h>
+#include <kernaux/mutex.h>
+
 #include <stddef.h>
 
 typedef struct KernAux_Alloc_Node {
-    struct KernAux_Alloc_Node *next;
-    bool free;
-    size_t actual_size, user_size;
+    struct KernAux_Alloc_Node *next, *prev;
+    size_t size;
     char *block;
 } *KernAux_Alloc_Node;
 
 typedef struct KernAux_Alloc {
+    KernAux_Mutex mutex;
     KernAux_Alloc_Node head;
 } *KernAux_Alloc;
 
-struct KernAux_Alloc KernAux_Alloc_create();
-void KernAux_Alloc_init(KernAux_Alloc alloc);
+struct KernAux_Alloc KernAux_Alloc_create(KernAux_Mutex mutex);
+void KernAux_Alloc_init(KernAux_Alloc alloc, KernAux_Mutex mutex);
 
-void
-KernAux_Alloc_add_memory_block(KernAux_Alloc alloc, void *ptr, size_t size);
+void KernAux_Alloc_add_zone(KernAux_Alloc alloc, void *ptr, size_t size);
 
 void *KernAux_Alloc_malloc(KernAux_Alloc alloc, size_t size);
 void  KernAux_Alloc_free  (KernAux_Alloc alloc, void *ptr);
diff --git a/src/alloc.c b/src/alloc.c
index 5d4054f2..b720ae83 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -14,46 +14,95 @@
 #include <stddef.h>
 #include <stdint.h>
 
-#define ALIGN_MASK(align) ((align) - 1) // align should be a power of 2
-#define ALIGN_UP(val, align) (((val) + ALIGN_MASK(align)) & ~ALIGN_MASK(align))
-
-#define PTR_ALIGNMENT (sizeof(void*)) // TODO: align node to this value
-
-#define ALLOC_HEADER_SIZE (offsetof(struct KernAux_Alloc_Node, block))
-#define MIN_ALLOC_SIZE (ALLOC_HEADER_SIZE + 16)
-
-struct KernAux_Alloc KernAux_Alloc_create()
+#define NODE_HEADER_SIZE (offsetof(struct KernAux_Alloc_Node, block))
+#define MIN_ZONE_SIZE (2 * NODE_HEADER_SIZE)
+#define MIN_SPLIT_SIZE (NODE_HEADER_SIZE + 16)
+
+#define CONTAINER_OF(ptr, type, member) ((type*)((uintptr_t)(ptr) - offsetof(type, member)))
+
+//#define ALIGN_MASK(align) ((align) - 1) // align should be a power of 2
+//#define ALIGN_UP(val, align) (((val) + ALIGN_MASK(align)) & ~ALIGN_MASK(align))
+
+//#define PTR_ALIGNMENT (sizeof(void*)) // TODO: align node to this value
+
+#define LOCK(alloc)                               \
+    do {                                          \
+        if ((alloc)->mutex) {                     \
+            KernAux_Mutex_lock((alloc)->mutex);   \
+        }                                         \
+    } while (0)
+
+#define UNLOCK(alloc)                             \
+    do {                                          \
+        if ((alloc)->mutex) {                     \
+            KernAux_Mutex_unlock((alloc)->mutex); \
+        }                                         \
+    } while (0)
+
+static void KernAux_Alloc_defrag(KernAux_Alloc alloc);
+static void KernAux_Alloc_insert(
+    KernAux_Alloc alloc,
+    KernAux_Alloc_Node node,
+    KernAux_Alloc_Node prev,
+    KernAux_Alloc_Node next
+);
+static void KernAux_Alloc_remove(KernAux_Alloc alloc, KernAux_Alloc_Node node);
+
+struct KernAux_Alloc KernAux_Alloc_create(const KernAux_Mutex mutex)
 {
     struct KernAux_Alloc alloc;
-    KernAux_Alloc_init(&alloc);
+    KernAux_Alloc_init(&alloc, mutex);
     return alloc;
 }
 
-void KernAux_Alloc_init(const KernAux_Alloc alloc)
+void KernAux_Alloc_init(const KernAux_Alloc alloc, const KernAux_Mutex mutex)
 {
     KERNAUX_ASSERT(alloc);
 
+    alloc->mutex = mutex;
     alloc->head = NULL;
 }
 
-void KernAux_Alloc_add_memory_block(
+void KernAux_Alloc_add_zone(
     const KernAux_Alloc alloc,
     void *const ptr,
     const size_t size
 ) {
     KERNAUX_ASSERT(alloc);
     KERNAUX_ASSERT(ptr);
-    KERNAUX_ASSERT(size >= 2 * sizeof(struct KernAux_Alloc_Node));
+    KERNAUX_ASSERT(size >= MIN_ZONE_SIZE);
+
+    LOCK(alloc);
 
     KernAux_Alloc_Node new_node = ptr;
-    new_node->free = true;
-    new_node->actual_size = size;
-    new_node->user_size = size - sizeof(struct KernAux_Alloc_Node);
-
-    // TODO: lock
-    new_node->next = alloc->head;
-    alloc->head = new_node;
-    // TODO: unlock
+    new_node->size = size;
+
+    KernAux_Alloc_Node prev_node = NULL;
+    KernAux_Alloc_Node next_node;
+    KernAux_Alloc_Node last_node = NULL;
+
+    for (
+        KernAux_Alloc_Node item_node = alloc->head;
+        item_node;
+        item_node = item_node->next
+    ) {
+        last_node = item_node;
+
+        if (item_node > new_node) {
+            next_node = item_node;
+            if (item_node->prev) prev_node = item_node->prev;
+            goto block_found;
+        }
+    }
+
+    prev_node = last_node;
+    next_node = NULL;
+
+block_found:
+    KernAux_Alloc_insert(alloc, new_node, prev_node, next_node);
+    KernAux_Alloc_defrag(alloc);
+
+    UNLOCK(alloc);
 }
 
 void *KernAux_Alloc_malloc(const KernAux_Alloc alloc, const size_t size)
@@ -61,17 +110,16 @@ void *KernAux_Alloc_malloc(const KernAux_Alloc alloc, const size_t size)
     KERNAUX_ASSERT(alloc);
     if (size == 0) return NULL;
 
-    KernAux_Alloc_Node node = NULL;
-    void *ptr = NULL;
+    LOCK(alloc);
 
-    // TODO: lock
+    KernAux_Alloc_Node node = NULL;
 
     for (
         KernAux_Alloc_Node item_node = alloc->head;
         item_node;
         item_node = item_node->next
     ) {
-        if (item_node->free && item_node->user_size >= size) {
+        if (item_node->size - NODE_HEADER_SIZE >= size) {
             node = item_node;
             break;
         }
@@ -79,31 +127,107 @@ void *KernAux_Alloc_malloc(const KernAux_Alloc alloc, const size_t size)
 
     if (node) {
         // Can we split the block?
-        if (node->actual_size - size >= MIN_ALLOC_SIZE) {
+        if (node->size - size >= MIN_SPLIT_SIZE) {
             KernAux_Alloc_Node new_node =
                 (KernAux_Alloc_Node)(((uintptr_t)&node->block) + size);
-            new_node->free = true;
-            new_node->actual_size = node->actual_size - size - ALLOC_HEADER_SIZE;
-            new_node->user_size   = node->user_size   - size - ALLOC_HEADER_SIZE;
-            new_node->next = node->next;
-            node->next = new_node;
+            node->size = NODE_HEADER_SIZE + size;
+            new_node->size = node->size - size - NODE_HEADER_SIZE;
+            KernAux_Alloc_insert(alloc, new_node, node, node->next);
         }
 
-        node->free = false;
-        ptr = &node->block;
+        KernAux_Alloc_remove(alloc, node);
     }
 
-    // TODO: unlock
+    UNLOCK(alloc);
 
-    return ptr;
+    if (node) {
+        return &node->block;
+    } else {
+        return NULL;
+    }
 }
 
 void KernAux_Alloc_free(const KernAux_Alloc alloc, void *const ptr)
 {
     KERNAUX_ASSERT(alloc);
+    if (!ptr) return;
+
+    LOCK(alloc);
 
-    // TODO: implement this
+    KernAux_Alloc_Node node =
+        CONTAINER_OF(ptr, struct KernAux_Alloc_Node, block);
+
+    KernAux_Alloc_Node last_node = NULL;
+
+    for (
+        KernAux_Alloc_Node item_node = alloc->head;
+        item_node;
+        item_node = item_node->next
+    ) {
+        last_node = item_node;
+
+        if (item_node > node) {
+            KernAux_Alloc_insert(alloc, node, item_node->prev, item_node);
+            goto block_added;
+        }
+    }
+
+    KernAux_Alloc_insert(alloc, node, last_node, NULL);
+
+block_added:
+    KernAux_Alloc_defrag(alloc);
+
+    UNLOCK(alloc);
+}
+
+void KernAux_Alloc_defrag(const KernAux_Alloc alloc)
+{
+    KERNAUX_ASSERT(alloc);
+
+    for (
+        KernAux_Alloc_Node item_node = alloc->head;
+        item_node;
+        item_node = item_node->next
+    ) {
+        const KernAux_Alloc_Node node = item_node->prev;
+        if (!node) continue;
+        if (((uintptr_t)node) + node->size != (uintptr_t)item_node) continue;
+
+        node->size += item_node->size;
+        KernAux_Alloc_remove(alloc, item_node);
+    }
+}
+
+void KernAux_Alloc_insert(
+    const KernAux_Alloc alloc,
+    const KernAux_Alloc_Node node,
+    const KernAux_Alloc_Node prev,
+    const KernAux_Alloc_Node next
+) {
+    KERNAUX_ASSERT(alloc);
+    KERNAUX_ASSERT(node);
+    KERNAUX_ASSERT(node != prev);
+    KERNAUX_ASSERT(node != next);
+    KERNAUX_ASSERT(!prev || prev->next == next);
+    KERNAUX_ASSERT(!next || next->prev == prev);
+
+    if (!prev) alloc->head = node;
+    node->next = next;
+    node->prev = prev;
+    if (node->next) node->next->prev = node;
+    if (node->prev) node->prev->next = node;
+}
+
+void KernAux_Alloc_remove(
+    const KernAux_Alloc alloc,
+    const KernAux_Alloc_Node node
+) {
+    KERNAUX_ASSERT(alloc);
+    KERNAUX_ASSERT(node);
+    KERNAUX_ASSERT(!node->next || node->next->prev == node);
+    KERNAUX_ASSERT(!node->prev || node->prev->next == node);
 
-    (void)alloc;
-    (void)ptr;
+    if (alloc->head == node) alloc->head = node->next;
+    if (node->next) node->next->prev = node->prev;
+    if (node->prev) node->prev->next = node->next;
 }
diff --git a/src/libc.h b/src/libc.h
index a749bd3b..b7415653 100644
--- a/src/libc.h
+++ b/src/libc.h
@@ -1,7 +1,7 @@
 // TODO: remove this file, require needed headers separately
 
-#ifndef KERNAUX_INCLUDED_LIBC
-#define KERNAUX_INCLUDED_LIBC
+#ifndef KERNAUX_INCLUDED_SRC_LIBC
+#define KERNAUX_INCLUDED_SRC_LIBC
 
 #ifdef __cplusplus
 extern "C" {


Test patch:
diff --git a/tests/Makefile.am b/tests/Makefile.am
index e866a74f..e7975ff7 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -12,6 +12,8 @@ if WITH_MULTIBOOT2
 noinst_PROGRAMS += multiboot2_header_print1
 multiboot2_header_print1_LDADD = $(top_builddir)/libkernaux.la
 multiboot2_header_print1_SOURCES = \
+	helper.c \
+	helper.h \
 	multiboot2_header_print1.c \
 	multiboot2_header_example1.h
 endif
@@ -24,6 +26,8 @@ if WITH_MULTIBOOT2
 noinst_PROGRAMS += multiboot2_header_print2
 multiboot2_header_print2_LDADD = $(top_builddir)/libkernaux.la
 multiboot2_header_print2_SOURCES = \
+	helper.c \
+	helper.h \
 	multiboot2_header_print2.c \
 	multiboot2_header_example2.h
 endif
@@ -36,6 +40,8 @@ if WITH_MULTIBOOT2
 noinst_PROGRAMS += multiboot2_info_print1
 multiboot2_info_print1_LDADD = $(top_builddir)/libkernaux.la
 multiboot2_info_print1_SOURCES = \
+	helper.c \
+	helper.h \
 	multiboot2_info_print1.c \
 	multiboot2_info_example1.h
 endif
@@ -48,6 +54,8 @@ if WITH_MULTIBOOT2
 noinst_PROGRAMS += multiboot2_info_print2
 multiboot2_info_print2_LDADD = $(top_builddir)/libkernaux.la
 multiboot2_info_print2_SOURCES = \
+	helper.c \
+	helper.h \
 	multiboot2_info_print2.c \
 	multiboot2_info_example2.h
 endif
@@ -59,7 +67,10 @@ endif
 if WITH_ALLOC
 TESTS += test_alloc
 test_alloc_LDADD = $(top_builddir)/libkernaux.la
-test_alloc_SOURCES = test_alloc.c
+test_alloc_SOURCES = \
+	helper.c \
+	helper.h \
+	test_alloc.c
 endif
 
 ################
@@ -69,7 +80,10 @@ endif
 if WITH_CMDLINE
 TESTS += test_cmdline
 test_cmdline_LDADD = $(top_builddir)/libkernaux.la
-test_cmdline_SOURCES = test_cmdline.c
+test_cmdline_SOURCES = \
+	helper.c \
+	helper.h \
+	test_cmdline.c
 endif
 
 ####################
@@ -81,6 +95,8 @@ if WITH_CMDLINE
 TESTS += test_cmdline_gen
 test_cmdline_gen_LDADD = $(top_builddir)/libkernaux.la
 test_cmdline_gen_SOURCES = \
+	helper.c \
+	helper.h \
 	test_cmdline_gen.c \
 	cmdline_gen.py \
 	cmdline_gen.jinja \
@@ -100,7 +116,10 @@ test_cmdline_gen.c: cmdline_gen.py cmdline_gen.jinja $(top_srcdir)/common/cmdlin
 if WITH_ELF
 TESTS += test_elf
 test_elf_LDADD = $(top_builddir)/libkernaux.la
-test_elf_SOURCES = test_elf.c
+test_elf_SOURCES = \
+	helper.c \
+	helper.h \
+	test_elf.c
 endif
 
 ############
@@ -110,7 +129,10 @@ endif
 if WITH_MBR
 TESTS += test_mbr
 test_mbr_LDADD = $(top_builddir)/libkernaux.la
-test_mbr_SOURCES = test_mbr.c
+test_mbr_SOURCES = \
+	helper.c \
+	helper.h \
+	test_mbr.c
 endif
 
 ###############
@@ -120,7 +142,10 @@ endif
 if WITH_MEMMAP
 TESTS += test_memmap
 test_memmap_LDADD = $(top_builddir)/libkernaux.la
-test_memmap_SOURCES = test_memmap.c
+test_memmap_SOURCES = \
+	helper.c \
+	helper.h \
+	test_memmap.c
 endif
 
 ##################################
@@ -131,6 +156,8 @@ if WITH_MULTIBOOT2
 TESTS += test_multiboot2_common_packing
 test_multiboot2_common_packing_LDADD = $(top_builddir)/libkernaux.la
 test_multiboot2_common_packing_SOURCES = \
+	helper.c \
+	helper.h \
 	test_multiboot2_common_packing.c \
 	multiboot2_header_example2.h \
 	multiboot2_info_example2.h
@@ -144,6 +171,8 @@ if WITH_MULTIBOOT2
 TESTS += test_multiboot2_header_helpers
 test_multiboot2_header_helpers_LDADD = $(top_builddir)/libkernaux.la
 test_multiboot2_header_helpers_SOURCES = \
+	helper.c \
+	helper.h \
 	test_multiboot2_header_helpers.c \
 	multiboot2_header_example1.h \
 	multiboot2_header_example2.h
@@ -159,7 +188,10 @@ test_multiboot2_header_print_DEPENDENCIES = \
 	multiboot2_header_print1 \
 	multiboot2_header_print2
 test_multiboot2_header_print_LDADD = $(top_builddir)/libkernaux.la
-test_multiboot2_header_print_SOURCES = test_multiboot2_header_print.c
+test_multiboot2_header_print_SOURCES = \
+	helper.c \
+	helper.h \
+	test_multiboot2_header_print.c
 endif
 
 #####################################
@@ -170,6 +202,8 @@ if WITH_MULTIBOOT2
 TESTS += test_multiboot2_header_validation
 test_multiboot2_header_validation_LDADD = $(top_builddir)/libkernaux.la
 test_multiboot2_header_validation_SOURCES = \
+	helper.c \
+	helper.h \
 	test_multiboot2_header_validation.c \
 	multiboot2_header_example1.h \
 	multiboot2_header_example2.h
@@ -183,6 +217,8 @@ if WITH_MULTIBOOT2
 TESTS += test_multiboot2_info_helpers
 test_multiboot2_info_helpers_LDADD = $(top_builddir)/libkernaux.la
 test_multiboot2_info_helpers_SOURCES = \
+	helper.c \
+	helper.h \
 	test_multiboot2_info_helpers.c \
 	multiboot2_info_example1.h \
 	multiboot2_info_example2.h
@@ -198,7 +234,10 @@ test_multiboot2_info_print_DEPENDENCIES = \
 	multiboot2_info_print1 \
 	multiboot2_info_print2
 test_multiboot2_info_print_LDADD = $(top_builddir)/libkernaux.la
-test_multiboot2_info_print_SOURCES = test_multiboot2_info_print.c
+test_multiboot2_info_print_SOURCES = \
+	helper.c \
+	helper.h \
+	test_multiboot2_info_print.c
 endif
 
 ###################################
@@ -209,6 +248,8 @@ if WITH_MULTIBOOT2
 TESTS += test_multiboot2_info_validation
 test_multiboot2_info_validation_LDADD = $(top_builddir)/libkernaux.la
 test_multiboot2_info_validation_SOURCES = \
+	helper.c \
+	helper.h \
 	test_multiboot2_info_validation.c \
 	multiboot2_info_example1.h \
 	multiboot2_info_example2.h
@@ -221,7 +262,10 @@ endif
 if WITH_NTOA
 TESTS += test_ntoa
 test_ntoa_LDADD = $(top_builddir)/libkernaux.la
-test_ntoa_SOURCES = test_ntoa.c
+test_ntoa_SOURCES = \
+	helper.c \
+	helper.h \
+	test_ntoa.c
 endif
 
 ####################
@@ -232,7 +276,10 @@ if ENABLE_DEBUG
 if WITH_NTOA
 TESTS += test_ntoa_assert
 test_ntoa_assert_LDADD = $(top_builddir)/libkernaux.la
-test_ntoa_assert_SOURCES = test_ntoa_assert.c
+test_ntoa_assert_SOURCES = \
+	helper.c \
+	helper.h \
+	test_ntoa_assert.c
 endif
 endif
 
@@ -243,7 +290,10 @@ endif
 if WITH_PFA
 TESTS += test_pfa
 test_pfa_LDADD = $(top_builddir)/libkernaux.la
-test_pfa_SOURCES = test_pfa.c
+test_pfa_SOURCES = \
+	helper.c \
+	helper.h \
+	test_pfa.c
 endif
 
 ###################
@@ -254,7 +304,10 @@ if ENABLE_DEBUG
 if WITH_PFA
 TESTS += test_pfa_assert
 test_pfa_assert_LDADD = $(top_builddir)/libkernaux.la
-test_pfa_assert_SOURCES = test_pfa_assert.c
+test_pfa_assert_SOURCES = \
+	helper.c \
+	helper.h \
+	test_pfa_assert.c
 endif
 endif
 
@@ -267,6 +320,8 @@ if WITH_PRINTF_FMT
 TESTS += test_printf_fmt_gen
 test_printf_fmt_gen_LDADD = $(top_builddir)/libkernaux.la
 test_printf_fmt_gen_SOURCES = \
+	helper.c \
+	helper.h \
 	test_printf_fmt_gen.c \
 	printf_fmt_gen.py \
 	printf_fmt_gen.jinja \
@@ -288,6 +343,8 @@ if WITH_PRINTF
 TESTS += test_printf_gen
 test_printf_gen_LDADD = $(top_builddir)/libkernaux.la
 test_printf_gen_SOURCES = \
+	helper.c \
+	helper.h \
 	test_printf_gen.c \
 	printf_gen.py \
 	printf_gen.jinja \
@@ -308,5 +365,8 @@ test_printf_gen.c: printf_gen.py printf_gen.jinja $(top_srcdir)/common/printf.ym
 if WITH_UNITS
 TESTS += test_units_human
 test_units_human_LDADD = $(top_builddir)/libkernaux.la
-test_units_human_SOURCES = test_units_human.c
+test_units_human_SOURCES = \
+	helper.c \
+	helper.h \
+	test_units_human.c
 endif
diff --git a/tests/helper.c b/tests/helper.c
new file mode 100644
index 00000000..194afbc1
--- /dev/null
+++ b/tests/helper.c
@@ -0,0 +1,24 @@
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <kernaux/assert.h>
+
+#include <stdio.h>
+#include <stdlib.h>
+
+static void assert_cb_abort(const char *file, int line, const char *msg);
+
+void setup_assert_abort()
+{
+    kernaux_assert_cb = assert_cb_abort;
+}
+
+void assert_cb_abort(
+    const char *const file,
+    const int line,
+    const char *const msg
+) {
+    fprintf(stderr, "%s:%d:%s\n", file, line, msg);
+    abort();
+}
diff --git a/tests/helper.h b/tests/helper.h
new file mode 100644
index 00000000..5399734e
--- /dev/null
+++ b/tests/helper.h
@@ -0,0 +1,14 @@
+#ifndef KERNAUX_INCLUDED_TESTS_HELPER
+#define KERNAUX_INCLUDED_TESTS_HELPER
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void setup_assert_abort();
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/tests/test_alloc.c b/tests/test_alloc.c
index 8bf6a13f..35c52ab4 100644
--- a/tests/test_alloc.c
+++ b/tests/test_alloc.c
@@ -2,15 +2,29 @@
 #include "config.h"
 #endif
 
+#include "helper.h"
+
 #include <kernaux/alloc.h>
 
 #include <assert.h>
+#include <stddef.h>
+
+static void test_default();
+static void test_cross_zone_defrag();
 
 int main()
+{
+    setup_assert_abort();
+    test_default();
+    test_cross_zone_defrag();
+    return 0;
+}
+
+void test_default()
 {
     char memory_block[1000];
-    struct KernAux_Alloc alloc = KernAux_Alloc_create();
-    KernAux_Alloc_add_memory_block(&alloc, memory_block, sizeof(memory_block));
+    struct KernAux_Alloc alloc = KernAux_Alloc_create(NULL);
+    KernAux_Alloc_add_zone(&alloc, memory_block, sizeof(memory_block));
 
     char *const ptr1 = KernAux_Alloc_malloc(&alloc, 100);
     assert(ptr1);
@@ -32,5 +46,37 @@ int main()
     assert(ptr4 > ptr3);
     assert(ptr4 < &memory_block[1000]);
 
-    return 0;
+    KernAux_Alloc_free(&alloc, ptr2);
+    KernAux_Alloc_free(&alloc, ptr3);
+
+    char *const ptr5 = KernAux_Alloc_malloc(&alloc, 100);
+    assert(ptr5 == ptr2);
+
+    char *const ptr6 = KernAux_Alloc_malloc(&alloc, 100);
+    assert(ptr6 == ptr3);
+
+    KernAux_Alloc_free(&alloc, ptr2);
+    KernAux_Alloc_free(&alloc, ptr3);
+
+    char *const ptr7 = KernAux_Alloc_malloc(&alloc, 200);
+    assert(ptr7 == ptr2);
+}
+
+void test_cross_zone_defrag()
+{
+    char zone[1000];
+    struct KernAux_Alloc alloc = KernAux_Alloc_create(NULL);
+    KernAux_Alloc_add_zone(&alloc, &zone[0],   500);
+    KernAux_Alloc_add_zone(&alloc, &zone[500], 500);
+
+    size_t nodes_count = 0;
+    for (
+        KernAux_Alloc_Node item_node = alloc.head;
+        item_node;
+        item_node = item_node->next
+    ) {
+        ++nodes_count;
+    }
+
+    assert(nodes_count == 1);
 }