libpcap  1.10.1
About: libpcap is a packet filter library used by tools like tcpdump.
  Fossies Dox: libpcap-1.10.1.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

optimize.c File Reference
#include <pcap-types.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <setjmp.h>
#include <string.h>
#include <errno.h>
#include "pcap-int.h"
#include "gencode.h"
#include "optimize.h"
Include dependency graph for optimize.c:

Go to the source code of this file.

Data Structures

struct  valnode
 
struct  vmapinfo
 
struct  opt_state_t
 
struct  conv_state_t
 

Macros

#define NOP   -1
 
#define A_ATOM   BPF_MEMWORDS
 
#define X_ATOM   (BPF_MEMWORDS+1)
 
#define AX_ATOM   N_ATOMS
 
#define K(i)   F(opt_state, BPF_LD|BPF_IMM|BPF_W, i, 0U)
 
#define BITS_PER_WORD   (8*sizeof(bpf_u_int32))
 
#define SET_MEMBER(p, a)   ((p)[(unsigned)(a) / BITS_PER_WORD] & ((bpf_u_int32)1 << ((unsigned)(a) % BITS_PER_WORD)))
 
#define SET_INSERT(p, a)   (p)[(unsigned)(a) / BITS_PER_WORD] |= ((bpf_u_int32)1 << ((unsigned)(a) % BITS_PER_WORD))
 
#define SET_DELETE(p, a)   (p)[(unsigned)(a) / BITS_PER_WORD] &= ~((bpf_u_int32)1 << ((unsigned)(a) % BITS_PER_WORD))
 
#define SET_INTERSECT(a, b, n)
 
#define SET_SUBTRACT(a, b, n)
 
#define SET_UNION(a, b, n)
 
#define MODULUS   213
 
#define MAX(a, b)   ((a)>(b)?(a):(b))
 

Functions

static u_int lowest_set_bit (int mask)
 
static void opt_init (opt_state_t *, struct icode *)
 
static void opt_cleanup (opt_state_t *)
 
static void opt_error (opt_state_t *, const char *,...)
 
static void intern_blocks (opt_state_t *, struct icode *)
 
static void find_inedges (opt_state_t *, struct block *)
 
static void find_levels_r (opt_state_t *opt_state, struct icode *ic, struct block *b)
 
static void find_levels (opt_state_t *opt_state, struct icode *ic)
 
static void find_dom (opt_state_t *opt_state, struct block *root)
 
static void propedom (opt_state_t *opt_state, struct edge *ep)
 
static void find_edom (opt_state_t *opt_state, struct block *root)
 
static void find_closure (opt_state_t *opt_state, struct block *root)
 
static int atomuse (struct stmt *s)
 
static int atomdef (struct stmt *s)
 
static void compute_local_ud (struct block *b)
 
static void find_ud (opt_state_t *opt_state, struct block *root)
 
static void init_val (opt_state_t *opt_state)
 
static bpf_u_int32 F (opt_state_t *opt_state, int code, bpf_u_int32 v0, bpf_u_int32 v1)
 
static void vstore (struct stmt *s, bpf_u_int32 *valp, bpf_u_int32 newval, int alter)
 
static void fold_op (opt_state_t *opt_state, struct stmt *s, bpf_u_int32 v0, bpf_u_int32 v1)
 
static struct slistthis_op (struct slist *s)
 
static void opt_not (struct block *b)
 
static void opt_peep (opt_state_t *opt_state, struct block *b)
 
static void opt_stmt (opt_state_t *opt_state, struct stmt *s, bpf_u_int32 val[], int alter)
 
static void deadstmt (opt_state_t *opt_state, register struct stmt *s, register struct stmt *last[])
 
static void opt_deadstores (opt_state_t *opt_state, register struct block *b)
 
static void opt_blk (opt_state_t *opt_state, struct block *b, int do_stmts)
 
static int use_conflict (struct block *b, struct block *succ)
 
static struct blockfold_edge (struct block *child, struct edge *ep)
 
static void opt_j (opt_state_t *opt_state, struct edge *ep)
 
static void or_pullup (opt_state_t *opt_state, struct block *b)
 
static void and_pullup (opt_state_t *opt_state, struct block *b)
 
