[ovs-dev] [PATCH v3] Improve kernel hash table

Jesse Gross jesse at nicira.com
Fri Sep 9 21:07:31 UTC 2011


On Thu, Sep 8, 2011 at 5:08 PM, Pravin Shelar <pshelar at nicira.com> wrote:
>  Currently OVS uses its own hashing implmentation for hash tables
> which has some problems, e.g. error case on deletion code.
> Following patch replaces that with hlist based hash table which is
> consistent with other kernel hash tables. As Jesse suggested, flex-array
> is used for allocating hash buckets, So that we can have large
> hash-table without large contiguous kernel memory.
>
> Signed-off-by: Pravin B Shelar <pshelar at nicira.com>

I have a few minor comments but this basically looks good to me.  I
don't think anything here is large enough to warrant another round of
review (there's nothing that is an actual bug).  Can you just let me
know what you think about the comments and then we can go from there?

> diff --git a/datapath/flow.c b/datapath/flow.c
> index e091f50..9be0224 100644
> --- a/datapath/flow.c
> +++ b/datapath/flow.c
> +void flow_tbl_destroy(struct flow_table *table)
> +{
> +       int i;
> +
> +       for (i = 0; i < table->n_buckets; i++) {
> +               struct sw_flow *flow;
> +               struct hlist_head *head = flex_array_get(table->buckets, i);
> +               struct hlist_node *node, *n;
> +
> +               hlist_for_each_entry_safe(flow, node, n, head, hash_node) {
> +                       hlist_del_init_rcu(&flow->hash_node);
> +                       flow_free(flow);
> +               }
> +       }

The usual convention for destroy functions is that passing NULL is OK.
 No caller relies on that but since the rest of the OVS code and the
kernel in general support this convention, can we add a check for NULL
at the beginning?

> +struct flow_table *flow_tbl_expand(struct flow_table *table)
> +{
> +       struct flow_table *new_table;
> +       struct sw_flow *flow;
> +       struct hlist_head *head;
> +       struct hlist_node *n, *pos;
> +       int n_buckets = table->n_buckets << 1;

I'm not sure why you kept the shift here.  It's obviously error prone
as we have already seen and is less clear than a simple multiply.  The
compiler is very good at recognizing multiplication and division by
powers of two and converting them to shifts so there's no difference
in the resulting compiled code.

> diff --git a/datapath/tunnel.c b/datapath/tunnel.c
> index 67556d7..738d1f8 100644
> --- a/datapath/tunnel.c
> +++ b/datapath/tunnel.c
> +static void tbl_add_port(struct vport *vport)
[...]
> +static void tbl_move_port(struct vport *vport,
> +                     struct tnl_mutable_config *new_mutable)
[...]
> +static void tbl_remove_port(struct vport *vport)

The tbl_ prefix on these functions really make me think that they
belong to some other module, not an integrated part of the tunnel
code.  Can we change it to port_table_[add/move/remove] or something
similar?

> +void tnl_exit(void)
> +{
> +       struct hlist_node *n, *pos;
> +       struct hlist_head *hash_head;
> +       struct tnl_vport * tnl_vport;
> +       int i;
> +
> +       if (!port_table)
> +               return;

This can never happen, right?

> +       cancel_delayed_work_sync(&cache_cleaner_wq);

This should have been stopped when the last port is removed, right?

> +       for (i = 0; i < PORT_TABLE_SIZE; i++) {
> +               hash_head = &port_table[i];
> +               hlist_for_each_entry_safe(tnl_vport, pos, n, hash_head,
> +                                         hash_node) {

It's not actually necessary to use the _safe variant since nothing is
getting removed by it.  I also noticed that you have a tendency to
declare variables at beginning of the function instead of the closest
scoped region (in this case the for loop), which is generally
preferred.



More information about the dev mailing list