cell.c

   1 /* DLIFE Copyright (C) 2000 Richard W.M. Jones <rich@annexia.org>
   2  * and other authors listed in the ``AUTHORS'' file.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  17  *
  18  * $Id: cell.c,v 1.3 2002/12/11 17:16:21 rich Exp $
  19  */
  20
  21 #include "config.h"
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25
  26 #ifdef HAVE_STRING_H
  27 #include <string.h>
  28 #endif
  29
  30 #ifdef HAVE_ASSERT_H
  31 #include <assert.h>
  32 #endif
  33
  34 #ifdef HAVE_TIME_H
  35 #include <time.h>
  36 #endif
  37
  38 #ifdef HAVE_UNISTD_H
  39 #include <unistd.h>
  40 #endif
  41
  42 #ifdef HAVE_SIGNAL_H
  43 #include <signal.h>
  44 #endif
  45
  46 #ifdef HAVE_SYS_TYPES_H
  47 #include <sys/types.h>
  48 #endif
  49
  50 #ifdef HAVE_DIRENT_H
  51 #include <dirent.h>
  52 #endif
  53
  54 #ifdef HAVE_SYSLOG_H
  55 #include <syslog.h>
  56 #endif
  57
  58 #include "cell.h"
  59 #include "soup.h"
  60 #include "random.h"
  61 #include "params.h"
  62 #include "dlink.h"
  63 #include "image.h"
  64 #include "load.h"
  65
  66 #define PRINT_SIMULATION_STATS 0
  67
  68 static volatile int quit = 0, save = 0, outgoing = 0, incoming = 0, info = 0;
  69 static void save_cell_in_outgoing (struct state *, const struct cell *);
  70
  71 /* Initialize the common fields of a cell. */
  72 static inline void
  73 init_cell (struct cell *cell)
  74 {
  75   /* Public fields are subject to initialization errors. */
  76   if (! chance (cell_initialization_failure))
  77     {
  78       cell->a = cell->b = cell->i = cell->p = 0;
  79       memset (cell->stack, 0, sizeof cell->stack);
  80     }
  81   else
  82     {
  83       int i;
  84
  85       cell->a = get_rand_short ();
  86       cell->b = get_rand_short ();
  87       cell->i = get_rand_short ();
  88       cell->p = 0;              /* Cell would be non-viable otherwise. */
  89
  90       for (i = 0; i < STACK_SIZE; ++i)
  91         cell->stack[i] = get_rand_short ();
  92     }
  93   cell->next = cell->prev = 0;
  94   cell->worse = cell->better = 0;
  95   cell->sp = 0;
  96   cell->errors = 0;
  97   cell->state = state_exec;
  98   cell->dir = 0;
  99   cell->plen = 0;
 100   cell->lim = 0;
 101   cell->frag = 0;
 102   cell->daughter = 0;
 103   cell->cycle = 0;
 104   cell->crc = 0;                /* Initialize these at DIVIDE. */
 105   cell->mother_crc = 0;
 106 }
 107
 108 struct cell *
 109 cell_malloc (struct state *state,
 110              const struct cell *mother,
 111              struct soup_frag *daughter_frag)
 112 {
 113   struct cell *cell;
 114
 115   cell = malloc (sizeof (struct cell));
 116   if (cell == 0) { perror ("malloc"); abort (); }
 117
 118   init_cell (cell);
 119   cell->frag = daughter_frag;
 120
 121   state->nr_cells_allocated++;
 122
 123   return cell;
 124 }
 125
 126 void
 127 cell_divide (struct state *state,
 128              const struct cell *mother,
 129              struct cell *daughter)
 130 {
 131   /* Initialize CRC fields. */
 132   daughter->mother_crc = mother->crc;
 133   daughter->crc = soup_frag_compute_crc32 (state, daughter->frag);
 134
 135   /* If the outgoing signal has just gone, then this cell is the
 136    * lucky cell which has been nominated to be written into the
 137    * outgoing queue.
 138    */
 139   if (outgoing)
 140     {
 141       outgoing = 0;
 142       save_cell_in_outgoing (state, daughter);
 143     }
 144
 145 #if 0
 146   printf ("DIVIDE: 0x%08X/%d -> 0x%08X/%d\n",
 147           daughter->mother_crc, mother->frag->len,
 148           daughter->crc, daughter->frag->len);
 149 #endif
 150 }
 151
 152 /* Put a cell onto the alive list. */
 153 void
 154 cell_activate (struct state *state, struct cell *cell)
 155 {
 156   insert_before_first (cell, &state->alive_list);
 157
 158   /* We assume that cells start off with no errors. */
 159   assert (cell->errors == 0);
 160   insert_before_first (cell, &state->best_list);
 161
 162   state->nr_cells_alive++;
 163 }
 164
 165 /* This function is called after the INC_ERRORS macro has incremented
 166  * the number of errors in a cell and found that the cell should be
 167  * moved up in the linked list by one or more places.
 168  */
 169 void
 170 _cell_move_worse (struct state *state, struct cell *cell)
 171 {
 172   while (cell->worse && cell->errors > cell->worse->errors)
 173     move_towards_last (cell, &state->best_list);
 174 }
 175
 176 /* Kill a cell (and undivided offspring, if any). */
 177 void
 178 cell_kill (struct state *state, struct cell *cell)
 179 {
 180   remove_element (cell, &state->alive_list);
 181   remove_element (cell, &state->best_list);
 182
 183   soup_frag_free (state, cell->frag);
 184
 185   /* Pro-life programmers may wish to look away at this point ... */
 186   if (cell->daughter)
 187     {
 188       soup_frag_free (state, cell->daughter->frag);
 189       cell->daughter->errors = -1;
 190       free (cell->daughter);
 191
 192       state->nr_cells_allocated--;
 193     }
 194
 195   cell->errors = -1;
 196   free (cell);
 197
 198   state->nr_cells_allocated--;
 199   state->nr_cells_alive--;
 200 }
 201
 202 /* Run the grim reaper, culling cells until the amount of free soup
 203  * left is less than the appropriate threshold.
 204  */
 205 static inline void
 206 reaper (struct state *state)
 207 {
 208   int bytes_to_free;
 209
 210   /* How many bytes do we need to free up? */
 211   bytes_to_free = (100 - reaper_reap_threshold) * state->soup_size
 212     / 100 - state->soup_free;
 213   assert (bytes_to_free > 0);
 214
 215 #if 0
 216   printf ("\ninvoking reaper to save %d bytes of soup ...\n", bytes_to_free);
 217 #endif
 218
 219   while (bytes_to_free > 0)
 220     {
 221       struct cell *cell;
 222
 223       /* Pick the most error-prone cell and kill it. */
 224       cell = (struct cell *) state->best_list.last;
 225       bytes_to_free -= cell->frag->len;
 226       if (cell->daughter) bytes_to_free -= cell->daughter->frag->len;
 227
 228 #if 0
 229       printf ("  killing cell with %d errors\n", cell->errors);
 230 #endif
 231
 232       cell_kill (state, cell);
 233     }
 234 }
 235
 236 /* Remove any cells with more than MAX_ERRORS errors. */
 237 static inline void
 238 reap_error_prone_cells (struct state *state)
 239 {
 240   struct cell *cell;
 241
 242   /* Just go down the list of cells, killing them until we
 243    * reach a cell with < MAX_ERRORS errors.
 244    */
 245   while ((cell = (struct cell *) state->best_list.last) &&
 246          cell->errors >= MAX_ERRORS)
 247     {
 248 #if 0
 249       printf ("killing cell with %d errors (>= MAX_ERRORS)\n", cell->errors);
 250 #endif
 251
 252       cell_kill (state, cell);
 253     }
 254 }
 255
 256 static void
 257 check_one_cell (struct state *state, const struct cell *cell, int is_daughter)
 258 {
 259   assert (cell->sp >= 0 && cell->sp < STACK_SIZE);
 260   assert (cell->errors >= 0);
 261   assert (cell->state == state_exec || cell->state == state_find);
 262   assert (cell->dir >= -1 && cell->dir <= 1);
 263   assert (cell->frag != 0);
 264
 265   if (cell->daughter)
 266     {
 267       assert (is_daughter == 0);
 268       check_one_cell (state, cell->daughter, 1);
 269     }
 270 }
 271
 272 /* Check the consistency of each cell. This is only used when we are
 273  * debugging the simulation.
 274  */
 275 void
 276 cell_check (struct state *state)
 277 {
 278   const struct cell *p;
 279   int alive = 0, allocated = 0, errors = 0;
 280
 281   /* Check the alive list and each cell on it. */
 282   for (p = (struct cell *) state->alive_list.first; p; p = p->next)
 283     {
 284       check_one_cell (state, p, 0);
 285       alive++; allocated++;
 286       if (p->daughter) allocated++;
 287     }
 288
 289   assert (alive == state->nr_cells_alive);
 290   assert (allocated == state->nr_cells_allocated);
 291
 292   /* Check the best list. */
 293   alive = allocated = 0;
 294   for (p = (struct cell *) state->best_list.first; p; p = p->worse)
 295     {
 296       assert (errors <= p->errors);
 297       errors = p->errors;
 298       alive++; allocated++;
 299       if (p->daughter) allocated++;
 300     }
 301
 302   assert (alive == state->nr_cells_alive);
 303   assert (allocated == state->nr_cells_allocated);
 304 }
 305
 306 /* Take a complete checkpoint of the state and save it onto disk. */
 307 static void
 308 save_me (struct state *state)
 309 {
 310   char filename2[256], filename3[256];
 311
 312   sprintf (filename2, "%s.new", state->filename);
 313
 314   if (image_save (state, filename2) == 0)
 315     {
 316       sprintf (filename3, "%s~", state->filename);
 317
 318       rename (state->filename, filename3);
 319       rename (filename2, state->filename);
 320
 321       if (verbose)
 322         printf ("CPU %d: Saved soup image to file.\n", state->thread_num);
 323     }
 324   else
 325     {
 326       sprintf (filename3, "/tmp/%s", state->filename);
 327
 328       if (image_save (state, filename3) == 0)
 329         {
 330           fprintf (stderr,
 331                    "save directory is unwritable! saved to %s instead\n",
 332                    filename3);
 333         }
 334       else
 335         {
 336           fprintf (stderr, "could not save state!\n");
 337         }
 338     }
 339 }
 340
 341 /* Check the incoming queue. */
 342 static void
 343 check_incoming (struct state *state)
 344 {
 345   DIR *dir;
 346   struct dirent *d;
 347   char filename[256];
 348   int cells_read = 0;
 349
 350 #ifndef HAVE_OPENDIR
 351 #error "require working opendir/readdir/closedir"
 352 #endif
 353
 354   dir = opendir ("incoming");
 355   if (dir == NULL) { perror ("incoming"); return; }
 356
 357   while ((d = readdir (dir)) != 0)
 358     {
 359       int len = strlen (d->d_name);
 360
 361       if (len >= 4 &&
 362           d->d_name[len-4] == '.' &&
 363           d->d_name[len-3] == 'd' &&
 364           d->d_name[len-2] == 'l' &&
 365           d->d_name[len-1] == 'o')
 366         {
 367           if (cells_read < max_cells_incoming_per_pass)
 368             {
 369               struct cell *cell;
 370
 371               sprintf (filename, "incoming/%s", d->d_name);
 372
 373               /* Read the contents of the file. */
 374               cell = load_cell (state, filename);
 375
 376               if (cell)
 377                 {
 378                   cell_activate (state, cell);
 379                   cells_read++;
 380                 }
 381             }
 382
 383           /* Remove the file - we've finished with it now. */
 384           unlink (filename);
 385         }
 386     }
 387 }
 388
 389 static void
 390 info_to_syslog (const struct state *state)
 391 {
 392   int soup_used_percent
 393     = 100 * (state->soup_size - state->soup_free) / state->soup_size;
 394
 395 #ifdef HAVE_SYSLOG
 396   syslog (LOG_INFO,
 397           "#%d: cycles: %LuB cells: %d [+%d] soup: %d%% (%d/%d)",
 398           state->thread_num,
 399           state->cell_cycle / 1000000000,
 400           state->nr_cells_alive,
 401           state->nr_cells_allocated - state->nr_cells_alive,
 402           soup_used_percent,
 403           state->soup_size - state->soup_free,
 404           state->soup_size);
 405 #endif
 406 }
 407
 408 static void
 409 catch_quit (int sig)
 410 {
 411   quit = 1;
 412 }
 413
 414 static void
 415 catch_alarm (int sig)
 416 {
 417   static int minutes = 0;
 418
 419   minutes++;
 420
 421   if ((minutes % save_period) == 0)
 422     {
 423       save = 1;
 424     }
 425
 426   if ((minutes % outgoing_period) == 0)
 427     {
 428       outgoing = 1;
 429     }
 430
 431   if ((minutes % incoming_period) == 0)
 432     {
 433       incoming = 1;
 434     }
 435
 436   if ((minutes % info_period) == 0)
 437     {
 438       info = 1;
 439     }
 440
 441   alarm (60);
 442 }
 443
 444 void
 445 run_thread (struct state *state)
 446 {
 447   int start_time = time (NULL), end_time;
 448   unsigned long long start_cycle = state->cell_cycle;
 449   struct sigaction sigact;
 450
 451   /* Set up signal handlers to save the soup periodically and
 452    * handle exits gracefully.
 453    */
 454   memset (&sigact, 0, sizeof sigact);
 455   sigact.sa_handler = catch_quit;
 456   sigact.sa_flags = 0;
 457
 458   sigaction (SIGINT, &sigact, 0);
 459   sigaction (SIGQUIT, &sigact, 0);
 460   sigaction (SIGTERM, &sigact, 0);
 461
 462   sigact.sa_handler = catch_alarm;
 463   sigact.sa_flags = SA_RESTART;
 464   sigaction (SIGALRM, &sigact, 0);
 465
 466   alarm (60);
 467
 468   while (!quit)
 469     {
 470       struct cell *p;
 471       int soup_used_percent;
 472
 473       /* Iterate over the list of alive cells, executing a single
 474        * intruction of each.
 475        */
 476       for (p = (struct cell *) state->alive_list.first; p; p = p->next)
 477         {
 478           exec_insn (state, p);
 479         }
 480
 481       /* Print some statistics. */
 482       soup_used_percent
 483         = 100 * (state->soup_size - state->soup_free) / state->soup_size;
 484
 485 #if PRINT_SIMULATION_STATS
 486       printf ("cycles: %LuB  cells: %d [+%d]  soup: %d%%  \r",
 487               state->cell_cycle / 1000000000,
 488               state->nr_cells_alive,
 489               state->nr_cells_allocated - state->nr_cells_alive,
 490               soup_used_percent);
 491       fflush (stdout);
 492 #endif
 493
 494       /* Do we need to invoke the grim reaper? */
 495       if (soup_used_percent >= reaper_invoke_threshold)
 496         {
 497           reaper (state);
 498         }
 499
 500       /* Do we need to reap any remaining cells with more than
 501        * MAX_ERRORS errors?
 502        */
 503       reap_error_prone_cells (state);
 504
 505 #if CHECK
 506       soup_check (state);
 507       cell_check (state);
 508 #endif
 509
 510       /* Save image every so often. */
 511       if (save)
 512         {
 513           save = 0;
 514           save_me (state);
 515         }
 516
 517       /* Check incoming queue? */
 518       if (incoming)
 519         {
 520           incoming = 0;
 521           check_incoming (state);
 522         }
 523
 524       /* Dump status information to syslog? */
 525       if (info)
 526         {
 527           info = 0;
 528           info_to_syslog (state);
 529         }
 530     }
 531
 532   end_time = time (NULL);
 533
 534   syslog (LOG_INFO, "CPU %d: Cycles processed: %LuB  Time: %dH  Cycles/second: %d\n",
 535           state->thread_num,
 536           (state->cell_cycle - start_cycle) / 1000000000,
 537           (end_time - start_time) / (60 * 60),
 538           (int) ((state->cell_cycle - start_cycle)
 539                  / (end_time - start_time)));
 540
 541   /* Each thread is responsible for saving its own state. */
 542   save_me (state);
 543 }
 544
 545 /* Something of a hack: get any fragment and return it. */
 546 struct soup_frag *
 547 _cell_get_any_frag (struct state *state)
 548 {
 549   return ((struct cell *) state->alive_list.first)->frag;
 550 }
 551
 552 /* Save the current state of the cell table to a file. This function
 553  * is non-destructive.
 554  */
 555 void
 556 cell_state_save (struct state *state, FILE *fp)
 557 {
 558   struct cell *p;
 559
 560   /* Write out the number of cells. */
 561   fwrite (&state->nr_cells_allocated, sizeof state->nr_cells_allocated, 1, fp);
 562   fwrite (&state->nr_cells_alive, sizeof state->nr_cells_alive, 1, fp);
 563
 564   /* Write the cells out in order to the file. */
 565   for (p = (struct cell *) state->alive_list.first; p; p = p->next)
 566     {
 567       p->fbase = p->frag->base;
 568       fwrite (p, sizeof (struct cell), 1, fp);
 569       if (p->daughter)
 570         {
 571           p->daughter->fbase = p->daughter->frag->base;
 572           fwrite (p->daughter, sizeof (struct cell), 1, fp);
 573         }
 574     }
 575 }
 576
 577 static int
 578 compare_nr_errors (const void *cv1, const void *cv2)
 579 {
 580   const struct cell **cp1 = (const struct cell **) cv1;
 581   const struct cell **cp2 = (const struct cell **) cv2;
 582
 583   return (*cp1)->errors - (*cp2)->errors;
 584 }
 585
 586 /* Load the cells from a previously saved file. */
 587 void
 588 cell_state_load (struct state *state, FILE *fp)
 589 {
 590   int i;
 591   struct cell *p;
 592   struct cell **cellptr_list;
 593
 594   assert (state->nr_cells_allocated == 0);
 595   assert (state->nr_cells_alive == 0);
 596
 597   /* Read in the number of cells. */
 598   if (fread (&state->nr_cells_allocated,
 599              sizeof state->nr_cells_allocated, 1, fp) != 1)
 600     {
 601       syslog (LOG_ERR, "error in cell state\n");
 602       abort ();
 603     }
 604   if (fread (&state->nr_cells_alive,
 605              sizeof state->nr_cells_alive, 1, fp) != 1)
 606     {
 607       syslog (LOG_ERR, "error in cell state\n");
 608       abort ();
 609     }
 610
 611   assert (state->nr_cells_alive <= state->nr_cells_allocated);
 612
 613   cellptr_list = malloc (sizeof (struct cell *) * state->nr_cells_alive);
 614
 615   /* Read each cell in from the file. */
 616   for (i = 0; i < state->nr_cells_alive; ++i)
 617     {
 618       p = malloc (sizeof (struct cell));
 619       if (p == 0) { perror ("malloc"); abort (); }
 620
 621       if (fread (p, sizeof (struct cell), 1, fp) != 1)
 622         {
 623           syslog (LOG_ERR, "error in cell state\n");
 624           abort ();
 625         }
 626
 627       cellptr_list[i] = p;
 628
 629       insert_before_last (p, &state->alive_list);
 630
 631       if (p->daughter)
 632         {
 633           p->daughter = malloc (sizeof (struct cell));
 634           if (p->daughter == 0) { perror ("malloc"); abort (); }
 635
 636           if (fread (p->daughter, sizeof (struct cell), 1, fp) != 1)
 637             {
 638               syslog (LOG_ERR, "error in cell state\n");
 639               abort ();
 640             }
 641         }
 642     }
 643
 644   /* Order the living cells from best to worst, and from this
 645    * reconstruct the best list.
 646    */
 647   qsort (cellptr_list, state->nr_cells_alive, sizeof (struct cell *),
 648          compare_nr_errors);
 649
 650   for (i = 0; i < state->nr_cells_alive; ++i)
 651     {
 652       insert_before_last (cellptr_list[i], &state->best_list);
 653     }
 654 }
 655
 656 /* This function is used when loading the soup (just after loading the
 657  * cells) to fix up references from the cells to soup fragments. It
 658  * uses the hidden ``fbase'' member of struct cell to save the reference.
 659  */
 660 void
 661 _cell_fixup_soup_ref (struct state *state,
 662                       addr_t fbase, struct soup_frag *frag)
 663 {
 664   struct cell *p;
 665
 666   for (p = (struct cell *) state->alive_list.first; p; p = p->next)
 667     {
 668       if (p->fbase == fbase)
 669         {
 670           p->frag = frag;
 671           return;
 672         }
 673       else if (p->daughter && p->daughter->fbase == fbase)
 674         {
 675           p->daughter->frag = frag;
 676           return;
 677         }
 678     }
 679
 680   syslog (LOG_ERR, "cell fixup not found (fbase = %d)\n", fbase);
 681   abort ();
 682 }
 683
 684 /* Save a single cell in the outgoing queue. */
 685 static void
 686 save_cell_in_outgoing (struct state *state,
 687                        const struct cell *cell)
 688 {
 689   char filename[256];
 690   FILE *fp;
 691   int i;
 692
 693   /* Choose a random name. */
 694   sprintf (filename, "outgoing/%d.dlo", get_rand_int());
 695
 696   fp = fopen (filename, "w");
 697   if (fp == NULL) { perror (filename); return; } /* Fail silently. */
 698
 699   for (i = 0; i < cell->frag->len; ++i)
 700     fprintf (fp, "%02X", get_soup (state, cell->frag, i));
 701
 702   fclose (fp);
 703 }