Leak Detection

To detect leaked memory locations:

1. Keep track of all memory objects that were allocated but not freed.
2. Identify all memory objects that are in use.
3. The leaked objects are the set 2 - 1.

There is no automated way of doing step 2. At various points, it is possible to identify points where no objects of a particular type are in use. Alternatively, with some work, it is generally possible to write a set of functions that walk over all data-structures. In general, to actually isolate leaks quickly, this is the only technique that is usable. We shall assume, in this section, that it is possible to walk over all allocated memory objects that are in use.

To automatically keep track of all allocated memory objects, we shall use the extended header idea. For leak detection, we define struct exthdr_ptr as:

	struct leak_exthdr_ptr {
	  char *		xhp_type_name;
	  unsigned		xhp_number;

	  /* doubly linked list of allocated, but not freed, blocks */
	  struct exthdr_ptr *	xhp_prev;
	  struct exthdr_ptr *	xhp_next;

	  /* Information useful for detecting leak location */
	  /* Location of allocation*/
	  char *		xhp_file;
	  int			xhp_line;
	  /* This is the <seq> allocation to occur; for leak location */
	  unsigned		xhp_seq;

	  /* used for mark-and-sweep */
	  unsigned		xhp_mark;

	  /* To force alignment */
	  union {
	    double		xhp_d;
	    unsigned long	xhp_ul;
	    int			xhp_i;
	    void *		xhp_p;
	  } xhp_align;
	};

	/* along with all the accessors */

We modify xalloc()/do_leak_xalloc() to pass in the file name and line number of the allocation. This turns out to be very useful for detecting where the leak actually occurred. Also, do_leak_xalloc() puts an allocated object on the list of blocks to allocated, but not freed.

	/* in xmemory.h */
	#define xalloc(_t) \
		((_t*)do_leak_xalloc(sizeof(_t), #_t, 0, __FILE__, __LINE__))
	#define xnalloc(_t,_n) \
		((_t*)do_leak_xalloc(sizeof(_t)*(_n), #_t, (_n), __FILE__, __LINE__))

	/* in leak_xmemory.c */

	static int lcl_seq_leak_xmemory = 0;
	static struct exthdr_ptr * lcl_list_leak_xmemory = 0;

	void *
      	do_leak_xalloc(
		unsigned	size,
		char *		type_name,
		unsigned	number,
		const char *	file_name,
		int		line
		)
	{
	  struct exthdr_ptr *	hdr = malloc(size + size_exthdr_ptr());

	  type_name_exthdr_ptr(hdr) = type_name;
	  number_exthdr_ptr(hdr) = number;
	  file_exthdr_ptr(hdr) = file_name;
	  line_exthdr_ptr(hdr) = line;

	  seq_extdhr_ptr(hdr) = lcl_seq_leak_xmemory;
	  lcl_seq_leak_xmemory++;

	  if( lcl_list_leak_xmemory ) {
	    x_prev_exthdr_ptr(lcl_list_leak_xmemory) = hdr;
	  }
	  x_next_exthdr_ptr(hdr) = lcl_list_leak_xmemory;
	  x_prev_exthdr_ptr(hdr) = 0;
	  lcl_list_leak_xmemory = hdr;

	  return alloc_exthdr_ptr(hdr);
	}

	void
	do_leak_xfree(
		void *		ptr
		)
        {
	  struct exthdr_ptr *	hdr = get_exthdr_ptr(ptr);
	  struct exthdr_ptr *	next = next_exthdr_ptr(hdr);
	  struct exthdr_ptr *	prev = prev_exthdr_ptr(hdr);

	  /* beginning of the list */
	  if( prev == 0 ) {
	    assert( lcl_list_leak_xmemory == hdr );
	    lcl_list_leak_xmemory = next;
	  }
	  else {
	    x_next_exthdr_ptr(prev) = next;
	  }
	  if( next ) {
	    x_prev_exthdr_ptr(next) = 0;
	  }

	  free(hdr);
	}

Now, we add 3 more functions to complete a minimal leak detection module.

	/* clear all marks for all still allocated objects */
	void
	reset_leak_xalloc( void )
	{
	  struct exthdr_ptr *	hdr;

	  for( hdr = lcl_list_leak_xmemory; hdr; hdr = next_exthdr_ptr(hdr)) {
	    x_mark_exthdr_ptr(hdr) = 0;
	  }
	}

	/* mark the object whose pointer is ptr */
	void
	mark_leak_xalloc(
		void *		ptr
		)
	{
	  struct exthdr_ptr *	hdr = get_exthdr_ptr(ptr);

	  x_mark_exthdr_ptr(hdr) = 1;
	}

	void
	dump_leak_xalloc(
		FILE *	fp
		)
	{
	  for( hdr = lcl_list_leak_xmemory; hdr; hdr = next_exthdr_ptr(hdr)) {
	    if( !mark_exthdr_ptr(hdr) ) {
	      fprintf(fp, "%p:%p:%s:%d:%s:%d:%d\n", ptr, hdr,
	      		type_name_exthdr_ptr(hdr),
	      		number_exthdr_ptr(hdr),
	      		file_name_exthdr_ptr(hdr),
	      		line_exthdr_ptr(hdr),
			seq_exthdr_ptr(hdr));
	    }
	  }
	}

To detect leaks using these functions:

1. clear all marks by calling reset_leak_xalloc().
2. Walk over all objects in use, marking each of them by using mark_leak_xalloc(object).
3. Finally, call dump_leak_xalloc() to report leaked objects.

The dump contains the type and number of the leaked object, the file name and line number it was originally allocated, and the sequence number where it was allocated. Hopefully, this will be enough to identify where the leak occurred.

Another way to identify where a leak occurs is to repeatedly call dump_leak_xalloc() at known points in the program. This way, you should be able to isolate the points between which a leak actually occurs.