#include "utils/commons.h"
#include "mm_allocator.h"
#define MM_ALLOCATOR_SEGMENT_INITIAL_REQUESTS 10000
#define MM_ALLOCATOR_INITIAL_SEGMENTS 10
#define MM_ALLOCATOR_INITIAL_MALLOC_REQUESTS 10
#define MM_ALLOCATOR_INITIAL_STATES 10
#define MM_ALLOCATOR_FREED_FLAG 0x80000000ul
#define MM_ALLOCATOR_REQUEST_IS_FREE(request) ((request)->size & MM_ALLOCATOR_FREED_FLAG)
#define MM_ALLOCATOR_REQUEST_SET_FREE(request) ((request)->size |= MM_ALLOCATOR_FREED_FLAG)
#define MM_ALLOCATOR_REQUEST_SIZE(request) ((request)->size & ~(MM_ALLOCATOR_FREED_FLAG))
typedef struct {
uint32_t segment_idx;
uint32_t request_idx;
} mm_allocator_reference_t;
typedef struct {
uint32_t offset;
uint32_t size;
#ifdef MM_ALLOCATOR_LOG
uint64_t timestamp;
char* func_name;
uint64_t line_no;
#endif
} mm_allocator_request_t;
typedef struct {
void* mem;
uint64_t size;
#ifdef MM_ALLOCATOR_LOG
uint64_t timestamp;
char* func_name;
uint64_t line_no;
#endif
mm_allocator_reference_t* reference;
} mm_malloc_request_t;
typedef struct {
uint64_t idx; uint64_t size; void* memory; uint64_t used; vector_t* requests; } mm_allocator_segment_t;
mm_allocator_segment_t* mm_allocator_segment_new(
mm_allocator_t* const mm_allocator) {
mm_allocator_segment_t* const segment = (mm_allocator_segment_t*) malloc(sizeof(mm_allocator_segment_t));
const uint64_t segment_idx = vector_get_used(mm_allocator->segments);
segment->idx = segment_idx;
segment->size = mm_allocator->segment_size;
segment->memory = malloc(mm_allocator->segment_size);
segment->used = 0;
segment->requests = vector_new(MM_ALLOCATOR_SEGMENT_INITIAL_REQUESTS,mm_allocator_request_t);
vector_insert(mm_allocator->segments,segment,mm_allocator_segment_t*);
return segment;
}
void mm_allocator_segment_clear(
mm_allocator_segment_t* const segment) {
segment->used = 0;
vector_clear(segment->requests);
}
void mm_allocator_segment_delete(
mm_allocator_segment_t* const segment) {
vector_delete(segment->requests);
free(segment->memory);
free(segment);
}
mm_allocator_request_t* mm_allocator_segment_get_request(
mm_allocator_segment_t* const segment,
const uint64_t request_idx) {
return vector_get_elm(segment->requests,request_idx,mm_allocator_request_t);
}
uint64_t mm_allocator_segment_get_num_requests(
mm_allocator_segment_t* const segment) {
return vector_get_used(segment->requests);
}
mm_allocator_t* mm_allocator_new(
const uint64_t segment_size) {
mm_allocator_t* const mm_allocator = (mm_allocator_t*) malloc(sizeof(mm_allocator_t));
mm_allocator->request_ticker = 0;
mm_allocator->segment_size = segment_size;
mm_allocator->segments = vector_new(MM_ALLOCATOR_INITIAL_SEGMENTS,mm_allocator_segment_t*);
mm_allocator->segments_free = vector_new(MM_ALLOCATOR_INITIAL_SEGMENTS,mm_allocator_segment_t*);
#ifndef MM_ALLOCATOR_FORCE_MALLOC
#ifndef MM_ALLOCATOR_DISABLE
mm_allocator_segment_new(mm_allocator);
#endif
#endif
mm_allocator->current_segment_idx = 0;
mm_allocator->malloc_requests = vector_new(MM_ALLOCATOR_INITIAL_MALLOC_REQUESTS,mm_malloc_request_t);
mm_allocator->malloc_requests_freed = 0;
return mm_allocator;
}
void mm_allocator_clear(
mm_allocator_t* const mm_allocator) {
vector_clear(mm_allocator->segments_free);
VECTOR_ITERATE(mm_allocator->segments,segment_ptr,p,mm_allocator_segment_t*) {
mm_allocator_segment_clear(*segment_ptr); vector_insert(mm_allocator->segments_free,*segment_ptr,mm_allocator_segment_t*); }
mm_allocator->current_segment_idx = 0;
VECTOR_ITERATE(mm_allocator->malloc_requests,malloc_request,m,mm_malloc_request_t) {
if (malloc_request->size > 0) free(malloc_request->mem); }
vector_clear(mm_allocator->malloc_requests);
mm_allocator->malloc_requests_freed = 0;
}
void mm_allocator_delete(
mm_allocator_t* const mm_allocator) {
VECTOR_ITERATE(mm_allocator->segments,segment_ptr,p,mm_allocator_segment_t*) {
mm_allocator_segment_delete(*segment_ptr);
}
vector_delete(mm_allocator->segments);
vector_delete(mm_allocator->segments_free);
VECTOR_ITERATE(mm_allocator->malloc_requests,malloc_request,m,mm_malloc_request_t) {
if (malloc_request->size > 0) free(malloc_request->mem); }
vector_delete(mm_allocator->malloc_requests);
free(mm_allocator);
}
mm_allocator_segment_t* mm_allocator_get_segment(
mm_allocator_t* const mm_allocator,
const uint64_t segment_idx) {
return *(vector_get_elm(mm_allocator->segments,segment_idx,mm_allocator_segment_t*));
}
mm_allocator_segment_t* mm_allocator_get_segment_free(
mm_allocator_t* const mm_allocator,
const uint64_t segment_idx) {
return *(vector_get_elm(mm_allocator->segments_free,segment_idx,mm_allocator_segment_t*));
}
uint64_t mm_allocator_get_num_segments(
mm_allocator_t* const mm_allocator) {
return vector_get_used(mm_allocator->segments);
}
uint64_t mm_allocator_get_num_segments_free(
mm_allocator_t* const mm_allocator) {
return vector_get_used(mm_allocator->segments_free);
}
mm_allocator_segment_t* mm_allocator_fetch_segment(
mm_allocator_t* const mm_allocator,
const uint64_t num_bytes) {
mm_allocator_segment_t* const curr_segment =
mm_allocator_get_segment(mm_allocator,mm_allocator->current_segment_idx);
if (num_bytes > curr_segment->size/2) { return NULL; }
if (curr_segment->used + num_bytes <= curr_segment->size) {
return curr_segment;
}
if (num_bytes > curr_segment->size) {
return NULL; }
const uint64_t free_segments = mm_allocator_get_num_segments_free(mm_allocator);
if (free_segments > 0) {
mm_allocator_segment_t* const segment =
mm_allocator_get_segment_free(mm_allocator,free_segments-1);
vector_dec_used(mm_allocator->segments_free);
mm_allocator->current_segment_idx = segment->idx;
return segment;
}
mm_allocator_segment_t* const segment = mm_allocator_segment_new(mm_allocator);
mm_allocator->current_segment_idx = segment->idx;
return segment;
}
void* mm_allocator_allocate(
mm_allocator_t* const mm_allocator,
const uint64_t num_bytes,
const bool zero_mem,
const uint64_t align_bytes
#ifdef MM_ALLOCATOR_LOG
,const char* func_name,
uint64_t line_no
#endif
) {
#ifdef MM_ALLOCATOR_DISABLE
void* memory = calloc(1,num_bytes);
if (zero_mem) memset(memory,0,num_bytes); return memory; #else
if (num_bytes == 0) {
fprintf(stderr,"MMAllocator error. Zero bytes requested\n");
exit(1);
}
const uint64_t num_bytes_allocated = num_bytes + sizeof(mm_allocator_reference_t) + align_bytes;
#ifdef MM_ALLOCATOR_FORCE_MALLOC
mm_allocator_segment_t* const segment = NULL; #else
mm_allocator_segment_t* const segment = mm_allocator_fetch_segment(mm_allocator,num_bytes_allocated);
#endif
if (segment != NULL) {
void* const memory_base = segment->memory + segment->used;
if (zero_mem) memset(memory_base,0,num_bytes_allocated); void* memory_aligned = memory_base + sizeof(mm_allocator_reference_t) + align_bytes;
if (align_bytes > 0) {
memory_aligned = memory_aligned - ((uintptr_t)memory_aligned % align_bytes);
}
mm_allocator_reference_t* const mm_reference = (mm_allocator_reference_t*)(memory_aligned - sizeof(mm_allocator_reference_t));
mm_reference->segment_idx = segment->idx;
mm_reference->request_idx = mm_allocator_segment_get_num_requests(segment);
mm_allocator_request_t* request;
vector_alloc_new(segment->requests,mm_allocator_request_t,request);
request->offset = segment->used;
request->size = num_bytes_allocated;
#ifdef MM_ALLOCATOR_LOG
request->timestamp = (mm_allocator->request_ticker)++;
request->func_name = (char*)func_name;
request->line_no = line_no;
#endif
segment->used += num_bytes_allocated;
return memory_aligned;
} else {
void* const memory_base = malloc(num_bytes_allocated);
if (zero_mem) memset(memory_base,0,num_bytes_allocated); void* memory_aligned = memory_base + sizeof(mm_allocator_reference_t) + align_bytes;
if (align_bytes > 0) {
memory_aligned = memory_aligned - ((uintptr_t)memory_aligned % align_bytes);
}
mm_allocator_reference_t* const mm_reference = (mm_allocator_reference_t*)(memory_aligned - sizeof(mm_allocator_reference_t));
mm_reference->segment_idx = UINT32_MAX;
mm_reference->request_idx = vector_get_used(mm_allocator->malloc_requests);
mm_malloc_request_t* request;
vector_alloc_new(mm_allocator->malloc_requests,mm_malloc_request_t,request);
request->mem = memory_base;
request->size = num_bytes_allocated;
#ifdef MM_ALLOCATOR_LOG
request->timestamp = (mm_allocator->request_ticker)++;
request->func_name = (char*)func_name;
request->line_no = line_no;
#endif
request->reference = mm_reference;
return memory_aligned;
}
#endif
}
void mm_allocator_free_malloc_request(
mm_allocator_t* const mm_allocator,
mm_allocator_reference_t* const mm_reference) {
mm_malloc_request_t* const request =
vector_get_elm(mm_allocator->malloc_requests,mm_reference->request_idx,mm_malloc_request_t);
if (request->size == 0) {
fprintf(stderr,"MMAllocator error: double free\n");
exit(1);
}
request->size = 0;
free(request->mem);
++(mm_allocator->malloc_requests_freed);
if (mm_allocator->malloc_requests_freed >= 1000) {
const uint64_t num_requests = vector_get_used(mm_allocator->malloc_requests);
mm_malloc_request_t* const requests = vector_get_mem(mm_allocator->malloc_requests,mm_malloc_request_t);
uint64_t i, busy_requests = 0;
for (i=0;i<num_requests;++i) {
if (requests[i].size > 0) {
requests[busy_requests] = requests[i];
requests[busy_requests].reference->request_idx = busy_requests;
++busy_requests;
}
}
vector_set_used(mm_allocator->malloc_requests,busy_requests);
mm_allocator->malloc_requests_freed = 0;
}
}
void mm_allocator_free_allocator_request(
mm_allocator_t* const mm_allocator,
mm_allocator_reference_t* const mm_reference) {
mm_allocator_segment_t* const segment =
mm_allocator_get_segment(mm_allocator,mm_reference->segment_idx);
mm_allocator_request_t* const request =
mm_allocator_segment_get_request(segment,mm_reference->request_idx);
if (MM_ALLOCATOR_REQUEST_IS_FREE(request)) {
fprintf(stderr,"MMAllocator error: double free\n");
exit(1);
}
MM_ALLOCATOR_REQUEST_SET_FREE(request);
uint64_t num_requests = mm_allocator_segment_get_num_requests(segment);
if (mm_reference->request_idx == num_requests-1) { --num_requests;
mm_allocator_request_t* request =
vector_get_mem(segment->requests,mm_allocator_request_t) + (num_requests-1);
while (num_requests>0 && MM_ALLOCATOR_REQUEST_IS_FREE(request)) {
--num_requests; --request;
}
if (num_requests > 0) {
segment->used = request->offset + request->size;
vector_set_used(segment->requests,num_requests);
} else {
mm_allocator_segment_clear(segment); if (segment->idx != mm_allocator->current_segment_idx) {
vector_insert(mm_allocator->segments_free,segment,mm_allocator_segment_t*);
}
}
}
}
void mm_allocator_free(
mm_allocator_t* const mm_allocator,
void* const memory) {
#ifdef MM_ALLOCATOR_DISABLE
free(memory);
#else
void* const effective_memory = memory - sizeof(mm_allocator_reference_t);
mm_allocator_reference_t* const mm_reference = (mm_allocator_reference_t*) effective_memory;
if (mm_reference->segment_idx == UINT32_MAX) {
mm_allocator_free_malloc_request(mm_allocator,mm_reference);
} else {
mm_allocator_free_allocator_request(mm_allocator,mm_reference);
}
#endif
}
void mm_allocator_get_occupation(
mm_allocator_t* const mm_allocator,
uint64_t* const bytes_used_malloc,
uint64_t* const bytes_used_allocator,
uint64_t* const bytes_free_available,
uint64_t* const bytes_free_fragmented) {
*bytes_used_malloc = 0;
*bytes_used_allocator = 0;
*bytes_free_available = 0;
*bytes_free_fragmented = 0;
const uint64_t num_segments = mm_allocator_get_num_segments(mm_allocator);
int64_t segment_idx, request_idx;
for (segment_idx=0;segment_idx<num_segments;++segment_idx) {
mm_allocator_segment_t* const segment = mm_allocator_get_segment(mm_allocator,segment_idx);
const uint64_t num_requests = mm_allocator_segment_get_num_requests(segment);
bool memory_freed = true;
for (request_idx=num_requests-1;request_idx>=0;--request_idx) {
mm_allocator_request_t* const request = mm_allocator_segment_get_request(segment,request_idx);
const uint64_t size = MM_ALLOCATOR_REQUEST_SIZE(request);
if (MM_ALLOCATOR_REQUEST_IS_FREE(request)) {
if (memory_freed) {
*bytes_free_available += size;
} else {
*bytes_free_fragmented += size;
}
} else {
memory_freed = false;
*bytes_used_allocator += size;
}
}
if (num_requests > 0) {
mm_allocator_request_t* const request = mm_allocator_segment_get_request(segment,num_requests-1);
const uint64_t bytes_free_at_end = segment->size - (request->offset+request->size);
if (segment_idx == mm_allocator->current_segment_idx) {
*bytes_free_available += bytes_free_at_end;
} else {
*bytes_free_fragmented += bytes_free_at_end;
}
}
}
const uint64_t num_requests = vector_get_used(mm_allocator->malloc_requests);
mm_malloc_request_t* const requests = vector_get_mem(mm_allocator->malloc_requests,mm_malloc_request_t);
uint64_t i;
for (i=0;i<num_requests;++i) {
*bytes_used_malloc += requests[i].size;
}
}
void mm_allocator_print_allocator_request(
FILE* const stream,
mm_allocator_request_t* const request,
const uint64_t segment_idx,
const uint64_t request_idx) {
fprintf(stream," [#%03" PRIu64 "/%05" PRIu64 "\t%s\t@%08u\t(%" PRIu64 " Bytes)"
#ifdef MM_ALLOCATOR_LOG
"\t%s:%" PRIu64 "\t{ts=%" PRIu64 "}"
#endif
"\n",
segment_idx,
request_idx,
MM_ALLOCATOR_REQUEST_IS_FREE(request) ? "Free] " : "Allocated]",
request->offset,
(uint64_t)MM_ALLOCATOR_REQUEST_SIZE(request)
#ifdef MM_ALLOCATOR_LOG
,request->func_name,
request->line_no,
request->timestamp
#endif
);
}
void mm_allocator_print_malloc_request(
FILE* const stream,
mm_malloc_request_t* const request) {
fprintf(stream," [@%p" PRIu64 "\t(%" PRIu64 " Bytes)"
#ifdef MM_ALLOCATOR_LOG
"\t%s:%" PRIu64 "\t{ts=%" PRIu64 "}"
#endif
"\n",
request->mem,
request->size
#ifdef MM_ALLOCATOR_LOG
,request->func_name,
request->line_no,
request->timestamp
#endif
);
}
void mm_allocator_print_allocator_requests(
FILE* const stream,
mm_allocator_t* const mm_allocator,
const bool compact_free) {
uint64_t segment_idx, request_idx;
uint64_t free_block = 0;
bool has_requests = false;
fprintf(stream," => MMAllocator.requests\n");
const uint64_t num_segments = mm_allocator_get_num_segments(mm_allocator);
for (segment_idx=0;segment_idx<num_segments;++segment_idx) {
mm_allocator_segment_t* const segment = mm_allocator_get_segment(mm_allocator,segment_idx);
const uint64_t num_requests = mm_allocator_segment_get_num_requests(segment);
for (request_idx=0;request_idx<num_requests;++request_idx) {
mm_allocator_request_t* const request = mm_allocator_segment_get_request(segment,request_idx);
if (compact_free) {
if (MM_ALLOCATOR_REQUEST_IS_FREE(request)) {
free_block += MM_ALLOCATOR_REQUEST_SIZE(request);
} else {
if (free_block > 0) {
fprintf(stream," [n/a\tFree] \t(%" PRIu64 " Bytes)\n",free_block);
free_block = 0;
}
mm_allocator_print_allocator_request(stream,request,segment_idx,request_idx);
has_requests = true;
}
} else {
mm_allocator_print_allocator_request(stream,request,segment_idx,request_idx);
has_requests = true;
}
}
}
if (!has_requests) {
fprintf(stream," -- No requests --\n");
}
fprintf(stream," => MMMalloc.requests\n");
const uint64_t num_requests = vector_get_used(mm_allocator->malloc_requests);
mm_malloc_request_t* const requests = vector_get_mem(mm_allocator->malloc_requests,mm_malloc_request_t);
uint64_t i;
for (i=0;i<num_requests;++i) {
if (requests[i].size > 0) {
mm_allocator_print_malloc_request(stream,requests+i);
}
}
if (num_requests == 0) {
fprintf(stream," -- No requests --\n");
}
}
void mm_allocator_print(
FILE* const stream,
mm_allocator_t* const mm_allocator,
const bool display_requests) {
fprintf(stream,"MMAllocator.report\n");
const uint64_t num_segments = mm_allocator_get_num_segments(mm_allocator);
const uint64_t segment_size = mm_allocator->segment_size;
fprintf(stream," => Segments.allocated %" PRIu64 "\n",num_segments);
fprintf(stream," => Segments.size %" PRIu64 " MB\n",segment_size/(1024*1024));
fprintf(stream," => Memory.available %" PRIu64 " MB\n",num_segments*(segment_size/(1024*1024)));
uint64_t bytes_used_malloc, bytes_used_allocator;
uint64_t bytes_free_available, bytes_free_fragmented;
mm_allocator_get_occupation(mm_allocator,&bytes_used_malloc,&bytes_used_allocator,&bytes_free_available,&bytes_free_fragmented);
const float bytes_total = num_segments * segment_size;
const uint64_t bytes_free = bytes_free_available + bytes_free_fragmented;
fprintf(stream," => Memory.used %" PRIu64 " (%2.1f %%)\n",
bytes_used_allocator,100.0f*(float)bytes_used_allocator/bytes_total);
fprintf(stream," => Memory.free %" PRIu64 " (%2.1f %%)\n",
bytes_free,100.0f*(float)bytes_free/bytes_total);
fprintf(stream," => Memory.free.available %" PRIu64 " (%2.1f %%)\n",
bytes_free_available,100.0f*(float)bytes_free_available/bytes_total);
fprintf(stream," => Memory.free.fragmented %" PRIu64 " (%2.1f %%)\n",
bytes_free_fragmented,100.0f*(float)bytes_free_fragmented/bytes_total);
fprintf(stream," => Memory.malloc %" PRIu64 "\n",bytes_used_malloc);
if (display_requests) {
mm_allocator_print_allocator_requests(stream,mm_allocator,false);
}
}