git.sesse.net Git - bcachefs-tools-debian/blob - linux/timer.c

   1
   2 #include <pthread.h>
   3 #include <signal.h>
   4 #include <time.h>
   5
   6 #include <linux/kernel.h>
   7 #include <linux/kthread.h>
   8 #include <linux/timer.h>
   9
  10 /**
  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
  14  *
  15  * This must always be inlined because its used from the x86-64 vdso,
  16  * which cannot call other kernel functions.
  17  */
  18 static struct timespec timespec_add_ns(struct timespec a, u64 ns)
  19 {
  20         a.tv_nsec       += ns;
  21         a.tv_sec        += a.tv_nsec / NSEC_PER_SEC;
  22         a.tv_nsec       %= NSEC_PER_SEC;
  23         return a;
  24 }
  25
  26 #define DECLARE_HEAP(type)                                              \
  27 struct {                                                                \
  28         size_t size, used;                                              \
  29         type *data;                                                     \
  30 }
  31
  32 #define heap_init(heap, _size)                                          \
  33 ({                                                                      \
  34         size_t _bytes;                                                  \
  35         (heap)->used = 0;                                               \
  36         (heap)->size = (_size);                                         \
  37         _bytes = (heap)->size * sizeof(*(heap)->data);                  \
  38         (heap)->data = malloc(_bytes);                                  \
  39         (heap)->data;                                                   \
  40 })
  41
  42 #define heap_free(heap)                                                 \
  43 do {                                                                    \
  44         kvfree((heap)->data);                                           \
  45         (heap)->data = NULL;                                            \
  46 } while (0)
  47
  48 #define heap_swap(h, i, j)      swap((h)->data[i], (h)->data[j])
  49
  50 #define heap_sift(h, i, cmp)                                            \
  51 do {                                                                    \
  52         size_t _r, _j = i;                                              \
  53                                                                         \
  54         for (; _j * 2 + 1 < (h)->used; _j = _r) {                       \
  55                 _r = _j * 2 + 1;                                        \
  56                 if (_r + 1 < (h)->used &&                               \
  57                     cmp((h)->data[_r], (h)->data[_r + 1]))              \
  58                         _r++;                                           \
  59                                                                         \
  60                 if (cmp((h)->data[_r], (h)->data[_j]))                  \
  61                         break;                                          \
  62                 heap_swap(h, _r, _j);                                   \
  63         }                                                               \
  64 } while (0)
  65
  66 #define heap_sift_down(h, i, cmp)                                       \
  67 do {                                                                    \
  68         while (i) {                                                     \
  69                 size_t p = (i - 1) / 2;                                 \
  70                 if (cmp((h)->data[i], (h)->data[p]))                    \
  71                         break;                                          \
  72                 heap_swap(h, i, p);                                     \
  73                 i = p;                                                  \
  74         }                                                               \
  75 } while (0)
  76
  77 #define heap_add(h, d, cmp)                                             \
  78 ({                                                                      \
  79         bool _r = !heap_full(h);                                        \
  80         if (_r) {                                                       \
  81                 size_t _i = (h)->used++;                                \
  82                 (h)->data[_i] = d;                                      \
  83                                                                         \
  84                 heap_sift_down(h, _i, cmp);                             \
  85                 heap_sift(h, _i, cmp);                                  \
  86         }                                                               \
  87         _r;                                                             \
  88 })
  89
  90 #define heap_del(h, i, cmp)                                             \
  91 do {                                                                    \
  92         size_t _i = (i);                                                \
  93                                                                         \
  94         BUG_ON(_i >= (h)->used);                                        \
  95         (h)->used--;                                                    \
  96         heap_swap(h, _i, (h)->used);                                    \
  97         heap_sift_down(h, _i, cmp);                                     \
  98         heap_sift(h, _i, cmp);                                          \
  99 } while (0)
 100
 101 #define heap_pop(h, d, cmp)                                             \
 102 ({                                                                      \
 103         bool _r = (h)->used;                                            \
 104         if (_r) {                                                       \
 105                 (d) = (h)->data[0];                                     \
 106                 heap_del(h, 0, cmp);                                    \
 107         }                                                               \
 108         _r;                                                             \
 109 })
 110
 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)
 114
 115 #define heap_resort(heap, cmp)                                          \
 116 do {                                                                    \
 117         ssize_t _i;                                                     \
 118         for (_i = (ssize_t) (heap)->used / 2 -  1; _i >= 0; --_i)       \
 119                 heap_sift(heap, _i, cmp);                               \
 120 } while (0)
 121
 122 struct pending_timer {
 123         struct timer_list       *timer;
 124         unsigned long           expires;
 125 };
 126
 127 static inline bool pending_timer_cmp(struct pending_timer a,
 128                                      struct pending_timer b)
 129 {
 130         return a.expires < b.expires;
 131 }
 132
 133 static DECLARE_HEAP(struct pending_timer) pending_timers;
 134
 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;
 139
 140 static inline bool timer_running(void)
 141 {
 142         return timer_seq & 1;
 143 }
 144
 145 static size_t timer_idx(struct timer_list *timer)
 146 {
 147         size_t i;
 148
 149         for (i = 0; i < pending_timers.size; i++)
 150                 if (pending_timers.data[i].timer == timer)
 151                         return i;
 152         BUG();
 153 }
 154
 155 int del_timer(struct timer_list *timer)
 156 {
 157         int pending;
 158
 159         pthread_mutex_lock(&timer_lock);
 160         pending = timer_pending(timer);
 161         timer->pending = false;
 162
 163         if (pending)
 164                 heap_del(&pending_timers, timer_idx(timer), pending_timer_cmp);
 165
 166         pthread_mutex_unlock(&timer_lock);
 167
 168         return pending;
 169 }
 170
 171 void flush_timers(void)
 172 {
 173         unsigned long seq;
 174
 175         pthread_mutex_lock(&timer_lock);
 176         seq = timer_seq;
 177         while (timer_running() && seq == timer_seq)
 178                 pthread_cond_wait(&timer_running_cond, &timer_lock);
 179
 180         pthread_mutex_unlock(&timer_lock);
 181 }
 182
 183 int del_timer_sync(struct timer_list *timer)
 184 {
 185         unsigned long seq;
 186         int pending;
 187
 188         pthread_mutex_lock(&timer_lock);
 189         pending = timer_pending(timer);
 190         timer->pending = false;
 191
 192         if (pending)
 193                 heap_del(&pending_timers, timer_idx(timer), pending_timer_cmp);
 194
 195         seq = timer_seq;
 196         while (timer_running() && seq == timer_seq)
 197                 pthread_cond_wait(&timer_running_cond, &timer_lock);
 198
 199         pthread_mutex_unlock(&timer_lock);
 200
 201         return pending;
 202 }
 203
 204 int mod_timer(struct timer_list *timer, unsigned long expires)
 205 {
 206         int pending;
 207         size_t i;
 208
 209         pthread_mutex_lock(&timer_lock);
 210         pending = timer_pending(timer);
 211
 212         if (pending && timer->expires == expires)
 213                 goto out;
 214
 215         timer->expires = expires;
 216         timer->pending = true;
 217
 218         if (pending) {
 219                 i = timer_idx(timer);
 220                 pending_timers.data[i].expires = expires;
 221
 222                 heap_sift_down(&pending_timers, i, pending_timer_cmp);
 223                 heap_sift(&pending_timers, i, pending_timer_cmp);
 224         } else {
 225                 if (heap_full(&pending_timers)) {
 226                         pending_timers.size *= 2;
 227                         pending_timers.data =
 228                                 realloc(pending_timers.data,
 229                                         pending_timers.size *
 230                                         sizeof(struct pending_timer));
 231
 232                         BUG_ON(!pending_timers.data);
 233                 }
 234
 235                 heap_add(&pending_timers,
 236                          ((struct pending_timer) {
 237                                 .timer = timer,
 238                                 .expires = expires,
 239                          }),
 240                          pending_timer_cmp);
 241         }
 242
 243         pthread_cond_signal(&timer_cond);
 244 out:
 245         pthread_mutex_unlock(&timer_lock);
 246
 247         return pending;
 248 }
 249
 250 static int timer_thread(void *arg)
 251 {
 252         struct pending_timer *p;
 253         struct timespec ts;
 254         unsigned long now;
 255         int ret;
 256
 257         pthread_mutex_lock(&timer_lock);
 258
 259         while (1) {
 260                 now = jiffies;
 261                 p = heap_peek(&pending_timers);
 262
 263                 if (!p) {
 264                         pthread_cond_wait(&timer_cond, &timer_lock);
 265                         continue;
 266                 }
 267
 268                 if (time_after_eq(now, p->expires)) {
 269                         struct timer_list *timer = p->timer;
 270
 271                         heap_del(&pending_timers, 0, pending_timer_cmp);
 272                         BUG_ON(!timer_pending(timer));
 273                         timer->pending = false;
 274
 275                         timer_seq++;
 276                         BUG_ON(!timer_running());
 277
 278                         pthread_mutex_unlock(&timer_lock);
 279                         timer->function(timer->data);
 280                         pthread_mutex_lock(&timer_lock);
 281
 282                         timer_seq++;
 283                         pthread_cond_broadcast(&timer_running_cond);
 284                         continue;
 285                 }
 286
 287
 288                 ret = clock_gettime(CLOCK_REALTIME, &ts);
 289                 BUG_ON(ret);
 290
 291                 ts = timespec_add_ns(ts, jiffies_to_nsecs(p->expires - now));
 292
 293                 pthread_cond_timedwait(&timer_cond, &timer_lock, &ts);
 294         }
 295
 296         pthread_mutex_unlock(&timer_lock);
 297
 298         return 0;
 299 }
 300
 301 __attribute__((constructor(103)))
 302 static void timers_init(void)
 303 {
 304         struct task_struct *p;
 305
 306         heap_init(&pending_timers, 64);
 307         BUG_ON(!pending_timers.data);
 308
 309         p = kthread_run(timer_thread, NULL, "timers");
 310         BUG_ON(IS_ERR(p));
 311 }