fs/hfsplus/extents.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  *  linux/fs/hfsplus/extents.c
0004  *
0005  * Copyright (C) 2001
0006  * Brad Boyer (flar@allandria.com)
0007  * (C) 2003 Ardis Technologies <roman@ardistech.com>
0008  *
0009  * Handling of Extents both in catalog and extents overflow trees
0010  */
0011
0012 #include <linux/errno.h>
0013 #include <linux/fs.h>
0014 #include <linux/pagemap.h>
0015
0016 #include "hfsplus_fs.h"
0017 #include "hfsplus_raw.h"
0018
0019 /* Compare two extents keys, returns 0 on same, pos/neg for difference */
0020 int hfsplus_ext_cmp_key(const hfsplus_btree_key *k1,
0021             const hfsplus_btree_key *k2)
0022 {
0023     __be32 k1id, k2id;
0024     __be32 k1s, k2s;
0025
0026     k1id = k1->ext.cnid;
0027     k2id = k2->ext.cnid;
0028     if (k1id != k2id)
0029         return be32_to_cpu(k1id) < be32_to_cpu(k2id) ? -1 : 1;
0030
0031     if (k1->ext.fork_type != k2->ext.fork_type)
0032         return k1->ext.fork_type < k2->ext.fork_type ? -1 : 1;
0033
0034     k1s = k1->ext.start_block;
0035     k2s = k2->ext.start_block;
0036     if (k1s == k2s)
0037         return 0;
0038     return be32_to_cpu(k1s) < be32_to_cpu(k2s) ? -1 : 1;
0039 }
0040
0041 static void hfsplus_ext_build_key(hfsplus_btree_key *key, u32 cnid,
0042                   u32 block, u8 type)
0043 {
0044     key->key_len = cpu_to_be16(HFSPLUS_EXT_KEYLEN - 2);
0045     key->ext.cnid = cpu_to_be32(cnid);
0046     key->ext.start_block = cpu_to_be32(block);
0047     key->ext.fork_type = type;
0048     key->ext.pad = 0;
0049 }
0050
0051 static u32 hfsplus_ext_find_block(struct hfsplus_extent *ext, u32 off)
0052 {
0053     int i;
0054     u32 count;
0055
0056     for (i = 0; i < 8; ext++, i++) {
0057         count = be32_to_cpu(ext->block_count);
0058         if (off < count)
0059             return be32_to_cpu(ext->start_block) + off;
0060         off -= count;
0061     }
0062     /* panic? */
0063     return 0;
0064 }
0065
0066 static int hfsplus_ext_block_count(struct hfsplus_extent *ext)
0067 {
0068     int i;
0069     u32 count = 0;
0070
0071     for (i = 0; i < 8; ext++, i++)
0072         count += be32_to_cpu(ext->block_count);
0073     return count;
0074 }
0075
0076 static u32 hfsplus_ext_lastblock(struct hfsplus_extent *ext)
0077 {
0078     int i;
0079
0080     ext += 7;
0081     for (i = 0; i < 7; ext--, i++)
0082         if (ext->block_count)
0083             break;
0084     return be32_to_cpu(ext->start_block) + be32_to_cpu(ext->block_count);
0085 }
0086
0087 static int __hfsplus_ext_write_extent(struct inode *inode,
0088         struct hfs_find_data *fd)
0089 {
0090     struct hfsplus_inode_info *hip = HFSPLUS_I(inode);
0091     int res;
0092
0093     WARN_ON(!mutex_is_locked(&hip->extents_lock));
0094
0095     hfsplus_ext_build_key(fd->search_key, inode->i_ino, hip->cached_start,
0096                   HFSPLUS_IS_RSRC(inode) ?
0097                 HFSPLUS_TYPE_RSRC : HFSPLUS_TYPE_DATA);
0098
0099     res = hfs_brec_find(fd, hfs_find_rec_by_key);
0100     if (hip->extent_state & HFSPLUS_EXT_NEW) {
0101         if (res != -ENOENT)
0102             return res;
0103         /* Fail early and avoid ENOSPC during the btree operation */
0104         res = hfs_bmap_reserve(fd->tree, fd->tree->depth + 1);
0105         if (res)
0106             return res;
0107         hfs_brec_insert(fd, hip->cached_extents,
0108                 sizeof(hfsplus_extent_rec));
0109         hip->extent_state &= ~(HFSPLUS_EXT_DIRTY | HFSPLUS_EXT_NEW);
0110     } else {
0111         if (res)
0112             return res;
0113         hfs_bnode_write(fd->bnode, hip->cached_extents,
0114                 fd->entryoffset, fd->entrylength);
0115         hip->extent_state &= ~HFSPLUS_EXT_DIRTY;
0116     }
0117
0118     /*
0119      * We can't just use hfsplus_mark_inode_dirty here, because we
0120      * also get called from hfsplus_write_inode, which should not
0121      * redirty the inode.  Instead the callers have to be careful
0122      * to explicily mark the inode dirty, too.
0123      */
0124     set_bit(HFSPLUS_I_EXT_DIRTY, &hip->flags);
0125
0126     return 0;
0127 }
0128
0129 static int hfsplus_ext_write_extent_locked(struct inode *inode)
0130 {
0131     int res = 0;
0132
0133     if (HFSPLUS_I(inode)->extent_state & HFSPLUS_EXT_DIRTY) {
0134         struct hfs_find_data fd;
0135
0136         res = hfs_find_init(HFSPLUS_SB(inode->i_sb)->ext_tree, &fd);
0137         if (res)
0138             return res;
0139         res = __hfsplus_ext_write_extent(inode, &fd);
0140         hfs_find_exit(&fd);
0141     }
0142     return res;
0143 }
0144
0145 int hfsplus_ext_write_extent(struct inode *inode)
0146 {
0147     int res;
0148
0149     mutex_lock(&HFSPLUS_I(inode)->extents_lock);
0150     res = hfsplus_ext_write_extent_locked(inode);
0151     mutex_unlock(&HFSPLUS_I(inode)->extents_lock);
0152
0153     return res;
0154 }
0155
0156 static inline int __hfsplus_ext_read_extent(struct hfs_find_data *fd,
0157                         struct hfsplus_extent *extent,
0158                         u32 cnid, u32 block, u8 type)
0159 {
0160     int res;
0161
0162     hfsplus_ext_build_key(fd->search_key, cnid, block, type);
0163     fd->key->ext.cnid = 0;
0164     res = hfs_brec_find(fd, hfs_find_rec_by_key);
0165     if (res && res != -ENOENT)
0166         return res;
0167     if (fd->key->ext.cnid != fd->search_key->ext.cnid ||
0168         fd->key->ext.fork_type != fd->search_key->ext.fork_type)
0169         return -ENOENT;
0170     if (fd->entrylength != sizeof(hfsplus_extent_rec))
0171         return -EIO;
0172     hfs_bnode_read(fd->bnode, extent, fd->entryoffset,
0173         sizeof(hfsplus_extent_rec));
0174     return 0;
0175 }
0176
0177 static inline int __hfsplus_ext_cache_extent(struct hfs_find_data *fd,
0178         struct inode *inode, u32 block)
0179 {
0180     struct hfsplus_inode_info *hip = HFSPLUS_I(inode);
0181     int res;
0182
0183     WARN_ON(!mutex_is_locked(&hip->extents_lock));
0184
0185     if (hip->extent_state & HFSPLUS_EXT_DIRTY) {
0186         res = __hfsplus_ext_write_extent(inode, fd);
0187         if (res)
0188             return res;
0189     }
0190
0191     res = __hfsplus_ext_read_extent(fd, hip->cached_extents, inode->i_ino,
0192                     block, HFSPLUS_IS_RSRC(inode) ?
0193                         HFSPLUS_TYPE_RSRC :
0194                         HFSPLUS_TYPE_DATA);
0195     if (!res) {
0196         hip->cached_start = be32_to_cpu(fd->key->ext.start_block);
0197         hip->cached_blocks =
0198             hfsplus_ext_block_count(hip->cached_extents);
0199     } else {
0200         hip->cached_start = hip->cached_blocks = 0;
0201         hip->extent_state &= ~(HFSPLUS_EXT_DIRTY | HFSPLUS_EXT_NEW);
0202     }
0203     return res;
0204 }
0205
0206 static int hfsplus_ext_read_extent(struct inode *inode, u32 block)
0207 {
0208     struct hfsplus_inode_info *hip = HFSPLUS_I(inode);
0209     struct hfs_find_data fd;
0210     int res;
0211
0212     if (block >= hip->cached_start &&
0213         block < hip->cached_start + hip->cached_blocks)
0214         return 0;
0215
0216     res = hfs_find_init(HFSPLUS_SB(inode->i_sb)->ext_tree, &fd);
0217     if (!res) {
0218         res = __hfsplus_ext_cache_extent(&fd, inode, block);
0219         hfs_find_exit(&fd);
0220     }
0221     return res;
0222 }
0223
0224 /* Get a block at iblock for inode, possibly allocating if create */
0225 int hfsplus_get_block(struct inode *inode, sector_t iblock,
0226               struct buffer_head *bh_result, int create)
0227 {
0228     struct super_block *sb = inode->i_sb;
0229     struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb);
0230     struct hfsplus_inode_info *hip = HFSPLUS_I(inode);
0231     int res = -EIO;
0232     u32 ablock, dblock, mask;
0233     sector_t sector;
0234     int was_dirty = 0;
0235
0236     /* Convert inode block to disk allocation block */
0237     ablock = iblock >> sbi->fs_shift;
0238
0239     if (iblock >= hip->fs_blocks) {
0240         if (!create)
0241             return 0;
0242         if (iblock > hip->fs_blocks)
0243             return -EIO;
0244         if (ablock >= hip->alloc_blocks) {
0245             res = hfsplus_file_extend(inode, false);
0246             if (res)
0247                 return res;
0248         }
0249     } else
0250         create = 0;
0251
0252     if (ablock < hip->first_blocks) {
0253         dblock = hfsplus_ext_find_block(hip->first_extents, ablock);
0254         goto done;
0255     }
0256
0257     if (inode->i_ino == HFSPLUS_EXT_CNID)
0258         return -EIO;
0259
0260     mutex_lock(&hip->extents_lock);
0261
0262     /*
0263      * hfsplus_ext_read_extent will write out a cached extent into
0264      * the extents btree.  In that case we may have to mark the inode
0265      * dirty even for a pure read of an extent here.
0266      */
0267     was_dirty = (hip->extent_state & HFSPLUS_EXT_DIRTY);
0268     res = hfsplus_ext_read_extent(inode, ablock);
0269     if (res) {
0270         mutex_unlock(&hip->extents_lock);
0271         return -EIO;
0272     }
0273     dblock = hfsplus_ext_find_block(hip->cached_extents,
0274                     ablock - hip->cached_start);
0275     mutex_unlock(&hip->extents_lock);
0276
0277 done:
0278     hfs_dbg(EXTENT, "get_block(%lu): %llu - %u\n",
0279         inode->i_ino, (long long)iblock, dblock);
0280
0281     mask = (1 << sbi->fs_shift) - 1;
0282     sector = ((sector_t)dblock << sbi->fs_shift) +
0283           sbi->blockoffset + (iblock & mask);
0284     map_bh(bh_result, sb, sector);
0285
0286     if (create) {
0287         set_buffer_new(bh_result);
0288         hip->phys_size += sb->s_blocksize;
0289         hip->fs_blocks++;
0290         inode_add_bytes(inode, sb->s_blocksize);
0291     }
0292     if (create || was_dirty)
0293         mark_inode_dirty(inode);
0294     return 0;
0295 }
0296
0297 static void hfsplus_dump_extent(struct hfsplus_extent *extent)
0298 {
0299     int i;
0300
0301     hfs_dbg(EXTENT, "   ");
0302     for (i = 0; i < 8; i++)
0303         hfs_dbg_cont(EXTENT, " %u:%u",
0304                  be32_to_cpu(extent[i].start_block),
0305                  be32_to_cpu(extent[i].block_count));
0306     hfs_dbg_cont(EXTENT, "\n");
0307 }
0308
0309 static int hfsplus_add_extent(struct hfsplus_extent *extent, u32 offset,
0310                   u32 alloc_block, u32 block_count)
0311 {
0312     u32 count, start;
0313     int i;
0314
0315     hfsplus_dump_extent(extent);
0316     for (i = 0; i < 8; extent++, i++) {
0317         count = be32_to_cpu(extent->block_count);
0318         if (offset == count) {
0319             start = be32_to_cpu(extent->start_block);
0320             if (alloc_block != start + count) {
0321                 if (++i >= 8)
0322                     return -ENOSPC;
0323                 extent++;
0324                 extent->start_block = cpu_to_be32(alloc_block);
0325             } else
0326                 block_count += count;
0327             extent->block_count = cpu_to_be32(block_count);
0328             return 0;
0329         } else if (offset < count)
0330             break;
0331         offset -= count;
0332     }
0333     /* panic? */
0334     return -EIO;
0335 }
0336
0337 static int hfsplus_free_extents(struct super_block *sb,
0338                 struct hfsplus_extent *extent,
0339                 u32 offset, u32 block_nr)
0340 {
0341     u32 count, start;
0342     int i;
0343     int err = 0;
0344
0345     /* Mapping the allocation file may lock the extent tree */
0346     WARN_ON(mutex_is_locked(&HFSPLUS_SB(sb)->ext_tree->tree_lock));
0347
0348     hfsplus_dump_extent(extent);
0349     for (i = 0; i < 8; extent++, i++) {
0350         count = be32_to_cpu(extent->block_count);
0351         if (offset == count)
0352             goto found;
0353         else if (offset < count)
0354             break;
0355         offset -= count;
0356     }
0357     /* panic? */
0358     return -EIO;
0359 found:
0360     for (;;) {
0361         start = be32_to_cpu(extent->start_block);
0362         if (count <= block_nr) {
0363             err = hfsplus_block_free(sb, start, count);
0364             if (err) {
0365                 pr_err("can't free extent\n");
0366                 hfs_dbg(EXTENT, " start: %u count: %u\n",
0367                     start, count);
0368             }
0369             extent->block_count = 0;
0370             extent->start_block = 0;
0371             block_nr -= count;
0372         } else {
0373             count -= block_nr;
0374             err = hfsplus_block_free(sb, start + count, block_nr);
0375             if (err) {
0376                 pr_err("can't free extent\n");
0377                 hfs_dbg(EXTENT, " start: %u count: %u\n",
0378                     start, count);
0379             }
0380             extent->block_count = cpu_to_be32(count);
0381             block_nr = 0;
0382         }
0383         if (!block_nr || !i) {
0384             /*
0385              * Try to free all extents and
0386              * return only last error
0387              */
0388             return err;
0389         }
0390         i--;
0391         extent--;
0392         count = be32_to_cpu(extent->block_count);
0393     }
0394 }
0395
0396 int hfsplus_free_fork(struct super_block *sb, u32 cnid,
0397         struct hfsplus_fork_raw *fork, int type)
0398 {
0399     struct hfs_find_data fd;
0400     hfsplus_extent_rec ext_entry;
0401     u32 total_blocks, blocks, start;
0402     int res, i;
0403
0404     total_blocks = be32_to_cpu(fork->total_blocks);
0405     if (!total_blocks)
0406         return 0;
0407
0408     blocks = 0;
0409     for (i = 0; i < 8; i++)
0410         blocks += be32_to_cpu(fork->extents[i].block_count);
0411
0412     res = hfsplus_free_extents(sb, fork->extents, blocks, blocks);
0413     if (res)
0414         return res;
0415     if (total_blocks == blocks)
0416         return 0;
0417
0418     res = hfs_find_init(HFSPLUS_SB(sb)->ext_tree, &fd);
0419     if (res)
0420         return res;
0421     do {
0422         res = __hfsplus_ext_read_extent(&fd, ext_entry, cnid,
0423                         total_blocks, type);
0424         if (res)
0425             break;
0426         start = be32_to_cpu(fd.key->ext.start_block);
0427         hfs_brec_remove(&fd);
0428
0429         mutex_unlock(&fd.tree->tree_lock);
0430         hfsplus_free_extents(sb, ext_entry, total_blocks - start,
0431                      total_blocks);
0432         total_blocks = start;
0433         mutex_lock(&fd.tree->tree_lock);
0434     } while (total_blocks > blocks);
0435     hfs_find_exit(&fd);
0436
0437     return res;
0438 }
0439
0440 int hfsplus_file_extend(struct inode *inode, bool zeroout)
0441 {
0442     struct super_block *sb = inode->i_sb;
0443     struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb);
0444     struct hfsplus_inode_info *hip = HFSPLUS_I(inode);
0445     u32 start, len, goal;
0446     int res;
0447
0448     if (sbi->alloc_file->i_size * 8 <
0449         sbi->total_blocks - sbi->free_blocks + 8) {
0450         /* extend alloc file */
0451         pr_err("extend alloc file! (%llu,%u,%u)\n",
0452                sbi->alloc_file->i_size * 8,
0453                sbi->total_blocks, sbi->free_blocks);
0454         return -ENOSPC;
0455     }
0456
0457     mutex_lock(&hip->extents_lock);
0458     if (hip->alloc_blocks == hip->first_blocks)
0459         goal = hfsplus_ext_lastblock(hip->first_extents);
0460     else {
0461         res = hfsplus_ext_read_extent(inode, hip->alloc_blocks);
0462         if (res)
0463             goto out;
0464         goal = hfsplus_ext_lastblock(hip->cached_extents);
0465     }
0466
0467     len = hip->clump_blocks;
0468     start = hfsplus_block_allocate(sb, sbi->total_blocks, goal, &len);
0469     if (start >= sbi->total_blocks) {
0470         start = hfsplus_block_allocate(sb, goal, 0, &len);
0471         if (start >= goal) {
0472             res = -ENOSPC;
0473             goto out;
0474         }
0475     }
0476
0477     if (zeroout) {
0478         res = sb_issue_zeroout(sb, start, len, GFP_NOFS);
0479         if (res)
0480             goto out;
0481     }
0482
0483     hfs_dbg(EXTENT, "extend %lu: %u,%u\n", inode->i_ino, start, len);
0484
0485     if (hip->alloc_blocks <= hip->first_blocks) {
0486         if (!hip->first_blocks) {
0487             hfs_dbg(EXTENT, "first extents\n");
0488             /* no extents yet */
0489             hip->first_extents[0].start_block = cpu_to_be32(start);
0490             hip->first_extents[0].block_count = cpu_to_be32(len);
0491             res = 0;
0492         } else {
0493             /* try to append to extents in inode */
0494             res = hfsplus_add_extent(hip->first_extents,
0495                          hip->alloc_blocks,
0496                          start, len);
0497             if (res == -ENOSPC)
0498                 goto insert_extent;
0499         }
0500         if (!res) {
0501             hfsplus_dump_extent(hip->first_extents);
0502             hip->first_blocks += len;
0503         }
0504     } else {
0505         res = hfsplus_add_extent(hip->cached_extents,
0506                      hip->alloc_blocks - hip->cached_start,
0507                      start, len);
0508         if (!res) {
0509             hfsplus_dump_extent(hip->cached_extents);
0510             hip->extent_state |= HFSPLUS_EXT_DIRTY;
0511             hip->cached_blocks += len;
0512         } else if (res == -ENOSPC)
0513             goto insert_extent;
0514     }
0515 out:
0516     if (!res) {
0517         hip->alloc_blocks += len;
0518         mutex_unlock(&hip->extents_lock);
0519         hfsplus_mark_inode_dirty(inode, HFSPLUS_I_ALLOC_DIRTY);
0520         return 0;
0521     }
0522     mutex_unlock(&hip->extents_lock);
0523     return res;
0524
0525 insert_extent:
0526     hfs_dbg(EXTENT, "insert new extent\n");
0527     res = hfsplus_ext_write_extent_locked(inode);
0528     if (res)
0529         goto out;
0530
0531     memset(hip->cached_extents, 0, sizeof(hfsplus_extent_rec));
0532     hip->cached_extents[0].start_block = cpu_to_be32(start);
0533     hip->cached_extents[0].block_count = cpu_to_be32(len);
0534     hfsplus_dump_extent(hip->cached_extents);
0535     hip->extent_state |= HFSPLUS_EXT_DIRTY | HFSPLUS_EXT_NEW;
0536     hip->cached_start = hip->alloc_blocks;
0537     hip->cached_blocks = len;
0538
0539     res = 0;
0540     goto out;
0541 }
0542
0543 void hfsplus_file_truncate(struct inode *inode)
0544 {
0545     struct super_block *sb = inode->i_sb;
0546     struct hfsplus_inode_info *hip = HFSPLUS_I(inode);
0547     struct hfs_find_data fd;
0548     u32 alloc_cnt, blk_cnt, start;
0549     int res;
0550
0551     hfs_dbg(INODE, "truncate: %lu, %llu -> %llu\n",
0552         inode->i_ino, (long long)hip->phys_size, inode->i_size);
0553
0554     if (inode->i_size > hip->phys_size) {
0555         struct address_space *mapping = inode->i_mapping;
0556         struct page *page;
0557         void *fsdata;
0558         loff_t size = inode->i_size;
0559
0560         res = hfsplus_write_begin(NULL, mapping, size, 0,
0561                       &page, &fsdata);
0562         if (res)
0563             return;
0564         res = generic_write_end(NULL, mapping, size, 0, 0,
0565                     page, fsdata);
0566         if (res < 0)
0567             return;
0568         mark_inode_dirty(inode);
0569         return;
0570     } else if (inode->i_size == hip->phys_size)
0571         return;
0572
0573     blk_cnt = (inode->i_size + HFSPLUS_SB(sb)->alloc_blksz - 1) >>
0574             HFSPLUS_SB(sb)->alloc_blksz_shift;
0575
0576     mutex_lock(&hip->extents_lock);
0577
0578     alloc_cnt = hip->alloc_blocks;
0579     if (blk_cnt == alloc_cnt)
0580         goto out_unlock;
0581
0582     res = hfs_find_init(HFSPLUS_SB(sb)->ext_tree, &fd);
0583     if (res) {
0584         mutex_unlock(&hip->extents_lock);
0585         /* XXX: We lack error handling of hfsplus_file_truncate() */
0586         return;
0587     }
0588     while (1) {
0589         if (alloc_cnt == hip->first_blocks) {
0590             mutex_unlock(&fd.tree->tree_lock);
0591             hfsplus_free_extents(sb, hip->first_extents,
0592                          alloc_cnt, alloc_cnt - blk_cnt);
0593             hfsplus_dump_extent(hip->first_extents);
0594             hip->first_blocks = blk_cnt;
0595             mutex_lock(&fd.tree->tree_lock);
0596             break;
0597         }
0598         res = __hfsplus_ext_cache_extent(&fd, inode, alloc_cnt);
0599         if (res)
0600             break;
0601
0602         start = hip->cached_start;
0603         if (blk_cnt <= start)
0604             hfs_brec_remove(&fd);
0605         mutex_unlock(&fd.tree->tree_lock);
0606         hfsplus_free_extents(sb, hip->cached_extents,
0607                      alloc_cnt - start, alloc_cnt - blk_cnt);
0608         hfsplus_dump_extent(hip->cached_extents);
0609         mutex_lock(&fd.tree->tree_lock);
0610         if (blk_cnt > start) {
0611             hip->extent_state |= HFSPLUS_EXT_DIRTY;
0612             break;
0613         }
0614         alloc_cnt = start;
0615         hip->cached_start = hip->cached_blocks = 0;
0616         hip->extent_state &= ~(HFSPLUS_EXT_DIRTY | HFSPLUS_EXT_NEW);
0617     }
0618     hfs_find_exit(&fd);
0619
0620     hip->alloc_blocks = blk_cnt;
0621 out_unlock:
0622     mutex_unlock(&hip->extents_lock);
0623     hip->phys_size = inode->i_size;
0624     hip->fs_blocks = (inode->i_size + sb->s_blocksize - 1) >>
0625         sb->s_blocksize_bits;
0626     inode_set_bytes(inode, hip->fs_blocks << sb->s_blocksize_bits);
0627     hfsplus_mark_inode_dirty(inode, HFSPLUS_I_ALLOC_DIRTY);
0628 }