From 4b41308d2d0398409620613c7eaaaf52c738b042 Mon Sep 17 00:00:00 2001 From: John Stultz Date: Wed, 10 Aug 2011 10:37:59 -0700 Subject: alarmtimers: Change alarmtimer functions to return alarmtimer_restart values In order to properly fix the denial of service issue with high freq periodic alarm timers, we need to push the re-arming logic into the alarm timer handler, much as the hrtimer code does. This patch introduces alarmtimer_restart enum and changes the alarmtimer handler declarations to use it as a return value. Further, to ease following changes, it extends the alarmtimer handler functions to also take the time at expiration. No logic is yet modified. CC: Thomas Gleixner Signed-off-by: John Stultz --- include/linux/alarmtimer.h | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) (limited to 'include/linux/alarmtimer.h') diff --git a/include/linux/alarmtimer.h b/include/linux/alarmtimer.h index c5d6095b46f8..0289eb29e794 100644 --- a/include/linux/alarmtimer.h +++ b/include/linux/alarmtimer.h @@ -13,6 +13,11 @@ enum alarmtimer_type { ALARM_NUMTYPE, }; +enum alarmtimer_restart { + ALARMTIMER_NORESTART, + ALARMTIMER_RESTART, +}; + /** * struct alarm - Alarm timer structure * @node: timerqueue node for adding to the event list this value @@ -26,14 +31,14 @@ enum alarmtimer_type { struct alarm { struct timerqueue_node node; ktime_t period; - void (*function)(struct alarm *); + enum alarmtimer_restart (*function)(struct alarm *, ktime_t now); enum alarmtimer_type type; bool enabled; void *data; }; void alarm_init(struct alarm *alarm, enum alarmtimer_type type, - void (*function)(struct alarm *)); + enum alarmtimer_restart (*function)(struct alarm *, ktime_t)); void alarm_start(struct alarm *alarm, ktime_t start, ktime_t period); void alarm_cancel(struct alarm *alarm); -- cgit v1.2.3 From dce75a8c71819ed4c7efdcd53c9b6f6356dc8cb5 Mon Sep 17 00:00:00 2001 From: John Stultz Date: Wed, 10 Aug 2011 11:31:03 -0700 Subject: alarmtimers: Add alarm_forward functionality In order to avoid wasting time expiring and re-adding very high freq periodic alarmtimers, introduce alarm_forward() which is similar to hrtimer_forward and moves the timer to the next future expiration time and returns the number of overruns. CC: Thomas Gleixner Signed-off-by: John Stultz --- include/linux/alarmtimer.h | 2 ++ kernel/time/alarmtimer.c | 37 ++++++++++++++++++++++++++++++++++++- 2 files changed, 38 insertions(+), 1 deletion(-) (limited to 'include/linux/alarmtimer.h') diff --git a/include/linux/alarmtimer.h b/include/linux/alarmtimer.h index 0289eb29e794..17535963b274 100644 --- a/include/linux/alarmtimer.h +++ b/include/linux/alarmtimer.h @@ -42,4 +42,6 @@ void alarm_init(struct alarm *alarm, enum alarmtimer_type type, void alarm_start(struct alarm *alarm, ktime_t start, ktime_t period); void alarm_cancel(struct alarm *alarm); +u64 alarm_forward(struct alarm *alarm, ktime_t now, ktime_t interval); + #endif diff --git a/kernel/time/alarmtimer.c b/kernel/time/alarmtimer.c index 55e634ea6054..f03b04291b6f 100644 --- a/kernel/time/alarmtimer.c +++ b/kernel/time/alarmtimer.c @@ -347,6 +347,41 @@ void alarm_cancel(struct alarm *alarm) } + +u64 alarm_forward(struct alarm *alarm, ktime_t now, ktime_t interval) +{ + u64 overrun = 1; + ktime_t delta; + + delta = ktime_sub(now, alarm->node.expires); + + if (delta.tv64 < 0) + return 0; + + if (unlikely(delta.tv64 >= interval.tv64)) { + s64 incr = ktime_to_ns(interval); + + overrun = ktime_divns(delta, incr); + + alarm->node.expires = ktime_add_ns(alarm->node.expires, + incr*overrun); + + if (alarm->node.expires.tv64 > now.tv64) + return overrun; + /* + * This (and the ktime_add() below) is the + * correction for exact: + */ + overrun++; + } + + alarm->node.expires = ktime_add(alarm->node.expires, interval); + return overrun; +} + + + + /** * clock2alarm - helper that converts from clockid to alarmtypes * @clockid: clockid. @@ -376,7 +411,7 @@ static enum alarmtimer_restart alarm_handle_timer(struct alarm *alarm, /* Re-add periodic timers */ if (alarm->period.tv64) { - alarm->node.expires = ktime_add(now, alarm->period); + ptr->it_overrun += alarm_forward(alarm, now, alarm->period); return ALARMTIMER_RESTART; } return ALARMTIMER_NORESTART; -- cgit v1.2.3 From 9e26476243e438f4534a562660c1296a15a9e202 Mon Sep 17 00:00:00 2001 From: John Stultz Date: Wed, 10 Aug 2011 12:09:24 -0700 Subject: alarmtimers: Remove period from alarm structure Now that periodic alarmtimers are managed by the handler function, remove the period value from the alarm structure and let the handlers manage the interval on their own. CC: Thomas Gleixner Signed-off-by: John Stultz --- include/linux/alarmtimer.h | 3 +-- include/linux/posix-timers.h | 5 ++++- kernel/time/alarmtimer.c | 30 ++++++++++++++---------------- 3 files changed, 19 insertions(+), 19 deletions(-) (limited to 'include/linux/alarmtimer.h') diff --git a/include/linux/alarmtimer.h b/include/linux/alarmtimer.h index 17535963b274..c854a8efa863 100644 --- a/include/linux/alarmtimer.h +++ b/include/linux/alarmtimer.h @@ -30,7 +30,6 @@ enum alarmtimer_restart { */ struct alarm { struct timerqueue_node node; - ktime_t period; enum alarmtimer_restart (*function)(struct alarm *, ktime_t now); enum alarmtimer_type type; bool enabled; @@ -39,7 +38,7 @@ struct alarm { void alarm_init(struct alarm *alarm, enum alarmtimer_type type, enum alarmtimer_restart (*function)(struct alarm *, ktime_t)); -void alarm_start(struct alarm *alarm, ktime_t start, ktime_t period); +void alarm_start(struct alarm *alarm, ktime_t start); void alarm_cancel(struct alarm *alarm); u64 alarm_forward(struct alarm *alarm, ktime_t now, ktime_t interval); diff --git a/include/linux/posix-timers.h b/include/linux/posix-timers.h index 959c14132f46..042058fdb0af 100644 --- a/include/linux/posix-timers.h +++ b/include/linux/posix-timers.h @@ -81,7 +81,10 @@ struct k_itimer { unsigned long incr; unsigned long expires; } mmtimer; - struct alarm alarmtimer; + struct { + struct alarm alarmtimer; + ktime_t interval; + } alarm; struct rcu_head rcu; } it; }; diff --git a/kernel/time/alarmtimer.c b/kernel/time/alarmtimer.c index a522c007e6fd..90935591dd44 100644 --- a/kernel/time/alarmtimer.c +++ b/kernel/time/alarmtimer.c @@ -303,7 +303,6 @@ void alarm_init(struct alarm *alarm, enum alarmtimer_type type, enum alarmtimer_restart (*function)(struct alarm *, ktime_t)) { timerqueue_init(&alarm->node); - alarm->period = ktime_set(0, 0); alarm->function = function; alarm->type = type; alarm->enabled = 0; @@ -313,9 +312,8 @@ void alarm_init(struct alarm *alarm, enum alarmtimer_type type, * alarm_start - Sets an alarm to fire * @alarm: ptr to alarm to set * @start: time to run the alarm - * @period: period at which the alarm will recur */ -void alarm_start(struct alarm *alarm, ktime_t start, ktime_t period) +void alarm_start(struct alarm *alarm, ktime_t start) { struct alarm_base *base = &alarm_bases[alarm->type]; unsigned long flags; @@ -324,7 +322,6 @@ void alarm_start(struct alarm *alarm, ktime_t start, ktime_t period) if (alarm->enabled) alarmtimer_remove(base, alarm); alarm->node.expires = start; - alarm->period = period; alarmtimer_enqueue(base, alarm); alarm->enabled = 1; spin_unlock_irqrestore(&base->lock, flags); @@ -405,13 +402,14 @@ static enum alarmtimer_restart alarm_handle_timer(struct alarm *alarm, ktime_t now) { struct k_itimer *ptr = container_of(alarm, struct k_itimer, - it.alarmtimer); + it.alarm.alarmtimer); if (posix_timer_event(ptr, 0) != 0) ptr->it_overrun++; /* Re-add periodic timers */ - if (alarm->period.tv64) { - ptr->it_overrun += alarm_forward(alarm, now, alarm->period); + if (ptr->it.alarm.interval.tv64) { + ptr->it_overrun += alarm_forward(alarm, now, + ptr->it.alarm.interval); return ALARMTIMER_RESTART; } return ALARMTIMER_NORESTART; @@ -471,7 +469,7 @@ static int alarm_timer_create(struct k_itimer *new_timer) type = clock2alarm(new_timer->it_clock); base = &alarm_bases[type]; - alarm_init(&new_timer->it.alarmtimer, type, alarm_handle_timer); + alarm_init(&new_timer->it.alarm.alarmtimer, type, alarm_handle_timer); return 0; } @@ -488,9 +486,9 @@ static void alarm_timer_get(struct k_itimer *timr, memset(cur_setting, 0, sizeof(struct itimerspec)); cur_setting->it_interval = - ktime_to_timespec(timr->it.alarmtimer.period); + ktime_to_timespec(timr->it.alarm.interval); cur_setting->it_value = - ktime_to_timespec(timr->it.alarmtimer.node.expires); + ktime_to_timespec(timr->it.alarm.alarmtimer.node.expires); return; } @@ -505,7 +503,7 @@ static int alarm_timer_del(struct k_itimer *timr) if (!rtcdev) return -ENOTSUPP; - alarm_cancel(&timr->it.alarmtimer); + alarm_cancel(&timr->it.alarm.alarmtimer); return 0; } @@ -529,12 +527,12 @@ static int alarm_timer_set(struct k_itimer *timr, int flags, alarm_timer_get(timr, old_setting); /* If the timer was already set, cancel it */ - alarm_cancel(&timr->it.alarmtimer); + alarm_cancel(&timr->it.alarm.alarmtimer); /* start the timer */ - alarm_start(&timr->it.alarmtimer, - timespec_to_ktime(new_setting->it_value), - timespec_to_ktime(new_setting->it_interval)); + timr->it.alarm.interval = timespec_to_ktime(new_setting->it_interval); + alarm_start(&timr->it.alarm.alarmtimer, + timespec_to_ktime(new_setting->it_value)); return 0; } @@ -567,7 +565,7 @@ static int alarmtimer_do_nsleep(struct alarm *alarm, ktime_t absexp) alarm->data = (void *)current; do { set_current_state(TASK_INTERRUPTIBLE); - alarm_start(alarm, absexp, ktime_set(0, 0)); + alarm_start(alarm, absexp); if (likely(alarm->data)) schedule(); -- cgit v1.2.3 From a28cde81ab13cc251748a4c4ef06883dd09a10ea Mon Sep 17 00:00:00 2001 From: John Stultz Date: Wed, 10 Aug 2011 12:30:21 -0700 Subject: alarmtimers: Add more refined alarm state tracking In order to allow for functionality like try_to_cancel, add more refined state tracking (similar to hrtimers). CC: Thomas Gleixner Signed-off-by: John Stultz --- include/linux/alarmtimer.h | 34 +++++++++++++++++++++++++++++++++- kernel/time/alarmtimer.c | 21 ++++++++++++++------- 2 files changed, 47 insertions(+), 8 deletions(-) (limited to 'include/linux/alarmtimer.h') diff --git a/include/linux/alarmtimer.h b/include/linux/alarmtimer.h index c854a8efa863..304124a6c982 100644 --- a/include/linux/alarmtimer.h +++ b/include/linux/alarmtimer.h @@ -18,6 +18,11 @@ enum alarmtimer_restart { ALARMTIMER_RESTART, }; + +#define ALARMTIMER_STATE_INACTIVE 0x00 +#define ALARMTIMER_STATE_ENQUEUED 0x01 +#define ALARMTIMER_STATE_CALLBACK 0x02 + /** * struct alarm - Alarm timer structure * @node: timerqueue node for adding to the event list this value @@ -32,7 +37,7 @@ struct alarm { struct timerqueue_node node; enum alarmtimer_restart (*function)(struct alarm *, ktime_t now); enum alarmtimer_type type; - bool enabled; + int state; void *data; }; @@ -43,4 +48,31 @@ void alarm_cancel(struct alarm *alarm); u64 alarm_forward(struct alarm *alarm, ktime_t now, ktime_t interval); +/* + * A alarmtimer is active, when it is enqueued into timerqueue or the + * callback function is running. + */ +static inline int alarmtimer_active(const struct alarm *timer) +{ + return timer->state != ALARMTIMER_STATE_INACTIVE; +} + +/* + * Helper function to check, whether the timer is on one of the queues + */ +static inline int alarmtimer_is_queued(struct alarm *timer) +{ + return timer->state & ALARMTIMER_STATE_ENQUEUED; +} + +/* + * Helper function to check, whether the timer is running the callback + * function + */ +static inline int alarmtimer_callback_running(struct alarm *timer) +{ + return timer->state & ALARMTIMER_STATE_CALLBACK; +} + + #endif diff --git a/kernel/time/alarmtimer.c b/kernel/time/alarmtimer.c index 90935591dd44..5b14cc29b6a6 100644 --- a/kernel/time/alarmtimer.c +++ b/kernel/time/alarmtimer.c @@ -126,6 +126,8 @@ static struct rtc_device *alarmtimer_get_rtcdev(void) static void alarmtimer_enqueue(struct alarm_base *base, struct alarm *alarm) { timerqueue_add(&base->timerqueue, &alarm->node); + alarm->state |= ALARMTIMER_STATE_ENQUEUED; + if (&alarm->node == timerqueue_getnext(&base->timerqueue)) { hrtimer_try_to_cancel(&base->timer); hrtimer_start(&base->timer, alarm->node.expires, @@ -147,7 +149,12 @@ static void alarmtimer_remove(struct alarm_base *base, struct alarm *alarm) { struct timerqueue_node *next = timerqueue_getnext(&base->timerqueue); + if (!(alarm->state & ALARMTIMER_STATE_ENQUEUED)) + return; + timerqueue_del(&base->timerqueue, &alarm->node); + alarm->state &= ~ALARMTIMER_STATE_ENQUEUED; + if (next == &alarm->node) { hrtimer_try_to_cancel(&base->timer); next = timerqueue_getnext(&base->timerqueue); @@ -188,16 +195,18 @@ static enum hrtimer_restart alarmtimer_fired(struct hrtimer *timer) alarm = container_of(next, struct alarm, node); timerqueue_del(&base->timerqueue, &alarm->node); - alarm->enabled = 0; + alarm->state &= ~ALARMTIMER_STATE_ENQUEUED; + alarm->state |= ALARMTIMER_STATE_CALLBACK; spin_unlock_irqrestore(&base->lock, flags); if (alarm->function) restart = alarm->function(alarm, now); spin_lock_irqsave(&base->lock, flags); + alarm->state &= ~ALARMTIMER_STATE_CALLBACK; if (restart != ALARMTIMER_NORESTART) { timerqueue_add(&base->timerqueue, &alarm->node); - alarm->enabled = 1; + alarm->state |= ALARMTIMER_STATE_ENQUEUED; } } @@ -305,7 +314,7 @@ void alarm_init(struct alarm *alarm, enum alarmtimer_type type, timerqueue_init(&alarm->node); alarm->function = function; alarm->type = type; - alarm->enabled = 0; + alarm->state = ALARMTIMER_STATE_INACTIVE; } /** @@ -319,11 +328,10 @@ void alarm_start(struct alarm *alarm, ktime_t start) unsigned long flags; spin_lock_irqsave(&base->lock, flags); - if (alarm->enabled) + if (alarmtimer_active(alarm)) alarmtimer_remove(base, alarm); alarm->node.expires = start; alarmtimer_enqueue(base, alarm); - alarm->enabled = 1; spin_unlock_irqrestore(&base->lock, flags); } @@ -337,9 +345,8 @@ void alarm_cancel(struct alarm *alarm) unsigned long flags; spin_lock_irqsave(&base->lock, flags); - if (alarm->enabled) + if (alarmtimer_is_queued(alarm)) alarmtimer_remove(base, alarm); - alarm->enabled = 0; spin_unlock_irqrestore(&base->lock, flags); } -- cgit v1.2.3 From 9082c465a5403f4a98734193e078552991a2e283 Mon Sep 17 00:00:00 2001 From: John Stultz Date: Wed, 10 Aug 2011 12:41:36 -0700 Subject: alarmtimers: Add try_to_cancel functionality There's a number of edge cases when cancelling a alarm, so to be sure we accurately do so, introduce try_to_cancel, which returns proper failure errors if it cannot. Also modify cancel to spin until the alarm is properly disabled. CC: Thomas Gleixner Signed-off-by: John Stultz --- include/linux/alarmtimer.h | 3 ++- kernel/time/alarmtimer.c | 43 +++++++++++++++++++++++++++++++++++++------ 2 files changed, 39 insertions(+), 7 deletions(-) (limited to 'include/linux/alarmtimer.h') diff --git a/include/linux/alarmtimer.h b/include/linux/alarmtimer.h index 304124a6c982..975009e1cbe6 100644 --- a/include/linux/alarmtimer.h +++ b/include/linux/alarmtimer.h @@ -44,7 +44,8 @@ struct alarm { void alarm_init(struct alarm *alarm, enum alarmtimer_type type, enum alarmtimer_restart (*function)(struct alarm *, ktime_t)); void alarm_start(struct alarm *alarm, ktime_t start); -void alarm_cancel(struct alarm *alarm); +int alarm_try_to_cancel(struct alarm *alarm); +int alarm_cancel(struct alarm *alarm); u64 alarm_forward(struct alarm *alarm, ktime_t now, ktime_t interval); diff --git a/kernel/time/alarmtimer.c b/kernel/time/alarmtimer.c index 5b14cc29b6a6..bdb7342b6896 100644 --- a/kernel/time/alarmtimer.c +++ b/kernel/time/alarmtimer.c @@ -336,21 +336,49 @@ void alarm_start(struct alarm *alarm, ktime_t start) } /** - * alarm_cancel - Tries to cancel an alarm timer + * alarm_try_to_cancel - Tries to cancel an alarm timer * @alarm: ptr to alarm to be canceled + * + * Returns 1 if the timer was canceled, 0 if it was not running, + * and -1 if the callback was running */ -void alarm_cancel(struct alarm *alarm) +int alarm_try_to_cancel(struct alarm *alarm) { struct alarm_base *base = &alarm_bases[alarm->type]; unsigned long flags; - + int ret = -1; spin_lock_irqsave(&base->lock, flags); - if (alarmtimer_is_queued(alarm)) + + if (alarmtimer_callback_running(alarm)) + goto out; + + if (alarmtimer_is_queued(alarm)) { alarmtimer_remove(base, alarm); + ret = 1; + } else + ret = 0; +out: spin_unlock_irqrestore(&base->lock, flags); + return ret; } +/** + * alarm_cancel - Spins trying to cancel an alarm timer until it is done + * @alarm: ptr to alarm to be canceled + * + * Returns 1 if the timer was canceled, 0 if it was not active. + */ +int alarm_cancel(struct alarm *alarm) +{ + for (;;) { + int ret = alarm_try_to_cancel(alarm); + if (ret >= 0) + return ret; + cpu_relax(); + } +} + u64 alarm_forward(struct alarm *alarm, ktime_t now, ktime_t interval) { @@ -510,7 +538,9 @@ static int alarm_timer_del(struct k_itimer *timr) if (!rtcdev) return -ENOTSUPP; - alarm_cancel(&timr->it.alarm.alarmtimer); + if (alarm_try_to_cancel(&timr->it.alarm.alarmtimer) < 0) + return TIMER_RETRY; + return 0; } @@ -534,7 +564,8 @@ static int alarm_timer_set(struct k_itimer *timr, int flags, alarm_timer_get(timr, old_setting); /* If the timer was already set, cancel it */ - alarm_cancel(&timr->it.alarm.alarmtimer); + if (alarm_try_to_cancel(&timr->it.alarm.alarmtimer) < 0) + return TIMER_RETRY; /* start the timer */ timr->it.alarm.interval = timespec_to_ktime(new_setting->it_interval); -- cgit v1.2.3