1

I located several unaddressable access errors in my code. I know the line where memory corruption happens and the way to solve the problem however I can't understand what causes these errors.

I used DrMemory to detect memory problems and it pointed unaddressable access errors at lines 90, 95, 105. These lines look as:

nodes.at(currNodeId).childrenId.at(QUADRANT::RU) =  makeSubtree(pointsByQuadrant.at(QUADRANT::RU),
                              maxX,
                              maxY,
                              minX+(maxX-minX)/2,
                              minY+(maxY-minY)/2);

where nodes is a vector<QuadTreeNode>, field children_Id is array<int32_t,4> and makeSubtree is a function that may push new elements to nodes vector.

The error happens during the assignment operation. As you may see I only use .at() to access data inside vectors and arrays. My code does not complain about index out range so element that I assign a value to do exist.

I feel that the problem is related to a fact that makeSubtree function pushes new data to nodes that leads to memory reallocation. However, I can't come up with a reasonable explanation of how this leads to memory corruption. So I am looking for an explanation of how assignment to existing vector element may lead to such memory corruption.

If I rewrite the above code line as 

int RU =  makeSubtree(pointsByQuadrant.at(QUADRANT::RU),
                              maxX,
                              maxY,
                              minX+(maxX-minX)/2,
                              minY+(maxY-minY)/2);
nodes.at(currNodeId).childrenId.at(QUADRANT::RU) = RU;

the problem disappears and no memory corruption happens.

Entire code and DrMemory log is attached below.

Code: 

#include <vector>
#include <algorithm>
#include <iostream>
#include <array>
using namespace std;

enum QUADRANT{LU=0,LB=1,RU=2,RB=3};

struct QuadTreeNode{
    static int _id;
    int id;
    QuadTreeNode(){
        id = _id++;
        cout<<"Node "<<id++<<" made"<<endl;
        for(int i=0;i<childrenId.size();i++){
            childrenId.at(i)=-1;
        }
    }
    QuadTreeNode(QuadTreeNode const &another){
        id = _id++;
        cout<<"Node "<<id++<<" copied"<<endl;
        for(int i=0;i<childrenId.size();i++){
            childrenId.at(i)=another.childrenId.at(i);
        }
    }
    QuadTreeNode(QuadTreeNode &&another){
        id = _id++;
        cout<<"Node "<<id++<<" moved"<<endl;
        for(int i=0;i<childrenId.size();i++){
            childrenId.at(i)=another.childrenId.at(i);
        }
    }
    ~QuadTreeNode(){
        cout<<"Node "<<id<<" destroyed"<<endl;
    }
    array<int32_t,4> childrenId;
};
int QuadTreeNode::_id=0;

struct QuadTreePointF{
    QuadTreePointF(){}
    QuadTreePointF(float x, float y): x(x),y(y){}
    float x;
    float y;
};

class QuadTree
{
public:
    //vector<double> points contains x1,y1,x2,y2,..xn,yn coordinates of points
    QuadTree(vector<double> points, double maxX, double maxY, double minX, double minY);
    vector<QuadTreeNode> nodes;
    int rootId;

private:
    //Splits points into 4 groups accoring to relative position to center
    void splitByQuadrant(const vector<QuadTreePointF> &points, vector<vector<QuadTreePointF>> &pointsByQuadrant, const QuadTreePointF &center);
    void makeTree(vector<double> points, double maxX, double maxY, double minX, double minY);
    int makeSubtree(const vector<QuadTreePointF> &points, double maxX, double maxY, double minX, double minY);
};

QuadTree::QuadTree(vector<double> points, double maxX, double maxY, double minX, double minY)
{
    this->makeTree(points,maxX,maxY,minX,minY);
}

void QuadTree::makeTree(vector<double> points, double maxX, double maxY, double minX, double minY)
{
    if(points.size() > 0){
        nodes.clear();
        vector<QuadTreePointF> quadTreePoints(points.size()/2);
        for(int i=0;i<points.size();i+=2){
            quadTreePoints.at(i/2) = QuadTreePointF(points.at(i),points.at(i+1));
        }

        rootId = makeSubtree(quadTreePoints,maxX,maxY,minX,minY);
    }
}

