apf: Tweak the interpreter data addressing schemeandroid-9.0.0_r47android-9.0.0_r46android-9.0.0_r45android-9.0.0_r44android-9.0.0_r43android-9.0.0_r42android-9.0.0_r41android-9.0.0_r40android-9.0.0_r39android-9.0.0_r38android-9.0.0_r37android-9.0.0_r36android-9.0.0_r35android-9.0.0_r34android-9.0.0_r33android-9.0.0_r32android-9.0.0_r31android-9.0.0_r30android-9.0.0_r22android-9.0.0_r21android-9.0.0_r20android-9.0.0_r19android-9.0.0_r16android-9.0.0_r12android-9.0.0_r11pie-qpr3-s1-releasepie-qpr3-releasepie-qpr3-b-releasepie-qpr2-releasepie-qpr1-s3-releasepie-qpr1-s2-releasepie-qpr1-s1-releasepie-qpr1-releasepie-dr1-releasepie-dr1-devpie-devpie-b4s4-releasepie-b4s4-dev

After releasing APFv3, we realized that addressing memory from the top
could be simplified by adjusting a few details:

1) The APF interpreter now receives a single unified buffer containing
both the program bytecode and the data segment, unambiguously matching
the memory layout seen by installApfPacketFilter() and
readApfPacketFilter().

2) Data address zero coincides with the beginning of the APF program,
thus decoupling data addresses from the length of the program (which
could change between invokations of installApfPacketFilter()). This
simplifies the ApfGenerator by not requiring a data relocation step
similar to jump relocation.

3) For convenience, the interpreter pre-fills one volatile memory slot
with the total size of the APF buffer. The APF program can load this
value into a register to efficiently write near the end of the data
segment, thus allowing the program-data boundary to shift freely.

4) Negative addresses wrap around the end of the data buffer, such that
address -1 coincides with the last byte of the buffer.

5) The immediate offet of LDDW and SDDW are now sign-extended, such that
small negative offsets can be encoded as a 1-byte immediate. This,
combined with the modular addressing at (4), can be used to address
memory cells near the end of the data region with 2-byte opcodes.

Overall, the above changes allow building a simple 32bit counter with
a sequence more or less like this:

 2  li R1, -4          ; R1  = -4 (last 32bit word of data)
 1  lddw R0, [R1 + 0]  ; R0  = old counter value
 2  add R0, 42         ; Increment counter by some value
 1  stdw R0, [R1 + 0]  ; Write back the new value

Total: 6 bytes. Note how the above bytecode is independent of the actual
size of the program and data segments. To reduce bytecode size,
the counter increment sequence can be moved to an "IncrementAndDrop"
trampoline, taking only 2 bytes more than a direct jump to DROP:

 2  li R1, -12         ; R0 = counter offset (third to last counter)
 3  jmp CountAndDrop  ; (could be 2 bytes if jumping nearby)
 ...
CountAndDrop:
 1  lddw R0, [R1+0]   ; R0 = old counter value
 2  add R0, 1         ; Increment counter
 1  stdw R0, [R1+0]   ; Write back updated value
 3  jmp DROP          ; cya!

Adding a 1-byte INC instruction would make things a little nicer.

Change-Id: Ia9b25e49e127a48d7344ddc60b17c93d6421ab7d
Bug: 73804303
Test: runtest -x tests/net/java/android/net/apf/ApfTest.java
(cherry picked from commit 17c1fbc9e98e380e508fa83d0f927bc742a5161b)

5 files changed, 67 insertions, 26 deletions

diff --git a/apf.h b/apf.h
index 2d64930..4722888 100644
--- a/apf.h
+++ b/apf.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2016, The Android Open Source Project
+ * Copyright 2018, The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -14,6 +14,9 @@
  * limitations under the License.
  */
 
+#ifndef ANDROID_APF_APF_H
+#define ANDROID_APF_APF_H
+
 // A brief overview of APF:
 //
 // APF machine is composed of:
@@ -83,6 +86,8 @@
 //    When the APF program begins execution, three of the sixteen memory slots
 //    are pre-filled by the interpreter with values that may be useful for
 //    programs:
+//      Slot #11 contains the size (in bytes) of the APF program.
+//      Slot #12 contains the total size of the APF buffer (program + data).
 //      Slot #13 is filled with the IPv4 header length. This value is calculated
 //               by loading the first byte of the IPv4 header and taking the
 //               bottom 4 bits and multiplying their value by 4. This value is
@@ -91,7 +96,7 @@
 //      Slot #14 is filled with size of the packet in bytes, including the
 //               link-layer header if any.
 //      Slot #15 is filled with the filter age in seconds. This is the number of
-//               seconds since the AP send the program to the chipset. This may
+//               seconds since the AP sent the program to the chipset. This may
 //               be used by filters that should have a particular lifetime. For
 //               example, it can be used to rate-limit particular packets to one
 //               every N seconds.
@@ -119,6 +124,8 @@
 // Number of temporary memory slots, see ldm/stm instructions.
 #define MEMORY_ITEMS 16
 // Upon program execution, some temporary memory slots are prefilled:
