1 /* find.c - Search directories for matching files.
2 *
3 * Copyright 2014 Rob Landley <rob@landley.net>
4 *
5 * See http://pubs.opengroup.org/onlinepubs/9699919799/utilities/find.c
6 *
7 * Our "unspecified" behavior for no paths is to use "."
8 * Parentheses can only stack 4096 deep
9 * Not treating two {} as an error, but only using last
10
11 USE_FIND(NEWTOY(find, "?^HL[-HL]", TOYFLAG_USR|TOYFLAG_BIN))
12
13 config FIND
14 bool "find"
15 default y
16 help
17 usage: find [-HL] [DIR...] [<options>]
18
19 Search directories for matching files.
20 Default: search "." match all -print all matches.
21
22 -H Follow command line symlinks -L Follow all symlinks
23
24 Match filters:
25 -name PATTERN filename with wildcards -iname case insensitive -name
26 -path PATTERN path name with wildcards -ipath case insensitive -path
27 -user UNAME belongs to user UNAME -nouser user ID not known
28 -group GROUP belongs to group GROUP -nogroup group ID not known
29 -perm [-/]MODE permissions (-=min /=any) -prune ignore contents of dir
30 -size N[c] 512 byte blocks (c=bytes) -xdev only this filesystem
31 -links N hardlink count -atime N[u] accessed N units ago
32 -ctime N[u] created N units ago -mtime N[u] modified N units ago
33 -newer FILE newer mtime than FILE -mindepth # at least # dirs down
34 -depth ignore contents of dir -maxdepth # at most # dirs down
35 -inum N inode number N -empty empty files and dirs
36 -type [bcdflps] (block, char, dir, file, symlink, pipe, socket)
37 -context PATTERN security context
38
39 Numbers N may be prefixed by a - (less than) or + (greater than). Units for
40 -Xtime are d (days, default), h (hours), m (minutes), or s (seconds).
41
42 Combine matches with:
43 !, -a, -o, ( ) not, and, or, group expressions
44
45 Actions:
46 -print Print match with newline -print0 Print match with null
47 -exec Run command with path -execdir Run command in file's dir
48 -ok Ask before exec -okdir Ask before execdir
49 -delete Remove matching file/dir
50
51 Commands substitute "{}" with matched file. End with ";" to run each file,
52 or "+" (next argument after "{}") to collect and run with multiple files.
53 */
54
55 #define FOR_find
56 #include "toys.h"
57
58 GLOBALS(
59 char **filter;
60 struct double_list *argdata;
61 int topdir, xdev, depth;
62 time_t now;
63 long max_bytes;
64 )
65
66 struct execdir_data {
67 struct execdir_data *next;
68
69 int namecount;
70 struct double_list *names;
71 };
72
73 // None of this can go in TT because you can have more than one -exec
74 struct exec_range {
75 char *next, *prev; // layout compatible with struct double_list
76
77 int dir, plus, arglen, argsize, curly;
78 char **argstart;
79 struct execdir_data exec, *execdir;
80 };
81
82 // Perform pending -exec (if any)
flush_exec(struct dirtree * new,struct exec_range * aa)83 static int flush_exec(struct dirtree *new, struct exec_range *aa)
84 {
85 struct execdir_data *bb = aa->execdir ? aa->execdir : &aa->exec;
86 char **newargs;
87 int rc, revert = 0;
88
89 if (!bb->namecount) return 0;
90
91 dlist_terminate(bb->names);
92
93 // switch to directory for -execdir, or back to top if we have an -execdir
94 // _and_ a normal -exec, or are at top of tree in -execdir
95 if (TT.topdir != -1) {
96 if (aa->dir && new && new->parent) {
97 revert++;
98 rc = fchdir(new->parent->dirfd);
99 } else rc = fchdir(TT.topdir);
100 if (rc) {
101 perror_msg_raw(revert ? new->name : ".");
102
103 return rc;
104 }
105 }
106
107 // execdir: accumulated execs in this directory's children.
108 newargs = xmalloc(sizeof(char *)*(aa->arglen+bb->namecount+1));
109 if (aa->curly < 0) {
110 memcpy(newargs, aa->argstart, sizeof(char *)*aa->arglen);
111 newargs[aa->arglen] = 0;
112 } else {
113 int pos = aa->curly, rest = aa->arglen - aa->curly;
114 struct double_list *dl;
115
116 // Collate argument list
117 memcpy(newargs, aa->argstart, sizeof(char *)*pos);
118 for (dl = bb->names; dl; dl = dl->next) newargs[pos++] = dl->data;
119 rest = aa->arglen - aa->curly - 1;
120 memcpy(newargs+pos, aa->argstart+aa->curly+1, sizeof(char *)*rest);
121 newargs[pos+rest] = 0;
122 }
123
124 rc = xrun(newargs);
125
126 llist_traverse(bb->names, llist_free_double);
127 bb->names = 0;
128 bb->namecount = 0;
129
130 if (revert) revert = fchdir(TT.topdir);
131
132 return rc;
133 }
134
135 // Return numeric value with explicit sign
compare_numsign(long val,long units,char * str)136 static int compare_numsign(long val, long units, char *str)
137 {
138 char sign = 0;
139 long myval;
140
141 if (*str == '+' || *str == '-') sign = *(str++);
142 else if (!isdigit(*str)) error_exit("%s not [+-]N", str);
143 myval = atolx(str);
144 if (units && isdigit(str[strlen(str)-1])) myval *= units;
145
146 if (sign == '+') return val > myval;
147 if (sign == '-') return val < myval;
148 return val == myval;
149 }
150
do_print(struct dirtree * new,char c)151 static void do_print(struct dirtree *new, char c)
152 {
153 char *s=dirtree_path(new, 0);
154
155 xprintf("%s%c", s, c);
156 free(s);
157 }
158
159 // Descend or ascend -execdir + directory level
execdir(struct dirtree * new,int flush)160 static void execdir(struct dirtree *new, int flush)
161 {
162 struct double_list *dl;
163 struct exec_range *aa;
164 struct execdir_data *bb;
165
166 if (new && TT.topdir == -1) return;
167
168 for (dl = TT.argdata; dl; dl = dl->next) {
169 if (dl->prev != (void *)1) continue;
170 aa = (void *)dl;
171 if (!aa->plus || (new && !aa->dir)) continue;
172
173 if (flush) {
174
175 // Flush pending "-execdir +" instances for this dir
176 // or flush everything for -exec at top
177 toys.exitval |= flush_exec(new, aa);
178
179 // pop per-directory struct
180 if ((bb = aa->execdir)) {
181 aa->execdir = bb->next;
182 free(bb);
183 }
184 } else if (aa->dir) {
185
186 // Push new per-directory struct for -execdir/okdir + codepath. (Can't
187 // use new->extra because command line may have multiple -execdir)
188 bb = xzalloc(sizeof(struct execdir_data));
189 bb->next = aa->execdir;
190 aa->execdir = bb;
191 }
192 }
193 }
194
195 // Call this with 0 for first pass argument parsing and syntax checking (which
196 // populates argdata). Later commands traverse argdata (in order) when they
197 // need "do once" results.
do_find(struct dirtree * new)198 static int do_find(struct dirtree *new)
199 {
200 int pcount = 0, print = 0, not = 0, active = !!new, test = active, recurse;
201 struct double_list *argdata = TT.argdata;
202 char *s, **ss;
203
204 recurse = DIRTREE_COMEAGAIN|(DIRTREE_SYMFOLLOW*!!(toys.optflags&FLAG_L));
205
206 // skip . and .. below topdir, handle -xdev and -depth
207 if (new) {
208 if (new->parent) {
209 if (!dirtree_notdotdot(new)) return 0;
210 if (TT.xdev && new->st.st_dev != new->parent->st.st_dev) recurse = 0;
211 }
212
213 if (S_ISDIR(new->st.st_mode)) {
214 // Descending into new directory
215 if (!new->again) {
216 struct dirtree *n;
217
218 for (n = new->parent; n; n = n->parent) {
219 if (n->st.st_ino==new->st.st_ino && n->st.st_dev==new->st.st_dev) {
220 error_msg("'%s': loop detected", s = dirtree_path(new, 0));
221 free(s);
222
223 return 0;
224 }
225 }
226
227 if (TT.depth) {
228 execdir(new, 0);
229
230 return recurse;
231 }
232 // Done with directory (COMEAGAIN call)
233 } else {
234 execdir(new, 1);
235 recurse = 0;
236 if (!TT.depth) return 0;
237 }
238 }
239 }
240
241 // pcount: parentheses stack depth (using toybuf bytes, 4096 max depth)
242 // test: result of most recent test
243 // active: if 0 don't perform tests
244 // not: a pending ! applies to this test (only set if performing tests)
245 // print: saw one of print/ok/exec, no need for default -print
246
247 if (TT.filter) for (ss = TT.filter; *ss; ss++) {
248 int check = active && test;
249
250 s = *ss;
251
252 // handle ! ( ) using toybuf as a stack
253 if (*s != '-') {
254 if (s[1]) goto error;
255
256 if (*s == '!') {
257 // Don't invert if we're not making a decision
258 if (check) not = !not;
259
260 // Save old "not" and "active" on toybuf stack.
261 // Deactivate this parenthetical if !test
262 // Note: test value should never change while !active
263 } else if (*s == '(') {
264 if (pcount == sizeof(toybuf)) goto error;
265 toybuf[pcount++] = not+(active<<1);
266 if (!check) active = 0;
267 not = 0;
268
269 // Pop status, apply deferred not to test
270 } else if (*s == ')') {
271 if (--pcount < 0) goto error;
272 // Pop active state, apply deferred not (which was only set if checking)
273 active = (toybuf[pcount]>>1)&1;
274 if (active && (toybuf[pcount]&1)) test = !test;
275 not = 0;
276 } else goto error;
277
278 continue;
279 } else s++;
280
281 if (!strcmp(s, "xdev")) TT.xdev = 1;
282 else if (!strcmp(s, "delete")) {
283 // Delete forces depth first
284 TT.depth = 1;
285 if (new && check)
286 test = !unlinkat(dirtree_parentfd(new), new->name,
287 S_ISDIR(new->st.st_mode) ? AT_REMOVEDIR : 0);
288 } else if (!strcmp(s, "depth")) TT.depth = 1;
289 else if (!strcmp(s, "o") || !strcmp(s, "or")) {
290 if (not) goto error;
291 if (active) {
292 if (!test) test = 1;
293 else active = 0; // decision has been made until next ")"
294 }
295 } else if (!strcmp(s, "not")) {
296 if (check) not = !not;
297 continue;
298 // Mostly ignore NOP argument
299 } else if (!strcmp(s, "a") || !strcmp(s, "and") || !strcmp(s, "noleaf")) {
300 if (not) goto error;
301
302 } else if (!strcmp(s, "print") || !strcmp("print0", s)) {
303 print++;
304 if (check) do_print(new, s[5] ? 0 : '\n');
305
306 } else if (!strcmp(s, "empty")) {
307 if (check) {
308 // Alas neither st_size nor st_blocks reliably show an empty directory
309 if (S_ISDIR(new->st.st_mode)) {
310 int fd = openat(dirtree_parentfd(new), new->name, O_RDONLY);
311 DIR *dfd = fdopendir(fd);
312 struct dirent *de = (void *)1;
313 if (dfd) {
314 while ((de = readdir(dfd)) && isdotdot(de->d_name));
315 closedir(dfd);
316 }
317 if (de) test = 0;
318 } else if (S_ISREG(new->st.st_mode)) {
319 if (new->st.st_size) test = 0;
320 } else test = 0;
321 }
322 } else if (!strcmp(s, "nouser")) {
323 if (check) if (bufgetpwuid(new->st.st_uid)) test = 0;
324 } else if (!strcmp(s, "nogroup")) {
325 if (check) if (bufgetgrgid(new->st.st_gid)) test = 0;
326 } else if (!strcmp(s, "prune")) {
327 if (check && S_ISDIR(new->st.st_mode) && !TT.depth) recurse = 0;
328
329 // Remaining filters take an argument
330 } else {
331 if (!strcmp(s, "name") || !strcmp(s, "iname")
332 || !strcmp(s, "wholename") || !strcmp(s, "iwholename")
333 || !strcmp(s, "path") || !strcmp(s, "ipath"))
334 {
335 int i = (*s == 'i'), is_path = (s[i] != 'n');
336 char *arg = ss[1], *path = 0, *name = new ? new->name : arg;
337
338 // Handle path expansion and case flattening
339 if (new && is_path) name = path = dirtree_path(new, 0);
340 if (i) {
341 if ((check || !new) && name) name = strlower(name);
342 if (!new) dlist_add(&TT.argdata, name);
343 else arg = ((struct double_list *)llist_pop(&argdata))->data;
344 }
345
346 if (check) {
347 test = !fnmatch(arg, name, FNM_PATHNAME*(!is_path));
348 if (i) free(name);
349 }
350 free(path);
351 } else if (!CFG_TOYBOX_LSM_NONE && !strcmp(s, "context")) {
352 if (check) {
353 char *path = dirtree_path(new, 0), *context;
354
355 if (lsm_get_context(path, &context) != -1) {
356 test = !fnmatch(ss[1], context, 0);
357 free(context);
358 } else test = 0;
359 free(path);
360 }
361 } else if (!strcmp(s, "perm")) {
362 if (check) {
363 char *m = ss[1];
364 int match_min = *m == '-',
365 match_any = *m == '/';
366 mode_t m1 = string_to_mode(m+(match_min || match_any), 0),
367 m2 = new->st.st_mode & 07777;
368
369 if (match_min || match_any) m2 &= m1;
370 test = match_any ? !m1 || m2 : m1 == m2;
371 }
372 } else if (!strcmp(s, "type")) {
373 if (check) {
374 int types[] = {S_IFBLK, S_IFCHR, S_IFDIR, S_IFLNK, S_IFIFO,
375 S_IFREG, S_IFSOCK}, i = stridx("bcdlpfs", *ss[1]);
376
377 if (i<0) error_exit("bad -type '%c'", *ss[1]);
378 if ((new->st.st_mode & S_IFMT) != types[i]) test = 0;
379 }
380
381 } else if (strchr("acm", *s)
382 && (!strcmp(s+1, "time") || !strcmp(s+1, "min")))
383 {
384 if (check) {
385 char *copy = ss[1];
386 time_t thyme = (int []){new->st.st_atime, new->st.st_ctime,
387 new->st.st_mtime}[stridx("acm", *s)];
388 int len = strlen(copy), uu, units = (s[1]=='m') ? 60 : 86400;
389
390 if (len && -1!=(uu = stridx("dhms",tolower(copy[len-1])))) {
391 copy = xstrdup(copy);
392 copy[--len] = 0;
393 units = (int []){86400, 3600, 60, 1}[uu];
394 }
395 test = compare_numsign(TT.now - thyme, units, copy);
396 if (copy != ss[1]) free(copy);
397 }
398 } else if (!strcmp(s, "size")) {
399 if (check) test = compare_numsign(new->st.st_size, 512, ss[1]);
400 } else if (!strcmp(s, "links")) {
401 if (check) test = compare_numsign(new->st.st_nlink, 0, ss[1]);
402 } else if (!strcmp(s, "inum")) {
403 if (check) test = compare_numsign(new->st.st_ino, 0, ss[1]);
404 } else if (!strcmp(s, "mindepth") || !strcmp(s, "maxdepth")) {
405 if (check) {
406 struct dirtree *dt = new;
407 int i = 0, d = atolx(ss[1]);
408
409 while ((dt = dt->parent)) i++;
410 if (s[1] == 'i') {
411 test = i >= d;
412 if (i == d && not) recurse = 0;
413 } else {
414 test = i <= d;
415 if (i == d && !not) recurse = 0;
416 }
417 }
418 } else if (!strcmp(s, "user") || !strcmp(s, "group")
419 || !strcmp(s, "newer"))
420 {
421 struct {
422 void *next, *prev;
423 union {
424 uid_t uid;
425 gid_t gid;
426 struct timespec tm;
427 } u;
428 } *udl;
429
430 if (!new) {
431 if (ss[1]) {
432 udl = xmalloc(sizeof(*udl));
433 dlist_add_nomalloc(&TT.argdata, (void *)udl);
434
435 if (*s == 'u') udl->u.uid = xgetuid(ss[1]);
436 else if (*s == 'g') udl->u.gid = xgetgid(ss[1]);
437 else {
438 struct stat st;
439
440 xstat(ss[1], &st);
441 udl->u.tm = st.st_mtim;
442 }
443 }
444 } else {
445 udl = (void *)llist_pop(&argdata);
446 if (check) {
447 if (*s == 'u') test = new->st.st_uid == udl->u.uid;
448 else if (*s == 'g') test = new->st.st_gid == udl->u.gid;
449 else {
450 test = new->st.st_mtim.tv_sec > udl->u.tm.tv_sec;
451 if (new->st.st_mtim.tv_sec == udl->u.tm.tv_sec)
452 test = new->st.st_mtim.tv_nsec > udl->u.tm.tv_nsec;
453 }
454 }
455 }
456 } else if (!strcmp(s, "exec") || !strcmp("ok", s)
457 || !strcmp(s, "execdir") || !strcmp(s, "okdir"))
458 {
459 struct exec_range *aa;
460
461 print++;
462
463 // Initial argument parsing pass
464 if (!new) {
465 int len;
466
467 // catch "-exec" with no args and "-exec \;"
468 if (!ss[1] || !strcmp(ss[1], ";")) error_exit("'%s' needs 1 arg", s);
469
470 dlist_add_nomalloc(&TT.argdata, (void *)(aa = xzalloc(sizeof(*aa))));
471 aa->argstart = ++ss;
472 aa->curly = -1;
473
474 // Record command line arguments to -exec
475 for (len = 0; ss[len]; len++) {
476 if (!strcmp(ss[len], ";")) break;
477 else if (!strcmp(ss[len], "{}")) {
478 aa->curly = len;
479 if (ss[len+1] && !strcmp(ss[len+1], "+")) {
480 aa->plus++;
481 len++;
482 break;
483 }
484 } else aa->argsize += sizeof(char *) + strlen(ss[len]) + 1;
485 }
486 if (!ss[len]) error_exit("-exec without %s",
487 aa->curly!=-1 ? "\\;" : "{}");
488 ss += len;
489 aa->arglen = len;
490 aa->dir = !!strchr(s, 'd');
491 if (TT.topdir == -1) TT.topdir = xopenro(".");
492
493 // collect names and execute commands
494 } else {
495 char *name, *ss1 = ss[1];
496 struct execdir_data *bb;
497
498 // Grab command line exec argument list
499 aa = (void *)llist_pop(&argdata);
500 ss += aa->arglen + 1;
501
502 if (!check) goto cont;
503 // name is always a new malloc, so we can always free it.
504 name = aa->dir ? xstrdup(new->name) : dirtree_path(new, 0);
505
506 if (*s == 'o') {
507 fprintf(stderr, "[%s] %s", ss1, name);
508 if (!(test = yesno(0))) {
509 free(name);
510 goto cont;
511 }
512 }
513
514 // Add next name to list (global list without -dir, local with)
515 bb = aa->execdir ? aa->execdir : &aa->exec;
516 dlist_add(&bb->names, name);
517 bb->namecount++;
518
519 // -exec + collates and saves result in exitval
520 if (aa->plus) {
521 // Mark entry so COMEAGAIN can call flush_exec() in parent.
522 // This is never a valid pointer value for prev to have otherwise
523 // Done here vs argument parsing pass so it's after dlist_terminate
524 aa->prev = (void *)1;
525
526 // Flush if the child's environment space gets too large.
527 // Linux caps individual arguments/variables at 131072 bytes,
528 // so this counter can't wrap.
529 if ((aa->plus += sizeof(char *)+strlen(name)+1) > TT.max_bytes) {
530 aa->plus = 1;
531 toys.exitval |= flush_exec(new, aa);
532 }
533 } else test = !flush_exec(new, aa);
534 }
535
536 // Argument consumed, skip the check.
537 goto cont;
538 } else goto error;
539
540 // This test can go at the end because we do a syntax checking
541 // pass first. Putting it here gets the error message (-unknown
542 // vs -known noarg) right.
543 if (!*++ss) error_exit("'%s' needs 1 arg", --s);
544 }
545 cont:
546 // Apply pending "!" to result
547 if (active && not) test = !test;
548 not = 0;
549 }
550
551 if (new) {
552 // If there was no action, print
553 if (!print && test) do_print(new, '\n');
554
555 if (S_ISDIR(new->st.st_mode)) execdir(new, 0);
556
557 } else dlist_terminate(TT.argdata);
558
559 return recurse;
560
561 error:
562 error_exit("bad arg '%s'", *ss);
563 }
564
find_main(void)565 void find_main(void)
566 {
567 int i, len;
568 char **ss = toys.optargs;
569
570 TT.topdir = -1;
571 TT.max_bytes = sysconf(_SC_ARG_MAX) - environ_bytes();
572
573 // Distinguish paths from filters
574 for (len = 0; toys.optargs[len]; len++)
575 if (strchr("-!(", *toys.optargs[len])) break;
576 TT.filter = toys.optargs+len;
577
578 // use "." if no paths
579 if (!len) {
580 ss = (char *[]){"."};
581 len = 1;
582 }
583
584 // first pass argument parsing, verify args match up, handle "evaluate once"
585 TT.now = time(0);
586 do_find(0);
587
588 // Loop through paths
589 for (i = 0; i < len; i++)
590 dirtree_flagread(ss[i], DIRTREE_SYMFOLLOW*!!(toys.optflags&(FLAG_H|FLAG_L)),
591 do_find);
592
593 execdir(0, 1);
594
595 if (CFG_TOYBOX_FREE) {
596 close(TT.topdir);
597 llist_traverse(TT.argdata, free);
598 }
599 }
600