1/*
2 * Copyright (c) 1989, 1993
3 *	The Regents of the University of California.  All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Guido van Rossum.
7 *
8 * Copyright (c) 2011 The FreeBSD Foundation
9 * All rights reserved.
10 * Portions of this software were developed by David Chisnall
11 * under sponsorship from the FreeBSD Foundation.
12 *
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions
15 * are met:
16 * 1. Redistributions of source code must retain the above copyright
17 *    notice, this list of conditions and the following disclaimer.
18 * 2. Redistributions in binary form must reproduce the above copyright
19 *    notice, this list of conditions and the following disclaimer in the
20 *    documentation and/or other materials provided with the distribution.
21 * 3. Neither the name of the University nor the names of its contributors
22 *    may be used to endorse or promote products derived from this software
23 *    without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 * SUCH DAMAGE.
36 *
37 * From: @(#)glob.c	8.3 (Berkeley) 10/13/93
38 * From: FreeBSD: head/lib/libc/gen/glob.c 317913 2017-05-07 19:52:56Z jilles
39 */
40
41#include <sys/cdefs.h>
42__FBSDID("$FreeBSD$");
43
44#include <sys/param.h>
45#define	_WANT_FREEBSD11_STAT
46#include <sys/stat.h>
47
48#include <ctype.h>
49#define	_WANT_FREEBSD11_DIRENT
50#include <dirent.h>
51#include <errno.h>
52#include <glob.h>
53#include <limits.h>
54#include <pwd.h>
55#include <stdint.h>
56#include <stdio.h>
57#include <stdlib.h>
58#include <string.h>
59#include <unistd.h>
60#include <wchar.h>
61
62#include "collate.h"
63#include "gen-compat.h"
64#include "glob-compat11.h"
65
66/*
67 * glob(3) expansion limits. Stop the expansion if any of these limits
68 * is reached. This caps the runtime in the face of DoS attacks. See
69 * also CVE-2010-2632
70 */
71#define	GLOB_LIMIT_BRACE	128	/* number of brace calls */
72#define	GLOB_LIMIT_PATH		65536	/* number of path elements */
73#define	GLOB_LIMIT_READDIR	16384	/* number of readdirs */
74#define	GLOB_LIMIT_STAT		1024	/* number of stat system calls */
75#define	GLOB_LIMIT_STRING	ARG_MAX	/* maximum total size for paths */
76
77struct glob_limit {
78	size_t	l_brace_cnt;
79	size_t	l_path_lim;
80	size_t	l_readdir_cnt;
81	size_t	l_stat_cnt;
82	size_t	l_string_cnt;
83};
84
85#define	DOT		L'.'
86#define	EOS		L'\0'
87#define	LBRACKET	L'['
88#define	NOT		L'!'
89#define	QUESTION	L'?'
90#define	QUOTE		L'\\'
91#define	RANGE		L'-'
92#define	RBRACKET	L']'
93#define	SEP		L'/'
94#define	STAR		L'*'
95#define	TILDE		L'~'
96#define	LBRACE		L'{'
97#define	RBRACE		L'}'
98#define	COMMA		L','
99
100#define	M_QUOTE		0x8000000000ULL
101#define	M_PROTECT	0x4000000000ULL
102#define	M_MASK		0xffffffffffULL
103#define	M_CHAR		0x00ffffffffULL
104
105typedef uint_fast64_t Char;
106
107#define	CHAR(c)		((Char)((c)&M_CHAR))
108#define	META(c)		((Char)((c)|M_QUOTE))
109#define	UNPROT(c)	((c) & ~M_PROTECT)
110#define	M_ALL		META(L'*')
111#define	M_END		META(L']')
112#define	M_NOT		META(L'!')
113#define	M_ONE		META(L'?')
114#define	M_RNG		META(L'-')
115#define	M_SET		META(L'[')
116#define	ismeta(c)	(((c)&M_QUOTE) != 0)
117#ifdef DEBUG
118#define	isprot(c)	(((c)&M_PROTECT) != 0)
119#endif
120
121static int	 compare(const void *, const void *);
122static int	 g_Ctoc(const Char *, char *, size_t);
123static int	 g_lstat(Char *, struct freebsd11_stat *, glob11_t *);
124static DIR	*g_opendir(Char *, glob11_t *);
125static const Char *g_strchr(const Char *, wchar_t);
126#ifdef notdef
127static Char	*g_strcat(Char *, const Char *);
128#endif
129static int	 g_stat(Char *, struct freebsd11_stat *, glob11_t *);
130static int	 glob0(const Char *, glob11_t *, struct glob_limit *,
131    const char *);
132static int	 glob1(Char *, glob11_t *, struct glob_limit *);
133static int	 glob2(Char *, Char *, Char *, Char *, glob11_t *,
134    struct glob_limit *);
135static int	 glob3(Char *, Char *, Char *, Char *, Char *, glob11_t *,
136    struct glob_limit *);
137static int	 globextend(const Char *, glob11_t *, struct glob_limit *,
138    const char *);
139static const Char *
140		 globtilde(const Char *, Char *, size_t, glob11_t *);
141static int	 globexp0(const Char *, glob11_t *, struct glob_limit *,
142    const char *);
143static int	 globexp1(const Char *, glob11_t *, struct glob_limit *);
144static int	 globexp2(const Char *, const Char *, glob11_t *,
145    struct glob_limit *);
146static int	 globfinal(glob11_t *, struct glob_limit *, size_t,
147    const char *);
148static int	 match(Char *, Char *, Char *);
149static int	 err_nomatch(glob11_t *, struct glob_limit *, const char *);
150static int	 err_aborted(glob11_t *, int, char *);
151#ifdef DEBUG
152static void	 qprintf(const char *, Char *);
153#endif
154
155int
156freebsd11_glob(const char * __restrict pattern, int flags,
157	 int (*errfunc)(const char *, int), glob11_t * __restrict pglob)
158{
159	struct glob_limit limit = { 0, 0, 0, 0, 0 };
160	const char *patnext;
161	Char *bufnext, *bufend, patbuf[MAXPATHLEN], prot;
162	mbstate_t mbs;
163	wchar_t wc;
164	size_t clen;
165	int too_long;
166
167	patnext = pattern;
168	if (!(flags & GLOB_APPEND)) {
169		pglob->gl_pathc = 0;
170		pglob->gl_pathv = NULL;
171		if (!(flags & GLOB_DOOFFS))
172			pglob->gl_offs = 0;
173	}
174	if (flags & GLOB_LIMIT) {
175		limit.l_path_lim = pglob->gl_matchc;
176		if (limit.l_path_lim == 0)
177			limit.l_path_lim = GLOB_LIMIT_PATH;
178	}
179	pglob->gl_flags = flags & ~GLOB_MAGCHAR;
180	pglob->gl_errfunc = errfunc;
181	pglob->gl_matchc = 0;
182
183	bufnext = patbuf;
184	bufend = bufnext + MAXPATHLEN - 1;
185	too_long = 1;
186	if (flags & GLOB_NOESCAPE) {
187		memset(&mbs, 0, sizeof(mbs));
188		while (bufnext <= bufend) {
189			clen = mbrtowc(&wc, patnext, MB_LEN_MAX, &mbs);
190			if (clen == (size_t)-1 || clen == (size_t)-2)
191				return (err_nomatch(pglob, &limit, pattern));
192			else if (clen == 0) {
193				too_long = 0;
194				break;
195			}
196			*bufnext++ = wc;
197			patnext += clen;
198		}
199	} else {
200		/* Protect the quoted characters. */
201		memset(&mbs, 0, sizeof(mbs));
202		while (bufnext <= bufend) {
203			if (*patnext == '\\') {
204				if (*++patnext == '\0') {
205					*bufnext++ = QUOTE;
206					continue;
207				}
208				prot = M_PROTECT;
209			} else
210				prot = 0;
211			clen = mbrtowc(&wc, patnext, MB_LEN_MAX, &mbs);
212			if (clen == (size_t)-1 || clen == (size_t)-2)
213				return (err_nomatch(pglob, &limit, pattern));
214			else if (clen == 0) {
215				too_long = 0;
216				break;
217			}
218			*bufnext++ = wc | prot;
219			patnext += clen;
220		}
221	}
222	if (too_long)
223		return (err_nomatch(pglob, &limit, pattern));
224	*bufnext = EOS;
225
226	if (flags & GLOB_BRACE)
227	    return (globexp0(patbuf, pglob, &limit, pattern));
228	else
229	    return (glob0(patbuf, pglob, &limit, pattern));
230}
231
232static int
233globexp0(const Char *pattern, glob11_t *pglob, struct glob_limit *limit,
234    const char *origpat) {
235	int rv;
236	size_t oldpathc;
237
238	/* Protect a single {}, for find(1), like csh */
239	if (pattern[0] == LBRACE && pattern[1] == RBRACE && pattern[2] == EOS) {
240		if ((pglob->gl_flags & GLOB_LIMIT) &&
241		    limit->l_brace_cnt++ >= GLOB_LIMIT_BRACE) {
242			errno = E2BIG;
243			return (GLOB_NOSPACE);
244		}
245		return (glob0(pattern, pglob, limit, origpat));
246	}
247
248	oldpathc = pglob->gl_pathc;
249
250	if ((rv = globexp1(pattern, pglob, limit)) != 0)
251		return rv;
252
253	return (globfinal(pglob, limit, oldpathc, origpat));
254}
255
256/*
257 * Expand recursively a glob {} pattern. When there is no more expansion
258 * invoke the standard globbing routine to glob the rest of the magic
259 * characters
260 */
261static int
262globexp1(const Char *pattern, glob11_t *pglob, struct glob_limit *limit)
263{
264	const Char* ptr;
265
266	if ((ptr = g_strchr(pattern, LBRACE)) != NULL) {
267		if ((pglob->gl_flags & GLOB_LIMIT) &&
268		    limit->l_brace_cnt++ >= GLOB_LIMIT_BRACE) {
269			errno = E2BIG;
270			return (GLOB_NOSPACE);
271		}
272		return (globexp2(ptr, pattern, pglob, limit));
273	}
274
275	return (glob0(pattern, pglob, limit, NULL));
276}
277
278
279/*
280 * Recursive brace globbing helper. Tries to expand a single brace.
281 * If it succeeds then it invokes globexp1 with the new pattern.
282 * If it fails then it tries to glob the rest of the pattern and returns.
283 */
284static int
285globexp2(const Char *ptr, const Char *pattern, glob11_t *pglob,
286    struct glob_limit *limit)
287{
288	int     i, rv;
289	Char   *lm, *ls;
290	const Char *pe, *pm, *pm1, *pl;
291	Char    patbuf[MAXPATHLEN];
292
293	/* copy part up to the brace */
294	for (lm = patbuf, pm = pattern; pm != ptr; *lm++ = *pm++)
295		continue;
296	*lm = EOS;
297	ls = lm;
298
299	/* Find the balanced brace */
300	for (i = 0, pe = ++ptr; *pe != EOS; pe++)
301		if (*pe == LBRACKET) {
302			/* Ignore everything between [] */
303			for (pm = pe++; *pe != RBRACKET && *pe != EOS; pe++)
304				continue;
305			if (*pe == EOS) {
306				/*
307				 * We could not find a matching RBRACKET.
308				 * Ignore and just look for RBRACE
309				 */
310				pe = pm;
311			}
312		}
313		else if (*pe == LBRACE)
314			i++;
315		else if (*pe == RBRACE) {
316			if (i == 0)
317				break;
318			i--;
319		}
320
321	/* Non matching braces; just glob the pattern */
322	if (i != 0 || *pe == EOS)
323		return (glob0(pattern, pglob, limit, NULL));
324
325	for (i = 0, pl = pm = ptr; pm <= pe; pm++)
326		switch (*pm) {
327		case LBRACKET:
328			/* Ignore everything between [] */
329			for (pm1 = pm++; *pm != RBRACKET && *pm != EOS; pm++)
330				continue;
331			if (*pm == EOS) {
332				/*
333				 * We could not find a matching RBRACKET.
334				 * Ignore and just look for RBRACE
335				 */
336				pm = pm1;
337			}
338			break;
339
340		case LBRACE:
341			i++;
342			break;
343
344		case RBRACE:
345			if (i) {
346			    i--;
347			    break;
348			}
349			/* FALLTHROUGH */
350		case COMMA:
351			if (i && *pm == COMMA)
352				break;
353			else {
354				/* Append the current string */
355				for (lm = ls; (pl < pm); *lm++ = *pl++)
356					continue;
357				/*
358				 * Append the rest of the pattern after the
359				 * closing brace
360				 */
361				for (pl = pe + 1; (*lm++ = *pl++) != EOS;)
362					continue;
363
364				/* Expand the current pattern */
365#ifdef DEBUG
366				qprintf("globexp2:", patbuf);
367#endif
368				rv = globexp1(patbuf, pglob, limit);
369				if (rv)
370					return (rv);
371
372				/* move after the comma, to the next string */
373				pl = pm + 1;
374			}
375			break;
376
377		default:
378			break;
379		}
380	return (0);
381}
382
383
384
385/*
386 * expand tilde from the passwd file.
387 */
388static const Char *
389globtilde(const Char *pattern, Char *patbuf, size_t patbuf_len, glob11_t *pglob)
390{
391	struct passwd *pwd;
392	char *h, *sc;
393	const Char *p;
394	Char *b, *eb;
395	wchar_t wc;
396	wchar_t wbuf[MAXPATHLEN];
397	wchar_t *wbufend, *dc;
398	size_t clen;
399	mbstate_t mbs;
400	int too_long;
401
402	if (*pattern != TILDE || !(pglob->gl_flags & GLOB_TILDE))
403		return (pattern);
404
405	/*
406	 * Copy up to the end of the string or /
407	 */
408	eb = &patbuf[patbuf_len - 1];
409	for (p = pattern + 1, b = patbuf;
410	    b < eb && *p != EOS && UNPROT(*p) != SEP; *b++ = *p++)
411		continue;
412
413	if (*p != EOS && UNPROT(*p) != SEP)
414		return (NULL);
415
416	*b = EOS;
417	h = NULL;
418
419	if (patbuf[0] == EOS) {
420		/*
421		 * handle a plain ~ or ~/ by expanding $HOME first (iff
422		 * we're not running setuid or setgid) and then trying
423		 * the password file
424		 */
425		if (issetugid() != 0 ||
426		    (h = getenv("HOME")) == NULL) {
427			if (((h = getlogin()) != NULL &&
428			     (pwd = getpwnam(h)) != NULL) ||
429			    (pwd = getpwuid(getuid())) != NULL)
430				h = pwd->pw_dir;
431			else
432				return (pattern);
433		}
434	}
435	else {
436		/*
437		 * Expand a ~user
438		 */
439		if (g_Ctoc(patbuf, (char *)wbuf, sizeof(wbuf)))
440			return (NULL);
441		if ((pwd = getpwnam((char *)wbuf)) == NULL)
442			return (pattern);
443		else
444			h = pwd->pw_dir;
445	}
446
447	/* Copy the home directory */
448	dc = wbuf;
449	sc = h;
450	wbufend = wbuf + MAXPATHLEN - 1;
451	too_long = 1;
452	memset(&mbs, 0, sizeof(mbs));
453	while (dc <= wbufend) {
454		clen = mbrtowc(&wc, sc, MB_LEN_MAX, &mbs);
455		if (clen == (size_t)-1 || clen == (size_t)-2) {
456			/* XXX See initial comment #2. */
457			wc = (unsigned char)*sc;
458			clen = 1;
459			memset(&mbs, 0, sizeof(mbs));
460		}
461		if ((*dc++ = wc) == EOS) {
462			too_long = 0;
463			break;
464		}
465		sc += clen;
466	}
467	if (too_long)
468		return (NULL);
469
470	dc = wbuf;
471	for (b = patbuf; b < eb && *dc != EOS; *b++ = *dc++ | M_PROTECT)
472		continue;
473	if (*dc != EOS)
474		return (NULL);
475
476	/* Append the rest of the pattern */
477	if (*p != EOS) {
478		too_long = 1;
479		while (b <= eb) {
480			if ((*b++ = *p++) == EOS) {
481				too_long = 0;
482				break;
483			}
484		}
485		if (too_long)
486			return (NULL);
487	} else
488		*b = EOS;
489
490	return (patbuf);
491}
492
493
494/*
495 * The main glob() routine: compiles the pattern (optionally processing
496 * quotes), calls glob1() to do the real pattern matching, and finally
497 * sorts the list (unless unsorted operation is requested).  Returns 0
498 * if things went well, nonzero if errors occurred.
499 */
500static int
501glob0(const Char *pattern, glob11_t *pglob, struct glob_limit *limit,
502    const char *origpat) {
503	const Char *qpatnext;
504	int err;
505	size_t oldpathc;
506	Char *bufnext, c, patbuf[MAXPATHLEN];
507
508	qpatnext = globtilde(pattern, patbuf, MAXPATHLEN, pglob);
509	if (qpatnext == NULL) {
510		errno = E2BIG;
511		return (GLOB_NOSPACE);
512	}
513	oldpathc = pglob->gl_pathc;
514	bufnext = patbuf;
515
516	/* We don't need to check for buffer overflow any more. */
517	while ((c = *qpatnext++) != EOS) {
518		switch (c) {
519		case LBRACKET:
520			c = *qpatnext;
521			if (c == NOT)
522				++qpatnext;
523			if (*qpatnext == EOS ||
524			    g_strchr(qpatnext+1, RBRACKET) == NULL) {
525				*bufnext++ = LBRACKET;
526				if (c == NOT)
527					--qpatnext;
528				break;
529			}
530			*bufnext++ = M_SET;
531			if (c == NOT)
532				*bufnext++ = M_NOT;
533			c = *qpatnext++;
534			do {
535				*bufnext++ = CHAR(c);
536				if (*qpatnext == RANGE &&
537				    (c = qpatnext[1]) != RBRACKET) {
538					*bufnext++ = M_RNG;
539					*bufnext++ = CHAR(c);
540					qpatnext += 2;
541				}
542			} while ((c = *qpatnext++) != RBRACKET);
543			pglob->gl_flags |= GLOB_MAGCHAR;
544			*bufnext++ = M_END;
545			break;
546		case QUESTION:
547			pglob->gl_flags |= GLOB_MAGCHAR;
548			*bufnext++ = M_ONE;
549			break;
550		case STAR:
551			pglob->gl_flags |= GLOB_MAGCHAR;
552			/* collapse adjacent stars to one,
553			 * to avoid exponential behavior
554			 */
555			if (bufnext == patbuf || bufnext[-1] != M_ALL)
556			    *bufnext++ = M_ALL;
557			break;
558		default:
559			*bufnext++ = CHAR(c);
560			break;
561		}
562	}
563	*bufnext = EOS;
564#ifdef DEBUG
565	qprintf("glob0:", patbuf);
566#endif
567
568	if ((err = glob1(patbuf, pglob, limit)) != 0)
569		return(err);
570
571	if (origpat != NULL)
572		return (globfinal(pglob, limit, oldpathc, origpat));
573
574	return (0);
575}
576
577static int
578globfinal(glob11_t *pglob, struct glob_limit *limit, size_t oldpathc,
579    const char *origpat) {
580	if (pglob->gl_pathc == oldpathc)
581		return (err_nomatch(pglob, limit, origpat));
582
583	if (!(pglob->gl_flags & GLOB_NOSORT))
584		qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
585		    pglob->gl_pathc - oldpathc, sizeof(char *), compare);
586
587	return (0);
588}
589
590static int
591compare(const void *p, const void *q)
592{
593	return (strcoll(*(char **)p, *(char **)q));
594}
595
596static int
597glob1(Char *pattern, glob11_t *pglob, struct glob_limit *limit)
598{
599	Char pathbuf[MAXPATHLEN];
600
601	/* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
602	if (*pattern == EOS)
603		return (0);
604	return (glob2(pathbuf, pathbuf, pathbuf + MAXPATHLEN - 1,
605	    pattern, pglob, limit));
606}
607
608/*
609 * The functions glob2 and glob3 are mutually recursive; there is one level
610 * of recursion for each segment in the pattern that contains one or more
611 * meta characters.
612 */
613static int
614glob2(Char *pathbuf, Char *pathend, Char *pathend_last, Char *pattern,
615      glob11_t *pglob, struct glob_limit *limit)
616{
617	struct freebsd11_stat sb;
618	Char *p, *q;
619	int anymeta;
620
621	/*
622	 * Loop over pattern segments until end of pattern or until
623	 * segment with meta character found.
624	 */
625	for (anymeta = 0;;) {
626		if (*pattern == EOS) {		/* End of pattern? */
627			*pathend = EOS;
628			if (g_lstat(pathbuf, &sb, pglob))
629				return (0);
630
631			if ((pglob->gl_flags & GLOB_LIMIT) &&
632			    limit->l_stat_cnt++ >= GLOB_LIMIT_STAT) {
633				errno = E2BIG;
634				return (GLOB_NOSPACE);
635			}
636			if ((pglob->gl_flags & GLOB_MARK) &&
637			    UNPROT(pathend[-1]) != SEP &&
638			    (S_ISDIR(sb.st_mode) ||
639			    (S_ISLNK(sb.st_mode) &&
640			    g_stat(pathbuf, &sb, pglob) == 0 &&
641			    S_ISDIR(sb.st_mode)))) {
642				if (pathend + 1 > pathend_last) {
643					errno = E2BIG;
644					return (GLOB_NOSPACE);
645				}
646				*pathend++ = SEP;
647				*pathend = EOS;
648			}
649			++pglob->gl_matchc;
650			return (globextend(pathbuf, pglob, limit, NULL));
651		}
652
653		/* Find end of next segment, copy tentatively to pathend. */
654		q = pathend;
655		p = pattern;
656		while (*p != EOS && UNPROT(*p) != SEP) {
657			if (ismeta(*p))
658				anymeta = 1;
659			if (q + 1 > pathend_last) {
660				errno = E2BIG;
661				return (GLOB_NOSPACE);
662			}
663			*q++ = *p++;
664		}
665
666		if (!anymeta) {		/* No expansion, do next segment. */
667			pathend = q;
668			pattern = p;
669			while (UNPROT(*pattern) == SEP) {
670				if (pathend + 1 > pathend_last) {
671					errno = E2BIG;
672					return (GLOB_NOSPACE);
673				}
674				*pathend++ = *pattern++;
675			}
676		} else			/* Need expansion, recurse. */
677			return (glob3(pathbuf, pathend, pathend_last, pattern,
678			    p, pglob, limit));
679	}
680	/* NOTREACHED */
681}
682
683static int
684glob3(Char *pathbuf, Char *pathend, Char *pathend_last,
685      Char *pattern, Char *restpattern,
686      glob11_t *pglob, struct glob_limit *limit)
687{
688	struct freebsd11_dirent *dp;
689	DIR *dirp;
690	int err, too_long, saverrno, saverrno2;
691	char buf[MAXPATHLEN + MB_LEN_MAX - 1];
692
693	struct freebsd11_dirent *(*readdirfunc)(DIR *);
694
695	if (pathend > pathend_last) {
696		errno = E2BIG;
697		return (GLOB_NOSPACE);
698	}
699	*pathend = EOS;
700	if (pglob->gl_errfunc != NULL &&
701	    g_Ctoc(pathbuf, buf, sizeof(buf))) {
702		errno = E2BIG;
703		return (GLOB_NOSPACE);
704	}
705
706	saverrno = errno;
707	errno = 0;
708	if ((dirp = g_opendir(pathbuf, pglob)) == NULL) {
709		if (errno == ENOENT || errno == ENOTDIR)
710			return (0);
711		err = err_aborted(pglob, errno, buf);
712		if (errno == 0)
713			errno = saverrno;
714		return (err);
715	}
716
717	err = 0;
718
719	/* pglob->gl_readdir takes a void *, fix this manually */
720	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
721		readdirfunc =
722		    (struct freebsd11_dirent *(*)(DIR *))pglob->gl_readdir;
723	else
724		readdirfunc = freebsd11_readdir;
725
726	errno = 0;
727	/* Search directory for matching names. */
728	while ((dp = (*readdirfunc)(dirp)) != NULL) {
729		char *sc;
730		Char *dc;
731		wchar_t wc;
732		size_t clen;
733		mbstate_t mbs;
734
735		if ((pglob->gl_flags & GLOB_LIMIT) &&
736		    limit->l_readdir_cnt++ >= GLOB_LIMIT_READDIR) {
737			errno = E2BIG;
738			err = GLOB_NOSPACE;
739			break;
740		}
741
742		/* Initial DOT must be matched literally. */
743		if (dp->d_name[0] == '.' && UNPROT(*pattern) != DOT) {
744			errno = 0;
745			continue;
746		}
747		memset(&mbs, 0, sizeof(mbs));
748		dc = pathend;
749		sc = dp->d_name;
750		too_long = 1;
751		while (dc <= pathend_last) {
752			clen = mbrtowc(&wc, sc, MB_LEN_MAX, &mbs);
753			if (clen == (size_t)-1 || clen == (size_t)-2) {
754				/* XXX See initial comment #2. */
755				wc = (unsigned char)*sc;
756				clen = 1;
757				memset(&mbs, 0, sizeof(mbs));
758			}
759			if ((*dc++ = wc) == EOS) {
760				too_long = 0;
761				break;
762			}
763			sc += clen;
764		}
765		if (too_long && (err = err_aborted(pglob, ENAMETOOLONG,
766		    buf))) {
767			errno = ENAMETOOLONG;
768			break;
769		}
770		if (too_long || !match(pathend, pattern, restpattern)) {
771			*pathend = EOS;
772			errno = 0;
773			continue;
774		}
775		if (errno == 0)
776			errno = saverrno;
777		err = glob2(pathbuf, --dc, pathend_last, restpattern,
778		    pglob, limit);
779		if (err)
780			break;
781		errno = 0;
782	}
783
784	saverrno2 = errno;
785	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
786		(*pglob->gl_closedir)(dirp);
787	else
788		closedir(dirp);
789	errno = saverrno2;
790
791	if (err)
792		return (err);
793
794	if (dp == NULL && errno != 0 &&
795	    (err = err_aborted(pglob, errno, buf)))
796		return (err);
797
798	if (errno == 0)
799		errno = saverrno;
800	return (0);
801}
802
803
804/*
805 * Extend the gl_pathv member of a glob11_t structure to accommodate a new item,
806 * add the new item, and update gl_pathc.
807 *
808 * This assumes the BSD realloc, which only copies the block when its size
809 * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
810 * behavior.
811 *
812 * Return 0 if new item added, error code if memory couldn't be allocated.
813 *
814 * Invariant of the glob11_t structure:
815 *	Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
816 *	gl_pathv points to (gl_offs + gl_pathc + 1) items.
817 */
818static int
819globextend(const Char *path, glob11_t *pglob, struct glob_limit *limit,
820    const char *origpat)
821{
822	char **pathv;
823	size_t i, newn, len;
824	char *copy;
825	const Char *p;
826
827	if ((pglob->gl_flags & GLOB_LIMIT) &&
828	    pglob->gl_matchc > limit->l_path_lim) {
829		errno = E2BIG;
830		return (GLOB_NOSPACE);
831	}
832
833	newn = 2 + pglob->gl_pathc + pglob->gl_offs;
834	/* reallocarray(NULL, newn, size) is equivalent to malloc(newn*size). */
835	pathv = reallocarray(pglob->gl_pathv, newn, sizeof(*pathv));
836	if (pathv == NULL)
837		return (GLOB_NOSPACE);
838
839	if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
840		/* first time around -- clear initial gl_offs items */
841		pathv += pglob->gl_offs;
842		for (i = pglob->gl_offs + 1; --i > 0; )
843			*--pathv = NULL;
844	}
845	pglob->gl_pathv = pathv;
846
847	if (origpat != NULL)
848		copy = strdup(origpat);
849	else {
850		for (p = path; *p++ != EOS;)
851			continue;
852		len = MB_CUR_MAX * (size_t)(p - path); /* XXX overallocation */
853		if ((copy = malloc(len)) != NULL) {
854			if (g_Ctoc(path, copy, len)) {
855				free(copy);
856				errno = E2BIG;
857				return (GLOB_NOSPACE);
858			}
859		}
860	}
861	if (copy != NULL) {
862		limit->l_string_cnt += strlen(copy) + 1;
863		if ((pglob->gl_flags & GLOB_LIMIT) &&
864		    limit->l_string_cnt >= GLOB_LIMIT_STRING) {
865			free(copy);
866			errno = E2BIG;
867			return (GLOB_NOSPACE);
868		}
869		pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
870	}
871	pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
872	return (copy == NULL ? GLOB_NOSPACE : 0);
873}
874
875/*
876 * pattern matching function for filenames.
877 */
878static int
879match(Char *name, Char *pat, Char *patend)
880{
881	int ok, negate_range;
882	Char c, k, *nextp, *nextn;
883	struct xlocale_collate *table =
884		(struct xlocale_collate*)__get_locale()->components[XLC_COLLATE];
885
886	nextn = NULL;
887	nextp = NULL;
888
889	while (1) {
890		while (pat < patend) {
891			c = *pat++;
892			switch (c & M_MASK) {
893			case M_ALL:
894				if (pat == patend)
895					return (1);
896				if (*name == EOS)
897					return (0);
898				nextn = name + 1;
899				nextp = pat - 1;
900				break;
901			case M_ONE:
902				if (*name++ == EOS)
903					goto fail;
904				break;
905			case M_SET:
906				ok = 0;
907				if ((k = *name++) == EOS)
908					goto fail;
909				negate_range = ((*pat & M_MASK) == M_NOT);
910				if (negate_range != 0)
911					++pat;
912				while (((c = *pat++) & M_MASK) != M_END)
913					if ((*pat & M_MASK) == M_RNG) {
914						if (table->__collate_load_error ?
915						    CHAR(c) <= CHAR(k) &&
916						    CHAR(k) <= CHAR(pat[1]) :
917						    __wcollate_range_cmp(CHAR(c),
918						    CHAR(k)) <= 0 &&
919						    __wcollate_range_cmp(CHAR(k),
920						    CHAR(pat[1])) <= 0)
921							ok = 1;
922						pat += 2;
923					} else if (c == k)
924						ok = 1;
925				if (ok == negate_range)
926					goto fail;
927				break;
928			default:
929				if (*name++ != c)
930					goto fail;
931				break;
932			}
933		}
934		if (*name == EOS)
935			return (1);
936
937	fail:
938		if (nextn == NULL)
939			break;
940		pat = nextp;
941		name = nextn;
942	}
943	return (0);
944}
945
946/* Free allocated data belonging to a glob11_t structure. */
947void
948freebsd11_globfree(glob11_t *pglob)
949{
950	size_t i;
951	char **pp;
952
953	if (pglob->gl_pathv != NULL) {
954		pp = pglob->gl_pathv + pglob->gl_offs;
955		for (i = pglob->gl_pathc; i--; ++pp)
956			if (*pp)
957				free(*pp);
958		free(pglob->gl_pathv);
959		pglob->gl_pathv = NULL;
960	}
961}
962
963static DIR *
964g_opendir(Char *str, glob11_t *pglob)
965{
966	char buf[MAXPATHLEN + MB_LEN_MAX - 1];
967
968	if (*str == EOS)
969		strcpy(buf, ".");
970	else {
971		if (g_Ctoc(str, buf, sizeof(buf))) {
972			errno = ENAMETOOLONG;
973			return (NULL);
974		}
975	}
976
977	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
978		return ((*pglob->gl_opendir)(buf));
979
980	return (opendir(buf));
981}
982
983static int
984g_lstat(Char *fn, struct freebsd11_stat *sb, glob11_t *pglob)
985{
986	char buf[MAXPATHLEN + MB_LEN_MAX - 1];
987
988	if (g_Ctoc(fn, buf, sizeof(buf))) {
989		errno = ENAMETOOLONG;
990		return (-1);
991	}
992	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
993		return((*pglob->gl_lstat)(buf, sb));
994	return (freebsd11_lstat(buf, sb));
995}
996
997static int
998g_stat(Char *fn, struct freebsd11_stat *sb, glob11_t *pglob)
999{
1000	char buf[MAXPATHLEN + MB_LEN_MAX - 1];
1001
1002	if (g_Ctoc(fn, buf, sizeof(buf))) {
1003		errno = ENAMETOOLONG;
1004		return (-1);
1005	}
1006	if (pglob->gl_flags & GLOB_ALTDIRFUNC)
1007		return ((*pglob->gl_stat)(buf, sb));
1008	return (freebsd11_stat(buf, sb));
1009}
1010
1011static const Char *
1012g_strchr(const Char *str, wchar_t ch)
1013{
1014
1015	do {
1016		if (*str == ch)
1017			return (str);
1018	} while (*str++);
1019	return (NULL);
1020}
1021
1022static int
1023g_Ctoc(const Char *str, char *buf, size_t len)
1024{
1025	mbstate_t mbs;
1026	size_t clen;
1027
1028	memset(&mbs, 0, sizeof(mbs));
1029	while (len >= MB_CUR_MAX) {
1030		clen = wcrtomb(buf, CHAR(*str), &mbs);
1031		if (clen == (size_t)-1) {
1032			/* XXX See initial comment #2. */
1033			*buf = (char)CHAR(*str);
1034			clen = 1;
1035			memset(&mbs, 0, sizeof(mbs));
1036		}
1037		if (CHAR(*str) == EOS)
1038			return (0);
1039		str++;
1040		buf += clen;
1041		len -= clen;
1042	}
1043	return (1);
1044}
1045
1046static int
1047err_nomatch(glob11_t *pglob, struct glob_limit *limit, const char *origpat) {
1048	/*
1049	 * If there was no match we are going to append the origpat
1050	 * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified
1051	 * and the origpat did not contain any magic characters
1052	 * GLOB_NOMAGIC is there just for compatibility with csh.
1053	 */
1054	if ((pglob->gl_flags & GLOB_NOCHECK) ||
1055	    ((pglob->gl_flags & GLOB_NOMAGIC) &&
1056	    !(pglob->gl_flags & GLOB_MAGCHAR)))
1057		return (globextend(NULL, pglob, limit, origpat));
1058	return (GLOB_NOMATCH);
1059}
1060
1061static int
1062err_aborted(glob11_t *pglob, int err, char *buf) {
1063	if ((pglob->gl_errfunc != NULL && pglob->gl_errfunc(buf, err)) ||
1064	    (pglob->gl_flags & GLOB_ERR))
1065		return (GLOB_ABORTED);
1066	return (0);
1067}
1068
1069#ifdef DEBUG
1070static void
1071qprintf(const char *str, Char *s)
1072{
1073	Char *p;
1074
1075	(void)printf("%s\n", str);
1076	if (s != NULL) {
1077		for (p = s; *p != EOS; p++)
1078			(void)printf("%c", (char)CHAR(*p));
1079		(void)printf("\n");
1080		for (p = s; *p != EOS; p++)
1081			(void)printf("%c", (isprot(*p) ? '\\' : ' '));
1082		(void)printf("\n");
1083		for (p = s; *p != EOS; p++)
1084			(void)printf("%c", (ismeta(*p) ? '_' : ' '));
1085		(void)printf("\n");
1086	}
1087}
1088#endif
1089
1090__sym_compat(glob, freebsd11_glob, FBSD_1.0);
1091__sym_compat(globfree, freebsd11_globfree, FBSD_1.0);
1092