/* DLIFE Copyright (C) 2000 Richard W.M. Jones <rich@annexia.org>
 * and other authors listed in the ``AUTHORS'' file.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 * $Id: cell.c,v 1.3 2002/12/11 17:16:21 rich Exp $
 */

#include "config.h"

#include <stdio.h>
#include <stdlib.h>

#ifdef HAVE_STRING_H
#include <string.h>
#endif

#ifdef HAVE_ASSERT_H
#include <assert.h>
#endif

#ifdef HAVE_TIME_H
#include <time.h>
#endif

#ifdef HAVE_UNISTD_H
#include <unistd.h>
#endif

#ifdef HAVE_SIGNAL_H
#include <signal.h>
#endif

#ifdef HAVE_SYS_TYPES_H
#include <sys/types.h>
#endif

#ifdef HAVE_DIRENT_H
#include <dirent.h>
#endif

#ifdef HAVE_SYSLOG_H
#include <syslog.h>
#endif

#include "cell.h"
#include "soup.h"
#include "random.h"
#include "params.h"
#include "dlink.h"
#include "image.h"
#include "load.h"

#define PRINT_SIMULATION_STATS 0

static volatile int quit = 0, save = 0, outgoing = 0, incoming = 0, info = 0;
static void save_cell_in_outgoing (struct state *, const struct cell *);

/* Initialize the common fields of a cell. */
static inline void
init_cell (struct cell *cell)
{
  /* Public fields are subject to initialization errors. */
  if (! chance (cell_initialization_failure))
    {
      cell->a = cell->b = cell->i = cell->p = 0;
      memset (cell->stack, 0, sizeof cell->stack);
    }
  else
    {
      int i;

      cell->a = get_rand_short ();
      cell->b = get_rand_short ();
      cell->i = get_rand_short ();
      cell->p = 0;		/* Cell would be non-viable otherwise. */

      for (i = 0; i < STACK_SIZE; ++i)
	cell->stack[i] = get_rand_short ();
    }
  cell->next = cell->prev = 0;
  cell->worse = cell->better = 0;
  cell->sp = 0;
  cell->errors = 0;
  cell->state = state_exec;
  cell->dir = 0;
  cell->plen = 0;
  cell->lim = 0;
  cell->frag = 0;
  cell->daughter = 0;
  cell->cycle = 0;
  cell->crc = 0;		/* Initialize these at DIVIDE. */
  cell->mother_crc = 0;
}

struct cell *
cell_malloc (struct state *state,
	     const struct cell *mother,
	     struct soup_frag *daughter_frag)
{
  struct cell *cell;

  cell = malloc (sizeof (struct cell));
  if (cell == 0) { perror ("malloc"); abort (); }

  init_cell (cell);
  cell->frag = daughter_frag;

  state->nr_cells_allocated++;

  return cell;
}

void
cell_divide (struct state *state,
	     const struct cell *mother,
	     struct cell *daughter)
{
  /* Initialize CRC fields. */
  daughter->mother_crc = mother->crc;
  daughter->crc = soup_frag_compute_crc32 (state, daughter->frag);

  /* If the outgoing signal has just gone, then this cell is the
   * lucky cell which has been nominated to be written into the
   * outgoing queue.
   */
  if (outgoing)
    {
      outgoing = 0;
      save_cell_in_outgoing (state, daughter);
    }

#if 0
  printf ("DIVIDE: 0x%08X/%d -> 0x%08X/%d\n",
	  daughter->mother_crc, mother->frag->len,
	  daughter->crc, daughter->frag->len);
#endif
}

/* Put a cell onto the alive list. */
void
cell_activate (struct state *state, struct cell *cell)
{
  insert_before_first (cell, &state->alive_list);

  /* We assume that cells start off with no errors. */
  assert (cell->errors == 0);
  insert_before_first (cell, &state->best_list);

  state->nr_cells_alive++;
}

/* This function is called after the INC_ERRORS macro has incremented
 * the number of errors in a cell and found that the cell should be
 * moved up in the linked list by one or more places.
 */
void
_cell_move_worse (struct state *state, struct cell *cell)
{
  while (cell->worse && cell->errors > cell->worse->errors)
    move_towards_last (cell, &state->best_list);
}

/* Kill a cell (and undivided offspring, if any). */
void
cell_kill (struct state *state, struct cell *cell)
{
  remove_element (cell, &state->alive_list);
  remove_element (cell, &state->best_list);

  soup_frag_free (state, cell->frag);

  /* Pro-life programmers may wish to look away at this point ... */
  if (cell->daughter)
    {
      soup_frag_free (state, cell->daughter->frag);
      cell->daughter->errors = -1;
      free (cell->daughter);

      state->nr_cells_allocated--;
    }

  cell->errors = -1;
  free (cell);

  state->nr_cells_allocated--;
  state->nr_cells_alive--;
}

