git.saurik.com Git - apple/libc.git/blob

1 /*

3 *

4 * @APPLE_LICENSE_HEADER_START@

5 *

6 * This file contains Original Code and/or Modifications of Original Code

7 * as defined in and that are subject to the Apple Public Source License

8 * Version 2.0 (the 'License'). You may not use this file except in

9 * compliance with the License. Please obtain a copy of the License at

10 * http://www.opensource.apple.com/apsl/ and read it before using this

11 * file.

12 *

13 * The Original Code and all software distributed under the License are

14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER

15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,

16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,

17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.

18 * Please see the License for the specific language governing rights and

19 * limitations under the License.

20 *

21 * @APPLE_LICENSE_HEADER_END@

22 */

23 /*

26 *

27 * Redistribution and use in source and binary forms, with or without

28 * modification, are permitted provided that the following conditions

29 * are met:

30 * 1. Redistributions of source code must retain the above copyright

31 * notice, this list of conditions and the following disclaimer.

32 * 2. Redistributions in binary form must reproduce the above copyright

33 * notice, this list of conditions and the following disclaimer in the

34 * documentation and/or other materials provided with the distribution.

35 * 3. Neither the name of the University nor the names of its contributors

36 * may be used to endorse or promote products derived from this software

37 * without specific prior written permission.

38 *

39 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND

40 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

41 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

42 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE

43 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL

44 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS

45 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)

46 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT

47 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY

48 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF

49 * SUCH DAMAGE.

50 */

52 /* $OpenBSD: fts.c,v 1.51 2015/09/12 13:32:24 guenther Exp $ */

54 #include <sys/param.h>

55 #include <sys/stat.h>

57 #include <dirent.h>

58 #include <errno.h>

59 #include <fcntl.h>

60 #include <fts.h>

61 #include <limits.h>

62 #include <stdlib.h>

63 #include <string.h>

64 #include <unistd.h>

65 #include <stdbool.h>

66 #include <sys/vnode.h>

67 #include <sys/attr.h>

68 #include <os/assumes.h>

70 #ifdef __BLOCKS__

71 #include <Block.h>

72 #endif /* __BLOCKS__ */

73 #include <malloc_private.h>

75 #pragma clang diagnostic push

76 #pragma clang diagnostic ignored "-Wstrict-prototypes"

 static FTSENT   *fts_alloc(FTS *, char *, ssize_t);

 static FTSENT   *fts_build(FTS *, int);

80 static void fts_lfree(FTSENT *);

 static void      fts_load(FTS *, FTSENT *);

 static size_t    fts_maxarglen(char * const *);

 static void      fts_padjust(FTS *, FTSENT *);

 static int       fts_palloc(FTS *, size_t);

 static FTSENT   *fts_sort(FTS *, FTSENT *, int);

 static u_short   fts_stat(FTS *, FTSENT *, int, int);

 static u_short   fts_stat2(FTS *, FTSENT *, int, int, struct stat *);

 static int       fts_safe_changedir(FTS *, FTSENT *, int, char *);

 #define ISDOT(a)        (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))

92 #define CLR(opt) (sp->fts_options &= ~(opt))

93 #define ISSET(opt) (sp->fts_options & (opt))

94 #define SET(opt) (sp->fts_options |= (opt))

96 #define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd))

98 /* fts_build flags */

99 #define BCHILD 1 /* fts_children */

100 #define BNAMES 2 /* fts_children, names only */

101 #define BREAD 3 /* fts_read */

102

103 /* 5653270

104 * For directories containing > 64k subdirectories (or HFS+ with > 64k files

105 * and subdirectories), struct stat's st_nlink (16 bits) will overflow. This

106 * causes the case with FTS_NOSTAT and FTS_PHYSICAL set to prematurely stop

107 * recursing into subdirectories, because of an optimization that expects

108 * st_nlink to be the number of subdirectories (once that number has been

109 * encountered, no further calls to stat should be needed).

110 *

111 * However, on Mac OS X, another optimization largely nullifies the st_nlink

112 * optimization. struct dirent contains d_type, which can distinguish

113 * directories from files without initially calling stat. So stat is only

114 * called on known directories, rather than on other files. With this

115 * optimization, the difference in also using the st_nlink optimization is

116 * pretty minimal (tests show an improvement of a percent or two, probably

117 * due to additional if statement clauses that need to be evaluated).

118 *

119 * So removing the st_nlink optimization code will fix the > 64k subdirectories

120 * problem. And if we replace the multiple if clause logic with a single

121 * switch statement, we can recover the minimal performance lose. We can

122 * go even further and for the case of FTS_NOSTAT and FTS_LOGICAL set, we

123 * can use d_type to also distinguish symbolic links, and so we only need to

124 * call stat on directories and symlinks, not on all files. This provides

125 * a significant performance boost in that special case.

126 */

127 /*

128 * The following macros defines values of the dostat variable, which is or-ed

129 * with the value of d_type, and the result used in a switch statement to

130 * determine whether to call stat or not. (We order the macros to minimize

131 * the size of any jump table that the compiler may generate.)

132 */

133 #define F_SHIFT 4 /* shift to leave space for d_type */

134 #define F_NOSTAT (0 << F_SHIFT) /* don't do any stat's */

135 #define F_STATDIRSYM (1 << F_SHIFT) /* only stat directories and symlinks (and unknowns) */

136 #define F_ALWAYSSTAT (2 << F_SHIFT) /* always stat */

137 #define F_STATDIR (3 << F_SHIFT) /* only stat directories (and unknowns) */

138 #define F_D_TYPE (4 << F_SHIFT) /* only stat directories but use d_type */

139 #define F_D_TYPESYM (5 << F_SHIFT) /* only stat directories and symlinks but use d_type */

140

141 static FTS *

 __fts_open(char * const *argv, FTS *sp)

143 {

144 FTSENT *p, *root;

145 int nitems;

146 FTSENT *parent, *tmp;

147 ssize_t len;

148

149 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */

         if (ISSET(FTS_LOGICAL))

151 SET(FTS_NOCHDIR);

152

153 /*

154 * Start out with 1K of path space, and enough, in any case,

155 * to hold the user's paths.

156 */

         if (fts_palloc(sp, MAX(fts_maxarglen(argv), PATH_MAX)))

158 goto mem1;

159

160 /* Allocate/initialize root's parent. */

         if ((parent = fts_alloc(sp, "", 0)) == NULL)

162 goto mem2;

163 parent->fts_level = FTS_ROOTPARENTLEVEL;

164

165 /* Allocate/initialize root(s). */

         for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) {

167 len = strlen(*argv);

                 if ((p = fts_alloc(sp, *argv, len)) == NULL)

169 goto mem3;

170 p->fts_level = FTS_ROOTLEVEL;

171 p->fts_parent = parent;

172 p->fts_accpath = p->fts_name;

                 p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOWDIR) ? -1 : ISSET(FTS_COMFOLLOW), -1);

174

175 /* Command-line "." and ".." are real directories. */

                 if (p->fts_info == FTS_DOT)

177 p->fts_info = FTS_D;

178

179 /*

180 * If comparison routine supplied, traverse in sorted

181 * order; otherwise traverse in the order specified.

182 */

183 if (sp->fts_compar) {

184 p->fts_link = root;

185 root = p;

186 } else {

187 p->fts_link = NULL;

188 if (root == NULL)

189 tmp = root = p;

190 else {

191 tmp->fts_link = p;

192 tmp = p;

193 }

194 }

195 }

         if (sp->fts_compar && nitems > 1)

                 root = fts_sort(sp, root, nitems);

198

199 /*

200 * Allocate a dummy pointer and make fts_read think that we've just

201 * finished the node before the root(s); set p->fts_info to FTS_INIT

202 * so that everything about the "current" node is ignored.

203 */

         if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)

205 goto mem3;

206 sp->fts_cur->fts_link = root;

207 sp->fts_cur->fts_info = FTS_INIT;

208

209 /*

210 * If using chdir(2), grab a file descriptor pointing to dot to ensure

211 * that we can get back here; this could be avoided for some paths,

212 * but almost certainly not worth the effort. Slashes, symbolic links,

213 * and ".." are all fairly nasty problems. Note, if we can't get the

214 * descriptor we run anyway, just more slowly.

215 */

         if (!ISSET(FTS_NOCHDIR) &&

             (sp->fts_rfd = open(".", O_RDONLY | O_CLOEXEC)) < 0)

218 SET(FTS_NOCHDIR);

219

         if (nitems == 0)

221 free(parent);

222

223 return (sp);

224

225 mem3: fts_lfree(root);

226 free(parent);

 mem2:   free(sp->fts_path);

228 mem1: free(sp);

229 return (NULL);

230 }

231

232 FTS *

 fts_open(char * const *argv, int options, int (*compar)())

234 {

235 FTS *sp;

236

237 /* Options check. */

238 if (options & ~FTS_OPTIONMASK) {

239 errno = EINVAL;

240 return (NULL);

241 }

         if (options & FTS_NOSTAT_TYPE) options |= FTS_NOSTAT;

243

244 /* Allocate/initialize the stream */

         if ((sp = calloc(1, sizeof(FTS))) == NULL)

246 return (NULL);

247 sp->fts_compar = compar;

248 sp->fts_options = options;

249

         return __fts_open(argv, sp);

251 }

252

253 #ifdef __BLOCKS__

254 FTS *

 fts_open_b(char * const *argv, int options, int (^compar)(const FTSENT **, const FTSENT **))

256 {

257 FTS *sp;

258

259 /* Options check. */

260 if (options & ~FTS_OPTIONMASK) {

261 errno = EINVAL;

262 return (NULL);

263 }

         if (options & FTS_NOSTAT_TYPE) options |= FTS_NOSTAT;

265

266 /* Allocate/initialize the stream */

         if ((sp = calloc(1, sizeof(FTS))) == NULL)

268 return (NULL);

         sp->fts_compar_b = (int (^)())Block_copy(compar);

270 sp->fts_options = options | FTS_BLOCK_COMPAR;

271

         return __fts_open(argv, sp);

273 }

274 #endif /* __BLOCKS__ */

275

276 static void

 fts_load(FTS *sp, FTSENT *p)

278 {

279 ssize_t len;

280 char *cp;

281

282 /*

283 * Load the stream structure for the next traversal. Since we don't

284 * actually enter the directory until after the preorder visit, set

285 * the fts_accpath field specially so the chdir gets done to the right

286 * place and the user can access the first node. From fts_open it's

287 * known that the path will fit.

288 */

         len = p->fts_pathlen = p->fts_namelen;

         memmove(sp->fts_path, p->fts_name, len + 1);

         if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {

292 len = strlen(++cp);

                 memmove(p->fts_name, cp, len + 1);

294 p->fts_namelen = len;

295 }

         p->fts_accpath = p->fts_path = sp->fts_path;

297 sp->fts_dev = p->fts_dev;

298 }

299

300 int

301 fts_close(FTS *sp)

302 {

303 FTSENT *freep, *p;

         int rfd, error = 0;

305

306 /*

307 * This still works if we haven't read anything -- the dummy structure

308 * points to the root list, so we step through to the end of the root

309 * list which has a valid parent pointer.

310 */

311 if (sp->fts_cur) {

                 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {

313 freep = p;

                         p = p->fts_link ? p->fts_link : p->fts_parent;

315 free(freep);

316 }

317 free(p);

318 }

319

320 /* Stash the original directory fd if needed. */

         rfd = ISSET(FTS_NOCHDIR) ? -1 : sp->fts_rfd;

322

323 /* Free up child linked list, sort array, path buffer, stream ptr.*/

324 if (sp->fts_child){

325 fts_lfree(sp->fts_child);

326 }

         free(sp->fts_array); sp->fts_array = NULL;

         free(sp->fts_path); sp->fts_path = NULL;

329

330 #ifdef __BLOCKS__

331 /* Free up any block pointer. */

         if (ISSET(FTS_BLOCK_COMPAR) && sp->fts_compar_b != NULL)

333 Block_release(sp->fts_compar_b);

334 #endif /* __BLOCKS__ */

335

336 /* Free up the stream pointer. */

337 free(sp);

338

339 /* Return to original directory, checking for error. */

         if (rfd != -1) {

341 int saved_errno = errno;

                 if (fchdir(rfd) != 0){

343 error = -1;

344 saved_errno = errno;

345 }

                 if (close(rfd) != 0){

347 error = -1;

348 saved_errno = errno;

349 }

350 errno = saved_errno;

351 }

352

353 return (error);

354 }

355

356 /*

357 * Special case a root of "/" so that slashes aren't appended which would

358 * cause paths to be written as "//foo".

359 */

360 #define NAPPEND(p) \

361 (p->fts_level == FTS_ROOTLEVEL && p->fts_pathlen == 1 && \

362 p->fts_path[0] == '/' ? 0 : p->fts_pathlen)

363

364 FTSENT *

365 fts_read(FTS *sp)

