6 #include <linux/kernel.h>
7 #include <linux/kthread.h>
8 #include <linux/timer.h>
11 * timespec_add_ns - Adds nanoseconds to a timespec
12 * @a: pointer to timespec to be incremented
13 * @ns: unsigned nanoseconds value to be added
15 * This must always be inlined because its used from the x86-64 vdso,
16 * which cannot call other kernel functions.
18 static struct timespec timespec_add_ns(struct timespec a, u64 ns)
21 a.tv_sec += a.tv_nsec / NSEC_PER_SEC;
22 a.tv_nsec %= NSEC_PER_SEC;
26 #define DECLARE_HEAP(type) \
32 #define heap_init(heap, _size) \
36 (heap)->size = (_size); \
37 _bytes = (heap)->size * sizeof(*(heap)->data); \
38 (heap)->data = malloc(_bytes); \
42 #define heap_free(heap) \
44 kvfree((heap)->data); \
45 (heap)->data = NULL; \
48 #define heap_swap(h, i, j) swap((h)->data[i], (h)->data[j])
50 #define heap_sift(h, i, cmp) \
54 for (; _j * 2 + 1 < (h)->used; _j = _r) { \
56 if (_r + 1 < (h)->used && \
57 cmp((h)->data[_r], (h)->data[_r + 1])) \
60 if (cmp((h)->data[_r], (h)->data[_j])) \
62 heap_swap(h, _r, _j); \
66 #define heap_sift_down(h, i, cmp) \
69 size_t p = (i - 1) / 2; \
70 if (cmp((h)->data[i], (h)->data[p])) \
77 #define heap_add(h, d, cmp) \
79 bool _r = !heap_full(h); \
81 size_t _i = (h)->used++; \
84 heap_sift_down(h, _i, cmp); \
85 heap_sift(h, _i, cmp); \
90 #define heap_del(h, i, cmp) \
94 BUG_ON(_i >= (h)->used); \
96 if ((_i) < (h)->used) { \
97 heap_swap(h, _i, (h)->used); \
98 heap_sift_down(h, _i, cmp); \
99 heap_sift(h, _i, cmp); \
103 #define heap_pop(h, d, cmp) \
105 bool _r = (h)->used; \
107 (d) = (h)->data[0]; \
108 heap_del(h, 0, cmp); \
113 #define heap_peek(h) ((h)->used ? &(h)->data[0] : NULL)
114 #define heap_full(h) ((h)->used == (h)->size)
115 #define heap_empty(h) ((h)->used == 0)
117 #define heap_resort(heap, cmp) \
120 for (_i = (ssize_t) (heap)->used / 2 - 1; _i >= 0; --_i) \
121 heap_sift(heap, _i, cmp); \
124 struct pending_timer {
125 struct timer_list *timer;
126 unsigned long expires;
129 static inline bool pending_timer_cmp(struct pending_timer a,
130 struct pending_timer b)
132 return a.expires < b.expires;
135 static DECLARE_HEAP(struct pending_timer) pending_timers;
137 static pthread_mutex_t timer_lock = PTHREAD_MUTEX_INITIALIZER;
138 static pthread_cond_t timer_cond = PTHREAD_COND_INITIALIZER;
139 static pthread_cond_t timer_running_cond = PTHREAD_COND_INITIALIZER;
140 static unsigned long timer_seq;
142 static inline bool timer_running(void)
144 return timer_seq & 1;
147 static ssize_t timer_idx(struct timer_list *timer)
151 for (i = 0; i < pending_timers.used; i++)
152 if (pending_timers.data[i].timer == timer)
158 int del_timer(struct timer_list *timer)
162 pthread_mutex_lock(&timer_lock);
163 idx = timer_idx(timer);
165 heap_del(&pending_timers, idx, pending_timer_cmp);
167 timer->pending = false;
168 pthread_mutex_unlock(&timer_lock);
173 void flush_timers(void)
177 pthread_mutex_lock(&timer_lock);
179 while (timer_running() && seq == timer_seq)
180 pthread_cond_wait(&timer_running_cond, &timer_lock);
182 pthread_mutex_unlock(&timer_lock);
185 int del_timer_sync(struct timer_list *timer)
190 pthread_mutex_lock(&timer_lock);
191 idx = timer_idx(timer);
193 heap_del(&pending_timers, idx, pending_timer_cmp);
195 timer->pending = false;
198 while (timer_running() && seq == timer_seq)
199 pthread_cond_wait(&timer_running_cond, &timer_lock);
200 pthread_mutex_unlock(&timer_lock);
205 int mod_timer(struct timer_list *timer, unsigned long expires)
209 pthread_mutex_lock(&timer_lock);
210 timer->expires = expires;
211 timer->pending = true;
212 idx = timer_idx(timer);
215 pending_timers.data[idx].expires == expires)
219 pending_timers.data[idx].expires = expires;
221 heap_sift_down(&pending_timers, idx, pending_timer_cmp);
222 heap_sift(&pending_timers, idx, pending_timer_cmp);
224 if (heap_full(&pending_timers)) {
225 pending_timers.size *= 2;
226 pending_timers.data =
227 realloc(pending_timers.data,
228 pending_timers.size *
229 sizeof(struct pending_timer));
231 BUG_ON(!pending_timers.data);
234 heap_add(&pending_timers,
235 ((struct pending_timer) {
242 pthread_cond_signal(&timer_cond);
244 pthread_mutex_unlock(&timer_lock);
249 static bool timer_thread_stop = false;
251 static int timer_thread(void *arg)
253 struct pending_timer *p;
258 pthread_mutex_lock(&timer_lock);
260 while (!timer_thread_stop) {
262 p = heap_peek(&pending_timers);
265 pthread_cond_wait(&timer_cond, &timer_lock);
269 if (time_after_eq(now, p->expires)) {
270 struct timer_list *timer = p->timer;
272 heap_del(&pending_timers, 0, pending_timer_cmp);
273 BUG_ON(!timer_pending(timer));
274 timer->pending = false;
277 BUG_ON(!timer_running());
279 pthread_mutex_unlock(&timer_lock);
280 timer->function(timer);
281 pthread_mutex_lock(&timer_lock);
284 pthread_cond_broadcast(&timer_running_cond);
289 ret = clock_gettime(CLOCK_REALTIME, &ts);
292 ts = timespec_add_ns(ts, jiffies_to_nsecs(p->expires - now));
294 pthread_cond_timedwait(&timer_cond, &timer_lock, &ts);
297 pthread_mutex_unlock(&timer_lock);
302 struct task_struct *timer_task;
304 __attribute__((constructor(103)))
305 static void timers_init(void)
307 heap_init(&pending_timers, 64);
308 BUG_ON(!pending_timers.data);
310 timer_task = kthread_run(timer_thread, NULL, "timers");
311 BUG_ON(IS_ERR(timer_task));
314 __attribute__((destructor(103)))
315 static void timers_cleanup(void)
317 get_task_struct(timer_task);
319 pthread_mutex_lock(&timer_lock);
320 timer_thread_stop = true;
321 pthread_cond_signal(&timer_cond);
322 pthread_mutex_unlock(&timer_lock);
324 int ret = kthread_stop(timer_task);
327 put_task_struct(timer_task);