garbagecollector.java

Java的面向对象数据库系统的源代码

// You can redistribute this software and/or modify it under the terms of
// the Ozone Core License version 1 published by ozone-db.org.
//
// The original code and portions created by SMB are
// Copyright (C) 1997-@year@ by SMB GmbH. All rights reserved.
//
// $Id: GarbageCollector.java,v 1.7 2002/12/29 11:15:56 per_nyfelt Exp $
package org.ozoneDB.core;

import org.ozoneDB.DxLib.DxIterator;
import org.ozoneDB.*;
import org.ozoneDB.util.LogWriter;
import org.ozoneDB.data.SimpleArrayList;
import org.ozoneDB.io.stream.NullOutputStream;

import java.io.IOException;
import java.io.ObjectOutputStream;
import java.util.HashSet;
import java.util.LinkedList;

/**
    Marks reachable objects and sweeps unreachable objects.
    <DIV>
        This implementation has at least following deficiencies:
        <UL>
            <LI>
                Method invocation observation is limited to the direct method parameters and the return value.
                A correct implementation should observe not only method parameters and return values but
                all objects which are reachable from these objects.
            </LI>
            <LI>
                Currently, the implementation is not scaleable, because the list
                {@link #surelyReachableObjectsWhichHaveToBeMarkedAsSuch} may grow to the count of objects.
                Possible solutions are:
                <UL>
                    <LI>
                        Export some contents of this stack to disk. This seems to be highly efficient, because
                        the "hot spot" of the corresponding file always would be the end of the file.
                    </LI>
                    <LI>
                        Simply forget entries if they are too much. Work through the whole list until it is empty.
                        Once the list is empty, walk through all objects to refill this list and continue.
                        This approach has some appeals, but seems to be element of O(n^2) for large databases because
                        there would be n*c1 walks trough 1/2*n objects each walk.
                    </LI>
                </UL>
            </LI>
        </UL>
    </DIV>

    @author Xu?n Baldauf (<A HREF="http://www.medium.net/">Medium.net</A)>
*/
public class GarbageCollector extends ServerComponent implements Runnable {

    /**
        Our database environment
    */
//  protected   Env     env;

   /**
        The thread which actually does the work.
    */
    protected   Thread  garbageCollectionThread;

    /**
        The list of  {@link Transaction}s, which have to be completed before the GarbageCollector
        may start. It may not start earlier because the rollback of those transaction may make
        objects live which were believed to be dead.
    */
    protected   HashSet transactionsRequiredToComplete;

    /**
        The number which represents the current garbage collection run.
        This number is the number mentioned in {@link org.ozoneDB.core.storage.wizardStore.WizardObjectContainer#garbageCollectionLevel}.
        There are tree sets of database objects
        <UL>
            <LI>probablyReachable: These objects may or may not be reachable. Their garbageCollectionLevel is below the currentGarbageCollectionLevel</LI>
            <LI>surelyReachable: These objects have been reached during the walk. Their garbageCollectionLevel is currentGarbageCollectionLevel</LI>
            <LI>doneReachable: These object have been processed for members. All their members are surelyReachable or better. Their garbageCollectionLevel is currentGarbageCollectionLevel+1</LI>
        </UL>
    */
    protected   int     currentGarbageCollectionLevel;

    /**
        The garbageCollectionLevel which objects have if they belong to the doneReachable set.
        This is {@link #currentGarbageCollectionLevel}+1
    */
    protected   int     doneReachableGarbageCollectionLevel;

    /**
        The current phase this GarbageCollector is in. Access only within synchronization to this object.
    */
    protected   int     phase   =   PHASE_IDLE;

    /** Doing nothing */
    protected final static int  PHASE_IDLE                                      =   0;

    /** A run has been initiated */
    protected final static int  PHASE_RUN_INITIATED                             =   1;

