eas-dev

eas-dev@lists.linaro.org

310 discussions

[PATCH RFC] sched/fair: let cpu's cfs_rq to reflect task migration

by Leo Yan

When task is migrated from CPU_A to CPU_B, scheduler will decrease the task's load/util from the task's cfs_rq and also add them into migrated cfs_rq. But if kernel enables CONFIG_FAIR_GROUP_SCHED then this cfs_rq is not the same one with cpu's cfs_rq. As a result, after task is migrated to CPU_B, then CPU_A still have task's stale value for load/util; on the other hand CPU_B also cannot reflect new load/util which introduced by the task. So this patch is to operate the task's load/util to cpu's cfs_rq, so finally cpu's cfs_rq can really reflect task's migration. Signed-off-by: Leo Yan <leo.yan(a)linaro.org> --- kernel/sched/fair.c | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+) diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 0fe30e6..10ca1a9 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -2825,12 +2825,24 @@ static inline u64 cfs_rq_clock_task(struct cfs_rq *cfs_rq); static inline int update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq) { struct sched_avg *sa = &cfs_rq->avg; + struct sched_avg *cpu_sa = NULL; int decayed, removed = 0; + int cpu = cpu_of(rq_of(cfs_rq)); + + if (&cpu_rq(cpu)->cfs != cfs_rq) + cpu_sa = &cpu_rq(cpu)->cfs.avg; if (atomic_long_read(&cfs_rq->removed_load_avg)) { s64 r = atomic_long_xchg(&cfs_rq->removed_load_avg, 0); sa->load_avg = max_t(long, sa->load_avg - r, 0); sa->load_sum = max_t(s64, sa->load_sum - r * LOAD_AVG_MAX, 0); + + if (cpu_sa) { + cpu_sa->load_avg = max_t(long, cpu_sa->load_avg - r, 0); + cpu_sa->load_sum = max_t(s64, + cpu_sa->load_sum - r * LOAD_AVG_MAX, 0); + } + removed = 1; } @@ -2838,6 +2850,12 @@ static inline int update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq) long r = atomic_long_xchg(&cfs_rq->removed_util_avg, 0); sa->util_avg = max_t(long, sa->util_avg - r, 0); sa->util_sum = max_t(s32, sa->util_sum - r * LOAD_AVG_MAX, 0); + + if (cpu_sa) { + cpu_sa->util_avg = max_t(long, cpu_sa->util_avg - r, 0); + cpu_sa->util_sum = max_t(s64, + cpu_sa->util_sum - r * LOAD_AVG_MAX, 0); + } } decayed = __update_load_avg(now, cpu_of(rq_of(cfs_rq)), sa, @@ -2896,6 +2914,8 @@ static inline void update_load_avg(struct sched_entity *se, int update_tg) static void attach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) { + int cpu = cpu_of(rq_of(cfs_rq)); + if (!sched_feat(ATTACH_AGE_LOAD)) goto skip_aging; @@ -2919,6 +2939,13 @@ skip_aging: cfs_rq->avg.load_sum += se->avg.load_sum; cfs_rq->avg.util_avg += se->avg.util_avg; cfs_rq->avg.util_sum += se->avg.util_sum; + + if (&cpu_rq(cpu)->cfs != cfs_rq) { + cpu_rq(cpu)->cfs.avg.load_avg += se->avg.load_avg; + cpu_rq(cpu)->cfs.avg.load_sum += se->avg.load_sum; + cpu_rq(cpu)->cfs.avg.util_avg += se->avg.util_avg; + cpu_rq(cpu)->cfs.avg.util_sum += se->avg.util_sum; + } } static void detach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) -- 1.9.1

10 years, 6 months

[PATCH] DEBUG: sched: always use CPU's cfs_rq for load tracking

by Leo Yan

When log CPU's load and utilization, should directly use CPU's cfs_rq for tracking. If use the task's cfs_rq, it may introduce error value by using task_group's cfs_rq but not real CPU's cfs_rq. Signed-off-by: Leo Yan <leo.yan(a)linaro.org> --- kernel/sched/fair.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 6ac9ea3..26f3f2d 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -2825,7 +2825,7 @@ static inline void update_load_avg(struct sched_entity *se, int update_tg) if (entity_is_task(se)) trace_sched_load_avg_task(task_of(se), &se->avg); - trace_sched_load_avg_cpu(cpu, cfs_rq); + trace_sched_load_avg_cpu(cpu, &cpu_rq(cpu)->cfs); } static void attach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) -- 1.9.1

