/*
 * Copyright 2022, Raghav Sharma, raghavself28@gmail.com
 * Copyright 2020, Shubham Bhagat, shubhambhagat111@yahoo.com
 * All rights reserved. Distributed under the terms of the MIT License.
 */


#include "LeafDirectory.h"

#include "Utility.h"
#include "VerifyHeader.h"


LeafDirectory::LeafDirectory(Inode* inode)
        :
        fInode(inode),
        fDataMap(NULL),
        fLeafMap(NULL),
        fOffset(0),
        fDataBuffer(NULL),
        fLeafBuffer(NULL),
        fCurBlockNumber(-1)
{
}


LeafDirectory::~LeafDirectory()
{
        delete fDataMap;
        delete fLeafMap;
        delete fDataBuffer;
        delete fLeafBuffer;
}


status_t
LeafDirectory::Init()
{
        fLeafMap = new(std::nothrow) ExtentMapEntry;
        if (fLeafMap == NULL)
                return B_NO_MEMORY;

        fDataMap = new(std::nothrow) ExtentMapEntry;
        if (fDataMap == NULL)
                return B_NO_MEMORY;

        FillMapEntry(fInode->DataExtentsCount()-1, fLeafMap);
        FillMapEntry(0, fDataMap);

        // check data buffer
        status_t status = FillBuffer(DATA, fDataBuffer, 0);
        if (status != B_OK)
                return status;
        ExtentDataHeader* data = ExtentDataHeader::Create(fInode, fDataBuffer);
        if (data == NULL)
                return B_NO_MEMORY;
        if (!VerifyHeader<ExtentDataHeader>(data, fDataBuffer, fInode, 0, fDataMap, XFS_LEAF)) {
                ERROR("Invalid data header");
                delete data;
                return B_BAD_VALUE;
        }
        delete data;

        // check leaf buffer
        status = FillBuffer(LEAF, fLeafBuffer, 0);
        if (status != B_OK)
                return status;
        ExtentLeafHeader* leaf = ExtentLeafHeader::Create(fInode, fLeafBuffer);
        if (leaf == NULL)
                return B_NO_MEMORY;
        if (!VerifyHeader<ExtentLeafHeader>(leaf, fLeafBuffer, fInode, 0, fLeafMap, XFS_LEAF)) {
                ERROR("Invalid leaf header");
                delete leaf;
                return B_BAD_VALUE;
        }
        delete leaf;

        return B_OK;
}


bool
LeafDirectory::IsLeafType()
{
        bool status = true;
        if (fInode->BlockCount() == 1
                || fInode->DataExtentsCount() == 1
                || (uint64) fInode->Size() !=
                        (fInode->BlockCount() - 1) * fInode->DirBlockSize())
                status = false;

        if (status == false)
                return status;

        void* directoryFork = DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize());

        uint64* pointerToMap = (uint64*)((char*)directoryFork
                + (fInode->DataExtentsCount() - 1) * EXTENT_SIZE);

        xfs_fileoff_t startoff = (B_BENDIAN_TO_HOST_INT64(*pointerToMap) & MASK(63)) >> 9;

        if (startoff != LEAF_STARTOFFSET(fInode->GetVolume()->BlockLog()))
                status = false;

        return status;
}


void
LeafDirectory::FillMapEntry(int num, ExtentMapEntry* fMap)
{
        void* directoryFork = DIR_DFORK_PTR(fInode->Buffer(), fInode->CoreInodeSize());

        uint64* pointerToMap = (uint64*)((char*)directoryFork + num * EXTENT_SIZE);
        uint64 firstHalf = pointerToMap[0];
        uint64 secondHalf = pointerToMap[1];
                //dividing the 128 bits into 2 parts.

        firstHalf = B_BENDIAN_TO_HOST_INT64(firstHalf);
        secondHalf = B_BENDIAN_TO_HOST_INT64(secondHalf);
        fMap->br_state = firstHalf >> 63;
        fMap->br_startoff = (firstHalf & MASK(63)) >> 9;
        fMap->br_startblock = ((firstHalf & MASK(9)) << 43) | (secondHalf >> 21);
        fMap->br_blockcount = secondHalf & MASK(21);
        TRACE("Extent::Init: startoff:(%" B_PRIu64 "), startblock:(%" B_PRIu64 "),"
                "blockcount:(%" B_PRIu64 "),state:(%" B_PRIu8 ")\n", fMap->br_startoff, fMap->br_startblock,
                fMap->br_blockcount, fMap->br_state);
}


