1 /* find.c - Search directories for matching files. 2 * 3 * Copyright 2014 Rob Landley <rob (at) 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) 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 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 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 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. 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 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