366 {

367 FTSENT *p, *tmp;

368 int instr;

369 char *t;

370 int saved_errno;

371

372 /* If finished or unrecoverable error, return NULL. */

         if (sp->fts_cur == NULL || ISSET(FTS_STOP))

374 return (NULL);

375

376 /* Set current node pointer. */

377 p = sp->fts_cur;

378

379 /* Save and zero out user instructions. */

380 instr = p->fts_instr;

381 p->fts_instr = FTS_NOINSTR;

382

383 /* Any type of file may be re-visited; re-stat and re-turn. */

384 if (instr == FTS_AGAIN) {

                 p->fts_info = fts_stat(sp, p, 0, -1);

386 return (p);

387 }

388

389 /*

390 * Following a symlink -- SLNONE test allows application to see

391 * SLNONE and recover. If indirecting through a symlink, have

392 * keep a pointer to current location. If unable to get that

393 * pointer, follow fails.

394 */

395 if (instr == FTS_FOLLOW &&

             (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {

                 p->fts_info = fts_stat(sp, p, 1, -1);

                 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {

399 if ((p->fts_symfd =

                             open(".", O_RDONLY | O_CLOEXEC)) < 0) {

401 p->fts_errno = errno;

402 p->fts_info = FTS_ERR;

403 } else {

404 p->fts_flags |= FTS_SYMFOLLOW;

405 }

406 }

407 return (p);

408 }

409

410 /* Directory in pre-order. */

         if (p->fts_info == FTS_D) {

412 /* If skipped or crossed mount point, do post-order visit. */

413 if (instr == FTS_SKIP ||

                     (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) {

                         if (p->fts_flags & FTS_SYMFOLLOW)

                                 (void)close(p->fts_symfd);

417 if (sp->fts_child) {

418 fts_lfree(sp->fts_child);

419 sp->fts_child = NULL;

420 }

421 p->fts_info = FTS_DP;

422 return (p);

423 }

424

425 /* Rebuild if only read the names and now traversing. */

                 if (sp->fts_child && ISSET(FTS_NAMEONLY)) {

427 CLR(FTS_NAMEONLY);

428 fts_lfree(sp->fts_child);

429 sp->fts_child = NULL;

430 }

431

432 /*

433 * Cd to the subdirectory.

434 *

435 * If have already read and now fail to chdir, whack the list

436 * to make the names come out right, and set the parent errno

437 * so the application will eventually get an error condition.

438 * Set the FTS_DONTCHDIR flag so that when we logically change

439 * directories back to the parent we don't do a chdir.

440 *

441 * If haven't read do so. If the read fails, fts_build sets

442 * FTS_STOP or the fts_info field of the node.

443 */

444 if (sp->fts_child) {

                         if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {

446 p->fts_errno = errno;

447 p->fts_flags |= FTS_DONTCHDIR;

                                 for (p = sp->fts_child; p; p = p->fts_link)

449 p->fts_accpath =

450 p->fts_parent->fts_accpath;

451 }

                 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {

                         if (ISSET(FTS_STOP))

454 return (NULL);

455 return (p);

456 }

457 p = sp->fts_child;

458 sp->fts_child = NULL;

459 goto name;

460 }

461

462 /* Move to the next node on this level. */

463 next: tmp = p;

         if ((p = p->fts_link)) {

465 free(tmp);

466

467 /*

468 * If reached the top, return to the original directory (or

469 * the root of the tree), and load the paths for the next root.

470 */

                 if (p->fts_level == FTS_ROOTLEVEL) {

                         if (FCHDIR(sp, sp->fts_rfd)) {

473 SET(FTS_STOP);

474 return (NULL);

475 }

476 fts_load(sp, p);

                         return (sp->fts_cur = p);

478 }

479

480 /*

481 * User may have called fts_set on the node. If skipped,

482 * ignore. If followed, get a file descriptor so we can

483 * get back if necessary.

484 */

                 if (p->fts_instr == FTS_SKIP) {

486 goto next;

487 }

                 if (p->fts_instr == FTS_FOLLOW) {

                         p->fts_info = fts_stat(sp, p, 1, -1);

                         if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {

491 if ((p->fts_symfd =

                                     open(".", O_RDONLY | O_CLOEXEC, 0)) < 0) {

493 p->fts_errno = errno;

494 p->fts_info = FTS_ERR;

495 } else {

496 p->fts_flags |= FTS_SYMFOLLOW;

497 }

498 }

499 p->fts_instr = FTS_NOINSTR;

500 }

501

 name:           t = sp->fts_path + NAPPEND(p->fts_parent);

503 *t++ = '/';

                 memmove(t, p->fts_name, p->fts_namelen + 1);

                 return (sp->fts_cur = p);

506 }

507

508 /* Move up to the parent node. */

509 p = tmp->fts_parent;

510 free(tmp);

511

         if (p->fts_level == FTS_ROOTPARENTLEVEL) {

513 /*

514 * Done; free everything up and set errno to 0 so the user

515 * can distinguish between error and EOF.

516 */

517 free(p);

518 errno = 0;

                 return (sp->fts_cur = NULL);

520 }

521

522 /* NUL terminate the pathname. */

         sp->fts_path[p->fts_pathlen] = '\0';

524

525 /*

526 * Return to the parent directory. If at a root node or came through

527 * a symlink, go back through the file descriptor. Otherwise, cd up

528 * one directory.

529 */

         if (p->fts_level == FTS_ROOTLEVEL) {

                 if (FCHDIR(sp, sp->fts_rfd)) {

532 SET(FTS_STOP);

533 sp->fts_cur = p;

534 return (NULL);

535 }

         } else if (p->fts_flags & FTS_SYMFOLLOW) {

                 if (FCHDIR(sp, p->fts_symfd)) {

538 saved_errno = errno;

                         (void)close(p->fts_symfd);

540 errno = saved_errno;

541 SET(FTS_STOP);

542 sp->fts_cur = p;

543 return (NULL);

544 }

                 (void)close(p->fts_symfd);

         } else if (!(p->fts_flags & FTS_DONTCHDIR) &&

             fts_safe_changedir(sp, p, -1, "..")) {

548 SET(FTS_STOP);

549 sp->fts_cur = p;

550 return (NULL);

551 }

         p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;

         return (sp->fts_cur = p);

554 }

555

556 /*

557 * Fts_set takes the stream as an argument although it's not used in this

558 * implementation; it would be necessary if anyone wanted to add global

559 * semantics to fts using fts_set. An error return is allowed for similar

560 * reasons.

561 */

562 /* ARGSUSED */

563 int

 fts_set(FTS __unused *sp, FTSENT *p, int instr)

565 {

         if (instr && instr != FTS_AGAIN && instr != FTS_FOLLOW &&

567 instr != FTS_NOINSTR && instr != FTS_SKIP) {

568 errno = EINVAL;

569 return (1);

570 }

571 p->fts_instr = instr;

572 return (0);

573 }

574

575 FTSENT *

 fts_children(FTS *sp, int instr)

577 {

578 FTSENT *p;

579 int fd;

580

         if (instr && instr != FTS_NAMEONLY) {

582 errno = EINVAL;

583 return (NULL);

584 }

585

586 /* Set current node pointer. */

587 p = sp->fts_cur;

588

589 /*

590 * Errno set to 0 so user can distinguish empty directory from

591 * an error.

592 */

593 errno = 0;

594

595 /* Fatal errors stop here. */

         if (ISSET(FTS_STOP))

597 return (NULL);

598

599 /* Return logical hierarchy of user's arguments. */

         if (p->fts_info == FTS_INIT)

601 return (p->fts_link);

602

603 /*

604 * If not a directory being visited in pre-order, stop here. Could

605 * allow FTS_DNR, assuming the user has fixed the problem, but the

606 * same effect is available with FTS_AGAIN.

607 */

         if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)

609 return (NULL);

610

611 /* Free up any previous child list. */

612 if (sp->fts_child)

613 fts_lfree(sp->fts_child);

614

615 if (instr == FTS_NAMEONLY) {

616 SET(FTS_NAMEONLY);

617 instr = BNAMES;

618 } else

619 instr = BCHILD;

620

621 /*

622 * If using chdir on a relative path and called BEFORE fts_read does

623 * its chdir to the root of a traversal, we can lose -- we need to

624 * chdir into the subdirectory, and we don't know where the current

625 * directory is, so we can't get back so that the upcoming chdir by

626 * fts_read will work.

627 */

         if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||

629 ISSET(FTS_NOCHDIR))

                 return (sp->fts_child = fts_build(sp, instr));

631

         if ((fd = open(".", O_RDONLY | O_CLOEXEC, 0)) < 0)

633 return (NULL);

         sp->fts_child = fts_build(sp, instr);

         if (fchdir(fd)) {

                 (void)close(fd);

637 return (NULL);

638 }

         (void)close(fd);

640 return (sp->fts_child);

641 }

642

 typedef struct __attribute__((packed)) __attribute__((__aligned__(4))) {

644 uint32_t length;

645

646 /* common attributes */

647 attribute_set_t attrset;

648 attrreference_t name;

649 dev_t st_dev;

650 fsobj_type_t objtype;

651 struct timespec st_birthtimespec;

652 struct timespec st_mtimespec;

653 struct timespec st_ctimespec;

654 struct timespec st_atimespec;

655 uid_t st_uid;

656 gid_t st_gid;

657 uint32_t accessmask;

658 uint32_t st_flags;

659 uint64_t st_ino;

660

661 /* non-directory attributes */

662 uint32_t st_nlink;

663 off_t allocsize;

664 uint32_t st_blksize;

665 uint32_t st_rdev;

666 off_t st_size;

667 } attrListAttributes;

668

 typedef struct __attribute__((packed)) {

670 uint32_t length;

671

672 /* common attributes */

673 attribute_set_t attrset;

674 attrreference_t name;

675 dev_t st_dev;

676 fsobj_type_t objtype;

677 uint64_t st_ino;

678

679 /* non-directory attributes */

680 uint32_t st_nlink;

681 uint32_t st_rdev;

682 } attrListAttributes_nostat;

683

684 #define ATTR_BUF_SIZE (32*1024)

685

686 typedef struct {

687 DIR *dirp;

688

689 struct attrlist requested_attrs;

690 void *attrbuf;

691 union {

692 attrListAttributes *curattr;

693 attrListAttributes_nostat *curattr_nostat;

694 };

695 int dirfd;

696 bool done;

697 bool nostat;

698 bool needs_dot;

699 bool needs_dotdot;

700

701 int entry_count;

702 int cur_entry;

703 } dir_handle;

704

705 typedef struct {

706 char *d_name;

707 size_t d_namlen;

708 struct stat sb;

709 int d_type;

710 bool stat_valid;

711 } dir_entry;

712

713 static bool

714 advance_directory(dir_handle *handle)

715 {

         if (handle->done) return true;

717

         os_assert(handle->dirfd != -1);

         handle->entry_count = getattrlistbulk(handle->dirfd, &handle->requested_attrs,

720 handle->attrbuf, ATTR_BUF_SIZE, FSOPT_PACK_INVAL_ATTRS);

         if (handle->entry_count == -1) {

722 goto error;

         } else if (handle->entry_count == 0) {

724 /* No more entries. */

725 handle->done = true;

726 }

727 handle->cur_entry = 0;

728 handle->curattr = handle->attrbuf;

729 return true;

730

731 error: {

732 int saved_errno = errno;

733 close(handle->dirfd);

734 handle->dirfd = -1;

735 errno = saved_errno;

736 return false;

737 }

738 }

739

740 static bool

 open_directory(FTS *sp, dir_handle *handle, const char *path)

742 {

         memset(handle, 0, sizeof(*handle));

744

         handle->nostat = ISSET(FTS_NOSTAT);

         handle->needs_dot = handle->needs_dotdot = ISSET(FTS_SEEDOT);

747

         handle->dirfd = open(path, O_RDONLY | O_NONBLOCK | O_DIRECTORY | O_CLOEXEC);

         if (handle->dirfd == -1) goto fallback;

750

         handle->attrbuf = malloc(ATTR_BUF_SIZE);

         if (!handle->attrbuf) goto fallback;

753

754 handle->requested_attrs.bitmapcount = ATTR_BIT_MAP_COUNT;

755 if (!handle->nostat) {

756 handle->requested_attrs.commonattr =

757 ATTR_CMN_RETURNED_ATTRS|

758 ATTR_CMN_NAME|ATTR_CMN_DEVID|ATTR_CMN_OBJTYPE|

759 ATTR_CMN_CRTIME|ATTR_CMN_MODTIME|ATTR_CMN_CHGTIME|ATTR_CMN_ACCTIME|

760 ATTR_CMN_OWNERID|ATTR_CMN_GRPID|ATTR_CMN_ACCESSMASK|ATTR_CMN_FLAGS|

761 ATTR_CMN_FILEID;

                 handle->requested_attrs.fileattr = ATTR_FILE_LINKCOUNT|ATTR_FILE_ALLOCSIZE|

763 ATTR_FILE_IOBLOCKSIZE|ATTR_FILE_DEVTYPE|ATTR_FILE_DATALENGTH;

764 } else {

765 handle->requested_attrs.commonattr = ATTR_CMN_RETURNED_ATTRS|

766 ATTR_CMN_NAME|ATTR_CMN_DEVID|ATTR_CMN_OBJTYPE|

767 ATTR_CMN_FILEID;

768 handle->requested_attrs.fileattr = ATTR_FILE_LINKCOUNT;

769 }

770

         if (advance_directory(handle)) {

772 /*

773 * We successfully read the first attribute buffer,

774 * so we'll use getdirentriesattr/getattrlistbulk.

775 */

776 return true;

777 }

778

779 fallback:

         if (handle->dirfd != -1) close(handle->dirfd);

781 handle->dirfd = -1;

782 free(handle->attrbuf);

783 handle->attrbuf = NULL;

         handle->dirp = opendir(path);

         return (handle->dirp != NULL);

786 }

787

788 static bool

 read_dirent(dir_handle *handle, dir_entry *entry)

790 {

791 if (handle->dirp) {

                 struct dirent *de = readdir(handle->dirp);

                 if (de == NULL) return false;

794 entry->d_name = de->d_name;

795 entry->d_namlen = de->d_namlen;

796 entry->d_type = de->d_type;

797 entry->stat_valid = false;

798 return true;

799 }

800

801 /*

802 * There are three states that our dir_handle can be in:

803 * - real getattrlistbulk use (entry_count >= 0) - the rest of this function

804 * - fallback - handled above with dirp

805 * - closed fallback (dirp == NULL) - handled with this check

806 */

         if (handle->dirfd == -1) {

808 return false;

809 }

810

811 if (handle->needs_dot) {

812 handle->needs_dot = false;

813 entry->d_name = ".";

                 entry->d_namlen = strlen(".");

815 entry->d_type = DT_DIR;

816 entry->stat_valid = false;

817 return true;

         } else if (handle->needs_dotdot) {

819 handle->needs_dotdot = false;

820 entry->d_name = "..";

                 entry->d_namlen = strlen("..");

822 entry->d_type = DT_DIR;

823 entry->stat_valid = false;

824 return true;

825 }

826

         if (handle->cur_entry == handle->entry_count) {

                 if (handle->done) return false;                /* Already done with the directory. */

                 if (!advance_directory(handle)) return false;  /* Reading the next buffer failed. */

                 if (handle->done) return false;                /* We're now done with the directory. */

831 }

832

         bzero(entry, sizeof(*entry));

834

835 attrListAttributes *curattr_stat = NULL;

836 attrListAttributes_nostat *curattr_nostat = NULL;

837 if (!handle->nostat) {

838 curattr_stat = handle->curattr;

839 handle->cur_entry++;

                 handle->curattr = (attrListAttributes*)(((char*)curattr_stat) + curattr_stat->length);

                 os_assert((handle->cur_entry == handle->entry_count) ||

                                 (void*)handle->curattr + handle->curattr->length <= (void*)handle->attrbuf + ATTR_BUF_SIZE);

843

                 os_assert(curattr_stat->name.attr_length > 0);

                 entry->d_name = ((char*)&curattr_stat->name) + curattr_stat->name.attr_dataoffset;

846 /* attr_length includes the null terminator, but readdir's d_namlen doesn't. */

                 entry->d_namlen = curattr_stat->name.attr_length - 1;

                 os_assert((void*)entry->d_name + curattr_stat->name.attr_length <= (void*)handle->attrbuf + ATTR_BUF_SIZE);

849 } else {

850 curattr_nostat = handle->curattr_nostat;

851 handle->cur_entry++;

                 handle->curattr_nostat = (attrListAttributes_nostat*)(((char*)curattr_nostat) + curattr_nostat->length);

                 os_assert((handle->cur_entry == handle->entry_count) ||

                                 (void*)handle->curattr + handle->curattr->length <= (void*)handle->attrbuf + ATTR_BUF_SIZE);

855

                 os_assert(curattr_nostat->name.attr_length > 0);

                 entry->d_name = ((char*)&curattr_nostat->name) + curattr_nostat->name.attr_dataoffset;

858 /* attr_length includes the null terminator, but readdir's d_namlen doesn't. */

                 entry->d_namlen = curattr_nostat->name.attr_length - 1;

                 os_assert((void*)entry->d_name + curattr_nostat->name.attr_length <= (void*)handle->attrbuf + ATTR_BUF_SIZE);

861 }

862

863 int stat_type = 0;

864

         switch (handle->nostat ? curattr_nostat->objtype : curattr_stat->objtype) {

866 case VREG:

867 entry->d_type = DT_REG;

868 stat_type = S_IFREG;

869 break;

870 case VDIR:

871 entry->d_type = DT_DIR;

872 /* Force a stat call so we don't have to guess on st_size, st_blocks, etc. */

873 // stat_type = S_IFDIR;

874 break;

875 case VBLK:

876 entry->d_type = DT_BLK;

877 stat_type = S_IFBLK;

878 break;

879 case VCHR:

880 entry->d_type = DT_CHR;

881 stat_type = S_IFCHR;

882 break;

883 case VLNK:

884 entry->d_type = DT_LNK;

885 stat_type = S_IFLNK;

886 break;

887 case VSOCK:

888 entry->d_type = DT_SOCK;

889 stat_type = S_IFSOCK;

890 break;

891 case VFIFO:

892 entry->d_type = DT_FIFO;

893 stat_type = S_IFIFO;

894 break;

895 default:

896 entry->d_type = DT_UNKNOWN;

897 break;

898 }

899

         if (!handle->nostat && stat_type) {

901 entry->stat_valid = true;

902

903 /*

904 * Make sure we got all the attributes we need to fill out a stat structure.

905 */

906

907 attrgroup_t requiredCommon = handle->requested_attrs.commonattr;

908 attrgroup_t requiredFile = handle->requested_attrs.fileattr;

909

                 if ((entry->d_type != DT_BLK) && (entry->d_type != DT_CHR)) {

911 /* It's okay for ATTR_FILE_DEVTYPE to be missing if the entry isn't a block or character device. */

912 curattr_stat->st_rdev = 0;

913 requiredFile &= ~ATTR_FILE_DEVTYPE;

914 }

915

                 if ((curattr_stat->attrset.commonattr & ATTR_CMN_CRTIME) == 0) {

917 /* Many (most?) file systems don't support create time (see vn_stat_noauth in xnu) */

                         curattr_stat->st_birthtimespec.tv_sec = curattr_stat->st_birthtimespec.tv_nsec = 0;

919 requiredCommon &= ~ ATTR_CMN_CRTIME;

920 }

921

                 if ((curattr_stat->attrset.commonattr & requiredCommon) != requiredCommon ||

                                 (curattr_stat->attrset.fileattr & requiredFile) != requiredFile) {

924 /* Some of our required attributes are missing. */

925 entry->stat_valid = false;

926 }

927 } else {

928 entry->stat_valid = false;

929 }

930

931 if (entry->stat_valid) {

932

933 #define COPY_FIELD(fld) entry->sb.fld = curattr_stat->fld

934 COPY_FIELD(st_dev);

935 /* COPY_FIELD(st_mode); Handled below. */

936 COPY_FIELD(st_nlink);

937 COPY_FIELD(st_ino);

938 COPY_FIELD(st_uid);

939 COPY_FIELD(st_gid);

940 COPY_FIELD(st_rdev);

941 COPY_FIELD(st_atimespec);

942 COPY_FIELD(st_mtimespec);

943 COPY_FIELD(st_ctimespec);

944 #if __DARWIN_64_BIT_INO_T

945 COPY_FIELD(st_birthtimespec);

946 #endif /* __DARWIN_64_BIT_INO_T */

947 COPY_FIELD(st_size);

948 /* COPY_FIELD(st_blocks); Handled below. */

949 COPY_FIELD(st_blksize);

950 COPY_FIELD(st_flags);

951 #undef COPY_FIELD

952

953 /* We have to handle some fields specially. */

                 entry->sb.st_mode = (curattr_stat->accessmask & ~S_IFMT) | stat_type;

                 entry->sb.st_blocks = howmany(curattr_stat->allocsize, 512); /* Matches vn_stat implementation in xnu. */

956 }

957 return true;

958 }

959

960 static int

961 dir_fd(dir_handle *handle)

962 {

         return handle->dirp ? dirfd(handle->dirp) : handle->dirfd;

964 }

965

966 static void

967 close_directory(dir_handle *handle)

968 {

969 if (handle->dirp) {

970 closedir(handle->dirp);

971 handle->dirp = NULL;

972 }

         if (handle->dirfd != -1) {

974 close(handle->dirfd);

975 handle->dirfd = -1;

976 }

977 free(handle->attrbuf);

978 handle->attrbuf = NULL;

979 }

980

981 /*

982 * This is the tricky part -- do not casually change *anything* in here. The

983 * idea is to build the linked list of entries that are used by fts_children

984 * and fts_read. There are lots of special cases.

985 *

986 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is

987 * set, we can use d_type to determine if the entry is a directory (or for

988 * logical walks, a directory or symlink) and not call stat for other file

989 * types. This cuts the number of stat calls significantly.

990 */

991 static FTSENT *

 fts_build(FTS *sp, int type)

993 {

994 dir_entry de = { 0 };

995 dir_entry *dp = &de;

996 FTSENT *p, *head;

997 int nitems;

998 FTSENT *cur, *tail;

999 dir_handle dirp;

1000 void *oldaddr;

1001 int len, maxlen;

         int cderrno, descend, level, dostat, doadjust;

1003 int saved_errno;

1004 char *cp;

1005

1006 /* Set current node pointer. */

1007 cur = sp->fts_cur;

1008

1009 /*

1010 * Open the directory for reading. If this fails, we're done.

1011 * If being called from fts_read, set the fts_info field.

1012 */

         if (!open_directory(sp, &dirp, cur->fts_accpath)) {

1014 if (type == BREAD) {

1015 cur->fts_info = FTS_DNR;

1016 cur->fts_errno = errno;

1017 }

1018 return (NULL);

1019 }

1020

1021 if (type == BNAMES)

1022 dostat = F_NOSTAT;

         else if (ISSET(FTS_NOSTAT_TYPE))

                 dostat = ISSET(FTS_PHYSICAL) ? F_D_TYPE : F_D_TYPESYM;

         else if (ISSET(FTS_NOSTAT))

                 dostat = ISSET(FTS_PHYSICAL) ? F_STATDIR : F_STATDIRSYM;

1027 else

1028 dostat = F_ALWAYSSTAT;

1029

1030 #ifdef notdef

         (void)printf("dostat == %d\n", dostat);

         (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",

             ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));

1034 #endif

1035 /*

1036 * If we're going to need to stat anything or we want to descend

1037 * and stay in the directory, chdir. If this fails we keep going,

1038 * but set a flag so we don't chdir after the post-order visit.

1039 * We won't be able to stat anything, but we can still return the

1040 * names themselves. Note, that since fts_read won't be able to

1041 * chdir into the directory, it will have to return different path

1042 * names than before, i.e. "a/b" instead of "b". Since the node

1043 * has already been visited in pre-order, have to wait until the

1044 * post-order visit to return the error. There is a special case

1045 * here, if there was nothing to stat then it's not an error to

1046 * not be able to stat. This is all fairly nasty. If a program

1047 * needed sorted entries or stat information, they had better be

1048 * checking FTS_NS on the returned nodes.

1049 */

1050 cderrno = 0;

         if (dostat || type == BREAD) {

                 if (fts_safe_changedir(sp, cur, dir_fd(&dirp), NULL)) {

                         if (dostat && type == BREAD) {

1054 cur->fts_errno = errno;

1055 }

1056 cur->fts_flags |= FTS_DONTCHDIR;

1057 descend = 0;

1058 cderrno = errno;

1059 close_directory(&dirp);

1060 } else {

1061 descend = 1;

1062 }

1063 } else {

1064 descend = 0;

1065 }

1066

1067 /*

1068 * Figure out the max file name length that can be stored in the

1069 * current path -- the inner loop allocates more path as necessary.

1070 * We really wouldn't have to do the maxlen calculations here, we

1071 * could do them in fts_read before returning the path, but it's a

1072 * lot easier here since the length is part of the dirent structure.

1073 *

1074 * If not changing directories set a pointer so that can just append

1075 * each new name into the path.

1076 */

1077 len = NAPPEND(cur);

         if (ISSET(FTS_NOCHDIR)) {

1079 cp = sp->fts_path + len;

1080 *cp++ = '/';

1081 }

1082 len++;

1083 maxlen = sp->fts_pathlen - len;

1084

1085 /*

1086 * fts_level is signed so we must prevent it from wrapping

1087 * around to FTS_ROOTLEVEL and FTS_ROOTPARENTLEVEL.

1088 */

1089 level = cur->fts_level;

1090 if (level < FTS_MAXLEVEL)

1091 level++;

1092

1093 /* Read the directory, attaching each entry to the `link' pointer. */

1094 doadjust = 0;

         for (head = tail = NULL, nitems = 0; read_dirent(&dirp, dp) ; ) {

                 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))

1097 continue;

1098

                 if ((p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen)) == NULL)

