From 60bda037f1dd8151e0c9ee5b09f0c091a0f643cd Mon Sep 17 00:00:00 2001 From: Thomas Gleixner Date: Tue, 27 Aug 2019 21:31:02 +0200 Subject: posix-cpu-timers: Utilize timerqueue for storage Using a linear O(N) search for timer insertion affects execution time and D-cache footprint badly with a larger number of timers. Switch the storage to a timerqueue which is already used for hrtimers and alarmtimers. It does not affect the size of struct k_itimer as it.alarm is still larger. The extra list head for the expiry list will go away later once the expiry is moved into task work context. Signed-off-by: Thomas Gleixner Reviewed-by: Frederic Weisbecker Link: https://lkml.kernel.org/r/alpine.DEB.2.21.1908272129220.1939@nanos.tec.linutronix.de --- include/linux/posix-timers.h | 65 +++++++++++++++++++++++++++++++++----------- include/linux/timerqueue.h | 10 +++++++ 2 files changed, 59 insertions(+), 16 deletions(-) (limited to 'include/linux') diff --git a/include/linux/posix-timers.h b/include/linux/posix-timers.h index a9e3f69d2db4..f9fbb4c620c1 100644 --- a/include/linux/posix-timers.h +++ b/include/linux/posix-timers.h @@ -5,17 +5,11 @@ #include #include #include +#include struct kernel_siginfo; struct task_struct; -struct cpu_timer_list { - struct list_head entry; - u64 expires; - struct task_struct *task; - int firing; -}; - /* * Bit fields within a clockid: * @@ -64,14 +58,58 @@ static inline int clockid_to_fd(const clockid_t clk) #ifdef CONFIG_POSIX_TIMERS +/** + * cpu_timer - Posix CPU timer representation for k_itimer + * @node: timerqueue node to queue in the task/sig + * @head: timerqueue head on which this timer is queued + * @task: Pointer to target task + * @elist: List head for the expiry list + * @firing: Timer is currently firing + */ +struct cpu_timer { + struct timerqueue_node node; + struct timerqueue_head *head; + struct task_struct *task; + struct list_head elist; + int firing; +}; + +static inline bool cpu_timer_requeue(struct cpu_timer *ctmr) +{ + return timerqueue_add(ctmr->head, &ctmr->node); +} + +static inline bool cpu_timer_enqueue(struct timerqueue_head *head, + struct cpu_timer *ctmr) +{ + ctmr->head = head; + return timerqueue_add(head, &ctmr->node); +} + +static inline void cpu_timer_dequeue(struct cpu_timer *ctmr) +{ + if (!RB_EMPTY_NODE(&ctmr->node.node)) + timerqueue_del(ctmr->head, &ctmr->node); +} + +static inline u64 cpu_timer_getexpires(struct cpu_timer *ctmr) +{ + return ctmr->node.expires; +} + +static inline void cpu_timer_setexpires(struct cpu_timer *ctmr, u64 exp) +{ + ctmr->node.expires = exp; +} + /** * posix_cputimer_base - Container per posix CPU clock * @nextevt: Earliest-expiration cache - * @cpu_timers: List heads to queue posix CPU timers + * @tqhead: timerqueue head for cpu_timers */ struct posix_cputimer_base { u64 nextevt; - struct list_head cpu_timers; + struct timerqueue_head tqhead; }; /** @@ -92,14 +130,10 @@ struct posix_cputimers { static inline void posix_cputimers_init(struct posix_cputimers *pct) { - pct->timers_active = 0; - pct->expiry_active = 0; + memset(pct, 0, sizeof(*pct)); pct->bases[0].nextevt = U64_MAX; pct->bases[1].nextevt = U64_MAX; pct->bases[2].nextevt = U64_MAX; - INIT_LIST_HEAD(&pct->bases[0].cpu_timers); - INIT_LIST_HEAD(&pct->bases[1].cpu_timers); - INIT_LIST_HEAD(&pct->bases[2].cpu_timers); } void posix_cputimers_group_init(struct posix_cputimers *pct, u64 cpu_limit); @@ -113,7 +147,6 @@ static inline void posix_cputimers_rt_watchdog(struct posix_cputimers *pct, /* Init task static initializer */ #define INIT_CPU_TIMERBASE(b) { \ .nextevt = U64_MAX, \ - .cpu_timers = LIST_HEAD_INIT(b.cpu_timers), \ } #define INIT_CPU_TIMERBASES(b) { \ @@ -182,7 +215,7 @@ struct k_itimer { struct { struct hrtimer timer; } real; - struct cpu_timer_list cpu; + struct cpu_timer cpu; struct { struct alarm alarmtimer; } alarm; diff --git a/include/linux/timerqueue.h b/include/linux/timerqueue.h index aff122f1062a..93884086f392 100644 --- a/include/linux/timerqueue.h +++ b/include/linux/timerqueue.h @@ -43,6 +43,16 @@ static inline void timerqueue_init(struct timerqueue_node *node) RB_CLEAR_NODE(&node->node); } +static inline bool timerqueue_node_queued(struct timerqueue_node *node) +{ + return !RB_EMPTY_NODE(&node->node); +} + +static inline bool timerqueue_node_expires(struct timerqueue_node *node) +{ + return node->expires; +} + static inline void timerqueue_init_head(struct timerqueue_head *head) { head->rb_root = RB_ROOT_CACHED; -- cgit v1.2.3