bpf_jit_comp.c 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687
  1. /* bpf_jit_comp.c: BPF JIT compiler for PPC64
  2. *
  3. * Copyright 2011 Matt Evans <matt@ozlabs.org>, IBM Corporation
  4. *
  5. * Based on the x86 BPF compiler, by Eric Dumazet (eric.dumazet@gmail.com)
  6. *
  7. * This program is free software; you can redistribute it and/or
  8. * modify it under the terms of the GNU General Public License
  9. * as published by the Free Software Foundation; version 2
  10. * of the License.
  11. */
  12. #include <linux/moduleloader.h>
  13. #include <asm/cacheflush.h>
  14. #include <linux/netdevice.h>
  15. #include <linux/filter.h>
  16. #include "bpf_jit.h"
  17. #ifndef __BIG_ENDIAN
  18. /* There are endianness assumptions herein. */
  19. #error "Little-endian PPC not supported in BPF compiler"
  20. #endif
  21. int bpf_jit_enable __read_mostly;
  22. static inline void bpf_flush_icache(void *start, void *end)
  23. {
  24. smp_wmb();
  25. flush_icache_range((unsigned long)start, (unsigned long)end);
  26. }
  27. static void bpf_jit_build_prologue(struct sk_filter *fp, u32 *image,
  28. struct codegen_context *ctx)
  29. {
  30. int i;
  31. const struct sock_filter *filter = fp->insns;
  32. if (ctx->seen & (SEEN_MEM | SEEN_DATAREF)) {
  33. /* Make stackframe */
  34. if (ctx->seen & SEEN_DATAREF) {
  35. /* If we call any helpers (for loads), save LR */
  36. EMIT(PPC_INST_MFLR | __PPC_RT(0));
  37. PPC_STD(0, 1, 16);
  38. /* Back up non-volatile regs. */
  39. PPC_STD(r_D, 1, -(8*(32-r_D)));
  40. PPC_STD(r_HL, 1, -(8*(32-r_HL)));
  41. }
  42. if (ctx->seen & SEEN_MEM) {
  43. /*
  44. * Conditionally save regs r15-r31 as some will be used
  45. * for M[] data.
  46. */
  47. for (i = r_M; i < (r_M+16); i++) {
  48. if (ctx->seen & (1 << (i-r_M)))
  49. PPC_STD(i, 1, -(8*(32-i)));
  50. }
  51. }
  52. EMIT(PPC_INST_STDU | __PPC_RS(1) | __PPC_RA(1) |
  53. (-BPF_PPC_STACKFRAME & 0xfffc));
  54. }
  55. if (ctx->seen & SEEN_DATAREF) {
  56. /*
  57. * If this filter needs to access skb data,
  58. * prepare r_D and r_HL:
  59. * r_HL = skb->len - skb->data_len
  60. * r_D = skb->data
  61. */
  62. PPC_LWZ_OFFS(r_scratch1, r_skb, offsetof(struct sk_buff,
  63. data_len));
  64. PPC_LWZ_OFFS(r_HL, r_skb, offsetof(struct sk_buff, len));
  65. PPC_SUB(r_HL, r_HL, r_scratch1);
  66. PPC_LD_OFFS(r_D, r_skb, offsetof(struct sk_buff, data));
  67. }
  68. if (ctx->seen & SEEN_XREG) {
  69. /*
  70. * TODO: Could also detect whether first instr. sets X and
  71. * avoid this (as below, with A).
  72. */
  73. PPC_LI(r_X, 0);
  74. }
  75. switch (filter[0].code) {
  76. case BPF_S_RET_K:
  77. case BPF_S_LD_W_LEN:
  78. case BPF_S_ANC_PROTOCOL:
  79. case BPF_S_ANC_IFINDEX:
  80. case BPF_S_ANC_MARK:
  81. case BPF_S_ANC_RXHASH:
  82. case BPF_S_ANC_CPU:
  83. case BPF_S_ANC_QUEUE:
  84. case BPF_S_LD_W_ABS:
  85. case BPF_S_LD_H_ABS:
  86. case BPF_S_LD_B_ABS:
  87. /* first instruction sets A register (or is RET 'constant') */
  88. break;
  89. default:
  90. /* make sure we dont leak kernel information to user */
  91. PPC_LI(r_A, 0);
  92. }
  93. }
  94. static void bpf_jit_build_epilogue(u32 *image, struct codegen_context *ctx)
  95. {
  96. int i;
  97. if (ctx->seen & (SEEN_MEM | SEEN_DATAREF)) {
  98. PPC_ADDI(1, 1, BPF_PPC_STACKFRAME);
  99. if (ctx->seen & SEEN_DATAREF) {
  100. PPC_LD(0, 1, 16);
  101. PPC_MTLR(0);
  102. PPC_LD(r_D, 1, -(8*(32-r_D)));
  103. PPC_LD(r_HL, 1, -(8*(32-r_HL)));
  104. }
  105. if (ctx->seen & SEEN_MEM) {
  106. /* Restore any saved non-vol registers */
  107. for (i = r_M; i < (r_M+16); i++) {
  108. if (ctx->seen & (1 << (i-r_M)))
  109. PPC_LD(i, 1, -(8*(32-i)));
  110. }
  111. }
  112. }
  113. /* The RETs have left a return value in R3. */
  114. PPC_BLR();
  115. }
  116. #define CHOOSE_LOAD_FUNC(K, func) \
  117. ((int)K < 0 ? ((int)K >= SKF_LL_OFF ? func##_negative_offset : func) : func##_positive_offset)
  118. /* Assemble the body code between the prologue & epilogue. */
  119. static int bpf_jit_build_body(struct sk_filter *fp, u32 *image,
  120. struct codegen_context *ctx,
  121. unsigned int *addrs)
  122. {
  123. const struct sock_filter *filter = fp->insns;
  124. int flen = fp->len;
  125. u8 *func;
  126. unsigned int true_cond;
  127. int i;
  128. /* Start of epilogue code */
  129. unsigned int exit_addr = addrs[flen];
  130. for (i = 0; i < flen; i++) {
  131. unsigned int K = filter[i].k;
  132. /*
  133. * addrs[] maps a BPF bytecode address into a real offset from
  134. * the start of the body code.
  135. */
  136. addrs[i] = ctx->idx * 4;
  137. switch (filter[i].code) {
  138. /*** ALU ops ***/
  139. case BPF_S_ALU_ADD_X: /* A += X; */
  140. ctx->seen |= SEEN_XREG;
  141. PPC_ADD(r_A, r_A, r_X);
  142. break;
  143. case BPF_S_ALU_ADD_K: /* A += K; */
  144. if (!K)
  145. break;
  146. PPC_ADDI(r_A, r_A, IMM_L(K));
  147. if (K >= 32768)
  148. PPC_ADDIS(r_A, r_A, IMM_HA(K));
  149. break;
  150. case BPF_S_ALU_SUB_X: /* A -= X; */
  151. ctx->seen |= SEEN_XREG;
  152. PPC_SUB(r_A, r_A, r_X);
  153. break;
  154. case BPF_S_ALU_SUB_K: /* A -= K */
  155. if (!K)
  156. break;
  157. PPC_ADDI(r_A, r_A, IMM_L(-K));
  158. if (K >= 32768)
  159. PPC_ADDIS(r_A, r_A, IMM_HA(-K));
  160. break;
  161. case BPF_S_ALU_MUL_X: /* A *= X; */
  162. ctx->seen |= SEEN_XREG;
  163. PPC_MUL(r_A, r_A, r_X);
  164. break;
  165. case BPF_S_ALU_MUL_K: /* A *= K */
  166. if (K < 32768)
  167. PPC_MULI(r_A, r_A, K);
  168. else {
  169. PPC_LI32(r_scratch1, K);
  170. PPC_MUL(r_A, r_A, r_scratch1);
  171. }
  172. break;
  173. case BPF_S_ALU_DIV_X: /* A /= X; */
  174. ctx->seen |= SEEN_XREG;
  175. PPC_CMPWI(r_X, 0);
  176. if (ctx->pc_ret0 != -1) {
  177. PPC_BCC(COND_EQ, addrs[ctx->pc_ret0]);
  178. } else {
  179. /*
  180. * Exit, returning 0; first pass hits here
  181. * (longer worst-case code size).
  182. */
  183. PPC_BCC_SHORT(COND_NE, (ctx->idx*4)+12);
  184. PPC_LI(r_ret, 0);
  185. PPC_JMP(exit_addr);
  186. }
  187. PPC_DIVWU(r_A, r_A, r_X);
  188. break;
  189. case BPF_S_ALU_DIV_K: /* A = reciprocal_divide(A, K); */
  190. PPC_LI32(r_scratch1, K);
  191. /* Top 32 bits of 64bit result -> A */
  192. PPC_MULHWU(r_A, r_A, r_scratch1);
  193. break;
  194. case BPF_S_ALU_AND_X:
  195. ctx->seen |= SEEN_XREG;
  196. PPC_AND(r_A, r_A, r_X);
  197. break;
  198. case BPF_S_ALU_AND_K:
  199. if (!IMM_H(K))
  200. PPC_ANDI(r_A, r_A, K);
  201. else {
  202. PPC_LI32(r_scratch1, K);
  203. PPC_AND(r_A, r_A, r_scratch1);
  204. }
  205. break;
  206. case BPF_S_ALU_OR_X:
  207. ctx->seen |= SEEN_XREG;
  208. PPC_OR(r_A, r_A, r_X);
  209. break;
  210. case BPF_S_ALU_OR_K:
  211. if (IMM_L(K))
  212. PPC_ORI(r_A, r_A, IMM_L(K));
  213. if (K >= 65536)
  214. PPC_ORIS(r_A, r_A, IMM_H(K));
  215. break;
  216. case BPF_S_ALU_LSH_X: /* A <<= X; */
  217. ctx->seen |= SEEN_XREG;
  218. PPC_SLW(r_A, r_A, r_X);
  219. break;
  220. case BPF_S_ALU_LSH_K:
  221. if (K == 0)
  222. break;
  223. else
  224. PPC_SLWI(r_A, r_A, K);
  225. break;
  226. case BPF_S_ALU_RSH_X: /* A >>= X; */
  227. ctx->seen |= SEEN_XREG;
  228. PPC_SRW(r_A, r_A, r_X);
  229. break;
  230. case BPF_S_ALU_RSH_K: /* A >>= K; */
  231. if (K == 0)
  232. break;
  233. else
  234. PPC_SRWI(r_A, r_A, K);
  235. break;
  236. case BPF_S_ALU_NEG:
  237. PPC_NEG(r_A, r_A);
  238. break;
  239. case BPF_S_RET_K:
  240. PPC_LI32(r_ret, K);
  241. if (!K) {
  242. if (ctx->pc_ret0 == -1)
  243. ctx->pc_ret0 = i;
  244. }
  245. /*
  246. * If this isn't the very last instruction, branch to
  247. * the epilogue if we've stuff to clean up. Otherwise,
  248. * if there's nothing to tidy, just return. If we /are/
  249. * the last instruction, we're about to fall through to
  250. * the epilogue to return.
  251. */
  252. if (i != flen - 1) {
  253. /*
  254. * Note: 'seen' is properly valid only on pass
  255. * #2. Both parts of this conditional are the
  256. * same instruction size though, meaning the
  257. * first pass will still correctly determine the
  258. * code size/addresses.
  259. */
  260. if (ctx->seen)
  261. PPC_JMP(exit_addr);
  262. else
  263. PPC_BLR();
  264. }
  265. break;
  266. case BPF_S_RET_A:
  267. PPC_MR(r_ret, r_A);
  268. if (i != flen - 1) {
  269. if (ctx->seen)
  270. PPC_JMP(exit_addr);
  271. else
  272. PPC_BLR();
  273. }
  274. break;
  275. case BPF_S_MISC_TAX: /* X = A */
  276. PPC_MR(r_X, r_A);
  277. break;
  278. case BPF_S_MISC_TXA: /* A = X */
  279. ctx->seen |= SEEN_XREG;
  280. PPC_MR(r_A, r_X);
  281. break;
  282. /*** Constant loads/M[] access ***/
  283. case BPF_S_LD_IMM: /* A = K */
  284. PPC_LI32(r_A, K);
  285. break;
  286. case BPF_S_LDX_IMM: /* X = K */
  287. PPC_LI32(r_X, K);
  288. break;
  289. case BPF_S_LD_MEM: /* A = mem[K] */
  290. PPC_MR(r_A, r_M + (K & 0xf));
  291. ctx->seen |= SEEN_MEM | (1<<(K & 0xf));
  292. break;
  293. case BPF_S_LDX_MEM: /* X = mem[K] */
  294. PPC_MR(r_X, r_M + (K & 0xf));
  295. ctx->seen |= SEEN_MEM | (1<<(K & 0xf));
  296. break;
  297. case BPF_S_ST: /* mem[K] = A */
  298. PPC_MR(r_M + (K & 0xf), r_A);
  299. ctx->seen |= SEEN_MEM | (1<<(K & 0xf));
  300. break;
  301. case BPF_S_STX: /* mem[K] = X */
  302. PPC_MR(r_M + (K & 0xf), r_X);
  303. ctx->seen |= SEEN_XREG | SEEN_MEM | (1<<(K & 0xf));
  304. break;
  305. case BPF_S_LD_W_LEN: /* A = skb->len; */
  306. BUILD_BUG_ON(FIELD_SIZEOF(struct sk_buff, len) != 4);
  307. PPC_LWZ_OFFS(r_A, r_skb, offsetof(struct sk_buff, len));
  308. break;
  309. case BPF_S_LDX_W_LEN: /* X = skb->len; */
  310. PPC_LWZ_OFFS(r_X, r_skb, offsetof(struct sk_buff, len));
  311. break;
  312. /*** Ancillary info loads ***/
  313. /* None of the BPF_S_ANC* codes appear to be passed by
  314. * sk_chk_filter(). The interpreter and the x86 BPF
  315. * compiler implement them so we do too -- they may be
  316. * planted in future.
  317. */
  318. case BPF_S_ANC_PROTOCOL: /* A = ntohs(skb->protocol); */
  319. BUILD_BUG_ON(FIELD_SIZEOF(struct sk_buff,
  320. protocol) != 2);
  321. PPC_LHZ_OFFS(r_A, r_skb, offsetof(struct sk_buff,
  322. protocol));
  323. /* ntohs is a NOP with BE loads. */
  324. break;
  325. case BPF_S_ANC_IFINDEX:
  326. PPC_LD_OFFS(r_scratch1, r_skb, offsetof(struct sk_buff,
  327. dev));
  328. PPC_CMPDI(r_scratch1, 0);
  329. if (ctx->pc_ret0 != -1) {
  330. PPC_BCC(COND_EQ, addrs[ctx->pc_ret0]);
  331. } else {
  332. /* Exit, returning 0; first pass hits here. */
  333. PPC_BCC_SHORT(COND_NE, (ctx->idx*4)+12);
  334. PPC_LI(r_ret, 0);
  335. PPC_JMP(exit_addr);
  336. }
  337. BUILD_BUG_ON(FIELD_SIZEOF(struct net_device,
  338. ifindex) != 4);
  339. PPC_LWZ_OFFS(r_A, r_scratch1,
  340. offsetof(struct net_device, ifindex));
  341. break;
  342. case BPF_S_ANC_MARK:
  343. BUILD_BUG_ON(FIELD_SIZEOF(struct sk_buff, mark) != 4);
  344. PPC_LWZ_OFFS(r_A, r_skb, offsetof(struct sk_buff,
  345. mark));
  346. break;
  347. case BPF_S_ANC_RXHASH:
  348. BUILD_BUG_ON(FIELD_SIZEOF(struct sk_buff, rxhash) != 4);
  349. PPC_LWZ_OFFS(r_A, r_skb, offsetof(struct sk_buff,
  350. rxhash));
  351. break;
  352. case BPF_S_ANC_QUEUE:
  353. BUILD_BUG_ON(FIELD_SIZEOF(struct sk_buff,
  354. queue_mapping) != 2);
  355. PPC_LHZ_OFFS(r_A, r_skb, offsetof(struct sk_buff,
  356. queue_mapping));
  357. break;
  358. case BPF_S_ANC_CPU:
  359. #ifdef CONFIG_SMP
  360. /*
  361. * PACA ptr is r13:
  362. * raw_smp_processor_id() = local_paca->paca_index
  363. */
  364. BUILD_BUG_ON(FIELD_SIZEOF(struct paca_struct,
  365. paca_index) != 2);
  366. PPC_LHZ_OFFS(r_A, 13,
  367. offsetof(struct paca_struct, paca_index));
  368. #else
  369. PPC_LI(r_A, 0);
  370. #endif
  371. break;
  372. /*** Absolute loads from packet header/data ***/
  373. case BPF_S_LD_W_ABS:
  374. func = CHOOSE_LOAD_FUNC(K, sk_load_word);
  375. goto common_load;
  376. case BPF_S_LD_H_ABS:
  377. func = CHOOSE_LOAD_FUNC(K, sk_load_half);
  378. goto common_load;
  379. case BPF_S_LD_B_ABS:
  380. func = CHOOSE_LOAD_FUNC(K, sk_load_byte);
  381. common_load:
  382. /* Load from [K]. */
  383. ctx->seen |= SEEN_DATAREF;
  384. PPC_LI64(r_scratch1, func);
  385. PPC_MTLR(r_scratch1);
  386. PPC_LI32(r_addr, K);
  387. PPC_BLRL();
  388. /*
  389. * Helper returns 'lt' condition on error, and an
  390. * appropriate return value in r3
  391. */
  392. PPC_BCC(COND_LT, exit_addr);
  393. break;
  394. /*** Indirect loads from packet header/data ***/
  395. case BPF_S_LD_W_IND:
  396. func = sk_load_word;
  397. goto common_load_ind;
  398. case BPF_S_LD_H_IND:
  399. func = sk_load_half;
  400. goto common_load_ind;
  401. case BPF_S_LD_B_IND:
  402. func = sk_load_byte;
  403. common_load_ind:
  404. /*
  405. * Load from [X + K]. Negative offsets are tested for
  406. * in the helper functions.
  407. */
  408. ctx->seen |= SEEN_DATAREF | SEEN_XREG;
  409. PPC_LI64(r_scratch1, func);
  410. PPC_MTLR(r_scratch1);
  411. PPC_ADDI(r_addr, r_X, IMM_L(K));
  412. if (K >= 32768)
  413. PPC_ADDIS(r_addr, r_addr, IMM_HA(K));
  414. PPC_BLRL();
  415. /* If error, cr0.LT set */
  416. PPC_BCC(COND_LT, exit_addr);
  417. break;
  418. case BPF_S_LDX_B_MSH:
  419. func = CHOOSE_LOAD_FUNC(K, sk_load_byte_msh);
  420. goto common_load;
  421. break;
  422. /*** Jump and branches ***/
  423. case BPF_S_JMP_JA:
  424. if (K != 0)
  425. PPC_JMP(addrs[i + 1 + K]);
  426. break;
  427. case BPF_S_JMP_JGT_K:
  428. case BPF_S_JMP_JGT_X:
  429. true_cond = COND_GT;
  430. goto cond_branch;
  431. case BPF_S_JMP_JGE_K:
  432. case BPF_S_JMP_JGE_X:
  433. true_cond = COND_GE;
  434. goto cond_branch;
  435. case BPF_S_JMP_JEQ_K:
  436. case BPF_S_JMP_JEQ_X:
  437. true_cond = COND_EQ;
  438. goto cond_branch;
  439. case BPF_S_JMP_JSET_K:
  440. case BPF_S_JMP_JSET_X:
  441. true_cond = COND_NE;
  442. /* Fall through */
  443. cond_branch:
  444. /* same targets, can avoid doing the test :) */
  445. if (filter[i].jt == filter[i].jf) {
  446. if (filter[i].jt > 0)
  447. PPC_JMP(addrs[i + 1 + filter[i].jt]);
  448. break;
  449. }
  450. switch (filter[i].code) {
  451. case BPF_S_JMP_JGT_X:
  452. case BPF_S_JMP_JGE_X:
  453. case BPF_S_JMP_JEQ_X:
  454. ctx->seen |= SEEN_XREG;
  455. PPC_CMPLW(r_A, r_X);
  456. break;
  457. case BPF_S_JMP_JSET_X:
  458. ctx->seen |= SEEN_XREG;
  459. PPC_AND_DOT(r_scratch1, r_A, r_X);
  460. break;
  461. case BPF_S_JMP_JEQ_K:
  462. case BPF_S_JMP_JGT_K:
  463. case BPF_S_JMP_JGE_K:
  464. if (K < 32768)
  465. PPC_CMPLWI(r_A, K);
  466. else {
  467. PPC_LI32(r_scratch1, K);
  468. PPC_CMPLW(r_A, r_scratch1);
  469. }
  470. break;
  471. case BPF_S_JMP_JSET_K:
  472. if (K < 32768)
  473. /* PPC_ANDI is /only/ dot-form */
  474. PPC_ANDI(r_scratch1, r_A, K);
  475. else {
  476. PPC_LI32(r_scratch1, K);
  477. PPC_AND_DOT(r_scratch1, r_A,
  478. r_scratch1);
  479. }
  480. break;
  481. }
  482. /* Sometimes branches are constructed "backward", with
  483. * the false path being the branch and true path being
  484. * a fallthrough to the next instruction.
  485. */
  486. if (filter[i].jt == 0)
  487. /* Swap the sense of the branch */
  488. PPC_BCC(true_cond ^ COND_CMP_TRUE,
  489. addrs[i + 1 + filter[i].jf]);
  490. else {
  491. PPC_BCC(true_cond, addrs[i + 1 + filter[i].jt]);
  492. if (filter[i].jf != 0)
  493. PPC_JMP(addrs[i + 1 + filter[i].jf]);
  494. }
  495. break;
  496. default:
  497. /* The filter contains something cruel & unusual.
  498. * We don't handle it, but also there shouldn't be
  499. * anything missing from our list.
  500. */
  501. if (printk_ratelimit())
  502. pr_err("BPF filter opcode %04x (@%d) unsupported\n",
  503. filter[i].code, i);
  504. return -ENOTSUPP;
  505. }
  506. }
  507. /* Set end-of-body-code address for exit. */
  508. addrs[i] = ctx->idx * 4;
  509. return 0;
  510. }
  511. void bpf_jit_compile(struct sk_filter *fp)
  512. {
  513. unsigned int proglen;
  514. unsigned int alloclen;
  515. u32 *image = NULL;
  516. u32 *code_base;
  517. unsigned int *addrs;
  518. struct codegen_context cgctx;
  519. int pass;
  520. int flen = fp->len;
  521. if (!bpf_jit_enable)
  522. return;
  523. addrs = kzalloc((flen+1) * sizeof(*addrs), GFP_KERNEL);
  524. if (addrs == NULL)
  525. return;
  526. /*
  527. * There are multiple assembly passes as the generated code will change
  528. * size as it settles down, figuring out the max branch offsets/exit
  529. * paths required.
  530. *
  531. * The range of standard conditional branches is +/- 32Kbytes. Since
  532. * BPF_MAXINSNS = 4096, we can only jump from (worst case) start to
  533. * finish with 8 bytes/instruction. Not feasible, so long jumps are
  534. * used, distinct from short branches.
  535. *
  536. * Current:
  537. *
  538. * For now, both branch types assemble to 2 words (short branches padded
  539. * with a NOP); this is less efficient, but assembly will always complete
  540. * after exactly 3 passes:
  541. *
  542. * First pass: No code buffer; Program is "faux-generated" -- no code
  543. * emitted but maximum size of output determined (and addrs[] filled
  544. * in). Also, we note whether we use M[], whether we use skb data, etc.
  545. * All generation choices assumed to be 'worst-case', e.g. branches all
  546. * far (2 instructions), return path code reduction not available, etc.
  547. *
  548. * Second pass: Code buffer allocated with size determined previously.
  549. * Prologue generated to support features we have seen used. Exit paths
  550. * determined and addrs[] is filled in again, as code may be slightly
  551. * smaller as a result.
  552. *
  553. * Third pass: Code generated 'for real', and branch destinations
  554. * determined from now-accurate addrs[] map.
  555. *
  556. * Ideal:
  557. *
  558. * If we optimise this, near branches will be shorter. On the
  559. * first assembly pass, we should err on the side of caution and
  560. * generate the biggest code. On subsequent passes, branches will be
  561. * generated short or long and code size will reduce. With smaller
  562. * code, more branches may fall into the short category, and code will
  563. * reduce more.
  564. *
  565. * Finally, if we see one pass generate code the same size as the
  566. * previous pass we have converged and should now generate code for
  567. * real. Allocating at the end will also save the memory that would
  568. * otherwise be wasted by the (small) current code shrinkage.
  569. * Preferably, we should do a small number of passes (e.g. 5) and if we
  570. * haven't converged by then, get impatient and force code to generate
  571. * as-is, even if the odd branch would be left long. The chances of a
  572. * long jump are tiny with all but the most enormous of BPF filter
  573. * inputs, so we should usually converge on the third pass.
  574. */
  575. cgctx.idx = 0;
  576. cgctx.seen = 0;
  577. cgctx.pc_ret0 = -1;
  578. /* Scouting faux-generate pass 0 */
  579. if (bpf_jit_build_body(fp, 0, &cgctx, addrs))
  580. /* We hit something illegal or unsupported. */
  581. goto out;
  582. /*
  583. * Pretend to build prologue, given the features we've seen. This will
  584. * update ctgtx.idx as it pretends to output instructions, then we can
  585. * calculate total size from idx.
  586. */
  587. bpf_jit_build_prologue(fp, 0, &cgctx);
  588. bpf_jit_build_epilogue(0, &cgctx);
  589. proglen = cgctx.idx * 4;
  590. alloclen = proglen + FUNCTION_DESCR_SIZE;
  591. image = module_alloc(max_t(unsigned int, alloclen,
  592. sizeof(struct work_struct)));
  593. if (!image)
  594. goto out;
  595. code_base = image + (FUNCTION_DESCR_SIZE/4);
  596. /* Code generation passes 1-2 */
  597. for (pass = 1; pass < 3; pass++) {
  598. /* Now build the prologue, body code & epilogue for real. */
  599. cgctx.idx = 0;
  600. bpf_jit_build_prologue(fp, code_base, &cgctx);
  601. bpf_jit_build_body(fp, code_base, &cgctx, addrs);
  602. bpf_jit_build_epilogue(code_base, &cgctx);
  603. if (bpf_jit_enable > 1)
  604. pr_info("Pass %d: shrink = %d, seen = 0x%x\n", pass,
  605. proglen - (cgctx.idx * 4), cgctx.seen);
  606. }
  607. if (bpf_jit_enable > 1)
  608. pr_info("flen=%d proglen=%u pass=%d image=%p\n",
  609. flen, proglen, pass, image);
  610. if (image) {
  611. if (bpf_jit_enable > 1)
  612. print_hex_dump(KERN_ERR, "JIT code: ",
  613. DUMP_PREFIX_ADDRESS,
  614. 16, 1, code_base,
  615. proglen, false);
  616. bpf_flush_icache(code_base, code_base + (proglen/4));
  617. /* Function descriptor nastiness: Address + TOC */
  618. ((u64 *)image)[0] = (u64)code_base;
  619. ((u64 *)image)[1] = local_paca->kernel_toc;
  620. fp->bpf_func = (void *)image;
  621. }
  622. out:
  623. kfree(addrs);
  624. return;
  625. }
  626. static void jit_free_defer(struct work_struct *arg)
  627. {
  628. module_free(NULL, arg);
  629. }
  630. /* run from softirq, we must use a work_struct to call
  631. * module_free() from process context
  632. */
  633. void bpf_jit_free(struct sk_filter *fp)
  634. {
  635. if (fp->bpf_func != sk_run_filter) {
  636. struct work_struct *work = (struct work_struct *)fp->bpf_func;
  637. INIT_WORK(work, jit_free_defer);
  638. schedule_work(work);
  639. }
  640. }