Date: Tue, 16 Apr 2024 12:28:39 +0200
From: Roberto Sassu <roberto.sassu@...weicloud.com>
To: Jarkko Sakkinen <jarkko@...nel.org>, corbet@....net, paul@...l-moore.com,
 jmorris@...ei.org, serge@...lyn.com, akpm@...ux-foundation.org,
 shuah@...nel.org, mcoquelin.stm32@...il.com, alexandre.torgue@...s.st.com,
 mic@...ikod.net
Cc: linux-security-module@...r.kernel.org, linux-doc@...r.kernel.org,
 linux-kernel@...r.kernel.org, linux-kselftest@...r.kernel.org,
 bpf@...r.kernel.org, zohar@...ux.ibm.com, dmitry.kasatkin@...il.com,
 linux-integrity@...r.kernel.org, wufan@...ux.microsoft.com,
 pbrobinson@...il.com, zbyszek@...waw.pl, hch@....de, mjg59@...f.ucam.org,
 pmatilai@...hat.com, jannh@...gle.com, dhowells@...hat.com,
 jikos@...nel.org, mkoutny@...e.com, ppavlu@...e.com, petr.vorel@...il.com,
 mzerqung@...inter.de, kgold@...ux.ibm.com,
 Roberto Sassu <roberto.sassu@...wei.com>
Subject: Re: [PATCH v4 04/14] digest_cache: Add hash tables and operations

