1 /*
2 * Copyright 2018, The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "apf_interpreter.h"
18
19 #include <string.h> // For memcmp
20
21 #include "apf.h"
22
23 // Return code indicating "packet" should accepted.
24 #define PASS_PACKET 1
25 // Return code indicating "packet" should be dropped.
26 #define DROP_PACKET 0
27 // Verify an internal condition and accept packet if it fails.
28 #define ASSERT_RETURN(c) if (!(c)) return PASS_PACKET
29 // If "c" is of an unsigned type, generate a compile warning that gets promoted to an error.
30 // This makes bounds checking simpler because ">= 0" can be avoided. Otherwise adding
31 // superfluous ">= 0" with unsigned expressions generates compile warnings.
32 #define ENFORCE_UNSIGNED(c) ((c)==(uint32_t)(c))
33
accept_packet(uint8_t * program,uint32_t program_len,uint32_t ram_len,const uint8_t * packet,uint32_t packet_len,uint32_t filter_age)34 int accept_packet(uint8_t* program, uint32_t program_len, uint32_t ram_len,
35 const uint8_t* packet, uint32_t packet_len,
36 uint32_t filter_age) {
37 // Is offset within program bounds?
38 #define IN_PROGRAM_BOUNDS(p) (ENFORCE_UNSIGNED(p) && (p) < program_len)
39 // Is offset within packet bounds?
40 #define IN_PACKET_BOUNDS(p) (ENFORCE_UNSIGNED(p) && (p) < packet_len)
41 // Is access to offset |p| length |size| within data bounds?
42 #define IN_DATA_BOUNDS(p, size) (ENFORCE_UNSIGNED(p) && \
43 ENFORCE_UNSIGNED(size) && \
44 (p) + (size) <= ram_len && \
45 (p) >= program_len && \
46 (p) + (size) >= (p)) // catch wraparounds
47 // Accept packet if not within program bounds
48 #define ASSERT_IN_PROGRAM_BOUNDS(p) ASSERT_RETURN(IN_PROGRAM_BOUNDS(p))
49 // Accept packet if not within packet bounds
50 #define ASSERT_IN_PACKET_BOUNDS(p) ASSERT_RETURN(IN_PACKET_BOUNDS(p))
51 // Accept packet if not within data bounds
52 #define ASSERT_IN_DATA_BOUNDS(p, size) ASSERT_RETURN(IN_DATA_BOUNDS(p, size))
53
54 // Program counter.
55 uint32_t pc = 0;
56 // Accept packet if not within program or not ahead of program counter
57 #define ASSERT_FORWARD_IN_PROGRAM(p) ASSERT_RETURN(IN_PROGRAM_BOUNDS(p) && (p) >= pc)
58 // Memory slot values.
59 uint32_t memory[MEMORY_ITEMS] = {};
60 // Fill in pre-filled memory slot values.
61 memory[MEMORY_OFFSET_PROGRAM_SIZE] = program_len;
62 memory[MEMORY_OFFSET_DATA_SIZE] = ram_len;
63 memory[MEMORY_OFFSET_PACKET_SIZE] = packet_len;
64 memory[MEMORY_OFFSET_FILTER_AGE] = filter_age;
65 ASSERT_IN_PACKET_BOUNDS(APF_FRAME_HEADER_SIZE);
66 // Only populate if IP version is IPv4.
67 if ((packet[APF_FRAME_HEADER_SIZE] & 0xf0) == 0x40) {
68 memory[MEMORY_OFFSET_IPV4_HEADER_SIZE] = (packet[APF_FRAME_HEADER_SIZE] & 15) * 4;
69 }
70 // Register values.
71 uint32_t registers[2] = {};
72 // Count of instructions remaining to execute. This is done to ensure an
73 // upper bound on execution time. It should never be hit and is only for
74 // safety. Initialize to the number of bytes in the program which is an
75 // upper bound on the number of instructions in the program.
76 uint32_t instructions_remaining = program_len;
77
78 do {
79 if (pc == program_len) {
80 return PASS_PACKET;
81 } else if (pc == (program_len + 1)) {
82 return DROP_PACKET;
83 }
84 ASSERT_IN_PROGRAM_BOUNDS(pc);
85 const uint8_t bytecode = program[pc++];
86 const uint32_t opcode = EXTRACT_OPCODE(bytecode);
87 const uint32_t reg_num = EXTRACT_REGISTER(bytecode);
88 #define REG (registers[reg_num])
89 #define OTHER_REG (registers[reg_num ^ 1])
90 // All instructions have immediate fields, so load them now.
91 const uint32_t len_field = EXTRACT_IMM_LENGTH(bytecode);
92 uint32_t imm = 0;
93 int32_t signed_imm = 0;
94 if (len_field != 0) {
95 const uint32_t imm_len = 1 << (len_field - 1);
96 ASSERT_FORWARD_IN_PROGRAM(pc + imm_len - 1);
97 uint32_t i;
98 for (i = 0; i < imm_len; i++)
99 imm = (imm << 8) | program[pc++];
100 // Sign extend imm into signed_imm.
101 signed_imm = imm << ((4 - imm_len) * 8);
102 signed_imm >>= (4 - imm_len) * 8;
103 }
104 switch (opcode) {
105 case LDB_OPCODE:
106 case LDH_OPCODE:
107 case LDW_OPCODE:
108 case LDBX_OPCODE:
109 case LDHX_OPCODE:
110 case LDWX_OPCODE: {
111 uint32_t offs = imm;
112 if (opcode >= LDBX_OPCODE) {
113 // Note: this can overflow and actually decrease offs.
114 offs += registers[1];
115 }
116 ASSERT_IN_PACKET_BOUNDS(offs);
117 uint32_t load_size;
118 switch (opcode) {
119 case LDB_OPCODE:
120 case LDBX_OPCODE:
121 load_size = 1;
122 break;
123 case LDH_OPCODE:
124 case LDHX_OPCODE:
125 load_size = 2;
126 break;
127 case LDW_OPCODE:
128 case LDWX_OPCODE:
129 load_size = 4;
130 break;
131 // Immediately enclosing switch statement guarantees
132 // opcode cannot be any other value.
133 }
134 const uint32_t end_offs = offs + (load_size - 1);
135 // Catch overflow/wrap-around.
136 ASSERT_RETURN(end_offs >= offs);
137 ASSERT_IN_PACKET_BOUNDS(end_offs);
138 uint32_t val = 0;
139 while (load_size--)
140 val = (val << 8) | packet[offs++];
141 REG = val;
142 break;
143 }
144 case JMP_OPCODE:
145 // This can jump backwards. Infinite looping prevented by instructions_remaining.
146 pc += imm;
147 break;
148 case JEQ_OPCODE:
149 case JNE_OPCODE:
150 case JGT_OPCODE:
151 case JLT_OPCODE:
152 case JSET_OPCODE:
153 case JNEBS_OPCODE: {
154 // Load second immediate field.
155 uint32_t cmp_imm = 0;
156 if (reg_num == 1) {
157 cmp_imm = registers[1];
158 } else if (len_field != 0) {
159 uint32_t cmp_imm_len = 1 << (len_field - 1);
160 ASSERT_FORWARD_IN_PROGRAM(pc + cmp_imm_len - 1);
161 uint32_t i;
162 for (i = 0; i < cmp_imm_len; i++)
163 cmp_imm = (cmp_imm << 8) | program[pc++];
164 }
165 switch (opcode) {
166 case JEQ_OPCODE:
167 if (registers[0] == cmp_imm)
168 pc += imm;
169 break;
170 case JNE_OPCODE:
171 if (registers[0] != cmp_imm)
172 pc += imm;
173 break;
174 case JGT_OPCODE:
175 if (registers[0] > cmp_imm)
176 pc += imm;
177 break;
178 case JLT_OPCODE:
179 if (registers[0] < cmp_imm)
180 pc += imm;
181 break;
182 case JSET_OPCODE:
183 if (registers[0] & cmp_imm)
184 pc += imm;
185 break;
186 case JNEBS_OPCODE: {
187 // cmp_imm is size in bytes of data to compare.
188 // pc is offset of program bytes to compare.
189 // imm is jump target offset.
190 // REG is offset of packet bytes to compare.
191 ASSERT_FORWARD_IN_PROGRAM(pc + cmp_imm - 1);
192 ASSERT_IN_PACKET_BOUNDS(REG);
193 const uint32_t last_packet_offs = REG + cmp_imm - 1;
194 ASSERT_RETURN(last_packet_offs >= REG);
195 ASSERT_IN_PACKET_BOUNDS(last_packet_offs);
196 if (memcmp(program + pc, packet + REG, cmp_imm))
197 pc += imm;
198 // skip past comparison bytes
199 pc += cmp_imm;
200 break;
201 }
202 }
203 break;
204 }
205 case ADD_OPCODE:
206 registers[0] += reg_num ? registers[1] : imm;
207 break;
208 case MUL_OPCODE:
209 registers[0] *= reg_num ? registers[1] : imm;
210 break;
211 case DIV_OPCODE: {
212 const uint32_t div_operand = reg_num ? registers[1] : imm;
213 ASSERT_RETURN(div_operand);
214 registers[0] /= div_operand;
215 break;
216 }
217 case AND_OPCODE:
218 registers[0] &= reg_num ? registers[1] : imm;
219 break;
220 case OR_OPCODE:
221 registers[0] |= reg_num ? registers[1] : imm;
222 break;
223 case SH_OPCODE: {
224 const int32_t shift_val = reg_num ? (int32_t)registers[1] : signed_imm;
225 if (shift_val > 0)
226 registers[0] <<= shift_val;
227 else
228 registers[0] >>= -shift_val;
229 break;
230 }
231 case LI_OPCODE:
232 REG = signed_imm;
233 break;
234 case EXT_OPCODE:
235 if (
236 // If LDM_EXT_OPCODE is 0 and imm is compared with it, a compiler error will result,
237 // instead just enforce that imm is unsigned (so it's always greater or equal to 0).
238 #if LDM_EXT_OPCODE == 0
239 ENFORCE_UNSIGNED(imm) &&
240 #else
241 imm >= LDM_EXT_OPCODE &&
242 #endif
243 imm < (LDM_EXT_OPCODE + MEMORY_ITEMS)) {
244 REG = memory[imm - LDM_EXT_OPCODE];
245 } else if (imm >= STM_EXT_OPCODE && imm < (STM_EXT_OPCODE + MEMORY_ITEMS)) {
246 memory[imm - STM_EXT_OPCODE] = REG;
247 } else switch (imm) {
248 case NOT_EXT_OPCODE:
249 REG = ~REG;
250 break;
251 case NEG_EXT_OPCODE:
252 REG = -REG;
253 break;
254 case SWAP_EXT_OPCODE: {
255 uint32_t tmp = REG;
256 REG = OTHER_REG;
257 OTHER_REG = tmp;
258 break;
259 }
260 case MOV_EXT_OPCODE:
261 REG = OTHER_REG;
262 break;
263 // Unknown extended opcode
264 default:
265 // Bail out
266 return PASS_PACKET;
267 }
268 break;
269 case LDDW_OPCODE: {
270 uint32_t offs = OTHER_REG + signed_imm;
271 uint32_t size = 4;
272 uint32_t val = 0;
273 // Negative offsets wrap around the end of the address space.
274 // This allows us to efficiently access the end of the
275 // address space with one-byte immediates without using %=.
276 if (offs & 0x80000000) {
277 offs = ram_len + offs; // unsigned overflow intended
278 }
279 ASSERT_IN_DATA_BOUNDS(offs, size);
280 while (size--)
281 val = (val << 8) | program[offs++];
282 REG = val;
283 break;
284 }
285 case STDW_OPCODE: {
286 uint32_t offs = OTHER_REG + signed_imm;
287 uint32_t size = 4;
288 uint32_t val = REG;
289 // Negative offsets wrap around the end of the address space.
290 // This allows us to efficiently access the end of the
291 // address space with one-byte immediates without using %=.
292 if (offs & 0x80000000) {
293 offs = ram_len + offs; // unsigned overflow intended
294 }
295 ASSERT_IN_DATA_BOUNDS(offs, size);
296 while (size--) {
297 program[offs++] = (val >> 24);
298 val <<= 8;
299 }
300 break;
301 }
302 // Unknown opcode
303 default:
304 // Bail out
305 return PASS_PACKET;
306 }
307 } while (instructions_remaining--);
308 return PASS_PACKET;
309 }
310