glusterfs

1
/*
2
 *  linux/kernel/timer.c
3
 *
4
 *  Kernel internal timers
5
 *
6
 *  Copyright (C) 1991, 1992  Linus Torvalds
7
 *
8
 */
9
/*
10
  This program is free software; you can redistribute it and/or modify
11
  it under the terms of the GNU General Public License as published by
12
  the Free Software Foundation; either version 2 of the License, or
13
  (at your option) any later version.
14

15
  This program is distributed in the hope that it will be useful,
16
  but WITHOUT ANY WARRANTY; without even the implied warranty of
17
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18
  GNU General Public License for more details.
19

20
  You should have received a copy of the GNU General Public License along
21
  with this program; if not, write to the Free Software Foundation, Inc.,
22
  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
23
*/
24

25
#include <stdio.h>
26
#include <stdlib.h>
27
#include <sys/time.h>
28
#include <sys/types.h>
29
#include <unistd.h>
30
#include <sys/select.h>
31
#include <pthread.h>
32

33
#include "timer-wheel.h"
34

35
static inline void
36
__gf_tw_add_timer (struct tvec_base *base, struct gf_tw_timer_list *timer)
37
{
38
        int i;
39
        unsigned long idx;
40
        unsigned long expires;
41
        struct list_head *vec;
42

43
        expires = timer->expires;
44

45
        idx = expires - base->timer_sec;
46

47
        if (idx < TVR_SIZE) {
48
                i = expires & TVR_MASK;
49
                vec = base->tv1.vec + i;
50
        } else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
51
                i = (expires >> TVR_BITS) & TVN_MASK;
52
                vec = base->tv2.vec + i;
53
        } else if (idx < 1 << (TVR_BITS + 2*TVN_BITS)) {
54
                i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;
55
                vec = base->tv3.vec + i;
56
        } else if (idx < 1 << (TVR_BITS + 3*TVN_BITS)) {
57
                i = (expires >> (TVR_BITS + 2*TVN_BITS)) & TVN_MASK;
58
                vec = base->tv4.vec + i;
59
        } else if (idx < 0) {
60
                vec = base->tv1.vec + (base->timer_sec & TVR_MASK);
61
        } else {
62
                i = (expires >> (TVR_BITS + 3*TVN_BITS)) & TVN_MASK;
63
                vec = base->tv5.vec + i;
64
        }
65

66
        list_add_tail (&timer->entry, vec);
67
}
68

69
unsigned long gf_tw_find_last_bit(const unsigned long *, unsigned long);
70

71
#if defined(__GNUC__) || defined(__clang__)
72
static inline unsigned long gf_tw_fls (unsigned long word)
73
{
74
        return BITS_PER_LONG - __builtin_clzl(word);
75
}
76
#else
77
extern unsigned long gf_tw_fls (unsigned long);
78
#endif
79

80
static inline unsigned long
81
apply_slack(struct tvec_base *base, struct gf_tw_timer_list *timer)
82
{
83
        long delta;
84
        unsigned long mask, expires, expires_limit;
85

86
        expires = timer->expires;
87

88
        delta = expires - base->timer_sec;
89
        if (delta < 256)
90
                return expires;
91

92
        expires_limit = expires + delta / 256;
93
        mask = expires ^ expires_limit;
94
        if (mask == 0)
95
                return expires;
96

97
        int bit = gf_tw_fls (mask);
98
        mask = (1UL << bit) - 1;
99

100
        expires_limit = expires_limit & ~(mask);
101
        return expires_limit;
102
}
103

104
static inline void
105
__gf_tw_detach_timer (struct gf_tw_timer_list *timer)
106
{
107
        struct list_head *entry = &timer->entry;
108

109
        list_del (entry);
110
        entry->next = NULL;
111
}
112

113
static inline int
114
cascade (struct tvec_base *base, struct tvec *tv, int index)
115
{
116
        struct gf_tw_timer_list *timer, *tmp;
117
        struct list_head tv_list;
118

119
        list_replace_init (tv->vec + index, &tv_list);
120

121
        list_for_each_entry_safe (timer, tmp, &tv_list, entry) {
122
                __gf_tw_add_timer (base, timer);
123
        }
124

125
        return index;
126
}
127

128
#define INDEX(N)  ((base->timer_sec >> (TVR_BITS + N * TVN_BITS)) & TVN_MASK)
129

130
/**
131
 * run expired timers
132
 */
133
static inline void
134
run_timers (struct tvec_base *base)
135
{
136
        unsigned long index, call_time;
137
        struct gf_tw_timer_list *timer;
138

139
        struct list_head work_list;
140
        struct list_head *head = &work_list;
141

142
        pthread_spin_lock (&base->lock);
143
        {
144
                index  = base->timer_sec & TVR_MASK;
145

146
                if (!index &&
147
                    (!cascade (base, &base->tv2, INDEX(0))) &&
148
                    (!cascade (base, &base->tv3, INDEX(1))) &&
149
                    (!cascade (base, &base->tv4, INDEX(2))))
150
                        cascade (base, &base->tv5, INDEX(3));
151

152
                call_time = base->timer_sec++;
153
                list_replace_init (base->tv1.vec + index, head);
154
                while (!list_empty(head)) {
155
                        void (*fn)(struct gf_tw_timer_list *, void *, unsigned long);
156
                        void *data;
157

158
                        timer = list_first_entry (head, struct gf_tw_timer_list, entry);
159
                        fn = timer->function;
160
                        data = timer->data;
161

162
                        __gf_tw_detach_timer (timer);
163
                        pthread_spin_unlock(&base->lock);
164
                        {
165
                            /* It is required to run the actual function outside
166
                               of the locked zone, so we don't bother about
167
                               locked operations inside that function */
168
                            fn(timer, data, call_time);
169
                        }
170
                        pthread_spin_lock(&base->lock);
171
                }
172
        }
173
        pthread_spin_unlock (&base->lock);
174

175
}
176

177
void *runner (void *arg)
178
{
179
        struct timeval tv = {0,};
180
        struct tvec_base *base = arg;
181

182
        while (1) {
183
                run_timers (base);
184

185
                tv.tv_sec  = 1;
186
                tv.tv_usec = 0;
187
                (void) select (0, NULL, NULL, NULL, &tv);
188
        }
189

190
        return NULL;
191

192
}
193

194
static inline int timer_pending (struct gf_tw_timer_list *timer)
195
{
196
        struct list_head *entry = &timer->entry;
197

198
        return (entry->next != NULL);
199
}
200

201
static inline int __detach_if_pending (struct gf_tw_timer_list *timer)
202
{
203
        if (!timer_pending (timer))
204
                return 0;
205

206
        __gf_tw_detach_timer (timer);
207
        return 1;
208
}
209

210
static inline int __mod_timer (struct tvec_base *base,
211
                               struct gf_tw_timer_list *timer, int pending_only)
212
{
213
        int ret = 0;
214

215
        ret = __detach_if_pending (timer);
216
        if (!ret && pending_only)
217
                goto done;
218

219
        ret = 1;
220
        __gf_tw_add_timer (base, timer);
221

222
 done:
223
        return ret;
224
}
225

226
/* interface */
227

228
/**
229
 * Add a timer in the timer wheel
230
 */
231
void gf_tw_add_timer (struct tvec_base *base, struct gf_tw_timer_list *timer)
232
{
233
        pthread_spin_lock (&base->lock);
234
        {
235
                timer->expires += base->timer_sec;
236
                timer->expires = apply_slack (base, timer);
237
                __gf_tw_add_timer (base, timer);
238
        }
239
        pthread_spin_unlock (&base->lock);
240
}
241

242
/**
243
 * Remove a timer from the timer wheel
244
 */
