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