blob: b7d6b920f65f129a1c2e656cf61d11329d33dcea [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"
21#include "endian.h"
22
23const befs_inode_addr BAD_IADDR = { 0, 0, 0 };
24
25static int befs_find_brun_direct(struct super_block *sb,
26 befs_data_stream * data,
27 befs_blocknr_t blockno, befs_block_run * run);
28
29static int befs_find_brun_indirect(struct super_block *sb,
30 befs_data_stream * data,
31 befs_blocknr_t blockno,
32 befs_block_run * run);
33
34static int befs_find_brun_dblindirect(struct super_block *sb,
35 befs_data_stream * data,
36 befs_blocknr_t blockno,
37 befs_block_run * run);
38
39/**
40 * befs_read_datastream - get buffer_head containing data, starting from pos.
41 * @sb: Filesystem superblock
42 * @ds: datastrem to find data with
43 * @pos: start of data
44 * @off: offset of data in buffer_head->b_data
45 *
46 * Returns pointer to buffer_head containing data starting with offset @off,
47 * if you don't need to know offset just set @off = NULL.
48 */
49struct buffer_head *
50befs_read_datastream(struct super_block *sb, befs_data_stream * ds,
51 befs_off_t pos, uint * off)
52{
53 struct buffer_head *bh = NULL;
54 befs_block_run run;
55 befs_blocknr_t block; /* block coresponding to pos */
56
57 befs_debug(sb, "---> befs_read_datastream() %Lu", pos);
58 block = pos >> BEFS_SB(sb)->block_shift;
59 if (off)
60 *off = pos - (block << BEFS_SB(sb)->block_shift);
61
62 if (befs_fblock2brun(sb, ds, block, &run) != BEFS_OK) {
63 befs_error(sb, "BeFS: Error finding disk addr of block %lu",
64 block);
65 befs_debug(sb, "<--- befs_read_datastream() ERROR");
66 return NULL;
67 }
68 bh = befs_bread_iaddr(sb, run);
69 if (!bh) {
70 befs_error(sb, "BeFS: Error reading block %lu from datastream",
71 block);
72 return NULL;
73 }
74
75 befs_debug(sb, "<--- befs_read_datastream() read data, starting at %Lu",
76 pos);
77
78 return bh;
79}
80
81/*
82 * Takes a file position and gives back a brun who's starting block
83 * is block number fblock of the file.
84 *
85 * Returns BEFS_OK or BEFS_ERR.
86 *
87 * Calls specialized functions for each of the three possible
88 * datastream regions.
89 *
90 * 2001-11-15 Will Dyson
91 */
92int
93befs_fblock2brun(struct super_block *sb, befs_data_stream * data,
94 befs_blocknr_t fblock, befs_block_run * run)
95{
96 int err;
97 befs_off_t pos = fblock << BEFS_SB(sb)->block_shift;
98
99 if (pos < data->max_direct_range) {
100 err = befs_find_brun_direct(sb, data, fblock, run);
101
102 } else if (pos < data->max_indirect_range) {
103 err = befs_find_brun_indirect(sb, data, fblock, run);
104
105 } else if (pos < data->max_double_indirect_range) {
106 err = befs_find_brun_dblindirect(sb, data, fblock, run);
107
108 } else {
109 befs_error(sb,
110 "befs_fblock2brun() was asked to find block %lu, "
111 "which is not mapped by the datastream\n", fblock);
112 err = BEFS_ERR;
113 }
114 return err;
115}
116
117/**
118 * befs_read_lsmylink - read long symlink from datastream.
119 * @sb: Filesystem superblock
120 * @ds: Datastrem to read from
Uwe Zeisbergerc30fe7f2006-03-24 18:23:14 +0100121 * @buf: Buffer in which to place long symlink data
Linus Torvalds1da177e2005-04-16 15:20:36 -0700122 * @len: Length of the long symlink in bytes
123 *
124 * Returns the number of bytes read
125 */
126size_t
127befs_read_lsymlink(struct super_block * sb, befs_data_stream * ds, void *buff,
128 befs_off_t len)
129{
130 befs_off_t bytes_read = 0; /* bytes readed */
131 u16 plen;
132 struct buffer_head *bh = NULL;
133 befs_debug(sb, "---> befs_read_lsymlink() length: %Lu", len);
134
135 while (bytes_read < len) {
136 bh = befs_read_datastream(sb, ds, bytes_read, NULL);
137 if (!bh) {
138 befs_error(sb, "BeFS: Error reading datastream block "
139 "starting from %Lu", bytes_read);
140 befs_debug(sb, "<--- befs_read_lsymlink() ERROR");
141 return bytes_read;
142
143 }
144 plen = ((bytes_read + BEFS_SB(sb)->block_size) < len) ?
145 BEFS_SB(sb)->block_size : len - bytes_read;
146 memcpy(buff + bytes_read, bh->b_data, plen);
147 brelse(bh);
148 bytes_read += plen;
149 }
150
151 befs_debug(sb, "<--- befs_read_lsymlink() read %u bytes", bytes_read);
152 return bytes_read;
153}
154
155/**
156 * befs_count_blocks - blocks used by a file
157 * @sb: Filesystem superblock
158 * @ds: Datastream of the file
159 *
160 * Counts the number of fs blocks that the file represented by
161 * inode occupies on the filesystem, counting both regular file
162 * data and filesystem metadata (and eventually attribute data
163 * when we support attributes)
164*/
165
166befs_blocknr_t
167befs_count_blocks(struct super_block * sb, befs_data_stream * ds)
168{
169 befs_blocknr_t blocks;
170 befs_blocknr_t datablocks; /* File data blocks */
171 befs_blocknr_t metablocks; /* FS metadata blocks */
172 befs_sb_info *befs_sb = BEFS_SB(sb);
173
174 befs_debug(sb, "---> befs_count_blocks()");
175
176 datablocks = ds->size >> befs_sb->block_shift;
177 if (ds->size & (befs_sb->block_size - 1))
178 datablocks += 1;
179
180 metablocks = 1; /* Start with 1 block for inode */
181
182 /* Size of indirect block */
183 if (ds->size > ds->max_direct_range)
184 metablocks += ds->indirect.len;
185
186 /*
187 Double indir block, plus all the indirect blocks it mapps
188 In the double-indirect range, all block runs of data are
189 BEFS_DBLINDIR_BRUN_LEN blocks long. Therefore, we know
190 how many data block runs are in the double-indirect region,
191 and from that we know how many indirect blocks it takes to
192 map them. We assume that the indirect blocks are also
193 BEFS_DBLINDIR_BRUN_LEN blocks long.
194 */
195 if (ds->size > ds->max_indirect_range && ds->max_indirect_range != 0) {
196 uint dbl_bytes;
197 uint dbl_bruns;
198 uint indirblocks;
199
200 dbl_bytes =
201 ds->max_double_indirect_range - ds->max_indirect_range;
202 dbl_bruns =
203 dbl_bytes / (befs_sb->block_size * BEFS_DBLINDIR_BRUN_LEN);
204 indirblocks = dbl_bruns / befs_iaddrs_per_block(sb);
205
206 metablocks += ds->double_indirect.len;
207 metablocks += indirblocks;
208 }
209
210 blocks = datablocks + metablocks;
211 befs_debug(sb, "<--- befs_count_blocks() %u blocks", blocks);
212
213 return blocks;
214}
215
216/*
217 Finds the block run that starts at file block number blockno
218 in the file represented by the datastream data, if that
219 blockno is in the direct region of the datastream.
220
221 sb: the superblock
222 data: the datastream
223 blockno: the blocknumber to find
224 run: The found run is passed back through this pointer
225
226 Return value is BEFS_OK if the blockrun is found, BEFS_ERR
227 otherwise.
228
229 Algorithm:
230 Linear search. Checks each element of array[] to see if it
231 contains the blockno-th filesystem block. This is necessary
232 because the block runs map variable amounts of data. Simply
233 keeps a count of the number of blocks searched so far (sum),
234 incrementing this by the length of each block run as we come
235 across it. Adds sum to *count before returning (this is so
236 you can search multiple arrays that are logicaly one array,
237 as in the indirect region code).
238
239 When/if blockno is found, if blockno is inside of a block
240 run as stored on disk, we offset the start and lenght members
241 of the block run, so that blockno is the start and len is
242 still valid (the run ends in the same place).
243
244 2001-11-15 Will Dyson
245*/
246static int
247befs_find_brun_direct(struct super_block *sb, befs_data_stream * data,
248 befs_blocknr_t blockno, befs_block_run * run)
249{
250 int i;
251 befs_block_run *array = data->direct;
252 befs_blocknr_t sum;
253 befs_blocknr_t max_block =
254 data->max_direct_range >> BEFS_SB(sb)->block_shift;
255
256 befs_debug(sb, "---> befs_find_brun_direct(), find %lu", blockno);
257
258 if (blockno > max_block) {
259 befs_error(sb, "befs_find_brun_direct() passed block outside of"
260 "direct region");
261 return BEFS_ERR;
262 }
263
264 for (i = 0, sum = 0; i < BEFS_NUM_DIRECT_BLOCKS;
265 sum += array[i].len, i++) {
266 if (blockno >= sum && blockno < sum + (array[i].len)) {
267 int offset = blockno - sum;
268 run->allocation_group = array[i].allocation_group;
269 run->start = array[i].start + offset;
270 run->len = array[i].len - offset;
271
272 befs_debug(sb, "---> befs_find_brun_direct(), "
273 "found %lu at direct[%d]", blockno, i);
274 return BEFS_OK;
275 }
276 }
277
278 befs_debug(sb, "---> befs_find_brun_direct() ERROR");
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_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, "---> befs_find_brun_indirect(), find %lu", 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,
331 "---> befs_find_brun_indirect() failed to "
332 "read disk block %lu from the indirect brun",
333 indirblockno + i);
334 return BEFS_ERR;
335 }
336
337 array = (befs_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 "<--- befs_find_brun_indirect() found "
354 "file block %lu at indirect[%d]",
355 blockno, 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: befs_find_brun_indirect() failed to find "
366 "file block %lu", blockno);
367
368 befs_debug(sb, "<--- befs_find_brun_indirect() ERROR");
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_inode_addr *iaddr_array = NULL;
431 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, "---> befs_find_brun_dblindirect() find %lu", 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 "befs_read_brun_dblindirect(), %d, is outside the range "
466 "of the double-indirect block", dblindir_indx);
467 return BEFS_ERR;
468 }
469
470 dbl_indir_block =
471 befs_bread(sb, iaddr2blockno(sb, &data->double_indirect) +
472 dbl_which_block);
473 if (dbl_indir_block == NULL) {
474 befs_error(sb, "befs_read_brun_dblindirect() couldn't read the "
475 "double-indirect block at blockno %lu",
476 iaddr2blockno(sb,
477 &data->double_indirect) +
478 dbl_which_block);
479 brelse(dbl_indir_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_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 iaddr_array = NULL;
489
490 /* Read indirect block */
491 which_block = indir_indx / befs_iaddrs_per_block(sb);
492 if (which_block > indir_run.len) {
493 befs_error(sb, "The indirect index calculated by "
494 "befs_read_brun_dblindirect(), %d, is outside the range "
495 "of the indirect block", indir_indx);
496 return BEFS_ERR;
497 }
498
499 indir_block =
500 befs_bread(sb, iaddr2blockno(sb, &indir_run) + which_block);
501 if (indir_block == NULL) {
502 befs_error(sb, "befs_read_brun_dblindirect() couldn't read the "
503 "indirect block at blockno %lu",
504 iaddr2blockno(sb, &indir_run) + which_block);
505 brelse(indir_block);
506 return BEFS_ERR;
507 }
508
509 block_indx = indir_indx - (which_block * befs_iaddrs_per_block(sb));
510 iaddr_array = (befs_inode_addr *) indir_block->b_data;
511 *run = fsrun_to_cpu(sb, iaddr_array[block_indx]);
512 brelse(indir_block);
513 iaddr_array = NULL;
514
515 blockno_at_run_start = indir_start_blk;
516 blockno_at_run_start += diblklen * dblindir_indx;
517 blockno_at_run_start += iblklen * indir_indx;
518 offset = blockno - blockno_at_run_start;
519
520 run->start += offset;
521 run->len -= offset;
522
523 befs_debug(sb, "Found file block %lu in double_indirect[%d][%d],"
524 " double_indirect_leftover = %lu",
525 blockno, dblindir_indx, indir_indx, dblindir_leftover);
526
527 return BEFS_OK;
528}