Merge lp:~pbeaman/akiban-persistit/fix_classIndex into lp:akiban-persistit

[Peter Beaman]

This branch heavily modfies the ClassIndex class and adds stronger unit tests. This was done in response to several critical bugs:

https://bugs.launchpad.net/akiban-persistit/+bug/1024857
https://bugs.launchpad.net/akiban-persistit/+bug/1026207
and a deadlock detected while testing.

At issue is that ClassIndex is very old and was never properly tested when used within the scope of a transaction, particularly a transaction that rolls back.

New implementation uses a private transaction scope within a private SessionId to perform all database activity. Before allowing a handle->class mapping to become visible in the cache, ClassIndex first commits the transaction that records it in the _classIndex tree. That transaction is not related to any enclosing transaction due to the use of a unique, private SessionId.

All update operations in the cache are synchronized. This is acceptable because so few updates occur in the lifetime of the system. All cache lookup operations are completed unsynchronized; they are safe by design for concurrent execution.

This branch adds new unit test to exercise multi-threaded operation.

[Peter Beaman (pbeaman)]

Upon reflection I have decided to withdraw this proposal and replace the hash table with a ConcurrentHashMap. Back again soon.

review: Needs Fixing

[Peter Beaman (pbeaman)]

Upon further reflection I have decided to leave the existing hash table implementation. As written it explicitly supports the possibility of multiple versions per class, and does so without a map-of-maps.

Specifically, ClassIndex can track multiple versions of a class named X, differentiated only by their SerialVersionUID values. Different versions of a class get different handles.

In normal operation attempting to decode a Value recorded with a different version of the class than is now available in the classloader at least fails with a ConversionException rather than obscure failures deeper in the deserialization code. (Note that even with standard Java serialization, the ObjectStreamClass information has been removed from the Value and encoded in ClassIndex under the handle. Therefore the ClassIndex must supply the SerialVersionUID for verification.)

In deciding to leave the current implementation I added a unit test for handling multiple versions of the same class. This test uses the javax.tools.JavaCompiler class to create a class file, and therefore this test requires the JDK (specifically tools.jar) to run. This also adds a dependency on Java 6.

review: Needs Resubmitting

[Nathan Williams (nwilliams)]

Could/should Persistit.classIndex be final?

lookupByHandle:
I'm not so sure of our correctness here. AtomicReferenceArray provides atomic operations and volatile access semantics for the elements of the array but that doesn't extend down into the fields of the elements of the array. Specifically, I'm concerned about ClassInfoEntry._next. That field is updated in a synchronized block but accessed outside of one. A simple solution to that would probably be re-checking the list inside the synch block.

I'm also concerned with the growth of the hash table, but it isn't as severe. We save the hash table and search in it. Another thread could be doing this at the same time. Say that 2nd thread gets into the synch block first and updates the three and the map. We'll then find the stored ClassInfo correctly and go to update the table. We bump the size before we check that it wasn't added.

test2a() seems odd or maybe I don't quite get it. We're storing parts of the ClassIndex externally in a map and operating concurrently on it. Why doesn't this get ConcurrentModifcationExceptions regularly? Don't we also want to validate the true map (hash table) in the ClassIndex?

The multiThreaded and the manyClassInfo test seem more appropriate for stress tests, especially the latter given the compilation and additional requirements (JDK6/tools.jar).

review: Needs Fixing

[Peter Beaman (pbeaman)]

Excellent points.

ClassIndex is now final. So is the singleton reference to it in Persistit, and while there I made a bunch of other singletons final also.

ClassInfoEntry's constructor now sets the _next field and is immutable. I believe the memory model guarantee is that the object reference can't be visible until the constructor has finished.

HashTable growth - size now measure entries correctly.

The two multi-xxx tests are pretty quick and not inconsistent with other Persistit "unit" tests so I decided to leave them. But I did get rid of the use of tools.jar and the Compiler by using a much simpler technique.

review: Needs Resubmitting

[Nathan Williams (nwilliams)]

Thanks for the fixes, glad I wasn't off on an incorrect tangent. The makeAClass() hack is a little crazy, but probably better than the requirements of the other one.

So all good by me!

review: Approve