status_t
LeafDirectory::FillBuffer(int type, char* blockBuffer, int howManyBlocksFurthur)
{
        TRACE("FILLBUFFER\n");
        ExtentMapEntry* map;
        if (type == DATA)
                map = fDataMap;
        else if (type == LEAF)
                map = fLeafMap;
        else
                return B_BAD_VALUE;

        if (map->br_state !=0)
                return B_BAD_VALUE;

        int len = fInode->DirBlockSize();
        if (blockBuffer == NULL) {
                blockBuffer = new(std::nothrow) char[len];
                if (blockBuffer == NULL)
                        return B_NO_MEMORY;
        }

        xfs_daddr_t readPos =
                fInode->FileSystemBlockToAddr(map->br_startblock + howManyBlocksFurthur);

        if (read_pos(fInode->GetVolume()->Device(), readPos, blockBuffer, len)
                != len) {
                ERROR("LeafDirectory::FillBlockBuffer(): IO Error");
                return B_IO_ERROR;
        }

        if (type == DATA) {
                fDataBuffer = blockBuffer;
        } else if (type == LEAF) {
                fLeafBuffer = blockBuffer;
                ExtentLeafHeader* header = ExtentLeafHeader::Create(fInode, fLeafBuffer);
                if (header == NULL)
                        return B_NO_MEMORY;
                TRACE("NumberOfEntries in leaf: (%" B_PRIu16 ")\n", header->Count());
                delete header;
        }
        return B_OK;
}


uint32
LeafDirectory::GetOffsetFromAddress(uint32 address)
{
        address = address * 8;
                // block offset in eight bytes, hence multiply with 8
        return address & (fInode->DirBlockSize() - 1);
}


ExtentLeafEntry*
LeafDirectory::FirstLeaf()
{
        TRACE("LeafDirectory: FirstLeaf\n");
        if (fLeafBuffer == NULL) {
                ASSERT(fLeafMap != NULL);
                status_t status = FillBuffer(LEAF, fLeafBuffer, 0);
                if (status != B_OK)
                        return NULL;
        }
        return (ExtentLeafEntry*)((char*)fLeafBuffer + ExtentLeafHeader::Size(fInode));
}


int
LeafDirectory::EntrySize(int len) const
{
        int entrySize = sizeof(xfs_ino_t) + sizeof(uint8) + len + sizeof(uint16);
                // uint16 is for the tag
        if (fInode->HasFileTypeField())
                entrySize += sizeof(uint8);

        return (entrySize + 7) & -8;
                // rounding off to closest multiple of 8
}


void
LeafDirectory::SearchAndFillDataMap(uint64 blockNo)
{
        int len = fInode->DataExtentsCount();

        for(int i = 0; i < len - 1; i++) {
                FillMapEntry(i, fDataMap);
                if (fDataMap->br_startoff <= blockNo
                        && (blockNo <= fDataMap->br_startoff + fDataMap->br_blockcount - 1))
                        // Map found
                        return;
        }
}


status_t
LeafDirectory::Rewind()
{
        fOffset = 0;
        fCurBlockNumber = -1;
        return B_OK;
}


