On Sun, 29 May 2022 10:50:09 +0200, Raghu Bankapur wrote:

use hashtabe instead of linear list to check kcontrol before adding them for improving early audio KPI.

Change-Id: I7134816736e08e338c0f22a8ae283a0520aa847a Signed-off-by: Raghu Bankapur quic_rbankapu@quicinc.com

Aha, interesting, a faster lookup is indeed measurable and needed.

One point with your patch is whether it works when a control element gets removed dynamically. It's often the case with the user-space kctls. Also, multiple ctl elements may have the same name string but with different index or device number. Comparing only the string isn't enough. (And I wonder how about the hash key collision.)

FWIW, I posted an RFC patch faster lookup with Xarray some time ago: https://lore.kernel.org/all/20211028130027.18764-1-tiwai@suse.de/T/

thanks,

Takashi

---

include/sound/control.h | 4 ++ include/sound/core.h | 12 +++++- sound/core/control.c | 92 +++++++++++++++++++++++++++++++++-------- sound/core/init.c | 3 ++ sound/soc/Kconfig | 9 ++++ 5 files changed, 101 insertions(+), 19 deletions(-)

diff --git a/include/sound/control.h b/include/sound/control.h index 985c51a8fb74..1b85d36c2066 100644 --- a/include/sound/control.h +++ b/include/sound/control.h @@ -70,6 +70,10 @@ struct snd_kcontrol_volatile { struct snd_kcontrol { struct list_head list; /* list of controls */ struct snd_ctl_elem_id id; +#ifdef CONFIG_SND_CTL_HASHTABLE

• struct hlist_node hnode;
• unsigned int knametoint; /* kctl name to uint, hash key value */

+#endif unsigned int count; /* count of same elements */ snd_kcontrol_info_t *info; snd_kcontrol_get_t *get; diff --git a/include/sound/core.h b/include/sound/core.h index b7e9b58d3c78..dd6714fc43ff 100644 --- a/include/sound/core.h +++ b/include/sound/core.h @@ -14,7 +14,9 @@ #include <linux/pm.h> /* pm_message_t */ #include <linux/stringify.h> #include <linux/printk.h>

+#ifdef CONFIG_SND_CTL_HASHTABLE +#include <linux/hashtable.h> +#endif /* number of supported soundcards */ #ifdef CONFIG_SND_DYNAMIC_MINORS #define SNDRV_CARDS CONFIG_SND_MAX_CARDS @@ -24,6 +26,10 @@

#define CONFIG_SND_MAJOR 116 /* standard configuration */

+#ifdef CONFIG_SND_CTL_HASHTABLE +#define SND_CTL_HASH_TABLE_BITS 14 /* buckets numbers: 1 << 14 */ +#endif

/* forward declarations */ struct pci_dev; struct module; @@ -103,7 +109,9 @@ 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_HASHTABLE

• DECLARE_HASHTABLE(ctl_htable, SND_CTL_HASH_TABLE_BITS);

+#endif struct snd_info_entry *proc_root; /* root for soundcard specific files */ struct proc_dir_entry *proc_root_link; /* number link to real id */

diff --git a/sound/core/control.c b/sound/core/control.c index a25c0d64d104..914d05647497 100644 --- a/sound/core/control.c +++ b/sound/core/control.c @@ -368,6 +368,47 @@ enum snd_ctl_add_mode { CTL_ADD_EXCLUSIVE, CTL_REPLACE, CTL_ADD_ON_REPLACE, };

+#ifdef CONFIG_SND_CTL_HASHTABLE +char snd_ctl_string[50] = { '\0' };

+/* Used to convert the string into int value -- BKDRHash */ +unsigned int snd_ctl_strtoint(const char *s) +{

• unsigned int res = 0;
• while (*s)

• res = (res << 5) - res + (*s++);
  

• return (res & 0x7FFFFFFF);

+}

+/**

• • snd_ctl_hash_check - Check the duplicate enrty on snd hashtable
• • @card: the card instance
• • @nametoint: kctl name to uint
• • Finds the control instance with the given nametoint from the card.
• • Return: The pointer of the instance if found, or %NULL if not.
• */

+static struct snd_kcontrol *snd_ctl_hash_check(struct snd_card *card,

• 		 unsigned int nametoint)
  

+{

• struct snd_kcontrol *kctl = NULL;
• if (snd_BUG_ON(!card))

• return NULL;
  

• hash_for_each_possible(card->ctl_htable, kctl, hnode, nametoint) {

• if (kctl->knametoint != nametoint)
  

• 	continue;
  

• return kctl;
  

• }
• return NULL;

+} +#endif

/* add/replace a new kcontrol object; call with card->controls_rwsem locked */ static int __snd_ctl_add_replace(struct snd_card *card, struct snd_kcontrol *kcontrol, @@ -382,24 +423,38 @@ static int __snd_ctl_add_replace(struct snd_card *card, if (id.index > UINT_MAX - kcontrol->count) return -EINVAL;

• old = snd_ctl_find_id(card, &id);
• if (!old) {

• if (mode == CTL_REPLACE)
  

• 	return -EINVAL;
  

• } else {

• if (mode == CTL_ADD_EXCLUSIVE) {
  

• 	dev_err(card->dev,
  

• 		"control %i:%i:%i:%s:%i is already present\n",
  

• 		id.iface, id.device, id.subdevice, id.name,
  

• 		id.index);
  

• 	return -EBUSY;
  

• }
  

+#ifdef CONFIG_SND_CTL_HASHTABLE

• snprintf(snd_ctl_string, strlen(kcontrol->id.name) + 6, "%s%d%d%d",

• kcontrol->id.name, kcontrol->id.iface, kcontrol->id.device,
  

• kcontrol->id.subdevice);
  
  

• err = snd_ctl_remove(card, old);
  

• if (err < 0)
  

• 	return err;
  

• }

• kcontrol->knametoint = snd_ctl_strtoint(snd_ctl_string);
• if (kcontrol->knametoint < 0)

• return -EINVAL;
  

• old = snd_ctl_hash_check(card, kcontrol->knametoint);
• if (old) {

+#endif

• old = snd_ctl_find_id(card, &id);
  

• if (!old) {
  

• 	if (mode == CTL_REPLACE)
  

• 		return -EINVAL;
  

• } else {
  

• 	if (mode == CTL_ADD_EXCLUSIVE) {
  

• 		dev_err(card->dev,
  

• 			"control %i:%i:%i:%s:%i is already present\n",
  

• 			id.iface, id.device, id.subdevice, id.name,
  

• 			id.index);
  

• 		return -EBUSY;
  

• 	}
  
  

• 	err = snd_ctl_remove(card, old);
  

• 	if (err < 0)
  

• 		return err;
  

• }
  

+#ifdef CONFIG_SND_CTL_HASHTABLE

• }

+#endif if (snd_ctl_find_hole(card, kcontrol->count) < 0) return -ENOMEM;

@@ -410,7 +465,10 @@ static int __snd_ctl_add_replace(struct snd_card *card,

for (idx = 0; idx < kcontrol->count; idx++) snd_ctl_notify_one(card, SNDRV_CTL_EVENT_MASK_ADD, kcontrol, idx);

+#ifdef CONFIG_SND_CTL_HASHTABLE

• hash_add(card->ctl_htable, &kcontrol->hnode, kcontrol->knametoint);

+#endif return 0; }

diff --git a/sound/core/init.c b/sound/core/init.c index 31ba7024e3ad..fda38b2137ee 100644 --- a/sound/core/init.c +++ b/sound/core/init.c @@ -284,6 +284,9 @@ static int snd_card_init(struct snd_card *card, struct device *parent, INIT_LIST_HEAD(&card->ctl_files); spin_lock_init(&card->files_lock); INIT_LIST_HEAD(&card->files_list); +#ifdef CONFIG_SND_CTL_HASHTABLE

• hash_init(card->ctl_htable);

+#endif mutex_init(&card->memory_mutex); #ifdef CONFIG_PM init_waitqueue_head(&card->power_sleep); diff --git a/sound/soc/Kconfig b/sound/soc/Kconfig index 5dcf77af07af..0eb18f8ee6fd 100644 --- a/sound/soc/Kconfig +++ b/sound/soc/Kconfig @@ -58,6 +58,15 @@ config SND_SOC_TOPOLOGY_KUNIT_TEST config SND_SOC_ACPI tristate

+config SND_CTL_HASHTABLE

• bool "Add SND CTL hashtable"
• help

•  This enables hash table in sound card for kcontrols. The traditional way is
  

•  traversing the linked list of controls and compare each exsiting control with
  

•  the new kcontrol to find out whether there are duplicate kcontrols, which will
  

•  consumes much time during bootup. Enable this will use hash table instead of
  

•  linked list to check new kcontrol and reduce much time for sound card registration.
  

# All the supported SoCs source "sound/soc/adi/Kconfig" source "sound/soc/amd/Kconfig" -- 2.17.1

On Sun, May 29, 2022 at 02:20:09PM +0530, Raghu Bankapur wrote:

index 5dcf77af07af..0eb18f8ee6fd 100644 --- a/sound/soc/Kconfig +++ b/sound/soc/Kconfig @@ -58,6 +58,15 @@ config SND_SOC_TOPOLOGY_KUNIT_TEST config SND_SOC_ACPI tristate

+config SND_CTL_HASHTABLE

• bool "Add SND CTL hashtable"
• help

•  This enables hash table in sound card for kcontrols. The traditional way is
  

Since the rest of the change is to the ALSA core this should be in the core ALSA Kconfig, though I'm also wondering if there's any reason to make it configurable at all - is there any big downside to just using the hastable all the time? This sort of tuning control tends to be a bit unclear for users.