-
-/*
- * As the readers are operating concurrently with the modifications, a
- * concurrent reader may or may not see the new rule, depending on how
- * the concurrent events overlap with each other. This is no
- * different from the former locked behavior, but there the visibility
- * of the new rule only depended on the timing of the locking
- * functions.
- *
- * The new rule is first added to the segment indices, so the readers
- * may find the rule in the indices before the rule is visible in the
- * subtables 'rules' map. This may result in us losing the
- * opportunity to quit lookups earlier, resulting in sub-optimal
- * wildcarding. This will be fixed by forthcoming revalidation always
- * scheduled after flow table changes.
- *
- * Similar behavior may happen due to us removing the overlapping rule
- * (if any) from the indices only after the new rule has been added.
- *
- * The subtable's max priority is updated only after the rule is
- * inserted, so the concurrent readers may not see the rule, as the
- * updated priority ordered subtable list will only be visible after
- * the subtable's max priority is updated.
- *
- * Similarly, the classifier's partitions for new rules are updated by
- * the caller after this function, so the readers may keep skipping
- * the subtable until they see the updated partitions.
- */
-static struct cls_match *
-insert_rule(struct classifier *cls, struct cls_subtable *subtable,
- struct cls_rule *new_rule)
- OVS_REQUIRES(cls->mutex)
-{
- struct cls_match *old = NULL;
- struct cls_match *new = cls_match_alloc(new_rule);
- struct cls_match *head;
- int i;
- uint32_t basis = 0, hash, ihash[CLS_MAX_INDICES];
- uint8_t prev_be32ofs = 0;
-
- /* Add new node to segment indices. */
- for (i = 0; i < subtable->n_indices; i++) {
- ihash[i] = minimatch_hash_range(&new_rule->match, prev_be32ofs,
- subtable->index_ofs[i], &basis);
- cmap_insert(&subtable->indices[i], &new->index_nodes[i], ihash[i]);
- prev_be32ofs = subtable->index_ofs[i];
- }
- hash = minimatch_hash_range(&new_rule->match, prev_be32ofs, FLOW_U32S,
- &basis);
- head = find_equal(subtable, &new_rule->match.flow, hash);
- if (!head) {
- cmap_insert(&subtable->rules, &new->cmap_node, hash);
- list_init(&new->list);
- goto out;
- } else {
- /* Scan the list for the insertion point that will keep the list in
- * order of decreasing priority. */
- struct cls_match *rule;
-
- FOR_EACH_RULE_IN_LIST (rule, head) {
- if (new->priority >= rule->priority) {
- if (rule == head) {
- /* 'new' is the new highest-priority flow in the list. */
- cmap_replace(&subtable->rules, &rule->cmap_node,
- &new->cmap_node, hash);
- }
-
- if (new->priority == rule->priority) {
- list_replace(&new->list, &rule->list);
- old = rule;
- } else {
- list_insert(&rule->list, &new->list);
- }
- goto out;
- }
- }
-
- /* Insert 'new' at the end of the list. */
- list_push_back(&head->list, &new->list);
- }
-
- out:
- if (!old) {
- subtable->n_rules++;
-
- /* Rule was added, not replaced. Update 'subtable's 'max_priority'
- * and 'max_count', if necessary. */
- if (subtable->n_rules == 1) {
- subtable->max_priority = new->priority;
- subtable->max_count = 1;
- pvector_insert(&cls->subtables, subtable, new->priority);
- } else if (subtable->max_priority == new->priority) {
- ++subtable->max_count;
- } else if (new->priority > subtable->max_priority) {
- subtable->max_priority = new->priority;
- subtable->max_count = 1;
- pvector_change_priority(&cls->subtables, subtable, new->priority);
- }
- } else {
- /* Remove old node from indices. */
- for (i = 0; i < subtable->n_indices; i++) {
- cmap_remove(&subtable->indices[i], &old->index_nodes[i], ihash[i]);
- }
- }
- return old;
-}
-
-static struct cls_match *
-next_rule_in_list__(struct cls_match *rule)
- OVS_NO_THREAD_SAFETY_ANALYSIS
-{
- struct cls_match *next = OBJECT_CONTAINING(rule->list.next, next, list);
- return next;
-}
-
-static struct cls_match *
-next_rule_in_list(struct cls_match *rule)
-{
- struct cls_match *next = next_rule_in_list__(rule);
- return next->priority < rule->priority ? next : NULL;
-}