On 4/15/2024 9:36 PM, Jarkko Sakkinen wrote:
> On Mon Apr 15, 2024 at 5:24 PM EEST, Roberto Sassu wrote:
>> From: Roberto Sassu <roberto.sassu@...wei.com>
>>
>> Add a linked list of hash tables to the digest cache, one per algorithm,
>> containing the digests extracted from digest lists.
>>
>> The number of hash table slots is determined by dividing the number of
>> digests to add to the average depth of the collision list defined with
>> CONFIG_DIGEST_CACHE_HTABLE_DEPTH (currently set to 30). It can be changed
>> in the kernel configuration.
>>
>> Add digest_cache_htable_init() and digest_cache_htable_add(), to be called
>> by digest list parsers, in order to allocate the hash tables and to add
>> extracted digests.
>>
>> Add digest_cache_htable_free(), to let the digest_cache LSM free the hash
>> tables at the time a digest cache is freed.
>>
>> Add digest_cache_htable_lookup() to search a digest in the hash table of a
>> digest cache for a given algorithm.
>>
>> Add digest_cache_lookup() to the public API, to let users of the
>> digest_cache LSM search a digest in a digest cache and, in a subsequent
>> patch, to search it in the digest caches for each directory entry.
>>
>> Return the digest cache containing the digest, as a different type,
>> digest_cache_found_t to avoid it being accidentally put. Also, introduce
>> digest_cache_from_found_t() to explicitly convert it back to a digest cache
>> for further use (e.g. retrieving verification data, introduced later).
>>
>> Finally, add digest_cache_hash_key() to compute the hash table key from the
>> first two bytes of the digest (modulo the number of slots).
>>
>> Signed-off-by: Roberto Sassu <roberto.sassu@...wei.com>
>> ---
>>   include/linux/digest_cache.h     |  34 +++++
>>   security/digest_cache/Kconfig    |  11 ++
>>   security/digest_cache/Makefile   |   2 +-
>>   security/digest_cache/htable.c   | 250 +++++++++++++++++++++++++++++++
>>   security/digest_cache/internal.h |  43 ++++++
>>   security/digest_cache/main.c     |   3 +
>>   6 files changed, 342 insertions(+), 1 deletion(-)
>>   create mode 100644 security/digest_cache/htable.c
>>
>> diff --git a/include/linux/digest_cache.h b/include/linux/digest_cache.h
>> index e79f94a60b0f..4872700ac205 100644
>> --- a/include/linux/digest_cache.h
>> +++ b/include/linux/digest_cache.h
>> @@ -11,12 +11,39 @@
>>   #define _LINUX_DIGEST_CACHE_H
>>   
>>   #include <linux/fs.h>
>> +#include <crypto/hash_info.h>
>>   
>>   struct digest_cache;
>>   
>> +/**
>> + * typedef digest_cache_found_t - Digest cache reference as numeric value
>> + *
>> + * This new type represents a digest cache reference that should not be put.
>> + */
>> +typedef unsigned long digest_cache_found_t;
>> +
>> +/**
>> + * digest_cache_from_found_t - Convert digest_cache_found_t to digest cache ptr
>> + * @found: digest_cache_found_t value
>> + *
>> + * Convert the digest_cache_found_t returned by digest_cache_lookup() to a
>> + * digest cache pointer, so that it can be passed to the other functions of the
>> + * API.
>> + *
>> + * Return: Digest cache pointer.
>> + */
>> +static inline struct digest_cache *
>> +digest_cache_from_found_t(digest_cache_found_t found)
>> +{
>> +	return (struct digest_cache *)found;
>> +}
>> +
>>   #ifdef CONFIG_SECURITY_DIGEST_CACHE
>>   struct digest_cache *digest_cache_get(struct dentry *dentry);
>>   void digest_cache_put(struct digest_cache *digest_cache);
>> +digest_cache_found_t digest_cache_lookup(struct dentry *dentry,
>> +					 struct digest_cache *digest_cache,
>> +					 u8 *digest, enum hash_algo algo);
>>   
>>   #else
>>   static inline struct digest_cache *digest_cache_get(struct dentry *dentry)
>> @@ -28,5 +55,12 @@ static inline void digest_cache_put(struct digest_cache *digest_cache)
>>   {
>>   }
>>   
>> +static inline digest_cache_found_t
>> +digest_cache_lookup(struct dentry *dentry, struct digest_cache *digest_cache,
>> +		    u8 *digest, enum hash_algo algo)
>> +{
>> +	return 0UL;
>> +}
>> +
>>   #endif /* CONFIG_SECURITY_DIGEST_CACHE */
>>   #endif /* _LINUX_DIGEST_CACHE_H */
>> diff --git a/security/digest_cache/Kconfig b/security/digest_cache/Kconfig
>> index dfabe5d6e3ca..71017954e5c5 100644
>> --- a/security/digest_cache/Kconfig
>> +++ b/security/digest_cache/Kconfig
>> @@ -18,3 +18,14 @@ config DIGEST_LIST_DEFAULT_PATH
>>   	  It can be changed at run-time, by writing the new path to the
>>   	  securityfs interface. Digest caches created with the old path are
>>   	  not affected by the change.
>> +
>> +config DIGEST_CACHE_HTABLE_DEPTH
>> +	int
>> +	default 30
>> +	help
>> +	  Desired average depth of the collision list in the digest cache
>> +	  hash tables.
>> +
>> +	  A smaller number will increase the amount of hash table slots, and
>> +	  make the search faster. A bigger number will decrease the number of
>> +	  hash table slots, but make the search slower.
>> diff --git a/security/digest_cache/Makefile b/security/digest_cache/Makefile
>> index 1330655e33b1..7e00c53d8f55 100644
>> --- a/security/digest_cache/Makefile
>> +++ b/security/digest_cache/Makefile
>> @@ -4,4 +4,4 @@
>>   
>>   obj-$(CONFIG_SECURITY_DIGEST_CACHE) += digest_cache.o
>>   
>> -digest_cache-y := main.o secfs.o
>> +digest_cache-y := main.o secfs.o htable.o
>> diff --git a/security/digest_cache/htable.c b/security/digest_cache/htable.c
>> new file mode 100644
>> index 000000000000..d2d5d8f5e5b1
>> --- /dev/null
>> +++ b/security/digest_cache/htable.c
>> @@ -0,0 +1,250 @@
>> +// SPDX-License-Identifier: GPL-2.0
>> +/*
>> + * Copyright (C) 2023-2024 Huawei Technologies Duesseldorf GmbH
>> + *
>> + * Author: Roberto Sassu <roberto.sassu@...wei.com>
>> + *
>> + * Implement hash table operations for the digest cache.
>> + */
>> +
>> +#define pr_fmt(fmt) "DIGEST CACHE: "fmt
> 
> For easier grepping from kernel tree i'd suggest to name this accordingly i.e.
> just "digest_cache".

Ok, no problem.

