[RFC][PATCH 03/12] integrity/digest_cache: Add functions to populate and search

[Roberto Sassu]

From: Roberto Sassu <roberto.sassu@xxxxxxxxxx>

Add digest_cache_init_htable(), to size a hash table depending on the
number of digests to be added to the cache.

Add digest_cache_add() and digest_cache_lookup() to respectively add and
lookup a digest in the digest cache.

Signed-off-by: Roberto Sassu <roberto.sassu@xxxxxxxxxx>
---
 security/integrity/digest_cache.c | 124 ++++++++++++++++++++++++++++++
 security/integrity/digest_cache.h |  24 ++++++
 2 files changed, 148 insertions(+)

diff --git a/security/integrity/digest_cache.c b/security/integrity/digest_cache.c
index 66c2c4088e9..7537c7232db 100644
--- a/security/integrity/digest_cache.c
+++ b/security/integrity/digest_cache.c
@@ -298,3 +298,127 @@ void digest_cache_put(struct digest_cache *digest_cache,
 	pr_debug("Put cache, algo: %s, digest list: %s",
 		 hash_algo_name[digest_cache->algo], digest_cache->path_str);
 }
+
+/**
+ * digest_cache_init_htable - Allocate and initialize the hash table
+ * @digest_cache: Digest cache
+ * @num_digests: Number of digests to add to the digest cache
+ *
+ * This function allocates and initializes the hash table. Its size is
+ * determined by the number of digests to add to the digest cache, known
+ * at this point by the parser calling this function.
+ *
+ * Return: Zero on success, a negative value otherwise.
+ */
+int digest_cache_init_htable(struct digest_cache *digest_cache,
+			     u64 num_digests)
+{
+	int i;
+
+	if (!digest_cache)
+		return 0;
+
+	digest_cache->num_slots = num_digests / DIGEST_CACHE_HTABLE_DEPTH;
+	if (!digest_cache->num_slots)
+		digest_cache->num_slots = 1;
+
+	digest_cache->slots = kmalloc_array(num_digests,
+					    sizeof(*digest_cache->slots),
+					    GFP_KERNEL);
+	if (!digest_cache->slots)
+		return -ENOMEM;
+
+	for (i = 0; i < digest_cache->num_slots; i++)
+		INIT_HLIST_HEAD(&digest_cache->slots[i]);
+
+	pr_debug("Initialized %d hash table slots for digest list %s\n",
+		 digest_cache->num_slots, digest_cache->path_str);
+	return 0;
+}
+
+/**
+ * digest_cache_add - Add a new digest to the digest cache
+ * @digest_cache: Digest cache
+ * @digest: Digest to add
+ *
+ * This function, invoked by a digest list parser, adds a digest extracted
+ * from a digest list to the digest cache.
+ *
+ * Return: Zero on success, a negative value on error.
+ */
+int digest_cache_add(struct digest_cache *digest_cache, u8 *digest)
+{
+	struct digest_cache_entry *entry;
+	unsigned int key;
+	int digest_len;
+
+	if (!digest_cache)
+		return 0;
+
+	digest_len = hash_digest_size[digest_cache->algo];
+
+	entry = kmalloc(sizeof(*entry) + digest_len, GFP_KERNEL);
+	if (!entry)
+		return -ENOMEM;
+
+	memcpy(entry->digest, digest, digest_len);
+
+	key = digest_cache_hash_key(digest, digest_cache->num_slots);
+	hlist_add_head(&entry->hnext, &digest_cache->slots[key]);
+	pr_debug("Add digest %s:%*phN from digest list %s\n",
+		 hash_algo_name[digest_cache->algo], digest_len, digest,
+		 digest_cache->path_str);
+	return 0;
+}
+
+/**
+ * digest_cache_lookup - Searches a digest in the digest cache
+ * @digest_cache: Digest cache
+ * @digest: Digest to search
+ * @algo: Algorithm of the digest to search
+ *
+ * This function, invoked by IMA or EVM, searches the calculated digest of
+ * a file or file metadata in the digest cache acquired with
+ * digest_cache_get().
+ *
+ * Return: Zero if the digest is found, a negative value if not.
+ */
+int digest_cache_lookup(struct digest_cache *digest_cache, u8 *digest,
+			enum hash_algo algo, const char *pathname)
+{
+	struct digest_cache_entry *entry;
+	unsigned int key;
+	int digest_len;
+	int search_depth = 0;
+
+	if (!digest_cache)
+		return -ENOENT;
+
+	digest_len = hash_digest_size[digest_cache->algo];
+
+	if (algo != digest_cache->algo) {
+		pr_debug("Algo mismatch for file %s, digest %s:%*phN in digest list %s (*%s)\n",
+			 pathname, hash_algo_name[algo], digest_len, digest,
+			 digest_cache->path_str,
+			 hash_algo_name[digest_cache->algo]);
+		return -ENOENT;
+	}
+
+	key = digest_cache_hash_key(digest, digest_cache->num_slots);
+
+	hlist_for_each_entry_rcu(entry, &digest_cache->slots[key], hnext) {
+		if (!memcmp(entry->digest, digest, digest_len)) {
+			pr_debug("Cache hit at depth %d for file %s, digest %s:%*phN in digest list %s\n",
+				 search_depth, pathname, hash_algo_name[algo], digest_len,
+				 digest, digest_cache->path_str);
+			return 0;
+		}
+
+		search_depth++;
+	}
+
+	pr_debug("Cache miss for file %s, digest %s:%*phN in digest list %s\n",
+		 pathname, hash_algo_name[algo], digest_len, digest,
+		 digest_cache->path_str);
+	return -ENOENT;
+}
diff --git a/security/integrity/digest_cache.h b/security/integrity/digest_cache.h
index fa4a716df65..5e3997b2723 100644
--- a/security/integrity/digest_cache.h
+++ b/security/integrity/digest_cache.h
@@ -64,6 +64,11 @@ struct digest_cache *digest_cache_get(struct dentry *dentry,
 				      struct path *digest_list_path);
 void digest_cache_put(struct digest_cache *digest_cache,
 		      struct path *digest_list_path);
+int digest_cache_init_htable(struct digest_cache *digest_cache,
+			     u64 num_digests);
+int digest_cache_add(struct digest_cache *digest_cache, u8 *digest);
+int digest_cache_lookup(struct digest_cache *digest_cache, u8 *digest,
+			enum hash_algo algo, const char *pathname);
 #else
 static inline void digest_cache_free(struct digest_cache *digest_cache)
 {
@@ -80,5 +85,24 @@ static inline void digest_cache_put(struct digest_cache *digest_cache,
 {
 }
 
+static inline int digest_cache_init_htable(struct digest_cache *digest_cache,
+					   u64 num_digests)
+{
+	return -EOPNOTSUPP;
+}
+
+static inline int digest_cache_add(struct digest_cache *digest_cache,
+				   u8 *digest)
+{
+	return -EOPNOTSUPP;
+}
+
+static inline int digest_cache_lookup(struct digest_cache *digest_cache,
+				      u8 *digest, enum hash_algo algo,
+				      const char *pathname)
+{
+	return -ENOENT;
+}
+
 #endif /* CONFIG_INTEGRITY_DIGEST_CACHE */
 #endif /* _DIGEST_CACHE_H */
-- 
2.34.1