I'm getting back to this, finally.
On Wed, May 08, 2013 at 08:13:18AM +0000, Rajahalme, Jarno (NSN - FI/Espoo)
wrote:
> On Mar 27, 2013, at 6:32 , ext Ben Pfaff wrote:
>
> > We have a controller that puts many rules with different metadata values
> > into the flow table, where metadata is used (by "resubmit"s) to distinguish
> > stages in a pipeline. Thus, any given flow only needs to be hashed into
> > classifier "cls_table"s that contain a match for the flow's metadata value.
> > This commit optimizes the classifier lookup by (probabilistically) skipping
> > the "cls_table"s that can't possibly match.
> >
> > (The "metadata" referred to here is the OpenFlow 1.1+ "metadata" field,
> > which is a 64-bit field similar in purpose to the "registers" defined by
> > Open vSwitch.)
> >
> > This speeds up flow setup performance with the controller in question by
> > about 19%.
> >
> > Bug #14282.
> > Signed-off-by: Ben Pfaff <b...@nicira.com>
...
> > +static struct cls_partition *
> > +create_partition(struct classifier *cls, struct cls_table *table,
> > + ovs_be64 metadata)
> > +{
> > + uint32_t hash = hash_metadata(metadata);
> > + struct cls_partition *partition = find_partition(cls, metadata, hash);
> > + if (partition) {
> > + partition->n_refs++;
> > + partition->tags |= table->tag;
>
> In principle, partition->tags could fill up over time as the bits
> are left there as rules are removed from the classifier. However, is
> seems that the rule/table dynamics could be such that this is no
> problem in practice?
I don't know. I don't think anyone has done long-term testing as
rules are added and removed.
I have an idea for how to solve the problem with O(1) additional work
when adding or removing rules. I'll work on that and probably post a
followup patch.
> > old_rule = insert_rule(cls, table, rule);
> > if (!old_rule) {
> > + if (minimask_get_metadata_mask(&rule->match.mask) == OVS_BE64_MAX)
> > {
> > + ovs_be64 metadata = miniflow_get_metadata(&rule->match.flow);
> > + rule->partition = create_partition(cls, table, metadata);
>
> I guess that Andy's comment on masked metadata support would be a
> generalization to this, where the metadata mask would be made part
> of the cls_partition, and the hmap would be keyed by the combination
> of the (masked) metadata and the mask. It would be pretty
> straightforward, but would be a bit more work. With this
> generalization this part would look like something like this:
>
> ovs_be64 metadata_mask =
> minimask_get_metadata_mask(&rule->match.mask);
> if (metadata_mask) {
> ovs_be64 metadata = miniflow_get_metadata(&rule->match.flow);
> rule->partition = create_partition(cls, table, metadata,
> metadata_mask);
>
> Corresponding changes would be needed elsewhere.
>
> I have no idea of the performance impact, though.
I see that you posted a later followup saying that this would probably
wouldn't be a good idea, so I'll ignore this.
> > best = NULL;
> > LIST_FOR_EACH (table, list_node, &cls->tables_priority) {
> > - struct cls_rule *rule = find_match(table, flow);
> > + struct cls_rule *rule = find_match(table, flow, tags);
>
> How about keeping the tags check here instead? Like:
> LIST_FOR_EACH (table, list_node, &cls->tables_priority) {
> if (!tag_intersects(tags, table->tag))
> continue;
> struct cls_rule *rule = find_match(table, flow);
OK, I folded this in, thanks.
> > if (rule) {
> > best = rule;
> > LIST_FOR_EACH_CONTINUE (table, list_node,
> > &cls->tables_priority) {
> > @@ -270,7 +361,7 @@ classifier_lookup(const struct classifier *cls, const
> > struct flow *flow)
> > * can not find anything better. */
> > return best;
> > }
> > - rule = find_match(table, flow);
> > + rule = find_match(table, flow, tags);
>
> And here:
>
> if (!tag_intersects(tags, table->tag))
> continue;
> rule = find_match(table, flow);
Here too.
> Maybe it could be a little bit faster, in addition to keeping the
> find_match() intact.
I think you're right.
> > @@ -19,17 +19,66 @@
> >
> > /* Flow classifier.
> > *
> > - * A classifier is a "struct classifier",
> > - * a hash map from a set of wildcards to a "struct cls_table",
> > - * a hash map from fixed field values to "struct cls_rule",
> > - * which can contain a list of otherwise identical
> > rules
> > - * with lower priorities.
> > + * Basic Design
> > + * ============
> > + *
>
> Maybe start with a note that each OpenFlow flow table is represented by a
> classifier instance so the difference between OF tables and classifier tables
> would be more apparent.
I added a section:
* What?
* =====
*
* A flow classifier holds any number of "rules", each of which specifies
* values to match for some fields or subfields and a priority. The primary
* design goal for the classifier is that, given a packet, it can as quickly as
* possible find the highest-priority rule that matches the packet.
*
* Each OpenFlow table is implemented as a flow classifier.
> > + * Suppose that all the rules in a classifier had the same form. For
> > example,
> > + * suppose that they all matched on the source and destination Ethernet
> > address
> > + * and wildcarded all the other fields. Then the obvious way to implement
> > a
> > + * classifier would be a hash table on the source and destination Ethernet
> > + * addresses. If new classification rules came along with a different
> > form,
> > + * you could add a second hash table that hashed on the fields matched in
> > those
> > + * rules. With two hash tables, you look up a given flow in each hash
> > table.
> > + * If there are no matches, the classifier didn't contain a match; if you
> > find
> > + * a match in one of them, that's the result; if you find a match in both
> > of
> > + * them, then the result is the rule with the higher priority.
> > + *
> > + * This is how the classifier works. In a "struct classifier", each form
> > of
> > + * "struct cls_rule" present (based on its ->match.mask) goes into a
> > separate
> > + * "struct cls_table". A lookup does a hash lookup in every "struct
> > cls_table"
> > + * in the classifier and returns the highest-priority match that it finds.
>
> Could add:
>
> "The tables are kept in a descending priority order according to the
> highest priority rule in each table. This way the lookups following
> a found match can be limited to tables that possibly have higher
> priority rules than already found."
Thanks. I changed this paragraph to:
* This is how the classifier works. In a "struct classifier", each form of
* "struct cls_rule" present (based on its ->match.mask) goes into a separate
* "struct cls_table". A lookup does a hash lookup in every "struct cls_table"
* in the classifier and tracks the highest-priority match that it finds. The
* tables are kept in a descending priority order according to the highest
* priority rule in each table, which allows lookup to skip over tables that
* can't possibly have a higher-priority match than already found.
> > + * The classifier has a special optimization to speed up matching in this
> > + * scenario:
> > + *
> > + * - Each cls_table that matches on metadata gets a random tag (see
> > tag.h).
>
> To me the word "random" caused some confusion at first, so maybe put it like
> this instead:
>
> "Each cls_table that matches on metadata gets a tag derived from the table's
> mask, so that it is highly likely that each table has a unique tag."
>
> And maybe add that the possible non-unique table tags lead to some
> harmless checking of more tables than needed.
That is better, thanks. I changed this item to:
* - Each cls_table that matches on metadata gets a tag derived from the
* table's mask, so that it is likely that each table has a unique tag.
* (Duplicate tags have a performance cost but do not affect
* correctness.)
> > + * - For each metadata value matched by any cls_rule, the classifier
> > + * constructs a "struct cls_partition" indexed by the metadata value.
> > + * The cls_partition has a 'tags' member whose value is the
> > bitwise-OR of
> > + * the tags of each cls_table that contains any rule that matches on
> > the
> > + * cls_partition's metadata value.
>
> So in other words 'struct cls_partition' associates metadata values with
> tables that
> need to be checked with flows with that specific metadata value.
OK, I added that sentence to this item. It would be clearer without
the two uses of "with", but I didn't see a good way to do that.
Thanks,
Ben.
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
