1/* 2 * linux/kernel/timer.c 3 * 4 * Kernel internal timers 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/export.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/pid_namespace.h> 30#include <linux/notifier.h> 31#include <linux/thread_info.h> 32#include <linux/time.h> 33#include <linux/jiffies.h> 34#include <linux/posix-timers.h> 35#include <linux/cpu.h> 36#include <linux/syscalls.h> 37#include <linux/delay.h> 38#include <linux/tick.h> 39#include <linux/kallsyms.h> 40#include <linux/irq_work.h> 41#include <linux/sched.h> 42#include <linux/sched/sysctl.h> 43#include <linux/slab.h> 44#include <linux/compat.h> 45 46#include <asm/uaccess.h> 47#include <asm/unistd.h> 48#include <asm/div64.h> 49#include <asm/timex.h> 50#include <asm/io.h> 51 52#define CREATE_TRACE_POINTS 53#include <trace/events/timer.h> 54 55__visible u64 jiffies_64 __cacheline_aligned_in_smp = INITIAL_JIFFIES; 56 57EXPORT_SYMBOL(jiffies_64); 58 59/* 60 * per-CPU timer vector definitions: 61 */ 62#define TVN_BITS (CONFIG_BASE_SMALL ? 4 : 6) 63#define TVR_BITS (CONFIG_BASE_SMALL ? 6 : 8) 64#define TVN_SIZE (1 << TVN_BITS) 65#define TVR_SIZE (1 << TVR_BITS) 66#define TVN_MASK (TVN_SIZE - 1) 67#define TVR_MASK (TVR_SIZE - 1) 68#define MAX_TVAL ((unsigned long)((1ULL << (TVR_BITS + 4*TVN_BITS)) - 1)) 69 70struct tvec { 71 struct list_head vec[TVN_SIZE]; 72}; 73 74struct tvec_root { 75 struct list_head vec[TVR_SIZE]; 76}; 77 78struct tvec_base { 79 spinlock_t lock; 80 struct timer_list *running_timer; 81 unsigned long timer_jiffies; 82 unsigned long next_timer; 83 unsigned long active_timers; 84 unsigned long all_timers; 85 int cpu; 86 struct tvec_root tv1; 87 struct tvec tv2; 88 struct tvec tv3; 89 struct tvec tv4; 90 struct tvec tv5; 91} ____cacheline_aligned; 92 93struct tvec_base boot_tvec_bases; 94EXPORT_SYMBOL(boot_tvec_bases); 95static DEFINE_PER_CPU(struct tvec_base *, tvec_bases) = &boot_tvec_bases; 96 97/* Functions below help us manage 'deferrable' flag */ 98static inline unsigned int tbase_get_deferrable(struct tvec_base *base) 99{ 100 return ((unsigned int)(unsigned long)base & TIMER_DEFERRABLE); 101} 102 103static inline unsigned int tbase_get_irqsafe(struct tvec_base *base) 104{ 105 return ((unsigned int)(unsigned long)base & TIMER_IRQSAFE); 106} 107 108static inline struct tvec_base *tbase_get_base(struct tvec_base *base) 109{ 110 return ((struct tvec_base *)((unsigned long)base & ~TIMER_FLAG_MASK)); 111} 112 113static inline void 114timer_set_base(struct timer_list *timer, struct tvec_base *new_base) 115{ 116 unsigned long flags = (unsigned long)timer->base & TIMER_FLAG_MASK; 117 118 timer->base = (struct tvec_base *)((unsigned long)(new_base) | flags); 119} 120 121static unsigned long round_jiffies_common(unsigned long j, int cpu, 122 bool force_up) 123{ 124 int rem; 125 unsigned long original = j; 126 127 /* 128 * We don't want all cpus firing their timers at once hitting the 129 * same lock or cachelines, so we skew each extra cpu with an extra 130 * 3 jiffies. This 3 jiffies came originally from the mm/ code which 131 * already did this. 132 * The skew is done by adding 3*cpunr, then round, then subtract this 133 * extra offset again. 134 */ 135 j += cpu * 3; 136 137 rem = j % HZ; 138 139 /* 140 * If the target jiffie is just after a whole second (which can happen 141 * due to delays of the timer irq, long irq off times etc etc) then 142 * we should round down to the whole second, not up. Use 1/4th second 143 * as cutoff for this rounding as an extreme upper bound for this. 144 * But never round down if @force_up is set. 145 */ 146 if (rem < HZ/4 && !force_up) /* round down */ 147 j = j - rem; 148 else /* round up */ 149 j = j - rem + HZ; 150 151 /* now that we have rounded, subtract the extra skew again */ 152 j -= cpu * 3; 153 154 /* 155 * Make sure j is still in the future. Otherwise return the 156 * unmodified value. 157 */ 158 return time_is_after_jiffies(j) ? j : original; 159} 160 161/** 162 * __round_jiffies - function to round jiffies to a full second 163 * @j: the time in (absolute) jiffies that should be rounded 164 * @cpu: the processor number on which the timeout will happen 165 * 166 * __round_jiffies() rounds an absolute time in the future (in jiffies) 167 * up or down to (approximately) full seconds. This is useful for timers 168 * for which the exact time they fire does not matter too much, as long as 169 * they fire approximately every X seconds. 170 * 171 * By rounding these timers to whole seconds, all such timers will fire 172 * at the same time, rather than at various times spread out. The goal 173 * of this is to have the CPU wake up less, which saves power. 174 * 175 * The exact rounding is skewed for each processor to avoid all 176 * processors firing at the exact same time, which could lead 177 * to lock contention or spurious cache line bouncing. 178 * 179 * The return value is the rounded version of the @j parameter. 180 */ 181unsigned long __round_jiffies(unsigned long j, int cpu) 182{ 183 return round_jiffies_common(j, cpu, false); 184} 185EXPORT_SYMBOL_GPL(__round_jiffies); 186 187/** 188 * __round_jiffies_relative - function to round jiffies to a full second 189 * @j: the time in (relative) jiffies that should be rounded 190 * @cpu: the processor number on which the timeout will happen 191 * 192 * __round_jiffies_relative() rounds a time delta in the future (in jiffies) 193 * up or down to (approximately) full seconds. This is useful for timers 194 * for which the exact time they fire does not matter too much, as long as 195 * they fire approximately every X seconds. 196 * 197 * By rounding these timers to whole seconds, all such timers will fire 198 * at the same time, rather than at various times spread out. The goal 199 * of this is to have the CPU wake up less, which saves power. 200 * 201 * The exact rounding is skewed for each processor to avoid all 202 * processors firing at the exact same time, which could lead 203 * to lock contention or spurious cache line bouncing. 204 * 205 * The return value is the rounded version of the @j parameter. 206 */ 207unsigned long __round_jiffies_relative(unsigned long j, int cpu) 208{ 209 unsigned long j0 = jiffies; 210 211 /* Use j0 because jiffies might change while we run */ 212 return round_jiffies_common(j + j0, cpu, false) - j0; 213} 214EXPORT_SYMBOL_GPL(__round_jiffies_relative); 215 216/** 217 * round_jiffies - function to round jiffies to a full second 218 * @j: the time in (absolute) jiffies that should be rounded 219 * 220 * round_jiffies() rounds an absolute time in the future (in jiffies) 221 * up or down to (approximately) full seconds. This is useful for timers 222 * for which the exact time they fire does not matter too much, as long as 223 * they fire approximately every X seconds. 224 * 225 * By rounding these timers to whole seconds, all such timers will fire 226 * at the same time, rather than at various times spread out. The goal 227 * of this is to have the CPU wake up less, which saves power. 228 * 229 * The return value is the rounded version of the @j parameter. 230 */ 231unsigned long round_jiffies(unsigned long j) 232{ 233 return round_jiffies_common(j, raw_smp_processor_id(), false); 234} 235EXPORT_SYMBOL_GPL(round_jiffies); 236 237/** 238 * round_jiffies_relative - function to round jiffies to a full second 239 * @j: the time in (relative) jiffies that should be rounded 240 * 241 * round_jiffies_relative() rounds a time delta in the future (in jiffies) 242 * up or down to (approximately) full seconds. This is useful for timers 243 * for which the exact time they fire does not matter too much, as long as 244 * they fire approximately every X seconds. 245 * 246 * By rounding these timers to whole seconds, all such timers will fire 247 * at the same time, rather than at various times spread out. The goal 248 * of this is to have the CPU wake up less, which saves power. 249 * 250 * The return value is the rounded version of the @j parameter. 251 */ 252unsigned long round_jiffies_relative(unsigned long j) 253{ 254 return __round_jiffies_relative(j, raw_smp_processor_id()); 255} 256EXPORT_SYMBOL_GPL(round_jiffies_relative); 257 258/** 259 * __round_jiffies_up - function to round jiffies up to a full second 260 * @j: the time in (absolute) jiffies that should be rounded 261 * @cpu: the processor number on which the timeout will happen 262 * 263 * This is the same as __round_jiffies() except that it will never 264 * round down. This is useful for timeouts for which the exact time 265 * of firing does not matter too much, as long as they don't fire too 266 * early. 267 */ 268unsigned long __round_jiffies_up(unsigned long j, int cpu) 269{ 270 return round_jiffies_common(j, cpu, true); 271} 272EXPORT_SYMBOL_GPL(__round_jiffies_up); 273 274/** 275 * __round_jiffies_up_relative - function to round jiffies up to a full second 276 * @j: the time in (relative) jiffies that should be rounded 277 * @cpu: the processor number on which the timeout will happen 278 * 279 * This is the same as __round_jiffies_relative() except that it will never 280 * round down. This is useful for timeouts for which the exact time 281 * of firing does not matter too much, as long as they don't fire too 282 * early. 283 */ 284unsigned long __round_jiffies_up_relative(unsigned long j, int cpu) 285{ 286 unsigned long j0 = jiffies; 287 288 /* Use j0 because jiffies might change while we run */ 289 return round_jiffies_common(j + j0, cpu, true) - j0; 290} 291EXPORT_SYMBOL_GPL(__round_jiffies_up_relative); 292 293/** 294 * round_jiffies_up - function to round jiffies up to a full second 295 * @j: the time in (absolute) jiffies that should be rounded 296 * 297 * This is the same as round_jiffies() except that it will never 298 * round down. This is useful for timeouts for which the exact time 299 * of firing does not matter too much, as long as they don't fire too 300 * early. 301 */ 302unsigned long round_jiffies_up(unsigned long j) 303{ 304 return round_jiffies_common(j, raw_smp_processor_id(), true); 305} 306EXPORT_SYMBOL_GPL(round_jiffies_up); 307 308/** 309 * round_jiffies_up_relative - function to round jiffies up to a full second 310 * @j: the time in (relative) jiffies that should be rounded 311 * 312 * This is the same as round_jiffies_relative() except that it will never 313 * round down. This is useful for timeouts for which the exact time 314 * of firing does not matter too much, as long as they don't fire too 315 * early. 316 */ 317unsigned long round_jiffies_up_relative(unsigned long j) 318{ 319 return __round_jiffies_up_relative(j, raw_smp_processor_id()); 320} 321EXPORT_SYMBOL_GPL(round_jiffies_up_relative); 322 323/** 324 * set_timer_slack - set the allowed slack for a timer 325 * @timer: the timer to be modified 326 * @slack_hz: the amount of time (in jiffies) allowed for rounding 327 * 328 * Set the amount of time, in jiffies, that a certain timer has 329 * in terms of slack. By setting this value, the timer subsystem 330 * will schedule the actual timer somewhere between 331 * the time mod_timer() asks for, and that time plus the slack. 332 * 333 * By setting the slack to -1, a percentage of the delay is used 334 * instead. 335 */ 336void set_timer_slack(struct timer_list *timer, int slack_hz) 337{ 338 timer->slack = slack_hz; 339} 340EXPORT_SYMBOL_GPL(set_timer_slack); 341 342/* 343 * If the list is empty, catch up ->timer_jiffies to the current time. 344 * The caller must hold the tvec_base lock. Returns true if the list 345 * was empty and therefore ->timer_jiffies was updated. 346 */ 347static bool catchup_timer_jiffies(struct tvec_base *base) 348{ 349 if (!base->all_timers) { 350 base->timer_jiffies = jiffies; 351 return true; 352 } 353 return false; 354} 355 356static void 357__internal_add_timer(struct tvec_base *base, struct timer_list *timer) 358{ 359 unsigned long expires = timer->expires; 360 unsigned long idx = expires - base->timer_jiffies; 361 struct list_head *vec; 362 363 if (idx < TVR_SIZE) { 364 int i = expires & TVR_MASK; 365 vec = base->tv1.vec + i; 366 } else if (idx < 1 << (TVR_BITS + TVN_BITS)) { 367 int i = (expires >> TVR_BITS) & TVN_MASK; 368 vec = base->tv2.vec + i; 369 } else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) { 370 int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK; 371 vec = base->tv3.vec + i; 372 } else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) { 373 int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK; 374 vec = base->tv4.vec + i; 375 } else if ((signed long) idx < 0) { 376 /* 377 * Can happen if you add a timer with expires == jiffies, 378 * or you set a timer to go off in the past 379 */ 380 vec = base->tv1.vec + (base->timer_jiffies & TVR_MASK); 381 } else { 382 int i; 383 /* If the timeout is larger than MAX_TVAL (on 64-bit 384 * architectures or with CONFIG_BASE_SMALL=1) then we 385 * use the maximum timeout. 386 */ 387 if (idx > MAX_TVAL) { 388 idx = MAX_TVAL; 389 expires = idx + base->timer_jiffies; 390 } 391 i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK; 392 vec = base->tv5.vec + i; 393 } 394 /* 395 * Timers are FIFO: 396 */ 397 list_add_tail(&timer->entry, vec); 398} 399 400static void internal_add_timer(struct tvec_base *base, struct timer_list *timer) 401{ 402 (void)catchup_timer_jiffies(base); 403 __internal_add_timer(base, timer); 404 /* 405 * Update base->active_timers and base->next_timer 406 */ 407 if (!tbase_get_deferrable(timer->base)) { 408 if (!base->active_timers++ || 409 time_before(timer->expires, base->next_timer)) 410 base->next_timer = timer->expires; 411 } 412 base->all_timers++; 413 414 /* 415 * Check whether the other CPU is in dynticks mode and needs 416 * to be triggered to reevaluate the timer wheel. 417 * We are protected against the other CPU fiddling 418 * with the timer by holding the timer base lock. This also 419 * makes sure that a CPU on the way to stop its tick can not 420 * evaluate the timer wheel. 421 * 422 * Spare the IPI for deferrable timers on idle targets though. 423 * The next busy ticks will take care of it. Except full dynticks 424 * require special care against races with idle_cpu(), lets deal 425 * with that later. 426 */ 427 if (!tbase_get_deferrable(base) || tick_nohz_full_cpu(base->cpu)) 428 wake_up_nohz_cpu(base->cpu); 429} 430 431#ifdef CONFIG_TIMER_STATS 432void __timer_stats_timer_set_start_info(struct timer_list *timer, void *addr) 433{ 434 if (timer->start_site) 435 return; 436 437 timer->start_site = addr; 438 memcpy(timer->start_comm, current->comm, TASK_COMM_LEN); 439 timer->start_pid = current->pid; 440} 441 442static void timer_stats_account_timer(struct timer_list *timer) 443{ 444 unsigned int flag = 0; 445 446 if (likely(!timer->start_site)) 447 return; 448 if (unlikely(tbase_get_deferrable(timer->base))) 449 flag |= TIMER_STATS_FLAG_DEFERRABLE; 450 451 timer_stats_update_stats(timer, timer->start_pid, timer->start_site, 452 timer->function, timer->start_comm, flag); 453} 454 455#else 456static void timer_stats_account_timer(struct timer_list *timer) {} 457#endif 458 459#ifdef CONFIG_DEBUG_OBJECTS_TIMERS 460 461static struct debug_obj_descr timer_debug_descr; 462 463static void *timer_debug_hint(void *addr) 464{ 465 return ((struct timer_list *) addr)->function; 466} 467 468/* 469 * fixup_init is called when: 470 * - an active object is initialized 471 */ 472static int timer_fixup_init(void *addr, enum debug_obj_state state) 473{ 474 struct timer_list *timer = addr; 475 476 switch (state) { 477 case ODEBUG_STATE_ACTIVE: 478 del_timer_sync(timer); 479 debug_object_init(timer, &timer_debug_descr); 480 return 1; 481 default: 482 return 0; 483 } 484} 485 486/* Stub timer callback for improperly used timers. */ 487static void stub_timer(unsigned long data) 488{ 489 WARN_ON(1); 490} 491 492/* 493 * fixup_activate is called when: 494 * - an active object is activated 495 * - an unknown object is activated (might be a statically initialized object) 496 */ 497static int timer_fixup_activate(void *addr, enum debug_obj_state state) 498{ 499 struct timer_list *timer = addr; 500 501 switch (state) { 502 503 case ODEBUG_STATE_NOTAVAILABLE: 504 /* 505 * This is not really a fixup. The timer was 506 * statically initialized. We just make sure that it 507 * is tracked in the object tracker. 508 */ 509 if (timer->entry.next == NULL && 510 timer->entry.prev == TIMER_ENTRY_STATIC) { 511 debug_object_init(timer, &timer_debug_descr); 512 debug_object_activate(timer, &timer_debug_descr); 513 return 0; 514 } else { 515 setup_timer(timer, stub_timer, 0); 516 return 1; 517 } 518 return 0; 519 520 case ODEBUG_STATE_ACTIVE: 521 WARN_ON(1); 522 523 default: 524 return 0; 525 } 526} 527 528/* 529 * fixup_free is called when: 530 * - an active object is freed 531 */ 532static int timer_fixup_free(void *addr, enum debug_obj_state state) 533{ 534 struct timer_list *timer = addr; 535 536 switch (state) { 537 case ODEBUG_STATE_ACTIVE: 538 del_timer_sync(timer); 539 debug_object_free(timer, &timer_debug_descr); 540 return 1; 541 default: 542 return 0; 543 } 544} 545 546/* 547 * fixup_assert_init is called when: 548 * - an untracked/uninit-ed object is found 549 */ 550static int timer_fixup_assert_init(void *addr, enum debug_obj_state state) 551{ 552 struct timer_list *timer = addr; 553 554 switch (state) { 555 case ODEBUG_STATE_NOTAVAILABLE: 556 if (timer->entry.prev == TIMER_ENTRY_STATIC) { 557 /* 558 * This is not really a fixup. The timer was 559 * statically initialized. We just make sure that it 560 * is tracked in the object tracker. 561 */ 562 debug_object_init(timer, &timer_debug_descr); 563 return 0; 564 } else { 565 setup_timer(timer, stub_timer, 0); 566 return 1; 567 } 568 default: 569 return 0; 570 } 571} 572 573static struct debug_obj_descr timer_debug_descr = { 574 .name = "timer_list", 575 .debug_hint = timer_debug_hint, 576 .fixup_init = timer_fixup_init, 577 .fixup_activate = timer_fixup_activate, 578 .fixup_free = timer_fixup_free, 579 .fixup_assert_init = timer_fixup_assert_init, 580}; 581 582static inline void debug_timer_init(struct timer_list *timer) 583{ 584 debug_object_init(timer, &timer_debug_descr); 585} 586 587static inline void debug_timer_activate(struct timer_list *timer) 588{ 589 debug_object_activate(timer, &timer_debug_descr); 590} 591 592static inline void debug_timer_deactivate(struct timer_list *timer) 593{ 594 debug_object_deactivate(timer, &timer_debug_descr); 595} 596 597static inline void debug_timer_free(struct timer_list *timer) 598{ 599 debug_object_free(timer, &timer_debug_descr); 600} 601 602static inline void debug_timer_assert_init(struct timer_list *timer) 603{ 604 debug_object_assert_init(timer, &timer_debug_descr); 605} 606 607static void do_init_timer(struct timer_list *timer, unsigned int flags, 608 const char *name, struct lock_class_key *key); 609 610void init_timer_on_stack_key(struct timer_list *timer, unsigned int flags, 611 const char *name, struct lock_class_key *key) 612{ 613 debug_object_init_on_stack(timer, &timer_debug_descr); 614 do_init_timer(timer, flags, name, key); 615} 616EXPORT_SYMBOL_GPL(init_timer_on_stack_key); 617 618void destroy_timer_on_stack(struct timer_list *timer) 619{ 620 debug_object_free(timer, &timer_debug_descr); 621} 622EXPORT_SYMBOL_GPL(destroy_timer_on_stack); 623 624#else 625static inline void debug_timer_init(struct timer_list *timer) { } 626static inline void debug_timer_activate(struct timer_list *timer) { } 627static inline void debug_timer_deactivate(struct timer_list *timer) { } 628static inline void debug_timer_assert_init(struct timer_list *timer) { } 629#endif 630 631static inline void debug_init(struct timer_list *timer) 632{ 633 debug_timer_init(timer); 634 trace_timer_init(timer); 635} 636 637static inline void 638debug_activate(struct timer_list *timer, unsigned long expires) 639{ 640 debug_timer_activate(timer); 641 trace_timer_start(timer, expires); 642} 643 644static inline void debug_deactivate(struct timer_list *timer) 645{ 646 debug_timer_deactivate(timer); 647 trace_timer_cancel(timer); 648} 649 650static inline void debug_assert_init(struct timer_list *timer) 651{ 652 debug_timer_assert_init(timer); 653} 654 655static void do_init_timer(struct timer_list *timer, unsigned int flags, 656 const char *name, struct lock_class_key *key) 657{ 658 struct tvec_base *base = raw_cpu_read(tvec_bases); 659 660 timer->entry.next = NULL; 661 timer->base = (void *)((unsigned long)base | flags); 662 timer->slack = -1; 663#ifdef CONFIG_TIMER_STATS 664 timer->start_site = NULL; 665 timer->start_pid = -1; 666 memset(timer->start_comm, 0, TASK_COMM_LEN); 667#endif 668 lockdep_init_map(&timer->lockdep_map, name, key, 0); 669} 670 671/** 672 * init_timer_key - initialize a timer 673 * @timer: the timer to be initialized 674 * @flags: timer flags 675 * @name: name of the timer 676 * @key: lockdep class key of the fake lock used for tracking timer 677 * sync lock dependencies 678 * 679 * init_timer_key() must be done to a timer prior calling *any* of the 680 * other timer functions. 681 */ 682void init_timer_key(struct timer_list *timer, unsigned int flags, 683 const char *name, struct lock_class_key *key) 684{ 685 debug_init(timer); 686 do_init_timer(timer, flags, name, key); 687} 688EXPORT_SYMBOL(init_timer_key); 689 690static inline void detach_timer(struct timer_list *timer, bool clear_pending) 691{ 692 struct list_head *entry = &timer->entry; 693 694 debug_deactivate(timer); 695 696 __list_del(entry->prev, entry->next); 697 if (clear_pending) 698 entry->next = NULL; 699 entry->prev = LIST_POISON2; 700} 701 702static inline void 703detach_expired_timer(struct timer_list *timer, struct tvec_base *base) 704{ 705 detach_timer(timer, true); 706 if (!tbase_get_deferrable(timer->base)) 707 base->active_timers--; 708 base->all_timers--; 709 (void)catchup_timer_jiffies(base); 710} 711 712static int detach_if_pending(struct timer_list *timer, struct tvec_base *base, 713 bool clear_pending) 714{ 715 if (!timer_pending(timer)) 716 return 0; 717 718 detach_timer(timer, clear_pending); 719 if (!tbase_get_deferrable(timer->base)) { 720 base->active_timers--; 721 if (timer->expires == base->next_timer) 722 base->next_timer = base->timer_jiffies; 723 } 724 base->all_timers--; 725 (void)catchup_timer_jiffies(base); 726 return 1; 727} 728 729/* 730 * We are using hashed locking: holding per_cpu(tvec_bases).lock 731 * means that all timers which are tied to this base via timer->base are 732 * locked, and the base itself is locked too. 733 * 734 * So __run_timers/migrate_timers can safely modify all timers which could 735 * be found on ->tvX lists. 736 * 737 * When the timer's base is locked, and the timer removed from list, it is 738 * possible to set timer->base = NULL and drop the lock: the timer remains 739 * locked. 740 */ 741static struct tvec_base *lock_timer_base(struct timer_list *timer, 742 unsigned long *flags) 743 __acquires(timer->base->lock) 744{ 745 struct tvec_base *base; 746 747 for (;;) { 748 struct tvec_base *prelock_base = timer->base; 749 base = tbase_get_base(prelock_base); 750 if (likely(base != NULL)) { 751 spin_lock_irqsave(&base->lock, *flags); 752 if (likely(prelock_base == timer->base)) 753 return base; 754 /* The timer has migrated to another CPU */ 755 spin_unlock_irqrestore(&base->lock, *flags); 756 } 757 cpu_relax(); 758 } 759} 760 761static inline int 762__mod_timer(struct timer_list *timer, unsigned long expires, 763 bool pending_only, int pinned) 764{ 765 struct tvec_base *base, *new_base; 766 unsigned long flags; 767 int ret = 0 , cpu; 768 769 timer_stats_timer_set_start_info(timer); 770 BUG_ON(!timer->function); 771 772 base = lock_timer_base(timer, &flags); 773 774 ret = detach_if_pending(timer, base, false); 775 if (!ret && pending_only) 776 goto out_unlock; 777 778 debug_activate(timer, expires); 779 780 cpu = get_nohz_timer_target(pinned); 781 new_base = per_cpu(tvec_bases, cpu); 782 783 if (base != new_base) { 784 /* 785 * We are trying to schedule the timer on the local CPU. 786 * However we can't change timer's base while it is running, 787 * otherwise del_timer_sync() can't detect that the timer's 788 * handler yet has not finished. This also guarantees that 789 * the timer is serialized wrt itself. 790 */ 791 if (likely(base->running_timer != timer)) { 792 /* See the comment in lock_timer_base() */ 793 timer_set_base(timer, NULL); 794 spin_unlock(&base->lock); 795 base = new_base; 796 spin_lock(&base->lock); 797 timer_set_base(timer, base); 798 } 799 } 800 801 timer->expires = expires; 802 internal_add_timer(base, timer); 803 804out_unlock: 805 spin_unlock_irqrestore(&base->lock, flags); 806 807 return ret; 808} 809 810/** 811 * mod_timer_pending - modify a pending timer's timeout 812 * @timer: the pending timer to be modified 813 * @expires: new timeout in jiffies 814 * 815 * mod_timer_pending() is the same for pending timers as mod_timer(), 816 * but will not re-activate and modify already deleted timers. 817 * 818 * It is useful for unserialized use of timers. 819 */ 820int mod_timer_pending(struct timer_list *timer, unsigned long expires) 821{ 822 return __mod_timer(timer, expires, true, TIMER_NOT_PINNED); 823} 824EXPORT_SYMBOL(mod_timer_pending); 825 826/* 827 * Decide where to put the timer while taking the slack into account 828 * 829 * Algorithm: 830 * 1) calculate the maximum (absolute) time 831 * 2) calculate the highest bit where the expires and new max are different 832 * 3) use this bit to make a mask 833 * 4) use the bitmask to round down the maximum time, so that all last 834 * bits are zeros 835 */ 836static inline 837unsigned long apply_slack(struct timer_list *timer, unsigned long expires) 838{ 839 unsigned long expires_limit, mask; 840 int bit; 841 842 if (timer->slack >= 0) { 843 expires_limit = expires + timer->slack; 844 } else { 845 long delta = expires - jiffies; 846 847 if (delta < 256) 848 return expires; 849 850 expires_limit = expires + delta / 256; 851 } 852 mask = expires ^ expires_limit; 853 if (mask == 0) 854 return expires; 855 856 bit = find_last_bit(&mask, BITS_PER_LONG); 857 858 mask = (1UL << bit) - 1; 859 860 expires_limit = expires_limit & ~(mask); 861 862 return expires_limit; 863} 864 865/** 866 * mod_timer - modify a timer's timeout 867 * @timer: the timer to be modified 868 * @expires: new timeout in jiffies 869 * 870 * mod_timer() is a more efficient way to update the expire field of an 871 * active timer (if the timer is inactive it will be activated) 872 * 873 * mod_timer(timer, expires) is equivalent to: 874 * 875 * del_timer(timer); timer->expires = expires; add_timer(timer); 876 * 877 * Note that if there are multiple unserialized concurrent users of the 878 * same timer, then mod_timer() is the only safe way to modify the timeout, 879 * since add_timer() cannot modify an already running timer. 880 * 881 * The function returns whether it has modified a pending timer or not. 882 * (ie. mod_timer() of an inactive timer returns 0, mod_timer() of an 883 * active timer returns 1.) 884 */ 885int mod_timer(struct timer_list *timer, unsigned long expires) 886{ 887 expires = apply_slack(timer, expires); 888 889 /* 890 * This is a common optimization triggered by the 891 * networking code - if the timer is re-modified 892 * to be the same thing then just return: 893 */ 894 if (timer_pending(timer) && timer->expires == expires) 895 return 1; 896 897 return __mod_timer(timer, expires, false, TIMER_NOT_PINNED); 898} 899EXPORT_SYMBOL(mod_timer); 900 901/** 902 * mod_timer_pinned - modify a timer's timeout 903 * @timer: the timer to be modified 904 * @expires: new timeout in jiffies 905 * 906 * mod_timer_pinned() is a way to update the expire field of an 907 * active timer (if the timer is inactive it will be activated) 908 * and to ensure that the timer is scheduled on the current CPU. 909 * 910 * Note that this does not prevent the timer from being migrated 911 * when the current CPU goes offline. If this is a problem for 912 * you, use CPU-hotplug notifiers to handle it correctly, for 913 * example, cancelling the timer when the corresponding CPU goes 914 * offline. 915 * 916 * mod_timer_pinned(timer, expires) is equivalent to: 917 * 918 * del_timer(timer); timer->expires = expires; add_timer(timer); 919 */ 920int mod_timer_pinned(struct timer_list *timer, unsigned long expires) 921{ 922 if (timer->expires == expires && timer_pending(timer)) 923 return 1; 924 925 return __mod_timer(timer, expires, false, TIMER_PINNED); 926} 927EXPORT_SYMBOL(mod_timer_pinned); 928 929/** 930 * add_timer - start a timer 931 * @timer: the timer to be added 932 * 933 * The kernel will do a ->function(->data) callback from the 934 * timer interrupt at the ->expires point in the future. The 935 * current time is 'jiffies'. 936 * 937 * The timer's ->expires, ->function (and if the handler uses it, ->data) 938 * fields must be set prior calling this function. 939 * 940 * Timers with an ->expires field in the past will be executed in the next 941 * timer tick. 942 */ 943void add_timer(struct timer_list *timer) 944{ 945 BUG_ON(timer_pending(timer)); 946 mod_timer(timer, timer->expires); 947} 948EXPORT_SYMBOL(add_timer); 949 950/** 951 * add_timer_on - start a timer on a particular CPU 952 * @timer: the timer to be added 953 * @cpu: the CPU to start it on 954 * 955 * This is not very scalable on SMP. Double adds are not possible. 956 */ 957void add_timer_on(struct timer_list *timer, int cpu) 958{ 959 struct tvec_base *base = per_cpu(tvec_bases, cpu); 960 unsigned long flags; 961 962 timer_stats_timer_set_start_info(timer); 963 BUG_ON(timer_pending(timer) || !timer->function); 964 spin_lock_irqsave(&base->lock, flags); 965 timer_set_base(timer, base); 966 debug_activate(timer, timer->expires); 967 internal_add_timer(base, timer); 968 spin_unlock_irqrestore(&base->lock, flags); 969} 970EXPORT_SYMBOL_GPL(add_timer_on); 971 972/** 973 * del_timer - deactive a timer. 974 * @timer: the timer to be deactivated 975 * 976 * del_timer() deactivates a timer - this works on both active and inactive 977 * timers. 978 * 979 * The function returns whether it has deactivated a pending timer or not. 980 * (ie. del_timer() of an inactive timer returns 0, del_timer() of an 981 * active timer returns 1.) 982 */ 983int del_timer(struct timer_list *timer) 984{ 985 struct tvec_base *base; 986 unsigned long flags; 987 int ret = 0; 988 989 debug_assert_init(timer); 990 991 timer_stats_timer_clear_start_info(timer); 992 if (timer_pending(timer)) { 993 base = lock_timer_base(timer, &flags); 994 ret = detach_if_pending(timer, base, true); 995 spin_unlock_irqrestore(&base->lock, flags); 996 } 997 998 return ret; 999} 1000EXPORT_SYMBOL(del_timer); 1001 1002/** 1003 * try_to_del_timer_sync - Try to deactivate a timer 1004 * @timer: timer do del 1005 * 1006 * This function tries to deactivate a timer. Upon successful (ret >= 0) 1007 * exit the timer is not queued and the handler is not running on any CPU. 1008 */ 1009int try_to_del_timer_sync(struct timer_list *timer) 1010{ 1011 struct tvec_base *base; 1012 unsigned long flags; 1013 int ret = -1; 1014 1015 debug_assert_init(timer); 1016 1017 base = lock_timer_base(timer, &flags); 1018 1019 if (base->running_timer != timer) { 1020 timer_stats_timer_clear_start_info(timer); 1021 ret = detach_if_pending(timer, base, true); 1022 } 1023 spin_unlock_irqrestore(&base->lock, flags); 1024 1025 return ret; 1026} 1027EXPORT_SYMBOL(try_to_del_timer_sync); 1028 1029#ifdef CONFIG_SMP 1030/** 1031 * del_timer_sync - deactivate a timer and wait for the handler to finish. 1032 * @timer: the timer to be deactivated 1033 * 1034 * This function only differs from del_timer() on SMP: besides deactivating 1035 * the timer it also makes sure the handler has finished executing on other 1036 * CPUs. 1037 * 1038 * Synchronization rules: Callers must prevent restarting of the timer, 1039 * otherwise this function is meaningless. It must not be called from 1040 * interrupt contexts unless the timer is an irqsafe one. The caller must 1041 * not hold locks which would prevent completion of the timer's 1042 * handler. The timer's handler must not call add_timer_on(). Upon exit the 1043 * timer is not queued and the handler is not running on any CPU. 1044 * 1045 * Note: For !irqsafe timers, you must not hold locks that are held in 1046 * interrupt context while calling this function. Even if the lock has 1047 * nothing to do with the timer in question. Here's why: 1048 * 1049 * CPU0 CPU1 1050 * ---- ---- 1051 * <SOFTIRQ> 1052 * call_timer_fn(); 1053 * base->running_timer = mytimer; 1054 * spin_lock_irq(somelock); 1055 * <IRQ> 1056 * spin_lock(somelock); 1057 * del_timer_sync(mytimer); 1058 * while (base->running_timer == mytimer); 1059 * 1060 * Now del_timer_sync() will never return and never release somelock. 1061 * The interrupt on the other CPU is waiting to grab somelock but 1062 * it has interrupted the softirq that CPU0 is waiting to finish. 1063 * 1064 * The function returns whether it has deactivated a pending timer or not. 1065 */ 1066int del_timer_sync(struct timer_list *timer) 1067{ 1068#ifdef CONFIG_LOCKDEP 1069 unsigned long flags; 1070 1071 /* 1072 * If lockdep gives a backtrace here, please reference 1073 * the synchronization rules above. 1074 */ 1075 local_irq_save(flags); 1076 lock_map_acquire(&timer->lockdep_map); 1077 lock_map_release(&timer->lockdep_map); 1078 local_irq_restore(flags); 1079#endif 1080 /* 1081 * don't use it in hardirq context, because it 1082 * could lead to deadlock. 1083 */ 1084 WARN_ON(in_irq() && !tbase_get_irqsafe(timer->base)); 1085 for (;;) { 1086 int ret = try_to_del_timer_sync(timer); 1087 if (ret >= 0) 1088 return ret; 1089 cpu_relax(); 1090 } 1091} 1092EXPORT_SYMBOL(del_timer_sync); 1093#endif 1094 1095static int cascade(struct tvec_base *base, struct tvec *tv, int index) 1096{ 1097 /* cascade all the timers from tv up one level */ 1098 struct timer_list *timer, *tmp; 1099 struct list_head tv_list; 1100 1101 list_replace_init(tv->vec + index, &tv_list); 1102 1103 /* 1104 * We are removing _all_ timers from the list, so we 1105 * don't have to detach them individually. 1106 */ 1107 list_for_each_entry_safe(timer, tmp, &tv_list, entry) { 1108 BUG_ON(tbase_get_base(timer->base) != base); 1109 /* No accounting, while moving them */ 1110 __internal_add_timer(base, timer); 1111 } 1112 1113 return index; 1114} 1115 1116static void call_timer_fn(struct timer_list *timer, void (*fn)(unsigned long), 1117 unsigned long data) 1118{ 1119 int count = preempt_count(); 1120 1121#ifdef CONFIG_LOCKDEP 1122 /* 1123 * It is permissible to free the timer from inside the 1124 * function that is called from it, this we need to take into 1125 * account for lockdep too. To avoid bogus "held lock freed" 1126 * warnings as well as problems when looking into 1127 * timer->lockdep_map, make a copy and use that here. 1128 */ 1129 struct lockdep_map lockdep_map; 1130 1131 lockdep_copy_map(&lockdep_map, &timer->lockdep_map); 1132#endif 1133 /* 1134 * Couple the lock chain with the lock chain at 1135 * del_timer_sync() by acquiring the lock_map around the fn() 1136 * call here and in del_timer_sync(). 1137 */ 1138 lock_map_acquire(&lockdep_map); 1139 1140 trace_timer_expire_entry(timer); 1141 fn(data); 1142 trace_timer_expire_exit(timer); 1143 1144 lock_map_release(&lockdep_map); 1145 1146 if (count != preempt_count()) { 1147 WARN_ONCE(1, "timer: %pF preempt leak: %08x -> %08x\n", 1148 fn, count, preempt_count()); 1149 /* 1150 * Restore the preempt count. That gives us a decent 1151 * chance to survive and extract information. If the 1152 * callback kept a lock held, bad luck, but not worse 1153 * than the BUG() we had. 1154 */ 1155 preempt_count_set(count); 1156 } 1157} 1158 1159#define INDEX(N) ((base->timer_jiffies >> (TVR_BITS + (N) * TVN_BITS)) & TVN_MASK) 1160 1161/** 1162 * __run_timers - run all expired timers (if any) on this CPU. 1163 * @base: the timer vector to be processed. 1164 * 1165 * This function cascades all vectors and executes all expired timer 1166 * vectors. 1167 */ 1168static inline void __run_timers(struct tvec_base *base) 1169{ 1170 struct timer_list *timer; 1171 1172 spin_lock_irq(&base->lock); 1173 if (catchup_timer_jiffies(base)) { 1174 spin_unlock_irq(&base->lock); 1175 return; 1176 } 1177 while (time_after_eq(jiffies, base->timer_jiffies)) { 1178 struct list_head work_list; 1179 struct list_head *head = &work_list; 1180 int index = base->timer_jiffies & TVR_MASK; 1181 1182 /* 1183 * Cascade timers: 1184 */ 1185 if (!index && 1186 (!cascade(base, &base->tv2, INDEX(0))) && 1187 (!cascade(base, &base->tv3, INDEX(1))) && 1188 !cascade(base, &base->tv4, INDEX(2))) 1189 cascade(base, &base->tv5, INDEX(3)); 1190 ++base->timer_jiffies; 1191 list_replace_init(base->tv1.vec + index, head); 1192 while (!list_empty(head)) { 1193 void (*fn)(unsigned long); 1194 unsigned long data; 1195 bool irqsafe; 1196 1197 timer = list_first_entry(head, struct timer_list,entry); 1198 fn = timer->function; 1199 data = timer->data; 1200 irqsafe = tbase_get_irqsafe(timer->base); 1201 1202 timer_stats_account_timer(timer); 1203 1204 base->running_timer = timer; 1205 detach_expired_timer(timer, base); 1206 1207 if (irqsafe) { 1208 spin_unlock(&base->lock); 1209 call_timer_fn(timer, fn, data); 1210 spin_lock(&base->lock); 1211 } else { 1212 spin_unlock_irq(&base->lock); 1213 call_timer_fn(timer, fn, data); 1214 spin_lock_irq(&base->lock); 1215 } 1216 } 1217 } 1218 base->running_timer = NULL; 1219 spin_unlock_irq(&base->lock); 1220} 1221 1222#ifdef CONFIG_NO_HZ_COMMON 1223/* 1224 * Find out when the next timer event is due to happen. This 1225 * is used on S/390 to stop all activity when a CPU is idle. 1226 * This function needs to be called with interrupts disabled. 1227 */ 1228static unsigned long __next_timer_interrupt(struct tvec_base *base) 1229{ 1230 unsigned long timer_jiffies = base->timer_jiffies; 1231 unsigned long expires = timer_jiffies + NEXT_TIMER_MAX_DELTA; 1232 int index, slot, array, found = 0; 1233 struct timer_list *nte; 1234 struct tvec *varray[4]; 1235 1236 /* Look for timer events in tv1. */ 1237 index = slot = timer_jiffies & TVR_MASK; 1238 do { 1239 list_for_each_entry(nte, base->tv1.vec + slot, entry) { 1240 if (tbase_get_deferrable(nte->base)) 1241 continue; 1242 1243 found = 1; 1244 expires = nte->expires; 1245 /* Look at the cascade bucket(s)? */ 1246 if (!index || slot < index) 1247 goto cascade; 1248 return expires; 1249 } 1250 slot = (slot + 1) & TVR_MASK; 1251 } while (slot != index); 1252 1253cascade: 1254 /* Calculate the next cascade event */ 1255 if (index) 1256 timer_jiffies += TVR_SIZE - index; 1257 timer_jiffies >>= TVR_BITS; 1258 1259 /* Check tv2-tv5. */ 1260 varray[0] = &base->tv2; 1261 varray[1] = &base->tv3; 1262 varray[2] = &base->tv4; 1263 varray[3] = &base->tv5; 1264 1265 for (array = 0; array < 4; array++) { 1266 struct tvec *varp = varray[array]; 1267 1268 index = slot = timer_jiffies & TVN_MASK; 1269 do { 1270 list_for_each_entry(nte, varp->vec + slot, entry) { 1271 if (tbase_get_deferrable(nte->base)) 1272 continue; 1273 1274 found = 1; 1275 if (time_before(nte->expires, expires)) 1276 expires = nte->expires; 1277 } 1278 /* 1279 * Do we still search for the first timer or are 1280 * we looking up the cascade buckets ? 1281 */ 1282 if (found) { 1283 /* Look at the cascade bucket(s)? */ 1284 if (!index || slot < index) 1285 break; 1286 return expires; 1287 } 1288 slot = (slot + 1) & TVN_MASK; 1289 } while (slot != index); 1290 1291 if (index) 1292 timer_jiffies += TVN_SIZE - index; 1293 timer_jiffies >>= TVN_BITS; 1294 } 1295 return expires; 1296} 1297 1298/* 1299 * Check, if the next hrtimer event is before the next timer wheel 1300 * event: 1301 */ 1302static unsigned long cmp_next_hrtimer_event(unsigned long now, 1303 unsigned long expires) 1304{ 1305 ktime_t hr_delta = hrtimer_get_next_event(); 1306 struct timespec tsdelta; 1307 unsigned long delta; 1308 1309 if (hr_delta.tv64 == KTIME_MAX) 1310 return expires; 1311 1312 /* 1313 * Expired timer available, let it expire in the next tick 1314 */ 1315 if (hr_delta.tv64 <= 0) 1316 return now + 1; 1317 1318 tsdelta = ktime_to_timespec(hr_delta); 1319 delta = timespec_to_jiffies(&tsdelta); 1320 1321 /* 1322 * Limit the delta to the max value, which is checked in 1323 * tick_nohz_stop_sched_tick(): 1324 */ 1325 if (delta > NEXT_TIMER_MAX_DELTA) 1326 delta = NEXT_TIMER_MAX_DELTA; 1327 1328 /* 1329 * Take rounding errors in to account and make sure, that it 1330 * expires in the next tick. Otherwise we go into an endless 1331 * ping pong due to tick_nohz_stop_sched_tick() retriggering 1332 * the timer softirq 1333 */ 1334 if (delta < 1) 1335 delta = 1; 1336 now += delta; 1337 if (time_before(now, expires)) 1338 return now; 1339 return expires; 1340} 1341 1342/** 1343 * get_next_timer_interrupt - return the jiffy of the next pending timer 1344 * @now: current time (in jiffies) 1345 */ 1346unsigned long get_next_timer_interrupt(unsigned long now) 1347{ 1348 struct tvec_base *base = __this_cpu_read(tvec_bases); 1349 unsigned long expires = now + NEXT_TIMER_MAX_DELTA; 1350 1351 /* 1352 * Pretend that there is no timer pending if the cpu is offline. 1353 * Possible pending timers will be migrated later to an active cpu. 1354 */ 1355 if (cpu_is_offline(smp_processor_id())) 1356 return expires; 1357 1358 spin_lock(&base->lock); 1359 if (base->active_timers) { 1360 if (time_before_eq(base->next_timer, base->timer_jiffies)) 1361 base->next_timer = __next_timer_interrupt(base); 1362 expires = base->next_timer; 1363 } 1364 spin_unlock(&base->lock); 1365 1366 if (time_before_eq(expires, now)) 1367 return now; 1368 1369 return cmp_next_hrtimer_event(now, expires); 1370} 1371#endif 1372 1373/* 1374 * Called from the timer interrupt handler to charge one tick to the current 1375 * process. user_tick is 1 if the tick is user time, 0 for system. 1376 */ 1377void update_process_times(int user_tick) 1378{ 1379 struct task_struct *p = current; 1380 int cpu = smp_processor_id(); 1381 1382 /* Note: this timer irq context must be accounted for as well. */ 1383 account_process_tick(p, user_tick); 1384 run_local_timers(); 1385 rcu_check_callbacks(cpu, user_tick); 1386#ifdef CONFIG_IRQ_WORK 1387 if (in_irq()) 1388 irq_work_tick(); 1389#endif 1390 scheduler_tick(); 1391 run_posix_cpu_timers(p); 1392} 1393 1394/* 1395 * This function runs timers and the timer-tq in bottom half context. 1396 */ 1397static void run_timer_softirq(struct softirq_action *h) 1398{ 1399 struct tvec_base *base = __this_cpu_read(tvec_bases); 1400 1401 hrtimer_run_pending(); 1402 1403 if (time_after_eq(jiffies, base->timer_jiffies)) 1404 __run_timers(base); 1405} 1406 1407/* 1408 * Called by the local, per-CPU timer interrupt on SMP. 1409 */ 1410void run_local_timers(void) 1411{ 1412 hrtimer_run_queues(); 1413 raise_softirq(TIMER_SOFTIRQ); 1414} 1415 1416#ifdef __ARCH_WANT_SYS_ALARM 1417 1418/* 1419 * For backwards compatibility? This can be done in libc so Alpha 1420 * and all newer ports shouldn't need it. 1421 */ 1422SYSCALL_DEFINE1(alarm, unsigned int, seconds) 1423{ 1424 return alarm_setitimer(seconds); 1425} 1426 1427#endif 1428 1429static void process_timeout(unsigned long __data) 1430{ 1431 wake_up_process((struct task_struct *)__data); 1432} 1433 1434/** 1435 * schedule_timeout - sleep until timeout 1436 * @timeout: timeout value in jiffies 1437 * 1438 * Make the current task sleep until @timeout jiffies have 1439 * elapsed. The routine will return immediately unless 1440 * the current task state has been set (see set_current_state()). 1441 * 1442 * You can set the task state as follows - 1443 * 1444 * %TASK_UNINTERRUPTIBLE - at least @timeout jiffies are guaranteed to 1445 * pass before the routine returns. The routine will return 0 1446 * 1447 * %TASK_INTERRUPTIBLE - the routine may return early if a signal is 1448 * delivered to the current task. In this case the remaining time 1449 * in jiffies will be returned, or 0 if the timer expired in time 1450 * 1451 * The current task state is guaranteed to be TASK_RUNNING when this 1452 * routine returns. 1453 * 1454 * Specifying a @timeout value of %MAX_SCHEDULE_TIMEOUT will schedule 1455 * the CPU away without a bound on the timeout. In this case the return 1456 * value will be %MAX_SCHEDULE_TIMEOUT. 1457 * 1458 * In all cases the return value is guaranteed to be non-negative. 1459 */ 1460signed long __sched schedule_timeout(signed long timeout) 1461{ 1462 struct timer_list timer; 1463 unsigned long expire; 1464 1465 switch (timeout) 1466 { 1467 case MAX_SCHEDULE_TIMEOUT: 1468 /* 1469 * These two special cases are useful to be comfortable 1470 * in the caller. Nothing more. We could take 1471 * MAX_SCHEDULE_TIMEOUT from one of the negative value 1472 * but I' d like to return a valid offset (>=0) to allow 1473 * the caller to do everything it want with the retval. 1474 */ 1475 schedule(); 1476 goto out; 1477 default: 1478 /* 1479 * Another bit of PARANOID. Note that the retval will be 1480 * 0 since no piece of kernel is supposed to do a check 1481 * for a negative retval of schedule_timeout() (since it 1482 * should never happens anyway). You just have the printk() 1483 * that will tell you if something is gone wrong and where. 1484 */ 1485 if (timeout < 0) { 1486 printk(KERN_ERR "schedule_timeout: wrong timeout " 1487 "value %lx\n", timeout); 1488 dump_stack(); 1489 current->state = TASK_RUNNING; 1490 goto out; 1491 } 1492 } 1493 1494 expire = timeout + jiffies; 1495 1496 setup_timer_on_stack(&timer, process_timeout, (unsigned long)current); 1497 __mod_timer(&timer, expire, false, TIMER_NOT_PINNED); 1498 schedule(); 1499 del_singleshot_timer_sync(&timer); 1500 1501 /* Remove the timer from the object tracker */ 1502 destroy_timer_on_stack(&timer); 1503 1504 timeout = expire - jiffies; 1505 1506 out: 1507 return timeout < 0 ? 0 : timeout; 1508} 1509EXPORT_SYMBOL(schedule_timeout); 1510 1511/* 1512 * We can use __set_current_state() here because schedule_timeout() calls 1513 * schedule() unconditionally. 1514 */ 1515signed long __sched schedule_timeout_interruptible(signed long timeout) 1516{ 1517 __set_current_state(TASK_INTERRUPTIBLE); 1518 return schedule_timeout(timeout); 1519} 1520EXPORT_SYMBOL(schedule_timeout_interruptible); 1521 1522signed long __sched schedule_timeout_killable(signed long timeout) 1523{ 1524 __set_current_state(TASK_KILLABLE); 1525 return schedule_timeout(timeout); 1526} 1527EXPORT_SYMBOL(schedule_timeout_killable); 1528 1529signed long __sched schedule_timeout_uninterruptible(signed long timeout) 1530{ 1531 __set_current_state(TASK_UNINTERRUPTIBLE); 1532 return schedule_timeout(timeout); 1533} 1534EXPORT_SYMBOL(schedule_timeout_uninterruptible); 1535 1536static int init_timers_cpu(int cpu) 1537{ 1538 int j; 1539 struct tvec_base *base; 1540 static char tvec_base_done[NR_CPUS]; 1541 1542 if (!tvec_base_done[cpu]) { 1543 static char boot_done; 1544 1545 if (boot_done) { 1546 /* 1547 * The APs use this path later in boot 1548 */ 1549 base = kzalloc_node(sizeof(*base), GFP_KERNEL, 1550 cpu_to_node(cpu)); 1551 if (!base) 1552 return -ENOMEM; 1553 1554 /* Make sure tvec_base has TIMER_FLAG_MASK bits free */ 1555 if (WARN_ON(base != tbase_get_base(base))) { 1556 kfree(base); 1557 return -ENOMEM; 1558 } 1559 per_cpu(tvec_bases, cpu) = base; 1560 } else { 1561 /* 1562 * This is for the boot CPU - we use compile-time 1563 * static initialisation because per-cpu memory isn't 1564 * ready yet and because the memory allocators are not 1565 * initialised either. 1566 */ 1567 boot_done = 1; 1568 base = &boot_tvec_bases; 1569 } 1570 spin_lock_init(&base->lock); 1571 tvec_base_done[cpu] = 1; 1572 base->cpu = cpu; 1573 } else { 1574 base = per_cpu(tvec_bases, cpu); 1575 } 1576 1577 1578 for (j = 0; j < TVN_SIZE; j++) { 1579 INIT_LIST_HEAD(base->tv5.vec + j); 1580 INIT_LIST_HEAD(base->tv4.vec + j); 1581 INIT_LIST_HEAD(base->tv3.vec + j); 1582 INIT_LIST_HEAD(base->tv2.vec + j); 1583 } 1584 for (j = 0; j < TVR_SIZE; j++) 1585 INIT_LIST_HEAD(base->tv1.vec + j); 1586 1587 base->timer_jiffies = jiffies; 1588 base->next_timer = base->timer_jiffies; 1589 base->active_timers = 0; 1590 base->all_timers = 0; 1591 return 0; 1592} 1593 1594#ifdef CONFIG_HOTPLUG_CPU 1595static void migrate_timer_list(struct tvec_base *new_base, struct list_head *head) 1596{ 1597 struct timer_list *timer; 1598 1599 while (!list_empty(head)) { 1600 timer = list_first_entry(head, struct timer_list, entry); 1601 /* We ignore the accounting on the dying cpu */ 1602 detach_timer(timer, false); 1603 timer_set_base(timer, new_base); 1604 internal_add_timer(new_base, timer); 1605 } 1606} 1607 1608static void migrate_timers(int cpu) 1609{ 1610 struct tvec_base *old_base; 1611 struct tvec_base *new_base; 1612 int i; 1613 1614 BUG_ON(cpu_online(cpu)); 1615 old_base = per_cpu(tvec_bases, cpu); 1616 new_base = get_cpu_var(tvec_bases); 1617 /* 1618 * The caller is globally serialized and nobody else 1619 * takes two locks at once, deadlock is not possible. 1620 */ 1621 spin_lock_irq(&new_base->lock); 1622 spin_lock_nested(&old_base->lock, SINGLE_DEPTH_NESTING); 1623 1624 BUG_ON(old_base->running_timer); 1625 1626 for (i = 0; i < TVR_SIZE; i++) 1627 migrate_timer_list(new_base, old_base->tv1.vec + i); 1628 for (i = 0; i < TVN_SIZE; i++) { 1629 migrate_timer_list(new_base, old_base->tv2.vec + i); 1630 migrate_timer_list(new_base, old_base->tv3.vec + i); 1631 migrate_timer_list(new_base, old_base->tv4.vec + i); 1632 migrate_timer_list(new_base, old_base->tv5.vec + i); 1633 } 1634 1635 spin_unlock(&old_base->lock); 1636 spin_unlock_irq(&new_base->lock); 1637 put_cpu_var(tvec_bases); 1638} 1639#endif /* CONFIG_HOTPLUG_CPU */ 1640 1641static int timer_cpu_notify(struct notifier_block *self, 1642 unsigned long action, void *hcpu) 1643{ 1644 long cpu = (long)hcpu; 1645 int err; 1646 1647 switch(action) { 1648 case CPU_UP_PREPARE: 1649 case CPU_UP_PREPARE_FROZEN: 1650 err = init_timers_cpu(cpu); 1651 if (err < 0) 1652 return notifier_from_errno(err); 1653 break; 1654#ifdef CONFIG_HOTPLUG_CPU 1655 case CPU_DEAD: 1656 case CPU_DEAD_FROZEN: 1657 migrate_timers(cpu); 1658 break; 1659#endif 1660 default: 1661 break; 1662 } 1663 return NOTIFY_OK; 1664} 1665 1666static struct notifier_block timers_nb = { 1667 .notifier_call = timer_cpu_notify, 1668}; 1669 1670 1671void __init init_timers(void) 1672{ 1673 int err; 1674 1675 /* ensure there are enough low bits for flags in timer->base pointer */ 1676 BUILD_BUG_ON(__alignof__(struct tvec_base) & TIMER_FLAG_MASK); 1677 1678 err = timer_cpu_notify(&timers_nb, (unsigned long)CPU_UP_PREPARE, 1679 (void *)(long)smp_processor_id()); 1680 BUG_ON(err != NOTIFY_OK); 1681 1682 init_timer_stats(); 1683 register_cpu_notifier(&timers_nb); 1684 open_softirq(TIMER_SOFTIRQ, run_timer_softirq); 1685} 1686 1687/** 1688 * msleep - sleep safely even with waitqueue interruptions 1689 * @msecs: Time in milliseconds to sleep for 1690 */ 1691void msleep(unsigned int msecs) 1692{ 1693 unsigned long timeout = msecs_to_jiffies(msecs) + 1; 1694 1695 while (timeout) 1696 timeout = schedule_timeout_uninterruptible(timeout); 1697} 1698 1699EXPORT_SYMBOL(msleep); 1700 1701/** 1702 * msleep_interruptible - sleep waiting for signals 1703 * @msecs: Time in milliseconds to sleep for 1704 */ 1705unsigned long msleep_interruptible(unsigned int msecs) 1706{ 1707 unsigned long timeout = msecs_to_jiffies(msecs) + 1; 1708 1709 while (timeout && !signal_pending(current)) 1710 timeout = schedule_timeout_interruptible(timeout); 1711 return jiffies_to_msecs(timeout); 1712} 1713 1714EXPORT_SYMBOL(msleep_interruptible); 1715 1716static int __sched do_usleep_range(unsigned long min, unsigned long max) 1717{ 1718 ktime_t kmin; 1719 unsigned long delta; 1720 1721 kmin = ktime_set(0, min * NSEC_PER_USEC); 1722 delta = (max - min) * NSEC_PER_USEC; 1723 return schedule_hrtimeout_range(&kmin, delta, HRTIMER_MODE_REL); 1724} 1725 1726/** 1727 * usleep_range - Drop in replacement for udelay where wakeup is flexible 1728 * @min: Minimum time in usecs to sleep 1729 * @max: Maximum time in usecs to sleep 1730 */ 1731void usleep_range(unsigned long min, unsigned long max) 1732{ 1733 __set_current_state(TASK_UNINTERRUPTIBLE); 1734 do_usleep_range(min, max); 1735} 1736EXPORT_SYMBOL(usleep_range); 1737