simple region allocator...

C

Chris M. Thomasson

Here is the pre-alpha v-0.0.1 impl:
_____________________________________________________________________
/* Simple Circular Doubly Linked-List
______________________________________________________________*/
#include <stddef.h>


#define CONTAINS(mp_this, mp_struct, mp_member) ((void*)( \
((ptrdiff_t)(mp_this)) - offsetof(mp_struct, mp_member) \
))


struct dlink {
struct dlink* next;
struct dlink* prev;
};


static void
dlinit(
struct dlink* const self
) {
self->next = self->prev = self;
}


static void
dlprv_insert(
struct dlink* const self,
struct dlink* const prev,
struct dlink* const next
) {
next->prev = self;
self->next = next;
self->prev = prev;
prev->next = self;
}


static void
dlprv_remove(
struct dlink* const prev,
struct dlink* const next
) {
next->prev = prev;
prev->next = next;
}


#define dlgethd(mp_self) ((mp_self)->next)
#define dlgettl(mp_self) ((mp_self)->prev)


#define dlpushhd(mp_self, mp_link) ( \
dlprv_insert((mp_link), (mp_self), (mp_self)->next) \
)


#define dlpushtl(mp_self, mp_link) ( \
dlprv_insert((mp_link), (mp_self)->prev, (mp_self)) \
)


#define dlpop(mp_self) ( \
dlprv_remove((mp_self)->prev, (mp_self)->next) \
)




/* Nasty Alignment HACK! ;^(...
______________________________________________________________*/
enum aligns_hack_enum {
ALIGNS_HACK_ENUM_1, ALIGNS_HACK_ENUM_2
};


struct aligns_hack {
char char_;
short int short_;
int int_;
long intlong_;
float float_;
double double_;
long double long_double_;
void* ptr_;
void* (*fptr_) (void*);
enum aligns_hack_enum enum_;
};


struct aligner_hack {
char pad;
struct aligns_hack aligns_hack;
};


#define ALIGN_MAX offsetof(struct aligner_hack, aligns_hack)

#define ALIGN_SIZE(mp_this, mp_type, mp_align) ((mp_type)( \
(((ptrdiff_t const)(mp_this)) + (mp_align) - 1) \
& (-(mp_align)) \
))




/* Simple General Purpose Region Allocator
______________________________________________________________*/
#include <stdlib.h>
#include <errno.h>


/* nasty <errno.h> hack wrt ENOMEM!!!!!! */
#if ! defined(ENOMEM)
# define ENOMEM -666
#endif


#define REGION_SIZE (1024 * 64)


struct region {
unsigned char buf[REGION_SIZE];
size_t offset;
struct dlink dlink;
};


struct ralloc {
struct dlink regions;
};


static void*
region_prv_alloc(
struct region* const self,
size_t const size
) {
size_t const offset = self->offset;
if (offset + size <= REGION_SIZE) {
self->offset = offset + size;
return self->buf + offset;
}
return NULL;
}


static struct region*
ralloc_prv_expand(
struct ralloc* const self
) {
struct region* const region = malloc(sizeof(*region));
if (region) {
region->offset = 0;
dlpushhd(&self->regions, &region->dlink);
return region;
}
return NULL;
}


static int
ralloc_create(
struct ralloc* const self
) {
dlinit(&self->regions);
if (ralloc_prv_expand(self)) {
return 0;
}
return ENOMEM;
}


static void
rflush(
struct ralloc* const self
) {
struct region* region =
CONTAINS(dlgethd(&self->regions), struct region, dlink);
if (region->dlink.next != &self->regions) {
region = CONTAINS(region->dlink.next, struct region, dlink);
while (&region->dlink != &self->regions) {
struct region* next =
CONTAINS(region->dlink.next, struct region, dlink);
dlpop(&region->dlink);
free(region);
region = next;
}
}
region = CONTAINS(dlgethd(&self->regions), struct region, dlink);
region->offset = 0;
}


static void*
ralloc(
struct ralloc* const self,
size_t size
) {
struct region* region =
CONTAINS(dlgethd(&self->regions), struct region, dlink);
size = (size) ? ALIGN_SIZE(size, size_t, ALIGN_MAX) : ALIGN_MAX;
while (&region->dlink != &self->regions) {
void* const mem = region_prv_alloc(region, size);
if (mem) {
return mem;
}
region = CONTAINS(region->dlink.next, struct region, dlink);
}
region = ralloc_prv_expand(self);
if (region) {
return region_prv_alloc(region, size);
}
return NULL;
}


