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