projects/linux·blob v2.6.15-rc4 · refs

1578 lines · 41.5 KiB

1/*
2 * linux/kernel/timer.c
3 *
4 * Kernel internal timers, kernel timekeeping, basic process system calls
5 *
6 * Copyright (C) 1991, 1992 Linus Torvalds
7 *
8 * 1997-01-28 Modified by Finn Arne Gangstad to make timers scale better.
9 *
10 * 1997-09-10 Updated NTP code according to technical memorandum Jan '96
11 * "A Kernel Model for Precision Timekeeping" by Dave Mills
12 * 1998-12-24 Fixed a xtime SMP race (we need the xtime_lock rw spinlock to
13 * serialize accesses to xtime/lost_ticks).
14 * Copyright (C) 1998 Andrea Arcangeli
15 * 1999-03-10 Improved NTP compatibility by Ulrich Windl
16 * 2002-05-31 Move sys_sysinfo here and make its locking sane, Robert Love
17 * 2000-10-05 Implemented scalable SMP per-CPU timer handling.
18 * Copyright (C) 2000, 2001, 2002 Ingo Molnar
19 * Designed by David S. Miller, Alexey Kuznetsov and Ingo Molnar
20 */
21
22#include <linux/kernel_stat.h>
23#include <linux/module.h>
24#include <linux/interrupt.h>
25#include <linux/percpu.h>
26#include <linux/init.h>
27#include <linux/mm.h>
28#include <linux/swap.h>
29#include <linux/notifier.h>
30#include <linux/thread_info.h>
31#include <linux/time.h>
32#include <linux/jiffies.h>
33#include <linux/posix-timers.h>
34#include <linux/cpu.h>
35#include <linux/syscalls.h>
36
37#include <asm/uaccess.h>
38#include <asm/unistd.h>
39#include <asm/div64.h>
40#include <asm/timex.h>
41#include <asm/io.h>
42
43#ifdef CONFIG_TIME_INTERPOLATION
44static void time_interpolator_update(long delta_nsec);
45#else
46#define time_interpolator_update(x)
47#endif
48
49u64 jiffies_64 __cacheline_aligned_in_smp = INITIAL_JIFFIES;
50
51EXPORT_SYMBOL(jiffies_64);
52
53/*
54 * per-CPU timer vector definitions:
55 */
56
57#define TVN_BITS (CONFIG_BASE_SMALL ? 4 : 6)
58#define TVR_BITS (CONFIG_BASE_SMALL ? 6 : 8)
59#define TVN_SIZE (1 << TVN_BITS)
60#define TVR_SIZE (1 << TVR_BITS)
61#define TVN_MASK (TVN_SIZE - 1)
62#define TVR_MASK (TVR_SIZE - 1)
63
64struct timer_base_s {
65 spinlock_t lock;
66 struct timer_list *running_timer;
67};
68
69typedef struct tvec_s {
70 struct list_head vec[TVN_SIZE];
71} tvec_t;
72
73typedef struct tvec_root_s {
74 struct list_head vec[TVR_SIZE];
75} tvec_root_t;
76
77struct tvec_t_base_s {
78 struct timer_base_s t_base;
79 unsigned long timer_jiffies;
80 tvec_root_t tv1;
81 tvec_t tv2;
82 tvec_t tv3;
83 tvec_t tv4;
84 tvec_t tv5;
85} ____cacheline_aligned_in_smp;
86
87typedef struct tvec_t_base_s tvec_base_t;
88static DEFINE_PER_CPU(tvec_base_t, tvec_bases);
89
90static inline void set_running_timer(tvec_base_t *base,
91 struct timer_list *timer)
92{
93#ifdef CONFIG_SMP
94 base->t_base.running_timer = timer;
95#endif
96}
97
98static void internal_add_timer(tvec_base_t *base, struct timer_list *timer)
99{
100 unsigned long expires = timer->expires;
101 unsigned long idx = expires - base->timer_jiffies;
102 struct list_head *vec;
103
104 if (idx < TVR_SIZE) {
105 int i = expires & TVR_MASK;
106 vec = base->tv1.vec + i;
107 } else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
108 int i = (expires >> TVR_BITS) & TVN_MASK;
109 vec = base->tv2.vec + i;
110 } else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) {
111 int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;
112 vec = base->tv3.vec + i;
113 } else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) {
114 int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;
115 vec = base->tv4.vec + i;
116 } else if ((signed long) idx < 0) {
117 /*
118 * Can happen if you add a timer with expires == jiffies,
119 * or you set a timer to go off in the past
120 */
121 vec = base->tv1.vec + (base->timer_jiffies & TVR_MASK);
122 } else {
123 int i;
124 /* If the timeout is larger than 0xffffffff on 64-bit
125 * architectures then we use the maximum timeout:
126 */
127 if (idx > 0xffffffffUL) {
128 idx = 0xffffffffUL;
129 expires = idx + base->timer_jiffies;
130 }
131 i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
132 vec = base->tv5.vec + i;
133 }
134 /*
135 * Timers are FIFO:
136 */
137 list_add_tail(&timer->entry, vec);
138}
139
140typedef struct timer_base_s timer_base_t;
141/*
142 * Used by TIMER_INITIALIZER, we can't use per_cpu(tvec_bases)
143 * at compile time, and we need timer->base to lock the timer.
144 */
145timer_base_t __init_timer_base
146 ____cacheline_aligned_in_smp = { .lock = SPIN_LOCK_UNLOCKED };
147EXPORT_SYMBOL(__init_timer_base);
148
149/***
150 * init_timer - initialize a timer.
151 * @timer: the timer to be initialized
152 *
153 * init_timer() must be done to a timer prior calling *any* of the
154 * other timer functions.
155 */
156void fastcall init_timer(struct timer_list *timer)
157{
158 timer->entry.next = NULL;
159 timer->base = &per_cpu(tvec_bases, raw_smp_processor_id()).t_base;
160}
161EXPORT_SYMBOL(init_timer);
162
163static inline void detach_timer(struct timer_list *timer,
164 int clear_pending)
165{
166 struct list_head *entry = &timer->entry;
167
168 __list_del(entry->prev, entry->next);
169 if (clear_pending)
170 entry->next = NULL;
171 entry->prev = LIST_POISON2;
172}
173
174/*
175 * We are using hashed locking: holding per_cpu(tvec_bases).t_base.lock
176 * means that all timers which are tied to this base via timer->base are
177 * locked, and the base itself is locked too.
178 *
179 * So __run_timers/migrate_timers can safely modify all timers which could
180 * be found on ->tvX lists.
181 *
182 * When the timer's base is locked, and the timer removed from list, it is
183 * possible to set timer->base = NULL and drop the lock: the timer remains
184 * locked.
185 */
186static timer_base_t *lock_timer_base(struct timer_list *timer,
187 unsigned long *flags)
188{
189 timer_base_t *base;
190
191 for (;;) {
192 base = timer->base;
193 if (likely(base != NULL)) {
194 spin_lock_irqsave(&base->lock, *flags);
195 if (likely(base == timer->base))
196 return base;
197 /* The timer has migrated to another CPU */
198 spin_unlock_irqrestore(&base->lock, *flags);
199 }
200 cpu_relax();
201 }
202}
203
204int __mod_timer(struct timer_list *timer, unsigned long expires)
205{
206 timer_base_t *base;
207 tvec_base_t *new_base;
208 unsigned long flags;
209 int ret = 0;
210
211 BUG_ON(!timer->function);
212
213 base = lock_timer_base(timer, &flags);
214
215 if (timer_pending(timer)) {
216 detach_timer(timer, 0);
217 ret = 1;
218 }
219
220 new_base = &__get_cpu_var(tvec_bases);
221
222 if (base != &new_base->t_base) {
223 /*
224 * We are trying to schedule the timer on the local CPU.
225 * However we can't change timer's base while it is running,
226 * otherwise del_timer_sync() can't detect that the timer's
227 * handler yet has not finished. This also guarantees that
228 * the timer is serialized wrt itself.
229 */
230 if (unlikely(base->running_timer == timer)) {
231 /* The timer remains on a former base */
232 new_base = container_of(base, tvec_base_t, t_base);
233 } else {
234 /* See the comment in lock_timer_base() */
235 timer->base = NULL;
236 spin_unlock(&base->lock);
237 spin_lock(&new_base->t_base.lock);
238 timer->base = &new_base->t_base;
239 }
240 }
241
242 timer->expires = expires;
243 internal_add_timer(new_base, timer);
244 spin_unlock_irqrestore(&new_base->t_base.lock, flags);
245
246 return ret;
247}
248
249EXPORT_SYMBOL(__mod_timer);
250
251/***
252 * add_timer_on - start a timer on a particular CPU
253 * @timer: the timer to be added
254 * @cpu: the CPU to start it on
255 *
256 * This is not very scalable on SMP. Double adds are not possible.
257 */
258void add_timer_on(struct timer_list *timer, int cpu)
259{
260 tvec_base_t *base = &per_cpu(tvec_bases, cpu);
261 unsigned long flags;
262
263 BUG_ON(timer_pending(timer) || !timer->function);
264 spin_lock_irqsave(&base->t_base.lock, flags);
265 timer->base = &base->t_base;
266 internal_add_timer(base, timer);
267 spin_unlock_irqrestore(&base->t_base.lock, flags);
268}
269
270
271/***
272 * mod_timer - modify a timer's timeout
273 * @timer: the timer to be modified
274 *
275 * mod_timer is a more efficient way to update the expire field of an
276 * active timer (if the timer is inactive it will be activated)
277 *
278 * mod_timer(timer, expires) is equivalent to:
279 *
280 * del_timer(timer); timer->expires = expires; add_timer(timer);
281 *
282 * Note that if there are multiple unserialized concurrent users of the
283 * same timer, then mod_timer() is the only safe way to modify the timeout,
284 * since add_timer() cannot modify an already running timer.
285 *
286 * The function returns whether it has modified a pending timer or not.
287 * (ie. mod_timer() of an inactive timer returns 0, mod_timer() of an
288 * active timer returns 1.)
289 */
290int mod_timer(struct timer_list *timer, unsigned long expires)
291{
292 BUG_ON(!timer->function);
293
294 /*
295 * This is a common optimization triggered by the
296 * networking code - if the timer is re-modified
297 * to be the same thing then just return:
298 */
299 if (timer->expires == expires && timer_pending(timer))
300 return 1;
301
302 return __mod_timer(timer, expires);
303}
304
305EXPORT_SYMBOL(mod_timer);
306
307/***
308 * del_timer - deactive a timer.
309 * @timer: the timer to be deactivated
310 *
311 * del_timer() deactivates a timer - this works on both active and inactive
312 * timers.
313 *
314 * The function returns whether it has deactivated a pending timer or not.
315 * (ie. del_timer() of an inactive timer returns 0, del_timer() of an
316 * active timer returns 1.)
317 */
318int del_timer(struct timer_list *timer)
319{
320 timer_base_t *base;
321 unsigned long flags;
322 int ret = 0;
323
324 if (timer_pending(timer)) {
325 base = lock_timer_base(timer, &flags);
326 if (timer_pending(timer)) {
327 detach_timer(timer, 1);
328 ret = 1;
329 }
330 spin_unlock_irqrestore(&base->lock, flags);
331 }
332
333 return ret;
334}
335
336EXPORT_SYMBOL(del_timer);
337
338#ifdef CONFIG_SMP
339/*
340 * This function tries to deactivate a timer. Upon successful (ret >= 0)
341 * exit the timer is not queued and the handler is not running on any CPU.
342 *
343 * It must not be called from interrupt contexts.
344 */
345int try_to_del_timer_sync(struct timer_list *timer)
346{
347 timer_base_t *base;
348 unsigned long flags;
349 int ret = -1;
350
351 base = lock_timer_base(timer, &flags);
352
353 if (base->running_timer == timer)
354 goto out;
355
356 ret = 0;
357 if (timer_pending(timer)) {
358 detach_timer(timer, 1);
359 ret = 1;
360 }
361out:
362 spin_unlock_irqrestore(&base->lock, flags);
363
364 return ret;
365}
366
367/***
368 * del_timer_sync - deactivate a timer and wait for the handler to finish.
369 * @timer: the timer to be deactivated
370 *
371 * This function only differs from del_timer() on SMP: besides deactivating
372 * the timer it also makes sure the handler has finished executing on other
373 * CPUs.
374 *
375 * Synchronization rules: callers must prevent restarting of the timer,
376 * otherwise this function is meaningless. It must not be called from
377 * interrupt contexts. The caller must not hold locks which would prevent
378 * completion of the timer's handler. The timer's handler must not call
379 * add_timer_on(). Upon exit the timer is not queued and the handler is
380 * not running on any CPU.
381 *
382 * The function returns whether it has deactivated a pending timer or not.
383 */
384int del_timer_sync(struct timer_list *timer)
385{
386 for (;;) {
387 int ret = try_to_del_timer_sync(timer);
388 if (ret >= 0)
389 return ret;
390 }
391}
392
393EXPORT_SYMBOL(del_timer_sync);
394#endif
395
396static int cascade(tvec_base_t *base, tvec_t *tv, int index)
397{
398 /* cascade all the timers from tv up one level */
399 struct list_head *head, *curr;
400
401 head = tv->vec + index;
402 curr = head->next;
403 /*
404 * We are removing _all_ timers from the list, so we don't have to
405 * detach them individually, just clear the list afterwards.
406 */
407 while (curr != head) {
408 struct timer_list *tmp;
409
410 tmp = list_entry(curr, struct timer_list, entry);
411 BUG_ON(tmp->base != &base->t_base);
412 curr = curr->next;
413 internal_add_timer(base, tmp);
414 }
415 INIT_LIST_HEAD(head);
416
417 return index;
418}
419
420/***
421 * __run_timers - run all expired timers (if any) on this CPU.
422 * @base: the timer vector to be processed.
423 *
424 * This function cascades all vectors and executes all expired timer
425 * vectors.
426 */
427#define INDEX(N) (base->timer_jiffies >> (TVR_BITS + N * TVN_BITS)) & TVN_MASK
428
429static inline void __run_timers(tvec_base_t *base)
430{
431 struct timer_list *timer;
432
433 spin_lock_irq(&base->t_base.lock);
434 while (time_after_eq(jiffies, base->timer_jiffies)) {
435 struct list_head work_list = LIST_HEAD_INIT(work_list);
436 struct list_head *head = &work_list;
437 int index = base->timer_jiffies & TVR_MASK;
438
439 /*
440 * Cascade timers:
441 */
442 if (!index &&
443 (!cascade(base, &base->tv2, INDEX(0))) &&
444 (!cascade(base, &base->tv3, INDEX(1))) &&
445 !cascade(base, &base->tv4, INDEX(2)))
446 cascade(base, &base->tv5, INDEX(3));
447 ++base->timer_jiffies;
448 list_splice_init(base->tv1.vec + index, &work_list);
449 while (!list_empty(head)) {
450 void (*fn)(unsigned long);
451 unsigned long data;
452
453 timer = list_entry(head->next,struct timer_list,entry);
454 fn = timer->function;
455 data = timer->data;
456
457 set_running_timer(base, timer);
458 detach_timer(timer, 1);
459 spin_unlock_irq(&base->t_base.lock);
460 {
461 int preempt_count = preempt_count();
462 fn(data);
463 if (preempt_count != preempt_count()) {
464 printk(KERN_WARNING "huh, entered %p "
465 "with preempt_count %08x, exited"
466 " with %08x?\n",
467 fn, preempt_count,
468 preempt_count());
469 BUG();
470 }
471 }
472 spin_lock_irq(&base->t_base.lock);
473 }
474 }
475 set_running_timer(base, NULL);
476 spin_unlock_irq(&base->t_base.lock);
477}
478
479#ifdef CONFIG_NO_IDLE_HZ
480/*
481 * Find out when the next timer event is due to happen. This
482 * is used on S/390 to stop all activity when a cpus is idle.
483 * This functions needs to be called disabled.
484 */
485unsigned long next_timer_interrupt(void)
486{
487 tvec_base_t *base;
488 struct list_head *list;
489 struct timer_list *nte;
490 unsigned long expires;
491 tvec_t *varray[4];
492 int i, j;
493
494 base = &__get_cpu_var(tvec_bases);
495 spin_lock(&base->t_base.lock);
496 expires = base->timer_jiffies + (LONG_MAX >> 1);
497 list = 0;
498
499 /* Look for timer events in tv1. */
500 j = base->timer_jiffies & TVR_MASK;
501 do {
502 list_for_each_entry(nte, base->tv1.vec + j, entry) {
503 expires = nte->expires;
504 if (j < (base->timer_jiffies & TVR_MASK))
505 list = base->tv2.vec + (INDEX(0));
506 goto found;
507 }
508 j = (j + 1) & TVR_MASK;
509 } while (j != (base->timer_jiffies & TVR_MASK));
510
511 /* Check tv2-tv5. */
512 varray[0] = &base->tv2;
513 varray[1] = &base->tv3;
514 varray[2] = &base->tv4;
515 varray[3] = &base->tv5;
516 for (i = 0; i < 4; i++) {
517 j = INDEX(i);
518 do {
519 if (list_empty(varray[i]->vec + j)) {
520 j = (j + 1) & TVN_MASK;
521 continue;
522 }
523 list_for_each_entry(nte, varray[i]->vec + j, entry)
524 if (time_before(nte->expires, expires))
525 expires = nte->expires;
526 if (j < (INDEX(i)) && i < 3)
527 list = varray[i + 1]->vec + (INDEX(i + 1));
528 goto found;
529 } while (j != (INDEX(i)));
530 }
531found:
532 if (list) {
533 /*
534 * The search wrapped. We need to look at the next list
535 * from next tv element that would cascade into tv element
536 * where we found the timer element.
537 */
538 list_for_each_entry(nte, list, entry) {
539 if (time_before(nte->expires, expires))
540 expires = nte->expires;
541 }
542 }
543 spin_unlock(&base->t_base.lock);
544 return expires;
545}
546#endif
547
548/******************************************************************/
549
550/*
551 * Timekeeping variables
552 */
553unsigned long tick_usec = TICK_USEC; /* USER_HZ period (usec) */
554unsigned long tick_nsec = TICK_NSEC; /* ACTHZ period (nsec) */
555
556/*
557 * The current time
558 * wall_to_monotonic is what we need to add to xtime (or xtime corrected
559 * for sub jiffie times) to get to monotonic time. Monotonic is pegged
560 * at zero at system boot time, so wall_to_monotonic will be negative,
561 * however, we will ALWAYS keep the tv_nsec part positive so we can use
562 * the usual normalization.
563 */
564struct timespec xtime __attribute__ ((aligned (16)));
565struct timespec wall_to_monotonic __attribute__ ((aligned (16)));
566
567EXPORT_SYMBOL(xtime);
568
569/* Don't completely fail for HZ > 500. */
570int tickadj = 500/HZ ? : 1; /* microsecs */
571
572
573/*
574 * phase-lock loop variables
575 */
576/* TIME_ERROR prevents overwriting the CMOS clock */
577int time_state = TIME_OK; /* clock synchronization status */
578int time_status = STA_UNSYNC; /* clock status bits */
579long time_offset; /* time adjustment (us) */
580long time_constant = 2; /* pll time constant */
581long time_tolerance = MAXFREQ; /* frequency tolerance (ppm) */
582long time_precision = 1; /* clock precision (us) */
583long time_maxerror = NTP_PHASE_LIMIT; /* maximum error (us) */
584long time_esterror = NTP_PHASE_LIMIT; /* estimated error (us) */
585static long time_phase; /* phase offset (scaled us) */
586long time_freq = (((NSEC_PER_SEC + HZ/2) % HZ - HZ/2) << SHIFT_USEC) / NSEC_PER_USEC;
587 /* frequency offset (scaled ppm)*/
588static long time_adj; /* tick adjust (scaled 1 / HZ) */
589long time_reftime; /* time at last adjustment (s) */
590long time_adjust;
591long time_next_adjust;
592
593/*
594 * this routine handles the overflow of the microsecond field
595 *
596 * The tricky bits of code to handle the accurate clock support
597 * were provided by Dave Mills ([email protected]) of NTP fame.
598 * They were originally developed for SUN and DEC kernels.
599 * All the kudos should go to Dave for this stuff.
600 *
601 */
602static void second_overflow(void)
603{
604 long ltemp;
605
606 /* Bump the maxerror field */
607 time_maxerror += time_tolerance >> SHIFT_USEC;
608 if (time_maxerror > NTP_PHASE_LIMIT) {
609 time_maxerror = NTP_PHASE_LIMIT;
610 time_status |= STA_UNSYNC;
611 }
612
613 /*
614 * Leap second processing. If in leap-insert state at the end of the
615 * day, the system clock is set back one second; if in leap-delete
616 * state, the system clock is set ahead one second. The microtime()
617 * routine or external clock driver will insure that reported time is
618 * always monotonic. The ugly divides should be replaced.
619 */
620 switch (time_state) {
621 case TIME_OK:
622 if (time_status & STA_INS)
623 time_state = TIME_INS;
624 else if (time_status & STA_DEL)
625 time_state = TIME_DEL;
626 break;
627 case TIME_INS:
628 if (xtime.tv_sec % 86400 == 0) {
629 xtime.tv_sec--;
630 wall_to_monotonic.tv_sec++;
631 /*
632 * The timer interpolator will make time change
633 * gradually instead of an immediate jump by one second
634 */
635 time_interpolator_update(-NSEC_PER_SEC);
636 time_state = TIME_OOP;
637 clock_was_set();
638 printk(KERN_NOTICE "Clock: inserting leap second "
639 "23:59:60 UTC\n");
640 }
641 break;
642 case TIME_DEL:
643 if ((xtime.tv_sec + 1) % 86400 == 0) {
644 xtime.tv_sec++;
645 wall_to_monotonic.tv_sec--;
646 /*
647 * Use of time interpolator for a gradual change of
648 * time
649 */
650 time_interpolator_update(NSEC_PER_SEC);
651 time_state = TIME_WAIT;
652 clock_was_set();
653 printk(KERN_NOTICE "Clock: deleting leap second "
654 "23:59:59 UTC\n");
655 }
656 break;
657 case TIME_OOP:
658 time_state = TIME_WAIT;
659 break;
660 case TIME_WAIT:
661 if (!(time_status & (STA_INS | STA_DEL)))
662 time_state = TIME_OK;
663 }
664
665 /*
666 * Compute the phase adjustment for the next second. In PLL mode, the
667 * offset is reduced by a fixed factor times the time constant. In FLL
668 * mode the offset is used directly. In either mode, the maximum phase
669 * adjustment for each second is clamped so as to spread the adjustment
670 * over not more than the number of seconds between updates.
671 */
672 ltemp = time_offset;
673 if (!(time_status & STA_FLL))
674 ltemp = shift_right(ltemp, SHIFT_KG + time_constant);
675 ltemp = min(ltemp, (MAXPHASE / MINSEC) << SHIFT_UPDATE);
676 ltemp = max(ltemp, -(MAXPHASE / MINSEC) << SHIFT_UPDATE);
677 time_offset -= ltemp;
678 time_adj = ltemp << (SHIFT_SCALE - SHIFT_HZ - SHIFT_UPDATE);
679
680 /*
681 * Compute the frequency estimate and additional phase adjustment due
682 * to frequency error for the next second. When the PPS signal is
683 * engaged, gnaw on the watchdog counter and update the frequency
684 * computed by the pll and the PPS signal.
685 */
686 pps_valid++;
687 if (pps_valid == PPS_VALID) { /* PPS signal lost */
688 pps_jitter = MAXTIME;
689 pps_stabil = MAXFREQ;
690 time_status &= ~(STA_PPSSIGNAL | STA_PPSJITTER |
691 STA_PPSWANDER | STA_PPSERROR);
692 }
693 ltemp = time_freq + pps_freq;
694 time_adj += shift_right(ltemp,(SHIFT_USEC + SHIFT_HZ - SHIFT_SCALE));
695
696#if HZ == 100
697 /*
698 * Compensate for (HZ==100) != (1 << SHIFT_HZ). Add 25% and 3.125% to
699 * get 128.125; => only 0.125% error (p. 14)
700 */
701 time_adj += shift_right(time_adj, 2) + shift_right(time_adj, 5);
702#endif
703#if HZ == 250
704 /*
705 * Compensate for (HZ==250) != (1 << SHIFT_HZ). Add 1.5625% and
706 * 0.78125% to get 255.85938; => only 0.05% error (p. 14)
707 */
708 time_adj += shift_right(time_adj, 6) + shift_right(time_adj, 7);
709#endif
710#if HZ == 1000
711 /*
712 * Compensate for (HZ==1000) != (1 << SHIFT_HZ). Add 1.5625% and
713 * 0.78125% to get 1023.4375; => only 0.05% error (p. 14)
714 */
715 time_adj += shift_right(time_adj, 6) + shift_right(time_adj, 7);
716#endif
717}
718
719/* in the NTP reference this is called "hardclock()" */
720static void update_wall_time_one_tick(void)
721{
722 long time_adjust_step, delta_nsec;
723
724 if ((time_adjust_step = time_adjust) != 0 ) {
725 /*
726 * We are doing an adjtime thing. Prepare time_adjust_step to
727 * be within bounds. Note that a positive time_adjust means we
728 * want the clock to run faster.
729 *
730 * Limit the amount of the step to be in the range
731 * -tickadj .. +tickadj
732 */
733 time_adjust_step = min(time_adjust_step, (long)tickadj);
734 time_adjust_step = max(time_adjust_step, (long)-tickadj);
735
736 /* Reduce by this step the amount of time left */
737 time_adjust -= time_adjust_step;
738 }
739 delta_nsec = tick_nsec + time_adjust_step * 1000;
740 /*
741 * Advance the phase, once it gets to one microsecond, then
742 * advance the tick more.
743 */
744 time_phase += time_adj;
745 if ((time_phase >= FINENSEC) || (time_phase <= -FINENSEC)) {
746 long ltemp = shift_right(time_phase, (SHIFT_SCALE - 10));
747 time_phase -= ltemp << (SHIFT_SCALE - 10);
748 delta_nsec += ltemp;
749 }
750 xtime.tv_nsec += delta_nsec;
751 time_interpolator_update(delta_nsec);
752
753 /* Changes by adjtime() do not take effect till next tick. */
754 if (time_next_adjust != 0) {
755 time_adjust = time_next_adjust;
756 time_next_adjust = 0;
757 }
758}
759
760/*
761 * Using a loop looks inefficient, but "ticks" is
762 * usually just one (we shouldn't be losing ticks,
763 * we're doing this this way mainly for interrupt
764 * latency reasons, not because we think we'll
765 * have lots of lost timer ticks
766 */
767static void update_wall_time(unsigned long ticks)
768{
769 do {
770 ticks--;
771 update_wall_time_one_tick();
772 if (xtime.tv_nsec >= 1000000000) {
773 xtime.tv_nsec -= 1000000000;
774 xtime.tv_sec++;
775 second_overflow();
776 }
777 } while (ticks);
778}
779
780/*
781 * Called from the timer interrupt handler to charge one tick to the current
782 * process. user_tick is 1 if the tick is user time, 0 for system.
783 */
784void update_process_times(int user_tick)
785{
786 struct task_struct *p = current;
787 int cpu = smp_processor_id();
788
789 /* Note: this timer irq context must be accounted for as well. */
790 if (user_tick)
791 account_user_time(p, jiffies_to_cputime(1));
792 else
793 account_system_time(p, HARDIRQ_OFFSET, jiffies_to_cputime(1));
794 run_local_timers();
795 if (rcu_pending(cpu))
796 rcu_check_callbacks(cpu, user_tick);
797 scheduler_tick();
798 run_posix_cpu_timers(p);
799}
800
801/*
802 * Nr of active tasks - counted in fixed-point numbers
803 */
804static unsigned long count_active_tasks(void)
805{
806 return (nr_running() + nr_uninterruptible()) * FIXED_1;
807}
808
809/*
810 * Hmm.. Changed this, as the GNU make sources (load.c) seems to
811 * imply that avenrun[] is the standard name for this kind of thing.
812 * Nothing else seems to be standardized: the fractional size etc
813 * all seem to differ on different machines.
814 *
815 * Requires xtime_lock to access.
816 */
817unsigned long avenrun[3];
818
819EXPORT_SYMBOL(avenrun);
820
821/*
822 * calc_load - given tick count, update the avenrun load estimates.
823 * This is called while holding a write_lock on xtime_lock.
824 */
825static inline void calc_load(unsigned long ticks)
826{
827 unsigned long active_tasks; /* fixed-point */
828 static int count = LOAD_FREQ;
829
830 count -= ticks;
831 if (count < 0) {
832 count += LOAD_FREQ;
833 active_tasks = count_active_tasks();
834 CALC_LOAD(avenrun[0], EXP_1, active_tasks);
835 CALC_LOAD(avenrun[1], EXP_5, active_tasks);
836 CALC_LOAD(avenrun[2], EXP_15, active_tasks);
837 }
838}
839
840/* jiffies at the most recent update of wall time */
841unsigned long wall_jiffies = INITIAL_JIFFIES;
842
843/*
844 * This read-write spinlock protects us from races in SMP while
845 * playing with xtime and avenrun.
846 */
847#ifndef ARCH_HAVE_XTIME_LOCK
848seqlock_t xtime_lock __cacheline_aligned_in_smp = SEQLOCK_UNLOCKED;
849
850EXPORT_SYMBOL(xtime_lock);
851#endif
852
853/*
854 * This function runs timers and the timer-tq in bottom half context.
855 */
856static void run_timer_softirq(struct softirq_action *h)
857{
858 tvec_base_t *base = &__get_cpu_var(tvec_bases);
859
860 if (time_after_eq(jiffies, base->timer_jiffies))
861 __run_timers(base);
862}
863
864/*
865 * Called by the local, per-CPU timer interrupt on SMP.
866 */
867void run_local_timers(void)
868{
869 raise_softirq(TIMER_SOFTIRQ);
870}
871
872/*
873 * Called by the timer interrupt. xtime_lock must already be taken
874 * by the timer IRQ!
875 */
876static inline void update_times(void)
877{
878 unsigned long ticks;
879
880 ticks = jiffies - wall_jiffies;
881 if (ticks) {
882 wall_jiffies += ticks;
883 update_wall_time(ticks);
884 }
885 calc_load(ticks);
886}
887
888/*
889 * The 64-bit jiffies value is not atomic - you MUST NOT read it
890 * without sampling the sequence number in xtime_lock.
891 * jiffies is defined in the linker script...
892 */
893
894void do_timer(struct pt_regs *regs)
895{
896 jiffies_64++;
897 update_times();
898 softlockup_tick(regs);
899}
900
901#ifdef __ARCH_WANT_SYS_ALARM
902
903/*
904 * For backwards compatibility? This can be done in libc so Alpha
905 * and all newer ports shouldn't need it.
906 */
907asmlinkage unsigned long sys_alarm(unsigned int seconds)
908{
909 struct itimerval it_new, it_old;
910 unsigned int oldalarm;
911
912 it_new.it_interval.tv_sec = it_new.it_interval.tv_usec = 0;
913 it_new.it_value.tv_sec = seconds;
914 it_new.it_value.tv_usec = 0;
915 do_setitimer(ITIMER_REAL, &it_new, &it_old);
916 oldalarm = it_old.it_value.tv_sec;
917 /* ehhh.. We can't return 0 if we have an alarm pending.. */
918 /* And we'd better return too much than too little anyway */
919 if ((!oldalarm && it_old.it_value.tv_usec) || it_old.it_value.tv_usec >= 500000)
920 oldalarm++;
921 return oldalarm;
922}
923
924#endif
925
926#ifndef __alpha__
927
928/*
929 * The Alpha uses getxpid, getxuid, and getxgid instead. Maybe this
930 * should be moved into arch/i386 instead?
931 */
932
933/**
934 * sys_getpid - return the thread group id of the current process
935 *
936 * Note, despite the name, this returns the tgid not the pid. The tgid and
937 * the pid are identical unless CLONE_THREAD was specified on clone() in
938 * which case the tgid is the same in all threads of the same group.
939 *
940 * This is SMP safe as current->tgid does not change.
941 */
942asmlinkage long sys_getpid(void)
943{
944 return current->tgid;
945}
946
947/*
948 * Accessing ->group_leader->real_parent is not SMP-safe, it could
949 * change from under us. However, rather than getting any lock
950 * we can use an optimistic algorithm: get the parent
951 * pid, and go back and check that the parent is still
952 * the same. If it has changed (which is extremely unlikely
953 * indeed), we just try again..
954 *
955 * NOTE! This depends on the fact that even if we _do_
956 * get an old value of "parent", we can happily dereference
957 * the pointer (it was and remains a dereferencable kernel pointer
958 * no matter what): we just can't necessarily trust the result
959 * until we know that the parent pointer is valid.
960 *
961 * NOTE2: ->group_leader never changes from under us.
962 */
963asmlinkage long sys_getppid(void)
964{
965 int pid;
966 struct task_struct *me = current;
967 struct task_struct *parent;
968
969 parent = me->group_leader->real_parent;
970 for (;;) {
971 pid = parent->tgid;
972#if defined(CONFIG_SMP) || defined(CONFIG_PREEMPT)
973{
974 struct task_struct *old = parent;
975
976 /*
977 * Make sure we read the pid before re-reading the
978 * parent pointer:
979 */
980 smp_rmb();
981 parent = me->group_leader->real_parent;
982 if (old != parent)
983 continue;
984}
985#endif
986 break;
987 }
988 return pid;
989}
990
991asmlinkage long sys_getuid(void)
992{
993 /* Only we change this so SMP safe */
994 return current->uid;
995}
996
997asmlinkage long sys_geteuid(void)
998{
999 /* Only we change this so SMP safe */
1000 return current->euid;
1001}
1002
1003asmlinkage long sys_getgid(void)
1004{
1005 /* Only we change this so SMP safe */
1006 return current->gid;
1007}
1008
1009asmlinkage long sys_getegid(void)
1010{
1011 /* Only we change this so SMP safe */
1012 return current->egid;
1013}
1014
1015#endif
1016
1017static void process_timeout(unsigned long __data)
1018{
1019 wake_up_process((task_t *)__data);
1020}
1021
1022/**
1023 * schedule_timeout - sleep until timeout
1024 * @timeout: timeout value in jiffies
1025 *
1026 * Make the current task sleep until @timeout jiffies have
1027 * elapsed. The routine will return immediately unless
1028 * the current task state has been set (see set_current_state()).
1029 *
1030 * You can set the task state as follows -
1031 *
1032 * %TASK_UNINTERRUPTIBLE - at least @timeout jiffies are guaranteed to
1033 * pass before the routine returns. The routine will return 0
1034 *
1035 * %TASK_INTERRUPTIBLE - the routine may return early if a signal is
1036 * delivered to the current task. In this case the remaining time
1037 * in jiffies will be returned, or 0 if the timer expired in time
1038 *
1039 * The current task state is guaranteed to be TASK_RUNNING when this
1040 * routine returns.
1041 *
1042 * Specifying a @timeout value of %MAX_SCHEDULE_TIMEOUT will schedule
1043 * the CPU away without a bound on the timeout. In this case the return
1044 * value will be %MAX_SCHEDULE_TIMEOUT.
1045 *
1046 * In all cases the return value is guaranteed to be non-negative.
1047 */
1048fastcall signed long __sched schedule_timeout(signed long timeout)
1049{
1050 struct timer_list timer;
1051 unsigned long expire;
1052
1053 switch (timeout)
1054 {
1055 case MAX_SCHEDULE_TIMEOUT:
1056 /*
1057 * These two special cases are useful to be comfortable
1058 * in the caller. Nothing more. We could take
1059 * MAX_SCHEDULE_TIMEOUT from one of the negative value
1060 * but I' d like to return a valid offset (>=0) to allow
1061 * the caller to do everything it want with the retval.
1062 */
1063 schedule();
1064 goto out;
1065 default:
1066 /*
1067 * Another bit of PARANOID. Note that the retval will be
1068 * 0 since no piece of kernel is supposed to do a check
1069 * for a negative retval of schedule_timeout() (since it
1070 * should never happens anyway). You just have the printk()
1071 * that will tell you if something is gone wrong and where.
1072 */
1073 if (timeout < 0)
1074 {
1075 printk(KERN_ERR "schedule_timeout: wrong timeout "
1076 "value %lx from %p\n", timeout,
1077 __builtin_return_address(0));
1078 current->state = TASK_RUNNING;
1079 goto out;
1080 }
1081 }
1082
1083 expire = timeout + jiffies;
1084
1085 setup_timer(&timer, process_timeout, (unsigned long)current);
1086 __mod_timer(&timer, expire);
1087 schedule();
1088 del_singleshot_timer_sync(&timer);
1089
1090 timeout = expire - jiffies;
1091
1092 out:
1093 return timeout < 0 ? 0 : timeout;
1094}
1095EXPORT_SYMBOL(schedule_timeout);
1096
1097/*
1098 * We can use __set_current_state() here because schedule_timeout() calls
1099 * schedule() unconditionally.
1100 */
1101signed long __sched schedule_timeout_interruptible(signed long timeout)
1102{
1103 __set_current_state(TASK_INTERRUPTIBLE);
1104 return schedule_timeout(timeout);
1105}
1106EXPORT_SYMBOL(schedule_timeout_interruptible);
1107
1108signed long __sched schedule_timeout_uninterruptible(signed long timeout)
1109{
1110 __set_current_state(TASK_UNINTERRUPTIBLE);
1111 return schedule_timeout(timeout);
1112}
1113EXPORT_SYMBOL(schedule_timeout_uninterruptible);
1114
1115/* Thread ID - the internal kernel "pid" */
1116asmlinkage long sys_gettid(void)
1117{
1118 return current->pid;
1119}
1120
1121static long __sched nanosleep_restart(struct restart_block *restart)
1122{
1123 unsigned long expire = restart->arg0, now = jiffies;
1124 struct timespec __user *rmtp = (struct timespec __user *) restart->arg1;
1125 long ret;
1126
1127 /* Did it expire while we handled signals? */
1128 if (!time_after(expire, now))
1129 return 0;
1130
1131 expire = schedule_timeout_interruptible(expire - now);
1132
1133 ret = 0;
1134 if (expire) {
1135 struct timespec t;
1136 jiffies_to_timespec(expire, &t);
1137
1138 ret = -ERESTART_RESTARTBLOCK;
1139 if (rmtp && copy_to_user(rmtp, &t, sizeof(t)))
1140 ret = -EFAULT;
1141 /* The 'restart' block is already filled in */
1142 }
1143 return ret;
1144}
1145
1146asmlinkage long sys_nanosleep(struct timespec __user *rqtp, struct timespec __user *rmtp)
1147{
1148 struct timespec t;
1149 unsigned long expire;
1150 long ret;
1151
1152 if (copy_from_user(&t, rqtp, sizeof(t)))
1153 return -EFAULT;
1154
1155 if ((t.tv_nsec >= 1000000000L) || (t.tv_nsec < 0) || (t.tv_sec < 0))
1156 return -EINVAL;
1157
1158 expire = timespec_to_jiffies(&t) + (t.tv_sec || t.tv_nsec);
1159 expire = schedule_timeout_interruptible(expire);
1160
1161 ret = 0;
1162 if (expire) {
1163 struct restart_block *restart;
1164 jiffies_to_timespec(expire, &t);
1165 if (rmtp && copy_to_user(rmtp, &t, sizeof(t)))
1166 return -EFAULT;
1167
1168 restart = &current_thread_info()->restart_block;
1169 restart->fn = nanosleep_restart;
1170 restart->arg0 = jiffies + expire;
1171 restart->arg1 = (unsigned long) rmtp;
1172 ret = -ERESTART_RESTARTBLOCK;
1173 }
1174 return ret;
1175}
1176
1177/*
1178 * sys_sysinfo - fill in sysinfo struct
1179 */
1180asmlinkage long sys_sysinfo(struct sysinfo __user *info)
1181{
1182 struct sysinfo val;
1183 unsigned long mem_total, sav_total;
1184 unsigned int mem_unit, bitcount;
1185 unsigned long seq;
1186
1187 memset((char *)&val, 0, sizeof(struct sysinfo));
1188
1189 do {
1190 struct timespec tp;
1191 seq = read_seqbegin(&xtime_lock);
1192
1193 /*
1194 * This is annoying. The below is the same thing
1195 * posix_get_clock_monotonic() does, but it wants to
1196 * take the lock which we want to cover the loads stuff
1197 * too.
1198 */
1199
1200 getnstimeofday(&tp);
1201 tp.tv_sec += wall_to_monotonic.tv_sec;
1202 tp.tv_nsec += wall_to_monotonic.tv_nsec;
1203 if (tp.tv_nsec - NSEC_PER_SEC >= 0) {
1204 tp.tv_nsec = tp.tv_nsec - NSEC_PER_SEC;
1205 tp.tv_sec++;
1206 }
1207 val.uptime = tp.tv_sec + (tp.tv_nsec ? 1 : 0);
1208
1209 val.loads[0] = avenrun[0] << (SI_LOAD_SHIFT - FSHIFT);
1210 val.loads[1] = avenrun[1] << (SI_LOAD_SHIFT - FSHIFT);
1211 val.loads[2] = avenrun[2] << (SI_LOAD_SHIFT - FSHIFT);
1212
1213 val.procs = nr_threads;
1214 } while (read_seqretry(&xtime_lock, seq));
1215
1216 si_meminfo(&val);
1217 si_swapinfo(&val);
1218
1219 /*
1220 * If the sum of all the available memory (i.e. ram + swap)
1221 * is less than can be stored in a 32 bit unsigned long then
1222 * we can be binary compatible with 2.2.x kernels. If not,
1223 * well, in that case 2.2.x was broken anyways...
1224 *
1225 * -Erik Andersen <[email protected]>
1226 */
1227
1228 mem_total = val.totalram + val.totalswap;
1229 if (mem_total < val.totalram || mem_total < val.totalswap)
1230 goto out;
1231 bitcount = 0;
1232 mem_unit = val.mem_unit;
1233 while (mem_unit > 1) {
1234 bitcount++;
1235 mem_unit >>= 1;
1236 sav_total = mem_total;
1237 mem_total <<= 1;
1238 if (mem_total < sav_total)
1239 goto out;
1240 }
1241
1242 /*
1243 * If mem_total did not overflow, multiply all memory values by
1244 * val.mem_unit and set it to 1. This leaves things compatible
1245 * with 2.2.x, and also retains compatibility with earlier 2.4.x
1246 * kernels...
1247 */
1248
1249 val.mem_unit = 1;
1250 val.totalram <<= bitcount;
1251 val.freeram <<= bitcount;
1252 val.sharedram <<= bitcount;
1253 val.bufferram <<= bitcount;
1254 val.totalswap <<= bitcount;
1255 val.freeswap <<= bitcount;
1256 val.totalhigh <<= bitcount;
1257 val.freehigh <<= bitcount;
1258
1259 out:
1260 if (copy_to_user(info, &val, sizeof(struct sysinfo)))
1261 return -EFAULT;
1262
1263 return 0;
1264}
1265
1266static void __devinit init_timers_cpu(int cpu)
1267{
1268 int j;
1269 tvec_base_t *base;
1270
1271 base = &per_cpu(tvec_bases, cpu);
1272 spin_lock_init(&base->t_base.lock);
1273 for (j = 0; j < TVN_SIZE; j++) {
1274 INIT_LIST_HEAD(base->tv5.vec + j);
1275 INIT_LIST_HEAD(base->tv4.vec + j);
1276 INIT_LIST_HEAD(base->tv3.vec + j);
1277 INIT_LIST_HEAD(base->tv2.vec + j);
1278 }
1279 for (j = 0; j < TVR_SIZE; j++)
1280 INIT_LIST_HEAD(base->tv1.vec + j);
1281
1282 base->timer_jiffies = jiffies;
1283}
1284
1285#ifdef CONFIG_HOTPLUG_CPU
1286static void migrate_timer_list(tvec_base_t *new_base, struct list_head *head)
1287{
1288 struct timer_list *timer;
1289
1290 while (!list_empty(head)) {
1291 timer = list_entry(head->next, struct timer_list, entry);
1292 detach_timer(timer, 0);
1293 timer->base = &new_base->t_base;
1294 internal_add_timer(new_base, timer);
1295 }
1296}
1297
1298static void __devinit migrate_timers(int cpu)
1299{
1300 tvec_base_t *old_base;
1301 tvec_base_t *new_base;
1302 int i;
1303
1304 BUG_ON(cpu_online(cpu));
1305 old_base = &per_cpu(tvec_bases, cpu);
1306 new_base = &get_cpu_var(tvec_bases);
1307
1308 local_irq_disable();
1309 spin_lock(&new_base->t_base.lock);
1310 spin_lock(&old_base->t_base.lock);
1311
1312 if (old_base->t_base.running_timer)
1313 BUG();
1314 for (i = 0; i < TVR_SIZE; i++)
1315 migrate_timer_list(new_base, old_base->tv1.vec + i);
1316 for (i = 0; i < TVN_SIZE; i++) {
1317 migrate_timer_list(new_base, old_base->tv2.vec + i);
1318 migrate_timer_list(new_base, old_base->tv3.vec + i);
1319 migrate_timer_list(new_base, old_base->tv4.vec + i);
1320 migrate_timer_list(new_base, old_base->tv5.vec + i);
1321 }
1322
1323 spin_unlock(&old_base->t_base.lock);
1324 spin_unlock(&new_base->t_base.lock);
1325 local_irq_enable();
1326 put_cpu_var(tvec_bases);
1327}
1328#endif /* CONFIG_HOTPLUG_CPU */
1329
1330static int __devinit timer_cpu_notify(struct notifier_block *self,
1331 unsigned long action, void *hcpu)
1332{
1333 long cpu = (long)hcpu;
1334 switch(action) {
1335 case CPU_UP_PREPARE:
1336 init_timers_cpu(cpu);
1337 break;
1338#ifdef CONFIG_HOTPLUG_CPU
1339 case CPU_DEAD:
1340 migrate_timers(cpu);
1341 break;
1342#endif
1343 default:
1344 break;
1345 }
1346 return NOTIFY_OK;
1347}
1348
1349static struct notifier_block __devinitdata timers_nb = {
1350 .notifier_call = timer_cpu_notify,
1351};
1352
1353
1354void __init init_timers(void)
1355{
1356 timer_cpu_notify(&timers_nb, (unsigned long)CPU_UP_PREPARE,
1357 (void *)(long)smp_processor_id());
1358 register_cpu_notifier(&timers_nb);
1359 open_softirq(TIMER_SOFTIRQ, run_timer_softirq, NULL);
1360}
1361
1362#ifdef CONFIG_TIME_INTERPOLATION
1363
1364struct time_interpolator *time_interpolator;
1365static struct time_interpolator *time_interpolator_list;
1366static DEFINE_SPINLOCK(time_interpolator_lock);
1367
1368static inline u64 time_interpolator_get_cycles(unsigned int src)
1369{
1370 unsigned long (*x)(void);
1371
1372 switch (src)
1373 {
1374 case TIME_SOURCE_FUNCTION:
1375 x = time_interpolator->addr;
1376 return x();
1377
1378 case TIME_SOURCE_MMIO64 :
1379 return readq((void __iomem *) time_interpolator->addr);
1380
1381 case TIME_SOURCE_MMIO32 :
1382 return readl((void __iomem *) time_interpolator->addr);
1383
1384 default: return get_cycles();
1385 }
1386}
1387
1388static inline u64 time_interpolator_get_counter(int writelock)
1389{
1390 unsigned int src = time_interpolator->source;
1391
1392 if (time_interpolator->jitter)
1393 {
1394 u64 lcycle;
1395 u64 now;
1396
1397 do {
1398 lcycle = time_interpolator->last_cycle;
1399 now = time_interpolator_get_cycles(src);
1400 if (lcycle && time_after(lcycle, now))
1401 return lcycle;
1402
1403 /* When holding the xtime write lock, there's no need
1404 * to add the overhead of the cmpxchg. Readers are
1405 * force to retry until the write lock is released.
1406 */
1407 if (writelock) {
1408 time_interpolator->last_cycle = now;
1409 return now;
1410 }
1411 /* Keep track of the last timer value returned. The use of cmpxchg here
1412 * will cause contention in an SMP environment.
1413 */
1414 } while (unlikely(cmpxchg(&time_interpolator->last_cycle, lcycle, now) != lcycle));
1415 return now;
1416 }
1417 else
1418 return time_interpolator_get_cycles(src);
1419}
1420
1421void time_interpolator_reset(void)
1422{
1423 time_interpolator->offset = 0;
1424 time_interpolator->last_counter = time_interpolator_get_counter(1);
1425}
1426
1427#define GET_TI_NSECS(count,i) (((((count) - i->last_counter) & (i)->mask) * (i)->nsec_per_cyc) >> (i)->shift)
1428
1429unsigned long time_interpolator_get_offset(void)
1430{
1431 /* If we do not have a time interpolator set up then just return zero */
1432 if (!time_interpolator)
1433 return 0;
1434
1435 return time_interpolator->offset +
1436 GET_TI_NSECS(time_interpolator_get_counter(0), time_interpolator);
1437}
1438
1439#define INTERPOLATOR_ADJUST 65536
1440#define INTERPOLATOR_MAX_SKIP 10*INTERPOLATOR_ADJUST
1441
1442static void time_interpolator_update(long delta_nsec)
1443{
1444 u64 counter;
1445 unsigned long offset;
1446
1447 /* If there is no time interpolator set up then do nothing */
1448 if (!time_interpolator)
1449 return;
1450
1451 /*
1452 * The interpolator compensates for late ticks by accumulating the late
1453 * time in time_interpolator->offset. A tick earlier than expected will
1454 * lead to a reset of the offset and a corresponding jump of the clock
1455 * forward. Again this only works if the interpolator clock is running
1456 * slightly slower than the regular clock and the tuning logic insures
1457 * that.
1458 */
1459
1460 counter = time_interpolator_get_counter(1);
1461 offset = time_interpolator->offset +
1462 GET_TI_NSECS(counter, time_interpolator);
1463
1464 if (delta_nsec < 0 || (unsigned long) delta_nsec < offset)
1465 time_interpolator->offset = offset - delta_nsec;
1466 else {
1467 time_interpolator->skips++;
1468 time_interpolator->ns_skipped += delta_nsec - offset;
1469 time_interpolator->offset = 0;
1470 }
1471 time_interpolator->last_counter = counter;
1472
1473 /* Tuning logic for time interpolator invoked every minute or so.
1474 * Decrease interpolator clock speed if no skips occurred and an offset is carried.
1475 * Increase interpolator clock speed if we skip too much time.
1476 */
1477 if (jiffies % INTERPOLATOR_ADJUST == 0)
1478 {
1479 if (time_interpolator->skips == 0 && time_interpolator->offset > TICK_NSEC)
1480 time_interpolator->nsec_per_cyc--;
1481 if (time_interpolator->ns_skipped > INTERPOLATOR_MAX_SKIP && time_interpolator->offset == 0)
1482 time_interpolator->nsec_per_cyc++;
1483 time_interpolator->skips = 0;
1484 time_interpolator->ns_skipped = 0;
1485 }
1486}
1487
1488static inline int
1489is_better_time_interpolator(struct time_interpolator *new)
1490{
1491 if (!time_interpolator)
1492 return 1;
1493 return new->frequency > 2*time_interpolator->frequency ||
1494 (unsigned long)new->drift < (unsigned long)time_interpolator->drift;
1495}
1496
1497void
1498register_time_interpolator(struct time_interpolator *ti)
1499{
1500 unsigned long flags;
1501
1502 /* Sanity check */
1503 if (ti->frequency == 0 || ti->mask == 0)
1504 BUG();
1505
1506 ti->nsec_per_cyc = ((u64)NSEC_PER_SEC << ti->shift) / ti->frequency;
1507 spin_lock(&time_interpolator_lock);
1508 write_seqlock_irqsave(&xtime_lock, flags);
1509 if (is_better_time_interpolator(ti)) {
1510 time_interpolator = ti;
1511 time_interpolator_reset();
1512 }
1513 write_sequnlock_irqrestore(&xtime_lock, flags);
1514
1515 ti->next = time_interpolator_list;
1516 time_interpolator_list = ti;
1517 spin_unlock(&time_interpolator_lock);
1518}
1519
1520void
1521unregister_time_interpolator(struct time_interpolator *ti)
1522{
1523 struct time_interpolator *curr, **prev;
1524 unsigned long flags;
1525
1526 spin_lock(&time_interpolator_lock);
1527 prev = &time_interpolator_list;
1528 for (curr = *prev; curr; curr = curr->next) {
1529 if (curr == ti) {
1530 *prev = curr->next;
1531 break;
1532 }
1533 prev = &curr->next;
1534 }
1535
1536 write_seqlock_irqsave(&xtime_lock, flags);
1537 if (ti == time_interpolator) {
1538 /* we lost the best time-interpolator: */
1539 time_interpolator = NULL;
1540 /* find the next-best interpolator */
1541 for (curr = time_interpolator_list; curr; curr = curr->next)
1542 if (is_better_time_interpolator(curr))
1543 time_interpolator = curr;
1544 time_interpolator_reset();
1545 }
1546 write_sequnlock_irqrestore(&xtime_lock, flags);
1547 spin_unlock(&time_interpolator_lock);
1548}
1549#endif /* CONFIG_TIME_INTERPOLATION */
1550
1551/**
1552 * msleep - sleep safely even with waitqueue interruptions
1553 * @msecs: Time in milliseconds to sleep for
1554 */
1555void msleep(unsigned int msecs)
1556{
1557 unsigned long timeout = msecs_to_jiffies(msecs) + 1;
1558
1559 while (timeout)
1560 timeout = schedule_timeout_uninterruptible(timeout);
1561}
1562
1563EXPORT_SYMBOL(msleep);
1564
1565/**
1566 * msleep_interruptible - sleep waiting for signals
1567 * @msecs: Time in milliseconds to sleep for
1568 */
1569unsigned long msleep_interruptible(unsigned int msecs)
1570{
1571 unsigned long timeout = msecs_to_jiffies(msecs) + 1;
1572
1573 while (timeout && !signal_pending(current))
1574 timeout = schedule_timeout_interruptible(timeout);
1575 return jiffies_to_msecs(timeout);
1576}
1577
1578EXPORT_SYMBOL(msleep_interruptible);