1100 goto mem1;

                 if (dp->d_namlen >= (size_t)maxlen) {   /* include space for NUL */

1102 oldaddr = sp->fts_path;

                         if (fts_palloc(sp, dp->d_namlen +len + 1)) {

1104 /*

1105 * No more memory for path or structures. Save

1106 * errno, free up the current structure and the

1107 * structures already allocated.

1108 */

1109 mem1: saved_errno = errno;

1110 free(p);

1111 fts_lfree(head);

1112 close_directory(&dirp);

1113 cur->fts_info = FTS_ERR;

1114 SET(FTS_STOP);

1115 errno = saved_errno;

1116 return (NULL);

1117 }

1118 /* Did realloc() change the pointer? */

                         if (oldaddr != sp->fts_path) {

1120 doadjust = 1;

                                 if (ISSET(FTS_NOCHDIR))

1122 cp = sp->fts_path + len;

1123 }

1124 maxlen = sp->fts_pathlen - len;

1125 }

1126

                 if (len + dp->d_namlen >= USHRT_MAX) {

1128 /*

1129 * In an FTSENT, fts_pathlen is a u_short so it is

1130 * possible to wraparound here. If we do, free up

1131 * the current structure and the structures already

1132 * allocated, then error out with ENAMETOOLONG.

1133 */

1134 free(p);

1135 fts_lfree(head);

1136 close_directory(&dirp);

1137 cur->fts_info = FTS_ERR;

1138 SET(FTS_STOP);

1139 errno = ENAMETOOLONG;

1140 return (NULL);

1141 }

