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