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 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
