Emil Askarov P3210

src/mem.c

 
-/*  освободить всю память, выделенную под кучу */
-void heap_term( ) {
-  /*  ??? */
-}
-
 #define BLOCK_MIN_CAPACITY 24
 
 /*  --- Разделение блоков (если найденный свободный блок слишком большой )--- */
 
 static bool block_splittable( struct block_header* restrict block, size_t query) {
-  return block-> is_free && query + offsetof( struct block_header, contents ) + BLOCK_MIN_CAPACITY <= block->capacity.bytes;
+  return block->is_free && query + offsetof( struct block_header, contents ) + BLOCK_MIN_CAPACITY <= block->capacity.bytes;
 }
 
 static bool split_if_too_big( struct block_header* block, size_t query ) {

src/mem.c

-/*  освободить всю память, выделенную под кучу */
-void heap_term( ) {
-  /*  ??? */
-}
-
 #define BLOCK_MIN_CAPACITY 24
 
 /*  --- Разделение блоков (если найденный свободный блок слишком большой )--- */
 
 static bool block_splittable( struct block_header* restrict block, size_t query) {
-  return block-> is_free && query + offsetof( struct block_header, contents ) + BLOCK_MIN_CAPACITY <= block->capacity.bytes;
+  return block->is_free && query + offsetof( struct block_header, contents ) + BLOCK_MIN_CAPACITY <= block->capacity.bytes;
 }
 
 static bool split_if_too_big( struct block_header* block, size_t query ) {
-  /*  ??? */

src/main.c

+}
+
+void test_allocated_two_blocks_then_released() {
+    void *b1 = _malloc(BASE_ALLOC_SIZE);
+    void *b2 = _malloc(BASE_ALLOC_SIZE*2);
+    void *b3 = _malloc(BASE_ALLOC_SIZE*3);
+    assert(b1 != NULL);
+    assert(b2 != NULL);
+    assert(b3 != NULL);
+
+    _free(b1);
+    _free(b2);
+
+    assert(b2 != NULL);
+
+    _free(b2);

src/main.c

+    _free(b1);
+    heap_term();
+}
+
+void test_allocated_two_blocks_then_released() {
+    void *b1 = _malloc(BASE_ALLOC_SIZE);
+    void *b2 = _malloc(BASE_ALLOC_SIZE*2);
+    void *b3 = _malloc(BASE_ALLOC_SIZE*3);
+    assert(b1 != NULL);
+    assert(b2 != NULL);
+    assert(b3 != NULL);
+
+    _free(b1);
+    _free(b2);
+
+    assert(b2 != NULL);

src/main.c

+    assert(b2 != NULL);
+
+    _free(b2);
+    heap_term();
+}
+
+void test_grow_heap_extended(void *heap) {
+    size_t initial_region_size = ((struct region *) heap)->size;
+
+    void *block = _malloc(5 * TEST_HEAP_SIZE);
+    struct block_header *new_block_header = get_header(block);
+    size_t expanded_region_size = ((struct region *) heap)->size;
+
+    assert(initial_region_size < expanded_region_size);
+    assert(new_block_header);
+    assert(new_block_header->capacity.bytes >= 5 * TEST_HEAP_SIZE);

src/CMakeLists.txt

 file(GLOB_RECURSE sources CONFIGURE_DEPENDS *.c *.h)
 list(FILTER sources EXCLUDE REGEX main.c)
 
-add_library(memalloc STATIC ${sources})
+add_library(memalloc STATIC ${sources} main.c)
 target_include_directories(memalloc PUBLIC .)
 
 if(EXISTS main.c)

src/main.c

+#include "mem.h"
+#include "mem_internals.h"
+#include <assert.h>
+#include <stddef.h>
+#include <stdint.h>
+
+#define TEST_HEAP_SIZE 2048
+#define BASE_ALLOC_SIZE 200
+
+static struct block_header* get_header(void *ptr) {
+    return (struct block_header *) ((uint8_t*) ptr - offsetof(struct block_header, contents));
+}
+
+void* test_init_heap() {
+    void *heap = heap_init(TEST_HEAP_SIZE);
+    assert(heap != NULL);
+    return heap;
+}
+
+void test_memory_allocation() {
+    void *allocated_block = _malloc(BASE_ALLOC_SIZE);
+    assert(allocated_block != NULL);
+    _free(allocated_block);
+    heap_term();
+}
+
+void test_allocated_one_block_then_released() {
+    void *b1 = _malloc(BASE_ALLOC_SIZE);
+    void *b2 = _malloc(BASE_ALLOC_SIZE * 2);
+
+    _free(b2);
+
+    struct block_header *header1 = get_header(b1);
+    struct block_header *header2 = get_header(b2);
+
+    assert(header1->next == header2);
+    assert(header2->is_free);
+
+    heap_term();
+}
+
+void test_allocated_two_blocks_then_released() {
+    void *b1 = _malloc(BASE_ALLOC_SIZE);
+    void *b2 = _malloc(BASE_ALLOC_SIZE*2);
+    void *b3 = _malloc(BASE_ALLOC_SIZE*3);
+    assert(b1 != NULL);
+    assert(b2 != NULL);
+    assert(b3 != NULL);
+
+    struct block_header* header1 = get_header(b1);
+    struct block_header* header2 = get_header(b2);
+    struct block_header* header3 = get_header(b3);
+
+    assert(header1->next == header2);
+    assert(header2->next == header3);
+
+    _free(b1);
+    _free(b2);
+
+    assert(header1->is_free);
+    assert(header2->is_free);
+
+    heap_term();
+}
+
+void test_grow_heap_extended(void *heap) {
+    size_t initial_region_size = ((struct region *) heap)->size;
+
+    void *block = _malloc(5 * TEST_HEAP_SIZE);
+    struct block_header *new_block_header = get_header(block);
+    size_t expanded_region_size = ((struct region *) heap)->size;
+
+    assert(initial_region_size < expanded_region_size);
+    assert(new_block_header);
+    assert(new_block_header->capacity.bytes == 5 * TEST_HEAP_SIZE);
+
+    _free(block);
+    heap_term();
+}
+
+void test_grow_heap_new_region() {
+    void *hole = mmap(HEAP_START + REGION_MIN_SIZE, BASE_ALLOC_SIZE, PROT_READ | PROT_WRITE, MAP_PRIVATE, -1, 0);
+    assert(hole == HEAP_START + REGION_MIN_SIZE);
+
+    void *new_block = _malloc(REGION_MIN_SIZE - offsetof(struct block_header, contents));
+    struct block_header *new_block_header = get_header(new_block);
+
+    assert(new_block != NULL);
+    assert(new_block != hole);
+    assert(new_block_header->capacity.bytes >= (REGION_MIN_SIZE - offsetof(struct block_header, contents)));
+
+    munmap(hole, BASE_ALLOC_SIZE);
+    _free(new_block);
+    heap_term();
+}
+
+int main() {
+    void *heap = test_init_heap();
+    test_memory_allocation();
+    test_allocated_one_block_then_released();
+    test_allocated_two_blocks_then_released();
+    test_grow_heap_extended(heap);
+    test_grow_heap_new_region();
+    return 0;
+}
\ No newline at end of file

src/mem.c

 
 /*  аллоцировать регион памяти и инициализировать его блоком */
 static struct region alloc_region  ( void const * addr, size_t query ) {
-  /*  ??? */
+  size_t region_size = region_actual_size(size_from_capacity((block_capacity) {query}).bytes);
+  struct block_header* region = map_pages(addr, region_size, MAP_FIXED);
+  if (region == MAP_FAILED) {
+      region = map_pages(addr, region_size, 0);
+  }
+  if (region == MAP_FAILED) {
+      return REGION_INVALID;
+  }
+  block_init(region, (block_size) {region_size}, NULL);
+  return (struct region) {
+      .addr = region,
+      .size = region_size,
+      .extends = region == addr
+  };
 }
 
 static void* block_after( struct block_header const* block )         ;
   return region.addr;
 }
 
-/*  освободить всю память, выделенную под кучу */
-void heap_term( ) {
-  /*  ??? */
-}
-
 #define BLOCK_MIN_CAPACITY 24
 
 /*  --- Разделение блоков (если найденный свободный блок слишком большой )--- */
 
 static bool block_splittable( struct block_header* restrict block, size_t query) {
-  return block-> is_free && query + offsetof( struct block_header, contents ) + BLOCK_MIN_CAPACITY <= block->capacity.bytes;
+  return block != NULL && block->is_free && query + offsetof( struct block_header, contents ) + BLOCK_MIN_CAPACITY <= block->capacity.bytes;
 }
 
 static bool split_if_too_big( struct block_header* block, size_t query ) {
-  /*  ??? */
+    if (block == NULL || !block_splittable(block, query)) {
+        return false;
+    }
+    query = size_max(query, BLOCK_MIN_CAPACITY);
+    size_t capacity = block->capacity.bytes;
+    block->capacity = (block_capacity) {query};
+    block_init(block_after(block), (block_size) {capacity - query}, block->next);
+    block->next = block_after(block);
+    return true;
 }
 
 
 }
 
 static bool try_merge_with_next( struct block_header* block ) {
-  /*  ??? */
+    struct block_header* next_block = block->next;
+
+    if (next_block == NULL || !mergeable(block, next_block)) {
+        return false;
+    }
+    block->capacity.bytes += size_from_capacity(next_block->capacity).bytes;
+    block->next = next_block->next;
+    return true;
 }
 
 
   struct block_header* block;
 };
 
