includes/cache/BacklinkCache.php

   1 <?php
   2 /**
   3  * Class for fetching backlink lists, approximate backlink counts and
   4  * partitions.
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License along
  17  * with this program; if not, write to the Free Software Foundation, Inc.,
  18  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  19  * http://www.gnu.org/copyleft/gpl.html
  20  *
  21  * @file
  22  * @author Tim Starling
  23  * @copyright © 2009, Tim Starling, Domas Mituzas
  24  * @copyright © 2010, Max Sem
  25  * @copyright © 2011, Antoine Musso
  26  */
  27
  28 use Wikimedia\Rdbms\ResultWrapper;
  29 use Wikimedia\Rdbms\FakeResultWrapper;
  30 use Wikimedia\Rdbms\IDatabase;
  31 use MediaWiki\MediaWikiServices;
  32
  33 /**
  34  * Class for fetching backlink lists, approximate backlink counts and
  35  * partitions. This is a shared cache.
  36  *
  37  * Instances of this class should typically be fetched with the method
  38  * $title->getBacklinkCache().
  39  *
  40  * Ideally you should only get your backlinks from here when you think
  41  * there is some advantage in caching them. Otherwise it's just a waste
  42  * of memory.
  43  *
  44  * Introduced by r47317
  45  */
  46 class BacklinkCache {
  47         /** @var BacklinkCache */
  48         protected static $instance;
  49
  50         /**
  51          * Multi dimensions array representing batches. Keys are:
  52          *  > (string) links table name
  53          *   > (int) batch size
  54          *    > 'numRows' : Number of rows for this link table
  55          *    > 'batches' : [ $start, $end ]
  56          *
  57          * @see BacklinkCache::partitionResult()
  58          *
  59          * Cleared with BacklinkCache::clear()
  60          * @var array[]
  61          */
  62         protected $partitionCache = [];
  63
  64         /**
  65          * Contains the whole links from a database result.
  66          * This is raw data that will be partitioned in $partitionCache
  67          *
  68          * Initialized with BacklinkCache::getLinks()
  69          * Cleared with BacklinkCache::clear()
  70          * @var ResultWrapper[]
  71          */
  72         protected $fullResultCache = [];
  73
  74         /**
  75          * @var WANObjectCache
  76          */
  77         protected $wanCache;
  78
  79         /**
  80          * Local copy of a database object.
  81          *
  82          * Accessor: BacklinkCache::getDB()
  83          * Mutator : BacklinkCache::setDB()
  84          * Cleared with BacklinkCache::clear()
  85          */
  86         protected $db;
  87
  88         /**
  89          * Local copy of a Title object
  90          */
  91         protected $title;
  92
  93         const CACHE_EXPIRY = 3600;
  94
  95         /**
  96          * Create a new BacklinkCache
  97          *
  98          * @param Title $title : Title object to create a backlink cache for
  99          */
 100         public function __construct( Title $title ) {
 101                 $this->title = $title;
 102                 $this->wanCache = MediaWikiServices::getInstance()->getMainWANObjectCache();
 103         }
 104
 105         /**
 106          * Create a new BacklinkCache or reuse any existing one.
 107          * Currently, only one cache instance can exist; callers that
 108          * need multiple backlink cache objects should keep them in scope.
 109          *
 110          * @param Title $title Title object to get a backlink cache for
 111          * @return BacklinkCache
 112          */
 113         public static function get( Title $title ) {
 114                 if ( !self::$instance || !self::$instance->title->equals( $title ) ) {
 115                         self::$instance = new self( $title );
 116                 }
 117                 return self::$instance;
 118         }
 119
 120         /**
 121          * Serialization handler, diasallows to serialize the database to prevent
 122          * failures after this class is deserialized from cache with dead DB
 123          * connection.
 124          *
 125          * @return array
 126          */
 127         function __sleep() {
 128                 return [ 'partitionCache', 'fullResultCache', 'title' ];
 129         }
 130
 131         /**
 132          * Clear locally stored data and database object. Invalidate data in memcache.
 133          */
 134         public function clear() {
 135                 $this->partitionCache = [];
 136                 $this->fullResultCache = [];
 137                 $this->wanCache->touchCheckKey( $this->makeCheckKey() );
 138                 unset( $this->db );
 139         }
 140
 141         /**
 142          * Set the Database object to use
 143          *
 144          * @param IDatabase $db
 145          */
 146         public function setDB( $db ) {
 147                 $this->db = $db;
 148         }
 149
 150         /**
 151          * Get the replica DB connection to the database
 152          * When non existing, will initialize the connection.
 153          * @return IDatabase
 154          */
 155         protected function getDB() {
 156                 if ( !isset( $this->db ) ) {
 157                         $this->db = wfGetDB( DB_REPLICA );
 158                 }
 159
 160                 return $this->db;
 161         }
 162
 163         /**
 164          * Get the backlinks for a given table. Cached in process memory only.
 165          * @param string $table
 166          * @param int|bool $startId
 167          * @param int|bool $endId
 168          * @param int $max
 169          * @return TitleArrayFromResult
 170          */
 171         public function getLinks( $table, $startId = false, $endId = false, $max = INF ) {
 172                 return TitleArray::newFromResult( $this->queryLinks( $table, $startId, $endId, $max ) );
 173         }
 174
 175         /**
 176          * Get the backlinks for a given table. Cached in process memory only.
 177          * @param string $table
 178          * @param int|bool $startId
 179          * @param int|bool $endId
 180          * @param int $max
 181          * @param string $select 'all' or 'ids'
 182          * @return ResultWrapper
 183          */
 184         protected function queryLinks( $table, $startId, $endId, $max, $select = 'all' ) {
 185                 $fromField = $this->getPrefix( $table ) . '_from';
 186
 187                 if ( !$startId && !$endId && is_infinite( $max )
 188                         && isset( $this->fullResultCache[$table] )
 189                 ) {
 190                         wfDebug( __METHOD__ . ": got results from cache\n" );
 191                         $res = $this->fullResultCache[$table];
 192                 } else {
 193                         wfDebug( __METHOD__ . ": got results from DB\n" );
 194                         $conds = $this->getConditions( $table );
 195                         // Use the from field in the condition rather than the joined page_id,
 196                         // because databases are stupid and don't necessarily propagate indexes.
 197                         if ( $startId ) {
 198                                 $conds[] = "$fromField >= " . intval( $startId );
 199                         }
 200                         if ( $endId ) {
 201                                 $conds[] = "$fromField <= " . intval( $endId );
 202                         }
 203                         $options = [ 'ORDER BY' => $fromField ];
 204                         if ( is_finite( $max ) && $max > 0 ) {
 205                                 $options['LIMIT'] = $max;
 206                         }
 207
 208                         if ( $select === 'ids' ) {
 209                                 // Just select from the backlink table and ignore the page JOIN
 210                                 $res = $this->getDB()->select(
 211                                         $table,
 212                                         [ $this->getPrefix( $table ) . '_from AS page_id' ],
 213                                         array_filter( $conds, function ( $clause ) { // kind of janky
 214                                                 return !preg_match( '/(\b|=)page_id(\b|=)/', $clause );
 215                                         } ),
 216                                         __METHOD__,
 217                                         $options
 218                                 );
 219                         } else {
 220                                 // Select from the backlink table and JOIN with page title information
 221                                 $res = $this->getDB()->select(
 222                                         [ $table, 'page' ],
 223                                         [ 'page_namespace', 'page_title', 'page_id' ],
 224                                         $conds,
 225                                         __METHOD__,
 226                                         array_merge( [ 'STRAIGHT_JOIN' ], $options )
 227                                 );
 228                         }
 229
 230                         if ( $select === 'all' && !$startId && !$endId && $res->numRows() < $max ) {
 231                                 // The full results fit within the limit, so cache them
 232                                 $this->fullResultCache[$table] = $res;
 233                         } else {
 234                                 wfDebug( __METHOD__ . ": results from DB were uncacheable\n" );
 235                         }
 236                 }
 237
 238                 return $res;
 239         }
 240
 241         /**
 242          * Get the field name prefix for a given table
 243          * @param string $table
 244          * @throws MWException
 245          * @return null|string
 246          */
 247         protected function getPrefix( $table ) {
 248                 static $prefixes = [
 249                         'pagelinks' => 'pl',
 250                         'imagelinks' => 'il',
 251                         'categorylinks' => 'cl',
 252                         'templatelinks' => 'tl',
 253                         'redirect' => 'rd',
 254                 ];
 255
 256                 if ( isset( $prefixes[$table] ) ) {
 257                         return $prefixes[$table];
 258                 } else {
 259                         $prefix = null;
 260                         Hooks::run( 'BacklinkCacheGetPrefix', [ $table, &$prefix ] );
 261                         if ( $prefix ) {
 262                                 return $prefix;
 263                         } else {
 264                                 throw new MWException( "Invalid table \"$table\" in " . __CLASS__ );
 265                         }
 266                 }
 267         }
 268
 269         /**
 270          * Get the SQL condition array for selecting backlinks, with a join
 271          * on the page table.
 272          * @param string $table
 273          * @throws MWException
 274          * @return array|null
 275          */
 276         protected function getConditions( $table ) {
 277                 $prefix = $this->getPrefix( $table );
 278
 279                 switch ( $table ) {
 280                         case 'pagelinks':
 281                         case 'templatelinks':
 282                                 $conds = [
 283                                         "{$prefix}_namespace" => $this->title->getNamespace(),
 284                                         "{$prefix}_title" => $this->title->getDBkey(),
 285                                         "page_id={$prefix}_from"
 286                                 ];
 287                                 break;
 288                         case 'redirect':
 289                                 $conds = [
 290                                         "{$prefix}_namespace" => $this->title->getNamespace(),
 291                                         "{$prefix}_title" => $this->title->getDBkey(),
 292                                         $this->getDB()->makeList( [
 293                                                 "{$prefix}_interwiki" => '',
 294                                                 "{$prefix}_interwiki IS NULL",
 295                                         ], LIST_OR ),
 296                                         "page_id={$prefix}_from"
 297                                 ];
 298                                 break;
 299                         case 'imagelinks':
 300                         case 'categorylinks':
 301                                 $conds = [
 302                                         "{$prefix}_to" => $this->title->getDBkey(),
 303                                         "page_id={$prefix}_from"
 304                                 ];
 305                                 break;
 306                         default:
 307                                 $conds = null;
 308                                 Hooks::run( 'BacklinkCacheGetConditions', [ $table, $this->title, &$conds ] );
 309                                 if ( !$conds ) {
 310                                         throw new MWException( "Invalid table \"$table\" in " . __CLASS__ );
 311                                 }
 312                 }
 313
 314                 return $conds;
 315         }
 316
 317         /**
 318          * Check if there are any backlinks
 319          * @param string $table
 320          * @return bool
 321          */
 322         public function hasLinks( $table ) {
 323                 return ( $this->getNumLinks( $table, 1 ) > 0 );
 324         }
 325
 326         /**
 327          * Get the approximate number of backlinks
 328          * @param string $table
 329          * @param int $max Only count up to this many backlinks
 330          * @return int
 331          */
 332         public function getNumLinks( $table, $max = INF ) {
 333                 global $wgUpdateRowsPerJob;
 334
 335                 // 1) try partition cache ...
 336                 if ( isset( $this->partitionCache[$table] ) ) {
 337                         $entry = reset( $this->partitionCache[$table] );
 338
 339                         return min( $max, $entry['numRows'] );
 340                 }
 341
 342                 // 2) ... then try full result cache ...
 343                 if ( isset( $this->fullResultCache[$table] ) ) {
 344                         return min( $max, $this->fullResultCache[$table]->numRows() );
 345                 }
 346
 347                 $memcKey = $this->wanCache->makeKey(
 348                         'numbacklinks',
 349                         md5( $this->title->getPrefixedDBkey() ),
 350                         $table
 351                 );
 352
 353                 // 3) ... fallback to memcached ...
 354                 $curTTL = INF;
 355                 $count = $this->wanCache->get(
 356                         $memcKey,
 357                         $curTTL,
 358                         [
 359                                 $this->makeCheckKey()
 360                         ]
 361                 );
 362                 if ( $count && ( $curTTL > 0 ) ) {
 363                         return min( $max, $count );
 364                 }
 365
 366                 // 4) fetch from the database ...
 367                 if ( is_infinite( $max ) ) { // no limit at all
 368                         // Use partition() since it will batch the query and skip the JOIN.
 369                         // Use $wgUpdateRowsPerJob just to encourage cache reuse for jobs.
 370                         $this->partition( $table, $wgUpdateRowsPerJob ); // updates $this->partitionCache
 371                         return $this->partitionCache[$table][$wgUpdateRowsPerJob]['numRows'];
 372                 } else { // probably some sane limit
 373                         // Fetch the full title info, since the caller will likely need it next
 374                         $count = $this->getLinks( $table, false, false, $max )->count();
 375                         if ( $count < $max ) { // full count
 376                                 $this->wanCache->set( $memcKey, $count, self::CACHE_EXPIRY );
 377                         }
 378                 }
 379
 380                 return min( $max, $count );
 381         }
 382
 383         /**
 384          * Partition the backlinks into batches.
 385          * Returns an array giving the start and end of each range. The first
 386          * batch has a start of false, and the last batch has an end of false.
 387          *
 388          * @param string $table The links table name
 389          * @param int $batchSize
 390          * @return array
 391          */
 392         public function partition( $table, $batchSize ) {
 393                 // 1) try partition cache ...
 394                 if ( isset( $this->partitionCache[$table][$batchSize] ) ) {
 395                         wfDebug( __METHOD__ . ": got from partition cache\n" );
 396
 397                         return $this->partitionCache[$table][$batchSize]['batches'];
 398                 }
 399
 400                 $this->partitionCache[$table][$batchSize] = false;
 401                 $cacheEntry =& $this->partitionCache[$table][$batchSize];
 402
 403                 // 2) ... then try full result cache ...
 404                 if ( isset( $this->fullResultCache[$table] ) ) {
 405                         $cacheEntry = $this->partitionResult( $this->fullResultCache[$table], $batchSize );
 406                         wfDebug( __METHOD__ . ": got from full result cache\n" );
 407
 408                         return $cacheEntry['batches'];
 409                 }
 410
 411                 $memcKey = $this->wanCache->makeKey(
 412                         'backlinks',
 413                         md5( $this->title->getPrefixedDBkey() ),
 414                         $table,
 415                         $batchSize
 416                 );
 417
 418                 // 3) ... fallback to memcached ...
 419                 $curTTL = 0;
 420                 $memcValue = $this->wanCache->get(
 421                         $memcKey,
 422                         $curTTL,
 423                         [
 424                                 $this->makeCheckKey()
 425                         ]
 426                 );
 427                 if ( is_array( $memcValue ) && ( $curTTL > 0 ) ) {
 428                         $cacheEntry = $memcValue;
 429                         wfDebug( __METHOD__ . ": got from memcached $memcKey\n" );
 430
 431                         return $cacheEntry['batches'];
 432                 }
 433
 434                 // 4) ... finally fetch from the slow database :(
 435                 $cacheEntry = [ 'numRows' => 0, 'batches' => [] ]; // final result
 436                 // Do the selects in batches to avoid client-side OOMs (T45452).
 437                 // Use a LIMIT that plays well with $batchSize to keep equal sized partitions.
 438                 $selectSize = max( $batchSize, 200000 - ( 200000 % $batchSize ) );
 439                 $start = false;
 440                 do {
 441                         $res = $this->queryLinks( $table, $start, false, $selectSize, 'ids' );
 442                         $partitions = $this->partitionResult( $res, $batchSize, false );
 443                         // Merge the link count and range partitions for this chunk
 444                         $cacheEntry['numRows'] += $partitions['numRows'];
 445                         $cacheEntry['batches'] = array_merge( $cacheEntry['batches'], $partitions['batches'] );
 446                         if ( count( $partitions['batches'] ) ) {
 447                                 list( , $lEnd ) = end( $partitions['batches'] );
 448                                 $start = $lEnd + 1; // pick up after this inclusive range
 449                         }
 450                 } while ( $partitions['numRows'] >= $selectSize );
 451                 // Make sure the first range has start=false and the last one has end=false
 452                 if ( count( $cacheEntry['batches'] ) ) {
 453                         $cacheEntry['batches'][0][0] = false;
 454                         $cacheEntry['batches'][count( $cacheEntry['batches'] ) - 1][1] = false;
 455                 }
 456
 457                 // Save partitions to memcached
 458                 $this->wanCache->set( $memcKey, $cacheEntry, self::CACHE_EXPIRY );
 459
 460                 // Save backlink count to memcached
 461                 $memcKey = $this->wanCache->makeKey(
 462                         'numbacklinks',
 463                         md5( $this->title->getPrefixedDBkey() ),
 464                         $table
 465                 );
 466                 $this->wanCache->set( $memcKey, $cacheEntry['numRows'], self::CACHE_EXPIRY );
 467
 468                 wfDebug( __METHOD__ . ": got from database\n" );
 469
 470                 return $cacheEntry['batches'];
 471         }
 472
 473         /**
 474          * Partition a DB result with backlinks in it into batches
 475          * @param ResultWrapper $res Database result
 476          * @param int $batchSize
 477          * @param bool $isComplete Whether $res includes all the backlinks
 478          * @throws MWException
 479          * @return array
 480          */
 481         protected function partitionResult( $res, $batchSize, $isComplete = true ) {
 482                 $batches = [];
 483                 $numRows = $res->numRows();
 484                 $numBatches = ceil( $numRows / $batchSize );
 485
 486                 for ( $i = 0; $i < $numBatches; $i++ ) {
 487                         if ( $i == 0 && $isComplete ) {
 488                                 $start = false;
 489                         } else {
 490                                 $rowNum = $i * $batchSize;
 491                                 $res->seek( $rowNum );
 492                                 $row = $res->fetchObject();
 493                                 $start = (int)$row->page_id;
 494                         }
 495
 496                         if ( $i == ( $numBatches - 1 ) && $isComplete ) {
 497                                 $end = false;
 498                         } else {
 499                                 $rowNum = min( $numRows - 1, ( $i + 1 ) * $batchSize - 1 );
 500                                 $res->seek( $rowNum );
 501                                 $row = $res->fetchObject();
 502                                 $end = (int)$row->page_id;
 503                         }
 504
 505                         # Sanity check order
 506                         if ( $start && $end && $start > $end ) {
 507                                 throw new MWException( __METHOD__ . ': Internal error: query result out of order' );
 508                         }
 509
 510                         $batches[] = [ $start, $end ];
 511                 }
 512
 513                 return [ 'numRows' => $numRows, 'batches' => $batches ];
 514         }
 515
 516         /**
 517          * Get a Title iterator for cascade-protected template/file use backlinks
 518          *
 519          * @return TitleArray
 520          * @since 1.25
 521          */
 522         public function getCascadeProtectedLinks() {
 523                 $dbr = $this->getDB();
 524
 525                 // @todo: use UNION without breaking tests that use temp tables
 526                 $resSets = [];
 527                 $resSets[] = $dbr->select(
 528                         [ 'templatelinks', 'page_restrictions', 'page' ],
 529                         [ 'page_namespace', 'page_title', 'page_id' ],
 530                         [
 531                                 'tl_namespace' => $this->title->getNamespace(),
 532                                 'tl_title' => $this->title->getDBkey(),
 533                                 'tl_from = pr_page',
 534                                 'pr_cascade' => 1,
 535                                 'page_id = tl_from'
 536                         ],
 537                         __METHOD__,
 538                         [ 'DISTINCT' ]
 539                 );
 540                 if ( $this->title->getNamespace() == NS_FILE ) {
 541                         $resSets[] = $dbr->select(
 542                                 [ 'imagelinks', 'page_restrictions', 'page' ],
 543                                 [ 'page_namespace', 'page_title', 'page_id' ],
 544                                 [
 545                                         'il_to' => $this->title->getDBkey(),
 546                                         'il_from = pr_page',
 547                                         'pr_cascade' => 1,
 548                                         'page_id = il_from'
 549                                 ],
 550                                 __METHOD__,
 551                                 [ 'DISTINCT' ]
 552                         );
 553                 }
 554
 555                 // Combine and de-duplicate the results
 556                 $mergedRes = [];
 557                 foreach ( $resSets as $res ) {
 558                         foreach ( $res as $row ) {
 559                                 $mergedRes[$row->page_id] = $row;
 560                         }
 561                 }
 562
 563                 return TitleArray::newFromResult(
 564                         new FakeResultWrapper( array_values( $mergedRes ) ) );
 565         }
 566
 567         /**
 568          * Returns check key for the backlinks cache for a particular title
 569          *
 570          * @return String
 571          */
 572         private function makeCheckKey() {
 573                 return $this->wanCache->makeKey(
 574                         'backlinks',
 575                         md5( $this->title->getPrefixedDBkey() )
 576                 );
 577         }
 578 }