LockManager.java
/*
** Module :LockManager.java
** Abstract :Directory tree locks management.
**
** Copyright (c) 2005-2023, Golden Code Development Corporation.
**
** -#- -I- --Date-- --JPRM-- ----------------Description-----------------
** 001 SIY 20050303 @20363 Created initial version
** 002 SIY 20050322 @20462 Fixed incorrect initial lock state
** 003 SIY 20050328 @20582 Fixed comments.
** 004 SIY 20050429 @21019 Fixed formatting, exclusive read lock now
** fails if intersects with other lock (instead
** of blocking).
** 005 SIY 20080626 @38970 Fixed significant synchronization issues,
** deeply refactored, cleaned up and documented.
** 006 SIY 20080725 @39216 Removed unnecessary exception in removeLock().
** 007 SIY 20090917 @43924 Replaced throwing an exception with logging in
** case of attempt to release already released lock.
** 008 SIY 20090924 @44007 Slightly changed enterLock() in order to simplify
** exit from wait loop in case of shutdown.
** 009 GBB 20230512 Logging methods replaced by CentralLogger/ConversionStatus.
*/
/*
** This program is free software: you can redistribute it and/or modify
** it under the terms of the GNU Affero General Public License as
** published by the Free Software Foundation, either version 3 of the
** License, or (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
** GNU Affero General Public License for more details.
**
** You may find a copy of the GNU Affero GPL version 3 at the following
** location: https://www.gnu.org/licenses/agpl-3.0.en.html
**
** Additional terms under GNU Affero GPL version 3 section 7:
**
** Under Section 7 of the GNU Affero GPL version 3, the following additional
** terms apply to the works covered under the License. These additional terms
** are non-permissive additional terms allowed under Section 7 of the GNU
** Affero GPL version 3 and may not be removed by you.
**
** 0. Attribution Requirement.
**
** You must preserve all legal notices or author attributions in the covered
** work or Appropriate Legal Notices displayed by works containing the covered
** work. You may not remove from the covered work any author or developer
** credit already included within the covered work.
**
** 1. No License To Use Trademarks.
**
** This license does not grant any license or rights to use the trademarks
** Golden Code, FWD, any Golden Code or FWD logo, or any other trademarks
** of Golden Code Development Corporation. You are not authorized to use the
** name Golden Code, FWD, or the names of any author or contributor, for
** publicity purposes without written authorization.
**
** 2. No Misrepresentation of Affiliation.
**
** You may not represent yourself as Golden Code Development Corporation or FWD.
**
** You may not represent yourself for publicity purposes as associated with
** Golden Code Development Corporation, FWD, or any author or contributor to
** the covered work, without written authorization.
**
** 3. No Misrepresentation of Source or Origin.
**
** You may not represent the covered work as solely your work. All modified
** versions of the covered work must be marked in a reasonable way to make it
** clear that the modified work is not originating from Golden Code Development
** Corporation or FWD. All modified versions must contain the notices of
** attribution required in this license.
*/
package com.goldencode.p2j.directory;
import java.util.ArrayList;
import java.util.logging.*;
import com.goldencode.p2j.util.logging.*;
/**
* The purpose of this class is to maintain a set of locks where each lock is
* identified by the DirectoryService ID. The Manager maintains different
* types of locks: Read/Write (R/W), Read-Only (R/O) and exclusive lock.
* Exclusive locks can be of two different types: Read-exclusive (R/X) and
* Write-exclusive (R/W). Read-exclusive locks allow R/O locks to be set but
* do not allow setting of R/W locks. Write-exclusive locks do not allow
* setting of other types of the locks. Read-only locks can coexist with the
* R/W locks.
*
* @author SIY
* @version 1.0
*/
class LockManager
{
/** String representation of lock types */
public static final String[] name = { "RO", "RW", "RX", "WX" };
/**
* Number of different types of locks. Note that changes in this
* constant will require adjustments in {@link Lock#getCount()}.*/
public static final int LOCK_COUNT = 4;
/** Read-only lock */
public static final int LOCK_RO = 0;
/** Read/Write lock */
public static final int LOCK_RW = 1;
/** Exclusive lock stage #1 */
public static final int LOCK_RX = 2;
/** Exclusive lock stage #2 */
public static final int LOCK_WX = 3;
/** Data storage where locks are stored */
private ArrayList<Lock> lockList = new ArrayList<Lock>();
/** Shutdown flag */
private boolean shutdown = false;
private static CentralLogger LOG = null;
/**
* Construct an instance of TreeLockManager.
*/
LockManager()
{
}
/**
* Try to lock sub-tree. If such a lock with compatible type already exists
* then lock count is increased, otherwise new lock is created. Note that
* W/X lock can't be set, it can be only upgraded from R/X lock.
* <p>
* Rules of lock coexistence:<br>
* <ol>
* <li>R/O lock can be set in parallel with any other lock.</li>
* <li>R/W lock can be set on R/O lock. If any other type of lock is set,
* R/W lock will wait while all other locks will be released.</li>
* <li>R/X lock can be set only if no lock exists.</li>
* <li>W/X lock can't be set at all, it only can be upgraded from R/X
* lock.</li>
* </ol>
*
* @param id
* Sub-tree id to lock
* @param type
* Lock type to set.
*
* @return Reference of the existing lock or new lock, or <code>null</code>
* if lock can't be set for some reason.
*/
public Object enterLock(String id, int type)
{
id = IdUtils.normalize(id);
if (id == null || type == LOCK_WX)
return null;
Lock lock = null;
boolean repeat = false;
do
{
repeat = false;
// this can happen when at previous iteration
// we have found existing lock
if (lock != null)
{
// wait while lock will be released completely
try
{
synchronized (lock)
{
while(lock.getCount() > 0)
lock.wait(1000);
if (shutdown && lock.getCount() > 0)
{
// no chances to obtain lock before shutdown, bail out
return null;
}
}
}
catch (InterruptedException e)
{
if (shutdown)
return null;
}
catch (Throwable e)
{
// probably something is very wrong, bail out
return null;
}
}
synchronized (lockList)
{
lock = locateLock(id);
if (lock == null ||
type == LOCK_RX ||
lock.getType() == LOCK_WX ||
((lock.getType() == LOCK_RX || lock.getType() == LOCK_WX) &&
type != LOCK_RO))
{
// we should wait while lock will be released
if (lock != null)
{
// lets wait outside the synchronization block
repeat = true;
continue;
}
lock = insertLock(new Lock(id, type));
}
synchronized (lock)
{
lock.enter(type);
}
}
}
while ((lock == null || repeat) && !shutdown);
if (shutdown)
return null;
return new LockRef(lock, type);
}
/**
* Release existing lock and notify all waiting threads if counter is set
* to 0.
*
* @param objLock
* Reference to lock which will be released.
*/
public void releaseLock(Object objLock)
{
if (!(objLock instanceof LockRef))
return;
((LockRef) objLock).release();
}
/**
* Shutdown manager and release all waiting threads.
*/
public synchronized void shutdownManager()
{
shutdown = true;
}
/**
* Upgrade RX lock into RW lock.
*
* @param objLock
* Reference to lock provided by the enterLock.
* @return <code>true</code> if upgrade was successful.
*/
public boolean upgradeLock(Object objLock)
{
if (!(objLock instanceof LockRef))
return false;
return ((LockRef) objLock).upgrade();
}
/**
* Get snapshot of the current list of locks.
*
* @param msg
* Additional message which will be printed in dump header.
*/
void dumpLocks(String msg)
{
synchronized (lockList)
{
StringBuilder sb = new StringBuilder("Lock manager state at [" + msg + "] stage ("
+ lockList.size() + ")");
sb.append(System.lineSeparator());
for (int i = 0; i < lockList.size(); i++)
{
sb.append(i);
sb.append(") ");
sb.append(lockList.get(i));
if (i < lockList.size() - 1)
{
sb.append(System.lineSeparator());
}
}
LOG.info(sb.toString());
}
}
/**
* Logging helper.
*
* @param level
* Debug level of this message.
* @param message
* Text of the message.
*/
private static void log(Level level, String message)
{
if (LOG == null)
{
LOG = CentralLogger.get(DirectoryService.class);
}
LOG.log(level, message, new Throwable());
}
/**
* Insert lock into the array.
*
* @param lock
* <code>Lock</code> instance to insert.
* @return Lock passed as a parameter if operation was successful and
* <code>null</code> otherwise.
*/
private Lock insertLock(Lock lock)
{
try
{
int index = locateLockIndex(lock.getId());
if (index >= 0 && index < lockList.size())
{
Lock tmpLock = lockList.get(index);
if (lock.getId().equals(tmpLock.getId()))
return null;
}
lockList.add(index, lock);
return lock;
}
catch (Exception e)
{
//Seems we're out of bounds, no such element then.
LOG.warning("", e);
}
return null;
}
/**
* Locate existing lock which is on the same path the ID passed as a
* parameter.
* <p>
* Note that this method is invoked only from inside synchronization block
* on {@link #lockList}.
*
* @param id
* Sub-tree ID.
*
* @return Existing lock or <code>null</code> if there is no such lock.
*/
private Lock locateLock(String id)
{
if (lockList.size() == 0)
return null;
int ndx = locateLockIndex(id);
Lock lock = null;
//The locateLockIndex() uses binary search
//and this algorithm has one interesting
//feature when applied to the arrays:
//it returns position of exactly matching
//element or position at which given element
//should be inserted into the list.
//Taking into account this behavior following
//possibilities are possible:
//1. Exact match
//2. Element at index below the returned by
// locateLockIndex() has id which is a prefix of given id
//3. Element at index returned by locateLockIndex() has id for which
// given id is an prefix.
//4. None of the 2 and 3 is true.
if (ndx == 0)
{
//Only #1 and #3 are possible
lock = lockList.get(ndx);
if (lock.getId().startsWith(id))
return lock;
return null;
}
if (ndx == lockList.size())
{
//Only #2 is possible
lock = lockList.get(ndx - 1);
if (id.startsWith(lock.getId()))
return lock;
return null;
}
lock = lockList.get(ndx);
//Cover cases #1 and #3
if (lock.getId().startsWith(id))
return lock;
//Cover case #2
lock = lockList.get(ndx - 1);
if (id.startsWith(lock.getId()))
return lock;
return null;
}
/**
* Locate an index of the lock with the same ID or index where element with
* ID provided as a parameter can be inserted without breaking ordering of
* the array. Binary search algorithm is used.
*
* @param id
* Subtree ID.
* @return Index of the element.
*/
private int locateLockIndex(String id)
{
int l = 0;
int m = 0;
int h = lockList.size() - 1;
while (l <= h)
{
m = (l + h) / 2;
Lock lock = lockList.get(m);
int rc = id.compareTo(lock.getId());
if (rc == 0)
return m;
if (rc < 0)
h = m - 1;
if (rc > 0)
l = m + 1;
}
return l;
}
/**
* Remove specified lock from the list.
* <p>
* Logic of {@link #enterLock(String, int)} and
* {@link #releaseLock(Object)} allow a situation when lock is found in the
* list and is about to be incremented (i.e {@link Lock#enter(int)} is
* called) while this method is called. Since methods mentioned above
* contain synchronization block on {@link #lockList}, the body of this
* method will not be executed until those method will finish their work.
* Since lock count may change, we check it right after entering the block.
*
* @param lock
* A lock to remove.
*/
private void removeLock(Lock lock)
{
synchronized (lockList)
{
for (int i = 0; i < lockList.size(); i++)
{
if (lockList.get(i) == lock)
{
synchronized (lock)
{
if(lock.getCount() == 0)
lockList.remove(i);
}
return;
}
}
// Following scenario may reach this point in code:
//
// 1. Thread #1 enters lock
// 2. Thread #1 leaves lock and calls removeLock()
// but waits for release of lockList
// 3. Thread #2 enters lock
// 4. Thread #2 leaves lock and calls removeLock()
// but waits for release of lockList
// 5. Regardless from the order in which threads
// will be release, one of them will fail to find
// lock in the list
//
// Since this scenario is safe from the point of view of
// integrity of all structures and data, just ignore it.
}
}
/**
* An utility class which represents single lock.
*/
private class Lock
{
/** Array of lock counters. */
int[] counters = new int[LOCK_COUNT];
/** Lock ID */
private String id;
/** Lock type */
private int type;
/**
* Construct new Lock object.
*
* @param id
* Directory object ID.
* @param type
* Lock type.
*/
Lock(String id, int type)
{
this.id = id;
this.type = type;
}
/**
* Dump current lock state into <code>String</code>.
*
* @see java.lang.Object#toString()
* @return <code>String</code> with dump of current lock state.
*/
public String toString()
{
StringBuilder buf = new StringBuilder();
synchronized (this)
{
buf.append("id: ");
buf.append(getId());
buf.append(" type: ");
buf.append(name[type]);
buf.append(" locks: ");
buf.append("{RO: ");
buf.append(counters[LOCK_RO]);
buf.append(" RW: ");
buf.append(counters[LOCK_RW]);
buf.append(" RX: ");
buf.append(counters[LOCK_RX]);
buf.append(" WX: ");
buf.append(counters[LOCK_WX]);
buf.append("}");
return buf.toString();
}
}
/**
* Increment lock count.
*
* @param lockType
* Type of lock to set,
*/
void enter(int lockType)
{
if (lockType >= 0 && lockType < LOCK_COUNT)
counters[lockType] += 1;
}
/**
* Get lock count.
*
* @return Number of locks set on specified ID.
*/
int getCount()
{
// //long algorithm
//int counter = 0;
//
//for (int i = 0; i < counters.length; i++)
// counter += counters[i];
//
//return counter;
return counters[LOCK_RO] +
counters[LOCK_RW] +
counters[LOCK_RX] +
counters[LOCK_WX];
}
/**
* Get lock type.
*
* @return lock type.
*/
int getType()
{
return type;
}
/**
* Get lock ID.
*
* @return the id.
*/
public String getId()
{
return id;
}
/**
* Decrement lock count. Note that it is called when lock on the current
* object is obtained, so there is no need for additional
* synchronization.
*
* @param lockType
* Type of lock to remove,
*/
void leave(int lockType)
{
if (lockType < 0 || lockType >= LOCK_COUNT)
return;
boolean tryRemove = false;
synchronized (this)
{
if (counters[lockType] > 0)
{
counters[lockType] -= 1;
if (getCount() == 0)
tryRemove = true;
}
else
{
log(Level.INFO, "Attempt to release already released lock.");
}
notifyAll();
}
if (tryRemove)
removeLock(this);
}
/**
* Upgrade lock from RX to WX type.
*/
boolean upgrade()
{
try
{
synchronized (this)
{
if (type != LOCK_RX)
return false;
while (getCount() != 1)
{
this.wait();
}
upgradeInt();
return true;
}
}
catch (Exception e)
{
//Application shutdown.
return false;
}
}
/**
* All internals of the lock upgrade are collected here.
*/
void upgradeInt()
{
counters[LOCK_RX] -= 1;
counters[LOCK_WX] += 1;
type = LOCK_WX;
}
}
/**
* Utility class which is used to pass lock data between user and
* <code>LockManager</code>.
*/
static class LockRef
{
/** Reference to Lock */
private Lock lock;
/** Lock type */
private int type;
/**
* Construct an instance of LockRef.
*
* @param lock
* Reference to Lock object
* @param type
* Type of the lock to set/remove.
*/
public LockRef(Lock lock, int type)
{
this.lock = lock;
this.type = type;
}
/**
* Upgrade RX lock to WX lock.
*
* @return <code>true</code> if upgrade was successful.
*/
public boolean upgrade()
{
if (lock.upgrade())
{
type = LOCK_WX;
return true;
}
return false;
}
/**
* Release lock.
*/
public void release()
{
lock.leave(type);
}
@Override
public String toString()
{
return lock.toString();
}
}
}