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