From: jholt@adobe.com (joe holt)
Subject: Re: Looping through all allocated blocks
Organization: Adobe Systems Inc.
Date: Thu, 27 Aug 1992 22:25:59 GMT

In article <17envmINNgab@function.mps.ohio-state.edu>, gregt@function.mps.ohio-state.edu (Gregory M Ferrar) writes:
> 
> I'm writing a program in THINK C, and I would really like to know how to
> examine each memory block in order.  In other words, I would like some sort
> of loop which allows me to process all handles or pointers which have been
> allocated since the start of the program.  How can this be done?
> 
>   -Greg Ferrar (gregt@function.mps.ohio-state.edu)
> 
> 

Greg,

Here's a small package I wrote for checking the consistency of a Macintosh
heap. It's similar to the routines in Swatch which build its memory bars (if
you've ever seen Swatch...). In broad terms, it shows how to walk a heap.
I hope this helps.
 
Written with THINK C 5.0.2.

/joe

---------- Heap_validate.h ----------

/**

	Heap_validate.h
	Check heap for consistency.

 **/

#ifndef __Heap_validate__
#define __Heap_validate__


/*	Errors returned by Heap_validate_info() about last Heap_validate() call. */

enum {
	Heap_validate_okay = 0,
	Heap_validate_zone_bad,						/* bad zone address */
	Heap_validate_zone_header_bad,				/* zone's bkLim not valid */
	Heap_validate_block_size_bad,				/* size is negative or way too big */
	Heap_validate_block_relative_handle_bad,	/* doesn't point where it should */
	Heap_validate_block_type_bad,				/* not a defined type */
	Heap_validate_master_pointer_bad			/* circle not consistent */
};


Boolean Heap_validate( THz zone );

/*	Validate the given heap. Returns true if the heap is consistent, false if
	there's a problem. For example:

		Heap_validate( ApplicZone() );	-- validate the current application
		Heap_validate( SystemZone() );	-- validate the system heap

	When Heap_validate returns false, call Heap_validate_info() for information
	about the nature of the inconsistency. */


void Heap_validate_info( short *error, Ptr *block );

/*	Return information about the nature of a heap inconsistency. If Heap_validate()
	says the heap is bad, Heap_validate_info() will point to the bad block and tell
	you why it is bad. Note that any inconsistency renders the heap unusable.

	Much heap debugging can be done without calling Heap_validate_info(). However, you
	may want to use this function to help zero in on the cause of the inconsistency.

	For example, if block A is bad with an error indicating that its header is
	clobbered (errors Heap_validate_block_size_bad, Heap_validate_block_type_bad or
	Heap_validate_block_relative_handle_bad), the cause may be that you wrote past
	the end of block A-1.

	Pass nil for error or block if you're not interested in the value. */

#endif

---------- end of Heap_validate.h ----------

---------- Heap_validate.c ----------

/**

	Heap_validate.c
	Check heap for consistency.

	version 1.0
	23 March 1992, joe holt

 **/


/**-----------------------------------------------------------------------------
 **
 **	Headers
 **
 **/

#include <GestaltEqu.h>		/* for querying about 24- and 32-bit addressing */
#include "Heap_validate.h"


/**-----------------------------------------------------------------------------
 **
 ** Private Variables
 **
 **/

/*	24-bit Memory Manager block header structure. Stored in the eight bytes
	preceding a heap block. See IM 2-23. */

typedef struct {
	long tag_and_size;		/* block type, size alignment, and physical size */
	long relative_handle;	/* pointer to master pointer */
} block_header_24_t;

/*	Physical size includes header size and size correction bytes at end of block.
	In other words, adding the physical size of block A to address of A gives
	the address of block A+1. */

/*	Relative handle is a pointer back to the block's master pointer if the block
	is relocatable. It is "relative" because it is expressed as an offset into
	the heap. That is, adding the relative handle of block A to the base address
	of the heap gives the address of block A's master pointer.

	If the block is nonrelocatable, the relative handle field contains the base
	address of the heap. The relative handles of all nonrelocatable blocks in
	the same heap contain the same value. */

/*	Size alignment is the extra "slop" bytes at the end of a block. They are
	not part of the logical block. See IM 2-24 for an explanation of why they
	exist. */

#define BLOCK_HEADER_24_SIZE_MASK 	0x00FFFFFF
#define BLOCK_HEADER_24_TYPE_MASK 	0xC0


/*	32-bit Memory Manager block header structure. Stored in the twelve bytes
	preceding a heap block. */

typedef struct {
	unsigned char type;		/* block type; see below */
	unsigned char flags;	/* block flags; see below */
	short alignment;		/* physical size alignment */
	long size;				/* physical size; same definition as above */
	long relative_handle;	/* same definition as above */
} block_header_32_t;


/*	Block type constants. Contained in upper byte of tag_and_size field for
	24-bit heaps and in the type field for 32-bit heaps. */

#define FREE_TYPE			0x00
#define NONREL_TYPE			0x40
#define HANDLE_TYPE			0x80


/*	Block flags constants. Contained in the upper byte of the master pointer
	for 24-bit heaps and in the flags field for 32-bit heaps. Defined only
	for relocatable blocks. */

#define LOCK_FLAG_MASK		0x80
#define PURGE_FLAG_MASK		0x40
#define RESOURCE_FLAG_MASK	0x20

#define MASTER_POINTER_24_ADDRESS_MASK	0x00FFFFFF


static Boolean heap_addressing_known = false;
static Boolean system_heap_is_32_bit, process_heaps_are_32_bit;

static short validate_error;
static void *validate_block;


