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