+#define MEMORY_OFFSET_PROGRAM_SIZE 11     // Size of program (in bytes)
+#define MEMORY_OFFSET_DATA_SIZE 12        // Total size of program + data
 #define MEMORY_OFFSET_IPV4_HEADER_SIZE 13 // 4*([APF_FRAME_HEADER_SIZE]&15)
 #define MEMORY_OFFSET_PACKET_SIZE 14      // Size of packet in bytes.
 #define MEMORY_OFFSET_FILTER_AGE 15       // Age since filter installed in seconds.
@@ -136,7 +143,7 @@
 #define AND_OPCODE 10   // And, e.g. "and R0,5"
 #define OR_OPCODE 11    // Or, e.g. "or R0,5"
 #define SH_OPCODE 12    // Left shift, e.g, "sh R0, 5" or "sh R0, -5" (shifts right)
-#define LI_OPCODE 13    // Load immediate, e.g. "li R0,5" (immediate encoded as signed value)
+#define LI_OPCODE 13    // Load signed immediate, e.g. "li R0,5"
 #define JMP_OPCODE 14   // Unconditional jump, e.g. "jmp label"
 #define JEQ_OPCODE 15   // Compare equal and branch, e.g. "jeq R0,5,label"
 #define JNE_OPCODE 16   // Compare not equal and branch, e.g. "jne R0,5,label"
@@ -145,8 +152,8 @@
 #define JSET_OPCODE 19  // Compare any bits set and branch, e.g. "jset R0,5,label"
 #define JNEBS_OPCODE 20 // Compare not equal byte sequence, e.g. "jnebs R0,5,label,0x1122334455"
 #define EXT_OPCODE 21   // Immediate value is one of *_EXT_OPCODE
-#define LDDW_OPCODE 22  // Load 4 bytes from data address (register + imm): "lddw R0, [5+R1]"
-#define STDW_OPCODE 23  // Store 4 bytes to data address (register + imm): "stdw R0, [5+R1]"
+#define LDDW_OPCODE 22  // Load 4 bytes from data address (register + simm): "lddw R0, [5+R1]"
+#define STDW_OPCODE 23  // Store 4 bytes to data address (register + simm): "stdw R0, [5+R1]"
 
 // Extended opcodes. These all have an opcode of EXT_OPCODE
 // and specify the actual opcode in the immediate field.
@@ -162,3 +169,5 @@
 #define EXTRACT_OPCODE(i) (((i) >> 3) & 31)
 #define EXTRACT_REGISTER(i) ((i) & 1)
 #define EXTRACT_IMM_LENGTH(i) (((i) >> 1) & 3)
