Mailing-List: contact derby-commits-help@db.apache.org; run by ezmlm
Precedence: bulk
Reply-To: "Derby Development" <derby-dev@db.apache.org>
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: svn commit: r603491 - in
 /db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache:
 CacheEntry.java ClockPolicy.java ConcurrentCache.java
Date: Wed, 12 Dec 2007 07:00:47 -0000
To: derby-commits@db.apache.org
From: kahatlen@apache.org
Message-Id: <20071212070049.BAE981A9838@eris.apache.org>

Author: kahatlen
Date: Tue Dec 11 23:00:46 2007
New Revision: 603491

URL: http://svn.apache.org/viewvc?rev=603491&view=rev
Log:
DERBY-2911: Implement a buffer manager using java.util.concurrent classes

Release the ReentrantLock on the CacheEntry while the identity of the
Cacheable is being set. Otherwise, we may run into a deadlock if the
Cacheable's setIdentity() or createIdentity() method accesses the cache.

Modified:
    db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/CacheEntry.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ClockPolicy.java
    db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ConcurrentCache.java

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/CacheEntry.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/CacheEntry.java?rev=603491&r1=603490&r2=603491&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/CacheEntry.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/CacheEntry.java Tue Dec 11 23:00:46 2007
@@ -39,13 +39,13 @@
  *
  * <dl>
  *
- * <dt>Uninitialized</dt> <dd>The entry object has just been constructed. In
- * this state, <code>isValid()</code> and <code>isKept()</code> return
- * <code>false</code>, and <code>getCacheable()</code> returns
- * <code>null</code>. As long as the entry is in this state, the reference to
- * the object should not be made available to other threads than the one that
- * created it, since there is no way for other threads to see the difference
- * between an uninitialized entry and a removed entry.</dd>
+ * <dt>Uninitialized</dt> <dd>The entry object has just been constructed, but
+ * has not yet been initialized. In this state, <code>isValid()</code> returns
+ * <code>false</code>, whereas <code>isKept()</code> returns <code>true</code>
+ * in order to prevent removal of the entry until it has been initialized.
+ * When the entry is in this state, calls to
+ * <code>lockWhenIdentityIsSet()</code> will block until
+ * <code>settingIdentityComplete()</code> has been called.</dd>
  *
  * <dt>Unkept</dt> <dd>In this state, the entry object contains a reference to
  * a <code>Cacheable</code> and the keep count is zero. <code>isValid()</code>
@@ -94,6 +94,14 @@
     private Condition forRemove;
 
     /**
+     * Condition variable used to notify a thread that the setting of this
+     * entry's identity is complete. This variable is non-null when the object
+     * is created, and will be set to null when the identity has been set.
+     * @see #settingIdentityComplete()
+     */
+    private Condition settingIdentity = mutex.newCondition();
+
+    /**
      * Callback object used to notify the replacement algorithm about events on
      * the cached objects (like accesses and requests for removal).
      */
@@ -110,6 +118,18 @@
     }
 
     /**
+     * Block until this entry's cacheable has been initialized (that is, until
+     * <code>settingIdentityComplete()</code> has been called on this object)
+     * and the current thread is granted exclusive access to the entry.
+     */
+    void lockWhenIdentityIsSet() {
+        lock();
+        while (settingIdentity != null) {
+            settingIdentity.awaitUninterruptibly();
+        }
+    }
+
+    /**
      * Give up exclusive access.
      */
     void unlock() {
@@ -117,6 +137,20 @@
     }
 
     /**
+     * Notify this entry that the initialization of its cacheable has been
+     * completed. This method should be called after
+     * <code>Cacheable.setIdentity()</code> or
+     * <code>Cacheable.createIdentity()</code> has been called.
+     */
+    void settingIdentityComplete() {
+        if (SanityManager.DEBUG) {
+            SanityManager.ASSERT(mutex.isHeldByCurrentThread());
+        }
+        settingIdentity.signalAll();
+        settingIdentity = null;
+    }
+
+    /**
      * Increase the keep count for this entry. An entry which is kept cannot be
      * removed from the cache.
      *
@@ -213,12 +247,17 @@
     }
 
     /**
-     * Check whether this entry holds a valid object.
+     * Check whether this entry holds a valid object. That is, it must hold
+     * a non-null <code>Cacheable</code> and have completed setting its
+     * identity.
      *
      * @return <code>true</code> if the entry holds a valid object
      */
     boolean isValid() {
-        return getCacheable() != null;
+        if (SanityManager.DEBUG) {
+            SanityManager.ASSERT(mutex.isHeldByCurrentThread());
+        }
+        return (settingIdentity == null) && (cacheable != null);
     }
 
     /**

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ClockPolicy.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ClockPolicy.java?rev=603491&r1=603490&r2=603491&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ClockPolicy.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ClockPolicy.java Tue Dec 11 23:00:46 2007
@@ -436,20 +436,22 @@
                     continue;
                 }
 
+                if (e.isKept()) {
+                    // The entry is in use. Move on to the next entry.
+                    continue;
+                }
+
                 if (SanityManager.DEBUG) {
-                    // At this point the entry must be valid. Otherwise, it
-                    // would have been removed from the Holder.
+                    // At this point the entry must be valid. If it's not, it's
+                    // either removed (in which case we shouldn't get here), or
+                    // it is setting it's identity (in which case it is kept,
+                    // and we shouldn't get here).
                     SanityManager.ASSERT(e.isValid(),
                             "Holder contains invalid entry");
                     SanityManager.ASSERT(!h.isEvicted(),
                             "Trying to reuse an evicted holder");
                 }
 
-                if (e.isKept()) {
-                    // The entry is in use. Move on to the next entry.
-                    continue;
-                }
-
                 if (h.recentlyUsed) {
                     // The object has been used recently. Clear the
                     // recentlyUsed flag and move on to the next entry.
@@ -620,17 +622,24 @@
                     continue;
                 }
 
+                if (e.isKept()) {
+                    // Don't evict entries currently in use.
+                    continue;
+                }
+
                 if (SanityManager.DEBUG) {
-                    // At this point the entry must be valid. Otherwise, it
-                    // would have been removed from the Holder.
+                    // At this point the entry must be valid. If it's not, it's
+                    // either removed (in which case we shouldn't get here), or
+                    // it is setting it's identity (in which case it is kept,
+                    // and we shouldn't get here).
                     SanityManager.ASSERT(e.isValid(),
                             "Holder contains invalid entry");
                     SanityManager.ASSERT(!h.isEvicted(),
                             "Trying to evict already evicted holder");
                 }
 
-                if (e.isKept() || h.recentlyUsed) {
-                    // Don't evict entries currently in use or recently used.
+                if (h.recentlyUsed) {
+                    // Don't evict recently used entries.
                     continue;
                 }
 

Modified: db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ConcurrentCache.java
URL: http://svn.apache.org/viewvc/db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ConcurrentCache.java?rev=603491&r1=603490&r2=603491&view=diff
==============================================================================
--- db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ConcurrentCache.java (original)
+++ db/derby/code/trunk/java/engine/org/apache/derby/impl/services/cache/ConcurrentCache.java Tue Dec 11 23:00:46 2007
@@ -105,7 +105,8 @@
      * Get the entry associated with the specified key from the cache. If the
      * entry does not exist, insert an empty one and return it. The returned
      * entry is always locked for exclusive access by the current thread, but
-     * not kept.
+     * not kept. If another thread is currently setting the identity of this
+     * entry, this method will block until the identity has been set.
      *
      * @param key the identity of the cached object
      * @return an entry for the specified key, always locked
@@ -114,9 +115,9 @@
         CacheEntry entry = cache.get(key);
         while (true) {
             if (entry != null) {
-                // Found an entry in the cache. Lock it and validate that it's
-                // still there.
-                entry.lock();
+                // Found an entry in the cache. Lock it, but wait until its
+                // identity has been set.
+                entry.lockWhenIdentityIsSet();
                 if (entry.isValid()) {
                     // Entry is still valid. Return it.
                     return entry;
@@ -147,22 +148,6 @@
     }
 
     /**
-     * Find a free cacheable and give the specified entry a pointer to it. If
-     * a free cacheable cannot be found, allocate a new one. The entry must be
-     * locked by the current thread.
-     *
-     * @param entry the entry for which a <code>Cacheable</code> is needed
-     * @exception StandardException if an error occurs during the search for
-     * a free cacheable
-     */
-    private void findFreeCacheable(CacheEntry entry) throws StandardException {
-        replacementPolicy.insertEntry(entry);
-        if (!entry.isValid()) {
-            entry.setCacheable(holderFactory.newCacheable(this));
-        }
-    }
-
-    /**
      * Remove an entry from the cache. Its <code>Cacheable</code> is cleared
      * and made available for other entries. This method should only be called
      * if the entry is present in the cache and locked by the current thread.
@@ -196,52 +181,94 @@
     }
 
     /**
-     * Initialize an entry by finding a free <code>Cacheable</code> and setting
-     * its identity. If the identity is successfully set, the entry is kept and
-     * the <code>Cacheable</code> is inserted into the entry and returned.
-     * Otherwise, the entry is removed from the cache and <code>null</code>
-     * is returned.
-     *
-     * @param entry the entry to initialize
-     * @param key the identity to set
-     * @param createParameter parameter to <code>createIdentity()</code>
-     * (ignored if <code>create</code> is <code>false</code>)
-     * @param create if <code>true</code>, create new identity with
-     * <code>Cacheable.createIdentity()</code>; otherwise, set identity with
-     * <code>Cacheable.setIdentity()</code>
-     * @return a <code>Cacheable</code> if the identity could be set,
-     * <code>null</code> otherwise
-     * @exception StandardException if an error occured while searching for a
-     * free <code>Cacheable</code> or while setting the identity
-     * @see Cacheable#setIdentity(Object)
-     * @see Cacheable#createIdentity(Object,Object)
+     * Find or create an object in the cache. If the object is not presently
+     * in the cache, it will be added to the cache.
+     *
+     * @param key the identity of the object to find or create
+     * @param create whether or not the object should be created
+     * @param createParameter used as argument to <code>createIdentity()</code>
+     * when <code>create</code> is <code>true</code>
+     * @return the cached object, or <code>null</code> if it cannot be found
+     * @throws StandardException if an error happens when accessing the object
      */
