1/*	$OpenBSD: main.c,v 1.47 2011/09/07 11:33:25 otto Exp $	*/
2/*	$OpenBSD: tty.c,v 1.9 2006/03/14 22:08:01 deraadt Exp $	*/
3/*	$OpenBSD: io.c,v 1.22 2006/03/17 16:30:13 millert Exp $	*/
4/*	$OpenBSD: table.c,v 1.13 2009/01/17 22:06:44 millert Exp $	*/
5
6/*-
7 * Copyright (c) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
8 *	Thorsten Glaser <tg@mirbsd.org>
9 *
10 * Provided that these terms and disclaimer and all copyright notices
11 * are retained or reproduced in an accompanying document, permission
12 * is granted to deal in this work without restriction, including un-
13 * limited rights to use, publicly perform, distribute, sell, modify,
14 * merge, give away, or sublicence.
15 *
16 * This work is provided "AS IS" and WITHOUT WARRANTY of any kind, to
17 * the utmost extent permitted by applicable law, neither express nor
18 * implied; without malicious intent or gross negligence. In no event
19 * may a licensor, author or contributor be held liable for indirect,
20 * direct, other damage, loss, or other issues arising in any way out
21 * of dealing in the work, even if advised of the possibility of such
22 * damage or existence of a defect, except proven that it results out
23 * of said person's immediate fault when using the work as intended.
24 */
25
26#define EXTERN
27#include "sh.h"
28
29#if HAVE_LANGINFO_CODESET
30#include <langinfo.h>
31#endif
32#if HAVE_SETLOCALE_CTYPE
33#include <locale.h>
34#endif
35
36__RCSID("$MirOS: src/bin/mksh/main.c,v 1.200 2011/10/07 19:51:28 tg Exp $");
37
38extern char **environ;
39
40#ifndef MKSHRC_PATH
41#define MKSHRC_PATH	"~/.mkshrc"
42#endif
43
44#ifndef MKSH_DEFAULT_TMPDIR
45#define MKSH_DEFAULT_TMPDIR	"/tmp"
46#endif
47
48void chvt_reinit(void);
49static void reclaim(void);
50static void remove_temps(struct temp *);
51static mksh_uari_t rndsetup(void);
52#ifdef SIGWINCH
53static void x_sigwinch(int);
54#endif
55
56static const char initifs[] = "IFS= \t\n";
57
58static const char initsubs[] =
59    "${PS2=> } ${PS3=#? } ${PS4=+ } ${SECONDS=0} ${TMOUT=0}";
60
61static const char *initcoms[] = {
62	Ttypeset, "-r", initvsn, NULL,
63	Ttypeset, "-x", "HOME", "PATH", "RANDOM", "SHELL", NULL,
64	Ttypeset, "-i10", "SECONDS", "TMOUT", NULL,
65	Talias,
66	"integer=typeset -i",
67	Tlocal_typeset,
68	/* not "alias -t --": hash -r needs to work */
69	"hash=alias -t",
70	"type=whence -v",
71#if !defined(ANDROID) && !defined(MKSH_UNEMPLOYED)
72	/* not in Android for political reasons */
73	/* not in ARGE mksh due to no job control */
74	"stop=kill -STOP",
75	"suspend=kill -STOP $$",
76#endif
77	"autoload=typeset -fu",
78	"functions=typeset -f",
79	"history=fc -l",
80	"nameref=typeset -n",
81	"nohup=nohup ",
82	Tr_fc_e_dash,
83	"source=PATH=$PATH:. command .",
84	"login=exec login",
85	NULL,
86	 /* this is what AT&T ksh seems to track, with the addition of emacs */
87	Talias, "-tU",
88	"cat", "cc", "chmod", "cp", "date", "ed", "emacs", "grep", "ls",
89	"make", "mv", "pr", "rm", "sed", "sh", "vi", "who", NULL,
90	NULL
91};
92
93static const char *restr_com[] = {
94	Ttypeset, "-r", "PATH", "ENV", "SHELL", NULL
95};
96
97static int initio_done;
98
99/* top-level parsing and execution environment */
100static struct env env;
101struct env *e = &env;
102
103static mksh_uari_t
104rndsetup(void)
105{
106	register uint32_t h;
107	struct {
108		ALLOC_ITEM alloc_INT;
109		void *dataptr, *stkptr, *mallocptr;
110		sigjmp_buf jbuf;
111		struct timeval tv;
112		struct timezone tz;
113	} *bufptr;
114	char *cp;
115
116	cp = alloc(sizeof(*bufptr) - ALLOC_SIZE, APERM);
117#ifdef DEBUG
118	/* clear the allocated space, for valgrind */
119	memset(cp, 0, sizeof(*bufptr) - ALLOC_SIZE);
120#endif
121	/* undo what alloc() did to the malloc result address */
122	bufptr = (void *)(cp - ALLOC_SIZE);
123	/* PIE or something similar provides us with deltas here */
124	bufptr->dataptr = &rndsetupstate;
125	/* ASLR in at least Windows, Linux, some BSDs */
126	bufptr->stkptr = &bufptr;
127	/* randomised malloc in BSD (and possibly others) */
128	bufptr->mallocptr = bufptr;
129	/* glibc pointer guard */
130	sigsetjmp(bufptr->jbuf, 1);
131	/* introduce variation */
132	gettimeofday(&bufptr->tv, &bufptr->tz);
133
134	NZATInit(h);
135	/* variation through pid, ppid, and the works */
136	NZATUpdateMem(h, &rndsetupstate, sizeof(rndsetupstate));
137	/* some variation, some possibly entropy, depending on OE */
138	NZATUpdateMem(h, bufptr, sizeof(*bufptr));
139	NZAATFinish(h);
140
141	afree(cp, APERM);
142	return ((mksh_uari_t)h);
143}
144
145void
146chvt_reinit(void)
147{
148	kshpid = procpid = getpid();
149	ksheuid = geteuid();
150	kshpgrp = getpgrp();
151	kshppid = getppid();
152}
153
154static const char *empty_argv[] = {
155	"mksh", NULL
156};
157
158int
159main(int argc, const char *argv[])
160{
161	int argi, i;
162	Source *s = NULL;
163	struct block *l;
164	unsigned char restricted, errexit, utf_flag;
165	char *cp;
166	const char *ccp, **wp;
167	struct tbl *vp;
168	struct stat s_stdin;
169#if !defined(_PATH_DEFPATH) && defined(_CS_PATH)
170	ssize_t k;
171#endif
172
173	/* do things like getpgrp() et al. */
174	chvt_reinit();
175
176	/* make sure argv[] is sane */
177	if (!*argv) {
178		argv = empty_argv;
179		argc = 1;
180	}
181	kshname = argv[0];
182
183	/* initialise permanent Area */
184	ainit(&aperm);
185
186	/* set up base environment */
187	env.type = E_NONE;
188	ainit(&env.area);
189	/* set up global l->vars and l->funs */
190	newblock();
191
192	/* Do this first so output routines (eg, errorf, shellf) can work */
193	initio();
194
195	/* determine the basename (without '-' or path) of the executable */
196	ccp = kshname;
197	goto begin_parse_kshname;
198	while ((i = ccp[argi++])) {
199		if (i == '/') {
200			ccp += argi;
201 begin_parse_kshname:
202			argi = 0;
203			if (*ccp == '-')
204				++ccp;
205		}
206	}
207	if (!*ccp)
208		ccp = empty_argv[0];
209
210	/* define built-in commands and see if we were called as one */
211	ktinit(APERM, &builtins,
212	    /* currently 50 builtins -> 80% of 64 (2^6) */
213	    6);
214	for (i = 0; mkshbuiltins[i].name != NULL; i++)
215		if (!strcmp(ccp, builtin(mkshbuiltins[i].name,
216		    mkshbuiltins[i].func)))
217			Flag(FAS_BUILTIN) = 1;
218
219	if (!Flag(FAS_BUILTIN)) {
220		/* check for -T option early */
221		argi = parse_args(argv, OF_FIRSTTIME, NULL);
222		if (argi < 0)
223			return (1);
224
225#ifdef MKSH_BINSHREDUCED
226		/* set FSH if we're called as -sh or /bin/sh or so */
227		if (!strcmp(ccp, "sh"))
228			change_flag(FSH, OF_FIRSTTIME, 1);
229#endif
230	}
231
232	initvar();
233
234	initctypes();
235
236	inittraps();
237
238	coproc_init();
239
240	/* set up variable and command dictionaries */
241	ktinit(APERM, &taliases, 0);
242	ktinit(APERM, &aliases, 0);
243#ifndef MKSH_NOPWNAM
244	ktinit(APERM, &homedirs, 0);
245#endif
246
247	/* define shell keywords */
248	initkeywords();
249
250	init_histvec();
251
252#ifdef _PATH_DEFPATH
253	def_path = _PATH_DEFPATH;
254#else
255#ifdef _CS_PATH
256	if ((k = confstr(_CS_PATH, NULL, 0)) > 0 &&
257	    confstr(_CS_PATH, cp = alloc(k + 1, APERM), k + 1) == k + 1)
258		def_path = cp;
259	else
260#endif
261		/*
262		 * this is uniform across all OSes unless it
263		 * breaks somewhere; don't try to optimise,
264		 * e.g. add stuff for Interix or remove /usr
265		 * for HURD, because e.g. Debian GNU/HURD is
266		 * "keeping a regular /usr"; this is supposed
267		 * to be a sane 'basic' default PATH
268		 */
269		def_path = "/bin:/usr/bin:/sbin:/usr/sbin";
270#endif
271
272	/*
273	 * Set PATH to def_path (will set the path global variable).
274	 * (import of environment below will probably change this setting).
275	 */
276	vp = global("PATH");
277	/* setstr can't fail here */
278	setstr(vp, def_path, KSH_RETURN_ERROR);
279
280	/*
281	 * Turn on nohup by default for now - will change to off
282	 * by default once people are aware of its existence
283	 * (AT&T ksh does not have a nohup option - it always sends
284	 * the hup).
285	 */
286	Flag(FNOHUP) = 1;
287
288	/*
289	 * Turn on brace expansion by default. AT&T kshs that have
290	 * alternation always have it on.
291	 */
292	Flag(FBRACEEXPAND) = 1;
293
294	/*
295	 * Set edit mode to emacs by default, may be overridden
296	 * by the environment or the user. Also, we want tab completion
297	 * on in vi by default.
298	 */
299	change_flag(FEMACS, OF_SPECIAL, 1);
300#if !MKSH_S_NOVI
301	Flag(FVITABCOMPLETE) = 1;
302#endif
303
304	/* import environment */
305	if (environ != NULL)
306		for (wp = (const char **)environ; *wp != NULL; wp++)
307			typeset(*wp, IMPORT | EXPORT, 0, 0, 0);
308
309	/* for security */
310	typeset(initifs, 0, 0, 0, 0);
311
312	/* assign default shell variable values */
313	substitute(initsubs, 0);
314
315	/* Figure out the current working directory and set $PWD */
316	vp = global("PWD");
317	cp = str_val(vp);
318	/* Try to use existing $PWD if it is valid */
319	set_current_wd((cp[0] == '/' && test_eval(NULL, TO_FILEQ, cp, ".",
320	    true)) ? cp : NULL);
321	if (current_wd[0])
322		simplify_path(current_wd);
323	/* Only set pwd if we know where we are or if it had a bogus value */
324	if (current_wd[0] || *cp)
325		/* setstr can't fail here */
326		setstr(vp, current_wd, KSH_RETURN_ERROR);
327
328	for (wp = initcoms; *wp != NULL; wp++) {
329		shcomexec(wp);
330		while (*wp != NULL)
331			wp++;
332	}
333	setint_n(global("COLUMNS"), 0);
334	setint_n(global("LINES"), 0);
335	setint_n(global("OPTIND"), 1);
336
337	kshuid = getuid();
338	kshgid = getgid();
339	kshegid = getegid();
340
341	safe_prompt = ksheuid ? "$ " : "# ";
342	vp = global("PS1");
343	/* Set PS1 if unset or we are root and prompt doesn't contain a # */
344	if (!(vp->flag & ISSET) ||
345	    (!ksheuid && !strchr(str_val(vp), '#')))
346		/* setstr can't fail here */
347		setstr(vp, safe_prompt, KSH_RETURN_ERROR);
348	setint_n((vp = global("PGRP")), (mksh_uari_t)kshpgrp);
349	vp->flag |= INT_U;
350	setint_n((vp = global("PPID")), (mksh_uari_t)kshppid);
351	vp->flag |= INT_U;
352	setint_n((vp = global("USER_ID")), (mksh_uari_t)ksheuid);
353	vp->flag |= INT_U;
354	setint_n((vp = global("KSHUID")), (mksh_uari_t)kshuid);
355	vp->flag |= INT_U;
356	setint_n((vp = global("KSHEGID")), (mksh_uari_t)kshegid);
357	vp->flag |= INT_U;
358	setint_n((vp = global("KSHGID")), (mksh_uari_t)kshgid);
359	vp->flag |= INT_U;
360	setint_n((vp = global("RANDOM")), rndsetup());
361	vp->flag |= INT_U;
362	setint_n((vp_pipest = global("PIPESTATUS")), 0);
363
364	/* Set this before parsing arguments */
365	Flag(FPRIVILEGED) = kshuid != ksheuid || kshgid != kshegid;
366
367	/* this to note if monitor is set on command line (see below) */
368#ifndef MKSH_UNEMPLOYED
369	Flag(FMONITOR) = 127;
370#endif
371	/* this to note if utf-8 mode is set on command line (see below) */
372	UTFMODE = 2;
373
374	if (!Flag(FAS_BUILTIN)) {
375		argi = parse_args(argv, OF_CMDLINE, NULL);
376		if (argi < 0)
377			return (1);
378	}
379
380#ifdef DEBUG
381	/* test wraparound of arithmetic types */
382	{
383		volatile long xl;
384		volatile unsigned long xul;
385		volatile int xi;
386		volatile unsigned int xui;
387		volatile mksh_ari_t xa;
388		volatile mksh_uari_t xua, xua2;
389		volatile uint8_t xc;
390
391		xa = 2147483647;
392		xua = 2147483647;
393		++xa;
394		++xua;
395		xua2 = xa;
396		xl = xa;
397		xul = xua;
398		xa = 0;
399		xua = 0;
400		--xa;
401		--xua;
402		xi = xa;
403		xui = xua;
404		xa = -1;
405		xua = xa;
406		++xa;
407		++xua;
408		xc = 0;
409		--xc;
410		if ((xua2 != 2147483648UL) ||
411		    (xl != -2147483648L) || (xul != 2147483648UL) ||
412		    (xi != -1) || (xui != 4294967295U) ||
413		    (xa != 0) || (xua != 0) || (xc != 255))
414			errorf("integer wraparound test failed");
415	}
416#endif
417
418	/* process this later only, default to off (hysterical raisins) */
419	utf_flag = UTFMODE;
420	UTFMODE = 0;
421
422	if (Flag(FAS_BUILTIN)) {
423		/* auto-detect from environment variables, always */
424		utf_flag = 3;
425	} else if (Flag(FCOMMAND)) {
426		s = pushs(SSTRING, ATEMP);
427		if (!(s->start = s->str = argv[argi++]))
428			errorf("%s %s", "-c", "requires an argument");
429#ifdef MKSH_MIDNIGHTBSD01ASH_COMPAT
430		/* compatibility to MidnightBSD 0.1 /bin/sh (kludge) */
431		if (Flag(FSH) && argv[argi] && !strcmp(argv[argi], "--"))
432			++argi;
433#endif
434		if (argv[argi])
435			kshname = argv[argi++];
436	} else if (argi < argc && !Flag(FSTDIN)) {
437		s = pushs(SFILE, ATEMP);
438		s->file = argv[argi++];
439		s->u.shf = shf_open(s->file, O_RDONLY, 0,
440		    SHF_MAPHI | SHF_CLEXEC);
441		if (s->u.shf == NULL) {
442			shl_stdout_ok = false;
443			warningf(true, "%s: %s", s->file, strerror(errno));
444			/* mandated by SUSv4 */
445			exstat = 127;
446			unwind(LERROR);
447		}
448		kshname = s->file;
449	} else {
450		Flag(FSTDIN) = 1;
451		s = pushs(SSTDIN, ATEMP);
452		s->file = "<stdin>";
453		s->u.shf = shf_fdopen(0, SHF_RD | can_seek(0),
454		    NULL);
455		if (isatty(0) && isatty(2)) {
456			Flag(FTALKING) = Flag(FTALKING_I) = 1;
457			/* The following only if isatty(0) */
458			s->flags |= SF_TTY;
459			s->u.shf->flags |= SHF_INTERRUPT;
460			s->file = NULL;
461		}
462	}
463
464	/* this bizarreness is mandated by POSIX */
465	if (fstat(0, &s_stdin) >= 0 && S_ISCHR(s_stdin.st_mode) &&
466	    Flag(FTALKING))
467		reset_nonblock(0);
468
469	/* initialise job control */
470	j_init();
471	/* Do this after j_init(), as tty_fd is not initialised until then */
472	if (Flag(FTALKING)) {
473		if (utf_flag == 2) {
474#ifndef MKSH_ASSUME_UTF8
475			/* auto-detect from locale or environment */
476			utf_flag = 4;
477#elif MKSH_ASSUME_UTF8
478			utf_flag = 1;
479#else
480			/* always disable UTF-8 (for interactive) */
481			utf_flag = 0;
482#endif
483		}
484		x_init();
485	}
486
487#ifdef SIGWINCH
488	sigtraps[SIGWINCH].flags |= TF_SHELL_USES;
489	setsig(&sigtraps[SIGWINCH], x_sigwinch,
490	    SS_RESTORE_ORIG|SS_FORCE|SS_SHTRAP);
491#endif
492
493	l = e->loc;
494	if (Flag(FAS_BUILTIN)) {
495		l->argc = argc;
496		l->argv = argv;
497		l->argv[0] = ccp;
498	} else {
499		l->argc = argc - argi;
500		l->argv = &argv[argi - 1];
501		l->argv[0] = kshname;
502		getopts_reset(1);
503	}
504
505	/* divine the initial state of the utf8-mode Flag */
506#define isuc(x)	(((x) != NULL) && \
507	    (stristr((x), "UTF-8") || stristr((x), "utf8")))
508	ccp = null;
509	switch (utf_flag) {
510
511	/* auto-detect from locale or environment */
512	case 4:
513#if HAVE_SETLOCALE_CTYPE
514		ccp = setlocale(LC_CTYPE, "");
515#if HAVE_LANGINFO_CODESET
516		if (!isuc(ccp))
517			ccp = nl_langinfo(CODESET);
518#endif
519		if (!isuc(ccp))
520			ccp = null;
521		/* FALLTHROUGH */
522#endif
523
524	/* auto-detect from environment */
525	case 3:
526		/* these were imported from environ earlier */
527		if (ccp == null)
528			ccp = str_val(global("LC_ALL"));
529		if (ccp == null)
530			ccp = str_val(global("LC_CTYPE"));
531		if (ccp == null)
532			ccp = str_val(global("LANG"));
533		UTFMODE = isuc(ccp);
534		break;
535
536	/* not set on command line, not FTALKING */
537	case 2:
538	/* unknown values */
539	default:
540		utf_flag = 0;
541		/* FALLTHROUGH */
542
543	/* known values */
544	case 1:
545	case 0:
546		UTFMODE = utf_flag;
547		break;
548	}
549#undef isuc
550
551	/* Disable during .profile/ENV reading */
552	restricted = Flag(FRESTRICTED);
553	Flag(FRESTRICTED) = 0;
554	errexit = Flag(FERREXIT);
555	Flag(FERREXIT) = 0;
556
557	/*
558	 * Do this before profile/$ENV so that if it causes problems in them,
559	 * user will know why things broke.
560	 */
561	if (!current_wd[0] && Flag(FTALKING))
562		warningf(false, "can't determine current directory");
563
564	if (Flag(FLOGIN)) {
565		include(MKSH_SYSTEM_PROFILE, 0, NULL, 1);
566		if (!Flag(FPRIVILEGED))
567			include(substitute("$HOME/.profile", 0), 0,
568			    NULL, 1);
569	}
570	if (Flag(FPRIVILEGED))
571		include(MKSH_SUID_PROFILE, 0, NULL, 1);
572	else if (Flag(FTALKING)) {
573		char *env_file;
574
575		/* include $ENV */
576		env_file = substitute(substitute("${ENV:-" MKSHRC_PATH "}", 0),
577		    DOTILDE);
578		if (*env_file != '\0')
579			include(env_file, 0, NULL, 1);
580	}
581
582	if (restricted) {
583		shcomexec(restr_com);
584		/* After typeset command... */
585		Flag(FRESTRICTED) = 1;
586	}
587	Flag(FERREXIT) = errexit;
588
589	if (Flag(FTALKING))
590		hist_init(s);
591	else
592		/* set after ENV */
593		Flag(FTRACKALL) = 1;
594
595	alarm_init();
596
597	if (Flag(FAS_BUILTIN))
598		return (shcomexec(l->argv));
599
600	/* doesn't return */
601	shell(s, true);
602	/* NOTREACHED */
603	return (0);
604}
605
606int
607include(const char *name, int argc, const char **argv, int intr_ok)
608{
609	Source *volatile s = NULL;
610	struct shf *shf;
611	const char **volatile old_argv;
612	volatile int old_argc;
613	int i;
614
615	shf = shf_open(name, O_RDONLY, 0, SHF_MAPHI | SHF_CLEXEC);
616	if (shf == NULL)
617		return (-1);
618
619	if (argv) {
620		old_argv = e->loc->argv;
621		old_argc = e->loc->argc;
622	} else {
623		old_argv = NULL;
624		old_argc = 0;
625	}
626	newenv(E_INCL);
627	i = sigsetjmp(e->jbuf, 0);
628	if (i) {
629		quitenv(s ? s->u.shf : NULL);
630		if (old_argv) {
631			e->loc->argv = old_argv;
632			e->loc->argc = old_argc;
633		}
634		switch (i) {
635		case LRETURN:
636		case LERROR:
637			/* see below */
638			return (exstat & 0xFF);
639		case LINTR:
640			/*
641			 * intr_ok is set if we are including .profile or $ENV.
642			 * If user ^Cs out, we don't want to kill the shell...
643			 */
644			if (intr_ok && (exstat - 128) != SIGTERM)
645				return (1);
646			/* FALLTHROUGH */
647		case LEXIT:
648		case LLEAVE:
649		case LSHELL:
650			unwind(i);
651			/* NOTREACHED */
652		default:
653			internal_errorf("%s %d", "include", i);
654			/* NOTREACHED */
655		}
656	}
657	if (argv) {
658		e->loc->argv = argv;
659		e->loc->argc = argc;
660	}
661	s = pushs(SFILE, ATEMP);
662	s->u.shf = shf;
663	strdupx(s->file, name, ATEMP);
664	i = shell(s, false);
665	quitenv(s->u.shf);
666	if (old_argv) {
667		e->loc->argv = old_argv;
668		e->loc->argc = old_argc;
669	}
670	/* & 0xff to ensure value not -1 */
671	return (i & 0xFF);
672}
673
674/* spawn a command into a shell optionally keeping track of the line number */
675int
676command(const char *comm, int line)
677{
678	Source *s;
679
680	s = pushs(SSTRING, ATEMP);
681	s->start = s->str = comm;
682	s->line = line;
683	return (shell(s, false));
684}
685
686/*
687 * run the commands from the input source, returning status.
688 */
689int
690shell(Source * volatile s, volatile int toplevel)
691{
692	struct op *t;
693	volatile int wastty = s->flags & SF_TTY;
694	volatile int attempts = 13;
695	volatile int interactive = Flag(FTALKING) && toplevel;
696	volatile bool sfirst = true;
697	Source *volatile old_source = source;
698	int i;
699
700	newenv(E_PARSE);
701	if (interactive)
702		really_exit = 0;
703	i = sigsetjmp(e->jbuf, 0);
704	if (i) {
705		switch (i) {
706		case LINTR:
707			/* we get here if SIGINT not caught or ignored */
708		case LERROR:
709		case LSHELL:
710			if (interactive) {
711				if (i == LINTR)
712					shellf("\n");
713				/*
714				 * Reset any eof that was read as part of a
715				 * multiline command.
716				 */
717				if (Flag(FIGNOREEOF) && s->type == SEOF &&
718				    wastty)
719					s->type = SSTDIN;
720				/*
721				 * Used by exit command to get back to
722				 * top level shell. Kind of strange since
723				 * interactive is set if we are reading from
724				 * a tty, but to have stopped jobs, one only
725				 * needs FMONITOR set (not FTALKING/SF_TTY)...
726				 */
727				/* toss any input we have so far */
728				s->start = s->str = null;
729				break;
730			}
731			/* FALLTHROUGH */
732		case LEXIT:
733		case LLEAVE:
734		case LRETURN:
735			source = old_source;
736			quitenv(NULL);
737			/* keep on going */
738			unwind(i);
739			/* NOTREACHED */
740		default:
741			source = old_source;
742			quitenv(NULL);
743			internal_errorf("%s %d", "shell", i);
744			/* NOTREACHED */
745		}
746	}
747	while (/* CONSTCOND */ 1) {
748		if (trap)
749			runtraps(0);
750
751		if (s->next == NULL) {
752			if (Flag(FVERBOSE))
753				s->flags |= SF_ECHO;
754			else
755				s->flags &= ~SF_ECHO;
756		}
757		if (interactive) {
758			j_notify();
759			set_prompt(PS1, s);
760		}
761		t = compile(s, sfirst);
762		sfirst = false;
763		if (t != NULL && t->type == TEOF) {
764			if (wastty && Flag(FIGNOREEOF) && --attempts > 0) {
765				shellf("Use 'exit' to leave mksh\n");
766				s->type = SSTDIN;
767			} else if (wastty && !really_exit &&
768			    j_stopped_running()) {
769				really_exit = 1;
770				s->type = SSTDIN;
771			} else {
772				/*
773				 * this for POSIX which says EXIT traps
774				 * shall be taken in the environment
775				 * immediately after the last command
776				 * executed.
777				 */
778				if (toplevel)
779					unwind(LEXIT);
780				break;
781			}
782		}
783		if (t && (!Flag(FNOEXEC) || (s->flags & SF_TTY)))
784			exstat = execute(t, 0, NULL);
785
786		if (t != NULL && t->type != TEOF && interactive && really_exit)
787			really_exit = 0;
788
789		reclaim();
790	}
791	quitenv(NULL);
792	source = old_source;
793	return (exstat);
794}
795
796/* return to closest error handler or shell(), exit if none found */
797void
798unwind(int i)
799{
800	/* ordering for EXIT vs ERR is a bit odd (this is what AT&T ksh does) */
801	if (i == LEXIT || (Flag(FERREXIT) && (i == LERROR || i == LINTR) &&
802	    sigtraps[ksh_SIGEXIT].trap)) {
803		++trap_nested;
804		runtrap(&sigtraps[ksh_SIGEXIT], trap_nested == 1);
805		--trap_nested;
806		i = LLEAVE;
807	} else if (Flag(FERREXIT) && (i == LERROR || i == LINTR)) {
808		++trap_nested;
809		runtrap(&sigtraps[ksh_SIGERR], trap_nested == 1);
810		--trap_nested;
811		i = LLEAVE;
812	}
813	while (/* CONSTCOND */ 1) {
814		switch (e->type) {
815		case E_PARSE:
816		case E_FUNC:
817		case E_INCL:
818		case E_LOOP:
819		case E_ERRH:
820			siglongjmp(e->jbuf, i);
821			/* NOTREACHED */
822		case E_NONE:
823			if (i == LINTR)
824				e->flags |= EF_FAKE_SIGDIE;
825			/* FALLTHROUGH */
826		default:
827			quitenv(NULL);
828		}
829	}
830}
831
832void
833newenv(int type)
834{
835	struct env *ep;
836	char *cp;
837
838	/*
839	 * struct env includes ALLOC_ITEM for alignment constraints
840	 * so first get the actually used memory, then assign it
841	 */
842	cp = alloc(sizeof(struct env) - ALLOC_SIZE, ATEMP);
843	/* undo what alloc() did to the malloc result address */
844	ep = (void *)(cp - ALLOC_SIZE);
845	/* initialise public members of struct env (not the ALLOC_ITEM) */
846	ainit(&ep->area);
847	ep->oenv = e;
848	ep->loc = e->loc;
849	ep->savefd = NULL;
850	ep->temps = NULL;
851	ep->type = type;
852	ep->flags = 0;
853	/* jump buffer is invalid because flags == 0 */
854	e = ep;
855}
856
857void
858quitenv(struct shf *shf)
859{
860	struct env *ep = e;
861	char *cp;
862	int fd;
863
864	if (ep->oenv && ep->oenv->loc != ep->loc)
865		popblock();
866	if (ep->savefd != NULL) {
867		for (fd = 0; fd < NUFILE; fd++)
868			/* if ep->savefd[fd] < 0, means fd was closed */
869			if (ep->savefd[fd])
870				restfd(fd, ep->savefd[fd]);
871		if (ep->savefd[2])
872			/* Clear any write errors */
873			shf_reopen(2, SHF_WR, shl_out);
874	}
875	/*
876	 * Bottom of the stack.
877	 * Either main shell is exiting or cleanup_parents_env() was called.
878	 */
879	if (ep->oenv == NULL) {
880		if (ep->type == E_NONE) {
881			/* Main shell exiting? */
882#if HAVE_PERSISTENT_HISTORY
883			if (Flag(FTALKING))
884				hist_finish();
885#endif
886			j_exit();
887			if (ep->flags & EF_FAKE_SIGDIE) {
888				int sig = exstat - 128;
889
890				/*
891				 * ham up our death a bit (AT&T ksh
892				 * only seems to do this for SIGTERM)
893				 * Don't do it for SIGQUIT, since we'd
894				 * dump a core..
895				 */
896				if ((sig == SIGINT || sig == SIGTERM) &&
897				    (kshpgrp == kshpid)) {
898					setsig(&sigtraps[sig], SIG_DFL,
899					    SS_RESTORE_CURR | SS_FORCE);
900					kill(0, sig);
901				}
902			}
903		}
904		if (shf)
905			shf_close(shf);
906		reclaim();
907		exit(exstat);
908	}
909	if (shf)
910		shf_close(shf);
911	reclaim();
912
913	e = e->oenv;
914
915	/* free the struct env - tricky due to the ALLOC_ITEM inside */
916	cp = (void *)ep;
917	afree(cp + ALLOC_SIZE, ATEMP);
918}
919
920/* Called after a fork to cleanup stuff left over from parents environment */
921void
922cleanup_parents_env(void)
923{
924	struct env *ep;
925	int fd;
926
927	mkssert(e != NULL);
928
929	/*
930	 * Don't clean up temporary files - parent will probably need them.
931	 * Also, can't easily reclaim memory since variables, etc. could be
932	 * anywhere.
933	 */
934
935	/* close all file descriptors hiding in savefd */
936	for (ep = e; ep; ep = ep->oenv) {
937		if (ep->savefd) {
938			for (fd = 0; fd < NUFILE; fd++)
939				if (ep->savefd[fd] > 0)
940					close(ep->savefd[fd]);
941			afree(ep->savefd, &ep->area);
942			ep->savefd = NULL;
943		}
944	}
945	e->oenv = NULL;
946}
947
948/* Called just before an execve cleanup stuff temporary files */
949void
950cleanup_proc_env(void)
951{
952	struct env *ep;
953
954	for (ep = e; ep; ep = ep->oenv)
955		remove_temps(ep->temps);
956}
957
958/* remove temp files and free ATEMP Area */
959static void
960reclaim(void)
961{
962	remove_temps(e->temps);
963	e->temps = NULL;
964	afreeall(&e->area);
965}
966
967static void
968remove_temps(struct temp *tp)
969{
970	for (; tp != NULL; tp = tp->next)
971		if (tp->pid == procpid)
972			unlink(tp->name);
973}
974
975/*
976 * Initialise tty_fd. Used for saving/reseting tty modes upon
977 * foreground job completion and for setting up tty process group.
978 */
979void
980tty_init(bool init_ttystate, bool need_tty)
981{
982	bool do_close = true;
983	int tfd;
984
985	if (tty_fd >= 0) {
986		close(tty_fd);
987		tty_fd = -1;
988	}
989	tty_devtty = true;
990
991#ifdef _UWIN
992	/*XXX imake style */
993	if (isatty(3)) {
994		/* fd 3 on UWIN _is_ /dev/tty (or our controlling tty) */
995		tfd = 3;
996		do_close = false;
997	} else
998#endif
999	  if ((tfd = open("/dev/tty", O_RDWR, 0)) < 0) {
1000		tty_devtty = false;
1001		if (need_tty)
1002			warningf(false, "%s: %s %s: %s",
1003			    "No controlling tty", "open", "/dev/tty",
1004			    strerror(errno));
1005	}
1006	if (tfd < 0) {
1007		do_close = false;
1008		if (isatty(0))
1009			tfd = 0;
1010		else if (isatty(2))
1011			tfd = 2;
1012		else {
1013			if (need_tty)
1014				warningf(false, "can't find tty fd");
1015			return;
1016		}
1017	}
1018	if ((tty_fd = fcntl(tfd, F_DUPFD, FDBASE)) < 0) {
1019		if (need_tty)
1020			warningf(false, "%s: %s %s: %s", "j_ttyinit",
1021			    "dup of tty fd", "failed", strerror(errno));
1022	} else if (fcntl(tty_fd, F_SETFD, FD_CLOEXEC) < 0) {
1023		if (need_tty)
1024			warningf(false, "%s: %s: %s", "j_ttyinit",
1025			    "can't set close-on-exec flag", strerror(errno));
1026		close(tty_fd);
1027		tty_fd = -1;
1028	} else if (init_ttystate)
1029		tcgetattr(tty_fd, &tty_state);
1030	if (do_close)
1031		close(tfd);
1032}
1033
1034void
1035tty_close(void)
1036{
1037	if (tty_fd >= 0) {
1038		close(tty_fd);
1039		tty_fd = -1;
1040	}
1041}
1042
1043/* A shell error occurred (eg, syntax error, etc.) */
1044
1045#define VWARNINGF_ERRORPREFIX	1
1046#define VWARNINGF_FILELINE	2
1047#define VWARNINGF_BUILTIN	4
1048#define VWARNINGF_INTERNAL	8
1049
1050static void vwarningf(unsigned int, const char *, va_list)
1051    MKSH_A_FORMAT(__printf__, 2, 0);
1052
1053static void
1054vwarningf(unsigned int flags, const char *fmt, va_list ap)
1055{
1056	if (*fmt != 1) {
1057		if (flags & VWARNINGF_INTERNAL)
1058			shf_fprintf(shl_out, "internal error: ");
1059		if (flags & VWARNINGF_ERRORPREFIX)
1060			error_prefix(tobool(flags & VWARNINGF_FILELINE));
1061		if ((flags & VWARNINGF_BUILTIN) &&
1062		    /* not set when main() calls parse_args() */
1063		    builtin_argv0 && builtin_argv0 != kshname)
1064			shf_fprintf(shl_out, "%s: ", builtin_argv0);
1065		shf_vfprintf(shl_out, fmt, ap);
1066		shf_putchar('\n', shl_out);
1067	}
1068	shf_flush(shl_out);
1069}
1070
1071void
1072errorfx(int rc, const char *fmt, ...)
1073{
1074	va_list va;
1075
1076	exstat = rc;
1077
1078	/* debugging: note that stdout not valid */
1079	shl_stdout_ok = false;
1080
1081	va_start(va, fmt);
1082	vwarningf(VWARNINGF_ERRORPREFIX | VWARNINGF_FILELINE, fmt, va);
1083	va_end(va);
1084	unwind(LERROR);
1085}
1086
1087void
1088errorf(const char *fmt, ...)
1089{
1090	va_list va;
1091
1092	exstat = 1;
1093
1094	/* debugging: note that stdout not valid */
1095	shl_stdout_ok = false;
1096
1097	va_start(va, fmt);
1098	vwarningf(VWARNINGF_ERRORPREFIX | VWARNINGF_FILELINE, fmt, va);
1099	va_end(va);
1100	unwind(LERROR);
1101}
1102
1103/* like errorf(), but no unwind is done */
1104void
1105warningf(bool fileline, const char *fmt, ...)
1106{
1107	va_list va;
1108
1109	va_start(va, fmt);
1110	vwarningf(VWARNINGF_ERRORPREFIX | (fileline ? VWARNINGF_FILELINE : 0),
1111	    fmt, va);
1112	va_end(va);
1113}
1114
1115/*
1116 * Used by built-in utilities to prefix shell and utility name to message
1117 * (also unwinds environments for special builtins).
1118 */
1119void
1120bi_errorf(const char *fmt, ...)
1121{
1122	va_list va;
1123
1124	/* debugging: note that stdout not valid */
1125	shl_stdout_ok = false;
1126
1127	exstat = 1;
1128
1129	va_start(va, fmt);
1130	vwarningf(VWARNINGF_ERRORPREFIX | VWARNINGF_FILELINE |
1131	    VWARNINGF_BUILTIN, fmt, va);
1132	va_end(va);
1133
1134	/*
1135	 * POSIX special builtins and ksh special builtins cause
1136	 * non-interactive shells to exit.
1137	 * XXX odd use of KEEPASN; also may not want LERROR here
1138	 */
1139	if (builtin_flag & SPEC_BI) {
1140		builtin_argv0 = NULL;
1141		unwind(LERROR);
1142	}
1143}
1144
1145/* Called when something that shouldn't happen does */
1146void
1147internal_errorf(const char *fmt, ...)
1148{
1149	va_list va;
1150
1151	va_start(va, fmt);
1152	vwarningf(VWARNINGF_INTERNAL, fmt, va);
1153	va_end(va);
1154	unwind(LERROR);
1155}
1156
1157void
1158internal_warningf(const char *fmt, ...)
1159{
1160	va_list va;
1161
1162	va_start(va, fmt);
1163	vwarningf(VWARNINGF_INTERNAL, fmt, va);
1164	va_end(va);
1165}
1166
1167/* used by error reporting functions to print "ksh: .kshrc[25]: " */
1168void
1169error_prefix(bool fileline)
1170{
1171	/* Avoid foo: foo[2]: ... */
1172	if (!fileline || !source || !source->file ||
1173	    strcmp(source->file, kshname) != 0)
1174		shf_fprintf(shl_out, "%s: ", kshname + (*kshname == '-'));
1175	if (fileline && source && source->file != NULL) {
1176		shf_fprintf(shl_out, "%s[%d]: ", source->file,
1177		    source->errline > 0 ? source->errline : source->line);
1178		source->errline = 0;
1179	}
1180}
1181
1182/* printf to shl_out (stderr) with flush */
1183void
1184shellf(const char *fmt, ...)
1185{
1186	va_list va;
1187
1188	if (!initio_done)
1189		/* shl_out may not be set up yet... */
1190		return;
1191	va_start(va, fmt);
1192	shf_vfprintf(shl_out, fmt, va);
1193	va_end(va);
1194	shf_flush(shl_out);
1195}
1196
1197/* printf to shl_stdout (stdout) */
1198void
1199shprintf(const char *fmt, ...)
1200{
1201	va_list va;
1202
1203	if (!shl_stdout_ok)
1204		internal_errorf("shl_stdout not valid");
1205	va_start(va, fmt);
1206	shf_vfprintf(shl_stdout, fmt, va);
1207	va_end(va);
1208}
1209
1210/* test if we can seek backwards fd (returns 0 or SHF_UNBUF) */
1211int
1212can_seek(int fd)
1213{
1214	struct stat statb;
1215
1216	return (fstat(fd, &statb) == 0 && !S_ISREG(statb.st_mode) ?
1217	    SHF_UNBUF : 0);
1218}
1219
1220struct shf shf_iob[3];
1221
1222void
1223initio(void)
1224{
1225	/* force buffer allocation */
1226	shf_fdopen(1, SHF_WR, shl_stdout);
1227	shf_fdopen(2, SHF_WR, shl_out);
1228	/* force buffer allocation */
1229	shf_fdopen(2, SHF_WR, shl_spare);
1230	initio_done = 1;
1231}
1232
1233/* A dup2() with error checking */
1234int
1235ksh_dup2(int ofd, int nfd, bool errok)
1236{
1237	int rv;
1238
1239	if (((rv = dup2(ofd, nfd)) < 0) && !errok && (errno != EBADF))
1240		errorf("too many files open in shell");
1241
1242#ifdef __ultrix
1243	/*XXX imake style */
1244	if (rv >= 0)
1245		fcntl(nfd, F_SETFD, 0);
1246#endif
1247
1248	return (rv);
1249}
1250
1251/*
1252 * Move fd from user space (0 <= fd < 10) to shell space (fd >= 10),
1253 * set close-on-exec flag. See FDBASE in sh.h, maybe 24 not 10 here.
1254 */
1255short
1256savefd(int fd)
1257{
1258	int nfd = fd;
1259
1260	if (fd < FDBASE && (nfd = fcntl(fd, F_DUPFD, FDBASE)) < 0 &&
1261	    errno == EBADF)
1262		return (-1);
1263	if (nfd < 0 || nfd > SHRT_MAX)
1264		errorf("too many files open in shell");
1265	fcntl(nfd, F_SETFD, FD_CLOEXEC);
1266	return ((short)nfd);
1267}
1268
1269void
1270restfd(int fd, int ofd)
1271{
1272	if (fd == 2)
1273		shf_flush(&shf_iob[fd]);
1274	if (ofd < 0)
1275		/* original fd closed */
1276		close(fd);
1277	else if (fd != ofd) {
1278		/*XXX: what to do if this dup fails? */
1279		ksh_dup2(ofd, fd, true);
1280		close(ofd);
1281	}
1282}
1283
1284void
1285openpipe(int *pv)
1286{
1287	int lpv[2];
1288
1289	if (pipe(lpv) < 0)
1290		errorf("can't create pipe - try again");
1291	pv[0] = savefd(lpv[0]);
1292	if (pv[0] != lpv[0])
1293		close(lpv[0]);
1294	pv[1] = savefd(lpv[1]);
1295	if (pv[1] != lpv[1])
1296		close(lpv[1]);
1297}
1298
1299void
1300closepipe(int *pv)
1301{
1302	close(pv[0]);
1303	close(pv[1]);
1304}
1305
1306/*
1307 * Called by iosetup() (deals with 2>&4, etc.), c_read, c_print to turn
1308 * a string (the X in 2>&X, read -uX, print -uX) into a file descriptor.
1309 */
1310int
1311check_fd(const char *name, int mode, const char **emsgp)
1312{
1313	int fd, fl;
1314
1315	if (name[0] == 'p' && !name[1])
1316		return (coproc_getfd(mode, emsgp));
1317	for (fd = 0; ksh_isdigit(*name); ++name)
1318		fd = (fd * 10) + *name - '0';
1319	if (*name || fd >= FDBASE) {
1320		if (emsgp)
1321			*emsgp = "illegal file descriptor name";
1322		return (-1);
1323	}
1324	if ((fl = fcntl(fd, F_GETFL, 0)) < 0) {
1325		if (emsgp)
1326			*emsgp = "bad file descriptor";
1327		return (-1);
1328	}
1329	fl &= O_ACCMODE;
1330	/*
1331	 * X_OK is a kludge to disable this check for dups (x<&1):
1332	 * historical shells never did this check (XXX don't know what
1333	 * POSIX has to say).
1334	 */
1335	if (!(mode & X_OK) && fl != O_RDWR && (
1336	    ((mode & R_OK) && fl != O_RDONLY) ||
1337	    ((mode & W_OK) && fl != O_WRONLY))) {
1338		if (emsgp)
1339			*emsgp = (fl == O_WRONLY) ?
1340			    "fd not open for reading" :
1341			    "fd not open for writing";
1342		return (-1);
1343	}
1344	return (fd);
1345}
1346
1347/* Called once from main */
1348void
1349coproc_init(void)
1350{
1351	coproc.read = coproc.readw = coproc.write = -1;
1352	coproc.njobs = 0;
1353	coproc.id = 0;
1354}
1355
1356/* Called by c_read() when eof is read - close fd if it is the co-process fd */
1357void
1358coproc_read_close(int fd)
1359{
1360	if (coproc.read >= 0 && fd == coproc.read) {
1361		coproc_readw_close(fd);
1362		close(coproc.read);
1363		coproc.read = -1;
1364	}
1365}
1366
1367/*
1368 * Called by c_read() and by iosetup() to close the other side of the
1369 * read pipe, so reads will actually terminate.
1370 */
1371void
1372coproc_readw_close(int fd)
1373{
1374	if (coproc.readw >= 0 && coproc.read >= 0 && fd == coproc.read) {
1375		close(coproc.readw);
1376		coproc.readw = -1;
1377	}
1378}
1379
1380/*
1381 * Called by c_print when a write to a fd fails with EPIPE and by iosetup
1382 * when co-process input is dup'd
1383 */
1384void
1385coproc_write_close(int fd)
1386{
1387	if (coproc.write >= 0 && fd == coproc.write) {
1388		close(coproc.write);
1389		coproc.write = -1;
1390	}
1391}
1392
1393/*
1394 * Called to check for existence of/value of the co-process file descriptor.
1395 * (Used by check_fd() and by c_read/c_print to deal with -p option).
1396 */
1397int
1398coproc_getfd(int mode, const char **emsgp)
1399{
1400	int fd = (mode & R_OK) ? coproc.read : coproc.write;
1401
1402	if (fd >= 0)
1403		return (fd);
1404	if (emsgp)
1405		*emsgp = "no coprocess";
1406	return (-1);
1407}
1408
1409/*
1410 * called to close file descriptors related to the coprocess (if any)
1411 * Should be called with SIGCHLD blocked.
1412 */
1413void
1414coproc_cleanup(int reuse)
1415{
1416	/* This to allow co-processes to share output pipe */
1417	if (!reuse || coproc.readw < 0 || coproc.read < 0) {
1418		if (coproc.read >= 0) {
1419			close(coproc.read);
1420			coproc.read = -1;
1421		}
1422		if (coproc.readw >= 0) {
1423			close(coproc.readw);
1424			coproc.readw = -1;
1425		}
1426	}
1427	if (coproc.write >= 0) {
1428		close(coproc.write);
1429		coproc.write = -1;
1430	}
1431}
1432
1433struct temp *
1434maketemp(Area *ap, Temp_type type, struct temp **tlist)
1435{
1436	struct temp *tp;
1437	size_t len;
1438	int fd;
1439	char *pathname;
1440	const char *dir;
1441
1442	dir = tmpdir ? tmpdir : MKSH_DEFAULT_TMPDIR;
1443#if HAVE_MKSTEMP
1444	len = strlen(dir) + 6 + 10 + 1;
1445#else
1446	pathname = tempnam(dir, "mksh.");
1447	len = ((pathname == NULL) ? 0 : strlen(pathname)) + 1;
1448#endif
1449	/* reasonably sure that this will not overflow */
1450	tp = alloc(sizeof(struct temp) + len, ap);
1451	tp->name = (char *)&tp[1];
1452#if !HAVE_MKSTEMP
1453	if (pathname == NULL)
1454		tp->name[0] = '\0';
1455	else {
1456		memcpy(tp->name, pathname, len);
1457		free_ostempnam(pathname);
1458	}
1459#endif
1460	pathname = tp->name;
1461	tp->shf = NULL;
1462	tp->type = type;
1463#if HAVE_MKSTEMP
1464	shf_snprintf(pathname, len, "%s%s", dir, "/mksh.XXXXXXXXXX");
1465	if ((fd = mkstemp(pathname)) >= 0)
1466#else
1467	if (tp->name[0] && (fd = open(tp->name, O_CREAT | O_RDWR, 0600)) >= 0)
1468#endif
1469		tp->shf = shf_fdopen(fd, SHF_WR, NULL);
1470	tp->pid = procpid;
1471
1472	tp->next = *tlist;
1473	*tlist = tp;
1474	return (tp);
1475}
1476
1477/*
1478 * We use a similar collision resolution algorithm as Python 2.5.4
1479 * but with a slightly tweaked implementation written from scratch.
1480 */
1481
1482#define	INIT_TBLSHIFT	3	/* initial table shift (2^3 = 8) */
1483#define PERTURB_SHIFT	5	/* see Python 2.5.4 Objects/dictobject.c */
1484
1485static void tgrow(struct table *);
1486static int tnamecmp(const void *, const void *);
1487
1488static void
1489tgrow(struct table *tp)
1490{
1491	size_t i, j, osize, mask, perturb;
1492	struct tbl *tblp, **pp;
1493	struct tbl **ntblp, **otblp = tp->tbls;
1494
1495	if (tp->tshift > 29)
1496		internal_errorf("hash table size limit reached");
1497
1498	/* calculate old size, new shift and new size */
1499	osize = (size_t)1 << (tp->tshift++);
1500	i = osize << 1;
1501
1502	ntblp = alloc2(i, sizeof(struct tbl *), tp->areap);
1503	/* multiplication cannot overflow: alloc2 checked that */
1504	memset(ntblp, 0, i * sizeof(struct tbl *));
1505
1506	/* table can get 80% full except when reaching its limit */
1507	tp->nfree = (tp->tshift == 30) ? 0x3FFF0000UL : ((i * 4) / 5);
1508	tp->tbls = ntblp;
1509	if (otblp == NULL)
1510		return;
1511
1512	mask = i - 1;
1513	for (i = 0; i < osize; i++)
1514		if ((tblp = otblp[i]) != NULL) {
1515			if ((tblp->flag & DEFINED)) {
1516				/* search for free hash table slot */
1517				j = (perturb = tblp->ua.hval) & mask;
1518				goto find_first_empty_slot;
1519 find_next_empty_slot:
1520				j = (j << 2) + j + perturb + 1;
1521				perturb >>= PERTURB_SHIFT;
1522 find_first_empty_slot:
1523				pp = &ntblp[j & mask];
1524				if (*pp != NULL)
1525					goto find_next_empty_slot;
1526				/* found an empty hash table slot */
1527				*pp = tblp;
1528				tp->nfree--;
1529			} else if (!(tblp->flag & FINUSE)) {
1530				afree(tblp, tp->areap);
1531			}
1532		}
1533	afree(otblp, tp->areap);
1534}
1535
1536void
1537ktinit(Area *ap, struct table *tp, uint8_t initshift)
1538{
1539	tp->areap = ap;
1540	tp->tbls = NULL;
1541	tp->tshift = ((initshift > INIT_TBLSHIFT) ?
1542	    initshift : INIT_TBLSHIFT) - 1;
1543	tgrow(tp);
1544}
1545
1546/* table, name (key) to search for, hash(name), rv pointer to tbl ptr */
1547struct tbl *
1548ktscan(struct table *tp, const char *name, uint32_t h, struct tbl ***ppp)
1549{
1550	size_t j, perturb, mask;
1551	struct tbl **pp, *p;
1552
1553	mask = ((size_t)1 << (tp->tshift)) - 1;
1554	/* search for hash table slot matching name */
1555	j = (perturb = h) & mask;
1556	goto find_first_slot;
1557 find_next_slot:
1558	j = (j << 2) + j + perturb + 1;
1559	perturb >>= PERTURB_SHIFT;
1560 find_first_slot:
1561	pp = &tp->tbls[j & mask];
1562	if ((p = *pp) != NULL && (p->ua.hval != h || !(p->flag & DEFINED) ||
1563	    strcmp(p->name, name)))
1564		goto find_next_slot;
1565	/* p == NULL if not found, correct found entry otherwise */
1566	if (ppp)
1567		*ppp = pp;
1568	return (p);
1569}
1570
1571/* table, name (key) to enter, hash(n) */
1572struct tbl *
1573ktenter(struct table *tp, const char *n, uint32_t h)
1574{
1575	struct tbl **pp, *p;
1576	size_t len;
1577
1578 Search:
1579	if ((p = ktscan(tp, n, h, &pp)))
1580		return (p);
1581
1582	if (tp->nfree == 0) {
1583		/* too full */
1584		tgrow(tp);
1585		goto Search;
1586	}
1587
1588	/* create new tbl entry */
1589	len = strlen(n);
1590	checkoktoadd(len, offsetof(struct tbl, name[0]) + 1);
1591	p = alloc(offsetof(struct tbl, name[0]) + ++len, tp->areap);
1592	p->flag = 0;
1593	p->type = 0;
1594	p->areap = tp->areap;
1595	p->ua.hval = h;
1596	p->u2.field = 0;
1597	p->u.array = NULL;
1598	memcpy(p->name, n, len);
1599
1600	/* enter in tp->tbls */
1601	tp->nfree--;
1602	*pp = p;
1603	return (p);
1604}
1605
1606void
1607ktwalk(struct tstate *ts, struct table *tp)
1608{
1609	ts->left = (size_t)1 << (tp->tshift);
1610	ts->next = tp->tbls;
1611}
1612
1613struct tbl *
1614ktnext(struct tstate *ts)
1615{
1616	while (--ts->left >= 0) {
1617		struct tbl *p = *ts->next++;
1618		if (p != NULL && (p->flag & DEFINED))
1619			return (p);
1620	}
1621	return (NULL);
1622}
1623
1624static int
1625tnamecmp(const void *p1, const void *p2)
1626{
1627	const struct tbl *a = *((const struct tbl * const *)p1);
1628	const struct tbl *b = *((const struct tbl * const *)p2);
1629
1630	return (strcmp(a->name, b->name));
1631}
1632
1633struct tbl **
1634ktsort(struct table *tp)
1635{
1636	size_t i;
1637	struct tbl **p, **sp, **dp;
1638
1639	/*
1640	 * since the table is never entirely full, no need to reserve
1641	 * additional space for the trailing NULL appended below
1642	 */
1643	i = (size_t)1 << (tp->tshift);
1644	p = alloc2(i, sizeof(struct tbl *), ATEMP);
1645	sp = tp->tbls;		/* source */
1646	dp = p;			/* dest */
1647	while (i--)
1648		if ((*dp = *sp++) != NULL && (((*dp)->flag & DEFINED) ||
1649		    ((*dp)->flag & ARRAY)))
1650			dp++;
1651	qsort(p, (i = dp - p), sizeof(struct tbl *), tnamecmp);
1652	p[i] = NULL;
1653	return (p);
1654}
1655
1656#ifdef SIGWINCH
1657static void
1658x_sigwinch(int sig MKSH_A_UNUSED)
1659{
1660	/* this runs inside interrupt context, with errno saved */
1661
1662	got_winch = 1;
1663}
1664#endif
1665