genirq/timings: Fixes and selftests
Subsystems (2)
v3 cover genirq/timings: Fixes and selftests
This series provides a couple of fixes, an optimization and the code to do the selftests.
While writing the selftests, a couple of issues were spotted with the circular buffer handling and the routine searching for the pattern multiple times.
In addition, a small optimization has been found while investigating the bugs above.
In order to write the selftest, the routine needed by the core code and the tests are wrapped into function which are always inline so the current code is not impacted by a new function call. There is no functional changes in this part.
Finally, the selftest uses samples to insert values in the arrays and use them to predict the next event. These tests cover the most difficult part of the code.
Changelog:
V3:
- Removed patch using the min macro
- Fixed comment typos in patch 1/8
V2:
- Removed defaulting to 'n' as it is already the case
*** BLURB HERE ***
Daniel Lezcano (8):
genirq/timings: Fix next event index function genirq/timings: Fix timings buffer inspection genirq/timings: Optimize the period detection speed genirq/timings: Encapsulate timings push genirq/timings: Encapsulate storing function genirq/timings: Add selftest for circular array genirq/timings: Add selftest for irqs circular buffer genirq/timings: Add selftest for next event computation
kernel/irq/Makefile | 3 + kernel/irq/internals.h | 21 +- kernel/irq/timings.c | 453 +++++++++++++++++++++++++++++++++++++---- lib/Kconfig.debug | 8 + 4 files changed, 442 insertions(+), 43 deletions(-)
Signature · 1 line
2.17.1
PATCH v3 1/8 genirq/timings: Fix next event index function
The current code was luckily working with most of the interval samples testing but actually it fails to correctly detect pattern repeatition breaking at the end of the buffer.
Narrowing down the bug has been a real pain because of the pointers, so the routine is rewrite by using indexes instead.
--- kernel/irq/timings.c | 51 ++++++++++++++++++++++++++++++++++++-------- 1 file changed, 42 insertions(+), 9 deletions(-)
kernel/irq/timings.c +42 -9
@@ -297,7 +297,16 @@ static u64 irq_timings_ema_new(u64 value, u64 ema_old)static int irq_timings_next_event_index (int *buffer,size_t len,int period_max) { -int i; +int period; + +/* +* Move the beginning pointer to the end minus the max period x 3. +* We are at the point we can begin searching the pattern +*/ + buffer = &buffer[len - (period_max *3 )]; + +/* Adjust the length to the maximum allowed period x 3 */ + len = period_max *3 ;/* * The buffer contains the suite of intervals, in a ilog2
@@ -306,21 +315,45 @@ static int irq_timings_next_event_index(int *buffer, size_t len, int period_max)* period beginning at the end of the buffer. We do that for * each suffix. */ -for (i = period_max; i >=PREDICTION_PERIOD_MIN ; i--) { +for (period = period_max; period >=PREDICTION_PERIOD_MIN ; period--) { -int *begin = &buffer[len - (i *3 )]; -int *ptr = begin; +/* +* The first comparison always succeed because the +* suffix is deduced from the first n-period bytes of +* the buffer and we compare the initial suffix with +* itself, so we can skip the first iteration. +*/ +int idx = period; +size_t size = period;/* * We look if the suite with period 'i' repeat * itself. If it is truncated at the end, as it * repeats we can use the period to find out the next -* element. +* element with the modulo. */ -while (!memcmp (ptr, begin, i *sizeof (*ptr))) { - ptr += i; -if (ptr >= &buffer[len]) -return begin[((i *3 ) % i)]; +while (!memcmp (buffer, &buffer[idx], size *sizeof (int ))) { + +/* +* Move the index in a period basis +*/ + idx += size; + +/* +* If this condition is reached, all previous +* memcmp were successful, so the period is +* found. +*/ +if (idx == len) +return buffer[len % period]; + +/* +* If the remaining elements to compare are +* smaller than the period, readjust the size +* of the comparison for the last iteration. +*/ +if (len - idx < period) + size = len - idx; } }
Signature · 1 line
2.17.1
tip-bot for Daniel Lezcano
merge bot[tip:irq/core] genirq/timings: Fix next event index function
genirq/timings: Fix next event index function
Commit-ID: 619c1baa91b2820eae9ff5d89eb525df81ea7a5a Gitweb: https://git.kernel.org/tip/619c1baa91b2820eae9ff5d89eb525df81ea7a5a Author: Daniel Lezcano <[email protected]> AuthorDate: Mon, 27 May 2019 22:55:14 +0200 Committer: Thomas Gleixner <[email protected]> CommitDate: Wed, 12 Jun 2019 10:47:03 +0200
genirq/timings: Fix next event index function
The current code is luckily working with most of the interval samples testing but actually it fails to correctly detect pattern repetition breaking at the end of the buffer.
Narrowing down the bug has been a real pain because of the pointers, so the routine is rewrittne by using indexes instead.
--- kernel/irq/timings.c | 51 ++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 42 insertions(+), 9 deletions(-)
kernel/irq/timings.c +42 -9
@@ -297,7 +297,16 @@ static u64 irq_timings_ema_new(u64 value, u64 ema_old)static int irq_timings_next_event_index (int *buffer,size_t len,int period_max) { -int i; +int period; + +/* +* Move the beginning pointer to the end minus the max period x 3. +* We are at the point we can begin searching the pattern +*/ + buffer = &buffer[len - (period_max *3 )]; + +/* Adjust the length to the maximum allowed period x 3 */ + len = period_max *3 ;/* * The buffer contains the suite of intervals, in a ilog2
@@ -306,21 +315,45 @@ static int irq_timings_next_event_index(int *buffer, size_t len, int period_max)* period beginning at the end of the buffer. We do that for * each suffix. */ -for (i = period_max; i >=PREDICTION_PERIOD_MIN ; i--) { +for (period = period_max; period >=PREDICTION_PERIOD_MIN ; period--) { -int *begin = &buffer[len - (i *3 )]; -int *ptr = begin; +/* +* The first comparison always succeed because the +* suffix is deduced from the first n-period bytes of +* the buffer and we compare the initial suffix with +* itself, so we can skip the first iteration. +*/ +int idx = period; +size_t size = period;/* * We look if the suite with period 'i' repeat * itself. If it is truncated at the end, as it * repeats we can use the period to find out the next -* element. +* element with the modulo. */ -while (!memcmp (ptr, begin, i *sizeof (*ptr))) { - ptr += i; -if (ptr >= &buffer[len]) -return begin[((i *3 ) % i)]; +while (!memcmp (buffer, &buffer[idx], size *sizeof (int ))) { + +/* +* Move the index in a period basis +*/ + idx += size; + +/* +* If this condition is reached, all previous +* memcmp were successful, so the period is +* found. +*/ +if (idx == len) +return buffer[len % period]; + +/* +* If the remaining elements to compare are +* smaller than the period, readjust the size +* of the comparison for the last iteration. +*/ +if (len - idx < period) + size = len - idx; } }
PATCH v3 2/8 genirq/timings: Fix timings buffer inspection
In reply to Daniel LezcanoIt appears the index beginning computation is not correct, the current code does:
i = (irqts->count & IRQ_TIMINGS_MASK) - 1
If irqts->count is equal to zero, we end up with an index equal to -1, but that does not happen because the function checks against zero before and returns in such case.
However, if irqts->count is a multiple of IRQ_TIMINGS_SIZE, the resulting & bit op will be zero and leads also to a -1 index.
Re-introduce the iteration loop belonging to the previous variance code which was correct.
--- kernel/irq/timings.c | 23 ++++++++++++++++++----- 1 file changed, 18 insertions(+), 5 deletions(-)
kernel/irq/timings.c +18 -5
@@ -267,6 +267,23 @@ void irq_timings_disable(void)#define PREDICTION_MAX 10/* 2 ^ PREDICTION_MAX useconds */ #define PREDICTION_BUFFER_SIZE 16/* slots for EMAs, hardly more than 16 */ +/* +* Number of elements in the circular buffer: If it happens it was +* flushed before, then the number of elements could be smaller than +* IRQ_TIMINGS_SIZE, so the count is used, otherwise the array size is +* used as we wrapped. The index begins from zero when we did not +* wrap. That could be done in a nicer way with the proper circular +* array structure type but with the cost of extra computation in the +* interrupt handler hot path. We choose efficiency. +*/ +#define for_each_irqts (i, irqts) \ + for (i = irqts->count < IRQ_TIMINGS_SIZE ? \ + 0 : irqts->count & IRQ_TIMINGS_MASK, \ + irqts->count = min(IRQ_TIMINGS_SIZE, \ + irqts->count); \ + irqts->count > 0; irqts->count--, \ + i = (i + 1) & IRQ_TIMINGS_MASK) +struct irqt_stat {u64 last_ts;u64 ema_time[PREDICTION_BUFFER_SIZE ];
@@ -526,11 +543,7 @@ u64 irq_timings_next_event(u64 now)* model while decrementing the counter because we consume the * data from our circular buffer. */ - - i = (irqts->count &IRQ_TIMINGS_MASK ) -1 ; - irqts->count =min (IRQ_TIMINGS_SIZE , irqts->count); - -for (; irqts->count >0 ; irqts->count--, i = (i +1 ) &IRQ_TIMINGS_MASK ) { +for_each_irqts (i, irqts) { irq =irq_timing_decode (irqts->values[i], &ts); s =idr_find (&irqt_stats, irq);if (s)
Signature · 1 line
2.17.1
tip-bot for Daniel Lezcano
merge bot[tip:irq/core] genirq/timings: Fix timings buffer inspection
genirq/timings: Fix timings buffer inspection
Commit-ID: 2840eef0513c518faeb8a0ab8d07268c6285cdd0 Gitweb: https://git.kernel.org/tip/2840eef0513c518faeb8a0ab8d07268c6285cdd0 Author: Daniel Lezcano <[email protected]> AuthorDate: Mon, 27 May 2019 22:55:15 +0200 Committer: Thomas Gleixner <[email protected]> CommitDate: Wed, 12 Jun 2019 10:47:03 +0200
genirq/timings: Fix timings buffer inspection
It appears the index beginning computation is not correct, the current code does:
i = (irqts->count & IRQ_TIMINGS_MASK) - 1
If irqts->count is equal to zero, we end up with an index equal to -1, but that does not happen because the function checks against zero before and returns in such case.
However, if irqts->count is a multiple of IRQ_TIMINGS_SIZE, the resulting & bit op will be zero and leads also to a -1 index.
Re-introduce the iteration loop belonging to the previous variance code which was correct.
--- kernel/irq/timings.c | 23 ++++++++++++++++++----- 1 file changed, 18 insertions(+), 5 deletions(-)
kernel/irq/timings.c +18 -5
@@ -267,6 +267,23 @@ void irq_timings_disable(void)#define PREDICTION_MAX 10/* 2 ^ PREDICTION_MAX useconds */ #define PREDICTION_BUFFER_SIZE 16/* slots for EMAs, hardly more than 16 */ +/* +* Number of elements in the circular buffer: If it happens it was +* flushed before, then the number of elements could be smaller than +* IRQ_TIMINGS_SIZE, so the count is used, otherwise the array size is +* used as we wrapped. The index begins from zero when we did not +* wrap. That could be done in a nicer way with the proper circular +* array structure type but with the cost of extra computation in the +* interrupt handler hot path. We choose efficiency. +*/ +#define for_each_irqts (i, irqts) \ + for (i = irqts->count < IRQ_TIMINGS_SIZE ? \ + 0 : irqts->count & IRQ_TIMINGS_MASK, \ + irqts->count = min(IRQ_TIMINGS_SIZE, \ + irqts->count); \ + irqts->count > 0; irqts->count--, \ + i = (i + 1) & IRQ_TIMINGS_MASK) +struct irqt_stat {u64 last_ts;u64 ema_time[PREDICTION_BUFFER_SIZE ];
@@ -526,11 +543,7 @@ u64 irq_timings_next_event(u64 now)* model while decrementing the counter because we consume the * data from our circular buffer. */ - - i = (irqts->count &IRQ_TIMINGS_MASK ) -1 ; - irqts->count =min (IRQ_TIMINGS_SIZE , irqts->count); - -for (; irqts->count >0 ; irqts->count--, i = (i +1 ) &IRQ_TIMINGS_MASK ) { +for_each_irqts (i, irqts) { irq =irq_timing_decode (irqts->values[i], &ts); s =idr_find (&irqt_stats, irq);if (s)
PATCH v3 3/8 genirq/timings: Optimize the period detection speed
In reply to Daniel LezcanoIf we have a minimal period and if there is a period which is a multiple of it but lesser than the max period then it will be detected before and the minimal period will be never reached.
1 2 1 2 1 2 1 2 1 2 1 2
<-----> <-----> <----->
<-> <-> <-> <-> <-> <->
In our case, the minimum period is 2 and the maximum period is 5. That means all repeating pattern of 2 will be detected as repeating pattern of 4, it is pointless to go up to 2 when searching for the period as it will always fail.
Remove one loop iteration by increasing the minimal period to 3.
--- kernel/irq/timings.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/irq/timings.c +1 -1
@@ -261,7 +261,7 @@ void irq_timings_disable(void)#define EMA_ALPHA_VAL 64#define EMA_ALPHA_SHIFT 7 -#define PREDICTION_PERIOD_MIN 2 +#define PREDICTION_PERIOD_MIN 3#define PREDICTION_PERIOD_MAX 5#define PREDICTION_FACTOR 4#define PREDICTION_MAX 10/* 2 ^ PREDICTION_MAX useconds */
Signature · 1 line
2.17.1
tip-bot for Daniel Lezcano
merge bot[tip:irq/core] genirq/timings: Optimize the period detection speed
genirq/timings: Optimize the period detection speed
Commit-ID: 3c2e79f4cef7938125b356e7f5c8fd038212619a Gitweb: https://git.kernel.org/tip/3c2e79f4cef7938125b356e7f5c8fd038212619a Author: Daniel Lezcano <[email protected]> AuthorDate: Mon, 27 May 2019 22:55:16 +0200 Committer: Thomas Gleixner <[email protected]> CommitDate: Wed, 12 Jun 2019 10:47:03 +0200
genirq/timings: Optimize the period detection speed
With a minimal period and if there is a period which is a multiple of it but lesser than the max period then it will be detected before and the minimal period will be never reached.
1 2 1 2 1 2 1 2 1 2 1 2
<-----> <-----> <----->
<-> <-> <-> <-> <-> <->
In that case, the minimum period is 2 and the maximum period is 5. That means all repeating pattern of 2 will be detected as repeating pattern of 4, it is pointless to go up to 2 when searching for the period as it will always fail.
Remove one loop iteration by increasing the minimal period to 3.
--- kernel/irq/timings.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/irq/timings.c +1 -1
@@ -261,7 +261,7 @@ void irq_timings_disable(void)#define EMA_ALPHA_VAL 64#define EMA_ALPHA_SHIFT 7 -#define PREDICTION_PERIOD_MIN 2 +#define PREDICTION_PERIOD_MIN 3#define PREDICTION_PERIOD_MAX 5#define PREDICTION_FACTOR 4#define PREDICTION_MAX 10/* 2 ^ PREDICTION_MAX useconds */
PATCH v3 4/8 genirq/timings: Encapsulate timings push
In reply to Daniel LezcanoFor the next patches providing the selftest, we do want to artificially insert timings value in the circular buffer in order to check the correctness of the code. Encapsulate the common code between the future test code and the current with an always-inline tag.
No functional change.
--- kernel/irq/internals.h | 21 ++++++++++++--------- 1 file changed, 12 insertions(+), 9 deletions(-)
kernel/irq/internals.h +12 -9
@@ -354,6 +354,16 @@ static inline int irq_timing_decode(u64 value, u64 *timestamp)return value &U16_MAX ; } +static __always_inline void irq_timings_push(u64 ts, int irq) +{ +struct irq_timings *timings =this_cpu_ptr (&irq_timings); + + timings->values[timings->count &IRQ_TIMINGS_MASK ] = +irq_timing_encode (ts, irq); + + timings->count++; +} +/* * The function record_irq_time is only called in one place in the * interrupts handler. We want this function always inline so the code
@@ -367,15 +377,8 @@ static __always_inline void record_irq_time(struct irq_desc *desc)if (!static_branch_likely (&irq_timing_enabled))return ; -if (desc->istate &IRQS_TIMINGS ) { -struct irq_timings *timings =this_cpu_ptr (&irq_timings); - - timings->values[timings->count &IRQ_TIMINGS_MASK ] = -irq_timing_encode (local_clock (), -irq_desc_get_irq (desc)); - - timings->count++; - } +if (desc->istate &IRQS_TIMINGS ) + irq_timings_push(local_clock(), irq_desc_get_irq(desc)); }#else static inline void irq_remove_timings (struct irq_desc *desc) {}
Signature · 1 line
2.17.1
tip-bot for Daniel Lezcano
merge bot[tip:irq/core] genirq/timings: Encapsulate timings push
genirq/timings: Encapsulate timings push
Commit-ID: df025e47e4e34b779af2cc72c350877be7104ef3 Gitweb: https://git.kernel.org/tip/df025e47e4e34b779af2cc72c350877be7104ef3 Author: Daniel Lezcano <[email protected]> AuthorDate: Mon, 27 May 2019 22:55:17 +0200 Committer: Thomas Gleixner <[email protected]> CommitDate: Wed, 12 Jun 2019 10:47:04 +0200
genirq/timings: Encapsulate timings push
For the next patches providing the selftest, it is required to artificially insert timings value in the circular buffer in order to check the correctness of the code. Encapsulate the common code between the future test code and the current code with an always-inline tag.
No functional change.
--- kernel/irq/internals.h | 21 ++++++++++++--------- 1 file changed, 12 insertions(+), 9 deletions(-)
kernel/irq/internals.h +12 -9
@@ -354,6 +354,16 @@ static inline int irq_timing_decode(u64 value, u64 *timestamp)return value &U16_MAX ; } +static __always_inline void irq_timings_push(u64 ts, int irq) +{ +struct irq_timings *timings =this_cpu_ptr (&irq_timings); + + timings->values[timings->count &IRQ_TIMINGS_MASK ] = +irq_timing_encode (ts, irq); + + timings->count++; +} +/* * The function record_irq_time is only called in one place in the * interrupts handler. We want this function always inline so the code
@@ -367,15 +377,8 @@ static __always_inline void record_irq_time(struct irq_desc *desc)if (!static_branch_likely (&irq_timing_enabled))return ; -if (desc->istate &IRQS_TIMINGS ) { -struct irq_timings *timings =this_cpu_ptr (&irq_timings); - - timings->values[timings->count &IRQ_TIMINGS_MASK ] = -irq_timing_encode (local_clock (), -irq_desc_get_irq (desc)); - - timings->count++; - } +if (desc->istate &IRQS_TIMINGS ) + irq_timings_push(local_clock(), irq_desc_get_irq(desc)); }#else static inline void irq_remove_timings (struct irq_desc *desc) {}
PATCH v3 5/8 genirq/timings: Encapsulate storing function
In reply to Daniel LezcanoFor the next patches providing the selftest, we want to insert interval values directly in the buffer in order to check the correctness of the code. Encapsulate the code doing that in a always inline function in order to reuse it in the test code.
No functional changes.
--- kernel/irq/timings.c | 53 ++++++++++++++++++++++++++++---------------- 1 file changed, 34 insertions(+), 19 deletions(-)
kernel/irq/timings.c +34 -19
@@ -430,11 +430,43 @@ static u64 __irq_timings_next_event(struct irqt_stat *irqs, int irq, u64 now)return irqs->last_ts + irqs->ema_time[index]; } +static __always_inline int irq_timings_interval_index(u64 interval) +{ +/* +* The PREDICTION_FACTOR increase the interval size for the +* array of exponential average. +*/ +u64 interval_us = (interval >>10 ) /PREDICTION_FACTOR ; + +return likely (interval_us) ?ilog2 (interval_us) :0 ; +} + +static __always_inline void __irq_timings_store(int irq, struct irqt_stat *irqs, +u64 interval) +{ +int index; + +/* +* Get the index in the ema table for this interrupt. +*/ + index =irq_timings_interval_index (interval); + +/* +* Store the index as an element of the pattern in another +* circular array. +*/ + irqs->circ_timings[irqs->count &IRQ_TIMINGS_MASK ] = index; + + irqs->ema_time[index] =irq_timings_ema_new (interval, + irqs->ema_time[index]); + + irqs->count++; +} +static inline void irq_timings_store (int irq,struct irqt_stat *irqs,u64 ts) {u64 old_ts = irqs->last_ts;u64 interval; -int index;/* * The timestamps are absolute time values, we need to compute
@@ -465,24 +497,7 @@ static inline void irq_timings_store(int irq, struct irqt_stat *irqs, u64 ts)return ; } -/* -* Get the index in the ema table for this interrupt. The -* PREDICTION_FACTOR increase the interval size for the array -* of exponential average. -*/ - index =likely (interval) ? -ilog2 ((interval >>10 ) /PREDICTION_FACTOR ) :0 ; - -/* -* Store the index as an element of the pattern in another -* circular array. -*/ - irqs->circ_timings[irqs->count &IRQ_TIMINGS_MASK ] = index; - - irqs->ema_time[index] =irq_timings_ema_new (interval, - irqs->ema_time[index]); - - irqs->count++; +__irq_timings_store (irq, irqs, interval); }/**
Signature · 1 line
2.17.1
tip-bot for Daniel Lezcano
merge bot[tip:irq/core] genirq/timings: Encapsulate storing function
genirq/timings: Encapsulate storing function
Commit-ID: 23aa3b9a6b7d5029c1f124426bc5ba4430dcc29c Gitweb: https://git.kernel.org/tip/23aa3b9a6b7d5029c1f124426bc5ba4430dcc29c Author: Daniel Lezcano <[email protected]> AuthorDate: Mon, 27 May 2019 22:55:18 +0200 Committer: Thomas Gleixner <[email protected]> CommitDate: Wed, 12 Jun 2019 10:47:04 +0200
genirq/timings: Encapsulate storing function
For the next patches providing the selftest, it is required to insert interval values directly in the buffer in order to check the correctness of the code. Encapsulate the code doing that in a always inline function in order to reuse it in the test code.
No functional changes.
--- kernel/irq/timings.c | 53 +++++++++++++++++++++++++++++++++------------------- 1 file changed, 34 insertions(+), 19 deletions(-)
kernel/irq/timings.c +34 -19
@@ -430,11 +430,43 @@ static u64 __irq_timings_next_event(struct irqt_stat *irqs, int irq, u64 now)return irqs->last_ts + irqs->ema_time[index]; } +static __always_inline int irq_timings_interval_index(u64 interval) +{ +/* +* The PREDICTION_FACTOR increase the interval size for the +* array of exponential average. +*/ +u64 interval_us = (interval >>10 ) /PREDICTION_FACTOR ; + +return likely (interval_us) ?ilog2 (interval_us) :0 ; +} + +static __always_inline void __irq_timings_store(int irq, struct irqt_stat *irqs, +u64 interval) +{ +int index; + +/* +* Get the index in the ema table for this interrupt. +*/ + index =irq_timings_interval_index (interval); + +/* +* Store the index as an element of the pattern in another +* circular array. +*/ + irqs->circ_timings[irqs->count &IRQ_TIMINGS_MASK ] = index; + + irqs->ema_time[index] =irq_timings_ema_new (interval, + irqs->ema_time[index]); + + irqs->count++; +} +static inline void irq_timings_store (int irq,struct irqt_stat *irqs,u64 ts) {u64 old_ts = irqs->last_ts;u64 interval; -int index;/* * The timestamps are absolute time values, we need to compute
@@ -465,24 +497,7 @@ static inline void irq_timings_store(int irq, struct irqt_stat *irqs, u64 ts)return ; } -/* -* Get the index in the ema table for this interrupt. The -* PREDICTION_FACTOR increase the interval size for the array -* of exponential average. -*/ - index =likely (interval) ? -ilog2 ((interval >>10 ) /PREDICTION_FACTOR ) :0 ; - -/* -* Store the index as an element of the pattern in another -* circular array. -*/ - irqs->circ_timings[irqs->count &IRQ_TIMINGS_MASK ] = index; - - irqs->ema_time[index] =irq_timings_ema_new (interval, - irqs->ema_time[index]); - - irqs->count++; +__irq_timings_store (irq, irqs, interval); }/**
PATCH v3 6/8 genirq/timings: Add selftest for circular array
In reply to Daniel LezcanoDue to the complexity of the code and the difficulty to debug it, let's add some selftests to the framework in order to spot issues or regression at boot time when the runtime testing is enabled for this subsystem.
This tests the circular buffer at the limits and validates:
- the encoding / decoding of the values
- the macro to browse the irq timings circular buffer
- the function to push data in the circular buffer
--- kernel/irq/Makefile | 3 ++ kernel/irq/timings.c | 119 +++++++++++++++++++++++++++++++++++++++++++ lib/Kconfig.debug | 8 +++ 3 files changed, 130 insertions(+)
kernel/irq/Makefile +3 -0
@@ -2,6 +2,9 @@ obj-y := irqdesc.o handle.o manage.o spurious.o resend.o chip.o dummychip.o devres.o obj-$(CONFIG_IRQ_TIMINGS) += timings.o +ifeq ($(CONFIG_TEST_IRQ_TIMINGS),y) + CFLAGS_timings.o += -DDEBUG +endif obj-$(CONFIG_GENERIC_IRQ_CHIP) += generic-chip.o obj-$(CONFIG_GENERIC_IRQ_PROBE) += autoprobe.o obj-$(CONFIG_IRQ_DOMAIN) += irqdomain.o
kernel/irq/timings.c +119 -0
132 lines not on this page · raw message
lib/Kconfig.debug +8 -0
@@ -1827,6 +1827,14 @@ config TEST_PARMAN If unsure, say N. +config TEST_IRQ_TIMINGS + bool "IRQ timings selftest" + depends on IRQ_TIMINGS + help + Enable this option to test the irq timings code on boot. + + If unsure, say N. + config TEST_LKM tristate "Test module loading with 'hello world' module" depends on m
Signature · 1 line
2.17.1
tip-bot for Daniel Lezcano
merge bot[tip:irq/core] genirq/timings: Add selftest for circular array
genirq/timings: Add selftest for circular array
Commit-ID: 6aed82de719b424bd5548aa4179e95f34fd779ab Gitweb: https://git.kernel.org/tip/6aed82de719b424bd5548aa4179e95f34fd779ab Author: Daniel Lezcano <[email protected]> AuthorDate: Mon, 27 May 2019 22:55:19 +0200 Committer: Thomas Gleixner <[email protected]> CommitDate: Wed, 12 Jun 2019 10:47:04 +0200
genirq/timings: Add selftest for circular array
Due to the complexity of the code and the difficulty to debug it, add some selftests to the framework in order to spot issues or regression at boot time when the runtime testing is enabled for this subsystem.
This tests the circular buffer at the limits and validates:
- the encoding / decoding of the values
- the macro to browse the irq timings circular buffer
- the function to push data in the circular buffer
--- kernel/irq/Makefile | 3 ++ kernel/irq/timings.c | 119 +++++++++++++++++++++++++++++++++++++++++++++++++++ lib/Kconfig.debug | 8 ++++ 3 files changed, 130 insertions(+)
kernel/irq/Makefile +3 -0
@@ -2,6 +2,9 @@ obj-y := irqdesc.o handle.o manage.o spurious.o resend.o chip.o dummychip.o devres.o obj-$(CONFIG_IRQ_TIMINGS) += timings.o +ifeq ($(CONFIG_TEST_IRQ_TIMINGS),y) + CFLAGS_timings.o += -DDEBUG +endif obj-$(CONFIG_GENERIC_IRQ_CHIP) += generic-chip.o obj-$(CONFIG_GENERIC_IRQ_PROBE) += autoprobe.o obj-$(CONFIG_IRQ_DOMAIN) += irqdomain.o
kernel/irq/timings.c +119 -0
132 lines not on this page · raw message
lib/Kconfig.debug +8 -0
@@ -1858,6 +1858,14 @@ config TEST_PARMAN If unsure, say N. +config TEST_IRQ_TIMINGS + bool "IRQ timings selftest" + depends on IRQ_TIMINGS + help + Enable this option to test the irq timings code on boot. + + If unsure, say N. + config TEST_LKM tristate "Test module loading with 'hello world' module" depends on m
PATCH v3 7/8 genirq/timings: Add selftest for irqs circular buffer
In reply to Daniel LezcanoAfter testing the per cpu interrupt circular event, we want to make sure the per interrupt circular buffer usage is correct.
Add tests to validate the interrupt circular buffer.
--- kernel/irq/timings.c | 139 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 139 insertions(+)
kernel/irq/timings.c +139 -0
@@ -629,6 +629,141 @@ int irq_timings_alloc(int irq) }#ifdef CONFIG_TEST_IRQ_TIMINGS +struct timings_intervals { +u64 *intervals; +size_t count; +}; + +/* +* Intervals are given in nanosecond base +*/ +static u64 intervals0[]__initdata = { +10000 ,50000 ,200000 ,500000 , +10000 ,50000 ,200000 ,500000 , +10000 ,50000 ,200000 ,500000 , +10000 ,50000 ,200000 ,500000 , +10000 ,50000 ,200000 ,500000 , +10000 ,50000 ,200000 ,500000 , +10000 ,50000 ,200000 ,500000 , +10000 ,50000 ,200000 ,500000 , +10000 ,50000 ,200000 , +}; + +static u64 intervals1[]__initdata = { +223947000 ,1240000 ,1384000 ,1386000 ,1386000 , +217416000 ,1236000 ,1384000 ,1386000 ,1387000 , +214719000 ,1241000 ,1386000 ,1387000 ,1384000 , +213696000 ,1234000 ,1384000 ,1386000 ,1388000 , +219904000 ,1240000 ,1385000 ,1389000 ,1385000 , +212240000 ,1240000 ,1386000 ,1386000 ,1386000 , +214415000 ,1236000 ,1384000 ,1386000 ,1387000 , +214276000 ,1234000 , +}; + +static u64 intervals2[]__initdata = { +4000 ,3000 ,5000 ,100000 , +3000 ,3000 ,5000 ,117000 , +4000 ,4000 ,5000 ,112000 , +4000 ,3000 ,4000 ,110000 , +3000 ,5000 ,3000 ,117000 , +4000 ,4000 ,5000 ,112000 , +4000 ,3000 ,4000 ,110000 , +3000 ,4000 ,5000 ,112000 , +4000 , +}; + +static u64 intervals3[]__initdata = { +1385000 ,212240000 ,1240000 , +1386000 ,214415000 ,1236000 , +1384000 ,214276000 ,1234000 , +1386000 ,214415000 ,1236000 , +1385000 ,212240000 ,1240000 , +1386000 ,214415000 ,1236000 , +1384000 ,214276000 ,1234000 , +1386000 ,214415000 ,1236000 , +1385000 ,212240000 ,1240000 , +}; + +static u64 intervals4[]__initdata = { +10000 ,50000 ,10000 ,50000 , +10000 ,50000 ,10000 ,50000 , +10000 ,50000 ,10000 ,50000 , +10000 ,50000 ,10000 ,50000 , +10000 ,50000 ,10000 ,50000 , +10000 ,50000 ,10000 ,50000 , +10000 ,50000 ,10000 ,50000 , +10000 ,50000 ,10000 ,50000 , +10000 , +}; + +static struct timings_intervals tis[]__initdata = { + { intervals0,ARRAY_SIZE (intervals0) }, + { intervals1,ARRAY_SIZE (intervals1) }, + { intervals2,ARRAY_SIZE (intervals2) }, + { intervals3,ARRAY_SIZE (intervals3) }, + { intervals4,ARRAY_SIZE (intervals4) }, +}; + +static int __init irq_timings_test_irqs (struct timings_intervals *ti) +{ +struct irqt_stat __percpu *s; +struct irqt_stat *irqs; +int i, index, ret, irq =0xACE5 ; + + ret =irq_timings_alloc (irq); +if (ret) { +pr_err ("Failed to allocate irq timings\n" ); +return ret; + } + + s =idr_find (&irqt_stats, irq); +if (!s) { + ret = -EIDRM ; + goto out; + } + + irqs =this_cpu_ptr (s); + +for (i =0 ; i < ti->count; i++) { + + index =irq_timings_interval_index (ti->intervals[i]); +pr_debug ("%d: interval=%llu ema_index=%d\n" , + i, ti->intervals[i], index); + +__irq_timings_store (irq, irqs, ti->intervals[i]); +if (irqs->circ_timings[i &IRQ_TIMINGS_MASK ] != index) { +pr_err ("Failed to store in the circular buffer\n" ); + goto out; + } + } + +if (irqs->count != ti->count) { +pr_err ("Count differs\n" ); + goto out; + } + + ret =0 ; +out: +irq_timings_free (irq); + +return ret; +} + +static int __init irq_timings_irqs_selftest (void ) +{ +int i, ret; + +for (i =0 ; i <ARRAY_SIZE (tis); i++) { +pr_info ("---> Injecting intervals number #%d (count=%zd)\n" , + i, tis[i].count); + ret =irq_timings_test_irqs (&tis[i]); +if (ret) +break ; + } + +return ret; +} +static int __init irq_timings_test_irqts (struct irq_timings *irqts,unsigned count) {
@@ -736,7 +871,11 @@ static int __init irq_timings_selftest(void) } ret =irq_timings_irqts_selftest (); +if (ret) + goto out; + ret =irq_timings_irqs_selftest (); +out:pr_info ("---------- selftest end with %s -----------\n" , ret ?"failure" :"success" );
Signature · 1 line
2.17.1
tip-bot for Daniel Lezcano
merge bot[tip:irq/core] genirq/timings: Add selftest for irqs circular buffer
genirq/timings: Add selftest for irqs circular buffer
Commit-ID: f52da98d900e18a250cb14ca426d4041ea7002db Gitweb: https://git.kernel.org/tip/f52da98d900e18a250cb14ca426d4041ea7002db Author: Daniel Lezcano <[email protected]> AuthorDate: Mon, 27 May 2019 22:55:20 +0200 Committer: Thomas Gleixner <[email protected]> CommitDate: Wed, 12 Jun 2019 10:47:05 +0200
genirq/timings: Add selftest for irqs circular buffer
After testing the per cpu interrupt circular event, make sure the per interrupt circular buffer usage is correct.
Add tests to validate the interrupt circular buffer.
--- kernel/irq/timings.c | 139 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 139 insertions(+)
kernel/irq/timings.c +139 -0
@@ -629,6 +629,141 @@ int irq_timings_alloc(int irq) }#ifdef CONFIG_TEST_IRQ_TIMINGS +struct timings_intervals { +u64 *intervals; +size_t count; +}; + +/* +* Intervals are given in nanosecond base +*/ +static u64 intervals0[]__initdata = { +10000 ,50000 ,200000 ,500000 , +10000 ,50000 ,200000 ,500000 , +10000 ,50000 ,200000 ,500000 , +10000 ,50000 ,200000 ,500000 , +10000 ,50000 ,200000 ,500000 , +10000 ,50000 ,200000 ,500000 , +10000 ,50000 ,200000 ,500000 , +10000 ,50000 ,200000 ,500000 , +10000 ,50000 ,200000 , +}; + +static u64 intervals1[]__initdata = { +223947000 ,1240000 ,1384000 ,1386000 ,1386000 , +217416000 ,1236000 ,1384000 ,1386000 ,1387000 , +214719000 ,1241000 ,1386000 ,1387000 ,1384000 , +213696000 ,1234000 ,1384000 ,1386000 ,1388000 , +219904000 ,1240000 ,1385000 ,1389000 ,1385000 , +212240000 ,1240000 ,1386000 ,1386000 ,1386000 , +214415000 ,1236000 ,1384000 ,1386000 ,1387000 , +214276000 ,1234000 , +}; + +static u64 intervals2[]__initdata = { +4000 ,3000 ,5000 ,100000 , +3000 ,3000 ,5000 ,117000 , +4000 ,4000 ,5000 ,112000 , +4000 ,3000 ,4000 ,110000 , +3000 ,5000 ,3000 ,117000 , +4000 ,4000 ,5000 ,112000 , +4000 ,3000 ,4000 ,110000 , +3000 ,4000 ,5000 ,112000 , +4000 , +}; + +static u64 intervals3[]__initdata = { +1385000 ,212240000 ,1240000 , +1386000 ,214415000 ,1236000 , +1384000 ,214276000 ,1234000 , +1386000 ,214415000 ,1236000 , +1385000 ,212240000 ,1240000 , +1386000 ,214415000 ,1236000 , +1384000 ,214276000 ,1234000 , +1386000 ,214415000 ,1236000 , +1385000 ,212240000 ,1240000 , +}; + +static u64 intervals4[]__initdata = { +10000 ,50000 ,10000 ,50000 , +10000 ,50000 ,10000 ,50000 , +10000 ,50000 ,10000 ,50000 , +10000 ,50000 ,10000 ,50000 , +10000 ,50000 ,10000 ,50000 , +10000 ,50000 ,10000 ,50000 , +10000 ,50000 ,10000 ,50000 , +10000 ,50000 ,10000 ,50000 , +10000 , +}; + +static struct timings_intervals tis[]__initdata = { + { intervals0,ARRAY_SIZE (intervals0) }, + { intervals1,ARRAY_SIZE (intervals1) }, + { intervals2,ARRAY_SIZE (intervals2) }, + { intervals3,ARRAY_SIZE (intervals3) }, + { intervals4,ARRAY_SIZE (intervals4) }, +}; + +static int __init irq_timings_test_irqs (struct timings_intervals *ti) +{ +struct irqt_stat __percpu *s; +struct irqt_stat *irqs; +int i, index, ret, irq =0xACE5 ; + + ret =irq_timings_alloc (irq); +if (ret) { +pr_err ("Failed to allocate irq timings\n" ); +return ret; + } + + s =idr_find (&irqt_stats, irq); +if (!s) { + ret = -EIDRM ; + goto out; + } + + irqs =this_cpu_ptr (s); + +for (i =0 ; i < ti->count; i++) { + + index =irq_timings_interval_index (ti->intervals[i]); +pr_debug ("%d: interval=%llu ema_index=%d\n" , + i, ti->intervals[i], index); + +__irq_timings_store (irq, irqs, ti->intervals[i]); +if (irqs->circ_timings[i &IRQ_TIMINGS_MASK ] != index) { +pr_err ("Failed to store in the circular buffer\n" ); + goto out; + } + } + +if (irqs->count != ti->count) { +pr_err ("Count differs\n" ); + goto out; + } + + ret =0 ; +out: +irq_timings_free (irq); + +return ret; +} + +static int __init irq_timings_irqs_selftest (void ) +{ +int i, ret; + +for (i =0 ; i <ARRAY_SIZE (tis); i++) { +pr_info ("---> Injecting intervals number #%d (count=%zd)\n" , + i, tis[i].count); + ret =irq_timings_test_irqs (&tis[i]); +if (ret) +break ; + } + +return ret; +} +static int __init irq_timings_test_irqts (struct irq_timings *irqts,unsigned count) {
@@ -736,7 +871,11 @@ static int __init irq_timings_selftest(void) } ret =irq_timings_irqts_selftest (); +if (ret) + goto out; + ret =irq_timings_irqs_selftest (); +out:pr_info ("---------- selftest end with %s -----------\n" , ret ?"failure" :"success" );
PATCH v3 8/8 genirq/timings: Add selftest for next event computation
In reply to Daniel LezcanoThe circular buffers are now validated at this point with the two previous patches. The next interrupt index algorithm which is the hardest part to validate can be validated with the tests provided with this patch.
It uses the intervals stored in the arrays and insert all the values except the last one. The next event computation must return the same value as the last element we did not inserted.
Add tests for the next event index computation.
--- kernel/irq/timings.c | 66 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 66 insertions(+)
kernel/irq/timings.c +66 -0
@@ -704,6 +704,68 @@ static struct timings_intervals tis[] __initdata = { { intervals4, ARRAY_SIZE(intervals4) }, }; +static int __init irq_timings_test_next_index (struct timings_intervals *ti) +{ +int _buffer[IRQ_TIMINGS_SIZE ]; +int buffer[IRQ_TIMINGS_SIZE ]; +int index, start, i, count, period_max; + + count = ti->count -1 ; + + period_max = count > (3 *PREDICTION_PERIOD_MAX ) ? +PREDICTION_PERIOD_MAX : count /3 ; + +/* +* Inject all values except the last one which will be used +* to compare with the next index result. +*/ +pr_debug ("index suite: " ); + +for (i =0 ; i < count; i++) { + index =irq_timings_interval_index (ti->intervals[i]); + _buffer[i &IRQ_TIMINGS_MASK ] = index; +pr_cont ("%d " , index); + } + + start = count <IRQ_TIMINGS_SIZE ?0 : + count &IRQ_TIMINGS_MASK ; + + count =min_t (int, count,IRQ_TIMINGS_SIZE ); + +for (i =0 ; i < count; i++) { +int index = (start + i) &IRQ_TIMINGS_MASK ; + buffer[i] = _buffer[index]; + } + + index =irq_timings_next_event_index (buffer, count, period_max); + i =irq_timings_interval_index (ti->intervals[ti->count -1 ]); + +if (index != i) { +pr_err ("Expected (%d) and computed (%d) next indexes differ\n" , + i, index); +return -EINVAL ; + } + +return 0 ; +} + +static int __init irq_timings_next_index_selftest (void ) +{ +int i, ret; + +for (i =0 ; i <ARRAY_SIZE (tis); i++) { + +pr_info ("---> Injecting intervals number #%d (count=%zd)\n" , + i, tis[i].count); + + ret =irq_timings_test_next_index (&tis[i]); +if (ret) +break ; + } + +return ret; +} +static int __init irq_timings_test_irqs (struct timings_intervals *ti) {struct irqt_stat __percpu *s;
@@ -875,6 +937,10 @@ static int __init irq_timings_selftest(void) goto out; ret =irq_timings_irqs_selftest (); +if (ret) + goto out; + + ret =irq_timings_next_index_selftest (); out:pr_info ("---------- selftest end with %s -----------\n" , ret ?"failure" :"success" );
Signature · 1 line
2.17.1
tip-bot for Daniel Lezcano
merge bot[tip:irq/core] genirq/timings: Add selftest for next event computation
genirq/timings: Add selftest for next event computation
Commit-ID: 699785f5d898965408430e841d10cd1cb2c02a77 Gitweb: https://git.kernel.org/tip/699785f5d898965408430e841d10cd1cb2c02a77 Author: Daniel Lezcano <[email protected]> AuthorDate: Mon, 27 May 2019 22:55:21 +0200 Committer: Thomas Gleixner <[email protected]> CommitDate: Wed, 12 Jun 2019 10:47:05 +0200
genirq/timings: Add selftest for next event computation
The circular buffers are now validated with selftests. The next interrupt index algorithm which is the hardest part to validate needs extra coverage.
Add a selftest which uses the intervals stored in the arrays and insert all the values except the last one. The next event computation must return the same value as the last element which was not inserted.
--- kernel/irq/timings.c | 66 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 66 insertions(+)
kernel/irq/timings.c +66 -0
@@ -704,6 +704,68 @@ static struct timings_intervals tis[] __initdata = { { intervals4, ARRAY_SIZE(intervals4) }, }; +static int __init irq_timings_test_next_index (struct timings_intervals *ti) +{ +int _buffer[IRQ_TIMINGS_SIZE ]; +int buffer[IRQ_TIMINGS_SIZE ]; +int index, start, i, count, period_max; + + count = ti->count -1 ; + + period_max = count > (3 *PREDICTION_PERIOD_MAX ) ? +PREDICTION_PERIOD_MAX : count /3 ; + +/* +* Inject all values except the last one which will be used +* to compare with the next index result. +*/ +pr_debug ("index suite: " ); + +for (i =0 ; i < count; i++) { + index =irq_timings_interval_index (ti->intervals[i]); + _buffer[i &IRQ_TIMINGS_MASK ] = index; +pr_cont ("%d " , index); + } + + start = count <IRQ_TIMINGS_SIZE ?0 : + count &IRQ_TIMINGS_MASK ; + + count =min_t (int, count,IRQ_TIMINGS_SIZE ); + +for (i =0 ; i < count; i++) { +int index = (start + i) &IRQ_TIMINGS_MASK ; + buffer[i] = _buffer[index]; + } + + index =irq_timings_next_event_index (buffer, count, period_max); + i =irq_timings_interval_index (ti->intervals[ti->count -1 ]); + +if (index != i) { +pr_err ("Expected (%d) and computed (%d) next indexes differ\n" , + i, index); +return -EINVAL ; + } + +return 0 ; +} + +static int __init irq_timings_next_index_selftest (void ) +{ +int i, ret; + +for (i =0 ; i <ARRAY_SIZE (tis); i++) { + +pr_info ("---> Injecting intervals number #%d (count=%zd)\n" , + i, tis[i].count); + + ret =irq_timings_test_next_index (&tis[i]); +if (ret) +break ; + } + +return ret; +} +static int __init irq_timings_test_irqs (struct timings_intervals *ti) {struct irqt_stat __percpu *s;
@@ -875,6 +937,10 @@ static int __init irq_timings_selftest(void) goto out; ret =irq_timings_irqs_selftest (); +if (ret) + goto out; + + ret =irq_timings_next_index_selftest (); out:pr_info ("---------- selftest end with %s -----------\n" , ret ?"failure" :"success" );
Hi,
is it possible to consider this series for merging?
Thanks in advance
-- Daniel
Quoted 46 lines · Daniel Lezcano
This series provides a couple of fixes, an optimization and the code to do the selftests.
While writing the selftests, a couple of issues were spotted with the circular buffer handling and the routine searching for the pattern multiple times.
In addition, a small optimization has been found while investigating the bugs above.
In order to write the selftest, the routine needed by the core code and the tests are wrapped into function which are always inline so the current code is not impacted by a new function call. There is no functional changes in this part.
Finally, the selftest uses samples to insert values in the arrays and use them to predict the next event. These tests cover the most difficult part of the code.
Changelog:
V3:
- Removed patch using the min macro
- Fixed comment typos in patch 1/8
V2:
- Removed defaulting to 'n' as it is already the case*** BLURB HERE ***
Daniel Lezcano (8):
genirq/timings: Fix next event index function genirq/timings: Fix timings buffer inspection genirq/timings: Optimize the period detection speed genirq/timings: Encapsulate timings push genirq/timings: Encapsulate storing function genirq/timings: Add selftest for circular array genirq/timings: Add selftest for irqs circular buffer genirq/timings: Add selftest for next event computationkernel/irq/Makefile | 3 + kernel/irq/internals.h | 21 +- kernel/irq/timings.c | 453 +++++++++++++++++++++++++++++++++++++---- lib/Kconfig.debug | 8 + 4 files changed, 442 insertions(+), 43 deletions(-)
Signature · 5 lines
<http://www.linaro.org/> Linaro.org │ Open source software for ARM SoCs Follow Linaro: <http://www.facebook.com/pages/Linaro> Facebook | <http://twitter.com/#!/linaroorg> Twitter | <http://www.linaro.org/linaro-blog/> Blog