src/add-ons/kernel/file_systems/ext2/ExtentStream.cpp

   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 }