xref: /illumos-gate/usr/src/contrib/ast/src/lib/libast/misc/stk.c (revision 3636ae5408a4c1fb68954277f99be72f62e3489e)
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