sched.c 20 KB

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