1142 p->fts_level = level;

1143 p->fts_parent = sp->fts_cur;

                 p->fts_pathlen = len + dp->d_namlen;

1145

1146 if (cderrno) {

1147 if (dostat) {

1148 p->fts_info = FTS_NS;

1149 p->fts_errno = cderrno;

1150 } else

1151 p->fts_info = FTS_NSOK;

1152 p->fts_accpath = cur->fts_accpath;

1153 } else {

1154 /*

1155 * We need to know all file types values that d_type may

1156 * be set to. So if that changes, the following needs

1157 * to be modified appropriately.

1158 */

                         switch(dostat | dp->d_type) {

1160 case (F_STATDIR | DT_UNKNOWN):

1161 case (F_STATDIR | DT_DIR):

1162 case (F_STATDIRSYM | DT_UNKNOWN):

1163 case (F_STATDIRSYM | DT_DIR):

1164 case (F_STATDIRSYM | DT_LNK):

1165 case (F_ALWAYSSTAT | DT_UNKNOWN):

1166 case (F_ALWAYSSTAT | DT_FIFO):

1167 case (F_ALWAYSSTAT | DT_CHR):

1168 case (F_ALWAYSSTAT | DT_DIR):

1169 case (F_ALWAYSSTAT | DT_BLK):

1170 case (F_ALWAYSSTAT | DT_REG):

1171 case (F_ALWAYSSTAT | DT_LNK):

1172 case (F_ALWAYSSTAT | DT_SOCK):

1173 case (F_ALWAYSSTAT | DT_WHT):

1174 case (F_D_TYPE | DT_UNKNOWN):

1175 case (F_D_TYPE | DT_DIR):

1176 case (F_D_TYPESYM | DT_UNKNOWN):

1177 case (F_D_TYPESYM | DT_DIR):

1178 case (F_D_TYPESYM | DT_LNK):

1179 /* Build a file name for fts_stat to stat. */

                                 if (ISSET(FTS_NOCHDIR)) {

1181 p->fts_accpath = p->fts_path;

                                         memmove(cp, p->fts_name, p->fts_namelen + 1);

                                         p->fts_info = fts_stat2(sp, p, 0, dir_fd(&dirp), dp->stat_valid ? &dp->sb : NULL);

1184 } else {

1185 p->fts_accpath = p->fts_name;

                                         p->fts_info = fts_stat2(sp, p, 0, -1, dp->stat_valid ? &dp->sb : NULL);

1187 }

1188 break;

1189 case (F_D_TYPE | DT_FIFO):

1190 case (F_D_TYPE | DT_CHR):

1191 case (F_D_TYPE | DT_BLK):

1192 case (F_D_TYPE | DT_SOCK):

1193 case (F_D_TYPESYM | DT_FIFO):

1194 case (F_D_TYPESYM | DT_CHR):

1195 case (F_D_TYPESYM | DT_BLK):

1196 case (F_D_TYPESYM | DT_SOCK):

1197 p->fts_info = FTS_DEFAULT;

1198 goto common_no_stat;

1199 case (F_D_TYPE | DT_REG):

1200 case (F_D_TYPESYM | DT_REG):

1201 p->fts_info = FTS_F;

1202 goto common_no_stat;

1203 case (F_D_TYPE | DT_LNK):

1204 p->fts_info = FTS_SL;

1205 goto common_no_stat;

1206 case (F_D_TYPE | DT_WHT):

1207 case (F_D_TYPESYM | DT_WHT):

1208 p->fts_info = FTS_W;

1209 goto common_no_stat;

1210 default:

1211 /* No stat necessary */

1212 p->fts_info = FTS_NSOK;

1213 common_no_stat:

1214 p->fts_accpath =

                                     ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;

1216 break;

1217 }

1218 }

