| 1 | package App::Syslogd::Cache; | ||||||||||||||||||||||||||||
| 2 | |||||||||||||||||||||||||||||
| 3 | # A small in-memory cache with expiry and a size limit: the default home | ||||||||||||||||||||||||||||
| 4 | # for App::Syslogd's reverse-DNS answers. | ||||||||||||||||||||||||||||
| 5 | # | ||||||||||||||||||||||||||||
| 6 | # It replaces a CHI Memory cache, which spent about 17 microseconds on | ||||||||||||||||||||||||||||
| 7 | # every hit (key transformation, cache objects, a Log::Any call): a third | ||||||||||||||||||||||||||||
| 8 | # of the time taken to record a datagram. Here a hit is one hash lookup | ||||||||||||||||||||||||||||
| 9 | # and a time comparison. It has the same compute() interface, so any CHI | ||||||||||||||||||||||||||||
| 10 | # object can still be passed to App::Syslogd instead. | ||||||||||||||||||||||||||||
| 11 | |||||||||||||||||||||||||||||
| 12 | 51 | ▶ | use strict; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 13 | 51 | ▶ | use warnings; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 14 | 51 | ▶ | use autodie qw(:all); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 15 | |||||||||||||||||||||||||||||
| 16 | 51 | ▶ | use Params::Get; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 17 | 51 | ▶ | use Params::Validate::Strict; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 18 | 51 | ▶ | use Readonly; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 19 | |||||||||||||||||||||||||||||
| 20 | 51 | our $VERSION = '0.002.1'; | |||||||||||||||||||||||||||
| 21 | |||||||||||||||||||||||||||||
| 22 | # Bytes charged for each entry on top of its key and value: a rough figure | ||||||||||||||||||||||||||||
| 23 | # for Perl's own bookkeeping (the hash entry, the small array, the queue | ||||||||||||||||||||||||||||
| 24 | # slot), so that many tiny entries cannot slip past the limit | ||||||||||||||||||||||||||||
| 25 | 51 | Readonly::Scalar my $ENTRY_OVERHEAD => 64; | |||||||||||||||||||||||||||
| 26 | |||||||||||||||||||||||||||||
| 27 | # The default limit, the same as App::Syslogd's dns_cache_bytes default | ||||||||||||||||||||||||||||
| 28 | 51 | Readonly::Scalar my $DEFAULT_MAX_BYTES => 262_144; | |||||||||||||||||||||||||||
| 29 | |||||||||||||||||||||||||||||
| 30 | # The age queue is rebuilt once it holds this many times more items than | ||||||||||||||||||||||||||||
| 31 | # there are entries (replaced entries leave stale items behind) | ||||||||||||||||||||||||||||
| 32 | 51 | Readonly::Scalar my $QUEUE_SLACK => 2; | |||||||||||||||||||||||||||
| 33 | |||||||||||||||||||||||||||||
| 34 | =encoding utf8 | ||||||||||||||||||||||||||||
| 35 | |||||||||||||||||||||||||||||
| 36 | =head1 NAME | ||||||||||||||||||||||||||||
| 37 | |||||||||||||||||||||||||||||
| 38 | App::Syslogd::Cache - A small, fast in-memory cache with expiry and a size limit | ||||||||||||||||||||||||||||
| 39 | |||||||||||||||||||||||||||||
| 40 | =head1 VERSION | ||||||||||||||||||||||||||||
| 41 | |||||||||||||||||||||||||||||
| 42 | Version 0.002.1 | ||||||||||||||||||||||||||||
| 43 | |||||||||||||||||||||||||||||
| 44 | =head1 SYNOPSIS | ||||||||||||||||||||||||||||
| 45 | |||||||||||||||||||||||||||||
| 46 | use App::Syslogd::Cache; | ||||||||||||||||||||||||||||
| 47 | |||||||||||||||||||||||||||||
| 48 | my $cache = App::Syslogd::Cache->new(max_bytes => 65_536); | ||||||||||||||||||||||||||||
| 49 | |||||||||||||||||||||||||||||
| 50 | # Look a value up; compute and remember it for 300 seconds if missing | ||||||||||||||||||||||||||||
| 51 | my $name = $cache->compute('192.0.2.1', 300, sub { slow_lookup('192.0.2.1') }); | ||||||||||||||||||||||||||||
| 52 | |||||||||||||||||||||||||||||
| 53 | =head1 DESCRIPTION | ||||||||||||||||||||||||||||
| 54 | |||||||||||||||||||||||||||||
| 55 | App::Syslogd uses this to remember reverse-DNS answers. It holds values in | ||||||||||||||||||||||||||||
| 56 | a Perl hash, forgets each one after its time to live, and keeps its total | ||||||||||||||||||||||||||||
| 57 | size under a limit by dropping the oldest entries first. | ||||||||||||||||||||||||||||
| 58 | |||||||||||||||||||||||||||||
| 59 | Its only method besides C<new()> is C<compute()>, which has the same calling | ||||||||||||||||||||||||||||
| 60 | convention as L<CHI>'s, so either can be given to App::Syslogd as its | ||||||||||||||||||||||||||||
| 61 | C<cache>. | ||||||||||||||||||||||||||||
| 62 | |||||||||||||||||||||||||||||
| 63 | =head1 METHODS | ||||||||||||||||||||||||||||
| 64 | |||||||||||||||||||||||||||||
| 65 | =head2 new | ||||||||||||||||||||||||||||
| 66 | |||||||||||||||||||||||||||||
| 67 | Purpose: make an empty cache. | ||||||||||||||||||||||||||||
| 68 | |||||||||||||||||||||||||||||
| 69 | Args: C<max_bytes> (optional): the most memory, roughly in bytes, that the | ||||||||||||||||||||||||||||
| 70 | entries may use. Default 262144. Each entry counts as the length of its | ||||||||||||||||||||||||||||
| 71 | key, plus the length of its value, plus 64. | ||||||||||||||||||||||||||||
| 72 | |||||||||||||||||||||||||||||
| 73 | Returns: the new cache. | ||||||||||||||||||||||||||||
| 74 | |||||||||||||||||||||||||||||
| 75 | Side Effects: none. | ||||||||||||||||||||||||||||
| 76 | |||||||||||||||||||||||||||||
| 77 | Usage: | ||||||||||||||||||||||||||||
| 78 | |||||||||||||||||||||||||||||
| 79 | my $cache = App::Syslogd::Cache->new(max_bytes => 65_536); | ||||||||||||||||||||||||||||
| 80 | |||||||||||||||||||||||||||||
| 81 | =head3 EXAMPLE | ||||||||||||||||||||||||||||
| 82 | |||||||||||||||||||||||||||||
| 83 | my $cache = App::Syslogd::Cache->new(); # 256 KB | ||||||||||||||||||||||||||||
| 84 | |||||||||||||||||||||||||||||
| 85 | =head3 API SPECIFICATION | ||||||||||||||||||||||||||||
| 86 | |||||||||||||||||||||||||||||
| 87 | =head4 INPUT | ||||||||||||||||||||||||||||
| 88 | |||||||||||||||||||||||||||||
| 89 | { | ||||||||||||||||||||||||||||
| 90 | max_bytes => { type => 'integer', min => 1, optional => 1 }, | ||||||||||||||||||||||||||||
| 91 | } | ||||||||||||||||||||||||||||
| 92 | |||||||||||||||||||||||||||||
| 93 | =head4 OUTPUT | ||||||||||||||||||||||||||||
| 94 | |||||||||||||||||||||||||||||
| 95 | { type => 'object', isa => 'App::Syslogd::Cache' } | ||||||||||||||||||||||||||||
| 96 | |||||||||||||||||||||||||||||
| 97 | =head3 MESSAGES | ||||||||||||||||||||||||||||
| 98 | |||||||||||||||||||||||||||||
| 99 | +--------------------------------------------+--------------------------+-------------------------+ | ||||||||||||||||||||||||||||
| 100 | | Message (dies) | Meaning | What to do | | ||||||||||||||||||||||||||||
| 101 | +--------------------------------------------+--------------------------+-------------------------+ | ||||||||||||||||||||||||||||
| 102 | | validate_strict: Parameter 'max_bytes' ... | Not a whole number of at | Give 1 or more | | ||||||||||||||||||||||||||||
| 103 | | | least 1 | | | ||||||||||||||||||||||||||||
| 104 | | validate_strict: Unknown parameter 'x' | A misspelt option | Use max_bytes | | ||||||||||||||||||||||||||||
| 105 | +--------------------------------------------+--------------------------+-------------------------+ | ||||||||||||||||||||||||||||
| 106 | |||||||||||||||||||||||||||||
| 107 | =cut | ||||||||||||||||||||||||||||
| 108 | |||||||||||||||||||||||||||||
| 109 | sub new | ||||||||||||||||||||||||||||
| 110 | 516 | ▶ | { | ||||||||||||||||||||||||||
|
Subroutine
new: called CC=3 SCAR=11.0
Pod
documented
| |||||||||||||||||||||||||||||
| 111 | 516 | my $class = shift; | |||||||||||||||||||||||||||
| 112 | |||||||||||||||||||||||||||||
| 113 | 516 | ▶ | my $args = Params::Validate::Strict::validate_strict({ | ||||||||||||||||||||||||||
|
Condition100%2/2
Params::Get::get_params(undef, \@_) || {}
MC/DC100%1/1
Params::Get::get_params(undef, \@_) || {}
Params::Get::get_params(undef, \@_)
Truth table100%2/2
A
A= Params::Get::get_params(undef, \@_)
| |||||||||||||||||||||||||||||
| 114 | schema => { max_bytes => { type => 'integer', min => 1, optional => 1 } }, | ||||||||||||||||||||||||||||
| 115 | input => Params::Get::get_params(undef, \@_) || {}, | ||||||||||||||||||||||||||||
| 116 | }); | ||||||||||||||||||||||||||||
| 117 | |||||||||||||||||||||||||||||
| 118 | # entries: key => [value, expiry time, size, serial] | ||||||||||||||||||||||||||||
| 119 | # order: [key, serial] pairs, oldest first, for eviction | ||||||||||||||||||||||||||||
| 120 | return bless { | ||||||||||||||||||||||||||||
| 121 | 513 | ▶ | max_bytes => $args->{max_bytes} // $DEFAULT_MAX_BYTES, | ||||||||||||||||||||||||||
|
Condition66%2/3
$args->{"max_bytes"} // $DEFAULT_MAX_BYTES
MC/DC0%0/2
$args->{"max_bytes"} // $DEFAULT_MAX_BYTES
$args->{"max_bytes"}
$DEFAULT_MAX_BYTES
Truth table66%2/3
A // B
A= $args->{"max_bytes"}B= $DEFAULT_MAX_BYTES
| |||||||||||||||||||||||||||||
| 122 | entries => {}, | ||||||||||||||||||||||||||||
| 123 | order => [], | ||||||||||||||||||||||||||||
| 124 | bytes => 0, | ||||||||||||||||||||||||||||
| 125 | serial => 0, | ||||||||||||||||||||||||||||
| 126 | }, $class; | ||||||||||||||||||||||||||||
| 127 | } | ||||||||||||||||||||||||||||
| 128 | |||||||||||||||||||||||||||||
| 129 | =head2 compute | ||||||||||||||||||||||||||||
| 130 | |||||||||||||||||||||||||||||
| 131 | Purpose: return the remembered value for a key, or compute, remember and | ||||||||||||||||||||||||||||
| 132 | return it. | ||||||||||||||||||||||||||||
| 133 | |||||||||||||||||||||||||||||
| 134 | Args: | ||||||||||||||||||||||||||||
| 135 | |||||||||||||||||||||||||||||
| 136 | =over 4 | ||||||||||||||||||||||||||||
| 137 | |||||||||||||||||||||||||||||
| 138 | =item 1. The key (a string). | ||||||||||||||||||||||||||||
| 139 | |||||||||||||||||||||||||||||
| 140 | =item 2. How many seconds to remember a new value. 0 (or less) means | ||||||||||||||||||||||||||||
| 141 | "do not remember": the value is computed every time. | ||||||||||||||||||||||||||||
| 142 | |||||||||||||||||||||||||||||
| 143 | =item 3. A code reference that computes the value. | ||||||||||||||||||||||||||||
| 144 | |||||||||||||||||||||||||||||
| 145 | =back | ||||||||||||||||||||||||||||
| 146 | |||||||||||||||||||||||||||||
| 147 | Returns: the value (it may be C<undef>, which is remembered like any other). | ||||||||||||||||||||||||||||
| 148 | |||||||||||||||||||||||||||||
| 149 | Side Effects: may call the code reference; may forget the oldest entries to | ||||||||||||||||||||||||||||
| 150 | stay under C<max_bytes>. A value too big to fit at all is returned but not | ||||||||||||||||||||||||||||
| 151 | remembered. If the code dies, the error is passed on and nothing is | ||||||||||||||||||||||||||||
| 152 | remembered. | ||||||||||||||||||||||||||||
| 153 | |||||||||||||||||||||||||||||
| 154 | Usage: | ||||||||||||||||||||||||||||
| 155 | |||||||||||||||||||||||||||||
| 156 | my $value = $cache->compute($key, $seconds, sub { ... }); | ||||||||||||||||||||||||||||
| 157 | |||||||||||||||||||||||||||||
| 158 | =head3 EXAMPLE | ||||||||||||||||||||||||||||
| 159 | |||||||||||||||||||||||||||||
| 160 | my $calls = 0; | ||||||||||||||||||||||||||||
| 161 | my $get = sub { $cache->compute('k', 60, sub { ++$calls }) }; | ||||||||||||||||||||||||||||
| 162 | $get->(); # 1: computed | ||||||||||||||||||||||||||||
| 163 | $get->(); # 1: remembered; $calls is still 1 | ||||||||||||||||||||||||||||
| 164 | |||||||||||||||||||||||||||||
| 165 | =head3 API SPECIFICATION | ||||||||||||||||||||||||||||
| 166 | |||||||||||||||||||||||||||||
| 167 | =head4 INPUT | ||||||||||||||||||||||||||||
| 168 | |||||||||||||||||||||||||||||
| 169 | { | ||||||||||||||||||||||||||||
| 170 | key => { type => 'string', position => 0 }, | ||||||||||||||||||||||||||||
| 171 | ttl => { type => 'number', position => 1 }, | ||||||||||||||||||||||||||||
| 172 | code => { type => 'coderef', position => 2 }, | ||||||||||||||||||||||||||||
| 173 | } | ||||||||||||||||||||||||||||
| 174 | |||||||||||||||||||||||||||||
| 175 | The arguments are not validated: this is called for every datagram, and its | ||||||||||||||||||||||||||||
| 176 | only caller is App::Syslogd. | ||||||||||||||||||||||||||||
| 177 | |||||||||||||||||||||||||||||
| 178 | =head4 OUTPUT | ||||||||||||||||||||||||||||
| 179 | |||||||||||||||||||||||||||||
| 180 | { type => 'any', optional => 1 } | ||||||||||||||||||||||||||||
| 181 | |||||||||||||||||||||||||||||
| 182 | =head3 MESSAGES | ||||||||||||||||||||||||||||
| 183 | |||||||||||||||||||||||||||||
| 184 | None of its own; an error from the code reference is passed on. | ||||||||||||||||||||||||||||
| 185 | |||||||||||||||||||||||||||||
| 186 | =head3 PSEUDOCODE | ||||||||||||||||||||||||||||
| 187 | |||||||||||||||||||||||||||||
| 188 | if the key has an entry that has not expired: return its value | ||||||||||||||||||||||||||||
| 189 | value = code() | ||||||||||||||||||||||||||||
| 190 | if ttl <= 0: return value (not remembered) | ||||||||||||||||||||||||||||
| 191 | forget any old entry for the key | ||||||||||||||||||||||||||||
| 192 | size = length(key) + length(value) + 64 | ||||||||||||||||||||||||||||
| 193 | if size > max_bytes: return value (too big to remember) | ||||||||||||||||||||||||||||
| 194 | while the entries plus size would exceed max_bytes: | ||||||||||||||||||||||||||||
| 195 | forget the oldest entry | ||||||||||||||||||||||||||||
| 196 | remember the value until now + ttl | ||||||||||||||||||||||||||||
| 197 | if the age queue has grown well past the entries: rebuild it | ||||||||||||||||||||||||||||
| 198 | return value | ||||||||||||||||||||||||||||
| 199 | |||||||||||||||||||||||||||||
| 200 | =cut | ||||||||||||||||||||||||||||
| 201 | |||||||||||||||||||||||||||||
| 202 | sub compute | ||||||||||||||||||||||||||||
| 203 | 3083 | ▶ | { | ||||||||||||||||||||||||||
|
Subroutine
compute: called CC=12 SCAR=24.8
Pod
documented
| |||||||||||||||||||||||||||||
| 204 | 3083 | my ($self, $key, $ttl, $code) = @_; | |||||||||||||||||||||||||||
| 205 | |||||||||||||||||||||||||||||
| 206 | # The fast path: a value that has not expired | ||||||||||||||||||||||||||||
| 207 | 3083 | my $entry = $self->{entries}{$key}; | |||||||||||||||||||||||||||
| 208 | 3083 | ▶ | return $entry->[0] if($entry && $entry->[1] > time()); | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$entry and $entry->[1] > time
MC/DC100%2/2
$entry and $entry->[1] > time
$entry
$entry->[1] > time
Truth table100%3/3
A and B
A= $entryB= $entry->[1] > time
| |||||||||||||||||||||||||||||
| 209 | |||||||||||||||||||||||||||||
| 210 | 3063 | my $value = $code->(); | |||||||||||||||||||||||||||
| 211 | 3060 | ▶ | return $value unless($ttl > 0); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 212 | |||||||||||||||||||||||||||||
| 213 | # Forget the old (expired) entry before charging for the new one | ||||||||||||||||||||||||||||
| 214 | 2688 | ▶ | $self->{bytes} -= delete($self->{entries}{$key})->[2] if($entry); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 215 | |||||||||||||||||||||||||||||
| 216 | 2688 | ▶ | my $size = length($key) + length($value // '') + $ENTRY_OVERHEAD; | ||||||||||||||||||||||||||
|
Condition100%2/2
$value // ""
MC/DC100%1/1
$value // ""
$value
Truth table100%2/2
A
A= $value
| |||||||||||||||||||||||||||||
| 217 | 2688 | ▶ | return $value if($size > $self->{max_bytes}); | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 218 | |||||||||||||||||||||||||||||
| 219 | # Make room, oldest first. Queue items whose serial no longer matches | ||||||||||||||||||||||||||||
| 220 | # are left over from replaced entries, and are just dropped. | ||||||||||||||||||||||||||||
| 221 | 2685 | my $order = $self->{order}; | |||||||||||||||||||||||||||
| 222 | 2685 | ▶ | while($self->{bytes} + $size > $self->{max_bytes}) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 223 | 1629 | ▶ | my $item = shift(@{$order}) or last; # cannot happen while bytes is right | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 224 | 1628 | my ($old_key, $old_serial) = @{$item}; | |||||||||||||||||||||||||||
| 225 | 1628 | my $old = $self->{entries}{$old_key}; | |||||||||||||||||||||||||||
| 226 | 1628 | ▶ | next unless($old && $old->[3] == $old_serial); | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$old and $old->[3] == $old_serial
MC/DC100%2/2
$old and $old->[3] == $old_serial
$old
$old->[3] == $old_serial
Truth table100%3/3
A and B
A= $oldB= $old->[3] == $old_serial
| |||||||||||||||||||||||||||||
| 227 | 1626 | delete $self->{entries}{$old_key}; | |||||||||||||||||||||||||||
| 228 | 1626 | $self->{bytes} -= $old->[2]; | |||||||||||||||||||||||||||
| 229 | } | ||||||||||||||||||||||||||||
| 230 | |||||||||||||||||||||||||||||
| 231 | 2685 | my $serial = ++$self->{serial}; | |||||||||||||||||||||||||||
| 232 | 2685 | $self->{entries}{$key} = [$value, time() + $ttl, $size, $serial]; | |||||||||||||||||||||||||||
| 233 | 2685 | $self->{bytes} += $size; | |||||||||||||||||||||||||||
| 234 | 2685 | push @{$order}, [$key, $serial]; | |||||||||||||||||||||||||||
| 235 | |||||||||||||||||||||||||||||
| 236 | # A key that is replaced again and again leaves stale queue items; | ||||||||||||||||||||||||||||
| 237 | # rebuild the queue from the live entries before they pile up | ||||||||||||||||||||||||||||
| 238 | 2685 | ▶ | if(@{$order} > $QUEUE_SLACK * keys(%{$self->{entries}}) + 1) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 239 | 251 | my $entries = $self->{entries}; | |||||||||||||||||||||||||||
| 240 | 502 | @{$order} = map { [$_, $entries->{$_}[3]] } | |||||||||||||||||||||||||||
| 241 | 251 | sort { $entries->{$a}[3] <=> $entries->{$b}[3] } keys %{$entries}; | |||||||||||||||||||||||||||
| 242 | } | ||||||||||||||||||||||||||||
| 243 | |||||||||||||||||||||||||||||
| 244 | 2685 | return $value; | |||||||||||||||||||||||||||
| 245 | } | ||||||||||||||||||||||||||||
| 246 | |||||||||||||||||||||||||||||
| 247 | =head1 LIMITATIONS | ||||||||||||||||||||||||||||
| 248 | |||||||||||||||||||||||||||||
| 249 | The size limit is an estimate: Perl's real memory use per entry depends on | ||||||||||||||||||||||||||||
| 250 | its build and the strings stored. Expired entries are only removed when | ||||||||||||||||||||||||||||
| 251 | their key is looked up again or when space is needed, not on a timer. | ||||||||||||||||||||||||||||
| 252 | Times are whole seconds. | ||||||||||||||||||||||||||||
| 253 | |||||||||||||||||||||||||||||
| 254 | =head1 AUTHOR | ||||||||||||||||||||||||||||
| 255 | |||||||||||||||||||||||||||||
| 256 | Nigel Horne, C<< <njh at nigelhorne.com> >> | ||||||||||||||||||||||||||||
| 257 | |||||||||||||||||||||||||||||
| 258 | =head1 LICENSE AND COPYRIGHT | ||||||||||||||||||||||||||||
| 259 | |||||||||||||||||||||||||||||
| 260 | Copyright 2026 Nigel Horne. | ||||||||||||||||||||||||||||
| 261 | |||||||||||||||||||||||||||||
| 262 | This program is released under the GNU General Public License, version 2 | ||||||||||||||||||||||||||||
| 263 | (see the F<LICENSE> file). If you use it, please let me know. | ||||||||||||||||||||||||||||
| 264 | |||||||||||||||||||||||||||||
| 265 | =head1 FORMAL SPECIFICATION | ||||||||||||||||||||||||||||
| 266 | |||||||||||||||||||||||||||||
| 267 | =head2 new | ||||||||||||||||||||||||||||
| 268 | |||||||||||||||||||||||||||||
| 269 | Cache | ||||||||||||||||||||||||||||
| 270 | entries : KEY ⇸ (VALUE × TIME × ℕ × ℕ) | ||||||||||||||||||||||||||||
| 271 | max_bytes, bytes : ℕ | ||||||||||||||||||||||||||||
| 272 | ───────── | ||||||||||||||||||||||||||||
| 273 | bytes = Σ { k : dom entries • size(entries(k)) } ∧ bytes ≤ max_bytes | ||||||||||||||||||||||||||||
| 274 | |||||||||||||||||||||||||||||
| 275 | New | ||||||||||||||||||||||||||||
| 276 | Cache' | ||||||||||||||||||||||||||||
| 277 | max? : ℕ₁ | ||||||||||||||||||||||||||||
| 278 | ───────── | ||||||||||||||||||||||||||||
| 279 | entries' = ∅ ∧ bytes' = 0 ∧ max_bytes' = max? | ||||||||||||||||||||||||||||
| 280 | |||||||||||||||||||||||||||||
| 281 | =head2 compute | ||||||||||||||||||||||||||||
| 282 | |||||||||||||||||||||||||||||
| 283 | Compute | ||||||||||||||||||||||||||||
| 284 | ΔCache | ||||||||||||||||||||||||||||
| 285 | k? : KEY ; ttl? : ℤ ; code? : → VALUE ; v! : VALUE | ||||||||||||||||||||||||||||
| 286 | ───────── | ||||||||||||||||||||||||||||
| 287 | k? ∈ dom entries ∧ expiry(entries(k?)) > now ⇒ | ||||||||||||||||||||||||||||
| 288 | v! = value(entries(k?)) ∧ θCache' = θCache | ||||||||||||||||||||||||||||
| 289 | otherwise ⇒ | ||||||||||||||||||||||||||||
| 290 | v! = code?() ∧ | ||||||||||||||||||||||||||||
| 291 | (ttl? ≤ 0 ∨ size(k?, v!) > max_bytes ⇒ k? ∉ dom entries') ∧ | ||||||||||||||||||||||||||||
| 292 | (ttl? > 0 ∧ size(k?, v!) ≤ max_bytes ⇒ | ||||||||||||||||||||||||||||
| 293 | entries'(k?) = (v!, now + ttl?, size(k?, v!), serial') ∧ | ||||||||||||||||||||||||||||
| 294 | ∀ k : dom entries' \ {k?} • k ∈ dom entries ∧ | ||||||||||||||||||||||||||||
| 295 | (∀ j : dom entries \ dom entries' • serial(entries(j)) < | ||||||||||||||||||||||||||||
| 296 | min(serial ∘ entries' (dom entries')))) ∧ | ||||||||||||||||||||||||||||
| 297 | bytes' ≤ max_bytes | ||||||||||||||||||||||||||||
| 298 | |||||||||||||||||||||||||||||
| 299 | =head1 STATE DIAGRAM | ||||||||||||||||||||||||||||
| 300 | |||||||||||||||||||||||||||||
| 301 | new() | ||||||||||||||||||||||||||||
| 302 | | | ||||||||||||||||||||||||||||
| 303 | v | ||||||||||||||||||||||||||||
| 304 | compute(k) hit +-------+ compute(k) miss, ttl > 0, fits | ||||||||||||||||||||||||||||
| 305 | +--------------->| CACHE |------------------------------------+ | ||||||||||||||||||||||||||||
| 306 | | [return the +-------+ [compute; drop oldest entries | | ||||||||||||||||||||||||||||
| 307 | | value] ^ until it fits; remember until | | ||||||||||||||||||||||||||||
| 308 | +--------------------+ now + ttl] | | ||||||||||||||||||||||||||||
| 309 | +----------------------------------------+ | ||||||||||||||||||||||||||||
| 310 | compute(k) miss with ttl <= 0, or too big: [compute; return; nothing kept] | ||||||||||||||||||||||||||||
| 311 | code dies: [error passed on; nothing kept] | ||||||||||||||||||||||||||||
| 312 | |||||||||||||||||||||||||||||
| 313 | =cut | ||||||||||||||||||||||||||||
| 314 | |||||||||||||||||||||||||||||
| 315 | 51 | 1; | |||||||||||||||||||||||||||