[PATCH] clockevents: add core functionality
[linux-2.6] / kernel / timer.c
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 #include <linux/delay.h>
37 #include <linux/clockchips.h>
38
39 #include <asm/uaccess.h>
40 #include <asm/unistd.h>
41 #include <asm/div64.h>
42 #include <asm/timex.h>
43 #include <asm/io.h>
44
45 u64 jiffies_64 __cacheline_aligned_in_smp = INITIAL_JIFFIES;
46
47 EXPORT_SYMBOL(jiffies_64);
48
49 /*
50  * per-CPU timer vector definitions:
51  */
52 #define TVN_BITS (CONFIG_BASE_SMALL ? 4 : 6)
53 #define TVR_BITS (CONFIG_BASE_SMALL ? 6 : 8)
54 #define TVN_SIZE (1 << TVN_BITS)
55 #define TVR_SIZE (1 << TVR_BITS)
56 #define TVN_MASK (TVN_SIZE - 1)
57 #define TVR_MASK (TVR_SIZE - 1)
58
59 typedef struct tvec_s {
60         struct list_head vec[TVN_SIZE];
61 } tvec_t;
62
63 typedef struct tvec_root_s {
64         struct list_head vec[TVR_SIZE];
65 } tvec_root_t;
66
67 struct tvec_t_base_s {
68         spinlock_t lock;
69         struct timer_list *running_timer;
70         unsigned long timer_jiffies;
71         tvec_root_t tv1;
72         tvec_t tv2;
73         tvec_t tv3;
74         tvec_t tv4;
75         tvec_t tv5;
76 } ____cacheline_aligned_in_smp;
77
78 typedef struct tvec_t_base_s tvec_base_t;
79
80 tvec_base_t boot_tvec_bases;
81 EXPORT_SYMBOL(boot_tvec_bases);
82 static DEFINE_PER_CPU(tvec_base_t *, tvec_bases) = &boot_tvec_bases;
83
84 /**
85  * __round_jiffies - function to round jiffies to a full second
86  * @j: the time in (absolute) jiffies that should be rounded
87  * @cpu: the processor number on which the timeout will happen
88  *
89  * __round_jiffies() rounds an absolute time in the future (in jiffies)
90  * up or down to (approximately) full seconds. This is useful for timers
91  * for which the exact time they fire does not matter too much, as long as
92  * they fire approximately every X seconds.
93  *
94  * By rounding these timers to whole seconds, all such timers will fire
95  * at the same time, rather than at various times spread out. The goal
96  * of this is to have the CPU wake up less, which saves power.
97  *
98  * The exact rounding is skewed for each processor to avoid all
99  * processors firing at the exact same time, which could lead
100  * to lock contention or spurious cache line bouncing.
101  *
102  * The return value is the rounded version of the @j parameter.
103  */
104 unsigned long __round_jiffies(unsigned long j, int cpu)
105 {
106         int rem;
107         unsigned long original = j;
108
109         /*
110          * We don't want all cpus firing their timers at once hitting the
111          * same lock or cachelines, so we skew each extra cpu with an extra
112          * 3 jiffies. This 3 jiffies came originally from the mm/ code which
113          * already did this.
114          * The skew is done by adding 3*cpunr, then round, then subtract this
115          * extra offset again.
116          */
117         j += cpu * 3;
118
119         rem = j % HZ;
120
121         /*
122          * If the target jiffie is just after a whole second (which can happen
123          * due to delays of the timer irq, long irq off times etc etc) then
124          * we should round down to the whole second, not up. Use 1/4th second
125          * as cutoff for this rounding as an extreme upper bound for this.
126          */
127         if (rem < HZ/4) /* round down */
128                 j = j - rem;
129         else /* round up */
130                 j = j - rem + HZ;
131
132         /* now that we have rounded, subtract the extra skew again */
133         j -= cpu * 3;
134
135         if (j <= jiffies) /* rounding ate our timeout entirely; */
136                 return original;
137         return j;
138 }
139 EXPORT_SYMBOL_GPL(__round_jiffies);
140
141 /**
142  * __round_jiffies_relative - function to round jiffies to a full second
143  * @j: the time in (relative) jiffies that should be rounded
144  * @cpu: the processor number on which the timeout will happen
145  *
146  * __round_jiffies_relative() rounds a time delta  in the future (in jiffies)
147  * up or down to (approximately) full seconds. This is useful for timers
148  * for which the exact time they fire does not matter too much, as long as
149  * they fire approximately every X seconds.
150  *
151  * By rounding these timers to whole seconds, all such timers will fire
152  * at the same time, rather than at various times spread out. The goal
153  * of this is to have the CPU wake up less, which saves power.
154  *
155  * The exact rounding is skewed for each processor to avoid all
156  * processors firing at the exact same time, which could lead
157  * to lock contention or spurious cache line bouncing.
158  *
159  * The return value is the rounded version of the @j parameter.
160  */
161 unsigned long __round_jiffies_relative(unsigned long j, int cpu)
162 {
163         /*
164          * In theory the following code can skip a jiffy in case jiffies
165          * increments right between the addition and the later subtraction.
166          * However since the entire point of this function is to use approximate
167          * timeouts, it's entirely ok to not handle that.
168          */
169         return  __round_jiffies(j + jiffies, cpu) - jiffies;
170 }
171 EXPORT_SYMBOL_GPL(__round_jiffies_relative);
172
173 /**
174  * round_jiffies - function to round jiffies to a full second
175  * @j: the time in (absolute) jiffies that should be rounded
176  *
177  * round_jiffies() rounds an absolute time in the future (in jiffies)
178  * up or down to (approximately) full seconds. This is useful for timers
179  * for which the exact time they fire does not matter too much, as long as
180  * they fire approximately every X seconds.
181  *
182  * By rounding these timers to whole seconds, all such timers will fire
183  * at the same time, rather than at various times spread out. The goal
184  * of this is to have the CPU wake up less, which saves power.
185  *
186  * The return value is the rounded version of the @j parameter.
187  */
188 unsigned long round_jiffies(unsigned long j)
189 {
190         return __round_jiffies(j, raw_smp_processor_id());
191 }
192 EXPORT_SYMBOL_GPL(round_jiffies);
193
194 /**
195  * round_jiffies_relative - function to round jiffies to a full second
196  * @j: the time in (relative) jiffies that should be rounded
197  *
198  * round_jiffies_relative() rounds a time delta  in the future (in jiffies)
199  * up or down to (approximately) full seconds. This is useful for timers
200  * for which the exact time they fire does not matter too much, as long as
201  * they fire approximately every X seconds.
202  *
203  * By rounding these timers to whole seconds, all such timers will fire
204  * at the same time, rather than at various times spread out. The goal
205  * of this is to have the CPU wake up less, which saves power.
206  *
207  * The return value is the rounded version of the @j parameter.
208  */
209 unsigned long round_jiffies_relative(unsigned long j)
210 {
211         return __round_jiffies_relative(j, raw_smp_processor_id());
212 }
213 EXPORT_SYMBOL_GPL(round_jiffies_relative);
214
215
216 static inline void set_running_timer(tvec_base_t *base,
217                                         struct timer_list *timer)
218 {
219 #ifdef CONFIG_SMP
220         base->running_timer = timer;
221 #endif
222 }
223
224 static void internal_add_timer(tvec_base_t *base, struct timer_list *timer)
225 {
226         unsigned long expires = timer->expires;
227         unsigned long idx = expires - base->timer_jiffies;
228         struct list_head *vec;
229
230         if (idx < TVR_SIZE) {
231                 int i = expires & TVR_MASK;
232                 vec = base->tv1.vec + i;
233         } else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
234                 int i = (expires >> TVR_BITS) & TVN_MASK;
235                 vec = base->tv2.vec + i;
236         } else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) {
237                 int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;
238                 vec = base->tv3.vec + i;
239         } else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) {
240                 int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;
241                 vec = base->tv4.vec + i;
242         } else if ((signed long) idx < 0) {
243                 /*
244                  * Can happen if you add a timer with expires == jiffies,
245                  * or you set a timer to go off in the past
246                  */
247                 vec = base->tv1.vec + (base->timer_jiffies & TVR_MASK);
248         } else {
249                 int i;
250                 /* If the timeout is larger than 0xffffffff on 64-bit
251                  * architectures then we use the maximum timeout:
252                  */
253                 if (idx > 0xffffffffUL) {
254                         idx = 0xffffffffUL;
255                         expires = idx + base->timer_jiffies;
256                 }
257                 i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
258                 vec = base->tv5.vec + i;
259         }
260         /*
261          * Timers are FIFO:
262          */
263         list_add_tail(&timer->entry, vec);
264 }
265
266 /**
267  * init_timer - initialize a timer.
268  * @timer: the timer to be initialized
269  *
270  * init_timer() must be done to a timer prior calling *any* of the
271  * other timer functions.
272  */
273 void fastcall init_timer(struct timer_list *timer)
274 {
275         timer->entry.next = NULL;
276         timer->base = __raw_get_cpu_var(tvec_bases);
277 }
278 EXPORT_SYMBOL(init_timer);
279
280 static inline void detach_timer(struct timer_list *timer,
281                                         int clear_pending)
282 {
283         struct list_head *entry = &timer->entry;
284
285         __list_del(entry->prev, entry->next);
286         if (clear_pending)
287                 entry->next = NULL;
288         entry->prev = LIST_POISON2;
289 }
290
291 /*
292  * We are using hashed locking: holding per_cpu(tvec_bases).lock
293  * means that all timers which are tied to this base via timer->base are
294  * locked, and the base itself is locked too.
295  *
296  * So __run_timers/migrate_timers can safely modify all timers which could
297  * be found on ->tvX lists.
298  *
299  * When the timer's base is locked, and the timer removed from list, it is
300  * possible to set timer->base = NULL and drop the lock: the timer remains
301  * locked.
302  */
303 static tvec_base_t *lock_timer_base(struct timer_list *timer,
304                                         unsigned long *flags)
305         __acquires(timer->base->lock)
306 {
307         tvec_base_t *base;
308
309         for (;;) {
310                 base = timer->base;
311                 if (likely(base != NULL)) {
312                         spin_lock_irqsave(&base->lock, *flags);
313                         if (likely(base == timer->base))
314                                 return base;
315                         /* The timer has migrated to another CPU */
316                         spin_unlock_irqrestore(&base->lock, *flags);
317                 }
318                 cpu_relax();
319         }
320 }
321
322 int __mod_timer(struct timer_list *timer, unsigned long expires)
323 {
324         tvec_base_t *base, *new_base;
325         unsigned long flags;
326         int ret = 0;
327
328         BUG_ON(!timer->function);
329
330         base = lock_timer_base(timer, &flags);
331
332         if (timer_pending(timer)) {
333                 detach_timer(timer, 0);
334                 ret = 1;
335         }
336
337         new_base = __get_cpu_var(tvec_bases);
338
339         if (base != new_base) {
340                 /*
341                  * We are trying to schedule the timer on the local CPU.
342                  * However we can't change timer's base while it is running,
343                  * otherwise del_timer_sync() can't detect that the timer's
344                  * handler yet has not finished. This also guarantees that
345                  * the timer is serialized wrt itself.
346                  */
347                 if (likely(base->running_timer != timer)) {
348                         /* See the comment in lock_timer_base() */
349                         timer->base = NULL;
350                         spin_unlock(&base->lock);
351                         base = new_base;
352                         spin_lock(&base->lock);
353                         timer->base = base;
354                 }
355         }
356
357         timer->expires = expires;
358         internal_add_timer(base, timer);
359         spin_unlock_irqrestore(&base->lock, flags);
360
361         return ret;
362 }
363
364 EXPORT_SYMBOL(__mod_timer);
365
366 /**
367  * add_timer_on - start a timer on a particular CPU
368  * @timer: the timer to be added
369  * @cpu: the CPU to start it on
370  *
371  * This is not very scalable on SMP. Double adds are not possible.
372  */
373 void add_timer_on(struct timer_list *timer, int cpu)
374 {
375         tvec_base_t *base = per_cpu(tvec_bases, cpu);
376         unsigned long flags;
377
378         BUG_ON(timer_pending(timer) || !timer->function);
379         spin_lock_irqsave(&base->lock, flags);
380         timer->base = base;
381         internal_add_timer(base, timer);
382         spin_unlock_irqrestore(&base->lock, flags);
383 }
384
385
386 /**
387  * mod_timer - modify a timer's timeout
388  * @timer: the timer to be modified
389  * @expires: new timeout in jiffies
390  *
391  * mod_timer() is a more efficient way to update the expire field of an
392  * active timer (if the timer is inactive it will be activated)
393  *
394  * mod_timer(timer, expires) is equivalent to:
395  *
396  *     del_timer(timer); timer->expires = expires; add_timer(timer);
397  *
398  * Note that if there are multiple unserialized concurrent users of the
399  * same timer, then mod_timer() is the only safe way to modify the timeout,
400  * since add_timer() cannot modify an already running timer.
401  *
402  * The function returns whether it has modified a pending timer or not.
403  * (ie. mod_timer() of an inactive timer returns 0, mod_timer() of an
404  * active timer returns 1.)
405  */
406 int mod_timer(struct timer_list *timer, unsigned long expires)
407 {
408         BUG_ON(!timer->function);
409
410         /*
411          * This is a common optimization triggered by the
412          * networking code - if the timer is re-modified
413          * to be the same thing then just return:
414          */
415         if (timer->expires == expires && timer_pending(timer))
416                 return 1;
417
418         return __mod_timer(timer, expires);
419 }
420
421 EXPORT_SYMBOL(mod_timer);
422
423 /**
424  * del_timer - deactive a timer.
425  * @timer: the timer to be deactivated
426  *
427  * del_timer() deactivates a timer - this works on both active and inactive
428  * timers.
429  *
430  * The function returns whether it has deactivated a pending timer or not.
431  * (ie. del_timer() of an inactive timer returns 0, del_timer() of an
432  * active timer returns 1.)
433  */
434 int del_timer(struct timer_list *timer)
435 {
436         tvec_base_t *base;
437         unsigned long flags;
438         int ret = 0;
439
440         if (timer_pending(timer)) {
441                 base = lock_timer_base(timer, &flags);
442                 if (timer_pending(timer)) {
443                         detach_timer(timer, 1);
444                         ret = 1;
445                 }
446                 spin_unlock_irqrestore(&base->lock, flags);
447         }
448
449         return ret;
450 }
451
452 EXPORT_SYMBOL(del_timer);
453
454 #ifdef CONFIG_SMP
455 /**
456  * try_to_del_timer_sync - Try to deactivate a timer
457  * @timer: timer do del
458  *
459  * This function tries to deactivate a timer. Upon successful (ret >= 0)
460  * exit the timer is not queued and the handler is not running on any CPU.
461  *
462  * It must not be called from interrupt contexts.
463  */
464 int try_to_del_timer_sync(struct timer_list *timer)
465 {
466         tvec_base_t *base;
467         unsigned long flags;
468         int ret = -1;
469
470         base = lock_timer_base(timer, &flags);
471
472         if (base->running_timer == timer)
473                 goto out;
474
475         ret = 0;
476         if (timer_pending(timer)) {
477                 detach_timer(timer, 1);
478                 ret = 1;
479         }
480 out:
481         spin_unlock_irqrestore(&base->lock, flags);
482
483         return ret;
484 }
485
486 /**
487  * del_timer_sync - deactivate a timer and wait for the handler to finish.
488  * @timer: the timer to be deactivated
489  *
490  * This function only differs from del_timer() on SMP: besides deactivating
491  * the timer it also makes sure the handler has finished executing on other
492  * CPUs.
493  *
494  * Synchronization rules: Callers must prevent restarting of the timer,
495  * otherwise this function is meaningless. It must not be called from
496  * interrupt contexts. The caller must not hold locks which would prevent
497  * completion of the timer's handler. The timer's handler must not call
498  * add_timer_on(). Upon exit the timer is not queued and the handler is
499  * not running on any CPU.
500  *
501  * The function returns whether it has deactivated a pending timer or not.
502  */
503 int del_timer_sync(struct timer_list *timer)
504 {
505         for (;;) {
506                 int ret = try_to_del_timer_sync(timer);
507                 if (ret >= 0)
508                         return ret;
509                 cpu_relax();
510         }
511 }
512
513 EXPORT_SYMBOL(del_timer_sync);
514 #endif
515
516 static int cascade(tvec_base_t *base, tvec_t *tv, int index)
517 {
518         /* cascade all the timers from tv up one level */
519         struct timer_list *timer, *tmp;
520         struct list_head tv_list;
521
522         list_replace_init(tv->vec + index, &tv_list);
523
524         /*
525          * We are removing _all_ timers from the list, so we
526          * don't have to detach them individually.
527          */
528         list_for_each_entry_safe(timer, tmp, &tv_list, entry) {
529                 BUG_ON(timer->base != base);
530                 internal_add_timer(base, timer);
531         }
532
533         return index;
534 }
535
536 #define INDEX(N) ((base->timer_jiffies >> (TVR_BITS + (N) * TVN_BITS)) & TVN_MASK)
537
538 /**
539  * __run_timers - run all expired timers (if any) on this CPU.
540  * @base: the timer vector to be processed.
541  *
542  * This function cascades all vectors and executes all expired timer
543  * vectors.
544  */
545 static inline void __run_timers(tvec_base_t *base)
546 {
547         struct timer_list *timer;
548
549         spin_lock_irq(&base->lock);
550         while (time_after_eq(jiffies, base->timer_jiffies)) {
551                 struct list_head work_list;
552                 struct list_head *head = &work_list;
553                 int index = base->timer_jiffies & TVR_MASK;
554
555                 /*
556                  * Cascade timers:
557                  */
558                 if (!index &&
559                         (!cascade(base, &base->tv2, INDEX(0))) &&
560                                 (!cascade(base, &base->tv3, INDEX(1))) &&
561                                         !cascade(base, &base->tv4, INDEX(2)))
562                         cascade(base, &base->tv5, INDEX(3));
563                 ++base->timer_jiffies;
564                 list_replace_init(base->tv1.vec + index, &work_list);
565                 while (!list_empty(head)) {
566                         void (*fn)(unsigned long);
567                         unsigned long data;
568
569                         timer = list_entry(head->next,struct timer_list,entry);
570                         fn = timer->function;
571                         data = timer->data;
572
573                         set_running_timer(base, timer);
574                         detach_timer(timer, 1);
575                         spin_unlock_irq(&base->lock);
576                         {
577                                 int preempt_count = preempt_count();
578                                 fn(data);
579                                 if (preempt_count != preempt_count()) {
580                                         printk(KERN_WARNING "huh, entered %p "
581                                                "with preempt_count %08x, exited"
582                                                " with %08x?\n",
583                                                fn, preempt_count,
584                                                preempt_count());
585                                         BUG();
586                                 }
587                         }
588                         spin_lock_irq(&base->lock);
589                 }
590         }
591         set_running_timer(base, NULL);
592         spin_unlock_irq(&base->lock);
593 }
594
595 #if defined(CONFIG_NO_IDLE_HZ) || defined(CONFIG_NO_HZ)
596 /*
597  * Find out when the next timer event is due to happen. This
598  * is used on S/390 to stop all activity when a cpus is idle.
599  * This functions needs to be called disabled.
600  */
601 static unsigned long __next_timer_interrupt(tvec_base_t *base)
602 {
603         unsigned long timer_jiffies = base->timer_jiffies;
604         unsigned long expires = timer_jiffies + (LONG_MAX >> 1);
605         int index, slot, array, found = 0;
606         struct timer_list *nte;
607         tvec_t *varray[4];
608
609         /* Look for timer events in tv1. */
610         index = slot = timer_jiffies & TVR_MASK;
611         do {
612                 list_for_each_entry(nte, base->tv1.vec + slot, entry) {
613                         found = 1;
614                         expires = nte->expires;
615                         /* Look at the cascade bucket(s)? */
616                         if (!index || slot < index)
617                                 goto cascade;
618                         return expires;
619                 }
620                 slot = (slot + 1) & TVR_MASK;
621         } while (slot != index);
622
623 cascade:
624         /* Calculate the next cascade event */
625         if (index)
626                 timer_jiffies += TVR_SIZE - index;
627         timer_jiffies >>= TVR_BITS;
628
629         /* Check tv2-tv5. */
630         varray[0] = &base->tv2;
631         varray[1] = &base->tv3;
632         varray[2] = &base->tv4;
633         varray[3] = &base->tv5;
634
635         for (array = 0; array < 4; array++) {
636                 tvec_t *varp = varray[array];
637
638                 index = slot = timer_jiffies & TVN_MASK;
639                 do {
640                         list_for_each_entry(nte, varp->vec + slot, entry) {
641                                 found = 1;
642                                 if (time_before(nte->expires, expires))
643                                         expires = nte->expires;
644                         }
645                         /*
646                          * Do we still search for the first timer or are
647                          * we looking up the cascade buckets ?
648                          */
649                         if (found) {
650                                 /* Look at the cascade bucket(s)? */
651                                 if (!index || slot < index)
652                                         break;
653                                 return expires;
654                         }
655                         slot = (slot + 1) & TVN_MASK;
656                 } while (slot != index);
657
658                 if (index)
659                         timer_jiffies += TVN_SIZE - index;
660                 timer_jiffies >>= TVN_BITS;
661         }
662         return expires;
663 }
664
665 /*
666  * Check, if the next hrtimer event is before the next timer wheel
667  * event:
668  */
669 static unsigned long cmp_next_hrtimer_event(unsigned long now,
670                                             unsigned long expires)
671 {
672         ktime_t hr_delta = hrtimer_get_next_event();
673         struct timespec tsdelta;
674
675         if (hr_delta.tv64 == KTIME_MAX)
676                 return expires;
677
678         if (hr_delta.tv64 <= TICK_NSEC)
679                 return now;
680
681         tsdelta = ktime_to_timespec(hr_delta);
682         now += timespec_to_jiffies(&tsdelta);
683         if (time_before(now, expires))
684                 return now;
685         return expires;
686 }
687
688 /**
689  * next_timer_interrupt - return the jiffy of the next pending timer
690  */
691 unsigned long get_next_timer_interrupt(unsigned long now)
692 {
693         tvec_base_t *base = __get_cpu_var(tvec_bases);
694         unsigned long expires;
695
696         spin_lock(&base->lock);
697         expires = __next_timer_interrupt(base);
698         spin_unlock(&base->lock);
699
700         if (time_before_eq(expires, now))
701                 return now;
702
703         return cmp_next_hrtimer_event(now, expires);
704 }
705
706 #ifdef CONFIG_NO_IDLE_HZ
707 unsigned long next_timer_interrupt(void)
708 {
709         return get_next_timer_interrupt(jiffies);
710 }
711 #endif
712
713 #endif
714
715 /******************************************************************/
716
717 /* 
718  * The current time 
719  * wall_to_monotonic is what we need to add to xtime (or xtime corrected 
720  * for sub jiffie times) to get to monotonic time.  Monotonic is pegged
721  * at zero at system boot time, so wall_to_monotonic will be negative,
722  * however, we will ALWAYS keep the tv_nsec part positive so we can use
723  * the usual normalization.
724  */
725 struct timespec xtime __attribute__ ((aligned (16)));
726 struct timespec wall_to_monotonic __attribute__ ((aligned (16)));
727
728 EXPORT_SYMBOL(xtime);
729
730
731 /* XXX - all of this timekeeping code should be later moved to time.c */
732 #include <linux/clocksource.h>
733 static struct clocksource *clock; /* pointer to current clocksource */
734
735 #ifdef CONFIG_GENERIC_TIME
736 /**
737  * __get_nsec_offset - Returns nanoseconds since last call to periodic_hook
738  *
739  * private function, must hold xtime_lock lock when being
740  * called. Returns the number of nanoseconds since the
741  * last call to update_wall_time() (adjusted by NTP scaling)
742  */
743 static inline s64 __get_nsec_offset(void)
744 {
745         cycle_t cycle_now, cycle_delta;
746         s64 ns_offset;
747
748         /* read clocksource: */
749         cycle_now = clocksource_read(clock);
750
751         /* calculate the delta since the last update_wall_time: */
752         cycle_delta = (cycle_now - clock->cycle_last) & clock->mask;
753
754         /* convert to nanoseconds: */
755         ns_offset = cyc2ns(clock, cycle_delta);
756
757         return ns_offset;
758 }
759
760 /**
761  * __get_realtime_clock_ts - Returns the time of day in a timespec
762  * @ts:         pointer to the timespec to be set
763  *
764  * Returns the time of day in a timespec. Used by
765  * do_gettimeofday() and get_realtime_clock_ts().
766  */
767 static inline void __get_realtime_clock_ts(struct timespec *ts)
768 {
769         unsigned long seq;
770         s64 nsecs;
771
772         do {
773                 seq = read_seqbegin(&xtime_lock);
774
775                 *ts = xtime;
776                 nsecs = __get_nsec_offset();
777
778         } while (read_seqretry(&xtime_lock, seq));
779
780         timespec_add_ns(ts, nsecs);
781 }
782
783 /**
784  * getnstimeofday - Returns the time of day in a timespec
785  * @ts:         pointer to the timespec to be set
786  *
787  * Returns the time of day in a timespec.
788  */
789 void getnstimeofday(struct timespec *ts)
790 {
791         __get_realtime_clock_ts(ts);
792 }
793
794 EXPORT_SYMBOL(getnstimeofday);
795
796 /**
797  * do_gettimeofday - Returns the time of day in a timeval
798  * @tv:         pointer to the timeval to be set
799  *
800  * NOTE: Users should be converted to using get_realtime_clock_ts()
801  */
802 void do_gettimeofday(struct timeval *tv)
803 {
804         struct timespec now;
805
806         __get_realtime_clock_ts(&now);
807         tv->tv_sec = now.tv_sec;
808         tv->tv_usec = now.tv_nsec/1000;
809 }
810
811 EXPORT_SYMBOL(do_gettimeofday);
812 /**
813  * do_settimeofday - Sets the time of day
814  * @tv:         pointer to the timespec variable containing the new time
815  *
816  * Sets the time of day to the new time and update NTP and notify hrtimers
817  */
818 int do_settimeofday(struct timespec *tv)
819 {
820         unsigned long flags;
821         time_t wtm_sec, sec = tv->tv_sec;
822         long wtm_nsec, nsec = tv->tv_nsec;
823
824         if ((unsigned long)tv->tv_nsec >= NSEC_PER_SEC)
825                 return -EINVAL;
826
827         write_seqlock_irqsave(&xtime_lock, flags);
828
829         nsec -= __get_nsec_offset();
830
831         wtm_sec  = wall_to_monotonic.tv_sec + (xtime.tv_sec - sec);
832         wtm_nsec = wall_to_monotonic.tv_nsec + (xtime.tv_nsec - nsec);
833
834         set_normalized_timespec(&xtime, sec, nsec);
835         set_normalized_timespec(&wall_to_monotonic, wtm_sec, wtm_nsec);
836
837         clock->error = 0;
838         ntp_clear();
839
840         write_sequnlock_irqrestore(&xtime_lock, flags);
841
842         /* signal hrtimers about time change */
843         clock_was_set();
844
845         return 0;
846 }
847
848 EXPORT_SYMBOL(do_settimeofday);
849
850 /**
851  * change_clocksource - Swaps clocksources if a new one is available
852  *
853  * Accumulates current time interval and initializes new clocksource
854  */
855 static void change_clocksource(void)
856 {
857         struct clocksource *new;
858         cycle_t now;
859         u64 nsec;
860
861         new = clocksource_get_next();
862
863         if (clock == new)
864                 return;
865
866         now = clocksource_read(new);
867         nsec =  __get_nsec_offset();
868         timespec_add_ns(&xtime, nsec);
869
870         clock = new;
871         clock->cycle_last = now;
872
873         clock->error = 0;
874         clock->xtime_nsec = 0;
875         clocksource_calculate_interval(clock, NTP_INTERVAL_LENGTH);
876
877         printk(KERN_INFO "Time: %s clocksource has been installed.\n",
878                clock->name);
879 }
880 #else
881 static inline void change_clocksource(void) { }
882 #endif
883
884 /**
885  * timeofday_is_continuous - check to see if timekeeping is free running
886  */
887 int timekeeping_is_continuous(void)
888 {
889         unsigned long seq;
890         int ret;
891
892         do {
893                 seq = read_seqbegin(&xtime_lock);
894
895                 ret = clock->flags & CLOCK_SOURCE_VALID_FOR_HRES;
896
897         } while (read_seqretry(&xtime_lock, seq));
898
899         return ret;
900 }
901
902 /**
903  * read_persistent_clock -  Return time in seconds from the persistent clock.
904  *
905  * Weak dummy function for arches that do not yet support it.
906  * Returns seconds from epoch using the battery backed persistent clock.
907  * Returns zero if unsupported.
908  *
909  *  XXX - Do be sure to remove it once all arches implement it.
910  */
911 unsigned long __attribute__((weak)) read_persistent_clock(void)
912 {
913         return 0;
914 }
915
916 /*
917  * timekeeping_init - Initializes the clocksource and common timekeeping values
918  */
919 void __init timekeeping_init(void)
920 {
921         unsigned long flags;
922         unsigned long sec = read_persistent_clock();
923
924         write_seqlock_irqsave(&xtime_lock, flags);
925
926         ntp_clear();
927
928         clock = clocksource_get_next();
929         clocksource_calculate_interval(clock, NTP_INTERVAL_LENGTH);
930         clock->cycle_last = clocksource_read(clock);
931
932         xtime.tv_sec = sec;
933         xtime.tv_nsec = 0;
934         set_normalized_timespec(&wall_to_monotonic,
935                 -xtime.tv_sec, -xtime.tv_nsec);
936
937         write_sequnlock_irqrestore(&xtime_lock, flags);
938 }
939
940
941 /* flag for if timekeeping is suspended */
942 static int timekeeping_suspended;
943 /* time in seconds when suspend began */
944 static unsigned long timekeeping_suspend_time;
945
946 /**
947  * timekeeping_resume - Resumes the generic timekeeping subsystem.
948  * @dev:        unused
949  *
950  * This is for the generic clocksource timekeeping.
951  * xtime/wall_to_monotonic/jiffies/etc are
952  * still managed by arch specific suspend/resume code.
953  */
954 static int timekeeping_resume(struct sys_device *dev)
955 {
956         unsigned long flags;
957         unsigned long now = read_persistent_clock();
958
959         write_seqlock_irqsave(&xtime_lock, flags);
960
961         if (now && (now > timekeeping_suspend_time)) {
962                 unsigned long sleep_length = now - timekeeping_suspend_time;
963
964                 xtime.tv_sec += sleep_length;
965                 wall_to_monotonic.tv_sec -= sleep_length;
966         }
967         /* re-base the last cycle value */
968         clock->cycle_last = clocksource_read(clock);
969         clock->error = 0;
970         timekeeping_suspended = 0;
971         write_sequnlock_irqrestore(&xtime_lock, flags);
972
973         touch_softlockup_watchdog();
974         /* Resume hrtimers */
975         clock_was_set();
976
977         return 0;
978 }
979
980 static int timekeeping_suspend(struct sys_device *dev, pm_message_t state)
981 {
982         unsigned long flags;
983
984         write_seqlock_irqsave(&xtime_lock, flags);
985         timekeeping_suspended = 1;
986         timekeeping_suspend_time = read_persistent_clock();
987         write_sequnlock_irqrestore(&xtime_lock, flags);
988         return 0;
989 }
990
991 /* sysfs resume/suspend bits for timekeeping */
992 static struct sysdev_class timekeeping_sysclass = {
993         .resume         = timekeeping_resume,
994         .suspend        = timekeeping_suspend,
995         set_kset_name("timekeeping"),
996 };
997
998 static struct sys_device device_timer = {
999         .id             = 0,
1000         .cls            = &timekeeping_sysclass,
1001 };
1002
1003 static int __init timekeeping_init_device(void)
1004 {
1005         int error = sysdev_class_register(&timekeeping_sysclass);
1006         if (!error)
1007                 error = sysdev_register(&device_timer);
1008         return error;
1009 }
1010
1011 device_initcall(timekeeping_init_device);
1012
1013 /*
1014  * If the error is already larger, we look ahead even further
1015  * to compensate for late or lost adjustments.
1016  */
1017 static __always_inline int clocksource_bigadjust(s64 error, s64 *interval,
1018                                                  s64 *offset)
1019 {
1020         s64 tick_error, i;
1021         u32 look_ahead, adj;
1022         s32 error2, mult;
1023
1024         /*
1025          * Use the current error value to determine how much to look ahead.
1026          * The larger the error the slower we adjust for it to avoid problems
1027          * with losing too many ticks, otherwise we would overadjust and
1028          * produce an even larger error.  The smaller the adjustment the
1029          * faster we try to adjust for it, as lost ticks can do less harm
1030          * here.  This is tuned so that an error of about 1 msec is adusted
1031          * within about 1 sec (or 2^20 nsec in 2^SHIFT_HZ ticks).
1032          */
1033         error2 = clock->error >> (TICK_LENGTH_SHIFT + 22 - 2 * SHIFT_HZ);
1034         error2 = abs(error2);
1035         for (look_ahead = 0; error2 > 0; look_ahead++)
1036                 error2 >>= 2;
1037
1038         /*
1039          * Now calculate the error in (1 << look_ahead) ticks, but first
1040          * remove the single look ahead already included in the error.
1041          */
1042         tick_error = current_tick_length() >>
1043                 (TICK_LENGTH_SHIFT - clock->shift + 1);
1044         tick_error -= clock->xtime_interval >> 1;
1045         error = ((error - tick_error) >> look_ahead) + tick_error;
1046
1047         /* Finally calculate the adjustment shift value.  */
1048         i = *interval;
1049         mult = 1;
1050         if (error < 0) {
1051                 error = -error;
1052                 *interval = -*interval;
1053                 *offset = -*offset;
1054                 mult = -1;
1055         }
1056         for (adj = 0; error > i; adj++)
1057                 error >>= 1;
1058
1059         *interval <<= adj;
1060         *offset <<= adj;
1061         return mult << adj;
1062 }
1063
1064 /*
1065  * Adjust the multiplier to reduce the error value,
1066  * this is optimized for the most common adjustments of -1,0,1,
1067  * for other values we can do a bit more work.
1068  */
1069 static void clocksource_adjust(struct clocksource *clock, s64 offset)
1070 {
1071         s64 error, interval = clock->cycle_interval;
1072         int adj;
1073
1074         error = clock->error >> (TICK_LENGTH_SHIFT - clock->shift - 1);
1075         if (error > interval) {
1076                 error >>= 2;
1077                 if (likely(error <= interval))
1078                         adj = 1;
1079                 else
1080                         adj = clocksource_bigadjust(error, &interval, &offset);
1081         } else if (error < -interval) {
1082                 error >>= 2;
1083                 if (likely(error >= -interval)) {
1084                         adj = -1;
1085                         interval = -interval;
1086                         offset = -offset;
1087                 } else
1088                         adj = clocksource_bigadjust(error, &interval, &offset);
1089         } else
1090                 return;
1091
1092         clock->mult += adj;
1093         clock->xtime_interval += interval;
1094         clock->xtime_nsec -= offset;
1095         clock->error -= (interval - offset) <<
1096                         (TICK_LENGTH_SHIFT - clock->shift);
1097 }
1098
1099 /**
1100  * update_wall_time - Uses the current clocksource to increment the wall time
1101  *
1102  * Called from the timer interrupt, must hold a write on xtime_lock.
1103  */
1104 static void update_wall_time(void)
1105 {
1106         cycle_t offset;
1107
1108         /* Make sure we're fully resumed: */
1109         if (unlikely(timekeeping_suspended))
1110                 return;
1111
1112 #ifdef CONFIG_GENERIC_TIME
1113         offset = (clocksource_read(clock) - clock->cycle_last) & clock->mask;
1114 #else
1115         offset = clock->cycle_interval;
1116 #endif
1117         clock->xtime_nsec += (s64)xtime.tv_nsec << clock->shift;
1118
1119         /* normally this loop will run just once, however in the
1120          * case of lost or late ticks, it will accumulate correctly.
1121          */
1122         while (offset >= clock->cycle_interval) {
1123                 /* accumulate one interval */
1124                 clock->xtime_nsec += clock->xtime_interval;
1125                 clock->cycle_last += clock->cycle_interval;
1126                 offset -= clock->cycle_interval;
1127
1128                 if (clock->xtime_nsec >= (u64)NSEC_PER_SEC << clock->shift) {
1129                         clock->xtime_nsec -= (u64)NSEC_PER_SEC << clock->shift;
1130                         xtime.tv_sec++;
1131                         second_overflow();
1132                 }
1133
1134                 /* interpolator bits */
1135                 time_interpolator_update(clock->xtime_interval
1136                                                 >> clock->shift);
1137
1138                 /* accumulate error between NTP and clock interval */
1139                 clock->error += current_tick_length();
1140                 clock->error -= clock->xtime_interval << (TICK_LENGTH_SHIFT - clock->shift);
1141         }
1142
1143         /* correct the clock when NTP error is too big */
1144         clocksource_adjust(clock, offset);
1145
1146         /* store full nanoseconds into xtime */
1147         xtime.tv_nsec = (s64)clock->xtime_nsec >> clock->shift;
1148         clock->xtime_nsec -= (s64)xtime.tv_nsec << clock->shift;
1149
1150         /* check to see if there is a new clocksource to use */
1151         change_clocksource();
1152 }
1153
1154 /*
1155  * Called from the timer interrupt handler to charge one tick to the current 
1156  * process.  user_tick is 1 if the tick is user time, 0 for system.
1157  */
1158 void update_process_times(int user_tick)
1159 {
1160         struct task_struct *p = current;
1161         int cpu = smp_processor_id();
1162
1163         /* Note: this timer irq context must be accounted for as well. */
1164         if (user_tick)
1165                 account_user_time(p, jiffies_to_cputime(1));
1166         else
1167                 account_system_time(p, HARDIRQ_OFFSET, jiffies_to_cputime(1));
1168         run_local_timers();
1169         if (rcu_pending(cpu))
1170                 rcu_check_callbacks(cpu, user_tick);
1171         scheduler_tick();
1172         run_posix_cpu_timers(p);
1173 }
1174
1175 /*
1176  * Nr of active tasks - counted in fixed-point numbers
1177  */
1178 static unsigned long count_active_tasks(void)
1179 {
1180         return nr_active() * FIXED_1;
1181 }
1182
1183 /*
1184  * Hmm.. Changed this, as the GNU make sources (load.c) seems to
1185  * imply that avenrun[] is the standard name for this kind of thing.
1186  * Nothing else seems to be standardized: the fractional size etc
1187  * all seem to differ on different machines.
1188  *
1189  * Requires xtime_lock to access.
1190  */
1191 unsigned long avenrun[3];
1192
1193 EXPORT_SYMBOL(avenrun);
1194
1195 /*
1196  * calc_load - given tick count, update the avenrun load estimates.
1197  * This is called while holding a write_lock on xtime_lock.
1198  */
1199 static inline void calc_load(unsigned long ticks)
1200 {
1201         unsigned long active_tasks; /* fixed-point */
1202         static int count = LOAD_FREQ;
1203
1204         count -= ticks;
1205         if (unlikely(count < 0)) {
1206                 active_tasks = count_active_tasks();
1207                 do {
1208                         CALC_LOAD(avenrun[0], EXP_1, active_tasks);
1209                         CALC_LOAD(avenrun[1], EXP_5, active_tasks);
1210                         CALC_LOAD(avenrun[2], EXP_15, active_tasks);
1211                         count += LOAD_FREQ;
1212                 } while (count < 0);
1213         }
1214 }
1215
1216 /*
1217  * This read-write spinlock protects us from races in SMP while
1218  * playing with xtime and avenrun.
1219  */
1220 __attribute__((weak)) __cacheline_aligned_in_smp DEFINE_SEQLOCK(xtime_lock);
1221
1222 EXPORT_SYMBOL(xtime_lock);
1223
1224 /*
1225  * This function runs timers and the timer-tq in bottom half context.
1226  */
1227 static void run_timer_softirq(struct softirq_action *h)
1228 {
1229         tvec_base_t *base = __get_cpu_var(tvec_bases);
1230
1231         hrtimer_run_queues();
1232         if (time_after_eq(jiffies, base->timer_jiffies))
1233                 __run_timers(base);
1234 }
1235
1236 /*
1237  * Called by the local, per-CPU timer interrupt on SMP.
1238  */
1239 void run_local_timers(void)
1240 {
1241         raise_softirq(TIMER_SOFTIRQ);
1242         softlockup_tick();
1243 }
1244
1245 /*
1246  * Called by the timer interrupt. xtime_lock must already be taken
1247  * by the timer IRQ!
1248  */
1249 static inline void update_times(unsigned long ticks)
1250 {
1251         update_wall_time();
1252         calc_load(ticks);
1253 }
1254   
1255 /*
1256  * The 64-bit jiffies value is not atomic - you MUST NOT read it
1257  * without sampling the sequence number in xtime_lock.
1258  * jiffies is defined in the linker script...
1259  */
1260
1261 void do_timer(unsigned long ticks)
1262 {
1263         jiffies_64 += ticks;
1264         update_times(ticks);
1265 }
1266
1267 #ifdef __ARCH_WANT_SYS_ALARM
1268
1269 /*
1270  * For backwards compatibility?  This can be done in libc so Alpha
1271  * and all newer ports shouldn't need it.
1272  */
1273 asmlinkage unsigned long sys_alarm(unsigned int seconds)
1274 {
1275         return alarm_setitimer(seconds);
1276 }
1277
1278 #endif
1279
1280 #ifndef __alpha__
1281
1282 /*
1283  * The Alpha uses getxpid, getxuid, and getxgid instead.  Maybe this
1284  * should be moved into arch/i386 instead?
1285  */
1286
1287 /**
1288  * sys_getpid - return the thread group id of the current process
1289  *
1290  * Note, despite the name, this returns the tgid not the pid.  The tgid and
1291  * the pid are identical unless CLONE_THREAD was specified on clone() in
1292  * which case the tgid is the same in all threads of the same group.
1293  *
1294  * This is SMP safe as current->tgid does not change.
1295  */
1296 asmlinkage long sys_getpid(void)
1297 {
1298         return current->tgid;
1299 }
1300
1301 /*
1302  * Accessing ->real_parent is not SMP-safe, it could
1303  * change from under us. However, we can use a stale
1304  * value of ->real_parent under rcu_read_lock(), see
1305  * release_task()->call_rcu(delayed_put_task_struct).
1306  */
1307 asmlinkage long sys_getppid(void)
1308 {
1309         int pid;
1310
1311         rcu_read_lock();
1312         pid = rcu_dereference(current->real_parent)->tgid;
1313         rcu_read_unlock();
1314
1315         return pid;
1316 }
1317
1318 asmlinkage long sys_getuid(void)
1319 {
1320         /* Only we change this so SMP safe */
1321         return current->uid;
1322 }
1323
1324 asmlinkage long sys_geteuid(void)
1325 {
1326         /* Only we change this so SMP safe */
1327         return current->euid;
1328 }
1329
1330 asmlinkage long sys_getgid(void)
1331 {
1332         /* Only we change this so SMP safe */
1333         return current->gid;
1334 }
1335
1336 asmlinkage long sys_getegid(void)
1337 {
1338         /* Only we change this so SMP safe */
1339         return  current->egid;
1340 }
1341
1342 #endif
1343
1344 static void process_timeout(unsigned long __data)
1345 {
1346         wake_up_process((struct task_struct *)__data);
1347 }
1348
1349 /**
1350  * schedule_timeout - sleep until timeout
1351  * @timeout: timeout value in jiffies
1352  *
1353  * Make the current task sleep until @timeout jiffies have
1354  * elapsed. The routine will return immediately unless
1355  * the current task state has been set (see set_current_state()).
1356  *
1357  * You can set the task state as follows -
1358  *
1359  * %TASK_UNINTERRUPTIBLE - at least @timeout jiffies are guaranteed to
1360  * pass before the routine returns. The routine will return 0
1361  *
1362  * %TASK_INTERRUPTIBLE - the routine may return early if a signal is
1363  * delivered to the current task. In this case the remaining time
1364  * in jiffies will be returned, or 0 if the timer expired in time
1365  *
1366  * The current task state is guaranteed to be TASK_RUNNING when this
1367  * routine returns.
1368  *
1369  * Specifying a @timeout value of %MAX_SCHEDULE_TIMEOUT will schedule
1370  * the CPU away without a bound on the timeout. In this case the return
1371  * value will be %MAX_SCHEDULE_TIMEOUT.
1372  *
1373  * In all cases the return value is guaranteed to be non-negative.
1374  */
1375 fastcall signed long __sched schedule_timeout(signed long timeout)
1376 {
1377         struct timer_list timer;
1378         unsigned long expire;
1379
1380         switch (timeout)
1381         {
1382         case MAX_SCHEDULE_TIMEOUT:
1383                 /*
1384                  * These two special cases are useful to be comfortable
1385                  * in the caller. Nothing more. We could take
1386                  * MAX_SCHEDULE_TIMEOUT from one of the negative value
1387                  * but I' d like to return a valid offset (>=0) to allow
1388                  * the caller to do everything it want with the retval.
1389                  */
1390                 schedule();
1391                 goto out;
1392         default:
1393                 /*
1394                  * Another bit of PARANOID. Note that the retval will be
1395                  * 0 since no piece of kernel is supposed to do a check
1396                  * for a negative retval of schedule_timeout() (since it
1397                  * should never happens anyway). You just have the printk()
1398                  * that will tell you if something is gone wrong and where.
1399                  */
1400                 if (timeout < 0) {
1401                         printk(KERN_ERR "schedule_timeout: wrong timeout "
1402                                 "value %lx\n", timeout);
1403                         dump_stack();
1404                         current->state = TASK_RUNNING;
1405                         goto out;
1406                 }
1407         }
1408
1409         expire = timeout + jiffies;
1410
1411         setup_timer(&timer, process_timeout, (unsigned long)current);
1412         __mod_timer(&timer, expire);
1413         schedule();
1414         del_singleshot_timer_sync(&timer);
1415
1416         timeout = expire - jiffies;
1417
1418  out:
1419         return timeout < 0 ? 0 : timeout;
1420 }
1421 EXPORT_SYMBOL(schedule_timeout);
1422
1423 /*
1424  * We can use __set_current_state() here because schedule_timeout() calls
1425  * schedule() unconditionally.
1426  */
1427 signed long __sched schedule_timeout_interruptible(signed long timeout)
1428 {
1429         __set_current_state(TASK_INTERRUPTIBLE);
1430         return schedule_timeout(timeout);
1431 }
1432 EXPORT_SYMBOL(schedule_timeout_interruptible);
1433
1434 signed long __sched schedule_timeout_uninterruptible(signed long timeout)
1435 {
1436         __set_current_state(TASK_UNINTERRUPTIBLE);
1437         return schedule_timeout(timeout);
1438 }
1439 EXPORT_SYMBOL(schedule_timeout_uninterruptible);
1440
1441 /* Thread ID - the internal kernel "pid" */
1442 asmlinkage long sys_gettid(void)
1443 {
1444         return current->pid;
1445 }
1446
1447 /**
1448  * do_sysinfo - fill in sysinfo struct
1449  * @info: pointer to buffer to fill
1450  */ 
1451 int do_sysinfo(struct sysinfo *info)
1452 {
1453         unsigned long mem_total, sav_total;
1454         unsigned int mem_unit, bitcount;
1455         unsigned long seq;
1456
1457         memset(info, 0, sizeof(struct sysinfo));
1458
1459         do {
1460                 struct timespec tp;
1461                 seq = read_seqbegin(&xtime_lock);
1462
1463                 /*
1464                  * This is annoying.  The below is the same thing
1465                  * posix_get_clock_monotonic() does, but it wants to
1466                  * take the lock which we want to cover the loads stuff
1467                  * too.
1468                  */
1469
1470                 getnstimeofday(&tp);
1471                 tp.tv_sec += wall_to_monotonic.tv_sec;
1472                 tp.tv_nsec += wall_to_monotonic.tv_nsec;
1473                 if (tp.tv_nsec - NSEC_PER_SEC >= 0) {
1474                         tp.tv_nsec = tp.tv_nsec - NSEC_PER_SEC;
1475                         tp.tv_sec++;
1476                 }
1477                 info->uptime = tp.tv_sec + (tp.tv_nsec ? 1 : 0);
1478
1479                 info->loads[0] = avenrun[0] << (SI_LOAD_SHIFT - FSHIFT);
1480                 info->loads[1] = avenrun[1] << (SI_LOAD_SHIFT - FSHIFT);
1481                 info->loads[2] = avenrun[2] << (SI_LOAD_SHIFT - FSHIFT);
1482
1483                 info->procs = nr_threads;
1484         } while (read_seqretry(&xtime_lock, seq));
1485
1486         si_meminfo(info);
1487         si_swapinfo(info);
1488
1489         /*
1490          * If the sum of all the available memory (i.e. ram + swap)
1491          * is less than can be stored in a 32 bit unsigned long then
1492          * we can be binary compatible with 2.2.x kernels.  If not,
1493          * well, in that case 2.2.x was broken anyways...
1494          *
1495          *  -Erik Andersen <andersee@debian.org>
1496          */
1497
1498         mem_total = info->totalram + info->totalswap;
1499         if (mem_total < info->totalram || mem_total < info->totalswap)
1500                 goto out;
1501         bitcount = 0;
1502         mem_unit = info->mem_unit;
1503         while (mem_unit > 1) {
1504                 bitcount++;
1505                 mem_unit >>= 1;
1506                 sav_total = mem_total;
1507                 mem_total <<= 1;
1508                 if (mem_total < sav_total)
1509                         goto out;
1510         }
1511
1512         /*
1513          * If mem_total did not overflow, multiply all memory values by
1514          * info->mem_unit and set it to 1.  This leaves things compatible
1515          * with 2.2.x, and also retains compatibility with earlier 2.4.x
1516          * kernels...
1517          */
1518
1519         info->mem_unit = 1;
1520         info->totalram <<= bitcount;
1521         info->freeram <<= bitcount;
1522         info->sharedram <<= bitcount;
1523         info->bufferram <<= bitcount;
1524         info->totalswap <<= bitcount;
1525         info->freeswap <<= bitcount;
1526         info->totalhigh <<= bitcount;
1527         info->freehigh <<= bitcount;
1528
1529 out:
1530         return 0;
1531 }
1532
1533 asmlinkage long sys_sysinfo(struct sysinfo __user *info)
1534 {
1535         struct sysinfo val;
1536
1537         do_sysinfo(&val);
1538
1539         if (copy_to_user(info, &val, sizeof(struct sysinfo)))
1540                 return -EFAULT;
1541
1542         return 0;
1543 }
1544
1545 /*
1546  * lockdep: we want to track each per-CPU base as a separate lock-class,
1547  * but timer-bases are kmalloc()-ed, so we need to attach separate
1548  * keys to them:
1549  */
1550 static struct lock_class_key base_lock_keys[NR_CPUS];
1551
1552 static int __devinit init_timers_cpu(int cpu)
1553 {
1554         int j;
1555         tvec_base_t *base;
1556         static char __devinitdata tvec_base_done[NR_CPUS];
1557
1558         if (!tvec_base_done[cpu]) {
1559                 static char boot_done;
1560
1561                 if (boot_done) {
1562                         /*
1563                          * The APs use this path later in boot
1564                          */
1565                         base = kmalloc_node(sizeof(*base), GFP_KERNEL,
1566                                                 cpu_to_node(cpu));
1567                         if (!base)
1568                                 return -ENOMEM;
1569                         memset(base, 0, sizeof(*base));
1570                         per_cpu(tvec_bases, cpu) = base;
1571                 } else {
1572                         /*
1573                          * This is for the boot CPU - we use compile-time
1574                          * static initialisation because per-cpu memory isn't
1575                          * ready yet and because the memory allocators are not
1576                          * initialised either.
1577                          */
1578                         boot_done = 1;
1579                         base = &boot_tvec_bases;
1580                 }
1581                 tvec_base_done[cpu] = 1;
1582         } else {
1583                 base = per_cpu(tvec_bases, cpu);
1584         }
1585
1586         spin_lock_init(&base->lock);
1587         lockdep_set_class(&base->lock, base_lock_keys + cpu);
1588
1589         for (j = 0; j < TVN_SIZE; j++) {
1590                 INIT_LIST_HEAD(base->tv5.vec + j);
1591                 INIT_LIST_HEAD(base->tv4.vec + j);
1592                 INIT_LIST_HEAD(base->tv3.vec + j);
1593                 INIT_LIST_HEAD(base->tv2.vec + j);
1594         }
1595         for (j = 0; j < TVR_SIZE; j++)
1596                 INIT_LIST_HEAD(base->tv1.vec + j);
1597
1598         base->timer_jiffies = jiffies;
1599         return 0;
1600 }
1601
1602 #ifdef CONFIG_HOTPLUG_CPU
1603 static void migrate_timer_list(tvec_base_t *new_base, struct list_head *head)
1604 {
1605         struct timer_list *timer;
1606
1607         while (!list_empty(head)) {
1608                 timer = list_entry(head->next, struct timer_list, entry);
1609                 detach_timer(timer, 0);
1610                 timer->base = new_base;
1611                 internal_add_timer(new_base, timer);
1612         }
1613 }
1614
1615 static void __devinit migrate_timers(int cpu)
1616 {
1617         tvec_base_t *old_base;
1618         tvec_base_t *new_base;
1619         int i;
1620
1621         BUG_ON(cpu_online(cpu));
1622         old_base = per_cpu(tvec_bases, cpu);
1623         new_base = get_cpu_var(tvec_bases);
1624
1625         local_irq_disable();
1626         spin_lock(&new_base->lock);
1627         spin_lock(&old_base->lock);
1628
1629         BUG_ON(old_base->running_timer);
1630
1631         for (i = 0; i < TVR_SIZE; i++)
1632                 migrate_timer_list(new_base, old_base->tv1.vec + i);
1633         for (i = 0; i < TVN_SIZE; i++) {
1634                 migrate_timer_list(new_base, old_base->tv2.vec + i);
1635                 migrate_timer_list(new_base, old_base->tv3.vec + i);
1636                 migrate_timer_list(new_base, old_base->tv4.vec + i);
1637                 migrate_timer_list(new_base, old_base->tv5.vec + i);
1638         }
1639
1640         spin_unlock(&old_base->lock);
1641         spin_unlock(&new_base->lock);
1642         local_irq_enable();
1643         put_cpu_var(tvec_bases);
1644 }
1645 #endif /* CONFIG_HOTPLUG_CPU */
1646
1647 static int __cpuinit timer_cpu_notify(struct notifier_block *self,
1648                                 unsigned long action, void *hcpu)
1649 {
1650         long cpu = (long)hcpu;
1651         switch(action) {
1652         case CPU_UP_PREPARE:
1653                 if (init_timers_cpu(cpu) < 0)
1654                         return NOTIFY_BAD;
1655                 break;
1656 #ifdef CONFIG_HOTPLUG_CPU
1657         case CPU_DEAD:
1658                 migrate_timers(cpu);
1659                 break;
1660 #endif
1661         default:
1662                 break;
1663         }
1664         return NOTIFY_OK;
1665 }
1666
1667 static struct notifier_block __cpuinitdata timers_nb = {
1668         .notifier_call  = timer_cpu_notify,
1669 };
1670
1671
1672 void __init init_timers(void)
1673 {
1674         int err = timer_cpu_notify(&timers_nb, (unsigned long)CPU_UP_PREPARE,
1675                                 (void *)(long)smp_processor_id());
1676
1677         BUG_ON(err == NOTIFY_BAD);
1678         register_cpu_notifier(&timers_nb);
1679         open_softirq(TIMER_SOFTIRQ, run_timer_softirq, NULL);
1680 }
1681
1682 #ifdef CONFIG_TIME_INTERPOLATION
1683
1684 struct time_interpolator *time_interpolator __read_mostly;
1685 static struct time_interpolator *time_interpolator_list __read_mostly;
1686 static DEFINE_SPINLOCK(time_interpolator_lock);
1687
1688 static inline cycles_t time_interpolator_get_cycles(unsigned int src)
1689 {
1690         unsigned long (*x)(void);
1691
1692         switch (src)
1693         {
1694                 case TIME_SOURCE_FUNCTION:
1695                         x = time_interpolator->addr;
1696                         return x();
1697
1698                 case TIME_SOURCE_MMIO64 :
1699                         return readq_relaxed((void __iomem *)time_interpolator->addr);
1700
1701                 case TIME_SOURCE_MMIO32 :
1702                         return readl_relaxed((void __iomem *)time_interpolator->addr);
1703
1704                 default: return get_cycles();
1705         }
1706 }
1707
1708 static inline u64 time_interpolator_get_counter(int writelock)
1709 {
1710         unsigned int src = time_interpolator->source;
1711
1712         if (time_interpolator->jitter)
1713         {
1714                 cycles_t lcycle;
1715                 cycles_t now;
1716
1717                 do {
1718                         lcycle = time_interpolator->last_cycle;
1719                         now = time_interpolator_get_cycles(src);
1720                         if (lcycle && time_after(lcycle, now))
1721                                 return lcycle;
1722
1723                         /* When holding the xtime write lock, there's no need
1724                          * to add the overhead of the cmpxchg.  Readers are
1725                          * force to retry until the write lock is released.
1726                          */
1727                         if (writelock) {
1728                                 time_interpolator->last_cycle = now;
1729                                 return now;
1730                         }
1731                         /* Keep track of the last timer value returned. The use of cmpxchg here
1732                          * will cause contention in an SMP environment.
1733                          */
1734                 } while (unlikely(cmpxchg(&time_interpolator->last_cycle, lcycle, now) != lcycle));
1735                 return now;
1736         }
1737         else
1738                 return time_interpolator_get_cycles(src);
1739 }
1740
1741 void time_interpolator_reset(void)
1742 {
1743         time_interpolator->offset = 0;
1744         time_interpolator->last_counter = time_interpolator_get_counter(1);
1745 }
1746
1747 #define GET_TI_NSECS(count,i) (((((count) - i->last_counter) & (i)->mask) * (i)->nsec_per_cyc) >> (i)->shift)
1748
1749 unsigned long time_interpolator_get_offset(void)
1750 {
1751         /* If we do not have a time interpolator set up then just return zero */
1752         if (!time_interpolator)
1753                 return 0;
1754
1755         return time_interpolator->offset +
1756                 GET_TI_NSECS(time_interpolator_get_counter(0), time_interpolator);
1757 }
1758
1759 #define INTERPOLATOR_ADJUST 65536
1760 #define INTERPOLATOR_MAX_SKIP 10*INTERPOLATOR_ADJUST
1761
1762 void time_interpolator_update(long delta_nsec)
1763 {
1764         u64 counter;
1765         unsigned long offset;
1766
1767         /* If there is no time interpolator set up then do nothing */
1768         if (!time_interpolator)
1769                 return;
1770
1771         /*
1772          * The interpolator compensates for late ticks by accumulating the late
1773          * time in time_interpolator->offset. A tick earlier than expected will
1774          * lead to a reset of the offset and a corresponding jump of the clock
1775          * forward. Again this only works if the interpolator clock is running
1776          * slightly slower than the regular clock and the tuning logic insures
1777          * that.
1778          */
1779
1780         counter = time_interpolator_get_counter(1);
1781         offset = time_interpolator->offset +
1782                         GET_TI_NSECS(counter, time_interpolator);
1783
1784         if (delta_nsec < 0 || (unsigned long) delta_nsec < offset)
1785                 time_interpolator->offset = offset - delta_nsec;
1786         else {
1787                 time_interpolator->skips++;
1788                 time_interpolator->ns_skipped += delta_nsec - offset;
1789                 time_interpolator->offset = 0;
1790         }
1791         time_interpolator->last_counter = counter;
1792
1793         /* Tuning logic for time interpolator invoked every minute or so.
1794          * Decrease interpolator clock speed if no skips occurred and an offset is carried.
1795          * Increase interpolator clock speed if we skip too much time.
1796          */
1797         if (jiffies % INTERPOLATOR_ADJUST == 0)
1798         {
1799                 if (time_interpolator->skips == 0 && time_interpolator->offset > tick_nsec)
1800                         time_interpolator->nsec_per_cyc--;
1801                 if (time_interpolator->ns_skipped > INTERPOLATOR_MAX_SKIP && time_interpolator->offset == 0)
1802                         time_interpolator->nsec_per_cyc++;
1803                 time_interpolator->skips = 0;
1804                 time_interpolator->ns_skipped = 0;
1805         }
1806 }
1807
1808 static inline int
1809 is_better_time_interpolator(struct time_interpolator *new)
1810 {
1811         if (!time_interpolator)
1812                 return 1;
1813         return new->frequency > 2*time_interpolator->frequency ||
1814             (unsigned long)new->drift < (unsigned long)time_interpolator->drift;
1815 }
1816
1817 void
1818 register_time_interpolator(struct time_interpolator *ti)
1819 {
1820         unsigned long flags;
1821
1822         /* Sanity check */
1823         BUG_ON(ti->frequency == 0 || ti->mask == 0);
1824
1825         ti->nsec_per_cyc = ((u64)NSEC_PER_SEC << ti->shift) / ti->frequency;
1826         spin_lock(&time_interpolator_lock);
1827         write_seqlock_irqsave(&xtime_lock, flags);
1828         if (is_better_time_interpolator(ti)) {
1829                 time_interpolator = ti;
1830                 time_interpolator_reset();
1831         }
1832         write_sequnlock_irqrestore(&xtime_lock, flags);
1833
1834         ti->next = time_interpolator_list;
1835         time_interpolator_list = ti;
1836         spin_unlock(&time_interpolator_lock);
1837 }
1838
1839 void
1840 unregister_time_interpolator(struct time_interpolator *ti)
1841 {
1842         struct time_interpolator *curr, **prev;
1843         unsigned long flags;
1844
1845         spin_lock(&time_interpolator_lock);
1846         prev = &time_interpolator_list;
1847         for (curr = *prev; curr; curr = curr->next) {
1848                 if (curr == ti) {
1849                         *prev = curr->next;
1850                         break;
1851                 }
1852                 prev = &curr->next;
1853         }
1854
1855         write_seqlock_irqsave(&xtime_lock, flags);
1856         if (ti == time_interpolator) {
1857                 /* we lost the best time-interpolator: */
1858                 time_interpolator = NULL;
1859                 /* find the next-best interpolator */
1860                 for (curr = time_interpolator_list; curr; curr = curr->next)
1861                         if (is_better_time_interpolator(curr))
1862                                 time_interpolator = curr;
1863                 time_interpolator_reset();
1864         }
1865         write_sequnlock_irqrestore(&xtime_lock, flags);
1866         spin_unlock(&time_interpolator_lock);
1867 }
1868 #endif /* CONFIG_TIME_INTERPOLATION */
1869
1870 /**
1871  * msleep - sleep safely even with waitqueue interruptions
1872  * @msecs: Time in milliseconds to sleep for
1873  */
1874 void msleep(unsigned int msecs)
1875 {
1876         unsigned long timeout = msecs_to_jiffies(msecs) + 1;
1877
1878         while (timeout)
1879                 timeout = schedule_timeout_uninterruptible(timeout);
1880 }
1881
1882 EXPORT_SYMBOL(msleep);
1883
1884 /**
1885  * msleep_interruptible - sleep waiting for signals
1886  * @msecs: Time in milliseconds to sleep for
1887  */
1888 unsigned long msleep_interruptible(unsigned int msecs)
1889 {
1890         unsigned long timeout = msecs_to_jiffies(msecs) + 1;
1891
1892         while (timeout && !signal_pending(current))
1893                 timeout = schedule_timeout_interruptible(timeout);
1894         return jiffies_to_msecs(timeout);
1895 }
1896
1897 EXPORT_SYMBOL(msleep_interruptible);