[Akiban Build User (build-akiban)]

There were 2 failures during build/test:

* job persistit-build failed at build number 384: http://172.16.20.104:8080/job/persistit-build/384/

* view must-pass failed: persistit-build is red

review: Needs Fixing

[lp:~pbeaman/akiban-persistit/fix_classIndex]

340. By Peter Beaman on 2012-07-20

Add license header

[Peter Beaman (pbeaman)]

Approving again after adding missing license header.

review: Approve

=== modified file 'src/main/java/com/persistit/ClassIndex.java'
--- src/main/java/com/persistit/ClassIndex.java	2012-05-25 18:50:59 +0000
+++ src/main/java/com/persistit/ClassIndex.java	2012-07-20 22:51:17 +0000
@@ -46,39 +46,49 @@
  * Note that certain handles for common classes are pre-assigned, and therefore
  * are not translated through this class. See {@link Value} for details.
  * </p>
+ * <p>
+ * Implementation note: this class implements a specialized hash table in which
+ * entries are never removed. Almost always this class returns a value by
+ * finding it in the hash table; the lookup is carefully designed to be
+ * threadsafe without requiring synchronization. Only in the event of a cache
+ * miss is there execution of a synchronized block which may read and/or update
+ * the _classIndex tree.
+ * </p>
  * 
  * @version 1.1
  */
