Open vSwitchのソースコードを読む(10) flow table の検索

static int
handle_upcalls(struct dpif_backer *backer, unsigned int max_batch)
{
    struct dpif_upcall misses[FLOW_MISS_MAX_BATCH];
    struct ofpbuf miss_bufs[FLOW_MISS_MAX_BATCH];
    uint64_t miss_buf_stubs[FLOW_MISS_MAX_BATCH][4096 / 8];
    int n_processed;
    int n_misses;
    int i;

    ovs_assert(max_batch <= FLOW_MISS_MAX_BATCH);

    n_misses = 0;
    for (n_processed = 0; n_processed < max_batch; n_processed++) {
        struct dpif_upcall *upcall = &misses[n_misses];
        struct ofpbuf *buf = &miss_bufs[n_misses];
        int error;

        ofpbuf_use_stub(buf, miss_buf_stubs[n_misses],
                        sizeof miss_buf_stubs[n_misses]);
        error = dpif_recv(backer->dpif, upcall, buf);
        if (error) {
            ofpbuf_uninit(buf);
            break;
        }

        switch (classify_upcall(upcall)) {
        case MISS_UPCALL:
            /* Handle it later. */
            n_misses++;
            break;

        case SFLOW_UPCALL:
            handle_sflow_upcall(backer, upcall);
            ofpbuf_uninit(buf);
            break;

        case BAD_UPCALL:
            ofpbuf_uninit(buf);
            break;
        }
    }

    /* Handle deferred MISS_UPCALL processing. */
    handle_miss_upcalls(backer, misses, n_misses);
    for (i = 0; i < n_misses; i++) {
        ofpbuf_uninit(&miss_bufs[i]);
    }

    return n_processed;
}

static void
handle_miss_upcalls(struct dpif_backer *backer, struct dpif_upcall *upcalls,
                    size_t n_upcalls)
{
    struct dpif_upcall *upcall;
    struct flow_miss *miss;
    struct flow_miss misses[FLOW_MISS_MAX_BATCH];
    struct flow_miss_op flow_miss_ops[FLOW_MISS_MAX_BATCH * 2];
    struct dpif_op *dpif_ops[FLOW_MISS_MAX_BATCH * 2];
    struct hmap todo;
    int n_misses;
    size_t n_ops;
    size_t i;

    if (!n_upcalls) {
        return;
    }

    /* Construct the to-do list.
     *
     * This just amounts to extracting the flow from each packet and sticking
     * the packets that have the same flow in the same "flow_miss" structure so
     * that we can process them together. */
    hmap_init(&todo);
    n_misses = 0;
    for (upcall = upcalls; upcall < &upcalls[n_upcalls]; upcall++) {
        struct flow_miss *miss = &misses[n_misses];
        struct flow_miss *existing_miss;
        struct ofproto_dpif *ofproto;
        uint32_t odp_in_port;
        struct flow flow;
        uint32_t hash;
        int error;

        error = ofproto_receive(backer, upcall->packet, upcall->key,
                                upcall->key_len, &flow, &miss->key_fitness,
                                &ofproto, &odp_in_port, &miss->initial_vals);

        if (error == ENODEV) {
            struct drop_key *drop_key;

            /* Received packet on port for which we couldn't associate
             * an ofproto.  This can happen if a port is removed while
             * traffic is being received.  Print a rate-limited message
             * in case it happens frequently.  Install a drop flow so
             * that future packets of the flow are inexpensively dropped
             * in the kernel. */
            VLOG_INFO_RL(&rl, "received packet on unassociated port %"PRIu32,
                         flow.in_port);

            drop_key = drop_key_lookup(backer, upcall->key, upcall->key_len);
            if (!drop_key) {
                drop_key = xmalloc(sizeof *drop_key);
                drop_key->key = xmemdup(upcall->key, upcall->key_len);
                drop_key->key_len = upcall->key_len;

                hmap_insert(&backer->drop_keys, &drop_key->hmap_node,
                            hash_bytes(drop_key->key, drop_key->key_len, 0));
                dpif_flow_put(backer->dpif, DPIF_FP_CREATE | DPIF_FP_MODIFY,
                              drop_key->key, drop_key->key_len, NULL, 0, NULL);
            }
            continue;
        }
        if (error) {
            continue;
        }

        ofproto->n_missed++;
        flow_extract(upcall->packet, flow.skb_priority, flow.skb_mark,
                     &flow.tunnel, flow.in_port, &miss->flow);

        /* Add other packets to a to-do list. */
        hash = flow_hash(&miss->flow, 0);
        existing_miss = flow_miss_find(&todo, ofproto, &miss->flow, hash);
        if (!existing_miss) {
            hmap_insert(&todo, &miss->hmap_node, hash);
            miss->ofproto = ofproto;
            miss->key = upcall->key;
            miss->key_len = upcall->key_len;
            miss->upcall_type = upcall->type;
            miss->odp_in_port = odp_in_port;
            list_init(&miss->packets);

            n_misses++;
        } else {
            miss = existing_miss;
        }
        list_push_back(&miss->packets, &upcall->packet->list_node);
    }

    /* Process each element in the to-do list, constructing the set of
     * operations to batch. */
    n_ops = 0;
    HMAP_FOR_EACH (miss, hmap_node, &todo) {
        handle_flow_miss(miss, flow_miss_ops, &n_ops);
    }
    ovs_assert(n_ops <= ARRAY_SIZE(flow_miss_ops));

    /* Execute batch. */
    for (i = 0; i < n_ops; i++) {
        dpif_ops[i] = &flow_miss_ops[i].dpif_op;
    }
    dpif_operate(backer->dpif, dpif_ops, n_ops);

    /* Free memory. */
    for (i = 0; i < n_ops; i++) {
        free(flow_miss_ops[i].garbage);
    }
    hmap_destroy(&todo);
}

