/*
 * Copyright 2001-2025, Axel Dörfler, axeld@pinc-software.de.
 * This file may be used under the terms of the MIT License.
 */


//! Block bitmap handling and allocation policies


#include "BlockAllocator.h"

#include "Debug.h"
#include "Inode.h"
#include "Volume.h"


// Things the BlockAllocator should do:

// - find a range of blocks of a certain size nearby a specific position
// - allocating an unsharp range of blocks for pre-allocation
// - free blocks
// - know how to deal with each allocation, special handling for directories,
//   files, symlinks, etc. (type sensitive allocation policies)

// What makes the code complicated is the fact that we are not just reading
// in the whole bitmap and operate on that in memory - e.g. a 13 GB partition
// with a block size of 2048 bytes already has a 800kB bitmap, and the size
// of partitions will grow even more - so that's not an option.
// Instead we are reading in every block when it's used - since an allocation
// group can span several blocks in the block bitmap, the AllocationBlock
// class is there to make handling those easier.

// The current implementation is only slightly optimized and could probably
// be improved a lot. Furthermore, the allocation policies used here should
// have some real world tests.

#if BFS_TRACING && !defined(FS_SHELL)
namespace BFSBlockTracing {


class Allocate : public AbstractTraceEntry {
public:
        Allocate(block_run run)
                :
                fRun(run)
        {
                Initialized();
        }

        virtual void AddDump(TraceOutput& out)
        {
                out.Print("bfs:alloc %" B_PRId32 ".%" B_PRIu16 ".%" B_PRIu16,
                        fRun.AllocationGroup(), fRun.Start(), fRun.Length());
        }

        const block_run& Run() const { return fRun; }

private:
                        block_run                       fRun;
};


class Free : public AbstractTraceEntry {
public:
        Free(block_run run)
                :
                fRun(run)
        {
                Initialized();
        }

        virtual void AddDump(TraceOutput& out)
        {
                out.Print("bfs:free %" B_PRId32 ".%" B_PRIu16 ".%" B_PRIu16,
                        fRun.AllocationGroup(), fRun.Start(), fRun.Length());
        }

        const block_run& Run() const { return fRun; }

private:
                        block_run                       fRun;
};


static uint32
checksum(const uint8* data, size_t size)
{
        const uint32* data4 = (const uint32*)data;
        uint32 sum = 0;
        while (size >= 4) {
                sum += *data4;
                data4++;
                size -= 4;
        }
        return sum;
}


class Block : public AbstractTraceEntry {
public:
        Block(const char* label, off_t blockNumber, const uint8* data,
                        size_t size, uint32 start = 0, uint32 length = 0)
                :
                fBlock(blockNumber),
                fData(data),
                fStart(start),
                fLength(length),
                fLabel(label)
        {
                fSum = checksum(data, size);
                Initialized();
        }

        virtual void AddDump(TraceOutput& out)
        {
                out.Print("bfs:%s: block %lld (%p), sum %lu, s/l %lu/%lu", fLabel,
                        fBlock, fData, fSum, fStart, fLength);
        }

private:
                        off_t                           fBlock;
                        const uint8*            fData;
                        uint32                          fStart;
                        uint32                          fLength;
                        uint32                          fSum;
                        const char*                     fLabel;
};


class BlockChange : public AbstractTraceEntry {
public:
        BlockChange(const char* label, int32 block, uint32 oldData, uint32 newData)
                :
                fBlock(block),
                fOldData(oldData),
                fNewData(newData),
                fLabel(label)
        {
                Initialized();
        }

        virtual void AddDump(TraceOutput& out)
        {
                out.Print("bfs:%s: block %ld, %08lx -> %08lx", fLabel,
                        fBlock, fOldData, fNewData);
        }

private:
                        int32                           fBlock;
                        uint32                          fOldData;
                        uint32                          fNewData;
                        const char*                     fLabel;
};


}       // namespace BFSBlockTracing

#       define T(x) new(std::nothrow) BFSBlockTracing::x;
#else
#       define T(x) ;
#endif

#ifdef DEBUG_ALLOCATION_GROUPS
#       define CHECK_ALLOCATION_GROUP(group) _CheckGroup(group)
#else
#       define CHECK_ALLOCATION_GROUP(group) ;
#endif


class AllocationBlock : public CachedBlock {
public:
        AllocationBlock(Volume* volume);

        inline void Allocate(uint16 start, uint16 numBlocks);
        inline void Free(uint16 start, uint16 numBlocks);
        inline bool IsUsed(uint16 block);
        inline uint32 NextFree(uint16 startBlock);

        status_t SetTo(AllocationGroup& group, uint16 block);
        status_t SetToWritable(Transaction& transaction, AllocationGroup& group,
                uint16 block);

        uint32 NumBlockBits() const { return fNumBits; }
        uint32& Chunk(int32 index) { return ((uint32*)fBlock)[index]; }
        uint8* Block() const { return (uint8*)fBlock; }

private:
        uint32  fNumBits;
#ifdef DEBUG
        bool    fWritable;
#endif
};


class AllocationGroup {
public:
        AllocationGroup();

        void AddFreeRange(int32 start, int32 blocks);
        bool IsFull() const { return fFreeBits == 0; }

        status_t Allocate(Transaction& transaction, uint16 start, int32 length);
        status_t Free(Transaction& transaction, uint16 start, int32 length);

        uint32 NumBits() const { return fNumBits; }
        uint32 NumBitmapBlocks() const { return fNumBitmapBlocks; }
        int32 Start() const { return fStart; }

private:
        friend class BlockAllocator;

        uint32  fNumBits;
        uint32  fNumBitmapBlocks;
        int32   fStart;
        int32   fFirstFree;
        int32   fFreeBits;

        int32   fLargestStart;
        int32   fLargestLength;
        bool    fLargestValid;
};


AllocationBlock::AllocationBlock(Volume* volume)
        : CachedBlock(volume)
{
}


status_t
AllocationBlock::SetTo(AllocationGroup& group, uint16 block)
{
        // 8 blocks per byte
        fNumBits = fVolume->BlockSize() << 3;
        // the last group may have less bits than the others
        if ((block + 1) * fNumBits > group.NumBits())
                fNumBits = group.NumBits() % fNumBits;

#ifdef DEBUG
        fWritable = false;
#endif
        return CachedBlock::SetTo(group.Start() + block);
}


status_t
AllocationBlock::SetToWritable(Transaction& transaction, AllocationGroup& group,
        uint16 block)
{
        // 8 blocks per byte
        fNumBits = fVolume->BlockSize() << 3;
        // the last group may have less bits in the last block
        if ((block + 1) * fNumBits > group.NumBits())
                fNumBits = group.NumBits() % fNumBits;

#ifdef DEBUG
        fWritable = true;
#endif
        return CachedBlock::SetToWritable(transaction, group.Start() + block);
}


