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