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 >