static void opt_blks (opt_state_t *opt_state, struct icode *ic, int do_stmts)
 
static void link_inedge (struct edge *parent, struct block *child)
 
static void opt_root (struct block **b)
 
static void opt_loop (opt_state_t *opt_state, struct icode *ic, int do_stmts)
 
int bpf_optimize (struct icode *ic, char *errbuf)
 
static void make_marks (struct icode *ic, struct block *p)
 
static void mark_code (struct icode *ic)
 
static int eq_slist (struct slist *x, struct slist *y)
 
static int eq_blk (struct block *b0, struct block *b1)
 
static u_int slength (struct slist *s)
 
static int count_blocks (struct icode *ic, struct block *p)
 
static void number_blks_r (opt_state_t *opt_state, struct icode *ic, struct block *p)
 
static u_int count_stmts (struct icode *ic, struct block *p)
 
static void conv_error (conv_state_t *, const char *,...)
 
static int convert_code_r (conv_state_t *conv_state, struct icode *ic, struct block *p)
 
struct bpf_insnicode_to_fcode (struct icode *ic, struct block *root, u_int *lenp, char *errbuf)
 
int install_bpf_program (pcap_t *p, struct bpf_program *fp)
 

Macro Definition Documentation

◆ A_ATOM

#define A_ATOM   BPF_MEMWORDS

Definition at line 198 of file optimize.c.

◆ AX_ATOM

#define AX_ATOM   N_ATOMS

Definition at line 206 of file optimize.c.

◆ BITS_PER_WORD

#define BITS_PER_WORD   (8*sizeof(bpf_u_int32))

Definition at line 274 of file optimize.c.

◆ K

#define K (   i)    F(opt_state, BPF_LD|BPF_IMM|BPF_W, i, 0U)

Definition at line 222 of file optimize.c.

◆ MAX

#define MAX (   a,
 
)    ((a)>(b)?(a):(b))

Definition at line 374 of file optimize.c.

◆ MODULUS

#define MODULUS   213

Definition at line 330 of file optimize.c.

◆ NOP

#define NOP   -1

Definition at line 190 of file optimize.c.

◆ SET_DELETE

#define SET_DELETE (   p,
 
)    (p)[(unsigned)(a) / BITS_PER_WORD] &= ~((bpf_u_int32)1 << ((unsigned)(a) % BITS_PER_WORD))

Definition at line 290 of file optimize.c.

◆ SET_INSERT

#define SET_INSERT (   p,
 
)    (p)[(unsigned)(a) / BITS_PER_WORD] |= ((bpf_u_int32)1 << ((unsigned)(a) % BITS_PER_WORD))

Definition at line 284 of file optimize.c.

◆ SET_INTERSECT

#define SET_INTERSECT (   a,
  b,
 
)
Value:
{\
register bpf_u_int32 *_x = a, *_y = b;\
register u_int _n = n;\
do *_x++ &= *_y++; while (--_n != 0);\
}
u_int bpf_u_int32
Definition: bpf.h:98

Definition at line 297 of file optimize.c.

◆ SET_MEMBER

#define SET_MEMBER (   p,
 
)    ((p)[(unsigned)(a) / BITS_PER_WORD] & ((bpf_u_int32)1 << ((unsigned)(a) % BITS_PER_WORD)))

Definition at line 278 of file optimize.c.

◆ SET_SUBTRACT

#define SET_SUBTRACT (   a,
  b,
 
)
Value:
{\
register bpf_u_int32 *_x = a, *_y = b;\
register u_int _n = n;\
do *_x++ &=~ *_y++; while (--_n != 0);\
}

Definition at line 308 of file optimize.c.

◆ SET_UNION

#define SET_UNION (   a,
  b,
 
)
Value:
{\
register bpf_u_int32 *_x = a, *_y = b;\
register u_int _n = n;\
do *_x++ |= *_y++; while (--_n != 0);\
}

Definition at line 319 of file optimize.c.

◆ X_ATOM

#define X_ATOM   (BPF_MEMWORDS+1)

Definition at line 199 of file optimize.c.

Function Documentation

◆ and_pullup()

static void and_pullup ( opt_state_t opt_state,
struct block b 
)
static

Definition at line 1981 of file optimize.c.

References A_ATOM, opt_state_t::done, block::id, block::in_edges, JF, JT, N_ATOMS, edge::next, edge::pred, SET_MEMBER, and block::val.

Referenced by opt_blks().

◆ atomdef()

static int atomdef ( struct stmt s)
static

◆ atomuse()

static int atomuse ( struct stmt s)
static

◆ bpf_optimize()

int bpf_optimize ( struct icode ic,
char *  errbuf 
)

◆ compute_local_ud()

static void compute_local_ud ( struct block b)
static

◆ conv_error()

static void conv_error ( conv_state_t conv_state,
const char *  fmt,
  ... 
)
static

Definition at line 2918 of file optimize.c.

References conv_state_t::errbuf, PCAP_ERRBUF_SIZE, conv_state_t::top_ctx, and vsnprintf().

Referenced by convert_code_r().

◆ convert_code_r()

static int convert_code_r ( conv_state_t conv_state,
struct icode ic,
struct block p 
)
static

◆ count_blocks()

static int count_blocks ( struct icode ic,
struct block p 
)
static

Definition at line 2445 of file optimize.c.

References isMarked, JF, JT, and Mark.

Referenced by opt_init().

◆ count_stmts()

static u_int count_stmts ( struct icode ic,
struct block p 
)
static

Definition at line 2499 of file optimize.c.

References isMarked, JF, JT, block::longjf, block::longjt, Mark, slength(), and block::stmts.

Referenced by icode_to_fcode().

◆ deadstmt()

static void deadstmt ( opt_state_t opt_state,
register struct stmt s,
register struct stmt last[] 
)
static

◆ eq_blk()

static int eq_blk ( struct block b0,
struct block b1 
)
inlinestatic

Definition at line 2343 of file optimize.c.

References stmt::code, block::ef, eq_slist(), block::et, stmt::k, block::s, block::stmts, and edge::succ.

Referenced by intern_blocks().

◆ eq_slist()

static int eq_slist ( struct slist x,
struct slist y 
)
static

Definition at line 2324 of file optimize.c.

References stmt::code, stmt::k, slist::next, NOP, and slist::s.

Referenced by eq_blk().

◆ F()

◆ find_closure()

static void find_closure ( opt_state_t opt_state,
struct block root 
)
static

◆ find_dom()

static void find_dom ( opt_state_t opt_state,
struct block root 
)
static

◆ find_edom()

static void find_edom ( opt_state_t opt_state,
struct block root 
)
static

◆ find_inedges()

static void find_inedges ( opt_state_t opt_state,
struct block root 
)
static

◆ find_levels()

static void find_levels ( opt_state_t opt_state,
struct icode ic 
)
static

Definition at line 406 of file optimize.c.

References find_levels_r(), opt_state_t::levels, opt_state_t::n_blocks, icode::root, and unMarkAll.

Referenced by opt_loop().

◆ find_levels_r()

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

Definition at line 378 of file optimize.c.

References isMarked, JF, JT, block::level, opt_state_t::levels, block::link, Mark, and MAX.

Referenced by find_levels().

◆ find_ud()

static void find_ud ( opt_state_t opt_state,
struct block root 
)
static

Definition at line 684 of file optimize.c.

References compute_local_ud(), block::in_use, JF, JT, block::level, opt_state_t::levels, block::link, and block::out_use.

Referenced by opt_loop().

◆ fold_edge()

static struct block* fold_edge ( struct block child,
struct edge ep 
)
static

Definition at line 1613 of file optimize.c.

References A_ATOM, BPF_JEQ, BPF_JMP, BPF_K, stmt::code, edge::code, JF, JT, block::oval, edge::pred, block::s, block::sense, and block::val.

Referenced by opt_j().

◆ fold_op()

◆ icode_to_fcode()

struct bpf_insn* icode_to_fcode ( struct icode ic,
struct block root,
u_int *  lenp,
char *  errbuf 
)

◆ init_val()

static void init_val ( opt_state_t opt_state)
static

◆ install_bpf_program()

◆ intern_blocks()

static void intern_blocks ( opt_state_t opt_state,
struct icode ic 
)
static

