Master

src/mem.c

 #include <stdlib.h>
 #include <unistd.h>
 
-#include "mem_internals.h"
 #include "mem.h"
+#include "mem_internals.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 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 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 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 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 *regix);
 
-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) {
+  struct region r = {.addr = NULL, .extends = false, .size = 0};
+  block_capacity capacity = {.bytes = query};
+  block_size size = size_from_capacity(capacity);
+
+  r.size = region_actual_size(size.bytes);
+  void *potential_addr = map_pages(addr, r.size, MAP_FIXED_NOREPLACE);
+
+  if (potential_addr != MAP_FAILED) {
+    r.addr = potential_addr;
+    r.extends = true;
+  } else {
+    potential_addr = map_pages(addr, r.size, 0);
+    if (potential_addr != MAP_FAILED) {
+      r.addr = potential_addr;
+    }
+  }
+
+  if (r.addr) {
+    block_init(r.addr, (block_size){.bytes = r.size}, NULL);
+  }
+
+  return r;
 }
 
-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;
 }
 
+static bool blocks_continuous(struct block_header const *fst,
+                              struct block_header const *snd);
+
 /*  освободить всю память, выделенную под кучу */
-void heap_term( ) {
-  /*  ??? */
+void heap_term() {
+  struct block_header *current_block = (struct block_header *)HEAP_START;
+  struct block_header *to_add = current_block;
+  size_t total_size = 0;
+
+  while (current_block) {
+    struct block_header *next = current_block->next;
+    total_size += size_from_capacity(current_block->capacity).bytes;
+    if (!next || !blocks_continuous(to_add, next)) {
+      to_add->capacity.bytes += total_size;
+      munmap((void *)to_add, total_size);
+      total_size = 0;
+      to_add = next;
+    }
+    current_block = next;
+  }
 }
 
 #define BLOCK_MIN_CAPACITY 24
 
+static size_t block_actual_capacity(size_t query) {
+  return size_max(query, BLOCK_MIN_CAPACITY);
+}
+
 /*  --- Разделение блоков (если найденный свободный блок слишком большой )--- */
 
-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)
+    return false;
 
+  query = size_max(query, BLOCK_MIN_CAPACITY);
+  if (!block_splittable(block, query))
+    return false;
+
+  size_t remaining_capacity = block->capacity.bytes - query;
+  struct block_header *new_block =
+      (struct block_header *)(block->contents + query);
+  block_init(new_block, (block_size){remaining_capacity}, block->next);
+  block->next = new_block;
+  block->capacity.bytes = query;
+
+  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 ? block->next : NULL;
+  if (next_block && mergeable(block, next_block)) {
+    block->capacity.bytes += size_from_capacity(next_block->capacity).bytes;
+    if (next_block->next) {
+      block->next = next_block->next;
+    } else {
+      block->next = NULL;
+    }
 
+    return true;
+  }
+
+  return false;
+}
 
 /*  --- ... ecли размера кучи хватает --- */
 
 struct block_search_result {
-  enum {BSR_FOUND_GOOD_BLOCK, BSR_REACHED_END_NOT_FOUND, BSR_CORRUPTED} type;
-  struct block_header* block;
+  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 )    {
-  /*??? */
+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){.type = BSR_REACHED_END_NOT_FOUND,
+                                      .block = block};
 }
 
-/*  Попробовать выделить память в куче начиная с блока `block` не пытаясь расширить кучу
- Можно переиспользовать как только кучу расширили. */
-static struct block_search_result try_memalloc_existing ( size_t query, struct block_header* block ) {
-  
-}
+/*  Попробовать выделить память в куче начиная с блока `block` не пытаясь
+ расширить кучу Можно переиспользовать как только кучу расширили. */
+static struct block_search_result
+try_memalloc_existing(size_t query, struct block_header *block) {
+  struct block_search_result search_result = find_good_or_last(block, query);
 
+  if (search_result.type == BSR_FOUND_GOOD_BLOCK) {
+    split_if_too_big(search_result.block, query);
+    search_result.block->is_free = false;
+  }
 
+  return search_result;
+}
 
-static struct block_header* grow_heap( struct block_header* restrict last, size_t query ) {
-  /*  ??? */
+static struct block_header *grow_heap(struct block_header *restrict last,
+                                      size_t query) {
+
+  if (!last) {
+    return NULL;
+  }
+
+  struct block_header *new_block = NULL;
+  struct region new_region = alloc_region(block_after(last), query);
+
+  if (!region_is_invalid(&new_region)) {
+    new_block = (struct block_header *)new_region.addr;
+    new_block->size = new_region.size;
+    new_block->next = NULL;
+    new_block->prev = NULL;
+    new_block->is_free = true;
+
+    last->next = new_block;
+
+    if (!try_merge_with_next(last)) {
+      return last->next;
+    } else {
+      return last;
+    }
+  } else {
+    return NULL;
+  }
 }
 
 /*  Реализует основную логику malloc и возвращает заголовок выделенного блока */
-static struct block_header* memalloc( size_t query, struct block_header* heap_start) {
-
-  /*  ??? */
-
+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 search_result;
+
+  search_result = try_memalloc_existing(query, heap_start);
+  switch (search_result.type) {
+  case BSR_CORRUPTED:
+    return NULL;
+  case BSR_FOUND_GOOD_BLOCK:
+    return search_result.block;
+  default: {
+    struct block_header *new_block = grow_heap(search_result.block, query);
+    if (!new_block)
+      return NULL;
+
+    search_result = try_memalloc_existing(query, heap_start);
+    if (search_result.type == BSR_CORRUPTED)
+      return NULL;
+    return search_result.block;
+  }
+  }
 }
 
-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;
+  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)) {
+  };
 }

src/mem_internals.h

 
 #define REGION_MIN_SIZE (2 * 4096)
 
-struct region { void* addr; size_t size; bool extends; };
+struct region {
+  void *addr;
+  size_t size;
+  bool extends;
+};
 static const struct region REGION_INVALID = {0};
 
-inline bool region_is_invalid( const struct region* r ) { return r->addr == NULL; }
+inline bool region_is_invalid(const struct region *r) {
+  return r->addr == NULL;
+}
 
-typedef struct { size_t bytes; } block_capacity;
-typedef struct { size_t bytes; } block_size;
+typedef struct {
+  size_t bytes;
+} block_capacity;
+typedef struct {
+  size_t bytes;
+} block_size;
 
 struct block_header {
-  struct block_header*    next;
+  struct block_header *next;
+  struct block_header *prev;
   block_capacity capacity;
-  bool           is_free;
-  uint8_t        contents[];
+  size_t size;
+  bool is_free;
+  uint8_t contents[];
 };
 
-inline block_size size_from_capacity( block_capacity cap ) { return (block_size) {cap.bytes + offsetof( struct block_header, contents ) }; }
-inline block_capacity capacity_from_size( block_size sz ) { return (block_capacity) {sz.bytes - offsetof( struct block_header, contents ) }; }
+inline block_size size_from_capacity(block_capacity cap) {
+  return (block_size){cap.bytes + offsetof(struct block_header, contents)};
+}
+inline block_capacity capacity_from_size(block_size sz) {
+  return (block_capacity){sz.bytes - offsetof(struct block_header, contents)};
+}
 
 #endif

[Andrey Zhdanov]

Ок