[src/trunk]: src/sys/net Refactor bpfjit code.

[alnsn <alnsn%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/5a282becd305
branches:  trunk
changeset: 329227:5a282becd305
user:      alnsn <alnsn%NetBSD.org@localhost>
date:      Thu May 15 22:20:08 2014 +0000

description:
Refactor bpfjit code.

 - Implement Array Bounds Check Elimination for packet bytes.
 - Track initialization of registers and memwords.
 - Remove "bj_" prefix from struct members.
 - Shorten "BPFJIT_" prefix to "BJ_".
 - Other small improvements.

diffstat:

 sys/net/bpfjit.c |  1124 ++++++++++++++++++++++++++++-------------------------
 1 files changed, 590 insertions(+), 534 deletions(-)

diffs (truncated from 1999 to 300 lines):

diff -r 313083885243 -r 5a282becd305 sys/net/bpfjit.c
--- a/sys/net/bpfjit.c  Thu May 15 19:37:22 2014 +0000
+++ b/sys/net/bpfjit.c  Thu May 15 22:20:08 2014 +0000
@@ -1,7 +1,7 @@
-/*     $NetBSD: bpfjit.c,v 1.6 2013/12/15 21:18:01 pooka Exp $ */
+/*     $NetBSD: bpfjit.c,v 1.7 2014/05/15 22:20:08 alnsn Exp $ */
 
 /*-
- * Copyright (c) 2011-2012 Alexander Nasonov.
+ * Copyright (c) 2011-2014 Alexander Nasonov.
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -31,30 +31,33 @@
 
 #include <sys/cdefs.h>
 #ifdef _KERNEL
-__KERNEL_RCSID(0, "$NetBSD: bpfjit.c,v 1.6 2013/12/15 21:18:01 pooka Exp $");
+__KERNEL_RCSID(0, "$NetBSD: bpfjit.c,v 1.7 2014/05/15 22:20:08 alnsn Exp $");
 #else
-__RCSID("$NetBSD: bpfjit.c,v 1.6 2013/12/15 21:18:01 pooka Exp $");
+__RCSID("$NetBSD: bpfjit.c,v 1.7 2014/05/15 22:20:08 alnsn Exp $");
 #endif
 
 #include <sys/types.h>
 #include <sys/queue.h>
 
 #ifndef _KERNEL
+#include <assert.h>
+#define BJ_ASSERT(c) assert(c)
+#else
+#define BJ_ASSERT(c) KASSERT(c)
+#endif
+
+#ifndef _KERNEL
 #include <stdlib.h>
-#include <assert.h>
-#define BPFJIT_ALLOC(sz) malloc(sz)
-#define BPFJIT_FREE(p, sz) free(p)
-#define BPFJIT_ASSERT(c) assert(c)
+#define BJ_ALLOC(sz) malloc(sz)
+#define BJ_FREE(p, sz) free(p)
 #else
 #include <sys/kmem.h>
-#define BPFJIT_ALLOC(sz) kmem_alloc(sz, KM_SLEEP)
-#define BPFJIT_FREE(p, sz) kmem_free(p, sz)
-#define BPFJIT_ASSERT(c) KASSERT(c)
+#define BJ_ALLOC(sz) kmem_alloc(sz, KM_SLEEP)
+#define BJ_FREE(p, sz) kmem_free(p, sz)
 #endif
 
 #ifndef _KERNEL
 #include <limits.h>
-#include <stdio.h>
 #include <stdbool.h>
 #include <stddef.h>
 #include <stdint.h>
@@ -68,28 +71,50 @@
 #include <net/bpfjit.h>
 #include <sljitLir.h>
 
-#define BPFJIT_A       SLJIT_TEMPORARY_REG1
-#define BPFJIT_X       SLJIT_TEMPORARY_EREG1
-#define BPFJIT_TMP1    SLJIT_TEMPORARY_REG2
-#define BPFJIT_TMP2    SLJIT_TEMPORARY_REG3
-#define BPFJIT_BUF     SLJIT_SAVED_REG1
-#define BPFJIT_WIRELEN SLJIT_SAVED_REG2
-#define BPFJIT_BUFLEN  SLJIT_SAVED_REG3
-#define BPFJIT_KERN_TMP SLJIT_TEMPORARY_EREG2
-
-/* 
- * Flags for bpfjit_optimization_hints().
- */
-#define BPFJIT_INIT_X 0x10000
-#define BPFJIT_INIT_A 0x20000
+#if !defined(_KERNEL) && defined(SLJIT_VERBOSE) && SLJIT_VERBOSE
+#include <stdio.h> /* for stderr */
+#endif
 
 /*
- * Node of bj_jumps list.
+ * Permanent register assignments.
+ */
+#define BJ_BUF         SLJIT_SAVED_REG1
+#define BJ_WIRELEN     SLJIT_SAVED_REG2
+#define BJ_BUFLEN      SLJIT_SAVED_REG3
+#define BJ_AREG                SLJIT_TEMPORARY_REG1
+#define BJ_TMP1REG     SLJIT_TEMPORARY_REG2
+#define BJ_TMP2REG     SLJIT_TEMPORARY_REG3
+#define BJ_XREG                SLJIT_TEMPORARY_EREG1
+#define BJ_TMP3REG     SLJIT_TEMPORARY_EREG2
+
+typedef unsigned int bpfjit_init_mask_t;
+#define BJ_INIT_NOBITS  0u
+#define BJ_INIT_MBIT(k) (1u << (k))
+#define BJ_INIT_MMASK   (BJ_INIT_MBIT(BPF_MEMWORDS) - 1u)
+#define BJ_INIT_ABIT    BJ_INIT_MBIT(BPF_MEMWORDS)
+#define BJ_INIT_XBIT    BJ_INIT_MBIT(BPF_MEMWORDS + 1)
+
+struct bpfjit_stack
+{
+       uint32_t mem[BPF_MEMWORDS];
+#ifdef _KERNEL
+       void *tmp;
+#endif
+};
+
+/*
+ * Data for BPF_JMP instruction.
+ * Forward declaration for struct bpfjit_jump.
+ */
+struct bpfjit_jump_data;
+
+/*
+ * Node of bjumps list.
  */
 struct bpfjit_jump {
-       struct sljit_jump *bj_jump;
-       SLIST_ENTRY(bpfjit_jump) bj_entries;
-       uint32_t bj_safe_length;
+       struct sljit_jump *sjump;
+       SLIST_ENTRY(bpfjit_jump) entries;
+       struct bpfjit_jump_data *jdata;
 };
 
 /*
@@ -97,11 +122,19 @@
  */
 struct bpfjit_jump_data {
        /*
-        * These entries make up bj_jumps list:
-        * bj_jtf[0] - when coming from jt path,
-        * bj_jtf[1] - when coming from jf path.
+        * These entries make up bjumps list:
+        * jtf[0] - when coming from jt path,
+        * jtf[1] - when coming from jf path.
         */
-       struct bpfjit_jump bj_jtf[2];
+       struct bpfjit_jump jtf[2];
+       /*
+        * Length calculated by Array Bounds Check Elimination (ABC) pass.
+        */
+       uint32_t abc_length;
+       /*
+        * Length checked by the last out-of-bounds check.
+        */
+       uint32_t checked_length;
 };
 
 /*
@@ -110,11 +143,16 @@
  */
 struct bpfjit_read_pkt_data {
        /*
-        * If positive, emit "if (buflen < bj_check_length) return 0".
+        * Length calculated by Array Bounds Check Elimination (ABC) pass.
+        */
+       uint32_t abc_length;
+       /*
+        * If positive, emit "if (buflen < check_length) return 0"
+        * out-of-bounds check.
         * We assume that buflen is never equal to UINT32_MAX (otherwise,
-        * we need a special bool variable to emit unconditional "return 0").
+        * we'd need a special bool variable to emit unconditional "return 0").
         */
-       uint32_t bj_check_length;
+       uint32_t check_length;
 };
 
 /*
@@ -122,14 +160,15 @@
  */
 struct bpfjit_insn_data {
        /* List of jumps to this insn. */
-       SLIST_HEAD(, bpfjit_jump) bj_jumps;
+       SLIST_HEAD(, bpfjit_jump) bjumps;
 
        union {
-               struct bpfjit_jump_data     bj_jdata;
-               struct bpfjit_read_pkt_data bj_rdata;
-       } bj_aux;
+               struct bpfjit_jump_data     jdata;
+               struct bpfjit_read_pkt_data rdata;
+       } u;
 
-       bool bj_unreachable;
+       bpfjit_init_mask_t invalid;
+       bool unreachable;
 };
 
 #ifdef _KERNEL
