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