SHARE
TWEET

Chris M Thomasson

a guest Aug 5th, 2008 127 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "stdafx.h"
  2. #include "../../relacy/relacy_std.hpp"
  3. #include <cstdio>
  4. #include <list>
  5.  
  6.  
  7. namespace raii {
  8.   template<typename T>
  9.   class unguard {
  10.     T& m_guard;
  11.  
  12.   public:
  13.     unguard(T& guard)
  14.       : m_guard(guard) {
  15.       m_guard.unlock();
  16.     }
  17.  
  18.     ~unguard() {
  19.       m_guard.lock();
  20.     }
  21.   };
  22.  
  23.   template<typename T, typename Y>
  24.   class guard {
  25.     T& m_mtx;
  26.     Y& m_tid;
  27.  
  28.     friend class unguard<guard>;
  29.  
  30.   public:
  31.     guard(T& mtx, Y& tid)
  32.       : m_mtx(mtx), m_tid(tid) {
  33.       lock();
  34.     }
  35.  
  36.     ~guard() {
  37.       unlock();
  38.     }
  39.  
  40.     Y& get_tid() const {
  41.       return m_tid;
  42.     }
  43.  
  44.   private:
  45.     void lock() {
  46.       m_mtx.lock(m_tid);
  47.     }
  48.  
  49.     void unlock() {
  50.       m_mtx.unlock(m_tid);
  51.     }
  52.   };
  53. }
  54.  
  55.  
  56. namespace pthread {
  57.   namespace sys {
  58.     static void spin_wait() {
  59.       rl::backoff wait;
  60.       wait.yield($);
  61.     }
  62.  
  63.  
  64.     class spinlock {
  65.       std::atomic<class thread*> m_state;
  66.  
  67.     public:
  68.       void before() {
  69.         m_state($) = NULL;
  70.       }
  71.  
  72.       void after() {
  73.         RL_ASSERT(! m_state($).load(std::memory_order_relaxed));
  74.       }
  75.  
  76.     public:
  77.       typedef raii::guard<spinlock, class thread> guard;
  78.       typedef raii::unguard<guard> unguard;
  79.  
  80.     public:
  81.       void lock(thread& tid) {
  82.         class thread* cmp = NULL;
  83.         while (! m_state($).compare_swap(cmp, &tid, std::memory_order_acquire)) {
  84.           spin_wait();
  85.           cmp = NULL;
  86.         }
  87.       }
  88.  
  89.       void unlock(thread& tid) {
  90.         class thread* cmp = m_state($).swap(NULL, std::memory_order_release);
  91.         if (cmp != &tid) {
  92.           RL_ASSERT(cmp == &tid);
  93.         }
  94.       }
  95.     };
  96.  
  97.  
  98.     class thread {
  99.       unsigned const m_idx;
  100.       std::atomic<bool> m_signal;
  101.  
  102.     public:
  103.       thread(unsigned const idx)
  104.         : m_idx(idx) {
  105.         m_signal($) = false;
  106.       }
  107.  
  108.       void wait() {
  109.         // std::cout << "thread: " << this << " waiting\n";
  110.         while (! m_signal($).swap(false, std::memory_order_acquire)) {
  111.           spin_wait();
  112.         }
  113.         // std::cout << "thread: " << this << " signal consume\n";
  114.       }
  115.  
  116.       void signal() {
  117.         m_signal($).store(true, std::memory_order_release);
  118.         // std::cout << "thread: " << this << " signalled\n";
  119.       }
  120.     };
  121.  
  122.  
  123.     class waitset {
  124.       spinlock m_mtx;
  125.       rl::var<unsigned> m_count;
  126.       std::list<thread*> m_threads;
  127.  
  128.     public:
  129.       void before() {
  130.         m_count($) = 0;
  131.         m_mtx.before();
  132.       }
  133.  
  134.       void after() {
  135.         RL_ASSERT(! m_threads.size());
  136.         m_mtx.after();
  137.       }
  138.  
  139.     public:
  140.       void push(thread& tid) {
  141.         spinlock::guard lock(m_mtx, tid);
  142.         m_threads.push_back(&tid);
  143.       }
  144.  
  145.       void pop(thread& tid) {
  146.         spinlock::guard lock(m_mtx, tid);
  147.         m_threads.remove(&tid);  
  148.       }
  149.  
  150.       void wait(thread& tid) {
  151.         spinlock::guard lock(m_mtx, tid);
  152.         if (! m_count($)) {
  153.           m_threads.push_back(&tid);
  154.           {
  155.             spinlock::unguard unlock(lock);
  156.             tid.wait();
  157.           }
  158.           m_threads.remove(&tid);
  159.           return;
  160.         }
  161.         --m_count($);
  162.       }
  163.  
  164.       void signal(thread& tid, unsigned count = 0) {
  165.         spinlock::guard lock(m_mtx, tid);
  166.         m_count($) += count;
  167.         if (! m_threads.empty()) {
  168.           m_threads.front()->signal();
  169.         }
  170.       }
  171.  
  172.       void broadcast(thread& tid, unsigned count = 0) {
  173.         spinlock::guard lock(m_mtx, tid);
  174.         m_count($) += count;
  175.         std::list<thread*>::iterator i;
  176.         for (i = m_threads.begin(); i != m_threads.end(); ++i) {
  177.           (*i)->signal();
  178.         }
  179.       }
  180.     };
  181.   } // namespace sys
  182.  
  183.  
  184.   class event {
  185.     std::atomic<bool> m_state;
  186.     sys::waitset m_wset;
  187.  
  188.   public:
  189.     void before() {
  190.       m_state($) = false;
  191.       m_wset.before();
  192.     }
  193.  
  194.     void after() {
  195.       m_wset.after();
  196.     }
  197.  
  198.   public:
  199.     void set(sys::thread& tid) {
  200.       if (! m_state($).swap(true, std::memory_order_seq_cst)) {
  201.         m_wset.signal(tid, 1);
  202.       }
  203.     }
  204.  
  205.     void wait(sys::thread& tid) {
  206.       bool cmp = true;
  207.       while (! m_state($).compare_swap(cmp, false, std::memory_order_acquire)) {
  208.         m_wset.wait(tid);
  209.         cmp = true;
  210.       }
  211.     }
  212.   };
  213.  
  214.  
  215.   class mutex {
  216.     enum constant {
  217.       UNLOCKED = 0,
  218.       LOCKED = 1,
  219.       CONTENTION = 2
  220.     };
  221.  
  222.     std::atomic<int> m_state;
  223.     event m_event;
  224.  
  225.   public:
  226.     void before() {
  227.       m_state($) = UNLOCKED;
  228.       m_event.before();
  229.     }
  230.  
  231.     void after() {
  232.       m_event.after();
  233.       RL_ASSERT(m_state($).load(std::memory_order_relaxed) == UNLOCKED);
  234.     }
  235.  
  236.   public:
  237.     typedef raii::guard<mutex, sys::thread> guard;
  238.     typedef raii::unguard<guard> unguard;
  239.  
  240.   public:
  241.     void lock(sys::thread& tid) {
  242.       if (m_state($).swap(LOCKED, std::memory_order_acquire)) {
  243.         while (m_state($).swap(CONTENTION, std::memory_order_acquire)) {
  244.           m_event.wait(tid);
  245.         }
  246.       }
  247.     }
  248.  
  249.     void unlock(sys::thread& tid) {
  250.       if (m_state($).swap(UNLOCKED, std::memory_order_release) == CONTENTION) {
  251.         m_event.set(tid);
  252.       }
  253.     }
  254.   };
  255.  
  256.  
  257.   class condvar {
  258.     sys::waitset m_wset;
  259.     std::atomic<unsigned> m_state;
  260.  
  261.   public:
  262.     void before() {
  263.       m_state($) = 0;
  264.       m_wset.before();
  265.     }
  266.  
  267.     void after() {
  268.       RL_ASSERT(! m_state($).load(std::memory_order_relaxed));
  269.       m_wset.after();
  270.     }
  271.  
  272.   public:
  273.     void wait(mutex::guard& lock) {
  274.       sys::thread& tid = lock.get_tid();
  275.       m_state($).fetch_add(1, std::memory_order_relaxed);
  276.       m_wset.push(tid);
  277.       mutex::unguard unlock(lock);
  278.       tid.wait();
  279.       m_wset.pop(tid);      
  280.     }
  281.  
  282.     void signal(sys::thread& tid) {
  283.       unsigned cmp = m_state($).load(std::memory_order_relaxed);
  284.       do {
  285.         if (! cmp) { return; }
  286.       } while(! m_state($).compare_swap(cmp, cmp - 1, std::memory_order_relaxed));
  287.       m_wset.signal(tid);
  288.     }
  289.  
  290.     void broadcast(sys::thread& tid) {
  291.       unsigned cmp = m_state($).load(std::memory_order_relaxed);
  292.       if (cmp) {
  293.         if (m_state($).swap(0, std::memory_order_relaxed)) {
  294.           m_wset.broadcast(tid);
  295.         }
  296.       }
  297.     }
  298.   };
  299. } // namespace pthread
  300.  
  301.  
  302.  
  303.  
  304. #define CONSUMER_COUNT 2
  305.  
  306. struct condvar_test : rl::test_suite<condvar_test, CONSUMER_COUNT + 1> {
  307.  
  308.   pthread::mutex m_mtx;
  309.   pthread::condvar m_cond;
  310.   rl::var<bool> m_signal;
  311.   rl::var<bool> m_finish;
  312.  
  313.  
  314.   void before() {
  315.     m_mtx.before();
  316.     m_cond.before();
  317.     m_signal($) = false;
  318.     m_finish($) = false;
  319.   }
  320.  
  321.  
  322.   void after() {
  323.     RL_ASSERT(! m_signal($));
  324.     RL_ASSERT(! m_finish($));
  325.     m_cond.after();
  326.     m_mtx.after();
  327.   }
  328.  
  329.  
  330.   void producer(pthread::sys::thread& tid) {
  331.     unsigned count = 0;
  332.     // std::cout << "producer " << &tid << "\n";
  333.     do {
  334.       {
  335.         pthread::mutex::guard lock(m_mtx, tid);
  336.         m_signal($) = true;
  337.       }
  338.       m_cond.signal(tid);
  339.       pthread::mutex::guard lock(m_mtx, tid);
  340.       while (! m_finish($)) {
  341.         m_cond.wait(lock);
  342.       }
  343.       m_finish($) = false;
  344.       RL_ASSERT(! m_signal($));
  345.       ++count;
  346.     } while (count < CONSUMER_COUNT);
  347.   }
  348.  
  349.  
  350.   void consumers(pthread::sys::thread& tid) {
  351.     // std::cout << "consumer " << &tid << "\n";
  352.     {
  353.       pthread::mutex::guard lock(m_mtx, tid);
  354.       while (! m_signal($)) {
  355.         m_cond.wait(lock);
  356.       }
  357.  
  358.       m_signal($) = false;
  359.       m_finish($) = true;
  360.     }
  361.  
  362.     m_cond.broadcast(tid);
  363.   }
  364.  
  365.  
  366.   void thread(unsigned tidx) {
  367.     pthread::sys::thread tid(tidx);
  368.     if (! tidx) { // producer
  369.       producer(tid);
  370.     } else { // consumers
  371.       consumers(tid);
  372.     }
  373.   }
  374. };
  375.  
  376.  
  377. int main() {
  378.   {
  379.     rl::test_params params;
  380.     params.search_type = rl::random_scheduler_type;
  381.     params.iteration_count = 1000;
  382.     rl::simulate<condvar_test>(params);
  383.     std::cout << rl::test_result_str(params.test_result) << std::endl;
  384.   }
  385.   std::puts("\n\n\nFINISHED!\n___________________________________\n\
  386. press <ENTER> to exit...");
  387.   std::getchar();
  388.   return 0;
  389. }
RAW Paste Data
Top