    /** Waiting for the old transactions to complete */
    protected final static int  PHASE_WAITING_FOR_OLD_TRANSACTIONS_TO_COMPLETE  =   2;

    /** We may start, all old transactions are complete */
    protected final static int  PHASE_READY_TO_START                            =   3;

    /** We are started, we are marking all reachable objects */
    protected final static int  PHASE_MARKING                                   =   4;

    /** Waiting for the old transactions to complete */
    protected final static int  PHASE_WAITING_FOR_NEW_TRANSACTIONS_TO_COMPLETE  =   5;

    /** We are started, we are marking all reachable objects */
    protected final static int  PHASE_MARKING2                                  =   6;

    /** We are started, we are sweeping all unreachable objects */
    protected final static int  PHASE_SWEEPING                                  =   7;

    /** Somebody requested to finish prematurely... */
//  protected final static int  PHASE_KILL                                      =   -1;

    /**
        The current transaction of this garbageCollector.
    */
    protected   Transaction     transaction;

    /**
        The count of actions which were done within this garbageCollector.
    */
    protected   int             actionsWithinTransactionCount   =   0;

    /**
        A stack of ObjectIDs of objects, which are surely reachable, but still
        were not marked as such.
        Access only during synchronization on it.
    */
//  protected   DxListDeque     surelyReachableObjectsWhichHaveToBeMarkedAsSuch;
    protected   SimpleArrayList surelyReachableObjectsWhichHaveToBeMarkedAsSuch;

    /**
        The list of ObjectIDs of objects which are surelyReachable and already were tried to
        be processed but where locking the objects failed. The processing the contents of this
        list should be retried some times later.

        To minimize overhead, access is only allowed during synchronization to {@link #surelyReachableObjectsWhichHaveToBeMarkedAsSuch}
    */
    protected   LinkedList      surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContented;

    /**
        This is the lock that everybody has to be synchronized to in order to
        be able to access any garbageCollectionLevel in any object within this database.
    */
    protected   Object          garbageCollectionLevelsLock =   new Object();

    /**
        Wether we should stop running as soon as possible. Synchronization is not required,
        because it does not matter wether we receive this signal soon or later.
    */
    protected   boolean         kill                        =   false;

    /**
        Creates a new garbage collector.
    */
    protected GarbageCollector(Env env) {
        super(env);
//      this.env                        =   env;
        setCurrentGarbageCollectionLevel(env.getState().intProperty(env.getState().GARBAGE_COLLECTION_LEVEL,0));
//      surelyReachableObjectsWhichHaveToBeMarkedAsSuch =   new DxListDeque;
        surelyReachableObjectsWhichHaveToBeMarkedAsSuch =   new SimpleArrayList(10000); // We expect at least 10000 entries in a busy database.
        surelyReachableObjectsWhichShouldHaveBeenProcessedButWereLockContented  =   new LinkedList();
        transactionsRequiredToComplete  =   new HashSet();
    }

    protected void setCurrentGarbageCollectionLevel(int to) {
        synchronized (garbageCollectionLevelsLock) {
            this.currentGarbageCollectionLevel          =   to;
            this.doneReachableGarbageCollectionLevel    =   this.currentGarbageCollectionLevel+1;
        }
    }

    public void startup() {
        env.getLogWriter().newEntry( this, "startup...", LogWriter.INFO);
        env.getLogWriter().newEntry( this, "garbageCollection level set to " + currentGarbageCollectionLevel, LogWriter.DEBUG);
    }


    public void shutdown() {
        kill = true;
    }


    public void save() {
    }

    /**
        Starts the garbage collection process.
    */
    public void start() {
        env.getLogWriter().newEntry(this,"start()", LogWriter.DEBUG1);
        synchronized (this) {
            if (phase==PHASE_IDLE) {
                if (garbageCollectionThread==null) {
                    setPhase(PHASE_RUN_INITIATED);
                    garbageCollectionThread =   env.getInvokeServer().newThread(this);
                    garbageCollectionThread.start();
                } else {
                    // We're already started
                }
            } else {
                // We're already started
            }
        }
    }

