CI: Call print_so_deps() on rpcapd in remote enabled build

[libpcap] / optimize.c

diff --git a/optimize.c b/optimize.c
index 4115cb55dc81f1a552504ebd3f2c5e692a631d79..c617f536936eef05d4b7a4895bfebd7b1f9c54d4 100644 (file)
--- a/optimize.c
+++ b/optimize.c
@@ -21,9 +21,7 @@
  *  Optimization module for BPF code intermediate representation.
  */
 
  *  Optimization module for BPF code intermediate representation.
  */
 

-#ifdef HAVE_CONFIG_H

 #include <config.h>
 #include <config.h>

-#endif

 
 #include <pcap-types.h>
 
 
 #include <pcap-types.h>
 


@@ -119,7 +117,7 @@ pcap_set_print_dot_graph(int value)
   #define lowest_set_bit(mask) ((u_int)__builtin_ctz(mask))
 #elif defined(_MSC_VER)
   /*
   #define lowest_set_bit(mask) ((u_int)__builtin_ctz(mask))
 #elif defined(_MSC_VER)
   /*

-   * Visual Studio; we support only 2005 and later, so use
+   * Visual Studio; we support only 2015 and later, so use

    * _BitScanForward().
    */
 #include <intrin.h>
    * _BitScanForward().
    */
 #include <intrin.h>


@@ -142,33 +140,14 @@ lowest_set_bit(int mask)
        return (u_int)bit;
 }
 #else
        return (u_int)bit;
 }
 #else

-/*
- * None of the above.
- * Use a perfect-hash-function-based function.
- */
-static u_int
-lowest_set_bit(int mask)
-{
-       unsigned int v = (unsigned int)mask;
-
-       static const u_int MultiplyDeBruijnBitPosition[32] = {
-               0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
-               31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
-       };
-
-       /*
-        * We strip off all but the lowermost set bit (v & ~v),
-        * and perform a minimal perfect hash on it to look up the
-        * number of low-order zero bits in a table.
-        *
-        * See:
-        *
-        *      http://7ooo.mooo.com/text/ComputingTrailingZerosHOWTO.pdf
-        *
-        *      http://supertech.csail.mit.edu/papers/debruijn.pdf
-        */
-       return (MultiplyDeBruijnBitPosition[((v & -v) * 0x077CB531U) >> 27]);
-}
+  /*
+   * POSIX.1-2001 says ffs() is in <strings.h>.  Every supported non-Windows OS
+   * (including Linux with musl libc and uclibc-ng) has the header and (except
+   * HP-UX) declares the function there.  HP-UX declares the function in
+   * <string.h>, which has already been included.
+   */
+  #include <strings.h>
+  #define lowest_set_bit(mask) ((u_int)(ffs((mask)) - 1))

 #endif
 
 /*
 #endif
 
 /*


@@ -357,10 +336,6 @@ static void find_inedges(opt_state_t *, struct block *);
 static void opt_dump(opt_state_t *, struct icode *);
 #endif
 
 static void opt_dump(opt_state_t *, struct icode *);
 #endif
 

-#ifndef MAX
-#define MAX(a,b) ((a)>(b)?(a):(b))
-#endif
-

 static void
 find_levels_r(opt_state_t *opt_state, struct icode *ic, struct block *b)
 {
 static void
 find_levels_r(opt_state_t *opt_state, struct icode *ic, struct block *b)
 {


@@ -375,7 +350,7 @@ find_levels_r(opt_state_t *opt_state, struct icode *ic, struct block *b)
        if (JT(b)) {
                find_levels_r(opt_state, ic, JT(b));
                find_levels_r(opt_state, ic, JF(b));
        if (JT(b)) {
                find_levels_r(opt_state, ic, JT(b));
                find_levels_r(opt_state, ic, JF(b));

-               level = MAX(JT(b)->level, JF(b)->level) + 1;
+               level = max(JT(b)->level, JF(b)->level) + 1;

        } else
                level = 0;
        b->level = level;
        } else
                level = 0;
        b->level = level;


@@ -850,11 +825,11 @@ fold_op(opt_state_t *opt_state, struct stmt *s, bpf_u_int32 v0, bpf_u_int32 v1)
        }
        s->k = a;
        s->code = BPF_LD|BPF_IMM;
        }
        s->k = a;
        s->code = BPF_LD|BPF_IMM;

+       opt_state->done = 0;

        /*
         * XXX - optimizer loop detection.
         */
        opt_state->non_branch_movement_performed = 1;
        /*
         * XXX - optimizer loop detection.
         */
        opt_state->non_branch_movement_performed = 1;

-       opt_state->done = 0;

 }
 
 static inline struct slist *
 }
 
 static inline struct slist *


