cfq-iosched.c 53 KB

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