1

I am new to this forum and I am still an amateur in programming languages so please be kind with any of my silly mistakes :p

I am programming a recursive function which builds a kd-tree for a search process. I am using the c language on Visual Studio '08. After some seconds of processing, the program execution halts due to an error namely:

Unhandled exception at 0x77063de7 in run_FAST_corner_detection.exe: 0xC00000FD: Stack overflow

Now when the code breaks, there is a green arrow just near the instruction:

kd_node = malloc(sizeof(struct kd_node));
//this function allocates a pointer to a reserved memory of size struct kd_node.

Is this the classical problem of running out of memory? How can I monitor the stack memory? (I know that this question has been asked repeatedly but honestly I have yet found no good method to do this).

4
  • Just in case it isn't clear: the dynamic memory allocated by malloc is not allocated on the stack, it is allocated on the heap. It might of course be possible that you get a stack overflow at that very function call, and it just happened to be malloc. To protect against the heap running out of memory, check the result of malloc against NULL.
    – Lundin
    Jan 20, 2012 at 7:31
  • This looks like a classic stack overflow to me. What is the condition that unwinds/returns from the recursive function? Even if you do this iteratively it will crash if your termination condition is incorrect. Posting the whole function will allow for a better appraisal. Jan 20, 2012 at 7:32
  • Ok I managed. A link to the code is below: skydrive.live.com/… This code is used to create a kd-tree for a kd-tree search algorithm. I have researched on tail recursion so to avoid recurion, but due to the if statement at the end I think that I cannot really use this technique. I am thinking about converting it to an iterative procedure, but I am not really sure how I can do this due to how the trees are made. Thanks for your time.
    – bouvett
    Jan 20, 2012 at 9:03
  • Instead of posting code to an external link, you should click "edit" and post the more relevant pieces of code in this question. If you don't it will likely cause people to vote to close the question if the question doesn't give them enough information to actually help them.
    – casperOne
    Jan 20, 2012 at 13:34

2 Answers 2

1

Well, the stack overflow might be due to you calling malloc while deep in the recursion. The call to malloc pushes the return address and perhaps even parameters on the stack and this might be the thing which causes the stack to overflow. Don't do recursions in your code - try to make the code iterative (with loops instead). This is especially true for when the recursion is not bounded.

2
  • Thanks for your reply. I am in the process of converting the process to an iterative one as you suggested. Is there a way to monitor the stack memory though? thanks again
    – bouvett
    Jan 20, 2012 at 7:10
  • 1
    Do you mean while debugging or at runtime? You could watch the SP register while debugging and see how it gets decreased until it reaches the stack limit. You could also probably handle your currently unhandled Stack Overflow exception, but again, this might only be adequate for debugging purposes.
    – smichak
    Jan 20, 2012 at 7:15
1

To monitor stack usage, simply take the address of any local variable (one defined within a function), and compare it against the address of a local variable in your main function (or thread entry function):

int stack_bottom;

int stack-usage () {
  int top = 0;

  /* Note, stack grows downward through memory, so high - low is .. */
  return stack_bottom - (int)⊤
}

....

int main () {
  int bottom = 0;

  stack_bottom = (int)⊥

  ....
}

To reduce stack usage, either limit recursion, or avoid using large local variables (such as structs, arrays) and don't use alloca. You can replace large local variable with pointers to dynamically allocated heap memory (but don't forget to free it!)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.