linux/fs/hfs/extent.c
<<
>>
Prefs
   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 */
  21static 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 */
  50int hfs_ext_keycmp(const btree_key *key1, const btree_key *key2)
  51{
  52        __be32 fnum1, fnum2;
  53        __be16 block1, block2;
  54
  55        fnum1 = key1->ext.FNum;
  56        fnum2 = key2->ext.FNum;
  57        if (fnum1 != fnum2)
  58                return be32_to_cpu(fnum1) < be32_to_cpu(fnum2) ? -1 : 1;
  59        if (key1->ext.FkType != key2->ext.FkType)
  60                return key1->ext.FkType < key2->ext.FkType ? -1 : 1;
  61
  62        block1 = key1->ext.FABN;
  63        block2 = key2->ext.FABN;
  64        if (block1 == block2)
  65                return 0;
  66        return be16_to_cpu(block1) < be16_to_cpu(block2) ? -1 : 1;
  67}
  68
  69/*
  70 * hfs_ext_find_block
  71 *
  72 * Find a block within an extent record
  73 */
  74static u16 hfs_ext_find_block(struct hfs_extent *ext, u16 off)
  75{
  76        int i;
  77        u16 count;
  78
  79        for (i = 0; i < 3; ext++, i++) {
  80                count = be16_to_cpu(ext->count);
  81                if (off < count)
  82                        return be16_to_cpu(ext->block) + off;
  83                off -= count;
  84        }
  85        /* panic? */
  86        return 0;
  87}
  88
  89static int hfs_ext_block_count(struct hfs_extent *ext)
  90{
  91        int i;
  92        u16 count = 0;
  93
  94        for (i = 0; i < 3; ext++, i++)
  95                count += be16_to_cpu(ext->count);
  96        return count;
  97}
  98
  99static u16 hfs_ext_lastblock(struct hfs_extent *ext)
 100{
 101        int i;
 102
 103        ext += 2;
 104        for (i = 0; i < 2; ext--, i++)
 105                if (ext->count)
 106                        break;
 107        return be16_to_cpu(ext->block) + be16_to_cpu(ext->count);
 108}
 109
 110static void __hfs_ext_write_extent(struct inode *inode, struct hfs_find_data *fd)
 111{
 112        int res;
 113
 114        hfs_ext_build_key(fd->search_key, inode->i_ino, HFS_I(inode)->cached_start,
 115                          HFS_IS_RSRC(inode) ?  HFS_FK_RSRC : HFS_FK_DATA);
 116        res = hfs_brec_find(fd);
 117        if (HFS_I(inode)->flags & HFS_FLG_EXT_NEW) {
 118                if (res != -ENOENT)
 119                        return;
 120                hfs_brec_insert(fd, HFS_I(inode)->cached_extents, sizeof(hfs_extent_rec));
 121                HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
 122        } else {
 123                if (res)
 124                        return;
 125                hfs_bnode_write(fd->bnode, HFS_I(inode)->cached_extents, fd->entryoffset, fd->entrylength);
 126                HFS_I(inode)->flags &= ~HFS_FLG_EXT_DIRTY;
 127        }
 128}
 129
 130void hfs_ext_write_extent(struct inode *inode)
 131{
 132        struct hfs_find_data fd;
 133
 134        if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY) {
 135                hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
 136                __hfs_ext_write_extent(inode, &fd);
 137                hfs_find_exit(&fd);
 138        }
 139}
 140
 141static inline int __hfs_ext_read_extent(struct hfs_find_data *fd, struct hfs_extent *extent,
 142                                        u32 cnid, u32 block, u8 type)
 143{
 144        int res;
 145
 146        hfs_ext_build_key(fd->search_key, cnid, block, type);
 147        fd->key->ext.FNum = 0;
 148        res = hfs_brec_find(fd);
 149        if (res && res != -ENOENT)
 150                return res;
 151        if (fd->key->ext.FNum != fd->search_key->ext.FNum ||
 152            fd->key->ext.FkType != fd->search_key->ext.FkType)
 153                return -ENOENT;
 154        if (fd->entrylength != sizeof(hfs_extent_rec))
 155                return -EIO;
 156        hfs_bnode_read(fd->bnode, extent, fd->entryoffset, sizeof(hfs_extent_rec));
 157        return 0;
 158}
 159
 160static inline int __hfs_ext_cache_extent(struct hfs_find_data *fd, struct inode *inode, u32 block)
 161{
 162        int res;
 163
 164        if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY)
 165                __hfs_ext_write_extent(inode, fd);
 166
 167        res = __hfs_ext_read_extent(fd, HFS_I(inode)->cached_extents, inode->i_ino,
 168                                    block, HFS_IS_RSRC(inode) ? HFS_FK_RSRC : HFS_FK_DATA);
 169        if (!res) {
 170                HFS_I(inode)->cached_start = be16_to_cpu(fd->key->ext.FABN);
 171                HFS_I(inode)->cached_blocks = hfs_ext_block_count(HFS_I(inode)->cached_extents);
 172        } else {
 173                HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0;
 174                HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
 175        }
 176        return res;
 177}
 178
 179static int hfs_ext_read_extent(struct inode *inode, u16 block)
 180{
 181        struct hfs_find_data fd;
 182        int res;
 183
 184        if (block >= HFS_I(inode)->cached_start &&
 185            block < HFS_I(inode)->cached_start + HFS_I(inode)->cached_blocks)
 186                return 0;
 187
 188        hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
 189        res = __hfs_ext_cache_extent(&fd, inode, block);
 190        hfs_find_exit(&fd);
 191        return res;
 192}
 193
 194static void hfs_dump_extent(struct hfs_extent *extent)
 195{
 196        int i;
 197
 198        dprint(DBG_EXTENT, "   ");
 199        for (i = 0; i < 3; i++)
 200                dprint(DBG_EXTENT, " %u:%u", be16_to_cpu(extent[i].block),
 201                                 be16_to_cpu(extent[i].count));
 202        dprint(DBG_EXTENT, "\n");
 203}
 204
 205static int hfs_add_extent(struct hfs_extent *extent, u16 offset,
 206                          u16 alloc_block, u16 block_count)
 207{
 208        u16 count, start;
 209        int i;
 210
 211        hfs_dump_extent(extent);
 212        for (i = 0; i < 3; extent++, i++) {
 213                count = be16_to_cpu(extent->count);
 214                if (offset == count) {
 215                        start = be16_to_cpu(extent->block);
 216                        if (alloc_block != start + count) {
 217                                if (++i >= 3)
 218                                        return -ENOSPC;
 219                                extent++;
 220                                extent->block = cpu_to_be16(alloc_block);
 221                        } else
 222                                block_count += count;
 223                        extent->count = cpu_to_be16(block_count);
 224                        return 0;
 225                } else if (offset < count)
 226                        break;
 227                offset -= count;
 228        }
 229        /* panic? */
 230        return -EIO;
 231}
 232
 233static int hfs_free_extents(struct super_block *sb, struct hfs_extent *extent,
 234                            u16 offset, u16 block_nr)
 235{
 236        u16 count, start;
 237        int i;
 238
 239        hfs_dump_extent(extent);
 240        for (i = 0; i < 3; extent++, i++) {
 241                count = be16_to_cpu(extent->count);
 242                if (offset == count)
 243                        goto found;
 244                else if (offset < count)
 245                        break;
 246                offset -= count;
 247        }
 248        /* panic? */
 249        return -EIO;
 250found:
 251        for (;;) {
 252                start = be16_to_cpu(extent->block);
 253                if (count <= block_nr) {
 254                        hfs_clear_vbm_bits(sb, start, count);
 255                        extent->block = 0;
 256                        extent->count = 0;
 257                        block_nr -= count;
 258                } else {
 259                        count -= block_nr;
 260                        hfs_clear_vbm_bits(sb, start + count, block_nr);
 261                        extent->count = cpu_to_be16(count);
 262                        block_nr = 0;
 263                }
 264                if (!block_nr || !i)
 265                        return 0;
 266                i--;
 267                extent--;
 268                count = be16_to_cpu(extent->count);
 269        }
 270}
 271
 272int hfs_free_fork(struct super_block *sb, struct hfs_cat_file *file, int type)
 273{
 274        struct hfs_find_data fd;
 275        u32 total_blocks, blocks, start;
 276        u32 cnid = be32_to_cpu(file->FlNum);
 277        struct hfs_extent *extent;
 278        int res, i;
 279
 280        if (type == HFS_FK_DATA) {
 281                total_blocks = be32_to_cpu(file->PyLen);
 282                extent = file->ExtRec;
 283        } else {
 284                total_blocks = be32_to_cpu(file->RPyLen);
 285                extent = file->RExtRec;
 286        }
 287        total_blocks /= HFS_SB(sb)->alloc_blksz;
 288        if (!total_blocks)
 289                return 0;
 290
 291        blocks = 0;
 292        for (i = 0; i < 3; extent++, i++)
 293                blocks += be16_to_cpu(extent[i].count);
 294
 295        res = hfs_free_extents(sb, extent, blocks, blocks);
 296        if (res)
 297                return res;
 298        if (total_blocks == blocks)
 299                return 0;
 300
 301        hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
 302        do {
 303                res = __hfs_ext_read_extent(&fd, extent, cnid, total_blocks, type);
 304                if (res)
 305                        break;
 306                start = be16_to_cpu(fd.key->ext.FABN);
 307                hfs_free_extents(sb, extent, total_blocks - start, total_blocks);
 308                hfs_brec_remove(&fd);
 309                total_blocks = start;
 310        } while (total_blocks > blocks);
 311        hfs_find_exit(&fd);
 312
 313        return res;
 314}
 315
 316/*
 317 * hfs_get_block
 318 */
 319int hfs_get_block(struct inode *inode, sector_t block,
 320                  struct buffer_head *bh_result, int create)
 321{
 322        struct super_block *sb;
 323        u16 dblock, ablock;
 324        int res;
 325
 326        sb = inode->i_sb;
 327        /* Convert inode block to disk allocation block */
 328        ablock = (u32)block / HFS_SB(sb)->fs_div;
 329
 330        if (block >= HFS_I(inode)->fs_blocks) {
 331                if (block > HFS_I(inode)->fs_blocks || !create)
 332                        return -EIO;
 333                if (ablock >= HFS_I(inode)->alloc_blocks) {
 334                        res = hfs_extend_file(inode);
 335                        if (res)
 336                                return res;
 337                }
 338        } else
 339                create = 0;
 340
 341        if (ablock < HFS_I(inode)->first_blocks) {
 342                dblock = hfs_ext_find_block(HFS_I(inode)->first_extents, ablock);
 343                goto done;
 344        }
 345
 346        mutex_lock(&HFS_I(inode)->extents_lock);
 347        res = hfs_ext_read_extent(inode, ablock);
 348        if (!res)
 349                dblock = hfs_ext_find_block(HFS_I(inode)->cached_extents,
 350                                            ablock - HFS_I(inode)->cached_start);
 351        else {
 352                mutex_unlock(&HFS_I(inode)->extents_lock);
 353                return -EIO;
 354        }
 355        mutex_unlock(&HFS_I(inode)->extents_lock);
 356
 357done:
 358        map_bh(bh_result, sb, HFS_SB(sb)->fs_start +
 359               dblock * HFS_SB(sb)->fs_div +
 360               (u32)block % HFS_SB(sb)->fs_div);
 361
 362        if (create) {
 363                set_buffer_new(bh_result);
 364                HFS_I(inode)->phys_size += sb->s_blocksize;
 365                HFS_I(inode)->fs_blocks++;
 366                inode_add_bytes(inode, sb->s_blocksize);
 367                mark_inode_dirty(inode);
 368        }
 369        return 0;
 370}
 371
 372int 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        mutex_lock(&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        }
 427out:
 428        mutex_unlock(&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                hfs_mark_mdb_dirty(sb);
 436        }
 437        return res;
 438
 439insert_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
 455void 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                void *fsdata;
 468                struct page *page;
 469                int res;
 470
 471                /* XXX: Can use generic_cont_expand? */
 472                size = inode->i_size - 1;
 473                res = pagecache_write_begin(NULL, mapping, size+1, 0,
 474                                AOP_FLAG_UNINTERRUPTIBLE, &page, &fsdata);
 475                if (!res) {
 476                        res = pagecache_write_end(NULL, mapping, size+1, 0, 0,
 477                                        page, fsdata);
 478                }
 479                if (res)
 480                        inode->i_size = HFS_I(inode)->phys_size;
 481                return;
 482        } else if (inode->i_size == HFS_I(inode)->phys_size)
 483                return;
 484        size = inode->i_size + HFS_SB(sb)->alloc_blksz - 1;
 485        blk_cnt = size / HFS_SB(sb)->alloc_blksz;
 486        alloc_cnt = HFS_I(inode)->alloc_blocks;
 487        if (blk_cnt == alloc_cnt)
 488                goto out;
 489
 490        mutex_lock(&HFS_I(inode)->extents_lock);
 491        hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
 492        while (1) {
 493                if (alloc_cnt == HFS_I(inode)->first_blocks) {
 494                        hfs_free_extents(sb, HFS_I(inode)->first_extents,
 495                                         alloc_cnt, alloc_cnt - blk_cnt);
 496                        hfs_dump_extent(HFS_I(inode)->first_extents);
 497                        HFS_I(inode)->first_blocks = blk_cnt;
 498                        break;
 499                }
 500                res = __hfs_ext_cache_extent(&fd, inode, alloc_cnt);
 501                if (res)
 502                        break;
 503                start = HFS_I(inode)->cached_start;
 504                hfs_free_extents(sb, HFS_I(inode)->cached_extents,
 505                                 alloc_cnt - start, alloc_cnt - blk_cnt);
 506                hfs_dump_extent(HFS_I(inode)->cached_extents);
 507                if (blk_cnt > start) {
 508                        HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY;
 509                        break;
 510                }
 511                alloc_cnt = start;
 512                HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0;
 513                HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
 514                hfs_brec_remove(&fd);
 515        }
 516        hfs_find_exit(&fd);
 517        mutex_unlock(&HFS_I(inode)->extents_lock);
 518
 519        HFS_I(inode)->alloc_blocks = blk_cnt;
 520out:
 521        HFS_I(inode)->phys_size = inode->i_size;
 522        HFS_I(inode)->fs_blocks = (inode->i_size + sb->s_blocksize - 1) >> sb->s_blocksize_bits;
 523        inode_set_bytes(inode, HFS_I(inode)->fs_blocks << sb->s_blocksize_bits);
 524        mark_inode_dirty(inode);
 525}
 526
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.