static void
ralloc_destroy(
struct ralloc* const self
) {
rflush(self);
free(CONTAINS(dlgethd(&self->regions), struct region, dlink));
}




/* Simple Example Usage
______________________________________________________________*/
#define RUNS 10
#define DEPTH (1024 * 64)


struct node {
struct node* next;
};


static struct node* g_list = NULL;
static struct ralloc g_ralloc;


int main(void) {
if (! ralloc_create(&g_ralloc)) {
unsigned i, r;

for (r = 0; r < RUNS; ++r) {
/* create linked-list */
for (i = 0; i < DEPTH; ++i) {
struct node* n = ralloc(&g_ralloc, sizeof(*n));
if (! n) { break; }
n->next = g_list;
g_list = n;
}

/* destroy linked-list */
g_list = NULL;
rflush(&g_ralloc);
}

ralloc_destroy(&g_ralloc);

return EXIT_SUCCESS;
}

return EXIT_FAILURE;
}
_____________________________________________________________________




Caveats:

- Can only allocate sizes <= `REGION_SIZE'! ;^(... However, this can be
omitted by using some tricks.

- Can only free all memory in one shot.

- Cannot free individual objects; this can be omitted by using an existing
reap algorithm.

- Uses nasty alignment hack.

- Uses nasty errno hack; however, this can be omitted.




Advantages:

- Can partition regions on a per-data-structure basis.

- Can destroy memory that makes up nodes within a container without explicit
traversal.

- Can potentially help remove memory leaks.

- Do not need to free individual objects.




What do you think?
 
C

Chris M. Thomasson

Chris M. Thomasson said:
Here is the pre-alpha v-0.0.1 impl:
_____________________________________________________________________
[...]

/* Nasty Alignment HACK! ;^(...
______________________________________________________________*/
enum aligns_hack_enum {
ALIGNS_HACK_ENUM_1, ALIGNS_HACK_ENUM_2
};


struct aligns_hack {
char char_;
short int short_;
int int_;
long intlong_;
float float_;
double double_;
long double long_double_;
void* ptr_;
void* (*fptr_) (void*);
enum aligns_hack_enum enum_;
};
Click to expand...
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

`struct aligns_hack' should be a union! ARGH:


union aligns_hack {
char char_;
short int short_;
int int_;
long intlong_;
float float_;
double double_;
long double long_double_;
void* ptr_;
void* (*fptr_) (void*);
enum aligns_hack_enum enum_;
};



struct aligner_hack {
char pad;
struct aligns_hack aligns_hack;
Click to expand...
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

union aligns_hack aligns_hack;
};

#define ALIGN_MAX offsetof(struct aligner_hack, aligns_hack)

#define ALIGN_SIZE(mp_this, mp_type, mp_align) ((mp_type)( \
(((ptrdiff_t const)(mp_this)) + (mp_align) - 1) \
& (-(mp_align)) \
))
Click to expand...

[...]




Sorry about that non-sense!

;^(...
 
C

Chris M. Thomasson

There was a nasty bug in the original code. It did not safely iterate the
region list on `rflush()' and `ralloc()'; here is fix:




/* Simple Circular Doubly Linked-List
______________________________________________________________*/
#include <stddef.h>


#define CONTAINS(mp_this, mp_struct, mp_member) ((void*)( \
((unsigned char*)(mp_this)) - offsetof(mp_struct, mp_member) \
))


struct dlink {
struct dlink* next;
struct dlink* prev;
};


static void
dlinit(
struct dlink* const self
) {
self->next = self->prev = self;
}


static void
dlprv_insert(
struct dlink* const self,
struct dlink* const prev,
struct dlink* const next
) {
next->prev = self;
self->next = next;
self->prev = prev;
prev->next = self;
}


static void
dlprv_remove(
struct dlink* const prev,
struct dlink* const next
) {
next->prev = prev;
prev->next = next;
}


#define dlgethd(mp_self) ((mp_self)->next)
#define dlgettl(mp_self) ((mp_self)->prev)

#define dlpushhd(mp_self, mp_link) ( \
dlprv_insert((mp_link), (mp_self), (mp_self)->next) \
)


#define dlpushtl(mp_self, mp_link) ( \
dlprv_insert((mp_link), (mp_self)->prev, (mp_self)) \
)


#define dlpop(mp_self) ( \
dlprv_remove((mp_self)->prev, (mp_self)->next) \
)


/* Nasty Alignment HACK! ;^(...
______________________________________________________________*/
enum aligns_hack_enum {
ALIGNS_HACK_ENUM_1, ALIGNS_HACK_ENUM_2
};


