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

[Roberto Sassu <roberto.sassu@xxxxxxxxxxxxxxx>]

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@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 | 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