⟦65c3a0da4⟧

TextFile

/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char	*sccsid = "@(#)mapit.c	8.16 (down!honey) 86/09/19";
#endif

#include "def.h"

#ifndef DEBUG
#define chkheap(i)	/* void */
#endif

/* exports */
extern void mapit();

/* invariant while mapping: Nheap < Slop < Hashpart */
long Hashpart;		/* start of unreached nodes */
long Slop;		/* start of mapped nodes */
long Nheap;		/* end of heap */

/* imports */
extern void freelink(), resetnodes(), putaside(), printit(), dumpgraph();
extern void showlinks(), die();
extern long pack(), allocation();
extern link *newlink(), *addlink();
extern int maptrace();

extern long Nheap, Slop, Hashpart, Tabsize;
extern int Dflag, Tflag, Vflag;
extern node **Table, *Home;
extern char *Linkout, *Graphout;


/* privates */
STATIC void insert(), heapup(), heapdown(), heapswap(), backlinks();
STATIC void setheapbits(), mtracereport();
STATIC link *min_node();
STATIC int dehash(), skiplink();
STATIC Cost costof();

static long	Heaphighwater;
static link	**Heap;

/* hook for mtracereport() */
static char *Add = "add";

/* transform the graph to a shortest-path tree by marking tree edges */
void
mapit(phase)
{	register node *n, *next;
	register link *l;
	link *lparent;
	Cost cost;
	static int firsttime = 0;
	int mtrace = 0;

	vprintf(stderr, "*** PHASE %d mapping\n", phase);
	Tflag = Tflag && Vflag;	/* tracing here only if verbose */
	/* re-use the hash table space for the heap */
	Heap = (link **) Table;
	Hashpart = pack(0L, Tabsize - 1);
	Slop = Hashpart - 1;

	/* expunge penalties from -a option and costs from earlier phases */
	resetnodes();

	if (firsttime++) {
		if (Linkout && *Linkout)	/* dump cheapest links */
			showlinks();
		if (Graphout && *Graphout)	/* dump the edge list */
			dumpgraph();
	}

	/* insert Home to get things started */
	l = newlink();		/* link to get things started */
	l->l_to = Home;
	(void) dehash(Home);
	insert(l);

	/* main mapping loop */
remap:
	Heaphighwater = Nheap;
	while ((lparent = min_node()) != 0) {
		chkheap(1);
		lparent->l_flag |= LTREE;
		n = lparent->l_to;
		if (Tflag && maptrace(n, n))
			fprintf(stderr, "%s -> %s mapped\n", n->n_name, n->n_parent->n_name);
		if (n->n_flag & MAPPED)
			die("mapped node in heap");
		n->n_flag |= MAPPED;

		/* add children to heap */
		for (l = n->n_link; l; l = l->l_next) {

			next = l->l_to;		/* neighboring node */

			mtrace = Tflag && maptrace(n, next);

			if (next->n_flag & MAPPED) {
				if (mtrace)
					mtracereport(n, next, "already mapped");
				continue;
			}
			cost = costof(n, l);
			if (phase == NODOMAINS && ISADOMAIN(next))
				cost += INF;
			if (skiplink(l, n, cost, mtrace))
				continue;

			/*
			 * put this link in the heap and restore the
			 * heap property.
			 */
			if (mtrace) {
				if (next->n_parent)
					mtracereport(next->n_parent, next, "drop");
				mtracereport(n, next, Add);
			}
			next->n_parent = n;
			if (dehash(next) == 0) {  /* first time */
				next->n_cost = cost;
				insert(l);	  /* insert at end */
				heapup(l);
			} else {
				/* replace inferior path */
				Heap[next->n_tloc] = l;
				if (cost > next->n_cost) {
					/* increase cost (gateway) */
					next->n_cost = cost;
					heapdown(l);
				} else if (cost < next->n_cost) {
					/* cheaper route */
					next->n_cost = cost;
					heapup(l);
				}
			}
			setheapbits(n, l);
			chkheap(1);

		}
		putaside(n);	/* put it aside for the next phase */

	}
	vprintf(stderr, "heap high water mark was %d\n", Heaphighwater);

	/* sanity check on implementation */
	if (Nheap != 0)
		die("null entry in heap");

	if (Dflag || phase == NODOMAINS) {
		if (Hashpart < Tabsize) {
			/*
			 * add back links from unreachable hosts to
			 * reachable neighbors, then remap.
			 *
			 * asymptotically, this is quadratic; in
			 * practice, this is done once or twice.
			 */
			backlinks();
			if (Nheap)
				goto remap;
		}
		if (Hashpart < Tabsize) {
			fputs("You can't get there from here:\n", stderr);
			for ( ; Hashpart < Tabsize; Hashpart++) {
				fprintf(stderr, "\t%s", Table[Hashpart]->n_name);
				if (Table[Hashpart]->n_flag & ISPRIVATE)
					fputs(" (private)", stderr);
				putc('\n', stderr);
			}
		}
	}
	vprintf(stderr, "allocation is %ldk after mapping\n", allocation());

	printit(phase);	/* traverse tree and print paths */

	vprintf(stderr, "allocation is %ldk after printing\n", allocation());
}

