ftp.nice.ch/pub/next/unix/developer/pcn.2.0.s.tar.gz#/src/runtime/grow_heap.c

This is grow_heap.c in view mode; [Download] [Up]

/*
 * PCN Abstract Machine Emulator
 * Authors:     Steve Tuecke and Ian Foster
 *              Argonne National Laboratory
 *
 * Please see the DISCLAIMER file in the top level directory of the
 * distribution regarding the provisions under which this software
 * is distributed.
 *
 * grow_heap.c - code to increase the heap size.
 */

#ifndef NO_VIRTUAL_MEMORY

#include	"pcn.h"

#define OnOldHeap(Ptr) \
    ((_p_heap_bottom <= (Ptr)) && ((Ptr) <= _p_heap_hard_top))


static	cell_t *new_heap_bottom;	/* newly malloc'ed heap */
#ifdef PCN_ALIGN_DOUBLES
static	int_t	new_heap_bottom_pad;
#endif
static	u_int_t	cells_in_use;		/* # of cells in use on the heap */
static	int_t	structure_ptr_offset;	/* offset between _p_structure*ptr's */

static	void		copy_scan();
static	void		deref_everything();
static	void		deref_proc_record();
static	void		deref_process_queue();
static	void		deref_suspension_queue();
static	void		deref_irt();
static	void		deref_current_proc();
static	void		deref_pointer();

/*
 * _p_grow_heap()
 *
 * Increase the heap size by malloc'ing new space
 * for the larger heap, copying all the
 * data over to the new heap, and then updating all pointer.
 *
 * Note: The marking method used by this algorithm restricts the
 * type of data structures that can live off the heap.  Specificly,
 * any offheap data structures must NOT contains pointers to other
 * data structures.  Therefore, you cannot have offheap tuples, undefs,
 * or rrefs.  The only allowable offheap data structures are integers,
 * doubles, and strings. (And, of course, proc_records and value_notes
 * can be offheap.  But they are not user data structures.)
 *
 * The copying routine (copy_scan) copies each data structure from
 * the old heap to the newly malloc'd heap.  In the process, it
 * changes the old heap data structure be a pointer to the new heap
 * data structure.  It also sets the mark bit in the data structure
 * headers on the new heap.
 *
 * The pointer dereferencing routine (deref_everything) traverses
 * the data structure tree, dereferencing all pointers along the way.
 * Therefore, any pointers to things on the old heap will be
 * dereferenced through to the new heap.  Along the way, it clears
 * the mark bit in the data structure headers. If an unmarked data
 * structure is found, we know we have either already visited it or
 * it is offheap.  In either case, do not follow the tree any deeper.
 *
 * Why was this marking strategy chosen?  The overhead is minimal,
 * both in execution time an in the amount of code required to
 * implement it. The above mentioned restriction is no problem in
 * the current implementation.  And it leaves all mark bits clear
 * when it is done, which is a prerequisite.
 */
