← Back to branch summary

~james-page/ubuntu/saucy/openvswitch/1.12-snapshot

« back to all changes in this revision

Viewing changes to lib/classifier.c

  • Committer: James Page
  • Date: 2013-08-21 10:16:57 UTC
  • mfrom: (1.1.20)
  • Revision ID: james.page@canonical.com-20130821101657-3o0z0qeiv5zkwlzi
New upstream snapshot

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/classifier.c
1
1
/*
2
 
 * Copyright (c) 2009, 2010, 2011, 2012 Nicira, Inc.
 
2
 * Copyright (c) 2009, 2010, 2011, 2012, 2013 Nicira, Inc.
3
3
 *
4
4
 * Licensed under the Apache License, Version 2.0 (the "License");
5
5
 * you may not use this file except in compliance with the License.
33
33
 
34
34
static void destroy_table(struct classifier *, struct cls_table *);
35
35
 
 
36
static void update_tables_after_insertion(struct classifier *,
 
37
                                          struct cls_table *,
 
38
                                          unsigned int new_priority);
 
39
static void update_tables_after_removal(struct classifier *,
 
40
                                        struct cls_table *,
 
41
                                        unsigned int del_priority);
 
42
 
36
43
static struct cls_rule *find_match(const struct cls_table *,
37
44
                                   const struct flow *);
38
45
static struct cls_rule *find_equal(struct cls_table *,
39
46
                                   const struct miniflow *, uint32_t hash);
40
 
static struct cls_rule *insert_rule(struct cls_table *, struct cls_rule *);
 
47
static struct cls_rule *insert_rule(struct classifier *,
 
48
                                    struct cls_table *, struct cls_rule *);
41
49
 
42
50
/* Iterates RULE over HEAD and all of the cls_rules on HEAD->list. */
43
51
#define FOR_EACH_RULE_IN_LIST(RULE, HEAD)                               \
134
142
{
135
143
    cls->n_rules = 0;
136
144
    hmap_init(&cls->tables);
 
145
    list_init(&cls->tables_priority);
137
146
}
138
147
 
139
148
/* Destroys 'cls'.  Rules within 'cls', if any, are not freed; this is the
189
198
        table = insert_table(cls, &rule->match.mask);
190
199
    }
191
200
 
192
 
    old_rule = insert_rule(table, rule);
 
201
    old_rule = insert_rule(cls, table, rule);
193
202
    if (!old_rule) {
194
203
        table->n_table_rules++;
195
204
        cls->n_rules++;
235
244
 
236
245
    if (--table->n_table_rules == 0) {
237
246
        destroy_table(cls, table);
 
247
    } else {
 
248
        update_tables_after_removal(cls, table, rule->priority);
238
249
    }
239
 
 
240
250
    cls->n_rules--;
241
251
}
242
252
 
243
253
/* Finds and returns the highest-priority rule in 'cls' that matches 'flow'.
244
254
 * Returns a null pointer if no rules in 'cls' match 'flow'.  If multiple rules
245
 
 * of equal priority match 'flow', returns one arbitrarily. */
 
255
 * of equal priority match 'flow', returns one arbitrarily.
 
256
 *
 
257
 * If a rule is found and 'wc' is non-null, bitwise-OR's 'wc' with the
 
258
 * set of bits that were significant in the lookup.  At some point
 
259
 * earlier, 'wc' should have been initialized (e.g., by
 
260
 * flow_wildcards_init_catchall()). */
246
261
struct cls_rule *
247
 
classifier_lookup(const struct classifier *cls, const struct flow *flow)
 
262
classifier_lookup(const struct classifier *cls, const struct flow *flow,
 
263
                  struct flow_wildcards *wc)
