linux-kernel - [PATCH 1/3] fat: define functions and data structures for a formatted name cache

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20210829142459.56081-2-calebdsb@protonmail.com>
Date:   Sun, 29 Aug 2021 14:25:22 +0000
From:   "Caleb D.S. Brzezinski" <calebdsb@...tonmail.com>
To:     hirofumi@...l.parknet.co.jp
Cc:     linux-kernel@...r.kernel.org, linux-fsdevel@...r.kernel.org,
        "Caleb D.S. Brzezinski" <calebdsb@...tonmail.com>
Subject: [PATCH 1/3] fat: define functions and data structures for a formatted name cache

Define the functions and data structures to use as a name formatting
cache for msdos, using the generic Linux hashtable.

Signed-off-by: Caleb D.S. Brzezinski <calebdsb@...tonmail.com>
---
 fs/fat/namei_msdos.c | 96 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 96 insertions(+)

diff --git a/fs/fat/namei_msdos.c b/fs/fat/namei_msdos.c
index efba301d6..7561674b1 100644
--- a/fs/fat/namei_msdos.c
+++ b/fs/fat/namei_msdos.c
@@ -9,12 +9,108 @@
 
 #include <linux/module.h>
 #include <linux/iversion.h>
+#include <linux/types.h>
+#include <linux/hashtable.h>
+#include <linux/slab.h>
+#include <linux/mutex.h>
 #include "fat.h"
 
 /* Characters that are undesirable in an MS-DOS file name */
 static unsigned char bad_chars[] = "*?<>|\"";
 static unsigned char bad_if_strict[] = "+=,; ";
 
+
+/**
+ * struct msdos_name_node - A formatted filename cache node
+ * @fname: the formatted filename
+ * @gc: a use counter for removing non-frequently used names
+ * @hash: the key for the item in the hash table
+ * @h_list: the list to the next set of values in this node's bucket
+ */
+struct msdos_name_node {
+	u16 gc;
+	char fname[9];
+	u64 hash;
+	struct hlist_node h_list;
+};
+
+DEFINE_HASHTABLE(msdos_ncache, 6);
+DEFINE_MUTEX(msdos_ncache_mutex); /* protect the name cache */
+
+/**
+ * msdos_fname_hash() - quickly "hash" an msdos filename
+ * @name: the name to hash, assumed to be a maximum of eight characters
+ *
+ * Bitwise-or the characters in an msdos filename into a simple "hash" that can
+ * be used as a fast hash for an msdos filename.
+ */
+static u64 msdos_fname_hash(const unsigned char *name)
+{
+	u64 res = 0;
+	short i;
+
+	for (i = 0; i < 8 && name[i] != '\0'; i++)
+		res |= (u64)(name[i] << (8 * i));
+
+	return res;
+}
+
+/**
+ * find_fname_in_cache() - retrieve a filename from the cache given a hash
+ * @out: the result buffer for the filename
+ * @ihash: the hash to check for
+ */
+static bool find_fname_in_cache(char *out, u64 ihash)
+{
+	struct msdos_name_node *node;
+	bool found = false;
+
+	mutex_lock(&msdos_ncache_mutex);
+	hash_for_each_possible(msdos_ncache, node, h_list, ihash) {
+		if (node->hash == ihash) {
+			strscpy(out, node->fname, 9);
+			found = true;
+			node->gc++;
+			goto out;
+		}
+	}
+
+out:
+	mutex_unlock(&msdos_ncache_mutex);
+	return found;
+}
+
+/**
+ * drop_fname_from_cache() - delete and free a filename from the hash entry
+ * @ihash: the hash to remove from the cache
+ */
+static void drop_fname_from_cache(u64 ihash)
+{
+	struct msdos_name_node *node, *gc;
+
+	gc = NULL;
+
+	mutex_lock(&msdos_ncache_mutex);
+	hash_for_each_possible(msdos_ncache, node, h_list, ihash) {
+		if (unlikely(gc)) {
+			hash_del(&gc->h_list);
+			kfree(gc);
+			gc = NULL;
+		}
+		if (node->hash == ihash) {
+			hash_del(&node->h_list);
+			kfree(node);
+			goto out;
+		}
+		/* if we don't find it, collect unused nodes until we do */
+		if (node->gc < 4)
+			gc = node;
+	}
+
+out:
+	mutex_unlock(&msdos_ncache_mutex);
+}
+
 /***** Formats an MS-DOS file name. Rejects invalid names. */
 static int msdos_format_name(const unsigned char *name, int len,
 			     unsigned char *res, struct fat_mount_options *opts)

base-commit: 85a90500f9a1717c4e142ce92e6c1cb1a339ec78
-- 
2.32.0