Greetings everyone,
So I've tested this patch and it appears to eliminate the corner case I've
talked about. This patch isn't based on master so it probably won't apply,
but it's not a very complicated patch.
For further optimization it would probably be useful to move the block of
code that scans the pendingRequests_ list into the annul_request() function
so it's not doing it every time an entry is cleared (since in theory if
nothing is annulled, the dependence chain has been followed so everyone
should point to the correct idx).
I also forgot to include the assertion that catches this bug.
@@ -816,11 +819,37 @@ bool CacheController::clear_entry_cb(void *arg)
if(queueEntry->depends >= 0) {
CacheQueueEntry* depEntry = &pendingRequests_[
queueEntry->depends];
- memoryHierarchy_->add_event(&cacheAccess_, 1,
depEntry);
+ assert(queueEntry->dependsAddr >= 0);
+ if (unlikely (!depEntry->annuled &&
queueEntry->dependsAddr != depEntry->request->get_physical_address()))
+ {
+ assert(0);
+ }
+ else
+ {
+ memoryHierarchy_->add_event(&cacheAccess_,
1, depEntry);
+ }
Again, it's unlikely that you'd ever see this bug with the stock mesiBus.
Just for reference, fluidanimate from parsec does a great job of
exacerbating this problem since it appears to ping pong a lot of cache lines
into and out of the L2 at certain points in the simulation.
-Paul
On Sun, Apr 3, 2011 at 8:19 PM, DRAM Ninjas <[email protected]> wrote:
> Actually I would hold off on changing that code. I realized that the
> problem is a little more subtle than what I initially thought. So storing
> the address was a good detection algorithm, but it doesn't fix the problem
> fully.
>
> Going back to my example, if entry A will wake up B and X takes B's spot,
> then you can build an incorrect dependence chain such that:
>
> A--> X --> Y (where Y is some valid request that comes in while A is still
> waiting for memory)
>
> But now, if you simply detect that X is the wrong entry and drop it, Y (a
> legitimate dependency) will never be sent for access. I have a fix that I'm
> currently testing (essentially going through the pending list and removing
> any depends fields that point to freed entries),
>
> If it works, I'll let you know.
>
> On Sun, Apr 3, 2011 at 8:11 PM, avadh patel <[email protected]> wrote:
>
>>
>>
>> On Sat, Apr 2, 2011 at 10:27 PM, DRAM Ninjas <[email protected]>wrote:
>>
>>> So actually I just noticed that annulled entries don't seem to get freed
>>> at all ... the only .free() in cacheController.cpp is in clear_entry_cb
>>> which will only free an entry if it's not annulled ....
>>>
>>> 'annul_request' function calls 'clear_entry_cb' right before it sets the
>> 'annuled' flag to 'true'. So 'clear_entry_cb' will free this annulled entry.
>>
>> Regarding your previous email, thanks for finding this bug. Your idea of
>> using 'address' to verify that dependent entry really need to be waken up is
>> good and I'll change the code to fix this problem.
>>
>> Thanks,
>> Avadh
>>
>>
>>> Maybe the contradicts my whole theory ... or perhaps I'm going crazy at
>>> this point ...
>>>
>>> On Sat, Apr 2, 2011 at 7:58 PM, DRAM Ninjas <[email protected]>wrote:
>>>
>>>> Let me start off by saying that the cache code works fine in the
>>>> mainline MARSSx86, however I've come across an interesting corner case that
>>>> could arise when trying to do something like what I am trying to do:
>>>> writing
>>>> a ridiculous bus model that will push as many requests to the memory system
>>>> as fast as possible. It might be something to think about since this
>>>> paradigm is used throughout the ptlsim code.
>>>>
>>>> I have an 8 core setup with a shared L2. All of the L1I/D and the L2
>>>> caches are on the mesiBus. When a request arrives at the L2 cache, the code
>>>> checks for dependencies. It finds the last dependence in the chain, stores
>>>> the idx value in the CacheQueueEntry->depends, and stashes the request for
>>>> later. Later on, when a request goes through clear_entry_cb, it will check
>>>> if something was dependent on it and then schedule that dependent entry for
>>>> cache access.
>>>>
>>>> So far so good.
>>>>
>>>> What happens in a pathological case like the one I've built is that the
>>>> rate at which requests pile up in the L2 is so high that the following
>>>> happens:
>>>>
>>>> - Request B comes into the L2, finds a dependence on request A
>>>> - RequestA->depends is set to the idx of B (since now B depends on A, A
>>>> will wake up B when A finishes)
>>>> - Let's say request A is waiting on a memory request so its takes at
>>>> least 100 cycles
>>>> - RequestB is annulled because an L1 cache fulfilled the request
>>>> (RequestB's pending entry is freed)
>>>> - 100 more requests come in while A is waiting on memory
>>>> - since B got annulled, and 100 more requests came in, the slot that
>>>> used to be occupied by B (which is now annulled and dead) is now occupied
>>>> by
>>>> X
>>>> - A completes the memory access, executes and wakes up the dependent
>>>> entry: pendingRequests_[depends] -- which is the idx of where B was, but is
>>>> now X (and since X is valid, A cannot tell the difference since all it has
>>>> is the idx)
>>>> - X is incorrectly woken up and sent for cache access
>>>>
>>>> It took me about 2 weeks to figure out what was happening. A normal
>>>> mesiBus won't encounter this corner case because it's way too slow and so
>>>> there will never be a high enough request rate to have the pendingRequests_
>>>> cycle back around and refill that entry with something else. Chances are
>>>> it'll just stay in that queue and just be marked free (invalid).
>>>>
>>>> However, it's something to consider since this type of memory pooling is
>>>> very prevalent throughout the code.
>>>>
>>>> The way I'm currently mitigating this error is by storing not only the
>>>> idx of the dependent entry, but also the address of that entry. That way,
>>>> if
>>>> I find idx but the address doesn't match what I saved back when it was
>>>> queued, I can safely assume that the entry got annulled and someone else
>>>> took its place, so I just ignore the dependent entry.
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>
>>> _______________________________________________
>>> http://www.marss86.org
>>> Marss86-Devel mailing list
>>> [email protected]
>>> https://www.cs.binghamton.edu/mailman/listinfo/marss86-devel
>>>
>>>
>>
>
diff --git a/ptlsim/cache/cacheController.cpp b/ptlsim/cache/cacheController.cpp
index efa9ef2..5a7f305 100644
--- a/ptlsim/cache/cacheController.cpp
+++ b/ptlsim/cache/cacheController.cpp
@@ -341,6 +341,7 @@ bool CacheController::handle_interconnect_cb(void *arg)
/* Found an dependency */
memdebug("dependent entry: ", *dependsOn, endl);
dependsOn->depends = queueEntry->idx;
+ dependsOn->dependsAddr = queueEntry->request->get_physical_address();
OP_TYPE type = queueEntry->request->get_type();
bool kernel_req = queueEntry->request->is_kernel();
if(type == MEMORY_OP_READ) {
@@ -823,8 +824,18 @@ bool CacheController::clear_entry_cb(void *arg)
if(!queueEntry->annuled) {
if(pendingRequests_.list().count == 0) {
ptl_logfile << "Removing from pending request queue ",
- pendingRequests_, " \nQueueEntry: ",
- queueEntry, endl;
+ pendingRequests_, " \nQueueEntry: ",
+ queueEntry, endl;
+ }
+
+ // make sure that no pending entry will wake up the removed entry (in the case of annuled)
+ int removed_idx = queueEntry->idx;
+ CacheQueueEntry *tmpEntry;
+ foreach_list_mutable(pendingRequests_.list(), tmpEntry, entry, nextentry) {
+ if(tmpEntry->depends == removed_idx) {
+ tmpEntry->depends = -1;
+ tmpEntry->dependsAddr = -1;
+ }
}
pendingRequests_.free(queueEntry);
}
diff --git a/ptlsim/cache/cacheController.h b/ptlsim/cache/cacheController.h
index 900aa1d..2d89569 100644
--- a/ptlsim/cache/cacheController.h
+++ b/ptlsim/cache/cacheController.h
@@ -181,6 +181,7 @@ struct CacheQueueEntry : public FixStateListObject
{
public:
int depends;
+ W64 dependsAddr;
bitvec<CACHE_NO_EVENTS> eventFlags;
@@ -196,6 +197,7 @@ struct CacheQueueEntry : public FixStateListObject
sender = null;
sendTo = null;
depends = -1;
+ dependsAddr = -1;
eventFlags.reset();
annuled = false;
prefetch = false;
@@ -210,6 +212,7 @@ struct CacheQueueEntry : public FixStateListObject
os << "Request{", *request, "} ";
+ os << "idx["<< this->idx <<"] ";
if(sender)
os << "sender[" << sender->get_name() << "] ";
else
_______________________________________________
http://www.marss86.org
Marss86-Devel mailing list
[email protected]
https://www.cs.binghamton.edu/mailman/listinfo/marss86-devel