@@ -162,7 +201,7 @@
 #endif
 
 static uint32_t
-read_width(struct bpf_insn *pc)
+read_width(const struct bpf_insn *pc)
 {
 
        switch (BPF_SIZE(pc->code)) {
@@ -173,27 +212,43 @@
        case BPF_B:
                return 1;
        default:
-               BPFJIT_ASSERT(false);
+               BJ_ASSERT(false);
                return 0;
        }
 }
 
-/*
- * Get offset of M[k] on the stack.
- */
-static size_t
-mem_local_offset(uint32_t k, unsigned int minm)
+static bool
+grow_jumps(struct sljit_jump ***jumps, size_t *size)
 {
-       size_t moff = (k - minm) * sizeof(uint32_t);
+       struct sljit_jump **newptr;
+       const size_t elemsz = sizeof(struct sljit_jump *);
+       size_t old_size = *size;
+       size_t new_size = 2 * old_size;
+
+       if (new_size < old_size || new_size > SIZE_MAX / elemsz)
+               return false;
+
+       newptr = BJ_ALLOC(new_size * elemsz);
+       if (newptr == NULL)
+               return false;
 
-#ifdef _KERNEL
-       /*
-        * 4 bytes for the third argument of m_xword/m_xhalf/m_xbyte.
-        */
-       return sizeof(uint32_t) + moff;
-#else
-       return moff;
-#endif
+       memcpy(newptr, *jumps, old_size * elemsz);
+       BJ_FREE(*jumps, old_size * elemsz);
+
+       *jumps = newptr;
+       *size = new_size;
+       return true;
+}
+
+static bool
+append_jump(struct sljit_jump *jump, struct sljit_jump ***jumps,
+    size_t *size, size_t *max_size)
+{
+       if (*size == *max_size && !grow_jumps(jumps, max_size))
+               return false;
+
+       (*jumps)[(*size)++] = jump;
+       return true;
 }
 
 /*
@@ -205,8 +260,8 @@
 
        return sljit_emit_op1(compiler,
            SLJIT_MOV_UB,
-           BPFJIT_A, 0,
-           SLJIT_MEM1(BPFJIT_BUF), k);
+           BJ_AREG, 0,
+           SLJIT_MEM1(BJ_BUF), k);
 }
 
 /*
@@ -220,24 +275,24 @@
        /* tmp1 = buf[k]; */
        status = sljit_emit_op1(compiler,
            SLJIT_MOV_UB,
-           BPFJIT_TMP1, 0,
-           SLJIT_MEM1(BPFJIT_BUF), k);
+           BJ_TMP1REG, 0,
+           SLJIT_MEM1(BJ_BUF), k);
        if (status != SLJIT_SUCCESS)
                return status;
 
        /* A = buf[k+1]; */
        status = sljit_emit_op1(compiler,
            SLJIT_MOV_UB,
-           BPFJIT_A, 0,
-           SLJIT_MEM1(BPFJIT_BUF), k+1);
+           BJ_AREG, 0,
+           SLJIT_MEM1(BJ_BUF), k+1);
        if (status != SLJIT_SUCCESS)
                return status;
 
        /* tmp1 = tmp1 << 8; */
        status = sljit_emit_op2(compiler,
            SLJIT_SHL,
-           BPFJIT_TMP1, 0,
-           BPFJIT_TMP1, 0,
+           BJ_TMP1REG, 0,
+           BJ_TMP1REG, 0,
            SLJIT_IMM, 8);
        if (status != SLJIT_SUCCESS)