P3230 Nikolaev Pavel

src/CMakeLists.txt

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

src/main.c

+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "mem.h"
+
+void debug(const char *fmt, ...);
+
+void test_1() {
+  debug("Test allocating 3 heaps\n");
+
+  void *heap = heap_init(0);
+
+  void *block_1 = _malloc(sizeof(uint64_t));
+  void *block_2 = _malloc(sizeof(uint64_t));
+  void *block_3 = _malloc(sizeof(uint64_t));
+
+  debug_heap(stdout, heap);
+
+  _free(block_1);
+  _free(block_2);
+  _free(block_3);
+
+  debug_heap(stdout, heap);
+
+  heap_term();
+
+  debug("\n");
+}
+
+void test_2() {
+  debug("Test freeing one\n");
+
+  void *heap = heap_init(0);
+
+  _malloc(sizeof(uint64_t));
+  void *block = _malloc(sizeof(uint64_t));
+  _malloc(sizeof(uint64_t));
+
+  debug_heap(stdout, heap);
+
+  _free(block);
+
+  debug_heap(stdout, heap);
+
+  heap_term();
+
+  debug("\n");
+}
+
+void test_3() {
+  debug("Test freeing two\n");
+
+  void *heap = heap_init(0);
+
+  _malloc(sizeof(uint64_t));
+  void *block_1 = _malloc(sizeof(uint64_t));
+  void *block_2 = _malloc(sizeof(uint64_t));
+
+  debug_heap(stdout, heap);
+
+  _free(block_1);
+  _free(block_2);
+
+  debug_heap(stdout, heap);
+
+  heap_term();
+
+  debug("\n");
+}
+
+void test_4() {
+  debug("Test memory expansion\n");
+
+  void* heap = heap_init(0);
+
+  while (_malloc(sizeof(uint64_t)) != NULL)
+    ;
+  
+  debug_heap(stdout, heap);
+
+  void* block = _malloc(sizeof(uint64_t));
+
+  debug_heap(stdout, heap);
+
+  _free(block);
+
+  debug_heap(stdout, heap);
+
+  heap_term();
+
+  debug("\n");
+}
+
+void test_5() {
+  debug("Test memory allocation in different region\n");
+
+  void* heap = heap_init(0);
+
+  while (_malloc(sizeof(uint64_t)) != NULL)
+    ;
+
+  debug_heap(stdout, heap);
+  
+  void* block = _malloc(sizeof(uint64_t));
+  void* block_2 = _malloc(sizeof(uint64_t));
+
+  debug_heap(stdout, heap);
+
+  _free(block);
+  _free(block_2);
+
+  debug_heap(stdout, heap);
+
+  heap_term();
+
+  debug("\n");
+}
+
+int main() {
+  test_1();
+  test_2();
+  test_3();
+  test_4();
+  test_5();
+  return 0;
+}
\ No newline at end of file

src/mem.c

   return mmap( (void*) addr, length, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS | additional_flags , -1, 0 );
 }
 
+
 /*  аллоцировать регион памяти и инициализировать его блоком */
 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);
+
+  void* mapped_addr = map_pages(addr, region_size, MAP_FIXED_NOREPLACE);
+
+  mapped_addr = mapped_addr == MAP_FAILED ? map_pages(addr, region_size, 0) : mapped_addr;
+
+  struct region result_region = {mapped_addr, region_size, mapped_addr == addr};
+
+  if(region_is_invalid(&result_region) || mapped_addr == MAP_FAILED) return REGION_INVALID;
+
+  block_init(mapped_addr, (block_size){result_region.size}, NULL);
+  return result_region;
 }
 
 static void* block_after( struct block_header const* block )         ;
   if ( region_is_invalid(&region) ) return NULL;
 
   return region.addr;
-}
+};
 
-/*  освободить всю память, выделенную под кучу */
-void heap_term( ) {
-  /*  ??? */
-}
 
 #define BLOCK_MIN_CAPACITY 24
 
 }
 
 static bool split_if_too_big( struct block_header* block, size_t query ) {
-  /*  ??? */
+  if (block && block_splittable(block, query)) 
+  {
+    void* second_half = (block->contents + query);
+
+    block_init(second_half, (block_size) {block->capacity.bytes - query}, block->next);
+
+    block->next = second_half;
+    block->capacity.bytes = query;
+
+    return true;
+  }
+  return false;
 }
 
 
 static void* block_after( struct block_header const* block )              {
   return  (void*) (block->contents + block->capacity.bytes);
 }
-static bool blocks_continuous (
-                               struct block_header const* fst,
-                               struct block_header const* snd ) {
+
+static bool blocks_continuous(struct block_header const *fst,
+                              struct block_header const *snd) {
   return (void*)snd == block_after(fst);
 }
 
 }
 
 static bool try_merge_with_next( struct block_header* block ) {
-  /*  ??? */
+  if (block && block->next != NULL && mergeable(block, block->next))
+  {
+    block->capacity.bytes += size_from_capacity((block->next)->capacity).bytes;
+    block->next = (block->next)->next;
+
+    return true;
+  }
+  return false;
 }
 
+void heap_term( ) {
+  struct block_header* block = HEAP_START;
+  while (block != NULL)
+  {
+    _free(block->contents);
+    block = block->next;
+  }
+  
+  block = HEAP_START;
+
+  while (block)
+  {
+    while (try_merge_with_next(block));
+    struct block_header* next = block->next;
+    munmap(block, round_pages(size_from_capacity(block->capacity).bytes));
+    block = next;
+  }
+}
 
 /*  --- ... ecли размера кучи хватает --- */
 
 
 
 static struct block_search_result find_good_or_last  ( struct block_header* restrict block, size_t sz )    {
-  /*??? */
+  // In NULL case
+  if (!block) return (struct block_search_result) {BSR_CORRUPTED, NULL};
+
+  struct block_search_result result = {BSR_FOUND_GOOD_BLOCK, NULL};
+  
+  while (true)
+  {
+    result.block = block;
+    if (block->is_free)
+    {
+      while (try_merge_with_next(block));
+      if (block_is_big_enough(sz, block)) return result;
+    }
+
+    if (!block->next) break;
+    block = block->next;
+  }
+  
+  return (struct block_search_result) {BSR_REACHED_END_NOT_FOUND, block};
 }
 
 /*  Попробовать выделить память в куче начиная с блока `block` не пытаясь расширить кучу
  Можно переиспользовать как только кучу расширили. */
 static struct block_search_result try_memalloc_existing ( size_t query, struct block_header* block ) {
-  
+  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 ) {
-  /*  ??? */
+  struct region region = alloc_region(block_after(last), query);
+
+  last->next = region.addr;
+
+  return try_merge_with_next(last) ? last : last->next;
 }
 
 /*  Реализует основную логику 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);
+
+  if (result.type == BSR_CORRUPTED) return NULL;
+
+  if (result.type == BSR_REACHED_END_NOT_FOUND) {
+    grow_heap(result.block, query);
+    result = try_memalloc_existing(query, heap_start);
+  }
 
-  /*  ??? */
+  if (result.type == BSR_FOUND_GOOD_BLOCK) {
+    return result.block;
+  }
 
+  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));
 }

[Pavel Nikolaev]

@Aglaia @andrew лаба загружена