@@ -910,12 +885,12 @@ opt_peep(opt_state_t *opt_state, struct block *b)
                if (s->s.code == BPF_ST &&
                    next->s.code == (BPF_LDX|BPF_MEM) &&
                    s->s.k == next->s.k) {
                if (s->s.code == BPF_ST &&
                    next->s.code == (BPF_LDX|BPF_MEM) &&
                    s->s.k == next->s.k) {

+                       opt_state->done = 0;
+                       next->s.code = BPF_MISC|BPF_TAX;

                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;
                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;

-                       opt_state->done = 0;
-                       next->s.code = BPF_MISC|BPF_TAX;

                }
                /*
                 * ld  #k       -->     ldx  #k
                }
                /*
                 * ld  #k       -->     ldx  #k


@@ -925,11 +900,11 @@ opt_peep(opt_state_t *opt_state, struct block *b)
                    next->s.code == (BPF_MISC|BPF_TAX)) {
                        s->s.code = BPF_LDX|BPF_IMM;
                        next->s.code = BPF_MISC|BPF_TXA;
                    next->s.code == (BPF_MISC|BPF_TAX)) {
                        s->s.code = BPF_LDX|BPF_IMM;
                        next->s.code = BPF_MISC|BPF_TXA;

+                       opt_state->done = 0;

                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;
                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;

-                       opt_state->done = 0;

                }
                /*
                 * This is an ugly special case, but it happens
                }
                /*
                 * This is an ugly special case, but it happens


@@ -1008,11 +983,11 @@ opt_peep(opt_state_t *opt_state, struct block *b)
                        s->s.code = NOP;
                        add->s.code = NOP;
                        tax->s.code = NOP;
                        s->s.code = NOP;
                        add->s.code = NOP;
                        tax->s.code = NOP;

+                       opt_state->done = 0;

                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;
                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;

-                       opt_state->done = 0;

                }
        }
        /*
                }
        }
        /*


@@ -1042,11 +1017,11 @@ opt_peep(opt_state_t *opt_state, struct block *b)
                                 */
                                b->s.k += opt_state->vmap[val].const_val;
                                last->s.code = NOP;
                                 */
                                b->s.k += opt_state->vmap[val].const_val;
                                last->s.code = NOP;

+                               opt_state->done = 0;

                                /*
                                 * XXX - optimizer loop detection.
                                 */
                                opt_state->non_branch_movement_performed = 1;
                                /*
                                 * XXX - optimizer loop detection.
                                 */
                                opt_state->non_branch_movement_performed = 1;

-                               opt_state->done = 0;

                        } else if (b->s.k == 0) {
                                /*
                                 * If the X register isn't a constant,
                        } else if (b->s.k == 0) {
                                /*
                                 * If the X register isn't a constant,


@@ -1059,11 +1034,11 @@ opt_peep(opt_state_t *opt_state, struct block *b)
                                 */
                                last->s.code = NOP;
                                b->s.code = BPF_JMP|BPF_JEQ|BPF_X;
                                 */
                                last->s.code = NOP;
                                b->s.code = BPF_JMP|BPF_JEQ|BPF_X;

+                               opt_state->done = 0;

                                /*
                                 * XXX - optimizer loop detection.
                                 */
                                opt_state->non_branch_movement_performed = 1;
                                /*
                                 * XXX - optimizer loop detection.
                                 */
                                opt_state->non_branch_movement_performed = 1;

-                               opt_state->done = 0;

                        }
                }
                /*
                        }
                }
                /*


@@ -1075,11 +1050,11 @@ opt_peep(opt_state_t *opt_state, struct block *b)
                else if (last->s.code == (BPF_ALU|BPF_SUB|BPF_K)) {
                        last->s.code = NOP;
                        b->s.k += last->s.k;
                else if (last->s.code == (BPF_ALU|BPF_SUB|BPF_K)) {
                        last->s.code = NOP;
                        b->s.k += last->s.k;

+                       opt_state->done = 0;

                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;
                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;

-                       opt_state->done = 0;

                }
                /*
                 * And, similarly, a constant AND can be simplified
                }
                /*
                 * And, similarly, a constant AND can be simplified


@@ -1093,12 +1068,12 @@ opt_peep(opt_state_t *opt_state, struct block *b)
                        b->s.k = last->s.k;
                        b->s.code = BPF_JMP|BPF_K|BPF_JSET;
                        last->s.code = NOP;
                        b->s.k = last->s.k;
                        b->s.code = BPF_JMP|BPF_K|BPF_JSET;
                        last->s.code = NOP;

+                       opt_state->done = 0;
+                       opt_not(b);

                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;
                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;

-                       opt_state->done = 0;
-                       opt_not(b);

                }
        }
        /*
                }
        }
        /*


@@ -1151,11 +1126,11 @@ opt_peep(opt_state_t *opt_state, struct block *b)
                        abort();
                }
                if (JF(b) != JT(b)) {
                        abort();
                }
                if (JF(b) != JT(b)) {

+                       opt_state->done = 0;

                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;
                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;

-                       opt_state->done = 0;

                }
                if (v)
                        JF(b) = JT(b);
                }
                if (v)
                        JF(b) = JT(b);


@@ -1193,11 +1168,11 @@ opt_stmt(opt_state_t *opt_state, struct stmt *s, bpf_u_int32 val[], int alter)
                        s->code = BPF_LD|BPF_ABS|BPF_SIZE(s->code);
                        s->k += opt_state->vmap[v].const_val;
                        v = F(opt_state, s->code, s->k, 0L);
                        s->code = BPF_LD|BPF_ABS|BPF_SIZE(s->code);
                        s->k += opt_state->vmap[v].const_val;
                        v = F(opt_state, s->code, s->k, 0L);

+                       opt_state->done = 0;

                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;
                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;

-                       opt_state->done = 0;

                }
                else
                        v = F(opt_state, s->code, s->k, v);
                }
                else
                        v = F(opt_state, s->code, s->k, v);


@@ -1324,13 +1299,13 @@ opt_stmt(opt_state_t *opt_state, struct stmt *s, bpf_u_int32 val[], int alter)
                                    s->k > 31)
                                        opt_error(opt_state,
                                            "shift by more than 31 bits");
                                    s->k > 31)
                                        opt_error(opt_state,
                                            "shift by more than 31 bits");

+                               opt_state->done = 0;
+                               val[A_ATOM] =
+                                       F(opt_state, s->code, val[A_ATOM], K(s->k));

                                /*
                                 * XXX - optimizer loop detection.
                                 */
                                opt_state->non_branch_movement_performed = 1;
                                /*
                                 * XXX - optimizer loop detection.
                                 */
                                opt_state->non_branch_movement_performed = 1;

