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