1 // SPDX-License-Identifier: MIT 2 /* Copyright 2015 Advanced Micro Devices, Inc. */ 3 /* Copyright (c) 2025 Valve Corporation */ 4 5 #include <linux/rbtree.h> 6 7 #include <drm/drm_print.h> 8 #include <drm/gpu_scheduler.h> 9 10 #include "sched_internal.h" 11 12 static __always_inline bool 13 drm_sched_entity_compare_before(struct rb_node *a, const struct rb_node *b) 14 { 15 struct drm_sched_entity *ea = 16 rb_entry((a), struct drm_sched_entity, rb_tree_node); 17 struct drm_sched_entity *eb = 18 rb_entry((b), struct drm_sched_entity, rb_tree_node); 19 20 return ktime_before(ea->oldest_job_waiting, eb->oldest_job_waiting); 21 } 22 23 static void drm_sched_rq_update_prio(struct drm_sched_rq *rq) 24 { 25 enum drm_sched_priority prio = DRM_SCHED_PRIORITY_INVALID; 26 struct rb_node *rb; 27 28 lockdep_assert_held(&rq->lock); 29 30 rb = rb_first_cached(&rq->rb_tree_root); 31 if (rb) { 32 struct drm_sched_entity *entity = 33 rb_entry(rb, typeof(*entity), rb_tree_node); 34 35 /* 36 * The normal locking order is entity then run-queue so taking 37 * the entity lock here would be a locking inversion for the 38 * case when the current head of the run-queue is different from 39 * the one we already have locked. The unlocked read is fine 40 * though, because if the priority had just changed it is no big 41 * deal for our algorithm, but just a transient reachable only 42 * by drivers with userspace dynamic priority changes API. Equal 43 * in effect to the priority change becoming visible a few 44 * instructions later. 45 */ 46 prio = READ_ONCE(entity->priority); 47 } 48 49 rq->head_prio = prio; 50 } 51 52 static void drm_sched_rq_remove_fifo_locked(struct drm_sched_entity *entity, 53 struct drm_sched_rq *rq) 54 { 55 lockdep_assert_held(&entity->lock); 56 lockdep_assert_held(&rq->lock); 57 58 if (!RB_EMPTY_NODE(&entity->rb_tree_node)) { 59 rb_erase_cached(&entity->rb_tree_node, &rq->rb_tree_root); 60 RB_CLEAR_NODE(&entity->rb_tree_node); 61 drm_sched_rq_update_prio(rq); 62 } 63 } 64 65 static void drm_sched_rq_update_fifo_locked(struct drm_sched_entity *entity, 66 struct drm_sched_rq *rq, 67 ktime_t ts) 68 { 69 /* 70 * Both locks need to be grabbed, one to protect from entity->rq change 71 * for entity from within concurrent drm_sched_entity_select_rq and the 72 * other to update the rb tree structure. 73 */ 74 lockdep_assert_held(&entity->lock); 75 lockdep_assert_held(&rq->lock); 76 77 drm_sched_rq_remove_fifo_locked(entity, rq); 78 79 entity->oldest_job_waiting = ts; 80 81 rb_add_cached(&entity->rb_tree_node, &rq->rb_tree_root, 82 drm_sched_entity_compare_before); 83 drm_sched_rq_update_prio(rq); 84 } 85 86 /** 87 * drm_sched_rq_init - initialize a given run queue struct 88 * @sched: scheduler instance to associate with this run queue 89 * @rq: scheduler run queue 90 * 91 * Initializes a scheduler runqueue. 92 */ 93 void drm_sched_rq_init(struct drm_gpu_scheduler *sched, 94 struct drm_sched_rq *rq) 95 { 96 spin_lock_init(&rq->lock); 97 INIT_LIST_HEAD(&rq->entities); 98 rq->rb_tree_root = RB_ROOT_CACHED; 99 rq->sched = sched; 100 rq->head_prio = DRM_SCHED_PRIORITY_INVALID; 101 } 102 103 /* 104 * Core part of the CFS-like algorithm is that the virtual runtime of lower 105 * priority tasks should grow quicker than the higher priority ones, so that 106 * when we then schedule entities with the aim of keeping their accumulated 107 * virtual time balanced, we can approach fair distribution of GPU time. 108 * 109 * For converting the real GPU time into virtual we pick some multipliers with 110 * the idea to achieve the following GPU time distribution: 111 * 112 * - Kernel priority gets roughly 2x GPU time compared to high. 113 * - High gets ~4x relative to normal. 114 * - Normal gets ~8x relative to low. 115 */ 116 static const unsigned int vruntime_shift[] = { 117 [DRM_SCHED_PRIORITY_KERNEL] = 1, 118 [DRM_SCHED_PRIORITY_HIGH] = 2, 119 [DRM_SCHED_PRIORITY_NORMAL] = 4, 120 [DRM_SCHED_PRIORITY_LOW] = 7, 121 }; 122 123 static ktime_t 124 drm_sched_rq_get_min_vruntime(struct drm_sched_rq *rq) 125 { 126 ktime_t vruntime = 0; 127 struct rb_node *rb; 128 129 lockdep_assert_held(&rq->lock); 130 131 rb = rb_first_cached(&rq->rb_tree_root); 132 if (rb) { 133 struct drm_sched_entity *entity = 134 rb_entry(rb, typeof(*entity), rb_tree_node); 135 struct drm_sched_entity_stats *stats = entity->stats; 136 137 spin_lock(&stats->lock); 138 vruntime = stats->vruntime; 139 spin_unlock(&stats->lock); 140 } 141 142 return vruntime; 143 } 144 145 static void 146 drm_sched_entity_save_vruntime(struct drm_sched_entity *entity, 147 ktime_t min_vruntime) 148 { 149 struct drm_sched_entity_stats *stats = entity->stats; 150 ktime_t vruntime; 151 152 spin_lock(&stats->lock); 153 vruntime = stats->vruntime; 154 if (min_vruntime && vruntime > min_vruntime) 155 vruntime = ktime_sub(vruntime, min_vruntime); 156 else 157 vruntime = 0; 158 stats->vruntime = vruntime; 159 spin_unlock(&stats->lock); 160 } 161 162 static ktime_t 163 drm_sched_entity_restore_vruntime(struct drm_sched_entity *entity, 164 ktime_t min_vruntime, 165 enum drm_sched_priority rq_prio) 166 { 167 struct drm_sched_entity_stats *stats = entity->stats; 168 struct drm_gpu_scheduler *sched = entity->rq->sched; 169 enum drm_sched_priority prio = entity->priority; 170 unsigned long avg_us, sched_avg_us; 171 ktime_t vruntime; 172 173 BUILD_BUG_ON(DRM_SCHED_PRIORITY_NORMAL < DRM_SCHED_PRIORITY_HIGH); 174 175 spin_lock(&stats->lock); 176 vruntime = stats->vruntime; 177 avg_us = ewma_drm_sched_avgtime_read(&stats->avg_job_us); 178 /* 179 * Unlocked read of the scheduler average is fine since it is just 180 * heuristics and data type is a natural word size. 181 */ 182 sched_avg_us = ewma_drm_sched_avgtime_read(&sched->avg_job_us); 183 184 /* 185 * Special handling for entities which were picked from the top of the 186 * queue and are now re-joining the top with another one already there. 187 */ 188 if (!vruntime && rq_prio != DRM_SCHED_PRIORITY_INVALID) { 189 if (prio > rq_prio) { 190 /* 191 * Lower priority should not overtake higher when re- 192 * joining at the top of the queue so push it back 193 * somewhere behind the "middle" of the run-queue, 194 * proportional to the scheduler and entity average job 195 * durations. 196 */ 197 vruntime = us_to_ktime((1 + avg_us + sched_avg_us) << 198 vruntime_shift[prio]); 199 } else if (prio < rq_prio) { 200 /* 201 * Higher priority can go first. 202 */ 203 vruntime = -ns_to_ktime(rq_prio - prio); 204 } else { 205 /* Favour entity with shorter jobs (interactivity). */ 206 if (avg_us <= sched_avg_us) 207 vruntime = -ns_to_ktime(1); 208 else 209 vruntime = ns_to_ktime(1); 210 } 211 } 212 213 /* 214 * Restore saved relative position in the queue. 215 */ 216 vruntime = ktime_add(min_vruntime, vruntime); 217 218 stats->vruntime = vruntime; 219 spin_unlock(&stats->lock); 220 221 return vruntime; 222 } 223 224 static ktime_t drm_sched_entity_update_vruntime(struct drm_sched_entity *entity) 225 { 226 struct drm_sched_entity_stats *stats = entity->stats; 227 ktime_t runtime, prev; 228 229 spin_lock(&stats->lock); 230 prev = stats->prev_runtime; 231 runtime = stats->runtime; 232 stats->prev_runtime = runtime; 233 runtime = ktime_add_ns(stats->vruntime, 234 ktime_to_ns(ktime_sub(runtime, prev)) << 235 vruntime_shift[entity->priority]); 236 stats->vruntime = runtime; 237 spin_unlock(&stats->lock); 238 239 return runtime; 240 } 241 242 static ktime_t drm_sched_entity_get_job_ts(struct drm_sched_entity *entity) 243 { 244 return drm_sched_entity_update_vruntime(entity); 245 } 246 247 /** 248 * drm_sched_rq_add_entity - add an entity 249 * @entity: scheduler entity 250 * @ts: submission timestamp 251 * 252 * Adds a scheduler entity to the run queue. 253 * 254 * Return: DRM scheduler selected to handle this entity or NULL if entity has 255 * been stopped and cannot be submitted to. 256 */ 257 struct drm_gpu_scheduler * 258 drm_sched_rq_add_entity(struct drm_sched_entity *entity, ktime_t ts) 259 { 260 struct drm_gpu_scheduler *sched; 261 struct drm_sched_rq *rq; 262 263 /* Add the entity to the run queue */ 264 spin_lock(&entity->lock); 265 if (entity->stopped) { 266 spin_unlock(&entity->lock); 267 268 DRM_ERROR("Trying to push to a killed entity\n"); 269 return NULL; 270 } 271 272 rq = entity->rq; 273 spin_lock(&rq->lock); 274 sched = rq->sched; 275 276 if (list_empty(&entity->list)) { 277 atomic_inc(sched->score); 278 list_add_tail(&entity->list, &rq->entities); 279 } 280 281 if (drm_sched_policy == DRM_SCHED_POLICY_FAIR) { 282 ts = drm_sched_rq_get_min_vruntime(rq); 283 ts = drm_sched_entity_restore_vruntime(entity, ts, 284 rq->head_prio); 285 } else if (drm_sched_policy == DRM_SCHED_POLICY_RR) { 286 ts = entity->rr_ts; 287 } 288 289 drm_sched_rq_update_fifo_locked(entity, rq, ts); 290 291 spin_unlock(&rq->lock); 292 spin_unlock(&entity->lock); 293 294 return sched; 295 } 296 297 /** 298 * drm_sched_rq_remove_entity - remove an entity 299 * @rq: scheduler run queue 300 * @entity: scheduler entity 301 * 302 * Removes a scheduler entity from the run queue. 303 */ 304 void drm_sched_rq_remove_entity(struct drm_sched_rq *rq, 305 struct drm_sched_entity *entity) 306 { 307 lockdep_assert_held(&entity->lock); 308 309 if (list_empty(&entity->list)) 310 return; 311 312 spin_lock(&rq->lock); 313 314 atomic_dec(rq->sched->score); 315 list_del_init(&entity->list); 316 317 drm_sched_rq_remove_fifo_locked(entity, rq); 318 319 spin_unlock(&rq->lock); 320 } 321 322 static ktime_t 323 drm_sched_rq_next_rr_ts(struct drm_sched_rq *rq, 324 struct drm_sched_entity *entity) 325 { 326 ktime_t ts; 327 328 lockdep_assert_held(&entity->lock); 329 lockdep_assert_held(&rq->lock); 330 331 ts = ktime_add_ns(rq->rr_ts, 1); 332 entity->rr_ts = ts; 333 rq->rr_ts = ts; 334 335 return ts; 336 } 337 338 /** 339 * drm_sched_rq_pop_entity - pops an entity 340 * @entity: scheduler entity 341 * 342 * To be called every time after a job is popped from the entity. 343 */ 344 void drm_sched_rq_pop_entity(struct drm_sched_entity *entity) 345 { 346 struct drm_sched_job *next_job; 347 struct drm_sched_rq *rq; 348 349 /* 350 * Update the entity's location in the min heap according to 351 * the timestamp of the next job, if any. 352 */ 353 spin_lock(&entity->lock); 354 rq = entity->rq; 355 spin_lock(&rq->lock); 356 next_job = drm_sched_entity_queue_peek(entity); 357 if (next_job) { 358 ktime_t ts; 359 360 if (drm_sched_policy == DRM_SCHED_POLICY_FAIR) 361 ts = drm_sched_entity_get_job_ts(entity); 362 else if (drm_sched_policy == DRM_SCHED_POLICY_FIFO) 363 ts = next_job->submit_ts; 364 else 365 ts = drm_sched_rq_next_rr_ts(rq, entity); 366 367 drm_sched_rq_update_fifo_locked(entity, rq, ts); 368 } else { 369 drm_sched_rq_remove_fifo_locked(entity, rq); 370 371 if (drm_sched_policy == DRM_SCHED_POLICY_FAIR) { 372 ktime_t min_vruntime; 373 374 min_vruntime = drm_sched_rq_get_min_vruntime(rq); 375 drm_sched_entity_save_vruntime(entity, min_vruntime); 376 } 377 } 378 spin_unlock(&rq->lock); 379 spin_unlock(&entity->lock); 380 } 381 382 /** 383 * drm_sched_rq_select_entity - Select an entity which provides a job to run 384 * @sched: the gpu scheduler 385 * @rq: scheduler run queue to check. 386 * 387 * Find oldest waiting ready entity. 388 * 389 * Return an entity if one is found; return an error-pointer (!NULL) if an 390 * entity was ready, but the scheduler had insufficient credits to accommodate 391 * its job; return NULL, if no ready entity was found. 392 */ 393 struct drm_sched_entity * 394 drm_sched_rq_select_entity(struct drm_gpu_scheduler *sched, 395 struct drm_sched_rq *rq) 396 { 397 struct rb_node *rb; 398 399 spin_lock(&rq->lock); 400 for (rb = rb_first_cached(&rq->rb_tree_root); rb; rb = rb_next(rb)) { 401 struct drm_sched_entity *entity; 402 403 entity = rb_entry(rb, struct drm_sched_entity, rb_tree_node); 404 if (drm_sched_entity_is_ready(entity)) { 405 /* If we can't queue yet, preserve the current entity in 406 * terms of fairness. 407 */ 408 if (!drm_sched_can_queue(sched, entity)) { 409 spin_unlock(&rq->lock); 410 return ERR_PTR(-ENOSPC); 411 } 412 413 reinit_completion(&entity->entity_idle); 414 break; 415 } 416 } 417 spin_unlock(&rq->lock); 418 419 return rb ? rb_entry(rb, struct drm_sched_entity, rb_tree_node) : NULL; 420 } 421