/*
 * return 1 if we definitely don't want want this link in the
 * shortest path tree, 0 if we might want it, i.e., best so far.
 *
 * if tracing is turned on, report only if this node is being skipped.
 */
STATIC int
skiplink(l, parent, cost, trace)
	link *l;		/* new link to this node */
	node *parent;		/* new parent of this node */
	Cost cost;		/* new cost to this node */
	int trace;		/* link is being traced? */
{	register node *n;	/* this node */
	link *lheap;		/* old link to this node */

	n = l->l_to;


	/* first time we've reached this node? */
	if (n->n_tloc >= Hashpart)
		return(0);

	lheap = Heap[n->n_tloc];

	/* examine links to nets that require gateways */
	if (GATEWAYED(n)) {
		/* if exactly one is a gateway, use it */
		if ((lheap->l_flag & LGATEWAY) && !(l->l_flag & LGATEWAY)) {
			if (trace)
				mtracereport(parent, n, "old gateway");
			return(1);	/* old is gateway */
		}
		if (!(lheap->l_flag & LGATEWAY) && (l->l_flag & LGATEWAY))
			return(0);	/* new is gateway */

		/* no gateway or both gateways;  resolve in standard way ... */
	}

	/* examine dup link (sanity check) */
	if (n->n_parent == parent && ((lheap->l_flag & LDEAD) || (l->l_flag & LDEAD)))
		die("dup dead link");


	/*  examine cost */
	if (cost < n->n_cost)
		return(0);
	if (cost > n->n_cost) {
		if (trace)
			mtracereport(parent, n, "cheaper");
		return(1);
	}

	/* all other things being equal, ask the oracle */
	if (tiebreaker(n, parent)) {
		if (trace)
			mtracereport(parent, n, "tiebreaker");
		return(1);
	}
	return(0);
}

STATIC Cost
costof(prev, l)
	register node *prev;
	register link *l;
{	register node *next;
	register Cost cost;
	node *alias;

	if (l->l_flag & LALIAS)
		return(prev->n_cost);	/* by definition */

	next = l->l_to;
	cost = prev->n_cost + l->l_cost;	/* basic cost */

	/*
	 * heuristics:
	 *    charge for a dead link.
	 *    charge for getting out of a dead host.
	 *    charge for getting into a gatewayed net (except at a gateway).
	 *    discourage mixing of left and right syntax when prev is a host.
	 *    charge for leaving a domain.
	 *
	 * life was simpler when pathalias computed true shortest paths.
	 */
	if (l->l_flag & LDEAD)		/* dead link */
		cost += INF;
	if (DEADHOST(prev))		/* dead host */
		cost += INF;
	if (GATEWAYED(next) && !(l->l_flag & LGATEWAY))	/* not gateway */
		cost += INF;
	if (!ISANET(prev)) {
		/* charge for mixed syntax here */
		if ((NETDIR(l) == LLEFT && (prev->n_flag & HASRIGHT))
		 || (NETDIR(l) == LRIGHT && (prev->n_flag & HASLEFT)))
			cost += INF;
	}
	/*
	 * discourage links out of domains (except subdomains).
	 */
	for (alias = prev; alias->n_flag & NALIAS; alias = alias->n_parent)
		;
	if (alias->n_parent && ISADOMAIN(alias->n_parent) && !ISADOMAIN(alias))
		cost += INF;	/* heavyweight, but appropriate */

	return(cost);
}

