1 /* 2 * Copyright 2001-2011, Haiku Inc. All rights reserved. 3 * This file may be used under the terms of the MIT License. 4 * 5 * Authors: 6 * Jérôme Duval 7 */ 8 9 10 #include "ExtentStream.h" 11 12 #include <string.h> 13 14 #include "CachedBlock.h" 15 #include "Inode.h" 16 #include "Volume.h" 17 18 19 #undef ASSERT 20 //#define TRACE_EXT2 21 #ifdef TRACE_EXT2 22 # define TRACE(x...) dprintf("\33[34mext2:\33[0m ExtentStream::" x) 23 # define ASSERT(x) { if (!(x)) kernel_debugger("ext2: assert failed: " #x "\n"); } 24 #else 25 # define TRACE(x...) ; 26 # define ASSERT(x) ; 27 #endif 28 #define ERROR(x...) dprintf("\33[34mext2:\33[0m ExtentStream::" x) 29 30 31 ExtentStream::ExtentStream(Volume* volume, Inode* inode, 32 ext2_extent_stream* stream, off_t size) 33 : 34 fVolume(volume), 35 fInode(inode), 36 fStream(stream), 37 fFirstBlock(volume->FirstDataBlock()), 38 fAllocatedPos(fFirstBlock), 39 fSize(size) 40 { 41 fNumBlocks = size == 0 ? 0 : ((size - 1) >> fVolume->BlockShift()) + 1; 42 } 43 44 45 ExtentStream::~ExtentStream() 46 { 47 } 48 49 50 status_t 51 ExtentStream::FindBlock(off_t offset, fsblock_t& block, uint32 *_count) 52 { 53 fileblock_t index = offset >> fVolume->BlockShift(); 54 TRACE("FindBlock(%" B_PRIdOFF ", %" B_PRIu64 ")\n", offset, index); 55 56 if (offset >= fSize) { 57 TRACE("FindBlock: offset larger than inode size\n"); 58 return B_ENTRY_NOT_FOUND; 59 } 60 61 ext2_extent_stream *stream = fStream; 62 if (!stream->extent_header.IsValid()) 63 panic("ExtentStream::FindBlock() invalid header\n"); 64 65 CachedBlock cached(fVolume); 66 while (stream->extent_header.Depth() != 0) { 67 TRACE("FindBlock() depth %d\n", 68 stream->extent_header.Depth()); 69 int32 i = 1; 70 while (i < stream->extent_header.NumEntries() 71 && stream->extent_index[i].LogicalBlock() <= index) { 72 i++; 73 } 74 TRACE("FindBlock() getting index %" B_PRId32 " at %" B_PRIu64 "\n", 75 i - 1, stream->extent_index[i - 1].PhysicalBlock()); 76 stream = (ext2_extent_stream *)cached.SetTo( 77 stream->extent_index[i - 1].PhysicalBlock()); 78 if (!stream->extent_header.IsValid()) 79 panic("ExtentStream::FindBlock() invalid header\n"); 80 if (!fInode->VerifyExtentChecksum(stream)) { 81 panic("ExtentStream::FindBlock() invalid checksum\n"); 82 return B_BAD_DATA; 83 } 84 } 85 86 // find the extend following the one that should contain the logical block 87 int32 extentIndex; 88 if (stream->extent_header.NumEntries() > 7) { 89 // binary search when enough entries 90 int32 low = 0; 91 int32 high = stream->extent_header.NumEntries() - 1; 92 while (low < high) { 93 int32 middle = (high + low + 1) / 2; 94 if (stream->extent_entries[middle].LogicalBlock() > index) 95 high = middle - 1; 96 else 97 low = middle; 98 } 99 100 extentIndex = low + 1; 101 } else { 102 extentIndex = stream->extent_header.NumEntries(); 103 for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) { 104 if (stream->extent_entries[i].LogicalBlock() > index) { 105 extentIndex = i; 106 break; 107 } 108 } 109 } 110 111 fileblock_t logicalEndIndex 112 = (fSize + fVolume->BlockSize() - 1) >> fVolume->BlockShift(); 113 114 if (extentIndex == 0) { 115 // sparse block at the beginning of the stream 116 block = 0; 117 if (_count != NULL) { 118 *_count = stream->extent_header.NumEntries() == 0 119 ? logicalEndIndex - index 120 : stream->extent_entries[0].LogicalBlock() - index; 121 } 122 TRACE("FindBlock() sparse block index %" B_PRIu64 " at beginning of " 123 "stream\n", index); 124 return B_OK; 125 } 126 127 const ext2_extent_entry& extent = stream->extent_entries[extentIndex - 1]; 128 // the extent supposedly containing the offset 129 fileblock_t diff = index - extent.LogicalBlock(); 130 if (diff >= extent.Length()) { 131 // sparse block between extends or at the end of the stream 132 TRACE("FindBlock() sparse block index %" B_PRIu64 " at %" B_PRIu32 133 "\n", index, extent.LogicalBlock()); 134 block = 0; 135 if (_count != NULL) { 136 *_count = stream->extent_header.NumEntries() == extentIndex 137 ? logicalEndIndex - index 138 : stream->extent_entries[extentIndex].LogicalBlock() - index; 139 } 140 return B_OK; 141 } 142 143 block = extent.PhysicalBlock() + diff; 144 if (_count != NULL) 145 *_count = extent.Length() - diff; 146 147 TRACE("FindBlock(offset %" B_PRIdOFF "): %" B_PRIu64 " %" B_PRIu32 148 "\n", offset, block, _count != NULL ? *_count : 1); 149 150 return B_OK; 151 } 152 153 154 status_t 155 ExtentStream::Enlarge(Transaction& transaction, off_t& numBlocks) 156 { 157 TRACE("Enlarge(): current size: %" B_PRIdOFF ", target size: %" B_PRIdOFF 158 "\n", fNumBlocks, numBlocks); 159 160 off_t targetBlocks = numBlocks; 161 numBlocks = targetBlocks - fNumBlocks; 162 uint32 allocated = 0; 163 164 while (fNumBlocks < targetBlocks) { 165 // allocate new blocks 166 uint32 blockGroup = (fAllocatedPos - fFirstBlock) 167 / fVolume->BlocksPerGroup(); 168 169 if (allocated == 0) { 170 status_t status = fVolume->AllocateBlocks(transaction, 1, 171 targetBlocks - fNumBlocks, blockGroup, fAllocatedPos, 172 allocated); 173 if (status != B_OK) { 174 ERROR("Enlarge(): AllocateBlocks() failed()\n"); 175 return status; 176 } 177 } 178 179 ASSERT(_CheckBlock(fStream, fAllocatedPos) == B_OK); 180 181 ext2_extent_stream *stream = fStream; 182 fsblock_t path[stream->extent_header.Depth()]; 183 184 // search for the leaf 185 CachedBlock cached(fVolume); 186 int32 level = -1; 187 for (; stream->extent_header.Depth() != 0;) { 188 if (stream->extent_header.NumEntries() == 0) 189 panic("stream->extent_header.NumEntries() == 0\n"); 190 int32 lastIndex = stream->extent_header.NumEntries() - 1; 191 TRACE("Enlarge() depth %d\n", stream->extent_header.Depth()); 192 TRACE("Enlarge() getting index %" B_PRId32 " at %" B_PRIu64 "\n", 193 lastIndex, stream->extent_index[lastIndex].PhysicalBlock()); 194 path[++level] = stream->extent_index[lastIndex].PhysicalBlock(); 195 stream = (ext2_extent_stream *)cached.SetTo(path[level]); 196 if (stream == NULL) 197 return B_IO_ERROR; 198 } 199 200 // check if the new extent is adjacent 201 if (stream->extent_header.NumEntries() > 0) { 202 ext2_extent_entry &last = stream->extent_entries[ 203 stream->extent_header.NumEntries() - 1]; 204 TRACE("Enlarge() last %" B_PRIu64 " allocatedPos %" B_PRIu64 "\n", 205 last.PhysicalBlock() + last.Length(), fAllocatedPos); 206 if (last.PhysicalBlock() + last.Length() == fAllocatedPos 207 && (last.Length() + allocated) <= EXT2_EXTENT_MAX_LENGTH) { 208 if (stream != fStream) { 209 stream = (ext2_extent_stream *)cached.SetToWritable( 210 transaction, cached.BlockNumber()); 211 if (stream == NULL) 212 return B_IO_ERROR; 213 } 214 stream->extent_entries[stream->extent_header.NumEntries() - 1] 215 .SetLength(last.Length() + allocated); 216 fInode->SetExtentChecksum(stream); 217 fNumBlocks += allocated; 218 allocated = 0; 219 TRACE("Enlarge() entry extended\n"); 220 continue; 221 } 222 } 223 224 if (stream->extent_header.NumEntries() 225 >= stream->extent_header.MaxEntries()) { 226 TRACE("Enlarge() adding leaf and indexes at depth %d level %" 227 B_PRId32 "\n", stream->extent_header.Depth(), level); 228 // try to add a leaf and indexes 229 while (--level >= 0) { 230 stream = (ext2_extent_stream *)cached.SetTo(path[level]); 231 if (stream == NULL) 232 return B_IO_ERROR; 233 if (stream->extent_header.NumEntries() 234 < stream->extent_header.MaxEntries()) { 235 break; 236 } 237 TRACE("Enlarge() going up from level %" B_PRId32 "\n", level); 238 } 239 240 if (level < 0 && fStream->extent_header.NumEntries() 241 >= fStream->extent_header.MaxEntries()) { 242 TRACE("Enlarge() add a level, increment root depth\n"); 243 fsblock_t newBlock = fStream->extent_index[0].PhysicalBlock(); 244 uint32 _allocated; 245 status_t status = fVolume->AllocateBlocks(transaction, 1, 1, 246 blockGroup, newBlock, _allocated); 247 if (status != B_OK) { 248 ERROR("Enlarge() AllocateBlocks() failed()\n"); 249 return status; 250 } 251 ASSERT(_CheckBlock(fStream, newBlock) == B_OK); 252 TRACE("Enlarge() move root to block %" B_PRIu64 "\n", 253 newBlock); 254 numBlocks++; 255 stream = (ext2_extent_stream *)cached.SetToWritable( 256 transaction, newBlock); 257 if (stream == NULL) 258 return B_IO_ERROR; 259 ASSERT(fStream->extent_header.IsValid()); 260 memcpy(stream, fStream, sizeof(ext2_extent_stream)); 261 fStream->extent_header.SetDepth(stream->extent_header.Depth() 262 + 1); 263 TRACE("Enlarge() new root depth %d\n", 264 fStream->extent_header.Depth()); 265 fStream->extent_header.SetNumEntries(1); 266 fStream->extent_index[0].SetLogicalBlock(0); 267 fStream->extent_index[0].SetPhysicalBlock(newBlock); 268 stream->extent_header.SetMaxEntries((fVolume->BlockSize() 269 - sizeof(ext2_extent_header)) / sizeof(ext2_extent_index)); 270 fInode->SetExtentChecksum(stream); 271 ASSERT(stream->extent_header.IsValid()); 272 273 ASSERT(Check()); 274 continue; 275 } 276 277 if (level < 0) 278 stream = fStream; 279 280 uint16 depth = stream->extent_header.Depth(); 281 while (depth > 1) { 282 TRACE("Enlarge() adding an index block at depth %d\n", depth); 283 fsblock_t newBlock = path[level]; 284 uint32 _allocated; 285 status_t status = fVolume->AllocateBlocks(transaction, 1, 1, 286 blockGroup, newBlock, _allocated); 287 if (status != B_OK) { 288 ERROR("Enlarge(): AllocateBlocks() failed()\n"); 289 return status; 290 } 291 ASSERT(_CheckBlock(fStream, newBlock) == B_OK); 292 numBlocks++; 293 int32 index = stream->extent_header.NumEntries(); 294 stream->extent_index[index].SetLogicalBlock(fNumBlocks); 295 stream->extent_index[index].SetPhysicalBlock(newBlock); 296 stream->extent_header.SetNumEntries(index + 1); 297 fInode->SetExtentChecksum(stream); 298 path[level++] = newBlock; 299 300 depth = stream->extent_header.Depth() - 1; 301 TRACE("Enlarge() init index block %" B_PRIu64 " at depth %d\n", 302 newBlock, depth); 303 stream = (ext2_extent_stream *)cached.SetToWritable( 304 transaction, newBlock); 305 if (stream == NULL) 306 return B_IO_ERROR; 307 stream->extent_header.magic = EXT2_EXTENT_MAGIC; 308 stream->extent_header.SetNumEntries(0); 309 stream->extent_header.SetMaxEntries((fVolume->BlockSize() 310 - sizeof(ext2_extent_header)) / sizeof(ext2_extent_index)); 311 stream->extent_header.SetDepth(depth); 312 stream->extent_header.SetGeneration(0); 313 fInode->SetExtentChecksum(stream); 314 315 ASSERT(Check()); 316 } 317 318 TRACE("Enlarge() depth %d level %" B_PRId32 "\n", 319 stream->extent_header.Depth(), level); 320 321 if (stream->extent_header.Depth() == 1) { 322 TRACE("Enlarge() adding an entry block at depth %d level %" 323 B_PRId32 "\n", depth, level); 324 fsblock_t newBlock; 325 if (level >= 0) 326 newBlock = path[level]; 327 else 328 newBlock = fStream->extent_index[0].PhysicalBlock(); 329 uint32 _allocated; 330 status_t status = fVolume->AllocateBlocks(transaction, 1, 1, 331 blockGroup, newBlock, _allocated); 332 if (status != B_OK) { 333 ERROR("Enlarge(): AllocateBlocks() failed()\n"); 334 return status; 335 } 336 337 ASSERT(_CheckBlock(fStream, newBlock) == B_OK); 338 numBlocks++; 339 int32 index = stream->extent_header.NumEntries(); 340 stream->extent_index[index].SetLogicalBlock(fNumBlocks); 341 stream->extent_index[index].SetPhysicalBlock(newBlock); 342 stream->extent_header.SetNumEntries(index + 1); 343 fInode->SetExtentChecksum(stream); 344 345 TRACE("Enlarge() init entry block %" B_PRIu64 346 " at depth %d\n", newBlock, depth); 347 stream = (ext2_extent_stream *)cached.SetToWritable( 348 transaction, newBlock); 349 if (stream == NULL) 350 return B_IO_ERROR; 351 stream->extent_header.magic = EXT2_EXTENT_MAGIC; 352 stream->extent_header.SetNumEntries(0); 353 stream->extent_header.SetMaxEntries((fVolume->BlockSize() 354 - sizeof(ext2_extent_header)) / sizeof(ext2_extent_entry)); 355 stream->extent_header.SetDepth(0); 356 stream->extent_header.SetGeneration(0); 357 fInode->SetExtentChecksum(stream); 358 ASSERT(Check()); 359 } 360 } 361 362 // add a new entry 363 TRACE("Enlarge() add entry %" B_PRIu64 "\n", fAllocatedPos); 364 if (stream != fStream) { 365 stream = (ext2_extent_stream *)cached.SetToWritable( 366 transaction, cached.BlockNumber()); 367 if (stream == NULL) 368 return B_IO_ERROR; 369 } 370 int32 index = stream->extent_header.NumEntries(); 371 stream->extent_entries[index].SetLogicalBlock(fNumBlocks); 372 stream->extent_entries[index].SetLength(allocated); 373 stream->extent_entries[index].SetPhysicalBlock(fAllocatedPos); 374 stream->extent_header.SetNumEntries(index + 1); 375 fInode->SetExtentChecksum(stream); 376 TRACE("Enlarge() entry added at index %" B_PRId32 "\n", index); 377 ASSERT(stream->extent_header.IsValid()); 378 379 fNumBlocks += allocated; 380 allocated = 0; 381 } 382 383 return B_OK; 384 } 385 386 387 status_t 388 ExtentStream::Shrink(Transaction& transaction, off_t& numBlocks) 389 { 390 TRACE("DataStream::Shrink(): current size: %" B_PRIdOFF ", target size: %" 391 B_PRIdOFF "\n", fNumBlocks, numBlocks); 392 393 off_t targetBlocks = numBlocks; 394 numBlocks = fNumBlocks - targetBlocks; 395 396 while (targetBlocks < fNumBlocks) { 397 ext2_extent_stream *stream = fStream; 398 fsblock_t path[stream->extent_header.Depth()]; 399 400 // search for the leaf 401 CachedBlock cached(fVolume); 402 int32 level = -1; 403 for (; stream->extent_header.Depth() != 0;) { 404 if (stream->extent_header.NumEntries() == 0) 405 panic("stream->extent_header.NumEntries() == 0\n"); 406 int32 lastIndex = stream->extent_header.NumEntries() - 1; 407 TRACE("Shrink() depth %d\n", stream->extent_header.Depth()); 408 TRACE("Shrink() getting index %" B_PRId32 " at %" B_PRIu64 "\n", 409 lastIndex, stream->extent_index[lastIndex].PhysicalBlock()); 410 path[++level] = stream->extent_index[lastIndex].PhysicalBlock(); 411 stream = (ext2_extent_stream *)cached.SetToWritable(transaction, 412 path[level]); 413 if (stream == NULL) 414 return B_IO_ERROR; 415 if (!stream->extent_header.IsValid()) 416 panic("Shrink() invalid header\n"); 417 } 418 419 int32 index = stream->extent_header.NumEntries() - 1; 420 status_t status = B_OK; 421 while (index >= 0 && targetBlocks < fNumBlocks) { 422 ext2_extent_entry &last = stream->extent_entries[index]; 423 if (last.LogicalBlock() + last.Length() < targetBlocks) { 424 status = B_BAD_DATA; 425 break; 426 } 427 uint16 length = min_c(last.Length(), fNumBlocks - targetBlocks); 428 fsblock_t block = last.PhysicalBlock() + last.Length() - length; 429 TRACE("Shrink() free block %" B_PRIu64 " length %d\n", block, 430 length); 431 status = fVolume->FreeBlocks(transaction, block, length); 432 if (status != B_OK) 433 break; 434 fNumBlocks -= length; 435 stream->extent_entries[index].SetLength(last.Length() - length); 436 TRACE("Shrink() new length for %" B_PRId32 ": %d\n", index, last.Length()); 437 if (last.Length() != 0) 438 break; 439 index--; 440 TRACE("Shrink() next index: %" B_PRId32 "\n", index); 441 } 442 TRACE("Shrink() new entry count: %" B_PRId32 "\n", index + 1); 443 stream->extent_header.SetNumEntries(index + 1); 444 fInode->SetExtentChecksum(stream); 445 ASSERT(Check()); 446 447 if (status != B_OK) 448 return status; 449 450 while (stream != fStream && stream->extent_header.NumEntries() == 0) { 451 TRACE("Shrink() empty leaf at depth %d\n", 452 stream->extent_header.Depth()); 453 level--; 454 if (level >= 0) { 455 stream = (ext2_extent_stream *)cached.SetToWritable( 456 transaction, path[level]); 457 if (stream == NULL) 458 return B_IO_ERROR; 459 } else 460 stream = fStream; 461 if (!stream->extent_header.IsValid()) 462 panic("Shrink() invalid header\n"); 463 uint16 index = stream->extent_header.NumEntries() - 1; 464 ext2_extent_index &last = stream->extent_index[index]; 465 if (last.PhysicalBlock() != path[level + 1]) 466 panic("Shrink() last.PhysicalBlock() != path[level + 1]\n"); 467 status = fVolume->FreeBlocks(transaction, last.PhysicalBlock(), 1); 468 if (status != B_OK) 469 return status; 470 numBlocks++; 471 stream->extent_header.SetNumEntries(index); 472 fInode->SetExtentChecksum(stream); 473 TRACE("Shrink() new entry count: %d\n", index); 474 } 475 if (stream == fStream && stream->extent_header.NumEntries() == 0) 476 stream->extent_header.SetDepth(0); 477 478 ASSERT(Check()); 479 } 480 481 return B_OK; 482 } 483 484 485 void 486 ExtentStream::Init() 487 { 488 fStream->extent_header.magic = EXT2_EXTENT_MAGIC; 489 fStream->extent_header.SetNumEntries(0); 490 fStream->extent_header.SetMaxEntries(4); 491 fStream->extent_header.SetDepth(0); 492 fStream->extent_header.SetGeneration(0); 493 fInode->SetExtentChecksum(fStream); 494 } 495 496 497 status_t 498 ExtentStream::_Check(ext2_extent_stream *stream, fileblock_t &block) 499 { 500 if (!stream->extent_header.IsValid()) { 501 panic("_Check() invalid header\n"); 502 return B_BAD_VALUE; 503 } 504 if (stream->extent_header.Depth() == 0) { 505 for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) { 506 ext2_extent_entry &entry = stream->extent_entries[i]; 507 if (entry.LogicalBlock() < block) { 508 panic("_Check() entry %" B_PRId32 " %" B_PRIu64 " %" B_PRIu32 509 "\n", i, block, entry.LogicalBlock()); 510 return B_BAD_VALUE; 511 } 512 block = entry.LogicalBlock() + entry.Length(); 513 } 514 return B_OK; 515 } 516 517 CachedBlock cached(fVolume); 518 for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) { 519 ext2_extent_index &index = stream->extent_index[i]; 520 if (index.LogicalBlock() < block) { 521 panic("_Check() index %" B_PRId32 " %" B_PRIu64 " %" B_PRIu32 522 "\n", i, block, index.LogicalBlock()); 523 return B_BAD_VALUE; 524 } 525 ext2_extent_stream *child = (ext2_extent_stream *)cached.SetTo( 526 index.PhysicalBlock()); 527 if (child->extent_header.Depth() != (stream->extent_header.Depth() - 1) 528 || _Check(child, block) != B_OK) 529 return B_BAD_VALUE; 530 } 531 return B_OK; 532 } 533 534 535 bool 536 ExtentStream::Check() 537 { 538 fileblock_t block = 0; 539 return _Check(fStream, block) == B_OK; 540 } 541 542 543 status_t 544 ExtentStream::_CheckBlock(ext2_extent_stream *stream, fsblock_t block) 545 { 546 if (stream->extent_header.Depth() == 0) { 547 for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) { 548 ext2_extent_entry &entry = stream->extent_entries[i]; 549 if (entry.PhysicalBlock() <= block 550 && (entry.PhysicalBlock() + entry.Length()) > block) { 551 panic("_CheckBlock() entry %" B_PRId32 " %" B_PRIu64 " %" 552 B_PRIu64 " %d\n", i, block, entry.PhysicalBlock(), 553 entry.Length()); 554 return B_BAD_VALUE; 555 } 556 } 557 return B_OK; 558 } 559 560 CachedBlock cached(fVolume); 561 for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) { 562 ext2_extent_index &index = stream->extent_index[i]; 563 if (index.PhysicalBlock() == block) { 564 panic("_CheckBlock() index %" B_PRId32 " %" B_PRIu64 "\n", i, block); 565 return B_BAD_VALUE; 566 } 567 ext2_extent_stream *child = (ext2_extent_stream *)cached.SetTo( 568 index.PhysicalBlock()); 569 if (child->extent_header.Depth() != (stream->extent_header.Depth() - 1) 570 || _CheckBlock(child, block) != B_OK) 571 return B_BAD_VALUE; 572 } 573 return B_OK; 574 } 575 576