Definition at line 2354 of file optimize.c.

References opt_state_t::blocks, eq_blk(), isMarked, JF, JT, block::link, mark_code(), and opt_state_t::n_blocks.

Referenced by bpf_optimize().

◆ link_inedge()

static void link_inedge ( struct edge parent,
struct block child 
)
inlinestatic

Definition at line 2127 of file optimize.c.

References block::in_edges, and edge::next.

Referenced by find_inedges().

◆ lowest_set_bit()

static u_int lowest_set_bit ( int  mask)
static

Definition at line 163 of file optimize.c.

Referenced by opt_j().

◆ make_marks()

static void make_marks ( struct icode ic,
struct block p 
)
static

Definition at line 2297 of file optimize.c.

References BPF_CLASS, BPF_RET, stmt::code, isMarked, JF, JT, Mark, and block::s.

Referenced by mark_code().

◆ mark_code()

static void mark_code ( struct icode ic)
static

Definition at line 2313 of file optimize.c.

References icode::cur_mark, make_marks(), and icode::root.

Referenced by intern_blocks().

◆ number_blks_r()

static void number_blks_r ( opt_state_t opt_state,
struct icode ic,
struct block p 
)
static

Definition at line 2458 of file optimize.c.

References opt_state_t::blocks, block::id, isMarked, JF, JT, Mark, opt_state_t::n_blocks, and opt_error().

Referenced by opt_init().

◆ opt_blk()

◆ opt_blks()

static void opt_blks ( opt_state_t opt_state,
struct icode ic,
int  do_stmts 
)
static

◆ opt_cleanup()

static void opt_cleanup ( opt_state_t opt_state)
static

◆ opt_deadstores()

static void opt_deadstores ( opt_state_t opt_state,
register struct block b 
)
static

◆ opt_error()

static void opt_error ( opt_state_t opt_state,
const char *  fmt,
  ... 
)
static

◆ opt_init()

◆ opt_j()

◆ opt_loop()

static void opt_loop ( opt_state_t opt_state,
struct icode ic,
int  do_stmts 
)
static

◆ opt_not()

static void opt_not ( struct block b)
static

Definition at line 882 of file optimize.c.

References JF, and JT.

Referenced by opt_peep().

◆ opt_peep()

◆ opt_root()

static void opt_root ( struct block **  b)
static

Definition at line 2156 of file optimize.c.

References BPF_CLASS, BPF_JMP, BPF_RET, JF, JT, slist::s, and sappend().

Referenced by bpf_optimize().

◆ opt_stmt()

◆ or_pullup()

static void or_pullup ( opt_state_t opt_state,
struct block b 
)
static

Definition at line 1817 of file optimize.c.

References A_ATOM, opt_state_t::done, block::id, block::in_edges, JF, JT, N_ATOMS, edge::next, edge::pred, SET_MEMBER, and block::val.

Referenced by opt_blks().

◆ propedom()

static void propedom ( opt_state_t opt_state,
struct edge ep 
)
static

Definition at line 456 of file optimize.c.

References opt_state_t::edgewords, edge::edom, block::ef, block::et, edge::id, SET_INSERT, SET_INTERSECT, and edge::succ.

Referenced by find_edom().

◆ slength()

static u_int slength ( struct slist s)
static

Definition at line 2430 of file optimize.c.

References stmt::code, NOP, and block::s.

Referenced by convert_code_r(), count_stmts(), and opt_init().

◆ this_op()

static struct slist* this_op ( struct slist s)
inlinestatic

Definition at line 874 of file optimize.c.

References stmt::code, NOP, and slist::s.

Referenced by opt_peep().

◆ use_conflict()

static int use_conflict ( struct block b,
struct block succ 
)
static

Definition at line 1590 of file optimize.c.

References ATOMELEM, N_ATOMS, block::out_use, edge::succ, and block::val.

Referenced by opt_j().

◆ vstore()

static void vstore ( struct stmt s,
bpf_u_int32 valp,
bpf_u_int32  newval,
int  alter 
)
inlinestatic

Definition at line 768 of file optimize.c.

References stmt::code, NOP, and VAL_UNKNOWN.

Referenced by opt_stmt().