summaryrefslogtreecommitdiff
path: root/src/mem/mem_checker.hh
diff options
context:
space:
mode:
Diffstat (limited to 'src/mem/mem_checker.hh')
-rw-r--r--src/mem/mem_checker.hh568
1 files changed, 568 insertions, 0 deletions
diff --git a/src/mem/mem_checker.hh b/src/mem/mem_checker.hh
new file mode 100644
index 000000000..0ec0f08df
--- /dev/null
+++ b/src/mem/mem_checker.hh
@@ -0,0 +1,568 @@
+/*
+ * Copyright (c) 2014 ARM Limited
+ * All rights reserved.
+ *
+ * The license below extends only to copyright in the software and shall
+ * not be construed as granting a license to any other intellectual
+ * property including but not limited to intellectual property relating
+ * to a hardware implementation of the functionality of the software
+ * licensed hereunder. You may use the software subject to the license
+ * terms below provided that you ensure that this notice is replicated
+ * unmodified and in its entirety in all distributions of the software,
+ * modified or unmodified, in source code or in binary form.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met: redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer;
+ * redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution;
+ * neither the name of the copyright holders nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Authors: Rune Holm
+ * Marco Elver
+ */
+
+#ifndef __MEM_MEM_CHECKER_HH__
+#define __MEM_MEM_CHECKER_HH__
+
+#include <list>
+#include <map>
+#include <string>
+#include <vector>
+
+#include "base/hashmap.hh"
+#include "base/misc.hh"
+#include "base/types.hh"
+#include "debug/MemChecker.hh"
+#include "params/MemChecker.hh"
+#include "sim/core.hh"
+#include "sim/sim_object.hh"
+
+/**
+ * MemChecker. Verifies that reads observe the values from permissible writes.
+ * As memory operations have a start and completion time, we consider them as
+ * transactions which have a start and end time. Because of this, the lifetimes
+ * of transactions of memory operations may be overlapping -- we assume that if
+ * there is overlap between writes, they could be reordered by the memory
+ * subsystem, and a read could any of these. For more detail, see comments of
+ * inExpectedData().
+ *
+ * For simplicity, the permissible values a read can observe are only dependent
+ * on the particular location, and we do not consider the effect of multi-byte
+ * reads or writes. This precludes us from discovering single-copy atomicity
+ * violations.
+*/
+class MemChecker : public SimObject
+{
+ public:
+ /**
+ * The Serial type is used to be able to uniquely identify a transaction as
+ * it passes through the system. It's value is independent of any other
+ * system counters.
+ */
+ typedef uint64_t Serial;
+
+ static const Serial SERIAL_INITIAL = 0; //!< Initial serial
+
+ /**
+ * The initial tick the system starts with. Must not be larger than the
+ * minimum value that curTick() could return at any time in the system's
+ * execution.
+ */
+ static const Tick TICK_INITIAL = 0;
+
+ /**
+ * The maximum value that curTick() could ever return.
+ */
+ static const Tick TICK_FUTURE = MaxTick;
+
+ /**
+ * Initial data value. No requirements.
+ */
+ static const uint8_t DATA_INITIAL = 0x00;
+
+ /**
+ * The Transaction class captures the lifetimes of read and write
+ * operations, and the values they consumed or produced respectively.
+ */
+ class Transaction
+ {
+ public:
+
+ Transaction(Serial _serial,
+ Tick _start, Tick _complete,
+ uint8_t _data = DATA_INITIAL)
+ : serial(_serial),
+ start(_start), complete(_complete),
+ data(_data)
+ {}
+
+ public:
+ Serial serial; //!< Unique identifying serial
+ Tick start; //!< Start tick
+ Tick complete; //!< Completion tick
+
+ /**
+ * Depending on the memory operation, the data value either represents:
+ * for writes, the value written upon start; for reads, the value read
+ * upon completion.
+ */
+ uint8_t data;
+
+ /**
+ * Orders Transactions for use with std::map.
+ */
+ bool operator<(const Transaction& rhs) const
+ { return serial < rhs.serial; }
+ };
+
+ /**
+ * The WriteCluster class captures sets of writes where all writes are
+ * overlapping with at least one other write. Capturing writes in this way
+ * simplifies pruning of writes.
+ */
+ class WriteCluster
+ {
+ public:
+ WriteCluster()
+ : start(TICK_FUTURE), complete(TICK_FUTURE),
+ completeMax(TICK_INITIAL), numIncomplete(0)
+ {}
+
+ /**
+ * Starts a write transaction.
+ *
+ * @param serial Unique identifier of the write.
+ * @param _start When the write was sent off to the memory subsystem.
+ * @param data The data that this write passed to the memory
+ * subsystem.
+ */
+ void startWrite(Serial serial, Tick _start, uint8_t data);
+
+ /**
+ * Completes a write transaction.
+ *
+ * @param serial Unique identifier of a write *previously started*.
+ * @param _complete When the write was sent off to the memory
+ * subsystem.
+ */
+ void completeWrite(Serial serial, Tick _complete);
+
+ /**
+ * Aborts a write transaction.
+ *
+ * @param serial Unique identifier of a write *previously started*.
+ */
+ void abortWrite(Serial serial);
+
+ /**
+ * @return true if this cluster's write all completed, false otherwise.
+ */
+ bool isComplete() const { return complete != TICK_FUTURE; }
+
+ public:
+ Tick start; //!< Start of earliest write in cluster
+ Tick complete; //!< Completion of last write in cluster
+
+ /**
+ * Map of Serial --> Transaction of all writes in cluster; contains
+ * all, in-flight or already completed.
+ */
+ m5::hash_map<Serial, Transaction> writes;
+
+ private:
+ Tick completeMax;
+ size_t numIncomplete;
+ };
+
+ typedef std::list<Transaction> TransactionList;
+ typedef std::list<WriteCluster> WriteClusterList;
+
+ /**
+ * The ByteTracker keeps track of transactions for the *same byte* -- all
+ * outstanding reads, the completed reads (and what they observed) and write
+ * clusters (see WriteCluster).
+ */
+ class ByteTracker : public Named
+ {
+ public:
+
+ ByteTracker(Addr addr = 0, const MemChecker *parent = NULL)
+ : Named((parent != NULL ? parent->name() : "") +
+ csprintf(".ByteTracker@%#llx", addr))
+ {
+ // The initial transaction has start == complete == TICK_INITIAL,
+ // indicating that there has been no real write to this location;
+ // therefore, upon checking, we do not expect any particular value.
+ readObservations.emplace_back(
+ Transaction(SERIAL_INITIAL, TICK_INITIAL, TICK_INITIAL,
+ DATA_INITIAL));
+ }
+
+ /**
+ * Starts a read transaction.
+ *
+ * @param serial Unique identifier for the read.
+ * @param start When the read was sent off to the memory subsystem.
+ */
+ void startRead(Serial serial, Tick start);
+
+ /**
+ * Given a start and end time (of any read transaction), this function
+ * iterates through all data that such a read is expected to see. The
+ * data parameter is the actual value that we observed, and the
+ * function immediately returns true when a match is found, false
+ * otherwise.
+ *
+ * The set of expected data are:
+ *
+ * 1. The last value observed by a read with a completion time before
+ * this start time (if any).
+ *
+ * 2. The data produced by write transactions with a completion after
+ * the last observed read start time. Only data produced in the
+ * closest overlapping / earlier write cluster relative to this check
+ * request is considered, as writes in separate clusters are not
+ * reordered.
+ *
+ * @param start Start time of transaction to validate.
+ * @param complete End time of transaction to validate.
+ * @param data The value that we have actually seen.
+ *
+ * @return True if a match is found, false otherwise.
+ */
+ bool inExpectedData(Tick start, Tick complete, uint8_t data);
+
+ /**
+ * Completes a read transaction that is still outstanding.
+ *
+ * @param serial Unique identifier of a read *previously started*.
+ * @param complete When the read got a response.
+ * @param data The data returned by the memory subsystem.
+ */
+ bool completeRead(Serial serial, Tick complete, uint8_t data);
+
+ /**
+ * Starts a write transaction. Wrapper to startWrite of WriteCluster
+ * instance.
+ *
+ * @param serial Unique identifier of the write.
+ * @param start When the write was sent off to the memory subsystem.
+ * @param data The data that this write passed to the memory
+ * subsystem.
+ */
+ void startWrite(Serial serial, Tick start, uint8_t data);
+
+ /**
+ * Completes a write transaction. Wrapper to startWrite of WriteCluster
+ * instance.
+ *
+ * @param serial Unique identifier of a write *previously started*.
+ * @param complete When the write was sent off to the memory subsystem.
+ */
+ void completeWrite(Serial serial, Tick complete);
+
+ /**
+ * Aborts a write transaction. Wrapper to abortWrite of WriteCluster
+ * instance.
+ *
+ * @param serial Unique identifier of a write *previously started*.
+ */
+ void abortWrite(Serial serial);
+
+ /**
+ * This function returns the expected data that inExpectedData iterated
+ * through in the last call. If inExpectedData last returned true, the
+ * set may be incomplete; if inExpectedData last returned false, the
+ * vector will contain the full set.
+ *
+ * @return Reference to internally maintained vector maintaining last
+ * expected data that inExpectedData iterated through.
+ */
+ const std::vector<uint8_t>& lastExpectedData() const
+ { return _lastExpectedData; }
+
+ private:
+
+ /**
+ * Convenience function to return the most recent incomplete write
+ * cluster. Instantiates new write cluster if the most recent one has
+ * been completed.
+ *
+ * @return The most recent incomplete write cluster.
+ */
+ WriteCluster* getIncompleteWriteCluster();
+
+ /**
+ * Helper function to return an iterator to the entry of a container of
+ * Transaction compatible classes, before a certain tick.
+ *
+ * @param before Tick value which should be greater than the
+ * completion tick of the returned element.
+ *
+ * @return Iterator into container.
+ */
+ template <class TList>
+ typename TList::iterator lastCompletedTransaction(TList *l, Tick before)
+ {
+ assert(!l->empty());
+
+ // Scanning backwards increases the chances of getting a match
+ // quicker.
+ auto it = l->end();
+
+ for (--it; it != l->begin() && it->complete >= before; --it);
+
+ return it;
+ }
+
+ /**
+ * Prunes no longer needed transactions. We only keep up to the last /
+ * most recent of each, readObservations and writeClusters, before the
+ * first outstanding read.
+ *
+ * It depends on the contention / overlap between memory operations to
+ * the same location of a particular workload how large each of them
+ * would grow.
+ */
+ void pruneTransactions();
+
+ private:
+
+ /**
+ * Maintains a map of Serial -> Transaction for all outstanding reads.
+ *
+ * Use an ordered map here, as this makes pruneTransactions() more
+ * efficient (find first outstanding read).
+ */
+ std::map<Serial, Transaction> outstandingReads;
+
+ /**
+ * List of completed reads, i.e. observations of reads.
+ */
+ TransactionList readObservations;
+
+ /**
+ * List of write clusters for this address.
+ */
+ WriteClusterList writeClusters;
+
+ /**
+ * See lastExpectedData().
+ */
+ std::vector<uint8_t> _lastExpectedData;
+ };
+
+ public:
+
+ MemChecker(const MemCheckerParams *p)
+ : SimObject(p),
+ nextSerial(SERIAL_INITIAL)
+ {}
+
+ virtual ~MemChecker() {}
+
+ /**
+ * Starts a read transaction.
+ *
+ * @param start Tick this read was sent to the memory subsystem.
+ * @param addr Address for read.
+ * @param size Size of data expected.
+ *
+ * @return Serial representing the unique identifier for this transaction.
+ */
+ Serial startRead(Tick start, Addr addr, size_t size);
+
+ /**
+ * Starts a write transaction.
+ *
+ * @param start Tick when this write was sent to the memory subsystem.
+ * @param addr Address for write.
+ * @param size Size of data to be written.
+ * @param data Pointer to size bytes, containing data to be written.
+ *
+ * @return Serial representing the unique identifier for this transaction.
+ */
+ Serial startWrite(Tick start, Addr addr, size_t size, const uint8_t *data);
+
+ /**
+ * Completes a previously started read transaction.
+ *
+ * @param serial A serial of a read that was previously started and
+ * matches the address of the previously started read.
+ * @param complete Tick we received the response from the memory subsystem.
+ * @param addr Address for read.
+ * @param size Size of data received.
+ * @param data Pointer to size bytes, containing data received.
+ *
+ * @return True if the data we received is in the expected set, false
+ * otherwise.
+ */
+ bool completeRead(Serial serial, Tick complete,
+ Addr addr, size_t size, uint8_t *data);
+
+ /**
+ * Completes a previously started write transaction.
+ *
+ * @param serial A serial of a write that was previously started and
+ * matches the address of the previously started write.
+ * @param complete Tick we received acknowledgment of completion from the
+ * memory subsystem.
+ * @param addr Address for write.
+ * @param size The size of the data written.
+ */
+ void completeWrite(Serial serial, Tick complete, Addr addr, size_t size);
+
+ /**
+ * Aborts a previously started write transaction.
+ *
+ * @param serial A serial of a write that was previously started and
+ * matches the address of the previously started write.
+ * @param addr Address for write.
+ * @param size The size of the data written.
+ */
+ void abortWrite(Serial serial, Addr addr, size_t size);
+
+ /**
+ * Resets the entire checker. Note that if there are transactions
+ * in-flight, this will cause a warning to be issued if these are completed
+ * after the reset. This does not reset nextSerial to avoid such a race
+ * condition: where a transaction started before a reset with serial S,
+ * then reset() was called, followed by a start of a transaction with the
+ * same serial S and then receive a completion of the transaction before
+ * the reset with serial S.
+ */
+ void reset()
+ { byte_trackers.clear(); }
+
+ /**
+ * Resets an address-range. This may be useful in case other unmonitored
+ * parts of the system caused modification to this memory, but we cannot
+ * track their written values.
+ *
+ * @param addr Address base.
+ * @param size Size of range to be invalidated.
+ */
+ void reset(Addr addr, size_t size);
+
+ /**
+ * In completeRead, if an error is encountered, this does not print nor
+ * cause an error, but instead should be handled by the caller. However, to
+ * record information about the cause of an error, completeRead creates an
+ * errorMessage. This function returns the last error that was detected in
+ * completeRead.
+ *
+ * @return Reference to string of error message.
+ */
+ const std::string& getErrorMessage() const { return errorMessage; }
+
+ private:
+ /**
+ * Returns the instance of ByteTracker for the requested location.
+ */
+ ByteTracker* getByteTracker(Addr addr)
+ {
+ auto it = byte_trackers.find(addr);
+ if (it == byte_trackers.end()) {
+ it = byte_trackers.insert(
+ std::make_pair(addr, ByteTracker(addr, this))).first;
+ }
+ return &it->second;
+ };
+
+ private:
+ /**
+ * Detailed error message of the last violation in completeRead.
+ */
+ std::string errorMessage;
+
+ /**
+ * Next distinct serial to be assigned to the next transaction to be
+ * started.
+ */
+ Serial nextSerial;
+
+ /**
+ * Maintain a map of address --> byte-tracker. Per-byte entries are
+ * initialized as needed.
+ *
+ * The required space for this obviously grows with the number of distinct
+ * addresses used for a particular workload. The used size is independent on
+ * the number of nodes in the system, those may affect the size of per-byte
+ * tracking information.
+ *
+ * Access via getByteTracker()!
+ */
+ m5::hash_map<Addr, ByteTracker> byte_trackers;
+};
+
+inline MemChecker::Serial
+MemChecker::startRead(Tick start, Addr addr, size_t size)
+{
+ DPRINTF(MemChecker,
+ "starting read: serial = %d, start = %d, addr = %#llx, "
+ "size = %d\n", nextSerial, start, addr , size);
+
+ for (size_t i = 0; i < size; ++i) {
+ getByteTracker(addr + i)->startRead(nextSerial, start);
+ }
+
+ return nextSerial++;
+}
+
+inline MemChecker::Serial
+MemChecker::startWrite(Tick start, Addr addr, size_t size, const uint8_t *data)
+{
+ DPRINTF(MemChecker,
+ "starting write: serial = %d, start = %d, addr = %#llx, "
+ "size = %d\n", nextSerial, start, addr, size);
+
+ for (size_t i = 0; i < size; ++i) {
+ getByteTracker(addr + i)->startWrite(nextSerial, start, data[i]);
+ }
+
+ return nextSerial++;
+}
+
+inline void
+MemChecker::completeWrite(MemChecker::Serial serial, Tick complete,
+ Addr addr, size_t size)
+{
+ DPRINTF(MemChecker,
+ "completing write: serial = %d, complete = %d, "
+ "addr = %#llx, size = %d\n", serial, complete, addr, size);
+
+ for (size_t i = 0; i < size; ++i) {
+ getByteTracker(addr + i)->completeWrite(serial, complete);
+ }
+}
+
+inline void
+MemChecker::abortWrite(MemChecker::Serial serial, Addr addr, size_t size)
+{
+ DPRINTF(MemChecker,
+ "aborting write: serial = %d, addr = %#llx, size = %d\n",
+ serial, addr, size);
+
+ for (size_t i = 0; i < size; ++i) {
+ getByteTracker(addr + i)->abortWrite(serial);
+ }
+}
+
+#endif // __MEM_MEM_CHECKER_HH__
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-27 16:46:09 +0000