3 * @defgroup LockManager Lock management
8 * Resource locking handling.
10 * This program is free software; you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation; either version 2 of the License, or
13 * (at your option) any later version.
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
20 * You should have received a copy of the GNU General Public License along
21 * with this program; if not, write to the Free Software Foundation, Inc.,
22 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
23 * http://www.gnu.org/copyleft/gpl.html
26 * @ingroup LockManager
27 * @author Aaron Schulz
31 * @brief Class for handling resource locking.
33 * Locks on resource keys can either be shared or exclusive.
35 * Implementations must keep track of what is locked by this proccess
36 * in-memory and support nested locking calls (using reference counting).
37 * At least LOCK_UW and LOCK_EX must be implemented. LOCK_SH can be a no-op.
38 * Locks should either be non-blocking or have low wait timeouts.
40 * Subclasses should avoid throwing exceptions at all costs.
42 * @ingroup LockManager
45 abstract class LockManager
{
46 /** @var Array Mapping of lock types to the type actually used */
47 protected $lockTypeMap = array(
48 self
::LOCK_SH
=> self
::LOCK_SH
,
49 self
::LOCK_UW
=> self
::LOCK_EX
, // subclasses may use self::LOCK_SH
50 self
::LOCK_EX
=> self
::LOCK_EX
53 /** @var Array Map of (resource path => lock type => count) */
54 protected $locksHeld = array();
56 /* Lock types; stronger locks have higher values */
57 const LOCK_SH
= 1; // shared lock (for reads)
58 const LOCK_UW
= 2; // shared lock (for reads used to write elsewhere)
59 const LOCK_EX
= 3; // exclusive lock (for writes)
62 * Construct a new instance from configuration
64 * @param $config Array
66 public function __construct( array $config ) {}
69 * Lock the resources at the given abstract paths
71 * @param $paths Array List of resource names
72 * @param $type integer LockManager::LOCK_* constant
75 final public function lock( array $paths, $type = self
::LOCK_EX
) {
76 wfProfileIn( __METHOD__
);
77 $status = $this->doLock( array_unique( $paths ), $this->lockTypeMap
[$type] );
78 wfProfileOut( __METHOD__
);
83 * Unlock the resources at the given abstract paths
85 * @param $paths Array List of storage paths
86 * @param $type integer LockManager::LOCK_* constant
89 final public function unlock( array $paths, $type = self
::LOCK_EX
) {
90 wfProfileIn( __METHOD__
);
91 $status = $this->doUnlock( array_unique( $paths ), $this->lockTypeMap
[$type] );
92 wfProfileOut( __METHOD__
);
97 * Get the base 36 SHA-1 of a string, padded to 31 digits
102 final protected static function sha1Base36( $path ) {
103 return wfBaseConvert( sha1( $path ), 16, 36, 31 );
107 * Lock resources with the given keys and lock type
109 * @param $paths Array List of storage paths
110 * @param $type integer LockManager::LOCK_* constant
113 abstract protected function doLock( array $paths, $type );
116 * Unlock resources with the given keys and lock type
118 * @param $paths Array List of storage paths
119 * @param $type integer LockManager::LOCK_* constant
122 abstract protected function doUnlock( array $paths, $type );
126 * Version of LockManager that uses a quorum from peer servers for locks.
127 * The resource space can also be sharded into separate peer groups.
129 * @ingroup LockManager
132 abstract class QuorumLockManager
extends LockManager
{
133 /** @var Array Map of bucket indexes to peer server lists */
134 protected $srvsByBucket = array(); // (bucket index => (lsrv1, lsrv2, ...))
137 * @see LockManager::doLock()
138 * @param $paths array
142 final protected function doLock( array $paths, $type ) {
143 $status = Status
::newGood();
145 $pathsToLock = array(); // (bucket => paths)
146 // Get locks that need to be acquired (buckets => locks)...
147 foreach ( $paths as $path ) {
148 if ( isset( $this->locksHeld
[$path][$type] ) ) {
149 ++
$this->locksHeld
[$path][$type];
150 } elseif ( isset( $this->locksHeld
[$path][self
::LOCK_EX
] ) ) {
151 $this->locksHeld
[$path][$type] = 1;
153 $bucket = $this->getBucketFromKey( $path );
154 $pathsToLock[$bucket][] = $path;
158 $lockedPaths = array(); // files locked in this attempt
159 // Attempt to acquire these locks...
160 foreach ( $pathsToLock as $bucket => $paths ) {
161 // Try to acquire the locks for this bucket
162 $status->merge( $this->doLockingRequestBucket( $bucket, $paths, $type ) );
163 if ( !$status->isOK() ) {
164 $status->merge( $this->doUnlock( $lockedPaths, $type ) );
167 // Record these locks as active
168 foreach ( $paths as $path ) {
169 $this->locksHeld
[$path][$type] = 1; // locked
171 // Keep track of what locks were made in this attempt
172 $lockedPaths = array_merge( $lockedPaths, $paths );
179 * @see LockManager::doUnlock()
180 * @param $paths array
184 final protected function doUnlock( array $paths, $type ) {
185 $status = Status
::newGood();
187 $pathsToUnlock = array();
188 foreach ( $paths as $path ) {
189 if ( !isset( $this->locksHeld
[$path][$type] ) ) {
190 $status->warning( 'lockmanager-notlocked', $path );
192 --$this->locksHeld
[$path][$type];
193 // Reference count the locks held and release locks when zero
194 if ( $this->locksHeld
[$path][$type] <= 0 ) {
195 unset( $this->locksHeld
[$path][$type] );
196 $bucket = $this->getBucketFromKey( $path );
197 $pathsToUnlock[$bucket][] = $path;
199 if ( !count( $this->locksHeld
[$path] ) ) {
200 unset( $this->locksHeld
[$path] ); // no SH or EX locks left for key
205 // Remove these specific locks if possible, or at least release
206 // all locks once this process is currently not holding any locks.
207 foreach ( $pathsToUnlock as $bucket => $paths ) {
208 $status->merge( $this->doUnlockingRequestBucket( $bucket, $paths, $type ) );
210 if ( !count( $this->locksHeld
) ) {
211 $status->merge( $this->releaseAllLocks() );
218 * Attempt to acquire locks with the peers for a bucket.
219 * This is all or nothing; if any key is locked then this totally fails.
221 * @param $bucket integer
222 * @param $paths Array List of resource keys to lock
223 * @param $type integer LockManager::LOCK_EX or LockManager::LOCK_SH
226 final protected function doLockingRequestBucket( $bucket, array $paths, $type ) {
227 $status = Status
::newGood();
229 $yesVotes = 0; // locks made on trustable servers
230 $votesLeft = count( $this->srvsByBucket
[$bucket] ); // remaining peers
231 $quorum = floor( $votesLeft/2 +
1 ); // simple majority
232 // Get votes for each peer, in order, until we have enough...
233 foreach ( $this->srvsByBucket
[$bucket] as $lockSrv ) {
234 if ( !$this->isServerUp( $lockSrv ) ) {
236 $status->warning( 'lockmanager-fail-svr-acquire', $lockSrv );
237 continue; // server down?
239 // Attempt to acquire the lock on this peer
240 $status->merge( $this->getLocksOnServer( $lockSrv, $paths, $type ) );
241 if ( !$status->isOK() ) {
242 return $status; // vetoed; resource locked
244 ++
$yesVotes; // success for this peer
245 if ( $yesVotes >= $quorum ) {
246 return $status; // lock obtained
249 $votesNeeded = $quorum - $yesVotes;
250 if ( $votesNeeded > $votesLeft ) {
251 break; // short-circuit
254 // At this point, we must not have met the quorum
255 $status->setResult( false );
261 * Attempt to release locks with the peers for a bucket
263 * @param $bucket integer
264 * @param $paths Array List of resource keys to lock
265 * @param $type integer LockManager::LOCK_EX or LockManager::LOCK_SH
268 final protected function doUnlockingRequestBucket( $bucket, array $paths, $type ) {
269 $status = Status
::newGood();
271 foreach ( $this->srvsByBucket
[$bucket] as $lockSrv ) {
272 if ( !$this->isServerUp( $lockSrv ) ) {
273 $status->fatal( 'lockmanager-fail-svr-release', $lockSrv );
274 // Attempt to release the lock on this peer
276 $status->merge( $this->freeLocksOnServer( $lockSrv, $paths, $type ) );
284 * Get the bucket for resource path.
285 * This should avoid throwing any exceptions.
287 * @param $path string
290 protected function getBucketFromKey( $path ) {
291 $prefix = substr( sha1( $path ), 0, 2 ); // first 2 hex chars (8 bits)
292 return (int)base_convert( $prefix, 16, 10 ) %
count( $this->srvsByBucket
);
296 * Check if a lock server is up
298 * @param $lockSrv string
301 abstract protected function isServerUp( $lockSrv );
304 * Get a connection to a lock server and acquire locks on $paths
306 * @param $lockSrv string
307 * @param $paths array
308 * @param $type integer
311 abstract protected function getLocksOnServer( $lockSrv, array $paths, $type );
314 * Get a connection to a lock server and release locks on $paths.
316 * Subclasses must effectively implement this or releaseAllLocks().
318 * @param $lockSrv string
319 * @param $paths array
320 * @param $type integer
323 abstract protected function freeLocksOnServer( $lockSrv, array $paths, $type );
326 * Release all locks that this session is holding.
328 * Subclasses must effectively implement this or freeLocksOnServer().
332 abstract protected function releaseAllLocks();
336 * Simple version of LockManager that does nothing
339 class NullLockManager
extends LockManager
{
341 * @see LockManager::doLock()
342 * @param $paths array
346 protected function doLock( array $paths, $type ) {
347 return Status
::newGood();
351 * @see LockManager::doUnlock()
352 * @param $paths array
356 protected function doUnlock( array $paths, $type ) {
357 return Status
::newGood();