From 98eaac36fc96c5168e76fd039d3d4aea97b6aa56 Mon Sep 17 00:00:00 2001 From: Jarno Rajahalme Date: Tue, 18 Jun 2013 19:48:14 +0300 Subject: [PATCH] ofproto: Index flows by cookie. 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 to a hash index, and use that when flows are queried, deleted, or modified with a full cookie mask. Signed-off-by: Jarno Rajahalme Signed-off-by: Ben Pfaff --- ofproto/ofproto-provider.h | 4 ++ ofproto/ofproto.c | 101 ++++++++++++++++++++++++++++++++++--- 2 files changed, 99 insertions(+), 6 deletions(-) diff --git a/ofproto/ofproto-provider.h b/ofproto/ofproto-provider.h index 23d9180c9..41b589f5f 100644 --- a/ofproto/ofproto-provider.h +++ b/ofproto/ofproto-provider.h @@ -23,6 +23,7 @@ #include "cfm.h" #include "classifier.h" #include "heap.h" +#include "hindex.h" #include "list.h" #include "ofp-errors.h" #include "ofp-util.h" @@ -69,6 +70,8 @@ struct ofproto { struct oftable *tables; int n_tables; + struct hindex cookies; /* Rules indexed on their 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 +206,7 @@ struct rule { struct ofoperation *pending; /* Operation now in progress, if nonnull. */ ovs_be64 flow_cookie; /* Controller-issued identifier. */ + struct hindex_node cookie_node; /* In owning ofproto's 'cookies' index. */ 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 7f9a88f92..eabe850a6 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; + hindex_init(&ofproto->cookies); list_init(&ofproto->expirable); ofproto->connmgr = connmgr_create(ofproto, datapath_name, datapath_name); ofproto->state = S_OPENFLOW; @@ -2622,6 +2623,39 @@ handle_port_desc_stats_request(struct ofconn *ofconn, return 0; } +static uint32_t +hash_cookie(ovs_be64 cookie) +{ + return hash_2words((OVS_FORCE uint64_t)cookie >> 32, + (OVS_FORCE uint64_t)cookie); +} + +static void +cookies_insert(struct ofproto *ofproto, struct rule *rule) +{ + hindex_insert(&ofproto->cookies, &rule->cookie_node, + hash_cookie(rule->flow_cookie)); +} + +static void +cookies_remove(struct ofproto *ofproto, struct rule *rule) +{ + hindex_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 +2761,32 @@ collect_rules_loose(struct ofproto *ofproto, uint8_t table_id, list_init(rules); cls_rule_init(&cr, match, 0); + + if (cookie_mask == htonll(UINT64_MAX)) { + struct rule *rule; + + HINDEX_FOR_EACH_WITH_HASH (rule, cookie_node, hash_cookie(cookie), + &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 /* Hash 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 +2838,32 @@ collect_rules_strict(struct ofproto *ofproto, uint8_t table_id, list_init(rules); cls_rule_init(&cr, match, priority); + + if (cookie_mask == htonll(UINT64_MAX)) { + struct rule *rule; + + HINDEX_FOR_EACH_WITH_HASH (rule, cookie_node, hash_cookie(cookie), + &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 /* Hash 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 +3361,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 +3373,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 +4417,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 +4946,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 +4967,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); } -- 2.43.0