Branch data Line data Source code
1 : : /* SPDX-License-Identifier: GPL-2.0-only */
2 : : /*
3 : : * Copyright (c) Meta Platforms, Inc. and affiliates.
4 : : */
5 : :
6 : : #include "cgen/matcher/cmp.h"
7 : :
8 : : #include <linux/bpf.h>
9 : : #include <linux/bpf_common.h>
10 : :
11 : : #include <assert.h>
12 : : #include <errno.h>
13 : : #include <stdbool.h>
14 : : #include <string.h>
15 : :
16 : : #include <bpfilter/logger.h>
17 : : #include <bpfilter/matcher.h>
18 : :
19 : : #include "cgen/jmp.h"
20 : : #include "cgen/program.h"
21 : :
22 : 2431 : uint8_t bf_cmp_get_jmp_ins(const struct bf_matcher *matcher)
23 : : {
24 : : bool continue_on_equal;
25 : :
26 : : assert(matcher);
27 : :
28 [ + - + ]: 2431 : switch (bf_matcher_get_op(matcher)) {
29 : : case BF_MATCHER_EQ:
30 : : case BF_MATCHER_ALL:
31 : : continue_on_equal = true;
32 : : break;
33 : 325 : case BF_MATCHER_ANY:
34 : : case BF_MATCHER_IN:
35 : : continue_on_equal = false;
36 : 325 : break;
37 : 0 : default:
38 [ # # ]: 0 : bf_abort("invalid matcher op to get jmp instruction %d",
39 : : bf_matcher_get_op(matcher));
40 : : }
41 : :
42 : 2431 : continue_on_equal ^= bf_matcher_get_negate(matcher);
43 : :
44 [ + + ]: 2431 : return continue_on_equal ? BPF_JNE : BPF_JEQ;
45 : : }
46 : :
47 : : #define _BF_MASK_LAST_BYTE 15
48 : :
49 : : static inline uint64_t _bf_read_u64(const void *ptr)
50 : : {
51 : : uint64_t val;
52 : :
53 : 978 : memcpy(&val, ptr, sizeof(val));
54 : :
55 : : return val;
56 : : }
57 : :
58 : : /**
59 : : * @brief Emit a 4-instruction sequence to build a 64-bit immediate from 8 bytes.
60 : : *
61 : : * Produces:
62 : : * @code
63 : : * MOV32_IMM(dst, high32) -> LSH(dst, 32) -> MOV32_IMM(scratch, low32) -> OR(dst, scratch)
64 : : * @endcode
65 : : *
66 : : * @param program Program to emit into. Can't be NULL.
67 : : * @param dst_reg Destination register for the 64-bit value.
68 : : * @param scratch_reg Scratch register (clobbered).
69 : : * @param data 64-bit value to load.
70 : : */
71 : 978 : static int _bf_cmp_build_imm64(struct bf_program *program, int dst_reg,
72 : : int scratch_reg, uint64_t data)
73 : : {
74 [ + - ]: 978 : EMIT(program, BPF_MOV32_IMM(dst_reg, (uint32_t)(data >> 32)));
75 [ + - ]: 978 : EMIT(program, BPF_ALU64_IMM(BPF_LSH, dst_reg, 32));
76 [ + - ]: 978 : EMIT(program, BPF_MOV32_IMM(scratch_reg, (uint32_t)data));
77 : 978 : EMIT(program, BPF_ALU64_REG(BPF_OR, dst_reg, scratch_reg));
78 : :
79 : : return 0;
80 : : }
81 : :
82 : : /**
83 : : * @brief Compute a network prefix mask.
84 : : *
85 : : * @param prefixlen Prefix length in bits.
86 : : * @param mask Output buffer. Can't be NULL.
87 : : * @param mask_len Size of mask buffer in bytes (4 or 16).
88 : : */
89 : 393 : static void _bf_prefix_to_mask(unsigned int prefixlen, uint8_t *mask,
90 : : size_t mask_len)
91 : : {
92 : : assert(mask);
93 : :
94 : 393 : memset(mask, 0x00, mask_len);
95 : 393 : memset(mask, 0xff, prefixlen / 8);
96 [ + + ]: 393 : if (prefixlen % 8)
97 : 41 : mask[prefixlen / 8] = (0xff << (8 - prefixlen % 8)) & 0xff;
98 : 393 : }
99 : :
100 : 1493 : int bf_cmp_value(struct bf_program *program, const struct bf_matcher *matcher,
101 : : const void *ref, unsigned int size, int reg)
102 : : {
103 : 1493 : enum bf_matcher_op op = bf_matcher_get_op(matcher);
104 : : uint8_t jmp_op;
105 : :
106 : : assert(program);
107 : : assert(matcher);
108 : : assert(ref);
109 : :
110 [ - + ]: 1493 : if (op != BF_MATCHER_EQ)
111 [ # # ]: 0 : return bf_err_r(-EINVAL, "unsupported operator %d", op);
112 : :
113 : 1493 : jmp_op = bf_cmp_get_jmp_ins(matcher);
114 : :
115 [ + + - + : 1493 : switch (size) {
- ]
116 : 1179 : case 1:
117 : : case 2: {
118 : : /* Small values: compare directly via JMP_IMM.
119 : : * For size 1, ref is uint8_t; for size 2, ref is uint16_t.
120 : : * Both fit in a signed 32-bit immediate. */
121 : 1179 : uint32_t val =
122 [ + + ]: 1179 : (size == 1) ? *(const uint8_t *)ref : *(const uint16_t *)ref;
123 : :
124 [ - + ]: 1179 : EMIT_FIXUP_JMP_NEXT_RULE(program, BPF_JMP_IMM(jmp_op, reg, val, 0));
125 : 1179 : break;
126 : : }
127 : 177 : case 4: {
128 : : /* 32-bit values: may exceed signed 32-bit immediate range, so
129 : : * use MOV32_IMM into R2 + JMP_REG. */
130 : 177 : uint32_t val = *(const uint32_t *)ref;
131 : :
132 [ + - ]: 177 : EMIT(program, BPF_MOV32_IMM(BPF_REG_2, val));
133 [ - + ]: 177 : EMIT_FIXUP_JMP_NEXT_RULE(program,
134 : : BPF_JMP_REG(jmp_op, reg, BPF_REG_2, 0));
135 : 177 : break;
136 : : }
137 : : case 8: {
138 : : /* 64-bit values: build immediate in R2 via `_bf_cmp_build_imm64`,
139 : : * then compare with `JMP_REG`. */
140 : : int r;
141 : :
142 : 0 : r = _bf_cmp_build_imm64(program, BPF_REG_2, BPF_REG_3,
143 : : _bf_read_u64(ref));
144 [ # # ]: 0 : if (r)
145 : : return r;
146 [ # # ]: 0 : EMIT_FIXUP_JMP_NEXT_RULE(program,
147 : : BPF_JMP_REG(jmp_op, reg, BPF_REG_2, 0));
148 : 0 : break;
149 : : }
150 : 137 : case 16: {
151 : : /* 128-bit values: reg holds low 64 bits, reg+1 holds high 64 bits.
152 : : * Compare each half against the reference. */
153 : : const uint8_t *addr = ref;
154 : : int r;
155 : :
156 : 137 : r = _bf_cmp_build_imm64(program, BPF_REG_3, BPF_REG_4,
157 : : _bf_read_u64(addr));
158 [ + - ]: 137 : if (r)
159 : : return r;
160 : :
161 [ + + ]: 137 : if (jmp_op == BPF_JNE) {
162 [ - + ]: 66 : EMIT_FIXUP_JMP_NEXT_RULE(program,
163 : : BPF_JMP_REG(BPF_JNE, reg, BPF_REG_3, 0));
164 : :
165 : 66 : r = _bf_cmp_build_imm64(program, BPF_REG_3, BPF_REG_4,
166 : : _bf_read_u64(addr + 8));
167 [ + - ]: 66 : if (r)
168 : : return r;
169 [ - + ]: 66 : EMIT_FIXUP_JMP_NEXT_RULE(
170 : : program, BPF_JMP_REG(BPF_JNE, reg + 1, BPF_REG_3, 0));
171 : : } else {
172 : : /* JEQ: the address must differ in at least one half.
173 : : * If the first half differs, the matcher matched — jump
174 : : * past the second half check and the unconditional
175 : : * jump-to-next-rule. If the first half matches, check the
176 : : * second half: if it also matches, the full address is
177 : : * equal, so the matcher fails — jump to next rule. */
178 : 71 : _clean_bf_jmpctx_ struct bf_jmpctx j0 = bf_jmpctx_default();
179 : 71 : _clean_bf_jmpctx_ struct bf_jmpctx j1 = bf_jmpctx_default();
180 : :
181 : 71 : j0 =
182 [ + - ]: 71 : bf_jmpctx_get(program, BPF_JMP_REG(BPF_JNE, reg, BPF_REG_3, 0));
183 : :
184 : 71 : r = _bf_cmp_build_imm64(program, BPF_REG_3, BPF_REG_4,
185 : : _bf_read_u64(addr + 8));
186 [ + - ]: 71 : if (r)
187 : : return r;
188 [ + - ]: 71 : j1 = bf_jmpctx_get(program,
189 : : BPF_JMP_REG(BPF_JNE, reg + 1, BPF_REG_3, 0));
190 : :
191 [ - + ]: 71 : EMIT_FIXUP_JMP_NEXT_RULE(program, BPF_JMP_A(0));
192 : : }
193 : : break;
194 : : }
195 : 0 : default:
196 [ # # ]: 0 : return bf_err_r(-EINVAL, "unsupported comparison size %u", size);
197 : : }
198 : :
199 : : return 0;
200 : : }
201 : :
202 : 393 : int bf_cmp_masked_value(struct bf_program *program,
203 : : const struct bf_matcher *matcher, const void *ref,
204 : : unsigned int prefixlen, unsigned int size, int reg)
205 : : {
206 : 393 : enum bf_matcher_op op = bf_matcher_get_op(matcher);
207 : : uint8_t jmp_op;
208 : :
209 : : assert(program);
210 : : assert(matcher);
211 : : assert(ref);
212 : :
213 [ - + ]: 393 : if (op != BF_MATCHER_EQ)
214 [ # # ]: 0 : return bf_err_r(-EINVAL, "unsupported operator %d", op);
215 : :
216 : 393 : jmp_op = bf_cmp_get_jmp_ins(matcher);
217 : :
218 [ + + - ]: 393 : switch (size) {
219 : 176 : case 4: {
220 : : uint32_t mask;
221 : : const uint32_t *addr = ref;
222 : :
223 : 176 : _bf_prefix_to_mask(prefixlen, (uint8_t *)&mask, 4);
224 : :
225 [ + - ]: 176 : EMIT(program, BPF_MOV32_IMM(BPF_REG_2, *addr));
226 : :
227 [ + + ]: 176 : if (mask != ~0U) {
228 [ + - ]: 136 : EMIT(program, BPF_MOV32_IMM(BPF_REG_3, mask));
229 [ + - ]: 136 : EMIT(program, BPF_ALU32_REG(BPF_AND, reg, BPF_REG_3));
230 [ + - ]: 136 : EMIT(program, BPF_ALU32_REG(BPF_AND, BPF_REG_2, BPF_REG_3));
231 : : }
232 : :
233 [ - + ]: 176 : EMIT_FIXUP_JMP_NEXT_RULE(program,
234 : : BPF_JMP_REG(jmp_op, reg, BPF_REG_2, 0));
235 : 176 : break;
236 : : }
237 : 217 : case 16: {
238 : : uint8_t mask[16];
239 : : uint8_t masked_lo[8], masked_hi[8];
240 : : const uint8_t *addr = ref;
241 : : int r;
242 : :
243 : 217 : _bf_prefix_to_mask(prefixlen, mask, 16);
244 : :
245 : : // Apply mask to loaded reg/reg+1 if not a full /128
246 [ + + ]: 217 : if (mask[_BF_MASK_LAST_BYTE] != (uint8_t)~0) {
247 : 135 : r = _bf_cmp_build_imm64(program, BPF_REG_3, BPF_REG_4,
248 : : _bf_read_u64(mask));
249 [ + - ]: 135 : if (r)
250 : 0 : return r;
251 [ + - ]: 135 : EMIT(program, BPF_ALU64_REG(BPF_AND, reg, BPF_REG_3));
252 : :
253 : 135 : r = _bf_cmp_build_imm64(program, BPF_REG_3, BPF_REG_4,
254 : : _bf_read_u64(mask + 8));
255 [ + - ]: 135 : if (r)
256 : : return r;
257 [ + - ]: 135 : EMIT(program, BPF_ALU64_REG(BPF_AND, reg + 1, BPF_REG_3));
258 : : }
259 : :
260 [ + + ]: 1953 : for (int i = 0; i < 8; i++)
261 : 1736 : masked_lo[i] = addr[i] & mask[i];
262 [ + + ]: 1953 : for (int i = 0; i < 8; i++)
263 : 1736 : masked_hi[i] = addr[i + 8] & mask[i + 8];
264 : :
265 : 217 : r = _bf_cmp_build_imm64(program, BPF_REG_3, BPF_REG_4,
266 : : _bf_read_u64(masked_lo));
267 [ + - ]: 217 : if (r)
268 : : return r;
269 : :
270 [ + + ]: 217 : if (jmp_op == BPF_JNE) {
271 [ - + ]: 116 : EMIT_FIXUP_JMP_NEXT_RULE(program,
272 : : BPF_JMP_REG(BPF_JNE, reg, BPF_REG_3, 0));
273 : :
274 : 116 : r = _bf_cmp_build_imm64(program, BPF_REG_3, BPF_REG_4,
275 : : _bf_read_u64(masked_hi));
276 [ + - ]: 116 : if (r)
277 : : return r;
278 [ - + ]: 116 : EMIT_FIXUP_JMP_NEXT_RULE(
279 : : program, BPF_JMP_REG(BPF_JNE, reg + 1, BPF_REG_3, 0));
280 : : } else {
281 : 101 : _clean_bf_jmpctx_ struct bf_jmpctx j0 = bf_jmpctx_default();
282 : 101 : _clean_bf_jmpctx_ struct bf_jmpctx j1 = bf_jmpctx_default();
283 : :
284 : 101 : j0 =
285 [ + - ]: 101 : bf_jmpctx_get(program, BPF_JMP_REG(BPF_JNE, reg, BPF_REG_3, 0));
286 : :
287 : 101 : r = _bf_cmp_build_imm64(program, BPF_REG_3, BPF_REG_4,
288 : : _bf_read_u64(masked_hi));
289 [ + - ]: 101 : if (r)
290 : : return r;
291 [ + - ]: 101 : j1 = bf_jmpctx_get(program,
292 : : BPF_JMP_REG(BPF_JNE, reg + 1, BPF_REG_3, 0));
293 : :
294 [ - + ]: 101 : EMIT_FIXUP_JMP_NEXT_RULE(program, BPF_JMP_A(0));
295 : : }
296 : 217 : break;
297 : : }
298 : 0 : default:
299 [ # # ]: 0 : return bf_err_r(-EINVAL, "unsupported masked comparison size %u", size);
300 : : }
301 : :
302 : : return 0;
303 : : }
304 : :
305 : 222 : int bf_cmp_range(struct bf_program *program, const struct bf_matcher *matcher,
306 : : uint32_t min, uint32_t max, int reg)
307 : : {
308 : : assert(program);
309 : : assert(matcher);
310 : :
311 [ + + ]: 222 : if (bf_matcher_get_negate(matcher)) {
312 : 10 : _clean_bf_jmpctx_ struct bf_jmpctx j0 = bf_jmpctx_default();
313 : 10 : _clean_bf_jmpctx_ struct bf_jmpctx j1 = bf_jmpctx_default();
314 : :
315 [ + - ]: 10 : j0 = bf_jmpctx_get(program, BPF_JMP32_IMM(BPF_JLT, reg, min, 0));
316 [ + - ]: 10 : j1 = bf_jmpctx_get(program, BPF_JMP32_IMM(BPF_JGT, reg, max, 0));
317 [ - + ]: 10 : EMIT_FIXUP_JMP_NEXT_RULE(program, BPF_JMP_A(0));
318 : :
319 : 10 : return 0;
320 : : }
321 : :
322 [ - + ]: 212 : EMIT_FIXUP_JMP_NEXT_RULE(program, BPF_JMP32_IMM(BPF_JLT, reg, min, 0));
323 [ - + ]: 212 : EMIT_FIXUP_JMP_NEXT_RULE(program, BPF_JMP32_IMM(BPF_JGT, reg, max, 0));
324 : :
325 : 212 : return 0;
326 : : }
327 : :
328 : 100 : int bf_cmp_bitfield(struct bf_program *program,
329 : : const struct bf_matcher *matcher, uint32_t flags, int reg)
330 : : {
331 : 100 : enum bf_matcher_op op = bf_matcher_get_op(matcher);
332 : :
333 : : assert(program);
334 : : assert(matcher);
335 : :
336 [ - + ]: 100 : if (op != BF_MATCHER_ANY && op != BF_MATCHER_ALL)
337 [ # # ]: 0 : return bf_err_r(-EINVAL, "unsupported operator %d", op);
338 : :
339 [ + - ]: 100 : EMIT(program, BPF_ALU32_IMM(BPF_AND, reg, flags));
340 [ + + - + ]: 150 : EMIT_FIXUP_JMP_NEXT_RULE(
341 : : program, BPF_JMP32_IMM(bf_cmp_get_jmp_ins(matcher), reg,
342 : : op == BF_MATCHER_ANY ? 0 : flags, 0));
343 : :
344 : 100 : return 0;
345 : : }
|
