t_allocator.cpp

Go to the documentation of this file.

/*****************************************************************************\
*                                                                             *
*  Name   : test_array_object_allocator                                       *
*  Author : Chris Koeritz                                                     *
*                                                                             *
*******************************************************************************
* Copyright (c) 1993-$now By Author.  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 is online at:      *
*     http://www.fsf.org/copyleft/gpl.html                                    *
* Please send any updates to: fred@gruntose.com                               *
\*****************************************************************************/

// this class exercises functionality that was formerly in the object_allocator
// base class for array and which is now just part of the array template.

#include <basis/array.cpp>
#include <basis/byte_array.h>
#include <basis/chaos.h>
#include <basis/function.h>
#include <basis/guards.h>
#include <basis/istring.h>
#include <mechanisms/time_stamp.h>
#include <opsystem/application_shell.h>
#include <loggers/file_logger.h>
#include <data_struct/static_memory_gremlin.h>
#include <textual/string_manipulation.h>

#define LOG(s) EMERGENCY_LOG(program_wide_logger(), s)

//#define DUMP_SIZES
  // uncomment to see periodic dumps of the object sizes.

//const int MAX_TEST_CYCLES = 5280;  // a mile of tests...
const int MAX_TEST_CYCLES = 1000;  // only about a fifth a mile.

const int MAX_SIMULTANEOUS_OBJECTS = 100;
const int MIN_BLOCK = -20;  // negative to test range checking.
const int MAX_BLOCK = 100;
const int MIN_OBJECT = 10;
const int MAX_OBJECT = 1200 - MAX_BLOCK;

// forward.
class test_object_allocator;

test_object_allocator *_rooty = NIL;  // replaces global gnarliness.

class test_object_allocator : public application_shell
{
public:
  test_object_allocator() : application_shell(class_name()) { _rooty = this; }

  IMPLEMENT_CLASS_NAME("test_object_allocator");

  virtual int execute();
};

HOOPLE_MAIN(test_object_allocator, )

test_object_allocator &root_object() { return *_rooty; }


class floopo
{
public:
  byte _init;
  istring _dreck;

  floopo(byte init = 0)
      : _init(init), _dreck(string_manipulation::make_random_name(1, 10)) {}

  bool operator == (const floopo &a) const { return (_init == a._init); }
  bool operator != (const floopo &a) const { return (_init != a._init); }

  operator byte() const { return _init; }
};


template <class contents>
class bug_finder : public array<contents>, public virtual object_base
{
public:
  IMPLEMENT_CLASS_NAME("allocator_bug_finder");

  bug_finder(int length, u_short flags)
  : array<contents>(length, NIL, flags) {}

  bug_finder(const bug_finder &copy_from)
  : object_base(), array<contents>(copy_from) {}

  virtual ~bug_finder() {}

  bool operator == (const bug_finder &compare) const {
    if (this->length() != compare.length()) return false;
    return !memcmp(this->observe(), compare.observe(), this->length());
  }
  inline bool operator != (const bug_finder &compare) const
      { return !this->operator ==(compare); }

  bug_finder sub_bug(int start, int end) {
    if (end < start)
      return bug_finder(0, this->flags());
    bounds_return(start, 0, this->length() - 1,
        bug_finder(0, this->flags()));
    bounds_return(end, 0, this->length() - 1,
        bug_finder(0, this->flags()));
    bug_finder to_return(end - start + 1, this->flags());
    for (int i = start; i <= end; i++)
        to_return[i - start] = this->access()[i];
    return to_return;
  }

  bug_finder operator + (const bug_finder &a2) const {
    bug_finder to_return(this->length() + a2.length(), this->flags());
    for (int j = 0; j < this->length(); j++) to_return[j] = (*this)[j];
    for (int i = this->length(); i < to_return.length(); i++)
      to_return[i] = a2[i - this->length()];
    return to_return;
  }

  contents &operator [] (int index)
      { return *(contents *)&(this->access()[index]); }
  const contents &operator [] (int index) const
      { return *(contents *)&(this->observe()[index]); }

