Index: /trunk/include/iprt/formats/xfs.h =================================================================== --- /trunk/include/iprt/formats/xfs.h (revision 77007) +++ /trunk/include/iprt/formats/xfs.h (revision 77008) @@ -442,5 +442,5 @@ /** 0x40: Number of direct and B-Tree blocks used for the forks. */ uint64_t cBlocks; - /** 0x48: Minimum exten size for the inode. */ + /** 0x48: Minimum extent size for the inode. */ uint32_t cExtentBlocksMin; /** 0x4c: Number of extents in the data fork. */ @@ -634,4 +634,76 @@ +/** + * XFS B+Tree root header. + */ +typedef struct XFSBTREEROOTHDR +{ + /** 0x00: Tree level. */ + uint16_t iLvl; + /** 0x02: Number of records. */ + uint16_t cRecs; +} XFSBTREEROOTHDR; +/** Pointer to a B+Tree root header */ +typedef XFSBTREEROOTHDR *PXFSBTREEROOTHDR; +/** Pointer to a const B+Tree root header. */ +typedef const XFSBTREEROOTHDR *PCXFSBTREEROOTHDR; + + +/** + * XFS B+Tree intermediate/leave node header. + */ +typedef struct XFSBTREENODEHDR +{ + /** 0x00: Magic identifying the node. */ + uint32_t u32Magic; + /** 0x04: Tree level. */ + uint16_t iLvl; + /** 0x06: Number of records. */ + uint16_t cRecs; + /** 0x08: Block number of the left sibling. */ + uint64_t uSibLeft; + /** 0x10: Block number of the right sibling. */ + uint64_t uSibRight; +} XFSBTREENODEHDR; +/** Pointer to a B+Tree intermediate/leave node header. */ +typedef XFSBTREENODEHDR *PXFSBTREENODEHDR; +/** Pointer to a const B+Tree intermediate/leave node header. */ +typedef const XFSBTREENODEHDR *PCXFSBTREENODEHDR; + +/** @name XFS_BTREENODEHDR_XXX - B+Tree node related defines. + * @{ */ +/** Magic for the tree node header. */ +#define XFS_BTREENODEHDR_MAGIC RT_MAKE_U32_FROM_U8('P', 'A', 'M', 'B') +/** @} */ + + +/** + * XFS Extent. + */ +typedef struct XFSEXTENT +{ + /** 0x00: Low 64 bits. */ + uint64_t u64Low; + /** 0x08: High 64 bits. */ + uint64_t u64High; +} XFSEXTENT; +/** Pointer to an XFS extent. */ +typedef XFSEXTENT *PXFSEXTENT; +/** Pointer to a const XFS extent. */ +typedef const XFSEXTENT *PCXFSEXTENT; + +/** @name XFS_EXTENT_XXX - Extent related getters. + * @{ */ +/** Returns whether the extent is allocated but unwritten (true) or a normal extent (false). */ +#define XFS_EXTENT_IS_UNWRITTEN(a_pExtent) (RT_BOOL((a_pExtent)->u64High & RT_BIT_64(63))) +/** Returns the number of blocks the extent covers. */ +#define XFS_EXTENT_GET_BLOCK_COUNT(a_pExtent) ((a_pExtent)->u64Low & UINT64_C(0x1fffff)) +/** Returns the absolute block number where the data is stored on the disk. */ +#define XFS_EXTENT_GET_DISK_BLOCK(a_pExtent) ( (((a_pExtent)->u64High & UINT64_C(0x1ff)) << 42) \ + | (((a_pExtent)->u64Low & UINT64_C(0xffffffffffe00000)) >> 21)) +/** Returns the logical inode block offset. */ +#define XFS_EXTENT_GET_LOGICAL_BLOCK(a_pExtent) (((a_pExtent)->u64High & UINT64_C(0x7ffffffffffffe00)) >> 9) +/** @} */ + /** @} */ Index: /trunk/src/VBox/Runtime/common/fs/xfsvfs.cpp =================================================================== --- /trunk/src/VBox/Runtime/common/fs/xfsvfs.cpp (revision 77007) +++ /trunk/src/VBox/Runtime/common/fs/xfsvfs.cpp (revision 77008) @@ -112,4 +112,10 @@ /** Inode flags. */ uint16_t fFlags; + /** Inode version. */ + uint8_t uVersion; + /** Number of extents in the data fork for XFS_INODE_FORMAT_EXTENTS. */ + uint32_t cExtentsData; + /** Raw inode data. */ + uint8_t abData[1]; } RTFSXFSINODE; /** Pointer to an in-memory inode. */ @@ -329,5 +335,5 @@ } - +#if 0 /* unused */ /** * Logs a AG free space block. @@ -367,5 +373,5 @@ } } - +#endif /** @@ -541,4 +547,37 @@ /** + * Returns the size of the core inode structure on disk for the given version. + * + * @returns Size of the on disk inode structure in bytes. + * @param uVersion The inode version. + */ +DECLINLINE(size_t) rtFsXfsInodeGetSz(uint8_t uVersion) +{ + if (uVersion < 3) + return RT_OFFSETOF(XFSINODECORE, uChkSum); + return sizeof(XFSINODECORE); +} + + +/** + * Returns the pointer to the data fork of the given inode. + * + * @returns Pointer to the data fork. + * @param pThis The XFS volume instance. + * @param pInode The inode to get the data fork for. + * @param pcb Where to store the size of the remaining data area beginning with the fork. + */ +DECLINLINE(void *) rtFsXfsInodeGetDataFork(PRTFSXFSVOL pThis, PRTFSXFSINODE pInode, size_t *pcb) +{ + size_t offDataFork = rtFsXfsInodeGetSz(pInode->uVersion); + size_t cbInodeData = pThis->cbInode - offDataFork; + if (pcb) + *pcb = cbInodeData; + + return &pInode->abData[offDataFork]; +} + + +/** * Allocates a new block group. * @@ -696,5 +735,5 @@ } - +#if 0 /* unused */ /** * Allocates a new alloction group. @@ -850,5 +889,5 @@ rtFsXfsAg_Free(pThis, pAg); } - +#endif /** @@ -861,10 +900,11 @@ static PRTFSXFSINODE rtFsXfsInode_Alloc(PRTFSXFSVOL pThis, uint32_t iInode) { - PRTFSXFSINODE pInode = (PRTFSXFSINODE)RTMemAllocZ(sizeof(RTFSXFSINODE)); + size_t cbAlloc = RT_UOFFSETOF_DYN(RTFSXFSINODE, abData[pThis->cbInode]); + PRTFSXFSINODE pInode = (PRTFSXFSINODE)RTMemAllocZ(cbAlloc); if (RT_LIKELY(pInode)) { pInode->Core.Key = iInode; pInode->cRefs = 0; - pThis->cbInodes += sizeof(RTFSXFSINODE); + pThis->cbInodes += cbAlloc; } @@ -899,5 +939,5 @@ Assert(pCore == &pInode->Core); RT_NOREF(pCore); RTMemFree(pInode); - pThis->cbInodes -= sizeof(RTFSXFSINODE); + pThis->cbInodes -= RT_UOFFSETOF_DYN(RTFSXFSINODE, abData[pThis->cbInode]); } } @@ -914,5 +954,5 @@ { PRTFSXFSINODE pInode = NULL; - if (pThis->cbInodes + sizeof(RTFSXFSINODE) <= RTFSXFS_MAX_INODE_CACHE_SIZE) + if (pThis->cbInodes + RT_UOFFSETOF_DYN(RTFSXFSINODE, abData[pThis->cbInode]) <= RTFSXFS_MAX_INODE_CACHE_SIZE) pInode = rtFsXfsInode_Alloc(pThis, iInode); else @@ -964,36 +1004,38 @@ uint64_t offRead = (iAg * pThis->cBlocksPerAg + uBlock) * pThis->cbBlock + offBlock; - XFSINODECORE Inode; - rc = RTVfsFileReadAt(pThis->hVfsBacking, offRead, &Inode, RT_MIN(sizeof(Inode), pThis->cbInode), NULL); + rc = RTVfsFileReadAt(pThis->hVfsBacking, offRead, &pInode->abData[0], pThis->cbInode, NULL); if (RT_SUCCESS(rc)) { + PCXFSINODECORE pInodeCore = (PCXFSINODECORE)&pInode->abData[0]; + #ifdef LOG_ENABLED - rtFsXfsInode_Log(pThis, iInode, &Inode); + rtFsXfsInode_Log(pThis, iInode, pInodeCore); #endif pInode->offInode = offRead; - pInode->fFlags = RT_BE2H_U16(Inode.fFlags); - pInode->enmFormat = Inode.enmFormat; - pInode->ObjInfo.cbObject = RT_BE2H_U64(Inode.cbInode); - pInode->ObjInfo.cbAllocated = RT_BE2H_U64(Inode.cBlocks) * pThis->cbBlock; - RTTimeSpecSetSeconds(&pInode->ObjInfo.AccessTime, RT_BE2H_U32(Inode.TsLastAccessed.cSecEpoch)); - RTTimeSpecAddNano(&pInode->ObjInfo.AccessTime, RT_BE2H_U32(Inode.TsLastAccessed.cNanoSec)); - RTTimeSpecSetSeconds(&pInode->ObjInfo.ModificationTime, RT_BE2H_U32(Inode.TsLastModified.cSecEpoch)); - RTTimeSpecAddNano(&pInode->ObjInfo.ModificationTime, RT_BE2H_U32(Inode.TsLastModified.cNanoSec)); - RTTimeSpecSetSeconds(&pInode->ObjInfo.ChangeTime, RT_BE2H_U32(Inode.TsCreatedModified.cSecEpoch)); - RTTimeSpecAddNano(&pInode->ObjInfo.ChangeTime, RT_BE2H_U32(Inode.TsCreatedModified.cNanoSec)); + pInode->fFlags = RT_BE2H_U16(pInodeCore->fFlags); + pInode->enmFormat = pInodeCore->enmFormat; + pInode->cExtentsData = RT_BE2H_U32(pInodeCore->cExtentsData); + pInode->ObjInfo.cbObject = RT_BE2H_U64(pInodeCore->cbInode); + pInode->ObjInfo.cbAllocated = RT_BE2H_U64(pInodeCore->cBlocks) * pThis->cbBlock; + RTTimeSpecSetSeconds(&pInode->ObjInfo.AccessTime, RT_BE2H_U32(pInodeCore->TsLastAccessed.cSecEpoch)); + RTTimeSpecAddNano(&pInode->ObjInfo.AccessTime, RT_BE2H_U32(pInodeCore->TsLastAccessed.cNanoSec)); + RTTimeSpecSetSeconds(&pInode->ObjInfo.ModificationTime, RT_BE2H_U32(pInodeCore->TsLastModified.cSecEpoch)); + RTTimeSpecAddNano(&pInode->ObjInfo.ModificationTime, RT_BE2H_U32(pInodeCore->TsLastModified.cNanoSec)); + RTTimeSpecSetSeconds(&pInode->ObjInfo.ChangeTime, RT_BE2H_U32(pInodeCore->TsCreatedModified.cSecEpoch)); + RTTimeSpecAddNano(&pInode->ObjInfo.ChangeTime, RT_BE2H_U32(pInodeCore->TsCreatedModified.cNanoSec)); pInode->ObjInfo.Attr.enmAdditional = RTFSOBJATTRADD_UNIX; - pInode->ObjInfo.Attr.u.Unix.uid = RT_BE2H_U32(Inode.uUid); - pInode->ObjInfo.Attr.u.Unix.gid = RT_BE2H_U32(Inode.uGid); - pInode->ObjInfo.Attr.u.Unix.cHardlinks = RT_BE2H_U16(Inode.cOnLinks); /** @todo v2 inodes. */ + pInode->ObjInfo.Attr.u.Unix.uid = RT_BE2H_U32(pInodeCore->uUid); + pInode->ObjInfo.Attr.u.Unix.gid = RT_BE2H_U32(pInodeCore->uGid); + pInode->ObjInfo.Attr.u.Unix.cHardlinks = RT_BE2H_U16(pInodeCore->cOnLinks); /** @todo v2 inodes. */ pInode->ObjInfo.Attr.u.Unix.INodeIdDevice = 0; pInode->ObjInfo.Attr.u.Unix.INodeId = iInode; pInode->ObjInfo.Attr.u.Unix.fFlags = 0; - pInode->ObjInfo.Attr.u.Unix.GenerationId = RT_BE2H_U32(Inode.cGeneration); + pInode->ObjInfo.Attr.u.Unix.GenerationId = RT_BE2H_U32(pInodeCore->cGeneration); pInode->ObjInfo.Attr.u.Unix.Device = 0; - if (Inode.iVersion >= 3) + if (pInodeCore->iVersion >= 3) { - RTTimeSpecSetSeconds(&pInode->ObjInfo.BirthTime, RT_BE2H_U32(Inode.TsCreation.cSecEpoch)); - RTTimeSpecAddNano(&pInode->ObjInfo.BirthTime, RT_BE2H_U32(Inode.TsCreation.cNanoSec)); + RTTimeSpecSetSeconds(&pInode->ObjInfo.BirthTime, RT_BE2H_U32(pInodeCore->TsCreation.cSecEpoch)); + RTTimeSpecAddNano(&pInode->ObjInfo.BirthTime, RT_BE2H_U32(pInodeCore->TsCreation.cNanoSec)); } else @@ -1002,5 +1044,5 @@ /* Fill in the mode. */ pInode->ObjInfo.Attr.fMode = 0; - uint16_t fInodeMode = RT_BE2H_U16(Inode.fMode); + uint16_t fInodeMode = RT_BE2H_U16(pInodeCore->fMode); switch (XFS_INODE_MODE_TYPE_GET_TYPE(fInodeMode)) { @@ -1136,4 +1178,83 @@ /** + * Locates the location of the next level in the B+Tree mapping the given offset. + * + * @returns Filesystem block number where the next level of the B+Tree is stored. + * @param paoffFile Array of file offset mappings. + * @param pauFsBlock Array of filesystem block mappings. + * @param cEntries Number of entries in the extent index node array. + * @param iBlock The block to resolve. + */ +DECLINLINE(XFSDFSBNO) rtFsXfsInode_BTreeNdLocateNextLvl(XFSDFILOFF *paoffFile, XFSDFSBNO *pauFsBlock, + uint16_t cEntries, XFSDFILOFF offFile) +{ + for (uint32_t i = 1; i < cEntries; i++) + { + if ( RT_BE2H_U64(paoffFile[i - 1]) <= offFile + && RT_BE2H_U64(paoffFile[i]) > offFile) + return RT_BE2H_U64(pauFsBlock[i]); + } + + /* Nothing found so far, the last entry must cover the block as the array is sorted. */ + return RT_BE2H_U64(pauFsBlock[cEntries - 1]); +} + + +/** + * Locates the extent mapping the file offset in the given extents list. + * + * @returns IPRT status. + * @param pExtents The array of extents to search. + * @param cEntries Number of entries in the array. + * @param uBlock The file offset to search the matching mapping for. + * @param cBlocks Number of blocks requested. + * @param piBlockFs Where to store the filesystem block on success. + * @param pcBlocks Where to store the number of contiguous blocks on success. + * @param pfSparse Where to store the sparse flag on success. + */ +DECLINLINE(int) rtFsXfsInode_ExtentLocate(PCXFSEXTENT paExtents, uint16_t cEntries, XFSDFILOFF uBlock, + size_t cBlocks, uint64_t *piBlockFs, size_t *pcBlocks, bool *pfSparse) +{ + int rc = VERR_VFS_BOGUS_FORMAT; + + for (uint32_t i = 0; i < cEntries; i++) + { + PCXFSEXTENT pExtent = &paExtents[i]; + uint64_t iBlockExtent = XFS_EXTENT_GET_LOGICAL_BLOCK(pExtent); + size_t cBlocksExtent = XFS_EXTENT_GET_BLOCK_COUNT(pExtent); + + if ( uBlock >= iBlockExtent + && uBlock < iBlockExtent + cBlocksExtent) + { + uint64_t offExtentBlocks = uBlock - iBlockExtent; + *piBlockFs = XFS_EXTENT_GET_DISK_BLOCK(pExtent) + offExtentBlocks; + *pcBlocks = RT_MIN(cBlocks, cBlocksExtent - offExtentBlocks); + *pfSparse = XFS_EXTENT_IS_UNWRITTEN(pExtent); + rc = VINF_SUCCESS; + break; + } + } + + return rc; +} + + +/** + * Validates the given node header. + * + * @returns IPRT status code. + * @param pThis The XFS volume instance. + * @param pNd The node header to validate. + * @param iLvl The current level. + */ +static int rtFsXfsInode_BTreeNdValidate(PRTFSXFSVOL pThis, PCXFSBTREENODEHDR pNd, uint16_t iLvl) +{ + RT_NOREF(pThis, pNd, iLvl); + /** @todo */ + return VINF_SUCCESS; +} + + +/** * Maps the given inode block to the destination filesystem block. * @@ -1152,6 +1273,88 @@ uint64_t *piBlockFs, size_t *pcBlocks, bool *pfSparse) { - RT_NOREF(pThis, pInode, iBlock, cBlocks, piBlockFs, pcBlocks, pfSparse); - return VERR_NOT_IMPLEMENTED; + int rc = VINF_SUCCESS; + + switch (pInode->enmFormat) + { + case XFS_INODE_FORMAT_EXTENTS: + { + size_t cbRemaining = 0; + PCXFSEXTENT paExtents = (PCXFSEXTENT)rtFsXfsInodeGetDataFork(pThis, pInode, &cbRemaining); + + if (cbRemaining <= pInode->cExtentsData * sizeof(XFSEXTENT)) + rc = rtFsXfsInode_ExtentLocate(paExtents, pInode->cExtentsData, cBlocks, iBlock, + piBlockFs, pcBlocks, pfSparse); + else + rc = VERR_VFS_BOGUS_FORMAT; + break; + } + case XFS_INODE_FORMAT_BTREE: + { + size_t cbRemaining = 0; + PCXFSBTREEROOTHDR pRoot = (PCXFSBTREEROOTHDR)rtFsXfsInodeGetDataFork(pThis, pInode, &cbRemaining); + if (cbRemaining >= RT_BE2H_U16(pRoot->cRecs) * (sizeof(XFSDFSBNO) + sizeof(XFSDFILOFF)) + sizeof(XFSBTREEROOTHDR)) + { + XFSDFILOFF *poffFile = (XFSDFILOFF *)(pRoot + 1); + XFSDFSBNO *puFsBlock = (XFSDFSBNO *)(&poffFile[RT_BE2H_U16(pRoot->cRecs)]); + + XFSDFSBNO uFsBlock = rtFsXfsInode_BTreeNdLocateNextLvl(poffFile, puFsBlock, RT_BE2H_U16(pRoot->cRecs), + iBlock); + uint16_t iLvl = RT_BE2H_U16(pRoot->iLvl) - 1; + + /* Resolve intermediate levels. */ + while ( iLvl > 0 + && RT_SUCCESS(rc)) + { + PRTFSXFSBLOCKENTRY pEntry; + PCXFSBTREENODEHDR pNd; + + rc = rtFsXfsVol_BlockLoad(pThis, uFsBlock, &pEntry, (void **)&pNd); + if (RT_SUCCESS(rc)) + { + rc = rtFsXfsInode_BTreeNdValidate(pThis, pNd, iLvl); + if (RT_SUCCESS(rc)) + { + poffFile = (XFSDFILOFF *)(pNd + 1); + puFsBlock = (XFSDFSBNO *)(&poffFile[RT_BE2H_U16(pNd->cRecs)]); + uFsBlock = rtFsXfsInode_BTreeNdLocateNextLvl(poffFile, puFsBlock, RT_BE2H_U16(pRoot->cRecs), + iBlock); + iLvl--; + } + rtFsXfsVol_BlockRelease(pThis, pEntry); + } + } + + /* Load the leave node and parse it. */ + if (RT_SUCCESS(rc)) + { + PRTFSXFSBLOCKENTRY pEntry; + PCXFSBTREENODEHDR pNd; + + rc = rtFsXfsVol_BlockLoad(pThis, uFsBlock, &pEntry, (void **)&pNd); + if (RT_SUCCESS(rc)) + { + rc = rtFsXfsInode_BTreeNdValidate(pThis, pNd, iLvl); + if (RT_SUCCESS(rc)) + { + PCXFSEXTENT paExtents = (PCXFSEXTENT)(pNd + 1); + rc = rtFsXfsInode_ExtentLocate(paExtents, RT_BE2H_U16(pNd->cRecs), cBlocks, iBlock, + piBlockFs, pcBlocks, pfSparse); + } + rtFsXfsVol_BlockRelease(pThis, pEntry); + } + } + } + else + rc = VERR_VFS_BOGUS_FORMAT; + break; + } + case XFS_INODE_FORMAT_LOCAL: + case XFS_INODE_FORMAT_UUID: + case XFS_INODE_FORMAT_DEV: + default: + rc = VERR_VFS_BOGUS_FORMAT; + } + + return rc; } @@ -1178,4 +1381,20 @@ else cbRead = (uint64_t)pInode->ObjInfo.cbObject - off; + } + + if (pInode->enmFormat == XFS_INODE_FORMAT_LOCAL) + { + /* Fast path when the data is inlined in the inode. */ + size_t cbRemaining = 0; + uint8_t *pbSrc = (uint8_t *)rtFsXfsInodeGetDataFork(pThis, pInode, &cbRemaining); + if (off + cbRemaining <= (uint64_t)pInode->ObjInfo.cbObject) + { + memcpy(pvBuf, &pbSrc[off], cbRead); + *pcbRead = cbRead; + } + else + rc = VERR_VFS_BOGUS_FORMAT; + + return rc; }