/
blocker.rs
1845 lines (1618 loc) · 73.7 KB
/
blocker.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
//! Holds `Blocker`, which handles all network-based adblocking queries.
use once_cell::sync::Lazy;
use serde::{Deserialize, Serialize};
use std::sync::Arc;
use std::collections::{HashMap, HashSet};
#[cfg(feature = "object-pooling")]
use lifeguard::Pool;
use crate::filters::network::{NetworkFilter, NetworkMatchable};
use crate::request::Request;
use crate::utils::{fast_hash, Hash};
use crate::optimizer;
use crate::resources::{Resource, RedirectResourceStorage, RedirectResource};
use crate::utils;
pub struct BlockerOptions {
pub enable_optimizations: bool,
}
/// Determines what should be loaded instead of a particular network request if the request also
/// matched a blocking filter.
#[derive(Debug, Deserialize, Serialize, PartialEq, Clone)]
pub enum Redirection {
/// Redirect to a stub resource loaded from the blocker's resource library. The field contains
/// the body of the redirect to be injected.
Resource(String),
/// Redirect to a remote resource. The field contains the URL of the replacement resource to be
/// loaded. These will only occur if previously enabled in `ParseOptions`.
Url(String),
}
#[derive(Debug, Serialize)]
pub struct BlockerResult {
pub matched: bool,
/// Important is used to signal that a rule with the `important` option
/// matched. An `important` match means that exceptions should not apply
/// and no further checking is neccesary--the request should be blocked
/// (empty body or cancelled).
///
/// Brave Browser keeps seperate instances of [`Blocker`] for default
/// lists and regional ones, so `important` here is used to correct
/// behaviour between them: checking should stop instead of moving to the
/// next instance iff an `important` rule matched.
pub important: bool,
/// Specifies what to load instead of the original request, rather than
/// just blocking it outright. This can come from a filter with a `redirect`
/// or `redirect-rule` option, or also from a `redirect-url` option if
/// enabled in `ParseOptions`. See `Redirection` for further instructions
/// on how the inner data should be interpreted.
///
/// Note that the presence of a redirect does _not_ imply that the request
/// should be blocked. The `redirect-rule` option can produce a redirection
/// that's only applied if another blocking filter matches a request.
pub redirect: Option<Redirection>,
/// Exception is `Some` when the blocker matched on an exception rule.
/// Effectively this means that there was a match, but the request should
/// not be blocked. It is a non-empty string if the blocker was initialized
/// from a list of rules with debugging enabled, otherwise the original
/// string representation is discarded to reduce memory use.
pub exception: Option<String>,
/// Filter--similarly to exception--includes the string representation of
/// the rule when there is a match and debugging is enabled. Otherwise, on
/// a match, it is `Some`.
pub filter: Option<String>,
/// The `error` field is only used to signal that there was an error in
/// parsing the provided URLs when using the simpler
/// [`crate::engine::Engine::check_network_urls`] method.
pub error: Option<String>,
}
impl Default for BlockerResult {
fn default() -> BlockerResult {
BlockerResult {
matched: false,
important: false,
redirect: None,
exception: None,
filter: None,
error: None,
}
}
}
#[derive(Debug, PartialEq)]
pub enum BlockerError {
SerializationError,
DeserializationError,
OptimizedFilterExistence,
BadFilterAddUnsupported,
FilterExists,
}
#[cfg(feature = "object-pooling")]
pub struct TokenPool {
pub pool: Pool<Vec<utils::Hash>>
}
#[cfg(feature = "object-pooling")]
impl Default for TokenPool {
fn default() -> TokenPool {
TokenPool {
pool: lifeguard::pool()
.with(lifeguard::StartingSize(1))
.with(lifeguard::Supplier(|| Vec::with_capacity(utils::TOKENS_BUFFER_SIZE)))
.build()
}
}
}
/// Stores network filters for efficient querying.
pub struct Blocker {
pub(crate) csp: NetworkFilterList,
pub(crate) exceptions: NetworkFilterList,
pub(crate) importants: NetworkFilterList,
pub(crate) redirects: NetworkFilterList,
pub(crate) filters_tagged: NetworkFilterList,
pub(crate) filters: NetworkFilterList,
pub(crate) generic_hide: NetworkFilterList,
// Enabled tags are not serialized - when deserializing, tags of the existing
// instance (the one we are recreating lists into) are maintained
pub(crate) tags_enabled: HashSet<String>,
pub(crate) tagged_filters_all: Vec<NetworkFilter>,
pub(crate) enable_optimizations: bool,
pub(crate) resources: RedirectResourceStorage,
// Not serialized
#[cfg(feature = "object-pooling")]
pub(crate) pool: TokenPool,
}
impl Blocker {
/// Decide if a network request (usually from WebRequest API) should be
/// blocked, redirected or allowed.
pub fn check(&self, request: &Request) -> BlockerResult {
self.check_parameterised(request, false, false)
}
pub fn check_generic_hide(&self, hostname_request: &Request) -> bool {
let mut request_tokens;
#[cfg(feature = "object-pooling")]
{
request_tokens = self.pool.pool.new();
}
#[cfg(not(feature = "object-pooling"))]
{
request_tokens = Vec::with_capacity(utils::TOKENS_BUFFER_SIZE);
}
hostname_request.get_tokens(&mut request_tokens);
self.generic_hide.check(hostname_request, &request_tokens, &HashSet::new()).is_some()
}
pub fn check_parameterised(&self, request: &Request, matched_rule: bool, force_check_exceptions: bool) -> BlockerResult {
if !request.is_supported {
return BlockerResult::default();
}
// only check for tags in tagged and exception rule buckets,
// pass empty set for the rest
static NO_TAGS: Lazy<HashSet<String>> = Lazy::new(HashSet::new);
let mut request_tokens;
#[cfg(feature = "object-pooling")]
{
request_tokens = self.pool.pool.new();
}
#[cfg(not(feature = "object-pooling"))]
{
request_tokens = Vec::with_capacity(utils::TOKENS_BUFFER_SIZE);
}
request.get_tokens(&mut request_tokens);
// Check the filters in the following order:
// 1. $important (not subject to exceptions)
// 2. redirection ($redirect=resource)
// 3. normal filters - if no match by then
// 4. exceptions - if any non-important match of forced
#[cfg(feature = "metrics")]
print!("importants\t");
// Always check important filters
let important_filter = self
.importants
.check(request, &request_tokens, &NO_TAGS);
// only check the rest of the rules if not previously matched
let filter = if important_filter.is_none() && !matched_rule {
#[cfg(feature = "metrics")]
print!("tagged\t");
self.filters_tagged.check(request, &request_tokens, &self.tags_enabled)
.or_else(|| {
#[cfg(feature = "metrics")]
print!("filters\t");
self.filters.check(request, &request_tokens, &NO_TAGS)
})
} else {
important_filter
};
let exception = match filter.as_ref() {
// if no other rule matches, only check exceptions if forced to
None if matched_rule || force_check_exceptions => {
#[cfg(feature = "metrics")]
print!("exceptions\t");
self.exceptions.check(request, &request_tokens, &self.tags_enabled)
}
None => None,
// If matched an important filter, exceptions don't atter
Some(f) if f.is_important() => None,
Some(f) if f.has_bug() => {
#[cfg(feature = "metrics")]
print!("exceptions\t");
// Set `bug` of request
let mut request_bug = request.clone();
request_bug.bug = f.bug;
self.exceptions.check(&request_bug, &request_tokens, &self.tags_enabled)
}
Some(_) => {
#[cfg(feature = "metrics")]
print!("exceptions\t");
self.exceptions.check(request, &request_tokens, &self.tags_enabled)
}
};
#[cfg(feature = "metrics")]
println!();
let redirect_filters = self.redirects.check_all(request, &request_tokens, &NO_TAGS);
// Extract the highest priority redirect directive.
// So far, priority specifiers are not supported, which means:
// 1. Exceptions - can bail immediately if found
// 2. Redirect URLs
// 3. Redirect resources
let redirect_option = {
// (true, s) implies s is a URL.
// (false, s) implies s is the name of a resource to lookup.
let mut redirect: Option<(bool, &str)> = None;
for redirect_filter in redirect_filters {
if redirect_filter.is_exception() {
redirect = None;
break;
} else if redirect_filter.is_redirect_url() {
// Unconditionally write to `redirect` - it's the highest priority option that
// does not break the loop.
redirect = redirect_filter.redirect.as_ref().map(|s| (true, s.as_str()));
} else if redirect.is_none() {
// Otherwise, only write to `redirect` if it hasn't already been set by a
// previous filter.
redirect = redirect_filter.redirect.as_ref().map(|s| (false, s.as_str()));
}
}
redirect
};
let redirect: Option<Redirection> = redirect_option.and_then(|(is_url, redirect_identifier)| {
if is_url {
Some(Redirection::Url(redirect_identifier.to_string()))
} else if let Some(resource) = self.resources.get_resource(redirect_identifier) {
// Only match resource redirects if a matching resource exists
let data_url = format!("data:{};base64,{}", resource.content_type, &resource.data);
Some(Redirection::Resource(data_url.trim().to_owned()))
} else {
// It's acceptable to pass no redirection if no matching resource is loaded.
// TODO - it may be useful to return a status flag to indicate that this occurred.
#[cfg(test)]
eprintln!("Matched rule with redirect option but did not find corresponding resource to send");
None
}
});
// If something has already matched before but we don't know what, still return a match
let matched = exception.is_none() && (filter.is_some() || matched_rule);
BlockerResult {
matched,
important: filter.is_some() && filter.as_ref().map(|f| f.is_important()).unwrap_or_else(|| false),
redirect,
exception: exception.as_ref().map(|f| f.to_string()), // copy the exception
filter: filter.as_ref().map(|f| f.to_string()), // copy the filter
error: None,
}
}
/// Given a "main_frame" or "subdocument" request, check if some content security policies
/// should be injected in the page.
pub fn get_csp_directives(&self, request: &Request) -> Option<String> {
use crate::request::RequestType;
if request.request_type != RequestType::Document && request.request_type != RequestType::Subdocument {
return None;
}
let mut request_tokens;
#[cfg(feature = "object-pooling")]
{
request_tokens = self.pool.pool.new();
}
#[cfg(not(feature = "object-pooling"))]
{
request_tokens = Vec::with_capacity(utils::TOKENS_BUFFER_SIZE);
}
request.get_tokens(&mut request_tokens);
let filters = self.csp.check_all(request, &request_tokens, &self.tags_enabled);
if filters.is_empty() {
return None;
}
let mut disabled_directives: HashSet<&str> = HashSet::new();
let mut enabled_directives: HashSet<&str> = HashSet::new();
for filter in filters {
if filter.is_exception() {
if let Some(directive) = &filter.csp {
disabled_directives.insert(directive);
} else {
// Exception filters with empty `csp` options will disable all CSP injections for
// matching pages.
return None
}
} else if let Some(directive) = &filter.csp {
enabled_directives.insert(directive);
}
}
let mut remaining_directives = enabled_directives.difference(&disabled_directives);
let mut merged = if let Some(directive) = remaining_directives.next() {
String::from(*directive)
} else {
return None;
};
remaining_directives.for_each(|directive| {
merged.push(',');
merged.push_str(directive);
});
Some(merged)
}
pub fn new(network_filters: Vec<NetworkFilter>, options: &BlockerOptions) -> Blocker {
// Capacity of filter subsets estimated based on counts in EasyList and EasyPrivacy - if necessary
// the Vectors will grow beyond the pre-set capacity, but it is more efficient to allocate all at once
// $csp=
let mut csp = Vec::with_capacity(200);
// @@filter
let mut exceptions = Vec::with_capacity(network_filters.len() / 8);
// $important
let mut importants = Vec::with_capacity(200);
// $redirect and $redirect-url
let mut redirects = Vec::with_capacity(200);
// $tag=
let mut tagged_filters_all = Vec::with_capacity(200);
// $badfilter
let mut badfilters = Vec::with_capacity(100);
// $generichide
let mut generic_hide = Vec::with_capacity(4000);
// All other filters
let mut filters = Vec::with_capacity(network_filters.len());
// Injections
// TODO: resource handling
if !network_filters.is_empty() {
for filter in network_filters.iter() {
if filter.is_badfilter() {
badfilters.push(filter);
}
}
let badfilter_ids: HashSet<Hash> = badfilters.iter().map(|f| f.get_id_without_badfilter()).collect();
for filter in network_filters {
// skip any bad filters
let filter_id = filter.get_id();
if badfilter_ids.contains(&filter_id) || filter.is_badfilter() {
continue;
}
// Redirects are independent of blocking behavior.
if filter.is_redirect() {
redirects.push(filter.clone());
}
if filter.is_csp() {
csp.push(filter);
} else if filter.is_generic_hide() {
generic_hide.push(filter);
} else if filter.is_exception() {
exceptions.push(filter);
} else if filter.is_important() {
importants.push(filter);
} else if filter.tag.is_some() && !filter.is_redirect() {
// `tag` + `redirect` is unsupported for now.
tagged_filters_all.push(filter);
} else {
filters.push(filter);
}
}
}
tagged_filters_all.shrink_to_fit();
Blocker {
csp: NetworkFilterList::new(csp, options.enable_optimizations),
exceptions: NetworkFilterList::new(exceptions, options.enable_optimizations),
importants: NetworkFilterList::new(importants, options.enable_optimizations),
redirects: NetworkFilterList::new(redirects, options.enable_optimizations),
filters_tagged: NetworkFilterList::new(Vec::new(), options.enable_optimizations),
filters: NetworkFilterList::new(filters, options.enable_optimizations),
generic_hide: NetworkFilterList::new(generic_hide, options.enable_optimizations),
// Tags special case for enabling/disabling them dynamically
tags_enabled: HashSet::new(),
tagged_filters_all,
// Options
enable_optimizations: options.enable_optimizations,
resources: RedirectResourceStorage::default(),
#[cfg(feature = "object-pooling")]
pool: TokenPool::default(),
}
}
/// If optimizations are enabled, the `Blocker` will be configured to automatically optimize
/// its filters after batch updates. However, even if they are disabled, it is possible to
/// manually call `optimize()`. It may be useful to have finer-grained control over
/// optimization scheduling when frequently updating filters.
pub fn optimize(&mut self) {
self.csp.optimize();
self.exceptions.optimize();
self.importants.optimize();
self.redirects.optimize();
self.filters_tagged.optimize();
self.filters.optimize();
self.generic_hide.optimize();
}
pub fn filter_exists(&self, filter: &NetworkFilter) -> bool {
if filter.is_csp() {
self.csp.filter_exists(filter)
} else if filter.is_generic_hide() {
self.generic_hide.filter_exists(filter)
} else if filter.is_exception() {
self.exceptions.filter_exists(filter)
} else if filter.is_important() {
self.importants.filter_exists(filter)
} else if filter.is_redirect() {
self.redirects.filter_exists(filter)
} else if filter.tag.is_some() {
self.tagged_filters_all.iter().any(|f| f.id == filter.id)
} else {
self.filters.filter_exists(filter)
}
}
pub fn add_filter(&mut self, filter: NetworkFilter) -> Result<(), BlockerError> {
if filter.is_badfilter() {
Err(BlockerError::BadFilterAddUnsupported)
} else if self.filter_exists(&filter) {
Err(BlockerError::FilterExists)
} else if filter.is_csp() {
self.csp.add_filter(filter);
Ok(())
} else if filter.is_generic_hide() {
self.generic_hide.add_filter(filter);
Ok(())
} else if filter.is_exception() {
self.exceptions.add_filter(filter);
Ok(())
} else if filter.is_important() {
self.importants.add_filter(filter);
Ok(())
} else if filter.is_redirect() {
self.redirects.add_filter(filter);
Ok(())
} else if filter.is_redirect_url() {
self.redirects.add_filter(filter);
Ok(())
} else if filter.tag.is_some() {
self.tagged_filters_all.push(filter);
let tags_enabled = self.tags_enabled().into_iter().collect::<HashSet<_>>();
self.tags_with_set(tags_enabled);
Ok(())
} else {
self.filters.add_filter(filter);
Ok(())
}
}
pub fn use_tags(&mut self, tags: &[&str]) {
let tag_set: HashSet<String> = tags.iter().map(|&t| String::from(t)).collect();
self.tags_with_set(tag_set);
}
pub fn enable_tags(&mut self, tags: &[&str]) {
let tag_set: HashSet<String> = tags.iter().map(|&t| String::from(t)).collect::<HashSet<_>>()
.union(&self.tags_enabled)
.cloned()
.collect();
self.tags_with_set(tag_set);
}
pub fn disable_tags(&mut self, tags: &[&str]) {
let tag_set: HashSet<String> = self.tags_enabled
.difference(&tags.iter().map(|&t| String::from(t)).collect())
.cloned()
.collect();
self.tags_with_set(tag_set);
}
fn tags_with_set(&mut self, tags_enabled: HashSet<String>) {
self.tags_enabled = tags_enabled;
let filters: Vec<NetworkFilter> = self.tagged_filters_all.iter()
.filter(|n| n.tag.is_some() && self.tags_enabled.contains(n.tag.as_ref().unwrap()))
.cloned()
.collect();
self.filters_tagged = NetworkFilterList::new(filters, self.enable_optimizations);
}
pub fn tags_enabled(&self) -> Vec<String> {
self.tags_enabled.iter().cloned().collect()
}
pub fn use_resources(&mut self, resources: &[Resource]) {
let resources = RedirectResourceStorage::from_resources(resources);
self.resources = resources;
}
pub fn add_resource(&mut self, resource: &Resource) -> Result<(), crate::resources::AddResourceError> {
self.resources.add_resource(resource)
}
pub fn get_resource(&self, key: &str) -> Option<&RedirectResource> {
self.resources.get_resource(key)
}
}
#[derive(Serialize, Deserialize, Default)]
pub struct NetworkFilterList {
#[serde(serialize_with = "crate::data_format::utils::stabilize_hashmap_serialization")]
pub(crate) filter_map: HashMap<Hash, Vec<Arc<NetworkFilter>>>,
}
impl NetworkFilterList {
pub fn new(filters: Vec<NetworkFilter>, optimize: bool) -> NetworkFilterList {
// Compute tokens for all filters
let filter_tokens: Vec<_> = filters
.into_iter()
.map(|filter| {
let tokens = filter.get_tokens();
(Arc::new(filter), tokens)
})
.collect();
// compute the tokens' frequency histogram
let (total_number_of_tokens, tokens_histogram) = token_histogram(&filter_tokens);
// Build a HashMap of tokens to Network Filters (held through Arc, Atomic Reference Counter)
let mut filter_map = HashMap::with_capacity(filter_tokens.len());
{
for (filter_pointer, multi_tokens) in filter_tokens {
for tokens in multi_tokens {
let mut best_token: Hash = 0;
let mut min_count = total_number_of_tokens + 1;
for token in tokens {
match tokens_histogram.get(&token) {
None => {
min_count = 0;
best_token = token
}
Some(&count) if count < min_count => {
min_count = count;
best_token = token
}
_ => {}
}
}
insert_dup(&mut filter_map, best_token, Arc::clone(&filter_pointer));
}
}
}
let mut self_ = NetworkFilterList {
filter_map,
};
if optimize {
self_.optimize();
} else {
self_.filter_map.shrink_to_fit();
}
self_
}
pub fn optimize(&mut self) {
let mut optimized_map = HashMap::with_capacity(self.filter_map.len());
for (key, filters) in self.filter_map.drain() {
let mut unoptimized: Vec<NetworkFilter> = Vec::with_capacity(filters.len());
let mut unoptimizable: Vec<Arc<NetworkFilter>> = Vec::with_capacity(filters.len());
for f in filters {
match Arc::try_unwrap(f) {
Ok(f) => unoptimized.push(f),
Err(af) => unoptimizable.push(af)
}
}
let mut optimized: Vec<_> = if unoptimized.len() > 1 {
optimizer::optimize(unoptimized).into_iter().map(Arc::new).collect()
} else {
// nothing to optimize
unoptimized.into_iter().map(Arc::new).collect()
};
optimized.append(&mut unoptimizable);
optimized_map.insert(key, optimized);
}
// won't mutate anymore, shrink to fit items
optimized_map.shrink_to_fit();
self.filter_map = optimized_map;
}
pub fn add_filter(&mut self, filter: NetworkFilter) {
let filter_tokens = filter.get_tokens();
let total_rules = vec_hashmap_len(&self.filter_map);
let filter_pointer = Arc::new(filter);
for tokens in filter_tokens {
let mut best_token: Hash = 0;
let mut min_count = total_rules + 1;
for token in tokens {
match self.filter_map.get(&token) {
None => {
min_count = 0;
best_token = token
}
Some(filters) if filters.len() < min_count => {
min_count = filters.len();
best_token = token
}
_ => {}
}
}
insert_dup(&mut self.filter_map, best_token, Arc::clone(&filter_pointer));
}
}
pub fn filter_exists(&self, filter: &NetworkFilter) -> bool {
// if self.optimized == Some(true) {
// return Err(BlockerError::OptimizedFilterExistence)
// }
let mut tokens: Vec<_> = filter.get_tokens().into_iter().flatten().collect();
if tokens.is_empty() {
tokens.push(0)
}
for token in tokens {
if let Some(filters) = self.filter_map.get(&token) {
for saved_filter in filters {
if saved_filter.id == filter.id {
return true;
}
}
}
}
false
}
/// Returns the first found filter, if any, that matches the given request. The backing storage
/// has a non-deterministic order, so this should be used for any category of filters where a
/// match from each would be functionally equivalent. For example, if two different exception
/// filters match a certain request, it doesn't matter _which_ one is matched - the request
/// will be excepted either way.
pub fn check(&self, request: &Request, request_tokens: &[Hash], active_tags: &HashSet<String>) -> Option<&NetworkFilter> {
#[cfg(feature = "metrics")]
let mut filters_checked = 0;
#[cfg(feature = "metrics")]
let mut filter_buckets = 0;
#[cfg(not(feature = "metrics"))]
{
if self.filter_map.is_empty() {
return None;
}
}
if let Some(source_hostname_hashes) = request.source_hostname_hashes.as_ref() {
for token in source_hostname_hashes {
if let Some(filter_bucket) = self.filter_map.get(token) {
#[cfg(feature = "metrics")]
{
filter_buckets += 1;
}
for filter in filter_bucket {
#[cfg(feature = "metrics")]
{
filters_checked += 1;
}
// if matched, also needs to be tagged with an active tag (or not tagged at all)
if filter.matches(request) && filter.tag.as_ref().map(|t| active_tags.contains(t)).unwrap_or(true) {
#[cfg(feature = "metrics")]
print!("true\t{}\t{}\tskipped\t{}\t{}\t", filter_buckets, filters_checked, filter_buckets, filters_checked);
return Some(filter);
}
}
}
}
}
#[cfg(feature = "metrics")]
print!("false\t{}\t{}\t", filter_buckets, filters_checked);
for token in request_tokens {
if let Some(filter_bucket) = self.filter_map.get(token) {
#[cfg(feature = "metrics")]
{
filter_buckets += 1;
}
for filter in filter_bucket {
#[cfg(feature = "metrics")]
{
filters_checked += 1;
}
// if matched, also needs to be tagged with an active tag (or not tagged at all)
if filter.matches(request) && filter.tag.as_ref().map(|t| active_tags.contains(t)).unwrap_or(true) {
#[cfg(feature = "metrics")]
print!("true\t{}\t{}\t", filter_buckets, filters_checked);
return Some(filter);
}
}
}
}
#[cfg(feature = "metrics")]
print!("false\t{}\t{}\t", filter_buckets, filters_checked);
None
}
/// Returns _all_ filters that match the given request. This should be used for any category of
/// filters where a match from each may carry unique information. For example, if two different
/// `$csp` filters match a certain request, they may each carry a distinct CSP directive, and
/// each directive should be combined for the final result.
pub fn check_all(&self, request: &Request, request_tokens: &[Hash], active_tags: &HashSet<String>) -> Vec<&NetworkFilter> {
#[cfg(feature = "metrics")]
let mut filters_checked = 0;
#[cfg(feature = "metrics")]
let mut filter_buckets = 0;
let mut filters = vec![];
#[cfg(not(feature = "metrics"))]
{
if self.filter_map.is_empty() {
return filters;
}
}
if let Some(source_hostname_hashes) = request.source_hostname_hashes.as_ref() {
for token in source_hostname_hashes {
if let Some(filter_bucket) = self.filter_map.get(token) {
#[cfg(feature = "metrics")]
{
filter_buckets += 1;
}
for filter in filter_bucket {
#[cfg(feature = "metrics")]
{
filters_checked += 1;
}
// if matched, also needs to be tagged with an active tag (or not tagged at all)
if filter.matches(request) && filter.tag.as_ref().map(|t| active_tags.contains(t)).unwrap_or(true) {
#[cfg(feature = "metrics")]
print!("true\t{}\t{}\tskipped\t{}\t{}\t", filter_buckets, filters_checked, filter_buckets, filters_checked);
filters.push(filter);
}
}
}
}
}
#[cfg(feature = "metrics")]
print!("false\t{}\t{}\t", filter_buckets, filters_checked);
for token in request_tokens {
if let Some(filter_bucket) = self.filter_map.get(token) {
#[cfg(feature = "metrics")]
{
filter_buckets += 1;
}
for filter in filter_bucket {
#[cfg(feature = "metrics")]
{
filters_checked += 1;
}
// if matched, also needs to be tagged with an active tag (or not tagged at all)
if filter.matches(request) && filter.tag.as_ref().map(|t| active_tags.contains(t)).unwrap_or(true) {
#[cfg(feature = "metrics")]
print!("true\t{}\t{}\t", filter_buckets, filters_checked);
filters.push(filter);
}
}
}
}
#[cfg(feature = "metrics")]
print!("false\t{}\t{}\t", filter_buckets, filters_checked);
filters
}
}
/// Inserts a value into the `Vec` under the specified key in the `HashMap`. The entry will be
/// created if it does not exist. If it already exists, it will be inserted in the `Vec` in a
/// sorted order.
fn insert_dup<K, V, H: std::hash::BuildHasher>(map: &mut HashMap<K, Vec<V>, H>, k: K, v: V)
where
K: std::cmp::Ord + std::hash::Hash,
V: PartialOrd,
{
let entry = map.entry(k).or_insert_with(Vec::new);
match entry.binary_search_by(|f| f.partial_cmp(&v).unwrap_or(std::cmp::Ordering::Equal)) {
Ok(_pos) => (), // Can occur if the exact same rule is inserted twice. No reason to add anything.
Err(slot) => entry.insert(slot, v),
}
}
fn vec_hashmap_len<K: std::cmp::Eq + std::hash::Hash, V, H: std::hash::BuildHasher>(map: &HashMap<K, Vec<V>, H>) -> usize {
let mut size = 0usize;
for (_, val) in map.iter() {
size += val.len();
}
size
}
fn token_histogram<T>(filter_tokens: &[(T, Vec<Vec<Hash>>)]) -> (u32, HashMap<Hash, u32>) {
let mut tokens_histogram: HashMap<Hash, u32> = HashMap::new();
let mut number_of_tokens = 0;
for (_, tokens) in filter_tokens.iter() {
for tg in tokens {
for t in tg {
*tokens_histogram.entry(*t).or_insert(0) += 1;
number_of_tokens += 1;
}
}
}
for bad_token in ["http", "https", "www", "com"].iter() {
tokens_histogram.insert(fast_hash(bad_token), number_of_tokens);
}
(number_of_tokens, tokens_histogram)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn insert_dup_works() {
let mut dup_map: HashMap<Hash, Vec<String>> = HashMap::new();
// inserts into empty
insert_dup(&mut dup_map, 1, String::from("foo"));
assert_eq!(dup_map.get(&1), Some(&vec![String::from("foo")]));
// adds item
insert_dup(&mut dup_map, 1, String::from("bar"));
assert_eq!(
dup_map.get(&1),
Some(&vec![String::from("bar"), String::from("foo")])
);
// inserts into another key item
insert_dup(&mut dup_map, 123, String::from("baz"));
assert_eq!(dup_map.get(&123), Some(&vec![String::from("baz")]));
assert_eq!(
dup_map.get(&1),
Some(&vec![String::from("bar"), String::from("foo")])
);
}
#[test]
fn token_histogram_works() {
// handle the case of just 1 token
{
let tokens = vec![(0, vec![vec![111]])];
let (total_tokens, histogram) = token_histogram(&tokens);
assert_eq!(total_tokens, 1);
assert_eq!(histogram.get(&111), Some(&1));
// include bad tokens
assert_eq!(histogram.get(&fast_hash("http")), Some(&1));
assert_eq!(histogram.get(&fast_hash("www")), Some(&1));
}
// handle the case of repeating tokens
{
let tokens = vec![(0, vec![vec![111]]), (1, vec![vec![111]])];
let (total_tokens, histogram) = token_histogram(&tokens);
assert_eq!(total_tokens, 2);
assert_eq!(histogram.get(&111), Some(&2));
// include bad tokens
assert_eq!(histogram.get(&fast_hash("http")), Some(&2));
assert_eq!(histogram.get(&fast_hash("www")), Some(&2));
}
// handle the different token set sizes
{
let tokens = vec![
(0, vec![vec![111, 123, 132]]),
(1, vec![vec![111], vec![123], vec![132]]),
(2, vec![vec![111, 123], vec![132]]),
(3, vec![vec![111, 111], vec![111]]),
];
let (total_tokens, histogram) = token_histogram(&tokens);
assert_eq!(total_tokens, 12);
assert_eq!(histogram.get(&111), Some(&6));
assert_eq!(histogram.get(&123), Some(&3));
assert_eq!(histogram.get(&132), Some(&3));
// include bad tokens
assert_eq!(histogram.get(&fast_hash("http")), Some(&12));
assert_eq!(histogram.get(&fast_hash("www")), Some(&12));
}
}
#[test]
fn network_filter_list_new_works() {
{
let filters = vec!["||foo.com"];
let network_filters: Vec<_> = filters
.into_iter()
.map(|f| NetworkFilter::parse(&f, true))
.filter_map(Result::ok)
.collect();
let filter_list = NetworkFilterList::new(network_filters, false);
let maybe_matching_filter = filter_list.filter_map.get(&fast_hash("foo"));
assert!(maybe_matching_filter.is_some(), "Expected filter not found");
}
// choses least frequent token
{
let filters = vec!["||foo.com", "||bar.com/foo"];
let network_filters: Vec<_> = filters
.into_iter()
.map(|f| NetworkFilter::parse(&f, true))
.filter_map(Result::ok)
.collect();
let filter_list = NetworkFilterList::new(network_filters, false);
assert_eq!(
filter_list.filter_map.get(&fast_hash("bar")).unwrap().len(),
1
);
assert_eq!(
filter_list.filter_map.get(&fast_hash("foo")).unwrap().len(),
1
);
}
// choses blacklisted token when no other choice
{
let filters = vec!["||foo.com", "||foo.com/bar", "||www"];
let network_filters: Vec<_> = filters
.into_iter()
.map(|f| NetworkFilter::parse(&f, true))
.filter_map(Result::ok)
.collect();
let filter_list = NetworkFilterList::new(network_filters, false);
assert!(
filter_list.filter_map.get(&fast_hash("www")).is_some(),
"Filter matching {} not found",
"www"
);
assert_eq!(
filter_list.filter_map.get(&fast_hash("www")).unwrap().len(),
1
);
}
// uses domain as token when only one domain
{
let filters = vec!["||foo.com", "||foo.com$domain=bar.com"];
let network_filters: Vec<_> = filters
.into_iter()
.map(|f| NetworkFilter::parse(&f, true))
.filter_map(Result::ok)
.collect();
let filter_list = NetworkFilterList::new(network_filters, false);
assert!(
filter_list.filter_map.get(&fast_hash("bar.com")).is_some(),
"Filter matching {} not found",
"bar.com"
);