includes/HistoryBlob.php

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