This series implements a prototype of using Header Space Analysis (HSA)
for OVS OpenFlow table analysis. The implementation allows users to find
all possible output ports with the input header format reachable from a
specified input port. It also allows users to check if there is any loop
formed in the OpenFlow table.
There are two major limitations of the prototype. Firstly, only a limited
set of OFPACT_* actions are supported and extending to work with more actions
can be very complicated. Secondly, the implementation is in single thread,
and can take 20+ mins to run on a production setup with ~100 OpenFlow rules.
Since this is a very complicated work, I'd like to post the prototype out
for high-level discussions (e.g. feasibility, design, multi-threading).
Sincerely welcome any comments.
==========================
Example - Find All Outputs
==========================
root:# ovs-appctl hsa/detect-leak br0 100
Header-Space init done:
reg0=0,reg1=0,reg2=0,reg3=0,reg4=0,reg5=0,reg6=0,reg7=0,metadata=0,in_port=100
Flows dump from bridge (br0):
table_id=0, priority=3,ip,in_port=100,nw_src=10.1.0.0/16,actions=output:200
table_id=0, priority=2,ip,in_port=100,nw_src=20.2.0.0/16,actions=drop
table_id=0,
priority=1,tcp,tun_id=0xffffffffffffffff,in_port=100,nw_src=30.1.0.0/16,tp_src=10,actions=output:200
OUTPUT
======
Output Port No Input Header Space
============== ==================
200
ip,reg0=0,reg1=0,reg2=0,reg3=0,reg4=0,reg5=0,reg6=0,reg7=0,metadata=0,in_port=100,nw_src=10.1.0.0/16
Output Port No Input Header Space
============== ==================
200
tcp,reg0=0,reg1=0,reg2=0,reg3=0,reg4=0,reg5=0,reg6=0,reg7=0,tun_id=0xffffffffffffffff,metadata=0,in_port=100,nw_src=30.1.0.0/16,tp_src=10
========================
Example - Loop Detection
========================
root:# ovs-appctl hsa/detect-loop br0 100
Header-Space init done:
reg0=0,reg1=0,reg2=0,reg3=0,reg4=0,reg5=0,reg6=0,reg7=0,metadata=0,in_port=100
Flows dump from bridge (br0):
table_id=0, priority=3,ip,in_port=100,nw_src=10.1.0.0/16,actions=resubmit(,1)
table_id=1, ip,in_port=100,nw_dst=20.2.0.0/16,actions=resubmit(,0)
OUTPUT
======
Input Header Space
==================
ip,reg0=0,reg1=0,reg2=0,reg3=0,reg4=0,reg5=0,reg6=0,reg7=0,metadata=0,in_port=100,nw_src=10.1.0.0/16,nw_dst=20.2.0.0/16
=========
Loop Path (Infinite Loop)
=========
table_id=0, priority=3,ip,in_port=100,nw_src=10.1.0.0/16,actions=resubmit(,1)
table_id=1, ip,in_port=100,nw_dst=20.2.0.0/16,actions=resubmit(,0)
table_id=0, priority=3,ip,in_port=100,nw_src=10.1.0.0/16,actions=resubmit(,1)
table_id=1, ip,in_port=100,nw_dst=20.2.0.0/16,actions=resubmit(,0)
table_id=0, priority=3,ip,in_port=100,nw_src=10.1.0.0/16,actions=resubmit(,1)
table_id=1, ip,in_port=100,nw_dst=20.2.0.0/16,actions=resubmit(,0)
table_id=0, priority=3,ip,in_port=100,nw_src=10.1.0.0/16,actions=resubmit(,1)
table_id=1, ip,in_port=100,nw_dst=20.2.0.0/16,actions=resubmit(,0)
table_id=0, priority=3,ip,in_port=100,nw_src=10.1.0.0/16,actions=resubmit(,1)
table_id=1, ip,in_port=100,nw_dst=20.2.0.0/16,actions=resubmit(,0)
table_id=0, priority=3,ip,in_port=100,nw_src=10.1.0.0/16,actions=resubmit(,1)
table_id=1, ip,in_port=100,nw_dst=20.2.0.0/16,actions=resubmit(,0)
table_id=0, priority=3,ip,in_port=100,nw_src=10.1.0.0/16,actions=resubmit(,1)
table_id=1, ip,in_port=100,nw_dst=20.2.0.0/16,actions=resubmit(,0)
table_id=0, priority=3,ip,in_port=100,nw_src=10.1.0.0/16,actions=resubmit(,1)
table_id=1, ip,in_port=100,nw_dst=20.2.0.0/16,actions=resubmit(,0)
table_id=0, priority=3,ip,in_port=100,nw_src=10.1.0.0/16,actions=resubmit(,1)
table_id=1, ip,in_port=100,nw_dst=20.2.0.0/16,actions=resubmit(,0)
table_id=0, priority=3,ip,in_port=100,nw_src=10.1.0.0/16,actions=resubmit(,1)
table_id=1, ip,in_port=100,nw_dst=20.2.0.0/16,actions=resubmit(,0)
table_id=0, priority=3,ip,in_port=100,nw_src=10.1.0.0/16,actions=resubmit(,1)
table_id=1, ip,in_port=100,nw_dst=20.2.0.0/16,actions=resubmit(,0)
table_id=0, priority=3,ip,in_port=100,nw_src=10.1.0.0/16,actions=resubmit(,1)
table_id=1, ip,in_port=100,nw_dst=20.2.0.0/16,actions=resubmit(,0)
table_id=0, priority=3,ip,in_port=100,nw_src=10.1.0.0/16,actions=resubmit(,1)
table_id=1, ip,in_port=100,nw_dst=20.2.0.0/16,actions=resubmit(,0)
table_id=0, priority=3,ip,in_port=100,nw_src=10.1.0.0/16,actions=resubmit(,1)
table_id=1, ip,in_port=100,nw_dst=20.2.0.0/16,actions=resubmit(,0)
table_id=0, priority=3,ip,in_port=100,nw_src=10.1.0.0/16,actions=resubmit(,1)
table_id=1, ip,in_port=100,nw_dst=20.2.0.0/16,actions=resubmit(,0)
table_id=0, priority=3,ip,in_port=100,nw_src=10.1.0.0/16,actions=resubmit(,1)
Alex Wang (4):
ovs_list: Extend list functions.
hsa-match: Sparse representation of a byte array derived from
"struct match".
flow: Add supporting functions for HSA.
ofprot-dpif-hsa: Implement HSA prototype.
lib/automake.mk | 2 +
lib/flow.c | 43 ++
lib/flow.h | 5 +
lib/hsa-match.c | 374 +++++++++++
lib/hsa-match.h | 92 +++
lib/list.h | 67 ++
ofproto/automake.mk | 2 +
ofproto/ofproto-dpif-hsa.c | 1572 ++++++++++++++++++++++++++++++++++++++++++++
ofproto/ofproto-dpif-hsa.h | 21 +
ofproto/ofproto-dpif.c | 2 +
tests/automake.mk | 2 +
tests/library.at | 7 +-
tests/test-hsa-match.c | 171 +++++
tests/test-list.c | 106 +++
14 files changed, 2465 insertions(+), 1 deletion(-)
create mode 100644 lib/hsa-match.c
create mode 100644 lib/hsa-match.h
create mode 100644 ofproto/ofproto-dpif-hsa.c
create mode 100644 ofproto/ofproto-dpif-hsa.h
create mode 100644 tests/test-hsa-match.c
--
1.7.9.5
_______________________________________________
dev mailing list
[email protected]
http://openvswitch.org/mailman/listinfo/dev
