1 // SPDX-License-Identifier: GPL-2.0-only
2 /* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */
3 #include <linux/bpf.h>
4 #include <linux/btf.h>
5 #include <linux/bpf_verifier.h>
6 #include <linux/filter.h>
7 #include <linux/vmalloc.h>
8 #include <linux/bsearch.h>
9 #include <linux/sort.h>
10 #include <linux/perf_event.h>
11 #include <linux/sched/signal.h>
12 #include <net/xdp.h>
13 #include "disasm.h"
14
15 #define verbose(env, fmt, args...) bpf_verifier_log_write(env, fmt, ##args)
16
17 /*
18 * Matches BPF_PROBE_ATOMIC too: bpf_convert_ctx_accesses() rewrites arena
19 * atomics before bpf_opt_subreg_zext_lo32_rnd_hi32() runs.
20 */
is_cmpxchg_insn(const struct bpf_insn * insn)21 static bool is_cmpxchg_insn(const struct bpf_insn *insn)
22 {
23 return BPF_CLASS(insn->code) == BPF_STX &&
24 (BPF_MODE(insn->code) == BPF_ATOMIC ||
25 BPF_MODE(insn->code) == BPF_PROBE_ATOMIC) &&
26 insn->imm == BPF_CMPXCHG;
27 }
28
29 /* Returns true if 'insn' is an address space cast instruction translated as BPF_ALU op */
is_addr_space_cast32(struct bpf_prog * prog,const struct bpf_insn * insn)30 static bool is_addr_space_cast32(struct bpf_prog *prog, const struct bpf_insn *insn)
31 {
32 struct bpf_map *arena = (struct bpf_map *)prog->aux->arena;
33
34 if (insn->code != (BPF_ALU64 | BPF_MOV | BPF_X) || insn->off != BPF_ADDR_SPACE_CAST)
35 return false;
36
37 /* cast from as(1) to as(0) */
38 if (insn->imm == 1)
39 return true;
40
41 /* cast from as(0) to as(1) */
42 if (insn->imm == 1 << 16)
43 return arena && arena->map_flags & BPF_F_NO_USER_CONV;
44
45 /* non-BPF_F_NO_USER_CONV cast from as(0) to as(1) should be handled by JIT */
46 return false;
47 }
48
49 /* Return the regno defined by the insn, or -1. */
insn_def_regno(const struct bpf_insn * insn)50 static int insn_def_regno(const struct bpf_insn *insn)
51 {
52 switch (BPF_CLASS(insn->code)) {
53 case BPF_JMP:
54 case BPF_JMP32:
55 case BPF_ST:
56 return -1;
57 case BPF_STX:
58 return bpf_atomic_load_reg(insn);
59 default:
60 return insn->dst_reg;
61 }
62 }
63
64 /*
65 * For use only in combination with insn_def_regno() >= 0.
66 * Returns TRUE if the destination register operates on 64-bit,
67 * otherwise return FALSE.
68 */
bpf_is_reg64(struct bpf_prog * prog,struct bpf_insn * insn)69 static bool bpf_is_reg64(struct bpf_prog *prog, struct bpf_insn *insn)
70 {
71 u8 class = BPF_CLASS(insn->code);
72 u8 mode = BPF_MODE(insn->code);
73 u8 size = BPF_SIZE(insn->code);
74 u8 op = BPF_OP(insn->code);
75 bool mode_mem;
76
77 /* subregister endiness swap */
78 if ((class == BPF_ALU || class == BPF_ALU64) && op == BPF_END && insn->imm != 64)
79 return false;
80
81 /* w0 += 1 */
82 if (class == BPF_ALU && op != BPF_END)
83 return false;
84
85 /* address space casts converted to BPF_ALU, see bpf_do_misc_fixups() */
86 if (is_addr_space_cast32(prog, insn))
87 return false;
88
89 /* non 64-bit, non signed extended loads */
90 mode_mem = mode == BPF_MEM || mode == BPF_PROBE_MEM || mode == BPF_PROBE_MEM32;
91 if (class == BPF_LDX && mode_mem && size != BPF_DW)
92 return false;
93
94 /* atomics, see insn_def_regno() */
95 if (class == BPF_STX && size != BPF_DW)
96 return false;
97
98 /* both LD_IND and LD_ABS return 32-bit data. */
99 if (class == BPF_LD && (mode == BPF_IND || mode == BPF_ABS))
100 return false;
101
102 /* Conservatively return true at default. */
103 return true;
104 }
105
106 /*
107 * Return the 32-bit subregister defined by INSN, or -1 if INSN does not
108 * explicitly define a 32-bit value.
109 */
bpf_insn_def32(struct bpf_prog * prog,struct bpf_insn * insn)110 int bpf_insn_def32(struct bpf_prog *prog, struct bpf_insn *insn)
111 {
112 int dst_reg = insn_def_regno(insn);
113
114 if (dst_reg < 0 || bpf_is_reg64(prog, insn))
115 return -1;
116
117 return dst_reg;
118 }
119
kfunc_desc_cmp_by_imm_off(const void * a,const void * b)120 static int kfunc_desc_cmp_by_imm_off(const void *a, const void *b)
121 {
122 const struct bpf_kfunc_desc *d0 = a;
123 const struct bpf_kfunc_desc *d1 = b;
124
125 if (d0->imm != d1->imm)
126 return d0->imm < d1->imm ? -1 : 1;
127 if (d0->offset != d1->offset)
128 return d0->offset < d1->offset ? -1 : 1;
129 return 0;
130 }
131
132 const struct btf_func_model *
bpf_jit_find_kfunc_model(const struct bpf_prog * prog,const struct bpf_insn * insn)133 bpf_jit_find_kfunc_model(const struct bpf_prog *prog,
134 const struct bpf_insn *insn)
135 {
136 const struct bpf_kfunc_desc desc = {
137 .imm = insn->imm,
138 .offset = insn->off,
139 };
140 const struct bpf_kfunc_desc *res;
141 struct bpf_kfunc_desc_tab *tab;
142
143 tab = prog->aux->kfunc_tab;
144 res = bsearch(&desc, tab->descs, tab->nr_descs,
145 sizeof(tab->descs[0]), kfunc_desc_cmp_by_imm_off);
146
147 return res ? &res->func_model : NULL;
148 }
149
set_kfunc_desc_imm(struct bpf_verifier_env * env,struct bpf_kfunc_desc * desc)150 static int set_kfunc_desc_imm(struct bpf_verifier_env *env, struct bpf_kfunc_desc *desc)
151 {
152 unsigned long call_imm;
153
154 if (bpf_jit_supports_far_kfunc_call()) {
155 call_imm = desc->func_id;
156 } else {
157 call_imm = BPF_CALL_IMM(desc->addr);
158 /* Check whether the relative offset overflows desc->imm */
159 if ((unsigned long)(s32)call_imm != call_imm) {
160 verbose(env, "address of kernel func_id %u is out of range\n",
161 desc->func_id);
162 return -EINVAL;
163 }
164 }
165 desc->imm = call_imm;
166 return 0;
167 }
168
sort_kfunc_descs_by_imm_off(struct bpf_verifier_env * env)169 static int sort_kfunc_descs_by_imm_off(struct bpf_verifier_env *env)
170 {
171 struct bpf_kfunc_desc_tab *tab;
172 int i, err;
173
174 tab = env->prog->aux->kfunc_tab;
175 if (!tab)
176 return 0;
177
178 for (i = 0; i < tab->nr_descs; i++) {
179 err = set_kfunc_desc_imm(env, &tab->descs[i]);
180 if (err)
181 return err;
182 }
183
184 sort(tab->descs, tab->nr_descs, sizeof(tab->descs[0]),
185 kfunc_desc_cmp_by_imm_off, NULL);
186 return 0;
187 }
188
add_kfunc_in_insns(struct bpf_verifier_env * env,struct bpf_insn * insn,int cnt)189 static int add_kfunc_in_insns(struct bpf_verifier_env *env,
190 struct bpf_insn *insn, int cnt)
191 {
192 int i, ret;
193
194 for (i = 0; i < cnt; i++, insn++) {
195 if (bpf_pseudo_kfunc_call(insn)) {
196 ret = bpf_add_kfunc_call(env, insn->imm, insn->off);
197 if (ret < 0)
198 return ret;
199 }
200 }
201 return 0;
202 }
203
204 #ifndef CONFIG_BPF_JIT_ALWAYS_ON
get_callee_stack_depth(struct bpf_verifier_env * env,const struct bpf_insn * insn,int idx)205 static int get_callee_stack_depth(struct bpf_verifier_env *env,
206 const struct bpf_insn *insn, int idx)
207 {
208 int start = idx + insn->imm + 1, subprog;
209
210 subprog = bpf_find_subprog(env, start);
211 if (verifier_bug_if(subprog < 0, env, "get stack depth: no program at insn %d", start))
212 return -EFAULT;
213 return env->subprog_info[subprog].stack_depth;
214 }
215 #endif
216
217 /* single env->prog->insni[off] instruction was replaced with the range
218 * insni[off, off + cnt). Adjust corresponding insn_aux_data by copying
219 * [0, off) and [off, end) to new locations, so the patched range stays zero
220 */
adjust_insn_aux_data(struct bpf_verifier_env * env,struct bpf_prog * new_prog,u32 off,u32 cnt)221 static void adjust_insn_aux_data(struct bpf_verifier_env *env,
222 struct bpf_prog *new_prog, u32 off, u32 cnt)
223 {
224 struct bpf_insn_aux_data *data = env->insn_aux_data;
225 struct bpf_insn *insn = new_prog->insnsi;
226 u32 old_seen = data[off].seen;
227 u32 prog_len;
228 int i;
229
230 /* aux info at OFF always needs adjustment, no matter fast path
231 * (cnt == 1) is taken or not. There is no guarantee INSN at OFF is the
232 * original insn at old prog.
233 */
234 data[off].zext_dst = bpf_insn_def32(new_prog, insn + off + cnt - 1) >= 0;
235
236 if (cnt == 1)
237 return;
238 prog_len = new_prog->len;
239 env->insn_aux_data_len = prog_len;
240
241 memmove(data + off + cnt - 1, data + off,
242 sizeof(struct bpf_insn_aux_data) * (prog_len - off - cnt + 1));
243 memset(data + off, 0, sizeof(struct bpf_insn_aux_data) * (cnt - 1));
244 for (i = off; i < off + cnt - 1; i++) {
245 /* Expand insni[off]'s seen count to the patched range. */
246 data[i].seen = old_seen;
247 data[i].zext_dst = bpf_insn_def32(new_prog, insn + i) >= 0;
248 }
249
250 /*
251 * The indirect_target flag of the original instruction was moved to the last of the
252 * new instructions by the above memmove and memset, but the indirect jump target is
253 * actually the first instruction, so move it back. This also matches with the behavior
254 * of bpf_insn_array_adjust(), which preserves xlated_off to point to the first new
255 * instruction.
256 */
257 if (data[off + cnt - 1].indirect_target) {
258 data[off].indirect_target = 1;
259 data[off + cnt - 1].indirect_target = 0;
260 }
261 }
262
adjust_subprog_starts(struct bpf_verifier_env * env,u32 off,u32 len)263 static void adjust_subprog_starts(struct bpf_verifier_env *env, u32 off, u32 len)
264 {
265 int i;
266
267 if (len == 1)
268 return;
269 /* NOTE: fake 'exit' subprog should be updated as well. */
270 for (i = 0; i <= env->subprog_cnt; i++) {
271 if (env->subprog_info[i].start <= off)
272 continue;
273 env->subprog_info[i].start += len - 1;
274 }
275 }
276
adjust_insn_arrays(struct bpf_verifier_env * env,u32 off,u32 len)277 static void adjust_insn_arrays(struct bpf_verifier_env *env, u32 off, u32 len)
278 {
279 int i;
280
281 if (len == 1)
282 return;
283
284 for (i = 0; i < env->insn_array_map_cnt; i++)
285 bpf_insn_array_adjust(env->insn_array_maps[i], off, len);
286 }
287
adjust_insn_arrays_after_remove(struct bpf_verifier_env * env,u32 off,u32 len)288 static void adjust_insn_arrays_after_remove(struct bpf_verifier_env *env, u32 off, u32 len)
289 {
290 int i;
291
292 for (i = 0; i < env->insn_array_map_cnt; i++)
293 bpf_insn_array_adjust_after_remove(env->insn_array_maps[i], off, len);
294 }
295
adjust_poke_descs(struct bpf_prog * prog,u32 off,u32 len)296 static void adjust_poke_descs(struct bpf_prog *prog, u32 off, u32 len)
297 {
298 struct bpf_jit_poke_descriptor *tab = prog->aux->poke_tab;
299 int i, sz = prog->aux->size_poke_tab;
300 struct bpf_jit_poke_descriptor *desc;
301
302 for (i = 0; i < sz; i++) {
303 desc = &tab[i];
304 if (desc->insn_idx <= off)
305 continue;
306 desc->insn_idx += len - 1;
307 }
308 }
309
310 /*
311 * Some post-verification instruction rewriting passes require an
312 * O(prog->len) operation per instruction. Keep their shared primitives
313 * killable and preemptible.
314 */
bpf_rewrite_must_abort(void)315 static bool bpf_rewrite_must_abort(void)
316 {
317 if (fatal_signal_pending(current))
318 return true;
319 cond_resched();
320 return false;
321 }
322
bpf_patch_insn_data(struct bpf_verifier_env * env,u32 off,const struct bpf_insn * patch,u32 len)323 struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off,
324 const struct bpf_insn *patch, u32 len)
325 {
326 struct bpf_prog *new_prog;
327 struct bpf_insn_aux_data *new_data = NULL;
328
329 if (bpf_rewrite_must_abort())
330 return NULL;
331
332 if (len > 1) {
333 new_data = vrealloc(env->insn_aux_data,
334 array_size(env->prog->len + len - 1,
335 sizeof(struct bpf_insn_aux_data)),
336 GFP_KERNEL_ACCOUNT | __GFP_ZERO);
337 if (!new_data)
338 return NULL;
339
340 env->insn_aux_data = new_data;
341 }
342
343 new_prog = bpf_patch_insn_single(env->prog, off, patch, len);
344 if (IS_ERR(new_prog)) {
345 if (PTR_ERR(new_prog) == -ERANGE)
346 verbose(env,
347 "insn %d cannot be patched due to 16-bit range\n",
348 env->insn_aux_data[off].orig_idx);
349 return NULL;
350 }
351 adjust_insn_aux_data(env, new_prog, off, len);
352 adjust_subprog_starts(env, off, len);
353 adjust_insn_arrays(env, off, len);
354 adjust_poke_descs(new_prog, off, len);
355 return new_prog;
356 }
357
358 /*
359 * For all jmp insns in a given 'prog' that point to 'tgt_idx' insn adjust the
360 * jump offset by 'delta'.
361 */
adjust_jmp_off(struct bpf_prog * prog,u32 tgt_idx,u32 delta)362 static int adjust_jmp_off(struct bpf_prog *prog, u32 tgt_idx, u32 delta)
363 {
364 struct bpf_insn *insn = prog->insnsi;
365 u32 insn_cnt = prog->len, i;
366 s32 imm;
367 s16 off;
368
369 for (i = 0; i < insn_cnt; i++, insn++) {
370 u8 code = insn->code;
371
372 if (tgt_idx <= i && i < tgt_idx + delta)
373 continue;
374
375 if ((BPF_CLASS(code) != BPF_JMP && BPF_CLASS(code) != BPF_JMP32) ||
376 BPF_OP(code) == BPF_CALL || BPF_OP(code) == BPF_EXIT)
377 continue;
378
379 if (insn->code == (BPF_JMP32 | BPF_JA)) {
380 if (i + 1 + insn->imm != tgt_idx)
381 continue;
382 if (check_add_overflow(insn->imm, delta, &imm))
383 return -ERANGE;
384 insn->imm = imm;
385 } else {
386 if (i + 1 + insn->off != tgt_idx)
387 continue;
388 if (check_add_overflow(insn->off, delta, &off))
389 return -ERANGE;
390 insn->off = off;
391 }
392 }
393 return 0;
394 }
395
adjust_subprog_starts_after_remove(struct bpf_verifier_env * env,u32 off,u32 cnt)396 static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env,
397 u32 off, u32 cnt)
398 {
399 int i, j;
400
401 /* find first prog starting at or after off (first to remove) */
402 for (i = 0; i < env->subprog_cnt; i++)
403 if (env->subprog_info[i].start >= off)
404 break;
405 /* find first prog starting at or after off + cnt (first to stay) */
406 for (j = i; j < env->subprog_cnt; j++)
407 if (env->subprog_info[j].start >= off + cnt)
408 break;
409 /* if j doesn't start exactly at off + cnt, we are just removing
410 * the front of previous prog
411 */
412 if (env->subprog_info[j].start != off + cnt)
413 j--;
414
415 if (j > i) {
416 struct bpf_prog_aux *aux = env->prog->aux;
417 int move;
418
419 /* move fake 'exit' subprog as well */
420 move = env->subprog_cnt + 1 - j;
421
422 memmove(env->subprog_info + i,
423 env->subprog_info + j,
424 sizeof(*env->subprog_info) * move);
425 env->subprog_cnt -= j - i;
426
427 /* remove func_info and its aux */
428 if (aux->func_info) {
429 move = aux->func_info_cnt - j;
430
431 memmove(aux->func_info + i,
432 aux->func_info + j,
433 sizeof(*aux->func_info) * move);
434 if (aux->func_info_aux)
435 memmove(aux->func_info_aux + i,
436 aux->func_info_aux + j,
437 sizeof(*aux->func_info_aux) * move);
438 aux->func_info_cnt -= j - i;
439 /* func_info->insn_off is set after all code rewrites,
440 * in adjust_btf_func() - no need to adjust
441 */
442 }
443 } else {
444 /* convert i from "first prog to remove" to "first to adjust" */
445 if (env->subprog_info[i].start == off)
446 i++;
447 }
448
449 /* update fake 'exit' subprog as well */
450 for (; i <= env->subprog_cnt; i++)
451 env->subprog_info[i].start -= cnt;
452
453 return 0;
454 }
455
bpf_adj_linfo_after_remove(struct bpf_verifier_env * env,u32 off,u32 cnt)456 static int bpf_adj_linfo_after_remove(struct bpf_verifier_env *env, u32 off,
457 u32 cnt)
458 {
459 struct bpf_prog *prog = env->prog;
460 u32 i, l_off, l_cnt, nr_linfo;
461 struct bpf_line_info *linfo;
462
463 nr_linfo = prog->aux->nr_linfo;
464 if (!nr_linfo)
465 return 0;
466
467 linfo = prog->aux->linfo;
468
469 /* find first line info to remove, count lines to be removed */
470 for (i = 0; i < nr_linfo; i++)
471 if (linfo[i].insn_off >= off)
472 break;
473
474 l_off = i;
475 l_cnt = 0;
476 for (; i < nr_linfo; i++)
477 if (linfo[i].insn_off < off + cnt)
478 l_cnt++;
479 else
480 break;
481
482 /* First live insn doesn't match first live linfo, it needs to "inherit"
483 * last removed linfo. prog is already modified, so prog->len == off
484 * means no live instructions after (tail of the program was removed).
485 */
486 if (prog->len != off && l_cnt &&
487 (i == nr_linfo || linfo[i].insn_off != off + cnt)) {
488 l_cnt--;
489 linfo[--i].insn_off = off + cnt;
490 }
491
492 /* remove the line info which refer to the removed instructions */
493 if (l_cnt) {
494 memmove(linfo + l_off, linfo + i,
495 sizeof(*linfo) * (nr_linfo - i));
496
497 prog->aux->nr_linfo -= l_cnt;
498 nr_linfo = prog->aux->nr_linfo;
499 }
500
501 /* pull all linfo[i].insn_off >= off + cnt in by cnt */
502 for (i = l_off; i < nr_linfo; i++)
503 linfo[i].insn_off -= cnt;
504
505 /* fix up all subprogs (incl. 'exit') which start >= off */
506 for (i = 0; i <= env->subprog_cnt; i++)
507 if (env->subprog_info[i].linfo_idx > l_off) {
508 /* program may have started in the removed region but
509 * may not be fully removed
510 */
511 if (env->subprog_info[i].linfo_idx >= l_off + l_cnt)
512 env->subprog_info[i].linfo_idx -= l_cnt;
513 else
514 env->subprog_info[i].linfo_idx = l_off;
515 }
516
517 return 0;
518 }
519
520 /*
521 * Clean up dynamically allocated fields of aux data for instructions [start, ...]
522 */
bpf_clear_insn_aux_data(struct bpf_verifier_env * env,int start,int len)523 void bpf_clear_insn_aux_data(struct bpf_verifier_env *env, int start, int len)
524 {
525 struct bpf_insn_aux_data *aux_data = env->insn_aux_data;
526 int end = start + len;
527 int i;
528
529 for (i = start; i < end; i++) {
530 if (aux_data[i].jt) {
531 kvfree(aux_data[i].jt);
532 aux_data[i].jt = NULL;
533 }
534 }
535 }
536
verifier_remove_insns(struct bpf_verifier_env * env,u32 off,u32 cnt)537 static int verifier_remove_insns(struct bpf_verifier_env *env, u32 off, u32 cnt)
538 {
539 struct bpf_insn_aux_data *aux_data = env->insn_aux_data;
540 unsigned int orig_prog_len = env->prog->len;
541 int err;
542
543 if (bpf_rewrite_must_abort())
544 return -EINTR;
545
546 if (bpf_prog_is_offloaded(env->prog->aux))
547 bpf_prog_offload_remove_insns(env, off, cnt);
548
549 bpf_clear_insn_aux_data(env, off, cnt);
550
551 err = bpf_remove_insns(env->prog, off, cnt);
552 if (err)
553 return err;
554
555 err = adjust_subprog_starts_after_remove(env, off, cnt);
556 if (err)
557 return err;
558
559 err = bpf_adj_linfo_after_remove(env, off, cnt);
560 if (err)
561 return err;
562
563 adjust_insn_arrays_after_remove(env, off, cnt);
564
565 memmove(aux_data + off, aux_data + off + cnt,
566 sizeof(*aux_data) * (orig_prog_len - off - cnt));
567 env->insn_aux_data_len -= cnt;
568
569 return 0;
570 }
571
572 static const struct bpf_insn NOP = BPF_JMP_IMM(BPF_JA, 0, 0, 0);
573 static const struct bpf_insn MAY_GOTO_0 = BPF_RAW_INSN(BPF_JMP | BPF_JCOND, 0, 0, 0, 0);
574
bpf_insn_is_cond_jump(u8 code)575 bool bpf_insn_is_cond_jump(u8 code)
576 {
577 u8 op;
578
579 op = BPF_OP(code);
580 if (BPF_CLASS(code) == BPF_JMP32)
581 return op != BPF_JA;
582
583 if (BPF_CLASS(code) != BPF_JMP)
584 return false;
585
586 return op != BPF_JA && op != BPF_EXIT && op != BPF_CALL;
587 }
588
bpf_opt_hard_wire_dead_code_branches(struct bpf_verifier_env * env)589 void bpf_opt_hard_wire_dead_code_branches(struct bpf_verifier_env *env)
590 {
591 struct bpf_insn_aux_data *aux_data = env->insn_aux_data;
592 struct bpf_insn ja = BPF_JMP_IMM(BPF_JA, 0, 0, 0);
593 struct bpf_insn *insn = env->prog->insnsi;
594 const int insn_cnt = env->prog->len;
595 int i;
596
597 for (i = 0; i < insn_cnt; i++, insn++) {
598 if (!bpf_insn_is_cond_jump(insn->code))
599 continue;
600
601 if (!aux_data[i + 1].seen)
602 ja.off = insn->off;
603 else if (!aux_data[i + 1 + insn->off].seen)
604 ja.off = 0;
605 else
606 continue;
607
608 if (bpf_prog_is_offloaded(env->prog->aux))
609 bpf_prog_offload_replace_insn(env, i, &ja);
610
611 memcpy(insn, &ja, sizeof(ja));
612 }
613 }
614
bpf_opt_remove_dead_code(struct bpf_verifier_env * env)615 int bpf_opt_remove_dead_code(struct bpf_verifier_env *env)
616 {
617 struct bpf_insn_aux_data *aux_data = env->insn_aux_data;
618 int insn_cnt = env->prog->len;
619 int i, err;
620
621 for (i = 0; i < insn_cnt; i++) {
622 int j;
623
624 j = 0;
625 while (i + j < insn_cnt && !aux_data[i + j].seen)
626 j++;
627 if (!j)
628 continue;
629
630 err = verifier_remove_insns(env, i, j);
631 if (err)
632 return err;
633 insn_cnt = env->prog->len;
634 }
635
636 return 0;
637 }
638
bpf_opt_remove_nops(struct bpf_verifier_env * env)639 int bpf_opt_remove_nops(struct bpf_verifier_env *env)
640 {
641 struct bpf_insn *insn = env->prog->insnsi;
642 int insn_cnt = env->prog->len;
643 bool is_may_goto_0, is_ja;
644 int i, err;
645
646 for (i = 0; i < insn_cnt; i++) {
647 is_may_goto_0 = !memcmp(&insn[i], &MAY_GOTO_0, sizeof(MAY_GOTO_0));
648 is_ja = !memcmp(&insn[i], &NOP, sizeof(NOP));
649
650 if (!is_may_goto_0 && !is_ja)
651 continue;
652
653 err = verifier_remove_insns(env, i, 1);
654 if (err)
655 return err;
656 insn_cnt--;
657 /* Go back one insn to catch may_goto +1; may_goto +0 sequence */
658 i -= (is_may_goto_0 && i > 0) ? 2 : 1;
659 }
660
661 return 0;
662 }
663
bpf_opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env * env,const union bpf_attr * attr)664 int bpf_opt_subreg_zext_lo32_rnd_hi32(struct bpf_verifier_env *env,
665 const union bpf_attr *attr)
666 {
667 struct bpf_insn *patch;
668 /* use env->insn_buf as two independent buffers */
669 struct bpf_insn *zext_patch = env->insn_buf;
670 struct bpf_insn *rnd_hi32_patch = &env->insn_buf[2];
671 struct bpf_insn_aux_data *aux = env->insn_aux_data;
672 int i, patch_len, delta = 0, len = env->prog->len;
673 struct bpf_insn *insns = env->prog->insnsi;
674 struct bpf_prog *new_prog;
675 bool rnd_hi32;
676
677 rnd_hi32 = attr->prog_flags & BPF_F_TEST_RND_HI32;
678 zext_patch[1] = BPF_ZEXT_REG(0);
679 rnd_hi32_patch[1] = BPF_ALU64_IMM(BPF_MOV, BPF_REG_AX, 0);
680 rnd_hi32_patch[2] = BPF_ALU64_IMM(BPF_LSH, BPF_REG_AX, 32);
681 rnd_hi32_patch[3] = BPF_ALU64_REG(BPF_OR, 0, BPF_REG_AX);
682 for (i = 0; i < len; i++) {
683 int adj_idx = i + delta;
684 struct bpf_insn insn;
685 int load_reg;
686
687 insn = insns[adj_idx];
688 load_reg = insn_def_regno(&insn);
689 if (!aux[adj_idx].zext_dst) {
690 u8 code, class;
691 u32 imm_rnd;
692
693 if (!rnd_hi32)
694 continue;
695
696 code = insn.code;
697 class = BPF_CLASS(code);
698 if (load_reg == -1)
699 continue;
700
701 if (bpf_is_reg64(env->prog, &insn)) {
702 if (class == BPF_LD &&
703 BPF_MODE(code) == BPF_IMM)
704 i++;
705 continue;
706 }
707
708 /* ctx load could be transformed into wider load. */
709 if (class == BPF_LDX &&
710 aux[adj_idx].ptr_type == PTR_TO_CTX)
711 continue;
712
713 imm_rnd = get_random_u32();
714 rnd_hi32_patch[0] = insn;
715 rnd_hi32_patch[1].imm = imm_rnd;
716 rnd_hi32_patch[3].dst_reg = load_reg;
717 patch = rnd_hi32_patch;
718 patch_len = 4;
719 goto apply_patch_buffer;
720 }
721
722 /* Add in an zero-extend instruction if a) the JIT has requested
723 * it or b) it's a CMPXCHG.
724 *
725 * The latter is because: BPF_CMPXCHG always loads a value into
726 * R0, therefore always zero-extends. However some archs'
727 * equivalent instruction only does this load when the
728 * comparison is successful. This detail of CMPXCHG is
729 * orthogonal to the general zero-extension behaviour of the
730 * CPU, so it's treated independently of bpf_jit_needs_zext.
731 */
732 if (!bpf_jit_needs_zext() && !is_cmpxchg_insn(&insn))
733 continue;
734
735 /* Zero-extension is done by the caller. */
736 if (bpf_pseudo_kfunc_call(&insn))
737 continue;
738
739 if (verifier_bug_if(load_reg == -1, env,
740 "zext_dst is set, but no reg is defined"))
741 return -EFAULT;
742
743 zext_patch[0] = insn;
744 zext_patch[1].dst_reg = load_reg;
745 zext_patch[1].src_reg = load_reg;
746 patch = zext_patch;
747 patch_len = 2;
748 apply_patch_buffer:
749 new_prog = bpf_patch_insn_data(env, adj_idx, patch, patch_len);
750 if (!new_prog)
751 return -ENOMEM;
752 env->prog = new_prog;
753 insns = new_prog->insnsi;
754 aux = env->insn_aux_data;
755 delta += patch_len - 1;
756 }
757
758 return 0;
759 }
760
761 /* convert load instructions that access fields of a context type into a
762 * sequence of instructions that access fields of the underlying structure:
763 * struct __sk_buff -> struct sk_buff
764 * struct bpf_sock_ops -> struct sock
765 */
bpf_convert_ctx_accesses(struct bpf_verifier_env * env)766 int bpf_convert_ctx_accesses(struct bpf_verifier_env *env)
767 {
768 struct bpf_subprog_info *subprogs = env->subprog_info;
769 const struct bpf_verifier_ops *ops = env->ops;
770 int i, cnt, size, ctx_field_size, ret, delta = 0, epilogue_cnt = 0;
771 const int insn_cnt = env->prog->len;
772 struct bpf_insn *epilogue_buf = env->epilogue_buf;
773 struct bpf_insn *insn_buf = env->insn_buf;
774 struct bpf_insn *insn;
775 u32 target_size, size_default, off;
776 struct bpf_prog *new_prog;
777 enum bpf_access_type type;
778 bool is_narrower_load;
779 int epilogue_idx = 0;
780
781 if (ops->gen_epilogue) {
782 epilogue_cnt = ops->gen_epilogue(epilogue_buf, env->prog,
783 -(subprogs[0].stack_depth + 8));
784 if (epilogue_cnt >= INSN_BUF_SIZE) {
785 verifier_bug(env, "epilogue is too long");
786 return -EFAULT;
787 } else if (epilogue_cnt) {
788 /* Save the ARG_PTR_TO_CTX for the epilogue to use */
789 cnt = 0;
790 subprogs[0].stack_depth += 8;
791 insn_buf[cnt++] = BPF_STX_MEM(BPF_DW, BPF_REG_FP, BPF_REG_1,
792 -subprogs[0].stack_depth);
793 insn_buf[cnt++] = env->prog->insnsi[0];
794 new_prog = bpf_patch_insn_data(env, 0, insn_buf, cnt);
795 if (!new_prog)
796 return -ENOMEM;
797 env->prog = new_prog;
798 delta += cnt - 1;
799
800 ret = add_kfunc_in_insns(env, epilogue_buf, epilogue_cnt - 1);
801 if (ret < 0)
802 return ret;
803 }
804 }
805
806 if (ops->gen_prologue || env->seen_direct_write) {
807 if (!ops->gen_prologue) {
808 verifier_bug(env, "gen_prologue is null");
809 return -EFAULT;
810 }
811 cnt = ops->gen_prologue(insn_buf, env->seen_direct_write,
812 env->prog);
813 if (cnt >= INSN_BUF_SIZE) {
814 verifier_bug(env, "prologue is too long");
815 return -EFAULT;
816 } else if (cnt) {
817 new_prog = bpf_patch_insn_data(env, 0, insn_buf, cnt);
818 if (!new_prog)
819 return -ENOMEM;
820
821 env->prog = new_prog;
822 delta += cnt - 1;
823
824 ret = add_kfunc_in_insns(env, insn_buf, cnt - 1);
825 if (ret < 0)
826 return ret;
827 }
828 }
829
830 if (delta)
831 WARN_ON(adjust_jmp_off(env->prog, 0, delta));
832
833 if (bpf_prog_is_offloaded(env->prog->aux))
834 return 0;
835
836 insn = env->prog->insnsi + delta;
837
838 for (i = 0; i < insn_cnt; i++, insn++) {
839 bpf_convert_ctx_access_t convert_ctx_access;
840 enum bpf_reg_type ptr_type;
841 u8 mode;
842
843 if (env->insn_aux_data[i + delta].nospec) {
844 WARN_ON_ONCE(env->insn_aux_data[i + delta].alu_state);
845 struct bpf_insn *patch = insn_buf;
846
847 *patch++ = BPF_ST_NOSPEC();
848 *patch++ = *insn;
849 cnt = patch - insn_buf;
850 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
851 if (!new_prog)
852 return -ENOMEM;
853
854 delta += cnt - 1;
855 env->prog = new_prog;
856 insn = new_prog->insnsi + i + delta;
857 /* This can not be easily merged with the
858 * nospec_result-case, because an insn may require a
859 * nospec before and after itself. Therefore also do not
860 * 'continue' here but potentially apply further
861 * patching to insn. *insn should equal patch[1] now.
862 */
863 }
864
865 if (insn->code == (BPF_LDX | BPF_MEM | BPF_B) ||
866 insn->code == (BPF_LDX | BPF_MEM | BPF_H) ||
867 insn->code == (BPF_LDX | BPF_MEM | BPF_W) ||
868 insn->code == (BPF_LDX | BPF_MEM | BPF_DW) ||
869 insn->code == (BPF_LDX | BPF_MEMSX | BPF_B) ||
870 insn->code == (BPF_LDX | BPF_MEMSX | BPF_H) ||
871 insn->code == (BPF_LDX | BPF_MEMSX | BPF_W)) {
872 type = BPF_READ;
873 } else if (insn->code == (BPF_STX | BPF_MEM | BPF_B) ||
874 insn->code == (BPF_STX | BPF_MEM | BPF_H) ||
875 insn->code == (BPF_STX | BPF_MEM | BPF_W) ||
876 insn->code == (BPF_STX | BPF_MEM | BPF_DW) ||
877 insn->code == (BPF_ST | BPF_MEM | BPF_B) ||
878 insn->code == (BPF_ST | BPF_MEM | BPF_H) ||
879 insn->code == (BPF_ST | BPF_MEM | BPF_W) ||
880 insn->code == (BPF_ST | BPF_MEM | BPF_DW)) {
881 type = BPF_WRITE;
882 } else if ((insn->code == (BPF_STX | BPF_ATOMIC | BPF_B) ||
883 insn->code == (BPF_STX | BPF_ATOMIC | BPF_H) ||
884 insn->code == (BPF_STX | BPF_ATOMIC | BPF_W) ||
885 insn->code == (BPF_STX | BPF_ATOMIC | BPF_DW)) &&
886 env->insn_aux_data[i + delta].ptr_type == PTR_TO_ARENA) {
887 insn->code = BPF_STX | BPF_PROBE_ATOMIC | BPF_SIZE(insn->code);
888 env->prog->aux->num_exentries++;
889 continue;
890 } else if (insn->code == (BPF_JMP | BPF_EXIT) &&
891 epilogue_cnt &&
892 i + delta < subprogs[1].start) {
893 /* Generate epilogue for the main prog */
894 if (epilogue_idx) {
895 /* jump back to the earlier generated epilogue */
896 insn_buf[0] = BPF_JMP32_A(epilogue_idx - i - delta - 1);
897 cnt = 1;
898 } else {
899 memcpy(insn_buf, epilogue_buf,
900 epilogue_cnt * sizeof(*epilogue_buf));
901 cnt = epilogue_cnt;
902 /* epilogue_idx cannot be 0. It must have at
903 * least one ctx ptr saving insn before the
904 * epilogue.
905 */
906 epilogue_idx = i + delta;
907 }
908 goto patch_insn_buf;
909 } else {
910 continue;
911 }
912
913 if (type == BPF_WRITE &&
914 env->insn_aux_data[i + delta].nospec_result) {
915 /* nospec_result is only used to mitigate Spectre v4 and
916 * to limit verification-time for Spectre v1.
917 */
918 struct bpf_insn *patch = insn_buf;
919
920 *patch++ = *insn;
921 *patch++ = BPF_ST_NOSPEC();
922 cnt = patch - insn_buf;
923 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
924 if (!new_prog)
925 return -ENOMEM;
926
927 delta += cnt - 1;
928 env->prog = new_prog;
929 insn = new_prog->insnsi + i + delta;
930 continue;
931 }
932
933 ptr_type = env->insn_aux_data[i + delta].ptr_type;
934 switch ((int)ptr_type) {
935 case PTR_TO_CTX:
936 if (!ops->convert_ctx_access)
937 continue;
938 convert_ctx_access = ops->convert_ctx_access;
939 break;
940 case PTR_TO_SOCKET:
941 case PTR_TO_SOCK_COMMON:
942 convert_ctx_access = bpf_sock_convert_ctx_access;
943 break;
944 case PTR_TO_TCP_SOCK:
945 convert_ctx_access = bpf_tcp_sock_convert_ctx_access;
946 break;
947 case PTR_TO_XDP_SOCK:
948 convert_ctx_access = bpf_xdp_sock_convert_ctx_access;
949 break;
950 case PTR_TO_ARENA:
951 if (BPF_MODE(insn->code) == BPF_MEMSX) {
952 if (!bpf_jit_supports_insn(insn, true)) {
953 verbose(env, "sign extending loads from arena are not supported yet\n");
954 return -EOPNOTSUPP;
955 }
956 insn->code = BPF_CLASS(insn->code) | BPF_PROBE_MEM32SX | BPF_SIZE(insn->code);
957 } else {
958 insn->code = BPF_CLASS(insn->code) | BPF_PROBE_MEM32 | BPF_SIZE(insn->code);
959 }
960 env->prog->aux->num_exentries++;
961 continue;
962 default:
963 /*
964 * A pointer which may fault on a dereference must not
965 * be loaded from without fault protection, hence turn
966 * the BPF_LDX into a BPF_PROBE_MEM one so that a bad
967 * address is handled rather than panicking the kernel.
968 * A store through one is rejected earlier, there is no
969 * probed counterpart to rewrite it into.
970 */
971 if (bpf_is_ptr_to_mem_or_btf_id(ptr_type) &&
972 bpf_may_fault_on_deref(ptr_type) &&
973 type == BPF_READ) {
974 if (BPF_MODE(insn->code) == BPF_MEM)
975 insn->code = BPF_LDX | BPF_PROBE_MEM |
976 BPF_SIZE(insn->code);
977 else
978 insn->code = BPF_LDX | BPF_PROBE_MEMSX |
979 BPF_SIZE(insn->code);
980 env->prog->aux->num_exentries++;
981 continue;
982 }
983 if (verifier_bug_if(bpf_may_fault_on_deref(ptr_type), env,
984 "access to a fault prone pointer is not rewritten as a probed one"))
985 return -EFAULT;
986 continue;
987 }
988
989 ctx_field_size = env->insn_aux_data[i + delta].ctx_field_size;
990 size = BPF_LDST_BYTES(insn);
991 mode = BPF_MODE(insn->code);
992
993 /* If the read access is a narrower load of the field,
994 * convert to a 4/8-byte load, to minimum program type specific
995 * convert_ctx_access changes. If conversion is successful,
996 * we will apply proper mask to the result.
997 */
998 is_narrower_load = size < ctx_field_size;
999 size_default = bpf_ctx_off_adjust_machine(ctx_field_size);
1000 off = insn->off;
1001 if (is_narrower_load) {
1002 u8 size_code;
1003
1004 if (type == BPF_WRITE) {
1005 verifier_bug(env, "narrow ctx access misconfigured");
1006 return -EFAULT;
1007 }
1008
1009 size_code = BPF_H;
1010 if (ctx_field_size == 4)
1011 size_code = BPF_W;
1012 else if (ctx_field_size == 8)
1013 size_code = BPF_DW;
1014
1015 insn->off = off & ~(size_default - 1);
1016 insn->code = BPF_LDX | BPF_MEM | size_code;
1017 }
1018
1019 target_size = 0;
1020 cnt = convert_ctx_access(type, insn, insn_buf, env->prog,
1021 &target_size);
1022 if (cnt == 0 || cnt >= INSN_BUF_SIZE ||
1023 (ctx_field_size && !target_size)) {
1024 verifier_bug(env, "error during ctx access conversion (%d)", cnt);
1025 return -EFAULT;
1026 }
1027
1028 if (is_narrower_load && size < target_size) {
1029 u8 shift = bpf_ctx_narrow_access_offset(
1030 off, size, size_default) * 8;
1031 if (shift && cnt + 1 >= INSN_BUF_SIZE) {
1032 verifier_bug(env, "narrow ctx load misconfigured");
1033 return -EFAULT;
1034 }
1035 if (ctx_field_size <= 4) {
1036 if (shift)
1037 insn_buf[cnt++] = BPF_ALU32_IMM(BPF_RSH,
1038 insn->dst_reg,
1039 shift);
1040 insn_buf[cnt++] = BPF_ALU32_IMM(BPF_AND, insn->dst_reg,
1041 (1 << size * 8) - 1);
1042 } else {
1043 if (shift)
1044 insn_buf[cnt++] = BPF_ALU64_IMM(BPF_RSH,
1045 insn->dst_reg,
1046 shift);
1047 insn_buf[cnt++] = BPF_ALU32_IMM(BPF_AND, insn->dst_reg,
1048 (1ULL << size * 8) - 1);
1049 }
1050 }
1051 if (mode == BPF_MEMSX)
1052 insn_buf[cnt++] = BPF_RAW_INSN(BPF_ALU64 | BPF_MOV | BPF_X,
1053 insn->dst_reg, insn->dst_reg,
1054 size * 8, 0);
1055
1056 patch_insn_buf:
1057 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
1058 if (!new_prog)
1059 return -ENOMEM;
1060
1061 delta += cnt - 1;
1062
1063 /* keep walking new program and skip insns we just inserted */
1064 env->prog = new_prog;
1065 insn = new_prog->insnsi + i + delta;
1066 }
1067
1068 return 0;
1069 }
1070
bpf_dup_subprog_starts(struct bpf_verifier_env * env)1071 static u32 *bpf_dup_subprog_starts(struct bpf_verifier_env *env)
1072 {
1073 u32 *starts = NULL;
1074
1075 starts = kvmalloc_objs(u32, env->subprog_cnt, GFP_KERNEL_ACCOUNT);
1076 if (starts) {
1077 for (int i = 0; i < env->subprog_cnt; i++)
1078 starts[i] = env->subprog_info[i].start;
1079 }
1080 return starts;
1081 }
1082
bpf_restore_subprog_starts(struct bpf_verifier_env * env,u32 * orig_starts)1083 static void bpf_restore_subprog_starts(struct bpf_verifier_env *env, u32 *orig_starts)
1084 {
1085 for (int i = 0; i < env->subprog_cnt; i++)
1086 env->subprog_info[i].start = orig_starts[i];
1087 /* restore the start of fake 'exit' subprog as well */
1088 env->subprog_info[env->subprog_cnt].start = env->prog->len;
1089 }
1090
jit_subprogs(struct bpf_verifier_env * env)1091 static int jit_subprogs(struct bpf_verifier_env *env)
1092 {
1093 struct bpf_prog *prog = env->prog, **func, *tmp;
1094 int i, j, subprog_start, subprog_end = 0, len, subprog;
1095 struct bpf_map *map_ptr;
1096 struct bpf_insn *insn;
1097 void *old_bpf_func;
1098 int err, num_exentries;
1099
1100 for (i = 0, insn = prog->insnsi; i < prog->len; i++, insn++) {
1101 if (!bpf_pseudo_func(insn) && !bpf_pseudo_call(insn))
1102 continue;
1103
1104 /* Upon error here we cannot fall back to interpreter but
1105 * need a hard reject of the program. Thus -EFAULT is
1106 * propagated in any case.
1107 */
1108 subprog = bpf_find_subprog(env, i + insn->imm + 1);
1109 if (verifier_bug_if(subprog < 0, env, "No program to jit at insn %d",
1110 i + insn->imm + 1))
1111 return -EFAULT;
1112 /* temporarily remember subprog id inside insn instead of
1113 * aux_data, since next loop will split up all insns into funcs
1114 */
1115 insn->off = subprog;
1116 /* remember original imm in case JIT fails and fallback
1117 * to interpreter will be needed
1118 */
1119 env->insn_aux_data[i].call_imm = insn->imm;
1120 /* point imm to __bpf_call_base+1 from JITs point of view */
1121 insn->imm = 1;
1122 if (bpf_pseudo_func(insn)) {
1123 #if defined(MODULES_VADDR)
1124 u64 addr = MODULES_VADDR;
1125 #else
1126 u64 addr = VMALLOC_START;
1127 #endif
1128 /* jit (e.g. x86_64) may emit fewer instructions
1129 * if it learns a u32 imm is the same as a u64 imm.
1130 * Set close enough to possible prog address.
1131 */
1132 insn[0].imm = (u32)addr;
1133 insn[1].imm = addr >> 32;
1134 }
1135 }
1136
1137 err = bpf_prog_alloc_jited_linfo(prog);
1138 if (err)
1139 goto out_undo_insn;
1140
1141 err = -ENOMEM;
1142 func = kzalloc_objs(prog, env->subprog_cnt);
1143 if (!func)
1144 goto out_undo_insn;
1145
1146 for (i = 0; i < env->subprog_cnt; i++) {
1147 subprog_start = subprog_end;
1148 subprog_end = env->subprog_info[i + 1].start;
1149
1150 len = subprog_end - subprog_start;
1151 /* bpf_prog_run() doesn't call subprogs directly,
1152 * hence main prog stats include the runtime of subprogs.
1153 * subprogs don't have IDs and not reachable via prog_get_next_id
1154 * func[i]->stats will never be accessed and stays NULL
1155 */
1156 func[i] = bpf_prog_alloc_no_stats(bpf_prog_size(len), GFP_USER);
1157 if (!func[i])
1158 goto out_free;
1159 memcpy(func[i]->insnsi, &prog->insnsi[subprog_start],
1160 len * sizeof(struct bpf_insn));
1161 func[i]->type = prog->type;
1162 func[i]->len = len;
1163 if (bpf_prog_calc_tag(func[i]))
1164 goto out_free;
1165 func[i]->is_func = 1;
1166 func[i]->sleepable = prog->sleepable;
1167 func[i]->blinded = prog->blinded;
1168 func[i]->aux->func_idx = i;
1169 /* Below members will be freed only at prog->aux */
1170 func[i]->aux->btf = prog->aux->btf;
1171 func[i]->aux->subprog_start = subprog_start;
1172 func[i]->aux->func_info = prog->aux->func_info;
1173 func[i]->aux->func_info_cnt = prog->aux->func_info_cnt;
1174 func[i]->aux->poke_tab = prog->aux->poke_tab;
1175 func[i]->aux->size_poke_tab = prog->aux->size_poke_tab;
1176 func[i]->aux->main_prog_aux = prog->aux;
1177
1178 for (j = 0; j < prog->aux->size_poke_tab; j++) {
1179 struct bpf_jit_poke_descriptor *poke;
1180
1181 poke = &prog->aux->poke_tab[j];
1182 if (poke->insn_idx < subprog_end &&
1183 poke->insn_idx >= subprog_start)
1184 poke->aux = func[i]->aux;
1185 }
1186
1187 func[i]->aux->name[0] = 'F';
1188 func[i]->aux->stack_depth = env->subprog_info[i].stack_depth;
1189 if (env->subprog_info[i].priv_stack_mode == PRIV_STACK_ADAPTIVE)
1190 func[i]->aux->jits_use_priv_stack = true;
1191
1192 func[i]->jit_requested = 1;
1193 func[i]->blinding_requested = prog->blinding_requested;
1194 func[i]->aux->kfunc_tab = prog->aux->kfunc_tab;
1195 func[i]->aux->kfunc_btf_tab = prog->aux->kfunc_btf_tab;
1196 func[i]->aux->linfo = prog->aux->linfo;
1197 func[i]->aux->nr_linfo = prog->aux->nr_linfo;
1198 func[i]->aux->jited_linfo = prog->aux->jited_linfo;
1199 func[i]->aux->linfo_idx = env->subprog_info[i].linfo_idx;
1200 func[i]->aux->arena = prog->aux->arena;
1201 func[i]->aux->used_maps = env->used_maps;
1202 func[i]->aux->used_map_cnt = env->used_map_cnt;
1203 num_exentries = 0;
1204 insn = func[i]->insnsi;
1205 for (j = 0; j < func[i]->len; j++, insn++) {
1206 if (BPF_CLASS(insn->code) == BPF_LDX &&
1207 (BPF_MODE(insn->code) == BPF_PROBE_MEM ||
1208 BPF_MODE(insn->code) == BPF_PROBE_MEM32 ||
1209 BPF_MODE(insn->code) == BPF_PROBE_MEM32SX ||
1210 BPF_MODE(insn->code) == BPF_PROBE_MEMSX))
1211 num_exentries++;
1212 if ((BPF_CLASS(insn->code) == BPF_STX ||
1213 BPF_CLASS(insn->code) == BPF_ST) &&
1214 BPF_MODE(insn->code) == BPF_PROBE_MEM32)
1215 num_exentries++;
1216 if (BPF_CLASS(insn->code) == BPF_STX &&
1217 BPF_MODE(insn->code) == BPF_PROBE_ATOMIC)
1218 num_exentries++;
1219 }
1220 func[i]->aux->num_exentries = num_exentries;
1221 func[i]->aux->tail_call_reachable = env->subprog_info[i].tail_call_reachable;
1222 func[i]->aux->exception_cb = env->subprog_info[i].is_exception_cb;
1223 func[i]->aux->changes_pkt_data = env->subprog_info[i].changes_pkt_data;
1224 func[i]->aux->might_sleep = env->subprog_info[i].might_sleep;
1225 func[i]->aux->token = prog->aux->token;
1226 if (!i)
1227 func[i]->aux->exception_boundary = env->seen_exception;
1228 func[i] = bpf_int_jit_compile(env, func[i]);
1229 if (!func[i]->jited) {
1230 err = -ENOTSUPP;
1231 goto out_free;
1232 }
1233 cond_resched();
1234 }
1235
1236 /* at this point all bpf functions were successfully JITed
1237 * now populate all bpf_calls with correct addresses and
1238 * run last pass of JIT
1239 */
1240 for (i = 0; i < env->subprog_cnt; i++) {
1241 insn = func[i]->insnsi;
1242 for (j = 0; j < func[i]->len; j++, insn++) {
1243 if (bpf_pseudo_func(insn)) {
1244 subprog = insn->off;
1245 insn[0].imm = (u32)(long)func[subprog]->bpf_func;
1246 insn[1].imm = ((u64)(long)func[subprog]->bpf_func) >> 32;
1247 continue;
1248 }
1249 if (!bpf_pseudo_call(insn))
1250 continue;
1251 subprog = insn->off;
1252 insn->imm = BPF_CALL_IMM(func[subprog]->bpf_func);
1253 }
1254
1255 /* we use the aux data to keep a list of the start addresses
1256 * of the JITed images for each function in the program
1257 *
1258 * for some architectures, such as powerpc64, the imm field
1259 * might not be large enough to hold the offset of the start
1260 * address of the callee's JITed image from __bpf_call_base
1261 *
1262 * in such cases, we can lookup the start address of a callee
1263 * by using its subprog id, available from the off field of
1264 * the call instruction, as an index for this list
1265 */
1266 func[i]->aux->func = func;
1267 func[i]->aux->func_cnt = env->subprog_cnt - env->hidden_subprog_cnt;
1268 func[i]->aux->real_func_cnt = env->subprog_cnt;
1269 }
1270 for (i = 0; i < env->subprog_cnt; i++) {
1271 old_bpf_func = func[i]->bpf_func;
1272 tmp = bpf_int_jit_compile(env, func[i]);
1273 if (tmp != func[i] || func[i]->bpf_func != old_bpf_func) {
1274 verbose(env, "JIT doesn't support bpf-to-bpf calls\n");
1275 err = -ENOTSUPP;
1276 goto out_free;
1277 }
1278 cond_resched();
1279 }
1280
1281 /*
1282 * Cleanup func[i]->aux fields which aren't required
1283 * or can become invalid in future
1284 */
1285 for (i = 0; i < env->subprog_cnt; i++) {
1286 func[i]->aux->used_maps = NULL;
1287 func[i]->aux->used_map_cnt = 0;
1288 }
1289
1290 /* finally lock prog and jit images for all functions and
1291 * populate kallsysm. Begin at the first subprogram, since
1292 * bpf_prog_load will add the kallsyms for the main program.
1293 */
1294 for (i = 1; i < env->subprog_cnt; i++) {
1295 err = bpf_prog_lock_ro(func[i]);
1296 if (err)
1297 goto out_free;
1298 }
1299
1300 for (i = 1; i < env->subprog_cnt; i++)
1301 bpf_prog_kallsyms_add(func[i]);
1302
1303 /* Last step: make now unused interpreter insns from main
1304 * prog consistent for later dump requests, so they can
1305 * later look the same as if they were interpreted only.
1306 */
1307 for (i = 0, insn = prog->insnsi; i < prog->len; i++, insn++) {
1308 if (bpf_pseudo_func(insn)) {
1309 insn[0].imm = env->insn_aux_data[i].call_imm;
1310 insn[1].imm = insn->off;
1311 insn->off = 0;
1312 continue;
1313 }
1314 if (!bpf_pseudo_call(insn))
1315 continue;
1316 insn->imm = env->insn_aux_data[i].call_imm;
1317 subprog = bpf_find_subprog(env, i + insn->imm + 1);
1318 insn->off = subprog;
1319 }
1320
1321 prog->jited = 1;
1322 prog->bpf_func = func[0]->bpf_func;
1323 prog->jited_len = func[0]->jited_len;
1324 prog->aux->extable = func[0]->aux->extable;
1325 prog->aux->num_exentries = func[0]->aux->num_exentries;
1326 prog->aux->func = func;
1327 prog->aux->func_cnt = env->subprog_cnt - env->hidden_subprog_cnt;
1328 prog->aux->real_func_cnt = env->subprog_cnt;
1329 prog->aux->bpf_exception_cb = (void *)func[env->exception_callback_subprog]->bpf_func;
1330 prog->aux->exception_boundary = func[0]->aux->exception_boundary;
1331 prog->aux->stack_arg_sp_adjust = func[0]->aux->stack_arg_sp_adjust;
1332 bpf_prog_jit_attempt_done(prog);
1333 return 0;
1334 out_free:
1335 /* We failed JIT'ing, so at this point we need to unregister poke
1336 * descriptors from subprogs, so that kernel is not attempting to
1337 * patch it anymore as we're freeing the subprog JIT memory.
1338 */
1339 for (i = 0; i < prog->aux->size_poke_tab; i++) {
1340 map_ptr = prog->aux->poke_tab[i].tail_call.map;
1341 map_ptr->ops->map_poke_untrack(map_ptr, prog->aux);
1342 }
1343 /* At this point we're guaranteed that poke descriptors are not
1344 * live anymore. We can just unlink its descriptor table as it's
1345 * released with the main prog.
1346 */
1347 for (i = 0; i < env->subprog_cnt; i++) {
1348 if (!func[i])
1349 continue;
1350 func[i]->aux->poke_tab = NULL;
1351 bpf_jit_free(func[i]);
1352 }
1353 kfree(func);
1354 out_undo_insn:
1355 bpf_prog_jit_attempt_done(prog);
1356 return err;
1357 }
1358
bpf_jit_subprogs(struct bpf_verifier_env * env)1359 int bpf_jit_subprogs(struct bpf_verifier_env *env)
1360 {
1361 int err, i;
1362 bool blinded = false;
1363 struct bpf_insn *insn;
1364 struct bpf_prog *prog, *orig_prog;
1365 u32 *orig_subprog_starts;
1366
1367 if (env->subprog_cnt <= 1)
1368 return 0;
1369
1370 prog = orig_prog = env->prog;
1371 if (bpf_prog_need_blind(prog)) {
1372 orig_subprog_starts = bpf_dup_subprog_starts(env);
1373 if (!orig_subprog_starts) {
1374 err = -ENOMEM;
1375 goto out_cleanup;
1376 }
1377 prog = bpf_jit_blind_constants(env, prog);
1378 if (IS_ERR(prog)) {
1379 err = PTR_ERR(prog);
1380 prog = orig_prog;
1381 goto out_restore;
1382 }
1383 blinded = true;
1384 }
1385
1386 err = jit_subprogs(env);
1387 if (err)
1388 goto out_jit_err;
1389
1390 if (blinded) {
1391 bpf_jit_prog_release_other(prog, orig_prog);
1392 kvfree(orig_subprog_starts);
1393 }
1394
1395 return 0;
1396
1397 out_jit_err:
1398 if (blinded) {
1399 bpf_jit_prog_release_other(orig_prog, prog);
1400 /* roll back to the clean original prog */
1401 prog = env->prog = orig_prog;
1402 goto out_restore;
1403 } else {
1404 if (err != -EFAULT) {
1405 /*
1406 * We will fall back to interpreter mode when err is not -EFAULT, before
1407 * that, insn->off and insn->imm should be restored to their original
1408 * values since they were modified by jit_subprogs.
1409 */
1410 for (i = 0, insn = prog->insnsi; i < prog->len; i++, insn++) {
1411 if (!bpf_pseudo_call(insn))
1412 continue;
1413 insn->off = 0;
1414 insn->imm = env->insn_aux_data[i].call_imm;
1415 }
1416 }
1417 goto out_cleanup;
1418 }
1419
1420 out_restore:
1421 bpf_restore_subprog_starts(env, orig_subprog_starts);
1422 kvfree(orig_subprog_starts);
1423 out_cleanup:
1424 /* cleanup main prog to be interpreted */
1425 prog->jit_requested = 0;
1426 prog->blinding_requested = 0;
1427 return err;
1428 }
1429
bpf_fixup_call_args(struct bpf_verifier_env * env)1430 int bpf_fixup_call_args(struct bpf_verifier_env *env)
1431 {
1432 #ifndef CONFIG_BPF_JIT_ALWAYS_ON
1433 struct bpf_prog *prog = env->prog;
1434 struct bpf_insn *insn = prog->insnsi;
1435 int depth;
1436 #endif
1437 int i, err = 0;
1438
1439 for (i = 0; i < env->subprog_cnt; i++) {
1440 struct bpf_subprog_info *subprog = &env->subprog_info[i];
1441 u16 outgoing = subprog->stack_arg_cnt - bpf_in_stack_arg_cnt(subprog);
1442
1443 if (subprog->max_out_stack_arg_cnt > outgoing) {
1444 verbose(env,
1445 "func#%d writes %u stack arg slots, but calls only require %u\n",
1446 i, subprog->max_out_stack_arg_cnt, outgoing);
1447 return -EINVAL;
1448 }
1449 }
1450
1451 if (env->prog->jit_requested &&
1452 !bpf_prog_is_offloaded(env->prog->aux)) {
1453 err = bpf_jit_subprogs(env);
1454 if (err == 0)
1455 return 0;
1456 if (err == -EFAULT || err == -EINTR)
1457 return err;
1458 }
1459 #ifndef CONFIG_BPF_JIT_ALWAYS_ON
1460 if (prog->jit_required) {
1461 verbose(env, "program requires BPF JIT compiler but it is not available\n");
1462 return -EINVAL;
1463 }
1464 for (i = 0; i < env->subprog_cnt; i++) {
1465 if (bpf_in_stack_arg_cnt(&env->subprog_info[i])) {
1466 verbose(env, "stack args are not supported in non-JITed programs\n");
1467 return -EINVAL;
1468 }
1469 }
1470 if (env->subprog_cnt > 1 && env->prog->aux->tail_call_reachable) {
1471 /* When JIT fails the progs with bpf2bpf calls and tail_calls
1472 * have to be rejected, since interpreter doesn't support them yet.
1473 */
1474 verbose(env, "tail_calls are not allowed in non-JITed programs with bpf-to-bpf calls\n");
1475 return -EINVAL;
1476 }
1477 for (i = 0; i < prog->len; i++, insn++) {
1478 if (bpf_pseudo_func(insn)) {
1479 /* When JIT fails the progs with callback calls
1480 * have to be rejected, since interpreter doesn't support them yet.
1481 */
1482 verbose(env, "callbacks are not allowed in non-JITed programs\n");
1483 return -EINVAL;
1484 }
1485
1486 if (!bpf_pseudo_call(insn))
1487 continue;
1488 depth = get_callee_stack_depth(env, insn, i);
1489 if (depth < 0)
1490 return depth;
1491 err = bpf_patch_call_args(insn, depth);
1492 if (err) {
1493 verbose(env, "stack depth %d exceeds interpreter stack depth limit\n",
1494 depth);
1495 return err;
1496 }
1497 }
1498 err = 0;
1499 #endif
1500 return err;
1501 }
1502
1503 /* The function requires that first instruction in 'patch' is insnsi[prog->len - 1] */
add_hidden_subprog(struct bpf_verifier_env * env,struct bpf_insn * patch,int len)1504 static int add_hidden_subprog(struct bpf_verifier_env *env, struct bpf_insn *patch, int len)
1505 {
1506 struct bpf_subprog_info *info = env->subprog_info;
1507 int cnt = env->subprog_cnt;
1508 struct bpf_prog *prog;
1509
1510 /* We only reserve one slot for hidden subprogs in subprog_info. */
1511 if (env->hidden_subprog_cnt) {
1512 verifier_bug(env, "only one hidden subprog supported");
1513 return -EFAULT;
1514 }
1515 /* We're not patching any existing instruction, just appending the new
1516 * ones for the hidden subprog. Hence all of the adjustment operations
1517 * in bpf_patch_insn_data are no-ops.
1518 */
1519 prog = bpf_patch_insn_data(env, env->prog->len - 1, patch, len);
1520 if (!prog)
1521 return -ENOMEM;
1522 env->prog = prog;
1523 info[cnt + 1].start = info[cnt].start;
1524 info[cnt].start = prog->len - len + 1;
1525 env->subprog_cnt++;
1526 env->hidden_subprog_cnt++;
1527 return 0;
1528 }
1529
1530 /* Do various post-verification rewrites in a single program pass.
1531 * These rewrites simplify JIT and interpreter implementations.
1532 */
bpf_do_misc_fixups(struct bpf_verifier_env * env)1533 int bpf_do_misc_fixups(struct bpf_verifier_env *env)
1534 {
1535 struct bpf_prog *prog = env->prog;
1536 enum bpf_attach_type eatype = prog->expected_attach_type;
1537 enum bpf_prog_type prog_type = resolve_prog_type(prog);
1538 struct bpf_insn *insn = prog->insnsi;
1539 const struct bpf_func_proto *fn;
1540 const int insn_cnt = prog->len;
1541 const struct bpf_map_ops *ops;
1542 struct bpf_insn_aux_data *aux;
1543 struct bpf_insn *insn_buf = env->insn_buf;
1544 struct bpf_prog *new_prog;
1545 struct bpf_map *map_ptr;
1546 int i, ret, cnt, delta = 0, cur_subprog = 0;
1547 struct bpf_subprog_info *subprogs = env->subprog_info;
1548 u16 stack_depth = subprogs[cur_subprog].stack_depth;
1549 u16 stack_depth_extra = 0;
1550
1551 if (env->seen_exception && !env->exception_callback_subprog) {
1552 struct bpf_insn *patch = insn_buf;
1553
1554 *patch++ = env->prog->insnsi[insn_cnt - 1];
1555 *patch++ = BPF_MOV64_REG(BPF_REG_0, BPF_REG_1);
1556 *patch++ = BPF_EXIT_INSN();
1557 ret = add_hidden_subprog(env, insn_buf, patch - insn_buf);
1558 if (ret < 0)
1559 return ret;
1560 prog = env->prog;
1561 insn = prog->insnsi;
1562
1563 env->exception_callback_subprog = env->subprog_cnt - 1;
1564 /* Don't update insn_cnt, as add_hidden_subprog always appends insns */
1565 bpf_mark_subprog_exc_cb(env, env->exception_callback_subprog);
1566 }
1567
1568 for (i = 0; i < insn_cnt;) {
1569 if (is_addr_space_cast32(env->prog, insn)) {
1570 /* convert to 32-bit mov that clears upper 32-bit */
1571 insn->code = BPF_ALU | BPF_MOV | BPF_X;
1572 /* clear off and imm, so it's a normal 'wX = wY' from JIT pov */
1573 insn->off = 0;
1574 insn->imm = 0;
1575 goto next_insn;
1576 }
1577
1578 if (env->insn_aux_data[i + delta].needs_zext)
1579 /* Convert BPF_CLASS(insn->code) == BPF_ALU64 to 32-bit ALU */
1580 insn->code = BPF_ALU | BPF_OP(insn->code) | BPF_SRC(insn->code);
1581
1582 /* Make sdiv/smod divide-by-minus-one exceptions impossible. */
1583 if ((insn->code == (BPF_ALU64 | BPF_MOD | BPF_K) ||
1584 insn->code == (BPF_ALU64 | BPF_DIV | BPF_K) ||
1585 insn->code == (BPF_ALU | BPF_MOD | BPF_K) ||
1586 insn->code == (BPF_ALU | BPF_DIV | BPF_K)) &&
1587 insn->off == 1 && insn->imm == -1) {
1588 bool is64 = BPF_CLASS(insn->code) == BPF_ALU64;
1589 bool isdiv = BPF_OP(insn->code) == BPF_DIV;
1590 struct bpf_insn *patch = insn_buf;
1591
1592 if (isdiv)
1593 *patch++ = BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
1594 BPF_NEG | BPF_K, insn->dst_reg,
1595 0, 0, 0);
1596 else
1597 *patch++ = BPF_MOV32_IMM(insn->dst_reg, 0);
1598
1599 cnt = patch - insn_buf;
1600
1601 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
1602 if (!new_prog)
1603 return -ENOMEM;
1604
1605 delta += cnt - 1;
1606 env->prog = prog = new_prog;
1607 insn = new_prog->insnsi + i + delta;
1608 goto next_insn;
1609 }
1610
1611 /* Make divide-by-zero and divide-by-minus-one exceptions impossible. */
1612 if (insn->code == (BPF_ALU64 | BPF_MOD | BPF_X) ||
1613 insn->code == (BPF_ALU64 | BPF_DIV | BPF_X) ||
1614 insn->code == (BPF_ALU | BPF_MOD | BPF_X) ||
1615 insn->code == (BPF_ALU | BPF_DIV | BPF_X)) {
1616 bool is64 = BPF_CLASS(insn->code) == BPF_ALU64;
1617 bool isdiv = BPF_OP(insn->code) == BPF_DIV;
1618 bool is_sdiv = isdiv && insn->off == 1;
1619 bool is_smod = !isdiv && insn->off == 1;
1620 struct bpf_insn *patch = insn_buf;
1621
1622 if (is_sdiv) {
1623 /* [R,W]x sdiv 0 -> 0
1624 * LLONG_MIN sdiv -1 -> LLONG_MIN
1625 * INT_MIN sdiv -1 -> INT_MIN
1626 */
1627 *patch++ = BPF_MOV64_REG(BPF_REG_AX, insn->src_reg);
1628 *patch++ = BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
1629 BPF_ADD | BPF_K, BPF_REG_AX,
1630 0, 0, 1);
1631 *patch++ = BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
1632 BPF_JGT | BPF_K, BPF_REG_AX,
1633 0, 4, 1);
1634 *patch++ = BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
1635 BPF_JEQ | BPF_K, BPF_REG_AX,
1636 0, 1, 0);
1637 *patch++ = BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
1638 BPF_MOV | BPF_K, insn->dst_reg,
1639 0, 0, 0);
1640 /* BPF_NEG(LLONG_MIN) == -LLONG_MIN == LLONG_MIN */
1641 *patch++ = BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
1642 BPF_NEG | BPF_K, insn->dst_reg,
1643 0, 0, 0);
1644 *patch++ = BPF_JMP_IMM(BPF_JA, 0, 0, 1);
1645 *patch++ = *insn;
1646 cnt = patch - insn_buf;
1647 } else if (is_smod) {
1648 /* [R,W]x mod 0 -> [R,W]x */
1649 /* [R,W]x mod -1 -> 0 */
1650 *patch++ = BPF_MOV64_REG(BPF_REG_AX, insn->src_reg);
1651 *patch++ = BPF_RAW_INSN((is64 ? BPF_ALU64 : BPF_ALU) |
1652 BPF_ADD | BPF_K, BPF_REG_AX,
1653 0, 0, 1);
1654 *patch++ = BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
1655 BPF_JGT | BPF_K, BPF_REG_AX,
1656 0, 3, 1);
1657 *patch++ = BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
1658 BPF_JEQ | BPF_K, BPF_REG_AX,
1659 0, 3 + (is64 ? 0 : 1), 1);
1660 *patch++ = BPF_MOV32_IMM(insn->dst_reg, 0);
1661 *patch++ = BPF_JMP_IMM(BPF_JA, 0, 0, 1);
1662 *patch++ = *insn;
1663
1664 if (!is64) {
1665 *patch++ = BPF_JMP_IMM(BPF_JA, 0, 0, 1);
1666 *patch++ = BPF_MOV32_REG(insn->dst_reg, insn->dst_reg);
1667 }
1668 cnt = patch - insn_buf;
1669 } else if (isdiv) {
1670 /* [R,W]x div 0 -> 0 */
1671 *patch++ = BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
1672 BPF_JNE | BPF_K, insn->src_reg,
1673 0, 2, 0);
1674 *patch++ = BPF_ALU32_REG(BPF_XOR, insn->dst_reg, insn->dst_reg);
1675 *patch++ = BPF_JMP_IMM(BPF_JA, 0, 0, 1);
1676 *patch++ = *insn;
1677 cnt = patch - insn_buf;
1678 } else {
1679 /* [R,W]x mod 0 -> [R,W]x */
1680 *patch++ = BPF_RAW_INSN((is64 ? BPF_JMP : BPF_JMP32) |
1681 BPF_JEQ | BPF_K, insn->src_reg,
1682 0, 1 + (is64 ? 0 : 1), 0);
1683 *patch++ = *insn;
1684
1685 if (!is64) {
1686 *patch++ = BPF_JMP_IMM(BPF_JA, 0, 0, 1);
1687 *patch++ = BPF_MOV32_REG(insn->dst_reg, insn->dst_reg);
1688 }
1689 cnt = patch - insn_buf;
1690 }
1691
1692 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
1693 if (!new_prog)
1694 return -ENOMEM;
1695
1696 delta += cnt - 1;
1697 env->prog = prog = new_prog;
1698 insn = new_prog->insnsi + i + delta;
1699 goto next_insn;
1700 }
1701
1702 /* Make it impossible to de-reference a userspace address */
1703 if (BPF_CLASS(insn->code) == BPF_LDX &&
1704 (BPF_MODE(insn->code) == BPF_PROBE_MEM ||
1705 BPF_MODE(insn->code) == BPF_PROBE_MEMSX)) {
1706 struct bpf_insn *patch = insn_buf;
1707 u64 uaddress_limit = bpf_arch_uaddress_limit();
1708
1709 if (!uaddress_limit)
1710 goto next_insn;
1711
1712 *patch++ = BPF_MOV64_REG(BPF_REG_AX, insn->src_reg);
1713 if (insn->off)
1714 *patch++ = BPF_ALU64_IMM(BPF_ADD, BPF_REG_AX, insn->off);
1715 *patch++ = BPF_ALU64_IMM(BPF_RSH, BPF_REG_AX, 32);
1716 *patch++ = BPF_JMP_IMM(BPF_JLE, BPF_REG_AX, uaddress_limit >> 32, 2);
1717 *patch++ = *insn;
1718 *patch++ = BPF_JMP_IMM(BPF_JA, 0, 0, 1);
1719 *patch++ = BPF_MOV64_IMM(insn->dst_reg, 0);
1720
1721 cnt = patch - insn_buf;
1722 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
1723 if (!new_prog)
1724 return -ENOMEM;
1725
1726 delta += cnt - 1;
1727 env->prog = prog = new_prog;
1728 insn = new_prog->insnsi + i + delta;
1729 goto next_insn;
1730 }
1731
1732 /* Implement LD_ABS and LD_IND with a rewrite, if supported by the program type. */
1733 if (BPF_CLASS(insn->code) == BPF_LD &&
1734 (BPF_MODE(insn->code) == BPF_ABS ||
1735 BPF_MODE(insn->code) == BPF_IND)) {
1736 cnt = env->ops->gen_ld_abs(insn, insn_buf);
1737 if (cnt == 0 || cnt >= INSN_BUF_SIZE) {
1738 verifier_bug(env, "%d insns generated for ld_abs", cnt);
1739 return -EFAULT;
1740 }
1741
1742 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
1743 if (!new_prog)
1744 return -ENOMEM;
1745
1746 delta += cnt - 1;
1747 env->prog = prog = new_prog;
1748 insn = new_prog->insnsi + i + delta;
1749 goto next_insn;
1750 }
1751
1752 /* Rewrite pointer arithmetic to mitigate speculation attacks. */
1753 if (insn->code == (BPF_ALU64 | BPF_ADD | BPF_X) ||
1754 insn->code == (BPF_ALU64 | BPF_SUB | BPF_X)) {
1755 const u8 code_add = BPF_ALU64 | BPF_ADD | BPF_X;
1756 const u8 code_sub = BPF_ALU64 | BPF_SUB | BPF_X;
1757 struct bpf_insn *patch = insn_buf;
1758 bool issrc, isneg, isimm;
1759 u32 off_reg;
1760
1761 aux = &env->insn_aux_data[i + delta];
1762 if (!aux->alu_state ||
1763 aux->alu_state == BPF_ALU_NON_POINTER)
1764 goto next_insn;
1765
1766 isneg = aux->alu_state & BPF_ALU_NEG_VALUE;
1767 issrc = (aux->alu_state & BPF_ALU_SANITIZE) ==
1768 BPF_ALU_SANITIZE_SRC;
1769 isimm = aux->alu_state & BPF_ALU_IMMEDIATE;
1770
1771 off_reg = issrc ? insn->src_reg : insn->dst_reg;
1772 if (isimm) {
1773 *patch++ = BPF_MOV32_IMM(BPF_REG_AX, aux->alu_limit);
1774 } else {
1775 if (isneg)
1776 *patch++ = BPF_ALU64_IMM(BPF_MUL, off_reg, -1);
1777 *patch++ = BPF_MOV32_IMM(BPF_REG_AX, aux->alu_limit);
1778 *patch++ = BPF_ALU64_REG(BPF_SUB, BPF_REG_AX, off_reg);
1779 *patch++ = BPF_ALU64_REG(BPF_OR, BPF_REG_AX, off_reg);
1780 *patch++ = BPF_ALU64_IMM(BPF_NEG, BPF_REG_AX, 0);
1781 *patch++ = BPF_ALU64_IMM(BPF_ARSH, BPF_REG_AX, 63);
1782 *patch++ = BPF_ALU64_REG(BPF_AND, BPF_REG_AX, off_reg);
1783 }
1784 if (!issrc)
1785 *patch++ = BPF_MOV64_REG(insn->dst_reg, insn->src_reg);
1786 insn->src_reg = BPF_REG_AX;
1787 if (isneg)
1788 insn->code = insn->code == code_add ?
1789 code_sub : code_add;
1790 *patch++ = *insn;
1791 if (issrc && isneg && !isimm)
1792 *patch++ = BPF_ALU64_IMM(BPF_MUL, off_reg, -1);
1793 cnt = patch - insn_buf;
1794
1795 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
1796 if (!new_prog)
1797 return -ENOMEM;
1798
1799 delta += cnt - 1;
1800 env->prog = prog = new_prog;
1801 insn = new_prog->insnsi + i + delta;
1802 goto next_insn;
1803 }
1804
1805 if (bpf_is_may_goto_insn(insn) && bpf_jit_supports_timed_may_goto()) {
1806 int stack_off_cnt = -stack_depth - 16;
1807
1808 /*
1809 * Two 8 byte slots, depth-16 stores the count, and
1810 * depth-8 stores the start timestamp of the loop.
1811 *
1812 * The starting value of count is BPF_MAX_TIMED_LOOPS
1813 * (0xffff). Every iteration loads it and subs it by 1,
1814 * until the value becomes 0 in AX (thus, 1 in stack),
1815 * after which we call arch_bpf_timed_may_goto, which
1816 * either sets AX to 0xffff to keep looping, or to 0
1817 * upon timeout. AX is then stored into the stack. In
1818 * the next iteration, we either see 0 and break out, or
1819 * continue iterating until the next time value is 0
1820 * after subtraction, rinse and repeat.
1821 */
1822 stack_depth_extra = 16;
1823 insn_buf[0] = BPF_LDX_MEM(BPF_DW, BPF_REG_AX, BPF_REG_10, stack_off_cnt);
1824 if (insn->off >= 0)
1825 insn_buf[1] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_AX, 0, insn->off + 5);
1826 else
1827 insn_buf[1] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_AX, 0, insn->off - 1);
1828 insn_buf[2] = BPF_ALU64_IMM(BPF_SUB, BPF_REG_AX, 1);
1829 insn_buf[3] = BPF_JMP_IMM(BPF_JNE, BPF_REG_AX, 0, 2);
1830 /*
1831 * AX is used as an argument to pass in stack_off_cnt
1832 * (to add to r10/fp), and also as the return value of
1833 * the call to arch_bpf_timed_may_goto.
1834 */
1835 insn_buf[4] = BPF_MOV64_IMM(BPF_REG_AX, stack_off_cnt);
1836 insn_buf[5] = BPF_EMIT_CALL(arch_bpf_timed_may_goto);
1837 insn_buf[6] = BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_AX, stack_off_cnt);
1838 cnt = 7;
1839
1840 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
1841 if (!new_prog)
1842 return -ENOMEM;
1843
1844 delta += cnt - 1;
1845 env->prog = prog = new_prog;
1846 insn = new_prog->insnsi + i + delta;
1847 goto next_insn;
1848 } else if (bpf_is_may_goto_insn(insn)) {
1849 int stack_off = -stack_depth - 8;
1850
1851 stack_depth_extra = 8;
1852 insn_buf[0] = BPF_LDX_MEM(BPF_DW, BPF_REG_AX, BPF_REG_10, stack_off);
1853 if (insn->off >= 0)
1854 insn_buf[1] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_AX, 0, insn->off + 2);
1855 else
1856 insn_buf[1] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_AX, 0, insn->off - 1);
1857 insn_buf[2] = BPF_ALU64_IMM(BPF_SUB, BPF_REG_AX, 1);
1858 insn_buf[3] = BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_AX, stack_off);
1859 cnt = 4;
1860
1861 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
1862 if (!new_prog)
1863 return -ENOMEM;
1864
1865 delta += cnt - 1;
1866 env->prog = prog = new_prog;
1867 insn = new_prog->insnsi + i + delta;
1868 goto next_insn;
1869 }
1870
1871 if (bpf_jit_supports_percpu_insn() &&
1872 insn->code == (BPF_LD | BPF_IMM | BPF_DW) &&
1873 (insn->src_reg == BPF_PSEUDO_MAP_VALUE ||
1874 insn->src_reg == BPF_PSEUDO_MAP_IDX_VALUE)) {
1875 struct bpf_map *map;
1876
1877 aux = &env->insn_aux_data[i + delta];
1878 map = env->used_maps[aux->map_index];
1879 if (map->map_type != BPF_MAP_TYPE_PERCPU_ARRAY)
1880 goto next_insn;
1881
1882 prog->jit_required = true;
1883
1884 /*
1885 * We are *skipping* first half of ld_imm64 insn
1886 * with 'i++;', patching over second half of it
1887 * with that same half + mov64_percpu_reg insn.
1888 * All because bpf_patch_insn_data() can only
1889 * replace one 8-byte insn, which does not work
1890 * well for ld_imm64 insn.
1891 */
1892
1893 insn_buf[0] = insn[1];
1894 insn_buf[1] = BPF_MOV64_PERCPU_REG(insn->dst_reg, insn->dst_reg);
1895 cnt = 2;
1896
1897 i++;
1898 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
1899 if (!new_prog)
1900 return -ENOMEM;
1901
1902 delta += cnt - 1;
1903 env->prog = prog = new_prog;
1904 insn = new_prog->insnsi + i + delta;
1905 goto next_insn;
1906 }
1907
1908 if (insn->code != (BPF_JMP | BPF_CALL))
1909 goto next_insn;
1910 if (insn->src_reg == BPF_PSEUDO_CALL)
1911 goto next_insn;
1912 if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL) {
1913 ret = bpf_fixup_kfunc_call(env, insn, insn_buf, i + delta, &cnt);
1914 if (ret)
1915 return ret;
1916 if (cnt == 0)
1917 goto next_insn;
1918
1919 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
1920 if (!new_prog)
1921 return -ENOMEM;
1922
1923 delta += cnt - 1;
1924 env->prog = prog = new_prog;
1925 insn = new_prog->insnsi + i + delta;
1926 goto next_insn;
1927 }
1928
1929 /* Skip inlining the helper call if the JIT does it. */
1930 if (bpf_jit_inlines_helper_call(insn->imm)) {
1931 prog->jit_required = 1;
1932 goto next_insn;
1933 }
1934
1935 if (insn->imm == BPF_FUNC_get_route_realm)
1936 prog->dst_needed = 1;
1937 if (insn->imm == BPF_FUNC_get_prandom_u32)
1938 bpf_user_rnd_init_once();
1939 if (insn->imm == BPF_FUNC_override_return)
1940 prog->kprobe_override = 1;
1941 if (insn->imm == BPF_FUNC_tail_call) {
1942 /* If we tail call into other programs, we
1943 * cannot make any assumptions since they can
1944 * be replaced dynamically during runtime in
1945 * the program array.
1946 */
1947 prog->cb_access = 1;
1948 if (!bpf_allow_tail_call_in_subprogs(env))
1949 prog->aux->stack_depth = MAX_BPF_STACK;
1950 prog->aux->max_pkt_offset = MAX_PACKET_OFF;
1951
1952 /* mark bpf_tail_call as different opcode to avoid
1953 * conditional branch in the interpreter for every normal
1954 * call and to prevent accidental JITing by JIT compiler
1955 * that doesn't support bpf_tail_call yet
1956 */
1957 insn->imm = 0;
1958 insn->code = BPF_JMP | BPF_TAIL_CALL;
1959
1960 aux = &env->insn_aux_data[i + delta];
1961 if (env->bpf_capable && !prog->blinding_requested &&
1962 prog->jit_requested &&
1963 !bpf_map_key_poisoned(aux) &&
1964 !bpf_map_ptr_poisoned(aux) &&
1965 !bpf_map_ptr_unpriv(aux)) {
1966 struct bpf_jit_poke_descriptor desc = {
1967 .reason = BPF_POKE_REASON_TAIL_CALL,
1968 .tail_call.map = aux->map_ptr_state.map_ptr,
1969 .tail_call.key = bpf_map_key_immediate(aux),
1970 .insn_idx = i + delta,
1971 };
1972
1973 ret = bpf_jit_add_poke_descriptor(prog, &desc);
1974 if (ret < 0) {
1975 verbose(env, "adding tail call poke descriptor failed\n");
1976 return ret;
1977 }
1978
1979 insn->imm = ret + 1;
1980 goto next_insn;
1981 }
1982
1983 if (!bpf_map_ptr_unpriv(aux))
1984 goto next_insn;
1985
1986 /* instead of changing every JIT dealing with tail_call
1987 * emit two extra insns:
1988 * if (index >= max_entries) goto out;
1989 * index &= array->index_mask;
1990 * to avoid out-of-bounds cpu speculation
1991 */
1992 if (bpf_map_ptr_poisoned(aux)) {
1993 verbose(env, "tail_call abusing map_ptr\n");
1994 return -EINVAL;
1995 }
1996
1997 map_ptr = aux->map_ptr_state.map_ptr;
1998 insn_buf[0] = BPF_JMP_IMM(BPF_JGE, BPF_REG_3,
1999 map_ptr->max_entries, 2);
2000 insn_buf[1] = BPF_ALU32_IMM(BPF_AND, BPF_REG_3,
2001 container_of(map_ptr,
2002 struct bpf_array,
2003 map)->index_mask);
2004 insn_buf[2] = *insn;
2005 cnt = 3;
2006 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
2007 if (!new_prog)
2008 return -ENOMEM;
2009
2010 delta += cnt - 1;
2011 env->prog = prog = new_prog;
2012 insn = new_prog->insnsi + i + delta;
2013 goto next_insn;
2014 }
2015
2016 if (insn->imm == BPF_FUNC_timer_set_callback) {
2017 /* The verifier will process callback_fn as many times as necessary
2018 * with different maps and the register states prepared by
2019 * set_timer_callback_state will be accurate.
2020 *
2021 * The following use case is valid:
2022 * map1 is shared by prog1, prog2, prog3.
2023 * prog1 calls bpf_timer_init for some map1 elements
2024 * prog2 calls bpf_timer_set_callback for some map1 elements.
2025 * Those that were not bpf_timer_init-ed will return -EINVAL.
2026 * prog3 calls bpf_timer_start for some map1 elements.
2027 * Those that were not both bpf_timer_init-ed and
2028 * bpf_timer_set_callback-ed will return -EINVAL.
2029 */
2030 struct bpf_insn ld_addrs[2] = {
2031 BPF_LD_IMM64(BPF_REG_3, (long)prog->aux),
2032 };
2033
2034 insn_buf[0] = ld_addrs[0];
2035 insn_buf[1] = ld_addrs[1];
2036 insn_buf[2] = *insn;
2037 cnt = 3;
2038
2039 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
2040 if (!new_prog)
2041 return -ENOMEM;
2042
2043 delta += cnt - 1;
2044 env->prog = prog = new_prog;
2045 insn = new_prog->insnsi + i + delta;
2046 goto patch_call_imm;
2047 }
2048
2049 /* bpf_per_cpu_ptr() and bpf_this_cpu_ptr() */
2050 if (env->insn_aux_data[i + delta].call_with_percpu_alloc_ptr) {
2051 /* patch with 'r1 = *(u64 *)(r1 + 0)' since for percpu data,
2052 * bpf_mem_alloc() returns a ptr to the percpu data ptr.
2053 */
2054 insn_buf[0] = BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_1, 0);
2055 insn_buf[1] = *insn;
2056 cnt = 2;
2057
2058 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
2059 if (!new_prog)
2060 return -ENOMEM;
2061
2062 delta += cnt - 1;
2063 env->prog = prog = new_prog;
2064 insn = new_prog->insnsi + i + delta;
2065 goto patch_call_imm;
2066 }
2067
2068 /* BPF_EMIT_CALL() assumptions in some of the map_gen_lookup
2069 * and other inlining handlers are currently limited to 64 bit
2070 * only.
2071 */
2072 if (prog->jit_requested && BITS_PER_LONG == 64 &&
2073 (insn->imm == BPF_FUNC_map_lookup_elem ||
2074 insn->imm == BPF_FUNC_map_update_elem ||
2075 insn->imm == BPF_FUNC_map_delete_elem ||
2076 insn->imm == BPF_FUNC_map_push_elem ||
2077 insn->imm == BPF_FUNC_map_pop_elem ||
2078 insn->imm == BPF_FUNC_map_peek_elem ||
2079 insn->imm == BPF_FUNC_redirect_map ||
2080 insn->imm == BPF_FUNC_for_each_map_elem ||
2081 insn->imm == BPF_FUNC_map_lookup_percpu_elem)) {
2082 aux = &env->insn_aux_data[i + delta];
2083 if (bpf_map_ptr_poisoned(aux))
2084 goto patch_call_imm;
2085
2086 map_ptr = aux->map_ptr_state.map_ptr;
2087 ops = map_ptr->ops;
2088 if (insn->imm == BPF_FUNC_map_lookup_elem &&
2089 ops->map_gen_lookup) {
2090 cnt = ops->map_gen_lookup(map_ptr, insn_buf);
2091 if (cnt == -EOPNOTSUPP)
2092 goto patch_map_ops_generic;
2093 if (cnt <= 0 || cnt >= INSN_BUF_SIZE) {
2094 verifier_bug(env, "%d insns generated for map lookup", cnt);
2095 return -EFAULT;
2096 }
2097
2098 if (bpf_map_is_percpu_map(map_ptr->map_type))
2099 prog->jit_required = true;
2100
2101 new_prog = bpf_patch_insn_data(env, i + delta,
2102 insn_buf, cnt);
2103 if (!new_prog)
2104 return -ENOMEM;
2105
2106 delta += cnt - 1;
2107 env->prog = prog = new_prog;
2108 insn = new_prog->insnsi + i + delta;
2109 goto next_insn;
2110 }
2111
2112 BUILD_BUG_ON(!__same_type(ops->map_lookup_elem,
2113 (void *(*)(struct bpf_map *map, void *key))NULL));
2114 BUILD_BUG_ON(!__same_type(ops->map_delete_elem,
2115 (long (*)(struct bpf_map *map, void *key))NULL));
2116 BUILD_BUG_ON(!__same_type(ops->map_update_elem,
2117 (long (*)(struct bpf_map *map, void *key, void *value,
2118 u64 flags))NULL));
2119 BUILD_BUG_ON(!__same_type(ops->map_push_elem,
2120 (long (*)(struct bpf_map *map, void *value,
2121 u64 flags))NULL));
2122 BUILD_BUG_ON(!__same_type(ops->map_pop_elem,
2123 (long (*)(struct bpf_map *map, void *value))NULL));
2124 BUILD_BUG_ON(!__same_type(ops->map_peek_elem,
2125 (long (*)(struct bpf_map *map, void *value))NULL));
2126 BUILD_BUG_ON(!__same_type(ops->map_redirect,
2127 (long (*)(struct bpf_map *map, u64 index, u64 flags))NULL));
2128 BUILD_BUG_ON(!__same_type(ops->map_for_each_callback,
2129 (long (*)(struct bpf_map *map,
2130 bpf_callback_t callback_fn,
2131 void *callback_ctx,
2132 u64 flags))NULL));
2133 BUILD_BUG_ON(!__same_type(ops->map_lookup_percpu_elem,
2134 (void *(*)(struct bpf_map *map, void *key, u32 cpu))NULL));
2135
2136 patch_map_ops_generic:
2137 switch (insn->imm) {
2138 case BPF_FUNC_map_lookup_elem:
2139 insn->imm = BPF_CALL_IMM(ops->map_lookup_elem);
2140 goto next_insn;
2141 case BPF_FUNC_map_update_elem:
2142 insn->imm = BPF_CALL_IMM(ops->map_update_elem);
2143 goto next_insn;
2144 case BPF_FUNC_map_delete_elem:
2145 insn->imm = BPF_CALL_IMM(ops->map_delete_elem);
2146 goto next_insn;
2147 case BPF_FUNC_map_push_elem:
2148 insn->imm = BPF_CALL_IMM(ops->map_push_elem);
2149 goto next_insn;
2150 case BPF_FUNC_map_pop_elem:
2151 insn->imm = BPF_CALL_IMM(ops->map_pop_elem);
2152 goto next_insn;
2153 case BPF_FUNC_map_peek_elem:
2154 insn->imm = BPF_CALL_IMM(ops->map_peek_elem);
2155 goto next_insn;
2156 case BPF_FUNC_redirect_map:
2157 insn->imm = BPF_CALL_IMM(ops->map_redirect);
2158 goto next_insn;
2159 case BPF_FUNC_for_each_map_elem:
2160 insn->imm = BPF_CALL_IMM(ops->map_for_each_callback);
2161 goto next_insn;
2162 case BPF_FUNC_map_lookup_percpu_elem:
2163 insn->imm = BPF_CALL_IMM(ops->map_lookup_percpu_elem);
2164 goto next_insn;
2165 }
2166
2167 goto patch_call_imm;
2168 }
2169
2170 /* Implement bpf_jiffies64 inline. */
2171 if (prog->jit_requested && BITS_PER_LONG == 64 &&
2172 insn->imm == BPF_FUNC_jiffies64) {
2173 struct bpf_insn ld_jiffies_addr[2] = {
2174 BPF_LD_IMM64(BPF_REG_0,
2175 (unsigned long)&jiffies),
2176 };
2177
2178 insn_buf[0] = ld_jiffies_addr[0];
2179 insn_buf[1] = ld_jiffies_addr[1];
2180 insn_buf[2] = BPF_LDX_MEM(BPF_DW, BPF_REG_0,
2181 BPF_REG_0, 0);
2182 cnt = 3;
2183
2184 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf,
2185 cnt);
2186 if (!new_prog)
2187 return -ENOMEM;
2188
2189 delta += cnt - 1;
2190 env->prog = prog = new_prog;
2191 insn = new_prog->insnsi + i + delta;
2192 goto next_insn;
2193 }
2194
2195 #if defined(CONFIG_X86_64) && !defined(CONFIG_UML)
2196 /* Implement bpf_get_smp_processor_id() inline. */
2197 if (insn->imm == BPF_FUNC_get_smp_processor_id &&
2198 bpf_verifier_inlines_helper_call(env, insn->imm)) {
2199 /* BPF_FUNC_get_smp_processor_id inlining is an
2200 * optimization, so if cpu_number is ever
2201 * changed in some incompatible and hard to support
2202 * way, it's fine to back out this inlining logic
2203 */
2204 #ifdef CONFIG_SMP
2205 prog->jit_required = true;
2206 insn_buf[0] = BPF_MOV64_IMM(BPF_REG_0, (u32)(unsigned long)&cpu_number);
2207 insn_buf[1] = BPF_MOV64_PERCPU_REG(BPF_REG_0, BPF_REG_0);
2208 insn_buf[2] = BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_0, 0);
2209 cnt = 3;
2210 #else
2211 insn_buf[0] = BPF_ALU32_REG(BPF_XOR, BPF_REG_0, BPF_REG_0);
2212 cnt = 1;
2213 #endif
2214 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
2215 if (!new_prog)
2216 return -ENOMEM;
2217
2218 delta += cnt - 1;
2219 env->prog = prog = new_prog;
2220 insn = new_prog->insnsi + i + delta;
2221 goto next_insn;
2222 }
2223
2224 /* Implement bpf_get_current_task() and bpf_get_current_task_btf() inline. */
2225 if ((insn->imm == BPF_FUNC_get_current_task || insn->imm == BPF_FUNC_get_current_task_btf) &&
2226 bpf_verifier_inlines_helper_call(env, insn->imm)) {
2227 prog->jit_required = true;
2228 insn_buf[0] = BPF_MOV64_IMM(BPF_REG_0, (u32)(unsigned long)¤t_task);
2229 insn_buf[1] = BPF_MOV64_PERCPU_REG(BPF_REG_0, BPF_REG_0);
2230 insn_buf[2] = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 0);
2231 cnt = 3;
2232
2233 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
2234 if (!new_prog)
2235 return -ENOMEM;
2236
2237 delta += cnt - 1;
2238 env->prog = prog = new_prog;
2239 insn = new_prog->insnsi + i + delta;
2240 goto next_insn;
2241 }
2242 #endif
2243 /* Implement bpf_get_func_arg inline. */
2244 if (prog_type == BPF_PROG_TYPE_TRACING &&
2245 insn->imm == BPF_FUNC_get_func_arg) {
2246 if (eatype == BPF_TRACE_RAW_TP) {
2247 int nr_args = btf_type_vlen(prog->aux->attach_func_proto);
2248
2249 /* skip 'void *__data' in btf_trace_##name() and save to reg0 */
2250 insn_buf[0] = BPF_MOV64_IMM(BPF_REG_0, nr_args - 1);
2251 cnt = 1;
2252 } else {
2253 /* Load nr_args from ctx - 8 */
2254 insn_buf[0] = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -8);
2255 insn_buf[1] = BPF_ALU64_IMM(BPF_AND, BPF_REG_0, 0xFF);
2256 cnt = 2;
2257 }
2258 insn_buf[cnt++] = BPF_JMP32_REG(BPF_JGE, BPF_REG_2, BPF_REG_0, 6);
2259 insn_buf[cnt++] = BPF_ALU64_IMM(BPF_LSH, BPF_REG_2, 3);
2260 insn_buf[cnt++] = BPF_ALU64_REG(BPF_ADD, BPF_REG_2, BPF_REG_1);
2261 insn_buf[cnt++] = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_2, 0);
2262 insn_buf[cnt++] = BPF_STX_MEM(BPF_DW, BPF_REG_3, BPF_REG_0, 0);
2263 insn_buf[cnt++] = BPF_MOV64_IMM(BPF_REG_0, 0);
2264 insn_buf[cnt++] = BPF_JMP_A(1);
2265 insn_buf[cnt++] = BPF_MOV64_IMM(BPF_REG_0, -EINVAL);
2266
2267 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
2268 if (!new_prog)
2269 return -ENOMEM;
2270
2271 delta += cnt - 1;
2272 env->prog = prog = new_prog;
2273 insn = new_prog->insnsi + i + delta;
2274 goto next_insn;
2275 }
2276
2277 /* Implement bpf_get_func_ret inline. */
2278 if (prog_type == BPF_PROG_TYPE_TRACING &&
2279 insn->imm == BPF_FUNC_get_func_ret) {
2280 if (eatype == BPF_TRACE_FEXIT ||
2281 eatype == BPF_TRACE_FSESSION ||
2282 eatype == BPF_TRACE_FEXIT_MULTI ||
2283 eatype == BPF_TRACE_FSESSION_MULTI ||
2284 eatype == BPF_MODIFY_RETURN) {
2285 /* Load nr_args from ctx - 8 */
2286 insn_buf[0] = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -8);
2287 insn_buf[1] = BPF_ALU64_IMM(BPF_AND, BPF_REG_0, 0xFF);
2288 insn_buf[2] = BPF_ALU64_IMM(BPF_LSH, BPF_REG_0, 3);
2289 insn_buf[3] = BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1);
2290 insn_buf[4] = BPF_LDX_MEM(BPF_DW, BPF_REG_3, BPF_REG_0, 0);
2291 insn_buf[5] = BPF_STX_MEM(BPF_DW, BPF_REG_2, BPF_REG_3, 0);
2292 insn_buf[6] = BPF_MOV64_IMM(BPF_REG_0, 0);
2293 cnt = 7;
2294 } else {
2295 insn_buf[0] = BPF_MOV64_IMM(BPF_REG_0, -EOPNOTSUPP);
2296 cnt = 1;
2297 }
2298
2299 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
2300 if (!new_prog)
2301 return -ENOMEM;
2302
2303 delta += cnt - 1;
2304 env->prog = prog = new_prog;
2305 insn = new_prog->insnsi + i + delta;
2306 goto next_insn;
2307 }
2308
2309 /* Implement get_func_arg_cnt inline. */
2310 if (prog_type == BPF_PROG_TYPE_TRACING &&
2311 insn->imm == BPF_FUNC_get_func_arg_cnt) {
2312 if (eatype == BPF_TRACE_RAW_TP) {
2313 int nr_args = btf_type_vlen(prog->aux->attach_func_proto);
2314
2315 /* skip 'void *__data' in btf_trace_##name() and save to reg0 */
2316 insn_buf[0] = BPF_MOV64_IMM(BPF_REG_0, nr_args - 1);
2317 cnt = 1;
2318 } else {
2319 /* Load nr_args from ctx - 8 */
2320 insn_buf[0] = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -8);
2321 insn_buf[1] = BPF_ALU64_IMM(BPF_AND, BPF_REG_0, 0xFF);
2322 cnt = 2;
2323 }
2324
2325 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
2326 if (!new_prog)
2327 return -ENOMEM;
2328
2329 delta += cnt - 1;
2330 env->prog = prog = new_prog;
2331 insn = new_prog->insnsi + i + delta;
2332 goto next_insn;
2333 }
2334
2335 /* Implement bpf_get_func_ip inline. */
2336 if (prog_type == BPF_PROG_TYPE_TRACING &&
2337 insn->imm == BPF_FUNC_get_func_ip) {
2338 /* Load IP address from ctx - 16 */
2339 insn_buf[0] = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_1, -16);
2340
2341 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, 1);
2342 if (!new_prog)
2343 return -ENOMEM;
2344
2345 env->prog = prog = new_prog;
2346 insn = new_prog->insnsi + i + delta;
2347 goto next_insn;
2348 }
2349
2350 /* Implement bpf_get_branch_snapshot inline. */
2351 if (IS_ENABLED(CONFIG_PERF_EVENTS) &&
2352 prog->jit_requested && BITS_PER_LONG == 64 &&
2353 insn->imm == BPF_FUNC_get_branch_snapshot) {
2354 /* We are dealing with the following func protos:
2355 * u64 bpf_get_branch_snapshot(void *buf, u32 size, u64 flags);
2356 * int perf_snapshot_branch_stack(struct perf_branch_entry *entries, u32 cnt);
2357 */
2358 const u32 br_entry_size = sizeof(struct perf_branch_entry);
2359
2360 /* struct perf_branch_entry is part of UAPI and is
2361 * used as an array element, so extremely unlikely to
2362 * ever grow or shrink
2363 */
2364 BUILD_BUG_ON(br_entry_size != 24);
2365
2366 /* if (unlikely(flags)) return -EINVAL */
2367 insn_buf[0] = BPF_JMP_IMM(BPF_JNE, BPF_REG_3, 0, 7);
2368
2369 /* Transform size (bytes) into number of entries (cnt = size / 24).
2370 * But to avoid expensive division instruction, we implement
2371 * divide-by-3 through multiplication, followed by further
2372 * division by 8 through 3-bit right shift.
2373 * Refer to book "Hacker's Delight, 2nd ed." by Henry S. Warren, Jr.,
2374 * p. 227, chapter "Unsigned Division by 3" for details and proofs.
2375 *
2376 * N / 3 <=> M * N / 2^33, where M = (2^33 + 1) / 3 = 0xaaaaaaab.
2377 */
2378 insn_buf[1] = BPF_MOV32_IMM(BPF_REG_0, 0xaaaaaaab);
2379 insn_buf[2] = BPF_ALU64_REG(BPF_MUL, BPF_REG_2, BPF_REG_0);
2380 insn_buf[3] = BPF_ALU64_IMM(BPF_RSH, BPF_REG_2, 36);
2381
2382 /* call perf_snapshot_branch_stack implementation */
2383 insn_buf[4] = BPF_EMIT_CALL(static_call_query(perf_snapshot_branch_stack));
2384 /* if (entry_cnt == 0) return -ENOENT */
2385 insn_buf[5] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 4);
2386 /* return entry_cnt * sizeof(struct perf_branch_entry) */
2387 insn_buf[6] = BPF_ALU32_IMM(BPF_MUL, BPF_REG_0, br_entry_size);
2388 insn_buf[7] = BPF_JMP_A(3);
2389 /* return -EINVAL; */
2390 insn_buf[8] = BPF_MOV64_IMM(BPF_REG_0, -EINVAL);
2391 insn_buf[9] = BPF_JMP_A(1);
2392 /* return -ENOENT; */
2393 insn_buf[10] = BPF_MOV64_IMM(BPF_REG_0, -ENOENT);
2394 cnt = 11;
2395
2396 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
2397 if (!new_prog)
2398 return -ENOMEM;
2399
2400 delta += cnt - 1;
2401 env->prog = prog = new_prog;
2402 insn = new_prog->insnsi + i + delta;
2403 goto next_insn;
2404 }
2405
2406 /* Implement bpf_kptr_xchg inline */
2407 if (prog->jit_requested && BITS_PER_LONG == 64 &&
2408 insn->imm == BPF_FUNC_kptr_xchg &&
2409 bpf_jit_supports_ptr_xchg()) {
2410 insn_buf[0] = BPF_MOV64_REG(BPF_REG_0, BPF_REG_2);
2411 insn_buf[1] = BPF_ATOMIC_OP(BPF_DW, BPF_XCHG, BPF_REG_1, BPF_REG_0, 0);
2412 cnt = 2;
2413
2414 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
2415 if (!new_prog)
2416 return -ENOMEM;
2417
2418 delta += cnt - 1;
2419 env->prog = prog = new_prog;
2420 insn = new_prog->insnsi + i + delta;
2421 goto next_insn;
2422 }
2423 patch_call_imm:
2424 fn = env->ops->get_func_proto(insn->imm, env->prog);
2425 /* all functions that have prototype and verifier allowed
2426 * programs to call them, must be real in-kernel functions
2427 */
2428 if (!fn->func) {
2429 verifier_bug(env,
2430 "not inlined functions %s#%d is missing func",
2431 func_id_name(insn->imm), insn->imm);
2432 return -EFAULT;
2433 }
2434 insn->imm = BPF_CALL_IMM(fn->func);
2435 next_insn:
2436 if (subprogs[cur_subprog + 1].start == i + delta + 1) {
2437 subprogs[cur_subprog].stack_depth += stack_depth_extra;
2438 subprogs[cur_subprog].stack_extra = stack_depth_extra;
2439
2440 stack_depth = subprogs[cur_subprog].stack_depth;
2441 if (stack_depth > MAX_BPF_STACK && !prog->jit_requested) {
2442 verbose(env, "stack size %d(extra %d) is too large\n",
2443 stack_depth, stack_depth_extra);
2444 return -EINVAL;
2445 }
2446 cur_subprog++;
2447 stack_depth = subprogs[cur_subprog].stack_depth;
2448 stack_depth_extra = 0;
2449 }
2450 i++;
2451 insn++;
2452 }
2453
2454 env->prog->aux->stack_depth = subprogs[0].stack_depth;
2455 for (i = 0; i < env->subprog_cnt; i++) {
2456 int delta = bpf_jit_supports_timed_may_goto() ? 2 : 1;
2457 int subprog_start = subprogs[i].start;
2458 int stack_slots = subprogs[i].stack_extra / 8;
2459 int slots = delta, cnt = 0;
2460
2461 if (!stack_slots)
2462 continue;
2463 /* We need two slots in case timed may_goto is supported. */
2464 if (stack_slots > slots) {
2465 verifier_bug(env, "stack_slots supports may_goto only");
2466 return -EFAULT;
2467 }
2468
2469 stack_depth = subprogs[i].stack_depth;
2470 if (bpf_jit_supports_timed_may_goto()) {
2471 insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_FP, -stack_depth,
2472 BPF_MAX_TIMED_LOOPS);
2473 insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_FP, -stack_depth + 8, 0);
2474 } else {
2475 /* Add ST insn to subprog prologue to init extra stack */
2476 insn_buf[cnt++] = BPF_ST_MEM(BPF_DW, BPF_REG_FP, -stack_depth,
2477 BPF_MAX_LOOPS);
2478 }
2479 /* Copy first actual insn to preserve it */
2480 insn_buf[cnt++] = env->prog->insnsi[subprog_start];
2481
2482 new_prog = bpf_patch_insn_data(env, subprog_start, insn_buf, cnt);
2483 if (!new_prog)
2484 return -ENOMEM;
2485 env->prog = prog = new_prog;
2486 /*
2487 * If may_goto is a first insn of a prog there could be a jmp
2488 * insn that points to it, hence adjust all such jmps to point
2489 * to insn after BPF_ST that inits may_goto count.
2490 * Adjustment will succeed because bpf_patch_insn_data() didn't fail.
2491 */
2492 WARN_ON(adjust_jmp_off(env->prog, subprog_start, delta));
2493 }
2494
2495 /* Since poke tab is now finalized, publish aux to tracker. */
2496 for (i = 0; i < prog->aux->size_poke_tab; i++) {
2497 map_ptr = prog->aux->poke_tab[i].tail_call.map;
2498 if (!map_ptr->ops->map_poke_track ||
2499 !map_ptr->ops->map_poke_untrack ||
2500 !map_ptr->ops->map_poke_run) {
2501 verifier_bug(env, "poke tab is misconfigured");
2502 return -EFAULT;
2503 }
2504
2505 ret = map_ptr->ops->map_poke_track(map_ptr, prog->aux);
2506 if (ret < 0) {
2507 verbose(env, "tracking tail call prog failed\n");
2508 return ret;
2509 }
2510 }
2511
2512 ret = sort_kfunc_descs_by_imm_off(env);
2513 if (ret)
2514 return ret;
2515
2516 return 0;
2517 }
2518
inline_bpf_loop(struct bpf_verifier_env * env,int position,s32 stack_base,u32 callback_subprogno,u32 * total_cnt)2519 static struct bpf_prog *inline_bpf_loop(struct bpf_verifier_env *env,
2520 int position,
2521 s32 stack_base,
2522 u32 callback_subprogno,
2523 u32 *total_cnt)
2524 {
2525 s32 r6_offset = stack_base + 0 * BPF_REG_SIZE;
2526 s32 r7_offset = stack_base + 1 * BPF_REG_SIZE;
2527 s32 r8_offset = stack_base + 2 * BPF_REG_SIZE;
2528 int reg_loop_max = BPF_REG_6;
2529 int reg_loop_cnt = BPF_REG_7;
2530 int reg_loop_ctx = BPF_REG_8;
2531
2532 struct bpf_insn *insn_buf = env->insn_buf;
2533 struct bpf_prog *new_prog;
2534 u32 callback_start;
2535 u32 call_insn_offset;
2536 s32 callback_offset;
2537 u32 cnt = 0;
2538
2539 /* This represents an inlined version of bpf_iter.c:bpf_loop,
2540 * be careful to modify this code in sync.
2541 */
2542
2543 /* Return error and jump to the end of the patch if
2544 * expected number of iterations is too big.
2545 */
2546 insn_buf[cnt++] = BPF_JMP_IMM(BPF_JLE, BPF_REG_1, BPF_MAX_LOOPS, 2);
2547 insn_buf[cnt++] = BPF_MOV32_IMM(BPF_REG_0, -E2BIG);
2548 insn_buf[cnt++] = BPF_JMP_IMM(BPF_JA, 0, 0, 16);
2549 /* spill R6, R7, R8 to use these as loop vars */
2550 insn_buf[cnt++] = BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_6, r6_offset);
2551 insn_buf[cnt++] = BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_7, r7_offset);
2552 insn_buf[cnt++] = BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_8, r8_offset);
2553 /* initialize loop vars */
2554 insn_buf[cnt++] = BPF_MOV64_REG(reg_loop_max, BPF_REG_1);
2555 insn_buf[cnt++] = BPF_MOV32_IMM(reg_loop_cnt, 0);
2556 insn_buf[cnt++] = BPF_MOV64_REG(reg_loop_ctx, BPF_REG_3);
2557 /* loop header,
2558 * if reg_loop_cnt >= reg_loop_max skip the loop body
2559 */
2560 insn_buf[cnt++] = BPF_JMP_REG(BPF_JGE, reg_loop_cnt, reg_loop_max, 5);
2561 /* callback call,
2562 * correct callback offset would be set after patching
2563 */
2564 insn_buf[cnt++] = BPF_MOV64_REG(BPF_REG_1, reg_loop_cnt);
2565 insn_buf[cnt++] = BPF_MOV64_REG(BPF_REG_2, reg_loop_ctx);
2566 insn_buf[cnt++] = BPF_CALL_REL(0);
2567 /* increment loop counter */
2568 insn_buf[cnt++] = BPF_ALU64_IMM(BPF_ADD, reg_loop_cnt, 1);
2569 /* jump to loop header if callback returned 0 */
2570 insn_buf[cnt++] = BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, -6);
2571 /* return value of bpf_loop,
2572 * set R0 to the number of iterations
2573 */
2574 insn_buf[cnt++] = BPF_MOV64_REG(BPF_REG_0, reg_loop_cnt);
2575 /* restore original values of R6, R7, R8 */
2576 insn_buf[cnt++] = BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_10, r6_offset);
2577 insn_buf[cnt++] = BPF_LDX_MEM(BPF_DW, BPF_REG_7, BPF_REG_10, r7_offset);
2578 insn_buf[cnt++] = BPF_LDX_MEM(BPF_DW, BPF_REG_8, BPF_REG_10, r8_offset);
2579
2580 *total_cnt = cnt;
2581 new_prog = bpf_patch_insn_data(env, position, insn_buf, cnt);
2582 if (!new_prog)
2583 return new_prog;
2584
2585 /* callback start is known only after patching */
2586 callback_start = env->subprog_info[callback_subprogno].start;
2587 /* Note: insn_buf[12] is an offset of BPF_CALL_REL instruction */
2588 call_insn_offset = position + 12;
2589 callback_offset = callback_start - call_insn_offset - 1;
2590 new_prog->insnsi[call_insn_offset].imm = callback_offset;
2591
2592 return new_prog;
2593 }
2594
is_bpf_loop_call(struct bpf_insn * insn)2595 static bool is_bpf_loop_call(struct bpf_insn *insn)
2596 {
2597 return insn->code == (BPF_JMP | BPF_CALL) &&
2598 insn->src_reg == 0 &&
2599 insn->imm == BPF_FUNC_loop;
2600 }
2601
2602 /* For all sub-programs in the program (including main) check
2603 * insn_aux_data to see if there are bpf_loop calls that require
2604 * inlining. If such calls are found the calls are replaced with a
2605 * sequence of instructions produced by `inline_bpf_loop` function and
2606 * subprog stack_depth is increased by the size of 3 registers.
2607 * This stack space is used to spill values of the R6, R7, R8. These
2608 * registers are used to store the loop bound, counter and context
2609 * variables.
2610 */
bpf_optimize_bpf_loop(struct bpf_verifier_env * env)2611 int bpf_optimize_bpf_loop(struct bpf_verifier_env *env)
2612 {
2613 struct bpf_subprog_info *subprogs = env->subprog_info;
2614 int i, cur_subprog = 0, cnt, delta = 0;
2615 struct bpf_insn *insn = env->prog->insnsi;
2616 int insn_cnt = env->prog->len;
2617 u16 stack_depth = subprogs[cur_subprog].stack_depth;
2618 u16 stack_depth_roundup = round_up(stack_depth, 8) - stack_depth;
2619 u16 stack_depth_extra = 0;
2620
2621 for (i = 0; i < insn_cnt; i++, insn++) {
2622 struct bpf_loop_inline_state *inline_state =
2623 &env->insn_aux_data[i + delta].loop_inline_state;
2624
2625 if (is_bpf_loop_call(insn) && inline_state->fit_for_inline) {
2626 struct bpf_prog *new_prog;
2627
2628 stack_depth_extra = BPF_REG_SIZE * 3 + stack_depth_roundup;
2629 new_prog = inline_bpf_loop(env,
2630 i + delta,
2631 -(stack_depth + stack_depth_extra),
2632 inline_state->callback_subprogno,
2633 &cnt);
2634 if (!new_prog)
2635 return -ENOMEM;
2636
2637 delta += cnt - 1;
2638 env->prog = new_prog;
2639 insn = new_prog->insnsi + i + delta;
2640 }
2641
2642 if (subprogs[cur_subprog + 1].start == i + delta + 1) {
2643 subprogs[cur_subprog].stack_depth += stack_depth_extra;
2644 cur_subprog++;
2645 stack_depth = subprogs[cur_subprog].stack_depth;
2646 stack_depth_roundup = round_up(stack_depth, 8) - stack_depth;
2647 stack_depth_extra = 0;
2648 }
2649 }
2650
2651 env->prog->aux->stack_depth = env->subprog_info[0].stack_depth;
2652
2653 return 0;
2654 }
2655
2656 /* Remove unnecessary spill/fill pairs, members of fastcall pattern,
2657 * adjust subprograms stack depth when possible.
2658 */
bpf_remove_fastcall_spills_fills(struct bpf_verifier_env * env)2659 int bpf_remove_fastcall_spills_fills(struct bpf_verifier_env *env)
2660 {
2661 struct bpf_subprog_info *subprog = env->subprog_info;
2662 struct bpf_insn_aux_data *aux = env->insn_aux_data;
2663 struct bpf_insn *insn = env->prog->insnsi;
2664 int insn_cnt = env->prog->len;
2665 u32 spills_num;
2666 bool modified = false;
2667 int i, j;
2668
2669 for (i = 0; i < insn_cnt; i++, insn++) {
2670 if (aux[i].fastcall_spills_num > 0) {
2671 spills_num = aux[i].fastcall_spills_num;
2672 /* NOPs would be removed by opt_remove_nops() */
2673 for (j = 1; j <= spills_num; ++j) {
2674 *(insn - j) = NOP;
2675 *(insn + j) = NOP;
2676 }
2677 modified = true;
2678 }
2679 if ((subprog + 1)->start == i + 1) {
2680 if (modified && !subprog->keep_fastcall_stack)
2681 subprog->stack_depth = -subprog->fastcall_stack_off;
2682 subprog++;
2683 modified = false;
2684 }
2685 }
2686
2687 return 0;
2688 }
2689
2690