1219

1220 /* We walk in directory order so "ls -f" doesn't get upset. */

1221 p->fts_link = NULL;

1222 if (head == NULL)

1223 head = tail = p;

1224 else {

1225 tail->fts_link = p;

1226 tail = p;

1227 }

1228 ++nitems;

1229 }

1230 close_directory(&dirp);

1231

1232 /*

1233 * If realloc() changed the address of the path, adjust the

1234 * addresses for the rest of the tree and the dir list.

1235 */

1236 if (doadjust)

1237 fts_padjust(sp, head);

1238

1239 /*

1240 * If not changing directories, reset the path back to original

1241 * state.

1242 */

         if (ISSET(FTS_NOCHDIR)) {

                 if (len == sp->fts_pathlen || nitems == 0)

1245 --cp;

1246 *cp = '\0';

1247 }

1248

1249 /*

1250 * If descended after called from fts_children or after called from

1251 * fts_read and nothing found, get back. At the root level we use

1252 * the saved fd; if one of fts_open()'s arguments is a relative path

1253 * to an empty directory, we wind up here with no other way back. If

1254 * can't get back, we're done.

1255 */

         if (descend && (type == BCHILD || !nitems) &&

             (cur->fts_level == FTS_ROOTLEVEL ? FCHDIR(sp, sp->fts_rfd) :

             fts_safe_changedir(sp, cur, -1, ".."))) {

1259 cur->fts_info = FTS_ERR;

1260 SET(FTS_STOP);

1261 return (NULL);

1262 }

