Merge lp:~pbeaman/akiban-persistit/fix-1058254-join-corrupts-keys into lp:akiban-persistit

[Peter Beaman]

Bug fixes for 1058254 Join on range delete can change successor keys and 1022567 Stress test failure in deallocateGarbageChain.

The primary change is in the calculation of newEbc in Buffer#join. The original code ignored the possibility if page A and C are being joined where A->B and B->C, then the ebc for some key on page B could be less than the value computed by joinMeasure. That case is now handled and a small unit test is provided to exercise that code.

Since 1058254 was found while hunting 1022567, and because the fix for 1022567 involves only the removal of a condition in the assert statement that fired, that change is also included in this branch. However, note that the unit test for this is a bit tricky and requires an enhancement of the ThreadSequencer code to permit a condition to be tested.

[Nathan Williams (nwilliams)]

I know I asked you last week but have forgotten. Why is it legitimate for the right pointer to already be the garbage root?

This looks good otherwise I think.

review: Needs Information

[Peter Beaman (pbeaman)]

I added an explanation to the original bug at https://bugs.launchpad.net/akiban-persistit/+bug/1022567. The unit test Bug1022567Test included in this proposal was used to demonstrate the feasibility of this mechanism.

[Nathan Williams (nwilliams)]

Thanks for the explanation. Makes sense to me.

review: Approve

[Akiban Build User (build-akiban)]

There were 2 failures during build/test:

* job system-tests-mtr failed at build number 2585: http://172.16.20.104:8080/job/system-tests-mtr/2585/

* view must-pass failed: system-tests-mtr is red

review: Needs Fixing

[Peter Beaman (pbeaman)]

Dopey problem. Re-approving.

=== modified file 'src/main/java/com/persistit/Buffer.java'
--- src/main/java/com/persistit/Buffer.java	2012-09-27 18:33:06 +0000
+++ src/main/java/com/persistit/Buffer.java	2012-09-28 22:19:23 +0000
@@ -2448,7 +2448,25 @@
         final long measureRight = buffer.joinMeasure(KEY_BLOCK_START, foundAt2);
         kbData = buffer.getInt(foundAt2);
         final int oldEbc = decodeKeyBlockEbc(kbData);
-        final int newEbc = Math.min(oldEbc, Math.min((int) (measureLeft >>> 32), (int) (measureRight >>> 32)));
+
+        final int newEbc;
+        if (_rightSibling == buffer._page) {
+            /*
+             * Pages are are contiguous so first key of right sibling is
+             * identical to max key of the current page.
+             */
+            newEbc = Math.min(oldEbc, Math.min((int) (measureLeft >>> 32), (int) (measureRight >>> 32)));
+        } else {
+            /*
+             * Since pages are not contiguous, we need to extract the max key
+             * from the current page and compute the ebc from it.
+             */
+            keyAt(foundAt1, indexKey);
+            final int firstUnique = indexKey.firstUniqueByteIndex(spareKey);
+            newEbc = Math.min(Math.min(oldEbc, firstUnique),
+                    Math.min((int) (measureLeft >>> 32), (int) (measureRight >>> 32)));
+        }
+
         tail = decodeKeyBlockTail(kbData);
         tbData = buffer.getInt(tail);
 

=== modified file 'src/main/java/com/persistit/Exchange.java'
--- src/main/java/com/persistit/Exchange.java	2012-09-27 18:23:17 +0000
+++ src/main/java/com/persistit/Exchange.java	2012-09-28 22:19:23 +0000
@@ -33,6 +33,7 @@
 import static com.persistit.Key.LTEQ;
 import static com.persistit.Key.RIGHT_GUARD_KEY;
 import static com.persistit.Key.maxStorableKeySize;
+import static com.persistit.util.SequencerConstants.DEALLOCATE_CHAIN_A;
 import static com.persistit.util.SequencerConstants.WRITE_WRITE_STORE_A;
 import static com.persistit.util.ThreadSequencer.sequence;
 
