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 Netfuture.ch.