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
 253         befs_debug(sb, "---> %s, find %lu", __func__, (unsigned long)blockno);
 254
 255         for (i = 0, sum = 0; i < BEFS_NUM_DIRECT_BLOCKS;
 256              sum += array[i].len, i++) {
 257                 if (blockno >= sum && blockno < sum + (array[i].len)) {
 258                         int offset = blockno - sum;
 259                         run->allocation_group = array[i].allocation_group;
 260                         run->start = array[i].start + offset;
 261                         run->len = array[i].len - offset;
 262
 263                         befs_debug(sb, "---> %s, "
 264                                    "found %lu at direct[%d]", __func__,
 265                                    (unsigned long)blockno, i);
 266                         return BEFS_OK;
 267                 }
 268         }
 269
 270         befs_error(sb, "%s failed to find file block %lu", __func__,
 271                    (unsigned long)blockno);
 272         befs_debug(sb, "---> %s ERROR", __func__);
 273         return BEFS_ERR;
 274 }
 275
 276 /*
 277         Finds the block run that starts at file block number blockno
 278         in the file represented by the datastream data, if that
 279         blockno is in the indirect region of the datastream.
 280
 281         sb: the superblock
 282         data: the datastream
 283         blockno: the blocknumber to find
 284         run: The found run is passed back through this pointer
 285
 286         Return value is BEFS_OK if the blockrun is found, BEFS_ERR
 287         otherwise.
 288
 289         Algorithm:
 290         For each block in the indirect run of the datastream, read
 291         it in and search through it for search_blk.
 292
 293         XXX:
 294         Really should check to make sure blockno is inside indirect
 295         region.
 296
 297         2001-11-15 Will Dyson
 298 */
 299 static int
 300 befs_find_brun_indirect(struct super_block *sb,
 301                         const befs_data_stream *data,
 302                         befs_blocknr_t blockno,
 303                         befs_block_run * run)
 304 {
 305         int i, j;
 306         befs_blocknr_t sum = 0;
 307         befs_blocknr_t indir_start_blk;
 308         befs_blocknr_t search_blk;
 309         struct buffer_head *indirblock;
 310         befs_disk_block_run *array;
 311
 312         befs_block_run indirect = data->indirect;
 313         befs_blocknr_t indirblockno = iaddr2blockno(sb, &indirect);
 314         int arraylen = befs_iaddrs_per_block(sb);
 315
 316         befs_debug(sb, "---> %s, find %lu", __func__, (unsigned long)blockno);
 317
 318         indir_start_blk = data->max_direct_range >> BEFS_SB(sb)->block_shift;
 319         search_blk = blockno - indir_start_blk;
 320
 321         /* Examine blocks of the indirect run one at a time */
 322         for (i = 0; i < indirect.len; i++) {
 323                 indirblock = sb_bread(sb, indirblockno + i);
 324                 if (indirblock == NULL) {
 325                         befs_error(sb, "---> %s failed to read "
 326                                    "disk block %lu from the indirect brun",
 327                                    __func__, (unsigned long)indirblockno + i);
 328                         befs_debug(sb, "<--- %s ERROR", __func__);
 329                         return BEFS_ERR;
 330                 }
 331
 332                 array = (befs_disk_block_run *) indirblock->b_data;
 333
 334                 for (j = 0; j < arraylen; ++j) {
 335                         int len = fs16_to_cpu(sb, array[j].len);
 336
 337                         if (search_blk >= sum && search_blk < sum + len) {
 338                                 int offset = search_blk - sum;
 339                                 run->allocation_group =
 340                                     fs32_to_cpu(sb, array[j].allocation_group);
 341                                 run->start =
 342                                     fs16_to_cpu(sb, array[j].start) + offset;
 343                                 run->len =
 344                                     fs16_to_cpu(sb, array[j].len) - offset;
 345
 346                                 brelse(indirblock);
 347                                 befs_debug(sb,
 348                                            "<--- %s found file block "
 349                                            "%lu at indirect[%d]", __func__,
 350                                            (unsigned long)blockno,
 351                                            j + (i * arraylen));
 352                                 return BEFS_OK;
 353                         }
 354                         sum += len;
 355                 }
 356
 357                 brelse(indirblock);
 358         }
 359
 360         /* Only fallthrough is an error */
 361         befs_error(sb, "BeFS: %s failed to find "
 362                    "file block %lu", __func__, (unsigned long)blockno);
 363
 364         befs_debug(sb, "<--- %s ERROR", __func__);
 365         return BEFS_ERR;
 366 }
 367
 368 /*
 369         Finds the block run that starts at file block number blockno
 370         in the file represented by the datastream data, if that
 371         blockno is in the double-indirect region of the datastream.
 372
 373         sb: the superblock
 374         data: the datastream
 375         blockno: the blocknumber to find
 376         run: The found run is passed back through this pointer
 377
 378         Return value is BEFS_OK if the blockrun is found, BEFS_ERR
 379         otherwise.
 380
 381         Algorithm:
 382         The block runs in the double-indirect region are different.
 383         They are always allocated 4 fs blocks at a time, so each
 384         block run maps a constant amount of file data. This means
 385         that we can directly calculate how many block runs into the
 386         double-indirect region we need to go to get to the one that
 387         maps a particular filesystem block.
 388
 389         We do this in two stages. First we calculate which of the
 390         inode addresses in the double-indirect block will point us
 391         to the indirect block that contains the mapping for the data,
 392         then we calculate which of the inode addresses in that
 393         indirect block maps the data block we are after.
 394
 395         Oh, and once we've done that, we actually read in the blocks
 396         that contain the inode addresses we calculated above. Even
 397         though the double-indirect run may be several blocks long,
 398         we can calculate which of those blocks will contain the index
 399         we are after and only read that one. We then follow it to
 400         the indirect block and perform a  similar process to find
 401         the actual block run that maps the data block we are interested
 402         in.
 403
 404         Then we offset the run as in befs_find_brun_array() and we are
 405         done.
 406
 407         2001-11-15 Will Dyson
 408 */
 409 static int
 410 befs_find_brun_dblindirect(struct super_block *sb,
 411                            const befs_data_stream *data,
 412                            befs_blocknr_t blockno,
 413                            befs_block_run * run)
 414 {
 415         int dblindir_indx;
 416         int indir_indx;
 417         int offset;
 418         int dbl_which_block;
 419         int which_block;
 420         int dbl_block_indx;
 421         int block_indx;
 422         off_t dblindir_leftover;
 423         befs_blocknr_t blockno_at_run_start;
 424         struct buffer_head *dbl_indir_block;
 425         struct buffer_head *indir_block;
 426         befs_block_run indir_run;
 427         befs_disk_inode_addr *iaddr_array;
 428
 429         befs_blocknr_t indir_start_blk =
 430             data->max_indirect_range >> BEFS_SB(sb)->block_shift;
 431
 432         off_t dbl_indir_off = blockno - indir_start_blk;
 433
 434         /* number of data blocks mapped by each of the iaddrs in
 435          * the indirect block pointed to by the double indirect block
 436          */
 437         size_t iblklen = BEFS_DBLINDIR_BRUN_LEN;
 438
 439         /* number of data blocks mapped by each of the iaddrs in
 440          * the double indirect block
 441          */
 442         size_t diblklen = iblklen * befs_iaddrs_per_block(sb)
 443             * BEFS_DBLINDIR_BRUN_LEN;
 444
 445         befs_debug(sb, "---> %s find %lu", __func__, (unsigned long)blockno);
 446
 447         /* First, discover which of the double_indir->indir blocks
 448          * contains pos. Then figure out how much of pos that
 449          * accounted for. Then discover which of the iaddrs in
 450          * the indirect block contains pos.
 451          */
 452
 453         dblindir_indx = dbl_indir_off / diblklen;
 454         dblindir_leftover = dbl_indir_off % diblklen;
 455         indir_indx = dblindir_leftover / diblklen;
 456
 457         /* Read double indirect block */
 458         dbl_which_block = dblindir_indx / befs_iaddrs_per_block(sb);
 459         if (dbl_which_block > data->double_indirect.len) {
 460                 befs_error(sb, "The double-indirect index calculated by "
 461                            "%s, %d, is outside the range "
 462                            "of the double-indirect block", __func__,
 463                            dblindir_indx);
 464                 return BEFS_ERR;
 465         }
 466
 467         dbl_indir_block =
 468             sb_bread(sb, iaddr2blockno(sb, &data->double_indirect) +
 469                                         dbl_which_block);
 470         if (dbl_indir_block == NULL) {
 471                 befs_error(sb, "%s couldn't read the "
 472                            "double-indirect block at blockno %lu", __func__,
 473                            (unsigned long)
 474                            iaddr2blockno(sb, &data->double_indirect) +
 475                            dbl_which_block);
 476                 return BEFS_ERR;
 477         }
 478
 479         dbl_block_indx =
 480             dblindir_indx - (dbl_which_block * befs_iaddrs_per_block(sb));
 481         iaddr_array = (befs_disk_inode_addr *) dbl_indir_block->b_data;
 482         indir_run = fsrun_to_cpu(sb, iaddr_array[dbl_block_indx]);
 483         brelse(dbl_indir_block);
 484
 485         /* Read indirect block */
 486         which_block = indir_indx / befs_iaddrs_per_block(sb);
 487         if (which_block > indir_run.len) {
 488                 befs_error(sb, "The indirect index calculated by "
 489                            "%s, %d, is outside the range "
 490                            "of the indirect block", __func__, indir_indx);
 491                 return BEFS_ERR;
 492         }
 493
 494         indir_block =
 495             sb_bread(sb, iaddr2blockno(sb, &indir_run) + which_block);
 496         if (indir_block == NULL) {
 497                 befs_error(sb, "%s couldn't read the indirect block "
 498                            "at blockno %lu", __func__, (unsigned long)
 499                            iaddr2blockno(sb, &indir_run) + which_block);
 500                 return BEFS_ERR;
 501         }
 502
 503         block_indx = indir_indx - (which_block * befs_iaddrs_per_block(sb));
 504         iaddr_array = (befs_disk_inode_addr *) indir_block->b_data;
 505         *run = fsrun_to_cpu(sb, iaddr_array[block_indx]);
 506         brelse(indir_block);
 507
 508         blockno_at_run_start = indir_start_blk;
 509         blockno_at_run_start += diblklen * dblindir_indx;
 510         blockno_at_run_start += iblklen * indir_indx;
 511         offset = blockno - blockno_at_run_start;
 512
 513         run->start += offset;
 514         run->len -= offset;
 515
 516         befs_debug(sb, "Found file block %lu in double_indirect[%d][%d],"
 517                    " double_indirect_leftover = %lu", (unsigned long)
 518                    blockno, dblindir_indx, indir_indx, dblindir_leftover);
 519
 520         return BEFS_OK;
 521 }