GarbageCollector


1   // You can redistribute this software and/or modify it under the terms of
2   // the Ozone Core License version 1 published by ozone-db.org.
3   //
4   // The original code and portions created by SMB are
5   // Copyright (C) 1997-@year@ by SMB GmbH. All rights reserved.
6   //
7   // $Id: GarbageCollector.java,v 1.7 2002/12/29 11:15:56 per_nyfelt Exp $
8   package org.ozoneDB.core;
9   
10  import org.ozoneDB.DxLib.DxIterator;
11  import org.ozoneDB.*;
12  import org.ozoneDB.util.LogWriter;
13  import org.ozoneDB.data.SimpleArrayList;
14  import org.ozoneDB.io.stream.NullOutputStream;
15  
16  import java.io.IOException  ;
17  import java.io.ObjectOutputStream  ;
18  import java.util.HashSet  ;
19  import java.util.LinkedList  ;
20  
21  /**
22      Marks reachable objects and sweeps unreachable objects.
23      <DIV>
24          This implementation has at least following deficiencies:
25          <UL>
26              <LI>
27                  Method invocation observation is limited to the direct method parameters and the return value.
28                  A correct implementation should observe not only method parameters and return values but
29                  all objects which are reachable from these objects.
30              </LI>
31              <LI>
32                  Currently, the implementation is not scaleable, because the list
33                  {@link #surelyReachableObjectsWhichHaveToBeMarkedAsSuch} may grow to the count of objects.
34                  Possible solutions are:
35                  <UL>
36                      <LI>
37                          Export some contents of this stack to disk. This seems to be highly efficient, because
38                          the "hot spot" of the corresponding file always would be the end of the file.
39                      </LI>
40                      <LI>
41                          Simply forget entries if they are too much. Work through the whole list until it is empty.
42                          Once the list is empty, walk through all objects to refill this list and continue.
43                          This approach has some appeals, but seems to be element of O(n^2) for large databases because
44                          there would be n*c1 walks trough 1/2*n objects each walk.
45                      </LI>
46                  </UL>
47              </LI>
48          </UL>
49      </DIV>
50  
51      @author Xu?n Baldauf (<A HREF="http://www.medium.net/">Medium.net</A)>
52  */
53  public class GarbageCollector extends ServerComponent implements Runnable   {
54  
55      /**
56          Our database environment
57      */
58  //  protected   Env     env;
59  
60     /**
61          The thread which actually does the work.
62      */
63      protected   Thread    garbageCollectionThread;
64  
65      /**
66          The list of  {@link Transaction}s, which have to be completed before the GarbageCollector
67          may start. It may not start earlier because the rollback of those transaction may make
68          objects live which were believed to be dead.
69      */
70      protected   HashSet   transactionsRequiredToComplete;
71  
72      /**
73          The number which represents the current garbage collection run.
74          This number is the number mentioned in {@link org.ozoneDB.core.storage.wizardStore.WizardObjectContainer#garbageCollectionLevel}.
75          There are tree sets of database objects
76          <UL>
77              <LI>probablyReachable: These objects may or may not be reachable. Their garbageCollectionLevel is below the currentGarbageCollectionLevel</LI>
78              <LI>surelyReachable: These objects have been reached during the walk. Their garbageCollectionLevel is currentGarbageCollectionLevel</LI>
79              <LI>doneReachable: These object have been processed for members. All their members are surelyReachable or better. Their garbageCollectionLevel is currentGarbageCollectionLevel+1</LI>
80          </UL>
81      */
82      protected   int     currentGarbageCollectionLevel;
83  
84      /**
85          The garbageCollectionLevel which objects have if they belong to the doneReachable set.
86          This is {@link #currentGarbageCollectionLevel}+1
87      */
88      protected   int     doneReachableGarbageCollectionLevel;
89  
90      /**
91          The current phase this GarbageCollector is in. Access only within synchronization to this object.
92      */
93      protected   int     phase   =   PHASE_IDLE;
94  
95      /** Doing nothing */
96      protected final static int  PHASE_IDLE                                      =   0;
97  
98      /** A run has been initiated */
99      protected final static int  PHASE_RUN_INITIATED                             =   1;
100 
101     /** Waiting for the old transactions to complete */
102     protected final static int  PHASE_WAITING_FOR_OLD_TRANSACTIONS_TO_COMPLETE  =   2;
103 
104     /** We may start, all old transactions are complete */
105     protected final static int  PHASE_READY_TO_START                            =   3;
106 
107     /** We are started, we are marking all reachable objects */
108     protected final static int  PHASE_MARKING                                   =   4;
109 
110     /** Waiting for the old transactions to complete */
111     protected final static int  PHASE_WAITING_FOR_NEW_TRANSACTIONS_TO_COMPLETE  =   5;
112 
113     /** We are started, we are marking all reachable objects */
114     protected final static int  PHASE_MARKING2                                  =   6;
115 
116     /** We are started, we are sweeping all unreachable objects */
117     protected final static int  PHASE_SWEEPING                                  =   7;
118 
119     /** Somebody requested to finish prematurely... */
120 //  protected final static int  PHASE_KILL                                      =   -1;
121 
122     /**
123         The current transaction of this garbageCollector.
124     */
125     protected   Transaction     transaction;
126 
127     /**
128         The count of actions which were done within this garbageCollector.
129     */
130     protected   int             actionsWithinTransactionCount   =   0;
131 
132     /**
133         A stack of ObjectIDs of objects, which are surely reachable, but still
134         were not marked as such.
135         Access only during synchronization on it.
136     */
137 //  protected   DxListDeque     surelyReachableObjectsWhichHaveToBeMarkedAsSuch;
138     protected   SimpleArrayList surelyReachableObjectsWhichHaveToBeMarkedAsSuch;
139 
140     /**
141         The list of ObjectIDs of objects which are surelyReachable and already were tried to
142         be processed but where locking the objects failed. The processing the contents of this
143         list should be retried some times later.
144 
145         To minimize overhead, access is only allowed during synchronization to {@link #surelyReachableObjectsWhichHaveToBeMarkedAsSuch}
146     */
147     protected   LinkedList        surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContented;
148 
149     /**
150         This is the lock that everybody has to be synchronized to in order to
151         be able to access any garbageCollectionLevel in any object within this database.
152     */
153     protected   Object            garbageCollectionLevelsLock =   new Object  ();
154 
155     /**
156         Wether we should stop running as soon as possible. Synchronization is not required,
157         because it does not matter wether we receive this signal soon or later.
158     */
159     protected   boolean         kill                        =   false;
160 
161     /**
162         Creates a new garbage collector.
163     */
164     protected GarbageCollector(Env env) {
165         super(env);
166 //      this.env                        =   env;
167         setCurrentGarbageCollectionLevel(env.getState().intProperty(env.getState().GARBAGE_COLLECTION_LEVEL,0));
168 //      surelyReachableObjectsWhichHaveToBeMarkedAsSuch =   new DxListDeque;
169         surelyReachableObjectsWhichHaveToBeMarkedAsSuch =   new SimpleArrayList(10000); // We expect at least 10000 entries in a busy database.
170         surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContented  =   new LinkedList  ();
171         transactionsRequiredToComplete  =   new HashSet  ();
172     }
173 
174     protected void setCurrentGarbageCollectionLevel(int to) {
175         synchronized (garbageCollectionLevelsLock) {
176             this.currentGarbageCollectionLevel          =   to;
177             this.doneReachableGarbageCollectionLevel    =   this.currentGarbageCollectionLevel+1;
178         }
179     }
180 
181     public void startup() {
182         env.getLogWriter().newEntry( this, "startup...", LogWriter.INFO);
183         env.getLogWriter().newEntry( this, "garbageCollection level set to " + currentGarbageCollectionLevel, LogWriter.DEBUG);
184     }
185 
186 
187     public void shutdown() {
188         kill = true;
189     }
190 
191 
192     public void save() {
193     }
194 
195     /**
196         Starts the garbage collection process.
197     */
198     public void start() {
199         env.getLogWriter().newEntry(this,"start()", LogWriter.DEBUG1);
200         synchronized (this) {
201             if (phase==PHASE_IDLE) {
202                 if (garbageCollectionThread==null) {
203                     setPhase(PHASE_RUN_INITIATED);
204                     garbageCollectionThread =   env.getInvokeServer().newThread(this);
205                     garbageCollectionThread.start();
206                 } else {
207                     // We're already started
208                 }
209             } else {
210                 // We're already started
211             }
212         }
213     }
214 
215     public void addTransactionRequiredToComplete(Object   ta) {
216         transactionsRequiredToComplete.add(ta);
217     }
218 
219     public void removeTransactionRequiredToComplete(Transaction ta) {
220         if (!transactionsRequiredToComplete.isEmpty()) {
221             transactionsRequiredToComplete.remove(ta);
222             checkForEndOfWaitForCurrentTransactionsToCompletePhase();
223         }
224     }
225 
226     protected void checkForEndOfWaitForCurrentTransactionsToCompletePhase() {
227         if (transactionsRequiredToComplete.isEmpty()) {
228             notifyEndOfWaitForCurrentTransactionsToCompletePhase();
229         }
230     }
231 
232     /**
233         Informs this GarbageCollector, the the pre-phase is done, there are no transactions that
234         are older than this garbage collector run.
235     */
236     protected void notifyEndOfWaitForCurrentTransactionsToCompletePhase() {
237         synchronized (this) {
238             /*
239             if (phase==PHASE_WAITING_FOR_OLD_TRANSACTIONS_TO_COMPLETE) {
240                 phase = PHASE_READY_TO_START;
241             }
242             */
243             setPhase(phase+1);
244             notify();
245         }
246     }
247 
248     protected void incCurrentGarbageCollectorLevel() {
249         setCurrentGarbageCollectionLevel(currentGarbageCollectionLevel+4);
250         env.getState().setIntProperty(env.getState().GARBAGE_COLLECTION_LEVEL,currentGarbageCollectionLevel);
251         setChanged();
252     }
253 
254     /**
255         The main method for garbage collection.
256     */
257     public void run() {
258         env.getLogWriter().newEntry(this,"garbage collection running...",LogWriter.DEBUG);
259         try {
260             incCurrentGarbageCollectorLevel();
261 
262             setPhase(PHASE_WAITING_FOR_OLD_TRANSACTIONS_TO_COMPLETE);
263 
264             env.getTransactionManager().startGarbageCollectionWaitForCurrentTransactionsToCompletePhase(this);
265 
266             waitForPhase(PHASE_READY_TO_START);
267 
268             renewTransactionIfRequired();
269 
270             addRootSetElementsToSurelyReachableSet();
271 
272             setPhase(PHASE_MARKING);
273 
274             processSurelyReachableObjectsWhichHaveToBeMarkedAsSuch();
275 
276             if (kill) {
277                 return;
278             }
279 
280             setPhase(PHASE_WAITING_FOR_NEW_TRANSACTIONS_TO_COMPLETE);
281 
282             env.getTransactionManager().startGarbageCollectionWaitForCurrentTransactionsToCompletePhase(this);
283 
284             waitForPhase(PHASE_MARKING2);
285 
286             processSurelyReachableObjectsWhichHaveToBeMarkedAsSuch();
287 
288             if (kill) {
289                 return;
290             }
291 
292             setPhase(PHASE_SWEEPING);
293 
294             sweepUnreachableObjects();
295 
296         } catch (Throwable   e) {
297             env.getLogWriter().newEntry(this,"GC caught: ",e,env.getLogWriter().ERROR);
298         } finally {
299             env.getLogWriter().newEntry(this,"garbage collection end...",LogWriter.DEBUG);
300             garbageCollectionThread = null;
301             setPhase(PHASE_IDLE);
302             try {
303                 if (transaction!=null) { // We are crashing with an open transaction, let's abort it..
304                     internalAbortTransaction(transaction);
305 //                  internalFinishTransaction(transaction);
306                     env.getTransactionManager().deleteTransaction();
307                     transaction = null;
308                 }
309             } catch (ClassNotFoundException   e) {
310                 env.getLogWriter().newEntry(this,"caught: ",e,env.getLogWriter().ERROR);
311             } catch (IOException   e) {
312                 env.getLogWriter().newEntry(this,"caught: ",e,env.getLogWriter().ERROR);
313             }
314         }
315     }
316 
317     protected void notifyAboutTransactionActionAndRenewTransactionIfRequired() throws IOException  ,ClassNotFoundException  ,TransactionException {
318         renewTransactionIfRequired();
319         actionsWithinTransactionCount++;
320     }
321 
322     /**
323         Checks wether the current transaction has to be committed (because it accumulated too much changes)
324         and if so, commits it and closes it. Afterwards (or if there has not been a current transaction already),
325         it creates a new current transaction.
326     */
327     protected void renewTransactionIfRequired() throws IOException  ,ClassNotFoundException  ,TransactionException {
328         if (actionsWithinTransactionCount>=100) { // We renew if we had 100 or more actions within this transaction.
329             completeTransaction();
330 
331             env.getLogWriter().newEntry(this,"toBeProcessedCount="+surelyReachableObjectsWhichHaveToBeMarkedAsSuch.size()+".",env.getLogWriter().DEBUG1);
332 
333         }
334 
335         if (transaction==null) {
336             transaction = env.getTransactionManager().newTransaction(env.getUserManager().getGarbageCollectorUser());
337         }
338     }
339 
340     /**
341         Completes the current transaction and releases it.
342     */
343     protected void completeTransaction() throws IOException  ,ClassNotFoundException   {
344         if (transaction!=null) {
345             internalCompleteTransaction(transaction);
346             actionsWithinTransactionCount   =   0;
347             env.getTransactionManager().deleteTransaction();
348             transaction = null;
349         }
350     }
351 
352 
353     protected void internalCompleteTransaction(Transaction transaction) throws IOException  ,ClassNotFoundException   {
354         boolean allright = false;
355         try {
356             transaction.prepareCommit();
357             allright = true;
358         } finally {
359             if (!allright) {
360                 internalAbortTransaction(transaction);
361             }
362         }
363 
364         internalFinishTransaction(transaction);
365     }
366 
367     protected void internalFinishTransaction(Transaction transaction) throws IOException  ,ClassNotFoundException   {
368         TransactionManager transactionManager = transaction.getManager();
369 
370         try {
371             transactionManager.beginExclusion();
372             transaction.commit();
373         } finally {
374             transactionManager.endExclusion();
375             transactionManager.notifyWaitingTransactions();
376         }
377     }
378 
379     protected void internalAbortTransaction(Transaction transaction) throws IOException  ,ClassNotFoundException   {
380         TransactionManager transactionManager = transaction.getManager();
381         try {
382             transactionManager.beginExclusion();
383             transaction.abort(null);
384         } finally {
385             transactionManager.endExclusion();
386             transactionManager.notifyWaitingTransactions();
387         }
388     }
389 
390     protected synchronized void setPhase(int to) {
391         phase = to;
392         env.getLogWriter().newEntry(this,"setPhase("+to+")",env.getLogWriter().DEBUG2);
393     }
394 
395     protected synchronized void waitForPhase(int newPhase) throws InterruptedException   {
396         while (phase!=newPhase) {
397             wait();
398         }
399     }
400 
401     protected void addRootSetElementsToSurelyReachableSet() {
402         startFilterDatabaseObjectReferencesAtExternalDatabaseGates();
403         addAllNamedObjectsToSurelyReachableSet();
404     }
405 
406 
407     protected void startFilterDatabaseObjectReferencesAtExternalDatabaseGates() {
408         env.getInvokeServer().startFilterDatabaseObjectReferencesExports(this);
409         env.getLocalClientTracker().startFilterDatabaseObjectReferencesExports(this);
410     }
411 
412     public void notifyDatabaseObjectIsExported(ObjectID id) {
413         notifyDatabaseObjectIsAboutToBeExported(id);
414     }
415 
416     /**
417         This method is called by DbInvokeClient to notify this garbageCollector
418         that there is a reference which is to be exported to a client.
419     */
420     public void notifyDatabaseObjectIsAboutToBeExported(ObjectID id) {
421         // These object referenced belong, because they are used, to the surelyReachable set.
422         ensureSurelyReachable(id);
423     }
424 
425     /**
426         This method walks through all named objects and adds each of them to the surelyReachable set.
427     */
428     protected void addAllNamedObjectsToSurelyReachableSet() {
429         env.getStoreManager().reportNamedObjectsToGarbageCollector();
430     }
431 
432     /**
433         This method is called by StoreManager to indicate that the object
434         with the given id is a named object.
435     */
436     public void notifyNamedObject(ObjectID id) {
437         ensureSurelyReachable(id);
438     }
439 
440     /**
441         This method is called by StoreManager in the event an unnamed object receives a name.
442         This is the case if an object which was formerly unnamed gets a name.
443     */
444     public void notifyNewObjectName(ObjectContainer objectContainer) {
445         ensureSurelyReachable(objectContainer);
446     }
447 
448     /**
449         This method is called by StoreManager in the event an object is freshly created.
450     */
451     public void notifyNewObjectContainer(/*Transaction transaction,*/ObjectContainer objectContainer) {
452         ensureDoneReachable(/*transaction,*/objectContainer);
453     }
454 
455     /**
456         Calling this method makes sure that the object which is referenced by the given ID is
457         at least surely reachable.
458     */
459     protected void ensureSurelyReachable(ObjectID id) {
460         synchronized (this) {
461             if (isRunning()) {
462                 addObjectIDToSurelyReachableObjectsWhichHaveToBeMarkedAsSuch(id);
463             }
464         }
465     }
466 
467     /**
468         This method may be called both from transaction threads and from GarbageCollector-Threads.
469     */
470     protected void addObjectIDToSurelyReachableObjectsWhichHaveToBeMarkedAsSuch(ObjectID id) {
471         synchronized (surelyReachableObjectsWhichHaveToBeMarkedAsSuch) {
472 //          env.getLogWriter().newEntry(this,"addObjectID(): adding "+id+".",new Exception(),env.getLogWriter().DEBUG3);
473             surelyReachableObjectsWhichHaveToBeMarkedAsSuch.push(id);
474         }
475     }
476 
477     /**
478         Calling this method makes sure that the object which is referenced by the given ID is
479         at least surely reachable. This method is called by non-GarbageCollector-Threads.
480     */
481     protected void ensureSurelyReachable(ObjectContainer objectContainer) {
482         // This is not possible because processing has to be done within a GarbageCollector transaction and not within any other transaction.
483         /*
484         objectContainer.pin();
485         processObjectContainerWhichWantsToBeSurelyReachable(objectContainer);
486         */
487         addObjectIDToSurelyReachableObjectsWhichHaveToBeMarkedAsSuch(objectContainer.id());
488     }
489 
490     /**
491         Returns wether this GarbageCollector is running. This method
492         must be called during synchronization on this GarbageCollector.
493     */
494     protected boolean isRunning() {
495         return phase!=PHASE_IDLE;
496     }
497 
498     /**
499         This is the "main()" method of the mark phase.
500     */
501     protected void processSurelyReachableObjectsWhichHaveToBeMarkedAsSuch() {
502         ObjectID id;
503 
504         int surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContentedSize = -1;
505 
506         retryLoop:
507         for (;;) {
508             for (;;) {
509                 if (kill) {
510                     break retryLoop;
511                 }
512                 synchronized (surelyReachableObjectsWhichHaveToBeMarkedAsSuch) {
513                     id = (ObjectID) surelyReachableObjectsWhichHaveToBeMarkedAsSuch.pop();
514                 }
515 
516                 if (id==null) {
517                     break;
518                 }
519 
520                 try {
521                     /*
522                     ObjectContainer container = env.getStoreManager().containerForID(null,id);
523 
524                     processObjectContainerWhichWantsToBeSurelyReachable(container);
525                     */
526 
527                     // We should acquire the container via our transaction
528                     notifyAboutTransactionActionAndRenewTransactionIfRequired();
529 
530 //                  env.getLogWriter().newEntry(this,"process(): processing "+id+".",env.getLogWriter().DEBUG3);
531 
532                     ObjectContainer container = transaction.acquireObject(id,Lock.LEVEL_READ);
533 
534                     processObjectContainerWhichWantsToBeSurelyReachable(transaction,container);
535 //              } catch (ObjNotFoundException e) {
536                 } catch (ObjectNotFoundException e) {
537                 } catch (ClassNotFoundException   e) {
538                 } catch (IOException   e) {
539                     // It does not matter if the object is gone in the meantime. This is the best case for a garbage collector :-)
540                 } catch (TransactionException e) {
541                     env.getLogWriter().newEntry(this,"caught: ",e,env.getLogWriter().ERROR);
542                     // FIXME. What do we in this case?
543                 }
544             }
545 
546             boolean waitRecommended;
547 
548             synchronized (surelyReachableObjectsWhichHaveToBeMarkedAsSuch) {
549                 waitRecommended = surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContentedSize==surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContented.size();
550 
551                 surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContentedSize = surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContented.size();
552 
553                 while (!surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContented.isEmpty()) {
554                     surelyReachableObjectsWhichHaveToBeMarkedAsSuch.push(surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContented.getFirst());
555                 }
556             }
557 
558             if (surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContentedSize>0) {
559                 if (waitRecommended) {
560                     try {
561                         try {
562                             completeTransaction(); // We should finish our transaction so that other transactions may complete.
563                         } catch (ClassNotFoundException   e) {
564                             env.getLogWriter().newEntry(this,"caught: ",e,env.getLogWriter().ERROR);
565                         } catch (IOException   e) {
566                             env.getLogWriter().newEntry(this,"caught: ",e,env.getLogWriter().ERROR);
567                         }
568 
569                         // We're waiting less if there are more lock-contented objects, but at least 100ms
570                         Thread.sleep(100+2000/(surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContentedSize));
571                     } catch (InterruptedException   e) {
572                     }
573                 }
574             } else {
575                 break;
576             }
577         }
578 
579         try {
580             completeTransaction();
581         } catch (ClassNotFoundException   e) {
582             env.getLogWriter().newEntry(this,"caught: ",e,env.getLogWriter().ERROR);
583         } catch (IOException   e) {
584             env.getLogWriter().newEntry(this,"caught: ",e,env.getLogWriter().ERROR);
585         }
586         // Pheew. We're done. Now sweep the unreachable objects.
587     }
588 
589     /**
590         Internally ensures that the given object is at least surelyReachable.
591 
592         @return
593             <0 if this object has been updated. If this is the case, this object has to join a transaction which will complete successfully.
594             =0 if this object has not been updated, it is surelyReachable
595             >0 if this object has not been updated, it is processedReachable
596     */
597     protected int internalEnsureSurelyReachable(ObjectContainer objectContainer) {
598         synchronized (garbageCollectionLevelsLock) {
599             return objectContainer.ensureGarbageCollectionLevel(currentGarbageCollectionLevel);
600         }
601     }
602 
603     /**
604         Ensures that the given object is doneReachable.
605     */
606     protected void ensureDoneReachable(/*Transaction transaction,*/ObjectContainer objectContainer) {
607         internalEnsureDoneReachable(objectContainer);
608     }
609 
610     /**
611         Internally ensures that the given object is doneReachable.
612     */
613     protected void internalEnsureDoneReachable(ObjectContainer objectContainer) {
614         synchronized (garbageCollectionLevelsLock) {
615             objectContainer.ensureGarbageCollectionLevel(doneReachableGarbageCollectionLevel);
616         }
617     }
618 
619 
620     /**
621      *   Processes an ObjectContainer which possibly has not already been registered as surely reachable.
622      *   This method may be called only by the garbage collector thread.
623      *
624      * @param transaction
625      * @param objectContainer
626      */
627     protected void processObjectContainerWhichWantsToBeSurelyReachable(Transaction transaction,ObjectContainer objectContainer) {
628         try {
629             int difference = internalEnsureSurelyReachable(objectContainer);
630 
631 //          env.getLogWriter().newEntry(this,"processObjectContainerWhichWantsToBeSurelyReachable("+objectContainer+"), difference="+difference+".",env.getLogWriter().DEBUG3);
632 
633             if (difference<=0) {
634                 processReferencesByThisObject(transaction,objectContainer);
635             }
636         } finally {
637             objectContainer.unpin();
638         }
639     }
640 
641     /**
642         Determines all references which are "contained" within the given object,
643         adds them to the list of {@link #surelyReachableObjectsWhichHaveToBeMarkedAsSuch}
644         and then marks the given object as doneReachable.
645 
646         This method may be called by any CommandThread.
647     */
648     protected void processReferencesByThisObject(Transaction transaction,ObjectContainer objectContainer) {
649         /*
650         CommandThread   thread      =   (CommandThread) Thread.currentThread();
651         Transaction     transaction =   thread.transaction();
652         */
653 
654         /*
655             We really only need READ locks, because only read and do not write the object.
656             But with READ locks, there may be transactions which have invoked a method on
657             this object. We do not want to read the object in this state, because there
658             may be references temporarily taken out of the object but onto the stack
659             which we would miss.
660 
661             That is why we must ensure that nobody has invoked the object currently.
662             This should be - in theory - be possible by checking WizardObjectContainer.invokeCount,
663             but this is not an option in practice because accessing invokeCount is not
664             synchronized. This may lead to the situation that this thread does not see
665             an invokeCount!=1 while the other thread which invoked the object already has
666             set invokeCount to !=1.
667 
668             Additionally, checking invokeCount would not suffice because a transaction thread
669             may invoke the object during our proxy identification.
670 
671             That is why we must use an exclusive lock, which is a write lock.
672         */
673 //      int previousLockLevel = objectContainer.lock().tryAcquire(transaction,Lock.LEVEL_READ);
674         int previousLockLevel = objectContainer.lock().tryAcquire(transaction,Lock.LEVEL_WRITE);
675 
676         if (previousLockLevel!=Lock.NOT_ACQUIRED) {
677             try {
678                 env.getStoreManager().updateLockLevel(transaction,objectContainer);
679                 GarbageCollectorProxyObjectIdentificationObjectOutputStream identificator = new GarbageCollectorProxyObjectIdentificationObjectOutputStream();
680 
681                 identificator.identifyProxys(objectContainer);
682 
683                 internalEnsureDoneReachable(objectContainer);
684             } catch (IOException   e) {
685                 // only supported from JDK1.4 on
686 //              throw new RuntimeException("Caught during serialization for proxy object identification: ",e);
687                 throw new RuntimeException  ("Caught during serialization for proxy object identification: "+e);
688             } finally {
689                 // The lock is released on transaction commit.
690 //              objectContainer.lock().release(transaction);
691             }
692         } else {
693             deferProcessingOfObjectContainerDueToLockContention(objectContainer);
694         }
695     }
696 
697     /**
698         Defers the processing of the given objectContainer because locking was not possible at current time.
699         Because objectContainers may be modified in the meantime
700         (in the case they are unloaded and loaded again, we would hold an old copy of objectContainer which
701         does not reflect the changes made to the new objectContainer), it's not wise to queue the ObjectContainer.
702         Instead, we have to queue the ObjectID of that ObjectContainer.
703     */
704     protected void deferProcessingOfObjectContainerDueToLockContention(ObjectContainer objectContainer) {
705         synchronized (surelyReachableObjectsWhichHaveToBeMarkedAsSuch) {
706             surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContented.add(objectContainer.id());
707         }
708     }
709 
710     /**
711         This method is called by Transactions to indicate that a method of the object callee
712         will be called by the transaction.
713 
714         This method will always be called, even if the GarbageCollector is not startet.
715     */
716     public void interceptInvocationPre(Transaction transaction,ObjectContainer callee,Object  [] args) {
717 
718         /*
719             This looks dangerous but is effective.
720             The method isRunning() is called without the lock on this GarbageCollector.
721 
722             This is safe because this GarbageCollector only really starts to run after all transactions which
723             existed during the initiation have completed. All new transactions see the right value of
724             isRunning because there is a synchronization on creation of such a transaction.
725 
726             The other possibility is that old transactions see this too early. But in this case, all
727             what can happen is that the callStack is empty and therefore the caller is null.
728 
729             The speed gain is that method invocation may be not disturbed at all on HotSpot VMs, where
730             calls to this method may be fully optimized away as long as isRunning() is constant.
731         */
732         if (isRunning()) {
733             SimpleArrayList callStack   =   transaction.getCallStack();
734 
735            try {
736                 if (args!=null) {
737                     ObjectContainer caller      =   (ObjectContainer) callStack.peek();
738 
739                     if (caller!=null) {
740 
741                         /*
742                             There is a design decision which heavily affects performance:
743                             -   Do we first check for the possibility of an OzoneProxy as parameter or
744                             -   Do we first check for the cross of the border of the different sets of database objects?
745 
746                             If we use true here, the first option is used.
747                             If we use false here, the first option is used.
748                         */
749                         if (false) {
750                             /*
751                                 This spaghetti code is for speed.
752                                 -   If we find an OzoneProxy, we have to look deeper and have to synchronize
753                                 -   If we do not find an OzoneProxy, we do not have to look deeper and to synchronized
754                             */
755                             checkForPossibleOzoneProxys:
756                             for (;;) {
757                                 for (int i = args.length-1;i>=0;i--) {
758                                     if (args[i] instanceof OzoneProxy) {
759                                         break checkForPossibleOzoneProxys;
760                                     }
761                                 }
762                                 return;
763                             }
764                         }
765 
766                         boolean possibleProxyBorderCross = false;
767 
768                         synchronized (garbageCollectionLevelsLock) {
769                             if (callee.getGarbageCollectionLevel()==doneReachableGarbageCollectionLevel) { // The callee belongs to the doneReachable set
770                                 if (caller.getGarbageCollectionLevel()!=doneReachableGarbageCollectionLevel) { // The caller does not belong to the doneReachable set
771                                     // The caller may transport object references to the doneReachable set where they are not checked. The referenced objects could falsely be identified as unreachable.
772                                     possibleProxyBorderCross = true;
773                                 }
774                             }
775                         }
776 
777                         if (possibleProxyBorderCross) {
778                             for (int i = args.length-1;i>=0;i--) {
779                                 checkForProxyBorderCross(args[i]);
780                             }
781                         }
782                     }
783                 }
784             } finally {
785                 callStack.push(callee);
786             }
787         }
788     }
789 
790     /**
791         This method is called by Transactions to indicate that a method of the object callee
792         was called by the transaction.
793 
794         This method will always be called, even if the GarbageCollector is not startet.
795     */
796     public void interceptInvocationPost(Transaction transaction,ObjectContainer callee,Object   result) {
797         /*
798             This looks dangerous but is effective.
799             The method isRunning() is called without the lock on this GarbageCollector.
800 
801             This is safe because this GarbageCollector only really starts to run after all transactions which
802             existed during the initiation have completed. All new transactions see the right value of
803             isRunning because there is a synchronization on creation of such a transaction.
804 
805             The other possibility is that old transactions see this too early. But in this case, all
806             what can happen is that the callStack is empty and therefore the caller is null.
807 
808             The speed gain is that method invocation may be not disturbed at all on HotSpot VMs, where
809             calls to this method may be fully optimized away as long as isRunning() is constant.
810         */
811         if (isRunning()) {
812             SimpleArrayList callStack   =   transaction.getCallStack();
813 
814             if (result!=null) {
815                 ObjectContainer caller      =   (ObjectContainer) callStack.peek();
816 
817                 if (caller!=null) {
818                     if (result instanceof OzoneCompatibleOrProxy) {
819                         // An indicator that this is a border cross proxy.
820 
821                         boolean possibleProxyBorderCross = false;
822 
823                         synchronized (garbageCollectionLevelsLock) {
824                             if (caller.getGarbageCollectionLevel()==doneReachableGarbageCollectionLevel) { // The caller belongs to the doneReachable set
825                                 if (callee.getGarbageCollectionLevel()!=doneReachableGarbageCollectionLevel) { // The callee does not belong to the doneReachable set
826                                     // The caller may receive object references to the doneReachable set where they are not checked. The referenced objects could falsely be identified as unreachable.
827                                     possibleProxyBorderCross = true;
828                                 }
829                             }
830                         }
831 
832                         if (possibleProxyBorderCross) {
833                             if (result instanceof OzoneCompatible) {
834                                 checkForProxyBorderCross((OzoneCompatible) result);
835                             } else { // Must be OzoneProxy
836                                 checkForProxyBorderCross((OzoneProxy) result);
837                             }
838                         }
839                     }
840                 }
841             }
842             callStack.pop();
843         }
844     }
845 
846     /**
847         This method checks wether the given object or the object graph reachable from this given object
848         contains OzoneProxys. If so, the database objects referenced by these proxies are considered
849         surelyReachable.
850     */
851     protected void checkForProxyBorderCross(Object   o) {
852         if (o instanceof OzoneProxy) {
853             checkForProxyBorderCross((OzoneProxy) o);
854         }
855     }
856 
857     /**
858         This method checks wether the given object or the object graph reachable from this given object
859         contains OzoneProxys. If so, the database objects referenced by these proxies are considered
860         surelyReachable.
861     */
862     protected void checkForProxyBorderCross(OzoneProxy o) {
863         ObjectID id = o.remoteID();
864 
865         addObjectIDToSurelyReachableObjectsWhichHaveToBeMarkedAsSuch(id);
866     }
867 
868     /**
869         This method checks wether the given object or the object graph reachable from this given object
870         contains OzoneProxys. If so, the database objects referenced by these proxies are considered
871         surelyReachable.
872     */
873     protected void checkForProxyBorderCross(OzoneCompatible o) {
874         // We should not process this object immediately because it is likely that this object itself is currently called.
875         ensureSurelyReachable(o.container().id());
876     }
877 
878     /**
879         ObjectOutputStream which servers as an intra ObjectContainer object-graph-walker to
880         detect all OzoneProxy instances an OzoneObject does refer.
881         Every detected OzoneProxy object is registered as to be marked as surely reachable.
882     */
883     public class GarbageCollectorProxyObjectIdentificationObjectOutputStream extends ObjectOutputStream   {
884         /*
885             Maybe one GarbageCollectorProxyObjectIdentificationObjectOutputStream per GarbageCollector
886             is sufficient, but there is state maintained in the ObjectOutputStream and
887             flushing state during time another thread is using the ObjectOutputStream as well
888             produces situationes which are unexpected by the developers of ObjectOutputStream.
889             So this is currently not considered.
890         */
891 
892         protected GarbageCollectorProxyObjectIdentificationObjectOutputStream() throws IOException   {
893             super(NullOutputStream.getDefault());
894         }
895 
896         public void notifyOzoneProxyEncountered(OzoneProxy encounteredProxy) {
897             addObjectIDToSurelyReachableObjectsWhichHaveToBeMarkedAsSuch(encounteredProxy.remoteID());
898         }
899 
900         protected void identifyProxys(ObjectContainer objectContainer) throws IOException   {
901             writeObject(objectContainer.target());
902         }
903     }
904 
905     /**
906         Sweeps all objects which are considered unreachable.
907     */
908     protected void sweepUnreachableObjects() {
909         env.getLogWriter().newEntry(this,"sweepUnreachableObjects(): starting to sweep...",env.getLogWriter().DEBUG3);
910 
911         DxIterator i = env.getStoreManager().objectIDIterator();
912 
913         while (i.next()!=null) {
914             if (kill) {
915                 break;
916             }
917 
918             ObjectID        id          = (ObjectID) i.key();
919             try {
920                 notifyAboutTransactionActionAndRenewTransactionIfRequired();
921 
922                 ObjectContainer container = transaction.acquireObject(id,Lock.LEVEL_READ);
923 
924                 try {
925                     synchronized (garbageCollectionLevelsLock) {
926 //                      env.getLogWriter().newEntry(this,"sweepUnreachableObjects(): processing "+id+": container.getGarbageCollectionLevel()="+container.getGarbageCollectionLevel()+", currentGarbageCollectionLevel="+currentGarbageCollectionLevel+".",env.getLogWriter().DEBUG3);
927 
928                         if (container.getGarbageCollectionLevel()-currentGarbageCollectionLevel<0) {
929                             env.getLogWriter().newEntry(this,"sweepUnreachableObjects(): deleting "+id,env.getLogWriter().DEBUG3);
930 
931                             transaction.deleteObject(id);
932                         }
933                     }
934                 } finally {
935                     transaction.releaseObject(container);
936                 }
937             } catch (ObjectNotFoundException e) {
938                 env.getLogWriter().newEntry(this,"caught while sweeping: ",e,env.getLogWriter().DEBUG3);
939             } catch (ClassNotFoundException   e) {
940                 env.getLogWriter().newEntry(this,"caught while sweeping: ",e,env.getLogWriter().DEBUG3);
941             } catch (IOException   e) {
942                 // It does not matter if the object is gone in the meantime. This is the best case for a garbage collector :-)
943                 env.getLogWriter().newEntry(this,"caught while sweeping: ",e,env.getLogWriter().DEBUG3);
944             } catch (TransactionException e) {
945                 // FIXME. What do we in this case?
946                 env.getLogWriter().newEntry(this,"caught while sweeping: ",e,env.getLogWriter().ERROR);
947             } catch (OzoneInternalException e) {
948                 env.getLogWriter().newEntry(this,"caught while sweeping: ",e,env.getLogWriter().ERROR);
949             } catch (OzoneRemoteException e) {
950                 env.getLogWriter().newEntry(this,"caught while sweeping: ",e,env.getLogWriter().ERROR);
951             }
952         }
953         try {
954             completeTransaction();
955         } catch (ClassNotFoundException   e) {
956             env.getLogWriter().newEntry(this,"caught: ",e,env.getLogWriter().ERROR);
957         } catch (IOException   e) {
958             env.getLogWriter().newEntry(this,"caught: ",e,env.getLogWriter().ERROR);
959         }
960     }
961 }
962
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags