VirtualBox

Changeset 86726 in vbox for trunk/src/VBox/VMM/VMMR3


Ignore:
Timestamp:
Oct 28, 2020 10:10:29 AM (4 years ago)
Author:
vboxsync
svn:sync-xref-src-repo-rev:
141114
Message:

VMM/DBGF: Implement L2 binary search tree node insertion and walking the tree in R0, bugref:9837

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/VBox/VMM/VMMR3/DBGFR3Bp.cpp

    r86704 r86726  
    157157#include <iprt/mem.h>
    158158
     159#include "DBGFInline.h"
     160
    159161
    160162/*********************************************************************************************************************************
    … …  
    855857
    856858/**
     859 * Returns the pointer to the L2 table entry from the given index.
     860 *
     861 * @returns Current context pointer to the L2 table entry or NULL if the provided index value is invalid.
     862 * @param   pUVM        The user mode VM handle.
     863 * @param   idxL2       The L2 table index to resolve.
     864 *
     865 * @note The content of the resolved L2 table entry is not validated!.
     866 */
     867DECLINLINE(PDBGFBPL2ENTRY) dbgfR3BpL2GetByIdx(PUVM pUVM, uint32_t idxL2)
     868{
     869    uint32_t idChunk  = DBGF_BP_L2_IDX_GET_CHUNK_ID(idxL2);
     870    uint32_t idxEntry = DBGF_BP_L2_IDX_GET_ENTRY(idxL2);
     871
     872    AssertReturn(idChunk < DBGF_BP_L2_TBL_CHUNK_COUNT, NULL);
     873    AssertReturn(idxEntry < DBGF_BP_L2_TBL_ENTRIES_PER_CHUNK, NULL);
     874
     875    PDBGFBPL2TBLCHUNKR3 pL2Chunk = &pUVM->dbgf.s.aBpL2TblChunks[idChunk];
     876    AssertPtrReturn(pL2Chunk->pbmAlloc, NULL);
     877    AssertReturn(ASMBitTest(pL2Chunk->pbmAlloc, idxEntry), NULL);
     878
     879    return &pL2Chunk->CTX_SUFF(pL2Base)[idxEntry];
     880}
     881
     882
     883/**
     884 * Creates a binary search tree with the given root and leaf nodes.
     885 *
     886 * @returns VBox status code.
     887 * @param   pUVM                The user mode VM handle.
     888 * @param   idxL1               The index into the L1 table where the created tree should be linked into.
     889 * @param   u32EntryOld         The old entry in the L1 table used to compare with in the atomic update.
     890 * @param   hBpRoot             The root node DBGF handle to assign.
     891 * @param   GCPtrRoot           The root nodes GC pointer to use as a key.
     892 * @param   hBpLeaf             The leafs node DBGF handle to assign.
     893 * @param   GCPtrLeaf           The leafs node GC pointer to use as a key.
     894 */
     895static int dbgfR3BpInt3L2BstCreate(PUVM pUVM, uint32_t idxL1, uint32_t u32EntryOld,
     896                                   DBGFBP hBpRoot, RTGCUINTPTR GCPtrRoot,
     897                                   DBGFBP hBpLeaf, RTGCUINTPTR GCPtrLeaf)
     898{
     899    AssertReturn(GCPtrRoot != GCPtrLeaf, VERR_DBGF_BP_IPE_9);
     900    Assert(DBGF_BP_INT3_L1_IDX_EXTRACT_FROM_ADDR(GCPtrRoot) == DBGF_BP_INT3_L1_IDX_EXTRACT_FROM_ADDR(GCPtrLeaf));
     901
     902    /* Allocate two nodes. */
     903    uint32_t idxL2Root = 0;
     904    PDBGFBPL2ENTRY pL2Root = NULL;
     905    int rc = dbgfR3BpL2TblEntryAlloc(pUVM, &idxL2Root, &pL2Root);
     906    if (RT_SUCCESS(rc))
     907    {
     908        uint32_t idxL2Leaf = 0;
     909        PDBGFBPL2ENTRY pL2Leaf = NULL;
     910        rc = dbgfR3BpL2TblEntryAlloc(pUVM, &idxL2Leaf, &pL2Leaf);
     911        if (RT_SUCCESS(rc))
     912        {
     913            dbgfBpL2TblEntryInit(pL2Leaf, hBpLeaf, GCPtrLeaf, DBGF_BP_L2_ENTRY_IDX_END, DBGF_BP_L2_ENTRY_IDX_END, 0 /*iDepth*/);
     914            if (GCPtrLeaf < GCPtrRoot)
     915                dbgfBpL2TblEntryInit(pL2Root, hBpRoot, GCPtrRoot, idxL2Leaf, DBGF_BP_L2_ENTRY_IDX_END, 0 /*iDepth*/);
     916            else
     917                dbgfBpL2TblEntryInit(pL2Root, hBpRoot, GCPtrRoot, DBGF_BP_L2_ENTRY_IDX_END, idxL2Leaf, 0 /*iDepth*/);
     918
     919            uint32_t const u32Entry = DBGF_BP_INT3_L1_ENTRY_CREATE_L2_IDX(idxL2Root);
     920            if (ASMAtomicCmpXchgU32(&pUVM->dbgf.s.paBpLocL1R3[idxL1], u32Entry, u32EntryOld))
     921                return VINF_SUCCESS;
     922
     923            /* The L1 entry has changed due to another thread racing us during insertion, free nodes and try again. */
     924            rc = VINF_TRY_AGAIN;
     925            dbgfR3BpL2TblEntryFree(pUVM, idxL2Leaf, pL2Leaf);
     926        }
     927
     928        dbgfR3BpL2TblEntryFree(pUVM, idxL2Root, pL2Root);
     929    }
     930
     931    return rc;
     932}
     933
     934
     935/**
     936 * Inserts the given breakpoint handle into an existing binary search tree.
     937 *
     938 * @returns VBox status code.
     939 * @param   pUVM                The user mode VM handle.
     940 * @param   idxL2Root           The index of the tree root in the L2 table.
     941 * @param   hBpRoot             The node DBGF handle to insert.
     942 * @param   GCPtrRoot           The nodes GC pointer to use as a key.
     943 */
     944static int dbgfR3BpInt2L2BstNodeInsert(PUVM pUVM, uint32_t idxL2Root, DBGFBP hBp, RTGCUINTPTR GCPtr)
     945{
     946    /* Allocate a new node first. */
     947    uint32_t idxL2Nd = 0;
     948    PDBGFBPL2ENTRY pL2Nd = NULL;
     949    int rc = dbgfR3BpL2TblEntryAlloc(pUVM, &idxL2Nd, &pL2Nd);
     950    if (RT_SUCCESS(rc))
     951    {
     952        /* Walk the tree and find the correct node to insert to. */
     953        PDBGFBPL2ENTRY pL2Entry = dbgfR3BpL2GetByIdx(pUVM, idxL2Root);
     954        while (RT_LIKELY(pL2Entry))
     955        {
     956            /* Make a copy of the entry. */
     957            DBGFBPL2ENTRY L2Entry;
     958            L2Entry.u64GCPtrKeyAndBpHnd1       = ASMAtomicReadU64((volatile uint64_t *)&pL2Entry->u64GCPtrKeyAndBpHnd1);
     959            L2Entry.u64LeftRightIdxDepthBpHnd2 = ASMAtomicReadU64((volatile uint64_t *)&pL2Entry->u64LeftRightIdxDepthBpHnd2);
     960
     961            RTGCUINTPTR GCPtrL2Entry = DBGF_BP_L2_ENTRY_GET_GCPTR(L2Entry.u64GCPtrKeyAndBpHnd1);
     962            AssertBreak(GCPtr != GCPtrL2Entry);
     963
     964            /* Not found, get to the next level. */
     965            uint32_t idxL2Next =   (GCPtr < GCPtrL2Entry)
     966                                 ? DBGF_BP_L2_ENTRY_GET_IDX_LEFT(L2Entry.u64LeftRightIdxDepthBpHnd2)
     967                                 : DBGF_BP_L2_ENTRY_GET_IDX_RIGHT(L2Entry.u64LeftRightIdxDepthBpHnd2);
     968            if (idxL2Next == DBGF_BP_L2_ENTRY_IDX_END)
     969            {
     970                /* Insert the new node here. */
     971                dbgfBpL2TblEntryInit(pL2Nd, hBp, GCPtr, DBGF_BP_L2_ENTRY_IDX_END, DBGF_BP_L2_ENTRY_IDX_END, 0 /*iDepth*/);
     972                if (GCPtr < GCPtrL2Entry)
     973                    dbgfBpL2TblEntryUpdateLeft(pL2Entry, idxL2Next, 0 /*iDepth*/);
     974                else
     975                    dbgfBpL2TblEntryUpdateRight(pL2Entry, idxL2Next, 0 /*iDepth*/);
     976                return VINF_SUCCESS;
     977            }
     978
     979            pL2Entry = dbgfR3BpL2GetByIdx(pUVM, idxL2Next);
     980        }
     981
     982        rc = VERR_DBGF_BP_L2_LOOKUP_FAILED;
     983        dbgfR3BpL2TblEntryFree(pUVM, idxL2Nd, pL2Nd);
     984    }
     985
     986    return rc;
     987}
     988
     989
     990/**
     991 * Adds the given breakpoint handle keyed with the GC pointer to the proper L2 binary search tree
     992 * possibly creating a new tree.
     993 *
     994 * @returns VBox status code.
     995 * @param   pUVM                The user mode VM handle.
     996 * @param   idxL1               The index into the L1 table the breakpoint uses.
     997 * @param   hBp                 The breakpoint handle which is to be added.
     998 * @param   GCPtr               The GC pointer the breakpoint is keyed with.
     999 */
     1000static int dbgfR3BpInt3L2BstNodeAdd(PUVM pUVM, uint32_t idxL1, DBGFBP hBp, RTGCUINTPTR GCPtr)
     1001{
     1002    int rc = RTSemFastMutexRequest(pUVM->dbgf.s.hMtxBpL2Wr); AssertRC(rc);
     1003
     1004    uint32_t u32Entry = ASMAtomicReadU32(&pUVM->dbgf.s.paBpLocL1R3[idxL1]); /* Re-read, could get raced by a remove operation. */
     1005    uint8_t u8Type = DBGF_BP_INT3_L1_ENTRY_GET_TYPE(u32Entry);
     1006    if (u8Type == DBGF_BP_INT3_L1_ENTRY_TYPE_BP_HND)
     1007    {
     1008        /* Create a new search tree, gather the necessary information first. */
     1009        DBGFBP hBp2 = DBGF_BP_INT3_L1_ENTRY_GET_BP_HND(u32Entry);
     1010        PDBGFBPINT pBp2 = dbgfR3BpGetByHnd(pUVM, hBp2);
     1011        AssertStmt(VALID_PTR(pBp2), rc = VERR_DBGF_BP_IPE_7);
     1012        if (RT_SUCCESS(rc))
     1013            rc = dbgfR3BpInt3L2BstCreate(pUVM, idxL1, u32Entry, hBp, GCPtr, hBp2, pBp2->Pub.u.Int3.GCPtr);
     1014    }
     1015    else if (u8Type == DBGF_BP_INT3_L1_ENTRY_TYPE_L2_IDX)
     1016        rc = dbgfR3BpInt2L2BstNodeInsert(pUVM, DBGF_BP_INT3_L1_ENTRY_GET_L2_IDX(u32Entry), hBp, GCPtr);
     1017
     1018    int rc2 = RTSemFastMutexRelease(pUVM->dbgf.s.hMtxBpL2Wr); AssertRC(rc2);
     1019    return rc;
     1020}
     1021
     1022
     1023/**
     1024 * Removes the given breakpoint handle keyed with the GC pointer from the L2 binary search tree
     1025 * pointed to by the given L2 root index.
     1026 *
     1027 * @returns VBox status code.
     1028 * @param   pUVM                The user mode VM handle.
     1029 * @param   idxL1               The index into the L1 table pointing to the binary search tree.
     1030 * @param   idxL2Root           The L2 table index where the tree root is located.
     1031 * @param   hBp                 The breakpoint handle which is to be removed.
     1032 * @param   GCPtr               The GC pointer the breakpoint is keyed with.
     1033 */
     1034static int dbgfR3BpInt2L2BstNodeRemove(PUVM pUVM, uint32_t idxL1, uint32_t idxL2Root, DBGFBP hBp, RTGCUINTPTR GCPtr)
     1035{
     1036    int rc = RTSemFastMutexRequest(pUVM->dbgf.s.hMtxBpL2Wr); AssertRC(rc);
     1037
     1038    RT_NOREF(idxL1, idxL2Root, hBp, GCPtr);
     1039
     1040    int rc2 = RTSemFastMutexRelease(pUVM->dbgf.s.hMtxBpL2Wr); AssertRC(rc2);
     1041
     1042    return rc;
     1043}
     1044
     1045
     1046/**
    8571047 * Adds the given int3 breakpoint to the appropriate lookup tables.
    8581048 *
    … …  
    8861076        else
    8871077        {
    888             uint8_t u8Type = DBGF_BP_INT3_L1_ENTRY_GET_TYPE(u32Entry);
    889             if (u8Type == DBGF_BP_INT3_L1_ENTRY_TYPE_BP_HND)
    890             {
    891                 /** @todo Allocate a new root entry and one leaf to accomodate for the two handles,
    892                  * then replace the new entry. */
    893                 rc = VERR_NOT_IMPLEMENTED;
    894                 break;
    895             }
    896             else if (u8Type == DBGF_BP_INT3_L1_ENTRY_TYPE_L2_IDX)
    897             {
    898                 /** @todo Walk the L2 tree searching for the correct spot, add the new entry
    899                  * and rebalance the tree. */
    900                 rc = VERR_NOT_IMPLEMENTED;
    901                 break;
    902             }
     1078            rc = dbgfR3BpInt3L2BstNodeAdd(pUVM, idxL1, hBp, pBp->Pub.u.Int3.GCPtr);
     1079            if (rc == VINF_TRY_AGAIN)
     1080                continue;
     1081
     1082            break;
    9031083        }
    9041084    }
    … …  
    9131093
    9141094/**
     1095 * @callback_method_impl{FNVMMEMTRENDEZVOUS}
     1096 */
     1097static DECLCALLBACK(VBOXSTRICTRC) dbgfR3BpInt3RemoveEmtWorker(PVM pVM, PVMCPU pVCpu, void *pvUser)
     1098{
     1099    DBGFBP hBp = (DBGFBP)(uintptr_t)pvUser;
     1100
     1101    VMCPU_ASSERT_EMT(pVCpu);
     1102    VM_ASSERT_VALID_EXT_RETURN(pVM, VERR_INVALID_VM_HANDLE);
     1103
     1104    PUVM pUVM = pVM->pUVM;
     1105    PDBGFBPINT pBp = dbgfR3BpGetByHnd(pUVM, hBp);
     1106    AssertPtrReturn(pBp, VERR_DBGF_BP_IPE_8);
     1107
     1108    int rc = VINF_SUCCESS;
     1109    if (pVCpu->idCpu == 0)
     1110    {
     1111        uint16_t idxL1 = DBGF_BP_INT3_L1_IDX_EXTRACT_FROM_ADDR(pBp->Pub.u.Int3.GCPtr);
     1112        uint32_t u32Entry = ASMAtomicReadU32(&pUVM->dbgf.s.paBpLocL1R3[idxL1]);
     1113        AssertReturn(u32Entry != DBGF_BP_INT3_L1_ENTRY_TYPE_NULL, VERR_DBGF_BP_IPE_6);
     1114
     1115        uint8_t u8Type = DBGF_BP_INT3_L1_ENTRY_GET_TYPE(u32Entry);
     1116        if (u8Type == DBGF_BP_INT3_L1_ENTRY_TYPE_BP_HND)
     1117        {
     1118            /* Single breakpoint, just exchange atomically with the null value. */
     1119            if (!ASMAtomicCmpXchgU32(&pUVM->dbgf.s.paBpLocL1R3[idxL1], DBGF_BP_INT3_L1_ENTRY_TYPE_NULL, u32Entry))
     1120            {
     1121                /*
     1122                 * A breakpoint addition must have raced us converting the L1 entry to an L2 index type, re-read
     1123                 * and remove the node from the created binary search tree.
     1124                 *
     1125                 * This works because after the entry was converted to an L2 index it can only be converted back
     1126                 * to a direct handle by removing one or more nodes which always goes through the fast mutex
     1127                 * protecting the L2 table. Likewise adding a new breakpoint requires grabbing the mutex as well
     1128                 * so there is serialization here and the node can be removed safely without having to worry about
     1129                 * concurrent tree modifications.
     1130                 */
     1131                u32Entry = ASMAtomicReadU32(&pUVM->dbgf.s.paBpLocL1R3[idxL1]);
     1132                AssertReturn(DBGF_BP_INT3_L1_ENTRY_GET_TYPE(u32Entry) == DBGF_BP_INT3_L1_ENTRY_TYPE_L2_IDX, VERR_DBGF_BP_IPE_9);
     1133
     1134                rc = dbgfR3BpInt2L2BstNodeRemove(pUVM, idxL1, DBGF_BP_INT3_L1_ENTRY_GET_L2_IDX(u32Entry),
     1135                                                 hBp, pBp->Pub.u.Int3.GCPtr);
     1136            }
     1137        }
     1138        else if (u8Type == DBGF_BP_INT3_L1_ENTRY_TYPE_L2_IDX)
     1139            rc = dbgfR3BpInt2L2BstNodeRemove(pUVM, idxL1, DBGF_BP_INT3_L1_ENTRY_GET_L2_IDX(u32Entry),
     1140                                             hBp, pBp->Pub.u.Int3.GCPtr);
     1141    }
     1142
     1143    return rc;
     1144}
     1145
     1146
     1147/**
    9151148 * Removes the given int3 breakpoint from all lookup tables.
    9161149 *
    … …  
    9241157    AssertReturn(DBGF_BP_PUB_GET_TYPE(pBp->Pub.fFlagsAndType) == DBGFBPTYPE_INT3, VERR_DBGF_BP_IPE_3);
    9251158
    926     int rc = VINF_SUCCESS;
    927     uint16_t idxL1 = DBGF_BP_INT3_L1_IDX_EXTRACT_FROM_ADDR(pBp->Pub.u.Int3.GCPtr);
    928 
    929     for (;;)
    930     {
    931         uint32_t u32Entry = ASMAtomicReadU32(&pUVM->dbgf.s.paBpLocL1R3[idxL1]);
    932         AssertReturn(u32Entry != DBGF_BP_INT3_L1_ENTRY_TYPE_NULL, VERR_DBGF_BP_IPE_6);
    933 
    934         uint8_t u8Type = DBGF_BP_INT3_L1_ENTRY_GET_TYPE(u32Entry);
    935         if (u8Type == DBGF_BP_INT3_L1_ENTRY_TYPE_BP_HND)
    936         {
    937             /* Single breakpoint, just exchange atomically with the null value. */
    938             if (ASMAtomicCmpXchgU32(&pUVM->dbgf.s.paBpLocL1R3[idxL1], DBGF_BP_INT3_L1_ENTRY_TYPE_NULL, u32Entry))
    939                 break;
    940             break;
    941         }
    942         else if (u8Type == DBGF_BP_INT3_L1_ENTRY_TYPE_L2_IDX)
    943         {
    944             /** @todo Walk the L2 tree searching for the correct spot, remove the entry
    945              * and rebalance the tree. */
    946             RT_NOREF(hBp);
    947             rc = VERR_NOT_IMPLEMENTED;
    948             break;
    949         }
    950     }
    951 
    952     return rc;
     1159    /*
     1160     * This has to be done by an EMT rendezvous in order to not have an EMT traversing
     1161     * any L2 trees while it is being removed.
     1162     */
     1163    return VMMR3EmtRendezvous(pUVM->pVM, VMMEMTRENDEZVOUS_FLAGS_TYPE_ALL_AT_ONCE, dbgfR3BpInt3RemoveEmtWorker, (void *)(uintptr_t)hBp);
    9531164}
    9541165
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