>> +#include "internal.h"
>> +
>> +/**
>> + * digest_cache_hash_key - Compute hash key
>> + * @digest: Digest cache
>> + * @num_slots: Number of slots in the hash table
>> + *
>> + * This function computes a hash key based on the first two bytes of the
>> + * digest and the number of slots of the hash table.
>> + *
>> + * Return: Hash key.
>> + */
>> +static inline unsigned int digest_cache_hash_key(u8 *digest,
>> +						 unsigned int num_slots)
>> +{
>> +	/* Same as ima_hash_key() but parametrized. */
>> +	return (digest[0] | digest[1] << 8) % num_slots;
>> +}
>> +
>> +/**
>> + * lookup_htable - Lookup a hash table
>> + * @digest_cache: Digest cache
>> + * @algo: Algorithm of the desired hash table
>> + *
>> + * This function searches the hash table for a given algorithm in the digest
>> + * cache.
>> + *
>> + * Return: A hash table if found, NULL otherwise.
>> + */
>> +static struct htable *lookup_htable(struct digest_cache *digest_cache,
>> +				    enum hash_algo algo)
>> +{
>> +	struct htable *h;
>> +
>> +	list_for_each_entry(h, &digest_cache->htables, next)
>> +		if (h->algo == algo)
>> +			return h;
>> +
>> +	return NULL;
>> +}
>> +
>> +/**
>> + * digest_cache_htable_init - Allocate and initialize the hash table
>> + * @digest_cache: Digest cache
>> + * @num_digests: Number of digests to add to the digest cache
>> + * @algo: Algorithm of the digests
>> + *
>> + * This function allocates and initializes the hash table for a given algorithm.
>> + * The number of slots depends on the number of digests to add to the digest
>> + * cache, and the constant CONFIG_DIGEST_CACHE_HTABLE_DEPTH stating the desired
>> + * average depth of the collision list.
>> + *
>> + * Return: Zero on success, a POSIX error code otherwise.
>> + */
>> +int digest_cache_htable_init(struct digest_cache *digest_cache, u64 num_digests,
>> +			     enum hash_algo algo)
>> +{
>> +	struct htable *h;
>> +	int i;
>> +
>> +	h = lookup_htable(digest_cache, algo);
>> +	if (h)
>> +		return 0;
>> +
>> +	h = kmalloc(sizeof(*h), GFP_KERNEL);
>> +	if (!h)
>> +		return -ENOMEM;
>> +
>> +	h->num_slots = DIV_ROUND_UP(num_digests,
>> +				    CONFIG_DIGEST_CACHE_HTABLE_DEPTH);
>> +	h->slots = kmalloc_array(h->num_slots, sizeof(*h->slots), GFP_KERNEL);
>> +	if (!h->slots) {
>> +		kfree(h);
>> +		return -ENOMEM;
>> +	}
>> +
>> +	for (i = 0; i < h->num_slots; i++)
>> +		INIT_HLIST_HEAD(&h->slots[i]);
>> +
>> +	h->num_digests = 0;
>> +	h->algo = algo;
>> +
>> +	list_add_tail(&h->next, &digest_cache->htables);
>> +
>> +	pr_debug("Initialized hash table for digest list %s, digests: %llu, slots: %u, algo: %s\n",
>> +		 digest_cache->path_str, num_digests, h->num_slots,
>> +		 hash_algo_name[algo]);
>> +	return 0;
>> +}
>> +
>> +/**
>> + * digest_cache_htable_add - Add a new digest to the digest cache
>> + * @digest_cache: Digest cache
>> + * @digest: Digest to add
>> + * @algo: Algorithm of digest
>> + *
>> + * 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 POSIX error code otherwise.
>> + */
>> +int digest_cache_htable_add(struct digest_cache *digest_cache, u8 *digest,
>> +			    enum hash_algo algo)
>> +{
>> +	struct htable *h;
>> +	struct digest_cache_entry *entry;
>> +	unsigned int key;
>> +	int digest_len;
>> +
>> +	h = lookup_htable(digest_cache, algo);
>> +	if (!h) {
>> +		pr_debug("No hash table for algorithm %s was found in digest cache %s, initialize one\n",
>> +			 hash_algo_name[algo], digest_cache->path_str);
>> +		return -ENOENT;
>> +	}
>> +
>> +	digest_len = hash_digest_size[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, h->num_slots);
>> +	hlist_add_head(&entry->hnext, &h->slots[key]);
>> +	h->num_digests++;
>> +	pr_debug("Added digest %s:%*phN to digest cache %s, num of %s digests: %llu\n",
>> +		 hash_algo_name[algo], digest_len, digest,
>> +		 digest_cache->path_str, hash_algo_name[algo], h->num_digests);
>> +	return 0;
>> +}
>> +
>> +/**
>> + * digest_cache_htable_lookup - Search a digest in the digest cache
>> + * @dentry: Dentry of the file whose digest is looked up
>> + * @digest_cache: Digest cache
>> + * @digest: Digest to search
>> + * @algo: Algorithm of the digest to search
>> + *
>> + * This function searches the passed digest and algorithm in the passed digest
>> + * cache.
>> + *
>> + * Return: Zero if the digest is found, -ENOENT if not.
>> + */
>> +int digest_cache_htable_lookup(struct dentry *dentry,
>> +			       struct digest_cache *digest_cache, u8 *digest,
>> +			       enum hash_algo algo)
>> +{
>> +	struct digest_cache_entry *entry;
>> +	struct htable *h;
>> +	unsigned int key;
>> +	int digest_len;
>> +	int search_depth = 0;
>> +
>> +	h = lookup_htable(digest_cache, algo);
>> +	if (!h)
>> +		return -ENOENT;
>> +
>> +	digest_len = hash_digest_size[algo];
>> +	key = digest_cache_hash_key(digest, h->num_slots);
>> +
>> +	hlist_for_each_entry(entry, &h->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 cache %s\n",
>> +				 search_depth, dentry->d_name.name,
>> +				 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 cache %s\n",
>> +		 dentry->d_name.name, hash_algo_name[algo], digest_len, digest,
>> +		 digest_cache->path_str);
>> +	return -ENOENT;
>> +}
>> +
>> +/**
>> + * digest_cache_lookup - Search a digest in the digest cache
>> + * @dentry: Dentry of the file whose digest is looked up
>> + * @digest_cache: Digest cache
>> + * @digest: Digest to search
>> + * @algo: Algorithm of the digest to search
>> + *
>> + * This function calls digest_cache_htable_lookup() to search a digest in the
>> + * passed digest cache, obtained with digest_cache_get().
>> + *
>> + * It returns the digest cache reference as the digest_cache_found_t type, to
>> + * avoid that the digest cache is accidentally put. The digest_cache_found_t
>> + * type can be converted back to a digest cache pointer, by
>> + * calling digest_cache_from_found_t().
>> + *
>> + * Return: A positive digest_cache_found_t if the digest is found, zero if not.
>> + */
>> +digest_cache_found_t digest_cache_lookup(struct dentry *dentry,
>> +					 struct digest_cache *digest_cache,
>> +					 u8 *digest, enum hash_algo algo)
>> +{
>> +	int ret;
>> +
>> +	ret = digest_cache_htable_lookup(dentry, digest_cache, digest, algo);
>> +	return (!ret) ? (digest_cache_found_t)digest_cache : 0UL;
>> +}
>> +EXPORT_SYMBOL_GPL(digest_cache_lookup);
>> +
>> +/**
>> + * digest_cache_htable_free - Free the hash tables
>> + * @digest_cache: Digest cache
>> + *
>> + * This function removes all digests from all hash tables in the digest cache,
>> + * and frees the memory.
>> + */
>> +void digest_cache_htable_free(struct digest_cache *digest_cache)
>> +{
>> +	struct htable *h, *h_tmp;
>> +	struct digest_cache_entry *p;
>> +	struct hlist_node *q;
>> +	int i;
>> +
>> +	list_for_each_entry_safe(h, h_tmp, &digest_cache->htables, next) {
>> +		for (i = 0; i < h->num_slots; i++) {
>> +			hlist_for_each_entry_safe(p, q, &h->slots[i], hnext) {
>> +				hlist_del(&p->hnext);
>> +				pr_debug("Removed digest %s:%*phN from digest cache %s\n",
>> +					 hash_algo_name[h->algo],
>> +					 hash_digest_size[h->algo], p->digest,
>> +					 digest_cache->path_str);
>> +				kfree(p);
>> +			}
>> +		}
>> +
>> +		list_del(&h->next);
>> +		kfree(h->slots);
>> +		kfree(h);
>> +	}
>> +}
>> diff --git a/security/digest_cache/internal.h b/security/digest_cache/internal.h
>> index bbf5eefe5c82..f6ffeaa25288 100644
>> --- a/security/digest_cache/internal.h
>> +++ b/security/digest_cache/internal.h
>> @@ -16,8 +16,40 @@
>>   /* Digest cache bits in flags. */
>>   #define INIT_IN_PROGRESS	0	/* Digest cache being initialized. */
>>   
>> +/**
>> + * struct digest_cache_entry - Entry of a digest cache hash table
>> + * @hnext: Pointer to the next element in the collision list
>> + * @digest: Stored digest
>> + *
>> + * This structure represents an entry of a digest cache hash table, storing a
>> + * digest.
>> + */
>> +struct digest_cache_entry {
>> +	struct hlist_node hnext;
>> +	u8 digest[];
>> +} __packed;
> 
> Please correct me if I'm wrong but I don't think __packed has any use
> here as the definition of hlist_node is:
> 
> 
> struct hlist_node {
> 	struct hlist_node *next, **pprev;
> };
> 
> It is naturally aligned to begin with.

