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 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 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 */ 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 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 */ 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; 314 befs_disk_block_run *array; 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 336 array = (befs_disk_block_run *) indirblock->b_data; 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; 429 befs_disk_inode_addr *iaddr_array = NULL; 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)); 484 iaddr_array = (befs_disk_inode_addr *) dbl_indir_block->b_data; 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)); 509 iaddr_array = (befs_disk_inode_addr *) indir_block->b_data; 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 } 528