From 4d76cfcee2adf467c41933f143f3cbbec41c9624 Mon Sep 17 00:00:00 2001 From: Jakub Jermar Date: Sat, 19 Aug 2017 02:01:04 +0200 Subject: [PATCH] Remove the linear IRQ hash table optimization --- kernel/generic/src/ddi/irq.c | 211 +++++++------------------------------------ 1 file changed, 35 insertions(+), 176 deletions(-) diff --git a/kernel/generic/src/ddi/irq.c b/kernel/generic/src/ddi/irq.c index 76a5074be..7af8a1a66 100644 --- a/kernel/generic/src/ddi/irq.c +++ b/kernel/generic/src/ddi/irq.c @@ -31,37 +31,11 @@ */ /** * @file - * @brief IRQ dispatcher. + * @brief IRQ dispatcher * - * This file provides means of connecting IRQs with particular devices and logic - * for dispatching interrupts to IRQ handlers defined by those devices. - * - * This code is designed to support: - * - multiple devices sharing single IRQ - * - multiple IRQs per single device - * - multiple instances of the same device - * - * - * Note about architectures. - * - * Some architectures have the term IRQ well defined. Examples of such - * architectures include amd64, ia32 and mips32. Some other architectures, such - * as sparc64, don't use the term at all. In those cases, we boldly step forward - * and define what an IRQ is. - * - * The implementation is generic enough and still allows the architectures to - * use the hardware layout effectively. For instance, on amd64 and ia32, where - * there is only 16 IRQs, the irq_hash_table can be optimized to a - * one-dimensional array. Next, when it is known that the IRQ numbers (aka - * INR's) are unique, the claim functions can always return IRQ_ACCEPT. - * - * - * Note about the irq_hash_table. - * - * The hash table is configured to use two keys: inr and mode. However, the - * hash index is computed only from inr. Moreover, if mode is IRQ_HT_MODE_CLAIM, - * the match is based also on the return value of the claim(). Otherwise the - * the keys do not match. + * This file provides means of connecting IRQs with respective device drivers + * and logic for dispatching interrupts to IRQ handlers defined by those + * drivers. */ #include @@ -74,7 +48,7 @@ #include #include -/** Spinlock protecting the kernel IRQ hash table. +/** Spinlock protecting the kernel IRQ hash table * * This lock must be taken only when interrupts are disabled. * @@ -84,20 +58,16 @@ IRQ_SPINLOCK_STATIC_INITIALIZE(irq_kernel_hash_table_lock); /** The kernel IRQ hash table. */ static hash_table_t irq_kernel_hash_table; -/** Spinlock protecting the uspace IRQ hash table. +/** Spinlock protecting the uspace IRQ hash table * * This lock must be taken only when interrupts are disabled. * */ IRQ_SPINLOCK_INITIALIZE(irq_uspace_hash_table_lock); -/** The uspace IRQ hash table. */ +/** The uspace IRQ hash table */ hash_table_t irq_uspace_hash_table; -/** - * Hash table operations for cases when we know that there will be collisions - * between different keys. - */ static size_t irq_ht_hash(sysarg_t *key); static bool irq_ht_compare(sysarg_t *key, size_t keys, link_t *item); static void irq_ht_remove(link_t *item); @@ -108,31 +78,16 @@ static hash_table_operations_t irq_ht_ops = { .remove_callback = irq_ht_remove, }; -/** - * Hash table operations for cases when we know that there will be no collisions - * between different keys. However, there might be still collisions among - * elements with single key (sharing of one IRQ). - */ -static size_t irq_lin_hash(sysarg_t *key); -static bool irq_lin_compare(sysarg_t *key, size_t keys, link_t *item); -static void irq_lin_remove(link_t *item); - -static hash_table_operations_t irq_lin_ops = { - .hash = irq_lin_hash, - .compare = irq_lin_compare, - .remove_callback = irq_lin_remove, -}; - -/** Number of buckets in either of the hash tables. */ +/** Number of buckets in either of the hash tables */ static size_t buckets; -/** Last valid INR. */ +/** Last valid INR */ inr_t last_inr = 0; -/** Initialize IRQ subsystem. +/** Initialize IRQ subsystem * - * @param inrs Numbers of unique IRQ numbers or INRs. - * @param chains Number of chains in the hash table. + * @param inrs Numbers of unique IRQ numbers or INRs. + * @param chains Number of buckets in the hash table. * */ void irq_init(size_t inrs, size_t chains) @@ -140,28 +95,13 @@ void irq_init(size_t inrs, size_t chains) buckets = chains; last_inr = inrs - 1; - /* - * Be smart about the choice of the hash table operations. In cases in - * which inrs equals the requested number of chains (i.e. where there is - * no collision between different keys), we can use optimized set of - * operations. - */ - if (inrs == chains) { - hash_table_create(&irq_uspace_hash_table, chains, 2, - &irq_lin_ops); - hash_table_create(&irq_kernel_hash_table, chains, 2, - &irq_lin_ops); - } else { - hash_table_create(&irq_uspace_hash_table, chains, 2, - &irq_ht_ops); - hash_table_create(&irq_kernel_hash_table, chains, 2, - &irq_ht_ops); - } + hash_table_create(&irq_uspace_hash_table, chains, 2, &irq_ht_ops); + hash_table_create(&irq_kernel_hash_table, chains, 2, &irq_ht_ops); } -/** Initialize one IRQ structure. +/** Initialize one IRQ structure * - * @param irq Pointer to the IRQ structure to be initialized. + * @param irq Pointer to the IRQ structure to be initialized. * */ void irq_initialize(irq_t *irq) @@ -175,12 +115,12 @@ void irq_initialize(irq_t *irq) irq_initialize_arch(irq); } -/** Register IRQ for device. +/** Register IRQ for device * * The irq structure must be filled with information about the interrupt source * and with the claim() function pointer and handler() function pointer. * - * @param irq IRQ structure belonging to a device. + * @param irq IRQ structure belonging to a device. * */ void irq_register(irq_t *irq) @@ -197,9 +137,7 @@ void irq_register(irq_t *irq) irq_spinlock_unlock(&irq_kernel_hash_table_lock, true); } -/** Search and lock the uspace IRQ hash table. - * - */ +/** Search and lock the uspace IRQ hash table */ static irq_t *irq_dispatch_and_lock_uspace(inr_t inr) { link_t *lnk; @@ -220,9 +158,7 @@ static irq_t *irq_dispatch_and_lock_uspace(inr_t inr) return NULL; } -/** Search and lock the kernel IRQ hash table. - * - */ +/** Search and lock the kernel IRQ hash table */ static irq_t *irq_dispatch_and_lock_kernel(inr_t inr) { link_t *lnk; @@ -243,7 +179,7 @@ static irq_t *irq_dispatch_and_lock_kernel(inr_t inr) return NULL; } -/** Dispatch the IRQ. +/** Dispatch the IRQ * * We assume this function is only called from interrupt context (i.e. that * interrupts are disabled prior to this call). @@ -251,7 +187,7 @@ static irq_t *irq_dispatch_and_lock_kernel(inr_t inr) * This function attempts to lookup a fitting IRQ structure. In case of success, * return with interrupts disabled and holding the respective structure. * - * @param inr Interrupt number (aka inr or irq). + * @param inr Interrupt number (aka inr or irq). * * @return IRQ structure of the respective device * @return NULL if no IRQ structure found @@ -281,14 +217,10 @@ irq_t *irq_dispatch_and_lock(inr_t inr) return irq_dispatch_and_lock_kernel(inr); } -/** Compute hash index for the key. - * - * This function computes hash index into the IRQ hash table for which there can - * be collisions between different INRs. +/** Compute hash index for the key * - * The mode is not used to compute the hash. - * - * @param key The first of the keys is inr and the second is mode. + * @param key The first of the keys is inr and the second is mode. Only inr is + * used to compute the hash. * * @return Index into the hash table. * @@ -299,23 +231,19 @@ size_t irq_ht_hash(sysarg_t key[]) return inr % buckets; } -/** Compare hash table element with a key. +/** Compare hash table element with a key * - * There are two things to note about this function. First, it is used for the - * more complex architecture setup in which there are way too many interrupt - * numbers (i.e. inr's) to arrange the hash table so that collisions occur only - * among same inrs of different devices. So the explicit check for inr match - * must be done. Second, if mode is IRQ_HT_MODE_CLAIM, the result of the - * claim() function is used for the match. Otherwise the key does not match. + * If mode is IRQ_HT_MODE_CLAIM, the result of the claim() function is used for + * the match. Otherwise the key does not match. * * This function assumes interrupts are already disabled. * - * @param key Keys (i.e. inr and mode). - * @param keys This is 2. - * @param item The item to compare the key with. + * @param key Keys (i.e. inr and mode). + * @param keys This is 2. + * @param item The item to compare the key with. * - * @return true on match - * @return false on no match + * @return True on match + * @return False on no match * */ bool irq_ht_compare(sysarg_t key[], size_t keys, link_t *item) @@ -342,9 +270,9 @@ bool irq_ht_compare(sysarg_t key[], size_t keys, link_t *item) return rv; } -/** Unlock IRQ structure after hash_table_remove(). +/** Unlock IRQ structure after hash_table_remove() * - * @param lnk Link in the removed and locked IRQ structure. + * @param lnk Link in the removed and locked IRQ structure. */ void irq_ht_remove(link_t *lnk) { @@ -353,74 +281,5 @@ void irq_ht_remove(link_t *lnk) irq_spinlock_unlock(&irq->lock, false); } -/** Compute hash index for the key. - * - * This function computes hash index into the IRQ hash table for which there are - * no collisions between different INRs. - * - * @param key The first of the keys is inr and the second is mode. - * - * @return Index into the hash table. - * - */ -size_t irq_lin_hash(sysarg_t key[]) -{ - inr_t inr = (inr_t) key[IRQ_HT_KEY_INR]; - return inr; -} - -/** Compare hash table element with a key. - * - * There are two things to note about this function. First, it is used for the - * less complex architecture setup in which there are not too many interrupt - * numbers (i.e. inr's) to arrange the hash table so that collisions occur only - * among same inrs of different devnos. So the explicit check for inr match is - * not done. Second, if devno is -1, the second key (i.e. devno) is not used - * for the match and the result of the claim() function is used instead. - * - * This function assumes interrupts are already disabled. - * - * @param key Keys (i.e. inr and mode). - * @param keys This is 2. - * @param item The item to compare the key with. - * - * @return true on match - * @return false on no match - * - */ -bool irq_lin_compare(sysarg_t key[], size_t keys, link_t *item) -{ - irq_t *irq = list_get_instance(item, irq_t, link); - irq_ht_mode_t mode = (irq_ht_mode_t) key[IRQ_HT_KEY_MODE]; - bool rv; - - irq_spinlock_lock(&irq->lock, false); - if (mode == IRQ_HT_MODE_CLAIM) { - /* Invoked by irq_dispatch_and_lock() */ - rv = (irq->claim(irq) == IRQ_ACCEPT); - } else { - /* Invoked by irq_find_and_lock() */ - rv = false; - } - - /* unlock only on non-match */ - if (!rv) - irq_spinlock_unlock(&irq->lock, false); - - return rv; -} - -/** Unlock IRQ structure after hash_table_remove(). - * - * @param lnk Link in the removed and locked IRQ structure. - * - */ -void irq_lin_remove(link_t *lnk) -{ - irq_t *irq __attribute__((unused)) - = hash_table_get_instance(lnk, irq_t, link); - irq_spinlock_unlock(&irq->lock, false); -} - /** @} */ -- 2.11.4.GIT