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