int QuadTree::makeSubtree(const vector<QuadTreePointF> &points, double maxX, double maxY, double minX, double minY)
{
    if(points.size()==0) return -1;
    else{
        int currNodeId = this->nodes.size();
        nodes.push_back(QuadTreeNode());

        if(points.size() != 1){
            vector<vector<QuadTreePointF>> pointsByQuadrant(4);
            splitByQuadrant(points,pointsByQuadrant,QuadTreePointF((maxX+minX)/2,(maxY+minY)/2));
/*line 90*/ nodes.at(currNodeId).childrenId.at(QUADRANT::RU) =  makeSubtree(pointsByQuadrant.at(QUADRANT::RU),
                              maxX,
                              maxY,
                              minX+(maxX-minX)/2,
                              minY+(maxY-minY)/2);
/*line 95*/ nodes.at(currNodeId).childrenId.at(QUADRANT::RB) = makeSubtree(pointsByQuadrant.at(QUADRANT::RB),
                                maxX,
                                maxY-(maxY-minY)/2,
                                minX+(maxX-minX)/2,
                                minY);
/*line 100*/nodes.at(currNodeId).childrenId.at(QUADRANT::LU) = makeSubtree(pointsByQuadrant.at(QUADRANT::LU),
                                 maxX-(maxX-minX)/2,
                                 maxY,
                                 minX,
                                 minY+(maxY-minY)/2);
/*line 105*/nodes.at(currNodeId).childrenId.at(QUADRANT::LB) = makeSubtree(pointsByQuadrant.at(QUADRANT::LB),
                                 maxX-(maxX-minX)/2,
                                 maxY-(maxY-minY)/2,
                                 minX,
                                 minY);
            cout << currNodeId << ": " << nodes.at(currNodeId).childrenId.at(QUADRANT::RU) << " " <<
                nodes.at(currNodeId).childrenId.at(QUADRANT::RB) << " " <<
                nodes.at(currNodeId).childrenId.at(QUADRANT::LU) << " " <<
                nodes.at(currNodeId).childrenId.at(QUADRANT::LB)<<endl;
        }
        return currNodeId;
    }
}

void QuadTree::splitByQuadrant(const vector<QuadTreePointF> &points, vector<vector<QuadTreePointF>> &pointsByQuadrant, const QuadTreePointF &center){
    for(QuadTreePointF point: points){
        if(point.x >= center.x && point.y >= center.y){
            pointsByQuadrant.at(QUADRANT::RU).push_back(point);
        }else if(point.x >= center.x && point.y < center.y){
            pointsByQuadrant.at(QUADRANT::RB).push_back(point);
        }else if(point.x < center.x && point.y >= center.y){
            pointsByQuadrant.at(QUADRANT::LU).push_back(point);
        }else if(point.x < center.x && point.y < center.y){
            pointsByQuadrant.at(QUADRANT::LB).push_back(point);
        }
    }
}

int main(int argc, char *argv[])
{
    QuadTree quadTree(vector<double>{100,100, 10,10,78,35,11,11},111,111,0,0);
}

DrMemory log:

Dr. Memory version 1.11.0 build 2 built on Aug 29 2016 02:41:18
Dr. Memory results for pid 12996: "StandaloneQuadTree.exe"
Application cmdline: ""D:\Code\Cpp algorithms\build-StandaloneQuadTree-Desktop_Qt_5_12_1_MinGW_64_bit-Debug\debug\StandaloneQuadTree.exe""
Recorded 115 suppression(s) from default D:\Programs\DrMemory-Windows-1.11.0-2\bin64\suppress-default.txt

