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: 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, 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 * 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, const 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, " 108 "which is not mapped by the datastream\n", 109 (unsigned long)fblock); 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 119 * @buff: Buffer in which to place long symlink data 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, const befs_data_stream *ds, 126 void *buff, befs_off_t len) 127 { 128 befs_off_t bytes_read = 0; /* bytes readed */ 129 u16 plen; 130 struct buffer_head *bh; 131 befs_debug(sb, "---> %s length: %llu", __func__, len); 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 " 137 "starting from %llu", bytes_read); 138 befs_debug(sb, "<--- %s ERROR", __func__); 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 149 befs_debug(sb, "<--- %s read %u bytes", __func__, (unsigned int) 150 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, const 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 struct befs_sb_info *befs_sb = BEFS_SB(sb); 172 173 befs_debug(sb, "---> %s", __func__); 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, "<--- %s %u blocks", __func__, (unsigned int)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 length 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, const befs_data_stream *data, 247 befs_blocknr_t blockno, befs_block_run * run) 248 { 249 int i; 250 const 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, "---> %s, find %lu", __func__, (unsigned long)blockno); 256 257 if (blockno > max_block) { 258 befs_error(sb, "%s passed block outside of direct region", 259 __func__); 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, "---> %s, " 272 "found %lu at direct[%d]", __func__, 273 (unsigned long)blockno, i); 274 return BEFS_OK; 275 } 276 } 277 278 befs_debug(sb, "---> %s ERROR", __func__); 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 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 = befs_bread(sb, indirblockno + i); 330 if (indirblock == NULL) { 331 befs_debug(sb, "---> %s failed to read " 332 "disk block %lu from the indirect brun", 333 __func__, (unsigned long)indirblockno + i); 334 return BEFS_ERR; 335 } 336 337 array = (befs_disk_block_run *) indirblock->b_data; 338 339 for (j = 0; j < arraylen; ++j) { 340 int len = fs16_to_cpu(sb, array[j].len); 341 342 if (search_blk >= sum && search_blk < sum + len) { 343 int offset = search_blk - sum; 344 run->allocation_group = 345 fs32_to_cpu(sb, array[j].allocation_group); 346 run->start = 347 fs16_to_cpu(sb, array[j].start) + offset; 348 run->len = 349 fs16_to_cpu(sb, array[j].len) - offset; 350 351 brelse(indirblock); 352 befs_debug(sb, 353 "<--- %s found file block " 354 "%lu at indirect[%d]", __func__, 355 (unsigned long)blockno, 356 j + (i * arraylen)); 357 return BEFS_OK; 358 } 359 sum += len; 360 } 361 362 brelse(indirblock); 363 } 364 365 /* Only fallthrough is an error */ 366 befs_error(sb, "BeFS: %s failed to find " 367 "file block %lu", __func__, (unsigned long)blockno); 368 369 befs_debug(sb, "<--- %s ERROR", __func__); 370 return BEFS_ERR; 371 } 372 373 /* 374 Finds the block run that starts at file block number blockno 375 in the file represented by the datastream data, if that 376 blockno is in the double-indirect region of the datastream. 377 378 sb: the superblock 379 data: the datastream 380 blockno: the blocknumber to find 381 run: The found run is passed back through this pointer 382 383 Return value is BEFS_OK if the blockrun is found, BEFS_ERR 384 otherwise. 385 386 Algorithm: 387 The block runs in the double-indirect region are different. 388 They are always allocated 4 fs blocks at a time, so each 389 block run maps a constant amount of file data. This means 390 that we can directly calculate how many block runs into the 391 double-indirect region we need to go to get to the one that 392 maps a particular filesystem block. 393 394 We do this in two stages. First we calculate which of the 395 inode addresses in the double-indirect block will point us 396 to the indirect block that contains the mapping for the data, 397 then we calculate which of the inode addresses in that 398 indirect block maps the data block we are after. 399 400 Oh, and once we've done that, we actually read in the blocks 401 that contain the inode addresses we calculated above. Even 402 though the double-indirect run may be several blocks long, 403 we can calculate which of those blocks will contain the index 404 we are after and only read that one. We then follow it to 405 the indirect block and perform a similar process to find 406 the actual block run that maps the data block we are interested 407 in. 408 409 Then we offset the run as in befs_find_brun_array() and we are 410 done. 411 412 2001-11-15 Will Dyson 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 struct befs_sb_info *befs_sb = BEFS_SB(sb); 434 435 befs_blocknr_t indir_start_blk = 436 data->max_indirect_range >> befs_sb->block_shift; 437 438 off_t dbl_indir_off = blockno - indir_start_blk; 439 440 /* number of data blocks mapped by each of the iaddrs in 441 * the indirect block pointed to by the double indirect block 442 */ 443 size_t iblklen = BEFS_DBLINDIR_BRUN_LEN; 444 445 /* number of data blocks mapped by each of the iaddrs in 446 * the double indirect block 447 */ 448 size_t diblklen = iblklen * befs_iaddrs_per_block(sb) 449 * BEFS_DBLINDIR_BRUN_LEN; 450 451 befs_debug(sb, "---> %s find %lu", __func__, (unsigned long)blockno); 452 453 /* First, discover which of the double_indir->indir blocks 454 * contains pos. Then figure out how much of pos that 455 * accounted for. Then discover which of the iaddrs in 456 * the indirect block contains pos. 457 */ 458 459 dblindir_indx = dbl_indir_off / diblklen; 460 dblindir_leftover = dbl_indir_off % diblklen; 461 indir_indx = dblindir_leftover / diblklen; 462 463 /* Read double indirect block */ 464 dbl_which_block = dblindir_indx / befs_iaddrs_per_block(sb); 465 if (dbl_which_block > data->double_indirect.len) { 466 befs_error(sb, "The double-indirect index calculated by " 467 "%s, %d, is outside the range " 468 "of the double-indirect block", __func__, 469 dblindir_indx); 470 return BEFS_ERR; 471 } 472 473 dbl_indir_block = 474 befs_bread(sb, iaddr2blockno(sb, &data->double_indirect) + 475 dbl_which_block); 476 if (dbl_indir_block == NULL) { 477 befs_error(sb, "%s couldn't read the " 478 "double-indirect block at blockno %lu", __func__, 479 (unsigned long) 480 iaddr2blockno(sb, &data->double_indirect) + 481 dbl_which_block); 482 brelse(dbl_indir_block); 483 return BEFS_ERR; 484 } 485 486 dbl_block_indx = 487 dblindir_indx - (dbl_which_block * befs_iaddrs_per_block(sb)); 488 iaddr_array = (befs_disk_inode_addr *) dbl_indir_block->b_data; 489 indir_run = fsrun_to_cpu(sb, iaddr_array[dbl_block_indx]); 490 brelse(dbl_indir_block); 491 492 /* Read indirect block */ 493 which_block = indir_indx / befs_iaddrs_per_block(sb); 494 if (which_block > indir_run.len) { 495 befs_error(sb, "The indirect index calculated by " 496 "%s, %d, is outside the range " 497 "of the indirect block", __func__, indir_indx); 498 return BEFS_ERR; 499 } 500 501 indir_block = 502 befs_bread(sb, iaddr2blockno(sb, &indir_run) + which_block); 503 if (indir_block == NULL) { 504 befs_error(sb, "%s couldn't read the indirect block " 505 "at blockno %lu", __func__, (unsigned long) 506 iaddr2blockno(sb, &indir_run) + which_block); 507 brelse(indir_block); 508 return BEFS_ERR; 509 } 510 511 block_indx = indir_indx - (which_block * befs_iaddrs_per_block(sb)); 512 iaddr_array = (befs_disk_inode_addr *) indir_block->b_data; 513 *run = fsrun_to_cpu(sb, iaddr_array[block_indx]); 514 brelse(indir_block); 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]," 525 " double_indirect_leftover = %lu", (unsigned long) 526 blockno, dblindir_indx, indir_indx, dblindir_leftover); 527 528 return BEFS_OK; 529 } 530