path: root/sys/memio/doc/memio.hlp

.help memio Feb83 "Dynamic Memory Management Routines"
.sh
Introduction

    The memory management routines manage both a stack and a heap.
Storage for the stack may be fragmented, and chunks of stack storage are
allocated dynamically from the heap as needed.  Programs may allocate
heap storage directly if desired, for large or semipermanent buffers.
Stack storage is intended for use with small buffers, where the overhead
of allocating and deallocating space must be kept to a minimum.


.ks
.nf
heap routines:

	malloc  (ptr, number_of_elements, data_type)
	calloc  (ptr, number_of_elements, data_type)
	realloc (ptr, number_of_elements, data_type)
	mfree   (ptr, data_type)


stack routines:

	salloc  (ptr, number_of_elements, data_type)
	smark   (ptr)
	sfree   (ptr)
.fi
.ke


MALLOC allocates space on the heap.  CALLOC does the same, and fills the buffer
with zeroes.  REALLOC is used to change the size of a previously allocated
buffer, copying the contents of the buffer if necessary.  MFREE frees space
allocated by a prior call to MALLOC, CALLOC, or REALLOC.

Space is allocated on the stack with SALLOC.  SMARK should be called before
SALLOC, to mark the position of the stack pointer.  SFREE returns all space
allocated on the stack since the matching call to SMARK.


.KS
Example:
.nf
	pointer	buf, sp

	begin
		call smark (sp)
		call salloc (buf, SZ_BUF, TY_CHAR)
		while (getline (fd, Memc[buf]) != EOF) {
		    (code to use buffer ...)
		}
		call sfree (sp)
.fi
.KE


These routines will generate an error abort if memory cannot be allocated
for some reason.

.sh
Heap Management

    Since many operating systems provide heap management facilities,
MALLOC and MFREE consist of little more than calls to Z routines to
allocate and free blocks of memory.  The main function of MALLOC is
to convert the physical buffer address returned by the Z routine into
a pointer of the requested type.

The pointer returned to the calling routine does not point at the beginning
of the physical buffer, but at a location a few bytes into the buffer.
The physical address of the buffer is stored in the buffer, immediately
before the cell pointed to by the pointer returned by MALLOC.  The
stored address must be intact when MFREE is later called to deallocate
the buffer, or a "Memory corrupted" error diagnostic will result.

The Z routines required to manage the heap are the following:

.KS
.nf
	 zmget (bufadr, nbytes)
	zmrget (bufadr, nbytes)
	zmfree (buf_addr)
.fi
.KE

The "get" routines should return NULL as the buffer address if space
cannot be allocated for some reason.

.sh
Stack Management

    The heap management routines have quite a bit of overhead associated
with them, which precludes their use in certain applications.  In addition,
the heap can be most efficiently managed when it contains few buffers.
The stack provides an efficient mechanism for parceling out small amounts
of storage, which can later all be freed with a single call.

The main use of the stack is to provide automatic storage for local 
arrays in procedures.  The preprocessor compiles code which makes calls
to the stack management routines whenever an array is declared with the
storage calls AUTO, or whenever the ALLOC statement is used in a procedure.


