Root/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
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

Archive Download this file



interactive