Subject: v12i001: Pathalias, version 9, Part01/02 Newsgroups: comp.sources.unix Sender: sources Approved: rs@uunet.UU.NET Submitted-by: honey@CITI.UMICH.EDU (Peter Honeyman) Posting-number: Volume 12, Issue 1 Archive-name: pathalias9/part01 [ This is the latest and greatest pathalias, and other tools. It may well be the last one peter ever works on, judging from his off-line remarks... :-) This version has had several bugs fixed, and has been tested on BSD, Sun, 3B, SysV, Mac, etc. MOST IMPORTANTLY: it has several new features, and additions to the input syntax, that you will need for all future UUCP maps. Finally, had I an irrelevant axe to grind, I'd point out that this code has no copyright and is in the public domain. --r$ ] #! /bin/sh # This is a shell archive. Remove anything before this line, then unpack # it by saving it into a file and typing "sh file". To overwrite existing # files, type "sh file -c". You can also feed this as standard input via # unshar, or by typing "sh CHANGES <<'END_OF_CHANGES' X-- mod.sources, 10/87 -- version 9 XTerminal edges and domains ( syntax and -D option). XDead hosts and edges in the input stream. XEmpty private list ends scope of privates. XFirst hop cost in output (-f option). XPenalize deprecated hosts (-a option). X X-- mod.sources, 4.3bsd, 1/86 -- version 8 XImproved alias treatment. XRoutes to domain gateways. XLeading dot in name implies domain. XLink/host tracing (-t option). XUse getopt(). X X-- mod.sources, 8/85 -- version 7 XPrivate hosts documented. XHomegrown scanner -- it was true what they said about lex. XMakedb. XDomains and gateways. XDEAD back link. X X-- net.sources, 1/85 -- version 6 XNo ! in dbm key. XNetwork character must be one of !@%: -- dot is dead. XPrivate hosts. XDiscourage hybrid addresses. XMagic @ <-> % rule. X X-- 1983-1984 -- version 5 XReverse sense of the -c (cost) flag. XUse cheapest among duplicate links. XElide network names in output. X X-- epoch (smb version) -- versions 1-4 END_OF_CHANGES if test 941 -ne `wc -c MANIFEST <<'END_OF_MANIFEST' X File Name Archive # Description X----------------------------------------------------------- X CHANGES 1 X MANIFEST 1 This shipping list X Makefile 1 X README 1 X addlink.c 1 X addnode.c 2 X arpa-privates 1 X arpatxt.c 2 X config.h 1 X def.h 1 X local.c 1 X main.c 1 X make.honey 1 X makedb.c 1 X mapaux.c 1 X mapit.c 2 X mem.c 1 X parse.y 2 X pathalias.1 2 X printit.c 1 END_OF_MANIFEST if test 714 -ne `wc -c Makefile <<'END_OF_Makefile' X#!/bin/make -f X# pathalias -- by steve bellovin, as told to peter honeyman X X### configuration section X### X# if you can't or don't intend to use dbm files, X# don't bother with DBM or makedb XDBM = -ldbm X# or if you roll your own ... X# DBM = dbm.o X### X# where is getopt (if not in the c library)? X# GETOPT = getopt.o X### end of configuration section X X XCC = cc XCFLAGS = -O -DSTATIC=static XLDFLAGS = -s $(GETOPT) XYFLAGS = -d X XOBJ = addlink.o addnode.o local.o main.o mapit.o mapaux.o mem.o parse.o printit.o XHDRS = def.h config.h XCSRC = addlink.c addnode.c local.c main.c mapit.c mapaux.c mem.c printit.c XLSRC = $(CSRC) parse.c XSRC = $(CSRC) parse.y makedb.c arpatxt.c X Xpathalias: $(OBJ) X $(CC) $(OBJ) $(LDFLAGS) -o pathalias X Xall: pathalias makedb arpatxt X X$(OBJ): $(HDRS) X Xparse.c: parse.y $(HDRS) X $(YACC) $(YFLAGS) parse.y X mv y.tab.c parse.c X Xmakedb: makedb.o X $(CC) makedb.o $(LDFLAGS) $(DBM) -o makedb X Xmakedb.o: config.h X Xarpatxt: arpatxt.o X $(CC) arpatxt.o $(LDFLAGS) -o arpatxt X Xclean: X rm -f *.o y.tab.? parse.c X Xclobber: clean X rm -f pathalias makedb arpatxt X Xtags: $(SRC) $(HDRS) X ctags -w $(HDRS) $(SRC) X Xbundle: X @bundle README CHANGES pathalias.1 Makefile ${HDRS} ${SRC} X Xlint: $(LSRC) X lint $(CFLAGS) $(LSRC) X lint makedb.c X lint arpatxt.c X Xinstall: X @echo "install pathalias, makedb, arpatxt, and pathalias.1" X @echo "according to local conventions" END_OF_Makefile if test 1364 -ne `wc -c README <<'END_OF_README' XFrom citi!honey Sun Oct 4 23:30 EDT 1987 XDate: 04 Oct 1987 23:30 EDT XFrom: honey@citi.umich.edu XTo: whom it may concern XSubject: pathalias compilation instructions X Xedit config.h Xmake X Xif getopt is undefined, obtain a copy from usenet group Xcomp.sources.unix and adjust Makefile. X Xpathalias input is regularly published in usenet group comp.mail.maps. X X peter X Xps: pathalias, written by steve bellovin and peter honeyman, is in the X public domain, and may be used by any person or organization, in X any way and for any purpose. X Xpps: There is no warranty of merchantability nor any warranty of fit- X ness for a particular purpose nor any other warranty, either ex- X press or implied, as to the accuracy of the enclosed materials or X as to their suitability for any particular purpose. Accordingly, X the authors assume no responsibility for their use by the recipi- X ent. Further, the authors assume no obligation to furnish any X assistance of any kind whatsoever, or to furnish any additional X information or documentation. END_OF_README if test 1073 -ne `wc -c addlink.c <<'END_OF_addlink.c' X/* pathalias -- by steve bellovin, as told to peter honeyman */ X#ifndef lint Xstatic char *sccsid = "@(#)addlink.c 9.1 87/10/04"; X#endif /* lint */ X X#include "def.h" X X/* exports */ Xextern link *addlink(); Xextern void deadlink(), atrace(); Xextern int tracelink(); Xchar *Netchars = "!:@%"; /* sparse, but sufficient */ Xlong Lcount; /* how many edges? */ X X X/* imports */ Xextern int Tflag, Dflag; Xextern link *newlink(); Xextern node *addnode(); Xextern void yyerror(), die(); X X/* privates */ XSTATIC void netbits(), ltrace(), ltrprint(); Xstatic link *Trace[NTRACE]; Xstatic int Tracecount; X Xlink * Xaddlink(from, to, cost, netchar, netdir) X node *from; X register node *to; X Cost cost; X char netchar, netdir; X{ register link *l, *prev = 0; X X if (Tflag) X ltrace(from, to, cost, netchar, netdir); X /* X * maintain uniqueness for dead links (only). X */ X for (l = from->n_link; l; l = l->l_next) { X if (!(l->l_flag & LDEAD)) X break; X if (to == l->l_to) { X /* what the hell, use cheaper dead cost */ X if (cost < l->l_cost) { X l->l_cost = cost; X netbits(l, netchar, netdir); X } X return l; X } X prev = l; X } X X X /* allocate and link in the new link struct */ X l = newlink(); X if (cost != INF) /* ignore back links */ X Lcount++; X if (prev) { X l->l_next = prev->l_next; X prev->l_next = l; X } else { X l->l_next = from->n_link; X from->n_link = l; X } X X l->l_to = to; X l->l_cost = cost + from->n_cost; /* add penalty */ X if (netchar == 0) { X netchar = DEFNET; X netdir = DEFDIR; X } X netbits(l, netchar, netdir); X if (Dflag && ISADOMAIN(from) && !ISADOMAIN(to)) X l->l_flag |= LTERMINAL; X X return l; X} X Xvoid Xdeadlink(nleft, nright) X node *nleft, *nright; X{ link *l, *lhold = 0, *lprev, *lnext; X X /* DEAD host */ X if (nright == 0) { X nleft->n_flag |= NDEAD; /* DEAD host */ X return; X } X X /* DEAD link */ X X /* grab instances at head of nleft adjacency list */ X while ((l = nleft->n_link) != 0 && l->l_to == nright) { X nleft->n_link = l->l_next; /* disconnect */ X l->l_next = lhold; /* terminate */ X lhold = l; /* add to lhold */ X } X X /* move remaining instances */ X for (lprev = nleft->n_link; lprev && lprev->l_next; lprev = lprev->l_next) { X if (lprev->l_next->l_to == nright) { X l = lprev->l_next; X lprev->l_next = l->l_next; /* disconnect */ X l->l_next = lhold; /* terminate */ X lhold = l; X } X } X X /* check for emptiness */ X if (lhold == 0) { X addlink(nleft, nright, INF / 2, DEFNET, DEFDIR)->l_flag |= LDEAD; X return; X } X X /* reinsert deleted edges as DEAD links */ X for (l = lhold; l; l = lnext) { X lnext = l->l_next; X addlink(nleft, nright, l->l_cost, NETCHAR(l), NETDIR(l))->l_flag |= LDEAD; X freelink(l); X } X} X XSTATIC void Xnetbits(l, netchar, netdir) X register link *l; X char netchar, netdir; X{ X l->l_flag &= ~LDIR; X l->l_flag |= netdir; X l->l_netop = netchar; X} X Xint Xtracelink(arg) X char *arg; X{ char *bang; X link *l; X X if (Tracecount >= NTRACE) X return -1; X l = newlink(); X bang = index(arg, '!'); X if (bang) { X *bang = 0; X l->l_to = addnode(bang+1); X } else X l->l_to = 0; X X l->l_from = addnode(arg); X Trace[Tracecount++] = l; X return 0; X} X XSTATIC void Xltrace(from, to, cost, netchar, netdir) X node *from, *to; X Cost cost; X char netchar, netdir; X{ link *l; X int i; X X for (i = 0; i < Tracecount; i++) { X l = Trace[i]; X /* overkill, but you asked for it! */ X if ((l->l_to == 0 X && (from == (node *) l->l_from || to == (node *) l->l_from)) X || (from == (node *) l->l_from && to == l->l_to) X || (to == (node *) l->l_from && from == l->l_to)) { X ltrprint(from, to, cost, netchar, netdir); X return; X } X } X} X X/* print a trace item */ XSTATIC void Xltrprint(from, to, cost, netchar, netdir) X node *from, *to; X Cost cost; X char netchar; X char netdir; X{ char buf[256], *bptr = buf; X X strcpy(bptr, from->n_name); X bptr += strlen(bptr); X *bptr++ = ' '; X if (netdir == LRIGHT) /* @% */ X *bptr++ = netchar; X strcpy(bptr, to->n_name); X bptr += strlen(bptr); X if (netdir == LLEFT) /* !: */ X *bptr++ = netchar; X sprintf(bptr, "(%ld)", cost); X yyerror(buf); X} X Xvoid Xatrace(n1, n2) X node *n1, *n2; X{ link *l; X int i; X char buf[256]; X X for (i = 0; i < Tracecount; i++) { X l = Trace[i]; X if (l->l_to == 0 && ((node *) l->l_from == n1 || (node *) l->l_from == n2)) { X sprintf(buf, "%s = %s", n1->n_name, n2->n_name); X yyerror(buf); X return; X } X } X} X X#define EQ(n1, n2) strcmp(n1->n_name, n2->n_name) == 0 Xmaptrace(from, to) X register node *from, *to; X{ register link *l; X register int i; X X for (i = 0; i < Tracecount; i++) { X l = Trace[i]; X if (l->l_to == 0) { X if (EQ(from, l->l_from) || EQ(to, l->l_from)) X return 1; X } else if (EQ(from, l->l_from) && EQ(to, l->l_to)) X return 1; X } X return 0; X} END_OF_addlink.c if test 4693 -ne `wc -c arpa-privates <<'END_OF_arpa-privates' X### X#host map file ([map file ...] for unregistered hosts) X# Xabbott usa.ca Xabel usa.ca Xachilles usa.nj.a Xacorn gbr Xadam [usa.il.a] Xadams swe Xadmin [usa.ut] Xads [usa.ca] Xai gbr Xalamo usa.tx Xalpha usa.in Xamc usa.wa Xames usa.ca (amazingly ...) Xamon swe Xamos [usa.ca?] Xanimal usa.nj.a Xanubis usa.il Xapollo usa.ma Xaramis usa.nj Xargus usa.nj Xariadne grc Xarthur [usa.oh] Xasgard usa.or Xastro [usa.ma] Xathena usa.or Xatlantis usa.nj.a Xatlas usa.oh.a Xaurora [usa.ca] Xb21 deu Xbach [usa.nc] Xbalder [usa.oh] Xbashful [usa.nc] Xbeaver [usa.pa?] Xbishop gbr Xbluebell usa.ca Xbluto [usa.tx?] Xbonnie usa.nj.a Xboojum usa.nj.a Xbosco [esp] Xbourbaki usa.il Xbozo usa.nj.a Xbrahms asia.japan Xcalico usa.ny Xcantor [usa.il] Xcapella swe Xcastor usa.nj.a Xcdr [usa.mi] Xcerberus [usa.il?] Xchaos usa.ok Xcirce usa.nj.a Xclara usa.ny Xclark usa.nj.a Xcleo usa.nj.b Xclutx [usa.fl?, usa.ny?] Xcogito usa.nj.a Xcolby usa.me Xcomet usa.or Xcondor usa.ma Xcottage [gbr] Xcsab [usa.il?] Xcsd1 usa.ny Xcsd2 usa.ny Xcsvax [usa.mn] Xcti usa.ca Xdanger can.ab Xdarwin can.on Xdcn1 [usa.ca?] Xdeimos [usa.il.a, usa.a] Xdelphi ita Xdev usa.md Xdewey usa.nj.a Xdickens [can.bc?] Xdiomedes usa.nj.a Xdoc [usa.nc] Xdopey [usa.nc] Xea usa.ok Xearth usa.nj.a Xed gbr Xeddie [gbr] Xedith [usa.oh] Xeinstein usa.ny Xelse [jpn] Xems usa.mn Xerc gbr Xernie [usa.oh] Xescher usa.ca Xeuclid [gbr] Xeuler usa.nj Xeunice usa.fl Xeuropa [usa.ri] Xexcalibur usa.pa Xfelix usa.ca Xfermat usa.nj Xfifi [usa.tx] Xfisher usa.nj Xflash [can.on] Xfloyd usa.nj.a Xfluke usa.wa Xforest [usa.tx] Xfred usa.co Xfrog usa.ma Xgalileo [usa.mo] Xgamma usa.nj.b Xgandalf can.on Xgarfield can.nf Xgateway usa.ny Xgizmo [usa.ca?, usa.il?] Xgodot usa.nc Xgolem usa.ca Xgonzo [usa.a?, usa.ca?] Xgould usa.fl Xgranite [usa.nh] Xgreen usa.md Xgrendel usa.nj.a Xgrumpy [usa.ga.a, usa.il.a, usa.a, usa.nc] Xhamlet [usa.nj.a] Xhappy [usa.nc] Xhaven usa.ct Xhawaii usa.hi Xhawk [usa.ca? Xhelios [usa.ca] Xhermes usa.il.a Xhilbert usa.wa Xhollywood [usa.ca?] Xhorus [usa.ca?] Xhottub [usa.ca] Xhub [usa.tx] Xhudson usa.nj.a Xhuey usa.nj.a Xicarus usa.nj.a Xicsd usa.fl.a Xindra usa.nj.b Xintech [gbr] Xio usa.nj.a Xipac [usa.az?, usa.ca?] Xiris usa.ri Xisis usa.co Xjack usa.ca Xjaguar [usa.il.a] Xjanus [usa.ca] Xjason usa.ny Xjenkins [usa.tx] Xjim [usa.ga.a, usa.il.a] Xjoey usa.pa.a Xjove usa.ny Xjuliet [usa.nj.a, usa.nj] Xkaos [usa.il] Xkermit usa.nj.a Xkobold [usa.ca] Xkronos grc Xlafite usa.nj.b Xlarry [usa.tx, usa.ma] Xleg [fra] Xlego dmk Xleopard usa.nj.b Xlilac kor Xlinus usa.ma Xlion usa.nj.b Xlouie usa.nj.a Xludwig usa.nj.a Xlynx [usa.ca] Xmadvax usa.ca Xmagic [usa.mo, usa.nj.b] Xmanx usa.nj Xmariner usa.nj.a Xmarvin gbr Xmath [usa.or] Xmaui usa.va Xmax usa.nj.a Xmaxwell usa.mo Xmedea [[usa.mi]] Xmegalon deu Xmerlin usa.nj.a Xmhuxc usa.nj.a Xmickey [usa.nj] Xmilo usa.md Xminnie usa.co Xmiranda usa.nj.a Xnemesis [usa.ca] Xnemo [usa.mo] Xnetman usa.oh.a Xnexus [can.ab, fra] Xnyquist usa.nj.b Xoac usa.nj.a Xoak [usa.ct] Xocean [usa.ca] Xodin usa.nj.a Xomega usa.nj.a Xopus [usa.a, usa.ga, usa.il.a] Xorion usa.nj.a Xorville usa.ny Xosiris usa.md Xotto usa.nv Xoz usa.wa Xpallas usa.il Xpandora usa.nj.b Xpelican usa.ca Xphobos usa.nj.a Xphoenix usa.nj.a Xphysics usa.nj.a Xpilchuck usa.wa Xpine kor Xpioneer [usa.il.a] Xplasma usa.pa.a Xpluto usa.ny Xpolaris usa.ny Xpolya usa.nj.a Xposeidon usa.nj.a Xpostel nld Xpresto usa.md Xpriam [che] Xprinceton usa.nj (stupid!) Xprism usa.nj Xprometheus usa.md Xpsc usa.md Xpsyche usa.nc Xpuma gbr Xqat [usa.tx] Xra usa.ny Xrainier swe Xralph [usa.tx] Xranger [usa.il.a] Xredwood [usa.ca] Xridge usa.ca Xrigel usa.ny Xrose usa.nj.a Xrover [usa.ma] Xrsch [usa.ma?] Xsabre usa.nj.b Xsal [swe] Xsales usa.a Xsamwise usa.nj.a Xsaturn usa.oh.a Xscience [usa.nj.b] Xsds [usa.mn] Xshark usa.or Xshrike [usa.tx] Xsimon [usa.il?] Xsleepy [usa.nc] Xsneezy [usa.wi] Xsnoopy [gbr] Xsol [usa.il.a, usa.ny, gbr] Xsolar usa.nm Xspam usa.nj Xsphinx usa.il Xstar [usa.ca?, usa.il.a?, usa.nj.b?] Xstars can.ns Xstc gbr Xstuart [usa.md] Xsunrise usa.nj Xsuper usa.md Xsurya usa.ca Xtb usa.ok.a Xterminus [usa.oh?, usa.wi?] Xterra usa.ma Xthor dmk Xthunder can.on Xthyme usa.ca Xtiger usa.nj Xtitan usa.ca Xtrillian usa.nj.a Xtriton [jpn, usa.or] Xtut fin Xubvax usa.ca Xulysses usa.nj.a Xunh usa.nh Xunicorn usa.nj.a Xunix [usa.or] Xunix3 [usa.ga.a, usa.il.a] Xusadhq2 [usa.ca?] Xusafa [usa.co?, usa.fl?, usa.nh?] Xvalid [usa.ca] Xvax1 [gbr] Xvax2 [gbr] Xvega swe Xvenice usa.ca.a Xvictoria can.on Xvortex usa.ca Xvoyager [usa.il.a] Xwang usa.ma Xwayback usa.nj.a Xwimsey usa.nj.a Xwombat usa.nj.a Xzaphod can.sk Xzeta usa.nj.b Xzorac can.on END_OF_arpa-privates if test 4636 -ne `wc -c config.h <<'END_OF_config.h' X/* pathalias -- by steve bellovin, as told to peter honeyman */ X X#undef STRCHR /* have strchr -- system v and many others */ X X#undef UNAME /* have uname() -- probably system v or 8th ed. */ X#undef MEMSET /* have memset() -- probably system v or 8th ed. */ X X#define GETHOSTNAME /* have gethostname() -- probably bsd */ X#define BZERO /* have bzero() -- probably bsd */ X X/* default place for dbm output of makedb (or use -o at run-time) */ X#define ALIASDB "/usr/local/lib/palias" X X X X/************************************************************************** X * * X * +--------------------------------------------------------------------+ * X * | | * X * | END OF CONFIGURATION SECTION | * X * | | * X * | EDIT NO MORE | * X * | | * X * +--------------------------------------------------------------------+ * X * * X **************************************************************************/ X X#ifdef MAIN X#ifndef lint Xstatic char *c_sccsid = "@(#)config.h 9.1 87/10/04"; X#endif /*lint*/ X#endif /*MAIN*/ X X/* X * malloc/free fine tuned for pathalias. X * X * MYMALLOC should work everwhere, so it's not a configuration X * option (anymore). nonetheless, if you're getting strange X * core dumps (or panics!), comment out the following manifest, X * and use the inferior C library malloc/free. X * X * please report problems to citi!honey or honey@citi.umich.edu. X */ X#define MYMALLOC /**/ X X#ifdef MYMALLOC X#define malloc mymalloc X#define calloc(n, s) malloc ((n)*(s)) X#define free(s) X#define cfree(s) Xextern char *memget(); X#else /* !MYMALLOC */ Xextern char *calloc(); X#endif /* MYMALLOC */ X X#ifdef STRCHR X#define index strchr X#define rindex strrchr X#else X#define strchr index X#define strrchr rindex X#endif X X#ifdef BZERO X#define strclear(s, n) ((void) bzero((s), (n))) X#else /*!BZERO*/ X X#ifdef MEMSET Xextern char *memset(); X#define strclear(s, n) ((void) memset((s), 0, (n))) X#else /*!MEMSET*/ Xextern void strclear(); X#endif /*MEMSET*/ X X#endif /*BZERO*/ X Xextern char *malloc(); Xextern char *strcpy(), *index(), *rindex(); END_OF_config.h if test 2061 -ne `wc -c def.h <<'END_OF_def.h' X/* pathalias -- by steve bellovin, as told to peter honeyman */ X X#ifndef lint X#ifdef MAIN Xstatic char *h_sccsid = "@(#)def.h 9.1 87/10/04"; X#endif /*MAIN*/ X#endif /*lint*/ X X#include X#include X#include "config.h" X Xtypedef long Cost; Xtypedef struct node node; Xtypedef struct link link; X X#ifdef lint X#define vprintf fprintf X#else /*!lint -- this gives null effect warning*/ X/* because it's there ... */ X#define vprintf !Vflag ? 0 : fprintf X#endif /*lint*/ X X#define NTRACE 16 /* can trace up to NTRACE hosts/links */ X X/* scanner states (yylex, parse) */ X#define OTHER 0 X#define COSTING 1 X#define NEWLINE 2 X X/* flags for n_flag */ X#define ISPRIVATE 0x0001 /* invisible outside its definition file */ X#define NALIAS 0x0002 /* heaped as an alias */ X#define ATSIGN 0x0004 /* seen an at sign? used for magic @/% rules */ X#define MAPPED 0x0008 /* extracted from heap */ X#define NDEAD 0x0010 /* out links are dead */ X#define HASLEFT 0x0020 /* has a left side net character */ X#define HASRIGHT 0x0040 /* route has a right side net character */ X#define NNET 0x0080 /* network pseudo-host */ X#define INDFS 0x0100 /* used when removing net cycles (for -g) */ X#define DUMP 0x0200 /* we have dumped this net's edges (for -g) */ X#define PRINTED 0x0400 /* this host has been printed */ X#define NTERMINAL 0x0800 /* heaped as terminal edge (or alias thereto) */ X X#define ISADOMAIN(n) ((n)->n_name[0] == '.') X#define ISANET(n) (((n)->n_flag & NNET) || ISADOMAIN(n)) X#define DEADHOST(n) ((((n)->n_flag & (NNET | NDEAD)) == NDEAD) || (n->n_flag & NTERMINAL)) X#define GATEWAYED(n) (((n)->n_flag & (NNET | NDEAD)) == (NNET | NDEAD) || ISADOMAIN(n)) X X#ifndef DEBUG X/* X * save some space in nodes -- there are > 10,000 allocated! X */ X X#define n_root un1.nu_root X#define n_net un1.nu_net X#define n_copy un1.nu_copy X X#define n_private un2.nu_priv X#define n_parent un2.nu_par X X/* WARNING: if > 2^16 nodes, type of n_tloc must change */ Xstruct node { X char *n_name; /* host name */ X link *n_link; /* adjacency list */ X Cost n_cost; /* cost to this host */ X union { X node *nu_net; /* others in this network (parsing) */ X node *nu_root; /* root of net cycle (graph dumping) */ X node *nu_copy; /* circular copy list (mapping) */ X } un1; X union { X node *nu_priv; /* other privates in this file (parsing) */ X node *nu_par; /* parent in shortest path tree (mapping) */ X } un2; X unsigned short n_tloc; /* back ptr to heap/hash table */ X unsigned short n_flag; /* see manifests above */ X}; X X#endif /*DEBUG*/ X X#define DEFNET '!' /* default network operator */ X#define DEFDIR LLEFT /* host on left is default */ X#define DEFCOST ((Cost) 4000) /* default cost of a link */ X#define INF ((Cost) 30000000) /* infinitely expensive link */ X#define DEFPENALTY ((Cost) 200) /* default avoidance cost */ X X/* data structure for adjacency list representation */ X X/* flags for l_dir */ X X#define NETDIR(l) ((l)->l_flag & LDIR) X#define NETCHAR(l) ((l)->l_netop) X X#define LDIR 0x0008 /* 0 for left, 1 for right */ X#define LRIGHT 0x0000 /* user@host style */ X#define LLEFT 0x0008 /* host!user style */ X X#define LDEAD 0x0010 /* this link is dead */ X#define LALIAS 0x0020 /* this link is an alias */ X#define LTREE 0x0040 /* member of shortest path tree */ X#define LGATEWAY 0x0080 /* this link is a gateway */ X#define LTERMINAL 0x0100 /* this link is terminal */ X X#ifndef DEBUG X/* X * borrow a field for link/node tracing. there's a shitload of X * edges -- every word counts. only so much squishing is possible: X * alignment dictates that the size be a multiple of four. X */ X X#define l_next un.lu_next X#define l_from un.lu_from X Xstruct link { X node *l_to; /* adjacent node */ X Cost l_cost; /* edge cost */ X union { X link *lu_next; /* rest of adjacency list (not tracing) */ X node *lu_from; /* source node (tracing) */ X } un; X short l_flag; /* right/left syntax, flags */ X char l_netop; /* network operator */ X}; X X#endif /*DEBUG*/ X X#ifdef DEBUG X/* X * flattening out the unions makes it easier X * to debug (when pi is unavailable). X */ Xstruct node { X char *n_name; X link *n_link; X Cost n_cost; X node *n_net; X node *n_root; X node *n_copy; X node *n_private; X node *n_parent; X unsigned short n_tloc; X unsigned short n_flag; X}; Xstruct link { X node *l_to; X Cost l_cost; X link *l_next; X node *l_from; X short l_flag; X char l_netop; X}; X#endif /*DEBUG*/ END_OF_def.h if test 4366 -ne `wc -c local.c <<'END_OF_local.c' X/* pathalias -- by steve bellovin, as told to peter honeyman */ X#ifndef lint Xstatic char *sccsid = "@(#)local.c 9.1 87/10/04"; X#endif /* lint */ X X#include X#include "config.h" X X#ifdef UNAME X#include X Xchar * Xlocal() X{ X static struct utsname utsname; X X uname(&utsname); X return(utsname.nodename); X} X X#else /* !UNAME */ X Xchar * Xlocal() X{ X static char lname[64]; X X gethostname(lname, sizeof(lname)); X return(lname); X} X X#ifndef GETHOSTNAME X Xstatic Xgethostname(name, len) Xchar *name; X{ X FILE *whoami, *fopen(), *popen(); X char *ptr, *index(); X X *name = '\0'; X X /* try /etc/whoami */ X if ((whoami = fopen("/etc/whoami", "r")) != 0) { X (void) fgets(name, len, whoami); X (void) fclose(whoami); X if ((ptr = index(name, '\n')) != 0) X *ptr = '\0'; X } X if (*name) X return 0; X X /* try /usr/include/whoami.h */ X if ((whoami = fopen("/usr/include/whoami.h", "r")) != 0) { X while (!feof(whoami)) { X char buf[100]; X X if (fgets(buf, 100, whoami) == 0) X break; X if (sscanf(buf, "#define sysname \"%[^\"]\"", name)) X break; X } X (void) fclose(whoami); X if (*name) X return 0; X } X X /* ask uucp */ X if ((whoami = popen("uuname -l", "r")) != 0) { X (void) fgets(name, len, whoami); X (void) pclose(whoami); X if ((ptr = index(name, '\n')) != 0) X *ptr = '\0'; X } X if (*name) X return 0; X X /* aw hell, i give up! is this really unix? */ X return -1; X} X#endif /* GETHOSTNAME */ X#endif /* UNAME */ END_OF_local.c if test 1420 -ne `wc -c main.c <<'END_OF_main.c' X/* pathalias -- by steve bellovin, as told to peter honeyman */ X#ifndef lint Xstatic char *sccsid = "@(#)main.c 9.1 87/10/04"; X#endif X X#define MAIN /* for sccsid in header files */ X X#include "def.h" X X/* exports */ Xextern void die(); Xchar *Cfile; /* current input file */ Xchar *Graphout; /* file for dumping edges (-g option) */ Xchar *Linkout; /* file for dumping shortest path tree */ Xchar **Argv; /* external copy of argv (for input files) */ Xnode *Home; /* node for local host */ Xint Cflag; /* print costs (-c option) */ Xint Dflag; /* penalize routes beyond domains (-D option) */ Xint Iflag; /* ignore case (-i option) */ Xint Tflag; /* trace links (-t option) */ Xint Vflag; /* verbose (-v option) */ Xint Fflag; /* print cost of first hop */ Xint Lineno = 1; /* line number within current input file */ Xint Argc; /* external copy of argc (for input files) */ X X/* imports */ Xextern long allocation(); Xextern void wasted(), mapit(), penalize(), hashanalyze(), deadlink(); Xextern char *local(); Xextern node *addnode(); Xextern char *optarg; Xextern int optind; Xextern long Lcount, Ncount; X X#define USAGE "usage: %s [-vciDf] [-l localname] [-d deadlink] [-t tracelink] [-g edgeout] [-s treeout] [-a avoid] [files ...]\n" X Xmain(argc, argv) X register int argc; X register char **argv; X{ char *locname = 0, buf[32], *bang; X register int c; X int errflg = 0; X X setbuf(stderr, (char *) 0); X (void) allocation(); /* initialize data space monitoring */ X Cfile = "[deadlinks]"; /* for tracing dead links */ X Argv = argv; X Argc = argc; X X while ((c = getopt(argc, argv, "a:cd:Dfg:il:s:t:v")) != EOF) X switch(c) { X case 'a': /* adjust cost out of arg */ X penalize(optarg, DEFPENALTY); X break; X case 'c': /* print cost info */ X Cflag++; X break; X case 'd': /* dead host or link */ X if ((bang = index(optarg, '!')) != 0) { X *bang++ = 0; X deadlink(addnode(optarg), addnode(bang)); X } else X deadlink(addnode(optarg), (node *) 0); X break; X case 'D': /* penalize routes beyond domains */ X Dflag++; X break; X case 'f': /* print cost of first hop */ X Cflag++; X Fflag++; X break; X case 'g': /* graph output file */ X Graphout = optarg; X break; X case 'i': /* ignore case */ X Iflag++; X break; X case 'l': /* local name */ X locname = optarg; X break; X case 's': /* show shortest path tree */ X Linkout = optarg; X break; X case 't': /* trace this link */ X if (tracelink(optarg) < 0) { X fprintf(stderr, "%s: can trace only %d links\n", Argv[0], NTRACE); X exit(1); X } X Tflag = 1; X break; X case 'v': /* verbose stderr, mixed blessing */ X Vflag++; X if (Vflag == 1) { X /* v8 pi snarf, benign EBADF elsewhere */ X sprintf(buf, "/proc/%05d\n", getpid()); X write(3, buf, strlen(buf)); X } X break; X default: X errflg++; X } X X if (errflg) { X fprintf(stderr, USAGE, Argv[0]); X exit(1); X } X argv += optind; /* kludge for yywrap() */ X X if (*argv) X freopen("/dev/null", "r", stdin); X else X Cfile = "[stdin]"; X X if (!locname) X locname = local(); X if (*locname == 0) { X locname = "lostinspace"; X fprintf(stderr, "%s: using \"%s\" for local name\n", X Argv[0], locname); X } X X Home = addnode(locname); /* add home node */ X Home->n_cost = 0; /* doesn't cost to get here */ X X yyparse(); /* read in link info */ X X if (Vflag > 1) X hashanalyze(); X vprintf(stderr, "%d vertices, %d edges\n", Ncount, Lcount); X vprintf(stderr, "allocation is %ldk after parsing\n", allocation()); X X Cfile = "[backlinks]"; /* for tracing back links */ X Lineno = 0; X X /* compute shortest path tree */ X mapit(); X vprintf(stderr, "allocation is %ldk after mapping\n", allocation()); X X /* traverse tree and print paths */ X printit(); X vprintf(stderr, "allocation is %ldk after printing\n", allocation()); X X wasted(); /* how much was wasted in memory allocation? */ X X return 0; X} X Xvoid Xdie(s) X char *s; X{ X fprintf(stderr, "%s: %s; notify the authorities\n", Argv[0], s); X#ifdef DEBUG X fflush(stdout); X fflush(stderr); X abort(); X#else X exit(-1); X#endif X} END_OF_main.c if test 3978 -ne `wc -c make.honey <<'END_OF_make.honey' X#!/bin/make -f X# pathalias -- by steve bellovin, as told to peter honeyman X X### configuration section X### X# if you can't or don't intend to use dbm files, X# don't bother with DBM or makedb XDBM = -ldbm X# or if you roll your own ... X# DBM = dbm.o X### X# where is getopt (if not in the c library)? X# GETOPT = -lgetopt X### end of configuration section X XCC = cc -g XCFLAGS = -DSTATIC=extern -DDEBUG XLDFLAGS = XYFLAGS = -d X XOBJ = addlink.o addnode.o local.o main.o mapit.o mapaux.o mem.o parse.o printit.o XOFILES = addlink.O addnode.O local.O main.O mapit.O mapaux.O mem.O parse.O printit.O XHDRS = def.h config.h XCSRC = addlink.c addnode.c local.c main.c mapit.c mapaux.c mem.c printit.c XLSRC = $(CSRC) parse.c XSRC = $(CSRC) parse.y makedb.c arpatxt.c X Xpathalias: $(OBJ) X $(CC) $(OBJ) $(LDFLAGS) -o pathalias X Xall: pathalias makedb arpatxt X X$(OBJ): $(HDRS) X Xparse.c: parse.y $(HDRS) X $(YACC) $(YFLAGS) parse.y X sed '/^# line/d' y.tab.c > parse.c X Xmakedb: makedb.o X $(CC) makedb.o $(LDFLAGS) $(DBM) -o makedb X Xmakedb.o: config.h X Xarpatxt: arpatxt.o X $(CC) arpatxt.o $(LDFLAGS) -o arpatxt X Xclean: X rm -f *.o y.tab.? parse.c X Xtags: $(SRC) $(HDRS) X ctags -w $(SRC) $(HDRS) X Xbundle: README CHANGES pathalias.1 Makefile ${HDRS} ${SRC} arpa-privates make.honey X @bundle README CHANGES pathalias.1 Makefile ${HDRS} ${SRC} arpa-privates make.honey X Xbundle1: README CHANGES pathalias.1 Makefile ${HDRS} X @bundle README CHANGES pathalias.1 Makefile ${HDRS} X Xbundle2: addlink.c addnode.c local.c main.c X @bundle addlink.c addnode.c local.c main.c X Xbundle3: mapit.c mapaux.c X @bundle mapit.c mapaux.c X Xbundle4: mem.c printit.c parse.y X @bundle mem.c printit.c parse.y makedb.c X Xbundle5: makedb.c arpatxt.c arpa-privates make.honey X @bundle makedb.c arpatxt.c arpa-privates make.honey X Xmake.honey: makefile X @cp makefile make.honey X Xlint: $(LSRC) X lint -hbau $(CFLAGS) $(LSRC) X lint makedb.c X X X# the remainder is site specific. X XPATHFILES = paths/* pp/* pm/* X Xpaths/internet: hosts.txt arpa-privates local.hosts X arpatxt -fi -g citi -g umix -p arpa-privates local.hosts hosts.txt > paths/internet X XAVOID = X X# map output (input, really) to lower case; verbose; terminal domains XARGS = -viD X XPARGS=$(ARGS) $(AVOID) $(PATHFILES) Xdwon: paths/local paths/internet X pathalias -l dwon $(PARGS) 2>ERRORS | sort -o dwon X X# desperation debugging -- examine the costs. Xcosts: X pathalias -icvvD ${PARGS} 2>error.costs | awk '{printf("%s\t%s\t%s\n", $$2, $$1, $$3)}' | sort -o pa.costs X X# make one BIG file. a BIG bad idea. Xcat: X for i in $(PATHFILES); do cat $$i; echo 'private {}'; done > CAT X X# make a pathparse database. -g is undocumented. Xedges: X pathalias -g edges $(PARGS) 2>ERRORS > edges.hosts X# makedb edges pa X Xumich: X pathalias -l umich $(PARGS) 2>umich.ERRORS | sort > umich X Xciti: paths/local paths/internet X pathalias -l citi $(PARGS) 2>citi.ERRORS | sort > citi X Xumix: X pathalias -l umix $(PARGS) 2>umix.ERRORS | sort > umix END_OF_make.honey if test 2912 -ne `wc -c makedb.c <<'END_OF_makedb.c' X/* pathalias -- by steve bellovin, as told to peter honeyman */ X#ifndef lint Xstatic char *sccsid = "@(#)makedb.c 9.1 87/10/04"; X#endif /* lint */ X X#include X#include "config.h" X Xtypedef struct { X char *dptr; X int dsize; X} datum; X Xchar *Ofile = ALIASDB, *ProgName; X X#define USAGE "%s [-o dbmname] [-a] [file ...]\n" X Xmain(argc, argv) X char *argv[]; X{ char *ofptr; X int c, append = 0; X extern int optind; X extern char *optarg; X X ProgName = argv[0]; X while ((c = getopt(argc, argv, "o:a")) != EOF) X switch(c) { X case 'o': /* dbm output file */ X Ofile = optarg; X break; X X case 'a': /* append mode */ X append++; X break; X X default: X fprintf(stderr, USAGE, ProgName); X exit(1); X break; X } X X X if ((ofptr = rindex(Ofile, '/')) != 0) X ofptr++; X else X ofptr = Ofile; X if (strlen(ofptr) > 10) { X ofptr[10] = 0; X fprintf(stderr, "%s: using %s for dbm output\n", ProgName, Ofile); X } X X if (append == 0 && dbfile(Ofile) != 0) { X perror_(Ofile); X exit(1); X } X X if (dbminit(Ofile) < 0) { X perror_(Ofile); X exit(1); X } X X if (optind == argc) X makedb((char *) 0); X else for ( ; optind < argc; optind++) X makedb(argv[optind]); X exit(0); X} X Xdbfile(dbf) X char *dbf; X{ X return (dbcreat(dbf, "dir") != 0 || dbcreat(dbf, "pag") != 0); X} X Xdbcreat(dbf, suffix) X char *dbf, *suffix; X{ char buf[BUFSIZ]; X int fd; X X (void) sprintf(buf, "%s.%s", dbf, suffix); X if ((fd = creat(buf, 0666)) < 0) X return(-1); X (void) close(fd); X return(0); X} X X Xmakedb(ifile) X char *ifile; X{ char line[BUFSIZ]; X datum key, val; X X if (ifile && (freopen(ifile, "r", stdin) == NULL)) { X perror_(ifile); X return; X } X X /* X * keys and values are 0 terminated. this wastes time and (disk) space, X * but does lend simplicity and backwards compatibility. X */ X key.dptr = line; X while (fgets(line, sizeof(line), stdin) != NULL) { X char *op, *end; X X end = line + strlen(line); X end[-1] = 0; /* kill newline, stuff null terminator */ X op = index(line, '\t'); X if (op != 0) { X *op++ = 0; X key.dsize = op - line; /* 0 terminated */ X val.dptr = op; X val.dsize = end - op; /* 0 terminated */ X } else { X key.dsize = end - line; /* 0 terminated */ X val.dptr = "\0"; /* why must i do this? */ X val.dsize = 1; X } X if (store(key, val) < 0) X perror_(Ofile); X } X} X Xperror_(str) X char *str; X{ X fprintf(stderr, "%s: ", ProgName); X perror(str); X} END_OF_makedb.c if test 2342 -ne `wc -c mapaux.c <<'END_OF_mapaux.c' X/* pathalias -- by steve bellovin, as told to peter honeyman */ X#ifndef lint Xstatic char *sccsid = "@(#)mapaux.c 9.1 87/10/04"; X#endif /* lint */ X X#include "def.h" X X/* imports */ Xextern long Nheap, Hashpart, Tabsize; Xextern node **Table, *Home; Xextern char *Graphout, *Linkout, *Netchars, **Argv; Xextern void freelink(), die(); Xextern long pack(); Xextern link *newlink(); Xextern node *newnode(); Xextern char *strsave(); X X/* exports */ Xlong pack(); Xvoid resetnodes(), dumpgraph(), showlinks(); Xint tiebreaker(); Xnode *ncopy(); X X/* privates */ Xstatic FILE *Gstream; /* for dumping graph */ XSTATIC void dumpnode(), untangle(), dfs(); XSTATIC int height(); XSTATIC link *lcopy(); X X X/* X * slide everything from Table[low] to Table[high] X * up toward the high end. make room! make room! X */ Xlong Xpack(low, high) X long low, high; X{ long hole, next; X X /* find first "hole " */ X for (hole = high; hole >= low && Table[hole] != 0; --hole) X ; X X /* repeatedly move next filled entry into last hole */ X for (next = hole - 1; next >= low; --next) { X if (Table[next] != 0) { X Table[hole] = Table[next]; X Table[hole]->n_tloc = hole; X Table[next] = 0; X while (Table[--hole] != 0) /* find next hole */ X ; X } X } X return hole + 1; X} X Xvoid Xresetnodes() X{ register long i; X register node *n; X X for (i = Hashpart; i < Tabsize; i++) X if ((n = Table[i]) != 0) { X n->n_cost = (Cost) 0; X n->n_flag &= ~(NALIAS|ATSIGN|MAPPED|HASLEFT|HASRIGHT|NTERMINAL); X n->n_copy = n; X } X X Home->n_cost = (Cost) 0; X Home->n_flag &= ~(NALIAS|ATSIGN|MAPPED|HASLEFT|HASRIGHT|NTERMINAL); X Home->n_copy = Home; X} X Xvoid Xdumpgraph() X{ register long i; X register node *n; X X if ((Gstream = fopen(Graphout, "w")) == NULL) { X fprintf(stderr, "%s: ", Argv[0]); X perror(Graphout); X return; X } X X untangle(); /* untangle net cycles for proper output */ X X for (i = Hashpart; i < Tabsize; i++) { X n = Table[i]; X if (n == 0) X continue; /* impossible, but ... */ X /* a minor optimization ... */ X if (n->n_link == 0) X continue; X /* pathparse doesn't need these */ X if (n->n_flag & NNET) X continue; X dumpnode(n); X } X} X XSTATIC void Xdumpnode(from) X register node *from; X{ register node *to; X register link *l; X link *lnet = 0, *ll, *lnext; X X for (l = from->n_link ; l; l = l->l_next) { X to = l->l_to; X if (from == to) X continue; /* oops -- it's me! */ X X if ((to->n_flag & NNET) == 0) { X /* host -> host -- print host>host */ X if (l->l_cost == INF) X continue; /* phoney link */ X fputs(from->n_name, Gstream); X putc('>', Gstream); X fputs(to->n_name, Gstream); X putc('\n', Gstream); X } else { X /* X * host -> net -- just cache it for now. X * first check for dups. (quadratic, but X * n is small here.) X */ X while (to->n_root && to != to->n_root) X to = to->n_root; X for (ll = lnet; ll; ll = ll->l_next) X if (strcmp(ll->l_to->n_name, to->n_name) == 0) X break; X if (ll) X continue; /* dup */ X ll = newlink(); X ll->l_next = lnet; X ll->l_to = to; X lnet = ll; X } X } X X /* dump nets */ X if (lnet) { X /* nets -- print host@\tnet,net, ... */ X fputs(from->n_name, Gstream); X putc('@', Gstream); X putc('\t', Gstream); X for (ll = lnet; ll; ll = lnext) { X lnext = ll->l_next; X fputs(ll->l_to->n_name, Gstream); X if (lnext) X fputc(',', Gstream); X freelink(ll); X } X putc('\n', Gstream); X } X} X X/* X * remove cycles in net definitions. X * X * depth-first search X * X * for each net, run dfs on its neighbors (nets only). if we return to X * a visited node, that's a net cycle. mark the cycle with a pointer X * in the n_root field (which gets us closer to the root of this X * portion of the dfs tree). X */ XSTATIC void Xuntangle() X{ register long i; X register node *n; X X for (i = Hashpart; i < Tabsize; i++) { X n = Table[i]; X if (n == 0 || (n->n_flag & NNET) == 0 || n->n_root) X continue; X dfs(n); X } X} X XSTATIC void Xdfs(n) X register node *n; X{ register link *l; X register node *next; X X n->n_flag |= INDFS; X n->n_root = n; X for (l = n->n_link; l; l = l->l_next) { X next = l->l_to; X if ((next->n_flag & NNET) == 0) X continue; X if ((next->n_flag & INDFS) == 0) { X dfs(next); X if (next->n_root != next) X n->n_root = next->n_root; X } else X n->n_root = next->n_root; X } X n->n_flag &= ~INDFS; X} X Xvoid Xshowlinks() X{ register link *l; X register node *n; X register long i; X FILE *estream; X X if ((estream = fopen(Linkout, "w")) == 0) X return; X X for (i = Hashpart; i < Tabsize; i++) { X n = Table[i]; X if (n == 0 || n->n_link == 0) X continue; X for (l = n->n_link; l; l = l->l_next) { X fputs(n->n_name, estream); X putc('\t', estream); X if (NETDIR(l) == LRIGHT) X putc(NETCHAR(l), estream); X fputs(l->l_to->n_name, estream); X if (NETDIR(l) == LLEFT) X putc(NETCHAR(l), estream); X fprintf(estream, "(%d)\n", l->l_cost); X } X } X (void) fclose(estream); X} X X/* X * n is node in heap, newp is candidate for new parent. X * choose between newp and n->n_parent for parent. X * return 0 to use newp, non-zero o.w. X */ X#define NEWP 0 X#define OLDP 1 Xint Xtiebreaker(n, newp) X node *n; X register node *newp; X{ register char *opname, *npname, *name; X register node *oldp; X int metric; X X oldp = n->n_parent; X X /* given the choice, avoid gatewayed nets */ X if (GATEWAYED(newp) && !GATEWAYED(oldp)) X return OLDP; X if (!GATEWAYED(newp) && GATEWAYED(oldp)) X return NEWP; X X /* look at real parents, not nets */ X while ((oldp->n_flag & NNET) && oldp->n_parent) X oldp = oldp->n_parent; X while ((newp->n_flag & NNET) && newp->n_parent) X newp = newp->n_parent; X X /* use fewer hops, if possible */ X metric = height(oldp) - height(newp); X if (metric < 0) X return OLDP; X if (metric > 0) X return NEWP; X X /* X * compare names X */ X opname = oldp->n_name; X npname = newp->n_name; X name = n->n_name; X X /* use longest common prefix with parent */ X while (*opname == *name && *npname == *name && *name) { X opname++; X npname++; X name++; X } X if (*opname == *name) X return OLDP; X if (*npname == *name) X return NEWP; X X /* use shorter host name */ X metric = strlen(opname) - strlen(npname); X if (metric < 0) X return OLDP; X if (metric > 0) X return NEWP; X X /* use larger lexicographically */ X metric = strcmp(opname, npname); X if (metric < 0) X return NEWP; X return OLDP; X} X XSTATIC int Xheight(n) X register node *n; X{ register int i = 0; X X if (n == 0) X return 0; X while ((n = n->n_parent) != 0) X if (ISADOMAIN(n) || !(n->n_flag & NNET)) X i++; X return i; X} X X/* l is a terminal edge from n -> next; return a copy of next */ Xnode * Xncopy(n) X register node *n; X{ register node *ncp; X X ncp = newnode(); X ncp->n_name = n->n_name; /* nonvolatile */ X ncp->n_tloc = --Hashpart; /* better not be > 20% of total ... */ X if (Hashpart == Nheap) X die("too many terminal links"); X Table[Hashpart] = ncp; X ncp->n_copy = n->n_copy; /* circular list */ X n->n_copy = ncp; X ncp->n_link = lcopy(n->n_link); X ncp->n_flag = (n->n_flag & ~(NALIAS|ATSIGN|MAPPED|HASLEFT|HASRIGHT)) | NTERMINAL; X return ncp; X} X XSTATIC link * Xlcopy(l) X register link *l; X{ register link *lcp; X X if (l == 0) X return 0; X lcp = newlink(); X *lcp = *l; X lcp->l_flag &= ~LTREE; X lcp->l_next = lcopy(l->l_next); X return lcp; X} END_OF_mapaux.c if test 7110 -ne `wc -c mem.c <<'END_OF_mem.c' X/* pathalias -- by steve bellovin, as told to peter honeyman */ X#ifndef lint Xstatic char *sccsid = "@(#)mem.c 9.1 87/10/04"; X#endif X X#include "def.h" X X/* exports */ Xextern void freelink(), wasted(); Xextern long allocation(); Xlong Ncount; X X/* imports */ Xextern char *sbrk(); Xextern char *Netchars; Xextern int Vflag; Xextern void die(); X X/* privates */ XSTATIC void nomem(); Xstatic link *Lcache; Xstatic unsigned int Memwaste; X Xlink * Xnewlink() X{ register link *rval; X X if (Lcache) { X rval = Lcache; X Lcache = Lcache->l_next; X strclear((char *) rval, sizeof(link)); X } else if ((rval = (link * ) calloc(1, sizeof(link))) == 0) X nomem(); X return rval; X} X X/* caution: this destroys the contents of l_next */ Xvoid Xfreelink(l) X link *l; X{ X l->l_next = Lcache; X Lcache = l; X} X Xnode * Xnewnode() X{ register node *rval; X X if ((rval = (node * ) calloc(1, sizeof(node))) == 0) X nomem(); X Ncount++; X return rval; X} X Xchar * Xstrsave(s) X char *s; X{ register char *r; X X if ((r = malloc((unsigned) strlen(s) + 1)) == 0) X nomem(); X (void) strcpy(r, s); X return r; X} X X#ifndef strclear Xvoid Xstrclear(str, len) X register char *str; X register long len; X{ X while (--len >= 0) X *str++ = 0; X} X#endif /*strclear*/ X Xnode ** Xnewtable(size) X long size; X{ register node **rval; X X if ((rval = (node **) calloc(1, (unsigned int) size * sizeof(node *))) == 0) X nomem(); X return rval; X} X Xfreetable(t, size) X node **t; X long size; X{ X#ifdef MYMALLOC X addtoheap((char *) t, size * sizeof(node *)); X#else X free((char *) t); X#endif X} X XSTATIC void Xnomem() X{ X static char epitaph[128]; X X sprintf(epitaph, "out of memory (%ldk allocated)", allocation()); X die(epitaph); X} X X/* data space allocation -- main sets `dataspace' very early */ Xlong Xallocation() X{ X static char *dataspace; X long rval; X X if (dataspace == 0) { /* first time */ X dataspace = sbrk(0); /* &end? */ X return 0; X } X rval = (sbrk(0) - dataspace)/1024; X if (rval < 0) /* funny architecture? */ X rval = -rval; X return rval; X} X X/* how much memory has been wasted? */ Xvoid Xwasted() X{ X if (Memwaste == 0) X return; X vprintf(stderr, "memory allocator wasted %ld bytes\n", Memwaste); X} X X#ifdef MYMALLOC X X/* use c library malloc/calloc here, and here only */ X#undef malloc X#undef calloc Xextern char *malloc(), *calloc(); X X/* allocate in MBUFSIZ chunks. 4k works ok (less 16 for malloc quirks). */ X#define MBUFSIZ (4 * 1024 - 16) X X/* X * mess with ALIGN at your peril. longword (== 0 mod 4) X * alignment seems to work everywhere. X */ X X#define ALIGN 2 X Xtypedef struct heap heap; Xstruct heap { X heap *h_next; X long h_size; X}; X Xstatic heap *Mheap; /* not to be confused with a priority queue */ X Xaddtoheap(p, size) X char *p; X long size; X{ int adjustment; X heap *pheap; X X /* p is aligned, but it doesn't hurt to check */ X adjustment = align(p); X p += adjustment; X size -= adjustment; X X if (size < 1024) X return; /* can't happen */ X pheap = (heap *) p; /* pheap is shorthand */ X pheap->h_next = Mheap; X pheap->h_size = size; X Mheap = pheap; X} X X/* X * buffered malloc() X * returns space initialized to 0. calloc isn't used, since X * strclear can be faster. X * X * free is ignored, except for very large objects, X * which are returned to the heap with addtoheap(). X */ X Xchar * Xmymalloc(n) X register unsigned int n; X{ static unsigned int size; /* how much do we have on hand? */ X static char *mstash; /* where is it? */ X register char *rval; X X if (n >= 1024) { /* for hash table */ X rval = malloc(n); /* aligned */ X if (rval) X strclear(rval, n); X return rval; X } X X n += align((char *) n); /* keep everything aligned */ X X if (n > size) { X Memwaste += size; /* toss the fragment */ X /* look in the heap */ X if (Mheap) { X mstash = (char *) Mheap; /* aligned */ X size = Mheap->h_size; X Mheap = Mheap->h_next; X } else { X mstash = malloc(MBUFSIZ); /* aligned */ X if (mstash == 0) { X size = 0; X return 0; X } X size = MBUFSIZ; X } X strclear(mstash, size); /* what if size > 2^16? */ X } X rval = mstash; X mstash += n; X size -= n; X return rval; X} X X/* X * what's the (mis-)alignment of n? return the complement of X * n mod 2^ALIGN X */ Xalign(n) X char *n; X{ register int abits; /* misalignment bits in n */ X X abits = (int) n & ~(0xff << ALIGN) & 0xff; X if (abits == 0) X return 0; X return (1 << ALIGN) - abits; X} X X#endif /*MYMALLOC*/ END_OF_mem.c if test 4277 -ne `wc -c printit.c <<'END_OF_printit.c' X/* pathalias -- by steve bellovin, as told to peter honeyman */ X#ifndef lint Xstatic char *sccsid = "@(#)printit.c 9.1 87/10/04"; X#endif X X#include "def.h" X X/* X * print the routes by traversing the shortest path tree in preorder. X * use lots of char bufs -- profiling indicates this costs about 5 kbytes X */ X X/* exports */ Xextern void printit(); X X/* imports */ Xextern int Cflag, Vflag, Dflag, Fflag; Xextern node *Home; Xextern char *Netchars; Xextern void die(); X X/* privates */ Xstatic link *Ancestor; /* for -f option */ XSTATIC void preorder(), setpath(), printhost(), printdomain(); XSTATIC char *hostpath(); X X/* in practice, even the longest paths are < 100 bytes */ X#define PATHSIZE 512 X Xvoid Xprintit() X{ link *l; X char pbuf[PATHSIZE]; X X /* print home */ X if (Cflag) X printf("%ld\t", (long) Home->n_cost); X printf("%s\t%%s\n", Home->n_name); X X strcpy(pbuf, "%s"); X for (l = Home->n_link; l; l = l->l_next) { X if (l->l_flag & LTREE) { X l->l_flag &= ~LTREE; X Ancestor = l; X preorder(l, pbuf); X strcpy(pbuf, "%s"); X } X } X fflush(stdout); X fflush(stderr); X} X X/* X * preorder traversal of shortest path tree. X */ XSTATIC void Xpreorder(l, ppath) X register link *l; X char *ppath; X{ register node *n; X node *ncp; /* circular copy list */ X Cost cost; X char npath[PATHSIZE]; X short p_dir; /* DIR bits of parent (for nets) */ X char p_op; /* net op of parent (for nets) */ X X setpath(l, ppath, npath); X n = l->l_to; X if (printable(n)) { X if (Fflag) X cost = Ancestor->l_to->n_cost; X else X cost = n->n_cost; X if (ISADOMAIN(n)) X printdomain(n, npath, cost); X else if (!(n->n_flag & NNET)) { X printhost(n, npath, cost); X } X n->n_flag |= PRINTED; X for (ncp = n->n_copy; ncp != n; ncp = ncp->n_copy) X ncp->n_flag |= PRINTED; X } X X /* prepare routing bits for domain members */ X p_dir = l->l_flag & LDIR; X p_op = l->l_netop; X X /* recursion */ X for (l = n->n_link; l; l = l->l_next) { X if (!(l->l_flag & LTREE)) X continue; X /* network member inherits the routing syntax of its gateway */ X if (ISANET(n)) { X l->l_flag = (l->l_flag & ~LDIR) | p_dir; X l->l_netop = p_op; X } X l->l_flag &= ~LTREE; X preorder(l, npath); X } X} X XSTATIC int Xprintable(n) X register node *n; X{ node *ncp; X link *l; X X if (n->n_flag & PRINTED) X return 0; X X /* is there a cheaper copy? */ X for (ncp = n->n_copy; n != ncp; ncp = ncp->n_copy) { X if (!(ncp->n_flag & MAPPED)) X continue; /* unmapped copy */ X X if (n->n_cost > ncp->n_cost) X return 0; /* cheaper copy */ X X if (n->n_cost == ncp->n_cost && !(ncp->n_flag & NTERMINAL)) X return 0; /* synthetic copy */ X } X X /* will a domain route suffice? */ X if (Dflag && !ISANET(n) && ISADOMAIN(n->n_parent)) { X /* X * are there any interesting links? a link X * is interesting if it doesn't point back X * to the parent, and is not an alias. X */ X X /* check n */ X for (l = n->n_link; l; l = l->l_next) { X if (l->l_to == n->n_parent) X continue; X if ((!l->l_flag & LALIAS)) X return 1; X } X X /* check copies of n */ X for (ncp = n->n_copy; ncp != n; ncp = ncp->n_copy) { X for (l = ncp->n_link; l; l = l->l_next) { X if (l->l_to == n->n_parent) X continue; X if (!(l->l_flag & LALIAS)) X return 1; X } X } X X /* domain route suffices */ X return 0; X } X return 1; X} X XSTATIC void Xsetpath(l, ppath, npath) X link *l; X register char *ppath, *npath; X{ register node *next, *parent; X char netchar; X X next = l->l_to; X parent = next->n_parent; X netchar = NETCHAR(l); X X /* for magic @->% conversion */ X if (parent->n_flag & ATSIGN) X next->n_flag |= ATSIGN; X X /* X * i've noticed that distant gateways to domains frequently get X * ...!gateway!user@dom.ain wrong. ...!gateway!user%dom.ain X * seems to work, so if next is a domain and the parent is X * not the local host, force a magic %->@ conversion. in this X * context, "parent" is the nearest ancestor that is not a net. X */ X while (ISANET(parent)) X parent = parent->n_parent; X if (ISADOMAIN(next) && parent != Home) X next->n_flag |= ATSIGN; X X /* X * special handling for nets (including domains) and aliases. X * part of the trick is to treat aliases to domains as 0 cost X * links. (the author believes they should be declared as such X * in the input, but the world disagrees). X */ X if (ISANET(next) || ((l->l_flag & LALIAS) && !ISADOMAIN(parent))) { X strcpy(npath, ppath); X return; X } X X if (netchar == '@') X if (next->n_flag & ATSIGN) X netchar = '%'; /* shazam? shaman? */ X else X next->n_flag |= ATSIGN; X X /* remainder should be a sprintf -- foo on '%' as an operator */ X for ( ; *npath = *ppath; ppath++) { X if (*ppath == '%') { X switch(ppath[1]) { X case 's': X ppath++; X npath = hostpath(npath, l, netchar); X break; X X case '%': X *++npath = *++ppath; X npath++; X break; X X default: X die("unknown escape in setpath"); X break; X } X } else X npath++; X } X} X XSTATIC char * Xhostpath(path, l, netchar) X register char *path; X register link *l; X char netchar; X{ register node *prev; X X prev = l->l_to->n_parent; X if (NETDIR(l) == LLEFT) { X /* host!%s */ X strcpy(path, l->l_to->n_name); X path += strlen(path); X while (ISADOMAIN(prev)) { X strcpy(path, prev->n_name); X path += strlen(path); X prev = prev->n_parent; X } X *path++ = netchar; X if (netchar == '%') X *path++ = '%'; X *path++ = '%'; X *path++ = 's'; X } else { X /* %s@host */ X *path++ = '%'; X *path++ = 's'; X *path++ = netchar; X if (netchar == '%') X *path++ = '%'; X strcpy(path, l->l_to->n_name); X path += strlen(path); X while (ISADOMAIN(prev)) { X strcpy(path, prev->n_name); X path += strlen(path); X prev = prev->n_parent; X } X } X return path; X} X XSTATIC void Xprinthost(n, path, cost) X register node *n; X char *path; X Cost cost; X{ X if (n->n_flag & PRINTED) X die("printhost called twice"); X n->n_flag |= PRINTED; X /* skip private hosts */ X if ((n->n_flag & ISPRIVATE) == 0) { X if (Cflag) X printf("%ld\t", (long) cost); X fputs(n->n_name, stdout); X putchar('\t'); X puts(path); X } X} X XSTATIC void Xprintdomain(n, path, cost) X register node *n; X char *path; X Cost cost; X{ node *p; X X if (n->n_flag & PRINTED) X die("printdomain called twice"); X n->n_flag |= PRINTED; X X /* X * print a route for dom.ain if it is a top-level domain, unless X * it is private. X * X * print a route for sub.dom.ain only if all its ancestor dom.ains X * are private and sub.dom.ain is not private. X */ X if (!ISADOMAIN(n->n_parent)) { X /* top-level domain */ X if (n->n_flag & ISPRIVATE) { X vprintf(stderr, "ignoring private top-level domain %s\n", n->n_name); X return; X } X } else { X /* subdomain */ X for (p = n->n_parent; ISADOMAIN(p); p = p->n_parent) X if (!(p->n_flag & ISPRIVATE)) X return; X if (n->n_flag & ISPRIVATE) X return; X } X X /* print it (at last!) */ X if (Cflag) X printf("%ld\t", (long) cost); X do { X fputs(n->n_name, stdout); X n = n->n_parent; X } while (ISADOMAIN(n)); X putchar('\t'); X puts(path); X} END_OF_printit.c if test 6855 -ne `wc -c