    public void addTransactionRequiredToComplete(Object ta) {
        transactionsRequiredToComplete.add(ta);
    }

    public void removeTransactionRequiredToComplete(Transaction ta) {
        if (!transactionsRequiredToComplete.isEmpty()) {
            transactionsRequiredToComplete.remove(ta);
            checkForEndOfWaitForCurrentTransactionsToCompletePhase();
        }
    }

    protected void checkForEndOfWaitForCurrentTransactionsToCompletePhase() {
        if (transactionsRequiredToComplete.isEmpty()) {
            notifyEndOfWaitForCurrentTransactionsToCompletePhase();
        }
    }

    /**
        Informs this GarbageCollector, the the pre-phase is done, there are no transactions that
        are older than this garbage collector run.
    */
    protected void notifyEndOfWaitForCurrentTransactionsToCompletePhase() {
        synchronized (this) {
            /*
            if (phase==PHASE_WAITING_FOR_OLD_TRANSACTIONS_TO_COMPLETE) {
                phase = PHASE_READY_TO_START;
            }
            */
            setPhase(phase+1);
            notify();
        }
    }

    protected void incCurrentGarbageCollectorLevel() {
        setCurrentGarbageCollectionLevel(currentGarbageCollectionLevel+4);
        env.getState().setIntProperty(env.getState().GARBAGE_COLLECTION_LEVEL,currentGarbageCollectionLevel);
        setChanged();
    }

    /**
        The main method for garbage collection.
    */
    public void run() {
        env.getLogWriter().newEntry(this,"garbage collection running...",LogWriter.DEBUG);
        try {
            incCurrentGarbageCollectorLevel();

            setPhase(PHASE_WAITING_FOR_OLD_TRANSACTIONS_TO_COMPLETE);

            env.getTransactionManager().startGarbageCollectionWaitForCurrentTransactionsToCompletePhase(this);

            waitForPhase(PHASE_READY_TO_START);

            renewTransactionIfRequired();

            addRootSetElementsToSurelyReachableSet();

            setPhase(PHASE_MARKING);

            processSurelyReachableObjectsWhichHaveToBeMarkedAsSuch();

            if (kill) {
                return;
            }

            setPhase(PHASE_WAITING_FOR_NEW_TRANSACTIONS_TO_COMPLETE);

            env.getTransactionManager().startGarbageCollectionWaitForCurrentTransactionsToCompletePhase(this);

            waitForPhase(PHASE_MARKING2);

            processSurelyReachableObjectsWhichHaveToBeMarkedAsSuch();

            if (kill) {
                return;
            }

            setPhase(PHASE_SWEEPING);

            sweepUnreachableObjects();

        } catch (Throwable e) {
            env.getLogWriter().newEntry(this,"GC caught: ",e,env.getLogWriter().ERROR);
        } finally {
            env.getLogWriter().newEntry(this,"garbage collection end...",LogWriter.DEBUG);
            garbageCollectionThread = null;
            setPhase(PHASE_IDLE);
            try {
                if (transaction!=null) { // We are crashing with an open transaction, let's abort it..
                    internalAbortTransaction(transaction);
//                  internalFinishTransaction(transaction);
                    env.getTransactionManager().deleteTransaction();
                    transaction = null;
                }
            } catch (ClassNotFoundException e) {
                env.getLogWriter().newEntry(this,"caught: ",e,env.getLogWriter().ERROR);
            } catch (IOException e) {
                env.getLogWriter().newEntry(this,"caught: ",e,env.getLogWriter().ERROR);
            }
        }
    }

    protected void notifyAboutTransactionActionAndRenewTransactionIfRequired() throws IOException,ClassNotFoundException,TransactionException {
        renewTransactionIfRequired();
        actionsWithinTransactionCount++;
    }