gem5  v20.1.0.0
eventq.cc
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2000-2005 The Regents of The University of Michigan
3  * Copyright (c) 2008 The Hewlett-Packard Development Company
4  * Copyright (c) 2013 Advanced Micro Devices, Inc.
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions are
9  * met: redistributions of source code must retain the above copyright
10  * notice, this list of conditions and the following disclaimer;
11  * redistributions in binary form must reproduce the above copyright
12  * notice, this list of conditions and the following disclaimer in the
13  * documentation and/or other materials provided with the distribution;
14  * neither the name of the copyright holders nor the names of its
15  * contributors may be used to endorse or promote products derived from
16  * this software without specific prior written permission.
17  *
18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29  */
30 
31 #include "sim/eventq.hh"
32 
33 #include <cassert>
34 #include <iostream>
35 #include <string>
36 #include <unordered_map>
37 #include <vector>
38 
39 #include "base/logging.hh"
40 #include "base/trace.hh"
41 #include "cpu/smt.hh"
42 #include "debug/Checkpoint.hh"
43 #include "sim/core.hh"
44 
45 using namespace std;
46 
48 
49 //
50 // Main Event Queues
51 //
52 // Events on these queues are processed at the *beginning* of each
53 // cycle, before the pipeline simulation is performed.
54 //
55 uint32_t numMainEventQueues = 0;
57 __thread EventQueue *_curEventQueue = NULL;
58 bool inParallelMode = false;
59 
60 EventQueue *
62 {
63  while (numMainEventQueues <= index) {
65  mainEventQueue.push_back(
66  new EventQueue(csprintf("MainEventQueue-%d", index)));
67  }
68 
69  return mainEventQueue[index];
70 }
71 
72 #ifndef NDEBUG
74 #endif
75 
77 {
78  assert(!scheduled());
79  flags = 0;
80 }
81 
82 const std::string
83 Event::name() const
84 {
85  return csprintf("Event_%s", instanceString());
86 }
87 
88 
89 Event *
91 {
92  // Either way, event will be the top element in the 'in bin' list
93  // which is the pointer we need in order to look into the list, so
94  // we need to insert that into the bin list.
95  if (!curr || *event < *curr) {
96  // Insert the event before the current list since it is in the future.
97  event->nextBin = curr;
98  event->nextInBin = NULL;
99  } else {
100  // Since we're on the correct list, we need to point to the next list
101  event->nextBin = curr->nextBin; // curr->nextBin can now become stale
102 
103  // Insert event at the top of the stack
104  event->nextInBin = curr;
105  }
106 
107  return event;
108 }
109 
110 void
112 {
113  // Deal with the head case
114  if (!head || *event <= *head) {
115  head = Event::insertBefore(event, head);
116  return;
117  }
118 
119  // Figure out either which 'in bin' list we are on, or where a new list
120  // needs to be inserted
121  Event *prev = head;
122  Event *curr = head->nextBin;
123  while (curr && *curr < *event) {
124  prev = curr;
125  curr = curr->nextBin;
126  }
127 
128  // Note: this operation may render all nextBin pointers on the
129  // prev 'in bin' list stale (except for the top one)
130  prev->nextBin = Event::insertBefore(event, curr);
131 }
132 
133 Event *
135 {
136  Event *curr = top;
137  Event *next = top->nextInBin;
138 
139  // if we removed the top item, we need to handle things specially
140  // and just remove the top item, fixing up the next bin pointer of
141  // the new top item
142  if (event == top) {
143  if (!next)
144  return top->nextBin;
145  next->nextBin = top->nextBin;
146  return next;
147  }
148 
149  // Since we already checked the current element, we're going to
150  // keep checking event against the next element.
151  while (event != next) {
152  if (!next)
153  panic("event not found!");
154 
155  curr = next;
156  next = next->nextInBin;
157  }
158 
159  // remove next from the 'in bin' list since it's what we're looking for
160  curr->nextInBin = next->nextInBin;
161  return top;
162 }
163 
164 void
166 {
167  if (head == NULL)
168  panic("event not found!");
169 
170  assert(event->queue == this);
171 
172  // deal with an event on the head's 'in bin' list (event has the same
173  // time as the head)
174  if (*head == *event) {
175  head = Event::removeItem(event, head);
176  return;
177  }
178 
179  // Find the 'in bin' list that this event belongs on
180  Event *prev = head;
181  Event *curr = head->nextBin;
182  while (curr && *curr < *event) {
183  prev = curr;
184  curr = curr->nextBin;
185  }
186 
187  if (!curr || *curr != *event)
188  panic("event not found!");
189 
190  // curr points to the top item of the the correct 'in bin' list, when
191  // we remove an item, it returns the new top item (which may be
192  // unchanged)
193  prev->nextBin = Event::removeItem(event, curr);
194 }
195 
196 Event *
198 {
199  std::lock_guard<EventQueue> lock(*this);
200  Event *event = head;
201  Event *next = head->nextInBin;
202  event->flags.clear(Event::Scheduled);
203 
204  if (next) {
205  // update the next bin pointer since it could be stale
206  next->nextBin = head->nextBin;
207 
208  // pop the stack
209  head = next;
210  } else {
211  // this was the only element on the 'in bin' list, so get rid of
212  // the 'in bin' list and point to the next bin list
213  head = head->nextBin;
214  }
215 
216  // handle action
217  if (!event->squashed()) {
218  // forward current cycle to the time when this event occurs.
219  setCurTick(event->when());
220  if (DTRACE(Event))
221  event->trace("executed");
222  event->process();
223  if (event->isExitEvent()) {
224  assert(!event->flags.isSet(Event::Managed) ||
225  !event->flags.isSet(Event::IsMainQueue)); // would be silly
226  return event;
227  }
228  } else {
229  event->flags.clear(Event::Squashed);
230  }
231 
232  event->release();
233 
234  return NULL;
235 }
236 
237 void
239 {
240  SERIALIZE_SCALAR(_when);
241  SERIALIZE_SCALAR(_priority);
242  short _flags = flags;
243  SERIALIZE_SCALAR(_flags);
244 }
245 
246 void
248 {
249  assert(!scheduled());
250 
251  UNSERIALIZE_SCALAR(_when);
252  UNSERIALIZE_SCALAR(_priority);
253 
254  FlagsType _flags;
255  UNSERIALIZE_SCALAR(_flags);
256 
257  // Old checkpoints had no concept of the Initialized flag
258  // so restoring from old checkpoints always fail.
259  // Events are initialized on construction but original code
260  // "flags = _flags" would just overwrite the initialization.
261  // So, read in the checkpoint flags, but then set the Initialized
262  // flag on top of it in order to avoid failures.
263  assert(initialized());
264  flags = _flags;
265  flags.set(Initialized);
266 
267  // need to see if original event was in a scheduled, unsquashed
268  // state, but don't want to restore those flags in the current
269  // object itself (since they aren't immediately true)
270  if (flags.isSet(Scheduled) && !flags.isSet(Squashed)) {
271  flags.clear(Squashed | Scheduled);
272  } else {
273  DPRINTF(Checkpoint, "Event '%s' need to be scheduled @%d\n",
274  name(), _when);
275  }
276 }
277 
278 void
280 {
281  // It's safe to call insert() directly here since this method
282  // should only be called when restoring from a checkpoint (which
283  // happens before thread creation).
284  if (event->flags.isSet(Event::Scheduled))
285  insert(event);
286 }
287 void
289 {
290  cprintf("============================================================\n");
291  cprintf("EventQueue Dump (cycle %d)\n", curTick());
292  cprintf("------------------------------------------------------------\n");
293 
294  if (empty())
295  cprintf("<No Events>\n");
296  else {
297  Event *nextBin = head;
298  while (nextBin) {
299  Event *nextInBin = nextBin;
300  while (nextInBin) {
301  nextInBin->dump();
302  nextInBin = nextInBin->nextInBin;
303  }
304 
305  nextBin = nextBin->nextBin;
306  }
307  }
308 
309  cprintf("============================================================\n");
310 }
311 
312 bool
314 {
315  std::unordered_map<long, bool> map;
316 
317  Tick time = 0;
318  short priority = 0;
319 
320  Event *nextBin = head;
321  while (nextBin) {
322  Event *nextInBin = nextBin;
323  while (nextInBin) {
324  if (nextInBin->when() < time) {
325  cprintf("time goes backwards!");
326  nextInBin->dump();
327  return false;
328  } else if (nextInBin->when() == time &&
329  nextInBin->priority() < priority) {
330  cprintf("priority inverted!");
331  nextInBin->dump();
332  return false;
333  }
334 
335  if (map[reinterpret_cast<long>(nextInBin)]) {
336  cprintf("Node already seen");
337  nextInBin->dump();
338  return false;
339  }
340  map[reinterpret_cast<long>(nextInBin)] = true;
341 
342  time = nextInBin->when();
343  priority = nextInBin->priority();
344 
345  nextInBin = nextInBin->nextInBin;
346  }
347 
348  nextBin = nextBin->nextBin;
349  }
350 
351  return true;
352 }
353 
354 Event*
356 {
357  Event* t = head;
358  head = s;
359  return t;
360 }
361 
362 void
364 {
365  for (uint32_t i = 0; i < numMainEventQueues; ++i) {
366  mainEventQueue[i]->dump();
367  }
368 }
369 
370 
371 const char *
373 {
374  return "generic";
375 }
376 
377 void
378 Event::trace(const char *action)
379 {
380  // This DPRINTF is unconditional because calls to this function
381  // are protected by an 'if (DTRACE(Event))' in the inlined Event
382  // methods.
383  //
384  // This is just a default implementation for derived classes where
385  // it's not worth doing anything special. If you want to put a
386  // more informative message in the trace, override this method on
387  // the particular subclass where you have the information that
388  // needs to be printed.
389  DPRINTF_UNCONDITIONAL(Event, "%s %s %s @ %d\n",
390  description(), instanceString(), action, when());
391 }
392 
393 const std::string
395 {
396 #ifndef NDEBUG
397  return csprintf("%d", instance);
398 #else
399  return csprintf("%#x", (uintptr_t)this);
400 #endif
401 }
402 
403 void
404 Event::dump() const
405 {
406  cprintf("Event %s (%s)\n", name(), description());
407  cprintf("Flags: %#x\n", flags);
408 #ifdef EVENTQ_DEBUG
409  cprintf("Created: %d\n", whenCreated);
410 #endif
411  if (scheduled()) {
412 #ifdef EVENTQ_DEBUG
413  cprintf("Scheduled at %d\n", whenScheduled);
414 #endif
415  cprintf("Scheduled for %d, priority %d\n", when(), _priority);
416  } else {
417  cprintf("Not Scheduled\n");
418  }
419 }
420 
421 EventQueue::EventQueue(const string &n)
422  : objName(n), head(NULL), _curTick(0)
423 {
424 }
425 
426 void
428 {
429  async_queue_mutex.lock();
430  async_queue.push_back(event);
431  async_queue_mutex.unlock();
432 }
433 
434 void
436 {
437  assert(this == curEventQueue());
438  async_queue_mutex.lock();
439 
440  while (!async_queue.empty()) {
441  insert(async_queue.front());
442  async_queue.pop_front();
443  }
444 
445  async_queue_mutex.unlock();
446 }
EventQueue::debugVerify
bool debugVerify() const
Definition: eventq.cc:313
Event::unserialize
void unserialize(CheckpointIn &cp) override
Unserialize an object.
Definition: eventq.cc:247
Event::nextBin
Event * nextBin
Definition: eventq.hh:260
EventQueue::serviceOne
Event * serviceOne()
Definition: eventq.cc:197
EventQueue::async_queue_mutex
std::mutex async_queue_mutex
Mutex to protect async queue.
Definition: eventq.hh:625
Event::insertBefore
static Event * insertBefore(Event *event, Event *curr)
Definition: eventq.cc:90
getEventQueue
EventQueue * getEventQueue(uint32_t index)
Function for returning eventq queue for the provided index.
Definition: eventq.cc:61
MipsISA::index
Bitfield< 30, 0 > index
Definition: pra_constants.hh:44
UNSERIALIZE_SCALAR
#define UNSERIALIZE_SCALAR(scalar)
Definition: serialize.hh:797
EventQueue::checkpointReschedule
void checkpointReschedule(Event *event)
Reschedule an event after a checkpoint.
Definition: eventq.cc:279
ArmISA::i
Bitfield< 7 > i
Definition: miscregs_types.hh:63
EventBase::Scheduled
static const FlagsType Scheduled
Definition: eventq.hh:100
EventQueue::replaceHead
Event * replaceHead(Event *s)
function for replacing the head of the event queue, so that a different set of events can run without...
Definition: eventq.cc:355
EventQueue::async_queue
std::list< Event * > async_queue
List of events added by other threads to this event queue.
Definition: eventq.hh:628
inParallelMode
bool inParallelMode
Current mode of execution: parallel / serial.
Definition: eventq.cc:58
X86ISA::lock
Bitfield< 5 > lock
Definition: types.hh:77
Tick
uint64_t Tick
Tick count type.
Definition: types.hh:63
Event::dump
void dump() const
Dump the current event data.
Definition: eventq.cc:404
top
Definition: test.h:61
DTRACE
#define DTRACE(x)
Definition: debug.hh:146
std::vector
STL vector class.
Definition: stl.hh:37
EventQueue::dump
void dump() const
This is a debugging function which will print everything on the event queue.
Definition: eventq.cc:288
Event::flags
Flags flags
Definition: eventq.hh:268
Event::description
virtual const char * description() const
Return a C string describing the event.
Definition: eventq.cc:372
EventBase::IsMainQueue
static const FlagsType IsMainQueue
Definition: eventq.hh:110
Event::when
Tick when() const
Get the time that the event is scheduled.
Definition: eventq.hh:503
EventBase::Managed
static const FlagsType Managed
Definition: eventq.hh:101
ArmISA::n
Bitfield< 31 > n
Definition: miscregs_types.hh:450
Counter
int64_t Counter
Statistics counter type.
Definition: types.hh:58
mainEventQueue
vector< EventQueue * > mainEventQueue
Array for main event queues.
Definition: eventq.cc:56
smt.hh
cp
Definition: cprintf.cc:40
dumpMainQueue
void dumpMainQueue()
Definition: eventq.cc:363
Flags::clear
void clear()
Definition: flags.hh:85
Event
Definition: eventq.hh:246
cprintf
void cprintf(const char *format, const Args &...args)
Definition: cprintf.hh:152
EventBase::FlagsType
unsigned short FlagsType
Definition: eventq.hh:94
DPRINTF
#define DPRINTF(x,...)
Definition: trace.hh:234
Event::nextInBin
Event * nextInBin
Definition: eventq.hh:261
MipsISA::event
Bitfield< 10, 5 > event
Definition: pra_constants.hh:297
EventQueue::handleAsyncInsertions
void handleAsyncInsertions()
Function for moving events from the async_queue to the main queue.
Definition: eventq.cc:435
Event::trace
virtual void trace(const char *action)
This function isn't really useful if TRACING_ON is not defined.
Definition: eventq.cc:378
curEventQueue
EventQueue * curEventQueue()
Definition: eventq.hh:83
EventQueue::asyncInsert
void asyncInsert(Event *event)
Function for adding events to the async queue.
Definition: eventq.cc:427
Event::instanceString
const std::string instanceString() const
Return the instance number as a string.
Definition: eventq.cc:394
Event::priority
Priority priority() const
Get the event priority.
Definition: eventq.hh:510
EventQueue::insert
void insert(Event *event)
Insert / remove event from the queue.
Definition: eventq.cc:111
core.hh
name
const std::string & name()
Definition: trace.cc:50
SERIALIZE_SCALAR
#define SERIALIZE_SCALAR(scalar)
Definition: serialize.hh:790
DPRINTF_UNCONDITIONAL
#define DPRINTF_UNCONDITIONAL(x,...)
Definition: trace.hh:240
std
Overload hash function for BasicBlockRange type.
Definition: vec_reg.hh:587
ArmISA::t
Bitfield< 5 > t
Definition: miscregs_types.hh:67
EventQueue::remove
void remove(Event *event)
Definition: eventq.cc:165
Event::removeItem
static Event * removeItem(Event *event, Event *last)
Definition: eventq.cc:134
logging.hh
simQuantum
Tick simQuantum
Simulation Quantum for multiple eventq simulation.
Definition: eventq.cc:47
CheckpointOut
std::ostream CheckpointOut
Definition: serialize.hh:63
EventBase::Squashed
static const FlagsType Squashed
Definition: eventq.hh:99
trace.hh
EventQueue
Queue of events sorted in time order.
Definition: eventq.hh:617
EventQueue::EventQueue
EventQueue(const EventQueue &)
ArmISA::s
Bitfield< 4 > s
Definition: miscregs_types.hh:556
numMainEventQueues
uint32_t numMainEventQueues
Current number of allocated main event queues.
Definition: eventq.cc:55
CheckpointIn
Definition: serialize.hh:67
Event::name
virtual const std::string name() const
Definition: eventq.cc:83
csprintf
std::string csprintf(const char *format, const Args &...args)
Definition: cprintf.hh:158
_curEventQueue
__thread EventQueue * _curEventQueue
The current event queue for the running thread.
Definition: eventq.cc:57
Event::~Event
virtual ~Event()
Definition: eventq.cc:76
Event::instanceCounter
static Counter instanceCounter
Global counter to generate unique IDs for Event instances.
Definition: eventq.hh:272
Event::serialize
void serialize(CheckpointOut &cp) const override
Serialize an object.
Definition: eventq.cc:238
panic
#define panic(...)
This implements a cprintf based panic() function.
Definition: logging.hh:171
curTick
Tick curTick()
The current simulated tick.
Definition: core.hh:45
eventq.hh

Generated on Wed Sep 30 2020 14:02:14 for gem5 by doxygen 1.8.17