+
+#endif  // ANDROID_APF_APF_H
diff --git a/apf_disassembler.c b/apf_disassembler.c
index b61202c..818de7b 100644
--- a/apf_disassembler.c
+++ b/apf_disassembler.c
@@ -211,7 +211,7 @@ int main(void) {
           case LDDW_OPCODE:
           case STDW_OPCODE:
               PRINT_OPCODE();
-              printf("r%u, [%u+r%u]", reg_num, imm, reg_num ^ 1);
+              printf("r%u, [%d+r%u]", reg_num, signed_imm, reg_num ^ 1);
               break;
 
           // Unknown opcode
diff --git a/apf_interpreter.c b/apf_interpreter.c
index e2f46cb..1585a34 100644
--- a/apf_interpreter.c
+++ b/apf_interpreter.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 2016, The Android Open Source Project
+ * Copyright 2018, The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -31,9 +31,8 @@
 // superfluous ">= 0" with unsigned expressions generates compile warnings.
 #define ENFORCE_UNSIGNED(c) ((c)==(uint32_t)(c))
 
-int accept_packet(const uint8_t* program, uint32_t program_len,
+int accept_packet(uint8_t* program, uint32_t program_len, uint32_t ram_len,
                   const uint8_t* packet, uint32_t packet_len,
-                  uint8_t* data, uint32_t data_len,
                   uint32_t filter_age) {
 // Is offset within program bounds?
 #define IN_PROGRAM_BOUNDS(p) (ENFORCE_UNSIGNED(p) && (p) < program_len)
@@ -42,7 +41,8 @@ int accept_packet(const uint8_t* program, uint32_t program_len,
 // Is access to offset |p| length |size| within data bounds?
 #define IN_DATA_BOUNDS(p, size) (ENFORCE_UNSIGNED(p) && \
                                  ENFORCE_UNSIGNED(size) && \
-                                 (p) + (size) <= data_len && \
+                                 (p) + (size) <= ram_len && \
+                                 (p) >= program_len && \
                                  (p) + (size) >= (p))  // catch wraparounds
 // Accept packet if not within program bounds
 #define ASSERT_IN_PROGRAM_BOUNDS(p) ASSERT_RETURN(IN_PROGRAM_BOUNDS(p))
@@ -58,6 +58,8 @@ int accept_packet(const uint8_t* program, uint32_t program_len,
   // Memory slot values.
   uint32_t memory[MEMORY_ITEMS] = {};
   // Fill in pre-filled memory slot values.
+  memory[MEMORY_OFFSET_PROGRAM_SIZE] = program_len;
+  memory[MEMORY_OFFSET_DATA_SIZE] = ram_len;
   memory[MEMORY_OFFSET_PACKET_SIZE] = packet_len;
   memory[MEMORY_OFFSET_FILTER_AGE] = filter_age;
   ASSERT_IN_PACKET_BOUNDS(APF_FRAME_HEADER_SIZE);
@@ -265,22 +267,34 @@ int accept_packet(const uint8_t* program, uint32_t program_len,
               }
               break;
           case LDDW_OPCODE: {
-              uint32_t offs = imm + OTHER_REG;
+              uint32_t offs = OTHER_REG + signed_imm;
               uint32_t size = 4;
               uint32_t val = 0;
+              // Negative offsets wrap around the end of the address space.
+              // This allows us to efficiently access the end of the
+              // address space with one-byte immediates without using %=.
+              if (offs & 0x80000000) {
+                  offs = ram_len + offs;  // unsigned overflow intended
+              }
               ASSERT_IN_DATA_BOUNDS(offs, size);
               while (size--)
-                  val = (val << 8) | data[offs++];
+                  val = (val << 8) | program[offs++];
               REG = val;
               break;
           }
           case STDW_OPCODE: {
-              uint32_t offs = imm + OTHER_REG;
+              uint32_t offs = OTHER_REG + signed_imm;
               uint32_t size = 4;
               uint32_t val = REG;
+              // Negative offsets wrap around the end of the address space.
+              // This allows us to efficiently access the end of the
+              // address space with one-byte immediates without using %=.
+              if (offs & 0x80000000) {
+                  offs = ram_len + offs;  // unsigned overflow intended
+              }
               ASSERT_IN_DATA_BOUNDS(offs, size);
               while (size--) {
-                  data[offs++] = (val >> 24);
+                  program[offs++] = (val >> 24);
                   val <<= 8;
               }
               break;
diff --git a/apf_interpreter.h b/apf_interpreter.h
index 78a0dd3..368ae04 100644
--- a/apf_interpreter.h
+++ b/apf_interpreter.h
@@ -27,26 +27,36 @@ extern "C" {
  * Version of APF instruction set processed by accept_packet().
  * Should be returned by wifi_get_packet_filter_info.
  */
-#define APF_VERSION 3
+#define APF_VERSION 4
 
 /**
  * Runs a packet filtering program over a packet.
  *
- * @param program the program bytecode.
- * @param program_len the length of {@code apf_program} in bytes.
+ * The text section containing the program instructions starts at address
+ * program and stops at + program_len - 1, and the writable data section
+ * begins at program + program_len and ends at program + ram_len - 1,
+ * as described in the following diagram:
+ *
+ *     program         program + program_len    program + ram_len
+ *        |    text section    |      data section      |
+ *        +--------------------+------------------------+
+ *
+ * @param program the program bytecode, followed by the writable data region.
+ * @param program_len the length in bytes of the read-only portion of the APF
+ *                    buffer pointed to by {@code program}.
+ * @param ram_len total length of the APF buffer pointed to by {@code program},
+ *                including the read-only bytecode portion and the read-write
+ *                data portion.
  * @param packet the packet bytes, starting from the 802.3 header and not
  *               including any CRC bytes at the end.
  * @param packet_len the length of {@code packet} in bytes.
- * @param data writable data memory region (preserved between packets).
- * @param data_len the length of {@code data} in bytes.
  * @param filter_age the number of seconds since the filter was programmed.
  *
  * @return non-zero if packet should be passed to AP, zero if
  *         packet should be dropped.
  */
-int accept_packet(const uint8_t* program, uint32_t program_len,
+int accept_packet(uint8_t* program, uint32_t program_len, uint32_t ram_len,
                   const uint8_t* packet, uint32_t packet_len,
-                  uint8_t* data, uint32_t data_len,
                   uint32_t filter_age);
 
 #ifdef __cplusplus
diff --git a/apf_run.c b/apf_run.c
index 3d654cf..d485b71 100644
--- a/apf_run.c
+++ b/apf_run.c
@@ -74,14 +74,22 @@ int main(int argc, char* argv[]) {
     uint8_t* data = NULL;
     uint32_t data_len = argc > 3 ? parse_hex(argv[3], &data) : 0;
     uint32_t filter_age = argc > 4 ? atoi(argv[4]) : 0;
-    int ret = accept_packet(program, program_len, packet, packet_len,
-                            data, data_len, filter_age);
-    printf("Packet %sed\n", ret ? "pass" : "dropp");
+
+    // Combine the program and data into the unified APF buffer.
     if (data) {
+        program = realloc(program, program_len + data_len);
+        memcpy(program + program_len, data, data_len);
+        free(data);
+    }
+
+    uint32_t ram_len = program_len + data_len;
+    int ret = accept_packet(program, program_len, ram_len, packet, packet_len,
+                            filter_age);
+    printf("Packet %sed\n", ret ? "pass" : "dropp");
+    if (data_len) {
         printf("Data: ");
-        print_hex(data, data_len);
+        print_hex(program + program_len, data_len);
         printf("\n");
-        free(data);
     }
     free(program);
     free(packet);