ApfGenerator.java revision deb145d2334635dc15781415603ff3a8559e7c49
1/* 2 * Copyright (C) 2016 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 17package android.net.apf; 18 19import java.util.ArrayList; 20import java.util.HashMap; 21 22/** 23 * APF assembler/generator. A tool for generating an APF program. 24 * 25 * Call add*() functions to add instructions to the program, then call 26 * {@link generate} to get the APF bytecode for the program. 27 * 28 * @hide 29 */ 30public class ApfGenerator { 31 /** 32 * This exception is thrown when an attempt is made to generate an illegal instruction. 33 */ 34 public static class IllegalInstructionException extends Exception { 35 IllegalInstructionException(String msg) { 36 super(msg); 37 } 38 } 39 private enum Opcodes { 40 LABEL(-1), 41 LDB(1), // Load 1 byte from immediate offset, e.g. "ldb R0, [5]" 42 LDH(2), // Load 2 bytes from immediate offset, e.g. "ldh R0, [5]" 43 LDW(3), // Load 4 bytes from immediate offset, e.g. "ldw R0, [5]" 44 LDBX(4), // Load 1 byte from immediate offset plus register, e.g. "ldbx R0, [5]R0" 45 LDHX(5), // Load 2 byte from immediate offset plus register, e.g. "ldhx R0, [5]R0" 46 LDWX(6), // Load 4 byte from immediate offset plus register, e.g. "ldwx R0, [5]R0" 47 ADD(7), // Add, e.g. "add R0,5" 48 MUL(8), // Multiply, e.g. "mul R0,5" 49 DIV(9), // Divide, e.g. "div R0,5" 50 AND(10), // And, e.g. "and R0,5" 51 OR(11), // Or, e.g. "or R0,5" 52 SH(12), // Left shift, e.g, "sh R0, 5" or "sh R0, -5" (shifts right) 53 LI(13), // Load immediate, e.g. "li R0,5" (immediate encoded as signed value) 54 JMP(14), // Jump, e.g. "jmp label" 55 JEQ(15), // Compare equal and branch, e.g. "jeq R0,5,label" 56 JNE(16), // Compare not equal and branch, e.g. "jne R0,5,label" 57 JGT(17), // Compare greater than and branch, e.g. "jgt R0,5,label" 58 JLT(18), // Compare less than and branch, e.g. "jlt R0,5,label" 59 JSET(19), // Compare any bits set and branch, e.g. "jset R0,5,label" 60 JNEBS(20), // Compare not equal byte sequence, e.g. "jnebs R0,5,label,0x1122334455" 61 EXT(21), // Followed by immediate indicating ExtendedOpcodes. 62 LDDW(22), // Load 4 bytes from data memory address (register + immediate): "lddw R0, [5]R1" 63 STDW(23); // Store 4 bytes to data memory address (register + immediate): "stdw R0, [5]R1" 64 65 final int value; 66 67 private Opcodes(int value) { 68 this.value = value; 69 } 70 } 71 // Extended opcodes. Primary opcode is Opcodes.EXT. ExtendedOpcodes are encoded in the immediate 72 // field. 73 private enum ExtendedOpcodes { 74 LDM(0), // Load from memory, e.g. "ldm R0,5" 75 STM(16), // Store to memory, e.g. "stm R0,5" 76 NOT(32), // Not, e.g. "not R0" 77 NEG(33), // Negate, e.g. "neg R0" 78 SWAP(34), // Swap, e.g. "swap R0,R1" 79 MOVE(35); // Move, e.g. "move R0,R1" 80 81 final int value; 82 83 private ExtendedOpcodes(int value) { 84 this.value = value; 85 } 86 } 87 public enum Register { 88 R0(0), 89 R1(1); 90 91 final int value; 92 93 private Register(int value) { 94 this.value = value; 95 } 96 } 97 private class Instruction { 98 private final byte mOpcode; // A "Opcode" value. 99 private final byte mRegister; // A "Register" value. 100 private boolean mHasImm; 101 private byte mImmSize; 102 private boolean mImmSigned; 103 private int mImm; 104 // When mOpcode is a jump: 105 private byte mTargetLabelSize; 106 private String mTargetLabel; 107 // When mOpcode == Opcodes.LABEL: 108 private String mLabel; 109 // When mOpcode == Opcodes.JNEBS: 110 private byte[] mCompareBytes; 111 // Offset in bytes from the begining of this program. Set by {@link ApfGenerator#generate}. 112 int offset; 113 114 Instruction(Opcodes opcode, Register register) { 115 mOpcode = (byte)opcode.value; 116 mRegister = (byte)register.value; 117 } 118 119 Instruction(Opcodes opcode) { 120 this(opcode, Register.R0); 121 } 122 123 void setImm(int imm, boolean signed) { 124 mHasImm = true; 125 mImm = imm; 126 mImmSigned = signed; 127 mImmSize = calculateImmSize(imm, signed); 128 } 129 130 void setUnsignedImm(int imm) { 131 setImm(imm, false); 132 } 133 134 void setSignedImm(int imm) { 135 setImm(imm, true); 136 } 137 138 void setLabel(String label) throws IllegalInstructionException { 139 if (mLabels.containsKey(label)) { 140 throw new IllegalInstructionException("duplicate label " + label); 141 } 142 if (mOpcode != Opcodes.LABEL.value) { 143 throw new IllegalStateException("adding label to non-label instruction"); 144 } 145 mLabel = label; 146 mLabels.put(label, this); 147 } 148 149 void setTargetLabel(String label) { 150 mTargetLabel = label; 151 mTargetLabelSize = 4; // May shrink later on in generate(). 152 } 153 154 void setCompareBytes(byte[] bytes) { 155 if (mOpcode != Opcodes.JNEBS.value) { 156 throw new IllegalStateException("adding compare bytes to non-JNEBS instruction"); 157 } 158 mCompareBytes = bytes; 159 } 160 161 /** 162 * @return size of instruction in bytes. 163 */ 164 int size() { 165 if (mOpcode == Opcodes.LABEL.value) { 166 return 0; 167 } 168 int size = 1; 169 if (mHasImm) { 170 size += generatedImmSize(); 171 } 172 if (mTargetLabel != null) { 173 size += generatedImmSize(); 174 } 175 if (mCompareBytes != null) { 176 size += mCompareBytes.length; 177 } 178 return size; 179 } 180 181 /** 182 * Resize immediate value field so that it's only as big as required to 183 * contain the offset of the jump destination. 184 * @return {@code true} if shrunk. 185 */ 186 boolean shrink() throws IllegalInstructionException { 187 if (mTargetLabel == null) { 188 return false; 189 } 190 int oldSize = size(); 191 int oldTargetLabelSize = mTargetLabelSize; 192 mTargetLabelSize = calculateImmSize(calculateTargetLabelOffset(), false); 193 if (mTargetLabelSize > oldTargetLabelSize) { 194 throw new IllegalStateException("instruction grew"); 195 } 196 return size() < oldSize; 197 } 198 199 /** 200 * Assemble value for instruction size field. 201 */ 202 private byte generateImmSizeField() { 203 byte immSize = generatedImmSize(); 204 // Encode size field to fit in 2 bits: 0->0, 1->1, 2->2, 3->4. 205 return immSize == 4 ? 3 : immSize; 206 } 207 208 /** 209 * Assemble first byte of generated instruction. 210 */ 211 private byte generateInstructionByte() { 212 byte sizeField = generateImmSizeField(); 213 return (byte)((mOpcode << 3) | (sizeField << 1) | mRegister); 214 } 215 216 /** 217 * Write {@code value} at offset {@code writingOffset} into {@code bytecode}. 218 * {@link generatedImmSize} bytes are written. {@code value} is truncated to 219 * {@code generatedImmSize} bytes. {@code value} is treated simply as a 220 * 32-bit value, so unsigned values should be zero extended and the truncation 221 * should simply throw away their zero-ed upper bits, and signed values should 222 * be sign extended and the truncation should simply throw away their signed 223 * upper bits. 224 */ 225 private int writeValue(int value, byte[] bytecode, int writingOffset) { 226 for (int i = generatedImmSize() - 1; i >= 0; i--) { 227 bytecode[writingOffset++] = (byte)((value >> (i * 8)) & 255); 228 } 229 return writingOffset; 230 } 231 232 /** 233 * Generate bytecode for this instruction at offset {@link offset}. 234 */ 235 void generate(byte[] bytecode) throws IllegalInstructionException { 236 if (mOpcode == Opcodes.LABEL.value) { 237 return; 238 } 239 int writingOffset = offset; 240 bytecode[writingOffset++] = generateInstructionByte(); 241 if (mTargetLabel != null) { 242 writingOffset = writeValue(calculateTargetLabelOffset(), bytecode, writingOffset); 243 } 244 if (mHasImm) { 245 writingOffset = writeValue(mImm, bytecode, writingOffset); 246 } 247 if (mCompareBytes != null) { 248 System.arraycopy(mCompareBytes, 0, bytecode, writingOffset, mCompareBytes.length); 249 writingOffset += mCompareBytes.length; 250 } 251 if ((writingOffset - offset) != size()) { 252 throw new IllegalStateException("wrote " + (writingOffset - offset) + 253 " but should have written " + size()); 254 } 255 } 256 257 /** 258 * Calculate the size of either the immediate field or the target label field, if either is 259 * present. Most instructions have either an immediate or a target label field, but for the 260 * instructions that have both, the size of the target label field must be the same as the 261 * size of the immediate field, because there is only one length field in the instruction 262 * byte, hence why this function simply takes the maximum of the two sizes, so neither is 263 * truncated. 264 */ 265 private byte generatedImmSize() { 266 return mImmSize > mTargetLabelSize ? mImmSize : mTargetLabelSize; 267 } 268 269 private int calculateTargetLabelOffset() throws IllegalInstructionException { 270 Instruction targetLabelInstruction; 271 if (mTargetLabel == DROP_LABEL) { 272 targetLabelInstruction = mDropLabel; 273 } else if (mTargetLabel == PASS_LABEL) { 274 targetLabelInstruction = mPassLabel; 275 } else { 276 targetLabelInstruction = mLabels.get(mTargetLabel); 277 } 278 if (targetLabelInstruction == null) { 279 throw new IllegalInstructionException("label not found: " + mTargetLabel); 280 } 281 // Calculate distance from end of this instruction to instruction.offset. 282 final int targetLabelOffset = targetLabelInstruction.offset - (offset + size()); 283 if (targetLabelOffset < 0) { 284 throw new IllegalInstructionException("backward branches disallowed; label: " + 285 mTargetLabel); 286 } 287 return targetLabelOffset; 288 } 289 290 private byte calculateImmSize(int imm, boolean signed) { 291 if (imm == 0) { 292 return 0; 293 } 294 if (signed && (imm >= -128 && imm <= 127) || 295 !signed && (imm >= 0 && imm <= 255)) { 296 return 1; 297 } 298 if (signed && (imm >= -32768 && imm <= 32767) || 299 !signed && (imm >= 0 && imm <= 65535)) { 300 return 2; 301 } 302 return 4; 303 } 304 } 305 306 /** 307 * Jump to this label to terminate the program and indicate the packet 308 * should be dropped. 309 */ 310 public static final String DROP_LABEL = "__DROP__"; 311 312 /** 313 * Jump to this label to terminate the program and indicate the packet 314 * should be passed to the AP. 315 */ 316 public static final String PASS_LABEL = "__PASS__"; 317 318 /** 319 * Number of memory slots available for access via APF stores to memory and loads from memory. 320 * The memory slots are numbered 0 to {@code MEMORY_SLOTS} - 1. This must be kept in sync with 321 * the APF interpreter. 322 */ 323 public static final int MEMORY_SLOTS = 16; 324 325 /** 326 * Memory slot number that is prefilled with the IPv4 header length. 327 * Note that this memory slot may be overwritten by a program that 328 * executes stores to this memory slot. This must be kept in sync with 329 * the APF interpreter. 330 */ 331 public static final int IPV4_HEADER_SIZE_MEMORY_SLOT = 13; 332 333 /** 334 * Memory slot number that is prefilled with the size of the packet being filtered in bytes. 335 * Note that this memory slot may be overwritten by a program that 336 * executes stores to this memory slot. This must be kept in sync with the APF interpreter. 337 */ 338 public static final int PACKET_SIZE_MEMORY_SLOT = 14; 339 340 /** 341 * Memory slot number that is prefilled with the age of the filter in seconds. The age of the 342 * filter is the time since the filter was installed until now. 343 * Note that this memory slot may be overwritten by a program that 344 * executes stores to this memory slot. This must be kept in sync with the APF interpreter. 345 */ 346 public static final int FILTER_AGE_MEMORY_SLOT = 15; 347 348 /** 349 * First memory slot containing prefilled values. Can be used in range comparisons to determine 350 * if memory slot index is within prefilled slots. 351 */ 352 public static final int FIRST_PREFILLED_MEMORY_SLOT = IPV4_HEADER_SIZE_MEMORY_SLOT; 353 354 /** 355 * Last memory slot containing prefilled values. Can be used in range comparisons to determine 356 * if memory slot index is within prefilled slots. 357 */ 358 public static final int LAST_PREFILLED_MEMORY_SLOT = FILTER_AGE_MEMORY_SLOT; 359 360 // This version number syncs up with APF_VERSION in hardware/google/apf/apf_interpreter.h 361 private static final int MIN_APF_VERSION = 2; 362 363 private final ArrayList<Instruction> mInstructions = new ArrayList<Instruction>(); 364 private final HashMap<String, Instruction> mLabels = new HashMap<String, Instruction>(); 365 private final Instruction mDropLabel = new Instruction(Opcodes.LABEL); 366 private final Instruction mPassLabel = new Instruction(Opcodes.LABEL); 367 private final int mVersion; 368 private boolean mGenerated; 369 370 /** 371 * Creates an ApfGenerator instance which is able to emit instructions for the specified 372 * {@code version} of the APF interpreter. Throws {@code IllegalInstructionException} if 373 * the requested version is unsupported. 374 */ 375 ApfGenerator(int version) throws IllegalInstructionException { 376 mVersion = version; 377 requireApfVersion(MIN_APF_VERSION); 378 } 379 380 /** 381 * Returns true if the specified {@code version} is supported by the ApfGenerator, otherwise 382 * false. 383 */ 384 public static boolean supportsVersion(int version) { 385 return version >= MIN_APF_VERSION; 386 } 387 388 private void requireApfVersion(int minimumVersion) throws IllegalInstructionException { 389 if (mVersion < minimumVersion) { 390 throw new IllegalInstructionException("Requires APF >= " + minimumVersion); 391 } 392 } 393 394 private void addInstruction(Instruction instruction) { 395 if (mGenerated) { 396 throw new IllegalStateException("Program already generated"); 397 } 398 mInstructions.add(instruction); 399 } 400 401 /** 402 * Define a label at the current end of the program. Jumps can jump to this label. Labels are 403 * their own separate instructions, though with size 0. This facilitates having labels with 404 * no corresponding code to execute, for example a label at the end of a program. For example 405 * an {@link ApfGenerator} might be passed to a function that adds a filter like so: 406 * <pre> 407 * load from packet 408 * compare loaded data, jump if not equal to "next_filter" 409 * load from packet 410 * compare loaded data, jump if not equal to "next_filter" 411 * jump to drop label 412 * define "next_filter" here 413 * </pre> 414 * In this case "next_filter" may not have any generated code associated with it. 415 */ 416 public ApfGenerator defineLabel(String name) throws IllegalInstructionException { 417 Instruction instruction = new Instruction(Opcodes.LABEL); 418 instruction.setLabel(name); 419 addInstruction(instruction); 420 return this; 421 } 422 423 /** 424 * Add an unconditional jump instruction to the end of the program. 425 */ 426 public ApfGenerator addJump(String target) { 427 Instruction instruction = new Instruction(Opcodes.JMP); 428 instruction.setTargetLabel(target); 429 addInstruction(instruction); 430 return this; 431 } 432 433 /** 434 * Add an instruction to the end of the program to load the byte at offset {@code offset} 435 * bytes from the begining of the packet into {@code register}. 436 */ 437 public ApfGenerator addLoad8(Register register, int offset) { 438 Instruction instruction = new Instruction(Opcodes.LDB, register); 439 instruction.setUnsignedImm(offset); 440 addInstruction(instruction); 441 return this; 442 } 443 444 /** 445 * Add an instruction to the end of the program to load 16-bits at offset {@code offset} 446 * bytes from the begining of the packet into {@code register}. 447 */ 448 public ApfGenerator addLoad16(Register register, int offset) { 449 Instruction instruction = new Instruction(Opcodes.LDH, register); 450 instruction.setUnsignedImm(offset); 451 addInstruction(instruction); 452 return this; 453 } 454 455 /** 456 * Add an instruction to the end of the program to load 32-bits at offset {@code offset} 457 * bytes from the begining of the packet into {@code register}. 458 */ 459 public ApfGenerator addLoad32(Register register, int offset) { 460 Instruction instruction = new Instruction(Opcodes.LDW, register); 461 instruction.setUnsignedImm(offset); 462 addInstruction(instruction); 463 return this; 464 } 465 466 /** 467 * Add an instruction to the end of the program to load a byte from the packet into 468 * {@code register}. The offset of the loaded byte from the begining of the packet is 469 * the sum of {@code offset} and the value in register R1. 470 */ 471 public ApfGenerator addLoad8Indexed(Register register, int offset) { 472 Instruction instruction = new Instruction(Opcodes.LDBX, register); 473 instruction.setUnsignedImm(offset); 474 addInstruction(instruction); 475 return this; 476 } 477 478 /** 479 * Add an instruction to the end of the program to load 16-bits from the packet into 480 * {@code register}. The offset of the loaded 16-bits from the begining of the packet is 481 * the sum of {@code offset} and the value in register R1. 482 */ 483 public ApfGenerator addLoad16Indexed(Register register, int offset) { 484 Instruction instruction = new Instruction(Opcodes.LDHX, register); 485 instruction.setUnsignedImm(offset); 486 addInstruction(instruction); 487 return this; 488 } 489 490 /** 491 * Add an instruction to the end of the program to load 32-bits from the packet into 492 * {@code register}. The offset of the loaded 32-bits from the begining of the packet is 493 * the sum of {@code offset} and the value in register R1. 494 */ 495 public ApfGenerator addLoad32Indexed(Register register, int offset) { 496 Instruction instruction = new Instruction(Opcodes.LDWX, register); 497 instruction.setUnsignedImm(offset); 498 addInstruction(instruction); 499 return this; 500 } 501 502 /** 503 * Add an instruction to the end of the program to add {@code value} to register R0. 504 */ 505 public ApfGenerator addAdd(int value) { 506 Instruction instruction = new Instruction(Opcodes.ADD); 507 instruction.setSignedImm(value); 508 addInstruction(instruction); 509 return this; 510 } 511 512 /** 513 * Add an instruction to the end of the program to multiply register R0 by {@code value}. 514 */ 515 public ApfGenerator addMul(int value) { 516 Instruction instruction = new Instruction(Opcodes.MUL); 517 instruction.setSignedImm(value); 518 addInstruction(instruction); 519 return this; 520 } 521 522 /** 523 * Add an instruction to the end of the program to divide register R0 by {@code value}. 524 */ 525 public ApfGenerator addDiv(int value) { 526 Instruction instruction = new Instruction(Opcodes.DIV); 527 instruction.setSignedImm(value); 528 addInstruction(instruction); 529 return this; 530 } 531 532 /** 533 * Add an instruction to the end of the program to logically and register R0 with {@code value}. 534 */ 535 public ApfGenerator addAnd(int value) { 536 Instruction instruction = new Instruction(Opcodes.AND); 537 instruction.setUnsignedImm(value); 538 addInstruction(instruction); 539 return this; 540 } 541 542 /** 543 * Add an instruction to the end of the program to logically or register R0 with {@code value}. 544 */ 545 public ApfGenerator addOr(int value) { 546 Instruction instruction = new Instruction(Opcodes.OR); 547 instruction.setUnsignedImm(value); 548 addInstruction(instruction); 549 return this; 550 } 551 552 /** 553 * Add an instruction to the end of the program to shift left register R0 by {@code value} bits. 554 */ 555 public ApfGenerator addLeftShift(int value) { 556 Instruction instruction = new Instruction(Opcodes.SH); 557 instruction.setSignedImm(value); 558 addInstruction(instruction); 559 return this; 560 } 561 562 /** 563 * Add an instruction to the end of the program to shift right register R0 by {@code value} 564 * bits. 565 */ 566 public ApfGenerator addRightShift(int value) { 567 Instruction instruction = new Instruction(Opcodes.SH); 568 instruction.setSignedImm(-value); 569 addInstruction(instruction); 570 return this; 571 } 572 573 /** 574 * Add an instruction to the end of the program to add register R1 to register R0. 575 */ 576 public ApfGenerator addAddR1() { 577 Instruction instruction = new Instruction(Opcodes.ADD, Register.R1); 578 addInstruction(instruction); 579 return this; 580 } 581 582 /** 583 * Add an instruction to the end of the program to multiply register R0 by register R1. 584 */ 585 public ApfGenerator addMulR1() { 586 Instruction instruction = new Instruction(Opcodes.MUL, Register.R1); 587 addInstruction(instruction); 588 return this; 589 } 590 591 /** 592 * Add an instruction to the end of the program to divide register R0 by register R1. 593 */ 594 public ApfGenerator addDivR1() { 595 Instruction instruction = new Instruction(Opcodes.DIV, Register.R1); 596 addInstruction(instruction); 597 return this; 598 } 599 600 /** 601 * Add an instruction to the end of the program to logically and register R0 with register R1 602 * and store the result back into register R0. 603 */ 604 public ApfGenerator addAndR1() { 605 Instruction instruction = new Instruction(Opcodes.AND, Register.R1); 606 addInstruction(instruction); 607 return this; 608 } 609 610 /** 611 * Add an instruction to the end of the program to logically or register R0 with register R1 612 * and store the result back into register R0. 613 */ 614 public ApfGenerator addOrR1() { 615 Instruction instruction = new Instruction(Opcodes.OR, Register.R1); 616 addInstruction(instruction); 617 return this; 618 } 619 620 /** 621 * Add an instruction to the end of the program to shift register R0 left by the value in 622 * register R1. 623 */ 624 public ApfGenerator addLeftShiftR1() { 625 Instruction instruction = new Instruction(Opcodes.SH, Register.R1); 626 addInstruction(instruction); 627 return this; 628 } 629 630 /** 631 * Add an instruction to the end of the program to move {@code value} into {@code register}. 632 */ 633 public ApfGenerator addLoadImmediate(Register register, int value) { 634 Instruction instruction = new Instruction(Opcodes.LI, register); 635 instruction.setSignedImm(value); 636 addInstruction(instruction); 637 return this; 638 } 639 640 /** 641 * Add an instruction to the end of the program to jump to {@code target} if register R0's 642 * value equals {@code value}. 643 */ 644 public ApfGenerator addJumpIfR0Equals(int value, String target) { 645 Instruction instruction = new Instruction(Opcodes.JEQ); 646 instruction.setUnsignedImm(value); 647 instruction.setTargetLabel(target); 648 addInstruction(instruction); 649 return this; 650 } 651 652 /** 653 * Add an instruction to the end of the program to jump to {@code target} if register R0's 654 * value does not equal {@code value}. 655 */ 656 public ApfGenerator addJumpIfR0NotEquals(int value, String target) { 657 Instruction instruction = new Instruction(Opcodes.JNE); 658 instruction.setUnsignedImm(value); 659 instruction.setTargetLabel(target); 660 addInstruction(instruction); 661 return this; 662 } 663 664 /** 665 * Add an instruction to the end of the program to jump to {@code target} if register R0's 666 * value is greater than {@code value}. 667 */ 668 public ApfGenerator addJumpIfR0GreaterThan(int value, String target) { 669 Instruction instruction = new Instruction(Opcodes.JGT); 670 instruction.setUnsignedImm(value); 671 instruction.setTargetLabel(target); 672 addInstruction(instruction); 673 return this; 674 } 675 676 /** 677 * Add an instruction to the end of the program to jump to {@code target} if register R0's 678 * value is less than {@code value}. 679 */ 680 public ApfGenerator addJumpIfR0LessThan(int value, String target) { 681 Instruction instruction = new Instruction(Opcodes.JLT); 682 instruction.setUnsignedImm(value); 683 instruction.setTargetLabel(target); 684 addInstruction(instruction); 685 return this; 686 } 687 688 /** 689 * Add an instruction to the end of the program to jump to {@code target} if register R0's 690 * value has any bits set that are also set in {@code value}. 691 */ 692 public ApfGenerator addJumpIfR0AnyBitsSet(int value, String target) { 693 Instruction instruction = new Instruction(Opcodes.JSET); 694 instruction.setUnsignedImm(value); 695 instruction.setTargetLabel(target); 696 addInstruction(instruction); 697 return this; 698 } 699 /** 700 * Add an instruction to the end of the program to jump to {@code target} if register R0's 701 * value equals register R1's value. 702 */ 703 public ApfGenerator addJumpIfR0EqualsR1(String target) { 704 Instruction instruction = new Instruction(Opcodes.JEQ, Register.R1); 705 instruction.setTargetLabel(target); 706 addInstruction(instruction); 707 return this; 708 } 709 710 /** 711 * Add an instruction to the end of the program to jump to {@code target} if register R0's 712 * value does not equal register R1's value. 713 */ 714 public ApfGenerator addJumpIfR0NotEqualsR1(String target) { 715 Instruction instruction = new Instruction(Opcodes.JNE, Register.R1); 716 instruction.setTargetLabel(target); 717 addInstruction(instruction); 718 return this; 719 } 720 721 /** 722 * Add an instruction to the end of the program to jump to {@code target} if register R0's 723 * value is greater than register R1's value. 724 */ 725 public ApfGenerator addJumpIfR0GreaterThanR1(String target) { 726 Instruction instruction = new Instruction(Opcodes.JGT, Register.R1); 727 instruction.setTargetLabel(target); 728 addInstruction(instruction); 729 return this; 730 } 731 732 /** 733 * Add an instruction to the end of the program to jump to {@code target} if register R0's 734 * value is less than register R1's value. 735 */ 736 public ApfGenerator addJumpIfR0LessThanR1(String target) { 737 Instruction instruction = new Instruction(Opcodes.JLT, Register.R1); 738 instruction.setTargetLabel(target); 739 addInstruction(instruction); 740 return this; 741 } 742 743 /** 744 * Add an instruction to the end of the program to jump to {@code target} if register R0's 745 * value has any bits set that are also set in R1's value. 746 */ 747 public ApfGenerator addJumpIfR0AnyBitsSetR1(String target) { 748 Instruction instruction = new Instruction(Opcodes.JSET, Register.R1); 749 instruction.setTargetLabel(target); 750 addInstruction(instruction); 751 return this; 752 } 753 754 /** 755 * Add an instruction to the end of the program to jump to {@code target} if the bytes of the 756 * packet at, an offset specified by {@code register}, match {@code bytes}. 757 */ 758 public ApfGenerator addJumpIfBytesNotEqual(Register register, byte[] bytes, String target) 759 throws IllegalInstructionException { 760 if (register == Register.R1) { 761 throw new IllegalInstructionException("JNEBS fails with R1"); 762 } 763 Instruction instruction = new Instruction(Opcodes.JNEBS, register); 764 instruction.setUnsignedImm(bytes.length); 765 instruction.setTargetLabel(target); 766 instruction.setCompareBytes(bytes); 767 addInstruction(instruction); 768 return this; 769 } 770 771 /** 772 * Add an instruction to the end of the program to load memory slot {@code slot} into 773 * {@code register}. 774 */ 775 public ApfGenerator addLoadFromMemory(Register register, int slot) 776 throws IllegalInstructionException { 777 if (slot < 0 || slot > (MEMORY_SLOTS - 1)) { 778 throw new IllegalInstructionException("illegal memory slot number: " + slot); 779 } 780 Instruction instruction = new Instruction(Opcodes.EXT, register); 781 instruction.setUnsignedImm(ExtendedOpcodes.LDM.value + slot); 782 addInstruction(instruction); 783 return this; 784 } 785 786 /** 787 * Add an instruction to the end of the program to store {@code register} into memory slot 788 * {@code slot}. 789 */ 790 public ApfGenerator addStoreToMemory(Register register, int slot) 791 throws IllegalInstructionException { 792 if (slot < 0 || slot > (MEMORY_SLOTS - 1)) { 793 throw new IllegalInstructionException("illegal memory slot number: " + slot); 794 } 795 Instruction instruction = new Instruction(Opcodes.EXT, register); 796 instruction.setUnsignedImm(ExtendedOpcodes.STM.value + slot); 797 addInstruction(instruction); 798 return this; 799 } 800 801 /** 802 * Add an instruction to the end of the program to logically not {@code register}. 803 */ 804 public ApfGenerator addNot(Register register) { 805 Instruction instruction = new Instruction(Opcodes.EXT, register); 806 instruction.setUnsignedImm(ExtendedOpcodes.NOT.value); 807 addInstruction(instruction); 808 return this; 809 } 810 811 /** 812 * Add an instruction to the end of the program to negate {@code register}. 813 */ 814 public ApfGenerator addNeg(Register register) { 815 Instruction instruction = new Instruction(Opcodes.EXT, register); 816 instruction.setUnsignedImm(ExtendedOpcodes.NEG.value); 817 addInstruction(instruction); 818 return this; 819 } 820 821 /** 822 * Add an instruction to swap the values in register R0 and register R1. 823 */ 824 public ApfGenerator addSwap() { 825 Instruction instruction = new Instruction(Opcodes.EXT); 826 instruction.setUnsignedImm(ExtendedOpcodes.SWAP.value); 827 addInstruction(instruction); 828 return this; 829 } 830 831 /** 832 * Add an instruction to the end of the program to move the value into 833 * {@code register} from the other register. 834 */ 835 public ApfGenerator addMove(Register register) { 836 Instruction instruction = new Instruction(Opcodes.EXT, register); 837 instruction.setUnsignedImm(ExtendedOpcodes.MOVE.value); 838 addInstruction(instruction); 839 return this; 840 } 841 842 /** 843 * Add an instruction to the end of the program to load 32 bits from the data memory into 844 * {@code register}. The source address is computed by adding the signed immediate 845 * @{code offset} to the other register. 846 * Requires APF v3 or greater. 847 */ 848 public ApfGenerator addLoadData(Register destinationRegister, int offset) 849 throws IllegalInstructionException { 850 requireApfVersion(3); 851 Instruction instruction = new Instruction(Opcodes.LDDW, destinationRegister); 852 instruction.setSignedImm(offset); 853 addInstruction(instruction); 854 return this; 855 } 856 857 /** 858 * Add an instruction to the end of the program to store 32 bits from {@code register} into the 859 * data memory. The destination address is computed by adding the signed immediate 860 * @{code offset} to the other register. 861 * Requires APF v3 or greater. 862 */ 863 public ApfGenerator addStoreData(Register sourceRegister, int offset) 864 throws IllegalInstructionException { 865 requireApfVersion(3); 866 Instruction instruction = new Instruction(Opcodes.STDW, sourceRegister); 867 instruction.setSignedImm(offset); 868 addInstruction(instruction); 869 return this; 870 } 871 872 /** 873 * Updates instruction offset fields using latest instruction sizes. 874 * @return current program length in bytes. 875 */ 876 private int updateInstructionOffsets() { 877 int offset = 0; 878 for (Instruction instruction : mInstructions) { 879 instruction.offset = offset; 880 offset += instruction.size(); 881 } 882 return offset; 883 } 884 885 /** 886 * Returns an overestimate of the size of the generated program. {@link #generate} may return 887 * a program that is smaller. 888 */ 889 public int programLengthOverEstimate() { 890 return updateInstructionOffsets(); 891 } 892 893 /** 894 * Generate the bytecode for the APF program. 895 * @return the bytecode. 896 * @throws IllegalStateException if a label is referenced but not defined. 897 */ 898 public byte[] generate() throws IllegalInstructionException { 899 // Enforce that we can only generate once because we cannot unshrink instructions and 900 // PASS/DROP labels may move further away requiring unshrinking if we add further 901 // instructions. 902 if (mGenerated) { 903 throw new IllegalStateException("Can only generate() once!"); 904 } 905 mGenerated = true; 906 int total_size; 907 boolean shrunk; 908 // Shrink the immediate value fields of instructions. 909 // As we shrink the instructions some branch offset 910 // fields may shrink also, thereby shrinking the 911 // instructions further. Loop until we've reached the 912 // minimum size. Rarely will this loop more than a few times. 913 // Limit iterations to avoid O(n^2) behavior. 914 int iterations_remaining = 10; 915 do { 916 total_size = updateInstructionOffsets(); 917 // Update drop and pass label offsets. 918 mDropLabel.offset = total_size + 1; 919 mPassLabel.offset = total_size; 920 // Limit run-time in aberant circumstances. 921 if (iterations_remaining-- == 0) break; 922 // Attempt to shrink instructions. 923 shrunk = false; 924 for (Instruction instruction : mInstructions) { 925 if (instruction.shrink()) { 926 shrunk = true; 927 } 928 } 929 } while (shrunk); 930 // Generate bytecode for instructions. 931 byte[] bytecode = new byte[total_size]; 932 for (Instruction instruction : mInstructions) { 933 instruction.generate(bytecode); 934 } 935 return bytecode; 936 } 937} 938 939