MediaWiki  1.23.2
UIDGenerator.php
Go to the documentation of this file.
1 <?php
29 class UIDGenerator {
31  protected static $instance = null;
32 
33  protected $nodeIdFile; // string; local file path
34  protected $nodeId32; // string; node ID in binary (32 bits)
35  protected $nodeId48; // string; node ID in binary (48 bits)
36 
37  protected $lockFile88; // string; local file path
38  protected $lockFile128; // string; local file path
39 
41  protected $fileHandles = array(); // cache file handles
42 
43  const QUICK_RAND = 1; // get randomness from fast and insecure sources
44  const QUICK_VOLATILE = 2; // use an APC like in-memory counter if available
45 
46  protected function __construct() {
47  $this->nodeIdFile = wfTempDir() . '/mw-' . __CLASS__ . '-UID-nodeid';
48  $nodeId = '';
49  if ( is_file( $this->nodeIdFile ) ) {
50  $nodeId = file_get_contents( $this->nodeIdFile );
51  }
52  // Try to get some ID that uniquely identifies this machine (RFC 4122)...
53  if ( !preg_match( '/^[0-9a-f]{12}$/i', $nodeId ) ) {
55  if ( wfIsWindows() ) {
56  // http://technet.microsoft.com/en-us/library/bb490913.aspx
57  $csv = trim( wfShellExec( 'getmac /NH /FO CSV' ) );
58  $line = substr( $csv, 0, strcspn( $csv, "\n" ) );
59  $info = str_getcsv( $line );
60  $nodeId = isset( $info[0] ) ? str_replace( '-', '', $info[0] ) : '';
61  } elseif ( is_executable( '/sbin/ifconfig' ) ) { // Linux/BSD/Solaris/OS X
62  // See http://linux.die.net/man/8/ifconfig
63  $m = array();
64  preg_match( '/\s([0-9a-f]{2}(:[0-9a-f]{2}){5})\s/',
65  wfShellExec( '/sbin/ifconfig -a' ), $m );
66  $nodeId = isset( $m[1] ) ? str_replace( ':', '', $m[1] ) : '';
67  }
69  if ( !preg_match( '/^[0-9a-f]{12}$/i', $nodeId ) ) {
70  $nodeId = MWCryptRand::generateHex( 12, true );
71  $nodeId[1] = dechex( hexdec( $nodeId[1] ) | 0x1 ); // set multicast bit
72  }
73  file_put_contents( $this->nodeIdFile, $nodeId ); // cache
74  }
75  $this->nodeId32 = wfBaseConvert( substr( sha1( $nodeId ), 0, 8 ), 16, 2, 32 );
76  $this->nodeId48 = wfBaseConvert( $nodeId, 16, 2, 48 );
77  // If different processes run as different users, they may have different temp dirs.
78  // This is dealt with by initializing the clock sequence number and counters randomly.
79  $this->lockFile88 = wfTempDir() . '/mw-' . __CLASS__ . '-UID-88';
80  $this->lockFile128 = wfTempDir() . '/mw-' . __CLASS__ . '-UID-128';
81  }
82 
86  protected static function singleton() {
87  if ( self::$instance === null ) {
88  self::$instance = new self();
89  }
90 
91  return self::$instance;
92  }
93 
109  public static function newTimestampedUID88( $base = 10 ) {
110  if ( !is_integer( $base ) || $base > 36 || $base < 2 ) {
111  throw new MWException( "Base must an integer be between 2 and 36" );
112  }
113  $gen = self::singleton();
114  $time = $gen->getTimestampAndDelay( 'lockFile88', 1, 1024 );
115 
116  return wfBaseConvert( $gen->getTimestampedID88( $time ), 2, $base );
117  }
118 
123  protected function getTimestampedID88( array $info ) {
124  list( $time, $counter ) = $info;
125  // Take the 46 MSBs of "milliseconds since epoch"
126  $id_bin = $this->millisecondsSinceEpochBinary( $time );
127  // Add a 10 bit counter resulting in 56 bits total
128  $id_bin .= str_pad( decbin( $counter ), 10, '0', STR_PAD_LEFT );
129  // Add the 32 bit node ID resulting in 88 bits total
130  $id_bin .= $this->nodeId32;
131  // Convert to a 1-27 digit integer string
132  if ( strlen( $id_bin ) !== 88 ) {
133  throw new MWException( "Detected overflow for millisecond timestamp." );
134  }
135 
136  return $id_bin;
137  }
138 
153  public static function newTimestampedUID128( $base = 10 ) {
154  if ( !is_integer( $base ) || $base > 36 || $base < 2 ) {
155  throw new MWException( "Base must be an integer between 2 and 36" );
156  }
157  $gen = self::singleton();
158  $time = $gen->getTimestampAndDelay( 'lockFile128', 16384, 1048576 );
159 
160  return wfBaseConvert( $gen->getTimestampedID128( $time ), 2, $base );
161  }
162 
167  protected function getTimestampedID128( array $info ) {
168  list( $time, $counter, $clkSeq ) = $info;
169  // Take the 46 MSBs of "milliseconds since epoch"
170  $id_bin = $this->millisecondsSinceEpochBinary( $time );
171  // Add a 20 bit counter resulting in 66 bits total
172  $id_bin .= str_pad( decbin( $counter ), 20, '0', STR_PAD_LEFT );
173  // Add a 14 bit clock sequence number resulting in 80 bits total
174  $id_bin .= str_pad( decbin( $clkSeq ), 14, '0', STR_PAD_LEFT );
175  // Add the 48 bit node ID resulting in 128 bits total
176  $id_bin .= $this->nodeId48;
177  // Convert to a 1-39 digit integer string
178  if ( strlen( $id_bin ) !== 128 ) {
179  throw new MWException( "Detected overflow for millisecond timestamp." );
180  }
181 
182  return $id_bin;
183  }
184 
192  public static function newUUIDv4( $flags = 0 ) {
193  $hex = ( $flags & self::QUICK_RAND )
194  ? wfRandomString( 31 )
195  : MWCryptRand::generateHex( 31 );
196 
197  return sprintf( '%s-%s-%s-%s-%s',
198  // "time_low" (32 bits)
199  substr( $hex, 0, 8 ),
200  // "time_mid" (16 bits)
201  substr( $hex, 8, 4 ),
202  // "time_hi_and_version" (16 bits)
203  '4' . substr( $hex, 12, 3 ),
204  // "clk_seq_hi_res (8 bits, variant is binary 10x) and "clk_seq_low" (8 bits)
205  dechex( 0x8 | ( hexdec( $hex[15] ) & 0x3 ) ) . $hex[16] . substr( $hex, 17, 2 ),
206  // "node" (48 bits)
207  substr( $hex, 19, 12 )
208  );
209  }
210 
218  public static function newRawUUIDv4( $flags = 0 ) {
219  return str_replace( '-', '', self::newUUIDv4( $flags ) );
220  }
221 
234  public static function newSequentialPerNodeID( $bucket, $bits = 48, $flags = 0 ) {
235  return current( self::newSequentialPerNodeIDs( $bucket, $bits, 1, $flags ) );
236  }
237 
249  public static function newSequentialPerNodeIDs( $bucket, $bits, $count, $flags = 0 ) {
250  $gen = self::singleton();
251  return $gen->getSequentialPerNodeIDs( $bucket, $bits, $count, $flags );
252  }
253 
264  protected function getSequentialPerNodeIDs( $bucket, $bits, $count, $flags ) {
265  if ( $count <= 0 ) {
266  return array(); // nothing to do
267  } elseif ( $count > 10000 ) {
268  throw new MWException( "Number of requested IDs ($count) is too high." );
269  } elseif ( $bits < 16 || $bits > 48 ) {
270  throw new MWException( "Requested bit size ($bits) is out of range." );
271  }
272 
273  $counter = null; // post-increment persistent counter value
274 
275  // Use APC/eAccelerator/xcache if requested, available, and not in CLI mode;
276  // Counter values would not survive accross script instances in CLI mode.
277  $cache = null;
278  if ( ( $flags & self::QUICK_VOLATILE ) && PHP_SAPI !== 'cli' ) {
279  try {
281  } catch ( MWException $e ) {} // not supported
282  }
283  if ( $cache ) {
284  $counter = $cache->incr( $bucket, $count );
285  if ( $counter === false ) {
286  if ( !$cache->add( $bucket, $count ) ) {
287  throw new MWException( 'Unable to set value to ' . get_class( $cache ) );
288  }
289  $counter = $count;
290  }
291  }
292 
293  // Note: use of fmod() avoids "division by zero" on 32 bit machines
294  if ( $counter === null ) {
295  $path = wfTempDir() . '/mw-' . __CLASS__ . '-' . rawurlencode( $bucket ) . '-48';
296  // Get the UID lock file handle
297  if ( isset( $this->fileHandles[$path] ) ) {
298  $handle = $this->fileHandles[$path];
299  } else {
300  $handle = fopen( $path, 'cb+' );
301  $this->fileHandles[$path] = $handle ?: null; // cache
302  }
303  // Acquire the UID lock file
304  if ( $handle === false ) {
305  throw new MWException( "Could not open '{$path}'." );
306  } elseif ( !flock( $handle, LOCK_EX ) ) {
307  fclose( $handle );
308  throw new MWException( "Could not acquire '{$path}'." );
309  }
310  // Fetch the counter value and increment it...
311  rewind( $handle );
312  $counter = floor( trim( fgets( $handle ) ) ) + $count; // fetch as float
313  // Write back the new counter value
314  ftruncate( $handle, 0 );
315  rewind( $handle );
316  fwrite( $handle, fmod( $counter, pow( 2, 48 ) ) ); // warp-around as needed
317  fflush( $handle );
318  // Release the UID lock file
319  flock( $handle, LOCK_UN );
320  }
321 
322  $ids = array();
323  $divisor = pow( 2, $bits );
324  $currentId = floor( $counter - $count ); // pre-increment counter value
325  for ( $i = 0; $i < $count; ++$i ) {
326  $ids[] = fmod( ++$currentId, $divisor );
327  }
328 
329  return $ids;
330  }
331 
343  protected function getTimestampAndDelay( $lockFile, $clockSeqSize, $counterSize ) {
344  // Get the UID lock file handle
345  $path = $this->$lockFile;
346  if ( isset( $this->fileHandles[$path] ) ) {
347  $handle = $this->fileHandles[$path];
348  } else {
349  $handle = fopen( $path, 'cb+' );
350  $this->fileHandles[$path] = $handle ?: null; // cache
351  }
352  // Acquire the UID lock file
353  if ( $handle === false ) {
354  throw new MWException( "Could not open '{$this->$lockFile}'." );
355  } elseif ( !flock( $handle, LOCK_EX ) ) {
356  fclose( $handle );
357  throw new MWException( "Could not acquire '{$this->$lockFile}'." );
358  }
359  // Get the current timestamp, clock sequence number, last time, and counter
360  rewind( $handle );
361  $data = explode( ' ', fgets( $handle ) ); // "<clk seq> <sec> <msec> <counter> <offset>"
362  $clockChanged = false; // clock set back significantly?
363  if ( count( $data ) == 5 ) { // last UID info already initialized
364  $clkSeq = (int)$data[0] % $clockSeqSize;
365  $prevTime = array( (int)$data[1], (int)$data[2] );
366  $offset = (int)$data[4] % $counterSize; // random counter offset
367  $counter = 0; // counter for UIDs with the same timestamp
368  // Delay until the clock reaches the time of the last ID.
369  // This detects any microtime() drift among processes.
370  $time = $this->timeWaitUntil( $prevTime );
371  if ( !$time ) { // too long to delay?
372  $clockChanged = true; // bump clock sequence number
374  } elseif ( $time == $prevTime ) {
375  // Bump the counter if there are timestamp collisions
376  $counter = (int)$data[3] % $counterSize;
377  if ( ++$counter >= $counterSize ) { // sanity (starts at 0)
378  flock( $handle, LOCK_UN ); // abort
379  throw new MWException( "Counter overflow for timestamp value." );
380  }
381  }
382  } else { // last UID info not initialized
383  $clkSeq = mt_rand( 0, $clockSeqSize - 1 );
384  $counter = 0;
385  $offset = mt_rand( 0, $counterSize - 1 );
387  }
388  // microtime() and gettimeofday() can drift from time() at least on Windows.
389  // The drift is immediate for processes running while the system clock changes.
390  // time() does not have this problem. See https://bugs.php.net/bug.php?id=42659.
391  if ( abs( time() - $time[0] ) >= 2 ) {
392  // We don't want processes using too high or low timestamps to avoid duplicate
393  // UIDs and clock sequence number churn. This process should just be restarted.
394  flock( $handle, LOCK_UN ); // abort
395  throw new MWException( "Process clock is outdated or drifted." );
396  }
397  // If microtime() is synced and a clock change was detected, then the clock went back
398  if ( $clockChanged ) {
399  // Bump the clock sequence number and also randomize the counter offset,
400  // which is useful for UIDs that do not include the clock sequence number.
401  $clkSeq = ( $clkSeq + 1 ) % $clockSeqSize;
402  $offset = mt_rand( 0, $counterSize - 1 );
403  trigger_error( "Clock was set back; sequence number incremented." );
404  }
405  // Update the (clock sequence number, timestamp, counter)
406  ftruncate( $handle, 0 );
407  rewind( $handle );
408  fwrite( $handle, "{$clkSeq} {$time[0]} {$time[1]} {$counter} {$offset}" );
409  fflush( $handle );
410  // Release the UID lock file
411  flock( $handle, LOCK_UN );
412 
413  return array( $time, ( $counter + $offset ) % $counterSize, $clkSeq );
414  }
415 
423  protected function timeWaitUntil( array $time ) {
424  do {
425  $ct = self::millitime();
426  if ( $ct >= $time ) { // http://php.net/manual/en/language.operators.comparison.php
427  return $ct; // current timestamp is higher than $time
428  }
429  } while ( ( ( $time[0] - $ct[0] ) * 1000 + ( $time[1] - $ct[1] ) ) <= 10 );
430 
431  return false;
432  }
433 
438  protected function millisecondsSinceEpochBinary( array $time ) {
439  list( $sec, $msec ) = $time;
440  $ts = 1000 * $sec + $msec;
441  if ( $ts > pow( 2, 52 ) ) {
442  throw new MWException( __METHOD__ .
443  ': sorry, this function doesn\'t work after the year 144680' );
444  }
445 
446  return substr( wfBaseConvert( $ts, 10, 2, 46 ), -46 );
447  }
448 
452  protected static function millitime() {
453  list( $msec, $sec ) = explode( ' ', microtime() );
454 
455  return array( (int)$sec, (int)( $msec * 1000 ) );
456  }
457 
469  protected function deleteCacheFiles() {
470  // Bug: 44850
471  foreach ( $this->fileHandles as $path => $handle ) {
472  if ( $handle !== null ) {
473  fclose( $handle );
474  }
475  if ( is_file( $path ) ) {
476  unlink( $path );
477  }
478  unset( $this->fileHandles[$path] );
479  }
480  if ( is_file( $this->nodeIdFile ) ) {
481  unlink( $this->nodeIdFile );
482  }
483  }
484 
496  public static function unitTestTearDown() {
497  // Bug: 44850
498  $gen = self::singleton();
499  $gen->deleteCacheFiles();
500  }
501 
502  function __destruct() {
503  array_map( 'fclose', array_filter( $this->fileHandles ) );
504  }
505 }
UIDGenerator\$nodeId32
$nodeId32
Definition: UIDGenerator.php:34
UIDGenerator\newTimestampedUID128
static newTimestampedUID128( $base=10)
Get a statistically unique 128-bit unsigned integer ID string.
Definition: UIDGenerator.php:152
$time
see documentation in includes Linker php for Linker::makeImageLink & $time
Definition: hooks.txt:1358
UIDGenerator\QUICK_RAND
const QUICK_RAND
Definition: UIDGenerator.php:42
wfShellExec
wfShellExec( $cmd, &$retval=null, $environ=array(), $limits=array(), $options=array())
Execute a shell command, with time and memory limits mirrored from the PHP configuration if supported...
Definition: GlobalFunctions.php:2804
php
skin txt MediaWiki includes four core it has been set as the default in MediaWiki since the replacing Monobook it had been been the default skin since before being replaced by Vector largely rewritten in while keeping its appearance Several legacy skins were removed in the as the burden of supporting them became too heavy to bear Those in etc for skin dependent CSS etc for skin dependent JavaScript These can also be customised on a per user by etc This feature has led to a wide variety of user styles becoming that gallery is a good place to ending in php
Definition: skin.txt:62
UIDGenerator\getTimestampedID128
getTimestampedID128(array $info)
Definition: UIDGenerator.php:166
UIDGenerator\getTimestampAndDelay
getTimestampAndDelay( $lockFile, $clockSeqSize, $counterSize)
Get a (time,counter,clock sequence) where (time,counter) is higher than any previous (time,...
Definition: UIDGenerator.php:342
UIDGenerator\$instance
static $instance
Definition: UIDGenerator.php:31
wfSuppressWarnings
wfSuppressWarnings( $end=false)
Reference-counted warning suppression.
Definition: GlobalFunctions.php:2387
UIDGenerator\$fileHandles
Array $fileHandles
Definition: UIDGenerator.php:40
MWCryptRand\generateHex
static generateHex( $chars, $forceStrong=false)
Generate a run of (ideally) cryptographically random data and return it in hexadecimal string format.
Definition: MWCryptRand.php:514
UIDGenerator
Class for getting statistically unique IDs.
Definition: UIDGenerator.php:29
$flags
it s the revision text itself In either if gzip is the revision text is gzipped $flags
Definition: hooks.txt:2113
UIDGenerator\$nodeId48
$nodeId48
Definition: UIDGenerator.php:35
UIDGenerator\getSequentialPerNodeIDs
getSequentialPerNodeIDs( $bucket, $bits, $count, $flags)
Return IDs that are sequential only for this node and bucket.
Definition: UIDGenerator.php:263
UIDGenerator\newRawUUIDv4
static newRawUUIDv4( $flags=0)
Return an RFC4122 compliant v4 UUID.
Definition: UIDGenerator.php:217
UIDGenerator\newSequentialPerNodeID
static newSequentialPerNodeID( $bucket, $bits=48, $flags=0)
Return an ID that is sequential only for this node and bucket.
Definition: UIDGenerator.php:233
UIDGenerator\millisecondsSinceEpochBinary
millisecondsSinceEpochBinary(array $time)
Definition: UIDGenerator.php:437
MWException
MediaWiki exception.
Definition: MWException.php:26
wfRestoreWarnings
wfRestoreWarnings()
Restore error level to previous value.
Definition: GlobalFunctions.php:2417
UIDGenerator\deleteCacheFiles
deleteCacheFiles()
Delete all cache files that have been created.
Definition: UIDGenerator.php:468
UIDGenerator\$lockFile128
$lockFile128
Definition: UIDGenerator.php:38
array
the array() calling protocol came about after MediaWiki 1.4rc1.
List of Api Query prop modules.
list
deferred txt A few of the database updates required by various functions here can be deferred until after the result page is displayed to the user For updating the view updating the linked to tables after a etc PHP does not yet have any way to tell the server to actually return and disconnect while still running these but it might have such a feature in the future We handle these by creating a deferred update object and putting those objects on a global list
Definition: deferred.txt:11
$line
$line
Definition: cdb.php:57
UIDGenerator\millitime
static millitime()
Definition: UIDGenerator.php:451
UIDGenerator\newTimestampedUID88
static newTimestampedUID88( $base=10)
Get a statistically unique 88-bit unsigned integer ID string.
Definition: UIDGenerator.php:108
UIDGenerator\newUUIDv4
static newUUIDv4( $flags=0)
Return an RFC4122 compliant v4 UUID.
Definition: UIDGenerator.php:191
UIDGenerator\unitTestTearDown
static unitTestTearDown()
Cleanup resources when tearing down after a unit test.
Definition: UIDGenerator.php:495
wfIsWindows
wfIsWindows()
Check if the operating system is Windows.
Definition: GlobalFunctions.php:2524
UIDGenerator\singleton
static singleton()
Definition: UIDGenerator.php:85
UIDGenerator\__construct
__construct()
Definition: UIDGenerator.php:45
UIDGenerator\$lockFile88
$lockFile88
Definition: UIDGenerator.php:37
ObjectCache\newAccelerator
static newAccelerator( $params)
Factory function referenced from DefaultSettings.php for CACHE_ACCEL.
Definition: ObjectCache.php:125
UIDGenerator\getTimestampedID88
getTimestampedID88(array $info)
Definition: UIDGenerator.php:122
$count
$count
Definition: UtfNormalTest2.php:96
wfTempDir
wfTempDir()
Tries to get the system directory for temporary files.
Definition: GlobalFunctions.php:2564
$cache
$cache
Definition: mcc.php:32
wfBaseConvert
wfBaseConvert( $input, $sourceBase, $destBase, $pad=1, $lowercase=true, $engine='auto')
Convert an arbitrarily-long digit string from one numeric base to another, optionally zero-padding to...
Definition: GlobalFunctions.php:3368
$path
$path
Definition: NoLocalSettings.php:35
as
This document is intended to provide useful advice for parties seeking to redistribute MediaWiki to end users It s targeted particularly at maintainers for Linux since it s been observed that distribution packages of MediaWiki often break We ve consistently had to recommend that users seeking support use official tarballs instead of their distribution s and this often solves whatever problem the user is having It would be nice if this could such as
Definition: distributors.txt:9
UIDGenerator\QUICK_VOLATILE
const QUICK_VOLATILE
Definition: UIDGenerator.php:43
UIDGenerator\newSequentialPerNodeIDs
static newSequentialPerNodeIDs( $bucket, $bits, $count, $flags=0)
Return IDs that are sequential only for this node and bucket.
Definition: UIDGenerator.php:248
$e
if( $useReadline) $e
Definition: eval.php:66
UIDGenerator\$nodeIdFile
$nodeIdFile
Definition: UIDGenerator.php:33
UIDGenerator\timeWaitUntil
timeWaitUntil(array $time)
Wait till the current timestamp reaches $time and return the current timestamp.
Definition: UIDGenerator.php:422
UIDGenerator\__destruct
__destruct()
Definition: UIDGenerator.php:501
wfRandomString
wfRandomString( $length=32)
Get a random string containing a number of pseudo-random hex characters.
Definition: GlobalFunctions.php:300