[PATCH v2 2/3] erofs-utils: lib: add bloom filter

[Hongzhen Luo]

Introduce following bloom filter helpers:

	erofs_bloom_init
	erofs_bloom_add
	erofs_bloom_test
	erofs_bloom_exit

Signed-off-by: Hongzhen Luo <hongzhen at linux.alibaba.com>
---
v2: Fold `struct bitmap` into `struct erofs_bloom_filter` to make it look cleaner.
v1: https://lore.kernel.org/all/20240718054025.427439-2-hongzhen@linux.alibaba.com/
---
 include/erofs/bloom_filter.h | 31 ++++++++++++
 include/erofs/internal.h     |  2 +
 lib/Makefile.am              |  2 +-
 lib/bloom_filter.c           | 93 ++++++++++++++++++++++++++++++++++++
 4 files changed, 127 insertions(+), 1 deletion(-)
 create mode 100644 include/erofs/bloom_filter.h
 create mode 100644 lib/bloom_filter.c

diff --git a/include/erofs/bloom_filter.h b/include/erofs/bloom_filter.h
new file mode 100644
index 0000000..6f30190
--- /dev/null
+++ b/include/erofs/bloom_filter.h
@@ -0,0 +1,31 @@
+/* SPDX-License-Identifier: GPL-2.0+ OR Apache-2.0 */
+#ifndef __EROFS_BLOOM_FILTER_H
+#define __EROFS_BLOOM_FILTER_H
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+#include "internal.h"
+#include "bitops.h"
+
+struct erofs_bloom_filter {
+        unsigned long size;
+        unsigned long *map;
+        unsigned long bitmap_mask;
+        u32 hash_seed;
+        u32 nr_funcs;
+};
+
+int erofs_bloom_init(struct erofs_sb_info *sbi, u32 nr_funcs,
+                     unsigned long entries, u32 seed);
+long erofs_bloom_add(struct erofs_sb_info *sbi, void *data, size_t length);
+long erofs_bloom_test(struct erofs_sb_info *sbi, void *data, size_t length);
+void erofs_bloom_exit(struct erofs_sb_info *sbi);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/include/erofs/internal.h b/include/erofs/internal.h
index 708e51e..d3dd676 100644
--- a/include/erofs/internal.h
+++ b/include/erofs/internal.h
@@ -74,6 +74,7 @@ struct erofs_xattr_prefix_item {
 #define EROFS_PACKED_NID_UNALLOCATED	-1
 
 struct erofs_mkfs_dfops;
+struct erofs_bloom_filter;
 struct erofs_sb_info {
 	struct erofs_device_info *devs;
 	char *devname;
@@ -134,6 +135,7 @@ struct erofs_sb_info {
 #endif
 	struct erofs_bufmgr *bmgr;
 	bool useqpl;
+	struct erofs_bloom_filter *bf;
 };
 
 #define EROFS_SUPER_END (EROFS_SUPER_OFFSET + sizeof(struct erofs_super_block))
diff --git a/lib/Makefile.am b/lib/Makefile.am
index 6b52470..78140e7 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -35,7 +35,7 @@ liberofs_la_SOURCES = config.c io.c cache.c super.c inode.c xattr.c exclude.c \
 		      namei.c data.c compress.c compressor.c zmap.c decompress.c \
 		      compress_hints.c hashmap.c sha256.c blobchunk.c dir.c \
 		      fragments.c dedupe.c uuid_unparse.c uuid.c tar.c \
-		      block_list.c xxhash.c rebuild.c diskbuf.c
+		      block_list.c xxhash.c rebuild.c diskbuf.c bloom_filter.c
 
 liberofs_la_CFLAGS = -Wall ${libuuid_CFLAGS} -I$(top_srcdir)/include
 if ENABLE_LZ4
diff --git a/lib/bloom_filter.c b/lib/bloom_filter.c
new file mode 100644
index 0000000..f35735b
--- /dev/null
+++ b/lib/bloom_filter.c
@@ -0,0 +1,93 @@
+// SPDX-License-Identifier: GPL-2.0+ OR Apache-2.0
+#include "erofs/bloom_filter.h"
+#include "xxhash.h"
+#include <stdlib.h>
+
+static u32 erofs_bloom_hash(struct erofs_bloom_filter *bf, void *data,
+                            size_t length, u32 index)
+{
+        u32 h;
+
+        h = xxh32(data, length, bf->hash_seed + index);
+        return h & bf->bitmap_mask;
+}
+
+/*
+ * The optimal bit array size that minimizes the false positive is
+ * m * k / ln(2) where m is the # of elements inserted into the bloom
+ * filter and k is the # of hash functions. Here, 1.44 is used to
+ * approximate 1 / ln(2).
+ */
+int erofs_bloom_init(struct erofs_sb_info *sbi, u32 nr_funcs,
+                     unsigned long entries, u32 seed)
+{
+        struct erofs_bloom_filter *bf;
+
+        bf = calloc(1, sizeof(struct erofs_bloom_filter));
+        if (!bf)
+                return -EINVAL;
+
+        bf->nr_funcs = nr_funcs;
+        bf->hash_seed = seed;
+        bf->size = roundup_pow_of_two(((long)(entries * nr_funcs * 1.44)));
+        bf->bitmap_mask = bf->size - 1;
+        bf->map = calloc(BITS_TO_LONGS(bf->size), sizeof(long));
+        if (!bf->map) {
+                free(bf);
+                return -ENOMEM;
+        }
+        sbi->bf = bf;
+
+        return 0;
+}
+
+long erofs_bloom_add(struct erofs_sb_info *sbi, void *data, size_t length)
+{
+        struct erofs_bloom_filter *bf;
+        u32 i, h;
+
+        bf = sbi->bf;
+        if (!bf)
+                return -EINVAL;
+
+        for (i = 0; i < bf->nr_funcs; i ++) {
+                h = erofs_bloom_hash(bf, data, length, i);
+                __set_bit(h, bf->map);
+        }
+
+        return 0;
+}
+
+/*
+ * Return negative error code on failure, 0 if the key is not in the bloom filter
+ * and 1 if the key might be in the bloom filter.
+ */
+long erofs_bloom_test(struct erofs_sb_info *sbi, void *data, size_t length)
+{
+        u32 i, h;
+        struct erofs_bloom_filter *bf;
+
+        bf = sbi->bf;
+        if (!bf)
+                return -EINVAL;
+
+        for (i = 0; i < bf->nr_funcs; i ++) {
+                h = erofs_bloom_hash(bf, data, length, i);
+                if (!__test_bit(h, bf->map))
+                        return 0;
+        }
+
+        return 1;
+}
+
+void erofs_bloom_exit(struct erofs_sb_info *sbi)
+{
+        if (sbi->bf) {
+                if (sbi->bf->map) {
+                        free(sbi->bf->map);
+                        sbi->bf->map = NULL;
+                }
+                free(sbi->bf);
+                sbi->bf = NULL;
+        }
+}
-- 
2.43.5