Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
JET memory manager
// Simple chunked memory manager with mark/sweep garbage collection.
// Main code parses text files given as cmdline args as quick test.
// -jcw, 2017-12-01
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define CHUNK_BITS 3
#define CHUNK_SIZE (1 << CHUNK_BITS)
#define STORE_BITS 12
#define STORE_SIZE (1 << STORE_BITS)
static int nthRef (int cnum, int index);
static void showObject (int cnum);
//------------------------------------------------------------------------------
#define TYPE(cnum) tags[cnum].type
#define NEXT(cnum) tags[cnum].next
#define MARK(cnum) tags[cnum].mark
#define FREE NEXT(0)
struct {
uint16_t type :3;
uint16_t next :STORE_BITS;
uint16_t mark :1;
} tags [STORE_SIZE];
static int countFreeChunks (void) {
int n = 0;
for (int first = FREE; first != 0; first = NEXT(first))
++n;
return n;
}
static int chunkSize (int cnum) {
int sz = 0;
while (NEXT(cnum) > CHUNK_SIZE) {
sz += CHUNK_SIZE;
cnum = NEXT(cnum);
}
return sz + NEXT(cnum);
}
static void markChunk (int cnum) {
if (cnum <= CHUNK_SIZE || MARK(cnum))
return;
MARK(cnum) = 1;
if (TYPE(cnum) == 0) {
int n = chunkSize(cnum) >> 1;
for (int i = 0; i < n; ++i)
markChunk(nthRef(cnum, i));
}
for (;;) {
cnum = NEXT(cnum);
if (cnum <= CHUNK_SIZE)
break;
markChunk(cnum);
}
}
static void sweepChunks (void) {
int f = 0;
// release in reverse order, so new ones get allocated in forward order
// for (int i = CHUNK_SIZE + 1; i < STORE_SIZE; ++i)
for (int i = STORE_SIZE - 1; i > CHUNK_SIZE; --i)
if (MARK(i))
MARK(i) = 0;
else
NEXT(i) = f, f = i;
FREE = f;
}
//------------------------------------------------------------------------------
typedef struct {
int16_t i :15;
uint16_t f :1;
} Value;
//------------------------------------------------------------------------------
enum { T_OBJ, T_STR, T_INT, T_FLT };
union {
char m [CHUNK_SIZE];
long l;
double d;
Value v;
} store [STORE_SIZE];
static void* chunkOffset (int cnum, int off) {
while (off >= CHUNK_SIZE) {
if (NEXT(cnum) <= CHUNK_SIZE)
return 0;
cnum = NEXT(cnum);
}
return store[cnum].m + off;
}
static int nthRef (int cnum, int index) {
Value* p = chunkOffset(cnum, index << 1);
return p != 0 && p->f ? p->i : 0;
}
static Value newChunk (int type, int size) {
Value v;
v.i = FREE;
v.f = 1;
for (;;) {
assert(FREE != 0); // fails when out of memory
if (size <= CHUNK_SIZE)
break;
size -= CHUNK_SIZE;
FREE = NEXT(FREE);
}
int next = NEXT(FREE);
NEXT(FREE) = size;
FREE = next;
TYPE(v.i) = type;
return v;
}
static Value longToVal (long l) {
Value v;
v.i = l;
if (v.i == l)
v.f = 0;
else {
v = newChunk(T_INT, sizeof (long));
store[v.i].l = l;
}
return v;
}
static Value doubleToVal (double d) {
Value v = newChunk(T_FLT, sizeof (double));
store[v.i].d = d;
return v;
}
static Value stringToVal (const char* s) {
int n = strlen(s) + 1;
Value v = newChunk(T_STR, n);
int cnum = v.i;
while (n > 0) {
strncpy(store[cnum].m, s, CHUNK_SIZE);
s += CHUNK_SIZE;
n -= CHUNK_SIZE;
cnum = NEXT(cnum);
}
return v;
}
static void pushValue (int cnum, Value v) {
// FIXME assert(TYPE(cnum) = T_OBJ);
while (NEXT(cnum) > CHUNK_SIZE)
cnum = NEXT(cnum);
if (NEXT(cnum) == CHUNK_SIZE) {
assert(FREE != 0); // out of memory
cnum = NEXT(cnum) = FREE;
FREE = NEXT(cnum);
NEXT(cnum) = 0;
}
*(Value*) (store[cnum].m + NEXT(cnum)) = v;
NEXT(cnum) += sizeof (Value);
}
//------------------------------------------------------------------------------
static void showString (int cnum) {
printf("'");
do {
printf("%.*s", CHUNK_SIZE, store[cnum].m);
cnum = NEXT(cnum);
} while (cnum > CHUNK_SIZE);
printf("'");
}
static void showValue (Value v) {
if (v.f == 0)
printf("%d", v.i);
else
switch (TYPE(v.i)) {
case T_OBJ: showObject(v.i); break;
case T_STR: showString(v.i); break;
case T_INT: printf("%ld", store[v.i].l); break;
case T_FLT: printf("%g", store[v.i].d); break;
default: printf("?"); break;
}
}
static void showObject (int cnum) {
printf("[");
int first = 1;
do {
const char* p = store[cnum].m;
cnum = NEXT(cnum);
for (int i = 0; i < cnum && i < CHUNK_SIZE; i += sizeof (Value)) {
if (first)
first = 0;
else
printf(" ");
showValue(*(Value*) (p + i));
}
} while (cnum > CHUNK_SIZE);
printf("]");
}
//------------------------------------------------------------------------------
static Value parseToken (const char* s) {
char* end;
long l = strtol(s, &end, 0);
if (end > s && *end == 0) {
return longToVal(l);
}
double d = strtod(s, &end);
if (end > s && *end == 0) {
return doubleToVal(d);
}
return stringToVal(s);
}
// note: buf is clobbered, strtok is not reentrant
static Value parseLine (char* buf) {
Value r = newChunk(T_OBJ, 0);
int curr = 0, stack [10];
stack[0] = r.i;
for (int i = 0; ; ++i) {
char* p = strtok(buf, " \t\r\n");
if (p == 0)
break;
buf = 0;
if (strcmp(p, "[") == 0) {
Value v = newChunk(T_OBJ, 0);
pushValue(stack[curr], v);
assert(curr < 9); // too deeply nested
stack[++curr] = v.i;
} else if (strcmp(p, "]") == 0) {
assert(curr > 0); // too many closing brackets
--curr;
} else {
Value v = parseToken(p);
pushValue(stack[curr], v);
}
}
return r;
}
static Value parseFile (const char* filename) {
FILE *fp = fopen(filename, "r");
if (fp == 0) {
perror(filename);
exit(1);;
}
Value r = newChunk(T_OBJ, 0);
char buf [100];
while (fgets(buf, sizeof buf, fp) != 0) {
Value v = parseLine(buf);
pushValue(r.i, v);
printf(" ");
showObject(v.i);
printf("\n");
}
fclose(fp);
return r;
}
//------------------------------------------------------------------------------
int main (int argc, const char* argv[]) {
assert(sizeof store[0] == CHUNK_SIZE);
assert(sizeof tags[0] == 2);
assert(sizeof (Value) == 2);
assert(T_OBJ == 0);
sweepChunks(); // this inits the free chain, assuming tags are all-zero
printf("store %lub, free %d x %db = %db\n",
sizeof store, countFreeChunks(), CHUNK_SIZE, chunkSize(0));
for (int i = 1; i < argc; ++i) {
Value v = parseFile(argv[i]);
int n = countFreeChunks();
markChunk(v.i);
sweepChunks();
printf("free %d => %d\n", n, countFreeChunks());
}
return 0;
}
@abstractsig

