1 /*
2 * Copyright (c) 1980 Regents of the University of California.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms are permitted
6 * provided that this notice is preserved and that due credit is given
7 * to the University of California at Berkeley. The name of the University
8 * may not be used to endorse or promote products derived from this
9 * software without specific prior written permission. This software
10 * is provided ``as is'' without express or implied warranty.
11 */
12
13 #ifdef notdef
14 static char sccsid[] = "@(#)optim.c 5.9 (Berkeley) 02/18/88";
15 #endif /* notdef */
16
17 /*
18 * Mail -- a program for sending and receiving mail.
19 *
20 * Network name modification routines.
21 */
22
23 #include "rcv.h"
24 #include "configdefs.h"
25
26 /*
27 * Map a name into the correct network "view" of the
28 * name. This is done by prepending the name with the
29 * network address of the sender, then optimizing away
30 * nonsense.
31 */
32
33 char *
netmap(name,from)34 netmap(name, from)
35 char name[], from[];
36 {
37 char nbuf[BUFSIZ], ret[BUFSIZ];
38 register char *cp;
39
40 if (strlen(from) == 0)
41 return(name);
42 if (any('@', name) || any('%', name))
43 return(savestr(arpafix(name, from)));
44 cp = revarpa(from);
45 if (cp == NOSTR)
46 return(name);
47 strcpy(nbuf, cp);
48 cp = &nbuf[strlen(nbuf) - 1];
49 while (!any(*cp, metanet) && cp > nbuf)
50 cp--;
51 if (cp == nbuf)
52 return(name);
53 *++cp = 0;
54 if ((cp = revarpa(name)) != NOSTR)
55 strcat(nbuf, cp);
56 optim(nbuf, ret);
57 cp = revarpa(ret);
58 if (cp && !icequal(name, cp))
59 return(savestr(cp));
60 return(name);
61 }
62
63 /*
64 * Turn a network machine name into a unique character
65 */
netlook(machine,attnet)66 netlook(machine, attnet)
67 char machine[];
68 {
69 register struct netmach *np;
70 register char *cp, *cp2;
71 char nbuf[BUFSIZ];
72
73 /*
74 * Make into lower case.
75 */
76
77 for (cp = machine, cp2 = nbuf; *cp; *cp2++ = little(*cp++))
78 if (cp2 >= &nbuf[sizeof(nbuf)-1])
79 break;
80 *cp2 = 0;
81
82 /*
83 * If a single letter machine, look through those first.
84 */
85
86 if (strlen(nbuf) == 1)
87 for (np = netmach; np->nt_mid != 0; np++)
88 if (np->nt_mid == nbuf[0])
89 return(nbuf[0]);
90
91 /*
92 * Look for usual name
93 */
94
95 for (np = netmach; np->nt_mid != 0; np++)
96 if (strcmp(np->nt_machine, nbuf) == 0)
97 return(np->nt_mid);
98
99 /*
100 * Look in side hash table.
101 */
102
103 return(mstash(nbuf, attnet));
104 }
105
106 /*
107 * Make a little character.
108 */
109
little(c)110 little(c)
111 register int c;
112 {
113
114 if (c >= 'A' && c <= 'Z')
115 c += 'a' - 'A';
116 return(c);
117 }
118
119 /*
120 * Turn a network unique character identifier into a network name.
121 */
122
123 char *
netname(mid)124 netname(mid)
125 {
126 register struct netmach *np;
127 char *mlook();
128
129 if (mid & 0200)
130 return(mlook(mid));
131 for (np = netmach; np->nt_mid != 0; np++)
132 if (np->nt_mid == mid)
133 return(np->nt_machine);
134 return(NOSTR);
135 }
136
137 /*
138 * Deal with arpa net addresses. The way this is done is strange.
139 * In particular, if the destination arpa net host is not Berkeley,
140 * then the address is correct as stands. Otherwise, we strip off
141 * the trailing @Berkeley, then cook up a phony person for it to
142 * be from and optimize the result.
143 */
144 char *
arpafix(name,from)145 arpafix(name, from)
146 char name[];
147 char from[];
148 {
149 register char *cp;
150 register int arpamach;
151 char newname[BUFSIZ];
152 char fake[5];
153 char fakepath[20];
154
155 if (debug) {
156 fprintf(stderr, "arpafix(%s, %s)\n", name, from);
157 }
158 cp = rindex(name, '@');
159 if (cp == NOSTR)
160 cp = rindex(name, '%');
161 if (cp == NOSTR) {
162 fprintf(stderr, "Somethings amiss -- no @ or %% in arpafix\n");
163 return(name);
164 }
165 cp++;
166 arpamach = netlook(cp, '@');
167 if (arpamach == 0) {
168 if (debug)
169 fprintf(stderr, "machine %s unknown, uses: %s\n", cp, name);
170 return(name);
171 }
172 if (((nettype(arpamach) & nettype(LOCAL)) & ~AN) == 0) {
173 if (debug)
174 fprintf(stderr, "machine %s known but remote, uses: %s\n",
175 cp, name);
176 return(name);
177 }
178 strcpy(newname, name);
179 cp = rindex(newname, '@');
180 if (cp == NOSTR)
181 cp = rindex(newname, '%');
182 *cp = 0;
183 fake[0] = arpamach;
184 fake[1] = ':';
185 fake[2] = LOCAL;
186 fake[3] = ':';
187 fake[4] = 0;
188 prefer(fake);
189 strcpy(fakepath, netname(fake[0]));
190 stradd(fakepath, fake[1]);
191 strcat(fakepath, "daemon");
192 if (debug)
193 fprintf(stderr, "machine local, call netmap(%s, %s)\n",
194 newname, fakepath);
195 return(netmap(newname, fakepath));
196 }
197
198 /*
199 * Take a network machine descriptor and find the types of connected
200 * nets and return it.
201 */
202
nettype(mid)203 nettype(mid)
204 {
205 register struct netmach *np;
206
207 if (mid & 0200)
208 return(mtype(mid));
209 for (np = netmach; np->nt_mid != 0; np++)
210 if (np->nt_mid == mid)
211 return(np->nt_type);
212 return(0);
213 }
214
215 /*
216 * Hashing routines to salt away machines seen scanning
217 * networks paths that we don't know about.
218 */
219
220 #define XHSIZE 19 /* Size of extra hash table */
221 #define NXMID (XHSIZE*3/4) /* Max extra machines */
222
223 struct xtrahash {
224 char *xh_name; /* Name of machine */
225 short xh_mid; /* Machine ID */
226 short xh_attnet; /* Attached networks */
227 } xtrahash[XHSIZE];
228
229 struct xtrahash *xtab[XHSIZE]; /* F: mid-->machine name */
230
231 short midfree; /* Next free machine id */
232
233 /*
234 * Initialize the extra host hash table.
235 * Called by sreset.
236 */
237
minit()238 minit()
239 {
240 register struct xtrahash *xp, **tp;
241
242 midfree = 0;
243 tp = &xtab[0];
244 for (xp = &xtrahash[0]; xp < &xtrahash[XHSIZE]; xp++) {
245 xp->xh_name = NOSTR;
246 xp->xh_mid = 0;
247 xp->xh_attnet = 0;
248 *tp++ = (struct xtrahash *) 0;
249 }
250 }
251
252 /*
253 * Stash a net name in the extra host hash table.
254 * If a new entry is put in the hash table, deduce what
255 * net the machine is attached to from the net character.
256 *
257 * If the machine is already known, add the given attached
258 * net to those already known.
259 */
260
mstash(name,attnet)261 mstash(name, attnet)
262 char name[];
263 {
264 register struct xtrahash *xp;
265 struct xtrahash *xlocate();
266 int x;
267
268 xp = xlocate(name);
269 if (xp == (struct xtrahash *) 0) {
270 printf("Ran out of machine id spots\n");
271 return(0);
272 }
273 if (xp->xh_name == NOSTR) {
274 if (midfree >= XHSIZE) {
275 printf("Out of machine ids\n");
276 return(0);
277 }
278 xtab[midfree] = xp;
279 xp->xh_name = savestr(name);
280 xp->xh_mid = 0200 + midfree++;
281 }
282 x = ntype(attnet);
283 if (x == 0)
284 xp->xh_attnet |= SN;
285 else
286 xp->xh_attnet |= x;
287 return(xp->xh_mid);
288 }
289
290 /*
291 * Search for the given name in the hash table
292 * and return the pointer to it if found, or to the first
293 * empty slot if not found.
294 *
295 * If no free slots can be found, return 0.
296 */
297
298 struct xtrahash *
xlocate(name)299 xlocate(name)
300 char name[];
301 {
302 register int h, q, i;
303 register char *cp;
304 register struct xtrahash *xp;
305
306 for (h = 0, cp = name; *cp; h = (h << 2) + *cp++)
307 ;
308 if (h < 0 && (h = -h) < 0)
309 h = 0;
310 h = h % XHSIZE;
311 cp = name;
312 for (i = 0, q = 0; q < XHSIZE; i++, q = i * i) {
313 xp = &xtrahash[(h + q) % XHSIZE];
314 if (xp->xh_name == NOSTR)
315 return(xp);
316 if (strcmp(cp, xp->xh_name) == 0)
317 return(xp);
318 if (h - q < 0)
319 h += XHSIZE;
320 xp = &xtrahash[(h - q) % XHSIZE];
321 if (xp->xh_name == NOSTR)
322 return(xp);
323 if (strcmp(cp, xp->xh_name) == 0)
324 return(xp);
325 }
326 return((struct xtrahash *) 0);
327 }
328
329 /*
330 * Return the name from the extra host hash table corresponding
331 * to the passed machine id.
332 */
333
334 char *
mlook(mid)335 mlook(mid)
336 {
337 register int m;
338
339 if ((mid & 0200) == 0)
340 return(NOSTR);
341 m = mid & 0177;
342 if (m >= midfree) {
343 printf("Use made of undefined machine id\n");
344 return(NOSTR);
345 }
346 return(xtab[m]->xh_name);
347 }
348
349 /*
350 * Return the bit mask of net's that the given extra host machine
351 * id has so far.
352 */
353
mtype(mid)354 mtype(mid)
355 {
356 register int m;
357
358 if ((mid & 0200) == 0)
359 return(0);
360 m = mid & 0177;
361 if (m >= midfree) {
362 printf("Use made of undefined machine id\n");
363 return(0);
364 }
365 return(xtab[m]->xh_attnet);
366 }
367
368 /*
369 * Take a network name and optimize it. This gloriously messy
370 * operation takes place as follows: the name with machine names
371 * in it is tokenized by mapping each machine name into a single
372 * character machine id (netlook). The separator characters (network
373 * metacharacters) are left intact. The last component of the network
374 * name is stripped off and assumed to be the destination user name --
375 * it does not participate in the optimization. As an example, the
376 * name "research!vax135!research!ucbvax!bill" becomes, tokenized,
377 * "r!x!r!v!" and "bill" A low level routine, optim1, fixes up the
378 * network part (eg, "r!x!r!v!"), then we convert back to network
379 * machine names and tack the user name on the end.
380 *
381 * The result of this is copied into the parameter "name"
382 */
383
optim(net,name)384 optim(net, name)
385 char net[], name[];
386 {
387 char netcomp[BUFSIZ], netstr[40], xfstr[40];
388 register char *cp, *cp2;
389 register int c;
390
391 strcpy(netstr, "");
392 cp = net;
393 for (;;) {
394 /*
395 * Rip off next path component into netcomp
396 */
397 cp2 = netcomp;
398 while (*cp && !any(*cp, metanet))
399 *cp2++ = *cp++;
400 *cp2 = 0;
401 /*
402 * If we hit null byte, then we just scanned
403 * the destination user name. Go off and optimize
404 * if its so.
405 */
406 if (*cp == 0)
407 break;
408 if ((c = netlook(netcomp, *cp)) == 0) {
409 printf("No host named \"%s\"\n", netcomp);
410 err:
411 strcpy(name, net);
412 return;
413 }
414 stradd(netstr, c);
415 stradd(netstr, *cp++);
416 /*
417 * If multiple network separators given,
418 * throw away the extras.
419 */
420 while (any(*cp, metanet))
421 cp++;
422 }
423 if (strlen(netcomp) == 0) {
424 printf("net name syntax\n");
425 goto err;
426 }
427 optim1(netstr, xfstr);
428
429 /*
430 * Convert back to machine names.
431 */
432
433 cp = xfstr;
434 strcpy(name, "");
435 while (*cp) {
436 if ((cp2 = netname(*cp++)) == NOSTR) {
437 printf("Made up bad net name\n");
438 printf("Machine code %c (0%o)\n", cp[-1], cp[-1]);
439 printf("Sorry -- dumping now. Alert K. Shoens\n");
440 core();
441 goto err;
442 }
443 strcat(name, cp2);
444 stradd(name, *cp++);
445 }
446 strcat(name, netcomp);
447 }
448
449 /*
450 * Take a string of network machine id's and separators and
451 * optimize them. We process these by pulling off maximal
452 * leading strings of the same type, passing these to the appropriate
453 * optimizer and concatenating the results.
454 */
455
optim1(netstr,name)456 optim1(netstr, name)
457 char netstr[], name[];
458 {
459 char path[40], rpath[40];
460 register char *cp, *cp2;
461 register int tp, nc;
462
463 cp = netstr;
464 prefer(cp);
465 strcpy(name, "");
466 /*
467 * If the address ultimately points back to us,
468 * just return a null network path.
469 */
470 if (strlen(cp) > 1 && cp[strlen(cp) - 2] == LOCAL)
471 return;
472 while (*cp != 0) {
473 strcpy(path, "");
474 tp = ntype(cp[1]);
475 nc = cp[1];
476 while (*cp && tp == ntype(cp[1])) {
477 stradd(path, *cp++);
478 cp++;
479 }
480 switch (netkind(tp)) {
481 default:
482 strcpy(rpath, path);
483 break;
484
485 case IMPLICIT:
486 optimimp(path, rpath);
487 break;
488
489 case EXPLICIT:
490 optimex(path, rpath);
491 break;
492 }
493 for (cp2 = rpath; *cp2 != 0; cp2++) {
494 stradd(name, *cp2);
495 stradd(name, nc);
496 }
497 }
498 optiboth(name);
499 prefer(name);
500 }
501
502 /*
503 * Return the network of the separator --
504 * AN for arpa net
505 * BN for Bell labs net
506 * SN for Schmidt (berkeley net)
507 * 0 if we don't know.
508 */
509
ntype(nc)510 ntype(nc)
511 register int nc;
512 {
513 register struct ntypetab *np;
514
515 for (np = ntypetab; np->nt_char != 0; np++)
516 if (np->nt_char == nc)
517 return(np->nt_bcode);
518 return(0);
519 }
520
521 /*
522 * Return the kind of routing used for the particular net
523 * EXPLICIT means explicitly routed
524 * IMPLICIT means implicitly routed
525 * 0 means don't know
526 */
527
netkind(nt)528 netkind(nt)
529 register int nt;
530 {
531 register struct nkindtab *np;
532
533 for (np = nkindtab; np->nk_type != 0; np++)
534 if (np->nk_type == nt)
535 return(np->nk_kind);
536 return(0);
537 }
538
539 /*
540 * Do name optimization for an explicitly routed network (eg BTL network).
541 */
542
optimex(net,name)543 optimex(net, name)
544 char net[], name[];
545 {
546 register char *cp, *rp;
547 register int m;
548
549 strcpy(name, net);
550 cp = name;
551 if (strlen(cp) == 0)
552 return(-1);
553 if (cp[strlen(cp)-1] == LOCAL) {
554 name[0] = 0;
555 return(0);
556 }
557 for (cp = name; *cp; cp++) {
558 m = *cp;
559 rp = rindex(cp+1, m);
560 if (rp != NOSTR)
561 strcpy(cp, rp);
562 }
563 return(0);
564 }
565
566 /*
567 * Do name optimization for implicitly routed network (eg, arpanet,
568 * Berkeley network)
569 */
570
optimimp(net,name)571 optimimp(net, name)
572 char net[], name[];
573 {
574 register char *cp;
575 register int m;
576
577 cp = net;
578 if (strlen(cp) == 0)
579 return(-1);
580 m = cp[strlen(cp) - 1];
581 if (m == LOCAL) {
582 strcpy(name, "");
583 return(0);
584 }
585 name[0] = m;
586 name[1] = 0;
587 return(0);
588 }
589
590 /*
591 * Perform global optimization on the given network path.
592 * The trick here is to look ahead to see if there are any loops
593 * in the path and remove them. The interpretation of loops is
594 * more strict here than in optimex since both the machine and net
595 * type must match.
596 */
597
optiboth(net)598 optiboth(net)
599 char net[];
600 {
601 register char *cp, *cp2;
602 char *rpair();
603
604 cp = net;
605 if (strlen(cp) == 0)
606 return;
607 if ((strlen(cp) % 2) != 0) {
608 printf("Strange arg to optiboth\n");
609 return;
610 }
611 while (*cp) {
612 cp2 = rpair(cp+2, *cp);
613 if (cp2 != NOSTR)
614 strcpy(cp, cp2);
615 cp += 2;
616 }
617 }
618
619 /*
620 * Find the rightmost instance of the given (machine, type) pair.
621 */
622
623 char *
rpair(str,mach)624 rpair(str, mach)
625 char str[];
626 {
627 register char *cp, *last;
628
629 cp = str;
630 last = NOSTR;
631 while (*cp) {
632 if (*cp == mach)
633 last = cp;
634 cp += 2;
635 }
636 return(last);
637 }
638
639 /*
640 * Change the network separators in the given network path
641 * to the preferred network transmission means.
642 */
643
prefer(name)644 prefer(name)
645 char name[];
646 {
647 register char *cp;
648 register int state, n;
649
650 state = LOCAL;
651 for (cp = name; *cp; cp += 2) {
652 n = best(state, *cp);
653 if (n)
654 cp[1] = n;
655 state = *cp;
656 }
657 }
658
659 /*
660 * Return the best network separator for the given machine pair.
661 */
662
best(src,dest)663 best(src, dest)
664 {
665 register int dtype, stype;
666 register struct netorder *np;
667
668 stype = nettype(src);
669 dtype = nettype(dest);
670 fflush(stdout);
671 if (stype == 0 || dtype == 0) {
672 printf("ERROR: unknown internal machine id\n");
673 return(0);
674 }
675 if ((stype & dtype) == 0)
676 return(0);
677 np = &netorder[0];
678 while ((np->no_stat & stype & dtype) == 0)
679 np++;
680 return(np->no_char);
681 }
682
683 #ifdef GETHOST
684 /*
685 * Initialize the network name of the current host.
686 */
inithost()687 inithost()
688 {
689 register struct netmach *np;
690 static char host[64];
691
692 gethostname(host, sizeof host);
693 for (np = netmach; np->nt_machine != 0; np++)
694 if (strcmp(np->nt_machine, EMPTY) == 0)
695 break;
696 if (np->nt_machine == 0) {
697 printf("Cannot find empty slot for dynamic host entry\n");
698 exit(1);
699 }
700 np->nt_machine = host;
701 }
702 #endif GETHOST
703
704 /*
705 * Code to twist around arpa net names.
706 */
707
708 #define WORD 257 /* Token for a string */
709
710 static char netbuf[256];
711 static char *yylval;
712
713 /*
714 * Reverse all of the arpa net addresses in the given name to
715 * be of the form "host @ user" instead of "user @ host"
716 * This function is its own inverse.
717 */
718
719 char *
revarpa(str)720 revarpa(str)
721 char str[];
722 {
723
724 if (yyinit(str) < 0)
725 return(NOSTR);
726 if (name())
727 return(NOSTR);
728 if (strcmp(str, netbuf) == 0)
729 return(str);
730 return(savestr(netbuf));
731 }
732
733 /*
734 * Parse (by recursive descent) network names, using the following grammar:
735 * name:
736 * term {':' term}
737 * term {'^' term}
738 * term {'!' term}
739 * term '@' name
740 * term '%' name
741 *
742 * term:
743 * string of characters.
744 */
745
name()746 name()
747 {
748 register int t;
749 register char *cp;
750
751 for (;;) {
752 t = yylex();
753 if (t != WORD)
754 return(-1);
755 cp = yylval;
756 t = yylex();
757 switch (t) {
758 case 0:
759 strcat(netbuf, cp);
760 return(0);
761
762 case '@':
763 case '%':
764 if (name())
765 return(-1);
766 stradd(netbuf, '@');
767 strcat(netbuf, cp);
768 return(0);
769
770 case WORD:
771 return(-1);
772
773 default:
774 strcat(netbuf, cp);
775 stradd(netbuf, t);
776 }
777 }
778 }
779
780 /*
781 * Scanner for network names.
782 */
783
784 static char *charp; /* Current input pointer */
785 static int nexttok; /* Salted away next token */
786
787 /*
788 * Initialize the network name scanner.
789 */
790
yyinit(str)791 yyinit(str)
792 char str[];
793 {
794 static char lexbuf[BUFSIZ];
795
796 netbuf[0] = 0;
797 if (strlen(str) >= sizeof lexbuf - 1)
798 return(-1);
799 nexttok = 0;
800 strcpy(lexbuf, str);
801 charp = lexbuf;
802 return(0);
803 }
804
805 /*
806 * Scan and return a single token.
807 * yylval is set to point to a scanned string.
808 */
809
yylex()810 yylex()
811 {
812 register char *cp, *dot;
813 register int s;
814
815 if (nexttok) {
816 s = nexttok;
817 nexttok = 0;
818 return(s);
819 }
820 cp = charp;
821 while (*cp && isspace(*cp))
822 cp++;
823 if (*cp == 0)
824 return(0);
825 if (any(*cp, metanet)) {
826 charp = cp+1;
827 return(*cp);
828 }
829 dot = cp;
830 while (*cp && !any(*cp, metanet) && !any(*cp, " \t"))
831 cp++;
832 if (any(*cp, metanet))
833 nexttok = *cp;
834 if (*cp == 0)
835 charp = cp;
836 else
837 charp = cp+1;
838 *cp = 0;
839 yylval = dot;
840 return(WORD);
841 }
842