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