-
-static struct block_search_result find_good_or_last  ( struct block_header* restrict block, size_t sz )    {
-  /*??? */
+static struct block_search_result CORRUPTED = {BSR_CORRUPTED};
+
+
+static struct block_search_result find_good_or_last  ( struct block_header* restrict block, size_t sz ) {
+    if (block == NULL) {
+        return CORRUPTED;
+    }
+    while (true) {
+        while (try_merge_with_next(block)) {
+        }
+        if (block->is_free && block_is_big_enough(size_max(sz, BLOCK_MIN_CAPACITY), block)) {
+            return (struct block_search_result) {
+                    .type = BSR_FOUND_GOOD_BLOCK,
+                    .block = block
+            };
+        }
+        if (block->next == NULL) {
+            return (struct block_search_result) {
+                    .type = BSR_REACHED_END_NOT_FOUND,
+                    .block = block
+            };
+        }
+        block = block->next;
+    }
 }
 
 /*  Попробовать выделить память в куче начиная с блока `block` не пытаясь расширить кучу
  Можно переиспользовать как только кучу расширили. */
 static struct block_search_result try_memalloc_existing ( size_t query, struct block_header* block ) {
-  
+    if (block == NULL) {
+        return CORRUPTED;
+    }
+    struct block_search_result result = find_good_or_last(block, query);
+    if (result.type == BSR_FOUND_GOOD_BLOCK) {
+        split_if_too_big(result.block, query);
+        result.block->is_free = false;
+    }
+    return result;
 }
 
 
 
 static struct block_header* grow_heap( struct block_header* restrict last, size_t query ) {
-  /*  ??? */
+    if (last == NULL) return NULL;
+
+    struct region region = alloc_region(block_after(last), query);
+    if (region_is_invalid(&region)) {
+        return NULL;
+    }
+    last->next = region.addr;
+    if (region.extends && try_merge_with_next(last)) {
+        return last;
+    }
+    return region.addr;
 }
 
 /*  Реализует основную логику malloc и возвращает заголовок выделенного блока */
 static struct block_header* memalloc( size_t query, struct block_header* heap_start) {
-
-  /*  ??? */
-
+    query = size_max(query, BLOCK_MIN_CAPACITY);
+    struct block_search_result result = try_memalloc_existing(query, heap_start);
+
+    switch (result.type) {
+        case BSR_FOUND_GOOD_BLOCK: {
+            return result.block;
+        }
+        case BSR_REACHED_END_NOT_FOUND: {
+            result = try_memalloc_existing(query, grow_heap(result.block, query));
+            if (result.type == BSR_FOUND_GOOD_BLOCK) {
+                return result.block;
+            }
+            return NULL;
+        }
+        case BSR_CORRUPTED: {
+            return NULL;
+        }
+    }
 }
 
 void* _malloc( size_t query ) {
   if (!mem) return ;
   struct block_header* header = block_get_header( mem );
   header->is_free = true;
-  /*  ??? */
+  while (try_merge_with_next(header)) {
+  }
+}
+
+/*  освободить всю память, выделенную под кучу */
+void heap_term() {
+    struct block_header* l = HEAP_START;
+    while (l != NULL) {
+        size_t length = size_from_capacity(l->capacity).bytes;
+        struct block_header* r = l;
+        while (r->next != NULL && blocks_continuous(r, r->next)) {
+            r = r->next;
+            length += size_from_capacity(r->capacity).bytes;
+        }
+        r = r->next;
+        munmap(l, length);
+        l = r;
+    }
 }

[Marat Khasanshin]

было бы хорошо проверять block == NULL

[Emil Askarov]

исправил

[Marat Khasanshin]

нужно, чтобы сплитилось на максимальное из query и BLOCK_MIN_CAPACITY

[Emil Askarov]

в эту функцию уже передается конечно максимум из query и BLOCK_MIN_CAPACITY, но в целом соглашусь

исправил

[Marat Khasanshin]

вызов функции к уже освобожденному блоку

[Emil Askarov]

косяк, исправил

[Marat Khasanshin]

тут как в пред тесте лучше проверять не на NULL (это уже проверено 3 строками выше), а является ли блок свободным (через хедер)

[Emil Askarov]

исправил

[Marat Khasanshin]

должно быть строгое равенство (выделяется памяти ровно)

[Emil Askarov]

конкретно с данными константами - да, но тут на случай если запрашиваемый размер будет меньше BLOCK_MIN_CAPACITY, но это да, слишком дурацкий случай

исправил, спасибо

[Emil Askarov]

@368988 исправил замечания, проверьте, пожалуйста

[Marat Khasanshin]

Замечания учтены, все исправлено.

[Emil Askarov]

@andrew

[Andrey Zhdanov]

Принято

[Marat Khasanshin]

было бы хорошо проверять block == NULL

[Emil Askarov]

исправил

[Marat Khasanshin]

нужно, чтобы сплитилось на максимальное из query и BLOCK_MIN_CAPACITY

[Emil Askarov]

в эту функцию уже передается конечно максимум из query и BLOCK_MIN_CAPACITY, но в целом соглашусь

исправил