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" 21 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 120 * @buf: Buffer in which to place long symlink data 121 * @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 239 run as stored on disk, we offset the start and lenght members 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*/ 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 281static int 282befs_find_brun_indirect(struct super_block *sb, 283 befs_data_stream * data, befs_blocknr_t blockno, 284 befs_block_run * run) 285{ 286 int i, j; 287 befs_blocknr_t sum = 0; 288 befs_blocknr_t indir_start_blk; 289 befs_blocknr_t search_blk; 290 struct buffer_head *indirblock; 291 befs_disk_block_run *array; 292 293 befs_block_run indirect = data->indirect; 294 befs_blocknr_t indirblockno = iaddr2blockno(sb, &indirect); 295 int arraylen = befs_iaddrs_per_block(sb); 296 297 befs_debug(sb, "---> befs_find_brun_indirect(), find %lu", blockno); 298 299 indir_start_blk = data->max_direct_range >> BEFS_SB(sb)->block_shift; 300 search_blk = blockno - indir_start_blk; 301 302 /* Examine blocks of the indirect run one at a time */ 303 for (i = 0; i < indirect.len; i++) { 304 indirblock = befs_bread(sb, indirblockno + i); 305 if (indirblock == NULL) { 306 befs_debug(sb, 307 "---> befs_find_brun_indirect() failed to " 308 "read disk block %lu from the indirect brun", 309 indirblockno + i); 310 return BEFS_ERR; 311 } 312 313 array = (befs_disk_block_run *) indirblock->b_data; 314 315 for (j = 0; j < arraylen; ++j) { 316 int len = fs16_to_cpu(sb, array[j].len); 317 318 if (search_blk >= sum && search_blk < sum + len) { 319 int offset = search_blk - sum; 320 run->allocation_group = 321 fs32_to_cpu(sb, array[j].allocation_group); 322 run->start = 323 fs16_to_cpu(sb, array[j].start) + offset; 324 run->len = 325 fs16_to_cpu(sb, array[j].len) - offset; 326 327 brelse(indirblock); 328 befs_debug(sb, 329 "<--- befs_find_brun_indirect() found " 330 "file block %lu at indirect[%d]", 331 blockno, j + (i * arraylen)); 332 return BEFS_OK; 333 } 334 sum += len; 335 } 336 337 brelse(indirblock); 338 } 339 340 /* Only fallthrough is an error */ 341 befs_error(sb, "BeFS: befs_find_brun_indirect() failed to find " 342 "file block %lu", blockno); 343 344 befs_debug(sb, "<--- befs_find_brun_indirect() ERROR"); 345 return BEFS_ERR; 346} 347 348/* 349 Finds the block run that starts at file block number blockno 350 in the file represented by the datastream data, if that 351 blockno is in the double-indirect region of the datastream. 352 353 sb: the superblock 354 data: the datastream 355 blockno: the blocknumber to find 356 run: The found run is passed back through this pointer 357 358 Return value is BEFS_OK if the blockrun is found, BEFS_ERR 359 otherwise. 360 361 Algorithm: 362 The block runs in the double-indirect region are different. 363 They are always allocated 4 fs blocks at a time, so each 364 block run maps a constant amount of file data. This means 365 that we can directly calculate how many block runs into the 366 double-indirect region we need to go to get to the one that 367 maps a particular filesystem block. 368 369 We do this in two stages. First we calculate which of the 370 inode addresses in the double-indirect block will point us 371 to the indirect block that contains the mapping for the data, 372 then we calculate which of the inode addresses in that 373 indirect block maps the data block we are after. 374 375 Oh, and once we've done that, we actually read in the blocks 376 that contain the inode addresses we calculated above. Even 377 though the double-indirect run may be several blocks long, 378 we can calculate which of those blocks will contain the index 379 we are after and only read that one. We then follow it to 380 the indirect block and perform a similar process to find 381 the actual block run that maps the data block we are interested 382 in. 383 384 Then we offset the run as in befs_find_brun_array() and we are 385 done. 386 387 2001-11-15 Will Dyson 388*/ 389static int 390befs_find_brun_dblindirect(struct super_block *sb, 391 befs_data_stream * data, befs_blocknr_t blockno, 392 befs_block_run * run) 393{ 394 int dblindir_indx; 395 int indir_indx; 396 int offset; 397 int dbl_which_block; 398 int which_block; 399 int dbl_block_indx; 400 int block_indx; 401 off_t dblindir_leftover; 402 befs_blocknr_t blockno_at_run_start; 403 struct buffer_head *dbl_indir_block; 404 struct buffer_head *indir_block; 405 befs_block_run indir_run; 406 befs_disk_inode_addr *iaddr_array = NULL; 407 befs_sb_info *befs_sb = BEFS_SB(sb); 408 409 befs_blocknr_t indir_start_blk = 410 data->max_indirect_range >> befs_sb->block_shift; 411 412 off_t dbl_indir_off = blockno - indir_start_blk; 413 414 /* number of data blocks mapped by each of the iaddrs in 415 * the indirect block pointed to by the double indirect block 416 */ 417 size_t iblklen = BEFS_DBLINDIR_BRUN_LEN; 418 419 /* number of data blocks mapped by each of the iaddrs in 420 * the double indirect block 421 */ 422 size_t diblklen = iblklen * befs_iaddrs_per_block(sb) 423 * BEFS_DBLINDIR_BRUN_LEN; 424 425 befs_debug(sb, "---> befs_find_brun_dblindirect() find %lu", blockno); 426 427 /* First, discover which of the double_indir->indir blocks 428 * contains pos. Then figure out how much of pos that 429 * accounted for. Then discover which of the iaddrs in 430 * the indirect block contains pos. 431 */ 432 433 dblindir_indx = dbl_indir_off / diblklen; 434 dblindir_leftover = dbl_indir_off % diblklen; 435 indir_indx = dblindir_leftover / diblklen; 436 437 /* Read double indirect block */ 438 dbl_which_block = dblindir_indx / befs_iaddrs_per_block(sb); 439 if (dbl_which_block > data->double_indirect.len) { 440 befs_error(sb, "The double-indirect index calculated by " 441 "befs_read_brun_dblindirect(), %d, is outside the range " 442 "of the double-indirect block", dblindir_indx); 443 return BEFS_ERR; 444 } 445 446 dbl_indir_block = 447 befs_bread(sb, iaddr2blockno(sb, &data->double_indirect) + 448 dbl_which_block); 449 if (dbl_indir_block == NULL) { 450 befs_error(sb, "befs_read_brun_dblindirect() couldn't read the " 451 "double-indirect block at blockno %lu", 452 iaddr2blockno(sb, 453 &data->double_indirect) + 454 dbl_which_block); 455 brelse(dbl_indir_block); 456 return BEFS_ERR; 457 } 458 459 dbl_block_indx = 460 dblindir_indx - (dbl_which_block * befs_iaddrs_per_block(sb)); 461 iaddr_array = (befs_disk_inode_addr *) dbl_indir_block->b_data; 462 indir_run = fsrun_to_cpu(sb, iaddr_array[dbl_block_indx]); 463 brelse(dbl_indir_block); 464 iaddr_array = NULL; 465 466 /* Read indirect block */ 467 which_block = indir_indx / befs_iaddrs_per_block(sb); 468 if (which_block > indir_run.len) { 469 befs_error(sb, "The indirect index calculated by " 470 "befs_read_brun_dblindirect(), %d, is outside the range " 471 "of the indirect block", indir_indx); 472 return BEFS_ERR; 473 } 474 475 indir_block = 476 befs_bread(sb, iaddr2blockno(sb, &indir_run) + which_block); 477 if (indir_block == NULL) { 478 befs_error(sb, "befs_read_brun_dblindirect() couldn't read the " 479 "indirect block at blockno %lu", 480 iaddr2blockno(sb, &indir_run) + which_block); 481 brelse(indir_block); 482 return BEFS_ERR; 483 } 484 485 block_indx = indir_indx - (which_block * befs_iaddrs_per_block(sb)); 486 iaddr_array = (befs_disk_inode_addr *) indir_block->b_data; 487 *run = fsrun_to_cpu(sb, iaddr_array[block_indx]); 488 brelse(indir_block); 489 iaddr_array = NULL; 490 491 blockno_at_run_start = indir_start_blk; 492 blockno_at_run_start += diblklen * dblindir_indx; 493 blockno_at_run_start += iblklen * indir_indx; 494 offset = blockno - blockno_at_run_start; 495 496 run->start += offset; 497 run->len -= offset; 498 499 befs_debug(sb, "Found file block %lu in double_indirect[%d][%d]," 500 " double_indirect_leftover = %lu", 501 blockno, dblindir_indx, indir_indx, dblindir_leftover); 502 503 return BEFS_OK; 504} 505