/**-----------------------------------------------------------------------------
 **
 ** Private Functions
 **
 **/

/*	Determine the Memory Manager addressing mode for the System heap and for
	process (application) heaps. Gestalt Manager documentation suggests that
	they may not necessarily be the same. */

static void get_heap_addressing( void );
static void get_heap_addressing( void )
{
	long response;

	if ( Gestalt( gestaltAddressingModeAttr, &response ) )
		DebugStr( "\p get_heap_addressing(): Gestalt call failed" );

	system_heap_is_32_bit = (response & (1<<gestalt32BitSysZone)) != 0;
	process_heaps_are_32_bit = (response & (1<<gestalt32BitAddressing)) != 0;

	heap_addressing_known = true;
}


/*******************************************************************************
 **
 **	Public Functions
 **
 **/

/*	Validate the given heap. Returns true if the heap is consistent, false if
	there's a problem. For example:

		Heap_validate( ApplicZone() );	-- validate the current application
		Heap_validate( SystemZone() );	-- validate the system heap

	When Heap_validate returns false, call Heap_validate_info() for information
	about the nature of the inconsistency. */

Boolean Heap_validate( THz zone )
{
	Ptr bh, bkLim;
	long size;
	unsigned char type;
	short error;

	validate_block = nil;

	if ( (Ptr) zone < (Ptr) SysZone || (long) zone & 1 ) {
		error = Heap_validate_zone_bad;
		goto out;
	}

	bh = (Ptr) &zone->heapData;
	bkLim = zone->bkLim;

	if ( bkLim < bh || (long) bkLim & 1 ) {
		error = Heap_validate_zone_header_bad;
		goto out;
	}


	if ( !heap_addressing_known ) get_heap_addressing();

	if ( (zone == SysZone && system_heap_is_32_bit) || process_heaps_are_32_bit ) {

		for ( ;; ) {

			if ( bh > bkLim || ((long) bh & 1) ) {
				error = Heap_validate_block_size_bad;
				break;
			}

			if ( bh == bkLim ) {
				error = Heap_validate_okay;
				validate_block = nil;
				break;		// reached the end w/o problems
			}


			validate_block = bh + 12;	/* block logical address */

			size = ((block_header_32_t *)bh)->size;
			if ( bh + size <= bh ) {
				error = Heap_validate_block_size_bad;
				break;
			}

			type = ((block_header_32_t *)bh)->type;

			if ( type == NONREL_TYPE ) {
				if ( ((block_header_32_t *)bh)->relative_handle != (long) zone ) {
					error = Heap_validate_block_relative_handle_bad;
					break;
				}
			}

			else if ( type == HANDLE_TYPE ) {

				Ptr tp = (Ptr) zone + ((block_header_32_t *)bh)->relative_handle;

				if ( tp > bkLim || ((long) tp & 1) ) {
					error = Heap_validate_block_relative_handle_bad;
					break;
				}

				if ( *(Ptr *)tp != bh + 12 /* points to contents */ ) {
					error = Heap_validate_master_pointer_bad;
					break;
				}

			}

			else if ( type != FREE_TYPE ) {
				error = Heap_validate_block_type_bad;
				break;
			}


			bh += size;

		}
	}
	else {

		for ( ;; ) {

			if ( bh > bkLim || ((long) bh & 1) ) {
				error = Heap_validate_block_size_bad;
				break;
			}

			if ( bh == bkLim ) {
				error = Heap_validate_okay;
				validate_block = nil;
				break;		// reached the end w/o problems
			}

			validate_block = bh + 8;	/* block logical address */

			size = ((block_header_24_t *)bh)->tag_and_size & BLOCK_HEADER_24_SIZE_MASK;
			if ( bh + size <= bh ) {
				error = Heap_validate_block_size_bad;
				break;
			}

			type = (((block_header_24_t *)bh)->tag_and_size >> 24) &
					BLOCK_HEADER_24_TYPE_MASK;

			if ( type == NONREL_TYPE ) {
				if ( ((block_header_24_t *)bh)->relative_handle != (long) zone ) {
					error = Heap_validate_block_relative_handle_bad;
					break;
				}
			}

			else if ( type == HANDLE_TYPE ) {

				Ptr tp = (Ptr) zone + ((block_header_24_t *)bh)->relative_handle;

				if ( tp > bkLim || ((long) tp & 1) ) {
					error = Heap_validate_block_relative_handle_bad;
					break;
				}

				if ( (*(long *)tp & MASTER_POINTER_24_ADDRESS_MASK) != (long) bh + 8 ) {
					error = Heap_validate_master_pointer_bad;
					break;
				}
			}

			else if ( type != FREE_TYPE ) {
				error = Heap_validate_block_type_bad;
				break;
			}


			bh += size;

		}
	}

out:
	validate_error = error;
	return error == Heap_validate_okay;
}


/*	Return information about the nature of a heap inconsistency. If Heap_validate()
	says the heap is bad, Heap_validate_info() will point to the bad block and tell
	you why it is bad. Note that any inconsistency renders the heap unusable.

	Much heap debugging can be done without calling Heap_validate_info(). However, you
	may want to use this function to help zero in on the cause of the inconsistency.

	For example, if block A is bad with an error indicating that its header is
	clobbered (errors Heap_validate_block_size_bad, Heap_validate_block_type_bad or
	Heap_validate_block_relative_handle_bad), the cause may be that you wrote past
	the end of block A-1.

	Pass nil for error or block if you're not interested in the value. */

void Heap_validate_info( short *error, Ptr *block )
{
	if ( error ) *error = validate_error;
	if ( block ) *block = validate_block;
}