Implement timedwait
authorweiyu <weiyuluo1232@gmail.com>
Fri, 11 Sep 2020 23:00:23 +0000 (16:00 -0700)
committerweiyu <weiyuluo1232@gmail.com>
Fri, 11 Sep 2020 23:00:23 +0000 (16:00 -0700)
action.cc
action.h
execution.cc
execution.h
fuzzer.cc
fuzzer.h
model.cc
pthread.cc

index 4cdca0d..d8ce567 100644 (file)
--- a/action.cc
+++ b/action.cc
@@ -251,6 +251,10 @@ bool ModelAction::is_wait() const {
        return type == ATOMIC_WAIT || type == ATOMIC_TIMEDWAIT;
 }
 
+bool ModelAction::is_timedwait() const {
+       return type == ATOMIC_TIMEDWAIT;
+}
+
 bool ModelAction::is_notify() const {
        return type == ATOMIC_NOTIFY_ONE || type == ATOMIC_NOTIFY_ALL;
 }
index 6dea9bc..5357fe4 100644 (file)
--- a/action.h
+++ b/action.h
@@ -140,6 +140,7 @@ public:
        bool is_trylock() const;
        bool is_unlock() const;
        bool is_wait() const;
+       bool is_timedwait() const;
        bool is_create() const;
        bool is_notify() const;
        bool is_notify_one() const;
index 4b8461e..4953718 100644 (file)
@@ -2,6 +2,7 @@
 #include <algorithm>
 #include <new>
 #include <stdarg.h>
+#include <errno.h>
 
 #include "model.h"
 #include "execution.h"
@@ -247,10 +248,8 @@ void ModelExecution::restore_last_seq_num()
  * @param thread The thread that we might wake up
  * @return True, if we should wake up the sleeping thread; false otherwise
  */