@@ -3523,6 +3524,7 @@
                     left = lc._deallocLeftPage;
                     right = lc._deallocRightPage;
                     if (left != 0) {
+                        sequence(DEALLOCATE_CHAIN_A);
                         _volume.getStructure().deallocateGarbageChain(left, right);
                         lc._deallocLeftPage = 0;
                         lc._deallocRightPage = 0;

=== modified file 'src/main/java/com/persistit/MVV.java'
--- src/main/java/com/persistit/MVV.java	2012-09-27 22:17:34 +0000
+++ src/main/java/com/persistit/MVV.java	2012-09-28 22:19:23 +0000
@@ -316,7 +316,7 @@
              */
             to++;
             int next = to;
-            
+
             while (next < end) {
                 final long curVersion = getVersion(target, to);
                 final int vlength = getLength(target, to);
@@ -342,7 +342,7 @@
                         next = to;
                     }
                 } else if (curVersion > versionHandle) {
-                    if  (vh2ts(versionHandle) != vh2ts(curVersion)) {
+                    if (vh2ts(versionHandle) != vh2ts(curVersion)) {
                         throw new IllegalStateException("Versions out of order");
                     }
                     remainder = end - to;

=== modified file 'src/main/java/com/persistit/VolumeStructure.java'
--- src/main/java/com/persistit/VolumeStructure.java	2012-09-27 18:22:25 +0000
+++ src/main/java/com/persistit/VolumeStructure.java	2012-09-28 22:19:23 +0000
@@ -541,8 +541,7 @@
                 try {
                     final long garbagePage = getGarbageRoot();
                     if (garbagePage != 0) {
-                        if (left == garbagePage || right == garbagePage) {
-                            Debug.$assert0.t(false);
+                        if (left == garbagePage) {
                             throw new IllegalStateException("De-allocating page that is already garbage: " + "root="
                                     + garbagePage + " left=" + left + " right=" + right);
                         }

=== modified file 'src/main/java/com/persistit/util/SequencerConstants.java'
--- src/main/java/com/persistit/util/SequencerConstants.java	2012-08-24 13:57:19 +0000
+++ src/main/java/com/persistit/util/SequencerConstants.java	2012-09-28 22:19:23 +0000
@@ -93,4 +93,14 @@
     int[][] LONG_RECORD_ALLOCATE_SCHEDULED = new int[][] { array(LONG_RECORD_ALLOCATE_B),
             array(LONG_RECORD_ALLOCATE_A, LONG_RECORD_ALLOCATE_B) };
 
+    /*
+     * Used in testing delete/deallocate sequence in Bug1022567Test
+     */
+    int DEALLOCATE_CHAIN_A = allocate("DEALLOCATE_CHAIN_A");
+    int DEALLOCATE_CHAIN_B = allocate("DEALLOCATE_CHAIN_B");
+    int DEALLOCATE_CHAIN_C = allocate("DEALLOCATE_CHAIN_C");
+    int[][] DEALLOCATE_CHAIN_SCHEDULED = new int[][] { array(DEALLOCATE_CHAIN_A, DEALLOCATE_CHAIN_B),
+            array(DEALLOCATE_CHAIN_B), array(DEALLOCATE_CHAIN_A, DEALLOCATE_CHAIN_C),
+            array(DEALLOCATE_CHAIN_A, DEALLOCATE_CHAIN_C) };
+
 }

=== modified file 'src/main/java/com/persistit/util/ThreadSequencer.java'
--- src/main/java/com/persistit/util/ThreadSequencer.java	2012-08-24 13:57:19 +0000
+++ src/main/java/com/persistit/util/ThreadSequencer.java	2012-09-28 22:19:23 +0000
@@ -110,8 +110,16 @@
 
     private final static List<String> LOCATIONS = new ArrayList<String>();
 
+    private final static List<Condition> CONDITIONS = new ArrayList<Condition>();
+
     private final static int MAX_LOCATIONS = 64;
 
+    public static class Condition {
+        public boolean enabled() {
+            return true;
+        }
+    }
+
     public synchronized static int allocate(final String locationName) {
         for (final String alreadyRegistered : LOCATIONS) {
             assert !alreadyRegistered.equals(locationName) : "Location name " + locationName + " is already in use";
@@ -119,6 +127,7 @@
         final int value = LOCATIONS.size();
         assert value < MAX_LOCATIONS : "Too many ThreadSequence locations";
         LOCATIONS.add(locationName);
+        CONDITIONS.add(new Condition());
         return value;
     }
 
@@ -167,6 +176,10 @@
         }
     }
 
+    public static void setCondition(final int location, final Condition condition) {
+        CONDITIONS.set(location, condition);
+    }
+
     public static String sequencerHistory() {
         return ENABLED_SEQUENCER.history();
     }
@@ -369,6 +382,10 @@
             assert location >= 0 && location < MAX_LOCATIONS : "Location must be between 0 and 63, inclusive";
             Semaphore semaphore = null;
 
+            if (!CONDITIONS.get(location).enabled()) {
+                return;
+            }
+
             synchronized (this) {
                 if ((_enabled & (1L << location)) == 0) {
                     return;

=== added file 'src/test/java/com/persistit/Bug1022567Test.java'
--- src/test/java/com/persistit/Bug1022567Test.java	1970-01-01 00:00:00 +0000
+++ src/test/java/com/persistit/Bug1022567Test.java	2012-09-28 22:19:23 +0000
@@ -0,0 +1,235 @@
+/**
+ * Copyright © 2012 Akiban Technologies, Inc.  All rights reserved.
+ * 
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ * 
+ * This program may also be available under different license terms.
+ * For more information, see www.akiban.com or contact [e-mail].
+ * 
+ * Contributors:
+ * Akiban Technologies, Inc.
+ */
+
+package com.persistit;
+
+import static com.persistit.unit.UnitTestProperties.VOLUME_NAME;
+import static com.persistit.util.SequencerConstants.DEALLOCATE_CHAIN_A;
+import static com.persistit.util.SequencerConstants.DEALLOCATE_CHAIN_B;
+import static com.persistit.util.SequencerConstants.DEALLOCATE_CHAIN_C;
+import static com.persistit.util.SequencerConstants.DEALLOCATE_CHAIN_SCHEDULED;
+import static com.persistit.util.ThreadSequencer.addSchedules;
+import static com.persistit.util.ThreadSequencer.enableSequencer;
+import static com.persistit.util.ThreadSequencer.sequence;
+import static com.persistit.util.ThreadSequencer.setCondition;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Properties;
+
+import org.junit.Test;
+
+import com.persistit.exception.PersistitException;
+import com.persistit.unit.UnitTestProperties;
+import com.persistit.util.ThreadSequencer;
+import com.persistit.util.ThreadSequencer.Condition;
+
+/**
+ * MixtureTxn1 suite failed with this Exception:
+ * 
+ * Stress6 [Thread-195] FAILED [Thread-195]: java.lang.IllegalStateException:
+ * De-allocating page that is already garbage: root=36689 left=72838 right=36689
+ * 
+ * at com.persistit.VolumeStructure.deallocateGarbageChain(VolumeStructure.java:
+ * 510)
+ * 
+ * As it turns out, the condition being asserted is a rare but legitimate state
+ * and the bug fix it to remove a conditional clause from the assert statement
+ * in VolumeStructure#deallocateGarbageChain. The recreate1022567 method below
+ * reproduces the legitimate case, and without the change in VolumeStructure
+ * cuases a the IllegalStateException.
+ */
+
+public class Bug1022567Test extends PersistitUnitTestCase {
+
+    private final static String TREE_NAME = "Bug1022567";
+
+    private Exchange getExchange() throws PersistitException {
+        return _persistit.getExchange(VOLUME_NAME, TREE_NAME, true);
+    }
+
+    @Override
+    public Properties getProperties(final boolean cleanup) {
+        return UnitTestProperties.getBiggerProperties(cleanup);
+    }
+
+    /**
+     * This method carefully constructs a scenario in which the right sibling of
+     * a chain being deallocated is the garbage root page. The reported bug is
+     * that this condition causes an assert, when in fact the condition is rare
+     * but legitimate. Prior to fixing the bug this method throws an
+     * IllegalStateException.
+     * 
+     * @throws Exception
+     */
+    @Test
+    public void recreate1022567() throws Exception {
+        try {
+            enableSequencer(true);
+            addSchedules(DEALLOCATE_CHAIN_SCHEDULED);
+
+            final long mainThreadId = Thread.currentThread().getId();
+            setCondition(DEALLOCATE_CHAIN_A, new Condition() {
+                @Override
+                public boolean enabled() {
+                    return Thread.currentThread().getId() == mainThreadId;
+                }
+            });
+            for (int loop = 0; loop < 1000; loop++) {
+                _persistit.getVolume(VOLUME_NAME).truncate();
+                final Exchange ex1 = getExchange();
+                final List<Integer> keys = new ArrayList<Integer>();
+                /*
+                 * Lay down 4 pages
+                 */
+                long nextAvailable = 0;
+                ex1.getValue().put(createString(2000));
+                for (int i = 0;; i++) {
+                    ex1.clear().append(i).store();
+                    final long newNextAvailable = nextAvailablePage();
+                    if (newNextAvailable != nextAvailable) {
+                        keys.add(i - 1);
+                        nextAvailable = newNextAvailable;
+                        if (keys.size() > 3) {
+                            break;
+                        }
+                    }
+                }
+                final Key key1 = new Key(_persistit);
+                final Key key2 = new Key(_persistit);
+                key1.to(keys.get(1));
+                key2.to(keys.get(3));
+
+                // Need to create a race: this thread needs to remove the inside
+                // two
+                // pages and then let the other thread proceed before
+                // deallocating
+                // them.
+
+                final Thread t = new Thread(new Runnable() {
+                    @Override
+                    public void run() {
+                        try {
+                            sequence(DEALLOCATE_CHAIN_B);
+                            final Exchange ex2 = getExchange();
+                            ex2.to(Key.AFTER);
+                            while (ex2.previous()) {
+                                ex2.remove();
+                            }
+                            sequence(DEALLOCATE_CHAIN_C);
+                        } catch (final PersistitException e) {
+                            e.printStackTrace();
+                        }
+                    }
+                });
+                t.start();
+                key1.nudgeLeft();
+                key2.nudgeLeft();
+                ex1.removeKeyRange(key1, key2);
+                t.join();
+            }
+        } finally {
+            ThreadSequencer.disableSequencer();
+        }
+    }
+
+    @Test
+    public void deleteEnlargingRanges() throws Exception {
+        final Exchange ex = getExchange();
+        final VolumeStructure vs = ex.getVolume().getStructure();
+        final List<KeyState> keys = new ArrayList<KeyState>();
+        /*
+         * Lay down about 1000 pages
+         */
+        long nextAvailable = 0;
+        ex.getValue().put(RED_FOX);
+        for (int i = 0;; i++) {
+            ex.clear().append(i).store();
+            final long newNextAvailable = nextAvailablePage();
+            if (newNextAvailable != nextAvailable) {
+                keys.add(new KeyState(ex.getKey()));
+                nextAvailable = newNextAvailable;
+                if (nextAvailable > 1000) {
+                    break;
+                }
+            }
+        }
+        final List<Thread> threads = new ArrayList<Thread>();
+        for (int i = 2; i < 480; i++) {
+            final int offset = i;
+            final Thread t = new Thread(new Runnable() {
+                @Override
+                public void run() {
+                    try {
+                        final Key key1 = new Key(_persistit);
+                        final Key key2 = new Key(_persistit);
+                        keys.get(500 - offset).copyTo(key1);
+                        keys.get(500 + offset).copyTo(key2);
+                        final Exchange exchange = _persistit.getExchange(VOLUME_NAME, TREE_NAME, false);
+                        exchange.removeKeyRange(key1, key2);
+                    } catch (final PersistitException e) {
+                        e.printStackTrace();
+                    }
+                }
+            });
+            t.start();
+            threads.add(t);
+        }
+        for (final Thread t : threads) {
+            t.join();
+        }
+    }
+
+    @Test
+    public void deleteEnlargingRangesSingleThread() throws Exception {
+        final Exchange ex = getExchange();
+        final VolumeStructure vs = ex.getVolume().getStructure();
+        final List<KeyState> keys = new ArrayList<KeyState>();
+        /*
+         * Lay down about 1000 pages
+         */
+        long nextAvailable = 0;
+        ex.getValue().put(createString(2000));
+        for (int i = 0;; i++) {
+            ex.clear().append(i).store();
+            final long newNextAvailable = nextAvailablePage();
+            if (newNextAvailable != nextAvailable) {
+                keys.add(new KeyState(ex.getKey()));
+                nextAvailable = newNextAvailable;
+                if (nextAvailable > 1000) {
+                    break;
+                }
+            }
+        }
+        for (int i = 2; i < 80; i++) {
+            final int offset = i;
+            try {
+                final Key key1 = new Key(_persistit);
+                final Key key2 = new Key(_persistit);
+                keys.get(500 - offset).copyTo(key1);
+                keys.get(500 + offset).copyTo(key2);
+                final Exchange exchange = _persistit.getExchange(VOLUME_NAME, TREE_NAME, false);
+                exchange.removeKeyRange(key1, key2);
+            } catch (final PersistitException e) {
+                e.printStackTrace();
+            }
+        }
+    }
+
+    private long nextAvailablePage() throws PersistitException {
+        return _persistit.getVolume(VOLUME_NAME).getStorage().getNextAvailablePage();
+    }
+
+}

=== modified file 'src/test/java/com/persistit/Bug1041003Test.java'
--- src/test/java/com/persistit/Bug1041003Test.java	2012-09-26 21:30:03 +0000
+++ src/test/java/com/persistit/Bug1041003Test.java	2012-09-28 22:19:23 +0000
@@ -15,26 +15,17 @@
 
 package com.persistit;
 
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertTrue;
 import static org.junit.Assert.fail;
 
-import java.io.File;
 import java.io.IOException;
-import java.io.RandomAccessFile;
 import java.nio.ByteBuffer;
 import java.nio.channels.FileChannel;
 import java.util.Properties;
-import java.util.Timer;
-import java.util.TimerTask;
 
 import org.junit.Test;
 
 import com.persistit.JournalRecord.JE;
 import com.persistit.Transaction.CommitPolicy;
-import com.persistit.exception.CorruptJournalException;
-import com.persistit.exception.CorruptVolumeException;
-import com.persistit.exception.PersistitException;
 import com.persistit.exception.PersistitIOException;
 import com.persistit.unit.UnitTestProperties;
 
@@ -74,15 +65,15 @@
     @Test
     public void leaveTransactionBufferFlipped() throws Exception {
         /*
-         * Need first journal file almost full so that an attempt to write a transaction
-         * will force a rollover.
+         * Need first journal file almost full so that an attempt to write a
+         * transaction will force a rollover.
          */
         final Exchange exchange = _persistit.getExchange(_volumeName, "Bug1041003Test", true);
         _persistit.flush();
         final JournalManager jman = _persistit.getJournalManager();
-        ByteBuffer bb = ByteBuffer.allocate(BLOCKSIZE);
-        long size = BLOCKSIZE - JE.OVERHEAD - jman.getCurrentAddress() - 1;
-        bb.position((int)(size - JournalRecord.TX.OVERHEAD));
+        final ByteBuffer bb = ByteBuffer.allocate(BLOCKSIZE);
+        final long size = BLOCKSIZE - JE.OVERHEAD - jman.getCurrentAddress() - 1;
+        bb.position((int) (size - JournalRecord.TX.OVERHEAD));
         jman.writeTransactionToJournal(bb, 1, 2, 0);
         final Transaction txn = _persistit.getTransaction();
         final ErrorInjectingFileChannel eifc = errorInjectingChannel(_persistit.getJournalManager().getFileChannel(
@@ -115,11 +106,12 @@
         try {
             exchange.getValue().put(RED_FOX + RED_FOX);
             /*
-             * Bug 1041003 causes the following line to throw an IllegalStateException.
+             * Bug 1041003 causes the following line to throw an
+             * IllegalStateException.
              */
             exchange.to(1).store();
             txn.commit(CommitPolicy.HARD);
-        } catch (IllegalStateException e) {
+        } catch (final IllegalStateException e) {
             fail("Bug 1041003 strikes: " + e);
         } finally {
             txn.end();

=== added file 'src/test/java/com/persistit/Bug1058254Test.java'
--- src/test/java/com/persistit/Bug1058254Test.java	1970-01-01 00:00:00 +0000
+++ src/test/java/com/persistit/Bug1058254Test.java	2012-09-28 22:19:23 +0000
@@ -0,0 +1,59 @@
+/**
+ * Copyright © 2012 Akiban Technologies, Inc.  All rights reserved.
+ * 
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ * 
+ * This program may also be available under different license terms.
+ * For more information, see www.akiban.com or contact [e-mail].
+ * 
+ * Contributors:
+ * Akiban Technologies, Inc.
+ */
+
+package com.persistit;
+
+import static com.persistit.unit.UnitTestProperties.VOLUME_NAME;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import org.junit.Test;
+
+import com.persistit.exception.PersistitException;
+
+/**
+ * A range delete that crosses at least two page boundaries can write an
+ * incorrect key when merging records; this causes it and subsequent keys within
+ * the page to be wrong and also leads to a discontinuity between the max key in
+ * the page and the first key of its right sibling.
+ */
+
+public class Bug1058254Test extends PersistitUnitTestCase {
+
+    private final static String TREE_NAME = "Bug1022567";
+
+    private Exchange getExchange() throws PersistitException {
+        return _persistit.getExchange(VOLUME_NAME, TREE_NAME, true);
+    }
+
+    @Test
+    public void joinDiscontinuity() throws Exception {
+        final Exchange ex = getExchange();
+        ex.getValue().put(createString(2000));
+        for (int i = 3444; i < 3600; i++) {
+            ex.to(i).store();
+        }
+        final Key key1 = new Key(_persistit);
+        final Key key2 = new Key(_persistit);
+        key1.to(3445);
+        key2.to(3557);
+        ex.removeKeyRange(key1, key2);
+        ex.to(Key.BEFORE);
+        assertTrue(ex.next());
+        assertEquals(3444, ex.getKey().decodeInt());
+        assertTrue(ex.next());
+        assertEquals(3557, ex.getKey().decodeInt());
+    }
+}