bool
AllocationBlock::IsUsed(uint16 block)
{
        if (block > fNumBits)
                return true;

        // the block bitmap is accessed in 32-bit chunks
        return Chunk(block >> 5) & HOST_ENDIAN_TO_BFS_INT32(1UL << (block % 32));
}


uint32
AllocationBlock::NextFree(uint16 startBlock)
{
        // Set all bits below the start block in the current chunk, to ignore them.
        uint32 ignoreNext = (1UL << (startBlock % 32)) - 1;

        for (uint32 offset = ROUNDDOWN(startBlock, 32);
                        offset < fNumBits; offset += 32) {
                uint32 chunk = Chunk(offset >> 5);
                chunk |= ignoreNext;
                ignoreNext = 0;

                if (chunk == UINT32_MAX)
                        continue;
                uint32 result = offset + ffs(~chunk) - 1;
                if (result >= fNumBits)
                        break;
                return result;
        }

        return fNumBits;
}


void
AllocationBlock::Allocate(uint16 start, uint16 numBlocks)
{
        ASSERT(start < fNumBits);
        ASSERT(uint32(start + numBlocks) <= fNumBits);
#ifdef DEBUG
        ASSERT(fWritable);
#endif

        T(Block("b-alloc-in", fBlockNumber, fBlock, fVolume->BlockSize(),
                start, numBlocks));

        int32 block = start >> 5;

        while (numBlocks > 0) {
                uint32 mask = 0;
                for (int32 i = start % 32; i < 32 && numBlocks; i++, numBlocks--)
                        mask |= 1UL << i;

                T(BlockChange("b-alloc", block, Chunk(block),
                        Block(block) | HOST_ENDIAN_TO_BFS_INT32(mask)));

#if KDEBUG
                // check for already set blocks
                if (HOST_ENDIAN_TO_BFS_INT32(mask) & ((uint32*)fBlock)[block]) {
                        FATAL(("AllocationBlock::Allocate(): some blocks are already "
                                "allocated, start = %u, numBlocks = %u\n", start, numBlocks));
                        panic("blocks already set!");
                }
#endif

                Chunk(block++) |= HOST_ENDIAN_TO_BFS_INT32(mask);
                start = 0;
        }
        T(Block("b-alloc-out", fBlockNumber, fBlock, fVolume->BlockSize(),
                start, numBlocks));
}


void
AllocationBlock::Free(uint16 start, uint16 numBlocks)
{
        ASSERT(start < fNumBits);
        ASSERT(uint32(start + numBlocks) <= fNumBits);
#ifdef DEBUG
        ASSERT(fWritable);
#endif

        int32 block = start >> 5;

        while (numBlocks > 0) {
                uint32 mask = 0;
                for (int32 i = start % 32; i < 32 && numBlocks; i++, numBlocks--)
                        mask |= 1UL << (i % 32);

                T(BlockChange("b-free", block, Chunk(block),
                        Block(block) & HOST_ENDIAN_TO_BFS_INT32(~mask)));

                Chunk(block++) &= HOST_ENDIAN_TO_BFS_INT32(~mask);
                start = 0;
        }
}


//      #pragma mark -


/*!     The allocation groups are created and initialized in
        BlockAllocator::Initialize() and BlockAllocator::InitializeAndClearBitmap()
        respectively.
*/
AllocationGroup::AllocationGroup()
        :
        fFirstFree(-1),
        fFreeBits(0),
        fLargestValid(false)
{
}


void
AllocationGroup::AddFreeRange(int32 start, int32 blocks)
{
        //D(if (blocks > 512)
        //      PRINT(("range of %ld blocks starting at %ld\n",blocks,start)));

        if (fFirstFree == -1)
                fFirstFree = start;

        if (!fLargestValid || fLargestLength < blocks) {
                fLargestStart = start;
                fLargestLength = blocks;
                fLargestValid = true;
        }

        fFreeBits += blocks;
}


/*!     Allocates the specified run in the allocation group.
        Doesn't check if the run is valid or already allocated partially, nor
        does it maintain the free ranges hints or the volume's used blocks count.
        It only does the low-level work of allocating some bits in the block bitmap.
        Assumes that the block bitmap lock is hold.
*/
status_t
AllocationGroup::Allocate(Transaction& transaction, uint16 start, int32 length)
{
        ASSERT(start + length <= (int32)fNumBits);

        // Update the allocation group info
        // TODO: this info will be incorrect if something goes wrong later
        // Note, the fFirstFree block doesn't have to be really free
        if (start == fFirstFree)
                fFirstFree = start + length;
        fFreeBits -= length;

        if (fLargestValid) {
                bool cut = false;
                if (fLargestStart == start) {
                        // cut from start
                        fLargestStart += length;
                        fLargestLength -= length;
                        cut = true;
                } else if (start > fLargestStart
                        && start < fLargestStart + fLargestLength) {
                        // cut from end
                        fLargestLength = start - fLargestStart;
                        cut = true;
                }
                if (cut && (fLargestLength < fLargestStart
                                || fLargestLength
                                                < (int32)fNumBits - (fLargestStart + fLargestLength))) {
                        // might not be the largest block anymore
                        fLargestValid = false;
                }
        }

        Volume* volume = transaction.GetVolume();

        // calculate block in the block bitmap and position within
        uint32 bitsPerBlock = volume->BlockSize() << 3;
        uint32 block = start / bitsPerBlock;
        start = start % bitsPerBlock;

        AllocationBlock cached(volume);

        while (length > 0) {
                if (cached.SetToWritable(transaction, *this, block) < B_OK) {
                        fLargestValid = false;
                        RETURN_ERROR(B_IO_ERROR);
                }

                uint32 numBlocks = length;
                if (start + numBlocks > cached.NumBlockBits())
                        numBlocks = cached.NumBlockBits() - start;

                cached.Allocate(start, numBlocks);

                length -= numBlocks;
                start = 0;
                block++;
        }

        return B_OK;
}


/*!     Frees the specified run in the allocation group.
        Doesn't check if the run is valid or was not completely allocated, nor
        does it maintain the free ranges hints or the volume's used blocks count.
        It only does the low-level work of freeing some bits in the block bitmap.
        Assumes that the block bitmap lock is hold.
*/
status_t
AllocationGroup::Free(Transaction& transaction, uint16 start, int32 length)
{
        ASSERT(start + length <= (int32)fNumBits);

        // Update the allocation group info
        // TODO: this info will be incorrect if something goes wrong later
        if (fFirstFree > start)
                fFirstFree = start;
        fFreeBits += length;

        // The range to be freed cannot be part of the valid largest range
        ASSERT(!fLargestValid || start + length <= fLargestStart
                || start > fLargestStart);

        if (fLargestValid
                && (start + length == fLargestStart
                        || fLargestStart + fLargestLength == start
                        || (start < fLargestStart && fLargestStart > fLargestLength)
                        || (start > fLargestStart
                                && (int32)fNumBits - (fLargestStart + fLargestLength)
                                                > fLargestLength))) {
                fLargestValid = false;
        }

        Volume* volume = transaction.GetVolume();

        // calculate block in the block bitmap and position within
        uint32 bitsPerBlock = volume->BlockSize() << 3;
        uint32 block = start / bitsPerBlock;
        start = start % bitsPerBlock;

        AllocationBlock cached(volume);

        while (length > 0) {
                if (cached.SetToWritable(transaction, *this, block) < B_OK)
                        RETURN_ERROR(B_IO_ERROR);

                T(Block("free-1", block, cached.Block(), volume->BlockSize()));
                uint16 freeLength = length;
                if (uint32(start + length) > cached.NumBlockBits())
                        freeLength = cached.NumBlockBits() - start;

                cached.Free(start, freeLength);

                length -= freeLength;
                start = 0;
                T(Block("free-2", block, cached.Block(), volume->BlockSize()));
                block++;
        }
        return B_OK;
}


//      #pragma mark -


BlockAllocator::BlockAllocator(Volume* volume)
        :
        fVolume(volume),
        fGroups(NULL),
        fAllowedBeginBlock(0),
        fAllowedEndBlock(0)
{
        recursive_lock_init(&fLock, "bfs allocator");
}


BlockAllocator::~BlockAllocator()
{
        recursive_lock_destroy(&fLock);
        delete[] fGroups;
}


status_t
BlockAllocator::Initialize(bool full)
{
        fNumGroups = fVolume->AllocationGroups();
        fBlocksPerGroup = fVolume->SuperBlock().BlocksPerAllocationGroup();
        fNumBitmapBlocks = fVolume->NumBitmapBlocks();

        fGroups = new(std::nothrow) AllocationGroup[fNumGroups];
        if (fGroups == NULL)
                return B_NO_MEMORY;

        if (!full)
                return B_OK;

        recursive_lock_lock(&fLock);
                // the lock will be released by the _Initialize() method

        thread_id id = spawn_kernel_thread((thread_func)BlockAllocator::_Initialize,
                "bfs block allocator", B_LOW_PRIORITY, this);
        if (id < B_OK)
                return _Initialize(this);

        recursive_lock_transfer_lock(&fLock, id);

        return resume_thread(id);
}


status_t
BlockAllocator::InitializeAndClearBitmap(Transaction& transaction)
{
        status_t status = Initialize(false);
        if (status != B_OK)
                return status;

        uint32 numBits = 8 * fBlocksPerGroup * fVolume->BlockSize();
        uint32 blockShift = fVolume->BlockShift();

        uint32* buffer = (uint32*)malloc(numBits >> 3);
        if (buffer == NULL)
                RETURN_ERROR(B_NO_MEMORY);

        memset(buffer, 0, numBits >> 3);

        off_t offset = 1;
                // the bitmap starts directly after the superblock

        // initialize the AllocationGroup objects and clear the on-disk bitmap

        for (int32 i = 0; i < fNumGroups; i++) {
                if (write_pos(fVolume->Device(), offset << blockShift, buffer,
                                fBlocksPerGroup << blockShift) < B_OK) {
                        free(buffer);
                        return B_ERROR;
                }

                // the last allocation group may contain less blocks than the others
                if (i == fNumGroups - 1) {
                        fGroups[i].fNumBits = fVolume->NumBlocks() - i * numBits;
                        fGroups[i].fNumBitmapBlocks = 1 + ((fGroups[i].NumBits() - 1)
                                >> (blockShift + 3));
                } else {
                        fGroups[i].fNumBits = numBits;
                        fGroups[i].fNumBitmapBlocks = fBlocksPerGroup;
                }
                fGroups[i].fStart = offset;
                fGroups[i].fFirstFree = fGroups[i].fLargestStart = 0;
                fGroups[i].fFreeBits = fGroups[i].fLargestLength = fGroups[i].fNumBits;
                fGroups[i].fLargestValid = true;

                offset += fBlocksPerGroup;
        }
        free(buffer);

        // reserve the boot block, the log area, and the block bitmap itself
        uint32 reservedBlocks = fVolume->ToBlock(fVolume->Log()) + fVolume->Log().Length();
        uint32 blocksToReserve = reservedBlocks;
        for (int32 i = 0; i < fNumGroups; i++) {
                int32 reservedBlocksInGroup = min_c(blocksToReserve, numBits);
                if (fGroups[i].Allocate(transaction, 0, reservedBlocksInGroup) < B_OK) {
                        FATAL(("could not allocate reserved space for block bitmap/log!\n"));
                        return B_ERROR;
                }
                blocksToReserve -= reservedBlocksInGroup;
                if (blocksToReserve == 0)
                        break;
        }
        fVolume->SuperBlock().used_blocks
                = HOST_ENDIAN_TO_BFS_INT64(reservedBlocks);

        return B_OK;
}


status_t
BlockAllocator::Reinitialize()
{
        // need to write back any pending changes to the block bitmap
        // TODO: shall we read through the cache in _Initialize instead?
        status_t status = fVolume->GetJournal(0)->FlushLogAndLockJournal();
        if (status != B_OK)
                return status;

        recursive_lock_lock(&fLock);
                // the lock will be unlocked in the call to Initialize()

        fVolume->GetJournal(0)->Unlock(NULL, true);
                // unlock the journal here: we only need to make sure that no one
                // starts a transaction before we get the allocator lock, as that
                // would cause a deadlock

        delete[] fGroups;
        return Initialize();
}


status_t
BlockAllocator::_Initialize(BlockAllocator* allocator)
{
        // The lock must already be held at this point
        RecursiveLocker locker(allocator->fLock, true);

        Volume* volume = allocator->fVolume;
        uint32 blocks = allocator->fBlocksPerGroup;
        uint32 blockShift = volume->BlockShift();
        off_t freeBlocks = 0;

        uint32* buffer = (uint32*)malloc(blocks << blockShift);
        if (buffer == NULL)
                RETURN_ERROR(B_NO_MEMORY);

        AllocationGroup* groups = allocator->fGroups;
        off_t offset = 1;
        uint32 bitsPerGroup = 8 * (blocks << blockShift);
        int32 numGroups = allocator->fNumGroups;

        for (int32 i = 0; i < numGroups; i++) {
                if (read_pos(volume->Device(), offset << blockShift, buffer,
                                blocks << blockShift) < B_OK)
                        break;

                // the last allocation group may contain less blocks than the others
                if (i == numGroups - 1) {
                        groups[i].fNumBits = volume->NumBlocks() - i * bitsPerGroup;
                        groups[i].fNumBitmapBlocks = 1 + ((groups[i].NumBits() - 1)
                                >> (blockShift + 3));
                } else {
                        groups[i].fNumBits = bitsPerGroup;
                        groups[i].fNumBitmapBlocks = blocks;
                }
                groups[i].fStart = offset;

                // finds all free ranges in this allocation group
                int32 start = -1, range = 0;
                int32 numBits = groups[i].fNumBits, bit = 0;
                int32 count = (numBits + 31) / 32;

                for (int32 k = 0; k < count; k++) {
                        for (int32 j = 0; j < 32 && bit < numBits; j++, bit++) {
                                if (buffer[k] & (1UL << j)) {
                                        // block is in use
                                        if (range > 0) {
                                                groups[i].AddFreeRange(start, range);
                                                range = 0;
                                        }
                                } else if (range++ == 0) {
                                        // block is free, start new free range
                                        start = bit;
                                }
                        }
                }
                if (range)
                        groups[i].AddFreeRange(start, range);

                freeBlocks += groups[i].fFreeBits;

                offset += blocks;
        }
        free(buffer);

        // check if block bitmap and log area are reserved
        uint32 reservedBlocks = volume->ToBlock(volume->Log()) + volume->Log().Length();

        if (allocator->CheckBlocks(0, reservedBlocks) != B_OK) {
                if (volume->IsReadOnly()) {
                        FATAL(("Space for block bitmap or log area is not reserved "
                                "(volume is mounted read-only)!\n"));
                } else {
                        Transaction transaction(volume, 0);
                        if (groups[0].Allocate(transaction, 0, reservedBlocks) != B_OK) {
                                FATAL(("Could not allocate reserved space for block "
                                        "bitmap/log!\n"));
                                volume->Panic();
                        } else {
                                transaction.Done();
                                FATAL(("Space for block bitmap or log area was not "
                                        "reserved!\n"));
                        }
                }
        }

        off_t usedBlocks = volume->NumBlocks() - freeBlocks;
        if (volume->UsedBlocks() != usedBlocks) {
                // If the disk in a dirty state at mount time, it's
                // normal that the values don't match
                INFORM(("volume reports %" B_PRIdOFF " used blocks, correct is %"
                        B_PRIdOFF "\n", volume->UsedBlocks(), usedBlocks));
                volume->SuperBlock().used_blocks = HOST_ENDIAN_TO_BFS_INT64(usedBlocks);
        }

        return B_OK;
}


void
BlockAllocator::Uninitialize()
{
        // We only have to make sure that the initializer thread isn't running
        // anymore.
        recursive_lock_lock(&fLock);
}


/*! Specifies the range in which blocks will be allocated, starting from
        \a beginBlock, up to but not including \a endBlock.
        \a beginBlock and \a endBlock values of 0 means that no limits on the
        allowed allocation range are imposed.
*/
void
BlockAllocator::SetAllowedRange(off_t beginBlock, off_t endBlock)
{
        RecursiveLocker lock(fLock);
        fAllowedBeginBlock = beginBlock;
        fAllowedEndBlock = endBlock;
}


bool
BlockAllocator::IsCompletelyInsideAllowedRange(block_run run) const
{
        if (fAllowedBeginBlock == 0 && fAllowedEndBlock == 0)
                return true;
        off_t runStart = fVolume->ToBlock(run);
        return runStart >= fAllowedBeginBlock && runStart + run.Length() <= fAllowedEndBlock;
}


bool
BlockAllocator::IsCompletelyOutsideAllowedRange(block_run run) const
{
        if (fAllowedBeginBlock == 0 && fAllowedEndBlock == 0)
                return false;
        // Note that this is not the opposite of _IsBlockRunInRange, as we only
        // return true if the block run is completely outside the range.
        off_t runStart = fVolume->ToBlock(run);
        return runStart + run.Length() <= fAllowedBeginBlock || runStart >= fAllowedEndBlock;
}


/*!     Tries to allocate between \a minimum, and \a maximum blocks, starting at
        group \a groupIndex with offset \a start. The resulting allocation is put
        into \a run.

        The number of allocated blocks is always a multiple of \a minimum which
        has to be a power of two value.
*/
status_t
BlockAllocator::AllocateBlocks(Transaction& transaction, int32 groupIndex,
        uint16 start, uint16 maximum, uint16 minimum, block_run& run)
{
        if (maximum == 0)
                return B_BAD_VALUE;
        if (fAllowedEndBlock > fVolume->NumBlocks())
                return B_BAD_VALUE;

        FUNCTION_START(("group = %" B_PRId32 ", start = %" B_PRIu16
                ", maximum = %" B_PRIu16 ", minimum = %" B_PRIu16 "\n",
                groupIndex, start, maximum, minimum));

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

        uint32 bitsPerFullBlock = fVolume->BlockSize() << 3;

        // Express the allowed allocation range in terms of allocation groups and
        // offsets.
        int32 firstAllowedGroup = fAllowedBeginBlock / bitsPerFullBlock;
        uint16 firstGroupBegin = fAllowedBeginBlock % bitsPerFullBlock;

        int32 lastAllowedGroup;
        int32 lastGroupEnd;

        if (fAllowedEndBlock == 0) {
                lastAllowedGroup = fNumGroups - 1;
                lastGroupEnd = fGroups[lastAllowedGroup].NumBits();
        } else {
                // If fEndBlock is the first block of an allocation group, the last
                // allowed group is the previous, and the end block offset is
                // bitsPerFullBlock.
                lastAllowedGroup = (fAllowedEndBlock - 1) / bitsPerFullBlock;
                lastGroupEnd = fAllowedEndBlock % bitsPerFullBlock;
                if (lastGroupEnd == 0)
                        lastGroupEnd = bitsPerFullBlock;
        }

        // Find the block_run that can fulfill the request best
        int32 bestGroup = -1;
        int32 bestStart = -1;
        int32 bestLength = -1;

        for (int32 i = 0; i < fNumGroups + 1; i++, groupIndex++, start = 0) {
                groupIndex = groupIndex % fNumGroups;
                AllocationGroup& group = fGroups[groupIndex];

                CHECK_ALLOCATION_GROUP(groupIndex);

                if (groupIndex < firstAllowedGroup || groupIndex > lastAllowedGroup)
                        continue;

                if (groupIndex == firstAllowedGroup && start < firstGroupBegin)
                        start = firstGroupBegin;

                uint32 end;
                if (groupIndex == lastAllowedGroup)
                        end = lastGroupEnd;
                else
                        end = group.NumBits();

                if (start >= end || group.IsFull())
                        continue;

                // The wanted maximum is smaller than the largest free block in the
                // group or already smaller than the minimum

                if (start < group.fFirstFree)
                        start = group.fFirstFree;

                if (group.fLargestValid) {
                        if (group.fLargestLength < bestLength)
                                continue;

                        if (group.fLargestStart >= start
                                && group.fLargestStart + group.fLargestLength <= (int32)end) {
                                if (group.fLargestLength >= bestLength) {
                                        bestGroup = groupIndex;
                                        bestStart = group.fLargestStart;
                                        bestLength = group.fLargestLength;

                                        if (bestLength >= maximum)
                                                break;
                                }

                                // We know everything about this group we have to, let's skip
                                // to the next
                                continue;
                        }
                }

                // 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 / bitsPerFullBlock;
                int32 currentStart = 0, currentLength = 0;
                int32 groupLargestStart = -1;
                int32 groupLargestLength = -1;
                int32 currentBit = start;
                bool canFindGroupLargest = start == 0 && end == group.NumBits();

                // If end is the first bit in a block, the last block considered is the
                // previous one, and the end bit is bitsPerFullBlock.
                uint32 lastBlock = (end - 1) / bitsPerFullBlock;
                uint32 lastBlockEndBit = end % bitsPerFullBlock;
                if (lastBlockEndBit == 0)
                        lastBlockEndBit = bitsPerFullBlock;

                for (; block <= lastBlock; block++) {
                        if (cached.SetTo(group, block) < B_OK)
                                RETURN_ERROR(B_ERROR);

                        T(Block("alloc-in", group.Start() + block, cached.Block(),
                                fVolume->BlockSize(), groupIndex, currentStart));

                        uint32 endBit;
                        if (block == lastBlock)
                                endBit = lastBlockEndBit;
                        else
                                endBit = cached.NumBlockBits();

                        // find a block large enough to hold the allocation
                        for (uint32 bit = start % bitsPerFullBlock; bit < endBit; bit++) {
                                if (!cached.IsUsed(bit)) {
                                        if (currentLength == 0) {
                                                // start new range
                                                currentStart = currentBit;
                                        }

                                        // have we found a range large enough to hold numBlocks?
                                        if (++currentLength >= maximum) {
                                                bestGroup = groupIndex;
                                                bestStart = currentStart;
                                                bestLength = currentLength;
                                                break;
                                        }
                                } else {
                                        if (currentLength) {
                                                // end of a range
                                                if (currentLength > bestLength) {
                                                        bestGroup = groupIndex;
                                                        bestStart = currentStart;
                                                        bestLength = currentLength;
                                                }
                                                if (currentLength > groupLargestLength) {
                                                        groupLargestStart = currentStart;
                                                        groupLargestLength = currentLength;
                                                }
                                                currentLength = 0;
                                        }
                                        if (((int32)group.NumBits() - currentBit)
                                                        <= groupLargestLength) {
                                                // We can't find a bigger block in this group anymore,
                                                // let's skip the rest.
                                                block = lastBlock + 1;
                                                break;
                                        }

                                        // Advance the current bit to one before the next free (or last) bit,
                                        // so that the next loop iteration will check the next free bit.
                                        const uint32 nextFreeOffset = cached.NextFree(bit) - bit;
                                        bit += nextFreeOffset - 1;
                                        currentBit += nextFreeOffset - 1;
                                }
                                currentBit++;
                        }

                        T(Block("alloc-out", block, cached.Block(),
                                fVolume->BlockSize(), groupIndex, currentStart));

                        if (bestLength >= maximum) {
                                canFindGroupLargest = false;
                                break;
                        }

                        // start from the beginning of the next block
                        start = 0;
                }

                if (currentBit == (int32)end) {
                        if (currentLength > bestLength) {
                                bestGroup = groupIndex;
                                bestStart = currentStart;
                                bestLength = currentLength;
                        }
                        if (canFindGroupLargest && currentLength > groupLargestLength) {
                                groupLargestStart = currentStart;
                                groupLargestLength = currentLength;
                        }
                }

                if (canFindGroupLargest && !group.fLargestValid
                        && groupLargestLength >= 0) {
                        group.fLargestStart = groupLargestStart;
                        group.fLargestLength = groupLargestLength;
                        group.fLargestValid = true;
                }

                if (bestLength >= maximum)
                        break;
        }

        // If we found a suitable range, mark the blocks as in use, and
        // write the updated block bitmap back to disk
        if (bestLength < minimum)
                return B_DEVICE_FULL;

        if (bestLength > maximum)
                bestLength = maximum;
        else if (minimum > 1) {
                // make sure bestLength is a multiple of minimum
                bestLength = round_down(bestLength, minimum);
        }

        if (fGroups[bestGroup].Allocate(transaction, bestStart, bestLength) != B_OK)
                RETURN_ERROR(B_IO_ERROR);

        CHECK_ALLOCATION_GROUP(bestGroup);

        run.allocation_group = HOST_ENDIAN_TO_BFS_INT32(bestGroup);
        run.start = HOST_ENDIAN_TO_BFS_INT16(bestStart);
        run.length = HOST_ENDIAN_TO_BFS_INT16(bestLength);

        ASSERT(fVolume->ToBlock(run) >= fAllowedBeginBlock);
        ASSERT(fAllowedEndBlock == 0 || fVolume->ToBlock(run) + run.Length() <= fAllowedEndBlock);

        fVolume->SuperBlock().used_blocks
                = HOST_ENDIAN_TO_BFS_INT64(fVolume->UsedBlocks() + bestLength);
                // We are not writing back the disk's superblock - 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.

        // We need to flush any remaining blocks in the new allocation to make sure
        // they won't interfere with the file cache.
        block_cache_discard(fVolume->BlockCache(), fVolume->ToBlock(run),
                run.Length());

        T(Allocate(run));
        return B_OK;
}


status_t
BlockAllocator::AllocateForInode(Transaction& transaction,
        const block_run* parent, mode_t type, block_run& run)
{
        // Apply some allocation policies here (AllocateBlocks() will break them
        // if necessary) - we will start with those described in Dominic Giampaolo's
        // "Practical File System Design", and see how good they work

        // Files are going in the same allocation group as its parent,
        // sub-directories will be inserted 8 allocation groups after
        // the one of the parent
        uint16 group = parent->AllocationGroup();
        if ((type & (S_DIRECTORY | S_INDEX_DIR | S_ATTR_DIR)) == S_DIRECTORY)
                group += 8;

        return AllocateBlocks(transaction, group, 0, 1, 1, run);
}


status_t
BlockAllocator::Allocate(Transaction& transaction, Inode* inode,
        off_t numBlocks, block_run& run, uint16 minimum)
{
        if (numBlocks <= 0)
                return B_ERROR;

        // one block_run can't hold more data than there is in one allocation group
        if (numBlocks > fGroups[0].NumBits())
                numBlocks = fGroups[0].NumBits();

        // since block_run.length is uint16, the largest number of blocks that
        // can be covered by a block_run is 65535
        // TODO: if we drop compatibility, couldn't we do this any better?
        // There are basically two possibilities:
        // a) since a length of zero doesn't have any sense, take that for 65536 -
        //    but that could cause many problems (bugs) in other areas
        // b) reduce the maximum amount of blocks per block_run, so that the
        //    remaining number of free blocks can be used in a useful manner
        //    (like 4 blocks) - but that would also reduce the maximum file size
        // c) have BlockRun::Length() return (length + 1).
        if (numBlocks > MAX_BLOCK_RUN_LENGTH)
                numBlocks = MAX_BLOCK_RUN_LENGTH;

        // Apply some allocation policies here (AllocateBlocks() will break them
        // if necessary)
        uint16 group = inode->BlockRun().AllocationGroup();
        uint16 start = 0;

        // Are there already allocated blocks? (then just try to allocate near the
        // last one)
        if (inode->Size() > 0) {
                const data_stream& data = inode->Node().data;
                // TODO: we currently don't care for when the data stream
                // is already grown into the indirect ranges
                if (data.max_double_indirect_range == 0
                        && data.max_indirect_range == 0) {
                        // Since size > 0, there must be a valid block run in this stream
                        int32 last = 0;
                        for (; last < NUM_DIRECT_BLOCKS - 1; last++)
                                if (data.direct[last + 1].IsZero())
                                        break;

                        group = data.direct[last].AllocationGroup();
                        start = data.direct[last].Start() + data.direct[last].Length();
                }
        } else if (inode->IsContainer() || inode->IsSymLink()) {
                // directory and symbolic link data will go in the same allocation
                // group as the inode is in but after the inode data
                start = inode->BlockRun().Start();
        } else {
                // file data will start in the next allocation group
                group = inode->BlockRun().AllocationGroup() + 1;
        }

        return AllocateBlocks(transaction, group, start, numBlocks, minimum, run);
}


/*!     Attempts to allocate a specific block run.
*/
status_t
BlockAllocator::AllocateBlockRun(Transaction& transaction, block_run run)
{
        RecursiveLocker lock(fLock);

        if (run.AllocationGroup() >= fNumGroups)
                return B_BAD_VALUE;

        if (!IsCompletelyInsideAllowedRange(run))
                return B_DEVICE_FULL;

        uint32 bitsPerBlock = fVolume->BlockSize() << 3;

        AllocationGroup& group = fGroups[run.AllocationGroup()];
        AllocationBlock cached(fVolume);

        int32 end = run.Start() + run.Length();

        // check that the requested blocks are free
        for (int32 block = run.Start(); block < end; block++) {
                if (cached.SetTo(group, block / bitsPerBlock) < B_OK)
                        RETURN_ERROR(B_ERROR);

                if (cached.IsUsed(block % bitsPerBlock))
                        return B_DEVICE_FULL;
        }

        status_t status = group.Allocate(transaction, run.Start(), run.Length());
        if (status != B_OK)
                return status;

        fVolume->SuperBlock().used_blocks
                = HOST_ENDIAN_TO_BFS_INT64(fVolume->UsedBlocks() + run.Length());

        return B_OK;
}


status_t
BlockAllocator::Free(Transaction& transaction, block_run run)
{
        RecursiveLocker lock(fLock);

        int32 group = run.AllocationGroup();
        uint16 start = run.Start();
        uint16 length = run.Length();

        FUNCTION_START(("group = %" B_PRId32 ", start = %" B_PRIu16
                ", length = %" B_PRIu16 "\n", group, start, length))
        T(Free(run));

        // doesn't use Volume::IsValidBlockRun() here because it can check better
        // against the group size (the last group may have a different length)
        if (group < 0 || group >= fNumGroups
                || start > fGroups[group].NumBits()
                || uint32(start + length) > fGroups[group].NumBits()
                || length == 0) {
                FATAL(("tried to free an invalid block_run"
                        " (%" B_PRId32 ", %" B_PRIu16 ", %" B_PRIu16")\n",
                        group, start, length));
                DEBUGGER(("tried to free invalid block_run"));
                return B_BAD_VALUE;
        }
        // check if someone tries to free reserved areas at the beginning of the
        // drive
        if (group < fVolume->Log().AllocationGroup()
                || (group == fVolume->Log().AllocationGroup()
                        && start < uint32(fVolume->Log().Start()) + fVolume->Log().Length())) {
                FATAL(("tried to free a reserved block_run"
                        " (%" B_PRId32 ", %" B_PRIu16 ", %" B_PRIu16")\n",
                        group, start, length));
                DEBUGGER(("tried to free reserved block"));
                return B_BAD_VALUE;
        }
#ifdef DEBUG
        if (CheckBlockRun(run) != B_OK)
                return B_BAD_DATA;
#endif

        CHECK_ALLOCATION_GROUP(group);

        if (fGroups[group].Free(transaction, start, length) != B_OK)
                RETURN_ERROR(B_IO_ERROR);

        CHECK_ALLOCATION_GROUP(group);

#ifdef DEBUG
        if (CheckBlockRun(run, NULL, false) != B_OK) {
                DEBUGGER(("CheckBlockRun() reports allocated blocks (which were just "
                        "freed)\n"));
        }
#endif

        fVolume->SuperBlock().used_blocks =
                HOST_ENDIAN_TO_BFS_INT64(fVolume->UsedBlocks() - run.Length());
        return B_OK;
}


#ifdef DEBUG_FRAGMENTER
void
BlockAllocator::Fragment()
{
        AllocationBlock cached(fVolume);
        RecursiveLocker lock(fLock);

        // only leave 4 block holes
        static const uint32 kMask = 0x0f0f0f0f;
        uint32 valuesPerBlock = fVolume->BlockSize() / 4;

        for (int32 i = 0; i < fNumGroups; i++) {
                AllocationGroup& group = fGroups[i];

                for (uint32 block = 0; block < group.NumBlocks(); block++) {
                        Transaction transaction(fVolume, 0);

                        if (cached.SetToWritable(transaction, group, block) != B_OK)
                                return;

                        for (int32 index = 0; index < valuesPerBlock; index++) {
                                cached.Block(index) |= HOST_ENDIAN_TO_BFS_INT32(kMask);
                        }

                        transaction.Done();
                }
        }
}
#endif  // DEBUG_FRAGMENTER


#ifdef DEBUG_ALLOCATION_GROUPS
void
BlockAllocator::_CheckGroup(int32 groupIndex) const
{
        AllocationBlock cached(fVolume);
        ASSERT_LOCKED_RECURSIVE(&fLock);

        AllocationGroup& group = fGroups[groupIndex];

        int32 currentStart = 0, currentLength = 0;
        int32 firstFree = -1;
        int32 largestStart = -1;
        int32 largestLength = 0;
        int32 currentBit = 0;

        for (uint32 block = 0; block < group.NumBlocks(); block++) {
                if (cached.SetTo(group, block) < B_OK) {
                        panic("setting group block %d failed\n", (int)block);
                        return;
                }

                for (uint32 bit = 0; bit < cached.NumBlockBits(); bit++) {
                        if (!cached.IsUsed(bit)) {
                                if (firstFree < 0) {
                                        firstFree = currentBit;
                                        if (!group.fLargestValid) {
                                                if (firstFree >= 0 && firstFree < group.fFirstFree) {
                                                        // mostly harmless but noteworthy
                                                        dprintf("group %d first free too late: should be "
                                                                "%d, is %d\n", (int)groupIndex, (int)firstFree,
                                                                (int)group.fFirstFree);
                                                }
                                                return;
                                        }
                                }

                                if (currentLength == 0) {
                                        // start new range
                                        currentStart = currentBit;
                                }
                                currentLength++;
                        } else if (currentLength) {
                                // end of a range
                                if (currentLength > largestLength) {
                                        largestStart = currentStart;
                                        largestLength = currentLength;
                                }
                                currentLength = 0;
                        }
                        currentBit++;
                }
        }

        if (currentLength > largestLength) {
                largestStart = currentStart;
                largestLength = currentLength;
        }

        if (firstFree >= 0 && firstFree < group.fFirstFree) {
                // mostly harmless but noteworthy
                dprintf("group %d first free too late: should be %d, is %d\n",
                        (int)groupIndex, (int)firstFree, (int)group.fFirstFree);
        }
        if (group.fLargestValid
                && (largestStart != group.fLargestStart
                        || largestLength != group.fLargestLength)) {
                panic("bfs %p: group %d largest differs: %d.%d, checked %d.%d.\n",
                        fVolume, (int)groupIndex, (int)group.fLargestStart,
                        (int)group.fLargestLength, (int)largestStart, (int)largestLength);
        }
}
#endif  // DEBUG_ALLOCATION_GROUPS


status_t
BlockAllocator::Trim(uint64 offset, uint64 size, uint64& trimmedSize)
{
        // TODO: Remove this check when offset and size handling is implemented
        if (offset != 0
                || fVolume->NumBlocks() < 0
                || size < (uint64)fVolume->NumBlocks() * fVolume->BlockSize()) {
                INFORM(("BFS Trim: Ranges smaller than the file system size"
                        " are not supported yet.\n"));
                return B_UNSUPPORTED;
        }

        const uint32 kTrimRanges = 128;
        fs_trim_data* trimData = (fs_trim_data*)malloc(sizeof(fs_trim_data)
                + 2 * sizeof(uint64) * (kTrimRanges - 1));
        if (trimData == NULL)
                return B_NO_MEMORY;

        MemoryDeleter deleter(trimData);
        RecursiveLocker locker(fLock);

        // TODO: take given offset and size into account!
        int32 lastGroup = fNumGroups - 1;
        uint32 firstBlock = 0;
        uint32 firstBit = 0;
        uint64 currentBlock = 0;
        uint32 blockShift = fVolume->BlockShift();

        uint64 firstFree = 0;
        uint64 freeLength = 0;

        trimData->range_count = 0;
        trimmedSize = 0;

        AllocationBlock cached(fVolume);
        for (int32 groupIndex = 0; groupIndex <= lastGroup; groupIndex++) {
                AllocationGroup& group = fGroups[groupIndex];

                for (uint32 block = firstBlock; block < group.NumBitmapBlocks(); block++) {
                        cached.SetTo(group, block);

                        for (uint32 i = firstBit; i < cached.NumBlockBits(); i++) {
                                if (cached.IsUsed(i)) {
                                        // Block is in use
                                        if (freeLength > 0) {
                                                // Overflow is unlikely to happen, but check it anyway
                                                if ((firstFree << blockShift) >> blockShift
                                                                != firstFree
                                                        || (freeLength << blockShift) >> blockShift
                                                                != freeLength) {
                                                        FATAL(("BlockAllocator::Trim:"
                                                                " Overflow detected!\n"));
                                                        return B_ERROR;
                                                }
                                                status_t status = _TrimNext(*trimData, kTrimRanges,
                                                        firstFree << blockShift, freeLength << blockShift,
                                                        false, trimmedSize);
                                                if (status != B_OK)
                                                        return status;

                                                freeLength = 0;
                                        }
                                } else if (freeLength++ == 0) {
                                        // Block is free, start new free range
                                        firstFree = currentBlock;
                                }

                                currentBlock++;
                        }
                }

                firstBlock = 0;
                firstBit = 0;
        }

        return _TrimNext(*trimData, kTrimRanges, firstFree << blockShift,
                freeLength << blockShift, true, trimmedSize);
}


//      #pragma mark -


/*!     Checks whether or not the specified block range is allocated or not,
        depending on the \a allocated argument.
*/
status_t
BlockAllocator::CheckBlocks(off_t start, off_t length, bool allocated,
        off_t* firstError)
{
        if (start < 0 || start + length > fVolume->NumBlocks())
                return B_BAD_VALUE;

        off_t block = start;

        int32 group = start >> fVolume->AllocationGroupShift();
        uint32 bitmapBlock = start / (fVolume->BlockSize() << 3);
        uint32 blockOffset = start % (fVolume->BlockSize() << 3);

        uint32 groupBlock = bitmapBlock % fBlocksPerGroup;

        AllocationBlock cached(fVolume);

        while (groupBlock < fGroups[group].NumBitmapBlocks() && length > 0) {
                if (cached.SetTo(fGroups[group], groupBlock) != B_OK)
                        RETURN_ERROR(B_IO_ERROR);

                for (; blockOffset < cached.NumBlockBits() && length > 0;
                                blockOffset++, length--, block++) {
                        if (cached.IsUsed(blockOffset) != allocated) {
                                PRINT(("CheckBlocks: Erroneous block (group = %" B_PRId32
                                        ", groupBlock = %" B_PRIu32
                                        ", blockOffset = %" B_PRIu32 ")!\n",
                                        group, groupBlock, blockOffset));

                                if (firstError)
                                        *firstError = block;

                                return B_BAD_DATA;
                        }
                }

                blockOffset = 0;

                if (++groupBlock >= fGroups[group].NumBitmapBlocks()) {
                        groupBlock = 0;
                        group++;
                }
        }

        return B_OK;
}