1263

1264 /* If didn't find anything, return NULL. */

1265 if (!nitems) {

1266 if (type == BREAD)

1267 cur->fts_info = FTS_DP;

1268 return (NULL);

1269 }

1270

1271 /* Sort the entries. */

         if (sp->fts_compar && nitems > 1)

                 head = fts_sort(sp, head, nitems);

1274 return (head);

1275 }

1276

1277 static u_short

 fts_stat(FTS *sp, FTSENT *p, int follow, int dfd)

1279 {

         return fts_stat2(sp, p, follow, dfd, NULL);

1281 }

1282

1283 static u_short

 fts_stat2(FTS *sp, FTSENT *p, int follow, int dfd, struct stat *insb)

1285 {

1286 FTSENT *t;

1287 dev_t dev;

1288 ino_t ino;

1289 struct stat *sbp, sb;

1290 int saved_errno;

1291 const char *path;

1292

         if (dfd == -1) {

1294 path = p->fts_accpath;

1295 dfd = AT_FDCWD;

1296 } else {

1297 path = p->fts_name;

1298 }

1299

1300 /* If user needs stat info, stat buffer already allocated. */

         sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;

1302

1303 /*

1304 * getattrlistbulk always returns information about the link, not its

1305 * destination, so if we are doing a logical walk we need to detect links

1306 * and do a stat anyway.

1307 */

1308 if (follow) {

1309 insb = NULL;

         } else if (insb && ISSET(FTS_LOGICAL) && ((insb->st_mode & S_IFLNK) == S_IFLNK)) {

1311 insb = NULL;

1312 }

1313

1314 if (insb) {

                 memcpy(sbp, insb, sizeof(*insb));

         } else if (ISSET(FTS_LOGICAL) || follow) {

1317 /*

1318 * If doing a logical walk, or application requested FTS_FOLLOW, do

1319 * a stat(2). If that fails, check for a non-existent symlink. If

1320 * fail, set the errno from the stat call.

1321 */

                 if (fstatat(dfd, path, sbp, 0)) {

1323 saved_errno = errno;

                         if (!fstatat(dfd, path, sbp, AT_SYMLINK_NOFOLLOW)) {

1325 if (saved_errno == ELOOP)

1326 p->fts_errno = ELOOP;

1327 errno = 0;

1328 return (FTS_SLNONE);

1329 }

1330 p->fts_errno = saved_errno;

1331 goto err;

1332 }

1333 /*

1334 * For FTS_COMFOLLOWDIR, drop back to lstat unless we have

1335 * a directory

1336 */

                 if (follow == -1 && !S_ISDIR(sbp->st_mode)) {

                         if (fstatat(dfd, path, sbp, AT_SYMLINK_NOFOLLOW)) {

1339 p->fts_errno = errno;

1340 goto err;

1341 }

1342 }

         } else if (fstatat(dfd, path, sbp, AT_SYMLINK_NOFOLLOW)) {

1344 p->fts_errno = errno;

 err:            memset(sbp, 0, sizeof(struct stat));

1346 return (FTS_NS);

1347 }

1348

         if (S_ISDIR(sbp->st_mode)) {

1350 /*

1351 * Set the device/inode. Used to find cycles and check for

1352 * crossing mount points. Also remember the link count, used

1353 * in fts_build to limit the number of stat calls. It is

1354 * understood that these fields are only referenced if fts_info

1355 * is set to FTS_D.

1356 */

                 dev = p->fts_dev = sbp->st_dev;

                 ino = p->fts_ino = sbp->st_ino;

1359 p->fts_nlink = sbp->st_nlink;

1360

                 if (ISDOT(p->fts_name))

1362 return (FTS_DOT);

1363

1364 /*

1365 * Cycle detection is done by brute force when the directory

1366 * is first encountered. If the tree gets deep enough or the

1367 * number of symbolic links to directories is high enough,

1368 * something faster might be worthwhile.

1369 */

                 for (t = p->fts_parent;

                     t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)

                         if (ino == t->fts_ino && dev == t->fts_dev) {

1373 p->fts_cycle = t;

1374 return (FTS_DC);

1375 }

1376 return (FTS_D);

1377 }

         if (S_ISLNK(sbp->st_mode))

1379 return (FTS_SL);

         if (S_ISREG(sbp->st_mode))

1381 return (FTS_F);

1382 return (FTS_DEFAULT);

1383 }

1384

1385 static FTSENT *

 fts_sort(FTS *sp, FTSENT *head, int nitems)

1387 {

1388 FTSENT **ap, *p;

1389

1390 /*

1391 * Construct an array of pointers to the structures and call qsort(3).

1392 * Reassemble the array in the order returned by qsort. If unable to

1393 * sort for memory reasons, return the directory entries in their

1394 * current order. Allocate enough space for the current needs plus

1395 * 40 so don't realloc one entry at a time.

1396 */

         if (nitems > sp->fts_nitems) {

1398 struct _ftsent **a;

1399

                 sp->fts_nitems = nitems + 40;

                 if ((a = reallocarray(sp->fts_array,

                     sp->fts_nitems, sizeof(FTSENT *))) == NULL) {

1403 free(sp->fts_array);

1404 sp->fts_array = NULL;

1405 sp->fts_nitems = 0;

1406 return (head);

1407 }

1408 sp->fts_array = a;

1409 }

         for (ap = sp->fts_array, p = head; p; p = p->fts_link)

1411 *ap++ = p;

1412 #ifdef __BLOCKS__

         if (ISSET(FTS_BLOCK_COMPAR))

                 qsort_b((void *)sp->fts_array, nitems, sizeof(FTSENT *), (int (^)(const void *, const void *))sp->fts_compar_b);

1415 else

1416 #endif /* __BLOCKS__ */

                 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar);

         for (head = *(ap = sp->fts_array); --nitems; ++ap)

                 ap[0]->fts_link = ap[1];

         ap[0]->fts_link = NULL;

