[ovs-dev] Question about moving the uuidset implementation from OVN to OVS

Hi Ben,

I was working on adding some OVN code and I realized I needed a uuidset
implementation.  OVN code already has a couple custom structures that do
that but it turns out (thanks Ilya for pointing it out) we actually have
an almost complete explicit uuidset implementation in
ovn-northd-ddlog.c:

https://github.com/ovn-org/ovn/blob/ae456e4fb70175ba8ec6bee96102bf9d85af3853/northd/ovn-northd-ddlog.c#L698

This code was introduced by the following OVN commit:
  0e77b3bcbfe2 ("ovn-northd-ddlog: New implementation of ovn-northd based on ddlog.")

which was authored by Leonid, Justin and you.

As OVN will be using this in a few places and due to the fact that a
uuidset is a generic data structure I think this code should actually
live in OVS.

I'd like to post an OVS patch to add this along with some more helpers
(see below) but I have a couple of questions:

1. What's the correct/desired way of maintaining authorship in this
case?  I can keep all original authors and add my own sign off to it too
but is that ok?

2. It seems we miss a copyright notice in ovn-northd-ddlog.c.  Would it
be ok if I add the following?

 * Copyright (c) 2020, 2022 VMware, Inc.
 * Copyright (c) 2022 Red Hat, Inc.

Thanks,
Dumitru

---

On 9/16/22 14:30, Dumitru Ceara wrote:
> Hi Ben,
> 
> I was working on adding some OVN code and I realized I needed a uuidset
> implementation.  OVN code already has a couple custom structures that do
> that but it turns out (thanks Ilya for pointing it out) we actually have
> an almost complete explicit uuidset implementation in
> ovn-northd-ddlog.c:
> 
> https://github.com/ovn-org/ovn/blob/ae456e4fb70175ba8ec6bee96102bf9d85af3853/northd/ovn-northd-ddlog.c#L698
> 
> This code was introduced by the following OVN commit:
>   0e77b3bcbfe2 ("ovn-northd-ddlog: New implementation of ovn-northd based on ddlog.")
> 
> which was authored by Leonid, Justin and you.
> 
> As OVN will be using this in a few places and due to the fact that a
> uuidset is a generic data structure I think this code should actually
> live in OVS.
> 
> I'd like to post an OVS patch to add this along with some more helpers
> (see below) but I have a couple of questions:

I had forgotten to add the test file, I appended it as an incremental
at the end.

