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