VirtualBox

Changeset 76316 in vbox for trunk/src/VBox/Runtime/common/fs


Ignore:
Timestamp:
Dec 20, 2018 3:33:24 PM (6 years ago)
Author:
vboxsync
Message:

Runtime/fs/extvfs: Updates, implement extent tree walking. Enables access to ext4 filesystems as long as they don't use the flex_bg feature

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/VBox/Runtime/common/fs/extvfs.cpp

    r76307 r76316  
    6262
    6363/** All supported incompatible features. */
    64 #define RTFSEXT_INCOMPAT_FEATURES_SUPP      (EXT_SB_FEAT_INCOMPAT_DIR_FILETYPE)
     64#define RTFSEXT_INCOMPAT_FEATURES_SUPP      (EXT_SB_FEAT_INCOMPAT_DIR_FILETYPE | EXT_SB_FEAT_INCOMPAT_EXTENTS | EXT_SB_FEAT_INCOMPAT_64BIT)
    6565
    6666
    … …  
    504504    }
    505505}
     506
     507
     508/**
     509 * Logs an extent header.
     510 *
     511 * @returns nothing.
     512 * @param   pExtentHdr          The extent header node.
     513 */
     514static void rtFsExtExtentHdr_Log(PCEXTEXTENTHDR pExtentHdr)
     515{
     516    if (LogIs2Enabled())
     517    {
     518        Log2(("EXT: Extent header:\n"));
     519        Log2(("EXT:   u16Magic                            %#RX16\n", RT_LE2H_U32(pExtentHdr->u16Magic)));
     520        Log2(("EXT:   cEntries                            %#RX16\n", RT_LE2H_U32(pExtentHdr->cEntries)));
     521        Log2(("EXT:   cMax                                %#RX16\n", RT_LE2H_U32(pExtentHdr->cMax)));
     522        Log2(("EXT:   uDepth                              %#RX16\n", RT_LE2H_U32(pExtentHdr->uDepth)));
     523        Log2(("EXT:   cGeneration                         %#RX32\n", RT_LE2H_U32(pExtentHdr->cGeneration)));
     524    }
     525}
     526
     527
     528/**
     529 * Logs an extent index node.
     530 *
     531 * @returns nothing.
     532 * @param   pExtentIdx          The extent index node.
     533 */
     534static void rtFsExtExtentIdx_Log(PCEXTEXTENTIDX pExtentIdx)
     535{
     536    if (LogIs2Enabled())
     537    {
     538        Log2(("EXT: Extent index node:\n"));
     539        Log2(("EXT:   iBlock                              %#RX32\n", RT_LE2H_U32(pExtentIdx->iBlock)));
     540        Log2(("EXT:   offChildLow                         %#RX32\n", RT_LE2H_U32(pExtentIdx->offChildLow)));
     541        Log2(("EXT:   offChildHigh                        %#RX16\n", RT_LE2H_U16(pExtentIdx->offChildHigh)));
     542    }
     543}
     544
     545
     546/**
     547 * Logs an extent.
     548 *
     549 * @returns nothing.
     550 * @param   pExtent             The extent.
     551 */
     552static void rtFsExtExtent_Log(PCEXTEXTENT pExtent)
     553{
     554    if (LogIs2Enabled())
     555    {
     556        Log2(("EXT: Extent:\n"));
     557        Log2(("EXT:   iBlock                              %#RX32\n", RT_LE2H_U32(pExtent->iBlock)));
     558        Log2(("EXT:   cBlocks                             %#RX16\n", RT_LE2H_U16(pExtent->cBlocks)));
     559        Log2(("EXT:   offStartHigh                        %#RX16\n", RT_LE2H_U32(pExtent->offStartHigh)));
     560        Log2(("EXT:   offStartLow                         %#RX16\n", RT_LE2H_U16(pExtent->offStartLow)));
     561    }
     562}
    506563#endif
    507564
    … …  
    10261083
    10271084/**
    1028  * Maps the given inode block to the destination filesystem block.
     1085 * Validates a given extent header.
     1086 *
     1087 * @returns Flag whether the extent header appears to be valid.
     1088 * @param   pExtentHdr          The extent header to validate.
     1089 */
     1090DECLINLINE(bool) rtFsExtInode_ExtentHdrValidate(PCEXTEXTENTHDR pExtentHdr)
     1091{
     1092    return    RT_LE2H_U16(pExtentHdr->u16Magic) == EXT_EXTENT_HDR_MAGIC
     1093           && RT_LE2H_U16(pExtentHdr->cEntries) <= RT_LE2H_U16(pExtentHdr->cMax)
     1094           && RT_LE2H_U16(pExtentHdr->uDepth) <= EXT_EXTENT_HDR_DEPTH_MAX;
     1095}
     1096
     1097
     1098/**
     1099 * Parses the given extent, checking whether it intersects with the given block.
     1100 *
     1101 * @returns Flag whether the extent maps the given range (at least partly).
     1102 * @param   pExtent             The extent to parse.
     1103 * @param   iBlock              The starting inode block to map.
     1104 * @param   cBlocks             Number of blocks requested.
     1105 * @param   piBlockFs           Where to store the filesystem block on success.
     1106 * @param   pcBlocks            Where to store the number of contiguous blocks on success.
     1107 * @param   pfSparse            Where to store the sparse flag on success.
     1108 */
     1109DECLINLINE(bool) rtFsExtInode_ExtentParse(PCEXTEXTENT pExtent, uint64_t iBlock, size_t cBlocks,
     1110                                          uint64_t *piBlockFs, size_t *pcBlocks, bool *pfSparse)
     1111{
     1112#ifdef LOG_ENABLED
     1113    rtFsExtExtent_Log(pExtent);
     1114#endif
     1115
     1116    uint32_t iExtentBlock = RT_LE2H_U32(pExtent->iBlock);
     1117    uint16_t cExtentLength = RT_LE2H_U16(pExtent->cBlocks);
     1118
     1119    /* Length over EXT_EXTENT_LENGTH_LIMIT blocks indicate a sparse extent. */
     1120    if (cExtentLength > EXT_EXTENT_LENGTH_LIMIT)
     1121    {
     1122        *pfSparse = true;
     1123        cExtentLength -= EXT_EXTENT_LENGTH_LIMIT;
     1124    }
     1125    else
     1126        *pfSparse = false;
     1127
     1128    if (   iExtentBlock <= iBlock
     1129        && iExtentBlock + cExtentLength > iBlock)
     1130    {
     1131        uint32_t iBlockRel = iBlock - iExtentBlock;
     1132        *pcBlocks = RT_MIN(cBlocks, cExtentLength - iBlockRel);
     1133        *piBlockFs = (  ((uint64_t)RT_LE2H_U16(pExtent->offStartHigh)) << 32
     1134                      | ((uint64_t)RT_LE2H_U32(pExtent->offStartLow))) + iBlockRel;
     1135        return true;
     1136    }
     1137
     1138    return false;
     1139}
     1140
     1141
     1142/**
     1143 * Locates the location of the next level in the extent tree mapping the given block.
     1144 *
     1145 * @returns Filesystem block number where the next level of the extent is stored.
     1146 * @param   paExtentIdx         Pointer to the array of extent index nodes.
     1147 * @param   cEntries            Number of entries in the extent index node array.
     1148 * @param   iBlock              The block to resolve.
     1149 */
     1150DECLINLINE(uint64_t) rtFsExtInode_ExtentIndexLocateNextLvl(PCEXTEXTENTIDX paExtentIdx, uint16_t cEntries, uint64_t iBlock)
     1151{
     1152    for (uint32_t i = 1; i < cEntries; i++)
     1153    {
     1154        PCEXTEXTENTIDX pPrev = &paExtentIdx[i - 1];
     1155        PCEXTEXTENTIDX pCur  = &paExtentIdx[i];
     1156
     1157#ifdef LOG_ENABLED
     1158        rtFsExtExtentIdx_Log(pPrev);
     1159#endif
     1160
     1161        if (   RT_LE2H_U32(pPrev->iBlock) <= iBlock
     1162            && RT_LE2H_U32(pCur->iBlock) > iBlock)
     1163            return   (uint64_t)RT_LE2H_U16(pPrev->offChildHigh) << 32
     1164                   | (uint64_t)RT_LE2H_U32(pPrev->offChildLow);
     1165    }
     1166
     1167    /* Nothing found so far, the blast extent index must cover the block as the array is sorted. */
     1168    PCEXTEXTENTIDX pLast = &paExtentIdx[cEntries - 1];
     1169#ifdef LOG_ENABLED
     1170    rtFsExtExtentIdx_Log(pLast);
     1171#endif
     1172
     1173    return   (uint64_t)RT_LE2H_U16(pLast->offChildHigh) << 32
     1174           | (uint64_t)RT_LE2H_U32(pLast->offChildLow);
     1175}
     1176
     1177
     1178/**
     1179 * Maps the given inode block to the destination filesystem block using the embedded extent tree.
     1180 *
     1181 * @returns IPRT status code.
     1182 * @param   pThis               The ext volume instance.
     1183 * @param   pInode              The inode structure to read from.
     1184 * @param   iBlock              The starting inode block to map.
     1185 * @param   cBlocks             Number of blocks requested.
     1186 * @param   piBlockFs           Where to store the filesystem block on success.
     1187 * @param   pcBlocks            Where to store the number of contiguous blocks on success.
     1188 * @param   pfSparse            Where to store the sparse flag on success.
     1189 *
     1190 * @todo Optimize
     1191 */
     1192static int rtFsExtInode_MapBlockToFsViaExtent(PRTFSEXTVOL pThis, PRTFSEXTINODE pInode, uint64_t iBlock, size_t cBlocks,
     1193                                              uint64_t *piBlockFs, size_t *pcBlocks, bool *pfSparse)
     1194{
     1195    int rc = VINF_SUCCESS;
     1196
     1197    /* The root of the extent tree is located in the block data of the inode. */
     1198    PCEXTEXTENTHDR pExtentHdr = (PCEXTEXTENTHDR)&pInode->aiBlocks[0];
     1199
     1200#ifdef LOG_ENABLED
     1201    rtFsExtExtentHdr_Log(pExtentHdr);
     1202#endif
     1203
     1204    /*
     1205     * Some validation, the top level is located inside the inode block data
     1206     * and has a maxmimum of 4 entries.
     1207     */
     1208    if (   rtFsExtInode_ExtentHdrValidate(pExtentHdr)
     1209        && RT_LE2H_U16(pExtentHdr->cMax) <= 4)
     1210    {
     1211        uint16_t uDepthCur = RT_LE2H_U16(pExtentHdr->uDepth);
     1212        if (!uDepthCur)
     1213        {
     1214            PCEXTEXTENT pExtent = (PCEXTEXTENT)(pExtentHdr + 1);
     1215
     1216            rc = VERR_VFS_BOGUS_FORMAT;
     1217            for (uint32_t i = 0; i < RT_LE2H_U16(pExtentHdr->cEntries); i++)
     1218            {
     1219                /* Check whether the extent intersects with the block. */
     1220                if (rtFsExtInode_ExtentParse(pExtent, iBlock, cBlocks, piBlockFs, pcBlocks, pfSparse))
     1221                {
     1222                    rc = VINF_SUCCESS;
     1223                    break;
     1224                }
     1225                pExtent++;
     1226            }
     1227        }
     1228        else
     1229        {
     1230            uint8_t *pbExtent = (uint8_t *)RTMemTmpAllocZ(pThis->cbBlock);
     1231            if (RT_LIKELY(pbExtent))
     1232            {
     1233                uint64_t iBlockNext = 0;
     1234                PCEXTEXTENTIDX paExtentIdx = (PCEXTEXTENTIDX)(pExtentHdr + 1);
     1235                uint16_t cEntries = RT_LE2H_U16(pExtentHdr->cEntries);
     1236
     1237                /* Descend the tree until we reached the leaf nodes. */
     1238                do
     1239                {
     1240                    iBlockNext = rtFsExtInode_ExtentIndexLocateNextLvl(paExtentIdx, cEntries, iBlock);
     1241                    /* Read in the full block. */
     1242                    uint64_t offRead = rtFsExtBlockIdxToDiskOffset(pThis, iBlockNext);
     1243                    rc = RTVfsFileReadAt(pThis->hVfsBacking, offRead, pbExtent, pThis->cbBlock, NULL);
     1244                    if (RT_SUCCESS(rc))
     1245                    {
     1246                        pExtentHdr = (PCEXTEXTENTHDR)pbExtent;
     1247
     1248#ifdef LOG_ENABLED
     1249                        rtFsExtExtentHdr_Log(pExtentHdr);
     1250#endif
     1251
     1252                        if (   rtFsExtInode_ExtentHdrValidate(pExtentHdr)
     1253                            && RT_LE2H_U16(pExtentHdr->cMax) <= (pThis->cbBlock - sizeof(EXTEXTENTHDR)) / sizeof(EXTEXTENTIDX)
     1254                            && RT_LE2H_U16(pExtentHdr->uDepth) == uDepthCur - 1)
     1255                        {
     1256                            uDepthCur--;
     1257                            cEntries = RT_LE2H_U16(pExtentHdr->cEntries);
     1258                            paExtentIdx = (PCEXTEXTENTIDX)(pExtentHdr + 1);
     1259                        }
     1260                        else
     1261                            rc = VERR_VFS_BOGUS_FORMAT;
     1262                    }
     1263                }
     1264                while (   uDepthCur > 0
     1265                       && RT_SUCCESS(rc));
     1266
     1267                if (RT_SUCCESS(rc))
     1268                {
     1269                    Assert(!uDepthCur);
     1270
     1271                    /* We reached the leaf nodes. */
     1272                    PCEXTEXTENT pExtent = (PCEXTEXTENT)(pExtentHdr + 1);
     1273                    for (uint32_t i = 0; i < RT_LE2H_U16(pExtentHdr->cEntries); i++)
     1274                    {
     1275                        /* Check whether the extent intersects with the block. */
     1276                        if (rtFsExtInode_ExtentParse(pExtent, iBlock, cBlocks, piBlockFs, pcBlocks, pfSparse))
     1277                        {
     1278                            rc = VINF_SUCCESS;
     1279                            break;
     1280                        }
     1281                        pExtent++;
     1282                    }
     1283                }
     1284
     1285                RTMemTmpFree(pbExtent);
     1286            }
     1287            else
     1288                rc = VERR_NO_MEMORY;
     1289        }
     1290    }
     1291    else
     1292        rc = VERR_VFS_BOGUS_FORMAT;
     1293
     1294    return rc;
     1295}
     1296
     1297
     1298/**
     1299 * Maps the given inode block to the destination filesystem block using the original block mapping scheme.
    10291300 *
    10301301 * @returns IPRT status code.
    … …  
    10321303 * @param   pInode              The inode structure to read from.
    10331304 * @param   iBlock              The inode block to map.
     1305 * @param   cBlocks             Number of blocks requested.
    10341306 * @param   piBlockFs           Where to store the filesystem block on success.
    1035  *
    1036  * @todo Optimize
    1037  */
    1038 static int rtFsExtInode_MapBlockToFs(PRTFSEXTVOL pThis, PRTFSEXTINODE pInode, uint64_t iBlock, uint64_t *piBlockFs)
     1307 * @param   pcBlocks            Where to store the number of contiguous blocks on success.
     1308 * @param   pfSparse            Where to store the sparse flag on success.
     1309 *
     1310 * @todo Optimize and handle sparse files.
     1311 */
     1312static int rtFsExtInode_MapBlockToFsViaBlockMap(PRTFSEXTVOL pThis, PRTFSEXTINODE pInode, uint64_t iBlock, size_t cBlocks,
     1313                                                uint64_t *piBlockFs, size_t *pcBlocks, bool *pfSparse)
    10391314{
    10401315    int rc = VINF_SUCCESS;
     1316    RT_NOREF(cBlocks);
     1317
     1318    *pfSparse = false;
     1319    *pcBlocks = 1;
    10411320
    10421321    /* The first 12 inode blocks are directly mapped from the inode. */
    … …  
    10891368
    10901369/**
     1370 * Maps the given inode block to the destination filesystem block.
     1371 *
     1372 * @returns IPRT status code.
     1373 * @param   pThis               The ext volume instance.
     1374 * @param   pInode              The inode structure to read from.
     1375 * @param   iBlock              The inode block to map.
     1376 * @param   cBlocks             Number of blocks requested.
     1377 * @param   piBlockFs           Where to store the filesystem block on success.
     1378 * @param   pcBlocks            Where to store the number of contiguous blocks on success.
     1379 * @param   pfSparse            Where to store the sparse flag on success.
     1380 *
     1381 * @todo Optimize
     1382 */
     1383static int rtFsExtInode_MapBlockToFs(PRTFSEXTVOL pThis, PRTFSEXTINODE pInode, uint64_t iBlock, size_t cBlocks,
     1384                                     uint64_t *piBlockFs, size_t *pcBlocks, bool *pfSparse)
     1385{
     1386    if (pInode->fFlags & EXT_INODE_F_EXTENTS)
     1387        return rtFsExtInode_MapBlockToFsViaExtent(pThis, pInode, iBlock, cBlocks, piBlockFs, pcBlocks, pfSparse);
     1388    else
     1389        return rtFsExtInode_MapBlockToFsViaBlockMap(pThis, pInode, iBlock, cBlocks, piBlockFs, pcBlocks, pfSparse);
     1390}
     1391
     1392
     1393/**
    10911394 * Reads data from the given inode at the given byte offset.
    10921395 *
    … …  
    11191422        /* Resolve the inode block to the proper filesystem block. */
    11201423        uint64_t iBlockFs = 0;
    1121         rc = rtFsExtInode_MapBlockToFs(pThis, pInode, iBlockStart, &iBlockFs);
     1424        size_t cBlocks = 0;
     1425        bool fSparse = false;
     1426        rc = rtFsExtInode_MapBlockToFs(pThis, pInode, iBlockStart, 1, &iBlockFs, &cBlocks, &fSparse);
    11221427        if (RT_SUCCESS(rc))
    11231428        {
     1429            Assert(cBlocks == 1);
     1430
    11241431            size_t cbThisRead = RT_MIN(cbRead, pThis->cbBlock - offBlockStart);
    1125             uint64_t offRead = rtFsExtBlockIdxToDiskOffset(pThis, iBlockFs);
    1126             rc = RTVfsFileReadAt(pThis->hVfsBacking, offRead + offBlockStart, pbBuf, cbThisRead, NULL);
     1432
     1433            if (!fSparse)
     1434            {
     1435                uint64_t offRead = rtFsExtBlockIdxToDiskOffset(pThis, iBlockFs);
     1436                rc = RTVfsFileReadAt(pThis->hVfsBacking, offRead + offBlockStart, pbBuf, cbThisRead, NULL);
     1437            }
     1438            else
     1439                memset(pbBuf, 0, cbThisRead);
     1440
    11271441            if (RT_SUCCESS(rc))
    11281442            {
    … …  
    20862400                                   RT_LE2H_U32(pSb->fFeaturesCompatRo));
    20872401
    2088     pThis->f64Bit          = false;
     2402    pThis->fFeaturesIncompat = RT_LE2H_U32(pSb->fFeaturesIncompat);
     2403    pThis->f64Bit            = RT_BOOL(pThis->fFeaturesIncompat & EXT_SB_FEAT_INCOMPAT_64BIT);
    20892404    pThis->cBlockShift     = 10 + RT_LE2H_U32(pSb->cLogBlockSize);
    20902405    pThis->cbBlock         = UINT64_C(1) << pThis->cBlockShift;
    20912406    pThis->cbInode         = RT_LE2H_U16(pSb->cbInode);
    2092     pThis->cbBlkGrpDesc    = sizeof(EXTBLOCKGROUPDESC32);
     2407    pThis->cbBlkGrpDesc    = pThis->f64Bit ? RT_LE2H_U16(pSb->cbGroupDesc) : sizeof(EXTBLOCKGROUPDESC32);
    20932408    pThis->cBlocksPerGroup = RT_LE2H_U32(pSb->cBlocksPerGroup);
    20942409    pThis->cInodesPerGroup = RT_LE2H_U32(pSb->cInodesPerBlockGroup);
    … …  
    21002415    if (pThis->cInodesPerGroup % 8)
    21012416        pThis->cbInodeBitmap++;
    2102     pThis->fFeaturesIncompat = RT_LE2H_U32(pSb->fFeaturesIncompat);
    21032417
    21042418    return VINF_SUCCESS;
Note: See TracChangeset for help on using the changeset viewer.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette