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/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
  22const befs_inode_addr BAD_IADDR = { 0, 0, 0 };
  23
  24static int befs_find_brun_direct(struct super_block *sb,
  25                                 befs_data_stream * data,
  26                                 befs_blocknr_t blockno, befs_block_run * run);
  27
  28static 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
  33static 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 */
  48struct buffer_head *
  49befs_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 */
  91int
  92befs_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 */
 125size_t
 126befs_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
 165befs_blocknr_t
 166befs_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 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*/
 245static int
 246befs_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*/
 304static int
 305befs_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*/
 412static int
 413befs_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}
 528
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.