status_t
LeafDirectory::GetNext(char* name, size_t* length, xfs_ino_t* ino)
{
        TRACE("LeafDirectory::GetNext\n");
        status_t status;

        if (fDataBuffer == NULL) {
                status = FillBuffer(DATA, fDataBuffer, 0);
                if (status != B_OK)
                        return status;
        }

        Volume* volume = fInode->GetVolume();

        void* entry; // This could be unused entry so we should check

        entry = (void*)(fDataBuffer + ExtentDataHeader::Size(fInode));

        uint32 blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume);
        if (fOffset != 0 && blockNoFromAddress == fCurBlockNumber)
                entry = (void*)(fDataBuffer
                                + BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode));
                // This gets us a little faster to the next entry

        uint32 curDirectorySize = fInode->Size();

        while (fOffset != curDirectorySize) {
                blockNoFromAddress = BLOCKNO_FROM_ADDRESS(fOffset, volume);

                TRACE("fOffset:(%" B_PRIu32 "), blockNoFromAddress:(%" B_PRIu32 ")\n",
                        fOffset, blockNoFromAddress);
                if (fCurBlockNumber != blockNoFromAddress
                        && blockNoFromAddress > fDataMap->br_startoff
                        && blockNoFromAddress
                                <= fDataMap->br_startoff + fDataMap->br_blockcount - 1) {
                        // When the block is mapped in the same data
                        // map entry but is not the first block
                        status = FillBuffer(DATA, fDataBuffer,
                                blockNoFromAddress - fDataMap->br_startoff);
                        if (status != B_OK)
                                return status;
                        entry = (void*)(fDataBuffer + ExtentDataHeader::Size(fInode));
                        fOffset = fOffset + ExtentDataHeader::Size(fInode);
                        fCurBlockNumber = blockNoFromAddress;
                } else if (fCurBlockNumber != blockNoFromAddress) {
                        // When the block isn't mapped in the current data map entry
                        SearchAndFillDataMap(blockNoFromAddress);
                        status = FillBuffer(DATA, fDataBuffer,
                                blockNoFromAddress - fDataMap->br_startoff);
                        if (status != B_OK)
                                return status;
                        entry = (void*)(fDataBuffer + ExtentDataHeader::Size(fInode));
                        fOffset = fOffset + ExtentDataHeader::Size(fInode);
                        fCurBlockNumber = blockNoFromAddress;
                }

                ExtentUnusedEntry* unusedEntry = (ExtentUnusedEntry*)entry;

                if (B_BENDIAN_TO_HOST_INT16(unusedEntry->freetag) == DIR2_FREE_TAG) {
                        TRACE("Unused entry found\n");
                        fOffset = fOffset + B_BENDIAN_TO_HOST_INT16(unusedEntry->length);
                        entry = (void*)
                                ((char*)entry + B_BENDIAN_TO_HOST_INT16(unusedEntry->length));
                        continue;
                }
                ExtentDataEntry* dataEntry = (ExtentDataEntry*) entry;

                uint16 currentOffset = (char*)dataEntry - fDataBuffer;
                TRACE("GetNext: fOffset:(%" B_PRIu32 "), currentOffset:(%" B_PRIu16 ")\n",
                        BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode), currentOffset);

                if (BLOCKOFFSET_FROM_ADDRESS(fOffset, fInode) > currentOffset) {
                        entry = (void*)((char*)entry + EntrySize(dataEntry->namelen));
                        continue;
                }

                if ((size_t)(dataEntry->namelen) >= *length)
                        return B_BUFFER_OVERFLOW;

                fOffset = fOffset + EntrySize(dataEntry->namelen);
                memcpy(name, dataEntry->name, dataEntry->namelen);
                name[dataEntry->namelen] = '\0';
                *length = dataEntry->namelen + 1;
                *ino = B_BENDIAN_TO_HOST_INT64(dataEntry->inumber);

                TRACE("Entry found. Name: (%s), Length: (%" B_PRIuSIZE "),ino: (%" B_PRIu64 ")\n",
                        name, *length, *ino);
                return B_OK;
        }

        return B_ENTRY_NOT_FOUND;
}