> 
> 1. What's the correct/desired way of maintaining authorship in this
> case?  I can keep all original authors and add my own sign off to it too
> but is that ok?
> 
> 2. It seems we miss a copyright notice in ovn-northd-ddlog.c.  Would it
> be ok if I add the following?
> 
>  * Copyright (c) 2020, 2022 VMware, Inc.
>  * Copyright (c) 2022 Red Hat, Inc.
> 
> Thanks,
> Dumitru
> 
> ---
> diff --git a/lib/automake.mk b/lib/automake.mk
> index a76de6dbfc4c..a0fabe38f36b 100644
> --- a/lib/automake.mk
> +++ b/lib/automake.mk
> @@ -386,6 +386,8 @@ lib_libopenvswitch_la_SOURCES = \
>  	lib/util.h \
>  	lib/uuid.c \
>  	lib/uuid.h \
> +	lib/uuidset.c \
> +	lib/uuidset.h \
>  	lib/valgrind.h \
>  	lib/vconn-provider.h \
>  	lib/vconn-stream.c \
> diff --git a/lib/uuidset.c b/lib/uuidset.c
> new file mode 100644
> index 000000000000..2b78df240b40
> --- /dev/null
> +++ b/lib/uuidset.c
> @@ -0,0 +1,98 @@
> +/*
> + * Copyright (c) 2022 TBD.
> + *
> + * Licensed under the Apache License, Version 2.0 (the "License");
> + * you may not use this file except in compliance with the License.
> + * You may obtain a copy of the License at:
> + *
> + *     http://www.apache.org/licenses/LICENSE-2.0
> + *
> + * Unless required by applicable law or agreed to in writing, software
> + * distributed under the License is distributed on an "AS IS" BASIS,
> + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
> + * See the License for the specific language governing permissions and
> + * limitations under the License.
> + */
> +
> +#include <config.h>
> +
> +#include "lib/uuidset.h"
> +#include "lib/util.h"
> +
> +void
> +uuidset_init(struct uuidset *set)
> +{
> +    hmap_init(&set->uuids);
> +}
> +
> +void
> +uuidset_destroy(struct uuidset *set)
> +{
> +    if (set) {
> +        uuidset_clear(set);
> +        hmap_destroy(&set->uuids);
> +    }
> +}
> +
> +void uuidset_clear(struct uuidset *set)
> +{
> +    struct uuidset_node *node;
> +
> +    HMAP_FOR_EACH_SAFE (node, hmap_node, &set->uuids) {
> +        uuidset_delete(set, node);
> +    }
> +}
> +
> +struct uuidset_node *
> +uuidset_find(const struct uuidset *set, const struct uuid *uuid)
> +{
> +    struct uuidset_node *node;
> +
> +    HMAP_FOR_EACH_WITH_HASH (node, hmap_node, uuid_hash(uuid), &set->uuids) {
> +        if (uuid_equals(uuid, &node->uuid)) {
> +            return node;
> +        }
> +    }
> +
> +    return NULL;
> +}
> +
> +bool
> +uuidset_find_and_delete(struct uuidset *set, const struct uuid *uuid)
> +{
> +    struct uuidset_node *node = uuidset_find(set, uuid);
> +    if (node) {
> +        uuidset_delete(set, node);
> +    }
> +    return !!node;
> +}
> +
> +void
> +uuidset_insert(struct uuidset *set, const struct uuid *uuid)
> +{
> +    if (!uuidset_find(set, uuid)) {
> +        struct uuidset_node *node = xmalloc(sizeof *node);
> +        node->uuid = *uuid;
> +        hmap_insert(&set->uuids, &node->hmap_node, uuid_hash(&node->uuid));
> +    }
> +}
> +
> +void
> +uuidset_delete(struct uuidset *set, struct uuidset_node *node)
> +{
> +    hmap_remove(&set->uuids, &node->hmap_node);
> +    free(node);
> +}
> +
> +struct uuid*
> +uuidset_array(const struct uuidset *set)
> +{
> +    struct uuid *array = xmalloc(uuidset_count(set) * sizeof *array);
> +    struct uuidset_node *node;
> +    size_t i = 0;
> +
> +    UUIDSET_FOR_EACH (node, set) {
> +        array[i++] = node->uuid;
> +    }
> +    return array;
> +}
> diff --git a/lib/uuidset.h b/lib/uuidset.h
> new file mode 100644
> index 000000000000..6ce7fd77fa86
> --- /dev/null
> +++ b/lib/uuidset.h
> @@ -0,0 +1,70 @@
> +/*
> + * Copyright (c) 2022 TBD.
> + *
> + * Licensed under the Apache License, Version 2.0 (the "License");
> + * you may not use this file except in compliance with the License.
> + * You may obtain a copy of the License at:
> + *
> + *     http://www.apache.org/licenses/LICENSE-2.0
> + *
> + * Unless required by applicable law or agreed to in writing, software
> + * distributed under the License is distributed on an "AS IS" BASIS,
> + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
> + * See the License for the specific language governing permissions and
> + * limitations under the License.
> + */
> +
> +#ifndef OVN_UUIDSET_H
> +#define OVN_UUIDSET_H 1
> +
> +#include "lib/uuid.h"
> +#include "openvswitch/hmap.h"
> +
> +/* A node within a set of uuids. */
> +struct uuidset_node {
> +    struct hmap_node hmap_node;
> +    struct uuid uuid;
> +};
> +
> +/* A set of UUIDs. */
> +struct uuidset {
> +    struct hmap uuids;
> +};
> +
> +#define UUIDSET_INITIALIZER(UUIDSET) \
> +    { .uuids = HMAP_INITIALIZER(&(UUIDSET)->uuids) }
> +
> +#define UUIDSET_FOR_EACH(NODE, SET) \
> +    HMAP_FOR_EACH (NODE, hmap_node, &(SET)->uuids)
> +
> +#define UUIDSET_FOR_EACH_SAFE(NODE, SET) \
> +    HMAP_FOR_EACH_SAFE (NODE, hmap_node, &(SET)->uuids)
> +
> +void uuidset_init(struct uuidset *);
> +void uuidset_destroy(struct uuidset *);
> +void uuidset_clear(struct uuidset *);
> +struct uuidset_node *uuidset_find(const struct uuidset *, const struct uuid *);
> +bool uuidset_find_and_delete(struct uuidset *, const struct uuid *);
> +void uuidset_insert(struct uuidset *, const struct uuid *);
> +void uuidset_delete(struct uuidset *, struct uuidset_node *);
> +struct uuid *uuidset_array(const struct uuidset *);
> +
> +static inline bool
> +uuidset_is_empty(const struct uuidset *set)
> +{
> +    return hmap_is_empty(&set->uuids);
> +}
> +
> +static inline size_t
> +uuidset_count(const struct uuidset *set)
> +{
> +    return hmap_count(&set->uuids);
> +}
> +
> +static inline bool
> +uuidset_contains(const struct uuidset *set, const struct uuid *uuid)
> +{
> +    return !!uuidset_find(set, uuid);
> +}
> +
> +#endif /* lib/uuidset.h */
> diff --git a/tests/.gitignore b/tests/.gitignore
> index a3d927e5d5ec..83b1cb3b489e 100644
> --- a/tests/.gitignore
> +++ b/tests/.gitignore
> @@ -67,6 +67,7 @@
>  /test-unix-socket
>  /test-util
>  /test-uuid
> +/test-uuidset
>  /test-vconn
>  /testsuite
>  /testsuite.dir/
> diff --git a/tests/automake.mk b/tests/automake.mk
> index 4b6dfd341f95..d509cf935045 100644
> --- a/tests/automake.mk
> +++ b/tests/automake.mk
> @@ -483,6 +483,7 @@ tests_ovstest_SOURCES = \
>  	tests/test-unixctl.c \
>  	tests/test-util.c \
>  	tests/test-uuid.c \
> +	tests/test-uuidset.c \
>  	tests/test-bitmap.c \
>  	tests/test-vconn.c \
>  	tests/test-aa.c \
> diff --git a/tests/library.at b/tests/library.at
> index e60d7707b8aa..bafb28277e8f 100644
> --- a/tests/library.at
> +++ b/tests/library.at
> @@ -274,3 +274,7 @@ AT_CLEANUP
>  AT_SETUP([id-fpool module])
>  AT_CHECK([ovstest test-id-fpool check], [0], [])
>  AT_CLEANUP
> +
> +AT_SETUP([uuidset module])
> +AT_CHECK([ovstest test-uuidset], [0], [], [ignore])
> +AT_CLEANUP

