issue: https://github.com/the-tcpdump-group/libpcap/pull/319

Merge branch 'master' of https://github.com/solofox/libpcap into solofox-master

10 files changed, 446 insertions, 3 deletions

diff --git a/optimize.c b/optimize.c
index feaf2017..ada20197 100644
--- a/optimize.c
+++ b/optimize.c
@@ -2244,7 +2244,92 @@ install_bpf_program(pcap_t *p, struct bpf_program *fp)
 
 #ifdef BDEBUG
 static void
-opt_dump(struct block *root)
+dot_dump_node(struct block *block, struct bpf_program *prog, FILE *out)
+{
+	int icount, noffset;
+	int i;
+
+	if (block == NULL || isMarked(block))
+		return;
+	Mark(block);
+
+	icount = slength(block->stmts) + 1 + block->longjt + block->longjf;
+	noffset = min(block->offset + icount, (int)prog->bf_len);
+
+	fprintf(out, "\tblock%d [shape=ellipse, id=\"block-%d\" label=\"BLOCK%d\\n", block->id, block->id, block->id);
+	for (i = block->offset; i < noffset; i++) {
+		fprintf(out, "\\n%s", bpf_image(prog->bf_insns + i, i));
+	}
+	fprintf(out, "\" tooltip=\"");
+	for (i = 0; i < BPF_MEMWORDS; i++)
+		if (block->val[i] != 0)
+			fprintf(out, "val[%d]=%d ", i, block->val[i]);
+	fprintf(out, "val[A]=%d ", block->val[A_ATOM]);
+	fprintf(out, "val[X]=%d", block->val[X_ATOM]);
+	fprintf(out, "\"");
+	if (JT(block) == NULL)
+		fprintf(out, ", peripheries=2");
+	fprintf(out, "];\n");
+
+	dot_dump_node(JT(block), prog, out);
+	dot_dump_node(JF(block), prog, out);
+}
+static void
+dot_dump_edge(struct block *block, FILE *out)
+{
+	if (block == NULL || isMarked(block))
+		return;
+	Mark(block);
+
+	if (JT(block)) {
+		fprintf(out, "\t\"block%d\":se -> \"block%d\":n [label=\"T\"]; \n",
+				block->id, JT(block)->id);
+		fprintf(out, "\t\"block%d\":sw -> \"block%d\":n [label=\"F\"]; \n",
+			   block->id, JF(block)->id);
+	}
+	dot_dump_edge(JT(block), out);
+	dot_dump_edge(JF(block), out);
+}
+/* Output the block CFG using graphviz/DOT language
+ * In the CFG, block's code, value index for each registers at EXIT,
+ * and the jump relationship is show.
+ *
+ * example DOT for BPF `ip src host 1.1.1.1' is:
+    digraph BPF {
+    	block0 [shape=ellipse, id="block-0" label="BLOCK0\n\n(000) ldh      [12]\n(001) jeq      #0x800           jt 2	jf 5" tooltip="val[A]=0 val[X]=0"];
+    	block1 [shape=ellipse, id="block-1" label="BLOCK1\n\n(002) ld       [26]\n(003) jeq      #0x1010101       jt 4	jf 5" tooltip="val[A]=0 val[X]=0"];
+    	block2 [shape=ellipse, id="block-2" label="BLOCK2\n\n(004) ret      #68" tooltip="val[A]=0 val[X]=0", peripheries=2];
+    	block3 [shape=ellipse, id="block-3" label="BLOCK3\n\n(005) ret      #0" tooltip="val[A]=0 val[X]=0", peripheries=2];
+    	"block0":se -> "block1":n [label="T"];
+    	"block0":sw -> "block3":n [label="F"];
+    	"block1":se -> "block2":n [label="T"];
+    	"block1":sw -> "block3":n [label="F"];
+    }
+ *
+ *  After install graphviz on http://www.graphviz.org/, save it as bpf.dot
+ *  and run `dot -Tpng -O bpf.dot' to draw the graph.
+ */
+static void
+dot_dump(struct block *root)
+{
+	struct bpf_program f;
+	FILE *out = stdout;
+
+	memset(bids, 0, sizeof bids);
+	f.bf_insns = icode_to_fcode(root, &f.bf_len);
+
+	fprintf(out, "digraph BPF {\n");
+	unMarkAll();
+	dot_dump_node(root, &f, out);
+	unMarkAll();
+	dot_dump_edge(root, out);
+	fprintf(out, "}\n");
+
+	free((char *)f.bf_insns);
+}
+
+static void
+plain_dump(struct block *root)
 {
 	struct bpf_program f;
 
@@ -2254,4 +2339,17 @@ opt_dump(struct block *root)
 	putchar('\n');
 	free((char *)f.bf_insns);
 }
