1263 lines
29 KiB
C
1263 lines
29 KiB
C
static char sccsid[] = "@(#)22 1.1 src/bos/usr/ccs/lib/libpthreads/stackdb.c, libpth, bos411, 9428A410j 10/15/93 07:31:58";
|
|
/*
|
|
* COMPONENT_NAME: libpth
|
|
*
|
|
* FUNCTIONS:
|
|
* stackdb_fork_before
|
|
* stackdb_fork_after
|
|
* _pthread_stackdb_startup
|
|
* square_root
|
|
* increment_stack_count
|
|
* decrement_stack_count
|
|
* find_cluster
|
|
* cluster_check
|
|
* calculate_new_midpoint
|
|
* create_new_cluster
|
|
* destroy_cluster
|
|
* merge_cluster
|
|
* remove_cluster_tail
|
|
* add_stack_to_cluster
|
|
* remove_stack_from_cluster
|
|
* collapse_clusters
|
|
* calculate_root_limits
|
|
* check_for_cluster_size
|
|
* _add_stack
|
|
* _delete_stack
|
|
* stack_lookup
|
|
* _stack_self
|
|
* toggle_tracing
|
|
* dump_stack_stats
|
|
* dump_cluster
|
|
* dump_cluster_element
|
|
* dump_stack_element
|
|
*
|
|
* ORIGINS: 71 83
|
|
*
|
|
* LEVEL 1, 5 Years Bull Confidential Information
|
|
*
|
|
* (c) Copyright 1990, 1991, 1992, 1993 OPEN SOFTWARE FOUNDATION, INC.
|
|
* ALL RIGHTS RESERVED
|
|
*
|
|
* OSF/1 1.2
|
|
*/
|
|
|
|
/*
|
|
* File: stackdb.c
|
|
*
|
|
* This file contains the functions which manage the stack database used
|
|
* to look up thread identity.
|
|
*
|
|
* The stack database is a linked list of clusters each of which contains
|
|
* a linked list of stack descriptors. There are mid point pointers to both
|
|
* the centre of the cluster list and to the centre of each stack list of
|
|
* each cluster. This structure is always kept roughly square ie there are
|
|
* the same number of clusters as there are stacks per cluster. If either
|
|
* the number of clusters or the number of stacks in a cluster gets too big
|
|
* or too small then the structure is shrunk or grown to keep it about square.
|
|
* The search for a stack starts at the mid cluster and proceeds to one end.
|
|
* In this way only half the clusters are searched. Once the correct cluster
|
|
* is found the stack list is searched from the centre to one end and so only
|
|
* half of the stacks in that list is searched.
|
|
*/
|
|
#include "internal.h"
|
|
|
|
/*
|
|
* Local Definitions
|
|
*/
|
|
#define BACKWARDS 0
|
|
#define FORWARDS 1
|
|
#define INITIAL_BASE ~0
|
|
#define INITIAL_LIMIT 0
|
|
|
|
|
|
/*
|
|
* Local Macros
|
|
*/
|
|
#define elements_after_mid(cluster) \
|
|
(cluster->elements / 2 + (cluster->mid_move > 0 ? 1 : 0))
|
|
#define elements_before_mid(cluster) \
|
|
(cluster->elements / 2 + (cluster->mid_move < 0 ? 1 : 0))
|
|
|
|
/*
|
|
* Local types
|
|
*/
|
|
struct cluster {
|
|
pthread_queue link;
|
|
unsigned long base;
|
|
unsigned long limit;
|
|
int elements;
|
|
int mid_move;
|
|
stk_t mid_list;
|
|
pthread_queue stack_list;
|
|
};
|
|
|
|
typedef struct cluster cluster_t;
|
|
|
|
#ifdef STATISTICS
|
|
struct stack_stats {
|
|
long stack_creates;
|
|
long stack_destroys;
|
|
long cluster_creates;
|
|
long cluster_destroys;
|
|
long cluster_checks;
|
|
long cluster_splits;
|
|
long midpoint_moves;
|
|
long stack_adds;
|
|
long stack_removes;
|
|
long cluster_merges;
|
|
long collapses;
|
|
long cheap_collapses;
|
|
long medium_collapses;
|
|
long expensive_collapses;
|
|
long lookups;
|
|
long lookup_cluster;
|
|
long lookup_stack;
|
|
};
|
|
#endif
|
|
|
|
/*
|
|
* Local Data
|
|
*/
|
|
private cluster_t root_cluster;
|
|
private long number_of_stacks;
|
|
private long max_clusters;
|
|
private long stacks_per_cluster;
|
|
private spinlock_t stackdb_lock;
|
|
#ifdef DEBUG_PTH
|
|
private int stackdb_trace = 0;
|
|
#endif
|
|
|
|
#ifdef STATISTICS
|
|
private struct stack_stats stats;
|
|
#endif
|
|
|
|
|
|
#ifdef STATISTICS
|
|
/*
|
|
* Function:
|
|
* reset_stack_stats
|
|
*
|
|
* Description:
|
|
* Set the statistics to 0 when the process starts up.
|
|
*/
|
|
void
|
|
reset_stack_stats(void)
|
|
{
|
|
stats.stack_creates = 0;
|
|
stats.stack_destroys = 0;
|
|
stats.cluster_creates = 0;
|
|
stats.cluster_destroys = 0;
|
|
stats.cluster_checks = 0;
|
|
stats.cluster_splits = 0;
|
|
stats.midpoint_moves = 0;
|
|
stats.stack_adds = 0;
|
|
stats.stack_removes = 0;
|
|
stats.cluster_merges = 0;
|
|
stats.collapses = 0;
|
|
stats.cheap_collapses = 0;
|
|
stats.medium_collapses = 0;
|
|
stats.expensive_collapses = 0;
|
|
stats.lookups = 0;
|
|
stats.lookup_cluster = 0;
|
|
stats.lookup_stack = 0;
|
|
}
|
|
#endif
|
|
|
|
|
|
/*
|
|
* Function:
|
|
* stackdb_fork_before
|
|
*
|
|
* Description:
|
|
* Quiesce the stackdb subsystem prior to a fork.
|
|
*/
|
|
private void
|
|
stackdb_fork_before(void)
|
|
{
|
|
_spin_lock(&stackdb_lock);
|
|
}
|
|
|
|
|
|
/*
|
|
* Function:
|
|
* stackdb_fork_after
|
|
*
|
|
* Description:
|
|
* Release stackdb following a fork.
|
|
*/
|
|
private void
|
|
stackdb_fork_after(void)
|
|
{
|
|
_spin_unlock(&stackdb_lock);
|
|
}
|
|
|
|
|
|
/*
|
|
* Function:
|
|
* _pthread_stackdb_startup
|
|
*
|
|
* Description:
|
|
* Initialize the stack database. Clear the root cluster and reset the
|
|
* stats structure.
|
|
* Register the fork handlers.
|
|
* This function is called from pthread_init().
|
|
*/
|
|
void
|
|
_pthread_stackdb_startup(void)
|
|
{
|
|
_spinlock_create(&stackdb_lock);
|
|
queue_init(&root_cluster.link);
|
|
root_cluster.base = INITIAL_BASE;
|
|
root_cluster.limit = INITIAL_LIMIT;
|
|
root_cluster.elements = 0;
|
|
queue_init(&root_cluster.stack_list);
|
|
root_cluster.mid_list = (stk_t)&root_cluster;
|
|
root_cluster.mid_move = 0;
|
|
number_of_stacks = 0;
|
|
#ifdef STATISTICS
|
|
reset_stack_stats();
|
|
#endif
|
|
|
|
if (pthread_atfork(stackdb_fork_before,
|
|
stackdb_fork_after,
|
|
stackdb_fork_after))
|
|
INTERNAL_ERROR("_pthread_stackdb_startup");
|
|
}
|
|
|
|
|
|
/*
|
|
* Function:
|
|
* square_root
|
|
*
|
|
* Parameters:
|
|
* val - the integer value you wish to take the root of
|
|
*
|
|
* Return value:
|
|
* The square root of val
|
|
*
|
|
* Description:
|
|
* Use a Maclaurin series factorization to work out the square root.
|
|
* The larger the value the more iterations needed to get the appropriate
|
|
* accuracy. This is here to remove a dependency on libm.
|
|
*/
|
|
private double
|
|
square_root(int val)
|
|
{
|
|
double an, an1, bn, root;
|
|
int i, loop;
|
|
|
|
/* Calculate the square root of an integral value using
|
|
* an infinite product expansion.
|
|
*/
|
|
|
|
/* Calculate the number of product iterations needed for this
|
|
* number. This produces values that are accurate to at least
|
|
* 10 decimal places.
|
|
*/
|
|
loop = 6;
|
|
for (i = val; i > 10; i /= 10)
|
|
loop += 2;
|
|
|
|
/* The algorithm works by factoring out the Maclaurin series.
|
|
* To calculate sqrt(1 + x) we let
|
|
* a[0] = x;
|
|
* a[n+1] = (a[n] * a[n]) / (4 * a[n] + 4)
|
|
* b[n] = (2 * a[n] + 2) / (a[n] + 2)
|
|
*
|
|
* and sqrt(1 + x) = b[0] * b[1] * b[2] * ... b[n]
|
|
* where the value of n is determined by the level of accuracy
|
|
* required and the value of x.
|
|
*/
|
|
root = 1;
|
|
an1 = (double)(val - 1);
|
|
for (i = 0; i < loop; i++) {
|
|
an = an1;
|
|
bn = (2 * an + 2)/(an + 2);
|
|
root = root * bn;
|
|
an1 = (an * an)/(4 * an + 4);
|
|
}
|
|
return (root);
|
|
}
|
|
|
|
|
|
/*
|
|
* Function:
|
|
* increment_stack_count
|
|
*
|
|
* Description:
|
|
* Increment the number of stacks in the database and calculate the
|
|
* new maximum number of clusters we need and the maximum number of
|
|
* stacks allowed in each cluster.
|
|
*/
|
|
private void
|
|
increment_stack_count(void)
|
|
{
|
|
number_of_stacks++;
|
|
max_clusters = 2 * (int)(square_root((number_of_stacks + 1)/2) + 0.5);
|
|
|
|
stacks_per_cluster = (number_of_stacks + (max_clusters - 1)) /
|
|
max_clusters;
|
|
}
|
|
|
|
|
|
/*
|
|
* Function:
|
|
* decrement_stack_count
|
|
*
|
|
* Description:
|
|
* Decrement the number of stacks in the database and calculate the
|
|
* new maximum number of clusters we need and the maximum number of
|
|
* stacks allowed in each cluster.
|
|
*/
|
|
private void
|
|
decrement_stack_count(void)
|
|
{
|
|
number_of_stacks--;
|
|
max_clusters = 2 * (int)(square_root((number_of_stacks + 1)/2) + 0.5);
|
|
|
|
stacks_per_cluster = (number_of_stacks + (max_clusters - 1)) /
|
|
max_clusters;
|
|
}
|
|
|
|
|
|
/*
|
|
* Function:
|
|
* find_cluster
|
|
*
|
|
* Parameters:
|
|
* stack - pointer to a stack structure containing the stack dimensions
|
|
*
|
|
* Return value:
|
|
* A pointer to a cluster to insert the stack into if one exists
|
|
* a pointer to the root cluster otherwise
|
|
*
|
|
* Description:
|
|
* Try to find a cluster in which this stack should be
|
|
* inserted into. Start the search at the mid point of the
|
|
* cluster list and search to the end or the beginning depending
|
|
* on the value of the stack. If the cluster list is empty, the root
|
|
* cluster is returned.
|
|
*/
|
|
private cluster_t *
|
|
find_cluster(stk_t stack)
|
|
{
|
|
cluster_t *mid;
|
|
cluster_t *end;
|
|
cluster_t *cluster;
|
|
cluster_t *next;
|
|
int search;
|
|
|
|
#ifdef DEBUG_PTH
|
|
if (stackdb_trace)
|
|
dbgPrintf("find_cluster(stack = %x)\n", stack);
|
|
#endif
|
|
|
|
/* Get the mid point in the root cluster and determine which way
|
|
* we have to search. If we strike it lucky that the stack should
|
|
* be in the mid cluster then return that.
|
|
*/
|
|
mid = (cluster_t *)root_cluster.mid_list;
|
|
|
|
if (mid->base > stack->limit) {
|
|
search = BACKWARDS;
|
|
cluster = (cluster_t *)queue_prev(&mid->link);
|
|
} else if (mid->limit < stack->base) {
|
|
search = FORWARDS;
|
|
cluster = mid;
|
|
} else
|
|
return (mid);
|
|
|
|
/* It doesn't matter which way we search, the end is always at
|
|
* root.
|
|
*/
|
|
end = (cluster_t *)queue_end(&root_cluster.link);
|
|
|
|
while (cluster != end) {
|
|
|
|
/* If this cluster spans our stack then we are done.
|
|
*/
|
|
if ((cluster->base <= stack->base) &&
|
|
(cluster->limit >= stack->limit))
|
|
return (cluster);
|
|
|
|
/* If this stack falls between this cluster and the following
|
|
* cluster then return this cluster.
|
|
*/
|
|
next = (cluster_t *)queue_next(&cluster->link);
|
|
if ((cluster->limit < stack->base) &&
|
|
((next->base > stack->limit) || (next == end)))
|
|
return (cluster);
|
|
|
|
/* Get the next cluster to search
|
|
*/
|
|
if (search == BACKWARDS)
|
|
cluster = (cluster_t *)queue_prev(&cluster->link);
|
|
else
|
|
cluster = (cluster_t *)queue_next(&cluster->link);
|
|
}
|
|
|
|
/* There are no clusters in the list, return the root cluster.
|
|
*/
|
|
return (&root_cluster);
|
|
}
|
|
|
|
|
|
#ifdef DEBUG_PTH
|
|
/*
|
|
* Function:
|
|
* cluster_check
|
|
*
|
|
* Parameters:
|
|
* cluster - pointer to the cluster to check.
|
|
*
|
|
* Description:
|
|
* perform a consistency check on the cluster. Check that the number
|
|
* of elements the cluster claims to have are actually there.
|
|
*/
|
|
private void
|
|
cluster_check(cluster_t *cluster)
|
|
{
|
|
cluster_t *c;
|
|
int n;
|
|
|
|
if (cluster == &root_cluster)
|
|
return;
|
|
|
|
for (c = (cluster_t *)queue_head(&cluster->stack_list), n = 0;
|
|
c != (cluster_t *)queue_end(&cluster->stack_list);
|
|
c = (cluster_t *)queue_next(&c->link))
|
|
n++;
|
|
|
|
if (n != cluster->elements) {
|
|
dbgPrintf("counted %d elements, expected %d\n",
|
|
n, cluster->elements);
|
|
INTERNAL_ERROR("cluster_check");
|
|
}
|
|
}
|
|
#endif
|
|
|
|
|
|
/*
|
|
* Function:
|
|
* calculate_new_midpoint
|
|
*
|
|
* Parameters:
|
|
* cluster - the cluster to be checked
|
|
*
|
|
* Description:
|
|
* Move the pointer to the middle of the stack list to a new
|
|
* position after stacks have been removed/added to this cluster.
|
|
* For every multiple of 2 of the mid_move value, the mid pointer
|
|
* should be advanced/retarded depending on the sign.
|
|
*/
|
|
private void
|
|
calculate_new_midpoint(cluster_t *cluster)
|
|
{
|
|
#ifdef DEBUG_PTH
|
|
if (stackdb_trace)
|
|
dbgPrintf("calculate_new_midpoint(cluster = %x)\n", cluster);
|
|
|
|
cluster_check(cluster); /* Paranoia */
|
|
#endif
|
|
|
|
for (;;) {
|
|
if (cluster->mid_move > 1) {
|
|
|
|
/* Move the mid pointer forward
|
|
*/
|
|
cluster->mid_list = (stk_t)
|
|
queue_next(&cluster->mid_list->link);
|
|
cluster->mid_move -= 2;
|
|
|
|
} else if (cluster->mid_move < -1) {
|
|
|
|
/* Move the mid pointer backwards
|
|
*/
|
|
cluster->mid_list = (stk_t)
|
|
queue_prev(&cluster->mid_list->link);
|
|
cluster->mid_move += 2;
|
|
|
|
} else {
|
|
|
|
/* We have done all the moving we need to do
|
|
*/
|
|
break;
|
|
}
|
|
#ifdef STATISTICS
|
|
stats.midpoint_moves++;
|
|
#endif
|
|
}
|
|
|
|
/* Check the cluster still makes sense
|
|
*/
|
|
if ((cluster->mid_list == (stk_t)cluster) &&
|
|
(cluster->elements != 0))
|
|
INTERNAL_ERROR("calculate_new_midpoint");
|
|
}
|
|
|
|
|
|
/*
|
|
* Function:
|
|
* create_new_cluster
|
|
*
|
|
* Parameters:
|
|
* prev - the cluster in the chain to insert the new cluster after
|
|
*
|
|
* Return value:
|
|
* A pointer to the new cluster if created
|
|
* NULL if no memory for the cluster is available.
|
|
*
|
|
* Description:
|
|
* Create and initialize a new cluster and add it into the cluster
|
|
* list. If the list already contained clusters then calculate a new
|
|
* midpoint which may be necessary.
|
|
*/
|
|
private cluster_t *
|
|
create_new_cluster(cluster_t *prev)
|
|
{
|
|
cluster_t *cluster;
|
|
|
|
#ifdef DEBUG_PTH
|
|
if (stackdb_trace)
|
|
dbgPrintf("create_new_cluster(prev = %x)\n", prev);
|
|
#endif
|
|
|
|
#ifdef STATISTICS
|
|
stats.cluster_creates++;
|
|
#endif
|
|
|
|
/* Allocate memory for the new cluster.
|
|
*/
|
|
cluster = (cluster_t *)malloc(sizeof(cluster_t));
|
|
if (cluster == NULL)
|
|
return (NULL);
|
|
|
|
/* Initialize the new cluster and insert it into the cluster list.
|
|
*/
|
|
cluster->base = 0;
|
|
cluster->limit = 0;
|
|
cluster->elements = 0;
|
|
queue_init(&cluster->stack_list);
|
|
cluster->mid_list = (stk_t)cluster;
|
|
cluster->mid_move = 0;
|
|
queue_insert(&prev->link, &cluster->link);
|
|
|
|
/* Check is this is the first cluster in the list, if so then
|
|
* set up the root cluster.
|
|
*/
|
|
if (root_cluster.elements == 0) {
|
|
root_cluster.mid_move = 1;
|
|
root_cluster.mid_list = (stk_t)cluster;
|
|
root_cluster.elements++;
|
|
|
|
} else {
|
|
|
|
/* This is not the first cluster. Calculate the new mid_move
|
|
* value and check to see if we need a new mid point.
|
|
*/
|
|
if ((prev->limit < root_cluster.mid_list->base) ||
|
|
(prev == &root_cluster)) {
|
|
/* we are adding before the mid point */
|
|
root_cluster.mid_move--;
|
|
} else {
|
|
/* we are adding after the mid point */
|
|
root_cluster.mid_move++;
|
|
}
|
|
root_cluster.elements++;
|
|
calculate_new_midpoint(&root_cluster);
|
|
}
|
|
return (cluster);
|
|
}
|
|
|
|
|
|
/*
|
|
* Function:
|
|
* destroy_cluster
|
|
*
|
|
* Parameters:
|
|
* cluster - remove an empty cluster from the cluster list
|
|
*
|
|
* Description:
|
|
* Remove a cluster from the cluster list. If the cluster is the mid point
|
|
* then we move the mid point before removal. Having removed the cluster
|
|
* we check to see if the mid point should be moved.
|
|
*/
|
|
private void
|
|
destroy_cluster(cluster_t * cluster)
|
|
{
|
|
#ifdef DEBUG_PTH
|
|
if (stackdb_trace)
|
|
dbgPrintf("destroy_cluster(cluster = %x)\n", cluster);
|
|
#endif
|
|
|
|
#ifdef STATISTICS
|
|
stats.cluster_destroys++;
|
|
#endif
|
|
|
|
/* Don't allow non empty clusters to be removed.
|
|
*/
|
|
if (cluster->elements != 0)
|
|
INTERNAL_ERROR("destroy_cluster");
|
|
|
|
/* If we are trying to remove the mid point then we move the mid
|
|
* point forwards or backwards depending on the current value of
|
|
* mid_move. The idea is to move the mid point in the direction that
|
|
* would be correct after the cluster has been removed.
|
|
*/
|
|
if (cluster == (cluster_t *)root_cluster.mid_list) {
|
|
if (root_cluster.mid_move <= 0) {
|
|
root_cluster.mid_list = (stk_t)
|
|
queue_prev(&root_cluster.mid_list->link);
|
|
root_cluster.mid_move += 2;
|
|
} else {
|
|
root_cluster.mid_list = (stk_t)
|
|
queue_next(&root_cluster.mid_list->link);
|
|
root_cluster.mid_move -= 2;
|
|
}
|
|
}
|
|
|
|
/* Check to see if we are removing before or after the mid point and
|
|
* adjust mid_move accordingly. We know that we are not removing the
|
|
* mid point so it has to be one or the other.
|
|
*/
|
|
if (cluster->limit < root_cluster.mid_list->base) {
|
|
/* we are destroying before the mid point */
|
|
root_cluster.mid_move++;
|
|
} else {
|
|
/* we are destroying after the mid point */
|
|
root_cluster.mid_move--;
|
|
}
|
|
|
|
/* Actually remove the cluster and update the root cluster.
|
|
*/
|
|
queue_remove(&cluster->link);
|
|
free(cluster);
|
|
root_cluster.elements--;
|
|
calculate_new_midpoint(&root_cluster);
|
|
}
|
|
|
|
|
|
/*
|
|
* Function:
|
|
* merge_clusters
|
|
*
|
|
* Parameters:
|
|
* target - the cluster to get all the stacks
|
|
* source - the cluster to lose all the stacks
|
|
*
|
|
* Description:
|
|
* move all the stacks from the source cluster onto the target cluster
|
|
* keeping the target mid point valid. This is normally done when there
|
|
* are too many clusters (the number of stacks has been reduced) and we
|
|
* need to delete some clusters.
|
|
*/
|
|
private void
|
|
merge_clusters(cluster_t *target, cluster_t *source)
|
|
{
|
|
#ifdef DEBUG_PTH
|
|
if (stackdb_trace)
|
|
dbgPrintf("merge_clusters(target = %x, source = %x)\n",
|
|
target, source);
|
|
#endif
|
|
|
|
#ifdef STATISTICS
|
|
stats.cluster_merges++;
|
|
#endif
|
|
|
|
/* Find out whether the source stacks have to be added on the
|
|
* head or the tail of the target stack list.
|
|
*/
|
|
if (source->base > target->limit) {
|
|
|
|
/* Add source to end of target.
|
|
*/
|
|
queue_merge(&target->stack_list, &source->stack_list);
|
|
target->mid_move += source->elements;
|
|
target->limit = source->limit;
|
|
|
|
/* We can merge onto an empty cluster so check for this.
|
|
*/
|
|
if (target->elements == 0)
|
|
target->base = source->base;
|
|
|
|
} else {
|
|
|
|
/* Add source to front of target.
|
|
*/
|
|
queue_merge(&source->stack_list, &target->stack_list);
|
|
queue_move(&target->stack_list, &source->stack_list);
|
|
target->mid_move -= source->elements;
|
|
target->base = source->base;
|
|
|
|
/* We can merge onto an empty cluster so check for this.
|
|
*/
|
|
if (target->elements == 0)
|
|
target->limit = source->limit;
|
|
}
|
|
|
|
/* If the merge was onto an empty cluster then the mid list does
|
|
* not point at anything sensible so we have to set it up.
|
|
*/
|
|
if (target->elements == 0)
|
|
target->mid_list = (stk_t)queue_head(&target->stack_list);
|
|
target->elements += source->elements;
|
|
source->elements = 0;
|
|
|
|
/* Finally move the mid point down the list to take into account of
|
|
* the new stacks.
|
|
*/
|
|
calculate_new_midpoint(target);
|
|
}
|
|
|
|
|
|
/*
|
|
* Function:
|
|
* remove_cluster_tail
|
|
*
|
|
* Parameters:
|
|
* cluster - the cluster to lose the end half of the stack list
|
|
* tail - the empty cluster to get the stacks
|
|
*
|
|
* Description:
|
|
* Remove all the stacks from the mid point to the end of the list
|
|
* from cluster and add it onto tail. Keep the mid point information
|
|
* valid for the cluster but we don't bother with the tail as this is
|
|
* normally a temporary cluster that will be merged with another cluster
|
|
* immediately.
|
|
*/
|
|
private void
|
|
remove_cluster_tail(cluster_t *cluster, cluster_t *tail)
|
|
{
|
|
stk_t mid_prev = NULL;
|
|
|
|
#ifdef DEBUG_PTH
|
|
if (stackdb_trace)
|
|
dbgPrintf("remove_cluster_tail(cluster = %x, tail = %x)\n",
|
|
cluster, tail);
|
|
#endif
|
|
|
|
/* Calculate the number of stacks being moved and adjust the mid point
|
|
* information.
|
|
*/
|
|
tail->elements = elements_after_mid(cluster);
|
|
cluster->elements = elements_before_mid(cluster);
|
|
cluster->mid_move = 2 - cluster->elements;
|
|
|
|
/* Save the cluster limit information for both clusters.
|
|
*/
|
|
tail->base = cluster->mid_list->base;
|
|
tail->limit = cluster->limit;
|
|
if (cluster->elements != 0) {
|
|
mid_prev = (stk_t)queue_prev(&cluster->mid_list->link);
|
|
cluster->limit = mid_prev->limit;
|
|
}
|
|
|
|
/* Copy the stacks over in one go.
|
|
*/
|
|
queue_split(&cluster->stack_list, &tail->stack_list,
|
|
&cluster->mid_list->link);
|
|
|
|
/* Adjust the mid list pointer
|
|
*/
|
|
if (cluster->elements != 0) {
|
|
cluster->mid_list = mid_prev;
|
|
calculate_new_midpoint(cluster);
|
|
}
|
|
}
|
|
|
|
|
|
/*
|
|
* Function:
|
|
* add_stack_to_cluster
|
|
*
|
|
* Parameters:
|
|
* cluster - the target cluster to get the stack
|
|
* new_stack - the stack being added
|
|
*
|
|
* Description:
|
|
* Add a stack to a cluster which may be empty. The cluster limit
|
|
* information and mid point information have to be kept updated.
|
|
*/
|
|
private void
|
|
add_stack_to_cluster(cluster_t *cluster, stk_t new_stack)
|
|
{
|
|
stk_t stack;
|
|
stk_t next;
|
|
stk_t end;
|
|
int search;
|
|
cluster_t *new_cluster;
|
|
cluster_t cluster_tail;
|
|
|
|
#ifdef DEBUG_PTH
|
|
if (stackdb_trace)
|
|
dbgPrintf("add_stack_to_cluster(cluster = %x, stack(%x, %x) = %x)\n",
|
|
cluster, new_stack->base, new_stack->limit, new_stack);
|
|
|
|
if (new_stack->limit == 0)
|
|
INTERNAL_ERROR("add_stack_to_cluster");
|
|
#endif
|
|
|
|
#ifdef STATISTICS
|
|
stats.stack_adds++;
|
|
#endif
|
|
|
|
if (cluster->elements == 0) {
|
|
|
|
/* This is the first stack in the cluster.
|
|
*/
|
|
queue_append(&cluster->stack_list, &new_stack->link);
|
|
cluster->base = new_stack->base;
|
|
cluster->limit = new_stack->limit;
|
|
cluster->mid_move = 1;
|
|
cluster->mid_list = new_stack;
|
|
cluster->elements++;
|
|
|
|
} else {
|
|
|
|
/* Add the stack into the correct point in the cluster.
|
|
* start the search for the insertion point at the middle
|
|
* and go to one end.
|
|
*/
|
|
stack = cluster->mid_list;
|
|
if (stack->base > new_stack->limit)
|
|
search = BACKWARDS;
|
|
else if (stack->limit < new_stack->base)
|
|
search = FORWARDS;
|
|
else /* overlapping stacks */
|
|
INTERNAL_ERROR("add_stack_to_cluster");
|
|
end = (stk_t)queue_end(&cluster->stack_list);
|
|
while (stack != end) {
|
|
next = (stk_t)queue_next(&stack->link);
|
|
|
|
/* Check to see if the stack falls inbetween this one
|
|
* and the next. If so break out of the loop.
|
|
*/
|
|
if ((new_stack->base > stack->limit) &&
|
|
((new_stack->limit < next->base) || (next == end)))
|
|
break;
|
|
if (search == BACKWARDS)
|
|
stack = (stk_t)queue_prev(&stack->link);
|
|
else
|
|
stack = next;
|
|
}
|
|
|
|
/* Insert in the correct position and adjust the cluster
|
|
* limit information.
|
|
*/
|
|
queue_insert(&stack->link, &new_stack->link);
|
|
if (cluster->base > new_stack->base)
|
|
cluster->base = new_stack->base;
|
|
if (cluster->limit < new_stack->limit)
|
|
cluster->limit = new_stack->limit;
|
|
|
|
/* Adjust the mid point information and move the mid list
|
|
* pointer if necessary.
|
|
*/
|
|
cluster->mid_move += (search == BACKWARDS ? -1 : 1);
|
|
cluster->elements++;
|
|
calculate_new_midpoint(cluster);
|
|
}
|
|
|
|
/* If we have just exceeded the number of stacks per cluster allowed
|
|
* the create a new cluster and split the stack list between them.
|
|
*/
|
|
if (cluster->elements > stacks_per_cluster) {
|
|
new_cluster = create_new_cluster(cluster);
|
|
remove_cluster_tail(cluster, &cluster_tail);
|
|
merge_clusters(new_cluster, &cluster_tail);
|
|
}
|
|
}
|
|
|
|
|
|
private void
|
|
remove_stack_from_cluster(cluster_t *cluster, stk_t stack)
|
|
{
|
|
stk_t stack_tmp;
|
|
|
|
#ifdef DEBUG_PTH
|
|
if (stackdb_trace)
|
|
dbgPrintf("remove_stack_from_cluster(cluster(%d) = %x, stack(%x, %x) = %x)\n",
|
|
cluster->elements, cluster, stack->base, stack->limit, stack);
|
|
#endif
|
|
|
|
#ifdef STATISTICS
|
|
stats.stack_removes++;
|
|
#endif
|
|
|
|
if (stack == cluster->mid_list) {
|
|
if (cluster->mid_move <= 0) {
|
|
cluster->mid_list = (stk_t)
|
|
queue_prev(&cluster->mid_list->link);
|
|
cluster->mid_move += 2;
|
|
} else {
|
|
cluster->mid_list = (stk_t)
|
|
queue_next(&cluster->mid_list->link);
|
|
cluster->mid_move -= 2;
|
|
}
|
|
}
|
|
if (stack->limit < cluster->mid_list->base) {
|
|
/* we are removing before the mid point */
|
|
cluster->mid_move++;
|
|
} else {
|
|
/* we are removing after the mid point */
|
|
cluster->mid_move--;
|
|
}
|
|
queue_remove(&stack->link);
|
|
cluster->elements--;
|
|
if (cluster->elements != 0) {
|
|
stack_tmp = (stk_t)queue_head(&cluster->stack_list);
|
|
cluster->base = stack_tmp->base;
|
|
stack_tmp = (stk_t)queue_tail(&cluster->stack_list);
|
|
cluster->limit = stack_tmp->limit;
|
|
calculate_new_midpoint(cluster);
|
|
}
|
|
}
|
|
|
|
|
|
private void
|
|
collapse_clusters(void)
|
|
{
|
|
cluster_t *cluster;
|
|
cluster_t *prev;
|
|
cluster_t *next;
|
|
cluster_t cluster_tail;
|
|
stk_t stack;
|
|
int prev_can_take_half = FALSE;
|
|
|
|
#ifdef DEBUG_PTH
|
|
if (stackdb_trace)
|
|
dbgPrintf("collapse_clusters()\n");
|
|
#endif
|
|
|
|
#ifdef STATISTICS
|
|
stats.collapses++;
|
|
#endif
|
|
|
|
cluster = (cluster_t *)queue_head(&root_cluster.link);
|
|
|
|
while (root_cluster.elements > max_clusters) {
|
|
next = (cluster_t *)queue_next(&cluster->link);
|
|
if (next == (cluster_t *)queue_end(&root_cluster.link))
|
|
break;
|
|
|
|
if ((cluster->elements + next->elements) <= stacks_per_cluster) {
|
|
merge_clusters(cluster, next);
|
|
destroy_cluster(next);
|
|
#ifdef STATISTICS
|
|
stats.cheap_collapses++;
|
|
#endif
|
|
continue;
|
|
}
|
|
|
|
if (prev_can_take_half &&
|
|
((next->elements + elements_after_mid(cluster))
|
|
<= stacks_per_cluster)) {
|
|
remove_cluster_tail(cluster, &cluster_tail);
|
|
prev = (cluster_t *)queue_prev(&cluster->link);
|
|
merge_clusters(prev, cluster);
|
|
destroy_cluster(cluster);
|
|
merge_clusters(next, &cluster_tail);
|
|
#ifdef STATISTICS
|
|
stats.medium_collapses++;
|
|
#endif
|
|
}
|
|
|
|
if ((cluster->elements + elements_before_mid(next))
|
|
<= stacks_per_cluster)
|
|
prev_can_take_half = TRUE;
|
|
else
|
|
prev_can_take_half = FALSE;
|
|
|
|
cluster = next;
|
|
}
|
|
|
|
if (root_cluster.elements <= max_clusters)
|
|
return;
|
|
|
|
/* There is no quick way to collapse the clusters.
|
|
*/
|
|
#ifdef STATISTICS
|
|
stats.expensive_collapses++;
|
|
#endif
|
|
cluster = (cluster_t *)queue_head(&root_cluster.link);
|
|
while (root_cluster.elements > max_clusters) {
|
|
next = (cluster_t *)queue_next(&cluster->link);
|
|
while (cluster->elements < stacks_per_cluster) {
|
|
stack = (stk_t)queue_head(&next->stack_list);
|
|
remove_stack_from_cluster(next, stack);
|
|
add_stack_to_cluster(cluster, stack);
|
|
if (next->elements == 0) {
|
|
destroy_cluster(next);
|
|
if (root_cluster.elements <= max_clusters)
|
|
return;
|
|
next = (cluster_t *)
|
|
queue_next(&cluster->link);
|
|
}
|
|
}
|
|
cluster = (cluster_t *)queue_next(&cluster->link);
|
|
}
|
|
}
|
|
|
|
|
|
private void
|
|
calculate_root_limits(void)
|
|
{
|
|
cluster_t *cluster;
|
|
|
|
if (root_cluster.elements == 0) {
|
|
root_cluster.base = INITIAL_BASE;
|
|
root_cluster.limit = INITIAL_LIMIT;
|
|
} else {
|
|
cluster = (cluster_t *)queue_head(&root_cluster.link);
|
|
root_cluster.base = cluster->base;
|
|
cluster = (cluster_t *)queue_tail(&root_cluster.link);
|
|
root_cluster.limit = cluster->limit;
|
|
}
|
|
}
|
|
|
|
|
|
private void
|
|
check_for_cluster_size(void)
|
|
{
|
|
cluster_t *cluster;
|
|
cluster_t *new_cluster;
|
|
cluster_t cluster_tail;
|
|
|
|
#ifdef DEBUG_PTH
|
|
if (stackdb_trace)
|
|
dbgPrintf("check_for_cluster_size()\n");
|
|
#endif
|
|
|
|
#ifdef STATISTICS
|
|
stats.cluster_checks++;
|
|
#endif
|
|
for (cluster = (cluster_t *)queue_head(&root_cluster.link);
|
|
cluster != (cluster_t *)queue_end(&root_cluster.link);
|
|
cluster = (cluster_t *)queue_next(&cluster->link)) {
|
|
if (cluster->elements > stacks_per_cluster) {
|
|
new_cluster = create_new_cluster(cluster);
|
|
remove_cluster_tail(cluster, &cluster_tail);
|
|
merge_clusters(new_cluster, &cluster_tail);
|
|
cluster = new_cluster;
|
|
#ifdef STATISTICS
|
|
stats.cluster_splits++;
|
|
#endif
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
void
|
|
_add_stack(stk_t new_stack)
|
|
{
|
|
cluster_t *cluster;
|
|
|
|
#ifdef STATISTICS
|
|
stats.stack_creates++;
|
|
#endif
|
|
|
|
_spin_lock(&stackdb_lock);
|
|
increment_stack_count();
|
|
cluster = find_cluster(new_stack);
|
|
if (cluster == &root_cluster)
|
|
cluster = create_new_cluster(cluster);
|
|
add_stack_to_cluster(cluster, new_stack);
|
|
calculate_root_limits();
|
|
if (root_cluster.elements > max_clusters)
|
|
collapse_clusters();
|
|
_spin_unlock(&stackdb_lock);
|
|
}
|
|
|
|
|
|
void
|
|
_delete_stack(stk_t stack)
|
|
{
|
|
cluster_t *cluster;
|
|
long old_stacks_per_cluster;
|
|
|
|
#ifdef STATISTICS
|
|
stats.stack_destroys++;
|
|
#endif
|
|
|
|
_spin_lock(&stackdb_lock);
|
|
old_stacks_per_cluster = stacks_per_cluster;
|
|
decrement_stack_count();
|
|
cluster = find_cluster(stack);
|
|
remove_stack_from_cluster(cluster, stack);
|
|
if (cluster->elements == 0)
|
|
destroy_cluster(cluster);
|
|
calculate_root_limits();
|
|
if (stacks_per_cluster < old_stacks_per_cluster)
|
|
check_for_cluster_size();
|
|
if (root_cluster.elements > max_clusters)
|
|
collapse_clusters();
|
|
_spin_unlock(&stackdb_lock);
|
|
}
|
|
|
|
|
|
private stk_t
|
|
stack_lookup(long sp)
|
|
{
|
|
cluster_t *cluster;
|
|
stk_t stack;
|
|
int search;
|
|
|
|
#ifdef STATISTICS
|
|
stats.lookups++;
|
|
#endif
|
|
|
|
_spin_lock(&stackdb_lock);
|
|
|
|
if ((sp < root_cluster.base) || (sp > root_cluster.limit)) {
|
|
_spin_unlock(&stackdb_lock);
|
|
return (NULL);
|
|
}
|
|
|
|
cluster = (cluster_t *)root_cluster.mid_list;
|
|
if (sp < cluster->base)
|
|
search = BACKWARDS;
|
|
else
|
|
search = FORWARDS;
|
|
|
|
for (;;) {
|
|
#ifdef STATISTICS
|
|
stats.lookup_cluster++;
|
|
#endif
|
|
if ((sp >= cluster->base) && (sp <= cluster->limit))
|
|
break;
|
|
if (search == BACKWARDS)
|
|
cluster = (cluster_t *)queue_prev(&cluster->link);
|
|
else
|
|
cluster = (cluster_t *)queue_next(&cluster->link);
|
|
if (cluster == (cluster_t *)queue_end(&root_cluster.link)) {
|
|
_spin_unlock(&stackdb_lock);
|
|
return (NULL);
|
|
}
|
|
}
|
|
|
|
stack = cluster->mid_list;
|
|
if (sp < stack->base)
|
|
search = BACKWARDS;
|
|
else
|
|
search = FORWARDS;
|
|
for (;;) {
|
|
#ifdef STATISTICS
|
|
stats.lookup_stack++;
|
|
#endif
|
|
if ((sp >= stack->base) && (sp <= stack->limit)) {
|
|
_spin_unlock(&stackdb_lock);
|
|
return (stack);
|
|
}
|
|
if (search == BACKWARDS)
|
|
stack = (stk_t)queue_prev(&stack->link);
|
|
else
|
|
stack = (stk_t)queue_next(&stack->link);
|
|
|
|
if (stack == (stk_t)queue_end(&cluster->stack_list)) {
|
|
_spin_unlock(&stackdb_lock);
|
|
return (NULL);
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
stk_t
|
|
_stack_self(void)
|
|
{
|
|
caddr_t sp;
|
|
stk_t self;
|
|
|
|
sp = (caddr_t)_get_stack_pointer();
|
|
self = stack_lookup((long)sp);
|
|
if (self == NULL) {
|
|
#ifdef DEBUG_PTH
|
|
if (stackdb_trace)
|
|
dump_cluster();
|
|
#endif
|
|
INTERNAL_ERROR("_stack_self");
|
|
}
|
|
return (self);
|
|
}
|
|
|
|
|
|
#ifdef DEBUG_PTH
|
|
|
|
void
|
|
toggle_tracing(void)
|
|
{
|
|
stackdb_trace = !stackdb_trace;
|
|
}
|
|
|
|
|
|
#ifdef STATISTICS
|
|
dump_stack_stats(void)
|
|
{
|
|
dbgPrintf("Stack: Creates %d, Destroys %d\n",
|
|
stats.stack_creates, stats.stack_destroys);
|
|
dbgPrintf("Cluster: Creates %d, Destroys %d, Mid moves %d\n",
|
|
stats.cluster_creates, stats.cluster_destroys,
|
|
stats.midpoint_moves);
|
|
dbgPrintf("Stack/Cluster: Adds %d, Removes %d, Merges %d\n",
|
|
stats.stack_adds, stats.stack_removes, stats.cluster_merges);
|
|
dbgPrintf("Collapses: Total %d, Cheap %d, Medium %d, Expensive %d\n",
|
|
stats.collapses, stats.cheap_collapses, stats.medium_collapses,
|
|
stats.expensive_collapses);
|
|
dbgPrintf("Cluster: checks %d, splits %d\n",
|
|
stats.cluster_checks, stats.cluster_splits);
|
|
dbgPrintf("Lookups %d, cluster cost %5.2f, Stack cost %5.2f,"
|
|
" ave cost %5.2f\n",
|
|
stats.lookups,
|
|
(double)stats.lookup_cluster / (double)stats.lookups,
|
|
(double)stats.lookup_stack / (double)stats.lookups,
|
|
(double)(stats.lookup_cluster + stats.lookup_stack)
|
|
/ (double)stats.lookups);
|
|
}
|
|
#endif
|
|
|
|
|
|
dump_cluster(void)
|
|
{
|
|
cluster_t *cluster;
|
|
|
|
dbgPrintf("Stacks: %d Max Clusters: %d Max stacks per cluster: %d"
|
|
" root: %x\n",
|
|
number_of_stacks, max_clusters, stacks_per_cluster,
|
|
&root_cluster);
|
|
dbgPrintf("Cluster root: ");
|
|
dbgPrintf("base: %x, limit: %x, size: %d, mid_list: %x,"
|
|
" mid_move: %d\n\n",
|
|
root_cluster.base, root_cluster.limit, root_cluster.elements,
|
|
root_cluster.mid_list, root_cluster.mid_move);
|
|
for (cluster = (cluster_t *)queue_head(&root_cluster.link);
|
|
cluster != (cluster_t *)queue_end(&root_cluster.link);
|
|
cluster = (cluster_t *)queue_next(&cluster->link))
|
|
dump_cluster_element(cluster);
|
|
}
|
|
|
|
|
|
dump_cluster_element(cluster_t *cluster)
|
|
{
|
|
stk_t stack;
|
|
|
|
dbgPrintf("Cluster %x:\n", cluster);
|
|
dbgPrintf("size: %d, mid_list: %x, base: %x, limit: %x, mid_move: %d\n",
|
|
cluster->elements, cluster->mid_list,
|
|
cluster->base, cluster->limit, cluster->mid_move);
|
|
|
|
for (stack = (stk_t)queue_head(&cluster->stack_list);
|
|
stack != (stk_t)queue_end(&cluster->stack_list);
|
|
stack = (stk_t)queue_next(&stack->link))
|
|
dump_stack_element(stack);
|
|
}
|
|
|
|
|
|
dump_stack_element(stk_t stack)
|
|
{
|
|
dbgPrintf("\tStack %x: ", stack);
|
|
dbgPrintf("base: %5x, limit: %5x, vp: %x\n",
|
|
stack->base, stack->limit, stack->vp);
|
|
}
|
|
|
|
#endif
|
|
|