testing/modify.h

   1 // -*- Mode: C++ -*-
   2 class Mutator {
   3 public:
   4   virtual ~Mutator() { }
   5   virtual void Mutate(SegmentMap *table,
   6                       const SegmentMap *source_table,
   7                       MTRandom *rand) const = 0;
   8 };
   9
  10 class Change {
  11 public:
  12   enum Kind {
  13     MODIFY = 1,     // Mutate a certain range w/ random or supplied data
  14     ADD = 2,        // Insert random or supplied data
  15     DELETE = 3,     // Delete a specified range of data
  16     COPY = 4,       // Copy from one region, inserting elsewhere
  17     MOVE = 5,       // Copy then delete copied-from range
  18     COPYOVER = 6    // Copy then delete copied-to range
  19
  20     // ADD, DELETE, and COPY change the file size
  21     // MODIFY, MOVE, COPYOVER preserve the file size
  22   };
  23
  24   // Constructor for modify, add, delete.
  25   Change(Kind kind0, xoff_t size0, xoff_t addr1_0)
  26     : kind(kind0),
  27       size(size0),
  28       addr1(addr1_0),
  29       addr2(0),
  30       insert(NULL) {
  31     CHECK(kind != MOVE && kind != COPY && kind != COPYOVER);
  32   }
  33
  34   // Constructor for modify, add w/ provided data.
  35   Change(Kind kind0, xoff_t size0, xoff_t addr1_0, Segment *insert0)
  36     : kind(kind0),
  37       size(size0),
  38       addr1(addr1_0),
  39       addr2(0),
  40       insert(insert0) {
  41     CHECK(kind != MOVE && kind != COPY && kind != COPYOVER);
  42   }
  43
  44   // Constructor for move, copy, overwrite
  45   Change(Kind kind0, xoff_t size0, xoff_t addr1_0, xoff_t addr2_0)
  46     : kind(kind0),
  47       size(size0),
  48       addr1(addr1_0),
  49       addr2(addr2_0),
  50       insert(NULL) {
  51     CHECK(kind == MOVE || kind == COPY || kind == COPYOVER);
  52   }
  53
  54   Kind kind;
  55   xoff_t size;
  56   xoff_t addr1;
  57   xoff_t addr2;
  58   Segment *insert;  // For modify and/or add
  59 };
  60
  61 typedef list<Change> ChangeList;
  62 typedef typename ChangeList::const_iterator ConstChangeListIterator;
  63 typedef typename ChangeList::iterator ChangeListIterator;
  64
  65 class ChangeListMutator : public Mutator {
  66 public:
  67   ChangeListMutator(const ChangeList &cl)
  68     : cl_(cl) { }
  69
  70   ChangeListMutator() { }
  71
  72   void Mutate(SegmentMap *table,
  73               const SegmentMap *source_table,
  74               MTRandom *rand) const {
  75     // The speed of processing gigabytes of data is so slow compared with
  76     // these table-copy operations, no attempt to make this fast.
  77     SegmentMap tmp;
  78
  79     for (ConstChangeListIterator iter(cl_.begin());
  80          iter != cl_.end(); ++iter) {
  81       const Change &ch = *iter;
  82       tmp.clear();
  83       Mutate(ch, &tmp, source_table, rand);
  84       tmp.swap(*table);
  85       source_table = table;
  86     }
  87   }
  88
  89   static void Mutate(const Change &ch,
  90                      SegmentMap *table,
  91                      const SegmentMap *source_table,
  92                      MTRandom *rand) {
  93     switch (ch.kind) {
  94     case Change::ADD:
  95       AddChange(ch, table, source_table, rand);
  96       break;
  97     case Change::MODIFY:
  98       ModifyChange(ch, table, source_table, rand);
  99       break;
 100     case Change::DELETE:
 101       DeleteChange(ch, table, source_table, rand);
 102       break;
 103     case Change::COPY:
 104       CopyChange(ch, table, source_table, rand);
 105       break;
 106     case Change::MOVE:
 107       MoveChange(ch, table, source_table, rand);
 108       break;
 109     case Change::COPYOVER:
 110       OverwriteChange(ch, table, source_table, rand);
 111       break;
 112     }
 113   }
 114
 115   static void ModifyChange(const Change &ch,
 116                            SegmentMap *table,
 117                            const SegmentMap *source_table,
 118                            MTRandom *rand) {
 119     xoff_t m_start = ch.addr1;
 120     xoff_t m_end = m_start + ch.size;
 121     xoff_t i_start = 0;
 122     xoff_t i_end = 0;
 123
 124     for (ConstSegmentMapIterator iter(source_table->begin());
 125          iter != source_table->end();
 126          ++iter) {
 127       const Segment &seg = iter->second;
 128       i_start = iter->first;
 129       i_end = i_start + seg.Size();
 130
 131       if (i_end <= m_start || i_start >= m_end) {
 132         table->insert(table->end(), make_pair(i_start, seg));
 133         continue;
 134       }
 135
 136       if (i_start < m_start) {
 137         table->insert(table->end(),
 138                       make_pair(i_start,
 139                                 seg.Subseg(0, m_start - i_start)));
 140       }
 141
 142       // Insert the entire segment, even though it may extend into later
 143       // segments.  This condition avoids inserting it during later
 144       // segments.
 145       if (m_start >= i_start) {
 146         if (ch.insert != NULL) {
 147           table->insert(table->end(), make_pair(m_start, *ch.insert));
 148         } else {
 149           Segment part(m_end - m_start, rand);
 150           table->insert(table->end(), make_pair(m_start, part));
 151         }
 152       }
 153
 154       if (i_end > m_end) {
 155         table->insert(table->end(),
 156                       make_pair(m_end,
 157                                 seg.Subseg(m_end - i_start, i_end - m_end)));
 158       }
 159     }
 160
 161     // This check verifies that the modify does not extend past the
 162     // source_table EOF.
 163     CHECK_LE(m_end, i_end);
 164   }
 165
 166   static void AddChange(const Change &ch,
 167                         SegmentMap *table,
 168                         const SegmentMap *source_table,
 169                         MTRandom *rand) {
 170     xoff_t m_start = ch.addr1;
 171     xoff_t i_start = 0;
 172     xoff_t i_end = 0;
 173
 174     for (ConstSegmentMapIterator iter(source_table->begin());
 175          iter != source_table->end();
 176          ++iter) {
 177       const Segment &seg = iter->second;
 178       i_start = iter->first;
 179       i_end = i_start + seg.Size();
 180
 181       if (i_end <= m_start) {
 182         table->insert(table->end(), make_pair(i_start, seg));
 183         continue;
 184       }
 185
 186       if (i_start > m_start) {
 187         table->insert(table->end(), make_pair(i_start + ch.size, seg));
 188         continue;
 189       }
 190
 191       if (i_start < m_start) {
 192         table->insert(table->end(),
 193                       make_pair(i_start,
 194                                 seg.Subseg(0, m_start - i_start)));
 195       }
 196
 197       if (ch.insert != NULL) {
 198         table->insert(table->end(), make_pair(m_start, *ch.insert));
 199       } else {
 200         Segment addseg(ch.size, rand);
 201         table->insert(table->end(), make_pair(m_start, addseg));
 202       }
 203
 204       if (m_start < i_end) {
 205         table->insert(table->end(),
 206                       make_pair(m_start + ch.size,
 207                                 seg.Subseg(m_start - i_start,
 208                                            i_end - m_start)));
 209       }
 210     }
 211
 212     CHECK_LE(m_start, i_end);
 213
 214     // Special case for add at end-of-input.
 215     if (m_start == i_end) {
 216       Segment addseg(ch.size, rand);
 217       table->insert(table->end(), make_pair(m_start, addseg));
 218     }
 219   }
 220
 221   static void DeleteChange(const Change &ch,
 222                            SegmentMap *table,
 223                            const SegmentMap *source_table,
 224                            MTRandom *rand) {
 225     xoff_t m_start = ch.addr1;
 226     xoff_t m_end = m_start + ch.size;
 227     xoff_t i_start = 0;
 228     xoff_t i_end = 0;
 229
 230     for (ConstSegmentMapIterator iter(source_table->begin());
 231          iter != source_table->end();
 232          ++iter) {
 233       const Segment &seg = iter->second;
 234       i_start = iter->first;
 235       i_end = i_start + seg.Size();
 236
 237       if (i_end <= m_start) {
 238         table->insert(table->end(), make_pair(i_start, seg));
 239         continue;
 240       }
 241
 242       if (i_start >= m_end) {
 243         table->insert(table->end(), make_pair(i_start - ch.size, seg));
 244         continue;
 245       }
 246
 247       if (i_start < m_start) {
 248         table->insert(table->end(),
 249                       make_pair(i_start,
 250                                 seg.Subseg(0, m_start - i_start)));
 251       }
 252
 253       if (i_end > m_end) {
 254         table->insert(table->end(),
 255                       make_pair(m_end - ch.size,
 256                                 seg.Subseg(m_end - i_start, i_end - m_end)));
 257       }
 258     }
 259
 260     CHECK_LT(m_start, i_end);
 261     CHECK_LE(m_end, i_end);
 262   }
 263
 264   // A move is a copy followed by delete of the copied-from range.
 265   static void MoveChange(const Change &ch,
 266                          SegmentMap *table,
 267                          const SegmentMap *source_table,
 268                          MTRandom *rand) {
 269     SegmentMap tmp;
 270     CHECK_NE(ch.addr1, ch.addr2);
 271     CopyChange(ch, &tmp, source_table, rand);
 272     Change d(Change::DELETE, ch.size,
 273              ch.addr1 < ch.addr2 ? ch.addr1 : ch.addr1 + ch.size);
 274     DeleteChange(d, table, &tmp, rand);
 275   }
 276
 277   // An overwrite is a copy followed by a delete of the copied-to range.
 278   static void OverwriteChange(const Change &ch,
 279                               SegmentMap *table,
 280                               const SegmentMap *source_table,
 281                               MTRandom *rand) {
 282     SegmentMap tmp;
 283     CHECK_NE(ch.addr1, ch.addr2);
 284     CopyChange(ch, &tmp, source_table, rand);
 285     Change d(Change::DELETE, ch.size, ch.addr2 + ch.size);
 286     DeleteChange(d, table, &tmp, rand);
 287   }
 288
 289   static void CopyChange(const Change &ch,
 290                          SegmentMap *table,
 291                          const SegmentMap *source_table,
 292                          MTRandom *ignore) {
 293     xoff_t m_start = ch.addr2;
 294     xoff_t c_start = ch.addr1;
 295     xoff_t i_start = 0;
 296     xoff_t i_end = 0;
 297
 298     // Like AddChange() with AppendCopy instead of a random segment.
 299     for (ConstSegmentMapIterator iter(source_table->begin());
 300          iter != source_table->end();
 301          ++iter) {
 302       const Segment &seg = iter->second;
 303       i_start = iter->first;
 304       i_end = i_start + seg.Size();
 305
 306       if (i_end <= m_start) {
 307         table->insert(table->end(), make_pair(i_start, seg));
 308         continue;
 309       }
 310
 311       if (i_start > m_start) {
 312         table->insert(table->end(), make_pair(i_start + ch.size, seg));
 313         continue;
 314       }
 315
 316       if (i_start < m_start) {
 317         table->insert(table->end(),
 318                       make_pair(i_start,
 319                                 seg.Subseg(0, m_start - i_start)));
 320       }
 321
 322       AppendCopy(table, source_table, c_start, m_start, ch.size);
 323
 324       if (m_start < i_end) {
 325         table->insert(table->end(),
 326                       make_pair(m_start + ch.size,
 327                                 seg.Subseg(m_start - i_start, i_end - m_start)));
 328       }
 329     }
 330
 331     CHECK_LE(m_start, i_end);
 332
 333     // Special case for copy to end-of-input.
 334     if (m_start == i_end) {
 335       AppendCopy(table, source_table, c_start, m_start, ch.size);
 336     }
 337   }
 338
 339   static void AppendCopy(SegmentMap *table,
 340                          const SegmentMap *source_table,
 341                          xoff_t copy_offset,
 342                          xoff_t append_offset,
 343                          xoff_t length) {
 344     ConstSegmentMapIterator pos(source_table->upper_bound(copy_offset));
 345     --pos;
 346     xoff_t got = 0;
 347
 348     while (got < length) {
 349       size_t seg_offset = copy_offset - pos->first;
 350       size_t advance = min(pos->second.Size() - seg_offset,
 351                            (size_t)(length - got));
 352
 353       table->insert(table->end(),
 354                     make_pair(append_offset,
 355                               pos->second.Subseg(seg_offset,
 356                                                  advance)));
 357
 358       got += advance;
 359       copy_offset += advance;
 360       append_offset += advance;
 361       ++pos;
 362     }
 363   }
 364
 365   ChangeList* Changes() {
 366     return &cl_;
 367   }
 368
 369   const ChangeList* Changes() const {
 370     return &cl_;
 371   }
 372
 373 private:
 374   ChangeList cl_;
 375 };
 376
 377 class Modify1stByte : public Mutator {
 378 public:
 379   void Mutate(SegmentMap *table,
 380               const SegmentMap *source_table,
 381               MTRandom *rand) const {
 382     ChangeListMutator::Mutate(Change(Change::MODIFY, 1, 0),
 383                               table, source_table, rand);
 384   }
 385 };