bpf_jit_comp.c 18 KB

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