bpf_jit_comp.c 18 KB

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