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