Hi On Mon, May 22, 2023 at 5:41 PM Albert Esteve <aest...@redhat.com> wrote:
> > > > On Mon, May 22, 2023 at 3:13 PM Albert Esteve <aest...@redhat.com> wrote: > >> >> >> >> On Sat, May 20, 2023 at 9:36 AM Marc-André Lureau < >> marcandre.lur...@gmail.com> wrote: >> >>> Hi >>> >>> On Thu, May 18, 2023 at 4:03 PM Albert Esteve <aest...@redhat.com> >>> wrote: >>> >>>> Add hash and an equal function to uuid module. >>>> >>>> Add a couple simple unit tests for new functions, >>>> checking collisions for similar UUIDs in the case >>>> of the hash function, and comparing generated UUIDs >>>> for the equal function. >>>> >>>> Signed-off-by: Albert Esteve <aest...@redhat.com> >>>> --- >>>> include/qemu/uuid.h | 4 ++++ >>>> tests/unit/test-uuid.c | 46 ++++++++++++++++++++++++++++++++++++++++++ >>>> util/uuid.c | 38 ++++++++++++++++++++++++++++++++++ >>>> 3 files changed, 88 insertions(+) >>>> >>>> diff --git a/include/qemu/uuid.h b/include/qemu/uuid.h >>>> index dc40ee1fc9..136df682c9 100644 >>>> --- a/include/qemu/uuid.h >>>> +++ b/include/qemu/uuid.h >>>> @@ -96,4 +96,8 @@ int qemu_uuid_parse(const char *str, QemuUUID *uuid); >>>> >>>> QemuUUID qemu_uuid_bswap(QemuUUID uuid); >>>> >>>> +uint32_t qemu_uuid_hash(const void *uuid); >>>> + >>>> +int qemu_uuid_equal(const void *lhv, const void *rhv); >>>> >>> >>> There is already qemu_uuid_is_equal() >>> >>> >> >> Agh, true. I'll remove it. Not sure why my brain ignored it as I was >> reading the code... >> > > One thing to consider here is that the function signature, if we want to > pass it as a parameter for g_hash_table_new, > expects void pointers whereas qemu_uuid_is_equal() takes QemuUUID pointers. > > How would you suggest proceeding here? Would be better to "overload" (or > wrap) a call to qemu_uuid_equal() from > another function that matches the expected signature? (int > qemu_uuid_is_equal(void*, void*) is not a good name in that case, > it should be something that highlights the difference between the two in > the name) Or should I change the current existing > function signature? > I would wrap the call, next to g_hash_table_new(). Alternatively, just cast the function. > > >> >>> + >>>> #endif >>>> diff --git a/tests/unit/test-uuid.c b/tests/unit/test-uuid.c >>>> index c111de5fc1..8c865869d5 100644 >>>> --- a/tests/unit/test-uuid.c >>>> +++ b/tests/unit/test-uuid.c >>>> @@ -171,6 +171,50 @@ static void test_uuid_unparse_strdup(void) >>>> } >>>> } >>>> >>>> +static void test_uuid_hash(void) >>>> +{ >>>> + QemuUUID uuid; >>>> + int i; >>>> + >>>> + for (i = 0; i < 100; i++) { >>>> + qemu_uuid_generate(&uuid); >>>> + /* Obtain the UUID hash */ >>>> + uint32_t hash_a = qemu_uuid_hash(&uuid); >>>> + int data_idx = g_random_int_range(0, 15); >>>> + /* Change a single random byte of the UUID */ >>>> + if (uuid.data[data_idx] < 0xFF) { >>>> + uuid.data[data_idx]++; >>>> + } else { >>>> + uuid.data[data_idx]--; >>>> + } >>>> + /* Obtain the UUID hash again */ >>>> + uint32_t hash_b = qemu_uuid_hash(&uuid); >>>> + /* >>>> + * Both hashes shall be different (avoid collision) >>>> + * for any change in the UUID fields >>>> + */ >>>> + g_assert_cmpint(hash_a, !=, hash_b); >>>> + } >>>> +} >>>> + >>>> +static void test_uuid_equal(void) >>>> +{ >>>> + QemuUUID uuid_a, uuid_b, uuid_c; >>>> + int i; >>>> + >>>> + for (i = 0; i < 100; i++) { >>>> + qemu_uuid_generate(&uuid_a); >>>> + qemu_uuid_generate(&uuid_b); >>>> + memcpy(&uuid_c, &uuid_a, sizeof(uuid_a)); >>>> + >>>> + g_assert(qemu_uuid_equal(&uuid_a, &uuid_a)); >>>> + g_assert(qemu_uuid_equal(&uuid_b, &uuid_b)); >>>> + g_assert(qemu_uuid_equal(&uuid_a, &uuid_c)); >>>> + g_assert_false(qemu_uuid_equal(&uuid_a, &uuid_b)); >>>> + g_assert_false(qemu_uuid_equal(NULL, NULL)); >>>> + } >>>> +} >>>> + >>>> int main(int argc, char **argv) >>>> { >>>> g_test_init(&argc, &argv, NULL); >>>> @@ -179,6 +223,8 @@ int main(int argc, char **argv) >>>> g_test_add_func("/uuid/parse", test_uuid_parse); >>>> g_test_add_func("/uuid/unparse", test_uuid_unparse); >>>> g_test_add_func("/uuid/unparse_strdup", test_uuid_unparse_strdup); >>>> + g_test_add_func("/uuid/hash", test_uuid_hash); >>>> + g_test_add_func("/uuid/equal", test_uuid_equal); >>>> >>>> return g_test_run(); >>>> } >>>> diff --git a/util/uuid.c b/util/uuid.c >>>> index b1108dde78..efa9b0a0e4 100644 >>>> --- a/util/uuid.c >>>> +++ b/util/uuid.c >>>> @@ -16,6 +16,7 @@ >>>> #include "qemu/osdep.h" >>>> #include "qemu/uuid.h" >>>> #include "qemu/bswap.h" >>>> +#include "qemu/xxhash.h" >>>> >>>> void qemu_uuid_generate(QemuUUID *uuid) >>>> { >>>> @@ -116,3 +117,40 @@ QemuUUID qemu_uuid_bswap(QemuUUID uuid) >>>> bswap16s(&uuid.fields.time_high_and_version); >>>> return uuid; >>>> } >>>> + >>>> +uint32_t qemu_uuid_hash(const void *uuid) >>>> +{ >>>> + QemuUUID *id = (QemuUUID *) uuid; >>>> + uint64_t ab = (id->fields.time_low) | >>>> + (((uint64_t) id->fields.time_mid) << 32) | >>>> + (((uint64_t) id->fields.time_high_and_version) << >>>> 48); >>>> + uint64_t cd = (id->fields.clock_seq_and_reserved) | >>>> + (id->fields.clock_seq_low << 8); >>>> + int i = 0, shift = 8; >>>> + >>>> + for (; i < 6; i++) { >>>> + shift += 8; >>>> + cd |= ((uint64_t) id->fields.node[i]) << shift; >>>> + } >>>> + >>>> + return qemu_xxhash4(ab, cd); >>>> + >>>> >>> >>> That looks quite complex, and I have no idea if this is a good hash or >>> not. >>> >>> Instead I would implement the traditional "djb" hash over the char[16] >>> data (see g_str_hash implementation for \0-terminated implementation) >>> >> >> ok, I'll try to do something like that. Thanks for the suggestion. >> >> I looked for any hash library within qemu code and xxhash was one of the >> options that seemed easier to use. >> >> >>> >>> >>>> } >>>> + >>>> +int qemu_uuid_equal(const void *lhv, const void *rhv) >>>> +{ >>>> + int i; >>>> + QemuUUID *lid = (QemuUUID *) lhv; >>>> + QemuUUID *rid = (QemuUUID *) rhv; >>>> + if (lid == NULL || rid == NULL) { >>>> + return 0; >>>> + } >>>> + if (lid == rid) { >>>> + return 1; >>>> + } >>>> + for (i = 0; i < 16; i++) { >>>> + if (lid->data[i] != rid->data[i]) { >>>> + return 0; >>>> + } >>>> + } >>>> + return 1; >>>> +} >>>> -- >>>> 2.40.0 >>>> >>>> >>> >>> -- >>> Marc-André Lureau >>> >> -- Marc-André Lureau