diff --git a/tests/test-uuidset.c b/tests/test-uuidset.c
new file mode 100644
index 000000000000..5f9dcf183d61
--- /dev/null
+++ b/tests/test-uuidset.c
@@ -0,0 +1,72 @@
+/*
+ * Copyright (c) 2022 Red Hat, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <config.h>
+
+#include "lib/util.h"
+#include "lib/uuidset.h"
+
+#include "ovstest.h"
+
+static void
+test_uuidset_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
+{
+    struct uuidset set = UUIDSET_INITIALIZER(&set);
+    struct uuid uuids[2];
+
+    for (size_t i = 0; i < ARRAY_SIZE(uuids); i++) {
+        uuid_generate(&uuids[i]);
+    }
+
+    ovs_assert(uuidset_is_empty(&set));
+
+    for (size_t i = 0; i < ARRAY_SIZE(uuids); i++) {
+        struct uuid *u = &uuids[i];
+
+        if (i == 0) {
+            ovs_assert(uuidset_is_empty(&set));
+        } else {
+            ovs_assert(!uuidset_is_empty(&set));
+        }
+        ovs_assert(uuidset_count(&set) == i);
+        ovs_assert(!uuidset_contains(&set, u));
+        ovs_assert(!uuidset_find_and_delete(&set, u));
+
+        /* Insert twice to check set property. */
+        uuidset_insert(&set, u);
+        uuidset_insert(&set, u);
+        ovs_assert(uuidset_count(&set) == i + 1);
+
+        struct uuidset_node *n = uuidset_find(&set, u);
+        ovs_assert(n);
+        uuidset_delete(&set, n);
+        ovs_assert(uuidset_count(&set) == i);
+        ovs_assert(!uuidset_contains(&set, u));
+
+        uuidset_insert(&set, u);
+        ovs_assert(uuidset_count(&set) == i + 1);
+        ovs_assert(uuidset_contains(&set, u));
+        ovs_assert(uuidset_find_and_delete(&set, u));
+        ovs_assert(uuidset_count(&set) == i);
+        ovs_assert(!uuidset_contains(&set, u));
+
+        uuidset_insert(&set, u);
+    }
+
+    uuidset_destroy(&set);
+}
+
+OVSTEST_REGISTER("test-uuidset", test_uuidset_main);

On Fri, Sep 16, 2022 at 5:30 AM Dumitru Ceara <dceara@redhat.com> wrote:
> I'd like to post an OVS patch to add this along with some more helpers
> (see below) but I have a couple of questions:
>
> 1. What's the correct/desired way of maintaining authorship in this
> case?  I can keep all original authors and add my own sign off to it too
> but is that ok?

Seems OK to me.

> 2. It seems we miss a copyright notice in ovn-northd-ddlog.c.  Would it
> be ok if I add the following?
>
>  * Copyright (c) 2020, 2022 VMware, Inc.
>  * Copyright (c) 2022 Red Hat, Inc.

That also seems OK to me.

Thanks,

Ben.

On 9/16/22 17:04, Ben Pfaff wrote:
> On Fri, Sep 16, 2022 at 5:30 AM Dumitru Ceara <dceara@redhat.com> wrote:
>> I'd like to post an OVS patch to add this along with some more helpers
>> (see below) but I have a couple of questions:
>>
>> 1. What's the correct/desired way of maintaining authorship in this
>> case?  I can keep all original authors and add my own sign off to it too
>> but is that ok?
> 
> Seems OK to me.
> 
>> 2. It seems we miss a copyright notice in ovn-northd-ddlog.c.  Would it
>> be ok if I add the following?
>>
>>  * Copyright (c) 2020, 2022 VMware, Inc.
>>  * Copyright (c) 2022 Red Hat, Inc.
> 
> That also seems OK to me.
> 

Great, thanks!  I posted a formal patch:

https://patchwork.ozlabs.org/project/openvswitch/patch/20220916155025.229354-1-dceara@redhat.com/

> Thanks,
> 
> Ben.
>