INList


1   /*-
2    * See the file LICENSE for redistribution information.
3    *
4    * Copyright (c) 2002,2006 Oracle.  All rights reserved.
5    *
6    * $Id: INList.java,v 1.48 2006/10/30 21:14:15 bostic Exp $
7    */
8   
9   package com.sleepycat.je.dbi;
10  
11  import java.util.HashSet  ;
12  import java.util.Iterator  ;
13  import java.util.Set  ;
14  import java.util.SortedSet  ;
15  import java.util.TreeSet  ;
16  
17  import com.sleepycat.je.DatabaseException;
18  import com.sleepycat.je.latch.Latch;
19  import com.sleepycat.je.latch.LatchSupport;
20  import com.sleepycat.je.tree.IN;
21  
22  /**
23   * The INList is a list of in-memory INs for a given environment. 
24   */
25  public class INList {
26      private static final String   DEBUG_NAME = INList.class.getName();
27      private SortedSet   ins = null; 
28      private Set   addedINs = null;
29      private EnvironmentImpl envImpl;
30  
31      /* If both latches are acquired, major must always be acquired first. */
32      private Latch majorLatch;
33      private Latch minorLatch;
34  
35      private boolean updateMemoryUsage;
36  
37      INList(EnvironmentImpl envImpl) {
38          this.envImpl = envImpl;
39          ins = new TreeSet  ();
40      addedINs = new HashSet  ();
41          majorLatch =
42          LatchSupport.makeLatch(DEBUG_NAME + " Major Latch", envImpl);
43          minorLatch =
44          LatchSupport.makeLatch(DEBUG_NAME + " Minor Latch", envImpl);
45          updateMemoryUsage = true;
46      }
47  
48      /**
49       * Used only by tree verifier when validating INList. Must be called with
50       * orig.majorLatch acquired.
51       */
52      public INList(INList orig, EnvironmentImpl envImpl)
53      throws DatabaseException {
54  
55      ins = new TreeSet  (orig.getINs());
56      addedINs = new HashSet  ();   
57          this.envImpl = envImpl;
58          majorLatch =
59          LatchSupport.makeLatch(DEBUG_NAME + " Major Latch", envImpl);
60          minorLatch =
61          LatchSupport.makeLatch(DEBUG_NAME + " Minor Latch", envImpl);
62          updateMemoryUsage = false;
63      }
64  
65      /* 
66       * We ignore latching on this method because it's only called from validate
67       * which ignores latching anyway.
68       */
69      public SortedSet   getINs() {
70      return ins;
71      }
72  
73      /* 
74       * Don't require latching, ok to be imprecise.
75       */
76      public int getSize() {
77      return ins.size();
78      }
79  
80      /**
81       * An IN has just come into memory, add it to the list.
82       */
83      public void add(IN in)
84      throws DatabaseException {
85  
86      boolean enteredWithLatchHeld = majorLatch.isOwner();
87          boolean addToMajor = true;
88          try {
89              if (enteredWithLatchHeld) {
90  
91                  /* 
92                   * Don't try to acquire the major latch twice, that's not
93                   * supported. If we do hold the latch, don't modify the major
94                   * list, we may be faulting in an IN while iterating over the
95                   * list from the evictor.
96                   */
97                  addToMajor = false;
98              } else {
99                  if (!(majorLatch.acquireNoWait())) {
100                     /* We couldn't acquire the latch. */
101                     addToMajor = false;
102                 }
103             }
104 
105             if (addToMajor) {
106                 addAndSetMemory(ins, in);
107             } else {
108                 minorLatch.acquire();
109                 try {
110                     addAndSetMemory(addedINs, in);
111                 } finally {
112                     minorLatch.release();
113                 }
114 
115                 /*
116                  * The holder of the majorLatch may have released it.  If so,
117                  * try to put the minor list into the major list so no INs are
118                  * orphaned.
119                  */
120                 if (!enteredWithLatchHeld) {
121                     if (majorLatch.acquireNoWait()) {
122                         try {
123                             latchMinorAndDumpAddedINs();
124                         } finally {
125                             releaseMajorLatch();
126                         }
127                     }
128                 }
129             }
130         } finally {
131             if (addToMajor) {
132                 releaseMajorLatchIfHeld();
133             }
134         }
135     }
136     
137     private void addAndSetMemory(Set   set, IN in) {
138         boolean addOk  = set.add(in);
139 
140         assert addOk : "failed adding in " + in.getNodeId();
141 
142         if (updateMemoryUsage) {
143             MemoryBudget mb =  envImpl.getMemoryBudget();
144             mb.updateTreeMemoryUsage(in.getInMemorySize());
145             in.setInListResident(true);
146         }
147     }
148 
149     /**
150      * An IN is getting evicted or is displaced by recovery.  Caller is
151      * responsible for acquiring the major latch before calling this and
152      * releasing it when they're done.
153      */
154     public void removeLatchAlreadyHeld(IN in)
155     throws DatabaseException {
156 
157     assert majorLatch.isOwner();
158         boolean removeDone = ins.remove(in);
159         if (!removeDone) {
160             /* Look in addedINs set. */
161             minorLatch.acquire();
162             try {
163                 removeDone = addedINs.remove(in);
164                 dumpAddedINsIntoMajorSet();
165             } finally {
166                 minorLatch.release();
167             }
168         }
169 
170         assert removeDone;
171 
172         if (updateMemoryUsage) {
173             envImpl.getMemoryBudget().
174                 updateTreeMemoryUsage(in.getAccumulatedDelta() -
175                       in.getInMemorySize());
176             in.setInListResident(false);
177         }
178     }
179 
180     /**
181      * An IN is getting swept or is displaced by recovery.
182      */
183     public void remove(IN in)
184     throws DatabaseException {
185 
186         assert LatchSupport.countLatchesHeld() == 0;
187         majorLatch.acquire();
188         try {
189             removeLatchAlreadyHeld(in);
190         } finally {
191             releaseMajorLatch();
192         }
193     }
194 
195     public SortedSet   tailSet(IN in)
196     throws DatabaseException {
197 
198     assert majorLatch.isOwner();
199     return ins.tailSet(in);
200     }
201 
202     public IN first()
203     throws DatabaseException {
204 
205     assert majorLatch.isOwner();
206     return (IN) ins.first();
207     }
208 
209     /**
210      * Return an iterator over the main 'ins' set.  Returned iterator will not
211      * show the elements in addedINs.
212      *
213      * The major latch should be held before entering.  The caller is
214      * responsible for releasing the major latch when they're finished with the
215      * iterator.
216      *
217      * @return an iterator over the main 'ins' set.
218      */
219     public Iterator   iterator() {
220     assert majorLatch.isOwner();
221     return ins.iterator();
222     }
223 
224     /**
225      * Clear the entire list during recovery and at shutdown.
226      */
227     public void clear()
228     throws DatabaseException {
229 
230         assert LatchSupport.countLatchesHeld() == 0;
231         majorLatch.acquire();
232     minorLatch.acquire();
233         ins.clear();
234     addedINs.clear();
235     minorLatch.release();
236         releaseMajorLatch();
237 
238         if (updateMemoryUsage) {
239             envImpl.getMemoryBudget().refreshTreeMemoryUsage(0);
240         }
241     }
242 
243     public void dump() {
244         System.out.println("size=" + getSize());
245     Iterator   iter = ins.iterator();
246     while (iter.hasNext()) {
247         IN theIN = (IN) iter.next();
248         System.out.println("db=" + theIN.getDatabase().getId() +
249                                " nid=: " + theIN.getNodeId() + "/" +
250                    theIN.getLevel());
251     }
252     }
253 
254     /**
255      * The locking hierarchy is:
256      *   1. INList major latch.
257      *   2. IN latch.
258      * In other words, the INList major latch must be taken before any IN
259      * latches to avoid deadlock. 
260      */
261     public void latchMajor()
262     throws DatabaseException {
263 
264         assert LatchSupport.countLatchesHeld() == 0;
265     majorLatch.acquire();
266     }
267 
268     public void releaseMajorLatchIfHeld()
269     throws DatabaseException {
270 
271     if (majorLatch.isOwner()) {
272         releaseMajorLatch();
273     }
274     }
275 
276     public void releaseMajorLatch()
277     throws DatabaseException {
278 
279     /*
280      * Before we release the major latch, take a look at addedINs and see
281      * if anything has been added to it while we held the major latch.  If
282      * so, added it to ins.
283      */
284         latchMinorAndDumpAddedINs();
285     majorLatch.release();
286     }
287 
288     private void dumpAddedINsIntoMajorSet() {
289     if (addedINs.size() > 0) {
290         ins.addAll(addedINs);
291         addedINs.clear();
292     }
293     }
294 
295     void latchMinorAndDumpAddedINs() 
296         throws DatabaseException {
297 
298     latchMinor();
299         try {
300             dumpAddedINsIntoMajorSet();
301         } finally {
302             releaseMinorLatch();
303         }
304     }
305 
306     private void latchMinor()
307     throws DatabaseException {
308 
309     minorLatch.acquire();
310     }
311 
312     private void releaseMinorLatch()
313     throws DatabaseException {
314 
315     minorLatch.release();
316     }
317 }
318
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags