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 heap_swap(h, _i, (h)->used); \
97 heap_sift_down(h, _i, cmp); \
98 heap_sift(h, _i, cmp); \
101 #define heap_pop(h, d, cmp) \
103 bool _r = (h)->used; \
105 (d) = (h)->data[0]; \
106 heap_del(h, 0, cmp); \
111 #define heap_peek(h) ((h)->used ? &(h)->data[0] : NULL)
112 #define heap_full(h) ((h)->used == (h)->size)
113 #define heap_empty(h) ((h)->used == 0)
115 #define heap_resort(heap, cmp) \
118 for (_i = (ssize_t) (heap)->used / 2 - 1; _i >= 0; --_i) \
119 heap_sift(heap, _i, cmp); \
122 struct pending_timer {
123 struct timer_list *timer;
124 unsigned long expires;
127 static inline bool pending_timer_cmp(struct pending_timer a,
128 struct pending_timer b)
130 return a.expires < b.expires;
133 static DECLARE_HEAP(struct pending_timer) pending_timers;
135 static pthread_mutex_t timer_lock = PTHREAD_MUTEX_INITIALIZER;
136 static pthread_cond_t timer_cond = PTHREAD_COND_INITIALIZER;
137 static pthread_cond_t timer_running_cond = PTHREAD_COND_INITIALIZER;
138 static unsigned long timer_seq;
140 static inline bool timer_running(void)
142 return timer_seq & 1;
145 static ssize_t timer_idx(struct timer_list *timer)
149 for (i = 0; i < pending_timers.used; i++)
150 if (pending_timers.data[i].timer == timer)
156 int del_timer(struct timer_list *timer)
160 pthread_mutex_lock(&timer_lock);
161 idx = timer_idx(timer);
163 heap_del(&pending_timers, idx, pending_timer_cmp);
165 timer->pending = false;
166 pthread_mutex_unlock(&timer_lock);
171 void flush_timers(void)
175 pthread_mutex_lock(&timer_lock);
177 while (timer_running() && seq == timer_seq)
178 pthread_cond_wait(&timer_running_cond, &timer_lock);
180 pthread_mutex_unlock(&timer_lock);
183 int del_timer_sync(struct timer_list *timer)
188 pthread_mutex_lock(&timer_lock);
189 idx = timer_idx(timer);
191 heap_del(&pending_timers, idx, pending_timer_cmp);
193 timer->pending = false;
196 while (timer_running() && seq == timer_seq)
197 pthread_cond_wait(&timer_running_cond, &timer_lock);
198 pthread_mutex_unlock(&timer_lock);
203 int mod_timer(struct timer_list *timer, unsigned long expires)
207 pthread_mutex_lock(&timer_lock);
208 timer->expires = expires;
209 timer->pending = true;
210 idx = timer_idx(timer);
213 pending_timers.data[idx].expires == expires)
217 pending_timers.data[idx].expires = expires;
219 heap_sift_down(&pending_timers, idx, pending_timer_cmp);
220 heap_sift(&pending_timers, idx, pending_timer_cmp);
222 if (heap_full(&pending_timers)) {
223 pending_timers.size *= 2;
224 pending_timers.data =
225 realloc(pending_timers.data,
226 pending_timers.size *
227 sizeof(struct pending_timer));
229 BUG_ON(!pending_timers.data);
232 heap_add(&pending_timers,
233 ((struct pending_timer) {
240 pthread_cond_signal(&timer_cond);
242 pthread_mutex_unlock(&timer_lock);
247 static int timer_thread(void *arg)
249 struct pending_timer *p;
254 pthread_mutex_lock(&timer_lock);
258 p = heap_peek(&pending_timers);
261 pthread_cond_wait(&timer_cond, &timer_lock);
265 if (time_after_eq(now, p->expires)) {
266 struct timer_list *timer = p->timer;
268 heap_del(&pending_timers, 0, pending_timer_cmp);
269 BUG_ON(!timer_pending(timer));
270 timer->pending = false;
273 BUG_ON(!timer_running());
275 pthread_mutex_unlock(&timer_lock);
276 timer->function(timer->data);
277 pthread_mutex_lock(&timer_lock);
280 pthread_cond_broadcast(&timer_running_cond);
285 ret = clock_gettime(CLOCK_REALTIME, &ts);
288 ts = timespec_add_ns(ts, jiffies_to_nsecs(p->expires - now));
290 pthread_cond_timedwait(&timer_cond, &timer_lock, &ts);
293 pthread_mutex_unlock(&timer_lock);
298 __attribute__((constructor(103)))
299 static void timers_init(void)
301 struct task_struct *p;
303 heap_init(&pending_timers, 64);
304 BUG_ON(!pending_timers.data);
306 p = kthread_run(timer_thread, NULL, "timers");