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
#![doc = include_str!("../README.md")]
#![cfg_attr(not(feature = "std"), no_std)]
mod backend;
pub mod shufti;
pub mod truffle;
pub use self::backend::SimdBackend;
#[cfg(test)]
mod tests {
extern crate std;
use std::{vec, vec::Vec};
// Needle/haystack pairs from Hyperscan's Shufti and Truffle search tests.
// Keep project-specific cases in the tests for their own methods.
// Source revision: bc3b191ab56055e8560c7cdc161c289c4d76e3d2.
// https://github.com/intel/hyperscan/blob/bc3b191ab56055e8560c7cdc161c289c4d76e3d2/unit/internal/shufti.cpp
// https://github.com/intel/hyperscan/blob/bc3b191ab56055e8560c7cdc161c289c4d76e3d2/unit/internal/truffle.cpp
pub(crate) fn hyperscan_needle_and_haystack() -> Vec<(Vec<u8>, Vec<u8>)> {
let mut inputs = Vec::new();
// Forward tests advance the beginning of the searched slice.
let forward16: &[(&[u8], &[u8])] = &[
(
b"aB",
b"bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb",
),
(
b"V",
b"eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee",
),
(
b"a",
b"bbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb",
),
(
b"aB",
b"bbbbbbbbbbbbbbbbbBaaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb",
),
(
b"aCAc",
b"bbbbbbbbbbbbbbbbbAaaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb",
),
(
b"aCAc",
b"bbbbbbbbbbbbbbbbbCaaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb",
),
(
b"aCAc",
b"bbbbbbbbbbbbbbbbbcaaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb",
),
(
b"aCAc",
b"bbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbabbbbbbbbbbbb",
),
(
b"a",
b"bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb\xff",
),
(
b"a",
b"bbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbb",
),
];
for &(needle, haystack) in forward16 {
for start in 0..16 {
inputs.push((needle.to_vec(), haystack[start..].to_vec()));
}
}
let forward32: &[(&[u8], &[u8])] = &[
(
b"a",
b"bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb",
),
(
b"a",
b"bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbabbbbbbbbbbbb",
),
];
for &(needle, haystack) in forward32 {
for start in 0..32 {
inputs.push((needle.to_vec(), haystack[start..].to_vec()));
}
}
// Reverse tests shorten the slice's end. These strings already omit
// the leading byte excluded by the original no-match calls.
let reverse16: &[(&[u8], &[u8])] = &[
(
b"a",
b"bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb",
),
(
b"aB",
b"bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb",
),
(
b"V",
b"eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee",
),
(
b"a",
b"bbbbbbabbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb",
),
(
b"a",
b"bbbbabbbbbbbbbbbbaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbb",
),
(
b"aB",
b"bbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaBbbbbbbbbbbbbbbbbbbbbbbbbbbbb",
),
(
b"aB",
b"bbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbb",
),
(
b"aCAc",
b"bbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaAbbbbbbbbbbbbbbbbbbbbbbbbbbbb",
),
(
b"aCAc",
b"bbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaCbbbbbbbbbbbbbbbbbbbbbbbbbbbb",
),
(
b"aCAc",
b"bbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaacbbbbbbbbbbbbbbbbbbbbbbbbbbbb",
),
(
b"aCAc",
b"bbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbb",
),
];
for &(needle, haystack) in reverse16 {
for trim in 0..16 {
inputs.push((needle.to_vec(), haystack[..haystack.len() - trim].to_vec()));
}
}
// Short inputs include embedded NUL bytes; their lengths are explicit.
let short: &[(&[u8], &[u8])] = &[
(b"a", b"a"),
(b"a", b"bbbbbbbabbb"),
(b"\0", b"bbbbbbb\0bbb"),
(b"a", b"\0\0\0\0\0\0\0a\0\0\0"),
(b"a", b"bbbbbbbabbbb"),
(b"a", b"babbbbbabbbb"),
];
for &(needle, haystack) in short {
inputs.push((needle.to_vec(), haystack.to_vec()));
}
// The original 400-byte buffer is searched only through byte 398.
let mut haystack = vec![b'b'; 399];
haystack[120] = b'a';
for start in 0..16 {
inputs.push((b"a".to_vec(), haystack[start..].to_vec()));
}
// Preserve accumulated matches as each source loop modifies its buffer.
let mut haystack = vec![b'b'; 76];
for step in 0..31 {
haystack[48 - step] = b'a';
inputs.push((b"a".to_vec(), haystack.clone()));
}
for len in [76, 256] {
let mut haystack = vec![b'b'; len];
for position in 0..len {
haystack[position] = b'a';
inputs.push((b"a".to_vec(), haystack.clone()));
}
}
// Truffle exercises every member of these two inclusive byte ranges.
let needle: Vec<u8> = (b'0'..=b'Z').collect();
let mut haystack = vec![b'*'; 128];
for &byte in &needle {
haystack[17] = byte;
inputs.push((needle.clone(), haystack.clone()));
}
let needle: Vec<u8> = (127..=255).collect();
let mut haystack = vec![b'*'; 128];
for &byte in &needle {
haystack[40] = byte;
inputs.push((needle.clone(), haystack.clone()));
}
// Forward/reverse and Shufti/Truffle tests share many identical pairs.
inputs.sort_unstable();
inputs.dedup();
inputs
}
// One writable page between two inaccessible pages.
#[cfg(target_os = "linux")]
pub(crate) struct GuardedPage {
mapping: *mut std::ffi::c_void,
page_size: usize,
}
#[cfg(target_os = "linux")]
impl GuardedPage {
pub(crate) fn new() -> Self {
use std::ptr;
// SAFETY: _SC_PAGESIZE is a valid sysconf query and takes no pointers.
let page_size = unsafe { libc::sysconf(libc::_SC_PAGESIZE) };
assert!(page_size > 0);
let page_size = page_size as usize;
// mmap's second argument is a byte count: page_size * 3 maps three
// contiguous pages. PROT_NONE initially makes all three inaccessible.
// libc supplies the target ABI's flags; MAP_ANONYMOUS differs
// between Linux architectures, so its numeric value is not portable.
// SAFETY: request a new anonymous mapping; no existing memory is replaced.
let mapping = unsafe {
libc::mmap(
ptr::null_mut(),
page_size * 3,
libc::PROT_NONE,
libc::MAP_PRIVATE | libc::MAP_ANONYMOUS,
-1,
0,
)
};
assert_ne!(mapping, libc::MAP_FAILED, "mmap failed");
// Own the mapping before mprotect so a failure also releases it.
let guarded = Self { mapping, page_size };
// mapping points to the first page. Casting to u8 makes add count
// bytes: adding page_size skips one page and reaches the start of
// the second (middle) page.
// SAFETY: this one-page offset stays inside the three-page mapping.
let middle = unsafe { mapping.cast::<u8>().add(page_size) };
// Grant read/write access only to the middle page, leaving
// this layout: [guard][read/write][guard].
// SAFETY: middle is page-aligned, and the entire page lies inside
// the mapping we own.
assert_eq!(
unsafe {
libc::mprotect(middle.cast(), page_size, libc::PROT_READ | libc::PROT_WRITE)
},
0
);
guarded
}
pub(crate) fn as_mut_slice(&mut self) -> &mut [u8] {
// SAFETY: new() made the middle page writable, and anonymous mmap
// initialized its bytes to zero. Borrowing self exclusively prevents
// aliasing and keeps the mapping alive for the returned slice.
unsafe {
std::slice::from_raw_parts_mut(
self.mapping.cast::<u8>().add(self.page_size),
self.page_size,
)
}
}
}
#[cfg(target_os = "linux")]
impl Drop for GuardedPage {
fn drop(&mut self) {
// SAFETY: self owns the original mapping address and all three pages.
assert_eq!(unsafe { libc::munmap(self.mapping, self.page_size * 3) }, 0);
}
}
}