status_t
LeafDirectory::Lookup(const char* name, size_t length, xfs_ino_t* ino)
{
        TRACE("LeafDirectory: Lookup\n");
        TRACE("Name: %s\n", name);
        uint32 hashValueOfRequest = hashfunction(name, length);
        TRACE("Hashval:(%" B_PRIu32 ")\n", hashValueOfRequest);

        status_t status = B_OK;
        if (fLeafBuffer == NULL)
                status = FillBuffer(LEAF, fLeafBuffer, 0);
        if (status != B_OK)
                return status;

        ExtentLeafHeader* leafHeader = ExtentLeafHeader::Create(fInode, fLeafBuffer);
        if (leafHeader == NULL)
                return B_NO_MEMORY;

        ExtentLeafEntry* leafEntry = FirstLeaf();
        if (leafEntry == NULL)
                return B_NO_MEMORY;

        int numberOfLeafEntries = leafHeader->Count();
        TRACE("numberOfLeafEntries:(%" B_PRId32 ")\n", numberOfLeafEntries);
        int left = 0;
        int right = numberOfLeafEntries - 1;
        Volume* volume = fInode->GetVolume();

        hashLowerBound<ExtentLeafEntry>(leafEntry, left, right, hashValueOfRequest);

        while (B_BENDIAN_TO_HOST_INT32(leafEntry[left].hashval)
                        == hashValueOfRequest) {

                uint32 address = B_BENDIAN_TO_HOST_INT32(leafEntry[left].address);
                if (address == 0) {
                        left++;
                        continue;
                }

                uint32 dataBlockNumber = BLOCKNO_FROM_ADDRESS(address * 8, volume);
                uint32 offset = BLOCKOFFSET_FROM_ADDRESS(address * 8, fInode);

                TRACE("DataBlockNumber:(%" B_PRIu32 "), offset:(%" B_PRIu32 ")\n", dataBlockNumber, offset);
                if (dataBlockNumber != fCurBlockNumber) {
                        fCurBlockNumber = dataBlockNumber;
                        SearchAndFillDataMap(dataBlockNumber);
                        status = FillBuffer(DATA, fDataBuffer,
                                dataBlockNumber - fDataMap->br_startoff);
                        if (status != B_OK)
                                return status;
                }

                TRACE("offset:(%" B_PRIu32 ")\n", offset);
                ExtentDataEntry* entry = (ExtentDataEntry*)(fDataBuffer + offset);

                if (xfs_name_comp(name, length, entry->name, entry->namelen)) {
                        *ino = B_BENDIAN_TO_HOST_INT64(entry->inumber);
                        TRACE("ino:(%" B_PRIu64 ")\n", *ino);
                        return B_OK;
                }
                left++;
        }

        delete leafHeader;

        return B_ENTRY_NOT_FOUND;
}


ExtentLeafHeader::~ExtentLeafHeader()
{
}


/*
        First see which type of directory we reading then
        return magic number as per Inode Version.
*/
uint32
ExtentLeafHeader::ExpectedMagic(int8 WhichDirectory, Inode* inode)
{
        if (WhichDirectory == XFS_LEAF) {
                if (inode->Version() == 1 || inode->Version() == 2)
                        return V4_LEAF_HEADER_MAGIC;
                else
                        return V5_LEAF_HEADER_MAGIC;
        } else {
                if (inode->Version() == 1 || inode->Version() == 2)
                        return XFS_DIR2_LEAFN_MAGIC;
                else
                        return XFS_DIR3_LEAFN_MAGIC;
        }
}


uint32
ExtentLeafHeader::CRCOffset()
{
        return offsetof(ExtentLeafHeaderV5::OnDiskData, info.crc);
}


ExtentLeafHeader*
ExtentLeafHeader::Create(Inode* inode, const char* buffer)
{
        if (inode->Version() == 1 || inode->Version() == 2) {
                ExtentLeafHeaderV4* header = new (std::nothrow) ExtentLeafHeaderV4(buffer);
                return header;
        } else {
                ExtentLeafHeaderV5* header = new (std::nothrow) ExtentLeafHeaderV5(buffer);
                return header;
        }
}


/*
        This Function returns Actual size of leaf header
        in all forms of directory.
        Never use sizeof() operator because we now have
        vtable as well and it will give wrong results
*/
uint32
ExtentLeafHeader::Size(Inode* inode)
{
        if (inode->Version() == 1 || inode->Version() == 2)
                return sizeof(ExtentLeafHeaderV4::OnDiskData);
        else
                return sizeof(ExtentLeafHeaderV5::OnDiskData);
}


void
ExtentLeafHeaderV4::SwapEndian()
{
        fData.info.forw =       B_BENDIAN_TO_HOST_INT32(fData.info.forw);
        fData.info.back =       B_BENDIAN_TO_HOST_INT32(fData.info.back);
        fData.info.magic        =       B_BENDIAN_TO_HOST_INT16(fData.info.magic);
        fData.info.pad  =       B_BENDIAN_TO_HOST_INT16(fData.info.pad);
        fData.count             =       B_BENDIAN_TO_HOST_INT16(fData.count);
        fData.stale             =       B_BENDIAN_TO_HOST_INT16(fData.stale);
}


ExtentLeafHeaderV4::ExtentLeafHeaderV4(const char* buffer)
{
        memcpy(&fData, buffer, sizeof(fData));
        SwapEndian();
}


ExtentLeafHeaderV4::~ExtentLeafHeaderV4()
{
}


uint16
ExtentLeafHeaderV4::Magic()
{
        return fData.info.magic;
}


uint64
ExtentLeafHeaderV4::Blockno()
{
        return B_BAD_VALUE;
}


uint64
ExtentLeafHeaderV4::Lsn()
{
        return B_BAD_VALUE;
}


uint64
ExtentLeafHeaderV4::Owner()
{
        return B_BAD_VALUE;
}


const uuid_t&
ExtentLeafHeaderV4::Uuid()
{
        static uuid_t nullUuid = {0};
        return nullUuid;
}


uint16
ExtentLeafHeaderV4::Count()
{
        return fData.count;
}


uint32
ExtentLeafHeaderV4::Forw()
{
        return fData.info.forw;
}


void
ExtentLeafHeaderV5::SwapEndian()
{
        fData.info.forw         =       B_BENDIAN_TO_HOST_INT32(fData.info.forw);
        fData.info.back         =       B_BENDIAN_TO_HOST_INT32(fData.info.back);
        fData.info.magic        =       B_BENDIAN_TO_HOST_INT16(fData.info.magic);
        fData.info.pad          =       B_BENDIAN_TO_HOST_INT16(fData.info.pad);
        fData.info.blkno        =       B_BENDIAN_TO_HOST_INT64(fData.info.blkno);
        fData.info.lsn          =       B_BENDIAN_TO_HOST_INT64(fData.info.lsn);
        fData.info.owner        =       B_BENDIAN_TO_HOST_INT64(fData.info.owner);
        fData.count                     =       B_BENDIAN_TO_HOST_INT16(fData.count);
        fData.stale                     =       B_BENDIAN_TO_HOST_INT16(fData.stale);
        fData.pad                       =       B_BENDIAN_TO_HOST_INT32(fData.pad);
}


ExtentLeafHeaderV5::ExtentLeafHeaderV5(const char* buffer)
{
        memcpy(&fData, buffer, sizeof(fData));
        SwapEndian();
}


ExtentLeafHeaderV5::~ExtentLeafHeaderV5()
{
}


uint16
ExtentLeafHeaderV5::Magic()
{
        return fData.info.magic;
}


uint64
ExtentLeafHeaderV5::Blockno()
{
        return fData.info.blkno;
}


uint64
ExtentLeafHeaderV5::Lsn()
{
        return fData.info.lsn;
}


uint64
ExtentLeafHeaderV5::Owner()
{
        return fData.info.owner;
}


const uuid_t&
ExtentLeafHeaderV5::Uuid()
{
        return fData.info.uuid;
}


uint16
ExtentLeafHeaderV5::Count()
{
        return fData.count;
}


uint32
ExtentLeafHeaderV5::Forw()
{
        return fData.info.forw;
}