/* Handles flow miss 'miss'.  May add any required datapath operations
 * to 'ops', incrementing '*n_ops' for each new op. */
static void
handle_flow_miss(struct flow_miss *miss, struct flow_miss_op *ops,
                 size_t *n_ops)
{
    struct ofproto_dpif *ofproto = miss->ofproto;
    struct facet *facet;
    long long int now;
    uint32_t hash;

    /* The caller must ensure that miss->hmap_node.hash contains
     * flow_hash(miss->flow, 0). */
    hash = miss->hmap_node.hash;

    facet = facet_lookup_valid(ofproto, &miss->flow, hash);
    if (!facet) {
        struct rule_dpif *rule = rule_dpif_lookup(ofproto, &miss->flow);

        if (!flow_miss_should_make_facet(ofproto, miss, hash)) {
            handle_flow_miss_without_facet(miss, rule, ops, n_ops);
            return;
        }

        facet = facet_create(rule, &miss->flow, hash);
        now = facet->used;
    } else {
        now = time_msec();
    }
    handle_flow_miss_with_facet(miss, facet, now, ops, n_ops);
}

/* Handles 'miss', which matches 'facet'.  May add any required datapath
 * operations to 'ops', incrementing '*n_ops' for each new op.
 *
 * All of the packets in 'miss' are considered to have arrived at time 'now'.
 * This is really important only for new facets: if we just called time_msec()
 * here, then the new subfacet or its packets could look (occasionally) as
 * though it was used some time after the facet was used.  That can make a
 * one-packet flow look like it has a nonzero duration, which looks odd in
 * e.g. NetFlow statistics. */
static void
handle_flow_miss_with_facet(struct flow_miss *miss, struct facet *facet,
                            long long int now,
                            struct flow_miss_op *ops, size_t *n_ops)
{
    struct ofproto_dpif *ofproto = ofproto_dpif_cast(facet->rule->up.ofproto);
    enum subfacet_path want_path;
    struct subfacet *subfacet;
    struct ofpbuf *packet;

    subfacet = subfacet_create(facet, miss, now);

    LIST_FOR_EACH (packet, list_node, &miss->packets) {
        struct flow_miss_op *op = &ops[*n_ops];
        struct dpif_flow_stats stats;
        struct ofpbuf odp_actions;

        handle_flow_miss_common(facet->rule, packet, &miss->flow);

        ofpbuf_use_stub(&odp_actions, op->stub, sizeof op->stub);
        if (!subfacet->actions || subfacet->slow) {
            subfacet_make_actions(subfacet, packet, &odp_actions);
        }

        dpif_flow_stats_extract(&facet->flow, packet, now, &stats);
        subfacet_update_stats(subfacet, &stats);

        if (subfacet->actions_len) {
            struct dpif_execute *execute = &op->dpif_op.u.execute;

            init_flow_miss_execute_op(miss, packet, op);
            if (!subfacet->slow) {
                execute->actions = subfacet->actions;
                execute->actions_len = subfacet->actions_len;
                ofpbuf_uninit(&odp_actions);
            } else {
                execute->actions = odp_actions.data;
                execute->actions_len = odp_actions.size;
                op->garbage = ofpbuf_get_uninit_pointer(&odp_actions);
            }

            (*n_ops)++;
        } else {
            ofpbuf_uninit(&odp_actions);
        }
    }

