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

[Raghu Ballappa Bankapur <quic_rbankapu@quicinc.com>]

Hi Takashi

Our implementation also falls inline with your approach [PATCH RFC] 
ALSA: control: Use xarray for faster lookups (kernel.org) 
<https://lore.kernel.org/all/20211028130027.18764-1-tiwai@suse.de/T/>, 
but you approach looks to be clean with xarray.

is it possible to upstream those changes?

Regards

Raghu Bankapur

On 5/29/2022 3:05 PM, Takashi Iwai wrote:
> 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
>>