Sacrificing the small hardware transaction for the greater good.

Ryan Yates and Michael Scott

http://goo.gl/DO0l7y

Goal

Support retry (blocking) with constant space overhead.

retry Implementation

We assume blocking is relatively rare, though occasionally long.
  • Bloom filter approximation of read- and write-sets.
  • Global wakeup structure holding blocked transactions.
    • Each entry is a read-set paired with the blocked thread.
    • Linked-list of chunks.
    • Protected by global "wakeup" lock

Wakeup Synchronization

  • A blocking transaction needs to add self to wakeup list.
  • A committing transaction needs to search wakeup list and wakeup transactions with a read-set overlapping the committing write-set.

Wakeup Synchronization Idea 1

Add transaction to wakeup list in HTM.
  • Conflicts between committing searches and blocking transactions abort entire blocking transaction.
  • Makes blocking transactions larger.
  • Still need to handle thread blocking.

Wakeup Synchronization Idea 2

Take the wakeup lock in HTM, then commit. Search in HTM.
  • Conflicts between committing searches and blocking transactions abort search.
  • Only one transaction can block at a time.

top:
  retrying = false
  XBEGIN // failure path not shown
    ...
    // retry with no prior TVar writes:
    if (wakeup_lock == 1)
      XABORT(RESTART)
    wakeup_lock = 1
    retrying = true
  XEND
  if (retrying)
    insert(wakeup_list, read_set)
    release(wakeup_lock)
    wait_for_wakeup()
    goto top
  

XBEGIN
... normal transaction execution with writes ...
XEND
for 0..retry count do
  XBEGIN(fail)
  if (wakeup_lock == 1)
    XABORT(RESTART)
  wakeup(wakeup_list, write_set)
  XEND
    return // exit transaction
  fail:
end
// fallback:
acquire(wakeup_lock)
wakeup(wakeup_list, write_set)
release(wakeup_lock)
  

Thanks!