Why am I getting a segmentation fault with this code?

Question

Trying to make a simple rectangle/bin packer in C. Takes a given area and finds placement for any given size rectangle.

About after 4 recursions is when I get the segmentation fault.

#include <stdio.h>
#include <stdlib.h>

typedef struct node_type PackNode;
struct node_type {
 int x , y;
 int width , height;
 int used;
 struct node_type *left;
 struct node_type *right;
};

typedef struct point_type PackPoint;
struct point_type {
 int x,y;
};


PackNode _clone(PackNode *node) {
 PackNode clone;
 clone.used = 0;
 clone.x = node->x;
 clone.y = node->y;
 clone.width = node->width;
 clone.height= node->height;
 clone.left = NULL;
 clone.right= NULL;
 return clone;
}
PackNode root;
int rcount;

PackPoint* recursiveFind(PackNode *node, int w, int h) {
 PackPoint rp;
 PackPoint *p = NULL;
 rcount++;
 printf ("rcount = %u\n", rcount);


 //left is not null go to left, if left didn't work try right.
 if (node->left!=NULL) {
  //move down to left branch

  p = recursiveFind(node->left, w, h);
  if (p!=NULL) {
   return p;
  } else {
   p =  recursiveFind(node->right, w, h);
   return p;
  }

 } else {
  //If used just return null and possible go to the right branch;
  if (node->used==1 || w > node->width || h > node->height) {

   return p;
  }

  //if current node is exact size and hasn't been used it return the x,y of the mid-point of the rectangle
  if (w==node->width && h == node->height) {

   node->used=1;


   rp.x = node->x+(w/2);
   rp.y = node->y+(h/2);

   p = &rp;
   return p;
  }


  //If rectangle wasn't exact fit, create branches from cloning it's parent.

  PackNode l_clone = _clone(node);
  PackNode r_clone = _clone(node);
  node->left = &l_clone;
  node->right = &r_clone;

  //adjust branches accordingly, split up the current unused areas
  if ( (node->width - w) > (node->height - h) )
  {
   node->left->width = w;
   node->right->x = node->x + w;
   node->right->width = node->width - w;

  } else {
   node->left->height = h;
   node->right->y = node->y + h;
   node->right->height = node->height - h;
  }

  p = recursiveFind(node->left, w, h);
  return p;
 }
 return p;
}





int main(void) {
 root = malloc(
 root.x=0;
 root.y=0;
 root.used=0;
 root.width=1000;
 root.height=1000;
 root.left=NULL;
 root.right=NULL;


 int i;
 PackPoint *pnt;
 int rw;
 int rh;
 for (i=0;i<10;i++) {
  rw = random()%20+1;
  rh = random()%20+1;
  pnt = recursiveFind(&root, rw, rh);
  printf("pnt.x,y: %d,%d\n",pnt->x,pnt->y);
 }



 return 0;

}

Answer 1

You're returning a pointer to a local variable in this case:

  //if current node is exact size and hasn't been used it return the x,y of the mid-point of the rectangle
  if (w==node->width && h == node->height) {

   node->used=1;


   rp.x = node->x+(w/2);
   rp.y = node->y+(h/2);

   p = &rp;
   return p;
  }

That's a big no-no. The local variable is no longer valid after the function returns, so the pointer you're returning points to stack memory that's now potentially being used for something else. When you start doing stuff with that, you're corrupting your stack, and your program will start behaving very erratically.

To fix this, you'll need to do one of a few things: (1) have recursiveFind() return a PackNode by value, instead of a pointer to a PackNode; (2) use a global/static PackNode instance, and return a pointer to that (note that this then makes recursiveFind() non-thread-safe); or (3) return a pointer to a dynamically allocated instance of a PackNode (e.g. allocated with malloc()); this then requires that the caller of recursiveFind() call free() on the returned pointer at some later point when it's no longer needed.

Likewise, this code is also wrong:

  //If rectangle wasn't exact fit, create branches from cloning it's parent.

  PackNode l_clone = _clone(node);
  PackNode r_clone = _clone(node);
  node->left = &l_clone;
  node->right = &r_clone;

You need to allocate l_clone and r_clone on the heap, not on the stack, because again, as soon as this function returns, those node pointers will no longer be valid. I'd recommend having _clone() return a pointer to a PackNode (allocated with malloc()) instead of a full PackNode object by value. If you do that, though, the calling code needs to know to call free() on the returned pointer at some later point when the object is no longer needed.

[Also, identifiers at global scope beginning with an underscore are reserved by the implementation, so you should avoid using such names; you should rename _clone() to something like clone() or clonePackNode()].

Answer 2

 if (node->left!=NULL) {
  //move down to left branch

  p = recursiveFind(node->left, w, h);
  if (p!=NULL) {
   return p;
  } else {
   p =  recursiveFind(node->right, w, h);

You never check if node->right is NULL, so the next recursion may dereference NULL.

Answer 3

Without looking closely at your code, you might try using a tool such as Valgrind or GDB to identify the line number/expression causing the segmentation fault. You can work backwards from there.

“Give a man a fish; you have fed him for today. Teach a man to fish; and you have fed him for a lifetime”