linux/fs/befs/datastream.c
<<
>>
Prefs
   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
  21const befs_inode_addr BAD_IADDR = { 0, 0, 0 };
  22
  23static int befs_find_brun_direct(struct super_block *sb,
  24                                 befs_data_stream * data,
  25                                 befs_blocknr_t blockno, befs_block_run * run);
  26
  27static 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
  32static 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 */
  47struct buffer_head *
  48befs_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 */
  90int
  91befs_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 */
 124size_t
 125befs_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
 164befs_blocknr_t
 165befs_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*/
 244static int
 245befs_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*/
 303static int
 304befs_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*/
 411static int
 412befs_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}
 527
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.