union aligns_hack {
char char_;
short int short_;
int int_;
long intlong_;
float float_;
double double_;
long double long_double_;
void* ptr_;
void* (*fptr_) (void*);
enum aligns_hack_enum enum_;
};


struct aligner_hack {
char pad;
union aligns_hack aligns_hack;
};


#define ALIGN_MAX offsetof(struct aligner_hack, aligns_hack)

#define ALIGN_SIZE(mp_this, mp_type, mp_align) ((mp_type)( \
(((ptrdiff_t const)(mp_this)) + (mp_align) - 1) \
& (-(mp_align)) \
))


/* Simple General Purpose Region Allocator
______________________________________________________________*/
#include <stdlib.h>
#include <errno.h>


/* nasty <errno.h> hack wrt ENOMEM!!!!!! */
#if ! defined(ENOMEM)
# define ENOMEM -666
#endif


#define REGION_SIZE (1024 * 32)


struct region {
unsigned char buf[REGION_SIZE];
size_t offset;
struct dlink dlink;
};


struct ralloc {
struct dlink regions;
};


static void*
region_prv_alloc(
struct region* const self,
size_t const size
) {
size_t const offset = self->offset;
if (offset + size <= REGION_SIZE) {
self->offset = offset + size;
return self->buf + offset;
}
return NULL;
}


static struct region*
ralloc_prv_expand(
struct ralloc* const self
) {
struct region* const region = malloc(sizeof(*region));
if (region) {
region->offset = 0;
dlpushhd(&self->regions, &region->dlink);
return region;
}
return NULL;
}


static int
ralloc_create(
struct ralloc* const self
) {
dlinit(&self->regions);
if (ralloc_prv_expand(self)) {
return 0;
}
return ENOMEM;
}


static void
rflush(
struct ralloc* const self
) {
struct region* region;
struct dlink* dlink = dlgethd(&self->regions);
if (dlink->next != &self->regions) {
dlink = dlink->next;
while (dlink != &self->regions) {
struct dlink* next = dlink->next;
region = CONTAINS(dlink, struct region, dlink);
dlpop(dlink);
free(region);
dlink = next;
}
}
region = CONTAINS(dlgethd(&self->regions), struct region, dlink);
region->offset = 0;
}


static void*
ralloc(
struct ralloc* const self,
size_t size
) {
struct region* region;
struct dlink* dlink = dlgethd(&self->regions);
size = (size) ? ALIGN_SIZE(size, size_t, ALIGN_MAX) : ALIGN_MAX;
while (dlink != &self->regions) {
void* mem;
region = CONTAINS(dlink, struct region, dlink);
mem = region_prv_alloc(region, size);
if (mem) {
return mem;
}
dlink = dlink->next;
}
region = ralloc_prv_expand(self);
if (region) {
return region_prv_alloc(region, size);
}
return NULL;
}


static void
ralloc_destroy(
struct ralloc* const self
) {
rflush(self);
free(CONTAINS(dlgethd(&self->regions), struct region, dlink));
}


/* Simple Example Usage
______________________________________________________________*/
#define RUNS 10
#define DEPTH (1024 * 512)

struct node {
struct node* next;
};


static struct node* g_list = NULL;
static struct ralloc g_ralloc;

int main(void) {
if (! ralloc_create(&g_ralloc)) {
unsigned i, r;


for (r = 0; r < RUNS; ++r) {
/* create linked-list */
for (i = 0; i < DEPTH; ++i) {
struct node* n = ralloc(&g_ralloc, sizeof(*n));
if (! n) { break; }
n->next = g_list;
g_list = n;
}


/* destroy linked-list */
g_list = NULL;
rflush(&g_ralloc);
}


ralloc_destroy(&g_ralloc);


return EXIT_SUCCESS;
}

return EXIT_FAILURE;
}






Sorry for that non-sense! Anyway, can you notice any more nasty bugs?



Thanks!
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

simple reap allocator... 0
a simple type-based C++ region allocator... 9
Queue in C 25
Need Help with List Destroy Function in Storage Allocator ( LongCode ) 6
Need Help with List Destroy function in Storage Allocator ( LongCode ) 0
A cast question 3
undefined behavior in "macro-based" single-linked list impl... 2
Request for source code review of simple Ising model 88

Members online

No members online now.
Total: 297 (members: 2, guests: 295)
Robots: 379

Forum statistics

Threads
473,967
Messages
2,570,148
Members
46,694
Latest member
LetaCadwal

Latest Threads

Top