248
264
{
249
265
    struct cls_table *table;
250
266
    struct cls_rule *best;
251
267
 
252
268
    best = NULL;
253
 
    HMAP_FOR_EACH (table, hmap_node, &cls->tables) {
 
269
    LIST_FOR_EACH (table, list_node, &cls->tables_priority) {
254
270
        struct cls_rule *rule = find_match(table, flow);
255
 
        if (rule && (!best || rule->priority > best->priority)) {
 
271
 
 
272
        if (wc) {
 
273
            flow_wildcards_fold_minimask(wc, &table->mask);
 
274
        }
 
275
        if (rule) {
256
276
            best = rule;
 
277
            LIST_FOR_EACH_CONTINUE (table, list_node, &cls->tables_priority) {
 
278
                if (table->max_priority <= best->priority) {
 
279
                    /* Tables in descending priority order,
 
280
                     * can not find anything better. */
 
281
                    return best;
 
282
                }
 
283
                rule = find_match(table, flow);
 
284
                if (wc) {
 
285
                    flow_wildcards_fold_minimask(wc, &table->mask);
 
286
                }
 
287
                if (rule && rule->priority > best->priority) {
 
288
                    best = rule;
 
289
                }
 
290
            }
 
291
            break;
257
292
        }
258
293
    }
259
294
    return best;
274
309
        return NULL;
275
310
    }
276
311
 
 
312
    /* Skip if there is no hope. */
 
313
    if (target->priority > table->max_priority) {
 
314
        return NULL;
 
315
    }
 
316
 
277
317
    head = find_equal(table, &target->match.flow,
278
318
                      miniflow_hash_in_minimask(&target->match.flow,
279
319
                                                &target->match.mask, 0));
312
352
{
313
353
    struct cls_table *table;
314
354
 
315
 
    HMAP_FOR_EACH (table, hmap_node, &cls->tables) {
 
355
    /* Iterate tables in the descending max priority order. */
 
356
    LIST_FOR_EACH (table, list_node, &cls->tables_priority) {
316
357
        uint32_t storage[FLOW_U32S];
317
358
        struct minimask mask;
318
359
        struct cls_rule *head;
319
360
 
 
361
        if (target->priority > table->max_priority) {
 
362
            break; /* Can skip this and the rest of the tables. */
 
363
        }
 
364
 
320
365
        minimask_combine(&mask, &target->match.mask, &table->mask, storage);
321
366
        HMAP_FOR_EACH (head, hmap_node, &table->rules) {
322
367
            struct cls_rule *rule;
323
368
 
324
369
            FOR_EACH_RULE_IN_LIST (rule, head) {
 
370
                if (rule->priority < target->priority) {
 
371
                    break; /* Rules in descending priority order. */
 
372
                }
325
373
                if (rule->priority == target->priority
326
374
                    && miniflow_equal_in_minimask(&target->match.flow,
327
375
                                                  &rule->match.flow, &mask)) {
494
542
    hmap_init(&table->rules);
495
543
    minimask_clone(&table->mask, mask);
496
544
    hmap_insert(&cls->tables, &table->hmap_node, minimask_hash(mask, 0));
 
545
    list_push_back(&cls->tables_priority, &table->list_node);
497
546
 
498
547
    return table;
499
548
}
504
553
    minimask_destroy(&table->mask);
505
554
    hmap_remove(&cls->tables, &table->hmap_node);
506
555
    hmap_destroy(&table->rules);
 
556
    list_remove(&table->list_node);
507
557
    free(table);
508
558
}
509
559
 
 
560
/* This function performs the following updates for 'table' in 'cls' following
 
561
 * the addition of a new rule with priority 'new_priority' to 'table':
 
562
 *
 
563
 *    - Update 'table->max_priority' and 'table->max_count' if necessary.
 
564
 *
 
565
 *    - Update 'table''s position in 'cls->tables_priority' if necessary.
 
566
 *
 
567
 * This function should only be called after adding a new rule, not after
 
568
 * replacing a rule by an identical one or modifying a rule in-place. */
 
569
static void
 
570
update_tables_after_insertion(struct classifier *cls, struct cls_table *table,
 
571
                              unsigned int new_priority)
 
572
{
 
573
    if (new_priority == table->max_priority) {
 
574
        ++table->max_count;
 
575
    } else if (new_priority > table->max_priority) {
 
576
        struct cls_table *iter;
 
577
 
 
578
        table->max_priority = new_priority;
 
579
        table->max_count = 1;
 
580
 
 
581
        /* Possibly move 'table' earlier in the priority list.  If we break out
 
582
         * of the loop, then 'table' should be moved just after that 'iter'.
 
583
         * If the loop terminates normally, then 'iter' will be the list head
 
584
         * and we'll move table just after that (e.g. to the front of the
 
585
         * list). */
 
586
        iter = table;
 
587
        LIST_FOR_EACH_REVERSE_CONTINUE (iter, list_node,
 
588
                                        &cls->tables_priority) {
 
589
            if (iter->max_priority >= table->max_priority) {
 
590
                break;
 
591
            }
 
592
        }
 
593
 
 
594
        /* Move 'table' just after 'iter' (unless it's already there). */
 
595
        if (iter->list_node.next != &table->list_node) {
 
596
            list_splice(iter->list_node.next,
 
597
                        &table->list_node, table->list_node.next);
 
598
        }
 
599
    }
 
600
}
 
601
 
 
602
/* This function performs the following updates for 'table' in 'cls' following
 
603
 * the deletion of a rule with priority 'del_priority' from 'table':
 
604
 *
 
605
 *    - Update 'table->max_priority' and 'table->max_count' if necessary.
 
606
 *
 
607
 *    - Update 'table''s position in 'cls->tables_priority' if necessary.
 
608
 *
 
609
 * This function should only be called after removing a rule, not after
 
610
 * replacing a rule by an identical one or modifying a rule in-place. */
 
611
static void
 
612
update_tables_after_removal(struct classifier *cls, struct cls_table *table,
 
613
                            unsigned int del_priority)
 
614
{
 
615
    struct cls_table *iter;
 
616
 
 
617
    if (del_priority == table->max_priority && --table->max_count == 0) {
 
618
        struct cls_rule *head;
 
619
 
 
620
        table->max_priority = 0;
 
621
        HMAP_FOR_EACH (head, hmap_node, &table->rules) {
 
622
            if (head->priority > table->max_priority) {
 
623
                table->max_priority = head->priority;
 
624
                table->max_count = 1;
 
625
            } else if (head->priority == table->max_priority) {
 
626
                ++table->max_count;
 
627
            }
 
628
        }
 
629
 
 
630
        /* Possibly move 'table' later in the priority list.  If we break out
 
631
         * of the loop, then 'table' should be moved just before that 'iter'.
 
632
         * If the loop terminates normally, then 'iter' will be the list head
 
633
         * and we'll move table just before that (e.g. to the back of the
 
634
         * list). */
 
635
        iter = table;
 
636
        LIST_FOR_EACH_CONTINUE (iter, list_node, &cls->tables_priority) {
 
637
            if (iter->max_priority <= table->max_priority) {
 
638
                break;
 
639
            }
 
640
        }
 
641
 
 
642
        /* Move 'table' just before 'iter' (unless it's already there). */
 
643
        if (iter->list_node.prev != &table->list_node) {
 
644
            list_splice(&iter->list_node,
 
645
                        &table->list_node, table->list_node.next);
 
646
        }
 
647
    }
 
648
}
 
649
 
510
650
static struct cls_rule *
511
651
find_match(const struct cls_table *table, const struct flow *flow)
512
652
{
537
677
}
538
678
 
539
679
static struct cls_rule *
540
 
insert_rule(struct cls_table *table, struct cls_rule *new)
 
680
insert_rule(struct classifier *cls,
 
681
            struct cls_table *table, struct cls_rule *new)
541
682
{
542
683
    struct cls_rule *head;
 
684
    struct cls_rule *old = NULL;
543
685
 
544
686
    new->hmap_node.hash = miniflow_hash_in_minimask(&new->match.flow,
545
687
                                                    &new->match.mask, 0);
548
690
    if (!head) {
549
691
        hmap_insert(&table->rules, &new->hmap_node, new->hmap_node.hash);
550
692
        list_init(&new->list);
551
 
        return NULL;
 
693
        goto out;
552
694
    } else {
553
695
        /* Scan the list for the insertion point that will keep the list in
554
696
         * order of decreasing priority. */
563
705
 
564
706
                if (new->priority == rule->priority) {
565
707
                    list_replace(&new->list, &rule->list);
566
 
                    return rule;
 
708
                    old = rule;
 
709
                    goto out;
567
710
                } else {
568
711
                    list_insert(&rule->list, &new->list);
569
 
                    return NULL;
 
712
                    goto out;
570
713
                }
571
714
            }
572
715
        }
573
716
 
574
717
        /* Insert 'new' at the end of the list. */
575
718
        list_push_back(&head->list, &new->list);
576
 
        return NULL;
577
 
    }
 
719
    }
 
720
 
 
721
 out:
 
722
    if (!old) {
 
723
        update_tables_after_insertion(cls, table, new->priority);
 
724
    }
 
725
    return old;
578
726
}
579
727
 
580
728
static struct cls_rule *