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 1.2 03/11/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, 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, 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 * opertions 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 strcpy(name, ""); 546 while (*cp != 0) { 547 strcpy(path, ""); 548 tp = ntype(cp[1]); 549 nc = cp[1]; 550 while (*cp && tp == ntype(cp[1])) { 551 stradd(path, *cp++); 552 cp++; 553 } 554 switch (netkind(tp)) { 555 default: 556 strcpy(rpath, path); 557 break; 558 559 case IMPLICIT: 560 optimimp(path, rpath); 561 break; 562 563 case EXPLICIT: 564 optimex(path, rpath); 565 break; 566 } 567 for (cp2 = rpath; *cp2 != 0; cp2++) { 568 stradd(name, *cp2); 569 stradd(name, nc); 570 } 571 } 572 optiboth(name); 573 prefer(name); 574 } 575 576 /* 577 * Return the network of the separator -- 578 * AN for arpa net 579 * BN for Bell labs net 580 * SN for Schmidt (berkeley net) 581 * 0 if we don't know. 582 */ 583 584 ntype(nc) 585 register int nc; 586 { 587 588 switch (nc) { 589 case '^': 590 case '!': 591 return(BN); 592 593 case ':': 594 case '.': 595 return(SN); 596 597 case '@': 598 case '%': 599 return(AN); 600 601 default: 602 return(0); 603 } 604 /* NOTREACHED */ 605 } 606 607 /* 608 * Return the kind of routing used for the particular net 609 * EXPLICIT means explicitly routed 610 * IMPLICIT means implicitly routed 611 * 0 means don't know 612 */ 613 614 netkind(nt) 615 register int nt; 616 { 617 618 switch (nt) { 619 case BN: 620 return(EXPLICIT); 621 622 case AN: 623 case SN: 624 return(IMPLICIT); 625 626 default: 627 return(0); 628 } 629 /* NOTREACHED */ 630 } 631 632 /* 633 * Do name optimization for an explicitly routed network (eg BTL network). 634 */ 635 636 optimex(net, name) 637 char net[], name[]; 638 { 639 register char *cp, *rp; 640 register int m; 641 char *rindex(); 642 643 strcpy(name, net); 644 cp = name; 645 if (strlen(cp) == 0) 646 return(-1); 647 if (cp[strlen(cp)-1] == LOCAL) { 648 name[0] = 0; 649 return(0); 650 } 651 for (cp = name; *cp; cp++) { 652 m = *cp; 653 rp = rindex(cp+1, m); 654 if (rp != NOSTR) 655 strcpy(cp, rp); 656 } 657 return(0); 658 } 659 660 /* 661 * Do name optimization for implicitly routed network (eg, arpanet, 662 * Berkeley network) 663 */ 664 665 optimimp(net, name) 666 char net[], name[]; 667 { 668 register char *cp; 669 register int m; 670 671 cp = net; 672 if (strlen(cp) == 0) 673 return(-1); 674 m = cp[strlen(cp) - 1]; 675 if (m == LOCAL) { 676 strcpy(name, ""); 677 return(0); 678 } 679 name[0] = m; 680 name[1] = 0; 681 return(0); 682 } 683 684 /* 685 686 * Perform global optimization on the given network path. 687 * The trick here is to look ahead to see if there are any loops 688 * in the path and remove them. The interpretation of loops is 689 * more strict here than in optimex since both the machine and net 690 * type must match. 691 */ 692 693 optiboth(net) 694 char net[]; 695 { 696 register char *cp, *cp2; 697 char *rpair(); 698 699 cp = net; 700 if (strlen(cp) == 0) 701 return; 702 if ((strlen(cp) % 2) != 0) { 703 printf("Strange arg to optiboth\n"); 704 return; 705 } 706 while (*cp) { 707 cp2 = rpair(cp+2, *cp); 708 if (cp2 != NOSTR) 709 strcpy(cp, cp2); 710 cp += 2; 711 } 712 } 713 714 /* 715 * Find the rightmost instance of the given (machine, type) pair. 716 */ 717 718 char * 719 rpair(str, mach) 720 char str[]; 721 { 722 register char *cp, *last; 723 724 last = NOSTR; 725 while (*cp) { 726 if (*cp == mach) 727 last = cp; 728 cp += 2; 729 } 730 return(last); 731 } 732 733 /* 734 * Change the network separators in the given network path 735 * to the preferred network transmission means. 736 */ 737 738 prefer(name) 739 char name[]; 740 { 741 register char *cp; 742 register int state, n; 743 744 state = LOCAL; 745 for (cp = name; *cp; cp += 2) { 746 n = best(state, *cp); 747 if (n) 748 cp[1] = n; 749 state = *cp; 750 } 751 } 752 753 /* 754 * Return the best network separator for the given machine pair. 755 */ 756 757 struct netorder { 758 short no_stat; 759 char no_char; 760 } netorder[] = { 761 CN, ':', 762 AN, '@', 763 AN, '%', 764 SN, ':', 765 BN, '!', 766 -1, 0 767 }; 768 769 best(src, dest) 770 { 771 register int dtype, stype; 772 register struct netorder *np; 773 774 stype = nettype(src); 775 dtype = nettype(dest); 776 if (stype == 0 || dtype == 0) { 777 printf("ERROR: unknown internal machine id\n"); 778 return(0); 779 } 780 if ((stype & dtype) == 0) { 781 #ifdef DELIVERMAIL 782 if (src != LOCAL) 783 #endif 784 printf("No way to get from \"%s\" to \"%s\"\n", 785 netname(src), netname(dest)); 786 return(0); 787 } 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