Dubuk Daniil P3219

src/CMakeLists.txt

 add_library(memalloc STATIC ${sources})
 target_include_directories(memalloc PUBLIC .)
 
-if(EXISTS main.c)
+if(EXISTS ${CMAKE_CURRENT_SOURCE_DIR}/main.c)
     add_executable(memalloc_exe main.c)
     target_link_libraries(memalloc_exe PRIVATE memalloc)
     set_target_properties(memalloc_exe PROPERTIES OUTPUT_NAME memalloc)

src/main.c

+#include "mem.h"
+#include <assert.h>
+#include <malloc.h>
+
+void success_alloc();
+void free_one_block();
+void free_two_blocks();
+void expand_old_region();
+void expand_old_region_v2();
+
+int main() {
+    printf("Tests started.\n");
+
+    success_alloc();
+    free_one_block();
+    free_two_blocks();
+    expand_old_region();
+    expand_old_region_v2();
+}
+
+void success_alloc() {
+    void *heap = heap_init(8175);
+
+    assert(heap);
+    debug_heap(stdout, heap);
+
+    void *block = _malloc(32);
+    assert(block);
+    debug_heap(stdout, heap);
+
+    _free(block);
+    debug_heap(stdout, heap);
+    heap_term();
+    printf("---------Test 1: succeed---------\n");
+}
+
+void free_one_block() {
+    void *heap = heap_init(8175);
+    debug_heap(stdout, heap);
+
+    void *block1 = _malloc(32);
+    void *block2 = _malloc(32);
+    void *block3 = _malloc(32);
+    void *block4 = _malloc(32);
+
+    debug_heap(stdout, heap);
+    
+    assert(block1);
+    assert(block2);
+    assert(block3);
+    assert(block4);
+
+    _free(block2);
+    debug_heap(stdout, heap);
+
+    _free(block1);
+    _free(block3);
+    _free(block4);
+    heap_term();
+    printf("---------Test 2: succeed---------\n");
+}
+
+void free_two_blocks() {
+    void *heap = heap_init(8175);
+    debug_heap(stdout, heap);
+
+    void *block1 = _malloc(32);
+    void *block2 = _malloc(32);
+    void *block3 = _malloc(32);
+    void *block4 = _malloc(32);
+
+    debug_heap(stdout, heap);
+    
+    assert(block1);
+    assert(block2);
+    assert(block3);
+    assert(block4);
+
+    _free(block3);
+    _free(block2);
+
+    debug_heap(stdout, heap);
+
+    _free(block1);
+    _free(block4);
+    heap_term();
+    printf("---------Test 3: succeed---------\n");
+}
+
+void expand_old_region() {
+    void *heap = heap_init(8175);
+    debug_heap(stdout, heap);
+
+    void *block1 = _malloc(8176);
+    debug_heap(stdout, heap);
+    assert(block1);
+    _free(block1);
+    heap_term();
+    printf("---------Test 4: succeed---------\n");
+}
+
+void expand_old_region_v2() {
+    const int h_size = 1024 * 8;
+    const int h_cap = h_size - 17;
+    const int block_size = 1024;
+
+    void *heap = heap_init(h_cap);
+    debug_heap(stdout, heap);
+
+    void* block_1 = _malloc(h_cap);
+    assert(block_1);
+    (void) mmap((void*)HEAP_START + h_size, block_size, PROT_READ | PROT_WRITE, MAP_PRIVATE, -1, 0);
+    debug_heap(stdout, heap);
+
+    void* block_2 = _malloc(block_size);
+    assert(block_2);
+    debug_heap(stdout, heap);
+
+    _free(block_1);
+    _free(block_2);
+
+    heap_term();
+    printf("---------Test 5: succeed---------\n");
+}

src/mem.c

 extern inline block_size size_from_capacity( block_capacity cap );
 extern inline block_capacity capacity_from_size( block_size sz );
 
