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 <[email protected]>
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/[email protected]/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
>