This comment has been minimized.

Show comment
Hide comment
@abstractsig

abstractsig Dec 13, 2017

I have found https://github.com/rhempel/umm_malloc to be a good memory manager for cpus with only a small amount of ram to play with.

It doesn't store any meta-data on the allocations by default but I found this was easy to add.

I have found https://github.com/rhempel/umm_malloc to be a good memory manager for cpus with only a small amount of ram to play with.

It doesn't store any meta-data on the allocations by default but I found this was easy to add.

@jcw

This comment has been minimized.

Show comment
Hide comment
@jcw

jcw Dec 13, 2017

Thanks for the pointer, I didn't know about that one. What I need is more than malloc, however - this is also a garbage collector, which frees unused memory, while letting me pass around and share nested data structures. Note that the above code is for even smaller contexts, I'm hoping this will work even for machines with as little as 8 Kbytes of RAM, i.e. well under 1000 chunks.

Owner

jcw commented Dec 13, 2017

Thanks for the pointer, I didn't know about that one. What I need is more than malloc, however - this is also a garbage collector, which frees unused memory, while letting me pass around and share nested data structures. Note that the above code is for even smaller contexts, I'm hoping this will work even for machines with as little as 8 Kbytes of RAM, i.e. well under 1000 chunks.

@abstractsig

This comment has been minimized.

Show comment
Hide comment
@abstractsig

abstractsig Dec 14, 2017

I think it is quite reasonable to expect to use GC memory with very small amounts of available memory.

To me, umm (with some small enhancements) is an example of a space efficient, garbage-collected memory manager with predictable performance suitable for small, real-time systems (allocating memory inside interrupt service routines is OK). Further it can be done without chaining fixed-size memory blocks, which is what I used to do before finding umm.

For example, I am currently using umm with a TI CC2650 (Arm cortex-M3) radio which has 20kB of RAM. I have modified umm to make it configurable to manage either tagged (garbage collected) or untagged malloc/free style memory. It is easy to iterate all allocated blocks which makes implementing garbage collection a simple matter of a few additional lines of code (see below). It is also quite easy to use flash as the underlying memory to get a read only memory. The minimum tagged allocation size in my case is 16 bytes: 4 bytes belong to umm, I use a 4 byte tag which leaves a minimum of 8 bytes of payload. So umm does have a bit more allocation overhead compared to your scheme but I think that this is compensated for with the benefit of continuous-block allocations of any size that you can cast to a C pointer. This means that the memory manager imposes no structural constraints on the composition of the tagged values.