/* binary heap implementation of priority queue */

STATIC void
insert(l)
	link *l;
{	register node *n;

	n = l->l_to;
	if (n->n_flag & MAPPED)
		die("insert mapped node");

	Heap[n->n_tloc] = 0;
	if (Nheap+1 == Slop)
		Slop = pack(Slop, Hashpart-1);
	if (Heap[Nheap+1] != 0)
		die("heap error in insert");
	if (Nheap++ == 0) {
		Heap[1] = l;
		n->n_tloc = 1;
		return;
	}
	if (Vflag && Nheap > Heaphighwater)
		Heaphighwater = Nheap;	/* diagnostics */

	/* insert at the end.  caller must heapup(l). */
	Heap[Nheap] = l;
	n->n_tloc = Nheap;
}

/*
 * "percolate" up the heap by exchanging with the parent.  as in
 * min_node(), give tiebreaker() a chance to produce better, stable
 * routes by moving nets and domains close to the root, nets closer
 * than domains.
 *
 * i know this seems obscure, but it's harmless and cheap.  trust me.
 */
STATIC void
heapup(l)
	link *l;
{	register long cindx, pindx;	/* child, parent indices */
	register Cost cost;
	register node *child, *parent;

	child = l->l_to;

	cost = child->n_cost;
	for (cindx = child->n_tloc; cindx > 1; cindx = pindx) {
		pindx = cindx / 2;
		if (Heap[pindx] == 0)	/* sanity check */
			die("impossible error in heapup");
		parent = Heap[pindx]->l_to;
		if (cost > parent->n_cost)
			return;

		/* net/domain heuristic */
		if (cost == parent->n_cost) {
			if (!ISANET(child))
				return;
			if (!ISADOMAIN(parent))
				return;
			if (ISADOMAIN(child))
				return;
		}
		heapswap(cindx, pindx);
	}
}

/* extract min (== Heap[1]) from heap */
STATIC link	*
min_node()
{	link *rval, *lastlink;
	register link **rheap;

	if (Nheap == 0)
		return(0);

	rheap = Heap;		/* in register -- heavily used */
	rval = rheap[1];	/* return this one */

	/* move last entry into root and reheap */
	lastlink = rheap[Nheap];
	rheap[Nheap] = 0;

	if (--Nheap) {
		rheap[1] = lastlink;
		lastlink->l_to->n_tloc = 1;
		heapdown(lastlink);	/* restore heap property */
	}

	return(rval);
}

/*
 * swap Heap[i] with smaller child, iteratively down the tree.
 *
 * given the opportunity, attempt to place nets and domains
 * near the root.  this helps tiebreaker() shun domain routes.
 */

STATIC void
heapdown(l)
	link *l;
{	register long pindx, cindx;
	register link **rheap = Heap;	/* in register -- heavily used */
	node *child, *rchild, *parent;

	pindx = l->l_to->n_tloc;
	parent = rheap[pindx]->l_to;	/* invariant */
	for ( ; (cindx = pindx * 2) <= Nheap; pindx = cindx) {
		/* pick lhs or rhs child */
		child = rheap[cindx]->l_to;
		if (cindx < Nheap) {
			/* compare with rhs child */
			rchild = rheap[cindx+1]->l_to;
			/*
			 * use rhs child if smaller than lhs child.
			 * if equal, use rhs if net or domain.
			 */
			if (child->n_cost > rchild->n_cost) {
				child = rchild;
				cindx++;
			} else if (child->n_cost == rchild->n_cost)
				if (ISANET(rchild)) {
					child = rchild;
					cindx++;
				}
		}

		/* child is the candidate for swapping */
		if (parent->n_cost < child->n_cost)
			break;

		/*
		 * heuristics:
		 *	move nets/domains up
		 *	move nets above domains
		 */
		if (parent->n_cost == child->n_cost) {
			if (!ISANET(child))
				break;
			if (ISANET(parent) && ISADOMAIN(child))
				break;
		}

		heapswap(pindx, cindx);
	}
}

