gem5  v22.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 <mutex>
36 #include <string>
37 #include <unordered_map>
38 #include <vector>
39 
40 #include "base/logging.hh"
41 #include "base/trace.hh"
42 #include "cpu/smt.hh"
43 #include "debug/Checkpoint.hh"
44 
45 namespace gem5
46 {
47 
49 
50 //
51 // Main Event Queues
52 //
53 // Events on these queues are processed at the *beginning* of each
54 // cycle, before the pipeline simulation is performed.
55 //
56 uint32_t numMainEventQueues = 0;
58 __thread EventQueue *_curEventQueue = NULL;
59 bool inParallelMode = false;
60 
61 EventQueue *
63 {
64  while (numMainEventQueues <= index) {
66  mainEventQueue.push_back(
67  new EventQueue(csprintf("MainEventQueue-%d", index)));
68  }
69 
70  return mainEventQueue[index];
71 }
72 
73 #ifndef NDEBUG
75 #endif
76 
78 {
79  assert(!scheduled());
80  flags = 0;
81 }
82 
83 const std::string
84 Event::name() const
85 {
86  return csprintf("Event_%s", instanceString());
87 }
88 
89 
90 Event *
92 {
93  // Either way, event will be the top element in the 'in bin' list
94  // which is the pointer we need in order to look into the list, so
95  // we need to insert that into the bin list.
96  if (!curr || *event < *curr) {
97  // Insert the event before the current list since it is in the future.
98  event->nextBin = curr;
99  event->nextInBin = NULL;
100  } else {
101  // Since we're on the correct list, we need to point to the next list
102  event->nextBin = curr->nextBin; // curr->nextBin can now become stale
103 
104  // Insert event at the top of the stack
105  event->nextInBin = curr;
106  }
107 
108  return event;
109 }
110 
111 void
113 {
114  // Deal with the head case
115  if (!head || *event <= *head) {
117  return;
118  }
119 
120  // Figure out either which 'in bin' list we are on, or where a new list
121  // needs to be inserted
122  Event *prev = head;
123  Event *curr = head->nextBin;
124  while (curr && *curr < *event) {
125  prev = curr;
126  curr = curr->nextBin;
127  }
128 
129  // Note: this operation may render all nextBin pointers on the
130  // prev 'in bin' list stale (except for the top one)
131  prev->nextBin = Event::insertBefore(event, curr);
132 }
133 
134 Event *
136 {
137  Event *curr = top;
138  Event *next = top->nextInBin;
139 
140  // if we removed the top item, we need to handle things specially
141  // and just remove the top item, fixing up the next bin pointer of
142  // the new top item
143  if (event == top) {
144  if (!next)
145  return top->nextBin;
146  next->nextBin = top->nextBin;
147  return next;
148  }
149 
150  // Since we already checked the current element, we're going to
151  // keep checking event against the next element.
152  while (event != next) {
153  if (!next)
154  panic("event not found!");
155 
156  curr = next;
157  next = next->nextInBin;
158  }
159 
160  // remove next from the 'in bin' list since it's what we're looking for
161  curr->nextInBin = next->nextInBin;
162  return top;
163 }
164 
165 void
167 {
168  if (head == NULL)
169  panic("event not found!");
170 
171  assert(event->queue == this);
172 
173  // deal with an event on the head's 'in bin' list (event has the same
174  // time as the head)
175  if (*head == *event) {
177  return;
178  }
179 
180  // Find the 'in bin' list that this event belongs on
181  Event *prev = head;
182  Event *curr = head->nextBin;
183  while (curr && *curr < *event) {
184  prev = curr;
185  curr = curr->nextBin;
186  }
187 
188  if (!curr || *curr != *event)
189  panic("event not found!");
190 
191  // curr points to the top item of the the correct 'in bin' list, when
192  // we remove an item, it returns the new top item (which may be
193  // unchanged)
194  prev->nextBin = Event::removeItem(event, curr);
195 }
196 
197 Event *
199 {
200  std::lock_guard<EventQueue> lock(*this);
201  Event *event = head;
202  Event *next = head->nextInBin;
203  event->flags.clear(Event::Scheduled);
204 
205  if (next) {
206  // update the next bin pointer since it could be stale
207  next->nextBin = head->nextBin;
208 
209  // pop the stack
210  head = next;
211  } else {
212  // this was the only element on the 'in bin' list, so get rid of
213  // the 'in bin' list and point to the next bin list
214  head = head->nextBin;
215  }
216 
217  // handle action
218  if (!event->squashed()) {
219  // forward current cycle to the time when this event occurs.
220  setCurTick(event->when());
221  if (debug::Event)
222  event->trace("executed");
223  event->process();
224  if (event->isExitEvent()) {
225  assert(!event->flags.isSet(Event::Managed) ||
226  !event->flags.isSet(Event::IsMainQueue)); // would be silly
227  return event;
228  }
229  } else {
230  event->flags.clear(Event::Squashed);
231  }
232 
233  event->release();
234 
235  return NULL;
236 }
237 
238 void
240 {
243  short _flags = flags;
244  SERIALIZE_SCALAR(_flags);
245 }
246 
247 void
249 {
250  assert(!scheduled());
251 
254 
255  FlagsType _flags;
256  UNSERIALIZE_SCALAR(_flags);
257 
258  // Old checkpoints had no concept of the Initialized flag
259  // so restoring from old checkpoints always fail.
260  // Events are initialized on construction but original code
261  // "flags = _flags" would just overwrite the initialization.
262  // So, read in the checkpoint flags, but then set the Initialized
263  // flag on top of it in order to avoid failures.
264  assert(initialized());
265  flags = _flags;
267 
268  // need to see if original event was in a scheduled, unsquashed
269  // state, but don't want to restore those flags in the current
270  // object itself (since they aren't immediately true)
271  if (flags.isSet(Scheduled) && !flags.isSet(Squashed)) {
273  } else {
274  DPRINTF(Checkpoint, "Event '%s' need to be scheduled @%d\n",
275  name(), _when);
276  }
277 }
278 
279 void
281 {
282  // It's safe to call insert() directly here since this method
283  // should only be called when restoring from a checkpoint (which
284  // happens before thread creation).
285  if (event->flags.isSet(Event::Scheduled))
286  insert(event);
287 }
288 void
290 {
291  cprintf("============================================================\n");
292  cprintf("EventQueue Dump (cycle %d)\n", curTick());
293  cprintf("------------------------------------------------------------\n");
294 
295  if (empty())
296  cprintf("<No Events>\n");
297  else {
298  Event *nextBin = head;
299  while (nextBin) {
300  Event *nextInBin = nextBin;
301  while (nextInBin) {
302  nextInBin->dump();
303  nextInBin = nextInBin->nextInBin;
304  }
305 
306  nextBin = nextBin->nextBin;
307  }
308  }
309 
310  cprintf("============================================================\n");
311 }
312 
313 bool
315 {
316  std::unordered_map<long, bool> map;
317 
318  Tick time = 0;
319  short priority = 0;
320 
321  Event *nextBin = head;
322  while (nextBin) {
323  Event *nextInBin = nextBin;
324  while (nextInBin) {
325  if (nextInBin->when() < time) {
326  cprintf("time goes backwards!");
327  nextInBin->dump();
328  return false;
329  } else if (nextInBin->when() == time &&
330  nextInBin->priority() < priority) {
331  cprintf("priority inverted!");
332  nextInBin->dump();
333  return false;
334  }
335 
336  if (map[reinterpret_cast<long>(nextInBin)]) {
337  cprintf("Node already seen");
338  nextInBin->dump();
339  return false;
340  }
341  map[reinterpret_cast<long>(nextInBin)] = true;
342 
343  time = nextInBin->when();
344  priority = nextInBin->priority();
345 
346  nextInBin = nextInBin->nextInBin;
347  }
348 
349  nextBin = nextBin->nextBin;
350  }
351 
352  return true;
353 }
354 
355 Event*
357 {
358  Event* t = head;
359  head = s;
360  return t;
361 }
362 
363 void
365 {
366  for (uint32_t i = 0; i < numMainEventQueues; ++i) {
367  mainEventQueue[i]->dump();
368  }
369 }
370 
371 
372 const char *
374 {
375  return "generic";
376 }
377 
378 void
379 Event::trace(const char *action)
380 {
381  // This is just a default implementation for derived classes where
382  // it's not worth doing anything special. If you want to put a
383  // more informative message in the trace, override this method on
384  // the particular subclass where you have the information that
385  // needs to be printed.
386  DPRINTF(Event, "%s %s %s @ %d\n",
387  description(), instanceString(), action, when());
388 }
389 
390 const std::string
392 {
393 #ifndef NDEBUG
394  return csprintf("%d", instance);
395 #else
396  return csprintf("%#x", (uintptr_t)this);
397 #endif
398 }
399 
400 void
401 Event::dump() const
402 {
403  cprintf("Event %s (%s)\n", name(), description());
404  cprintf("Flags: %#x\n", flags);
405 #ifdef EVENTQ_DEBUG
406  cprintf("Created: %d\n", whenCreated);
407 #endif
408  if (scheduled()) {
409 #ifdef EVENTQ_DEBUG
410  cprintf("Scheduled at %d\n", whenScheduled);
411 #endif
412  cprintf("Scheduled for %d, priority %d\n", when(), _priority);
413  } else {
414  cprintf("Not Scheduled\n");
415  }
416 }
417 
418 EventQueue::EventQueue(const std::string &n)
419  : objName(n), head(NULL), _curTick(0)
420 {
421 }
422 
423 void
425 {
427  async_queue.push_back(event);
429 }
430 
431 void
433 {
434  assert(this == curEventQueue());
436 
437  while (!async_queue.empty()) {
438  insert(async_queue.front());
439  async_queue.pop_front();
440  }
441 
443 }
444 
445 } // namespace gem5
#define DPRINTF(x,...)
Definition: trace.hh:186
static const FlagsType Squashed
Definition: eventq.hh:104
static const FlagsType IsMainQueue
Definition: eventq.hh:115
static const FlagsType Initialized
Definition: eventq.hh:116
static const FlagsType Managed
Definition: eventq.hh:106
static const FlagsType Scheduled
Definition: eventq.hh:105
unsigned short FlagsType
Definition: eventq.hh:99
Queue of events sorted in time order.
Definition: eventq.hh:623
Event * serviceOne()
Definition: eventq.cc:198
EventQueue(const EventQueue &)
bool debugVerify() const
Definition: eventq.cc:314
void handleAsyncInsertions()
Function for moving events from the async_queue to the main queue.
Definition: eventq.cc:432
std::list< Event * > async_queue
List of events added by other threads to this event queue.
Definition: eventq.hh:635
void setCurTick(Tick newVal)
Definition: eventq.hh:844
void asyncInsert(Event *event)
Function for adding events to the async queue.
Definition: eventq.cc:424
Event * head
Definition: eventq.hh:628
void lock()
Provide an interface for locking/unlocking the event queue.
Definition: eventq.hh:954
void checkpointReschedule(Event *event)
Reschedule an event after a checkpoint.
Definition: eventq.cc:280
friend void curEventQueue(EventQueue *)
Definition: eventq.hh:979
void insert(Event *event)
Insert / remove event from the queue.
Definition: eventq.cc:112
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:356
void remove(Event *event)
Definition: eventq.cc:166
UncontendedMutex async_queue_mutex
Mutex to protect async queue.
Definition: eventq.hh:632
Priority _priority
event priority
Definition: eventq.hh:272
static Event * removeItem(Event *event, Event *last)
Definition: eventq.cc:135
Flags flags
Definition: eventq.hh:273
Event * nextBin
Definition: eventq.hh:265
static Event * insertBefore(Event *event, Event *curr)
Definition: eventq.cc:91
void unserialize(CheckpointIn &cp) override
Unserialize an object.
Definition: eventq.cc:248
static Counter instanceCounter
Global counter to generate unique IDs for Event instances.
Definition: eventq.hh:277
Counter instance
This event's unique ID.
Definition: eventq.hh:283
bool initialized() const
Definition: eventq.hh:308
Tick _when
timestamp when event should be processed
Definition: eventq.hh:271
Event * nextInBin
Definition: eventq.hh:266
const std::string instanceString() const
Return the instance number as a string.
Definition: eventq.cc:391
void serialize(CheckpointOut &cp) const override
Serialize an object.
Definition: eventq.cc:239
STL vector class.
Definition: stl.hh:37
Definition: test.h:63
void dump() const
This is a debugging function which will print everything on the event queue.
Definition: eventq.cc:289
virtual void trace(const char *action)
This function isn't really useful if TRACING_ON is not defined.
Definition: eventq.cc:379
virtual ~Event()
Definition: eventq.cc:77
virtual const std::string name() const
Definition: eventq.cc:84
bool scheduled() const
Determine if the current event is scheduled.
Definition: eventq.hh:465
void dump() const
Dump the current event data.
Definition: eventq.cc:401
Priority priority() const
Get the event priority.
Definition: eventq.hh:515
bool empty() const
Returns true if no events are queued.
Definition: eventq.hh:898
virtual const char * description() const
Return a C string describing the event.
Definition: eventq.cc:373
Tick when() const
Get the time that the event is scheduled.
Definition: eventq.hh:508
void set(Type mask)
Set all flag's bits matching the given mask.
Definition: flags.hh:116
bool isSet(Type mask) const
Verifies whether any bit matching the given mask is set.
Definition: flags.hh:83
void clear()
Clear all flag's bits.
Definition: flags.hh:102
#define panic(...)
This implements a cprintf based panic() function.
Definition: logging.hh:178
Bitfield< 31 > n
Definition: misc_types.hh:462
Bitfield< 7 > i
Definition: misc_types.hh:67
Bitfield< 10, 5 > event
Bitfield< 30, 0 > index
Bitfield< 1 > s
Definition: pagetable.hh:64
Bitfield< 51 > t
Definition: pagetable.hh:56
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Tick simQuantum
Simulation Quantum for multiple eventq simulation.
Definition: eventq.cc:48
void cprintf(const char *format, const Args &...args)
Definition: cprintf.hh:155
Tick curTick()
The universal simulation clock.
Definition: cur_tick.hh:46
std::ostream CheckpointOut
Definition: serialize.hh:66
__thread EventQueue * _curEventQueue
The current event queue for the running thread.
Definition: eventq.cc:58
void dumpMainQueue()
Definition: eventq.cc:364
int64_t Counter
Statistics counter type.
Definition: types.hh:53
uint64_t Tick
Tick count type.
Definition: types.hh:58
uint32_t numMainEventQueues
Current number of allocated main event queues.
Definition: eventq.cc:56
std::string csprintf(const char *format, const Args &...args)
Definition: cprintf.hh:161
bool inParallelMode
Current mode of execution: parallel / serial.
Definition: eventq.cc:59
EventQueue * getEventQueue(uint32_t index)
Function for returning eventq queue for the provided index.
Definition: eventq.cc:62
std::vector< EventQueue * > mainEventQueue
Array for main event queues.
Definition: eventq.cc:57
#define UNSERIALIZE_SCALAR(scalar)
Definition: serialize.hh:575
#define SERIALIZE_SCALAR(scalar)
Definition: serialize.hh:568
Defines SMT_MAX_THREADS.

Generated on Wed Dec 21 2022 10:22:39 for gem5 by doxygen 1.9.1