[ovs-dev] [RFC PATCH 2/2] ofproto: Index flows by cookie.
Rajahalme, Jarno (NSN - FI/Espoo)
jarno.rajahalme at nsn.com
Mon Jun 17 11:45:49 UTC 2013
On Jun 17, 2013, at 3:55 , Jarno Rajahalme wrote:
> The simplest way for an OpenFlow controller to refer to a (set of) flows
> is by a controller-issued flow cookie. Make this fast by inserting
> flows with non-zero cookies to a hmap, and use that when flows are
> queried with a full cookie mask.
>
Here are some measurements on this, using a flow table with
138260 different flow like below, each flow with a different IP prefix,
a priority corresponding to the prefix length, and a unique cookie:
"ip nw_dst=91.216.208.0/24 cookie=4007532 priority=240 actions=drop"
For reference, setting up the flow table with "ovs-ofctl add-flows" from
a file takes about 20 seconds in a VM running on a dual-core laptop.
I measured the running time (with "time ovs-ofctl ...") with eight different methods.
Each consists of 138260 different flow deletes each targeting a specific
flow entry in the switch, emptying the flow table one flow entry at a time.
Each case is run only once, so the figures should not be taken too literally:
1) Cookie only (del-flows br0 "cookie=4007532/-1"):
Before: 25 min 50 sec After: 20 sec
2) Cookie strict (del-flows --strict br0 "ip nw_dst=91.216.208.0/24 \
cookie=4007532/-1 priority=240"):
Before: 33 sec After: 21 sec
3) No cookie (del-flows br0 "ip nw_dst=91.216.208.0/24"):
Before: 18 min 18 sec After: 19 min
4) No cookie, strict (del-flows --strict br0 "ip nw_dst=91.216.208.0/24 \
priority=240"):
Before 24 sec After: 23 sec
5) Table+Cookie only (del-flows br0 "table=0 cookie=4007532/-1"):
Before: 25 min 18 sec After: 20 sec
6) Table+Cookie strict (del-flows --strict br0 "table=0 ip \
nw_dst=91.216.208.0/24 cookie=4007532/-1 priority=240"):
Before: 20 sec After: 20 sec
7) Table+No cookie (del-flows br0 "table=0 ip nw_dst=91.216.208.0/24"):
Before: 18 min 29 sec After: 18 min 59 sec
8) Table+No cookie, strict (del-flows --strict br0 "table=0 ip \
nw_dst=91.216.208.0/24 priority=240"):
Before 20 sec After: 20 sec
Conclusions: strict delete (and by extension, modify) is very efficient, but
always targets only one flow, and the controller needs to supply full flow
match, including the priority. Specifying the flow table might be beneficial
if there are multiple large tables, but this was not really captured by the
tests above, as only one table was populated.
With the proposed update the controller can refer to flows using only a
(fully masked) cookie, possibly covering more than one flow del/mod very
efficiently. There does not seem to be any real performance penalty, but
controllers should still be careful with non-strict dels/flows with partially
masked cookies, as those will still be very expensive with non-trivial/large
flow tables.
Jarno
> Signed-off-by: Jarno Rajahalme <jarno.rajahalme at nsn.com>
> ---
> ofproto/ofproto-provider.h | 3 ++
> ofproto/ofproto.c | 104 +++++++++++++++++++++++++++++++++++++++++---
> 2 files changed, 101 insertions(+), 6 deletions(-)
>
> diff --git a/ofproto/ofproto-provider.h b/ofproto/ofproto-provider.h
> index 23d9180..313610b 100644
> --- a/ofproto/ofproto-provider.h
> +++ b/ofproto/ofproto-provider.h
> @@ -69,6 +69,8 @@ struct ofproto {
> struct oftable *tables;
> int n_tables;
>
> + struct hmap cookies; /* Flows with non-zero cookie values */
> +
> /* Optimisation for flow expiry.
> * These flows should all be present in tables. */
> struct list expirable; /* Expirable 'struct rule"s in all tables. */
> @@ -203,6 +205,7 @@ struct rule {
> struct ofoperation *pending; /* Operation now in progress, if nonnull. */
>
> ovs_be64 flow_cookie; /* Controller-issued identifier. */
> + struct hmap_node cookie_node; /* In owning ofproto's cookies map */
>
> long long int created; /* Creation time. */
> long long int modified; /* Time of last modification. */
> diff --git a/ofproto/ofproto.c b/ofproto/ofproto.c
> index 7f9a88f..a5b3a08 100644
> --- a/ofproto/ofproto.c
> +++ b/ofproto/ofproto.c
> @@ -424,6 +424,7 @@ ofproto_create(const char *datapath_name, const char *datapath_type,
> ofproto->max_ports = OFPP_MAX;
> ofproto->tables = NULL;
> ofproto->n_tables = 0;
> + hmap_init(&ofproto->cookies);
> list_init(&ofproto->expirable);
> ofproto->connmgr = connmgr_create(ofproto, datapath_name, datapath_name);
> ofproto->state = S_OPENFLOW;
> @@ -2622,6 +2623,42 @@ handle_port_desc_stats_request(struct ofconn *ofconn,
> return 0;
> }
>
> +static uint32_t
> +hash_cookie(ovs_be64 cookie)
> +{
> + return hash_2words((uint32_t)(cookie >> 32),(uint32_t)cookie);
> +}
> +
> +static void
> +cookies_insert(struct ofproto *ofproto, struct rule *rule)
> +{
> + if (rule->flow_cookie) {
> + hmap_insert(&ofproto->cookies, &rule->cookie_node,
> + hash_cookie(rule->flow_cookie));
> + }
> +}
> +
> +static void
> +cookies_remove(struct ofproto *ofproto, struct rule *rule)
> +{
> + if (rule->flow_cookie) {
> + hmap_remove(&ofproto->cookies, &rule->cookie_node);
> + }
> +}
> +
> +static void
> +ofproto_rule_change_cookie(struct ofproto *ofproto, struct rule *rule,
> + ovs_be64 new_cookie)
> +{
> + if (new_cookie != rule->flow_cookie) {
> + cookies_remove(ofproto, rule);
> +
> + rule->flow_cookie = new_cookie;
> +
> + cookies_insert(ofproto, rule);
> + }
> +}
> +
> static void
> calc_duration(long long int start, long long int now,
> uint32_t *sec, uint32_t *nsec)
> @@ -2727,6 +2764,32 @@ collect_rules_loose(struct ofproto *ofproto, uint8_t table_id,
>
> list_init(rules);
> cls_rule_init(&cr, match, 0);
> +
> + if (cookie && cookie_mask == UINT64_MAX) {
> + uint32_t hash = hash_cookie(cookie);
> + struct rule *rule;
> +
> + HMAP_FOR_EACH_WITH_HASH (rule, cookie_node, hash, &ofproto->cookies) {
> + if (table_id != rule->table_id && table_id != 0xff) {
> + continue;
> + }
> + if (ofproto_rule_is_hidden(rule)) {
> + continue;
> + }
> + if (cls_rule_is_loose_match(&rule->cr, &cr.match)) {
> + if (rule->pending) {
> + error = OFPROTO_POSTPONE;
> + goto exit;
> + }
> + if (rule->flow_cookie == cookie /* hmap collisions possible. */
> + && ofproto_rule_has_out_port(rule, out_port)) {
> + list_push_back(rules, &rule->ofproto_node);
> + }
> + }
> + }
> + goto exit;
> + }
> +
> FOR_EACH_MATCHING_TABLE (table, table_id, ofproto) {
> struct cls_cursor cursor;
> struct rule *rule;
> @@ -2778,6 +2841,32 @@ collect_rules_strict(struct ofproto *ofproto, uint8_t table_id,
>
> list_init(rules);
> cls_rule_init(&cr, match, priority);
> +
> + if (cookie && cookie_mask == UINT64_MAX) {
> + uint32_t hash = hash_cookie(cookie);
> + struct rule *rule;
> +
> + HMAP_FOR_EACH_WITH_HASH (rule, cookie_node, hash, &ofproto->cookies) {
> + if (table_id != rule->table_id && table_id != 0xff) {
> + continue;
> + }
> + if (ofproto_rule_is_hidden(rule)) {
> + continue;
> + }
> + if (cls_rule_equal(&rule->cr, &cr)) {
> + if (rule->pending) {
> + error = OFPROTO_POSTPONE;
> + goto exit;
> + }
> + if (rule->flow_cookie == cookie /* hmap collisions possible. */
> + && ofproto_rule_has_out_port(rule, out_port)) {
> + list_push_back(rules, &rule->ofproto_node);
> + }
> + }
> + }
> + goto exit;
> + }
> +
> FOR_EACH_MATCHING_TABLE (table, table_id, ofproto) {
> struct rule *rule;
>
> @@ -3275,7 +3364,6 @@ modify_flows__(struct ofproto *ofproto, struct ofconn *ofconn,
> LIST_FOR_EACH (rule, ofproto_node, rules) {
> struct ofoperation *op;
> bool actions_changed;
> - ovs_be64 new_cookie;
>
> /* FIXME: Implement OFPFF12_RESET_COUNTS */
>
> @@ -3288,12 +3376,12 @@ modify_flows__(struct ofproto *ofproto, struct ofconn *ofconn,
>
> actions_changed = !ofpacts_equal(fm->ofpacts, fm->ofpacts_len,
> rule->ofpacts, rule->ofpacts_len);
> - new_cookie = (fm->new_cookie != htonll(UINT64_MAX)
> - ? fm->new_cookie
> - : rule->flow_cookie);
>
> op = ofoperation_create(group, rule, OFOPERATION_MODIFY, 0);
> - rule->flow_cookie = new_cookie;
> +
> + if (fm->new_cookie != htonll(UINT64_MAX)) {
> + ofproto_rule_change_cookie(ofproto, rule, fm->new_cookie);
> + }
> if (actions_changed) {
> op->ofpacts = rule->ofpacts;
> op->ofpacts_len = rule->ofpacts_len;
> @@ -4332,7 +4420,7 @@ ofopgroup_complete(struct ofopgroup *group)
> if (!op->error) {
> rule->modified = time_msec();
> } else {
> - rule->flow_cookie = op->flow_cookie;
> + ofproto_rule_change_cookie(ofproto, rule, op->flow_cookie);
> if (op->ofpacts) {
> free(rule->ofpacts);
> rule->ofpacts = op->ofpacts;
> @@ -4861,6 +4949,7 @@ oftable_remove_rule(struct rule *rule)
> struct oftable *table = &ofproto->tables[rule->table_id];
>
> classifier_remove(&table->cls, &rule->cr);
> + cookies_remove(ofproto, rule);
> eviction_group_remove_rule(rule);
> if (!list_is_empty(&rule->expirable)) {
> list_remove(&rule->expirable);
> @@ -4881,9 +4970,12 @@ oftable_replace_rule(struct rule *rule)
> if (may_expire) {
> list_insert(&ofproto->expirable, &rule->expirable);
> }
> + cookies_insert(ofproto, rule);
>
> victim = rule_from_cls_rule(classifier_replace(&table->cls, &rule->cr));
> if (victim) {
> + cookies_remove(ofproto, victim);
> +
> if (!list_is_empty(&victim->expirable)) {
> list_remove(&victim->expirable);
> }
> --
> 1.7.10.4
>
More information about the dev
mailing list