chase-lev-deque-bugfix/note.txt

   1 #1: Ordering parameters
   2
   3 wildcard8 -> sc (fence in take())
   4 wildcard12 -> sc (update of top in take())
   5 *wildcard23 -> release (update of array in resize())
   6 wildcard25 -> acquire (load of top in push())
   7 *wildcard31 -> release (fence in push())
   8 wildcard33 -> acquire (load of top in steal())
   9 wildcard34 -> sc (fence in steal())
  10 *wildcard35 -> acquire (load of bottom in steal())
  11 *wildcard36 -> acquire (load of array in steal())
  12 wildcard39 -> sc (update of top in steal())
  13
  14 #1:
  15 wildcard31 -> release (fence)
  16 wildcard35 -> acquire
  17 Establish hb between push() and steal() via the variable bottom.
  18 **************** testcase1.c ****************
  19
  20 #2:
  21 wildcard8 -> sc (fence)
  22 wildcard34 -> sc (fence)
  23 When there are two consecutive steal() in the same thread, and another take() in
  24 another thread. The first steal() updates the top, and then gets the
  25 fence(wildcard34) in the second steal(), then it loads bottom (wildcard35). At
  26 the same time, in take() it first updates bottom (wildcard7), gets the fence (
  27 wildcard8) and then loads the top (wildcard9), as follows.
  28
  29 t.CAS (w39 in first steal())         b.store (w7 in take())
  30 fence (w34 in second steal())        fence (w8 in take())
  31 b.load (w35 in second steal())       t.load (w9 in take())
  32 Both loads can reads old value, so it makes both fences seq_cst.
  33 **************** testcase2.c ****************
  34
  35 #3:
  36 wildcard23 -> release
  37 wildcard36 -> acquire
  38 Update of array in resize(), should be release; since only steal() need to
  39 establish hb, so in steal wildcard36 should be acquire.
  40 **************** testcase4.c ****************
  41
  42 #5:
  43 wildcard25 -> acquire
  44 wildcard39 -> release (at least)
  45 Establish hb between steal() and push() when steal() loads bottom (w35) and uses
  46 CAS (w39) to update the top, and push() reads the top (w25) and updates bottom
  47 (w32). If not, w35 can read from w39 (future value).
  48 **************** testcase5.c ****************
  49
  50 wildcard33 -> acquire
  51 wildcard12 -> release (at least)
  52 Establish hb between take() and steal() when there's only one element in the
  53 deque, and take() gets the last element. The hb ensures that the steal() will
  54 see the updated bottom in take(). However, since fence (w34) is SC, w33 MAY be
  55 relaxed.
  56 !!! w33 can be relaxed since w34 is an SC fence. Probably w12 doesn't have to be
  57 release since w8 is an SC fence too, so it will have establish hb between the
  58 fences.
  59
  60 ##################################################
  61 testcase5.c is a testcase that has 2 threads, 1 of which has 1 steal() and the
  62 other has 3 push() followed by 2 take().
  63
  64
  65 By running our testcases from 1-6, it took:
  66 0m0.013s (testcase1)
  67 0m0.028s (testcase2)
  68 0m6.264s (testcase3)
  69 0m0.824s (testcase4)
  70 0m0.054s (testcase5)
  71 9m19.887s (testcase6)
  72
  73 In total: 9m27.02s
  74