sched.c 27 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106
  1. /* sched.c - SPU scheduler.
  2. *
  3. * Copyright (C) IBM 2005
  4. * Author: Mark Nutter <mnutter@us.ibm.com>
  5. *
  6. * 2006-03-31 NUMA domains added.
  7. *
  8. * This program is free software; you can redistribute it and/or modify
  9. * it under the terms of the GNU General Public License as published by
  10. * the Free Software Foundation; either version 2, or (at your option)
  11. * any later version.
  12. *
  13. * This program is distributed in the hope that it will be useful,
  14. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  16. * GNU General Public License for more details.
  17. *
  18. * You should have received a copy of the GNU General Public License
  19. * along with this program; if not, write to the Free Software
  20. * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21. */
  22. #undef DEBUG
  23. #include <linux/module.h>
  24. #include <linux/errno.h>
  25. #include <linux/sched.h>
  26. #include <linux/kernel.h>
  27. #include <linux/mm.h>
  28. #include <linux/completion.h>
  29. #include <linux/vmalloc.h>
  30. #include <linux/smp.h>
  31. #include <linux/stddef.h>
  32. #include <linux/unistd.h>
  33. #include <linux/numa.h>
  34. #include <linux/mutex.h>
  35. #include <linux/notifier.h>
  36. #include <linux/kthread.h>
  37. #include <linux/pid_namespace.h>
  38. #include <linux/proc_fs.h>
  39. #include <linux/seq_file.h>
  40. #include <linux/marker.h>
  41. #include <asm/io.h>
  42. #include <asm/mmu_context.h>
  43. #include <asm/spu.h>
  44. #include <asm/spu_csa.h>
  45. #include <asm/spu_priv1.h>
  46. #include "spufs.h"
  47. struct spu_prio_array {
  48. DECLARE_BITMAP(bitmap, MAX_PRIO);
  49. struct list_head runq[MAX_PRIO];
  50. spinlock_t runq_lock;
  51. int nr_waiting;
  52. };
  53. static unsigned long spu_avenrun[3];
  54. static struct spu_prio_array *spu_prio;
  55. static struct task_struct *spusched_task;
  56. static struct timer_list spusched_timer;
  57. static struct timer_list spuloadavg_timer;
  58. /*
  59. * Priority of a normal, non-rt, non-niced'd process (aka nice level 0).
  60. */
  61. #define NORMAL_PRIO 120
  62. /*
  63. * Frequency of the spu scheduler tick. By default we do one SPU scheduler
  64. * tick for every 10 CPU scheduler ticks.
  65. */
  66. #define SPUSCHED_TICK (10)
  67. /*
  68. * These are the 'tuning knobs' of the scheduler:
  69. *
  70. * Minimum timeslice is 5 msecs (or 1 spu scheduler tick, whichever is
  71. * larger), default timeslice is 100 msecs, maximum timeslice is 800 msecs.
  72. */
  73. #define MIN_SPU_TIMESLICE max(5 * HZ / (1000 * SPUSCHED_TICK), 1)
  74. #define DEF_SPU_TIMESLICE (100 * HZ / (1000 * SPUSCHED_TICK))
  75. #define MAX_USER_PRIO (MAX_PRIO - MAX_RT_PRIO)
  76. #define SCALE_PRIO(x, prio) \
  77. max(x * (MAX_PRIO - prio) / (MAX_USER_PRIO / 2), MIN_SPU_TIMESLICE)
  78. /*
  79. * scale user-nice values [ -20 ... 0 ... 19 ] to time slice values:
  80. * [800ms ... 100ms ... 5ms]
  81. *
  82. * The higher a thread's priority, the bigger timeslices
  83. * it gets during one round of execution. But even the lowest
  84. * priority thread gets MIN_TIMESLICE worth of execution time.
  85. */
  86. void spu_set_timeslice(struct spu_context *ctx)
  87. {
  88. if (ctx->prio < NORMAL_PRIO)
  89. ctx->time_slice = SCALE_PRIO(DEF_SPU_TIMESLICE * 4, ctx->prio);
  90. else
  91. ctx->time_slice = SCALE_PRIO(DEF_SPU_TIMESLICE, ctx->prio);
  92. }
  93. /*
  94. * Update scheduling information from the owning thread.
  95. */
  96. void __spu_update_sched_info(struct spu_context *ctx)
  97. {
  98. /*
  99. * assert that the context is not on the runqueue, so it is safe
  100. * to change its scheduling parameters.
  101. */
  102. BUG_ON(!list_empty(&ctx->rq));
  103. /*
  104. * 32-Bit assignments are atomic on powerpc, and we don't care about
  105. * memory ordering here because retrieving the controlling thread is
  106. * per definition racy.
  107. */
  108. ctx->tid = current->pid;
  109. /*
  110. * We do our own priority calculations, so we normally want
  111. * ->static_prio to start with. Unfortunately this field
  112. * contains junk for threads with a realtime scheduling
  113. * policy so we have to look at ->prio in this case.
  114. */
  115. if (rt_prio(current->prio))
  116. ctx->prio = current->prio;
  117. else
  118. ctx->prio = current->static_prio;
  119. ctx->policy = current->policy;
  120. /*
  121. * TO DO: the context may be loaded, so we may need to activate
  122. * it again on a different node. But it shouldn't hurt anything
  123. * to update its parameters, because we know that the scheduler
  124. * is not actively looking at this field, since it is not on the
  125. * runqueue. The context will be rescheduled on the proper node
  126. * if it is timesliced or preempted.
  127. */
  128. ctx->cpus_allowed = current->cpus_allowed;
  129. /* Save the current cpu id for spu interrupt routing. */
  130. ctx->last_ran = raw_smp_processor_id();
  131. }
  132. void spu_update_sched_info(struct spu_context *ctx)
  133. {
  134. int node;
  135. if (ctx->state == SPU_STATE_RUNNABLE) {
  136. node = ctx->spu->node;
  137. /*
  138. * Take list_mutex to sync with find_victim().
  139. */
  140. mutex_lock(&cbe_spu_info[node].list_mutex);
  141. __spu_update_sched_info(ctx);
  142. mutex_unlock(&cbe_spu_info[node].list_mutex);
  143. } else {
  144. __spu_update_sched_info(ctx);
  145. }
  146. }
  147. static int __node_allowed(struct spu_context *ctx, int node)
  148. {
  149. if (nr_cpus_node(node)) {
  150. cpumask_t mask = node_to_cpumask(node);
  151. if (cpus_intersects(mask, ctx->cpus_allowed))
  152. return 1;
  153. }
  154. return 0;
  155. }
  156. static int node_allowed(struct spu_context *ctx, int node)
  157. {
  158. int rval;
  159. spin_lock(&spu_prio->runq_lock);
  160. rval = __node_allowed(ctx, node);
  161. spin_unlock(&spu_prio->runq_lock);
  162. return rval;
  163. }
  164. void do_notify_spus_active(void)
  165. {
  166. int node;
  167. /*
  168. * Wake up the active spu_contexts.
  169. *
  170. * When the awakened processes see their "notify_active" flag is set,
  171. * they will call spu_switch_notify().
  172. */
  173. for_each_online_node(node) {
  174. struct spu *spu;
  175. mutex_lock(&cbe_spu_info[node].list_mutex);
  176. list_for_each_entry(spu, &cbe_spu_info[node].spus, cbe_list) {
  177. if (spu->alloc_state != SPU_FREE) {
  178. struct spu_context *ctx = spu->ctx;
  179. set_bit(SPU_SCHED_NOTIFY_ACTIVE,
  180. &ctx->sched_flags);
  181. mb();
  182. wake_up_all(&ctx->stop_wq);
  183. }
  184. }
  185. mutex_unlock(&cbe_spu_info[node].list_mutex);
  186. }
  187. }
  188. /**
  189. * spu_bind_context - bind spu context to physical spu
  190. * @spu: physical spu to bind to
  191. * @ctx: context to bind
  192. */
  193. static void spu_bind_context(struct spu *spu, struct spu_context *ctx)
  194. {
  195. spu_context_trace(spu_bind_context__enter, ctx, spu);
  196. spuctx_switch_state(ctx, SPU_UTIL_SYSTEM);
  197. if (ctx->flags & SPU_CREATE_NOSCHED)
  198. atomic_inc(&cbe_spu_info[spu->node].reserved_spus);
  199. ctx->stats.slb_flt_base = spu->stats.slb_flt;
  200. ctx->stats.class2_intr_base = spu->stats.class2_intr;
  201. spu->ctx = ctx;
  202. spu->flags = 0;
  203. ctx->spu = spu;
  204. ctx->ops = &spu_hw_ops;
  205. spu->pid = current->pid;
  206. spu->tgid = current->tgid;
  207. spu_associate_mm(spu, ctx->owner);
  208. spu->ibox_callback = spufs_ibox_callback;
  209. spu->wbox_callback = spufs_wbox_callback;
  210. spu->stop_callback = spufs_stop_callback;
  211. spu->mfc_callback = spufs_mfc_callback;
  212. mb();
  213. spu_unmap_mappings(ctx);
  214. spu_switch_log_notify(spu, ctx, SWITCH_LOG_START, 0);
  215. spu_restore(&ctx->csa, spu);
  216. spu->timestamp = jiffies;
  217. spu_switch_notify(spu, ctx);
  218. ctx->state = SPU_STATE_RUNNABLE;
  219. spuctx_switch_state(ctx, SPU_UTIL_USER);
  220. }
  221. /*
  222. * Must be used with the list_mutex held.
  223. */
  224. static inline int sched_spu(struct spu *spu)
  225. {
  226. BUG_ON(!mutex_is_locked(&cbe_spu_info[spu->node].list_mutex));
  227. return (!spu->ctx || !(spu->ctx->flags & SPU_CREATE_NOSCHED));
  228. }
  229. static void aff_merge_remaining_ctxs(struct spu_gang *gang)
  230. {
  231. struct spu_context *ctx;
  232. list_for_each_entry(ctx, &gang->aff_list_head, aff_list) {
  233. if (list_empty(&ctx->aff_list))
  234. list_add(&ctx->aff_list, &gang->aff_list_head);
  235. }
  236. gang->aff_flags |= AFF_MERGED;
  237. }
  238. static void aff_set_offsets(struct spu_gang *gang)
  239. {
  240. struct spu_context *ctx;
  241. int offset;
  242. offset = -1;
  243. list_for_each_entry_reverse(ctx, &gang->aff_ref_ctx->aff_list,
  244. aff_list) {
  245. if (&ctx->aff_list == &gang->aff_list_head)
  246. break;
  247. ctx->aff_offset = offset--;
  248. }
  249. offset = 0;
  250. list_for_each_entry(ctx, gang->aff_ref_ctx->aff_list.prev, aff_list) {
  251. if (&ctx->aff_list == &gang->aff_list_head)
  252. break;
  253. ctx->aff_offset = offset++;
  254. }
  255. gang->aff_flags |= AFF_OFFSETS_SET;
  256. }
  257. static struct spu *aff_ref_location(struct spu_context *ctx, int mem_aff,
  258. int group_size, int lowest_offset)
  259. {
  260. struct spu *spu;
  261. int node, n;
  262. /*
  263. * TODO: A better algorithm could be used to find a good spu to be
  264. * used as reference location for the ctxs chain.
  265. */
  266. node = cpu_to_node(raw_smp_processor_id());
  267. for (n = 0; n < MAX_NUMNODES; n++, node++) {
  268. node = (node < MAX_NUMNODES) ? node : 0;
  269. if (!node_allowed(ctx, node))
  270. continue;
  271. mutex_lock(&cbe_spu_info[node].list_mutex);
  272. list_for_each_entry(spu, &cbe_spu_info[node].spus, cbe_list) {
  273. if ((!mem_aff || spu->has_mem_affinity) &&
  274. sched_spu(spu)) {
  275. mutex_unlock(&cbe_spu_info[node].list_mutex);
  276. return spu;
  277. }
  278. }
  279. mutex_unlock(&cbe_spu_info[node].list_mutex);
  280. }
  281. return NULL;
  282. }
  283. static void aff_set_ref_point_location(struct spu_gang *gang)
  284. {
  285. int mem_aff, gs, lowest_offset;
  286. struct spu_context *ctx;
  287. struct spu *tmp;
  288. mem_aff = gang->aff_ref_ctx->flags & SPU_CREATE_AFFINITY_MEM;
  289. lowest_offset = 0;
  290. gs = 0;
  291. list_for_each_entry(tmp, &gang->aff_list_head, aff_list)
  292. gs++;
  293. list_for_each_entry_reverse(ctx, &gang->aff_ref_ctx->aff_list,
  294. aff_list) {
  295. if (&ctx->aff_list == &gang->aff_list_head)
  296. break;
  297. lowest_offset = ctx->aff_offset;
  298. }
  299. gang->aff_ref_spu = aff_ref_location(gang->aff_ref_ctx, mem_aff, gs,
  300. lowest_offset);
  301. }
  302. static struct spu *ctx_location(struct spu *ref, int offset, int node)
  303. {
  304. struct spu *spu;
  305. spu = NULL;
  306. if (offset >= 0) {
  307. list_for_each_entry(spu, ref->aff_list.prev, aff_list) {
  308. BUG_ON(spu->node != node);
  309. if (offset == 0)
  310. break;
  311. if (sched_spu(spu))
  312. offset--;
  313. }
  314. } else {
  315. list_for_each_entry_reverse(spu, ref->aff_list.next, aff_list) {
  316. BUG_ON(spu->node != node);
  317. if (offset == 0)
  318. break;
  319. if (sched_spu(spu))
  320. offset++;
  321. }
  322. }
  323. return spu;
  324. }
  325. /*
  326. * affinity_check is called each time a context is going to be scheduled.
  327. * It returns the spu ptr on which the context must run.
  328. */
  329. static int has_affinity(struct spu_context *ctx)
  330. {
  331. struct spu_gang *gang = ctx->gang;
  332. if (list_empty(&ctx->aff_list))
  333. return 0;
  334. if (!gang->aff_ref_spu) {
  335. if (!(gang->aff_flags & AFF_MERGED))
  336. aff_merge_remaining_ctxs(gang);
  337. if (!(gang->aff_flags & AFF_OFFSETS_SET))
  338. aff_set_offsets(gang);
  339. aff_set_ref_point_location(gang);
  340. }
  341. return gang->aff_ref_spu != NULL;
  342. }
  343. /**
  344. * spu_unbind_context - unbind spu context from physical spu
  345. * @spu: physical spu to unbind from
  346. * @ctx: context to unbind
  347. */
  348. static void spu_unbind_context(struct spu *spu, struct spu_context *ctx)
  349. {
  350. spu_context_trace(spu_unbind_context__enter, ctx, spu);
  351. spuctx_switch_state(ctx, SPU_UTIL_SYSTEM);
  352. if (spu->ctx->flags & SPU_CREATE_NOSCHED)
  353. atomic_dec(&cbe_spu_info[spu->node].reserved_spus);
  354. if (ctx->gang){
  355. mutex_lock(&ctx->gang->aff_mutex);
  356. if (has_affinity(ctx)) {
  357. if (atomic_dec_and_test(&ctx->gang->aff_sched_count))
  358. ctx->gang->aff_ref_spu = NULL;
  359. }
  360. mutex_unlock(&ctx->gang->aff_mutex);
  361. }
  362. spu_switch_notify(spu, NULL);
  363. spu_unmap_mappings(ctx);
  364. spu_save(&ctx->csa, spu);
  365. spu_switch_log_notify(spu, ctx, SWITCH_LOG_STOP, 0);
  366. spu->timestamp = jiffies;
  367. ctx->state = SPU_STATE_SAVED;
  368. spu->ibox_callback = NULL;
  369. spu->wbox_callback = NULL;
  370. spu->stop_callback = NULL;
  371. spu->mfc_callback = NULL;
  372. spu_associate_mm(spu, NULL);
  373. spu->pid = 0;
  374. spu->tgid = 0;
  375. ctx->ops = &spu_backing_ops;
  376. spu->flags = 0;
  377. spu->ctx = NULL;
  378. ctx->stats.slb_flt +=
  379. (spu->stats.slb_flt - ctx->stats.slb_flt_base);
  380. ctx->stats.class2_intr +=
  381. (spu->stats.class2_intr - ctx->stats.class2_intr_base);
  382. /* This maps the underlying spu state to idle */
  383. spuctx_switch_state(ctx, SPU_UTIL_IDLE_LOADED);
  384. ctx->spu = NULL;
  385. }
  386. /**
  387. * spu_add_to_rq - add a context to the runqueue
  388. * @ctx: context to add
  389. */
  390. static void __spu_add_to_rq(struct spu_context *ctx)
  391. {
  392. /*
  393. * Unfortunately this code path can be called from multiple threads
  394. * on behalf of a single context due to the way the problem state
  395. * mmap support works.
  396. *
  397. * Fortunately we need to wake up all these threads at the same time
  398. * and can simply skip the runqueue addition for every but the first
  399. * thread getting into this codepath.
  400. *
  401. * It's still quite hacky, and long-term we should proxy all other
  402. * threads through the owner thread so that spu_run is in control
  403. * of all the scheduling activity for a given context.
  404. */
  405. if (list_empty(&ctx->rq)) {
  406. list_add_tail(&ctx->rq, &spu_prio->runq[ctx->prio]);
  407. set_bit(ctx->prio, spu_prio->bitmap);
  408. if (!spu_prio->nr_waiting++)
  409. __mod_timer(&spusched_timer, jiffies + SPUSCHED_TICK);
  410. }
  411. }
  412. static void spu_add_to_rq(struct spu_context *ctx)
  413. {
  414. spin_lock(&spu_prio->runq_lock);
  415. __spu_add_to_rq(ctx);
  416. spin_unlock(&spu_prio->runq_lock);
  417. }
  418. static void __spu_del_from_rq(struct spu_context *ctx)
  419. {
  420. int prio = ctx->prio;
  421. if (!list_empty(&ctx->rq)) {
  422. if (!--spu_prio->nr_waiting)
  423. del_timer(&spusched_timer);
  424. list_del_init(&ctx->rq);
  425. if (list_empty(&spu_prio->runq[prio]))
  426. clear_bit(prio, spu_prio->bitmap);
  427. }
  428. }
  429. void spu_del_from_rq(struct spu_context *ctx)
  430. {
  431. spin_lock(&spu_prio->runq_lock);
  432. __spu_del_from_rq(ctx);
  433. spin_unlock(&spu_prio->runq_lock);
  434. }
  435. static void spu_prio_wait(struct spu_context *ctx)
  436. {
  437. DEFINE_WAIT(wait);
  438. /*
  439. * The caller must explicitly wait for a context to be loaded
  440. * if the nosched flag is set. If NOSCHED is not set, the caller
  441. * queues the context and waits for an spu event or error.
  442. */
  443. BUG_ON(!(ctx->flags & SPU_CREATE_NOSCHED));
  444. spin_lock(&spu_prio->runq_lock);
  445. prepare_to_wait_exclusive(&ctx->stop_wq, &wait, TASK_INTERRUPTIBLE);
  446. if (!signal_pending(current)) {
  447. __spu_add_to_rq(ctx);
  448. spin_unlock(&spu_prio->runq_lock);
  449. mutex_unlock(&ctx->state_mutex);
  450. schedule();
  451. mutex_lock(&ctx->state_mutex);
  452. spin_lock(&spu_prio->runq_lock);
  453. __spu_del_from_rq(ctx);
  454. }
  455. spin_unlock(&spu_prio->runq_lock);
  456. __set_current_state(TASK_RUNNING);
  457. remove_wait_queue(&ctx->stop_wq, &wait);
  458. }
  459. static struct spu *spu_get_idle(struct spu_context *ctx)
  460. {
  461. struct spu *spu, *aff_ref_spu;
  462. int node, n;
  463. spu_context_nospu_trace(spu_get_idle__enter, ctx);
  464. if (ctx->gang) {
  465. mutex_lock(&ctx->gang->aff_mutex);
  466. if (has_affinity(ctx)) {
  467. aff_ref_spu = ctx->gang->aff_ref_spu;
  468. atomic_inc(&ctx->gang->aff_sched_count);
  469. mutex_unlock(&ctx->gang->aff_mutex);
  470. node = aff_ref_spu->node;
  471. mutex_lock(&cbe_spu_info[node].list_mutex);
  472. spu = ctx_location(aff_ref_spu, ctx->aff_offset, node);
  473. if (spu && spu->alloc_state == SPU_FREE)
  474. goto found;
  475. mutex_unlock(&cbe_spu_info[node].list_mutex);
  476. mutex_lock(&ctx->gang->aff_mutex);
  477. if (atomic_dec_and_test(&ctx->gang->aff_sched_count))
  478. ctx->gang->aff_ref_spu = NULL;
  479. mutex_unlock(&ctx->gang->aff_mutex);
  480. goto not_found;
  481. }
  482. mutex_unlock(&ctx->gang->aff_mutex);
  483. }
  484. node = cpu_to_node(raw_smp_processor_id());
  485. for (n = 0; n < MAX_NUMNODES; n++, node++) {
  486. node = (node < MAX_NUMNODES) ? node : 0;
  487. if (!node_allowed(ctx, node))
  488. continue;
  489. mutex_lock(&cbe_spu_info[node].list_mutex);
  490. list_for_each_entry(spu, &cbe_spu_info[node].spus, cbe_list) {
  491. if (spu->alloc_state == SPU_FREE)
  492. goto found;
  493. }
  494. mutex_unlock(&cbe_spu_info[node].list_mutex);
  495. }
  496. not_found:
  497. spu_context_nospu_trace(spu_get_idle__not_found, ctx);
  498. return NULL;
  499. found:
  500. spu->alloc_state = SPU_USED;
  501. mutex_unlock(&cbe_spu_info[node].list_mutex);
  502. spu_context_trace(spu_get_idle__found, ctx, spu);
  503. spu_init_channels(spu);
  504. return spu;
  505. }
  506. /**
  507. * find_victim - find a lower priority context to preempt
  508. * @ctx: canidate context for running
  509. *
  510. * Returns the freed physical spu to run the new context on.
  511. */
  512. static struct spu *find_victim(struct spu_context *ctx)
  513. {
  514. struct spu_context *victim = NULL;
  515. struct spu *spu;
  516. int node, n;
  517. spu_context_nospu_trace(spu_find_victim__enter, ctx);
  518. /*
  519. * Look for a possible preemption candidate on the local node first.
  520. * If there is no candidate look at the other nodes. This isn't
  521. * exactly fair, but so far the whole spu scheduler tries to keep
  522. * a strong node affinity. We might want to fine-tune this in
  523. * the future.
  524. */
  525. restart:
  526. node = cpu_to_node(raw_smp_processor_id());
  527. for (n = 0; n < MAX_NUMNODES; n++, node++) {
  528. node = (node < MAX_NUMNODES) ? node : 0;
  529. if (!node_allowed(ctx, node))
  530. continue;
  531. mutex_lock(&cbe_spu_info[node].list_mutex);
  532. list_for_each_entry(spu, &cbe_spu_info[node].spus, cbe_list) {
  533. struct spu_context *tmp = spu->ctx;
  534. if (tmp && tmp->prio > ctx->prio &&
  535. !(tmp->flags & SPU_CREATE_NOSCHED) &&
  536. (!victim || tmp->prio > victim->prio))
  537. victim = spu->ctx;
  538. }
  539. mutex_unlock(&cbe_spu_info[node].list_mutex);
  540. if (victim) {
  541. /*
  542. * This nests ctx->state_mutex, but we always lock
  543. * higher priority contexts before lower priority
  544. * ones, so this is safe until we introduce
  545. * priority inheritance schemes.
  546. *
  547. * XXX if the highest priority context is locked,
  548. * this can loop a long time. Might be better to
  549. * look at another context or give up after X retries.
  550. */
  551. if (!mutex_trylock(&victim->state_mutex)) {
  552. victim = NULL;
  553. goto restart;
  554. }
  555. spu = victim->spu;
  556. if (!spu || victim->prio <= ctx->prio) {
  557. /*
  558. * This race can happen because we've dropped
  559. * the active list mutex. Not a problem, just
  560. * restart the search.
  561. */
  562. mutex_unlock(&victim->state_mutex);
  563. victim = NULL;
  564. goto restart;
  565. }
  566. spu_context_trace(__spu_deactivate__unload, ctx, spu);
  567. mutex_lock(&cbe_spu_info[node].list_mutex);
  568. cbe_spu_info[node].nr_active--;
  569. spu_unbind_context(spu, victim);
  570. mutex_unlock(&cbe_spu_info[node].list_mutex);
  571. victim->stats.invol_ctx_switch++;
  572. spu->stats.invol_ctx_switch++;
  573. if (test_bit(SPU_SCHED_SPU_RUN, &ctx->sched_flags))
  574. spu_add_to_rq(victim);
  575. mutex_unlock(&victim->state_mutex);
  576. return spu;
  577. }
  578. }
  579. return NULL;
  580. }
  581. static void __spu_schedule(struct spu *spu, struct spu_context *ctx)
  582. {
  583. int node = spu->node;
  584. int success = 0;
  585. spu_set_timeslice(ctx);
  586. mutex_lock(&cbe_spu_info[node].list_mutex);
  587. if (spu->ctx == NULL) {
  588. spu_bind_context(spu, ctx);
  589. cbe_spu_info[node].nr_active++;
  590. spu->alloc_state = SPU_USED;
  591. success = 1;
  592. }
  593. mutex_unlock(&cbe_spu_info[node].list_mutex);
  594. if (success)
  595. wake_up_all(&ctx->run_wq);
  596. else
  597. spu_add_to_rq(ctx);
  598. }
  599. static void spu_schedule(struct spu *spu, struct spu_context *ctx)
  600. {
  601. /* not a candidate for interruptible because it's called either
  602. from the scheduler thread or from spu_deactivate */
  603. mutex_lock(&ctx->state_mutex);
  604. __spu_schedule(spu, ctx);
  605. spu_release(ctx);
  606. }
  607. static void spu_unschedule(struct spu *spu, struct spu_context *ctx)
  608. {
  609. int node = spu->node;
  610. mutex_lock(&cbe_spu_info[node].list_mutex);
  611. cbe_spu_info[node].nr_active--;
  612. spu->alloc_state = SPU_FREE;
  613. spu_unbind_context(spu, ctx);
  614. ctx->stats.invol_ctx_switch++;
  615. spu->stats.invol_ctx_switch++;
  616. mutex_unlock(&cbe_spu_info[node].list_mutex);
  617. }
  618. /**
  619. * spu_activate - find a free spu for a context and execute it
  620. * @ctx: spu context to schedule
  621. * @flags: flags (currently ignored)
  622. *
  623. * Tries to find a free spu to run @ctx. If no free spu is available
  624. * add the context to the runqueue so it gets woken up once an spu
  625. * is available.
  626. */
  627. int spu_activate(struct spu_context *ctx, unsigned long flags)
  628. {
  629. struct spu *spu;
  630. /*
  631. * If there are multiple threads waiting for a single context
  632. * only one actually binds the context while the others will
  633. * only be able to acquire the state_mutex once the context
  634. * already is in runnable state.
  635. */
  636. if (ctx->spu)
  637. return 0;
  638. spu_activate_top:
  639. if (signal_pending(current))
  640. return -ERESTARTSYS;
  641. spu = spu_get_idle(ctx);
  642. /*
  643. * If this is a realtime thread we try to get it running by
  644. * preempting a lower priority thread.
  645. */
  646. if (!spu && rt_prio(ctx->prio))
  647. spu = find_victim(ctx);
  648. if (spu) {
  649. unsigned long runcntl;
  650. runcntl = ctx->ops->runcntl_read(ctx);
  651. __spu_schedule(spu, ctx);
  652. if (runcntl & SPU_RUNCNTL_RUNNABLE)
  653. spuctx_switch_state(ctx, SPU_UTIL_USER);
  654. return 0;
  655. }
  656. if (ctx->flags & SPU_CREATE_NOSCHED) {
  657. spu_prio_wait(ctx);
  658. goto spu_activate_top;
  659. }
  660. spu_add_to_rq(ctx);
  661. return 0;
  662. }
  663. /**
  664. * grab_runnable_context - try to find a runnable context
  665. *
  666. * Remove the highest priority context on the runqueue and return it
  667. * to the caller. Returns %NULL if no runnable context was found.
  668. */
  669. static struct spu_context *grab_runnable_context(int prio, int node)
  670. {
  671. struct spu_context *ctx;
  672. int best;
  673. spin_lock(&spu_prio->runq_lock);
  674. best = find_first_bit(spu_prio->bitmap, prio);
  675. while (best < prio) {
  676. struct list_head *rq = &spu_prio->runq[best];
  677. list_for_each_entry(ctx, rq, rq) {
  678. /* XXX(hch): check for affinity here aswell */
  679. if (__node_allowed(ctx, node)) {
  680. __spu_del_from_rq(ctx);
  681. goto found;
  682. }
  683. }
  684. best++;
  685. }
  686. ctx = NULL;
  687. found:
  688. spin_unlock(&spu_prio->runq_lock);
  689. return ctx;
  690. }
  691. static int __spu_deactivate(struct spu_context *ctx, int force, int max_prio)
  692. {
  693. struct spu *spu = ctx->spu;
  694. struct spu_context *new = NULL;
  695. if (spu) {
  696. new = grab_runnable_context(max_prio, spu->node);
  697. if (new || force) {
  698. spu_unschedule(spu, ctx);
  699. if (new) {
  700. if (new->flags & SPU_CREATE_NOSCHED)
  701. wake_up(&new->stop_wq);
  702. else {
  703. spu_release(ctx);
  704. spu_schedule(spu, new);
  705. /* this one can't easily be made
  706. interruptible */
  707. mutex_lock(&ctx->state_mutex);
  708. }
  709. }
  710. }
  711. }
  712. return new != NULL;
  713. }
  714. /**
  715. * spu_deactivate - unbind a context from it's physical spu
  716. * @ctx: spu context to unbind
  717. *
  718. * Unbind @ctx from the physical spu it is running on and schedule
  719. * the highest priority context to run on the freed physical spu.
  720. */
  721. void spu_deactivate(struct spu_context *ctx)
  722. {
  723. spu_context_nospu_trace(spu_deactivate__enter, ctx);
  724. __spu_deactivate(ctx, 1, MAX_PRIO);
  725. }
  726. /**
  727. * spu_yield - yield a physical spu if others are waiting
  728. * @ctx: spu context to yield
  729. *
  730. * Check if there is a higher priority context waiting and if yes
  731. * unbind @ctx from the physical spu and schedule the highest
  732. * priority context to run on the freed physical spu instead.
  733. */
  734. void spu_yield(struct spu_context *ctx)
  735. {
  736. spu_context_nospu_trace(spu_yield__enter, ctx);
  737. if (!(ctx->flags & SPU_CREATE_NOSCHED)) {
  738. mutex_lock(&ctx->state_mutex);
  739. __spu_deactivate(ctx, 0, MAX_PRIO);
  740. mutex_unlock(&ctx->state_mutex);
  741. }
  742. }
  743. static noinline void spusched_tick(struct spu_context *ctx)
  744. {
  745. struct spu_context *new = NULL;
  746. struct spu *spu = NULL;
  747. if (spu_acquire(ctx))
  748. BUG(); /* a kernel thread never has signals pending */
  749. if (ctx->state != SPU_STATE_RUNNABLE)
  750. goto out;
  751. if (ctx->flags & SPU_CREATE_NOSCHED)
  752. goto out;
  753. if (ctx->policy == SCHED_FIFO)
  754. goto out;
  755. if (--ctx->time_slice && test_bit(SPU_SCHED_SPU_RUN, &ctx->sched_flags))
  756. goto out;
  757. spu = ctx->spu;
  758. spu_context_trace(spusched_tick__preempt, ctx, spu);
  759. new = grab_runnable_context(ctx->prio + 1, spu->node);
  760. if (new) {
  761. spu_unschedule(spu, ctx);
  762. if (test_bit(SPU_SCHED_SPU_RUN, &ctx->sched_flags))
  763. spu_add_to_rq(ctx);
  764. } else {
  765. spu_context_nospu_trace(spusched_tick__newslice, ctx);
  766. ctx->time_slice++;
  767. }
  768. out:
  769. spu_release(ctx);
  770. if (new)
  771. spu_schedule(spu, new);
  772. }
  773. /**
  774. * count_active_contexts - count nr of active tasks
  775. *
  776. * Return the number of tasks currently running or waiting to run.
  777. *
  778. * Note that we don't take runq_lock / list_mutex here. Reading
  779. * a single 32bit value is atomic on powerpc, and we don't care
  780. * about memory ordering issues here.
  781. */
  782. static unsigned long count_active_contexts(void)
  783. {
  784. int nr_active = 0, node;
  785. for (node = 0; node < MAX_NUMNODES; node++)
  786. nr_active += cbe_spu_info[node].nr_active;
  787. nr_active += spu_prio->nr_waiting;
  788. return nr_active;
  789. }
  790. /**
  791. * spu_calc_load - update the avenrun load estimates.
  792. *
  793. * No locking against reading these values from userspace, as for
  794. * the CPU loadavg code.
  795. */
  796. static void spu_calc_load(void)
  797. {
  798. unsigned long active_tasks; /* fixed-point */
  799. active_tasks = count_active_contexts() * FIXED_1;
  800. CALC_LOAD(spu_avenrun[0], EXP_1, active_tasks);
  801. CALC_LOAD(spu_avenrun[1], EXP_5, active_tasks);
  802. CALC_LOAD(spu_avenrun[2], EXP_15, active_tasks);
  803. }
  804. static void spusched_wake(unsigned long data)
  805. {
  806. mod_timer(&spusched_timer, jiffies + SPUSCHED_TICK);
  807. wake_up_process(spusched_task);
  808. }
  809. static void spuloadavg_wake(unsigned long data)
  810. {
  811. mod_timer(&spuloadavg_timer, jiffies + LOAD_FREQ);
  812. spu_calc_load();
  813. }
  814. static int spusched_thread(void *unused)
  815. {
  816. struct spu *spu;
  817. int node;
  818. while (!kthread_should_stop()) {
  819. set_current_state(TASK_INTERRUPTIBLE);
  820. schedule();
  821. for (node = 0; node < MAX_NUMNODES; node++) {
  822. struct mutex *mtx = &cbe_spu_info[node].list_mutex;
  823. mutex_lock(mtx);
  824. list_for_each_entry(spu, &cbe_spu_info[node].spus,
  825. cbe_list) {
  826. struct spu_context *ctx = spu->ctx;
  827. if (ctx) {
  828. mutex_unlock(mtx);
  829. spusched_tick(ctx);
  830. mutex_lock(mtx);
  831. }
  832. }
  833. mutex_unlock(mtx);
  834. }
  835. }
  836. return 0;
  837. }
  838. void spuctx_switch_state(struct spu_context *ctx,
  839. enum spu_utilization_state new_state)
  840. {
  841. unsigned long long curtime;
  842. signed long long delta;
  843. struct timespec ts;
  844. struct spu *spu;
  845. enum spu_utilization_state old_state;
  846. ktime_get_ts(&ts);
  847. curtime = timespec_to_ns(&ts);
  848. delta = curtime - ctx->stats.tstamp;
  849. WARN_ON(!mutex_is_locked(&ctx->state_mutex));
  850. WARN_ON(delta < 0);
  851. spu = ctx->spu;
  852. old_state = ctx->stats.util_state;
  853. ctx->stats.util_state = new_state;
  854. ctx->stats.tstamp = curtime;
  855. /*
  856. * Update the physical SPU utilization statistics.
  857. */
  858. if (spu) {
  859. ctx->stats.times[old_state] += delta;
  860. spu->stats.times[old_state] += delta;
  861. spu->stats.util_state = new_state;
  862. spu->stats.tstamp = curtime;
  863. }
  864. }
  865. #define LOAD_INT(x) ((x) >> FSHIFT)
  866. #define LOAD_FRAC(x) LOAD_INT(((x) & (FIXED_1-1)) * 100)
  867. static int show_spu_loadavg(struct seq_file *s, void *private)
  868. {
  869. int a, b, c;
  870. a = spu_avenrun[0] + (FIXED_1/200);
  871. b = spu_avenrun[1] + (FIXED_1/200);
  872. c = spu_avenrun[2] + (FIXED_1/200);
  873. /*
  874. * Note that last_pid doesn't really make much sense for the
  875. * SPU loadavg (it even seems very odd on the CPU side...),
  876. * but we include it here to have a 100% compatible interface.
  877. */
  878. seq_printf(s, "%d.%02d %d.%02d %d.%02d %ld/%d %d\n",
  879. LOAD_INT(a), LOAD_FRAC(a),
  880. LOAD_INT(b), LOAD_FRAC(b),
  881. LOAD_INT(c), LOAD_FRAC(c),
  882. count_active_contexts(),
  883. atomic_read(&nr_spu_contexts),
  884. current->nsproxy->pid_ns->last_pid);
  885. return 0;
  886. }
  887. static int spu_loadavg_open(struct inode *inode, struct file *file)
  888. {
  889. return single_open(file, show_spu_loadavg, NULL);
  890. }
  891. static const struct file_operations spu_loadavg_fops = {
  892. .open = spu_loadavg_open,
  893. .read = seq_read,
  894. .llseek = seq_lseek,
  895. .release = single_release,
  896. };
  897. int __init spu_sched_init(void)
  898. {
  899. struct proc_dir_entry *entry;
  900. int err = -ENOMEM, i;
  901. spu_prio = kzalloc(sizeof(struct spu_prio_array), GFP_KERNEL);
  902. if (!spu_prio)
  903. goto out;
  904. for (i = 0; i < MAX_PRIO; i++) {
  905. INIT_LIST_HEAD(&spu_prio->runq[i]);
  906. __clear_bit(i, spu_prio->bitmap);
  907. }
  908. spin_lock_init(&spu_prio->runq_lock);
  909. setup_timer(&spusched_timer, spusched_wake, 0);
  910. setup_timer(&spuloadavg_timer, spuloadavg_wake, 0);
  911. spusched_task = kthread_run(spusched_thread, NULL, "spusched");
  912. if (IS_ERR(spusched_task)) {
  913. err = PTR_ERR(spusched_task);
  914. goto out_free_spu_prio;
  915. }
  916. mod_timer(&spuloadavg_timer, 0);
  917. entry = proc_create("spu_loadavg", 0, NULL, &spu_loadavg_fops);
  918. if (!entry)
  919. goto out_stop_kthread;
  920. pr_debug("spusched: tick: %d, min ticks: %d, default ticks: %d\n",
  921. SPUSCHED_TICK, MIN_SPU_TIMESLICE, DEF_SPU_TIMESLICE);
  922. return 0;
  923. out_stop_kthread:
  924. kthread_stop(spusched_task);
  925. out_free_spu_prio:
  926. kfree(spu_prio);
  927. out:
  928. return err;
  929. }
  930. void spu_sched_exit(void)
  931. {
  932. struct spu *spu;
  933. int node;
  934. remove_proc_entry("spu_loadavg", NULL);
  935. del_timer_sync(&spusched_timer);
  936. del_timer_sync(&spuloadavg_timer);
  937. kthread_stop(spusched_task);
  938. for (node = 0; node < MAX_NUMNODES; node++) {
  939. mutex_lock(&cbe_spu_info[node].list_mutex);
  940. list_for_each_entry(spu, &cbe_spu_info[node].spus, cbe_list)
  941. if (spu->alloc_state != SPU_FREE)
  942. spu->alloc_state = SPU_FREE;
  943. mutex_unlock(&cbe_spu_info[node].list_mutex);
  944. }
  945. kfree(spu_prio);
  946. }