+static bool blocks_continuous (struct block_header const* fst, struct block_header const* snd );
 static bool            block_is_big_enough( size_t query, struct block_header* block ) { return block->capacity.bytes >= query; }
 static size_t          pages_count   ( size_t mem )                      { return mem / getpagesize() + ((mem % getpagesize()) > 0); }
 static size_t          round_pages   ( size_t mem )                      { return getpagesize() * pages_count( mem ) ; }
 
 /*  аллоцировать регион памяти и инициализировать его блоком */
 static struct region alloc_region  ( void const * addr, size_t query ) {
-  /*  ??? */
+  size_t reg_size = region_actual_size( size_from_capacity( (block_capacity){query} ).bytes );
+  void* new_adrr = map_pages( addr, reg_size, MAP_FIXED_NOREPLACE );
+
+  if (new_adrr == MAP_FAILED)
+    new_adrr = map_pages( addr, reg_size, 0 );
+  
+  if (new_adrr == MAP_FAILED)
+    return REGION_INVALID;
+  
+  block_init( new_adrr, (block_size) { reg_size }, NULL );
+  return (struct region) { .addr = new_adrr, .size = reg_size, .extends = (new_adrr == addr) };
 }
 
 static void* block_after( struct block_header const* block )         ;
 
 /*  освободить всю память, выделенную под кучу */
 void heap_term( ) {
-  /*  ??? */
+  struct block_header* current_block = (struct block_header*) HEAP_START;
+  void* reg_start = HEAP_START;
+  size_t reg_size = 0;
+
+  struct block_header* next_block = NULL;
+  while (current_block) {
+    reg_size += size_from_capacity( current_block->capacity ).bytes;
+    next_block = current_block->next;
+
+    if (next_block == NULL || !blocks_continuous( current_block, next_block )) {
+      munmap( reg_start, reg_size );
+      reg_start = next_block;
+      reg_size = 0;
+    }
+
+    current_block = next_block;
+  }
 }
 
 #define BLOCK_MIN_CAPACITY 24
 }
 
 static bool split_if_too_big( struct block_header* block, size_t query ) {
-  /*  ??? */
+  if (!block || !block_splittable( block, query ))
+    return false;
+  
+  query = size_max( query, BLOCK_MIN_CAPACITY );
+  block_size size_1 = size_from_capacity( (block_capacity){ query } );
+  block_size size_2 = (block_size) { size_from_capacity( block->capacity ).bytes - size_1.bytes };
+
+  block_init( block->contents + query, size_2, block->next );
+  block_init( block, size_1, block->contents + query );
+  return true;
 }
 
 
 }
 
 static bool try_merge_with_next( struct block_header* block ) {
-  /*  ??? */
+  if (!block || !block->next || !mergeable( block, block->next ))
+    return false;
+  
+  block->capacity.bytes += size_from_capacity( block->next->capacity ).bytes;
+  block->next = block->next->next;
+  return true;
 }
 
 
 };
 
 
-static struct block_search_result find_good_or_last  ( struct block_header* restrict block, size_t sz )    {
-  /*??? */
+static struct block_search_result find_good_or_last  ( struct block_header* restrict block, size_t sz ) {
+  if (!block)
+    return (struct block_search_result) { .type = BSR_CORRUPTED };
+  
+  while(block) {
+    while(try_merge_with_next( block ));
+    
+    if (block->is_free && block_is_big_enough( sz, block ))
+      return (struct block_search_result) { .type = BSR_FOUND_GOOD_BLOCK, .block = block };
+    
+    if (!block->next)
+      break;
+    
+    block = block->next;
+  }
+
+  return (struct block_search_result) { .block = block, .type = BSR_REACHED_END_NOT_FOUND };
 }
 
 /*  Попробовать выделить память в куче начиная с блока `block` не пытаясь расширить кучу
  Можно переиспользовать как только кучу расширили. */
 static struct block_search_result try_memalloc_existing ( size_t query, struct block_header* block ) {
+  struct block_search_result res = find_good_or_last( block, query );
+  if (res.type != BSR_FOUND_GOOD_BLOCK)
+    return res;
   
+  split_if_too_big( res.block, query );
+  while(try_merge_with_next( res.block->next ));
+
+  res.block->is_free = false;
+  return res;
 }
 
 
 
 static struct block_header* grow_heap( struct block_header* restrict last, size_t query ) {
-  /*  ??? */
+  if (!last)
+    return NULL;
+  
+  struct region reg = alloc_region( block_after( last ), query );
+  last->next = reg.addr;
+  
+  if (try_merge_with_next( last ))
+    return last;
+  
+  return last->next;
 }
 
 /*  Реализует основную логику malloc и возвращает заголовок выделенного блока */
 static struct block_header* memalloc( size_t query, struct block_header* heap_start) {
-
-  /*  ??? */
-
+  if (!heap_start)
+    return NULL;
+  
+  query = size_max( query, BLOCK_MIN_CAPACITY );
+  struct block_search_result res = try_memalloc_existing(query, heap_start);
+  switch(res.type) {
+    case BSR_FOUND_GOOD_BLOCK:
+      return res.block;
+    
+    case BSR_CORRUPTED:
+      return NULL;
+    
+    case BSR_REACHED_END_NOT_FOUND:
+      heap_start = grow_heap( res.block, query );
+      return heap_start ? try_memalloc_existing( query, heap_start ).block : heap_start;
+  }
+
+  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 ));
 }

[Daniil Dubuk]

@Stt1xX проверяйте, сделал

[Timur Rameev]

Всё хорошо, изменения приняты. @andrew Добрый день, Вы не могли бы принять?

[Andrey Zhdanov]

Принято