1 /* 2 * Copyright 2001-2010, Haiku Inc. All rights reserved. 3 * This file may be used under the terms of the MIT License. 4 * 5 * Authors: 6 * Janito V. Ferreira Filho 7 */ 8 9 10 #include "DataStream.h" 11 12 #include "CachedBlock.h" 13 #include "Volume.h" 14 15 16 //#define TRACE_EXT2 17 #ifdef TRACE_EXT2 18 # define TRACE(x...) dprintf("\33[34mext2:\33[0m " x) 19 #else 20 # define TRACE(x...) ; 21 #endif 22 23 24 DataStream::DataStream(Volume* volume, ext2_data_stream* stream, 25 off_t size) 26 : 27 kBlockSize(volume->BlockSize()), 28 kIndirectsPerBlock(kBlockSize / sizeof(uint32)), 29 kIndirectsPerBlock2(kIndirectsPerBlock * kIndirectsPerBlock), 30 kIndirectsPerBlock3(kIndirectsPerBlock2 * kIndirectsPerBlock), 31 kMaxDirect(EXT2_DIRECT_BLOCKS), 32 kMaxIndirect(kMaxDirect + kIndirectsPerBlock), 33 kMaxDoubleIndirect(kMaxIndirect + kIndirectsPerBlock2), 34 fVolume(volume), 35 fStream(stream), 36 fFirstBlock(volume->FirstDataBlock()), 37 fAllocated(0), 38 fAllocatedPos(fFirstBlock), 39 fWaiting(0), 40 fFreeStart(0), 41 fFreeCount(0), 42 fRemovedBlocks(0) 43 { 44 fNumBlocks = size == 0 ? 0 : (size - 1) / kBlockSize + 1; 45 } 46 47 48 DataStream::~DataStream() 49 { 50 } 51 52 53 status_t 54 DataStream::Enlarge(Transaction& transaction, uint32& numBlocks) 55 { 56 TRACE("DataStream::Enlarge(): current size: %lu, target size: %lu\n", 57 fNumBlocks, numBlocks); 58 59 uint32 targetBlocks = numBlocks; 60 fWaiting = _BlocksNeeded(numBlocks); 61 numBlocks = fWaiting; 62 63 status_t status; 64 65 if (fNumBlocks <= kMaxDirect) { 66 status = _AddForDirectBlocks(transaction, targetBlocks); 67 68 if (status != B_OK) 69 return status; 70 71 TRACE("DataStream::Enlarge(): current size: %lu, target size: %lu\n", 72 fNumBlocks, targetBlocks); 73 74 if (fNumBlocks == targetBlocks) 75 return B_OK; 76 } 77 78 if (fNumBlocks <= kMaxIndirect) { 79 status = _AddForIndirectBlock(transaction, targetBlocks); 80 81 if (status != B_OK) 82 return status; 83 84 TRACE("DataStream::Enlarge(): current size: %lu, target size: %lu\n", 85 fNumBlocks, targetBlocks); 86 87 if (fNumBlocks == targetBlocks) 88 return B_OK; 89 } 90 91 if (fNumBlocks <= kMaxDoubleIndirect) { 92 status = _AddForDoubleIndirectBlock(transaction, targetBlocks); 93 94 if (status != B_OK) 95 return status; 96 97 TRACE("DataStream::Enlarge(): current size: %lu, target size: %lu\n", 98 fNumBlocks, targetBlocks); 99 100 if (fNumBlocks == targetBlocks) 101 return B_OK; 102 } 103 104 TRACE("DataStream::Enlarge(): allocated: %lu, waiting: %lu\n", fAllocated, 105 fWaiting); 106 107 return _AddForTripleIndirectBlock(transaction, targetBlocks); 108 } 109 110 111 status_t 112 DataStream::Shrink(Transaction& transaction, uint32& numBlocks) 113 { 114 TRACE("DataStream::Shrink(): current size: %lu, target size: %lu\n", 115 fNumBlocks, numBlocks); 116 117 fFreeStart = 0; 118 fFreeCount = 0; 119 fRemovedBlocks = 0; 120 121 uint32 oldNumBlocks = fNumBlocks; 122 uint32 blocksToRemove = fNumBlocks - numBlocks; 123 124 status_t status; 125 126 if (numBlocks < kMaxDirect) { 127 status = _RemoveFromDirectBlocks(transaction, numBlocks); 128 129 if (status != B_OK) 130 return status; 131 132 if (fRemovedBlocks == blocksToRemove) { 133 fNumBlocks -= fRemovedBlocks; 134 numBlocks = _BlocksNeeded(oldNumBlocks); 135 136 return _PerformFree(transaction); 137 } 138 } 139 140 if (numBlocks < kMaxIndirect) { 141 status = _RemoveFromIndirectBlock(transaction, numBlocks); 142 143 if (status != B_OK) 144 return status; 145 146 if (fRemovedBlocks == blocksToRemove) { 147 fNumBlocks -= fRemovedBlocks; 148 numBlocks = _BlocksNeeded(oldNumBlocks); 149 150 return _PerformFree(transaction); 151 } 152 } 153 154 if (numBlocks < kMaxDoubleIndirect) { 155 status = _RemoveFromDoubleIndirectBlock(transaction, numBlocks); 156 157 if (status != B_OK) 158 return status; 159 160 if (fRemovedBlocks == blocksToRemove) { 161 fNumBlocks -= fRemovedBlocks; 162 numBlocks = _BlocksNeeded(oldNumBlocks); 163 164 return _PerformFree(transaction); 165 } 166 } 167 168 status = _RemoveFromTripleIndirectBlock(transaction, numBlocks); 169 170 if (status != B_OK) 171 return status; 172 173 fNumBlocks -= fRemovedBlocks; 174 numBlocks = _BlocksNeeded(oldNumBlocks); 175 176 return _PerformFree(transaction); 177 } 178 179 180 uint32 181 DataStream::_BlocksNeeded(uint32 numBlocks) 182 { 183 TRACE("DataStream::BlocksNeeded(): num blocks %lu\n", numBlocks); 184 uint32 blocksNeeded = 0; 185 186 if (numBlocks > fNumBlocks) { 187 blocksNeeded += numBlocks - fNumBlocks; 188 189 if (numBlocks > kMaxDirect) { 190 if (fNumBlocks <= kMaxDirect) 191 blocksNeeded += 1; 192 193 if (numBlocks > kMaxIndirect) { 194 if (fNumBlocks <= kMaxIndirect) { 195 blocksNeeded += 2 + (numBlocks - kMaxIndirect - 1) 196 / kIndirectsPerBlock; 197 } else { 198 blocksNeeded += (numBlocks - kMaxIndirect - 1) 199 / kIndirectsPerBlock - (fNumBlocks 200 - kMaxIndirect - 1) / kIndirectsPerBlock; 201 } 202 203 if (numBlocks > kMaxDoubleIndirect) { 204 if (fNumBlocks <= kMaxDoubleIndirect) { 205 blocksNeeded += 2 + (numBlocks - kMaxDoubleIndirect - 1) 206 / kIndirectsPerBlock2; 207 } else { 208 blocksNeeded += (numBlocks - kMaxDoubleIndirect - 1) 209 / kIndirectsPerBlock - (fNumBlocks 210 - kMaxDoubleIndirect - 1) / kIndirectsPerBlock; 211 } 212 } 213 } 214 } 215 } 216 217 TRACE("DataStream::BlocksNeeded(): %lu\n", blocksNeeded); 218 return blocksNeeded; 219 } 220 221 222 status_t 223 DataStream::_GetBlock(Transaction& transaction, uint32& block) 224 { 225 TRACE("DataStream::_GetBlock(): allocated: %lu, pos: %lu, waiting: %lu\n", 226 fAllocated, fAllocatedPos, fWaiting); 227 228 if (fAllocated == 0) { 229 uint32 blockGroup = (fAllocatedPos - fFirstBlock) 230 / fVolume->BlocksPerGroup(); 231 fAllocatedPos %= fVolume->BlocksPerGroup(); 232 233 status_t status = fVolume->AllocateBlocks(transaction, 1, fWaiting, 234 blockGroup, fAllocatedPos, fAllocated); 235 if (status != B_OK) 236 return status; 237 238 fWaiting -= fAllocated; 239 fAllocatedPos += fVolume->BlocksPerGroup() * blockGroup + fFirstBlock; 240 241 TRACE("DataStream::_GetBlock(): newAllocated: %lu, newpos: %lu," 242 "newwaiting: %lu\n", fAllocated, fAllocatedPos, fWaiting); 243 } 244 245 fAllocated--; 246 block = fAllocatedPos++; 247 248 return B_OK; 249 } 250 251 252 status_t 253 DataStream::_PrepareBlock(Transaction& transaction, uint32* pos, 254 uint32& blockNum, bool& clear) 255 { 256 blockNum = B_LENDIAN_TO_HOST_INT32(*pos); 257 clear = false; 258 259 if (blockNum == 0) { 260 status_t status = _GetBlock(transaction, blockNum); 261 if (status != B_OK) 262 return status; 263 264 *pos = B_HOST_TO_LENDIAN_INT32(blockNum); 265 clear = true; 266 } 267 268 return B_OK; 269 } 270 271 272 status_t 273 DataStream::_AddBlocks(Transaction& transaction, uint32* block, uint32 _count) 274 { 275 uint32 count = _count; 276 TRACE("DataStream::_AddBlocks(): count: %lu\n", count); 277 278 while (count > 0) { 279 uint32 blockNum; 280 status_t status = _GetBlock(transaction, blockNum); 281 if (status != B_OK) 282 return status; 283 284 *(block++) = B_HOST_TO_LENDIAN_INT32(blockNum); 285 --count; 286 } 287 288 fNumBlocks += _count; 289 290 return B_OK; 291 } 292 293 294 status_t 295 DataStream::_AddBlocks(Transaction& transaction, uint32* block, uint32 start, 296 uint32 end, int recursion) 297 { 298 TRACE("DataStream::_AddBlocks(): start: %lu, end %lu, recursion: %d\n", 299 start, end, recursion); 300 301 bool clear; 302 uint32 blockNum; 303 status_t status = _PrepareBlock(transaction, block, blockNum, clear); 304 if (status != B_OK) 305 return status; 306 307 CachedBlock cached(fVolume); 308 uint32* childBlock = (uint32*)cached.SetToWritable(transaction, blockNum, 309 clear); 310 if (childBlock == NULL) 311 return B_IO_ERROR; 312 313 if (recursion == 0) 314 return _AddBlocks(transaction, &childBlock[start], end - start); 315 316 uint32 elementWidth; 317 if (recursion == 1) 318 elementWidth = kIndirectsPerBlock; 319 else if (recursion == 2) 320 elementWidth = kIndirectsPerBlock2; 321 else { 322 panic("Undefined recursion level\n"); 323 elementWidth = 0; 324 } 325 326 uint32 elementPos = start / elementWidth; 327 uint32 endPos = end / elementWidth; 328 329 TRACE("DataStream::_AddBlocks(): element pos: %lu, end pos: %lu\n", 330 elementPos, endPos); 331 332 recursion--; 333 334 if (elementPos == endPos) { 335 return _AddBlocks(transaction, &childBlock[elementPos], 336 start % elementWidth, end % elementWidth, recursion); 337 } 338 339 if (start % elementWidth != 0) { 340 status = _AddBlocks(transaction, &childBlock[elementPos], 341 start % elementWidth, elementWidth, recursion); 342 if (status != B_OK) 343 return status; 344 345 elementPos++; 346 } 347 348 while (elementPos < endPos) { 349 status = _AddBlocks(transaction, &childBlock[elementPos], 0, 350 elementWidth, recursion); 351 if (status != B_OK) 352 return status; 353 354 elementPos++; 355 } 356 357 if (end % elementWidth != 0) { 358 status = _AddBlocks(transaction, &childBlock[elementPos], 0, 359 end % elementWidth, recursion); 360 if (status != B_OK) 361 return status; 362 } 363 364 return B_OK; 365 } 366 367 368 status_t 369 DataStream::_AddForDirectBlocks(Transaction& transaction, uint32 numBlocks) 370 { 371 TRACE("DataStream::_AddForDirectBlocks(): current size: %lu, target size: " 372 "%lu\n", fNumBlocks, numBlocks); 373 uint32* direct = &fStream->direct[fNumBlocks]; 374 uint32 end = numBlocks > kMaxDirect ? kMaxDirect : numBlocks; 375 376 return _AddBlocks(transaction, direct, end - fNumBlocks); 377 } 378 379 380 status_t 381 DataStream::_AddForIndirectBlock(Transaction& transaction, uint32 numBlocks) 382 { 383 TRACE("DataStream::_AddForIndirectBlocks(): current size: %lu, target " 384 "size: %lu\n", fNumBlocks, numBlocks); 385 uint32 *indirect = &fStream->indirect; 386 uint32 start = fNumBlocks - kMaxDirect; 387 uint32 end = numBlocks - kMaxDirect; 388 389 if (end > kIndirectsPerBlock) 390 end = kIndirectsPerBlock; 391 392 return _AddBlocks(transaction, indirect, start, end, 0); 393 } 394 395 396 status_t 397 DataStream::_AddForDoubleIndirectBlock(Transaction& transaction, 398 uint32 numBlocks) 399 { 400 TRACE("DataStream::_AddForDoubleIndirectBlock(): current size: %lu, " 401 "target size: %lu\n", fNumBlocks, numBlocks); 402 uint32 *doubleIndirect = &fStream->double_indirect; 403 uint32 start = fNumBlocks - kMaxIndirect; 404 uint32 end = numBlocks - kMaxIndirect; 405 406 if (end > kIndirectsPerBlock2) 407 end = kIndirectsPerBlock2; 408 409 return _AddBlocks(transaction, doubleIndirect, start, end, 1); 410 } 411 412 413 status_t 414 DataStream::_AddForTripleIndirectBlock(Transaction& transaction, 415 uint32 numBlocks) 416 { 417 TRACE("DataStream::_AddForTripleIndirectBlock(): current size: %lu, " 418 "target size: %lu\n", fNumBlocks, numBlocks); 419 uint32 *tripleIndirect = &fStream->triple_indirect; 420 uint32 start = fNumBlocks - kMaxDoubleIndirect; 421 uint32 end = numBlocks - kMaxDoubleIndirect; 422 423 return _AddBlocks(transaction, tripleIndirect, start, end, 2); 424 } 425 426 427 status_t 428 DataStream::_PerformFree(Transaction& transaction) 429 { 430 TRACE("DataStream::_PerformFree(): start: %lu, count: %lu\n", fFreeStart, 431 fFreeCount); 432 status_t status; 433 434 if (fFreeCount == 0) 435 status = B_OK; 436 else 437 status = fVolume->FreeBlocks(transaction, fFreeStart, fFreeCount); 438 439 fFreeStart = 0; 440 fFreeCount = 0; 441 442 return status; 443 } 444 445 446 status_t 447 DataStream::_MarkBlockForRemoval(Transaction& transaction, uint32* block) 448 { 449 TRACE("DataStream::_MarkBlockForRemoval(*(%p) = %lu): free start: %lu, " 450 "free count: %lu\n", block, *block, fFreeStart, fFreeCount); 451 uint32 blockNum = B_LENDIAN_TO_HOST_INT32(*block); 452 *block = 0; 453 454 if (blockNum != fFreeStart + fFreeCount) { 455 if (fFreeCount != 0) { 456 status_t status = fVolume->FreeBlocks(transaction, fFreeStart, 457 fFreeCount); 458 if (status != B_OK) 459 return status; 460 } 461 462 fFreeStart = blockNum; 463 fFreeCount = 0; 464 } 465 466 fFreeCount++; 467 468 return B_OK; 469 } 470 471 472 status_t 473 DataStream::_FreeBlocks(Transaction& transaction, uint32* block, uint32 _count) 474 { 475 uint32 count = _count; 476 TRACE("DataStream::_FreeBlocks(%p, %lu)\n", block, count); 477 478 while (count > 0) { 479 status_t status = _MarkBlockForRemoval(transaction, block); 480 if (status != B_OK) 481 return status; 482 483 block++; 484 count--; 485 } 486 487 fRemovedBlocks += _count; 488 489 return B_OK; 490 } 491 492 493 status_t 494 DataStream::_FreeBlocks(Transaction& transaction, uint32* block, uint32 start, 495 uint32 end, bool freeParent, int recursion) 496 { 497 // TODO: Designed specifically for shrinking. Perhaps make it more general? 498 TRACE("DataStream::_FreeBlocks(%p, %lu, %lu, %c, %d)\n", 499 block, start, end, freeParent ? 't' : 'f', recursion); 500 501 uint32 blockNum = B_LENDIAN_TO_HOST_INT32(*block); 502 503 if (freeParent) { 504 status_t status = _MarkBlockForRemoval(transaction, block); 505 if (status != B_OK) 506 return status; 507 } 508 509 CachedBlock cached(fVolume); 510 uint32* childBlock = (uint32*)cached.SetToWritable(transaction, blockNum); 511 if (childBlock == NULL) 512 return B_IO_ERROR; 513 514 if (recursion == 0) 515 return _FreeBlocks(transaction, &childBlock[start], end - start); 516 517 uint32 elementWidth; 518 if (recursion == 1) 519 elementWidth = kIndirectsPerBlock; 520 else if (recursion == 2) 521 elementWidth = kIndirectsPerBlock2; 522 else { 523 panic("Undefinied recursion level\n"); 524 elementWidth = 0; 525 } 526 527 uint32 elementPos = start / elementWidth; 528 uint32 endPos = end / elementWidth; 529 530 recursion--; 531 532 if (elementPos == endPos) { 533 bool free = freeParent || start % elementWidth == 0; 534 return _FreeBlocks(transaction, &childBlock[elementPos], 535 start % elementWidth, end % elementWidth, free, recursion); 536 } 537 538 status_t status = B_OK; 539 540 if (start % elementWidth != 0) { 541 status = _FreeBlocks(transaction, &childBlock[elementPos], 542 start % elementWidth, elementWidth, false, recursion); 543 if (status != B_OK) 544 return status; 545 546 elementPos++; 547 } 548 549 while (elementPos < endPos) { 550 status = _FreeBlocks(transaction, &childBlock[elementPos], 0, 551 elementWidth, true, recursion); 552 if (status != B_OK) 553 return status; 554 555 elementPos++; 556 } 557 558 if (end % elementWidth != 0) { 559 status = _FreeBlocks(transaction, &childBlock[elementPos], 0, 560 end % elementWidth, true, recursion); 561 } 562 563 return status; 564 } 565 566 567 status_t 568 DataStream::_RemoveFromDirectBlocks(Transaction& transaction, uint32 numBlocks) 569 { 570 TRACE("DataStream::_RemoveFromDirectBlocks(): current size: %lu, " 571 "target size: %lu\n", fNumBlocks, numBlocks); 572 uint32* direct = &fStream->direct[numBlocks]; 573 uint32 end = fNumBlocks > kMaxDirect ? kMaxDirect : fNumBlocks; 574 575 return _FreeBlocks(transaction, direct, end - numBlocks); 576 } 577 578 579 status_t 580 DataStream::_RemoveFromIndirectBlock(Transaction& transaction, uint32 numBlocks) 581 { 582 TRACE("DataStream::_RemoveFromIndirectBlock(): current size: %lu, " 583 "target size: %lu\n", fNumBlocks, numBlocks); 584 uint32* indirect = &fStream->indirect; 585 uint32 start = numBlocks <= kMaxDirect ? 0 : numBlocks - kMaxDirect; 586 uint32 end = fNumBlocks - kMaxDirect; 587 588 if (end > kIndirectsPerBlock) 589 end = kIndirectsPerBlock; 590 591 bool freeAll = start == 0; 592 593 return _FreeBlocks(transaction, indirect, start, end, freeAll, 0); 594 } 595 596 597 status_t 598 DataStream::_RemoveFromDoubleIndirectBlock(Transaction& transaction, 599 uint32 numBlocks) 600 { 601 TRACE("DataStream::_RemoveFromDoubleIndirectBlock(): current size: %lu, " 602 "target size: %lu\n", fNumBlocks, numBlocks); 603 uint32* doubleIndirect = &fStream->double_indirect; 604 uint32 start = numBlocks <= kMaxIndirect ? 0 : numBlocks - kMaxIndirect; 605 uint32 end = fNumBlocks - kMaxIndirect; 606 607 if (end > kIndirectsPerBlock2) 608 end = kIndirectsPerBlock2; 609 610 bool freeAll = start == 0; 611 612 return _FreeBlocks(transaction, doubleIndirect, start, end, freeAll, 1); 613 } 614 615 616 status_t 617 DataStream::_RemoveFromTripleIndirectBlock(Transaction& transaction, 618 uint32 numBlocks) 619 { 620 TRACE("DataStream::_RemoveFromTripleIndirectBlock(): current size: %lu, " 621 "target size: %lu\n", fNumBlocks, numBlocks); 622 uint32* tripleIndirect = &fStream->triple_indirect; 623 uint32 start = numBlocks <= kMaxDoubleIndirect ? 0 624 : numBlocks - kMaxDoubleIndirect; 625 uint32 end = fNumBlocks - kMaxDoubleIndirect; 626 627 bool freeAll = start == 0; 628 629 return _FreeBlocks(transaction, tripleIndirect, start, end, freeAll, 2); 630 } 631