10 years, 6 months

[PATCH] sched/fair: replace return with break if success to find capacity

by Mark Yang

the cap_idx should be set to energy_env->cap_idx, it is used by group_norm_usage() later. Signed-off-by: Mark Yang <mark.yang(a)spreadtrum.com> --- kernel/sched/fair.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 93005c9..ced4a99 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -4617,7 +4617,7 @@ static int find_new_capacity(struct energy_env *eenv, for (idx = 0; idx < sge->nr_cap_states; idx++) { if (sge->cap_states[idx].cap >= util) - return idx; + break; } eenv->cap_idx = idx; -- 2.5.0

10 years, 7 months

[EAS] Report on utilization estimation

by Patrick Bellasi

Hi all, as promised during our meeting last week here is a link to the report I've presented regarding "Task Estimation Utilization": https://docs.google.com/document/d/1f2NpnYUS0ci_sLn4i2IY6ZKrRVOqRNnktI9xnt4… Comment can be added to the document. Patches are still under internal review, we will post the initial proposal as soon as we get them validated. Cheers Patrick -- #include <best/regards.h> Patrick Bellasi

10 years, 7 months

[PATCH] cpufreq_sched: set governor_data before waking up kschedfreq

by Pingbo Wen

Fix null pointer dereference error liked below. This BUG can be easily re-produced by 'monkey --throttle 50' in android 6.0. Unable to handle kernel NULL pointer dereference at virtual address 00000010 [KERN Warning] check backtrace: CPU: 0 PID: 10714 Comm: kschedfreq:0 Tainted: Call trace: [<ffffffc00008b8ac>] dump_backtrace+0x0/0x15c [<ffffffc00008ba18>] show_stack+0x10/0x1c [<ffffffc000b97bf8>] dump_stack+0x74/0xb8 [<ffffffc00036208c>] debug_locks_off+0x4c/0x7c [<ffffffc0000a3450>] oops_enter+0xc/0x28 [<ffffffc00008ba50>] die+0x2c/0x1a4 [<ffffffc000b96588>] __do_kernel_fault.part.5+0x70/0x84 [<ffffffc00009c728>] do_page_fault+0x344/0x348 [<ffffffc00009c7e8>] do_translation_fault+0xbc/0xf0 [<ffffffc0000822b0>] do_mem_abort+0x38/0x9c [<ffffffc000085c50>] el1_da+0x14/0x80 [<ffffffc0000c0168>] kthread+0xd4/0xec Signed-off-by: Pingbo Wen <pingbo.wen(a)linaro.org> --- kernel/sched/cpufreq_sched.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/kernel/sched/cpufreq_sched.c b/kernel/sched/cpufreq_sched.c index e1d208e..93731ef 100644 --- a/kernel/sched/cpufreq_sched.c +++ b/kernel/sched/cpufreq_sched.c @@ -265,6 +265,8 @@ static int cpufreq_sched_policy_init(struct cpufreq_policy *policy) pr_debug("%s: throttle threshold = %u [ns]\n", __func__, gd->throttle_nsec); + policy->governor_data = gd; + if (cpufreq_driver_is_slow()) { cpufreq_driver_slow = true; gd->task = kthread_create(cpufreq_sched_thread, policy, @@ -281,7 +283,6 @@ static int cpufreq_sched_policy_init(struct cpufreq_policy *policy) init_irq_work(&gd->irq_work, cpufreq_sched_irq_work); } - policy->governor_data = gd; set_sched_freq(); return 0; -- 1.9.1

10 years, 8 months

[PATCH 0/4] EASv5: Fix rt-app-31/38/44 Inconsistent Issue

by Leo Yan

This patch series is a following up for EASv5 power profiling on Hikey. >From profiling result, rt-app-31/38/44 are inconsistent; Finally found this issue can be fixed by these 4 patches. After applied these patch, we can get good improvement for these cases (mW): Energy BestComb Mainline(ndm) noEAS(ndm) EAS(ndm) EAS(sched) EAS(Applied Patches) mp3 412 604.41 551.79 528.99 530.20 491.10 rt-app-6 676 864.18 846.72 792.88 840.33 759.96 rt-app-13 968 1222.47 1210.35 1673.04 1332.13 1253.99 rt-app-19 1348 1412.08 1474.86 1612.12 1421.28 1355.49 rt-app-25 1619 1718.67 1710.73 2104.41 2028.25 1584.25 rt-app-31 1878 1968.08 1965.87 2318.11 2976.59 1903.69 rt-app-38 2283 2580.23 2540.45 2576.46 2724.32 2241.29 rt-app-44 2578 3092.66 3056.92 2913.91 2669.91 2406.45 rt-app-50 2848 3492.36 3423.26 3489.14 3429.41 3290.25 This patch series is ONLY for EXPERIMENTAL purpose. Leo Yan (4): sched/fair: EASv5: Fix CPU shared capacity issue sched/fair: EASv5: snapshot CPU's utilization sched/fair: EASv5: Add CPU's total utilization sched/fair: EASv5: update new capacity index kernel/sched/fair.c | 88 +++++++++++++++++++++++++++++++++++++++++++--------- kernel/sched/sched.h | 1 + 2 files changed, 74 insertions(+), 15 deletions(-) -- 1.9.1

10 years, 9 months

[Question] EAS: Spread Tasks With Lower OPP

by Leo Yan

Hi all, At connect, Steve also brought out related questions: pack tasks with higher OPP or spread tasks with lower OPP? so I'd like to summary this and combind with recently profiling result: - When task_A is waken up, then scheduler need decide it should pack task_A onto a busy CPU, or scheduler need spread task_A to a idle CPU. If pack task_A onto one busy CPU, this will introduce possible power penalty caused by higher OPP; on the other hand, if spread task_A to a idle CPU (The idle CPU's cluster may also stay in idle state), then this will introduce power penalty caused by extra power domain. So I think we can enhance energy calculation algorithm when wake up the task in function energy_aware_wake_cpu(). For example, we can select two candidate CPUs for waken up task, one possible CPU is in the same schedule group with the task's original CPU, and another possible CPU is in another schedule group (this schedule group should have best or equal power efficiency in system). Then finally we can get to know if need spread tasks to different cluster, or need spread task to different CPU but in the same cluster, or just stay on original CPU. - I also observed here have another possible scenario. For example, if tasks have been already packed to several CPUs, and though every task's workload is not quite high (such like rt-app-13) but they accumulate load on one CPU, so finally CPU will run at high OPP. So if EAS pick up only one of these tasks and try to migrate the task to another CPU, usually will not migrate to that CPU. The reason is even target CPU have run at high OPP, but usually it still have capacity to run more workloads with highest OPP; so energy_diff() also will get worse power result after increase OPP, and task will stay on original CPU. [1][2] Even if pick one idle CPU from another cluster, still cannot resolve this issue. Because if spread task to another cluster, the original cluster and CPU's OPP will not decrease but introduce extra power by the new cluster and CPU. So in this case, should consider as a global view and define some criteria: * CPUs don't stay on lowest OPP, but system have idle CPUs; * CPU's lower OPP can meet capacity requirement for all task's average load; * CPU's lower OPP can meet capacity requirement for the highest load task in system. If meet these criteria, EAS can select idle CPU from schedule group with best power efficiency. I think you guys may have discussed this topic yet, so before I start to try with these ideas, want to check if I missed some discussion and welcom any suggestion. [1] http://people.linaro.org/~leo.yan/eas_profiling/eas_tasks_in_one_cluster_hi… [2] http://people.linaro.org/~leo.yan/eas_profiling/eas_tasks_in_one_cluster_en… Thanks, Leo Yan

10 years, 9 months

[PATCH] rt-app: Fix compilation warnings

by Daniel Lezcano

Fix the following compilation warnings: rt-app_utils.c: In function ‘gettid’: rt-app_utils.c:150:9: warning: implicit declaration of function ‘syscall’ [-Wimplicit-function-declaration] return syscall(__NR_gettid); ^ rt-app_utils.c: In function ‘ftrace_write’: rt-app_utils.c:277:4: warning: implicit declaration of function ‘write’ [-Wimplicit-function-declaration] write(mark_fd, tmp, n); ^ mv -f .deps/rt-app_utils.Tpo .deps/rt-app_utils.Po gcc -DHAVE_CONFIG_H -I. -I./../libdl/ -g -O2 -MT rt-app_args.o -MD -MP -MF .deps/rt-app_args.Tpo -c -o rt-app_args.o rt-app_args.c rt-app_args.c: In function ‘parse_command_line’: rt-app_args.c:44:3: warning: implicit declaration of function ‘parse_config’ [-Wimplicit-function-declaration] parse_config(argv[1], opts); ^ rt-app_args.c:47:3: warning: implicit declaration of function ‘parse_config_stdin’ [-Wimplicit-function-declaration] parse_config_stdin(opts); ^ mv -f .deps/rt-app_args.Tpo .deps/rt-app_args.Po gcc -DHAVE_CONFIG_H -I. -I./../libdl/ -g -O2 -MT rt-app.o -MD -MP -MF .deps/rt-app.Tpo -c -o rt-app.o rt-app.c rt-app.c:173:15: warning: return type defaults to ‘int’ [-Wimplicit-int] static inline loadwait(unsigned long exec) ^ rt-app.c: In function ‘ioload’: rt-app.c:195:9: warning: implicit declaration of function ‘write’ [-Wimplicit-function-declaration] ret = write(io_fd, iomem->ptr, size); ^ rt-app.c: In function ‘run’: rt-app.c:340:4: warning: ‘return’ with no value, in function returning non-void return; ^ rt-app.c: In function ‘shutdown’: rt-app.c:381:3: warning: implicit declaration of function ‘close’ [-Wimplicit-function-declaration] close(ft_data.trace_fd); ^ rt-app.c: In function ‘main’: rt-app.c:848:3: warning: implicit declaration of function ‘sleep’ [-Wimplicit-function-declaration] sleep(opts.duration); Signed-off-by: Daniel Lezcano <daniel.lezcano(a)linaro.org> --- src/rt-app.c | 5 +++-- src/rt-app_args.c | 1 + src/rt-app_parse_config.h | 2 ++ src/rt-app_utils.c | 2 +- 4 files changed, 7 insertions(+), 3 deletions(-) diff --git a/src/rt-app.c b/src/rt-app.c index fef12d8..c3e5df4 100644 --- a/src/rt-app.c +++ b/src/rt-app.c @@ -21,6 +21,7 @@ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. #define _GNU_SOURCE #include <fcntl.h> +#include <unistd.h> #include "rt-app.h" #include "rt-app_utils.h" #include <sched.h> @@ -170,7 +171,7 @@ int calibrate_cpu_cycles(int clock) } -static inline loadwait(unsigned long exec) +static inline unsigned long loadwait(unsigned long exec) { unsigned long load_count; @@ -337,7 +338,7 @@ int run(int ind, event_data_t *events, for (i = 0; i < nbevents; i++) { if (!continue_running && !lock) - return; + return 0; log_debug("[%d] runs events %d type %d ", ind, i, events[i].type); if (opts.ftrace) diff --git a/src/rt-app_args.c b/src/rt-app_args.c index e16415d..c4d56de 100644 --- a/src/rt-app_args.c +++ b/src/rt-app_args.c @@ -19,6 +19,7 @@ along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ +#include "rt-app_parse_config.h" #include "rt-app_args.h" void diff --git a/src/rt-app_parse_config.h b/src/rt-app_parse_config.h index 023cabd..9b0e5fa 100644 --- a/src/rt-app_parse_config.h +++ b/src/rt-app_parse_config.h @@ -45,5 +45,7 @@ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. void parse_config(const char *filename, rtapp_options_t *opts); +void +parse_config_stdin(rtapp_options_t *opts); #endif // _RTAPP_PARSE_CONFIG_H diff --git a/src/rt-app_utils.c b/src/rt-app_utils.c index c4840db..190affc 100644 --- a/src/rt-app_utils.c +++ b/src/rt-app_utils.c @@ -18,7 +18,7 @@ You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ - +#include <unistd.h> #include "rt-app_utils.h" unsigned long -- 1.9.1

10 years, 10 months

[PATCH 1/3] irq: Add a framework to measure interrupt timings

by Daniel Lezcano

The interrupt framework gives a lot of information and statistics about each interrupt (time accounting, statistics, ...). Unfortunately there is no way to measure when interrupts occur and provide a mathematical model for their behavior which could help in predicting their next occurence. This framework allows for registering a callback function that is invoked when an interrupt occurs. Each time an interrupt occurs, the callback will be called with the interval corresponding to the duration between two interrupts. This framework allows a subsystem to register a handler in order to receive the timing information for the registered interrupt. That gives other subsystems the ability to compute predictions for the next interrupt occurence. The main objective is to track and detect the periodic interrupts in order to predict the next event on a cpu and anticipate the sleeping time when entering idle. This fine grain approach allows to simplify and rationalize a wake up event prediction without IPIs interference, thus letting the scheduler to be smarter with the wakeup IPIs regarding the idle period. The irq timings tracking showed, in the proof-of-concept, an improvement with the predictions, the approach is correct but my knowledge to the irq subsystem is limited. I am not sure this patch measuring irq time interval is correct or acceptable, so it is at the RFC state (minus some polishing). Signed-off-by: Daniel Lezcano <daniel.lezcano(a)linaro.org> --- include/linux/interrupt.h | 45 ++++++++++++++++++++++++++++++++ include/linux/irqdesc.h | 3 +++ kernel/irq/Kconfig | 4 +++ kernel/irq/handle.c | 12 +++++++++ kernel/irq/manage.c | 65 ++++++++++++++++++++++++++++++++++++++++++++++- 5 files changed, 128 insertions(+), 1 deletion(-) diff --git a/include/linux/interrupt.h b/include/linux/interrupt.h index be7e75c..f48e8ff 100644 --- a/include/linux/interrupt.h +++ b/include/linux/interrupt.h @@ -123,6 +123,51 @@ struct irqaction { extern irqreturn_t no_action(int cpl, void *dev_id); +#ifdef CONFIG_IRQ_TIMINGS +/** + * timing handler to be called when an interrupt happens + */ +typedef void (*irqt_handler_t)(unsigned int, ktime_t, void *, void *); + +/** + * struct irqtimings - per interrupt irq timings descriptor + * @handler: interrupt handler timings function + * @data: pointer to the private data to be passed to the handler + * @timestamp: latest interruption occurence + */ +struct irqtimings { + irqt_handler_t handler; + void *data; +} ____cacheline_internodealigned_in_smp; + +/** + * struct irqt_ops - structure to be used by the subsystem to call the + * register and unregister ops when an irq is setup or freed. + * @setup: registering callback + * @free: unregistering callback + * + * The callbacks assumes the lock is held on the irq desc + */ +struct irqtimings_ops { + int (*setup)(unsigned int, struct irqaction *); + void (*free)(unsigned int, void *); +}; + +extern int register_irq_timings(struct irqtimings_ops *ops); +extern int setup_irq_timings(unsigned int irq, struct irqaction *act); +extern void free_irq_timings(unsigned int irq, void *dev_id); +#else +static inline int setup_irq_timings(unsigned int irq, struct irqaction *act) +{ + return 0; +} + +static inline void free_irq_timings(unsigned int irq, void *dev_id) +{ + ; +} +#endif + extern int __must_check request_threaded_irq(unsigned int irq, irq_handler_t handler, irq_handler_t thread_fn, diff --git a/include/linux/irqdesc.h b/include/linux/irqdesc.h index a587a33..e0d4263 100644 --- a/include/linux/irqdesc.h +++ b/include/linux/irqdesc.h @@ -51,6 +51,9 @@ struct irq_desc { #ifdef CONFIG_IRQ_PREFLOW_FASTEOI irq_preflow_handler_t preflow_handler; #endif +#ifdef CONFIG_IRQ_TIMINGS + struct irqtimings *timings; +#endif struct irqaction *action; /* IRQ action list */ unsigned int status_use_accessors; unsigned int core_internal_state__do_not_mess_with_it; diff --git a/kernel/irq/Kconfig b/kernel/irq/Kconfig index 9a76e3b..1275fd1 100644 --- a/kernel/irq/Kconfig +++ b/kernel/irq/Kconfig @@ -73,6 +73,10 @@ config GENERIC_MSI_IRQ_DOMAIN config HANDLE_DOMAIN_IRQ bool +config IRQ_TIMINGS + bool + default y + config IRQ_DOMAIN_DEBUG bool "Expose hardware/virtual IRQ mapping via debugfs" depends on IRQ_DOMAIN && DEBUG_FS diff --git a/kernel/irq/handle.c b/kernel/irq/handle.c index e25a83b..ca8b0c5 100644 --- a/kernel/irq/handle.c +++ b/kernel/irq/handle.c @@ -132,6 +132,17 @@ void __irq_wake_thread(struct irq_desc *desc, struct irqaction *action) wake_up_process(action->thread); } +#ifdef CONFIG_IRQ_TIMINGS +void handle_irqt_event(struct irqtimings *irqt, struct irqaction *action) +{ + if (irqt) + irqt->handler(action->irq, ktime_get(), + action->dev_id, irqt->data); +} +#else +#define handle_irqt_event(a, b) +#endif + irqreturn_t handle_irq_event_percpu(struct irq_desc *desc, struct irqaction *action) { @@ -165,6 +176,7 @@ handle_irq_event_percpu(struct irq_desc *desc, struct irqaction *action) /* Fall through to add to randomness */ case IRQ_HANDLED: flags |= action->flags; + handle_irqt_event(desc->timings, action); break; default: diff --git a/kernel/irq/manage.c b/kernel/irq/manage.c index f9a59f6..21cc7bf 100644 --- a/kernel/irq/manage.c +++ b/kernel/irq/manage.c @@ -1017,6 +1017,60 @@ static void irq_release_resources(struct irq_desc *desc) c->irq_release_resources(d); } +#ifdef CONFIG_IRQ_TIMINGS +/* + * Global variable, only used by accessor functions, currently only + * one user is allowed and it is up to the caller to make sure to + * setup the irq timings which are already setup. + */ +static struct irqtimings_ops *irqtimings_ops; + +/** + * register_irq_timings - register the ops when an irq is setup or freed + * + * @ops: the register/unregister ops to be called when at setup or + * free time + * + * Returns -EBUSY if the slot is already in use, zero on success. + */ +int register_irq_timings(struct irqtimings_ops *ops) +{ + if (irqtimings_ops) + return -EBUSY; + + irqtimings_ops = ops; + + return 0; +} + +/** + * setup_irq_timings - call the timing register callback + * + * @desc: an irq desc structure + * + * Returns -EINVAL in case of error, zero on success. + */ +int setup_irq_timings(unsigned int irq, struct irqaction *act) +{ + if (irqtimings_ops && irqtimings_ops->setup) + return irqtimings_ops->setup(irq, act); + return 0; +} + +/** + * free_irq_timings - call the timing unregister callback + * + * @irq: the interrupt number + * @dev_id: the device id + * + */ +void free_irq_timings(unsigned int irq, void *dev_id) +{ + if (irqtimings_ops && irqtimings_ops->free) + irqtimings_ops->free(irq, dev_id); +} +#endif /* CONFIG_IRQ_TIMINGS */ + /* * Internal function to register an irqaction - typically used to * allocate special interrupts that are part of the architecture. @@ -1037,6 +1091,9 @@ __setup_irq(unsigned int irq, struct irq_desc *desc, struct irqaction *new) if (!try_module_get(desc->owner)) return -ENODEV; + ret = setup_irq_timings(irq, new); + if (ret) + goto out_mput; /* * Check whether the interrupt nests into another interrupt * thread. @@ -1045,7 +1102,7 @@ __setup_irq(unsigned int irq, struct irq_desc *desc, struct irqaction *new) if (nested) { if (!new->thread_fn) { ret = -EINVAL; - goto out_mput; + goto out_free_timings; } /* * Replace the primary handler which was provided from @@ -1323,6 +1380,10 @@ out_thread: kthread_stop(t); put_task_struct(t); } + +out_free_timings: + free_irq_timings(irq, new->dev_id); + out_mput: module_put(desc->owner); return ret; @@ -1408,6 +1469,8 @@ static struct irqaction *__free_irq(unsigned int irq, void *dev_id) unregister_handler_proc(irq, action); + free_irq_timings(irq, dev_id); + /* Make sure it's not being used on another CPU: */ synchronize_irq(irq); -- 1.9.1

10 years, 10 months

[PATCH 01/10] lib: Add a simple statistics library

by Daniel Lezcano

It is usually interesting to do some statistics on a set of data, especially when the values are coming in a stream (measured time by time for instance). Instead of having the statistics formula inside a specific subsystem, this small library provides the basic statistics functions available for all the kernel. The library is designed to do the minimum computation when a new value is added. Only the basic value storage, array shifting and accumulation is done. The average, variance and standard deviation is computed when requested via the corresponding functions. The statistic library can deal up to 65536 values in the range of -2^24 and 2^24 - 1. These are large values and does not really make sense to the kernel code to use the statistics at these limits, so it is up to developer to use wisely the library. Signed-off-by: Daniel Lezcano <daniel.lezcano(a)linaro.org> --- include/linux/stats.h | 29 +++++++ lib/Makefile | 3 +- lib/stats.c | 235 ++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 266 insertions(+), 1 deletion(-) create mode 100644 include/linux/stats.h create mode 100644 lib/stats.c diff --git a/include/linux/stats.h b/include/linux/stats.h new file mode 100644 index 0000000..664eb30 --- /dev/null +++ b/include/linux/stats.h @@ -0,0 +1,29 @@ +/* + * include/linux/stats.h + */ +#ifndef _LINUX_STATS_H +#define _LINUX_STATS_H + +struct stats { + s64 sum; /* sum of values */ + u64 sq_sum; /* sum of the square values */ + s32 *values; /* array of values */ + s32 min; /* minimal value of the entire series */ + s32 max; /* maximal value of the entire series */ + unsigned int n; /* current number of values */ + unsigned int w_ptr; /* current window pointer */ + unsigned short len; /* size of the value array */ +}; + +extern s32 stats_max(struct stats *s); +extern s32 stats_min(struct stats *s); +extern s32 stats_mean(struct stats *s); +extern u32 stats_variance(struct stats *s); +extern u32 stats_stddev(struct stats *s); +extern void stats_add(struct stats *s, s32 val); +extern void stats_reset(struct stats *s); +extern void stats_free(struct stats *s); +extern struct stats *stats_alloc(unsigned short len); +extern unsigned short stats_n(struct stats *s); + +#endif /* _LINUX_STATS_H */ diff --git a/lib/Makefile b/lib/Makefile index 13a7c6a..18460d2 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -26,7 +26,8 @@ obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \ bust_spinlocks.o kasprintf.o bitmap.o scatterlist.o \ gcd.o lcm.o list_sort.o uuid.o flex_array.o iov_iter.o clz_ctz.o \ bsearch.o find_bit.o llist.o memweight.o kfifo.o \ - percpu-refcount.o percpu_ida.o rhashtable.o reciprocal_div.o + percpu-refcount.o percpu_ida.o rhashtable.o reciprocal_div.o \ + stats.o obj-y += string_helpers.o obj-$(CONFIG_TEST_STRING_HELPERS) += test-string_helpers.o obj-y += hexdump.o diff --git a/lib/stats.c b/lib/stats.c new file mode 100644 index 0000000..f5425d1 --- /dev/null +++ b/lib/stats.c @@ -0,0 +1,235 @@ +/* + * Implementation of basics statistics functions useful to compute on + * a stream of data. + * + * Copyright: (C) 2015-2016 Linaro Limited + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + */ +#include <linux/export.h> +#include <linux/kernel.h> +#include <linux/slab.h> +#include <linux/stats.h> +#include <linux/types.h> + +/** + * stats_n - number of elements present in the statistics + * + * @s: the statistic structure + * + * Returns an unsigned short representing the number of values in the + * statistics series + */ +unsigned short stats_n(struct stats *s) +{ + return s->n; +} + +/** + * stats_max - maximal value of the series + * + * @s: the statistic structure + * + * Returns a s32 representing the maximum value of the series + */ +s32 stats_max(struct stats *s) +{ + return s->max; +} +EXPORT_SYMBOL_GPL(stats_max); + +/** + * stats_min - minimal value of the series + * + * @s: the statistic structure + * + * Returns a s32 representing the minimal value of the series + */ +s32 stats_min(struct stats *s) +{ + return s->min; +} +EXPORT_SYMBOL_GPL(stats_min); + +/** + * stats_mean - compute the average + * + * @s: the statistics structure + * + * Returns an s32 corresponding to the mean value, or zero if there is + * no data + */ +s32 stats_mean(struct stats *s) +{ + return s->n ? s->sum / s->n : 0; +} +EXPORT_SYMBOL_GPL(stats_mean); + +/** + * stats_variance - compute the variance + * + * @s: the statistic structure + * + * Returns an u32 corresponding to the variance, or zero if there is no + * data + */ +u32 stats_variance(struct stats *s) +{ + s32 mean = stats_mean(s); + return s->n ? (s->sq_sum / s->n) - (mean * mean) : 0; +} +EXPORT_SYMBOL_GPL(stats_variance); + +/** + * stats_stddev - compute the standard deviation + * + * @s: the statistic structure + * + * Returns an u32 corresponding to the standard deviation, or zero if + * there is no data + */ +u32 stats_stddev(struct stats *s) +{ + return int_sqrt(stats_variance(s)); +} +EXPORT_SYMBOL_GPL(stats_stddev); + +/** + * stats_add - add a new value in the statistic structure + * + * @s: the statistic structure + * @value: the new value to be added, max 2^24 - 1 + * + * Adds the value to the array, if the array is full, then the array + * is shifted. + * + */ +void stats_add(struct stats *s, s32 value) +{ + /* + * In order to prevent an overflow in the statistic code, we + * limit the value to 2^24 - 1, if it is greater we just + * ignore it with a WARN_ON_ONCE letting know to userspace we + * are dealing with out-of-range values. + */ + if (WARN_ON_ONCE(value >= ((2<<24) - 1))) + return; + + /* + * Insert the value in the array. If the array is already + * full, shift the values and add the value at the end of the + * series, otherwise add the value directly. + */ + if (likely(s->len == s->n)) { + s->sum -= s->values[s->w_ptr]; + s->sq_sum -= s->values[s->w_ptr] * s->values[s->w_ptr]; + s->values[s->w_ptr] = value; + s->w_ptr = (s->w_ptr + 1) % s->len; + } else { + s->values[s->n] = value; + s->n++; + } + + /* + * Keep track of the min and max. + */ + s->min = min(s->min, value); + s->max = max(s->max, value); + + /* + * In order to reduce the overhead and to prevent value + * derivation due to the integer computation, we just sum the + * value and do the division when the average and the variance + * are requested. + */ + s->sum += value; + s->sq_sum += value * value; +} +EXPORT_SYMBOL_GPL(stats_add); + +/** + * stats_reset - reset the stats + * + * @s: the statistic structure + * + * Reset the statistics and reset the values + * + */ +void stats_reset(struct stats *s) +{ + s->sum = s->sq_sum = s->n = s->w_ptr = 0; + s->max = S32_MIN; + s->min = S32_MAX; +} +EXPORT_SYMBOL_GPL(stats_reset); + +/** + * stats_alloc - allocate a structure for statistics + * + * @len: The number of items in the array which is limited by the + * unsigned short type. That allows to prevent overflow in all + * the statistics code. + * + * Allocates memory to store the different values and initialize the + * structure. + * + * In order to prevent an overflow in the computation, the maximum + * allowed number of values is 65536 and each value max is 2^24 - 1. + * + * The variance is the sum of the square value of the difference of + * each value to the average. The variance is a u64 (square values are + * always positives), so that gives a maximum of 18446744073709551615. + * We can store 65536 values, so: + * + * 18446744073709551615 / 65536 = 281474976710655 + * + * ... is the square max value we can have, hence the difference to + * the mean is max sqrt(281474976710655) = 16777215 (2^24 -1) + * + * Even if these values are not realistics (statistic in the kernel is + * for a few hundred values, large dispersion in the integer limits is + * very very rare so the sum won't be very high, or high integers + * series means low variance), we prevent any overflow in the code and + * we are safe. + * + * Returns a valid pointer a struct stats, NULL if the memory + * allocation fails. + */ +struct stats *stats_alloc(unsigned short len) +{ + struct stats *s; + s32 *values; + + s = kzalloc(sizeof(*s), GFP_KERNEL); + if (s) { + values = kzalloc(sizeof(*values) * len, GFP_KERNEL); + if (!values) { + kfree(s); + return NULL; + } + + s->values = values; + s->len = len; + s->min = S32_MAX; + s->max = S32_MIN; + } + + return s; +} +EXPORT_SYMBOL_GPL(stats_alloc); + +/** + * stats_free - free the statistics structure + * + * @s : the statistics structure + * + * Frees the memory allocated by the function stats_alloc. + */ +void stats_free(struct stats *s) +{ + kfree(s->values); + kfree(s); +} +EXPORT_SYMBOL_GPL(stats_free); -- 1.9.1

10 years, 10 months

← Newer
1
...
24
25
26
27
28
29
30
31
Older →

Jump to page:

2026

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

eas-dev