ALSA: control: Use xarray for faster lookups

The control elements are managed in a single linked list and we
traverse the whole list for matching each numid or ctl id per every
inquiry of a control element.  This is OK-ish for a small number of
elements but obviously it doesn't scale.  Especially the matching with
the ctl id takes time because it checks each field of the snd_ctl_id
element, e.g. the name string is matched with strcmp().

This patch adds the hash tables with Xarray for improving the lookup
speed of a control element.  There are two xarray tables added to the
card; one for numid and another for ctl id.  For the numid, we use the
numid as the index, while for the ctl id, we calculate a hash key.

The lookup is done via a single xa_load() execution.  As long as the
given control element is found on the Xarray table, that's fine, we
can give back a quick lookup result.  The problem is when no entry
hits on the table, and for this case, we have a slight optimization.
Namely, the driver checks whether we had a collision on Xarray table,
and do a fallback search (linear lookup of the full entries) only if a
hash key collision happened beforehand.
So, in theory, the inquiry for a non-existing element might take still
time even with this patch in a worst case, but this must be pretty
rare.

The feature is enabled via CONFIG_SND_CTL_FAST_LOOKUP, which is turned
on as default.  For simplicity, the option can be turned off only when
CONFIG_EXPERT is set ("You are expert? Then you manage 1000 knobs").

Link: https://lore.kernel.org/r/20211028130027.18764-1-tiwai@suse.de
Link: https://lore.kernel.org/r/20220609180504.775-1-tiwai@suse.de
Link: https://lore.kernel.org/all/cover.1653813866.git.quic_rbankapu@quicinc.com/
Link: https://lore.kernel.org/r/20220610064537.18660-1-tiwai@suse.de
Signed-off-by: Takashi Iwai <tiwai@suse.de>

1 files changed, 6 insertions, 0 deletions

diff --git a/include/sound/core.h b/include/sound/core.h
index 6d4cc49584c6..dd28de2343b8 100644
--- a/include/sound/core.h
+++ b/include/sound/core.h
@@ -14,6 +14,7 @@
 #include <linux/pm.h>			/* pm_message_t */
 #include <linux/stringify.h>
 #include <linux/printk.h>
+#include <linux/xarray.h>
 
 /* number of supported soundcards */
 #ifdef CONFIG_SND_DYNAMIC_MINORS
@@ -103,6 +104,11 @@ struct snd_card {
 	size_t user_ctl_alloc_size;	// current memory allocation by user controls.
 	struct list_head controls;	/* all controls for this card */
 	struct list_head ctl_files;	/* active control files */
+#ifdef CONFIG_SND_CTL_FAST_LOOKUP
+	struct xarray ctl_numids;	/* hash table for numids */
+	struct xarray ctl_hash;		/* hash table for ctl id matching */
+	bool ctl_hash_collision;	/* ctl_hash collision seen? */
+#endif
 
 	struct snd_info_entry *proc_root;	/* root for soundcard specific files */
 	struct proc_dir_entry *proc_root_link;	/* number link to real id */