bool
BlockAllocator::IsValidBlockRun(block_run run, const char* type)
{
        if (run.AllocationGroup() < 0 || run.AllocationGroup() >= fNumGroups
                || run.Start() > fGroups[run.AllocationGroup()].fNumBits
                || uint32(run.Start() + run.Length())
                                > fGroups[run.AllocationGroup()].fNumBits
                || run.length == 0) {
                PRINT(("%s: block_run(%" B_PRId32 ", %" B_PRIu16 ", %" B_PRIu16")"
                        " is invalid!\n", type, run.AllocationGroup(), run.Start(),
                        run.Length()));
                return false;
        }
        return true;
}


status_t
BlockAllocator::CheckBlockRun(block_run run, const char* type, bool allocated)
{
        if (!IsValidBlockRun(run, type))
                return B_BAD_DATA;

        status_t status = CheckBlocks(fVolume->ToBlock(run), run.Length(),
                allocated);
        if (status != B_OK) {
                PRINT(("%s: block_run(%" B_PRId32 ", %" B_PRIu16 ", %" B_PRIu16")"
                        " is only partially allocated!\n", type, run.AllocationGroup(),
                        run.Start(), run.Length()));
        }

        return status;
}


bool
BlockAllocator::_AddTrim(fs_trim_data& trimData, uint32 maxRanges,
        uint64 offset, uint64 size)
{
        ASSERT(trimData.range_count < maxRanges);
        if (size == 0)
                return false;

        trimData.ranges[trimData.range_count].offset = offset;
        trimData.ranges[trimData.range_count].size = size;
        trimData.range_count++;

        return (trimData.range_count == maxRanges);
}


status_t
BlockAllocator::_TrimNext(fs_trim_data& trimData, uint32 maxRanges,
        uint64 offset, uint64 size, bool force, uint64& trimmedSize)
{
        PRINT(("_TrimNext(index %" B_PRIu32 ", offset %" B_PRIu64 ", size %"
                B_PRIu64 ")\n", trimData.range_count, offset, size));

        const bool rangesFilled = _AddTrim(trimData, maxRanges, offset, size);

        if (rangesFilled || force) {
                // Trim now
                trimData.trimmed_size = 0;
#ifdef DEBUG_TRIM
                dprintf("TRIM: BFS: free ranges (bytes):\n");
                for (uint32 i = 0; i < trimData.range_count; i++) {
                        dprintf("[%3" B_PRIu32 "] %" B_PRIu64 " : %" B_PRIu64 "\n", i,
                                trimData.ranges[i].offset, trimData.ranges[i].size);
                }
#endif
                if (ioctl(fVolume->Device(), B_TRIM_DEVICE, &trimData,
                                sizeof(fs_trim_data)
                                        + 2 * sizeof(uint64) * (trimData.range_count - 1)) != 0) {
                        return errno;
                }

                trimmedSize += trimData.trimmed_size;
                trimData.range_count = 0;
        }

        return B_OK;
}


//      #pragma mark - debugger commands


#ifdef BFS_DEBUGGER_COMMANDS

void
BlockAllocator::Dump(int32 index)
{
        kprintf("allocation groups: %" B_PRId32 " (base %p)\n", fNumGroups, fGroups);
        kprintf("blocks per group: %" B_PRId32 "\n", fBlocksPerGroup);

        for (int32 i = 0; i < fNumGroups; i++) {
                if (index != -1 && i != index)
                        continue;

                AllocationGroup& group = fGroups[i];

                kprintf("[%3" B_PRId32 "] num bits:       %" B_PRIu32 "  (%p)\n", i,
                        group.NumBits(), &group);
                kprintf("      num blocks:     %" B_PRIu32 "\n", group.NumBitmapBlocks());
                kprintf("      start:          %" B_PRId32 "\n", group.Start());
                kprintf("      first free:     %" B_PRId32 "\n", group.fFirstFree);
                kprintf("      largest start:  %" B_PRId32 "%s\n", group.fLargestStart,
                        group.fLargestValid ? "" : "  (invalid)");
                kprintf("      largest length: %" B_PRId32 "\n", group.fLargestLength);
                kprintf("      free bits:      %" B_PRId32 "\n", group.fFreeBits);
        }
}


#if BFS_TRACING
static char kTraceBuffer[256];


int
dump_block_allocator_blocks(int argc, char** argv)
{
        if (argc != 3 || !strcmp(argv[1], "--help")) {
                kprintf("usage: %s <ptr-to-volume> <block>\n", argv[0]);
                return 0;
        }

        Volume* volume = (Volume*)parse_expression(argv[1]);
        off_t block = parse_expression(argv[2]);

        // iterate over all tracing entries to find overlapping actions

        using namespace BFSBlockTracing;

        LazyTraceOutput out(kTraceBuffer, sizeof(kTraceBuffer), 0);
        TraceEntryIterator iterator;
        while (TraceEntry* _entry = iterator.Next()) {
                if (Allocate* entry = dynamic_cast<Allocate*>(_entry)) {
                        off_t first = volume->ToBlock(entry->Run());
                        off_t last = first - 1 + entry->Run().Length();
                        if (block >= first && block <= last) {
                                out.Clear();
                                const char* dump = out.DumpEntry(entry);
                                kprintf("%5ld. %s\n", iterator.Index(), dump);
                        }
                } else if (Free* entry = dynamic_cast<Free*>(_entry)) {
                        off_t first = volume->ToBlock(entry->Run());
                        off_t last = first - 1 + entry->Run().Length();
                        if (block >= first && block <= last) {
                                out.Clear();
                                const char* dump = out.DumpEntry(entry);
                                kprintf("%5ld. %s\n", iterator.Index(), dump);
                        }
                }
        }

        return 0;
}
#endif


int
dump_block_allocator(int argc, char** argv)
{
        int32 group = -1;
        if (argc == 3) {
                group = parse_expression(argv[2]);
                argc--;
        }

        if (argc != 2 || !strcmp(argv[1], "--help")) {
                kprintf("usage: %s <ptr-to-volume> [group]\n", argv[0]);
                return 0;
        }

        Volume* volume = (Volume*)parse_expression(argv[1]);
        BlockAllocator& allocator = volume->Allocator();

        allocator.Dump(group);
        return 0;
}

#endif  // BFS_DEBUGGER_COMMANDS