Skip to content

GitLab

Closed
Created by Максим Лобов@HellCat
Report abuse

Лобов Максим Павлович P3212

Compare
and
8 files
+ 193
- 72
.i‎dea‎
cmak‎e.xml‎ +6 -6
s‎rc‎
CMakeLi‎sts.txt‎ +1 -1
mai‎n.c‎ +6 -0
me‎m.c‎ +174 -64
me‎m.h‎ +1 -0
mem_int‎ernals.h‎ +2 -1
teste‎r/src‎
test_u‎tils.h‎ +2 -0
CMakeLi‎sts.txt‎ +1 -0
.idea/cmake.xml
+ 6
- 6
Show all unchanged lines Show 20 lines
<project version="4">
<component name="CMakeSharedSettings">
<configurations>
<configuration PROFILE_NAME="Debug" ENABLED="true" GENERATION_DIR="out/build/debug" CONFIG_NAME="Debug" GENERATION_OPTIONS="-G Ninja -DCMAKE_BUILD_TYPE=Debug" />
<configuration PROFILE_NAME="Release" ENABLED="true" GENERATION_DIR="out/build/release" CONFIG_NAME="Release" GENERATION_OPTIONS="-G Ninja -DCMAKE_BUILD_TYPE=Release" />
<configuration PROFILE_NAME="ASan" ENABLED="true" GENERATION_DIR="out/build/asan" CONFIG_NAME="ASan" GENERATION_OPTIONS="-G Ninja -DCMAKE_BUILD_TYPE=ASan" />
<configuration PROFILE_NAME="LSan" ENABLED="true" GENERATION_DIR="out/build/lsan" CONFIG_NAME="LSan" GENERATION_OPTIONS="-G Ninja -DCMAKE_BUILD_TYPE=LSan" />
<configuration PROFILE_NAME="MSan" ENABLED="true" GENERATION_DIR="out/build/msan" CONFIG_NAME="MSan" GENERATION_OPTIONS="-G Ninja -DCMAKE_BUILD_TYPE=MSan" />
<configuration PROFILE_NAME="UBSan" ENABLED="true" GENERATION_DIR="out/build/ubsan" CONFIG_NAME="UBSan" GENERATION_OPTIONS="-G Ninja -DCMAKE_BUILD_TYPE=UBSan" />
<configuration PROFILE_NAME="Debug-WSL" ENABLED="true" GENERATION_DIR="out/build/debug" CONFIG_NAME="Debug" TOOLCHAIN_NAME="WSL" GENERATION_OPTIONS="-DCMAKE_BUILD_TYPE=Debug" NO_GENERATOR="true" />
<configuration PROFILE_NAME="Release-WSL" ENABLED="true" GENERATION_DIR="out/build/release" CONFIG_NAME="Release" TOOLCHAIN_NAME="WSL" GENERATION_OPTIONS="-DCMAKE_BUILD_TYPE=Release" NO_GENERATOR="true" />
<configuration PROFILE_NAME="ASan-WSL" ENABLED="true" GENERATION_DIR="out/build/asan" CONFIG_NAME="ASan" TOOLCHAIN_NAME="WSL" GENERATION_OPTIONS="-DCMAKE_BUILD_TYPE=ASan" NO_GENERATOR="true" />
<configuration PROFILE_NAME="LSan-WSL" ENABLED="true" GENERATION_DIR="out/build/lsan" CONFIG_NAME="LSan" TOOLCHAIN_NAME="WSL" GENERATION_OPTIONS="-DCMAKE_BUILD_TYPE=LSan" NO_GENERATOR="true" />
<configuration PROFILE_NAME="MSan-WSL" ENABLED="true" GENERATION_DIR="out/build/msan" CONFIG_NAME="MSan" TOOLCHAIN_NAME="WSL" GENERATION_OPTIONS="-DCMAKE_BUILD_TYPE=MSan" NO_GENERATOR="true" />
<configuration PROFILE_NAME="UBSan-WSL" ENABLED="true" GENERATION_DIR="out/build/ubsan" CONFIG_NAME="UBSan" TOOLCHAIN_NAME="WSL" GENERATION_OPTIONS="-DCMAKE_BUILD_TYPE=UBSan" NO_GENERATOR="true" />
</configurations>
</component>
</project>
\ No newline at end of file
src/CMakeLists.txt
+ 1
- 1
Show all unchanged lines Show 20 lines
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)
Show 20 lines Show all unchanged lines
src/main.c
+ 6
- 0
#include <stdio.h>
int main (){
printf("wee");
}
src/mem.c
+ 174
- 64
#define _DEFAULT_SOURCE
#include <assert.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.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, ... );
extern inline block_size size_from_capacity( block_capacity cap );
extern inline block_capacity capacity_from_size( block_size sz );
#define BLOCK_MIN_CAPACITY (alignof(max_align_t) * 2)
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
};
}
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);
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 region_actual_size( size_t query ) { return size_max( round_pages( query ), REGION_MIN_SIZE ); }
static size_t round_pages(size_t mem) { return getpagesize() * pages_count(mem); }
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 *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 alloc_size = region_actual_size(query);
alloc_size += (query == REGION_MIN_SIZE) ? getpagesize() : 0;
bool extends = true;
void *mapped_address = map_pages(addr, alloc_size, MAP_FIXED_NOREPLACE);
if (mapped_address == MAP_FAILED) {
extends = false;
mapped_address = map_pages(addr, alloc_size, 0);
}
if (mapped_address == MAP_FAILED) {
return REGION_INVALID;
}
struct region new_region = {mapped_address, alloc_size, extends};
block_init(mapped_address, (block_size) {alloc_size}, NULL);
return new_region;
}
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;
static bool blocks_continuous(struct block_header const *fst,
struct block_header const *snd);
return region.addr;
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 *current = (struct block_header *) HEAP_START;
struct block_header *start = current, *next;
size_t allocated_mem = 0;
for (; current;) {
next = current->next;
allocated_mem += size_from_capacity(current->capacity).bytes;
if (!blocks_continuous(current, next)) {
munmap(start, region_actual_size(allocated_mem));
start = next;
allocated_mem = 0;
}
current = next;
}
munmap(start, region_actual_size(allocated_mem));
}
#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 is_block_splittable(const struct block_header *restrict block, const 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 == NULL || !is_block_splittable(block, query)) return false;
const size_t block_capacity = size_max(query, BLOCK_MIN_CAPACITY);
const size_t new_block_size = block->capacity.bytes - block_capacity;
block->capacity.bytes = block_capacity;
struct block_header *next_block = block_after(block);
next_block->is_free = true;
next_block->next = block->next;
next_block->capacity = capacity_from_size((block_size) {new_block_size});
block->next = next_block;
// block->capacity.bytes = block_capacity;
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) {
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;
}
/* --- ... 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) {
struct block_search_result res = {BSR_CORRUPTED, block};
for (; block;) {
if (try_merge_with_next(block)) continue;
if (block->is_free && block->capacity.bytes >= sz) {
res.type = BSR_FOUND_GOOD_BLOCK;
break;
}
if (!block->next) {
res.type = BSR_REACHED_END_NOT_FOUND;
break;
}
block = block->next;
}
res.block = block;
return res;
}
/* Попробовать выделить память в куче начиная с блока `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 block_header *created_block = alloc_region(last->contents + last->capacity.bytes, query).addr;
if (!created_block) return NULL;
last->next = created_block;
if (try_merge_with_next(last) == true) return last;
static struct block_header* grow_heap( struct block_header* restrict last, size_t query ) {
/* ??? */
return created_block;
}
/* Реализует основную логику 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) {
query = size_max(query, BLOCK_MIN_CAPACITY);
while (true) {
struct block_search_result result = try_memalloc_existing(query, heap_start);
if (result.type == BSR_FOUND_GOOD_BLOCK) return result.block;
if (!result.block) return NULL;
result.block->next = grow_heap(result.block, query);
/* ??? */
if (!result.block->next) return NULL;
heap_start = 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;
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 );
header->is_free = true;
/* ??? */
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.h
+ 1
- 0
Show all unchanged lines Show 20 lines
#define _MEM_H_
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
Show 20 lines Show all unchanged lines

Menu

Help