xref: /freebsd/lib/libc/gen/glob-compat11.c (revision d3d381b2b194b4d24853e92eecef55f262688d1a)
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 
77 struct 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 
105 typedef 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 
121 static int	 compare(const void *, const void *);
122 static int	 g_Ctoc(const Char *, char *, size_t);
123 static int	 g_lstat(Char *, struct freebsd11_stat *, glob11_t *);
124 static DIR	*g_opendir(Char *, glob11_t *);
125 static const Char *g_strchr(const Char *, wchar_t);
126 #ifdef notdef
127 static Char	*g_strcat(Char *, const Char *);
128 #endif
129 static int	 g_stat(Char *, struct freebsd11_stat *, glob11_t *);
130 static int	 glob0(const Char *, glob11_t *, struct glob_limit *,
131     const char *);
132 static int	 glob1(Char *, glob11_t *, struct glob_limit *);
133 static int	 glob2(Char *, Char *, Char *, Char *, glob11_t *,
134     struct glob_limit *);
135 static int	 glob3(Char *, Char *, Char *, Char *, Char *, glob11_t *,
136     struct glob_limit *);
137 static int	 globextend(const Char *, glob11_t *, struct glob_limit *,
138     const char *);
139 static const Char *
140 		 globtilde(const Char *, Char *, size_t, glob11_t *);
141 static int	 globexp0(const Char *, glob11_t *, struct glob_limit *,
142     const char *);
143 static int	 globexp1(const Char *, glob11_t *, struct glob_limit *);
144 static int	 globexp2(const Char *, const Char *, glob11_t *,
145     struct glob_limit *);
146 static int	 globfinal(glob11_t *, struct glob_limit *, size_t,
147     const char *);
148 static int	 match(Char *, Char *, Char *);
149 static int	 err_nomatch(glob11_t *, struct glob_limit *, const char *);
150 static int	 err_aborted(glob11_t *, int, char *);
151 #ifdef DEBUG
152 static void	 qprintf(const char *, Char *);
153 #endif
154 
155 int
156 freebsd11_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 
232 static int
233 globexp0(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  */
261 static int
262 globexp1(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  */
284 static int
285 globexp2(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  */
388 static const Char *
389 globtilde(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  */
500 static int
501 glob0(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 
577 static int
578 globfinal(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 
590 static int
591 compare(const void *p, const void *q)
592 {
593 	return (strcoll(*(char **)p, *(char **)q));
594 }
595 
596 static int
597 glob1(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  */
613 static int
614 glob2(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 
683 static int
684 glob3(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  */
818 static int
819 globextend(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  */
878 static int
879 match(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. */
947 void
948 freebsd11_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 
963 static DIR *
964 g_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 
983 static int
984 g_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 
997 static int
998 g_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 
1011 static const Char *
1012 g_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 
1022 static int
1023 g_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 
1046 static int
1047 err_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 
1061 static int
1062 err_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
1070 static void
1071 qprintf(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