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