/* exchange Heap[i] and Heap[j] pointers */
STATIC void
heapswap(i, j)
	long i, j;
{	register link *temp, **rheap;

	rheap = Heap;	/* heavily used -- put in register */
	temp = rheap[i];
	rheap[i] = rheap[j];
	rheap[j] = temp;
	rheap[j]->l_to->n_tloc = j;
	rheap[i]->l_to->n_tloc = i;
}

/* return 1 if n is already de-hashed (n_tloc < Hashpart), 0 o.w. */
STATIC int
dehash(n)
	register node *n;
{
	if (n->n_tloc < Hashpart)
		return(1);

	/* swap with entry in Table[Hashpart] */
	Table[Hashpart]->n_tloc = n->n_tloc;
	Table[n->n_tloc] = Table[Hashpart];
	Table[Hashpart] = n;

	n->n_tloc = Hashpart++;
	return(0);
}

STATIC void
backlinks()
{	link *l;
	node *n, *parent, *nomap;
	long i;

	for (i = Hashpart; i < Tabsize; i++) {
		nomap = Table[i];
		parent = 0;
		for (l = nomap->n_link; l; l = l->l_next) {
			n = l->l_to;
			if (!(n->n_flag & MAPPED))
				continue;
			if (parent == 0) {
				parent = n;
				continue;
			}
			if (n->n_cost > parent->n_cost)
				continue;
			if (n->n_cost == parent->n_cost) {
				nomap->n_parent = parent;
				if (tiebreaker(nomap, n))
					continue;
			}
			parent = n;
		}
		if (parent == 0)
			continue;
		(void) dehash(nomap);
		l = addlink(parent, nomap, INF, DEFNET, DEFDIR);
		nomap->n_parent = parent;
		nomap->n_cost = costof(parent, l);
		insert(l);
		heapup(l);
	}
	vprintf(stderr, "%d backlinks\n", Nheap);
}

STATIC void
setheapbits(prev, l)
	register node *prev;
	register link *l;
{	register node *next;

	next = l->l_to;
	next->n_flag &= ~(NALIAS|HASLEFT|HASRIGHT);	/* reset */

	/* record whether link is an alias */
	if (l->l_flag & LALIAS)
		next->n_flag |= NALIAS;

	/* set left/right bits */
	if (NETDIR(l) == LLEFT || (prev->n_flag & HASLEFT))
		next->n_flag |= HASLEFT;
	if (NETDIR(l) == LRIGHT || (prev->n_flag & HASRIGHT))
		next->n_flag |= HASRIGHT;
}

STATIC void
mtracereport(from, to, excuse)
	node *from, *to;
	char *excuse;
{
	if (excuse == Add) {
		fprintf(stderr, "+ %s -> %s\n", from->n_name, to->n_name);
		return;
	}
	fprintf(stderr, "- %s -> %s (%s)\n", from->n_name, to->n_name, excuse);
}
	
#ifdef DEBUG
chkheap(i)
{	int lhs, rhs;

	lhs = i * 2;
	rhs = lhs + 1;

	if (lhs <= Nheap) {
		if (Heap[i]->l_to->n_cost > Heap[lhs]->l_to->n_cost)
			die("chkheap failure on lhs");
		chkheap(lhs);
	}
	if (rhs <= Nheap) {
		if (Heap[i]->l_to->n_cost > Heap[rhs]->l_to->n_cost)
			die("chkheap failure on rhs");
		chkheap(rhs);
	}
}
#endif
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦65c3a0da4⟧ TextFile

Derivation

TextFile
