1 /* Copyright (c) 2015 Regents of the University of California
3 * Author: Brian Demsky <bdemsky@uci.edu>
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License
7 * version 2 as published by the Free Software Foundation.
10 #include "mcschedule.h"
11 #include "mcexecution.h"
13 WaitPair::WaitPair(ExecPoint *stoppoint, ExecPoint *waitpoint) :
14 stop_point(stoppoint),
15 wait_point(waitpoint) {
18 WaitPair::~WaitPair() {
21 ExecPoint * WaitPair::getStop() {
25 ExecPoint * WaitPair::getWait() {
29 MCScheduler::MCScheduler(MCExecution *e) :
32 waitset(new ModelVector<ModelVector<WaitPair *> *>()),
33 waitsetindex((unsigned int *)model_calloc(sizeof(unsigned int)*waitsetlen, 1)),
37 storesetindex=(unsigned int *)model_calloc(sizeof(unsigned int)*waitsetlen, 1);
38 storeset=new ModelVector<ModelVector<WaitPair *> *>();
42 MCScheduler::~MCScheduler() {
45 void MCScheduler::setNewFlag() {
49 void MCScheduler::addWaitPair(EPRecord *stoprec, EPRecord *waitrec) {
50 ExecPoint *stoppoint=stoprec->getEP();
51 ExecPoint *waitpoint=waitrec->getEP();
53 uint tid=id_to_int(stoppoint->get_tid());
54 if (waitset->size()<=tid) {
55 uint oldsize=waitset->size();
56 waitset->resize(tid+1);
57 for(uint i=oldsize;i<=tid;i++) {
58 (*waitset)[i]=new ModelVector<WaitPair *>();
61 storeset->resize(tid+1);
62 for(uint i=oldsize;i<=tid;i++) {
63 (*storeset)[i]=new ModelVector<WaitPair *>();
67 if (tid>=waitsetlen) {
68 waitsetindex=(uint *) model_realloc(waitsetindex, sizeof(uint)*(tid << 1));
69 for(uint i=waitsetlen;i<(tid<<1);i++)
72 storesetindex=(uint *) model_realloc(storesetindex, sizeof(uint)*(tid << 1));
73 for(uint i=waitsetlen;i<(tid<<1);i++)
79 if (stoprec->getType()==STORE)
80 (*storeset)[tid]->push_back(new WaitPair(stoppoint, waitpoint));
82 (*waitset)[tid]->push_back(new WaitPair(stoppoint, waitpoint));
84 (*waitset)[tid]->push_back(new WaitPair(stoppoint, waitpoint));
88 void MCScheduler::reset() {
89 for(unsigned int i=0;i<waitset->size();i++) {
90 ModelVector<WaitPair*> * v=(*waitset)[i];
91 for(unsigned int j=0;j<v->size();j++) {
97 for(unsigned int i=0;i<waitsetlen;i++)
100 for(unsigned int i=0;i<storeset->size();i++) {
101 ModelVector<WaitPair*> * v=(*storeset)[i];
102 for(unsigned int j=0;j<v->size();j++) {
103 WaitPair *wp=(*v)[j];
108 for(unsigned int i=0;i<waitsetlen;i++)
116 void MCScheduler::check_preempt() {
117 Thread *t=execution->get_current_thread();
120 //start at the next thread
121 unsigned int tid=id_to_int(t->get_id());
122 bool storebuffer=true;
123 for(unsigned int i=0;i<(2*execution->get_num_threads());i++) {
125 //Don't try to do a store from an empty store buffer
126 if (!execution->isEmptyStoreBuffer(int_to_id(tid))&&
127 check_store_buffer(tid)) {
128 execution->doStore(int_to_id(tid));
131 tid=(tid+1)%execution->get_num_threads();
134 //don't try to schedule finished threads
135 if (!execution->get_thread(int_to_id(tid))->is_complete() &&
143 //start at the next thread
144 unsigned int tid=(id_to_int(t->get_id())+1)%execution->get_num_threads();
146 for(unsigned int i=0;i<execution->get_num_threads();i++,tid=(tid+1)%execution->get_num_threads()) {
147 //don't try to schedule finished threads
148 if (execution->get_thread(int_to_id(tid))->is_complete())
150 if (check_thread(tid)) {
156 Thread *next_thread=execution->get_thread(int_to_id(tid));
157 if (next_thread->is_complete())
160 swap_threads(t,next_thread);
164 bool MCScheduler::check_store_buffer(unsigned int tid) {
165 ExecPoint *current=execution->getStoreBuffer(tid)->getEP();
166 return checkSet(tid, storeset, storesetindex, current);
170 bool MCScheduler::check_thread(unsigned int tid) {
171 ExecPoint *current=execution->get_execpoint(tid);
172 return checkSet(tid, waitset, waitsetindex, current);
176 bool MCScheduler::checkSet(unsigned int tid, ModelVector<ModelVector<WaitPair* > * > *set, unsigned int *setindex, ExecPoint *current) {
177 if (tid >= set->size())
179 ModelVector<WaitPair *> * wps=&(*((*set)[tid]));
182 for(;setindex[tid]<wps->size();setindex[tid]++) {
183 WaitPair *nextwp=(*wps)[setindex[tid]];
184 ExecPoint *stoppoint=nextwp->getStop();
185 CompareResult compare=stoppoint->compare(current);
186 if (compare==CR_EQUALS) {
188 ExecPoint *waitpoint=nextwp->getWait();
189 thread_id_t waittid=waitpoint->get_tid();
190 ExecPoint *waitthread=execution->get_execpoint(waittid);
191 CompareResult comparewt=waitthread->compare(waitpoint);
192 //we've resolved this wait, keep going
193 if (comparewt==CR_BEFORE||comparewt==CR_INCOMPARABLE) {
195 EPRecord *waitrec=execution->getRecord(waitpoint);
196 if (waitrec->getType()==STORE) {
197 EPValue *first_store=execution->getStoreBuffer(waittid);
198 if (first_store==NULL)
200 ExecPoint *storebuffer_ep=first_store->getEP();
201 CompareResult sb_comparewt=storebuffer_ep->compare(waitpoint);
202 if (sb_comparewt==CR_BEFORE||sb_comparewt==CR_INCOMPARABLE)
204 //need to wait to commit store out of buffer
213 //wait for store buffer to empty
214 if (!execution->isEmptyStoreBuffer(waittid)) {
218 //don't wait on a completed thread if store buffer is empty
219 if (execution->get_thread(id_to_int(waittid))->is_complete())
221 //Need to wait for another thread to take a step
223 } else if (compare==CR_BEFORE) {
224 //we haven't reached the context switch point
228 //oops..missed the point...
229 //this means we are past the point of our model's validity...
236 /** Swap context from thread from to thread to. If a thread is NULL,
237 * then we switch to the system context. */
239 void MCScheduler::swap_threads(Thread * from, Thread *to) {
240 ucontext_t * fromcontext=(from==NULL) ? get_system_context() : from->get_context();
241 ucontext_t * tocontext=(to==NULL) ? get_system_context() : to->get_context();
242 execution->set_current_thread(to);
243 model_swapcontext(fromcontext, tocontext);