fs/befs/datastream.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * linux/fs/befs/datastream.c
0004  *
0005  * Copyright (C) 2001 Will Dyson <will_dyson@pobox.com>
0006  *
0007  * Based on portions of file.c by Makoto Kato <m_kato@ga2.so-net.ne.jp>
0008  *
0009  * Many thanks to Dominic Giampaolo, author of "Practical File System
0010  * Design with the Be File System", for such a helpful book.
0011  *
0012  */
0013
0014 #include <linux/kernel.h>
0015 #include <linux/buffer_head.h>
0016 #include <linux/string.h>
0017
0018 #include "befs.h"
0019 #include "datastream.h"
0020 #include "io.h"
0021
0022 const befs_inode_addr BAD_IADDR = { 0, 0, 0 };
0023
0024 static int befs_find_brun_direct(struct super_block *sb,
0025                  const befs_data_stream *data,
0026                  befs_blocknr_t blockno, befs_block_run *run);
0027
0028 static int befs_find_brun_indirect(struct super_block *sb,
0029                    const befs_data_stream *data,
0030                    befs_blocknr_t blockno,
0031                    befs_block_run *run);
0032
0033 static int befs_find_brun_dblindirect(struct super_block *sb,
0034                       const befs_data_stream *data,
0035                       befs_blocknr_t blockno,
0036                       befs_block_run *run);
0037
0038 /**
0039  * befs_read_datastream - get buffer_head containing data, starting from pos.
0040  * @sb: Filesystem superblock
0041  * @ds: datastream to find data with
0042  * @pos: start of data
0043  * @off: offset of data in buffer_head->b_data
0044  *
0045  * Returns pointer to buffer_head containing data starting with offset @off,
0046  * if you don't need to know offset just set @off = NULL.
0047  */
0048 struct buffer_head *
0049 befs_read_datastream(struct super_block *sb, const befs_data_stream *ds,
0050              befs_off_t pos, uint *off)
0051 {
0052     struct buffer_head *bh;
0053     befs_block_run run;
0054     befs_blocknr_t block;   /* block coresponding to pos */
0055
0056     befs_debug(sb, "---> %s %llu", __func__, pos);
0057     block = pos >> BEFS_SB(sb)->block_shift;
0058     if (off)
0059         *off = pos - (block << BEFS_SB(sb)->block_shift);
0060
0061     if (befs_fblock2brun(sb, ds, block, &run) != BEFS_OK) {
0062         befs_error(sb, "BeFS: Error finding disk addr of block %lu",
0063                (unsigned long)block);
0064         befs_debug(sb, "<--- %s ERROR", __func__);
0065         return NULL;
0066     }
0067     bh = befs_bread_iaddr(sb, run);
0068     if (!bh) {
0069         befs_error(sb, "BeFS: Error reading block %lu from datastream",
0070                (unsigned long)block);
0071         return NULL;
0072     }
0073
0074     befs_debug(sb, "<--- %s read data, starting at %llu", __func__, pos);
0075
0076     return bh;
0077 }
0078
0079 /**
0080  * befs_fblock2brun - give back block run for fblock
0081  * @sb: the superblock
0082  * @data: datastream to read from
0083  * @fblock: the blocknumber with the file position to find
0084  * @run: The found run is passed back through this pointer
0085  *
0086  * Takes a file position and gives back a brun who's starting block
0087  * is block number fblock of the file.
0088  *
0089  * Returns BEFS_OK or BEFS_ERR.
0090  *
0091  * Calls specialized functions for each of the three possible
0092  * datastream regions.
0093  */
0094 int
0095 befs_fblock2brun(struct super_block *sb, const befs_data_stream *data,
0096          befs_blocknr_t fblock, befs_block_run *run)
0097 {
0098     int err;
0099     befs_off_t pos = fblock << BEFS_SB(sb)->block_shift;
0100
0101     if (pos < data->max_direct_range) {
0102         err = befs_find_brun_direct(sb, data, fblock, run);
0103
0104     } else if (pos < data->max_indirect_range) {
0105         err = befs_find_brun_indirect(sb, data, fblock, run);
0106
0107     } else if (pos < data->max_double_indirect_range) {
0108         err = befs_find_brun_dblindirect(sb, data, fblock, run);
0109
0110     } else {
0111         befs_error(sb,
0112                "befs_fblock2brun() was asked to find block %lu, "
0113                "which is not mapped by the datastream\n",
0114                (unsigned long)fblock);
0115         err = BEFS_ERR;
0116     }
0117     return err;
0118 }
0119
0120 /**
0121  * befs_read_lsmylink - read long symlink from datastream.
0122  * @sb: Filesystem superblock
0123  * @ds: Datastream to read from
0124  * @buff: Buffer in which to place long symlink data
0125  * @len: Length of the long symlink in bytes
0126  *
0127  * Returns the number of bytes read
0128  */
0129 size_t
0130 befs_read_lsymlink(struct super_block *sb, const befs_data_stream *ds,
0131            void *buff, befs_off_t len)
0132 {
0133     befs_off_t bytes_read = 0;  /* bytes readed */
0134     u16 plen;
0135     struct buffer_head *bh;
0136
0137     befs_debug(sb, "---> %s length: %llu", __func__, len);
0138
0139     while (bytes_read < len) {
0140         bh = befs_read_datastream(sb, ds, bytes_read, NULL);
0141         if (!bh) {
0142             befs_error(sb, "BeFS: Error reading datastream block "
0143                    "starting from %llu", bytes_read);
0144             befs_debug(sb, "<--- %s ERROR", __func__);
0145             return bytes_read;
0146
0147         }
0148         plen = ((bytes_read + BEFS_SB(sb)->block_size) < len) ?
0149             BEFS_SB(sb)->block_size : len - bytes_read;
0150         memcpy(buff + bytes_read, bh->b_data, plen);
0151         brelse(bh);
0152         bytes_read += plen;
0153     }
0154
0155     befs_debug(sb, "<--- %s read %u bytes", __func__, (unsigned int)
0156            bytes_read);
0157     return bytes_read;
0158 }
0159
0160 /**
0161  * befs_count_blocks - blocks used by a file
0162  * @sb: Filesystem superblock
0163  * @ds: Datastream of the file
0164  *
0165  * Counts the number of fs blocks that the file represented by
0166  * inode occupies on the filesystem, counting both regular file
0167  * data and filesystem metadata (and eventually attribute data
0168  * when we support attributes)
0169 */
0170
0171 befs_blocknr_t
0172 befs_count_blocks(struct super_block *sb, const befs_data_stream *ds)
0173 {
0174     befs_blocknr_t blocks;
0175     befs_blocknr_t datablocks;  /* File data blocks */
0176     befs_blocknr_t metablocks;  /* FS metadata blocks */
0177     struct befs_sb_info *befs_sb = BEFS_SB(sb);
0178
0179     befs_debug(sb, "---> %s", __func__);
0180
0181     datablocks = ds->size >> befs_sb->block_shift;
0182     if (ds->size & (befs_sb->block_size - 1))
0183         datablocks += 1;
0184
0185     metablocks = 1;     /* Start with 1 block for inode */
0186
0187     /* Size of indirect block */
0188     if (ds->size > ds->max_direct_range)
0189         metablocks += ds->indirect.len;
0190
0191     /*
0192      * Double indir block, plus all the indirect blocks it maps.
0193      * In the double-indirect range, all block runs of data are
0194      * BEFS_DBLINDIR_BRUN_LEN blocks long. Therefore, we know
0195      * how many data block runs are in the double-indirect region,
0196      * and from that we know how many indirect blocks it takes to
0197      * map them. We assume that the indirect blocks are also
0198      * BEFS_DBLINDIR_BRUN_LEN blocks long.
0199      */
0200     if (ds->size > ds->max_indirect_range && ds->max_indirect_range != 0) {
0201         uint dbl_bytes;
0202         uint dbl_bruns;
0203         uint indirblocks;
0204
0205         dbl_bytes =
0206             ds->max_double_indirect_range - ds->max_indirect_range;
0207         dbl_bruns =
0208             dbl_bytes / (befs_sb->block_size * BEFS_DBLINDIR_BRUN_LEN);
0209         indirblocks = dbl_bruns / befs_iaddrs_per_block(sb);
0210
0211         metablocks += ds->double_indirect.len;
0212         metablocks += indirblocks;
0213     }
0214
0215     blocks = datablocks + metablocks;
0216     befs_debug(sb, "<--- %s %u blocks", __func__, (unsigned int)blocks);
0217
0218     return blocks;
0219 }
0220
0221 /**
0222  * befs_find_brun_direct - find a direct block run in the datastream
0223  * @sb: the superblock
0224  * @data: the datastream
0225  * @blockno: the blocknumber to find
0226  * @run: The found run is passed back through this pointer
0227  *
0228  * Finds the block run that starts at file block number blockno
0229  * in the file represented by the datastream data, if that
0230  * blockno is in the direct region of the datastream.
0231  *
0232  * Return value is BEFS_OK if the blockrun is found, BEFS_ERR
0233  * otherwise.
0234  *
0235  * Algorithm:
0236  * Linear search. Checks each element of array[] to see if it
0237  * contains the blockno-th filesystem block. This is necessary
0238  * because the block runs map variable amounts of data. Simply
0239  * keeps a count of the number of blocks searched so far (sum),
0240  * incrementing this by the length of each block run as we come
0241  * across it. Adds sum to *count before returning (this is so
0242  * you can search multiple arrays that are logicaly one array,
0243  * as in the indirect region code).
0244  *
0245  * When/if blockno is found, if blockno is inside of a block
0246  * run as stored on disk, we offset the start and length members
0247  * of the block run, so that blockno is the start and len is
0248  * still valid (the run ends in the same place).
0249  */
0250 static int
0251 befs_find_brun_direct(struct super_block *sb, const befs_data_stream *data,
0252               befs_blocknr_t blockno, befs_block_run *run)
0253 {
0254     int i;
0255     const befs_block_run *array = data->direct;
0256     befs_blocknr_t sum;
0257
0258     befs_debug(sb, "---> %s, find %lu", __func__, (unsigned long)blockno);
0259
0260     for (i = 0, sum = 0; i < BEFS_NUM_DIRECT_BLOCKS;
0261          sum += array[i].len, i++) {
0262         if (blockno >= sum && blockno < sum + (array[i].len)) {
0263             int offset = blockno - sum;
0264
0265             run->allocation_group = array[i].allocation_group;
0266             run->start = array[i].start + offset;
0267             run->len = array[i].len - offset;
0268
0269             befs_debug(sb, "---> %s, "
0270                    "found %lu at direct[%d]", __func__,
0271                    (unsigned long)blockno, i);
0272             return BEFS_OK;
0273         }
0274     }
0275
0276     befs_error(sb, "%s failed to find file block %lu", __func__,
0277            (unsigned long)blockno);
0278     befs_debug(sb, "---> %s ERROR", __func__);
0279     return BEFS_ERR;
0280 }
0281
0282 /**
0283  * befs_find_brun_indirect - find a block run in the datastream
0284  * @sb: the superblock
0285  * @data: the datastream
0286  * @blockno: the blocknumber to find
0287  * @run: The found run is passed back through this pointer
0288  *
0289  * Finds the block run that starts at file block number blockno
0290  * in the file represented by the datastream data, if that
0291  * blockno is in the indirect region of the datastream.
0292  *
0293  * Return value is BEFS_OK if the blockrun is found, BEFS_ERR
0294  * otherwise.
0295  *
0296  * Algorithm:
0297  * For each block in the indirect run of the datastream, read
0298  * it in and search through it for search_blk.
0299  *
0300  * XXX:
0301  * Really should check to make sure blockno is inside indirect
0302  * region.
0303  */
0304 static int
0305 befs_find_brun_indirect(struct super_block *sb,
0306             const befs_data_stream *data,
0307             befs_blocknr_t blockno,
0308             befs_block_run *run)
0309 {
0310     int i, j;
0311     befs_blocknr_t sum = 0;
0312     befs_blocknr_t indir_start_blk;
0313     befs_blocknr_t search_blk;
0314     struct buffer_head *indirblock;
0315     befs_disk_block_run *array;
0316
0317     befs_block_run indirect = data->indirect;
0318     befs_blocknr_t indirblockno = iaddr2blockno(sb, &indirect);
0319     int arraylen = befs_iaddrs_per_block(sb);
0320
0321     befs_debug(sb, "---> %s, find %lu", __func__, (unsigned long)blockno);
0322
0323     indir_start_blk = data->max_direct_range >> BEFS_SB(sb)->block_shift;
0324     search_blk = blockno - indir_start_blk;
0325
0326     /* Examine blocks of the indirect run one at a time */
0327     for (i = 0; i < indirect.len; i++) {
0328         indirblock = sb_bread(sb, indirblockno + i);
0329         if (indirblock == NULL) {
0330             befs_error(sb, "---> %s failed to read "
0331                    "disk block %lu from the indirect brun",
0332                    __func__, (unsigned long)indirblockno + i);
0333             befs_debug(sb, "<--- %s ERROR", __func__);
0334             return BEFS_ERR;
0335         }
0336
0337         array = (befs_disk_block_run *) indirblock->b_data;
0338
0339         for (j = 0; j < arraylen; ++j) {
0340             int len = fs16_to_cpu(sb, array[j].len);
0341
0342             if (search_blk >= sum && search_blk < sum + len) {
0343                 int offset = search_blk - sum;
0344                 run->allocation_group =
0345                     fs32_to_cpu(sb, array[j].allocation_group);
0346                 run->start =
0347                     fs16_to_cpu(sb, array[j].start) + offset;
0348                 run->len =
0349                     fs16_to_cpu(sb, array[j].len) - offset;
0350
0351                 brelse(indirblock);
0352                 befs_debug(sb,
0353                        "<--- %s found file block "
0354                        "%lu at indirect[%d]", __func__,
0355                        (unsigned long)blockno,
0356                        j + (i * arraylen));
0357                 return BEFS_OK;
0358             }
0359             sum += len;
0360         }
0361
0362         brelse(indirblock);
0363     }
0364
0365     /* Only fallthrough is an error */
0366     befs_error(sb, "BeFS: %s failed to find "
0367            "file block %lu", __func__, (unsigned long)blockno);
0368
0369     befs_debug(sb, "<--- %s ERROR", __func__);
0370     return BEFS_ERR;
0371 }
0372
0373 /**
0374  * befs_find_brun_dblindirect - find a block run in the datastream
0375  * @sb: the superblock
0376  * @data: the datastream
0377  * @blockno: the blocknumber to find
0378  * @run: The found run is passed back through this pointer
0379  *
0380  * Finds the block run that starts at file block number blockno
0381  * in the file represented by the datastream data, if that
0382  * blockno is in the double-indirect region of the datastream.
0383  *
0384  * Return value is BEFS_OK if the blockrun is found, BEFS_ERR
0385  * otherwise.
0386  *
0387  * Algorithm:
0388  * The block runs in the double-indirect region are different.
0389  * They are always allocated 4 fs blocks at a time, so each
0390  * block run maps a constant amount of file data. This means
0391  * that we can directly calculate how many block runs into the
0392  * double-indirect region we need to go to get to the one that
0393  * maps a particular filesystem block.
0394  *
0395  * We do this in two stages. First we calculate which of the
0396  * inode addresses in the double-indirect block will point us
0397  * to the indirect block that contains the mapping for the data,
0398  * then we calculate which of the inode addresses in that
0399  * indirect block maps the data block we are after.
0400  *
0401  * Oh, and once we've done that, we actually read in the blocks
0402  * that contain the inode addresses we calculated above. Even
0403  * though the double-indirect run may be several blocks long,
0404  * we can calculate which of those blocks will contain the index
0405  * we are after and only read that one. We then follow it to
0406  * the indirect block and perform a similar process to find
0407  * the actual block run that maps the data block we are interested
0408  * in.
0409  *
0410  * Then we offset the run as in befs_find_brun_array() and we are
0411  * done.
0412  */
0413 static int
0414 befs_find_brun_dblindirect(struct super_block *sb,
0415                const befs_data_stream *data,
0416                befs_blocknr_t blockno,
0417                befs_block_run *run)
0418 {
0419     int dblindir_indx;
0420     int indir_indx;
0421     int offset;
0422     int dbl_which_block;
0423     int which_block;
0424     int dbl_block_indx;
0425     int block_indx;
0426     off_t dblindir_leftover;
0427     befs_blocknr_t blockno_at_run_start;
0428     struct buffer_head *dbl_indir_block;
0429     struct buffer_head *indir_block;
0430     befs_block_run indir_run;
0431     befs_disk_inode_addr *iaddr_array;
0432
0433     befs_blocknr_t indir_start_blk =
0434         data->max_indirect_range >> BEFS_SB(sb)->block_shift;
0435
0436     off_t dbl_indir_off = blockno - indir_start_blk;
0437
0438     /* number of data blocks mapped by each of the iaddrs in
0439      * the indirect block pointed to by the double indirect block
0440      */
0441     size_t iblklen = BEFS_DBLINDIR_BRUN_LEN;
0442
0443     /* number of data blocks mapped by each of the iaddrs in
0444      * the double indirect block
0445      */
0446     size_t diblklen = iblklen * befs_iaddrs_per_block(sb)
0447         * BEFS_DBLINDIR_BRUN_LEN;
0448
0449     befs_debug(sb, "---> %s find %lu", __func__, (unsigned long)blockno);
0450
0451     /* First, discover which of the double_indir->indir blocks
0452      * contains pos. Then figure out how much of pos that
0453      * accounted for. Then discover which of the iaddrs in
0454      * the indirect block contains pos.
0455      */
0456
0457     dblindir_indx = dbl_indir_off / diblklen;
0458     dblindir_leftover = dbl_indir_off % diblklen;
0459     indir_indx = dblindir_leftover / diblklen;
0460
0461     /* Read double indirect block */
0462     dbl_which_block = dblindir_indx / befs_iaddrs_per_block(sb);
0463     if (dbl_which_block > data->double_indirect.len) {
0464         befs_error(sb, "The double-indirect index calculated by "
0465                "%s, %d, is outside the range "
0466                "of the double-indirect block", __func__,
0467                dblindir_indx);
0468         return BEFS_ERR;
0469     }
0470
0471     dbl_indir_block =
0472         sb_bread(sb, iaddr2blockno(sb, &data->double_indirect) +
0473                     dbl_which_block);
0474     if (dbl_indir_block == NULL) {
0475         befs_error(sb, "%s couldn't read the "
0476                "double-indirect block at blockno %lu", __func__,
0477                (unsigned long)
0478                iaddr2blockno(sb, &data->double_indirect) +
0479                dbl_which_block);
0480         return BEFS_ERR;
0481     }
0482
0483     dbl_block_indx =
0484         dblindir_indx - (dbl_which_block * befs_iaddrs_per_block(sb));
0485     iaddr_array = (befs_disk_inode_addr *) dbl_indir_block->b_data;
0486     indir_run = fsrun_to_cpu(sb, iaddr_array[dbl_block_indx]);
0487     brelse(dbl_indir_block);
0488
0489     /* Read indirect block */
0490     which_block = indir_indx / befs_iaddrs_per_block(sb);
0491     if (which_block > indir_run.len) {
0492         befs_error(sb, "The indirect index calculated by "
0493                "%s, %d, is outside the range "
0494                "of the indirect block", __func__, indir_indx);
0495         return BEFS_ERR;
0496     }
0497
0498     indir_block =
0499         sb_bread(sb, iaddr2blockno(sb, &indir_run) + which_block);
0500     if (indir_block == NULL) {
0501         befs_error(sb, "%s couldn't read the indirect block "
0502                "at blockno %lu", __func__, (unsigned long)
0503                iaddr2blockno(sb, &indir_run) + which_block);
0504         return BEFS_ERR;
0505     }
0506
0507     block_indx = indir_indx - (which_block * befs_iaddrs_per_block(sb));
0508     iaddr_array = (befs_disk_inode_addr *) indir_block->b_data;
0509     *run = fsrun_to_cpu(sb, iaddr_array[block_indx]);
0510     brelse(indir_block);
0511
0512     blockno_at_run_start = indir_start_blk;
0513     blockno_at_run_start += diblklen * dblindir_indx;
0514     blockno_at_run_start += iblklen * indir_indx;
0515     offset = blockno - blockno_at_run_start;
0516
0517     run->start += offset;
0518     run->len -= offset;
0519
0520     befs_debug(sb, "Found file block %lu in double_indirect[%d][%d],"
0521            " double_indirect_leftover = %lu", (unsigned long)
0522            blockno, dblindir_indx, indir_indx, dblindir_leftover);
0523
0524     return BEFS_OK;
0525 }