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