The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/fs/hfs/extent.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    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 }

Cache object: 0299653b3155044ebe051a41a0b2ff08


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.