Error #1: UNADDRESSABLE ACCESS of freed memory: writing 0x0000000002891c0c-0x0000000002891c10 4 byte(s)
# 0 QuadTree::makeSubtree                              [../StandaloneQuadTree/main.cpp:90]
# 1 std::vector<>::_M_default_initialize               [D:/Programs/Qt5.9/Tools/mingw730_64/lib/gcc/x86_64-w64-mingw32/7.3.0/include/c++/bits/stl_vector.h:1347]
# 2 QuadTree::makeTree                                 [../StandaloneQuadTree/main.cpp:76]
# 3 QuadTree::QuadTree                                 [../StandaloneQuadTree/main.cpp:64]
# 4 main                                               [../StandaloneQuadTree/main.cpp:135]
Note: @0:00:00.172 in thread 14268
Note: 0x0000000002891c0c-0x0000000002891c10 overlaps memory 0x0000000002891c00-0x0000000002891c14 that was freed here:
Note: # 0 replace_operator_delete_nothrow               [d:\drmemory_package\common\alloc_replace.c:2974]
Note: # 1 msvcrt.dll!isleadbyte_l                      +0xd1     (0x00007fffb53e3372 <msvcrt.dll+0x3372>)
Note: # 2 libstdc++-6.dll!?                            +0x0      (0x000000006fcaec18 <libstdc++-6.dll+0x6ec18>)
Note: # 3 libstdc++-6.dll!?                            +0x0      (0x000000006fcfda9f <libstdc++-6.dll+0xbda9f>)
Note: # 4 libstdc++-6.dll!?                            +0x0      (0x000000006fcadc82 <libstdc++-6.dll+0x6dc82>)
Note: # 5 QuadTreeNode::~QuadTreeNode                   [../StandaloneQuadTree/main.cpp:34]
Note: instruction: mov    %eax -> (%rbx)

Error #2: UNADDRESSABLE ACCESS of freed memory: writing 0x0000000002891e50-0x0000000002891e54 4 byte(s)
# 0 QuadTree::makeSubtree                              [../StandaloneQuadTree/main.cpp:95]
# 1 std::vector<>::_M_default_initialize               [D:/Programs/Qt5.9/Tools/mingw730_64/lib/gcc/x86_64-w64-mingw32/7.3.0/include/c++/bits/stl_vector.h:1347]
# 2 QuadTree::makeTree                                 [../StandaloneQuadTree/main.cpp:76]
# 3 QuadTree::QuadTree                                 [../StandaloneQuadTree/main.cpp:64]
# 4 main                                               [../StandaloneQuadTree/main.cpp:135]
Note: @0:00:00.188 in thread 14268
Note: 0x0000000002891e50-0x0000000002891e54 overlaps memory 0x0000000002891e40-0x0000000002891e68 that was freed here:
Note: # 0 replace_operator_delete_nothrow               [d:\drmemory_package\common\alloc_replace.c:2974]
Note: # 1 msvcrt.dll!isleadbyte_l                      +0xd1     (0x00007fffb53e3372 <msvcrt.dll+0x3372>)
Note: # 2 libstdc++-6.dll!?                            +0x0      (0x000000006fcaec18 <libstdc++-6.dll+0x6ec18>)
Note: # 3 libstdc++-6.dll!?                            +0x0      (0x000000006fcfda9f <libstdc++-6.dll+0xbda9f>)
Note: # 4 libstdc++-6.dll!?                            +0x0      (0x000000006fcadc82 <libstdc++-6.dll+0x6dc82>)
Note: # 5 QuadTreeNode::~QuadTreeNode                   [../StandaloneQuadTree/main.cpp:34]
Note: instruction: mov    %eax -> (%rbx)