  #define use operator[]
  #define get operator[]

  void retrain(int new_size, const contents *to_copy)
      { array<contents>::retrain(new_size, (contents *)to_copy); }

  void test_allocation();
};


template <class contents>
void bug_finder<contents>::test_allocation()
{
  int outcome_size = sizeof(outcome);
  if (outcome_size != sizeof(int))
    deadly_error(class_name(), "outcome size check", "outcomes are larger than ints");

  // the space that all training for object_allocators comes from.
  contents *junk_space = new contents[MAX_OBJECT];
  for (int i = 0; i < MAX_OBJECT - 1; i++)
    junk_space[i] = contents(root_object().randomizer().inclusive('a', 'z'));
  junk_space[MAX_OBJECT - 1] = contents('\0');

  bug_finder<contents> *testers[MAX_SIMULTANEOUS_OBJECTS];
  for (int c = 0; c < MAX_SIMULTANEOUS_OBJECTS; c++) {
    // set up the initial object_allocator guys.
    testers[c] = new bug_finder<contents>(root_object().randomizer().inclusive(MIN_OBJECT,
        MAX_OBJECT), this->flags());
    if (this->flags() & byte_array::SIMPLE_COPY) {
      // copy the randomized junk space into the new object.
      memory_assign(testers[c]->access(), junk_space, testers[c]->length());
    }
  }

  enum actions { do_train, do_size, do_assign, do_access,
      do_zap, do_resizer, do_observe, do_swap, do_shrink, do_shift };

  time_stamp next_dump;

  for (int iterations = 0; iterations < MAX_TEST_CYCLES; iterations++) {
#ifdef DUMP_SIZES
    if (time_stamp() >= next_dump) {
      for (int i = 0; i < MAX_SIMULTANEOUS_OBJECTS; i++) {
        printf("%d ", testers[i]->internal_real_length());
      }
      printf("\n\n");
      next_dump = time_stamp(14 * SECOND_ms);
    }
#endif
    int index = root_object().randomizer().inclusive(0, MAX_SIMULTANEOUS_OBJECTS - 1);
    int choice = root_object().randomizer().inclusive(do_train, do_observe);
    switch (choice) {
      case do_train: {
        testers[index]->retrain(root_object().randomizer().inclusive(MIN_OBJECT, MAX_OBJECT),
            junk_space);
//hmmm: compare!
        break;
      }
      case do_size: {
        bug_finder<contents> old_version = *testers[index];
        bool at_front = bool(root_object().randomizer().inclusive(0, 1));
        int new_size = root_object().randomizer().inclusive(MIN_OBJECT, MAX_OBJECT);
        bool smaller = new_size < old_version.length();
        int difference = absolute_value(new_size - old_version.length());
        testers[index]->resize(new_size,
            at_front? common::NEW_AT_BEGINNING : common::NEW_AT_END);
        if (!smaller && difference) {
          // neuter the contents in the new section so we can compare.  this
          // space is filled however it happens to be constructed for the
          // object in question.
          if (at_front) {
            if (this->flags() & byte_array::SIMPLE_COPY)
              memset(testers[index]->access(), 'Q', difference);
            else
              for (int i = 0; i < difference; i++)
                testers[index]->use(i) = contents('Q');
          } else {
            if (this->flags() & byte_array::SIMPLE_COPY)
              memset(testers[index]->access() + old_version.length(), 'Q',
                  difference);
            else
              for (int i = old_version.length();
                  i < old_version.length() + difference; i++)
                testers[index]->use(i) = contents('Q');
          }
        }
        // now compute an equivalent form of what the state should be.
        bug_finder<contents> equivalent(0, old_version.flags());
        if (at_front) {
          if (smaller) {
            equivalent = old_version.sub_bug(difference,
                old_version.length() - 1);
          } else {
            bug_finder<contents> blank(difference, old_version.flags());
            if (this->flags() & byte_array::SIMPLE_COPY)
              memset(blank.access(), 'Q', blank.length());
            else
              for (int i = 0; i < blank.length(); i++)
                blank.use(i) = contents('Q');
            equivalent = blank + old_version;
          }
        } else {
          if (smaller) {
            equivalent = old_version.sub_bug(0, old_version.length()
                - difference - 1);
          } else {
            bug_finder<contents> blank(difference, old_version.flags());
            if (this->flags() & byte_array::SIMPLE_COPY)
              memset(blank.access(), 'Q', blank.length());
            else
              for (int i = 0; i < blank.length(); i++)
                blank.use(i) = contents('Q');
            equivalent = old_version + blank;
          }
        }
        if (equivalent.length() != testers[index]->length())
          deadly_error(class_name(), __WHERE__, "the resized form had "
              "erroneous length");
        if (this->flags() & byte_array::SIMPLE_COPY) {
          if (memcmp(testers[index]->access(), equivalent.observe(),
              equivalent.length())) 
            deadly_error(class_name(), __WHERE__, "the resized form had "
                "erroneous contents");
        } else {
          for (int i = 0; i < equivalent.length(); i++)
            if (testers[index]->use(i) != equivalent[i])
              deadly_error(class_name(), __WHERE__, "the resized form had "
                  "erroneous contents");
        }
        break;
      }
      case do_assign: {
        int to_assign = root_object().randomizer().inclusive(0, MAX_SIMULTANEOUS_OBJECTS - 1);
        *testers[index] = *testers[to_assign];
        break;
      }
      case do_access: {
        int start = root_object().randomizer().inclusive(0, testers[index]->length());
        int end = root_object().randomizer().inclusive(0, testers[index]->length());
        flip_increasing(start, end);
        for (int i = start; i < end; i++)
          testers[index]->access()[i] = contents(root_object().randomizer().inclusive(1, 255));
        break;
      }
      case do_observe: {
        int start = root_object().randomizer().inclusive(0, testers[index]->length());
        int end = root_object().randomizer().inclusive(0, testers[index]->length());
        flip_increasing(start, end);
        int total = 0;
        for (int i = start; i < end; i++)
          total += testers[index]->observe()[i];
        if (total < 20) start = total;  // compiler muffler.  
        break;
      }
      case do_resizer: {
        // tests whether the array will reuse space when it should be able to.
        bug_finder<contents> &arrh = *testers[index];
        // fill with known data.
        int i;
        for (i = 0; i < arrh.length(); i++)
          arrh[i] = contents((i + 23) % 256);
        // record the old starting point.
        const contents *start = (contents *)arrh.internal_block_start();
        int zap_amount = root_object().randomizer().inclusive(1, arrh.length() - 1);
        // now take out a chunk from the array at the beginning.
        arrh.zap(0, zap_amount - 1);
        // test the contents.
        for (i = 0; i < arrh.length(); i++)
          if (arrh[i] != contents((i + 23 + zap_amount) % 256))
            deadly_error(class_name(), __WHERE__, "the resized form "
                "had different contents");
        // now add back in the space we ate.
        arrh.resize(arrh.length() + zap_amount, common::NEW_AT_END);
        // check the pointer; it should not have changed.
        if (start != (contents *)arrh.internal_block_start())
          deadly_error(class_name(), __WHERE__, "the resized form had "
              "a different start address");
        // test the contents again.  they should start at zero and have the
        // same zap_amount offset.  the stuff past the original point shouldn't
        // be tested since we haven't set it.
        for (i = 0; i < arrh.length() - zap_amount; i++)
          if (arrh[i] != contents((i + 23 + zap_amount) % 256))
            deadly_error(class_name(), __WHERE__, "the resized form "
                "had different contents");
        // now a test of all values through the zap_amount.
        arrh.zap(0, zap_amount - 1);
        for (i = 0; i < zap_amount; i++) {
          arrh.resize(arrh.length() + 1, common::NEW_AT_END);
          if (start != (contents *)arrh.internal_block_start())
            deadly_error(class_name(), __WHERE__, "the slowly resized "
                "form had a different start address");
        }
        // test the contents once more.  they should start at zero and have
        // double the zap_amount offset.  the stuff past the original point
        // shouldn't be tested since we haven't set it.
        for (i = 0; i < arrh.length() - 2 * zap_amount; i++)
          if (arrh[i] != contents((i + 23 + 2 * zap_amount) % 256))
            deadly_error(class_name(), __WHERE__, "the slowly resized "
                "form had different contents");

        // the tests below should be nearly identical to the ones above, but
        // they use the NEW_AT_BEGINNING style of copying.

        // fill with known data.
        for (i = 0; i < arrh.length(); i++)
          arrh[i] = contents((i + 23) % 256);
        // record the old starting point.
        start = (contents *)arrh.internal_block_start();
        zap_amount = root_object().randomizer().inclusive(1, arrh.length() - 1);
        // now take out a chunk from the array at the beginning.
        arrh.zap(0, zap_amount - 1);
        // test the contents.
        for (i = 0; i < arrh.length(); i++)
          if (arrh[i] != contents((i + 23 + zap_amount) % 256))
            deadly_error(class_name(), __WHERE__, "the resized form "
                "had different contents");
        // now add back in the space we ate.
        arrh.resize(arrh.length() + zap_amount, common::NEW_AT_BEGINNING);
        // check the pointer; it should not have changed.
        if (start != (contents *)arrh.internal_block_start())
          deadly_error(class_name(), __WHERE__, "the resized form had "
              "a different start address");
        // test the contents again.  they should start at zap_amount but have
        // the same zap_amount offset.  the stuff before the original point
        // shouldn't be tested since we haven't set it.
        for (i = zap_amount; i < arrh.length(); i++)
          if (arrh[i] != contents((i + 23) % 256))
            deadly_error(class_name(), __WHERE__, "the resized form "
                "had different contents");
        // now a test of all values through the zap_amount.
        arrh.zap(0, zap_amount - 1);
        for (i = 0; i < zap_amount; i++) {
          arrh.resize(arrh.length() + 1, common::NEW_AT_BEGINNING);
          if (start != (contents *)arrh.internal_block_start())
            deadly_error(class_name(), __WHERE__, "the slowly resized "
                "form had a different start address");
        }
        // test the contents once more.  the zap_amount offset should stay the
        // same since we clobbered the place we added originally, then added
        // more space in.  so we skip the first part still.
        for (i = zap_amount; i < arrh.length(); i++)
          if (arrh[i] != contents((i + 23) % 256))
            deadly_error(class_name(), __WHERE__, "the slowly resized "
                "form had different contents");
      }
      case do_zap: {
        int start;
        int end;
        bool erroneous = false;
        int chose = root_object().randomizer().inclusive(1, 100);
        if (chose <= 90) {
          // there's a ninety percent chance we pick a range that's valid.
          start = root_object().randomizer().inclusive(0, testers[index]->length() - 1);
          end = root_object().randomizer().inclusive(0, testers[index]->length() - 1);
        } else if (chose <= 95) {
          // and a 5 percent chance we pick to choose the zero index as our
          // start; this gets at the code for fast zapping.
          start = 0;
          end = root_object().randomizer().inclusive(0, testers[index]->length() - 1);
        } else {
          // and a 5 percent chance we'll allow picking a bad index.  the
          // actual chance of picking a bad one is less.
          erroneous = true;
          start = root_object().randomizer().inclusive(-2, testers[index]->length() + 3);
          end = root_object().randomizer().inclusive(-2, testers[index]->length() + 3);
        }
        flip_increasing(start, end);
        bug_finder<contents> old_version = *testers[index];
        testers[index]->zap(start, end);
        if (!erroneous) {
          bug_finder<contents> old_head = old_version.sub_bug(0, start - 1);
          bug_finder<contents> old_tail = old_version.sub_bug(end + 1,
              old_version.length() - 1);
          bug_finder<contents> equivalent = old_head + old_tail;
          if (equivalent.length() != testers[index]->length())
            deadly_error(class_name(), __WHERE__, "the zapped form had "
                "erroneous length");
          if (this->flags() & byte_array::SIMPLE_COPY) {
            if (memcmp(testers[index]->access(), equivalent.observe(),
                equivalent.length())) 
              deadly_error(class_name(), __WHERE__, "the zapped form had "
                  "erroneous contents");
          } else {
            for (int i = 0; i < equivalent.length(); i++)
              if (testers[index]->get(i) != equivalent.get(i))
                deadly_error(class_name(), __WHERE__, "the zapped form had "
                    "erroneous contents");
          }
        }
        break;
      }
      case do_swap: {
        int first = root_object().randomizer().inclusive(0, MAX_SIMULTANEOUS_OBJECTS - 1);
        int second = first;
        while (first == second) 
          second = root_object().randomizer().inclusive(0, MAX_SIMULTANEOUS_OBJECTS - 1);
        bug_finder<contents> old_first = *testers[first];
        bug_finder<contents> old_second = *testers[second];
        testers[first]->swap_contents(*testers[second]);
        if (*testers[first] != old_second)
          deadly_error(class_name(), __WHERE__, "the old second entry was different "
              "from the new first");
        if (*testers[second] != old_first)
          deadly_error(class_name(), __WHERE__, "the old first entry was different "
              "from the new second");
        break;
      }
      case do_shrink: {
        int shrinker = root_object().randomizer().inclusive(0, MAX_SIMULTANEOUS_OBJECTS - 1);
        bug_finder<contents> old = *testers[shrinker];
        testers[shrinker]->shrink();
        if (old != *testers[shrinker])
          deadly_error(class_name(), __WHERE__, "contents were wrong after shrink");
        if (testers[shrinker]->internal_real_length() > old.length() + 1)
          deadly_error(class_name(), __WHERE__, "size was too large after shrink");
        break;
      }
      case do_shift: {
        int shifty = root_object().randomizer().inclusive(0, MAX_SIMULTANEOUS_OBJECTS - 1);
        bug_finder<contents> old = *testers[shifty];
        testers[shifty]->shift_data(bug_finder<contents>::TO_LEFT);
        if (testers[shifty]->internal_offset() != 0)
          deadly_error(class_name(), __WHERE__, "offset is wrong after shift to left");
        if (*testers[shifty] != old)
          deadly_error(class_name(), __WHERE__, "contents wrong after shift to left");
        testers[shifty]->shift_data(bug_finder<contents>::TO_RIGHT);
        if (testers[shifty]->internal_offset()
            != testers[shifty]->internal_real_length()
                 - testers[shifty]->length())
          deadly_error(class_name(), __WHERE__, "offset is wrong after shift to right");
        if (*testers[shifty] != old)
          deadly_error(class_name(), __WHERE__, "contents wrong after shift to right");
        break;
      }
      default: {
        deadly_error(class_name(), "action choice", "invalid choice!");
        break;
      }
    }
  }

  // clean up.
  delete [] junk_space;
  for (int d = 0; d < MAX_SIMULTANEOUS_OBJECTS; d++) delete testers[d];
}


int test_object_allocator::execute() {
  LOG("doing test on non-simple object.\n");
  bug_finder<floopo> complex_tester(0, bug_finder<floopo>::EXPONE
      | bug_finder<floopo>::FLUSH_INVISIBLE);
  complex_tester.test_allocation();
  LOG("finished test on non-simple object.\n");

  LOG("doing test on simple object.\n");
  bug_finder<char> simple_tester(0, bug_finder<floopo>::SIMPLE_COPY
      | bug_finder<floopo>::EXPONE);
  simple_tester.test_allocation();
  LOG("finished test on simple object.\n");

  guards::alert_message("object_allocator:: works for those "
      "functions tested.");
  return 0;
}

---