sched.c 23 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978
  1. /* CFS-lite scheduler core: per-CPU state, a weighted run queue, a sorted sleep
  2. * list and the timer entry.
  3. *
  4. * Weight is an integer 1..SCHED_WEIGHT_MAX. Each ready process has a 64-bit
  5. * virtual runtime advanced by (elapsed ticks * stride) while it runs, where
  6. * stride = SCHED_WEIGHT_SCALE / weight. The smallest vruntime gets the CPU,
  7. * so the long-term share is proportional to the weight. A 10 ms slice bounds
  8. * latency; a wake-up gets clamped to the current minimum vruntime so an
  9. * interactive process is scheduled promptly without accumulating unbounded
  10. * credit.
  11. *
  12. * The run queue is a single global list protected by sched_lock; per-CPU
  13. * current lets every CPU pick the next eligible task from it.
  14. */
  15. #include "sched.h"
  16. #include "io.h"
  17. #include "lapic.h"
  18. #include "paging.h"
  19. #include "process.h"
  20. #include "smp.h"
  21. #include "spinlock.h"
  22. #include "syscall.h"
  23. #include "power.h"
  24. #include "thermal.h"
  25. #include "timer.h"
  26. #include "tss.h"
  27. /* 2^20 / weight, so weight 8 advances 131072 per tick and weight 16 half
  28. * that. The product fits comfortably in the 64-bit vruntime. */
  29. #define SCHED_WEIGHT_SCALE (1u << 20)
  30. struct cpu cpus[MAX_CPUS];
  31. unsigned int cpu_count;
  32. unsigned int cpu_gs_ready;
  33. static struct process *runq_head, *runq_tail;
  34. static struct process *sleep_head, *sleep_tail;
  35. static unsigned int wakeups;
  36. /* Protects the global run/sleep/wait queues and the process-table state that
  37. * the timer path touches. This is a spinlock: it is held with interrupts
  38. * off for short, non-blocking critical sections only. */
  39. static spinlock_t sched_lock;
  40. /* Sleeping big kernel lock. One owner process at a time (recursive); the
  41. * owner is never timer-preempted, and every voluntary block drops it so the
  42. * other CPU can keep making progress. See bkl_lock()/bkl_unlock(). */
  43. static struct {
  44. struct process *owner;
  45. unsigned int depth;
  46. struct wait_queue wait;
  47. unsigned int since; /* get_ticks_ms() when the owner took it */
  48. } bkl;
  49. /* BKL contention, for `sched`: how often a taker had to sleep, the total
  50. * wait, and the longest single hold with its holder (reset when printed).
  51. * Every syscall takes the lock, so a long holder stalls ring-3 work on the
  52. * other CPUs. */
  53. static struct {
  54. unsigned int contended, wait_ms, hold_max_ms;
  55. char hold_max_name[PROC_NAME_LEN];
  56. } bkl_stat;
  57. static void bkl_note_release(struct process *p)
  58. {
  59. unsigned int held = get_ticks_ms() - bkl.since;
  60. unsigned int i;
  61. if (held <= bkl_stat.hold_max_ms)
  62. return;
  63. bkl_stat.hold_max_ms = held;
  64. for (i = 0; i + 1 < PROC_NAME_LEN && p->name[i]; i++)
  65. bkl_stat.hold_max_name[i] = p->name[i];
  66. bkl_stat.hold_max_name[i] = '\0';
  67. }
  68. unsigned int sched_lock_acquire(void)
  69. {
  70. unsigned int flags = spin_irq_save_disable();
  71. spin_lock(&sched_lock);
  72. return flags;
  73. }
  74. void sched_lock_release(unsigned int flags)
  75. {
  76. spin_unlock(&sched_lock);
  77. spin_irq_restore(flags);
  78. }
  79. void sched_lock_reset(void)
  80. {
  81. sched_lock.locked = 0;
  82. }
  83. /* switch.S reads these two facts directly: current at %gs:0 and esp at
  84. * offset 0 of the process. Keep them true. */
  85. _Static_assert(__builtin_offsetof(struct cpu, current) == 0,
  86. "switch.S reads current from %gs:0");
  87. _Static_assert(__builtin_offsetof(struct process, esp) == 0,
  88. "switch.S saves the interrupted esp at offset 0");
  89. _Static_assert(__builtin_offsetof(struct cpu, need_resched) == 24,
  90. "smp_resched_wake expects need_resched at offset 24");
  91. static inline unsigned long long weight_stride(unsigned int weight)
  92. {
  93. if (weight < 1)
  94. weight = 1;
  95. if (weight > SCHED_WEIGHT_MAX)
  96. weight = SCHED_WEIGHT_MAX;
  97. return (unsigned long long)(SCHED_WEIGHT_SCALE / weight);
  98. }
  99. /* ---- run queue (interrupts off) ---- */
  100. static void runq_add_locked(struct process *p)
  101. {
  102. if (p->on_runq)
  103. return;
  104. p->on_runq = 1;
  105. p->run_prev = runq_tail;
  106. p->run_next = 0;
  107. if (runq_tail)
  108. runq_tail->run_next = p;
  109. else
  110. runq_head = p;
  111. runq_tail = p;
  112. }
  113. static void runq_del_locked(struct process *p)
  114. {
  115. if (!p->on_runq)
  116. return;
  117. if (p->run_prev)
  118. p->run_prev->run_next = p->run_next;
  119. else
  120. runq_head = p->run_next;
  121. if (p->run_next)
  122. p->run_next->run_prev = p->run_prev;
  123. else
  124. runq_tail = p->run_prev;
  125. p->on_runq = 0;
  126. p->run_next = p->run_prev = 0;
  127. }
  128. static void sleepq_add_locked(struct process *p)
  129. {
  130. struct process *it = sleep_head, *prev = 0;
  131. while (it && (int)(it->wake_ms - p->wake_ms) <= 0) {
  132. prev = it;
  133. it = it->sleep_next;
  134. }
  135. p->sleep_prev = prev;
  136. p->sleep_next = it;
  137. if (prev)
  138. prev->sleep_next = p;
  139. else
  140. sleep_head = p;
  141. if (it)
  142. it->sleep_prev = p;
  143. else
  144. sleep_tail = p;
  145. }
  146. static void sleepq_del_locked(struct process *p)
  147. {
  148. if (p->sleep_prev)
  149. p->sleep_prev->sleep_next = p->sleep_next;
  150. else if (sleep_head == p)
  151. sleep_head = p->sleep_next;
  152. if (p->sleep_next)
  153. p->sleep_next->sleep_prev = p->sleep_prev;
  154. else if (sleep_tail == p)
  155. sleep_tail = p->sleep_prev;
  156. p->sleep_next = p->sleep_prev = 0;
  157. }
  158. void wait_queue_init(struct wait_queue *wq)
  159. {
  160. wq->head = wq->tail = 0;
  161. }
  162. static void waitq_add_locked(struct wait_queue *wq, struct process *p)
  163. {
  164. p->waiting_on = wq;
  165. p->wait_next = 0;
  166. p->wait_prev = wq->tail;
  167. if (wq->tail)
  168. wq->tail->wait_next = p;
  169. else
  170. wq->head = p;
  171. wq->tail = p;
  172. }
  173. static void waitq_del_locked(struct process *p)
  174. {
  175. struct wait_queue *wq = p->waiting_on;
  176. if (!wq)
  177. return;
  178. if (p->wait_prev)
  179. p->wait_prev->wait_next = p->wait_next;
  180. else
  181. wq->head = p->wait_next;
  182. if (p->wait_next)
  183. p->wait_next->wait_prev = p->wait_prev;
  184. else
  185. wq->tail = p->wait_prev;
  186. p->wait_next = p->wait_prev = 0;
  187. p->waiting_on = 0;
  188. }
  189. /* Current minimum vruntime among READY processes. If nothing is ready, use
  190. * the running process's vruntime so a freshly woken process does not receive
  191. * an enormous credit relative to a CPU-bound one. */
  192. static unsigned long long min_vruntime_locked(void)
  193. {
  194. struct process *p;
  195. unsigned long long min = 0;
  196. int found = 0;
  197. for (p = runq_head; p; p = p->run_next) {
  198. if (!found || p->vruntime < min) {
  199. min = p->vruntime;
  200. found = 1;
  201. }
  202. }
  203. if (found)
  204. return min;
  205. p = current_proc();
  206. return (p && p != this_cpu()->idle) ? p->vruntime : 0;
  207. }
  208. static void account_locked(struct process *p)
  209. {
  210. unsigned int elapsed;
  211. if (!p || p == this_cpu()->idle || p->state != PROC_RUNNING)
  212. return;
  213. elapsed = get_ticks_ms() - p->slice_start;
  214. if (elapsed) {
  215. p->vruntime += (unsigned long long)elapsed * p->stride;
  216. p->slice_start = get_ticks_ms();
  217. }
  218. }
  219. /* Clamp a woken process to the current minimum and make it runnable. */
  220. static void wake_locked(struct process *p)
  221. {
  222. struct process *cur = current_proc();
  223. struct cpu *c = this_cpu();
  224. if (!p || p->state == PROC_DEAD || p->state == PROC_UNUSED)
  225. return;
  226. if (p->waiting_on)
  227. waitq_del_locked(p);
  228. if (p->state == PROC_SLEEPING)
  229. sleepq_del_locked(p);
  230. p->state = PROC_READY;
  231. if (p->vruntime < min_vruntime_locked())
  232. p->vruntime = min_vruntime_locked();
  233. runq_add_locked(p);
  234. wakeups++;
  235. if (cur && (p->affinity & (1u << c->id)) &&
  236. (cur == c->idle || p->weight >= cur->weight)) {
  237. c->need_resched = 1;
  238. /* The idle timer period is 10 ms; shorten it so the woken
  239. * process runs at the next millisecond instead. */
  240. smp_resched_wake();
  241. }
  242. }
  243. void sched_add_ready(struct process *p)
  244. {
  245. unsigned int flags = sched_lock_acquire();
  246. if (!p->weight) {
  247. p->weight = SCHED_WEIGHT_DEFAULT;
  248. p->stride = weight_stride(p->weight);
  249. p->vruntime = min_vruntime_locked();
  250. }
  251. p->state = PROC_READY;
  252. runq_add_locked(p);
  253. sched_lock_release(flags);
  254. }
  255. void sched_unlink_locked(struct process *p)
  256. {
  257. runq_del_locked(p);
  258. if (p->waiting_on)
  259. waitq_del_locked(p);
  260. if (p->state == PROC_SLEEPING)
  261. sleepq_del_locked(p);
  262. }
  263. void sched_unlink(struct process *p)
  264. {
  265. unsigned int flags = sched_lock_acquire();
  266. sched_unlink_locked(p);
  267. sched_lock_release(flags);
  268. }
  269. void sched_set_weight_locked(struct process *p, unsigned int weight)
  270. {
  271. if (!p)
  272. return;
  273. if (weight < 1)
  274. weight = 1;
  275. if (weight > SCHED_WEIGHT_MAX)
  276. weight = SCHED_WEIGHT_MAX;
  277. if (p->state == PROC_RUNNING)
  278. account_locked(p);
  279. p->weight = weight;
  280. p->stride = weight_stride(weight);
  281. }
  282. /* Add the current process to a wait queue. The caller holds interrupts off
  283. * and must restore the flags and call sched_yield() itself. */
  284. void sched_block_on_locked(struct wait_queue *wq)
  285. {
  286. struct process *p = current_proc();
  287. if (!p)
  288. return;
  289. runq_del_locked(p);
  290. waitq_add_locked(wq, p);
  291. p->state = PROC_BLOCKED;
  292. p->on_runq = 0;
  293. }
  294. void sched_block_on(struct wait_queue *wq)
  295. {
  296. unsigned int flags;
  297. if (this_cpu()->preempt_count)
  298. return;
  299. flags = sched_lock_acquire();
  300. sched_block_on_locked(wq);
  301. sched_lock_release(flags);
  302. sched_yield();
  303. }
  304. /* Block on a wait queue with a deadline. Either a waiter wake or the sleep
  305. * list expiry removes the process from both queues. */
  306. void sched_block_timeout(struct wait_queue *wq, unsigned int ms)
  307. {
  308. struct process *p = current_proc();
  309. unsigned int flags;
  310. if (!p)
  311. return;
  312. if (ms == 0) {
  313. sched_block_on(wq);
  314. return;
  315. }
  316. if (this_cpu()->preempt_count)
  317. return;
  318. flags = sched_lock_acquire();
  319. p->wake_ms = get_ticks_ms() + ms;
  320. p->state = PROC_SLEEPING;
  321. runq_del_locked(p);
  322. waitq_add_locked(wq, p);
  323. sleepq_add_locked(p);
  324. sched_lock_release(flags);
  325. sched_yield();
  326. }
  327. static void wake_one_locked(struct wait_queue *wq)
  328. {
  329. struct process *p = wq->head;
  330. if (!p)
  331. return;
  332. waitq_del_locked(p);
  333. if (p->state == PROC_BLOCKED || p->state == PROC_SLEEPING)
  334. wake_locked(p);
  335. }
  336. void wait_wake_one(struct wait_queue *wq)
  337. {
  338. unsigned int flags = sched_lock_acquire();
  339. wake_one_locked(wq);
  340. sched_lock_release(flags);
  341. }
  342. void wait_wake_all(struct wait_queue *wq)
  343. {
  344. unsigned int flags = sched_lock_acquire();
  345. while (wq->head)
  346. wake_one_locked(wq);
  347. sched_lock_release(flags);
  348. }
  349. /* ---- sleeping big kernel lock ---- */
  350. void bkl_init(void)
  351. {
  352. bkl.owner = 0;
  353. bkl.depth = 0;
  354. wait_queue_init(&bkl.wait);
  355. }
  356. void bkl_lock(void)
  357. {
  358. struct process *p = current_proc();
  359. unsigned int flags;
  360. if (!p)
  361. return;
  362. unsigned int t0 = 0;
  363. if (bkl.owner == p) {
  364. bkl.depth++;
  365. return;
  366. }
  367. for (;;) {
  368. flags = sched_lock_acquire();
  369. if (!bkl.owner) {
  370. bkl.owner = p;
  371. bkl.depth = 1;
  372. bkl.since = get_ticks_ms();
  373. if (t0)
  374. bkl_stat.wait_ms += bkl.since - t0;
  375. sched_lock_release(flags);
  376. return;
  377. }
  378. if (!t0) {
  379. t0 = get_ticks_ms();
  380. bkl_stat.contended++;
  381. }
  382. sched_block_on_locked(&bkl.wait);
  383. sched_lock_release(flags);
  384. sched_yield();
  385. }
  386. }
  387. void bkl_unlock(void)
  388. {
  389. struct process *p = current_proc();
  390. unsigned int flags;
  391. if (!p)
  392. return;
  393. flags = sched_lock_acquire();
  394. if (bkl.owner == p) {
  395. if (bkl.depth > 1) {
  396. bkl.depth--;
  397. } else {
  398. bkl_note_release(p);
  399. bkl.owner = 0;
  400. bkl.depth = 0;
  401. wake_one_locked(&bkl.wait);
  402. }
  403. }
  404. sched_lock_release(flags);
  405. }
  406. int bkl_trylock(void)
  407. {
  408. struct process *p = current_proc();
  409. unsigned int flags;
  410. if (!p)
  411. return 1;
  412. if (bkl.owner == p) {
  413. bkl.depth++;
  414. return 1;
  415. }
  416. flags = sched_lock_acquire();
  417. if (!bkl.owner) {
  418. bkl.owner = p;
  419. bkl.depth = 1;
  420. bkl.since = get_ticks_ms();
  421. sched_lock_release(flags);
  422. return 1;
  423. }
  424. sched_lock_release(flags);
  425. return 0;
  426. }
  427. /* Drop the BKL around a voluntary switch and take it back on resume. The
  428. * saved depth lives in the PCB: only the owner can be holding it, and it is
  429. * the current process on this CPU. */
  430. static void bkl_yield_release(void)
  431. {
  432. struct process *p = current_proc();
  433. unsigned int flags;
  434. if (!p)
  435. return;
  436. flags = sched_lock_acquire();
  437. if (bkl.owner == p) {
  438. p->bkl_saved = bkl.depth;
  439. bkl_note_release(p);
  440. bkl.owner = 0;
  441. bkl.depth = 0;
  442. wake_one_locked(&bkl.wait);
  443. }
  444. /* Not the owner: leave bkl_saved alone. A nested sleep inside a
  445. * bkl_pause() section must not forget that it still has to resume the
  446. * paused ownership. */
  447. sched_lock_release(flags);
  448. }
  449. static void bkl_yield_reacquire(void)
  450. {
  451. struct process *p = current_proc();
  452. unsigned int depth;
  453. if (!p)
  454. return;
  455. depth = p->bkl_saved;
  456. if (!depth)
  457. return;
  458. p->bkl_saved = 0;
  459. bkl_lock();
  460. bkl.depth = depth;
  461. }
  462. void bkl_pause(void)
  463. {
  464. bkl_yield_release();
  465. }
  466. void bkl_resume(void)
  467. {
  468. bkl_yield_reacquire();
  469. }
  470. /* Run once on the new kernel stack: queue the process this CPU just left, so
  471. * its stack/page directory cannot be freed while switch.S still uses them. */
  472. void sched_finish_switch(void)
  473. {
  474. struct cpu *c = this_cpu();
  475. struct process *p;
  476. unsigned int flags;
  477. if (!c->deferred_unlock)
  478. return;
  479. p = c->pending_zombie;
  480. c->pending_zombie = 0;
  481. flags = c->sched_flags;
  482. c->deferred_unlock = 0;
  483. sched_lock_release(flags);
  484. if (p)
  485. process_zombie_add(p);
  486. }
  487. void sched_init(void)
  488. {
  489. unsigned int i;
  490. cpu_count = 1;
  491. runq_head = runq_tail = 0;
  492. sleep_head = sleep_tail = 0;
  493. wakeups = 0;
  494. sched_lock.locked = 0;
  495. bkl_init();
  496. for (i = 0; i < MAX_CPUS; i++) {
  497. cpus[i].current = 0;
  498. cpus[i].idle = 0;
  499. cpus[i].id = i;
  500. cpus[i].lapic_id = 0;
  501. cpus[i].need_resched = 0;
  502. cpus[i].preempt_count = 0;
  503. cpus[i].idle_ticks = 0;
  504. cpus[i].switches = 0;
  505. cpus[i].pending_zombie = 0;
  506. cpus[i].deferred_unlock = 0;
  507. cpus[i].temp_div = 0;
  508. cpus[i].temp_c = -1;
  509. cpus[i].tick_ms = 1;
  510. }
  511. }
  512. /* Each process owns its x87 state; the CPU's registers are not shared
  513. * between them any more (a preempted floating-point computation used to
  514. * continue with another process's stack and control word). Eager and
  515. * cheap enough at 1 kHz: FNSAVE/FRSTOR move 108 bytes and need no FXSR,
  516. * so they work back to the Pentium. The kernel uses no x87 itself; its
  517. * SSE fill helpers touch only XMM registers, which ring 3 never uses. */
  518. static void fpu_switch(struct process *cur, struct process *next)
  519. {
  520. if (cur) {
  521. __asm__ volatile ("fnsave %0" : "=m"(cur->fpu));
  522. cur->fpu_valid = 1;
  523. }
  524. if (next->fpu_valid)
  525. __asm__ volatile ("frstor %0" :: "m"(next->fpu));
  526. else
  527. __asm__ volatile ("fninit");
  528. }
  529. static void sched_switch_to(struct process *next)
  530. {
  531. struct cpu *c = this_cpu();
  532. unsigned int cr3 = paging_current_cr3();
  533. if (next->cr3 && next->cr3 != cr3) {
  534. __asm__ volatile ("movl %0, %%cr3"
  535. :
  536. : "r"(next->cr3)
  537. : "memory");
  538. }
  539. if (c->tss && next->kstack_top)
  540. c->tss->esp0 = next->kstack_top;
  541. }
  542. /* Pick the READY process with the smallest vruntime that may run on this
  543. * CPU. Ties go to the lower pid for determinism. */
  544. static struct process *pick_locked(void)
  545. {
  546. struct process *p, *best = 0;
  547. struct cpu *c = this_cpu();
  548. unsigned int mask = 1u << c->id;
  549. for (p = runq_head; p; p = p->run_next) {
  550. if (!(p->affinity & mask))
  551. continue;
  552. /* A process still marked on another CPU is a wake-up race
  553. * victim: it is about to reach its own CPU's schedule(). Let
  554. * that CPU deal with it instead of running it twice. */
  555. if (p->on_cpu != PROC_NO_CPU && p->on_cpu != c->id)
  556. continue;
  557. if (!best || p->vruntime < best->vruntime ||
  558. (p->vruntime == best->vruntime && p->pid < best->pid))
  559. best = p;
  560. }
  561. return best;
  562. }
  563. static void wake_sleepers_locked(void)
  564. {
  565. unsigned int now = get_ticks_ms();
  566. while (sleep_head && (int)(sleep_head->wake_ms - now) <= 0) {
  567. struct process *p = sleep_head;
  568. sleepq_del_locked(p);
  569. p->state = PROC_READY;
  570. p->wake_ms = 0;
  571. wake_locked(p);
  572. }
  573. }
  574. /*
  575. * CFS-lite schedule. Called from the PIT stub (after ESP has been saved) or
  576. * from the int 0x81 gate, always with interrupts disabled.
  577. */
  578. void schedule(void)
  579. {
  580. struct cpu *c = this_cpu();
  581. struct process *cur = c->current;
  582. struct process *next;
  583. unsigned int flags = sched_lock_acquire();
  584. if (cur && cur != c->idle) {
  585. if (cur->state == PROC_RUNNING) {
  586. account_locked(cur);
  587. cur->state = PROC_READY;
  588. runq_add_locked(cur);
  589. } else if (cur->state == PROC_READY) {
  590. /* Woken between setting BLOCKED/SLEEPING and entering
  591. * the gate: already on the run queue. */
  592. } else if (cur->state == PROC_DEAD) {
  593. /* Defer the zombie until switch.S has loaded the new
  594. * stack: its kernel stack and page directory are still
  595. * live until then. */
  596. c->pending_zombie = cur;
  597. }
  598. }
  599. next = pick_locked();
  600. if (!next) {
  601. next = c->idle;
  602. if (!next) {
  603. sched_lock_release(flags);
  604. for (;;)
  605. __asm__ volatile ("cli; hlt");
  606. }
  607. }
  608. if (next != cur) {
  609. if (cur)
  610. cur->on_cpu = PROC_NO_CPU;
  611. c->switches++;
  612. fpu_switch(cur, next);
  613. }
  614. runq_del_locked(next);
  615. next->state = PROC_RUNNING;
  616. next->on_cpu = c->id;
  617. next->last_cpu = c->id;
  618. next->slice_start = get_ticks_ms();
  619. c->current = next;
  620. c->need_resched = 0;
  621. /* The BSP PIT and each AP's LAPIC timer tick at 1 kHz while a process
  622. * runs; while a CPU is idle they drop to 100 Hz so MWAIT can hold C2
  623. * for 10 ms. The global millisecond clock stays accurate because the
  624. * PIT stub adds tick_ms (see timer_tick_advance). */
  625. if (c->id == 0) {
  626. timer_set_hz(next == c->idle ? 100 : 1000);
  627. } else {
  628. unsigned int ms = (next == c->idle) ? 10 : 1;
  629. c->tick_ms = ms;
  630. lapic_timer_set_ms(ms);
  631. }
  632. sched_switch_to(next);
  633. /* Keep the lock across the stack switch performed by switch.S; the
  634. * old process must not become runnable on another CPU while this CPU
  635. * is still using its kernel stack. */
  636. c->sched_flags = flags;
  637. c->deferred_unlock = 1;
  638. }
  639. void sched_yield(void)
  640. {
  641. struct cpu *c = this_cpu();
  642. /* Blocking helpers must not be used inside a preempt-disabled section.
  643. * If one is, record the request instead of switching with the count
  644. * still owned by the old process. */
  645. if (c->preempt_count) {
  646. c->need_resched = 1;
  647. return;
  648. }
  649. /* Release the BKL before switching away and take it back after being
  650. * resumed; a process that never resumes (exit) simply never reacquires
  651. * it. Blocking helpers therefore need no explicit BKL handling. */
  652. bkl_yield_release();
  653. __asm__ volatile ("int $0x81" ::: "memory");
  654. bkl_yield_reacquire();
  655. }
  656. void sched_sleep_ms(unsigned int ms)
  657. {
  658. struct process *p = current_proc();
  659. unsigned int flags;
  660. if (!p)
  661. return;
  662. if (ms == 0) {
  663. sched_yield();
  664. return;
  665. }
  666. if (this_cpu()->preempt_count)
  667. return; /* sleeping inside a non-preemptible section is invalid */
  668. flags = sched_lock_acquire();
  669. p->wake_ms = get_ticks_ms() + ms;
  670. p->state = PROC_SLEEPING;
  671. runq_del_locked(p);
  672. sleepq_add_locked(p);
  673. sched_lock_release(flags);
  674. sched_yield();
  675. }
  676. /* Called from the PIT after ticks has been incremented. Returns 1 when the
  677. * assembly should call schedule(). */
  678. /* Common tail of the tick path: with the scheduler lock held, decide whether
  679. * the assembly stub should call schedule(). */
  680. static int tick_decide_locked(struct cpu *c, struct process *p, int ap,
  681. unsigned int ms)
  682. {
  683. if (p) {
  684. p->cpu_ticks += ms;
  685. if (p == c->idle)
  686. c->idle_ticks += ms;
  687. }
  688. /* A process inside the kernel holding the big lock must not be
  689. * preempted: the lock is not preemptible, and its owner may be in the
  690. * middle of a kernel data structure update. Voluntary block points
  691. * release it first. */
  692. if (p && bkl.owner == p && p->state == PROC_RUNNING)
  693. return 0;
  694. if (c->preempt_count) {
  695. if (p && p != c->idle && p->state == PROC_RUNNING &&
  696. (unsigned int)(get_ticks_ms() - p->slice_start) >=
  697. SCHED_SLICE_TICKS)
  698. c->need_resched = 1;
  699. return 0;
  700. }
  701. /* APs only start taking work once the BSP has finished booting. */
  702. if (ap && !smp_sched_enabled)
  703. return 0;
  704. if (!p)
  705. return 0;
  706. if (p == c->idle) {
  707. if (pick_locked()) {
  708. c->need_resched = 1;
  709. return 1;
  710. }
  711. return 0;
  712. }
  713. if (p->state != PROC_RUNNING) {
  714. c->need_resched = 1;
  715. return 1;
  716. }
  717. if ((unsigned int)(get_ticks_ms() - p->slice_start) >= SCHED_SLICE_TICKS)
  718. c->need_resched = 1;
  719. return c->need_resched ? 1 : 0;
  720. }
  721. /* BSP PIT: also wakes the global sleep list (the PIT is the system clock). */
  722. int sched_tick_bsp(void)
  723. {
  724. struct cpu *c = this_cpu();
  725. struct process *p;
  726. unsigned int flags = sched_lock_acquire();
  727. int r;
  728. thermal_tick();
  729. p = c->current;
  730. power_tick(p == c->idle, timer_tick_ms());
  731. wake_sleepers_locked();
  732. r = tick_decide_locked(c, p, 0, timer_tick_ms());
  733. sched_lock_release(flags);
  734. return r;
  735. }
  736. /* AP local timer: no global tick counter and no sleeper wake-up (the BSP PIT
  737. * owns both); only this CPU's scheduling decision. */
  738. int sched_tick_ap(void)
  739. {
  740. struct cpu *c = this_cpu();
  741. struct process *p;
  742. unsigned int flags = sched_lock_acquire();
  743. int r;
  744. thermal_tick();
  745. p = c->current;
  746. power_tick(p == c->idle, c->tick_ms);
  747. r = tick_decide_locked(c, p, 1, c->tick_ms);
  748. if (!r && p == c->idle && c->tick_ms != 10) {
  749. /* Entered idle without a schedule(): stretch this CPU's LAPIC
  750. * period so MWAIT can hold C2 for 10 ms. */
  751. c->tick_ms = 10;
  752. lapic_timer_set_ms(10);
  753. }
  754. sched_lock_release(flags);
  755. return r;
  756. }
  757. void preempt_disable(void)
  758. {
  759. this_cpu()->preempt_count++;
  760. }
  761. void preempt_enable(void)
  762. {
  763. struct cpu *c = this_cpu();
  764. if (c->preempt_count)
  765. c->preempt_count--;
  766. }
  767. int sched_snapshot(struct sys_schedinfo *out)
  768. {
  769. unsigned int flags, i;
  770. struct process *p;
  771. if (!out)
  772. return -1;
  773. flags = sched_lock_acquire();
  774. out->ncpus = cpu_count;
  775. out->runnable = 0;
  776. for (p = runq_head; p; p = p->run_next)
  777. out->runnable++;
  778. out->sleeping = 0;
  779. for (p = sleep_head; p; p = p->sleep_next)
  780. out->sleeping++;
  781. out->blocked = 0;
  782. for (i = 0; i < PROC_MAX; i++) {
  783. p = procs[i];
  784. if (p && p->state == PROC_BLOCKED)
  785. out->blocked++;
  786. }
  787. out->zombies = process_zombie_count_locked();
  788. out->switches = 0;
  789. out->idle_ticks = 0;
  790. for (i = 0; i < cpu_count && i < MAX_CPUS; i++) {
  791. out->switches += cpus[i].switches;
  792. out->idle_ticks += cpus[i].idle_ticks;
  793. }
  794. out->wakeups = wakeups;
  795. out->slice_ticks = SCHED_SLICE_TICKS;
  796. sched_lock_release(flags);
  797. return 0;
  798. }
  799. static void sched_put_dec(unsigned int n)
  800. {
  801. char buf[12];
  802. unsigned int i = sizeof(buf) - 1;
  803. buf[i] = '\0';
  804. if (n == 0) {
  805. io_putchar('0');
  806. return;
  807. }
  808. while (n && i > 0) {
  809. buf[--i] = (char)('0' + (n % 10));
  810. n /= 10;
  811. }
  812. io_putstr(buf + i);
  813. }
  814. void sched_print(void)
  815. {
  816. struct sys_schedinfo s;
  817. unsigned int uptime, idle_pm, up_s, total_s, idle_s, idle_frac, ncpu;
  818. if (sched_snapshot(&s) != 0)
  819. return;
  820. uptime = get_ticks_ms();
  821. ncpu = s.ncpus ? s.ncpus : 1;
  822. /* Idle is a share of the total CPU capacity, so 4 idle CPUs at 50%
  823. * each report 50%, not 200%. Avoid 64-bit division: scale to seconds
  824. * first (four CPUs overflow after ~12 days; good enough for the
  825. * display). */
  826. up_s = uptime / 1000u;
  827. total_s = up_s * ncpu;
  828. if (total_s == 0) {
  829. idle_pm = (s.idle_ticks >= uptime * ncpu) ? 1000 : 0;
  830. } else {
  831. idle_s = s.idle_ticks / 1000u;
  832. idle_frac = s.idle_ticks % 1000u;
  833. idle_pm = (idle_s * 1000u) / total_s;
  834. idle_pm += (idle_frac * 1000u / total_s) / 1000u;
  835. if (idle_pm > 1000u)
  836. idle_pm = 1000u;
  837. }
  838. io_putstr("sched: cfs, ");
  839. sched_put_dec(s.ncpus);
  840. io_putstr(" cpu, ");
  841. sched_put_dec(s.slice_ticks);
  842. io_putstr(" ms slice\nrunq ");
  843. sched_put_dec(s.runnable);
  844. io_putstr(" sleep ");
  845. sched_put_dec(s.sleeping);
  846. io_putstr(" block ");
  847. sched_put_dec(s.blocked);
  848. io_putstr(" zombie ");
  849. sched_put_dec(s.zombies);
  850. io_putstr("\nswitches ");
  851. sched_put_dec(s.switches);
  852. io_putstr(" wakeups ");
  853. sched_put_dec(s.wakeups);
  854. io_putstr(" idle ");
  855. sched_put_dec(idle_pm / 10);
  856. io_putchar('.');
  857. io_putchar((char)('0' + idle_pm % 10));
  858. io_putstr("%\n");
  859. /* Since the last `sched`. */
  860. io_putstr("bkl: contended ");
  861. sched_put_dec(bkl_stat.contended);
  862. io_putstr(" waited ");
  863. sched_put_dec(bkl_stat.wait_ms);
  864. io_putstr(" ms longest hold ");
  865. sched_put_dec(bkl_stat.hold_max_ms);
  866. io_putstr(" ms (");
  867. io_putstr(bkl_stat.hold_max_name[0] ? bkl_stat.hold_max_name : "-");
  868. io_putstr(")\n");
  869. bkl_stat.contended = 0;
  870. bkl_stat.wait_ms = 0;
  871. bkl_stat.hold_max_ms = 0;
  872. bkl_stat.hold_max_name[0] = '\0';
  873. }