[PATCH v4 04/14] digest_cache: Add hash tables and operations
Roberto Sassu
roberto.sassu at huaweicloud.com
Tue Apr 16 10:28:39 UTC 2024
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 at huawei.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 at huawei.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 at huawei.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
More information about the Linux-security-module-archive
mailing list