245
int gf_tw_del_timer (struct tvec_base *base, struct gf_tw_timer_list *timer)
246
{
247
        int ret = 0;
248

249
        pthread_spin_lock (&base->lock);
250
        {
251
                if (timer_pending (timer)) {
252
                        ret = 1;
253
                        __gf_tw_detach_timer (timer);
254
                }
255
        }
256
        pthread_spin_unlock (&base->lock);
257

258
        return ret;
259
}
260

261
int gf_tw_mod_timer_pending (struct tvec_base *base,
262
                             struct gf_tw_timer_list *timer,
263
                             unsigned long expires)
264
{
265
        int ret = 1;
266

267
        pthread_spin_lock (&base->lock);
268
        {
269
                timer->expires = expires + base->timer_sec;
270
                timer->expires = apply_slack (base, timer);
271

272
                ret = __mod_timer (base, timer, 1);
273
        }
274
        pthread_spin_unlock (&base->lock);
275

276
        return ret;
277
}
278

279
int gf_tw_mod_timer (struct tvec_base *base,
280
                     struct gf_tw_timer_list *timer, unsigned long expires)
281
{
282
        int ret = 1;
283

284
        pthread_spin_lock (&base->lock);
285
        {
286
                /* fast path optimization */
287
                if (timer_pending (timer) && timer->expires == expires)
288
                        goto unblock;
289

290
                timer->expires = expires + base->timer_sec;
291
                timer->expires = apply_slack (base, timer);
292

293
                ret = __mod_timer (base, timer, 0);
294
        }
295
 unblock:
296
        pthread_spin_unlock (&base->lock);
297

298
        return ret;
299
}
300

301
int gf_tw_cleanup_timers (struct tvec_base *base)
302
{
303
        int ret = 0;
304
        void *res = NULL;
305

306
        /* terminate runner */
307
        ret = pthread_cancel (base->runner);
308
        if (ret != 0)
309
                goto error_return;
310
        ret = pthread_join (base->runner, &res);
311
        if (ret != 0)
312
                goto error_return;
313
        if (res != PTHREAD_CANCELED)
314
                goto error_return;
315

316
        /* destroy lock */
317
        ret = pthread_spin_destroy (&base->lock);
318
        if (ret != 0)
319
                goto error_return;
320

321
        /* deallocated timer base */
322
        free (base);
323
        return 0;
324

325
 error_return:
326
        return -1;
327
}
328

329
/**
330
 * Initialize various timer wheel lists and spawn a thread that
331
 * invokes run_timers()
332
 */
333
struct tvec_base *gf_tw_init_timers (void)
334
{
335
        int               j    = 0;
336
        int               ret  = 0;
337
        struct timeval    tv   = {0,};
338
        struct tvec_base *base = NULL;
339

340
        base = malloc (sizeof (*base));
341
        if (!base)
342
                goto error_return;
343

344
        ret = pthread_spin_init (&base->lock, 0);
345
        if (ret != 0)
346
                goto error_dealloc;
347

348
        for (j = 0; j < TVN_SIZE; j++) {
349
                INIT_LIST_HEAD (base->tv5.vec + j);
350
                INIT_LIST_HEAD (base->tv4.vec + j);
351
                INIT_LIST_HEAD (base->tv3.vec + j);
352
                INIT_LIST_HEAD (base->tv2.vec + j);
353
        }
354

355
        for (j = 0; j < TVR_SIZE; j++) {
356
                INIT_LIST_HEAD (base->tv1.vec + j);
357
        }
358

359
        ret = gettimeofday (&tv, 0);
360
        if (ret < 0)
361
                goto destroy_lock;
362
        base->timer_sec = tv.tv_sec;
363

364
        ret = pthread_create (&base->runner, NULL, runner, base);
365
        if (ret != 0)
366
                goto destroy_lock;
367
        return base;
368

369
 destroy_lock:
370
        (void) pthread_spin_destroy (&base->lock);
371
 error_dealloc:
372
        free (base);
373
 error_return:
374
        return NULL;
375
}
376