    want_path = subfacet_want_path(subfacet->slow);
    if (miss->upcall_type == DPIF_UC_MISS || subfacet->path != want_path) {
        struct flow_miss_op *op = &ops[(*n_ops)++];
        struct dpif_flow_put *put = &op->dpif_op.u.flow_put;

        subfacet->path = want_path;

        op->garbage = NULL;
        op->dpif_op.type = DPIF_OP_FLOW_PUT;
        put->flags = DPIF_FP_CREATE | DPIF_FP_MODIFY;
        put->key = miss->key;
        put->key_len = miss->key_len;
        if (want_path == SF_FAST_PATH) {
            put->actions = subfacet->actions;
            put->actions_len = subfacet->actions_len;
        } else {
            compose_slow_path(ofproto, &facet->flow, subfacet->slow,
                              op->stub, sizeof op->stub,
                              &put->actions, &put->actions_len);
        }
        put->stats = NULL;
    }
}

/* Rules. */

static struct rule_dpif *
rule_dpif_lookup(struct ofproto_dpif *ofproto, const struct flow *flow)
{
    struct rule_dpif *rule;

    rule = rule_dpif_lookup__(ofproto, flow, 0);
    if (rule) {
        return rule;
    }

    return rule_dpif_miss_rule(ofproto, flow);
}

static struct rule_dpif *
rule_dpif_lookup__(struct ofproto_dpif *ofproto, const struct flow *flow,
                   uint8_t table_id)
{
    struct cls_rule *cls_rule;
    struct classifier *cls;

    if (table_id >= N_TABLES) {
        return NULL;
    }

    cls = &ofproto->up.tables[table_id].cls;
    if (flow->nw_frag & FLOW_NW_FRAG_ANY
        && ofproto->up.frag_handling == OFPC_FRAG_NORMAL) {
        /* For OFPC_NORMAL frag_handling, we must pretend that transport ports
         * are unavailable. */
        struct flow ofpc_normal_flow = *flow;
        ofpc_normal_flow.tp_src = htons(0);
        ofpc_normal_flow.tp_dst = htons(0);
        cls_rule = classifier_lookup(cls, &ofpc_normal_flow);
    } else {
        cls_rule = classifier_lookup(cls, flow);
    }
    return rule_dpif_cast(rule_from_cls_rule(cls_rule));
}

/* Finds and returns the highest-priority rule in 'cls' that matches 'flow'.
 * Returns a null pointer if no rules in 'cls' match 'flow'.  If multiple rules
 * of equal priority match 'flow', returns one arbitrarily. */
struct cls_rule *
classifier_lookup(const struct classifier *cls, const struct flow *flow)
{
    struct cls_table *table;
    struct cls_rule *best;

    best = NULL;
    HMAP_FOR_EACH (table, hmap_node, &cls->tables) {
        struct cls_rule *rule = find_match(table, flow);
        if (rule && (!best || rule->priority > best->priority)) {
            best = rule;
        }
    }
    return best;
}

/* A set of rules that all have the same fields wildcarded. */
struct cls_table {
    struct hmap_node hmap_node; /* Within struct classifier 'tables' hmap. */
    struct hmap rules;          /* Contains "struct cls_rule"s. */
    struct minimask mask;       /* Wildcards for fields. */
    int n_table_rules;          /* Number of rules, including duplicates. */
};

static struct cls_rule *
find_match(const struct cls_table *table, const struct flow *flow)
{
    uint32_t hash = flow_hash_in_minimask(flow, &table->mask, 0);
    struct cls_rule *rule;

    HMAP_FOR_EACH_WITH_HASH (rule, hmap_node, hash, &table->rules) {
        if (miniflow_equal_flow_in_minimask(&rule->match.flow, flow,
                                            &table->mask)) {
            return rule;
        }
    }

    return NULL;
}

/* A sparse representation of a "struct flow".
 *
 * A "struct flow" is fairly large and tends to be mostly zeros.  Sparse
 * representation has two advantages.  First, it saves memory.  Second, it
 * saves time when the goal is to iterate over only the nonzero parts of the
 * struct.
 *
 * The 'map' member holds one bit for each uint32_t in a "struct flow".  Each
 * 0-bit indicates that the corresponding uint32_t is zero, each 1-bit that it
 * is nonzero.
 *
 * 'values' points to the start of an array that has one element for each 1-bit
 * in 'map'.  The least-numbered 1-bit is in values[0], the next 1-bit is in
 * values[1], and so on.
 *
 * 'values' may point to a few different locations:
 *
 *     - If 'map' has MINI_N_INLINE or fewer 1-bits, it may point to
 *       'inline_values'.  One hopes that this is the common case.
 *
 *     - If 'map' has more than MINI_N_INLINE 1-bits, it may point to memory
 *       allocated with malloc().
 *
 *     - The caller could provide storage on the stack for situations where
 *       that makes sense.  So far that's only proved useful for
 *       minimask_combine(), but the principle works elsewhere.
 *
 * The implementation maintains and depends on the invariant that every element
 * in 'values' is nonzero; that is, wherever a 1-bit appears in 'map', the
 * corresponding element of 'values' must be nonzero.
 */