Author: saya Date: Fri Sep 9 12:29:08 2011 New Revision: 1167130 URL: http://svn.apache.org/viewvc?rev=1167130&view=rev Log: some fixes and more tests for the recent jdbm related changes. Added two tests to test read by multiple reader and a single writer thread. Also tested the case where reader/writer cannot find a replacable cache entry. Added toString methods and messages to assert statements. Based on the tests, fixed some lock related issues when no free cache entry was found. Modified: directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BPage.java directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BTree.java directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/ActionContext.java directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/ActionVersioning.java directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/ExplicitList.java directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/LRUCache.java directory/apacheds/trunk/jdbm/src/main/java/jdbm/recman/SnapshotRecordManager.java directory/apacheds/trunk/jdbm/src/test/java/jdbm/btree/TestSnapshotBTree.java Modified: directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BPage.java URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BPage.java?rev=1167130&r1=1167129&r2=1167130&view=diff ============================================================================== --- directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BPage.java (original) +++ directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BPage.java Fri Sep 9 12:29:08 2011 @@ -401,7 +401,7 @@ public class BPage implements Seri if ( replace ) { - pageNewCopy.values[index] = value; + pageNewCopy.values[index] = btree.copyValue( value ); btree.recordManager.update( recordId, pageNewCopy, this ); } @@ -956,10 +956,10 @@ public class BPage implements Seri /** * Set the entry at the given index. */ - private void setEntry( BPage page, int index, K key, V value ) + private void setEntry( BPage page, int index, K key, V value ) throws IOException { page.keys[index] = key; - page.values[index] = value; + page.values[index] = btree.copyValue( value ); } Modified: directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BTree.java URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BTree.java?rev=1167130&r1=1167129&r2=1167130&view=diff ============================================================================== --- directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BTree.java (original) +++ directory/apacheds/trunk/jdbm/src/main/java/jdbm/btree/BTree.java Fri Sep 9 12:29:08 2011 @@ -949,6 +949,10 @@ public class BTree implements Exte byte[] array; V valueCopy = null; + + if ( value == null ) + return null; + if ( this.valueSerializer != null ) { array = this.valueSerializer.serialize( value ); @@ -969,7 +973,7 @@ public class BTree implements Exte out.flush(); byte[] arr = bout.toByteArray(); bin = new ByteArrayInputStream( arr ); - in =new ObjectInputStream( bin ); + in = new ObjectInputStream( bin ); valueCopy = ( V )in.readObject(); } catch ( ClassNotFoundException e ) Modified: directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/ActionContext.java URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/ActionContext.java?rev=1167130&r1=1167129&r2=1167130&view=diff ============================================================================== --- directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/ActionContext.java (original) +++ directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/ActionContext.java Fri Sep 9 12:29:08 2011 @@ -45,7 +45,7 @@ public class ActionContext public void endAction() { - assert( version != null ); + assert( version != null ) : "Unexpected action state during endAction: " + this; version = null; } @@ -78,4 +78,17 @@ public class ActionContext { return whoStarted; } + + @Override + public String toString() + { + StringBuilder sb = new StringBuilder(); + sb.append( "ActionContext: " ); + sb.append( "(readOnly: " ).append( readOnly ); + sb.append( ", version: " ).append( version ); + sb.append( ", whoStarted: " ).append( whoStarted ); + sb.append( ")\n" ); + + return sb.toString(); + } } Modified: directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/ActionVersioning.java URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/ActionVersioning.java?rev=1167130&r1=1167129&r2=1167130&view=diff ============================================================================== --- directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/ActionVersioning.java (original) +++ directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/ActionVersioning.java Fri Sep 9 12:29:08 2011 @@ -153,7 +153,7 @@ public class ActionVersioning { long numActions = version.getNumActions().decrementAndGet(); - assert( numActions >= 0 ); + assert( numActions >= 0 ) : "NumActions zero when read action is ended : " + version; if ( ( numActions > 0 ) || ( version == readReference.get() ) ) { @@ -216,5 +216,17 @@ public class ActionVersioning { return version; } + + @Override + public String toString() + { + StringBuilder sb = new StringBuilder(); + sb.append( "Version: "); + sb.append( "(vesion: " ).append( version ); + sb.append( ", numActions: " ).append( numActions ); + sb.append( ")\n" ); + + return sb.toString(); + } } } \ No newline at end of file Modified: directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/ExplicitList.java URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/ExplicitList.java?rev=1167130&r1=1167129&r2=1167130&view=diff ============================================================================== --- directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/ExplicitList.java (original) +++ directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/ExplicitList.java Fri Sep 9 12:29:08 2011 @@ -31,8 +31,10 @@ package jdbm.helper; public class ExplicitList { - Link head = new Link( null ); + private Link head = new Link( null ); + private int listSize = 0; + public static class Link { private V element; @@ -73,7 +75,7 @@ public class ExplicitList public void remove() { - assert ( isLinked() ); + assert( isLinked() ) : "Trying to remove from list an unlinked link"; this.getPrev().setNext( this.getNext() ); this.getNext().setPrev( this.getPrev() ); this.reset(); @@ -82,6 +84,7 @@ public class ExplicitList public void addAfter( Link after ) { + assert( this.isUnLinked() ) : "Trying to add to list already linked link: " + this; after.getNext().setPrev( this ); this.setNext( after.getNext() ); after.setNext( this ); @@ -91,6 +94,7 @@ public class ExplicitList public void addBefore( Link before ) { + assert( this.isUnLinked() ) : "Trying to add to list already linked link: " + this; before.getPrev().setNext( this ); this.setPrev( before.getPrev() ); before.setPrev( this ); @@ -98,6 +102,11 @@ public class ExplicitList } + /** + * Splices the given list by making this link as the new head. + * + * @param listHead head of the existing list + */ public void splice( Link listHead ) { Link prevLink = listHead.getPrev(); @@ -110,7 +119,7 @@ public class ExplicitList public boolean isUnLinked() { - return ( prev == this && next == this ); + return ( ( prev == this ) && ( next == this ) ); } @@ -129,7 +138,7 @@ public class ExplicitList public void uninit() { - assert ( this.isUnLinked() ); + assert ( this.isUnLinked() ) : " Unitializing a still linked entry" + this; element = null; } @@ -138,23 +147,39 @@ public class ExplicitList { return this.element; } + + @Override + public String toString() + { + StringBuilder sb = new StringBuilder(); + sb.append( "Link: " ).append( this ).append( " " ); + sb.append( "(next: " ).append( next ); + sb.append( ",prev: " ).append( prev ).append(")"); + sb.append( "\n" ); + + return sb.toString(); + } } public void remove( Link link ) { + assert( listSize > 0 ) : "Trying to remove link " + link + " from a list with no elements"; + listSize--; link.remove(); } public void addFirst( Link link ) { + listSize++; link.addAfter( head ); } public void addLast( Link link ) { + listSize++; link.addBefore( head ); } @@ -169,5 +194,21 @@ public class ExplicitList { return head; } + + public int size() + { + return listSize; + } + + @Override + public String toString() + { + StringBuilder sb = new StringBuilder(); + sb.append( "List: " ); + sb.append( "(size: " ).append( listSize ).append( ")" ); + sb.append( "\n" ); + + return sb.toString(); + } } \ No newline at end of file Modified: directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/LRUCache.java URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/LRUCache.java?rev=1167130&r1=1167129&r2=1167130&view=diff ============================================================================== --- directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/LRUCache.java (original) +++ directory/apacheds/trunk/jdbm/src/main/java/jdbm/helper/LRUCache.java Fri Sep 9 12:29:08 2011 @@ -1,4 +1,4 @@ -/* + /* * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information @@ -65,7 +65,7 @@ public class LRUCache private final int numBuckets; /** Log of number of hash buckets each latch protects */ - private final static int LOG_BUCKET_PER_LATCH = 3; + private final static int LOG_BUCKET_PER_LATCH = 0; /** Number of lrus */ private final static int NUM_LRUS = 16; @@ -74,7 +74,7 @@ public class LRUCache private final static int MIN_ENTRIES = 1 << 10; /** Max sleep time(in ms) for writes in case of cache eviction failure */ - private final static long MAX_WRITE_SLEEP_TIME = 10000; + private final static long MAX_WRITE_SLEEP_TIME = 600000; /** lru list */ LRU lrus[]; @@ -94,8 +94,18 @@ public class LRUCache /** minimum version cache has to satisfy during reads */ private long minReadVersion; - - + /** Stats to keep track of cache gets */ + private long cacheGets; + + /** Stats to keep track of cache hits for cache gets */ + private long cacheMisses; + + /** Stats to keep track of cache puts */ + private long cachePuts; + + /** Stats to keep track of # of times writes sleep for free cache entry */ + private long cachePutSleeps; + @SuppressWarnings("unchecked") public LRUCache( EntryIO entryIO, int cacheSize ) { @@ -196,6 +206,8 @@ public class LRUCache * While reading or waiting, latch is released. */ + this.cachePuts++; + while ( true ) { latches[latchIndex].lock(); @@ -226,7 +238,18 @@ public class LRUCache if ( !entry.isCurrentVersion() ) { - CacheEntry newEntry = this.findNewEntry( key, latchIndex ); + assert( entry.isNeverReplace() == false ) : " Non current entry should not have neverReplace set " + entry; + + entry.setNeverReplace(); + CacheEntry newEntry = null; + try + { + newEntry = this.findNewEntry( key, hashIndex >> LOG_BUCKET_PER_LATCH ); + } + finally + { + entry.clearNeverReplace(); + } /* * Remove existing entry, chain as a snapshot @@ -269,7 +292,7 @@ public class LRUCache // FALLTHROUGH default: - assert ( false ); + assert ( false ): "Unknown cache entry state: " + entry ; } } else @@ -287,6 +310,7 @@ public class LRUCache if ( sleepForFreeEntry == false ) { + System.out.println(" NO cache entry for write " + totalSleepTime ); throw e; } } @@ -314,6 +338,9 @@ public class LRUCache break; } } + + if ( totalSleepTime != 0 ) + this.cachePutSleeps++; } @@ -346,6 +373,9 @@ public class LRUCache * * While reading or waiting, latch is released. */ + + this.cacheGets++; + latches[latchIndex].lock(); boolean chainExists = false; @@ -376,8 +406,21 @@ public class LRUCache if (value != null) break; - - CacheEntry newEntry = this.findNewEntry( key, latchIndex ); + + this.cacheMisses++; + + assert( entry.isNeverReplace() == false ) : "Non Current Entry has neverReplace set to true:" + entry; + + entry.setNeverReplace(); + CacheEntry newEntry = null; + try + { + newEntry = this.findNewEntry( key, hashIndex >> LOG_BUCKET_PER_LATCH ); + } + finally + { + entry.clearNeverReplace(); + } /* * Remove existing entry, chain as a snapshot @@ -411,16 +454,18 @@ public class LRUCache case ENTRY_INITIAL: LOG.warn( "Entry with key {} is at intial while trying to read from it", entry.getKey() ); + this.cacheMisses++; this.doRead( entry, latches[latchIndex], serializer ); value = this.searchChainForVersion( entry, version ); break; default: - assert ( false ); + assert ( false ) : "Unknown cache entry state: " + entry; } } else { + this.cacheMisses++; entry = this.findNewEntry( key, latchIndex ); buckets[hashIndex].add( entry ); this.doRead( entry, latches[latchIndex], serializer ); @@ -444,6 +489,21 @@ public class LRUCache return value; } + @Override + public String toString() + { + StringBuilder sb = new StringBuilder(); + sb.append( "LRUCache: " ); + sb.append( "(numEntries:" ).append( this.numEntries ); + sb.append( ",maxEntries:" ).append( this.maxEntries ); + sb.append( ",cacheGets:" ).append( this.cacheGets ); + sb.append( ",cacheMisses:" ).append( this.cacheMisses ); + sb.append( ",cachePuts:" ).append( this.cachePuts ); + sb.append( ",cachePutSleeps:" ).append( this.cachePutSleeps ); + sb.append( ")\n" ); + + return sb.toString(); + } /** * Creates a new version of the given entry with the given new version. @@ -461,12 +521,29 @@ public class LRUCache private void putNewVersion( CacheEntry entry, K key, V value, long newVersion, int hashIndex, Lock latch, Serializer serializer, boolean neverReplace ) throws IOException, CacheEvictionException { + if ( entry.getStartVersion() != newVersion ) { - CacheEntry newEntry = this.findNewEntry( key, hashIndex >> LOG_BUCKET_PER_LATCH ); - - // Initialize and set to new version - newEntry.initialize( key ); + + boolean resetNeverReplace = true; + if ( entry.isNeverReplace() ) + resetNeverReplace = false; + + entry.setNeverReplace(); + CacheEntry newEntry = null; + try + { + newEntry = this.findNewEntry( key, hashIndex >> LOG_BUCKET_PER_LATCH ); + } + finally + { + if ( resetNeverReplace ) + entry.clearNeverReplace(); + } + + + + // Set to new version newEntry.setAsCurrentVersion( value, newVersion ); /* @@ -482,7 +559,7 @@ public class LRUCache } else { - assert( entry.isCurrentVersion() ); + assert( entry.isCurrentVersion() ) : "Entry not at expected version: " + entry ; // Entry already at current version. Just update the value entry.setAsCurrentVersion( value, newVersion ); @@ -506,7 +583,11 @@ public class LRUCache * Not much we can do here, just leave the entry in an * inconsistent state. */ + latch.lock(); + + entry.setState( EntryState.ENTRY_INITIAL ); + entry.clearNeverReplace(); if ( entry.anyWaiters() ) { @@ -559,14 +640,15 @@ public class LRUCache if ( curEntry.getState() != EntryState.ENTRY_READY ) { - assert( curEntry == head ); + assert( curEntry == head ) : "Unexpected state for entry: " + curEntry; curLink = curLink.getNext(); continue; } if ( curStartVersion != 0 && ( curEntry.getEndVersion() > curStartVersion ) ) { - assert( false ); + assert( false ) : "Unexpected version number for entry. curStartVersion: " + + curStartVersion + " entry: " + curEntry; } curStartVersion = curEntry.getStartVersion(); @@ -594,7 +676,7 @@ public class LRUCache if ( value == null && mustFind == true ) { - assert( false ); + assert( false ) : "Traversed all versions and could not find cache entry"; } return value; @@ -711,18 +793,17 @@ public class LRUCache numEntries.incrementAndGet(); CacheEntry newEntry = new CacheEntry( index ); lru = lrus[index]; + newEntry.initialize( key ); lru.getLock().lock(); lru.addToLRU( newEntry ); lru.getLock().unlock(); - newEntry.initialize( key ); return newEntry; } /* * We start with a lru determined by the lru randomizer and try to lock the lru without waiting. - * If this doesnt work, we wait on the first lru lock. Once we get the lru, we walk over each lru - * (this time waiting on the lock when we switch to a new lru) and try to find a victim. + * If this doesnt work, we wait on the first lru lock. */ CacheEntry victimEntry = null; lru = null; @@ -747,37 +828,23 @@ public class LRUCache lru.getLock().lock(); } - int startingIndex = curIndex; + victimEntry = lru.findVictim( latchIndex ); - do - { - victimEntry = lru.findVictim( latchIndex ); - lru.getLock().unlock(); - - if ( victimEntry != null ) - { - break; - } - - curIndex = (curIndex + 1) % NUM_LRUS; - if ( curIndex == startingIndex ) - break; - - lru = lrus[curIndex]; - lru.getLock().lock(); - } - while ( true ); if ( victimEntry != null ) { victimEntry.initialize( key ); + lru.getLock().unlock(); } else { + lru.getLock().unlock(); + LOG.warn( "Cache eviction failure: " + this.minReadVersion ); throw new CacheEvictionException( null ); } + return victimEntry; } @@ -856,17 +923,18 @@ public class LRUCache { this.key = key; value = null; - startVersion = endVersion = 0; + startVersion = 0; + endVersion = Long.MAX_VALUE; stateCondition = null; - assert ( numWaiters == 0 ); + assert ( numWaiters == 0 ) : "Numwaiters is not zero when entry is newly initialized: " + this; state = EntryState.ENTRY_INITIAL; assert ( versionsLink.isUnLinked() == true ); hashIndex = hash( key ) & ( numBuckets - 1 ); - assert( neverReplace == false ); + assert( neverReplace == false ) : "Neverreplace is true when entry is newly intialized:" + this; } public void setNeverReplace() @@ -874,6 +942,16 @@ public class LRUCache neverReplace = true; } + public void clearNeverReplace() + { + neverReplace = false; + } + + public boolean isNeverReplace() + { + return neverReplace; + } + public K getKey() { @@ -918,7 +996,7 @@ public class LRUCache public void decrementWaiters() { - assert ( numWaiters > 0 ); + assert ( numWaiters > 0 ) : "Unexpected num waiters for entry:" + this; numWaiters--; } @@ -1000,10 +1078,10 @@ public class LRUCache public void setAsSnapshotVersion( long newEndVersion ) { - this.endVersion = newEndVersion; - neverReplace = false; + this.clearNeverReplace(); LRU lru = this.getLru(); lru.getLock().lock(); + this.endVersion = newEndVersion; lru.addToSnapshots( this ); lru.getLock().unlock(); } @@ -1014,6 +1092,23 @@ public class LRUCache return ( this.state != EntryState.ENTRY_READING && this.numWaiters == 0 && this.state != EntryState.ENTRY_WRITING && !neverReplace); } + + @Override + public String toString() + { + StringBuilder sb = new StringBuilder(); + sb.append( "Entry: " ); + sb.append("(state: ").append( this.state ); + sb.append(",numWaiters:").append( this.numWaiters ); + sb.append(",startVersion:").append( this.startVersion ); + sb.append(",endVersion:").append( this.endVersion ); + sb.append(",key:").append( this.key ); + sb.append(",value:").append( this.value ).append( ")" ); + sb.append( "\n" ); + + return sb.toString(); + + } } @@ -1023,11 +1118,17 @@ public class LRUCache private ExplicitList mostRecentVersions = new ExplicitList(); /** List of snapshot entries */ - private LinkedList snapshotVersions = new LinkedList(); + private ExplicitList snapshotVersions = new ExplicitList(); /** Lock protecting the list */ private Lock lock = new ReentrantLock(); + /** Number of snaphot versions created */ + private int numSnapshotsCreated; + + /** True if lru needs to be purged of unusable snapshot versions */ + private boolean snapshotPurgeNeeded; + public Lock getLock() { return lock; @@ -1054,7 +1155,9 @@ public class LRUCache public void addToSnapshots( CacheEntry entry ) { mostRecentVersions.remove( entry.getLruLink() ); - snapshotVersions.addLast( entry ); + snapshotVersions.addLast( entry.getLruLink() ); + + numSnapshotsCreated++; } @@ -1102,28 +1205,40 @@ public class LRUCache * gotten from the tail of the lru. */ - Iterator it = snapshotVersions.listIterator(); + ExplicitList.Link curLink; + + curLink = snapshotVersions.begin(); - while ( it.hasNext() ) + while ( curLink != snapshotVersions.end() ) { - victimEntry = it.next(); + victimEntry = curLink.getElement(); if ( victimEntry.getEndVersion() > minReadVersion ) { break; } + + assert( victimEntry.getKey() != null ) : + "Snapshot victimEntry doesnt have key set:" + victimEntry ; - assert ( victimEntry.isEntryFreeable() == true ); - + if ( victimEntry.isNeverReplace() ) + { + curLink = curLink.getNext(); + continue; + } victimBucketIndex = victimEntry.getHashIndex(); victimLatchIndex = (victimBucketIndex >> LOG_BUCKET_PER_LATCH ); if ( ( latchIndex != victimLatchIndex ) && ( latches[victimLatchIndex].tryLock() == false ) ) { + curLink = curLink.getNext(); continue; } + assert( victimEntry.isEntryFreeable() == true ) : + "Snapshot victimEntry is not freeable:" + victimEntry ; + int hashChainIndex = buckets[victimEntry.getHashIndex()].indexOf( victimEntry ); if ( hashChainIndex != -1 ) @@ -1149,13 +1264,13 @@ public class LRUCache latches[victimLatchIndex].unlock(); } - it.remove(); - this.mostRecentVersions.addLast( victimEntry.lruLink ); + this.snapshotVersions.remove( victimEntry.getLruLink() ); + this.mostRecentVersions.addLast( victimEntry.getLruLink() ); return victimEntry; } - ExplicitList.Link curLink = mostRecentVersions.begin(); + curLink = mostRecentVersions.begin(); while ( curLink != mostRecentVersions.end() ) { Modified: directory/apacheds/trunk/jdbm/src/main/java/jdbm/recman/SnapshotRecordManager.java URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm/src/main/java/jdbm/recman/SnapshotRecordManager.java?rev=1167130&r1=1167129&r2=1167130&view=diff ============================================================================== --- directory/apacheds/trunk/jdbm/src/main/java/jdbm/recman/SnapshotRecordManager.java (original) +++ directory/apacheds/trunk/jdbm/src/main/java/jdbm/recman/SnapshotRecordManager.java Fri Sep 9 12:29:08 2011 @@ -625,6 +625,17 @@ public class SnapshotRecordManager imple bigLock.unlock(); } } + + @Override + public String toString() + { + StringBuilder sb = new StringBuilder(); + sb.append( "SnapshotRecordManager: " ); + sb.append( "(lruCache:" ).append( this.versionedCache ); + sb.append( ")\n" ); + + return sb.toString(); + } /** Modified: directory/apacheds/trunk/jdbm/src/test/java/jdbm/btree/TestSnapshotBTree.java URL: http://svn.apache.org/viewvc/directory/apacheds/trunk/jdbm/src/test/java/jdbm/btree/TestSnapshotBTree.java?rev=1167130&r1=1167129&r2=1167130&view=diff ============================================================================== --- directory/apacheds/trunk/jdbm/src/test/java/jdbm/btree/TestSnapshotBTree.java (original) +++ directory/apacheds/trunk/jdbm/src/test/java/jdbm/btree/TestSnapshotBTree.java Fri Sep 9 12:29:08 2011 @@ -24,6 +24,7 @@ import static org.junit.Assert.assertTru import java.io.IOException; import java.io.Serializable; +import java.util.Random; import java.util.concurrent.Semaphore; import jdbm.RecordManager; @@ -47,8 +48,8 @@ import com.mycila.junit.concurrent.Concu * * @author Apache Directory Project */ -@RunWith(ConcurrentJunitRunner.class) -@Concurrency() +//@RunWith(ConcurrentJunitRunner.class) +//@Concurrency() public class TestSnapshotBTree { @Rule @@ -77,8 +78,8 @@ public class TestSnapshotBTree int idx; int numReadThreads = 1; - TestThread readThreads[] = new TestThread[numReadThreads]; - TestThread updateThread; + BasicTestThread readThreads[] = new BasicTestThread[numReadThreads]; + BasicTestThread updateThread; Semaphore browseSem = new Semaphore( 0 ); Semaphore updateSem = new Semaphore( 0 ); @@ -95,9 +96,9 @@ public class TestSnapshotBTree for ( idx = 0; idx < numReadThreads; idx++ ) { - readThreads[idx] = new TestThread( true, tree, browseSem, updateSem, numReadThreads ); + readThreads[idx] = new BasicTestThread( true, tree, browseSem, updateSem, numReadThreads ); } - updateThread = new TestThread( false, tree, browseSem, updateSem, numReadThreads ); + updateThread = new BasicTestThread( false, tree, browseSem, updateSem, numReadThreads ); updateThread.start(); for ( idx = 0; idx < numReadThreads; idx++ ) @@ -115,8 +116,10 @@ public class TestSnapshotBTree snapshotRecman.close(); } + - class TestThread extends Thread + + class BasicTestThread extends Thread { boolean readOnly; BTree btree; @@ -124,8 +127,8 @@ public class TestSnapshotBTree Semaphore updateSem; int numReadThreads; - TestThread( boolean readOnly, BTree btree, Semaphore firstBrowse, - Semaphore updateDone, int numReadThreads) + BasicTestThread( boolean readOnly, BTree btree, Semaphore firstBrowse, + Semaphore updateDone, int numReadThreads ) { this.readOnly = readOnly; this.btree = btree; @@ -242,12 +245,345 @@ public class TestSnapshotBTree } catch( IOException e ) { + e.printStackTrace(); + assertTrue( false ); } catch( InterruptedException e ) { + e.printStackTrace(); + assertTrue( false ); + } + + } + } // end of class BasicTestThread + + + @Test + public void testLongBrowsing() throws IOException, InterruptedException + { + RecordManager recman; + BTree tree; + int numElements = 10000; + + int idx; + int numReadThreads = 4; + LongBrowsingTestThread readThreads[] = new LongBrowsingTestThread[numReadThreads]; + LongBrowsingTestThread updateThread; + + recman = RecordManagerFactory.createRecordManager( getTemporaryFile( "testLongBrowsing" ) ); + SnapshotRecordManager snapshotRecman = new SnapshotRecordManager( recman, 1 << 10 ); + + tree = new BTree( snapshotRecman, new IntegerComparator() ); + + for ( idx = 0; idx < numElements; idx++ ) + { + tree.insert( new Integer( idx ), new IntWrapper( 0 ), true ); + } + + for ( idx = 0; idx < numReadThreads; idx++ ) + { + readThreads[idx] = new LongBrowsingTestThread( true, tree, numElements); + } + updateThread = new LongBrowsingTestThread( false, tree, numElements ); + + + readThreads[0].start(); + + Thread.sleep( 10 ); + + updateThread.start(); + for ( idx = 1; idx < numReadThreads; idx++ ) + { + Thread.sleep( 1000 ); + readThreads[idx].start(); + } + + + for ( idx = 0; idx < numReadThreads; idx++ ) + { + readThreads[idx].join(); + } + updateThread.join(); + + snapshotRecman.close(); + } + + class LongBrowsingTestThread extends Thread + { + boolean readOnly; + BTree btree; + int numElements; + + + LongBrowsingTestThread( boolean readOnly, BTree btree, int numElements) + { + this.readOnly = readOnly; + this.btree = btree; + this.numElements = numElements; + } + + + + private void readOnlyActions() throws IOException, InterruptedException + { + int count = 0; + TupleBrowser browser = btree.browse(); + Tuple tuple = new Tuple(); + + assert( browser.getNext( tuple ) ); + int max = tuple.getValue().value; + count++; + System.out.println( " TestLongBrowsing read thread min key is" + tuple.getKey() + "max value is" + max ); + + while( browser.getNext( tuple ) ) + { + count++; + + // Sleep for a while to keep browsing long + Thread.sleep( 10 ); + + + if ( tuple.getValue().value > max ) + { + System.out.println(" tupe value:" + tuple.getValue().value + " Expected max:" + max + " count:" + count); + + } + + assertTrue( tuple.getValue().value <= max ); } + + + System.out.println( "TestLongBrowsing read thread count is " + count ); + assertEquals( count, numElements ); + browser.close(); + } + + private void readWriteActions() + { + int idx; + Random updateRandomizer = new Random(); + try + { + for ( idx = 1; idx < 100; idx++ ) + { + Integer key = new Integer( 0 ); + IntWrapper value = btree.find( key ); + value.value = idx; + btree.insert( key, value, true ); + + for ( int updates = 0; updates < 2048; updates++ ) + { + key = new Integer( updateRandomizer.nextInt( numElements ) ); + value = btree.find( key ); + + assertTrue( value.value <= idx ); + + value.value = idx; + btree.insert( key, value, true ); + } + } + + System.out.println( "TestLongBrowsing updates ended" ); + + } + catch( IOException e ) + { + e.printStackTrace(); + assertTrue( false ); + } } - } // end of class TestThread + + + public void run() + { + try + { + if ( readOnly ) + this.readOnlyActions(); + else + this.readWriteActions(); + } + catch( IOException e ) + { + e.printStackTrace(); + assertTrue( false ); + } + catch( InterruptedException e ) + { + e.printStackTrace(); + assertTrue( false ); + } + + } + } // end of class LongBrowsingTestThread + + + + @Test + public void testRemoveInsert() throws IOException, InterruptedException + { + RecordManager recman; + BTree tree; + int numElements = 10000; + + int idx; + int numReadThreads = 4; + RemoveInsertTestThread readThreads[] = new RemoveInsertTestThread[numReadThreads]; + RemoveInsertTestThread updateThread; + + Semaphore browseSem = new Semaphore( 0 ); + + recman = RecordManagerFactory.createRecordManager( getTemporaryFile( "testRemoveInsert" ) ); + SnapshotRecordManager snapshotRecman = new SnapshotRecordManager( recman, 1 << 12 ); + + tree = new BTree( snapshotRecman, new IntegerComparator() ); + + for ( idx = 0; idx < numElements; idx++ ) + { + tree.insert( new Integer( idx ), new IntWrapper( 0 ), true ); + } + + for ( idx = 0; idx < numReadThreads; idx++ ) + { + readThreads[idx] = new RemoveInsertTestThread( true, tree, numElements, browseSem, numReadThreads ); + } + updateThread = new RemoveInsertTestThread( false, tree, numElements, browseSem, numReadThreads ); + + + updateThread.start(); + for ( idx = 0; idx < numReadThreads; idx++ ) + { + Thread.sleep( 1000 ); + readThreads[idx].start(); + } + + + for ( idx = 0; idx < numReadThreads; idx++ ) + { + readThreads[idx].join(); + } + updateThread.join(); + + snapshotRecman.close(); + } + + + + class RemoveInsertTestThread extends Thread + { + boolean readOnly; + BTree btree; + int numElements; + Semaphore browseSem; + int numReadThreads; + + RemoveInsertTestThread( boolean readOnly, BTree btree, int numElements, Semaphore browseSem, int numReadThreads ) + { + this.readOnly = readOnly; + this.btree = btree; + this.numElements = numElements; + this.browseSem = browseSem; + this.numReadThreads = numReadThreads; + } + + private void readOnlyActions() throws IOException, InterruptedException + { + int count = 0; + TupleBrowser browser = btree.browse(); + Tuple tuple = new Tuple(); + + browseSem.release(); + + while( browser.getNext( tuple ) ) + { + count++; + + // Sleep for a while to keep browsing long + Thread.sleep( 10 ); + + + if ( tuple.getValue().value == -1 ) + { + System.out.println(" tupe key:" + tuple.getKey() + " value:" + tuple.getValue().value); + + } + + assertTrue( tuple.getValue().value != -1 ); + } + + + System.out.println( "TestRemoveInsert read thread count is " + count ); + assertEquals( count, numElements ); + browser.close(); + } + + private void readWriteActions() throws IOException, InterruptedException + { + int idx; + Random updateRandomizer = new Random(); + + for ( idx = 0; idx < numReadThreads; idx++ ) + browseSem.acquireUninterruptibly(); + + + Integer key; + IntWrapper value = new IntWrapper( -1 ); + + for ( idx = 0; idx < 10; idx++ ) + { + Thread.sleep( 10000 ); + + int startingIndex = updateRandomizer.nextInt( numElements ); + + for ( int updates = 0; updates < 32; updates++ ) + { + key = new Integer( startingIndex + updates ); + + if ( key.intValue() >= numElements ) + break; + + + btree.remove( key ); + } + + for ( int updates = 0; updates < 32; updates++ ) + { + key = new Integer( startingIndex + updates ); + btree.insert( key, value, true ); + } + } + + System.out.println( "TestRemoveInsert updates ended" ); + + } + + + public void run() + { + try + { + if ( readOnly ) + this.readOnlyActions(); + else + this.readWriteActions(); + } + catch( IOException e ) + { + e.printStackTrace(); + assertTrue( false ); + } + catch( InterruptedException e ) + { + e.printStackTrace(); + assertTrue( false ); + } + + + } + } // end of class RemoveInsertTestThread + + + } \ No newline at end of file