Башаримов Евгений P3206

src/mem.c

 #define _DEFAULT_SOURCE
 
+#define MAX(x, y) ((x) > (y) ? (x) : (y))
+
 #include <assert.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include "mem.h"
 #include "util.h"
 
-void debug_block(struct block_header* b, const char* fmt, ... );
-void debug(const char* fmt, ... );
+void debug_block(struct block_header *b, const char *fmt, ...);
+void debug(const char *fmt, ...);
 
-extern inline block_size size_from_capacity( block_capacity cap );
-extern inline block_capacity capacity_from_size( block_size sz );
+extern inline block_size size_from_capacity(block_capacity cap);
+extern inline block_capacity capacity_from_size(block_size sz);
 
-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 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 void block_init( void* restrict addr, block_size block_sz, void* restrict next ) {
-  *((struct block_header*)addr) = (struct block_header) {
-    .next = next,
-    .capacity = capacity_from_size(block_sz),
-    .is_free = true
-  };
+static void block_init(void *restrict addr, block_size block_sz, void *restrict next)
+{
+  *((struct block_header *)addr) = (struct block_header){
+      .next = next,
+      .capacity = capacity_from_size(block_sz),
+      .is_free = true};
 }
 
-static size_t region_actual_size( size_t query ) { return size_max( round_pages( query ), REGION_MIN_SIZE ); }
-
-extern inline bool region_is_invalid( const struct region* r );
+static size_t region_actual_size(size_t query) { return size_max(round_pages(query), REGION_MIN_SIZE); }
 
+extern inline bool region_is_invalid(const struct region *r);
 
-
-static void* map_pages(void const* addr, size_t length, int additional_flags) {
-  return mmap( (void*) addr, length, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS | additional_flags , -1, 0 );
+static void *map_pages(void const *addr, size_t length, int additional_flags)
+{
+  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 ) {
-  /*  ??? */
+static struct region alloc_region(void const *addr, size_t query)
+{
+  size_t size = region_actual_size(query + offsetof(struct block_header, contents));
+  void *new_addr = map_pages(addr, size, MAP_FIXED);
+  bool extends = true;
+
+  if (new_addr == MAP_FAILED) {
+    new_addr = map_pages(addr, size, 0);
+    if (new_addr == MAP_FAILED) {
+      return (struct region){0};
+    } else {
+      extends = false;
+    }
+  }
+
+  block_init(new_addr, (block_size){size}, NULL);
+
+  return (struct region){new_addr, size, extends};
 }
 
-static void* block_after( struct block_header const* block )         ;
+static void *block_after(struct block_header const *block);
 
-void* heap_init( size_t initial ) {
-  const struct region region = alloc_region( HEAP_START, initial );
-  if ( region_is_invalid(&region) ) return NULL;
+void *heap_init(size_t initial)
+{
+  const struct region region = alloc_region(HEAP_START, initial);
+  if (region_is_invalid(&region))
+    return NULL;
 
   return region.addr;
 }
 
 /*  освободить всю память, выделенную под кучу */
-void heap_term( ) {
-  /*  ??? */
+void heap_term()
+{
+  struct block_header *start_region = HEAP_START;
+
+  while (start_region) {
+    size_t region_size = 0;
+    struct block_header *start_reg = start_region;
+
+    while (start_region->next == block_after(start_region)) {
+        region_size += size_from_capacity(start_region->capacity).bytes;
+        start_region = start_region->next;
+    }
+
+    region_size += size_from_capacity(start_region->capacity).bytes;
+    start_region = start_region->next;
+
+    if (munmap(start_reg, region_size) == -1) {
+        perror("munmap error");
+    }
+  }
 }
 
 #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;
+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;
 }
 
-static bool split_if_too_big( struct block_header* block, size_t query ) {
-  /*  ??? */
-}
+static bool split_if_too_big(struct block_header *block, size_t query)
+{
+  if (!block_splittable(block, query)) {
+    return false;
+  }
 
+  block_capacity new_capacity = {.bytes = size_max(BLOCK_MIN_CAPACITY, query)};
+  void *address = block->contents + new_capacity.bytes;
+  size_t new_size = size_from_capacity(block->capacity).bytes - size_from_capacity(new_capacity).bytes;
+
+  block_init(address, (block_size){new_size}, block->next);
+  block_init(block, size_from_capacity(new_capacity), address);
+
+  return true;
+}
 
 /*  --- Слияние соседних свободных блоков --- */
 
-static void* block_after( struct block_header const* block )              {
-  return  (void*) (block->contents + block->capacity.bytes);
+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 ) {
-  return (void*)snd == block_after(fst);
+static bool blocks_continuous(
+  struct block_header const *fst,
+  struct block_header const *snd)
+{
+  return (void *)snd == block_after(fst);
 }
 
-static bool mergeable(struct block_header const* restrict fst, struct block_header const* restrict snd) {
-  return fst->is_free && snd->is_free && blocks_continuous( fst, snd ) ;
+static bool mergeable(struct block_header const *restrict fst, struct block_header const *restrict snd)
+{
+  return fst->is_free && snd->is_free && blocks_continuous(fst, snd);
 }
 
-static bool try_merge_with_next( struct block_header* block ) {
-  /*  ??? */
-}
+static bool try_merge_with_next(struct block_header *block)
+{
+  struct block_header *next_block = block->next;
+  if (!next_block || !mergeable(block, next_block)) {
+    return false;
+  }
 
+  block_size new_size = {size_from_capacity(block->capacity).bytes +
+                        size_from_capacity(next_block->capacity).bytes};
+  block_init(block, new_size, next_block->next);
+
+  return true;
+}
 
 /*  --- ... ecли размера кучи хватает --- */
 
-struct block_search_result {
-  enum {BSR_FOUND_GOOD_BLOCK, BSR_REACHED_END_NOT_FOUND, BSR_CORRUPTED} type;
-  struct block_header* block;
+struct block_search_result
+{
+  enum
+  {
+    BSR_FOUND_GOOD_BLOCK,
+    BSR_REACHED_END_NOT_FOUND,
+    BSR_CORRUPTED
+  } type;
+  struct block_header *block;
 };
 
+static struct block_search_result find_good_or_last(struct block_header *restrict block, size_t sz)
+{
+  struct block_search_result result = {.type = BSR_CORRUPTED};
+
+  while (block && block->next) {
+    while (try_merge_with_next(block));
+      
+    if (block->capacity.bytes >= sz && block->is_free) {
+      return (struct block_search_result){.type = BSR_FOUND_GOOD_BLOCK, .block = block};
+    }
+
+    block = block->next;
+  }
 
-static struct block_search_result find_good_or_last  ( struct block_header* restrict block, size_t sz )    {
-  /*??? */
+  if (block && block->capacity.bytes >= sz && block->is_free) {
+    return (struct block_search_result){.type = BSR_FOUND_GOOD_BLOCK, .block = block};
+  }
+
+  return (struct block_search_result){.type = BSR_REACHED_END_NOT_FOUND, .block = block};
 }
 
 /*  Попробовать выделить память в куче начиная с блока `block` не пытаясь расширить кучу
  Можно переиспользовать как только кучу расширили. */
-static struct block_search_result try_memalloc_existing ( size_t query, struct block_header* 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)
+{
+  if(!last) return NULL;
 
+  struct region new_region = alloc_region(block_after(last), query);
+  if(region_is_invalid(&new_region)) return NULL;
 
-static struct block_header* grow_heap( struct block_header* restrict last, size_t query ) {
-  /*  ??? */
+  last->next = new_region.addr;
+  if (try_merge_with_next(last)){
+    return last;
+  } else {
+    return last->next;
+  }
 }
 
-/*  Реализует основную логику malloc и возвращает заголовок выделенного блока */
-static struct block_header* memalloc( size_t query, struct block_header* heap_start) {
-
-  /*  ??? */
+#define BLOCK_MIN_SIZE 24
 
+/*  Реализует основную логику malloc и возвращает заголовок выделенного блока */
+static struct block_header *memalloc(size_t query, struct block_header *heap_start)
+{
+  query = MAX(query, BLOCK_MIN_SIZE);
+
+  struct block_search_result result = try_memalloc_existing(query, heap_start);
+  struct block_header *new_block = NULL;
+
+  switch (result.type) {
+    case BSR_FOUND_GOOD_BLOCK:
+      return result.block;
+    case BSR_REACHED_END_NOT_FOUND:
+      new_block = grow_heap(result.block, query);
+      result = try_memalloc_existing(query, new_block);
+      return result.block;
+    case BSR_CORRUPTED:
+      return NULL;
+  }
+
+  return NULL;
 }
 
-void* _malloc( size_t query ) {
-  struct block_header* const addr = memalloc( query, (struct block_header*) HEAP_START );
-  if (addr) return addr->contents;
-  else return NULL;
+void *_malloc(size_t query)
+{
+  struct block_header *const addr = memalloc(query, (struct block_header *)HEAP_START);
+  if (addr){
+    return addr->contents;
+  } else {
+    return NULL;
+  }
 }
 
-static struct block_header* block_get_header(void* contents) {
-  return (struct block_header*) (((uint8_t*)contents)-offsetof(struct block_header, contents));
+static struct block_header *block_get_header(void *contents)
+{
+  return (struct block_header *)(((uint8_t *)contents) - offsetof(struct block_header, contents));
 }
 
-void _free( void* mem ) {
-  if (!mem) return ;
-  struct block_header* header = block_get_header( mem );
+void _free(void *mem)
+{
+  if (!mem)
+    return;
+  struct block_header *header = block_get_header(mem);
   header->is_free = true;
-  /*  ??? */
+  while (try_merge_with_next(header));
 }

CMakeLists.txt

     set(CMAKE_C_FLAGS_ASAN  "${CMAKE_C_FLAGS_DEBUG} -fsanitize=address -fno-optimize-sibling-calls -fno-omit-frame-pointer")
     set(CMAKE_C_FLAGS_LSAN  "${CMAKE_C_FLAGS_DEBUG} -fsanitize=leak")
     set(CMAKE_C_FLAGS_MSAN  "${CMAKE_C_FLAGS_DEBUG} -fsanitize=memory -fno-optimize-sibling-calls -fno-omit-frame-pointer")
-    set(CMAKE_C_FLAGS_UBSAN "${CMAKE_C_FLAGS_DEBUG} -fsanitize=undefined")
+    set(CMAKE_C_FLAGS_UBSAN "${CMAKE_C_FLAGS_DEBUG} -fsanitize=undefined -fno-sanitize=alignment -fno-sanitize=shift")
 elseif(MSVC)
     set(CMAKE_C_FLAGS       "/std:c17")
     set(CMAKE_C_FLAGS_ASAN  "${CMAKE_C_FLAGS_DEBUG} /fsanitize=address")

[Евгений Башаримов]

Все замечания исправлены, @dsadyrin

[Paul Malkov]

От меня ОК

[Даниил Садырин]

@vedzevgn Принято после дедлайна @plmlkff Ревью принято