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> | |
1da177e4 LT |
14 | #include <linux/buffer_head.h> |
15 | #include <linux/string.h> | |
16 | ||
17 | #include "befs.h" | |
18 | #include "datastream.h" | |
19 | #include "io.h" | |
1da177e4 LT |
20 | |
21 | const befs_inode_addr BAD_IADDR = { 0, 0, 0 }; | |
22 | ||
23 | static int befs_find_brun_direct(struct super_block *sb, | |
24 | befs_data_stream * data, | |
25 | befs_blocknr_t blockno, befs_block_run * run); | |
26 | ||
27 | static 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 | ||
32 | static 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 | */ | |
47 | struct buffer_head * | |
48 | befs_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 | ||
dac52fc1 | 55 | befs_debug(sb, "---> %s %llu", __func__, pos); |
1da177e4 LT |
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", | |
dac52fc1 FF |
62 | (unsigned long)block); |
63 | befs_debug(sb, "<--- %s ERROR", __func__); | |
1da177e4 LT |
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", | |
dac52fc1 | 69 | (unsigned long)block); |
1da177e4 LT |
70 | return NULL; |
71 | } | |
72 | ||
dac52fc1 | 73 | befs_debug(sb, "<--- %s read data, starting at %llu", __func__, pos); |
1da177e4 LT |
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 | */ | |
89 | int | |
90 | befs_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, " | |
dac52fc1 FF |
108 | "which is not mapped by the datastream\n", |
109 | (unsigned long)fblock); | |
1da177e4 LT |
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 | |
817e1d90 | 119 | * @buff: Buffer in which to place long symlink data |
1da177e4 LT |
120 | * @len: Length of the long symlink in bytes |
121 | * | |
122 | * Returns the number of bytes read | |
123 | */ | |
124 | size_t | |
125 | befs_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; | |
dac52fc1 | 131 | befs_debug(sb, "---> %s length: %llu", __func__, len); |
1da177e4 LT |
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 " | |
dac52fc1 FF |
137 | "starting from %llu", bytes_read); |
138 | befs_debug(sb, "<--- %s ERROR", __func__); | |
1da177e4 LT |
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 | ||
dac52fc1 FF |
149 | befs_debug(sb, "<--- %s read %u bytes", __func__, (unsigned int) |
150 | bytes_read); | |
1da177e4 LT |
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 | ||
dac52fc1 | 173 | befs_debug(sb, "---> %s", __func__); |
1da177e4 LT |
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; | |
dac52fc1 | 210 | befs_debug(sb, "<--- %s %u blocks", __func__, (unsigned int)blocks); |
1da177e4 LT |
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 | ||
dac52fc1 | 255 | befs_debug(sb, "---> %s, find %lu", __func__, (unsigned long)blockno); |
1da177e4 LT |
256 | |
257 | if (blockno > max_block) { | |
dac52fc1 FF |
258 | befs_error(sb, "%s passed block outside of direct region", |
259 | __func__); | |
1da177e4 LT |
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 | ||
dac52fc1 FF |
271 | befs_debug(sb, "---> %s, " |
272 | "found %lu at direct[%d]", __func__, | |
273 | (unsigned long)blockno, i); | |
1da177e4 LT |
274 | return BEFS_OK; |
275 | } | |
276 | } | |
277 | ||
dac52fc1 | 278 | befs_debug(sb, "---> %s ERROR", __func__); |
1da177e4 LT |
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 | */ | |
305 | static int | |
306 | befs_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; | |
a9721f31 | 315 | befs_disk_block_run *array; |
1da177e4 LT |
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 | ||
dac52fc1 | 321 | befs_debug(sb, "---> %s, find %lu", __func__, (unsigned long)blockno); |
1da177e4 LT |
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) { | |
dac52fc1 FF |
330 | befs_debug(sb, "---> %s failed to read " |
331 | "disk block %lu from the indirect brun", | |
332 | __func__, (unsigned long)indirblockno + i); | |
1da177e4 LT |
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, | |
dac52fc1 FF |
352 | "<--- %s found file block " |
353 | "%lu at indirect[%d]", __func__, | |
354 | (unsigned long)blockno, | |
355 | j + (i * arraylen)); | |
1da177e4 LT |
356 | return BEFS_OK; |
357 | } | |
358 | sum += len; | |
359 | } | |
360 | ||
361 | brelse(indirblock); | |
362 | } | |
363 | ||
364 | /* Only fallthrough is an error */ | |
dac52fc1 FF |
365 | befs_error(sb, "BeFS: %s failed to find " |
366 | "file block %lu", __func__, (unsigned long)blockno); | |
1da177e4 | 367 | |
dac52fc1 | 368 | befs_debug(sb, "<--- %s ERROR", __func__); |
1da177e4 LT |
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 | */ | |
413 | static int | |
414 | befs_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; | |
a9721f31 | 430 | befs_disk_inode_addr *iaddr_array = NULL; |
1da177e4 LT |
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 | ||
dac52fc1 | 449 | befs_debug(sb, "---> %s find %lu", __func__, (unsigned long)blockno); |
1da177e4 LT |
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 " | |
dac52fc1 FF |
465 | "%s, %d, is outside the range " |
466 | "of the double-indirect block", __func__, | |
467 | dblindir_indx); | |
1da177e4 LT |
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) { | |
dac52fc1 FF |
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) + | |
1da177e4 LT |
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)); | |
a9721f31 | 486 | iaddr_array = (befs_disk_inode_addr *) dbl_indir_block->b_data; |
1da177e4 LT |
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 " | |
dac52fc1 FF |
495 | "%s, %d, is outside the range " |
496 | "of the indirect block", __func__, indir_indx); | |
1da177e4 LT |
497 | return BEFS_ERR; |
498 | } | |
499 | ||
500 | indir_block = | |
501 | befs_bread(sb, iaddr2blockno(sb, &indir_run) + which_block); | |
502 | if (indir_block == NULL) { | |
dac52fc1 FF |
503 | befs_error(sb, "%s couldn't read the indirect block " |
504 | "at blockno %lu", __func__, (unsigned long) | |
1da177e4 LT |
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)); | |
a9721f31 | 511 | iaddr_array = (befs_disk_inode_addr *) indir_block->b_data; |
1da177e4 LT |
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]," | |
dac52fc1 | 525 | " double_indirect_leftover = %lu", (unsigned long) |
1da177e4 LT |
526 | blockno, dblindir_indx, indir_indx, dblindir_leftover); |
527 | ||
528 | return BEFS_OK; | |
529 | } |