blob: e3287d0d1a58815020044ef9f47383eec92cddcb [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * linux/fs/befs/datastream.c
3 *
4 * Copyright (C) 2001 Will Dyson <will_dyson@pobox.com>
5 *
6 * Based on portions of file.c by Makoto Kato <m_kato@ga2.so-net.ne.jp>
7 *
8 * Many thanks to Dominic Giampaolo, author of "Practical File System
9 * Design with the Be File System", for such a helpful book.
10 *
11 */
12
13#include <linux/kernel.h>
14#include <linux/slab.h>
15#include <linux/buffer_head.h>
16#include <linux/string.h>
17
18#include "befs.h"
19#include "datastream.h"
20#include "io.h"
Linus Torvalds1da177e2005-04-16 15:20:36 -070021
22const befs_inode_addr BAD_IADDR = { 0, 0, 0 };
23
24static int befs_find_brun_direct(struct super_block *sb,
25 befs_data_stream * data,
26 befs_blocknr_t blockno, befs_block_run * run);
27
28static int befs_find_brun_indirect(struct super_block *sb,
29 befs_data_stream * data,
30 befs_blocknr_t blockno,
31 befs_block_run * run);
32
33static int befs_find_brun_dblindirect(struct super_block *sb,
34 befs_data_stream * data,
35 befs_blocknr_t blockno,
36 befs_block_run * run);
37
38/**
39 * befs_read_datastream - get buffer_head containing data, starting from pos.
40 * @sb: Filesystem superblock
41 * @ds: datastrem to find data with
42 * @pos: start of data
43 * @off: offset of data in buffer_head->b_data
44 *
45 * Returns pointer to buffer_head containing data starting with offset @off,
46 * if you don't need to know offset just set @off = NULL.
47 */
48struct buffer_head *
49befs_read_datastream(struct super_block *sb, befs_data_stream * ds,
50 befs_off_t pos, uint * off)
51{
52 struct buffer_head *bh = NULL;
53 befs_block_run run;
54 befs_blocknr_t block; /* block coresponding to pos */
55
56 befs_debug(sb, "---> befs_read_datastream() %Lu", pos);
57 block = pos >> BEFS_SB(sb)->block_shift;
58 if (off)
59 *off = pos - (block << BEFS_SB(sb)->block_shift);
60
61 if (befs_fblock2brun(sb, ds, block, &run) != BEFS_OK) {
62 befs_error(sb, "BeFS: Error finding disk addr of block %lu",
63 block);
64 befs_debug(sb, "<--- befs_read_datastream() ERROR");
65 return NULL;
66 }
67 bh = befs_bread_iaddr(sb, run);
68 if (!bh) {
69 befs_error(sb, "BeFS: Error reading block %lu from datastream",
70 block);
71 return NULL;
72 }
73
74 befs_debug(sb, "<--- befs_read_datastream() read data, starting at %Lu",
75 pos);
76
77 return bh;
78}
79
80/*
81 * Takes a file position and gives back a brun who's starting block
82 * is block number fblock of the file.
83 *
84 * Returns BEFS_OK or BEFS_ERR.
85 *
86 * Calls specialized functions for each of the three possible
87 * datastream regions.
88 *
89 * 2001-11-15 Will Dyson
90 */
91int
92befs_fblock2brun(struct super_block *sb, befs_data_stream * data,
93 befs_blocknr_t fblock, befs_block_run * run)
94{
95 int err;
96 befs_off_t pos = fblock << BEFS_SB(sb)->block_shift;
97
98 if (pos < data->max_direct_range) {
99 err = befs_find_brun_direct(sb, data, fblock, run);
100
101 } else if (pos < data->max_indirect_range) {
102 err = befs_find_brun_indirect(sb, data, fblock, run);
103
104 } else if (pos < data->max_double_indirect_range) {
105 err = befs_find_brun_dblindirect(sb, data, fblock, run);
106
107 } else {
108 befs_error(sb,
109 "befs_fblock2brun() was asked to find block %lu, "
110 "which is not mapped by the datastream\n", fblock);
111 err = BEFS_ERR;
112 }
113 return err;
114}
115
116/**
117 * befs_read_lsmylink - read long symlink from datastream.
118 * @sb: Filesystem superblock
119 * @ds: Datastrem to read from
Uwe Zeisbergerc30fe7f2006-03-24 18:23:14 +0100120 * @buf: Buffer in which to place long symlink data
Linus Torvalds1da177e2005-04-16 15:20:36 -0700121 * @len: Length of the long symlink in bytes
122 *
123 * Returns the number of bytes read
124 */
125size_t
126befs_read_lsymlink(struct super_block * sb, befs_data_stream * ds, void *buff,
127 befs_off_t len)
128{
129 befs_off_t bytes_read = 0; /* bytes readed */
130 u16 plen;
131 struct buffer_head *bh = NULL;
132 befs_debug(sb, "---> befs_read_lsymlink() length: %Lu", len);
133
134 while (bytes_read < len) {
135 bh = befs_read_datastream(sb, ds, bytes_read, NULL);
136 if (!bh) {
137 befs_error(sb, "BeFS: Error reading datastream block "
138 "starting from %Lu", bytes_read);
139 befs_debug(sb, "<--- befs_read_lsymlink() ERROR");
140 return bytes_read;
141
142 }
143 plen = ((bytes_read + BEFS_SB(sb)->block_size) < len) ?
144 BEFS_SB(sb)->block_size : len - bytes_read;
145 memcpy(buff + bytes_read, bh->b_data, plen);
146 brelse(bh);
147 bytes_read += plen;
148 }
149
150 befs_debug(sb, "<--- befs_read_lsymlink() read %u bytes", bytes_read);
151 return bytes_read;
152}
153
154/**
155 * befs_count_blocks - blocks used by a file
156 * @sb: Filesystem superblock
157 * @ds: Datastream of the file
158 *
159 * Counts the number of fs blocks that the file represented by
160 * inode occupies on the filesystem, counting both regular file
161 * data and filesystem metadata (and eventually attribute data
162 * when we support attributes)
163*/
164
165befs_blocknr_t
166befs_count_blocks(struct super_block * sb, befs_data_stream * ds)
167{
168 befs_blocknr_t blocks;
169 befs_blocknr_t datablocks; /* File data blocks */
170 befs_blocknr_t metablocks; /* FS metadata blocks */
171 befs_sb_info *befs_sb = BEFS_SB(sb);
172
173 befs_debug(sb, "---> befs_count_blocks()");
174
175 datablocks = ds->size >> befs_sb->block_shift;
176 if (ds->size & (befs_sb->block_size - 1))
177 datablocks += 1;
178
179 metablocks = 1; /* Start with 1 block for inode */
180
181 /* Size of indirect block */
182 if (ds->size > ds->max_direct_range)
183 metablocks += ds->indirect.len;
184
185 /*
186 Double indir block, plus all the indirect blocks it mapps
187 In the double-indirect range, all block runs of data are
188 BEFS_DBLINDIR_BRUN_LEN blocks long. Therefore, we know
189 how many data block runs are in the double-indirect region,
190 and from that we know how many indirect blocks it takes to
191 map them. We assume that the indirect blocks are also
192 BEFS_DBLINDIR_BRUN_LEN blocks long.
193 */
194 if (ds->size > ds->max_indirect_range && ds->max_indirect_range != 0) {
195 uint dbl_bytes;
196 uint dbl_bruns;
197 uint indirblocks;
198
199 dbl_bytes =
200 ds->max_double_indirect_range - ds->max_indirect_range;
201 dbl_bruns =
202 dbl_bytes / (befs_sb->block_size * BEFS_DBLINDIR_BRUN_LEN);
203 indirblocks = dbl_bruns / befs_iaddrs_per_block(sb);
204
205 metablocks += ds->double_indirect.len;
206 metablocks += indirblocks;
207 }
208
209 blocks = datablocks + metablocks;
210 befs_debug(sb, "<--- befs_count_blocks() %u blocks", blocks);
211
212 return blocks;
213}
214
215/*
216 Finds the block run that starts at file block number blockno
217 in the file represented by the datastream data, if that
218 blockno is in the direct region of the datastream.
219
220 sb: the superblock
221 data: the datastream
222 blockno: the blocknumber to find
223 run: The found run is passed back through this pointer
224
225 Return value is BEFS_OK if the blockrun is found, BEFS_ERR
226 otherwise.
227
228 Algorithm:
229 Linear search. Checks each element of array[] to see if it
230 contains the blockno-th filesystem block. This is necessary
231 because the block runs map variable amounts of data. Simply
232 keeps a count of the number of blocks searched so far (sum),
233 incrementing this by the length of each block run as we come
234 across it. Adds sum to *count before returning (this is so
235 you can search multiple arrays that are logicaly one array,
236 as in the indirect region code).
237
238 When/if blockno is found, if blockno is inside of a block
Paulius Zaleckasefad798b2008-02-03 15:42:53 +0200239 run as stored on disk, we offset the start and length members
Linus Torvalds1da177e2005-04-16 15:20:36 -0700240 of the block run, so that blockno is the start and len is
241 still valid (the run ends in the same place).
242
243 2001-11-15 Will Dyson
244*/
245static int
246befs_find_brun_direct(struct super_block *sb, befs_data_stream * data,
247 befs_blocknr_t blockno, befs_block_run * run)
248{
249 int i;
250 befs_block_run *array = data->direct;
251 befs_blocknr_t sum;
252 befs_blocknr_t max_block =
253 data->max_direct_range >> BEFS_SB(sb)->block_shift;
254
255 befs_debug(sb, "---> befs_find_brun_direct(), find %lu", blockno);
256
257 if (blockno > max_block) {
258 befs_error(sb, "befs_find_brun_direct() passed block outside of"
259 "direct region");
260 return BEFS_ERR;
261 }
262
263 for (i = 0, sum = 0; i < BEFS_NUM_DIRECT_BLOCKS;
264 sum += array[i].len, i++) {
265 if (blockno >= sum && blockno < sum + (array[i].len)) {
266 int offset = blockno - sum;
267 run->allocation_group = array[i].allocation_group;
268 run->start = array[i].start + offset;
269 run->len = array[i].len - offset;
270
271 befs_debug(sb, "---> befs_find_brun_direct(), "
272 "found %lu at direct[%d]", blockno, i);
273 return BEFS_OK;
274 }
275 }
276
277 befs_debug(sb, "---> befs_find_brun_direct() ERROR");
278 return BEFS_ERR;
279}
280
281/*
282 Finds the block run that starts at file block number blockno
283 in the file represented by the datastream data, if that
284 blockno is in the indirect region of the datastream.
285
286 sb: the superblock
287 data: the datastream
288 blockno: the blocknumber to find
289 run: The found run is passed back through this pointer
290
291 Return value is BEFS_OK if the blockrun is found, BEFS_ERR
292 otherwise.
293
294 Algorithm:
295 For each block in the indirect run of the datastream, read
296 it in and search through it for search_blk.
297
298 XXX:
299 Really should check to make sure blockno is inside indirect
300 region.
301
302 2001-11-15 Will Dyson
303*/
304static int
305befs_find_brun_indirect(struct super_block *sb,
306 befs_data_stream * data, befs_blocknr_t blockno,
307 befs_block_run * run)
308{
309 int i, j;
310 befs_blocknr_t sum = 0;
311 befs_blocknr_t indir_start_blk;
312 befs_blocknr_t search_blk;
313 struct buffer_head *indirblock;
Al Viroa9721f32005-12-24 14:28:55 -0500314 befs_disk_block_run *array;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700315
316 befs_block_run indirect = data->indirect;
317 befs_blocknr_t indirblockno = iaddr2blockno(sb, &indirect);
318 int arraylen = befs_iaddrs_per_block(sb);
319
320 befs_debug(sb, "---> befs_find_brun_indirect(), find %lu", blockno);
321
322 indir_start_blk = data->max_direct_range >> BEFS_SB(sb)->block_shift;
323 search_blk = blockno - indir_start_blk;
324
325 /* Examine blocks of the indirect run one at a time */
326 for (i = 0; i < indirect.len; i++) {
327 indirblock = befs_bread(sb, indirblockno + i);
328 if (indirblock == NULL) {
329 befs_debug(sb,
330 "---> befs_find_brun_indirect() failed to "
331 "read disk block %lu from the indirect brun",
332 indirblockno + i);
333 return BEFS_ERR;
334 }
335
Al Viroa9721f32005-12-24 14:28:55 -0500336 array = (befs_disk_block_run *) indirblock->b_data;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700337
338 for (j = 0; j < arraylen; ++j) {
339 int len = fs16_to_cpu(sb, array[j].len);
340
341 if (search_blk >= sum && search_blk < sum + len) {
342 int offset = search_blk - sum;
343 run->allocation_group =
344 fs32_to_cpu(sb, array[j].allocation_group);
345 run->start =
346 fs16_to_cpu(sb, array[j].start) + offset;
347 run->len =
348 fs16_to_cpu(sb, array[j].len) - offset;
349
350 brelse(indirblock);
351 befs_debug(sb,
352 "<--- befs_find_brun_indirect() found "
353 "file block %lu at indirect[%d]",
354 blockno, j + (i * arraylen));
355 return BEFS_OK;
356 }
357 sum += len;
358 }
359
360 brelse(indirblock);
361 }
362
363 /* Only fallthrough is an error */
364 befs_error(sb, "BeFS: befs_find_brun_indirect() failed to find "
365 "file block %lu", blockno);
366
367 befs_debug(sb, "<--- befs_find_brun_indirect() ERROR");
368 return BEFS_ERR;
369}
370
371/*
372 Finds the block run that starts at file block number blockno
373 in the file represented by the datastream data, if that
374 blockno is in the double-indirect region of the datastream.
375
376 sb: the superblock
377 data: the datastream
378 blockno: the blocknumber to find
379 run: The found run is passed back through this pointer
380
381 Return value is BEFS_OK if the blockrun is found, BEFS_ERR
382 otherwise.
383
384 Algorithm:
385 The block runs in the double-indirect region are different.
386 They are always allocated 4 fs blocks at a time, so each
387 block run maps a constant amount of file data. This means
388 that we can directly calculate how many block runs into the
389 double-indirect region we need to go to get to the one that
390 maps a particular filesystem block.
391
392 We do this in two stages. First we calculate which of the
393 inode addresses in the double-indirect block will point us
394 to the indirect block that contains the mapping for the data,
395 then we calculate which of the inode addresses in that
396 indirect block maps the data block we are after.
397
398 Oh, and once we've done that, we actually read in the blocks
399 that contain the inode addresses we calculated above. Even
400 though the double-indirect run may be several blocks long,
401 we can calculate which of those blocks will contain the index
402 we are after and only read that one. We then follow it to
403 the indirect block and perform a similar process to find
404 the actual block run that maps the data block we are interested
405 in.
406
407 Then we offset the run as in befs_find_brun_array() and we are
408 done.
409
410 2001-11-15 Will Dyson
411*/
412static int
413befs_find_brun_dblindirect(struct super_block *sb,
414 befs_data_stream * data, befs_blocknr_t blockno,
415 befs_block_run * run)
416{
417 int dblindir_indx;
418 int indir_indx;
419 int offset;
420 int dbl_which_block;
421 int which_block;
422 int dbl_block_indx;
423 int block_indx;
424 off_t dblindir_leftover;
425 befs_blocknr_t blockno_at_run_start;
426 struct buffer_head *dbl_indir_block;
427 struct buffer_head *indir_block;
428 befs_block_run indir_run;
Al Viroa9721f32005-12-24 14:28:55 -0500429 befs_disk_inode_addr *iaddr_array = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700430 befs_sb_info *befs_sb = BEFS_SB(sb);
431
432 befs_blocknr_t indir_start_blk =
433 data->max_indirect_range >> befs_sb->block_shift;
434
435 off_t dbl_indir_off = blockno - indir_start_blk;
436
437 /* number of data blocks mapped by each of the iaddrs in
438 * the indirect block pointed to by the double indirect block
439 */
440 size_t iblklen = BEFS_DBLINDIR_BRUN_LEN;
441
442 /* number of data blocks mapped by each of the iaddrs in
443 * the double indirect block
444 */
445 size_t diblklen = iblklen * befs_iaddrs_per_block(sb)
446 * BEFS_DBLINDIR_BRUN_LEN;
447
448 befs_debug(sb, "---> befs_find_brun_dblindirect() find %lu", blockno);
449
450 /* First, discover which of the double_indir->indir blocks
451 * contains pos. Then figure out how much of pos that
452 * accounted for. Then discover which of the iaddrs in
453 * the indirect block contains pos.
454 */
455
456 dblindir_indx = dbl_indir_off / diblklen;
457 dblindir_leftover = dbl_indir_off % diblklen;
458 indir_indx = dblindir_leftover / diblklen;
459
460 /* Read double indirect block */
461 dbl_which_block = dblindir_indx / befs_iaddrs_per_block(sb);
462 if (dbl_which_block > data->double_indirect.len) {
463 befs_error(sb, "The double-indirect index calculated by "
464 "befs_read_brun_dblindirect(), %d, is outside the range "
465 "of the double-indirect block", dblindir_indx);
466 return BEFS_ERR;
467 }
468
469 dbl_indir_block =
470 befs_bread(sb, iaddr2blockno(sb, &data->double_indirect) +
471 dbl_which_block);
472 if (dbl_indir_block == NULL) {
473 befs_error(sb, "befs_read_brun_dblindirect() couldn't read the "
474 "double-indirect block at blockno %lu",
475 iaddr2blockno(sb,
476 &data->double_indirect) +
477 dbl_which_block);
478 brelse(dbl_indir_block);
479 return BEFS_ERR;
480 }
481
482 dbl_block_indx =
483 dblindir_indx - (dbl_which_block * befs_iaddrs_per_block(sb));
Al Viroa9721f32005-12-24 14:28:55 -0500484 iaddr_array = (befs_disk_inode_addr *) dbl_indir_block->b_data;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700485 indir_run = fsrun_to_cpu(sb, iaddr_array[dbl_block_indx]);
486 brelse(dbl_indir_block);
487 iaddr_array = NULL;
488
489 /* Read indirect block */
490 which_block = indir_indx / befs_iaddrs_per_block(sb);
491 if (which_block > indir_run.len) {
492 befs_error(sb, "The indirect index calculated by "
493 "befs_read_brun_dblindirect(), %d, is outside the range "
494 "of the indirect block", indir_indx);
495 return BEFS_ERR;
496 }
497
498 indir_block =
499 befs_bread(sb, iaddr2blockno(sb, &indir_run) + which_block);
500 if (indir_block == NULL) {
501 befs_error(sb, "befs_read_brun_dblindirect() couldn't read the "
502 "indirect block at blockno %lu",
503 iaddr2blockno(sb, &indir_run) + which_block);
504 brelse(indir_block);
505 return BEFS_ERR;
506 }
507
508 block_indx = indir_indx - (which_block * befs_iaddrs_per_block(sb));
Al Viroa9721f32005-12-24 14:28:55 -0500509 iaddr_array = (befs_disk_inode_addr *) indir_block->b_data;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700510 *run = fsrun_to_cpu(sb, iaddr_array[block_indx]);
511 brelse(indir_block);
512 iaddr_array = NULL;
513
514 blockno_at_run_start = indir_start_blk;
515 blockno_at_run_start += diblklen * dblindir_indx;
516 blockno_at_run_start += iblklen * indir_indx;
517 offset = blockno - blockno_at_run_start;
518
519 run->start += offset;
520 run->len -= offset;
521
522 befs_debug(sb, "Found file block %lu in double_indirect[%d][%d],"
523 " double_indirect_leftover = %lu",
524 blockno, dblindir_indx, indir_indx, dblindir_leftover);
525
526 return BEFS_OK;
527}