Update JSR-166 to Revision 1.43

This is CVS HEAD as of Tue Mar 24 22:30:53 2015 UTC with
android specific patches applied. All android patches have
a clear "android-note" header.

- Most changes are documentation related.
- @hide tags have been applied to 1.8 APIs
- Atomic*Updater have been updated to use VMStack.* APIs.

bug: 20628776
bug: https://code.google.com/p/android/issues/detail?id=170073

(cherry picked from commit aa2ed9e105504f21641d919b410c692981cfe386)

Change-Id: Ie7ce1780eda837f3455e6aa365861886956c4063

54 files changed, 708 insertions, 457 deletions

diff --git a/luni/src/main/java/java/util/concurrent/AbstractExecutorService.java b/luni/src/main/java/java/util/concurrent/AbstractExecutorService.java
index 23e68bb..26649a8 100644
--- a/luni/src/main/java/java/util/concurrent/AbstractExecutorService.java
+++ b/luni/src/main/java/java/util/concurrent/AbstractExecutorService.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent;
+
 import java.util.*;
 
 /**
diff --git a/luni/src/main/java/java/util/concurrent/ArrayBlockingQueue.java b/luni/src/main/java/java/util/concurrent/ArrayBlockingQueue.java
index 3cfe6d5..9dca1b3 100644
--- a/luni/src/main/java/java/util/concurrent/ArrayBlockingQueue.java
+++ b/luni/src/main/java/java/util/concurrent/ArrayBlockingQueue.java
@@ -5,13 +5,15 @@
  */
 
 package java.util.concurrent;
-import java.util.concurrent.locks.Condition;
-import java.util.concurrent.locks.ReentrantLock;
+
+import java.lang.ref.WeakReference;
+import java.util.Arrays;
 import java.util.AbstractQueue;
 import java.util.Collection;
 import java.util.Iterator;
 import java.util.NoSuchElementException;
-import java.lang.ref.WeakReference;
+import java.util.concurrent.locks.Condition;
+import java.util.concurrent.locks.ReentrantLock;
 
 // BEGIN android-note
 // removed link to collections framework docs
@@ -46,7 +48,7 @@ import java.lang.ref.WeakReference;
  *
  * @since 1.5
  * @author Doug Lea
