MediaWiki  REL1_22
UIDGenerator.php
Go to the documentation of this file.
00001 <?php
00029 class UIDGenerator {
00031     protected static $instance = null;
00032 
00033     protected $nodeId32; // string; node ID in binary (32 bits)
00034     protected $nodeId48; // string; node ID in binary (48 bits)
00035 
00036     protected $lockFile88; // string; local file path
00037     protected $lockFile128; // string; local file path
00038 
00040     protected $fileHandles = array(); // cache file handles
00041 
00042     const QUICK_RAND = 1; // get randomness from fast and insecure sources
00043 
00044     protected function __construct() {
00045         $idFile = wfTempDir() . '/mw-' . __CLASS__ . '-UID-nodeid';
00046         $nodeId = is_file( $idFile ) ? file_get_contents( $idFile ) : '';
00047         // Try to get some ID that uniquely identifies this machine (RFC 4122)...
00048         if ( !preg_match( '/^[0-9a-f]{12}$/i', $nodeId ) ) {
00049             wfSuppressWarnings();
00050             if ( wfIsWindows() ) {
00051                 // http://technet.microsoft.com/en-us/library/bb490913.aspx
00052                 $csv = trim( wfShellExec( 'getmac /NH /FO CSV' ) );
00053                 $line = substr( $csv, 0, strcspn( $csv, "\n" ) );
00054                 $info = str_getcsv( $line );
00055                 $nodeId = isset( $info[0] ) ? str_replace( '-', '', $info[0] ) : '';
00056             } elseif ( is_executable( '/sbin/ifconfig' ) ) { // Linux/BSD/Solaris/OS X
00057                 // See http://linux.die.net/man/8/ifconfig
00058                 $m = array();
00059                 preg_match( '/\s([0-9a-f]{2}(:[0-9a-f]{2}){5})\s/',
00060                     wfShellExec( '/sbin/ifconfig -a' ), $m );
00061                 $nodeId = isset( $m[1] ) ? str_replace( ':', '', $m[1] ) : '';
00062             }
00063             wfRestoreWarnings();
00064             if ( !preg_match( '/^[0-9a-f]{12}$/i', $nodeId ) ) {
00065                 $nodeId = MWCryptRand::generateHex( 12, true );
00066                 $nodeId[1] = dechex( hexdec( $nodeId[1] ) | 0x1 ); // set multicast bit
00067             }
00068             file_put_contents( $idFile, $nodeId ); // cache
00069         }
00070         $this->nodeId32 = wfBaseConvert( substr( sha1( $nodeId ), 0, 8 ), 16, 2, 32 );
00071         $this->nodeId48 = wfBaseConvert( $nodeId, 16, 2, 48 );
00072         // If different processes run as different users, they may have different temp dirs.
00073         // This is dealt with by initializing the clock sequence number and counters randomly.
00074         $this->lockFile88 = wfTempDir() . '/mw-' . __CLASS__ . '-UID-88';
00075         $this->lockFile128 = wfTempDir() . '/mw-' . __CLASS__ . '-UID-128';
00076     }
00077 
00081     protected static function singleton() {
00082         if ( self::$instance === null ) {
00083             self::$instance = new self();
00084         }
00085         return self::$instance;
00086     }
00087 
00103     public static function newTimestampedUID88( $base = 10 ) {
00104         if ( !is_integer( $base ) || $base > 36 || $base < 2 ) {
00105             throw new MWException( "Base must an integer be between 2 and 36" );
00106         }
00107         $gen = self::singleton();
00108         $time = $gen->getTimestampAndDelay( 'lockFile88', 1, 1024 );
00109         return wfBaseConvert( $gen->getTimestampedID88( $time ), 2, $base );
00110     }
00111 
00116     protected function getTimestampedID88( array $info ) {
00117         list( $time, $counter ) = $info;
00118         // Take the 46 MSBs of "milliseconds since epoch"
00119         $id_bin = $this->millisecondsSinceEpochBinary( $time );
00120         // Add a 10 bit counter resulting in 56 bits total
00121         $id_bin .= str_pad( decbin( $counter ), 10, '0', STR_PAD_LEFT );
00122         // Add the 32 bit node ID resulting in 88 bits total
00123         $id_bin .= $this->nodeId32;
00124         // Convert to a 1-27 digit integer string
00125         if ( strlen( $id_bin ) !== 88 ) {
00126             throw new MWException( "Detected overflow for millisecond timestamp." );
00127         }
00128         return $id_bin;
00129     }
00130 
00145     public static function newTimestampedUID128( $base = 10 ) {
00146         if ( !is_integer( $base ) || $base > 36 || $base < 2 ) {
00147             throw new MWException( "Base must be an integer between 2 and 36" );
00148         }
00149         $gen = self::singleton();
00150         $time = $gen->getTimestampAndDelay( 'lockFile128', 16384, 1048576 );
00151         return wfBaseConvert( $gen->getTimestampedID128( $time ), 2, $base );
00152     }
00153 
00158     protected function getTimestampedID128( array $info ) {
00159         list( $time, $counter, $clkSeq ) = $info;
00160         // Take the 46 MSBs of "milliseconds since epoch"
00161         $id_bin = $this->millisecondsSinceEpochBinary( $time );
00162         // Add a 20 bit counter resulting in 66 bits total
00163         $id_bin .= str_pad( decbin( $counter ), 20, '0', STR_PAD_LEFT );
00164         // Add a 14 bit clock sequence number resulting in 80 bits total
00165         $id_bin .= str_pad( decbin( $clkSeq ), 14, '0', STR_PAD_LEFT );
00166         // Add the 48 bit node ID resulting in 128 bits total
00167         $id_bin .= $this->nodeId48;
00168         // Convert to a 1-39 digit integer string
00169         if ( strlen( $id_bin ) !== 128 ) {
00170             throw new MWException( "Detected overflow for millisecond timestamp." );
00171         }
00172         return $id_bin;
00173     }
00174 
00182     public static function newUUIDv4( $flags = 0 ) {
00183         $hex = ( $flags & self::QUICK_RAND )
00184             ? wfRandomString( 31 )
00185             : MWCryptRand::generateHex( 31 );
00186 
00187         return sprintf( '%s-%s-%s-%s-%s',
00188             // "time_low" (32 bits)
00189             substr( $hex, 0, 8 ),
00190             // "time_mid" (16 bits)
00191             substr( $hex, 8, 4 ),
00192             // "time_hi_and_version" (16 bits)
00193             '4' . substr( $hex, 12, 3 ),
00194             // "clk_seq_hi_res (8 bits, variant is binary 10x) and "clk_seq_low" (8 bits)
00195             dechex( 0x8 | ( hexdec( $hex[15] ) & 0x3 ) ) . $hex[16] . substr( $hex, 17, 2 ),
00196             // "node" (48 bits)
00197             substr( $hex, 19, 12 )
00198         );
00199     }
00200 
00208     public static function newRawUUIDv4( $flags = 0 ) {
00209         return str_replace( '-', '', self::newUUIDv4( $flags ) );
00210     }
00211 
00223     protected function getTimestampAndDelay( $lockFile, $clockSeqSize, $counterSize ) {
00224         // Get the UID lock file handle
00225         if ( isset( $this->fileHandles[$lockFile] ) ) {
00226             $handle = $this->fileHandles[$lockFile];
00227         } else {
00228             $handle = fopen( $this->$lockFile, 'cb+' );
00229             $this->fileHandles[$lockFile] = $handle ?: null; // cache
00230         }
00231         // Acquire the UID lock file
00232         if ( $handle === false ) {
00233             throw new MWException( "Could not open '{$this->$lockFile}'." );
00234         } elseif ( !flock( $handle, LOCK_EX ) ) {
00235             throw new MWException( "Could not acquire '{$this->$lockFile}'." );
00236         }
00237         // Get the current timestamp, clock sequence number, last time, and counter
00238         rewind( $handle );
00239         $data = explode( ' ', fgets( $handle ) ); // "<clk seq> <sec> <msec> <counter> <offset>"
00240         $clockChanged = false; // clock set back significantly?
00241         if ( count( $data ) == 5 ) { // last UID info already initialized
00242             $clkSeq = (int)$data[0] % $clockSeqSize;
00243             $prevTime = array( (int)$data[1], (int)$data[2] );
00244             $offset = (int)$data[4] % $counterSize; // random counter offset
00245             $counter = 0; // counter for UIDs with the same timestamp
00246             // Delay until the clock reaches the time of the last ID.
00247             // This detects any microtime() drift among processes.
00248             $time = $this->timeWaitUntil( $prevTime );
00249             if ( !$time ) { // too long to delay?
00250                 $clockChanged = true; // bump clock sequence number
00251                 $time = self::millitime();
00252             } elseif ( $time == $prevTime ) {
00253                 // Bump the counter if there are timestamp collisions
00254                 $counter = (int)$data[3] % $counterSize;
00255                 if ( ++$counter >= $counterSize ) { // sanity (starts at 0)
00256                     flock( $handle, LOCK_UN ); // abort
00257                     throw new MWException( "Counter overflow for timestamp value." );
00258                 }
00259             }
00260         } else { // last UID info not initialized
00261             $clkSeq = mt_rand( 0, $clockSeqSize - 1 );
00262             $counter = 0;
00263             $offset = mt_rand( 0, $counterSize - 1 );
00264             $time = self::millitime();
00265         }
00266         // microtime() and gettimeofday() can drift from time() at least on Windows.
00267         // The drift is immediate for processes running while the system clock changes.
00268         // time() does not have this problem. See https://bugs.php.net/bug.php?id=42659.
00269         if ( abs( time() - $time[0] ) >= 2 ) {
00270             // We don't want processes using too high or low timestamps to avoid duplicate
00271             // UIDs and clock sequence number churn. This process should just be restarted.
00272             flock( $handle, LOCK_UN ); // abort
00273             throw new MWException( "Process clock is outdated or drifted." );
00274         }
00275         // If microtime() is synced and a clock change was detected, then the clock went back
00276         if ( $clockChanged ) {
00277             // Bump the clock sequence number and also randomize the counter offset,
00278             // which is useful for UIDs that do not include the clock sequence number.
00279             $clkSeq = ( $clkSeq + 1 ) % $clockSeqSize;
00280             $offset = mt_rand( 0, $counterSize - 1 );
00281             trigger_error( "Clock was set back; sequence number incremented." );
00282         }
00283         // Update the (clock sequence number, timestamp, counter)
00284         ftruncate( $handle, 0 );
00285         rewind( $handle );
00286         fwrite( $handle, "{$clkSeq} {$time[0]} {$time[1]} {$counter} {$offset}" );
00287         fflush( $handle );
00288         // Release the UID lock file
00289         flock( $handle, LOCK_UN );
00290 
00291         return array( $time, ( $counter + $offset ) % $counterSize, $clkSeq );
00292     }
00293 
00301     protected function timeWaitUntil( array $time ) {
00302         do {
00303             $ct = self::millitime();
00304             if ( $ct >= $time ) { // http://php.net/manual/en/language.operators.comparison.php
00305                 return $ct; // current timestamp is higher than $time
00306             }
00307         } while ( ( ( $time[0] - $ct[0] ) * 1000 + ( $time[1] - $ct[1] ) ) <= 10 );
00308 
00309         return false;
00310     }
00311 
00316     protected function millisecondsSinceEpochBinary( array $time ) {
00317         list( $sec, $msec ) = $time;
00318         $ts = 1000 * $sec + $msec;
00319         if ( $ts > pow( 2, 52 ) ) {
00320             throw new MWException( __METHOD__ .
00321                 ': sorry, this function doesn\'t work after the year 144680' );
00322         }
00323         return substr( wfBaseConvert( $ts, 10, 2, 46 ), -46 );
00324     }
00325 
00329     protected static function millitime() {
00330         list( $msec, $sec ) = explode( ' ', microtime() );
00331         return array( (int)$sec, (int)( $msec * 1000 ) );
00332     }
00333 
00334     function __destruct() {
00335         array_map( 'fclose', $this->fileHandles );
00336     }
00337 }