Commit | Line | Data |
---|---|---|
1da177e4 LT |
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/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" | |
1da177e4 LT |
21 | |
22 | const befs_inode_addr BAD_IADDR = { 0, 0, 0 }; | |
23 | ||
24 | static int befs_find_brun_direct(struct super_block *sb, | |
25 | befs_data_stream * data, | |
26 | befs_blocknr_t blockno, befs_block_run * run); | |
27 | ||
28 | static 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 | ||
33 | static 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 | */ | |
48 | struct buffer_head * | |
49 | befs_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 | */ | |
91 | int | |
92 | befs_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 | |
c30fe7f7 | 120 | * @buf: Buffer in which to place long symlink data |
1da177e4 LT |
121 | * @len: Length of the long symlink in bytes |
122 | * | |
123 | * Returns the number of bytes read | |
124 | */ | |
125 | size_t | |
126 | befs_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 | ||
165 | befs_blocknr_t | |
166 | befs_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 | |
efad798b | 239 | run as stored on disk, we offset the start and length members |
1da177e4 LT |
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 | */ | |
245 | static int | |
246 | befs_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 | */ | |
304 | static int | |
305 | befs_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; | |
a9721f31 | 314 | befs_disk_block_run *array; |
1da177e4 LT |
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, "---> 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 | ||
a9721f31 | 336 | array = (befs_disk_block_run *) indirblock->b_data; |
1da177e4 LT |
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 | "<--- 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 | */ | |
412 | static int | |
413 | befs_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; | |
a9721f31 | 429 | befs_disk_inode_addr *iaddr_array = NULL; |
1da177e4 LT |
430 | 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)); | |
a9721f31 | 484 | iaddr_array = (befs_disk_inode_addr *) dbl_indir_block->b_data; |
1da177e4 LT |
485 | 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)); | |
a9721f31 | 509 | iaddr_array = (befs_disk_inode_addr *) indir_block->b_data; |
1da177e4 LT |
510 | *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 | } |