edits
authorPeizhao Ou <peizhaoo@uci.edu>
Sat, 14 Nov 2015 01:56:22 +0000 (17:56 -0800)
committerPeizhao Ou <peizhaoo@uci.edu>
Sat, 14 Nov 2015 01:56:22 +0000 (17:56 -0800)
14 files changed:
benchmark/concurrent-hashmap/ConcurrentHashMap.java [new file with mode: 0644]
benchmark/concurrent-hashmap/Makefile [new file with mode: 0644]
benchmark/concurrent-hashmap/hashmap.h [new file with mode: 0644]
benchmark/concurrent-hashmap/main.cc [new file with mode: 0644]
benchmark/concurrent-hashmap/note.txt [new file with mode: 0644]
benchmark/ms-queue/my_queue.h
grammer/README.txt
grammer/spec_compiler.jj
note.txt [deleted file]
notes/interesting_examples.txt
src/edu/uci/eecs/specCompiler/codeGenerator/CodeGenerator.java
src/edu/uci/eecs/specCompiler/codeGenerator/CodeVariables.java
src/edu/uci/eecs/specCompiler/specExtraction/CommutativityRule.java [new file with mode: 0644]
src/edu/uci/eecs/specCompiler/specExtraction/GlobalConstruct.java

diff --git a/benchmark/concurrent-hashmap/ConcurrentHashMap.java b/benchmark/concurrent-hashmap/ConcurrentHashMap.java
new file mode 100644 (file)
index 0000000..23a4ed4
--- /dev/null
@@ -0,0 +1,1224 @@
+/*
+  File: ConcurrentHashMap
+
+  Written by Doug Lea. Adapted and released, under explicit
+  permission, from JDK1.2 HashMap.java and Hashtable.java which
+  carries the following copyright:
+
+     * Copyright 1997 by Sun Microsystems, Inc.,
+     * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
+     * All rights reserved.
+     *
+     * This software is the confidential and proprietary information
+     * of Sun Microsystems, Inc. ("Confidential Information").  You
+     * shall not disclose such Confidential Information and shall use
+     * it only in accordance with the terms of the license agreement
+     * you entered into with Sun.
+
+  History:
+  Date       Who                What
+  26nov2000  dl               Created, based on ConcurrentReaderHashMap
+  12jan2001  dl               public release
+  17nov2001  dl               Minor tunings
+  24oct2003  dl               Segment implements Serializable
+*/
+
+package EDU.oswego.cs.dl.util.concurrent;
+
+import java.util.Map;
+import java.util.AbstractMap;
+import java.util.AbstractSet;
+import java.util.AbstractCollection;
+import java.util.Collection;
+import java.util.Set;
+import java.util.Iterator;
+import java.util.Enumeration;
+import java.util.NoSuchElementException;
+
+import java.io.Serializable;
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+
+
+/**
+ * A version of Hashtable supporting 
+ * concurrency for both retrievals and updates:
+ *
+ * <dl> 
+ * <dt> Retrievals
+ *
+ * <dd> Retrievals may overlap updates.  (This is the same policy as
+ * ConcurrentReaderHashMap.)  Successful retrievals using get(key) and
+ * containsKey(key) usually run without locking. Unsuccessful
+ * retrievals (i.e., when the key is not present) do involve brief
+ * synchronization (locking).  Because retrieval operations can
+ * ordinarily overlap with update operations (i.e., put, remove, and
+ * their derivatives), retrievals can only be guaranteed to return the
+ * results of the most recently <em>completed</em> operations holding
+ * upon their onset. Retrieval operations may or may not return
+ * results reflecting in-progress writing operations.  However, the
+ * retrieval operations do always return consistent results -- either
+ * those holding before any single modification or after it, but never
+ * a nonsense result.  For aggregate operations such as putAll and
+ * clear, concurrent reads may reflect insertion or removal of only
+ * some entries.  
+ * <p>
+ *
+ * Iterators and Enumerations (i.e., those returned by
+ * keySet().iterator(), entrySet().iterator(), values().iterator(),
+ * keys(), and elements()) return elements reflecting the state of the
+ * hash table at some point at or since the creation of the
+ * iterator/enumeration.  They will return at most one instance of
+ * each element (via next()/nextElement()), but might or might not
+ * reflect puts and removes that have been processed since they were
+ * created.  They do <em>not</em> throw ConcurrentModificationException.
+ * However, these iterators are designed to be used by only one
+ * thread at a time. Passing an iterator across multiple threads may
+ * lead to unpredictable results if the table is being concurrently
+ * modified.  <p>
+ *
+ *
+ * <dt> Updates
+ *
+ * <dd> This class supports a hard-wired preset <em>concurrency
+ * level</em> of 32. This allows a maximum of 32 put and/or remove
+ * operations to proceed concurrently. This level is an upper bound on
+ * concurrency, not a guarantee, since it interacts with how
+ * well-strewn elements are across bins of the table. (The preset
+ * value in part reflects the fact that even on large multiprocessors,
+ * factors other than synchronization tend to be bottlenecks when more
+ * than 32 threads concurrently attempt updates.)
+ * Additionally, operations triggering internal resizing and clearing
+ * do not execute concurrently with any operation.  
+ * <p>
+ *
+ * There is <em>NOT</em> any support for locking the entire table to
+ * prevent updates. This makes it imposssible, for example, to
+ * add an element only if it is not already present, since another
+ * thread may be in the process of doing the same thing.
+ * If you need such capabilities, consider instead using the
+ * ConcurrentReaderHashMap class. 
+ *
+ * </dl>
+ *
+ * Because of how concurrency control is split up, the
+ * size() and isEmpty() methods require accumulations across 32
+ * control segments, and so might be slightly slower than you expect.
+ * <p>
+ *
+ * This class may be used as a direct replacement for
+ * java.util.Hashtable in any application that does not rely
+ * on the ability to lock the entire table to prevent updates.  
+ * As of this writing, it performs much faster than Hashtable in
+ * typical multi-threaded applications with multiple readers and writers.
+ * Like Hashtable but unlike java.util.HashMap,
+ * this class does NOT allow <tt>null</tt> to be used as a key or
+ * value. 
+ * <p> 
+ *
+ * Implementation note: A slightly
+ * faster implementation of this class will be possible once planned
+ * Java Memory Model revisions are in place.
+ *
+ * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>]
+
+ **/
+
+
+public class ConcurrentHashMap 
+  extends    AbstractMap 
+  implements Map, Cloneable, Serializable {
+
+  /*
+    The basic strategy is an optimistic-style scheme based on
+    the guarantee that the hash table and its lists are always
+    kept in a consistent enough state to be read without locking:
+
+    * Read operations first proceed without locking, by traversing the
+       apparently correct list of the apparently correct bin. If an
+       entry is found, but not invalidated (value field null), it is
+       returned. If not found, operations must recheck (after a memory
+       barrier) to make sure they are using both the right list and
+       the right table (which can change under resizes). If
+       invalidated, reads must acquire main update lock to wait out
+       the update, and then re-traverse.
+
+    * All list additions are at the front of each bin, making it easy
+       to check changes, and also fast to traverse.  Entry next
+       pointers are never assigned. Remove() builds new nodes when
+       necessary to preserve this.
+
+    * Remove() (also clear()) invalidates removed nodes to alert read
+       operations that they must wait out the full modifications.
+
+    * Locking for puts, removes (and, when necessary gets, etc)
+      is controlled by Segments, each covering a portion of the
+      table. During operations requiring global exclusivity (mainly
+      resize and clear), ALL of these locks are acquired at once.
+      Note that these segments are NOT contiguous -- they are based
+      on the least 5 bits of hashcodes. This ensures that the same
+      segment controls the same slots before and after resizing, which
+      is necessary for supporting concurrent retrievals. This
+      comes at the price of a mismatch of logical vs physical locality,
+      but this seems not to be a performance problem in practice.
+  */
+
+  /**
+   * The hash table data.
+   */
+  protected transient Entry[] table;
+
+
+  /** 
+   * The number of concurrency control segments.
+   * The value can be at most 32 since ints are used
+   * as bitsets over segments. Emprically, it doesn't
+   * seem to pay to decrease it either, so the value should be at least 32.
+   * In other words, do not redefine this :-)
+   **/
+
+  protected static final int CONCURRENCY_LEVEL = 32;
+
+  /**
+   * Mask value for indexing into segments
+   **/
+
+  protected static final int SEGMENT_MASK = CONCURRENCY_LEVEL - 1;
+
+  /**
+   * Bookkeeping for each concurrency control segment.
+   * Each segment contains a local count of the number of 
+   * elements in its region.
+   * However, the main use of a Segment is for its lock.
+   **/
+  protected final static class Segment implements Serializable {
+    /**
+     * The number of elements in this segment's region.
+     * It is always updated within synchronized blocks.
+     **/
+    protected int count;
+
+    /**
+     * Get the count under synch. 
+     **/
+    protected synchronized int getCount() { return count; }
+
+    /**
+     * Force a synchronization
+     **/
+    protected synchronized void synch() {}
+  }
+
+  /**
+   * The array of concurrency control segments.
+   **/
+
+  protected final Segment[] segments = new Segment[CONCURRENCY_LEVEL]; 
+
+
+  /**
+   * The default initial number of table slots for this table (32).
+   * Used when not otherwise specified in constructor.
+   **/
+  public static int DEFAULT_INITIAL_CAPACITY = 32; 
+
+
+  /**
+   * The minimum capacity, used if a lower value is implicitly specified
+   * by either of the constructors with arguments.  
+   * MUST be a power of two.
+   */
+  private static final int MINIMUM_CAPACITY = 32;
+  
+  /**
+   * The maximum capacity, used if a higher value is implicitly specified
+   * by either of the constructors with arguments.
+   * MUST be a power of two <= 1<<30.
+   */
+  private static final int MAXIMUM_CAPACITY = 1 << 30;
+  
+  /**
+   * The default load factor for this table (0.75)
+   * Used when not otherwise specified in constructor.
+   **/
+
+  public static final float DEFAULT_LOAD_FACTOR = 0.75f; 
+
+  /**
+   * The load factor for the hash table.
+   *
+   * @serial
+   */
+  protected final float loadFactor;
+
+  /**
+   * Per-segment resize threshold.  
+   *
+   * @serial
+   */
+  protected int threshold;
+
+
+  /**
+   * Number of segments voting for resize. The table is
+   * doubled when 1/4 of the segments reach threshold.
+   * Volatile but updated without synch since this is just a heuristic.
+   **/
+
+  protected transient volatile int votesForResize;
+
+
+  /**
+   * Return the number of set bits in w.
+   * For a derivation of this algorithm, see
+   * "Algorithms and data structures with applications to 
+   *  graphics and geometry", by Jurg Nievergelt and Klaus Hinrichs,
+   *  Prentice Hall, 1993.
+   * See also notes by Torsten Sillke at
+   * http://www.mathematik.uni-bielefeld.de/~sillke/PROBLEMS/bitcount
+   **/
+  protected static int bitcount(int w) {
+    w -= (0xaaaaaaaa & w) >>> 1;
+    w = (w & 0x33333333) + ((w >>> 2) & 0x33333333);
+    w = (w + (w >>> 4)) & 0x0f0f0f0f;
+    w += w >>> 8;
+    w += w >>> 16;
+    return w & 0xff;
+  }
+
+  /**
+   * Returns the appropriate capacity (power of two) for the specified 
+   * initial capacity argument.
+   */
+  private int p2capacity(int initialCapacity) {
+    int cap = initialCapacity;
+    
+    // Compute the appropriate capacity
+    int result;
+    if (cap > MAXIMUM_CAPACITY || cap < 0) {
+      result = MAXIMUM_CAPACITY;
+    } else {
+      result = MINIMUM_CAPACITY;
+      while (result < cap)
+        result <<= 1;
+    }
+    return result;
+  }
+
+  /**
+   * Return hash code for Object x. Since we are using power-of-two
+   * tables, it is worth the effort to improve hashcode via
+   * the same multiplicative scheme as used in IdentityHashMap.
+   */
+  protected static int hash(Object x) {
+    int h = x.hashCode();
+    // Multiply by 127 (quickly, via shifts), and mix in some high
+    // bits to help guard against bunching of codes that are
+    // consecutive or equally spaced.
+    return ((h << 7) - h + (h >>> 9) + (h >>> 17));
+  }
+
+
+  /** 
+   * Check for equality of non-null references x and y. 
+   **/
+  protected boolean eq(Object x, Object y) {
+    return x == y || x.equals(y);
+  }
+
+  /** Create table array and set the per-segment threshold **/
+  protected Entry[] newTable(int capacity) {
+    threshold = (int)(capacity * loadFactor / CONCURRENCY_LEVEL) + 1;
+    return new Entry[capacity];
+  }
+
+  /**
+   * Constructs a new, empty map with the specified initial 
+   * capacity and the specified load factor.
+   *
+   * @param initialCapacity the initial capacity.
+   *  The actual initial capacity is rounded to the nearest power of two.
+   * @param loadFactor  the load factor threshold, used to control resizing.
+   *   This value is used in an approximate way: When at least
+   *   a quarter of the segments of the table reach per-segment threshold, or
+   *   one of the segments itself exceeds overall threshold,
+   *   the table is doubled. 
+   *   This will on average cause resizing when the table-wide
+   *   load factor is slightly less than the threshold. If you'd like
+   *   to avoid resizing, you can set this to a ridiculously large
+   *   value.
+   * @throws IllegalArgumentException  if the load factor is nonpositive.
+   */
+  public ConcurrentHashMap(int initialCapacity, 
+                           float loadFactor) {
+    if (!(loadFactor > 0))
+      throw new IllegalArgumentException("Illegal Load factor: "+
+                                         loadFactor);
+    this.loadFactor = loadFactor;
+    for (int i = 0; i < segments.length; ++i) 
+      segments[i] = new Segment();
+    int cap = p2capacity(initialCapacity);
+    table = newTable(cap);
+  }
+
+  /**
+   * Constructs a new, empty map with the specified initial 
+   * capacity and default load factor.
+   *
+   * @param   initialCapacity   the initial capacity of the 
+   *                            ConcurrentHashMap.
+   * @throws    IllegalArgumentException if the initial maximum number 
+   *              of elements is less
+   *              than zero.
+   */
+  public ConcurrentHashMap(int initialCapacity) {
+    this(initialCapacity, DEFAULT_LOAD_FACTOR);
+  }
+
+  /**
+   * Constructs a new, empty map with a default initial capacity
+   * and default load factor.
+   */
+  public ConcurrentHashMap() {
+    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
+  }
+
+  /**
+   * Constructs a new map with the same mappings as the given map.  The
+   * map is created with a capacity of twice the number of mappings in
+   * the given map or 32 (whichever is greater), and a default load factor.
+   */
+  public ConcurrentHashMap(Map t) {
+    this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1, 
+                  MINIMUM_CAPACITY),
+         DEFAULT_LOAD_FACTOR);
+    putAll(t);
+  }
+
+  /**
+   * Returns the number of key-value mappings in this map.
+   *
+   * @return the number of key-value mappings in this map.
+   */
+  public int size() {
+    int c = 0;
+    for (int i = 0; i < segments.length; ++i) 
+      c += segments[i].getCount();
+    return c;
+  }
+
+  /**
+   * Returns <tt>true</tt> if this map contains no key-value mappings.
+   *
+   * @return <tt>true</tt> if this map contains no key-value mappings.
+   */
+  public boolean isEmpty() {
+    for (int i = 0; i < segments.length; ++i) 
+      if (segments[i].getCount() != 0)
+        return false;
+    return true;
+  }
+
+
+  /**
+   * Returns the value to which the specified key is mapped in this table.
+   *
+   * @param   key   a key in the table.
+   * @return  the value to which the key is mapped in this table;
+   *          <code>null</code> if the key is not mapped to any value in
+   *          this table.
+   * @exception  NullPointerException  if the key is
+   *               <code>null</code>.
+   * @see     #put(Object, Object)
+   */
+  public Object get(Object key) {
+    int hash = hash(key);     // throws null pointer exception if key null
+
+    // Try first without locking...
+    Entry[] tab = table;
+    int index = hash & (tab.length - 1);
+    Entry first = tab[index];
+    Entry e;
+
+    for (e = first; e != null; e = e.next) {
+      if (e.hash == hash && eq(key, e.key)) {
+        Object value = e.value;
+        if (value != null) 
+          return value;
+        else
+          break;
+      }
+    }
+
+    // Recheck under synch if key apparently not there or interference
+    Segment seg = segments[hash & SEGMENT_MASK];
+    synchronized(seg) { 
+      tab = table;
+      index = hash & (tab.length - 1);
+      Entry newFirst = tab[index];
+      if (e != null || first != newFirst) {
+        for (e = newFirst; e != null; e = e.next) {
+          if (e.hash == hash && eq(key, e.key)) 
+            return e.value;
+        }
+      }
+      return null;
+    }
+  }
+
+  /**
+   * Tests if the specified object is a key in this table.
+   * 
+   * @param   key   possible key.
+   * @return  <code>true</code> if and only if the specified object 
+   *          is a key in this table, as determined by the 
+   *          <tt>equals</tt> method; <code>false</code> otherwise.
+   * @exception  NullPointerException  if the key is
+   *               <code>null</code>.
+   * @see     #contains(Object)
+   */
+
+  public boolean containsKey(Object key) {
+    return get(key) != null;
+  }
+  
+
+  /**
+   * Maps the specified <code>key</code> to the specified 
+   * <code>value</code> in this table. Neither the key nor the 
+   * value can be <code>null</code>. (Note that this policy is
+   * the same as for java.util.Hashtable, but unlike java.util.HashMap,
+   * which does accept nulls as valid keys and values.)<p>
+   *
+   * The value can be retrieved by calling the <code>get</code> method 
+   * with a key that is equal to the original key. 
+   *
+   * @param      key     the table key.
+   * @param      value   the value.
+   * @return     the previous value of the specified key in this table,
+   *             or <code>null</code> if it did not have one.
+   * @exception  NullPointerException  if the key or value is
+   *               <code>null</code>.
+   * @see     Object#equals(Object)
+   * @see     #get(Object)
+   */
+  public Object put(Object key, Object value) {
+    if (value == null) 
+      throw new NullPointerException();
+    
+    int hash = hash(key);
+    Segment seg = segments[hash & SEGMENT_MASK];
+    int segcount;
+    Entry[] tab;
+    int votes;
+
+    synchronized(seg) {
+      tab = table;
+      int index = hash & (tab.length-1);
+      Entry first = tab[index];
+
+      for (Entry e = first; e != null; e = e.next) {
+        if (e.hash == hash && eq(key, e.key)) {
+          Object oldValue = e.value; 
+          e.value = value;
+          return oldValue;
+        }
+      }
+
+      //  Add to front of list
+      Entry newEntry = new Entry(hash, key, value, first);
+      tab[index] = newEntry;
+
+      if ((segcount = ++seg.count) < threshold)
+        return null;
+
+      int bit = (1 << (hash & SEGMENT_MASK));
+      votes = votesForResize;
+      if ((votes & bit) == 0)
+        votes = votesForResize |= bit;
+    }
+
+    // Attempt resize if 1/4 segs vote,
+    // or if this seg itself reaches the overall threshold.
+    // (The latter check is just a safeguard to avoid pathological cases.)
+    if (bitcount(votes) >= CONCURRENCY_LEVEL / 4  ||
+        segcount > (threshold * CONCURRENCY_LEVEL)) 
+      resize(0, tab);
+
+    return null;
+  }
+
+  /**
+   * Gather all locks in order to call rehash, by
+   * recursing within synch blocks for each segment index.
+   * @param index the current segment. initially call value must be 0
+   * @param assumedTab the state of table on first call to resize. If
+   * this changes on any call, the attempt is aborted because the
+   * table has already been resized by another thread.
+   */
+
+  protected void resize(int index, Entry[] assumedTab) {
+    Segment seg = segments[index];
+    synchronized(seg) {
+      if (assumedTab == table) {
+        int next = index+1;
+        if (next < segments.length)
+          resize(next, assumedTab);
+        else
+          rehash();
+      }
+    }
+  }
+
+  /**
+   * Rehashes the contents of this map into a new table
+   * with a larger capacity. 
+   */
+  protected void rehash() {
+    votesForResize = 0; // reset
+
+    Entry[] oldTable = table;
+    int oldCapacity = oldTable.length;
+
+    if (oldCapacity >= MAXIMUM_CAPACITY) {
+      threshold = Integer.MAX_VALUE; // avoid retriggering
+      return;
+    }
+    
+    int newCapacity = oldCapacity << 1;
+    Entry[] newTable = newTable(newCapacity);
+    int mask = newCapacity - 1;
+
+    /*
+     * Reclassify nodes in each list to new Map.  Because we are
+     * using power-of-two expansion, the elements from each bin
+     * must either stay at same index, or move to
+     * oldCapacity+index. We also eliminate unnecessary node
+     * creation by catching cases where old nodes can be reused
+     * because their next fields won't change. Statistically, at
+     * the default threshhold, only about one-sixth of them need
+     * cloning. (The nodes they replace will be garbage
+     * collectable as soon as they are no longer referenced by any
+     * reader thread that may be in the midst of traversing table
+     * right now.)
+     */
+    
+    for (int i = 0; i < oldCapacity ; i++) {
+      // We need to guarantee that any existing reads of old Map can
+      //  proceed. So we cannot yet null out each bin.  
+      Entry e = oldTable[i];
+      
+      if (e != null) {
+        int idx = e.hash & mask;
+        Entry next = e.next;
+        
+        //  Single node on list
+        if (next == null) 
+          newTable[idx] = e;
+        
+        else {    
+          // Reuse trailing consecutive sequence of all same bit
+          Entry lastRun = e;
+          int lastIdx = idx;
+          for (Entry last = next; last != null; last = last.next) {
+            int k = last.hash & mask;
+            if (k != lastIdx) {
+              lastIdx = k;
+              lastRun = last;
+            }
+          }
+          newTable[lastIdx] = lastRun;
+          
+          // Clone all remaining nodes
+          for (Entry p = e; p != lastRun; p = p.next) {
+            int k = p.hash & mask;
+            newTable[k] = new Entry(p.hash, p.key, 
+                                    p.value, newTable[k]);
+          }
+        }
+      }
+    }
+    
+    table = newTable;
+  }
+
+
+  /**
+   * Removes the key (and its corresponding value) from this 
+   * table. This method does nothing if the key is not in the table.
+   *
+   * @param   key   the key that needs to be removed.
+   * @return  the value to which the key had been mapped in this table,
+   *          or <code>null</code> if the key did not have a mapping.
+   * @exception  NullPointerException  if the key is
+   *               <code>null</code>.
+   */
+  public Object remove(Object key) {
+    return remove(key, null); 
+  }
+
+
+  /**
+   * Removes the (key, value) pair from this 
+   * table. This method does nothing if the key is not in the table,
+   * or if the key is associated with a different value. This method
+   * is needed by EntrySet.
+   *
+   * @param   key   the key that needs to be removed.
+   * @param   value   the associated value. If the value is null,
+   *                   it means "any value".
+   * @return  the value to which the key had been mapped in this table,
+   *          or <code>null</code> if the key did not have a mapping.
+   * @exception  NullPointerException  if the key is
+   *               <code>null</code>.
+   */
+
+  protected Object remove(Object key, Object value) {
+    /*
+      Find the entry, then 
+        1. Set value field to null, to force get() to retry
+        2. Rebuild the list without this entry.
+           All entries following removed node can stay in list, but
+           all preceeding ones need to be cloned.  Traversals rely
+           on this strategy to ensure that elements will not be
+          repeated during iteration.
+    */
+
+    int hash = hash(key);
+    Segment seg = segments[hash & SEGMENT_MASK];
+
+    synchronized(seg) {
+      Entry[] tab = table;
+      int index = hash & (tab.length-1);
+      Entry first = tab[index];
+      Entry e = first;
+
+      for (;;) {
+        if (e == null)
+          return null;
+        if (e.hash == hash && eq(key, e.key)) 
+          break;
+        e = e.next;
+      }
+
+      Object oldValue = e.value;
+      if (value != null && !value.equals(oldValue))
+        return null;
+     
+      e.value = null;
+
+      Entry head = e.next;
+      for (Entry p = first; p != e; p = p.next) 
+        head = new Entry(p.hash, p.key, p.value, head);
+      tab[index] = head;
+      seg.count--;
+      return oldValue;
+    }
+  }
+
+
+  /**
+   * Returns <tt>true</tt> if this map maps one or more keys to the
+   * specified value. Note: This method requires a full internal
+   * traversal of the hash table, and so is much slower than
+   * method <tt>containsKey</tt>.
+   *
+   * @param value value whose presence in this map is to be tested.
+   * @return <tt>true</tt> if this map maps one or more keys to the
+   * specified value.  
+   * @exception  NullPointerException  if the value is <code>null</code>.
+   */
+  public boolean containsValue(Object value) {
+
+    if (value == null) throw new NullPointerException();
+
+    for (int s = 0; s < segments.length; ++s) {
+      Segment seg = segments[s];
+      Entry[] tab;
+      synchronized(seg) { tab = table; }
+      for (int i = s; i < tab.length; i+= segments.length) {
+        for (Entry e = tab[i]; e != null; e = e.next) 
+          if (value.equals(e.value))
+            return true;
+      }
+    }
+    return false;
+  }
+
+  /**
+   * Tests if some key maps into the specified value in this table.
+   * This operation is more expensive than the <code>containsKey</code>
+   * method.<p>
+   *
+   * Note that this method is identical in functionality to containsValue,
+   * (which is part of the Map interface in the collections framework).
+   * 
+   * @param      value   a value to search for.
+   * @return     <code>true</code> if and only if some key maps to the
+   *             <code>value</code> argument in this table as 
+   *             determined by the <tt>equals</tt> method;
+   *             <code>false</code> otherwise.
+   * @exception  NullPointerException  if the value is <code>null</code>.
+   * @see        #containsKey(Object)
+   * @see        #containsValue(Object)
+   * @see         Map
+   */
+
+  public boolean contains(Object value) {
+    return containsValue(value);
+  }
+
+  /**
+   * Copies all of the mappings from the specified map to this one.
+   * 
+   * These mappings replace any mappings that this map had for any of the
+   * keys currently in the specified Map.
+   *
+   * @param t Mappings to be stored in this map.
+   */
+
+  public void putAll(Map t) {
+    int n = t.size();
+    if (n == 0)
+      return;
+
+    // Expand enough to hold at least n elements without resizing.
+    // We can only resize table by factor of two at a time.
+    // It is faster to rehash with fewer elements, so do it now.
+    for(;;) {
+      Entry[] tab;
+      int max;
+      synchronized(segments[0]) { // must synch on some segment. pick 0.
+        tab = table;
+        max = threshold * CONCURRENCY_LEVEL;
+      }
+      if (n < max)
+        break;
+      resize(0, tab);
+    }
+
+    for (Iterator it = t.entrySet().iterator(); it.hasNext();) {
+      Map.Entry entry = (Map.Entry) it.next();
+      put(entry.getKey(), entry.getValue());
+    }
+  }
+
+  /**
+   * Removes all mappings from this map.
+   */
+
+  public void clear() {
+    // We don't need all locks at once so long as locks
+    //   are obtained in low to high order
+    for (int s = 0; s < segments.length; ++s) {
+      Segment seg = segments[s];
+      synchronized(seg) {
+        Entry[] tab = table;
+        for (int i = s; i < tab.length; i+= segments.length) {
+          for (Entry e = tab[i]; e != null; e = e.next) 
+            e.value = null; 
+          tab[i] = null;
+          seg.count = 0;
+        }
+      }
+    }
+  }
+
+  /**
+   * Returns a shallow copy of this 
+   * <tt>ConcurrentHashMap</tt> instance: the keys and
+   * values themselves are not cloned.
+   *
+   * @return a shallow copy of this map.
+   */
+
+  public Object clone() {
+    // We cannot call super.clone, since it would share final segments array,
+    // and there's no way to reassign finals.
+    return new ConcurrentHashMap(this);
+  }
+
+  // Views
+
+  protected transient Set keySet = null;
+  protected transient Set entrySet = null;
+  protected transient Collection values = null;
+
+  /**
+   * Returns a set view of the keys contained in this map.  The set is
+   * backed by the map, so changes to the map are reflected in the set, and
+   * vice-versa.  The set supports element removal, which removes the
+   * corresponding mapping from this map, via the <tt>Iterator.remove</tt>,
+   * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt>, and
+   * <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
+   * <tt>addAll</tt> operations.
+   *
+   * @return a set view of the keys contained in this map.
+   */
+  
+  public Set keySet() {
+    Set ks = keySet;
+    return (ks != null)? ks : (keySet = new KeySet());
+  }
+  
+  private class KeySet extends AbstractSet {
+    public Iterator iterator() {
+      return new KeyIterator();
+    }
+    public int size() {
+      return ConcurrentHashMap.this.size();
+    }
+    public boolean contains(Object o) {
+      return ConcurrentHashMap.this.containsKey(o);
+    }
+    public boolean remove(Object o) {
+      return ConcurrentHashMap.this.remove(o) != null;
+    }
+    public void clear() {
+      ConcurrentHashMap.this.clear();
+    }
+  }
+
+  /**
+   * Returns a collection view of the values contained in this map.  The
+   * collection is backed by the map, so changes to the map are reflected in
+   * the collection, and vice-versa.  The collection supports element
+   * removal, which removes the corresponding mapping from this map, via the
+   * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
+   * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
+   * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
+   *
+   * @return a collection view of the values contained in this map.
+   */
+  
+  public Collection values() {
+    Collection vs = values;
+    return (vs != null)? vs : (values = new Values());
+  }
+  
+  private class Values extends AbstractCollection {
+    public Iterator iterator() {
+      return new ValueIterator();
+    }
+    public int size() {
+      return ConcurrentHashMap.this.size();
+    }
+    public boolean contains(Object o) {
+      return ConcurrentHashMap.this.containsValue(o);
+    }
+    public void clear() {
+      ConcurrentHashMap.this.clear();
+    }
+  }
+
+  /**
+   * Returns a collection view of the mappings contained in this map.  Each
+   * element in the returned collection is a <tt>Map.Entry</tt>.  The
+   * collection is backed by the map, so changes to the map are reflected in
+   * the collection, and vice-versa.  The collection supports element
+   * removal, which removes the corresponding mapping from the map, via the
+   * <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
+   * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
+   * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
+   *
+   * @return a collection view of the mappings contained in this map.
+   */
+  
+  public Set entrySet() {
+    Set es = entrySet;
+    return (es != null) ? es : (entrySet = new EntrySet());
+  }
+
+  private class EntrySet extends AbstractSet {
+    public Iterator iterator() {
+      return new HashIterator();
+    }
+    public boolean contains(Object o) {
+      if (!(o instanceof Map.Entry))
+        return false;
+      Map.Entry entry = (Map.Entry)o;
+      Object v = ConcurrentHashMap.this.get(entry.getKey());
+      return v != null && v.equals(entry.getValue());
+    }
+    public boolean remove(Object o) {
+      if (!(o instanceof Map.Entry))
+        return false;
+      Map.Entry e = (Map.Entry)o;
+      return ConcurrentHashMap.this.remove(e.getKey(), e.getValue()) != null;
+    }
+    public int size() {
+      return ConcurrentHashMap.this.size();
+    }
+    public void clear() {
+      ConcurrentHashMap.this.clear();
+    }
+  }
+
+  /**
+   * Returns an enumeration of the keys in this table.
+   *
+   * @return  an enumeration of the keys in this table.
+   * @see     Enumeration
+   * @see     #elements()
+   * @see      #keySet()
+   * @see      Map
+   */
+  public Enumeration keys() {
+    return new KeyIterator();
+  }
+
+  /**
+   * Returns an enumeration of the values in this table.
+   * Use the Enumeration methods on the returned object to fetch the elements
+   * sequentially.
+   *
+   * @return  an enumeration of the values in this table.
+   * @see     java.util.Enumeration
+   * @see     #keys()
+   * @see      #values()
+   * @see      Map
+   */
+  
+  public Enumeration elements() {
+    return new ValueIterator();
+  }
+
+  /**
+   * ConcurrentHashMap collision list entry.
+   */
+
+  protected static class Entry implements Map.Entry {
+    /* 
+       The use of volatile for value field ensures that
+       we can detect status changes without synchronization.
+       The other fields are never changed, and are
+       marked as final. 
+    */
+
+    protected final Object key;
+    protected volatile Object value;
+    protected final int hash;
+    protected final Entry next;
+
+    Entry(int hash, Object key, Object value, Entry next) {
+      this.value = value;
+      this.hash = hash;
+      this.key = key;
+      this.next = next;
+    }
+
+    // Map.Entry Ops 
+
+    public Object getKey() {
+      return key;
+    }
+
+    /**
+     * Get the value.  Note: In an entrySet or entrySet.iterator,
+     * unless you can guarantee lack of concurrent modification,
+     * <tt>getValue</tt> <em>might</em> return null, reflecting the
+     * fact that the entry has been concurrently removed. However,
+     * there are no assurances that concurrent removals will be
+     * reflected using this method.
+     * 
+     * @return     the current value, or null if the entry has been 
+     * detectably removed.
+     **/
+    public Object getValue() {
+      return value; 
+    }
+
+    /**
+     * Set the value of this entry.  Note: In an entrySet or
+     * entrySet.iterator), unless you can guarantee lack of concurrent
+     * modification, <tt>setValue</tt> is not strictly guaranteed to
+     * actually replace the value field obtained via the <tt>get</tt>
+     * operation of the underlying hash table in multithreaded
+     * applications.  If iterator-wide synchronization is not used,
+     * and any other concurrent <tt>put</tt> or <tt>remove</tt>
+     * operations occur, sometimes even to <em>other</em> entries,
+     * then this change is not guaranteed to be reflected in the hash
+     * table. (It might, or it might not. There are no assurances
+     * either way.)
+     *
+     * @param      value   the new value.
+     * @return     the previous value, or null if entry has been detectably
+     * removed.
+     * @exception  NullPointerException  if the value is <code>null</code>.
+     * 
+     **/
+
+    public Object setValue(Object value) {
+      if (value == null)
+        throw new NullPointerException();
+      Object oldValue = this.value;
+      this.value = value;
+      return oldValue;
+    }
+
+    public boolean equals(Object o) {
+      if (!(o instanceof Map.Entry))
+        return false;
+      Map.Entry e = (Map.Entry)o;
+      return (key.equals(e.getKey()) && value.equals(e.getValue()));
+    }
+    
+    public int hashCode() {
+      return  key.hashCode() ^ value.hashCode();
+    }
+    
+    public String toString() {
+      return key + "=" + value;
+    }
+
+  }
+
+  protected class HashIterator implements Iterator, Enumeration {
+    protected final Entry[] tab;           // snapshot of table
+    protected int index;                   // current slot 
+    protected Entry entry = null;          // current node of slot
+    protected Object currentKey;           // key for current node
+    protected Object currentValue;         // value for current node
+    protected Entry lastReturned = null;   // last node returned by next
+
+    protected HashIterator() {
+      // force all segments to synch
+      synchronized(segments[0]) { tab = table; }
+      for (int i = 1; i < segments.length; ++i) segments[i].synch();
+      index = tab.length - 1;
+    }
+
+    public boolean hasMoreElements() { return hasNext(); }
+    public Object nextElement() { return next(); }
+
+    public boolean hasNext() {
+      /*
+        currentkey and currentValue are set here to ensure that next()
+        returns normally if hasNext() returns true. This avoids
+        surprises especially when final element is removed during
+        traversal -- instead, we just ignore the removal during
+        current traversal.  
+      */
+
+      for (;;) {
+        if (entry != null) {
+          Object v = entry.value;
+          if (v != null) {
+            currentKey = entry.key;
+            currentValue = v;
+            return true;
+          }
+          else
+            entry = entry.next;
+        }
+
+        while (entry == null && index >= 0)
+          entry = tab[index--];
+
+        if (entry == null) {
+          currentKey = currentValue = null;
+          return false;
+        }
+      }
+    }
+
+    protected Object returnValueOfNext() { return entry; }
+
+    public Object next() {
+      if (currentKey == null && !hasNext())
+        throw new NoSuchElementException();
+
+      Object result = returnValueOfNext();
+      lastReturned = entry;
+      currentKey = currentValue = null;
+      entry = entry.next;
+      return result;
+    }
+
+    public void remove() {
+      if (lastReturned == null)
+        throw new IllegalStateException();
+      ConcurrentHashMap.this.remove(lastReturned.key);
+      lastReturned = null;
+    }
+
+  }
+
+  protected class KeyIterator extends HashIterator {
+    protected Object returnValueOfNext() { return currentKey; }
+  }
+  
+  protected class ValueIterator extends HashIterator {
+    protected Object returnValueOfNext() { return currentValue; }
+  }
+  
+  /**
+   * Save the state of the <tt>ConcurrentHashMap</tt> 
+   * instance to a stream (i.e.,
+   * serialize it).
+   *
+   * @serialData  
+   * An estimate of the table size, followed by
+   * the key (Object) and value (Object)
+   * for each key-value mapping, followed by a null pair.
+   * The key-value mappings are emitted in no particular order.
+   */
+
+  private void writeObject(java.io.ObjectOutputStream s)
+    throws IOException  {
+    // Write out the loadfactor, and any hidden stuff
+    s.defaultWriteObject();
+
+    // Write out capacity estimate. It is OK if this
+    // changes during the write, since it is only used by
+    // readObject to set initial capacity, to avoid needless resizings.
+
+    int cap;
+    synchronized(segments[0]) { cap = table.length; }
+    s.writeInt(cap);
+
+    // Write out keys and values (alternating)
+    for (int k = 0; k < segments.length; ++k) {
+      Segment seg = segments[k];
+      Entry[] tab;
+      synchronized(seg) { tab = table; }
+      for (int i = k; i < tab.length; i+= segments.length) {
+        for (Entry e = tab[i]; e != null; e = e.next) {
+          s.writeObject(e.key);
+          s.writeObject(e.value);
+        }
+      }
+    }
+
+    s.writeObject(null);
+    s.writeObject(null);
+  }
+
+  /**
+   * Reconstitute the <tt>ConcurrentHashMap</tt> 
+   * instance from a stream (i.e.,
+   * deserialize it).
+   */
+  private void readObject(java.io.ObjectInputStream s)
+    throws IOException, ClassNotFoundException  {
+    // Read in the threshold, loadfactor, and any hidden stuff
+    s.defaultReadObject();
+
+    int cap = s.readInt();
+    table = newTable(cap);
+    for (int i = 0; i < segments.length; ++i) 
+      segments[i] = new Segment();
+
+
+    // Read the keys and values, and put the mappings in the table
+    for (;;) {
+      Object key = s.readObject();
+      Object value = s.readObject();
+      if (key == null)
+        break;
+      put(key, value);
+    }
+  }
+}
diff --git a/benchmark/concurrent-hashmap/Makefile b/benchmark/concurrent-hashmap/Makefile
new file mode 100644 (file)
index 0000000..4c0a7dc
--- /dev/null
@@ -0,0 +1,27 @@
+include ../benchmarks.mk
+
+BENCH := hashmap
+NORMAL_TESTS := testcase1 testcase2 
+
+WILDCARD_TESTS := $(patsubst %, %_wildcard, $(NORMAL_TESTS))
+
+TESTS := $(NORMAL_TESTS) $(WILDCARD_TESTS)
+
+all: $(TESTS)
+
+$(WILDCARD_TESTS): CXXFLAGS += -DWILDCARD
+
+$(BENCH).o : $(BENCH).h
+       $(CXX) -o $@ $< $(CXXFLAGS) -c $(LDFLAGS)
+
+$(BENCH)_wildcard.o : $(BENCH)_wildcard.h
+       $(CXX) -o $@ $< $(CXXFLAGS) -c $(LDFLAGS)
+
+$(WILDCARD_TESTS): %_wildcard : %.cc $(BENCH)_wildcard.o 
+       $(CXX) -o $@ $< $(CXXFLAGS) $(LDFLAGS)
+
+$(NORMAL_TESTS): % : %.cc $(BENCH).o
+       $(CXX) -o $@ $< $(CXXFLAGS) $(LDFLAGS)
+
+clean:
+       rm -f *.o *.d $(TESTS)
diff --git a/benchmark/concurrent-hashmap/hashmap.h b/benchmark/concurrent-hashmap/hashmap.h
new file mode 100644 (file)
index 0000000..0d24925
--- /dev/null
@@ -0,0 +1,308 @@
+#ifndef _HASHMAP_H
+#define _HASHMAP_H
+
+#include <iostream>
+#include <atomic>
+#include "stdio.h" 
+//#include <common.h>
+#ifdef STANDALONE
+#include <assert.h>
+#define MODEL_ASSERT assert 
+#else
+#include <model-assert.h>
+#endif
+#include <stdlib.h>
+#include <mutex>
+
+#include "common.h"
+#include "sc_annotation.h"
+
+#define relaxed memory_order_relaxed
+#define release memory_order_release
+#define acquire memory_order_acquire
+#define acq_rel memory_order_acq_rel
+#define seq_cst memory_order_seq_cst
+
+using namespace std;
+
+/**
+       For the sake of simplicity, we do not use template but some toy structs to
+       represent the Key and Value.
+*/
+struct Key {
+       // Probably represent the coordinate (x, y, z)
+       int x;
+       int y;
+       int z;
+
+       int hashCode() {
+               return x + 31 * y + 31 * 31 * z;
+       }
+
+       bool equals(Key *other) {
+               if (!other)
+                       return false;
+               return x == other->x && y == other->y && z == other->z;
+       }
+
+       Key(int x, int y, int z) :
+               x(x),
+               y(y),
+               z(z)
+       {
+
+       }
+};
+
+struct Value {
+       // Probably represent the speed vector (vX, vY, vZ)
+       int vX;
+       int vY;
+       int vZ;
+
+       Value(int vX, int vY, int vZ) :
+               vX(vX),
+               vY(vY),
+               vZ(vZ)
+       {
+
+       }
+
+       bool equals(Value *other) {
+               if (!other)
+                       return false;
+               return vX == other->vX && vY == other->vY && vZ == other->vZ;
+       }
+};
+
+class Entry {
+       public:
+       Key *key;
+       atomic<Value*> value;
+       int hash;
+       atomic<Entry*> next;
+
+       Entry(int h, Key *k, Value *v, Entry *n) {
+               this->hash = h;
+               this->key = k;
+               this->value.store(v, relaxed);
+               this->next.store(n, relaxed);
+       }
+};
+
+class Segment {
+       public:
+       int count;
+       mutex segMutex;
+
+       void lock() {
+               segMutex.lock();
+       }
+
+       void unlock() {
+               segMutex.unlock();
+       }
+
+       Segment() {
+               this->count = 0;
+       }
+};
+
+class HashMap {
+       public:
+       atomic<Entry*> *table;
+
+       int capacity;
+       int size;
+
+       static const int CONCURRENCY_LEVEL = 16;
+
+       static const int SEGMENT_MASK = CONCURRENCY_LEVEL - 1;
+
+       Segment *segments[CONCURRENCY_LEVEL];
+
+       static const int DEFAULT_INITIAL_CAPACITY = 16;
+
+       // Not gonna consider resize now...
+       
+       HashMap() {
+               this->size = 0;
+               this->capacity = DEFAULT_INITIAL_CAPACITY;
+               this->table = new atomic<Entry*>[capacity];
+               for (int i = 0; i < capacity; i++) {
+                       atomic_init(&table[i], NULL);
+               }
+               for (int i = 0; i < CONCURRENCY_LEVEL; i++) {
+                       segments[i] = new Segment;
+               }
+       }
+
+       int hashKey(Key *x) {
+               int h = x->hashCode();
+               // Use logical right shift
+               unsigned int tmp = (unsigned int) h;
+               return ((h << 7) - h + (tmp >> 9) + (tmp >> 17));
+       }
+
+       bool eq(Key *x, Key *y) {
+               return x == y || x->equals(y);
+       }
+
+       Value* get(Key *key) {
+               MODEL_ASSERT (key);
+               int hash = hashKey(key);
+
+               // Try first without locking...
+               atomic<Entry*> *tab = table;
+               int index = hash & (capacity - 1);
+               atomic<Entry*> *first = &tab[index];
+               Entry *e;
+               Value *res = NULL;
+
+               // Should be a load acquire
+               // This load action here makes it problematic for the SC analysis, what
+               // we need to do is as follows: if the get() method ever acquires the
+               // lock, we ignore this operation for the SC analysis, and otherwise we
+               // take it into consideration
+               
+               SC_BEGIN();
+               Entry *firstPtr = first->load(acquire);
+               SC_END();
+
+               e = firstPtr;
+               while (e != NULL) {
+                       if (e->hash == hash && eq(key, e->key)) {
+                               res = e->value.load(seq_cst);
+                               if (res != NULL)
+                                       return res;
+                               else
+                                       break;
+                       }
+                       // Loading the next entry, this can be relaxed because the
+                       // synchronization has been established by the load of head
+                       e = e->next.load(relaxed);
+               }
+       
+               // Recheck under synch if key apparently not there or interference
+               Segment *seg = segments[hash & SEGMENT_MASK];
+               seg->lock(); // Critical region begins
+               // Not considering resize now, so ignore the reload of table...
+
+               // Synchronized by locking, no need to be load acquire
+               Entry *newFirstPtr = first->load(relaxed);
+               if (e != NULL || firstPtr != newFirstPtr) {
+                       e = newFirstPtr;
+                       while (e != NULL) {
+                               if (e->hash == hash && eq(key, e->key)) {
+                                       // Protected by lock, no need to be SC
+                                       res = e->value.load(relaxed);
+                                       seg->unlock(); // Critical region ends
+                                       return res;
+                               }
+                               // Synchronized by locking
+                               e = e->next.load(relaxed);
+                       }
+               }
+               seg->unlock(); // Critical region ends
+               return NULL;
+       }
+
+       Value* put(Key *key, Value *value) {
+               // Don't allow NULL key or value
+               MODEL_ASSERT (key && value);
+
+               int hash = hashKey(key);
+               Segment *seg = segments[hash & SEGMENT_MASK];
+               atomic<Entry*> *tab;
+
+               seg->lock(); // Critical region begins
+               tab = table;
+               int index = hash & (capacity - 1);
+
+               atomic<Entry*> *first = &tab[index];
+               Entry *e;
+               Value *oldValue = NULL;
+       
+               // The written of the entry is synchronized by locking
+               Entry *firstPtr = first->load(relaxed);
+               e = firstPtr;
+               while (e != NULL) {
+                       if (e->hash == hash && eq(key, e->key)) {
+                               // FIXME: This could be a relaxed (because locking synchronize
+                               // with the previous put())??  no need to be acquire
+                               oldValue = e->value.load(relaxed);
+                               e->value.store(value, seq_cst);
+                               seg->unlock(); // Don't forget to unlock before return
+                               return oldValue;
+                       }
+                       // Synchronized by locking
+                       e = e->next.load(relaxed);
+               }
+
+               // Add to front of list
+               Entry *newEntry = new Entry(hash, key, value, firstPtr);
+               // Publish the newEntry to others
+               first->store(newEntry, release);
+               seg->unlock(); // Critical region ends
+               return NULL;
+       }
+
+       Value* remove(Key *key, Value *value) {
+               MODEL_ASSERT (key);
+               int hash = hashKey(key);
+               Segment *seg = segments[hash & SEGMENT_MASK];
+               atomic<Entry*> *tab;
+
+               seg->lock(); // Critical region begins
+               tab = table;
+               int index = hash & (capacity - 1);
+
+               atomic<Entry*> *first = &tab[index];
+               Entry *e;
+               Value *oldValue = NULL;
+       
+               // The written of the entry is synchronized by locking
+               Entry *firstPtr = first->load(relaxed);
+               e = firstPtr;
+
+               while (true) {
+                       if (e != NULL) {
+                               seg->unlock(); // Don't forget to unlock
+                               return NULL;
+                       }
+                       if (e->hash == hash && eq(key, e->key))
+                               break;
+                       // Synchronized by locking
+                       e = e->next.load(relaxed);
+               }
+
+               // FIXME: This could be a relaxed (because locking synchronize
+               // with the previous put())?? No need to be acquire
+               oldValue = e->value.load(relaxed);
+               // If the value parameter is NULL, we will remove the entry anyway
+               if (value != NULL && value->equals(oldValue)) {
+                       seg->unlock();
+                       return NULL;
+               }
+
+               // Force the get() to grab the lock and retry
+               e->value.store(NULL, relaxed);
+
+               // The strategy to remove the entry is to keep the entries after the
+               // removed one and copy the ones before it
+               Entry *head = e->next.load(relaxed);
+               Entry *p;
+               p = first->load(relaxed);
+               while (p != e) {
+                       head = new Entry(p->hash, p->key, p->value.load(relaxed), head);
+                       p = p->next.load(relaxed);
+               }
+
+               // Publish the new head to readers 
+               first->store(head, release);
+               seg->unlock(); // Critical region ends
+               return oldValue;
+       }
+};
+
+#endif
diff --git a/benchmark/concurrent-hashmap/main.cc b/benchmark/concurrent-hashmap/main.cc
new file mode 100644 (file)
index 0000000..084230e
--- /dev/null
@@ -0,0 +1,75 @@
+#include <iostream>
+#include <threads.h>
+#include "hashmap.h"
+
+HashMap *table;
+
+
+void printKey(Key *key) {
+       if (key)
+               printf("pos = (%d, %d, %d)\n", key->x, key->y, key->z);
+       else
+               printf("pos = NULL\n");
+}
+
+void printValue(Value *value) {
+       if (value)
+               printf("velocity = (%d, %d, %d)\n", value->vX, value->vY, value->vZ);
+       else
+               printf("velocity = NULL\n");
+}
+
+// Key(3, 2, 6) & Key(1, 3, 3) are hashed to the same slot -> 4
+// Key(1, 1, 1) & Key(3, 2, 2) are hashed to the same slot -> 0
+// Key(2, 4, 1) & Key(3, 4, 2) are hashed to the same slot -> 3
+// Key(3, 4, 5) & Key(1, 4, 3) are hashed to the same slot -> 5
+
+
+void threadA(void *arg) {
+       Key *k1 = new Key(3, 2, 6);
+       Key *k2 = new Key(1, 1, 1);
+       Value *v1 = new Value(10, 10, 10);
+       Value *r1 = table->put(k1, v1);
+       //printValue(r1);
+       Value *r2 = table->get(k2);
+       //printf("Thrd A:\n");
+       printValue(r2);
+}
+
+void threadB(void *arg) {
+       Key *k1 = new Key(3, 2, 6);
+       Key *k2 = new Key(1, 1, 1);
+       Value *v2 = new Value(30, 40, 50);
+       Value *r3 = table->put(k2, v2);
+       //printValue(r3);
+       Value *r4 = table->get(k1);
+       printf("Thrd B:\n");
+       printValue(r4);
+}
+
+int user_main(int argc, char *argv[]) {
+       thrd_t t1, t2;
+
+       Key *k1 = new Key(1, 3, 3);
+       Key *k1_prime = new Key(3, 2, 6);
+       Key *k2 = new Key(3, 2, 2);
+       Key *k2_prime = new Key(1, 1, 1);
+       Value *v1 = new Value(111, 111, 111);
+       Value *v2 = new Value(222, 222, 222);
+
+       table = new HashMap;
+
+       printf("Key1: %d\n", table->hashKey(k1) % table->capacity);
+       printf("Key1': %d\n", table->hashKey(k1_prime) % table->capacity);
+       printf("Key2: %d\n", table->hashKey(k2) % table->capacity);
+       printf("Key2': %d\n", table->hashKey(k2_prime) % table->capacity);
+
+       thrd_create(&t1, threadA, NULL);
+       thrd_create(&t2, threadB, NULL);
+       thrd_join(t1);
+       thrd_join(t2);
+       
+       return 0;
+}
+
+
diff --git a/benchmark/concurrent-hashmap/note.txt b/benchmark/concurrent-hashmap/note.txt
new file mode 100644 (file)
index 0000000..f080a48
--- /dev/null
@@ -0,0 +1,17 @@
+#Non-SC:
+The following case can be non-SC.
+
+Thrd1                                          Thrd2
+put(k1, v1); // a                      put(k2, v2); // c
+get(k2); // b                          get(k1); // d
+
+When b and d both read the old head of the list (and they later grab the lock,
+making it the interface SC), it's non-SC because neither reads the updated
+value.
+
+Run testcase1 to make the store and load of value slot to be seq_cst.
+
+Then run testcase2 with "-o annotation" to get store and load of key slot to be
+release/acquire.
+
+0m0.015s + 0m0.000 = 0m0.015s 
index ce6fd06..e678378 100644 (file)
@@ -85,6 +85,8 @@ void init_queue(queue_t *q, int num_threads);
                # Only check the happens-before relationship according to the id of the
                # commit_point_set. For commit_point_set that has same ID, A -> B means
                # B happens after the previous A.
+       @Commutativity: Enqueue <-> Dequeue: _Method1.__RET__ == NULL 
+       @Commutativity: Enqueue <-> Dequeue: _Method1.q != _Method2.q 
        @End
 */
 
index 418c712..0d25b20 100644 (file)
@@ -1,5 +1,5 @@
 "preScanner.jj" is used to process the backslash sign at the end of a line
-(basically splce broken lines before really processing the specifications).
+(basically splice broken lines before really processing the specifications).
 
 "util.jj" is used to process some specific strings, such as the declaration of a
 function with templated types. It is designed to be used as a library funcions.
index 305eabf..62b098e 100644 (file)
                @DefineFunc:
        @Interface_cluster:
                ...
-       @Happens-before:
+       @Happens_before:
                ...
+       @Commutativity: // This is to define the admissibility condition
+               // Enq <-> Enq (_M1.q != _M2.q)
+               // Enq <-> Deq (_M1.q != _M2.q)
+               // Deq <-> Deq (_M1.q != _M2.q)
+               // Enq <-> Deq (_M1.q == _M2.q && _M2.__RET__ == NULL)
        @End
        
        b) Interface construct
@@ -154,6 +159,7 @@ import edu.uci.eecs.specCompiler.specExtraction.Construct;
 import edu.uci.eecs.specCompiler.specExtraction.GlobalConstruct;
 import edu.uci.eecs.specCompiler.specExtraction.InterfaceConstruct;
 import edu.uci.eecs.specCompiler.specExtraction.PotentialCPDefineConstruct;