Error #3: UNADDRESSABLE ACCESS of freed memory: writing 0x0000000002892100-0x0000000002892104 4 byte(s)
# 0 QuadTree::makeSubtree                              [../StandaloneQuadTree/main.cpp:105]
# 1 QuadTree::splitByQuadrant                          [../StandaloneQuadTree/main.cpp:120]
# 2 QuadTree::makeSubtree                              [../StandaloneQuadTree/main.cpp:90]
# 3 QuadTree::splitByQuadrant                          [../StandaloneQuadTree/main.cpp:120]
# 4 QuadTree::makeSubtree                              [../StandaloneQuadTree/main.cpp:105]
# 5 QuadTree::splitByQuadrant                          [../StandaloneQuadTree/main.cpp:120]
# 6 QuadTree::makeSubtree                              [../StandaloneQuadTree/main.cpp:105]
# 7 QuadTree::makeSubtree                              [../StandaloneQuadTree/main.cpp:105]
# 8 std::vector<>::_M_default_initialize               [D:/Programs/Qt5.9/Tools/mingw730_64/lib/gcc/x86_64-w64-mingw32/7.3.0/include/c++/bits/stl_vector.h:1347]
# 9 QuadTree::makeTree                                 [../StandaloneQuadTree/main.cpp:76]
#10 QuadTree::QuadTree                                 [../StandaloneQuadTree/main.cpp:64]
#11 main                                               [../StandaloneQuadTree/main.cpp:135]
Note: @0:00:00.188 in thread 14268
Note: 0x0000000002892100-0x0000000002892104 overlaps memory 0x0000000002892080-0x0000000002892120 that was freed here:
Note: # 0 replace_operator_delete_nothrow               [d:\drmemory_package\common\alloc_replace.c:2974]
Note: # 1 msvcrt.dll!isleadbyte_l                      +0xd1     (0x00007fffb53e3372 <msvcrt.dll+0x3372>)
Note: # 2 libstdc++-6.dll!?                            +0x0      (0x000000006fcaec18 <libstdc++-6.dll+0x6ec18>)
Note: # 3 libstdc++-6.dll!?                            +0x0      (0x000000006fcfda9f <libstdc++-6.dll+0xbda9f>)
Note: # 4 libstdc++-6.dll!?                            +0x0      (0x000000006fcadc82 <libstdc++-6.dll+0x6dc82>)
Note: # 5 QuadTreeNode::~QuadTreeNode                   [../StandaloneQuadTree/main.cpp:34]
Note: instruction: mov    %eax -> (%rbx)

Error #4: UNADDRESSABLE ACCESS of freed memory: writing 0x00000000028920f0-0x00000000028920f4 4 byte(s)
# 0 QuadTree::makeSubtree                              [../StandaloneQuadTree/main.cpp:90]
# 1 QuadTree::splitByQuadrant                          [../StandaloneQuadTree/main.cpp:120]
# 2 QuadTree::makeSubtree                              [../StandaloneQuadTree/main.cpp:105]
# 3 QuadTree::splitByQuadrant                          [../StandaloneQuadTree/main.cpp:120]
# 4 QuadTree::makeSubtree                              [../StandaloneQuadTree/main.cpp:105]
# 5 QuadTree::makeSubtree                              [../StandaloneQuadTree/main.cpp:105]
# 6 std::vector<>::_M_default_initialize               [D:/Programs/Qt5.9/Tools/mingw730_64/lib/gcc/x86_64-w64-mingw32/7.3.0/include/c++/bits/stl_vector.h:1347]
# 7 QuadTree::makeTree                                 [../StandaloneQuadTree/main.cpp:76]
# 8 QuadTree::QuadTree                                 [../StandaloneQuadTree/main.cpp:64]
# 9 main                                               [../StandaloneQuadTree/main.cpp:135]
Note: @0:00:00.204 in thread 14268
Note: 0x00000000028920f0-0x00000000028920f4 overlaps memory 0x0000000002892080-0x0000000002892120 that was freed here:
Note: # 0 replace_operator_delete_nothrow               [d:\drmemory_package\common\alloc_replace.c:2974]
Note: # 1 msvcrt.dll!isleadbyte_l                      +0xd1     (0x00007fffb53e3372 <msvcrt.dll+0x3372>)
Note: # 2 libstdc++-6.dll!?                            +0x0      (0x000000006fcaec18 <libstdc++-6.dll+0x6ec18>)
Note: # 3 libstdc++-6.dll!?                            +0x0      (0x000000006fcfda9f <libstdc++-6.dll+0xbda9f>)
Note: # 4 libstdc++-6.dll!?                            +0x0      (0x000000006fcadc82 <libstdc++-6.dll+0x6dc82>)
Note: # 5 QuadTreeNode::~QuadTreeNode                   [../StandaloneQuadTree/main.cpp:34]
Note: instruction: mov    %eax -> (%rbx)

