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