- * @param <E> the type of elements held in this collection
+ * @param <E> the type of elements held in this queue
  */
 public class ArrayBlockingQueue<E> extends AbstractQueue<E>
         implements BlockingQueue<E>, java.io.Serializable {
@@ -95,14 +97,7 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
     // Internal helper methods
 
     /**
-     * Circularly increment i.
-     */
-    final int inc(int i) {
-        return (++i == items.length) ? 0 : i;
-    }
-
-    /**
-     * Circularly decrement i.
+     * Circularly decrements array index i.
      */
     final int dec(int i) {
         return ((i == 0) ? items.length : i) - 1;
@@ -117,24 +112,15 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
     }
 
     /**
-     * Throws NullPointerException if argument is null.
-     *
-     * @param v the element
-     */
-    private static void checkNotNull(Object v) {
-        if (v == null)
-            throw new NullPointerException();
-    }
-
-    /**
      * Inserts element at current put position, advances, and signals.
      * Call only when holding lock.
      */
     private void enqueue(E x) {
         // assert lock.getHoldCount() == 1;
         // assert items[putIndex] == null;
+        final Object[] items = this.items;
         items[putIndex] = x;
-        putIndex = inc(putIndex);
+        if (++putIndex == items.length) putIndex = 0;
         count++;
         notEmpty.signal();
     }
@@ -150,7 +136,7 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
         @SuppressWarnings("unchecked")
         E x = (E) items[takeIndex];
         items[takeIndex] = null;
-        takeIndex = inc(takeIndex);
+        if (++takeIndex == items.length) takeIndex = 0;
         count--;
         if (itrs != null)
             itrs.elementDequeued();
@@ -171,7 +157,7 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
         if (removeIndex == takeIndex) {
             // removing front item; just advance
             items[takeIndex] = null;
-            takeIndex = inc(takeIndex);
+            if (++takeIndex == items.length) takeIndex = 0;
             count--;
             if (itrs != null)
                 itrs.elementDequeued();
@@ -179,17 +165,15 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
             // an "interior" remove
 
             // slide over all others up through putIndex.
-            final int putIndex = this.putIndex;
-            for (int i = removeIndex;;) {
-                int next = inc(i);
-                if (next != putIndex) {
-                    items[i] = items[next];
-                    i = next;
-                } else {
-                    items[i] = null;
-                    this.putIndex = i;
+            for (int i = removeIndex, putIndex = this.putIndex;;) {
+                int pred = i;
+                if (++i == items.length) i = 0;
+                if (i == putIndex) {
+                    items[pred] = null;
+                    this.putIndex = pred;
                     break;
                 }
+                items[pred] = items[i];
             }
             count--;
             if (itrs != null)
@@ -254,7 +238,7 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
             int i = 0;
             try {
                 for (E e : c) {
-                    checkNotNull(e);
+                    if (e == null) throw new NullPointerException();
                     items[i++] = e;
                 }
             } catch (ArrayIndexOutOfBoundsException ex) {
@@ -292,7 +276,7 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
      * @throws NullPointerException if the specified element is null
      */
     public boolean offer(E e) {
-        checkNotNull(e);
+        if (e == null) throw new NullPointerException();
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
@@ -315,7 +299,7 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
      * @throws NullPointerException {@inheritDoc}
      */
     public void put(E e) throws InterruptedException {
-        checkNotNull(e);
+        if (e == null) throw new NullPointerException();
         final ReentrantLock lock = this.lock;
         lock.lockInterruptibly();
         try {
@@ -338,7 +322,7 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
     public boolean offer(E e, long timeout, TimeUnit unit)
         throws InterruptedException {
 
-        checkNotNull(e);
+        if (e == null) throw new NullPointerException();
         long nanos = unit.toNanos(timeout);
         final ReentrantLock lock = this.lock;
         lock.lockInterruptibly();
@@ -462,11 +446,11 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
      */
     public boolean remove(Object o) {
         if (o == null) return false;
-        final Object[] items = this.items;
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
             if (count > 0) {
+                final Object[] items = this.items;
                 final int putIndex = this.putIndex;
                 int i = takeIndex;
                 do {
@@ -474,7 +458,8 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
                         removeAt(i);
                         return true;
                     }
-                } while ((i = inc(i)) != putIndex);
+                    if (++i == items.length) i = 0;
+                } while (i != putIndex);
             }
             return false;
         } finally {
@@ -492,17 +477,18 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
      */
     public boolean contains(Object o) {
         if (o == null) return false;
-        final Object[] items = this.items;
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
             if (count > 0) {
+                final Object[] items = this.items;
                 final int putIndex = this.putIndex;
                 int i = takeIndex;
                 do {
                     if (o.equals(items[i]))
                         return true;
-                } while ((i = inc(i)) != putIndex);
+                    if (++i == items.length) i = 0;
+                } while (i != putIndex);
             }
             return false;
         } finally {
@@ -524,19 +510,14 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
      * @return an array containing all of the elements in this queue
      */
     public Object[] toArray() {
-        final Object[] items = this.items;
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
-            final int count = this.count;
-            Object[] a = new Object[count];
-            int n = items.length - takeIndex;
-            if (count <= n) {
-                System.arraycopy(items, takeIndex, a, 0, count);
-            } else {
-                System.arraycopy(items, takeIndex, a, 0, n);
-                System.arraycopy(items, 0, a, n, count - n);
-            }
+            final Object[] items = this.items;
+            final int end = takeIndex + count;
+            final Object[] a = Arrays.copyOfRange(items, takeIndex, end);
+            if (end != putIndex)
+                System.arraycopy(items, 0, a, items.length - takeIndex, putIndex);
             return a;
         } finally {
             lock.unlock();
@@ -564,7 +545,7 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
      * The following code can be used to dump the queue into a newly
      * allocated array of {@code String}:
      *
-     *  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
+     * <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
      *
      * Note that {@code toArray(new Object[0])} is identical in function to
      * {@code toArray()}.
@@ -580,24 +561,22 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
      */
     @SuppressWarnings("unchecked")
     public <T> T[] toArray(T[] a) {
-        final Object[] items = this.items;
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
+            final Object[] items = this.items;
             final int count = this.count;
-            final int len = a.length;
-            if (len < count)
-                a = (T[])java.lang.reflect.Array.newInstance(
-                    a.getClass().getComponentType(), count);
-            int n = items.length - takeIndex;
-            if (count <= n)
-                System.arraycopy(items, takeIndex, a, 0, count);
-            else {
-                System.arraycopy(items, takeIndex, a, 0, n);
-                System.arraycopy(items, 0, a, n, count - n);
+            final int firstLeg = Math.min(items.length - takeIndex, count);
+            if (a.length < count) {
+                a = (T[]) Arrays.copyOfRange(items, takeIndex, takeIndex + count,
+                                             a.getClass());
+            } else {
+                System.arraycopy(items, takeIndex, a, 0, firstLeg);
+                if (a.length > count)
+                    a[count] = null;
             }
-            if (len > count)
-                a[count] = null;
+            if (firstLeg < count)
+                System.arraycopy(items, 0, a, firstLeg, putIndex);
             return a;
         } finally {
             lock.unlock();
@@ -612,14 +591,16 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
             if (k == 0)
                 return "[]";
 
+            final Object[] items = this.items;
             StringBuilder sb = new StringBuilder();
             sb.append('[');
-            for (int i = takeIndex; ; i = inc(i)) {
+            for (int i = takeIndex; ; ) {
                 Object e = items[i];
                 sb.append(e == this ? "(this Collection)" : e);
                 if (--k == 0)
                     return sb.append(']').toString();
                 sb.append(',').append(' ');
+                if (++i == items.length) i = 0;
             }
         } finally {
             lock.unlock();
@@ -641,7 +622,8 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
                 int i = takeIndex;
                 do {
                     items[i] = null;
-                } while ((i = inc(i)) != putIndex);
+                    if (++i == items.length) i = 0;
+                } while (i != putIndex);
                 takeIndex = putIndex;
                 count = 0;
                 if (itrs != null)
@@ -671,7 +653,7 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
      * @throws IllegalArgumentException      {@inheritDoc}
      */
     public int drainTo(Collection<? super E> c, int maxElements) {
-        checkNotNull(c);
+        if (c == null) throw new NullPointerException();
         if (c == this)
             throw new IllegalArgumentException();
         if (maxElements <= 0)
@@ -689,7 +671,7 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
                     E x = (E) items[take];
                     c.add(x);
                     items[take] = null;
-                    take = inc(take);
+                    if (++take == items.length) take = 0;
                     i++;
                 }
                 return n;
@@ -717,12 +699,8 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
      * Returns an iterator over the elements in this queue in proper sequence.
      * The elements will be returned in order from first (head) to last (tail).
      *
-     * <p>The returned iterator is a "weakly consistent" iterator that
-     * will never throw {@link java.util.ConcurrentModificationException
-     * ConcurrentModificationException}, and guarantees to traverse
-     * elements as they existed upon construction of the iterator, and
-     * may (but is not guaranteed to) reflect any modifications
-     * subsequent to construction.
+     * <p>The returned iterator is
+     * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
      *
      * @return an iterator over the elements in this queue in proper sequence
      */
@@ -796,13 +774,13 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
         }
 
         /** Incremented whenever takeIndex wraps around to 0 */
-        int cycles = 0;
+        int cycles;
 
         /** Linked list of weak iterator references */
         private Node head;
 
         /** Used to expunge stale iterators */
-        private Node sweeper = null;
+        private Node sweeper;
 
         private static final int SHORT_SWEEP_PROBES = 4;
         private static final int LONG_SWEEP_PROBES = 16;
@@ -910,7 +888,7 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
         }
 
         /**
-         * Called whenever an interior remove (not at takeIndex) occured.
+         * Called whenever an interior remove (not at takeIndex) occurred.
          *
          * Notifies all iterators, and expunges any that are now stale.
          */
@@ -1059,9 +1037,8 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
 
         private int incCursor(int index) {
             // assert lock.getHoldCount() == 1;
-            index = inc(index);
-            if (index == putIndex)
-                index = NONE;
+            if (++index == items.length) index = 0;
+            if (index == putIndex) index = NONE;
             return index;
         }
 
@@ -1268,7 +1245,7 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
         }
 
         /**
-         * Called whenever an interior remove (not at takeIndex) occured.
+         * Called whenever an interior remove (not at takeIndex) occurred.
          *
          * @return true if this iterator should be unlinked from itrs
          */
@@ -1277,17 +1254,18 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
             if (isDetached())
                 return true;
 
-            final int cycles = itrs.cycles;
             final int takeIndex = ArrayBlockingQueue.this.takeIndex;
-            final int prevCycles = this.prevCycles;
             final int prevTakeIndex = this.prevTakeIndex;
             final int len = items.length;
-            int cycleDiff = cycles - prevCycles;
-            if (removedIndex < takeIndex)
-                cycleDiff++;
+            // distance from prevTakeIndex to removedIndex
             final int removedDistance =
-                (cycleDiff * len) + (removedIndex - prevTakeIndex);
-            // assert removedDistance >= 0;
+                len * (itrs.cycles - this.prevCycles
+                       + ((removedIndex < takeIndex) ? 1 : 0))
+                + (removedIndex - prevTakeIndex);
+            // assert itrs.cycles - this.prevCycles >= 0;
+            // assert itrs.cycles - this.prevCycles <= 1;
+            // assert removedDistance > 0;
+            // assert removedIndex != takeIndex;
             int cursor = this.cursor;
             if (cursor >= 0) {
                 int x = distance(cursor, prevTakeIndex, len);
@@ -1316,7 +1294,7 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
                 else if (x > removedDistance)
                     this.nextIndex = nextIndex = dec(nextIndex);
             }
-            else if (cursor < 0 && nextIndex < 0 && lastRet < 0) {
+            if (cursor < 0 && nextIndex < 0 && lastRet < 0) {
                 this.prevTakeIndex = DETACHED;
                 return true;
             }
@@ -1354,4 +1332,5 @@ public class ArrayBlockingQueue<E> extends AbstractQueue<E>
 //                     "remainingCapacity()=" + remainingCapacity());
 //         }
     }
+
 }
diff --git a/luni/src/main/java/java/util/concurrent/BlockingDeque.java b/luni/src/main/java/java/util/concurrent/BlockingDeque.java
index 8a393ba..b1437cc 100644
--- a/luni/src/main/java/java/util/concurrent/BlockingDeque.java
+++ b/luni/src/main/java/java/util/concurrent/BlockingDeque.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent;
+
 import java.util.*;
 
 /**
@@ -23,6 +24,7 @@ import java.util.*;
  *
  * <p>
  * <table BORDER CELLPADDING=3 CELLSPACING=1>
+ * <caption>Summary of BlockingDeque methods</caption>
  *  <tr>
  *    <td ALIGN=CENTER COLSPAN = 5> <b>First Element (Head)</b></td>
  *  </tr>
@@ -98,6 +100,7 @@ import java.util.*;
  *
  * <p>
  * <table BORDER CELLPADDING=3 CELLSPACING=1>
+ * <caption>Comparison of BlockingQueue and BlockingDeque methods</caption>
  *  <tr>
  *    <td ALIGN=CENTER> <b>{@code BlockingQueue} Method</b></td>
  *    <td ALIGN=CENTER> <b>Equivalent {@code BlockingDeque} Method</b></td>
@@ -606,9 +609,10 @@ public interface BlockingDeque<E> extends BlockingQueue<E>, Deque<E> {
     // *** Stack methods ***
 
     /**
-     * Pushes an element onto the stack represented by this deque.  In other
-     * words, inserts the element at the front of this deque unless it would
-     * violate capacity restrictions.
+     * Pushes an element onto the stack represented by this deque (in other
+     * words, at the head of this deque) if it is possible to do so
+     * immediately without violating capacity restrictions, throwing an
+     * {@code IllegalStateException} if no space is currently available.
      *
      * <p>This method is equivalent to {@link #addFirst(Object) addFirst}.
      *
diff --git a/luni/src/main/java/java/util/concurrent/BlockingQueue.java b/luni/src/main/java/java/util/concurrent/BlockingQueue.java
index cc6d541..33d83b7 100644
--- a/luni/src/main/java/java/util/concurrent/BlockingQueue.java
+++ b/luni/src/main/java/java/util/concurrent/BlockingQueue.java
@@ -30,6 +30,7 @@ import java.util.Queue;
  *
  * <p>
  * <table BORDER CELLPADDING=3 CELLSPACING=1>
+ * <caption>Summary of BlockingQueue methods</caption>
  *  <tr>
  *    <td></td>
  *    <td ALIGN=CENTER><em>Throws exception</em></td>
diff --git a/luni/src/main/java/java/util/concurrent/ConcurrentHashMap.java b/luni/src/main/java/java/util/concurrent/ConcurrentHashMap.java
index ea3b1e9..3ed54cf 100644
--- a/luni/src/main/java/java/util/concurrent/ConcurrentHashMap.java
+++ b/luni/src/main/java/java/util/concurrent/ConcurrentHashMap.java
@@ -10,9 +10,9 @@ import java.io.ObjectStreamField;
 import java.io.Serializable;
 import java.lang.reflect.ParameterizedType;
 import java.lang.reflect.Type;
+import java.util.AbstractMap;
 import java.util.Arrays;
 import java.util.Collection;
-import java.util.Comparator;
 import java.util.ConcurrentModificationException;
 import java.util.Enumeration;
 import java.util.HashMap;
@@ -22,7 +22,6 @@ import java.util.Map;
 import java.util.NoSuchElementException;
 import java.util.Set;
 import java.util.concurrent.ConcurrentMap;
-import java.util.concurrent.ForkJoinPool;
 import java.util.concurrent.atomic.AtomicInteger;
 import java.util.concurrent.locks.LockSupport;
 import java.util.concurrent.locks.ReentrantLock;
@@ -99,7 +98,9 @@ import java.util.concurrent.locks.ReentrantLock;
  * @param <K> the type of keys maintained by this map
  * @param <V> the type of mapped values
  */
-public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
+// android-note: removed documentation about hidden newKeySet and newKeySet(int) APIs.
+// android-note: Added "extends AbstractMap<K, V>.
+public class ConcurrentHashMap<K,V> extends AbstractMap<K, V>
         implements ConcurrentMap<K,V>, Serializable {
     private static final long serialVersionUID = 7249069246763182397L;
 
@@ -208,14 +209,15 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
      * The table is resized when occupancy exceeds a percentage
      * threshold (nominally, 0.75, but see below).  Any thread
      * noticing an overfull bin may assist in resizing after the
-     * initiating thread allocates and sets up the replacement
-     * array. However, rather than stalling, these other threads may
-     * proceed with insertions etc.  The use of TreeBins shields us
-     * from the worst case effects of overfilling while resizes are in
+     * initiating thread allocates and sets up the replacement array.
+     * However, rather than stalling, these other threads may proceed
+     * with insertions etc.  The use of TreeBins shields us from the
+     * worst case effects of overfilling while resizes are in
      * progress.  Resizing proceeds by transferring bins, one by one,
-     * from the table to the next table. To enable concurrency, the
-     * next table must be (incrementally) prefilled with place-holders
-     * serving as reverse forwarders to the old table.  Because we are
+     * from the table to the next table. However, threads claim small
+     * blocks of indices to transfer (via field transferIndex) before
+     * doing so, reducing contention.  A generation stamp in field
+     * sizeCtl ensures that resizings do not overlap. Because we are
      * using power-of-two expansion, the elements from each bin must
      * either stay at same index, or move with a power of two
      * offset. We eliminate unnecessary node creation by catching
@@ -236,13 +238,19 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
      * locks, average aggregate waits become shorter as resizing
      * progresses.  The transfer operation must also ensure that all
      * accessible bins in both the old and new table are usable by any
-     * traversal.  This is arranged by proceeding from the last bin
-     * (table.length - 1) up towards the first.  Upon seeing a
-     * forwarding node, traversals (see class Traverser) arrange to
-     * move to the new table without revisiting nodes.  However, to
-     * ensure that no intervening nodes are skipped, bin splitting can
-     * only begin after the associated reverse-forwarders are in
-     * place.
+     * traversal.  This is arranged in part by proceeding from the
+     * last bin (table.length - 1) up towards the first.  Upon seeing
+     * a forwarding node, traversals (see class Traverser) arrange to
+     * move to the new table without revisiting nodes.  To ensure that
+     * no intervening nodes are skipped even when moved out of order,
+     * a stack (see class TableStack) is created on first encounter of
+     * a forwarding node during a traversal, to maintain its place if
+     * later processing the current table. The need for these
+     * save/restore mechanics is relatively rare, but when one
+     * forwarding node is encountered, typically many more will be.
+     * So Traversers use a simple caching scheme to avoid creating so
+     * many new TableStack nodes. (Thanks to Peter Levart for
+     * suggesting use of a stack here.)
      *
      * The traversal scheme also applies to partial traversals of
      * ranges of bins (via an alternate Traverser constructor)
@@ -274,16 +282,18 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
      * related operations (which is the main reason we cannot use
      * existing collections such as TreeMaps). TreeBins contain
      * Comparable elements, but may contain others, as well as
-     * elements that are Comparable but not necessarily Comparable
-     * for the same T, so we cannot invoke compareTo among them. To
-     * handle this, the tree is ordered primarily by hash value, then
-     * by Comparable.compareTo order if applicable.  On lookup at a
-     * node, if elements are not comparable or compare as 0 then both
-     * left and right children may need to be searched in the case of
-     * tied hash values. (This corresponds to the full list search
-     * that would be necessary if all elements were non-Comparable and
-     * had tied hashes.)  The red-black balancing code is updated from
-     * pre-jdk-collections
+     * elements that are Comparable but not necessarily Comparable for
+     * the same T, so we cannot invoke compareTo among them. To handle
+     * this, the tree is ordered primarily by hash value, then by
+     * Comparable.compareTo order if applicable.  On lookup at a node,
+     * if elements are not comparable or compare as 0 then both left
+     * and right children may need to be searched in the case of tied
+     * hash values. (This corresponds to the full list search that
+     * would be necessary if all elements were non-Comparable and had
+     * tied hashes.) On insertion, to keep a total ordering (or as
+     * close as is required here) across rebalancings, we compare
+     * classes and identityHashCodes as tie-breakers. The red-black
+     * balancing code is updated from pre-jdk-collections
      * (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
      * based in turn on Cormen, Leiserson, and Rivest "Introduction to
      * Algorithms" (CLR).
@@ -313,6 +323,10 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
      * unused "Segment" class that is instantiated in minimal form
      * only when serializing.
      *
+     * Also, solely for compatibility with previous versions of this
+     * class, it extends AbstractMap, even though all of its methods
+     * are overridden, so it is just useless baggage.
+     *
      * This file is organized to make things a little easier to follow
      * while reading than they might otherwise: First the main static
      * declarations and utilities, then fields, then main public
@@ -321,6 +335,7 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
      * bulk operations.
      */
 
+
     /* ---------------- Constants -------------- */
 
     /**
@@ -393,6 +408,23 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
      */
     private static final int MIN_TRANSFER_STRIDE = 16;
 
+    /**
+     * The number of bits used for generation stamp in sizeCtl.
+     * Must be at least 6 for 32bit arrays.
+     */
+    private static int RESIZE_STAMP_BITS = 16;
+
+    /**
+     * The maximum number of threads that can help resize.
+     * Must fit in 32 - RESIZE_STAMP_BITS bits.
+     */
+    private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
+
+    /**
+     * The bit shift for recording size stamp in sizeCtl.
+     */
+    private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
+
     /*
      * Encodings for Node hash fields. See above for explanation.
      */
@@ -504,7 +536,6 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
         return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
     }
 
-
     /**
      * Returns x's Class if it is of the form "class C implements
      * Comparable<C>", else null.
@@ -605,11 +636,6 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
     private transient volatile int transferIndex;
 
     /**
-     * The least available table index to split while resizing.
-     */
-    private transient volatile int transferOrigin;
-
-    /**
      * Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
      */
     private transient volatile int cellsBusy;
@@ -1035,8 +1061,8 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
      * reflect any modifications subsequent to construction.
      *
      * @return the set view
-     *
      */
+    // android-note : changed KeySetView<K,V> to Set<K> to maintain API compatibility.
     public Set<K> keySet() {
         KeySetView<K,V> ks;
         return (ks = keySet) != null ? ks : (keySet = new KeySetView<K,V>(this, null));
@@ -1209,9 +1235,10 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
             new Segment<?,?>[DEFAULT_CONCURRENCY_LEVEL];
         for (int i = 0; i < segments.length; ++i)
             segments[i] = new Segment<K,V>(LOAD_FACTOR);
-        s.putFields().put("segments", segments);
-        s.putFields().put("segmentShift", segmentShift);
-        s.putFields().put("segmentMask", segmentMask);
+        java.io.ObjectOutputStream.PutField streamFields = s.putFields();
+        streamFields.put("segments", segments);
+        streamFields.put("segmentShift", segmentShift);
+        streamFields.put("segmentMask", segmentMask);
         s.writeFields();
 
         Node<K,V>[] t;
@@ -1264,8 +1291,8 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
                 int sz = (int)size;
                 n = tableSizeFor(sz + (sz >>> 1) + 1);
             }
-            @SuppressWarnings({"rawtypes","unchecked"})
-                Node<K,V>[] tab = (Node<K,V>[])new Node[n];
+            @SuppressWarnings("unchecked")
+                Node<K,V>[] tab = (Node<K,V>[])new Node<?,?>[n];
             int mask = n - 1;
             long added = 0L;
             while (p != null) {
@@ -1377,9 +1404,13 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
 
     /**
      * Legacy method testing if some key maps into the specified value
-     * in this table.  This method is identical in functionality to
+     * in this table.
+     *
+     * This method is identical in functionality to
      * {@link #containsValue(Object)}, and exists solely to ensure
-     * full compatibility with class {@link java.util.Hashtable}.
+     * full compatibility with class {@link java.util.Hashtable},
+     * which supported this method prior to introduction of the
+     * Java Collections framework.
      *
      * @param  value a value to search for
      * @return {@code true} if and only if some key maps to the
@@ -1388,6 +1419,7 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
      *         {@code false} otherwise
      * @throws NullPointerException if the specified value is null
      */
+    // android-note : removed @deprecated tag from javadoc.
     public boolean contains(Object value) {
         // BEGIN android-note
         // removed deprecation
@@ -1442,6 +1474,7 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
      * Creates a new {@link Set} backed by a ConcurrentHashMap
      * from the given type to {@code Boolean.TRUE}.
      *
+     * @param <K> the element type of the returned set
      * @return the new set
      * @since 1.8
      *
@@ -1458,9 +1491,10 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
      *
      * @param initialCapacity The implementation performs internal
      * sizing to accommodate this many elements.
+     * @param <K> the element type of the returned set
+     * @return the new set
      * @throws IllegalArgumentException if the initial capacity of
      * elements is negative
-     * @return the new set
      * @since 1.8
      *
      * @hide
@@ -1483,7 +1517,7 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
      *
      * @hide
      */
-    public Set<K> keySet(V mappedValue) {
+    public KeySetView<K,V> keySet(V mappedValue) {
         if (mappedValue == null)
             throw new NullPointerException();
         return new KeySetView<K,V>(this, mappedValue);
@@ -1535,6 +1569,14 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
     /* ---------------- Table Initialization and Resizing -------------- */
 
     /**
+     * Returns the stamp bits for resizing a table of size n.
+     * Must be negative when shifted left by RESIZE_STAMP_SHIFT.
+     */
+    static final int resizeStamp(int n) {
+        return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
+    }
+
+    /**
      * Initializes table, using the size recorded in sizeCtl.
      */
     private final Node<K,V>[] initTable() {
@@ -1546,8 +1588,8 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
                 try {
                     if ((tab = table) == null || tab.length == 0) {
                         int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
-                        @SuppressWarnings({"rawtypes","unchecked"})
-                            Node<K,V>[] nt = (Node<K,V>[])new Node[n];
+                        @SuppressWarnings("unchecked")
+                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                         table = tab = nt;
                         sc = n - (n >>> 2);
                     }
@@ -1589,17 +1631,20 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
             s = sumCount();
         }
         if (check >= 0) {
-            Node<K,V>[] tab, nt; int sc;
+            Node<K,V>[] tab, nt; int n, sc;
             while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
-                   tab.length < MAXIMUM_CAPACITY) {
+                   (n = tab.length) < MAXIMUM_CAPACITY) {
+                int rs = resizeStamp(n);
                 if (sc < 0) {
-                    if (sc == -1 || transferIndex <= transferOrigin ||
-                        (nt = nextTable) == null)
+                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
+                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
+                        transferIndex <= 0)
                         break;
-                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
+                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                         transfer(tab, nt);
                 }
-                else if (U.compareAndSwapInt(this, SIZECTL, sc, -2))
+                else if (U.compareAndSwapInt(this, SIZECTL, sc,
+                                             (rs << RESIZE_STAMP_SHIFT) + 2))
                     transfer(tab, null);
                 s = sumCount();
             }
@@ -1611,12 +1656,19 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
      */
     final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
         Node<K,V>[] nextTab; int sc;
-        if ((f instanceof ForwardingNode) &&
+        if (tab != null && (f instanceof ForwardingNode) &&
             (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
-            if (nextTab == nextTable && tab == table &&
-                transferIndex > transferOrigin && (sc = sizeCtl) < -1 &&
-                U.compareAndSwapInt(this, SIZECTL, sc, sc - 1))
-                transfer(tab, nextTab);
+            int rs = resizeStamp(tab.length);
+            while (nextTab == nextTable && table == tab &&
+                   (sc = sizeCtl) < 0) {
+                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
+                    sc == rs + MAX_RESIZERS || transferIndex <= 0)
+                    break;
+                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
+                    transfer(tab, nextTab);
+                    break;
+                }
+            }
             return nextTab;
         }
         return table;
@@ -1638,8 +1690,8 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
                 if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                     try {
                         if (table == tab) {
-                            @SuppressWarnings({"rawtypes","unchecked"})
-                                Node<K,V>[] nt = (Node<K,V>[])new Node[n];
+                            @SuppressWarnings("unchecked")
+                            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                             table = nt;
                             sc = n - (n >>> 2);
                         }
@@ -1650,9 +1702,21 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
             }
             else if (c <= sc || n >= MAXIMUM_CAPACITY)
                 break;
-            else if (tab == table &&
-                     U.compareAndSwapInt(this, SIZECTL, sc, -2))
-                transfer(tab, null);
+            else if (tab == table) {
+                int rs = resizeStamp(n);
+                if (sc < 0) {
+                    Node<K,V>[] nt;
+                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
+                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
+                        transferIndex <= 0)
+                        break;
+                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
+                        transfer(tab, nt);
+                }
+                else if (U.compareAndSwapInt(this, SIZECTL, sc,
+                                             (rs << RESIZE_STAMP_SHIFT) + 2))
+                    transfer(tab, null);
+            }
         }
     }
 
@@ -1666,35 +1730,27 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
             stride = MIN_TRANSFER_STRIDE; // subdivide range
         if (nextTab == null) {            // initiating
             try {
-                @SuppressWarnings({"rawtypes","unchecked"})
-                    Node<K,V>[] nt = (Node<K,V>[])new Node[n << 1];
+                @SuppressWarnings("unchecked")
+                Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
                 nextTab = nt;
             } catch (Throwable ex) {      // try to cope with OOME
                 sizeCtl = Integer.MAX_VALUE;
                 return;
             }
             nextTable = nextTab;
-            transferOrigin = n;
             transferIndex = n;
-            ForwardingNode<K,V> rev = new ForwardingNode<K,V>(tab);
-            for (int k = n; k > 0;) {    // progressively reveal ready slots
-                int nextk = (k > stride) ? k - stride : 0;
-                for (int m = nextk; m < k; ++m)
-                    nextTab[m] = rev;
-                for (int m = n + nextk; m < n + k; ++m)
-                    nextTab[m] = rev;
-                U.putOrderedInt(this, TRANSFERORIGIN, k = nextk);
-            }
         }
         int nextn = nextTab.length;
         ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
         boolean advance = true;
+        boolean finishing = false; // to ensure sweep before committing nextTab
         for (int i = 0, bound = 0;;) {
-            int nextIndex, nextBound, fh; Node<K,V> f;
+            Node<K,V> f; int fh;
             while (advance) {
-                if (--i >= bound)
+                int nextIndex, nextBound;
+                if (--i >= bound || finishing)
                     advance = false;
-                else if ((nextIndex = transferIndex) <= transferOrigin) {
+                else if ((nextIndex = transferIndex) <= 0) {
                     i = -1;
                     advance = false;
                 }
@@ -1708,24 +1764,22 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
                 }
             }
             if (i < 0 || i >= n || i + n >= nextn) {
-                for (int sc;;) {
-                    if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, ++sc)) {
-                        if (sc == -1) {
-                            nextTable = null;
-                            table = nextTab;
-                            sizeCtl = (n << 1) - (n >>> 1);
-                        }
-                        return;
-                    }
+                int sc;
+                if (finishing) {
+                    nextTable = null;
+                    table = nextTab;
+                    sizeCtl = (n << 1) - (n >>> 1);
+                    return;
                 }
-            }
-            else if ((f = tabAt(tab, i)) == null) {
-                if (casTabAt(tab, i, null, fwd)) {
-                    setTabAt(nextTab, i, null);
-                    setTabAt(nextTab, i + n, null);
-                    advance = true;
+                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
+                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
+                        return;
+                    finishing = advance = true;
+                    i = n; // recheck before commit
                 }
             }
+            else if ((f = tabAt(tab, i)) == null)
+                advance = casTabAt(tab, i, null, fwd);
             else if ((fh = f.hash) == MOVED)
                 advance = true; // already processed
             else {
@@ -1757,6 +1811,10 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
                                 else
                                     hn = new Node<K,V>(ph, pk, pv, hn);
                             }
+                            setTabAt(nextTab, i, ln);
+                            setTabAt(nextTab, i + n, hn);
+                            setTabAt(tab, i, fwd);
+                            advance = true;
                         }
                         else if (f instanceof TreeBin) {
                             TreeBin<K,V> t = (TreeBin<K,V>)f;
@@ -1788,13 +1846,11 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
                                 (hc != 0) ? new TreeBin<K,V>(lo) : t;
                             hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                                 (lc != 0) ? new TreeBin<K,V>(hi) : t;
+                            setTabAt(nextTab, i, ln);
+                            setTabAt(nextTab, i + n, hn);
+                            setTabAt(tab, i, fwd);
+                            advance = true;
                         }
-                        else
-                            ln = hn = null;
-                        setTabAt(nextTab, i, ln);
-                        setTabAt(nextTab, i + n, hn);
-                        setTabAt(tab, i, fwd);
-                        advance = true;
                     }
                 }
             }
@@ -1810,12 +1866,9 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
     private final void treeifyBin(Node<K,V>[] tab, int index) {
         Node<K,V> b; int n, sc;
         if (tab != null) {
-            if ((n = tab.length) < MIN_TREEIFY_CAPACITY) {
-                if (tab == table && (sc = sizeCtl) >= 0 &&
-                    U.compareAndSwapInt(this, SIZECTL, sc, -2))
-                    transfer(tab, null);
-            }
-            else if ((b = tabAt(tab, index)) != null) {
+            if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
+                tryPresize(n << 1);
+            else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
                 synchronized (b) {
                     if (tabAt(tab, index) == b) {
                         TreeNode<K,V> hd = null, tl = null;
@@ -1881,7 +1934,7 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
         final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
             if (k != null) {
                 TreeNode<K,V> p = this;
-                do  {
+                do {
                     int ph, dir; K pk; TreeNode<K,V> q;
                     TreeNode<K,V> pl = p.left, pr = p.right;
                     if ((ph = p.hash) > h)
@@ -1890,25 +1943,25 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
                         p = pr;
                     else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
                         return p;
-                    else if (pl == null && pr == null)
-                        break;
+                    else if (pl == null)
+                        p = pr;
+                    else if (pr == null)
+                        p = pl;
                     else if ((kc != null ||
                               (kc = comparableClassFor(k)) != null) &&
                              (dir = compareComparables(kc, k, pk)) != 0)
                         p = (dir < 0) ? pl : pr;
-                    else if (pl == null)
-                        p = pr;
-                    else if (pr == null ||
-                             (q = pr.findTreeNode(h, k, kc)) == null)
-                        p = pl;
-                    else
+                    else if ((q = pr.findTreeNode(h, k, kc)) != null)
                         return q;
+                    else
+                        p = pl;
                 } while (p != null);
             }
             return null;
         }
     }
 
+
     /* ---------------- TreeBins -------------- */
 
     /**
@@ -1929,6 +1982,23 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
         static final int READER = 4; // increment value for setting read lock
 
         /**
+         * Tie-breaking utility for ordering insertions when equal
+         * hashCodes and non-comparable. We don't require a total
+         * order, just a consistent insertion rule to maintain
+         * equivalence across rebalancings. Tie-breaking further than
+         * necessary simplifies testing a bit.
+         */
+        static int tieBreakOrder(Object a, Object b) {
+            int d;
+            if (a == null || b == null ||
+                (d = a.getClass().getName().
+                 compareTo(b.getClass().getName())) == 0)
+                d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
+                     -1 : 1);
+            return d;
+        }
+
+        /**
          * Creates bin with initial set of nodes headed by b.
          */
         TreeBin(TreeNode<K,V> b) {
@@ -1944,21 +2014,21 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
                     r = x;
                 }
                 else {
-                    Object key = x.key;
-                    int hash = x.hash;
+                    K k = x.key;
+                    int h = x.hash;
                     Class<?> kc = null;
                     for (TreeNode<K,V> p = r;;) {
                         int dir, ph;
-                        if ((ph = p.hash) > hash)
+                        K pk = p.key;
+                        if ((ph = p.hash) > h)
                             dir = -1;
-                        else if (ph < hash)
+                        else if (ph < h)
                             dir = 1;
-                        else if ((kc != null ||
-                                  (kc = comparableClassFor(key)) != null))
-                            dir = compareComparables(kc, key, p.key);
-                        else
-                            dir = 0;
-                        TreeNode<K,V> xp = p;
+                        else if ((kc == null &&
+                                  (kc = comparableClassFor(k)) == null) ||
+                                 (dir = compareComparables(kc, k, pk)) == 0)
+                            dir = tieBreakOrder(k, pk);
+                            TreeNode<K,V> xp = p;
                         if ((p = (dir <= 0) ? p.left : p.right) == null) {
                             x.parent = xp;
                             if (dir <= 0)
@@ -1972,6 +2042,7 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
                 }
             }
             this.root = r;
+            assert checkInvariants(root);
         }
 
         /**
@@ -1995,7 +2066,7 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
         private final void contendedLock() {
             boolean waiting = false;
             for (int s;;) {
-                if (((s = lockState) & WRITER) == 0) {
+                if (((s = lockState) & ~WAITER) == 0) {
                     if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
                         if (waiting)
                             waiter = null;
@@ -2020,12 +2091,13 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
          */
         final Node<K,V> find(int h, Object k) {
             if (k != null) {
-                for (Node<K,V> e = first; e != null; e = e.next) {
+                for (Node<K,V> e = first; e != null; ) {
                     int s; K ek;
                     if (((s = lockState) & (WAITER|WRITER)) != 0) {
                         if (e.hash == h &&
                             ((ek = e.key) == k || (ek != null && k.equals(ek))))
                             return e;
+                        e = e.next;
                     }
                     else if (U.compareAndSwapInt(this, LOCKSTATE, s,
                                                  s + READER)) {
@@ -2054,10 +2126,15 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
          * Finds or adds a node.
          * @return null if added
          */
+        /**
+         * Finds or adds a node.
+         * @return null if added
+         */
         final TreeNode<K,V> putTreeVal(int h, K k, V v) {
             Class<?> kc = null;
+            boolean searched = false;
             for (TreeNode<K,V> p = root;;) {
-                int dir, ph; K pk; TreeNode<K,V> q, pr;
+                int dir, ph; K pk;
                 if (p == null) {
                     first = root = new TreeNode<K,V>(h, k, v, null, null);
                     break;
@@ -2071,21 +2148,25 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
                 else if ((kc == null &&
                           (kc = comparableClassFor(k)) == null) ||
                          (dir = compareComparables(kc, k, pk)) == 0) {
-                    if (p.left == null)
-                        dir = 1;
-                    else if ((pr = p.right) == null ||
-                             (q = pr.findTreeNode(h, k, kc)) == null)
-                        dir = -1;
-                    else
-                        return q;
+                    if (!searched) {
+                        TreeNode<K,V> q, ch;
+                        searched = true;
+                        if (((ch = p.left) != null &&
+                             (q = ch.findTreeNode(h, k, kc)) != null) ||
+                            ((ch = p.right) != null &&
+                             (q = ch.findTreeNode(h, k, kc)) != null))
+                            return q;
+                    }
+                    dir = tieBreakOrder(k, pk);
                 }
+
                 TreeNode<K,V> xp = p;
-                if ((p = (dir < 0) ? p.left : p.right) == null) {
+                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                     TreeNode<K,V> x, f = first;
                     first = x = new TreeNode<K,V>(h, k, v, f, xp);
                     if (f != null)
                         f.prev = x;
-                    if (dir < 0)
+                    if (dir <= 0)
                         xp.left = x;
                     else
                         xp.right = x;
@@ -2308,7 +2389,7 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
 
         static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {
-            for (TreeNode<K,V> xp, xpl, xpr;;)  {
+            for (TreeNode<K,V> xp, xpl, xpr;;) {
                 if (x == null || x == root)
                     return root;
                 else if ((xp = x.parent) == null) {
@@ -2440,8 +2521,20 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
     /* ----------------Table Traversal -------------- */
 
     /**
+     * Records the table, its length, and current traversal index for a
+     * traverser that must process a region of a forwarded table before
+     * proceeding with current table.
+     */
+    static final class TableStack<K,V> {
+        int length;
+        int index;
+        Node<K,V>[] tab;
+        TableStack<K,V> next;
+    }
+
+    /**
      * Encapsulates traversal for methods such as containsValue; also
-     * serves as a base class for other iterators.
+     * serves as a base class for other iterators and spliterators.
      *
      * Method advance visits once each still-valid node that was
      * reachable upon iterator construction. It might miss some that
@@ -2463,6 +2556,7 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
     static class Traverser<K,V> {
         Node<K,V>[] tab;        // current table; updated if resized
         Node<K,V> next;         // the next entry to use
+        TableStack<K,V> stack, spare; // to save/restore on ForwardingNodes
         int index;              // index of bin to use next
         int baseIndex;          // current index of initial table
         int baseLimit;          // index bound for initial table
@@ -2484,16 +2578,17 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
             if ((e = next) != null)
                 e = e.next;
             for (;;) {
-                Node<K,V>[] t; int i, n; K ek;  // must use locals in checks
+                Node<K,V>[] t; int i, n;  // must use locals in checks
                 if (e != null)
                     return next = e;
                 if (baseIndex >= baseLimit || (t = tab) == null ||
                     (n = t.length) <= (i = index) || i < 0)
                     return next = null;
-                if ((e = tabAt(t, index)) != null && e.hash < 0) {
+                if ((e = tabAt(t, i)) != null && e.hash < 0) {
                     if (e instanceof ForwardingNode) {
                         tab = ((ForwardingNode<K,V>)e).nextTable;
                         e = null;
+                        pushState(t, i, n);
                         continue;
                     }
                     else if (e instanceof TreeBin)
@@ -2501,9 +2596,48 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
                     else
                         e = null;
                 }
-                if ((index += baseSize) >= n)
-                    index = ++baseIndex;    // visit upper slots if present
+                if (stack != null)
+                    recoverState(n);
+                else if ((index = i + baseSize) >= n)
+                    index = ++baseIndex; // visit upper slots if present
+            }
+        }
+
+        /**
+         * Saves traversal state upon encountering a forwarding node.
+         */
+        private void pushState(Node<K,V>[] t, int i, int n) {
+            TableStack<K,V> s = spare;  // reuse if possible
+            if (s != null)
+                spare = s.next;
+            else
+                s = new TableStack<K,V>();
+            s.tab = t;
+            s.length = n;
+            s.index = i;
+            s.next = stack;
+            stack = s;
+        }
+
+        /**
+         * Possibly pops traversal state.
+         *
+         * @param n length of current table
+         */
+        private void recoverState(int n) {
+            TableStack<K,V> s; int len;
+            while ((s = stack) != null && (index += (len = s.length)) >= n) {
+                n = len;
+                index = s.index;
+                tab = s.tab;
+                s.tab = null;
+                TableStack<K,V> next = s.next;
+                s.next = spare; // save for reuse
+                stack = next;
+                spare = s;
             }
+            if (s == null && (index += baseSize) >= n)
+                index = ++baseIndex;
         }
     }
 
@@ -2639,7 +2773,6 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
 
     /**
      * Base class for views.
-     *
      */
     abstract static class CollectionView<K,V,E>
         implements Collection<E>, java.io.Serializable {
@@ -2797,13 +2930,12 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
      * common value.  This class cannot be directly instantiated.
      * See {@link #keySet() keySet()},
      * {@link #keySet(Object) keySet(V)},
-     * {@link #newKeySet() newKeySet()},
-     * {@link #newKeySet(int) newKeySet(int)}.
      *
      * @since 1.8
      *
      * @hide
      */
+    // android-note: removed references to hidden APIs.
     public static class KeySetView<K,V> extends CollectionView<K,V,K>
         implements Set<K>, java.io.Serializable {
         private static final long serialVersionUID = 7249069246763182397L;
@@ -3162,7 +3294,6 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
     private static final sun.misc.Unsafe U;
     private static final long SIZECTL;
     private static final long TRANSFERINDEX;
-    private static final long TRANSFERORIGIN;
     private static final long BASECOUNT;
     private static final long CELLSBUSY;
     private static final long CELLVALUE;
@@ -3177,8 +3308,6 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
                 (k.getDeclaredField("sizeCtl"));
             TRANSFERINDEX = U.objectFieldOffset
                 (k.getDeclaredField("transferIndex"));
-            TRANSFERORIGIN = U.objectFieldOffset
-                (k.getDeclaredField("transferOrigin"));
             BASECOUNT = U.objectFieldOffset
                 (k.getDeclaredField("baseCount"));
             CELLSBUSY = U.objectFieldOffset
@@ -3195,6 +3324,10 @@ public class ConcurrentHashMap<K,V> extends java.util.AbstractMap<K,V>
         } catch (Exception e) {
             throw new Error(e);
         }
+
+        // Reduce the risk of rare disastrous classloading in first call to
+        // LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
+        Class<?> ensureLoaded = LockSupport.class;
     }
 
 }
diff --git a/luni/src/main/java/java/util/concurrent/ConcurrentLinkedQueue.java b/luni/src/main/java/java/util/concurrent/ConcurrentLinkedQueue.java
index b39a533..9010cbe 100644
--- a/luni/src/main/java/java/util/concurrent/ConcurrentLinkedQueue.java
+++ b/luni/src/main/java/java/util/concurrent/ConcurrentLinkedQueue.java
@@ -32,9 +32,9 @@ import java.util.Queue;
  * does not permit the use of {@code null} elements.
  *
  * <p>This implementation employs an efficient <em>non-blocking</em>
- * algorithm based on one described in <a
- * href="http://www.cs.rochester.edu/u/michael/PODC96.html"> Simple,
- * Fast, and Practical Non-Blocking and Blocking Concurrent Queue
+ * algorithm based on one described in
+ * <a href="http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf">
+ * Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue
  * Algorithms</a> by Maged M. Michael and Michael L. Scott.
  *
  * <p>Iterators are <i>weakly consistent</i>, returning elements
diff --git a/luni/src/main/java/java/util/concurrent/ConcurrentMap.java b/luni/src/main/java/java/util/concurrent/ConcurrentMap.java
index 27feeb2..1391f04 100644
--- a/luni/src/main/java/java/util/concurrent/ConcurrentMap.java
+++ b/luni/src/main/java/java/util/concurrent/ConcurrentMap.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent;
+
 import java.util.Map;
 
 // BEGIN android-note
diff --git a/luni/src/main/java/java/util/concurrent/ConcurrentNavigableMap.java b/luni/src/main/java/java/util/concurrent/ConcurrentNavigableMap.java
index e87fbee..17890ff 100644
--- a/luni/src/main/java/java/util/concurrent/ConcurrentNavigableMap.java
+++ b/luni/src/main/java/java/util/concurrent/ConcurrentNavigableMap.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent;
+
 import java.util.*;
 
 // BEGIN android-note
diff --git a/luni/src/main/java/java/util/concurrent/ConcurrentSkipListMap.java b/luni/src/main/java/java/util/concurrent/ConcurrentSkipListMap.java
index 4a76104..0e8b64a 100644
--- a/luni/src/main/java/java/util/concurrent/ConcurrentSkipListMap.java
+++ b/luni/src/main/java/java/util/concurrent/ConcurrentSkipListMap.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent;
+
 import java.util.*;
 
 // BEGIN android-note
@@ -215,7 +216,7 @@ public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
      * highly contended cases.
      *
      * Unlike most skip-list implementations, index insertion and
-     * deletion here require a separate traversal pass occuring after
+     * deletion here require a separate traversal pass occurring after
      * the base-level action, to add or remove index nodes.  This adds
      * to single-threaded overhead, but improves contended
      * multithreaded performance by narrowing interference windows,
@@ -2358,8 +2359,8 @@ public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
     }
 
     static final class Values<E> extends AbstractCollection<E> {
-        private final ConcurrentNavigableMap<?, E> m;
-        Values(ConcurrentNavigableMap<?, E> map) {
+        private final ConcurrentNavigableMap<?,E> m;
+        Values(ConcurrentNavigableMap<?,E> map) {
             m = map;
         }
         public Iterator<E> iterator() {
@@ -2566,7 +2567,7 @@ public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
         }
 
         /**
-         * Returns lowest absolute key (ignoring directonality).
+         * Returns lowest absolute key (ignoring directionality).
          */
         private K lowestKey() {
             ConcurrentSkipListMap.Node<K,V> n = loNode();
@@ -2577,7 +2578,7 @@ public class ConcurrentSkipListMap<K,V> extends AbstractMap<K,V>
         }
 
         /**
-         * Returns highest absolute key (ignoring directonality).
+         * Returns highest absolute key (ignoring directionality).
          */
         private K highestKey() {
             ConcurrentSkipListMap.Node<K,V> n = hiNode();
diff --git a/luni/src/main/java/java/util/concurrent/ConcurrentSkipListSet.java b/luni/src/main/java/java/util/concurrent/ConcurrentSkipListSet.java
index f1402b6..13f1a43 100644
--- a/luni/src/main/java/java/util/concurrent/ConcurrentSkipListSet.java
+++ b/luni/src/main/java/java/util/concurrent/ConcurrentSkipListSet.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent;
+
 import java.util.*;
 
 // BEGIN android-note
diff --git a/luni/src/main/java/java/util/concurrent/CopyOnWriteArraySet.java b/luni/src/main/java/java/util/concurrent/CopyOnWriteArraySet.java
index 6fa8feb..347ed14 100644
--- a/luni/src/main/java/java/util/concurrent/CopyOnWriteArraySet.java
+++ b/luni/src/main/java/java/util/concurrent/CopyOnWriteArraySet.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent;
+
 import java.util.*;
 
 // BEGIN android-note
diff --git a/luni/src/main/java/java/util/concurrent/CountDownLatch.java b/luni/src/main/java/java/util/concurrent/CountDownLatch.java
index fe0fa65..77093f7 100644
--- a/luni/src/main/java/java/util/concurrent/CountDownLatch.java
+++ b/luni/src/main/java/java/util/concurrent/CountDownLatch.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent;
+
 import java.util.concurrent.locks.AbstractQueuedSynchronizer;
 
 /**
diff --git a/luni/src/main/java/java/util/concurrent/CountedCompleter.java b/luni/src/main/java/java/util/concurrent/CountedCompleter.java
index d5f794e..b868037 100644
--- a/luni/src/main/java/java/util/concurrent/CountedCompleter.java
+++ b/luni/src/main/java/java/util/concurrent/CountedCompleter.java
@@ -686,7 +686,7 @@ public abstract class CountedCompleter<T> extends ForkJoinTask<T> {
     }
 
     /**
-     * Returns the result of the computation. By default
+     * Returns the result of the computation.  By default,
      * returns {@code null}, which is appropriate for {@code Void}
      * actions, but in other cases should be overridden, almost
      * always to return a field or function of a field that
diff --git a/luni/src/main/java/java/util/concurrent/CyclicBarrier.java b/luni/src/main/java/java/util/concurrent/CyclicBarrier.java
index e1a7bee..d698501 100644
--- a/luni/src/main/java/java/util/concurrent/CyclicBarrier.java
+++ b/luni/src/main/java/java/util/concurrent/CyclicBarrier.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent;
+
 import java.util.concurrent.locks.Condition;
 import java.util.concurrent.locks.ReentrantLock;
 
@@ -125,7 +126,7 @@ public class CyclicBarrier {
     private final Condition trip = lock.newCondition();
     /** The number of parties */
     private final int parties;
-    /* The command to run when tripped */
+    /** The command to run when tripped */
     private final Runnable barrierCommand;
     /** The current generation */
     private Generation generation = new Generation();
diff --git a/luni/src/main/java/java/util/concurrent/DelayQueue.java b/luni/src/main/java/java/util/concurrent/DelayQueue.java
index 945249e..e4a715e 100644
--- a/luni/src/main/java/java/util/concurrent/DelayQueue.java
+++ b/luni/src/main/java/java/util/concurrent/DelayQueue.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent;
+
 import static java.util.concurrent.TimeUnit.NANOSECONDS;
 import java.util.concurrent.locks.Condition;
 import java.util.concurrent.locks.ReentrantLock;
@@ -60,7 +61,7 @@ public class DelayQueue<E extends Delayed> extends AbstractQueue<E>
      * signalled.  So waiting threads must be prepared to acquire
      * and lose leadership while waiting.
      */
-    private Thread leader = null;
+    private Thread leader;
 
     /**
      * Condition signalled when a newer element becomes available
diff --git a/luni/src/main/java/java/util/concurrent/Exchanger.java b/luni/src/main/java/java/util/concurrent/Exchanger.java
index 01d5960..60871b4 100644
--- a/luni/src/main/java/java/util/concurrent/Exchanger.java
+++ b/luni/src/main/java/java/util/concurrent/Exchanger.java
@@ -6,9 +6,6 @@
  */
 
 package java.util.concurrent;
-import java.util.concurrent.atomic.AtomicInteger;
-import java.util.concurrent.atomic.AtomicReference;
-import java.util.concurrent.locks.LockSupport;
 
 /**
  * A synchronization point at which threads can pair and swap elements
diff --git a/luni/src/main/java/java/util/concurrent/Executor.java b/luni/src/main/java/java/util/concurrent/Executor.java
index f55209a..095ebfc 100644
--- a/luni/src/main/java/java/util/concurrent/Executor.java
+++ b/luni/src/main/java/java/util/concurrent/Executor.java
@@ -12,7 +12,7 @@ package java.util.concurrent;
  * mechanics of how each task will be run, including details of thread
  * use, scheduling, etc.  An {@code Executor} is normally used
  * instead of explicitly creating threads. For example, rather than
- * invoking {@code new Thread(new(RunnableTask())).start()} for each
+ * invoking {@code new Thread(new RunnableTask()).start()} for each
  * of a set of tasks, you might use:
  *
  * <pre>
@@ -52,7 +52,7 @@ package java.util.concurrent;
  *
  *  <pre> {@code
  * class SerialExecutor implements Executor {
- *   final Queue<Runnable> tasks = new ArrayDeque<Runnable>();
+ *   final Queue<Runnable> tasks = new ArrayDeque<>();
  *   final Executor executor;
  *   Runnable active;
  *
@@ -61,7 +61,7 @@ package java.util.concurrent;
  *   }
  *
  *   public synchronized void execute(final Runnable r) {
- *     tasks.offer(new Runnable() {
+ *     tasks.add(new Runnable() {
  *       public void run() {
  *         try {
  *           r.run();
diff --git a/luni/src/main/java/java/util/concurrent/ExecutorCompletionService.java b/luni/src/main/java/java/util/concurrent/ExecutorCompletionService.java
index c0d6006..9514246 100644
--- a/luni/src/main/java/java/util/concurrent/ExecutorCompletionService.java
+++ b/luni/src/main/java/java/util/concurrent/ExecutorCompletionService.java
@@ -132,7 +132,7 @@ public class ExecutorCompletionService<V> implements CompletionService<V> {
      * @param completionQueue the queue to use as the completion queue
      *        normally one dedicated for use by this service. This
      *        queue is treated as unbounded -- failed attempted
-     *        {@code Queue.add} operations for completed taskes cause
+     *        {@code Queue.add} operations for completed tasks cause
      *        them not to be retrievable.
      * @throws NullPointerException if executor or completionQueue are {@code null}
      */
diff --git a/luni/src/main/java/java/util/concurrent/ExecutorService.java b/luni/src/main/java/java/util/concurrent/ExecutorService.java
index 4599f59..2173529 100644
--- a/luni/src/main/java/java/util/concurrent/ExecutorService.java
+++ b/luni/src/main/java/java/util/concurrent/ExecutorService.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent;
+
 import java.util.List;
 import java.util.Collection;
 
@@ -29,8 +30,8 @@ import java.util.Collection;
  * reclamation of its resources.
  *
  * <p>Method {@code submit} extends base method {@link
- * Executor#execute} by creating and returning a {@link Future} that
- * can be used to cancel execution and/or wait for completion.
+ * Executor#execute(Runnable)} by creating and returning a {@link Future}
+ * that can be used to cancel execution and/or wait for completion.
  * Methods {@code invokeAny} and {@code invokeAll} perform the most
  * commonly useful forms of bulk execution, executing a collection of
  * tasks and then waiting for at least one, or all, to
diff --git a/luni/src/main/java/java/util/concurrent/Executors.java b/luni/src/main/java/java/util/concurrent/Executors.java
index 53c68fc..8731372 100644
--- a/luni/src/main/java/java/util/concurrent/Executors.java
+++ b/luni/src/main/java/java/util/concurrent/Executors.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent;
+
 import java.util.*;
 import java.util.concurrent.atomic.AtomicInteger;
 import java.security.AccessControlContext;
diff --git a/luni/src/main/java/java/util/concurrent/ForkJoinPool.java b/luni/src/main/java/java/util/concurrent/ForkJoinPool.java
index 9448616..5bcac28 100644
--- a/luni/src/main/java/java/util/concurrent/ForkJoinPool.java
+++ b/luni/src/main/java/java/util/concurrent/ForkJoinPool.java
@@ -12,14 +12,6 @@ import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.List;
-import java.util.concurrent.AbstractExecutorService;
-import java.util.concurrent.Callable;
-import java.util.concurrent.ExecutorService;
-import java.util.concurrent.Future;
-import java.util.concurrent.RejectedExecutionException;
-import java.util.concurrent.RunnableFuture;
-import java.util.concurrent.ThreadLocalRandom;
-import java.util.concurrent.TimeUnit;
 
 /**
  * An {@link ExecutorService} for running {@link ForkJoinTask}s.
@@ -498,6 +490,7 @@ public class ForkJoinPool extends AbstractExecutorService {
      * (7) Exported methods
      * (8) Static block initializing statics in minimally dependent order
      */
+    // android-note: Removed references to CountedCompleters.
 
     // Static utilities
 
@@ -524,8 +517,8 @@ public class ForkJoinPool extends AbstractExecutorService {
          * Returns a new worker thread operating in the given pool.
          *
          * @param pool the pool this thread works in
-         * @throws NullPointerException if the pool is null
          * @return the new worker thread
+         * @throws NullPointerException if the pool is null
          */
         public ForkJoinWorkerThread newThread(ForkJoinPool pool);
     }
@@ -2090,7 +2083,7 @@ public class ForkJoinPool extends AbstractExecutorService {
                     w.currentSteal = ps;
                 }
             }
-            else if (active) {       // decrement active count without queuing
+            else if (active) {      // decrement active count without queuing
                 long nc = ((c = ctl) & ~AC_MASK) | ((c & AC_MASK) - AC_UNIT);
                 if ((int)(nc >> AC_SHIFT) + parallelism == 0)
                     break;          // bypass decrement-then-increment
diff --git a/luni/src/main/java/java/util/concurrent/ForkJoinTask.java b/luni/src/main/java/java/util/concurrent/ForkJoinTask.java
index c6bc6de..d34cae3 100644
--- a/luni/src/main/java/java/util/concurrent/ForkJoinTask.java
+++ b/luni/src/main/java/java/util/concurrent/ForkJoinTask.java
@@ -12,14 +12,6 @@ import java.util.List;
 import java.util.RandomAccess;
 import java.lang.ref.WeakReference;
 import java.lang.ref.ReferenceQueue;
-import java.util.concurrent.Callable;
-import java.util.concurrent.CancellationException;
-import java.util.concurrent.ExecutionException;
-import java.util.concurrent.Future;
-import java.util.concurrent.RejectedExecutionException;
-import java.util.concurrent.RunnableFuture;
-import java.util.concurrent.TimeUnit;
-import java.util.concurrent.TimeoutException;
 import java.util.concurrent.locks.ReentrantLock;
 import java.lang.reflect.Constructor;
 
@@ -177,6 +169,8 @@ import java.lang.reflect.Constructor;
  * @since 1.7
  * @author Doug Lea
  */
+// android-note: Removed references to hidden apis commonPool, CountedCompleter
+// etc.
 public abstract class ForkJoinTask<V> implements Future<V>, Serializable {
 
     /*
@@ -407,11 +401,13 @@ public abstract class ForkJoinTask<V> implements Future<V>, Serializable {
         final Throwable ex;
         ExceptionNode next;
         final long thrower;  // use id not ref to avoid weak cycles
+        final int hashCode;  // store task hashCode before weak ref disappears
         ExceptionNode(ForkJoinTask<?> task, Throwable ex, ExceptionNode next) {
             super(task, exceptionTableRefQueue);
             this.ex = ex;
             this.next = next;
             this.thrower = Thread.currentThread().getId();
+            this.hashCode = System.identityHashCode(task);
         }
     }
 
@@ -573,9 +569,9 @@ public abstract class ForkJoinTask<V> implements Future<V>, Serializable {
     private static void expungeStaleExceptions() {
         for (Object x; (x = exceptionTableRefQueue.poll()) != null;) {
             if (x instanceof ExceptionNode) {
-                ForkJoinTask<?> key = ((ExceptionNode)x).get();
+                int hashCode = ((ExceptionNode)x).hashCode;
                 ExceptionNode[] t = exceptionTable;
-                int i = System.identityHashCode(key) & (t.length - 1);
+                int i = hashCode & (t.length - 1);
                 ExceptionNode e = t[i];
                 ExceptionNode pred = null;
                 while (e != null) {
@@ -1413,8 +1409,6 @@ public abstract class ForkJoinTask<V> implements Future<V>, Serializable {
             try {
                 result = callable.call();
                 return true;
-            } catch (Error err) {
-                throw err;
             } catch (RuntimeException rex) {
                 throw rex;
             } catch (Exception ex) {
diff --git a/luni/src/main/java/java/util/concurrent/FutureTask.java b/luni/src/main/java/java/util/concurrent/FutureTask.java
index 114fe49..5e24fc8 100644
--- a/luni/src/main/java/java/util/concurrent/FutureTask.java
+++ b/luni/src/main/java/java/util/concurrent/FutureTask.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent;
+
 import java.util.concurrent.locks.LockSupport;
 
 /**
@@ -134,7 +135,7 @@ public class FutureTask<V> implements RunnableFuture<V> {
 
     public boolean cancel(boolean mayInterruptIfRunning) {
         if (!(state == NEW &&
-              UNSAFE.compareAndSwapInt(this, stateOffset, NEW,
+              U.compareAndSwapInt(this, STATE, NEW,
                   mayInterruptIfRunning ? INTERRUPTING : CANCELLED)))
             return false;
         try {    // in case call to interrupt throws exception
@@ -144,7 +145,7 @@ public class FutureTask<V> implements RunnableFuture<V> {
                     if (t != null)
                         t.interrupt();
                 } finally { // final state
-                    UNSAFE.putOrderedInt(this, stateOffset, INTERRUPTED);
+                    U.putOrderedInt(this, STATE, INTERRUPTED);
                 }
             }
         } finally {
@@ -198,9 +199,9 @@ public class FutureTask<V> implements RunnableFuture<V> {
      * @param v the value
      */
     protected void set(V v) {
-        if (UNSAFE.compareAndSwapInt(this, stateOffset, NEW, COMPLETING)) {
+        if (U.compareAndSwapInt(this, STATE, NEW, COMPLETING)) {
             outcome = v;
-            UNSAFE.putOrderedInt(this, stateOffset, NORMAL); // final state
+            U.putOrderedInt(this, STATE, NORMAL); // final state
             finishCompletion();
         }
     }
@@ -216,17 +217,16 @@ public class FutureTask<V> implements RunnableFuture<V> {
      * @param t the cause of failure
      */
     protected void setException(Throwable t) {
-        if (UNSAFE.compareAndSwapInt(this, stateOffset, NEW, COMPLETING)) {
+        if (U.compareAndSwapInt(this, STATE, NEW, COMPLETING)) {
             outcome = t;
-            UNSAFE.putOrderedInt(this, stateOffset, EXCEPTIONAL); // final state
+            U.putOrderedInt(this, STATE, EXCEPTIONAL); // final state
             finishCompletion();
         }
     }
 
     public void run() {
         if (state != NEW ||
-            !UNSAFE.compareAndSwapObject(this, runnerOffset,
-                                         null, Thread.currentThread()))
+            !U.compareAndSwapObject(this, RUNNER, null, Thread.currentThread()))
             return;
         try {
             Callable<V> c = callable;
@@ -263,12 +263,11 @@ public class FutureTask<V> implements RunnableFuture<V> {
      * designed for use with tasks that intrinsically execute more
      * than once.
      *
-     * @return true if successfully run and reset
+     * @return {@code true} if successfully run and reset
      */
     protected boolean runAndReset() {
         if (state != NEW ||
-            !UNSAFE.compareAndSwapObject(this, runnerOffset,
-                                         null, Thread.currentThread()))
+            !U.compareAndSwapObject(this, RUNNER, null, Thread.currentThread()))
             return false;
         boolean ran = false;
         int s = state;
@@ -335,7 +334,7 @@ public class FutureTask<V> implements RunnableFuture<V> {
     private void finishCompletion() {
         // assert state > COMPLETING;
         for (WaitNode q; (q = waiters) != null;) {
-            if (UNSAFE.compareAndSwapObject(this, waitersOffset, q, null)) {
+            if (U.compareAndSwapObject(this, WAITERS, q, null)) {
                 for (;;) {
                     Thread t = q.thread;
                     if (t != null) {
@@ -362,39 +361,61 @@ public class FutureTask<V> implements RunnableFuture<V> {
      *
      * @param timed true if use timed waits
      * @param nanos time to wait, if timed
-     * @return state upon completion
+     * @return state upon completion or at timeout
      */
     private int awaitDone(boolean timed, long nanos)
         throws InterruptedException {
-        final long deadline = timed ? System.nanoTime() + nanos : 0L;
+        // The code below is very delicate, to achieve these goals:
+        // - call nanoTime exactly once for each call to park
+        // - if nanos <= 0, return promptly without allocation or nanoTime
+        // - if nanos == Long.MIN_VALUE, don't underflow
+        // - if nanos == Long.MAX_VALUE, and nanoTime is non-monotonic
+        //   and we suffer a spurious wakeup, we will do no worse than
+        //   to park-spin for a while
+        long startTime = 0L;    // Special value 0L means not yet parked
         WaitNode q = null;
         boolean queued = false;
         for (;;) {
-            if (Thread.interrupted()) {
-                removeWaiter(q);
-                throw new InterruptedException();
-            }
-
             int s = state;
             if (s > COMPLETING) {
                 if (q != null)
                     q.thread = null;
                 return s;
             }
-            else if (s == COMPLETING) // cannot time out yet
+            else if (s == COMPLETING)
+                // We may have already promised (via isDone) that we are done
+                // so never return empty-handed or throw InterruptedException
                 Thread.yield();
-            else if (q == null)
+            else if (Thread.interrupted()) {
+                removeWaiter(q);
+                throw new InterruptedException();
+            }
+            else if (q == null) {
+                if (timed && nanos <= 0L)
+                    return s;
                 q = new WaitNode();
+            }
             else if (!queued)
-                queued = UNSAFE.compareAndSwapObject(this, waitersOffset,
-                                                     q.next = waiters, q);
+                queued = U.compareAndSwapObject(this, WAITERS,
+                                                q.next = waiters, q);
             else if (timed) {
-                nanos = deadline - System.nanoTime();
-                if (nanos <= 0L) {
-                    removeWaiter(q);
-                    return state;
+                final long parkNanos;
+                if (startTime == 0L) { // first time
+                    startTime = System.nanoTime();
+                    if (startTime == 0L)
+                        startTime = 1L;
+                    parkNanos = nanos;
+                } else {
+                    long elapsed = System.nanoTime() - startTime;
+                    if (elapsed >= nanos) {
+                        removeWaiter(q);
+                        return state;
+                    }
+                    parkNanos = nanos - elapsed;
                 }
-                LockSupport.parkNanos(this, nanos);
+                // nanoTime may be slow; recheck before parking
+                if (state < COMPLETING)
+                    LockSupport.parkNanos(this, parkNanos);
             }
             else
                 LockSupport.park(this);
@@ -425,8 +446,7 @@ public class FutureTask<V> implements RunnableFuture<V> {
                         if (pred.thread == null) // check for race
                             continue retry;
                     }
-                    else if (!UNSAFE.compareAndSwapObject(this, waitersOffset,
-                                                          q, s))
+                    else if (!U.compareAndSwapObject(this, WAITERS, q, s))
                         continue retry;
                 }
                 break;
@@ -435,23 +455,25 @@ public class FutureTask<V> implements RunnableFuture<V> {
     }
 
     // Unsafe mechanics
-    private static final sun.misc.Unsafe UNSAFE;
-    private static final long stateOffset;
-    private static final long runnerOffset;
-    private static final long waitersOffset;
+    private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
+    private static final long STATE;
+    private static final long RUNNER;
+    private static final long WAITERS;
     static {
         try {
-            UNSAFE = sun.misc.Unsafe.getUnsafe();
-            Class<?> k = FutureTask.class;
-            stateOffset = UNSAFE.objectFieldOffset
-                (k.getDeclaredField("state"));
-            runnerOffset = UNSAFE.objectFieldOffset
-                (k.getDeclaredField("runner"));
-            waitersOffset = UNSAFE.objectFieldOffset
-                (k.getDeclaredField("waiters"));
+            STATE = U.objectFieldOffset
+                (FutureTask.class.getDeclaredField("state"));
+            RUNNER = U.objectFieldOffset
+                (FutureTask.class.getDeclaredField("runner"));
+            WAITERS = U.objectFieldOffset
+                (FutureTask.class.getDeclaredField("waiters"));
         } catch (Exception e) {
             throw new Error(e);
         }
+
+        // Reduce the risk of rare disastrous classloading in first call to
+        // LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
+        Class<?> ensureLoaded = LockSupport.class;
     }
 
 }
diff --git a/luni/src/main/java/java/util/concurrent/LinkedTransferQueue.java b/luni/src/main/java/java/util/concurrent/LinkedTransferQueue.java
index a041fb1..db48420 100644
--- a/luni/src/main/java/java/util/concurrent/LinkedTransferQueue.java
+++ b/luni/src/main/java/java/util/concurrent/LinkedTransferQueue.java
@@ -11,7 +11,6 @@ import java.util.Collection;
 import java.util.Iterator;
 import java.util.NoSuchElementException;
 import java.util.Queue;
-import java.util.concurrent.TimeUnit;
 import java.util.concurrent.locks.LockSupport;
 
 // BEGIN android-note
@@ -76,7 +75,7 @@ public class LinkedTransferQueue<E> extends AbstractQueue<E>
      *
      * A FIFO dual queue may be implemented using a variation of the
      * Michael & Scott (M&S) lock-free queue algorithm
-     * (http://www.cs.rochester.edu/u/scott/papers/1996_PODC_queues.pdf).
+     * (http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf).
      * It maintains two pointer fields, "head", pointing to a
      * (matched) node that in turn points to the first actual
      * (unmatched) queue node (or null if empty); and "tail" that
@@ -1313,5 +1312,9 @@ public class LinkedTransferQueue<E> extends AbstractQueue<E>
         } catch (Exception e) {
             throw new Error(e);
         }
+
+        // Reduce the risk of rare disastrous classloading in first call to
+        // LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
+        Class<?> ensureLoaded = LockSupport.class;
     }
 }
diff --git a/luni/src/main/java/java/util/concurrent/Phaser.java b/luni/src/main/java/java/util/concurrent/Phaser.java
index a97d187..c5faf16 100644
--- a/luni/src/main/java/java/util/concurrent/Phaser.java
+++ b/luni/src/main/java/java/util/concurrent/Phaser.java
@@ -6,8 +6,6 @@
 
 package java.util.concurrent;
 
-import java.util.concurrent.TimeUnit;
-import java.util.concurrent.TimeoutException;
 import java.util.concurrent.atomic.AtomicReference;
 import java.util.concurrent.locks.LockSupport;
 
@@ -1128,5 +1126,9 @@ public class Phaser {
         } catch (Exception e) {
             throw new Error(e);
         }
+
+        // Reduce the risk of rare disastrous classloading in first call to
+        // LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
+        Class<?> ensureLoaded = LockSupport.class;
     }
 }
diff --git a/luni/src/main/java/java/util/concurrent/PriorityBlockingQueue.java b/luni/src/main/java/java/util/concurrent/PriorityBlockingQueue.java
index 0f9e715..40b3510 100644
--- a/luni/src/main/java/java/util/concurrent/PriorityBlockingQueue.java
+++ b/luni/src/main/java/java/util/concurrent/PriorityBlockingQueue.java
@@ -190,7 +190,7 @@ public class PriorityBlockingQueue<E> extends AbstractQueue<E>
     /**
      * Creates a {@code PriorityBlockingQueue} containing the elements
      * in the specified collection.  If the specified collection is a
-     * {@link SortedSet} or a {@link PriorityQueue},  this
+     * {@link SortedSet} or a {@link PriorityQueue}, this
      * priority queue will be ordered according to the same ordering.
      * Otherwise, this priority queue will be ordered according to the
      * {@linkplain Comparable natural ordering} of its elements.
diff --git a/luni/src/main/java/java/util/concurrent/RecursiveTask.java b/luni/src/main/java/java/util/concurrent/RecursiveTask.java
index 80baa52..d201bd6 100644
--- a/luni/src/main/java/java/util/concurrent/RecursiveTask.java
+++ b/luni/src/main/java/java/util/concurrent/RecursiveTask.java
@@ -46,6 +46,7 @@ public abstract class RecursiveTask<V> extends ForkJoinTask<V> {
 
     /**
      * The main computation performed by this task.
+     * @return the result of the computation
      */
     protected abstract V compute();
 
diff --git a/luni/src/main/java/java/util/concurrent/ScheduledExecutorService.java b/luni/src/main/java/java/util/concurrent/ScheduledExecutorService.java
index b978fae..d5bae22 100644
--- a/luni/src/main/java/java/util/concurrent/ScheduledExecutorService.java
+++ b/luni/src/main/java/java/util/concurrent/ScheduledExecutorService.java
@@ -16,9 +16,9 @@ package java.util.concurrent;
  * {@code scheduleWithFixedDelay} methods create and execute tasks
  * that run periodically until cancelled.
  *
- * <p>Commands submitted using the {@link Executor#execute} and
- * {@link ExecutorService} {@code submit} methods are scheduled with
- * a requested delay of zero. Zero and negative delays (but not
+ * <p>Commands submitted using the {@link Executor#execute(Runnable)}
+ * and {@link ExecutorService} {@code submit} methods are scheduled
+ * with a requested delay of zero. Zero and negative delays (but not
  * periods) are also allowed in {@code schedule} methods, and are
  * treated as requests for immediate execution.
  *
@@ -33,7 +33,7 @@ package java.util.concurrent;
  * which the task is enabled due to network time synchronization
  * protocols, clock drift, or other factors.
  *
- * The {@link Executors} class provides convenient factory methods for
+ * <p>The {@link Executors} class provides convenient factory methods for
  * the ScheduledExecutorService implementations provided in this package.
  *
  * <h3>Usage Example</h3>
diff --git a/luni/src/main/java/java/util/concurrent/ScheduledThreadPoolExecutor.java b/luni/src/main/java/java/util/concurrent/ScheduledThreadPoolExecutor.java
index 483981d..d01cc33 100644
--- a/luni/src/main/java/java/util/concurrent/ScheduledThreadPoolExecutor.java
+++ b/luni/src/main/java/java/util/concurrent/ScheduledThreadPoolExecutor.java
@@ -5,7 +5,9 @@
  */
 
 package java.util.concurrent;
+
 import static java.util.concurrent.TimeUnit.NANOSECONDS;
+import static java.util.concurrent.TimeUnit.MILLISECONDS;
 import java.util.concurrent.atomic.AtomicLong;
 import java.util.concurrent.locks.Condition;
 import java.util.concurrent.locks.ReentrantLock;
@@ -17,11 +19,11 @@ import java.util.*;
 
 /**
  * A {@link ThreadPoolExecutor} that can additionally schedule
- * commands to run after a given delay, or to execute
- * periodically. This class is preferable to {@link java.util.Timer}
- * when multiple worker threads are needed, or when the additional
- * flexibility or capabilities of {@link ThreadPoolExecutor} (which
- * this class extends) are required.
+ * commands to run after a given delay, or to execute periodically.
+ * This class is preferable to {@link java.util.Timer} when multiple
+ * worker threads are needed, or when the additional flexibility or
+ * capabilities of {@link ThreadPoolExecutor} (which this class
+ * extends) are required.
  *
  * <p>Delayed tasks execute no sooner than they are enabled, but
  * without any real-time guarantees about when, after they are
@@ -35,9 +37,9 @@ import java.util.*;
  * elapses. While this enables further inspection and monitoring, it
  * may also cause unbounded retention of cancelled tasks.
  *
- * <p>Successive executions of a task scheduled via
- * {@code scheduleAtFixedRate} or
- * {@code scheduleWithFixedDelay} do not overlap. While different
+ * <p>Successive executions of a periodic task scheduled via
+ * {@link #scheduleAtFixedRate} or
+ * {@link #scheduleWithFixedDelay} do not overlap. While different
  * executions may be performed by different threads, the effects of
  * prior executions <a
  * href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
@@ -132,7 +134,7 @@ public class ScheduledThreadPoolExecutor
     private volatile boolean executeExistingDelayedTasksAfterShutdown = true;
 
     /**
-     * True if ScheduledFutureTask.cancel should remove from queue
+     * True if ScheduledFutureTask.cancel should remove from queue.
      */
     private volatile boolean removeOnCancel = false;
 
@@ -159,10 +161,10 @@ public class ScheduledThreadPoolExecutor
         private long time;
 
         /**
-         * Period in nanoseconds for repeating tasks.  A positive
-         * value indicates fixed-rate execution.  A negative value
-         * indicates fixed-delay execution.  A value of 0 indicates a
-         * non-repeating task.
+         * Period in nanoseconds for repeating tasks.
+         * A positive value indicates fixed-rate execution.
+         * A negative value indicates fixed-delay execution.
+         * A value of 0 indicates a non-repeating (one-shot) task.
          */
         private final long period;
 
@@ -177,19 +179,21 @@ public class ScheduledThreadPoolExecutor
         /**
          * Creates a one-shot action with given nanoTime-based trigger time.
          */
-        ScheduledFutureTask(Runnable r, V result, long ns) {
+        ScheduledFutureTask(Runnable r, V result, long triggerTime) {
             super(r, result);
-            this.time = ns;
+            this.time = triggerTime;
             this.period = 0;
             this.sequenceNumber = sequencer.getAndIncrement();
         }
 
         /**
-         * Creates a periodic action with given nano time and period.
+         * Creates a periodic action with given nanoTime-based initial
+         * trigger time and period.
          */
-        ScheduledFutureTask(Runnable r, V result, long ns, long period) {
+        ScheduledFutureTask(Runnable r, V result, long triggerTime,
+                            long period) {
             super(r, result);
-            this.time = ns;
+            this.time = triggerTime;
             this.period = period;
             this.sequenceNumber = sequencer.getAndIncrement();
         }
@@ -197,9 +201,9 @@ public class ScheduledThreadPoolExecutor
         /**
          * Creates a one-shot action with given nanoTime-based trigger time.
          */
-        ScheduledFutureTask(Callable<V> callable, long ns) {
+        ScheduledFutureTask(Callable<V> callable, long triggerTime) {
             super(callable);
-            this.time = ns;
+            this.time = triggerTime;
             this.period = 0;
             this.sequenceNumber = sequencer.getAndIncrement();
         }
@@ -389,6 +393,22 @@ public class ScheduledThreadPoolExecutor
     }
 
     /**
+     * The default keep-alive time for pool threads.
+     *
+     * Normally, this value is unused because all pool threads will be
+     * core threads, but if a user creates a pool with a corePoolSize
+     * of zero (against our advice), we keep a thread alive as long as
+     * there are queued tasks.  If the keep alive time is zero (the
+     * historic value), we end up hot-spinning in getTask, wasting a
+     * CPU.  But on the other hand, if we set the value too high, and
+     * users create a one-shot pool which they don't cleanly shutdown,
+     * the pool's non-daemon threads will prevent JVM termination.  A
+     * small but non-zero value (relative to a JVM's lifetime) seems
+     * best.
+     */
+    private static final long DEFAULT_KEEPALIVE_MILLIS = 10L;
+
+    /**
      * Creates a new {@code ScheduledThreadPoolExecutor} with the
      * given core pool size.
      *
@@ -397,7 +417,8 @@ public class ScheduledThreadPoolExecutor
      * @throws IllegalArgumentException if {@code corePoolSize < 0}
      */
     public ScheduledThreadPoolExecutor(int corePoolSize) {
-        super(corePoolSize, Integer.MAX_VALUE, 0, NANOSECONDS,
+        super(corePoolSize, Integer.MAX_VALUE,
+              DEFAULT_KEEPALIVE_MILLIS, MILLISECONDS,
               new DelayedWorkQueue());
     }
 
@@ -414,13 +435,14 @@ public class ScheduledThreadPoolExecutor
      */
     public ScheduledThreadPoolExecutor(int corePoolSize,
                                        ThreadFactory threadFactory) {
-        super(corePoolSize, Integer.MAX_VALUE, 0, NANOSECONDS,
+        super(corePoolSize, Integer.MAX_VALUE,
+              DEFAULT_KEEPALIVE_MILLIS, MILLISECONDS,
               new DelayedWorkQueue(), threadFactory);
     }
 
     /**
-     * Creates a new ScheduledThreadPoolExecutor with the given
-     * initial parameters.
+     * Creates a new {@code ScheduledThreadPoolExecutor} with the
+     * given initial parameters.
      *
      * @param corePoolSize the number of threads to keep in the pool, even
      *        if they are idle, unless {@code allowCoreThreadTimeOut} is set
@@ -431,13 +453,14 @@ public class ScheduledThreadPoolExecutor
      */
     public ScheduledThreadPoolExecutor(int corePoolSize,
                                        RejectedExecutionHandler handler) {
-        super(corePoolSize, Integer.MAX_VALUE, 0, NANOSECONDS,
+        super(corePoolSize, Integer.MAX_VALUE,
+              DEFAULT_KEEPALIVE_MILLIS, MILLISECONDS,
               new DelayedWorkQueue(), handler);
     }
 
     /**
-     * Creates a new ScheduledThreadPoolExecutor with the given
-     * initial parameters.
+     * Creates a new {@code ScheduledThreadPoolExecutor} with the
+     * given initial parameters.
      *
      * @param corePoolSize the number of threads to keep in the pool, even
      *        if they are idle, unless {@code allowCoreThreadTimeOut} is set
@@ -452,19 +475,20 @@ public class ScheduledThreadPoolExecutor
     public ScheduledThreadPoolExecutor(int corePoolSize,
                                        ThreadFactory threadFactory,
                                        RejectedExecutionHandler handler) {
-        super(corePoolSize, Integer.MAX_VALUE, 0, NANOSECONDS,
+        super(corePoolSize, Integer.MAX_VALUE,
+              DEFAULT_KEEPALIVE_MILLIS, MILLISECONDS,
               new DelayedWorkQueue(), threadFactory, handler);
     }
 
     /**
-     * Returns the trigger time of a delayed action.
+     * Returns the nanoTime-based trigger time of a delayed action.
      */
     private long triggerTime(long delay, TimeUnit unit) {
         return triggerTime(unit.toNanos((delay < 0) ? 0 : delay));
     }
 
     /**
-     * Returns the trigger time of a delayed action.
+     * Returns the nanoTime-based trigger time of a delayed action.
      */
     long triggerTime(long delay) {
         return now() +
@@ -497,7 +521,7 @@ public class ScheduledThreadPoolExecutor
                                        TimeUnit unit) {
         if (command == null || unit == null)
             throw new NullPointerException();
-        RunnableScheduledFuture<?> t = decorateTask(command,
+        RunnableScheduledFuture<Void> t = decorateTask(command,
             new ScheduledFutureTask<Void>(command, null,
                                           triggerTime(delay, unit)));
         delayedExecute(t);
@@ -725,6 +749,7 @@ public class ScheduledThreadPoolExecutor
      * {@code true}, future executions of existing periodic tasks will
      * be cancelled.
      */
+    // android-note: Removed "throws SecurityException" doc.
     public void shutdown() {
         super.shutdown();
     }
@@ -744,23 +769,28 @@ public class ScheduledThreadPoolExecutor
      * fails to respond to interrupts may never terminate.
      *
      * @return list of tasks that never commenced execution.
-     *         Each element of this list is a {@link ScheduledFuture},
-     *         including those tasks submitted using {@code execute},
-     *         which are for scheduling purposes used as the basis of a
-     *         zero-delay {@code ScheduledFuture}.
+     *         Each element of this list is a {@link ScheduledFuture}.
+     *         For tasks submitted via one of the {@code schedule}
+     *         methods, the element will be identical to the returned
+     *         {@code ScheduledFuture}.  For tasks submitted using
+     *         {@link #execute}, the element will be a zero-delay {@code
+     *         ScheduledFuture}.
      */
+    // android-note: Removed "throws SecurityException" doc.
     public List<Runnable> shutdownNow() {
         return super.shutdownNow();
     }
 
     /**
-     * Returns the task queue used by this executor.  Each element of
-     * this queue is a {@link ScheduledFuture}, including those
-     * tasks submitted using {@code execute} which are for scheduling
-     * purposes used as the basis of a zero-delay
-     * {@code ScheduledFuture}.  Iteration over this queue is
-     * <em>not</em> guaranteed to traverse tasks in the order in
-     * which they will execute.
+     * Returns the task queue used by this executor.
+     * Each element of this list is a {@link ScheduledFuture}.
+     * For tasks submitted via one of the {@code schedule} methods, the
+     * element will be identical to the returned {@code ScheduledFuture}.
+     * For tasks submitted using {@link #execute}, the element will be a
+     * zero-delay {@code ScheduledFuture}.
+     *
+     * <p>Iteration over this queue is <em>not</em> guaranteed to traverse
+     * tasks in the order in which they will execute.
      *
      * @return the task queue
      */
@@ -803,7 +833,7 @@ public class ScheduledThreadPoolExecutor
         private RunnableScheduledFuture<?>[] queue =
             new RunnableScheduledFuture<?>[INITIAL_CAPACITY];
         private final ReentrantLock lock = new ReentrantLock();
-        private int size = 0;
+        private int size;
 
         /**
          * Thread designated to wait for the task at the head of the
@@ -821,7 +851,7 @@ public class ScheduledThreadPoolExecutor
          * signalled.  So waiting threads must be prepared to acquire
          * and lose leadership while waiting.
          */
-        private Thread leader = null;
+        private Thread leader;
 
         /**
          * Condition signalled when a newer task becomes available at the
@@ -1220,11 +1250,11 @@ public class ScheduledThreadPoolExecutor
          * Snapshot iterator that works off copy of underlying q array.
          */
         private class Itr implements Iterator<Runnable> {
-            final RunnableScheduledFuture[] array;
+            final RunnableScheduledFuture<?>[] array;
             int cursor = 0;     // index of next element to return
             int lastRet = -1;   // index of last element, or -1 if no such
 
-            Itr(RunnableScheduledFuture[] array) {
+            Itr(RunnableScheduledFuture<?>[] array) {
                 this.array = array;
             }
 
diff --git a/luni/src/main/java/java/util/concurrent/Semaphore.java b/luni/src/main/java/java/util/concurrent/Semaphore.java
index 9ee18a8..b4b7edd 100644
--- a/luni/src/main/java/java/util/concurrent/Semaphore.java
+++ b/luni/src/main/java/java/util/concurrent/Semaphore.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent;
+
 import java.util.Collection;
 import java.util.concurrent.locks.AbstractQueuedSynchronizer;
 
diff --git a/luni/src/main/java/java/util/concurrent/SynchronousQueue.java b/luni/src/main/java/java/util/concurrent/SynchronousQueue.java
index ea6b3d1..69452af 100644
--- a/luni/src/main/java/java/util/concurrent/SynchronousQueue.java
+++ b/luni/src/main/java/java/util/concurrent/SynchronousQueue.java
@@ -6,6 +6,7 @@
  */
 
 package java.util.concurrent;
+
 import java.util.concurrent.locks.LockSupport;
 import java.util.concurrent.locks.ReentrantLock;
 import java.util.*;
@@ -1057,7 +1058,7 @@ public class SynchronousQueue<E> extends AbstractQueue<E>
     }
 
     /**
-     * Sets the zeroeth element of the specified array to {@code null}
+     * Sets the zeroth element of the specified array to {@code null}
      * (if the array has non-zero length) and returns it.
      *
      * @param a the array
@@ -1150,7 +1151,7 @@ public class SynchronousQueue<E> extends AbstractQueue<E>
     /**
      * Reconstitutes this queue from a stream (that is, deserializes it).
      */
-    private void readObject(final java.io.ObjectInputStream s)
+    private void readObject(java.io.ObjectInputStream s)
         throws java.io.IOException, ClassNotFoundException {
         s.defaultReadObject();
         if (waitingProducers instanceof FifoWaitQueue)
@@ -1172,4 +1173,9 @@ public class SynchronousQueue<E> extends AbstractQueue<E>
         }
     }
 
+    static {
+        // Reduce the risk of rare disastrous classloading in first call to
+        // LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
+        Class<?> ensureLoaded = LockSupport.class;
+    }
 }
diff --git a/luni/src/main/java/java/util/concurrent/ThreadLocalRandom.java b/luni/src/main/java/java/util/concurrent/ThreadLocalRandom.java
index 5baf75f..b007af2 100644
--- a/luni/src/main/java/java/util/concurrent/ThreadLocalRandom.java
+++ b/luni/src/main/java/java/util/concurrent/ThreadLocalRandom.java
@@ -107,9 +107,9 @@ public class ThreadLocalRandom extends Random {
      *
      * @param least the least value returned
      * @param bound the upper bound (exclusive)
+     * @return the next value
      * @throws IllegalArgumentException if least greater than or equal
      * to bound
-     * @return the next value
      */
     public int nextInt(int least, int bound) {
         if (least >= bound)
@@ -172,7 +172,7 @@ public class ThreadLocalRandom extends Random {
      * @throws IllegalArgumentException if n is not positive
      */
     public double nextDouble(double n) {
-        if (n <= 0)
+        if (!(n > 0))
             throw new IllegalArgumentException("n must be positive");
         return nextDouble() * n;
     }
diff --git a/luni/src/main/java/java/util/concurrent/ThreadPoolExecutor.java b/luni/src/main/java/java/util/concurrent/ThreadPoolExecutor.java
index 9586293..c484920 100644
--- a/luni/src/main/java/java/util/concurrent/ThreadPoolExecutor.java
+++ b/luni/src/main/java/java/util/concurrent/ThreadPoolExecutor.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent;
+
 import java.util.concurrent.locks.AbstractQueuedSynchronizer;
 import java.util.concurrent.locks.Condition;
 import java.util.concurrent.locks.ReentrantLock;
@@ -582,7 +583,7 @@ public class ThreadPoolExecutor extends AbstractExecutorService {
             this.thread = getThreadFactory().newThread(this);
         }
 
-        /** Delegates main run loop to outer runWorker  */
+        /** Delegates main run loop to outer runWorker. */
         public void run() {
             runWorker(this);
         }
@@ -1348,6 +1349,7 @@ public class ThreadPoolExecutor extends AbstractExecutorService {
      * complete execution.  Use {@link #awaitTermination awaitTermination}
      * to do that.
      */
+    // android-note: Removed @throws SecurityException
     public void shutdown() {
         final ReentrantLock mainLock = this.mainLock;
         mainLock.lock();
@@ -1377,6 +1379,7 @@ public class ThreadPoolExecutor extends AbstractExecutorService {
      * cancels tasks via {@link Thread#interrupt}, so any task that
      * fails to respond to interrupts may never terminate.
      */
+    // android-note: Removed @throws SecurityException
     public List<Runnable> shutdownNow() {
         List<Runnable> tasks;
         final ReentrantLock mainLock = this.mainLock;
diff --git a/luni/src/main/java/java/util/concurrent/TimeUnit.java b/luni/src/main/java/java/util/concurrent/TimeUnit.java
index eb2c495..8e6a5f7 100644
--- a/luni/src/main/java/java/util/concurrent/TimeUnit.java
+++ b/luni/src/main/java/java/util/concurrent/TimeUnit.java
@@ -40,6 +40,9 @@ package java.util.concurrent;
  * @author Doug Lea
  */
 public enum TimeUnit {
+    /**
+     * Time unit representing one thousandth of a microsecond
+     */
     NANOSECONDS {
         public long toNanos(long d)   { return d; }
         public long toMicros(long d)  { return d/(C1/C0); }
@@ -51,6 +54,10 @@ public enum TimeUnit {
         public long convert(long d, TimeUnit u) { return u.toNanos(d); }
         int excessNanos(long d, long m) { return (int)(d - (m*C2)); }
     },
+
+    /**
+     * Time unit representing one thousandth of a millisecond
+     */
     MICROSECONDS {
         public long toNanos(long d)   { return x(d, C1/C0, MAX/(C1/C0)); }
         public long toMicros(long d)  { return d; }
@@ -62,6 +69,10 @@ public enum TimeUnit {
         public long convert(long d, TimeUnit u) { return u.toMicros(d); }
         int excessNanos(long d, long m) { return (int)((d*C1) - (m*C2)); }
     },
+
+    /**
+     * Time unit representing one thousandth of a second
+     */
     MILLISECONDS {
         public long toNanos(long d)   { return x(d, C2/C0, MAX/(C2/C0)); }
         public long toMicros(long d)  { return x(d, C2/C1, MAX/(C2/C1)); }
@@ -73,6 +84,10 @@ public enum TimeUnit {
         public long convert(long d, TimeUnit u) { return u.toMillis(d); }
         int excessNanos(long d, long m) { return 0; }
     },
+
+    /**
+     * Time unit representing one second
+     */
     SECONDS {
         public long toNanos(long d)   { return x(d, C3/C0, MAX/(C3/C0)); }
         public long toMicros(long d)  { return x(d, C3/C1, MAX/(C3/C1)); }
@@ -84,6 +99,11 @@ public enum TimeUnit {
         public long convert(long d, TimeUnit u) { return u.toSeconds(d); }
         int excessNanos(long d, long m) { return 0; }
     },
+
+    /**
+     * Time unit representing sixty seconds
+     * @since 1.6
+     */
     MINUTES {
         public long toNanos(long d)   { return x(d, C4/C0, MAX/(C4/C0)); }
         public long toMicros(long d)  { return x(d, C4/C1, MAX/(C4/C1)); }
@@ -95,6 +115,11 @@ public enum TimeUnit {
         public long convert(long d, TimeUnit u) { return u.toMinutes(d); }
         int excessNanos(long d, long m) { return 0; }
     },
+
+    /**
+     * Time unit representing sixty minutes
+     * @since 1.6
+     */
     HOURS {
         public long toNanos(long d)   { return x(d, C5/C0, MAX/(C5/C0)); }
         public long toMicros(long d)  { return x(d, C5/C1, MAX/(C5/C1)); }
@@ -106,6 +131,11 @@ public enum TimeUnit {
         public long convert(long d, TimeUnit u) { return u.toHours(d); }
         int excessNanos(long d, long m) { return 0; }
     },
+
+    /**
+     * Time unit representing twenty four hours
+     * @since 1.6
+     */
     DAYS {
         public long toNanos(long d)   { return x(d, C6/C0, MAX/(C6/C0)); }
         public long toMicros(long d)  { return x(d, C6/C1, MAX/(C6/C1)); }
@@ -145,14 +175,13 @@ public enum TimeUnit {
     // etc. are not declared abstract but otherwise act as abstract methods.
 
     /**
-     * Convert the given time duration in the given unit to this
-     * unit.  Conversions from finer to coarser granularities
-     * truncate, so lose precision. For example converting
-     * {@code 999} milliseconds to seconds results in
-     * {@code 0}. Conversions from coarser to finer granularities
-     * with arguments that would numerically overflow saturate to
-     * {@code Long.MIN_VALUE} if negative or {@code Long.MAX_VALUE}
-     * if positive.
+     * Converts the given time duration in the given unit to this unit.
+     * Conversions from finer to coarser granularities truncate, so
+     * lose precision. For example, converting {@code 999} milliseconds
+     * to seconds results in {@code 0}. Conversions from coarser to
+     * finer granularities with arguments that would numerically
+     * overflow saturate to {@code Long.MIN_VALUE} if negative or
+     * {@code Long.MAX_VALUE} if positive.
      *
      * <p>For example, to convert 10 minutes to milliseconds, use:
      * {@code TimeUnit.MILLISECONDS.convert(10L, TimeUnit.MINUTES)}
@@ -168,60 +197,60 @@ public enum TimeUnit {
     }
 
     /**
-     * Equivalent to {@code NANOSECONDS.convert(duration, this)}.
+     * Equivalent to
+     * {@link #convert(long, TimeUnit) NANOSECONDS.convert(duration, this)}.
      * @param duration the duration
      * @return the converted duration,
      * or {@code Long.MIN_VALUE} if conversion would negatively
      * overflow, or {@code Long.MAX_VALUE} if it would positively overflow.
-     * @see #convert
      */
     public long toNanos(long duration) {
         throw new AbstractMethodError();
     }
 
     /**
-     * Equivalent to {@code MICROSECONDS.convert(duration, this)}.
+     * Equivalent to
+     * {@link #convert(long, TimeUnit) MICROSECONDS.convert(duration, this)}.
      * @param duration the duration
      * @return the converted duration,
      * or {@code Long.MIN_VALUE} if conversion would negatively
      * overflow, or {@code Long.MAX_VALUE} if it would positively overflow.
-     * @see #convert
      */
     public long toMicros(long duration) {
         throw new AbstractMethodError();
     }
 
     /**
-     * Equivalent to {@code MILLISECONDS.convert(duration, this)}.
+     * Equivalent to
+     * {@link #convert(long, TimeUnit) MILLISECONDS.convert(duration, this)}.
      * @param duration the duration
      * @return the converted duration,
      * or {@code Long.MIN_VALUE} if conversion would negatively
      * overflow, or {@code Long.MAX_VALUE} if it would positively overflow.
-     * @see #convert
      */
     public long toMillis(long duration) {
         throw new AbstractMethodError();
     }
 
     /**
-     * Equivalent to {@code SECONDS.convert(duration, this)}.
+     * Equivalent to
+     * {@link #convert(long, TimeUnit) SECONDS.convert(duration, this)}.
      * @param duration the duration
      * @return the converted duration,
      * or {@code Long.MIN_VALUE} if conversion would negatively
      * overflow, or {@code Long.MAX_VALUE} if it would positively overflow.
-     * @see #convert
      */
     public long toSeconds(long duration) {
         throw new AbstractMethodError();
     }
 
     /**
-     * Equivalent to {@code MINUTES.convert(duration, this)}.
+     * Equivalent to
+     * {@link #convert(long, TimeUnit) MINUTES.convert(duration, this)}.
      * @param duration the duration
      * @return the converted duration,
      * or {@code Long.MIN_VALUE} if conversion would negatively
      * overflow, or {@code Long.MAX_VALUE} if it would positively overflow.
-     * @see #convert
      * @since 1.6
      */
     public long toMinutes(long duration) {
@@ -229,12 +258,12 @@ public enum TimeUnit {
     }
 
     /**
-     * Equivalent to {@code HOURS.convert(duration, this)}.
+     * Equivalent to
+     * {@link #convert(long, TimeUnit) HOURS.convert(duration, this)}.
      * @param duration the duration
      * @return the converted duration,
      * or {@code Long.MIN_VALUE} if conversion would negatively
      * overflow, or {@code Long.MAX_VALUE} if it would positively overflow.
-     * @see #convert
      * @since 1.6
      */
     public long toHours(long duration) {
@@ -242,10 +271,10 @@ public enum TimeUnit {
     }
 
     /**
-     * Equivalent to {@code DAYS.convert(duration, this)}.
+     * Equivalent to
+     * {@link #convert(long, TimeUnit) DAYS.convert(duration, this)}.
      * @param duration the duration
      * @return the converted duration
-     * @see #convert
      * @since 1.6
      */
     public long toDays(long duration) {
diff --git a/luni/src/main/java/java/util/concurrent/atomic/AtomicBoolean.java b/luni/src/main/java/java/util/concurrent/atomic/AtomicBoolean.java
index 13b12aa..f51e6af 100644
--- a/luni/src/main/java/java/util/concurrent/atomic/AtomicBoolean.java
+++ b/luni/src/main/java/java/util/concurrent/atomic/AtomicBoolean.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent.atomic;
+
 import sun.misc.Unsafe;
 
 /**
diff --git a/luni/src/main/java/java/util/concurrent/atomic/AtomicInteger.java b/luni/src/main/java/java/util/concurrent/atomic/AtomicInteger.java
index d67b20a..8a15298 100644
--- a/luni/src/main/java/java/util/concurrent/atomic/AtomicInteger.java
+++ b/luni/src/main/java/java/util/concurrent/atomic/AtomicInteger.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent.atomic;
+
 import sun.misc.Unsafe;
 
 /**
diff --git a/luni/src/main/java/java/util/concurrent/atomic/AtomicIntegerArray.java b/luni/src/main/java/java/util/concurrent/atomic/AtomicIntegerArray.java
index 1f6980d..fd492d1 100644
--- a/luni/src/main/java/java/util/concurrent/atomic/AtomicIntegerArray.java
+++ b/luni/src/main/java/java/util/concurrent/atomic/AtomicIntegerArray.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent.atomic;
+
 import sun.misc.Unsafe;
 
 /**
diff --git a/luni/src/main/java/java/util/concurrent/atomic/AtomicIntegerFieldUpdater.java b/luni/src/main/java/java/util/concurrent/atomic/AtomicIntegerFieldUpdater.java
index 6067152..4354cb6 100644
--- a/luni/src/main/java/java/util/concurrent/atomic/AtomicIntegerFieldUpdater.java
+++ b/luni/src/main/java/java/util/concurrent/atomic/AtomicIntegerFieldUpdater.java
@@ -10,6 +10,9 @@ import dalvik.system.VMStack; // android-added
 import sun.misc.Unsafe;
 import java.lang.reflect.Field;
 import java.lang.reflect.Modifier;
+import java.security.AccessController;
+import java.security.PrivilegedExceptionAction;
+import java.security.PrivilegedActionException;
 
 /**
  * A reflection-based utility that enables atomic updates to
@@ -243,7 +246,7 @@ public abstract class AtomicIntegerFieldUpdater<T> {
         private final Class<T> tclass;
         private final Class<?> cclass;
 
-        AtomicIntegerFieldUpdaterImpl(Class<T> tclass, String fieldName) {
+        AtomicIntegerFieldUpdaterImpl(final Class<T> tclass, final String fieldName) {
             final Field field;
             final Class<?> caller;
             final int modifiers;
diff --git a/luni/src/main/java/java/util/concurrent/atomic/AtomicLong.java b/luni/src/main/java/java/util/concurrent/atomic/AtomicLong.java
index 278c5b5..ab2961a 100644
--- a/luni/src/main/java/java/util/concurrent/atomic/AtomicLong.java
+++ b/luni/src/main/java/java/util/concurrent/atomic/AtomicLong.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent.atomic;
+
 import sun.misc.Unsafe;
 
 /**
diff --git a/luni/src/main/java/java/util/concurrent/atomic/AtomicLongArray.java b/luni/src/main/java/java/util/concurrent/atomic/AtomicLongArray.java
index 2e8c2b7..b7f3d1e 100644
--- a/luni/src/main/java/java/util/concurrent/atomic/AtomicLongArray.java
+++ b/luni/src/main/java/java/util/concurrent/atomic/AtomicLongArray.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent.atomic;
+
 import sun.misc.Unsafe;
 
 /**
diff --git a/luni/src/main/java/java/util/concurrent/atomic/AtomicLongFieldUpdater.java b/luni/src/main/java/java/util/concurrent/atomic/AtomicLongFieldUpdater.java
index 0096a6b..715788c 100644
--- a/luni/src/main/java/java/util/concurrent/atomic/AtomicLongFieldUpdater.java
+++ b/luni/src/main/java/java/util/concurrent/atomic/AtomicLongFieldUpdater.java
@@ -243,7 +243,7 @@ public abstract class AtomicLongFieldUpdater<T> {
         private final Class<T> tclass;
         private final Class<?> cclass;
 
-        CASUpdater(Class<T> tclass, String fieldName) {
+        CASUpdater(final Class<T> tclass, final String fieldName) {
             final Field field;
             final Class<?> caller;
             final int modifiers;
@@ -337,7 +337,7 @@ public abstract class AtomicLongFieldUpdater<T> {
         private final Class<T> tclass;
         private final Class<?> cclass;
 
-        LockedUpdater(Class<T> tclass, String fieldName) {
+        LockedUpdater(final Class<T> tclass, final String fieldName) {
             Field field = null;
             Class<?> caller = null;
             int modifiers = 0;
diff --git a/luni/src/main/java/java/util/concurrent/atomic/AtomicMarkableReference.java b/luni/src/main/java/java/util/concurrent/atomic/AtomicMarkableReference.java
index 1257be0..18d148f 100644
--- a/luni/src/main/java/java/util/concurrent/atomic/AtomicMarkableReference.java
+++ b/luni/src/main/java/java/util/concurrent/atomic/AtomicMarkableReference.java
@@ -68,7 +68,7 @@ public class AtomicMarkableReference<V> {
      * Typical usage is {@code boolean[1] holder; ref = v.get(holder); }.
      *
      * @param markHolder an array of size of at least one. On return,
-     * {@code markholder[0]} will hold the value of the mark.
+     * {@code markHolder[0]} will hold the value of the mark.
      * @return the current value of the reference
      */
     public V get(boolean[] markHolder) {
diff --git a/luni/src/main/java/java/util/concurrent/atomic/AtomicReference.java b/luni/src/main/java/java/util/concurrent/atomic/AtomicReference.java
index 98b402a..7ea6066 100644
--- a/luni/src/main/java/java/util/concurrent/atomic/AtomicReference.java
+++ b/luni/src/main/java/java/util/concurrent/atomic/AtomicReference.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent.atomic;
+
 import sun.misc.Unsafe;
 
 /**
diff --git a/luni/src/main/java/java/util/concurrent/atomic/AtomicReferenceFieldUpdater.java b/luni/src/main/java/java/util/concurrent/atomic/AtomicReferenceFieldUpdater.java
index eb2d73e..4b5e59c 100644
--- a/luni/src/main/java/java/util/concurrent/atomic/AtomicReferenceFieldUpdater.java
+++ b/luni/src/main/java/java/util/concurrent/atomic/AtomicReferenceFieldUpdater.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent.atomic;
+
 import dalvik.system.VMStack; // android-added
 import sun.misc.Unsafe;
 import java.lang.reflect.Field;
@@ -27,7 +28,7 @@ import java.lang.reflect.Modifier;
  *   private static AtomicReferenceFieldUpdater<Node, Node> rightUpdater =
  *     AtomicReferenceFieldUpdater.newUpdater(Node.class, Node.class, "right");
  *
- *   Node getLeft() { return left;  }
+ *   Node getLeft() { return left; }
  *   boolean compareAndSetLeft(Node expect, Node update) {
  *     return leftUpdater.compareAndSet(this, expect, update);
  *   }
@@ -63,10 +64,11 @@ public abstract class AtomicReferenceFieldUpdater<T,V> {
      * or the field is inaccessible to the caller according to Java language
      * access control
      */
-    public static <U, W> AtomicReferenceFieldUpdater<U,W> newUpdater(Class<U> tclass, Class<W> vclass, String fieldName) {
-        return new AtomicReferenceFieldUpdaterImpl<U,W>(tclass,
-                                                        vclass,
-                                                        fieldName);
+    public static <U,W> AtomicReferenceFieldUpdater<U,W> newUpdater(Class<U> tclass,
+                                                                    Class<W> vclass,
+                                                                    String fieldName) {
+        return new AtomicReferenceFieldUpdaterImpl<U,W>
+            (tclass, vclass, fieldName);
     }
 
     /**
diff --git a/luni/src/main/java/java/util/concurrent/atomic/AtomicStampedReference.java b/luni/src/main/java/java/util/concurrent/atomic/AtomicStampedReference.java
index b93a6f3..1449856 100644
--- a/luni/src/main/java/java/util/concurrent/atomic/AtomicStampedReference.java
+++ b/luni/src/main/java/java/util/concurrent/atomic/AtomicStampedReference.java
@@ -68,7 +68,7 @@ public class AtomicStampedReference<V> {
      * Typical usage is {@code int[1] holder; ref = v.get(holder); }.
      *
      * @param stampHolder an array of size of at least one.  On return,
-     * {@code stampholder[0]} will hold the value of the stamp.
+     * {@code stampHolder[0]} will hold the value of the stamp.
      * @return the current value of the reference
      */
     public V get(int[] stampHolder) {
diff --git a/luni/src/main/java/java/util/concurrent/locks/AbstractOwnableSynchronizer.java b/luni/src/main/java/java/util/concurrent/locks/AbstractOwnableSynchronizer.java
index fa01824..66a2f8e 100644
--- a/luni/src/main/java/java/util/concurrent/locks/AbstractOwnableSynchronizer.java
+++ b/luni/src/main/java/java/util/concurrent/locks/AbstractOwnableSynchronizer.java
@@ -35,20 +35,20 @@ public abstract class AbstractOwnableSynchronizer
     private transient Thread exclusiveOwnerThread;
 
     /**
-     * Sets the thread that currently owns exclusive access. A
-     * {@code null} argument indicates that no thread owns access.
+     * Sets the thread that currently owns exclusive access.
+     * A {@code null} argument indicates that no thread owns access.
      * This method does not otherwise impose any synchronization or
      * {@code volatile} field accesses.
+     * @param thread the owner thread
      */
-    protected final void setExclusiveOwnerThread(Thread t) {
-        exclusiveOwnerThread = t;
+    protected final void setExclusiveOwnerThread(Thread thread) {
+        exclusiveOwnerThread = thread;
     }
 
     /**
-     * Returns the thread last set by
-     * {@code setExclusiveOwnerThread}, or {@code null} if never
-     * set.  This method does not otherwise impose any synchronization
-     * or {@code volatile} field accesses.
+     * Returns the thread last set by {@code setExclusiveOwnerThread},
+     * or {@code null} if never set.  This method does not otherwise
+     * impose any synchronization or {@code volatile} field accesses.
      * @return the owner thread
      */
     protected final Thread getExclusiveOwnerThread() {
diff --git a/luni/src/main/java/java/util/concurrent/locks/AbstractQueuedLongSynchronizer.java b/luni/src/main/java/java/util/concurrent/locks/AbstractQueuedLongSynchronizer.java
index 37aa9d0..47a02a9 100644
--- a/luni/src/main/java/java/util/concurrent/locks/AbstractQueuedLongSynchronizer.java
+++ b/luni/src/main/java/java/util/concurrent/locks/AbstractQueuedLongSynchronizer.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent.locks;
+
 import java.util.concurrent.TimeUnit;
 import java.util.ArrayList;
 import java.util.Collection;
@@ -227,7 +228,7 @@ public abstract class AbstractQueuedLongSynchronizer
         Node nextWaiter;
 
         /**
-         * @return true if node is waiting in shared mode
+         * Returns true if node is waiting in shared mode.
          */
         final boolean isShared() {
             return nextWaiter == SHARED;
@@ -403,9 +404,9 @@ public abstract class AbstractQueuedLongSynchronizer
         Node s = node.next;
         if (s == null || s.waitStatus > 0) {
             s = null;
-            for (Node t = tail; t != null && t != node; t = t.prev)
-                if (t.waitStatus <= 0)
-                    s = t;
+            for (Node p = tail; p != null && p != node; p = p.prev)
+                if (p.waitStatus <= 0)
+                    s = p;
         }
         if (s != null)
             LockSupport.unpark(s.thread);
@@ -1397,13 +1398,13 @@ public abstract class AbstractQueuedLongSynchronizer
      * @return true if present
      */
     private boolean findNodeFromTail(Node node) {
-        Node t = tail;
+        Node p = tail;
         for (;;) {
-            if (t == node)
+            if (p == node)
                 return true;
-            if (t == null)
+            if (p == null)
                 return false;
-            t = t.prev;
+            p = p.prev;
         }
     }
 
@@ -1814,6 +1815,7 @@ public abstract class AbstractQueuedLongSynchronizer
                 throws InterruptedException {
             if (Thread.interrupted())
                 throw new InterruptedException();
+            long initialNanos = nanosTimeout;
             Node node = addConditionWaiter();
             long savedState = fullyRelease(node);
             final long deadline = System.nanoTime() + nanosTimeout;
@@ -1835,7 +1837,8 @@ public abstract class AbstractQueuedLongSynchronizer
                 unlinkCancelledWaiters();
             if (interruptMode != 0)
                 reportInterruptAfterWait(interruptMode);
-            return deadline - System.nanoTime();
+            long remaining = deadline - System.nanoTime(); // avoid overflow
+            return (remaining < initialNanos) ? remaining : Long.MIN_VALUE;
         }
 
         /**
@@ -2027,6 +2030,10 @@ public abstract class AbstractQueuedLongSynchronizer
                 (Node.class.getDeclaredField("next"));
 
         } catch (Exception ex) { throw new Error(ex); }
+
+        // Reduce the risk of rare disastrous classloading in first call to
+        // LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
+        Class<?> ensureLoaded = LockSupport.class;
     }
 
     /**
diff --git a/luni/src/main/java/java/util/concurrent/locks/AbstractQueuedSynchronizer.java b/luni/src/main/java/java/util/concurrent/locks/AbstractQueuedSynchronizer.java
index e711da5..bfe88e5 100644
--- a/luni/src/main/java/java/util/concurrent/locks/AbstractQueuedSynchronizer.java
+++ b/luni/src/main/java/java/util/concurrent/locks/AbstractQueuedSynchronizer.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent.locks;
+
 import java.util.concurrent.TimeUnit;
 import java.util.ArrayList;
 import java.util.Collection;
@@ -128,15 +129,11 @@ import sun.misc.Unsafe;
  * others that are blocked and queued.  However, you can, if desired,
  * define {@code tryAcquire} and/or {@code tryAcquireShared} to
  * disable barging by internally invoking one or more of the inspection
- * methods. In particular, a strict FIFO lock can define
- * {@code tryAcquire} to immediately return {@code false} if {@link
- * #getFirstQueuedThread} does not return the current thread.  A
- * normally preferable non-strict fair version can immediately return
- * {@code false} only if {@link #hasQueuedThreads} returns
- * {@code true} and {@code getFirstQueuedThread} is not the current
- * thread; or equivalently, that {@code getFirstQueuedThread} is both
- * non-null and not the current thread. Further variations are
- * possible.
+ * methods, thereby providing a <em>fair</em> FIFO acquisition order.
+ * In particular, most fair synchronizers can define {@code tryAcquire}
+ * to return {@code false} if {@code hasQueuedPredecessors} (a method
+ * specifically designed to be used by fair synchronizers) returns
+ * {@code true}.  Other variations are possible.
  *
  * <p>Throughput and scalability are generally highest for the
  * default barging (also known as <em>greedy</em>,
@@ -1461,7 +1458,7 @@ public abstract class AbstractQueuedSynchronizer
      * due to the queue being empty.
      *
      * <p>This method is designed to be used by a fair synchronizer to
-     * avoid <a href="AbstractQueuedSynchronizer#barging">barging</a>.
+     * avoid <a href="AbstractQueuedSynchronizer.html#barging">barging</a>.
      * Such a synchronizer's {@link #tryAcquire} method should return
      * {@code false}, and its {@link #tryAcquireShared} method should
      * return a negative value, if this method returns {@code true}
@@ -2042,6 +2039,7 @@ public abstract class AbstractQueuedSynchronizer
                 throws InterruptedException {
             if (Thread.interrupted())
                 throw new InterruptedException();
+            long initialNanos = nanosTimeout;
             Node node = addConditionWaiter();
             int savedState = fullyRelease(node);
             final long deadline = System.nanoTime() + nanosTimeout;
@@ -2063,7 +2061,8 @@ public abstract class AbstractQueuedSynchronizer
                 unlinkCancelledWaiters();
             if (interruptMode != 0)
                 reportInterruptAfterWait(interruptMode);
-            return deadline - System.nanoTime();
+            long remaining = deadline - System.nanoTime(); // avoid overflow
+            return (remaining < initialNanos) ? remaining : Long.MIN_VALUE;
         }
 
         /**
@@ -2255,6 +2254,10 @@ public abstract class AbstractQueuedSynchronizer
                 (Node.class.getDeclaredField("next"));
 
         } catch (Exception ex) { throw new Error(ex); }
+
+        // Reduce the risk of rare disastrous classloading in first call to
+        // LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
+        Class<?> ensureLoaded = LockSupport.class;
     }
 
     /**
diff --git a/luni/src/main/java/java/util/concurrent/locks/Condition.java b/luni/src/main/java/java/util/concurrent/locks/Condition.java
index 522e9e2..11a7090 100644
--- a/luni/src/main/java/java/util/concurrent/locks/Condition.java
+++ b/luni/src/main/java/java/util/concurrent/locks/Condition.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent.locks;
+
 import java.util.concurrent.TimeUnit;
 import java.util.Date;
 
diff --git a/luni/src/main/java/java/util/concurrent/locks/Lock.java b/luni/src/main/java/java/util/concurrent/locks/Lock.java
index 6eeb236..a7ca001 100644
--- a/luni/src/main/java/java/util/concurrent/locks/Lock.java
+++ b/luni/src/main/java/java/util/concurrent/locks/Lock.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent.locks;
+
 import java.util.concurrent.TimeUnit;
 
 /**
diff --git a/luni/src/main/java/java/util/concurrent/locks/LockSupport.java b/luni/src/main/java/java/util/concurrent/locks/LockSupport.java
index 875b2bf..089d818 100644
--- a/luni/src/main/java/java/util/concurrent/locks/LockSupport.java
+++ b/luni/src/main/java/java/util/concurrent/locks/LockSupport.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent.locks;
+
 import sun.misc.Unsafe;
 
 /**
diff --git a/luni/src/main/java/java/util/concurrent/locks/ReentrantLock.java b/luni/src/main/java/java/util/concurrent/locks/ReentrantLock.java
index bde4741..3654248 100644
--- a/luni/src/main/java/java/util/concurrent/locks/ReentrantLock.java
+++ b/luni/src/main/java/java/util/concurrent/locks/ReentrantLock.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent.locks;
+
 import java.util.concurrent.TimeUnit;
 import java.util.Collection;
 
diff --git a/luni/src/main/java/java/util/concurrent/locks/ReentrantReadWriteLock.java b/luni/src/main/java/java/util/concurrent/locks/ReentrantReadWriteLock.java
index 2d3c65d..cc7ba4c 100644
--- a/luni/src/main/java/java/util/concurrent/locks/ReentrantReadWriteLock.java
+++ b/luni/src/main/java/java/util/concurrent/locks/ReentrantReadWriteLock.java
@@ -5,6 +5,7 @@
  */
 
 package java.util.concurrent.locks;
+
 import java.util.concurrent.TimeUnit;
 import java.util.Collection;
 
@@ -236,14 +237,14 @@ public class ReentrantReadWriteLock
         static final int MAX_COUNT      = (1 << SHARED_SHIFT) - 1;
         static final int EXCLUSIVE_MASK = (1 << SHARED_SHIFT) - 1;
 
-        /** Returns the number of shared holds represented in count  */
+        /** Returns the number of shared holds represented in count. */
         static int sharedCount(int c)    { return c >>> SHARED_SHIFT; }
-        /** Returns the number of exclusive holds represented in count  */
+        /** Returns the number of exclusive holds represented in count. */
         static int exclusiveCount(int c) { return c & EXCLUSIVE_MASK; }
 
         /**
          * A counter for per-thread read hold counts.
-         * Maintained as a ThreadLocal; cached in cachedHoldCounter
+         * Maintained as a ThreadLocal; cached in cachedHoldCounter.
          */
         static final class HoldCounter {
             int count = 0;
@@ -303,7 +304,7 @@ public class ReentrantReadWriteLock
          * <p>This allows tracking of read holds for uncontended read
          * locks to be very cheap.
          */
-        private transient Thread firstReader = null;
+        private transient Thread firstReader;
         private transient int firstReaderHoldCount;
 
         Sync() {
diff --git a/luni/src/main/java/java/util/concurrent/package-info.java b/luni/src/main/java/java/util/concurrent/package-info.java
index 51a29e8..afc8ca4 100644
--- a/luni/src/main/java/java/util/concurrent/package-info.java
+++ b/luni/src/main/java/java/util/concurrent/package-info.java
@@ -4,10 +4,6 @@
  * http://creativecommons.org/publicdomain/zero/1.0/
  */
 
-// BEGIN android-note
-// omit links to ForkJoinPool, ForkJoinTask, LinkedTransferQueue, Phaser, TransferQueue
-// END android-note
-
 /**
  * Utility classes commonly useful in concurrent programming.  This
  * package includes a few small standardized extensible frameworks, as
@@ -67,11 +63,20 @@
  * assists in coordinating the processing of groups of
  * asynchronous tasks.
  *
+ * <p>Class {@link java.util.concurrent.ForkJoinPool} provides an
+ * Executor primarily designed for processing instances of {@link
+ * java.util.concurrent.ForkJoinTask} and its subclasses.  These
+ * classes employ a work-stealing scheduler that attains high
+ * throughput for tasks conforming to restrictions that often hold in
+ * computation-intensive parallel processing.
+ *
  * <h2>Queues</h2>
  *
  * The {@link java.util.concurrent.ConcurrentLinkedQueue} class
- * supplies an efficient scalable thread-safe non-blocking FIFO
- * queue.
+ * supplies an efficient scalable thread-safe non-blocking FIFO queue.
+ * The {@link java.util.concurrent.ConcurrentLinkedDeque} class is
+ * similar, but additionally supports the {@link java.util.Deque}
+ * interface.
  *
  * <p>Five implementations in {@code java.util.concurrent} support
  * the extended {@link java.util.concurrent.BlockingQueue}
@@ -85,6 +90,12 @@
  * for producer-consumer, messaging, parallel tasking, and
  * related concurrent designs.
  *
+ * <p>Extended interface {@link java.util.concurrent.TransferQueue},
+ * and implementation {@link java.util.concurrent.LinkedTransferQueue}
+ * introduce a synchronous {@code transfer} method (along with related
+ * features) in which a producer may optionally block awaiting its
+ * consumer.
+ *
  * <p>The {@link java.util.concurrent.BlockingDeque} interface
  * extends {@code BlockingQueue} to support both FIFO and LIFO
  * (stack-based) operations.
@@ -111,7 +122,7 @@
  *
  * <h2>Synchronizers</h2>
  *
- * Four classes aid common special-purpose synchronization idioms.
+ * Five classes aid common special-purpose synchronization idioms.
  * <ul>
  *
  * <li>{@link java.util.concurrent.Semaphore} is a classic concurrency tool.
@@ -124,6 +135,10 @@
  * multiway synchronization point useful in some styles of parallel
  * programming.
  *
+ * <li>A {@link java.util.concurrent.Phaser} provides
+ * a more flexible form of barrier that may be used to control phased
+ * computation among multiple threads.
+ *
  * <li>An {@link java.util.concurrent.Exchanger} allows two threads to
  * exchange objects at a rendezvous point, and is useful in several
  * pipeline designs.
@@ -176,7 +191,7 @@
  *
  * <h2 id="MemoryVisibility">Memory Consistency Properties</h2>
  *
- * <a href="http://java.sun.com/docs/books/jls/third_edition/html/memory.html">
+ * <a href="http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.5">
  * Chapter 17 of the Java Language Specification</a> defines the
  * <i>happens-before</i> relation on memory operations such as reads and
  * writes of shared variables.  The results of a write by one thread are
@@ -243,7 +258,8 @@
  *   in each thread <i>happen-before</i> those subsequent to the
  *   corresponding {@code exchange()} in another thread.
  *
- *   <li>Actions prior to calling {@code CyclicBarrier.await}
+ *   <li>Actions prior to calling {@code CyclicBarrier.await} and
+ *   {@code Phaser.awaitAdvance} (as well as its variants)
  *   <i>happen-before</i> actions performed by the barrier action, and
  *   actions performed by the barrier action <i>happen-before</i> actions
  *   subsequent to a successful return from the corresponding {@code await}