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