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 program bytes. Each entry is charged the tier it compiled
56 : /// within, not its true size, so the number is an upper bound on what the
57 : /// map holds.
58 : pub const MAX_REGEX_CACHE_BYTES: usize = 64 * 1024 * 1024;
59 :
60 : /// A program that fits this is charged this much against
61 : /// [`MAX_REGEX_CACHE_BYTES`]; anything larger is charged the full
62 : /// [`MAX_REGEX_PROGRAM_BYTES`]. Almost every pattern a deployment writes
63 : /// lands in the first tier, so the byte budget holds thousands of
64 : /// Subscription `idPattern`s and still bounds a mix of the largest programs
65 : /// the ceiling admits.
66 : const PROGRAM_TIER_BYTES: usize = 32 * 1024;
67 :
68 : use std::collections::HashMap;
69 : use std::sync::atomic::{AtomicU64, AtomicUsize, Ordering};
70 : use std::sync::{Arc, LazyLock, RwLock};
71 :
72 : /// What a pattern compiled to, or the refusal it earned. A refusal is
73 : /// retained as its message so the pattern is not rebuilt per candidate.
74 : type Outcome = Result<Arc<regex::Regex>, Box<str>>;
75 :
76 : /// A retained entry: what it holds and when it was last handed out. `Entry`
77 : /// is what the eviction below orders by, so every cache here stores one.
78 : type Entry<V> = (V, AtomicU64);
79 :
80 : /// Source of the use stamps. Wrapping after 2^64 hand-outs would mis-order
81 : /// one eviction; nothing else depends on it.
82 : static CLOCK: AtomicU64 = AtomicU64::new(0);
83 :
84 12605 : fn stamp<V>(v: V) -> Entry<V> {
85 12605 : (v, AtomicU64::new(CLOCK.fetch_add(1, Ordering::Relaxed)))
86 12605 : }
87 :
88 : /// Record that an entry was just handed out. Done under the READ lock — the
89 : /// stamp is the only mutable part of an entry, and ordering evictions is the
90 : /// only thing that reads it, so a lost update costs one entry a place in the
91 : /// order and nothing else.
92 37721 : fn touch<V>(e: &Entry<V>) -> &V {
93 37721 : e.1.store(CLOCK.fetch_add(1, Ordering::Relaxed), Ordering::Relaxed);
94 37721 : &e.0
95 37721 : }
96 :
97 : /// Drop the least recently used half. The entries a request in flight is
98 : /// using were stamped by that request, so they are on the surviving side:
99 : /// crossing a bound costs the pattern that crossed it, not the working set.
100 24 : fn evict_lru_half<V>(map: &mut HashMap<Box<str>, Entry<V>>) {
101 24 : let keep = map.len() / 2;
102 24 : if keep == 0 {
103 4 : map.clear();
104 4 : return;
105 20 : }
106 18448 : let mut stamps: Vec<u64> = map.values().map(|e| e.1.load(Ordering::Relaxed)).collect();
107 20 : stamps.sort_unstable();
108 : // `keep` newest survive; a tie on the boundary stamp keeps both, which
109 : // costs at most a few entries over the half and never a bound.
110 20 : let cut = stamps[stamps.len() - keep];
111 18448 : map.retain(|_, e| e.1.load(Ordering::Relaxed) >= cut);
112 24 : }
113 :
114 : /// One bounded cache: client-supplied text to what it compiled or parsed
115 : /// to, each entry carrying the stamp [`evict_lru_half`] orders by.
116 : type Cache<V> = LazyLock<RwLock<HashMap<Box<str>, Entry<V>>>>;
117 :
118 32 : static CACHE: Cache<(Outcome, usize)> = LazyLock::new(|| RwLock::new(HashMap::new()));
119 : static COMPILES: AtomicU64 = AtomicU64::new(0);
120 : static BYTES: AtomicUsize = AtomicUsize::new(0);
121 :
122 10425 : fn build(pattern: &str, limit: usize) -> Result<regex::Regex, regex::Error> {
123 10425 : regex::RegexBuilder::new(pattern).size_limit(limit).build()
124 10425 : }
125 :
126 : /// The compiled program for `pattern`, shared with every other caller that
127 : /// asked for the same pattern text. `Err` carries the builder's own message
128 : /// — a syntax error, or the refusal of a program above
129 : /// [`MAX_REGEX_PROGRAM_BYTES`] — and each call site keeps mapping it to its
130 : /// own spec error.
131 48000 : pub fn compile(pattern: &str) -> Result<Arc<regex::Regex>, String> {
132 48000 : if let Some(hit) = CACHE
133 48000 : .read()
134 48000 : .ok()
135 48000 : .and_then(|c| c.get(pattern).map(|e| touch(e).0.clone()))
136 : {
137 37617 : return hit.map_err(String::from);
138 10383 : }
139 10383 : COMPILES.fetch_add(1, Ordering::Relaxed);
140 : // Compiled OUTSIDE the lock — a pattern compile must never serialize the
141 : // matcher — and a poisoned lock degrades to "compile every time", never
142 : // to a failed request.
143 10383 : let (outcome, charge): (Outcome, usize) = match build(pattern, PROGRAM_TIER_BYTES) {
144 10343 : Ok(re) => (Ok(Arc::new(re)), PROGRAM_TIER_BYTES),
145 40 : Err(_) => match build(pattern, MAX_REGEX_PROGRAM_BYTES) {
146 2 : Ok(re) => (Ok(Arc::new(re)), MAX_REGEX_PROGRAM_BYTES),
147 : // A refusal retains a message, not a program.
148 38 : Err(e) => (Err(e.to_string().into()), 0),
149 : },
150 : };
151 10383 : if let Ok(mut c) = CACHE.write() {
152 : // Halving is repeated rather than assumed sufficient: one charge can
153 : // be the whole byte budget's worth of the tier above, so the loop —
154 : // which halves what is left each pass — is what makes the bound hold.
155 10383 : let mut bytes = BYTES.load(Ordering::Relaxed);
156 10399 : while !c.is_empty()
157 10367 : && (c.len() >= MAX_REGEX_CACHE || bytes.saturating_add(charge) > MAX_REGEX_CACHE_BYTES)
158 : {
159 16 : evict_lru_half(&mut c);
160 16 : bytes = c.values().map(|e| e.0 .1).sum();
161 : }
162 10383 : BYTES.store(bytes.saturating_add(charge), Ordering::Relaxed);
163 10383 : c.insert(pattern.into(), stamp((outcome.clone(), charge)));
164 0 : }
165 10383 : outcome.map_err(String::from)
166 48000 : }
167 :
168 : /// The retained program for `pattern`, without compiling anything. A
169 : /// retained refusal holds no program and reads as `None` here.
170 40 : pub fn cached(pattern: &str) -> Option<Arc<regex::Regex>> {
171 40 : CACHE.read().ok().and_then(|c| {
172 40 : c.get(pattern)
173 40 : .and_then(|e| touch(e).0.as_ref().ok())
174 40 : .cloned()
175 40 : })
176 40 : }
177 :
178 : /// Compilations performed since process start (i.e. cache misses).
179 10 : pub fn compiles() -> u64 {
180 10 : COMPILES.load(Ordering::Relaxed)
181 10 : }
182 :
183 : /// Patterns currently retained — never above `MAX_REGEX_CACHE`.
184 6148 : pub fn len() -> usize {
185 6148 : CACHE.read().map(|c| c.len()).unwrap_or(0)
186 6148 : }
187 :
188 : /// Program bytes currently charged — never above `MAX_REGEX_CACHE_BYTES`.
189 6144 : pub fn retained_bytes() -> usize {
190 6144 : BYTES.load(Ordering::Relaxed)
191 6144 : }
192 :
193 14 : static Q_CACHE: Cache<Arc<crate::QNode>> = LazyLock::new(|| RwLock::new(HashMap::new()));
194 4 : static GEO_CACHE: Cache<Arc<crate::geo::GeoQuery>> = LazyLock::new(|| RwLock::new(HashMap::new()));
195 :
196 : /// The parsed 4.9 query for `q`, shared across every event that evaluates the
197 : /// same subscription. Like the regex cache this changes no outcome: only an
198 : /// `Ok` parse is retained, so an invalid or over-complex `q` keeps exactly
199 : /// the handling its call site has (`parse_q` is re-run and its error stands).
200 : /// Entry size is already capped by the parser's own complexity ceiling
201 : /// (`MAX_Q_NODES`), entry count by the same bound and eviction as above.
202 2258 : pub fn q_node(q: &str) -> Option<Arc<crate::QNode>> {
203 2258 : if let Some(hit) = Q_CACHE
204 2258 : .read()
205 2258 : .ok()
206 2258 : .and_then(|c| c.get(q).map(|e| Arc::clone(touch(e))))
207 : {
208 52 : return Some(hit);
209 2206 : }
210 2206 : let node = Arc::new(crate::parse_q(q).ok()?);
211 2198 : if let Ok(mut c) = Q_CACHE.write() {
212 2198 : if c.len() >= MAX_REGEX_CACHE {
213 2 : evict_lru_half(&mut c);
214 2196 : }
215 2198 : c.insert(q.into(), stamp(Arc::clone(&node)));
216 0 : }
217 2198 : Some(node)
218 2258 : }
219 :
220 : /// The parsed geoquery (4.10) for a subscription's `geoQ`, keyed by the
221 : /// caller's serialization of that member. `build` runs on a miss and only a
222 : /// `Some` is retained — a `geoQ` that does not parse keeps failing exactly as
223 : /// before, per call. Geometry size is already capped at the parse
224 : /// (`MAX_GEO_VERTICES`), entry count by the same bound and eviction.
225 18 : pub fn geo_query(
226 18 : key: &str,
227 18 : build: impl FnOnce() -> Option<crate::geo::GeoQuery>,
228 18 : ) -> Option<Arc<crate::geo::GeoQuery>> {
229 18 : if let Some(hit) = GEO_CACHE
230 18 : .read()
231 18 : .ok()
232 18 : .and_then(|c| c.get(key).map(|e| Arc::clone(touch(e))))
233 : {
234 10 : return Some(hit);
235 8 : }
236 8 : let gq = Arc::new(build()?);
237 6 : if let Ok(mut c) = GEO_CACHE.write() {
238 6 : if c.len() >= MAX_REGEX_CACHE {
239 0 : evict_lru_half(&mut c);
240 6 : }
241 6 : c.insert(key.into(), stamp(Arc::clone(&gq)));
242 0 : }
243 6 : Some(gq)
244 18 : }
245 :
246 : /// Test-only serialization: a test that flushes the shared cache must not
247 : /// race the tests asserting what is retained.
248 : #[cfg(test)]
249 18 : pub(crate) fn serial_lock() -> std::sync::MutexGuard<'static, ()> {
250 : static SERIAL: std::sync::Mutex<()> = std::sync::Mutex::new(());
251 18 : SERIAL.lock().unwrap_or_else(|poison| poison.into_inner())
252 18 : }
253 :
254 : // regex compiles run for hours under Miri; the fuzz job covers them
255 : #[cfg(all(test, not(miri)))]
256 : mod tests {
257 : use super::*;
258 :
259 : /// The same pattern text is compiled once: the second call gets the very
260 : /// program the first one built (4.9 patternOp / 5.2.33 idPattern are
261 : /// evaluated per candidate, so this identity is the whole point).
262 : #[test]
263 2 : fn same_pattern_is_compiled_once() {
264 2 : let _serial = serial_lock();
265 2 : let p = "^urn:ngsi-ld:Vehicle:compiled-once-[0-9]+$";
266 2 : assert!(cached(p).is_none(), "cold pattern must not start retained");
267 2 : let before = compiles();
268 2 : let first = compile(p).expect("valid pattern");
269 2 : assert!(compiles() > before, "a cold pattern is compiled");
270 2 : let second = compile(p).expect("valid pattern");
271 2 : assert!(
272 2 : Arc::ptr_eq(&first, &second),
273 : "the second call must reuse the compiled program, not rebuild it"
274 : );
275 2 : assert!(
276 2 : cached(p).is_some_and(|c| Arc::ptr_eq(&c, &first)),
277 : "the cache holds that same program"
278 : );
279 2 : assert!(first.is_match("urn:ngsi-ld:Vehicle:compiled-once-7"));
280 2 : assert!(
281 2 : !first.is_match("urn:ngsi-ld:Vehicle:compiled-once-x"),
282 : "a shared program still rejects what the pattern excludes"
283 : );
284 2 : }
285 :
286 : /// An invalid pattern yields `Regex::new`'s own error, verbatim, so the
287 : /// spec error each call site maps it to is unchanged — an `idPattern`
288 : /// stays 400 BadRequestData (Table 6.3.2-1) and never becomes a 500.
289 : /// What is retained for it is the refusal, never a program.
290 : #[test]
291 2 : fn invalid_pattern_keeps_the_error_regex_new_returns() {
292 2 : let _serial = serial_lock();
293 14 : for p in ["[", "(", "a{2,1}", "(?P<", "*", "\\", "(?"] {
294 14 : let want = regex::Regex::new(p).map_err(|e| e.to_string());
295 14 : let got = compile(p).map(|_| ()).map_err(|e| e.to_string());
296 14 : assert!(want.is_err(), "fixture must be an invalid pattern: {p:?}");
297 14 : assert_eq!(
298 14 : got.map(|_| ()),
299 14 : want.map(|_| ()),
300 : "the cache must return the same error text for {p:?}"
301 : );
302 14 : assert!(cached(p).is_none(), "an invalid pattern yields no program");
303 14 : assert!(
304 14 : compile(p).is_err(),
305 : "and it stays an error on the second call for {p:?}"
306 : );
307 : }
308 2 : assert!(compile("^ok$").is_ok(), "a valid pattern is not rejected");
309 2 : }
310 :
311 : /// Retention is bounded in both dimensions: distinct patterns are
312 : /// client input, so many of them must grow the map past neither
313 : /// `MAX_REGEX_CACHE` nor `MAX_REGEX_CACHE_BYTES`, and the programs
314 : /// handed out across an eviction stay correct.
315 : #[test]
316 2 : fn cache_stays_bounded_under_many_distinct_patterns() {
317 2 : let _serial = serial_lock();
318 6144 : for i in 0..MAX_REGEX_CACHE * 3 {
319 6144 : let p = format!("^bounded-{i}-[a-z]+$");
320 6144 : let re = compile(&p).expect("valid pattern");
321 6144 : assert!(re.is_match(&format!("bounded-{i}-abc")));
322 6144 : assert!(!re.is_match(&format!("bounded-{i}-123")));
323 6144 : assert!(
324 6144 : len() <= MAX_REGEX_CACHE,
325 : "retained {} patterns after {i} distinct ones",
326 0 : len()
327 : );
328 6144 : assert!(
329 6144 : retained_bytes() <= MAX_REGEX_CACHE_BYTES,
330 : "charged {} bytes after {i} distinct patterns",
331 0 : retained_bytes()
332 : );
333 : }
334 2 : assert!(len() > 0, "the cache must still be caching after a flush");
335 2 : }
336 :
337 : /// A subscription fan-out evaluates the same `idPattern` per event while
338 : /// query traffic keeps bringing new `patternOp` operands in, so the
339 : /// working set and the entries that overflow a bound are different
340 : /// patterns. Crossing a bound must therefore cost the entries nothing is
341 : /// using: recompiling the live working set on the request unlucky enough
342 : /// to cross the line is the cost the eviction order exists to avoid.
343 : #[test]
344 2 : fn eviction_drops_the_least_recently_used_half() {
345 2 : let mut map: HashMap<Box<str>, Entry<u32>> = HashMap::new();
346 16 : for i in 0..8u32 {
347 16 : map.insert(format!("p{i}").into(), stamp(i));
348 16 : }
349 : // three of the eight are in use and are stamped again
350 6 : for k in ["p0", "p3", "p7"] {
351 6 : touch(map.get(k).expect("present"));
352 6 : }
353 2 : evict_lru_half(&mut map);
354 2 : assert_eq!(map.len(), 4, "half of eight is four");
355 6 : for k in ["p0", "p3", "p7"] {
356 6 : assert!(map.contains_key(k), "{k} was in use and must survive");
357 : }
358 : // the survivors are exactly the newest half: the fourth is the
359 : // newest of the untouched ones
360 2 : assert!(
361 2 : map.contains_key("p6"),
362 : "the newest untouched entry survives"
363 : );
364 8 : for k in ["p1", "p2", "p4", "p5"] {
365 8 : assert!(!map.contains_key(k), "{k} was the oldest and must go");
366 : }
367 2 : }
368 :
369 : /// The bound holds whatever the map's size, so the halving has to be
370 : /// defined at the sizes where "half" is not a whole entry.
371 : #[test]
372 2 : fn eviction_of_a_map_too_small_to_halve_empties_it() {
373 2 : let mut map: HashMap<Box<str>, Entry<u32>> = HashMap::new();
374 2 : evict_lru_half(&mut map);
375 2 : assert!(map.is_empty(), "an empty map stays empty");
376 2 : map.insert("only".into(), stamp(0));
377 2 : evict_lru_half(&mut map);
378 2 : assert!(map.is_empty(), "one entry cannot be halved and is dropped");
379 2 : }
380 :
381 : /// 4.9 evaluates a `patternOp` per candidate Entity and 5.2.33 an
382 : /// `idPattern` per event per Subscription, so an unbounded compile is
383 : /// multiplied by the candidate count. Program size follows counted
384 : /// repetition of a character class, not pattern length, so the bound
385 : /// has to be on the program: above the ceiling the pattern is refused,
386 : /// and the refusal is remembered so it costs one build pass, ever.
387 : #[test]
388 2 : fn a_program_above_the_ceiling_is_refused_once_not_rebuilt_per_candidate() {
389 2 : let _serial = serial_lock();
390 2 : let p = r"(?:\p{Any}{100}){100}";
391 2 : assert_eq!(p.len(), 21, "the fixture is what a client can send");
392 2 : assert!(
393 2 : build(p, MAX_REGEX_PROGRAM_BYTES).is_err(),
394 : "fixture must ask for a program above the ceiling"
395 : );
396 2 : let before = compiles();
397 2 : assert!(
398 2 : compile(p).is_err(),
399 : "a program above the ceiling is refused, not compiled"
400 : );
401 2 : let after = compiles();
402 2 : assert_eq!(after, before + 1, "one refusal costs one build pass");
403 2 : for _ in 0..64 {
404 128 : assert!(compile(p).is_err(), "and it stays refused");
405 : }
406 2 : assert_eq!(
407 2 : compiles(),
408 : after,
409 : "the refusal is remembered, not rebuilt for the next candidate"
410 : );
411 2 : assert!(cached(p).is_none(), "a refusal retains no program");
412 2 : }
413 :
414 : /// The ceiling bounds the automaton, not the expressiveness a
415 : /// deployment needs: the patterns an `idPattern` or a `~=` operand
416 : /// actually carries compile well inside it and are retained.
417 : #[test]
418 2 : fn the_ceiling_admits_the_patterns_a_deployment_writes() {
419 2 : let _serial = serial_lock();
420 10 : for p in [
421 2 : r"^urn:ngsi-ld:Vehicle:.*$",
422 2 : r"^urn:ngsi-ld:(Vehicle|Sensor|Building):[A-Za-z0-9_-]{1,64}$",
423 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}$",
424 2 : r"(?i)^urn:ngsi-ld:vehicle:.*$",
425 2 : r"^\d{4}-\d{2}-\d{2}T\d{2}:\d{2}:\d{2}Z$",
426 2 : ] {
427 10 : assert!(compile(p).is_ok(), "the ceiling must not refuse {p:?}");
428 10 : assert!(
429 10 : cached(p).is_some(),
430 : "what the ceiling admits, the cache retains: {p:?}"
431 : );
432 : }
433 2 : }
434 :
435 : /// The same q text parses once and every caller shares the tree; an
436 : /// invalid or over-complex q is parsed as before and never retained, so
437 : /// its call-site handling (no-match / 400) is unchanged.
438 : #[test]
439 2 : fn q_text_is_parsed_once_and_bad_q_is_not_retained() {
440 2 : let _serial = serial_lock();
441 2 : let q = r#"speed>20;brandName=="cache-q-probe""#;
442 2 : let first = q_node(q).expect("valid q");
443 2 : let second = q_node(q).expect("valid q");
444 2 : assert!(
445 2 : Arc::ptr_eq(&first, &second),
446 : "the second evaluation must reuse the parsed tree"
447 : );
448 8 : for bad in ["", "==5", "a==\"unterminated", "a==1)"] {
449 8 : assert!(q_node(bad).is_none(), "invalid q {bad:?} must not parse");
450 8 : assert!(
451 8 : Q_CACHE.read().is_ok_and(|c| !c.contains_key(bad)),
452 : "invalid q {bad:?} must not be retained"
453 : );
454 : }
455 : // boundedness under distinct client q texts
456 2176 : for i in 0..MAX_REGEX_CACHE + 64 {
457 2176 : q_node(&format!("qbound{i}>0")).expect("valid q");
458 2176 : assert!(
459 2176 : Q_CACHE.read().map(|c| c.len()).unwrap_or(usize::MAX) <= MAX_REGEX_CACHE,
460 : "q cache must stay bounded"
461 : );
462 : }
463 2 : }
464 :
465 : /// The geo cache shares one parsed geometry per distinct geoQ key, and a
466 : /// geoQ whose build fails is rebuilt (and re-fails) per call — never a
467 : /// cached wrong answer.
468 : #[test]
469 2 : fn geo_query_is_shared_per_key_and_failures_are_not_retained() {
470 2 : let _serial = serial_lock();
471 2 : let build_calls = std::sync::atomic::AtomicUsize::new(0);
472 4 : let params = || {
473 4 : let mut m = HashMap::new();
474 4 : m.insert("georel".to_owned(), "near;maxDistance==2000".to_owned());
475 4 : m.insert("geometry".to_owned(), "Point".to_owned());
476 4 : m.insert("coordinates".to_owned(), "[13.38,52.52]".to_owned());
477 4 : m
478 4 : };
479 4 : let build = || {
480 4 : build_calls.fetch_add(1, Ordering::Relaxed);
481 4 : crate::geo::GeoQuery::from_params(¶ms()).ok().flatten()
482 4 : };
483 2 : let first = geo_query("geo-probe-1", build).expect("valid geoQ");
484 2 : let second = geo_query("geo-probe-1", build).expect("valid geoQ");
485 2 : assert!(Arc::ptr_eq(&first, &second), "one parse per key");
486 2 : assert_eq!(
487 2 : build_calls.load(Ordering::Relaxed),
488 : 1,
489 : "the second call must not rebuild"
490 : );
491 2 : assert!(
492 2 : geo_query("geo-probe-bad", || None).is_none(),
493 : "a failing build yields None"
494 : );
495 2 : assert!(
496 2 : geo_query("geo-probe-bad", build).is_some(),
497 : "…and is not retained as a failure: the next build runs"
498 : );
499 2 : }
500 :
501 : /// Concurrent use: the same and different patterns compiled from many
502 : /// threads at once must stay correct and bounded, never deadlock, and
503 : /// never hand out a program built for another pattern.
504 : #[test]
505 2 : fn concurrent_compiles_are_safe() {
506 2 : let _serial = serial_lock();
507 2 : let pats = [
508 2 : ("^shared-a-[0-9]+$", "shared-a-1", "shared-a-x"),
509 2 : ("^shared-b-[a-z]+$", "shared-b-z", "shared-b-9"),
510 2 : ("shared-c", "xx-shared-c-xx", "shared-d"),
511 2 : ];
512 2 : let handles: Vec<_> = (0..8)
513 16 : .map(|t| {
514 16 : std::thread::spawn(move || {
515 3200 : for round in 0..200 {
516 3200 : let (p, hit, miss) = pats[round % pats.len()];
517 3200 : let re = compile(p).expect("valid pattern");
518 3200 : assert!(re.is_match(hit), "thread {t} pattern {p}");
519 3200 : assert!(!re.is_match(miss), "thread {t} pattern {p}");
520 : // a per-thread pattern exercises concurrent inserts
521 3200 : let own = format!("^t{t}-r{round}-[0-9]+$");
522 3200 : assert!(compile(&own)
523 3200 : .expect("valid")
524 3200 : .is_match(&format!("t{t}-r{round}-5")));
525 3200 : assert!(compile("[").is_err(), "invalid stays invalid");
526 : }
527 16 : })
528 16 : })
529 2 : .collect();
530 16 : for h in handles {
531 16 : h.join().expect("no thread panicked");
532 16 : }
533 2 : assert!(len() <= MAX_REGEX_CACHE, "still bounded after the race");
534 2 : assert!(
535 2 : cached("shared-c").is_some(),
536 : "a hot pattern survives concurrent use"
537 : );
538 2 : }
539 : }
|
