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 fNumBlocks += allocated; 217 allocated = 0; 218 TRACE("Enlarge() entry extended\n"); 219 continue; 220 } 221 } 222 223 if (stream->extent_header.NumEntries() 224 >= stream->extent_header.MaxEntries()) { 225 TRACE("Enlarge() adding leaf and indexes at depth %d level %" 226 B_PRId32 "\n", stream->extent_header.Depth(), level); 227 // try to add a leaf and indexes 228 while (--level >= 0) { 229 stream = (ext2_extent_stream *)cached.SetTo(path[level]); 230 if (stream == NULL) 231 return B_IO_ERROR; 232 if (stream->extent_header.NumEntries() 233 < stream->extent_header.MaxEntries()) { 234 break; 235 } 236 TRACE("Enlarge() going up from level %" B_PRId32 "\n", level); 237 } 238 239 if (level < 0 && fStream->extent_header.NumEntries() 240 >= fStream->extent_header.MaxEntries()) { 241 TRACE("Enlarge() add a level, increment root depth\n"); 242 fsblock_t newBlock = fStream->extent_index[0].PhysicalBlock(); 243 uint32 _allocated; 244 status_t status = fVolume->AllocateBlocks(transaction, 1, 1, 245 blockGroup, newBlock, _allocated); 246 if (status != B_OK) { 247 ERROR("Enlarge() AllocateBlocks() failed()\n"); 248 return status; 249 } 250 ASSERT(_CheckBlock(fStream, newBlock) == B_OK); 251 TRACE("Enlarge() move root to block %" B_PRIu64 "\n", 252 newBlock); 253 numBlocks++; 254 stream = (ext2_extent_stream *)cached.SetToWritable( 255 transaction, newBlock); 256 if (stream == NULL) 257 return B_IO_ERROR; 258 ASSERT(fStream->extent_header.IsValid()); 259 memcpy(stream, fStream, sizeof(ext2_extent_stream)); 260 fStream->extent_header.SetDepth(stream->extent_header.Depth() 261 + 1); 262 TRACE("Enlarge() new root depth %d\n", 263 fStream->extent_header.Depth()); 264 fStream->extent_header.SetNumEntries(1); 265 fStream->extent_index[0].SetLogicalBlock(0); 266 fStream->extent_index[0].SetPhysicalBlock(newBlock); 267 stream->extent_header.SetMaxEntries((fVolume->BlockSize() 268 - sizeof(ext2_extent_header)) / sizeof(ext2_extent_index)); 269 ASSERT(stream->extent_header.IsValid()); 270 271 ASSERT(Check()); 272 continue; 273 } 274 275 if (level < 0) 276 stream = fStream; 277 278 uint16 depth = stream->extent_header.Depth(); 279 while (depth > 1) { 280 TRACE("Enlarge() adding an index block at depth %d\n", depth); 281 fsblock_t newBlock = path[level]; 282 uint32 _allocated; 283 status_t status = fVolume->AllocateBlocks(transaction, 1, 1, 284 blockGroup, newBlock, _allocated); 285 if (status != B_OK) { 286 ERROR("Enlarge(): AllocateBlocks() failed()\n"); 287 return status; 288 } 289 ASSERT(_CheckBlock(fStream, newBlock) == B_OK); 290 numBlocks++; 291 int32 index = stream->extent_header.NumEntries(); 292 stream->extent_index[index].SetLogicalBlock(fNumBlocks); 293 stream->extent_index[index].SetPhysicalBlock(newBlock); 294 stream->extent_header.SetNumEntries(index + 1); 295 path[level++] = newBlock; 296 297 depth = stream->extent_header.Depth() - 1; 298 TRACE("Enlarge() init index block %" B_PRIu64 " at depth %d\n", 299 newBlock, depth); 300 stream = (ext2_extent_stream *)cached.SetToWritable( 301 transaction, newBlock); 302 if (stream == NULL) 303 return B_IO_ERROR; 304 stream->extent_header.magic = EXT2_EXTENT_MAGIC; 305 stream->extent_header.SetNumEntries(0); 306 stream->extent_header.SetMaxEntries((fVolume->BlockSize() 307 - sizeof(ext2_extent_header)) / sizeof(ext2_extent_index)); 308 stream->extent_header.SetDepth(depth); 309 stream->extent_header.SetGeneration(0); 310 311 ASSERT(Check()); 312 } 313 314 TRACE("Enlarge() depth %d level %" B_PRId32 "\n", 315 stream->extent_header.Depth(), level); 316 317 if (stream->extent_header.Depth() == 1) { 318 TRACE("Enlarge() adding an entry block at depth %d level %" 319 B_PRId32 "\n", depth, level); 320 fsblock_t newBlock; 321 if (level >= 0) 322 newBlock = path[level]; 323 else 324 newBlock = fStream->extent_index[0].PhysicalBlock(); 325 uint32 _allocated; 326 status_t status = fVolume->AllocateBlocks(transaction, 1, 1, 327 blockGroup, newBlock, _allocated); 328 if (status != B_OK) { 329 ERROR("Enlarge(): AllocateBlocks() failed()\n"); 330 return status; 331 } 332 333 ASSERT(_CheckBlock(fStream, newBlock) == B_OK); 334 numBlocks++; 335 int32 index = stream->extent_header.NumEntries(); 336 stream->extent_index[index].SetLogicalBlock(fNumBlocks); 337 stream->extent_index[index].SetPhysicalBlock(newBlock); 338 stream->extent_header.SetNumEntries(index + 1); 339 340 TRACE("Enlarge() init entry block %" B_PRIu64 341 " at depth %d\n", newBlock, depth); 342 stream = (ext2_extent_stream *)cached.SetToWritable( 343 transaction, newBlock); 344 if (stream == NULL) 345 return B_IO_ERROR; 346 stream->extent_header.magic = EXT2_EXTENT_MAGIC; 347 stream->extent_header.SetNumEntries(0); 348 stream->extent_header.SetMaxEntries((fVolume->BlockSize() 349 - sizeof(ext2_extent_header)) / sizeof(ext2_extent_entry)); 350 stream->extent_header.SetDepth(0); 351 stream->extent_header.SetGeneration(0); 352 ASSERT(Check()); 353 } 354 } 355 356 // add a new entry 357 TRACE("Enlarge() add entry %" B_PRIu64 "\n", fAllocatedPos); 358 if (stream != fStream) { 359 stream = (ext2_extent_stream *)cached.SetToWritable( 360 transaction, cached.BlockNumber()); 361 if (stream == NULL) 362 return B_IO_ERROR; 363 } 364 int32 index = stream->extent_header.NumEntries(); 365 stream->extent_entries[index].SetLogicalBlock(fNumBlocks); 366 stream->extent_entries[index].SetLength(allocated); 367 stream->extent_entries[index].SetPhysicalBlock(fAllocatedPos); 368 stream->extent_header.SetNumEntries(index + 1); 369 TRACE("Enlarge() entry added at index %" B_PRId32 "\n", index); 370 ASSERT(stream->extent_header.IsValid()); 371 372 fNumBlocks += allocated; 373 allocated = 0; 374 } 375 376 return B_OK; 377 } 378 379 380 status_t 381 ExtentStream::Shrink(Transaction& transaction, off_t& numBlocks) 382 { 383 TRACE("DataStream::Shrink(): current size: %" B_PRIdOFF ", target size: %" 384 B_PRIdOFF "\n", fNumBlocks, numBlocks); 385 386 off_t targetBlocks = numBlocks; 387 numBlocks = fNumBlocks - targetBlocks; 388 389 while (targetBlocks < fNumBlocks) { 390 ext2_extent_stream *stream = fStream; 391 fsblock_t path[stream->extent_header.Depth()]; 392 393 // search for the leaf 394 CachedBlock cached(fVolume); 395 int32 level = -1; 396 for (; stream->extent_header.Depth() != 0;) { 397 if (stream->extent_header.NumEntries() == 0) 398 panic("stream->extent_header.NumEntries() == 0\n"); 399 int32 lastIndex = stream->extent_header.NumEntries() - 1; 400 TRACE("Shrink() depth %d\n", stream->extent_header.Depth()); 401 TRACE("Shrink() getting index %" B_PRId32 " at %" B_PRIu64 "\n", 402 lastIndex, stream->extent_index[lastIndex].PhysicalBlock()); 403 path[++level] = stream->extent_index[lastIndex].PhysicalBlock(); 404 stream = (ext2_extent_stream *)cached.SetToWritable(transaction, 405 path[level]); 406 if (stream == NULL) 407 return B_IO_ERROR; 408 if (!stream->extent_header.IsValid()) 409 panic("Shrink() invalid header\n"); 410 } 411 412 int32 index = stream->extent_header.NumEntries() - 1; 413 status_t status = B_OK; 414 while (index >= 0 && targetBlocks < fNumBlocks) { 415 ext2_extent_entry &last = stream->extent_entries[index]; 416 if (last.LogicalBlock() + last.Length() < targetBlocks) { 417 status = B_BAD_DATA; 418 break; 419 } 420 uint16 length = min_c(last.Length(), fNumBlocks - targetBlocks); 421 fsblock_t block = last.PhysicalBlock() + last.Length() - length; 422 TRACE("Shrink() free block %" B_PRIu64 " length %d\n", block, 423 length); 424 status = fVolume->FreeBlocks(transaction, block, length); 425 if (status != B_OK) 426 break; 427 fNumBlocks -= length; 428 stream->extent_entries[index].SetLength(last.Length() - length); 429 TRACE("Shrink() new length for %" B_PRId32 ": %d\n", index, last.Length()); 430 if (last.Length() != 0) 431 break; 432 index--; 433 TRACE("Shrink() next index: %" B_PRId32 "\n", index); 434 } 435 TRACE("Shrink() new entry count: %" B_PRId32 "\n", index + 1); 436 stream->extent_header.SetNumEntries(index + 1); 437 ASSERT(Check()); 438 439 if (status != B_OK) 440 return status; 441 442 while (stream != fStream && stream->extent_header.NumEntries() == 0) { 443 TRACE("Shrink() empty leaf at depth %d\n", 444 stream->extent_header.Depth()); 445 level--; 446 if (level >= 0) { 447 stream = (ext2_extent_stream *)cached.SetToWritable( 448 transaction, path[level]); 449 if (stream == NULL) 450 return B_IO_ERROR; 451 } else 452 stream = fStream; 453 if (!stream->extent_header.IsValid()) 454 panic("Shrink() invalid header\n"); 455 uint16 index = stream->extent_header.NumEntries() - 1; 456 ext2_extent_index &last = stream->extent_index[index]; 457 if (last.PhysicalBlock() != path[level + 1]) 458 panic("Shrink() last.PhysicalBlock() != path[level + 1]\n"); 459 status = fVolume->FreeBlocks(transaction, last.PhysicalBlock(), 1); 460 if (status != B_OK) 461 return status; 462 numBlocks++; 463 stream->extent_header.SetNumEntries(index); 464 TRACE("Shrink() new entry count: %d\n", index); 465 } 466 if (stream == fStream && stream->extent_header.NumEntries() == 0) 467 stream->extent_header.SetDepth(0); 468 469 ASSERT(Check()); 470 } 471 472 return B_OK; 473 } 474 475 476 void 477 ExtentStream::Init() 478 { 479 fStream->extent_header.magic = EXT2_EXTENT_MAGIC; 480 fStream->extent_header.SetNumEntries(0); 481 fStream->extent_header.SetMaxEntries(4); 482 fStream->extent_header.SetDepth(0); 483 fStream->extent_header.SetGeneration(0); 484 } 485 486 487 status_t 488 ExtentStream::_Check(ext2_extent_stream *stream, fileblock_t &block) 489 { 490 if (!stream->extent_header.IsValid()) { 491 panic("_Check() invalid header\n"); 492 return B_BAD_VALUE; 493 } 494 if (stream->extent_header.Depth() == 0) { 495 for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) { 496 ext2_extent_entry &entry = stream->extent_entries[i]; 497 if (entry.LogicalBlock() < block) { 498 panic("_Check() entry %" B_PRId32 " %" B_PRIu64 " %" B_PRIu32 499 "\n", i, block, entry.LogicalBlock()); 500 return B_BAD_VALUE; 501 } 502 block = entry.LogicalBlock() + entry.Length(); 503 } 504 return B_OK; 505 } 506 507 CachedBlock cached(fVolume); 508 for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) { 509 ext2_extent_index &index = stream->extent_index[i]; 510 if (index.LogicalBlock() < block) { 511 panic("_Check() index %" B_PRId32 " %" B_PRIu64 " %" B_PRIu32 512 "\n", i, block, index.LogicalBlock()); 513 return B_BAD_VALUE; 514 } 515 ext2_extent_stream *child = (ext2_extent_stream *)cached.SetTo( 516 index.PhysicalBlock()); 517 if (child->extent_header.Depth() != (stream->extent_header.Depth() - 1) 518 || _Check(child, block) != B_OK) 519 return B_BAD_VALUE; 520 } 521 return B_OK; 522 } 523 524 525 bool 526 ExtentStream::Check() 527 { 528 fileblock_t block = 0; 529 return _Check(fStream, block) == B_OK; 530 } 531 532 533 status_t 534 ExtentStream::_CheckBlock(ext2_extent_stream *stream, fsblock_t block) 535 { 536 if (stream->extent_header.Depth() == 0) { 537 for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) { 538 ext2_extent_entry &entry = stream->extent_entries[i]; 539 if (entry.PhysicalBlock() <= block 540 && (entry.PhysicalBlock() + entry.Length()) > block) { 541 panic("_CheckBlock() entry %" B_PRId32 " %" B_PRIu64 " %" 542 B_PRIu64 " %d\n", i, block, entry.PhysicalBlock(), 543 entry.Length()); 544 return B_BAD_VALUE; 545 } 546 } 547 return B_OK; 548 } 549 550 CachedBlock cached(fVolume); 551 for (int32 i = 0; i < stream->extent_header.NumEntries(); i++) { 552 ext2_extent_index &index = stream->extent_index[i]; 553 if (index.PhysicalBlock() == block) { 554 panic("_CheckBlock() index %" B_PRId32 " %" B_PRIu64 "\n", i, block); 555 return B_BAD_VALUE; 556 } 557 ext2_extent_stream *child = (ext2_extent_stream *)cached.SetTo( 558 index.PhysicalBlock()); 559 if (child->extent_header.Depth() != (stream->extent_header.Depth() - 1) 560 || _CheckBlock(child, block) != B_OK) 561 return B_BAD_VALUE; 562 } 563 return B_OK; 564 } 565 566