void _p_grow_heap(new_heap_size)
u_int_t new_heap_size;
{

#ifdef DEBUG
    fprintf(_p_stdout, "(%lu,%lu) Warning: Start increasing heap size (old_size=%lu, new_size=%lu)\n",
	    (unsigned long) _p_my_id, (unsigned long) _p_reduction,
	    (unsigned long) _p_heap_size,
	    (unsigned long) new_heap_size);
    fflush(_p_stdout);
    if (GCDebug(4))
    {
	fprintf(_p_stdout, "(%lu) GROW: Before: _p_heap_bottom=%lx, _p_heap_ptr=%lx, _p_heap_hard_top=%lx\n",
		(unsigned long) _p_my_id, (unsigned long) _p_heap_bottom,
		(unsigned long) _p_heap_ptr,
		(unsigned long) _p_heap_hard_top);
	fflush(_p_stdout);
    }
#endif /* DEBUG */
    
#ifdef PDB
    if (GCDebug(5))
    {
	fprintf(_p_stdout, "(%lu) GROW:\t Process Queues - BEFORE\n",
		(unsigned long) _p_my_id);
	_pdb_print_all_processes();
	fprintf(_p_stdout, "(%lu) GROW:\t End of Process Queues - BEFORE\n",
		(unsigned long) _p_my_id);
	fflush(_p_stdout);
    }
#endif /* PDB */
    
    /*******************************************************
     *
     * This is the real heap increase code.
     *
     * We must use malloc() instead of realloc() because we need
     * to use the old heap in order to trace pointers through to
     * the new heap.
     *
     *******************************************************/
    cells_in_use = _p_heap_ptr - _p_heap_bottom;
    if ( ( (new_heap_bottom =
	    (cell_t *) malloc((size_t) ((new_heap_size * CELL_SIZE)
#ifdef PCN_ALIGN_DOUBLES					
					+ DOUBLE_WORD_SIZE
#endif
					))) == (cell_t *) NULL) )
    {
	_p_malloc_error();
    }
    AlignDoubleOnOddWord((cell_t *), new_heap_bottom, new_heap_bottom_pad);

    structure_ptr_offset = -1;
    copy_scan();
    deref_everything();
    if (structure_ptr_offset >= 0)
	_p_structure_ptr = _p_structure_start_ptr + structure_ptr_offset;

    ZeroOutMemory(_p_heap_bottom, (_p_heap_size * CELL_SIZE));
    free(((char *) _p_heap_bottom)
#ifdef PCN_ALIGN_DOUBLES	 
	 - _p_heap_bottom_pad
#endif
	 );
    
    _p_heap_bottom = new_heap_bottom;
#ifdef PCN_ALIGN_DOUBLES	 
    _p_heap_bottom_pad = new_heap_bottom_pad;
#endif
    _p_heap_size = new_heap_size;
    _p_heap_cancel_top = _p_heap_real_top = _p_heap_bottom + new_heap_size;
    CalcHeapTops();
    _p_heap_ptr = _p_heap_bottom + cells_in_use;

#ifdef PDB
    if (GCDebug(5))
    {
	fprintf(_p_stdout, "(%lu) GROW:\t Process Queues - AFTER\n",
		(unsigned long) _p_my_id);
	_pdb_print_all_processes();
	fprintf(_p_stdout, "(%lu) GROW:\t End of Process Queues - AFTER\n",
		(unsigned long) _p_my_id);
	fflush(_p_stdout);
    }
#endif /* PDB */
    
#ifdef DEBUG	
    if (GCDebug(4))
    {
	fprintf(_p_stdout, "(%lu) GROW:  After: _p_heap_bottom=%lx, _p_heap_ptr=%lx, _p_heap_hard_top=%lx\n",
		(unsigned long) _p_my_id, (unsigned long) _p_heap_bottom,
		(unsigned long) _p_heap_ptr,
		(unsigned long) _p_heap_hard_top);
	fflush(_p_stdout);
    }
    fprintf(_p_stdout, "(%lu,%lu) Warning: Done  increasing heap size\n",
	    (unsigned long) _p_my_id, (unsigned long) _p_reduction);
    fflush(_p_stdout);
#endif /* DEBUG */
	
} /* _p_grow_heap() */


/*
 * copy_scan();
 *
 * Do a scan of the data on the old heap.  In the process:
 *	- copying each data structure from the old heap to the new heap, and
 *	- overwrite the data structure on the old heap to have a pointer
 *		to the equivalent data structure on the new heap
 */
static void copy_scan()
{
    cell_t *cp, *cp_target;
    cell_t *new_loc;
    u_int_t tag;
    u_int_t size, i, size_in_cells;
    cell_t *arg, *arg_target;
    cell_t *heap_last_used;

    /*
     * new_loc is used to point to where data structure will
     * end up on the new heap.
     */
    new_loc = new_heap_bottom;
    
    cp = _p_heap_bottom;
    heap_last_used = cp + cells_in_use;
    while (cp < heap_last_used)
    {
	/*
	 * It is assumed that the old heap is fully garbage collected, so
	 * that we should never encounter pointers on the heap, except inside
	 * tuples, undefs, and rrefs.  And we should never encounter
	 * empty cells (i.e., contain the value 0).
	 */
#ifdef DEBUG	
	if (*cp == 0 || IsRef(cp))
	{
	    _p_fatal_error("copy_scan(): Corrupt heap encountered during heap increase!");
	}
#endif /* DEBUG */	
	
	size_in_cells = _p_size_with_trailer(((data_header_t *) cp)->tag,
					     ((data_header_t *) cp)->size);
	
	/*
	 * Copy this data structure to its new location, and leave
	 * a forwarding address at the old location.
	 */
	memcpy(new_loc, cp, (size_in_cells * CELL_SIZE));
	*((cell_t **) cp) = new_loc;
	((data_header_t *)new_loc)->mark = 1;
	
	new_loc += size_in_cells;
	cp += size_in_cells;
    }

#ifdef DEBUG
    if (new_loc != new_heap_bottom + cells_in_use)
    {
	char buf[256];
	sprintf(buf,
		"copy_scan(): new_loc (0x%lx) != new_heap_bottom + cells_in_use (0x%lx) at end of copy scan in heap increase",
		(unsigned long) new_loc,
		(unsigned long) (new_heap_bottom + cells_in_use) );
	_p_fatal_error(buf);
    }
#endif /* DEBUG */    

} /* copy_scan() */


