tests/hfs_extents_test.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 "hfs_extents_test.h"
  30 #include "../core/hfs_extents.h"
  31
  32 typedef struct extent_group {
  33         LIST_ENTRY(extent_group) chain;
  34         uint32_t start_block;
  35         HFSPlusExtentRecord extents;
  36         bool deleted;
  37 } extent_group_t;
  38
  39 int32_t BTDeleteRecord(filefork_t    *ff,
  40                                            BTreeIterator *iterator)
  41 {
  42         (void)ff;
  43
  44         assert(!iterator->group->deleted);
  45
  46         LIST_REMOVE(iterator->group, chain);
  47
  48         iterator->group->deleted = true;
  49
  50         return 0;
  51 }
  52
  53 errno_t hfs_ext_iter_next_group(struct hfs_ext_iter *iter)
  54 {
  55         off_t offset = (iter->bt_iter.key.startBlock + iter->group_block_count) * 4096;
  56
  57         errno_t ret = hfs_ext_find(iter->vp, offset, iter);
  58
  59         if (ret)
  60                 return ret;
  61
  62         if (iter->bt_iter.key.startBlock != offset / 4096)
  63                 return ESTALE;
  64
  65         return 0;
  66 }
  67
  68 errno_t hfs_ext_iter_update(hfs_ext_iter_t *iter,
  69                                                         HFSPlusExtentDescriptor *extents,
  70                                                         int count,
  71                                                         HFSPlusExtentRecord cat_extents)
  72 {
  73         if (count % kHFSPlusExtentDensity) {
  74                 // Zero out last group
  75                 int to_zero = kHFSPlusExtentDensity - (count % 8);
  76                 bzero(&extents[count], to_zero * sizeof(*extents));
  77                 count += to_zero;
  78         }
  79
  80         extent_group_t *group = NULL;
  81
  82         if (!iter->bt_iter.key.startBlock) {
  83                 memcpy(cat_extents, extents, sizeof(HFSPlusExtentRecord));
  84                 group = LIST_FIRST(&iter->vp->ffork->groups);
  85                 hfs_ext_copy_rec(extents, group->extents);
  86
  87                 iter->bt_iter.key.startBlock += hfs_total_blocks(extents, 8);
  88
  89                 count -= 8;
  90                 extents += 8;
  91         } else {
  92                 extent_group_t *next;
  93                 LIST_FOREACH(next, &iter->vp->ffork->groups, chain) {
  94                         if (iter->bt_iter.key.startBlock < next->start_block)
  95                                 break;
  96                         group = next;
  97                 }
  98         }
  99
 100         iter->bt_iter.group = NULL;
 101
 102         while (count > 0) {
 103                 extent_group_t *new_group = malloc(sizeof(*new_group));
 104                 hfs_ext_copy_rec(extents, new_group->extents);
 105                 new_group->start_block = iter->bt_iter.key.startBlock;
 106                 new_group->deleted = false;
 107
 108                 if (group) {
 109                         LIST_INSERT_AFTER(group, new_group, chain);
 110                 } else
 111                         LIST_INSERT_HEAD(&iter->vp->ffork->groups, new_group, chain);
 112                 group = new_group;
 113
 114                 iter->bt_iter.key.startBlock += hfs_total_blocks(extents, 8);
 115
 116                 count -= 8;
 117                 extents += 8;
 118         }
 119
 120         return 0;
 121 }
 122
 123 errno_t hfs_ext_find(vnode_t vp, off_t offset, hfs_ext_iter_t *iter)
 124 {
 125         (void)vp;
 126         const uint32_t block = (uint32_t)(offset / 4096);
 127
 128         iter->vp = vp;
 129         extent_group_t *next, *group = NULL;
 130         LIST_FOREACH(next, &vp->ffork->groups, chain) {
 131                 if (block < next->start_block)
 132                         break;
 133                 group = next;
 134         }
 135
 136         if (!group)
 137                 return ENOENT;
 138
 139         iter->file_block = iter->bt_iter.key.startBlock = group->start_block;
 140         iter->bt_iter.group = group;
 141
 142         for (iter->ndx = 0; iter->ndx < 8; ++iter->ndx) {
 143                 HFSPlusExtentDescriptor *ext = &group->extents[iter->ndx];
 144                 if (iter->file_block + ext->blockCount > block) {
 145                         hfs_ext_copy_rec(group->extents, iter->group);
 146                         return hfs_ext_iter_check_group(iter);
 147                 }
 148                 iter->file_block += ext->blockCount;
 149         }
 150
 151         return ENOENT;
 152 }
 153
 154 void dump_extents(struct extent_groups *groups)
 155 {
 156         extent_group_t *group;
 157         int i = 0;
 158
 159         LIST_FOREACH(group, groups, chain) {
 160                 for (int j = 0; j < 8; ++j) {
 161                         HFSPlusExtentDescriptor *ext = &group->extents[j];
 162                         if (!ext->blockCount) {
 163                                 // Make sure all the reset are NULL
 164                                 if (LIST_NEXT(group, chain))
 165                                         goto keep_going;
 166
 167                                 for (int k = j; k < 8; ++k) {
 168                                         if (group->extents[k].startBlock
 169                                                 || group->extents[k].blockCount) {
 170                                                 goto keep_going;
 171                                         }
 172                                 }
 173
 174                                 break;
 175                         }
 176
 177                 keep_going:
 178
 179                         printf("%s{ %u, %u }", (i == 0 ? "" : i % 4 == 0 ? ",\n" : ", "),
 180                                    ext->startBlock, ext->blockCount);
 181                         ++i;
 182                 }
 183         }
 184         printf("\n");
 185 }
 186
 187 void check_extents(unsigned line, vnode_t vnode,
 188                                    const HFSPlusExtentDescriptor *extents, int count)
 189 {
 190         uint32_t block = 0;
 191         extent_group_t *group;
 192         LIST_FOREACH(group, &vnode->ffork->groups, chain) {
 193                 if (group->start_block != block)
 194                         goto bad;
 195                 int cnt = MIN(count, 8);
 196                 if (memcmp(group->extents, extents, cnt * sizeof(*extents)))
 197                         goto bad;
 198                 while (cnt < 8) {
 199                         if (group->extents[cnt].startBlock || group->extents[cnt].blockCount)
 200                                 goto bad;
 201                         ++cnt;
 202                 }
 203                 if ((count -= 8) <= 0)
 204                         break;
 205                 block += hfs_total_blocks(extents, 8);
 206                 extents += 8;
 207         }
 208
 209         if (LIST_NEXT(group, chain))
 210                 goto bad;
 211
 212         return;
 213
 214 bad:
 215
 216         printf("hfs_extents_test:%u: error: unexpected extents:\n", line);
 217         dump_extents(&vnode->ffork->groups);
 218         exit(1);
 219 }
 220
 221 int main(void)
 222 {
 223         cnode_t cnode = {};
 224         hfsmount_t mount = {
 225                 .blockSize = 4096,
 226                 .hfs_extents_cp = &cnode,
 227         };
 228         filefork_t ffork = {
 229                 .ff_blocks                      = 200,
 230                 .ff_unallocblocks       = 100,
 231                 .groups = LIST_HEAD_INITIALIZER(ffork.groups),
 232         };
 233         struct vnode vnode = {
 234                 .ffork = &ffork,
 235                 .mount = &mount,
 236                 .is_rsrc = false,
 237                 .cnode = &cnode,
 238         };
 239
 240         extent_group_t group = {
 241                 .extents = { { 100, 100 } },
 242         };
 243
 244         LIST_INSERT_HEAD(&ffork.groups, &group, chain);
 245
 246         HFSPlusExtentRecord cat_extents;
 247
 248 #define E(...)                  (HFSPlusExtentDescriptor[]) { __VA_ARGS__ }
 249 #define lengthof(x)             (sizeof(x) / sizeof(*x))
 250
 251 #define CHECK_EXTENTS(...)                                                                              \
 252         do {                                                                                                            \
 253                 HFSPlusExtentDescriptor extents_[] = __VA_ARGS__;               \
 254                 check_extents(__LINE__, &vnode, extents_,                               \
 255                                           lengthof(extents_));                                          \
 256         } while (0)
 257
 258 #define CHECK_REPLACE(file_block, repl, expected)                                                               \
 259         do {                                                                                                                                            \
 260                 HFSPlusExtentDescriptor repl_[] = repl;                                                                 \
 261                 hfs_ext_replace(&mount, &vnode, file_block, repl_,                                              \
 262                                                 lengthof(repl_), cat_extents);                                                  \
 263                 CHECK_EXTENTS(expected);                                                                                                \
 264         } while (0)
 265
 266         CHECK_REPLACE(10, E({ 200, 10 }),
 267                                   E({ 100, 10 }, { 200, 10 }, { 120, 80 }));
 268
 269         CHECK_REPLACE(5, E({ 300, 10 }),
 270                                   E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 120, 80 }));
 271
 272         CHECK_REPLACE(20, E({ 400, 1 }),
 273                                   E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 400, 1 },
 274                                         { 121, 79 }));
 275
 276         CHECK_REPLACE(21, E({ 402, 1 }),
 277                                   E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 400, 1 },
 278                                         { 402, 1 }, { 122, 78 }));
 279
 280         CHECK_REPLACE(22, E({ 404, 1 }),
 281                                   E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 400, 1 },
 282                                         { 402, 1 }, { 404, 1 }, { 123, 77 }));
 283
 284         CHECK_REPLACE(23, E({ 406, 1 }),
 285                                   E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 400, 1 },
 286                                         { 402, 1 }, { 404, 1 }, { 406, 1 }, { 124, 76 }));
 287
 288         CHECK_REPLACE(24, E({ 408, 1 }),
 289                                   E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 400, 1 },
 290                                         { 402, 1 }, { 404, 1 }, { 406, 1 }, { 408, 1 },
 291                                         { 125, 75 }));
 292
 293         /*
 294          * OK, now we won't see any padding until we get the number of extents
 295          * over 32.  So let's get to that point now.
 296          */
 297
 298         for (int i = 25, j = 500; i < 25 + 24; ++i, j += 2) {
 299                 hfs_ext_replace(&mount, &vnode, i, E({ j, 1 }),
 300                                                 1, cat_extents);
 301         }
 302
 303         CHECK_EXTENTS(E({ 100, 5 }, { 300, 10 }, { 205, 5 }, { 400, 1 },
 304                                         { 402, 1 }, { 404, 1 }, { 406, 1 }, { 408, 1 },
 305                                         { 500, 1 }, { 502, 1 }, { 504, 1 }, { 506, 1 },
 306                                         { 508, 1 }, { 510, 1 }, { 512, 1 }, { 514, 1 },
 307                                         { 516, 1 }, { 518, 1 }, { 520, 1 }, { 522, 1 },
 308                                         { 524, 1 }, { 526, 1 }, { 528, 1 }, { 530, 1 },
 309                                         { 532, 1 }, { 534, 1 }, { 536, 1 }, { 538, 1 },
 310                                         { 540, 1 }, { 542, 1 }, { 544, 1 }, { 546, 1 },
 311                                         { 149, 51 }));
 312
 313         /*
 314          * So if we replace an extent in the first group, we should see it pad using
 315          * the 205 extent and some of the 300 extent.
 316          */
 317
 318         CHECK_REPLACE(2, E({ 600, 1 }),
 319                                   E({ 100, 2 }, { 600, 1 }, { 103, 2 }, { 300, 8 },
 320                                         { 308, 1 }, { 309, 1 }, { 205, 1 }, { 206, 1 },
 321                                         { 207, 1 }, { 208, 1 }, { 209, 1 }, { 400, 1 },
 322                                         { 402, 1 }, { 404, 1 }, { 406, 1 }, { 408, 1 },
 323                                         { 500, 1 }, { 502, 1 }, { 504, 1 }, { 506, 1 },
 324                                         { 508, 1 }, { 510, 1 }, { 512, 1 }, { 514, 1 },
 325                                         { 516, 1 }, { 518, 1 }, { 520, 1 }, { 522, 1 },
 326                                         { 524, 1 }, { 526, 1 }, { 528, 1 }, { 530, 1 },
 327                                         { 532, 1 }, { 534, 1 }, { 536, 1 }, { 538, 1 },
 328                                         { 540, 1 }, { 542, 1 }, { 544, 1 }, { 546, 1 },
 329                                         { 149, 51 }));
 330
 331         /*
 332          * Now try and test the case where it fails to pad and is forced to move
 333          * to the next group.  First, merge the 544 and 546 extents to reduce
 334          * the number of extents by 1.
 335          */
 336
 337         CHECK_REPLACE(47, E({ 700, 2 }),
 338                                   E({ 100, 2 }, { 600, 1 }, { 103, 2 }, { 300, 8 },
 339                                         { 308, 1 }, { 309, 1 }, { 205, 1 }, { 206, 1 },
 340                                         { 207, 1 }, { 208, 1 }, { 209, 1 }, { 400, 1 },
 341                                         { 402, 1 }, { 404, 1 }, { 406, 1 }, { 408, 1 },
 342                                         { 500, 1 }, { 502, 1 }, { 504, 1 }, { 506, 1 },
 343                                         { 508, 1 }, { 510, 1 }, { 512, 1 }, { 514, 1 },
 344                                         { 516, 1 }, { 518, 1 }, { 520, 1 }, { 522, 1 },
 345                                         { 524, 1 }, { 526, 1 }, { 528, 1 }, { 530, 1 },
 346                                         { 532, 1 }, { 534, 1 }, { 536, 1 }, { 538, 1 },
 347                                         { 540, 1 }, { 542, 1 }, { 700, 2 }, { 149, 51 }));
 348
 349         // Now force 207-209 to be merged
 350
 351         CHECK_REPLACE(21, E({ 800, 1 }),
 352                                   E({ 100, 2 }, { 600, 1 }, { 103, 2 }, { 300, 8 },
 353                                         { 308, 1 }, { 309, 1 }, { 205, 1 }, { 206, 1 },
 354                                         { 207, 3 }, { 400, 1 }, { 800, 1 }, { 404, 1 },
 355                                         { 406, 1 }, { 408, 1 }, { 500, 1 }, { 502, 1 },
 356                                         { 504, 1 }, { 506, 1 }, { 508, 1 }, { 510, 1 },
 357                                         { 512, 1 }, { 514, 1 }, { 516, 1 }, { 518, 1 },
 358                                         { 520, 1 }, { 522, 1 }, { 524, 1 }, { 526, 1 },
 359                                         { 528, 1 }, { 530, 1 }, { 532, 1 }, { 534, 1 },
 360                                         { 536, 1 }, { 538, 1 }, { 540, 1 }, { 542, 1 },
 361                                         { 700, 2 }, { 149, 51 }));
 362
 363         // Now let's push the last extent into a new group
 364
 365         CHECK_REPLACE(50, E({ 800, 1 }),
 366                                   E({ 100, 2 }, { 600, 1 }, { 103, 2 }, { 300, 8 },
 367                                         { 308, 1 }, { 309, 1 }, { 205, 1 }, { 206, 1 },
 368                                         { 207, 3 }, { 400, 1 }, { 800, 1 }, { 404, 1 },
 369                                         { 406, 1 }, { 408, 1 }, { 500, 1 }, { 502, 1 },
 370                                         { 504, 1 }, { 506, 1 }, { 508, 1 }, { 510, 1 },
 371                                         { 512, 1 }, { 514, 1 }, { 516, 1 }, { 518, 1 },
 372                                         { 520, 1 }, { 522, 1 }, { 524, 1 }, { 526, 1 },
 373                                         { 528, 1 }, { 530, 1 }, { 532, 1 }, { 534, 1 },
 374                                         { 536, 1 }, { 538, 1 }, { 540, 1 }, { 542, 1 },
 375                                         { 700, 2 }, { 149, 1 }, { 800, 1 }, { 151, 49 }));
 376
 377         CHECK_REPLACE(52, E({ 802, 1 }),
 378                                   E({ 100, 2 }, { 600, 1 }, { 103, 2 }, { 300, 8 },
 379                                         { 308, 1 }, { 309, 1 }, { 205, 1 }, { 206, 1 },
 380                                         { 207, 3 }, { 400, 1 }, { 800, 1 }, { 404, 1 },
 381                                         { 406, 1 }, { 408, 1 }, { 500, 1 }, { 502, 1 },
 382                                         { 504, 1 }, { 506, 1 }, { 508, 1 }, { 510, 1 },
 383                                         { 512, 1 }, { 514, 1 }, { 516, 1 }, { 518, 1 },
 384                                         { 520, 1 }, { 522, 1 }, { 524, 1 }, { 526, 1 },
 385                                         { 528, 1 }, { 530, 1 }, { 532, 1 }, { 534, 1 },
 386                                         { 536, 1 }, { 538, 1 }, { 540, 1 }, { 542, 1 },
 387                                         { 700, 2 }, { 149, 1 }, { 800, 1 }, { 151, 1 },
 388                                         { 802, 1 }, { 153, 47 }));
 389
 390         /*
 391          * And now if we split the 207 extent, it will fail to pad within the
 392          * 32 extents and so it will be forced to pull in more extents.
 393          */
 394
 395         CHECK_REPLACE(18, E({ 900, 1 }),
 396                                   E({ 100, 2 }, { 600, 1 }, { 103, 2 }, { 300, 8 },
 397                                         { 308, 1 }, { 309, 1 }, { 205, 1 }, { 206, 1 },
 398                                         { 207, 1 }, { 900, 1 }, { 209, 1 }, { 400, 1 },
 399                                         { 800, 1 }, { 404, 1 }, { 406, 1 }, { 408, 1 },
 400                                         { 500, 1 }, { 502, 1 }, { 504, 1 }, { 506, 1 },
 401                                         { 508, 1 }, { 510, 1 }, { 512, 1 }, { 514, 1 },
 402                                         { 516, 1 }, { 518, 1 }, { 520, 1 }, { 522, 1 },
 403                                         { 524, 1 }, { 526, 1 }, { 528, 1 }, { 530, 1 },
 404                                         { 532, 1 }, { 534, 1 }, { 536, 1 }, { 538, 1 },
 405                                         { 540, 1 }, { 542, 1 }, { 700, 2 }, { 149, 1 },
 406                                         { 800, 1 }, { 151, 1 }, { 802, 1 }, { 153, 47 }));
 407
 408         // Some tests covering replacing the beginning and end
 409
 410         CHECK_REPLACE(0, E({ 100, 100 }), E({ 100, 100 }));
 411         CHECK_REPLACE(10, E({ 200, 90 }), E({ 100, 10 }, { 200, 90 }));
 412         CHECK_REPLACE(0, E({ 300, 10 }), E({ 300, 10 }, { 200, 90 }));
 413
 414         // Test replacing with multiple extents
 415         CHECK_REPLACE(5, E({ 400, 1 }, { 400, 2 }),
 416                                   E({ 300, 5 }, { 400, 1 }, { 400, 2 }, { 308, 2 }, { 200, 90 }));
 417
 418         /*
 419          * Test an unlikely case where we have lots of extents that could
 420          * be coalesced.  When replacing extents here, we can't coalesce
 421          * all of them because we will not be able to roll back.
 422          */
 423
 424         // First, set things up
 425         hfs_ext_iter_t iter;
 426
 427         assert(!hfs_ext_find(&vnode, 0, &iter));
 428
 429         for (int i = 0; i < 32768; i += 8) {
 430                 HFSPlusExtentRecord r = { { i, 1 }, { i + 1, 1 }, { i + 2, 1 }, { i + 3, 1 },
 431                                                                   { i + 4, 1 }, { i + 5, 1 }, { i + 6, 1 }, { i + 7, 1 } };
 432
 433                 hfs_ext_iter_update(&iter, r, 8, cat_extents);
 434         }
 435
 436         ffork.ff_blocks = 32768;
 437         ffork.ff_unallocblocks = 0;
 438
 439         /*
 440          * Now we have 32768 extents that could be coalesced.  Check the
 441          * following succeeds.
 442          */
 443         assert(!hfs_ext_replace(&mount, &vnode, 0,
 444                                                         E({ 1, 8 }), 1, cat_extents));
 445
 446         printf("[PASSED] hfs_extents_test\n");
 447
 448         return 0;
 449 }