For my CC2650 app. I use 3 umm instances, tagged-flash plus one each of tagged and untaged RAM which are 1kB, 4kB and 8kB respectively. (As a side note I am not trying to promote the CC2650; as a radio it is rubbish, but playing with umm on it has been fun.)

umm GC loop iterating all allocated blocks:
uint16_t blockNo = UMM_NBLOCK(memory,0) & UMM_BLOCKNO_MASK;
while( UMM_NBLOCK(memory,blockNo) & UMM_BLOCKNO_MASK ) {
//
// your test if blockNo should be freed or not ...
//
blockNo = UMM_NBLOCK(memory,blockNo) & UMM_BLOCKNO_MASK;
}

I think it is quite reasonable to expect to use GC memory with very small amounts of available memory.

To me, umm (with some small enhancements) is an example of a space efficient, garbage-collected memory manager with predictable performance suitable for small, real-time systems (allocating memory inside interrupt service routines is OK). Further it can be done without chaining fixed-size memory blocks, which is what I used to do before finding umm.

For example, I am currently using umm with a TI CC2650 (Arm cortex-M3) radio which has 20kB of RAM. I have modified umm to make it configurable to manage either tagged (garbage collected) or untagged malloc/free style memory. It is easy to iterate all allocated blocks which makes implementing garbage collection a simple matter of a few additional lines of code (see below). It is also quite easy to use flash as the underlying memory to get a read only memory. The minimum tagged allocation size in my case is 16 bytes: 4 bytes belong to umm, I use a 4 byte tag which leaves a minimum of 8 bytes of payload. So umm does have a bit more allocation overhead compared to your scheme but I think that this is compensated for with the benefit of continuous-block allocations of any size that you can cast to a C pointer. This means that the memory manager imposes no structural constraints on the composition of the tagged values.

For my CC2650 app. I use 3 umm instances, tagged-flash plus one each of tagged and untaged RAM which are 1kB, 4kB and 8kB respectively. (As a side note I am not trying to promote the CC2650; as a radio it is rubbish, but playing with umm on it has been fun.)

umm GC loop iterating all allocated blocks:
uint16_t blockNo = UMM_NBLOCK(memory,0) & UMM_BLOCKNO_MASK;
while( UMM_NBLOCK(memory,blockNo) & UMM_BLOCKNO_MASK ) {
//
// your test if blockNo should be freed or not ...
//
blockNo = UMM_NBLOCK(memory,blockNo) & UMM_BLOCKNO_MASK;
}

@dwaq

This comment has been minimized.

Show comment
Hide comment
@dwaq

dwaq Dec 14, 2017

This reminds me of EEPROM emulation because you're keeping track of status of various blocks. I wrote a logging system based on information in ST's AN2594. It might be useful to review their concepts to see if it gives you any ideas. More information available here

dwaq commented Dec 14, 2017

This reminds me of EEPROM emulation because you're keeping track of status of various blocks. I wrote a logging system based on information in ST's AN2594. It might be useful to review their concepts to see if it gives you any ideas. More information available here

@jcw

This comment has been minimized.

Show comment
Hide comment
@jcw

jcw Dec 14, 2017

There's definitely a benefit in having non-chunked memory.

Yes I've seen that @dwaq, thanks. Slightly different use case I think, I need the following two: 1) structured objects, entirely in ROM (flash), never changed, only referencing other ROM objects, and 2) structured objects, in RAM, which can also point to some fixed elements (structured objects, strings, etc) in ROM. I don't need frequent r/w of flash/eeprom, the data structures will represent the "application" that needs to run on power-up (or more accurately: the configuration and wiring between pre-loaded components).

I now have a first/crude implementation which does this. It can handle up to 4000 chunks in RAM and 16000 objects in ROM, and the latter are not chunked. This will handle RAM up to about 30 KB and ROM up to around 200 KB, which should be enough to cover the microcontroller ranges I'm currently interested in, with some room for expansion.

Owner

jcw commented Dec 14, 2017

There's definitely a benefit in having non-chunked memory.

Yes I've seen that @dwaq, thanks. Slightly different use case I think, I need the following two: 1) structured objects, entirely in ROM (flash), never changed, only referencing other ROM objects, and 2) structured objects, in RAM, which can also point to some fixed elements (structured objects, strings, etc) in ROM. I don't need frequent r/w of flash/eeprom, the data structures will represent the "application" that needs to run on power-up (or more accurately: the configuration and wiring between pre-loaded components).

I now have a first/crude implementation which does this. It can handle up to 4000 chunks in RAM and 16000 objects in ROM, and the latter are not chunked. This will handle RAM up to about 30 KB and ROM up to around 200 KB, which should be enough to cover the microcontroller ranges I'm currently interested in, with some room for expansion.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment