0001: /* 0002: * Deadline Scheduling Class (SCHED_DEADLINE) 0003: * 0004: * Earliest Deadline First (EDF) + Constant Bandwidth Server (CBS). 0005: * 0006: * Tasks that periodically executes their instances for less than their 0007: * runtime won't miss any of their deadlines. 0008: * Tasks that are not periodic or sporadic or that tries to execute more 0009: * than their reserved bandwidth will be slowed down (and may potentially 0010: * miss some of their deadlines), and won't affect any other task. 0011: * 0012: * Copyright (C) 2012 Dario Faggioli <raistlin@linux.it>, 0013: * Juri Lelli <juri.lelli@gmail.com>, 0014: * Michael Trimarchi <michael@amarulasolutions.com>, 0015: * Fabio Checconi <fchecconi@gmail.com> 0016: */ 0017: #include "sched.h" 0018: 0019: #include <linux/slab.h> 0020: 0021: struct dl_bandwidth def_dl_bandwidth; 0022: 0023: static inline struct task_struct *dl_task_of(struct sched_dl_entity *dl_se) 0024: { 0025: return container_of(dl_se, struct task_struct, dl); 0026: } 0027: 0028: static inline struct rq *rq_of_dl_rq(struct dl_rq *dl_rq) 0029: { 0030: return container_of(dl_rq, struct rq, dl); 0031: } 0032: 0033: static inline struct dl_rq *dl_rq_of_se(struct sched_dl_entity *dl_se) 0034: { 0035: struct task_struct *p = dl_task_of(dl_se); 0036: struct rq *rq = task_rq(p); 0037: 0038: return &rq->dl; 0039: } 0040: 0041: static inline int on_dl_rq(struct sched_dl_entity *dl_se) 0042: { 0043: return !RB_EMPTY_NODE(&dl_se->rb_node); 0044: } 0045: 0046: static inline int is_leftmost(struct task_struct *p, struct dl_rq *dl_rq) 0047: { 0048: struct sched_dl_entity *dl_se = &p->dl; 0049: 0050: return dl_rq->rb_leftmost == &dl_se->rb_node; 0051: } 0052: 0053: void init_dl_bandwidth(struct dl_bandwidth *dl_b, u64 period, u64 runtime) 0054: { 0055: raw_spin_lock_init(&dl_b->dl_runtime_lock); 0056: dl_b->dl_period = period; 0057: dl_b->dl_runtime = runtime; 0058: } 0059: 0060: void init_dl_bw(struct dl_bw *dl_b) 0061: { 0062: raw_spin_lock_init(&dl_b->lock); 0063: raw_spin_lock(&def_dl_bandwidth.dl_runtime_lock); 0064: if (global_rt_runtime() == RUNTIME_INF) 0065: dl_b->bw = -1; 0066: else 0067: dl_b->bw = to_ratio(global_rt_period(), global_rt_runtime()); 0068: raw_spin_unlock(&def_dl_bandwidth.dl_runtime_lock); 0069: dl_b->total_bw = 0; 0070: } 0071: 0072: void init_dl_rq(struct dl_rq *dl_rq) 0073: { 0074: dl_rq->rb_root = RB_ROOT; 0075: 0076: #ifdef CONFIG_SMP 0077: /* zero means no -deadline tasks */ 0078: dl_rq->earliest_dl.curr = dl_rq->earliest_dl.next = 0; 0079: 0080: dl_rq->dl_nr_migratory = 0; 0081: dl_rq->overloaded = 0; 0082: dl_rq->pushable_dl_tasks_root = RB_ROOT; 0083: #else 0084: init_dl_bw(&dl_rq->dl_bw); 0085: #endif 0086: } 0087: 0088: #ifdef CONFIG_SMP 0089: 0090: static inline int dl_overloaded(struct rq *rq) 0091: { 0092: return atomic_read(&rq->rd->dlo_count); 0093: } 0094: 0095: static inline void dl_set_overload(struct rq *rq) 0096: { 0097: if (!rq->online) 0098: return; 0099: 0100: cpumask_set_cpu(rq->cpu, rq->rd->dlo_mask); 0101: /* 0102: * Must be visible before the overload count is 0103: * set (as in sched_rt.c). 0104: * 0105: * Matched by the barrier in pull_dl_task(). 0106: */ 0107: smp_wmb(); 0108: atomic_inc(&rq->rd->dlo_count); 0109: } 0110: 0111: static inline void dl_clear_overload(struct rq *rq) 0112: { 0113: if (!rq->online) 0114: return; 0115: 0116: atomic_dec(&rq->rd->dlo_count); 0117: cpumask_clear_cpu(rq->cpu, rq->rd->dlo_mask); 0118: } 0119: 0120: static void update_dl_migration(struct dl_rq *dl_rq) 0121: { 0122: if (dl_rq->dl_nr_migratory && dl_rq->dl_nr_running > 1) { 0123: if (!dl_rq->overloaded) { 0124: dl_set_overload(rq_of_dl_rq(dl_rq)); 0125: dl_rq->overloaded = 1; 0126: } 0127: } else if (dl_rq->overloaded) { 0128: dl_clear_overload(rq_of_dl_rq(dl_rq)); 0129: dl_rq->overloaded = 0; 0130: } 0131: } 0132: 0133: static void inc_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq) 0134: { 0135: struct task_struct *p = dl_task_of(dl_se); 0136: 0137: if (p->nr_cpus_allowed > 1) 0138: dl_rq->dl_nr_migratory++; 0139: 0140: update_dl_migration(dl_rq); 0141: } 0142: 0143: static void dec_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq) 0144: { 0145: struct task_struct *p = dl_task_of(dl_se); 0146: 0147: if (p->nr_cpus_allowed > 1) 0148: dl_rq->dl_nr_migratory--; 0149: 0150: update_dl_migration(dl_rq); 0151: } 0152: 0153: /* 0154: * The list of pushable -deadline task is not a plist, like in 0155: * sched_rt.c, it is an rb-tree with tasks ordered by deadline. 0156: */ 0157: static void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p) 0158: { 0159: struct dl_rq *dl_rq = &rq->dl; 0160: struct rb_node **link = &dl_rq->pushable_dl_tasks_root.rb_node; 0161: struct rb_node *parent = NULL; 0162: struct task_struct *entry; 0163: int leftmost = 1; 0164: 0165: BUG_ON(!RB_EMPTY_NODE(&p->pushable_dl_tasks)); 0166: 0167: while (*link) { 0168: parent = *link; 0169: entry = rb_entry(parent, struct task_struct, 0170: pushable_dl_tasks); 0171: if (dl_entity_preempt(&p->dl, &entry->dl)) 0172: link = &parent->rb_left; 0173: else { 0174: link = &parent->rb_right; 0175: leftmost = 0; 0176: } 0177: } 0178: 0179: if (leftmost) 0180: dl_rq->pushable_dl_tasks_leftmost = &p->pushable_dl_tasks; 0181: 0182: rb_link_node(&p->pushable_dl_tasks, parent, link); 0183: rb_insert_color(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root); 0184: } 0185: 0186: static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p) 0187: { 0188: struct dl_rq *dl_rq = &rq->dl; 0189: 0190: if (RB_EMPTY_NODE(&p->pushable_dl_tasks)) 0191: return; 0192: 0193: if (dl_rq->pushable_dl_tasks_leftmost == &p->pushable_dl_tasks) { 0194: struct rb_node *next_node; 0195: 0196: next_node = rb_next(&p->pushable_dl_tasks); 0197: dl_rq->pushable_dl_tasks_leftmost = next_node; 0198: } 0199: 0200: rb_erase(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root); 0201: RB_CLEAR_NODE(&p->pushable_dl_tasks); 0202: } 0203: 0204: static inline int has_pushable_dl_tasks(struct rq *rq) 0205: { 0206: return !RB_EMPTY_ROOT(&rq->dl.pushable_dl_tasks_root); 0207: } 0208: 0209: static int push_dl_task(struct rq *rq); 0210: 0211: static inline bool need_pull_dl_task(struct rq *rq, struct task_struct *prev) 0212: { 0213: return dl_task(prev); 0214: } 0215: 0216: static DEFINE_PER_CPU(struct callback_head, dl_push_head); 0217: static DEFINE_PER_CPU(struct callback_head, dl_pull_head); 0218: 0219: static void push_dl_tasks(struct rq *); 0220: static void pull_dl_task(struct rq *); 0221: 0222: static inline void queue_push_tasks(struct rq *rq) 0223: { 0224: if (!has_pushable_dl_tasks(rq)) 0225: return; 0226: 0227: queue_balance_callback(rq, &per_cpu(dl_push_head, rq->cpu), push_dl_tasks); 0228: } 0229: 0230: static inline void queue_pull_task(struct rq *rq) 0231: { 0232: queue_balance_callback(rq, &per_cpu(dl_pull_head, rq->cpu), pull_dl_task); 0233: } 0234: 0235: static struct rq *find_lock_later_rq(struct task_struct *task, struct rq *rq); 0236: 0237: static struct rq *dl_task_offline_migration(struct rq *rq, struct task_struct *p) 0238: { 0239: struct rq *later_rq = NULL; 0240: bool fallback = false; 0241: 0242: later_rq = find_lock_later_rq(p, rq); 0243: 0244: if (!later_rq) { 0245: int cpu; 0246: 0247: /* 0248: * If we cannot preempt any rq, fall back to pick any 0249: * online cpu. 0250: */ 0251: fallback = true; 0252: cpu = cpumask_any_and(cpu_active_mask, tsk_cpus_allowed(p)); 0253: if (cpu >= nr_cpu_ids) { 0254: /* 0255: * Fail to find any suitable cpu. 0256: * The task will never come back! 0257: */ 0258: BUG_ON(dl_bandwidth_enabled()); 0259: 0260: /* 0261: * If admission control is disabled we 0262: * try a little harder to let the task 0263: * run. 0264: */ 0265: cpu = cpumask_any(cpu_active_mask); 0266: } 0267: later_rq = cpu_rq(cpu); 0268: double_lock_balance(rq, later_rq); 0269: } 0270: 0271: /* 0272: * By now the task is replenished and enqueued; migrate it. 0273: */ 0274: deactivate_task(rq, p, 0); 0275: set_task_cpu(p, later_rq->cpu); 0276: activate_task(later_rq, p, 0); 0277: 0278: if (!fallback) 0279: resched_curr(later_rq); 0280: 0281: double_unlock_balance(later_rq, rq); 0282: 0283: return later_rq; 0284: } 0285: 0286: #else 0287: 0288: static inline 0289: void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p) 0290: { 0291: } 0292: 0293: static inline 0294: void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p) 0295: { 0296: } 0297: 0298: static inline 0299: void inc_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq) 0300: { 0301: } 0302: 0303: static inline 0304: void dec_dl_migration(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq) 0305: { 0306: } 0307: 0308: static inline bool need_pull_dl_task(struct rq *rq, struct task_struct *prev) 0309: { 0310: return false; 0311: } 0312: 0313: static inline void pull_dl_task(struct rq *rq) 0314: { 0315: } 0316: 0317: static inline void queue_push_tasks(struct rq *rq) 0318: { 0319: } 0320: 0321: static inline void queue_pull_task(struct rq *rq) 0322: { 0323: } 0324: #endif /* CONFIG_SMP */ 0325: 0326: static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags); 0327: static void __dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags); 0328: static void check_preempt_curr_dl(struct rq *rq, struct task_struct *p, 0329: int flags); 0330: 0331: /* 0332: * We are being explicitly informed that a new instance is starting, 0333: * and this means that: 0334: * - the absolute deadline of the entity has to be placed at 0335: * current time + relative deadline; 0336: * - the runtime of the entity has to be set to the maximum value. 0337: * 0338: * The capability of specifying such event is useful whenever a -deadline 0339: * entity wants to (try to!) synchronize its behaviour with the scheduler's 0340: * one, and to (try to!) reconcile itself with its own scheduling 0341: * parameters. 0342: */ 0343: static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se, 0344: struct sched_dl_entity *pi_se) 0345: { 0346: struct dl_rq *dl_rq = dl_rq_of_se(dl_se); 0347: struct rq *rq = rq_of_dl_rq(dl_rq); 0348: 0349: WARN_ON(!dl_se->dl_new || dl_se->dl_throttled); 0350: 0351: /* 0352: * We use the regular wall clock time to set deadlines in the 0353: * future; in fact, we must consider execution overheads (time 0354: * spent on hardirq context, etc.). 0355: */ 0356: dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline; 0357: dl_se->runtime = pi_se->dl_runtime; 0358: dl_se->dl_new = 0; 0359: } 0360: 0361: /* 0362: * Pure Earliest Deadline First (EDF) scheduling does not deal with the 0363: * possibility of a entity lasting more than what it declared, and thus 0364: * exhausting its runtime. 0365: * 0366: * Here we are interested in making runtime overrun possible, but we do 0367: * not want a entity which is misbehaving to affect the scheduling of all 0368: * other entities. 0369: * Therefore, a budgeting strategy called Constant Bandwidth Server (CBS) 0370: * is used, in order to confine each entity within its own bandwidth. 0371: * 0372: * This function deals exactly with that, and ensures that when the runtime 0373: * of a entity is replenished, its deadline is also postponed. That ensures 0374: * the overrunning entity can't interfere with other entity in the system and 0375: * can't make them miss their deadlines. Reasons why this kind of overruns 0376: * could happen are, typically, a entity voluntarily trying to overcome its 0377: * runtime, or it just underestimated it during sched_setattr(). 0378: */ 0379: static void replenish_dl_entity(struct sched_dl_entity *dl_se, 0380: struct sched_dl_entity *pi_se) 0381: { 0382: struct dl_rq *dl_rq = dl_rq_of_se(dl_se); 0383: struct rq *rq = rq_of_dl_rq(dl_rq); 0384: 0385: BUG_ON(pi_se->dl_runtime <= 0); 0386: 0387: /* 0388: * This could be the case for a !-dl task that is boosted. 0389: * Just go with full inherited parameters. 0390: */ 0391: if (dl_se->dl_deadline == 0) { 0392: dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline; 0393: dl_se->runtime = pi_se->dl_runtime; 0394: } 0395: 0396: /* 0397: * We keep moving the deadline away until we get some 0398: * available runtime for the entity. This ensures correct 0399: * handling of situations where the runtime overrun is 0400: * arbitrary large. 0401: */ 0402: while (dl_se->runtime <= 0) { 0403: dl_se->deadline += pi_se->dl_period; 0404: dl_se->runtime += pi_se->dl_runtime; 0405: } 0406: 0407: /* 0408: * At this point, the deadline really should be "in 0409: * the future" with respect to rq->clock. If it's 0410: * not, we are, for some reason, lagging too much! 0411: * Anyway, after having warn userspace abut that, 0412: * we still try to keep the things running by 0413: * resetting the deadline and the budget of the 0414: * entity. 0415: */ 0416: if (dl_time_before(dl_se->deadline, rq_clock(rq))) { 0417: printk_deferred_once("sched: DL replenish lagged to much\n"); 0418: dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline; 0419: dl_se->runtime = pi_se->dl_runtime; 0420: } 0421: 0422: if (dl_se->dl_yielded) 0423: dl_se->dl_yielded = 0; 0424: if (dl_se->dl_throttled) 0425: dl_se->dl_throttled = 0; 0426: } 0427: 0428: /* 0429: * Here we check if --at time t-- an entity (which is probably being 0430: * [re]activated or, in general, enqueued) can use its remaining runtime 0431: * and its current deadline _without_ exceeding the bandwidth it is 0432: * assigned (function returns true if it can't). We are in fact applying 0433: * one of the CBS rules: when a task wakes up, if the residual runtime 0434: * over residual deadline fits within the allocated bandwidth, then we 0435: * can keep the current (absolute) deadline and residual budget without 0436: * disrupting the schedulability of the system. Otherwise, we should 0437: * refill the runtime and set the deadline a period in the future, 0438: * because keeping the current (absolute) deadline of the task would 0439: * result in breaking guarantees promised to other tasks (refer to 0440: * Documentation/scheduler/sched-deadline.txt for more informations). 0441: * 0442: * This function returns true if: 0443: * 0444: * runtime / (deadline - t) > dl_runtime / dl_deadline , 0445: * 0446: * IOW we can't recycle current parameters. 0447: * 0448: * Notice that the bandwidth check is done against the deadline. For 0449: * task with deadline equal to period this is the same of using 0450: * dl_period instead of dl_deadline in the equation above. 0451: */ 0452: static bool dl_entity_overflow(struct sched_dl_entity *dl_se, 0453: struct sched_dl_entity *pi_se, u64 t) 0454: { 0455: u64 left, right; 0456: 0457: /* 0458: * left and right are the two sides of the equation above, 0459: * after a bit of shuffling to use multiplications instead 0460: * of divisions. 0461: * 0462: * Note that none of the time values involved in the two 0463: * multiplications are absolute: dl_deadline and dl_runtime 0464: * are the relative deadline and the maximum runtime of each 0465: * instance, runtime is the runtime left for the last instance 0466: * and (deadline - t), since t is rq->clock, is the time left 0467: * to the (absolute) deadline. Even if overflowing the u64 type 0468: * is very unlikely to occur in both cases, here we scale down 0469: * as we want to avoid that risk at all. Scaling down by 10 0470: * means that we reduce granularity to 1us. We are fine with it, 0471: * since this is only a true/false check and, anyway, thinking 0472: * of anything below microseconds resolution is actually fiction 0473: * (but still we want to give the user that illusion >;). 0474: */ 0475: left = (pi_se->dl_deadline >> DL_SCALE) * (dl_se->runtime >> DL_SCALE); 0476: right = ((dl_se->deadline - t) >> DL_SCALE) * 0477: (pi_se->dl_runtime >> DL_SCALE); 0478: 0479: return dl_time_before(right, left); 0480: } 0481: 0482: /* 0483: * Revised wakeup rule [1]: For self-suspending tasks, rather then 0484: * re-initializing task's runtime and deadline, the revised wakeup 0485: * rule adjusts the task's runtime to avoid the task to overrun its 0486: * density. 0487: * 0488: * Reasoning: a task may overrun the density if: 0489: * runtime / (deadline - t) > dl_runtime / dl_deadline 0490: * 0491: * Therefore, runtime can be adjusted to: 0492: * runtime = (dl_runtime / dl_deadline) * (deadline - t) 0493: * 0494: * In such way that runtime will be equal to the maximum density 0495: * the task can use without breaking any rule. 0496: * 0497: * [1] Luca Abeni, Giuseppe Lipari, and Juri Lelli. 2015. Constant 0498: * bandwidth server revisited. SIGBED Rev. 11, 4 (January 2015), 19-24. 0499: */ 0500: static void 0501: update_dl_revised_wakeup(struct sched_dl_entity *dl_se, struct rq *rq) 0502: { 0503: u64 laxity = dl_se->deadline - rq_clock(rq); 0504: 0505: /* 0506: * If the task has deadline < period, and the deadline is in the past, 0507: * it should already be throttled before this check. 0508: * 0509: * See update_dl_entity() comments for further details. 0510: */ 0511: WARN_ON(dl_time_before(dl_se->deadline, rq_clock(rq))); 0512: 0513: dl_se->runtime = (dl_se->dl_density * laxity) >> 20; 0514: } 0515: 0516: /* 0517: * Regarding the deadline, a task with implicit deadline has a relative 0518: * deadline == relative period. A task with constrained deadline has a 0519: * relative deadline <= relative period. 0520: * 0521: * We support constrained deadline tasks. However, there are some restrictions 0522: * applied only for tasks which do not have an implicit deadline. See 0523: * update_dl_entity() to know more about such restrictions. 0524: * 0525: * The dl_is_implicit() returns true if the task has an implicit deadline. 0526: */ 0527: static inline bool dl_is_implicit(struct sched_dl_entity *dl_se) 0528: { 0529: return dl_se->dl_deadline == dl_se->dl_period; 0530: } 0531: 0532: /* 0533: * When a deadline entity is placed in the runqueue, its runtime and deadline 0534: * might need to be updated. This is done by a CBS wake up rule. There are two 0535: * different rules: 1) the original CBS; and 2) the Revisited CBS. 0536: * 0537: * When the task is starting a new period, the Original CBS is used. In this 0538: * case, the runtime is replenished and a new absolute deadline is set. 0539: * 0540: * When a task is queued before the begin of the next period, using the 0541: * remaining runtime and deadline could make the entity to overflow, see 0542: * dl_entity_overflow() to find more about runtime overflow. When such case 0543: * is detected, the runtime and deadline need to be updated. 0544: * 0545: * If the task has an implicit deadline, i.e., deadline == period, the Original 0546: * CBS is applied. the runtime is replenished and a new absolute deadline is 0547: * set, as in the previous cases. 0548: * 0549: * However, the Original CBS does not work properly for tasks with 0550: * deadline < period, which are said to have a constrained deadline. By 0551: * applying the Original CBS, a constrained deadline task would be able to run 0552: * runtime/deadline in a period. With deadline < period, the task would 0553: * overrun the runtime/period allowed bandwidth, breaking the admission test. 0554: * 0555: * In order to prevent this misbehave, the Revisited CBS is used for 0556: * constrained deadline tasks when a runtime overflow is detected. In the 0557: * Revisited CBS, rather than replenishing & setting a new absolute deadline, 0558: * the remaining runtime of the task is reduced to avoid runtime overflow. 0559: * Please refer to the comments update_dl_revised_wakeup() function to find 0560: * more about the Revised CBS rule. 0561: */ 0562: static void update_dl_entity(struct sched_dl_entity *dl_se, 0563: struct sched_dl_entity *pi_se) 0564: { 0565: struct dl_rq *dl_rq = dl_rq_of_se(dl_se); 0566: struct rq *rq = rq_of_dl_rq(dl_rq); 0567: 0568: /* 0569: * The arrival of a new instance needs special treatment, i.e., 0570: * the actual scheduling parameters have to be "renewed". 0571: */ 0572: if (dl_se->dl_new) { 0573: setup_new_dl_entity(dl_se, pi_se); 0574: return; 0575: } 0576: 0577: if (dl_time_before(dl_se->deadline, rq_clock(rq)) || 0578: dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) { 0579: 0580: if (unlikely(!dl_is_implicit(dl_se) && 0581: !dl_time_before(dl_se->deadline, rq_clock(rq)) && 0582: !dl_se->dl_boosted)){ 0583: update_dl_revised_wakeup(dl_se, rq); 0584: return; 0585: } 0586: 0587: dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline; 0588: dl_se->runtime = pi_se->dl_runtime; 0589: } 0590: } 0591: 0592: static inline u64 dl_next_period(struct sched_dl_entity *dl_se) 0593: { 0594: return dl_se->deadline - dl_se->dl_deadline + dl_se->dl_period; 0595: } 0596: 0597: /* 0598: * If the entity depleted all its runtime, and if we want it to sleep 0599: * while waiting for some new execution time to become available, we 0600: * set the bandwidth replenishment timer to the replenishment instant 0601: * and try to activate it. 0602: * 0603: * Notice that it is important for the caller to know if the timer 0604: * actually started or not (i.e., the replenishment instant is in 0605: * the future or in the past). 0606: */ 0607: static int start_dl_timer(struct task_struct *p) 0608: { 0609: struct sched_dl_entity *dl_se = &p->dl; 0610: struct hrtimer *timer = &dl_se->dl_timer; 0611: struct rq *rq = task_rq(p); 0612: ktime_t now, act; 0613: s64 delta; 0614: 0615: lockdep_assert_held(&rq->lock); 0616: 0617: /* 0618: * We want the timer to fire at the deadline, but considering 0619: * that it is actually coming from rq->clock and not from 0620: * hrtimer's time base reading. 0621: */ 0622: act = ns_to_ktime(dl_next_period(dl_se)); 0623: now = hrtimer_cb_get_time(timer); 0624: delta = ktime_to_ns(now) - rq_clock(rq); 0625: act = ktime_add_ns(act, delta); 0626: 0627: /* 0628: * If the expiry time already passed, e.g., because the value 0629: * chosen as the deadline is too small, don't even try to 0630: * start the timer in the past! 0631: */ 0632: if (ktime_us_delta(act, now) < 0) 0633: return 0; 0634: 0635: /* 0636: * !enqueued will guarantee another callback; even if one is already in 0637: * progress. This ensures a balanced {get,put}_task_struct(). 0638: * 0639: * The race against __run_timer() clearing the enqueued state is 0640: * harmless because we're holding task_rq()->lock, therefore the timer 0641: * expiring after we've done the check will wait on its task_rq_lock() 0642: * and observe our state. 0643: */ 0644: if (!hrtimer_is_queued(timer)) { 0645: get_task_struct(p); 0646: hrtimer_start(timer, act, HRTIMER_MODE_ABS); 0647: } 0648: 0649: return 1; 0650: } 0651: 0652: /* 0653: * This is the bandwidth enforcement timer callback. If here, we know 0654: * a task is not on its dl_rq, since the fact that the timer was running 0655: * means the task is throttled and needs a runtime replenishment. 0656: * 0657: * However, what we actually do depends on the fact the task is active, 0658: * (it is on its rq) or has been removed from there by a call to 0659: * dequeue_task_dl(). In the former case we must issue the runtime 0660: * replenishment and add the task back to the dl_rq; in the latter, we just 0661: * do nothing but clearing dl_throttled, so that runtime and deadline 0662: * updating (and the queueing back to dl_rq) will be done by the 0663: * next call to enqueue_task_dl(). 0664: */ 0665: static enum hrtimer_restart dl_task_timer(struct hrtimer *timer) 0666: { 0667: struct sched_dl_entity *dl_se = container_of(timer, 0668: struct sched_dl_entity, 0669: dl_timer); 0670: struct task_struct *p = dl_task_of(dl_se); 0671: unsigned long flags; 0672: struct rq *rq; 0673: 0674: rq = task_rq_lock(p, &flags); 0675: 0676: /* 0677: * The task might have changed its scheduling policy to something 0678: * different than SCHED_DEADLINE (through switched_fromd_dl()). 0679: */ 0680: if (!dl_task(p)) { 0681: __dl_clear_params(p); 0682: goto unlock; 0683: } 0684: 0685: /* 0686: * This is possible if switched_from_dl() raced against a running 0687: * callback that took the above !dl_task() path and we've since then 0688: * switched back into SCHED_DEADLINE. 0689: * 0690: * There's nothing to do except drop our task reference. 0691: */ 0692: if (dl_se->dl_new) 0693: goto unlock; 0694: 0695: /* 0696: * The task might have been boosted by someone else and might be in the 0697: * boosting/deboosting path, its not throttled. 0698: */ 0699: if (dl_se->dl_boosted) 0700: goto unlock; 0701: 0702: /* 0703: * Spurious timer due to start_dl_timer() race; or we already received 0704: * a replenishment from rt_mutex_setprio(). 0705: */ 0706: if (!dl_se->dl_throttled) 0707: goto unlock; 0708: 0709: sched_clock_tick(); 0710: update_rq_clock(rq); 0711: 0712: /* 0713: * If the throttle happened during sched-out; like: 0714: * 0715: * schedule() 0716: * deactivate_task() 0717: * dequeue_task_dl() 0718: * update_curr_dl() 0719: * start_dl_timer() 0720: * __dequeue_task_dl() 0721: * prev->on_rq = 0; 0722: * 0723: * We can be both throttled and !queued. Replenish the counter 0724: * but do not enqueue -- wait for our wakeup to do that. 0725: */ 0726: if (!task_on_rq_queued(p)) { 0727: replenish_dl_entity(dl_se, dl_se); 0728: goto unlock; 0729: } 0730: 0731: enqueue_task_dl(rq, p, ENQUEUE_REPLENISH); 0732: if (dl_task(rq->curr)) 0733: check_preempt_curr_dl(rq, p, 0); 0734: else 0735: resched_curr(rq); 0736: 0737: #ifdef CONFIG_SMP 0738: /* 0739: * Perform balancing operations here; after the replenishments. We 0740: * cannot drop rq->lock before this, otherwise the assertion in 0741: * start_dl_timer() about not missing updates is not true. 0742: * 0743: * If we find that the rq the task was on is no longer available, we 0744: * need to select a new rq. 0745: * 0746: * XXX figure out if select_task_rq_dl() deals with offline cpus. 0747: */ 0748: if (unlikely(!rq->online)) 0749: rq = dl_task_offline_migration(rq, p); 0750: 0751: /* 0752: * Queueing this task back might have overloaded rq, check if we need 0753: * to kick someone away. 0754: */ 0755: if (has_pushable_dl_tasks(rq)) { 0756: /* 0757: * Nothing relies on rq->lock after this, so its safe to drop 0758: * rq->lock. 0759: */ 0760: lockdep_unpin_lock(&rq->lock); 0761: push_dl_task(rq); 0762: lockdep_pin_lock(&rq->lock); 0763: } 0764: #endif 0765: 0766: unlock: 0767: task_rq_unlock(rq, p, &flags); 0768: 0769: /* 0770: * This can free the task_struct, including this hrtimer, do not touch 0771: * anything related to that after this. 0772: */ 0773: put_task_struct(p); 0774: 0775: return HRTIMER_NORESTART; 0776: } 0777: 0778: void init_dl_task_timer(struct sched_dl_entity *dl_se) 0779: { 0780: struct hrtimer *timer = &dl_se->dl_timer; 0781: 0782: hrtimer_init(timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL); 0783: timer->function = dl_task_timer; 0784: } 0785: 0786: /* 0787: * During the activation, CBS checks if it can reuse the current task's 0788: * runtime and period. If the deadline of the task is in the past, CBS 0789: * cannot use the runtime, and so it replenishes the task. This rule 0790: * works fine for implicit deadline tasks (deadline == period), and the 0791: * CBS was designed for implicit deadline tasks. However, a task with 0792: * constrained deadline (deadine < period) might be awakened after the 0793: * deadline, but before the next period. In this case, replenishing the 0794: * task would allow it to run for runtime / deadline. As in this case 0795: * deadline < period, CBS enables a task to run for more than the 0796: * runtime / period. In a very loaded system, this can cause a domino 0797: * effect, making other tasks miss their deadlines. 0798: * 0799: * To avoid this problem, in the activation of a constrained deadline 0800: * task after the deadline but before the next period, throttle the 0801: * task and set the replenishing timer to the begin of the next period, 0802: * unless it is boosted. 0803: */ 0804: static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se) 0805: { 0806: struct task_struct *p = dl_task_of(dl_se); 0807: struct rq *rq = rq_of_dl_rq(dl_rq_of_se(dl_se)); 0808: 0809: if (dl_time_before(dl_se->deadline, rq_clock(rq)) && 0810: dl_time_before(rq_clock(rq), dl_next_period(dl_se))) { 0811: if (unlikely(dl_se->dl_boosted || !start_dl_timer(p))) 0812: return; 0813: dl_se->dl_throttled = 1; 0814: if (dl_se->runtime > 0) 0815: dl_se->runtime = 0; 0816: } 0817: } 0818: 0819: static 0820: int dl_runtime_exceeded(struct sched_dl_entity *dl_se) 0821: { 0822: return (dl_se->runtime <= 0); 0823: } 0824: 0825: extern bool sched_rt_bandwidth_account(struct rt_rq *rt_rq); 0826: 0827: /* 0828: * Update the current task's runtime statistics (provided it is still 0829: * a -deadline task and has not been removed from the dl_rq). 0830: */ 0831: static void update_curr_dl(struct rq *rq) 0832: { 0833: struct task_struct *curr = rq->curr; 0834: struct sched_dl_entity *dl_se = &curr->dl; 0835: u64 delta_exec; 0836: 0837: if (!dl_task(curr) || !on_dl_rq(dl_se)) 0838: return; 0839: 0840: /* 0841: * Consumed budget is computed considering the time as 0842: * observed by schedulable tasks (excluding time spent 0843: * in hardirq context, etc.). Deadlines are instead 0844: * computed using hard walltime. This seems to be the more 0845: * natural solution, but the full ramifications of this 0846: * approach need further study. 0847: */ 0848: delta_exec = rq_clock_task(rq) - curr->se.exec_start; 0849: if (unlikely((s64)delta_exec <= 0)) 0850: return; 0851: 0852: schedstat_set(curr->se.statistics.exec_max, 0853: max(curr->se.statistics.exec_max, delta_exec)); 0854: 0855: curr->se.sum_exec_runtime += delta_exec; 0856: account_group_exec_runtime(curr, delta_exec); 0857: 0858: curr->se.exec_start = rq_clock_task(rq); 0859: cpuacct_charge(curr, delta_exec); 0860: 0861: sched_rt_avg_update(rq, delta_exec); 0862: 0863: dl_se->runtime -= dl_se->dl_yielded ? 0 : delta_exec; 0864: if (dl_runtime_exceeded(dl_se)) { 0865: dl_se->dl_throttled = 1; 0866: __dequeue_task_dl(rq, curr, 0); 0867: if (unlikely(dl_se->dl_boosted || !start_dl_timer(curr))) 0868: enqueue_task_dl(rq, curr, ENQUEUE_REPLENISH); 0869: 0870: if (!is_leftmost(curr, &rq->dl)) 0871: resched_curr(rq); 0872: } 0873: 0874: /* 0875: * Because -- for now -- we share the rt bandwidth, we need to 0876: * account our runtime there too, otherwise actual rt tasks 0877: * would be able to exceed the shared quota. 0878: * 0879: * Account to the root rt group for now. 0880: * 0881: * The solution we're working towards is having the RT groups scheduled 0882: * using deadline servers -- however there's a few nasties to figure 0883: * out before that can happen. 0884: */ 0885: if (rt_bandwidth_enabled()) { 0886: struct rt_rq *rt_rq = &rq->rt; 0887: 0888: raw_spin_lock(&rt_rq->rt_runtime_lock); 0889: /* 0890: * We'll let actual RT tasks worry about the overflow here, we 0891: * have our own CBS to keep us inline; only account when RT 0892: * bandwidth is relevant. 0893: */ 0894: if (sched_rt_bandwidth_account(rt_rq)) 0895: rt_rq->rt_time += delta_exec; 0896: raw_spin_unlock(&rt_rq->rt_runtime_lock); 0897: } 0898: } 0899: 0900: #ifdef CONFIG_SMP 0901: 0902: static struct task_struct *pick_next_earliest_dl_task(struct rq *rq, int cpu); 0903: 0904: static inline u64 next_deadline(struct rq *rq) 0905: { 0906: struct task_struct *next = pick_next_earliest_dl_task(rq, rq->cpu); 0907: 0908: if (next && dl_prio(next->prio)) 0909: return next->dl.deadline; 0910: else 0911: return 0; 0912: } 0913: 0914: static void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline) 0915: { 0916: struct rq *rq = rq_of_dl_rq(dl_rq); 0917: 0918: if (dl_rq->earliest_dl.curr == 0 || 0919: dl_time_before(deadline, dl_rq->earliest_dl.curr)) { 0920: /* 0921: * If the dl_rq had no -deadline tasks, or if the new task 0922: * has shorter deadline than the current one on dl_rq, we 0923: * know that the previous earliest becomes our next earliest, 0924: * as the new task becomes the earliest itself. 0925: */ 0926: dl_rq->earliest_dl.next = dl_rq->earliest_dl.curr; 0927: dl_rq->earliest_dl.curr = deadline; 0928: cpudl_set(&rq->rd->cpudl, rq->cpu, deadline, 1); 0929: } else if (dl_rq->earliest_dl.next == 0 || 0930: dl_time_before(deadline, dl_rq->earliest_dl.next)) { 0931: /* 0932: * On the other hand, if the new -deadline task has a 0933: * a later deadline than the earliest one on dl_rq, but 0934: * it is earlier than the next (if any), we must 0935: * recompute the next-earliest. 0936: */ 0937: dl_rq->earliest_dl.next = next_deadline(rq); 0938: } 0939: } 0940: 0941: static void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline) 0942: { 0943: struct rq *rq = rq_of_dl_rq(dl_rq); 0944: 0945: /* 0946: * Since we may have removed our earliest (and/or next earliest) 0947: * task we must recompute them. 0948: */ 0949: if (!dl_rq->dl_nr_running) { 0950: dl_rq->earliest_dl.curr = 0; 0951: dl_rq->earliest_dl.next = 0; 0952: cpudl_set(&rq->rd->cpudl, rq->cpu, 0, 0); 0953: } else { 0954: struct rb_node *leftmost = dl_rq->rb_leftmost; 0955: struct sched_dl_entity *entry; 0956: 0957: entry = rb_entry(leftmost, struct sched_dl_entity, rb_node); 0958: dl_rq->earliest_dl.curr = entry->deadline; 0959: dl_rq->earliest_dl.next = next_deadline(rq); 0960: cpudl_set(&rq->rd->cpudl, rq->cpu, entry->deadline, 1); 0961: } 0962: } 0963: 0964: #else 0965: 0966: static inline void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline) {} 0967: static inline void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline) {} 0968: 0969: #endif /* CONFIG_SMP */ 0970: 0971: static inline 0972: void inc_dl_tasks(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq) 0973: { 0974: int prio = dl_task_of(dl_se)->prio; 0975: u64 deadline = dl_se->deadline; 0976: 0977: WARN_ON(!dl_prio(prio)); 0978: dl_rq->dl_nr_running++; 0979: add_nr_running(rq_of_dl_rq(dl_rq), 1); 0980: 0981: inc_dl_deadline(dl_rq, deadline); 0982: inc_dl_migration(dl_se, dl_rq); 0983: } 0984: 0985: static inline 0986: void dec_dl_tasks(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq) 0987: { 0988: int prio = dl_task_of(dl_se)->prio; 0989: 0990: WARN_ON(!dl_prio(prio)); 0991: WARN_ON(!dl_rq->dl_nr_running); 0992: dl_rq->dl_nr_running--; 0993: sub_nr_running(rq_of_dl_rq(dl_rq), 1); 0994: 0995: dec_dl_deadline(dl_rq, dl_se->deadline); 0996: dec_dl_migration(dl_se, dl_rq); 0997: } 0998: 0999: static void __enqueue_dl_entity(struct sched_dl_entity *dl_se) 1000: { 1001: struct dl_rq *dl_rq = dl_rq_of_se(dl_se); 1002: struct rb_node **link = &dl_rq->rb_root.rb_node; 1003: struct rb_node *parent = NULL; 1004: struct sched_dl_entity *entry; 1005: int leftmost = 1; 1006: 1007: BUG_ON(!RB_EMPTY_NODE(&dl_se->rb_node)); 1008: 1009: while (*link) { 1010: parent = *link; 1011: entry = rb_entry(parent, struct sched_dl_entity, rb_node); 1012: if (dl_time_before(dl_se->deadline, entry->deadline)) 1013: link = &parent->rb_left; 1014: else { 1015: link = &parent->rb_right; 1016: leftmost = 0; 1017: } 1018: } 1019: 1020: if (leftmost) 1021: dl_rq->rb_leftmost = &dl_se->rb_node; 1022: 1023: rb_link_node(&dl_se->rb_node, parent, link); 1024: rb_insert_color(&dl_se->rb_node, &dl_rq->rb_root); 1025: 1026: inc_dl_tasks(dl_se, dl_rq); 1027: } 1028: 1029: static void __dequeue_dl_entity(struct sched_dl_entity *dl_se) 1030: { 1031: struct dl_rq *dl_rq = dl_rq_of_se(dl_se); 1032: 1033: if (RB_EMPTY_NODE(&dl_se->rb_node)) 1034: return; 1035: 1036: if (dl_rq->rb_leftmost == &dl_se->rb_node) { 1037: struct rb_node *next_node; 1038: 1039: next_node = rb_next(&dl_se->rb_node); 1040: dl_rq->rb_leftmost = next_node; 1041: } 1042: 1043: rb_erase(&dl_se->rb_node, &dl_rq->rb_root); 1044: RB_CLEAR_NODE(&dl_se->rb_node); 1045: 1046: dec_dl_tasks(dl_se, dl_rq); 1047: } 1048: 1049: static void 1050: enqueue_dl_entity(struct sched_dl_entity *dl_se, 1051: struct sched_dl_entity *pi_se, int flags) 1052: { 1053: BUG_ON(on_dl_rq(dl_se)); 1054: 1055: /* 1056: * If this is a wakeup or a new instance, the scheduling 1057: * parameters of the task might need updating. Otherwise, 1058: * we want a replenishment of its runtime. 1059: */ 1060: if (dl_se->dl_new || flags & ENQUEUE_WAKEUP) 1061: update_dl_entity(dl_se, pi_se); 1062: else if (flags & ENQUEUE_REPLENISH) 1063: replenish_dl_entity(dl_se, pi_se); 1064: 1065: __enqueue_dl_entity(dl_se); 1066: } 1067: 1068: static void dequeue_dl_entity(struct sched_dl_entity *dl_se) 1069: { 1070: __dequeue_dl_entity(dl_se); 1071: } 1072: 1073: static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags) 1074: { 1075: struct task_struct *pi_task = rt_mutex_get_top_task(p); 1076: struct sched_dl_entity *pi_se = &p->dl; 1077: 1078: /* 1079: * Use the scheduling parameters of the top pi-waiter 1080: * task if we have one and its (absolute) deadline is 1081: * smaller than our one... OTW we keep our runtime and 1082: * deadline. 1083: */ 1084: if (pi_task && p->dl.dl_boosted && dl_prio(pi_task->normal_prio)) { 1085: pi_se = &pi_task->dl; 1086: } else if (!dl_prio(p->normal_prio)) { 1087: /* 1088: * Special case in which we have a !SCHED_DEADLINE task 1089: * that is going to be deboosted, but exceedes its 1090: * runtime while doing so. No point in replenishing 1091: * it, as it's going to return back to its original 1092: * scheduling class after this. 1093: */ 1094: BUG_ON(!p->dl.dl_boosted || flags != ENQUEUE_REPLENISH); 1095: return; 1096: } 1097: 1098: /* 1099: * Check if a constrained deadline task was activated 1100: * after the deadline but before the next period. 1101: * If that is the case, the task will be throttled and 1102: * the replenishment timer will be set to the next period. 1103: */ 1104: if (!p->dl.dl_throttled && !dl_is_implicit(&p->dl)) 1105: dl_check_constrained_dl(&p->dl); 1106: 1107: /* 1108: * If p is throttled, we do nothing. In fact, if it exhausted 1109: * its budget it needs a replenishment and, since it now is on 1110: * its rq, the bandwidth timer callback (which clearly has not 1111: * run yet) will take care of this. 1112: */ 1113: if (p->dl.dl_throttled && !(flags & ENQUEUE_REPLENISH)) 1114: return; 1115: 1116: enqueue_dl_entity(&p->dl, pi_se, flags); 1117: 1118: if (!task_current(rq, p) && p->nr_cpus_allowed > 1) 1119: enqueue_pushable_dl_task(rq, p); 1120: } 1121: 1122: static void __dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags) 1123: { 1124: dequeue_dl_entity(&p->dl); 1125: dequeue_pushable_dl_task(rq, p); 1126: } 1127: 1128: static void dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags) 1129: { 1130: update_curr_dl(rq); 1131: __dequeue_task_dl(rq, p, flags); 1132: } 1133: 1134: /* 1135: * Yield task semantic for -deadline tasks is: 1136: * 1137: * get off from the CPU until our next instance, with 1138: * a new runtime. This is of little use now, since we 1139: * don't have a bandwidth reclaiming mechanism. Anyway, 1140: * bandwidth reclaiming is planned for the future, and 1141: * yield_task_dl will indicate that some spare budget 1142: * is available for other task instances to use it. 1143: */ 1144: static void yield_task_dl(struct rq *rq) 1145: { 1146: struct task_struct *p = rq->curr; 1147: 1148: /* 1149: * We make the task go to sleep until its current deadline by 1150: * forcing its runtime to zero. This way, update_curr_dl() stops 1151: * it and the bandwidth timer will wake it up and will give it 1152: * new scheduling parameters (thanks to dl_yielded=1). 1153: */ 1154: if (p->dl.runtime > 0) { 1155: rq->curr->dl.dl_yielded = 1; 1156: p->dl.runtime = 0; 1157: } 1158: update_rq_clock(rq); 1159: update_curr_dl(rq); 1160: /* 1161: * Tell update_rq_clock() that we've just updated, 1162: * so we don't do microscopic update in schedule() 1163: * and double the fastpath cost. 1164: */ 1165: rq_clock_skip_update(rq, true); 1166: } 1167: 1168: #ifdef CONFIG_SMP 1169: 1170: static int find_later_rq(struct task_struct *task); 1171: 1172: static int 1173: select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags) 1174: { 1175: struct task_struct *curr; 1176: struct rq *rq; 1177: 1178: if (sd_flag != SD_BALANCE_WAKE) 1179: goto out; 1180: 1181: rq = cpu_rq(cpu); 1182: 1183: rcu_read_lock(); 1184: curr = READ_ONCE(rq->curr); /* unlocked access */ 1185: 1186: /* 1187: * If we are dealing with a -deadline task, we must 1188: * decide where to wake it up. 1189: * If it has a later deadline and the current task 1190: * on this rq can't move (provided the waking task 1191: * can!) we prefer to send it somewhere else. On the 1192: * other hand, if it has a shorter deadline, we 1193: * try to make it stay here, it might be important. 1194: */ 1195: if (unlikely(dl_task(curr)) && 1196: (curr->nr_cpus_allowed < 2 || 1197: !dl_entity_preempt(&p->dl, &curr->dl)) && 1198: (p->nr_cpus_allowed > 1)) { 1199: int target = find_later_rq(p); 1200: 1201: if (target != -1 && 1202: (dl_time_before(p->dl.deadline, 1203: cpu_rq(target)->dl.earliest_dl.curr) || 1204: (cpu_rq(target)->dl.dl_nr_running == 0))) 1205: cpu = target; 1206: } 1207: rcu_read_unlock(); 1208: 1209: out: 1210: return cpu; 1211: } 1212: 1213: static void check_preempt_equal_dl(struct rq *rq, struct task_struct *p) 1214: { 1215: /* 1216: * Current can't be migrated, useless to reschedule, 1217: * let's hope p can move out. 1218: */ 1219: if (rq->curr->nr_cpus_allowed == 1 || 1220: cpudl_find(&rq->rd->cpudl, rq->curr, NULL) == -1) 1221: return; 1222: 1223: /* 1224: * p is migratable, so let's not schedule it and 1225: * see if it is pushed or pulled somewhere else. 1226: */ 1227: if (p->nr_cpus_allowed != 1 && 1228: cpudl_find(&rq->rd->cpudl, p, NULL) != -1) 1229: return; 1230: 1231: resched_curr(rq); 1232: } 1233: 1234: #endif /* CONFIG_SMP */ 1235: 1236: /* 1237: * Only called when both the current and waking task are -deadline 1238: * tasks. 1239: */ 1240: static void check_preempt_curr_dl(struct rq *rq, struct task_struct *p, 1241: int flags) 1242: { 1243: if (dl_entity_preempt(&p->dl, &rq->curr->dl)) { 1244: resched_curr(rq); 1245: return; 1246: } 1247: 1248: #ifdef CONFIG_SMP 1249: /* 1250: * In the unlikely case current and p have the same deadline 1251: * let us try to decide what's the best thing to do... 1252: */ 1253: if ((p->dl.deadline == rq->curr->dl.deadline) && 1254: !test_tsk_need_resched(rq->curr)) 1255: check_preempt_equal_dl(rq, p); 1256: #endif /* CONFIG_SMP */ 1257: } 1258: 1259: #ifdef CONFIG_SCHED_HRTICK 1260: static void start_hrtick_dl(struct rq *rq, struct task_struct *p) 1261: { 1262: hrtick_start(rq, p->dl.runtime); 1263: } 1264: #else /* !CONFIG_SCHED_HRTICK */ 1265: static void start_hrtick_dl(struct rq *rq, struct task_struct *p) 1266: { 1267: } 1268: #endif 1269: 1270: static struct sched_dl_entity *pick_next_dl_entity(struct rq *rq, 1271: struct dl_rq *dl_rq) 1272: { 1273: struct rb_node *left = dl_rq->rb_leftmost; 1274: 1275: if (!left) 1276: return NULL; 1277: 1278: return rb_entry(left, struct sched_dl_entity, rb_node); 1279: } 1280: 1281: struct task_struct *pick_next_task_dl(struct rq *rq, struct task_struct *prev) 1282: { 1283: struct sched_dl_entity *dl_se; 1284: struct task_struct *p; 1285: struct dl_rq *dl_rq; 1286: 1287: dl_rq = &rq->dl; 1288: 1289: if (need_pull_dl_task(rq, prev)) { 1290: /* 1291: * This is OK, because current is on_cpu, which avoids it being 1292: * picked for load-balance and preemption/IRQs are still 1293: * disabled avoiding further scheduler activity on it and we're 1294: * being very careful to re-start the picking loop. 1295: */ 1296: lockdep_unpin_lock(&rq->lock); 1297: pull_dl_task(rq); 1298: lockdep_pin_lock(&rq->lock); 1299: /* 1300: * pull_rt_task() can drop (and re-acquire) rq->lock; this 1301: * means a stop task can slip in, in which case we need to 1302: * re-start task selection. 1303: */ 1304: if (rq->stop && task_on_rq_queued(rq->stop)) 1305: return RETRY_TASK; 1306: } 1307: 1308: /* 1309: * When prev is DL, we may throttle it in put_prev_task(). 1310: * So, we update time before we check for dl_nr_running. 1311: */ 1312: if (prev->sched_class == &dl_sched_class) 1313: update_curr_dl(rq); 1314: 1315: if (unlikely(!dl_rq->dl_nr_running)) 1316: return NULL; 1317: 1318: put_prev_task(rq, prev); 1319: 1320: dl_se = pick_next_dl_entity(rq, dl_rq); 1321: BUG_ON(!dl_se); 1322: 1323: p = dl_task_of(dl_se); 1324: p->se.exec_start = rq_clock_task(rq); 1325: 1326: /* Running task will never be pushed. */ 1327: dequeue_pushable_dl_task(rq, p); 1328: 1329: if (hrtick_enabled(rq)) 1330: start_hrtick_dl(rq, p); 1331: 1332: queue_push_tasks(rq); 1333: 1334: return p; 1335: } 1336: 1337: static void put_prev_task_dl(struct rq *rq, struct task_struct *p) 1338: { 1339: update_curr_dl(rq); 1340: 1341: if (on_dl_rq(&p->dl) && p->nr_cpus_allowed > 1) 1342: enqueue_pushable_dl_task(rq, p); 1343: } 1344: 1345: static void task_tick_dl(struct rq *rq, struct task_struct *p, int queued) 1346: { 1347: update_curr_dl(rq); 1348: 1349: /* 1350: * Even when we have runtime, update_curr_dl() might have resulted in us 1351: * not being the leftmost task anymore. In that case NEED_RESCHED will 1352: * be set and schedule() will start a new hrtick for the next task. 1353: */ 1354: if (hrtick_enabled(rq) && queued && p->dl.runtime > 0 && 1355: is_leftmost(p, &rq->dl)) 1356: start_hrtick_dl(rq, p); 1357: } 1358: 1359: static void task_fork_dl(struct task_struct *p) 1360: { 1361: /* 1362: * SCHED_DEADLINE tasks cannot fork and this is achieved through 1363: * sched_fork() 1364: */ 1365: } 1366: 1367: static void task_dead_dl(struct task_struct *p) 1368: { 1369: struct dl_bw *dl_b = dl_bw_of(task_cpu(p)); 1370: 1371: /* 1372: * Since we are TASK_DEAD we won't slip out of the domain! 1373: */ 1374: raw_spin_lock_irq(&dl_b->lock); 1375: /* XXX we should retain the bw until 0-lag */ 1376: dl_b->total_bw -= p->dl.dl_bw; 1377: raw_spin_unlock_irq(&dl_b->lock); 1378: } 1379: 1380: static void set_curr_task_dl(struct rq *rq) 1381: { 1382: struct task_struct *p = rq->curr; 1383: 1384: p->se.exec_start = rq_clock_task(rq); 1385: 1386: /* You can't push away the running task */ 1387: dequeue_pushable_dl_task(rq, p); 1388: } 1389: 1390: #ifdef CONFIG_SMP 1391: 1392: /* Only try algorithms three times */ 1393: #define DL_MAX_TRIES 3 1394: 1395: static int pick_dl_task(struct rq *rq, struct task_struct *p, int cpu) 1396: { 1397: if (!task_running(rq, p) && 1398: cpumask_test_cpu(cpu, tsk_cpus_allowed(p))) 1399: return 1; 1400: return 0; 1401: } 1402: 1403: /* Returns the second earliest -deadline task, NULL otherwise */ 1404: static struct task_struct *pick_next_earliest_dl_task(struct rq *rq, int cpu) 1405: { 1406: struct rb_node *next_node = rq->dl.rb_leftmost; 1407: struct sched_dl_entity *dl_se; 1408: struct task_struct *p = NULL; 1409: 1410: next_node: 1411: next_node = rb_next(next_node); 1412: if (next_node) { 1413: dl_se = rb_entry(next_node, struct sched_dl_entity, rb_node); 1414: p = dl_task_of(dl_se); 1415: 1416: if (pick_dl_task(rq, p, cpu)) 1417: return p; 1418: 1419: goto next_node; 1420: } 1421: 1422: return NULL; 1423: } 1424: 1425: /* 1426: * Return the earliest pushable rq's task, which is suitable to be executed 1427: * on the CPU, NULL otherwise: 1428: */ 1429: static struct task_struct *pick_earliest_pushable_dl_task(struct rq *rq, int cpu) 1430: { 1431: struct rb_node *next_node = rq->dl.pushable_dl_tasks_leftmost; 1432: struct task_struct *p = NULL; 1433: 1434: if (!has_pushable_dl_tasks(rq)) 1435: return NULL; 1436: 1437: next_node: 1438: if (next_node) { 1439: p = rb_entry(next_node, struct task_struct, pushable_dl_tasks); 1440: 1441: if (pick_dl_task(rq, p, cpu)) 1442: return p; 1443: 1444: next_node = rb_next(next_node); 1445: goto next_node; 1446: } 1447: 1448: return NULL; 1449: } 1450: 1451: static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask_dl); 1452: 1453: static int find_later_rq(struct task_struct *task) 1454: { 1455: struct sched_domain *sd; 1456: struct cpumask *later_mask = this_cpu_cpumask_var_ptr(local_cpu_mask_dl); 1457: int this_cpu = smp_processor_id(); 1458: int best_cpu, cpu = task_cpu(task); 1459: 1460: /* Make sure the mask is initialized first */ 1461: if (unlikely(!later_mask)) 1462: return -1; 1463: 1464: if (task->nr_cpus_allowed == 1) 1465: return -1; 1466: 1467: /* 1468: * We have to consider system topology and task affinity 1469: * first, then we can look for a suitable cpu. 1470: */ 1471: best_cpu = cpudl_find(&task_rq(task)->rd->cpudl, 1472: task, later_mask); 1473: if (best_cpu == -1) 1474: return -1; 1475: 1476: /* 1477: * If we are here, some target has been found, 1478: * the most suitable of which is cached in best_cpu. 1479: * This is, among the runqueues where the current tasks 1480: * have later deadlines than the task's one, the rq 1481: * with the latest possible one. 1482: * 1483: * Now we check how well this matches with task's 1484: * affinity and system topology. 1485: * 1486: * The last cpu where the task run is our first 1487: * guess, since it is most likely cache-hot there. 1488: */ 1489: if (cpumask_test_cpu(cpu, later_mask)) 1490: return cpu; 1491: /* 1492: * Check if this_cpu is to be skipped (i.e., it is 1493: * not in the mask) or not. 1494: */ 1495: if (!cpumask_test_cpu(this_cpu, later_mask)) 1496: this_cpu = -1; 1497: 1498: rcu_read_lock(); 1499: for_each_domain(cpu, sd) { 1500: if (sd->flags & SD_WAKE_AFFINE) { 1501: 1502: /* 1503: * If possible, preempting this_cpu is 1504: * cheaper than migrating. 1505: */ 1506: if (this_cpu != -1 && 1507: cpumask_test_cpu(this_cpu, sched_domain_span(sd))) { 1508: rcu_read_unlock(); 1509: return this_cpu; 1510: } 1511: 1512: /* 1513: * Last chance: if best_cpu is valid and is 1514: * in the mask, that becomes our choice. 1515: */ 1516: if (best_cpu < nr_cpu_ids && 1517: cpumask_test_cpu(best_cpu, sched_domain_span(sd))) { 1518: rcu_read_unlock(); 1519: return best_cpu; 1520: } 1521: } 1522: } 1523: rcu_read_unlock(); 1524: 1525: /* 1526: * At this point, all our guesses failed, we just return 1527: * 'something', and let the caller sort the things out. 1528: */ 1529: if (this_cpu != -1) 1530: return this_cpu; 1531: 1532: cpu = cpumask_any(later_mask); 1533: if (cpu < nr_cpu_ids) 1534: return cpu; 1535: 1536: return -1; 1537: } 1538: 1539: /* Locks the rq it finds */ 1540: static struct rq *find_lock_later_rq(struct task_struct *task, struct rq *rq) 1541: { 1542: struct rq *later_rq = NULL; 1543: int tries; 1544: int cpu; 1545: 1546: for (tries = 0; tries < DL_MAX_TRIES; tries++) { 1547: cpu = find_later_rq(task); 1548: 1549: if ((cpu == -1) || (cpu == rq->cpu)) 1550: break; 1551: 1552: later_rq = cpu_rq(cpu); 1553: 1554: if (later_rq->dl.dl_nr_running && 1555: !dl_time_before(task->dl.deadline, 1556: later_rq->dl.earliest_dl.curr)) { 1557: /* 1558: * Target rq has tasks of equal or earlier deadline, 1559: * retrying does not release any lock and is unlikely 1560: * to yield a different result. 1561: */ 1562: later_rq = NULL; 1563: break; 1564: } 1565: 1566: /* Retry if something changed. */ 1567: if (double_lock_balance(rq, later_rq)) { 1568: if (unlikely(task_rq(task) != rq || 1569: !cpumask_test_cpu(later_rq->cpu, 1570: &task->cpus_allowed) || 1571: task_running(rq, task) || 1572: !task_on_rq_queued(task))) { 1573: double_unlock_balance(rq, later_rq); 1574: later_rq = NULL; 1575: break; 1576: } 1577: } 1578: 1579: /* 1580: * If the rq we found has no -deadline task, or 1581: * its earliest one has a later deadline than our 1582: * task, the rq is a good one. 1583: */ 1584: if (!later_rq->dl.dl_nr_running || 1585: dl_time_before(task->dl.deadline, 1586: later_rq->dl.earliest_dl.curr)) 1587: break; 1588: 1589: /* Otherwise we try again. */ 1590: double_unlock_balance(rq, later_rq); 1591: later_rq = NULL; 1592: } 1593: 1594: return later_rq; 1595: } 1596: 1597: static struct task_struct *pick_next_pushable_dl_task(struct rq *rq) 1598: { 1599: struct task_struct *p; 1600: 1601: if (!has_pushable_dl_tasks(rq)) 1602: return NULL; 1603: 1604: p = rb_entry(rq->dl.pushable_dl_tasks_leftmost, 1605: struct task_struct, pushable_dl_tasks); 1606: 1607: BUG_ON(rq->cpu != task_cpu(p)); 1608: BUG_ON(task_current(rq, p)); 1609: BUG_ON(p->nr_cpus_allowed <= 1); 1610: 1611: BUG_ON(!task_on_rq_queued(p)); 1612: BUG_ON(!dl_task(p)); 1613: 1614: return p; 1615: } 1616: 1617: /* 1618: * See if the non running -deadline tasks on this rq 1619: * can be sent to some other CPU where they can preempt 1620: * and start executing. 1621: */ 1622: static int push_dl_task(struct rq *rq) 1623: { 1624: struct task_struct *next_task; 1625: struct rq *later_rq; 1626: int ret = 0; 1627: 1628: if (!rq->dl.overloaded) 1629: return 0; 1630: 1631: next_task = pick_next_pushable_dl_task(rq); 1632: if (!next_task) 1633: return 0; 1634: 1635: retry: 1636: if (unlikely(next_task == rq->curr)) { 1637: WARN_ON(1); 1638: return 0; 1639: } 1640: 1641: /* 1642: * If next_task preempts rq->curr, and rq->curr 1643: * can move away, it makes sense to just reschedule 1644: * without going further in pushing next_task. 1645: */ 1646: if (dl_task(rq->curr) && 1647: dl_time_before(next_task->dl.deadline, rq->curr->dl.deadline) && 1648: rq->curr->nr_cpus_allowed > 1) { 1649: resched_curr(rq); 1650: return 0; 1651: } 1652: 1653: /* We might release rq lock */ 1654: get_task_struct(next_task); 1655: 1656: /* Will lock the rq it'll find */ 1657: later_rq = find_lock_later_rq(next_task, rq); 1658: if (!later_rq) { 1659: struct task_struct *task; 1660: 1661: /* 1662: * We must check all this again, since 1663: * find_lock_later_rq releases rq->lock and it is 1664: * then possible that next_task has migrated. 1665: */ 1666: task = pick_next_pushable_dl_task(rq); 1667: if (task_cpu(next_task) == rq->cpu && task == next_task) { 1668: /* 1669: * The task is still there. We don't try 1670: * again, some other cpu will pull it when ready. 1671: */ 1672: goto out; 1673: } 1674: 1675: if (!task) 1676: /* No more tasks */ 1677: goto out; 1678: 1679: put_task_struct(next_task); 1680: next_task = task; 1681: goto retry; 1682: } 1683: 1684: deactivate_task(rq, next_task, 0); 1685: set_task_cpu(next_task, later_rq->cpu); 1686: activate_task(later_rq, next_task, 0); 1687: ret = 1; 1688: 1689: resched_curr(later_rq); 1690: 1691: double_unlock_balance(rq, later_rq); 1692: 1693: out: 1694: put_task_struct(next_task); 1695: 1696: return ret; 1697: } 1698: 1699: static void push_dl_tasks(struct rq *rq) 1700: { 1701: /* push_dl_task() will return true if it moved a -deadline task */ 1702: while (push_dl_task(rq)) 1703: ; 1704: } 1705: 1706: static void pull_dl_task(struct rq *this_rq) 1707: { 1708: int this_cpu = this_rq->cpu, cpu; 1709: struct task_struct *p; 1710: bool resched = false; 1711: struct rq *src_rq; 1712: u64 dmin = LONG_MAX; 1713: 1714: if (likely(!dl_overloaded(this_rq))) 1715: return; 1716: 1717: /* 1718: * Match the barrier from dl_set_overloaded; this guarantees that if we 1719: * see overloaded we must also see the dlo_mask bit. 1720: */ 1721: smp_rmb(); 1722: 1723: for_each_cpu(cpu, this_rq->rd->dlo_mask) { 1724: if (this_cpu == cpu) 1725: continue; 1726: 1727: src_rq = cpu_rq(cpu); 1728: 1729: /* 1730: * It looks racy, abd it is! However, as in sched_rt.c, 1731: * we are fine with this. 1732: */ 1733: if (this_rq->dl.dl_nr_running && 1734: dl_time_before(this_rq->dl.earliest_dl.curr, 1735: src_rq->dl.earliest_dl.next)) 1736: continue; 1737: 1738: /* Might drop this_rq->lock */ 1739: double_lock_balance(this_rq, src_rq); 1740: 1741: /* 1742: * If there are no more pullable tasks on the 1743: * rq, we're done with it. 1744: */ 1745: if (src_rq->dl.dl_nr_running <= 1) 1746: goto skip; 1747: 1748: p = pick_earliest_pushable_dl_task(src_rq, this_cpu); 1749: 1750: /* 1751: * We found a task to be pulled if: 1752: * - it preempts our current (if there's one), 1753: * - it will preempt the last one we pulled (if any). 1754: */ 1755: if (p && dl_time_before(p->dl.deadline, dmin) && 1756: (!this_rq->dl.dl_nr_running || 1757: dl_time_before(p->dl.deadline, 1758: this_rq->dl.earliest_dl.curr))) { 1759: WARN_ON(p == src_rq->curr); 1760: WARN_ON(!task_on_rq_queued(p)); 1761: 1762: /* 1763: * Then we pull iff p has actually an earlier 1764: * deadline than the current task of its runqueue. 1765: */ 1766: if (dl_time_before(p->dl.deadline, 1767: src_rq->curr->dl.deadline)) 1768: goto skip; 1769: 1770: resched = true; 1771: 1772: deactivate_task(src_rq, p, 0); 1773: set_task_cpu(p, this_cpu); 1774: activate_task(this_rq, p, 0); 1775: dmin = p->dl.deadline; 1776: 1777: /* Is there any other task even earlier? */ 1778: } 1779: skip: 1780: double_unlock_balance(this_rq, src_rq); 1781: } 1782: 1783: if (resched) 1784: resched_curr(this_rq); 1785: } 1786: 1787: /* 1788: * Since the task is not running and a reschedule is not going to happen 1789: * anytime soon on its runqueue, we try pushing it away now. 1790: */ 1791: static void task_woken_dl(struct rq *rq, struct task_struct *p) 1792: { 1793: if (!task_running(rq, p) && 1794: !test_tsk_need_resched(rq->curr) && 1795: p->nr_cpus_allowed > 1 && 1796: dl_task(rq->curr) && 1797: (rq->curr->nr_cpus_allowed < 2 || 1798: !dl_entity_preempt(&p->dl, &rq->curr->dl))) { 1799: push_dl_tasks(rq); 1800: } 1801: } 1802: 1803: static void set_cpus_allowed_dl(struct task_struct *p, 1804: const struct cpumask *new_mask) 1805: { 1806: struct root_domain *src_rd; 1807: struct rq *rq; 1808: 1809: BUG_ON(!dl_task(p)); 1810: 1811: rq = task_rq(p); 1812: src_rd = rq->rd; 1813: /* 1814: * Migrating a SCHED_DEADLINE task between exclusive 1815: * cpusets (different root_domains) entails a bandwidth 1816: * update. We already made space for us in the destination 1817: * domain (see cpuset_can_attach()). 1818: */ 1819: if (!cpumask_intersects(src_rd->span, new_mask)) { 1820: struct dl_bw *src_dl_b; 1821: 1822: src_dl_b = dl_bw_of(cpu_of(rq)); 1823: /* 1824: * We now free resources of the root_domain we are migrating 1825: * off. In the worst case, sched_setattr() may temporary fail 1826: * until we complete the update. 1827: */ 1828: raw_spin_lock(&src_dl_b->lock); 1829: __dl_clear(src_dl_b, p->dl.dl_bw); 1830: raw_spin_unlock(&src_dl_b->lock); 1831: } 1832: 1833: set_cpus_allowed_common(p, new_mask); 1834: } 1835: 1836: /* Assumes rq->lock is held */ 1837: static void rq_online_dl(struct rq *rq) 1838: { 1839: if (rq->dl.overloaded) 1840: dl_set_overload(rq); 1841: 1842: cpudl_set_freecpu(&rq->rd->cpudl, rq->cpu); 1843: if (rq->dl.dl_nr_running > 0) 1844: cpudl_set(&rq->rd->cpudl, rq->cpu, rq->dl.earliest_dl.curr, 1); 1845: } 1846: 1847: /* Assumes rq->lock is held */ 1848: static void rq_offline_dl(struct rq *rq) 1849: { 1850: if (rq->dl.overloaded) 1851: dl_clear_overload(rq); 1852: 1853: cpudl_set(&rq->rd->cpudl, rq->cpu, 0, 0); 1854: cpudl_clear_freecpu(&rq->rd->cpudl, rq->cpu); 1855: } 1856: 1857: void __init init_sched_dl_class(void) 1858: { 1859: unsigned int i; 1860: 1861: for_each_possible_cpu(i) 1862: zalloc_cpumask_var_node(&per_cpu(local_cpu_mask_dl, i), 1863: GFP_KERNEL, cpu_to_node(i)); 1864: } 1865: 1866: #endif /* CONFIG_SMP */ 1867: 1868: static void switched_from_dl(struct rq *rq, struct task_struct *p) 1869: { 1870: /* 1871: * Start the deadline timer; if we switch back to dl before this we'll 1872: * continue consuming our current CBS slice. If we stay outside of 1873: * SCHED_DEADLINE until the deadline passes, the timer will reset the 1874: * task. 1875: */ 1876: if (!start_dl_timer(p)) 1877: __dl_clear_params(p); 1878: 1879: /* 1880: * Since this might be the only -deadline task on the rq, 1881: * this is the right place to try to pull some other one 1882: * from an overloaded cpu, if any. 1883: */ 1884: if (!task_on_rq_queued(p) || rq->dl.dl_nr_running) 1885: return; 1886: 1887: queue_pull_task(rq); 1888: } 1889: 1890: /* 1891: * When switching to -deadline, we may overload the rq, then 1892: * we try to push someone off, if possible. 1893: */ 1894: static void switched_to_dl(struct rq *rq, struct task_struct *p) 1895: { 1896: if (task_on_rq_queued(p) && rq->curr != p) { 1897: #ifdef CONFIG_SMP 1898: if (p->nr_cpus_allowed > 1 && rq->dl.overloaded) 1899: queue_push_tasks(rq); 1900: #endif 1901: if (dl_task(rq->curr)) 1902: check_preempt_curr_dl(rq, p, 0); 1903: else 1904: resched_curr(rq); 1905: } 1906: } 1907: 1908: /* 1909: * If the scheduling parameters of a -deadline task changed, 1910: * a push or pull operation might be needed. 1911: */ 1912: static void prio_changed_dl(struct rq *rq, struct task_struct *p, 1913: int oldprio) 1914: { 1915: if (task_on_rq_queued(p) || rq->curr == p) { 1916: #ifdef CONFIG_SMP 1917: /* 1918: * This might be too much, but unfortunately 1919: * we don't have the old deadline value, and 1920: * we can't argue if the task is increasing 1921: * or lowering its prio, so... 1922: */ 1923: if (!rq->dl.overloaded) 1924: queue_pull_task(rq); 1925: 1926: /* 1927: * If we now have a earlier deadline task than p, 1928: * then reschedule, provided p is still on this 1929: * runqueue. 1930: */ 1931: if (dl_time_before(rq->dl.earliest_dl.curr, p->dl.deadline)) 1932: resched_curr(rq); 1933: #else 1934: /* 1935: * Again, we don't know if p has a earlier 1936: * or later deadline, so let's blindly set a 1937: * (maybe not needed) rescheduling point. 1938: */ 1939: resched_curr(rq); 1940: #endif /* CONFIG_SMP */ 1941: } else 1942: switched_to_dl(rq, p); 1943: } 1944: 1945: const struct sched_class dl_sched_class = { 1946: .next = &rt_sched_class, 1947: .enqueue_task = enqueue_task_dl, 1948: .dequeue_task = dequeue_task_dl, 1949: .yield_task = yield_task_dl, 1950: 1951: .check_preempt_curr = check_preempt_curr_dl, 1952: 1953: .pick_next_task = pick_next_task_dl, 1954: .put_prev_task = put_prev_task_dl, 1955: 1956: #ifdef CONFIG_SMP 1957: .select_task_rq = select_task_rq_dl, 1958: .set_cpus_allowed = set_cpus_allowed_dl, 1959: .rq_online = rq_online_dl, 1960: .rq_offline = rq_offline_dl, 1961: .task_woken = task_woken_dl, 1962: #endif 1963: 1964: .set_curr_task = set_curr_task_dl, 1965: .task_tick = task_tick_dl, 1966: .task_fork = task_fork_dl, 1967: .task_dead = task_dead_dl, 1968: 1969: .prio_changed = prio_changed_dl, 1970: .switched_from = switched_from_dl, 1971: .switched_to = switched_to_dl, 1972: 1973: .update_curr = update_curr_dl, 1974: }; 1975: 1976: #ifdef CONFIG_SCHED_DEBUG 1977: extern void print_dl_rq(struct seq_file *m, int cpu, struct dl_rq *dl_rq); 1978: 1979: void print_dl_stats(struct seq_file *m, int cpu) 1980: { 1981: print_dl_rq(m, cpu, &cpu_rq(cpu)->dl); 1982: } 1983: #endif /* CONFIG_SCHED_DEBUG */