soup.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: soup.c,v 1.2 2002/04/05 16:47:13 rich Exp $
  19  */
  20
  21 #include "config.h"
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25
  26 #ifdef HAVE_UNISTD_H
  27 #include <unistd.h>
  28 #endif
  29
  30 #ifdef HAVE_ASSERT_H
  31 #include <assert.h>
  32 #endif
  33
  34 #include "types.h"
  35 #include "soup.h"
  36 #include "cell.h"
  37 #include "random.h"
  38 #include "state.h"
  39 #include "crc.h"
  40
  41 #define TRACE_SOUP_ALLOCATIONS 0
  42
  43 void
  44 soup_init (struct state *state, int _soup_size)
  45 {
  46   int i;
  47
  48   state->soup_size = _soup_size;
  49   state->soup_free = _soup_size;
  50   state->soup = malloc (_soup_size);
  51   if (state->soup == 0) { perror ("malloc"); abort (); }
  52
  53   /* Fill the soup with entropy. */
  54   for (i = 0; i < _soup_size; ++i)
  55     {
  56       state->soup[i] = get_rand_byte ();
  57     }
  58 }
  59
  60 /* Allocate a new fragment of soup. */
  61 struct soup_frag *
  62 soup_frag_malloc (struct state *state,
  63                   struct soup_frag *mother_frag, reg_t len)
  64 {
  65   struct soup_frag *p, *t;
  66   int offset;
  67   int is_first_cell = state->soup_free == state->soup_size;
  68
  69 #if TRACE_SOUP_ALLOCATIONS
  70   printf ("soup alloc: want %d bytes ", len);
  71 #endif
  72
  73   p = malloc (sizeof (struct soup_frag));
  74   if (p == 0) { perror ("malloc"); abort (); }
  75
  76   /* Common fields. */
  77   p->len = len;
  78   state->soup_free -= len;
  79
  80   /* The first cell is allocated specially. */
  81   if (is_first_cell)
  82     {
  83       p->next = p;
  84       p->prev = p;
  85       p->base = 0;
  86
  87 #if TRACE_SOUP_ALLOCATIONS
  88       printf ("first cell 0 OK\n");
  89 #endif
  90
  91       return p;
  92     }
  93
  94   /* If a cell has no parent, we can insert it anywhere. */
  95   if (mother_frag == 0)
  96     {
  97       /* Need to go and grab a cell at random, then search indefinitely
  98        * for a free space.
  99        */
 100       mother_frag = _cell_get_any_frag (state);
 101       t = mother_frag;
 102       offset = 0;
 103
 104       do
 105         {
 106           int diff;
 107
 108 #if TRACE_SOUP_ALLOCATIONS
 109           printf ("[%d,%d:%d,%d] ",
 110                   t->base, t->base + t->len,
 111                   t->next->base, t->next->base + t->next->len);
 112 #endif
 113
 114           /* Handle the wrap-around case gracefully. */
 115           if (t->next->base > t->base)
 116             diff = t->next->base - (t->base + t->len);
 117           else
 118             diff = t->next->base - (t->base + t->len) + state->soup_size;
 119
 120           /* Is there space after this fragment? */
 121           if (diff >= len)
 122             {
 123               /* Yes: insert the cell here. */
 124               p->prev = t;
 125               p->next = t->next;
 126               p->base = (t->base + t->len) & (state->soup_size-1);
 127               t->next->prev = p;
 128               t->next = p;
 129
 130 #if TRACE_SOUP_ALLOCATIONS
 131               printf ("%d OK\n", p->base);
 132 #endif
 133
 134               return p;
 135             }
 136
 137           offset += diff + t->len;
 138           t = t->next;
 139         }
 140       while (offset <= state->soup_size && t != mother_frag);
 141
 142       /* No space for it. */
 143       state->soup_free += len;
 144       free (p);
 145
 146 #if TRACE_SOUP_ALLOCATIONS
 147       printf ("FAILED\n");
 148 #endif
 149
 150       return 0;
 151     }
 152
 153   /* Find a suitable fragment near the mother. */
 154
 155   /* Search forwards first. */
 156   t = mother_frag;
 157   offset = 0;
 158   do
 159     {
 160       int diff;
 161
 162 #if TRACE_SOUP_ALLOCATIONS
 163       printf ("[%d,%d:%d,%d] ",
 164               t->base, t->base + t->len,
 165               t->next->base, t->next->base + t->next->len);
 166 #endif
 167
 168       /* Handle the wrap-around case gracefully. */
 169       if (t->next->base > t->base)
 170         diff = t->next->base - (t->base + t->len);
 171       else
 172         diff = t->next->base - (t->base + t->len) + state->soup_size;
 173
 174       /* Is there space after this fragment? */
 175       if (diff >= len)
 176         {
 177           /* Yes: insert the cell here. */
 178           p->prev = t;
 179           p->next = t->next;
 180           p->base = (t->base + t->len) & (state->soup_size-1);
 181           t->next->prev = p;
 182           t->next = p;
 183
 184 #if TRACE_SOUP_ALLOCATIONS
 185   printf ("%d OK\n", p->base);
 186 #endif
 187
 188           return p;
 189         }
 190
 191       offset += diff + t->len;
 192       t = t->next;
 193     }
 194   while (offset <= MAX_SPAWN_DISTANCE && t != mother_frag);
 195
 196   /* Search backwards. */
 197   t = mother_frag;
 198   offset = 0;
 199   do
 200     {
 201       int diff;
 202
 203 #if TRACE_SOUP_ALLOCATIONS
 204       printf ("[%d,%d:%d,%d] ",
 205               t->prev->base, t->prev->base + t->prev->len,
 206               t->base, t->base + t->len);
 207 #endif
 208
 209       /* Handle the wrap-around case gracefully. */
 210       if (t->prev->base < t->base)
 211         diff = t->base - (t->prev->base + t->prev->len);
 212       else
 213         diff = t->base - (t->prev->base + t->prev->len) + state->soup_size;
 214
 215       /* Is there space before this fragment? */
 216       if (diff >= len)
 217         {
 218           /* Yes: insert the cell here. */
 219           p->prev = t->prev;
 220           p->next = t;
 221           p->base = (t->base - len) & (state->soup_size-1);
 222           p->len = len;
 223           t->prev->next = p;
 224           t->prev = p;
 225
 226 #if TRACE_SOUP_ALLOCATIONS
 227   printf ("%d OK\n", p->base);
 228 #endif
 229
 230           return p;
 231         }
 232
 233       offset += diff + t->prev->len;
 234       t = t->prev;
 235     }
 236   while (offset <= MAX_SPAWN_DISTANCE && t != mother_frag);
 237
 238   /* No space for it. */
 239   state->soup_free += len;
 240   free (p);
 241
 242 #if TRACE_SOUP_ALLOCATIONS
 243   printf ("FAILED\n");
 244 #endif
 245
 246   return 0;
 247 }
 248
 249 /* Free up a soup fragment. */
 250 void
 251 soup_frag_free (struct state *state,
 252                 struct soup_frag *frag)
 253 {
 254   /* NB. We ignore the case of freeing up the single last remaining
 255    * fragment, since that should never happen in real life.
 256    */
 257   frag->next->prev = frag->prev;
 258   frag->prev->next = frag->next;
 259
 260   state->soup_free += frag->len;
 261
 262   free (frag);
 263 }
 264
 265 /* Compute the CRC for a frag. */
 266 crc_t
 267 soup_frag_compute_crc32 (const struct state *state,
 268                          const struct soup_frag *frag)
 269 {
 270   /* Take care of the case where a cell straddles the end of the soup. */
 271   if (frag->base + frag->len <= state->soup_size)
 272     {
 273       return compute_crc32 (state->soup + frag->base, frag->len);
 274     }
 275   else
 276     {
 277       crc_t crc = compute_crc32 (state->soup + frag->base,
 278                                  state->soup_size - frag->base);
 279       return incr_compute_crc32 (crc, state->soup,
 280                                  frag->len - (state->soup_size - frag->base));
 281     }
 282
 283 }
 284
 285 /* This function checks that the soup is consistent. We are passed
 286  * one fragment (at random) and walk the circular linked list,
 287  * examining the fragments to ensure they are in order and do not
 288  * overlap.
 289  */
 290 void
 291 soup_check (struct state *state)
 292 {
 293   const struct soup_frag *start_frag = _cell_get_any_frag (state);
 294   const struct soup_frag *frag = start_frag;
 295   int nr_frags = 0;
 296   int soup_free = state->soup_size;
 297
 298   do
 299     {
 300       assert (0 <= frag->base && frag->base < state->soup_size);
 301       assert (frag->len > 0);
 302
 303       assert (frag->next->prev == frag);
 304       assert (frag->prev->next == frag);
 305
 306       if (frag->prev->base < frag->base)
 307         assert (frag->prev->base + frag->prev->len <= frag->base);
 308       else
 309         assert (frag->prev->base + frag->prev->len <= frag->base + state->soup_size);
 310
 311       if (frag->base < frag->next->base)
 312         assert (frag->base + frag->len <= frag->next->base);
 313       else
 314         assert (frag->base + frag->len <= frag->next->base + state->soup_size);
 315
 316       soup_free -= frag->len;
 317
 318       frag = frag->next;
 319       nr_frags++;
 320     }
 321   while (frag != start_frag);
 322
 323   assert (nr_frags == state->nr_cells_allocated);
 324   assert (soup_free == state->soup_free);
 325 }
 326
 327 /* Dump the soup and soup structures out to a file. This function is
 328  * non-destructive.
 329  */
 330 void
 331 soup_state_save (struct state *state, FILE *fp)
 332 {
 333   struct soup_frag *start_frag, *frag;
 334
 335   /* Write out the size of the soup. */
 336   fwrite (&state->soup_size, sizeof state->soup_size, 1, fp);
 337   fwrite (&state->soup_free, sizeof state->soup_free, 1, fp);
 338
 339   /* Write out the soup itself. */
 340   fwrite (state->soup, 1, state->soup_size, fp);
 341
 342   /* Write out the number of fragments. Note that this is the same
 343    * as the number of allocated cells.
 344    */
 345   fwrite (&state->nr_cells_allocated,
 346           sizeof state->nr_cells_allocated, 1, fp);
 347
 348   /* Write out the fragment list. */
 349   frag = start_frag = _cell_get_any_frag (state);
 350   do
 351     {
 352       fwrite (frag, sizeof (struct soup_frag), 1, fp);
 353
 354       frag = frag->next;
 355     }
 356   while (frag != start_frag);
 357 }
 358
 359 /* Load the soup state from a previously saved file. */
 360 void
 361 soup_state_load (struct state *state, FILE *fp)
 362 {
 363   int _soup_size, nr_frags, i;
 364   struct soup_frag *first_frag = 0, *prev_frag = 0;
 365
 366   /* Load the size of the soup expected. */
 367   if (fread (&_soup_size, sizeof _soup_size, 1, fp) != 1)
 368     {
 369       fprintf (stderr, "error in soup state\n");
 370       abort ();
 371     }
 372   if (state->soup_size != _soup_size)
 373     {
 374       fprintf (stderr, "soup size doesn't match - can't load this soup image\n");
 375       abort ();
 376     }
 377   if (fread (&state->soup_free, sizeof state->soup_free, 1, fp) != 1)
 378     {
 379       fprintf (stderr, "error in soup state\n");
 380       abort ();
 381     }
 382   if (state->soup_free > state->soup_size)
 383     {
 384       fprintf (stderr, "soup free > soup_size - can't load this soup image\n");
 385       abort ();
 386     }
 387
 388   /* Load the soup itself. */
 389   if (fread (state->soup, 1, _soup_size, fp) != _soup_size)
 390     {
 391       fprintf (stderr, "error in soup state\n");
 392       abort ();
 393     }
 394
 395   /* Load the number of fragments expected. */
 396   if (fread (&nr_frags, sizeof nr_frags, 1, fp) != 1)
 397     {
 398       fprintf (stderr, "error in soup state\n");
 399       abort ();
 400     }
 401   if (nr_frags != state->nr_cells_allocated)
 402     {
 403       fprintf (stderr, "nr_frags != nr_cells_allocated - can't load this soup image\n");
 404       abort ();
 405     }
 406
 407   /* Load each fragment. */
 408   for (i = 0; i < nr_frags; ++i)
 409     {
 410       struct soup_frag *p;
 411
 412       p = malloc (sizeof (struct soup_frag));
 413       if (p == 0) { perror ("malloc"); abort (); }
 414
 415       if (fread (p, sizeof (struct soup_frag), 1, fp) != 1)
 416         {
 417           fprintf (stderr, "error in soup state\n");
 418           abort ();
 419         }
 420
 421       if (i == 0)
 422         first_frag = p;
 423
 424       /* Find the cell which references this fragment and fix it up. */
 425       _cell_fixup_soup_ref (state, p->base, p);
 426
 427       /* Join the fragments to form a circular linked list. */
 428       if (prev_frag)
 429         {
 430           p->prev = prev_frag;
 431           p->prev->next = p;
 432         }
 433
 434       prev_frag = p;
 435     }
 436
 437   /* Finish off the circular linked list. */
 438   first_frag->prev = prev_frag;
 439   prev_frag->next = first_frag;
 440 }