/*
 * deref_everything()
 *
 * For each of the off heap pointers (process queues, IRT, etc),
 * dereference the pointer, and trace down through data structures,
 * dereferencing pointers in the process.
 */
static void deref_everything()
{
    int_t i;

    deref_process_queue(_p_active_qf, _p_active_qb);
    deref_process_queue(_p_globsusp_qf, _p_globsusp_qb);
#ifdef PDB    
    deref_process_queue(_pdb_pending_qf, _pdb_pending_qb);
#endif /* PDB */
    
#ifdef PARALLEL
    if (_p_multiprocessing)
    {
	deref_irt();
    }
#endif /* PARALLEL */

    if (_p_current_proc != (proc_record_t *) NULL)
    {
	deref_current_proc();
    }
    
    /*
     * Dereference the gc reference stack.
     * In order to support the ability
     * to garbage collect at any time, some procedures will
     * need to have local variables garbage collected.
     * The gc refererence stack contains a list of pointers
     * to variables that need to be updated during a gc.
     * The PushGCReference(&v) and PopGCReference() should be
     * used to maintain the stack.
     */
    for (i = 0; i < _p_gc_ref_stack_top; i++)
	deref_pointer(_p_gc_ref_stack[i]);

} /* deref_everything() */


/*
 * deref_proc_record()
 *
 * Dereference the pointers originating from the arguments of
 * this process record.
 */
static void deref_proc_record(proc_record)
proc_record_t *proc_record;
{
    cell_t **arg = &(proc_record->args[0]);
    cell_t **last_arg = arg + proc_record->proc->arity;
    while (arg < last_arg)
    {
	deref_pointer(arg++);
    }
} /* deref_proc_record() */


/*
 * deref_process_queue()
 *
 * Dereference the pointers originating from the arguments of
 * the process records in this process queue.
 */
static void deref_process_queue(QF, QB)
proc_record_t *QF, *QB;
{
    proc_record_t *proc_record = QF;

    while (proc_record != (proc_record_t *) NULL)
    {
	deref_proc_record(proc_record);
	proc_record = proc_record->next;
    }
} /* deref_process_queue() */


/*
 * deref_suspension_queue()
 *
 * Dereference the pointers originating from the arguments of
 * the process records in this suspension queue (queue hung off
 * an undef or rref).
 *
 * Suspension queues are circular queues, where the last proc_record
 * in the queue points back to the first.  (This is done so that
 * in a uniprocessor run, a suspension queue can be appended to
 * the active queue with just a couple pointer manipulations -- no
 * need to traverse the whole queue.)
 */
static void deref_suspension_queue(queue_head)
proc_record_t *queue_head;
{
    proc_record_t *proc_record = queue_head;
    do
    {
	/* We do not need to do anything with value notes */
	if (IsProcRecord(proc_record))
	    deref_proc_record(proc_record);
	proc_record = proc_record->next;
    } while (proc_record != queue_head);
} /* deref_suspension_queue() */


/*
 * deref_irt()
 *
 * Dereference the pointers originating from the IRT.
 *
 * At the same time, reconstruct the IRT free list so that
 * the entries are ascending by index, to improve locality.
 */
static void deref_irt()
{
    irt_t *irt_entry, *irt_end;

    for (irt_entry = _p_irt, irt_end = _p_irt + _p_irt_size;
	 irt_entry < irt_end;
	 irt_entry++)
    {
	if (irt_entry->weight != 0)
	{
	    /* Used entry */
	    deref_pointer(&(irt_entry->u.ptr));
	}
    }
} /* deref_irt() */


