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/buffer_head.h> 15 #include <linux/string.h> 16 17 #include "befs.h" 18 #include "datastream.h" 19 #include "io.h" 20 21 const befs_inode_addr BAD_IADDR = { 0, 0, 0 }; 22 23 static int befs_find_brun_direct(struct super_block *sb, 24 const 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 const 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 const 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: datastream 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, const befs_data_stream *ds, 49 befs_off_t pos, uint *off) 50 { 51 struct buffer_head *bh; 52 befs_block_run run; 53 befs_blocknr_t block; /* block coresponding to pos */ 54 55 befs_debug(sb, "---> %s %llu", __func__, pos); 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", 62 (unsigned long)block); 63 befs_debug(sb, "<--- %s ERROR", __func__); 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", 69 (unsigned long)block); 70 return NULL; 71 } 72 73 befs_debug(sb, "<--- %s read data, starting at %llu", __func__, pos); 74 75 return bh; 76 } 77 78 /** 79 * befs_fblock2brun - give back block run for fblock 80 * @sb: the superblock 81 * @data: datastream to read from 82 * @fblock: the blocknumber with the file position to find 83 * @run: The found run is passed back through this pointer 84 * 85 * Takes a file position and gives back a brun who's starting block 86 * is block number fblock of the file. 87 * 88 * Returns BEFS_OK or BEFS_ERR. 89 * 90 * Calls specialized functions for each of the three possible 91 * datastream regions. 92 * 93 * 2001-11-15 Will Dyson 94 */ 95 int 96 befs_fblock2brun(struct super_block *sb, const befs_data_stream *data, 97 befs_blocknr_t fblock, befs_block_run *run) 98 { 99 int err; 100 befs_off_t pos = fblock << BEFS_SB(sb)->block_shift; 101 102 if (pos < data->max_direct_range) { 103 err = befs_find_brun_direct(sb, data, fblock, run); 104 105 } else if (pos < data->max_indirect_range) { 106 err = befs_find_brun_indirect(sb, data, fblock, run); 107 108 } else if (pos < data->max_double_indirect_range) { 109 err = befs_find_brun_dblindirect(sb, data, fblock, run); 110 111 } else { 112 befs_error(sb, 113 "befs_fblock2brun() was asked to find block %lu, " 114 "which is not mapped by the datastream\n", 115 (unsigned long)fblock); 116 err = BEFS_ERR; 117 } 118 return err; 119 } 120 121 /** 122 * befs_read_lsmylink - read long symlink from datastream. 123 * @sb: Filesystem superblock 124 * @ds: Datastream to read from 125 * @buff: Buffer in which to place long symlink data 126 * @len: Length of the long symlink in bytes 127 * 128 * Returns the number of bytes read 129 */ 130 size_t 131 befs_read_lsymlink(struct super_block *sb, const befs_data_stream *ds, 132 void *buff, befs_off_t len) 133 { 134 befs_off_t bytes_read = 0; /* bytes readed */ 135 u16 plen; 136 struct buffer_head *bh; 137 138 befs_debug(sb, "---> %s length: %llu", __func__, len); 139 140 while (bytes_read < len) { 141 bh = befs_read_datastream(sb, ds, bytes_read, NULL); 142 if (!bh) { 143 befs_error(sb, "BeFS: Error reading datastream block " 144 "starting from %llu", bytes_read); 145 befs_debug(sb, "<--- %s ERROR", __func__); 146 return bytes_read; 147 148 } 149 plen = ((bytes_read + BEFS_SB(sb)->block_size) < len) ? 150 BEFS_SB(sb)->block_size : len - bytes_read; 151 memcpy(buff + bytes_read, bh->b_data, plen); 152 brelse(bh); 153 bytes_read += plen; 154 } 155 156 befs_debug(sb, "<--- %s read %u bytes", __func__, (unsigned int) 157 bytes_read); 158 return bytes_read; 159 } 160 161 /** 162 * befs_count_blocks - blocks used by a file 163 * @sb: Filesystem superblock 164 * @ds: Datastream of the file 165 * 166 * Counts the number of fs blocks that the file represented by 167 * inode occupies on the filesystem, counting both regular file 168 * data and filesystem metadata (and eventually attribute data 169 * when we support attributes) 170 */ 171 172 befs_blocknr_t 173 befs_count_blocks(struct super_block *sb, const befs_data_stream *ds) 174 { 175 befs_blocknr_t blocks; 176 befs_blocknr_t datablocks; /* File data blocks */ 177 befs_blocknr_t metablocks; /* FS metadata blocks */ 178 struct befs_sb_info *befs_sb = BEFS_SB(sb); 179 180 befs_debug(sb, "---> %s", __func__); 181 182 datablocks = ds->size >> befs_sb->block_shift; 183 if (ds->size & (befs_sb->block_size - 1)) 184 datablocks += 1; 185 186 metablocks = 1; /* Start with 1 block for inode */ 187 188 /* Size of indirect block */ 189 if (ds->size > ds->max_direct_range) 190 metablocks += ds->indirect.len; 191 192 /* 193 * Double indir block, plus all the indirect blocks it maps. 194 * In the double-indirect range, all block runs of data are 195 * BEFS_DBLINDIR_BRUN_LEN blocks long. Therefore, we know 196 * how many data block runs are in the double-indirect region, 197 * and from that we know how many indirect blocks it takes to 198 * map them. We assume that the indirect blocks are also 199 * BEFS_DBLINDIR_BRUN_LEN blocks long. 200 */ 201 if (ds->size > ds->max_indirect_range && ds->max_indirect_range != 0) { 202 uint dbl_bytes; 203 uint dbl_bruns; 204 uint indirblocks; 205 206 dbl_bytes = 207 ds->max_double_indirect_range - ds->max_indirect_range; 208 dbl_bruns = 209 dbl_bytes / (befs_sb->block_size * BEFS_DBLINDIR_BRUN_LEN); 210 indirblocks = dbl_bruns / befs_iaddrs_per_block(sb); 211 212 metablocks += ds->double_indirect.len; 213 metablocks += indirblocks; 214 } 215 216 blocks = datablocks + metablocks; 217 befs_debug(sb, "<--- %s %u blocks", __func__, (unsigned int)blocks); 218 219 return blocks; 220 } 221 222 /** 223 * befs_find_brun_direct - find a direct block run in the datastream 224 * @sb: the superblock 225 * @data: the datastream 226 * @blockno: the blocknumber to find 227 * @run: The found run is passed back through this pointer 228 * 229 * Finds the block run that starts at file block number blockno 230 * in the file represented by the datastream data, if that 231 * blockno is in the direct region of the datastream. 232 * 233 * Return value is BEFS_OK if the blockrun is found, BEFS_ERR 234 * otherwise. 235 * 236 * Algorithm: 237 * Linear search. Checks each element of array[] to see if it 238 * contains the blockno-th filesystem block. This is necessary 239 * because the block runs map variable amounts of data. Simply 240 * keeps a count of the number of blocks searched so far (sum), 241 * incrementing this by the length of each block run as we come 242 * across it. Adds sum to *count before returning (this is so 243 * you can search multiple arrays that are logicaly one array, 244 * as in the indirect region code). 245 * 246 * When/if blockno is found, if blockno is inside of a block 247 * run as stored on disk, we offset the start and length members 248 * of the block run, so that blockno is the start and len is 249 * still valid (the run ends in the same place). 250 */ 251 static int 252 befs_find_brun_direct(struct super_block *sb, const befs_data_stream *data, 253 befs_blocknr_t blockno, befs_block_run *run) 254 { 255 int i; 256 const befs_block_run *array = data->direct; 257 befs_blocknr_t sum; 258 259 befs_debug(sb, "---> %s, find %lu", __func__, (unsigned long)blockno); 260 261 for (i = 0, sum = 0; i < BEFS_NUM_DIRECT_BLOCKS; 262 sum += array[i].len, i++) { 263 if (blockno >= sum && blockno < sum + (array[i].len)) { 264 int offset = blockno - sum; 265 266 run->allocation_group = array[i].allocation_group; 267 run->start = array[i].start + offset; 268 run->len = array[i].len - offset; 269 270 befs_debug(sb, "---> %s, " 271 "found %lu at direct[%d]", __func__, 272 (unsigned long)blockno, i); 273 return BEFS_OK; 274 } 275 } 276 277 befs_error(sb, "%s failed to find file block %lu", __func__, 278 (unsigned long)blockno); 279 befs_debug(sb, "---> %s ERROR", __func__); 280 return BEFS_ERR; 281 } 282 283 /** 284 * befs_find_brun_indirect - find a block run in the datastream 285 * @sb: the superblock 286 * @data: the datastream 287 * @blockno: the blocknumber to find 288 * @run: The found run is passed back through this pointer 289 * 290 * Finds the block run that starts at file block number blockno 291 * in the file represented by the datastream data, if that 292 * blockno is in the indirect region of the datastream. 293 * 294 * Return value is BEFS_OK if the blockrun is found, BEFS_ERR 295 * otherwise. 296 * 297 * Algorithm: 298 * For each block in the indirect run of the datastream, read 299 * it in and search through it for search_blk. 300 * 301 * XXX: 302 * Really should check to make sure blockno is inside indirect 303 * region. 304 */ 305 static int 306 befs_find_brun_indirect(struct super_block *sb, 307 const befs_data_stream *data, 308 befs_blocknr_t blockno, 309 befs_block_run *run) 310 { 311 int i, j; 312 befs_blocknr_t sum = 0; 313 befs_blocknr_t indir_start_blk; 314 befs_blocknr_t search_blk; 315 struct buffer_head *indirblock; 316 befs_disk_block_run *array; 317 318 befs_block_run indirect = data->indirect; 319 befs_blocknr_t indirblockno = iaddr2blockno(sb, &indirect); 320 int arraylen = befs_iaddrs_per_block(sb); 321 322 befs_debug(sb, "---> %s, find %lu", __func__, (unsigned long)blockno); 323 324 indir_start_blk = data->max_direct_range >> BEFS_SB(sb)->block_shift; 325 search_blk = blockno - indir_start_blk; 326 327 /* Examine blocks of the indirect run one at a time */ 328 for (i = 0; i < indirect.len; i++) { 329 indirblock = sb_bread(sb, indirblockno + i); 330 if (indirblock == NULL) { 331 befs_error(sb, "---> %s failed to read " 332 "disk block %lu from the indirect brun", 333 __func__, (unsigned long)indirblockno + i); 334 befs_debug(sb, "<--- %s ERROR", __func__); 335 return BEFS_ERR; 336 } 337 338 array = (befs_disk_block_run *) indirblock->b_data; 339 340 for (j = 0; j < arraylen; ++j) { 341 int len = fs16_to_cpu(sb, array[j].len); 342 343 if (search_blk >= sum && search_blk < sum + len) { 344 int offset = search_blk - sum; 345 run->allocation_group = 346 fs32_to_cpu(sb, array[j].allocation_group); 347 run->start = 348 fs16_to_cpu(sb, array[j].start) + offset; 349 run->len = 350 fs16_to_cpu(sb, array[j].len) - offset; 351 352 brelse(indirblock); 353 befs_debug(sb, 354 "<--- %s found file block " 355 "%lu at indirect[%d]", __func__, 356 (unsigned long)blockno, 357 j + (i * arraylen)); 358 return BEFS_OK; 359 } 360 sum += len; 361 } 362 363 brelse(indirblock); 364 } 365 366 /* Only fallthrough is an error */ 367 befs_error(sb, "BeFS: %s failed to find " 368 "file block %lu", __func__, (unsigned long)blockno); 369 370 befs_debug(sb, "<--- %s ERROR", __func__); 371 return BEFS_ERR; 372 } 373 374 /** 375 * befs_find_brun_dblindirect - find a block run in the datastream 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 * Finds the block run that starts at file block number blockno 382 * in the file represented by the datastream data, if that 383 * blockno is in the double-indirect region of the datastream. 384 * 385 * Return value is BEFS_OK if the blockrun is found, BEFS_ERR 386 * otherwise. 387 * 388 * Algorithm: 389 * The block runs in the double-indirect region are different. 390 * They are always allocated 4 fs blocks at a time, so each 391 * block run maps a constant amount of file data. This means 392 * that we can directly calculate how many block runs into the 393 * double-indirect region we need to go to get to the one that 394 * maps a particular filesystem block. 395 * 396 * We do this in two stages. First we calculate which of the 397 * inode addresses in the double-indirect block will point us 398 * to the indirect block that contains the mapping for the data, 399 * then we calculate which of the inode addresses in that 400 * indirect block maps the data block we are after. 401 * 402 * Oh, and once we've done that, we actually read in the blocks 403 * that contain the inode addresses we calculated above. Even 404 * though the double-indirect run may be several blocks long, 405 * we can calculate which of those blocks will contain the index 406 * we are after and only read that one. We then follow it to 407 * the indirect block and perform a similar process to find 408 * the actual block run that maps the data block we are interested 409 * in. 410 * 411 * Then we offset the run as in befs_find_brun_array() and we are 412 * done. 413 */ 414 static int 415 befs_find_brun_dblindirect(struct super_block *sb, 416 const befs_data_stream *data, 417 befs_blocknr_t blockno, 418 befs_block_run *run) 419 { 420 int dblindir_indx; 421 int indir_indx; 422 int offset; 423 int dbl_which_block; 424 int which_block; 425 int dbl_block_indx; 426 int block_indx; 427 off_t dblindir_leftover; 428 befs_blocknr_t blockno_at_run_start; 429 struct buffer_head *dbl_indir_block; 430 struct buffer_head *indir_block; 431 befs_block_run indir_run; 432 befs_disk_inode_addr *iaddr_array; 433 434 befs_blocknr_t indir_start_blk = 435 data->max_indirect_range >> BEFS_SB(sb)->block_shift; 436 437 off_t dbl_indir_off = blockno - indir_start_blk; 438 439 /* number of data blocks mapped by each of the iaddrs in 440 * the indirect block pointed to by the double indirect block 441 */ 442 size_t iblklen = BEFS_DBLINDIR_BRUN_LEN; 443 444 /* number of data blocks mapped by each of the iaddrs in 445 * the double indirect block 446 */ 447 size_t diblklen = iblklen * befs_iaddrs_per_block(sb) 448 * BEFS_DBLINDIR_BRUN_LEN; 449 450 befs_debug(sb, "---> %s find %lu", __func__, (unsigned long)blockno); 451 452 /* First, discover which of the double_indir->indir blocks 453 * contains pos. Then figure out how much of pos that 454 * accounted for. Then discover which of the iaddrs in 455 * the indirect block contains pos. 456 */ 457 458 dblindir_indx = dbl_indir_off / diblklen; 459 dblindir_leftover = dbl_indir_off % diblklen; 460 indir_indx = dblindir_leftover / diblklen; 461 462 /* Read double indirect block */ 463 dbl_which_block = dblindir_indx / befs_iaddrs_per_block(sb); 464 if (dbl_which_block > data->double_indirect.len) { 465 befs_error(sb, "The double-indirect index calculated by " 466 "%s, %d, is outside the range " 467 "of the double-indirect block", __func__, 468 dblindir_indx); 469 return BEFS_ERR; 470 } 471 472 dbl_indir_block = 473 sb_bread(sb, iaddr2blockno(sb, &data->double_indirect) + 474 dbl_which_block); 475 if (dbl_indir_block == NULL) { 476 befs_error(sb, "%s couldn't read the " 477 "double-indirect block at blockno %lu", __func__, 478 (unsigned long) 479 iaddr2blockno(sb, &data->double_indirect) + 480 dbl_which_block); 481 return BEFS_ERR; 482 } 483 484 dbl_block_indx = 485 dblindir_indx - (dbl_which_block * befs_iaddrs_per_block(sb)); 486 iaddr_array = (befs_disk_inode_addr *) dbl_indir_block->b_data; 487 indir_run = fsrun_to_cpu(sb, iaddr_array[dbl_block_indx]); 488 brelse(dbl_indir_block); 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 "%s, %d, is outside the range " 495 "of the indirect block", __func__, indir_indx); 496 return BEFS_ERR; 497 } 498 499 indir_block = 500 sb_bread(sb, iaddr2blockno(sb, &indir_run) + which_block); 501 if (indir_block == NULL) { 502 befs_error(sb, "%s couldn't read the indirect block " 503 "at blockno %lu", __func__, (unsigned long) 504 iaddr2blockno(sb, &indir_run) + which_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 513 blockno_at_run_start = indir_start_blk; 514 blockno_at_run_start += diblklen * dblindir_indx; 515 blockno_at_run_start += iblklen * indir_indx; 516 offset = blockno - blockno_at_run_start; 517 518 run->start += offset; 519 run->len -= offset; 520 521 befs_debug(sb, "Found file block %lu in double_indirect[%d][%d]," 522 " double_indirect_leftover = %lu", (unsigned long) 523 blockno, dblindir_indx, indir_indx, dblindir_leftover); 524 525 return BEFS_OK; 526 } 527