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