0001: // You can redistribute this software and/or modify it under the terms of
0002: // the Ozone Core License version 1 published by ozone-db.org.
0003: //
0004: // The original code and portions created by SMB are
0005: // Copyright (C) 1997-@year@ by SMB GmbH. All rights reserved.
0006: //
0007: // $Id: GarbageCollector.java,v 1.3 2002/07/26 12:29:22 per_nyfelt Exp $
0008: package org.ozoneDB.core;
0009:
0010: import java.io.ObjectOutputStream;
0011: import java.io.IOException;
0012: import java.util.HashSet;
0013: import java.util.LinkedList;
0014:
0015: import org.ozoneDB.data.SimpleArrayList;
0016: import org.ozoneDB.io.stream.NullOutputStream;
0017:
0018: import org.ozoneDB.DxLib.DxIterator;
0019:
0020: import org.ozoneDB.core.DbRemote.CommandThread;
0021: import org.ozoneDB.OzoneProxy;
0022: import org.ozoneDB.OzoneCompatible;
0023: import org.ozoneDB.OzoneCompatibleOrProxy;
0024: import org.ozoneDB.ObjectNotFoundExc;
0025: import org.ozoneDB.TransactionExc;
0026: import org.ozoneDB.OzoneRemoteExc;
0027: import org.ozoneDB.OzoneInternalExc;
0028:
0029: /**
0030: Marks reachable objects and sweeps unreachable objects.
0031: <DIV>
0032: This implementation has at least following deficiencies:
0033: <UL>
0034: <LI>
0035: Method invocation observation is limited to the direct method parameters and the return value.
0036: A correct implementation should observe not only method parameters and return values but
0037: all objects which are reachable from these objects.
0038: </LI>
0039: <LI>
0040: Currently, the implementation is not scaleable, because the list
0041: {@link #surelyReachableObjectsWhichHaveToBeMarkedAsSuch} may grow to the count of objects.
0042: Possible solutions are:
0043: <UL>
0044: <LI>
0045: Export some contents of this stack to disk. This seems to be highly efficient, because
0046: the "hot spot" of the corresponding file always would be the end of the file.
0047: </LI>
0048: <LI>
0049: Simply forget entries if they are too much. Work through the whole list until it is empty.
0050: Once the list is empty, walk through all objects to refill this list and continue.
0051: This approach has some appeals, but seems to be element of O(n^2) for large databases because
0052: there would be n*c1 walks trough 1/2*n objects each walk.
0053: </LI>
0054: </UL>
0055: </LI>
0056: </UL>
0057: </DIV>
0058:
0059: @author Xuân Baldauf (<A HREF="http://www.medium.net/">Medium.net</A)>
0060: */
0061: public class GarbageCollector extends ServerComponent implements
0062: Runnable {
0063:
0064: /**
0065: Our database environment
0066: */
0067: // protected Env env;
0068: /**
0069: The thread which actually does the work.
0070: */
0071: protected Thread garbageCollectionThread;
0072:
0073: /**
0074: The list of {@link Transaction}s, which have to be completed before the GarbageCollector
0075: may start. It may not start earlier because the rollback of those transaction may make
0076: objects live which were believed to be dead.
0077: */
0078: protected HashSet transactionsRequiredToComplete;
0079:
0080: /**
0081: The number which represents the current garbage collection run.
0082: This number is the number mentioned in {@link org.ozoneDB.core.wizardStore.WizardObjectContainer#garbageCollectionLevel}.
0083: There are tree sets of database objects
0084: <UL>
0085: <LI>probablyReachable: These objects may or may not be reachable. Their garbageCollectionLevel is below the currentGarbageCollectionLevel</LI>
0086: <LI>surelyReachable: These objects have been reached during the walk. Their garbageCollectionLevel is currentGarbageCollectionLevel</LI>
0087: <LI>doneReachable: These object have been processed for members. All their members are surelyReachable or better. Their garbageCollectionLevel is currentGarbageCollectionLevel+1</LI>
0088: </UL>
0089: */
0090: protected int currentGarbageCollectionLevel;
0091:
0092: /**
0093: The garbageCollectionLevel which objects have if they belong to the doneReachable set.
0094: This is {@link #currentGarbageCollectionLevel}+1
0095: */
0096: protected int doneReachableGarbageCollectionLevel;
0097:
0098: /**
0099: The current phase this GarbageCollector is in. Access only within synchronization to this object.
0100: */
0101: protected int phase = PHASE_IDLE;
0102:
0103: /** Doing nothing */
0104: protected final static int PHASE_IDLE = 0;
0105:
0106: /** A run has been initiated */
0107: protected final static int PHASE_RUN_INITIATED = 1;
0108:
0109: /** Waiting for the old transactions to complete */
0110: protected final static int PHASE_WAITING_FOR_OLD_TRANSACTIONS_TO_COMPLETE = 2;
0111:
0112: /** We may start, all old transactions are complete */
0113: protected final static int PHASE_READY_TO_START = 3;
0114:
0115: /** We are started, we are marking all reachable objects */
0116: protected final static int PHASE_MARKING = 4;
0117:
0118: /** Waiting for the old transactions to complete */
0119: protected final static int PHASE_WAITING_FOR_NEW_TRANSACTIONS_TO_COMPLETE = 5;
0120:
0121: /** We are started, we are marking all reachable objects */
0122: protected final static int PHASE_MARKING2 = 6;
0123:
0124: /** We are started, we are sweeping all unreachable objects */
0125: protected final static int PHASE_SWEEPING = 7;
0126:
0127: /** Somebody requested to finish prematurely... */
0128: // protected final static int PHASE_KILL = -1;
0129: /**
0130: The current transaction of this garbageCollector.
0131: */
0132: protected Transaction transaction;
0133:
0134: /**
0135: The count of actions which were done within this garbageCollector.
0136: */
0137: protected int actionsWithinTransactionCount = 0;
0138:
0139: /**
0140: A stack of ObjectIDs of objects, which are surely reachable, but still
0141: were not marked as such.
0142: Access only during synchronization on it.
0143: */
0144: // protected DxListDeque surelyReachableObjectsWhichHaveToBeMarkedAsSuch;
0145: protected SimpleArrayList surelyReachableObjectsWhichHaveToBeMarkedAsSuch;
0146:
0147: /**
0148: The list of ObjectIDs of objects which are surelyReachable and already were tried to
0149: be processed but where locking the objects failed. The processing the contents of this
0150: list should be retried some times later.
0151:
0152: To minimize overhead, access is only allowed during synchronization to {@link #surelyReachableObjectsWhichHaveToBeMarkedAsSuch}
0153: */
0154: protected LinkedList surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContented;
0155:
0156: /**
0157: This is the lock that everybody has to be synchronized to in order to
0158: be able to access any garbageCollectionLevel in any object within this database.
0159: */
0160: protected Object garbageCollectionLevelsLock = new Object();
0161:
0162: /**
0163: Wether we should stop running as soon as possible. Synchronization is not required,
0164: because it does not matter wether we receive this signal soon or later.
0165: */
0166: protected boolean kill = false;
0167:
0168: /**
0169: Creates a new garbage collector.
0170: */
0171: protected GarbageCollector(Env env) {
0172: super (env);
0173: // this.env = env;
0174: setCurrentGarbageCollectionLevel(env.getState().intProperty(
0175: env.getState().GARBAGE_COLLECTION_LEVEL, 0));
0176: // surelyReachableObjectsWhichHaveToBeMarkedAsSuch = new DxListDeque;
0177: surelyReachableObjectsWhichHaveToBeMarkedAsSuch = new SimpleArrayList(
0178: 10000); // We expect at least 10000 entries in a busy database.
0179: surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContented = new LinkedList();
0180: transactionsRequiredToComplete = new HashSet();
0181: }
0182:
0183: protected void setCurrentGarbageCollectionLevel(int to) {
0184: synchronized (garbageCollectionLevelsLock) {
0185: this .currentGarbageCollectionLevel = to;
0186: this .doneReachableGarbageCollectionLevel = this .currentGarbageCollectionLevel + 1;
0187: }
0188: }
0189:
0190: public void startup() {
0191: env.getLogWriter().newEntry(this , "startup...",
0192: env.getLogWriter().DEBUG3);
0193: }
0194:
0195: public void shutdown() {
0196: kill = true;
0197: }
0198:
0199: public void save() {
0200: }
0201:
0202: /**
0203: Starts the garbage collection process.
0204: */
0205: public void start() {
0206: // env.getLogWriter().newEntry(this,"start()",env.getLogWriter().INFO);
0207: synchronized (this ) {
0208: if (phase == PHASE_IDLE) {
0209: if (garbageCollectionThread == null) {
0210: setPhase(PHASE_RUN_INITIATED);
0211: garbageCollectionThread = env.getInvokeServer()
0212: .newThread(this );
0213: garbageCollectionThread.start();
0214: } else {
0215: // We're already started
0216: }
0217: } else {
0218: // We're already started
0219: }
0220: }
0221: }
0222:
0223: public void addTransactionRequiredToComplete(Object ta) {
0224: transactionsRequiredToComplete.add(ta);
0225: }
0226:
0227: public void removeTransactionRequiredToComplete(Transaction ta) {
0228: if (!transactionsRequiredToComplete.isEmpty()) {
0229: transactionsRequiredToComplete.remove(ta);
0230: checkForEndOfWaitForCurrentTransactionsToCompletePhase();
0231: }
0232: }
0233:
0234: protected void checkForEndOfWaitForCurrentTransactionsToCompletePhase() {
0235: if (transactionsRequiredToComplete.isEmpty()) {
0236: notifyEndOfWaitForCurrentTransactionsToCompletePhase();
0237: }
0238: }
0239:
0240: /**
0241: Informs this GarbageCollector, the the pre-phase is done, there are no transactions that
0242: are older than this garbage collector run.
0243: */
0244: protected void notifyEndOfWaitForCurrentTransactionsToCompletePhase() {
0245: synchronized (this ) {
0246: /*
0247: if (phase==PHASE_WAITING_FOR_OLD_TRANSACTIONS_TO_COMPLETE) {
0248: phase = PHASE_READY_TO_START;
0249: }
0250: */
0251: setPhase(phase + 1);
0252: notify();
0253: }
0254: }
0255:
0256: protected void incCurrentGarbageCollectorLevel() {
0257: setCurrentGarbageCollectionLevel(currentGarbageCollectionLevel + 4);
0258: env.getState().setIntProperty(
0259: env.getState().GARBAGE_COLLECTION_LEVEL,
0260: currentGarbageCollectionLevel);
0261: setChanged();
0262: }
0263:
0264: /**
0265: The main method for garbage collection.
0266: */
0267: public void run() {
0268: env.getLogWriter().newEntry(this ,
0269: "garbage collection start...", env.getLogWriter().INFO);
0270: try {
0271: incCurrentGarbageCollectorLevel();
0272:
0273: setPhase(PHASE_WAITING_FOR_OLD_TRANSACTIONS_TO_COMPLETE);
0274:
0275: env
0276: .getTransactionManager()
0277: .startGarbageCollectionWaitForCurrentTransactionsToCompletePhase(
0278: this );
0279:
0280: waitForPhase(PHASE_READY_TO_START);
0281:
0282: renewTransactionIfRequired();
0283:
0284: addRootSetElementsToSurelyReachableSet();
0285:
0286: setPhase(PHASE_MARKING);
0287:
0288: processSurelyReachableObjectsWhichHaveToBeMarkedAsSuch();
0289:
0290: if (kill) {
0291: return;
0292: }
0293:
0294: setPhase(PHASE_WAITING_FOR_NEW_TRANSACTIONS_TO_COMPLETE);
0295:
0296: env
0297: .getTransactionManager()
0298: .startGarbageCollectionWaitForCurrentTransactionsToCompletePhase(
0299: this );
0300:
0301: waitForPhase(PHASE_MARKING2);
0302:
0303: processSurelyReachableObjectsWhichHaveToBeMarkedAsSuch();
0304:
0305: if (kill) {
0306: return;
0307: }
0308:
0309: setPhase(PHASE_SWEEPING);
0310:
0311: sweepUnreachableObjects();
0312:
0313: } catch (Throwable e) {
0314: env.getLogWriter().newEntry(this , "GC caught: ", e,
0315: env.getLogWriter().ERROR);
0316: } finally {
0317: env.getLogWriter().newEntry(this ,
0318: "garbage collection end...",
0319: env.getLogWriter().INFO);
0320: garbageCollectionThread = null;
0321: setPhase(PHASE_IDLE);
0322: try {
0323: if (transaction != null) { // We are crashing with an open transaction, let's abort it..
0324: internalAbortTransaction(transaction);
0325: // internalFinishTransaction(transaction);
0326: env.getTransactionManager().deleteTransaction();
0327: transaction = null;
0328: }
0329: } catch (ClassNotFoundException e) {
0330: env.getLogWriter().newEntry(this , "caught: ", e,
0331: env.getLogWriter().ERROR);
0332: } catch (IOException e) {
0333: env.getLogWriter().newEntry(this , "caught: ", e,
0334: env.getLogWriter().ERROR);
0335: }
0336: }
0337: }
0338:
0339: protected void notifyAboutTransactionActionAndRenewTransactionIfRequired()
0340: throws IOException, ClassNotFoundException, TransactionExc {
0341: renewTransactionIfRequired();
0342: actionsWithinTransactionCount++;
0343: }
0344:
0345: /**
0346: Checks wether the current transaction has to be committed (because it accumulated too much changes)
0347: and if so, commits it and closes it. Afterwards (or if there has not been a current transaction already),
0348: it creates a new current transaction.
0349: */
0350: protected void renewTransactionIfRequired() throws IOException,
0351: ClassNotFoundException, TransactionExc {
0352: if (actionsWithinTransactionCount >= 100) { // We renew if we had 100 or more actions within this transaction.
0353: completeTransaction();
0354:
0355: env
0356: .getLogWriter()
0357: .newEntry(
0358: this ,
0359: "toBeProcessedCount="
0360: + surelyReachableObjectsWhichHaveToBeMarkedAsSuch
0361: .size() + ".",
0362: env.getLogWriter().DEBUG1);
0363:
0364: }
0365:
0366: if (transaction == null) {
0367: transaction = env.getTransactionManager().newTransaction(
0368: env.getUserManager().getGarbageCollectorUser());
0369: }
0370: }
0371:
0372: /**
0373: Completes the current transaction and releases it.
0374: */
0375: protected void completeTransaction() throws IOException,
0376: ClassNotFoundException {
0377: if (transaction != null) {
0378: internalCompleteTransaction(transaction);
0379: actionsWithinTransactionCount = 0;
0380: env.getTransactionManager().deleteTransaction();
0381: transaction = null;
0382: }
0383: }
0384:
0385: protected void internalCompleteTransaction(Transaction transaction)
0386: throws IOException, ClassNotFoundException {
0387: boolean allright = false;
0388: try {
0389: transaction.prepareCommit();
0390: allright = true;
0391: } finally {
0392: if (!allright) {
0393: internalAbortTransaction(transaction);
0394: }
0395: }
0396:
0397: internalFinishTransaction(transaction);
0398: }
0399:
0400: protected void internalFinishTransaction(Transaction transaction)
0401: throws IOException, ClassNotFoundException {
0402: TransactionManager transactionManager = transaction
0403: .getManager();
0404:
0405: try {
0406: transactionManager.beginExclusion();
0407: transaction.commit();
0408: } finally {
0409: transactionManager.endExclusion();
0410: transactionManager.notifyWaitingTransactions();
0411: }
0412: }
0413:
0414: protected void internalAbortTransaction(Transaction transaction)
0415: throws IOException, ClassNotFoundException {
0416: TransactionManager transactionManager = transaction
0417: .getManager();
0418: try {
0419: transactionManager.beginExclusion();
0420: transaction.abort(null);
0421: } finally {
0422: transactionManager.endExclusion();
0423: transactionManager.notifyWaitingTransactions();
0424: }
0425: }
0426:
0427: protected synchronized void setPhase(int to) {
0428: phase = to;
0429: env.getLogWriter().newEntry(this , "setPhase(" + to + ")",
0430: env.getLogWriter().DEBUG2);
0431: }
0432:
0433: protected synchronized void waitForPhase(int newPhase)
0434: throws InterruptedException {
0435: while (phase != newPhase) {
0436: wait();
0437: }
0438: }
0439:
0440: protected void addRootSetElementsToSurelyReachableSet() {
0441: startFilterDatabaseObjectReferencesAtExternalDatabaseGates();
0442: addAllNamedObjectsToSurelyReachableSet();
0443: }
0444:
0445: protected void startFilterDatabaseObjectReferencesAtExternalDatabaseGates() {
0446: env.getInvokeServer()
0447: .startFilterDatabaseObjectReferencesExports(this );
0448: env.getLocalClientTracker()
0449: .startFilterDatabaseObjectReferencesExports(this );
0450: }
0451:
0452: public void notifyDatabaseObjectIsExported(ObjectID id) {
0453: notifyDatabaseObjectIsAboutToBeExported(id);
0454: }
0455:
0456: /**
0457: This method is called by DbInvokeClient to notify this garbageCollector
0458: that there is a reference which is to be exported to a client.
0459: */
0460: public void notifyDatabaseObjectIsAboutToBeExported(ObjectID id) {
0461: // These object referenced belong, because they are used, to the surelyReachable set.
0462: ensureSurelyReachable(id);
0463: }
0464:
0465: /**
0466: This method walks through all named objects and adds each of them to the surelyReachable set.
0467: */
0468: protected void addAllNamedObjectsToSurelyReachableSet() {
0469: env.getStoreManager().reportNamedObjectsToGarbageCollector();
0470: }
0471:
0472: /**
0473: This method is called by StoreManager to indicate that the object
0474: with the given id is a named object.
0475: */
0476: public void notifyNamedObject(ObjectID id) {
0477: ensureSurelyReachable(id);
0478: }
0479:
0480: /**
0481: This method is called by StoreManager in the event an unnamed object receives a name.
0482: This is the case if an object which was formerly unnamed gets a name.
0483: */
0484: public void notifyNewObjectName(ObjectContainer objectContainer) {
0485: ensureSurelyReachable(objectContainer);
0486: }
0487:
0488: /**
0489: This method is called by StoreManager in the event an object is freshly created.
0490: */
0491: public void notifyNewObjectContainer(
0492: /*Transaction transaction,*/ObjectContainer objectContainer) {
0493: ensureDoneReachable(/*transaction,*/objectContainer);
0494: }
0495:
0496: /**
0497: Calling this method makes sure that the object which is referenced by the given ID is
0498: at least surely reachable.
0499: */
0500: protected void ensureSurelyReachable(ObjectID id) {
0501: synchronized (this ) {
0502: if (isRunning()) {
0503: addObjectIDToSurelyReachableObjectsWhichHaveToBeMarkedAsSuch(id);
0504: }
0505: }
0506: }
0507:
0508: /**
0509: This method may be called both from transaction threads and from GarbageCollector-Threads.
0510: */
0511: protected void addObjectIDToSurelyReachableObjectsWhichHaveToBeMarkedAsSuch(
0512: ObjectID id) {
0513: synchronized (surelyReachableObjectsWhichHaveToBeMarkedAsSuch) {
0514: // env.getLogWriter().newEntry(this,"addObjectID(): adding "+id+".",new Exception(),env.getLogWriter().DEBUG3);
0515: surelyReachableObjectsWhichHaveToBeMarkedAsSuch.push(id);
0516: }
0517: }
0518:
0519: /**
0520: Calling this method makes sure that the object which is referenced by the given ID is
0521: at least surely reachable. This method is called by non-GarbageCollector-Threads.
0522: */
0523: protected void ensureSurelyReachable(ObjectContainer objectContainer) {
0524: // This is not possible because processing has to be done within a GarbageCollector transaction and not within any other transaction.
0525: /*
0526: objectContainer.pin();
0527: processObjectContainerWhichWantsToBeSurelyReachableAndUnpin(objectContainer);
0528: */
0529: addObjectIDToSurelyReachableObjectsWhichHaveToBeMarkedAsSuch(objectContainer
0530: .id());
0531: }
0532:
0533: /**
0534: Returns wether this GarbageCollector is running. This method
0535: must be called during synchronization on this GarbageCollector.
0536: */
0537: protected boolean isRunning() {
0538: return phase != PHASE_IDLE;
0539: }
0540:
0541: /**
0542: This is the "main()" method of the mark phase.
0543: */
0544: protected void processSurelyReachableObjectsWhichHaveToBeMarkedAsSuch() {
0545: ObjectID id;
0546:
0547: int surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContentedSize = -1;
0548:
0549: retryLoop: for (;;) {
0550: for (;;) {
0551: if (kill) {
0552: break retryLoop;
0553: }
0554: synchronized (surelyReachableObjectsWhichHaveToBeMarkedAsSuch) {
0555: id = (ObjectID) surelyReachableObjectsWhichHaveToBeMarkedAsSuch
0556: .pop();
0557: }
0558:
0559: if (id == null) {
0560: break;
0561: }
0562:
0563: try {
0564: /*
0565: ObjectContainer container = env.getStoreManager().containerForIDAndPin(null,id);
0566:
0567: processObjectContainerWhichWantsToBeSurelyReachableAndUnpin(container);
0568: */
0569:
0570: // We should acquire the container via our transaction
0571: notifyAboutTransactionActionAndRenewTransactionIfRequired();
0572:
0573: // env.getLogWriter().newEntry(this,"process(): processing "+id+".",env.getLogWriter().DEBUG3);
0574:
0575: ObjectContainer container = transaction
0576: .acquireObjectAndPin(id, Lock.LEVEL_READ);
0577:
0578: processObjectContainerWhichWantsToBeSurelyReachableAndUnpin(
0579: transaction, container);
0580: // } catch (ObjNotFoundException e) {
0581: } catch (ObjectNotFoundExc e) {
0582: } catch (ClassNotFoundException e) {
0583: } catch (IOException e) {
0584: // It does not matter if the object is gone in the meantime. This is the best case for a garbage collector :-)
0585: } catch (TransactionExc e) {
0586: env.getLogWriter().newEntry(this , "caught: ", e,
0587: env.getLogWriter().ERROR);
0588: // FIXME. What do we in this case?
0589: }
0590: }
0591:
0592: boolean waitRecommended;
0593:
0594: synchronized (surelyReachableObjectsWhichHaveToBeMarkedAsSuch) {
0595: waitRecommended = surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContentedSize == surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContented
0596: .size();
0597:
0598: surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContentedSize = surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContented
0599: .size();
0600:
0601: while (!surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContented
0602: .isEmpty()) {
0603: surelyReachableObjectsWhichHaveToBeMarkedAsSuch
0604: .push(surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContented
0605: .getFirst());
0606: }
0607: }
0608:
0609: if (surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContentedSize > 0) {
0610: if (waitRecommended) {
0611: try {
0612: try {
0613: completeTransaction(); // We should finish our transaction so that other transactions may complete.
0614: } catch (ClassNotFoundException e) {
0615: env.getLogWriter().newEntry(this ,
0616: "caught: ", e,
0617: env.getLogWriter().ERROR);
0618: } catch (IOException e) {
0619: env.getLogWriter().newEntry(this ,
0620: "caught: ", e,
0621: env.getLogWriter().ERROR);
0622: }
0623:
0624: // We're waiting less if there are more lock-contented objects, but at least 100ms
0625: Thread
0626: .sleep(100 + 2000 / (surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContentedSize));
0627: } catch (InterruptedException e) {
0628: }
0629: }
0630: } else {
0631: break;
0632: }
0633: }
0634:
0635: try {
0636: completeTransaction();
0637: } catch (ClassNotFoundException e) {
0638: env.getLogWriter().newEntry(this , "caught: ", e,
0639: env.getLogWriter().ERROR);
0640: } catch (IOException e) {
0641: env.getLogWriter().newEntry(this , "caught: ", e,
0642: env.getLogWriter().ERROR);
0643: }
0644: // Pheew. We're done. Now sweep the unreachable objects.
0645: }
0646:
0647: /**
0648: Internally ensures that the given object is at least surelyReachable.
0649:
0650: @return
0651: <0 if this object has been updated. If this is the case, this object has to join a transaction which will complete successfully.
0652: =0 if this object has not been updated, it is surelyReachable
0653: >0 if this object has not been updated, it is processedReachable
0654: */
0655: protected int internalEnsureSurelyReachable(
0656: ObjectContainer objectContainer) {
0657: synchronized (garbageCollectionLevelsLock) {
0658: return objectContainer
0659: .ensureGarbageCollectionLevel(currentGarbageCollectionLevel);
0660: }
0661: }
0662:
0663: /**
0664: Ensures that the given object is doneReachable.
0665: */
0666: protected void ensureDoneReachable(
0667: /*Transaction transaction,*/ObjectContainer objectContainer) {
0668: internalEnsureDoneReachable(objectContainer);
0669: }
0670:
0671: /**
0672: Internally ensures that the given object is doneReachable.
0673: */
0674: protected void internalEnsureDoneReachable(
0675: ObjectContainer objectContainer) {
0676: synchronized (garbageCollectionLevelsLock) {
0677: objectContainer
0678: .ensureGarbageCollectionLevel(doneReachableGarbageCollectionLevel);
0679: }
0680: }
0681:
0682: /**
0683: Processes an ObjectContainer which possibly has not already been registered as surely reachable.
0684:
0685: // This method may be called by any CommandThread.
0686: This method may be called only by the garbage collector thread.
0687: */
0688: protected void processObjectContainerWhichWantsToBeSurelyReachableAndUnpin(
0689: Transaction transaction, ObjectContainer objectContainer) {
0690: try {
0691: int difference = internalEnsureSurelyReachable(objectContainer);
0692:
0693: // env.getLogWriter().newEntry(this,"processObjectContainerWhichWantsToBeSurelyReachableAndUnpin("+objectContainer+"), difference="+difference+".",env.getLogWriter().DEBUG3);
0694:
0695: if (difference <= 0) {
0696: processReferencesByThisObject(transaction,
0697: objectContainer);
0698: }
0699: } finally {
0700: objectContainer.unpin();
0701: }
0702: }
0703:
0704: /**
0705: Determines all references which are "contained" within the given object,
0706: adds them to the list of {@link #surelyReachableObjectsWhichHaveToBeMarkedAsSuch}
0707: and then marks the given object as doneReachable.
0708:
0709: This method may be called by any CommandThread.
0710: */
0711: protected void processReferencesByThisObject(
0712: Transaction transaction, ObjectContainer objectContainer) {
0713: /*
0714: CommandThread thread = (CommandThread) Thread.currentThread();
0715: Transaction transaction = thread.transaction();
0716: */
0717:
0718: /*
0719: We really only need READ locks, because only read and do not write the object.
0720: But with READ locks, there may be transactions which have invoked a method on
0721: this object. We do not want to read the object in this state, because there
0722: may be references temporarily taken out of the object but onto the stack
0723: which we would miss.
0724:
0725: That is why we must ensure that nobody has invoked the object currently.
0726: This should be - in theory - be possible by checking WizardObjectContainer.invokeCount,
0727: but this is not an option in practice because accessing invokeCount is not
0728: synchronized. This may lead to the situation that this thread does not see
0729: an invokeCount!=1 while the other thread which invoked the object already has
0730: set invokeCount to !=1.
0731:
0732: Additionally, checking invokeCount would not suffice because a transaction thread
0733: may invoke the object during our proxy identification.
0734:
0735: That is why we must use an exclusive lock, which is a write lock.
0736: */
0737: // int previousLockLevel = objectContainer.lock().tryAcquire(transaction,Lock.LEVEL_READ);
0738: int previousLockLevel = objectContainer.lock().tryAcquire(
0739: transaction, Lock.LEVEL_WRITE);
0740:
0741: if (previousLockLevel != Lock.NOT_ACQUIRED) {
0742: try {
0743: env.getStoreManager().updateLockLevel(transaction,
0744: objectContainer);
0745: GarbageCollectorProxyObjectIdentificationObjectOutputStream identificator = new GarbageCollectorProxyObjectIdentificationObjectOutputStream();
0746:
0747: identificator.identifyProxys(objectContainer);
0748:
0749: internalEnsureDoneReachable(objectContainer);
0750: } catch (IOException e) {
0751: // only supported from JDK1.4 on
0752: // throw new RuntimeException("Caught during serialization for proxy object identification: ",e);
0753: throw new RuntimeException(
0754: "Caught during serialization for proxy object identification: "
0755: + e);
0756: } finally {
0757: // The lock is released on transaction commit.
0758: // objectContainer.lock().release(transaction);
0759: }
0760: } else {
0761: deferProcessingOfObjectContainerDueToLockContention(objectContainer);
0762: }
0763: }
0764:
0765: /**
0766: Defers the processing of the given objectContainer because locking was not possible at current time.
0767: Because objectContainers may be modified in the meantime
0768: (in the case they are unloaded and loaded again, we would hold an old copy of objectContainer which
0769: does not reflect the changes made to the new objectContainer), it's not wise to queue the ObjectContainer.
0770: Instead, we have to queue the ObjectID of that ObjectContainer.
0771: */
0772: protected void deferProcessingOfObjectContainerDueToLockContention(
0773: ObjectContainer objectContainer) {
0774: synchronized (surelyReachableObjectsWhichHaveToBeMarkedAsSuch) {
0775: surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContented
0776: .add(objectContainer.id());
0777: }
0778: }
0779:
0780: /**
0781: This method is called by Transactions to indicate that a method of the object callee
0782: will be called by the transaction.
0783:
0784: This method will always be called, even if the GarbageCollector is not startet.
0785: */
0786: public void interceptInvocationPre(Transaction transaction,
0787: ObjectContainer callee, Object[] args) {
0788:
0789: /*
0790: This looks dangerous but is effective.
0791: The method isRunning() is called without the lock on this GarbageCollector.
0792:
0793: This is safe because this GarbageCollector only really starts to run after all transactions which
0794: existed during the initiation have completed. All new transactions see the right value of
0795: isRunning because there is a synchronization on creation of such a transaction.
0796:
0797: The other possibility is that old transactions see this too early. But in this case, all
0798: what can happen is that the callStack is empty and therefore the caller is null.
0799:
0800: The speed gain is that method invocation may be not disturbed at all on HotSpot VMs, where
0801: calls to this method may be fully optimized away as long as isRunning() is constant.
0802: */
0803: if (isRunning()) {
0804: SimpleArrayList callStack = transaction.getCallStack();
0805:
0806: try {
0807: if (args != null) {
0808: ObjectContainer caller = (ObjectContainer) callStack
0809: .peek();
0810:
0811: if (caller != null) {
0812:
0813: /*
0814: There is a design decision which heavily affects performance:
0815: - Do we first check for the possibility of an OzoneProxy as parameter or
0816: - Do we first check for the cross of the border of the different sets of database objects?
0817:
0818: If we use true here, the first option is used.
0819: If we use false here, the first option is used.
0820: */
0821: if (false) {
0822: /*
0823: This spaghetti code is for speed.
0824: - If we find an OzoneProxy, we have to look deeper and have to synchronize
0825: - If we do not find an OzoneProxy, we do not have to look deeper and to synchronized
0826: */
0827: checkForPossibleOzoneProxys: for (;;) {
0828: for (int i = args.length - 1; i >= 0; i--) {
0829: if (args[i] instanceof OzoneProxy) {
0830: break checkForPossibleOzoneProxys;
0831: }
0832: }
0833: return;
0834: }
0835: }
0836:
0837: boolean possibleProxyBorderCross = false;
0838:
0839: synchronized (garbageCollectionLevelsLock) {
0840: if (callee.getGarbageCollectionLevel() == doneReachableGarbageCollectionLevel) { // The callee belongs to the doneReachable set
0841: if (caller.getGarbageCollectionLevel() != doneReachableGarbageCollectionLevel) { // The caller does not belong to the doneReachable set
0842: // The caller may transport object references to the doneReachable set where they are not checked. The referenced objects could falsely be identified as unreachable.
0843: possibleProxyBorderCross = true;
0844: }
0845: }
0846: }
0847:
0848: if (possibleProxyBorderCross) {
0849: for (int i = args.length - 1; i >= 0; i--) {
0850: checkForProxyBorderCross(args[i]);
0851: }
0852: }
0853: }
0854: }
0855: } finally {
0856: callStack.push(callee);
0857: }
0858: }
0859: }
0860:
0861: /**
0862: This method is called by Transactions to indicate that a method of the object callee
0863: was called by the transaction.
0864:
0865: This method will always be called, even if the GarbageCollector is not startet.
0866: */
0867: public void interceptInvocationPost(Transaction transaction,
0868: ObjectContainer callee, Object result) {
0869: /*
0870: This looks dangerous but is effective.
0871: The method isRunning() is called without the lock on this GarbageCollector.
0872:
0873: This is safe because this GarbageCollector only really starts to run after all transactions which
0874: existed during the initiation have completed. All new transactions see the right value of
0875: isRunning because there is a synchronization on creation of such a transaction.
0876:
0877: The other possibility is that old transactions see this too early. But in this case, all
0878: what can happen is that the callStack is empty and therefore the caller is null.
0879:
0880: The speed gain is that method invocation may be not disturbed at all on HotSpot VMs, where
0881: calls to this method may be fully optimized away as long as isRunning() is constant.
0882: */
0883: if (isRunning()) {
0884: SimpleArrayList callStack = transaction.getCallStack();
0885:
0886: if (result != null) {
0887: ObjectContainer caller = (ObjectContainer) callStack
0888: .peek();
0889:
0890: if (caller != null) {
0891: if (result instanceof OzoneCompatibleOrProxy) {
0892: // An indicator that this is a border cross proxy.
0893:
0894: boolean possibleProxyBorderCross = false;
0895:
0896: synchronized (garbageCollectionLevelsLock) {
0897: if (caller.getGarbageCollectionLevel() == doneReachableGarbageCollectionLevel) { // The caller belongs to the doneReachable set
0898: if (callee.getGarbageCollectionLevel() != doneReachableGarbageCollectionLevel) { // The callee does not belong to the doneReachable set
0899: // The caller may receive object references to the doneReachable set where they are not checked. The referenced objects could falsely be identified as unreachable.
0900: possibleProxyBorderCross = true;
0901: }
0902: }
0903: }
0904:
0905: if (possibleProxyBorderCross) {
0906: if (result instanceof OzoneCompatible) {
0907: checkForProxyBorderCross((OzoneCompatible) result);
0908: } else { // Must be OzoneProxy
0909: checkForProxyBorderCross((OzoneProxy) result);
0910: }
0911: }
0912: }
0913: }
0914: }
0915: callStack.pop();
0916: }
0917: }
0918:
0919: /**
0920: This method checks wether the given object or the object graph reachable from this given object
0921: contains OzoneProxys. If so, the database objects referenced by these proxies are considered
0922: surelyReachable.
0923: */
0924: protected void checkForProxyBorderCross(Object o) {
0925: if (o instanceof OzoneProxy) {
0926: checkForProxyBorderCross((OzoneProxy) o);
0927: }
0928: }
0929:
0930: /**
0931: This method checks wether the given object or the object graph reachable from this given object
0932: contains OzoneProxys. If so, the database objects referenced by these proxies are considered
0933: surelyReachable.
0934: */
0935: protected void checkForProxyBorderCross(OzoneProxy o) {
0936: ObjectID id = o.remoteID();
0937:
0938: addObjectIDToSurelyReachableObjectsWhichHaveToBeMarkedAsSuch(id);
0939: }
0940:
0941: /**
0942: This method checks wether the given object or the object graph reachable from this given object
0943: contains OzoneProxys. If so, the database objects referenced by these proxies are considered
0944: surelyReachable.
0945: */
0946: protected void checkForProxyBorderCross(OzoneCompatible o) {
0947: // We should not process this object immediately because it is likely that this object itself is currently called.
0948: ensureSurelyReachable(o.container().id());
0949: }
0950:
0951: /**
0952: ObjectOutputStream which servers as an intra ObjectContainer object-graph-walker to
0953: detect all OzoneProxy instances an OzoneObject does refer.
0954: Every detected OzoneProxy object is registered as to be marked as surely reachable.
0955: */
0956: public class GarbageCollectorProxyObjectIdentificationObjectOutputStream
0957: extends ObjectOutputStream {
0958: /*
0959: Maybe one GarbageCollectorProxyObjectIdentificationObjectOutputStream per GarbageCollector
0960: is sufficient, but there is state maintained in the ObjectOutputStream and
0961: flushing state during time another thread is using the ObjectOutputStream as well
0962: produces situationes which are unexpected by the developers of ObjectOutputStream.
0963: So this is currently not considered.
0964: */
0965:
0966: protected GarbageCollectorProxyObjectIdentificationObjectOutputStream()
0967: throws IOException {
0968: super (NullOutputStream.getDefault());
0969: }
0970:
0971: public void notifyOzoneProxyEncountered(
0972: OzoneProxy encounteredProxy) {
0973: addObjectIDToSurelyReachableObjectsWhichHaveToBeMarkedAsSuch(encounteredProxy
0974: .remoteID());
0975: }
0976:
0977: protected void identifyProxys(ObjectContainer objectContainer)
0978: throws IOException {
0979: writeObject(objectContainer.target());
0980: }
0981: }
0982:
0983: /**
0984: Sweeps all objects which are considered unreachable.
0985: */
0986: protected void sweepUnreachableObjects() {
0987: env.getLogWriter().newEntry(this ,
0988: "sweepUnreachableObjects(): starting to sweep...",
0989: env.getLogWriter().DEBUG3);
0990:
0991: DxIterator i = env.getStoreManager().objectIDIterator();
0992: while (i.next() != null) {
0993: if (kill) {
0994: break;
0995: }
0996:
0997: ObjectID id = (ObjectID) i.key();
0998: try {
0999: notifyAboutTransactionActionAndRenewTransactionIfRequired();
1000: ObjectContainer container = transaction
1001: .acquireObjectAndPin(id, Lock.LEVEL_READ);
1002:
1003: try {
1004: synchronized (garbageCollectionLevelsLock) {
1005: // env.getLogWriter().newEntry(this,"sweepUnreachableObjects(): processing "+id+": container.getGarbageCollectionLevel()="+container.getGarbageCollectionLevel()+", currentGarbageCollectionLevel="+currentGarbageCollectionLevel+".",env.getLogWriter().DEBUG3);
1006:
1007: if (container.getGarbageCollectionLevel()
1008: - currentGarbageCollectionLevel < 0) {
1009: env.getLogWriter().newEntry(
1010: this ,
1011: "sweepUnreachableObjects(): deleting "
1012: + id,
1013: env.getLogWriter().DEBUG3);
1014:
1015: transaction.deleteObject(id);
1016: }
1017: }
1018: } finally {
1019: transaction.releaseObjectAndUnpin(container);
1020: }
1021: } catch (ObjectNotFoundExc e) {
1022: env.getLogWriter().newEntry(this ,
1023: "caught while sweeping: ", e,
1024: env.getLogWriter().DEBUG3);
1025: } catch (ClassNotFoundException e) {
1026: env.getLogWriter().newEntry(this ,
1027: "caught while sweeping: ", e,
1028: env.getLogWriter().DEBUG3);
1029: } catch (IOException e) {
1030: // It does not matter if the object is gone in the meantime. This is the best case for a garbage collector :-)
1031: env.getLogWriter().newEntry(this ,
1032: "caught while sweeping: ", e,
1033: env.getLogWriter().DEBUG3);
1034: } catch (TransactionExc e) {
1035: // FIXME. What do we in this case?
1036: env.getLogWriter().newEntry(this ,
1037: "caught while sweeping: ", e,
1038: env.getLogWriter().ERROR);
1039: } catch (OzoneInternalExc e) {
1040: env.getLogWriter().newEntry(this ,
1041: "caught while sweeping: ", e,
1042: env.getLogWriter().ERROR);
1043: } catch (OzoneRemoteExc e) {
1044: env.getLogWriter().newEntry(this ,
1045: "caught while sweeping: ", e,
1046: env.getLogWriter().ERROR);
1047: }
1048: }
1049: try {
1050: completeTransaction();
1051: } catch (ClassNotFoundException e) {
1052: env.getLogWriter().newEntry(this , "caught: ", e,
1053: env.getLogWriter().ERROR);
1054: } catch (IOException e) {
1055: env.getLogWriter().newEntry(this , "caught: ", e,
1056: env.getLogWriter().ERROR);
1057: }
1058: }
1059: }
|