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/slab.h>
  15 #include <linux/buffer_head.h>
  16 #include <linux/string.h>
  17
  18 #include "befs.h"
  19 #include "datastream.h"
  20 #include "io.h"
  21
  22 const befs_inode_addr BAD_IADDR = { 0, 0, 0 };
  23
  24 static int befs_find_brun_direct(struct super_block *sb,
  25                                  befs_data_stream * data,
  26                                  befs_blocknr_t blockno, befs_block_run * run);
  27
  28 static int befs_find_brun_indirect(struct super_block *sb,
  29                                    befs_data_stream * data,
  30                                    befs_blocknr_t blockno,
  31                                    befs_block_run * run);
  32
  33 static int befs_find_brun_dblindirect(struct super_block *sb,
  34                                       befs_data_stream * data,
  35                                       befs_blocknr_t blockno,
  36                                       befs_block_run * run);
  37
  38 /**
  39  * befs_read_datastream - get buffer_head containing data, starting from pos.
  40  * @sb: Filesystem superblock
  41  * @ds: datastrem to find data with
  42  * @pos: start of data
  43  * @off: offset of data in buffer_head->b_data
  44  *
  45  * Returns pointer to buffer_head containing data starting with offset @off,
  46  * if you don't need to know offset just set @off = NULL.
  47  */
  48 struct buffer_head *
  49 befs_read_datastream(struct super_block *sb, befs_data_stream * ds,
  50                      befs_off_t pos, uint * off)
  51 {
  52         struct buffer_head *bh = NULL;
  53         befs_block_run run;
  54         befs_blocknr_t block;   /* block coresponding to pos */
  55
  56         befs_debug(sb, "---> befs_read_datastream() %Lu", pos);
  57         block = pos >> BEFS_SB(sb)->block_shift;
  58         if (off)
  59                 *off = pos - (block << BEFS_SB(sb)->block_shift);
  60
  61         if (befs_fblock2brun(sb, ds, block, &run) != BEFS_OK) {
  62                 befs_error(sb, "BeFS: Error finding disk addr of block %lu",
  63                            block);
  64                 befs_debug(sb, "<--- befs_read_datastream() ERROR");
  65                 return NULL;
  66         }
  67         bh = befs_bread_iaddr(sb, run);
  68         if (!bh) {
  69                 befs_error(sb, "BeFS: Error reading block %lu from datastream",
  70                            block);
  71                 return NULL;
  72         }
  73
  74         befs_debug(sb, "<--- befs_read_datastream() read data, starting at %Lu",
  75                    pos);
  76
  77         return bh;
  78 }
  79
  80 /*
  81  * Takes a file position and gives back a brun who's starting block
  82  * is block number fblock of the file.
  83  *
  84  * Returns BEFS_OK or BEFS_ERR.
  85  *
  86  * Calls specialized functions for each of the three possible
  87  * datastream regions.
  88  *
  89  * 2001-11-15 Will Dyson
  90  */
  91 int
  92 befs_fblock2brun(struct super_block *sb, befs_data_stream * data,
  93                  befs_blocknr_t fblock, befs_block_run * run)
  94 {
  95         int err;
  96         befs_off_t pos = fblock << BEFS_SB(sb)->block_shift;
  97
  98         if (pos < data->max_direct_range) {
  99                 err = befs_find_brun_direct(sb, data, fblock, run);
 100
 101         } else if (pos < data->max_indirect_range) {
 102                 err = befs_find_brun_indirect(sb, data, fblock, run);
 103
 104         } else if (pos < data->max_double_indirect_range) {
 105                 err = befs_find_brun_dblindirect(sb, data, fblock, run);
 106
 107         } else {
 108                 befs_error(sb,
 109                            "befs_fblock2brun() was asked to find block %lu, "
 110                            "which is not mapped by the datastream\n", fblock);
 111                 err = BEFS_ERR;
 112         }
 113         return err;
 114 }
 115
 116 /**
 117  * befs_read_lsmylink - read long symlink from datastream.
 118  * @sb: Filesystem superblock
 119  * @ds: Datastrem to read from
 120  * @buf: Buffer in which to place long symlink data
 121  * @len: Length of the long symlink in bytes
 122  *
 123  * Returns the number of bytes read
 124  */
 125 size_t
 126 befs_read_lsymlink(struct super_block * sb, befs_data_stream * ds, void *buff,
 127                    befs_off_t len)
 128 {
 129         befs_off_t bytes_read = 0;      /* bytes readed */
 130         u16 plen;
 131         struct buffer_head *bh = NULL;
 132         befs_debug(sb, "---> befs_read_lsymlink() length: %Lu", len);
 133
 134         while (bytes_read < len) {
 135                 bh = befs_read_datastream(sb, ds, bytes_read, NULL);
 136                 if (!bh) {
 137                         befs_error(sb, "BeFS: Error reading datastream block "
 138                                    "starting from %Lu", bytes_read);
 139                         befs_debug(sb, "<--- befs_read_lsymlink() ERROR");
 140                         return bytes_read;
 141
 142                 }
 143                 plen = ((bytes_read + BEFS_SB(sb)->block_size) < len) ?
 144                     BEFS_SB(sb)->block_size : len - bytes_read;
 145                 memcpy(buff + bytes_read, bh->b_data, plen);
 146                 brelse(bh);
 147                 bytes_read += plen;
 148         }
 149
 150         befs_debug(sb, "<--- befs_read_lsymlink() read %u bytes", 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, 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         befs_sb_info *befs_sb = BEFS_SB(sb);
 172
 173         befs_debug(sb, "---> befs_count_blocks()");
 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, "<--- befs_count_blocks() %u blocks", 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 lenght 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, befs_data_stream * data,
 247                       befs_blocknr_t blockno, befs_block_run * run)
 248 {
 249         int i;
 250         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, "---> befs_find_brun_direct(), find %lu", blockno);
 256
 257         if (blockno > max_block) {
 258                 befs_error(sb, "befs_find_brun_direct() passed block outside of"
 259                            "direct region");
 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, "---> befs_find_brun_direct(), "
 272                                    "found %lu at direct[%d]", blockno, i);
 273                         return BEFS_OK;
 274                 }
 275         }
 276
 277         befs_debug(sb, "---> befs_find_brun_direct() ERROR");
 278         return BEFS_ERR;
 279 }
 280
 281 /*
 282         Finds the block run that starts at file block number blockno
 283         in the file represented by the datastream data, if that
 284         blockno is in the indirect region of the datastream.
 285
 286         sb: the superblock
 287         data: the datastream
 288         blockno: the blocknumber to find
 289         run: The found run is passed back through this pointer
 290
 291         Return value is BEFS_OK if the blockrun is found, BEFS_ERR
 292         otherwise.
 293
 294         Algorithm:
 295         For each block in the indirect run of the datastream, read
 296         it in and search through it for search_blk.
 297
 298         XXX:
 299         Really should check to make sure blockno is inside indirect
 300         region.
 301
 302         2001-11-15 Will Dyson
 303 */
 304 static int
 305 befs_find_brun_indirect(struct super_block *sb,
 306                         befs_data_stream * data, befs_blocknr_t blockno,
 307                         befs_block_run * run)
 308 {
 309         int i, j;
 310         befs_blocknr_t sum = 0;
 311         befs_blocknr_t indir_start_blk;
 312         befs_blocknr_t search_blk;
 313         struct buffer_head *indirblock;
 314         befs_disk_block_run *array;
 315
 316         befs_block_run indirect = data->indirect;
 317         befs_blocknr_t indirblockno = iaddr2blockno(sb, &indirect);
 318         int arraylen = befs_iaddrs_per_block(sb);
 319
 320         befs_debug(sb, "---> befs_find_brun_indirect(), find %lu", blockno);
 321
 322         indir_start_blk = data->max_direct_range >> BEFS_SB(sb)->block_shift;
 323         search_blk = blockno - indir_start_blk;
 324
 325         /* Examine blocks of the indirect run one at a time */
 326         for (i = 0; i < indirect.len; i++) {
 327                 indirblock = befs_bread(sb, indirblockno + i);
 328                 if (indirblock == NULL) {
 329                         befs_debug(sb,
 330                                    "---> befs_find_brun_indirect() failed to "
 331                                    "read disk block %lu from the indirect brun",
 332                                    indirblockno + i);
 333                         return BEFS_ERR;
 334                 }
 335
 336                 array = (befs_disk_block_run *) indirblock->b_data;
 337
 338                 for (j = 0; j < arraylen; ++j) {
 339                         int len = fs16_to_cpu(sb, array[j].len);
 340
 341                         if (search_blk >= sum && search_blk < sum + len) {
 342                                 int offset = search_blk - sum;
 343                                 run->allocation_group =
 344                                     fs32_to_cpu(sb, array[j].allocation_group);
 345                                 run->start =
 346                                     fs16_to_cpu(sb, array[j].start) + offset;
 347                                 run->len =
 348                                     fs16_to_cpu(sb, array[j].len) - offset;
 349
 350                                 brelse(indirblock);
 351                                 befs_debug(sb,
 352                                            "<--- befs_find_brun_indirect() found "
 353                                            "file block %lu at indirect[%d]",
 354                                            blockno, j + (i * arraylen));
 355                                 return BEFS_OK;
 356                         }
 357                         sum += len;
 358                 }
 359
 360                 brelse(indirblock);
 361         }
 362
 363         /* Only fallthrough is an error */
 364         befs_error(sb, "BeFS: befs_find_brun_indirect() failed to find "
 365                    "file block %lu", blockno);
 366
 367         befs_debug(sb, "<--- befs_find_brun_indirect() ERROR");
 368         return BEFS_ERR;
 369 }
 370
 371 /*
 372         Finds the block run that starts at file block number blockno
 373         in the file represented by the datastream data, if that
 374         blockno is in the double-indirect region of the datastream.
 375
 376         sb: the superblock
 377         data: the datastream
 378         blockno: the blocknumber to find
 379         run: The found run is passed back through this pointer
 380
 381         Return value is BEFS_OK if the blockrun is found, BEFS_ERR
 382         otherwise.
 383
 384         Algorithm:
 385         The block runs in the double-indirect region are different.
 386         They are always allocated 4 fs blocks at a time, so each
 387         block run maps a constant amount of file data. This means
 388         that we can directly calculate how many block runs into the
 389         double-indirect region we need to go to get to the one that
 390         maps a particular filesystem block.
 391
 392         We do this in two stages. First we calculate which of the
 393         inode addresses in the double-indirect block will point us
 394         to the indirect block that contains the mapping for the data,
 395         then we calculate which of the inode addresses in that
 396         indirect block maps the data block we are after.
 397
 398         Oh, and once we've done that, we actually read in the blocks
 399         that contain the inode addresses we calculated above. Even
 400         though the double-indirect run may be several blocks long,
 401         we can calculate which of those blocks will contain the index
 402         we are after and only read that one. We then follow it to
 403         the indirect block and perform a  similar process to find
 404         the actual block run that maps the data block we are interested
 405         in.
 406
 407         Then we offset the run as in befs_find_brun_array() and we are
 408         done.
 409
 410         2001-11-15 Will Dyson
 411 */
 412 static int
 413 befs_find_brun_dblindirect(struct super_block *sb,
 414                            befs_data_stream * data, befs_blocknr_t blockno,
 415                            befs_block_run * run)
 416 {
 417         int dblindir_indx;
 418         int indir_indx;
 419         int offset;
 420         int dbl_which_block;
 421         int which_block;
 422         int dbl_block_indx;
 423         int block_indx;
 424         off_t dblindir_leftover;
 425         befs_blocknr_t blockno_at_run_start;
 426         struct buffer_head *dbl_indir_block;
 427         struct buffer_head *indir_block;
 428         befs_block_run indir_run;
 429         befs_disk_inode_addr *iaddr_array = NULL;
 430         befs_sb_info *befs_sb = BEFS_SB(sb);
 431
 432         befs_blocknr_t indir_start_blk =
 433             data->max_indirect_range >> befs_sb->block_shift;
 434
 435         off_t dbl_indir_off = blockno - indir_start_blk;
 436
 437         /* number of data blocks mapped by each of the iaddrs in
 438          * the indirect block pointed to by the double indirect block
 439          */
 440         size_t iblklen = BEFS_DBLINDIR_BRUN_LEN;
 441
 442         /* number of data blocks mapped by each of the iaddrs in
 443          * the double indirect block
 444          */
 445         size_t diblklen = iblklen * befs_iaddrs_per_block(sb)
 446             * BEFS_DBLINDIR_BRUN_LEN;
 447
 448         befs_debug(sb, "---> befs_find_brun_dblindirect() find %lu", blockno);
 449
 450         /* First, discover which of the double_indir->indir blocks
 451          * contains pos. Then figure out how much of pos that
 452          * accounted for. Then discover which of the iaddrs in
 453          * the indirect block contains pos.
 454          */
 455
 456         dblindir_indx = dbl_indir_off / diblklen;
 457         dblindir_leftover = dbl_indir_off % diblklen;
 458         indir_indx = dblindir_leftover / diblklen;
 459
 460         /* Read double indirect block */
 461         dbl_which_block = dblindir_indx / befs_iaddrs_per_block(sb);
 462         if (dbl_which_block > data->double_indirect.len) {
 463                 befs_error(sb, "The double-indirect index calculated by "
 464                            "befs_read_brun_dblindirect(), %d, is outside the range "
 465                            "of the double-indirect block", dblindir_indx);
 466                 return BEFS_ERR;
 467         }
 468
 469         dbl_indir_block =
 470             befs_bread(sb, iaddr2blockno(sb, &data->double_indirect) +
 471                                         dbl_which_block);
 472         if (dbl_indir_block == NULL) {
 473                 befs_error(sb, "befs_read_brun_dblindirect() couldn't read the "
 474                            "double-indirect block at blockno %lu",
 475                            iaddr2blockno(sb,
 476                                          &data->double_indirect) +
 477                            dbl_which_block);
 478                 brelse(dbl_indir_block);
 479                 return BEFS_ERR;
 480         }
 481
 482         dbl_block_indx =
 483             dblindir_indx - (dbl_which_block * befs_iaddrs_per_block(sb));
 484         iaddr_array = (befs_disk_inode_addr *) dbl_indir_block->b_data;
 485         indir_run = fsrun_to_cpu(sb, iaddr_array[dbl_block_indx]);
 486         brelse(dbl_indir_block);
 487         iaddr_array = NULL;
 488
 489         /* Read indirect block */
 490         which_block = indir_indx / befs_iaddrs_per_block(sb);
 491         if (which_block > indir_run.len) {
 492                 befs_error(sb, "The indirect index calculated by "
 493                            "befs_read_brun_dblindirect(), %d, is outside the range "
 494                            "of the indirect block", indir_indx);
 495                 return BEFS_ERR;
 496         }
 497
 498         indir_block =
 499             befs_bread(sb, iaddr2blockno(sb, &indir_run) + which_block);
 500         if (indir_block == NULL) {
 501                 befs_error(sb, "befs_read_brun_dblindirect() couldn't read the "
 502                            "indirect block at blockno %lu",
 503                            iaddr2blockno(sb, &indir_run) + which_block);
 504                 brelse(indir_block);
 505                 return BEFS_ERR;
 506         }
 507
 508         block_indx = indir_indx - (which_block * befs_iaddrs_per_block(sb));
 509         iaddr_array = (befs_disk_inode_addr *) indir_block->b_data;
 510         *run = fsrun_to_cpu(sb, iaddr_array[block_indx]);
 511         brelse(indir_block);
 512         iaddr_array = NULL;
 513
 514         blockno_at_run_start = indir_start_blk;
 515         blockno_at_run_start += diblklen * dblindir_indx;
 516         blockno_at_run_start += iblklen * indir_indx;
 517         offset = blockno - blockno_at_run_start;
 518
 519         run->start += offset;
 520         run->len -= offset;
 521
 522         befs_debug(sb, "Found file block %lu in double_indirect[%d][%d],"
 523                    " double_indirect_leftover = %lu",
 524                    blockno, dblindir_indx, indir_indx, dblindir_leftover);
 525
 526         return BEFS_OK;
 527 }