bpf_jit_comp.c 18 KB

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