src/mem/mem_checker.hh

   1 /*
   2  * Copyright (c) 2014 ARM Limited
   3  * All rights reserved.
   4  *
   5  * The license below extends only to copyright in the software and shall
   6  * not be construed as granting a license to any other intellectual
   7  * property including but not limited to intellectual property relating
   8  * to a hardware implementation of the functionality of the software
   9  * licensed hereunder.  You may use the software subject to the license
  10  * terms below provided that you ensure that this notice is replicated
  11  * unmodified and in its entirety in all distributions of the software,
  12  * modified or unmodified, in source code or in binary form.
  13  *
  14  * Redistribution and use in source and binary forms, with or without
  15  * modification, are permitted provided that the following conditions are
  16  * met: redistributions of source code must retain the above copyright
  17  * notice, this list of conditions and the following disclaimer;
  18  * redistributions in binary form must reproduce the above copyright
  19  * notice, this list of conditions and the following disclaimer in the
  20  * documentation and/or other materials provided with the distribution;
  21  * neither the name of the copyright holders nor the names of its
  22  * contributors may be used to endorse or promote products derived from
  23  * this software without specific prior written permission.
  24  *
  25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  26  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  27  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  28  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  29  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  30  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  31  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  32  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  33  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  34  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  35  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  36  */
  37
  38 #ifndef __MEM_MEM_CHECKER_HH__
  39 #define __MEM_MEM_CHECKER_HH__
  40
  41 #include <cassert>
  42 #include <cstdint>
  43 #include <list>
  44 #include <map>
  45 #include <string>
  46 #include <unordered_map>
  47 #include <vector>
  48
  49 #include "base/cprintf.hh"
  50 #include "base/trace.hh"
  51 #include "base/types.hh"
  52 #include "debug/MemChecker.hh"
  53 #include "params/MemChecker.hh"
  54 #include "sim/core.hh"
  55 #include "sim/sim_object.hh"
  56
  57 /**
  58  * MemChecker. Verifies that reads observe the values from permissible writes.
  59  * As memory operations have a start and completion time, we consider them as
  60  * transactions which have a start and end time. Because of this, the lifetimes
  61  * of transactions of memory operations may be overlapping -- we assume that if
  62  * there is overlap between writes, they could be reordered by the memory
  63  * subsystem, and a read could any of these.  For more detail, see comments of
  64  * inExpectedData().
  65  *
  66  * For simplicity, the permissible values a read can observe are only dependent
  67  * on the particular location, and we do not consider the effect of multi-byte
  68  * reads or writes. This precludes us from discovering single-copy atomicity
  69  * violations.
  70 */
  71 class MemChecker : public SimObject
  72 {
  73   public:
  74     /**
  75      * The Serial type is used to be able to uniquely identify a transaction as
  76      * it passes through the system. It's value is independent of any other
  77      * system counters.
  78      */
  79     typedef uint64_t Serial;
  80
  81     static const Serial  SERIAL_INITIAL = 0; //!< Initial serial
  82
  83     /**
  84      * The initial tick the system starts with. Must not be larger than the
  85      * minimum value that curTick() could return at any time in the system's
  86      * execution.
  87      */
  88     static const Tick    TICK_INITIAL   = 0;
  89
  90     /**
  91      * The maximum value that curTick() could ever return.
  92      */
  93     static const Tick    TICK_FUTURE  = MaxTick;
  94
  95     /**
  96      * Initial data value. No requirements.
  97      */
  98     static const uint8_t DATA_INITIAL   = 0x00;
  99
 100     /**
 101      * The Transaction class captures the lifetimes of read and write
 102      * operations, and the values they consumed or produced respectively.
 103      */
 104     class Transaction
 105     {
 106       public:
 107
 108         Transaction(Serial _serial,
 109                     Tick _start, Tick _complete,
 110                     uint8_t _data = DATA_INITIAL)
 111             : serial(_serial),
 112               start(_start), complete(_complete),
 113               data(_data)
 114         {}
 115
 116       public:
 117         Serial serial; //!< Unique identifying serial
 118         Tick start;    //!< Start tick
 119         Tick complete; //!< Completion tick
 120
 121         /**
 122          * Depending on the memory operation, the data value either represents:
 123          * for writes, the value written upon start; for reads, the value read
 124          * upon completion.
 125          */
 126         uint8_t data;
 127
 128         /**
 129          * Orders Transactions for use with std::map.
 130          */
 131         bool operator<(const Transaction& rhs) const
 132         { return serial < rhs.serial; }
 133     };
 134
 135     /**
 136      * The WriteCluster class captures sets of writes where all writes are
 137      * overlapping with at least one other write. Capturing writes in this way
 138      * simplifies pruning of writes.
 139      */
 140     class WriteCluster
 141     {
 142       public:
 143         WriteCluster()
 144             : start(TICK_FUTURE), complete(TICK_FUTURE),
 145               completeMax(TICK_INITIAL), numIncomplete(0)
 146         {}
 147
 148         /**
 149          * Starts a write transaction.
 150          *
 151          * @param serial  Unique identifier of the write.
 152          * @param _start  When the write was sent off to the memory subsystem.
 153          * @param data    The data that this write passed to the memory
 154          *                subsystem.
 155          */
 156         void startWrite(Serial serial, Tick _start, uint8_t data);
 157
 158         /**
 159          * Completes a write transaction.
 160          *
 161          * @param serial    Unique identifier of a write *previously started*.
 162          * @param _complete When the write was sent off to the memory
 163          *                  subsystem.
 164          */
 165         void completeWrite(Serial serial, Tick _complete);
 166
 167         /**
 168          * Aborts a write transaction.
 169          *
 170          * @param serial Unique identifier of a write *previously started*.
 171          */
 172         void abortWrite(Serial serial);
 173
 174         /**
 175          * @return true if this cluster's write all completed, false otherwise.
 176          */
 177         bool isComplete() const { return complete != TICK_FUTURE; }
 178
 179       public:
 180         Tick start;     //!< Start of earliest write in cluster
 181         Tick complete;  //!< Completion of last write in cluster
 182
 183         /**
 184          * Map of Serial --> Transaction of all writes in cluster; contains
 185          * all, in-flight or already completed.
 186          */
 187         std::unordered_map<Serial, Transaction> writes;
 188
 189       private:
 190         Tick completeMax;
 191         size_t numIncomplete;
 192     };
 193
 194     typedef std::list<Transaction> TransactionList;
 195     typedef std::list<WriteCluster> WriteClusterList;
 196
 197     /**
 198      * The ByteTracker keeps track of transactions for the *same byte* -- all
 199      * outstanding reads, the completed reads (and what they observed) and write
 200      * clusters (see WriteCluster).
 201      */
 202     class ByteTracker : public Named
 203     {
 204       public:
 205
 206         ByteTracker(Addr addr = 0, const MemChecker *parent = NULL)
 207             : Named((parent != NULL ? parent->name() : "") +
 208                      csprintf(".ByteTracker@%#llx", addr))
 209         {
 210             // The initial transaction has start == complete == TICK_INITIAL,
 211             // indicating that there has been no real write to this location;
 212             // therefore, upon checking, we do not expect any particular value.
 213             readObservations.emplace_back(
 214                     Transaction(SERIAL_INITIAL, TICK_INITIAL, TICK_INITIAL,
 215                                 DATA_INITIAL));
 216         }
 217
 218         /**
 219          * Starts a read transaction.
 220          *
 221          * @param serial  Unique identifier for the read.
 222          * @param start   When the read was sent off to the memory subsystem.
 223          */
 224         void startRead(Serial serial, Tick start);
 225
 226         /**
 227          * Given a start and end time (of any read transaction), this function
 228          * iterates through all data that such a read is expected to see. The
 229          * data parameter is the actual value that we observed, and the
 230          * function immediately returns true when a match is found, false
 231          * otherwise.
 232          *
 233          * The set of expected data are:
 234          *
 235          * 1. The last value observed by a read with a completion time before
 236          *    this start time (if any).
 237          *
 238          * 2. The data produced by write transactions with a completion after
 239          *    the last observed read start time. Only data produced in the
 240          *    closest overlapping / earlier write cluster relative to this check
 241          *    request is considered, as writes in separate clusters are not
 242          *    reordered.
 243          *
 244          * @param start     Start time of transaction to validate.
 245          * @param complete  End time of transaction to validate.
 246          * @param data      The value that we have actually seen.
 247          *
 248          * @return          True if a match is found, false otherwise.
 249          */
 250         bool inExpectedData(Tick start, Tick complete, uint8_t data);
 251
 252         /**
 253          * Completes a read transaction that is still outstanding.
 254          *
 255          * @param serial   Unique identifier of a read *previously started*.
 256          * @param complete When the read got a response.
 257          * @param data     The data returned by the memory subsystem.
 258          */
 259         bool completeRead(Serial serial, Tick complete, uint8_t data);
 260
 261         /**
 262          * Starts a write transaction. Wrapper to startWrite of WriteCluster
 263          * instance.
 264          *
 265          * @param serial  Unique identifier of the write.
 266          * @param start   When the write was sent off to the memory subsystem.
 267          * @param data    The data that this write passed to the memory
 268          *                subsystem.
 269          */
 270         void startWrite(Serial serial, Tick start, uint8_t data);
 271
 272         /**
 273          * Completes a write transaction. Wrapper to startWrite of WriteCluster
 274          * instance.
 275          *
 276          * @param serial   Unique identifier of a write *previously started*.
 277          * @param complete When the write was sent off to the memory subsystem.
 278          */
 279         void completeWrite(Serial serial, Tick complete);
 280
 281         /**
 282          * Aborts a write transaction. Wrapper to abortWrite of WriteCluster
 283          * instance.
 284          *
 285          * @param serial Unique identifier of a write *previously started*.
 286          */
 287         void abortWrite(Serial serial);
 288
 289         /**
 290          * This function returns the expected data that inExpectedData iterated
 291          * through in the last call. If inExpectedData last returned true, the
 292          * set may be incomplete; if inExpectedData last returned false, the
 293          * vector will contain the full set.
 294          *
 295          * @return Reference to internally maintained vector maintaining last
 296          *         expected data that inExpectedData iterated through.
 297          */
 298         const std::vector<uint8_t>& lastExpectedData() const
 299         { return _lastExpectedData; }
 300
 301       private:
 302
 303         /**
 304          * Convenience function to return the most recent incomplete write
 305          * cluster. Instantiates new write cluster if the most recent one has
 306          * been completed.
 307          *
 308          * @return The most recent incomplete write cluster.
 309          */
 310         WriteCluster* getIncompleteWriteCluster();
 311
 312         /**
 313          * Helper function to return an iterator to the entry of a container of
 314          * Transaction compatible classes, before a certain tick.
 315          *
 316          * @param before Tick value which should be greater than the
 317          *               completion tick of the returned element.
 318          *
 319          * @return Iterator into container.
 320          */
 321         template <class TList>
 322         typename TList::iterator lastCompletedTransaction(TList *l, Tick before)
 323         {
 324             assert(!l->empty());
 325
 326             // Scanning backwards increases the chances of getting a match
 327             // quicker.
 328             auto it = l->end();
 329
 330             for (--it; it != l->begin() && it->complete >= before; --it);
 331
 332             return it;
 333         }
 334
 335         /**
 336          * Prunes no longer needed transactions. We only keep up to the last /
 337          * most recent of each, readObservations and writeClusters, before the
 338          * first outstanding read.
 339          *
 340          * It depends on the contention / overlap between memory operations to
 341          * the same location of a particular workload how large each of them
 342          * would grow.
 343          */
 344         void pruneTransactions();
 345
 346       private:
 347
 348         /**
 349          * Maintains a map of Serial -> Transaction for all outstanding reads.
 350          *
 351          * Use an ordered map here, as this makes pruneTransactions() more
 352          * efficient (find first outstanding read).
 353          */
 354         std::map<Serial, Transaction> outstandingReads;
 355
 356         /**
 357          * List of completed reads, i.e. observations of reads.
 358          */
 359         TransactionList readObservations;
 360
 361         /**
 362          * List of write clusters for this address.
 363          */
 364         WriteClusterList writeClusters;
 365
 366         /**
 367          * See lastExpectedData().
 368          */
 369         std::vector<uint8_t> _lastExpectedData;
 370     };
 371
 372   public:
 373
 374     MemChecker(const MemCheckerParams &p)
 375         : SimObject(p),
 376           nextSerial(SERIAL_INITIAL)
 377     {}
 378
 379     virtual ~MemChecker() {}
 380
 381     /**
 382      * Starts a read transaction.
 383      *
 384      * @param start  Tick this read was sent to the memory subsystem.
 385      * @param addr   Address for read.
 386      * @param size   Size of data expected.
 387      *
 388      * @return Serial representing the unique identifier for this transaction.
 389      */
 390     Serial startRead(Tick start, Addr addr, size_t size);
 391
 392     /**
 393      * Starts a write transaction.
 394      *
 395      * @param start Tick when this write was sent to the memory subsystem.
 396      * @param addr  Address for write.
 397      * @param size  Size of data to be written.
 398      * @param data  Pointer to size bytes, containing data to be written.
 399      *
 400      * @return Serial representing the unique identifier for this transaction.
 401      */
 402     Serial startWrite(Tick start, Addr addr, size_t size, const uint8_t *data);
 403
 404     /**
 405      * Completes a previously started read transaction.
 406      *
 407      * @param serial    A serial of a read that was previously started and
 408      *                  matches the address of the previously started read.
 409      * @param complete  Tick we received the response from the memory subsystem.
 410      * @param addr      Address for read.
 411      * @param size      Size of data received.
 412      * @param data      Pointer to size bytes, containing data received.
 413      *
 414      * @return True if the data we received is in the expected set, false
 415      *         otherwise.
 416      */
 417     bool completeRead(Serial serial, Tick complete,
 418                       Addr addr, size_t size, uint8_t *data);
 419
 420     /**
 421      * Completes a previously started write transaction.
 422      *
 423      * @param serial    A serial of a write that was previously started and
 424      *                  matches the address of the previously started write.
 425      * @param complete  Tick we received acknowledgment of completion from the
 426      *                  memory subsystem.
 427      * @param addr      Address for write.
 428      * @param size      The size of the data written.
 429      */
 430     void completeWrite(Serial serial, Tick complete, Addr addr, size_t size);
 431
 432     /**
 433      * Aborts a previously started write transaction.
 434      *
 435      * @param serial    A serial of a write that was previously started and
 436      *                  matches the address of the previously started write.
 437      * @param addr      Address for write.
 438      * @param size      The size of the data written.
 439      */
 440     void abortWrite(Serial serial, Addr addr, size_t size);
 441
 442     /**
 443      * Resets the entire checker. Note that if there are transactions
 444      * in-flight, this will cause a warning to be issued if these are completed
 445      * after the reset. This does not reset nextSerial to avoid such a race
 446      * condition: where a transaction started before a reset with serial S,
 447      * then reset() was called, followed by a start of a transaction with the
 448      * same serial S and then receive a completion of the transaction before
 449      * the reset with serial S.
 450      */
 451     void reset()
 452     { byte_trackers.clear(); }
 453
 454     /**
 455      * Resets an address-range. This may be useful in case other unmonitored
 456      * parts of the system caused modification to this memory, but we cannot
 457      * track their written values.
 458      *
 459      * @param addr Address base.
 460      * @param size Size of range to be invalidated.
 461      */
 462     void reset(Addr addr, size_t size);
 463
 464     /**
 465      * In completeRead, if an error is encountered, this does not print nor
 466      * cause an error, but instead should be handled by the caller. However, to
 467      * record information about the cause of an error, completeRead creates an
 468      * errorMessage. This function returns the last error that was detected in
 469      * completeRead.
 470      *
 471      * @return Reference to string of error message.
 472      */
 473     const std::string& getErrorMessage() const { return errorMessage; }
 474
 475   private:
 476     /**
 477      * Returns the instance of ByteTracker for the requested location.
 478      */
 479     ByteTracker* getByteTracker(Addr addr)
 480     {
 481         auto it = byte_trackers.find(addr);
 482         if (it == byte_trackers.end()) {
 483             it = byte_trackers.insert(
 484                 std::make_pair(addr, ByteTracker(addr, this))).first;
 485         }
 486         return &it->second;
 487     };
 488
 489   private:
 490     /**
 491      * Detailed error message of the last violation in completeRead.
 492      */
 493     std::string errorMessage;
 494
 495     /**
 496      * Next distinct serial to be assigned to the next transaction to be
 497      * started.
 498      */
 499     Serial nextSerial;
 500
 501     /**
 502      * Maintain a map of address --> byte-tracker. Per-byte entries are
 503      * initialized as needed.
 504      *
 505      * The required space for this obviously grows with the number of distinct
 506      * addresses used for a particular workload. The used size is independent on
 507      * the number of nodes in the system, those may affect the size of per-byte
 508      * tracking information.
 509      *
 510      * Access via getByteTracker()!
 511      */
 512     std::unordered_map<Addr, ByteTracker> byte_trackers;
 513 };
 514
 515 inline MemChecker::Serial
 516 MemChecker::startRead(Tick start, Addr addr, size_t size)
 517 {
 518     DPRINTF(MemChecker,
 519             "starting read: serial = %d, start = %d, addr = %#llx, "
 520             "size = %d\n", nextSerial, start, addr , size);
 521
 522     for (size_t i = 0; i < size; ++i) {
 523         getByteTracker(addr + i)->startRead(nextSerial, start);
 524     }
 525
 526     return nextSerial++;
 527 }
 528
 529 inline MemChecker::Serial
 530 MemChecker::startWrite(Tick start, Addr addr, size_t size, const uint8_t *data)
 531 {
 532     DPRINTF(MemChecker,
 533             "starting write: serial = %d, start = %d, addr = %#llx, "
 534             "size = %d\n", nextSerial, start, addr, size);
 535
 536     for (size_t i = 0; i < size; ++i) {
 537         getByteTracker(addr + i)->startWrite(nextSerial, start, data[i]);
 538     }
 539
 540     return nextSerial++;
 541 }
 542
 543 inline void
 544 MemChecker::completeWrite(MemChecker::Serial serial, Tick complete,
 545                           Addr addr, size_t size)
 546 {
 547     DPRINTF(MemChecker,
 548             "completing write: serial = %d, complete = %d, "
 549             "addr = %#llx, size = %d\n", serial, complete, addr, size);
 550
 551     for (size_t i = 0; i < size; ++i) {
 552         getByteTracker(addr + i)->completeWrite(serial, complete);
 553     }
 554 }
 555
 556 inline void
 557 MemChecker::abortWrite(MemChecker::Serial serial, Addr addr, size_t size)
 558 {
 559     DPRINTF(MemChecker,
 560             "aborting write: serial = %d, addr = %#llx, size = %d\n",
 561             serial, addr, size);
 562
 563     for (size_t i = 0; i < size; ++i) {
 564         getByteTracker(addr + i)->abortWrite(serial);
 565     }
 566 }
 567
 568 #endif // __MEM_MEM_CHECKER_HH__