/* Run the grim reaper, culling cells until the amount of free soup
 * left is less than the appropriate threshold.
 */
static inline void
reaper (struct state *state)
{
  int bytes_to_free;

  /* How many bytes do we need to free up? */
  bytes_to_free = (100 - reaper_reap_threshold) * state->soup_size
    / 100 - state->soup_free;
  assert (bytes_to_free > 0);

#if 0
  printf ("\ninvoking reaper to save %d bytes of soup ...\n", bytes_to_free);
#endif

  while (bytes_to_free > 0)
    {
      struct cell *cell;

      /* Pick the most error-prone cell and kill it. */
      cell = (struct cell *) state->best_list.last;
      bytes_to_free -= cell->frag->len;
      if (cell->daughter) bytes_to_free -= cell->daughter->frag->len;

#if 0
      printf ("  killing cell with %d errors\n", cell->errors);
#endif

      cell_kill (state, cell);
    }
}

/* Remove any cells with more than MAX_ERRORS errors. */
static inline void
reap_error_prone_cells (struct state *state)
{
  struct cell *cell;

  /* Just go down the list of cells, killing them until we
   * reach a cell with < MAX_ERRORS errors.
   */
  while ((cell = (struct cell *) state->best_list.last) &&
	 cell->errors >= MAX_ERRORS)
    {
#if 0
      printf ("killing cell with %d errors (>= MAX_ERRORS)\n", cell->errors);
#endif

      cell_kill (state, cell);
    }
}

static void
check_one_cell (struct state *state, const struct cell *cell, int is_daughter)
{
  assert (cell->sp >= 0 && cell->sp < STACK_SIZE);
  assert (cell->errors >= 0);
  assert (cell->state == state_exec || cell->state == state_find);
  assert (cell->dir >= -1 && cell->dir <= 1);
  assert (cell->frag != 0);

  if (cell->daughter)
    {
      assert (is_daughter == 0);
      check_one_cell (state, cell->daughter, 1);
    }
}

/* Check the consistency of each cell. This is only used when we are
 * debugging the simulation.
 */
void
cell_check (struct state *state)
{
  const struct cell *p;
  int alive = 0, allocated = 0, errors = 0;

  /* Check the alive list and each cell on it. */
  for (p = (struct cell *) state->alive_list.first; p; p = p->next)
    {
      check_one_cell (state, p, 0);
      alive++; allocated++;
      if (p->daughter) allocated++;
    }

  assert (alive == state->nr_cells_alive);
  assert (allocated == state->nr_cells_allocated);

  /* Check the best list. */
  alive = allocated = 0;
  for (p = (struct cell *) state->best_list.first; p; p = p->worse)
    {
      assert (errors <= p->errors);
      errors = p->errors;
      alive++; allocated++;
      if (p->daughter) allocated++;
    }

  assert (alive == state->nr_cells_alive);
  assert (allocated == state->nr_cells_allocated);
}

/* Take a complete checkpoint of the state and save it onto disk. */
static void
save_me (struct state *state)
{
  char filename2[256], filename3[256];

  sprintf (filename2, "%s.new", state->filename);

  if (image_save (state, filename2) == 0)
    {
      sprintf (filename3, "%s~", state->filename);

      rename (state->filename, filename3);
      rename (filename2, state->filename);

      if (verbose)
	printf ("CPU %d: Saved soup image to file.\n", state->thread_num);
    }
  else
    {
      sprintf (filename3, "/tmp/%s", state->filename);

      if (image_save (state, filename3) == 0)
	{
	  fprintf (stderr,
		   "save directory is unwritable! saved to %s instead\n",
		   filename3);
	}
      else
	{
	  fprintf (stderr, "could not save state!\n");
	}
    }
}