+static void
+opt_dump(struct block *root)
+{
+	/* if optimizer debugging is enabled, output DOT graph
+	 * `dflag=4' is equivalent to -dddd to follow -d/-dd/-ddd
+     * convention in tcpdump command line
+	 */
+	if (dflag > 3)
+		dot_dump(root);
+	else
+		plain_dump(root);
+}
+
 #endif
diff --git a/tests/BPF/1.txt b/tests/BPF/1.txt
new file mode 100644
index 00000000..66086952
--- /dev/null
+++ b/tests/BPF/1.txt
@@ -0,0 +1,2 @@
+# common block merging, same block elimination, result propogation
+host 192.168.1.1
diff --git a/tests/BPF/2.txt b/tests/BPF/2.txt
new file mode 100644
index 00000000..e9bc1165
--- /dev/null
+++ b/tests/BPF/2.txt
@@ -0,0 +1,2 @@
+# common block merging
+port 80
diff --git a/tests/BPF/3.txt b/tests/BPF/3.txt
new file mode 100644
index 00000000..6c08d3d0
--- /dev/null
+++ b/tests/BPF/3.txt
@@ -0,0 +1 @@
+tcp[tcpflags]&tcp-syn != 0 or tcp[tcpflags]&tcp-fin != 0 or tcp[tcpflags]&tcp-rst != 0
diff --git a/tests/BPF/4.txt b/tests/BPF/4.txt
new file mode 100644
index 00000000..f705d8ff
--- /dev/null
+++ b/tests/BPF/4.txt
@@ -0,0 +1,2 @@
+# or pullup
+ether[12:2] = 0x800 or ether[12:2] = 0x8100 or ether[0] & 0x80 != 0 or ether[12:2] = 0x9100 
diff --git a/tests/BPF/5.txt b/tests/BPF/5.txt
new file mode 100644
index 00000000..23fc0ca5
--- /dev/null
+++ b/tests/BPF/5.txt
@@ -0,0 +1 @@
+vlan 186 and ip
diff --git a/tests/BPF/6.txt b/tests/BPF/6.txt
new file mode 100644
index 00000000..694c185b
--- /dev/null
+++ b/tests/BPF/6.txt
@@ -0,0 +1 @@
+ip and ((icmp and dst host 1.1.1.1 and not host 2.2.2.2) or (host 1.1.1.1 and src host 3.3.3.3))
diff --git a/tests/BPF/7.txt b/tests/BPF/7.txt
new file mode 100644
index 00000000..33978a4e
--- /dev/null
+++ b/tests/BPF/7.txt
@@ -0,0 +1 @@
+not vlan and tcp port 80
diff --git a/tests/filtertest.c b/tests/filtertest.c
index a36490d4..e45db21e 100644
--- a/tests/filtertest.c
+++ b/tests/filtertest.c
@@ -57,6 +57,9 @@ static void warn(const char *, ...)
 extern int optind;
 extern int opterr;
 extern char *optarg;
+#ifdef BDEBUG
+int dflag;
+#endif
 
 /*
  * On Windows, we need to open the file in binary mode, so that
@@ -178,7 +181,9 @@ main(int argc, char **argv)
 {
 	char *cp;
 	int op;
+#ifndef BDEBUG
 	int dflag;
+#endif
 	char *infile;
 	int Oflag;
 	long snaplen;
@@ -193,11 +198,19 @@ main(int argc, char **argv)
 	if(wsockinit() != 0) return 1;
 #endif /* WIN32 */
 
+#ifndef BDEBUG
 	dflag = 1;
+#else
+	/* if optimizer debugging is enabled, output DOT graph
+	 * `dflag=4' is equivalent to -dddd to follow -d/-dd/-ddd
+     * convention in tcpdump command line
+	 */
+	dflag = 4;
+#endif
 	infile = NULL;
 	Oflag = 1;
 	snaplen = 68;
-  
+
 	if ((cp = strrchr(argv[0], '/')) != NULL)
 		program_name = cp + 1;
 	else
@@ -258,7 +271,7 @@ main(int argc, char **argv)
 		if (p == argv[optind] || *p != '\0')
 			error("invalid data link type %s", argv[optind]);
 	}
-	
+
 	if (infile)
 		cmdbuf = read_infile(infile);
 	else
@@ -270,8 +283,21 @@ main(int argc, char **argv)
 
 	if (pcap_compile(pd, &fcode, cmdbuf, Oflag, netmask) < 0)
 		error("%s", pcap_geterr(pd));
+
 	if (!bpf_validate(fcode.bf_insns, fcode.bf_len))
 		warn("Filter doesn't pass validation");
+
+#ifdef BDEBUG
+	// replace line feed with space
+	for (cp = cmdbuf; *cp != '\0'; ++cp) {
+		if (*cp == '\r' || *cp == '\n') {
+			*cp = ' ';
+		}
+	}
+	// only show machine code if BDEBUG defined, since dflag > 3
+	printf("machine codes for filter: %s\n", cmdbuf);
+#endif
+
 	bpf_dump(&fcode, dflag);
 	pcap_close(pd);
 	exit(0);
diff --git a/tests/visopts.py b/tests/visopts.py
new file mode 100755
index 00000000..f3853125
--- /dev/null
+++ b/tests/visopts.py
@@ -0,0 +1,309 @@
+#!/usr/bin/env python
+
+"""
+This program parse the output from pcap_compile() to visualize the CFG after
+each optimize phase.
+
+Usage guide:
+1. Enable optimizier debugging code when configure libpcap, 
+   and build libpcap & filtertest
+       ./configure --enable-optimizer-dbg
+       make
+       make filtertest
+2. Run filtertest to compile BPF expression, save to output a.txt
+       ./filtertest EN10MB host 192.168.1.1 > a.txt
+3. Send a.txt to this program's standard input
+       cat a.txt | tests/visopts.py
+4. Step 2&3 can be merged: 
+       ./filtertest EN10MB host 192.168.1.1 | tests/visopts.py
+5. The standard output is something like this:
+       generated files under directory: /tmp/visopts-W9ekBw
+         the directory will be removed when this programs finished.
+       open this link: http://localhost:39062/expr1.html
+6. Using open link at the 3rd line `http://localhost:39062/expr1.html' 
+
+Note:
+1. CFG graph is translated to SVG document, expr1.html embeded them as external
+   document. If you open expr1.html as local file using file:// protocol, some 
+   browsers will deny such requests so the web pages will not shown properly.
+   For chrome, you can run it using following command to avoid this: 
+       chromium --disable-web-security
+   That's why this program start a localhost http server.
+2. expr1.html use jquery from http://ajax.googleapis.com, so you need internet 
+   access to show the web page. 
+"""
+
+import sys, os
+import string
+import subprocess
+import json
+
+html_template = string.Template("""
+<html>
+  <head>
+    <title>BPF compiler optimization phases for $expr </title>
+    <style type="text/css">
+      .hc {
+         /* half width container */
+         display: inline-block;
+         float: left;
+         width: 50%;
+      }
+    </style>
+
+    <script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.10.2/jquery.min.js"/></script>
+    <!--script type="text/javascript" src="./jquery.min.js"/></script-->
+    <script type="text/javascript">
+      var expr = '$expr';
+      var exprid = 1;
+      var gcount = $gcount;
+      var logs = JSON.parse('$logs');
+      logs[gcount] = "";
+
+      var leftsvg = null;
+      var rightsvg = null;
+
+      function gurl(index) {
+         index += 1;
+         if (index < 10)
+           s = "00" + index;
+         else if (index < 100) 
+           s = "0" + index;
+         else 
+           s = "" + index;
+         return "./expr" + exprid + "_g" + s + ".svg"
+      }
+
+      function annotate_svgs() {
+         if (!leftsvg || !rightsvg) return;
+
+         $$.each([$$(leftsvg), $$(rightsvg)], function() {
+           $$(this).find("[id|='block'][opacity]").each(function() {
+             $$(this).removeAttr('opacity');
+            });
+          });
+         
+         $$(leftsvg).find("[id|='block']").each(function() {
+           var has = $$(rightsvg).find("#" + this.id).length != 0;
+           if (!has) $$(this).attr("opacity", "0.4");
+           else {
+             $$(this).click(function() {
+                var target = $$(rightsvg).find("#" + this.id);
+                var offset = $$("#rightsvgc").offset().top + target.position().top;
+                window.scrollTo(0, offset);
+                target.focus();
+             });
+           }
+          });
+         $$(rightsvg).find("[id|='block']").each(function() {
+           var has = $$(leftsvg).find("#" + this.id).length != 0;
+           if (!has) $$(this).attr("opacity", "0.4");
+           else {
+             $$(this).click(function() {
+                var target = $$(leftsvg).find("#" + this.id);
+                var offset = $$("#leftsvgc").offset().top + target.position().top;
+                window.scrollTo(0, offset);
+                target.focus();
+             });
+           }
+          });  
+      }
+
+      function init_svgroot(svg) {
+         svg.setAttribute("width", "100%");
+         svg.setAttribute("height", "100%");
+      }
+      function wait_leftsvg() {
+         if (leftsvg) return;
+         var doc = document.getElementById("leftsvgc").getSVGDocument();
+         if (doc == null) {
+            setTimeout(wait_leftsvg, 500);
+            return;
+         }
+         leftsvg = doc.documentElement;
+         //console.log(leftsvg);
+         // initialize it
+         init_svgroot(leftsvg);
+         annotate_svgs();
+      }
+      function wait_rightsvg() {
+         if (rightsvg) return;
+         var doc = document.getElementById("rightsvgc").getSVGDocument();
+         if (doc == null) {
+            setTimeout(wait_rightsvg, 500);
+            return;
+         }
+         rightsvg = doc.documentElement;
+         //console.log(rightsvg);
+         // initialize it
+         init_svgroot(rightsvg);
+         annotate_svgs();
+      }
+      function load_left(index) {
+        var url = gurl(index);
+        var frag = "<embed id='leftsvgc'  type='image/svg+xml' pluginspage='http://www.adobe.com/svg/viewer/install/' src='" + url + "'/>";
+        $$("#lsvg").html(frag);
+        $$("#lcomment").html(logs[index]);
+        $$("#lsvglink").attr("href", url);
+        leftsvg = null;
+        wait_leftsvg();
+      }
+      function load_right(index) {
+        var url = gurl(index);
+        var frag = "<embed id='rightsvgc' type='image/svg+xml' pluginspage='http://www.adobe.com/svg/viewer/install/' src='" + url + "'/>";
+        $$("#rsvg").html(frag);
+        $$("#rcomment").html(logs[index]);
+        $$("#rsvglink").attr("href", url);
+        rightsvg = null;
+        wait_rightsvg();
+      }
+
+      $$(document).ready(function() {
+        for (var i = 0; i < gcount; i++) {
+          var opt = "<option value='" + i + "'>loop" + i + " -- " + logs[i] + "</option>"; 
+          $$("#lselect").append(opt);
+          $$("#rselect").append(opt);
+        }
+        var on_selected = function() {
+          var index = parseInt($$(this).children("option:selected").val());
+          if (this.id == "lselect")
+             load_left(index);
+          else 
+             load_right(index);
+        }
+        $$("#lselect").change(on_selected);
+        $$("#rselect").change(on_selected);
+
+        $$("#backward").click(function() {
+          var index = parseInt($$("#lselect option:selected").val());
+          if (index <= 0) return;
+          $$("#lselect").val(index - 1).change();
+          $$("#rselect").val(index).change();
+        });        
+        $$("#forward").click(function() {
+          var index = parseInt($$("#rselect option:selected").val());
+          if (index >= gcount - 1) return;
+          $$("#lselect").val(index).change();
+          $$("#rselect").val(index + 1).change();
+        });
+
+        if (gcount >= 1) $$("#lselect").val(0).change();
+        if (gcount >= 2) $$("#rselect").val(1).change();
+      });
+    </script>
+  </head>
+  <body style="width: 96%">
+    <div>
+      <h1>$expr</h1>
+      <div style="text-align: center;">
+        <button id="backward" type="button">&lt;&lt;</button>
+          &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
+        <button id="forward" type="button">&gt;&gt;</button>
+      </div>
+    </div>
+    <br/>
+    <div style="clear: both;">
+       <div class="hc lc">
+        <select id="lselect"></select>
+        <a id="lsvglink" target="_blank">open this svg in browser</a>
+        <p id="lcomment"></p>
+       </div>
+       <div class="hc rc">
+        <select id="rselect"></select>
+        <a id="rsvglink" target="_blank">open this svg in browser</a>
+        <p id="rcomment"></p>
+       </div>
+    </div>
+    <br/>
+    <div style="clear: both;">
+       <div id="lsvg"  class="hc lc"></div>
+       <div id="rsvg" class="hc rc"></div>
+    </div>
+  </body>
+</html>
+""")
+
+def write_html(expr, gcount, logs):
+    logs = map(lambda s: s.strip().replace("\n", "<br/>"), logs)
+    
+    global html_template
+    html = html_template.safe_substitute(expr=expr.encode("string-escape"), gcount=gcount, logs=json.dumps(logs).encode("string-escape"))
+    with file("expr1.html", "wt") as f:
+        f.write(html)
+
+def render_on_html(infile):
+    expr = None
+    gid = 1
+    log = ""
+    dot = ""
+    indot = 0
+    logs = []
+
+    for line in infile:
+        if line.startswith("machine codes for filter:"):
+            expr = line[len("machine codes for filter:"):].strip()
+            break
+        elif line.startswith("digraph BPF {"):
+            indot = 1
+            dot = line
+        elif indot:
+            dot += line
+            if line.startswith("}"):
+                indot = 2
+        else:
+            log += line
+            
+        if indot == 2:
+            p = subprocess.Popen(['dot', '-Tsvg'], stdin=subprocess.PIPE, stdout=subprocess.PIPE)
+            svg = p.communicate(dot)[0]
+            with file("expr1_g%03d.svg" % (gid), "wt") as f:
+                f.write(svg)
+
+            logs.append(log)
+            gid += 1
+            log = ""
+            dot = ""
+            indot = 0
+            
+    if indot != 0:
+        #unterminated dot graph for expression
+        return False
+    if expr is None:
+        # BPF parser encounter error(s)
+        return False
+    write_html(expr, gid - 1, logs)
+    return True
+
+def run_httpd():
+    import SimpleHTTPServer
+    import SocketServer
+    
+    class MySocketServer(SocketServer.TCPServer):
+        allow_reuse_address = True
+    Handler = SimpleHTTPServer.SimpleHTTPRequestHandler
+    httpd = MySocketServer(("localhost", 0), Handler)
+    print "open this link: http://localhost:%d/expr1.html" % (httpd.server_address[1])
+    try:
+        httpd.serve_forever()
+    except KeyboardInterrupt as e:
+        pass
+
+def main():
+    import tempfile
+    import atexit
+    import shutil
+    os.chdir(tempfile.mkdtemp(prefix="visopts-"))
+    atexit.register(shutil.rmtree, os.getcwd())
+    print "generated files under directory: %s" % os.getcwd()
+    print "  the directory will be removed when this programs finished."
+
+    if not render_on_html(sys.stdin):
+        return 1
+    run_httpd()
+    return 0
+    
+if __name__ == "__main__":
+    if '-h' in sys.argv or '--help' in sys.argv:
+        print __doc__
+        exit(0)
+    exit(main())