1 /***********************************************************************
2 * *
3 * This software is part of the ast package *
4 * Copyright (c) 1985-2012 AT&T Intellectual Property *
5 * and is licensed under the *
6 * Eclipse Public License, Version 1.0 *
7 * by AT&T Intellectual Property *
8 * *
9 * A copy of the License is available at *
10 * http://www.eclipse.org/org/documents/epl-v10.html *
11 * (with md5 checksum b35adb5213ca9657e911e9befb180842) *
12 * *
13 * Information and Software Systems Research *
14 * AT&T Research *
15 * Florham Park NJ *
16 * *
17 * Glenn Fowler <gsf@research.att.com> *
18 * David Korn <dgk@research.att.com> *
19 * Phong Vo <kpv@research.att.com> *
20 * *
21 ***********************************************************************/
22 #pragma prototyped
23 /*
24 * Routines to implement a stack-like storage library
25 *
26 * A stack consists of a link list of variable size frames
27 * The beginning of each frame is initialized with a frame structure
28 * that contains a pointer to the previous frame and a pointer to the
29 * end of the current frame.
30 *
31 * This is a rewrite of the stk library that uses sfio
32 *
33 * David Korn
34 * AT&T Research
35 * dgk@research.att.com
36 *
37 */
38
39 #include <sfio_t.h>
40 #include <ast.h>
41 #include <align.h>
42 #include <stk.h>
43
44 /*
45 * A stack is a header and a linked list of frames
46 * The first frame has structure
47 * Sfio_t
48 * Sfdisc_t
49 * struct stk
50 * Frames have structure
51 * struct frame
52 * data
53 */
54
55 #define STK_ALIGN ALIGN_BOUND
56 #define STK_FSIZE (1024*sizeof(char*))
57 #define STK_HDRSIZE (sizeof(Sfio_t)+sizeof(Sfdisc_t))
58
59 typedef char* (*_stk_overflow_)(int);
60
61 static int stkexcept(Sfio_t*,int,void*,Sfdisc_t*);
62 static Sfdisc_t stkdisc = { 0, 0, 0, stkexcept };
63
64 Sfio_t _Stak_data = SFNEW((char*)0,0,-1,SF_STATIC|SF_WRITE|SF_STRING,&stkdisc,0);
65
66 __EXTERN__(Sfio_t, _Stak_data);
67
68 struct frame
69 {
70 char *prev; /* address of previous frame */
71 char *end; /* address of end this frame */
72 char **aliases; /* address aliases */
73 int nalias; /* number of aliases */
74 };
75
76 struct stk
77 {
78 _stk_overflow_ stkoverflow; /* called when malloc fails */
79 short stkref; /* reference count; */
80 short stkflags; /* stack attributes */
81 char *stkbase; /* beginning of current stack frame */
82 char *stkend; /* end of current stack frame */
83 };
84
85 static size_t init; /* 1 when initialized */
86 static struct stk *stkcur; /* pointer to current stk */
87 static char *stkgrow(Sfio_t*, size_t);
88
89 #define stream2stk(stream) ((stream)==stkstd? stkcur:\
90 ((struct stk*)(((char*)(stream))+STK_HDRSIZE)))
91 #define stk2stream(sp) ((Sfio_t*)(((char*)(sp))-STK_HDRSIZE))
92 #define stkleft(stream) ((stream)->_endb-(stream)->_data)
93
94
95 #ifdef STKSTATS
96 static struct
97 {
98 int create;
99 int delete;
100 int install;
101 int alloc;
102 int copy;
103 int puts;
104 int seek;
105 int set;
106 int grow;
107 int addsize;
108 int delsize;
109 int movsize;
110 } _stkstats;
111 # define increment(x) (_stkstats.x++)
112 # define count(x,n) (_stkstats.x += (n))
113 #else
114 # define increment(x)
115 # define count(x,n)
116 #endif /* STKSTATS */
117
118 static const char Omsg[] = "malloc failed while growing stack\n";
119
120 /*
121 * default overflow exception
122 */
overflow(int n)123 static char *overflow(int n)
124 {
125 NoP(n);
126 write(2,Omsg, sizeof(Omsg)-1);
127 exit(2);
128 /* NOTREACHED */
129 return(0);
130 }
131
132 /*
133 * initialize stkstd, sfio operations may have already occcured
134 */
stkinit(size_t size)135 static void stkinit(size_t size)
136 {
137 register Sfio_t *sp;
138 init = size;
139 sp = stkopen(0);
140 init = 1;
141 stkinstall(sp,overflow);
142 }
143
stkexcept(register Sfio_t * stream,int type,void * val,Sfdisc_t * dp)144 static int stkexcept(register Sfio_t *stream, int type, void* val, Sfdisc_t* dp)
145 {
146 NoP(dp);
147 NoP(val);
148 switch(type)
149 {
150 case SF_CLOSING:
151 {
152 register struct stk *sp = stream2stk(stream);
153 register char *cp = sp->stkbase;
154 register struct frame *fp;
155 if(--sp->stkref<=0)
156 {
157 increment(delete);
158 if(stream==stkstd)
159 stkset(stream,(char*)0,0);
160 else
161 {
162 while(1)
163 {
164 fp = (struct frame*)cp;
165 if(fp->prev)
166 {
167 cp = fp->prev;
168 free(fp);
169 }
170 else
171 {
172 free(fp);
173 break;
174 }
175 }
176 }
177 }
178 stream->_data = stream->_next = 0;
179 }
180 return(0);
181 case SF_FINAL:
182 free(stream);
183 return(1);
184 case SF_DPOP:
185 return(-1);
186 case SF_WRITE:
187 case SF_SEEK:
188 {
189 long size = sfvalue(stream);
190 if(init)
191 {
192 Sfio_t *old = 0;
193 if(stream!=stkstd)
194 old = stkinstall(stream,NiL);
195 if(!stkgrow(stkstd,size-(stkstd->_endb-stkstd->_data)))
196 return(-1);
197 if(old)
198 stkinstall(old,NiL);
199 }
200 else
201 stkinit(size);
202 }
203 return(1);
204 case SF_NEW:
205 return(-1);
206 }
207 return(0);
208 }
209
210 /*
211 * create a stack
212 */
stkopen(int flags)213 Sfio_t *stkopen(int flags)
214 {
215 register size_t bsize;
216 register Sfio_t *stream;
217 register struct stk *sp;
218 register struct frame *fp;
219 register Sfdisc_t *dp;
220 register char *cp;
221 if(!(stream=newof((char*)0,Sfio_t, 1, sizeof(*dp)+sizeof(*sp))))
222 return(0);
223 increment(create);
224 count(addsize,sizeof(*stream)+sizeof(*dp)+sizeof(*sp));
225 dp = (Sfdisc_t*)(stream+1);
226 dp->exceptf = stkexcept;
227 sp = (struct stk*)(dp+1);
228 sp->stkref = 1;
229 sp->stkflags = (flags&STK_SMALL);
230 if(flags&STK_NULL) sp->stkoverflow = 0;
231 else sp->stkoverflow = stkcur?stkcur->stkoverflow:overflow;
232 bsize = init+sizeof(struct frame);
233 #ifndef USE_REALLOC
234 if(flags&STK_SMALL)
235 bsize = roundof(bsize,STK_FSIZE/16);
236 else
237 #endif /* USE_REALLOC */
238 bsize = roundof(bsize,STK_FSIZE);
239 bsize -= sizeof(struct frame);
240 if(!(fp=newof((char*)0,struct frame, 1,bsize)))
241 {
242 free(stream);
243 return(0);
244 }
245 count(addsize,sizeof(*fp)+bsize);
246 cp = (char*)(fp+1);
247 sp->stkbase = (char*)fp;
248 fp->prev = 0;
249 fp->nalias = 0;
250 fp->aliases = 0;
251 fp->end = sp->stkend = cp+bsize;
252 if(!sfnew(stream,cp,bsize,-1,SF_STRING|SF_WRITE|SF_STATIC|SF_EOF))
253 return((Sfio_t*)0);
254 sfdisc(stream,dp);
255 return(stream);
256 }
257
258 /*
259 * return a pointer to the current stack
260 * if <stream> is not null, it becomes the new current stack
261 * <oflow> becomes the new overflow function
262 */
stkinstall(Sfio_t * stream,_stk_overflow_ oflow)263 Sfio_t *stkinstall(Sfio_t *stream, _stk_overflow_ oflow)
264 {
265 Sfio_t *old;
266 register struct stk *sp;
267 if(!init)
268 {
269 stkinit(1);
270 if(oflow)
271 stkcur->stkoverflow = oflow;
272 return((Sfio_t*)0);
273 }
274 increment(install);
275 old = stkcur?stk2stream(stkcur):0;
276 if(stream)
277 {
278 sp = stream2stk(stream);
279 while(sfstack(stkstd, SF_POPSTACK));
280 if(stream!=stkstd)
281 sfstack(stkstd,stream);
282 stkcur = sp;
283 #ifdef USE_REALLOC
284 /*** someday ***/
285 #endif /* USE_REALLOC */
286 }
287 else
288 sp = stkcur;
289 if(oflow)
290 sp->stkoverflow = oflow;
291 return(old);
292 }
293
294 /*
295 * increase the reference count on the given <stack>
296 */
stklink(register Sfio_t * stream)297 int stklink(register Sfio_t* stream)
298 {
299 register struct stk *sp = stream2stk(stream);
300 return(sp->stkref++);
301 }
302
303 /*
304 * terminate a stack and free up the space
305 * >0 returned if reference decremented but still > 0
306 * 0 returned on last close
307 * <0 returned on error
308 */
stkclose(Sfio_t * stream)309 int stkclose(Sfio_t* stream)
310 {
311 register struct stk *sp = stream2stk(stream);
312 if(sp->stkref>1)
313 {
314 sp->stkref--;
315 return(1);
316 }
317 return(sfclose(stream));
318 }
319
320 /*
321 * returns 1 if <loc> is on this stack
322 */
stkon(register Sfio_t * stream,register char * loc)323 int stkon(register Sfio_t * stream, register char* loc)
324 {
325 register struct stk *sp = stream2stk(stream);
326 register struct frame *fp;
327 for(fp=(struct frame*)sp->stkbase; fp; fp=(struct frame*)fp->prev)
328 if(loc>=((char*)(fp+1)) && loc< fp->end)
329 return(1);
330 return(0);
331 }
332 /*
333 * reset the bottom of the current stack back to <loc>
334 * if <loc> is null, then the stack is reset to the beginning
335 * if <loc> is not in this stack, the program dumps core
336 * otherwise, the top of the stack is set to stkbot+<offset>
337 */
stkset(register Sfio_t * stream,register char * loc,size_t offset)338 char *stkset(register Sfio_t * stream, register char* loc, size_t offset)
339 {
340 register struct stk *sp = stream2stk(stream);
341 register char *cp;
342 register struct frame *fp;
343 register int frames = 0;
344 int n;
345 if(!init)
346 stkinit(offset+1);
347 increment(set);
348 while(1)
349 {
350 fp = (struct frame*)sp->stkbase;
351 cp = sp->stkbase + roundof(sizeof(struct frame), STK_ALIGN);
352 n = fp->nalias;
353 while(n-->0)
354 {
355 if(loc==fp->aliases[n])
356 {
357 loc = cp;
358 break;
359 }
360 }
361 /* see whether <loc> is in current stack frame */
362 if(loc>=cp && loc<=sp->stkend)
363 {
364 if(frames)
365 sfsetbuf(stream,cp,sp->stkend-cp);
366 stream->_data = (unsigned char*)(cp + roundof(loc-cp,STK_ALIGN));
367 stream->_next = (unsigned char*)loc+offset;
368 goto found;
369 }
370 if(fp->prev)
371 {
372 sp->stkbase = fp->prev;
373 sp->stkend = ((struct frame*)(fp->prev))->end;
374 free((void*)fp);
375 }
376 else
377 break;
378 frames++;
379 }
380 /* not found: produce a useful stack trace now instead of a useless one later */
381 if(loc)
382 abort();
383 /* set stack back to the beginning */
384 cp = (char*)(fp+1);
385 if(frames)
386 sfsetbuf(stream,cp,sp->stkend-cp);
387 else
388 stream->_data = stream->_next = (unsigned char*)cp;
389 found:
390 return((char*)stream->_data);
391 }
392
393 /*
394 * allocate <n> bytes on the current stack
395 */
stkalloc(register Sfio_t * stream,register size_t n)396 char *stkalloc(register Sfio_t *stream, register size_t n)
397 {
398 register unsigned char *old;
399 if(!init)
400 stkinit(n);
401 increment(alloc);
402 n = roundof(n,STK_ALIGN);
403 if(stkleft(stream) <= (int)n && !stkgrow(stream,n))
404 return(0);
405 old = stream->_data;
406 stream->_data = stream->_next = old+n;
407 return((char*)old);
408 }
409
410 /*
411 * begin a new stack word of at least <n> bytes
412 */
_stkseek(register Sfio_t * stream,register ssize_t n)413 char *_stkseek(register Sfio_t *stream, register ssize_t n)
414 {
415 if(!init)
416 stkinit(n);
417 increment(seek);
418 if(stkleft(stream) <= n && !stkgrow(stream,n))
419 return(0);
420 stream->_next = stream->_data+n;
421 return((char*)stream->_data);
422 }
423
424 /*
425 * advance the stack to the current top
426 * if extra is non-zero, first add a extra bytes and zero the first
427 */
stkfreeze(register Sfio_t * stream,register size_t extra)428 char *stkfreeze(register Sfio_t *stream, register size_t extra)
429 {
430 register unsigned char *old, *top;
431 if(!init)
432 stkinit(extra);
433 old = stream->_data;
434 top = stream->_next;
435 if(extra)
436 {
437 if(extra > (stream->_endb-stream->_next))
438 {
439 if (!(top = (unsigned char*)stkgrow(stream,extra)))
440 return(0);
441 old = stream->_data;
442 }
443 *top = 0;
444 top += extra;
445 }
446 stream->_next = stream->_data += roundof(top-old,STK_ALIGN);
447 return((char*)old);
448 }
449
450 /*
451 * copy string <str> onto the stack as a new stack word
452 */
stkcopy(Sfio_t * stream,const char * str)453 char *stkcopy(Sfio_t *stream, const char* str)
454 {
455 register unsigned char *cp = (unsigned char*)str;
456 register size_t n;
457 register int off=stktell(stream);
458 char buff[40], *tp=buff;
459 if(off)
460 {
461 if(off > sizeof(buff))
462 {
463 if(!(tp = malloc(off)))
464 {
465 struct stk *sp = stream2stk(stream);
466 if(!sp->stkoverflow || !(tp = (*sp->stkoverflow)(off)))
467 return(0);
468 }
469 }
470 memcpy(tp, stream->_data, off);
471 }
472 while(*cp++);
473 n = roundof(cp-(unsigned char*)str,STK_ALIGN);
474 if(!init)
475 stkinit(n);
476 increment(copy);
477 if(stkleft(stream) <= n && !stkgrow(stream,n))
478 cp = 0;
479 else
480 {
481 strcpy((char*)(cp=stream->_data),str);
482 stream->_data = stream->_next = cp+n;
483 if(off)
484 {
485 _stkseek(stream,off);
486 memcpy(stream->_data, tp, off);
487 }
488 }
489 if(tp!=buff)
490 free((void*)tp);
491 return((char*)cp);
492 }
493
494 /*
495 * add a new stack frame of size >= <n> to the current stack.
496 * if <n> > 0, copy the bytes from stkbot to stktop to the new stack
497 * if <n> is zero, then copy the remainder of the stack frame from stkbot
498 * to the end is copied into the new stack frame
499 */
500
stkgrow(register Sfio_t * stream,size_t size)501 static char *stkgrow(register Sfio_t *stream, size_t size)
502 {
503 register size_t n = size;
504 register struct stk *sp = stream2stk(stream);
505 register struct frame *fp= (struct frame*)sp->stkbase;
506 register char *cp, *dp=0;
507 register size_t m = stktell(stream);
508 size_t endoff;
509 char *end=0, *oldbase=0;
510 int nn=0,add=1;
511 n += (m + sizeof(struct frame)+1);
512 if(sp->stkflags&STK_SMALL)
513 #ifndef USE_REALLOC
514 n = roundof(n,STK_FSIZE/16);
515 else
516 #endif /* !USE_REALLOC */
517 n = roundof(n,STK_FSIZE);
518 /* see whether current frame can be extended */
519 if(stkptr(stream,0)==sp->stkbase+sizeof(struct frame))
520 {
521 nn = fp->nalias+1;
522 dp=sp->stkbase;
523 sp->stkbase = ((struct frame*)dp)->prev;
524 end = fp->end;
525 oldbase = dp;
526 }
527 endoff = end - dp;
528 cp = newof(dp, char, n, nn*sizeof(char*));
529 if(!cp && (!sp->stkoverflow || !(cp = (*sp->stkoverflow)(n))))
530 return(0);
531 increment(grow);
532 count(addsize,n - (dp?m:0));
533 if(dp==cp)
534 {
535 nn--;
536 add = 0;
537 }
538 else if(dp)
539 {
540 dp = cp;
541 end = dp + endoff;
542 }
543 fp = (struct frame*)cp;
544 fp->prev = sp->stkbase;
545 sp->stkbase = cp;
546 sp->stkend = fp->end = cp+n;
547 cp = (char*)(fp+1);
548 cp = sp->stkbase + roundof((cp-sp->stkbase),STK_ALIGN);
549 if(fp->nalias=nn)
550 {
551 fp->aliases = (char**)fp->end;
552 if(end && nn>add)
553 memmove(fp->aliases,end,(nn-add)*sizeof(char*));
554 if(add)
555 fp->aliases[nn-1] = oldbase + roundof(sizeof(struct frame),STK_ALIGN);
556 }
557 if(m && !dp)
558 {
559 memcpy(cp,(char*)stream->_data,m);
560 count(movsize,m);
561 }
562 sfsetbuf(stream,cp,sp->stkend-cp);
563 return((char*)(stream->_next = stream->_data+m));
564 }
565