/*
 * deref_current_proc()
 *
 * Dereference the pointers originating from the currently
 * scheduled process.  This includes:
 *	Argument registers (_p_a_reg[])
 *	_p_structure_start_ptr
 */
static void deref_current_proc()
{
    int_t i;

    /*
     * Dereference the argument registers.
     *
     * Normally, _p_first_unused_register is 256, which means we'll
     * gc all of the registers.  But in some instances
     * (i.e., save_arguments()) we know exactly how many registers
     * need to be gc'd.  By temporarily overriding this value in those
     * spots, we can control the gc better.
     */
    for (i = 0; i < _p_first_unused_register; i++)
    {
	if (_p_a_reg[i] != (cell_t) 0)
	    deref_pointer(&(_p_a_reg[i]));
    }
    
    /*
     * Dereference the _p_structure_start_ptr, if it points to
     * something on the heap.  Also, compute the offset of the
     * _p_structure_ptr from it.
     */
    if (OnOldHeap(_p_structure_start_ptr))
    {
	structure_ptr_offset = _p_structure_ptr - _p_structure_start_ptr;
	deref_pointer(&_p_structure_start_ptr);
    }

    /*
     * Dereference the _p_suspension_var if it points to something
     */
    if (   _p_suspension_var != (cell_t *) NULL
	&& _p_suspension_var != (cell_t *) -1 )
    {
	deref_pointer(&_p_suspension_var);
    }
} /* deref_current_proc() */


/*
 * deref_pointer()
 *
 * 'source' is the address of a pointer that we want to dereference.
 *
 * So dereference it, and then recursively
 * decend through the pointers of the the data structure
 * to derefercne them.  However, to avoid deep recursion on long lists,
 * the last tuple argument is dealt with specially by having a loop
 * around the body of this procedure -- so the tails of lists are
 * dealt with iteratively, rather than recursively (basic tail
 * recursion optimization).
 */
static void deref_pointer(source)
cell_t *source;
{
    cell_t *target, *t;
    u_int_t size;

    while (1)
    {
	/*
	 * Dereference the pointer, and store back the dereferenced
	 * pointer value into the source to remove any indirection.
	 * After this dereference, we are guaranteed to be pointing
	 * at a data header cell.
	 */
	Dereference((cell_t *), *((cell_t **) source), target);
	if (*((cell_t **) source) != target)
	    *((cell_t **) source) = target;

#ifdef DEBUG
	/*
	 * The target should point to the old heap!
	 */
	if (OnOldHeap(target))
	{
	    _p_fatal_error("deref_pointer(): Dereferenced to data structure on old heap during heap increase!");
	}
#endif /* DEBUG */

	if (IsMarked(target))
	{
	    /*
	     * This is a node that was marked during copy_scan().
	     * Therefore, we have not yet visited it.  So unmark it
	     * and traverse it.
	     */
	    ((data_header_t *)target)->mark = 0;
	    
	    if (IsTuple(target))
	    {
		if ((size = ((data_header_t *) target)->size) > 0)
		{
		    /*
		     * This is a non-empty tuple, so dereference its subterms
		     */
		    t = target + 1;
		    while(size > 1)
		    {
			/*
			 * If *t is a NULL pointer, then
			 * the gc occurred in the middle of filling a
			 * tuple (between build_static and last put_value),
			 * so there are NULL pointer arguments still.
			 */
			if (*((cell_t **) t) != (cell_t *) NULL)
			    deref_pointer(t, size);
			t++;
			size--;
		    }
		    if (*((cell_t **) t) != (cell_t *) NULL)
		    {
			source = t;	/* tail recursion optimization */
			continue;
		    }
		}
	    }
	    else if (IsUnknown(target) && SuspensionsAt(target))
	    {
		/*
		 * This is an unknown with suspensions, so recursively
		 * dereference the suspended processes.
		 */
		proc_record_t *suspension_queue = SuspendedProcs(target);
		deref_suspension_queue(suspension_queue);
	    }
	    /*
	     * else:  this is a data structure that does
	     *        not contain pointers.
	     */
	}
	/*
	 * else (!IsMarked(target))
	 *
	 * Either this data structure (target) has already been visited
	 * by the dereferencing routine, or it lives off the heap.  In
	 * either case, do not continue traversing the data structure.
	 */

	break;
    }
} /* deref_pointer() */

#endif /* !NO_VIRTUAL_MEMORY */

These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Marcel Waldvogel and Netfuture.ch.