Loading...
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, "---> %s %llu", __func__, 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 (unsigned long)block);
63 befs_debug(sb, "<--- %s ERROR", __func__);
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 (unsigned long)block);
70 return NULL;
71 }
72
73 befs_debug(sb, "<--- %s read data, starting at %llu", __func__, pos);
74
75 return bh;
76}
77
78/*
79 * Takes a file position and gives back a brun who's starting block
80 * is block number fblock of the file.
81 *
82 * Returns BEFS_OK or BEFS_ERR.
83 *
84 * Calls specialized functions for each of the three possible
85 * datastream regions.
86 *
87 * 2001-11-15 Will Dyson
88 */
89int
90befs_fblock2brun(struct super_block *sb, befs_data_stream * data,
91 befs_blocknr_t fblock, befs_block_run * run)
92{
93 int err;
94 befs_off_t pos = fblock << BEFS_SB(sb)->block_shift;
95
96 if (pos < data->max_direct_range) {
97 err = befs_find_brun_direct(sb, data, fblock, run);
98
99 } else if (pos < data->max_indirect_range) {
100 err = befs_find_brun_indirect(sb, data, fblock, run);
101
102 } else if (pos < data->max_double_indirect_range) {
103 err = befs_find_brun_dblindirect(sb, data, fblock, run);
104
105 } else {
106 befs_error(sb,
107 "befs_fblock2brun() was asked to find block %lu, "
108 "which is not mapped by the datastream\n",
109 (unsigned long)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 * @buff: 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, "---> %s length: %llu", __func__, 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 %llu", bytes_read);
138 befs_debug(sb, "<--- %s ERROR", __func__);
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, "<--- %s read %u bytes", __func__, (unsigned int)
150 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 struct befs_sb_info *befs_sb = BEFS_SB(sb);
172
173 befs_debug(sb, "---> %s", __func__);
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, "<--- %s %u blocks", __func__, (unsigned int)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, "---> %s, find %lu", __func__, (unsigned long)blockno);
256
257 if (blockno > max_block) {
258 befs_error(sb, "%s passed block outside of direct region",
259 __func__);
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, "---> %s, "
272 "found %lu at direct[%d]", __func__,
273 (unsigned long)blockno, i);
274 return BEFS_OK;
275 }
276 }
277
278 befs_debug(sb, "---> %s ERROR", __func__);
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*/
305static int
306befs_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_disk_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, "---> %s, find %lu", __func__, (unsigned long)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, "---> %s failed to read "
331 "disk block %lu from the indirect brun",
332 __func__, (unsigned long)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 "<--- %s found file block "
353 "%lu at indirect[%d]", __func__,
354 (unsigned long)blockno,
355 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: %s failed to find "
366 "file block %lu", __func__, (unsigned long)blockno);
367
368 befs_debug(sb, "<--- %s ERROR", __func__);
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*/
413static int
414befs_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_disk_inode_addr *iaddr_array = NULL;
431 struct 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, "---> %s find %lu", __func__, (unsigned long)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 "%s, %d, is outside the range "
466 "of the double-indirect block", __func__,
467 dblindir_indx);
468 return BEFS_ERR;
469 }
470
471 dbl_indir_block =
472 befs_bread(sb, iaddr2blockno(sb, &data->double_indirect) +
473 dbl_which_block);
474 if (dbl_indir_block == NULL) {
475 befs_error(sb, "%s couldn't read the "
476 "double-indirect block at blockno %lu", __func__,
477 (unsigned long)
478 iaddr2blockno(sb, &data->double_indirect) +
479 dbl_which_block);
480 brelse(dbl_indir_block);
481 return BEFS_ERR;
482 }
483
484 dbl_block_indx =
485 dblindir_indx - (dbl_which_block * befs_iaddrs_per_block(sb));
486 iaddr_array = (befs_disk_inode_addr *) dbl_indir_block->b_data;
487 indir_run = fsrun_to_cpu(sb, iaddr_array[dbl_block_indx]);
488 brelse(dbl_indir_block);
489 iaddr_array = NULL;
490
491 /* Read indirect block */
492 which_block = indir_indx / befs_iaddrs_per_block(sb);
493 if (which_block > indir_run.len) {
494 befs_error(sb, "The indirect index calculated by "
495 "%s, %d, is outside the range "
496 "of the indirect block", __func__, indir_indx);
497 return BEFS_ERR;
498 }
499
500 indir_block =
501 befs_bread(sb, iaddr2blockno(sb, &indir_run) + which_block);
502 if (indir_block == NULL) {
503 befs_error(sb, "%s couldn't read the indirect block "
504 "at blockno %lu", __func__, (unsigned long)
505 iaddr2blockno(sb, &indir_run) + which_block);
506 brelse(indir_block);
507 return BEFS_ERR;
508 }
509
510 block_indx = indir_indx - (which_block * befs_iaddrs_per_block(sb));
511 iaddr_array = (befs_disk_inode_addr *) indir_block->b_data;
512 *run = fsrun_to_cpu(sb, iaddr_array[block_indx]);
513 brelse(indir_block);
514 iaddr_array = NULL;
515
516 blockno_at_run_start = indir_start_blk;
517 blockno_at_run_start += diblklen * dblindir_indx;
518 blockno_at_run_start += iblklen * indir_indx;
519 offset = blockno - blockno_at_run_start;
520
521 run->start += offset;
522 run->len -= offset;
523
524 befs_debug(sb, "Found file block %lu in double_indirect[%d][%d],"
525 " double_indirect_leftover = %lu", (unsigned long)
526 blockno, dblindir_indx, indir_indx, dblindir_leftover);
527
528 return BEFS_OK;
529}
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 const 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 const 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 const 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: datastream 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, const befs_data_stream *ds,
49 befs_off_t pos, uint *off)
50{
51 struct buffer_head *bh;
52 befs_block_run run;
53 befs_blocknr_t block; /* block coresponding to pos */
54
55 befs_debug(sb, "---> %s %llu", __func__, 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 (unsigned long)block);
63 befs_debug(sb, "<--- %s ERROR", __func__);
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 (unsigned long)block);
70 return NULL;
71 }
72
73 befs_debug(sb, "<--- %s read data, starting at %llu", __func__, pos);
74
75 return bh;
76}
77
78/**
79 * befs_fblock2brun - give back block run for fblock
80 * @sb: the superblock
81 * @data: datastream to read from
82 * @fblock: the blocknumber with the file position to find
83 * @run: The found run is passed back through this pointer
84 *
85 * Takes a file position and gives back a brun who's starting block
86 * is block number fblock of the file.
87 *
88 * Returns BEFS_OK or BEFS_ERR.
89 *
90 * Calls specialized functions for each of the three possible
91 * datastream regions.
92 */
93int
94befs_fblock2brun(struct super_block *sb, const befs_data_stream *data,
95 befs_blocknr_t fblock, befs_block_run *run)
96{
97 int err;
98 befs_off_t pos = fblock << BEFS_SB(sb)->block_shift;
99
100 if (pos < data->max_direct_range) {
101 err = befs_find_brun_direct(sb, data, fblock, run);
102
103 } else if (pos < data->max_indirect_range) {
104 err = befs_find_brun_indirect(sb, data, fblock, run);
105
106 } else if (pos < data->max_double_indirect_range) {
107 err = befs_find_brun_dblindirect(sb, data, fblock, run);
108
109 } else {
110 befs_error(sb,
111 "befs_fblock2brun() was asked to find block %lu, "
112 "which is not mapped by the datastream\n",
113 (unsigned long)fblock);
114 err = BEFS_ERR;
115 }
116 return err;
117}
118
119/**
120 * befs_read_lsmylink - read long symlink from datastream.
121 * @sb: Filesystem superblock
122 * @ds: Datastream to read from
123 * @buff: Buffer in which to place long symlink data
124 * @len: Length of the long symlink in bytes
125 *
126 * Returns the number of bytes read
127 */
128size_t
129befs_read_lsymlink(struct super_block *sb, const befs_data_stream *ds,
130 void *buff, befs_off_t len)
131{
132 befs_off_t bytes_read = 0; /* bytes readed */
133 u16 plen;
134 struct buffer_head *bh;
135
136 befs_debug(sb, "---> %s length: %llu", __func__, len);
137
138 while (bytes_read < len) {
139 bh = befs_read_datastream(sb, ds, bytes_read, NULL);
140 if (!bh) {
141 befs_error(sb, "BeFS: Error reading datastream block "
142 "starting from %llu", bytes_read);
143 befs_debug(sb, "<--- %s ERROR", __func__);
144 return bytes_read;
145
146 }
147 plen = ((bytes_read + BEFS_SB(sb)->block_size) < len) ?
148 BEFS_SB(sb)->block_size : len - bytes_read;
149 memcpy(buff + bytes_read, bh->b_data, plen);
150 brelse(bh);
151 bytes_read += plen;
152 }
153
154 befs_debug(sb, "<--- %s read %u bytes", __func__, (unsigned int)
155 bytes_read);
156 return bytes_read;
157}
158
159/**
160 * befs_count_blocks - blocks used by a file
161 * @sb: Filesystem superblock
162 * @ds: Datastream of the file
163 *
164 * Counts the number of fs blocks that the file represented by
165 * inode occupies on the filesystem, counting both regular file
166 * data and filesystem metadata (and eventually attribute data
167 * when we support attributes)
168*/
169
170befs_blocknr_t
171befs_count_blocks(struct super_block *sb, const befs_data_stream *ds)
172{
173 befs_blocknr_t blocks;
174 befs_blocknr_t datablocks; /* File data blocks */
175 befs_blocknr_t metablocks; /* FS metadata blocks */
176 struct befs_sb_info *befs_sb = BEFS_SB(sb);
177
178 befs_debug(sb, "---> %s", __func__);
179
180 datablocks = ds->size >> befs_sb->block_shift;
181 if (ds->size & (befs_sb->block_size - 1))
182 datablocks += 1;
183
184 metablocks = 1; /* Start with 1 block for inode */
185
186 /* Size of indirect block */
187 if (ds->size > ds->max_direct_range)
188 metablocks += ds->indirect.len;
189
190 /*
191 * Double indir block, plus all the indirect blocks it maps.
192 * In the double-indirect range, all block runs of data are
193 * BEFS_DBLINDIR_BRUN_LEN blocks long. Therefore, we know
194 * how many data block runs are in the double-indirect region,
195 * and from that we know how many indirect blocks it takes to
196 * map them. We assume that the indirect blocks are also
197 * BEFS_DBLINDIR_BRUN_LEN blocks long.
198 */
199 if (ds->size > ds->max_indirect_range && ds->max_indirect_range != 0) {
200 uint dbl_bytes;
201 uint dbl_bruns;
202 uint indirblocks;
203
204 dbl_bytes =
205 ds->max_double_indirect_range - ds->max_indirect_range;
206 dbl_bruns =
207 dbl_bytes / (befs_sb->block_size * BEFS_DBLINDIR_BRUN_LEN);
208 indirblocks = dbl_bruns / befs_iaddrs_per_block(sb);
209
210 metablocks += ds->double_indirect.len;
211 metablocks += indirblocks;
212 }
213
214 blocks = datablocks + metablocks;
215 befs_debug(sb, "<--- %s %u blocks", __func__, (unsigned int)blocks);
216
217 return blocks;
218}
219
220/**
221 * befs_find_brun_direct - find a direct block run in the datastream
222 * @sb: the superblock
223 * @data: the datastream
224 * @blockno: the blocknumber to find
225 * @run: The found run is passed back through this pointer
226 *
227 * Finds the block run that starts at file block number blockno
228 * in the file represented by the datastream data, if that
229 * blockno is in the direct region of the datastream.
230 *
231 * Return value is BEFS_OK if the blockrun is found, BEFS_ERR
232 * otherwise.
233 *
234 * Algorithm:
235 * Linear search. Checks each element of array[] to see if it
236 * contains the blockno-th filesystem block. This is necessary
237 * because the block runs map variable amounts of data. Simply
238 * keeps a count of the number of blocks searched so far (sum),
239 * incrementing this by the length of each block run as we come
240 * across it. Adds sum to *count before returning (this is so
241 * you can search multiple arrays that are logicaly one array,
242 * as in the indirect region code).
243 *
244 * When/if blockno is found, if blockno is inside of a block
245 * run as stored on disk, we offset the start and length members
246 * of the block run, so that blockno is the start and len is
247 * still valid (the run ends in the same place).
248 */
249static int
250befs_find_brun_direct(struct super_block *sb, const befs_data_stream *data,
251 befs_blocknr_t blockno, befs_block_run *run)
252{
253 int i;
254 const befs_block_run *array = data->direct;
255 befs_blocknr_t sum;
256
257 befs_debug(sb, "---> %s, find %lu", __func__, (unsigned long)blockno);
258
259 for (i = 0, sum = 0; i < BEFS_NUM_DIRECT_BLOCKS;
260 sum += array[i].len, i++) {
261 if (blockno >= sum && blockno < sum + (array[i].len)) {
262 int offset = blockno - sum;
263
264 run->allocation_group = array[i].allocation_group;
265 run->start = array[i].start + offset;
266 run->len = array[i].len - offset;
267
268 befs_debug(sb, "---> %s, "
269 "found %lu at direct[%d]", __func__,
270 (unsigned long)blockno, i);
271 return BEFS_OK;
272 }
273 }
274
275 befs_error(sb, "%s failed to find file block %lu", __func__,
276 (unsigned long)blockno);
277 befs_debug(sb, "---> %s ERROR", __func__);
278 return BEFS_ERR;
279}
280
281/**
282 * befs_find_brun_indirect - find a block run in the datastream
283 * @sb: the superblock
284 * @data: the datastream
285 * @blockno: the blocknumber to find
286 * @run: The found run is passed back through this pointer
287 *
288 * Finds the block run that starts at file block number blockno
289 * in the file represented by the datastream data, if that
290 * blockno is in the indirect region of the datastream.
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 */
303static int
304befs_find_brun_indirect(struct super_block *sb,
305 const befs_data_stream *data,
306 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, "---> %s, find %lu", __func__, (unsigned long)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 = sb_bread(sb, indirblockno + i);
328 if (indirblock == NULL) {
329 befs_error(sb, "---> %s failed to read "
330 "disk block %lu from the indirect brun",
331 __func__, (unsigned long)indirblockno + i);
332 befs_debug(sb, "<--- %s ERROR", __func__);
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 "<--- %s found file block "
353 "%lu at indirect[%d]", __func__,
354 (unsigned long)blockno,
355 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: %s failed to find "
366 "file block %lu", __func__, (unsigned long)blockno);
367
368 befs_debug(sb, "<--- %s ERROR", __func__);
369 return BEFS_ERR;
370}
371
372/**
373 * befs_find_brun_dblindirect - find a block run in the datastream
374 * @sb: the superblock
375 * @data: the datastream
376 * @blockno: the blocknumber to find
377 * @run: The found run is passed back through this pointer
378 *
379 * Finds the block run that starts at file block number blockno
380 * in the file represented by the datastream data, if that
381 * blockno is in the double-indirect region of the datastream.
382 *
383 * Return value is BEFS_OK if the blockrun is found, BEFS_ERR
384 * otherwise.
385 *
386 * Algorithm:
387 * The block runs in the double-indirect region are different.
388 * They are always allocated 4 fs blocks at a time, so each
389 * block run maps a constant amount of file data. This means
390 * that we can directly calculate how many block runs into the
391 * double-indirect region we need to go to get to the one that
392 * maps a particular filesystem block.
393 *
394 * We do this in two stages. First we calculate which of the
395 * inode addresses in the double-indirect block will point us
396 * to the indirect block that contains the mapping for the data,
397 * then we calculate which of the inode addresses in that
398 * indirect block maps the data block we are after.
399 *
400 * Oh, and once we've done that, we actually read in the blocks
401 * that contain the inode addresses we calculated above. Even
402 * though the double-indirect run may be several blocks long,
403 * we can calculate which of those blocks will contain the index
404 * we are after and only read that one. We then follow it to
405 * the indirect block and perform a similar process to find
406 * the actual block run that maps the data block we are interested
407 * in.
408 *
409 * Then we offset the run as in befs_find_brun_array() and we are
410 * done.
411 */
412static int
413befs_find_brun_dblindirect(struct super_block *sb,
414 const befs_data_stream *data,
415 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_disk_inode_addr *iaddr_array;
431
432 befs_blocknr_t indir_start_blk =
433 data->max_indirect_range >> BEFS_SB(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, "---> %s find %lu", __func__, (unsigned long)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 "%s, %d, is outside the range "
465 "of the double-indirect block", __func__,
466 dblindir_indx);
467 return BEFS_ERR;
468 }
469
470 dbl_indir_block =
471 sb_bread(sb, iaddr2blockno(sb, &data->double_indirect) +
472 dbl_which_block);
473 if (dbl_indir_block == NULL) {
474 befs_error(sb, "%s couldn't read the "
475 "double-indirect block at blockno %lu", __func__,
476 (unsigned long)
477 iaddr2blockno(sb, &data->double_indirect) +
478 dbl_which_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
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 "%s, %d, is outside the range "
493 "of the indirect block", __func__, indir_indx);
494 return BEFS_ERR;
495 }
496
497 indir_block =
498 sb_bread(sb, iaddr2blockno(sb, &indir_run) + which_block);
499 if (indir_block == NULL) {
500 befs_error(sb, "%s couldn't read the indirect block "
501 "at blockno %lu", __func__, (unsigned long)
502 iaddr2blockno(sb, &indir_run) + which_block);
503 return BEFS_ERR;
504 }
505
506 block_indx = indir_indx - (which_block * befs_iaddrs_per_block(sb));
507 iaddr_array = (befs_disk_inode_addr *) indir_block->b_data;
508 *run = fsrun_to_cpu(sb, iaddr_array[block_indx]);
509 brelse(indir_block);
510
511 blockno_at_run_start = indir_start_blk;
512 blockno_at_run_start += diblklen * dblindir_indx;
513 blockno_at_run_start += iblklen * indir_indx;
514 offset = blockno - blockno_at_run_start;
515
516 run->start += offset;
517 run->len -= offset;
518
519 befs_debug(sb, "Found file block %lu in double_indirect[%d][%d],"
520 " double_indirect_leftover = %lu", (unsigned long)
521 blockno, dblindir_indx, indir_indx, dblindir_leftover);
522
523 return BEFS_OK;
524}