includes/libs/MapCacheLRU.php

   1 <?php
   2 /**
   3  * Per-process memory cache for storing items.
   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  * @ingroup Cache
  22  */
  23 use Wikimedia\Assert\Assert;
  24
  25 /**
  26  * Handles a simple LRU key/value map with a maximum number of entries
  27  *
  28  * The last-modification timestamp of entries is internally tracked so that callers can
  29  * specify the maximum acceptable age of entries in calls to the has() method. As a convenience,
  30  * the hasField(), getField(), and setField() methods can be used for entries that are field/value
  31  * maps themselves; such fields will have their own internally tracked last-modification timestamp.
  32  *
  33  * @see ProcessCacheLRU
  34  * @ingroup Cache
  35  * @since 1.23
  36  */
  37 class MapCacheLRU implements IExpiringStore, Serializable {
  38         /** @var array Map of (key => value) */
  39         private $cache = [];
  40         /** @var array Map of (key => (UNIX timestamp, (field => UNIX timestamp))) */
  41         private $timestamps = [];
  42         /** @var float Default entry timestamp if not specified */
  43         private $epoch;
  44
  45         /** @var int Max number of entries */
  46         private $maxCacheKeys;
  47
  48         /** @var float|null */
  49         private $wallClockOverride;
  50
  51         /** @var float */
  52         const RANK_TOP = 1.0;
  53
  54         /** @var int Array key that holds the entry's main timestamp (flat key use) */
  55         const SIMPLE = 0;
  56         /** @var int Array key that holds the entry's field timestamps (nested key use) */
  57         const FIELDS = 1;
  58
  59         /**
  60          * @param int $maxKeys Maximum number of entries allowed (min 1)
  61          * @throws Exception When $maxKeys is not an int or not above zero
  62          */
  63         public function __construct( $maxKeys ) {
  64                 Assert::parameterType( 'integer', $maxKeys, '$maxKeys' );
  65                 Assert::parameter( $maxKeys > 0, '$maxKeys', 'must be above zero' );
  66
  67                 $this->maxCacheKeys = $maxKeys;
  68                 // Use the current time as the default "as of" timestamp of entries
  69                 $this->epoch = $this->getCurrentTime();
  70         }
  71
  72         /**
  73          * @param array $values Key/value map in order of increasingly recent access
  74          * @param int $maxKeys
  75          * @return MapCacheLRU
  76          * @since 1.30
  77          */
  78         public static function newFromArray( array $values, $maxKeys ) {
  79                 $mapCache = new self( $maxKeys );
  80                 $mapCache->cache = ( count( $values ) > $maxKeys )
  81                         ? array_slice( $values, -$maxKeys, null, true )
  82                         : $values;
  83
  84                 return $mapCache;
  85         }
  86
  87         /**
  88          * @return array Key/value map in order of increasingly recent access
  89          * @since 1.30
  90          */
  91         public function toArray() {
  92                 return $this->cache;
  93         }
  94
  95         /**
  96          * Set a key/value pair.
  97          * This will prune the cache if it gets too large based on LRU.
  98          * If the item is already set, it will be pushed to the top of the cache.
  99          *
 100          * To reduce evictions due to one-off use of many new keys, $rank can be
 101          * set to have keys start at the top of a bottom fraction of the list. A value
 102          * of 3/8 means values start at the top of the bottom 3/8s of the list and are
 103          * moved to the top of the list when accessed a second time.
 104          *
 105          * @param string $key
 106          * @param mixed $value
 107          * @param float $rank Bottom fraction of the list where keys start off [default: 1.0]
 108          * @return void
 109          */
 110         public function set( $key, $value, $rank = self::RANK_TOP ) {
 111                 if ( $this->has( $key ) ) {
 112                         $this->ping( $key );
 113                 } elseif ( count( $this->cache ) >= $this->maxCacheKeys ) {
 114                         reset( $this->cache );
 115                         $evictKey = key( $this->cache );
 116                         unset( $this->cache[$evictKey] );
 117                         unset( $this->timestamps[$evictKey] );
 118                 }
 119
 120                 if ( $rank < 1.0 && $rank > 0 ) {
 121                         $offset = intval( $rank * count( $this->cache ) );
 122                         $this->cache = array_slice( $this->cache, 0, $offset, true )
 123                                 + [ $key => $value ]
 124                                 + array_slice( $this->cache, $offset, null, true );
 125                 } else {
 126                         $this->cache[$key] = $value;
 127                 }
 128
 129                 $this->timestamps[$key] = [
 130                         self::SIMPLE => $this->getCurrentTime(),
 131                         self::FIELDS => []
 132                 ];
 133         }
 134
 135         /**
 136          * Check if a key exists
 137          *
 138          * @param string $key
 139          * @param float $maxAge Ignore items older than this many seconds [default: INF]
 140          * @return bool
 141          * @since 1.32 Added $maxAge
 142          */
 143         public function has( $key, $maxAge = INF ) {
 144                 if ( !is_int( $key ) && !is_string( $key ) ) {
 145                         throw new UnexpectedValueException(
 146                                 __METHOD__ . ': invalid key; must be string or integer.' );
 147                 }
 148
 149                 if ( !array_key_exists( $key, $this->cache ) ) {
 150                         return false;
 151                 }
 152
 153                 return ( $maxAge <= 0 || $this->getAge( $key ) <= $maxAge );
 154         }
 155
 156         /**
 157          * Get the value for a key.
 158          * This returns null if the key is not set.
 159          * If the item is already set, it will be pushed to the top of the cache.
 160          *
 161          * @param string $key
 162          * @param float $maxAge Ignore items older than this many seconds [default: INF]
 163          * @param mixed|null $default Value to return if no key is found [default: null]
 164          * @return mixed Returns $default if the key was not found or is older than $maxAge
 165          * @since 1.32 Added $maxAge
 166          * @since 1.34 Added $default
 167          */
 168         public function get( $key, $maxAge = INF, $default = null ) {
 169                 if ( !$this->has( $key, $maxAge ) ) {
 170                         return $default;
 171                 }
 172
 173                 $this->ping( $key );
 174
 175                 return $this->cache[$key];
 176         }
 177
 178         /**
 179          * @param string|int $key
 180          * @param string|int $field
 181          * @param mixed $value
 182          * @param float $initRank
 183          */
 184         public function setField( $key, $field, $value, $initRank = self::RANK_TOP ) {
 185                 if ( $this->has( $key ) ) {
 186                         $this->ping( $key );
 187                 } else {
 188                         $this->set( $key, [], $initRank );
 189                 }
 190
 191                 if ( !is_int( $field ) && !is_string( $field ) ) {
 192                         throw new UnexpectedValueException(
 193                                 __METHOD__ . ": invalid field for '$key'; must be string or integer." );
 194                 }
 195
 196                 if ( !is_array( $this->cache[$key] ) ) {
 197                         $type = gettype( $this->cache[$key] );
 198
 199                         throw new UnexpectedValueException( "The value of '$key' ($type) is not an array." );
 200                 }
 201
 202                 $this->cache[$key][$field] = $value;
 203                 $this->timestamps[$key][self::FIELDS][$field] = $this->getCurrentTime();
 204         }
 205
 206         /**
 207          * @param string|int $key
 208          * @param string|int $field
 209          * @param float $maxAge Ignore items older than this many seconds [default: INF]
 210          * @return bool
 211          * @since 1.32 Added $maxAge
 212          */
 213         public function hasField( $key, $field, $maxAge = INF ) {
 214                 $value = $this->get( $key );
 215
 216                 if ( !is_int( $field ) && !is_string( $field ) ) {
 217                         throw new UnexpectedValueException(
 218                                 __METHOD__ . ": invalid field for '$key'; must be string or integer." );
 219                 }
 220
 221                 if ( !is_array( $value ) || !array_key_exists( $field, $value ) ) {
 222                         return false;
 223                 }
 224
 225                 return ( $maxAge <= 0 || $this->getAge( $key, $field ) <= $maxAge );
 226         }
 227
 228         /**
 229          * @param string|int $key
 230          * @param string|int $field
 231          * @param float $maxAge Ignore items older than this many seconds [default: INF]
 232          * @return mixed Returns null if the key was not found or is older than $maxAge
 233          * @since 1.32 Added $maxAge
 234          */
 235         public function getField( $key, $field, $maxAge = INF ) {
 236                 if ( !$this->hasField( $key, $field, $maxAge ) ) {
 237                         return null;
 238                 }
 239
 240                 return $this->cache[$key][$field];
 241         }
 242
 243         /**
 244          * @return array
 245          * @since 1.25
 246          */
 247         public function getAllKeys() {
 248                 return array_keys( $this->cache );
 249         }
 250
 251         /**
 252          * Get an item with the given key, producing and setting it if not found.
 253          *
 254          * If the callback returns false, then nothing is stored.
 255          *
 256          * @since 1.28
 257          * @param string $key
 258          * @param callable $callback Callback that will produce the value
 259          * @param float $rank Bottom fraction of the list where keys start off [default: 1.0]
 260          * @param float $maxAge Ignore items older than this many seconds [default: INF]
 261          * @return mixed The cached value if found or the result of $callback otherwise
 262          * @since 1.32 Added $maxAge
 263          */
 264         public function getWithSetCallback(
 265                 $key, callable $callback, $rank = self::RANK_TOP, $maxAge = INF
 266         ) {
 267                 if ( $this->has( $key, $maxAge ) ) {
 268                         $value = $this->get( $key );
 269                 } else {
 270                         $value = call_user_func( $callback );
 271                         if ( $value !== false ) {
 272                                 $this->set( $key, $value, $rank );
 273                         }
 274                 }
 275
 276                 return $value;
 277         }
 278
 279         /**
 280          * Clear one or several cache entries, or all cache entries
 281          *
 282          * @param string|array|null $keys
 283          * @return void
 284          */
 285         public function clear( $keys = null ) {
 286                 if ( func_num_args() == 0 ) {
 287                         $this->cache = [];
 288                         $this->timestamps = [];
 289                 } else {
 290                         foreach ( (array)$keys as $key ) {
 291                                 unset( $this->cache[$key] );
 292                                 unset( $this->timestamps[$key] );
 293                         }
 294                 }
 295         }
 296
 297         /**
 298          * Get the maximum number of keys allowed
 299          *
 300          * @return int
 301          * @since 1.32
 302          */
 303         public function getMaxSize() {
 304                 return $this->maxCacheKeys;
 305         }
 306
 307         /**
 308          * Resize the maximum number of cache entries, removing older entries as needed
 309          *
 310          * @param int $maxKeys Maximum number of entries allowed (min 1)
 311          * @return void
 312          * @throws Exception When $maxKeys is not an int or not above zero
 313          * @since 1.32
 314          */
 315         public function setMaxSize( $maxKeys ) {
 316                 Assert::parameterType( 'integer', $maxKeys, '$maxKeys' );
 317                 Assert::parameter( $maxKeys > 0, '$maxKeys', 'must be above zero' );
 318
 319                 $this->maxCacheKeys = $maxKeys;
 320                 while ( count( $this->cache ) > $this->maxCacheKeys ) {
 321                         reset( $this->cache );
 322                         $evictKey = key( $this->cache );
 323                         unset( $this->cache[$evictKey] );
 324                         unset( $this->timestamps[$evictKey] );
 325                 }
 326         }
 327
 328         /**
 329          * Push an entry to the top of the cache
 330          *
 331          * @param string $key
 332          */
 333         private function ping( $key ) {
 334                 $item = $this->cache[$key];
 335                 unset( $this->cache[$key] );
 336                 $this->cache[$key] = $item;
 337         }
 338
 339         /**
 340          * @param string|int $key
 341          * @param string|int|null $field [optional]
 342          * @return float UNIX timestamp; the age of the given entry or entry field
 343          */
 344         private function getAge( $key, $field = null ) {
 345                 if ( $field !== null ) {
 346                         $mtime = $this->timestamps[$key][self::FIELDS][$field] ?? $this->epoch;
 347                 } else {
 348                         $mtime = $this->timestamps[$key][self::SIMPLE] ?? $this->epoch;
 349                 }
 350
 351                 return ( $this->getCurrentTime() - $mtime );
 352         }
 353
 354         public function serialize() {
 355                 return serialize( [
 356                         'entries' => $this->cache,
 357                         'timestamps' => $this->timestamps
 358                 ] );
 359         }
 360
 361         public function unserialize( $serialized ) {
 362                 $data = unserialize( $serialized );
 363                 $this->cache = $data['entries'] ?? [];
 364                 $this->timestamps = $data['timestamps'] ?? [];
 365                 $this->epoch = $this->getCurrentTime();
 366         }
 367
 368         /**
 369          * @return float UNIX timestamp
 370          * @codeCoverageIgnore
 371          */
 372         protected function getCurrentTime() {
 373                 return $this->wallClockOverride ?: microtime( true );
 374         }
 375
 376         /**
 377          * @param float|null &$time Mock UNIX timestamp for testing
 378          * @codeCoverageIgnore
 379          */
 380         public function setMockTime( &$time ) {
 381                 $this->wallClockOverride =& $time;
 382         }
 383 }