fs/befs/datastream.c

   1 /*
   2  * linux/fs/befs/datastream.c
   3  *
   4  * Copyright (C) 2001 Will Dyson <will_dyson@pobox.com>
   5  *
   6  * Based on portions of file.c by Makoto Kato <m_kato@ga2.so-net.ne.jp>
   7  *
   8  * Many thanks to Dominic Giampaolo, author of "Practical File System
   9  * Design with the Be File System", for such a helpful book.
  10  *
  11  */
  12
  13 #include <linux/kernel.h>
  14 #include <linux/buffer_head.h>
  15 #include <linux/string.h>
  16
  17 #include "befs.h"
  18 #include "datastream.h"
  19 #include "io.h"
  20
  21 const befs_inode_addr BAD_IADDR = { 0, 0, 0 };
  22
  23 static int befs_find_brun_direct(struct super_block *sb,
  24                                  const befs_data_stream *data,
  25                                  befs_blocknr_t blockno, befs_block_run * run);
  26
  27 static int befs_find_brun_indirect(struct super_block *sb,
  28                                    const befs_data_stream *data,
  29                                    befs_blocknr_t blockno,
  30                                    befs_block_run * run);
  31
  32 static int befs_find_brun_dblindirect(struct super_block *sb,
  33                                       const befs_data_stream *data,
  34                                       befs_blocknr_t blockno,
  35                                       befs_block_run * run);
  36
  37 /**
  38  * befs_read_datastream - get buffer_head containing data, starting from pos.
  39  * @sb: Filesystem superblock
  40  * @ds: datastrem to find data with
  41  * @pos: start of data
  42  * @off: offset of data in buffer_head->b_data
  43  *
  44  * Returns pointer to buffer_head containing data starting with offset @off,
  45  * if you don't need to know offset just set @off = NULL.
  46  */
  47 struct buffer_head *
  48 befs_read_datastream(struct super_block *sb, const befs_data_stream *ds,
  49                      befs_off_t pos, uint * off)
  50 {
  51         struct buffer_head *bh;
  52         befs_block_run run;
  53         befs_blocknr_t block;   /* block coresponding to pos */
  54
  55         befs_debug(sb, "---> %s %llu", __func__, pos);
  56         block = pos >> BEFS_SB(sb)->block_shift;
  57         if (off)
  58                 *off = pos - (block << BEFS_SB(sb)->block_shift);
  59
  60         if (befs_fblock2brun(sb, ds, block, &run) != BEFS_OK) {
  61                 befs_error(sb, "BeFS: Error finding disk addr of block %lu",
  62                            (unsigned long)block);
  63                 befs_debug(sb, "<--- %s ERROR", __func__);
  64                 return NULL;
  65         }
  66         bh = befs_bread_iaddr(sb, run);
  67         if (!bh) {
  68                 befs_error(sb, "BeFS: Error reading block %lu from datastream",
  69                            (unsigned long)block);
  70                 return NULL;
  71         }
  72
  73         befs_debug(sb, "<--- %s read data, starting at %llu", __func__, pos);
  74
  75         return bh;
  76 }
  77
  78 /*
  79  * Takes a file position and gives back a brun who's starting block
  80  * is block number fblock of the file.
  81  *
  82  * Returns BEFS_OK or BEFS_ERR.
  83  *
  84  * Calls specialized functions for each of the three possible
  85  * datastream regions.
  86  *
  87  * 2001-11-15 Will Dyson
  88  */
  89 int
  90 befs_fblock2brun(struct super_block *sb, const befs_data_stream *data,
  91                  befs_blocknr_t fblock, befs_block_run * run)
  92 {
  93         int err;
  94         befs_off_t pos = fblock << BEFS_SB(sb)->block_shift;
  95
  96         if (pos < data->max_direct_range) {
  97                 err = befs_find_brun_direct(sb, data, fblock, run);
  98
  99         } else if (pos < data->max_indirect_range) {
 100                 err = befs_find_brun_indirect(sb, data, fblock, run);
 101
 102         } else if (pos < data->max_double_indirect_range) {
 103                 err = befs_find_brun_dblindirect(sb, data, fblock, run);
 104
 105         } else {
 106                 befs_error(sb,
 107                            "befs_fblock2brun() was asked to find block %lu, "
 108                            "which is not mapped by the datastream\n",
 109                            (unsigned long)fblock);
 110                 err = BEFS_ERR;
 111         }
 112         return err;
 113 }
 114
 115 /**
 116  * befs_read_lsmylink - read long symlink from datastream.
 117  * @sb: Filesystem superblock
 118  * @ds: Datastrem to read from
 119  * @buff: Buffer in which to place long symlink data
 120  * @len: Length of the long symlink in bytes
 121  *
 122  * Returns the number of bytes read
 123  */
 124 size_t
 125 befs_read_lsymlink(struct super_block *sb, const befs_data_stream *ds,
 126                    void *buff, befs_off_t len)
 127 {
 128         befs_off_t bytes_read = 0;      /* bytes readed */
 129         u16 plen;
 130         struct buffer_head *bh;
 131         befs_debug(sb, "---> %s length: %llu", __func__, len);
 132
 133         while (bytes_read < len) {
 134                 bh = befs_read_datastream(sb, ds, bytes_read, NULL);
 135                 if (!bh) {
 136                         befs_error(sb, "BeFS: Error reading datastream block "
 137                                    "starting from %llu", bytes_read);
 138                         befs_debug(sb, "<--- %s ERROR", __func__);
 139                         return bytes_read;
 140
 141                 }
 142                 plen = ((bytes_read + BEFS_SB(sb)->block_size) < len) ?
 143                     BEFS_SB(sb)->block_size : len - bytes_read;
 144                 memcpy(buff + bytes_read, bh->b_data, plen);
 145                 brelse(bh);
 146                 bytes_read += plen;
 147         }
 148
 149         befs_debug(sb, "<--- %s read %u bytes", __func__, (unsigned int)
 150                    bytes_read);
 151         return bytes_read;
 152 }
 153
 154 /**
 155  * befs_count_blocks - blocks used by a file
 156  * @sb: Filesystem superblock
 157  * @ds: Datastream of the file
 158  *
 159  * Counts the number of fs blocks that the file represented by
 160  * inode occupies on the filesystem, counting both regular file
 161  * data and filesystem metadata (and eventually attribute data
 162  * when we support attributes)
 163 */
 164
 165 befs_blocknr_t
 166 befs_count_blocks(struct super_block *sb, const befs_data_stream *ds)
 167 {
 168         befs_blocknr_t blocks;
 169         befs_blocknr_t datablocks;      /* File data blocks */
 170         befs_blocknr_t metablocks;      /* FS metadata blocks */
 171         struct befs_sb_info *befs_sb = BEFS_SB(sb);
 172
 173         befs_debug(sb, "---> %s", __func__);
 174
 175         datablocks = ds->size >> befs_sb->block_shift;
 176         if (ds->size & (befs_sb->block_size - 1))
 177                 datablocks += 1;
 178
 179         metablocks = 1;         /* Start with 1 block for inode */
 180
 181         /* Size of indirect block */
 182         if (ds->size > ds->max_direct_range)
 183                 metablocks += ds->indirect.len;
 184
 185         /*
 186            Double indir block, plus all the indirect blocks it mapps
 187            In the double-indirect range, all block runs of data are
 188            BEFS_DBLINDIR_BRUN_LEN blocks long. Therefore, we know
 189            how many data block runs are in the double-indirect region,
 190            and from that we know how many indirect blocks it takes to
 191            map them. We assume that the indirect blocks are also
 192            BEFS_DBLINDIR_BRUN_LEN blocks long.
 193          */
 194         if (ds->size > ds->max_indirect_range && ds->max_indirect_range != 0) {
 195                 uint dbl_bytes;
 196                 uint dbl_bruns;
 197                 uint indirblocks;
 198
 199                 dbl_bytes =
 200                     ds->max_double_indirect_range - ds->max_indirect_range;
 201                 dbl_bruns =
 202                     dbl_bytes / (befs_sb->block_size * BEFS_DBLINDIR_BRUN_LEN);
 203                 indirblocks = dbl_bruns / befs_iaddrs_per_block(sb);
 204
 205                 metablocks += ds->double_indirect.len;
 206                 metablocks += indirblocks;
 207         }
 208
 209         blocks = datablocks + metablocks;
 210         befs_debug(sb, "<--- %s %u blocks", __func__, (unsigned int)blocks);
 211
 212         return blocks;
 213 }
 214
 215 /*
 216         Finds the block run that starts at file block number blockno
 217         in the file represented by the datastream data, if that
 218         blockno is in the direct region of the datastream.
 219
 220         sb: the superblock
 221         data: the datastream
 222         blockno: the blocknumber to find
 223         run: The found run is passed back through this pointer
 224
 225         Return value is BEFS_OK if the blockrun is found, BEFS_ERR
 226         otherwise.
 227
 228         Algorithm:
 229         Linear search. Checks each element of array[] to see if it
 230         contains the blockno-th filesystem block. This is necessary
 231         because the block runs map variable amounts of data. Simply
 232         keeps a count of the number of blocks searched so far (sum),
 233         incrementing this by the length of each block run as we come
 234         across it. Adds sum to *count before returning (this is so
 235         you can search multiple arrays that are logicaly one array,
 236         as in the indirect region code).
 237
 238         When/if blockno is found, if blockno is inside of a block
 239         run as stored on disk, we offset the start and length members
 240         of the block run, so that blockno is the start and len is
 241         still valid (the run ends in the same place).
 242
 243         2001-11-15 Will Dyson
 244 */
 245 static int
 246 befs_find_brun_direct(struct super_block *sb, const befs_data_stream *data,
 247                       befs_blocknr_t blockno, befs_block_run * run)
 248 {
 249         int i;
 250         const befs_block_run *array = data->direct;
 251         befs_blocknr_t sum;
 252         befs_blocknr_t max_block =
 253             data->max_direct_range >> BEFS_SB(sb)->block_shift;
 254
 255         befs_debug(sb, "---> %s, find %lu", __func__, (unsigned long)blockno);
 256
 257         if (blockno > max_block) {
 258                 befs_error(sb, "%s passed block outside of direct region",
 259                            __func__);
 260                 return BEFS_ERR;
 261         }
 262
 263         for (i = 0, sum = 0; i < BEFS_NUM_DIRECT_BLOCKS;
 264              sum += array[i].len, i++) {
 265                 if (blockno >= sum && blockno < sum + (array[i].len)) {
 266                         int offset = blockno - sum;
 267                         run->allocation_group = array[i].allocation_group;
 268                         run->start = array[i].start + offset;
 269                         run->len = array[i].len - offset;
 270
 271                         befs_debug(sb, "---> %s, "
 272                                    "found %lu at direct[%d]", __func__,
 273                                    (unsigned long)blockno, i);
 274                         return BEFS_OK;
 275                 }
 276         }
 277
 278         befs_debug(sb, "---> %s ERROR", __func__);
 279         return BEFS_ERR;
 280 }
 281
 282 /*
 283         Finds the block run that starts at file block number blockno
 284         in the file represented by the datastream data, if that
 285         blockno is in the indirect region of the datastream.
 286
 287         sb: the superblock
 288         data: the datastream
 289         blockno: the blocknumber to find
 290         run: The found run is passed back through this pointer
 291
 292         Return value is BEFS_OK if the blockrun is found, BEFS_ERR
 293         otherwise.
 294
 295         Algorithm:
 296         For each block in the indirect run of the datastream, read
 297         it in and search through it for search_blk.
 298
 299         XXX:
 300         Really should check to make sure blockno is inside indirect
 301         region.
 302
 303         2001-11-15 Will Dyson
 304 */
 305 static int
 306 befs_find_brun_indirect(struct super_block *sb,
 307                         const befs_data_stream *data,
 308                         befs_blocknr_t blockno,
 309                         befs_block_run * run)
 310 {
 311         int i, j;
 312         befs_blocknr_t sum = 0;
 313         befs_blocknr_t indir_start_blk;
 314         befs_blocknr_t search_blk;
 315         struct buffer_head *indirblock;
 316         befs_disk_block_run *array;
 317
 318         befs_block_run indirect = data->indirect;
 319         befs_blocknr_t indirblockno = iaddr2blockno(sb, &indirect);
 320         int arraylen = befs_iaddrs_per_block(sb);
 321
 322         befs_debug(sb, "---> %s, find %lu", __func__, (unsigned long)blockno);
 323
 324         indir_start_blk = data->max_direct_range >> BEFS_SB(sb)->block_shift;
 325         search_blk = blockno - indir_start_blk;
 326
 327         /* Examine blocks of the indirect run one at a time */
 328         for (i = 0; i < indirect.len; i++) {
 329                 indirblock = befs_bread(sb, indirblockno + i);
 330                 if (indirblock == NULL) {
 331                         befs_debug(sb, "---> %s failed to read "
 332                                    "disk block %lu from the indirect brun",
 333                                    __func__, (unsigned long)indirblockno + i);
 334                         return BEFS_ERR;
 335                 }
 336
 337                 array = (befs_disk_block_run *) indirblock->b_data;
 338
 339                 for (j = 0; j < arraylen; ++j) {
 340                         int len = fs16_to_cpu(sb, array[j].len);
 341
 342                         if (search_blk >= sum && search_blk < sum + len) {
 343                                 int offset = search_blk - sum;
 344                                 run->allocation_group =
 345                                     fs32_to_cpu(sb, array[j].allocation_group);
 346                                 run->start =
 347                                     fs16_to_cpu(sb, array[j].start) + offset;
 348                                 run->len =
 349                                     fs16_to_cpu(sb, array[j].len) - offset;
 350
 351                                 brelse(indirblock);
 352                                 befs_debug(sb,
 353                                            "<--- %s found file block "
 354                                            "%lu at indirect[%d]", __func__,
 355                                            (unsigned long)blockno,
 356                                            j + (i * arraylen));
 357                                 return BEFS_OK;
 358                         }
 359                         sum += len;
 360                 }
 361
 362                 brelse(indirblock);
 363         }
 364
 365         /* Only fallthrough is an error */
 366         befs_error(sb, "BeFS: %s failed to find "
 367                    "file block %lu", __func__, (unsigned long)blockno);
 368
 369         befs_debug(sb, "<--- %s ERROR", __func__);
 370         return BEFS_ERR;
 371 }
 372
 373 /*
 374         Finds the block run that starts at file block number blockno
 375         in the file represented by the datastream data, if that
 376         blockno is in the double-indirect region of the datastream.
 377
 378         sb: the superblock
 379         data: the datastream
 380         blockno: the blocknumber to find
 381         run: The found run is passed back through this pointer
 382
 383         Return value is BEFS_OK if the blockrun is found, BEFS_ERR
 384         otherwise.
 385
 386         Algorithm:
 387         The block runs in the double-indirect region are different.
 388         They are always allocated 4 fs blocks at a time, so each
 389         block run maps a constant amount of file data. This means
 390         that we can directly calculate how many block runs into the
 391         double-indirect region we need to go to get to the one that
 392         maps a particular filesystem block.
 393
 394         We do this in two stages. First we calculate which of the
 395         inode addresses in the double-indirect block will point us
 396         to the indirect block that contains the mapping for the data,
 397         then we calculate which of the inode addresses in that
 398         indirect block maps the data block we are after.
 399
 400         Oh, and once we've done that, we actually read in the blocks
 401         that contain the inode addresses we calculated above. Even
 402         though the double-indirect run may be several blocks long,
 403         we can calculate which of those blocks will contain the index
 404         we are after and only read that one. We then follow it to
 405         the indirect block and perform a  similar process to find
 406         the actual block run that maps the data block we are interested
 407         in.
 408
 409         Then we offset the run as in befs_find_brun_array() and we are
 410         done.
 411
 412         2001-11-15 Will Dyson
 413 */
 414 static int
 415 befs_find_brun_dblindirect(struct super_block *sb,
 416                            const befs_data_stream *data,
 417                            befs_blocknr_t blockno,
 418                            befs_block_run * run)
 419 {
 420         int dblindir_indx;
 421         int indir_indx;
 422         int offset;
 423         int dbl_which_block;
 424         int which_block;
 425         int dbl_block_indx;
 426         int block_indx;
 427         off_t dblindir_leftover;
 428         befs_blocknr_t blockno_at_run_start;
 429         struct buffer_head *dbl_indir_block;
 430         struct buffer_head *indir_block;
 431         befs_block_run indir_run;
 432         befs_disk_inode_addr *iaddr_array;
 433         struct befs_sb_info *befs_sb = BEFS_SB(sb);
 434
 435         befs_blocknr_t indir_start_blk =
 436             data->max_indirect_range >> befs_sb->block_shift;
 437
 438         off_t dbl_indir_off = blockno - indir_start_blk;
 439
 440         /* number of data blocks mapped by each of the iaddrs in
 441          * the indirect block pointed to by the double indirect block
 442          */
 443         size_t iblklen = BEFS_DBLINDIR_BRUN_LEN;
 444
 445         /* number of data blocks mapped by each of the iaddrs in
 446          * the double indirect block
 447          */
 448         size_t diblklen = iblklen * befs_iaddrs_per_block(sb)
 449             * BEFS_DBLINDIR_BRUN_LEN;
 450
 451         befs_debug(sb, "---> %s find %lu", __func__, (unsigned long)blockno);
 452
 453         /* First, discover which of the double_indir->indir blocks
 454          * contains pos. Then figure out how much of pos that
 455          * accounted for. Then discover which of the iaddrs in
 456          * the indirect block contains pos.
 457          */
 458
 459         dblindir_indx = dbl_indir_off / diblklen;
 460         dblindir_leftover = dbl_indir_off % diblklen;
 461         indir_indx = dblindir_leftover / diblklen;
 462
 463         /* Read double indirect block */
 464         dbl_which_block = dblindir_indx / befs_iaddrs_per_block(sb);
 465         if (dbl_which_block > data->double_indirect.len) {
 466                 befs_error(sb, "The double-indirect index calculated by "
 467                            "%s, %d, is outside the range "
 468                            "of the double-indirect block", __func__,
 469                            dblindir_indx);
 470                 return BEFS_ERR;
 471         }
 472
 473         dbl_indir_block =
 474             befs_bread(sb, iaddr2blockno(sb, &data->double_indirect) +
 475                                         dbl_which_block);
 476         if (dbl_indir_block == NULL) {
 477                 befs_error(sb, "%s couldn't read the "
 478                            "double-indirect block at blockno %lu", __func__,
 479                            (unsigned long)
 480                            iaddr2blockno(sb, &data->double_indirect) +
 481                            dbl_which_block);
 482                 brelse(dbl_indir_block);
 483                 return BEFS_ERR;
 484         }
 485
 486         dbl_block_indx =
 487             dblindir_indx - (dbl_which_block * befs_iaddrs_per_block(sb));
 488         iaddr_array = (befs_disk_inode_addr *) dbl_indir_block->b_data;
 489         indir_run = fsrun_to_cpu(sb, iaddr_array[dbl_block_indx]);
 490         brelse(dbl_indir_block);
 491
 492         /* Read indirect block */
 493         which_block = indir_indx / befs_iaddrs_per_block(sb);
 494         if (which_block > indir_run.len) {
 495                 befs_error(sb, "The indirect index calculated by "
 496                            "%s, %d, is outside the range "
 497                            "of the indirect block", __func__, indir_indx);
 498                 return BEFS_ERR;
 499         }
 500
 501         indir_block =
 502             befs_bread(sb, iaddr2blockno(sb, &indir_run) + which_block);
 503         if (indir_block == NULL) {
 504                 befs_error(sb, "%s couldn't read the indirect block "
 505                            "at blockno %lu", __func__, (unsigned long)
 506                            iaddr2blockno(sb, &indir_run) + which_block);
 507                 brelse(indir_block);
 508                 return BEFS_ERR;
 509         }
 510
 511         block_indx = indir_indx - (which_block * befs_iaddrs_per_block(sb));
 512         iaddr_array = (befs_disk_inode_addr *) indir_block->b_data;
 513         *run = fsrun_to_cpu(sb, iaddr_array[block_indx]);
 514         brelse(indir_block);
 515
 516         blockno_at_run_start = indir_start_blk;
 517         blockno_at_run_start += diblklen * dblindir_indx;
 518         blockno_at_run_start += iblklen * indir_indx;
 519         offset = blockno - blockno_at_run_start;
 520
 521         run->start += offset;
 522         run->len -= offset;
 523
 524         befs_debug(sb, "Found file block %lu in double_indirect[%d][%d],"
 525                    " double_indirect_leftover = %lu", (unsigned long)
 526                    blockno, dblindir_indx, indir_indx, dblindir_leftover);
 527
 528         return BEFS_OK;
 529 }