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