~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/tools/testing/selftests/bpf/test_align.c

Version: ~ [ linux-5.10-rc5 ] ~ [ linux-5.9.10 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.79 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.159 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.208 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.245 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.245 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 #include <asm/types.h>
  2 #include <linux/types.h>
  3 #include <stdint.h>
  4 #include <stdio.h>
  5 #include <stdlib.h>
  6 #include <unistd.h>
  7 #include <errno.h>
  8 #include <string.h>
  9 #include <stddef.h>
 10 #include <stdbool.h>
 11 
 12 #include <linux/unistd.h>
 13 #include <linux/filter.h>
 14 #include <linux/bpf_perf_event.h>
 15 #include <linux/bpf.h>
 16 
 17 #include <bpf/bpf.h>
 18 
 19 #include "../../../include/linux/filter.h"
 20 #include "bpf_rlimit.h"
 21 
 22 #ifndef ARRAY_SIZE
 23 # define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
 24 #endif
 25 
 26 #define MAX_INSNS       512
 27 #define MAX_MATCHES     16
 28 
 29 struct bpf_reg_match {
 30         unsigned int line;
 31         const char *match;
 32 };
 33 
 34 struct bpf_align_test {
 35         const char *descr;
 36         struct bpf_insn insns[MAX_INSNS];
 37         enum {
 38                 UNDEF,
 39                 ACCEPT,
 40                 REJECT
 41         } result;
 42         enum bpf_prog_type prog_type;
 43         /* Matches must be in order of increasing line */
 44         struct bpf_reg_match matches[MAX_MATCHES];
 45 };
 46 
 47 static struct bpf_align_test tests[] = {
 48         /* Four tests of known constants.  These aren't staggeringly
 49          * interesting since we track exact values now.
 50          */
 51         {
 52                 .descr = "mov",
 53                 .insns = {
 54                         BPF_MOV64_IMM(BPF_REG_3, 2),
 55                         BPF_MOV64_IMM(BPF_REG_3, 4),
 56                         BPF_MOV64_IMM(BPF_REG_3, 8),
 57                         BPF_MOV64_IMM(BPF_REG_3, 16),
 58                         BPF_MOV64_IMM(BPF_REG_3, 32),
 59                         BPF_MOV64_IMM(BPF_REG_0, 0),
 60                         BPF_EXIT_INSN(),
 61                 },
 62                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
 63                 .matches = {
 64                         {1, "R1=ctx(id=0,off=0,imm=0)"},
 65                         {1, "R10=fp0"},
 66                         {1, "R3_w=inv2"},
 67                         {2, "R3_w=inv4"},
 68                         {3, "R3_w=inv8"},
 69                         {4, "R3_w=inv16"},
 70                         {5, "R3_w=inv32"},
 71                 },
 72         },
 73         {
 74                 .descr = "shift",
 75                 .insns = {
 76                         BPF_MOV64_IMM(BPF_REG_3, 1),
 77                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
 78                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
 79                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
 80                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
 81                         BPF_ALU64_IMM(BPF_RSH, BPF_REG_3, 4),
 82                         BPF_MOV64_IMM(BPF_REG_4, 32),
 83                         BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
 84                         BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
 85                         BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
 86                         BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
 87                         BPF_MOV64_IMM(BPF_REG_0, 0),
 88                         BPF_EXIT_INSN(),
 89                 },
 90                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
 91                 .matches = {
 92                         {1, "R1=ctx(id=0,off=0,imm=0)"},
 93                         {1, "R10=fp0"},
 94                         {1, "R3_w=inv1"},
 95                         {2, "R3_w=inv2"},
 96                         {3, "R3_w=inv4"},
 97                         {4, "R3_w=inv8"},
 98                         {5, "R3_w=inv16"},
 99                         {6, "R3_w=inv1"},
100                         {7, "R4_w=inv32"},
101                         {8, "R4_w=inv16"},
102                         {9, "R4_w=inv8"},
103                         {10, "R4_w=inv4"},
104                         {11, "R4_w=inv2"},
105                 },
106         },
107         {
108                 .descr = "addsub",
109                 .insns = {
110                         BPF_MOV64_IMM(BPF_REG_3, 4),
111                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_3, 4),
112                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_3, 2),
113                         BPF_MOV64_IMM(BPF_REG_4, 8),
114                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
115                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 2),
116                         BPF_MOV64_IMM(BPF_REG_0, 0),
117                         BPF_EXIT_INSN(),
118                 },
119                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
120                 .matches = {
121                         {1, "R1=ctx(id=0,off=0,imm=0)"},
122                         {1, "R10=fp0"},
123                         {1, "R3_w=inv4"},
124                         {2, "R3_w=inv8"},
125                         {3, "R3_w=inv10"},
126                         {4, "R4_w=inv8"},
127                         {5, "R4_w=inv12"},
128                         {6, "R4_w=inv14"},
129                 },
130         },
131         {
132                 .descr = "mul",
133                 .insns = {
134                         BPF_MOV64_IMM(BPF_REG_3, 7),
135                         BPF_ALU64_IMM(BPF_MUL, BPF_REG_3, 1),
136                         BPF_ALU64_IMM(BPF_MUL, BPF_REG_3, 2),
137                         BPF_ALU64_IMM(BPF_MUL, BPF_REG_3, 4),
138                         BPF_MOV64_IMM(BPF_REG_0, 0),
139                         BPF_EXIT_INSN(),
140                 },
141                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
142                 .matches = {
143                         {1, "R1=ctx(id=0,off=0,imm=0)"},
144                         {1, "R10=fp0"},
145                         {1, "R3_w=inv7"},
146                         {2, "R3_w=inv7"},
147                         {3, "R3_w=inv14"},
148                         {4, "R3_w=inv56"},
149                 },
150         },
151 
152         /* Tests using unknown values */
153 #define PREP_PKT_POINTERS \
154         BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, \
155                     offsetof(struct __sk_buff, data)), \
156         BPF_LDX_MEM(BPF_W, BPF_REG_3, BPF_REG_1, \
157                     offsetof(struct __sk_buff, data_end))
158 
159 #define LOAD_UNKNOWN(DST_REG) \
160         PREP_PKT_POINTERS, \
161         BPF_MOV64_REG(BPF_REG_0, BPF_REG_2), \
162         BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, 8), \
163         BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_0, 1), \
164         BPF_EXIT_INSN(), \
165         BPF_LDX_MEM(BPF_B, DST_REG, BPF_REG_2, 0)
166 
167         {
168                 .descr = "unknown shift",
169                 .insns = {
170                         LOAD_UNKNOWN(BPF_REG_3),
171                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
172                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
173                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
174                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_3, 1),
175                         LOAD_UNKNOWN(BPF_REG_4),
176                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_4, 5),
177                         BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
178                         BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
179                         BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
180                         BPF_ALU64_IMM(BPF_RSH, BPF_REG_4, 1),
181                         BPF_MOV64_IMM(BPF_REG_0, 0),
182                         BPF_EXIT_INSN(),
183                 },
184                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
185                 .matches = {
186                         {7, "R0=pkt(id=0,off=8,r=8,imm=0)"},
187                         {7, "R3_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
188                         {8, "R3_w=inv(id=0,umax_value=510,var_off=(0x0; 0x1fe))"},
189                         {9, "R3_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
190                         {10, "R3_w=inv(id=0,umax_value=2040,var_off=(0x0; 0x7f8))"},
191                         {11, "R3_w=inv(id=0,umax_value=4080,var_off=(0x0; 0xff0))"},
192                         {18, "R3=pkt_end(id=0,off=0,imm=0)"},
193                         {18, "R4_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
194                         {19, "R4_w=inv(id=0,umax_value=8160,var_off=(0x0; 0x1fe0))"},
195                         {20, "R4_w=inv(id=0,umax_value=4080,var_off=(0x0; 0xff0))"},
196                         {21, "R4_w=inv(id=0,umax_value=2040,var_off=(0x0; 0x7f8))"},
197                         {22, "R4_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
198                         {23, "R4_w=inv(id=0,umax_value=510,var_off=(0x0; 0x1fe))"},
199                 },
200         },
201         {
202                 .descr = "unknown mul",
203                 .insns = {
204                         LOAD_UNKNOWN(BPF_REG_3),
205                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_3),
206                         BPF_ALU64_IMM(BPF_MUL, BPF_REG_4, 1),
207                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_3),
208                         BPF_ALU64_IMM(BPF_MUL, BPF_REG_4, 2),
209                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_3),
210                         BPF_ALU64_IMM(BPF_MUL, BPF_REG_4, 4),
211                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_3),
212                         BPF_ALU64_IMM(BPF_MUL, BPF_REG_4, 8),
213                         BPF_ALU64_IMM(BPF_MUL, BPF_REG_4, 2),
214                         BPF_MOV64_IMM(BPF_REG_0, 0),
215                         BPF_EXIT_INSN(),
216                 },
217                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
218                 .matches = {
219                         {7, "R3_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
220                         {8, "R4_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
221                         {9, "R4_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
222                         {10, "R4_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
223                         {11, "R4_w=inv(id=0,umax_value=510,var_off=(0x0; 0x1fe))"},
224                         {12, "R4_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
225                         {13, "R4_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
226                         {14, "R4_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
227                         {15, "R4_w=inv(id=0,umax_value=2040,var_off=(0x0; 0x7f8))"},
228                         {16, "R4_w=inv(id=0,umax_value=4080,var_off=(0x0; 0xff0))"},
229                 },
230         },
231         {
232                 .descr = "packet const offset",
233                 .insns = {
234                         PREP_PKT_POINTERS,
235                         BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
236 
237                         BPF_MOV64_IMM(BPF_REG_0, 0),
238 
239                         /* Skip over ethernet header.  */
240                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 14),
241                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
242                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
243                         BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
244                         BPF_EXIT_INSN(),
245 
246                         BPF_LDX_MEM(BPF_B, BPF_REG_4, BPF_REG_5, 0),
247                         BPF_LDX_MEM(BPF_B, BPF_REG_4, BPF_REG_5, 1),
248                         BPF_LDX_MEM(BPF_B, BPF_REG_4, BPF_REG_5, 2),
249                         BPF_LDX_MEM(BPF_B, BPF_REG_4, BPF_REG_5, 3),
250                         BPF_LDX_MEM(BPF_H, BPF_REG_4, BPF_REG_5, 0),
251                         BPF_LDX_MEM(BPF_H, BPF_REG_4, BPF_REG_5, 2),
252                         BPF_LDX_MEM(BPF_W, BPF_REG_4, BPF_REG_5, 0),
253 
254                         BPF_MOV64_IMM(BPF_REG_0, 0),
255                         BPF_EXIT_INSN(),
256                 },
257                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
258                 .matches = {
259                         {4, "R5_w=pkt(id=0,off=0,r=0,imm=0)"},
260                         {5, "R5_w=pkt(id=0,off=14,r=0,imm=0)"},
261                         {6, "R4_w=pkt(id=0,off=14,r=0,imm=0)"},
262                         {10, "R2=pkt(id=0,off=0,r=18,imm=0)"},
263                         {10, "R5=pkt(id=0,off=14,r=18,imm=0)"},
264                         {10, "R4_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff))"},
265                         {14, "R4_w=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff))"},
266                         {15, "R4_w=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff))"},
267                 },
268         },
269         {
270                 .descr = "packet variable offset",
271                 .insns = {
272                         LOAD_UNKNOWN(BPF_REG_6),
273                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_6, 2),
274 
275                         /* First, add a constant to the R5 packet pointer,
276                          * then a variable with a known alignment.
277                          */
278                         BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
279                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 14),
280                         BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
281                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
282                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
283                         BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
284                         BPF_EXIT_INSN(),
285                         BPF_LDX_MEM(BPF_W, BPF_REG_4, BPF_REG_5, 0),
286 
287                         /* Now, test in the other direction.  Adding first
288                          * the variable offset to R5, then the constant.
289                          */
290                         BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
291                         BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
292                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 14),
293                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
294                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
295                         BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
296                         BPF_EXIT_INSN(),
297                         BPF_LDX_MEM(BPF_W, BPF_REG_4, BPF_REG_5, 0),
298 
299                         /* Test multiple accumulations of unknown values
300                          * into a packet pointer.
301                          */
302                         BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
303                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 14),
304                         BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
305                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 4),
306                         BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
307                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
308                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
309                         BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
310                         BPF_EXIT_INSN(),
311                         BPF_LDX_MEM(BPF_W, BPF_REG_4, BPF_REG_5, 0),
312 
313                         BPF_MOV64_IMM(BPF_REG_0, 0),
314                         BPF_EXIT_INSN(),
315                 },
316                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
317                 .matches = {
318                         /* Calculated offset in R6 has unknown value, but known
319                          * alignment of 4.
320                          */
321                         {8, "R2=pkt(id=0,off=0,r=8,imm=0)"},
322                         {8, "R6_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
323                         /* Offset is added to packet pointer R5, resulting in
324                          * known fixed offset, and variable offset from R6.
325                          */
326                         {11, "R5_w=pkt(id=1,off=14,r=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
327                         /* At the time the word size load is performed from R5,
328                          * it's total offset is NET_IP_ALIGN + reg->off (0) +
329                          * reg->aux_off (14) which is 16.  Then the variable
330                          * offset is considered using reg->aux_off_align which
331                          * is 4 and meets the load's requirements.
332                          */
333                         {15, "R4=pkt(id=1,off=18,r=18,umax_value=1020,var_off=(0x0; 0x3fc))"},
334                         {15, "R5=pkt(id=1,off=14,r=18,umax_value=1020,var_off=(0x0; 0x3fc))"},
335                         /* Variable offset is added to R5 packet pointer,
336                          * resulting in auxiliary alignment of 4.
337                          */
338                         {18, "R5_w=pkt(id=2,off=0,r=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
339                         /* Constant offset is added to R5, resulting in
340                          * reg->off of 14.
341                          */
342                         {19, "R5_w=pkt(id=2,off=14,r=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
343                         /* At the time the word size load is performed from R5,
344                          * its total fixed offset is NET_IP_ALIGN + reg->off
345                          * (14) which is 16.  Then the variable offset is 4-byte
346                          * aligned, so the total offset is 4-byte aligned and
347                          * meets the load's requirements.
348                          */
349                         {23, "R4=pkt(id=2,off=18,r=18,umax_value=1020,var_off=(0x0; 0x3fc))"},
350                         {23, "R5=pkt(id=2,off=14,r=18,umax_value=1020,var_off=(0x0; 0x3fc))"},
351                         /* Constant offset is added to R5 packet pointer,
352                          * resulting in reg->off value of 14.
353                          */
354                         {26, "R5_w=pkt(id=0,off=14,r=8"},
355                         /* Variable offset is added to R5, resulting in a
356                          * variable offset of (4n).
357                          */
358                         {27, "R5_w=pkt(id=3,off=14,r=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
359                         /* Constant is added to R5 again, setting reg->off to 18. */
360                         {28, "R5_w=pkt(id=3,off=18,r=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
361                         /* And once more we add a variable; resulting var_off
362                          * is still (4n), fixed offset is not changed.
363                          * Also, we create a new reg->id.
364                          */
365                         {29, "R5_w=pkt(id=4,off=18,r=0,umax_value=2040,var_off=(0x0; 0x7fc))"},
366                         /* At the time the word size load is performed from R5,
367                          * its total fixed offset is NET_IP_ALIGN + reg->off (18)
368                          * which is 20.  Then the variable offset is (4n), so
369                          * the total offset is 4-byte aligned and meets the
370                          * load's requirements.
371                          */
372                         {33, "R4=pkt(id=4,off=22,r=22,umax_value=2040,var_off=(0x0; 0x7fc))"},
373                         {33, "R5=pkt(id=4,off=18,r=22,umax_value=2040,var_off=(0x0; 0x7fc))"},
374                 },
375         },
376         {
377                 .descr = "packet variable offset 2",
378                 .insns = {
379                         /* Create an unknown offset, (4n+2)-aligned */
380                         LOAD_UNKNOWN(BPF_REG_6),
381                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_6, 2),
382                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_6, 14),
383                         /* Add it to the packet pointer */
384                         BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
385                         BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
386                         /* Check bounds and perform a read */
387                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
388                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
389                         BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
390                         BPF_EXIT_INSN(),
391                         BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_5, 0),
392                         /* Make a (4n) offset from the value we just read */
393                         BPF_ALU64_IMM(BPF_AND, BPF_REG_6, 0xff),
394                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_6, 2),
395                         /* Add it to the packet pointer */
396                         BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
397                         /* Check bounds and perform a read */
398                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
399                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
400                         BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
401                         BPF_EXIT_INSN(),
402                         BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_5, 0),
403                         BPF_MOV64_IMM(BPF_REG_0, 0),
404                         BPF_EXIT_INSN(),
405                 },
406                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
407                 .matches = {
408                         /* Calculated offset in R6 has unknown value, but known
409                          * alignment of 4.
410                          */
411                         {8, "R2=pkt(id=0,off=0,r=8,imm=0)"},
412                         {8, "R6_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
413                         /* Adding 14 makes R6 be (4n+2) */
414                         {9, "R6_w=inv(id=0,umin_value=14,umax_value=1034,var_off=(0x2; 0x7fc))"},
415                         /* Packet pointer has (4n+2) offset */
416                         {11, "R5_w=pkt(id=1,off=0,r=0,umin_value=14,umax_value=1034,var_off=(0x2; 0x7fc))"},
417                         {13, "R4=pkt(id=1,off=4,r=0,umin_value=14,umax_value=1034,var_off=(0x2; 0x7fc))"},
418                         /* At the time the word size load is performed from R5,
419                          * its total fixed offset is NET_IP_ALIGN + reg->off (0)
420                          * which is 2.  Then the variable offset is (4n+2), so
421                          * the total offset is 4-byte aligned and meets the
422                          * load's requirements.
423                          */
424                         {15, "R5=pkt(id=1,off=0,r=4,umin_value=14,umax_value=1034,var_off=(0x2; 0x7fc))"},
425                         /* Newly read value in R6 was shifted left by 2, so has
426                          * known alignment of 4.
427                          */
428                         {18, "R6_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
429                         /* Added (4n) to packet pointer's (4n+2) var_off, giving
430                          * another (4n+2).
431                          */
432                         {19, "R5_w=pkt(id=2,off=0,r=0,umin_value=14,umax_value=2054,var_off=(0x2; 0xffc))"},
433                         {21, "R4=pkt(id=2,off=4,r=0,umin_value=14,umax_value=2054,var_off=(0x2; 0xffc))"},
434                         /* At the time the word size load is performed from R5,
435                          * its total fixed offset is NET_IP_ALIGN + reg->off (0)
436                          * which is 2.  Then the variable offset is (4n+2), so
437                          * the total offset is 4-byte aligned and meets the
438                          * load's requirements.
439                          */
440                         {23, "R5=pkt(id=2,off=0,r=4,umin_value=14,umax_value=2054,var_off=(0x2; 0xffc))"},
441                 },
442         },
443         {
444                 .descr = "dubious pointer arithmetic",
445                 .insns = {
446                         PREP_PKT_POINTERS,
447                         BPF_MOV64_IMM(BPF_REG_0, 0),
448                         /* (ptr - ptr) << 2 */
449                         BPF_MOV64_REG(BPF_REG_5, BPF_REG_3),
450                         BPF_ALU64_REG(BPF_SUB, BPF_REG_5, BPF_REG_2),
451                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_5, 2),
452                         /* We have a (4n) value.  Let's make a packet offset
453                          * out of it.  First add 14, to make it a (4n+2)
454                          */
455                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_5, 14),
456                         /* Then make sure it's nonnegative */
457                         BPF_JMP_IMM(BPF_JSGE, BPF_REG_5, 0, 1),
458                         BPF_EXIT_INSN(),
459                         /* Add it to packet pointer */
460                         BPF_MOV64_REG(BPF_REG_6, BPF_REG_2),
461                         BPF_ALU64_REG(BPF_ADD, BPF_REG_6, BPF_REG_5),
462                         /* Check bounds and perform a read */
463                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_6),
464                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
465                         BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
466                         BPF_EXIT_INSN(),
467                         BPF_LDX_MEM(BPF_W, BPF_REG_4, BPF_REG_6, 0),
468                         BPF_EXIT_INSN(),
469                 },
470                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
471                 .result = REJECT,
472                 .matches = {
473                         {4, "R5_w=pkt_end(id=0,off=0,imm=0)"},
474                         /* (ptr - ptr) << 2 == unknown, (4n) */
475                         {6, "R5_w=inv(id=0,smax_value=9223372036854775804,umax_value=18446744073709551612,var_off=(0x0; 0xfffffffffffffffc))"},
476                         /* (4n) + 14 == (4n+2).  We blow our bounds, because
477                          * the add could overflow.
478                          */
479                         {7, "R5=inv(id=0,var_off=(0x2; 0xfffffffffffffffc))"},
480                         /* Checked s>=0 */
481                         {9, "R5=inv(id=0,umin_value=2,umax_value=9223372036854775806,var_off=(0x2; 0x7ffffffffffffffc))"},
482                         /* packet pointer + nonnegative (4n+2) */
483                         {11, "R6_w=pkt(id=1,off=0,r=0,umin_value=2,umax_value=9223372036854775806,var_off=(0x2; 0x7ffffffffffffffc))"},
484                         {13, "R4=pkt(id=1,off=4,r=0,umin_value=2,umax_value=9223372036854775806,var_off=(0x2; 0x7ffffffffffffffc))"},
485                         /* NET_IP_ALIGN + (4n+2) == (4n), alignment is fine.
486                          * We checked the bounds, but it might have been able
487                          * to overflow if the packet pointer started in the
488                          * upper half of the address space.
489                          * So we did not get a 'range' on R6, and the access
490                          * attempt will fail.
491                          */
492                         {15, "R6=pkt(id=1,off=0,r=0,umin_value=2,umax_value=9223372036854775806,var_off=(0x2; 0x7ffffffffffffffc))"},
493                 }
494         },
495         {
496                 .descr = "variable subtraction",
497                 .insns = {
498                         /* Create an unknown offset, (4n+2)-aligned */
499                         LOAD_UNKNOWN(BPF_REG_6),
500                         BPF_MOV64_REG(BPF_REG_7, BPF_REG_6),
501                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_6, 2),
502                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_6, 14),
503                         /* Create another unknown, (4n)-aligned, and subtract
504                          * it from the first one
505                          */
506                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_7, 2),
507                         BPF_ALU64_REG(BPF_SUB, BPF_REG_6, BPF_REG_7),
508                         /* Bounds-check the result */
509                         BPF_JMP_IMM(BPF_JSGE, BPF_REG_6, 0, 1),
510                         BPF_EXIT_INSN(),
511                         /* Add it to the packet pointer */
512                         BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
513                         BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_6),
514                         /* Check bounds and perform a read */
515                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
516                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
517                         BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
518                         BPF_EXIT_INSN(),
519                         BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_5, 0),
520                         BPF_EXIT_INSN(),
521                 },
522                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
523                 .matches = {
524                         /* Calculated offset in R6 has unknown value, but known
525                          * alignment of 4.
526                          */
527                         {7, "R2=pkt(id=0,off=0,r=8,imm=0)"},
528                         {9, "R6_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
529                         /* Adding 14 makes R6 be (4n+2) */
530                         {10, "R6_w=inv(id=0,umin_value=14,umax_value=1034,var_off=(0x2; 0x7fc))"},
531                         /* New unknown value in R7 is (4n) */
532                         {11, "R7_w=inv(id=0,umax_value=1020,var_off=(0x0; 0x3fc))"},
533                         /* Subtracting it from R6 blows our unsigned bounds */
534                         {12, "R6=inv(id=0,smin_value=-1006,smax_value=1034,var_off=(0x2; 0xfffffffffffffffc))"},
535                         /* Checked s>= 0 */
536                         {14, "R6=inv(id=0,umin_value=2,umax_value=1034,var_off=(0x2; 0x7fc))"},
537                         /* At the time the word size load is performed from R5,
538                          * its total fixed offset is NET_IP_ALIGN + reg->off (0)
539                          * which is 2.  Then the variable offset is (4n+2), so
540                          * the total offset is 4-byte aligned and meets the
541                          * load's requirements.
542                          */
543                         {20, "R5=pkt(id=1,off=0,r=4,umin_value=2,umax_value=1034,var_off=(0x2; 0x7fc))"},
544                 },
545         },
546         {
547                 .descr = "pointer variable subtraction",
548                 .insns = {
549                         /* Create an unknown offset, (4n+2)-aligned and bounded
550                          * to [14,74]
551                          */
552                         LOAD_UNKNOWN(BPF_REG_6),
553                         BPF_MOV64_REG(BPF_REG_7, BPF_REG_6),
554                         BPF_ALU64_IMM(BPF_AND, BPF_REG_6, 0xf),
555                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_6, 2),
556                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_6, 14),
557                         /* Subtract it from the packet pointer */
558                         BPF_MOV64_REG(BPF_REG_5, BPF_REG_2),
559                         BPF_ALU64_REG(BPF_SUB, BPF_REG_5, BPF_REG_6),
560                         /* Create another unknown, (4n)-aligned and >= 74.
561                          * That in fact means >= 76, since 74 % 4 == 2
562                          */
563                         BPF_ALU64_IMM(BPF_LSH, BPF_REG_7, 2),
564                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_7, 76),
565                         /* Add it to the packet pointer */
566                         BPF_ALU64_REG(BPF_ADD, BPF_REG_5, BPF_REG_7),
567                         /* Check bounds and perform a read */
568                         BPF_MOV64_REG(BPF_REG_4, BPF_REG_5),
569                         BPF_ALU64_IMM(BPF_ADD, BPF_REG_4, 4),
570                         BPF_JMP_REG(BPF_JGE, BPF_REG_3, BPF_REG_4, 1),
571                         BPF_EXIT_INSN(),
572                         BPF_LDX_MEM(BPF_W, BPF_REG_6, BPF_REG_5, 0),
573                         BPF_EXIT_INSN(),
574                 },
575                 .prog_type = BPF_PROG_TYPE_SCHED_CLS,
576                 .matches = {
577                         /* Calculated offset in R6 has unknown value, but known
578                          * alignment of 4.
579                          */
580                         {7, "R2=pkt(id=0,off=0,r=8,imm=0)"},
581                         {10, "R6_w=inv(id=0,umax_value=60,var_off=(0x0; 0x3c))"},
582                         /* Adding 14 makes R6 be (4n+2) */
583                         {11, "R6_w=inv(id=0,umin_value=14,umax_value=74,var_off=(0x2; 0x7c))"},
584                         /* Subtracting from packet pointer overflows ubounds */
585                         {13, "R5_w=pkt(id=1,off=0,r=8,umin_value=18446744073709551542,umax_value=18446744073709551602,var_off=(0xffffffffffffff82; 0x7c))"},
586                         /* New unknown value in R7 is (4n), >= 76 */
587                         {15, "R7_w=inv(id=0,umin_value=76,umax_value=1096,var_off=(0x0; 0x7fc))"},
588                         /* Adding it to packet pointer gives nice bounds again */
589                         {16, "R5_w=pkt(id=2,off=0,r=0,umin_value=2,umax_value=1082,var_off=(0x2; 0x7fc))"},
590                         /* At the time the word size load is performed from R5,
591                          * its total fixed offset is NET_IP_ALIGN + reg->off (0)
592                          * which is 2.  Then the variable offset is (4n+2), so
593                          * the total offset is 4-byte aligned and meets the
594                          * load's requirements.
595                          */
596                         {20, "R5=pkt(id=2,off=0,r=4,umin_value=2,umax_value=1082,var_off=(0x2; 0x7fc))"},
597                 },
598         },
599 };
600 
601 static int probe_filter_length(const struct bpf_insn *fp)
602 {
603         int len;
604 
605         for (len = MAX_INSNS - 1; len > 0; --len)
606                 if (fp[len].code != 0 || fp[len].imm != 0)
607                         break;
608         return len + 1;
609 }
610 
611 static char bpf_vlog[32768];
612 
613 static int do_test_single(struct bpf_align_test *test)
614 {
615         struct bpf_insn *prog = test->insns;
616         int prog_type = test->prog_type;
617         char bpf_vlog_copy[32768];
618         const char *line_ptr;
619         int cur_line = -1;
620         int prog_len, i;
621         int fd_prog;
622         int ret;
623 
624         prog_len = probe_filter_length(prog);
625         fd_prog = bpf_verify_program(prog_type ? : BPF_PROG_TYPE_SOCKET_FILTER,
626                                      prog, prog_len, 1, "GPL", 0,
627                                      bpf_vlog, sizeof(bpf_vlog), 2);
628         if (fd_prog < 0 && test->result != REJECT) {
629                 printf("Failed to load program.\n");
630                 printf("%s", bpf_vlog);
631                 ret = 1;
632         } else if (fd_prog >= 0 && test->result == REJECT) {
633                 printf("Unexpected success to load!\n");
634                 printf("%s", bpf_vlog);
635                 ret = 1;
636                 close(fd_prog);
637         } else {
638                 ret = 0;
639                 /* We make a local copy so that we can strtok() it */
640                 strncpy(bpf_vlog_copy, bpf_vlog, sizeof(bpf_vlog_copy));
641                 line_ptr = strtok(bpf_vlog_copy, "\n");
642                 for (i = 0; i < MAX_MATCHES; i++) {
643                         struct bpf_reg_match m = test->matches[i];
644 
645                         if (!m.match)
646                                 break;
647                         while (line_ptr) {
648                                 cur_line = -1;
649                                 sscanf(line_ptr, "%u: ", &cur_line);
650                                 if (cur_line == m.line)
651                                         break;
652                                 line_ptr = strtok(NULL, "\n");
653                         }
654                         if (!line_ptr) {
655                                 printf("Failed to find line %u for match: %s\n",
656                                        m.line, m.match);
657                                 ret = 1;
658                                 printf("%s", bpf_vlog);
659                                 break;
660                         }
661                         if (!strstr(line_ptr, m.match)) {
662                                 printf("Failed to find match %u: %s\n",
663                                        m.line, m.match);
664                                 ret = 1;
665                                 printf("%s", bpf_vlog);
666                                 break;
667                         }
668                 }
669                 if (fd_prog >= 0)
670                         close(fd_prog);
671         }
672         return ret;
673 }
674 
675 static int do_test(unsigned int from, unsigned int to)
676 {
677         int all_pass = 0;
678         int all_fail = 0;
679         unsigned int i;
680 
681         for (i = from; i < to; i++) {
682                 struct bpf_align_test *test = &tests[i];
683                 int fail;
684 
685                 printf("Test %3d: %s ... ",
686                        i, test->descr);
687                 fail = do_test_single(test);
688                 if (fail) {
689                         all_fail++;
690                         printf("FAIL\n");
691                 } else {
692                         all_pass++;
693                         printf("PASS\n");
694                 }
695         }
696         printf("Results: %d pass %d fail\n",
697                all_pass, all_fail);
698         return all_fail ? EXIT_FAILURE : EXIT_SUCCESS;
699 }
700 
701 int main(int argc, char **argv)
702 {
703         unsigned int from = 0, to = ARRAY_SIZE(tests);
704 
705         if (argc == 3) {
706                 unsigned int l = atoi(argv[argc - 2]);
707                 unsigned int u = atoi(argv[argc - 1]);
708 
709                 if (l < to && u < to) {
710                         from = l;
711                         to   = u + 1;
712                 }
713         } else if (argc == 2) {
714                 unsigned int t = atoi(argv[argc - 1]);
715 
716                 if (t < to) {
717                         from = t;
718                         to   = t + 1;
719                 }
720         }
721         return do_test(from, to);
722 }
723 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp