minsk.c

   1 /*
   2  *      Minsk-2 Emulator
   3  *
   4  *      (c) 2010 Martin Mares <mj@ucw.cz>
   5  */
   6
   7 /*
   8  * TODO:
   9  *      - we probably have to disable NOP
  10  */
  11
  12 /*
  13  * Things that are not implemented:
  14  *
  15  *      - rounding modes
  16  *      - exact behavior of accumulator/R1/R2 (the manual lacks details)
  17  *      - exact behavior of negative zero
  18  *      - I/O instructions for devices that are not emulated (paper tape
  19  *        reader and puncher, card reader and puncher, magnetic tape unit)
  20  */
  21
  22 #define _GNU_SOURCE
  23
  24 #include <stdio.h>
  25 #include <string.h>
  26 #include <stdlib.h>
  27 #include <stdarg.h>
  28 #include <inttypes.h>
  29 #include <assert.h>
  30 #include <math.h>
  31
  32 static int trace;
  33 static int cpu_quota = -1;
  34 static int print_quota = -1;
  35 static void (*error_hook)(char *msg);
  36
  37 // Minsk-2 has 37-bit words in sign-magnitude representation (bit 36 = sign)
  38 typedef unsigned long long int word;
  39
  40 #define WORD_MASK 01777777777777ULL
  41 #define SIGN_MASK 01000000000000ULL
  42 #define  VAL_MASK 00777777777777ULL
  43
  44 static int wsign(word w)
  45 {
  46   return (w & SIGN_MASK) ? -1 : 1;
  47 }
  48
  49 static word wabs(word w)
  50 {
  51   return w & VAL_MASK;
  52 }
  53
  54 #define WF(w) (wsign(w) < 0 ? '-' : '+'), wabs(w)
  55
  56 static long long wtoll(word w)
  57 {
  58   if (wsign(w) < 0)
  59     return -wabs(w);
  60   else
  61     return wabs(w);
  62 }
  63
  64 static word wfromll(long long x)
  65 {
  66   word w = ((x < 0) ? -x : x) & VAL_MASK;
  67   if (x < 0)
  68     w |= SIGN_MASK;
  69   return w;
  70 }
  71
  72 static double wtofrac(word w)
  73 {
  74   return (double)wtoll(w) / (double)(1ULL << 36);
  75 }
  76
  77 static word wfromfrac(double d)
  78 {
  79   return wfromll((long long)(d * (double)(1ULL << 36)));
  80 }
  81
  82 static int int_in_range(long long x)
  83 {
  84   return (x >= -(long long)VAL_MASK && x <= (long long)VAL_MASK);
  85 }
  86
  87 static int frac_in_range(double d)
  88 {
  89   return (d > -1. && d < 1.);
  90 }
  91
  92 static int wexp(word w)
  93 {
  94   int exp = w & 077;
  95   return (w & 0100 ? -exp : exp);
  96 }
  97
  98 static word wputexp(word w, int exp)
  99 {
 100   return ((w & ~(word)0177) | ((exp < 0) ? 0100 | (-exp) : exp));
 101 }
 102
 103 static int wmanti(word w)
 104 {
 105   return ((w >> 8) & ((1 << 28) - 1));
 106 }
 107
 108 static double wtofloat(word w)
 109 {
 110   double x = wmanti(w);
 111   return ldexp(x, wexp(w) - 28);
 112 }
 113
 114 static int float_in_range(double x)
 115 {
 116   x = fabs(x);
 117   return (x <= ldexp((1 << 28) - 1, 63 - 28));
 118 }
 119
 120 static word wfromfloat(double x, int normalized)
 121 {
 122   word w = 0;
 123   if (x < 0)
 124     {
 125       w |= SIGN_MASK;
 126       x = -x;
 127     }
 128   int exp;
 129   double m = frexp(x, &exp);
 130   word mm = (word) ldexp(m, 28);
 131   if (exp > 63)
 132     assert(0);
 133   else if (exp < -63)
 134     {
 135       if (normalized || exp < -91)
 136         mm=0, exp=0;
 137       else
 138         {
 139           mm >>= -exp - 63;
 140           exp = -63;
 141         }
 142     }
 143   w |= mm << 8;
 144   if (exp < 0)
 145     {
 146       w |= 0100;
 147       exp = -exp;
 148     }
 149   w |= exp;
 150   return w;
 151 }
 152
 153 static word mem[4096];
 154
 155 static word rd(int addr)
 156 {
 157   word val = addr ? mem[addr] : 0;
 158   if (trace > 2)
 159     printf("\tRD %04o = %c%012llo\n", addr, WF(val));
 160   return val;
 161 }
 162
 163 static void wr(int addr, word val)
 164 {
 165   assert(!(val & ~(WORD_MASK)));
 166   if (trace > 2)
 167     printf("\tWR %04o = %c%012llo\n", addr, WF(val));
 168   mem[addr] = val;
 169 }
 170
 171 static int lino;
 172
 173 static void parse_error(char *msg)
 174 {
 175   if (error_hook)
 176     error_hook("Parse error");
 177   printf("Ошибка входа (стр. %d): %s\n", lino, msg);
 178   exit(0);
 179 }
 180
 181 static void parse_in(void)
 182 {
 183   char line[80];
 184   int addr = 0;
 185
 186   while (fgets(line, sizeof(line), stdin))
 187     {
 188       lino++;
 189       char *eol = strchr(line, '\n');
 190       if (!eol)
 191         parse_error("Строка слишком долгая");
 192       *eol = 0;
 193
 194       char *c = line;
 195       if (!c[0] || c[0] == ';')
 196         continue;
 197       if (c[0] == '@')
 198         {
 199           c++;
 200           addr = 0;
 201           for (int i=0; i<4; i++)
 202             {
 203               while (*c == ' ')
 204                 c++;
 205               if (*c >= '0' && *c <= '7')
 206                 addr = 8*addr + *c++ - '0';
 207               else
 208                 parse_error("Плохая цифра");
 209             }
 210           while (*c == ' ')
 211             c++;
 212           if (*c)
 213             parse_error("Адрес слишком долгий");
 214           continue;
 215         }
 216
 217       word w = 0;
 218       if (*c == '-')
 219         w = 1;
 220       else if (*c != '+')
 221         parse_error("Плохой знак");
 222       c++;
 223       for (int i=0; i<12; i++)
 224         {
 225           while (*c == ' ')
 226             c++;
 227           if (*c >= '0' && *c <= '7')
 228             w = 8*w + *c++ - '0';
 229           else
 230             parse_error("Плохая цифра");
 231         }
 232       while (*c == ' ')
 233         c++;
 234       if (*c)
 235         parse_error("Номер слишком долгий");
 236       wr(addr++, w);
 237       addr &= 07777;
 238     }
 239 }
 240
 241 static word acc;
 242 static word r1, r2, current_ins;
 243 static int ip = 00050;                  // Standard program start location
 244 static int prev_ip;
 245
 246 static void stop(char *reason, char *notice)
 247 {
 248   if (error_hook)
 249     error_hook(notice);
 250   printf("Машина остановлена -- %s\n", reason);
 251   printf("СчАК:%04o См:%c%012llo Р1:%c%012llo Р2:%c%012llo\n", prev_ip, WF(acc), WF(r1), WF(r2));
 252   exit(0);
 253 }
 254
 255 static void over(void)
 256 {
 257   stop("Аварийный останов", "Overflow");
 258 }
 259
 260 static void notimp(void)
 261 {
 262   acc = current_ins;
 263   stop("Устройство разбитое", "Not implemented");
 264 }
 265
 266 static void noins(void)
 267 {
 268   acc = current_ins;
 269   stop("Эту команду не знаю", "Illegal instruction");
 270 }
 271
 272 static uint16_t linebuf[128];
 273
 274 static uint16_t russian_chars[64] = {
 275         '0',    '1',    '2',    '3',    '4',    '5',    '6',    '7',    // 0x
 276         '8',    '9',    '+',    '-',    '/',    ',',    '.',    ' ',    // 1x
 277         0x2169, '^',    '(',    ')',    0x00d7, '=',    ';',    '[',    // 2x
 278         ']',    '*',    '`',    '\'',   0x2260, '<',    '>',    ':',    // 3x
 279         0x410,  0x411,  0x412,  0x413,  0x414,  0x415,  0x416,  0x417,  // 4x
 280         0x418,  0x419,  0x41a,  0x41b,  0x41c,  0x41d,  0x41e,  0x41f,  // 5x
 281         0x420,  0x421,  0x422,  0x423,  0x424,  0x425,  0x426,  0x427,  // 6x
 282         0x428,  0x429,  0x42b,  0x42c,  0x42d,  0x42e,  0x42f,  0x2013  // 7x
 283 };
 284
 285 static uint16_t latin_chars[64] = {
 286         '0',    '1',    '2',    '3',    '4',    '5',    '6',    '7',    // 0x
 287         '8',    '9',    '+',    '-',    '/',    ',',    '.',    ' ',    // 1x
 288         0x2169, '^',    '(',    ')',    0x00d7, '=',    ';',    '[',    // 2x
 289         ']',    '*',    '`',    '\'',   0x2260, '<',    '>',    ':',    // 3x
 290         'A',    'B',    'W',    'G',    'D',    'E',    'V',    'Z',    // 4x
 291         'I',    'J',    'K',    'L',    'M',    'N',    'O',    'P',    // 5x
 292         'R',    'S',    'T',    'U',    'F',    'H',    'C',    ' ',    // 6x
 293         ' ',    ' ',    'Y',    'X',    ' ',    ' ',    'Q',    0x2013  // 7x
 294 };
 295
 296 static void print_line(int r)
 297 {
 298   /*
 299    *  Meaning of bits of r:
 300    *    0 = perform line feed
 301    *    1 = clear buffer
 302    *    2 = actually print
 303    */
 304   if (r & 4)
 305     {
 306       if (print_quota > 0 && !--print_quota)
 307         stop("Бумага дошла - нужно ехать в Сибирь про новую", "Out of paper");
 308       for (int i=0; i<128; i++)
 309         {
 310           int ch = linebuf[i];
 311           if (!ch)
 312             ch = ' ';
 313           if (ch < 0x80)
 314             putchar(ch);
 315           else if (ch < 0x800)
 316             {
 317               putchar(0xc0 | (ch >> 6));
 318               putchar(0x80 | (ch & 0x3f));
 319             }
 320           else
 321             {
 322               putchar(0xe0 | (ch >> 12));
 323               putchar(0x80 | ((ch >> 6) & 0x3f));
 324               putchar(0x80 | (ch & 0x3f));
 325             }
 326         }
 327     }
 328   if (r & 2)
 329     memset(linebuf, 0, sizeof(linebuf));
 330   if (r & 1)
 331     putchar('\n');
 332   else if (r & 4)
 333     putchar('\r');
 334   fflush(stdout);
 335 }
 336
 337 static void print_ins(int x, int y)
 338 {
 339   word yy = rd(y);
 340   int pos = x & 0177;
 341   int r = (x >> 9) & 7;
 342
 343   if (x & 0400)
 344     {
 345       print_line(r);
 346       return;
 347     }
 348
 349   char *fmt;
 350   int bit = 37;
 351   int eat = 0;
 352   switch (r)
 353     {
 354     case 0:                             // Decimal float
 355       fmt = "+dddddddx+xbd";
 356       break;
 357     case 1:                             // Octal number
 358       fmt = "+oooooooooooo";
 359       break;
 360     case 2:                             // Decimal fixed
 361       fmt = "+ddddddddd";
 362       break;
 363     case 3:                             // Decimal unsigned
 364       fmt = "x ddddddddd";
 365       eat = 1;
 366       break;
 367     case 4:                             // One Russian symbol
 368       bit = 6;
 369       fmt = "r";
 370       break;
 371     case 5:                             // Russian text
 372       fmt = "xrrrrrr";
 373       break;
 374     case 6:                             // One Latin symbol
 375       bit = 6;
 376       fmt = "l";
 377       break;
 378     default:                            // Latin text
 379       fmt = "xllllll";
 380     }
 381
 382   while (*fmt)
 383     {
 384       int ch;
 385       switch (*fmt++)
 386         {
 387         case 'x':
 388           bit--;
 389           continue;
 390         case ' ':
 391           ch = ' ';
 392           break;
 393         case '+':
 394           bit--;
 395           ch = (yy & (1ULL << bit)) ? '-' : '+';
 396           break;
 397         case 'b':
 398           bit--;
 399           ch = '0' + ((yy >> bit) & 1);
 400           break;
 401         case 'o':
 402           bit -= 3;
 403           ch = '0' + ((yy >> bit) & 7);
 404           break;
 405         case 'd':
 406           bit -= 4;
 407           ch = '0' + ((yy >> bit) & 15);
 408           if (ch > '0' + 9)
 409             ch += 7;
 410           break;
 411         case 'r':
 412           bit -= 6;
 413           ch = russian_chars[(yy >> bit) & 077];
 414           break;
 415         case 'l':
 416           bit -= 6;
 417           ch = latin_chars[(yy >> bit) & 077];
 418           break;
 419         default:
 420           assert(0);
 421         }
 422
 423       if (eat && *fmt)
 424         {
 425           if (ch == '0' || ch == ' ')
 426             ch = ' ';
 427           else
 428             eat = 0;
 429         }
 430       linebuf[pos] = ch;
 431       pos = (pos+1) & 0177;
 432     }
 433   assert(!bit);
 434 }
 435
 436 static void run(void)
 437 {
 438   for (;;)
 439     {
 440       r2 = acc;
 441       prev_ip = ip;
 442       word w = mem[ip];
 443       current_ins = w;
 444
 445       int op = (w >> 30) & 0177;        // Operation code
 446       int ax = (w >> 28) & 3;           // Address extensions not supported
 447       int ix = (w >> 24) & 15;          // Indexing
 448       int x = (w >> 12) & 07777;        // Operands (original form)
 449       int y = w & 07777;
 450       int xi=x, yi=y;                   // (indexed form)
 451       if (trace)
 452         printf("@%04o  %c%02o %02o %04o %04o\n",
 453           ip,
 454           (w & SIGN_MASK) ? '-' : '+',
 455           (int)((w >> 30) & 077),
 456           (int)((w >> 24) & 077),
 457           x,
 458           y);
 459       if (ix)
 460         {
 461           if (op != 0120)
 462             {
 463               word i = rd(ix);
 464               xi = (xi + (int)((i >> 12) & 07777)) & 07777;
 465               yi = (yi + (int)(i & 07777)) & 07777;
 466               if (trace > 2)
 467                 printf("\tIndexing -> %04o %04o\n", xi, yi);
 468             }
 469         }
 470       ip = (ip+1) & 07777;
 471
 472       if (cpu_quota > 0 && !--cpu_quota)
 473         stop("Тайм-аут", "CPU quota exceeded");
 474
 475       /* Arithmetic operations */
 476
 477       word a, b, c;
 478       long long aa, bb, cc;
 479       double ad, bd;
 480       int i;
 481
 482       auto void afetch(void);
 483       void afetch(void)
 484         {
 485           if (op & 2)
 486             a = r2;
 487           else
 488             a = rd(yi);
 489           b = r1 = rd(xi);
 490         }
 491
 492       auto void astore(word result);
 493       void astore(word result)
 494         {
 495           acc = result;
 496           if (op & 1)
 497             wr(yi, acc);
 498         }
 499
 500       auto void astore_int(long long x);
 501       void astore_int(long long x)
 502         {
 503           if (!int_in_range(x))
 504             over();
 505           astore(wfromll(x));
 506         }
 507
 508       auto void astore_frac(double f);
 509       void astore_frac(double f)
 510         {
 511           if (!frac_in_range(f))
 512             over();
 513           astore(wfromfrac(f));
 514         }
 515
 516       auto void astore_float(double f);
 517       void astore_float(double f)
 518         {
 519           if (!float_in_range(f))
 520             over();
 521           astore(wfromfloat(f, 0));
 522         }
 523
 524       if (ax)
 525         op = -1;
 526       switch (op)
 527         {
 528         case 000:               // NOP
 529           break;
 530         case 004 ... 007:       // XOR
 531           afetch();
 532           astore(a^b);
 533           break;
 534         case 010 ... 013:       // FIX addition
 535           afetch();
 536           astore_int(wtoll(a) + wtoll(b));
 537           break;
 538         case 014 ... 017:       // FP addition
 539           afetch();
 540           astore_float(wtofloat(a) + wtofloat(b));
 541           break;
 542         case 020 ... 023:       // FIX subtraction
 543           afetch();
 544           astore_int(wtoll(a) - wtoll(b));
 545           break;
 546         case 024 ... 027:       // FP subtraction
 547           afetch();
 548           astore_float(wtofloat(a) - wtofloat(b));
 549           break;
 550         case 030 ... 033:       // FIX multiplication
 551           afetch();
 552           astore_frac(wtofrac(a) * wtofrac(b));
 553           break;
 554         case 034 ... 037:       // FP multiplication
 555           afetch();
 556           astore_float(wtofloat(a) * wtofloat(b));
 557           break;
 558         case 040 ... 043:       // FIX division
 559           afetch();
 560           ad = wtofrac(a);
 561           bd = wtofrac(b);
 562           if (!wabs(b))
 563             over();
 564           astore_frac(ad / bd);
 565           break;
 566         case 044 ... 047:       // FP division
 567           afetch();
 568           ad = wtofloat(a);
 569           bd = wtofloat(b);
 570           if (!bd || wexp(b) < -63)
 571             over();
 572           astore_float(ad / bd);
 573           break;
 574         case 050 ... 053:       // FIX subtraction of abs values
 575           afetch();
 576           astore_int(wabs(a) - wabs(b));
 577           break;
 578         case 054 ... 057:       // FP subtraction of abs values
 579           afetch();
 580           astore_float(fabs(wtofloat(a)) - fabs(wtofloat(b)));
 581           break;
 582         case 060 ... 063:       // Shift logical
 583           afetch();
 584           i = wexp(b);
 585           if (i <= -37 || i >= 37)
 586             astore(0);
 587           else if (i >= 0)
 588             astore((a << i) & WORD_MASK);
 589           else
 590             astore(a >> (-i));
 591           break;
 592         case 064 ... 067:       // Shift arithmetical
 593           afetch();
 594           i = wexp(b);
 595           aa = wabs(a);
 596           if (i <= -36 || i >= 36)
 597             cc = 0;
 598           else if (i >= 0)
 599             cc = (aa << i) & VAL_MASK;
 600           else
 601             cc = aa >> (-i);
 602           astore((a & SIGN_MASK) | wfromll(cc));
 603           break;
 604         case 070 ... 073:       // And
 605           afetch();
 606           astore(a&b);
 607           break;
 608         case 074 ... 077:       // Or
 609           afetch();
 610           astore(a|b);
 611           break;
 612
 613         case 0100:              // Halt
 614           r1 = rd(x);
 615           acc = rd(y);
 616           stop("Останов машины", "Halted");
 617         case 0103:              // I/O magtape
 618           notimp();
 619         case 0104:              // Disable rounding
 620           notimp();
 621         case 0105:              // Enable rounding
 622           notimp();
 623         case 0106:              // Interrupt control
 624           notimp();
 625         case 0107:              // Reverse tape
 626           notimp();
 627         case 0110:              // Move
 628           wr(yi, r1 = acc = rd(xi));
 629           break;
 630         case 0111:              // Move negative
 631           wr(yi, acc = (r1 = rd(xi)) ^ SIGN_MASK);
 632           break;
 633         case 0112:              // Move absolute value
 634           wr(yi, acc = (r1 = rd(xi)) & VAL_MASK);
 635           break;
 636         case 0113:              // Read from keyboard
 637           notimp();
 638         case 0114:              // Copy sign
 639           wr(yi, acc = rd(yi) ^ ((r1 = rd(xi)) & SIGN_MASK));
 640           break;
 641         case 0115:              // Read code from R1 (obscure)
 642           notimp();
 643         case 0116:              // Copy exponent
 644           wr(yi, acc = wputexp(rd(yi), wexp(r1 = rd(xi))));
 645           break;
 646         case 0117:              // I/O teletype
 647           notimp();
 648         case 0120:              // Loop
 649           if (!ix)
 650             noins();
 651           a = r1 = rd(ix);
 652           aa = (a >> 24) & 017777;
 653           if (!aa)
 654             break;
 655           b = rd(y);            // (a mountain range near Prague)
 656           acc = ((aa-1) << 24) |
 657                 (((((a >> 12) & 07777) + (b >> 12) & 07777) & 07777) << 12) |
 658                 (((a & 07777) + (b & 07777)) & 07777);
 659           wr(ix, acc);
 660           ip = x;
 661           break;
 662         case 0130:              // Jump
 663           wr(y, r2);
 664           ip = x;
 665           break;
 666         case 0131:              // Jump to subroutine
 667           wr(y, acc = ((030ULL << 30) | ((ip & 07777ULL) << 12)));
 668           ip = x;
 669           break;
 670         case 0132:              // Jump if positive
 671           if (wsign(r2) >= 0)
 672             ip = x;
 673           else
 674             ip = y;
 675           break;
 676         case 0133:              // Jump if overflow
 677           // Since we always trap on overflow, this instruction always jumps to the 1st address
 678           ip = x;
 679           break;
 680         case 0134:              // Jump if zero
 681           if (!wabs(r2))
 682             ip = y;
 683           else
 684             ip = x;
 685           break;
 686         case 0135:              // Jump if key pressed
 687           // No keys are ever pressed, so always jump to 2nd
 688           ip = y;
 689           break;
 690         case 0136:              // Interrupt masking
 691           notimp();
 692         case 0137:              // Used only when reading from tape
 693           notimp();
 694         case 0140 ... 0147:     // I/O
 695           notimp();
 696         case 0150 ... 0154:     // I/O
 697           notimp();
 698         case 0160 ... 0161:     // I/O
 699           notimp();
 700         case 0162:              // Printing
 701           print_ins(x, y);
 702           break;
 703         case 0163:              // I/O
 704           notimp();
 705         case 0170:              // FIX multiplication, bottom part
 706           afetch();
 707           if (wtofrac(a) * wtofrac(b) >= .1/(1ULL << 32))
 708             over();
 709           acc = wfromll(((unsigned long long)wabs(a) * (unsigned long long)wabs(b)) & VAL_MASK);
 710           // XXX: What should be the sign? The book does not define that.
 711           break;
 712         case 0171:              // Modulo
 713           afetch();
 714           aa = wabs(a);
 715           bb = wabs(b);
 716           if (!bb)
 717             over();
 718           cc = aa % bb;
 719           if (wsign(b) < 0)
 720             cc = -cc;
 721           acc = wfromll(cc);
 722           break;
 723         case 0172:              // Add exponents
 724           a = r1 = rd(xi);
 725           b = rd(yi);
 726           i = wexp(a) + wexp(b);
 727           if (i < -63 || i > 63)
 728             over();
 729           acc = wputexp(b, i);
 730           wr(yi, acc);
 731           break;
 732         case 0173:              // Sub exponents
 733           a = r1 = rd(xi);
 734           b = rd(yi);
 735           i = wexp(b) - wexp(a);
 736           if (i < -63 || i > 63)
 737             over();
 738           acc = wputexp(b, i);
 739           wr(yi, acc);
 740           break;
 741         case 0174:              // Addition in one's complement
 742           a = r1 = rd(xi);
 743           b = rd(yi);
 744           c = a + b;
 745           if (c > VAL_MASK)
 746             c = c - VAL_MASK;
 747           wr(yi, c);
 748           // XXX: The effect on the accumulator is undocumented, but likely to be as follows:
 749           acc = c;
 750           break;
 751         case 0175:              // Normalization
 752           a = r1 = rd(xi);
 753           if (!wabs(a))
 754             {
 755               wr(yi, 0);
 756               wr((yi+1) & 07777, 0);
 757               acc = 0;
 758             }
 759           else
 760             {
 761               i = 0;
 762               acc = a & SIGN_MASK;
 763               a &= VAL_MASK;
 764               while (!(a & (SIGN_MASK >> 1)))
 765                 {
 766                   a <<= 1;
 767                   i++;
 768                 }
 769               acc |= a;
 770               wr(yi, acc);
 771               wr((yi+1) & 07777, i);
 772             }
 773           break;
 774         case 0176:              // Population count
 775           a = r1 = rd(xi);
 776           cc = 0;
 777           for (int i=0; i<36; i++)
 778             if (a & (1ULL << i))
 779               cc++;
 780           // XXX: Guessing that acc gets a copy of the result
 781           acc = wfromll(cc);
 782           wr(yi, acc);
 783           break;
 784         default:
 785           noins();
 786         }
 787
 788       if (trace > 1)
 789         printf("\tACC:%c%012llo R1:%c%012llo R2:%c%012llo\n", WF(acc), WF(r1), WF(r2));
 790     }
 791 }
 792
 793 /*** Daemon interface ***/
 794
 795 #include <unistd.h>
 796 #include <errno.h>
 797 #include <time.h>
 798 #include <syslog.h>
 799 #include <sys/signal.h>
 800 #include <sys/wait.h>
 801 #include <sys/poll.h>
 802 #include <sys/socket.h>
 803 #include <netinet/in.h>
 804 #include <arpa/inet.h>
 805
 806 #if 0
 807 #define DTRACE(msg, args...) fprintf(stderr, msg "\n", ##args)
 808 #define DLOG(msg, args...) fprintf(stderr, msg "\n", ##args)
 809 #else
 810 #define DTRACE(msg, args...) do { } while(0)
 811 #define DLOG(msg, args...) syslog(LOG_INFO, msg, ##args)
 812 #endif
 813
 814 #define MAX_CONNECTIONS 50              // Per daemon
 815 #define MAX_CONNS_PER_IP 1              // Per IP
 816 #define MAX_TRACKERS 200                // IP address trackers
 817 #define TBF_MAX 5                       // Max number of tokens in the bucket
 818 #define TBF_REFILL_PER_SEC 0.2          // Bucket refill rate (buckets/sec)
 819
 820 #define PID_FILE "/var/run/minsk.pid"
 821 #define UID 65534
 822 #define GID 65534
 823
 824 static void die(char *msg)
 825 {
 826   fprintf(stderr, "minsk: ");
 827   fprintf(stderr, msg);
 828   fputc('\n', stderr);
 829   exit(1);
 830 }
 831
 832 static char **spt_argv;
 833 static char *spt_start, *spt_end;
 834
 835 static void setproctitle_init(int argc, char **argv)
 836 {
 837   int i, len;
 838   char **env, **oldenv, *t;
 839
 840   spt_argv = argv;
 841
 842   /* Create a backup copy of environment */
 843   oldenv = __environ;
 844   len = 0;
 845   for (i=0; oldenv[i]; i++)
 846     len += strlen(oldenv[i]) + 1;
 847   __environ = env = malloc(sizeof(char *)*(i+1));
 848   t = malloc(len);
 849   if (!__environ || !t)
 850     die("malloc failed");
 851   for (i=0; oldenv[i]; i++)
 852     {
 853       env[i] = t;
 854       len = strlen(oldenv[i]) + 1;
 855       memcpy(t, oldenv[i], len);
 856       t += len;
 857     }
 858   env[i] = NULL;
 859
 860   /* Scan for consecutive free space */
 861   spt_start = spt_end = argv[0];
 862   for (i=0; i<argc; i++)
 863     if (!i || spt_end+1 == argv[i])
 864       spt_end = argv[i] + strlen(argv[i]);
 865   for (i=0; oldenv[i]; i++)
 866     if (spt_end+1 == oldenv[i])
 867       spt_end = oldenv[i] + strlen(oldenv[i]);
 868 }
 869
 870 static void
 871 setproctitle(const char *msg, ...)
 872 {
 873   va_list args;
 874   char buf[256];
 875   int n;
 876
 877   va_start(args, msg);
 878   if (spt_end > spt_start)
 879     {
 880       n = vsnprintf(buf, sizeof(buf), msg, args);
 881       if (n >= (int) sizeof(buf) || n < 0)
 882         sprintf(buf, "<too-long>");
 883       n = spt_end - spt_start;
 884       strncpy(spt_start, buf, n);
 885       spt_start[n] = 0;
 886       spt_argv[0] = spt_start;
 887       spt_argv[1] = NULL;
 888     }
 889   va_end(args);
 890 }
 891
 892 static void sigchld_handler(int sig __attribute__((unused)))
 893 {
 894 }
 895
 896 static void sigalrm_handler(int sig __attribute__((unused)))
 897 {
 898   const char err[] = "--- Timed out. Time machine disconnected. ---\n";
 899   write(1, err, sizeof(err));
 900   DLOG("Connection timed out");
 901   exit(0);
 902 }
 903
 904 static void child_error_hook(char *err)
 905 {
 906   DLOG("Stopped: %s", err);
 907 }
 908
 909 static void child(int sk2)
 910 {
 911   dup2(sk2, 0);
 912   dup2(sk2, 1);
 913   close(sk2);
 914
 915   struct sigaction sact = {
 916     .sa_handler = sigalrm_handler,
 917   };
 918   if (sigaction(SIGALRM, &sact, NULL) < 0)
 919     die("sigaction: %m");
 920
 921   // Set up limits
 922   alarm(60);
 923   cpu_quota = 100000;
 924   print_quota = 100;
 925
 926   const char welcome[] = "+++ Welcome to our computer museum. +++\n+++ Our time machine will connect you to one of our exhibits. +++\n\n";
 927   write(1, welcome, sizeof(welcome));
 928
 929   error_hook = child_error_hook;
 930   parse_in();
 931   run();
 932   fflush(stdout);
 933   DTRACE("Finished");
 934 }
 935
 936 struct conn {
 937   pid_t pid;
 938   struct in_addr addr;
 939   struct tracker *tracker;
 940 };
 941
 942 static struct conn connections[MAX_CONNECTIONS];
 943
 944 static struct conn *get_conn(struct in_addr *a)
 945 {
 946   for (int i=0; i<MAX_CONNECTIONS; i++)
 947     {
 948       struct conn *c = &connections[i];
 949       if (!c->pid)
 950         {
 951           memcpy(&c->addr, a, sizeof(struct in_addr));
 952           return c;
 953         }
 954     }
 955   return NULL;
 956 }
 957
 958 static struct conn *pid_to_conn(pid_t pid)
 959 {
 960   for (int i=0; i<MAX_CONNECTIONS; i++)
 961     {
 962       struct conn *c = &connections[i];
 963       if (c->pid == pid)
 964         return c;
 965     }
 966   return NULL;
 967 }
 968
 969 static void put_conn(struct conn *c)
 970 {
 971   c->pid = 0;
 972   c->tracker = NULL;
 973 }
 974
 975 struct tracker {
 976   struct in_addr addr;
 977   int active_conns;
 978   time_t last_access;
 979   double tokens;
 980 };
 981
 982 static struct tracker trackers[MAX_TRACKERS];
 983
 984 static int get_tracker(struct conn *c)
 985 {
 986   struct tracker *t;
 987   time_t now = time(NULL);
 988   int i;
 989
 990   for (i=0; i<MAX_TRACKERS; i++)
 991     {
 992       t = &trackers[i];
 993       if (!memcmp(&t->addr, &c->addr, sizeof(struct in_addr)))
 994         break;
 995     }
 996   if (i < MAX_TRACKERS)
 997     {
 998       if (now > t->last_access)
 999         {
1000           t->tokens += (now - t->last_access) * (double) TBF_REFILL_PER_SEC;
1001           t->last_access = now;
1002           if (t->tokens > TBF_MAX)
1003             t->tokens = TBF_MAX;
1004         }
1005       DTRACE("TBF: Using tracker %d (%.3f tokens)", i, t->tokens);
1006     }
1007   else
1008     {
1009       int min_i = -1;
1010       for (int i=0; i<MAX_TRACKERS; i++)
1011         {
1012           t = &trackers[i];
1013           if (!t->active_conns && (min_i < 0 || t->last_access < trackers[min_i].last_access))
1014             min_i = i;
1015         }
1016       if (min_i < 0)
1017         {
1018           DLOG("TBF: Out of trackers!");
1019           return 0;
1020         }
1021       t = &trackers[min_i];
1022       if (t->last_access)
1023         DTRACE("TBF: Recycling tracker %d", min_i);
1024       else
1025         DTRACE("TBF: Creating tracker %d", min_i);
1026       memset(t, 0, sizeof(*t));
1027       t->addr = c->addr;
1028       t->last_access = now;
1029       t->tokens = TBF_MAX;
1030     }
1031
1032   if (t->active_conns >= MAX_CONNS_PER_IP)
1033     {
1034       DTRACE("TBF: Too many conns per IP");
1035       return 0;
1036     }
1037
1038   if (t->tokens >= 0.999)
1039     {
1040       t->tokens -= 1;
1041       t->active_conns++;
1042       c->tracker = t;
1043       DTRACE("TBF: Passed (%d conns)", t->active_conns);
1044       return 1;
1045     }
1046   else
1047     {
1048       DTRACE("TBF: Failed");
1049       t->tokens = 0;
1050       return 0;
1051     }
1052 }
1053
1054 static void put_tracker(struct conn *c)
1055 {
1056   struct tracker *t = c->tracker;
1057   if (!t)
1058     {
1059       DLOG("put_tracker: no tracker?");
1060       sleep(5);
1061       return;
1062     }
1063   if (t->active_conns <= 0)
1064     {
1065       DLOG("put_tracker: no counter?");
1066       sleep(5);
1067       return;
1068     }
1069   t->active_conns--;
1070   DTRACE("TBF: Put tracker (%d conns remain)", t->active_conns);
1071 }
1072
1073 static void run_as_daemon(int do_fork)
1074 {
1075   int sk = socket(PF_INET, SOCK_STREAM, IPPROTO_TCP);
1076   if (sk < 0)
1077     die("socket: %m");
1078
1079   int one = 1;
1080   if (setsockopt(sk, SOL_SOCKET, SO_REUSEADDR, &one, sizeof(one)) < 0)
1081     die("setsockopt: %m");
1082
1083   struct sockaddr_in sa = {
1084     .sin_family = AF_INET,
1085     .sin_port = ntohs(1969),
1086     .sin_addr.s_addr = INADDR_ANY,
1087   };
1088   if (bind(sk, (struct sockaddr *) &sa, sizeof(sa)) < 0)
1089     die("bind: %m");
1090   if (listen(sk, 128) < 0)
1091     die("listen: %m");
1092   // if (fcntl(sk, F_SETFL, O_NONBLOCK) < 0)
1093   //  die("fcntl: %m");
1094
1095   if (do_fork)
1096     {
1097       pid_t pid = fork();
1098       if (pid < 0)
1099         die("fork: %m");
1100       if (pid)
1101         {
1102           FILE *f = fopen(PID_FILE, "w");
1103           if (f)
1104             {
1105               fprintf(f, "%d\n", pid);
1106               fclose(f);
1107             }
1108           exit(0);
1109         }
1110
1111       chdir("/");
1112       setresgid(GID, GID, GID);
1113       setresuid(UID, UID, UID);
1114       setsid();
1115     }
1116
1117   struct sigaction sact = {
1118     .sa_handler = sigchld_handler,
1119     .sa_flags = SA_RESTART,
1120   };
1121   if (sigaction(SIGCHLD, &sact, NULL) < 0)
1122     die("sigaction: %m");
1123
1124   DLOG("Daemon ready");
1125   setproctitle("minsk: Listening");
1126   openlog("minsk", LOG_PID, LOG_LOCAL7);
1127
1128   for (;;)
1129     {
1130       struct pollfd pfd[1] = {
1131         { .fd = sk, .events = POLLIN },
1132       };
1133
1134       int nfds = poll(pfd, 1, 60000);
1135       if (nfds < 0 && errno != EINTR)
1136         {
1137           DLOG("poll: %m");
1138           sleep(5);
1139           continue;
1140         }
1141
1142       int status;
1143       pid_t pid;
1144       while ((pid = waitpid(-1, &status, WNOHANG)) > 0)
1145         {
1146           if (!WIFEXITED(status) || WEXITSTATUS(status))
1147             DLOG("Process %d exited with strange status %x", pid, status);
1148
1149           struct conn *conn = pid_to_conn(pid);
1150           if (conn)
1151             {
1152               DTRACE("Connection with PID %d exited", pid);
1153               put_tracker(conn);
1154               put_conn(conn);
1155             }
1156           else
1157             DTRACE("PID %d exited, matching no connection", pid);
1158         }
1159
1160       if (!(pfd[0].revents & POLLIN))
1161         continue;
1162
1163       socklen_t salen = sizeof(sa);
1164       int sk2 = accept(sk, (struct sockaddr *) &sa, &salen);
1165       if (sk2 < 0)
1166         {
1167           if (errno != EINTR)
1168             {
1169               DLOG("accept: %m");
1170               sleep(5);
1171             }
1172           continue;
1173         }
1174       DTRACE("Got connection: fd=%d", sk2);
1175
1176       struct conn *conn = get_conn(&sa.sin_addr);
1177       const char *reason = NULL;
1178       if (conn)
1179         {
1180           if (!get_tracker(conn))
1181             {
1182               DLOG("Connection from %s dropped: Throttling", inet_ntoa(sa.sin_addr));
1183               put_conn(conn);
1184               conn = NULL;
1185               reason = "--- Sorry, but you are sending too many requests. Please slow down. ---\n";
1186             }
1187         }
1188       else
1189         {
1190           DLOG("Connection from %s dropped: Too many connections", inet_ntoa(sa.sin_addr));
1191           reason = "--- Sorry, maximum number of connections exceeded. Please come later. ---\n";
1192         }
1193
1194       pid = fork();
1195       if (pid < 0)
1196         {
1197           DLOG("fork failed: %m");
1198           close(sk2);
1199           continue;
1200         }
1201       if (!pid)
1202         {
1203           close(sk);
1204           if (conn)
1205             {
1206               DLOG("Accepted connection from %s", inet_ntoa(sa.sin_addr));
1207               setproctitle("minsk: %s", inet_ntoa(sa.sin_addr));
1208               child(sk2);
1209             }
1210           else
1211             {
1212               DLOG("Sending error message to %s", inet_ntoa(sa.sin_addr));
1213               setproctitle("minsk: %s ERR", inet_ntoa(sa.sin_addr));
1214               write(sk2, reason, strlen(reason));
1215             }
1216           exit(0);
1217         }
1218
1219       DTRACE("Created process %d", pid);
1220       if (conn)
1221         conn->pid = pid;
1222       close(sk2);
1223     }
1224 }
1225
1226 int main(int argc, char **argv)
1227 {
1228   if (argc > 1)
1229     {
1230       setproctitle_init(argc, argv);
1231       if (!strcmp(argv[1], "--daemon"))
1232         run_as_daemon(1);
1233       else if (!strcmp(argv[1], "--net"))
1234         run_as_daemon(0);
1235       else
1236         die("Usage: minsk [--daemon | --net]");
1237     }
1238
1239   trace = 3;
1240   parse_in();
1241   run();
1242   return 0;
1243 }