[openbeos] Possible BFS Problem #2

Hi!

Ok, I debugged the BFS Problem a bit futher and think I have found the problem (though I may not be right at all).

I have following filesystem layout:

132: Device:
132: ===========================
132: Device size          : 4208652 blocks
132: Device block size    : 512 byte
132: Filesystem blocksize : 2048 byte
132:
132: Superblock:
132: ===========================
132: disk_super_block:
132:   magic1         = 0x534b5931 (SKY1) valid
132:   fs_byte_order  = 0x42494745 (BIGE)
132:   block_size     = 2048
132:   block_shift    = 11
132:   num_blocks     = 1052163
132:   used_blocks    = 155171
132:   inode_size     = 2048
132:   magic2         = 0x33551214 (3U..) valid
132:   blocks_per_ag  = 2
132:   ag_shift       = 15 (8938037396406272 bytes)
132:   num_ags        = 33
132:   flags          = 0x434c454e (CLEN)
132:   log_blocks     = (837518622720, 2048, 28)
132:   log_start      = 1051
132:   log_end        = 1051
132:   magic3         = 0x12149977 (...w) valid
132:   bootloadersize = 128
132:   root_dir       = (8, 1, 49)
132:   indices        = (9633611644928, 1, 49)
132:
132: BlockAllocator:
132: ===========================
132: Blocks per group : 2
132: Numbits          : 32768
132: Blockshift       : 11
132: AllcationGrpShift: 15


From time to time, the creation of a new inode fails. When it fails, then always when trying to allocate blocks in the last allocation group.

Take a look at following code: (blockallocator.cpp)
status_t
BlockAllocator::AllocateBlocks(Transaction *transaction, int32 group, uint16 start,
uint16 maximum, uint16 minimum, block_run &run)
{
if (maximum == 0)
return B_BAD_VALUE;

       AllocationBlock cached(fVolume);
       Locker lock(fLock);

       // the first scan through all allocation groups will look for the
       // wanted maximum of blocks, the second scan will just look to
       // satisfy the minimal requirement
       uint16 numBlocks = maximum;

       for (int32 i = 0; i < fNumGroups * 2; i++, group++, start = 0)
       {
               group = group % fNumGroups;

if (start >= fGroups[group].fNumBits || fGroups[group].IsFull())
continue;

if (i >= fNumGroups) {
// if the minimum is the same as the maximum, it's not necessary to
// search for in the allocation groups a second time
if (maximum == minimum)
return B_DEVICE_FULL;

                       numBlocks = minimum;
               }

// The wanted maximum is smaller than the largest free block in the group
// or already smaller than the minimum
// ToDo: disabled because it's currently not maintained after the first allocation
//if (numBlocks > fGroups[group].fLargest)
// continue;

               if (start < fGroups[group].fFirstFree)
                       start = fGroups[group].fFirstFree;

// there may be more than one block per allocation group - and
// we iterate through it to find a place for the allocation.
// (one allocation can't exceed one allocation group)

               uint32 block = start / (fVolume->BlockSize() << 3);
               int32 range = 0, rangeStart = 0;


*****
NOTE1
*****
               for (; block < fBlocksPerGroup; block++)
               {
                       if (cached.SetTo(fGroups[group], block) < B_OK)
                               RETURN_ERROR(B_ERROR);

// find a block large enough to hold the allocation
for (uint32 bit = start % cached.NumBlockBits(); bit < cached.NumBlockBits(); bit++)
{
if (!cached.IsUsed(bit))
{
if (range == 0)
{
// start new range
rangeStart = block * cached.NumBlockBits() + bit;
}

// have we found a range large enough to hold numBlocks?
if (++range >= maximum)
break;
}
else if (i >= fNumGroups && range >= minimum)
{
// we have found a block larger than the required minimum (second pass)
break;
}
else
{
// end of a range
range = 0;
}
}

// if we found a suitable block, mark the blocks as in use, and write
// the updated block bitmap back to disk
*****
NOTE2
*****
if (range >= numBlocks)
{
// adjust allocation size
if (numBlocks < maximum)
numBlocks = range;

if (fGroups[group].Allocate(transaction,rangeStart, numBlocks) < B_OK)
{
printk("blockallocator.cpp: Failed to allocate block");
printk(" group: %d, rangeStart: %d, numBlocks: %d, start :%d, numbits: %d, block: %d, rangeStart: %d",
group, rangeStart, numBlocks, start, cached.NumBlockBits(), block, range, rangeStart);

sys_KernelDebuggerEnter();
}
else
{
run.allocation_group = HOST_ENDIAN_TO_BFS_INT32(group);
run.start = HOST_ENDIAN_TO_BFS_INT16(rangeStart);
run.length = HOST_ENDIAN_TO_BFS_INT16(numBlocks);

fVolume->SuperBlock().used_blocks =
HOST_ENDIAN_TO_BFS_INT64(fVolume->UsedBlocks() + numBlocks);
// We are not writing back the disk's super block - it's
// either done by the journaling code, or when the disk
// is unmounted.
// If the value is not correct at mount time, it will be
// fixed anyway.

                                       return B_OK;
                               }
                       }

*****
NOTE3
*****
                       // start from the beginning of the next block
                       start = 0;
               }
       }
       return B_DEVICE_FULL;
}

At the time the allocation fails, BlockAllocator::AllocateBlocks gets called with:

BlockAllocator::AllocateBlocks(transaction, group = 32, start = 0, maximum=32, minimum, run).
which means, BlockAllocator::AllocateBlocks is called to allocate 32 blocks in the last allocation group.

At NOTE1, the "for (; block < fBlocksPerGroup; block++)" loop tries to find a free block range with 32 blocks in it.

The first free bit is found at 3559 (block 0). (The last allocation group has 3587 blocks in total. cached.NumBlockBits() == 3587 ).
The loop leaves with just 28 available free blocks right at the end of the first block.

The "if" at NOTE2 fails because we didn't find a range with 32 blocks yet.

At NOTE3, start gets reset and we enter the loop again.

But exactely there is the problem, I think. The last allocation group has just one bitmap block, but the second iteration will read the second block, which got filled with zeros (meaning free block) while initializing the filesystem.And because the second block content is all zero, the allocation for 32blocks in the last allocation groupd will succeed, leading to access out of the device limit and setting fFreeBits to a negative value.

Additional info:

1. Most time this block allocation error occures only when using odd filesystem sizes, like 1055MB, 3119MB, 73333MB ...

2. If I replace the loop at NOTE1 with:
iBlocksInGroup = fGroups[group].fNumBits / 8 / fVolume->BlockSize();

       for (; block < iBlocksInGroup; block++)
       {

everything can be installed correctly. No block allocation erros anymore.


I may have missed something here, can anyone confirm this?


Thanks!
Robert


Other related posts: