libdarwin/dirstat.c

   1 /*
   2  * Copyright (c) 2017 Apple Inc. All rights reserved.
   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
  24 #include <strings.h>
  25 #include <stddef.h>
  26 #include <stdlib.h>
  27 #include <stdio.h>
  28 #include <fcntl.h>
  29 #include <unistd.h>
  30 #include <sys/fsctl.h>
  31 #include <sys/vnode.h>
  32 #include <sys/errno.h>
  33
  34 #include <os/assumes.h>
  35
  36 #include <TargetConditionals.h>
  37
  38 #include "dirstat.h"
  39 #include "dirstat_collection.h"
  40
  41 #if !TARGET_OS_SIMULATOR
  42 #define HAS_APFS
  43 #endif
  44
  45 #ifdef HAS_APFS
  46 #include <apfs/apfs_fsctl.h>
  47 #endif
  48
  49 #if DEBUG
  50 #define DEBUGPRINT(...) fprintf(stderr, __VA_ARGS__)
  51 #else
  52 #define DEBUGPRINT(...) do { } while(0)
  53 #endif
  54
  55 static int
  56 fdirstat_fallback(int fd, int flags, struct dirstat *ds);
  57
  58 #ifdef HAS_APFS
  59 static int
  60 fdirstat(int fd, int flags, struct dirstat *ds)
  61 {
  62         struct apfs_dir_stats_ext dstats = {0};
  63         if (flags & DIRSTAT_FAST_ONLY) {
  64                 dstats.flags |= APFS_DIR_STATS_FAST_PATH;
  65         }
  66
  67         int err = ffsctl(fd, APFSIOC_GET_DIR_STATS_EXT, &dstats, 0);
  68         if (err == -1) {
  69                 if (errno == ENOENT) {
  70                         // <rdar://problem/31696225>
  71                         errno = ENOTSUP;
  72                 }
  73                 return -1;
  74         }
  75
  76         ds->total_size = dstats.total_size;
  77         ds->descendants = dstats.num_children;
  78
  79         return 0;
  80 }
  81 #endif
  82
  83 int
  84 dirstatat_np(int dfd, const char *path, int flags, struct dirstat *ds_out, size_t ds_size)
  85 {
  86 #ifdef HAS_APFS
  87         // <rdar://problem/32794924>
  88         // Until APFS directory sizing is fixed, only the fallback path is
  89         // available.
  90         flags |= DIRSTAT_FORCE_FALLBACK;
  91
  92         // FORCE_FALLBACK trumps FAST_ONLY.  Make sure to set errno accordingly in
  93         // the case that a confused caller asks for both.
  94         if ((flags & (DIRSTAT_FAST_ONLY)) && (flags & DIRSTAT_FORCE_FALLBACK)) {
  95                 errno = ENOTSUP;
  96                 return -1;
  97         }
  98 #endif
  99
 100         int fd = openat(dfd, path, O_RDONLY | O_DIRECTORY);
 101         DEBUGPRINT("Opened %d:%s as %d\n", dfd, path, fd);
 102         if (fd == -1) return -1;
 103
 104         struct dirstat ds = {};
 105         int ret = -1;
 106
 107 #ifdef HAS_APFS
 108         if (!(flags & DIRSTAT_FORCE_FALLBACK)) {
 109                 ret = fdirstat(fd, flags, &ds);
 110         }
 111
 112         if (ret == -1 && ((flags & DIRSTAT_FORCE_FALLBACK) || ((errno == ENOTTY) && !(flags & DIRSTAT_FAST_ONLY)))) {
 113                 ret = fdirstat_fallback(fd, flags, &ds);
 114         }
 115 #else
 116         ret = fdirstat_fallback(fd, flags, &ds);
 117 #endif
 118         int saved_errno = errno;
 119
 120         if (ds_size >= sizeof(ds)) {
 121                 memcpy(ds_out, &ds, sizeof(ds));
 122         } else {
 123                 memcpy(ds_out, &ds, ds_size);
 124         }
 125
 126         close(fd);
 127
 128         errno = saved_errno;
 129         return ret;
 130 }
 131
 132 int
 133 dirstat_np(const char *path, int flags, struct dirstat *ds, size_t ds_size)
 134 {
 135         return dirstatat_np(AT_FDCWD, path, flags, ds, ds_size);
 136 }
 137
 138 #pragma mark Fallback
 139
 140 struct dirqueue_entry {
 141         STAILQ_ENTRY(dirqueue_entry) entries;
 142         char *path;
 143 };
 144
 145 static int
 146 fdirstat_fallback(int parent_fd, int flags, struct dirstat *ds)
 147 {
 148         int reterror = 0;
 149
 150         /*
 151          * This method of gathering disk usage is the fastest by far over other
 152          * methods using fts or opendir/readdir + getattrlist or stat to gather
 153          * information about filesystem usage.  That's because this method avoids
 154          * creating vnodes for each item in a directory.  We implement a recursive
 155          * filesystem search by appending each directory child found to a
 156          * processing queue, and then process each child directory in that queue on
 157          * a FIFO basis resulting in a breadth-first traversal of the filesystem.
 158          * This keeps our actual implementation iterative to avoid deep filesystem
 159          * hierarchies overflowing our stack.
 160          */
 161
 162         dirstat_fileid_set_t fileid_seen = _dirstat_fileid_set_create();
 163         STAILQ_HEAD(, dirqueue_entry) dirqueue_head = STAILQ_HEAD_INITIALIZER(dirqueue_head);
 164
 165         struct attrlist attrlist = {
 166                 .bitmapcount = ATTR_BIT_MAP_COUNT,
 167                 .commonattr =  ATTR_CMN_RETURNED_ATTRS | ATTR_CMN_ERROR |
 168                                 ATTR_CMN_NAME | ATTR_CMN_OBJTYPE | ATTR_CMN_FILEID,
 169                 .dirattr = ATTR_DIR_ENTRYCOUNT,
 170                 .fileattr = ATTR_FILE_LINKCOUNT | ATTR_FILE_ALLOCSIZE |
 171                                 ATTR_FILE_DATAALLOCSIZE,
 172         };
 173
 174         typedef struct {
 175                 /*
 176                  * fields are in order of possible return in buffer (but note that data
 177                  * is packed in the actual buffer, and only relevant fields are
 178                  * returned)
 179                  */
 180                 uint32_t length;
 181                 attribute_set_t returned;       //ATTR_CMN_RETURNED_ATTRS
 182                 uint32_t error;                 //ATTR_CMN_ERROR
 183                 attrreference_t item_name_info; //ATTR_CMN_NAME
 184                 fsobj_type_t type;              //ATTR_CMN_OBJTYPE
 185                 uint64_t fileid;                //ATTR_CMN_FILEID
 186                 union {
 187                         struct {
 188                                 u_int32_t entry_count;  //ATTR_DIR_ENTRYCOUNT
 189                         };
 190                         struct {
 191                                 u_int32_t link_count;   //ATTR_FILE_LINKCOUNT
 192                                 off_t alloc_size;       //ATTR_FILE_ALLOCSIZE
 193                                 off_t data_alloc_size;  //ATTR_FILE_DATAALLOCSIZE
 194                         };
 195                 };
 196         } max_attr_entry_t;
 197
 198         size_t attrbuf_len = (32 * 1024);
 199         char *attrbuf = alloca(attrbuf_len);
 200
 201 #ifdef HAS_APFS
 202         os_assert(!(flags & DIRSTAT_FAST_ONLY));
 203 #endif
 204
 205         do {
 206                 int fd = -1;
 207                 char *path;
 208
 209                 if (STAILQ_EMPTY(&dirqueue_head)) {
 210                         fd = parent_fd;
 211                         path = NULL;
 212                 } else {
 213                         struct dirqueue_entry *dqe = STAILQ_FIRST(&dirqueue_head);
 214                         STAILQ_REMOVE_HEAD(&dirqueue_head, entries);
 215                         path = dqe->path;
 216                         free(dqe);
 217
 218                         fd = openat(parent_fd, path, O_RDONLY | O_DIRECTORY);
 219
 220                         if (fd < 0) {
 221                                 DEBUGPRINT( "Unable to open directory %d:%s => %s\n", parent_fd, path, strerror(errno));
 222                                 continue;
 223                         }
 224                 }
 225
 226                 while (1) {
 227                         int ret_entry_count = getattrlistbulk(fd, &attrlist, attrbuf, attrbuf_len, 0);
 228                         if (-1 == ret_entry_count) {
 229                                 if (fd == parent_fd) {
 230                                         reterror = errno;
 231                                 }
 232                                 DEBUGPRINT( "getattrlistbulk on in %s returned error %s\n", path, strerror(errno));
 233                                 break;
 234                         } else if (0 == ret_entry_count) {
 235                                 break;
 236                         } else {
 237                                 char *cursor = NULL; //pointer into attrbuf
 238                                 char *entry_start = attrbuf;
 239
 240                                 for (int index = 0; index < ret_entry_count; index++) {
 241                                         max_attr_entry_t attrs = {0};
 242                                         char *name = NULL;
 243
 244                                         cursor = entry_start;
 245
 246                                         memcpy(&attrs.length, cursor, sizeof(attrs.length));
 247                                         cursor += sizeof(attrs.length);
 248
 249                                         /* set starting point for next entry */
 250                                         entry_start += attrs.length;
 251
 252                                         memcpy(&attrs.returned, cursor, sizeof(attrs.returned));
 253                                         cursor += sizeof(attrs.returned);
 254
 255                                         if (attrs.returned.commonattr & ATTR_CMN_ERROR) {
 256                                                 memcpy(&attrs.error, cursor, sizeof(attrs.error));
 257                                                 cursor += sizeof(attrs.error);
 258                                         }
 259
 260                                         if (attrs.error) {
 261                                                 DEBUGPRINT( "Got error %s while processing in %s\n", strerror(errno), path);
 262                                                 continue;
 263                                         }
 264
 265                                         if (attrs.returned.commonattr & ATTR_CMN_NAME) {
 266                                                 memcpy(&attrs.item_name_info, cursor, sizeof(attrs.item_name_info));
 267                                                 name = cursor + attrs.item_name_info.attr_dataoffset;
 268                                                 if (name + attrs.item_name_info.attr_length > entry_start) {
 269                                                         name = NULL;
 270                                                 }
 271                                                 cursor += sizeof(attrs.item_name_info);
 272                                         }
 273
 274                                         if (attrs.returned.commonattr & ATTR_CMN_OBJTYPE) {
 275                                                 memcpy(&attrs.type, cursor, sizeof(attrs.type));
 276                                                 cursor += sizeof(attrs.type);
 277                                         }
 278
 279                                         if (attrs.returned.commonattr & ATTR_CMN_FILEID) {
 280                                                 memcpy(&attrs.fileid, cursor, sizeof(attrs.fileid));
 281                                                 cursor += sizeof(attrs.fileid);
 282                                         }
 283
 284                                         if (VDIR == attrs.type) {
 285                                                 if (attrs.returned.dirattr & ATTR_DIR_ENTRYCOUNT) {
 286                                                         memcpy(&attrs.entry_count, cursor, sizeof(attrs.entry_count));
 287                                                         cursor += sizeof(attrs.entry_count);
 288                                                 } else {
 289                                                         // Fake it so we go down the right path below
 290                                                         attrs.entry_count = -1;
 291                                                 }
 292
 293                                                 // avoid descending into empty directories
 294                                                 if (attrs.entry_count && name) {
 295                                                         struct dirqueue_entry *dqe = malloc(sizeof(struct dirqueue_entry));
 296                                                         if (path == NULL) {
 297                                                                 dqe->path = strdup(name);
 298                                                         } else {
 299                                                                 asprintf(&dqe->path, "%s/%s", path, name);
 300                                                         }
 301
 302                                                         if (dqe->path != NULL) {
 303                                                                 STAILQ_INSERT_TAIL(&dirqueue_head, dqe, entries);
 304                                                         } else {
 305                                                                 DEBUGPRINT( "Unable to create dqe\n");
 306                                                                 free(dqe);
 307                                                         }
 308                                                 } else if (attrs.entry_count != 0) {
 309                                                         DEBUGPRINT( "Failed to get name for item in %s\n", path);
 310                                                 } else if (attrs.entry_count == 0) {
 311                                                         // Empty directory, nothing to do
 312                                                 }
 313                                         } else {
 314                                                 off_t object_size = 0;
 315
 316                                                 if (attrs.returned.fileattr & ATTR_FILE_LINKCOUNT) {
 317                                                         memcpy(&attrs.link_count, cursor, sizeof(attrs.link_count));
 318                                                         cursor += sizeof(attrs.link_count);
 319                                                 }
 320
 321                                                 if (attrs.returned.fileattr & ATTR_FILE_ALLOCSIZE) {
 322                                                         memcpy(&attrs.alloc_size, cursor, sizeof(attrs.alloc_size));
 323                                                         cursor += sizeof(attrs.alloc_size);
 324                                                         object_size = attrs.alloc_size;
 325                                                 }
 326
 327                                                 if (attrs.returned.fileattr & ATTR_FILE_DATAALLOCSIZE) {
 328                                                         memcpy(&attrs.data_alloc_size, cursor, sizeof(attrs.data_alloc_size));
 329                                                         cursor += sizeof(attrs.data_alloc_size);
 330                                                         if (0 == object_size) {
 331                                                                 object_size = attrs.data_alloc_size;
 332                                                         }
 333                                                 }
 334
 335                                                 if (1 == attrs.link_count) {
 336                                                         ds->total_size += object_size;
 337                                                 } else {
 338                                                         bool seen_fileid = _dirstat_fileid_set_add(fileid_seen, attrs.fileid);
 339                                                         if (!seen_fileid) {
 340                                                                 ds->total_size += object_size;
 341                                                         } else {
 342                                                                 DEBUGPRINT( "Skipping hardlinked file at %s/%s\n", path, name);
 343                                                         }
 344                                                 }
 345                                         }
 346                                         ds->descendants++;
 347                                 }
 348                         }
 349                 }
 350
 351                 if (path) {
 352                         close(fd);
 353                         free(path);
 354                 }
 355         } while (!STAILQ_EMPTY(&dirqueue_head));
 356
 357         _dirstat_fileid_set_destroy(fileid_seen);
 358
 359         if (reterror) {
 360                 errno = reterror;
 361                 return -1;
 362         } else {
 363                 return 0;
 364         }
 365 }