1 /* 2 * Copyright (C) 2023 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 static android.net.apf.ApfGenerator.Register.R0; 20 21 import androidx.annotation.NonNull; 22 23 import java.util.LinkedHashMap; 24 import java.util.Map; 25 import java.util.NoSuchElementException; 26 import java.util.Objects; 27 28 /** 29 * A table that stores program labels to jump to. 30 * 31 * This is needed to implement subroutines because APF jump targets must be known at compile 32 * time and cannot be computed dynamically. 33 * 34 * At compile time, any code that calls a subroutine must: 35 * 36 * <ul> 37 * <li>Define a label (via {@link ApfGenerator#defineLabel}) immediately after the code that invokes 38 * the subroutine. 39 * <li>Add the label to the jump table using {@link #addLabel}. 40 * <li>Generate the jump table in the program. 41 * </ul> 42 * 43 * <p>At runtime, before invoking the subroutine, the APF code must store the index of the return 44 * label (obtained via {@link #getIndex}) into the jump table's return address memory slot, and then 45 * jump to the subroutine. To return to the caller, the subroutine must jump to the label returned 46 * by {@link #getStartLabel}, and the jump table will then jump to the return label. 47 * 48 * <p>Implementation details: 49 * <ul> 50 * <li>The jumps are added to the program in the same order as the labels were added. 51 * <li>Using the jump table will overwrite the value of register R0. 52 * <li>If, before calling a subroutine, the APF code stores a nonexistent return label index, then 53 * the jump table will pass the packet. This cannot happen if the code correctly obtains the 54 * label using {@link #getIndex}, as that would throw an exception when generating the program. 55 * </ul> 56 * 57 * For example: 58 * <pre> 59 * JumpTable t = new JumpTable("my_jump_table", 7); 60 * t.addLabel("jump_1"); 61 * ... 62 * t.addLabel("after_parsing"); 63 * ... 64 * t.addLabel("after_subroutine"); 65 * t.generate(gen); 66 *</pre> 67 * generates the following APF code: 68 * <pre> 69 * :my_jump_table 70 * ldm r0, 7 71 * jeq r0, 0, jump_1 72 * jeq r0, 1, after_parsing 73 * jeq r0, 2, after_subroutine 74 * jmp DROP 75 * </pre> 76 */ 77 public class JumpTable { 78 /** Maps jump indices to jump labels. LinkedHashMap guarantees iteration in insertion order. */ 79 private final Map<String, Integer> mJumpLabels = new LinkedHashMap<>(); 80 /** Label to jump to to execute this jump table. */ 81 private final String mStartLabel; 82 /** Memory slot that contains the return value index. */ 83 private final int mReturnAddressMemorySlot; 84 85 private int mIndex = 0; 86 JumpTable(@onNull String startLabel, int returnAddressMemorySlot)87 public JumpTable(@NonNull String startLabel, int returnAddressMemorySlot) { 88 Objects.requireNonNull(startLabel); 89 mStartLabel = startLabel; 90 if (returnAddressMemorySlot < 0 91 || returnAddressMemorySlot >= ApfGenerator.FIRST_PREFILLED_MEMORY_SLOT) { 92 throw new IllegalArgumentException("Invalid memory slot " + returnAddressMemorySlot); 93 } 94 mReturnAddressMemorySlot = returnAddressMemorySlot; 95 } 96 97 /** Returns the label to jump to to start executing the table. */ 98 @NonNull getStartLabel()99 public String getStartLabel() { 100 return mStartLabel; 101 } 102 103 /** 104 * Adds a jump label to this table. Passing a label that was already added is not an error. 105 * 106 * @param label the label to add 107 */ addLabel(@onNull String label)108 public void addLabel(@NonNull String label) { 109 Objects.requireNonNull(label); 110 if (mJumpLabels.putIfAbsent(label, mIndex) == null) mIndex++; 111 } 112 113 /** 114 * Gets the index of a previously-added label. 115 * @return the label's index. 116 * @throws NoSuchElementException if the label was never added. 117 */ getIndex(@onNull String label)118 public int getIndex(@NonNull String label) { 119 final Integer index = mJumpLabels.get(label); 120 if (index == null) throw new NoSuchElementException("Unknown label " + label); 121 return index; 122 } 123 124 /** Generates APF code for this jump table */ generate(@onNull ApfGenerator gen)125 public void generate(@NonNull ApfGenerator gen) 126 throws ApfGenerator.IllegalInstructionException { 127 gen.defineLabel(mStartLabel); 128 gen.addLoadFromMemory(R0, mReturnAddressMemorySlot); 129 for (Map.Entry<String, Integer> e : mJumpLabels.entrySet()) { 130 gen.addJumpIfR0Equals(e.getValue(), e.getKey()); 131 } 132 // Cannot happen unless the program is malformed (i.e., the APF code loads an invalid return 133 // label index before jumping to the subroutine. 134 gen.addJump(ApfGenerator.PASS_LABEL); 135 } 136 } 137