1 // -*- Mode: C++ -*- 2 class Mutator { 3 public: ~Mutator()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 DELRANGE = 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, DELRANGE, and COPY change the file size 21 // MODIFY, MOVE, COPYOVER preserve the file size 22 }; 23 24 // Constructor for modify, add, delete. Change(Kind kind0,xoff_t size0,xoff_t addr1_0)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. Change(Kind kind0,xoff_t size0,xoff_t addr1_0,Segment * insert0)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 Change(Kind kind0,xoff_t size0,xoff_t addr1_0,xoff_t addr2_0)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: ChangeListMutator(const ChangeList & cl)67 ChangeListMutator(const ChangeList &cl) 68 : cl_(cl) { } 69 ChangeListMutator()70 ChangeListMutator() { } 71 Mutate(SegmentMap * table,const SegmentMap * source_table,MTRandom * rand)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 Mutate(const Change & ch,SegmentMap * table,const SegmentMap * source_table,MTRandom * rand)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::DELRANGE: 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 ModifyChange(const Change & ch,SegmentMap * table,const SegmentMap * source_table,MTRandom * rand)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 AddChange(const Change & ch,SegmentMap * table,const SegmentMap * source_table,MTRandom * rand)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 DeleteChange(const Change & ch,SegmentMap * table,const SegmentMap * source_table,MTRandom * rand)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. MoveChange(const Change & ch,SegmentMap * table,const SegmentMap * source_table,MTRandom * rand)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::DELRANGE, 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. OverwriteChange(const Change & ch,SegmentMap * table,const SegmentMap * source_table,MTRandom * rand)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::DELRANGE, ch.size, ch.addr2 + ch.size); 286 DeleteChange(d, table, &tmp, rand); 287 } 288 CopyChange(const Change & ch,SegmentMap * table,const SegmentMap * source_table,MTRandom * ignore)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 AppendCopy(SegmentMap * table,const SegmentMap * source_table,xoff_t copy_offset,xoff_t append_offset,xoff_t length)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 Changes()365 ChangeList* Changes() { 366 return &cl_; 367 } 368 Changes()369 const ChangeList* Changes() const { 370 return &cl_; 371 } 372 373 private: 374 ChangeList cl_; 375 }; 376 377 class Modify1stByte : public Mutator { 378 public: Mutate(SegmentMap * table,const SegmentMap * source_table,MTRandom * rand)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 }; 386