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