src/mem/mem_checker.cc

   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 #include <cassert>
  42
  43 #include "mem/mem_checker.hh"
  44
  45 void
  46 MemChecker::WriteCluster::startWrite(MemChecker::Serial serial, Tick _start,
  47                                      uint8_t data)
  48 {
  49     assert(!isComplete());
  50
  51     if (start == TICK_FUTURE) {
  52         // Initialize a fresh write cluster
  53         start = _start;
  54     }
  55     chatty_assert(start <= _start, "WriteClusters must filled in order!");
  56
  57     ++numIncomplete;
  58
  59     if (complete != TICK_FUTURE) {
  60        // Reopen a closed write cluster
  61         assert(_start < complete);  // should open a new write cluster, instead;
  62         // also somewhat fishy wrt causality / ordering of calls vs time
  63         // progression TODO: Check me!
  64         complete = TICK_FUTURE;
  65     }
  66
  67     // Create new transaction, and denote completion time to be in the future.
  68     writes.insert(std::make_pair(serial,
  69                   MemChecker::Transaction(serial, _start, TICK_FUTURE, data)));
  70 }
  71
  72 void
  73 MemChecker::WriteCluster::completeWrite(MemChecker::Serial serial, Tick _complete)
  74 {
  75     auto it = writes.find(serial);
  76
  77     if (it == writes.end()) {
  78         warn("Could not locate write transaction: serial = %d, complete = %d\n",
  79              serial, _complete);
  80         return;
  81     }
  82
  83     // Record completion time of the write
  84     assert(it->second.complete == TICK_FUTURE);
  85     it->second.complete = _complete;
  86
  87     // Update max completion time for the cluster
  88     if (completeMax < _complete) {
  89         completeMax = _complete;
  90     }
  91
  92     if (--numIncomplete == 0) {
  93         // All writes have completed, this cluster is now complete and will be
  94         // assigned the max of completion tick values among all writes.
  95         //
  96         // Note that we cannot simply keep updating complete, because that would
  97         // count the cluster as closed already.  Instead, we keep TICK_FUTURE
  98         // until all writes have completed.
  99         complete = completeMax;
 100     }
 101 }
 102
 103 void
 104 MemChecker::WriteCluster::abortWrite(MemChecker::Serial serial)
 105 {
 106     if (!writes.erase(serial)) {
 107         warn("Could not locate write transaction: serial = %d\n", serial);
 108         return;
 109     }
 110
 111     if (--numIncomplete == 0 && !writes.empty()) {
 112         // This write cluster is now complete, and we can assign the current
 113         // completeMax value.
 114         complete = completeMax;
 115     }
 116
 117     // Note: this WriteCluster is in pristine state if this was the only
 118     // write present; the cluster will get reused through
 119     // getIncompleteWriteCluster().
 120 }
 121
 122 void
 123 MemChecker::ByteTracker::startRead(MemChecker::Serial serial, Tick start)
 124 {
 125     outstandingReads.insert(std::make_pair(serial,
 126             MemChecker::Transaction(serial, start, TICK_FUTURE)));
 127 }
 128
 129 bool
 130 MemChecker::ByteTracker::inExpectedData(Tick start, Tick complete, uint8_t data)
 131 {
 132     _lastExpectedData.clear();
 133
 134     bool wc_overlap = true;
 135
 136     // Find the last value read from the location
 137     const Transaction& last_obs =
 138         *lastCompletedTransaction(&readObservations, start);
 139     bool last_obs_valid = (last_obs.complete != TICK_INITIAL);
 140
 141     // Scan backwards through the write clusters to find the closest younger
 142     // preceding & overlapping writes.
 143     for (auto cluster = writeClusters.rbegin();
 144          cluster != writeClusters.rend() && wc_overlap; ++cluster) {
 145         for (const auto& addr_write : cluster->writes) {
 146             const Transaction& write = addr_write.second;
 147
 148             if (write.complete < last_obs.start) {
 149                 // If this write transaction completed before the last
 150                 // observation, we ignore it as the last_observation has the
 151                 // correct value
 152                 continue;
 153             }
 154
 155             if (write.data == data) {
 156                 // Found a match, end search.
 157                 return true;
 158             }
 159
 160             // Record possible, but non-matching data for debugging
 161             _lastExpectedData.push_back(write.data);
 162
 163             if (write.complete > start) {
 164                 // This write overlapped with the transaction we want to check
 165                 // -> continue checking the overlapping write cluster
 166                 continue;
 167             }
 168
 169             // This write cluster has writes that have completed before the
 170             // checked transaction. There is no need to check an earlier
 171             // write-cluster -> set the exit condition for the outer loop
 172             wc_overlap = false;
 173
 174             if (last_obs.complete < write.start) {
 175                 // We found a write which started after the last observed read,
 176                 // therefore we can not longer consider the value seen by the
 177                 // last observation as a valid expected value.
 178                 //
 179                 // Once all writes have been iterated through, we can check if
 180                 // the last observation is still valid to compare against.
 181                 last_obs_valid = false;
 182             }
 183         }
 184     }
 185
 186     // We have not found any matching write, so far; check other sources of
 187     // confirmation
 188     if (last_obs_valid) {
 189         // The last observation is not outdated according to the writes we have
 190         // seen so far.
 191         assert(last_obs.complete <= start);
 192         if (last_obs.data == data) {
 193             // Matched data from last observation -> all good
 194             return true;
 195         }
 196         // Record non-matching, but possible value
 197         _lastExpectedData.push_back(last_obs.data);
 198     }
 199
 200     if (_lastExpectedData.empty()) {
 201         assert(last_obs.complete == TICK_INITIAL);
 202         // We have not found any possible (non-matching data). Can happen in
 203         // initial system state
 204         DPRINTF(MemChecker, "no last observation nor write! start = %d, "\
 205                 "complete = %d, data = %#x\n", start, complete, data);
 206         return true;
 207     }
 208     return false;
 209 }
 210
 211 bool
 212 MemChecker::ByteTracker::completeRead(MemChecker::Serial serial,
 213                                       Tick complete, uint8_t data)
 214 {
 215     auto it = outstandingReads.find(serial);
 216
 217     if (it == outstandingReads.end()) {
 218         // Can happen if concurrent with reset_address_range
 219         warn("Could not locate read transaction: serial = %d, complete = %d\n",
 220              serial, complete);
 221         return true;
 222     }
 223
 224     Tick start = it->second.start;
 225     outstandingReads.erase(it);
 226
 227     // Verify data
 228     const bool result = inExpectedData(start, complete, data);
 229
 230     readObservations.emplace_back(serial, start, complete, data);
 231     pruneTransactions();
 232
 233     return result;
 234 }
 235
 236 MemChecker::WriteCluster*
 237 MemChecker::ByteTracker::getIncompleteWriteCluster()
 238 {
 239     if (writeClusters.empty() || writeClusters.back().isComplete()) {
 240         writeClusters.emplace_back();
 241     }
 242
 243     return &writeClusters.back();
 244 }
 245
 246 void
 247 MemChecker::ByteTracker::startWrite(MemChecker::Serial serial, Tick start,
 248                                     uint8_t data)
 249 {
 250     getIncompleteWriteCluster()->startWrite(serial, start, data);
 251 }
 252
 253 void
 254 MemChecker::ByteTracker::completeWrite(MemChecker::Serial serial, Tick complete)
 255 {
 256     getIncompleteWriteCluster()->completeWrite(serial, complete);
 257     pruneTransactions();
 258 }
 259
 260 void
 261 MemChecker::ByteTracker::abortWrite(MemChecker::Serial serial)
 262 {
 263     getIncompleteWriteCluster()->abortWrite(serial);
 264 }
 265
 266 void
 267 MemChecker::ByteTracker::pruneTransactions()
 268 {
 269     // Obtain tick of first outstanding read. If there are no outstanding
 270     // reads, we use curTick(), i.e. we will remove all readObservation except
 271     // the most recent one.
 272     const Tick before = outstandingReads.empty() ? curTick() :
 273                         outstandingReads.begin()->second.start;
 274
 275     // Pruning of readObservations
 276     readObservations.erase(readObservations.begin(),
 277                            lastCompletedTransaction(&readObservations, before));
 278
 279     // Pruning of writeClusters
 280     if (!writeClusters.empty()) {
 281         writeClusters.erase(writeClusters.begin(),
 282                             lastCompletedTransaction(&writeClusters, before));
 283     }
 284 }
 285
 286 bool
 287 MemChecker::completeRead(MemChecker::Serial serial, Tick complete,
 288                          Addr addr, size_t size, uint8_t *data)
 289 {
 290     bool result = true;
 291
 292     DPRINTF(MemChecker,
 293             "completing read: serial = %d, complete = %d, "
 294             "addr = %#llx, size = %d\n", serial, complete, addr, size);
 295
 296     for (size_t i = 0; i < size; ++i) {
 297         ByteTracker *tracker = getByteTracker(addr + i);
 298
 299         if (!tracker->completeRead(serial, complete, data[i])) {
 300             // Generate error message, and aggregate all failures for the bytes
 301             // considered in this transaction in one message.
 302             if (result) {
 303                 result = false;
 304                 errorMessage = "";
 305             } else {
 306                 errorMessage += "\n";
 307             }
 308
 309             errorMessage += csprintf("  Read transaction for address %#llx "
 310                                      "failed: received %#x, expected ",
 311                                      (unsigned long long)(addr + i), data[i]);
 312
 313             for (size_t j = 0; j < tracker->lastExpectedData().size(); ++j) {
 314                 errorMessage +=
 315                     csprintf("%#x%s",
 316                              tracker->lastExpectedData()[j],
 317                              (j == tracker->lastExpectedData().size() - 1)
 318                              ? "" : "|");
 319             }
 320         }
 321     }
 322
 323     if (!result) {
 324         DPRINTF(MemChecker, "read of %#llx @ cycle %d failed:\n%s\n", addr,
 325                 complete, errorMessage);
 326     }
 327
 328     return result;
 329 }
 330
 331 void
 332 MemChecker::reset(Addr addr, size_t size)
 333 {
 334     for (size_t i = 0; i < size; ++i) {
 335         byte_trackers.erase(addr + i);
 336     }
 337 }
 338
 339 MemChecker*
 340 MemCheckerParams::create()
 341 {
 342     return new MemChecker(this);
 343 }