cfq-iosched.c 54 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309
  1. /*
  2. * CFQ, or complete fairness queueing, disk scheduler.
  3. *
  4. * Based on ideas from a previously unfinished io
  5. * scheduler (round robin per-process disk scheduling) and Andrea Arcangeli.
  6. *
  7. * Copyright (C) 2003 Jens Axboe <axboe@kernel.dk>
  8. */
  9. #include <linux/module.h>
  10. #include <linux/blkdev.h>
  11. #include <linux/elevator.h>
  12. #include <linux/rbtree.h>
  13. #include <linux/ioprio.h>
  14. /*
  15. * tunables
  16. */
  17. static const int cfq_quantum = 4; /* max queue in one round of service */
  18. static const int cfq_fifo_expire[2] = { HZ / 4, HZ / 8 };
  19. static const int cfq_back_max = 16 * 1024; /* maximum backwards seek, in KiB */
  20. static const int cfq_back_penalty = 2; /* penalty of a backwards seek */
  21. static const int cfq_slice_sync = HZ / 10;
  22. static int cfq_slice_async = HZ / 25;
  23. static const int cfq_slice_async_rq = 2;
  24. static int cfq_slice_idle = HZ / 125;
  25. /*
  26. * grace period before allowing idle class to get disk access
  27. */
  28. #define CFQ_IDLE_GRACE (HZ / 10)
  29. /*
  30. * below this threshold, we consider thinktime immediate
  31. */
  32. #define CFQ_MIN_TT (2)
  33. #define CFQ_SLICE_SCALE (5)
  34. #define RQ_CIC(rq) ((struct cfq_io_context*)(rq)->elevator_private)
  35. #define RQ_CFQQ(rq) ((rq)->elevator_private2)
  36. static struct kmem_cache *cfq_pool;
  37. static struct kmem_cache *cfq_ioc_pool;
  38. static DEFINE_PER_CPU(unsigned long, ioc_count);
  39. static struct completion *ioc_gone;
  40. #define CFQ_PRIO_LISTS IOPRIO_BE_NR
  41. #define cfq_class_idle(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_IDLE)
  42. #define cfq_class_rt(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_RT)
  43. #define ASYNC (0)
  44. #define SYNC (1)
  45. #define sample_valid(samples) ((samples) > 80)
  46. /*
  47. * Most of our rbtree usage is for sorting with min extraction, so
  48. * if we cache the leftmost node we don't have to walk down the tree
  49. * to find it. Idea borrowed from Ingo Molnars CFS scheduler. We should
  50. * move this into the elevator for the rq sorting as well.
  51. */
  52. struct cfq_rb_root {
  53. struct rb_root rb;
  54. struct rb_node *left;
  55. };
  56. #define CFQ_RB_ROOT (struct cfq_rb_root) { RB_ROOT, NULL, }
  57. /*
  58. * Per block device queue structure
  59. */
  60. struct cfq_data {
  61. struct request_queue *queue;
  62. /*
  63. * rr list of queues with requests and the count of them
  64. */
  65. struct cfq_rb_root service_tree;
  66. unsigned int busy_queues;
  67. int rq_in_driver;
  68. int sync_flight;
  69. int hw_tag;
  70. /*
  71. * idle window management
  72. */
  73. struct timer_list idle_slice_timer;
  74. struct work_struct unplug_work;
  75. struct cfq_queue *active_queue;
  76. struct cfq_io_context *active_cic;
  77. /*
  78. * async queue for each priority case
  79. */
  80. struct cfq_queue *async_cfqq[2][IOPRIO_BE_NR];
  81. struct cfq_queue *async_idle_cfqq;
  82. struct timer_list idle_class_timer;
  83. sector_t last_position;
  84. unsigned long last_end_request;
  85. /*
  86. * tunables, see top of file
  87. */
  88. unsigned int cfq_quantum;
  89. unsigned int cfq_fifo_expire[2];
  90. unsigned int cfq_back_penalty;
  91. unsigned int cfq_back_max;
  92. unsigned int cfq_slice[2];
  93. unsigned int cfq_slice_async_rq;
  94. unsigned int cfq_slice_idle;
  95. struct list_head cic_list;
  96. };
  97. /*
  98. * Per process-grouping structure
  99. */
  100. struct cfq_queue {
  101. /* reference count */
  102. atomic_t ref;
  103. /* parent cfq_data */
  104. struct cfq_data *cfqd;
  105. /* service_tree member */
  106. struct rb_node rb_node;
  107. /* service_tree key */
  108. unsigned long rb_key;
  109. /* sorted list of pending requests */
  110. struct rb_root sort_list;
  111. /* if fifo isn't expired, next request to serve */
  112. struct request *next_rq;
  113. /* requests queued in sort_list */
  114. int queued[2];
  115. /* currently allocated requests */
  116. int allocated[2];
  117. /* pending metadata requests */
  118. int meta_pending;
  119. /* fifo list of requests in sort_list */
  120. struct list_head fifo;
  121. unsigned long slice_end;
  122. long slice_resid;
  123. /* number of requests that are on the dispatch list or inside driver */
  124. int dispatched;
  125. /* io prio of this group */
  126. unsigned short ioprio, org_ioprio;
  127. unsigned short ioprio_class, org_ioprio_class;
  128. /* various state flags, see below */
  129. unsigned int flags;
  130. };
  131. enum cfqq_state_flags {
  132. CFQ_CFQQ_FLAG_on_rr = 0, /* on round-robin busy list */
  133. CFQ_CFQQ_FLAG_wait_request, /* waiting for a request */
  134. CFQ_CFQQ_FLAG_must_alloc, /* must be allowed rq alloc */
  135. CFQ_CFQQ_FLAG_must_alloc_slice, /* per-slice must_alloc flag */
  136. CFQ_CFQQ_FLAG_must_dispatch, /* must dispatch, even if expired */
  137. CFQ_CFQQ_FLAG_fifo_expire, /* FIFO checked in this slice */
  138. CFQ_CFQQ_FLAG_idle_window, /* slice idling enabled */
  139. CFQ_CFQQ_FLAG_prio_changed, /* task priority has changed */
  140. CFQ_CFQQ_FLAG_queue_new, /* queue never been serviced */
  141. CFQ_CFQQ_FLAG_slice_new, /* no requests dispatched in slice */
  142. CFQ_CFQQ_FLAG_sync, /* synchronous queue */
  143. };
  144. #define CFQ_CFQQ_FNS(name) \
  145. static inline void cfq_mark_cfqq_##name(struct cfq_queue *cfqq) \
  146. { \
  147. cfqq->flags |= (1 << CFQ_CFQQ_FLAG_##name); \
  148. } \
  149. static inline void cfq_clear_cfqq_##name(struct cfq_queue *cfqq) \
  150. { \
  151. cfqq->flags &= ~(1 << CFQ_CFQQ_FLAG_##name); \
  152. } \
  153. static inline int cfq_cfqq_##name(const struct cfq_queue *cfqq) \
  154. { \
  155. return (cfqq->flags & (1 << CFQ_CFQQ_FLAG_##name)) != 0; \
  156. }
  157. CFQ_CFQQ_FNS(on_rr);
  158. CFQ_CFQQ_FNS(wait_request);
  159. CFQ_CFQQ_FNS(must_alloc);
  160. CFQ_CFQQ_FNS(must_alloc_slice);
  161. CFQ_CFQQ_FNS(must_dispatch);
  162. CFQ_CFQQ_FNS(fifo_expire);
  163. CFQ_CFQQ_FNS(idle_window);
  164. CFQ_CFQQ_FNS(prio_changed);
  165. CFQ_CFQQ_FNS(queue_new);
  166. CFQ_CFQQ_FNS(slice_new);
  167. CFQ_CFQQ_FNS(sync);
  168. #undef CFQ_CFQQ_FNS
  169. static void cfq_dispatch_insert(struct request_queue *, struct request *);
  170. static struct cfq_queue *cfq_get_queue(struct cfq_data *, int,
  171. struct task_struct *, gfp_t);
  172. static struct cfq_io_context *cfq_cic_rb_lookup(struct cfq_data *,
  173. struct io_context *);
  174. static inline struct cfq_queue *cic_to_cfqq(struct cfq_io_context *cic,
  175. int is_sync)
  176. {
  177. return cic->cfqq[!!is_sync];
  178. }
  179. static inline void cic_set_cfqq(struct cfq_io_context *cic,
  180. struct cfq_queue *cfqq, int is_sync)
  181. {
  182. cic->cfqq[!!is_sync] = cfqq;
  183. }
  184. /*
  185. * We regard a request as SYNC, if it's either a read or has the SYNC bit
  186. * set (in which case it could also be direct WRITE).
  187. */
  188. static inline int cfq_bio_sync(struct bio *bio)
  189. {
  190. if (bio_data_dir(bio) == READ || bio_sync(bio))
  191. return 1;
  192. return 0;
  193. }
  194. /*
  195. * scheduler run of queue, if there are requests pending and no one in the
  196. * driver that will restart queueing
  197. */
  198. static inline void cfq_schedule_dispatch(struct cfq_data *cfqd)
  199. {
  200. if (cfqd->busy_queues)
  201. kblockd_schedule_work(&cfqd->unplug_work);
  202. }
  203. static int cfq_queue_empty(struct request_queue *q)
  204. {
  205. struct cfq_data *cfqd = q->elevator->elevator_data;
  206. return !cfqd->busy_queues;
  207. }
  208. /*
  209. * Scale schedule slice based on io priority. Use the sync time slice only
  210. * if a queue is marked sync and has sync io queued. A sync queue with async
  211. * io only, should not get full sync slice length.
  212. */
  213. static inline int cfq_prio_slice(struct cfq_data *cfqd, int sync,
  214. unsigned short prio)
  215. {
  216. const int base_slice = cfqd->cfq_slice[sync];
  217. WARN_ON(prio >= IOPRIO_BE_NR);
  218. return base_slice + (base_slice/CFQ_SLICE_SCALE * (4 - prio));
  219. }
  220. static inline int
  221. cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  222. {
  223. return cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio);
  224. }
  225. static inline void
  226. cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  227. {
  228. cfqq->slice_end = cfq_prio_to_slice(cfqd, cfqq) + jiffies;
  229. }
  230. /*
  231. * We need to wrap this check in cfq_cfqq_slice_new(), since ->slice_end
  232. * isn't valid until the first request from the dispatch is activated
  233. * and the slice time set.
  234. */
  235. static inline int cfq_slice_used(struct cfq_queue *cfqq)
  236. {
  237. if (cfq_cfqq_slice_new(cfqq))
  238. return 0;
  239. if (time_before(jiffies, cfqq->slice_end))
  240. return 0;
  241. return 1;
  242. }
  243. /*
  244. * Lifted from AS - choose which of rq1 and rq2 that is best served now.
  245. * We choose the request that is closest to the head right now. Distance
  246. * behind the head is penalized and only allowed to a certain extent.
  247. */
  248. static struct request *
  249. cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2)
  250. {
  251. sector_t last, s1, s2, d1 = 0, d2 = 0;
  252. unsigned long back_max;
  253. #define CFQ_RQ1_WRAP 0x01 /* request 1 wraps */
  254. #define CFQ_RQ2_WRAP 0x02 /* request 2 wraps */
  255. unsigned wrap = 0; /* bit mask: requests behind the disk head? */
  256. if (rq1 == NULL || rq1 == rq2)
  257. return rq2;
  258. if (rq2 == NULL)
  259. return rq1;
  260. if (rq_is_sync(rq1) && !rq_is_sync(rq2))
  261. return rq1;
  262. else if (rq_is_sync(rq2) && !rq_is_sync(rq1))
  263. return rq2;
  264. if (rq_is_meta(rq1) && !rq_is_meta(rq2))
  265. return rq1;
  266. else if (rq_is_meta(rq2) && !rq_is_meta(rq1))
  267. return rq2;
  268. s1 = rq1->sector;
  269. s2 = rq2->sector;
  270. last = cfqd->last_position;
  271. /*
  272. * by definition, 1KiB is 2 sectors
  273. */
  274. back_max = cfqd->cfq_back_max * 2;
  275. /*
  276. * Strict one way elevator _except_ in the case where we allow
  277. * short backward seeks which are biased as twice the cost of a
  278. * similar forward seek.
  279. */
  280. if (s1 >= last)
  281. d1 = s1 - last;
  282. else if (s1 + back_max >= last)
  283. d1 = (last - s1) * cfqd->cfq_back_penalty;
  284. else
  285. wrap |= CFQ_RQ1_WRAP;
  286. if (s2 >= last)
  287. d2 = s2 - last;
  288. else if (s2 + back_max >= last)
  289. d2 = (last - s2) * cfqd->cfq_back_penalty;
  290. else
  291. wrap |= CFQ_RQ2_WRAP;
  292. /* Found required data */
  293. /*
  294. * By doing switch() on the bit mask "wrap" we avoid having to
  295. * check two variables for all permutations: --> faster!
  296. */
  297. switch (wrap) {
  298. case 0: /* common case for CFQ: rq1 and rq2 not wrapped */
  299. if (d1 < d2)
  300. return rq1;
  301. else if (d2 < d1)
  302. return rq2;
  303. else {
  304. if (s1 >= s2)
  305. return rq1;
  306. else
  307. return rq2;
  308. }
  309. case CFQ_RQ2_WRAP:
  310. return rq1;
  311. case CFQ_RQ1_WRAP:
  312. return rq2;
  313. case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both rqs wrapped */
  314. default:
  315. /*
  316. * Since both rqs are wrapped,
  317. * start with the one that's further behind head
  318. * (--> only *one* back seek required),
  319. * since back seek takes more time than forward.
  320. */
  321. if (s1 <= s2)
  322. return rq1;
  323. else
  324. return rq2;
  325. }
  326. }
  327. /*
  328. * The below is leftmost cache rbtree addon
  329. */
  330. static struct rb_node *cfq_rb_first(struct cfq_rb_root *root)
  331. {
  332. if (!root->left)
  333. root->left = rb_first(&root->rb);
  334. return root->left;
  335. }
  336. static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
  337. {
  338. if (root->left == n)
  339. root->left = NULL;
  340. rb_erase(n, &root->rb);
  341. RB_CLEAR_NODE(n);
  342. }
  343. /*
  344. * would be nice to take fifo expire time into account as well
  345. */
  346. static struct request *
  347. cfq_find_next_rq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
  348. struct request *last)
  349. {
  350. struct rb_node *rbnext = rb_next(&last->rb_node);
  351. struct rb_node *rbprev = rb_prev(&last->rb_node);
  352. struct request *next = NULL, *prev = NULL;
  353. BUG_ON(RB_EMPTY_NODE(&last->rb_node));
  354. if (rbprev)
  355. prev = rb_entry_rq(rbprev);
  356. if (rbnext)
  357. next = rb_entry_rq(rbnext);
  358. else {
  359. rbnext = rb_first(&cfqq->sort_list);
  360. if (rbnext && rbnext != &last->rb_node)
  361. next = rb_entry_rq(rbnext);
  362. }
  363. return cfq_choose_req(cfqd, next, prev);
  364. }
  365. static unsigned long cfq_slice_offset(struct cfq_data *cfqd,
  366. struct cfq_queue *cfqq)
  367. {
  368. /*
  369. * just an approximation, should be ok.
  370. */
  371. return (cfqd->busy_queues - 1) * (cfq_prio_slice(cfqd, 1, 0) -
  372. cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio));
  373. }
  374. /*
  375. * The cfqd->service_tree holds all pending cfq_queue's that have
  376. * requests waiting to be processed. It is sorted in the order that
  377. * we will service the queues.
  378. */
  379. static void cfq_service_tree_add(struct cfq_data *cfqd,
  380. struct cfq_queue *cfqq, int add_front)
  381. {
  382. struct rb_node **p = &cfqd->service_tree.rb.rb_node;
  383. struct rb_node *parent = NULL;
  384. unsigned long rb_key;
  385. int left;
  386. if (!add_front) {
  387. rb_key = cfq_slice_offset(cfqd, cfqq) + jiffies;
  388. rb_key += cfqq->slice_resid;
  389. cfqq->slice_resid = 0;
  390. } else
  391. rb_key = 0;
  392. if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
  393. /*
  394. * same position, nothing more to do
  395. */
  396. if (rb_key == cfqq->rb_key)
  397. return;
  398. cfq_rb_erase(&cfqq->rb_node, &cfqd->service_tree);
  399. }
  400. left = 1;
  401. while (*p) {
  402. struct cfq_queue *__cfqq;
  403. struct rb_node **n;
  404. parent = *p;
  405. __cfqq = rb_entry(parent, struct cfq_queue, rb_node);
  406. /*
  407. * sort RT queues first, we always want to give
  408. * preference to them. IDLE queues goes to the back.
  409. * after that, sort on the next service time.
  410. */
  411. if (cfq_class_rt(cfqq) > cfq_class_rt(__cfqq))
  412. n = &(*p)->rb_left;
  413. else if (cfq_class_rt(cfqq) < cfq_class_rt(__cfqq))
  414. n = &(*p)->rb_right;
  415. else if (cfq_class_idle(cfqq) < cfq_class_idle(__cfqq))
  416. n = &(*p)->rb_left;
  417. else if (cfq_class_idle(cfqq) > cfq_class_idle(__cfqq))
  418. n = &(*p)->rb_right;
  419. else if (rb_key < __cfqq->rb_key)
  420. n = &(*p)->rb_left;
  421. else
  422. n = &(*p)->rb_right;
  423. if (n == &(*p)->rb_right)
  424. left = 0;
  425. p = n;
  426. }
  427. if (left)
  428. cfqd->service_tree.left = &cfqq->rb_node;
  429. cfqq->rb_key = rb_key;
  430. rb_link_node(&cfqq->rb_node, parent, p);
  431. rb_insert_color(&cfqq->rb_node, &cfqd->service_tree.rb);
  432. }
  433. /*
  434. * Update cfqq's position in the service tree.
  435. */
  436. static void cfq_resort_rr_list(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  437. {
  438. /*
  439. * Resorting requires the cfqq to be on the RR list already.
  440. */
  441. if (cfq_cfqq_on_rr(cfqq))
  442. cfq_service_tree_add(cfqd, cfqq, 0);
  443. }
  444. /*
  445. * add to busy list of queues for service, trying to be fair in ordering
  446. * the pending list according to last request service
  447. */
  448. static inline void
  449. cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  450. {
  451. BUG_ON(cfq_cfqq_on_rr(cfqq));
  452. cfq_mark_cfqq_on_rr(cfqq);
  453. cfqd->busy_queues++;
  454. cfq_resort_rr_list(cfqd, cfqq);
  455. }
  456. /*
  457. * Called when the cfqq no longer has requests pending, remove it from
  458. * the service tree.
  459. */
  460. static inline void
  461. cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  462. {
  463. BUG_ON(!cfq_cfqq_on_rr(cfqq));
  464. cfq_clear_cfqq_on_rr(cfqq);
  465. if (!RB_EMPTY_NODE(&cfqq->rb_node))
  466. cfq_rb_erase(&cfqq->rb_node, &cfqd->service_tree);
  467. BUG_ON(!cfqd->busy_queues);
  468. cfqd->busy_queues--;
  469. }
  470. /*
  471. * rb tree support functions
  472. */
  473. static inline void cfq_del_rq_rb(struct request *rq)
  474. {
  475. struct cfq_queue *cfqq = RQ_CFQQ(rq);
  476. struct cfq_data *cfqd = cfqq->cfqd;
  477. const int sync = rq_is_sync(rq);
  478. BUG_ON(!cfqq->queued[sync]);
  479. cfqq->queued[sync]--;
  480. elv_rb_del(&cfqq->sort_list, rq);
  481. if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list))
  482. cfq_del_cfqq_rr(cfqd, cfqq);
  483. }
  484. static void cfq_add_rq_rb(struct request *rq)
  485. {
  486. struct cfq_queue *cfqq = RQ_CFQQ(rq);
  487. struct cfq_data *cfqd = cfqq->cfqd;
  488. struct request *__alias;
  489. cfqq->queued[rq_is_sync(rq)]++;
  490. /*
  491. * looks a little odd, but the first insert might return an alias.
  492. * if that happens, put the alias on the dispatch list
  493. */
  494. while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL)
  495. cfq_dispatch_insert(cfqd->queue, __alias);
  496. if (!cfq_cfqq_on_rr(cfqq))
  497. cfq_add_cfqq_rr(cfqd, cfqq);
  498. /*
  499. * check if this request is a better next-serve candidate
  500. */
  501. cfqq->next_rq = cfq_choose_req(cfqd, cfqq->next_rq, rq);
  502. BUG_ON(!cfqq->next_rq);
  503. }
  504. static inline void
  505. cfq_reposition_rq_rb(struct cfq_queue *cfqq, struct request *rq)
  506. {
  507. elv_rb_del(&cfqq->sort_list, rq);
  508. cfqq->queued[rq_is_sync(rq)]--;
  509. cfq_add_rq_rb(rq);
  510. }
  511. static struct request *
  512. cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
  513. {
  514. struct task_struct *tsk = current;
  515. struct cfq_io_context *cic;
  516. struct cfq_queue *cfqq;
  517. cic = cfq_cic_rb_lookup(cfqd, tsk->io_context);
  518. if (!cic)
  519. return NULL;
  520. cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
  521. if (cfqq) {
  522. sector_t sector = bio->bi_sector + bio_sectors(bio);
  523. return elv_rb_find(&cfqq->sort_list, sector);
  524. }
  525. return NULL;
  526. }
  527. static void cfq_activate_request(struct request_queue *q, struct request *rq)
  528. {
  529. struct cfq_data *cfqd = q->elevator->elevator_data;
  530. cfqd->rq_in_driver++;
  531. /*
  532. * If the depth is larger 1, it really could be queueing. But lets
  533. * make the mark a little higher - idling could still be good for
  534. * low queueing, and a low queueing number could also just indicate
  535. * a SCSI mid layer like behaviour where limit+1 is often seen.
  536. */
  537. if (!cfqd->hw_tag && cfqd->rq_in_driver > 4)
  538. cfqd->hw_tag = 1;
  539. cfqd->last_position = rq->hard_sector + rq->hard_nr_sectors;
  540. }
  541. static void cfq_deactivate_request(struct request_queue *q, struct request *rq)
  542. {
  543. struct cfq_data *cfqd = q->elevator->elevator_data;
  544. WARN_ON(!cfqd->rq_in_driver);
  545. cfqd->rq_in_driver--;
  546. }
  547. static void cfq_remove_request(struct request *rq)
  548. {
  549. struct cfq_queue *cfqq = RQ_CFQQ(rq);
  550. if (cfqq->next_rq == rq)
  551. cfqq->next_rq = cfq_find_next_rq(cfqq->cfqd, cfqq, rq);
  552. list_del_init(&rq->queuelist);
  553. cfq_del_rq_rb(rq);
  554. if (rq_is_meta(rq)) {
  555. WARN_ON(!cfqq->meta_pending);
  556. cfqq->meta_pending--;
  557. }
  558. }
  559. static int cfq_merge(struct request_queue *q, struct request **req,
  560. struct bio *bio)
  561. {
  562. struct cfq_data *cfqd = q->elevator->elevator_data;
  563. struct request *__rq;
  564. __rq = cfq_find_rq_fmerge(cfqd, bio);
  565. if (__rq && elv_rq_merge_ok(__rq, bio)) {
  566. *req = __rq;
  567. return ELEVATOR_FRONT_MERGE;
  568. }
  569. return ELEVATOR_NO_MERGE;
  570. }
  571. static void cfq_merged_request(struct request_queue *q, struct request *req,
  572. int type)
  573. {
  574. if (type == ELEVATOR_FRONT_MERGE) {
  575. struct cfq_queue *cfqq = RQ_CFQQ(req);
  576. cfq_reposition_rq_rb(cfqq, req);
  577. }
  578. }
  579. static void
  580. cfq_merged_requests(struct request_queue *q, struct request *rq,
  581. struct request *next)
  582. {
  583. /*
  584. * reposition in fifo if next is older than rq
  585. */
  586. if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&
  587. time_before(next->start_time, rq->start_time))
  588. list_move(&rq->queuelist, &next->queuelist);
  589. cfq_remove_request(next);
  590. }
  591. static int cfq_allow_merge(struct request_queue *q, struct request *rq,
  592. struct bio *bio)
  593. {
  594. struct cfq_data *cfqd = q->elevator->elevator_data;
  595. struct cfq_io_context *cic;
  596. struct cfq_queue *cfqq;
  597. /*
  598. * Disallow merge of a sync bio into an async request.
  599. */
  600. if (cfq_bio_sync(bio) && !rq_is_sync(rq))
  601. return 0;
  602. /*
  603. * Lookup the cfqq that this bio will be queued with. Allow
  604. * merge only if rq is queued there.
  605. */
  606. cic = cfq_cic_rb_lookup(cfqd, current->io_context);
  607. if (!cic)
  608. return 0;
  609. cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
  610. if (cfqq == RQ_CFQQ(rq))
  611. return 1;
  612. return 0;
  613. }
  614. static inline void
  615. __cfq_set_active_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  616. {
  617. if (cfqq) {
  618. /*
  619. * stop potential idle class queues waiting service
  620. */
  621. del_timer(&cfqd->idle_class_timer);
  622. cfqq->slice_end = 0;
  623. cfq_clear_cfqq_must_alloc_slice(cfqq);
  624. cfq_clear_cfqq_fifo_expire(cfqq);
  625. cfq_mark_cfqq_slice_new(cfqq);
  626. cfq_clear_cfqq_queue_new(cfqq);
  627. }
  628. cfqd->active_queue = cfqq;
  629. }
  630. /*
  631. * current cfqq expired its slice (or was too idle), select new one
  632. */
  633. static void
  634. __cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
  635. int timed_out)
  636. {
  637. if (cfq_cfqq_wait_request(cfqq))
  638. del_timer(&cfqd->idle_slice_timer);
  639. cfq_clear_cfqq_must_dispatch(cfqq);
  640. cfq_clear_cfqq_wait_request(cfqq);
  641. /*
  642. * store what was left of this slice, if the queue idled/timed out
  643. */
  644. if (timed_out && !cfq_cfqq_slice_new(cfqq))
  645. cfqq->slice_resid = cfqq->slice_end - jiffies;
  646. cfq_resort_rr_list(cfqd, cfqq);
  647. if (cfqq == cfqd->active_queue)
  648. cfqd->active_queue = NULL;
  649. if (cfqd->active_cic) {
  650. put_io_context(cfqd->active_cic->ioc);
  651. cfqd->active_cic = NULL;
  652. }
  653. }
  654. static inline void cfq_slice_expired(struct cfq_data *cfqd, int timed_out)
  655. {
  656. struct cfq_queue *cfqq = cfqd->active_queue;
  657. if (cfqq)
  658. __cfq_slice_expired(cfqd, cfqq, timed_out);
  659. }
  660. /*
  661. * Get next queue for service. Unless we have a queue preemption,
  662. * we'll simply select the first cfqq in the service tree.
  663. */
  664. static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
  665. {
  666. struct cfq_queue *cfqq;
  667. struct rb_node *n;
  668. if (RB_EMPTY_ROOT(&cfqd->service_tree.rb))
  669. return NULL;
  670. n = cfq_rb_first(&cfqd->service_tree);
  671. cfqq = rb_entry(n, struct cfq_queue, rb_node);
  672. if (cfq_class_idle(cfqq)) {
  673. unsigned long end;
  674. /*
  675. * if we have idle queues and no rt or be queues had
  676. * pending requests, either allow immediate service if
  677. * the grace period has passed or arm the idle grace
  678. * timer
  679. */
  680. end = cfqd->last_end_request + CFQ_IDLE_GRACE;
  681. if (time_before(jiffies, end)) {
  682. mod_timer(&cfqd->idle_class_timer, end);
  683. cfqq = NULL;
  684. }
  685. }
  686. return cfqq;
  687. }
  688. /*
  689. * Get and set a new active queue for service.
  690. */
  691. static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd)
  692. {
  693. struct cfq_queue *cfqq;
  694. cfqq = cfq_get_next_queue(cfqd);
  695. __cfq_set_active_queue(cfqd, cfqq);
  696. return cfqq;
  697. }
  698. static inline sector_t cfq_dist_from_last(struct cfq_data *cfqd,
  699. struct request *rq)
  700. {
  701. if (rq->sector >= cfqd->last_position)
  702. return rq->sector - cfqd->last_position;
  703. else
  704. return cfqd->last_position - rq->sector;
  705. }
  706. static inline int cfq_rq_close(struct cfq_data *cfqd, struct request *rq)
  707. {
  708. struct cfq_io_context *cic = cfqd->active_cic;
  709. if (!sample_valid(cic->seek_samples))
  710. return 0;
  711. return cfq_dist_from_last(cfqd, rq) <= cic->seek_mean;
  712. }
  713. static int cfq_close_cooperator(struct cfq_data *cfq_data,
  714. struct cfq_queue *cfqq)
  715. {
  716. /*
  717. * We should notice if some of the queues are cooperating, eg
  718. * working closely on the same area of the disk. In that case,
  719. * we can group them together and don't waste time idling.
  720. */
  721. return 0;
  722. }
  723. #define CIC_SEEKY(cic) ((cic)->seek_mean > (8 * 1024))
  724. static void cfq_arm_slice_timer(struct cfq_data *cfqd)
  725. {
  726. struct cfq_queue *cfqq = cfqd->active_queue;
  727. struct cfq_io_context *cic;
  728. unsigned long sl;
  729. WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list));
  730. WARN_ON(cfq_cfqq_slice_new(cfqq));
  731. /*
  732. * idle is disabled, either manually or by past process history
  733. */
  734. if (!cfqd->cfq_slice_idle || !cfq_cfqq_idle_window(cfqq))
  735. return;
  736. /*
  737. * task has exited, don't wait
  738. */
  739. cic = cfqd->active_cic;
  740. if (!cic || !cic->ioc->task)
  741. return;
  742. /*
  743. * See if this prio level has a good candidate
  744. */
  745. if (cfq_close_cooperator(cfqd, cfqq) &&
  746. (sample_valid(cic->ttime_samples) && cic->ttime_mean > 2))
  747. return;
  748. cfq_mark_cfqq_must_dispatch(cfqq);
  749. cfq_mark_cfqq_wait_request(cfqq);
  750. /*
  751. * we don't want to idle for seeks, but we do want to allow
  752. * fair distribution of slice time for a process doing back-to-back
  753. * seeks. so allow a little bit of time for him to submit a new rq
  754. */
  755. sl = cfqd->cfq_slice_idle;
  756. if (sample_valid(cic->seek_samples) && CIC_SEEKY(cic))
  757. sl = min(sl, msecs_to_jiffies(CFQ_MIN_TT));
  758. mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
  759. }
  760. /*
  761. * Move request from internal lists to the request queue dispatch list.
  762. */
  763. static void cfq_dispatch_insert(struct request_queue *q, struct request *rq)
  764. {
  765. struct cfq_data *cfqd = q->elevator->elevator_data;
  766. struct cfq_queue *cfqq = RQ_CFQQ(rq);
  767. cfq_remove_request(rq);
  768. cfqq->dispatched++;
  769. elv_dispatch_sort(q, rq);
  770. if (cfq_cfqq_sync(cfqq))
  771. cfqd->sync_flight++;
  772. }
  773. /*
  774. * return expired entry, or NULL to just start from scratch in rbtree
  775. */
  776. static inline struct request *cfq_check_fifo(struct cfq_queue *cfqq)
  777. {
  778. struct cfq_data *cfqd = cfqq->cfqd;
  779. struct request *rq;
  780. int fifo;
  781. if (cfq_cfqq_fifo_expire(cfqq))
  782. return NULL;
  783. cfq_mark_cfqq_fifo_expire(cfqq);
  784. if (list_empty(&cfqq->fifo))
  785. return NULL;
  786. fifo = cfq_cfqq_sync(cfqq);
  787. rq = rq_entry_fifo(cfqq->fifo.next);
  788. if (time_before(jiffies, rq->start_time + cfqd->cfq_fifo_expire[fifo]))
  789. return NULL;
  790. return rq;
  791. }
  792. static inline int
  793. cfq_prio_to_maxrq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  794. {
  795. const int base_rq = cfqd->cfq_slice_async_rq;
  796. WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);
  797. return 2 * (base_rq + base_rq * (CFQ_PRIO_LISTS - 1 - cfqq->ioprio));
  798. }
  799. /*
  800. * Select a queue for service. If we have a current active queue,
  801. * check whether to continue servicing it, or retrieve and set a new one.
  802. */
  803. static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
  804. {
  805. struct cfq_queue *cfqq;
  806. cfqq = cfqd->active_queue;
  807. if (!cfqq)
  808. goto new_queue;
  809. /*
  810. * The active queue has run out of time, expire it and select new.
  811. */
  812. if (cfq_slice_used(cfqq))
  813. goto expire;
  814. /*
  815. * The active queue has requests and isn't expired, allow it to
  816. * dispatch.
  817. */
  818. if (!RB_EMPTY_ROOT(&cfqq->sort_list))
  819. goto keep_queue;
  820. /*
  821. * No requests pending. If the active queue still has requests in
  822. * flight or is idling for a new request, allow either of these
  823. * conditions to happen (or time out) before selecting a new queue.
  824. */
  825. if (timer_pending(&cfqd->idle_slice_timer) ||
  826. (cfqq->dispatched && cfq_cfqq_idle_window(cfqq))) {
  827. cfqq = NULL;
  828. goto keep_queue;
  829. }
  830. expire:
  831. cfq_slice_expired(cfqd, 0);
  832. new_queue:
  833. cfqq = cfq_set_active_queue(cfqd);
  834. keep_queue:
  835. return cfqq;
  836. }
  837. /*
  838. * Dispatch some requests from cfqq, moving them to the request queue
  839. * dispatch list.
  840. */
  841. static int
  842. __cfq_dispatch_requests(struct cfq_data *cfqd, struct cfq_queue *cfqq,
  843. int max_dispatch)
  844. {
  845. int dispatched = 0;
  846. BUG_ON(RB_EMPTY_ROOT(&cfqq->sort_list));
  847. do {
  848. struct request *rq;
  849. /*
  850. * follow expired path, else get first next available
  851. */
  852. if ((rq = cfq_check_fifo(cfqq)) == NULL)
  853. rq = cfqq->next_rq;
  854. /*
  855. * finally, insert request into driver dispatch list
  856. */
  857. cfq_dispatch_insert(cfqd->queue, rq);
  858. dispatched++;
  859. if (!cfqd->active_cic) {
  860. atomic_inc(&RQ_CIC(rq)->ioc->refcount);
  861. cfqd->active_cic = RQ_CIC(rq);
  862. }
  863. if (RB_EMPTY_ROOT(&cfqq->sort_list))
  864. break;
  865. } while (dispatched < max_dispatch);
  866. /*
  867. * expire an async queue immediately if it has used up its slice. idle
  868. * queue always expire after 1 dispatch round.
  869. */
  870. if (cfqd->busy_queues > 1 && ((!cfq_cfqq_sync(cfqq) &&
  871. dispatched >= cfq_prio_to_maxrq(cfqd, cfqq)) ||
  872. cfq_class_idle(cfqq))) {
  873. cfqq->slice_end = jiffies + 1;
  874. cfq_slice_expired(cfqd, 0);
  875. }
  876. return dispatched;
  877. }
  878. static inline int __cfq_forced_dispatch_cfqq(struct cfq_queue *cfqq)
  879. {
  880. int dispatched = 0;
  881. while (cfqq->next_rq) {
  882. cfq_dispatch_insert(cfqq->cfqd->queue, cfqq->next_rq);
  883. dispatched++;
  884. }
  885. BUG_ON(!list_empty(&cfqq->fifo));
  886. return dispatched;
  887. }
  888. /*
  889. * Drain our current requests. Used for barriers and when switching
  890. * io schedulers on-the-fly.
  891. */
  892. static int cfq_forced_dispatch(struct cfq_data *cfqd)
  893. {
  894. int dispatched = 0;
  895. struct rb_node *n;
  896. while ((n = cfq_rb_first(&cfqd->service_tree)) != NULL) {
  897. struct cfq_queue *cfqq = rb_entry(n, struct cfq_queue, rb_node);
  898. dispatched += __cfq_forced_dispatch_cfqq(cfqq);
  899. }
  900. cfq_slice_expired(cfqd, 0);
  901. BUG_ON(cfqd->busy_queues);
  902. return dispatched;
  903. }
  904. static int cfq_dispatch_requests(struct request_queue *q, int force)
  905. {
  906. struct cfq_data *cfqd = q->elevator->elevator_data;
  907. struct cfq_queue *cfqq;
  908. int dispatched;
  909. if (!cfqd->busy_queues)
  910. return 0;
  911. if (unlikely(force))
  912. return cfq_forced_dispatch(cfqd);
  913. dispatched = 0;
  914. while ((cfqq = cfq_select_queue(cfqd)) != NULL) {
  915. int max_dispatch;
  916. max_dispatch = cfqd->cfq_quantum;
  917. if (cfq_class_idle(cfqq))
  918. max_dispatch = 1;
  919. if (cfqq->dispatched >= max_dispatch) {
  920. if (cfqd->busy_queues > 1)
  921. break;
  922. if (cfqq->dispatched >= 4 * max_dispatch)
  923. break;
  924. }
  925. if (cfqd->sync_flight && !cfq_cfqq_sync(cfqq))
  926. break;
  927. cfq_clear_cfqq_must_dispatch(cfqq);
  928. cfq_clear_cfqq_wait_request(cfqq);
  929. del_timer(&cfqd->idle_slice_timer);
  930. dispatched += __cfq_dispatch_requests(cfqd, cfqq, max_dispatch);
  931. }
  932. return dispatched;
  933. }
  934. /*
  935. * task holds one reference to the queue, dropped when task exits. each rq
  936. * in-flight on this queue also holds a reference, dropped when rq is freed.
  937. *
  938. * queue lock must be held here.
  939. */
  940. static void cfq_put_queue(struct cfq_queue *cfqq)
  941. {
  942. struct cfq_data *cfqd = cfqq->cfqd;
  943. BUG_ON(atomic_read(&cfqq->ref) <= 0);
  944. if (!atomic_dec_and_test(&cfqq->ref))
  945. return;
  946. BUG_ON(rb_first(&cfqq->sort_list));
  947. BUG_ON(cfqq->allocated[READ] + cfqq->allocated[WRITE]);
  948. BUG_ON(cfq_cfqq_on_rr(cfqq));
  949. if (unlikely(cfqd->active_queue == cfqq)) {
  950. __cfq_slice_expired(cfqd, cfqq, 0);
  951. cfq_schedule_dispatch(cfqd);
  952. }
  953. kmem_cache_free(cfq_pool, cfqq);
  954. }
  955. static void cfq_free_io_context(struct io_context *ioc)
  956. {
  957. struct cfq_io_context *__cic;
  958. struct rb_node *n;
  959. int freed = 0;
  960. ioc->ioc_data = NULL;
  961. while ((n = rb_first(&ioc->cic_root)) != NULL) {
  962. __cic = rb_entry(n, struct cfq_io_context, rb_node);
  963. rb_erase(&__cic->rb_node, &ioc->cic_root);
  964. kmem_cache_free(cfq_ioc_pool, __cic);
  965. freed++;
  966. }
  967. elv_ioc_count_mod(ioc_count, -freed);
  968. if (ioc_gone && !elv_ioc_count_read(ioc_count))
  969. complete(ioc_gone);
  970. }
  971. static void cfq_exit_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  972. {
  973. if (unlikely(cfqq == cfqd->active_queue)) {
  974. __cfq_slice_expired(cfqd, cfqq, 0);
  975. cfq_schedule_dispatch(cfqd);
  976. }
  977. cfq_put_queue(cfqq);
  978. }
  979. static void __cfq_exit_single_io_context(struct cfq_data *cfqd,
  980. struct cfq_io_context *cic)
  981. {
  982. list_del_init(&cic->queue_list);
  983. smp_wmb();
  984. cic->key = NULL;
  985. if (cic->cfqq[ASYNC]) {
  986. cfq_exit_cfqq(cfqd, cic->cfqq[ASYNC]);
  987. cic->cfqq[ASYNC] = NULL;
  988. }
  989. if (cic->cfqq[SYNC]) {
  990. cfq_exit_cfqq(cfqd, cic->cfqq[SYNC]);
  991. cic->cfqq[SYNC] = NULL;
  992. }
  993. }
  994. static void cfq_exit_single_io_context(struct cfq_io_context *cic)
  995. {
  996. struct cfq_data *cfqd = cic->key;
  997. if (cfqd) {
  998. struct request_queue *q = cfqd->queue;
  999. spin_lock_irq(q->queue_lock);
  1000. __cfq_exit_single_io_context(cfqd, cic);
  1001. spin_unlock_irq(q->queue_lock);
  1002. }
  1003. }
  1004. /*
  1005. * The process that ioc belongs to has exited, we need to clean up
  1006. * and put the internal structures we have that belongs to that process.
  1007. */
  1008. static void cfq_exit_io_context(struct io_context *ioc)
  1009. {
  1010. struct cfq_io_context *__cic;
  1011. struct rb_node *n;
  1012. ioc->ioc_data = NULL;
  1013. /*
  1014. * put the reference this task is holding to the various queues
  1015. */
  1016. n = rb_first(&ioc->cic_root);
  1017. while (n != NULL) {
  1018. __cic = rb_entry(n, struct cfq_io_context, rb_node);
  1019. cfq_exit_single_io_context(__cic);
  1020. n = rb_next(n);
  1021. }
  1022. }
  1023. static struct cfq_io_context *
  1024. cfq_alloc_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
  1025. {
  1026. struct cfq_io_context *cic;
  1027. cic = kmem_cache_alloc_node(cfq_ioc_pool, gfp_mask | __GFP_ZERO,
  1028. cfqd->queue->node);
  1029. if (cic) {
  1030. cic->last_end_request = jiffies;
  1031. INIT_LIST_HEAD(&cic->queue_list);
  1032. cic->dtor = cfq_free_io_context;
  1033. cic->exit = cfq_exit_io_context;
  1034. elv_ioc_count_inc(ioc_count);
  1035. }
  1036. return cic;
  1037. }
  1038. static void cfq_init_prio_data(struct cfq_queue *cfqq)
  1039. {
  1040. struct task_struct *tsk = current;
  1041. int ioprio_class;
  1042. if (!cfq_cfqq_prio_changed(cfqq))
  1043. return;
  1044. ioprio_class = IOPRIO_PRIO_CLASS(tsk->ioprio);
  1045. switch (ioprio_class) {
  1046. default:
  1047. printk(KERN_ERR "cfq: bad prio %x\n", ioprio_class);
  1048. case IOPRIO_CLASS_NONE:
  1049. /*
  1050. * no prio set, place us in the middle of the BE classes
  1051. */
  1052. cfqq->ioprio = task_nice_ioprio(tsk);
  1053. cfqq->ioprio_class = IOPRIO_CLASS_BE;
  1054. break;
  1055. case IOPRIO_CLASS_RT:
  1056. cfqq->ioprio = task_ioprio(tsk);
  1057. cfqq->ioprio_class = IOPRIO_CLASS_RT;
  1058. break;
  1059. case IOPRIO_CLASS_BE:
  1060. cfqq->ioprio = task_ioprio(tsk);
  1061. cfqq->ioprio_class = IOPRIO_CLASS_BE;
  1062. break;
  1063. case IOPRIO_CLASS_IDLE:
  1064. cfqq->ioprio_class = IOPRIO_CLASS_IDLE;
  1065. cfqq->ioprio = 7;
  1066. cfq_clear_cfqq_idle_window(cfqq);
  1067. break;
  1068. }
  1069. /*
  1070. * keep track of original prio settings in case we have to temporarily
  1071. * elevate the priority of this queue
  1072. */
  1073. cfqq->org_ioprio = cfqq->ioprio;
  1074. cfqq->org_ioprio_class = cfqq->ioprio_class;
  1075. cfq_clear_cfqq_prio_changed(cfqq);
  1076. }
  1077. static inline void changed_ioprio(struct cfq_io_context *cic)
  1078. {
  1079. struct cfq_data *cfqd = cic->key;
  1080. struct cfq_queue *cfqq;
  1081. unsigned long flags;
  1082. if (unlikely(!cfqd))
  1083. return;
  1084. spin_lock_irqsave(cfqd->queue->queue_lock, flags);
  1085. cfqq = cic->cfqq[ASYNC];
  1086. if (cfqq) {
  1087. struct cfq_queue *new_cfqq;
  1088. new_cfqq = cfq_get_queue(cfqd, ASYNC, cic->ioc->task,
  1089. GFP_ATOMIC);
  1090. if (new_cfqq) {
  1091. cic->cfqq[ASYNC] = new_cfqq;
  1092. cfq_put_queue(cfqq);
  1093. }
  1094. }
  1095. cfqq = cic->cfqq[SYNC];
  1096. if (cfqq)
  1097. cfq_mark_cfqq_prio_changed(cfqq);
  1098. spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
  1099. }
  1100. static void cfq_ioc_set_ioprio(struct io_context *ioc)
  1101. {
  1102. struct cfq_io_context *cic;
  1103. struct rb_node *n;
  1104. ioc->ioprio_changed = 0;
  1105. n = rb_first(&ioc->cic_root);
  1106. while (n != NULL) {
  1107. cic = rb_entry(n, struct cfq_io_context, rb_node);
  1108. changed_ioprio(cic);
  1109. n = rb_next(n);
  1110. }
  1111. }
  1112. static struct cfq_queue *
  1113. cfq_find_alloc_queue(struct cfq_data *cfqd, int is_sync,
  1114. struct task_struct *tsk, gfp_t gfp_mask)
  1115. {
  1116. struct cfq_queue *cfqq, *new_cfqq = NULL;
  1117. struct cfq_io_context *cic;
  1118. retry:
  1119. cic = cfq_cic_rb_lookup(cfqd, tsk->io_context);
  1120. /* cic always exists here */
  1121. cfqq = cic_to_cfqq(cic, is_sync);
  1122. if (!cfqq) {
  1123. if (new_cfqq) {
  1124. cfqq = new_cfqq;
  1125. new_cfqq = NULL;
  1126. } else if (gfp_mask & __GFP_WAIT) {
  1127. /*
  1128. * Inform the allocator of the fact that we will
  1129. * just repeat this allocation if it fails, to allow
  1130. * the allocator to do whatever it needs to attempt to
  1131. * free memory.
  1132. */
  1133. spin_unlock_irq(cfqd->queue->queue_lock);
  1134. new_cfqq = kmem_cache_alloc_node(cfq_pool,
  1135. gfp_mask | __GFP_NOFAIL | __GFP_ZERO,
  1136. cfqd->queue->node);
  1137. spin_lock_irq(cfqd->queue->queue_lock);
  1138. goto retry;
  1139. } else {
  1140. cfqq = kmem_cache_alloc_node(cfq_pool,
  1141. gfp_mask | __GFP_ZERO,
  1142. cfqd->queue->node);
  1143. if (!cfqq)
  1144. goto out;
  1145. }
  1146. RB_CLEAR_NODE(&cfqq->rb_node);
  1147. INIT_LIST_HEAD(&cfqq->fifo);
  1148. atomic_set(&cfqq->ref, 0);
  1149. cfqq->cfqd = cfqd;
  1150. if (is_sync) {
  1151. cfq_mark_cfqq_idle_window(cfqq);
  1152. cfq_mark_cfqq_sync(cfqq);
  1153. }
  1154. cfq_mark_cfqq_prio_changed(cfqq);
  1155. cfq_mark_cfqq_queue_new(cfqq);
  1156. cfq_init_prio_data(cfqq);
  1157. }
  1158. if (new_cfqq)
  1159. kmem_cache_free(cfq_pool, new_cfqq);
  1160. out:
  1161. WARN_ON((gfp_mask & __GFP_WAIT) && !cfqq);
  1162. return cfqq;
  1163. }
  1164. static struct cfq_queue **
  1165. cfq_async_queue_prio(struct cfq_data *cfqd, int ioprio_class, int ioprio)
  1166. {
  1167. switch(ioprio_class) {
  1168. case IOPRIO_CLASS_RT:
  1169. return &cfqd->async_cfqq[0][ioprio];
  1170. case IOPRIO_CLASS_BE:
  1171. return &cfqd->async_cfqq[1][ioprio];
  1172. case IOPRIO_CLASS_IDLE:
  1173. return &cfqd->async_idle_cfqq;
  1174. default:
  1175. BUG();
  1176. }
  1177. }
  1178. static struct cfq_queue *
  1179. cfq_get_queue(struct cfq_data *cfqd, int is_sync, struct task_struct *tsk,
  1180. gfp_t gfp_mask)
  1181. {
  1182. const int ioprio = task_ioprio(tsk);
  1183. const int ioprio_class = task_ioprio_class(tsk);
  1184. struct cfq_queue **async_cfqq = NULL;
  1185. struct cfq_queue *cfqq = NULL;
  1186. if (!is_sync) {
  1187. async_cfqq = cfq_async_queue_prio(cfqd, ioprio_class, ioprio);
  1188. cfqq = *async_cfqq;
  1189. }
  1190. if (!cfqq)
  1191. cfqq = cfq_find_alloc_queue(cfqd, is_sync, tsk, gfp_mask);
  1192. /*
  1193. * pin the queue now that it's allocated, scheduler exit will prune it
  1194. */
  1195. if (!is_sync && !(*async_cfqq)) {
  1196. atomic_inc(&cfqq->ref);
  1197. *async_cfqq = cfqq;
  1198. }
  1199. atomic_inc(&cfqq->ref);
  1200. return cfqq;
  1201. }
  1202. /*
  1203. * We drop cfq io contexts lazily, so we may find a dead one.
  1204. */
  1205. static void
  1206. cfq_drop_dead_cic(struct io_context *ioc, struct cfq_io_context *cic)
  1207. {
  1208. WARN_ON(!list_empty(&cic->queue_list));
  1209. if (ioc->ioc_data == cic)
  1210. ioc->ioc_data = NULL;
  1211. rb_erase(&cic->rb_node, &ioc->cic_root);
  1212. kmem_cache_free(cfq_ioc_pool, cic);
  1213. elv_ioc_count_dec(ioc_count);
  1214. }
  1215. static struct cfq_io_context *
  1216. cfq_cic_rb_lookup(struct cfq_data *cfqd, struct io_context *ioc)
  1217. {
  1218. struct rb_node *n;
  1219. struct cfq_io_context *cic;
  1220. void *k, *key = cfqd;
  1221. if (unlikely(!ioc))
  1222. return NULL;
  1223. /*
  1224. * we maintain a last-hit cache, to avoid browsing over the tree
  1225. */
  1226. cic = ioc->ioc_data;
  1227. if (cic && cic->key == cfqd)
  1228. return cic;
  1229. restart:
  1230. n = ioc->cic_root.rb_node;
  1231. while (n) {
  1232. cic = rb_entry(n, struct cfq_io_context, rb_node);
  1233. /* ->key must be copied to avoid race with cfq_exit_queue() */
  1234. k = cic->key;
  1235. if (unlikely(!k)) {
  1236. cfq_drop_dead_cic(ioc, cic);
  1237. goto restart;
  1238. }
  1239. if (key < k)
  1240. n = n->rb_left;
  1241. else if (key > k)
  1242. n = n->rb_right;
  1243. else {
  1244. ioc->ioc_data = cic;
  1245. return cic;
  1246. }
  1247. }
  1248. return NULL;
  1249. }
  1250. static inline void
  1251. cfq_cic_link(struct cfq_data *cfqd, struct io_context *ioc,
  1252. struct cfq_io_context *cic)
  1253. {
  1254. struct rb_node **p;
  1255. struct rb_node *parent;
  1256. struct cfq_io_context *__cic;
  1257. unsigned long flags;
  1258. void *k;
  1259. cic->ioc = ioc;
  1260. cic->key = cfqd;
  1261. restart:
  1262. parent = NULL;
  1263. p = &ioc->cic_root.rb_node;
  1264. while (*p) {
  1265. parent = *p;
  1266. __cic = rb_entry(parent, struct cfq_io_context, rb_node);
  1267. /* ->key must be copied to avoid race with cfq_exit_queue() */
  1268. k = __cic->key;
  1269. if (unlikely(!k)) {
  1270. cfq_drop_dead_cic(ioc, __cic);
  1271. goto restart;
  1272. }
  1273. if (cic->key < k)
  1274. p = &(*p)->rb_left;
  1275. else if (cic->key > k)
  1276. p = &(*p)->rb_right;
  1277. else
  1278. BUG();
  1279. }
  1280. rb_link_node(&cic->rb_node, parent, p);
  1281. rb_insert_color(&cic->rb_node, &ioc->cic_root);
  1282. spin_lock_irqsave(cfqd->queue->queue_lock, flags);
  1283. list_add(&cic->queue_list, &cfqd->cic_list);
  1284. spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
  1285. }
  1286. /*
  1287. * Setup general io context and cfq io context. There can be several cfq
  1288. * io contexts per general io context, if this process is doing io to more
  1289. * than one device managed by cfq.
  1290. */
  1291. static struct cfq_io_context *
  1292. cfq_get_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
  1293. {
  1294. struct io_context *ioc = NULL;
  1295. struct cfq_io_context *cic;
  1296. might_sleep_if(gfp_mask & __GFP_WAIT);
  1297. ioc = get_io_context(gfp_mask, cfqd->queue->node);
  1298. if (!ioc)
  1299. return NULL;
  1300. cic = cfq_cic_rb_lookup(cfqd, ioc);
  1301. if (cic)
  1302. goto out;
  1303. cic = cfq_alloc_io_context(cfqd, gfp_mask);
  1304. if (cic == NULL)
  1305. goto err;
  1306. cfq_cic_link(cfqd, ioc, cic);
  1307. out:
  1308. smp_read_barrier_depends();
  1309. if (unlikely(ioc->ioprio_changed))
  1310. cfq_ioc_set_ioprio(ioc);
  1311. return cic;
  1312. err:
  1313. put_io_context(ioc);
  1314. return NULL;
  1315. }
  1316. static void
  1317. cfq_update_io_thinktime(struct cfq_data *cfqd, struct cfq_io_context *cic)
  1318. {
  1319. unsigned long elapsed = jiffies - cic->last_end_request;
  1320. unsigned long ttime = min(elapsed, 2UL * cfqd->cfq_slice_idle);
  1321. cic->ttime_samples = (7*cic->ttime_samples + 256) / 8;
  1322. cic->ttime_total = (7*cic->ttime_total + 256*ttime) / 8;
  1323. cic->ttime_mean = (cic->ttime_total + 128) / cic->ttime_samples;
  1324. }
  1325. static void
  1326. cfq_update_io_seektime(struct cfq_data *cfqd, struct cfq_io_context *cic,
  1327. struct request *rq)
  1328. {
  1329. sector_t sdist;
  1330. u64 total;
  1331. if (cic->last_request_pos < rq->sector)
  1332. sdist = rq->sector - cic->last_request_pos;
  1333. else
  1334. sdist = cic->last_request_pos - rq->sector;
  1335. /*
  1336. * Don't allow the seek distance to get too large from the
  1337. * odd fragment, pagein, etc
  1338. */
  1339. if (cic->seek_samples <= 60) /* second&third seek */
  1340. sdist = min(sdist, (cic->seek_mean * 4) + 2*1024*1024);
  1341. else
  1342. sdist = min(sdist, (cic->seek_mean * 4) + 2*1024*64);
  1343. cic->seek_samples = (7*cic->seek_samples + 256) / 8;
  1344. cic->seek_total = (7*cic->seek_total + (u64)256*sdist) / 8;
  1345. total = cic->seek_total + (cic->seek_samples/2);
  1346. do_div(total, cic->seek_samples);
  1347. cic->seek_mean = (sector_t)total;
  1348. }
  1349. /*
  1350. * Disable idle window if the process thinks too long or seeks so much that
  1351. * it doesn't matter
  1352. */
  1353. static void
  1354. cfq_update_idle_window(struct cfq_data *cfqd, struct cfq_queue *cfqq,
  1355. struct cfq_io_context *cic)
  1356. {
  1357. int enable_idle;
  1358. if (!cfq_cfqq_sync(cfqq))
  1359. return;
  1360. enable_idle = cfq_cfqq_idle_window(cfqq);
  1361. if (!cic->ioc->task || !cfqd->cfq_slice_idle ||
  1362. (cfqd->hw_tag && CIC_SEEKY(cic)))
  1363. enable_idle = 0;
  1364. else if (sample_valid(cic->ttime_samples)) {
  1365. if (cic->ttime_mean > cfqd->cfq_slice_idle)
  1366. enable_idle = 0;
  1367. else
  1368. enable_idle = 1;
  1369. }
  1370. if (enable_idle)
  1371. cfq_mark_cfqq_idle_window(cfqq);
  1372. else
  1373. cfq_clear_cfqq_idle_window(cfqq);
  1374. }
  1375. /*
  1376. * Check if new_cfqq should preempt the currently active queue. Return 0 for
  1377. * no or if we aren't sure, a 1 will cause a preempt.
  1378. */
  1379. static int
  1380. cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
  1381. struct request *rq)
  1382. {
  1383. struct cfq_queue *cfqq;
  1384. cfqq = cfqd->active_queue;
  1385. if (!cfqq)
  1386. return 0;
  1387. if (cfq_slice_used(cfqq))
  1388. return 1;
  1389. if (cfq_class_idle(new_cfqq))
  1390. return 0;
  1391. if (cfq_class_idle(cfqq))
  1392. return 1;
  1393. /*
  1394. * if the new request is sync, but the currently running queue is
  1395. * not, let the sync request have priority.
  1396. */
  1397. if (rq_is_sync(rq) && !cfq_cfqq_sync(cfqq))
  1398. return 1;
  1399. /*
  1400. * So both queues are sync. Let the new request get disk time if
  1401. * it's a metadata request and the current queue is doing regular IO.
  1402. */
  1403. if (rq_is_meta(rq) && !cfqq->meta_pending)
  1404. return 1;
  1405. if (!cfqd->active_cic || !cfq_cfqq_wait_request(cfqq))
  1406. return 0;
  1407. /*
  1408. * if this request is as-good as one we would expect from the
  1409. * current cfqq, let it preempt
  1410. */
  1411. if (cfq_rq_close(cfqd, rq))
  1412. return 1;
  1413. return 0;
  1414. }
  1415. /*
  1416. * cfqq preempts the active queue. if we allowed preempt with no slice left,
  1417. * let it have half of its nominal slice.
  1418. */
  1419. static void cfq_preempt_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  1420. {
  1421. cfq_slice_expired(cfqd, 1);
  1422. /*
  1423. * Put the new queue at the front of the of the current list,
  1424. * so we know that it will be selected next.
  1425. */
  1426. BUG_ON(!cfq_cfqq_on_rr(cfqq));
  1427. cfq_service_tree_add(cfqd, cfqq, 1);
  1428. cfqq->slice_end = 0;
  1429. cfq_mark_cfqq_slice_new(cfqq);
  1430. }
  1431. /*
  1432. * Called when a new fs request (rq) is added (to cfqq). Check if there's
  1433. * something we should do about it
  1434. */
  1435. static void
  1436. cfq_rq_enqueued(struct cfq_data *cfqd, struct cfq_queue *cfqq,
  1437. struct request *rq)
  1438. {
  1439. struct cfq_io_context *cic = RQ_CIC(rq);
  1440. if (rq_is_meta(rq))
  1441. cfqq->meta_pending++;
  1442. cfq_update_io_thinktime(cfqd, cic);
  1443. cfq_update_io_seektime(cfqd, cic, rq);
  1444. cfq_update_idle_window(cfqd, cfqq, cic);
  1445. cic->last_request_pos = rq->sector + rq->nr_sectors;
  1446. if (cfqq == cfqd->active_queue) {
  1447. /*
  1448. * if we are waiting for a request for this queue, let it rip
  1449. * immediately and flag that we must not expire this queue
  1450. * just now
  1451. */
  1452. if (cfq_cfqq_wait_request(cfqq)) {
  1453. cfq_mark_cfqq_must_dispatch(cfqq);
  1454. del_timer(&cfqd->idle_slice_timer);
  1455. blk_start_queueing(cfqd->queue);
  1456. }
  1457. } else if (cfq_should_preempt(cfqd, cfqq, rq)) {
  1458. /*
  1459. * not the active queue - expire current slice if it is
  1460. * idle and has expired it's mean thinktime or this new queue
  1461. * has some old slice time left and is of higher priority
  1462. */
  1463. cfq_preempt_queue(cfqd, cfqq);
  1464. cfq_mark_cfqq_must_dispatch(cfqq);
  1465. blk_start_queueing(cfqd->queue);
  1466. }
  1467. }
  1468. static void cfq_insert_request(struct request_queue *q, struct request *rq)
  1469. {
  1470. struct cfq_data *cfqd = q->elevator->elevator_data;
  1471. struct cfq_queue *cfqq = RQ_CFQQ(rq);
  1472. cfq_init_prio_data(cfqq);
  1473. cfq_add_rq_rb(rq);
  1474. list_add_tail(&rq->queuelist, &cfqq->fifo);
  1475. cfq_rq_enqueued(cfqd, cfqq, rq);
  1476. }
  1477. static void cfq_completed_request(struct request_queue *q, struct request *rq)
  1478. {
  1479. struct cfq_queue *cfqq = RQ_CFQQ(rq);
  1480. struct cfq_data *cfqd = cfqq->cfqd;
  1481. const int sync = rq_is_sync(rq);
  1482. unsigned long now;
  1483. now = jiffies;
  1484. WARN_ON(!cfqd->rq_in_driver);
  1485. WARN_ON(!cfqq->dispatched);
  1486. cfqd->rq_in_driver--;
  1487. cfqq->dispatched--;
  1488. if (cfq_cfqq_sync(cfqq))
  1489. cfqd->sync_flight--;
  1490. if (!cfq_class_idle(cfqq))
  1491. cfqd->last_end_request = now;
  1492. if (sync)
  1493. RQ_CIC(rq)->last_end_request = now;
  1494. /*
  1495. * If this is the active queue, check if it needs to be expired,
  1496. * or if we want to idle in case it has no pending requests.
  1497. */
  1498. if (cfqd->active_queue == cfqq) {
  1499. if (cfq_cfqq_slice_new(cfqq)) {
  1500. cfq_set_prio_slice(cfqd, cfqq);
  1501. cfq_clear_cfqq_slice_new(cfqq);
  1502. }
  1503. if (cfq_slice_used(cfqq))
  1504. cfq_slice_expired(cfqd, 1);
  1505. else if (sync && RB_EMPTY_ROOT(&cfqq->sort_list))
  1506. cfq_arm_slice_timer(cfqd);
  1507. }
  1508. if (!cfqd->rq_in_driver)
  1509. cfq_schedule_dispatch(cfqd);
  1510. }
  1511. /*
  1512. * we temporarily boost lower priority queues if they are holding fs exclusive
  1513. * resources. they are boosted to normal prio (CLASS_BE/4)
  1514. */
  1515. static void cfq_prio_boost(struct cfq_queue *cfqq)
  1516. {
  1517. if (has_fs_excl()) {
  1518. /*
  1519. * boost idle prio on transactions that would lock out other
  1520. * users of the filesystem
  1521. */
  1522. if (cfq_class_idle(cfqq))
  1523. cfqq->ioprio_class = IOPRIO_CLASS_BE;
  1524. if (cfqq->ioprio > IOPRIO_NORM)
  1525. cfqq->ioprio = IOPRIO_NORM;
  1526. } else {
  1527. /*
  1528. * check if we need to unboost the queue
  1529. */
  1530. if (cfqq->ioprio_class != cfqq->org_ioprio_class)
  1531. cfqq->ioprio_class = cfqq->org_ioprio_class;
  1532. if (cfqq->ioprio != cfqq->org_ioprio)
  1533. cfqq->ioprio = cfqq->org_ioprio;
  1534. }
  1535. }
  1536. static inline int __cfq_may_queue(struct cfq_queue *cfqq)
  1537. {
  1538. if ((cfq_cfqq_wait_request(cfqq) || cfq_cfqq_must_alloc(cfqq)) &&
  1539. !cfq_cfqq_must_alloc_slice(cfqq)) {
  1540. cfq_mark_cfqq_must_alloc_slice(cfqq);
  1541. return ELV_MQUEUE_MUST;
  1542. }
  1543. return ELV_MQUEUE_MAY;
  1544. }
  1545. static int cfq_may_queue(struct request_queue *q, int rw)
  1546. {
  1547. struct cfq_data *cfqd = q->elevator->elevator_data;
  1548. struct task_struct *tsk = current;
  1549. struct cfq_io_context *cic;
  1550. struct cfq_queue *cfqq;
  1551. /*
  1552. * don't force setup of a queue from here, as a call to may_queue
  1553. * does not necessarily imply that a request actually will be queued.
  1554. * so just lookup a possibly existing queue, or return 'may queue'
  1555. * if that fails
  1556. */
  1557. cic = cfq_cic_rb_lookup(cfqd, tsk->io_context);
  1558. if (!cic)
  1559. return ELV_MQUEUE_MAY;
  1560. cfqq = cic_to_cfqq(cic, rw & REQ_RW_SYNC);
  1561. if (cfqq) {
  1562. cfq_init_prio_data(cfqq);
  1563. cfq_prio_boost(cfqq);
  1564. return __cfq_may_queue(cfqq);
  1565. }
  1566. return ELV_MQUEUE_MAY;
  1567. }
  1568. /*
  1569. * queue lock held here
  1570. */
  1571. static void cfq_put_request(struct request *rq)
  1572. {
  1573. struct cfq_queue *cfqq = RQ_CFQQ(rq);
  1574. if (cfqq) {
  1575. const int rw = rq_data_dir(rq);
  1576. BUG_ON(!cfqq->allocated[rw]);
  1577. cfqq->allocated[rw]--;
  1578. put_io_context(RQ_CIC(rq)->ioc);
  1579. rq->elevator_private = NULL;
  1580. rq->elevator_private2 = NULL;
  1581. cfq_put_queue(cfqq);
  1582. }
  1583. }
  1584. /*
  1585. * Allocate cfq data structures associated with this request.
  1586. */
  1587. static int
  1588. cfq_set_request(struct request_queue *q, struct request *rq, gfp_t gfp_mask)
  1589. {
  1590. struct cfq_data *cfqd = q->elevator->elevator_data;
  1591. struct task_struct *tsk = current;
  1592. struct cfq_io_context *cic;
  1593. const int rw = rq_data_dir(rq);
  1594. const int is_sync = rq_is_sync(rq);
  1595. struct cfq_queue *cfqq;
  1596. unsigned long flags;
  1597. might_sleep_if(gfp_mask & __GFP_WAIT);
  1598. cic = cfq_get_io_context(cfqd, gfp_mask);
  1599. spin_lock_irqsave(q->queue_lock, flags);
  1600. if (!cic)
  1601. goto queue_fail;
  1602. cfqq = cic_to_cfqq(cic, is_sync);
  1603. if (!cfqq) {
  1604. cfqq = cfq_get_queue(cfqd, is_sync, tsk, gfp_mask);
  1605. if (!cfqq)
  1606. goto queue_fail;
  1607. cic_set_cfqq(cic, cfqq, is_sync);
  1608. }
  1609. cfqq->allocated[rw]++;
  1610. cfq_clear_cfqq_must_alloc(cfqq);
  1611. atomic_inc(&cfqq->ref);
  1612. spin_unlock_irqrestore(q->queue_lock, flags);
  1613. rq->elevator_private = cic;
  1614. rq->elevator_private2 = cfqq;
  1615. return 0;
  1616. queue_fail:
  1617. if (cic)
  1618. put_io_context(cic->ioc);
  1619. cfq_schedule_dispatch(cfqd);
  1620. spin_unlock_irqrestore(q->queue_lock, flags);
  1621. return 1;
  1622. }
  1623. static void cfq_kick_queue(struct work_struct *work)
  1624. {
  1625. struct cfq_data *cfqd =
  1626. container_of(work, struct cfq_data, unplug_work);
  1627. struct request_queue *q = cfqd->queue;
  1628. unsigned long flags;
  1629. spin_lock_irqsave(q->queue_lock, flags);
  1630. blk_start_queueing(q);
  1631. spin_unlock_irqrestore(q->queue_lock, flags);
  1632. }
  1633. /*
  1634. * Timer running if the active_queue is currently idling inside its time slice
  1635. */
  1636. static void cfq_idle_slice_timer(unsigned long data)
  1637. {
  1638. struct cfq_data *cfqd = (struct cfq_data *) data;
  1639. struct cfq_queue *cfqq;
  1640. unsigned long flags;
  1641. int timed_out = 1;
  1642. spin_lock_irqsave(cfqd->queue->queue_lock, flags);
  1643. if ((cfqq = cfqd->active_queue) != NULL) {
  1644. timed_out = 0;
  1645. /*
  1646. * expired
  1647. */
  1648. if (cfq_slice_used(cfqq))
  1649. goto expire;
  1650. /*
  1651. * only expire and reinvoke request handler, if there are
  1652. * other queues with pending requests
  1653. */
  1654. if (!cfqd->busy_queues)
  1655. goto out_cont;
  1656. /*
  1657. * not expired and it has a request pending, let it dispatch
  1658. */
  1659. if (!RB_EMPTY_ROOT(&cfqq->sort_list)) {
  1660. cfq_mark_cfqq_must_dispatch(cfqq);
  1661. goto out_kick;
  1662. }
  1663. }
  1664. expire:
  1665. cfq_slice_expired(cfqd, timed_out);
  1666. out_kick:
  1667. cfq_schedule_dispatch(cfqd);
  1668. out_cont:
  1669. spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
  1670. }
  1671. /*
  1672. * Timer running if an idle class queue is waiting for service
  1673. */
  1674. static void cfq_idle_class_timer(unsigned long data)
  1675. {
  1676. struct cfq_data *cfqd = (struct cfq_data *) data;
  1677. unsigned long flags, end;
  1678. spin_lock_irqsave(cfqd->queue->queue_lock, flags);
  1679. /*
  1680. * race with a non-idle queue, reset timer
  1681. */
  1682. end = cfqd->last_end_request + CFQ_IDLE_GRACE;
  1683. if (!time_after_eq(jiffies, end))
  1684. mod_timer(&cfqd->idle_class_timer, end);
  1685. else
  1686. cfq_schedule_dispatch(cfqd);
  1687. spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
  1688. }
  1689. static void cfq_shutdown_timer_wq(struct cfq_data *cfqd)
  1690. {
  1691. del_timer_sync(&cfqd->idle_slice_timer);
  1692. del_timer_sync(&cfqd->idle_class_timer);
  1693. blk_sync_queue(cfqd->queue);
  1694. }
  1695. static void cfq_put_async_queues(struct cfq_data *cfqd)
  1696. {
  1697. int i;
  1698. for (i = 0; i < IOPRIO_BE_NR; i++) {
  1699. if (cfqd->async_cfqq[0][i])
  1700. cfq_put_queue(cfqd->async_cfqq[0][i]);
  1701. if (cfqd->async_cfqq[1][i])
  1702. cfq_put_queue(cfqd->async_cfqq[1][i]);
  1703. if (cfqd->async_idle_cfqq)
  1704. cfq_put_queue(cfqd->async_idle_cfqq);
  1705. }
  1706. }
  1707. static void cfq_exit_queue(elevator_t *e)
  1708. {
  1709. struct cfq_data *cfqd = e->elevator_data;
  1710. struct request_queue *q = cfqd->queue;
  1711. cfq_shutdown_timer_wq(cfqd);
  1712. spin_lock_irq(q->queue_lock);
  1713. if (cfqd->active_queue)
  1714. __cfq_slice_expired(cfqd, cfqd->active_queue, 0);
  1715. while (!list_empty(&cfqd->cic_list)) {
  1716. struct cfq_io_context *cic = list_entry(cfqd->cic_list.next,
  1717. struct cfq_io_context,
  1718. queue_list);
  1719. __cfq_exit_single_io_context(cfqd, cic);
  1720. }
  1721. cfq_put_async_queues(cfqd);
  1722. spin_unlock_irq(q->queue_lock);
  1723. cfq_shutdown_timer_wq(cfqd);
  1724. kfree(cfqd);
  1725. }
  1726. static void *cfq_init_queue(struct request_queue *q)
  1727. {
  1728. struct cfq_data *cfqd;
  1729. cfqd = kmalloc_node(sizeof(*cfqd), GFP_KERNEL | __GFP_ZERO, q->node);
  1730. if (!cfqd)
  1731. return NULL;
  1732. cfqd->service_tree = CFQ_RB_ROOT;
  1733. INIT_LIST_HEAD(&cfqd->cic_list);
  1734. cfqd->queue = q;
  1735. init_timer(&cfqd->idle_slice_timer);
  1736. cfqd->idle_slice_timer.function = cfq_idle_slice_timer;
  1737. cfqd->idle_slice_timer.data = (unsigned long) cfqd;
  1738. init_timer(&cfqd->idle_class_timer);
  1739. cfqd->idle_class_timer.function = cfq_idle_class_timer;
  1740. cfqd->idle_class_timer.data = (unsigned long) cfqd;
  1741. INIT_WORK(&cfqd->unplug_work, cfq_kick_queue);
  1742. cfqd->cfq_quantum = cfq_quantum;
  1743. cfqd->cfq_fifo_expire[0] = cfq_fifo_expire[0];
  1744. cfqd->cfq_fifo_expire[1] = cfq_fifo_expire[1];
  1745. cfqd->cfq_back_max = cfq_back_max;
  1746. cfqd->cfq_back_penalty = cfq_back_penalty;
  1747. cfqd->cfq_slice[0] = cfq_slice_async;
  1748. cfqd->cfq_slice[1] = cfq_slice_sync;
  1749. cfqd->cfq_slice_async_rq = cfq_slice_async_rq;
  1750. cfqd->cfq_slice_idle = cfq_slice_idle;
  1751. return cfqd;
  1752. }
  1753. static void cfq_slab_kill(void)
  1754. {
  1755. if (cfq_pool)
  1756. kmem_cache_destroy(cfq_pool);
  1757. if (cfq_ioc_pool)
  1758. kmem_cache_destroy(cfq_ioc_pool);
  1759. }
  1760. static int __init cfq_slab_setup(void)
  1761. {
  1762. cfq_pool = KMEM_CACHE(cfq_queue, 0);
  1763. if (!cfq_pool)
  1764. goto fail;
  1765. cfq_ioc_pool = KMEM_CACHE(cfq_io_context, 0);
  1766. if (!cfq_ioc_pool)
  1767. goto fail;
  1768. return 0;
  1769. fail:
  1770. cfq_slab_kill();
  1771. return -ENOMEM;
  1772. }
  1773. /*
  1774. * sysfs parts below -->
  1775. */
  1776. static ssize_t
  1777. cfq_var_show(unsigned int var, char *page)
  1778. {
  1779. return sprintf(page, "%d\n", var);
  1780. }
  1781. static ssize_t
  1782. cfq_var_store(unsigned int *var, const char *page, size_t count)
  1783. {
  1784. char *p = (char *) page;
  1785. *var = simple_strtoul(p, &p, 10);
  1786. return count;
  1787. }
  1788. #define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \
  1789. static ssize_t __FUNC(elevator_t *e, char *page) \
  1790. { \
  1791. struct cfq_data *cfqd = e->elevator_data; \
  1792. unsigned int __data = __VAR; \
  1793. if (__CONV) \
  1794. __data = jiffies_to_msecs(__data); \
  1795. return cfq_var_show(__data, (page)); \
  1796. }
  1797. SHOW_FUNCTION(cfq_quantum_show, cfqd->cfq_quantum, 0);
  1798. SHOW_FUNCTION(cfq_fifo_expire_sync_show, cfqd->cfq_fifo_expire[1], 1);
  1799. SHOW_FUNCTION(cfq_fifo_expire_async_show, cfqd->cfq_fifo_expire[0], 1);
  1800. SHOW_FUNCTION(cfq_back_seek_max_show, cfqd->cfq_back_max, 0);
  1801. SHOW_FUNCTION(cfq_back_seek_penalty_show, cfqd->cfq_back_penalty, 0);
  1802. SHOW_FUNCTION(cfq_slice_idle_show, cfqd->cfq_slice_idle, 1);
  1803. SHOW_FUNCTION(cfq_slice_sync_show, cfqd->cfq_slice[1], 1);
  1804. SHOW_FUNCTION(cfq_slice_async_show, cfqd->cfq_slice[0], 1);
  1805. SHOW_FUNCTION(cfq_slice_async_rq_show, cfqd->cfq_slice_async_rq, 0);
  1806. #undef SHOW_FUNCTION
  1807. #define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \
  1808. static ssize_t __FUNC(elevator_t *e, const char *page, size_t count) \
  1809. { \
  1810. struct cfq_data *cfqd = e->elevator_data; \
  1811. unsigned int __data; \
  1812. int ret = cfq_var_store(&__data, (page), count); \
  1813. if (__data < (MIN)) \
  1814. __data = (MIN); \
  1815. else if (__data > (MAX)) \
  1816. __data = (MAX); \
  1817. if (__CONV) \
  1818. *(__PTR) = msecs_to_jiffies(__data); \
  1819. else \
  1820. *(__PTR) = __data; \
  1821. return ret; \
  1822. }
  1823. STORE_FUNCTION(cfq_quantum_store, &cfqd->cfq_quantum, 1, UINT_MAX, 0);
  1824. STORE_FUNCTION(cfq_fifo_expire_sync_store, &cfqd->cfq_fifo_expire[1], 1, UINT_MAX, 1);
  1825. STORE_FUNCTION(cfq_fifo_expire_async_store, &cfqd->cfq_fifo_expire[0], 1, UINT_MAX, 1);
  1826. STORE_FUNCTION(cfq_back_seek_max_store, &cfqd->cfq_back_max, 0, UINT_MAX, 0);
  1827. STORE_FUNCTION(cfq_back_seek_penalty_store, &cfqd->cfq_back_penalty, 1, UINT_MAX, 0);
  1828. STORE_FUNCTION(cfq_slice_idle_store, &cfqd->cfq_slice_idle, 0, UINT_MAX, 1);
  1829. STORE_FUNCTION(cfq_slice_sync_store, &cfqd->cfq_slice[1], 1, UINT_MAX, 1);
  1830. STORE_FUNCTION(cfq_slice_async_store, &cfqd->cfq_slice[0], 1, UINT_MAX, 1);
  1831. STORE_FUNCTION(cfq_slice_async_rq_store, &cfqd->cfq_slice_async_rq, 1, UINT_MAX, 0);
  1832. #undef STORE_FUNCTION
  1833. #define CFQ_ATTR(name) \
  1834. __ATTR(name, S_IRUGO|S_IWUSR, cfq_##name##_show, cfq_##name##_store)
  1835. static struct elv_fs_entry cfq_attrs[] = {
  1836. CFQ_ATTR(quantum),
  1837. CFQ_ATTR(fifo_expire_sync),
  1838. CFQ_ATTR(fifo_expire_async),
  1839. CFQ_ATTR(back_seek_max),
  1840. CFQ_ATTR(back_seek_penalty),
  1841. CFQ_ATTR(slice_sync),
  1842. CFQ_ATTR(slice_async),
  1843. CFQ_ATTR(slice_async_rq),
  1844. CFQ_ATTR(slice_idle),
  1845. __ATTR_NULL
  1846. };
  1847. static struct elevator_type iosched_cfq = {
  1848. .ops = {
  1849. .elevator_merge_fn = cfq_merge,
  1850. .elevator_merged_fn = cfq_merged_request,
  1851. .elevator_merge_req_fn = cfq_merged_requests,
  1852. .elevator_allow_merge_fn = cfq_allow_merge,
  1853. .elevator_dispatch_fn = cfq_dispatch_requests,
  1854. .elevator_add_req_fn = cfq_insert_request,
  1855. .elevator_activate_req_fn = cfq_activate_request,
  1856. .elevator_deactivate_req_fn = cfq_deactivate_request,
  1857. .elevator_queue_empty_fn = cfq_queue_empty,
  1858. .elevator_completed_req_fn = cfq_completed_request,
  1859. .elevator_former_req_fn = elv_rb_former_request,
  1860. .elevator_latter_req_fn = elv_rb_latter_request,
  1861. .elevator_set_req_fn = cfq_set_request,
  1862. .elevator_put_req_fn = cfq_put_request,
  1863. .elevator_may_queue_fn = cfq_may_queue,
  1864. .elevator_init_fn = cfq_init_queue,
  1865. .elevator_exit_fn = cfq_exit_queue,
  1866. .trim = cfq_free_io_context,
  1867. },
  1868. .elevator_attrs = cfq_attrs,
  1869. .elevator_name = "cfq",
  1870. .elevator_owner = THIS_MODULE,
  1871. };
  1872. static int __init cfq_init(void)
  1873. {
  1874. int ret;
  1875. /*
  1876. * could be 0 on HZ < 1000 setups
  1877. */
  1878. if (!cfq_slice_async)
  1879. cfq_slice_async = 1;
  1880. if (!cfq_slice_idle)
  1881. cfq_slice_idle = 1;
  1882. if (cfq_slab_setup())
  1883. return -ENOMEM;
  1884. ret = elv_register(&iosched_cfq);
  1885. if (ret)
  1886. cfq_slab_kill();
  1887. return ret;
  1888. }
  1889. static void __exit cfq_exit(void)
  1890. {
  1891. DECLARE_COMPLETION_ONSTACK(all_gone);
  1892. elv_unregister(&iosched_cfq);
  1893. ioc_gone = &all_gone;
  1894. /* ioc_gone's update must be visible before reading ioc_count */
  1895. smp_wmb();
  1896. if (elv_ioc_count_read(ioc_count))
  1897. wait_for_completion(ioc_gone);
  1898. synchronize_rcu();
  1899. cfq_slab_kill();
  1900. }
  1901. module_init(cfq_init);
  1902. module_exit(cfq_exit);
  1903. MODULE_AUTHOR("Jens Axboe");
  1904. MODULE_LICENSE("GPL");
  1905. MODULE_DESCRIPTION("Completely Fair Queueing IO scheduler");