-class ClassIndex {
+final class ClassIndex {
     private final static int INITIAL_CAPACITY = 123;
 
     private final static String BY_HANDLE = "byHandle";
     private final static String BY_NAME = "byName";
     private final static String NEXT_ID = "nextId";
+    private final static int EXTRA_FACTOR = 2;
+
     final static String CLASS_INDEX_TREE_NAME = "_classIndex";
 
-    private AtomicInteger _size = new AtomicInteger();
-    private Persistit _persistit;
+    private final AtomicInteger _size = new AtomicInteger();
+    private final Persistit _persistit;
+    private final SessionId _sessionId = new SessionId();
 
-    private AtomicReferenceArray<ClassInfoEntry> _hashById = new AtomicReferenceArray<ClassInfoEntry>(INITIAL_CAPACITY);
-    private AtomicReferenceArray<ClassInfoEntry> _hashByName = new AtomicReferenceArray<ClassInfoEntry>(
+    private volatile AtomicReferenceArray<ClassInfoEntry> _hashTable = new AtomicReferenceArray<ClassInfoEntry>(
             INITIAL_CAPACITY);
-    private ClassInfoEntry _knownNull = null;
 
     private int _testIdFloor = Integer.MIN_VALUE;
-    
+    private AtomicInteger _cacheMisses = new AtomicInteger();
+    private AtomicInteger _discardedDuplicates = new AtomicInteger();
+
     /**
      * A structure holding a ClassInfo, plus links to other related
      * <code>ClassInfoEntry</code>s.
      */
     private static class ClassInfoEntry {
-        ClassInfoEntry _nextByIdHash;
-        ClassInfoEntry _nextByNameHash;
-
-        ClassInfo _classInfo;
-
-        ClassInfoEntry(ClassInfo ci) {
+        final ClassInfoEntry _next;
+        final ClassInfo _classInfo;
+
+        ClassInfoEntry(ClassInfo ci, ClassInfoEntry next) {
             _classInfo = ci;
+            _next = next;
         }
     }
 
@@ -102,33 +112,32 @@
     }
 
     /**
-     * Looks up and returns the ClassInfo for an integer handle. This is used
-     * when decoding an <code>Object</code> from a
-     * <code>com.persistit.Value</code> to associate the encoded integer handle
-     * value with the corresponding class.
+     * Look up and return the ClassInfo for an integer handle. This is used when
+     * decoding an <code>Object</code> from a <code>com.persistit.Value</code>
+     * to associate the encoded integer handle value with the corresponding
+     * class.
      * 
      * @param handle
      *            The handle
      * @return The associated ClassInfo, or <i>null</i> if there is none.
      */
     public ClassInfo lookupByHandle(int handle) {
-        ClassInfoEntry cie = _hashById.get(handle % _hashById.length());
+        AtomicReferenceArray<ClassInfoEntry> hashTable = _hashTable;
+        ClassInfoEntry cie = hashTable.get(handle % hashTable.length());
         while (cie != null) {
             if (cie._classInfo.getHandle() == handle)
                 return cie._classInfo;
-            cie = cie._nextByIdHash;
-        }
-        cie = _knownNull;
-        while (cie != null) {
-            if (cie._classInfo.getHandle() == handle)
-                return null;
-            cie = cie._nextByIdHash;
-        }
+            cie = cie._next;
+        }
+
+        _cacheMisses.incrementAndGet();
+
         synchronized (this) {
+            _sessionId.assign();
             Exchange ex = null;
             try {
                 ex = getExchange();
-                Transaction txn = ex.getTransaction();
+                final Transaction txn = ex.getTransaction();
                 txn.begin();
                 try {
                     ex.clear().append(BY_HANDLE).append(handle).fetch();
@@ -152,7 +161,7 @@
                     Class<?> cl = Class.forName(storedName, false, Thread.currentThread().getContextClassLoader());
 
                     long suid = 0;
-                    ObjectStreamClass osc = ObjectStreamClass.lookup(cl);
+                    ObjectStreamClass osc = ObjectStreamClass.lookupAny(cl);
                     if (osc != null)
                         suid = osc.getSerialVersionUID();
                     if (storedSuid != suid) {
@@ -164,9 +173,8 @@
                     return ci;
                 } else {
                     ClassInfo ci = new ClassInfo(null, 0, handle, null);
-                    cie = _knownNull;
-                    _knownNull = new ClassInfoEntry(ci);
-                    _knownNull._nextByIdHash = cie;
+                    hashClassInfo(ci);
+                    return ci;
                 }
             } catch (ClassNotFoundException cnfe) {
                 throw new ConversionException(cnfe);
@@ -176,13 +184,11 @@
                 if (ex != null)
                     releaseExchange(ex);
             }
-            // TODO - lookup in ClassIndex Exchange
-            return null;
         }
     }
 
     /**
-     * Looks up and returns a ClassInfo for a class. This is used when encoding
+     * Look up and return the ClassInfo for a class. This is used when encoding
      * an <code>Object</code> into a <code>com.persistit.Value</code>.
      * 
      * @param clazz
@@ -190,20 +196,21 @@
      * @return The ClassInfo for the specified Class.
      */
     public ClassInfo lookupByClass(Class<?> clazz) {
+        AtomicReferenceArray<ClassInfoEntry> hashTable = _hashTable;
 
         ObjectStreamClass osc = null;
         long suid = 0;
 
         int nh = clazz.getName().hashCode() & 0x7FFFFFFF;
-        ClassInfoEntry cie = _hashByName.get(nh % _hashById.length());
+        ClassInfoEntry cie = hashTable.get(nh % hashTable.length());
 
         while (cie != null) {
-            if (cie._classInfo.getDescribedClass().equals(clazz)) {
+            if (clazz.equals(cie._classInfo.getDescribedClass())) {
                 return cie._classInfo;
             }
-            if (cie._classInfo.getName().equals(clazz.getName())) {
+            if (cie._classInfo.getDescribedClass() != null && cie._classInfo.getName().equals(clazz.getName())) {
                 if (osc == null) {
-                    osc = ObjectStreamClass.lookup(clazz);
+                    osc = ObjectStreamClass.lookupAny(clazz);
                     if (osc != null) {
                         suid = osc.getSerialVersionUID();
                     }
@@ -212,22 +219,49 @@
                     return cie._classInfo;
                 }
             }
-            cie = cie._nextByNameHash;
-        }
+            cie = cie._next;
+        }
+
+        if (osc == null) {
+            osc = ObjectStreamClass.lookupAny(clazz);
+        }
+        if (osc != null) {
+            suid = osc.getSerialVersionUID();
+        }
+
+        _cacheMisses.incrementAndGet();
+
+        /**
+         * To update the tree, this class uses a unique SessionId and results in
+         * using a unique Transaction context unrelated to the application
+         * context. Therefore if an application does this:
+         * 
+         * <pre>
+         * <code> 
+         * txn.begin(); 
+         * value.put(new SomeClass()); 
+         * txn.rollback();
+         * txn.end(); 
+         * </code>
+         * </pre>
+         * 
+         * the class SomeClass will be registered even though the enclosing
+         * transaction rolled back. This is important because other concurrent
+         * threads may have started using the handle for SomeClass. Therefore
+         * this class ensures that a non-nested transaction to insert the new
+         * ClassInfo into the system volume has committed before adding the
+         * handle to the hash table. </p>
+         */
 
         synchronized (this) {
-            if (osc == null) {
-                osc = ObjectStreamClass.lookup(clazz);
-            }
-            if (osc != null) {
-                suid = osc.getSerialVersionUID();
-            }
+            final SessionId saveSessionId = _persistit.getSessionId();
             Exchange ex = null;
             try {
+                _persistit.setSessionId(_sessionId);
                 ex = getExchange();
+                final Transaction txn = ex.getTransaction();
                 final ClassInfo ci;
                 final int handle;
-                Transaction txn = ex.getTransaction();
                 txn.begin();
                 ex.clear().append(BY_NAME).append(clazz.getName()).append(suid).fetch();
                 Value value = ex.getValue();
@@ -274,8 +308,10 @@
             } catch (PersistitException pe) {
                 throw new ConversionException(pe);
             } finally {
-                if (ex != null)
+                if (ex != null) {
                     releaseExchange(ex);
+                }
+                _persistit.setSessionId(saveSessionId);
             }
         }
     }
@@ -295,45 +331,50 @@
     }
 
     private void hashClassInfo(ClassInfo ci) {
-        int size = _size.incrementAndGet();
-        if (size * 2 > _hashById.length()) {
-            AtomicReferenceArray<ClassInfoEntry> hashById = new AtomicReferenceArray<ClassInfoEntry>(size * 2);
-            AtomicReferenceArray<ClassInfoEntry> hashByName = new AtomicReferenceArray<ClassInfoEntry>(size * 2);
-            for (int i = 0; i < _hashById.length(); i++) {
-                ClassInfoEntry cie = _hashById.get(i);
+        int size = _size.get();
+        if (size * EXTRA_FACTOR > _hashTable.length()) {
+            int discarded = _discardedDuplicates.get();
+            AtomicReferenceArray<ClassInfoEntry> newHashTable = new AtomicReferenceArray<ClassInfoEntry>(EXTRA_FACTOR
+                    * 2 * size);
+            for (int i = 0; i < _hashTable.length(); i++) {
+                ClassInfoEntry cie = _hashTable.get(i);
                 while (cie != null) {
-                    addHashEntry(cie._classInfo, hashById, hashByName);
-                    cie = cie._nextByIdHash;
+                    addHashEntry(newHashTable, cie._classInfo);
+                    cie = cie._next;
                 }
             }
-            _hashById = hashById;
-            _hashByName = hashByName;
-        }
-        addHashEntry(ci, _hashById, _hashByName);
-    }
-
-    private void addHashEntry(final ClassInfo ci, final AtomicReferenceArray<ClassInfoEntry> hashById,
-            final AtomicReferenceArray<ClassInfoEntry> hashByName) {
-        ClassInfoEntry cie = new ClassInfoEntry(ci);
-        int handle = ci.getHandle();
-        int nh = ci.getName().hashCode() & 0x7FFFFFFF;
-
-        ClassInfoEntry cie1 = hashById.get(handle % hashById.length());
-        ClassInfoEntry cie2 = hashByName.get(nh % hashByName.length());
-
-        cie._nextByIdHash = cie1;
-        cie._nextByNameHash = cie2;
-
-        hashById.set(handle % hashById.length(), cie);
-        hashByName.set(nh % hashByName.length(), cie);
-
-        ClassInfoEntry cie3 = _knownNull;
-        while (cie3 != null) {
-            if (cie3._classInfo.getHandle() != handle) {
-                _knownNull = cie3._nextByIdHash;
+            _hashTable = newHashTable;
+            _discardedDuplicates.set(discarded);
+        }
+        addHashEntry(_hashTable, ci);
+    }
+
+    private void addHashEntry(final AtomicReferenceArray<ClassInfoEntry> hashTable, ClassInfo ci) {
+        final int hh = ci.getHandle() % hashTable.length();
+        final int nh = ci.getDescribedClass() == null ? -1
+                : ((ci.getDescribedClass().getName().hashCode() & 0x7FFFFFFF) % hashTable.length());
+        boolean added = addHashEntry(hashTable, ci, hh);
+        if (nh != -1 && nh != hh) {
+            added |= addHashEntry(hashTable, ci, nh);
+        }
+        if (!added) {
+            _discardedDuplicates.incrementAndGet();
+        }
+    }
+
+    private boolean addHashEntry(final AtomicReferenceArray<ClassInfoEntry> hashTable, ClassInfo ci, final int hash) {
+        ClassInfoEntry cie = hashTable.get(hash);
+        while (cie != null) {
+            if (ci.equals(cie._classInfo)) {
+                return false;
             }
-            cie3 = cie3._nextByIdHash;
+            cie = cie._next;
         }
+        cie = hashTable.get(hash);
+        ClassInfoEntry newCie = new ClassInfoEntry(ci, cie);
+        hashTable.set(hash, newCie);
+        _size.incrementAndGet();
+        return true;
     }
 
     private Exchange getExchange() throws PersistitException {
@@ -348,22 +389,45 @@
     private void releaseExchange(Exchange ex) {
         _persistit.releaseExchange(ex);
     }
-    
+
     /**
-     * For unit tests only. Next class ID handle will be at least
-     * as large as this.
+     * For unit tests only. Next class ID handle will be at least as large as
+     * this.
+     * 
      * @param id
      */
     void setTestIdFloor(final int id) {
         _testIdFloor = id;
     }
-    
+
     /**
-     * For unit tests only.  Clears all entries.
+     * For unit tests only. Clears all entries.
+     * 
      * @throws PersistitException
      */
     void clearAllEntries() throws PersistitException {
         getExchange().removeAll();
-    }
-
+        _cacheMisses.set(0);
+        _discardedDuplicates.set(0);
+    }
+
+    /**
+     * For unit tests only.
+     * 
+     * @return count (since beginning or last call to {@link #clearAllEntries()}
+     *         ) of cache misses.
+     */
+    int getCacheMisses() {
+        return _cacheMisses.get();
+    }
+
+    /**
+     * For unit tests only.
+     * 
+     * @return count (since beginning or last call to {@link #clearAllEntries()}
+     *         ) of discarded duplicates.
+     */
+    int getDiscardedDuplicates() {
+        return _discardedDuplicates.get();
+    }
 }

=== modified file 'src/main/java/com/persistit/ClassInfo.java'
--- src/main/java/com/persistit/ClassInfo.java	2012-05-25 18:50:59 +0000
+++ src/main/java/com/persistit/ClassInfo.java	2012-07-20 22:51:17 +0000
@@ -44,7 +44,7 @@
     public boolean equals(final Object object) {
         if (object instanceof ClassInfo) {
             ClassInfo ci = (ClassInfo) object;
-            if (_class.equals(ci._class) && _handle == ci._handle && _suid == ci._suid) {
+            if (equals(_class, ci._class) && _handle == ci._handle && _suid == ci._suid) {
                 return true;
             }
         }
@@ -91,5 +91,9 @@
     public ObjectStreamClass getClassDescriptor() {
         return _osc;
     }
+    
+    private boolean equals(Class<?> a, Class<?> b) {
+        return a == null ? b == null : a.equals(b);
+    }
 }
 

=== modified file 'src/main/java/com/persistit/Persistit.java'
--- src/main/java/com/persistit/Persistit.java	2012-06-30 15:12:11 +0000
+++ src/main/java/com/persistit/Persistit.java	2012-07-20 22:51:17 +0000
@@ -397,23 +397,22 @@
     private final HashMap<Integer, BufferPool> _bufferPoolTable = new HashMap<Integer, BufferPool>();
     private final ArrayList<Volume> _volumes = new ArrayList<Volume>();
 
-    private AtomicBoolean _initialized = new AtomicBoolean();
-    private AtomicBoolean _closed = new AtomicBoolean();
-    private AtomicBoolean _fatal = new AtomicBoolean();
+    private final AtomicBoolean _initialized = new AtomicBoolean();
+    private final AtomicBoolean _closed = new AtomicBoolean();
+    private final AtomicBoolean _fatal = new AtomicBoolean();
 
     private long _beginCloseTime;
     private long _nextCloseTime;
 
     private final LogBase _logBase = new LogBase();
 
-    private AtomicBoolean _suspendShutdown = new AtomicBoolean(false);
-    private AtomicBoolean _suspendUpdates = new AtomicBoolean(false);
+    private final AtomicBoolean _suspendShutdown = new AtomicBoolean(false);
+    private final AtomicBoolean _suspendUpdates = new AtomicBoolean(false);
 
     private UtilControl _localGUI;
 
-    private AtomicReference<CoderManager> _coderManager = new AtomicReference<CoderManager>();
-
-    private ClassIndex _classIndex = new ClassIndex(this);
+    private final AtomicReference<CoderManager> _coderManager = new AtomicReference<CoderManager>();
+    private final ClassIndex _classIndex = new ClassIndex(this);
 
     private final ThreadLocal<SessionId> _sessionIdThreadLocal = new ThreadLocal<SessionId>() {
         @Override

=== modified file 'src/test/java/com/persistit/ClassIndexTest.java'
--- src/test/java/com/persistit/ClassIndexTest.java	2012-05-25 18:50:59 +0000
+++ src/test/java/com/persistit/ClassIndexTest.java	2012-07-20 22:51:17 +0000
@@ -21,22 +21,50 @@
 package com.persistit;
 
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
 import static org.junit.Assert.assertNull;
 import static org.junit.Assert.assertTrue;
 
+import java.io.InputStream;
+import java.io.Serializable;
 import java.lang.reflect.Field;
-import java.util.HashMap;
+import java.util.HashSet;
 import java.util.Map;
+import java.util.Set;
+import java.util.concurrent.ConcurrentHashMap;
 
 import org.junit.Test;
 
+import com.persistit.Transaction.CommitPolicy;
 import com.persistit.unit.PersistitUnitTestCase;
+import com.persistit.util.Util;
 
 public class ClassIndexTest extends PersistitUnitTestCase {
 
+    /**
+     * Arbitrary constant chosen to be found exactly once in the MockSerailizableObject
+     * class file. 
+     */
+    final static long SUID_CONSTANT = 0xF3E1D4C1B5A99286L;
+    private final static String MOCK_SERIALIZABLE_CLASS_NAME = "MockSerializableObject";
+
     private int _maxHandle = 0;
 
-    final Map<Integer, ClassInfo> map = new HashMap<Integer, ClassInfo>();
+    final Map<Integer, ClassInfo> map = new ConcurrentHashMap<Integer, ClassInfo>();
+
+    @SuppressWarnings("serial")
+    public static class A implements Serializable {
+
+    }
+
+    @SuppressWarnings("serial")
+    public static class B implements Serializable {
+
+    }
+
+    public static class C {
+
+    }
 
     @Override
     public void tearDown() throws Exception {
@@ -45,7 +73,7 @@
     }
 
     @Test
-    public void testOneClassInfo() throws Exception {
+    public void oneClassInfo() throws Exception {
         final ClassIndex cx = _persistit.getClassIndex();
         cx.registerClass(this.getClass());
         ClassInfo ci = cx.lookupByClass(this.getClass());
@@ -54,18 +82,22 @@
     }
 
     @Test
-    public void test2() throws Exception {
+    public void manyClassInfo() throws Exception {
         _maxHandle = 0;
         final ClassIndex cx = _persistit.getClassIndex();
         Class<?> clazz = Persistit.class;
         test2a(cx, clazz);
+
+        assertEquals("Cache misses should match map size", map.size(), cx.getCacheMisses()
+                - cx.getDiscardedDuplicates());
+
         for (int handle = 0; handle < _maxHandle + 10; handle++) {
-            assertEquals(map.get(handle), cx.lookupByHandle(handle));
+            assertTrue(equals(map.get(handle), cx.lookupByHandle(handle)));
         }
 
         final ClassIndex cy = new ClassIndex(_persistit);
         for (int handle = 0; handle < _maxHandle + 10; handle++) {
-            assertEquals(map.get(handle), cy.lookupByHandle(handle));
+            assertTrue(equals(map.get(handle), cy.lookupByHandle(handle)));
         }
         for (int handle = 0; handle < _maxHandle + 10; handle++) {
             ClassInfo ci = map.get(handle);
@@ -84,6 +116,143 @@
         System.out.println(cx.size() + " classes");
     }
 
+    @Test
+    public void multiThreaded() throws Exception {
+        final int threadCount = 50;
+
+        final Thread[] threads = new Thread[threadCount];
+        for (int i = 0; i < threadCount; i++) {
+            final int index = i;
+            threads[i] = new Thread(new Runnable() {
+                public void run() {
+                    final Transaction transaction = _persistit.getTransaction();
+                    for (int k = 0; k < 10; k++) {
+                        try {
+                            transaction.begin();
+                            try {
+                                test2a(_persistit.getClassIndex(), Persistit.class);
+                                if ((index % 3) == 0) {
+                                    transaction.rollback();
+                                } else {
+                                    transaction.commit();
+                                }
+                            } finally {
+                                transaction.end();
+                            }
+                        } catch (Exception e) {
+                            e.printStackTrace();
+                        }
+                    }
+                }
+            });
+        }
+        for (int i = 0; i < threadCount; i++) {
+            threads[i].start();
+        }
+        for (int i = 0; i < threadCount; i++) {
+            threads[i].join();
+        }
+
+        final ClassIndex cx = _persistit.getClassIndex();
+
+        /*
+         * Verify that almost all lookups were satisfied from cache. There
+         * should be one "cache miss" for every class in the map. There may be
+         * more: these are caused by concurrent execution and are explicitly
+         * permitted - they will happen only rarely and only when multiple
+         * threads are contending to register a new class. Such instances are
+         * safely discarded and the following adjusts the cache miss count by
+         * the number so discarded.
+         */
+        assertEquals("Cache misses should match map size", map.size(), cx.getCacheMisses()
+                - cx.getDiscardedDuplicates());
+
+        for (int handle = 0; handle < _maxHandle + 10; handle++) {
+            assertTrue(equals(map.get(handle), cx.lookupByHandle(handle)));
+        }
+
+    }
+
+    @Test
+    public void rollback() throws Exception {
+        Exchange ex = _persistit.getExchange("persistit", "ClassIndexTest", true);
+        Transaction txn = ex.getTransaction();
+        txn.begin();
+        try {
+
+            ex.getValue().put(new A());
+            ex.to("A").store();
+            ex.getValue().put(new B());
+            ex.to("B").store();
+            txn.rollback();
+        } finally {
+            txn.end();
+        }
+
+        txn.begin();
+        try {
+            ex.getValue().put(new B());
+            ex.to("B").store();
+            ex.getValue().put(new A());
+            ex.to("A").store();
+            txn.commit(CommitPolicy.HARD);
+        } finally {
+            txn.end();
+        }
+
+        final Configuration config = _persistit.getConfiguration();
+        _persistit.crash();
+        _persistit = new Persistit();
+        _persistit.initialize(config);
+        ex = _persistit.getExchange("persistit", "ClassIndexTest", false);
+        Object b = ex.to("B").fetch().getValue().get();
+        Object a = ex.to("A").fetch().getValue().get();
+        assertTrue("Incorrect class", a instanceof A);
+        assertTrue("Incorrect class", b instanceof B);
+    }
+
+    @Test
+    public void knownNull() throws Exception {
+        ClassIndex cx = _persistit.getClassIndex();
+        final ClassInfo ci = cx.lookupByHandle(12345);
+        assertEquals("Should return cached known null", ci, cx.lookupByHandle(12345));
+    }
+
+    @Test
+    public void multipleVersions() throws Exception {
+        ClassIndex cx = _persistit.getClassIndex();
+        cx.clearAllEntries();
+        int count = 10;
+        final Class<?>[] classes = new Class<?>[count];
+        for (int i = 0; i < count; i++) {
+            classes[i] = makeAClass(i);
+            assertNotNull("this test requires tools.jar on the classpath", classes[i]);
+            cx.lookupByClass(classes[i]);
+        }
+        assertEquals("Each version should be unique", count, cx.getCacheMisses());
+        Set<Integer> handles = new HashSet<Integer>();
+        for (int i = 0; i < count; i++) {
+            ClassInfo ci = cx.lookupByClass(classes[i]);
+            int handle = ci.getHandle();
+            assertTrue("Handles must be unique", handles.add(handle));
+        }
+        assertEquals("Each version should be in cache", count, cx.getCacheMisses());
+        for (final Integer handle : handles) {
+            ClassInfo ci = cx.lookupByHandle(handle);
+            assertEquals("Lookup by handle and class must match", ci, cx.lookupByClass(ci.getDescribedClass()));
+        }
+    }
+
+    private boolean equals(final ClassInfo a, final ClassInfo b) {
+        if (a == b) {
+            return true;
+        }
+        if (a == null) {
+            return b.getDescribedClass() == null;
+        }
+        return a.equals(b);
+    }
+
     private void test2a(final ClassIndex cx, final Class<?> clazz) throws Exception {
         if (clazz.isPrimitive()) {
             return;
@@ -103,13 +272,44 @@
         } else {
             assert (copy.equals(ci));
         }
-
-    }
-
-    @Override
-    public void runAllTests() throws Exception {
-        // TODO Auto-generated method stub
-
+    }
+
+    private static Class<?> makeAClass(final long suid) throws Exception {
+        InputStream is = ClassIndexTest.class.getClassLoader().getResourceAsStream(
+                "com/persistit/" + MOCK_SERIALIZABLE_CLASS_NAME + "_classBytes");
+        final byte[] bytes = new byte[10000];
+        final int length = is.read(bytes);
+        replaceSuid(bytes, suid);
+        ClassLoader cl = new ClassLoader(ClassIndexTest.class.getClassLoader()) {
+            public Class<?> loadClass(final String name) {
+                if (name.contains(MOCK_SERIALIZABLE_CLASS_NAME)) {
+                    return defineClass(name, bytes, 0, length);
+                } else {
+                    try {
+                        return ClassIndexTest.class.getClassLoader().loadClass(name);
+                    } catch (Exception e) {
+                        throw new RuntimeException(e);
+                    }
+                }
+            }
+        };
+        return cl.loadClass("com.persistit." + MOCK_SERIALIZABLE_CLASS_NAME);
+    }
+
+    private final static void replaceSuid(final byte[] bytes, final long suid) {
+        boolean replaced = false;
+        for (int i = 0; i < bytes.length; i++) {
+            boolean found = true;
+            for (int j = 0; found && j < 8; j++) {
+                found &= ((bytes[i + j] & 0xFF) == ((SUID_CONSTANT >>> (56 - j * 8)) & 0xFF));
+            }
+            if (found) {
+                assertTrue("Found multiple instances of SUID_CONSTANT", !replaced);
+                Util.putLong(bytes, i, suid);
+                replaced = true;
+            }
+        }
+        assertTrue("Did not find SUID_CONSTANT", replaced);
     }
 
 }

=== added file 'src/test/java/com/persistit/MockSerializableObject.java'
--- src/test/java/com/persistit/MockSerializableObject.java	1970-01-01 00:00:00 +0000
+++ src/test/java/com/persistit/MockSerializableObject.java	2012-07-20 22:51:17 +0000
@@ -0,0 +1,29 @@
+/**
+ * Copyright © 2011-2012 Akiban Technologies, Inc.  All rights reserved.
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as
+ * published by the Free Software Foundation, version 3 (only) of the
+ * License.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ * 
+ * This program may also be available under different license terms. For more
+ * information, see www.akiban.com or contact [e-mail].
+ */
+
+package com.persistit;
+
+import java.io.Serializable;
+
+public class MockSerializableObject implements Serializable {
+
+    private static final long serialVersionUID = ClassIndexTest.SUID_CONSTANT;
+    
+}

=== added file 'src/test/resources/com/persistit/MockSerializableObject_classBytes'
Binary files src/test/resources/com/persistit/MockSerializableObject_classBytes	1970-01-01 00:00:00 +0000 and src/test/resources/com/persistit/MockSerializableObject_classBytes	2012-07-20 22:51:17 +0000 differ