| Message ID | 20230802090824.91688-2-aesteve@redhat.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | Virtio shared dma-buf | expand |
On 2/8/23 11:08, Albert Esteve wrote: > Add hash function to uuid module using the > djb2 hash algorithm. ^ This info ... > Add a couple simple unit tests for the hash > function, checking collisions for similar UUIDs. > > Signed-off-by: Albert Esteve <aesteve@redhat.com> > --- > include/qemu/uuid.h | 2 ++ > tests/unit/test-uuid.c | 27 +++++++++++++++++++++++++++ > util/uuid.c | 14 ++++++++++++++ > 3 files changed, 43 insertions(+) > > diff --git a/include/qemu/uuid.h b/include/qemu/uuid.h > index dc40ee1fc9..e24a1099e4 100644 > --- a/include/qemu/uuid.h > +++ b/include/qemu/uuid.h > @@ -96,4 +96,6 @@ int qemu_uuid_parse(const char *str, QemuUUID *uuid); > > QemuUUID qemu_uuid_bswap(QemuUUID uuid); > > +uint32_t qemu_uuid_hash(const void *uuid); > + > #endif > diff --git a/tests/unit/test-uuid.c b/tests/unit/test-uuid.c > index c111de5fc1..aedc125ae9 100644 > --- a/tests/unit/test-uuid.c > +++ b/tests/unit/test-uuid.c > @@ -171,6 +171,32 @@ 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); > + } > +} > + > int main(int argc, char **argv) > { > g_test_init(&argc, &argv, NULL); > @@ -179,6 +205,7 @@ 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); > > return g_test_run(); > } > diff --git a/util/uuid.c b/util/uuid.c > index b1108dde78..64eaf2e208 100644 > --- a/util/uuid.c > +++ b/util/uuid.c > @@ -116,3 +116,17 @@ QemuUUID qemu_uuid_bswap(QemuUUID uuid) > bswap16s(&uuid.fields.time_high_and_version); > return uuid; > } ... would be more useful as a comment here. /* djb2 hash algorithm */ Anyhow, Reviewed-by: Philippe Mathieu-Daudé <philmd@linaro.org> > +uint32_t qemu_uuid_hash(const void *uuid) > +{ > + QemuUUID *qid = (QemuUUID *) uuid; > + uint32_t h = 5381; > + int i; > + > + for (i = 0; i < ARRAY_SIZE(qid->data); i++) { > + h = (h << 5) + h + qid->data[i]; > + } > + > + return h; > +} > +
diff --git a/include/qemu/uuid.h b/include/qemu/uuid.h index dc40ee1fc9..e24a1099e4 100644 --- a/include/qemu/uuid.h +++ b/include/qemu/uuid.h @@ -96,4 +96,6 @@ int qemu_uuid_parse(const char *str, QemuUUID *uuid); QemuUUID qemu_uuid_bswap(QemuUUID uuid); +uint32_t qemu_uuid_hash(const void *uuid); + #endif diff --git a/tests/unit/test-uuid.c b/tests/unit/test-uuid.c index c111de5fc1..aedc125ae9 100644 --- a/tests/unit/test-uuid.c +++ b/tests/unit/test-uuid.c @@ -171,6 +171,32 @@ 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); + } +} + int main(int argc, char **argv) { g_test_init(&argc, &argv, NULL); @@ -179,6 +205,7 @@ 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); return g_test_run(); } diff --git a/util/uuid.c b/util/uuid.c index b1108dde78..64eaf2e208 100644 --- a/util/uuid.c +++ b/util/uuid.c @@ -116,3 +116,17 @@ QemuUUID qemu_uuid_bswap(QemuUUID uuid) bswap16s(&uuid.fields.time_high_and_version); return uuid; } + +uint32_t qemu_uuid_hash(const void *uuid) +{ + QemuUUID *qid = (QemuUUID *) uuid; + uint32_t h = 5381; + int i; + + for (i = 0; i < ARRAY_SIZE(qid->data); i++) { + h = (h << 5) + h + qid->data[i]; + } + + return h; +} +
Add hash function to uuid module using the djb2 hash algorithm. Add a couple simple unit tests for the hash function, checking collisions for similar UUIDs. Signed-off-by: Albert Esteve <aesteve@redhat.com> --- include/qemu/uuid.h | 2 ++ tests/unit/test-uuid.c | 27 +++++++++++++++++++++++++++ util/uuid.c | 14 ++++++++++++++ 3 files changed, 43 insertions(+)