Error #5: UNADDRESSABLE ACCESS of freed memory: writing 0x00000000028920d8-0x00000000028920dc 4 byte(s)
# 0 QuadTree::makeSubtree                              [../StandaloneQuadTree/main.cpp:105]
# 1 QuadTree::splitByQuadrant                          [../StandaloneQuadTree/main.cpp:120]
# 2 QuadTree::makeSubtree                              [../StandaloneQuadTree/main.cpp:105]
# 3 QuadTree::makeSubtree                              [../StandaloneQuadTree/main.cpp:105]
# 4 std::vector<>::_M_default_initialize               [D:/Programs/Qt5.9/Tools/mingw730_64/lib/gcc/x86_64-w64-mingw32/7.3.0/include/c++/bits/stl_vector.h:1347]
# 5 QuadTree::makeTree                                 [../StandaloneQuadTree/main.cpp:76]
# 6 QuadTree::QuadTree                                 [../StandaloneQuadTree/main.cpp:64]
# 7 main                                               [../StandaloneQuadTree/main.cpp:135]
Note: @0:00:00.204 in thread 14268
Note: 0x00000000028920d8-0x00000000028920dc overlaps memory 0x0000000002892080-0x0000000002892120 that was freed here:
Note: # 0 replace_operator_delete_nothrow               [d:\drmemory_package\common\alloc_replace.c:2974]
Note: # 1 msvcrt.dll!isleadbyte_l                      +0xd1     (0x00007fffb53e3372 <msvcrt.dll+0x3372>)
Note: # 2 libstdc++-6.dll!?                            +0x0      (0x000000006fcaec18 <libstdc++-6.dll+0x6ec18>)
Note: # 3 libstdc++-6.dll!?                            +0x0      (0x000000006fcfda9f <libstdc++-6.dll+0xbda9f>)
Note: # 4 libstdc++-6.dll!?                            +0x0      (0x000000006fcadc82 <libstdc++-6.dll+0x6dc82>)
Note: # 5 QuadTreeNode::~QuadTreeNode                   [../StandaloneQuadTree/main.cpp:34]
Note: instruction: mov    %eax -> (%rbx)

Error #6: UNADDRESSABLE ACCESS of freed memory: writing 0x0000000002891ef4-0x0000000002891ef8 4 byte(s)
# 0 QuadTree::makeSubtree                              [../StandaloneQuadTree/main.cpp:105]
# 1 std::vector<>::_M_default_initialize               [D:/Programs/Qt5.9/Tools/mingw730_64/lib/gcc/x86_64-w64-mingw32/7.3.0/include/c++/bits/stl_vector.h:1347]
# 2 QuadTree::makeTree                                 [../StandaloneQuadTree/main.cpp:76]
# 3 QuadTree::QuadTree                                 [../StandaloneQuadTree/main.cpp:64]
# 4 main                                               [../StandaloneQuadTree/main.cpp:135]
Note: @0:00:00.204 in thread 14268
Note: 0x0000000002891ef4-0x0000000002891ef8 overlaps memory 0x0000000002891eb0-0x0000000002891f00 that was freed here:
Note: # 0 replace_operator_delete_nothrow               [d:\drmemory_package\common\alloc_replace.c:2974]
Note: # 1 msvcrt.dll!isleadbyte_l                      +0xd1     (0x00007fffb53e3372 <msvcrt.dll+0x3372>)
Note: # 2 libstdc++-6.dll!?                            +0x0      (0x000000006fcaec18 <libstdc++-6.dll+0x6ec18>)
Note: # 3 libstdc++-6.dll!?                            +0x0      (0x000000006fcfda9f <libstdc++-6.dll+0xbda9f>)
Note: # 4 libstdc++-6.dll!?                            +0x0      (0x000000006fcadc82 <libstdc++-6.dll+0x6dc82>)
Note: # 5 QuadTreeNode::~QuadTreeNode                   [../StandaloneQuadTree/main.cpp:34]
Note: instruction: mov    %eax -> (%rbx)

