Back to home page

OSCL-LXR
 
 

     

0001 /*
0002  *  linux/fs/hfs/extent.c
0003  *
0004  * Copyright (C) 1995-1997  Paul H. Hargrove
0005  * (C) 2003 Ardis Technologies <roman@ardistech.com>
0006  * This file may be distributed under the terms of the GNU General Public License.
0007  *
0008  * This file contains the functions related to the extents B-tree.
0009  */
0010 
0011 #include <linux/pagemap.h>
0012 
0013 #include "hfs_fs.h"
0014 #include "btree.h"
0015 
0016 /*================ File-local functions ================*/
0017 
0018 /*
0019  * build_key
0020  */
0021 static void hfs_ext_build_key(hfs_btree_key *key, u32 cnid, u16 block, u8 type)
0022 {
0023     key->key_len = 7;
0024     key->ext.FkType = type;
0025     key->ext.FNum = cpu_to_be32(cnid);
0026     key->ext.FABN = cpu_to_be16(block);
0027 }
0028 
0029 /*
0030  * hfs_ext_compare()
0031  *
0032  * Description:
0033  *   This is the comparison function used for the extents B-tree.  In
0034  *   comparing extent B-tree entries, the file id is the most
0035  *   significant field (compared as unsigned ints); the fork type is
0036  *   the second most significant field (compared as unsigned chars);
0037  *   and the allocation block number field is the least significant
0038  *   (compared as unsigned ints).
0039  * Input Variable(s):
0040  *   struct hfs_ext_key *key1: pointer to the first key to compare
0041  *   struct hfs_ext_key *key2: pointer to the second key to compare
0042  * Output Variable(s):
0043  *   NONE
0044  * Returns:
0045  *   int: negative if key1<key2, positive if key1>key2, and 0 if key1==key2
0046  * Preconditions:
0047  *   key1 and key2 point to "valid" (struct hfs_ext_key)s.
0048  * Postconditions:
0049  *   This function has no side-effects */
0050 int hfs_ext_keycmp(const btree_key *key1, const btree_key *key2)
0051 {
0052     __be32 fnum1, fnum2;
0053     __be16 block1, block2;
0054 
0055     fnum1 = key1->ext.FNum;
0056     fnum2 = key2->ext.FNum;
0057     if (fnum1 != fnum2)
0058         return be32_to_cpu(fnum1) < be32_to_cpu(fnum2) ? -1 : 1;
0059     if (key1->ext.FkType != key2->ext.FkType)
0060         return key1->ext.FkType < key2->ext.FkType ? -1 : 1;
0061 
0062     block1 = key1->ext.FABN;
0063     block2 = key2->ext.FABN;
0064     if (block1 == block2)
0065         return 0;
0066     return be16_to_cpu(block1) < be16_to_cpu(block2) ? -1 : 1;
0067 }
0068 
0069 /*
0070  * hfs_ext_find_block
0071  *
0072  * Find a block within an extent record
0073  */
0074 static u16 hfs_ext_find_block(struct hfs_extent *ext, u16 off)
0075 {
0076     int i;
0077     u16 count;
0078 
0079     for (i = 0; i < 3; ext++, i++) {
0080         count = be16_to_cpu(ext->count);
0081         if (off < count)
0082             return be16_to_cpu(ext->block) + off;
0083         off -= count;
0084     }
0085     /* panic? */
0086     return 0;
0087 }
0088 
0089 static int hfs_ext_block_count(struct hfs_extent *ext)
0090 {
0091     int i;
0092     u16 count = 0;
0093 
0094     for (i = 0; i < 3; ext++, i++)
0095         count += be16_to_cpu(ext->count);
0096     return count;
0097 }
0098 
0099 static u16 hfs_ext_lastblock(struct hfs_extent *ext)
0100 {
0101     int i;
0102 
0103     ext += 2;
0104     for (i = 0; i < 2; ext--, i++)
0105         if (ext->count)
0106             break;
0107     return be16_to_cpu(ext->block) + be16_to_cpu(ext->count);
0108 }
0109 
0110 static int __hfs_ext_write_extent(struct inode *inode, struct hfs_find_data *fd)
0111 {
0112     int res;
0113 
0114     hfs_ext_build_key(fd->search_key, inode->i_ino, HFS_I(inode)->cached_start,
0115               HFS_IS_RSRC(inode) ?  HFS_FK_RSRC : HFS_FK_DATA);
0116     res = hfs_brec_find(fd);
0117     if (HFS_I(inode)->flags & HFS_FLG_EXT_NEW) {
0118         if (res != -ENOENT)
0119             return res;
0120         /* Fail early and avoid ENOSPC during the btree operation */
0121         res = hfs_bmap_reserve(fd->tree, fd->tree->depth + 1);
0122         if (res)
0123             return res;
0124         hfs_brec_insert(fd, HFS_I(inode)->cached_extents, sizeof(hfs_extent_rec));
0125         HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
0126     } else {
0127         if (res)
0128             return res;
0129         hfs_bnode_write(fd->bnode, HFS_I(inode)->cached_extents, fd->entryoffset, fd->entrylength);
0130         HFS_I(inode)->flags &= ~HFS_FLG_EXT_DIRTY;
0131     }
0132     return 0;
0133 }
0134 
0135 int hfs_ext_write_extent(struct inode *inode)
0136 {
0137     struct hfs_find_data fd;
0138     int res = 0;
0139 
0140     if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY) {
0141         res = hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
0142         if (res)
0143             return res;
0144         res = __hfs_ext_write_extent(inode, &fd);
0145         hfs_find_exit(&fd);
0146     }
0147     return res;
0148 }
0149 
0150 static inline int __hfs_ext_read_extent(struct hfs_find_data *fd, struct hfs_extent *extent,
0151                     u32 cnid, u32 block, u8 type)
0152 {
0153     int res;
0154 
0155     hfs_ext_build_key(fd->search_key, cnid, block, type);
0156     fd->key->ext.FNum = 0;
0157     res = hfs_brec_find(fd);
0158     if (res && res != -ENOENT)
0159         return res;
0160     if (fd->key->ext.FNum != fd->search_key->ext.FNum ||
0161         fd->key->ext.FkType != fd->search_key->ext.FkType)
0162         return -ENOENT;
0163     if (fd->entrylength != sizeof(hfs_extent_rec))
0164         return -EIO;
0165     hfs_bnode_read(fd->bnode, extent, fd->entryoffset, sizeof(hfs_extent_rec));
0166     return 0;
0167 }
0168 
0169 static inline int __hfs_ext_cache_extent(struct hfs_find_data *fd, struct inode *inode, u32 block)
0170 {
0171     int res;
0172 
0173     if (HFS_I(inode)->flags & HFS_FLG_EXT_DIRTY) {
0174         res = __hfs_ext_write_extent(inode, fd);
0175         if (res)
0176             return res;
0177     }
0178 
0179     res = __hfs_ext_read_extent(fd, HFS_I(inode)->cached_extents, inode->i_ino,
0180                     block, HFS_IS_RSRC(inode) ? HFS_FK_RSRC : HFS_FK_DATA);
0181     if (!res) {
0182         HFS_I(inode)->cached_start = be16_to_cpu(fd->key->ext.FABN);
0183         HFS_I(inode)->cached_blocks = hfs_ext_block_count(HFS_I(inode)->cached_extents);
0184     } else {
0185         HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0;
0186         HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
0187     }
0188     return res;
0189 }
0190 
0191 static int hfs_ext_read_extent(struct inode *inode, u16 block)
0192 {
0193     struct hfs_find_data fd;
0194     int res;
0195 
0196     if (block >= HFS_I(inode)->cached_start &&
0197         block < HFS_I(inode)->cached_start + HFS_I(inode)->cached_blocks)
0198         return 0;
0199 
0200     res = hfs_find_init(HFS_SB(inode->i_sb)->ext_tree, &fd);
0201     if (!res) {
0202         res = __hfs_ext_cache_extent(&fd, inode, block);
0203         hfs_find_exit(&fd);
0204     }
0205     return res;
0206 }
0207 
0208 static void hfs_dump_extent(struct hfs_extent *extent)
0209 {
0210     int i;
0211 
0212     hfs_dbg(EXTENT, "   ");
0213     for (i = 0; i < 3; i++)
0214         hfs_dbg_cont(EXTENT, " %u:%u",
0215                  be16_to_cpu(extent[i].block),
0216                  be16_to_cpu(extent[i].count));
0217     hfs_dbg_cont(EXTENT, "\n");
0218 }
0219 
0220 static int hfs_add_extent(struct hfs_extent *extent, u16 offset,
0221               u16 alloc_block, u16 block_count)
0222 {
0223     u16 count, start;
0224     int i;
0225 
0226     hfs_dump_extent(extent);
0227     for (i = 0; i < 3; extent++, i++) {
0228         count = be16_to_cpu(extent->count);
0229         if (offset == count) {
0230             start = be16_to_cpu(extent->block);
0231             if (alloc_block != start + count) {
0232                 if (++i >= 3)
0233                     return -ENOSPC;
0234                 extent++;
0235                 extent->block = cpu_to_be16(alloc_block);
0236             } else
0237                 block_count += count;
0238             extent->count = cpu_to_be16(block_count);
0239             return 0;
0240         } else if (offset < count)
0241             break;
0242         offset -= count;
0243     }
0244     /* panic? */
0245     return -EIO;
0246 }
0247 
0248 static int hfs_free_extents(struct super_block *sb, struct hfs_extent *extent,
0249                 u16 offset, u16 block_nr)
0250 {
0251     u16 count, start;
0252     int i;
0253 
0254     hfs_dump_extent(extent);
0255     for (i = 0; i < 3; extent++, i++) {
0256         count = be16_to_cpu(extent->count);
0257         if (offset == count)
0258             goto found;
0259         else if (offset < count)
0260             break;
0261         offset -= count;
0262     }
0263     /* panic? */
0264     return -EIO;
0265 found:
0266     for (;;) {
0267         start = be16_to_cpu(extent->block);
0268         if (count <= block_nr) {
0269             hfs_clear_vbm_bits(sb, start, count);
0270             extent->block = 0;
0271             extent->count = 0;
0272             block_nr -= count;
0273         } else {
0274             count -= block_nr;
0275             hfs_clear_vbm_bits(sb, start + count, block_nr);
0276             extent->count = cpu_to_be16(count);
0277             block_nr = 0;
0278         }
0279         if (!block_nr || !i)
0280             return 0;
0281         i--;
0282         extent--;
0283         count = be16_to_cpu(extent->count);
0284     }
0285 }
0286 
0287 int hfs_free_fork(struct super_block *sb, struct hfs_cat_file *file, int type)
0288 {
0289     struct hfs_find_data fd;
0290     u32 total_blocks, blocks, start;
0291     u32 cnid = be32_to_cpu(file->FlNum);
0292     struct hfs_extent *extent;
0293     int res, i;
0294 
0295     if (type == HFS_FK_DATA) {
0296         total_blocks = be32_to_cpu(file->PyLen);
0297         extent = file->ExtRec;
0298     } else {
0299         total_blocks = be32_to_cpu(file->RPyLen);
0300         extent = file->RExtRec;
0301     }
0302     total_blocks /= HFS_SB(sb)->alloc_blksz;
0303     if (!total_blocks)
0304         return 0;
0305 
0306     blocks = 0;
0307     for (i = 0; i < 3; i++)
0308         blocks += be16_to_cpu(extent[i].count);
0309 
0310     res = hfs_free_extents(sb, extent, blocks, blocks);
0311     if (res)
0312         return res;
0313     if (total_blocks == blocks)
0314         return 0;
0315 
0316     res = hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
0317     if (res)
0318         return res;
0319     do {
0320         res = __hfs_ext_read_extent(&fd, extent, cnid, total_blocks, type);
0321         if (res)
0322             break;
0323         start = be16_to_cpu(fd.key->ext.FABN);
0324         hfs_free_extents(sb, extent, total_blocks - start, total_blocks);
0325         hfs_brec_remove(&fd);
0326         total_blocks = start;
0327     } while (total_blocks > blocks);
0328     hfs_find_exit(&fd);
0329 
0330     return res;
0331 }
0332 
0333 /*
0334  * hfs_get_block
0335  */
0336 int hfs_get_block(struct inode *inode, sector_t block,
0337           struct buffer_head *bh_result, int create)
0338 {
0339     struct super_block *sb;
0340     u16 dblock, ablock;
0341     int res;
0342 
0343     sb = inode->i_sb;
0344     /* Convert inode block to disk allocation block */
0345     ablock = (u32)block / HFS_SB(sb)->fs_div;
0346 
0347     if (block >= HFS_I(inode)->fs_blocks) {
0348         if (!create)
0349             return 0;
0350         if (block > HFS_I(inode)->fs_blocks)
0351             return -EIO;
0352         if (ablock >= HFS_I(inode)->alloc_blocks) {
0353             res = hfs_extend_file(inode);
0354             if (res)
0355                 return res;
0356         }
0357     } else
0358         create = 0;
0359 
0360     if (ablock < HFS_I(inode)->first_blocks) {
0361         dblock = hfs_ext_find_block(HFS_I(inode)->first_extents, ablock);
0362         goto done;
0363     }
0364 
0365     mutex_lock(&HFS_I(inode)->extents_lock);
0366     res = hfs_ext_read_extent(inode, ablock);
0367     if (!res)
0368         dblock = hfs_ext_find_block(HFS_I(inode)->cached_extents,
0369                         ablock - HFS_I(inode)->cached_start);
0370     else {
0371         mutex_unlock(&HFS_I(inode)->extents_lock);
0372         return -EIO;
0373     }
0374     mutex_unlock(&HFS_I(inode)->extents_lock);
0375 
0376 done:
0377     map_bh(bh_result, sb, HFS_SB(sb)->fs_start +
0378            dblock * HFS_SB(sb)->fs_div +
0379            (u32)block % HFS_SB(sb)->fs_div);
0380 
0381     if (create) {
0382         set_buffer_new(bh_result);
0383         HFS_I(inode)->phys_size += sb->s_blocksize;
0384         HFS_I(inode)->fs_blocks++;
0385         inode_add_bytes(inode, sb->s_blocksize);
0386         mark_inode_dirty(inode);
0387     }
0388     return 0;
0389 }
0390 
0391 int hfs_extend_file(struct inode *inode)
0392 {
0393     struct super_block *sb = inode->i_sb;
0394     u32 start, len, goal;
0395     int res;
0396 
0397     mutex_lock(&HFS_I(inode)->extents_lock);
0398     if (HFS_I(inode)->alloc_blocks == HFS_I(inode)->first_blocks)
0399         goal = hfs_ext_lastblock(HFS_I(inode)->first_extents);
0400     else {
0401         res = hfs_ext_read_extent(inode, HFS_I(inode)->alloc_blocks);
0402         if (res)
0403             goto out;
0404         goal = hfs_ext_lastblock(HFS_I(inode)->cached_extents);
0405     }
0406 
0407     len = HFS_I(inode)->clump_blocks;
0408     start = hfs_vbm_search_free(sb, goal, &len);
0409     if (!len) {
0410         res = -ENOSPC;
0411         goto out;
0412     }
0413 
0414     hfs_dbg(EXTENT, "extend %lu: %u,%u\n", inode->i_ino, start, len);
0415     if (HFS_I(inode)->alloc_blocks == HFS_I(inode)->first_blocks) {
0416         if (!HFS_I(inode)->first_blocks) {
0417             hfs_dbg(EXTENT, "first extents\n");
0418             /* no extents yet */
0419             HFS_I(inode)->first_extents[0].block = cpu_to_be16(start);
0420             HFS_I(inode)->first_extents[0].count = cpu_to_be16(len);
0421             res = 0;
0422         } else {
0423             /* try to append to extents in inode */
0424             res = hfs_add_extent(HFS_I(inode)->first_extents,
0425                          HFS_I(inode)->alloc_blocks,
0426                          start, len);
0427             if (res == -ENOSPC)
0428                 goto insert_extent;
0429         }
0430         if (!res) {
0431             hfs_dump_extent(HFS_I(inode)->first_extents);
0432             HFS_I(inode)->first_blocks += len;
0433         }
0434     } else {
0435         res = hfs_add_extent(HFS_I(inode)->cached_extents,
0436                      HFS_I(inode)->alloc_blocks -
0437                      HFS_I(inode)->cached_start,
0438                      start, len);
0439         if (!res) {
0440             hfs_dump_extent(HFS_I(inode)->cached_extents);
0441             HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY;
0442             HFS_I(inode)->cached_blocks += len;
0443         } else if (res == -ENOSPC)
0444             goto insert_extent;
0445     }
0446 out:
0447     mutex_unlock(&HFS_I(inode)->extents_lock);
0448     if (!res) {
0449         HFS_I(inode)->alloc_blocks += len;
0450         mark_inode_dirty(inode);
0451         if (inode->i_ino < HFS_FIRSTUSER_CNID)
0452             set_bit(HFS_FLG_ALT_MDB_DIRTY, &HFS_SB(sb)->flags);
0453         set_bit(HFS_FLG_MDB_DIRTY, &HFS_SB(sb)->flags);
0454         hfs_mark_mdb_dirty(sb);
0455     }
0456     return res;
0457 
0458 insert_extent:
0459     hfs_dbg(EXTENT, "insert new extent\n");
0460     res = hfs_ext_write_extent(inode);
0461     if (res)
0462         goto out;
0463 
0464     memset(HFS_I(inode)->cached_extents, 0, sizeof(hfs_extent_rec));
0465     HFS_I(inode)->cached_extents[0].block = cpu_to_be16(start);
0466     HFS_I(inode)->cached_extents[0].count = cpu_to_be16(len);
0467     hfs_dump_extent(HFS_I(inode)->cached_extents);
0468     HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW;
0469     HFS_I(inode)->cached_start = HFS_I(inode)->alloc_blocks;
0470     HFS_I(inode)->cached_blocks = len;
0471 
0472     res = 0;
0473     goto out;
0474 }
0475 
0476 void hfs_file_truncate(struct inode *inode)
0477 {
0478     struct super_block *sb = inode->i_sb;
0479     struct hfs_find_data fd;
0480     u16 blk_cnt, alloc_cnt, start;
0481     u32 size;
0482     int res;
0483 
0484     hfs_dbg(INODE, "truncate: %lu, %Lu -> %Lu\n",
0485         inode->i_ino, (long long)HFS_I(inode)->phys_size,
0486         inode->i_size);
0487     if (inode->i_size > HFS_I(inode)->phys_size) {
0488         struct address_space *mapping = inode->i_mapping;
0489         void *fsdata;
0490         struct page *page;
0491 
0492         /* XXX: Can use generic_cont_expand? */
0493         size = inode->i_size - 1;
0494         res = hfs_write_begin(NULL, mapping, size + 1, 0, &page,
0495                 &fsdata);
0496         if (!res) {
0497             res = generic_write_end(NULL, mapping, size + 1, 0, 0,
0498                     page, fsdata);
0499         }
0500         if (res)
0501             inode->i_size = HFS_I(inode)->phys_size;
0502         return;
0503     } else if (inode->i_size == HFS_I(inode)->phys_size)
0504         return;
0505     size = inode->i_size + HFS_SB(sb)->alloc_blksz - 1;
0506     blk_cnt = size / HFS_SB(sb)->alloc_blksz;
0507     alloc_cnt = HFS_I(inode)->alloc_blocks;
0508     if (blk_cnt == alloc_cnt)
0509         goto out;
0510 
0511     mutex_lock(&HFS_I(inode)->extents_lock);
0512     res = hfs_find_init(HFS_SB(sb)->ext_tree, &fd);
0513     if (res) {
0514         mutex_unlock(&HFS_I(inode)->extents_lock);
0515         /* XXX: We lack error handling of hfs_file_truncate() */
0516         return;
0517     }
0518     while (1) {
0519         if (alloc_cnt == HFS_I(inode)->first_blocks) {
0520             hfs_free_extents(sb, HFS_I(inode)->first_extents,
0521                      alloc_cnt, alloc_cnt - blk_cnt);
0522             hfs_dump_extent(HFS_I(inode)->first_extents);
0523             HFS_I(inode)->first_blocks = blk_cnt;
0524             break;
0525         }
0526         res = __hfs_ext_cache_extent(&fd, inode, alloc_cnt);
0527         if (res)
0528             break;
0529         start = HFS_I(inode)->cached_start;
0530         hfs_free_extents(sb, HFS_I(inode)->cached_extents,
0531                  alloc_cnt - start, alloc_cnt - blk_cnt);
0532         hfs_dump_extent(HFS_I(inode)->cached_extents);
0533         if (blk_cnt > start) {
0534             HFS_I(inode)->flags |= HFS_FLG_EXT_DIRTY;
0535             break;
0536         }
0537         alloc_cnt = start;
0538         HFS_I(inode)->cached_start = HFS_I(inode)->cached_blocks = 0;
0539         HFS_I(inode)->flags &= ~(HFS_FLG_EXT_DIRTY|HFS_FLG_EXT_NEW);
0540         hfs_brec_remove(&fd);
0541     }
0542     hfs_find_exit(&fd);
0543     mutex_unlock(&HFS_I(inode)->extents_lock);
0544 
0545     HFS_I(inode)->alloc_blocks = blk_cnt;
0546 out:
0547     HFS_I(inode)->phys_size = inode->i_size;
0548     HFS_I(inode)->fs_blocks = (inode->i_size + sb->s_blocksize - 1) >> sb->s_blocksize_bits;
0549     inode_set_bytes(inode, HFS_I(inode)->fs_blocks << sb->s_blocksize_bits);
0550     mark_inode_dirty(inode);
0551 }
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!