+import edu.uci.eecs.specCompiler.specExtraction.CommutativityRule;
 import edu.uci.eecs.specCompiler.specExtraction.CPDefineConstruct;
 import edu.uci.eecs.specCompiler.specExtraction.CPDefineCheckConstruct;
 import edu.uci.eecs.specCompiler.specExtraction.CPClearConstruct;
@@ -374,6 +380,8 @@ SKIP : {
        <INTERFACE_CLUSTER: "@Interface_cluster:">
 |
        <HAPPENS_BEFORE: "@Happens_before:">
+|
+       <COMMUTATIVITY: "@Commutativity:">
 |
        <INTERFACE: "@Interface:">
 |
@@ -468,6 +476,8 @@ SKIP : {
        <CLOSE_BRACE: "}">
 |
        <HB_SYMBOL: "->">
+|
+       <COMMUTATIVITY_SYMBOL: "<->">
 |
        <COMMA: ",">
 |
@@ -977,6 +987,7 @@ GlobalConstruct Global_construct() :
                        { res = new GlobalConstruct(_file, _content.size(), code, options); }
                        (Interface_clusters(res))?
                        (Happens_before(res))?
+                       (Commutativity(res))?
                <END>
        {
                res.unfoldInterfaceCluster();
@@ -1067,6 +1078,29 @@ void Happens_before(GlobalConstruct inst) :
        )+
 }
 
+void Commutativity(GlobalConstruct inst) :
+{
+       String method1, method2, condition;
+       ArrayList<String> content;
+}
+{
+       {
+               content = new ArrayList<String>();
+       }
+
+       (
+       <COMMUTATIVITY>
+       method1 = <IDENTIFIER>.image  <COMMUTATIVITY_SYMBOL>
+       method2 = <IDENTIFIER>.image
+       <COLON>
+       content = C_CPP_CODE(null)
+       { condition = stringArray2String(content); }
+       {
+               inst.addCommutativityRule(method1, method2, condition);
+       }
+       )+
+}
+
 InterfaceConstruct Interface() :
 {
        InterfaceConstruct res;
diff --git a/note.txt b/note.txt
deleted file mode 100644 (file)
index b0fa4a5..0000000
--- a/note.txt
+++ /dev/null
@@ -1,19 +0,0 @@
-#1 Some metrics to show how difficult to write specifications for the
-benchmarks.
-ELOC --- Essential Lines of Code (Without counting blanks and comments)
-LOES --- Lines of Essential Specificaitons (Without counting the "/** @Begin" and "@End */")
-SDS --- Sequential Data Structure
-OP --- Ordering Points
-PS --- Pre/post-conditions and SideEffects
-
-Benchmark              ELOC    #API methods    #OP     LOES for SDS    LOES for PS     LOES for OP     LOES for Synchronization        total LOES      LOES (OP + Sync)
-Chase-Lev Deque                92      3               5       27              19              13              6                               65              19
-SPSC Queue             129     2               2       27              7               6               3                               43              9
-ReadCopyUpdate         26      2               2       3               5               6               3                               17              9
-Lockfree Hashtable     421     2               4       44              11              22              5                               82              27
-MCS Lock               151     2               4       3               6               10              1                               20              11
-MPMC Queue             65      4               8       0               0               32              5                               37              37
-M&S Queue              59      2               6       27              10              22              3                               62              25
-Linux RW Lock          90      6               11      6               21              28              10                              65              38
-
-Total                  1033    23              42      137             79              139             36                              391             175
index fcee3f1..84b3300 100644 (file)
@@ -288,14 +288,14 @@ public class CodeGenerator {
        public static void main(String[] argvs) {
                String homeDir = Environment.HOME_DIRECTORY;
 
-               File[] srcLinuxRWLocks = { new File(homeDir
-                               + "/benchmark/linuxrwlocks/linuxrwlocks.c") };
-
-               File[] srcHashtable = {
-                               new File(homeDir
-                                               + "/benchmark/cliffc-hashtable/cliffc_hashtable.h"),
-                               new File(homeDir + "/benchmark/cliffc-hashtable/main.cc") };
-
+//             File[] srcLinuxRWLocks = { new File(homeDir
+//                             + "/benchmark/linuxrwlocks/linuxrwlocks.c") };
+//
+//             File[] srcHashtable = {
+//                             new File(homeDir
+//                                             + "/benchmark/cliffc-hashtable/cliffc_hashtable.h"),
+//                             new File(homeDir + "/benchmark/cliffc-hashtable/main.cc") };
+//
                File[] srcMSQueue = {
                                new File(homeDir + "/benchmark/ms-queue/my_queue.c"),
                                new File(homeDir + "/benchmark/ms-queue/testcase.c"),
@@ -303,32 +303,35 @@ public class CodeGenerator {
                                new File(homeDir + "/benchmark/ms-queue/main.c"),
                                new File(homeDir + "/benchmark/ms-queue/my_queue.h") };
 
-               File[] srcRCU = { new File(homeDir
-                               + "/benchmark/read-copy-update/rcu.cc") };
-
-               File[] srcDeque = {
-                               new File(homeDir + "/benchmark/chase-lev-deque-bugfix/deque.c"),
-                               new File(homeDir + "/benchmark/chase-lev-deque-bugfix/main.c"),
-                               new File(homeDir + "/benchmark/chase-lev-deque-bugfix/testcase.c"),
-                               new File(homeDir + "/benchmark/chase-lev-deque-bugfix/deque.h") };
-
-               File[] srcMCSLock = {
-                               new File(homeDir + "/benchmark/mcs-lock/mcs-lock.cc"),
-                               new File(homeDir + "/benchmark/mcs-lock/mcs-lock.h") };
-
-               File[] srcSPSCQueue = {
-                               new File(homeDir + "/benchmark/spsc-bugfix/spsc-queue.cc"),
-                               new File(homeDir + "/benchmark/spsc-bugfix/eventcount.h"),
-                               new File(homeDir + "/benchmark/spsc-bugfix/queue.h") };
-
-               File[] srcMPMCQueue = {
-                               new File(homeDir + "/benchmark/mpmc-queue/mpmc-queue.h"),
-                               new File(homeDir + "/benchmark/mpmc-queue/mpmc-queue.cc") };
+//             File[] srcRCU = { new File(homeDir
+//                             + "/benchmark/read-copy-update/rcu.cc") };
+//             
+//             File[] srcTrylock = { new File(homeDir
+//                             + "/benchmark/trylock/trylock.c") };
+
+//             File[] srcDeque = {
+//                             new File(homeDir + "/benchmark/chase-lev-deque-bugfix/deque.c"),
+//                             new File(homeDir + "/benchmark/chase-lev-deque-bugfix/main.c"),
+//                             new File(homeDir + "/benchmark/chase-lev-deque-bugfix/testcase.c"),
+//                             new File(homeDir + "/benchmark/chase-lev-deque-bugfix/deque.h") };
+//
+//             File[] srcMCSLock = {
+//                             new File(homeDir + "/benchmark/mcs-lock/mcs-lock.cc"),
+//                             new File(homeDir + "/benchmark/mcs-lock/mcs-lock.h") };
+//
+//             File[] srcSPSCQueue = {
+//                             new File(homeDir + "/benchmark/spsc-bugfix/spsc-queue.cc"),
+//                             new File(homeDir + "/benchmark/spsc-bugfix/eventcount.h"),
+//                             new File(homeDir + "/benchmark/spsc-bugfix/queue.h") };
+//
+//             File[] srcMPMCQueue = {
+//                             new File(homeDir + "/benchmark/mpmc-queue/mpmc-queue.h"),
+//                             new File(homeDir + "/benchmark/mpmc-queue/mpmc-queue.cc") };
 //
 //             File[][] sources = { srcLinuxRWLocks,  srcMSQueue, srcRCU,
 //                             srcDeque, srcMCSLock, srcSPSCQueue, srcMPMCQueue, srcHashtable };
 
-                File[][] sources = {srcRCU };
+                File[][] sources = {srcMSQueue };
                // Compile all the benchmarks
                for (int i = 0; i < sources.length; i++) {
                        CodeGenerator gen = new CodeGenerator(sources[i]);
index 3d4583d..bb572c1 100644 (file)
@@ -10,6 +10,7 @@ import edu.uci.eecs.specCompiler.grammerParser.utilParser.ParseException;
 import edu.uci.eecs.specCompiler.specExtraction.CPClearConstruct;
 import edu.uci.eecs.specCompiler.specExtraction.CPDefineCheckConstruct;
 import edu.uci.eecs.specCompiler.specExtraction.CPDefineConstruct;
+import edu.uci.eecs.specCompiler.specExtraction.CommutativityRule;
 import edu.uci.eecs.specCompiler.specExtraction.ConditionalInterface;
 import edu.uci.eecs.specCompiler.specExtraction.Construct;
 import edu.uci.eecs.specCompiler.specExtraction.FunctionHeader;
@@ -65,6 +66,7 @@ public class CodeVariables {
 
        public static final String ANNO_INIT = "anno_init";
        public static final String ANNO_HB_INIT = "anno_hb_init";
+       public static final String ANNO_COMMUTATIVITY_RULE = "anno_commutativity_rule";
        public static final String ANNO_INTERFACE_BEGIN = "anno_interface_begin";
        public static final String ANNO_INTERFACE_END = "anno_interface_end";
        public static final String ANNO_POTENTIAL_CP_DEFINE = "anno_potential_cp_define";
@@ -417,9 +419,32 @@ public class CodeVariables {
                // Happens-before initialization rules
                // Should make it static
                newCode.add("static " + DECLARE(ANNO_HB_INIT + "**", "hb_init_table"));
+               
+               // Declare the Commutativity Rule table
+               newCode.add("static " + DECLARE(ANNO_COMMUTATIVITY_RULE + "**", "commutativity_rule_table"));
+               // Define the Commutativity Rule condition functions
+               ArrayList<CommutativityRule> rules = semantics.getGlobalConstruct().commutativityRules;
+               for (int i = 0; i < rules.size(); i++) {
+                       CommutativityRule rule = rules.get(i);
+                       String infoStructType1 = rule.method1 + "_info";
+                       String infoStructType2 = rule.method2 + "_info";
+                       String condition = rule.condition;
+                       
+                       // Declare
+                       
+                       // Replace the "_M1." and "_M2." with the actual info struct
+                       condition.replaceAll("_M1\\.", infoStructType1 + "->");
+                       condition.replaceAll("_M2\\.", infoStructType2 + "->");
+                       
+                       // Cast the "void*" type to the actual info type
+                       
+                       newCode.add(e)
+               }
+               
 
                newCode.add("");
                
+               // Beginning initialization
                // Define the __SPEC_INIT__ function to initialize user-defined
                // variables
                newCode.add(COMMENT("Initialization of sequential varialbes"));
@@ -437,6 +462,7 @@ public class CodeVariables {
                
                newCode.add(COMMENT("Define function for sequential code initialization"));
                newCode.add("inline static void __sequential_init() {");
+               
                // Init func_ptr_table
                newCode.add("\t" + COMMENT("Init func_ptr_table"));
                newCode.add("\t"
@@ -452,12 +478,19 @@ public class CodeVariables {
                                        + ASSIGN("func_ptr_table[2 * " + interfaceNum + " + 1]",
                                                        "(void*) &" + interfaceName + "_check_action"));
                }
+               
+               // Init Commutativity rules table
+               
+               
                // Init Happens-before rules table
                newCode.addAll(generateHBInitAnnotation(semantics));
+               
+               // Init Commutativity rules table
+               newCode.addAll(generateCommutativityAnnotation(semantics));
 
                // Pass init info, including function table info & HB rules
                newCode.add("\t"
-                               + COMMENT("Pass init info, including function table info & HB rules"));
+                               + COMMENT("Pass init info, including function table info & HB rules & Commutativity Rules"));
                String structName = "anno_init", anno = "init";
                newCode.add("\t" + STRUCT_NEW_DECLARE_DEFINE(ANNO_INIT, structName));
                newCode.add("\t"
@@ -473,6 +506,13 @@ public class CodeVariables {
                newCode.add("\t"
                                + ASSIGN_TO_PTR(structName, "hb_init_table_size",
                                                "HB_INIT_TABLE_SIZE"));
+               
+               newCode.add("\t"
+                               + ASSIGN_TO_PTR(structName, "commutativity_rule_table", "hb_init_table"));
+               newCode.add("\t"
+                               + ASSIGN_TO_PTR(structName, "hb_init_table_size",
+                                               "HB_INIT_TABLE_SIZE"));
+               
                newCode.add("\t" + STRUCT_NEW_DECLARE_DEFINE(SPEC_ANNOTATION, anno));
                newCode.add("\t" + ASSIGN_TO_PTR(anno, "type", SPEC_ANNO_TYPE_INIT));
                newCode.add("\t" + ASSIGN_TO_PTR(anno, "annotation", structName));
@@ -582,6 +622,31 @@ public class CodeVariables {
                return newCode;
        }
 
+       private static ArrayList<String> generateCommutativityAnnotation(
+                       SemanticsChecker semantics) {
+               ArrayList<String> newCode = new ArrayList<String>();
+               ArrayList<CommutativityRule> rules = semantics.getGlobalConstruct().commutativityRules;
+               for (CommutativityRule rule : rules) {
+
+               }
+
+               // Init commutativity_rule_table
+               newCode.add("\t" + COMMENT("Init commutativity_rule_table"));
+               newCode.add("\t"
+                               + ASSIGN("hb_init_table", "(" + ANNO_HB_INIT
+                                               + "**) malloc(sizeof(" + ANNO_HB_INIT + "*) * "
+                                               + hbConditionInitIdx + ")"));
+               // Define HB_INIT_TABLE_SIZE
+               newCode.add("\t"
+                               + DEFINE("HB_INIT_TABLE_SIZE",
+                                               Integer.toString(hbConditionInitIdx)));
+               for (int i = 0; i < hbConditionInitIdx; i++) {
+                       newCode.add("\t"
+                                       + ASSIGN("hb_init_table[" + i + "]", "hbConditionInit" + i));
+               }
+               return newCode;
+       }
+
        public static ArrayList<String> generateEntryPointInitCall() {
                ArrayList<String> newCode = new ArrayList<String>();
                newCode.add("\t" + "__sequential_init();");
diff --git a/src/edu/uci/eecs/specCompiler/specExtraction/CommutativityRule.java b/src/edu/uci/eecs/specCompiler/specExtraction/CommutativityRule.java
new file mode 100644 (file)
index 0000000..60ee385
--- /dev/null
@@ -0,0 +1,17 @@
+package edu.uci.eecs.specCompiler.specExtraction;
+
+public class CommutativityRule {
+       public final String method1, method2;
+       
+       public final String condition;
+       
+       public CommutativityRule(String m1, String m2, String condition) {
+               this.method1 = m1;
+               this.method2 = m2;
+               this.condition = condition;
+       }
+       
+       public String toString() {
+               return "@Commutativity: " + method1 + " <-> " + method2 + ": " + condition; 
+       }
+}
index 366dab7..499a710 100644 (file)
@@ -1,6 +1,7 @@
 package edu.uci.eecs.specCompiler.specExtraction;
 
 import java.io.File;
+import java.util.ArrayList;
 import java.util.HashMap;
 import java.util.HashSet;
 
@@ -9,6 +10,7 @@ public class GlobalConstruct extends Construct {
        private final HashMap<String, HashSet<ConditionalInterface>> interfaceCluster;
        private final HashMap<ConditionalInterface, HashSet<ConditionalInterface>> originalHBRelations;
        public final HashMap<ConditionalInterface, HashSet<ConditionalInterface>> hbRelations;
+       public final ArrayList<CommutativityRule> commutativityRules;
        public final HashMap<String, String> options;
 
        public GlobalConstruct(File file, int beginLineNum,
@@ -19,6 +21,7 @@ public class GlobalConstruct extends Construct {
                this.originalHBRelations = new HashMap<ConditionalInterface, HashSet<ConditionalInterface>>();
                this.hbRelations = new HashMap<ConditionalInterface, HashSet<ConditionalInterface>>();
                this.options = options;
+               this.commutativityRules = new ArrayList<CommutativityRule>();
        }
 
        public void addInterface2Cluster(String clusterName,
@@ -39,6 +42,13 @@ public class GlobalConstruct extends Construct {
                HashSet<ConditionalInterface> set = originalHBRelations.get(left);
                set.add(right);
        }
+       
+       public void addCommutativityRule(String method1, String method2, String condition) {
+               CommutativityRule rule = new CommutativityRule(method1, method2, condition);
+               if (!commutativityRules.contains(rule)) {
+                       commutativityRules.add(rule);
+               }
+       }
 
        private void addUnfoldedHBCondition(ConditionalInterface left,
                        ConditionalInterface right) {