save and getinterval with 8byte objects?
luser- -droog
the more expansive 12byte objects that xpost uses, and
I've hit a problem. If an array object is laid out like this,
struct {
unsigned char tag;
unsigned char pad;
unsigned short size;
unsigned long vmptr;
};
so that array objects are not distinguishable from
subarrays produced by getinterval, how does a
write operation to the subarray find the allocation
information to determine if it needs to copy before
writing?
Consider the postscript fragment:
5 array
dup 0 1 getinterval
0 save put
dup 0 get restore
==
It should print [null null null null null].
But for a moment it contained [save null null null null].
With the 12byte objects, I had room for a 16bit size
and a 16bit offset along with a 32bit pointer but
here I just don't see how to do it wthout scanning
through memory looking for a Magic Number.
But that just seems inelegant as well as inefficient.
I'm afraid to look through the gs source for this because
it's part of the memory management. Mr. Deutsch
invented early algorithms in the field! I fear the code
may not yield easy answers.
Any ideas?
luser- -droog
how does a
> write operation to the subarray find the allocation
> information to determine if it needs to copy before
> writing?
I suppose one obvious way is to add another level of indirection.
If the array object points to a descriptor which then points to
the actual data. Getinterval would allocate a new descriptor
which could contain an offset.
I fear I could easily confuse myself with extra pointers.
It multiplies terms, perhaps needlessly.
luser- -droog
I've come up with another idea, but it's very tricksy, and potentially
the most confusing way possible.
To recap:
struct ARRAY {
unsigned char tag;
unsigned short length;
unsigned short offset;
object *data;
};
won't fit nicely into 8 bytes. Unless we make the pointer smaller.
At first blush, if the pointer is stored as an integer offset from
a base pointer, it can be scaled down by the size of an object
(if data in vm is object-aligned), or integer indices into a dynamic
lookup-table. This last one I've rejected for a rather round-about
reason, but I'll spill it now because I think it helps motivate this
whole tangent.
To make the inner loop of the interpreter as simple as possible,
I want to define all the actions in terms of operators. So executing
a procedure involves
proc 0 get
to snag the first element (obviously) and
proc 1 1 index length 1 sub getinterval
to do a lisp CDR operation so the remainder can be executed
on the next iteration. So I want getinterval to be super-cheap.
It cannot allocate any new structures. No entry in a table.
No allocated descriptor.
So the tricksy idea is: to organize vm in a binary tree of allocations
and use a binary-encoded path for the "pointer".
A variable length binary tree path consists of a sequence of
single or double digits determined by the first digit.
0 - follow left path
10 - follow right path
11 - select this node
So "left,right,left,right,here" is 01001011 ???????? (8 bits of
padding).
I haven't done the math on how many allocations this allows.
But I hope it's enough to squeeze this thing into 16bits, and not
impose bizarre limitations.
I'm skimming Knuth right now (read the stories, skip the heavy math,
browse the exercises), maybe he's got something pertinent.
luser- -droog
> the more expansive 12byte objects that xpost uses, and
> I've hit a problem. If an array object is laid out like this,
>
> struct {
> unsigned char tag;
> unsigned char pad;
> unsigned short size;
> unsigned long vmptr;
>
> };
>
I think I've got a much better solution now.
I can squeeze the offset in by making the pointer
smaller by making the pointer a table index.
struct composite {
unsigned short tag; /*lsb-type, msb-flags*/
unsigned short size;
unsigned short tabind;
unsigned short offset;
};
This seems much more straightforward than that
encoded tree-path stuff. But I'm not quite sure
I can get away with it. We're clearly limited
to 65535 distinct composite objects. I can of
course steal a few bits from the tag or make
separate tables for array, string, dict etc.
But the PLRM makes no mention of a limit on the
number of active allocations, and level-2 is
supposed to remove limits, not add them.
On a related note, it seems potentially useful
to make the object size a compile-time option.
If I continue to use cairo, I'm going to pay
a speed penalty if I try to use 32-bit reals,
since they'll have to be converted to double
and back for every function call.
And if it's compiled for doubles, then it can
use a larger index field to increase the allocation
limit above notice.
If I go this route, would there be any value
in offering a 64-bit integer option?
Ps.
One more thing. PLRM says packed array elements occupy 1 to 9 bytes.
What kind of object needs 9 bytes packed but only 8 bytes unpacked?!!
luser- -droog
virtual memory module fitted together. This setup should
work with the object structure described upthread.
The composite-reference object will consist of 4 16-bit words:
{ tag; size; entity; offset; }
Entity is the "pointer", an integer index into an address table
with 32bit "pointers" to the actual memory. These address
table "pointers" are integer offsets from from a base pointer
to the start of virtual memory. This last pointer is the
real pointer.
The Offset in the reference is scaled by the data size of
the component objects in virtual memory (1 for strings,
8 for arrays, 16 for dictionary pairs).
In order to make growable stacks, I'm thinking of implementing
them in a manner very similar to the address tables here.
Each stack "segment" will have an integer cursor pointing
to the top, or if it's maxxed, the next-segment pointer will
point to the next one.
And I think I can speed up the launching of the interpreter
by backing up the vm memory to a file and just reloading it
from disk. I think I can put the operator table in there, too!
And if the file isn't present, it builds a new one using the
initops() function from xpost2.
Anyway, proud papa time.
540(1)02:05 AM:proto 0> cat v.c
#define TESTMODULE
/* define MMAP and MREMAP for Linux */
/* define MMAP without MREMAP should work for Irix (using AUTOGROW) */
/* define neither to use malloc/realloc/free */
#define MMAP
#define MREMAP
#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;
void pr_mfile(mfile *mem) {
printf("mfile: { .base = %p, "
".used = 0x%x (%u), "
".max = 0x%x (%u)};\n",
mem->base,
mem->used, mem->used,
mem->max, mem->max);
}
/* initialize the memory file */
void initmem(mfile *mem) {
#ifdef MMAP
mem->base = mmap(NULL, pgsz,
PROT_READ|PROT_WRITE, MAP_PRIVATE
# ifndef MREMAP
|MAP_AUTOGROW
# endif
|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) {
void *tmp;
//unsigned char *tmp;
//pr_mfile(mem);
if (sz < pgsz) sz = pgsz;
else sz = (sz/pgsz + 1) * pgsz;
sz += mem->max;
#ifdef MMAP
# ifdef MREMAP
tmp = mremap(mem->base, mem->max, sz, MREMAP_MAYMOVE);
# else
tmp = mem->base; /* without mremap, we rely on MAP_AUTOGROW */
# endif
if (tmp == MAP_FAILED)
#else
tmp = realloc(mem->base, sz);
if (!tmp)
#endif
error("unable to grow memory");
mem->base = tmp;
mem->max = sz;
//pr_mfile(mem);
}
/* 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;
bzero(mem->base+adr, sz);
/* bus error with mremap(map(SHARED,ANON)) ! */
return adr;
}
#define TABSZ 1000
typedef struct {
unsigned nexttab;
unsigned nextent;
struct {
unsigned adr;
unsigned sz;
/* add fields here for ref counts or marks */
} tab[TABSZ];
} mtab;
/* allocate and initialize a new table */
unsigned initmtab(mfile *mem) {
unsigned adr;
adr = mfalloc(mem, sizeof(mtab));
mtab *tab = (void *)(mem->base + adr);
tab->nexttab = 0;
tab->nextent = 0;
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);
tab->tab[ent].sz = 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;
}
if (offset*sz + sz > tab->tab[ent].sz) error("get: out of
bounds");
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;
}
if (offset*sz + sz > tab->tab[ent].sz) error("put: out of
bounds");
memcpy(mem->base + tab->tab[ent].adr + offset*sz, src, sz);
}
#ifdef TESTMODULE
mfile mem;
/* initialize everything */
void init(void) {
pgsz = getpagesize();
initmem(&mem);
(void)initmtab(&mem); /*create mtab at address 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);
unsigned adr2;
adr2 = mtalloc(&mem, 0, 8*sizeof seven);
put(&mem, adr2, 6, sizeof seven, &seven);
get(&mem, adr2, 6, sizeof seven, &ret);
printf("put seven in slot 7, got a %d\n", ret);
/*
get(&mem, adr2, 9, sizeof seven, &ret);
printf("attempted to retrieve element 10 from an 8-eleemnt array,
got %d \n", ret);
*/
unsigned adr3;
char str[] = "beads in buddha's necklace";
char sret[sizeof str];
adr3 = mtalloc(&mem, 0, strlen(str)+1);
put(&mem, adr3, 0, sizeof str, str);
get(&mem, adr3, 0, sizeof str, sret);
printf("stored and retrieved %s\n", sret);
xit();
return 0;
}
#endif
541(1)02:05 AM:proto 0>
luser- -droog
design.
There are some big problems with this code, but the small test works!
One problem is that none of these functions correctly handle multiple
address tables.
Here's the code, then the output, then some explanation of the output
so you don't have to read the code to understand it.
[ m is the memory module
ob describes the object type and simple constructors
s is the growable stack
ar is the array module
st is the string module
I'll put the headers at the very and the semantics should be
obvious. ]
543(2)06:02 PM:xpost3 0> cat gc.c
#include "m.h"
#include "ob.h"
#include "s.h"
#include "ar.h"
#include "st.h"
#ifdef TESTMODULE
#include <stdio.h>
#endif
void unmark(mfile *mem) {
mtab *tab = (void *)(mem->base);
int i;
next:
for (i=0; i < tab->nextent; i++) {
tab->tab[i].mark = 0;
}
if (i==TABSZ) { /* ie. s->top == STACKSEGSZ */
tab = (void *)(mem->base + tab->nexttab);
goto next;
}
}
void markent(mfile *mem, unsigned ent) {
mtab *tab = (void *)(mem->base);
while (ent >= TABSZ) {
tab = (void *)(mem->base + tab->nextent);
ent -= TABSZ;
}
tab->tab[ent].mark = 1;
}
int marked(mfile *mem, unsigned ent) {
mtab *tab = (void *)(mem->base);
while (ent >= TABSZ) {
tab = (void *)(mem->base + tab->nextent);
ent -= TABSZ;
}
return tab->tab[ent].mark;
}
unsigned adrent(mfile *mem, unsigned ent) {
mtab *tab = (void *)(mem->base);
while (ent >= TABSZ) {
tab = (void *)(mem->base + tab->nextent);
ent -= TABSZ;
}
return tab->tab[ent].adr;
}
void markarray(mfile *mem, unsigned adr, unsigned sz) {
object *op = (void *)(mem->base + adr);
int j;
for (j=0; j < sz; j++) {
switch(op->tag) {
case arraytype:
if (!marked(mem, op->comp_.ent)) {
markent(mem, op->comp_.ent);
markarray(mem, adrent(mem, op->comp_.ent), op-
>comp_.sz);
}
break;
case stringtype:
markent(mem, op->comp_.ent);
break;
}
op++;
}
}
/* mark all allocations refered to by objects in stack */
void markstack(mfile *mem, unsigned stackadr) {
stack *s = (void *)(mem->base + stackadr);
int i;
next:
for (i=0; i < s->top; i++) {
#ifdef TESTMODULE
printf("markstack: %d\n", s->data[i].tag);
#endif
switch(s->data[i].tag) {
case arraytype:
if (!marked(mem, s->data[i].comp_.ent)) {
markent(mem, s->data[i].comp_.ent);
markarray(mem, adrent(mem, s->data[i].comp_.ent), s-
>data[i].comp_.sz);
}
break;
case stringtype:
markent(mem, s->data[i].comp_.ent);
break;
}
}
if (i==STACKSEGSZ) { /* ie. s->top == STACKSEGSZ */
s = (void *)(mem->base + s->nextseg);
goto next;
}
}
void mfree(mfile *mem, unsigned ent) {
unsigned a = adrent(mem, ent);
*(unsigned *)(mem->base + a) = mem->avail;
mem->avail = ent;
}
void sweep(mfile *mem) {
mtab *tab = (void *)(mem->base);
int i;
next:
for (i=0; i < tab->nextent; i++) {
if (tab->tab[i].mark == 0)
mfree(mem, i);
}
if (i==TABSZ) { /* ie. s->top == STACKSEGSZ */
tab = (void *)(mem->base + tab->nexttab);
goto next;
}
}
void collect(mfile *mem, unsigned stackadr) {
unmark(mem);
markstack(mem, stackadr);
sweep(mem);
}
#ifdef TESTMODULE
mfile mem;
unsigned stac;
void init(void) {
initmem(&mem);
(void)initmtab(&mem);
stac = initstack(&mem);
}
int main(void) {
init();
push(&mem, stac, consint(5));
push(&mem, stac, consint(6));
push(&mem, stac, consreal(7.0));
object ar;
ar = consarr(&mem, 3);
int i;
for (i=0; i < 3; i++)
arrput(&mem, ar, i, pop(&mem, stac));
push(&mem, stac, ar);
/* array on stack */
push(&mem, stac, consint(1));
push(&mem, stac, consint(2));
push(&mem, stac, consint(3));
ar = consarr(&mem, 3);
for (i=0; i < 3; i++)
arrput(&mem, ar, i, pop(&mem, stac));
pr_obj(ar);
/* array not on stack */
#define CNT_STR(x) sizeof(x), x
push(&mem, stac, consstr(&mem, CNT_STR("string on stack")));
pr_obj(consstr(&mem, CNT_STR("string not on stack")));
collect(&mem, stac);
printf("stackadr: %04x\n", stac);
pr_mfile(&mem);
pr_mtab(&mem, 0);
return 0;
}
#endif
544(2)06:03 PM:xpost3 0> make test-gc
cc -g -Wall -c -o m.o m.c
cc -g -Wall -c -o s.o s.c
cc -g -Wall -c -o ob.o ob.c
cc -g -Wall -c -o st.o st.c
cc -g -Wall -c -o ar.o ar.c
cc -g -DTESTMODULE -o gc gc.c m.o s.o ob.o st.o ar.o
gc
%program output begins here:
{array, 3, 1, 0}
%this is the discarded array {tag, size, ent, offset}
{string, 20, 3, 0}
%this is the discarded string
markstack: 5
markstack: 6
%the markstack function tells us it is traversing an array (type 5)
% and then marking a string (type 6)
stackadr: 0080
% memory begins with the address table: 2 4-byte fields,
% followed by 10 pairs of 4-byte fields (address and size).
% the stack begins at hex 80
% the stack has 2 4-byte fields followed by 10 8-byte objects.
% then comes the heap.
000000 0000: 00 00 00 00 04 00 00 00 d8 00 00 00 18 00 00 00
000016 0010: 01 00 00 00 f0 00 00 00 18 00 00 00 00 00 00 00
000032 0020: 08 01 00 00 14 00 00 00 01 00 00 00 1c 01 00 00
000048 0030: 18 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
000064 0040: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
000080 0050: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
000096 0060: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
000112 0070: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
000128 0080: 00 00 00 00 02 00 00 00 05 00 03 00 00 00 00 00
000144 0090: 06 00 10 00 02 00 00 00 00 00 00 00 02 00 00 00
000160 00a0: 00 00 00 00 03 00 00 00 00 00 00 00 00 00 00 00
000176 00b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
000192 00c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
000208 00d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 e0 40
000224 00e0: 00 00 00 00 06 00 00 00 00 00 00 00 05 00 00 00
000240 00f0: 00 00 00 00 03 00 00 00 00 00 00 00 02 00 00 00
000256 0100: 00 00 00 00 01 00 00 00 73 74 72 69 6e 67 20 6f
000272 0110: 6e 20 73 74 61 63 6b 00 00 00 00 00 01 00 00 00
000288 0120: 6e 67 20 6e 6f 74 20 6f 6e 20 73 74 61 63 6b 00
000304 0130: 00 00 00 00 mfile: { .base = 0x4001e000, .used = 0x134
(308), .avail = 0x3 , .max = 0x1000 (4096)};
% .avail = 0x3 means entry 3 is the head of the free list
% the first 4 bytes at the address in that slot is the index
% of the next free node.
nexttab: 0 0000
% we haven't filled this table so nexttab is null
nextent: 4 0004
% we've only allocated 4 objects, in slots 0-3
0: 216 00d8 [24] #
00 00 00 00 00 00 e0 40 00 00 00 00 06 00 00 00 00 00 00 00 05 00 00
00
1: 240 00f0 [24] _
00 00 00 00 03 00 00 00 00 00 00 00 02 00 00 00 00 00 00 00 01 00 00
00
2: 264 0108 [20] #
73 74 72 69 6e 67 20 6f 6e 20 73 74 61 63 6b 00 00 00 00 00
3: 284 011c [24] _
01 00 00 00 6e 67 20 6e 6f 74 20 6f 6e 20 73 74 61 63 6b 00 00 00 00
00
% The format here is
%table-index: decimal-address hex-address [decimal-size] #=mark/
_=unmarked
% followed by a hex dump of size bytes starting at address.
% So we see 2 objects marked and 2 objects not marked.
% The free list starts with slot 3, and in the data of slot 3 we find
index 1
% which is also unmarked.
% So it's mostly working, pretty much!
% I can see from here that strings are getting too much padding.
So thanks for your patience.
% and here are those other headers I promised.
545(2)06:03 PM:xpost3 0> cat ob.h
typedef unsigned char byte;
typedef unsigned short word;
typedef unsigned long dword;
typedef int integer;
typedef float real;
typedef dword addr;
#define TYPES(_) \
_(invalid) \
_(null) \
_(mark) \
_(integer) \
_(real) \
_(array) \
_(string) \
/*enddef TYPES */
#define AS_TYPE(_) _ ## type ,
enum { TYPES(AS_TYPE) };
#define AS_STR(_) #_ ,
extern char *types[] /*= { TYPES(AS_STR) }*/;
typedef struct {
word tag;
word pad0;
word pad1;
word pad2;
} mark_;
typedef struct {
word tag;
word pad;
integer val;
} int_;
typedef struct {
word tag;
word pad;
real val;
} real_;
typedef struct {
word tag;
word sz;
word ent;
word off;
} comp_;
typedef union {
word tag;
mark_ null_;
mark_ mark_;
int_ int_;
real_ real_;
comp_ comp_;
} object;
extern object invalid /*= { .tag = invalidtype }*/;
extern object mark /*= { .tag = marktype }*/;
extern object null /*= { .tag = nulltype }*/;
object consint(integer i);
object consreal(real r);
void pr_obj(object o);
546(2)06:03 PM:xpost3 0> cat s.h
/* must include ob.h */
/*typedef long long object;*/
#define STACKSEGSZ 10
typedef struct {
unsigned nextseg;
unsigned top;
object data[STACKSEGSZ];
} stack;
unsigned initstack(mfile *mem);
void push(mfile *mem, unsigned stackadr, object o);
object pop(mfile *mem, unsigned stackadr);
/*int pop(mfile *mem, unsigned stackadr, object *po);*/
547(2)06:03 PM:xpost3 0> cat st.h
object consstr(mfile *mem, unsigned sz, char *ini);
void strput(mfile *mem, object s, integer i, integer c);
integer strget(mfile *mem, object s, integer i);
548(2)06:03 PM:xpost3 0> cat ar.h
object consarr(mfile *mem, unsigned sz);
void arrput(mfile *mem, object a, integer i, object o);
object arrget(mfile *mem, object a, integer i);
549(2)06:03 PM:xpost3 0>
luser- -droog
> I've got the barebones of a mark-sweep garbage collector for my new
> design.
> There are some big problems with this code, but the small test works!
> One problem is that none of these functions correctly handle multiple
> address tables.
>
> Here's the code, then the output, then some explanation of the output
> so you don't have to read the code to understand it.
>
> [ m is the memory module
> ob describes the object type and simple constructors
> s is the growable stack
> ar is the array module
> st is the string module
> I'll put the headers at the very and the semantics should be
> obvious. ]
>
> 543(2)06:02 PM:xpost3 0> cat gc.c
Sorry.
The address table holds 10 *triples* of 4-bytes fields
(address, size, mark).
[snip]
luser- -droog
> One problem is that none of these functions correctly handle multiple
> address tables.
>
[snip]
> void mfree(mfile *mem, unsigned ent) {
> unsigned a = adrent(mem, ent);
> *(unsigned *)(mem->base + a) = mem->avail;
> mem->avail = ent;
>
> }
>
> void sweep(mfile *mem) {
> mtab *tab = (void *)(mem->base);
> int i;
> next:
> for (i=0; i < tab->nextent; i++) {
> if (tab->tab[i].mark == 0)
> mfree(mem, i);
> }
> if (i==TABSZ) { /* ie. s->top == STACKSEGSZ */
> tab = (void *)(mem->base + tab->nexttab);
> goto next;
> }
>
> }
>
It looks like this is the only part that has problems
with multiple tables, because it's calling mfree with
a relative index.
So it should be more like this:
void sweep(mfile *mem) {
mtab *tab = (void *)(mem->base);
int ntab = 0;
int i;
next:
for (i=0; i < tab->nextent; i++) {
if (tab->tab[i].mark == 0)
mfree(mem, i + ntab*TABSZ);
}
if (i==TABSZ) {
tab = (void *)(mem->base + tab->nexttab);
++ntab;
goto next;
}
}
luser- -droog
For the save/restore to behave like a stack, it is best represented
as, surprise! a stack. So the save stack (VS) holds only save objects.
typedef struct {
word tag; // enum { ..., savetype, ... }
word lev; // save level is also position on stack
unsigned stk; // address of a stack to hold save-records
} save_;
Executing 'save' allocates a new stack to hold saverec objects
typedef struct {
unsigned src;
unsigned cpy;
} saverec_;
where src is the index in the address table for the object being
saved, and cpy is the index for a copy of the object which is
created when an unsaved object gets written into.
'restore' then merely has to pop each saverec and exchange the
address fields in the address table for the two entries.
The save stack itself will have to be part of the "root set"
of the garbage collector. I've decided to have the address
table begin with several "special entries": the head of the
free list, the save stack, the operand stack, execution stack,
dictionary stack.
/* special entries */
enum {
FREE,
VS,
OS,
ES,
DS,
};
So the local memory table will start with all of these, and
the global memory table will have just a free list and save stack.
I was surprised to read in PLRM2ed 3.7.7, that the outermost save
obtains a snapshot of the initial state of objects in both local
and global VM. So global needs a save stack, too.
I'm hoping that I've got the interfaces right this time, so I can
finally stop starting over from scratch to add new pieces.
So, to get anything from the save module, first you have to see
the stack module. And then probably the array module, too, to
see where the saverec_s get created (in arrput).
In consarr, you also see the packing of 4 fields into the mark
field of the address table. This is so it can hold a mark, a reference
count, the "low level" (save level at which object was created),
and the "top level" (highest level for which a saverec exists).
The reference count isn't currently used. This packing uses these
symbols from m.h for bitmasks and offsets:
/* fields in mtab.tab[].mark */
enum {
MARKM = 0xFF000000,
MARKO = 24,
RFCTM = 0x00FF0000,
RFCTO = 16,
LLEVM = 0x0000FF00,
LLEVO = 8,
TLEVM = 0x000000FF,
TLEVO = 0,
};
I know I don't need a whole byte for the mark, but it makes a nice
symmetry.
So here they are: stacks, save-stacks, arrays. And then the test
output from each one.
504(1)10:46 PM:xpost3 0> cat s.h s.c
/* must include ob.h */
/*typedef long long object;*/
#define STACKSEGSZ 10
typedef struct {
unsigned nextseg;
unsigned top;
object data[STACKSEGSZ];
} stack;
unsigned initstack(mfile *mem);
void pr_stack(mfile *mem, unsigned stackadr);
void sfree(mfile *mem, unsigned stackadr);
unsigned count(mfile *mem, unsigned stackadr);
void push(mfile *mem, unsigned stackadr, object o);
object top(mfile *mem, unsigned stackadr, integer i);
object pop(mfile *mem, unsigned stackadr);
//#define TESTMODULE
#include <stdlib.h> /* NULL */
#include "m.h" /* mfile mfalloc */
#include "ob.h" /* object size */
/*typedef long long object;*/
#include "s.h"
unsigned initstack(mfile *mem) {
unsigned adr = mfalloc(mem, sizeof(stack));
stack *s = (void *)(mem->base + adr);
s->nextseg = 0;
s->top = 0;
return adr;
}
void pr_stack(mfile *mem, unsigned stackadr) {
stack *s = (void *)(mem->base + stackadr);
int i;
while(1) {
for (i=0; i < s->top; i++) {
pr_obj(s->data[i]);
}
if (i != STACKSEGSZ) break;
s = (void *)(mem->base + s->nextseg);
}
}
void sfree(mfile *mem, unsigned stackadr) {
stack *s = (void *)(mem->base + stackadr);
if (s->nextseg) sfree(mem, s->nextseg);
mtab *tab;
unsigned e = mtalloc(mem, 0, 0);
findtabent(mem, &tab, &e);
tab->tab[e].adr = stackadr;
tab->tab[e].sz = sizeof(stack);
}
unsigned count(mfile *mem, unsigned stackadr) {
stack *s = (void *)(mem->base + stackadr);
unsigned ct = 0;
while (s->top == STACKSEGSZ) {
ct += STACKSEGSZ;
s = (void *)(mem->base + s->nextseg);
}
return ct + s->top;
}
void push(mfile *mem, unsigned stackadr, object o) {
stack *s = (void *)(mem->base + stackadr); /* load the stack */
while (s->top == STACKSEGSZ) { /* find top segment */
s = (void *)(mem->base + s->nextseg);
}
s->data[s->top++] = o; /* push value */
/* if push maxxed the topmost segment, link a new one */
if (s->top == STACKSEGSZ)
if (s->nextseg == 0)
s->nextseg = initstack(mem);
}
/* index the stack from top-down */
object top(mfile *mem, unsigned stackadr, integer i) {
stack *s = (void *)(mem->base + stackadr);
stack *p = NULL;
/* find top segment */
while (s->top == STACKSEGSZ) {
p = s;
s = (void *)(mem->base + stackadr);
}
if (s->top == 0) {
if (p != NULL)
s = p;
else
error("stack underflow");
}
return s->data[s->top-1-i];
}
object pop(mfile *mem, unsigned stackadr) {
stack *s = (void *)(mem->base + stackadr); /* load the stack */
stack *p = NULL;
while (s->top == STACKSEGSZ) { /* find top segment */
p = s;
s = (void *)(mem->base + s->nextseg);
}
if (s->top == 0) {
if (p != NULL)
s = p; /* back up if top is empty */
else
error("stack underflow");
}
return s->data[--s->top]; /* pop value */
}
#ifdef TESTMODULE
#include <stdio.h>
#include <unistd.h>
mfile mem;
unsigned s, t;
/* initialize everything */
void init(void) {
pgsz = getpagesize();
initmem(&mem);
s = initstack(&mem);
t = initstack(&mem);
}
/* destroy everything */
void xit(void) {
exitmem(&mem);
}
int main() {
init();
printf("test stack by reversing a sequence\n");
object a = { .int_.val = 2 }, b = { .int_.val = 12 }, c =
{ .int_.val = 0xF00 };
object x,y,z;
push(&mem, s, a);
push(&mem, s, b);
push(&mem, s, c);
x = pop(&mem, s); /* x = c */
push(&mem, t, x);
y = pop(&mem, s); /* y = b */
push(&mem, t, y);
z = pop(&mem, s); /* z = a */
push(&mem, t, z);
printf("x = %d, y = %d, z = %d\n", x.int_.val, y.int_.val,
z.int_.val);
x = pop(&mem, t); /* x = a */
y = pop(&mem, t); /* y = b */
z = pop(&mem, t); /* z = c */
printf("x = %d, y = %d, z = %d\n", x.int_.val, y.int_.val,
z.int_.val);
//z = pop(&mem, t); // trigger a stackunderflow
xit();
return 0;
}
#endif
505(1)10:47 PM:xpost3 0> cat v.h v.c
void initsave(mfile *mem);
object save(mfile *mem);
unsigned stashed(mfile *mem, unsigned ent);
unsigned copy(mfile *mem, unsigned ent);
void stash(mfile *mem, unsigned ent);
void restore(mfile *mem);
#include <assert.h>
#include <string.h>
#include "m.h"
#include "ob.h"
#include "s.h"
#include "gc.h"
/*
typedef struct {
unsigned lev;
unsigned stk;
} save_;
typedef struct {
unsigned src;
unsigned cpy;
} saverec_;
*/
/*create a stack in slot VS
sz is 0 so gc will ignore it
*/
void initsave(mfile *mem) {
unsigned ent = mtalloc(mem, 0, 0); /* allocate an entry of zero
length */
assert(ent == VS);
mtab *tab = (void *)mem->base;
tab->tab[ent].adr = initstack(mem);
}
/* push a new save object on the save stack
this object is itself a stack (contains a stackadr)
*/
object save(mfile *mem) {
object v = { .save_.tag = savetype,
.save_.lev = count(mem, adrent(mem, VS)),
.save_.stk = initstack(mem) };
push(mem, adrent(mem, VS), v);
return v;
}
/* check ent's tlev against current save level (save-stack count) */
unsigned stashed(mfile *mem, unsigned ent) {
//object sav = top(mem, adrent(mem, VS), 0);
unsigned cnt = count(mem, adrent(mem, VS));
mtab *tab;
findtabent(mem, &tab, &ent);
unsigned tlev = (tab->tab[ent].mark & TLEVM) >> TLEVO;
return tlev == cnt; //sav.save_.lev;
}
/* make a clone of ent, return new ent */
unsigned copy(mfile *mem, unsigned ent) {
mtab *tab;
findtabent(mem, &tab, &ent);
unsigned new = gballoc(mem, tab->tab[ent].sz);
memcpy(mem->base+adrent(mem, new), mem->base+tab->tab[ent].adr,
tab->tab[ent].sz);
return new;
}
/* set tlev for ent to current save level
push saverec relating ent to saved copy
*/
void stash(mfile *mem, unsigned ent) {
object sav = top(mem, adrent(mem, VS), 0);
mtab *tab;
unsigned rent = ent;
findtabent(mem, &tab, &rent);
unsigned tlev = sav.save_.lev;
tab->tab[rent].mark &= ~TLEVM;
tab->tab[rent].mark |= (tlev << TLEVO);
push(mem, sav.save_.stk,
(object){ .saverec_.src = ent, .saverec_.cpy = copy(mem,
ent) });
}
/* for each saverec from current save stack
exchange adrs between src and cpy
pop saverec
pop save stack
*/
void restore(mfile *mem) {
unsigned v = adrent(mem, VS);
//object sav = top(mem, v, 0);
object sav = pop(mem, v);
mtab *stab, *ctab;
unsigned cnt = count(mem, sav.save_.stk);
unsigned sent, cent;
while (cnt--) {
object rec = pop(mem, sav.save_.stk);
sent = rec.saverec_.src;
cent = rec.saverec_.cpy;
findtabent(mem, &stab, &sent);
findtabent(mem, &ctab, ¢);
unsigned hold;
hold = stab->tab[sent].adr;
stab->tab[sent].adr = ctab->tab[cent].adr;
ctab->tab[cent].adr = hold;
}
sfree(mem, sav.save_.stk);
//(void)pop(mem, v);
}
#ifdef TESTMODULE
#include "ar.h"
#include <stdio.h>
mfile mf;
void init(void) {
initmem(&mf);
(void)initmtab(&mf);
initfree(&mf);
initsave(&mf);
}
int main(void) {
mfile *mem = &mf;
init();
object a = consarr(mem, 2);
arrput(mem, a, 0, consint(33));
arrput(mem, a, 1, consint(66));
printf("%d\n", arrget(mem, a, 0).int_.val);
object v = save(mem);
pr_mtab(mem, 0);
pr_stack(mem, adrent(mem, VS));
arrput(mem, a, 0, consint(77));
pr_mtab(mem, 0);
pr_stack(mem, adrent(mem, VS));
restore(mem);
pr_mtab(mem, 0);
pr_stack(mem, adrent(mem, VS));
return 0;
}
#endif
506(1)10:47 PM:xpost3 0> cat ar.h ar.c
object consarr(mfile *mem, unsigned sz);
void arrput(mfile *mem, object a, integer i, object o);
object arrget(mfile *mem, object a, integer i);
object arrgetinterval(object a, integer s, integer n);
#include "m.h"
#include "ob.h"
#include "s.h"
#include "gc.h"
#include "v.h"
object consarr(mfile *mem, unsigned sz) {
//unsigned ent = mtalloc(mem, 0, sz * sizeof(object));
unsigned ent = gballoc(mem, sz * sizeof(object));
mtab *tab;
unsigned rent = ent;
findtabent(mem, &tab, &rent);
unsigned cnt = count(mem, adrent(mem, VS));
tab->tab[rent].mark = ( (0 << MARKO) & (0 << RFCTO) &
(cnt << LLEVO) & (cnt << TLEVO) );
return (object){ .comp_.tag = arraytype, .comp_.sz =
sz, .comp_.ent = ent, .comp_.off = 0};
}
void arrput(mfile *mem, object a, integer i, object o) {
if (!stashed(mem, a.comp_.ent)) stash(mem, a.comp_.ent);
put(mem, a.comp_.ent, a.comp_.off + i, sizeof(object), &o);
}
object arrget(mfile *mem, object a, integer i) {
object o;
get(mem, a.comp_.ent, a.comp_.off + i, sizeof(object), &o);
return o;
}
object arrgetinterval(object a, integer s, integer n) {
a.comp_.off += s;
a.comp_.sz = n;
return a;
}
#ifdef TESTMODULE
#include <stdio.h>
mfile mem;
int main(void) {
initmem(&mem);
(void)initmtab(&mem);
initfree(&mem);
initsave(&mem);
printf("allocating array occupying %zu bytes\n",
5*sizeof(object));
object a = consarr(&mem, 5);
printf("the memory table:\n");
pr_mtab(&mem, 0);
printf("test array by filling\n");
int i;
for (i=0; i < 5; i++) {
printf("%d: %d\n", i, i+1);
arrput(&mem, a, i, (object){ .tag = integertype, .int_.val = i
+1 });
}
printf("and accessing.\n");
for (i=0; i < 5; i++) {
object t;
t = arrget(&mem, a, i);
printf("%d: %d\n", i, t.int_.val);
}
printf("the memory table:\n");
pr_mtab(&mem, 0);
return 0;
}
#endif
507(1)10:48 PM:xpost3 0> make test-s
s
test stack by reversing a sequence
x = 3840, y = 12, z = 2
x = 2, y = 12, z = 3840
508(1)10:48 PM:xpost3 0> make test-v
v
33
nexttab: 0 0000
nextent: 3 0003
0: 128 0080 [4] _ 0 0 0
00 00 00 00
1: 132 0084 [0] _ 0 0 0
2: 220 00dc [16] _ 0 0 0
03 00 00 00 21 00 00 00 03 00 00 00 42 00 00 00
{save, 0, 236}
nexttab: 0 0000
nextent: 4 0004
0: 128 0080 [4] _ 0 0 0
00 00 00 00
1: 132 0084 [0] _ 0 0 0
2: 220 00dc [16] _ 0 0 0
03 00 00 00 4d 00 00 00 03 00 00 00 42 00 00 00
3: 324 0144 [16] _ 0 0 0
03 00 00 00 21 00 00 00 03 00 00 00 42 00 00 00
{save, 0, 236}
nexttab: 0 0000
nextent: 5 0005
0: 128 0080 [4] _ 0 0 0
00 00 00 00
1: 132 0084 [0] _ 0 0 0
2: 324 0144 [16] _ 0 0 0
03 00 00 00 21 00 00 00 03 00 00 00 42 00 00 00
3: 220 00dc [16] _ 0 0 0
03 00 00 00 4d 00 00 00 03 00 00 00 42 00 00 00
4: 236 00ec [88] _ 0 0 0
00 00 00 00 00 00 00 00 02 00 00 00 03 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
509(1)10:48 PM:xpost3 0> make test-ar
ar
allocating array occupying 40 bytes
the memory table:
nexttab: 0 0000
nextent: 3 0003
0: 128 0080 [4] _ 0 0 0
00 00 00 00
1: 132 0084 [0] _ 0 0 0
2: 220 00dc [40] _ 0 0 0
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
test array by filling
0: 1
1: 2
2: 3
3: 4
4: 5
and accessing.
0: 1
1: 2
2: 3
3: 4
4: 5
the memory table:
nexttab: 0 0000
nextent: 3 0003
0: 128 0080 [4] _ 0 0 0
00 00 00 00
1: 132 0084 [0] _ 0 0 0
2: 220 00dc [40] _ 0 0 0
00 00 00 00 01 00 00 00 00 00 00 00 02 00 00 00 00 00 00 00 03 00 00
00 00 00 00 00 04 00 00 00 00 00 00 00 05 00 00 00
510(1)10:48 PM:xpost3 0>
luser- -droog
luser- -droog wrote:
[...]
>
> In consarr, you also see the packing of 4 fields into the mark
> field of the address table. This is so it can hold a mark, a reference
> count, the "low level" (save level at which object was created),
> and the "top level" (highest level for which a saverec exists).
> The reference count isn't currently used. This packing uses these
> symbols from m.h for bitmasks and offsets:
>
> /* fields in mtab.tab[].mark */
> enum {
> MARKM = 0xFF000000,
> MARKO = 24,
> RFCTM = 0x00FF0000,
> RFCTO = 16,
> LLEVM = 0x0000FF00,
> LLEVO = 8,
> TLEVM = 0x000000FF,
> TLEVO = 0,
> };
>
> I know I don't need a whole byte for the mark, but it makes a nice
> symmetry.
>
[...]
>
> object consarr(mfile *mem, unsigned sz) {
> //unsigned ent = mtalloc(mem, 0, sz * sizeof(object));
> unsigned ent = gballoc(mem, sz * sizeof(object));
> mtab *tab;
> unsigned rent = ent;
> findtabent(mem, &tab, &rent);
> unsigned cnt = count(mem, adrent(mem, VS));
> tab->tab[rent].mark = ( (0 << MARKO) & (0 << RFCTO) &
> (cnt << LLEVO) & (cnt << TLEVO) );
Oops! should be:
tab->tab[rent].mark = ( (0 << MARKO) | (0 << RFCTO) |
(cnt << LLEVO) | (cnt << TLEVO) );