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