2 * linux/fs/befs/datastream.c
4 * Copyright (C) 2001 Will Dyson <will_dyson@pobox.com>
6 * Based on portions of file.c by Makoto Kato <m_kato@ga2.so-net.ne.jp>
8 * Many thanks to Dominic Giampaolo, author of "Practical File System
9 * Design with the Be File System", for such a helpful book.
13 #include <linux/kernel.h>
14 #include <linux/buffer_head.h>
15 #include <linux/string.h>
18 #include "datastream.h"
21 const befs_inode_addr BAD_IADDR = { 0, 0, 0 };
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);
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);
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);
38 * befs_read_datastream - get buffer_head containing data, starting from pos.
39 * @sb: Filesystem superblock
40 * @ds: datastream to find data with
42 * @off: offset of data in buffer_head->b_data
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.
48 befs_read_datastream(struct super_block *sb, const befs_data_stream *ds,
49 befs_off_t pos, uint * off)
51 struct buffer_head *bh;
53 befs_blocknr_t block; /* block coresponding to pos */
55 befs_debug(sb, "---> %s %llu", __func__, pos);
56 block = pos >> BEFS_SB(sb)->block_shift;
58 *off = pos - (block << BEFS_SB(sb)->block_shift);
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__);
66 bh = befs_bread_iaddr(sb, run);
68 befs_error(sb, "BeFS: Error reading block %lu from datastream",
69 (unsigned long)block);
73 befs_debug(sb, "<--- %s read data, starting at %llu", __func__, pos);
79 * Takes a file position and gives back a brun who's starting block
80 * is block number fblock of the file.
82 * Returns BEFS_OK or BEFS_ERR.
84 * Calls specialized functions for each of the three possible
87 * 2001-11-15 Will Dyson
90 befs_fblock2brun(struct super_block *sb, const befs_data_stream *data,
91 befs_blocknr_t fblock, befs_block_run * run)
94 befs_off_t pos = fblock << BEFS_SB(sb)->block_shift;
96 if (pos < data->max_direct_range) {
97 err = befs_find_brun_direct(sb, data, fblock, run);
99 } else if (pos < data->max_indirect_range) {
100 err = befs_find_brun_indirect(sb, data, fblock, run);
102 } else if (pos < data->max_double_indirect_range) {
103 err = befs_find_brun_dblindirect(sb, data, fblock, run);
107 "befs_fblock2brun() was asked to find block %lu, "
108 "which is not mapped by the datastream\n",
109 (unsigned long)fblock);
116 * befs_read_lsmylink - read long symlink from datastream.
117 * @sb: Filesystem superblock
118 * @ds: Datastream to read from
119 * @buff: Buffer in which to place long symlink data
120 * @len: Length of the long symlink in bytes
122 * Returns the number of bytes read
125 befs_read_lsymlink(struct super_block *sb, const befs_data_stream *ds,
126 void *buff, befs_off_t len)
128 befs_off_t bytes_read = 0; /* bytes readed */
130 struct buffer_head *bh;
131 befs_debug(sb, "---> %s length: %llu", __func__, len);
133 while (bytes_read < len) {
134 bh = befs_read_datastream(sb, ds, bytes_read, NULL);
136 befs_error(sb, "BeFS: Error reading datastream block "
137 "starting from %llu", bytes_read);
138 befs_debug(sb, "<--- %s ERROR", __func__);
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);
149 befs_debug(sb, "<--- %s read %u bytes", __func__, (unsigned int)
155 * befs_count_blocks - blocks used by a file
156 * @sb: Filesystem superblock
157 * @ds: Datastream of the file
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)
166 befs_count_blocks(struct super_block *sb, const befs_data_stream *ds)
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);
173 befs_debug(sb, "---> %s", __func__);
175 datablocks = ds->size >> befs_sb->block_shift;
176 if (ds->size & (befs_sb->block_size - 1))
179 metablocks = 1; /* Start with 1 block for inode */
181 /* Size of indirect block */
182 if (ds->size > ds->max_direct_range)
183 metablocks += ds->indirect.len;
186 Double indir block, plus all the indirect blocks it maps.
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.
194 if (ds->size > ds->max_indirect_range && ds->max_indirect_range != 0) {
200 ds->max_double_indirect_range - ds->max_indirect_range;
202 dbl_bytes / (befs_sb->block_size * BEFS_DBLINDIR_BRUN_LEN);
203 indirblocks = dbl_bruns / befs_iaddrs_per_block(sb);
205 metablocks += ds->double_indirect.len;
206 metablocks += indirblocks;
209 blocks = datablocks + metablocks;
210 befs_debug(sb, "<--- %s %u blocks", __func__, (unsigned int)blocks);
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.
222 blockno: the blocknumber to find
223 run: The found run is passed back through this pointer
225 Return value is BEFS_OK if the blockrun is found, BEFS_ERR
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).
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).
243 2001-11-15 Will Dyson
246 befs_find_brun_direct(struct super_block *sb, const befs_data_stream *data,
247 befs_blocknr_t blockno, befs_block_run * run)
250 const befs_block_run *array = data->direct;
253 befs_debug(sb, "---> %s, find %lu", __func__, (unsigned long)blockno);
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;
263 befs_debug(sb, "---> %s, "
264 "found %lu at direct[%d]", __func__,
265 (unsigned long)blockno, i);
270 befs_error(sb, "%s failed to find file block %lu", __func__,
271 (unsigned long)blockno);
272 befs_debug(sb, "---> %s ERROR", __func__);
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.
283 blockno: the blocknumber to find
284 run: The found run is passed back through this pointer
286 Return value is BEFS_OK if the blockrun is found, BEFS_ERR
290 For each block in the indirect run of the datastream, read
291 it in and search through it for search_blk.
294 Really should check to make sure blockno is inside indirect
297 2001-11-15 Will Dyson
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)
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;
312 befs_block_run indirect = data->indirect;
313 befs_blocknr_t indirblockno = iaddr2blockno(sb, &indirect);
314 int arraylen = befs_iaddrs_per_block(sb);
316 befs_debug(sb, "---> %s, find %lu", __func__, (unsigned long)blockno);
318 indir_start_blk = data->max_direct_range >> BEFS_SB(sb)->block_shift;
319 search_blk = blockno - indir_start_blk;
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__);
332 array = (befs_disk_block_run *) indirblock->b_data;
334 for (j = 0; j < arraylen; ++j) {
335 int len = fs16_to_cpu(sb, array[j].len);
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);
342 fs16_to_cpu(sb, array[j].start) + offset;
344 fs16_to_cpu(sb, array[j].len) - offset;
348 "<--- %s found file block "
349 "%lu at indirect[%d]", __func__,
350 (unsigned long)blockno,
360 /* Only fallthrough is an error */
361 befs_error(sb, "BeFS: %s failed to find "
362 "file block %lu", __func__, (unsigned long)blockno);
364 befs_debug(sb, "<--- %s ERROR", __func__);
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.
375 blockno: the blocknumber to find
376 run: The found run is passed back through this pointer
378 Return value is BEFS_OK if the blockrun is found, BEFS_ERR
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.
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.
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
404 Then we offset the run as in befs_find_brun_array() and we are
407 2001-11-15 Will Dyson
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)
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;
429 befs_blocknr_t indir_start_blk =
430 data->max_indirect_range >> BEFS_SB(sb)->block_shift;
432 off_t dbl_indir_off = blockno - indir_start_blk;
434 /* number of data blocks mapped by each of the iaddrs in
435 * the indirect block pointed to by the double indirect block
437 size_t iblklen = BEFS_DBLINDIR_BRUN_LEN;
439 /* number of data blocks mapped by each of the iaddrs in
440 * the double indirect block
442 size_t diblklen = iblklen * befs_iaddrs_per_block(sb)
443 * BEFS_DBLINDIR_BRUN_LEN;
445 befs_debug(sb, "---> %s find %lu", __func__, (unsigned long)blockno);
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.
453 dblindir_indx = dbl_indir_off / diblklen;
454 dblindir_leftover = dbl_indir_off % diblklen;
455 indir_indx = dblindir_leftover / diblklen;
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__,
468 sb_bread(sb, iaddr2blockno(sb, &data->double_indirect) +
470 if (dbl_indir_block == NULL) {
471 befs_error(sb, "%s couldn't read the "
472 "double-indirect block at blockno %lu", __func__,
474 iaddr2blockno(sb, &data->double_indirect) +
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);
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);
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);
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]);
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;
513 run->start += offset;
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);