-    private Cacheable initIdentity(CacheEntry entry,
-            Object key, Object createParameter, boolean create)
+    private Cacheable findOrCreateObject(Object key, boolean create,
+                                         Object createParameter)
             throws StandardException {
+
+        if (SanityManager.DEBUG) {
+            SanityManager.ASSERT(createParameter == null || create,
+                    "createParameter should be null when create is false");
+        }
+
+        if (stopped) {
+            return null;
+        }
+
+        // A free cacheable which we'll initialize if we don't find the object
+        // in the cache.
+        Cacheable free;
+
+        CacheEntry entry = getEntry(key);
+        try {
+            Cacheable item = entry.getCacheable();
+            if (item != null) {
+                if (create) {
+                    throw StandardException.newException(
+                            SQLState.OBJECT_EXISTS_IN_CACHE, name, key);
+                }
+                entry.keep(true);
+                return item;
+            }
+
+            // not currently in the cache
+            try {
+                replacementPolicy.insertEntry(entry);
+            } catch (StandardException se) {
+                removeEntry(key);
+                throw se;
+            }
+
+            free = entry.getCacheable();
+            if (free == null) {
+                // We didn't get a reusable cacheable. Create a new one.
+                free = holderFactory.newCacheable(this);
+            }
+
+            entry.keep(true);
+
+        } finally {
+            entry.unlock();
+        }
+
+        // Set the identity in a try/finally so that we can remove the entry
+        // if the operation fails. We have released the lock on the entry so
+        // that we don't run into deadlocks if the user code (setIdentity() or
+        // createIdentity()) reenters the cache.
         Cacheable c = null;
         try {
-            findFreeCacheable(entry);
             if (create) {
-                c = entry.getCacheable().createIdentity(key, createParameter);
+                c = free.createIdentity(key, createParameter);
             } else {
-                c = entry.getCacheable().setIdentity(key);
+                c = free.setIdentity(key);
             }
         } finally {
-            if (c == null) {
-                // Either an exception was thrown, or setIdentity() or
-                // createIdentity() returned null. In either case, the entry is
-                // invalid and must be removed.
-                removeEntry(key);
+            entry.lock();
+            try {
+                // Notify the entry that setIdentity() or createIdentity() has
+                // finished.
+                entry.settingIdentityComplete();
+                if (c == null) {
+                    // Setting identity failed, or the object was not found.
+                    removeEntry(key);
+                } else {
+                    // Successfully set the identity.
+                    entry.setCacheable(c);
+                }
+            } finally {
+                entry.unlock();
             }
         }
 
-        // If we successfully set the identity, insert the cacheable and mark
-        // the entry as kept.
-        if (c != null) {
-            entry.setCacheable(c);
-            entry.keep(true);
-        }
         return c;
     }
 
@@ -256,23 +283,7 @@
      * @return the cached object, or <code>null</code> if it cannot be found
      */
     public Cacheable find(Object key) throws StandardException {
-
-        if (stopped) {
-            return null;
-        }
-
-        CacheEntry entry = getEntry(key);
-        try {
-            Cacheable item = entry.getCacheable();
-            if (item != null) {
-                entry.keep(true);
-                return item;
-            }
-            // not currently in the cache
-            return initIdentity(entry, key, null, false);
-        } finally {
-            entry.unlock();
-        }
+        return findOrCreateObject(key, false, null);
     }
 
     /**
@@ -296,7 +307,9 @@
             // No such object was found in the cache.
             return null;
         }
-        entry.lock();
+
+        // Lock the entry, but wait until its identity has been set.
+        entry.lockWhenIdentityIsSet();
         try {
             // Return the cacheable. If the entry was removed right before we
             // locked it, getCacheable() returns null and so should we do.
@@ -325,21 +338,7 @@
      */
     public Cacheable create(Object key, Object createParameter)
             throws StandardException {
-
-        if (stopped) {
-            return null;
-        }
-
-        CacheEntry entry = getEntry(key);
-        try {
-            if (entry.isValid()) {
-                throw StandardException.newException(
-                    SQLState.OBJECT_EXISTS_IN_CACHE, name, key);
-            }
-            return initIdentity(entry, key, createParameter, true);
-        } finally {
-            entry.unlock();
-        }
+        return findOrCreateObject(key, true, createParameter);
     }
 
     /**