Line data Source code
1 : // SPDX-License-Identifier: EUPL-1.2
2 : //! Process-wide cache of compiled regular expressions.
3 : //!
4 : //! Two NGSI-LD surfaces carry a client-supplied regular expression. The query
5 : //! language, 4.9 **Match pattern** (production rule `patternOp`): "A matching
6 : //! entity shall contain the target element and the target value shall be in
7 : //! the L(R) of the regular pattern specified by the Query Term" — and its
8 : //! `notPatternOp` mirror. And `idPattern`, on an EntitySelector (5.2.33), an
9 : //! EntityInfo (5.2.8) and the query parameters of Table 6.4.3.2-1.
10 : //!
11 : //! Both are evaluated per candidate entity and, for a subscription, per event
12 : //! per subscription — while the pattern text belongs to the query or the
13 : //! subscription, not to the candidate. Compiling at the point of use
14 : //! therefore pays `Regex::new` again for every candidate; compiling through
15 : //! here pays it once per distinct pattern and hands out a shared program.
16 : //!
17 : //! One compile has to be bounded and a pattern has to be compiled at most
18 : //! once, because both numbers are multiplied by the candidate count.
19 : //! `regex` builds an automaton whose size follows counted repetition of a
20 : //! character class rather than pattern length, so a 21-byte pattern can ask
21 : //! for a 16 MiB program and the tenth of a second that costs;
22 : //! `MAX_REGEX_PROGRAM_BYTES` is the ceiling on that, and a pattern above it
23 : //! is refused with the builder's own error — the error every call site
24 : //! already maps, so an over-large `idPattern` keeps the 400 BadRequestData
25 : //! its call site returns (Table 6.3.2-1) and an over-large `~=` operand
26 : //! keeps having no L(R), i.e. matching nothing (4.9), exactly as a
27 : //! syntactically invalid one does.
28 : //!
29 : //! Every outcome is retained, refusals included, so no pattern is compiled
30 : //! twice. Retention is bounded in entries and in bytes —
31 : //! `MAX_REGEX_CACHE` and `MAX_REGEX_CACHE_BYTES` — because the key is
32 : //! client input and an unbounded map of it is a memory attack, not a cache.
33 : //! Crossing a bound drops the least recently used half, never the whole map:
34 : //! a subscription fan-out evaluates the same few patterns per event, and
35 : //! dropping those along with the one-off pattern that overflowed the map
36 : //! makes every one of them recompile at once, on the request that was
37 : //! unlucky enough to cross the line.
38 :
39 : /// Ceiling on the automaton compiled for one pattern, and with it on what
40 : /// one compile costs. The pattern is client input — the
41 : /// `patternOp`/`notPatternOp` operand of a query term (4.9) and the
42 : /// `idPattern` of an EntitySelector (5.2.33), an EntityInfo (5.2.8) or a
43 : /// query parameter (Table 6.4.3.2-1) — and program size does not follow
44 : /// pattern length: `(?:\p{Any}{100}){100}` is 21 bytes and compiles to
45 : /// 16 MiB. Ordinary patterns sit far below the ceiling —
46 : /// `^urn:ngsi-ld:Vehicle:.*$` compiles to 2 KiB,
47 : /// `^urn:ngsi-ld:(Vehicle|Sensor|Building):[A-Za-z0-9_-]{1,64}$` to 16 KiB,
48 : /// a fifty-way alternation of URNs to 128 KiB — and one above it is refused
49 : /// rather than compiled, so no request can buy an unbounded automaton.
50 : pub const MAX_REGEX_PROGRAM_BYTES: usize = 256 * 1024;
51 : /// Distinct patterns retained. A `q` is capped at 4 KiB and so carries at
52 : /// most a low hundreds of distinct patterns, which the cache holds whole:
53 : /// one request never evicts its own working set.
54 : pub const MAX_REGEX_CACHE: usize = 1024;
55 : /// Retained bytes. Each entry is charged the tier it compiled within, not
56 : /// its true size, plus its key and, for a refusal, its message — both
57 : /// client-sized, a syntax error reprinting the pattern — so the number is an
58 : /// upper bound on what the map holds.
59 : pub const MAX_REGEX_CACHE_BYTES: usize = 64 * 1024 * 1024;
60 :
61 : /// A program that fits this is charged this much against
62 : /// [`MAX_REGEX_CACHE_BYTES`]; anything larger is charged the full
63 : /// [`MAX_REGEX_PROGRAM_BYTES`]. Almost every pattern a deployment writes
64 : /// lands in the first tier, so the byte budget holds thousands of
65 : /// Subscription `idPattern`s and still bounds a mix of the largest programs
66 : /// the ceiling admits.
67 : const PROGRAM_TIER_BYTES: usize = 32 * 1024;
68 :
69 : use std::collections::HashMap;
70 : use std::sync::atomic::{AtomicU64, AtomicUsize, Ordering};
71 : use std::sync::{Arc, LazyLock, RwLock};
72 :
73 : /// What a pattern compiled to, or the refusal it earned. A refusal is
74 : /// retained as its message so the pattern is not rebuilt per candidate.
75 : type Outcome = Result<Arc<regex::Regex>, Box<str>>;
76 :
77 : /// A retained entry: what it holds and when it was last handed out. `Entry`
78 : /// is what the eviction below orders by, so every cache here stores one.
79 : type Entry<V> = (V, AtomicU64);
80 :
81 : /// Source of the use stamps. Wrapping after 2^64 hand-outs would mis-order
82 : /// one eviction; nothing else depends on it.
83 : static CLOCK: AtomicU64 = AtomicU64::new(0);
84 :
85 13827 : fn stamp<V>(v: V) -> Entry<V> {
86 13827 : (v, AtomicU64::new(CLOCK.fetch_add(1, Ordering::Relaxed)))
87 13827 : }
88 :
89 : /// Record that an entry was just handed out. Done under the READ lock — the
90 : /// stamp is the only mutable part of an entry, and ordering evictions is the
91 : /// only thing that reads it, so a lost update costs one entry a place in the
92 : /// order and nothing else.
93 41177 : fn touch<V>(e: &Entry<V>) -> &V {
94 41177 : e.1.store(CLOCK.fetch_add(1, Ordering::Relaxed), Ordering::Relaxed);
95 41177 : &e.0
96 41177 : }
97 :
98 : /// Drop the least recently used half. The entries a request in flight is
99 : /// using were stamped by that request, so they are on the surviving side:
100 : /// crossing a bound costs the pattern that crossed it, not the working set.
101 30 : fn evict_lru_half<V>(map: &mut HashMap<Box<str>, Entry<V>>) {
102 30 : let keep = map.len() / 2;
103 30 : if keep == 0 {
104 4 : map.clear();
105 4 : return;
106 26 : }
107 22430 : let mut stamps: Vec<u64> = map.values().map(|e| e.1.load(Ordering::Relaxed)).collect();
108 26 : stamps.sort_unstable();
109 : // `keep` newest survive; a tie on the boundary stamp keeps both, which
110 : // costs at most a few entries over the half and never a bound.
111 26 : let Some(&cut) = stamps.len().checked_sub(keep).and_then(|i| stamps.get(i)) else {
112 0 : return;
113 : };
114 22430 : map.retain(|_, e| e.1.load(Ordering::Relaxed) >= cut);
115 30 : }
116 :
117 : /// One bounded cache: client-supplied text to what it compiled or parsed
118 : /// to, each entry carrying the stamp [`evict_lru_half`] orders by.
119 : type Cache<V> = LazyLock<RwLock<HashMap<Box<str>, Entry<V>>>>;
120 :
121 31 : static CACHE: Cache<(Outcome, usize)> = LazyLock::new(|| RwLock::new(HashMap::new()));
122 : #[cfg(test)]
123 : thread_local! {
124 : /// Compilations on this thread. Per thread, so a test counts its own cache misses and never
125 : /// those of a test running beside it; a compile runs on the caller's thread.
126 : static COMPILES: std::cell::Cell<u64> = const { std::cell::Cell::new(0) };
127 : }
128 : static BYTES: AtomicUsize = AtomicUsize::new(0);
129 :
130 12237 : fn build(pattern: &str, limit: usize) -> Result<regex::Regex, regex::Error> {
131 12237 : regex::RegexBuilder::new(pattern).size_limit(limit).build()
132 12237 : }
133 :
134 : /// The compiled program for `pattern`, shared with every other caller that
135 : /// asked for the same pattern text. `Err` carries the builder's own message
136 : /// — a syntax error, or the refusal of a program above
137 : /// [`MAX_REGEX_PROGRAM_BYTES`] — and each call site keeps mapping it to its
138 : /// own spec error.
139 52038 : pub fn compile(pattern: &str) -> Result<Arc<regex::Regex>, String> {
140 52038 : if let Some(hit) = CACHE
141 52038 : .read()
142 52038 : .ok()
143 52038 : .and_then(|c| c.get(pattern).map(|e| touch(e).0.clone()))
144 : {
145 40455 : return hit.map_err(String::from);
146 11583 : }
147 : #[cfg(test)]
148 10663 : COMPILES.with(|n| n.set(n.get().saturating_add(1)));
149 : // Compiled OUTSIDE the lock — a pattern compile must never serialize the
150 : // matcher — and a poisoned lock degrades to "compile every time", never
151 : // to a failed request.
152 11583 : let (outcome, charge): (Outcome, usize) = match build(pattern, PROGRAM_TIER_BYTES) {
153 10931 : Ok(re) => (Ok(Arc::new(re)), PROGRAM_TIER_BYTES),
154 652 : Err(_) => match build(pattern, MAX_REGEX_PROGRAM_BYTES) {
155 602 : Ok(re) => (Ok(Arc::new(re)), MAX_REGEX_PROGRAM_BYTES),
156 : // A refusal retains a message, not a program.
157 50 : Err(e) => (Err(e.to_string().into()), 0),
158 : },
159 : };
160 : // The key and a refusal's message are as long as the client made them:
161 : // charged, or a few oversized patterns pin memory the budget never sees.
162 11583 : let charge = charge
163 11583 : .saturating_add(pattern.len())
164 11583 : .saturating_add(outcome.as_ref().err().map_or(0, |m| m.len()));
165 : // An entry past the whole budget is not retained at all: the bound holds.
166 11583 : if let Some(mut c) = CACHE
167 11583 : .write()
168 11583 : .ok()
169 11583 : .filter(|_| charge <= MAX_REGEX_CACHE_BYTES)
170 11583 : {
171 11583 : retain(&mut c, pattern, outcome.clone(), charge);
172 11583 : }
173 11583 : outcome.map_err(String::from)
174 52038 : }
175 :
176 : /// Retain one compile outcome charged `charge` bytes, evicting first so both
177 : /// bounds hold, and keep [`BYTES`] the sum of what the map holds.
178 11587 : fn retain(
179 11587 : c: &mut HashMap<Box<str>, Entry<(Outcome, usize)>>,
180 11587 : pattern: &str,
181 11587 : outcome: Outcome,
182 11587 : charge: usize,
183 11587 : ) {
184 : // Halving is repeated rather than assumed sufficient: one charge can
185 : // be the whole byte budget's worth of the tier above, so the loop —
186 : // which halves what is left each pass — is what makes the bound hold.
187 11587 : let mut bytes = BYTES.load(Ordering::Relaxed);
188 11609 : while !c.is_empty()
189 11578 : && (c.len() >= MAX_REGEX_CACHE || bytes.saturating_add(charge) > MAX_REGEX_CACHE_BYTES)
190 : {
191 22 : evict_lru_half(c);
192 22 : bytes = c.values().map(|e| e.0 .1).sum();
193 : }
194 : // Two callers that missed the same pattern at once both compile and both
195 : // retain it: the second entry replaces the first, and so does its charge.
196 11587 : let replaced = c
197 11587 : .insert(pattern.into(), stamp((outcome, charge)))
198 11587 : .map_or(0, |e| e.0 .1);
199 11587 : BYTES.store(
200 11587 : bytes.saturating_add(charge).saturating_sub(replaced),
201 11587 : Ordering::Relaxed,
202 : );
203 11587 : }
204 :
205 : /// The retained program for `pattern`, without compiling anything. A
206 : /// retained refusal holds no program and reads as `None` here.
207 640 : pub fn cached(pattern: &str) -> Option<Arc<regex::Regex>> {
208 640 : CACHE.read().ok().and_then(|c| {
209 640 : c.get(pattern)
210 640 : .and_then(|e| touch(e).0.as_ref().ok())
211 640 : .cloned()
212 640 : })
213 640 : }
214 :
215 : /// Compilations performed on the calling thread (i.e. its cache misses).
216 : #[cfg(test)]
217 10 : fn compiles() -> u64 {
218 10 : COMPILES.with(std::cell::Cell::get)
219 10 : }
220 :
221 : /// Patterns currently retained — never above `MAX_REGEX_CACHE`.
222 6152 : pub fn len() -> usize {
223 6152 : CACHE.read().map(|c| c.len()).unwrap_or(0)
224 6152 : }
225 :
226 : /// Program bytes currently charged — never above `MAX_REGEX_CACHE_BYTES`.
227 6752 : pub fn retained_bytes() -> usize {
228 6752 : BYTES.load(Ordering::Relaxed)
229 6752 : }
230 :
231 16 : static Q_CACHE: Cache<Arc<crate::QNode>> = LazyLock::new(|| RwLock::new(HashMap::new()));
232 4 : static GEO_CACHE: Cache<Arc<crate::geo::GeoQuery>> = LazyLock::new(|| RwLock::new(HashMap::new()));
233 :
234 : /// The parsed 4.9 query for `q`, shared across every event that evaluates the
235 : /// same subscription. Like the regex cache this changes no outcome: only an
236 : /// `Ok` parse is retained, so an invalid or over-complex `q` keeps exactly
237 : /// the handling its call site has (`parse_q` is re-run and its error stands).
238 : /// Entry size is already capped by the parser's own complexity ceiling
239 : /// (`MAX_Q_NODES`), entry count by the same bound and eviction as above.
240 2294 : pub fn q_node(q: &str) -> Option<Arc<crate::QNode>> {
241 2294 : if let Some(hit) = Q_CACHE
242 2294 : .read()
243 2294 : .ok()
244 2294 : .and_then(|c| c.get(q).map(|e| Arc::clone(touch(e))))
245 : {
246 68 : return Some(hit);
247 2226 : }
248 2226 : let node = Arc::new(crate::parse_q(q).ok()?);
249 2212 : if let Ok(mut c) = Q_CACHE.write() {
250 2212 : if c.len() >= MAX_REGEX_CACHE {
251 2 : evict_lru_half(&mut c);
252 2210 : }
253 2212 : c.insert(q.into(), stamp(Arc::clone(&node)));
254 0 : }
255 2212 : Some(node)
256 2294 : }
257 :
258 : /// The parsed geoquery (4.10) for a subscription's `geoQ`, keyed by the
259 : /// caller's serialization of that member. `build` runs on a miss and only a
260 : /// `Some` is retained — a `geoQ` that does not parse keeps failing exactly as
261 : /// before, per call. Geometry size is already capped at the parse
262 : /// (`MAX_GEO_VERTICES`), entry count by the same bound and eviction.
263 28 : pub fn geo_query(
264 28 : key: &str,
265 28 : build: impl FnOnce() -> Option<crate::geo::GeoQuery>,
266 28 : ) -> Option<Arc<crate::geo::GeoQuery>> {
267 28 : if let Some(hit) = GEO_CACHE
268 28 : .read()
269 28 : .ok()
270 28 : .and_then(|c| c.get(key).map(|e| Arc::clone(touch(e))))
271 : {
272 12 : return Some(hit);
273 16 : }
274 16 : let gq = Arc::new(build()?);
275 : // ponytail: a key above MAX_GEO_KEY_BYTES is built per call and never
276 : // retained, so the cache holds at most MAX_REGEX_CACHE keys of at most
277 : // that size (64 MiB, the regex cache's byte budget)
278 12 : if key.len() > MAX_GEO_KEY_BYTES {
279 2 : return Some(gq);
280 10 : }
281 10 : if let Ok(mut c) = GEO_CACHE.write() {
282 10 : if c.len() >= MAX_REGEX_CACHE {
283 0 : evict_lru_half(&mut c);
284 10 : }
285 10 : c.insert(key.into(), stamp(Arc::clone(&gq)));
286 0 : }
287 10 : Some(gq)
288 28 : }
289 :
290 : /// The largest `geoQ` serialization [`geo_query`] retains. The key, and the
291 : /// geometry parsed from it, follow the client's vertex count: without a
292 : /// per-entry ceiling the entry bound alone let 1024 of the largest
293 : /// geometries the parser admits pin memory no budget counted.
294 : const MAX_GEO_KEY_BYTES: usize = MAX_REGEX_CACHE_BYTES / MAX_REGEX_CACHE;
295 :
296 : /// Test-only serialization: a test that flushes the shared cache must not
297 : /// race the tests asserting what is retained.
298 : #[cfg(test)]
299 28 : pub(crate) fn serial_lock() -> std::sync::MutexGuard<'static, ()> {
300 : static SERIAL: std::sync::Mutex<()> = std::sync::Mutex::new(());
301 28 : SERIAL.lock().unwrap_or_else(|poison| poison.into_inner())
302 28 : }
303 :
304 : // regex compiles run for hours under Miri; the fuzz job covers them
305 : #[cfg(all(test, not(miri)))]
306 : mod tests {
307 : use super::*;
308 :
309 6 : fn near_point() -> Option<crate::geo::GeoQuery> {
310 6 : crate::geo::GeoQuery::from_params(&HashMap::from([
311 6 : ("georel".to_owned(), "near;maxDistance==10".to_owned()),
312 6 : ("geometry".to_owned(), "Point".to_owned()),
313 6 : ("coordinates".to_owned(), "[1,2]".to_owned()),
314 6 : ]))
315 6 : .ok()
316 6 : .flatten()
317 6 : }
318 :
319 : /// The same pattern text is compiled once: the second call gets the very
320 : /// program the first one built (4.9 patternOp / 5.2.33 idPattern are
321 : /// evaluated per candidate, so this identity is the whole point).
322 : #[test]
323 2 : fn same_pattern_is_compiled_once() {
324 2 : let _serial = serial_lock();
325 2 : let p = "^urn:ngsi-ld:Vehicle:compiled-once-[0-9]+$";
326 2 : assert!(cached(p).is_none(), "cold pattern must not start retained");
327 2 : let before = compiles();
328 2 : let first = compile(p).expect("valid pattern");
329 2 : assert!(compiles() > before, "a cold pattern is compiled");
330 2 : let second = compile(p).expect("valid pattern");
331 2 : assert!(
332 2 : Arc::ptr_eq(&first, &second),
333 : "the second call must reuse the compiled program, not rebuild it"
334 : );
335 2 : assert!(
336 2 : cached(p).is_some_and(|c| Arc::ptr_eq(&c, &first)),
337 : "the cache holds that same program"
338 : );
339 2 : assert!(first.is_match("urn:ngsi-ld:Vehicle:compiled-once-7"));
340 2 : assert!(
341 2 : !first.is_match("urn:ngsi-ld:Vehicle:compiled-once-x"),
342 : "a shared program still rejects what the pattern excludes"
343 : );
344 2 : }
345 :
346 : /// An invalid pattern yields `Regex::new`'s own error, verbatim, so the
347 : /// spec error each call site maps it to is unchanged — an `idPattern`
348 : /// stays 400 BadRequestData (Table 6.3.2-1) and never becomes a 500.
349 : /// What is retained for it is the refusal, never a program.
350 : #[test]
351 2 : fn invalid_pattern_keeps_the_error_regex_new_returns() {
352 2 : let _serial = serial_lock();
353 14 : for p in ["[", "(", "a{2,1}", "(?P<", "*", "\\", "(?"] {
354 14 : let want = regex::Regex::new(p).map_err(|e| e.to_string());
355 14 : let got = compile(p).map(|_| ()).map_err(|e| e.to_string());
356 14 : assert!(want.is_err(), "fixture must be an invalid pattern: {p:?}");
357 14 : assert_eq!(
358 14 : got.map(|_| ()),
359 14 : want.map(|_| ()),
360 : "the cache must return the same error text for {p:?}"
361 : );
362 14 : assert!(cached(p).is_none(), "an invalid pattern yields no program");
363 14 : assert!(
364 14 : compile(p).is_err(),
365 : "and it stays an error on the second call for {p:?}"
366 : );
367 : }
368 2 : assert!(compile("^ok$").is_ok(), "a valid pattern is not rejected");
369 2 : }
370 :
371 : /// Retention is bounded in both dimensions: distinct patterns are
372 : /// client input, so many of them must grow the map past neither
373 : /// `MAX_REGEX_CACHE` nor `MAX_REGEX_CACHE_BYTES`, and the programs
374 : /// handed out across an eviction stay correct.
375 : #[test]
376 2 : fn cache_stays_bounded_under_many_distinct_patterns() {
377 2 : let _serial = serial_lock();
378 6144 : for i in 0..MAX_REGEX_CACHE * 3 {
379 6144 : let p = format!("^bounded-{i}-[a-z]+$");
380 6144 : let re = compile(&p).expect("valid pattern");
381 6144 : assert!(re.is_match(&format!("bounded-{i}-abc")));
382 6144 : assert!(!re.is_match(&format!("bounded-{i}-123")));
383 6144 : assert!(
384 6144 : len() <= MAX_REGEX_CACHE,
385 : "retained {} patterns after {i} distinct ones",
386 0 : len()
387 : );
388 6144 : assert!(
389 6144 : retained_bytes() <= MAX_REGEX_CACHE_BYTES,
390 : "charged {} bytes after {i} distinct patterns",
391 0 : retained_bytes()
392 : );
393 : }
394 2 : assert!(len() > 0, "the cache must still be caching after a flush");
395 2 : }
396 :
397 : /// A subscription fan-out evaluates the same `idPattern` per event while
398 : /// query traffic keeps bringing new `patternOp` operands in, so the
399 : /// working set and the entries that overflow a bound are different
400 : /// patterns. Crossing a bound must therefore cost the entries nothing is
401 : /// using: recompiling the live working set on the request unlucky enough
402 : /// to cross the line is the cost the eviction order exists to avoid.
403 : #[test]
404 2 : fn eviction_drops_the_least_recently_used_half() {
405 2 : let mut map: HashMap<Box<str>, Entry<u32>> = HashMap::new();
406 16 : for i in 0..8u32 {
407 16 : map.insert(format!("p{i}").into(), stamp(i));
408 16 : }
409 : // three of the eight are in use and are stamped again
410 6 : for k in ["p0", "p3", "p7"] {
411 6 : touch(map.get(k).expect("present"));
412 6 : }
413 2 : evict_lru_half(&mut map);
414 2 : assert_eq!(map.len(), 4, "half of eight is four");
415 6 : for k in ["p0", "p3", "p7"] {
416 6 : assert!(map.contains_key(k), "{k} was in use and must survive");
417 : }
418 : // the survivors are exactly the newest half: the fourth is the
419 : // newest of the untouched ones
420 2 : assert!(
421 2 : map.contains_key("p6"),
422 : "the newest untouched entry survives"
423 : );
424 8 : for k in ["p1", "p2", "p4", "p5"] {
425 8 : assert!(!map.contains_key(k), "{k} was the oldest and must go");
426 : }
427 2 : }
428 :
429 : /// The bound holds whatever the map's size, so the halving has to be
430 : /// defined at the sizes where "half" is not a whole entry.
431 : #[test]
432 2 : fn eviction_of_a_map_too_small_to_halve_empties_it() {
433 2 : let mut map: HashMap<Box<str>, Entry<u32>> = HashMap::new();
434 2 : evict_lru_half(&mut map);
435 2 : assert!(map.is_empty(), "an empty map stays empty");
436 2 : map.insert("only".into(), stamp(0));
437 2 : evict_lru_half(&mut map);
438 2 : assert!(map.is_empty(), "one entry cannot be halved and is dropped");
439 2 : }
440 :
441 : /// 4.9 evaluates a `patternOp` per candidate Entity and 5.2.33 an
442 : /// `idPattern` per event per Subscription, so an unbounded compile is
443 : /// multiplied by the candidate count. Program size follows counted
444 : /// repetition of a character class, not pattern length, so the bound
445 : /// has to be on the program: above the ceiling the pattern is refused,
446 : /// and the refusal is remembered so it costs one build pass, ever.
447 : #[test]
448 2 : fn a_program_above_the_ceiling_is_refused_once_not_rebuilt_per_candidate() {
449 2 : let _serial = serial_lock();
450 2 : let p = r"(?:\p{Any}{100}){100}";
451 2 : assert_eq!(p.len(), 21, "the fixture is what a client can send");
452 2 : assert!(
453 2 : build(p, MAX_REGEX_PROGRAM_BYTES).is_err(),
454 : "fixture must ask for a program above the ceiling"
455 : );
456 2 : let before = compiles();
457 2 : assert!(
458 2 : compile(p).is_err(),
459 : "a program above the ceiling is refused, not compiled"
460 : );
461 2 : let after = compiles();
462 2 : assert_eq!(after, before + 1, "one refusal costs one build pass");
463 2 : for _ in 0..64 {
464 128 : assert!(compile(p).is_err(), "and it stays refused");
465 : }
466 2 : assert_eq!(
467 2 : compiles(),
468 : after,
469 : "the refusal is remembered, not rebuilt for the next candidate"
470 : );
471 2 : assert!(cached(p).is_none(), "a refusal retains no program");
472 2 : }
473 :
474 : /// The ceiling bounds the automaton, not the expressiveness a
475 : /// deployment needs: the patterns an `idPattern` or a `~=` operand
476 : /// actually carries compile well inside it and are retained.
477 : #[test]
478 2 : fn the_ceiling_admits_the_patterns_a_deployment_writes() {
479 2 : let _serial = serial_lock();
480 10 : for p in [
481 2 : r"^urn:ngsi-ld:Vehicle:.*$",
482 2 : r"^urn:ngsi-ld:(Vehicle|Sensor|Building):[A-Za-z0-9_-]{1,64}$",
483 2 : r"^urn:ngsi-ld:Device:[0-9a-f]{8}-[0-9a-f]{4}-[0-9a-f]{4}-[0-9a-f]{4}-[0-9a-f]{12}$",
484 2 : r"(?i)^urn:ngsi-ld:vehicle:.*$",
485 2 : r"^\d{4}-\d{2}-\d{2}T\d{2}:\d{2}:\d{2}Z$",
486 2 : ] {
487 10 : assert!(compile(p).is_ok(), "the ceiling must not refuse {p:?}");
488 10 : assert!(
489 10 : cached(p).is_some(),
490 : "what the ceiling admits, the cache retains: {p:?}"
491 : );
492 : }
493 2 : }
494 :
495 : /// Below the bounds nothing is evicted: a parsed q, a built geoQ and
496 : /// 300 small programs all stay retained, and the counters report them
497 : /// (mutants on the eviction conditions and the byte charge).
498 : #[test]
499 2 : fn below_the_bounds_every_entry_is_kept() {
500 2 : let _serial = serial_lock();
501 2 : let a = q_node("keep_a>1").expect("valid q");
502 2 : q_node("keep_b>1").expect("valid q");
503 2 : assert!(Arc::ptr_eq(&a, &q_node("keep_a>1").expect("valid q")));
504 :
505 2 : let builds = std::cell::Cell::new(0);
506 4 : let build = || {
507 4 : builds.set(builds.get() + 1);
508 4 : near_point()
509 4 : };
510 2 : geo_query("keep-geo-a", build).expect("geo");
511 2 : geo_query("keep-geo-b", build).expect("geo");
512 2 : geo_query("keep-geo-a", build).expect("geo");
513 2 : assert_eq!(builds.get(), 2, "the first geoQ was evicted");
514 :
515 600 : let patterns: Vec<String> = (0..300).map(|i| format!("^keep-{i}$")).collect();
516 600 : for p in &patterns {
517 600 : compile(p).expect("compiles");
518 600 : }
519 600 : let missing = patterns.iter().filter(|p| cached(p).is_none()).count();
520 2 : assert_eq!(missing, 0, "{missing} of 300 small programs were evicted");
521 2 : assert!(len() >= 300);
522 : // the documented tier, written out: a small program costs 32 KiB
523 2 : assert!(retained_bytes() >= 300 * 32 * 1024);
524 2 : }
525 :
526 : /// Two callers that missed one pattern together both retain it; the
527 : /// charge follows the entry that stays, so the byte count is still the
528 : /// sum of what the map holds.
529 : #[test]
530 2 : fn retaining_one_pattern_twice_charges_it_once() {
531 2 : let _serial = serial_lock();
532 2 : let mut c = CACHE.write().expect("cache");
533 4 : let re = || Ok(Arc::new(regex::Regex::new("^twice$").expect("regex")));
534 2 : retain(&mut c, "^twice$", re(), 100);
535 2 : retain(&mut c, "^twice$", re(), 100);
536 2 : let held: usize = c.values().map(|e| e.0 .1).sum();
537 2 : assert_eq!(retained_bytes(), held, "the replaced entry stayed charged");
538 2 : }
539 :
540 : /// A geoQ larger than the per-entry ceiling is built per call and never
541 : /// retained: the cache's bytes stay bounded by entries times ceiling.
542 : #[test]
543 2 : fn an_oversized_geo_key_is_not_retained() {
544 2 : let _serial = serial_lock();
545 2 : let key = format!("big-geo-{}", "x".repeat(MAX_GEO_KEY_BYTES));
546 2 : geo_query(&key, near_point).expect("geo");
547 2 : assert!(
548 2 : GEO_CACHE
549 2 : .read()
550 2 : .is_ok_and(|c| !c.contains_key(key.as_str())),
551 : "an oversized geoQ key was retained"
552 : );
553 2 : }
554 :
555 : /// The byte budget evicts on its own, before the entry count does:
556 : /// programs past the 32 KiB tier are charged 256 KiB each, so ~260 of
557 : /// them overrun MAX_REGEX_CACHE_BYTES long before MAX_REGEX_CACHE.
558 : #[test]
559 2 : fn the_byte_budget_evicts_before_the_entry_count() {
560 2 : let _serial = serial_lock();
561 600 : for i in 0..300 {
562 600 : compile(&format!("^[a-z]{{{}}}$", 3000 + i)).expect("compiles");
563 600 : assert!(
564 600 : retained_bytes() <= MAX_REGEX_CACHE_BYTES,
565 : "after {i}: {} bytes retained",
566 0 : retained_bytes()
567 : );
568 : }
569 2 : assert!(len() < MAX_REGEX_CACHE);
570 2 : }
571 :
572 : /// A refusal's key and message are client-sized (a syntax error
573 : /// reprints the pattern), so the byte budget is charged for them: a
574 : /// retained refusal is never free.
575 : #[test]
576 2 : fn a_retained_refusal_is_charged_its_key_and_message() {
577 2 : let _serial = serial_lock();
578 2 : let before = retained_bytes();
579 2 : let p = format!("({}", "a".repeat(1 << 20));
580 2 : assert!(compile(&p).is_err());
581 2 : assert!(
582 2 : retained_bytes() >= before + p.len(),
583 : "a 1 MiB refusal was retained free of charge"
584 : );
585 2 : }
586 :
587 : /// The same q text parses once and every caller shares the tree; an
588 : /// invalid or over-complex q is parsed as before and never retained, so
589 : /// its call-site handling (no-match / 400) is unchanged.
590 : #[test]
591 2 : fn q_text_is_parsed_once_and_bad_q_is_not_retained() {
592 2 : let _serial = serial_lock();
593 2 : let q = r#"speed>20;brandName=="cache-q-probe""#;
594 2 : let first = q_node(q).expect("valid q");
595 2 : let second = q_node(q).expect("valid q");
596 2 : assert!(
597 2 : Arc::ptr_eq(&first, &second),
598 : "the second evaluation must reuse the parsed tree"
599 : );
600 8 : for bad in ["", "==5", "a==\"unterminated", "a==1)"] {
601 8 : assert!(q_node(bad).is_none(), "invalid q {bad:?} must not parse");
602 8 : assert!(
603 8 : Q_CACHE.read().is_ok_and(|c| !c.contains_key(bad)),
604 : "invalid q {bad:?} must not be retained"
605 : );
606 : }
607 : // boundedness under distinct client q texts
608 2176 : for i in 0..MAX_REGEX_CACHE + 64 {
609 2176 : q_node(&format!("qbound{i}>0")).expect("valid q");
610 2176 : assert!(
611 2176 : Q_CACHE.read().map(|c| c.len()).unwrap_or(usize::MAX) <= MAX_REGEX_CACHE,
612 : "q cache must stay bounded"
613 : );
614 : }
615 2 : }
616 :
617 : /// The geo cache shares one parsed geometry per distinct geoQ key, and a
618 : /// geoQ whose build fails is rebuilt (and re-fails) per call — never a
619 : /// cached wrong answer.
620 : #[test]
621 2 : fn geo_query_is_shared_per_key_and_failures_are_not_retained() {
622 2 : let _serial = serial_lock();
623 2 : let build_calls = std::sync::atomic::AtomicUsize::new(0);
624 4 : let params = || {
625 4 : let mut m = HashMap::new();
626 4 : m.insert("georel".to_owned(), "near;maxDistance==2000".to_owned());
627 4 : m.insert("geometry".to_owned(), "Point".to_owned());
628 4 : m.insert("coordinates".to_owned(), "[13.38,52.52]".to_owned());
629 4 : m
630 4 : };
631 4 : let build = || {
632 4 : build_calls.fetch_add(1, Ordering::Relaxed);
633 4 : crate::geo::GeoQuery::from_params(¶ms()).ok().flatten()
634 4 : };
635 2 : let first = geo_query("geo-probe-1", build).expect("valid geoQ");
636 2 : let second = geo_query("geo-probe-1", build).expect("valid geoQ");
637 2 : assert!(Arc::ptr_eq(&first, &second), "one parse per key");
638 2 : assert_eq!(
639 2 : build_calls.load(Ordering::Relaxed),
640 : 1,
641 : "the second call must not rebuild"
642 : );
643 2 : assert!(
644 2 : geo_query("geo-probe-bad", || None).is_none(),
645 : "a failing build yields None"
646 : );
647 2 : assert!(
648 2 : geo_query("geo-probe-bad", build).is_some(),
649 : "…and is not retained as a failure: the next build runs"
650 : );
651 2 : }
652 :
653 : /// Concurrent use: the same and different patterns compiled from many
654 : /// threads at once must stay correct and bounded, never deadlock, and
655 : /// never hand out a program built for another pattern.
656 : #[test]
657 2 : fn concurrent_compiles_are_safe() {
658 2 : let _serial = serial_lock();
659 2 : let pats = [
660 2 : ("^shared-a-[0-9]+$", "shared-a-1", "shared-a-x"),
661 2 : ("^shared-b-[a-z]+$", "shared-b-z", "shared-b-9"),
662 2 : ("shared-c", "xx-shared-c-xx", "shared-d"),
663 2 : ];
664 2 : let handles: Vec<_> = (0..8)
665 16 : .map(|t| {
666 16 : std::thread::spawn(move || {
667 3200 : for round in 0..200 {
668 3200 : let (p, hit, miss) = pats[round % pats.len()];
669 3200 : let re = compile(p).expect("valid pattern");
670 3200 : assert!(re.is_match(hit), "thread {t} pattern {p}");
671 3200 : assert!(!re.is_match(miss), "thread {t} pattern {p}");
672 : // a per-thread pattern exercises concurrent inserts
673 3200 : let own = format!("^t{t}-r{round}-[0-9]+$");
674 3200 : assert!(compile(&own)
675 3200 : .expect("valid")
676 3200 : .is_match(&format!("t{t}-r{round}-5")));
677 3200 : assert!(compile("[").is_err(), "invalid stays invalid");
678 : }
679 16 : })
680 16 : })
681 2 : .collect();
682 16 : for h in handles {
683 16 : h.join().expect("no thread panicked");
684 16 : }
685 2 : assert!(len() <= MAX_REGEX_CACHE, "still bounded after the race");
686 2 : assert!(
687 2 : cached("shared-c").is_some(),
688 : "a hot pattern survives concurrent use"
689 : );
690 2 : }
691 : }
|
