SHARE
TWEET

Chris M Thomasson

a guest Jun 26th, 2009 194 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. Unbounded Dynamic Work-Stealing Deque
  3. Copyright (C) 2009  Christopher Michael Thomasson
  4.  
  5. This program is free software: you can redistribute it and/or modify
  6. it under the terms of the GNU General Public License as published by
  7. the Free Software Foundation, either version 3 of the License, or
  8. (at your option) any later version.
  9.  
  10.  
  11. This program is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16.  
  17. You should have received a copy of the GNU General Public License
  18. along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19. _______________________________________________________________________*/
  20.  
  21.  
  22.  
  23.  
  24.  
  25.  
  26. #include <relacy/relacy_std.hpp>
  27. #include <cstdio>
  28.  
  29.  
  30.  
  31.  
  32. #if ! defined (NDEBUG)
  33. #  define DBG_PRINTF(mp_exp) std::printf mp_exp
  34. #else
  35. #  define DBG_PRINTF(mp_exp) ((void)0)
  36. #endif
  37.  
  38.  
  39.  
  40.  
  41. #define WSDEQUE_SPLIT 4
  42.  
  43.  
  44. class wsdeque {
  45. public:
  46.   struct node {
  47.     rl::atomic<node*> m_next;
  48.     rl::atomic<node*> m_prev;
  49.   };
  50.  
  51.  
  52. private:
  53.   rl::atomic<node*> m_head;
  54.   rl::atomic<node*> m_tail;
  55.   rl::atomic<unsigned> m_lcount;
  56.   rl::atomic<unsigned> m_rcount;
  57.   rl::mutex m_mutex;
  58.  
  59.  
  60. public:
  61.   wsdeque() {
  62.     m_head($).store(NULL);
  63.     m_tail($).store(NULL);
  64.     m_lcount($).store(0);
  65.     m_rcount($).store(0);
  66.   }
  67.  
  68.  
  69.   ~wsdeque() {
  70.     RL_ASSERT(! m_head($).load());
  71.     RL_ASSERT(! m_tail($).load());
  72.     RL_ASSERT(! (m_lcount($).load() - m_rcount($).load()));
  73.   }
  74.  
  75.  
  76.   void push(node* n) {
  77.     unsigned lcount = m_lcount($).load();
  78.     node* head = m_head($).load();
  79.     n->m_prev($).store(NULL);
  80.     n->m_next($).store(head);
  81.     if (! head) {
  82.       m_tail($).store(n);
  83.     } else {
  84.       head->m_prev($).store(n);
  85.     }
  86.     m_head($).store(n);
  87.     m_lcount($).store(lcount + 1);
  88.   }
  89.  
  90.  
  91.   node* pop() {
  92.    retry:
  93.     node* head = m_head($).load();
  94.     if (head) {
  95.       bool unlock = false;
  96.       unsigned lcount = m_lcount($).load();
  97.       unsigned rcount = m_rcount($).load();
  98.       if (lcount - rcount <= WSDEQUE_SPLIT) {
  99.         m_mutex.lock($);
  100.         lcount = m_lcount($).load();
  101.         rcount = m_rcount($).load();
  102.         if (lcount - rcount > WSDEQUE_SPLIT ||
  103.           m_head($).load() != head) {
  104.           m_mutex.unlock($);
  105.           goto retry;
  106.         }
  107.         unlock = true;
  108.       }
  109.       node* next = head->m_next($).load();
  110.       m_head($).store(next);
  111.       if (! next) {
  112.         m_tail($).store(NULL);
  113.       } else {
  114.         next->m_prev($).store(NULL);
  115.       }
  116.       m_lcount($).store(lcount - 1);
  117.       if (unlock) {
  118.         m_mutex.unlock($);
  119.       }
  120.     }
  121.     return head;
  122.   }
  123.  
  124.  
  125.   node* steal() {
  126.    retry:
  127.     node* tail = m_tail($).load();
  128.     if (tail) {
  129.       unsigned lcount = m_lcount($).load();
  130.       unsigned rcount = m_rcount($).load();
  131.       if (lcount - rcount < WSDEQUE_SPLIT) {
  132.         return NULL;
  133.       }
  134.       if (! m_mutex.try_lock($)) {
  135.         return NULL;
  136.       }
  137.       lcount = m_lcount($).load();
  138.       rcount = m_rcount($).load();
  139.       if (lcount - rcount < WSDEQUE_SPLIT ||
  140.         m_tail($).load() != tail) {
  141.         m_mutex.unlock($);
  142.         goto retry;
  143.       }
  144.       node* prev = tail->m_prev($).load();
  145.       prev->m_next($) = NULL;
  146.       m_tail($).store(prev);
  147.       m_rcount($).store(rcount + 1);
  148.       m_mutex.unlock($);
  149.     }
  150.     return tail;
  151.   }
  152. };
  153.  
  154.  
  155.  
  156.  
  157. #define THREADS 7
  158. #define ITERS 10
  159.  
  160.  
  161. struct wsdeque_test : rl::test_suite<wsdeque_test, THREADS> {
  162.   wsdeque m_wsdeque;
  163.  
  164.   void thread(unsigned tidx) {
  165.     unsigned i;
  166.     wsdeque::node* n;
  167.     if (tidx < 1) {
  168.       rl::backoff b;
  169.       for (i = 0; i < ITERS; ++i) {
  170.         n = RL_NEW wsdeque::node;
  171.         m_wsdeque.push(n);
  172.         DBG_PRINTF(("Thread(%u) has locally pushed node(%p)\n",
  173.           tidx, (void*)n));
  174.       }
  175.       for (i = 0; i < ITERS; ++i) {
  176.         if ((n = m_wsdeque.pop())) {
  177.           DBG_PRINTF(("Thread(%u) has locally popped node(%p)\n",
  178.             tidx, (void*)n));
  179.           RL_DELETE(n);
  180.           b.yield($);
  181.         }
  182.       }  
  183.     } else {
  184.       for (i = 0; i < ITERS; ++i) {
  185.         if ((n = m_wsdeque.steal())) {
  186.           DBG_PRINTF(("Thread(%u) has remotely stolen node(%p)!\n",
  187.             tidx, (void*)n));
  188.           RL_DELETE(n);
  189.         }
  190.       }
  191.     }
  192.   }
  193. };
  194.  
  195.  
  196.  
  197.  
  198. int main() {
  199.   rl::test_params params;
  200.   params.iteration_count = 99999999;
  201.   //params.search_type = rl::fair_full_search_scheduler_type;
  202.   //params.search_type = rl::fair_context_bound_scheduler_type;
  203.   rl::simulate<wsdeque_test>(params);
  204.   std::puts("\n\n\n____________________________________\n"
  205.             "DONE!!!!\npress <ENTER> to exit...");
  206.   std::fflush(stdin);
  207.   std::fflush(stdout);
  208.   std::getchar();
  209.   return 0;
  210. }
RAW Paste Data
Top