| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <98959e3d-7543-4a8e-9712-05a3ba04d2c8@huaweicloud.com>
Date: Wed, 16 Aug 2023 10:35:56 +0200
From: Roberto Sassu <roberto.sassu@...weicloud.com>
To: Jarkko Sakkinen <jarkko@...nel.org>, corbet@....net,
zohar@...ux.ibm.com, dmitry.kasatkin@...il.com,
paul@...l-moore.com, jmorris@...ei.org, serge@...lyn.com
Cc: linux-kernel@...r.kernel.org, linux-doc@...r.kernel.org,
linux-integrity@...r.kernel.org,
linux-security-module@...r.kernel.org, bpf@...r.kernel.org,
pbrobinson@...il.com, zbyszek@...waw.pl, hch@....de,
mjg59@...f.ucam.org, pmatilai@...hat.com, jannh@...gle.com,
Roberto Sassu <roberto.sassu@...wei.com>
Subject: Re: [RFC][PATCH v2 03/13] integrity/digest_cache: Add functions to
populate and search
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@...wei.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@...wei.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
Powered by blists - more mailing lists