mcschedule.cc

   1 /*      Copyright (c) 2015 Regents of the University of California
   2  *
   3  *      Author: Brian Demsky <bdemsky@uci.edu>
   4  *
   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.
   8  */
   9
  10 #include "mcschedule.h"
  11 #include "mcexecution.h"
  12
  13 WaitPair::WaitPair(ExecPoint *stoppoint, ExecPoint *waitpoint) :
  14         stop_point(stoppoint),
  15         wait_point(waitpoint) {
  16 }
  17
  18 WaitPair::~WaitPair() {
  19 }
  20
  21 ExecPoint * WaitPair::getStop() {
  22         return stop_point;
  23 }
  24
  25 ExecPoint * WaitPair::getWait() {
  26         return wait_point;
  27 }
  28
  29 MCScheduler::MCScheduler(MCExecution *e) :
  30         waitsetlen(4),
  31         execution(e),
  32         waitset(new ModelVector<ModelVector<WaitPair *> *>()),
  33         waitsetindex((unsigned int *)model_calloc(sizeof(unsigned int)*waitsetlen, 1)),
  34         newbehavior(false)
  35 {
  36 #ifdef TSO
  37         storesetindex=(unsigned int *)model_calloc(sizeof(unsigned int)*waitsetlen, 1);
  38         storeset=new ModelVector<ModelVector<WaitPair *> *>();
  39 #endif
  40 }
  41
  42 MCScheduler::~MCScheduler() {
  43 }
  44
  45 void MCScheduler::setNewFlag() {
  46         newbehavior=true;
  47 }
  48
  49 void MCScheduler::addWaitPair(EPRecord *stoprec, EPRecord *waitrec) {
  50         ExecPoint *stoppoint=stoprec->getEP();
  51         ExecPoint *waitpoint=waitrec->getEP();
  52
  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 *>();
  59                 }
  60 #ifdef TSO
  61                 storeset->resize(tid+1);
  62                 for(uint i=oldsize;i<=tid;i++) {
  63                         (*storeset)[i]=new ModelVector<WaitPair *>();
  64                 }
  65 #endif
  66         }
  67         if (tid>=waitsetlen) {
  68                 waitsetindex=(uint *) model_realloc(waitsetindex, sizeof(uint)*(tid << 1));
  69                 for(uint i=waitsetlen;i<(tid<<1);i++)
  70                         waitsetindex[i]=0;
  71 #ifdef TSO
  72                 storesetindex=(uint *) model_realloc(storesetindex, sizeof(uint)*(tid << 1));
  73                 for(uint i=waitsetlen;i<(tid<<1);i++)
  74                         storesetindex[i]=0;
  75 #endif
  76                 waitsetlen=tid<<1;
  77         }
  78 #ifdef TSO
  79         if (stoprec->getType()==STORE)
  80                 (*storeset)[tid]->push_back(new WaitPair(stoppoint, waitpoint));
  81         else
  82                 (*waitset)[tid]->push_back(new WaitPair(stoppoint, waitpoint));
  83 #else
  84         (*waitset)[tid]->push_back(new WaitPair(stoppoint, waitpoint));
  85 #endif
  86 }
  87
  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++) {
  92                         WaitPair *wp=(*v)[j];
  93                         delete wp;
  94                 }
  95                 v->clear();
  96         }
  97         for(unsigned int i=0;i<waitsetlen;i++)
  98                 waitsetindex[i]=0;
  99 #ifdef TSO
 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];
 104                         delete wp;
 105                 }
 106                 v->clear();
 107         }
 108         for(unsigned int i=0;i<waitsetlen;i++)
 109                 storesetindex[i]=0;
 110 #endif
 111         newbehavior=false;
 112 }
 113
 114
 115
 116 void MCScheduler::check_preempt() {
 117         Thread *t=execution->get_current_thread();
 118 #ifdef TSO
 119 restart_search:
 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++) {
 124                 if (storebuffer) {
 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));
 129                                 goto restart_search;
 130                         }
 131                         tid=(tid+1)%execution->get_num_threads();
 132                         storebuffer=false;
 133                 } else {
 134                         //don't try to schedule finished threads
 135                         if (!execution->get_thread(int_to_id(tid))->is_complete() &&
 136                                         check_thread(tid)) {
 137                                 break;
 138                         }
 139                         storebuffer=true;
 140                 }
 141         }
 142 #else
 143         //start at the next thread
 144         unsigned int tid=(id_to_int(t->get_id())+1)%execution->get_num_threads();
 145
 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())
 149                         continue;
 150                 if (check_thread(tid)) {
 151                         break;
 152                 }
 153         }
 154 #endif
 155
 156         Thread *next_thread=execution->get_thread(int_to_id(tid));
 157         if (next_thread->is_complete())
 158                 next_thread=NULL;
 159
 160         swap_threads(t,next_thread);
 161 }
 162
 163 #ifdef TSO
 164 bool MCScheduler::check_store_buffer(unsigned int tid) {
 165         ExecPoint *current=execution->getStoreBuffer(tid)->getEP();
 166         return checkSet(tid, storeset, storesetindex, current);
 167 }
 168 #endif
 169
 170 bool MCScheduler::check_thread(unsigned int tid) {
 171         ExecPoint *current=execution->get_execpoint(tid);
 172         return checkSet(tid, waitset, waitsetindex, current);
 173 }
 174
 175
 176 bool MCScheduler::checkSet(unsigned int tid, ModelVector<ModelVector<WaitPair* > * > *set, unsigned int *setindex, ExecPoint *current) {
 177         if (tid >= set->size())
 178                 return true;
 179         ModelVector<WaitPair *> * wps=&(*((*set)[tid]));
 180
 181         if (!newbehavior) {
 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) {
 187                                 //hit stop point
 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) {
 194 #ifdef TSO
 195                                         EPRecord *waitrec=execution->getRecord(waitpoint);
 196                                         if (waitrec->getType()==STORE) {
 197                                                 EPValue *first_store=execution->getStoreBuffer(waittid);
 198                                                 if (first_store==NULL)
 199                                                         continue;
 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)
 203                                                         continue;
 204                                                 //need to wait to commit store out of buffer
 205                                                 return false;
 206                                         } else
 207                                                 continue;
 208 #else
 209                                         continue;
 210 #endif
 211                                 }
 212 #ifdef TSO
 213                                 //wait for store buffer to empty
 214                                 if (!execution->isEmptyStoreBuffer(waittid)) {
 215                                         return false;
 216                                 }
 217 #endif
 218                                 //don't wait on a completed thread if store buffer is empty
 219                                 if (execution->get_thread(id_to_int(waittid))->is_complete())
 220                                         continue;
 221                                 //Need to wait for another thread to take a step
 222                                 return false;
 223                         } else if (compare==CR_BEFORE) {
 224                                 //we haven't reached the context switch point
 225                                 return true;
 226                         } else {
 227                                 return true;
 228                                 //oops..missed the point...
 229                                 //this means we are past the point of our model's validity...
 230                         }
 231                 }
 232         }
 233         return true;
 234 }
 235
 236 /** Swap context from thread from to thread to.  If a thread is NULL,
 237  *  then we switch to the system context. */
 238
 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);
 244 }