-                               opt_state->done = 0;
-                               val[A_ATOM] =
-                                       F(opt_state, s->code, val[A_ATOM], K(s->k));

                        }
                        break;
                }
                        }
                        break;
                }


@@ -1372,11 +1347,11 @@ opt_stmt(opt_state_t *opt_state, struct stmt *s, bpf_u_int32 val[], int alter)
                if (alter && opt_state->vmap[v].is_const) {
                        s->code = BPF_LD|BPF_IMM;
                        s->k = opt_state->vmap[v].const_val;
                if (alter && opt_state->vmap[v].is_const) {
                        s->code = BPF_LD|BPF_IMM;
                        s->k = opt_state->vmap[v].const_val;

+                       opt_state->done = 0;

                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;
                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;

-                       opt_state->done = 0;

                }
                vstore(s, &val[A_ATOM], v, alter);
                break;
                }
                vstore(s, &val[A_ATOM], v, alter);
                break;


@@ -1390,11 +1365,11 @@ opt_stmt(opt_state_t *opt_state, struct stmt *s, bpf_u_int32 val[], int alter)
                if (alter && opt_state->vmap[v].is_const) {
                        s->code = BPF_LDX|BPF_IMM;
                        s->k = opt_state->vmap[v].const_val;
                if (alter && opt_state->vmap[v].is_const) {
                        s->code = BPF_LDX|BPF_IMM;
                        s->k = opt_state->vmap[v].const_val;

+                       opt_state->done = 0;

                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;
                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;

-                       opt_state->done = 0;

                }
                vstore(s, &val[X_ATOM], v, alter);
                break;
                }
                vstore(s, &val[X_ATOM], v, alter);
                break;


@@ -1426,12 +1401,12 @@ deadstmt(opt_state_t *opt_state, register struct stmt *s, register struct stmt *
        atom = atomdef(s);
        if (atom >= 0) {
                if (last[atom]) {
        atom = atomdef(s);
        if (atom >= 0) {
                if (last[atom]) {

+                       opt_state->done = 0;
+                       last[atom]->code = NOP;

                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;
                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;

-                       opt_state->done = 0;
-                       last[atom]->code = NOP;

                }
                last[atom] = s;
        }
                }
                last[atom] = s;
        }


@@ -1453,11 +1428,17 @@ opt_deadstores(opt_state_t *opt_state, register struct block *b)
        for (atom = 0; atom < N_ATOMS; ++atom)
                if (last[atom] && !ATOMELEM(b->out_use, atom)) {
                        last[atom]->code = NOP;
        for (atom = 0; atom < N_ATOMS; ++atom)
                if (last[atom] && !ATOMELEM(b->out_use, atom)) {
                        last[atom]->code = NOP;

+                       /*
+                        * The store was removed as it's dead,
+                        * so the value stored into now has
+                        * an unknown value.
+                        */
+                       vstore(0, &b->val[atom], VAL_UNKNOWN, 0);
+                       opt_state->done = 0;

                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;
                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;

-                       opt_state->done = 0;

                }
 }
 
                }
 }
 


