luserXtrog
5/10/2011 6:47:00 AM
I'm trying to build a new memory allocation scheme for
my postscript interpreter to satisfy these requirements:
% pointer + offset + size + short tag <= 32bits
% 'garbage-collection'-ready (structure the heap for easy iteration)
% all memory is in one region for easy restore from disk
So I've written a prototype where the "pointer" is an index
into an extendable address table stored in the heap itself.
And it seems to work! But I don't trust it, you know?
I'd appreciate any comments the experts here could offer.
One apology. I'm trying to use mmap if available or malloc
as a fallback, but ifdefs, it seems, can't be made pretty.
Or, at least I have yet to discover how, unless it's just to
"put it in a file you don't need to look at". :)
569(1)01:27 AM:proto 0> make v
cc -g -Wall v.c -o v
570(1)01:27 AM:proto 0> v
put seven, got a 7
571(1)01:27 AM:proto 0> cat v.c
#define MMAP
#define _GNU_SOURCE
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#ifdef MMAP
#include <sys/mman.h>
#endif /* otherwise, use malloc/realloc/free */
void error(char *msg) {
fprintf(stderr, "%s\n", msg);
exit(EXIT_FAILURE);
}
unsigned pgsz /*= getpagesize()*/;
typedef struct {
unsigned char *base;
unsigned used;
unsigned max;
} mfile;
/* initialize the memory file */
void initmem(mfile *mem) {
#ifdef MMAP
mem->base = mmap(NULL, pgsz, PROT_READ|PROT_WRITE, MAP_SHARED
|MAP_ANONYMOUS,-1,0 );
if (mem->base == MAP_FAILED)
#else
mem->base = malloc(pgsz);
if (mem->base == NULL)
#endif
error("unable to initialize memory file");
mem->used = 0;
mem->max = pgsz;
}
/* destroy memory file */
void exitmem(mfile *mem) {
#ifdef MMAP
munmap(mem->base, mem->max);
#else
free(mem->base);
#endif
mem->base = NULL;
mem->used = 0;
mem->max = 0;
}
/* grow memory by sz */
void growmem(mfile *mem, unsigned sz) {
unsigned char *tmp;
if (sz < pgsz) sz = pgsz;
else sz = (sz/pgsz + 1) * pgsz;
sz += mem->max;
#ifdef MMAP
tmp = mremap(mem->base, mem->max, sz, MREMAP_MAYMOVE);
if (tmp == MAP_FAILED)
#else
tmp = realloc(mem->base, sz);
if (!tmp)
#endif
error("unable to grow memory");
mem->base = tmp;
mem->max = sz;
}
/* allocate memory, returns offset in memory file */
unsigned mfalloc(mfile *mem, unsigned sz) {
unsigned adr = mem->used;
if (sz + mem->used > mem->max) growmem(mem,sz);
mem->used += sz;
return adr;
}
#define TABSZ 1000
typedef struct {
unsigned nexttab;
unsigned nextent;
struct {
unsigned adr;
} tab[TABSZ];
} mtab;
/* allocate and initialize a new table */
unsigned initmtab(mfile *mem) {
unsigned adr;
adr = mfalloc(mem, sizeof(mtab)); /*create mtab at address 0*/
memset(mem->base + adr, 0, sizeof(mtab));
return adr;
}
/* allocate memory, returns table index */
unsigned mtalloc(mfile *mem, unsigned mtabloc, unsigned sz) {
mtab *tab = (void *)(mem->base + mtabloc);
if (tab->nextent >= TABSZ)
return mtalloc(mem, tab->nexttab, sz);
else {
unsigned ent = tab->nextent;
tab->nextent++;
tab->tab[ent].adr = mfalloc(mem, sz);
if (tab->nextent == TABSZ) {
tab->nexttab = initmtab(mem);
}
return ent;
}
}
/* fetch a value from a composite object */
void get(mfile *mem, unsigned ent, unsigned offset, unsigned sz, void
*dest) {
mtab *tab;
unsigned mtabloc = 0;
tab = (void *)(mem->base + mtabloc);
while (ent >= TABSZ) {
tab = (void *)(mem->base + mtabloc);
mtabloc = tab->nexttab;
ent -= TABSZ;
}
memcpy(dest, mem->base + tab->tab[ent].adr + offset*sz, sz);
}
/* put a value into a composite object */
void put(mfile *mem, unsigned ent, unsigned offset, unsigned sz, void
*src) {
mtab *tab;
unsigned mtabloc = 0;
tab = (void *)(mem->base + mtabloc);
while (ent >= TABSZ) {
tab = (void *)(mem->base + mtabloc);
mtabloc = tab->nexttab;
ent -= TABSZ;
}
memcpy(mem->base + tab->tab[ent].adr + offset*sz, src, sz);
}
mfile mem;
/* initialize everything */
void init(void) {
pgsz = getpagesize();
initmem(&mem);
(void)initmtab(&mem); /* init table zero */
}
/* destroy everything */
void xit(void) {
exitmem(&mem);
}
int main() {
init();
unsigned adr;
int seven = 7;
int ret;
adr = mtalloc(&mem, 0, sizeof seven);
put(&mem, adr, 0, sizeof seven, &seven);
get(&mem, adr, 0, sizeof seven, &ret);
printf("put seven, got a %d\n", ret);
xit();
return 0;
}
--
572(1)01:27 AM:proto 0> !ni
nice -n 19 firefox &
[3] 4978
573(2)01:27 AM:proto 0>