.KS
.nf
	auto	char lbuf[SZ_LINE]
	real	x[n], y[n]
	int	n

	begin
		alloc (x[npix], y[npix])

		while (getline (fd, lbuf) != EOF) {
		    ...
.fi
.KE


The AUTO storage class and the ALLOC statement are provided in the full
preprocessor, but not in the subset preprocessor.  The following subset
preprocessor code is functionally equivalent to the code show above:


.KS
.nf
	pointer	lbuf, x, y, sp
	int	n, getline()

	begin
		call smark (sp)
		call salloc (lbuf, SZ_LINE, TY_CHAR)
		n = npix
		call salloc (x, n, TY_REAL)
		call salloc (y, n, TY_REAL)

		while (getline (fd, Memc[lbuf]) != EOF) {
		    ...

		call sfree (sp)
.fi
.KE

.sh
Semicode for Stack Management

    At any given time, the "stack" is a contiguous buffer of a certain size.
Stack overflow is handled by calling MALLOC to allocate another stack segment.
A pointer to the previous stack segment is kept in each new stack segment,
to permit reclamation of stack space.




.KS
.nf
		salloc             smark              sfree



	    stack_overflow 


	
		malloc            realloc             mfree



		zmget              zmrget             zmfree



		Structure of the Memory Management Routines
.fi
.KE




.tp 5
.nf
procedure salloc (bufptr, nelements, data_type)

bufptr:		upon output, contains pointer to the allocated space
nelements:	number of elements of space to be allocated
data_type:	data type of the elements and of the buffer pointer

begin
	# align stack pointer for the specified data type,
	# compute amount of storage to be allocated

	if (data_type == TY_CHAR)
	    nchars = nelements
	else {
	    sp = sp + mod (sp-1, sizeof(data_type))
	    nchars = nelements * sizeof(data_type)
	}

	if (sp + nchars > stack_top)		# see if room
	    call stack_overflow (nchars)

	if (data_type == TY_CHAR)		# return pointer
	    bufptr = sp
	else
	    bufptr = (sp-1) / sizeof(data_type) + 1

	sp = sp + nchars			# bump stack ptr
	return
end




.tp 5
procedure sfree (old_sp)			# pop the stack

begin
	# return entire segments until segment containing the old
	# stack pointer is reached

	while (old_sp < stack_base || old_sp > stack_top) {
	    if (this is the first stack segment)
		fatal error, invalid value for old_sp
	    stack_base = old_segment.stack_base
	    stack_top = old_segment.stack_top
	    mfree (segment_pointer, TY_CHAR)
	    segment_pointer = old_segment
	}

	sp = old_sp
end




.tp 5
procedure smark (old_sp)			# save stack pointer

begin
	old_sp = sp
end




.tp 5
procedure stack_overflow (nchars_needed)	# increase stk size

begin
	# allocate storage for new segment
	segment_size = max (SZ_STACK, nchars_needed + SZ_STKHDR)
	malloc (new_segment, segment_size, TY_CHAR)

	# initialize header for the new segment
	new_segment.old_segment = segment_pointer
	new_segment.stack_base = new_segment + SZ_STKHDR
	new_segment.stack_top = new_segment + segment_size

	# make new segment the current segment
	segment_pointer = new_segment
	stack_base = new_segment.stack_base
	stack_top = new_segment.stack_top
	sp = stack_base
end


.fi
The segment header contains fields describing the location and size of
the segment, plus a link pointer to the previous segment in the list.


.KS
.nf
	struct stack_header {
		char	*stack_base
		char	*stack_top
		struct	stack_header *old_segment
	}
.fi
.KE

.sh
Pointers and Addresses

    Pointers are indices into (one indexed) Fortran arrays.  A pointer to
an object of one datatype will in general have a different value than a
pointer to an object of a different datatype, even if the objects are stored
at the same physical address.  Pointers have strict alignment requirements,
and it is not always possible to coerce the type of a pointer.  For this
reason, the pointers returned by MALLOC and SALLOC are always aligned for
all data types, regardless of the data type requested.

The IRAF system code must occasionally manipulate and store true physical
addresses, obtained with the function LOC.  The problem with physical
addresses is that they are unsigned integers, but Fortran does not provide
any unsigned data types.  Thus, comparisons of addresses are difficult
in Fortran.

A second LOC primitive is provided for use in routines which must compare
addresses.  LOCC returns the address of the object passed as argument,
right shifted to the size of a CHAR.  Thus, the difference between LOCC(a[1])
and LOCC(a[n]) is the size of the N element array A in chars.

The relationship between chars, bytes, and machine addresses is machine
dependent.  Bytes seem to be the smallest units.  Some machines are byte
addressable, others are word addressable.  The size of a CHAR in machine
bytes is given by the constant SZB_CHAR.  The size of a machine word in
machine bytes is given by the constant SZB_WORD.