Shredding memory in C

I don’t recall exactly where I picked up the technique for shredding memory on allocation and dealloaction in C programs. I think it was from a usenet post (comp.lang.c). I do recall reading about memory shredding in a book I purchased some afterwards, but I don’t recall the title of that book.

While I don’t code C professionally at the moment, I do a bit of recreational C programming. I find that C keeps me “honest” when I’m working in other languages.

Here’s a great example of C memory shredding taken from a current project:

0xdadadada indicates uninitialized memory.

(Open the image in a new tab to see it at full size.)

See the line where it says u->parent: 0xdadadadadadadada? That’s my signal for unassigned pointer, which I set (by “shredding”) right after allocating the memory for the struct.

Backstory

The chain of events that led to this happening started with an attempt to implement a full suite of algorithms on binary search trees, using only left and right child pointers, and no parent pointers. This increases the difficulty of algorithms such as successor and predecesor, but not that much. A parent-free delete algorithm may also be defined and implemented, at the risk of unbalancing the tree over successive deletes.

The delete algorithm I’m currently implementing comes from CLRS 3rd Edition, and relies on parent pointers.

Which is fine, and not difficult at all to add to the Node struct:

#ifndef BST_NODE_PRIVATE_H
#define BST_NODE_PRIVATE_H

#include "../include/node.h"

struct _node {
  int key;
  Node * left;
  Node * right;
  Node * parent; // <--- parent member added for delete
};

#endif

What didn’t happen is initializing the new node’s parent to NULL on instantiation.

Which cause the transplant algorithm to fail its test, as can be seen in the screenshot above.

Instantiating a class in C

It’s possible to write object oriented code in C, and not that difficult for simple data structures. One key technique is treating memory allocations as “instantiations.” For example, consider instantiating a Node object:

  #include "node_private.h"

  Node *
  node_new(int key) {
    Node * n = calloc(1, sizeof(Node));
    memset((void *)n, 0xDA, sizeof(Node));
    n->key = key;
    n->left = NULL;
    n->right = NULL;
    n->parent = NULL // <---- forgot to do this!
    return n;
  }

Deallocating memory is the reverse: shred, then free.

If performance is critical, shredding and deallocation can be wrapped with #if DEBUG. It’s not pretty but it works.

Very simple technique, amazingly useful when practiced, and probably old hat to competent C programmers. If you’re just starting out with C, consider implementing a shredding policy for all your memory management. For the small amount of extra work involved, the time savings can be enormous. Shredded memory is one of those things which is invisible until you need it, then absolutely indispensible.