diff mbox series

[RFC,v2,03/13] integrity/digest_cache: Add functions to populate and search

Message ID 20230812104616.2190095-4-roberto.sassu@huaweicloud.com (mailing list archive)
State Handled Elsewhere
Headers show
Series integrity: Introduce a digest cache | expand

Commit Message

Roberto Sassu Aug. 12, 2023, 10:46 a.m. UTC 
From: Roberto Sassu <roberto.sassu@huawei.com>

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@huawei.com>
---
 security/integrity/digest_cache.c | 131 ++++++++++++++++++++++++++++++
 security/integrity/digest_cache.h |  24 ++++++
 2 files changed, 155 insertions(+)

Comments

Jarkko Sakkinen Aug. 14, 2023, 5:13 p.m. UTC | #1 
On Sat Aug 12, 2023 at 1:46 PM EEST, Roberto Sassu wrote:
> From: Roberto Sassu <roberto.sassu@huawei.com>
>
> 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@huawei.com>
> ---
>  security/integrity/digest_cache.c | 131 ++++++++++++++++++++++++++++++
>  security/integrity/digest_cache.h |  24 ++++++
>  2 files changed, 155 insertions(+)
>
> diff --git a/security/integrity/digest_cache.c b/security/integrity/digest_cache.c
> index 4201c68171a..d14d84b804b 100644
> --- a/security/integrity/digest_cache.c
> +++ b/security/integrity/digest_cache.c
> @@ -315,3 +315,134 @@ struct digest_cache *digest_cache_get(struct dentry *dentry,
>  
>  	return iint->dig_user;
>  }
> +
> +/**
> + * 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.

Nit: previous had a different phrasing "a negative value otherwise".

I would suggest "a POSIX error code otherwise" for both.

> + */
> +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
> + * @pathname: Path of the file whose digest is looked up
> + *
> + * 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;
> +
> +	if (digest_cache->algo == HASH_ALGO__LAST) {
> +		pr_debug("Algorithm not set for digest list %s\n",
> +			 digest_cache->path_str);
> +		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 ff88e8593c6..01cd70f9850 100644
> --- a/security/integrity/digest_cache.h
> +++ b/security/integrity/digest_cache.h
> @@ -66,6 +66,11 @@ static inline unsigned int digest_cache_hash_key(u8 *digest,
>  void digest_cache_free(struct digest_cache *digest_cache);
>  struct digest_cache *digest_cache_get(struct dentry *dentry,
>  				      struct integrity_iint_cache *iint);
> +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)
>  {
> @@ -77,5 +82,24 @@ digest_cache_get(struct dentry *dentry, struct integrity_iint_cache *iint)
>  	return NULL;
>  }
>  
> +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

Why all this complexity instead of using xarray?

https://docs.kernel.org/core-api/xarray.html

BR, Jarkko
Roberto Sassu Aug. 16, 2023, 8:35 a.m. UTC | #2 
On 8/14/2023 7:13 PM, Jarkko Sakkinen wrote:
> On Sat Aug 12, 2023 at 1:46 PM EEST, Roberto Sassu wrote:
>> From: Roberto Sassu <roberto.sassu@huawei.com>
>>
>> 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@huawei.com>
>> ---
>>   security/integrity/digest_cache.c | 131 ++++++++++++++++++++++++++++++
>>   security/integrity/digest_cache.h |  24 ++++++
>>   2 files changed, 155 insertions(+)
>>
>> diff --git a/security/integrity/digest_cache.c b/security/integrity/digest_cache.c
>> index 4201c68171a..d14d84b804b 100644
>> --- a/security/integrity/digest_cache.c
>> +++ b/security/integrity/digest_cache.c
>> @@ -315,3 +315,134 @@ struct digest_cache *digest_cache_get(struct dentry *dentry,
>>   
>>   	return iint->dig_user;
>>   }
>> +
>> +/**
>> + * 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.
> 
> Nit: previous had a different phrasing "a negative value otherwise".
> 
> I would suggest "a POSIX error code otherwise" for both.

Ok.

>> + */
>> +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
>> + * @pathname: Path of the file whose digest is looked up
>> + *
>> + * 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;
>> +
>> +	if (digest_cache->algo == HASH_ALGO__LAST) {
>> +		pr_debug("Algorithm not set for digest list %s\n",
>> +			 digest_cache->path_str);
>> +		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 ff88e8593c6..01cd70f9850 100644
>> --- a/security/integrity/digest_cache.h
>> +++ b/security/integrity/digest_cache.h
>> @@ -66,6 +66,11 @@ static inline unsigned int digest_cache_hash_key(u8 *digest,
>>   void digest_cache_free(struct digest_cache *digest_cache);
>>   struct digest_cache *digest_cache_get(struct dentry *dentry,
>>   				      struct integrity_iint_cache *iint);
>> +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)
>>   {
>> @@ -77,5 +82,24 @@ digest_cache_get(struct dentry *dentry, struct integrity_iint_cache *iint)
>>   	return NULL;
>>   }
>>   
>> +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
> 
> Why all this complexity instead of using xarray?
> 
> https://docs.kernel.org/core-api/xarray.html

Uhm, did I get correctly from the documentation that it isn't the 
optimal solution for hash tables?

Thanks

Roberto
Jarkko Sakkinen Aug. 16, 2023, 9 p.m. UTC | #3 
On Wed Aug 16, 2023 at 11:35 AM EEST, Roberto Sassu wrote:
> On 8/14/2023 7:13 PM, Jarkko Sakkinen wrote:
> > On Sat Aug 12, 2023 at 1:46 PM EEST, Roberto Sassu wrote:
> >> From: Roberto Sassu <roberto.sassu@huawei.com>
> >>
> >> 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@huawei.com>
> >> ---
> >>   security/integrity/digest_cache.c | 131 ++++++++++++++++++++++++++++++
> >>   security/integrity/digest_cache.h |  24 ++++++
> >>   2 files changed, 155 insertions(+)
> >>
> >> diff --git a/security/integrity/digest_cache.c b/security/integrity/digest_cache.c
> >> index 4201c68171a..d14d84b804b 100644
> >> --- a/security/integrity/digest_cache.c
> >> +++ b/security/integrity/digest_cache.c
> >> @@ -315,3 +315,134 @@ struct digest_cache *digest_cache_get(struct dentry *dentry,
> >>   
> >>   	return iint->dig_user;
> >>   }
> >> +
> >> +/**
> >> + * 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.
> > 
> > Nit: previous had a different phrasing "a negative value otherwise".
> > 
> > I would suggest "a POSIX error code otherwise" for both.
>
> Ok.
>
> >> + */
> >> +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
> >> + * @pathname: Path of the file whose digest is looked up
> >> + *
> >> + * 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;
> >> +
> >> +	if (digest_cache->algo == HASH_ALGO__LAST) {
> >> +		pr_debug("Algorithm not set for digest list %s\n",
> >> +			 digest_cache->path_str);
> >> +		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 ff88e8593c6..01cd70f9850 100644
> >> --- a/security/integrity/digest_cache.h
> >> +++ b/security/integrity/digest_cache.h
> >> @@ -66,6 +66,11 @@ static inline unsigned int digest_cache_hash_key(u8 *digest,
> >>   void digest_cache_free(struct digest_cache *digest_cache);
> >>   struct digest_cache *digest_cache_get(struct dentry *dentry,
> >>   				      struct integrity_iint_cache *iint);
> >> +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)
> >>   {
> >> @@ -77,5 +82,24 @@ digest_cache_get(struct dentry *dentry, struct integrity_iint_cache *iint)
> >>   	return NULL;
> >>   }
> >>   
> >> +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
> > 
> > Why all this complexity instead of using xarray?
> > 
> > https://docs.kernel.org/core-api/xarray.html
>
> Uhm, did I get correctly from the documentation that it isn't the 
> optimal solution for hash tables?

I think you are correct with xarray that it is not a great fit here 
(I overlooked).

BR, Jarkko
diff mbox series

Patch

diff --git a/security/integrity/digest_cache.c b/security/integrity/digest_cache.c
index 4201c68171a..d14d84b804b 100644
--- a/security/integrity/digest_cache.c
+++ b/security/integrity/digest_cache.c
@@ -315,3 +315,134 @@  struct digest_cache *digest_cache_get(struct dentry *dentry,
 
 	return iint->dig_user;
 }
+
+/**
+ * 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
+ * @pathname: Path of the file whose digest is looked up
+ *
+ * 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;
+
+	if (digest_cache->algo == HASH_ALGO__LAST) {
+		pr_debug("Algorithm not set for digest list %s\n",
+			 digest_cache->path_str);
+		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 ff88e8593c6..01cd70f9850 100644
--- a/security/integrity/digest_cache.h
+++ b/security/integrity/digest_cache.h
@@ -66,6 +66,11 @@  static inline unsigned int digest_cache_hash_key(u8 *digest,
 void digest_cache_free(struct digest_cache *digest_cache);
 struct digest_cache *digest_cache_get(struct dentry *dentry,
 				      struct integrity_iint_cache *iint);
+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)
 {
@@ -77,5 +82,24 @@  digest_cache_get(struct dentry *dentry, struct integrity_iint_cache *iint)
 	return NULL;
 }
 
+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 */