Code:
#include <inttypes.h>
#include <sys/types.h>
#include <errno.h>
#include <ctype.h>
#include <unistd.h>
#include <fcntl.h>
#include <dirent.h>
#include <string.h>
#include <sys/mman.h>
#include <malloc.h>
#include <stdlib.h>
#include <stdio.h>
int fail() {
printf("Error 0x%08X %s\n", errno, strerror(errno) );
return EXIT_FAILURE;
}
void foo_atexit() {
(void)fail();
}
typedef unsigned char uchar;
typedef struct foo_addr {
uintptr_t size;
void *page, *data;
struct foo_addr *next, *prev;
} foo_addr_t;
typedef struct foo_page {
uintptr_t size, left;
uchar *base, *data, *stop;
struct foo_addr * root, *last;
} foo_page_t;
size_t pages_size = 0, pages_want = 0;
size_t pages_used = 0, pages_upto = 0, pages_node = 0;
foo_page_t* pages;
int page_fd = -1;
int foo__has_addr(
foo_page_t **dst, foo_addr_t **pos, void *ptr ) {
size_t p = 0;
foo_page_t *page;
foo_addr_t *addr;
if ( !dst || !pos ) return EDESTADDRREQ;
*dst = NULL;
*pos = NULL;
if ( !ptr ) return EXIT_FAILURE;
for ( p = 0; p < pages_used; ++p ) {
page = &(pages[p]);
for ( addr = page->root; addr; addr = addr->next ) {
if ( addr->data == ptr ) {
*dst = page;
*pos = addr;
printf("%s() page = %p, addr = %p\n", __func__, page, addr );
return EXIT_SUCCESS;
}
if ( addr == page->last ) break;
}
}
return EINVAL;
}
int foo__try_addr(
foo_page_t *page, foo_addr_t *addr, size_t want ) {
foo_addr_t *next = NULL;
size_t size;
if ( !page || !addr ) return EDESTADDRREQ;
if ( (size = want % sizeof(void*)) )
want += sizeof(void*) - size;
if ( (next = addr->next) ) {
for ( next = addr->next; addr->size < want; next = next->next ) {
if ( next->data ) return ENOMEM;
addr->size += (next->size + sizeof(foo_addr_t));
if ( next == page->last ) {
next = NULL;
page->last = addr;
break;
}
addr->next = next->next;
}
}
addr->next = next;
if ( addr->size < want ) return ENOMEM;
addr->data = (uchar*)(addr + sizeof(foo_addr_t));
if ( !next && addr->size > want ) {
if ( addr->size - want > sizeof(foo_addr_t) ) {
next = (foo_addr_t*)((uintptr_t)(addr->data) + want);
if ( (void*)next >= (void*)
((uintptr_t)(page->stop) - (sizeof(foo_addr_t) + 1)) ) {
printf("%s(1) page = %p, addr = %p, want = %zu\n", __func__, page, addr, want );
return EXIT_SUCCESS;
}
next->next = addr->next;
next->prev = addr;
addr->next = next;
next->size = (addr->size - want) - sizeof(foo_addr_t);
next->data = (void*)((uintptr_t)next + sizeof(foo_addr_t));
addr->size = want;
if ( page->last == addr ) page->last = next;
}
}
printf("%s(2) page = %p, addr = %p, want = %zu\n", __func__, page, addr, want );
return EXIT_SUCCESS;
}
int foo__new_addr(
foo_page_t **dst, foo_addr_t **pos, size_t want )
{
foo_page_t *page = NULL;
foo_addr_t *addr = NULL;
if ( !dst || !pos ) return EDESTADDRREQ;
size_t p;
*dst = NULL;
*pos = NULL;
for ( p = 0; p < pages_used; ++p ) {
page = &(pages[p]);
addr = page->root;
while ( addr ) {
if ( foo__try_addr( page, addr, want ) == EXIT_SUCCESS ) {
*dst = page;
*pos = addr;
printf("%s(1) page = %p, addr = %p, want = %zu\n", __func__, page, addr, want );
return EXIT_SUCCESS;
}
addr = addr->next;
}
}
if ( pages_used == pages_upto ) {
pages_want = sizeof(foo_page_t) * (pages_used + 100);
page = (foo_page_t*)realloc((void*)pages, pages_want);
if ( !page ) {
if ( errno == EXIT_SUCCESS ) errno = ENOMEM;
return errno;
}
pages = page;
pages_upto += 100;
pages_size = pages_want;
}
page = &(pages[p]);
page->size = sysconf(_SC_PAGESIZE);
if ( want > page->size ) page->size *= (want / page->size)+1;
if ( page_fd < 0 ) {
page_fd = open("/dev/zero", O_RDWR);
if ( page_fd < 0 ) {
if (errno == EXIT_SUCCESS) errno = EXIT_FAILURE;
return errno;
}
}
page->base = mmap( NULL, page->size,
PROT_READ | PROT_WRITE | PROT_EXEC, MAP_SHARED, page_fd ,0);
if ( !(page->base) || page->base == (uchar*)-1 ) {
if ( errno == EXIT_SUCCESS ) errno = ENOMEM;
return errno;
}
++pages_used;
page->stop = (page->base + page->size);
if ( (p = (uintptr_t)(page->base) % sizeof(void*)) ) {
page->data = page->base + p;
page->left = page->size - p;
}
else {
page->data = page->base;
page->left = page->size;
}
addr = page->last = page->root =
(foo_addr_t*)(memset( page->data, 0, page->left ));
addr->size = page->left - sizeof(foo_addr_t);
addr->next = page->last;
addr->data = NULL;
if ( (errno = foo__try_addr( page, addr, want )) != EXIT_SUCCESS )
return errno;
*dst = page;
*pos = addr;
printf("%s(2) page = %p, addr = %p, want = %zu\n", __func__, page, addr, want );
return EXIT_SUCCESS;
}
int foo__alloc( void **dst, size_t want ) {
foo_page_t *page = NULL;
foo_addr_t *addr = NULL, *prev = NULL;
if ( !dst ) return EDESTADDRREQ;
if ( !want ) {
if ((errno = foo__has_addr( &page, &addr, *dst ))
!= EXIT_SUCCESS)
return errno;
*dst = NULL;
addr->data = NULL;
return EXIT_SUCCESS;
}
if ( *dst ) {
if ((errno = foo__has_addr(&page,&prev,*dst))
!= EXIT_SUCCESS)
return errno;
if ( foo__try_addr( page, prev, want ) == EXIT_SUCCESS ) {
printf("%s(1) page = %p, addr = %p, want = %zu\n", __func__, page, addr, want );
return EXIT_SUCCESS;
}
if ( (errno = foo__new_addr( &page, &addr, want ))
!= EXIT_SUCCESS )
return errno;
printf("%s(2) page = %p, addr = %p, want = %zu\n", __func__, page, addr, want );
*dst = memcpy( addr->data, prev->data, prev->size );
prev->data = NULL;
return EXIT_SUCCESS;
}
if ( (errno = foo__new_addr( &page, &addr, want ))
!= EXIT_SUCCESS )
return errno;
printf("%s(3) page = %p, addr = %p, want = %zu\n", __func__, page, addr, want );
if ( (errno = foo__try_addr( page, addr, want )) != EXIT_SUCCESS )
return errno;
*dst = addr->data;
return EXIT_SUCCESS;
}
void foo__freeall() {
size_t p;
for ( p = 0; p < pages_used; ++p )
munmap( pages[p].base, sysconf(_SC_PAGESIZE) );
free(pages);
pages = NULL;
pages_used = pages_upto = 0;
pages_size = pages_want = 0;
if ( page_fd >= 0 ) close(page_fd);
}
void *foo_alloc( void *ud, void *ptr, size_t size, size_t want ) {
uchar *tmp = ptr;
(void)ud;
if ( (errno = foo__alloc( (void**)(&tmp), want ))
!= EXIT_SUCCESS )
return NULL;
if ( !want ) return NULL;
if ( !ptr || !size ) memset( tmp, 0, want );
if ( size < want ) memset( &tmp[size], 0, want - size );
return tmp;
}
int main( int argc, char *argv[] ) {
size_t size = 8096;
char *buff = NULL;
atexit(foo_atexit);
puts("Allocating memory...");
if ( !(buff = foo_alloc(NULL,buff,0,size)) )
return fail();
puts("Clearing memory...");
memset(buff,0,size);
puts("Filling memory...");
strcpy( buff, "Hello World!\n" );
puts( buff );
puts("Releasing memory...");
foo_alloc( NULL, buff, size, 0 );
foo__freeall();
return EXIT_SUCCESS;
}