sched.c 21 KB

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