includes/filebackend/lockmanager/LockManager.php

   1 <?php
   2 /**
   3  * @defgroup LockManager Lock management
   4  * @ingroup FileBackend
   5  */
   6
   7 /**
   8  * Resource locking handling.
   9  *
  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.
  14  *
  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.
  19  *
  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
  24  *
  25  * @file
  26  * @ingroup LockManager
  27  * @author Aaron Schulz
  28  */
  29
  30 /**
  31  * @brief Class for handling resource locking.
  32  *
  33  * Locks on resource keys can either be shared or exclusive.
  34  *
  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.
  39  *
  40  * Subclasses should avoid throwing exceptions at all costs.
  41  *
  42  * @ingroup LockManager
  43  * @since 1.19
  44  */
  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
  51         );
  52
  53         /** @var Array Map of (resource path => lock type => count) */
  54         protected $locksHeld = array();
  55
  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)
  60
  61         /**
  62          * Construct a new instance from configuration
  63          *
  64          * @param $config Array
  65          */
  66         public function __construct( array $config ) {}
  67
  68         /**
  69          * Lock the resources at the given abstract paths
  70          *
  71          * @param $paths Array List of resource names
  72          * @param $type integer LockManager::LOCK_* constant
  73          * @return Status
  74          */
  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__ );
  79                 return $status;
  80         }
  81
  82         /**
  83          * Unlock the resources at the given abstract paths
  84          *
  85          * @param $paths Array List of storage paths
  86          * @param $type integer LockManager::LOCK_* constant
  87          * @return Status
  88          */
  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__ );
  93                 return $status;
  94         }
  95
  96         /**
  97          * Get the base 36 SHA-1 of a string, padded to 31 digits
  98          *
  99          * @param $path string
 100          * @return string
 101          */
 102         final protected static function sha1Base36( $path ) {
 103                 return wfBaseConvert( sha1( $path ), 16, 36, 31 );
 104         }
 105
 106         /**
 107          * Lock resources with the given keys and lock type
 108          *
 109          * @param $paths Array List of storage paths
 110          * @param $type integer LockManager::LOCK_* constant
 111          * @return string
 112          */
 113         abstract protected function doLock( array $paths, $type );
 114
 115         /**
 116          * Unlock resources with the given keys and lock type
 117          *
 118          * @param $paths Array List of storage paths
 119          * @param $type integer LockManager::LOCK_* constant
 120          * @return string
 121          */
 122         abstract protected function doUnlock( array $paths, $type );
 123 }
 124
 125 /**
 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.
 128  *
 129  * @ingroup LockManager
 130  * @since 1.20
 131  */
 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, ...))
 135
 136         /**
 137          * @see LockManager::doLock()
 138          * @param $paths array
 139          * @param $type int
 140          * @return Status
 141          */
 142         final protected function doLock( array $paths, $type ) {
 143                 $status = Status::newGood();
 144
 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;
 152                         } else {
 153                                 $bucket = $this->getBucketFromKey( $path );
 154                                 $pathsToLock[$bucket][] = $path;
 155                         }
 156                 }
 157
 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 ) );
 165                                 return $status;
 166                         }
 167                         // Record these locks as active
 168                         foreach ( $paths as $path ) {
 169                                 $this->locksHeld[$path][$type] = 1; // locked
 170                         }
 171                         // Keep track of what locks were made in this attempt
 172                         $lockedPaths = array_merge( $lockedPaths, $paths );
 173                 }
 174
 175                 return $status;
 176         }
 177
 178         /**
 179          * @see LockManager::doUnlock()
 180          * @param $paths array
 181          * @param $type int
 182          * @return Status
 183          */
 184         final protected function doUnlock( array $paths, $type ) {
 185                 $status = Status::newGood();
 186
 187                 $pathsToUnlock = array();
 188                 foreach ( $paths as $path ) {
 189                         if ( !isset( $this->locksHeld[$path][$type] ) ) {
 190                                 $status->warning( 'lockmanager-notlocked', $path );
 191                         } else {
 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;
 198                                 }
 199                                 if ( !count( $this->locksHeld[$path] ) ) {
 200                                         unset( $this->locksHeld[$path] ); // no SH or EX locks left for key
 201                                 }
 202                         }
 203                 }
 204
 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 ) );
 209                 }
 210                 if ( !count( $this->locksHeld ) ) {
 211                         $status->merge( $this->releaseAllLocks() );
 212                 }
 213
 214                 return $status;
 215         }
 216
 217         /**
 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.
 220          *
 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
 224          * @return Status
 225          */
 226         final protected function doLockingRequestBucket( $bucket, array $paths, $type ) {
 227                 $status = Status::newGood();
 228
 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 ) ) {
 235                                 --$votesLeft;
 236                                 $status->warning( 'lockmanager-fail-svr-acquire', $lockSrv );
 237                                 continue; // server down?
 238                         }
 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
 243                         }
 244                         ++$yesVotes; // success for this peer
 245                         if ( $yesVotes >= $quorum ) {
 246                                 return $status; // lock obtained
 247                         }
 248                         --$votesLeft;
 249                         $votesNeeded = $quorum - $yesVotes;
 250                         if ( $votesNeeded > $votesLeft ) {
 251                                 break; // short-circuit
 252                         }
 253                 }
 254                 // At this point, we must not have met the quorum
 255                 $status->setResult( false );
 256
 257                 return $status;
 258         }
 259
 260         /**
 261          * Attempt to release locks with the peers for a bucket
 262          *
 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
 266          * @return Status
 267          */
 268         final protected function doUnlockingRequestBucket( $bucket, array $paths, $type ) {
 269                 $status = Status::newGood();
 270
 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
 275                         } else {
 276                                 $status->merge( $this->freeLocksOnServer( $lockSrv, $paths, $type ) );
 277                         }
 278                 }
 279
 280                 return $status;
 281         }
 282
 283         /**
 284          * Get the bucket for resource path.
 285          * This should avoid throwing any exceptions.
 286          *
 287          * @param $path string
 288          * @return integer
 289          */
 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 );
 293         }
 294
 295         /**
 296          * Check if a lock server is up
 297          *
 298          * @param $lockSrv string
 299          * @return bool
 300          */
 301         abstract protected function isServerUp( $lockSrv );
 302
 303         /**
 304          * Get a connection to a lock server and acquire locks on $paths
 305          *
 306          * @param $lockSrv string
 307          * @param $paths array
 308          * @param $type integer
 309          * @return Status
 310          */
 311         abstract protected function getLocksOnServer( $lockSrv, array $paths, $type );
 312
 313         /**
 314          * Get a connection to a lock server and release locks on $paths.
 315          *
 316          * Subclasses must effectively implement this or releaseAllLocks().
 317          *
 318          * @param $lockSrv string
 319          * @param $paths array
 320          * @param $type integer
 321          * @return Status
 322          */
 323         abstract protected function freeLocksOnServer( $lockSrv, array $paths, $type );
 324
 325         /**
 326          * Release all locks that this session is holding.
 327          *
 328          * Subclasses must effectively implement this or freeLocksOnServer().
 329          *
 330          * @return Status
 331          */
 332         abstract protected function releaseAllLocks();
 333 }
 334
 335 /**
 336  * Simple version of LockManager that does nothing
 337  * @since 1.19
 338  */
 339 class NullLockManager extends LockManager {
 340         /**
 341          * @see LockManager::doLock()
 342          * @param $paths array
 343          * @param $type int
 344          * @return Status
 345          */
 346         protected function doLock( array $paths, $type ) {
 347                 return Status::newGood();
 348         }
 349
 350         /**
 351          * @see LockManager::doUnlock()
 352          * @param $paths array
 353          * @param $type int
 354          * @return Status
 355          */
 356         protected function doUnlock( array $paths, $type ) {
 357                 return Status::newGood();
 358         }
 359 }