fs/hfs/extent.c

   1 /*
   2  *  linux/fs/hfs/extent.c
   3  *
   4  * Copyright (C) 1995-1997  Paul H. Hargrove
   5  * (C) 2003 Ardis Technologies <roman@ardistech.com>
   6  * This file may be distributed under the terms of the GNU General Public License.
   7  *
   8  * This file contains the functions related to the extents B-tree.
   9  */
  10
  11 #include <linux/pagemap.h>
  12
  13 #include "hfs_fs.h"
  14 #include "btree.h"
  15
  16 /*================ File-local functions ================*/
  17
  18 /*
  19  * build_key
  20  */
  21 static void hfs_ext_build_key(hfs_btree_key *key, u32 cnid, u16 block, u8 type)
  22 {
  23         key->key_len = 7;
  24         key->ext.FkType = type;
  25         key->ext.FNum = cpu_to_be32(cnid);
  26         key->ext.FABN = cpu_to_be16(block);
  27 }
  28
  29 /*
  30  * hfs_ext_compare()
  31  *
  32  * Description:
  33  *   This is the comparison function used for the extents B-tree.  In
  34  *   comparing extent B-tree entries, the file id is the most
  35  *   significant field (compared as unsigned ints); the fork type is
  36  *   the second most significant field (compared as unsigned chars);
  37  *   and the allocation block number field is the least significant
  38  *   (compared as unsigned ints).
  39  * Input Variable(s):
  40  *   struct hfs_ext_key *key1: pointer to the first key to compare
  41  *   struct hfs_ext_key *key2: pointer to the second key to compare
  42  * Output Variable(s):
  43  *   NONE
  44  * Returns:
  45  *   int: negative if key1<key2, positive if key1>key2, and 0 if key1==key2
  46  * Preconditions:
  47  *   key1 and key2 point to "valid" (struct hfs_ext_key)s.
  48  * Postconditions:
  49  *   This function has no side-effects */
  50 int hfs_ext_keycmp(const btree_key *key1, const btree_key *key2)
  51 {
  52         unsigned int tmp;
  53         int retval;
  54
  55         tmp = be32_to_cpu(key1->ext.FNum) - be32_to_cpu(key2->ext.FNum);
  56         if (tmp != 0) {
  57                 retval = (int)tmp;
  58         } else {
  59                 tmp = (unsigned char)key1->ext.FkType - (unsigned char)key2->ext.FkType;
  60                 if (tmp != 0) {
  61                         retval = (int)tmp;
  62                 } else {
  63                         retval = (int)(be16_to_cpu(key1->ext.FABN)
  64                                        - be16_to_cpu(key2->ext.FABN));
  65                 }
  66         }
  67         return retval;
  68 }
  69
  70 /*
  71  * hfs_ext_find_block
  72  *
  73  * Find a block within an extent record
  74  */
  75 static u16 hfs_ext_find_block(struct hfs_extent *ext, u16 off)
  76 {
  77         int i;
  78         u16 count;
  79
  80         for (i = 0; i < 3; ext++, i++) {
  81                 count = be16_to_cpu(ext->count);
  82                 if (off < count)
  83                         return be16_to_cpu(ext->block) + off;
  84                 off -= count;
  85         }
  86         /* panic? */
  87         return 0;
  88 }
  89
  90 static int hfs_ext_block_count(struct hfs_extent *ext)
  91 {
  92         int i;
  93         u16 count = 0;
  94
  95         for (i = 0; i < 3; ext++, i++)
  96                 count += be16_to_cpu(ext->count);
  97         return count;
  98 }
  99
 100 static u16 hfs_ext_lastblock(struct hfs_extent *ext)
 101 {
 102         int i;
 103
 104         ext += 2;
 105         for (i = 0; i < 2; ext--, i++)
 106                 if (ext->count)
 107                         break;
 108         return be16_to_cpu(ext->block) + be16_to_cpu(ext->count);
 109 }
 110
 111 static void __hfs_ext_write_extent(struct inode *inode, struct hfs_find_data *fd)
 112 {
 113         int res;
 114
 115         hfs_ext_build_key(fd->search_key, inode->i_ino, HFS_I(inode)->cached_start,
 116                           HFS_IS_RSRC(inode) ?  HFS_FK_RSRC : HFS_FK_DATA);
 117         res = hfs_brec_find(fd);
 118         if (HFS_I(inode)->flags & HFS_FLG_EXT_NEW) {
 119                 if (res != -ENOENT)
 120                         return;
 121                 hfs_brec_insert(fd, HFS_I(inode)->cached_extents, sizeof(hfs_extent_rec));
 122                 HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
 123         } else {
 124                 if (res)
 125                         return;
 126                 hfs_bnode_write(fd->bnode, HFS_I(inode)->cached_extents, fd->entryoffset, fd->entrylength);
 127                 HFS_I(inode)->flags &= ~HFS_FLG_EXT_DIRTY;
 128         }
 129 }
 130
 131 void hfs_ext_write_extent(struct inode *inode)
 132 {
 133         struct hfs_find_data fd;
 134
 135         if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY) {
 136                 hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
 137                 __hfs_ext_write_extent(inode, &fd);
 138                 hfs_find_exit(&fd);
 139         }
 140 }
 141
 142 static inline int __hfs_ext_read_extent(struct hfs_find_data *fd, struct hfs_extent *extent,
 143                                         u32 cnid, u32 block, u8 type)
 144 {
 145         int res;
 146
 147         hfs_ext_build_key(fd->search_key, cnid, block, type);
 148         fd->key->ext.FNum = 0;
 149         res = hfs_brec_find(fd);
 150         if (res && res != -ENOENT)
 151                 return res;
 152         if (fd->key->ext.FNum != fd->search_key->ext.FNum ||
 153             fd->key->ext.FkType != fd->search_key->ext.FkType)
 154                 return -ENOENT;
 155         if (fd->entrylength != sizeof(hfs_extent_rec))
 156                 return -EIO;
 157         hfs_bnode_read(fd->bnode, extent, fd->entryoffset, sizeof(hfs_extent_rec));
 158         return 0;
 159 }
 160
 161 static inline int __hfs_ext_cache_extent(struct hfs_find_data *fd, struct inode *inode, u32 block)
 162 {
 163         int res;
 164
 165         if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY)
 166                 __hfs_ext_write_extent(inode, fd);
 167
 168         res = __hfs_ext_read_extent(fd, HFS_I(inode)->cached_extents, inode->i_ino,
 169                                     block, HFS_IS_RSRC(inode) ? HFS_FK_RSRC : HFS_FK_DATA);
 170         if (!res) {
 171                 HFS_I(inode)->cached_start = be16_to_cpu(fd->key->ext.FABN);
 172                 HFS_I(inode)->cached_blocks = hfs_ext_block_count(HFS_I(inode)->cached_extents);
 173         } else {
 174                 HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0;
 175                 HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
 176         }
 177         return res;
 178 }
 179
 180 static int hfs_ext_read_extent(struct inode *inode, u16 block)
 181 {
 182         struct hfs_find_data fd;
 183         int res;
 184
 185         if (block >= HFS_I(inode)->cached_start &&
 186             block < HFS_I(inode)->cached_start + HFS_I(inode)->cached_blocks)
 187                 return 0;
 188
 189         hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
 190         res = __hfs_ext_cache_extent(&fd, inode, block);
 191         hfs_find_exit(&fd);
 192         return res;
 193 }
 194
 195 static void hfs_dump_extent(struct hfs_extent *extent)
 196 {
 197         int i;
 198
 199         dprint(DBG_EXTENT, "   ");
 200         for (i = 0; i < 3; i++)
 201                 dprint(DBG_EXTENT, " %u:%u", be16_to_cpu(extent[i].block),
 202                                  be16_to_cpu(extent[i].count));
 203         dprint(DBG_EXTENT, "\n");
 204 }
 205
 206 static int hfs_add_extent(struct hfs_extent *extent, u16 offset,
 207                           u16 alloc_block, u16 block_count)
 208 {
 209         u16 count, start;
 210         int i;
 211
 212         hfs_dump_extent(extent);
 213         for (i = 0; i < 3; extent++, i++) {
 214                 count = be16_to_cpu(extent->count);
 215                 if (offset == count) {
 216                         start = be16_to_cpu(extent->block);
 217                         if (alloc_block != start + count) {
 218                                 if (++i >= 3)
 219                                         return -ENOSPC;
 220                                 extent++;
 221                                 extent->block = cpu_to_be16(alloc_block);
 222                         } else
 223                                 block_count += count;
 224                         extent->count = cpu_to_be16(block_count);
 225                         return 0;
 226                 } else if (offset < count)
 227                         break;
 228                 offset -= count;
 229         }
 230         /* panic? */
 231         return -EIO;
 232 }
 233
 234 int hfs_free_extents(struct super_block *sb, struct hfs_extent *extent,
 235                      u16 offset, u16 block_nr)
 236 {
 237         u16 count, start;
 238         int i;
 239
 240         hfs_dump_extent(extent);
 241         for (i = 0; i < 3; extent++, i++) {
 242                 count = be16_to_cpu(extent->count);
 243                 if (offset == count)
 244                         goto found;
 245                 else if (offset < count)
 246                         break;
 247                 offset -= count;
 248         }
 249         /* panic? */
 250         return -EIO;
 251 found:
 252         for (;;) {
 253                 start = be16_to_cpu(extent->block);
 254                 if (count <= block_nr) {
 255                         hfs_clear_vbm_bits(sb, start, count);
 256                         extent->block = 0;
 257                         extent->count = 0;
 258                         block_nr -= count;
 259                 } else {
 260                         count -= block_nr;
 261                         hfs_clear_vbm_bits(sb, start + count, block_nr);
 262                         extent->count = cpu_to_be16(count);
 263                         block_nr = 0;
 264                 }
 265                 if (!block_nr || !i)
 266                         return 0;
 267                 i--;
 268                 extent--;
 269                 count = be16_to_cpu(extent->count);
 270         }
 271 }
 272
 273 int hfs_free_fork(struct super_block *sb, struct hfs_cat_file *file, int type)
 274 {
 275         struct hfs_find_data fd;
 276         u32 total_blocks, blocks, start;
 277         u32 cnid = be32_to_cpu(file->FlNum);
 278         struct hfs_extent *extent;
 279         int res, i;
 280
 281         if (type == HFS_FK_DATA) {
 282                 total_blocks = file->PyLen;
 283                 extent = file->ExtRec;
 284         } else {
 285                 total_blocks = file->RPyLen;
 286                 extent = file->RExtRec;
 287         }
 288         total_blocks = be32_to_cpu(total_blocks) / HFS_SB(sb)->alloc_blksz;
 289         if (!total_blocks)
 290                 return 0;
 291
 292         blocks = 0;
 293         for (i = 0; i < 3; extent++, i++)
 294                 blocks += be16_to_cpu(extent[i].count);
 295
 296         res = hfs_free_extents(sb, extent, blocks, blocks);
 297         if (res)
 298                 return res;
 299         if (total_blocks == blocks)
 300                 return 0;
 301
 302         hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
 303         do {
 304                 res = __hfs_ext_read_extent(&fd, extent, cnid, total_blocks, type);
 305                 if (res)
 306                         break;
 307                 start = be16_to_cpu(fd.key->ext.FABN);
 308                 hfs_free_extents(sb, extent, total_blocks - start, total_blocks);
 309                 hfs_brec_remove(&fd);
 310                 total_blocks = start;
 311         } while (total_blocks > blocks);
 312         hfs_find_exit(&fd);
 313
 314         return res;
 315 }
 316
 317 /*
 318  * hfs_get_block
 319  */
 320 int hfs_get_block(struct inode *inode, sector_t block,
 321                   struct buffer_head *bh_result, int create)
 322 {
 323         struct super_block *sb;
 324         u16 dblock, ablock;
 325         int res;
 326
 327         sb = inode->i_sb;
 328         /* Convert inode block to disk allocation block */
 329         ablock = (u32)block / HFS_SB(sb)->fs_div;
 330
 331         if (block >= inode->i_blocks) {
 332                 if (block > inode->i_blocks || !create)
 333                         return -EIO;
 334                 if (ablock >= HFS_I(inode)->alloc_blocks) {
 335                         res = hfs_extend_file(inode);
 336                         if (res)
 337                                 return res;
 338                 }
 339         } else
 340                 create = 0;
 341
 342         if (ablock < HFS_I(inode)->first_blocks) {
 343                 dblock = hfs_ext_find_block(HFS_I(inode)->first_extents, ablock);
 344                 goto done;
 345         }
 346
 347         down(&HFS_I(inode)->extents_lock);
 348         res = hfs_ext_read_extent(inode, ablock);
 349         if (!res)
 350                 dblock = hfs_ext_find_block(HFS_I(inode)->cached_extents,
 351                                             ablock - HFS_I(inode)->cached_start);
 352         else {
 353                 up(&HFS_I(inode)->extents_lock);
 354                 return -EIO;
 355         }
 356         up(&HFS_I(inode)->extents_lock);
 357
 358 done:
 359         map_bh(bh_result, sb, HFS_SB(sb)->fs_start +
 360                dblock * HFS_SB(sb)->fs_div +
 361                (u32)block % HFS_SB(sb)->fs_div);
 362
 363         if (create) {
 364                 set_buffer_new(bh_result);
 365                 HFS_I(inode)->phys_size += sb->s_blocksize;
 366                 inode->i_blocks++;
 367                 mark_inode_dirty(inode);
 368         }
 369         return 0;
 370 }
 371
 372 int hfs_extend_file(struct inode *inode)
 373 {
 374         struct super_block *sb = inode->i_sb;
 375         u32 start, len, goal;
 376         int res;
 377
 378         down(&HFS_I(inode)->extents_lock);
 379         if (HFS_I(inode)->alloc_blocks == HFS_I(inode)->first_blocks)
 380                 goal = hfs_ext_lastblock(HFS_I(inode)->first_extents);
 381         else {
 382                 res = hfs_ext_read_extent(inode, HFS_I(inode)->alloc_blocks);
 383                 if (res)
 384                         goto out;
 385                 goal = hfs_ext_lastblock(HFS_I(inode)->cached_extents);
 386         }
 387
 388         len = HFS_I(inode)->clump_blocks;
 389         start = hfs_vbm_search_free(sb, goal, &len);
 390         if (!len) {
 391                 res = -ENOSPC;
 392                 goto out;
 393         }
 394
 395         dprint(DBG_EXTENT, "extend %lu: %u,%u\n", inode->i_ino, start, len);
 396         if (HFS_I(inode)->alloc_blocks == HFS_I(inode)->first_blocks) {
 397                 if (!HFS_I(inode)->first_blocks) {
 398                         dprint(DBG_EXTENT, "first extents\n");
 399                         /* no extents yet */
 400                         HFS_I(inode)->first_extents[0].block = cpu_to_be16(start);
 401                         HFS_I(inode)->first_extents[0].count = cpu_to_be16(len);
 402                         res = 0;
 403                 } else {
 404                         /* try to append to extents in inode */
 405                         res = hfs_add_extent(HFS_I(inode)->first_extents,
 406                                              HFS_I(inode)->alloc_blocks,
 407                                              start, len);
 408                         if (res == -ENOSPC)
 409                                 goto insert_extent;
 410                 }
 411                 if (!res) {
 412                         hfs_dump_extent(HFS_I(inode)->first_extents);
 413                         HFS_I(inode)->first_blocks += len;
 414                 }
 415         } else {
 416                 res = hfs_add_extent(HFS_I(inode)->cached_extents,
 417                                      HFS_I(inode)->alloc_blocks -
 418                                      HFS_I(inode)->cached_start,
 419                                      start, len);
 420                 if (!res) {
 421                         hfs_dump_extent(HFS_I(inode)->cached_extents);
 422                         HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY;
 423                         HFS_I(inode)->cached_blocks += len;
 424                 } else if (res == -ENOSPC)
 425                         goto insert_extent;
 426         }
 427 out:
 428         up(&HFS_I(inode)->extents_lock);
 429         if (!res) {
 430                 HFS_I(inode)->alloc_blocks += len;
 431                 mark_inode_dirty(inode);
 432                 if (inode->i_ino < HFS_FIRSTUSER_CNID)
 433                         set_bit(HFS_FLG_ALT_MDB_DIRTY, &HFS_SB(sb)->flags);
 434                 set_bit(HFS_FLG_MDB_DIRTY, &HFS_SB(sb)->flags);
 435                 sb->s_dirt = 1;
 436         }
 437         return res;
 438
 439 insert_extent:
 440         dprint(DBG_EXTENT, "insert new extent\n");
 441         hfs_ext_write_extent(inode);
 442
 443         memset(HFS_I(inode)->cached_extents, 0, sizeof(hfs_extent_rec));
 444         HFS_I(inode)->cached_extents[0].block = cpu_to_be16(start);
 445         HFS_I(inode)->cached_extents[0].count = cpu_to_be16(len);
 446         hfs_dump_extent(HFS_I(inode)->cached_extents);
 447         HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW;
 448         HFS_I(inode)->cached_start = HFS_I(inode)->alloc_blocks;
 449         HFS_I(inode)->cached_blocks = len;
 450
 451         res = 0;
 452         goto out;
 453 }
 454
 455 void hfs_file_truncate(struct inode *inode)
 456 {
 457         struct super_block *sb = inode->i_sb;
 458         struct hfs_find_data fd;
 459         u16 blk_cnt, alloc_cnt, start;
 460         u32 size;
 461         int res;
 462
 463         dprint(DBG_INODE, "truncate: %lu, %Lu -> %Lu\n", inode->i_ino,
 464                (long long)HFS_I(inode)->phys_size, inode->i_size);
 465         if (inode->i_size > HFS_I(inode)->phys_size) {
 466                 struct address_space *mapping = inode->i_mapping;
 467                 struct page *page;
 468                 int res;
 469
 470                 size = inode->i_size - 1;
 471                 page = grab_cache_page(mapping, size >> PAGE_CACHE_SHIFT);
 472                 if (!page)
 473                         return;
 474                 size &= PAGE_CACHE_SIZE - 1;
 475                 size++;
 476                 res = mapping->a_ops->prepare_write(NULL, page, size, size);
 477                 if (!res)
 478                         res = mapping->a_ops->commit_write(NULL, page, size, size);
 479                 if (res)
 480                         inode->i_size = HFS_I(inode)->phys_size;
 481                 unlock_page(page);
 482                 page_cache_release(page);
 483                 mark_inode_dirty(inode);
 484                 return;
 485         }
 486         size = inode->i_size + HFS_SB(sb)->alloc_blksz - 1;
 487         blk_cnt = size / HFS_SB(sb)->alloc_blksz;
 488         alloc_cnt = HFS_I(inode)->alloc_blocks;
 489         if (blk_cnt == alloc_cnt)
 490                 goto out;
 491
 492         down(&HFS_I(inode)->extents_lock);
 493         hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
 494         while (1) {
 495                 if (alloc_cnt == HFS_I(inode)->first_blocks) {
 496                         hfs_free_extents(sb, HFS_I(inode)->first_extents,
 497                                          alloc_cnt, alloc_cnt - blk_cnt);
 498                         hfs_dump_extent(HFS_I(inode)->first_extents);
 499                         HFS_I(inode)->first_blocks = blk_cnt;
 500                         break;
 501                 }
 502                 res = __hfs_ext_cache_extent(&fd, inode, alloc_cnt);
 503                 if (res)
 504                         break;
 505                 start = HFS_I(inode)->cached_start;
 506                 hfs_free_extents(sb, HFS_I(inode)->cached_extents,
 507                                  alloc_cnt - start, alloc_cnt - blk_cnt);
 508                 hfs_dump_extent(HFS_I(inode)->cached_extents);
 509                 if (blk_cnt > start) {
 510                         HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY;
 511                         break;
 512                 }
 513                 alloc_cnt = start;
 514                 HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0;
 515                 HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
 516                 hfs_brec_remove(&fd);
 517         }
 518         hfs_find_exit(&fd);
 519         up(&HFS_I(inode)->extents_lock);
 520
 521         HFS_I(inode)->alloc_blocks = blk_cnt;
 522 out:
 523         HFS_I(inode)->phys_size = inode->i_size;
 524         mark_inode_dirty(inode);
 525         inode->i_blocks = (inode->i_size + sb->s_blocksize - 1) >> sb->s_blocksize_bits;
 526 }