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, "---> 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}
1// SPDX-License-Identifier: GPL-2.0
2/*
3 * linux/fs/befs/datastream.c
4 *
5 * Copyright (C) 2001 Will Dyson <will_dyson@pobox.com>
6 *
7 * Based on portions of file.c by Makoto Kato <m_kato@ga2.so-net.ne.jp>
8 *
9 * Many thanks to Dominic Giampaolo, author of "Practical File System
10 * Design with the Be File System", for such a helpful book.
11 *
12 */
13
14#include <linux/kernel.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 const 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 const 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 const 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: datastream 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, const befs_data_stream *ds,
50 befs_off_t pos, uint *off)
51{
52 struct buffer_head *bh;
53 befs_block_run run;
54 befs_blocknr_t block; /* block coresponding to pos */
55
56 befs_debug(sb, "---> %s %llu", __func__, 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 (unsigned long)block);
64 befs_debug(sb, "<--- %s ERROR", __func__);
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 (unsigned long)block);
71 return NULL;
72 }
73
74 befs_debug(sb, "<--- %s read data, starting at %llu", __func__, pos);
75
76 return bh;
77}
78
79/**
80 * befs_fblock2brun - give back block run for fblock
81 * @sb: the superblock
82 * @data: datastream to read from
83 * @fblock: the blocknumber with the file position to find
84 * @run: The found run is passed back through this pointer
85 *
86 * Takes a file position and gives back a brun who's starting block
87 * is block number fblock of the file.
88 *
89 * Returns BEFS_OK or BEFS_ERR.
90 *
91 * Calls specialized functions for each of the three possible
92 * datastream regions.
93 */
94int
95befs_fblock2brun(struct super_block *sb, const befs_data_stream *data,
96 befs_blocknr_t fblock, befs_block_run *run)
97{
98 int err;
99 befs_off_t pos = fblock << BEFS_SB(sb)->block_shift;
100
101 if (pos < data->max_direct_range) {
102 err = befs_find_brun_direct(sb, data, fblock, run);
103
104 } else if (pos < data->max_indirect_range) {
105 err = befs_find_brun_indirect(sb, data, fblock, run);
106
107 } else if (pos < data->max_double_indirect_range) {
108 err = befs_find_brun_dblindirect(sb, data, fblock, run);
109
110 } else {
111 befs_error(sb,
112 "befs_fblock2brun() was asked to find block %lu, "
113 "which is not mapped by the datastream\n",
114 (unsigned long)fblock);
115 err = BEFS_ERR;
116 }
117 return err;
118}
119
120/**
121 * befs_read_lsmylink - read long symlink from datastream.
122 * @sb: Filesystem superblock
123 * @ds: Datastream to read from
124 * @buff: Buffer in which to place long symlink data
125 * @len: Length of the long symlink in bytes
126 *
127 * Returns the number of bytes read
128 */
129size_t
130befs_read_lsymlink(struct super_block *sb, const befs_data_stream *ds,
131 void *buff, befs_off_t len)
132{
133 befs_off_t bytes_read = 0; /* bytes readed */
134 u16 plen;
135 struct buffer_head *bh;
136
137 befs_debug(sb, "---> %s length: %llu", __func__, len);
138
139 while (bytes_read < len) {
140 bh = befs_read_datastream(sb, ds, bytes_read, NULL);
141 if (!bh) {
142 befs_error(sb, "BeFS: Error reading datastream block "
143 "starting from %llu", bytes_read);
144 befs_debug(sb, "<--- %s ERROR", __func__);
145 return bytes_read;
146
147 }
148 plen = ((bytes_read + BEFS_SB(sb)->block_size) < len) ?
149 BEFS_SB(sb)->block_size : len - bytes_read;
150 memcpy(buff + bytes_read, bh->b_data, plen);
151 brelse(bh);
152 bytes_read += plen;
153 }
154
155 befs_debug(sb, "<--- %s read %u bytes", __func__, (unsigned int)
156 bytes_read);
157 return bytes_read;
158}
159
160/**
161 * befs_count_blocks - blocks used by a file
162 * @sb: Filesystem superblock
163 * @ds: Datastream of the file
164 *
165 * Counts the number of fs blocks that the file represented by
166 * inode occupies on the filesystem, counting both regular file
167 * data and filesystem metadata (and eventually attribute data
168 * when we support attributes)
169*/
170
171befs_blocknr_t
172befs_count_blocks(struct super_block *sb, const befs_data_stream *ds)
173{
174 befs_blocknr_t blocks;
175 befs_blocknr_t datablocks; /* File data blocks */
176 befs_blocknr_t metablocks; /* FS metadata blocks */
177 struct befs_sb_info *befs_sb = BEFS_SB(sb);
178
179 befs_debug(sb, "---> %s", __func__);
180
181 datablocks = ds->size >> befs_sb->block_shift;
182 if (ds->size & (befs_sb->block_size - 1))
183 datablocks += 1;
184
185 metablocks = 1; /* Start with 1 block for inode */
186
187 /* Size of indirect block */
188 if (ds->size > ds->max_direct_range)
189 metablocks += ds->indirect.len;
190
191 /*
192 * Double indir block, plus all the indirect blocks it maps.
193 * In the double-indirect range, all block runs of data are
194 * BEFS_DBLINDIR_BRUN_LEN blocks long. Therefore, we know
195 * how many data block runs are in the double-indirect region,
196 * and from that we know how many indirect blocks it takes to
197 * map them. We assume that the indirect blocks are also
198 * BEFS_DBLINDIR_BRUN_LEN blocks long.
199 */
200 if (ds->size > ds->max_indirect_range && ds->max_indirect_range != 0) {
201 uint dbl_bytes;
202 uint dbl_bruns;
203 uint indirblocks;
204
205 dbl_bytes =
206 ds->max_double_indirect_range - ds->max_indirect_range;
207 dbl_bruns =
208 dbl_bytes / (befs_sb->block_size * BEFS_DBLINDIR_BRUN_LEN);
209 indirblocks = dbl_bruns / befs_iaddrs_per_block(sb);
210
211 metablocks += ds->double_indirect.len;
212 metablocks += indirblocks;
213 }
214
215 blocks = datablocks + metablocks;
216 befs_debug(sb, "<--- %s %u blocks", __func__, (unsigned int)blocks);
217
218 return blocks;
219}
220
221/**
222 * befs_find_brun_direct - find a direct block run in the datastream
223 * @sb: the superblock
224 * @data: the datastream
225 * @blockno: the blocknumber to find
226 * @run: The found run is passed back through this pointer
227 *
228 * Finds the block run that starts at file block number blockno
229 * in the file represented by the datastream data, if that
230 * blockno is in the direct region of the datastream.
231 *
232 * Return value is BEFS_OK if the blockrun is found, BEFS_ERR
233 * otherwise.
234 *
235 * Algorithm:
236 * Linear search. Checks each element of array[] to see if it
237 * contains the blockno-th filesystem block. This is necessary
238 * because the block runs map variable amounts of data. Simply
239 * keeps a count of the number of blocks searched so far (sum),
240 * incrementing this by the length of each block run as we come
241 * across it. Adds sum to *count before returning (this is so
242 * you can search multiple arrays that are logicaly one array,
243 * as in the indirect region code).
244 *
245 * When/if blockno is found, if blockno is inside of a block
246 * run as stored on disk, we offset the start and length members
247 * of the block run, so that blockno is the start and len is
248 * still valid (the run ends in the same place).
249 */
250static int
251befs_find_brun_direct(struct super_block *sb, const befs_data_stream *data,
252 befs_blocknr_t blockno, befs_block_run *run)
253{
254 int i;
255 const befs_block_run *array = data->direct;
256 befs_blocknr_t sum;
257
258 befs_debug(sb, "---> %s, find %lu", __func__, (unsigned long)blockno);
259
260 for (i = 0, sum = 0; i < BEFS_NUM_DIRECT_BLOCKS;
261 sum += array[i].len, i++) {
262 if (blockno >= sum && blockno < sum + (array[i].len)) {
263 int offset = blockno - sum;
264
265 run->allocation_group = array[i].allocation_group;
266 run->start = array[i].start + offset;
267 run->len = array[i].len - offset;
268
269 befs_debug(sb, "---> %s, "
270 "found %lu at direct[%d]", __func__,
271 (unsigned long)blockno, i);
272 return BEFS_OK;
273 }
274 }
275
276 befs_error(sb, "%s failed to find file block %lu", __func__,
277 (unsigned long)blockno);
278 befs_debug(sb, "---> %s ERROR", __func__);
279 return BEFS_ERR;
280}
281
282/**
283 * befs_find_brun_indirect - find a block run in the datastream
284 * @sb: the superblock
285 * @data: the datastream
286 * @blockno: the blocknumber to find
287 * @run: The found run is passed back through this pointer
288 *
289 * Finds the block run that starts at file block number blockno
290 * in the file represented by the datastream data, if that
291 * blockno is in the indirect region of the datastream.
292 *
293 * Return value is BEFS_OK if the blockrun is found, BEFS_ERR
294 * otherwise.
295 *
296 * Algorithm:
297 * For each block in the indirect run of the datastream, read
298 * it in and search through it for search_blk.
299 *
300 * XXX:
301 * Really should check to make sure blockno is inside indirect
302 * region.
303 */
304static int
305befs_find_brun_indirect(struct super_block *sb,
306 const befs_data_stream *data,
307 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 = sb_bread(sb, indirblockno + i);
329 if (indirblock == NULL) {
330 befs_error(sb, "---> %s failed to read "
331 "disk block %lu from the indirect brun",
332 __func__, (unsigned long)indirblockno + i);
333 befs_debug(sb, "<--- %s ERROR", __func__);
334 return BEFS_ERR;
335 }
336
337 array = (befs_disk_block_run *) indirblock->b_data;
338
339 for (j = 0; j < arraylen; ++j) {
340 int len = fs16_to_cpu(sb, array[j].len);
341
342 if (search_blk >= sum && search_blk < sum + len) {
343 int offset = search_blk - sum;
344 run->allocation_group =
345 fs32_to_cpu(sb, array[j].allocation_group);
346 run->start =
347 fs16_to_cpu(sb, array[j].start) + offset;
348 run->len =
349 fs16_to_cpu(sb, array[j].len) - offset;
350
351 brelse(indirblock);
352 befs_debug(sb,
353 "<--- %s found file block "
354 "%lu at indirect[%d]", __func__,
355 (unsigned long)blockno,
356 j + (i * arraylen));
357 return BEFS_OK;
358 }
359 sum += len;
360 }
361
362 brelse(indirblock);
363 }
364
365 /* Only fallthrough is an error */
366 befs_error(sb, "BeFS: %s failed to find "
367 "file block %lu", __func__, (unsigned long)blockno);
368
369 befs_debug(sb, "<--- %s ERROR", __func__);
370 return BEFS_ERR;
371}
372
373/**
374 * befs_find_brun_dblindirect - find a block run in the datastream
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 * Finds the block run that starts at file block number blockno
381 * in the file represented by the datastream data, if that
382 * blockno is in the double-indirect region of the datastream.
383 *
384 * Return value is BEFS_OK if the blockrun is found, BEFS_ERR
385 * otherwise.
386 *
387 * Algorithm:
388 * The block runs in the double-indirect region are different.
389 * They are always allocated 4 fs blocks at a time, so each
390 * block run maps a constant amount of file data. This means
391 * that we can directly calculate how many block runs into the
392 * double-indirect region we need to go to get to the one that
393 * maps a particular filesystem block.
394 *
395 * We do this in two stages. First we calculate which of the
396 * inode addresses in the double-indirect block will point us
397 * to the indirect block that contains the mapping for the data,
398 * then we calculate which of the inode addresses in that
399 * indirect block maps the data block we are after.
400 *
401 * Oh, and once we've done that, we actually read in the blocks
402 * that contain the inode addresses we calculated above. Even
403 * though the double-indirect run may be several blocks long,
404 * we can calculate which of those blocks will contain the index
405 * we are after and only read that one. We then follow it to
406 * the indirect block and perform a similar process to find
407 * the actual block run that maps the data block we are interested
408 * in.
409 *
410 * Then we offset the run as in befs_find_brun_array() and we are
411 * done.
412 */
413static int
414befs_find_brun_dblindirect(struct super_block *sb,
415 const befs_data_stream *data,
416 befs_blocknr_t blockno,
417 befs_block_run *run)
418{
419 int dblindir_indx;
420 int indir_indx;
421 int offset;
422 int dbl_which_block;
423 int which_block;
424 int dbl_block_indx;
425 int block_indx;
426 off_t dblindir_leftover;
427 befs_blocknr_t blockno_at_run_start;
428 struct buffer_head *dbl_indir_block;
429 struct buffer_head *indir_block;
430 befs_block_run indir_run;
431 befs_disk_inode_addr *iaddr_array;
432
433 befs_blocknr_t indir_start_blk =
434 data->max_indirect_range >> BEFS_SB(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 sb_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 return BEFS_ERR;
481 }
482
483 dbl_block_indx =
484 dblindir_indx - (dbl_which_block * befs_iaddrs_per_block(sb));
485 iaddr_array = (befs_disk_inode_addr *) dbl_indir_block->b_data;
486 indir_run = fsrun_to_cpu(sb, iaddr_array[dbl_block_indx]);
487 brelse(dbl_indir_block);
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 "%s, %d, is outside the range "
494 "of the indirect block", __func__, indir_indx);
495 return BEFS_ERR;
496 }
497
498 indir_block =
499 sb_bread(sb, iaddr2blockno(sb, &indir_run) + which_block);
500 if (indir_block == NULL) {
501 befs_error(sb, "%s couldn't read the indirect block "
502 "at blockno %lu", __func__, (unsigned long)
503 iaddr2blockno(sb, &indir_run) + which_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
512 blockno_at_run_start = indir_start_blk;
513 blockno_at_run_start += diblklen * dblindir_indx;
514 blockno_at_run_start += iblklen * indir_indx;
515 offset = blockno - blockno_at_run_start;
516
517 run->start += offset;
518 run->len -= offset;
519
520 befs_debug(sb, "Found file block %lu in double_indirect[%d][%d],"
521 " double_indirect_leftover = %lu", (unsigned long)
522 blockno, dblindir_indx, indir_indx, dblindir_leftover);
523
524 return BEFS_OK;
525}