You're right. __packed is not needed (no reordering).

Thanks

Roberto

>> +
>> +/**
>> + * struct htable - Hash table
>> + * @next: Next hash table in the linked list
>> + * @slots: Hash table slots
>> + * @num_slots: Number of slots
>> + * @num_digests: Number of digests stored in the hash table
>> + * @algo: Algorithm of the digests
>> + *
>> + * This structure is a hash table storing digests of file data or metadata.
>> + */
>> +struct htable {
>> +	struct list_head next;
>> +	struct hlist_head *slots;
>> +	unsigned int num_slots;
>> +	u64 num_digests;
>> +	enum hash_algo algo;
>> +};
>> +
>>   /**
>>    * struct digest_cache - Digest cache
>> + * @htables: Hash tables (one per algorithm)
>>    * @ref_count: Number of references to the digest cache
>>    * @path_str: Path of the digest list the digest cache was created from
>>    * @flags: Control flags
>> @@ -25,6 +57,7 @@
>>    * This structure represents a cache of digests extracted from a digest list.
>>    */
>>   struct digest_cache {
>> +	struct list_head htables;
>>   	atomic_t ref_count;
>>   	char *path_str;
>>   	unsigned long flags;
>> @@ -84,4 +117,14 @@ struct digest_cache *digest_cache_create(struct dentry *dentry,
>>   					 struct path *digest_list_path,
>>   					 char *path_str, char *filename);
>>   
>> +/* htable.c */
>> +int digest_cache_htable_init(struct digest_cache *digest_cache, u64 num_digests,
>> +			     enum hash_algo algo);
>> +int digest_cache_htable_add(struct digest_cache *digest_cache, u8 *digest,
>> +			    enum hash_algo algo);
>> +int digest_cache_htable_lookup(struct dentry *dentry,
>> +			       struct digest_cache *digest_cache, u8 *digest,
>> +			       enum hash_algo algo);
>> +void digest_cache_htable_free(struct digest_cache *digest_cache);
>> +
>>   #endif /* _DIGEST_CACHE_INTERNAL_H */
>> diff --git a/security/digest_cache/main.c b/security/digest_cache/main.c
>> index 661c8d106791..0b201af6432c 100644
>> --- a/security/digest_cache/main.c
>> +++ b/security/digest_cache/main.c
>> @@ -48,6 +48,7 @@ static struct digest_cache *digest_cache_alloc_init(char *path_str,
>>   
>>   	atomic_set(&digest_cache->ref_count, 1);
>>   	digest_cache->flags = 0UL;
>> +	INIT_LIST_HEAD(&digest_cache->htables);
>>   
>>   	pr_debug("New digest cache %s (ref count: %d)\n",
>>   		 digest_cache->path_str, atomic_read(&digest_cache->ref_count));
>> @@ -63,6 +64,8 @@ static struct digest_cache *digest_cache_alloc_init(char *path_str,
>>    */
>>   static void digest_cache_free(struct digest_cache *digest_cache)
>>   {
>> +	digest_cache_htable_free(digest_cache);
>> +
>>   	pr_debug("Freed digest cache %s\n", digest_cache->path_str);
>>   	kfree(digest_cache->path_str);
>>   	kmem_cache_free(digest_cache_cache, digest_cache);
> 
> 
> BR, Jarkko

Powered by blists - more mailing lists