fs/hfs/extent.c

   1 /*
   2  * linux/fs/hfs/extent.c
   3  *
   4  * Copyright (C) 1995-1997  Paul H. Hargrove
   5  * This file may be distributed under the terms of the GNU General Public License.
   6  *
   7  * This file contains the functions related to the extents B-tree.
   8  *
   9  * "XXX" in a comment is a note to myself to consider changing something.
  10  *
  11  * In function preconditions the term "valid" applied to a pointer to
  12  * a structure means that the pointer is non-NULL and the structure it
  13  * points to has all fields initialized to consistent values.
  14  */
  15
  16 #include "hfs.h"
  17
  18 /*================ File-local data type ================*/
  19
  20 /* An extent record on disk*/
  21 struct hfs_raw_extent {
  22         hfs_word_t      block1;
  23         hfs_word_t      length1;
  24         hfs_word_t      block2;
  25         hfs_word_t      length2;
  26         hfs_word_t      block3;
  27         hfs_word_t      length3;
  28 };
  29
  30 /*================ File-local functions ================*/
  31
  32 /*
  33  * build_key
  34  */
  35 static inline void build_key(struct hfs_ext_key *key,
  36                              const struct hfs_fork *fork, hfs_u16 block)
  37 {
  38         key->KeyLen = 7;
  39         key->FkType = fork->fork;
  40         hfs_put_nl(fork->entry->cnid, key->FNum);
  41         hfs_put_hs(block,             key->FABN);
  42 }
  43
  44
  45 /*
  46  * lock_bitmap()
  47  *
  48  * Get an exclusive lock on the B-tree bitmap.
  49  */
  50 static inline void lock_bitmap(struct hfs_mdb *mdb) {
  51         while (mdb->bitmap_lock) {
  52                 hfs_sleep_on(&mdb->bitmap_wait);
  53         }
  54         mdb->bitmap_lock = 1;
  55 }
  56
  57 /*
  58  * unlock_bitmap()
  59  *
  60  * Relinquish an exclusive lock on the B-tree bitmap.
  61  */
  62 static inline void unlock_bitmap(struct hfs_mdb *mdb) {
  63         mdb->bitmap_lock = 0;
  64         hfs_wake_up(&mdb->bitmap_wait);
  65 }
  66
  67 /*
  68  * dump_ext()
  69  *
  70  * prints the content of a extent for debugging purposes.
  71  */
  72 #if defined(DEBUG_EXTENTS) || defined(DEBUG_ALL)
  73 static void dump_ext(const char *msg, const struct hfs_extent *e) {
  74         if (e) {
  75                 hfs_warn("%s (%d-%d) (%d-%d) (%d-%d)\n", msg,
  76                          e->start,
  77                          e->start + e->length[0] - 1,
  78                          e->start + e->length[0],
  79                          e->start + e->length[0] + e->length[1] - 1,
  80                          e->start + e->length[0] + e->length[1],
  81                          e->end);
  82         } else {
  83                 hfs_warn("%s NULL\n", msg);
  84         }
  85 }
  86 #else
  87 #define dump_ext(A,B) {}
  88 #endif
  89
  90 /*
  91  * read_extent()
  92  *
  93  * Initializes a (struct hfs_extent) from a (struct hfs_raw_extent) and
  94  * the number of the starting block for the extent.
  95  *
  96  * Note that the callers must check that to,from != NULL
  97  */
  98 static void read_extent(struct hfs_extent *to,
  99                         const struct hfs_raw_extent *from,
 100                         hfs_u16 start)
 101 {
 102         to->start = start;
 103         to->block[0]  = hfs_get_hs(from->block1);
 104         to->length[0] = hfs_get_hs(from->length1);
 105         to->block[1]  = hfs_get_hs(from->block2);
 106         to->length[1] = hfs_get_hs(from->length2);
 107         to->block[2]  = hfs_get_hs(from->block3);
 108         to->length[2] = hfs_get_hs(from->length3);
 109         to->end = start + to->length[0] + to->length[1] + to->length[2] - 1;
 110         to->next = to->prev = NULL;
 111         to->count = 0;
 112 }
 113
 114 /*
 115  * write_extent()
 116  *
 117  * Initializes a (struct hfs_raw_extent) from a (struct hfs_extent).
 118  *
 119  * Note that the callers must check that to,from != NULL
 120  */
 121 static void write_extent(struct hfs_raw_extent *to,
 122                          const struct hfs_extent *from)
 123 {
 124         hfs_put_hs(from->block[0], to->block1);
 125         hfs_put_hs(from->length[0], to->length1);
 126         hfs_put_hs(from->block[1], to->block2);
 127         hfs_put_hs(from->length[1], to->length2);
 128         hfs_put_hs(from->block[2], to->block3);
 129         hfs_put_hs(from->length[2], to->length3);
 130 }
 131
 132 /*
 133  * decode_extent()
 134  *
 135  * Given an extent record and allocation block offset into the file,
 136  * return the number of the corresponding allocation block on disk,
 137  * or -1 if the desired block is not mapped by the given extent.
 138  *
 139  * Note that callers must check that extent != NULL
 140  */
 141 static int decode_extent(const struct hfs_extent * extent, int block)
 142 {
 143         if (!extent || (block < extent->start) || (block > extent->end) ||
 144             (extent->end == (hfs_u16)(extent->start - 1))) {
 145                 return -1;
 146         }
 147         block -= extent->start;
 148         if (block < extent->length[0]) {
 149                 return block + extent->block[0];
 150         }
 151         block -= extent->length[0];
 152         if (block < extent->length[1]) {
 153                 return block + extent->block[1];
 154         }
 155         return block + extent->block[2] - extent->length[1];
 156 }
 157
 158 /*
 159  * relse_ext()
 160  *
 161  * Reduce the reference count of an in-core extent record by one,
 162  * removing it from memory if the count falls to zero.
 163  */
 164 static void relse_ext(struct hfs_extent *ext)
 165 {
 166         if (--ext->count || !ext->start) {
 167                 return;
 168         }
 169         ext->prev->next = ext->next;
 170         if (ext->next) {
 171                 ext->next->prev = ext->prev;
 172         }
 173         HFS_DELETE(ext);
 174 }
 175
 176 /*
 177  * set_cache()
 178  *
 179  * Changes the 'cache' field of the fork.
 180  */
 181 static inline void set_cache(struct hfs_fork *fork, struct hfs_extent *ext)
 182 {
 183         struct hfs_extent *tmp = fork->cache;
 184
 185         ++ext->count;
 186         fork->cache = ext;
 187         relse_ext(tmp);
 188 }
 189
 190 /*
 191  * find_ext()
 192  *
 193  * Given a pointer to a (struct hfs_file) and an allocation block
 194  * number in the file, find the extent record containing that block.
 195  * Returns a pointer to the extent record on success or NULL on failure.
 196  * The 'cache' field of 'fil' also points to the extent so it has a
 197  * reference count of at least 2.
 198  *
 199  * Callers must check that fil != NULL
 200  */
 201 static struct hfs_extent * find_ext(struct hfs_fork *fork, int alloc_block)
 202 {
 203         struct hfs_cat_entry *entry = fork->entry;
 204         struct hfs_btree *tr= entry->mdb->ext_tree;
 205         struct hfs_ext_key target, *key;
 206         struct hfs_brec brec;
 207         struct hfs_extent *ext, *ptr;
 208         int tmp;
 209
 210         if (alloc_block < 0) {
 211                 ext = &fork->first;
 212                 goto found;
 213         }
 214
 215         ext = fork->cache;
 216         if (!ext || (alloc_block < ext->start)) {
 217                 ext = &fork->first;
 218         }
 219         while (ext->next && (alloc_block > ext->end)) {
 220                 ext = ext->next;
 221         }
 222         if ((alloc_block <= ext->end) && (alloc_block >= ext->start)) {
 223                 goto found;
 224         }
 225
 226         /* time to read more extents */
 227         if (!HFS_NEW(ext)) {
 228                 goto bail3;
 229         }
 230
 231         build_key(&target, fork, alloc_block);
 232
 233         tmp = hfs_bfind(&brec, tr, HFS_BKEY(&target), HFS_BFIND_READ_LE);
 234         if (tmp < 0) {
 235                 goto bail2;
 236         }
 237
 238         key = (struct hfs_ext_key *)brec.key;
 239         if ((hfs_get_nl(key->FNum) != hfs_get_nl(target.FNum)) ||
 240             (key->FkType != fork->fork)) {
 241                 goto bail1;
 242         }
 243
 244         read_extent(ext, brec.data, hfs_get_hs(key->FABN));
 245         hfs_brec_relse(&brec, NULL);
 246
 247         if ((alloc_block > ext->end) && (alloc_block < ext->start)) {
 248                 /* something strange happened */
 249                 goto bail2;
 250         }
 251
 252         ptr = fork->cache;
 253         if (!ptr || (alloc_block < ptr->start)) {
 254                 ptr = &fork->first;
 255         }
 256         while (ptr->next && (alloc_block > ptr->end)) {
 257                 ptr = ptr->next;
 258         }
 259         if (ext->start == ptr->start) {
 260                 /* somebody beat us to it. */
 261                 HFS_DELETE(ext);
 262                 ext = ptr;
 263         } else if (ext->start < ptr->start) {
 264                 /* insert just before ptr */
 265                 ptr->prev->next = ext;
 266                 ext->prev = ptr->prev;
 267                 ext->next = ptr;
 268                 ptr->prev = ext;
 269         } else {
 270                 /* insert at end */
 271                 ptr->next = ext;
 272                 ext->prev = ptr;
 273         }
 274  found:
 275         ++ext->count; /* for return value */
 276         set_cache(fork, ext);
 277         return ext;
 278
 279  bail1:
 280         hfs_brec_relse(&brec, NULL);
 281  bail2:
 282         HFS_DELETE(ext);
 283  bail3:
 284         return NULL;
 285 }
 286
 287 /*
 288  * delete_extent()
 289  *
 290  * Description:
 291  *   Deletes an extent record from a fork, reducing its physical length.
 292  * Input Variable(s):
 293  *   struct hfs_fork *fork: the fork
 294  *   struct hfs_extent *ext: the current last extent for 'fork'
 295  * Output Variable(s):
 296  *   NONE
 297  * Returns:
 298  *   void
 299  * Preconditions:
 300  *   'fork' points to a valid (struct hfs_fork)
 301  *   'ext' point to a valid (struct hfs_extent) which is the last in 'fork'
 302  *    and which is not also the first extent in 'fork'.
 303  * Postconditions:
 304  *   The extent record has been removed if possible, and a warning has been
 305  *   printed otherwise.
 306  */
 307 static void delete_extent(struct hfs_fork *fork, struct hfs_extent *ext)
 308 {
 309         struct hfs_mdb *mdb = fork->entry->mdb;
 310         struct hfs_ext_key key;
 311         int error;
 312
 313         if (fork->cache == ext) {
 314                 set_cache(fork, ext->prev);
 315         }
 316         ext->prev->next = NULL;
 317         if (ext->count != 1) {
 318                 hfs_warn("hfs_truncate: extent has count %d.\n", ext->count);
 319         }
 320
 321         lock_bitmap(mdb);
 322         error = hfs_clear_vbm_bits(mdb, ext->block[2], ext->length[2]);
 323         if (error) {
 324                 hfs_warn("hfs_truncate: error %d freeing blocks.\n", error);
 325         }
 326         error = hfs_clear_vbm_bits(mdb, ext->block[1], ext->length[1]);
 327         if (error) {
 328                 hfs_warn("hfs_truncate: error %d freeing blocks.\n", error);
 329         }
 330         error = hfs_clear_vbm_bits(mdb, ext->block[0], ext->length[0]);
 331         if (error) {
 332                 hfs_warn("hfs_truncate: error %d freeing blocks.\n", error);
 333         }
 334         unlock_bitmap(mdb);
 335
 336         build_key(&key, fork, ext->start);
 337
 338         error = hfs_bdelete(mdb->ext_tree, HFS_BKEY(&key));
 339         if (error) {
 340                 hfs_warn("hfs_truncate: error %d deleting an extent.\n", error);
 341         }
 342
 343         HFS_DELETE(ext);
 344 }
 345
 346 /*
 347  * new_extent()
 348  *
 349  * Description:
 350  *   Adds a new extent record to a fork, extending its physical length.
 351  * Input Variable(s):
 352  *   struct hfs_fork *fork: the fork to extend
 353  *   struct hfs_extent *ext: the current last extent for 'fork'
 354  *   hfs_u16 ablock: the number of allocation blocks in 'fork'.
 355  *   hfs_u16 start: first allocation block to add to 'fork'.
 356  *   hfs_u16 len: the number of allocation blocks to add to 'fork'.
 357  *   hfs_u32 ablksz: number of sectors in an allocation block.
 358  * Output Variable(s):
 359  *   NONE
 360  * Returns:
 361  *   (struct hfs_extent *) the new extent or NULL
 362  * Preconditions:
 363  *   'fork' points to a valid (struct hfs_fork)
 364  *   'ext' point to a valid (struct hfs_extent) which is the last in 'fork'
 365  *   'ablock', 'start', 'len' and 'ablksz' are what they claim to be.
 366  * Postconditions:
 367  *   If NULL is returned then no changes have been made to 'fork'.
 368  *   If the return value is non-NULL that it is the extent that has been
 369  *   added to 'fork' both in memory and on disk.  The 'psize' field of
 370  *   'fork' has been updated to reflect the new physical size.
 371  */
 372 static struct hfs_extent *new_extent(struct hfs_fork *fork,
 373                                      struct hfs_extent *ext,
 374                                      hfs_u16 ablock, hfs_u16 start,
 375                                      hfs_u16 len, hfs_u16 ablksz)
 376 {
 377         struct hfs_raw_extent raw;
 378         struct hfs_ext_key key;
 379         int error;
 380
 381         if (fork->entry->cnid == htonl(HFS_EXT_CNID)) {
 382                 /* Limit extents tree to the record in the MDB */
 383                 return NULL;
 384         }
 385
 386         if (!HFS_NEW(ext->next)) {
 387                 return NULL;
 388         }
 389         ext->next->prev = ext;
 390         ext->next->next = NULL;
 391         ext = ext->next;
 392         relse_ext(ext->prev);
 393
 394         ext->start = ablock;
 395         ext->block[0] = start;
 396         ext->length[0] = len;
 397         ext->block[1] = 0;
 398         ext->length[1] = 0;
 399         ext->block[2] = 0;
 400         ext->length[2] = 0;
 401         ext->end = ablock + len - 1;
 402         ext->count = 1;
 403
 404         write_extent(&raw, ext);
 405
 406         build_key(&key, fork, ablock);
 407
 408         error = hfs_binsert(fork->entry->mdb->ext_tree,
 409                             HFS_BKEY(&key), &raw, sizeof(raw));
 410         if (error) {
 411                 ext->prev->next = NULL;
 412                 HFS_DELETE(ext);
 413                 return NULL;
 414         }
 415         set_cache(fork, ext);
 416         return ext;
 417 }
 418
 419 /*
 420  * update_ext()
 421  *
 422  * Given a (struct hfs_fork) write an extent record back to disk.
 423  */
 424 static void update_ext(struct hfs_fork *fork, struct hfs_extent *ext)
 425 {
 426         struct hfs_ext_key target;
 427         struct hfs_brec brec;
 428
 429         if (ext->start) {
 430                 build_key(&target, fork, ext->start);
 431
 432                 if (!hfs_bfind(&brec, fork->entry->mdb->ext_tree,
 433                                HFS_BKEY(&target), HFS_BFIND_WRITE)) {
 434                         write_extent(brec.data, ext);
 435                         hfs_brec_relse(&brec, NULL);
 436                 }
 437         }
 438 }
 439
 440 /*
 441  * zero_blocks()
 442  *
 443  * Zeros-out 'num' allocation blocks beginning with 'start'.
 444  */
 445 static int zero_blocks(struct hfs_mdb *mdb, int start, int num) {
 446         hfs_buffer buf;
 447         int end;
 448         int j;
 449
 450         start = mdb->fs_start + start * mdb->alloc_blksz;
 451         end = start + num * mdb->alloc_blksz;
 452
 453         for (j=start; j<end; ++j) {
 454                 if (hfs_buffer_ok(buf = hfs_buffer_get(mdb->sys_mdb, j, 0))) {
 455                         memset(hfs_buffer_data(buf), 0, HFS_SECTOR_SIZE);
 456                         hfs_buffer_dirty(buf);
 457                         hfs_buffer_put(buf);
 458                 }
 459         }
 460         return 0;
 461 }
 462
 463 /*
 464  * shrink_fork()
 465  *
 466  * Try to remove enough allocation blocks from 'fork'
 467  * so that it is 'ablocks' allocation blocks long.
 468  */
 469 static void shrink_fork(struct hfs_fork *fork, int ablocks)
 470 {
 471         struct hfs_mdb *mdb = fork->entry->mdb;
 472         struct hfs_extent *ext;
 473         int i, error, next, count;
 474         hfs_u32 ablksz = mdb->alloc_blksz;
 475
 476         next =  (fork->psize / ablksz) - 1;
 477         ext = find_ext(fork, next);
 478         while (ext && ext->start && (ext->start >= ablocks)) {
 479                 next = ext->start - 1;
 480                 delete_extent(fork, ext);
 481                 ext = find_ext(fork, next);
 482         }
 483         if (!ext) {
 484                 fork->psize = (next + 1) * ablksz;
 485                 return;
 486         }
 487
 488         if ((count = next + 1 - ablocks) > 0) {
 489                 for (i=2; (i>=0) && !ext->length[i]; --i) {};
 490                 lock_bitmap(mdb);
 491                 while (count && (ext->length[i] <= count)) {
 492                         ext->end -= ext->length[i];
 493                         count -= ext->length[i];
 494                         error = hfs_clear_vbm_bits(mdb, ext->block[i],
 495                                                    ext->length[i]);
 496                         if (error) {
 497                                 hfs_warn("hfs_truncate: error %d freeing "
 498                                        "blocks.\n", error);
 499                         }
 500                         ext->block[i] = ext->length[i] = 0;
 501                         --i;
 502                 }
 503                 if (count) {
 504                         ext->end -= count;
 505                         ext->length[i] -= count;
 506                         error = hfs_clear_vbm_bits(mdb, ext->block[i] +
 507                                                        ext->length[i], count);
 508                         if (error) {
 509                                 hfs_warn("hfs_truncate: error %d freeing "
 510                                        "blocks.\n", error);
 511                         }
 512                 }
 513                 unlock_bitmap(mdb);
 514                 update_ext(fork, ext);
 515         }
 516
 517         fork->psize = ablocks * ablksz;
 518 }
 519
 520 /*
 521  * grow_fork()
 522  *
 523  * Try to add enough allocation blocks to 'fork'
 524  * so that it is 'ablock' allocation blocks long.
 525  */
 526 static int grow_fork(struct hfs_fork *fork, int ablocks)
 527 {
 528         struct hfs_cat_entry *entry = fork->entry;
 529         struct hfs_mdb *mdb = entry->mdb;
 530         struct hfs_extent *ext;
 531         int i, start, err;
 532         hfs_u16 need, len=0;
 533         hfs_u32 ablksz = mdb->alloc_blksz;
 534         hfs_u32 blocks, clumpablks;
 535
 536         blocks = fork->psize;
 537         need = ablocks - blocks/ablksz;
 538         if (need < 1) { /* no need to grow the fork */
 539                 return 0;
 540         }
 541
 542         /* round up to clumpsize */
 543         if (entry->u.file.clumpablks) {
 544                 clumpablks = entry->u.file.clumpablks;
 545         } else {
 546                 clumpablks = mdb->clumpablks;
 547         }
 548         need = ((need + clumpablks - 1) / clumpablks) * clumpablks;
 549
 550         /* find last extent record and try to extend it */
 551         if (!(ext = find_ext(fork, blocks/ablksz - 1))) {
 552                 /* somehow we couldn't find the end of the file! */
 553                 return -1;
 554         }
 555
 556         /* determine which is the last used extent in the record */
 557         /* then try to allocate the blocks immediately following it */
 558         for (i=2; (i>=0) && !ext->length[i]; --i) {};
 559         if (i>=0) {
 560                 /* try to extend the last extent */
 561                 start = ext->block[i] + ext->length[i];
 562
 563                 err = 0;
 564                 lock_bitmap(mdb);
 565                 len = hfs_vbm_count_free(mdb, start);
 566                 if (!len) {
 567                         unlock_bitmap(mdb);
 568                         goto more_extents;
 569                 }
 570                 if (need < len) {
 571                         len = need;
 572                 }
 573                 err = hfs_set_vbm_bits(mdb, start, len);
 574                 unlock_bitmap(mdb);
 575                 if (err) {
 576                         relse_ext(ext);
 577                         return -1;
 578                 }
 579
 580                 zero_blocks(mdb, start, len);
 581
 582                 ext->length[i] += len;
 583                 ext->end += len;
 584                 blocks = (fork->psize += len * ablksz);
 585                 need -= len;
 586                 update_ext(fork, ext);
 587         }
 588
 589 more_extents:
 590         /* add some more extents */
 591         while (need) {
 592                 len = need;
 593                 err = 0;
 594                 lock_bitmap(mdb);
 595                 start = hfs_vbm_search_free(mdb, &len);
 596                 if (need < len) {
 597                         len = need;
 598                 }
 599                 err = hfs_set_vbm_bits(mdb, start, len);
 600                 unlock_bitmap(mdb);
 601                 if (!len || err) {
 602                         relse_ext(ext);
 603                         return -1;
 604                 }
 605                 zero_blocks(mdb, start, len);
 606
 607                 /* determine which is the first free extent in the record */
 608                 for (i=0; (i<3) && ext->length[i]; ++i) {};
 609                 if (i < 3) {
 610                         ext->block[i] = start;
 611                         ext->length[i] = len;
 612                         ext->end += len;
 613                         update_ext(fork, ext);
 614                 } else {
 615                         if (!(ext = new_extent(fork, ext, blocks/ablksz,
 616                                                start, len, ablksz))) {
 617                                 lock_bitmap(mdb);
 618                                 hfs_clear_vbm_bits(mdb, start, len);
 619                                 unlock_bitmap(mdb);
 620                                 return -1;
 621                         }
 622                 }
 623                 blocks = (fork->psize += len * ablksz);
 624                 need -= len;
 625         }
 626         set_cache(fork, ext);
 627         relse_ext(ext);
 628         return 0;
 629 }
 630
 631 /*================ Global functions ================*/
 632
 633 /*
 634  * hfs_ext_compare()
 635  *
 636  * Description:
 637  *   This is the comparison function used for the extents B-tree.  In
 638  *   comparing extent B-tree entries, the file id is the most
 639  *   significant field (compared as unsigned ints); the fork type is
 640  *   the second most significant field (compared as unsigned chars);
 641  *   and the allocation block number field is the least significant
 642  *   (compared as unsigned ints).
 643  * Input Variable(s):
 644  *   struct hfs_ext_key *key1: pointer to the first key to compare
 645  *   struct hfs_ext_key *key2: pointer to the second key to compare
 646  * Output Variable(s):
 647  *   NONE
 648  * Returns:
 649  *   int: negative if key1<key2, positive if key1>key2, and 0 if key1==key2
 650  * Preconditions:
 651  *   key1 and key2 point to "valid" (struct hfs_ext_key)s.
 652  * Postconditions:
 653  *   This function has no side-effects */
 654 int hfs_ext_compare(const struct hfs_ext_key *key1,
 655                     const struct hfs_ext_key *key2)
 656 {
 657         unsigned int tmp;
 658         int retval;
 659
 660         tmp = hfs_get_hl(key1->FNum) - hfs_get_hl(key2->FNum);
 661         if (tmp != 0) {
 662                 retval = (int)tmp;
 663         } else {
 664                 tmp = (unsigned char)key1->FkType - (unsigned char)key2->FkType;
 665                 if (tmp != 0) {
 666                         retval = (int)tmp;
 667                 } else {
 668                         retval = (int)(hfs_get_hs(key1->FABN)
 669                                        - hfs_get_hs(key2->FABN));
 670                 }
 671         }
 672         return retval;
 673 }
 674
 675 /*
 676  * hfs_extent_adj()
 677  *
 678  * Given an hfs_fork shrink or grow the fork to hold the
 679  * forks logical size.
 680  */
 681 void hfs_extent_adj(struct hfs_fork *fork)
 682 {
 683         if (fork) {
 684                 hfs_u32 blks, ablocks, ablksz;
 685
 686                 if (fork->lsize > HFS_FORK_MAX) {
 687                         fork->lsize = HFS_FORK_MAX;
 688                 }
 689
 690                 blks = (fork->lsize+HFS_SECTOR_SIZE-1) >> HFS_SECTOR_SIZE_BITS;
 691                 ablksz = fork->entry->mdb->alloc_blksz;
 692                 ablocks = (blks + ablksz - 1) / ablksz;
 693
 694                 if (blks > fork->psize) {
 695                         grow_fork(fork, ablocks);
 696                         if (blks > fork->psize) {
 697                                 fork->lsize =
 698                                         fork->psize >> HFS_SECTOR_SIZE_BITS;
 699                         }
 700                 } else if (blks < fork->psize) {
 701                         shrink_fork(fork, ablocks);
 702                 }
 703         }
 704 }
 705
 706 /*
 707  * hfs_extent_map()
 708  *
 709  * Given an hfs_fork and a block number within the fork, return the
 710  * number of the corresponding physical block on disk, or zero on
 711  * error.
 712  */
 713 int hfs_extent_map(struct hfs_fork *fork, int block, int create)
 714 {
 715         int ablksz, ablock, offset, tmp;
 716         struct hfs_extent *ext;
 717
 718         if (!fork || !fork->entry || !fork->entry->mdb) {
 719                 return 0;
 720         }
 721
 722 #if defined(DEBUG_EXTENTS) || defined(DEBUG_ALL)
 723         hfs_warn("hfs_extent_map: ablock %d of file %d, fork %d\n",
 724                  block, fork->entry->cnid, fork->fork);
 725 #endif
 726
 727         if (block < 0) {
 728                 hfs_warn("hfs_extent_map: block < 0\n");
 729                 return 0;
 730         }
 731         if (block > (HFS_FORK_MAX >> HFS_SECTOR_SIZE_BITS)) {
 732                 hfs_warn("hfs_extent_map: block(0x%08x) > big; cnid=%d "
 733                          "fork=%d\n", block, fork->entry->cnid, fork->fork);
 734                 return 0;
 735         }
 736         ablksz = fork->entry->mdb->alloc_blksz;
 737         offset = fork->entry->mdb->fs_start + (block % ablksz);
 738         ablock = block / ablksz;
 739
 740         if (block >= fork->psize) {
 741                 if (!create || (grow_fork(fork, ablock + 1) < 0))
 742                         return 0;
 743         }
 744
 745 #if defined(DEBUG_EXTENTS) || defined(DEBUG_ALL)
 746         hfs_warn("(lblock %d offset %d)\n", ablock, offset);
 747 #endif
 748
 749         if ((ext = find_ext(fork, ablock))) {
 750                 dump_ext("trying new: ", ext);
 751                 tmp = decode_extent(ext, ablock);
 752                 relse_ext(ext);
 753                 if (tmp >= 0) {
 754                         return tmp*ablksz + offset;
 755                 }
 756         }
 757
 758         return 0;
 759 }
 760
 761 /*
 762  * hfs_extent_out()
 763  *
 764  * Copy the first extent record from a (struct hfs_fork) to a (struct
 765  * raw_extent), record (normally the one in the catalog entry).
 766  */
 767 void hfs_extent_out(const struct hfs_fork *fork, hfs_byte_t dummy[12])
 768 {
 769         struct hfs_raw_extent *ext = (struct hfs_raw_extent *)dummy;
 770
 771         if (fork && ext) {
 772                 write_extent(ext, &fork->first);
 773                 dump_ext("extent out: ", &fork->first);
 774         }
 775 }
 776
 777 /*
 778  * hfs_extent_in()
 779  *
 780  * Copy an raw_extent to the 'first' and 'cache' fields of an hfs_fork.
 781  */
 782 void hfs_extent_in(struct hfs_fork *fork, const hfs_byte_t dummy[12])
 783 {
 784         const struct hfs_raw_extent *ext =
 785                 (const struct hfs_raw_extent *)dummy;
 786
 787         if (fork && ext) {
 788                 read_extent(&fork->first, ext, 0);
 789                 fork->cache = &fork->first;
 790                 fork->first.count = 2;
 791                 dump_ext("extent in: ", &fork->first);
 792         }
 793 }
 794
 795 /*
 796  * hfs_extent_free()
 797  *
 798  * Removes from memory all extents associated with 'fil'.
 799  */
 800 void hfs_extent_free(struct hfs_fork *fork)
 801 {
 802         if (fork) {
 803                 set_cache(fork, &fork->first);
 804
 805                 if (fork->first.next) {
 806                         hfs_warn("hfs_extent_free: extents in use!\n");
 807                 }
 808         }
 809 }