memory.safe.c
Go to the documentation of this file.
1 /****************************************************************/
2 /* memory.c: memory manager for eulisp */
3 /* Copyright(c) Toshihiro MATSUI
4 /* Electrotechnical Laboratory,1986.
5 /****************************************************************/
6 
7 #if vxworks
8 #include <sys/types.h>
9 #else
10 #include <sys/types.h>
11 #include <sys/times.h>
12 #endif
13 
14 #include "eus.h"
15 #include <synch.h>
16 #include <thread.h>
17 
18 #define nextbuddy(p) ((bpointer)((int)p+(buddy[p->h.bix].size<<2)))
19 #define marked(p) (p->h.mark)
20 #define markon(p) p->h.mark=1
21 #define markoff(p) p->h.mark=0
22 
23 extern _end();
24 
25 char *maxmemory=(char *)0x100000;
26 long freeheap=0,totalheap=0; /*size of heap left and allocated*/
28 /* timers */
30 long alloccount[MAXBUDDY];
31 
32 mutex_t alloc_lock;
33 
35 register int k;
36 { register int s;
37  register struct chunk *cp;
38  if (k<DEFAULTCHUNKINDEX) k=DEFAULTCHUNKINDEX;
39  if (QDEBUG && debug) fprintf(stderr,";; newchunk: k=%d\n",k);
40  s=buddy[k].size;
41  cp=(struct chunk *)(malloc((s+2)*sizeof(pointer)+3) & ~3);
42  maxmemory=(char *)sbrk(0);
43  if (cp==NULL) return(ERR); /*can't allocate new memory*/
44  cp->nextchunk=chunklist; /*link to chunk list*/
45  chunklist=cp;
46  cp->chunkbix=k;
47  cp->rootcell.h.mark=0;
48  cp->rootcell.h.b=1; /*initial buddy marks*/
49  cp->rootcell.h.m=0;
50  cp->rootcell.h.bix=k;
51  cp->rootcell.b.nextbcell=0;
52  buddy[k].bp= &cp->rootcell;
53  totalheap += s; freeheap += s;
54  return(k);
55  }
56 
57 static void splitheap(k) /*heart of the allocator*/
58 register int k;
59 { register bpointer b1,b2,bnext;
60  b1= buddy[k].bp; /*root buddy pointer*/
61  bnext=b1->b.nextbcell;
62  buddy[k].bp= bnext; /*remove first element*/
63  b2= (bpointer)((long)b1+buddy[k-1].size*sizeof(pointer));
64  if (k==2) { /*b1 and b2 are of the same size*/
65  b1->b.nextbcell=b2;
66  b2->b.nextbcell=buddy[k-1].bp;
67  buddy[k-1].bp=b1;
68  b2->h.bix= 1;}
69  else {
70  b1->b.nextbcell= buddy[k-1].bp;
71  buddy[k-1].bp=b1;
72  b2->b.nextbcell=buddy[k-2].bp;
73  buddy[k-2].bp=b2;
74  b2->h.bix= k-2;}
75  b2->h.m=b1->h.m;
76  b1->h.m=b1->h.b;
77  b1->h.b=0; b1->h.bix= k-1; b2->h.b=1;
78  b2->h.mark=b2->h.smark=b2->h.pmark=0;}
79 
80 pointer halloc(req,e,cid)
81 register int req; /*index to buddy: must be greater than 0*/
82 int e; /*element type*/
83 int cid; /*class id*/
84 { register int k=req;
85  register struct buddybase *bbreq= &buddy[req];
86  register bpointer b;
87  register pointer p;
88  numunion nu;
89 
90  mutex_lock(&alloc_lock);
91  while (buddy[k].bp==0) k++; /*find blocks of adequate size*/
92  if (k>=MAXBUDDY) { /*no enough room*/
93  if (bbreq->size<totalheap/8) { /*relatively small cell is requested;*/
94  gc(); /* then try garbage collection*/
95  while (freeheap<(totalheap*min(5.0,fltval(spevalof(GCMARGIN)))))
96  newchunk(req); /*still not enough space*/
97  for (k=req; buddy[k].bp==0; ) k++;}
98  if (k>=MAXBUDDY) {
99  k=newchunk(req);
100  if (k==ERR) { mutex_unlock(&alloc_lock); error(E_ALLOCATION);}}}
101  while (req<k) { splitheap(k--); if (k>req) k--;}
102  b=bbreq->bp;
103  b->h.elmtype=e;
104  b->h.cix=cid;
105  bbreq->bp=b->b.nextbcell;
106  freeheap -= bbreq->size;
107  alloccount[k]++;
108  p=makepointer(b);
110  mutex_unlock(&alloc_lock);
111  return(p);}
112 
113 pointer alloc(s,e,cid,nils) /*allocate heap of 's' longwords*/
114 register int s,nils;
115 int e,cid;
116 { register int i=1,ss;
117  register cell *c;
118  register pointer *v;
119  ss=max(3,s+1); /*one more word for the allocation information*/
120  while (buddy[i].size<ss) i++;
121  if (i>=MAXBUDDY) return(NULL);
122  c=halloc(i,e,cid);
123  i=buddy[i].size-1;
124  v=c->c.obj.iv;
125  while (nils<s) v[nils++]=NIL; /*fill NILs in user's slots*/
126  while (s<i) v[s++]=NULL; /*fill NULLs in buddy-cells extra slots*/
127  return(c);}
128 
129 /****************************************************************/
130 /* gc: garbage collector
131 /****************************************************************/
132 
134 
136 register pointer p;
137 { register int s;
138  register bpointer bp;
139 
140  if ((int)p<(int)_end || (pointer)0x20000000<p) return(NULL);
141 markagain:
142  bp=bpointerof(p);
143  if (marked(bp)) return; /*already marked*/
144  markon(bp); /*mark it first to avoid endless marking*/
145  if (pisclosure(p)) return; /*avoid marking contents of closure*/
146  if (bp->h.elmtype==ELM_FIXED) { /*contents are all pointers*/
147  if (bp->h.cix==conscp.cix) { /*save stack when cons*/
148  p=bp->b.c[0];
149  if ((int)p>(int)_end && (int)p<0x20000000 && ispointer(p)) mark(p);
150  p=bp->b.c[1];
151  if ((int)p>(int)_end && (int)p<0x20000000 && ispointer(p)) goto markagain;
152  }
153  else {
154  s=buddy[bp->h.bix].size-1;
155  while (s>0) {
156  p=bp->b.c[--s];
157  if (ispointer(p)) mark(p);}}}
158  else if (bp->h.elmtype==ELM_POINTER) { /*varing number of pointers*/
159  s=buddy[bp->h.bix].size-1;
160  while (--s>0) {
161  p=bp->b.c[s];
162  if (ispointer(p)) mark(p);}
163  }
164  }
165 
167 { register pointer *p,*spsave;
168  register int i,j;
169  register context *ctx;
170  markctx=euscontexts[thr_self()];
171  mark(sysobj); /*mark internally reachable objects*/
172  mark(pkglist); /*mark all packages*/
173  for (i=0; i<MAXTHREAD; i++) {
174  /*mark everything reachable from stacks in euscontexts*/
175  if (ctx=euscontexts[i]) {
176  markctx=ctx;
177  for (p=ctx->stack; p<ctx->vsp; p++)
178  if (ispointer(*p) && ((ctx->stack>(pointer *)*p)
179  || ((pointer *)*p>ctx->stacklimit))) { mark(*p); } ;
180  mark(ctx->lastalloc);}}
181  for (i=0; i<MAXCLASS; i++) {
182  markctx=euscontexts[thr_self()];
183  if (ispointer(classtab[i].def)) mark(classtab[i].def); }
184  }
185 
187 register bpointer p;
188 { register int rbix,stat;
189  register pointer s;
190  s=makepointer(p);
191  if (pisfilestream(s)) {
192  if (!isint(s->c.fstream.fname) && s->c.fstream.direction!=NIL) {
193  if (s->c.fstream.fd==makeint(0) || s->c.fstream.fd==makeint(1)) {
194  fprintf(stderr,";; gc! bogus stream at %x fd=%d\n",
195  (int)s,intval(s->c.fstream.fd));}
196  else if ((closestream(s)==0) && debug)
197  fprintf(stderr,";; gc: dangling stream(address=%x fd=%d) is closed\n",
198  (int)s,intval(s->c.fstream.fd)); } }
199  p->h.cix= -1;
200  rbix=p->h.bix;
201  p->b.nextbcell=buddy[rbix].bp;
202  buddy[rbix].bp=p;
203  freeheap+=buddy[rbix].size;}
204 
205 static bpointer mergecell(p,cbix)
206 register bpointer p;
207 int cbix;
208 /*the cell pointed by 'p' must not be marked*/
209 /*mergecell kindly returns next uncollectable cell address*/
210 { register bpointer np,p2;
211  np=nextbuddy(p);
212  while (p->h.b==0 && (int)p->h.bix<cbix) {
213  if (marked(np)) return(np);
214  p2=mergecell(np,cbix); /*merge neighbor cell*/
215  if (np->h.b==1) { /*can be merged*/
216  p->h.b=p->h.m; /*merge them into bigger cell*/
217  p->h.m=np->h.m;
218  p->h.bix++;
219  np=p2;}
220  else {
221  reclaim(np);
222  return(p2);}}
223  return(np);}
224 
225 static void sweep(cp)
226 struct chunk *cp;
227 { register int s,gcmerge;
228  register bpointer p,np,tail;
229  numunion nu;
230 
231  gcmerge=totalheap * min(1.0,fltval(spevalof(GCMARGIN)))
232  * max(0.1,fltval(spevalof(GCMERGE)));
233  s=buddy[cp->chunkbix].size;
234  p= &cp->rootcell;
235  tail=(bpointer)((int)p+(s<<2));
236  while (p<tail) {
237  if (marked(p)) { markoff(p); p=nextbuddy(p);} /*don't collect*/
238  else if (gcmerge<freeheap) { /* no merge */
239  np=nextbuddy(p);
240  reclaim(p);
241  p=np;}
242  else {
243  np=mergecell(p,cp->chunkbix); /*update free buddy list*/
244  reclaim(p);
245  p=np;} }
246  }
247 
248 void sweepall()
249 {
250  register struct chunk *chp;
251  register int i;
252  for (i=0; i<MAXBUDDY-1; i++) buddy[i].bp=0; /*purge buddies*/
253  freeheap=0;
254  for (chp=chunklist; chp!=0; chp=chp->nextchunk) sweep(chp);
255  }
256 
257 #if vxworks
258 gc()
259 { if (debug) fprintf(stderr,"\n;; gc:");
260  breakck;
261  gccount++;
262  markall();
263  sweepall();
264  if (debug) {
265  fprintf(stderr," free/total=%d/%d stack=%d ",
266  freeheap,totalheap,markctx->vsp-markctx->stack);
267  }
268  breakck;
269  }
270 #else
271 gc()
272 { struct tms tbuf1,tbuf2,tbuf3;
273 
274  if (debug) fprintf(stderr,"\n;; gc:");
275  breakck;
276  mutex_lock(&mark_lock);
277  gccount++;
278  times(&tbuf1);
279  markall();
280  times(&tbuf2);
281  marktime+=(tbuf2.tms_utime-tbuf1.tms_utime);
282  sweepall();
283  times(&tbuf3);
284  sweeptime+=(tbuf3.tms_utime-tbuf2.tms_utime);
285  if (debug) {
286  fprintf(stderr," thread=%d free/total=%d/%d stack=%d ",
287  thr_self(),
288  freeheap,totalheap,markctx->vsp - markctx->stack);
289  fprintf(stderr," mark=%d sweep=%d\n", marktime,sweeptime);}
290  mutex_unlock(&mark_lock);
291  breakck;
292 }
293 #endif
294 
context * euscontexts[MAXTHREAD]
Definition: eus.c:105
pointer GCMARGIN
Definition: eus.c:173
unsigned pmark
Definition: eus.h:181
pointer * stack
Definition: eus.h:525
pointer alloc(int s, int e, int cid, int nils)
Definition: memory.safe.c:113
unsigned elmtype
Definition: eus.h:182
markall()
Definition: memory.safe.c:166
char * maxmemory
Definition: memory.safe.c:25
struct chunk * chunklist
Definition: memory.safe.c:27
pointer * stacklimit
Definition: eus.h:525
long marktime
Definition: memory.safe.c:29
static int gcmerge
Definition: collector.c:45
#define makeint(v)
Definition: sfttest.c:2
struct cell * pointer
Definition: eus.h:165
long gccount
Definition: memory.safe.c:29
static void sweep(struct chunk *cp)
Definition: memory.safe.c:225
Definition: eus.h:524
struct filestream fstream
Definition: eus.h:406
pointer GCMERGE
Definition: eus.c:173
_end()
long sweeptime
Definition: memory.safe.c:29
mark(pointer p)
Definition: memory.safe.c:135
pointer * vsp
Definition: eus.h:525
int closestream(pointer)
Definition: eusstream.c:53
struct bcell * bpointer
Definition: eus.h:445
bpointer bp
Definition: eus.h:565
pointer QDEBUG
Definition: eus.c:123
cixpair conscp
Definition: eus.c:70
#define intval(p)
Definition: sfttest.c:1
mutex_t alloc_lock
Definition: memory.safe.c:32
Definition: eus.h:447
context * markctx
Definition: memory.safe.c:133
#define min(x, y)
Definition: rmflags.c:17
bpointer bp
Definition: eus.old.h:398
mutex_t mark_lock
Definition: mthread.c:25
union cell::cellunion c
pointer iv[2]
Definition: eus.h:321
pointer lastalloc
Definition: eus.h:536
void sweepall()
Definition: memory.safe.c:248
Definition: eus.h:428
pointer halloc(int req, int e, int cid)
Definition: memory.safe.c:80
unsigned smark
Definition: eus.h:180
reclaim(bpointer p)
Definition: memory.safe.c:186
Definition: eus.h:381
pointer fname
Definition: eus.h:287
struct cellheader h
Definition: eus.h:440
int chunkbix
Definition: eus.h:449
long alloccount[MAXBUDDY]
Definition: memory.safe.c:30
short s
Definition: structsize.c:2
struct bcell * nextbcell
Definition: eus.h:442
int size
Definition: eus.old.h:397
pointer error(enum errorcode ec,...) pointer error(va_alist) va_dcl
Definition: eus.c:297
union bcell::@12 b
newchunk(int k)
Definition: memory.safe.c:34
struct bcell rootcell
Definition: eus.h:450
unsigned mark
Definition: eus.h:177
static int bp
Definition: helpsub.c:22
struct buddyfree buddy[MAXBUDDY+1]
Definition: eus.c:46
float fltval()
tail(char *cp)
Definition: eustags.c:1181
unsigned bix
Definition: eus.h:185
short cix
Definition: eus.h:190
static void splitheap(int k)
Definition: memory.safe.c:57
#define max(I1, I2)
Definition: eustags.c:134
#define NULL
Definition: transargv.c:8
struct object obj
Definition: eus.h:417
pointer fd
Definition: eus.h:286
GLfloat v[8][3]
Definition: cube.c:21
gc()
Definition: memory.safe.c:258
unsigned b
Definition: eus.h:178
pointer direction
Definition: eus.h:282
pointer sysobj
Definition: eus.c:54
Definition: eus.h:439
long totalheap
Definition: memory.safe.c:26
unsigned int thr_self()
Definition: eus.c:25
long freeheap
Definition: memory.safe.c:26
struct chunk * nextchunk
Definition: eus.h:448
short cix
Definition: eus.h:453
unsigned m
Definition: eus.h:179
struct class_desc classtab[MAXCLASS]
Definition: eus.c:138
pointer pkglist
Definition: eus.c:109
struct cell * c[2]
Definition: eus.h:443
pointer NIL
Definition: eus.c:110
static bpointer mergecell(bpointer p, int cbix)
Definition: memory.safe.c:205


euslisp
Author(s): Toshihiro Matsui
autogenerated on Mon Feb 28 2022 22:18:27