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