1421 return (head);

1422 }

1423

1424 static FTSENT *

 fts_alloc(FTS *sp, char *name, ssize_t namelen)

1426 {

1427 FTSENT *p;

1428 size_t len;

1429

1430 /*

1431 * The file name is a variable length array and no stat structure is

1432 * necessary if the user has set the nostat bit. Allocate the FTSENT

1433 * structure, the file name and the stat structure in one chunk, but

1434 * be careful that the stat structure is reasonably aligned. Since the

1435 * fts_name field is declared to be of size 1, the fts_name pointer is

1436 * namelen + 2 before the first possible address of the stat structure.

1437 */

         len = sizeof(FTSENT) + namelen;

         if (!ISSET(FTS_NOSTAT))

                 len += sizeof(struct stat) + ALIGNBYTES;

         if ((p = calloc(1, len)) == NULL)

1442 return (NULL);

1443

1444 p->fts_path = sp->fts_path;

1445 p->fts_namelen = namelen;

1446 p->fts_instr = FTS_NOINSTR;

         if (!ISSET(FTS_NOSTAT))

                 p->fts_statp = (struct stat *)ALIGN(p->fts_name + namelen + 2);

         memcpy(p->fts_name, name, namelen);

1450

1451 return (p);

1452 }

1453

1454 static void

1455 fts_lfree(FTSENT *head)

1456 {

1457 FTSENT *p;

1458

1459 /* Free a linked list of structures. */

1460 while ((p = head)) {

1461 head = head->fts_link;

1462 free(p);

1463 }

1464 }

1465

1466 /*

1467 * Allow essentially unlimited paths; find, rm, ls should all work on any tree.

1468 * Most systems will allow creation of paths much longer than PATH_MAX, even

1469 * though the kernel won't resolve them. Add the size (not just what's needed)

1470 * plus 256 bytes so don't realloc the path 2 bytes at a time.

1471 */

1472 static int

 fts_palloc(FTS *sp, size_t more)

1474 {

1475 char *p;

1476

         sp->fts_pathlen += more + 256;

1478 /*

1479 * Check for possible wraparound. In an FTS, fts_pathlen is

1480 * a signed int but in an FTSENT it is an unsigned short.

1481 * We limit fts_pathlen to USHRT_MAX to be safe in both cases.

1482 */

         if (sp->fts_pathlen < 0 || sp->fts_pathlen >= USHRT_MAX) {

1484 free(sp->fts_path);

1485 sp->fts_path = NULL;

1486 errno = ENAMETOOLONG;

1487 return (1);

1488 }

         p = realloc(sp->fts_path, sp->fts_pathlen);

1490 if (p == NULL) {

1491 free(sp->fts_path);

1492 sp->fts_path = NULL;

1493 return (1);

1494 }

1495 sp->fts_path = p;

1496 return (0);

1497 }

1498

1499 /*

1500 * When the path is realloc'd, have to fix all of the pointers in structures

1501 * already returned.

1502 */

1503 static void

 fts_padjust(FTS *sp, FTSENT *head)

1505 {

1506 FTSENT *p;

         char *addr = sp->fts_path;

1508

1509 #define ADJUST(p) { \

1510 if ((p)->fts_accpath != (p)->fts_name) { \

1511 (p)->fts_accpath = \

1512 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \

1513 } \

1514 (p)->fts_path = addr; \

1515 }

1516 /* Adjust the current set of children. */

         for (p = sp->fts_child; p; p = p->fts_link)

1518 ADJUST(p);

1519

1520 /* Adjust the rest of the tree, including the current level. */

         for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {

1522 ADJUST(p);

                 p = p->fts_link ? p->fts_link : p->fts_parent;

1524 }

1525 }

1526

1527 static size_t

 fts_maxarglen(char * const *argv)

1529 {

1530 size_t len, max;

1531

         for (max = 0; *argv; ++argv)

                 if ((len = strlen(*argv)) > max)

1534 max = len;

         return (max + 1);

1536 }

1537

1538 /*

1539 * Change to dir specified by fd or p->fts_accpath without getting

1540 * tricked by someone changing the world out from underneath us.

1541 * Assumes p->fts_dev and p->fts_ino are filled in.

1542 */

1543 static int

 fts_safe_changedir(FTS *sp, FTSENT *p, int fd, char *path)

1545 {

1546 int ret, oerrno, newfd;

1547 struct stat sb;

1548

1549 newfd = fd;

         if (ISSET(FTS_NOCHDIR))

1551 return (0);

         if (fd < 0 && (newfd = open(path, O_RDONLY|O_DIRECTORY|O_CLOEXEC)) < 0)

1553 return (-1);

         if (fstat(newfd, &sb)) {

1555 ret = -1;

1556 goto bail;

1557 }

1558 /*

1559 * On Darwin this check causes us to not correctly descend into automounts,

1560 * since the mount point and trigger will have a different devices and

1561 * inodes. It would be preferable to find a way to use

1562 * ATTR_DIR_MOUNTSTATUS and DIR_MNTSTATUS_TRIGGER to detect these cases,

1563 * but plumbing that through will be challenging. Instead, will just

1564 * disable it for now.

1565 */

1566 #if 0

         if (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) {

1568 errno = ENOENT; /* disinformation */

1569 ret = -1;

1570 goto bail;

1571 }

1572 #endif

1573

         if (fd != -1) {

1575 // Going down

1576 struct stat csb;

                 int cfd =  open(".", O_RDONLY | O_CLOEXEC);

                 if (cfd < 0) {

1579 ret = -1;

1580 goto bail;

                 } else if (fstat(cfd, &csb)) {

1582 oerrno = errno;

                         (void)close(cfd);

1584 errno = oerrno;

1585 ret = -1;

1586 goto bail;

1587 } else {

                         if (sb.st_dev != csb.st_dev) {

1589 // Changed device, so we'll need to track the fd of the current

1590 // directory

1591 p->fts_symfd = cfd;

1592 p->fts_flags |= FTS_CHDIRFD;

1593 } else {

1594 // Same device so assume open("..") will work

                                 (void)close(cfd);

1596 }

1597 }

         } else if (fd == -1 && strcmp(path, "..") == 0) {

1599 // Going up

                 if (p->fts_flags & FTS_CHDIRFD) {

1601 // If FTS_CHDIRFD is set, use the stashed fd to follow ".."

                         (void)close(newfd);

1603 newfd = p->fts_symfd;

1604 p->fts_symfd = 0;

1605 p->fts_flags &= ~FTS_CHDIRFD;

1606 }

1607 }

1608

1609 ret = fchdir(newfd);

1610 bail:

1611 oerrno = errno;

         if (fd < 0)

                 (void)close(newfd);

1614 errno = oerrno;

1615 return (ret);

1616 }

1617 #pragma clang diagnostic pop