- uint8_t be32ofs, unsigned int nbits);
-
-static void
-cls_subtables_init(struct cls_subtables *subtables)
-{
- memset(subtables, 0, sizeof *subtables);
-}
-
-static void
-cls_subtables_destroy(struct cls_subtables *subtables)
-{
- free(subtables->array);
- memset(subtables, 0, sizeof *subtables);
-}
-
-/* Subtables insertion. */
-static void
-cls_subtables_push_back(struct cls_subtables *subtables,
- struct cls_subtable_entry a)
-{
- if (subtables->count == subtables->alloc_size) {
- subtables->array = x2nrealloc(subtables->array, &subtables->alloc_size,
- sizeof a);
- }
-
- subtables->array[subtables->count++] = a;
-}
-
-/* Move subtable entry at 'from' to 'to', shifting the elements in between
- * (including the one at 'to') accordingly. */
-static inline void
-cls_subtables_move(struct cls_subtable_entry *to,
- struct cls_subtable_entry *from)
-{
- if (to != from) {
- struct cls_subtable_entry temp = *from;
-
- if (to > from) {
- /* Shift entries (from,to] backwards to make space at 'to'. */
- memmove(from, from + 1, (to - from) * sizeof *to);
- } else {
- /* Shift entries [to,from) forward to make space at 'to'. */
- memmove(to + 1, to, (from - to) * sizeof *to);
- }
-
- *to = temp;
- }
-}
-
-/* Subtables removal. */
-static inline void
-cls_subtables_remove(struct cls_subtables *subtables,
- struct cls_subtable_entry *elem)
-{
- ssize_t size = (&subtables->array[subtables->count]
- - (elem + 1)) * sizeof *elem;
- if (size > 0) {
- memmove(elem, elem + 1, size);
- }
- subtables->count--;
-}
-
-#define CLS_SUBTABLES_FOR_EACH(SUBTABLE, ITER, SUBTABLES) \
- for ((ITER) = (SUBTABLES)->array; \
- (ITER) < &(SUBTABLES)->array[(SUBTABLES)->count] \
- && OVS_LIKELY((SUBTABLE) = (ITER)->subtable); \
- ++(ITER))
-#define CLS_SUBTABLES_FOR_EACH_CONTINUE(SUBTABLE, ITER, SUBTABLES) \
- for (++(ITER); \
- (ITER) < &(SUBTABLES)->array[(SUBTABLES)->count] \
- && OVS_LIKELY((SUBTABLE) = (ITER)->subtable); \
- ++(ITER))
-#define CLS_SUBTABLES_FOR_EACH_REVERSE(SUBTABLE, ITER, SUBTABLES) \
- for ((ITER) = &(SUBTABLES)->array[(SUBTABLES)->count]; \
- (ITER) > (SUBTABLES)->array \
- && OVS_LIKELY((SUBTABLE) = (--(ITER))->subtable);)
-
-static void
-cls_subtables_verify(struct cls_subtables *subtables)
-{
- struct cls_subtable *table;
- struct cls_subtable_entry *iter;
- unsigned int priority = 0;
-
- CLS_SUBTABLES_FOR_EACH_REVERSE (table, iter, subtables) {
- if (iter->max_priority != table->max_priority) {
- VLOG_WARN("Subtable %p has mismatching priority in cache (%u != %u)",
- table, iter->max_priority, table->max_priority);
- }
- if (iter->max_priority < priority) {
- VLOG_WARN("Subtable cache is out of order (%u < %u)",
- iter->max_priority, priority);
- }
- priority = iter->max_priority;
- }
-}
-
-static void
-cls_subtables_reset(struct cls_classifier *cls)
-{
- struct cls_subtables old = cls->subtables;
- struct cls_subtable *subtable;
-
- VLOG_WARN("Resetting subtable cache.");
-
- cls_subtables_verify(&cls->subtables);
-
- cls_subtables_init(&cls->subtables);
-
- HMAP_FOR_EACH (subtable, hmap_node, &cls->subtables_map) {
- struct cls_match *head;
- struct cls_subtable_entry elem;
- struct cls_subtable *table;
- struct cls_subtable_entry *iter, *from = NULL;
- unsigned int new_max = 0;
- unsigned int max_count = 0;
- bool found;
-
- /* Verify max_priority. */
- HMAP_FOR_EACH (head, hmap_node, &subtable->rules) {
- if (head->priority > new_max) {
- new_max = head->priority;
- max_count = 1;
- } else if (head->priority == new_max) {
- max_count++;
- }
- }
- if (new_max != subtable->max_priority ||
- max_count != subtable->max_count) {
- VLOG_WARN("subtable %p (%u rules) has mismatching max_priority "
- "(%u) or max_count (%u). Highest priority found was %u, "
- "count: %u",
- subtable, subtable->n_rules, subtable->max_priority,
- subtable->max_count, new_max, max_count);
- subtable->max_priority = new_max;
- subtable->max_count = max_count;
- }
-
- /* Locate the subtable from the old cache. */
- found = false;
- CLS_SUBTABLES_FOR_EACH (table, iter, &old) {
- if (table == subtable) {
- if (iter->max_priority != new_max) {
- VLOG_WARN("Subtable %p has wrong max priority (%u != %u) "
- "in the old cache.",
- subtable, iter->max_priority, new_max);
- }
- if (found) {
- VLOG_WARN("Subtable %p duplicated in the old cache.",
- subtable);
- }
- found = true;
- }
- }
- if (!found) {
- VLOG_WARN("Subtable %p not found from the old cache.", subtable);
- }
-
- elem.subtable = subtable;
- elem.tag = subtable->tag;
- elem.max_priority = subtable->max_priority;
- cls_subtables_push_back(&cls->subtables, elem);
-
- /* Possibly move 'subtable' earlier in the priority array. If
- * we break out of the loop, then the subtable (at 'from')
- * should be moved to the position right after the current
- * element. If the loop terminates normally, then 'iter' will
- * be at the first array element and we'll move the subtable
- * to the front of the array. */
- CLS_SUBTABLES_FOR_EACH_REVERSE (table, iter, &cls->subtables) {
- if (table == subtable) {
- from = iter; /* Locate the subtable as we go. */
- } else if (table->max_priority >= new_max) {
- ovs_assert(from != NULL);
- iter++; /* After this. */
- break;
- }
- }
-
- /* Move subtable at 'from' to 'iter'. */
- cls_subtables_move(iter, from);
- }
-
- /* Verify that the old and the new have the same size. */
- if (old.count != cls->subtables.count) {
- VLOG_WARN("subtables cache sizes differ: old (%"PRIuSIZE
- ") != new (%"PRIuSIZE").",
- old.count, cls->subtables.count);
- }
-
- cls_subtables_destroy(&old);
-
- cls_subtables_verify(&cls->subtables);
-}
-