-bool ModelExecution::should_wake_up(const Thread *thread) const
+bool ModelExecution::should_wake_up(const ModelAction * asleep) const
 {
-       const ModelAction *asleep = thread->get_pending();
-
        /* The sleep is literally sleeping */
        switch (asleep->get_type()) {
                case THREAD_SLEEP:
@@ -275,14 +274,16 @@ void ModelExecution::wake_up_sleeping_actions()
                thread_id_t tid = int_to_id(i);
                if (scheduler->is_sleep_set(tid)) {
                        Thread *thr = get_thread(tid);
-                       if (should_wake_up(thr)) {
+                       ModelAction * pending = thr->get_pending();
+                       if (should_wake_up(pending)) {
                                /* Remove this thread from sleep set */
                                scheduler->remove_sleep(thr);
-                               ModelAction * pending = thr->get_pending();
+
                                if (pending->is_sleep()) {
                                        thr->set_wakeup_state(true);
                                } else if (pending->is_wait()) {
                                        thr->set_wakeup_state(true);
+                                       /* Remove this thread from list of waiters */
                                        simple_action_list_t *waiters = get_safe_ptr_action(&condvar_waiters_map, pending->get_location());
                                        for (sllnode<ModelAction *> * rit = waiters->begin();rit != NULL;rit=rit->getNext()) {
                                                if (rit->getVal()->get_tid() == tid) {
@@ -290,6 +291,10 @@ void ModelExecution::wake_up_sleeping_actions()
                                                        break;
                                                }
                                        }
+
+                                       /* Set ETIMEDOUT error */
+                                       if (pending->is_timedwait())
+                                               thr->set_return_value(ETIMEDOUT);
                                }
                        }
                }
@@ -507,24 +512,38 @@ bool ModelExecution::process_mutex(ModelAction *curr)
                waiters->push_back(curr);
                curr_thrd->set_pending(curr);   // Forbid this thread to stash a new action
 
-               if (fuzzer->waitShouldFail(curr))
-                       scheduler->add_sleep(curr_thrd);        // Place this thread into THREAD_SLEEP_SET
+               if (fuzzer->waitShouldFail(curr))               // If wait should fail spuriously,
+                       scheduler->add_sleep(curr_thrd);        // place this thread into THREAD_SLEEP_SET
                else
                        scheduler->sleep(curr_thrd);
 
                break;
        }
-       case ATOMIC_TIMEDWAIT:
-       case ATOMIC_UNLOCK: {
-               //TODO: FIX WAIT SITUATION...WAITS CAN SPURIOUSLY
-               //FAIL...TIMED WAITS SHOULD PROBABLY JUST BE THE SAME
-               //AS NORMAL WAITS...THINK ABOUT PROBABILITIES
-               //THOUGH....AS IN TIMED WAIT MUST FAIL TO GUARANTEE
-               //PROGRESS...NORMAL WAIT MAY FAIL...SO NEED NORMAL
-               //WAIT TO WORK CORRECTLY IN THE CASE IT SPURIOUSLY
-               //FAILS AND IN THE CASE IT DOESN'T...  TIMED WAITS
-               //MUST EVENMTUALLY RELEASE...
+       case ATOMIC_TIMEDWAIT: {
+               Thread *curr_thrd = get_thread(curr);
+               if (!fuzzer->randomizeWaitTime(curr)) {
+                       curr_thrd->set_return_value(ETIMEDOUT);
+                       return false;
+               }
 
+               /* wake up the other threads */
+               for (unsigned int i = 0;i < get_num_threads();i++) {
+                       Thread *t = get_thread(int_to_id(i));
+                       if (t->waiting_on() == curr_thrd && t->get_pending()->is_lock())
+                               scheduler->wake(t);
+               }
+
+               /* unlock the lock - after checking who was waiting on it */
+               state->locked = NULL;
+
+               /* disable this thread */
+               simple_action_list_t * waiters = get_safe_ptr_action(&condvar_waiters_map, curr->get_location());
+               waiters->push_back(curr);
+               curr_thrd->set_pending(curr);   // Forbid this thread to stash a new action
+               scheduler->add_sleep(curr_thrd);
+               break;
+       }
+       case ATOMIC_UNLOCK: {
                // TODO: lock count for recursive mutexes
                /* wake up the other threads */
                Thread *curr_thrd = get_thread(curr);
index 51062ea..82d629c 100644 (file)
@@ -99,7 +99,7 @@ public:
        SNAPSHOTALLOC
 private:
        int get_execution_number() const;
-       bool should_wake_up(const Thread *thread) const;
+       bool should_wake_up(const ModelAction * asleep) const;
        void wake_up_sleeping_actions();
        modelclock_t get_next_seq_num();
        bool next_execution();
index f3be1d3..7e488ce 100644 (file)
--- a/fuzzer.cc
+++ b/fuzzer.cc
@@ -58,10 +58,28 @@ bool Fuzzer::waitShouldFail(ModelAction * wait)
 
 bool Fuzzer::waitShouldWakeUp(const ModelAction * wait)
 {
-       uint64_t time_to_expire = wait->get_time();
        struct timespec currtime;
        clock_gettime(CLOCK_MONOTONIC, &currtime);
        uint64_t lcurrtime = currtime.tv_sec * 1000000000 + currtime.tv_nsec;
 
-       return (time_to_expire < lcurrtime);
+       return (wait->get_time() < lcurrtime);
+}
+
+bool Fuzzer::randomizeWaitTime(ModelAction * timed_wait)
+{
+       uint64_t abstime = timed_wait->get_time();
+       struct timespec currtime;
+       clock_gettime(CLOCK_MONOTONIC, &currtime);
+       uint64_t lcurrtime = currtime.tv_sec * 1000000000 + currtime.tv_nsec;
+       if (abstime <= lcurrtime)
+               return false;
+
+       // Shorten wait time
+       if ((random() & 1) == 0) {
+               uint64_t tmp = abstime - lcurrtime;
+               uint64_t time_to_expire = random() % tmp + lcurrtime;
+               timed_wait->set_time(time_to_expire);
+       }
+
+       return true;
 }
index e3cd445..65210e0 100644 (file)
--- a/fuzzer.h
+++ b/fuzzer.h
@@ -17,6 +17,7 @@ public:
        bool shouldWake(const ModelAction *sleep);
        virtual bool waitShouldFail(ModelAction *wait);
        bool waitShouldWakeUp(const ModelAction *wait);
+       bool randomizeWaitTime(ModelAction * timed_wait);
        virtual void register_engine(ModelChecker * _model, ModelExecution * execution) {}
        SNAPSHOTALLOC
 private:
index 2aa31e9..4b2143d 100644 (file)
--- a/model.cc
+++ b/model.cc
@@ -385,7 +385,7 @@ Thread* ModelChecker::getNextThread(Thread *old)
                }
 
                ModelAction *act = thr->get_pending();
-               if (act && execution->is_enabled(tid)){
+               if (act && scheduler->is_enabled(tid)){
                        /* Don't schedule threads which should be disabled */
                        if (!execution->check_action_enabled(act)) {
                                scheduler->sleep(thr);
index 20999ae..fecca66 100644 (file)
@@ -174,7 +174,6 @@ int pthread_cond_wait(pthread_cond_t *p_cond, pthread_mutex_t *p_mutex) {
 int pthread_cond_timedwait(pthread_cond_t *p_cond,
                                                                                                         pthread_mutex_t *p_mutex, const struct timespec *abstime) {
        ModelExecution *execution = model->get_execution();
-
        if ( !execution->getCondMap()->contains(p_cond) )
                pthread_cond_init(p_cond, NULL);
        if ( !execution->getMutexMap()->contains(p_mutex) )
@@ -183,10 +182,14 @@ int pthread_cond_timedwait(pthread_cond_t *p_cond,
        cdsc::snapcondition_variable *v = execution->getCondMap()->get(p_cond);
        cdsc::snapmutex *m = execution->getMutexMap()->get(p_mutex);
 
-       model->switch_thread(new ModelAction(ATOMIC_TIMEDWAIT, std::memory_order_seq_cst, v, (uint64_t) m));
+       uint64_t time = abstime->tv_sec * 1000000000 + abstime->tv_nsec;
+       ModelAction * timed_wait = new ModelAction(ATOMIC_TIMEDWAIT, std::memory_order_seq_cst, v, (uint64_t) m);
+       timed_wait->set_time(time);
+       if (model->switch_thread(timed_wait) == ETIMEDOUT) {
+               //model_print("thread %u wait timedout\n", thread_current_id());
+               return ETIMEDOUT;
+       }
        m->lock();
-
-       // model_print("Timed_wait is called\n");
        return 0;
 }