Re: [PATCH V0 1/1] asoc: msm: use hashtable to check kcontrol

[Takashi Iwai]

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@xxxxxxxxxxx>

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@xxxxxxx/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
>