cpudeadline.c 6.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295
  1. // SPDX-License-Identifier: GPL-2.0-only
  2. /*
  3. * kernel/sched/cpudeadline.c
  4. *
  5. * Global CPU deadline management
  6. *
  7. * Author: Juri Lelli <[email protected]>
  8. */
  9. static inline int parent(int i)
  10. {
  11. return (i - 1) >> 1;
  12. }
  13. static inline int left_child(int i)
  14. {
  15. return (i << 1) + 1;
  16. }
  17. static inline int right_child(int i)
  18. {
  19. return (i << 1) + 2;
  20. }
  21. static void cpudl_heapify_down(struct cpudl *cp, int idx)
  22. {
  23. int l, r, largest;
  24. int orig_cpu = cp->elements[idx].cpu;
  25. u64 orig_dl = cp->elements[idx].dl;
  26. if (left_child(idx) >= cp->size)
  27. return;
  28. /* adapted from lib/prio_heap.c */
  29. while (1) {
  30. u64 largest_dl;
  31. l = left_child(idx);
  32. r = right_child(idx);
  33. largest = idx;
  34. largest_dl = orig_dl;
  35. if ((l < cp->size) && dl_time_before(orig_dl,
  36. cp->elements[l].dl)) {
  37. largest = l;
  38. largest_dl = cp->elements[l].dl;
  39. }
  40. if ((r < cp->size) && dl_time_before(largest_dl,
  41. cp->elements[r].dl))
  42. largest = r;
  43. if (largest == idx)
  44. break;
  45. /* pull largest child onto idx */
  46. cp->elements[idx].cpu = cp->elements[largest].cpu;
  47. cp->elements[idx].dl = cp->elements[largest].dl;
  48. cp->elements[cp->elements[idx].cpu].idx = idx;
  49. idx = largest;
  50. }
  51. /* actual push down of saved original values orig_* */
  52. cp->elements[idx].cpu = orig_cpu;
  53. cp->elements[idx].dl = orig_dl;
  54. cp->elements[cp->elements[idx].cpu].idx = idx;
  55. }
  56. static void cpudl_heapify_up(struct cpudl *cp, int idx)
  57. {
  58. int p;
  59. int orig_cpu = cp->elements[idx].cpu;
  60. u64 orig_dl = cp->elements[idx].dl;
  61. if (idx == 0)
  62. return;
  63. do {
  64. p = parent(idx);
  65. if (dl_time_before(orig_dl, cp->elements[p].dl))
  66. break;
  67. /* pull parent onto idx */
  68. cp->elements[idx].cpu = cp->elements[p].cpu;
  69. cp->elements[idx].dl = cp->elements[p].dl;
  70. cp->elements[cp->elements[idx].cpu].idx = idx;
  71. idx = p;
  72. } while (idx != 0);
  73. /* actual push up of saved original values orig_* */
  74. cp->elements[idx].cpu = orig_cpu;
  75. cp->elements[idx].dl = orig_dl;
  76. cp->elements[cp->elements[idx].cpu].idx = idx;
  77. }
  78. static void cpudl_heapify(struct cpudl *cp, int idx)
  79. {
  80. if (idx > 0 && dl_time_before(cp->elements[parent(idx)].dl,
  81. cp->elements[idx].dl))
  82. cpudl_heapify_up(cp, idx);
  83. else
  84. cpudl_heapify_down(cp, idx);
  85. }
  86. static inline int cpudl_maximum(struct cpudl *cp)
  87. {
  88. return cp->elements[0].cpu;
  89. }
  90. /*
  91. * cpudl_find - find the best (later-dl) CPU in the system
  92. * @cp: the cpudl max-heap context
  93. * @p: the task
  94. * @later_mask: a mask to fill in with the selected CPUs (or NULL)
  95. *
  96. * Returns: int - CPUs were found
  97. */
  98. int cpudl_find(struct cpudl *cp, struct task_struct *p,
  99. struct cpumask *later_mask)
  100. {
  101. const struct sched_dl_entity *dl_se = &p->dl;
  102. if (later_mask &&
  103. cpumask_and(later_mask, cp->free_cpus, &p->cpus_mask)) {
  104. unsigned long cap, max_cap = 0;
  105. int cpu, max_cpu = -1;
  106. if (!sched_asym_cpucap_active())
  107. return 1;
  108. /* Ensure the capacity of the CPUs fits the task. */
  109. for_each_cpu(cpu, later_mask) {
  110. if (!dl_task_fits_capacity(p, cpu)) {
  111. cpumask_clear_cpu(cpu, later_mask);
  112. cap = capacity_orig_of(cpu);
  113. if (cap > max_cap ||
  114. (cpu == task_cpu(p) && cap == max_cap)) {
  115. max_cap = cap;
  116. max_cpu = cpu;
  117. }
  118. }
  119. }
  120. if (cpumask_empty(later_mask))
  121. cpumask_set_cpu(max_cpu, later_mask);
  122. return 1;
  123. } else {
  124. int best_cpu = cpudl_maximum(cp);
  125. WARN_ON(best_cpu != -1 && !cpu_present(best_cpu));
  126. if (cpumask_test_cpu(best_cpu, &p->cpus_mask) &&
  127. dl_time_before(dl_se->deadline, cp->elements[0].dl)) {
  128. if (later_mask)
  129. cpumask_set_cpu(best_cpu, later_mask);
  130. return 1;
  131. }
  132. }
  133. return 0;
  134. }
  135. /*
  136. * cpudl_clear - remove a CPU from the cpudl max-heap
  137. * @cp: the cpudl max-heap context
  138. * @cpu: the target CPU
  139. *
  140. * Notes: assumes cpu_rq(cpu)->lock is locked
  141. *
  142. * Returns: (void)
  143. */
  144. void cpudl_clear(struct cpudl *cp, int cpu)
  145. {
  146. int old_idx, new_cpu;
  147. unsigned long flags;
  148. WARN_ON(!cpu_present(cpu));
  149. raw_spin_lock_irqsave(&cp->lock, flags);
  150. old_idx = cp->elements[cpu].idx;
  151. if (old_idx == IDX_INVALID) {
  152. /*
  153. * Nothing to remove if old_idx was invalid.
  154. * This could happen if a rq_offline_dl is
  155. * called for a CPU without -dl tasks running.
  156. */
  157. } else {
  158. new_cpu = cp->elements[cp->size - 1].cpu;
  159. cp->elements[old_idx].dl = cp->elements[cp->size - 1].dl;
  160. cp->elements[old_idx].cpu = new_cpu;
  161. cp->size--;
  162. cp->elements[new_cpu].idx = old_idx;
  163. cp->elements[cpu].idx = IDX_INVALID;
  164. cpudl_heapify(cp, old_idx);
  165. cpumask_set_cpu(cpu, cp->free_cpus);
  166. }
  167. raw_spin_unlock_irqrestore(&cp->lock, flags);
  168. }
  169. /*
  170. * cpudl_set - update the cpudl max-heap
  171. * @cp: the cpudl max-heap context
  172. * @cpu: the target CPU
  173. * @dl: the new earliest deadline for this CPU
  174. *
  175. * Notes: assumes cpu_rq(cpu)->lock is locked
  176. *
  177. * Returns: (void)
  178. */
  179. void cpudl_set(struct cpudl *cp, int cpu, u64 dl)
  180. {
  181. int old_idx;
  182. unsigned long flags;
  183. WARN_ON(!cpu_present(cpu));
  184. raw_spin_lock_irqsave(&cp->lock, flags);
  185. old_idx = cp->elements[cpu].idx;
  186. if (old_idx == IDX_INVALID) {
  187. int new_idx = cp->size++;
  188. cp->elements[new_idx].dl = dl;
  189. cp->elements[new_idx].cpu = cpu;
  190. cp->elements[cpu].idx = new_idx;
  191. cpudl_heapify_up(cp, new_idx);
  192. cpumask_clear_cpu(cpu, cp->free_cpus);
  193. } else {
  194. cp->elements[old_idx].dl = dl;
  195. cpudl_heapify(cp, old_idx);
  196. }
  197. raw_spin_unlock_irqrestore(&cp->lock, flags);
  198. }
  199. /*
  200. * cpudl_set_freecpu - Set the cpudl.free_cpus
  201. * @cp: the cpudl max-heap context
  202. * @cpu: rd attached CPU
  203. */
  204. void cpudl_set_freecpu(struct cpudl *cp, int cpu)
  205. {
  206. cpumask_set_cpu(cpu, cp->free_cpus);
  207. }
  208. /*
  209. * cpudl_clear_freecpu - Clear the cpudl.free_cpus
  210. * @cp: the cpudl max-heap context
  211. * @cpu: rd attached CPU
  212. */
  213. void cpudl_clear_freecpu(struct cpudl *cp, int cpu)
  214. {
  215. cpumask_clear_cpu(cpu, cp->free_cpus);
  216. }
  217. /*
  218. * cpudl_init - initialize the cpudl structure
  219. * @cp: the cpudl max-heap context
  220. */
  221. int cpudl_init(struct cpudl *cp)
  222. {
  223. int i;
  224. raw_spin_lock_init(&cp->lock);
  225. cp->size = 0;
  226. cp->elements = kcalloc(nr_cpu_ids,
  227. sizeof(struct cpudl_item),
  228. GFP_KERNEL);
  229. if (!cp->elements)
  230. return -ENOMEM;
  231. if (!zalloc_cpumask_var(&cp->free_cpus, GFP_KERNEL)) {
  232. kfree(cp->elements);
  233. return -ENOMEM;
  234. }
  235. for_each_possible_cpu(i)
  236. cp->elements[i].idx = IDX_INVALID;
  237. return 0;
  238. }
  239. /*
  240. * cpudl_cleanup - clean up the cpudl structure
  241. * @cp: the cpudl max-heap context
  242. */
  243. void cpudl_cleanup(struct cpudl *cp)
  244. {
  245. free_cpumask_var(cp->free_cpus);
  246. kfree(cp->elements);
  247. }