#include "dynamic-string.h"
#include "hash.h"
#include "hmap.h"
+#include "meta-flow.h"
#include "netdev.h"
#include "nx-match.h"
#include "ofp-errors.h"
#include "pinsched.h"
#include "pktbuf.h"
#include "poll-loop.h"
+#include "random.h"
#include "shash.h"
#include "sset.h"
#include "timeval.h"
enum ofproto_state {
S_OPENFLOW, /* Processing OpenFlow commands. */
+ S_EVICT, /* Evicting flows from over-limit tables. */
S_FLUSH, /* Deleting all flow table rules. */
};
static void oftable_init(struct oftable *);
static void oftable_destroy(struct oftable *);
+static void oftable_set_name(struct oftable *, const char *name);
+
+static void oftable_disable_eviction(struct oftable *);
+static void oftable_enable_eviction(struct oftable *,
+ const struct mf_subfield *fields,
+ size_t n_fields);
+
static void oftable_remove_rule(struct rule *);
static struct rule *oftable_replace_rule(struct rule *);
static void oftable_substitute_rule(struct rule *old, struct rule *new);
-/* rule. */
-static void ofproto_rule_destroy__(struct rule *);
-static void ofproto_rule_send_removed(struct rule *, uint8_t reason);
+/* A set of rules within a single OpenFlow table (oftable) that have the same
+ * values for the oftable's eviction_fields. A rule to be evicted, when one is
+ * needed, is taken from the eviction group that contains the greatest number
+ * of rules.
+ *
+ * An oftable owns any number of eviction groups, each of which contains any
+ * number of rules.
+ *
+ * Membership in an eviction group is imprecise, based on the hash of the
+ * oftable's eviction_fields (in the eviction_group's id_node.hash member).
+ * That is, if two rules have different eviction_fields, but those
+ * eviction_fields hash to the same value, then they will belong to the same
+ * eviction_group anyway.
+ *
+ * (When eviction is not enabled on an oftable, we don't track any eviction
+ * groups, to save time and space.) */
+struct eviction_group {
+ struct hmap_node id_node; /* In oftable's "eviction_groups_by_id". */
+ struct heap_node size_node; /* In oftable's "eviction_groups_by_size". */
+ struct heap rules; /* Contains "struct rule"s. */
+};
+
+static struct rule *choose_rule_to_evict(struct oftable *);
+static void ofproto_evict(struct ofproto *);
+static uint32_t rule_eviction_priority(struct rule *);
/* ofport. */
static void ofport_destroy__(struct ofport *);
static int init_ports(struct ofproto *);
static void reinit_ports(struct ofproto *);
+/* rule. */
+static void ofproto_rule_destroy__(struct rule *);
+static void ofproto_rule_send_removed(struct rule *, uint8_t reason);
+static bool rule_is_modifiable(const struct rule *);
+static bool rule_is_hidden(const struct rule *);
+
/* OpenFlow. */
static enum ofperr add_flow(struct ofproto *, struct ofconn *,
const struct ofputil_flow_mod *,
const struct ofp_header *);
-
+static void delete_flow__(struct rule *, struct ofopgroup *);
static bool handle_openflow(struct ofconn *, struct ofpbuf *);
static enum ofperr handle_flow_mod__(struct ofproto *, struct ofconn *,
const struct ofputil_flow_mod *,
{
const struct ofproto_class *class;
struct ofproto *ofproto;
- struct oftable *table;
- int n_tables;
int error;
*ofprotop = NULL;
ofproto->vlan_bitmap = NULL;
ofproto->vlans_changed = false;
- error = ofproto->ofproto_class->construct(ofproto, &n_tables);
+ error = ofproto->ofproto_class->construct(ofproto);
if (error) {
VLOG_ERR("failed to open datapath %s: %s",
datapath_name, strerror(error));
return error;
}
- assert(n_tables >= 1 && n_tables <= 255);
- ofproto->n_tables = n_tables;
- ofproto->tables = xmalloc(n_tables * sizeof *ofproto->tables);
- OFPROTO_FOR_EACH_TABLE (table, ofproto) {
- oftable_init(table);
- }
+ assert(ofproto->n_tables);
ofproto->datapath_id = pick_datapath_id(ofproto);
VLOG_INFO("using datapath ID %016"PRIx64, ofproto->datapath_id);
return 0;
}
+void
+ofproto_init_tables(struct ofproto *ofproto, int n_tables)
+{
+ struct oftable *table;
+
+ assert(!ofproto->n_tables);
+ assert(n_tables >= 1 && n_tables <= 255);
+
+ ofproto->n_tables = n_tables;
+ ofproto->tables = xmalloc(n_tables * sizeof *ofproto->tables);
+ OFPROTO_FOR_EACH_TABLE (table, ofproto) {
+ oftable_init(table);
+ }
+}
+
void
ofproto_set_datapath_id(struct ofproto *p, uint64_t datapath_id)
{
}
}
+/* Sets the MAC aging timeout for the OFPP_NORMAL action on 'ofproto' to
+ * 'idle_time', in seconds. */
+void
+ofproto_set_mac_idle_time(struct ofproto *ofproto, unsigned idle_time)
+{
+ if (ofproto->ofproto_class->set_mac_idle_time) {
+ ofproto->ofproto_class->set_mac_idle_time(ofproto, idle_time);
+ }
+}
+
void
ofproto_set_desc(struct ofproto *p,
const char *mfr_desc, const char *hw_desc,
: false);
}
\f
+/* Configuration of OpenFlow tables. */
+
+/* Returns the number of OpenFlow tables in 'ofproto'. */
+int
+ofproto_get_n_tables(const struct ofproto *ofproto)
+{
+ return ofproto->n_tables;
+}
+
+/* Configures the OpenFlow table in 'ofproto' with id 'table_id' with the
+ * settings from 's'. 'table_id' must be in the range 0 through the number of
+ * OpenFlow tables in 'ofproto' minus 1, inclusive.
+ *
+ * For read-only tables, only the name may be configured. */
+void
+ofproto_configure_table(struct ofproto *ofproto, int table_id,
+ const struct ofproto_table_settings *s)
+{
+ struct oftable *table;
+
+ assert(table_id >= 0 && table_id < ofproto->n_tables);
+ table = &ofproto->tables[table_id];
+
+ oftable_set_name(table, s->name);
+
+ if (table->flags & OFTABLE_READONLY) {
+ return;
+ }
+
+ if (s->groups) {
+ oftable_enable_eviction(table, s->groups, s->n_groups);
+ } else {
+ oftable_disable_eviction(table);
+ }
+
+ table->max_flows = s->max_flows;
+ if (classifier_count(&table->cls) > table->max_flows
+ && table->eviction_fields) {
+ /* 'table' contains more flows than allowed. We might not be able to
+ * evict them right away because of the asynchronous nature of flow
+ * table changes. Schedule eviction for later. */
+ switch (ofproto->state) {
+ case S_OPENFLOW:
+ ofproto->state = S_EVICT;
+ break;
+ case S_EVICT:
+ case S_FLUSH:
+ /* We're already deleting flows, nothing more to do. */
+ break;
+ }
+ }
+}
+\f
bool
ofproto_has_snoops(const struct ofproto *ofproto)
{
struct rule *rule, *next_rule;
struct cls_cursor cursor;
+ if (table->flags & OFTABLE_HIDDEN) {
+ continue;
+ }
+
cls_cursor_init(&cursor, &table->cls, NULL);
CLS_CURSOR_FOR_EACH_SAFE (rule, next_rule, cr, &cursor) {
if (!rule->pending) {
}
}
-
switch (p->state) {
case S_OPENFLOW:
connmgr_run(p->connmgr, handle_openflow);
break;
+ case S_EVICT:
+ connmgr_run(p->connmgr, NULL);
+ ofproto_evict(p);
+ if (list_is_empty(&p->pending) && hmap_is_empty(&p->deletions)) {
+ p->state = S_OPENFLOW;
+ }
+ break;
+
case S_FLUSH:
connmgr_run(p->connmgr, NULL);
ofproto_flush__(p);
connmgr_wait(p->connmgr, true);
break;
+ case S_EVICT:
case S_FLUSH:
connmgr_wait(p->connmgr, false);
if (list_is_empty(&p->pending) && hmap_is_empty(&p->deletions)) {
struct ofopgroup *group = ofopgroup_create_unattached(ofproto);
ofoperation_create(group, rule, OFOPERATION_DELETE);
oftable_remove_rule(rule);
- rule->ofproto->ofproto_class->rule_destruct(rule);
+ ofproto->ofproto_class->rule_destruct(rule);
ofopgroup_submit(group);
return true;
}
static void
ofproto_rule_destroy__(struct rule *rule)
{
- free(rule->actions);
- rule->ofproto->ofproto_class->rule_dealloc(rule);
+ if (rule) {
+ free(rule->actions);
+ rule->ofproto->ofproto_class->rule_dealloc(rule);
+ }
}
/* This function allows an ofproto implementation to destroy any rules that
{
return rule->cr.priority > UINT16_MAX;
}
+
+static enum oftable_flags
+rule_get_flags(const struct rule *rule)
+{
+ return rule->ofproto->tables[rule->table_id].flags;
+}
+
+static bool
+rule_is_modifiable(const struct rule *rule)
+{
+ return !(rule_get_flags(rule) & OFTABLE_READONLY);
+}
\f
static enum ofperr
handle_echo_request(struct ofconn *ofconn, const struct ofp_header *oh)
}
static enum ofperr
-handle_packet_out(struct ofconn *ofconn, const struct ofp_header *oh)
+handle_packet_out(struct ofconn *ofconn, const struct ofp_packet_out *opo)
{
struct ofproto *p = ofconn_get_ofproto(ofconn);
- struct ofp_packet_out *opo;
- struct ofpbuf payload, *buffer;
- union ofp_action *ofp_actions;
- struct ofpbuf request;
+ struct ofputil_packet_out po;
+ struct ofpbuf *payload;
struct flow flow;
- size_t n_ofp_actions;
enum ofperr error;
- uint16_t in_port;
COVERAGE_INC(ofproto_packet_out);
return error;
}
- /* Get ofp_packet_out. */
- ofpbuf_use_const(&request, oh, ntohs(oh->length));
- opo = ofpbuf_pull(&request, offsetof(struct ofp_packet_out, actions));
-
- /* Get actions. */
- error = ofputil_pull_actions(&request, ntohs(opo->actions_len),
- &ofp_actions, &n_ofp_actions);
+ /* Decode message. */
+ error = ofputil_decode_packet_out(&po, opo);
if (error) {
return error;
}
/* Get payload. */
- if (opo->buffer_id != htonl(UINT32_MAX)) {
- error = ofconn_pktbuf_retrieve(ofconn, ntohl(opo->buffer_id),
- &buffer, NULL);
- if (error || !buffer) {
+ if (po.buffer_id != UINT32_MAX) {
+ error = ofconn_pktbuf_retrieve(ofconn, po.buffer_id, &payload, NULL);
+ if (error || !payload) {
return error;
}
- payload = *buffer;
} else {
- payload = request;
- buffer = NULL;
- }
-
- /* Get in_port and partially validate it.
- *
- * We don't know what range of ports the ofproto actually implements, but
- * we do know that only certain reserved ports (numbered OFPP_MAX and
- * above) are valid. */
- in_port = ntohs(opo->in_port);
- if (in_port >= OFPP_MAX && in_port != OFPP_LOCAL && in_port != OFPP_NONE) {
- return OFPERR_NXBRC_BAD_IN_PORT;
+ payload = xmalloc(sizeof *payload);
+ ofpbuf_use_const(payload, po.packet, po.packet_len);
}
/* Send out packet. */
- flow_extract(&payload, 0, 0, in_port, &flow);
- error = p->ofproto_class->packet_out(p, &payload, &flow,
- ofp_actions, n_ofp_actions);
- ofpbuf_delete(buffer);
+ flow_extract(payload, 0, 0, po.in_port, &flow);
+ error = p->ofproto_class->packet_out(p, payload, &flow,
+ po.actions, po.n_actions);
+ ofpbuf_delete(payload);
return error;
}
p->ofproto_class->get_tables(p, ots);
+ for (i = 0; i < p->n_tables; i++) {
+ const struct oftable *table = &p->tables[i];
+
+ if (table->name) {
+ ovs_strzcpy(ots[i].name, table->name, sizeof ots[i].name);
+ }
+
+ if (table->max_flows < ntohl(ots[i].max_entries)) {
+ ots[i].max_entries = htonl(table->max_flows);
+ }
+ }
+
ofconn_send_reply(ofconn, msg);
return 0;
}
}
static void
-calc_flow_duration__(long long int start, uint32_t *sec, uint32_t *nsec)
+calc_flow_duration__(long long int start, long long int now,
+ uint32_t *sec, uint32_t *nsec)
{
- long long int msecs = time_msec() - start;
+ long long int msecs = now - start;
*sec = msecs / 1000;
*nsec = (msecs % 1000) * (1000 * 1000);
}
}
+static struct oftable *
+next_visible_table(struct ofproto *ofproto, uint8_t table_id)
+{
+ struct oftable *table;
+
+ for (table = &ofproto->tables[table_id];
+ table < &ofproto->tables[ofproto->n_tables];
+ table++) {
+ if (!(table->flags & OFTABLE_HIDDEN)) {
+ return table;
+ }
+ }
+
+ return NULL;
+}
+
static struct oftable *
first_matching_table(struct ofproto *ofproto, uint8_t table_id)
{
if (table_id == 0xff) {
- return &ofproto->tables[0];
+ return next_visible_table(ofproto, 0);
} else if (table_id < ofproto->n_tables) {
return &ofproto->tables[table_id];
} else {
next_matching_table(struct ofproto *ofproto,
struct oftable *table, uint8_t table_id)
{
- return (table_id == 0xff && table < &ofproto->tables[ofproto->n_tables - 1]
- ? table + 1
+ return (table_id == 0xff
+ ? next_visible_table(ofproto, (table - ofproto->tables) + 1)
: NULL);
}
/* Assigns TABLE to each oftable, in turn, that matches TABLE_ID in OFPROTO:
*
* - If TABLE_ID is 0xff, this iterates over every classifier table in
- * OFPROTO.
+ * OFPROTO, skipping tables marked OFTABLE_HIDDEN.
*
* - If TABLE_ID is the number of a table in OFPROTO, then the loop iterates
- * only once, for that table.
+ * only once, for that table. (This can be used to access tables marked
+ * OFTABLE_HIDDEN.)
*
* - Otherwise, TABLE_ID isn't valid for OFPROTO, so the loop won't be
* entered at all. (Perhaps you should have validated TABLE_ID with
return 0;
}
+/* Returns 'age_ms' (a duration in milliseconds), converted to seconds and
+ * forced into the range of a uint16_t. */
+static int
+age_secs(long long int age_ms)
+{
+ return (age_ms < 0 ? 0
+ : age_ms >= UINT16_MAX * 1000 ? UINT16_MAX
+ : (unsigned int) age_ms / 1000);
+}
+
static enum ofperr
handle_flow_stats_request(struct ofconn *ofconn,
const struct ofp_stats_msg *osm)
ofputil_start_stats_reply(osm, &replies);
LIST_FOR_EACH (rule, ofproto_node, &rules) {
+ long long int now = time_msec();
struct ofputil_flow_stats fs;
fs.rule = rule->cr;
fs.cookie = rule->flow_cookie;
fs.table_id = rule->table_id;
- calc_flow_duration__(rule->created, &fs.duration_sec,
+ calc_flow_duration__(rule->created, now, &fs.duration_sec,
&fs.duration_nsec);
fs.idle_timeout = rule->idle_timeout;
fs.hard_timeout = rule->hard_timeout;
+ fs.idle_age = age_secs(now - rule->used);
+ fs.hard_age = age_secs(now - rule->modified);
ofproto->ofproto_class->rule_get_stats(rule, &fs.packet_count,
&fs.byte_count);
fs.actions = rule->actions;
ofproto->ofproto_class->get_netflow_ids(ofproto, engine_type, engine_id);
}
-/* Checks the fault status of CFM for 'ofp_port' within 'ofproto'. Returns 1
- * if CFM is faulted (generally indiciating a connectivity problem), 0 if CFM
- * is not faulted, and -1 if CFM is not enabled on 'ofp_port'. */
+/* Checks the fault status of CFM for 'ofp_port' within 'ofproto'. Returns a
+ * bitmask of 'cfm_fault_reason's to indicate a CFM fault (generally
+ * indicating a connectivity problem). Returns zero if CFM is not faulted,
+ * and -1 if CFM is not enabled on 'port'. */
int
ofproto_port_get_cfm_fault(const struct ofproto *ofproto, uint16_t ofp_port)
{
return OFPERR_NXFMFC_BAD_TABLE_ID;
}
+ if (table->flags & OFTABLE_READONLY) {
+ return OFPERR_OFPBRC_EPERM;
+ }
+
/* Check for overlap, if requested. */
if (fm->flags & OFPFF_CHECK_OVERLAP
&& classifier_rule_overlaps(&table->cls, &fm->cr)) {
rule->cr = fm->cr;
rule->pending = NULL;
rule->flow_cookie = fm->cookie;
- rule->created = rule->modified = time_msec();
+ rule->created = rule->modified = rule->used = time_msec();
rule->idle_timeout = fm->idle_timeout;
rule->hard_timeout = fm->hard_timeout;
rule->table_id = table - ofproto->tables;
rule->send_flow_removed = (fm->flags & OFPFF_SEND_FLOW_REM) != 0;
rule->actions = ofputil_actions_clone(fm->actions, fm->n_actions);
rule->n_actions = fm->n_actions;
+ rule->evictable = true;
+ rule->eviction_group = NULL;
/* Insert new rule. */
victim = oftable_replace_rule(rule);
- if (victim && victim->pending) {
+ if (victim && !rule_is_modifiable(victim)) {
+ error = OFPERR_OFPBRC_EPERM;
+ } else if (victim && victim->pending) {
error = OFPROTO_POSTPONE;
} else {
+ struct rule *evict;
+
+ if (classifier_count(&table->cls) > table->max_flows) {
+ bool was_evictable;
+
+ was_evictable = rule->evictable;
+ rule->evictable = false;
+ evict = choose_rule_to_evict(table);
+ rule->evictable = was_evictable;
+
+ if (!evict) {
+ error = OFPERR_OFPFMFC_ALL_TABLES_FULL;
+ goto exit;
+ } else if (evict->pending) {
+ error = OFPROTO_POSTPONE;
+ goto exit;
+ }
+ } else {
+ evict = NULL;
+ }
+
group = ofopgroup_create(ofproto, ofconn, request, fm->buffer_id);
ofoperation_create(group, rule, OFOPERATION_ADD);
rule->pending->victim = victim;
error = ofproto->ofproto_class->rule_construct(rule);
if (error) {
ofoperation_destroy(rule->pending);
+ } else if (evict) {
+ delete_flow__(evict, group);
}
ofopgroup_submit(group);
}
+exit:
/* Back out if an error occurred. */
if (error) {
oftable_substitute_rule(rule, victim);
{
struct ofopgroup *group;
struct rule *rule;
+ enum ofperr error;
group = ofopgroup_create(ofproto, ofconn, request, fm->buffer_id);
+ error = OFPERR_OFPBRC_EPERM;
LIST_FOR_EACH (rule, ofproto_node, rules) {
+ if (rule_is_modifiable(rule)) {
+ /* At least one rule is modifiable, don't report EPERM error. */
+ error = 0;
+ } else {
+ continue;
+ }
+
if (!ofputil_actions_equal(fm->actions, fm->n_actions,
rule->actions, rule->n_actions)) {
ofoperation_create(group, rule, OFOPERATION_MODIFY);
rule->pending->n_actions = rule->n_actions;
rule->actions = ofputil_actions_clone(fm->actions, fm->n_actions);
rule->n_actions = fm->n_actions;
- rule->ofproto->ofproto_class->rule_modify_actions(rule);
+ ofproto->ofproto_class->rule_modify_actions(rule);
} else {
rule->modified = time_msec();
}
}
ofopgroup_submit(group);
- return 0;
+ return error;
}
/* Implements OFPFC_MODIFY. Returns 0 on success or an OpenFlow error code on
\f
/* OFPFC_DELETE implementation. */
+static void
+delete_flow__(struct rule *rule, struct ofopgroup *group)
+{
+ struct ofproto *ofproto = rule->ofproto;
+
+ ofproto_rule_send_removed(rule, OFPRR_DELETE);
+
+ ofoperation_create(group, rule, OFOPERATION_DELETE);
+ oftable_remove_rule(rule);
+ ofproto->ofproto_class->rule_destruct(rule);
+}
+
/* Deletes the rules listed in 'rules'.
*
* Returns 0 on success, otherwise an OpenFlow error code. */
group = ofopgroup_create(ofproto, ofconn, request, UINT32_MAX);
LIST_FOR_EACH_SAFE (rule, next, ofproto_node, rules) {
- ofproto_rule_send_removed(rule, OFPRR_DELETE);
-
- ofoperation_create(group, rule, OFOPERATION_DELETE);
- oftable_remove_rule(rule);
- rule->ofproto->ofproto_class->rule_destruct(rule);
+ delete_flow__(rule, group);
}
ofopgroup_submit(group);
fr.rule = rule->cr;
fr.cookie = rule->flow_cookie;
fr.reason = reason;
- calc_flow_duration__(rule->created, &fr.duration_sec, &fr.duration_nsec);
+ calc_flow_duration__(rule->created, time_msec(),
+ &fr.duration_sec, &fr.duration_nsec);
fr.idle_timeout = rule->idle_timeout;
rule->ofproto->ofproto_class->rule_get_stats(rule, &fr.packet_count,
&fr.byte_count);
connmgr_send_flow_removed(rule->ofproto->connmgr, &fr);
}
+void
+ofproto_rule_update_used(struct rule *rule, long long int used)
+{
+ if (used > rule->used) {
+ struct eviction_group *evg = rule->eviction_group;
+
+ rule->used = used;
+ if (evg) {
+ heap_change(&evg->rules, &rule->evg_node,
+ rule_eviction_priority(rule));
+ }
+ }
+}
+
/* Sends an OpenFlow "flow removed" message with the given 'reason' (either
* OFPRR_HARD_TIMEOUT or OFPRR_IDLE_TIMEOUT), and then removes 'rule' from its
* ofproto.
group = ofopgroup_create_unattached(ofproto);
ofoperation_create(group, rule, OFOPERATION_DELETE);
oftable_remove_rule(rule);
- rule->ofproto->ofproto_class->rule_destruct(rule);
+ ofproto->ofproto_class->rule_destruct(rule);
ofopgroup_submit(group);
}
\f
struct ofpbuf *buf;
uint32_t role;
- if (ofconn_get_type(ofconn) != OFCONN_PRIMARY) {
- return OFPERR_OFPBRC_EPERM;
- }
-
role = ntohl(nrr->role);
if (role != NX_ROLE_OTHER && role != NX_ROLE_MASTER
&& role != NX_ROLE_SLAVE) {
return 0;
}
+static enum ofperr
+handle_nxt_set_async_config(struct ofconn *ofconn, const struct ofp_header *oh)
+{
+ const struct nx_async_config *msg = (const struct nx_async_config *) oh;
+ uint32_t master[OAM_N_TYPES];
+ uint32_t slave[OAM_N_TYPES];
+
+ master[OAM_PACKET_IN] = ntohl(msg->packet_in_mask[0]);
+ master[OAM_PORT_STATUS] = ntohl(msg->port_status_mask[0]);
+ master[OAM_FLOW_REMOVED] = ntohl(msg->flow_removed_mask[0]);
+
+ slave[OAM_PACKET_IN] = ntohl(msg->packet_in_mask[1]);
+ slave[OAM_PORT_STATUS] = ntohl(msg->port_status_mask[1]);
+ slave[OAM_FLOW_REMOVED] = ntohl(msg->flow_removed_mask[1]);
+
+ ofconn_set_async_config(ofconn, master, slave);
+
+ return 0;
+}
+
static enum ofperr
handle_barrier_request(struct ofconn *ofconn, const struct ofp_header *oh)
{
return handle_set_config(ofconn, msg->data);
case OFPUTIL_OFPT_PACKET_OUT:
- return handle_packet_out(ofconn, oh);
+ return handle_packet_out(ofconn, msg->data);
case OFPUTIL_OFPT_PORT_MOD:
return handle_port_mod(ofconn, oh);
case OFPUTIL_NXT_FLOW_MOD:
return handle_flow_mod(ofconn, oh);
+ case OFPUTIL_NXT_FLOW_AGE:
+ /* Nothing to do. */
+ return 0;
+
+ case OFPUTIL_NXT_SET_ASYNC_CONFIG:
+ return handle_nxt_set_async_config(ofconn, oh);
+
/* Statistics requests. */
case OFPUTIL_OFPST_DESC_REQUEST:
return handle_desc_stats_request(ofconn, msg->data);
switch (op->type) {
case OFOPERATION_ADD:
if (!error) {
- if (op->victim) {
- ofproto_rule_destroy__(op->victim);
- }
+ ofproto_rule_destroy__(op->victim);
if ((rule->cr.wc.vlan_tci_mask & htons(VLAN_VID_MASK))
== htons(VLAN_VID_MASK)) {
if (ofproto->vlan_bitmap) {
oftable_substitute_rule(rule, op->victim);
ofproto_rule_destroy__(rule);
}
- op->victim = NULL;
break;
case OFOPERATION_DELETE:
return eth_addr_to_uint64(ea);
}
\f
+/* Table overflow policy. */
+
+/* Chooses and returns a rule to evict from 'table'. Returns NULL if the table
+ * is not configured to evict rules or if the table contains no evictable
+ * rules. (Rules with 'evictable' set to false or with no timeouts are not
+ * evictable.) */
+static struct rule *
+choose_rule_to_evict(struct oftable *table)
+{
+ struct eviction_group *evg;
+
+ if (!table->eviction_fields) {
+ return NULL;
+ }
+
+ /* In the common case, the outer and inner loops here will each be entered
+ * exactly once:
+ *
+ * - The inner loop normally "return"s in its first iteration. If the
+ * eviction group has any evictable rules, then it always returns in
+ * some iteration.
+ *
+ * - The outer loop only iterates more than once if the largest eviction
+ * group has no evictable rules.
+ *
+ * - The outer loop can exit only if table's 'max_flows' is all filled up
+ * by unevictable rules'. */
+ HEAP_FOR_EACH (evg, size_node, &table->eviction_groups_by_size) {
+ struct rule *rule;
+
+ HEAP_FOR_EACH (rule, evg_node, &evg->rules) {
+ if (rule->evictable) {
+ return rule;
+ }
+ }
+ }
+
+ return NULL;
+}
+
+/* Searches 'ofproto' for tables that have more flows than their configured
+ * maximum and that have flow eviction enabled, and evicts as many flows as
+ * necessary and currently feasible from them.
+ *
+ * This triggers only when an OpenFlow table has N flows in it and then the
+ * client configures a maximum number of flows less than N. */
+static void
+ofproto_evict(struct ofproto *ofproto)
+{
+ struct ofopgroup *group;
+ struct oftable *table;
+
+ group = ofopgroup_create_unattached(ofproto);
+ OFPROTO_FOR_EACH_TABLE (table, ofproto) {
+ while (classifier_count(&table->cls) > table->max_flows
+ && table->eviction_fields) {
+ struct rule *rule;
+
+ rule = choose_rule_to_evict(table);
+ if (!rule || rule->pending) {
+ break;
+ }
+
+ ofoperation_create(group, rule, OFOPERATION_DELETE);
+ oftable_remove_rule(rule);
+ ofproto->ofproto_class->rule_destruct(rule);
+ }
+ }
+ ofopgroup_submit(group);
+}
+\f
+/* Eviction groups. */
+
+/* Returns the priority to use for an eviction_group that contains 'n_rules'
+ * rules. The priority contains low-order random bits to ensure that eviction
+ * groups with the same number of rules are prioritized randomly. */
+static uint32_t
+eviction_group_priority(size_t n_rules)
+{
+ uint16_t size = MIN(UINT16_MAX, n_rules);
+ return (size << 16) | random_uint16();
+}
+
+/* Updates 'evg', an eviction_group within 'table', following a change that
+ * adds or removes rules in 'evg'. */
+static void
+eviction_group_resized(struct oftable *table, struct eviction_group *evg)
+{
+ heap_change(&table->eviction_groups_by_size, &evg->size_node,
+ eviction_group_priority(heap_count(&evg->rules)));
+}
+
+/* Destroys 'evg', an eviction_group within 'table':
+ *
+ * - Removes all the rules, if any, from 'evg'. (It doesn't destroy the
+ * rules themselves, just removes them from the eviction group.)
+ *
+ * - Removes 'evg' from 'table'.
+ *
+ * - Frees 'evg'. */
+static void
+eviction_group_destroy(struct oftable *table, struct eviction_group *evg)
+{
+ while (!heap_is_empty(&evg->rules)) {
+ struct rule *rule;
+
+ rule = CONTAINER_OF(heap_pop(&evg->rules), struct rule, evg_node);
+ rule->eviction_group = NULL;
+ }
+ hmap_remove(&table->eviction_groups_by_id, &evg->id_node);
+ heap_remove(&table->eviction_groups_by_size, &evg->size_node);
+ heap_destroy(&evg->rules);
+ free(evg);
+}
+
+/* Removes 'rule' from its eviction group, if any. */
+static void
+eviction_group_remove_rule(struct rule *rule)
+{
+ if (rule->eviction_group) {
+ struct oftable *table = &rule->ofproto->tables[rule->table_id];
+ struct eviction_group *evg = rule->eviction_group;
+
+ rule->eviction_group = NULL;
+ heap_remove(&evg->rules, &rule->evg_node);
+ if (heap_is_empty(&evg->rules)) {
+ eviction_group_destroy(table, evg);
+ } else {
+ eviction_group_resized(table, evg);
+ }
+ }
+}
+
+/* Hashes the 'rule''s values for the eviction_fields of 'rule''s table, and
+ * returns the hash value. */
+static uint32_t
+eviction_group_hash_rule(struct rule *rule)
+{
+ struct oftable *table = &rule->ofproto->tables[rule->table_id];
+ const struct mf_subfield *sf;
+ uint32_t hash;
+
+ hash = table->eviction_group_id_basis;
+ for (sf = table->eviction_fields;
+ sf < &table->eviction_fields[table->n_eviction_fields];
+ sf++)
+ {
+ if (mf_are_prereqs_ok(sf->field, &rule->cr.flow)) {
+ union mf_value value;
+
+ mf_get_value(sf->field, &rule->cr.flow, &value);
+ if (sf->ofs) {
+ bitwise_zero(&value, sf->field->n_bytes, 0, sf->ofs);
+ }
+ if (sf->ofs + sf->n_bits < sf->field->n_bytes * 8) {
+ unsigned int start = sf->ofs + sf->n_bits;
+ bitwise_zero(&value, sf->field->n_bytes, start,
+ sf->field->n_bytes * 8 - start);
+ }
+ hash = hash_bytes(&value, sf->field->n_bytes, hash);
+ } else {
+ hash = hash_int(hash, 0);
+ }
+ }
+
+ return hash;
+}
+
+/* Returns an eviction group within 'table' with the given 'id', creating one
+ * if necessary. */
+static struct eviction_group *
+eviction_group_find(struct oftable *table, uint32_t id)
+{
+ struct eviction_group *evg;
+
+ HMAP_FOR_EACH_WITH_HASH (evg, id_node, id, &table->eviction_groups_by_id) {
+ return evg;
+ }
+
+ evg = xmalloc(sizeof *evg);
+ hmap_insert(&table->eviction_groups_by_id, &evg->id_node, id);
+ heap_insert(&table->eviction_groups_by_size, &evg->size_node,
+ eviction_group_priority(0));
+ heap_init(&evg->rules);
+
+ return evg;
+}
+
+/* Returns an eviction priority for 'rule'. The return value should be
+ * interpreted so that higher priorities make a rule more attractive candidates
+ * for eviction. */
+static uint32_t
+rule_eviction_priority(struct rule *rule)
+{
+ long long int hard_expiration;
+ long long int idle_expiration;
+ long long int expiration;
+ uint32_t expiration_offset;
+
+ /* Calculate time of expiration. */
+ hard_expiration = (rule->hard_timeout
+ ? rule->modified + rule->hard_timeout * 1000
+ : LLONG_MAX);
+ idle_expiration = (rule->idle_timeout
+ ? rule->used + rule->idle_timeout * 1000
+ : LLONG_MAX);
+ expiration = MIN(hard_expiration, idle_expiration);
+ if (expiration == LLONG_MAX) {
+ return 0;
+ }
+
+ /* Calculate the time of expiration as a number of (approximate) seconds
+ * after program startup.
+ *
+ * This should work OK for program runs that last UINT32_MAX seconds or
+ * less. Therefore, please restart OVS at least once every 136 years. */
+ expiration_offset = (expiration >> 10) - (time_boot_msec() >> 10);
+
+ /* Invert the expiration offset because we're using a max-heap. */
+ return UINT32_MAX - expiration_offset;
+}
+
+/* Adds 'rule' to an appropriate eviction group for its oftable's
+ * configuration. Does nothing if 'rule''s oftable doesn't have eviction
+ * enabled, or if 'rule' is a permanent rule (one that will never expire on its
+ * own).
+ *
+ * The caller must ensure that 'rule' is not already in an eviction group. */
+static void
+eviction_group_add_rule(struct rule *rule)
+{
+ struct ofproto *ofproto = rule->ofproto;
+ struct oftable *table = &ofproto->tables[rule->table_id];
+
+ if (table->eviction_fields
+ && (rule->hard_timeout || rule->idle_timeout)) {
+ struct eviction_group *evg;
+
+ evg = eviction_group_find(table, eviction_group_hash_rule(rule));
+
+ rule->eviction_group = evg;
+ heap_insert(&evg->rules, &rule->evg_node,
+ rule_eviction_priority(rule));
+ eviction_group_resized(table, evg);
+ }
+}
+\f
/* oftables. */
/* Initializes 'table'. */
static void
oftable_init(struct oftable *table)
{
+ memset(table, 0, sizeof *table);
classifier_init(&table->cls);
}
-/* Destroys 'table'.
+/* Destroys 'table', including its classifier and eviction groups.
*
* The caller is responsible for freeing 'table' itself. */
static void
oftable_destroy(struct oftable *table)
{
assert(classifier_is_empty(&table->cls));
+ oftable_disable_eviction(table);
classifier_destroy(&table->cls);
+ free(table->name);
+}
+
+/* Changes the name of 'table' to 'name'. If 'name' is NULL or the empty
+ * string, then 'table' will use its default name.
+ *
+ * This only affects the name exposed for a table exposed through the OpenFlow
+ * OFPST_TABLE (as printed by "ovs-ofctl dump-tables"). */
+static void
+oftable_set_name(struct oftable *table, const char *name)
+{
+ if (name && name[0]) {
+ int len = strnlen(name, OFP_MAX_TABLE_NAME_LEN);
+ if (!table->name || strncmp(name, table->name, len)) {
+ free(table->name);
+ table->name = xmemdup0(name, len);
+ }
+ } else {
+ free(table->name);
+ table->name = NULL;
+ }
+}
+
+/* oftables support a choice of two policies when adding a rule would cause the
+ * number of flows in the table to exceed the configured maximum number: either
+ * they can refuse to add the new flow or they can evict some existing flow.
+ * This function configures the former policy on 'table'. */
+static void
+oftable_disable_eviction(struct oftable *table)
+{
+ if (table->eviction_fields) {
+ struct eviction_group *evg, *next;
+
+ HMAP_FOR_EACH_SAFE (evg, next, id_node,
+ &table->eviction_groups_by_id) {
+ eviction_group_destroy(table, evg);
+ }
+ hmap_destroy(&table->eviction_groups_by_id);
+ heap_destroy(&table->eviction_groups_by_size);
+
+ free(table->eviction_fields);
+ table->eviction_fields = NULL;
+ table->n_eviction_fields = 0;
+ }
+}
+
+/* oftables support a choice of two policies when adding a rule would cause the
+ * number of flows in the table to exceed the configured maximum number: either
+ * they can refuse to add the new flow or they can evict some existing flow.
+ * This function configures the latter policy on 'table', with fairness based
+ * on the values of the 'n_fields' fields specified in 'fields'. (Specifying
+ * 'n_fields' as 0 disables fairness.) */
+static void
+oftable_enable_eviction(struct oftable *table,
+ const struct mf_subfield *fields, size_t n_fields)
+{
+ struct cls_cursor cursor;
+ struct rule *rule;
+
+ if (table->eviction_fields
+ && n_fields == table->n_eviction_fields
+ && (!n_fields
+ || !memcmp(fields, table->eviction_fields,
+ n_fields * sizeof *fields))) {
+ /* No change. */
+ return;
+ }
+
+ oftable_disable_eviction(table);
+
+ table->n_eviction_fields = n_fields;
+ table->eviction_fields = xmemdup(fields, n_fields * sizeof *fields);
+
+ table->eviction_group_id_basis = random_uint32();
+ hmap_init(&table->eviction_groups_by_id);
+ heap_init(&table->eviction_groups_by_size);
+
+ cls_cursor_init(&cursor, &table->cls, NULL);
+ CLS_CURSOR_FOR_EACH (rule, cr, &cursor) {
+ eviction_group_add_rule(rule);
+ }
}
/* Removes 'rule' from the oftable that contains it. */
struct oftable *table = &ofproto->tables[rule->table_id];
classifier_remove(&table->cls, &rule->cr);
+ eviction_group_remove_rule(rule);
}
/* Inserts 'rule' into its oftable. Removes any existing rule from 'rule''s
{
struct ofproto *ofproto = rule->ofproto;
struct oftable *table = &ofproto->tables[rule->table_id];
+ struct rule *victim;
- return rule_from_cls_rule(classifier_replace(&table->cls, &rule->cr));
+ victim = rule_from_cls_rule(classifier_replace(&table->cls, &rule->cr));
+ if (victim) {
+ eviction_group_remove_rule(victim);
+ }
+ eviction_group_add_rule(rule);
+ return victim;
}
/* Removes 'old' from its oftable then, if 'new' is nonnull, inserts 'new'. */
git://git.onelab.eu / sliver-openvswitch.git / blobdiff