Error #7: POSSIBLE LEAK 131 direct bytes 0x00000000028901e0-0x0000000002890263 + 0 indirect bytes
# 0 replace_malloc                     [d:\drmemory_package\common\alloc_replace.c:2576]
# 1 ntdll.dll!RtlCopyUnicodeString    +0x45     (0x00007fffb58c382a <ntdll.dll+0x2382a>)
# 2 ntdll.dll!LdrGetDllFullName       +0x52     (0x00007fffb58bffeb <ntdll.dll+0x1ffeb>)
# 3 pre_cpp_init          
# 4 msvcrt.dll!initterm               +0x1e     (0x00007fffb53e5d53 <msvcrt.dll+0x5d53>)
# 5 __tmainCRTStartup     
# 6 .l_start              
# 7 KERNEL32.dll!BaseThreadInitThunk  +0xc      (0x00007fffb39816ad <KERNEL32.dll+0x16ad>)

===========================================================================
FINAL SUMMARY:

DUPLICATE ERROR COUNTS:
    Error #   6:      2

SUPPRESSIONS USED:

ERRORS FOUND:
      6 unique,     7 total unaddressable access(es)
      0 unique,     0 total invalid heap argument(s)
      0 unique,     0 total GDI usage error(s)
      0 unique,     0 total handle leak(s)
      0 unique,     0 total warning(s)
      0 unique,     0 total,      0 byte(s) of leak(s)
      1 unique,     1 total,    131 byte(s) of possible leak(s)
ERRORS IGNORED:
      2 potential error(s) (suspected false positives)
         (details: D:\Programs\DrMemory-Windows-1.11.0-2\drmemory\logs\DrMemory-StandaloneQuadTree.exe.12996.000\potential_errors.txt)
      7 unique,     7 total,   5002 byte(s) of still-reachable allocation(s)
         (re-run with "-show_reachable" for details)
Details: D:\Programs\DrMemory-Windows-1.11.0-2\drmemory\logs\DrMemory-StandaloneQuadTree.exe.12996.000\results.txt
E_net4
  • 27,810
  • 13
  • 101
  • 139
xevepisis
  • 47
  • 1
  • 5

1 Answers1

0

Seems really easy to understand after all the investigation you already did.

If the vector is resized then the memory gets relocated and you're accessing already freed memory on the assignment.

//this is essentially the left side in your original code
int32_t* leftSide = &(nodes.at(currNodeId).childrenId.at(QUADRANT::RU));
int RU =  makeSubtree(pointsByQuadrant.at(QUADRANT::RU),
                              maxX,
                              maxY,
                              minX+(maxX-minX)/2,
                              minY+(maxY-minY)/2);
//this is the left side as it should be
int32_t* leftSide2 = &(nodes.at(currNodeId).childrenId.at(QUADRANT::RU));
assert(leftSide2 == leftSide); //this will fail if the vector resizes

As an aside I'm not sure that this failing is now standards conforming, because the C++17 Standard introduced this rule:

In every simple assignment expression E1=E2 and every compound assignment expression E1@=E2, every value computation and side-effect of E2 is sequenced before every value computation and side effect of E1

PeterT
  • 7,981
  • 1
  • 26
  • 34
  • Ha, I remember doing that in C back in the 90s. *Plus ça change …* – Tom Zych Feb 16 '19 at 12:21
  • The thing that is was not clear for me is when the address of `nodes.at(currNodeId)` is computed. Apparently from your answer and things I observe in my code this happens before the right side is evaluated. That explains everything. I was thinking that the order is different. Actually, I just found [this post](https://stackoverflow.com/questions/3457967/what-belongs-in-an-educational-tool-to-demonstrate-the-unwarranted-assumptions-p/3458842#3458842) that says "The order of evaluation of `=` is undefined". I guess the answer should mention this fact. Add it if you can. Thank you. – xevepisis Feb 16 '19 at 12:38
  • Thank you for mentioning that the evaluation order is defined in C++17. That useful information. – xevepisis Feb 16 '19 at 12:44