sources-request@genrad.UUCP (08/08/85)
Mod.sources: Volume 2, Issue 36
Submitted by: Peter Honeyman (princeton!honey)
------------------- cut here --------------------------
: To unbundle, sh this file
echo README 1>&2
sed 's/^-//' >README <<'//GO.SYSIN DD README'
-From princeton!honey Wed Aug 7 00:02:19 EDT 1985
To: whom it may concern
Subject: new pathalias instructions
edit config.h
make
peter
//GO.SYSIN DD README
echo CHANGES 1>&2
sed 's/^-//' >CHANGES <<'//GO.SYSIN DD CHANGES'
--- posted 8/85
Private hosts documented.
Homegrown scanner -- it's true what they say about lex.
Slight improvement in memory allocation. More to come.
Build dbm file with pathalias ... | makedb ...
Don't print paths for private hosts, or anyone they collide with.
Domain-style addresses. See man page.
Make links bidirectional by adding DEAD back link. Dumb, expensive, and wrong.
Gatewayed nets. See man page.
--- posted 1/85
By popular request, no ! in dbm key.
Network character must be one of !@%: -- dot is dead.
Private hosts. (Undocumented. Goal is to support host name collisions.)
Discourage mixing of left- (@) and right-associative (!) operators.
Magic @ <-> % rule in paths involving multiple @'s.
--- from smb version
Directed graph.
Reverse the sense of the -c (cost) flag.
Don't complain about duplicate links -- use cheapest.
No network names in the output.
--- epoch
//GO.SYSIN DD CHANGES
echo pathalias.1 1>&2
sed 's/^-//' >pathalias.1 <<'//GO.SYSIN DD pathalias.1'
.TH PATHALIAS 1
.SH NAME
pathalias, makedb \- electronic address router
.SH SYNOPSIS
.B pathalias
[
.B \-vci
] [
.B \-l
host
] [
.B \-d
link
] [
.ig
.\" the -g option is for pathparse. it's not really used by pathalias.
.B \-g
file
] [
..
inputfiles
]
.PP
.B makedb
[
.B \-a
] [
.B \-o
dbmfile
] [
files ...
]
.SH DESCRIPTION
.I Pathalias
computes the shortest paths and corresponding routes from one
host to all other known, reachable hosts.
\fIPathalias\fP expects as input host-to-host connectivity
information, with
a host name in column 1, followed by white space, followed by
a comma-separated list of links (also host names),
denoting a connection from the host to the links.
Connections are assumed to be unidirectional.
A link-name may be preceded or followed by a network character to use
in the path name.
Valid network characters are `!', `@', `:', and `%'.
The link-name (and network character, if present) may be
followed by a ``cost'' in parentheses.
.PP
For example,
.RS
.nf
down princeton!(DEDICATED)
princeton topaz!(DEMAND+LOW)
topaz @rutgers(LOCAL)
.fi
.RE
Costs may be arbitrary
arithmetic expressions involving numbers, parentheses, '+', '\-', '*',
and '/'. Several symbolic numbers are
defined, as follows:
.PP
.RS
.nf
.ta 10m 20m
LOCAL 25 (local-area network connection)
DEDICATED 95 (high speed dedicated link)
DIRECT 200 (toll-free call)
DEMAND 300 (long-distance call)
HOURLY 500 (hourly poll)
EVENING 1800 (time restricted call)
DAILY 5000 (daily poll)
WEEKLY 30000 (irregular poll)
.fi
.RE
.PP
In addition,
DEAD is a very large number (effectively infinite),
and HIGH and LOW are \-5 and +5 respectively,
for baud-rate or quality bonuses/penalties.
.PP
The numbers are intended to represent frequency
of connection, which seems to be far more important than baud
rates for this type of traffic. There is an assumed
high overhead for each hop; thus, e.g., HOURLY is far more than
DAILY / 24.
.PP
For the most part, arithmetic expressions that mix symbolic constants
other than HIGH and LOW make no sense. Thus, \fIe.g.\fP, if a host
calls a local neighbor whenever there is work,
and additionally polls every evening, the cost is
DIRECT, \fInot\fP DIRECT+EVENING.
.PP
Aliases may be indicated by including lines of the form
.RS
name = alias [ , alias...]
.RE
The primary name is used in the output.
.PP
Fully connected networks, such as the ARPANET or a LAN,
are indicated by
.RS
net = {host, host, ...}
.RE
The host-list may be preceded or followed by a routing
character, and may be followed by a cost:
.RS
.nf
princeton-ethernet = {down, yoyo, flakey, quirky, princeton, ivy}!(LOCAL)
ARPA = @{sri-unix, mit-ai, su-score}(DEDICATED)
.fi
.RE
Also see the section on \fIgateways and domains\fP below.
.PP
Connection data may be given while hiding host names
by declaring
.RS
private {host [, host ...]}
.RE
.PP
.I Pathalias
will not generate routes for private hosts or for any otherwise declared
host with the same name, but may produce routes
through them.
The scope of a private declaration extends from the declaration to the end of
the input file in which it appears.
It is best to put private definitions at the beginning of the
appropriate input file.
.PP
Anything following # on an input line is ignored. A line that begins with white
space is taken as a continuation of the previous line.
.PP
The output, which appears on the standard output,
is a list of host\-route pairs,
where route is a string appropriate for use with
\fIprintf\fP(3), e.g.
.RS
.nf
.ta 10m 20m
rutgers princeton!topaz!%s@rutgers
.fi
.RE
The ``%s'' in the route string should be replaced by the
user name at the destination host.
(This task is normally performed by a mailer.)
.PP
Except in the case of \fidomains\fP (see below),
the name of a network is never used in
expansions; thus, in the above example, the path from sri-unix to
mit-ai would be '%s@mit-ai', not '%s@ARPA@mit-ai'.
.PP
Options:
.TP 6
.B \-i
Map all host names to lower case.
.TP 6
.B \-c
Print the costs of paths.
.TP 6
.B \-v
Report some statistics on stderr.
.ig
.\" the -g option is for pathparse and is not for public consumption (yet!).
.TP 6
.BR \-g " file\^"
Dump the edges of the graph into the named file.
..
.TP 6
.BR \-l " host\^"
Use host as local host name.
.TP 6
.BR \-d " link\^"
Declares a dead link, host, or network.
If link is of the form host1!host2, the link from host1 to host2
is treated as an extremely high cost (i.e., dead) link.
If link is a single host name, that
host is treated as dead and will be used as an intermediate host of
last resort on any path.
If link is a network name, the network requires a gateway.
.PP
\fBGateways and domains.\fP\ \ A network is represented by
a pseudo-host and a set of network members.
Links from the network to the members have the weight given in
the input, while
links from the members to the network
have zero cost.
Networks that are declared dead on the command line show these
latter weights as expensive ones,
effectively prohibiting paths to members by way of the network.
If the input also shows non-zero weight links from some members to the network,
these hosts will act as gateways for the network.
E.g., if csnet is declared dead on the command line (with
the -d flag) and the input contains
.RS
.nf
csnet = {...}
csnet-relay csnet
.fi
.RE
then routes to csnet hosts will use csnet-relay as a gateway,
rather than some other csnet host, one that might not
be able or willing to act as a gateway.
Furthermore, it is presumed that forwarding through
gatewayed networks is to be discouraged.
.PP
Some intermediate nodes expect routes to specify domain names, e.g.,
to get to bitnet host technion through the gateway at psuvax1,
the appropriate route might be psuvax1!technion.bitnet!user.
This syntax is generated if the routing character is repeated in
the declaration of the gateway to the ``domain'', e.g.,
.RS
.nf
bitnet = {..., technion, ...}!(DIRECT)
psuvax1 bitnet!!(DIRECT)
.fi
.RE
This syntax works with other routing characters as well, e.g.,
.RS
.nf
csnet = @{...}
csnet-relay @@csnet
.fi
.RE
.PP
.I Makedb
builds a
.IR dbm (3)
database from the named input files, or from the standard input if
no files are specified.
(This replaces the obsolete
.I -b
flag of
.IR pathalias .)
Normally, the database is truncated;
if
.B \-a
is specified, the input records are appended to the existing database.
The
.B \-o
flag specifies the base name of the dbm file.
Input is expected to be sequence of ascii records
each consisting of a key field and a data field, separated by a single tab.
If the tab is missing, the data field is assumed to be empty.
.SH FILES
.ta \w'/usr/local/lib/palias.{dir,pag} 'u
/usr/local/lib/palias.{dir,pag} default dbm output
.SH BUGS
White space in options is mandatory;
.I pathalias
should use
.IR getopt (3).
.br
The format string intended for
.I printf
is unable to anticipate the variety of addressing
rules.
In particular, if it contains an ``@'' and is given to
.I printf
along with an argument that also contains an ``@'', havoc is loosed.
.br
Domains constitute a futile attempt to defeat anarchy.
.br
The -i flag makes rice.rice impossible.
.br
.IR Dbm (3)
wants a non-empty data field, forcing
.I makedb
to be imaginative.
.SH COMPILE-TIME
Edit config.h to accommodate \s-2UNIX\s0 variants.
.SH AUTHORS
Steve Bellovin (ulysses!smb)
.br
Peter Honeyman (princeton!honey)
//GO.SYSIN DD pathalias.1
echo Makefile 1>&2
sed 's/^-//' >Makefile <<'//GO.SYSIN DD Makefile'
# pathalias -- by steve bellovin, as told to peter honeyman
# if you can't or don't intend to use dbm files, don't bother with makedb
DBM = -ldbm
# or if you roll your own ...
# DBM = dbm.o
CC = cc
CFLAGS =
LDFLAGS =
YFLAGS = -d
OBJ = addlink.o addnode.o extern.o local.o main.o mapit.o mapaux.o mem.o parse.o yylex.o
HDRS = def.h config.h
SRC = addlink.c addnode.c extern.c local.c main.c mapit.c mapaux.c mem.c parse.y yylex.c
CSRC = addlink.c addnode.c extern.c local.c main.c mapit.c mapaux.c mem.c parse.c yylex.c
pathalias: $(OBJ)
$(CC) $(LDFLAGS) $(OBJ) $(LIBE) -o pathalias
all: pathalias makedb
$(OBJ): def.h
# if touch had a proper exit status, this would work...
def.h: config.h
touch def.h || get -s sccs/s.def.h
parse.c: parse.y def.h
$(YACC) $(YFLAGS) parse.y
mv y.tab.c parse.c
yylex.o: parse.c yylex.c
makedb: makedb.o
$(CC) makedb.o $(DBM) -o makedb
makedb.o: config.h
clean:
rm -f *.o pa y.tab.c y.tab.h parse.c core
tags: $(SRC) $(HDRS) makedb.c
ctags -w $(HDRS) $(SRC)
bundle:
@bundle README CHANGES pathalias.1 Makefile ${HDRS} ${SRC} makedb.c
lint: $(CSRC)
lint $(CFLAGS) $(CSRC)
lint makedb.c
# the remainder is site specific and can be deleted.
# administering paths on 6 machines is easy -- here's how i do it
# hosts running delivermail
DMEQUIV = tilt
# hosts running sendmail
SMEQUIV = quirky flakey yoyo
# all neighbors
NEIGHBORS = ${DMEQUIV} ${SMEQUIV} princeton
# including me
SITES = down ${NEIGHBORS}
# in v8, * includes . files, sh has extended syntax.
PATHFILES = paths/[^.]* paths.bell/[^.]* path.map/[^.]*
# from observation and rumor
# avoid like the plague
DEADHOSTS = -d harpo -d zeppo -d chico -d gummo -d tucc -d hogpc -d eosp1 -d twg
DEADLINKS = -d fortune!analog -d uiucdcs!uokmet -d siemens!uiucdcs -d vax135!uw-beaver -d research!eagle -d decvax!humus -d ulysses!ucbarpa
# nets that require gateways
DEADNETS = -d CSNET -d BITNET -d ARPA -d DEC -d MAILNET
DEAD = ${DEADHOSTS} ${DEADLINKS} ${DEADNETS}
# map output to lower case. dead links.
ARGS = -i $(DEAD)
paths: ${SITES}
# don't touch "down" until completely done.
down: paths/princeton
pathalias -v ${ARGS} $(PATHFILES) > down.new 2>ERRORS
sort down.new > down
# rm down.new
# NEIGHBORS have exactly the same links as down, so turn
# down %s
# up up!%s
# into
# up %s
# down down!%s
# generate phoney costs for delivermail neighbors
${DMEQUIV}: down
sed -e "s/^down %s$$/$@ %s/" -e "s/^$@ $@!%s$$/down down!%s/" -e 's/^/0 /' down > $@
# reorder the output and generate phoney costs for sendmail neighbors
${SMEQUIV}: down
sed -e "s/^down %s$$/$@ %s/" -e "s/$@ $@!%s$$/down down!%s/" -e 's/\(.*\) \(.*\)/\1 0 \2/' down > $@
# ship it!
sendit: ${NEIGHBORS}
for i in ${DMEQUIV}; do\
uucp -ga $$i $$i!/usr/local/lib/pathaliases;\
uux -z -gb $$i!newaliases;\
done
for i in ${SMEQUIV} princeton; do uucp $$i $$i!~/paths; done
touch sendit
# reorder the output for princeton/sendmail/uubang and generate phoney costs.
princeton: down
pathalias ${ARGS} -l $@ $(PATHFILES)> $@.new 2>ERRORS
sed -e 's/\(.*\) \(.*\)/\1 0 \2/' $@.new > $@
rm $@.new
# make output for friends. (make friends for output?)
sfyog rcalabs neoucom:
pathalias ${ARGS} -l $@ $(PATHFILES) > $@ 2>ERRORS
# desperation debugging -- examine the costs.
costs:
pathalias -vci ${DEAD} -l down $(PATHFILES) > down.costs 2>ERRORS
# make one BIG file. a bad idea.
cat:
cat $(PATHFILES) > CAT
# generate test data using undocumented features. (go away.)
edges: down
pathalias -i -g edges $(PATHFILES)
//GO.SYSIN DD Makefile
echo def.h 1>&2
sed 's/^-//' >def.h <<'//GO.SYSIN DD def.h'
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
#ifdef MAIN
static char *h_sccsid = "@(#)def.h 7.1 (down!honey) 85/08/06";
#endif MAIN
#endif lint
#include <stdio.h>
#include <ctype.h>
#include "config.h"
typedef long Cost;
typedef struct node node;
typedef struct link link;
#ifdef lint
#define vprintf fprintf
#else !lint -- this gives null effect warning
/* because it's there ... */
#define vprintf !Vflag ? 0 : fprintf
#endif lint
/* scanner (yylex) states */
#define OTHER 0
#define COSTING 1
#define NEWLINE 2
#define PRIVATING 3
#define isnetc(c) ((c)=='!' || (c)==':' || (c)=='@' || (c)=='%')
#define dirbits(c) (c)
/* flags for n_flag */
#define ISPRIVATE 0x0001 /* this node invisible outside its definition file */
#define DEHASH 0x0002 /* removed from hash table yet? */
#define ATSIGN 0x0004 /* seen an at sign? used for magic @/% rules */
#define MAPPED 0x0008 /* done mapping this node */
#define NDEAD 0x0010 /* node is dead */
#define HASLEFT 0x0020 /* route has a left side net character */
#define HASRIGHT 0x0040 /* route has a right side net character */
#define NNET 0x0080 /* node is a network name */
#define INDFS 0x0100 /* used when removing net cycles */
#define DUMP 0x0200 /* we have dumped this net's edges */
#define NDOMAIN 0x0400 /* use .domain style addressing */
#define GATEWAYIN 0x0800 /* heaped via gatewayed net */
#define COLLISION 0x1000 /* collides with a private host name */
#define DEADNET(n) (((n)->n_flag & (NNET | NDEAD)) == (NNET | NDEAD))
/*
* save some space in nodes -- there are > 10,000 allocated!
*
* node *n_net others in this network (parsing)
* node *n_root root of net cycle (mapping)
*
* node *n_private other privates in this file (parsing)
* char *n_path path to this host (mapping)
*
*/
#define n_root n_unetroot.nu_root
#define n_net n_unetroot.nu_net
#define n_private n_uprivatepath.nu_private
#define n_path n_uprivatepath.nu_path
struct node {
char *n_name; /* host name */
link *n_link; /* head of adjacency list */
node *n_alias; /* real node (when this node is an alias) */
node *n_aliaslink; /* other aliases for this node */
union {
node *nu_root; /* root of net cycle (mapping) */
node *nu_net; /* others in this network (parsing) */
} n_unetroot;
union {
node *nu_private; /* other privates in this file (parsing) */
char *nu_path; /* path to this host (mapping) */
} n_uprivatepath;
Cost n_cost; /* cost to this host */
short n_tloc; /* back ptr to heap/hash table */
short n_flag; /* see manifests above */
};
#define DEFNET '!' /* default network character */
#define DEFDIR LLEFT /* host on left in default net */
#define DEFCOST ((Cost) 4000) /* default cost of a link */
#define INF ((Cost) 30000000) /* infinitely expensive link */
/* data structure for adjacency list representation */
/* flags for l_dir */
/*
* there's an ugly dependency between the following manifests and the
* variable Netchars = "!:^@%", defined in extern.c. this saves 2
* bytes per link (of which there are well over 20k). this does not
* mean i'm satsified with bad design.
*/
#define NETDIR(l) ((l)->l_flag & LDIR)
#define NETCHAR(l) (Netchars[(l)->l_flag & LNETCHARS])
#define LNETCHARS 0x3
#define LBANG 0x0
#define LCOLON 0x1
#define LAT 0x2
#define LPERCENT 0x3
#define LDIR 0x8 /* 0 for left, 1 for right */
#define LRIGHT 0x0 /* user@host style */
#define LLEFT 0x8 /* host!user style */
#define LDEAD 0x10 /* this link is dead */
#define LDOMAIN 0x20 /* use host.domain. i feel sick. */
struct link {
link *l_next; /* rest of adjacency list */
node *l_to; /* adjacent node */
Cost l_cost; /* edge cost */
char l_flag; /* right/left syntax */
};
node *addnode(), *newnode(), **newtable(), *addprivate();
link *addlink(), *lmerge(), *newlink();
char *strsave(), *local();
void setpath(), pack();
#define STATIC static
extern node *Home;
extern char *Cfile;
extern int Fcnt;
extern char **Ifiles;
extern char *ProgName;
extern int Lineno;
extern node **Table;
extern int Tabsize;
extern char *Netchars;
extern int Vflag;
extern int Cflag;
extern int Iflag;
extern int Ncount;
extern int Lcount;
extern char *Pathout;
extern char *Graphout;
extern char *Linkout;
extern node *Private;
extern int Hashpart;
extern int Scanstate;
//GO.SYSIN DD def.h
echo config.h 1>&2
sed 's/^-//' >config.h <<'//GO.SYSIN DD config.h'
/* pathalias -- by steve bellovin, as told to peter honeyman */
/* use strchr (strrchr), not index (rindex) -- probably system v */
/* #define STRCHR /* */
/* uname() -- probably system v or 8th ed. */
#define UNAME /* */
/* memset() -- probably system v or 8th ed. */
#define MEMSET /* */
/* gethostname() -- probably 4.2bsd */
/* #define GETHOSTNAME /* */
/* bzero() -- probably 4.2bsd */
/* #define BZERO /* */
/* default place for dbm output of makedb; can use -o file at run-time */
#define ALIASDB "/usr/local/lib/palias"
/*
* after much profiling, i finally found a decent malloc/free
* remove the next line if you disagree
*/
#define MYMALLOC /**/
/*
* how many trailing 0's needed in a pointer?
*
* vax doesn't care, but setting ALIGN to 2 saves about 5% in time, at
* the expense of about 2% in space. why bother?
*
* i am told that the 68000 and 3b20 want ALIGN to be 1.
*
* perkin-elmer 3220 wants ALIGN to be 2.
*/
#define ALIGN 0
/****************************************/
/* END OF CONFIGURATION SECTION */
/* EDIT NO MORE */
/****************************************/
#ifdef MAIN
#ifndef lint
static char *c_sccsid = "@(#)config.h 7.1 (down!honey) 85/08/06";
#endif lint
#endif MAIN
#ifdef MYMALLOC
#define malloc mymalloc
#define free myfree
char *sbrk(), *mymalloc();
#ifdef ALIGN
#if ALIGN == 0
#undef ALIGN
#endif ALIGN == 0
#endif ALIGN
#ifndef ALIGN
#define memget sbrk
#else ALIGN
char *memget();
#endif ALIGN
#endif MYMALLOC
#ifdef STRCHR
#define index strchr
#define rindex strrchr
#endif STRCHR
#ifdef BZERO
#define strclear(s, n) ((void) bzero((s), (n)))
#else !BZERO
# ifdef MEMSET
char *memset();
# define strclear(s, n) ((void) memset((s), 0, (n)))
# else !MEMSET
(void) strclear();
# endif MEMSET
#endif BZERO
long atol();
char *malloc();
char *index();
char *rindex();
FILE *popen();
char *strcpy();
//GO.SYSIN DD config.h
echo addlink.c 1>&2
sed 's/^-//' >addlink.c <<'//GO.SYSIN DD addlink.c'
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)addlink.c 7.1 (down!honey) 85/08/06";
#endif lint
#include "def.h"
link *
addlink(from, to, cost, netchar, netdir)
node *from;
register node *to;
Cost cost;
char netchar;
char netdir;
{
register link *l, *prev = 0;
#ifndef SQUANDER
/* welcome to cycle city -- inner loop follows */
/*
* link chains are sorted by host struct address, largest to smallest.
* thus, newly declared hosts are at the front of the list.
*/
for (l = from->n_link; l; l = l->l_next) {
if (to >= l->l_to)
break;
prev = l;
}
/* you are now leaving cycle city -- hope you enjoyed your stay */
if (l && (to == l->l_to)) {
/*
* this is twisted by the awful gateway semantics.
*
* if "to" is a dead network, use the cheapest non-zero cost.
* ("from" is a gateway.)
*
* otherwise, use new cost if cheaper.
*/
if ((DEADNET(to) && l->l_cost == 0) || cost < l->l_cost) {
l->l_cost = cost;
netbits(l, netchar, netdir);
}
return(l);
}
#endif !SQUANDER
l = newlink();
if (prev) {
l->l_next = prev->l_next;
prev->l_next = l;
} else {
l->l_next = from->n_link;
from->n_link = l;
}
l->l_to = to;
l->l_cost = cost;
if (netchar == 0) {
netchar = DEFNET;
netdir = DEFDIR;
}
netbits(l, netchar, netdir);
return(l);
}
deadlink(s)
char *s;
{
char *t, c;
link *l;
for (t = s; !isnetc(*t); t++)
if (*t == 0)
break;
if ((c = *t) != 0) {
*t = 0;
l = addlink(addnode(s), addnode(t + 1), INF / 2, c, DEFDIR);
l->l_flag |= LDEAD;
} else
addnode(s)->n_flag |= NDEAD;
}
netbits(l, netchar, netdir)
link *l;
char netchar, netdir;
{
int isadomain = 0;
char *nptr;
if (netchar & 0200) {
netchar &= 0177;
isadomain = LDOMAIN;
}
if ((nptr = index(Netchars, netchar)) == 0) {
fprintf(stderr, "%s: unknown network operator: %c\n",
ProgName, netchar);
badmagic(1);
}
l->l_flag &= ~(LNETCHARS|LDIR|LDOMAIN);
l->l_flag |= (nptr - Netchars) | dirbits(netdir) | isadomain;
}
//GO.SYSIN DD addlink.c
echo addnode.c 1>&2
sed 's/^-//' >addnode.c <<'//GO.SYSIN DD addnode.c'
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)addnode.c 7.1 (down!honey) 85/08/07";
#endif lint
#include "def.h"
void lowercase();
node *isprivate();
/*
* these numbers are chosen because:
* -> they are prime,
* -> they are monotonic increasing,
* -> each is a tad smaller than a multiple of 1024.
* the first point yields good hash functions, the second is used for the
* standard re-hashing implementation of open addressing, and the third
* optimizes for quirks in some mallocs i have seen.
*/
STATIC int Primes[] = {
1021, 2039, 3067, 4093, 5113, 6133, 7159, 8179, 9209,
10223, 11261, 12281, 13309, 14327, 15349, 16381, 17401,
18427, 19447, 20477, 21499, 22511, 23549, 24571, 25589, 0
};
STATIC int Tabindex = -1;
STATIC int Collision; /* mark host name collisions in hash() */
int Tabsize; /* used later for the priority queue */
node **Table; /* ditto */
node *
addnode(name)
register char *name;
{
register int i;
register node *n;
if (Iflag)
lowercase(name);
/* is it a private host? */
n = isprivate(name);
if (n != 0) {
while (n->n_alias)
n = n->n_alias;
return(n);
}
i = hash(name, 0);
if (Table[i] != 0) {
n = Table[i];
while (n->n_alias)
n = n->n_alias;
return(n);
}
n = newnode();
n->n_name = strsave(name);
Table[i] = n;
n->n_tloc = i; /* essentially a back link to the table */
if (Collision)
n->n_flag |= COLLISION; /* name collision with private host */
return(n);
}
alias(parent, child)
register node *parent; /* real node */
register node *child; /* alias node */
{
register node *root; /* root of this alias tree */
if (parent == child) {
char buf[BUFSIZ];
sprintf(buf, "warning: alias redeclaration: %s = %s",
parent->n_name, parent->n_name);
yyerror(buf);
return; /* caused by redeclaration of alias */
}
/* avoid alias loops, force many-to-one */
/* can't happen -- wish it could ... */
if (parent->n_alias || child->n_alias) {
yyerror("can't nest aliases");
return;
}
/* merge links from parent(s) to root, point parent at root */
for (root = parent->n_alias; root; root = root->n_alias) {
root->n_link = lmerge(root->n_link, parent->n_link);
parent->n_link = 0;
parent = root;
}
/* merge child links into parent (now root) */
parent->n_link = lmerge(parent->n_link, child->n_link);
child->n_link = 0;
/* set up the alias pointers */
child->n_alias = parent;
child->n_aliaslink = parent->n_aliaslink;
parent->n_aliaslink = child;
}
/* double hashing */
#define HASH1(n) ((n) % Tabsize);
#define HASH2(n) (((n) % (Tabsize - 2)) + 1)
/*
* at 75% full, probes per access is about 2.
*/
#define HIGHWATER 75
#define LOWWATER 50
#define isfull(n, size) ((n) > (((size) * HIGHWATER) / 100))
#define isempty(n, size) ((n) < (((size) * LOWWATER) / 100))
STATIC int
hash(name, unique)
char *name;
{
register int probe, hash2;
register node *n;
if (Tabindex < 0) { /* first time */
Tabindex = 0;
Tabsize = Primes[0];
Table = newtable(Tabsize);
}
if (isfull(Ncount, Tabsize))
rehash(); /* more, more! */
probe = fold(name);
/* don't change the order of the next two lines */
hash2 = HASH2(probe);
probe = HASH1(probe);
/* thank you! */
/*
* probe the hash table.
* if unique is set, we require a fresh slot.
* otherwise, use double hashing to find either
* (1) an empty slot, or
* (2) a non-private copy of this host name
*
* as a side effect, if we notice a collision with a private host
* we mark the other so that it is skipped at output time.
*/
Collision = 0;
while ((n = Table[probe]) != 0) {
if (strcmp(n->n_name, name) == 0) {
if (unique)
n->n_flag |= COLLISION;
else if (n->n_flag & ISPRIVATE)
Collision++;
else
break; /* this is it! */
}
probe -= hash2;
if (probe < 0)
probe += Tabsize;
}
return(probe);
}
STATIC int
rehash()
{
register node **otable, **optr;
register int probe;
int osize;
#ifdef DEBUG
hashanalyze();
#endif DEBUG
optr = Table + Tabsize - 1; /* ptr to last */
otable = Table;
osize = Tabsize;
do {
Tabsize = Primes[++Tabindex];
if (Tabsize == 0) {
fprintf(stderr, "%s: > %d hosts\n", ProgName,
Primes[Tabindex-1]);
badmagic(1);
}
} while (!isempty(Ncount, Tabsize));
vprintf(stderr, "rehash into %d\n", Tabsize);
Table = newtable(Tabsize);
do {
if (*optr == 0)
continue;
probe = hash((*optr)->n_name, (*optr)->n_flag & ISPRIVATE);
if (Table[probe] != 0) {
fprintf(stderr, "%s: rehash error\n", ProgName);
badmagic(1);
}
Table[probe] = *optr;
(*optr)->n_tloc = probe;
} while (optr-- > otable);
freetable(otable, osize);
}
STATIC
fold(s)
register char *s;
{
register int sum = 0;
while (*s) {
sum <<= 2;
sum += *s++;
}
if (sum < 0)
sum = -sum;
return(sum);
}
/* merge the l2 list into the l1 list */
link *
lmerge(l1, l2)
register link *l1, *l2;
{
register link *ltmp;
link *rval;
if (l1 == 0)
return(l2);
if (l2 == 0)
return(l1);
if (l1->l_to > l2->l_to) {
ltmp = rval = l1;
l1 = l1->l_next;
} else if (l1->l_to < l2->l_to) {
ltmp = rval = l2;
l2 = l2->l_next;
} else if (l1->l_cost <= l2->l_cost) {
ltmp = rval = l1;
l1 = l1->l_next;
free((char *) l2);
l2 = l2->l_next;
} else {
ltmp = rval = l2;
l2 = l2->l_next;
free((char *) l1);
l1 = l1->l_next;
}
while (l1 && l2) {
if (l1->l_to > l2->l_to) {
ltmp->l_next = l1;
ltmp = l1;
l1 = l1->l_next;
} else if (l1->l_to < l2->l_to) {
ltmp->l_next = l2;
ltmp = l2;
l2 = l2->l_next;
} else if (l1->l_cost <= l2->l_cost) { /* use cheaper link */
ltmp->l_next = l1;
ltmp = l1;
l1 = l1->l_next;
free((char *) l2);
l2 = l2->l_next;
} else {
ltmp->l_next = l2;
ltmp = l2;
l2 = l2->l_next;
free((char *) l1);
l1 = l1->l_next;
}
}
if (l1)
ltmp->l_next = l1;
else
ltmp->l_next = l2;
return(rval);
}
hashanalyze()
{
int probe, hash2, count, i, collision[5];
int longest = 0, total = 0, slots = 0;
int nslots = sizeof(collision)/sizeof(collision[0]);
if (!Vflag)
return;
strclear((char *) collision, sizeof(collision));
for (i = 0; i < Tabsize; i++) {
if (Table[i] == 0)
continue;
/* private hosts too hard to account for ... */
if (Table[i]->n_flag & ISPRIVATE)
continue;
count = 1;
probe = fold(Table[i]->n_name);
/* don't change the order of the next two lines */
hash2 = HASH2(probe);
probe = HASH1(probe);
/* thank you! */
while (Table[probe] != 0
&& strcmp(Table[probe]->n_name, Table[i]->n_name) != 0) {
count++;
probe -= hash2;
if (probe < 0)
probe += Tabsize;
}
if (Table[probe] == 0) {
fprintf(stderr, "%s: impossible hash error for %s\n",
ProgName, Table[i]->n_name);
continue;
}
total += count;
slots++;
if (count > longest)
longest = count;
if (count >= nslots)
count = 0;
collision[count]++;
}
for (i = 1; i < nslots; i++)
if (collision[i])
fprintf(stderr, "%d chains: %d (%d%%)\n",
i, collision[i], (collision[i] * 100)/ slots);
if (collision[0])
fprintf(stderr, "> %d chains: %d (%d%%)\n",
nslots - 1, collision[0],
(collision[0] * 100)/ slots);
fprintf(stderr, "%2.2f probes per access, longest chain: %d\n",
(double) total / slots, longest);
}
STATIC void
lowercase(s)
register char *s;
{
do {
*s = isupper(*s) ? tolower(*s) : *s;
} while (*s++);
}
STATIC node *
isprivate(name)
register char *name;
{
register node *n;
for (n = Private; n != 0; n = n->n_private)
if (strcmp(name, n->n_name) == 0)
return(n);
return(0);
}
fixprivate()
{
register node *n, *next;
register int i;
for (n = Private; n != 0; n = next) {
n->n_flag |= ISPRIVATE; /* overkill, but safe */
i = hash(n->n_name, 1);
if (Table[i] != 0) {
fprintf(stderr, "%s: impossible private node error on %s\n",
ProgName, n->n_name);
badmagic(1);
}
Table[i] = n;
n->n_tloc = i; /* essentially a back link to the table */
next = n->n_private;
n->n_private = 0; /* clear for later use */
}
Private = 0;
}
node *
addprivate(name)
register char *name;
{
register node *n;
if (Iflag)
lowercase(name);
n = isprivate(name);
if (n)
return(n); /* this isn't even worth a warning */
n = newnode();
n->n_name = strsave(name);
n->n_private = Private;
Private = n;
return(n);
}
//GO.SYSIN DD addnode.c
echo extern.c 1>&2
sed 's/^-//' >extern.c <<'//GO.SYSIN DD extern.c'
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)extern.c 7.1 (down!honey) 85/08/06";
#endif lint
#include "def.h"
node *Home;
int Fcnt = -1;
char *Cfile;
char **Ifiles;
char *ProgName;
int Vflag;
int Cflag;
int Iflag;
int Lineno = 1;
char *Netchars = "!:@%"; /* sparse, but sufficient */
int Ncount;
int Lcount;
char *Graphout;
char *Linkout;
node *Private; /* list of private nodes in this file */
int Hashpart; /* used while mapping -- above is heap */
int Scanstate = NEWLINE; /* scanner (yylex) state */
//GO.SYSIN DD extern.c
echo local.c 1>&2
sed 's/^-//' >local.c <<'//GO.SYSIN DD local.c'
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)local.c 7.1 (down!honey) 85/08/06";
#endif lint
#include <stdio.h>
#include "config.h"
#ifdef UNAME
#include <sys/utsname.h>
char *
local()
{
static struct utsname utsname;
uname(&utsname);
return(utsname.nodename);
}
#else !UNAME
char *
local()
{
static char lname[64];
void gethostname();
gethostname(lname, sizeof(lname));
return(lname);
}
#ifndef GETHOSTNAME
STATIC void
gethostname(name, len)
char *name;
{
FILE *whoami, *fopen(), *popen();
char *ptr, *index();
*name = '\0';
/* try /etc/whoami */
if ((whoami = fopen("/etc/whoami", "r")) != 0) {
(void) fgets(name, len, whoami);
(void) fclose(whoami);
if ((ptr = index(name, '\n')) != 0)
*ptr = '\0';
}
if (*name)
return;
/* try /usr/include/whoami.h */
if ((whoami = fopen("/usr/include/whoami.h", "r")) != 0) {
while (!feof(whoami)) {
char buf[100];
if (fgets(buf, 100, whoami) == 0)
break;
if (sscanf(buf, "#define sysname \"%[^\"]\"", name))
break;
}
(void) fclose(whoami);
if (*name)
return;
}
/* ask uucp */
if ((whoami = popen("uuname -l", "r")) != 0) {
(void) fgets(name, len, whoami);
(void) pclose(whoami);
if ((ptr = index(name, '\n')) != 0)
*ptr = '\0';
}
if (*name)
return;
/* aw hell, i give up! is this a real unix? */
return;
}
#endif GETHOSTNAME
#endif UNAME
//GO.SYSIN DD local.c
echo main.c 1>&2
sed 's/^-//' >main.c <<'//GO.SYSIN DD main.c'
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
#define MAIN
static char *sccsid = "@(#)main.c 7.1 (down!honey) 85/08/06";
#endif lint
#include "def.h"
main(argc, argv)
int argc;
char *argv[];
{
char *locname = 0;
#ifdef lint
argc = argc;
#endif lint
ProgName = argv[0];
while (*++argv && **argv == '-') {
(*argv)++;
switch(**argv) {
case 'l': /* local name */
locname = *++argv;
if (!*locname) {
fprintf(stderr, "%s: -l requires host name\n",
ProgName);
exit(1);
}
break;
case 'd': /* dead host or link */
if (!*++argv) {
fprintf(stderr, "%s: -d requires host name\n",
ProgName);
exit(1);
}
deadlink(*argv);
break;
case 'g': /* graph output file */
Graphout = *++argv;
if (!*Graphout) {
fprintf(stderr, "%s: -g requires output file name\n",
ProgName);
exit(1);
}
break;
case 's': /* show cheapest links */
Linkout = *++argv;
if (!*Linkout) {
fprintf(stderr, "%s: -s requires output file name\n",
ProgName);
exit(1);
}
break;
case 0:
break; /* ignore naked '-' */
default:
while (**argv) {
switch (**argv) {
case 'v': /* verbose stderr, somewhat boring */
Vflag++;
break;
case 'c': /* print cost info */
Cflag++;
break;
case 'i': /* ignore case */
Iflag++;
break;
default:
fprintf(stderr, "%s: -%c: unknown flag\n", ProgName,
**argv);
exit(1);
}
(*argv)++;
}
}
}
Fcnt++;
if (*argv) {
Ifiles = argv;
freopen("/dev/null", "r", stdin);
}
if (!locname)
locname = local();
if (*locname == 0) {
locname = "lostinspace";
fprintf(stderr, "%s: using \"%s\" for local name\n",
ProgName, locname);
}
Home = addnode(locname); /* add home node */
Home->n_cost = 0; /* doesn't cost to get here */
yyparse(); /* read in link info */
hashanalyze();
while (Home->n_alias)
Home = Home->n_alias; /* bad practice, but conceivable */
mapit(); /* compute shortest paths */
exit(0);
}
badmagic(n)
{
#ifdef DEBUG
abort();
#else !DEBUG
exit(n);
#endif DEBUG
}
//GO.SYSIN DD main.c
echo mapit.c 1>&2
sed 's/^-//' >mapit.c <<'//GO.SYSIN DD mapit.c'
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)mapit.c 7.1 (down!honey) 85/08/06";
#endif lint
#include "def.h"
void reheap(), insert(), setpath(), swap();
node *min_node();
STATIC int Nheap;
mapit()
{
node *n, *next;
link *l;
Cost cost, setcost();
char *sbrk();
vprintf(stderr, "%d vertices, %d edges\n", Ncount, Lcount);
vprintf(stderr, "break is %ld after parsing\n", (long) sbrk(0));
/* use the hash Table for the heap */
/* TODO: coalesce the following functions into a single one */
pack(); /* remove holes in the Table */
amerge(); /* merge all alias links once and for all */
if (Linkout && *Linkout) /* dump cheapest links */
showlinks();
if (Graphout && *Graphout) /* dump the edge list */
dumpgraph();
while (Home->n_alias)
Home = Home->n_alias;
dehash(Home);
Home->n_path = strsave("%s");
insert(Home);
/*
* main mapping loop.
* assertion: no alias can ever appear in the heap. 'struth.
*/
while ((n = min_node()) != 0) {
printit(n);
/*
* if reached by a gatewayed net, discourage further links.
* this has some relevance to common carriers and the FCC ...
*/
if (n->n_flag & GATEWAYIN)
n->n_cost += 2* DEFCOST;
/* add children to heap */
for (l = n->n_link; l != 0; l = l->l_next) {
next = l->l_to;
while (next->n_alias)
next = next->n_alias;
if (next->n_flag & MAPPED)
continue;
dehash(next);
cost = setcost(n, l, next);
if (next->n_cost == 0) { /* first time */
next->n_cost = cost;
insert(next);
} else if (cost < next->n_cost) { /* cheaper route */
next->n_cost = cost;
reheap(next);
} else /* lose lose */
continue;
/* note whether we got here via a gatewayed net */
if (DEADNET(n))
next->n_flag |= GATEWAYIN;
else
next->n_flag &= ~GATEWAYIN;
setpath(n, next, l);
free((char *) l);
}
/* done with this node forever -- free as much as possible */
free((char *) n->n_path); /* absolutely free ... */
free((char *) n->n_name);
/* expunge aliases */
for (next = n->n_aliaslink; next; next = next->n_aliaslink) {
dehash(next);
Table[next->n_tloc] = 0;
next->n_tloc = 0;
free((char *) next->n_name);
}
}
vprintf(stderr, "break is %ld at after mapping\n", (long) sbrk(0));
if (Nheap != 0) {
fprintf(stderr, "%s: null entry found in heap\n", ProgName);
badmagic(1);
}
if (Hashpart < Tabsize) {
fprintf(stderr, "You can't get there from here:\n");
while (Hashpart < Tabsize) {
n = Table[Hashpart++];
if (n->n_alias)
continue; /* primary hosts only */
fprintf(stderr, "\t%s", n->n_name);
if (n->n_aliaslink) {
fprintf(stderr, " (alias %s", n->n_aliaslink->n_name);
n = n->n_aliaslink;
while (n = n->n_aliaslink)
fprintf(stderr, ", %s", n->n_name);
putc(')', stderr);
}
putc('\n', stderr);
}
}
}
STATIC Cost
setcost(n, l, next)
register node *n;
register link *l;
node *next;
{
register Cost cost;
cost = n->n_cost + l->l_cost; /* fundamental cost */
/*
* heuristics:
* charge for getting out of a dead host.
* charge for getting in to a dead net
* unless the link cost is non-zero (gateway).
* charge for a dead link.
* discourage mixing of left and right syntax.
*/
if ((n->n_flag & (NNET | NDEAD)) == NDEAD)
cost += INF/2; /* dead host */
if (DEADNET(next) && l->l_cost == 0)
cost += INF/2; /* dead net, not gateway */
if (l->l_flag & LDEAD)
cost += INF/2; /* dead link */
if ((n->n_flag & HASLEFT) && (NETDIR(l) == LRIGHT))
cost += DEFCOST; /* mix */
if ((n->n_flag & HASRIGHT) && (NETDIR(l) == LLEFT))
cost += DEFCOST; /* mix */
return(cost);
}
/*
* heap implementation of priority queue.
*/
STATIC void
insert(n)
node *n;
{
int i, parent;
Table[n->n_tloc] = 0;
if (Table[Nheap+1] != 0) {
fprintf(stderr, "%s: heap error in insert\n", ProgName);
badmagic(1);
}
if (Nheap++ == 0) {
Table[1] = n;
n->n_tloc = 1;
return;
}
/* insert at the end and percolate up */
Table[Nheap] = n;
n->n_tloc = Nheap;
for (i = Nheap; i > 1; i = parent) {
if (Table[i] == 0) {
fprintf(stderr, "%s: heap error in insert\n", ProgName);
badmagic(1);
}
parent = i / 2;
if (Table[i]->n_cost < Table[parent]->n_cost)
swap(i, parent);
}
return;
}
STATIC node *
min_node()
{
node *rval;
int i;
if (Nheap == 0)
return(0);
rval = Table[1]; /* return this one */
/* move last entry into root, percolate down */
Table[1] = Table[Nheap];
Table[1]->n_tloc = 1;
Table[Nheap] = 0;
if (--Nheap == 0)
return(rval);
i = 1;
for (;;) {
/* swap with smaller child (if larger than same) */
int child;
child = i * 2;
if (child > Nheap)
break;
if (child < Nheap) /* right child exists? */
if (Table[child]->n_cost > Table[child+1]->n_cost)
child++;
if (Table[i]->n_cost > Table[child]->n_cost)
swap(i, child);
i = child;
}
return(rval);
}
STATIC void
swap(i, j)
{
node *temp;
temp = Table[i];
Table[i] = Table[j];
Table[j] = temp;
Table[j]->n_tloc = j;
Table[i]->n_tloc = i;
}
/* "percolate" node n up the heap by exchanging with the parent */
STATIC void
reheap(n)
node *n;
{
int loc, parent;
Cost cost;
cost = n->n_cost;
for (loc = n->n_tloc; loc != 1; loc = parent) {
parent = loc / 2;
if (cost >= Table[parent]->n_cost)
return;
swap(loc, parent);
}
}
STATIC void
setpath(prev, next, l)
node *prev, *next;
link *l;
{
char pathbuf[BUFSIZ], hostbuf[BUFSIZ], *hptr;
char netchar, netdir;
netchar = NETCHAR(l);
netdir = NETDIR(l);
/* undo settings from earlier calls */
if (next->n_path)
free((char *) next->n_path); /* absolutely free ... */
if (prev->n_flag & ATSIGN)
next->n_flag |= ATSIGN;
else
next->n_flag &= ~ATSIGN;
if (prev->n_flag & HASLEFT)
next->n_flag |= HASLEFT;
else
next->n_flag &= ~HASLEFT;
if (prev->n_flag & HASRIGHT)
next->n_flag |= HASRIGHT;
else
next->n_flag &= ~HASRIGHT;
if (next->n_flag & NNET) {
/*
* grumble. when climbing onto a "domain" style network,
* append .netname. but we can't do it 'til later ...
*
* unless, of course, we are in transit from another
* domain style network, in which case we tack the
* predecessor's name onto the next domain.
*
* e.g., prev = arpa, next = csnet. change next->n_name
* to csnet.arpa. but first wipe out any previous
* domain on next. this is too gross for words.
*/
if (l->l_flag & LDOMAIN) {
next->n_flag |= NDOMAIN;
if (prev->n_flag & NDOMAIN) {
/*
* clean out dots in next->n_name -- they're
* no longer valid. N.B.: we are guaranteed
* that next is not an alias
*/
hptr = index(next->n_name, '.');
if (hptr)
*hptr = 0;
sprintf(hostbuf, "%s.%s", next->n_name, prev->n_name);
free(next->n_name);
next->n_name = strsave(hostbuf);
}
} else
next->n_flag &= ~NDOMAIN;
next->n_path = strsave(prev->n_path);
return;
}
/* do it by hand instead of sprintf-ing -- foo on '%' */
if (netdir == LLEFT) {
/* e.g., host!%s */
next->n_flag |= HASLEFT;
strcpy(hostbuf, next->n_name);
hptr = hostbuf + strlen(hostbuf);
if (prev->n_flag & NDOMAIN) {
*hptr++ = '.';
strcpy(hptr, prev->n_name);
hptr += strlen(hptr);
}
*hptr++ = netchar;
if (netchar == '%')
*hptr++ = netchar;
*hptr++ = '%';
*hptr++ = 's';
*hptr = 0;
} else {
/* e.g., %s@host, but watch out for the magic @-% conversion */
next->n_flag |= HASRIGHT;
if (netchar == '@') {
next->n_flag |= ATSIGN;
if (prev->n_flag & ATSIGN)
netchar = '%'; /* shazam? shaman? */
}
hptr = hostbuf;
*hptr++ = '%';
*hptr++ = 's';
*hptr++ = netchar;
if (netchar == '%')
*hptr++ = '%';
strcpy(hptr, next->n_name);
if (prev->n_flag & NDOMAIN) {
hptr += strlen(hptr);
*hptr++ = '.';
strcpy(hptr, prev->n_name);
}
}
/* this would be an sprintf were it not for the %'s. feh. */
pathprintf(pathbuf, prev->n_path, hostbuf);
next->n_path = strsave(pathbuf);
}
dehash(n)
node *n;
{
if (n->n_flag & DEHASH)
return;
Table[Hashpart]->n_tloc = n->n_tloc;
Table[n->n_tloc] = Table[Hashpart];
Table[Hashpart] = n;
n->n_flag |= DEHASH;
n->n_tloc = Hashpart++;
}
pathprintf(buf, path, host)
char *buf, *path, *host;
{
for ( ; *buf = *path; path++) {
if (*path == '%') {
switch(path[1]) {
case 's':
strcpy(buf, host);
buf += strlen(buf);
path++;
break;
case '%':
*++buf = *++path;
buf++;
break;
}
} else
buf++;
}
}
printit(n)
node *n;
{
char *path = n->n_path;
Cost cost = n->n_cost;
for ( ; n; n = n->n_aliaslink) {
n->n_flag |= MAPPED;
if (n->n_flag & (NNET | ISPRIVATE | COLLISION))
continue;
if (Cflag)
printf("%ld\t", (long) cost);
printf("%s\t%s\n", n->n_name, path);
}
}
//GO.SYSIN DD mapit.c
echo mapaux.c 1>&2
sed 's/^-//' >mapaux.c <<'//GO.SYSIN DD mapaux.c'
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)mapaux.c 7.1 (down!honey) 85/08/06";
#endif lint
#include "def.h"
void pack();
void
pack()
{
int hole, next;
/* find first "hole " */
for (hole = Tabsize - 1; hole >= 0 && Table[hole] != 0; --hole)
;
/* repeatedly move next filled entry into last hole */
for (next = hole - 1; next >= 0; --next) {
if (Table[next] != 0) {
Table[hole] = Table[next];
Table[hole]->n_tloc = hole;
Table[next] = 0;
while (Table[--hole] != 0) /* find next hole */
;
}
}
Hashpart = hole + 1;
}
amerge()
{
node *n, *a;
int i;
for (i = Hashpart; i < Tabsize; i++) {
n = Table[i];
if (n == 0) /* impossible, but ... */
continue;
for (a = n->n_alias; a; a = a->n_alias) {
a->n_link = lmerge(a->n_link, n->n_link);
n->n_link = 0;
n = a;
}
}
}
STATIC FILE *Gstream;
dumpgraph()
{
int i;
node *n;
if ((Gstream = fopen(Graphout, "w")) == NULL) {
fprintf(stderr, "%s: ", ProgName);
perror(Graphout);
}
untangle(); /* untangle net cycles for proper output */
for (i = Hashpart; i < Tabsize; i++) {
n = Table[i];
if (n == 0)
continue; /* impossible, but ... */
if (n->n_alias)
continue; /* primaries only (wrong?) */
/* a minor optimization ... */
if (n->n_link == 0)
continue;
/* pathparse doesn't need these */
if (n->n_flag & NNET)
continue;
dumpnode(n);
}
}
dumpnode(from)
node *from;
{
node *to;
link *l;
char netbuf[BUFSIZ], *nptr = netbuf;
for (l = from->n_link ; l; l = l->l_next) {
to = l->l_to;
while (to->n_alias)
to = to->n_alias; /* get to primary */
if (from == to)
continue; /* oops -- it's me! */
if ((to->n_flag & NNET) == 0) {
/* host -> host -- print host>host */
if (l->l_cost == INF)
continue; /* phoney link */
fputs(from->n_name, Gstream);
putc('>', Gstream);
fputs(to->n_name, Gstream);
putc('\n', Gstream);
} else {
/* host -> net -- just cache it for now */
while (to->n_root && to != to->n_root)
to = to->n_root;
*nptr++ = ',';
strcpy(nptr, to->n_name);
nptr += strlen(nptr);
}
}
/* dump nets */
if (nptr != netbuf) {
/* nets -- print host@\tnet,net, ... */
*nptr = 0;
fputs(from->n_name, Gstream);
putc('@', Gstream);
*netbuf = '\t'; /* insert tab by killing initial ',' */
fputs(netbuf, Gstream); /* skip initial ',' */
putc('\n', Gstream);
}
}
/*
* remove cycles in net definitions.
*
* depth-first search
*
* for each net, run dfs on its neighbors (nets only). if we return to
* a visited node, that's a net cycle. mark the cycle with a pointer
* in the n_root field (which gets us closer to the root of this
* portion of the dfs tree).
*/
untangle()
{
int i;
node *n;
for (i = Hashpart; i < Tabsize; i++) {
n = Table[i];
if (n == 0 || (n->n_flag & NNET) == 0 || n->n_root)
continue;
dfs(n);
}
}
dfs(n)
node *n;
{
link *l;
node *next;
n->n_flag |= INDFS;
n->n_root = n;
for (l = n->n_link; l; l = l->l_next) {
next = l->l_to;
if ((next->n_flag & NNET) == 0)
continue;
if ((next->n_flag & INDFS) == 0) {
dfs(next);
if (next->n_root != next)
n->n_root = next->n_root;
} else
n->n_root = next->n_root;
}
n->n_flag &= ~INDFS;
}
showlinks()
{
link *l;
node *n;
int i;
FILE *estream;
if ((estream = fopen(Linkout, "w")) == 0)
return;
for (i = Hashpart; i < Tabsize; i++) {
n = Table[i];
if (n == 0) /* impossible, but ... */
continue;
if (l = n->n_link) {
fprintf(estream, "%s\t%s(%d)", n->n_name,
l->l_to->n_name,
l->l_cost ? l->l_cost : DEFCOST);
for (l = l->l_next; l; l = l->l_next)
fprintf(estream, ",\n\t%s(%d)", l->l_to->n_name,
l->l_cost ? l->l_cost : DEFCOST);
fputc('\n', estream);
}
}
(void) fclose(estream);
}
//GO.SYSIN DD mapaux.c
echo mem.c 1>&2
sed 's/^-//' >mem.c <<'//GO.SYSIN DD mem.c'
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)mem.c 7.1 (down!honey) 85/08/06";
#endif lint
#include "def.h"
link *
newlink()
{
register link *rval;
if ((rval = (link * ) malloc(sizeof(link))) == 0)
nomem();
strclear((char *) rval, sizeof(link)); /* fresh as a daisy */
Lcount++;
return(rval);
}
node *
newnode()
{
register node *rval;
if ((rval = (node * ) malloc(sizeof(node))) == 0)
nomem();
strclear((char *) rval, sizeof(node)); /* fresh as a daisy */
Ncount++;
return(rval);
}
char *
strsave(s)
register char *s;
{
register char *r;
if ((r = malloc(strlen(s) + 1)) == 0)
nomem();
(void) strcpy(r, s);
return(r);
}
#ifndef strclear
void
strclear(dst, len)
register char *dst;
register int len;
{
while (--len >= 0)
*dst++ = 0;
}
#endif strclear
node **
newtable(size)
register int size;
{
register node **rval;
if ((rval = (node **) malloc(size * sizeof(*rval))) == 0)
nomem();
strclear((char *) rval, size * sizeof(*rval));
return(rval);
}
freetable(t, size)
register node **t;
{
#ifdef MYMALLOC
addtoheap((char *) t, (long) (size * sizeof(*t)));
#else !MYMALLOC
free((char *) t);
#endif MYMALLOC
}
nomem()
{
fprintf(stderr, "%s: Out of memory\n", ProgName);
badmagic(1);
}
#ifdef MYMALLOC
typedef struct heap heap;
struct heap {
heap *h_next;
long h_size;
};
STATIC heap *Heap; /* not to be confused with a priority queue */
addtoheap(p, size)
register char *p;
register long size;
{
register heap *hptr = (heap *) p;
hptr->h_next = Heap;
hptr->h_size = size;
Heap = hptr;
}
char *
mymalloc(n)
register int n;
{
static long size;
static char *mem;
register char *rval;
register heap *hptr;
if (n > BUFSIZ)
rval = memget(n);
else {
#ifdef ALIGN
int adjustment;
adjustment = align(mem);
mem += adjustment;
size -= adjustment;
#endif ALIGN
if (n > size) {
/* look in the heap -- already aligned */
if (Heap) {
if (Heap->h_size >= size) {
mem = (char *) Heap;
size = Heap->h_size;
Heap = Heap->h_next;
} else {
for (hptr = Heap; hptr->h_next; hptr = hptr->h_next)
if (hptr->h_next->h_size >= size)
break;
if (hptr->h_next) {
mem = (char *) hptr->h_next;
size = hptr->h_next->h_size;
hptr->h_next = hptr->h_next->h_next;
}
}
} else {
mem = memget(BUFSIZ);
size = BUFSIZ;
}
}
rval = mem;
mem += n;
size -= n;
}
return(rval);
}
myfree(s)
char *s;
{
#ifdef lint
s = s;
#endif lint
}
#ifdef ALIGN
char *
memget(n)
register int n;
{
register char *rval;
register int adjustment = 0;
adjustment = align(sbrk(0));
rval = sbrk(n + adjustment);
if (rval <= 0)
return(0);
return(rval + adjustment);
}
align(n)
register char *n;
{
register int abits; /* alignment bits */
register int adjustment = 0;
abits = (int) n & ~(0xff << ALIGN) & 0xff;
if (abits != 0)
adjustment = (1 << ALIGN) - abits;
return(adjustment);
}
#endif ALIGN
#endif MYMALLOC
//GO.SYSIN DD mem.c
echo parse.y 1>&2
sed 's/^-//' >parse.y <<'//GO.SYSIN DD parse.y'
%{
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)parse.y 7.1 (down!honey) 85/08/06";
#endif lint
#include "def.h"
%}
%union {
node *y_node;
Cost y_cost;
char y_net;
char *y_name;
struct {
node *ys_node;
Cost ys_cost;
char ys_net;
char ys_dir;
} y_s;
}
%type <y_s> site
%type <y_node> links aliases plist network nlist nsite host
%type <y_cost> cost cexpr
%type <y_net> netchar
%token <y_node> SITE HOST
%token <y_cost> COST
%token <y_net> NET
%token NL PRIVATE
%left '+' '-'
%left '*' '/'
%%
map : /* empty */
| map NL
| map links NL
| map aliases NL
| map network NL
| map private NL
| error NL
;
host : HOST
| PRIVATE {$$ = addnode("private");}
;
private : PRIVATE '{' {Scanstate = PRIVATING;} plist {Scanstate = OTHER;} '}'
;
plist : SITE {$1->n_flag |= ISPRIVATE;}
| plist ',' SITE {$3->n_flag |= ISPRIVATE;}
| plist ',' /* admit this benign error */
;
network : host '=' nlist cost
{fixnet($1, $3, $4, DEFNET, DEFDIR);}
| host '=' netchar nlist cost
{fixnet($1, $4, $5, $3, LRIGHT);}
| host '=' nlist netchar cost
{fixnet($1, $3, $5, $4, LLEFT);}
;
nlist : '{' nsite '}' {$$ = $2;}
;
nsite : SITE
| nsite ',' SITE {
/* be careful not to put anything on the list twice */
if ($3->n_net == 0) {
$3->n_net = $1;
$$ = $3;
}
}
| nsite ',' /* admit this benign error */
;
aliases : host '=' SITE {alias($1, $3);}
| aliases ',' SITE {alias($1, $3);}
| aliases ',' /* admit this benign error */
;
links : host site cost {
addlink($1, $2.ys_node, $3, $2.ys_net, $2.ys_dir);
/*
* give a default path for the return link.
* this is wrong, but it's soothes the masses,
* who insist on putting error output in the
* output. who said vox populi, vox Dei?
*/
addlink($2.ys_node, $1, INF, $2.ys_net, $2.ys_dir);
}
| links ',' site cost {
addlink($1, $3.ys_node, $4, $3.ys_net, $3.ys_dir);
/* ditto */
addlink($3.ys_node, $1, INF, $3.ys_net, $3.ys_dir);
}
| links ',' /* admit this benign error */
;
site : SITE {
$$.ys_node = $1;
$$.ys_net = DEFNET;
$$.ys_dir = DEFDIR;
}
| netchar SITE {
$$.ys_node = $2;
$$.ys_net = $1;
$$.ys_dir = LRIGHT;
}
| SITE netchar {
$$.ys_node = $1;
$$.ys_net = $2;
$$.ys_dir = LLEFT;
}
;
cost : /* empty -- cost is always optional */
{$$ = DEFCOST;}
| '(' {Scanstate = COSTING;} cexpr {Scanstate = OTHER;} ')'
{$$ = $3;}
;
cexpr : COST
| '(' cexpr ')' {$$ = $2;}
| cexpr '+' cexpr {$$ = $1 + $3;}
| cexpr '-' cexpr {$$ = $1 - $3;}
| cexpr '*' cexpr {$$ = $1 * $3;}
| cexpr '/' cexpr {
if ($3 == 0)
yyerror("zero term in divison\n");
else
$$ = $1 / $3;
}
;
netchar : NET /* normal network operator */
| NET NET { /* for "domains" */
if ($1 != $2)
yyerror("invalid domain specifier\n");
else
$$=($1 | 0200);
}
;
%%
node *revnetlist();
yyerror(s)
char *s;
{
/* a concession to bsd error(1) */
if (Cfile)
fprintf(stderr, "\"%s\", ", Cfile);
else
fprintf(stderr, "%s: ", ProgName);
fprintf(stderr, "line %d: %s\n", Lineno, s);
}
/*
* patch in the costs of getting on/off the network.
*
* for each network member on netlist, add links:
* network -> member cost = parameter;
* member -> network cost = 0.
* note that a network can have varying costs to its members, by suitable
* multiple declarations. this is a feechur.
*/
fixnet(netnode, netlist, cost, netchar, netdir)
register node *netnode, *netlist;
Cost cost;
char netchar, netdir;
{
register node *nextnet;
netnode->n_flag |= NNET;
/*
* avoid quadratic behavior in addlink(), by reversing net list.
* this is cheap, and not necessarily effective, but in practice,
* it cuts the cost of addlink() by three. can you believe that?!?
*/
netlist = revnetlist(netlist);
/* now insert the links */
for ( ; netlist; netlist = nextnet) {
/* network -> member */
(void) addlink(netnode, netlist, cost, netchar, netdir);
/* member -> network */
(void) addlink(netlist, netnode, (Cost) 0, netchar, netdir);
nextnet = netlist->n_net;
netlist->n_net = 0; /* clear for later use */
}
}
STATIC node *
revnetlist(n)
node *n;
{
register node *pred, *current, *succ;
if ((pred = n) == 0 || (current = n->n_net) == 0)
return(n);
pred->n_net = 0;
while (current) {
succ = current->n_net;
current->n_net = pred;
pred = current;
current = succ;
}
return(pred);
}
//GO.SYSIN DD parse.y
echo yylex.c 1>&2
sed 's/^-//' >yylex.c <<'//GO.SYSIN DD yylex.c'
#ifndef lint
static char *sccsid = "@(#)yylex.c 7.1 (down!honey) 85/08/06";
#endif lint
#include "def.h"
#include "y.tab.h"
extern YYSTYPE yylval;
#define LBRACE '{'
#define RBRACE '}'
#define LPAREN '('
#define RPAREN ')'
#define QUOTE '"'
Cost isacost();
int
yylex()
{
int c;
Cost cost;
char buf[BUFSIZ], errbuf[128];
tailrecursion:
if (feof(stdin) && yywrap())
return(EOF);
if ((c = getchar()) == EOF)
goto tailrecursion;
while (c == ' ' || c == '\t')
c = getchar();
if (c == '\n') {
Lineno++;
c = getchar();
if (c == ' ' || c == '\t')
goto tailrecursion;
ungetc(c, stdin);
Scanstate = NEWLINE;
return(NL);
}
if (c == '#') {
while ((c = getchar()) != '\n')
if (c == EOF)
goto tailrecursion;
ungetc(c, stdin);
goto tailrecursion;
}
ungetc(c, stdin);
switch(Scanstate) {
case COSTING:
if (isdigit(c)) {
cost = 0;
for (c = getchar(); isdigit(c); c = getchar())
cost = (cost * 10) + c - '0';
ungetc(c, stdin);
yylval.y_cost = cost;
return(COST);
}
if (getword(buf) == 0) {
if ((yylval.y_cost = isacost(buf)) == 0) {
sprintf(errbuf, "unknown cost (%s), using default", buf);
yyerror(errbuf);
yylval.y_cost = DEFCOST;
}
return(COST);
}
return(getchar()); /* can't be EOF */
case NEWLINE:
Scanstate = OTHER;
if (getword(buf) != 0)
return(getchar()); /* can't be EOF */
if (c != '"' && strcmp(buf, "private") == 0)
return(PRIVATE);
yylval.y_node = addnode(buf);
return(HOST);
case PRIVATING:
if (getword(buf) == 0) {
yylval.y_node = addprivate(buf);
return(SITE);
}
return(getchar()); /* can't be EOF */
}
if (getword(buf) == 0) {
yylval.y_node = addnode(buf);
return(SITE);
}
c = getchar(); /* can't be EOF */
if (index(Netchars, c)) {
yylval.y_net = c;
return(NET);
}
return(c);
}
getword(str)
char *str;
{
int c;
c = getchar();
if (c == QUOTE) {
for ( ; (*str = getchar()) != '"'; str++) {
if (*str == '\n') {
yyerror("newline in quoted string\n");
ungetc('\n', stdin);
return(-1);
}
}
*str = 0;
return(0);
}
/* host name must start with alphanumeric or _ */
if (!isalnum(c) && c != '_') {
ungetc(c, stdin);
return(-1);
}
yymore:
do {
*str++ = c;
c = getchar();
} while (isalnum(c) || c == '.' || c == '_');
if (c == '-' && Scanstate != COSTING)
goto yymore;
ungetc(c, stdin);
*str = 0;
return(0);
}
static struct ctable {
char *cname;
Cost cval;
} ctable[] = {
/*
* this list is searched sequentially (with strcmps!).
* it is too long. (they are ordered by frequency of
* appearance in a "typical" dataset.)
*
* adding a 0 cost token breaks isacost(). don't do it.
*/
{"DEMAND", 300},
{"DAILY", 5000},
{"DIRECT", 200},
{"EVENING", 1800},
{"LOCAL", 25},
{"LOW", 5}, /* baud rate penalty */
{"HOURLY", 500},
{"POLLED", 5000},
{"DEDICATED", 95},
{"WEEKLY", 30000},
{"DEAD", INF/2},
{"HIGH", -5}, /* baud rate bonus */
/* the remainder are reviled */
{"ARPA", 100},
{"DIALED", 300},
{"A", 300},
{"B", 500},
{"C", 1800},
{"D", 5000},
{"E", 30000},
{"F", INF/2},
0
};
STATIC Cost
isacost(buf)
char *buf;
{
struct ctable *ct;
for (ct = ctable; ct->cname; ct++)
if (strcmp(buf, ct->cname) == 0)
return(ct->cval);
return((Cost) 0);
}
yywrap()
{
char errbuf[100];
fixprivate(); /* munge private host definitions */
if (Ifiles == 0)
return(1);
fclose(stdin);
while (*Ifiles) {
Lineno = 1;
Fcnt++;
if (fopen((Cfile = *Ifiles++), "r"))
return(0);
sprintf(errbuf, "%s: %s", ProgName, Cfile);
perror(errbuf);
}
return(1);
}
//GO.SYSIN DD yylex.c
echo makedb.c 1>&2
sed 's/^-//' >makedb.c <<'//GO.SYSIN DD makedb.c'
/* pathalias -- by steve bellovin, as told to peter honeyman */
#ifndef lint
static char *sccsid = "@(#)makedb.c 7.1 (down!honey) 85/08/06";
#endif lint
#include <stdio.h>
#include "config.h"
typedef struct {
char *dptr;
int dsize;
} datum;
char *Ofile = ALIASDB, *ProgName, *Fname;
int Nets, Paths, Edges;
char *strany();
#define USAGE "makedb [-o dbname] [file ...]"
main(argc, argv)
char *argv[];
{ int verbose = 0, append = 0;
char *ofptr;
FILE *dbstream;
ProgName = argv[0];
--argc;
for ( ; *++argv && **argv == '-'; --argc) {
(*argv)++;
switch(**argv) {
case 'o': /* dbm output file */
Ofile = *++argv;
--argc;
if (*Ofile == 0) {
usage();
exit(1);
}
if ((ofptr = rindex(Ofile, '/')) != 0)
ofptr++;
else
ofptr = Ofile;
if (strlen(ofptr) > 10) {
ofptr[10] = 0;
fprintf(stderr, "%s: using %s for db output\n",
ProgName, Ofile);
}
break;
case 'v': /* chatty */
verbose++;
break;
case 'a': /* append mode */
append++;
break;
default:
fprintf(stderr, "%s: -%s: unknown flag\n", ProgName, *argv);
usage();
exit(1);
break;
}
}
if (append == 0 && dbmfile(Ofile) < 0) {
perror_(Ofile);
exit(1);
}
if (dbminit(Ofile) < 0) {
perror_(Ofile);
exit(1);
}
if (argc == 0) {
makedb(stdin);
} else {
while (argc > 0) {
if ((dbstream = fopen(*argv, "r")) == NULL) {
perror_(*argv);
} else {
Fname = *argv;
makedb(dbstream);
fclose(dbstream);
}
--argc;
argv++;
}
}
if (verbose)
fprintf(stderr, "%d paths, %d edges, %d nets\n", Paths, Edges, Nets);
}
dbmfile(dbmf)
char *dbmf;
{ int fd;
char buf[BUFSIZ];
sprintf(buf, "%s.dir", dbmf);
fd = creat(buf, 0666);
if (fd < 0)
return(-1);
close(fd);
sprintf(buf, "%s.pag", dbmf);
fd = creat(buf, 0666);
if (fd < 0)
return(-1);
close(fd);
return(0);
}
makedb(stream)
FILE *stream;
{ char *op, line[BUFSIZ], *end;
datum key, val;
/*
* keys and values are 0 terminated. this wastes time and
* (disk) space, and is generally stupid. it does buy
* simplicity and backwards compatibility.
*/
key.dptr = line;
while (fgets(line, sizeof(line), stream) != NULL) {
end = line + strlen(line);
end[-1] = 0; /* kill newline */
op = index(line, '\t');
if (op != 0) {
*op++ = 0;
key.dsize = op - line; /* 0 terminated */
val.dptr = op;
val.dsize = end - op; /* 0 terminated */
} else {
key.dsize = end - line; /* 0 terminated */
val.dptr = "\0"; /* why must i do this? */
val.dsize = 1;
}
if (store(key, val) < 0)
perror_(Ofile);
}
}
perror_(str)
char *str;
{
fprintf(stderr, "%s: ", ProgName);
perror(str);
}
usage()
{
fputs(USAGE, stderr);
}
//GO.SYSIN DD makedb.c
exit