vector passed by ref to the function getting de-allocated automatically

Question

I am trying to implement a segment tree and whenever I am trying to call my queryST(...) function below it's throwing a segmentation fault because it can not access the input vector st anymore. The vector st below is getting populated correctly via buildSt(...) but whenever the function queryST(...) is being called it's throwing segmentation fault. Code is shared below.

I have tried debugging with GDB and it shows a lot of similar backtraces like :

Program received signal SIGSEGV, Segmentation fault. 0x0000555555554de1 in queryST (st=..., v=0, L=0, R=0, l=2, r=3) at segtree.cpp:30 30 return queryST(st, 2*v, L, mid, l, r) + queryST(st, 2*v+1, mid+1, R, l, r);

Furthermore, when I am trying to print vector st in GDB for above mentioned frame, it says it cannot access memory at address ...

The vector st getting deallocated automatically or it's memory no more accessible, is being concluded by GDB.

queryST(...)

int queryST(vector<int>& st, int v, int L, int R, int l, int r) {

    if(l > R && r < L)
      return 0;

    if(l <= L && r >= R)
      return st[v];
    int mid = (L + R) / 2;

    return  queryST(st, 2*v, L, mid, l, r) + queryST(st, 2*v+1, mid+1, R, l, r);
 }

main(...)

int main() {
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

   vector<int> a({1,2,-3, 8, 9});
   vector<int> st(a.size()*4 + 1);
   buildST(st, a, 1, 0, 4);
   //cout << st[1] << endl;
   cout << queryST(st, 1, 0, 4, 2, 3) << endl;
   return 0;
 }

updateST(...)

void buildST(vector<int>& st, vector<int>& a, int v, int L, int R) {                                      
   if(L == R) {
      st[v] = a[L];
      return;
   }
    if(L < R) {
      int mid = (L+R)/2;
      buildST(st, a, 2*v, L, mid);
      buildST(st, a, 2*v+1, mid+1, R);
      st[v] = st[2*v] + st[2*v+1];
    } 
  }

Expected result should be the answer to the query range[2,3] corresponding to the parameters 5th and 6th of queryST(...)

Thanks.

Just taking a quick glance at the code you are not validating the value of `v`, is it possible it is going beyond the range of `st`? Can you show your `buildST` code, that way we could try to reproduce your error. — pstrjds, Aug 10 '19 at 21:07
You are blowing up the stack. You are recursing infinitely. You end up in a state where the arguments passed in are `v=0`, `L=0`, `l=2`, `R=0` and `r=3`. In that state both if's fail and you call the function again with the same arguments. — pstrjds, Aug 10 '19 at 21:18
exactly what I thought, but I still can't figure out how, my base condition is working correctly I think. — NoSuchUserException, Aug 10 '19 at 21:20
Well you are computing a `mid` based on the average of L and R, but when they are both 0, then the computation results in 0, you are then using that as your new R value and in that case v is also 0, which means you are making the call with the same values over again, which will again do the same computation and call with the same values, and so on... — pstrjds, Aug 10 '19 at 21:23
Okay my base condition for queryST is going bad, I figured it out, thanks a lot, a question tho: how did you figure out the stack is getting blown by looking at the stacktrace? Is there a way to do this in GDB? — NoSuchUserException, Aug 10 '19 at 21:26
Running out of stack space is a likely reason when you get an exception on a recursive call. — 1201ProgramAlarm, Aug 10 '19 at 21:27
one solution can be instead of using operator[] for the vector, use .at(). This way you can catch the exception and debug the code easier. — TonySalimi, Aug 10 '19 at 21:28
I used Visual Studio to catch it, but you can take a look here to see about setting catch points in gdb. https://stackoverflow.com/questions/1115428/run-an-application-in-gdb-until-an-exception-occurs — pstrjds, Aug 10 '19 at 21:30
Well I get stackoverflow a lot less rather I get those pointer faults a lot and I should have figured this out by looking at the backtrace because there were like 10000+ backtraces for this particular call of queryST(...) and all of them were for exact same parameters, so kind of got the idea but could not figure it out completely. I'm really thankful to you all. — NoSuchUserException, Aug 10 '19 at 21:31
But I still can't think of "why gdb couldn't access the vector `st` inside queryST() " as it was allocated before the stackoverflow and not yet deallocated — NoSuchUserException, Aug 10 '19 at 21:34
Stepping into the code and comparing what you get with what you expect at each step is a good way to debug that kind of good. You write the problem on paper and compare each step — Phil1970, Aug 11 '19 at 00:00

score 1 · Answer 1 · answered Aug 11 '19 at 07:34

But I still can't think of "why gdb couldn't access the vector st inside queryST() "

GDB uses debug info to access variables.

In order to print st, GDB needs to find a pointer to it. The debug info tells GDB that the pointer to st is on the stack, at certain offset from the $rsp or the $rbp register. When GDB tries to read that memory (via ptrace system call), ptrace returns an error (because $rsp points to unreadable memory due to stack overflow). Hence you get the cannot access memory at address ... error.

If you look at the actual address, you'll discover that it's just below the page boundary, and that the page above it is readable and is the last page of your stack.

vector passed by ref to the function getting de-allocated automatically

1 Answers1