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