[PATCH] tick-management: dyntick / highres functionality
[linux-2.6.git] / 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/tick.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         tick_clock_notify();
878
879         printk(KERN_INFO "Time: %s clocksource has been installed.\n",
880                clock->name);
881 }
882 #else
883 static inline void change_clocksource(void) { }
884 #endif
885
886 /**
887  * timeofday_is_continuous - check to see if timekeeping is free running
888  */
889 int timekeeping_is_continuous(void)
890 {
891         unsigned long seq;
892         int ret;
893
894         do {
895                 seq = read_seqbegin(&xtime_lock);
896
897                 ret = clock->flags & CLOCK_SOURCE_VALID_FOR_HRES;
898
899         } while (read_seqretry(&xtime_lock, seq));
900
901         return ret;
902 }
903
904 /**
905  * read_persistent_clock -  Return time in seconds from the persistent clock.
906  *
907  * Weak dummy function for arches that do not yet support it.
908  * Returns seconds from epoch using the battery backed persistent clock.
909  * Returns zero if unsupported.
910  *
911  *  XXX - Do be sure to remove it once all arches implement it.
912  */
913 unsigned long __attribute__((weak)) read_persistent_clock(void)
914 {
915         return 0;
916 }
917
918 /*
919  * timekeeping_init - Initializes the clocksource and common timekeeping values
920  */
921 void __init timekeeping_init(void)
922 {
923         unsigned long flags;
924         unsigned long sec = read_persistent_clock();
925
926         write_seqlock_irqsave(&xtime_lock, flags);
927
928         ntp_clear();
929
930         clock = clocksource_get_next();
931         clocksource_calculate_interval(clock, NTP_INTERVAL_LENGTH);
932         clock->cycle_last = clocksource_read(clock);
933
934         xtime.tv_sec = sec;
935         xtime.tv_nsec = 0;
936         set_normalized_timespec(&wall_to_monotonic,
937                 -xtime.tv_sec, -xtime.tv_nsec);
938
939         write_sequnlock_irqrestore(&xtime_lock, flags);
940 }
941
942 /* flag for if timekeeping is suspended */
943 static int timekeeping_suspended;
944 /* time in seconds when suspend began */
945 static unsigned long timekeeping_suspend_time;
946
947 /**
948  * timekeeping_resume - Resumes the generic timekeeping subsystem.
949  * @dev:        unused
950  *
951  * This is for the generic clocksource timekeeping.
952  * xtime/wall_to_monotonic/jiffies/etc are
953  * still managed by arch specific suspend/resume code.
954  */
955 static int timekeeping_resume(struct sys_device *dev)
956 {
957         unsigned long flags;
958         unsigned long now = read_persistent_clock();
959
960         write_seqlock_irqsave(&xtime_lock, flags);
961
962         if (now && (now > timekeeping_suspend_time)) {
963                 unsigned long sleep_length = now - timekeeping_suspend_time;
964
965                 xtime.tv_sec += sleep_length;
966                 wall_to_monotonic.tv_sec -= sleep_length;
967         }
968         /* re-base the last cycle value */
969         clock->cycle_last = clocksource_read(clock);
970         clock->error = 0;
971         timekeeping_suspended = 0;
972         write_sequnlock_irqrestore(&xtime_lock, flags);
973
974         touch_softlockup_watchdog();
975         /* Resume hrtimers */
976         clock_was_set();
977
978         return 0;
979 }
980
981 static int timekeeping_suspend(struct sys_device *dev, pm_message_t state)
982 {
983         unsigned long flags;
984
985         write_seqlock_irqsave(&xtime_lock, flags);
986         timekeeping_suspended = 1;
987         timekeeping_suspend_time = read_persistent_clock();
988         write_sequnlock_irqrestore(&xtime_lock, flags);
989         return 0;
990 }
991
992 /* sysfs resume/suspend bits for timekeeping */
993 static struct sysdev_class timekeeping_sysclass = {
994         .resume         = timekeeping_resume,
995         .suspend        = timekeeping_suspend,
996         set_kset_name("timekeeping"),
997 };
998
999 static struct sys_device device_timer = {
1000         .id             = 0,
1001         .cls            = &timekeeping_sysclass,
1002 };
1003
1004 static int __init timekeeping_init_device(void)
1005 {
1006         int error = sysdev_class_register(&timekeeping_sysclass);
1007         if (!error)
1008                 error = sysdev_register(&device_timer);
1009         return error;
1010 }
1011
1012 device_initcall(timekeeping_init_device);
1013
1014 /*
1015  * If the error is already larger, we look ahead even further
1016  * to compensate for late or lost adjustments.
1017  */
1018 static __always_inline int clocksource_bigadjust(s64 error, s64 *interval,
1019                                                  s64 *offset)
1020 {
1021         s64 tick_error, i;
1022         u32 look_ahead, adj;
1023         s32 error2, mult;
1024
1025         /*
1026          * Use the current error value to determine how much to look ahead.
1027          * The larger the error the slower we adjust for it to avoid problems
1028          * with losing too many ticks, otherwise we would overadjust and
1029          * produce an even larger error.  The smaller the adjustment the
1030          * faster we try to adjust for it, as lost ticks can do less harm
1031          * here.  This is tuned so that an error of about 1 msec is adusted
1032          * within about 1 sec (or 2^20 nsec in 2^SHIFT_HZ ticks).
1033          */
1034         error2 = clock->error >> (TICK_LENGTH_SHIFT + 22 - 2 * SHIFT_HZ);
1035         error2 = abs(error2);
1036         for (look_ahead = 0; error2 > 0; look_ahead++)
1037                 error2 >>= 2;
1038
1039         /*
1040          * Now calculate the error in (1 << look_ahead) ticks, but first
1041          * remove the single look ahead already included in the error.
1042          */
1043         tick_error = current_tick_length() >>
1044                 (TICK_LENGTH_SHIFT - clock->shift + 1);
1045         tick_error -= clock->xtime_interval >> 1;
1046         error = ((error - tick_error) >> look_ahead) + tick_error;
1047
1048         /* Finally calculate the adjustment shift value.  */
1049         i = *interval;
1050         mult = 1;
1051         if (error < 0) {
1052                 error = -error;
1053                 *interval = -*interval;
1054                 *offset = -*offset;
1055                 mult = -1;
1056         }
1057         for (adj = 0; error > i; adj++)
1058                 error >>= 1;
1059
1060         *interval <<= adj;
1061         *offset <<= adj;
1062         return mult << adj;
1063 }
1064
1065 /*
1066  * Adjust the multiplier to reduce the error value,
1067  * this is optimized for the most common adjustments of -1,0,1,
1068  * for other values we can do a bit more work.
1069  */
1070 static void clocksource_adjust(struct clocksource *clock, s64 offset)
1071 {
1072         s64 error, interval = clock->cycle_interval;
1073         int adj;
1074
1075         error = clock->error >> (TICK_LENGTH_SHIFT - clock->shift - 1);
1076         if (error > interval) {
1077                 error >>= 2;
1078                 if (likely(error <= interval))
1079                         adj = 1;
1080                 else
1081                         adj = clocksource_bigadjust(error, &interval, &offset);
1082         } else if (error < -interval) {
1083                 error >>= 2;
1084                 if (likely(error >= -interval)) {
1085                         adj = -1;
1086                         interval = -interval;
1087                         offset = -offset;
1088                 } else
1089                         adj = clocksource_bigadjust(error, &interval, &offset);
1090         } else
1091                 return;
1092
1093         clock->mult += adj;
1094         clock->xtime_interval += interval;
1095         clock->xtime_nsec -= offset;
1096         clock->error -= (interval - offset) <<
1097                         (TICK_LENGTH_SHIFT - clock->shift);
1098 }
1099
1100 /**
1101  * update_wall_time - Uses the current clocksource to increment the wall time
1102  *
1103  * Called from the timer interrupt, must hold a write on xtime_lock.
1104  */
1105 static void update_wall_time(void)
1106 {
1107         cycle_t offset;
1108
1109         /* Make sure we're fully resumed: */
1110         if (unlikely(timekeeping_suspended))
1111                 return;
1112
1113 #ifdef CONFIG_GENERIC_TIME
1114         offset = (clocksource_read(clock) - clock->cycle_last) & clock->mask;
1115 #else
1116         offset = clock->cycle_interval;
1117 #endif
1118         clock->xtime_nsec += (s64)xtime.tv_nsec << clock->shift;
1119
1120         /* normally this loop will run just once, however in the
1121          * case of lost or late ticks, it will accumulate correctly.
1122          */
1123         while (offset >= clock->cycle_interval) {
1124                 /* accumulate one interval */
1125                 clock->xtime_nsec += clock->xtime_interval;
1126                 clock->cycle_last += clock->cycle_interval;
1127                 offset -= clock->cycle_interval;
1128
1129                 if (clock->xtime_nsec >= (u64)NSEC_PER_SEC << clock->shift) {
1130                         clock->xtime_nsec -= (u64)NSEC_PER_SEC << clock->shift;
1131                         xtime.tv_sec++;
1132                         second_overflow();
1133                 }
1134
1135                 /* interpolator bits */
1136                 time_interpolator_update(clock->xtime_interval
1137                                                 >> clock->shift);
1138
1139                 /* accumulate error between NTP and clock interval */
1140                 clock->error += current_tick_length();
1141                 clock->error -= clock->xtime_interval << (TICK_LENGTH_SHIFT - clock->shift);
1142         }
1143
1144         /* correct the clock when NTP error is too big */
1145         clocksource_adjust(clock, offset);
1146
1147         /* store full nanoseconds into xtime */
1148         xtime.tv_nsec = (s64)clock->xtime_nsec >> clock->shift;
1149         clock->xtime_nsec -= (s64)xtime.tv_nsec << clock->shift;
1150
1151         /* check to see if there is a new clocksource to use */
1152         change_clocksource();
1153 }
1154
1155 /*
1156  * Called from the timer interrupt handler to charge one tick to the current 
1157  * process.  user_tick is 1 if the tick is user time, 0 for system.
1158  */
1159 void update_process_times(int user_tick)
1160 {
1161         struct task_struct *p = current;
1162         int cpu = smp_processor_id();
1163
1164         /* Note: this timer irq context must be accounted for as well. */
1165         if (user_tick)
1166                 account_user_time(p, jiffies_to_cputime(1));
1167         else
1168                 account_system_time(p, HARDIRQ_OFFSET, jiffies_to_cputime(1));
1169         run_local_timers();
1170         if (rcu_pending(cpu))
1171                 rcu_check_callbacks(cpu, user_tick);
1172         scheduler_tick();
1173         run_posix_cpu_timers(p);
1174 }
1175
1176 /*
1177  * Nr of active tasks - counted in fixed-point numbers
1178  */
1179 static unsigned long count_active_tasks(void)
1180 {
1181         return nr_active() * FIXED_1;
1182 }
1183
1184 /*
1185  * Hmm.. Changed this, as the GNU make sources (load.c) seems to
1186  * imply that avenrun[] is the standard name for this kind of thing.
1187  * Nothing else seems to be standardized: the fractional size etc
1188  * all seem to differ on different machines.
1189  *
1190  * Requires xtime_lock to access.
1191  */
1192 unsigned long avenrun[3];
1193
1194 EXPORT_SYMBOL(avenrun);
1195
1196 /*
1197  * calc_load - given tick count, update the avenrun load estimates.
1198  * This is called while holding a write_lock on xtime_lock.
1199  */
1200 static inline void calc_load(unsigned long ticks)
1201 {
1202         unsigned long active_tasks; /* fixed-point */
1203         static int count = LOAD_FREQ;
1204
1205         count -= ticks;
1206         if (unlikely(count < 0)) {
1207                 active_tasks = count_active_tasks();
1208                 do {
1209                         CALC_LOAD(avenrun[0], EXP_1, active_tasks);
1210                         CALC_LOAD(avenrun[1], EXP_5, active_tasks);
1211                         CALC_LOAD(avenrun[2], EXP_15, active_tasks);
1212                         count += LOAD_FREQ;
1213                 } while (count < 0);
1214         }
1215 }
1216
1217 /*
1218  * This read-write spinlock protects us from races in SMP while
1219  * playing with xtime and avenrun.
1220  */
1221 __attribute__((weak)) __cacheline_aligned_in_smp DEFINE_SEQLOCK(xtime_lock);
1222
1223 EXPORT_SYMBOL(xtime_lock);
1224
1225 /*
1226  * This function runs timers and the timer-tq in bottom half context.
1227  */
1228 static void run_timer_softirq(struct softirq_action *h)
1229 {
1230         tvec_base_t *base = __get_cpu_var(tvec_bases);
1231
1232         hrtimer_run_queues();
1233         if (time_after_eq(jiffies, base->timer_jiffies))
1234                 __run_timers(base);
1235 }
1236
1237 /*
1238  * Called by the local, per-CPU timer interrupt on SMP.
1239  */
1240 void run_local_timers(void)
1241 {
1242         raise_softirq(TIMER_SOFTIRQ);
1243         softlockup_tick();
1244 }
1245
1246 /*
1247  * Called by the timer interrupt. xtime_lock must already be taken
1248  * by the timer IRQ!
1249  */
1250 static inline void update_times(unsigned long ticks)
1251 {
1252         update_wall_time();
1253         calc_load(ticks);
1254 }
1255   
1256 /*
1257  * The 64-bit jiffies value is not atomic - you MUST NOT read it
1258  * without sampling the sequence number in xtime_lock.
1259  * jiffies is defined in the linker script...
1260  */
1261
1262 void do_timer(unsigned long ticks)
1263 {
1264         jiffies_64 += ticks;
1265         update_times(ticks);
1266 }
1267
1268 #ifdef __ARCH_WANT_SYS_ALARM
1269
1270 /*
1271  * For backwards compatibility?  This can be done in libc so Alpha
1272  * and all newer ports shouldn't need it.
1273  */
1274 asmlinkage unsigned long sys_alarm(unsigned int seconds)
1275 {
1276         return alarm_setitimer(seconds);
1277 }
1278
1279 #endif
1280
1281 #ifndef __alpha__
1282
1283 /*
1284  * The Alpha uses getxpid, getxuid, and getxgid instead.  Maybe this
1285  * should be moved into arch/i386 instead?
1286  */
1287
1288 /**
1289  * sys_getpid - return the thread group id of the current process
1290  *
1291  * Note, despite the name, this returns the tgid not the pid.  The tgid and
1292  * the pid are identical unless CLONE_THREAD was specified on clone() in
1293  * which case the tgid is the same in all threads of the same group.
1294  *
1295  * This is SMP safe as current->tgid does not change.
1296  */
1297 asmlinkage long sys_getpid(void)
1298 {
1299         return current->tgid;
1300 }
1301
1302 /*
1303  * Accessing ->real_parent is not SMP-safe, it could
1304  * change from under us. However, we can use a stale
1305  * value of ->real_parent under rcu_read_lock(), see
1306  * release_task()->call_rcu(delayed_put_task_struct).
1307  */
1308 asmlinkage long sys_getppid(void)
1309 {
1310         int pid;
1311
1312         rcu_read_lock();
1313         pid = rcu_dereference(current->real_parent)->tgid;
1314         rcu_read_unlock();
1315
1316         return pid;
1317 }
1318
1319 asmlinkage long sys_getuid(void)
1320 {
1321         /* Only we change this so SMP safe */
1322         return current->uid;
1323 }
1324
1325 asmlinkage long sys_geteuid(void)
1326 {
1327         /* Only we change this so SMP safe */
1328         return current->euid;
1329 }
1330
1331 asmlinkage long sys_getgid(void)
1332 {
1333         /* Only we change this so SMP safe */
1334         return current->gid;
1335 }
1336
1337 asmlinkage long sys_getegid(void)
1338 {
1339         /* Only we change this so SMP safe */
1340         return  current->egid;
1341 }
1342
1343 #endif
1344
1345 static void process_timeout(unsigned long __data)
1346 {
1347         wake_up_process((struct task_struct *)__data);
1348 }
1349
1350 /**
1351  * schedule_timeout - sleep until timeout
1352  * @timeout: timeout value in jiffies
1353  *
1354  * Make the current task sleep until @timeout jiffies have
1355  * elapsed. The routine will return immediately unless
1356  * the current task state has been set (see set_current_state()).
1357  *
1358  * You can set the task state as follows -
1359  *
1360  * %TASK_UNINTERRUPTIBLE - at least @timeout jiffies are guaranteed to
1361  * pass before the routine returns. The routine will return 0
1362  *
1363  * %TASK_INTERRUPTIBLE - the routine may return early if a signal is
1364  * delivered to the current task. In this case the remaining time
1365  * in jiffies will be returned, or 0 if the timer expired in time
1366  *
1367  * The current task state is guaranteed to be TASK_RUNNING when this
1368  * routine returns.
1369  *
1370  * Specifying a @timeout value of %MAX_SCHEDULE_TIMEOUT will schedule
1371  * the CPU away without a bound on the timeout. In this case the return
1372  * value will be %MAX_SCHEDULE_TIMEOUT.
1373  *
1374  * In all cases the return value is guaranteed to be non-negative.
1375  */
1376 fastcall signed long __sched schedule_timeout(signed long timeout)
1377 {
1378         struct timer_list timer;
1379         unsigned long expire;
1380
1381         switch (timeout)
1382         {
1383         case MAX_SCHEDULE_TIMEOUT:
1384                 /*
1385                  * These two special cases are useful to be comfortable
1386                  * in the caller. Nothing more. We could take
1387                  * MAX_SCHEDULE_TIMEOUT from one of the negative value
1388                  * but I' d like to return a valid offset (>=0) to allow
1389                  * the caller to do everything it want with the retval.
1390                  */
1391                 schedule();
1392                 goto out;
1393         default:
1394                 /*
1395                  * Another bit of PARANOID. Note that the retval will be
1396                  * 0 since no piece of kernel is supposed to do a check
1397                  * for a negative retval of schedule_timeout() (since it
1398                  * should never happens anyway). You just have the printk()
1399                  * that will tell you if something is gone wrong and where.
1400                  */
1401                 if (timeout < 0) {
1402                         printk(KERN_ERR "schedule_timeout: wrong timeout "
1403                                 "value %lx\n", timeout);
1404                         dump_stack();
1405                         current->state = TASK_RUNNING;
1406                         goto out;
1407                 }
1408         }
1409
1410         expire = timeout + jiffies;
1411
1412         setup_timer(&timer, process_timeout, (unsigned long)current);
1413         __mod_timer(&timer, expire);
1414         schedule();
1415         del_singleshot_timer_sync(&timer);
1416
1417         timeout = expire - jiffies;
1418
1419  out:
1420         return timeout < 0 ? 0 : timeout;
1421 }
1422 EXPORT_SYMBOL(schedule_timeout);
1423
1424 /*
1425  * We can use __set_current_state() here because schedule_timeout() calls
1426  * schedule() unconditionally.
1427  */
1428 signed long __sched schedule_timeout_interruptible(signed long timeout)
1429 {
1430         __set_current_state(TASK_INTERRUPTIBLE);
1431         return schedule_timeout(timeout);
1432 }
1433 EXPORT_SYMBOL(schedule_timeout_interruptible);
1434
1435 signed long __sched schedule_timeout_uninterruptible(signed long timeout)
1436 {
1437         __set_current_state(TASK_UNINTERRUPTIBLE);
1438         return schedule_timeout(timeout);
1439 }
1440 EXPORT_SYMBOL(schedule_timeout_uninterruptible);
1441
1442 /* Thread ID - the internal kernel "pid" */
1443 asmlinkage long sys_gettid(void)
1444 {
1445         return current->pid;
1446 }
1447
1448 /**
1449  * do_sysinfo - fill in sysinfo struct
1450  * @info: pointer to buffer to fill
1451  */ 
1452 int do_sysinfo(struct sysinfo *info)
1453 {
1454         unsigned long mem_total, sav_total;
1455         unsigned int mem_unit, bitcount;
1456         unsigned long seq;
1457
1458         memset(info, 0, sizeof(struct sysinfo));
1459
1460         do {
1461                 struct timespec tp;
1462                 seq = read_seqbegin(&xtime_lock);
1463
1464                 /*
1465                  * This is annoying.  The below is the same thing
1466                  * posix_get_clock_monotonic() does, but it wants to
1467                  * take the lock which we want to cover the loads stuff
1468                  * too.
1469                  */
1470
1471                 getnstimeofday(&tp);
1472                 tp.tv_sec += wall_to_monotonic.tv_sec;
1473                 tp.tv_nsec += wall_to_monotonic.tv_nsec;
1474                 if (tp.tv_nsec - NSEC_PER_SEC >= 0) {
1475                         tp.tv_nsec = tp.tv_nsec - NSEC_PER_SEC;
1476                         tp.tv_sec++;
1477                 }
1478                 info->uptime = tp.tv_sec + (tp.tv_nsec ? 1 : 0);
1479
1480                 info->loads[0] = avenrun[0] << (SI_LOAD_SHIFT - FSHIFT);
1481                 info->loads[1] = avenrun[1] << (SI_LOAD_SHIFT - FSHIFT);
1482                 info->loads[2] = avenrun[2] << (SI_LOAD_SHIFT - FSHIFT);
1483
1484                 info->procs = nr_threads;
1485         } while (read_seqretry(&xtime_lock, seq));
1486
1487         si_meminfo(info);
1488         si_swapinfo(info);
1489
1490         /*
1491          * If the sum of all the available memory (i.e. ram + swap)
1492          * is less than can be stored in a 32 bit unsigned long then
1493          * we can be binary compatible with 2.2.x kernels.  If not,
1494          * well, in that case 2.2.x was broken anyways...
1495          *
1496          *  -Erik Andersen <andersee@debian.org>
1497          */
1498
1499         mem_total = info->totalram + info->totalswap;
1500         if (mem_total < info->totalram || mem_total < info->totalswap)
1501                 goto out;
1502         bitcount = 0;
1503         mem_unit = info->mem_unit;
1504         while (mem_unit > 1) {
1505                 bitcount++;
1506                 mem_unit >>= 1;
1507                 sav_total = mem_total;
1508                 mem_total <<= 1;
1509                 if (mem_total < sav_total)
1510                         goto out;
1511         }
1512
1513         /*
1514          * If mem_total did not overflow, multiply all memory values by
1515          * info->mem_unit and set it to 1.  This leaves things compatible
1516          * with 2.2.x, and also retains compatibility with earlier 2.4.x
1517          * kernels...
1518          */
1519
1520         info->mem_unit = 1;
1521         info->totalram <<= bitcount;
1522         info->freeram <<= bitcount;
1523         info->sharedram <<= bitcount;
1524         info->bufferram <<= bitcount;
1525         info->totalswap <<= bitcount;
1526         info->freeswap <<= bitcount;
1527         info->totalhigh <<= bitcount;
1528         info->freehigh <<= bitcount;
1529
1530 out:
1531         return 0;
1532 }
1533
1534 asmlinkage long sys_sysinfo(struct sysinfo __user *info)
1535 {
1536         struct sysinfo val;
1537
1538         do_sysinfo(&val);
1539
1540         if (copy_to_user(info, &val, sizeof(struct sysinfo)))
1541                 return -EFAULT;
1542
1543         return 0;
1544 }
1545
1546 /*
1547  * lockdep: we want to track each per-CPU base as a separate lock-class,
1548  * but timer-bases are kmalloc()-ed, so we need to attach separate
1549  * keys to them:
1550  */
1551 static struct lock_class_key base_lock_keys[NR_CPUS];
1552
1553 static int __devinit init_timers_cpu(int cpu)
1554 {
1555         int j;
1556         tvec_base_t *base;
1557         static char __devinitdata tvec_base_done[NR_CPUS];
1558
1559         if (!tvec_base_done[cpu]) {
1560                 static char boot_done;
1561
1562                 if (boot_done) {
1563                         /*
1564                          * The APs use this path later in boot
1565                          */
1566                         base = kmalloc_node(sizeof(*base), GFP_KERNEL,
1567                                                 cpu_to_node(cpu));
1568                         if (!base)
1569                                 return -ENOMEM;
1570                         memset(base, 0, sizeof(*base));
1571                         per_cpu(tvec_bases, cpu) = base;
1572                 } else {
1573                         /*
1574                          * This is for the boot CPU - we use compile-time
1575                          * static initialisation because per-cpu memory isn't
1576                          * ready yet and because the memory allocators are not
1577                          * initialised either.
1578                          */
1579                         boot_done = 1;
1580                         base = &boot_tvec_bases;
1581                 }
1582                 tvec_base_done[cpu] = 1;
1583         } else {
1584                 base = per_cpu(tvec_bases, cpu);
1585         }
1586
1587         spin_lock_init(&base->lock);
1588         lockdep_set_class(&base->lock, base_lock_keys + cpu);
1589
1590         for (j = 0; j < TVN_SIZE; j++) {
1591                 INIT_LIST_HEAD(base->tv5.vec + j);
1592                 INIT_LIST_HEAD(base->tv4.vec + j);
1593                 INIT_LIST_HEAD(base->tv3.vec + j);
1594                 INIT_LIST_HEAD(base->tv2.vec + j);
1595         }
1596         for (j = 0; j < TVR_SIZE; j++)
1597                 INIT_LIST_HEAD(base->tv1.vec + j);
1598
1599         base->timer_jiffies = jiffies;
1600         return 0;
1601 }
1602
1603 #ifdef CONFIG_HOTPLUG_CPU
1604 static void migrate_timer_list(tvec_base_t *new_base, struct list_head *head)
1605 {
1606         struct timer_list *timer;
1607
1608         while (!list_empty(head)) {
1609                 timer = list_entry(head->next, struct timer_list, entry);
1610                 detach_timer(timer, 0);
1611                 timer->base = new_base;
1612                 internal_add_timer(new_base, timer);
1613         }
1614 }
1615
1616 static void __devinit migrate_timers(int cpu)
1617 {
1618         tvec_base_t *old_base;
1619         tvec_base_t *new_base;
1620         int i;
1621
1622         BUG_ON(cpu_online(cpu));
1623         old_base = per_cpu(tvec_bases, cpu);
1624         new_base = get_cpu_var(tvec_bases);
1625
1626         local_irq_disable();
1627         spin_lock(&new_base->lock);
1628         spin_lock(&old_base->lock);
1629
1630         BUG_ON(old_base->running_timer);
1631
1632         for (i = 0; i < TVR_SIZE; i++)
1633                 migrate_timer_list(new_base, old_base->tv1.vec + i);
1634         for (i = 0; i < TVN_SIZE; i++) {
1635                 migrate_timer_list(new_base, old_base->tv2.vec + i);
1636                 migrate_timer_list(new_base, old_base->tv3.vec + i);
1637                 migrate_timer_list(new_base, old_base->tv4.vec + i);
1638                 migrate_timer_list(new_base, old_base->tv5.vec + i);
1639         }
1640
1641         spin_unlock(&old_base->lock);
1642         spin_unlock(&new_base->lock);
1643         local_irq_enable();
1644         put_cpu_var(tvec_bases);
1645 }
1646 #endif /* CONFIG_HOTPLUG_CPU */
1647
1648 static int __cpuinit timer_cpu_notify(struct notifier_block *self,
1649                                 unsigned long action, void *hcpu)
1650 {
1651         long cpu = (long)hcpu;
1652         switch(action) {
1653         case CPU_UP_PREPARE:
1654                 if (init_timers_cpu(cpu) < 0)
1655                         return NOTIFY_BAD;
1656                 break;
1657 #ifdef CONFIG_HOTPLUG_CPU
1658         case CPU_DEAD:
1659                 migrate_timers(cpu);
1660                 break;
1661 #endif
1662         default:
1663                 break;
1664         }
1665         return NOTIFY_OK;
1666 }
1667
1668 static struct notifier_block __cpuinitdata timers_nb = {
1669         .notifier_call  = timer_cpu_notify,
1670 };
1671
1672
1673 void __init init_timers(void)
1674 {
1675         int err = timer_cpu_notify(&timers_nb, (unsigned long)CPU_UP_PREPARE,
1676                                 (void *)(long)smp_processor_id());
1677
1678         BUG_ON(err == NOTIFY_BAD);
1679         register_cpu_notifier(&timers_nb);
1680         open_softirq(TIMER_SOFTIRQ, run_timer_softirq, NULL);
1681 }
1682
1683 #ifdef CONFIG_TIME_INTERPOLATION
1684
1685 struct time_interpolator *time_interpolator __read_mostly;
1686 static struct time_interpolator *time_interpolator_list __read_mostly;
1687 static DEFINE_SPINLOCK(time_interpolator_lock);
1688
1689 static inline cycles_t time_interpolator_get_cycles(unsigned int src)
1690 {
1691         unsigned long (*x)(void);
1692
1693         switch (src)
1694         {
1695                 case TIME_SOURCE_FUNCTION:
1696                         x = time_interpolator->addr;
1697                         return x();
1698
1699                 case TIME_SOURCE_MMIO64 :
1700                         return readq_relaxed((void __iomem *)time_interpolator->addr);
1701
1702                 case TIME_SOURCE_MMIO32 :
1703                         return readl_relaxed((void __iomem *)time_interpolator->addr);
1704
1705                 default: return get_cycles();
1706         }
1707 }
1708
1709 static inline u64 time_interpolator_get_counter(int writelock)
1710 {
1711         unsigned int src = time_interpolator->source;
1712
1713         if (time_interpolator->jitter)
1714         {
1715                 cycles_t lcycle;
1716                 cycles_t now;
1717
1718                 do {
1719                         lcycle = time_interpolator->last_cycle;
1720                         now = time_interpolator_get_cycles(src);
1721                         if (lcycle && time_after(lcycle, now))
1722                                 return lcycle;
1723
1724                         /* When holding the xtime write lock, there's no need
1725                          * to add the overhead of the cmpxchg.  Readers are
1726                          * force to retry until the write lock is released.
1727                          */
1728                         if (writelock) {
1729                                 time_interpolator->last_cycle = now;
1730                                 return now;
1731                         }
1732                         /* Keep track of the last timer value returned. The use of cmpxchg here
1733                          * will cause contention in an SMP environment.
1734                          */
1735                 } while (unlikely(cmpxchg(&time_interpolator->last_cycle, lcycle, now) != lcycle));
1736                 return now;
1737         }
1738         else
1739                 return time_interpolator_get_cycles(src);
1740 }
1741
1742 void time_interpolator_reset(void)
1743 {
1744         time_interpolator->offset = 0;
1745         time_interpolator->last_counter = time_interpolator_get_counter(1);
1746 }
1747
1748 #define GET_TI_NSECS(count,i) (((((count) - i->last_counter) & (i)->mask) * (i)->nsec_per_cyc) >> (i)->shift)
1749
1750 unsigned long time_interpolator_get_offset(void)
1751 {
1752         /* If we do not have a time interpolator set up then just return zero */
1753         if (!time_interpolator)
1754                 return 0;
1755
1756         return time_interpolator->offset +
1757                 GET_TI_NSECS(time_interpolator_get_counter(0), time_interpolator);
1758 }
1759
1760 #define INTERPOLATOR_ADJUST 65536
1761 #define INTERPOLATOR_MAX_SKIP 10*INTERPOLATOR_ADJUST
1762
1763 void time_interpolator_update(long delta_nsec)
1764 {
1765         u64 counter;
1766         unsigned long offset;
1767
1768         /* If there is no time interpolator set up then do nothing */
1769         if (!time_interpolator)
1770                 return;
1771
1772         /*
1773          * The interpolator compensates for late ticks by accumulating the late
1774          * time in time_interpolator->offset. A tick earlier than expected will
1775          * lead to a reset of the offset and a corresponding jump of the clock
1776          * forward. Again this only works if the interpolator clock is running
1777          * slightly slower than the regular clock and the tuning logic insures
1778          * that.
1779          */
1780
1781         counter = time_interpolator_get_counter(1);
1782         offset = time_interpolator->offset +
1783                         GET_TI_NSECS(counter, time_interpolator);
1784
1785         if (delta_nsec < 0 || (unsigned long) delta_nsec < offset)
1786                 time_interpolator->offset = offset - delta_nsec;
1787         else {
1788                 time_interpolator->skips++;
1789                 time_interpolator->ns_skipped += delta_nsec - offset;
1790                 time_interpolator->offset = 0;
1791         }
1792         time_interpolator->last_counter = counter;
1793
1794         /* Tuning logic for time interpolator invoked every minute or so.
1795          * Decrease interpolator clock speed if no skips occurred and an offset is carried.
1796          * Increase interpolator clock speed if we skip too much time.
1797          */
1798         if (jiffies % INTERPOLATOR_ADJUST == 0)
1799         {
1800                 if (time_interpolator->skips == 0 && time_interpolator->offset > tick_nsec)
1801                         time_interpolator->nsec_per_cyc--;
1802                 if (time_interpolator->ns_skipped > INTERPOLATOR_MAX_SKIP && time_interpolator->offset == 0)
1803                         time_interpolator->nsec_per_cyc++;
1804                 time_interpolator->skips = 0;
1805                 time_interpolator->ns_skipped = 0;
1806         }
1807 }
1808
1809 static inline int
1810 is_better_time_interpolator(struct time_interpolator *new)
1811 {
1812         if (!time_interpolator)
1813                 return 1;
1814         return new->frequency > 2*time_interpolator->frequency ||
1815             (unsigned long)new->drift < (unsigned long)time_interpolator->drift;
1816 }
1817
1818 void
1819 register_time_interpolator(struct time_interpolator *ti)
1820 {
1821         unsigned long flags;
1822
1823         /* Sanity check */
1824         BUG_ON(ti->frequency == 0 || ti->mask == 0);
1825
1826         ti->nsec_per_cyc = ((u64)NSEC_PER_SEC << ti->shift) / ti->frequency;
1827         spin_lock(&time_interpolator_lock);
1828         write_seqlock_irqsave(&xtime_lock, flags);
1829         if (is_better_time_interpolator(ti)) {
1830                 time_interpolator = ti;
1831                 time_interpolator_reset();
1832         }
1833         write_sequnlock_irqrestore(&xtime_lock, flags);
1834
1835         ti->next = time_interpolator_list;
1836         time_interpolator_list = ti;
1837         spin_unlock(&time_interpolator_lock);
1838 }
1839
1840 void
1841 unregister_time_interpolator(struct time_interpolator *ti)
1842 {
1843         struct time_interpolator *curr, **prev;
1844         unsigned long flags;
1845
1846         spin_lock(&time_interpolator_lock);
1847         prev = &time_interpolator_list;
1848         for (curr = *prev; curr; curr = curr->next) {
1849                 if (curr == ti) {
1850                         *prev = curr->next;
1851                         break;
1852                 }
1853                 prev = &curr->next;
1854         }
1855
1856         write_seqlock_irqsave(&xtime_lock, flags);
1857         if (ti == time_interpolator) {
1858                 /* we lost the best time-interpolator: */
1859                 time_interpolator = NULL;
1860                 /* find the next-best interpolator */
1861                 for (curr = time_interpolator_list; curr; curr = curr->next)
1862                         if (is_better_time_interpolator(curr))
1863                                 time_interpolator = curr;
1864                 time_interpolator_reset();
1865         }
1866         write_sequnlock_irqrestore(&xtime_lock, flags);
1867         spin_unlock(&time_interpolator_lock);
1868 }
1869 #endif /* CONFIG_TIME_INTERPOLATION */
1870
1871 /**
1872  * msleep - sleep safely even with waitqueue interruptions
1873  * @msecs: Time in milliseconds to sleep for
1874  */
1875 void msleep(unsigned int msecs)
1876 {
1877         unsigned long timeout = msecs_to_jiffies(msecs) + 1;
1878
1879         while (timeout)
1880                 timeout = schedule_timeout_uninterruptible(timeout);
1881 }
1882
1883 EXPORT_SYMBOL(msleep);
1884
1885 /**
1886  * msleep_interruptible - sleep waiting for signals
1887  * @msecs: Time in milliseconds to sleep for
1888  */
1889 unsigned long msleep_interruptible(unsigned int msecs)
1890 {
1891         unsigned long timeout = msecs_to_jiffies(msecs) + 1;
1892
1893         while (timeout && !signal_pending(current))
1894                 timeout = schedule_timeout_interruptible(timeout);
1895         return jiffies_to_msecs(timeout);
1896 }
1897
1898 EXPORT_SYMBOL(msleep_interruptible);