@@ -1547,11 +1528,11 @@ opt_blk(opt_state_t *opt_state, struct block *b, int do_stmts)
             BPF_CLASS(b->s.code) == BPF_RET)) {
                if (b->stmts != 0) {
                        b->stmts = 0;
             BPF_CLASS(b->s.code) == BPF_RET)) {
                if (b->stmts != 0) {
                        b->stmts = 0;

+                       opt_state->done = 0;

                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;
                        /*
                         * XXX - optimizer loop detection.
                         */
                        opt_state->non_branch_movement_performed = 1;

-                       opt_state->done = 0;

                }
        } else {
                opt_peep(opt_state, b);
                }
        } else {
                opt_peep(opt_state, b);


@@ -1719,12 +1700,13 @@ opt_j(opt_state_t *opt_state, struct edge *ep)
                         * Make this edge go to the block to
                         * which the successor of that edge
                         * goes.
                         * Make this edge go to the block to
                         * which the successor of that edge
                         * goes.

-                        *
-                        * XXX - optimizer loop detection.

                         */
                         */

-                       opt_state->non_branch_movement_performed = 1;

                        opt_state->done = 0;
                        ep->succ = JT(ep->succ);
                        opt_state->done = 0;
                        ep->succ = JT(ep->succ);

+                       /*
+                        * XXX - optimizer loop detection.
+                        */
+                       opt_state->non_branch_movement_performed = 1;

                }
        }
        /*
                }
        }
        /*


@@ -2179,7 +2161,7 @@ opt_loop(opt_state_t *opt_state, struct icode *ic, int do_stmts)
 
 #ifdef BDEBUG
        if (pcap_optimizer_debug > 1 || pcap_print_dot_graph) {
 
 #ifdef BDEBUG
        if (pcap_optimizer_debug > 1 || pcap_print_dot_graph) {

-               printf("opt_loop(root, %d) begin\n", do_stmts);
+               printf("%s(root, %d) begin\n", __func__, do_stmts);

                opt_dump(opt_state, ic);
        }
 #endif
                opt_dump(opt_state, ic);
        }
 #endif


@@ -2189,11 +2171,11 @@ opt_loop(opt_state_t *opt_state, struct icode *ic, int do_stmts)
         */
        int loop_count = 0;
        for (;;) {
         */
        int loop_count = 0;
        for (;;) {

-               opt_state->done = 1;

                /*
                 * XXX - optimizer loop detection.
                 */
                opt_state->non_branch_movement_performed = 0;
                /*
                 * XXX - optimizer loop detection.
                 */
                opt_state->non_branch_movement_performed = 0;

+               opt_state->done = 1;

                find_levels(opt_state, ic);
                find_dom(opt_state, ic->root);
                find_closure(opt_state, ic->root);
                find_levels(opt_state, ic);
                find_dom(opt_state, ic->root);
                find_closure(opt_state, ic->root);


@@ -2202,7 +2184,7 @@ opt_loop(opt_state_t *opt_state, struct icode *ic, int do_stmts)
                opt_blks(opt_state, ic, do_stmts);
 #ifdef BDEBUG
                if (pcap_optimizer_debug > 1 || pcap_print_dot_graph) {
                opt_blks(opt_state, ic, do_stmts);
 #ifdef BDEBUG
                if (pcap_optimizer_debug > 1 || pcap_print_dot_graph) {

-                       printf("opt_loop(root, %d) bottom, done=%d\n", do_stmts, opt_state->done);
+                       printf("%s(root, %d) bottom, done=%d\n", __func__, do_stmts, opt_state->done);

                        opt_dump(opt_state, ic);
                }
 #endif
                        opt_dump(opt_state, ic);
                }
 #endif


@@ -2264,7 +2246,6 @@ bpf_optimize(struct icode *ic, char *errbuf)
 
        memset(&opt_state, 0, sizeof(opt_state));
        opt_state.errbuf = errbuf;
 
        memset(&opt_state, 0, sizeof(opt_state));
        opt_state.errbuf = errbuf;

-       opt_state.non_branch_movement_performed = 0;

        if (setjmp(opt_state.top_ctx)) {
                opt_cleanup(&opt_state);
                return -1;
        if (setjmp(opt_state.top_ctx)) {
                opt_cleanup(&opt_state);
                return -1;


@@ -3090,6 +3071,6 @@ opt_dump(opt_state_t *opt_state, struct icode *ic)
        else
                status = plain_dump(ic, errbuf);
        if (status == -1)
        else
                status = plain_dump(ic, errbuf);
        if (status == -1)

-               opt_error(opt_state, "opt_dump: icode_to_fcode failed: %s", errbuf);
+               opt_error(opt_state, "%s: icode_to_fcode failed: %s", __func__, errbuf);

 }
 #endif
 }
 #endif