VirtualBox

Changeset 93695 in vbox for trunk/include/iprt/cpp


Ignore:
Timestamp:
Feb 11, 2022 12:07:23 PM (3 years ago)
Author:
vboxsync
Message:

IPRT/hardavl: Wrap node index reads to try prevent the compiler from re-reading them after validation. bugref:10093

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/include/iprt/cpp/hardavlrange.h

    r93693 r93695  
    4747#ifdef RT_STRICT
    4848# define RTHARDAVL_STRICT_CHECK_HEIGHTS(a_pNode, a_pAvlStack, a_cStackEntries) do { \
    49         NodeType * const pLeftNodeX    = a_pAllocator->ptrFromInt((a_pNode)->idxLeft); \
     49        NodeType * const pLeftNodeX    = a_pAllocator->ptrFromInt(readIdx(&(a_pNode)->idxLeft)); \
    5050        AssertReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNodeX), m_cErrors++, a_pAllocator->ptrErrToStatus((a_pNode))); \
    51         NodeType * const pRightNodeX   = a_pAllocator->ptrFromInt((a_pNode)->idxRight); \
     51        NodeType * const pRightNodeX   = a_pAllocator->ptrFromInt(readIdx(&(a_pNode)->idxRight)); \
    5252        AssertReturnStmt(a_pAllocator->isPtrRetOkay(pRightNodeX), m_cErrors++, a_pAllocator->ptrErrToStatus((a_pNode))); \
    5353        uint8_t const    cLeftHeightX  = pLeftNodeX  ? pLeftNodeX->cHeight  : 0; \
    … …  
    125125    /** @} */
    126126
     127    /**
     128     * Read an index value trying to prevent the compiler from re-reading it.
     129     */
     130    DECL_FORCE_INLINE(uint32_t) readIdx(uint32_t volatile *pidx)
     131    {
     132        uint32_t idx = *pidx;
     133        ASMCompilerBarrier();
     134        return idx;
     135    }
     136
     137
    127138    RTCHardAvlRangeTree()
    128139        : m_idxRoot(0)
    … …  
    170181        for (;;)
    171182        {
    172             NodeType *pCurNode = a_pAllocator->ptrFromInt(*pidxCurNode);
     183            NodeType *pCurNode = a_pAllocator->ptrFromInt(readIdx(pidxCurNode));
    173184            AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pCurNode), ("*pidxCurNode=%#x pCurNode=%p\n", *pidxCurNode, pCurNode),
    174185                                m_cErrors++, a_pAllocator->ptrErrToStatus(pCurNode));
    … …  
    271282        for (;;)
    272283        {
    273             pDeleteNode = a_pAllocator->ptrFromInt(*pidxDeleteNode);
     284            pDeleteNode = a_pAllocator->ptrFromInt(readIdx(pidxDeleteNode));
    274285            AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pDeleteNode),
    275286                                ("*pidxCurNode=%#x pDeleteNode=%p\n", *pidxDeleteNode, pDeleteNode),
    … …  
    309320         * Do the deletion.
    310321         */
    311         uint32_t const idxDeleteLeftNode = pDeleteNode->idxLeft;
     322        uint32_t const idxDeleteLeftNode = readIdx(&pDeleteNode->idxLeft);
    312323        if (idxDeleteLeftNode != a_pAllocator->kNilIndex)
    313324        {
    … …  
    320331                                m_cErrors++, a_pAllocator->ptrErrToStatus(pDeleteLeftNode));
    321332
    322             uint32_t const   idxDeleteRightNode = pDeleteNode->idxRight;
     333            uint32_t const   idxDeleteRightNode = readIdx(&pDeleteNode->idxRight);
    323334            AssertReturnStmt(a_pAllocator->isIntValid(idxDeleteRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
    324335
    … …  
    330341            RTHARDAVL_STRICT_CHECK_HEIGHTS(pLeftBiggestNode, &AVLStack, AVLStack.cEntries);
    331342
    332             while (pLeftBiggestNode->idxRight != a_pAllocator->kNilIndex)
     343            uint32_t idxRightTmp;
     344            while ((idxRightTmp = readIdx(&pLeftBiggestNode->idxRight)) != a_pAllocator->kNilIndex)
    333345            {
    334346                unsigned const cEntries = AVLStack.cEntries;
    … …  
    346358
    347359                pidxLeftBiggest    = &pLeftBiggestNode->idxRight;
    348                 idxLeftBiggestNode = pLeftBiggestNode->idxRight;
    349                 pLeftBiggestNode   = a_pAllocator->ptrFromInt(idxLeftBiggestNode);
     360                idxLeftBiggestNode = idxRightTmp;
     361                pLeftBiggestNode   = a_pAllocator->ptrFromInt(idxRightTmp);
    350362                AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftBiggestNode),
    351363                                    ("idxLeftBiggestNode=%#x pLeftBiggestNode=%p\n", idxLeftBiggestNode, pLeftBiggestNode),
    … …  
    354366            }
    355367
    356             uint32_t const idxLeftBiggestLeftNode = pLeftBiggestNode->idxLeft;
     368            uint32_t const idxLeftBiggestLeftNode = readIdx(&pLeftBiggestNode->idxLeft);
    357369            AssertReturnStmt(a_pAllocator->isIntValid(idxLeftBiggestLeftNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
    358370
    … …  
    374386        {
    375387            /* No left node, just pull up the right one. */
    376             uint32_t const idxDeleteRightNode = pDeleteNode->idxRight;
     388            uint32_t const idxDeleteRightNode = readIdx(&pDeleteNode->idxRight);
    377389            AssertReturnStmt(a_pAllocator->isIntValid(idxDeleteRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
    378390            *pidxDeleteNode = idxDeleteRightNode;
    … …  
    398410        *a_ppFound = NULL;
    399411
    400         NodeType *pNode = a_pAllocator->ptrFromInt(m_idxRoot);
     412        NodeType *pNode = a_pAllocator->ptrFromInt(readIdx(&m_idxRoot));
    401413        AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode),
    402414                            m_cErrors++, a_pAllocator->ptrErrToStatus(pNode));
    … …  
    423435                AVLStack.apidxEntries[AVLStack.cEntries++] = &pNode->idxLeft;
    424436#endif
    425                 uint32_t const idxLeft = pNode->idxLeft;
     437                uint32_t const idxLeft = readIdx(&pNode->idxLeft);
    426438                pNode = a_pAllocator->ptrFromInt(idxLeft);
    427439                AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("idxLeft=%#x pNode=%p\n", idxLeft, pNode),
    … …  
    433445                AVLStack.apidxEntries[AVLStack.cEntries++] = &pNode->idxRight;
    434446#endif
    435                 uint32_t const idxRight = pNode->idxRight;
     447                uint32_t const idxRight = readIdx(&pNode->idxRight);
    436448                pNode = a_pAllocator->ptrFromInt(idxRight);
    437449                AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("idxRight=%#x pNode=%p\n", idxRight, pNode),
    … …  
    466478    int doWithAllFromLeft(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator, PFNCALLBACK a_pfnCallBack, void *a_pvUser)
    467479    {
    468         NodeType *pNode = a_pAllocator->ptrFromInt(m_idxRoot);
     480        NodeType *pNode = a_pAllocator->ptrFromInt(readIdx(&m_idxRoot));
    469481        AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode),
    470482                            m_cErrors++, a_pAllocator->ptrErrToStatus(pNode));
    … …  
    492504                    abState[cEntries - 1] = 1;
    493505
    494                     NodeType * const pLeftNode = a_pAllocator->ptrFromInt(pNode->idxLeft);
     506                    NodeType * const pLeftNode = a_pAllocator->ptrFromInt(readIdx(&pNode->idxLeft));
    495507                    AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNode),
    496508                                        ("idxLeft=%#x pLeftNode=%p\n", pNode->idxLeft, pLeftNode),
    … …  
    528540                        return rc;
    529541
    530                     NodeType * const pRightNode = a_pAllocator->ptrFromInt(pNode->idxRight);
     542                    NodeType * const pRightNode = a_pAllocator->ptrFromInt(readIdx(&pNode->idxRight));
    531543                    AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightNode),
    532544                                        ("idxRight=%#x pRightNode=%p\n", pNode->idxRight, pRightNode),
    … …  
    589601    int destroy(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator, PFNDESTROYCALLBACK a_pfnCallBack = NULL, void *a_pvUser = NULL)
    590602    {
    591         NodeType *pNode = a_pAllocator->ptrFromInt(m_idxRoot);
     603        NodeType *pNode = a_pAllocator->ptrFromInt(readIdx(&m_idxRoot));
    592604        AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode),
    593605                            m_cErrors++, a_pAllocator->ptrErrToStatus(pNode));
    … …  
    615627                    abState[cEntries - 1] = 1;
    616628
    617                     NodeType * const pLeftNode = a_pAllocator->ptrFromInt(pNode->idxLeft);
     629                    NodeType * const pLeftNode = a_pAllocator->ptrFromInt(readIdx(&pNode->idxLeft));
    618630                    AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNode),
    619631                                        ("idxLeft=%#x pLeftNode=%p\n", pNode->idxLeft, pLeftNode),
    … …  
    645657                    abState[cEntries - 1] = 2;
    646658
    647                     NodeType * const pRightNode = a_pAllocator->ptrFromInt(pNode->idxRight);
     659                    NodeType * const pRightNode = a_pAllocator->ptrFromInt(readIdx(&pNode->idxRight));
    648660                    AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightNode),
    649661                                        ("idxRight=%#x pRightNode=%p\n", pNode->idxRight, pRightNode),
    … …  
    697709    uint8_t getHeight(RTCHardAvlTreeSlabAllocator<NodeType> *a_pAllocator)
    698710    {
    699         NodeType *pNode = a_pAllocator->ptrFromInt(m_idxRoot);
     711        NodeType *pNode = a_pAllocator->ptrFromInt(readIdx(&m_idxRoot));
    700712        AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode), ("m_idxRoot=%#x pNode=%p\n", m_idxRoot, pNode),
    701713                            m_cErrors++, UINT8_MAX);
    … …  
    730742        {
    731743            NodeType *pNode = a_pAllocator->ptrFromInt(a_idxRoot);
    732             printTree(a_pAllocator, pNode->idxRight, a_uLevel + 1, a_uMaxLevel, "/ ");
     744            printTree(a_pAllocator, readIdx(&pNode->idxRight), a_uLevel + 1, a_uMaxLevel, "/ ");
    733745            RTAssertMsg2("%*s%#x/%u\n", a_uLevel * 6, a_pszDir, a_idxRoot, pNode->cHeight);
    734             printTree(a_pAllocator, pNode->idxLeft, a_uLevel + 1, a_uMaxLevel, "\\ ");
     746            printTree(a_pAllocator, readIdx(&pNode->idxLeft), a_uLevel + 1, a_uMaxLevel, "\\ ");
    735747        }
    736748        else
    … …  
    807819            /* pop */
    808820            uint32_t * const pidxNode  = a_pStack->apidxEntries[--a_pStack->cEntries];
    809             uint32_t const   idxNode   = *pidxNode;
     821            uint32_t const   idxNode   = readIdx(pidxNode);
    810822            NodeType * const pNode     = a_pAllocator->ptrFromInt(idxNode);
    811823            AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pNode),
    … …  
    814826
    815827            /* Read node properties: */
    816             uint32_t const   idxLeftNode = pNode->idxLeft;
     828            uint32_t const   idxLeftNode = readIdx(&pNode->idxLeft);
    817829            NodeType * const pLeftNode   = a_pAllocator->ptrFromInt(idxLeftNode);
    818830            AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftNode),
    … …  
    820832                                m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftNode));
    821833
    822             uint32_t const   idxRightNode = pNode->idxRight;
     834            uint32_t const   idxRightNode = readIdx(&pNode->idxRight);
    823835            NodeType * const pRightNode   = a_pAllocator->ptrFromInt(idxRightNode);
    824836            AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightNode),
    … …  
    838850                AssertReturnStmt(pLeftNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_LEFT);
    839851
    840                 uint32_t const   idxLeftLeftNode = pLeftNode->idxLeft;
     852                uint32_t const   idxLeftLeftNode = readIdx(&pLeftNode->idxLeft);
    841853                NodeType * const pLeftLeftNode   = a_pAllocator->ptrFromInt(idxLeftLeftNode);
    842854                AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftLeftNode),
    … …  
    844856                                    m_cErrors++, a_pAllocator->ptrErrToStatus(pLeftLeftNode));
    845857
    846                 uint32_t const   idxLeftRightNode = pLeftNode->idxRight;
     858                uint32_t const   idxLeftRightNode = readIdx(&pLeftNode->idxRight);
    847859                NodeType * const pLeftRightNode   = a_pAllocator->ptrFromInt(idxLeftRightNode);
    848860                AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pLeftRightNode),
    … …  
    868880                    AssertReturnStmt(pLeftRightNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_RIGHT);
    869881
    870                     uint32_t const idxLeftRightLeftNode  = pLeftRightNode->idxLeft;
     882                    uint32_t const idxLeftRightLeftNode  = readIdx(&pLeftRightNode->idxLeft);
    871883                    AssertReturnStmt(a_pAllocator->isIntValid(idxLeftRightLeftNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
    872                     uint32_t const idxLeftRightRightNode = pLeftRightNode->idxRight;
     884                    uint32_t const idxLeftRightRightNode = readIdx(&pLeftRightNode->idxRight);
    873885                    AssertReturnStmt(a_pAllocator->isIntValid(idxLeftRightRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
    874886                    pLeftNode->idxRight = idxLeftRightLeftNode;
    … …  
    891903                AssertReturnStmt(pRightNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_RIGHT);
    892904
    893                 uint32_t const   idxRightLeftNode = pRightNode->idxLeft;
     905                uint32_t const   idxRightLeftNode = readIdx(&pRightNode->idxLeft);
    894906                NodeType * const pRightLeftNode   = a_pAllocator->ptrFromInt(idxRightLeftNode);
    895907                AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightLeftNode),
    … …  
    897909                                    m_cErrors++, a_pAllocator->ptrErrToStatus(pRightLeftNode));
    898910
    899                 uint32_t const   idxRightRightNode = pRightNode->idxRight;
     911                uint32_t const   idxRightRightNode = readIdx(&pRightNode->idxRight);
    900912                NodeType * const pRightRightNode   = a_pAllocator->ptrFromInt(idxRightRightNode);
    901913                AssertMsgReturnStmt(a_pAllocator->isPtrRetOkay(pRightRightNode),
    … …  
    924936                    AssertReturnStmt(pRightLeftNode, m_cErrors++, VERR_HARDAVL_UNEXPECTED_NULL_LEFT);
    925937
    926                     uint32_t const idxRightLeftRightNode = pRightLeftNode->idxRight;
     938                    uint32_t const idxRightLeftRightNode = readIdx(&pRightLeftNode->idxRight);
    927939                    AssertReturnStmt(a_pAllocator->isIntValid(idxRightLeftRightNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
    928                     uint32_t const idxRightLeftLeftNode  = pRightLeftNode->idxLeft;
     940                    uint32_t const idxRightLeftLeftNode  = readIdx(&pRightLeftNode->idxLeft);
    929941                    AssertReturnStmt(a_pAllocator->isIntValid(idxRightLeftLeftNode), m_cErrors++, VERR_HARDAVL_INDEX_OUT_OF_BOUNDS);
    930942                    pRightNode->idxLeft      = idxRightLeftRightNode;
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