/* Check the incoming queue. */
static void
check_incoming (struct state *state)
{
  DIR *dir;
  struct dirent *d;
  char filename[256];
  int cells_read = 0;

#ifndef HAVE_OPENDIR
#error "require working opendir/readdir/closedir"
#endif

  dir = opendir ("incoming");
  if (dir == NULL) { perror ("incoming"); return; }

  while ((d = readdir (dir)) != 0)
    {
      int len = strlen (d->d_name);

      if (len >= 4 &&
	  d->d_name[len-4] == '.' &&
	  d->d_name[len-3] == 'd' &&
	  d->d_name[len-2] == 'l' &&
	  d->d_name[len-1] == 'o')
	{
	  if (cells_read < max_cells_incoming_per_pass)
	    {
	      struct cell *cell;

	      sprintf (filename, "incoming/%s", d->d_name);

	      /* Read the contents of the file. */
	      cell = load_cell (state, filename);

	      if (cell)
		{
		  cell_activate (state, cell);
		  cells_read++;
		}
	    }

	  /* Remove the file - we've finished with it now. */
	  unlink (filename);
	}
    }
}

static void
info_to_syslog (const struct state *state)
{
  int soup_used_percent
    = 100 * (state->soup_size - state->soup_free) / state->soup_size;

#ifdef HAVE_SYSLOG
  syslog (LOG_INFO,
	  "#%d: cycles: %LuB cells: %d [+%d] soup: %d%% (%d/%d)",
	  state->thread_num,
	  state->cell_cycle / 1000000000,
	  state->nr_cells_alive,
	  state->nr_cells_allocated - state->nr_cells_alive,
	  soup_used_percent,
	  state->soup_size - state->soup_free,
	  state->soup_size);
#endif
}

static void
catch_quit (int sig)
{
  quit = 1;
}

static void
catch_alarm (int sig)
{
  static int minutes = 0;

  minutes++;

  if ((minutes % save_period) == 0)
    {
      save = 1;
    }

  if ((minutes % outgoing_period) == 0)
    {
      outgoing = 1;
    }

  if ((minutes % incoming_period) == 0)
    {
      incoming = 1;
    }

  if ((minutes % info_period) == 0)
    {
      info = 1;
    }

  alarm (60);
}

void
run_thread (struct state *state)
{
  int start_time = time (NULL), end_time;
  unsigned long long start_cycle = state->cell_cycle;
  struct sigaction sigact;

  /* Set up signal handlers to save the soup periodically and
   * handle exits gracefully.
   */
  memset (&sigact, 0, sizeof sigact);
  sigact.sa_handler = catch_quit;
  sigact.sa_flags = 0;

  sigaction (SIGINT, &sigact, 0);
  sigaction (SIGQUIT, &sigact, 0);
  sigaction (SIGTERM, &sigact, 0);

  sigact.sa_handler = catch_alarm;
  sigact.sa_flags = SA_RESTART;
  sigaction (SIGALRM, &sigact, 0);

  alarm (60);

  while (!quit)
    {
      struct cell *p;
      int soup_used_percent;

      /* Iterate over the list of alive cells, executing a single
       * intruction of each.
       */
      for (p = (struct cell *) state->alive_list.first; p; p = p->next)
	{
	  exec_insn (state, p);
	}

      /* Print some statistics. */
      soup_used_percent
	= 100 * (state->soup_size - state->soup_free) / state->soup_size;

#if PRINT_SIMULATION_STATS
      printf ("cycles: %LuB  cells: %d [+%d]  soup: %d%%  \r",
	      state->cell_cycle / 1000000000,
	      state->nr_cells_alive,
	      state->nr_cells_allocated - state->nr_cells_alive,
	      soup_used_percent);
      fflush (stdout);
#endif

      /* Do we need to invoke the grim reaper? */
      if (soup_used_percent >= reaper_invoke_threshold)
	{
	  reaper (state);
	}

      /* Do we need to reap any remaining cells with more than
       * MAX_ERRORS errors?
       */
      reap_error_prone_cells (state);

#if CHECK
      soup_check (state);
      cell_check (state);
#endif

      /* Save image every so often. */
      if (save)
	{
	  save = 0;
	  save_me (state);
	}

      /* Check incoming queue? */
      if (incoming)
	{
	  incoming = 0;
	  check_incoming (state);
	}

      /* Dump status information to syslog? */
      if (info)
	{
	  info = 0;
	  info_to_syslog (state);
	}
    }

  end_time = time (NULL);

  syslog (LOG_INFO, "CPU %d: Cycles processed: %LuB  Time: %dH  Cycles/second: %d\n",
	  state->thread_num,
	  (state->cell_cycle - start_cycle) / 1000000000,
	  (end_time - start_time) / (60 * 60),
	  (int) ((state->cell_cycle - start_cycle)
		 / (end_time - start_time)));

  /* Each thread is responsible for saving its own state. */
  save_me (state);
}

/* Something of a hack: get any fragment and return it. */
struct soup_frag *
_cell_get_any_frag (struct state *state)
{
  return ((struct cell *) state->alive_list.first)->frag;
}

