includes/HistoryBlob.php

   1 <?php
   2
   3 /**
   4  * Base class for general text storage via the "object" flag in old_flags, or
   5  * two-part external storage URLs. Used for represent efficient concatenated
   6  * storage, and migration-related pointer objects.
   7  */
   8 interface HistoryBlob
   9 {
  10         /**
  11          * Adds an item of text, returns a stub object which points to the item.
  12          * You must call setLocation() on the stub object before storing it to the
  13          * database
  14          *
  15          * @param $text string
  16          *
  17          * @return String: the key for getItem()
  18          */
  19         function addItem( $text );
  20
  21         /**
  22          * Get item by key, or false if the key is not present
  23          *
  24          * @param $key string
  25          *
  26          * @return String or false
  27          */
  28         function getItem( $key );
  29
  30         /**
  31          * Set the "default text"
  32          * This concept is an odd property of the current DB schema, whereby each text item has a revision
  33          * associated with it. The default text is the text of the associated revision. There may, however,
  34          * be other revisions in the same object.
  35          *
  36          * Default text is not required for two-part external storage URLs.
  37          *
  38          * @param $text string
  39          */
  40         function setText( $text );
  41
  42         /**
  43          * Get default text. This is called from Revision::getRevisionText()
  44          *
  45          * @return String
  46          */
  47         function getText();
  48 }
  49
  50 /**
  51  * Concatenated gzip (CGZ) storage
  52  * Improves compression ratio by concatenating like objects before gzipping
  53  */
  54 class ConcatenatedGzipHistoryBlob implements HistoryBlob
  55 {
  56         public $mVersion = 0, $mCompressed = false, $mItems = array(), $mDefaultHash = '';
  57         public $mSize = 0;
  58         public $mMaxSize = 10000000;
  59         public $mMaxCount = 100;
  60
  61         /** Constructor */
  62         public function __construct() {
  63                 if ( !function_exists( 'gzdeflate' ) ) {
  64                         throw new MWException( "Need zlib support to read or write this kind of history object (ConcatenatedGzipHistoryBlob)\n" );
  65                 }
  66         }
  67
  68         /**
  69          * @param $text string
  70          * @return string
  71          */
  72         public function addItem( $text ) {
  73                 $this->uncompress();
  74                 $hash = md5( $text );
  75                 if ( !isset( $this->mItems[$hash] ) ) {
  76                         $this->mItems[$hash] = $text;
  77                         $this->mSize += strlen( $text );
  78                 }
  79                 return $hash;
  80         }
  81
  82         /**
  83          * @param $hash string
  84          * @return array|bool
  85          */
  86         public function getItem( $hash ) {
  87                 $this->uncompress();
  88                 if ( array_key_exists( $hash, $this->mItems ) ) {
  89                         return $this->mItems[$hash];
  90                 } else {
  91                         return false;
  92                 }
  93         }
  94
  95         /**
  96          * @param $text string
  97          * @return void
  98          */
  99         public function setText( $text ) {
 100                 $this->uncompress();
 101                 $this->mDefaultHash = $this->addItem( $text );
 102         }
 103
 104         /**
 105          * @return array|bool
 106          */
 107         public function getText() {
 108                 $this->uncompress();
 109                 return $this->getItem( $this->mDefaultHash );
 110         }
 111
 112         /**
 113          * Remove an item
 114          *
 115          * @param $hash string
 116          */
 117         public function removeItem( $hash ) {
 118                 $this->mSize -= strlen( $this->mItems[$hash] );
 119                 unset( $this->mItems[$hash] );
 120         }
 121
 122         /**
 123          * Compress the bulk data in the object
 124          */
 125         public function compress() {
 126                 if ( !$this->mCompressed  ) {
 127                         $this->mItems = gzdeflate( serialize( $this->mItems ) );
 128                         $this->mCompressed = true;
 129                 }
 130         }
 131
 132         /**
 133          * Uncompress bulk data
 134          */
 135         public function uncompress() {
 136                 if ( $this->mCompressed ) {
 137                         $this->mItems = unserialize( gzinflate( $this->mItems ) );
 138                         $this->mCompressed = false;
 139                 }
 140         }
 141
 142         /**
 143          * @return array
 144          */
 145         function __sleep() {
 146                 $this->compress();
 147                 return array( 'mVersion', 'mCompressed', 'mItems', 'mDefaultHash' );
 148         }
 149
 150         function __wakeup() {
 151                 $this->uncompress();
 152         }
 153
 154         /**
 155          * Helper function for compression jobs
 156          * Returns true until the object is "full" and ready to be committed
 157          *
 158          * @return bool
 159          */
 160         public function isHappy() {
 161                 return $this->mSize < $this->mMaxSize
 162                         && count( $this->mItems ) < $this->mMaxCount;
 163         }
 164 }
 165
 166
 167 /**
 168  * Pointer object for an item within a CGZ blob stored in the text table.
 169  */
 170 class HistoryBlobStub {
 171         /**
 172          * One-step cache variable to hold base blobs; operations that
 173          * pull multiple revisions may often pull multiple times from
 174          * the same blob. By keeping the last-used one open, we avoid
 175          * redundant unserialization and decompression overhead.
 176          */
 177         protected static $blobCache = array();
 178
 179         var $mOldId, $mHash, $mRef;
 180
 181         /**
 182          * @param $hash string the content hash of the text
 183          * @param $oldid Integer the old_id for the CGZ object
 184          */
 185         function __construct( $hash = '', $oldid = 0 ) {
 186                 $this->mHash = $hash;
 187         }
 188
 189         /**
 190          * Sets the location (old_id) of the main object to which this object
 191          * points
 192          */
 193         function setLocation( $id ) {
 194                 $this->mOldId = $id;
 195         }
 196
 197         /**
 198          * Sets the location (old_id) of the referring object
 199          */
 200         function setReferrer( $id ) {
 201                 $this->mRef = $id;
 202         }
 203
 204         /**
 205          * Gets the location of the referring object
 206          */
 207         function getReferrer() {
 208                 return $this->mRef;
 209         }
 210
 211         /**
 212          * @return string
 213          */
 214         function getText() {
 215                 $fname = 'HistoryBlobStub::getText';
 216
 217                 if( isset( self::$blobCache[$this->mOldId] ) ) {
 218                         $obj = self::$blobCache[$this->mOldId];
 219                 } else {
 220                         $dbr = wfGetDB( DB_SLAVE );
 221                         $row = $dbr->selectRow( 'text', array( 'old_flags', 'old_text' ), array( 'old_id' => $this->mOldId ) );
 222                         if( !$row ) {
 223                                 return false;
 224                         }
 225                         $flags = explode( ',', $row->old_flags );
 226                         if( in_array( 'external', $flags ) ) {
 227                                 $url=$row->old_text;
 228                                 $parts = explode( '://', $url, 2 );
 229                                 if ( !isset( $parts[1] ) || $parts[1] == '' ) {
 230                                         wfProfileOut( $fname );
 231                                         return false;
 232                                 }
 233                                 $row->old_text = ExternalStore::fetchFromUrl($url);
 234
 235                         }
 236                         if( !in_array( 'object', $flags ) ) {
 237                                 return false;
 238                         }
 239
 240                         if( in_array( 'gzip', $flags ) ) {
 241                                 // This shouldn't happen, but a bug in the compress script
 242                                 // may at times gzip-compress a HistoryBlob object row.
 243                                 $obj = unserialize( gzinflate( $row->old_text ) );
 244                         } else {
 245                                 $obj = unserialize( $row->old_text );
 246                         }
 247
 248                         if( !is_object( $obj ) ) {
 249                                 // Correct for old double-serialization bug.
 250                                 $obj = unserialize( $obj );
 251                         }
 252
 253                         // Save this item for reference; if pulling many
 254                         // items in a row we'll likely use it again.
 255                         $obj->uncompress();
 256                         self::$blobCache = array( $this->mOldId => $obj );
 257                 }
 258                 return $obj->getItem( $this->mHash );
 259         }
 260
 261         /**
 262          * Get the content hash
 263          *
 264          * @return string
 265          */
 266         function getHash() {
 267                 return $this->mHash;
 268         }
 269 }
 270
 271
 272 /**
 273  * To speed up conversion from 1.4 to 1.5 schema, text rows can refer to the
 274  * leftover cur table as the backend. This avoids expensively copying hundreds
 275  * of megabytes of data during the conversion downtime.
 276  *
 277  * Serialized HistoryBlobCurStub objects will be inserted into the text table
 278  * on conversion if $wgFastSchemaUpgrades is set to true.
 279  */
 280 class HistoryBlobCurStub {
 281         var $mCurId;
 282
 283         /**
 284          * @param $curid Integer: the cur_id pointed to
 285          */
 286         function __construct( $curid = 0 ) {
 287                 $this->mCurId = $curid;
 288         }
 289
 290         /**
 291          * Sets the location (cur_id) of the main object to which this object
 292          * points
 293          *
 294          * @param $id int
 295          */
 296         function setLocation( $id ) {
 297                 $this->mCurId = $id;
 298         }
 299
 300         /**
 301          * @return string|bool
 302          */
 303         function getText() {
 304                 $dbr = wfGetDB( DB_SLAVE );
 305                 $row = $dbr->selectRow( 'cur', array( 'cur_text' ), array( 'cur_id' => $this->mCurId ) );
 306                 if( !$row ) {
 307                         return false;
 308                 }
 309                 return $row->cur_text;
 310         }
 311 }
 312
 313 /**
 314  * Diff-based history compression
 315  * Requires xdiff 1.5+ and zlib
 316  */
 317 class DiffHistoryBlob implements HistoryBlob {
 318         /** Uncompressed item cache */
 319         var $mItems = array();
 320
 321         /** Total uncompressed size */
 322         var $mSize = 0;
 323
 324         /**
 325          * Array of diffs. If a diff D from A to B is notated D = B - A, and Z is
 326          * an empty string:
 327          *
 328          *              { item[map[i]] - item[map[i-1]]   where i > 0
 329          *    diff[i] = {
 330          *              { item[map[i]] - Z                where i = 0
 331          */
 332         var $mDiffs;
 333
 334         /** The diff map, see above */
 335         var $mDiffMap;
 336
 337         /**
 338          * The key for getText()
 339          */
 340         var $mDefaultKey;
 341
 342         /**
 343          * Compressed storage
 344          */
 345         var $mCompressed;
 346
 347         /**
 348          * True if the object is locked against further writes
 349          */
 350         var $mFrozen = false;
 351
 352         /**
 353          * The maximum uncompressed size before the object becomes sad
 354          * Should be less than max_allowed_packet
 355          */
 356         var $mMaxSize = 10000000;
 357
 358         /**
 359          * The maximum number of text items before the object becomes sad
 360          */
 361         var $mMaxCount = 100;
 362
 363         /** Constants from xdiff.h */
 364         const XDL_BDOP_INS = 1;
 365         const XDL_BDOP_CPY = 2;
 366         const XDL_BDOP_INSB = 3;
 367
 368         function __construct() {
 369                 if ( !function_exists( 'gzdeflate' ) ) {
 370                         throw new MWException( "Need zlib support to read or write DiffHistoryBlob\n" );
 371                 }
 372         }
 373
 374         /**
 375          * @throws MWException
 376          * @param $text string
 377          * @return int
 378          */
 379         function addItem( $text ) {
 380                 if ( $this->mFrozen ) {
 381                         throw new MWException( __METHOD__.": Cannot add more items after sleep/wakeup" );
 382                 }
 383
 384                 $this->mItems[] = $text;
 385                 $this->mSize += strlen( $text );
 386                 $this->mDiffs = null; // later
 387                 return count( $this->mItems ) - 1;
 388         }
 389
 390         /**
 391          * @param $key string
 392          * @return string
 393          */
 394         function getItem( $key ) {
 395                 return $this->mItems[$key];
 396         }
 397
 398         /**
 399          * @param $text string
 400          */
 401         function setText( $text ) {
 402                 $this->mDefaultKey = $this->addItem( $text );
 403         }
 404
 405         /**
 406          * @return string
 407          */
 408         function getText() {
 409                 return $this->getItem( $this->mDefaultKey );
 410         }
 411
 412         /**
 413          * @throws MWException
 414          */
 415         function compress() {
 416                 if ( !function_exists( 'xdiff_string_rabdiff' ) ){
 417                         throw new MWException( "Need xdiff 1.5+ support to write DiffHistoryBlob\n" );
 418                 }
 419                 if ( isset( $this->mDiffs ) ) {
 420                         // Already compressed
 421                         return;
 422                 }
 423                 if ( !count( $this->mItems ) ) {
 424                         // Empty
 425                         return;
 426                 }
 427
 428                 // Create two diff sequences: one for main text and one for small text
 429                 $sequences = array(
 430                         'small' => array(
 431                                 'tail' => '',
 432                                 'diffs' => array(),
 433                                 'map' => array(),
 434                         ),
 435                         'main' => array(
 436                                 'tail' => '',
 437                                 'diffs' => array(),
 438                                 'map' => array(),
 439                         ),
 440                 );
 441                 $smallFactor = 0.5;
 442
 443                 for ( $i = 0; $i < count( $this->mItems ); $i++ ) {
 444                         $text = $this->mItems[$i];
 445                         if ( $i == 0 ) {
 446                                 $seqName = 'main';
 447                         } else {
 448                                 $mainTail = $sequences['main']['tail'];
 449                                 if ( strlen( $text ) < strlen( $mainTail ) * $smallFactor ) {
 450                                         $seqName = 'small';
 451                                 } else {
 452                                         $seqName = 'main';
 453                                 }
 454                         }
 455                         $seq =& $sequences[$seqName];
 456                         $tail = $seq['tail'];
 457                         $diff = $this->diff( $tail, $text );
 458                         $seq['diffs'][] = $diff;
 459                         $seq['map'][] = $i;
 460                         $seq['tail'] = $text;
 461                 }
 462                 unset( $seq ); // unlink dangerous alias
 463
 464                 // Knit the sequences together
 465                 $tail = '';
 466                 $this->mDiffs = array();
 467                 $this->mDiffMap = array();
 468                 foreach ( $sequences as $seq ) {
 469                         if ( !count( $seq['diffs'] ) ) {
 470                                 continue;
 471                         }
 472                         if ( $tail === '' ) {
 473                                 $this->mDiffs[] = $seq['diffs'][0];
 474                         } else {
 475                                 $head = $this->patch( '', $seq['diffs'][0] );
 476                                 $this->mDiffs[] = $this->diff( $tail, $head );
 477                         }
 478                         $this->mDiffMap[] = $seq['map'][0];
 479                         for ( $i = 1; $i < count( $seq['diffs'] ); $i++ ) {
 480                                 $this->mDiffs[] = $seq['diffs'][$i];
 481                                 $this->mDiffMap[] = $seq['map'][$i];
 482                         }
 483                         $tail = $seq['tail'];
 484                 }
 485         }
 486
 487         /**
 488          * @param $t1
 489          * @param $t2
 490          * @return string
 491          */
 492         function diff( $t1, $t2 ) {
 493                 # Need to do a null concatenation with warnings off, due to bugs in the current version of xdiff
 494                 # "String is not zero-terminated"
 495                 wfSuppressWarnings();
 496                 $diff = xdiff_string_rabdiff( $t1, $t2 ) . '';
 497                 wfRestoreWarnings();
 498                 return $diff;
 499         }
 500
 501         /**
 502          * @param $base
 503          * @param $diff
 504          * @return bool|string
 505          */
 506         function patch( $base, $diff ) {
 507                 if ( function_exists( 'xdiff_string_bpatch' ) ) {
 508                         wfSuppressWarnings();
 509                         $text = xdiff_string_bpatch( $base, $diff ) . '';
 510                         wfRestoreWarnings();
 511                         return $text;
 512                 }
 513
 514                 # Pure PHP implementation
 515
 516                 $header = unpack( 'Vofp/Vcsize', substr( $diff, 0, 8 ) );
 517
 518                 # Check the checksum if hash/mhash is available
 519                 $ofp = $this->xdiffAdler32( $base );
 520                 if ( $ofp !== false && $ofp !== substr( $diff, 0, 4 ) ) {
 521                         wfDebug( __METHOD__. ": incorrect base checksum\n" );
 522                         return false;
 523                 }
 524                 if ( $header['csize'] != strlen( $base ) ) {
 525                         wfDebug( __METHOD__. ": incorrect base length\n" );
 526                         return false;
 527                 }
 528
 529                 $p = 8;
 530                 $out = '';
 531                 while ( $p < strlen( $diff ) ) {
 532                         $x = unpack( 'Cop', substr( $diff, $p, 1 ) );
 533                         $op = $x['op'];
 534                         ++$p;
 535                         switch ( $op ) {
 536                         case self::XDL_BDOP_INS:
 537                                 $x = unpack( 'Csize', substr( $diff, $p, 1 ) );
 538                                 $p++;
 539                                 $out .= substr( $diff, $p, $x['size'] );
 540                                 $p += $x['size'];
 541                                 break;
 542                         case self::XDL_BDOP_INSB:
 543                                 $x = unpack( 'Vcsize', substr( $diff, $p, 4 ) );
 544                                 $p += 4;
 545                                 $out .= substr( $diff, $p, $x['csize'] );
 546                                 $p += $x['csize'];
 547                                 break;
 548                         case self::XDL_BDOP_CPY:
 549                                 $x = unpack( 'Voff/Vcsize', substr( $diff, $p, 8 ) );
 550                                 $p += 8;
 551                                 $out .= substr( $base, $x['off'], $x['csize'] );
 552                                 break;
 553                         default:
 554                                 wfDebug( __METHOD__.": invalid op\n" );
 555                                 return false;
 556                         }
 557                 }
 558                 return $out;
 559         }
 560
 561         /**
 562          * Compute a binary "Adler-32" checksum as defined by LibXDiff, i.e. with
 563          * the bytes backwards and initialised with 0 instead of 1. See bug 34428.
 564          *
 565          * Returns false if no hashing library is available
 566          */
 567         function xdiffAdler32( $s ) {
 568                 static $init;
 569                 if ( $init === null ) {
 570                         $init = str_repeat( "\xf0", 205 ) . "\xee" . str_repeat( "\xf0", 67 ) . "\x02";
 571                 }
 572                 // The real Adler-32 checksum of $init is zero, so it initialises the
 573                 // state to zero, as it is at the start of LibXDiff's checksum
 574                 // algorithm. Appending the subject string then simulates LibXDiff.
 575                 if ( function_exists( 'hash' ) ) {
 576                         $hash = hash( 'adler32', $init . $s, true );
 577                 } elseif ( function_exists( 'mhash' ) ) {
 578                         $hash = mhash( MHASH_ADLER32, $init . $s );
 579                 } else {
 580                         return false;
 581                 }
 582                 return strrev( $hash );
 583         }
 584
 585         function uncompress() {
 586                 if ( !$this->mDiffs ) {
 587                         return;
 588                 }
 589                 $tail = '';
 590                 for ( $diffKey = 0; $diffKey < count( $this->mDiffs ); $diffKey++ ) {
 591                         $textKey = $this->mDiffMap[$diffKey];
 592                         $text = $this->patch( $tail, $this->mDiffs[$diffKey] );
 593                         $this->mItems[$textKey] = $text;
 594                         $tail = $text;
 595                 }
 596         }
 597
 598         /**
 599          * @return array
 600          */
 601         function __sleep() {
 602                 $this->compress();
 603                 if ( !count( $this->mItems ) ) {
 604                         // Empty object
 605                         $info = false;
 606                 } else {
 607                         // Take forward differences to improve the compression ratio for sequences
 608                         $map = '';
 609                         $prev = 0;
 610                         foreach ( $this->mDiffMap as $i ) {
 611                                 if ( $map !== '' ) {
 612                                         $map .= ',';
 613                                 }
 614                                 $map .= $i - $prev;
 615                                 $prev = $i;
 616                         }
 617                         $info = array(
 618                                 'diffs' => $this->mDiffs,
 619                                 'map' => $map
 620                         );
 621                 }
 622                 if ( isset( $this->mDefaultKey ) ) {
 623                         $info['default'] = $this->mDefaultKey;
 624                 }
 625                 $this->mCompressed = gzdeflate( serialize( $info ) );
 626                 return array( 'mCompressed' );
 627         }
 628
 629         function __wakeup() {
 630                 // addItem() doesn't work if mItems is partially filled from mDiffs
 631                 $this->mFrozen = true;
 632                 $info = unserialize( gzinflate( $this->mCompressed ) );
 633                 unset( $this->mCompressed );
 634
 635                 if ( !$info ) {
 636                         // Empty object
 637                         return;
 638                 }
 639
 640                 if ( isset( $info['default'] ) ) {
 641                         $this->mDefaultKey = $info['default'];
 642                 }
 643                 $this->mDiffs = $info['diffs'];
 644                 if ( isset( $info['base'] ) ) {
 645                         // Old format
 646                         $this->mDiffMap = range( 0, count( $this->mDiffs ) - 1 );
 647                         array_unshift( $this->mDiffs,
 648                                 pack( 'VVCV', 0, 0, self::XDL_BDOP_INSB, strlen( $info['base'] ) ) .
 649                                 $info['base'] );
 650                 } else {
 651                         // New format
 652                         $map = explode( ',', $info['map'] );
 653                         $cur = 0;
 654                         $this->mDiffMap = array();
 655                         foreach ( $map as $i ) {
 656                                 $cur += $i;
 657                                 $this->mDiffMap[] = $cur;
 658                         }
 659                 }
 660                 $this->uncompress();
 661         }
 662
 663         /**
 664          * Helper function for compression jobs
 665          * Returns true until the object is "full" and ready to be committed
 666          *
 667          * @return bool
 668          */
 669         function isHappy() {
 670                 return $this->mSize < $this->mMaxSize
 671                         && count( $this->mItems ) < $this->mMaxCount;
 672         }
 673
 674 }