Branch data     Line data    Source code

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