/* Save the current state of the cell table to a file. This function
 * is non-destructive.
 */
void
cell_state_save (struct state *state, FILE *fp)
{
  struct cell *p;

  /* Write out the number of cells. */
  fwrite (&state->nr_cells_allocated, sizeof state->nr_cells_allocated, 1, fp);
  fwrite (&state->nr_cells_alive, sizeof state->nr_cells_alive, 1, fp);

  /* Write the cells out in order to the file. */
  for (p = (struct cell *) state->alive_list.first; p; p = p->next)
    {
      p->fbase = p->frag->base;
      fwrite (p, sizeof (struct cell), 1, fp);
      if (p->daughter)
	{
	  p->daughter->fbase = p->daughter->frag->base;
	  fwrite (p->daughter, sizeof (struct cell), 1, fp);
	}
    }
}

static int
compare_nr_errors (const void *cv1, const void *cv2)
{
  const struct cell **cp1 = (const struct cell **) cv1;
  const struct cell **cp2 = (const struct cell **) cv2;

  return (*cp1)->errors - (*cp2)->errors;
}

/* Load the cells from a previously saved file. */
void
cell_state_load (struct state *state, FILE *fp)
{
  int i;
  struct cell *p;
  struct cell **cellptr_list;

  assert (state->nr_cells_allocated == 0);
  assert (state->nr_cells_alive == 0);

  /* Read in the number of cells. */
  if (fread (&state->nr_cells_allocated,
	     sizeof state->nr_cells_allocated, 1, fp) != 1)
    {
      syslog (LOG_ERR, "error in cell state\n");
      abort ();
    }
  if (fread (&state->nr_cells_alive,
	     sizeof state->nr_cells_alive, 1, fp) != 1)
    {
      syslog (LOG_ERR, "error in cell state\n");
      abort ();
    }

  assert (state->nr_cells_alive <= state->nr_cells_allocated);

  cellptr_list = malloc (sizeof (struct cell *) * state->nr_cells_alive);

  /* Read each cell in from the file. */
  for (i = 0; i < state->nr_cells_alive; ++i)
    {
      p = malloc (sizeof (struct cell));
      if (p == 0) { perror ("malloc"); abort (); }

      if (fread (p, sizeof (struct cell), 1, fp) != 1)
	{
	  syslog (LOG_ERR, "error in cell state\n");
	  abort ();
	}

      cellptr_list[i] = p;

      insert_before_last (p, &state->alive_list);

      if (p->daughter)
	{
	  p->daughter = malloc (sizeof (struct cell));
	  if (p->daughter == 0) { perror ("malloc"); abort (); }

	  if (fread (p->daughter, sizeof (struct cell), 1, fp) != 1)
	    {
	      syslog (LOG_ERR, "error in cell state\n");
	      abort ();
	    }
	}
    }

  /* Order the living cells from best to worst, and from this
   * reconstruct the best list.
   */
  qsort (cellptr_list, state->nr_cells_alive, sizeof (struct cell *),
	 compare_nr_errors);

  for (i = 0; i < state->nr_cells_alive; ++i)
    {
      insert_before_last (cellptr_list[i], &state->best_list);
    }
}

/* This function is used when loading the soup (just after loading the
 * cells) to fix up references from the cells to soup fragments. It
 * uses the hidden ``fbase'' member of struct cell to save the reference.
 */
void
_cell_fixup_soup_ref (struct state *state,
		      addr_t fbase, struct soup_frag *frag)
{
  struct cell *p;

  for (p = (struct cell *) state->alive_list.first; p; p = p->next)
    {
      if (p->fbase == fbase)
	{
	  p->frag = frag;
	  return;
	}
      else if (p->daughter && p->daughter->fbase == fbase)
	{
	  p->daughter->frag = frag;
	  return;
	}
    }

  syslog (LOG_ERR, "cell fixup not found (fbase = %d)\n", fbase);
  abort ();
}

/* Save a single cell in the outgoing queue. */
static void
save_cell_in_outgoing (struct state *state,
		       const struct cell *cell)
{
  char filename[256];
  FILE *fp;
  int i;

  /* Choose a random name. */
  sprintf (filename, "outgoing/%d.dlo", get_rand_int());

  fp = fopen (filename, "w");
  if (fp == NULL) { perror (filename); return; } /* Fail silently. */

  for (i = 0; i < cell->frag->len; ++i)
    fprintf (fp, "%02X", get_soup (state, cell->frag, i));

  fclose (fp);
}