/* *  linux/kernel/timer.c * *  Kernel internal timers, kernel timekeeping, basic process system calls * *  Copyright (C) 1991, 1992  Linus Torvalds * *  1997-01-28  Modified by Finn Arne Gangstad to make timers scale better. * *  1997-09-10  Updated NTP code according to technical memorandum Jan '96 *              "A Kernel Model for Precision Timekeeping" by Dave Mills *  1998-12-24  Fixed a xtime SMP race (we need the xtime_lock rw spinlock to *              serialize accesses to xtime/lost_ticks). *                              Copyright (C) 1998  Andrea Arcangeli *  1999-03-10  Improved NTP compatibility by Ulrich Windl *  2002-05-31	Move sys_sysinfo here and make its locking sane, Robert Love *  2000-10-05  Implemented scalable SMP per-CPU timer handling. *                              Copyright (C) 2000, 2001, 2002  Ingo Molnar *              Designed by David S. Miller, Alexey Kuznetsov and Ingo Molnar */ #include <linux/kernel_stat.h>#include <linux/module.h>#include <linux/interrupt.h>#include <linux/percpu.h>#include <linux/init.h>#include <linux/mm.h>#include <linux/swap.h>#include <linux/notifier.h>#include <linux/thread_info.h>#include <linux/time.h>#include <linux/jiffies.h>#include <linux/posix-timers.h>#include <linux/cpu.h>#include <linux/syscalls.h>#include <linux/delay.h> #include <asm/uaccess.h>#include <asm/unistd.h>#include <asm/div64.h>#include <asm/timex.h>#include <asm/io.h> #ifdef CONFIG_TIME_INTERPOLATIONstatic void time_interpolator_update(long delta_nsec);#else#define time_interpolator_update(x)#endif u64 jiffies_64 __cacheline_aligned_in_smp = INITIAL_JIFFIES; EXPORT_SYMBOL(jiffies_64); /* * per-CPU timer vector definitions: */ #define TVN_BITS (CONFIG_BASE_SMALL ? 4 : 6)#define TVR_BITS (CONFIG_BASE_SMALL ? 6 : 8)#define TVN_SIZE (1 << TVN_BITS)#define TVR_SIZE (1 << TVR_BITS)#define TVN_MASK (TVN_SIZE - 1)#define TVR_MASK (TVR_SIZE - 1) struct timer_base_s {	spinlock_t lock;	struct timer_list *running_timer;}; typedef struct tvec_s {	struct list_head vec[TVN_SIZE];} tvec_t; typedef struct tvec_root_s {	struct list_head vec[TVR_SIZE];} tvec_root_t; struct tvec_t_base_s {	struct timer_base_s t_base;	unsigned long timer_jiffies;	tvec_root_t tv1;	tvec_t tv2;	tvec_t tv3;	tvec_t tv4;	tvec_t tv5;} ____cacheline_aligned_in_smp; typedef struct tvec_t_base_s tvec_base_t;static DEFINE_PER_CPU(tvec_base_t *, tvec_bases);static tvec_base_t boot_tvec_bases; static inline void set_running_timer(tvec_base_t *base,					struct timer_list *timer){#ifdef CONFIG_SMP	base->t_base.running_timer = timer;#endif} static void internal_add_timer(tvec_base_t *base, struct timer_list *timer){	unsigned long expires = timer->expires;	unsigned long idx = expires - base->timer_jiffies;	struct list_head *vec; 	if (idx < TVR_SIZE) {		int i = expires & TVR_MASK;		vec = base->tv1.vec + i;	} else if (idx < 1 << (TVR_BITS + TVN_BITS)) {		int i = (expires >> TVR_BITS) & TVN_MASK;		vec = base->tv2.vec + i;	} else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) {		int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;		vec = base->tv3.vec + i;	} else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) {		int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;		vec = base->tv4.vec + i;	} else if ((signed long) idx < 0) {		/*		 * Can happen if you add a timer with expires == jiffies,		 * or you set a timer to go off in the past		 */		vec = base->tv1.vec + (base->timer_jiffies & TVR_MASK);	} else {		int i;		/* If the timeout is larger than 0xffffffff on 64-bit		 * architectures then we use the maximum timeout:		 */		if (idx > 0xffffffffUL) {			idx = 0xffffffffUL;			expires = idx + base->timer_jiffies;		}		i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;		vec = base->tv5.vec + i;	}	/*	 * Timers are FIFO:	 */	list_add_tail(&timer->entry, vec);} typedef struct timer_base_s timer_base_t;/* * Used by TIMER_INITIALIZER, we can't use per_cpu(tvec_bases) * at compile time, and we need timer->base to lock the timer. */timer_base_t __init_timer_base	____cacheline_aligned_in_smp = { .lock = SPIN_LOCK_UNLOCKED };EXPORT_SYMBOL(__init_timer_base); /*** * init_timer - initialize a timer. * @timer: the timer to be initialized * * init_timer() must be done to a timer prior calling *any* of the * other timer functions. */void fastcall init_timer(struct timer_list *timer){	timer->entry.next = NULL;	timer->base = &per_cpu(tvec_bases, raw_smp_processor_id())->t_base;}EXPORT_SYMBOL(init_timer); static inline void detach_timer(struct timer_list *timer,					int clear_pending){	struct list_head *entry = &timer->entry; 	__list_del(entry->prev, entry->next);	if (clear_pending)		entry->next = NULL;	entry->prev = LIST_POISON2;} /* * We are using hashed locking: holding per_cpu(tvec_bases).t_base.lock * means that all timers which are tied to this base via timer->base are * locked, and the base itself is locked too. * * So __run_timers/migrate_timers can safely modify all timers which could * be found on ->tvX lists. * * When the timer's base is locked, and the timer removed from list, it is * possible to set timer->base = NULL and drop the lock: the timer remains * locked. */static timer_base_t *lock_timer_base(struct timer_list *timer,					unsigned long *flags){	timer_base_t *base; 	for (;;) {		base = timer->base;		if (likely(base != NULL)) {			spin_lock_irqsave(&base->lock, *flags);			if (likely(base == timer->base))				return base;			/* The timer has migrated to another CPU */			spin_unlock_irqrestore(&base->lock, *flags);		}		cpu_relax();	}} int __mod_timer(struct timer_list *timer, unsigned long expires){	timer_base_t *base;	tvec_base_t *new_base;	unsigned long flags;	int ret = 0; 	BUG_ON(!timer->function); 	base = lock_timer_base(timer, &flags); 	if (timer_pending(timer)) {		detach_timer(timer, 0);		ret = 1;	} 	new_base = __get_cpu_var(tvec_bases); 	if (base != &new_base->t_base) {		/*		 * We are trying to schedule the timer on the local CPU.		 * However we can't change timer's base while it is running,		 * otherwise del_timer_sync() can't detect that the timer's		 * handler yet has not finished. This also guarantees that		 * the timer is serialized wrt itself.		 */		if (unlikely(base->running_timer == timer)) {			/* The timer remains on a former base */			new_base = container_of(base, tvec_base_t, t_base);		} else {			/* See the comment in lock_timer_base() */			timer->base = NULL;			spin_unlock(&base->lock);			spin_lock(&new_base->t_base.lock);			timer->base = &new_base->t_base;		}	} 	timer->expires = expires;	internal_add_timer(new_base, timer);	spin_unlock_irqrestore(&new_base->t_base.lock, flags); 	return ret;} EXPORT_SYMBOL(__mod_timer); /*** * add_timer_on - start a timer on a particular CPU * @timer: the timer to be added * @cpu: the CPU to start it on * * This is not very scalable on SMP. Double adds are not possible. */void add_timer_on(struct timer_list *timer, int cpu){	tvec_base_t *base = per_cpu(tvec_bases, cpu);  	unsigned long flags;   	BUG_ON(timer_pending(timer) || !timer->function);	spin_lock_irqsave(&base->t_base.lock, flags);	timer->base = &base->t_base;	internal_add_timer(base, timer);	spin_unlock_irqrestore(&base->t_base.lock, flags);}  /*** * mod_timer - modify a timer's timeout * @timer: the timer to be modified * * mod_timer is a more efficient way to update the expire field of an * active timer (if the timer is inactive it will be activated) * * mod_timer(timer, expires) is equivalent to: * *     del_timer(timer); timer->expires = expires; add_timer(timer); * * Note that if there are multiple unserialized concurrent users of the * same timer, then mod_timer() is the only safe way to modify the timeout, * since add_timer() cannot modify an already running timer. * * The function returns whether it has modified a pending timer or not. * (ie. mod_timer() of an inactive timer returns 0, mod_timer() of an * active timer returns 1.) */int mod_timer(struct timer_list *timer, unsigned long expires){	BUG_ON(!timer->function); 	/*	 * This is a common optimization triggered by the	 * networking code - if the timer is re-modified	 * to be the same thing then just return:	 */	if (timer->expires == expires && timer_pending(timer))		return 1; 	return __mod_timer(timer, expires);} EXPORT_SYMBOL(mod_timer); /*** * del_timer - deactive a timer. * @timer: the timer to be deactivated * * del_timer() deactivates a timer - this works on both active and inactive * timers. * * The function returns whether it has deactivated a pending timer or not. * (ie. del_timer() of an inactive timer returns 0, del_timer() of an * active timer returns 1.) */int del_timer(struct timer_list *timer){	timer_base_t *base;	unsigned long flags;	int ret = 0; 	if (timer_pending(timer)) {		base = lock_timer_base(timer, &flags);		if (timer_pending(timer)) {			detach_timer(timer, 1);			ret = 1;		}		spin_unlock_irqrestore(&base->lock, flags);	} 	return ret;} EXPORT_SYMBOL(del_timer); #ifdef CONFIG_SMP/* * This function tries to deactivate a timer. Upon successful (ret >= 0) * exit the timer is not queued and the handler is not running on any CPU. * * It must not be called from interrupt contexts. */int try_to_del_timer_sync(struct timer_list *timer){	timer_base_t *base;	unsigned long flags;	int ret = -1; 	base = lock_timer_base(timer, &flags); 	if (base->running_timer == timer)		goto out; 	ret = 0;	if (timer_pending(timer)) {		detach_timer(timer, 1);		ret = 1;	}out:	spin_unlock_irqrestore(&base->lock, flags); 	return ret;} /*** * del_timer_sync - deactivate a timer and wait for the handler to finish. * @timer: the timer to be deactivated * * This function only differs from del_timer() on SMP: besides deactivating * the timer it also makes sure the handler has finished executing on other * CPUs. * * Synchronization rules: callers must prevent restarting of the timer, * otherwise this function is meaningless. It must not be called from * interrupt contexts. The caller must not hold locks which would prevent * completion of the timer's handler. The timer's handler must not call * add_timer_on(). Upon exit the timer is not queued and the handler is * not running on any CPU. * * The function returns whether it has deactivated a pending timer or not. */int del_timer_sync(struct timer_list *timer){	for (;;) {		int ret = try_to_del_timer_sync(timer);		if (ret >= 0)			return ret;	}} EXPORT_SYMBOL(del_timer_sync);#endif static int cascade(tvec_base_t *base, tvec_t *tv, int index){	/* cascade all the timers from tv up one level */	struct list_head *head, *curr; 	head = tv->vec + index;	curr = head->next;	/*	 * We are removing _all_ timers from the list, so we don't  have to	 * detach them individually, just clear the list afterwards.	 */	while (curr != head) {		struct timer_list *tmp; 		tmp = list_entry(curr, struct timer_list, entry);		BUG_ON(tmp->base != &base->t_base);		curr = curr->next;		internal_add_timer(base, tmp);	}	INIT_LIST_HEAD(head); 	return index;} /*** * __run_timers - run all expired timers (if any) on this CPU. * @base: the timer vector to be processed. * * This function cascades all vectors and executes all expired timer * vectors. */#define INDEX(N) (base->timer_jiffies >> (TVR_BITS + N * TVN_BITS)) & TVN_MASK static inline void __run_timers(tvec_base_t *base){	struct timer_list *timer; 	spin_lock_irq(&base->t_base.lock);	while (time_after_eq(jiffies, base->timer_jiffies)) {		struct list_head work_list = LIST_HEAD_INIT(work_list);		struct list_head *head = &work_list; 		int index = base->timer_jiffies & TVR_MASK; 		/*		 * Cascade timers:		 */		if (!index &&			(!cascade(base, &base->tv2, INDEX(0))) &&				(!cascade(base, &base->tv3, INDEX(1))) &&					!cascade(base, &base->tv4, INDEX(2)))			cascade(base, &base->tv5, INDEX(3));		++base->timer_jiffies; 		list_splice_init(base->tv1.vec + index, &work_list);		while (!list_empty(head)) {			void (*fn)(unsigned long);			unsigned long data; 			timer = list_entry(head->next,struct timer_list,entry); 			fn = timer->function; 			data = timer->data; 			set_running_timer(base, timer);			detach_timer(timer, 1);			spin_unlock_irq(&base->t_base.lock);			{				int preempt_count = preempt_count();				fn(data);				if (preempt_count != preempt_count()) {					printk(KERN_WARNING "huh, entered %p "					       "with preempt_count %08x, exited"					       " with %08x?\n",					       fn, preempt_count,					       preempt_count());					BUG();				}			}			spin_lock_irq(&base->t_base.lock);		}	}	set_running_timer(base, NULL);	spin_unlock_irq(&base->t_base.lock);} #ifdef CONFIG_NO_IDLE_HZ/* * Find out when the next timer event is due to happen. This * is used on S/390 to stop all activity when a cpus is idle. * This functions needs to be called disabled. */unsigned long next_timer_interrupt(void){	tvec_base_t *base;	struct list_head *list;	struct timer_list *nte;	unsigned long expires;	unsigned long hr_expires = MAX_JIFFY_OFFSET;	ktime_t hr_delta;	tvec_t *varray[4];	int i, j; 	hr_delta = hrtimer_get_next_event();	if (hr_delta.tv64 != KTIME_MAX) {		struct timespec tsdelta;

Lines 1–500 of 1594. Load more