KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sleepycat > je > tree > SplitRace_SR11144Test


1 /*-
2  * See the file LICENSE for redistribution information.
3  *
4  * Copyright (c) 2005,2006 Oracle. All rights reserved.
5  *
6  * $Id: SplitRace_SR11144Test.java,v 1.9 2006/10/30 21:14:52 bostic Exp $
7  */
8
9 package com.sleepycat.je.tree;
10
11 import java.io.File JavaDoc;
12 import java.io.IOException JavaDoc;
13
14 import junit.framework.TestCase;
15
16 import com.sleepycat.bind.tuple.IntegerBinding;
17 import com.sleepycat.je.Cursor;
18 import com.sleepycat.je.Database;
19 import com.sleepycat.je.DatabaseConfig;
20 import com.sleepycat.je.DatabaseEntry;
21 import com.sleepycat.je.DatabaseException;
22 import com.sleepycat.je.DbInternal;
23 import com.sleepycat.je.Environment;
24 import com.sleepycat.je.EnvironmentConfig;
25 import com.sleepycat.je.LockMode;
26 import com.sleepycat.je.OperationStatus;
27 import com.sleepycat.je.util.TestUtils;
28 import com.sleepycat.je.utilint.TestHook;
29
30 /*********************************************************************
31   Exercise a race condition in split processing. The case requires a
32   at least 3 level btree where the root has maxEntries-1 children.
33   i.e suppose node max = 4. Our test case will start with data like this:
34
35                         RootIN
36                  +--------+----------+
37                  / | \
38               INa INb INc
39                       / | \ / | \
40                      BIN BIN BINx BIN BIN BINy
41                              /||\ /||\
42
43   Note that it takes some finagling to make the data look this way. An insert
44   of sequentially ascending values won't look like this, because opportunistic
45   splitting prevents all but the righitmost BIN from being completely full.
46
47   At this point, suppose that thread1 wants to insert into BINx and thread2
48   wants to insert into BINy. Our split code looks like this:
49
50   Body of Tree.searchSplitsAllowed()
51
52      rootLatch.acquire()
53      fetch rootIN
54      rootIN.latch
55      opportunitically split root (dropping and re-acquiring rootINlatches)
56       splitting the root requires updating the dbmapping tree
57      rootLatch.release()
58
59      // leave this block of code owning the rootIN latch.
60      call searchSubTreeSplitsAllowed()
61
62   Body of Tree.searchSubTreeSplitsAllowed()
63      while (true) {
64        try {
65           // throws if finds a node that needs splitting
66           return searchSubTreeUntilSplit()
67        } catch (SplitRequiredException e) {
68           // acquire latches down the depth of the tree
69           forceSplit();
70        }
71      }
72
73   If code is executed in this order:
74
75   thread 1 executes searchSplitsAllowed(), root doesn't need splitting
76   thread 1 executes searchSubTreeUntilSplit(), throws out because of BINx
77   thread 1 hold no latches before executing forceSplit()
78   thread 2 executes searchSplitsAllowed(), root doesn't need splitting
79   thread 2 executes searchSubTreeUntilSplit(), throws out because of BINy
80   thread 2 hold no latches before executing forceSplit()
81   thread 1 executes forceSplit, splits BINx, which ripples upward,
82                adding a new level 2 IN. The root is full
83   thread 2 executes forceSplit, splits BINy, which ripples upward,
84                adding a new level 2 IN. The root can't hold the new child!
85
86  The root split is done this way, outside forceSplit, because it's special
87  because you must hold the rootLatch.
88
89  This case does not exist for duplicates because:
90    a. in 1 case, the owning BIN (the equivalent of the root) stays latched
91    b. in a 2nd case, the caller is recovery, which is single threaded.
92
93  The solution was to check for root fullness in forceSplit(), before
94  latching down the whole depth of the tree. In that case, we throw out
95  and re-execute the rootLatch latching.
96
97 ********************************************************************/
98
99 public class SplitRace_SR11144Test extends TestCase {
100     private static final boolean DEBUG = false;
101     private File JavaDoc envHome;
102     private Environment env = null;
103     private Database db = null;
104
105     public SplitRace_SR11144Test() {
106         envHome = new File JavaDoc(System.getProperty(TestUtils.DEST_DIR));
107     }
108
109     public void setUp()
110         throws IOException JavaDoc {
111
112         TestUtils.removeLogFiles("Setup", envHome, false);
113     }
114     
115     public void tearDown()
116         throws Exception JavaDoc {
117
118         try {
119             /* Close in case we hit an exception and didn't close */
120             if (env != null) {
121         env.close();
122             }
123         } catch (DatabaseException e) {
124             /* Ok if already closed */
125         }
126         env = null; // for JUNIT, to reduce memory usage when run in a suite.
127 TestUtils.removeLogFiles("TearDown", envHome, false);
128     }
129
130     public void testSplitRootRace()
131         throws Throwable JavaDoc {
132
133         /* Create tree topology described in header comments. */
134         initData();
135
136         /*
137          * Create two threads, and hold them in a barrier at the
138          * designated point in Tree.java. They'll insert keys which
139          * will split BINx and BINy.
140          */
141
142         InsertThread a = new InsertThread(92, db);
143         InsertThread b = new InsertThread(202, db);
144         setWaiterHook();
145         b.start();
146         a.start();
147
148         a.join();
149         b.join();
150
151         close();
152     }
153
154     /**
155      * Create this:
156      * RootIN
157      * +--------+----------+
158      * / | \
159      * INa INb INc
160      * / | \ / | \
161      * BIN BIN BINx BIN BIN BINy
162      * /||\ /||\
163      *
164      */
165     private void initData() {
166     try {
167         initEnvInternal(true);
168             
169             /*
170              * Opportunistic splitting will cause the following inserts to
171              * add three child entries per parent.
172              */
173             int value = 0;
174             for (int i = 0; i < 23; i++) {
175                 put(db, value);
176                 value += 10;
177             }
178
179             /* Add a fourth child to BINx and BINy */
180             put(db, 91);
181             put(db, 201);
182
183             if (DEBUG) {
184                 dump();
185             }
186         } catch (DatabaseException DBE) {
187         throw new RuntimeException JavaDoc(DBE);
188     }
189     }
190     
191     private static void put(Database db, int value)
192         throws DatabaseException {
193
194         DatabaseEntry key = new DatabaseEntry();
195         DatabaseEntry data = new DatabaseEntry();
196         /* put the value in the key. */
197         IntegerBinding.intToEntry(11, data);
198         IntegerBinding.intToEntry(value, key);
199
200         OperationStatus status = db.putNoOverwrite(null, key, data);
201         if (status != OperationStatus.SUCCESS) {
202             throw new RuntimeException JavaDoc("status=" + status);
203         }
204     }
205
206     private void close() {
207         try {
208             db.close();
209             env.close();
210     } catch (DatabaseException DBE) {
211         throw new RuntimeException JavaDoc(DBE);
212     }
213     }
214     
215     private void dump() {
216         try {
217             Cursor cursor = db.openCursor(null, null);
218             DatabaseEntry key = new DatabaseEntry();
219             DatabaseEntry data = new DatabaseEntry();
220             while (cursor.getNext(key, data, LockMode.DEFAULT) ==
221                    OperationStatus.SUCCESS) {
222                 System.out.println("<rec key=\"" +
223                                    IntegerBinding.entryToInt(key) +
224                                    "\" data=\"" +
225                                    IntegerBinding.entryToInt(data) +
226                                    "\"/>");
227             }
228             DbInternal.dbGetDatabaseImpl(db).getTree().dump();
229             cursor.close();
230         } catch (DatabaseException DBE) {
231             throw new RuntimeException JavaDoc(DBE);
232         }
233     }
234
235     private void initEnvInternal(boolean create)
236     throws DatabaseException {
237
238         EnvironmentConfig envConfig = TestUtils.initEnvConfig();
239         envConfig.setTransactional(true);
240         envConfig.setAllowCreate(create);
241         envConfig.setConfigParam("je.nodeMaxEntries", "4");
242         envConfig.setConfigParam("je.nodeDupTreeMaxEntries", "4");
243         env = new Environment(envHome, envConfig);
244
245         DatabaseConfig dbConfig = new DatabaseConfig();
246         dbConfig.setAllowCreate(create);
247         dbConfig.setTransactional(true);
248         dbConfig.setExclusiveCreate(create);
249         db = env.openDatabase(null, "foo", dbConfig);
250     }
251
252     private void setWaiterHook() {
253         TestHook hook = new WaiterHook();
254         DbInternal.dbGetDatabaseImpl(db).getTree().setWaitHook(hook);
255     }
256
257     /*
258      * This hook merely acts as a barrier. 2 threads enter and cannot
259      * proceed until both have arrived at that point.
260      */
261     static class WaiterHook implements TestHook {
262         private int numArrived;
263         private Object JavaDoc block;
264
265         WaiterHook() {
266             numArrived = 0;
267             block = new Object JavaDoc();
268         }
269
270         public void doHook() {
271             synchronized (block) {
272                 if (numArrived == 0) {
273                     numArrived = 1;
274                     try {
275                         block.wait();
276                     } catch (InterruptedException JavaDoc e) {
277                         e.printStackTrace();
278                     }
279                 } else if (numArrived == 1) {
280                     numArrived = 2;
281                     block.notify();
282                 }
283             }
284         }
285
286     public void doIOHook()
287         throws IOException JavaDoc {
288
289     }
290
291         public Object JavaDoc getHookValue() {
292             return null;
293         }
294     }
295
296     /* This thread merely inserts the specified value. */
297     static class InsertThread extends Thread JavaDoc {
298         private int value;
299         private Database db;
300         
301         InsertThread(int value, Database db) {
302             this.value = value;
303             this.db = db;
304         }
305
306         public void run() {
307             try {
308                 put(db, value);
309             } catch (Exception JavaDoc e) {
310                 e.printStackTrace();
311                 fail(e.getMessage());
312             }
313         }
314     }
315 }
316
Popular Tags