bsd/hfs/hfs_fsinfo.c

   1 /*
   2  * Copyright (c) 2014-2015 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_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. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28
  29 #include <sys/cprotect.h>
  30 #include <sys/xattr.h>
  31 #include <sys/utfconv.h>
  32 #include <libkern/OSByteOrder.h>
  33 #include <kern/kalloc.h>
  34 #include <sys/stat.h>
  35
  36 #include "hfs.h"
  37 #include "hfs_fsctl.h"
  38 #include "hfs_endian.h"
  39 #include "hfscommon/headers/BTreesInternal.h"
  40 #include "hfscommon/headers/BTreesPrivate.h"
  41 #include "hfscommon/headers/FileMgrInternal.h"
  42
  43 #if CONFIG_PROTECT
  44 #include <hfs/hfs_cprotect.h>
  45 #endif
  46
  47
  48 union HFSPlusRecord {
  49         HFSPlusCatalogFolder folder_record;
  50         HFSPlusCatalogFile file_record;
  51         HFSPlusCatalogThread thread_record;
  52         HFSPlusExtentRecord extent_record;
  53         HFSPlusAttrRecord attr_record;
  54 };
  55 typedef union HFSPlusRecord HFSPlusRecord;
  56
  57 union HFSPlusKey {
  58         HFSPlusExtentKey extent_key;
  59         HFSPlusAttrKey attr_key;
  60 };
  61 typedef union HFSPlusKey HFSPlusKey;
  62
  63 typedef enum traverse_btree_flag {
  64
  65         //If set, extents btree will also be traversed along with catalog btree, so grab correct locks upfront
  66         TRAVERSE_BTREE_EXTENTS = 1,
  67
  68         // Getting content-protection attributes, allocate enough space to accomodate the records.
  69         TRAVERSE_BTREE_XATTR_CPROTECT = 2,
  70
  71 } traverse_btree_flag_t;
  72
  73
  74
  75 static errno_t hfs_fsinfo_metadata_blocks(struct hfsmount *hfsmp, struct hfs_fsinfo_metadata *fsinfo);
  76 static errno_t hfs_fsinfo_metadata_extents(struct hfsmount *hfsmp, struct hfs_fsinfo_metadata *fsinfo);
  77 static errno_t hfs_fsinfo_metadata_percentfree(struct hfsmount *hfsmp, struct hfs_fsinfo_metadata *fsinfo);
  78 static errno_t fsinfo_file_extent_count_callback(struct hfsmount *hfsmp, HFSPlusKey *key, HFSPlusRecord *record, void *data);
  79 static errno_t fsinfo_file_extent_size_catalog_callback(struct hfsmount *hfsmp, HFSPlusKey *key, HFSPlusRecord *record, void *data);
  80 static errno_t fsinfo_file_extent_size_overflow_callback(struct hfsmount *hfsmp, HFSPlusKey *key, HFSPlusRecord *record, void *data);
  81 static errno_t fsinfo_file_size_callback(struct hfsmount *hfsmp, HFSPlusKey *key, HFSPlusRecord *record, void *data);
  82 static errno_t fsinfo_dir_valence_callback(struct hfsmount *hfsmp, HFSPlusKey *key, HFSPlusRecord *record, void *data);
  83 static errno_t fsinfo_name_size_callback(struct hfsmount *hfsmp, HFSPlusKey *key, HFSPlusRecord *record, void *data);
  84 static errno_t fsinfo_xattr_size_callback(struct hfsmount *hfsmp, HFSPlusKey *key, HFSPlusRecord *record, void *data);
  85 static errno_t traverse_btree(struct hfsmount *hfsmp, uint32_t btree_fileID, traverse_btree_flag_t flags, void *fsinfo,
  86                 int (*callback)(struct hfsmount *, HFSPlusKey *, HFSPlusRecord *, void *));
  87 static errno_t hfs_fsinfo_free_extents(struct hfsmount *hfsmp, struct hfs_fsinfo_data *fsinfo);
  88 static void fsinfo_free_extents_callback(void *data, off_t free_extent_size);
  89 #if CONFIG_PROTECT
  90 static errno_t fsinfo_cprotect_count_callback(struct hfsmount *hfsmp, HFSPlusKey *key, HFSPlusRecord *record, void *data);
  91 #endif
  92 static errno_t fsinfo_symlink_size_callback(struct hfsmount *hfsmp, HFSPlusKey *key, HFSPlusRecord *record, void *data);
  93
  94 /*
  95  * Entry function for all the fsinfo requests from hfs_vnop_ioctl()
  96  * Depending on the type of request, this function will call the
  97  * appropriate sub-function and return success or failure back to
  98  * the caller.
  99  */
 100 __private_extern__
 101 errno_t hfs_get_fsinfo(struct hfsmount *hfsmp, void *a_data)
 102 {
 103         int error = 0;
 104         hfs_fsinfo *fsinfo_union;
 105         uint32_t request_type;
 106         uint32_t header_len = sizeof(hfs_fsinfo_header_t);
 107
 108         fsinfo_union = (hfs_fsinfo *)a_data;
 109         request_type = fsinfo_union->header.request_type;
 110
 111         // Zero out output fields to fsinfo_union, keep the user input fields intact.
 112         bzero((char *)fsinfo_union + header_len, sizeof(hfs_fsinfo) - header_len);
 113
 114         switch (request_type) {
 115                 case HFS_FSINFO_METADATA_BLOCKS_INFO:
 116                         error = hfs_fsinfo_metadata_blocks(hfsmp, &(fsinfo_union->metadata));
 117                         break;
 118
 119                 case HFS_FSINFO_METADATA_EXTENTS:
 120                         error = hfs_fsinfo_metadata_extents(hfsmp, &(fsinfo_union->metadata));
 121                         break;
 122
 123                 case HFS_FSINFO_METADATA_PERCENTFREE:
 124                         error = hfs_fsinfo_metadata_percentfree(hfsmp, &(fsinfo_union->metadata));
 125                         break;
 126
 127                 case HFS_FSINFO_FILE_EXTENT_COUNT:
 128                         /* Traverse catalog btree and invoke callback for all records */
 129                         error = traverse_btree(hfsmp, kHFSCatalogFileID, TRAVERSE_BTREE_EXTENTS, &(fsinfo_union->data), fsinfo_file_extent_count_callback);
 130                         break;
 131
 132                 case HFS_FSINFO_FILE_EXTENT_SIZE:
 133                         /* Traverse the catalog btree first */
 134                         error = traverse_btree(hfsmp, kHFSCatalogFileID, 0, &(fsinfo_union->data), &fsinfo_file_extent_size_catalog_callback);
 135                         if (error) {
 136                                 break;
 137                         }
 138                         /* Traverse the overflow extents btree now */
 139                         error = traverse_btree(hfsmp, kHFSExtentsFileID, 0, &(fsinfo_union->data), &fsinfo_file_extent_size_overflow_callback);
 140                         break;
 141
 142                 case HFS_FSINFO_FILE_SIZE:
 143                         /* Traverse catalog btree and invoke callback for all records */
 144                         error = traverse_btree(hfsmp, kHFSCatalogFileID, 0, &(fsinfo_union->data), &fsinfo_file_size_callback);
 145                         break;
 146
 147                 case HFS_FSINFO_DIR_VALENCE:
 148                         /* Traverse catalog btree and invoke callback for all records */
 149                         error = traverse_btree(hfsmp, kHFSCatalogFileID, 0, &(fsinfo_union->data), &fsinfo_dir_valence_callback);
 150                         break;
 151
 152                 case HFS_FSINFO_NAME_SIZE:
 153                         /* Traverse catalog btree and invoke callback for all records */
 154                         error = traverse_btree(hfsmp, kHFSCatalogFileID, 0, &(fsinfo_union->name), &fsinfo_name_size_callback);
 155                         break;
 156
 157                 case HFS_FSINFO_XATTR_SIZE:
 158                         /* Traverse attribute btree and invoke callback for all records */
 159                         error = traverse_btree(hfsmp, kHFSAttributesFileID, 0, &(fsinfo_union->data), &fsinfo_xattr_size_callback);
 160                         break;
 161
 162                 case HFS_FSINFO_FREE_EXTENTS:
 163                         error = hfs_fsinfo_free_extents(hfsmp, &(fsinfo_union->data));
 164                         break;
 165
 166                 case HFS_FSINFO_SYMLINK_SIZE:
 167                         /* Traverse catalog btree and invoke callback for all records */
 168                         error = traverse_btree(hfsmp, kHFSCatalogFileID, 0, &(fsinfo_union->data), &fsinfo_symlink_size_callback);
 169                         break;
 170
 171 #if CONFIG_PROTECT
 172                 case HFS_FSINFO_FILE_CPROTECT_COUNT:
 173                         /* Traverse attribute btree and invoke callback for all records */
 174                         error = traverse_btree(hfsmp, kHFSAttributesFileID, TRAVERSE_BTREE_XATTR_CPROTECT, &(fsinfo_union->cprotect), &fsinfo_cprotect_count_callback);
 175                         break;
 176 #endif
 177
 178                 default:
 179                         return ENOTSUP;
 180         };
 181
 182         return error;
 183 }
 184
 185 /*
 186  * This function provides information about total number of allocation blocks
 187  * for each individual metadata file.
 188  */
 189 static errno_t
 190 hfs_fsinfo_metadata_blocks(struct hfsmount *hfsmp, struct hfs_fsinfo_metadata *fsinfo)
 191 {
 192         int lockflags = 0;
 193         int ret_lockflags = 0;
 194
 195         /*
 196          * Getting number of allocation blocks for all metadata files
 197          * should be a relatively quick operation, so we grab locks for all
 198          * the btrees at the same time
 199          */
 200         lockflags = SFL_CATALOG | SFL_EXTENTS | SFL_BITMAP | SFL_ATTRIBUTE;
 201         ret_lockflags = hfs_systemfile_lock(hfsmp, lockflags, HFS_SHARED_LOCK);
 202
 203         /* Get information about all the btrees */
 204         fsinfo->extents    = hfsmp->hfs_extents_cp->c_datafork->ff_blocks;
 205         fsinfo->catalog    = hfsmp->hfs_catalog_cp->c_datafork->ff_blocks;
 206         fsinfo->allocation = hfsmp->hfs_allocation_cp->c_datafork->ff_blocks;
 207         if (hfsmp->hfs_attribute_cp)
 208                 fsinfo->attribute  = hfsmp->hfs_attribute_cp->c_datafork->ff_blocks;
 209         else
 210                 fsinfo->attribute = 0;
 211
 212         /* Done with btrees, give up the locks */
 213         hfs_systemfile_unlock(hfsmp, ret_lockflags);
 214
 215         /* Get information about journal file */
 216         fsinfo->journal = howmany(hfsmp->jnl_size, hfsmp->blockSize);
 217
 218         return 0;
 219 }
 220
 221 /*
 222  * Helper function to count the number of valid extents in a file fork structure
 223  */
 224 static uint32_t
 225 hfs_count_extents_fp(struct filefork *ff)
 226 {
 227         int i;
 228         uint32_t count = 0;
 229         for (i = 0; i < kHFSPlusExtentDensity; i++) {
 230                 if (ff->ff_data.cf_extents[i].blockCount == 0) {
 231                         break;
 232                 }
 233                 count++;
 234         }
 235         return count;
 236 }
 237
 238
 239 /*
 240  * This is a helper function that counts the total number of valid
 241  * extents in all the overflow extent records for given fileID
 242  * in overflow extents btree
 243  */
 244 static errno_t
 245 hfs_count_overflow_extents(struct hfsmount *hfsmp, uint32_t fileID, uint32_t *num_extents)
 246 {
 247         int error;
 248         FCB *fcb;
 249         struct BTreeIterator *iterator = NULL;
 250         FSBufferDescriptor btdata;
 251         HFSPlusExtentKey *extentKey;
 252         HFSPlusExtentRecord extentData;
 253         uint32_t extent_count = 0;
 254         int i;
 255
 256         fcb = VTOF(hfsmp->hfs_extents_vp);
 257         MALLOC(iterator, struct BTreeIterator *, sizeof(struct BTreeIterator), M_TEMP, M_WAITOK | M_ZERO);
 258
 259         extentKey = (HFSPlusExtentKey *) &iterator->key;
 260         extentKey->keyLength = kHFSPlusExtentKeyMaximumLength;
 261         extentKey->forkType = kHFSDataForkType;
 262         extentKey->fileID = fileID;
 263         extentKey->startBlock = 0;
 264
 265         btdata.bufferAddress = &extentData;
 266         btdata.itemSize = sizeof(HFSPlusExtentRecord);
 267         btdata.itemCount = 1;
 268
 269         /* Search for overflow extent record */
 270         error = BTSearchRecord(fcb, iterator, &btdata, NULL, iterator);
 271
 272         /*
 273          * We used startBlock of zero, so we will not find any records and errors
 274          * are expected.  It will also position the iterator just before the first
 275          * overflow extent record for given fileID (if any).
 276          */
 277         if (error && error != fsBTRecordNotFoundErr && error != fsBTEndOfIterationErr)
 278                         goto out;
 279         error = 0;
 280
 281         for (;;) {
 282
 283                 if (msleep(NULL, NULL, PINOD | PCATCH,
 284                                    "hfs_fsinfo", NULL) == EINTR) {
 285                         error = EINTR;
 286                         break;
 287                 }
 288
 289                 error = BTIterateRecord(fcb, kBTreeNextRecord, iterator, &btdata, NULL);
 290                 if (error != 0) {
 291                         /* These are expected errors, so mask them */
 292                         if (error == fsBTRecordNotFoundErr || error == fsBTEndOfIterationErr) {
 293                                 error = 0;
 294                         }
 295                         break;
 296                 }
 297
 298                 /* If we encounter different fileID, stop the iteration */
 299                 if (extentKey->fileID != fileID) {
 300                         break;
 301                 }
 302
 303                 if (extentKey->forkType != kHFSDataForkType)
 304                         break;
 305
 306                 /* This is our record of interest; only count the datafork extents. */
 307                 for (i = 0; i < kHFSPlusExtentDensity; i++) {
 308                         if (extentData[i].blockCount == 0) {
 309                                 break;
 310                         }
 311                         extent_count++;
 312                 }
 313         }
 314
 315 out:
 316         FREE(iterator, M_TEMP);
 317
 318         if (error == 0) {
 319                 *num_extents = extent_count;
 320         }
 321         return MacToVFSError(error);
 322 }
 323
 324 /*
 325  * This function provides information about total number of extents (including
 326  * extents from overflow extents btree, if any) for each individual metadata
 327  * file.
 328  */
 329 static errno_t
 330 hfs_fsinfo_metadata_extents(struct hfsmount *hfsmp, struct hfs_fsinfo_metadata *fsinfo)
 331 {
 332         int error = 0;
 333         int lockflags = 0;
 334         int ret_lockflags = 0;
 335         uint32_t overflow_count;
 336
 337         /*
 338          * Counting the number of extents for all metadata files should
 339          * be a relatively quick operation, so we grab locks for all the
 340          * btrees at the same time
 341          */
 342         lockflags = SFL_CATALOG | SFL_EXTENTS | SFL_BITMAP | SFL_ATTRIBUTE;
 343         ret_lockflags = hfs_systemfile_lock(hfsmp, lockflags, HFS_SHARED_LOCK);
 344
 345         /* Get number of extents for extents overflow btree */
 346         fsinfo->extents = hfs_count_extents_fp(hfsmp->hfs_extents_cp->c_datafork);
 347
 348         /* Get number of extents for catalog btree */
 349         fsinfo->catalog = hfs_count_extents_fp(hfsmp->hfs_catalog_cp->c_datafork);
 350         if (fsinfo->catalog >= kHFSPlusExtentDensity) {
 351                 error = hfs_count_overflow_extents(hfsmp, kHFSCatalogFileID, &overflow_count);
 352                 if (error) {
 353                         goto out;
 354                 }
 355                 fsinfo->catalog += overflow_count;
 356         }
 357
 358         /* Get number of extents for allocation file */
 359         fsinfo->allocation = hfs_count_extents_fp(hfsmp->hfs_allocation_cp->c_datafork);
 360         if (fsinfo->allocation >= kHFSPlusExtentDensity) {
 361                 error = hfs_count_overflow_extents(hfsmp, kHFSAllocationFileID, &overflow_count);
 362                 if (error) {
 363                         goto out;
 364                 }
 365                 fsinfo->allocation += overflow_count;
 366         }
 367
 368         /*
 369          * Get number of extents for attribute btree.
 370          *      hfs_attribute_cp might be NULL.
 371          */
 372         if (hfsmp->hfs_attribute_cp) {
 373                 fsinfo->attribute = hfs_count_extents_fp(hfsmp->hfs_attribute_cp->c_datafork);
 374                 if (fsinfo->attribute >= kHFSPlusExtentDensity) {
 375                         error = hfs_count_overflow_extents(hfsmp, kHFSAttributesFileID, &overflow_count);
 376                         if (error) {
 377                                 goto out;
 378                         }
 379                         fsinfo->attribute += overflow_count;
 380                 }
 381         }
 382         /* Journal always has one extent */
 383         fsinfo->journal = 1;
 384 out:
 385         hfs_systemfile_unlock(hfsmp, ret_lockflags);
 386         return error;
 387 }
 388
 389 /*
 390  * Helper function to calculate percentage i.e. X is what percent of Y?
 391  */
 392 static inline uint32_t
 393 hfs_percent(uint32_t X, uint32_t Y)
 394 {
 395         return (X * 100ll) / Y;
 396 }
 397
 398 /*
 399  * This function provides percentage of free nodes vs total nodes for each
 400  * individual metadata btrees, i.e. for catalog, overflow extents and
 401  * attributes btree.  This information is not applicable for allocation
 402  * file and journal file.
 403  */
 404 static errno_t
 405 hfs_fsinfo_metadata_percentfree(struct hfsmount *hfsmp, struct hfs_fsinfo_metadata *fsinfo)
 406 {
 407         int lockflags = 0;
 408         int ret_lockflags = 0;
 409         BTreeControlBlockPtr btreePtr;
 410         uint32_t free_nodes, total_nodes;
 411
 412         /*
 413          * Getting total and used nodes for all metadata btrees should
 414          * be a relatively quick operation, so we grab locks for all the
 415          * btrees at the same time
 416          */
 417         lockflags = SFL_CATALOG | SFL_EXTENTS | SFL_BITMAP | SFL_ATTRIBUTE;
 418         ret_lockflags = hfs_systemfile_lock(hfsmp, lockflags, HFS_SHARED_LOCK);
 419
 420         /* Overflow extents btree */
 421         btreePtr = VTOF(hfsmp->hfs_extents_vp)->fcbBTCBPtr;
 422         total_nodes = btreePtr->totalNodes;
 423         free_nodes = btreePtr->freeNodes;
 424         fsinfo->extents = hfs_percent(free_nodes, total_nodes);
 425
 426         /* Catalog btree */
 427         btreePtr = VTOF(hfsmp->hfs_catalog_vp)->fcbBTCBPtr;
 428         total_nodes = btreePtr->totalNodes;
 429         free_nodes = btreePtr->freeNodes;
 430         fsinfo->catalog = hfs_percent(free_nodes, total_nodes);
 431
 432         /* Attributes btree */
 433         if (hfsmp->hfs_attribute_vp) {
 434                 btreePtr = VTOF(hfsmp->hfs_attribute_vp)->fcbBTCBPtr;
 435                 total_nodes = btreePtr->totalNodes;
 436                 free_nodes = btreePtr->freeNodes;
 437                 fsinfo->attribute = hfs_percent(free_nodes, total_nodes);
 438         }
 439
 440         hfs_systemfile_unlock(hfsmp, ret_lockflags);
 441         return 0;
 442 }
 443
 444 /*
 445  * Helper function to calculate log base 2 for given number
 446  */
 447 static inline int
 448 hfs_log2(uint64_t entry)
 449 {
 450         return (63 - __builtin_clzll(entry|1));
 451 }
 452
 453 /*
 454  * Helper function to account for input entry into the data
 455  * array based on its log base 2 value
 456  */
 457 __private_extern__
 458 void hfs_fsinfo_data_add(struct hfs_fsinfo_data *fsinfo, uint64_t entry)
 459 {
 460         /*
 461          * From hfs_fsctl.h -
 462          *
 463          * hfs_fsinfo_data is generic data structure to aggregate information like sizes
 464          * or counts in buckets of power of 2.  Each bucket represents a range of values
 465          * that is determined based on its index in the array.  Specifically, buckets[i]
 466          * represents values that are greater than or equal to 2^(i-1) and less than 2^i,
 467          * except the last bucket which represents range greater than or equal to 2^(i-1)
 468          *
 469          * The current maximum number of buckets is 41, so we can represent range from
 470          * 0 up to 1TB in increments of power of 2, and then a catch-all bucket of
 471          * anything that is greater than or equal to 1TB.
 472          *
 473          * For example,
 474          * bucket[0]  -> greater than or equal to 0 and less than 1
 475          * bucket[1]  -> greater than or equal to 1 and less than 2
 476          * bucket[10] -> greater than or equal to 2^(10-1) = 512 and less than 2^10 = 1024
 477          * bucket[20] -> greater than or equal to 2^(20-1) = 512KB and less than 2^20 = 1MB
 478          * bucket[41] -> greater than or equal to 2^(41-1) = 1TB
 479          */
 480         uint32_t bucket;
 481
 482         if (entry) {
 483                 /*
 484                  * Calculate log base 2 value for the entry.
 485                  * Account for this value in the appropriate bucket.
 486                  * The last bucket is a catch-all bucket of
 487                  * anything that is greater than or equal to 1TB
 488                  */
 489                 bucket = MIN(hfs_log2(entry) + 1, HFS_FSINFO_DATA_MAX_BUCKETS-1);
 490                 ++fsinfo->bucket[bucket];
 491         } else {
 492                 /* Entry is zero, so account it in 0th offset */
 493                 fsinfo->bucket[0]++;
 494         }
 495 }
 496
 497 /*
 498  * Function to traverse all the records of a btree and then call caller-provided
 499  * callback function for every record found.  The type of btree is chosen based
 500  * on the fileID provided by the caller.  This fuction grabs the correct locks
 501  * depending on the type of btree it will be traversing and flags provided
 502  * by the caller.
 503  *
 504  * Note: It might drop and reacquire the locks during execution.
 505  */
 506 static errno_t
 507 traverse_btree(struct hfsmount *hfsmp, uint32_t btree_fileID, traverse_btree_flag_t flags,
 508                            void *fsinfo, int (*callback)(struct hfsmount *, HFSPlusKey *, HFSPlusRecord *, void *))
 509 {
 510         int error = 0;
 511         int lockflags = 0;
 512         int ret_lockflags = 0;
 513         FCB *fcb;
 514         struct BTreeIterator *iterator = NULL;
 515         struct FSBufferDescriptor btdata;
 516         int btree_operation;
 517         HFSPlusRecord record;
 518         HFSPlusKey *key;
 519         uint64_t start, timeout_abs;
 520
 521         switch(btree_fileID) {
 522                 case kHFSExtentsFileID:
 523                         fcb = VTOF(hfsmp->hfs_extents_vp);
 524                         lockflags = SFL_EXTENTS;
 525                         break;
 526                 case kHFSCatalogFileID:
 527                         fcb = VTOF(hfsmp->hfs_catalog_vp);
 528                         lockflags = SFL_CATALOG;
 529                         break;
 530                 case kHFSAttributesFileID:
 531                         // Attributes file doesn’t exist, There are no records to iterate.
 532                         if (hfsmp->hfs_attribute_vp == NULL)
 533                                 return error;
 534                         fcb = VTOF(hfsmp->hfs_attribute_vp);
 535                         lockflags = SFL_ATTRIBUTE;
 536                         break;
 537
 538                 default:
 539                         return EINVAL;
 540         }
 541
 542         MALLOC(iterator, struct BTreeIterator *, sizeof(struct BTreeIterator), M_TEMP, M_WAITOK | M_ZERO);
 543
 544         /* The key is initialized to zero because we are traversing entire btree */
 545         key = (HFSPlusKey *)&iterator->key;
 546
 547         if (flags & TRAVERSE_BTREE_EXTENTS) {
 548                 lockflags |= SFL_EXTENTS;
 549         }
 550
 551         btdata.bufferAddress = &record;
 552         btdata.itemSize = sizeof(HFSPlusRecord);
 553         btdata.itemCount = 1;
 554
 555         /* Lock btree for duration of traversal */
 556         ret_lockflags = hfs_systemfile_lock(hfsmp, lockflags, HFS_SHARED_LOCK);
 557         btree_operation = kBTreeFirstRecord;
 558
 559         nanoseconds_to_absolutetime(HFS_FSINFO_MAX_LOCKHELD_TIME, &timeout_abs);
 560         start = mach_absolute_time();
 561
 562         while (1) {
 563
 564                 if (msleep(NULL, NULL, PINOD | PCATCH,
 565                                    "hfs_fsinfo", NULL) == EINTR) {
 566                         error = EINTR;
 567                         break;
 568                 }
 569
 570                 error = BTIterateRecord(fcb, btree_operation, iterator, &btdata, NULL);
 571                 if (error != 0) {
 572                         if (error == fsBTRecordNotFoundErr || error == fsBTEndOfIterationErr) {
 573                                 error = 0;
 574                         }
 575                         break;
 576                 }
 577                 /* Lookup next btree record on next call to BTIterateRecord() */
 578                 btree_operation = kBTreeNextRecord;
 579
 580                 /* Call our callback function and stop iteration if there are any errors */
 581                 error = callback(hfsmp, key, &record, fsinfo);
 582                 if (error) {
 583                         break;
 584                 }
 585
 586                 /* let someone else use the tree after we've processed over HFS_FSINFO_MAX_LOCKHELD_TIME */
 587                 if ((mach_absolute_time() - start) >= timeout_abs) {
 588
 589                         /* release b-tree locks and let someone else get the lock */
 590                         hfs_systemfile_unlock (hfsmp, ret_lockflags);
 591
 592                         /* add tsleep here to force context switch and fairness */
 593                         tsleep((caddr_t)hfsmp, PRIBIO, "hfs_fsinfo", 1);
 594
 595                         /*
 596                          * re-acquire the locks in the same way that we wanted them originally.
 597                          * note: it is subtle but worth pointing out that in between the time that we
 598                          * released and now want to re-acquire these locks that the b-trees may have shifted
 599                          * slightly but significantly. For example, the catalog or other b-tree could have grown
 600                          * past 8 extents and now requires the extents lock to be held in order to be safely
 601                          * manipulated. We can't be sure of the state of the b-tree from where we last left off.
 602                          */
 603
 604                         ret_lockflags = hfs_systemfile_lock (hfsmp, lockflags, HFS_SHARED_LOCK);
 605
 606                         /*
 607                          * It's highly likely that the search key we stashed away before dropping lock
 608                          * no longer points to an existing item.  Iterator's IterateRecord is able to
 609                          * re-position itself and process the next record correctly.  With lock dropped,
 610                          * there might be records missed for statistic gathering, which is ok. The
 611                          * point is to get aggregate values.
 612                          */
 613
 614                         start = mach_absolute_time();
 615
 616                         /* loop back around and get another record */
 617                 }
 618         }
 619
 620         hfs_systemfile_unlock(hfsmp, ret_lockflags);
 621         FREE (iterator, M_TEMP);
 622         return MacToVFSError(error);
 623 }
 624
 625 /*
 626  * Callback function to get distribution of number of extents
 627  * for all user files in given file system.  Note that this only
 628  * accounts for data fork, no resource fork.
 629  */
 630 static errno_t
 631 fsinfo_file_extent_count_callback(struct hfsmount *hfsmp,
 632                 __unused HFSPlusKey *key, HFSPlusRecord *record, void *data)
 633 {
 634         int i;
 635         int error = 0;
 636         uint32_t num_extents = 0;
 637         uint32_t num_overflow = 0;
 638         uint32_t blockCount;
 639
 640         if (record->file_record.recordType == kHFSPlusFileRecord) {
 641                 /* Count total number of extents for this file */
 642                 for (i = 0; i < kHFSPlusExtentDensity; i++) {
 643                         blockCount = record->file_record.dataFork.extents[i].blockCount;
 644                         if (blockCount == 0) {
 645                                 break;
 646                         }
 647                         num_extents++;
 648                 }
 649                 /* This file has overflow extent records, so search overflow btree */
 650                 if (num_extents >= kHFSPlusExtentDensity) {
 651                         /* The caller also hold extents overflow btree lock */
 652                         error = hfs_count_overflow_extents(hfsmp, record->file_record.fileID, &num_overflow);
 653                         if (error) {
 654                                 goto out;
 655                         }
 656                         num_extents += num_overflow;
 657                 }
 658                 hfs_fsinfo_data_add(data, num_extents);
 659         }
 660 out:
 661         return error;
 662 }
 663
 664 /*
 665  * Callback function to get distribution of individual extent sizes
 666  * (in bytes) for all user files in given file system from catalog
 667  * btree only.  Note that this only accounts for data fork, no resource
 668  * fork.
 669  */
 670 static errno_t fsinfo_file_extent_size_catalog_callback(__unused struct hfsmount *hfsmp,
 671                 __unused HFSPlusKey *key, HFSPlusRecord *record, void *data)
 672 {
 673         int i;
 674         uint32_t blockCount;
 675         uint64_t extent_size;
 676
 677         if (record->file_record.recordType == kHFSPlusFileRecord) {
 678                 /* Traverse through all valid extents */
 679                 for (i = 0; i < kHFSPlusExtentDensity; i++) {
 680                         blockCount = record->file_record.dataFork.extents[i].blockCount;
 681                         if (blockCount == 0) {
 682                                 break;
 683                         }
 684                         extent_size = hfs_blk_to_bytes(blockCount, hfsmp->blockSize);
 685                         hfs_fsinfo_data_add(data, extent_size);
 686                 }
 687         }
 688         return 0;
 689 }
 690
 691 /*
 692  * Callback function to get distribution of individual extent sizes
 693  * (in bytes) for all user files in given file system from overflow
 694  * extents btree only.  Note that this only accounts for data fork,
 695  * no resource fork.
 696  */
 697 static errno_t fsinfo_file_extent_size_overflow_callback(__unused struct hfsmount *hfsmp,
 698                 HFSPlusKey *key, HFSPlusRecord *record, void *data)
 699 {
 700         int i;
 701         uint32_t blockCount;
 702         uint64_t extent_size;
 703
 704         if (key->extent_key.fileID >= kHFSFirstUserCatalogNodeID) {
 705                 // Only count the data fork extents.
 706                 if (key->extent_key.forkType == kHFSDataForkType) {
 707                         for (i = 0; i < kHFSPlusExtentDensity; i++) {
 708                                 blockCount = record->extent_record[i].blockCount;
 709                                 if (blockCount == 0) {
 710                                         break;
 711                                 }
 712                                 extent_size = hfs_blk_to_bytes(blockCount, hfsmp->blockSize);
 713                                 hfs_fsinfo_data_add(data, extent_size);
 714                         }
 715                 }
 716         }
 717         return 0;
 718 }
 719
 720 /*
 721  * Callback function to get distribution of file sizes (in bytes)
 722  * for all user files in given file system.  Note that this only
 723  * accounts for data fork, no resource fork.
 724  */
 725 static errno_t fsinfo_file_size_callback(__unused struct hfsmount *hfsmp,
 726                 __unused HFSPlusKey *key, HFSPlusRecord *record, void *data)
 727 {
 728         if (record->file_record.recordType == kHFSPlusFileRecord) {
 729                 /* Record of interest, account for the size in the bucket */
 730                 hfs_fsinfo_data_add(data, record->file_record.dataFork.logicalSize);
 731         }
 732         return 0;
 733 }
 734
 735 /*
 736  * Callback function to get distribution of directory valence
 737  * for all directories in the given file system.
 738  */
 739 static errno_t fsinfo_dir_valence_callback(__unused struct hfsmount *hfsmp,
 740                 __unused HFSPlusKey *key, HFSPlusRecord *record, void *data)
 741 {
 742         if (record->folder_record.recordType == kHFSPlusFolderRecord) {
 743                 hfs_fsinfo_data_add(data, record->folder_record.valence);
 744         }
 745         return 0;
 746 }
 747
 748 /*
 749  * Callback function to get distribution of number of unicode
 750  * characters in name for all files and directories for a given
 751  * file system.
 752  */
 753 static errno_t fsinfo_name_size_callback(__unused struct hfsmount *hfsmp,
 754                 __unused HFSPlusKey *key, HFSPlusRecord *record, void *data)
 755 {
 756         struct hfs_fsinfo_name *fsinfo = (struct hfs_fsinfo_name *)data;
 757         uint32_t length;
 758
 759         if ((record->folder_record.recordType == kHFSPlusFolderThreadRecord) ||
 760             (record->folder_record.recordType == kHFSPlusFileThreadRecord)) {
 761                 length = record->thread_record.nodeName.length;
 762                 /* Make sure that the nodeName is bounded, otherwise return error */
 763                 if (length > kHFSPlusMaxFileNameChars) {
 764                         return EIO;
 765                 }
 766
 767                 // sanity check for a name length of zero, which isn't valid on disk.
 768                 if (length == 0)
 769                         return EIO;
 770
 771                 /* Round it down to nearest multiple of 5 to match our buckets granularity */
 772                 length = (length - 1)/ 5;
 773                 /* Account this value into our bucket */
 774                 fsinfo->bucket[length]++;
 775         }
 776         return 0;
 777 }
 778
 779 /*
 780  * Callback function to get distribution of size of all extended
 781  * attributes for a given file system.
 782  */
 783 static errno_t fsinfo_xattr_size_callback(__unused struct hfsmount *hfsmp,
 784                 __unused HFSPlusKey *key, HFSPlusRecord *record, void *data)
 785 {
 786         if (record->attr_record.recordType == kHFSPlusAttrInlineData) {
 787                 /* Inline attribute */
 788                 hfs_fsinfo_data_add(data, record->attr_record.attrData.attrSize);
 789         } else if (record->attr_record.recordType == kHFSPlusAttrForkData) {
 790                 /* Larger attributes with extents information */
 791                 hfs_fsinfo_data_add(data, record->attr_record.forkData.theFork.logicalSize);
 792         }
 793         return 0;
 794 }
 795
 796
 797 /*
 798  * Callback function to get distribution of free space extents for a given file system.
 799  */
 800 static void fsinfo_free_extents_callback(void *data, off_t free_extent_size)
 801 {
 802         // Assume a minimum of 4 KB block size
 803         hfs_fsinfo_data_add(data, free_extent_size / 4096);
 804 }
 805
 806 /*
 807  * Function to get distribution of free space extents for a given file system.
 808  */
 809 static errno_t hfs_fsinfo_free_extents(struct hfsmount *hfsmp, struct hfs_fsinfo_data *fsinfo)
 810 {
 811         return hfs_find_free_extents(hfsmp, &fsinfo_free_extents_callback, fsinfo);
 812 }
 813
 814 /*
 815  * Callback function to get distribution of symblock link sizes (in bytes)
 816  * for all user files in given file system.  Note that this only
 817  * accounts for data fork, no resource fork.
 818  */
 819 static errno_t fsinfo_symlink_size_callback(__unused struct hfsmount *hfsmp,
 820                                                                          __unused HFSPlusKey *key, HFSPlusRecord *record, void *data)
 821 {
 822         if (record->file_record.recordType == kHFSPlusFileRecord) {
 823                 /* Record of interest, account for the size in the bucket */
 824                 if (S_ISLNK(record->file_record.bsdInfo.fileMode))
 825                         hfs_fsinfo_data_add((struct hfs_fsinfo_data *)data, record->file_record.dataFork.logicalSize);
 826         }
 827         return 0;
 828 }
 829
 830 #if CONFIG_PROTECT
 831 /*
 832  * Callback function to get total number of files/directories
 833  * for each content protection class
 834  */
 835 static int fsinfo_cprotect_count_callback(struct hfsmount *hfsmp, HFSPlusKey *key,
 836                                                                                   HFSPlusRecord *record, void *data)
 837 {
 838         struct hfs_fsinfo_cprotect *fsinfo = (struct hfs_fsinfo_cprotect *)data;
 839         static const uint16_t cp_xattrname_utf16[] = CONTENT_PROTECTION_XATTR_NAME_CHARS;
 840         static const size_t cp_xattrname_utf16_len = sizeof(cp_xattrname_utf16)/2;
 841         struct cp_xattr_v5 *xattr;
 842         size_t xattr_len = sizeof(struct cp_xattr_v5);
 843         struct cprotect cp_entry;
 844         struct cprotect *cp_entryp = &cp_entry;
 845         int error = 0;
 846
 847         /* Content protect xattrs are inline attributes only, so skip all others */
 848         if (record->attr_record.recordType != kHFSPlusAttrInlineData)
 849                 return 0;
 850
 851         /* We only look at content protection xattrs */
 852         if ((key->attr_key.attrNameLen != cp_xattrname_utf16_len) ||
 853                 (bcmp(key->attr_key.attrName, cp_xattrname_utf16, cp_xattrname_utf16_len))) {
 854                 return 0;
 855         }
 856
 857         xattr = (struct cp_xattr_v5 *)((void *)(record->attr_record.attrData.attrData));
 858         error = cp_read_xattr_v5(hfsmp, xattr, xattr_len, (cprotect_t *)&cp_entryp,
 859                                                          CP_GET_XATTR_BASIC_INFO);
 860         if (error)
 861                 return 0;
 862
 863         /* No key present, skip this record */
 864         if (!ISSET(cp_entry.cp_flags, CP_HAS_A_KEY))
 865                 return 0;
 866
 867         /* Now account for the persistent class */
 868         switch (CP_CLASS(cp_entry.cp_pclass)) {
 869                 case PROTECTION_CLASS_A:
 870                         fsinfo->class_A++;
 871                         break;
 872                 case PROTECTION_CLASS_B:
 873                         fsinfo->class_B++;
 874                         break;
 875                 case PROTECTION_CLASS_C:
 876                         fsinfo->class_C++;
 877                         break;
 878                 case PROTECTION_CLASS_D:
 879                         fsinfo->class_D++;
 880                         break;
 881                 case PROTECTION_CLASS_E:
 882                         fsinfo->class_E++;
 883                         break;
 884                 case PROTECTION_CLASS_F:
 885                         fsinfo->class_F++;
 886                         break;
 887         };
 888
 889         return 0;
 890 }
 891 #endif