cfq-iosched.c 99 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183318431853186318731883189319031913192319331943195319631973198319932003201320232033204320532063207320832093210321132123213321432153216321732183219322032213222322332243225322632273228322932303231323232333234323532363237323832393240324132423243324432453246324732483249325032513252325332543255325632573258325932603261326232633264326532663267326832693270327132723273327432753276327732783279328032813282328332843285328632873288328932903291329232933294329532963297329832993300330133023303330433053306330733083309331033113312331333143315331633173318331933203321332233233324332533263327332833293330333133323333333433353336333733383339334033413342334333443345334633473348334933503351335233533354335533563357335833593360336133623363336433653366336733683369337033713372337333743375337633773378337933803381338233833384338533863387338833893390339133923393339433953396339733983399340034013402340334043405340634073408340934103411341234133414341534163417341834193420342134223423342434253426342734283429343034313432343334343435343634373438343934403441344234433444344534463447344834493450345134523453345434553456345734583459346034613462346334643465346634673468346934703471347234733474347534763477347834793480348134823483348434853486348734883489349034913492349334943495349634973498349935003501350235033504350535063507350835093510351135123513351435153516351735183519352035213522352335243525352635273528352935303531353235333534353535363537353835393540354135423543354435453546354735483549355035513552355335543555355635573558355935603561356235633564356535663567356835693570357135723573357435753576357735783579358035813582358335843585358635873588358935903591359235933594359535963597359835993600360136023603360436053606360736083609361036113612361336143615361636173618361936203621362236233624362536263627362836293630363136323633363436353636363736383639364036413642364336443645364636473648364936503651365236533654365536563657365836593660366136623663366436653666366736683669367036713672367336743675367636773678367936803681368236833684368536863687368836893690369136923693369436953696369736983699370037013702370337043705370637073708370937103711371237133714371537163717371837193720372137223723372437253726372737283729373037313732373337343735373637373738373937403741374237433744374537463747374837493750375137523753375437553756375737583759376037613762376337643765376637673768376937703771377237733774377537763777377837793780378137823783378437853786378737883789379037913792379337943795379637973798379938003801380238033804380538063807380838093810381138123813381438153816381738183819382038213822382338243825382638273828382938303831383238333834383538363837383838393840384138423843384438453846384738483849385038513852385338543855385638573858385938603861386238633864386538663867386838693870387138723873387438753876387738783879388038813882388338843885388638873888388938903891389238933894389538963897389838993900390139023903390439053906390739083909391039113912391339143915391639173918391939203921392239233924392539263927392839293930
  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/slab.h>
  11. #include <linux/blkdev.h>
  12. #include <linux/elevator.h>
  13. #include <linux/jiffies.h>
  14. #include <linux/rbtree.h>
  15. #include <linux/ioprio.h>
  16. #include <linux/blktrace_api.h>
  17. #include "blk.h"
  18. #include "cfq.h"
  19. /*
  20. * tunables
  21. */
  22. /* max queue in one round of service */
  23. static const int cfq_quantum = 8;
  24. static const int cfq_fifo_expire[2] = { HZ / 4, HZ / 8 };
  25. /* maximum backwards seek, in KiB */
  26. static const int cfq_back_max = 16 * 1024;
  27. /* penalty of a backwards seek */
  28. static const int cfq_back_penalty = 2;
  29. static const int cfq_slice_sync = HZ / 10;
  30. static int cfq_slice_async = HZ / 25;
  31. static const int cfq_slice_async_rq = 2;
  32. static int cfq_slice_idle = HZ / 125;
  33. static int cfq_group_idle = HZ / 125;
  34. static const int cfq_target_latency = HZ * 3/10; /* 300 ms */
  35. static const int cfq_hist_divisor = 4;
  36. /*
  37. * offset from end of service tree
  38. */
  39. #define CFQ_IDLE_DELAY (HZ / 5)
  40. /*
  41. * below this threshold, we consider thinktime immediate
  42. */
  43. #define CFQ_MIN_TT (2)
  44. #define CFQ_SLICE_SCALE (5)
  45. #define CFQ_HW_QUEUE_MIN (5)
  46. #define CFQ_SERVICE_SHIFT 12
  47. #define CFQQ_SEEK_THR (sector_t)(8 * 100)
  48. #define CFQQ_CLOSE_THR (sector_t)(8 * 1024)
  49. #define CFQQ_SECT_THR_NONROT (sector_t)(2 * 32)
  50. #define CFQQ_SEEKY(cfqq) (hweight32(cfqq->seek_history) > 32/8)
  51. #define RQ_CIC(rq) icq_to_cic((rq)->elv.icq)
  52. #define RQ_CFQQ(rq) (struct cfq_queue *) ((rq)->elv.priv[0])
  53. #define RQ_CFQG(rq) (struct cfq_group *) ((rq)->elv.priv[1])
  54. static struct kmem_cache *cfq_pool;
  55. #define CFQ_PRIO_LISTS IOPRIO_BE_NR
  56. #define cfq_class_idle(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_IDLE)
  57. #define cfq_class_rt(cfqq) ((cfqq)->ioprio_class == IOPRIO_CLASS_RT)
  58. #define sample_valid(samples) ((samples) > 80)
  59. #define rb_entry_cfqg(node) rb_entry((node), struct cfq_group, rb_node)
  60. struct cfq_ttime {
  61. unsigned long last_end_request;
  62. unsigned long ttime_total;
  63. unsigned long ttime_samples;
  64. unsigned long ttime_mean;
  65. };
  66. /*
  67. * Most of our rbtree usage is for sorting with min extraction, so
  68. * if we cache the leftmost node we don't have to walk down the tree
  69. * to find it. Idea borrowed from Ingo Molnars CFS scheduler. We should
  70. * move this into the elevator for the rq sorting as well.
  71. */
  72. struct cfq_rb_root {
  73. struct rb_root rb;
  74. struct rb_node *left;
  75. unsigned count;
  76. unsigned total_weight;
  77. u64 min_vdisktime;
  78. struct cfq_ttime ttime;
  79. };
  80. #define CFQ_RB_ROOT (struct cfq_rb_root) { .rb = RB_ROOT, \
  81. .ttime = {.last_end_request = jiffies,},}
  82. /*
  83. * Per process-grouping structure
  84. */
  85. struct cfq_queue {
  86. /* reference count */
  87. int ref;
  88. /* various state flags, see below */
  89. unsigned int flags;
  90. /* parent cfq_data */
  91. struct cfq_data *cfqd;
  92. /* service_tree member */
  93. struct rb_node rb_node;
  94. /* service_tree key */
  95. unsigned long rb_key;
  96. /* prio tree member */
  97. struct rb_node p_node;
  98. /* prio tree root we belong to, if any */
  99. struct rb_root *p_root;
  100. /* sorted list of pending requests */
  101. struct rb_root sort_list;
  102. /* if fifo isn't expired, next request to serve */
  103. struct request *next_rq;
  104. /* requests queued in sort_list */
  105. int queued[2];
  106. /* currently allocated requests */
  107. int allocated[2];
  108. /* fifo list of requests in sort_list */
  109. struct list_head fifo;
  110. /* time when queue got scheduled in to dispatch first request. */
  111. unsigned long dispatch_start;
  112. unsigned int allocated_slice;
  113. unsigned int slice_dispatch;
  114. /* time when first request from queue completed and slice started. */
  115. unsigned long slice_start;
  116. unsigned long slice_end;
  117. long slice_resid;
  118. /* pending priority requests */
  119. int prio_pending;
  120. /* number of requests that are on the dispatch list or inside driver */
  121. int dispatched;
  122. /* io prio of this group */
  123. unsigned short ioprio, org_ioprio;
  124. unsigned short ioprio_class;
  125. pid_t pid;
  126. u32 seek_history;
  127. sector_t last_request_pos;
  128. struct cfq_rb_root *service_tree;
  129. struct cfq_queue *new_cfqq;
  130. struct cfq_group *cfqg;
  131. /* Number of sectors dispatched from queue in single dispatch round */
  132. unsigned long nr_sectors;
  133. };
  134. /*
  135. * First index in the service_trees.
  136. * IDLE is handled separately, so it has negative index
  137. */
  138. enum wl_prio_t {
  139. BE_WORKLOAD = 0,
  140. RT_WORKLOAD = 1,
  141. IDLE_WORKLOAD = 2,
  142. CFQ_PRIO_NR,
  143. };
  144. /*
  145. * Second index in the service_trees.
  146. */
  147. enum wl_type_t {
  148. ASYNC_WORKLOAD = 0,
  149. SYNC_NOIDLE_WORKLOAD = 1,
  150. SYNC_WORKLOAD = 2
  151. };
  152. /* This is per cgroup per device grouping structure */
  153. struct cfq_group {
  154. /* group service_tree member */
  155. struct rb_node rb_node;
  156. /* group service_tree key */
  157. u64 vdisktime;
  158. unsigned int weight;
  159. unsigned int new_weight;
  160. bool needs_update;
  161. /* number of cfqq currently on this group */
  162. int nr_cfqq;
  163. /*
  164. * Per group busy queues average. Useful for workload slice calc. We
  165. * create the array for each prio class but at run time it is used
  166. * only for RT and BE class and slot for IDLE class remains unused.
  167. * This is primarily done to avoid confusion and a gcc warning.
  168. */
  169. unsigned int busy_queues_avg[CFQ_PRIO_NR];
  170. /*
  171. * rr lists of queues with requests. We maintain service trees for
  172. * RT and BE classes. These trees are subdivided in subclasses
  173. * of SYNC, SYNC_NOIDLE and ASYNC based on workload type. For IDLE
  174. * class there is no subclassification and all the cfq queues go on
  175. * a single tree service_tree_idle.
  176. * Counts are embedded in the cfq_rb_root
  177. */
  178. struct cfq_rb_root service_trees[2][3];
  179. struct cfq_rb_root service_tree_idle;
  180. unsigned long saved_workload_slice;
  181. enum wl_type_t saved_workload;
  182. enum wl_prio_t saved_serving_prio;
  183. struct blkio_group blkg;
  184. #ifdef CONFIG_CFQ_GROUP_IOSCHED
  185. struct hlist_node cfqd_node;
  186. int ref;
  187. #endif
  188. /* number of requests that are on the dispatch list or inside driver */
  189. int dispatched;
  190. struct cfq_ttime ttime;
  191. };
  192. struct cfq_io_cq {
  193. struct io_cq icq; /* must be the first member */
  194. struct cfq_queue *cfqq[2];
  195. struct cfq_ttime ttime;
  196. };
  197. /*
  198. * Per block device queue structure
  199. */
  200. struct cfq_data {
  201. struct request_queue *queue;
  202. /* Root service tree for cfq_groups */
  203. struct cfq_rb_root grp_service_tree;
  204. struct cfq_group root_group;
  205. /*
  206. * The priority currently being served
  207. */
  208. enum wl_prio_t serving_prio;
  209. enum wl_type_t serving_type;
  210. unsigned long workload_expires;
  211. struct cfq_group *serving_group;
  212. /*
  213. * Each priority tree is sorted by next_request position. These
  214. * trees are used when determining if two or more queues are
  215. * interleaving requests (see cfq_close_cooperator).
  216. */
  217. struct rb_root prio_trees[CFQ_PRIO_LISTS];
  218. unsigned int busy_queues;
  219. unsigned int busy_sync_queues;
  220. int rq_in_driver;
  221. int rq_in_flight[2];
  222. /*
  223. * queue-depth detection
  224. */
  225. int rq_queued;
  226. int hw_tag;
  227. /*
  228. * hw_tag can be
  229. * -1 => indeterminate, (cfq will behave as if NCQ is present, to allow better detection)
  230. * 1 => NCQ is present (hw_tag_est_depth is the estimated max depth)
  231. * 0 => no NCQ
  232. */
  233. int hw_tag_est_depth;
  234. unsigned int hw_tag_samples;
  235. /*
  236. * idle window management
  237. */
  238. struct timer_list idle_slice_timer;
  239. struct work_struct unplug_work;
  240. struct cfq_queue *active_queue;
  241. struct cfq_io_cq *active_cic;
  242. /*
  243. * async queue for each priority case
  244. */
  245. struct cfq_queue *async_cfqq[2][IOPRIO_BE_NR];
  246. struct cfq_queue *async_idle_cfqq;
  247. sector_t last_position;
  248. /*
  249. * tunables, see top of file
  250. */
  251. unsigned int cfq_quantum;
  252. unsigned int cfq_fifo_expire[2];
  253. unsigned int cfq_back_penalty;
  254. unsigned int cfq_back_max;
  255. unsigned int cfq_slice[2];
  256. unsigned int cfq_slice_async_rq;
  257. unsigned int cfq_slice_idle;
  258. unsigned int cfq_group_idle;
  259. unsigned int cfq_latency;
  260. /*
  261. * Fallback dummy cfqq for extreme OOM conditions
  262. */
  263. struct cfq_queue oom_cfqq;
  264. unsigned long last_delayed_sync;
  265. /* List of cfq groups being managed on this device*/
  266. struct hlist_head cfqg_list;
  267. /* Number of groups which are on blkcg->blkg_list */
  268. unsigned int nr_blkcg_linked_grps;
  269. };
  270. static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd);
  271. static struct cfq_rb_root *service_tree_for(struct cfq_group *cfqg,
  272. enum wl_prio_t prio,
  273. enum wl_type_t type)
  274. {
  275. if (!cfqg)
  276. return NULL;
  277. if (prio == IDLE_WORKLOAD)
  278. return &cfqg->service_tree_idle;
  279. return &cfqg->service_trees[prio][type];
  280. }
  281. enum cfqq_state_flags {
  282. CFQ_CFQQ_FLAG_on_rr = 0, /* on round-robin busy list */
  283. CFQ_CFQQ_FLAG_wait_request, /* waiting for a request */
  284. CFQ_CFQQ_FLAG_must_dispatch, /* must be allowed a dispatch */
  285. CFQ_CFQQ_FLAG_must_alloc_slice, /* per-slice must_alloc flag */
  286. CFQ_CFQQ_FLAG_fifo_expire, /* FIFO checked in this slice */
  287. CFQ_CFQQ_FLAG_idle_window, /* slice idling enabled */
  288. CFQ_CFQQ_FLAG_prio_changed, /* task priority has changed */
  289. CFQ_CFQQ_FLAG_slice_new, /* no requests dispatched in slice */
  290. CFQ_CFQQ_FLAG_sync, /* synchronous queue */
  291. CFQ_CFQQ_FLAG_coop, /* cfqq is shared */
  292. CFQ_CFQQ_FLAG_split_coop, /* shared cfqq will be splitted */
  293. CFQ_CFQQ_FLAG_deep, /* sync cfqq experienced large depth */
  294. CFQ_CFQQ_FLAG_wait_busy, /* Waiting for next request */
  295. };
  296. #define CFQ_CFQQ_FNS(name) \
  297. static inline void cfq_mark_cfqq_##name(struct cfq_queue *cfqq) \
  298. { \
  299. (cfqq)->flags |= (1 << CFQ_CFQQ_FLAG_##name); \
  300. } \
  301. static inline void cfq_clear_cfqq_##name(struct cfq_queue *cfqq) \
  302. { \
  303. (cfqq)->flags &= ~(1 << CFQ_CFQQ_FLAG_##name); \
  304. } \
  305. static inline int cfq_cfqq_##name(const struct cfq_queue *cfqq) \
  306. { \
  307. return ((cfqq)->flags & (1 << CFQ_CFQQ_FLAG_##name)) != 0; \
  308. }
  309. CFQ_CFQQ_FNS(on_rr);
  310. CFQ_CFQQ_FNS(wait_request);
  311. CFQ_CFQQ_FNS(must_dispatch);
  312. CFQ_CFQQ_FNS(must_alloc_slice);
  313. CFQ_CFQQ_FNS(fifo_expire);
  314. CFQ_CFQQ_FNS(idle_window);
  315. CFQ_CFQQ_FNS(prio_changed);
  316. CFQ_CFQQ_FNS(slice_new);
  317. CFQ_CFQQ_FNS(sync);
  318. CFQ_CFQQ_FNS(coop);
  319. CFQ_CFQQ_FNS(split_coop);
  320. CFQ_CFQQ_FNS(deep);
  321. CFQ_CFQQ_FNS(wait_busy);
  322. #undef CFQ_CFQQ_FNS
  323. #ifdef CONFIG_CFQ_GROUP_IOSCHED
  324. #define cfq_log_cfqq(cfqd, cfqq, fmt, args...) \
  325. blk_add_trace_msg((cfqd)->queue, "cfq%d%c %s " fmt, (cfqq)->pid, \
  326. cfq_cfqq_sync((cfqq)) ? 'S' : 'A', \
  327. blkg_path(&(cfqq)->cfqg->blkg), ##args)
  328. #define cfq_log_cfqg(cfqd, cfqg, fmt, args...) \
  329. blk_add_trace_msg((cfqd)->queue, "%s " fmt, \
  330. blkg_path(&(cfqg)->blkg), ##args) \
  331. #else
  332. #define cfq_log_cfqq(cfqd, cfqq, fmt, args...) \
  333. blk_add_trace_msg((cfqd)->queue, "cfq%d " fmt, (cfqq)->pid, ##args)
  334. #define cfq_log_cfqg(cfqd, cfqg, fmt, args...) do {} while (0)
  335. #endif
  336. #define cfq_log(cfqd, fmt, args...) \
  337. blk_add_trace_msg((cfqd)->queue, "cfq " fmt, ##args)
  338. /* Traverses through cfq group service trees */
  339. #define for_each_cfqg_st(cfqg, i, j, st) \
  340. for (i = 0; i <= IDLE_WORKLOAD; i++) \
  341. for (j = 0, st = i < IDLE_WORKLOAD ? &cfqg->service_trees[i][j]\
  342. : &cfqg->service_tree_idle; \
  343. (i < IDLE_WORKLOAD && j <= SYNC_WORKLOAD) || \
  344. (i == IDLE_WORKLOAD && j == 0); \
  345. j++, st = i < IDLE_WORKLOAD ? \
  346. &cfqg->service_trees[i][j]: NULL) \
  347. static inline bool cfq_io_thinktime_big(struct cfq_data *cfqd,
  348. struct cfq_ttime *ttime, bool group_idle)
  349. {
  350. unsigned long slice;
  351. if (!sample_valid(ttime->ttime_samples))
  352. return false;
  353. if (group_idle)
  354. slice = cfqd->cfq_group_idle;
  355. else
  356. slice = cfqd->cfq_slice_idle;
  357. return ttime->ttime_mean > slice;
  358. }
  359. static inline bool iops_mode(struct cfq_data *cfqd)
  360. {
  361. /*
  362. * If we are not idling on queues and it is a NCQ drive, parallel
  363. * execution of requests is on and measuring time is not possible
  364. * in most of the cases until and unless we drive shallower queue
  365. * depths and that becomes a performance bottleneck. In such cases
  366. * switch to start providing fairness in terms of number of IOs.
  367. */
  368. if (!cfqd->cfq_slice_idle && cfqd->hw_tag)
  369. return true;
  370. else
  371. return false;
  372. }
  373. static inline enum wl_prio_t cfqq_prio(struct cfq_queue *cfqq)
  374. {
  375. if (cfq_class_idle(cfqq))
  376. return IDLE_WORKLOAD;
  377. if (cfq_class_rt(cfqq))
  378. return RT_WORKLOAD;
  379. return BE_WORKLOAD;
  380. }
  381. static enum wl_type_t cfqq_type(struct cfq_queue *cfqq)
  382. {
  383. if (!cfq_cfqq_sync(cfqq))
  384. return ASYNC_WORKLOAD;
  385. if (!cfq_cfqq_idle_window(cfqq))
  386. return SYNC_NOIDLE_WORKLOAD;
  387. return SYNC_WORKLOAD;
  388. }
  389. static inline int cfq_group_busy_queues_wl(enum wl_prio_t wl,
  390. struct cfq_data *cfqd,
  391. struct cfq_group *cfqg)
  392. {
  393. if (wl == IDLE_WORKLOAD)
  394. return cfqg->service_tree_idle.count;
  395. return cfqg->service_trees[wl][ASYNC_WORKLOAD].count
  396. + cfqg->service_trees[wl][SYNC_NOIDLE_WORKLOAD].count
  397. + cfqg->service_trees[wl][SYNC_WORKLOAD].count;
  398. }
  399. static inline int cfqg_busy_async_queues(struct cfq_data *cfqd,
  400. struct cfq_group *cfqg)
  401. {
  402. return cfqg->service_trees[RT_WORKLOAD][ASYNC_WORKLOAD].count
  403. + cfqg->service_trees[BE_WORKLOAD][ASYNC_WORKLOAD].count;
  404. }
  405. static void cfq_dispatch_insert(struct request_queue *, struct request *);
  406. static struct cfq_queue *cfq_get_queue(struct cfq_data *, bool,
  407. struct io_context *, gfp_t);
  408. static inline struct cfq_io_cq *icq_to_cic(struct io_cq *icq)
  409. {
  410. /* cic->icq is the first member, %NULL will convert to %NULL */
  411. return container_of(icq, struct cfq_io_cq, icq);
  412. }
  413. static inline struct cfq_io_cq *cfq_cic_lookup(struct cfq_data *cfqd,
  414. struct io_context *ioc)
  415. {
  416. if (ioc)
  417. return icq_to_cic(ioc_lookup_icq(ioc, cfqd->queue));
  418. return NULL;
  419. }
  420. static inline struct cfq_queue *cic_to_cfqq(struct cfq_io_cq *cic, bool is_sync)
  421. {
  422. return cic->cfqq[is_sync];
  423. }
  424. static inline void cic_set_cfqq(struct cfq_io_cq *cic, struct cfq_queue *cfqq,
  425. bool is_sync)
  426. {
  427. cic->cfqq[is_sync] = cfqq;
  428. }
  429. static inline struct cfq_data *cic_to_cfqd(struct cfq_io_cq *cic)
  430. {
  431. return cic->icq.q->elevator->elevator_data;
  432. }
  433. /*
  434. * We regard a request as SYNC, if it's either a read or has the SYNC bit
  435. * set (in which case it could also be direct WRITE).
  436. */
  437. static inline bool cfq_bio_sync(struct bio *bio)
  438. {
  439. return bio_data_dir(bio) == READ || (bio->bi_rw & REQ_SYNC);
  440. }
  441. /*
  442. * scheduler run of queue, if there are requests pending and no one in the
  443. * driver that will restart queueing
  444. */
  445. static inline void cfq_schedule_dispatch(struct cfq_data *cfqd)
  446. {
  447. if (cfqd->busy_queues) {
  448. cfq_log(cfqd, "schedule dispatch");
  449. kblockd_schedule_work(cfqd->queue, &cfqd->unplug_work);
  450. }
  451. }
  452. /*
  453. * Scale schedule slice based on io priority. Use the sync time slice only
  454. * if a queue is marked sync and has sync io queued. A sync queue with async
  455. * io only, should not get full sync slice length.
  456. */
  457. static inline int cfq_prio_slice(struct cfq_data *cfqd, bool sync,
  458. unsigned short prio)
  459. {
  460. const int base_slice = cfqd->cfq_slice[sync];
  461. WARN_ON(prio >= IOPRIO_BE_NR);
  462. return base_slice + (base_slice/CFQ_SLICE_SCALE * (4 - prio));
  463. }
  464. static inline int
  465. cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  466. {
  467. return cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio);
  468. }
  469. static inline u64 cfq_scale_slice(unsigned long delta, struct cfq_group *cfqg)
  470. {
  471. u64 d = delta << CFQ_SERVICE_SHIFT;
  472. d = d * BLKIO_WEIGHT_DEFAULT;
  473. do_div(d, cfqg->weight);
  474. return d;
  475. }
  476. static inline u64 max_vdisktime(u64 min_vdisktime, u64 vdisktime)
  477. {
  478. s64 delta = (s64)(vdisktime - min_vdisktime);
  479. if (delta > 0)
  480. min_vdisktime = vdisktime;
  481. return min_vdisktime;
  482. }
  483. static inline u64 min_vdisktime(u64 min_vdisktime, u64 vdisktime)
  484. {
  485. s64 delta = (s64)(vdisktime - min_vdisktime);
  486. if (delta < 0)
  487. min_vdisktime = vdisktime;
  488. return min_vdisktime;
  489. }
  490. static void update_min_vdisktime(struct cfq_rb_root *st)
  491. {
  492. struct cfq_group *cfqg;
  493. if (st->left) {
  494. cfqg = rb_entry_cfqg(st->left);
  495. st->min_vdisktime = max_vdisktime(st->min_vdisktime,
  496. cfqg->vdisktime);
  497. }
  498. }
  499. /*
  500. * get averaged number of queues of RT/BE priority.
  501. * average is updated, with a formula that gives more weight to higher numbers,
  502. * to quickly follows sudden increases and decrease slowly
  503. */
  504. static inline unsigned cfq_group_get_avg_queues(struct cfq_data *cfqd,
  505. struct cfq_group *cfqg, bool rt)
  506. {
  507. unsigned min_q, max_q;
  508. unsigned mult = cfq_hist_divisor - 1;
  509. unsigned round = cfq_hist_divisor / 2;
  510. unsigned busy = cfq_group_busy_queues_wl(rt, cfqd, cfqg);
  511. min_q = min(cfqg->busy_queues_avg[rt], busy);
  512. max_q = max(cfqg->busy_queues_avg[rt], busy);
  513. cfqg->busy_queues_avg[rt] = (mult * max_q + min_q + round) /
  514. cfq_hist_divisor;
  515. return cfqg->busy_queues_avg[rt];
  516. }
  517. static inline unsigned
  518. cfq_group_slice(struct cfq_data *cfqd, struct cfq_group *cfqg)
  519. {
  520. struct cfq_rb_root *st = &cfqd->grp_service_tree;
  521. return cfq_target_latency * cfqg->weight / st->total_weight;
  522. }
  523. static inline unsigned
  524. cfq_scaled_cfqq_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  525. {
  526. unsigned slice = cfq_prio_to_slice(cfqd, cfqq);
  527. if (cfqd->cfq_latency) {
  528. /*
  529. * interested queues (we consider only the ones with the same
  530. * priority class in the cfq group)
  531. */
  532. unsigned iq = cfq_group_get_avg_queues(cfqd, cfqq->cfqg,
  533. cfq_class_rt(cfqq));
  534. unsigned sync_slice = cfqd->cfq_slice[1];
  535. unsigned expect_latency = sync_slice * iq;
  536. unsigned group_slice = cfq_group_slice(cfqd, cfqq->cfqg);
  537. if (expect_latency > group_slice) {
  538. unsigned base_low_slice = 2 * cfqd->cfq_slice_idle;
  539. /* scale low_slice according to IO priority
  540. * and sync vs async */
  541. unsigned low_slice =
  542. min(slice, base_low_slice * slice / sync_slice);
  543. /* the adapted slice value is scaled to fit all iqs
  544. * into the target latency */
  545. slice = max(slice * group_slice / expect_latency,
  546. low_slice);
  547. }
  548. }
  549. return slice;
  550. }
  551. static inline void
  552. cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  553. {
  554. unsigned slice = cfq_scaled_cfqq_slice(cfqd, cfqq);
  555. cfqq->slice_start = jiffies;
  556. cfqq->slice_end = jiffies + slice;
  557. cfqq->allocated_slice = slice;
  558. cfq_log_cfqq(cfqd, cfqq, "set_slice=%lu", cfqq->slice_end - jiffies);
  559. }
  560. /*
  561. * We need to wrap this check in cfq_cfqq_slice_new(), since ->slice_end
  562. * isn't valid until the first request from the dispatch is activated
  563. * and the slice time set.
  564. */
  565. static inline bool cfq_slice_used(struct cfq_queue *cfqq)
  566. {
  567. if (cfq_cfqq_slice_new(cfqq))
  568. return false;
  569. if (time_before(jiffies, cfqq->slice_end))
  570. return false;
  571. return true;
  572. }
  573. /*
  574. * Lifted from AS - choose which of rq1 and rq2 that is best served now.
  575. * We choose the request that is closest to the head right now. Distance
  576. * behind the head is penalized and only allowed to a certain extent.
  577. */
  578. static struct request *
  579. cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2, sector_t last)
  580. {
  581. sector_t s1, s2, d1 = 0, d2 = 0;
  582. unsigned long back_max;
  583. #define CFQ_RQ1_WRAP 0x01 /* request 1 wraps */
  584. #define CFQ_RQ2_WRAP 0x02 /* request 2 wraps */
  585. unsigned wrap = 0; /* bit mask: requests behind the disk head? */
  586. if (rq1 == NULL || rq1 == rq2)
  587. return rq2;
  588. if (rq2 == NULL)
  589. return rq1;
  590. if (rq_is_sync(rq1) != rq_is_sync(rq2))
  591. return rq_is_sync(rq1) ? rq1 : rq2;
  592. if ((rq1->cmd_flags ^ rq2->cmd_flags) & REQ_PRIO)
  593. return rq1->cmd_flags & REQ_PRIO ? rq1 : rq2;
  594. s1 = blk_rq_pos(rq1);
  595. s2 = blk_rq_pos(rq2);
  596. /*
  597. * by definition, 1KiB is 2 sectors
  598. */
  599. back_max = cfqd->cfq_back_max * 2;
  600. /*
  601. * Strict one way elevator _except_ in the case where we allow
  602. * short backward seeks which are biased as twice the cost of a
  603. * similar forward seek.
  604. */
  605. if (s1 >= last)
  606. d1 = s1 - last;
  607. else if (s1 + back_max >= last)
  608. d1 = (last - s1) * cfqd->cfq_back_penalty;
  609. else
  610. wrap |= CFQ_RQ1_WRAP;
  611. if (s2 >= last)
  612. d2 = s2 - last;
  613. else if (s2 + back_max >= last)
  614. d2 = (last - s2) * cfqd->cfq_back_penalty;
  615. else
  616. wrap |= CFQ_RQ2_WRAP;
  617. /* Found required data */
  618. /*
  619. * By doing switch() on the bit mask "wrap" we avoid having to
  620. * check two variables for all permutations: --> faster!
  621. */
  622. switch (wrap) {
  623. case 0: /* common case for CFQ: rq1 and rq2 not wrapped */
  624. if (d1 < d2)
  625. return rq1;
  626. else if (d2 < d1)
  627. return rq2;
  628. else {
  629. if (s1 >= s2)
  630. return rq1;
  631. else
  632. return rq2;
  633. }
  634. case CFQ_RQ2_WRAP:
  635. return rq1;
  636. case CFQ_RQ1_WRAP:
  637. return rq2;
  638. case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both rqs wrapped */
  639. default:
  640. /*
  641. * Since both rqs are wrapped,
  642. * start with the one that's further behind head
  643. * (--> only *one* back seek required),
  644. * since back seek takes more time than forward.
  645. */
  646. if (s1 <= s2)
  647. return rq1;
  648. else
  649. return rq2;
  650. }
  651. }
  652. /*
  653. * The below is leftmost cache rbtree addon
  654. */
  655. static struct cfq_queue *cfq_rb_first(struct cfq_rb_root *root)
  656. {
  657. /* Service tree is empty */
  658. if (!root->count)
  659. return NULL;
  660. if (!root->left)
  661. root->left = rb_first(&root->rb);
  662. if (root->left)
  663. return rb_entry(root->left, struct cfq_queue, rb_node);
  664. return NULL;
  665. }
  666. static struct cfq_group *cfq_rb_first_group(struct cfq_rb_root *root)
  667. {
  668. if (!root->left)
  669. root->left = rb_first(&root->rb);
  670. if (root->left)
  671. return rb_entry_cfqg(root->left);
  672. return NULL;
  673. }
  674. static void rb_erase_init(struct rb_node *n, struct rb_root *root)
  675. {
  676. rb_erase(n, root);
  677. RB_CLEAR_NODE(n);
  678. }
  679. static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
  680. {
  681. if (root->left == n)
  682. root->left = NULL;
  683. rb_erase_init(n, &root->rb);
  684. --root->count;
  685. }
  686. /*
  687. * would be nice to take fifo expire time into account as well
  688. */
  689. static struct request *
  690. cfq_find_next_rq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
  691. struct request *last)
  692. {
  693. struct rb_node *rbnext = rb_next(&last->rb_node);
  694. struct rb_node *rbprev = rb_prev(&last->rb_node);
  695. struct request *next = NULL, *prev = NULL;
  696. BUG_ON(RB_EMPTY_NODE(&last->rb_node));
  697. if (rbprev)
  698. prev = rb_entry_rq(rbprev);
  699. if (rbnext)
  700. next = rb_entry_rq(rbnext);
  701. else {
  702. rbnext = rb_first(&cfqq->sort_list);
  703. if (rbnext && rbnext != &last->rb_node)
  704. next = rb_entry_rq(rbnext);
  705. }
  706. return cfq_choose_req(cfqd, next, prev, blk_rq_pos(last));
  707. }
  708. static unsigned long cfq_slice_offset(struct cfq_data *cfqd,
  709. struct cfq_queue *cfqq)
  710. {
  711. /*
  712. * just an approximation, should be ok.
  713. */
  714. return (cfqq->cfqg->nr_cfqq - 1) * (cfq_prio_slice(cfqd, 1, 0) -
  715. cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio));
  716. }
  717. static inline s64
  718. cfqg_key(struct cfq_rb_root *st, struct cfq_group *cfqg)
  719. {
  720. return cfqg->vdisktime - st->min_vdisktime;
  721. }
  722. static void
  723. __cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
  724. {
  725. struct rb_node **node = &st->rb.rb_node;
  726. struct rb_node *parent = NULL;
  727. struct cfq_group *__cfqg;
  728. s64 key = cfqg_key(st, cfqg);
  729. int left = 1;
  730. while (*node != NULL) {
  731. parent = *node;
  732. __cfqg = rb_entry_cfqg(parent);
  733. if (key < cfqg_key(st, __cfqg))
  734. node = &parent->rb_left;
  735. else {
  736. node = &parent->rb_right;
  737. left = 0;
  738. }
  739. }
  740. if (left)
  741. st->left = &cfqg->rb_node;
  742. rb_link_node(&cfqg->rb_node, parent, node);
  743. rb_insert_color(&cfqg->rb_node, &st->rb);
  744. }
  745. static void
  746. cfq_update_group_weight(struct cfq_group *cfqg)
  747. {
  748. BUG_ON(!RB_EMPTY_NODE(&cfqg->rb_node));
  749. if (cfqg->needs_update) {
  750. cfqg->weight = cfqg->new_weight;
  751. cfqg->needs_update = false;
  752. }
  753. }
  754. static void
  755. cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
  756. {
  757. BUG_ON(!RB_EMPTY_NODE(&cfqg->rb_node));
  758. cfq_update_group_weight(cfqg);
  759. __cfq_group_service_tree_add(st, cfqg);
  760. st->total_weight += cfqg->weight;
  761. }
  762. static void
  763. cfq_group_notify_queue_add(struct cfq_data *cfqd, struct cfq_group *cfqg)
  764. {
  765. struct cfq_rb_root *st = &cfqd->grp_service_tree;
  766. struct cfq_group *__cfqg;
  767. struct rb_node *n;
  768. cfqg->nr_cfqq++;
  769. if (!RB_EMPTY_NODE(&cfqg->rb_node))
  770. return;
  771. /*
  772. * Currently put the group at the end. Later implement something
  773. * so that groups get lesser vtime based on their weights, so that
  774. * if group does not loose all if it was not continuously backlogged.
  775. */
  776. n = rb_last(&st->rb);
  777. if (n) {
  778. __cfqg = rb_entry_cfqg(n);
  779. cfqg->vdisktime = __cfqg->vdisktime + CFQ_IDLE_DELAY;
  780. } else
  781. cfqg->vdisktime = st->min_vdisktime;
  782. cfq_group_service_tree_add(st, cfqg);
  783. }
  784. static void
  785. cfq_group_service_tree_del(struct cfq_rb_root *st, struct cfq_group *cfqg)
  786. {
  787. st->total_weight -= cfqg->weight;
  788. if (!RB_EMPTY_NODE(&cfqg->rb_node))
  789. cfq_rb_erase(&cfqg->rb_node, st);
  790. }
  791. static void
  792. cfq_group_notify_queue_del(struct cfq_data *cfqd, struct cfq_group *cfqg)
  793. {
  794. struct cfq_rb_root *st = &cfqd->grp_service_tree;
  795. BUG_ON(cfqg->nr_cfqq < 1);
  796. cfqg->nr_cfqq--;
  797. /* If there are other cfq queues under this group, don't delete it */
  798. if (cfqg->nr_cfqq)
  799. return;
  800. cfq_log_cfqg(cfqd, cfqg, "del_from_rr group");
  801. cfq_group_service_tree_del(st, cfqg);
  802. cfqg->saved_workload_slice = 0;
  803. cfq_blkiocg_update_dequeue_stats(&cfqg->blkg, 1);
  804. }
  805. static inline unsigned int cfq_cfqq_slice_usage(struct cfq_queue *cfqq,
  806. unsigned int *unaccounted_time)
  807. {
  808. unsigned int slice_used;
  809. /*
  810. * Queue got expired before even a single request completed or
  811. * got expired immediately after first request completion.
  812. */
  813. if (!cfqq->slice_start || cfqq->slice_start == jiffies) {
  814. /*
  815. * Also charge the seek time incurred to the group, otherwise
  816. * if there are mutiple queues in the group, each can dispatch
  817. * a single request on seeky media and cause lots of seek time
  818. * and group will never know it.
  819. */
  820. slice_used = max_t(unsigned, (jiffies - cfqq->dispatch_start),
  821. 1);
  822. } else {
  823. slice_used = jiffies - cfqq->slice_start;
  824. if (slice_used > cfqq->allocated_slice) {
  825. *unaccounted_time = slice_used - cfqq->allocated_slice;
  826. slice_used = cfqq->allocated_slice;
  827. }
  828. if (time_after(cfqq->slice_start, cfqq->dispatch_start))
  829. *unaccounted_time += cfqq->slice_start -
  830. cfqq->dispatch_start;
  831. }
  832. return slice_used;
  833. }
  834. static void cfq_group_served(struct cfq_data *cfqd, struct cfq_group *cfqg,
  835. struct cfq_queue *cfqq)
  836. {
  837. struct cfq_rb_root *st = &cfqd->grp_service_tree;
  838. unsigned int used_sl, charge, unaccounted_sl = 0;
  839. int nr_sync = cfqg->nr_cfqq - cfqg_busy_async_queues(cfqd, cfqg)
  840. - cfqg->service_tree_idle.count;
  841. BUG_ON(nr_sync < 0);
  842. used_sl = charge = cfq_cfqq_slice_usage(cfqq, &unaccounted_sl);
  843. if (iops_mode(cfqd))
  844. charge = cfqq->slice_dispatch;
  845. else if (!cfq_cfqq_sync(cfqq) && !nr_sync)
  846. charge = cfqq->allocated_slice;
  847. /* Can't update vdisktime while group is on service tree */
  848. cfq_group_service_tree_del(st, cfqg);
  849. cfqg->vdisktime += cfq_scale_slice(charge, cfqg);
  850. /* If a new weight was requested, update now, off tree */
  851. cfq_group_service_tree_add(st, cfqg);
  852. /* This group is being expired. Save the context */
  853. if (time_after(cfqd->workload_expires, jiffies)) {
  854. cfqg->saved_workload_slice = cfqd->workload_expires
  855. - jiffies;
  856. cfqg->saved_workload = cfqd->serving_type;
  857. cfqg->saved_serving_prio = cfqd->serving_prio;
  858. } else
  859. cfqg->saved_workload_slice = 0;
  860. cfq_log_cfqg(cfqd, cfqg, "served: vt=%llu min_vt=%llu", cfqg->vdisktime,
  861. st->min_vdisktime);
  862. cfq_log_cfqq(cfqq->cfqd, cfqq,
  863. "sl_used=%u disp=%u charge=%u iops=%u sect=%lu",
  864. used_sl, cfqq->slice_dispatch, charge,
  865. iops_mode(cfqd), cfqq->nr_sectors);
  866. cfq_blkiocg_update_timeslice_used(&cfqg->blkg, used_sl,
  867. unaccounted_sl);
  868. cfq_blkiocg_set_start_empty_time(&cfqg->blkg);
  869. }
  870. #ifdef CONFIG_CFQ_GROUP_IOSCHED
  871. static inline struct cfq_group *cfqg_of_blkg(struct blkio_group *blkg)
  872. {
  873. if (blkg)
  874. return container_of(blkg, struct cfq_group, blkg);
  875. return NULL;
  876. }
  877. static void cfq_update_blkio_group_weight(void *key, struct blkio_group *blkg,
  878. unsigned int weight)
  879. {
  880. struct cfq_group *cfqg = cfqg_of_blkg(blkg);
  881. cfqg->new_weight = weight;
  882. cfqg->needs_update = true;
  883. }
  884. static void cfq_init_add_cfqg_lists(struct cfq_data *cfqd,
  885. struct cfq_group *cfqg, struct blkio_cgroup *blkcg)
  886. {
  887. struct backing_dev_info *bdi = &cfqd->queue->backing_dev_info;
  888. unsigned int major, minor;
  889. /*
  890. * Add group onto cgroup list. It might happen that bdi->dev is
  891. * not initialized yet. Initialize this new group without major
  892. * and minor info and this info will be filled in once a new thread
  893. * comes for IO.
  894. */
  895. if (bdi->dev) {
  896. sscanf(dev_name(bdi->dev), "%u:%u", &major, &minor);
  897. cfq_blkiocg_add_blkio_group(blkcg, &cfqg->blkg,
  898. (void *)cfqd, MKDEV(major, minor));
  899. } else
  900. cfq_blkiocg_add_blkio_group(blkcg, &cfqg->blkg,
  901. (void *)cfqd, 0);
  902. cfqd->nr_blkcg_linked_grps++;
  903. cfqg->weight = blkcg_get_weight(blkcg, cfqg->blkg.dev);
  904. /* Add group on cfqd list */
  905. hlist_add_head(&cfqg->cfqd_node, &cfqd->cfqg_list);
  906. }
  907. /*
  908. * Should be called from sleepable context. No request queue lock as per
  909. * cpu stats are allocated dynamically and alloc_percpu needs to be called
  910. * from sleepable context.
  911. */
  912. static struct cfq_group * cfq_alloc_cfqg(struct cfq_data *cfqd)
  913. {
  914. struct cfq_group *cfqg = NULL;
  915. int i, j, ret;
  916. struct cfq_rb_root *st;
  917. cfqg = kzalloc_node(sizeof(*cfqg), GFP_ATOMIC, cfqd->queue->node);
  918. if (!cfqg)
  919. return NULL;
  920. for_each_cfqg_st(cfqg, i, j, st)
  921. *st = CFQ_RB_ROOT;
  922. RB_CLEAR_NODE(&cfqg->rb_node);
  923. cfqg->ttime.last_end_request = jiffies;
  924. /*
  925. * Take the initial reference that will be released on destroy
  926. * This can be thought of a joint reference by cgroup and
  927. * elevator which will be dropped by either elevator exit
  928. * or cgroup deletion path depending on who is exiting first.
  929. */
  930. cfqg->ref = 1;
  931. ret = blkio_alloc_blkg_stats(&cfqg->blkg);
  932. if (ret) {
  933. kfree(cfqg);
  934. return NULL;
  935. }
  936. return cfqg;
  937. }
  938. static struct cfq_group *
  939. cfq_find_cfqg(struct cfq_data *cfqd, struct blkio_cgroup *blkcg)
  940. {
  941. struct cfq_group *cfqg = NULL;
  942. void *key = cfqd;
  943. struct backing_dev_info *bdi = &cfqd->queue->backing_dev_info;
  944. unsigned int major, minor;
  945. /*
  946. * This is the common case when there are no blkio cgroups.
  947. * Avoid lookup in this case
  948. */
  949. if (blkcg == &blkio_root_cgroup)
  950. cfqg = &cfqd->root_group;
  951. else
  952. cfqg = cfqg_of_blkg(blkiocg_lookup_group(blkcg, key));
  953. if (cfqg && !cfqg->blkg.dev && bdi->dev && dev_name(bdi->dev)) {
  954. sscanf(dev_name(bdi->dev), "%u:%u", &major, &minor);
  955. cfqg->blkg.dev = MKDEV(major, minor);
  956. }
  957. return cfqg;
  958. }
  959. /*
  960. * Search for the cfq group current task belongs to. request_queue lock must
  961. * be held.
  962. */
  963. static struct cfq_group *cfq_get_cfqg(struct cfq_data *cfqd)
  964. {
  965. struct blkio_cgroup *blkcg;
  966. struct cfq_group *cfqg = NULL, *__cfqg = NULL;
  967. struct request_queue *q = cfqd->queue;
  968. rcu_read_lock();
  969. blkcg = task_blkio_cgroup(current);
  970. cfqg = cfq_find_cfqg(cfqd, blkcg);
  971. if (cfqg) {
  972. rcu_read_unlock();
  973. return cfqg;
  974. }
  975. /*
  976. * Need to allocate a group. Allocation of group also needs allocation
  977. * of per cpu stats which in-turn takes a mutex() and can block. Hence
  978. * we need to drop rcu lock and queue_lock before we call alloc.
  979. *
  980. * Not taking any queue reference here and assuming that queue is
  981. * around by the time we return. CFQ queue allocation code does
  982. * the same. It might be racy though.
  983. */
  984. rcu_read_unlock();
  985. spin_unlock_irq(q->queue_lock);
  986. cfqg = cfq_alloc_cfqg(cfqd);
  987. spin_lock_irq(q->queue_lock);
  988. rcu_read_lock();
  989. blkcg = task_blkio_cgroup(current);
  990. /*
  991. * If some other thread already allocated the group while we were
  992. * not holding queue lock, free up the group
  993. */
  994. __cfqg = cfq_find_cfqg(cfqd, blkcg);
  995. if (__cfqg) {
  996. kfree(cfqg);
  997. rcu_read_unlock();
  998. return __cfqg;
  999. }
  1000. if (!cfqg)
  1001. cfqg = &cfqd->root_group;
  1002. cfq_init_add_cfqg_lists(cfqd, cfqg, blkcg);
  1003. rcu_read_unlock();
  1004. return cfqg;
  1005. }
  1006. static inline struct cfq_group *cfq_ref_get_cfqg(struct cfq_group *cfqg)
  1007. {
  1008. cfqg->ref++;
  1009. return cfqg;
  1010. }
  1011. static void cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg)
  1012. {
  1013. /* Currently, all async queues are mapped to root group */
  1014. if (!cfq_cfqq_sync(cfqq))
  1015. cfqg = &cfqq->cfqd->root_group;
  1016. cfqq->cfqg = cfqg;
  1017. /* cfqq reference on cfqg */
  1018. cfqq->cfqg->ref++;
  1019. }
  1020. static void cfq_put_cfqg(struct cfq_group *cfqg)
  1021. {
  1022. struct cfq_rb_root *st;
  1023. int i, j;
  1024. BUG_ON(cfqg->ref <= 0);
  1025. cfqg->ref--;
  1026. if (cfqg->ref)
  1027. return;
  1028. for_each_cfqg_st(cfqg, i, j, st)
  1029. BUG_ON(!RB_EMPTY_ROOT(&st->rb));
  1030. free_percpu(cfqg->blkg.stats_cpu);
  1031. kfree(cfqg);
  1032. }
  1033. static void cfq_destroy_cfqg(struct cfq_data *cfqd, struct cfq_group *cfqg)
  1034. {
  1035. /* Something wrong if we are trying to remove same group twice */
  1036. BUG_ON(hlist_unhashed(&cfqg->cfqd_node));
  1037. hlist_del_init(&cfqg->cfqd_node);
  1038. BUG_ON(cfqd->nr_blkcg_linked_grps <= 0);
  1039. cfqd->nr_blkcg_linked_grps--;
  1040. /*
  1041. * Put the reference taken at the time of creation so that when all
  1042. * queues are gone, group can be destroyed.
  1043. */
  1044. cfq_put_cfqg(cfqg);
  1045. }
  1046. static void cfq_release_cfq_groups(struct cfq_data *cfqd)
  1047. {
  1048. struct hlist_node *pos, *n;
  1049. struct cfq_group *cfqg;
  1050. hlist_for_each_entry_safe(cfqg, pos, n, &cfqd->cfqg_list, cfqd_node) {
  1051. /*
  1052. * If cgroup removal path got to blk_group first and removed
  1053. * it from cgroup list, then it will take care of destroying
  1054. * cfqg also.
  1055. */
  1056. if (!cfq_blkiocg_del_blkio_group(&cfqg->blkg))
  1057. cfq_destroy_cfqg(cfqd, cfqg);
  1058. }
  1059. }
  1060. /*
  1061. * Blk cgroup controller notification saying that blkio_group object is being
  1062. * delinked as associated cgroup object is going away. That also means that
  1063. * no new IO will come in this group. So get rid of this group as soon as
  1064. * any pending IO in the group is finished.
  1065. *
  1066. * This function is called under rcu_read_lock(). key is the rcu protected
  1067. * pointer. That means "key" is a valid cfq_data pointer as long as we are rcu
  1068. * read lock.
  1069. *
  1070. * "key" was fetched from blkio_group under blkio_cgroup->lock. That means
  1071. * it should not be NULL as even if elevator was exiting, cgroup deltion
  1072. * path got to it first.
  1073. */
  1074. static void cfq_unlink_blkio_group(void *key, struct blkio_group *blkg)
  1075. {
  1076. unsigned long flags;
  1077. struct cfq_data *cfqd = key;
  1078. spin_lock_irqsave(cfqd->queue->queue_lock, flags);
  1079. cfq_destroy_cfqg(cfqd, cfqg_of_blkg(blkg));
  1080. spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
  1081. }
  1082. #else /* GROUP_IOSCHED */
  1083. static struct cfq_group *cfq_get_cfqg(struct cfq_data *cfqd)
  1084. {
  1085. return &cfqd->root_group;
  1086. }
  1087. static inline struct cfq_group *cfq_ref_get_cfqg(struct cfq_group *cfqg)
  1088. {
  1089. return cfqg;
  1090. }
  1091. static inline void
  1092. cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg) {
  1093. cfqq->cfqg = cfqg;
  1094. }
  1095. static void cfq_release_cfq_groups(struct cfq_data *cfqd) {}
  1096. static inline void cfq_put_cfqg(struct cfq_group *cfqg) {}
  1097. #endif /* GROUP_IOSCHED */
  1098. /*
  1099. * The cfqd->service_trees holds all pending cfq_queue's that have
  1100. * requests waiting to be processed. It is sorted in the order that
  1101. * we will service the queues.
  1102. */
  1103. static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
  1104. bool add_front)
  1105. {
  1106. struct rb_node **p, *parent;
  1107. struct cfq_queue *__cfqq;
  1108. unsigned long rb_key;
  1109. struct cfq_rb_root *service_tree;
  1110. int left;
  1111. int new_cfqq = 1;
  1112. service_tree = service_tree_for(cfqq->cfqg, cfqq_prio(cfqq),
  1113. cfqq_type(cfqq));
  1114. if (cfq_class_idle(cfqq)) {
  1115. rb_key = CFQ_IDLE_DELAY;
  1116. parent = rb_last(&service_tree->rb);
  1117. if (parent && parent != &cfqq->rb_node) {
  1118. __cfqq = rb_entry(parent, struct cfq_queue, rb_node);
  1119. rb_key += __cfqq->rb_key;
  1120. } else
  1121. rb_key += jiffies;
  1122. } else if (!add_front) {
  1123. /*
  1124. * Get our rb key offset. Subtract any residual slice
  1125. * value carried from last service. A negative resid
  1126. * count indicates slice overrun, and this should position
  1127. * the next service time further away in the tree.
  1128. */
  1129. rb_key = cfq_slice_offset(cfqd, cfqq) + jiffies;
  1130. rb_key -= cfqq->slice_resid;
  1131. cfqq->slice_resid = 0;
  1132. } else {
  1133. rb_key = -HZ;
  1134. __cfqq = cfq_rb_first(service_tree);
  1135. rb_key += __cfqq ? __cfqq->rb_key : jiffies;
  1136. }
  1137. if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
  1138. new_cfqq = 0;
  1139. /*
  1140. * same position, nothing more to do
  1141. */
  1142. if (rb_key == cfqq->rb_key &&
  1143. cfqq->service_tree == service_tree)
  1144. return;
  1145. cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree);
  1146. cfqq->service_tree = NULL;
  1147. }
  1148. left = 1;
  1149. parent = NULL;
  1150. cfqq->service_tree = service_tree;
  1151. p = &service_tree->rb.rb_node;
  1152. while (*p) {
  1153. struct rb_node **n;
  1154. parent = *p;
  1155. __cfqq = rb_entry(parent, struct cfq_queue, rb_node);
  1156. /*
  1157. * sort by key, that represents service time.
  1158. */
  1159. if (time_before(rb_key, __cfqq->rb_key))
  1160. n = &(*p)->rb_left;
  1161. else {
  1162. n = &(*p)->rb_right;
  1163. left = 0;
  1164. }
  1165. p = n;
  1166. }
  1167. if (left)
  1168. service_tree->left = &cfqq->rb_node;
  1169. cfqq->rb_key = rb_key;
  1170. rb_link_node(&cfqq->rb_node, parent, p);
  1171. rb_insert_color(&cfqq->rb_node, &service_tree->rb);
  1172. service_tree->count++;
  1173. if (add_front || !new_cfqq)
  1174. return;
  1175. cfq_group_notify_queue_add(cfqd, cfqq->cfqg);
  1176. }
  1177. static struct cfq_queue *
  1178. cfq_prio_tree_lookup(struct cfq_data *cfqd, struct rb_root *root,
  1179. sector_t sector, struct rb_node **ret_parent,
  1180. struct rb_node ***rb_link)
  1181. {
  1182. struct rb_node **p, *parent;
  1183. struct cfq_queue *cfqq = NULL;
  1184. parent = NULL;
  1185. p = &root->rb_node;
  1186. while (*p) {
  1187. struct rb_node **n;
  1188. parent = *p;
  1189. cfqq = rb_entry(parent, struct cfq_queue, p_node);
  1190. /*
  1191. * Sort strictly based on sector. Smallest to the left,
  1192. * largest to the right.
  1193. */
  1194. if (sector > blk_rq_pos(cfqq->next_rq))
  1195. n = &(*p)->rb_right;
  1196. else if (sector < blk_rq_pos(cfqq->next_rq))
  1197. n = &(*p)->rb_left;
  1198. else
  1199. break;
  1200. p = n;
  1201. cfqq = NULL;
  1202. }
  1203. *ret_parent = parent;
  1204. if (rb_link)
  1205. *rb_link = p;
  1206. return cfqq;
  1207. }
  1208. static void cfq_prio_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  1209. {
  1210. struct rb_node **p, *parent;
  1211. struct cfq_queue *__cfqq;
  1212. if (cfqq->p_root) {
  1213. rb_erase(&cfqq->p_node, cfqq->p_root);
  1214. cfqq->p_root = NULL;
  1215. }
  1216. if (cfq_class_idle(cfqq))
  1217. return;
  1218. if (!cfqq->next_rq)
  1219. return;
  1220. cfqq->p_root = &cfqd->prio_trees[cfqq->org_ioprio];
  1221. __cfqq = cfq_prio_tree_lookup(cfqd, cfqq->p_root,
  1222. blk_rq_pos(cfqq->next_rq), &parent, &p);
  1223. if (!__cfqq) {
  1224. rb_link_node(&cfqq->p_node, parent, p);
  1225. rb_insert_color(&cfqq->p_node, cfqq->p_root);
  1226. } else
  1227. cfqq->p_root = NULL;
  1228. }
  1229. /*
  1230. * Update cfqq's position in the service tree.
  1231. */
  1232. static void cfq_resort_rr_list(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  1233. {
  1234. /*
  1235. * Resorting requires the cfqq to be on the RR list already.
  1236. */
  1237. if (cfq_cfqq_on_rr(cfqq)) {
  1238. cfq_service_tree_add(cfqd, cfqq, 0);
  1239. cfq_prio_tree_add(cfqd, cfqq);
  1240. }
  1241. }
  1242. /*
  1243. * add to busy list of queues for service, trying to be fair in ordering
  1244. * the pending list according to last request service
  1245. */
  1246. static void cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  1247. {
  1248. cfq_log_cfqq(cfqd, cfqq, "add_to_rr");
  1249. BUG_ON(cfq_cfqq_on_rr(cfqq));
  1250. cfq_mark_cfqq_on_rr(cfqq);
  1251. cfqd->busy_queues++;
  1252. if (cfq_cfqq_sync(cfqq))
  1253. cfqd->busy_sync_queues++;
  1254. cfq_resort_rr_list(cfqd, cfqq);
  1255. }
  1256. /*
  1257. * Called when the cfqq no longer has requests pending, remove it from
  1258. * the service tree.
  1259. */
  1260. static void cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  1261. {
  1262. cfq_log_cfqq(cfqd, cfqq, "del_from_rr");
  1263. BUG_ON(!cfq_cfqq_on_rr(cfqq));
  1264. cfq_clear_cfqq_on_rr(cfqq);
  1265. if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
  1266. cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree);
  1267. cfqq->service_tree = NULL;
  1268. }
  1269. if (cfqq->p_root) {
  1270. rb_erase(&cfqq->p_node, cfqq->p_root);
  1271. cfqq->p_root = NULL;
  1272. }
  1273. cfq_group_notify_queue_del(cfqd, cfqq->cfqg);
  1274. BUG_ON(!cfqd->busy_queues);
  1275. cfqd->busy_queues--;
  1276. if (cfq_cfqq_sync(cfqq))
  1277. cfqd->busy_sync_queues--;
  1278. }
  1279. /*
  1280. * rb tree support functions
  1281. */
  1282. static void cfq_del_rq_rb(struct request *rq)
  1283. {
  1284. struct cfq_queue *cfqq = RQ_CFQQ(rq);
  1285. const int sync = rq_is_sync(rq);
  1286. BUG_ON(!cfqq->queued[sync]);
  1287. cfqq->queued[sync]--;
  1288. elv_rb_del(&cfqq->sort_list, rq);
  1289. if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list)) {
  1290. /*
  1291. * Queue will be deleted from service tree when we actually
  1292. * expire it later. Right now just remove it from prio tree
  1293. * as it is empty.
  1294. */
  1295. if (cfqq->p_root) {
  1296. rb_erase(&cfqq->p_node, cfqq->p_root);
  1297. cfqq->p_root = NULL;
  1298. }
  1299. }
  1300. }
  1301. static void cfq_add_rq_rb(struct request *rq)
  1302. {
  1303. struct cfq_queue *cfqq = RQ_CFQQ(rq);
  1304. struct cfq_data *cfqd = cfqq->cfqd;
  1305. struct request *prev;
  1306. cfqq->queued[rq_is_sync(rq)]++;
  1307. elv_rb_add(&cfqq->sort_list, rq);
  1308. if (!cfq_cfqq_on_rr(cfqq))
  1309. cfq_add_cfqq_rr(cfqd, cfqq);
  1310. /*
  1311. * check if this request is a better next-serve candidate
  1312. */
  1313. prev = cfqq->next_rq;
  1314. cfqq->next_rq = cfq_choose_req(cfqd, cfqq->next_rq, rq, cfqd->last_position);
  1315. /*
  1316. * adjust priority tree position, if ->next_rq changes
  1317. */
  1318. if (prev != cfqq->next_rq)
  1319. cfq_prio_tree_add(cfqd, cfqq);
  1320. BUG_ON(!cfqq->next_rq);
  1321. }
  1322. static void cfq_reposition_rq_rb(struct cfq_queue *cfqq, struct request *rq)
  1323. {
  1324. elv_rb_del(&cfqq->sort_list, rq);
  1325. cfqq->queued[rq_is_sync(rq)]--;
  1326. cfq_blkiocg_update_io_remove_stats(&(RQ_CFQG(rq))->blkg,
  1327. rq_data_dir(rq), rq_is_sync(rq));
  1328. cfq_add_rq_rb(rq);
  1329. cfq_blkiocg_update_io_add_stats(&(RQ_CFQG(rq))->blkg,
  1330. &cfqq->cfqd->serving_group->blkg, rq_data_dir(rq),
  1331. rq_is_sync(rq));
  1332. }
  1333. static struct request *
  1334. cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
  1335. {
  1336. struct task_struct *tsk = current;
  1337. struct cfq_io_cq *cic;
  1338. struct cfq_queue *cfqq;
  1339. cic = cfq_cic_lookup(cfqd, tsk->io_context);
  1340. if (!cic)
  1341. return NULL;
  1342. cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
  1343. if (cfqq) {
  1344. sector_t sector = bio->bi_sector + bio_sectors(bio);
  1345. return elv_rb_find(&cfqq->sort_list, sector);
  1346. }
  1347. return NULL;
  1348. }
  1349. static void cfq_activate_request(struct request_queue *q, struct request *rq)
  1350. {
  1351. struct cfq_data *cfqd = q->elevator->elevator_data;
  1352. cfqd->rq_in_driver++;
  1353. cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "activate rq, drv=%d",
  1354. cfqd->rq_in_driver);
  1355. cfqd->last_position = blk_rq_pos(rq) + blk_rq_sectors(rq);
  1356. }
  1357. static void cfq_deactivate_request(struct request_queue *q, struct request *rq)
  1358. {
  1359. struct cfq_data *cfqd = q->elevator->elevator_data;
  1360. WARN_ON(!cfqd->rq_in_driver);
  1361. cfqd->rq_in_driver--;
  1362. cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "deactivate rq, drv=%d",
  1363. cfqd->rq_in_driver);
  1364. }
  1365. static void cfq_remove_request(struct request *rq)
  1366. {
  1367. struct cfq_queue *cfqq = RQ_CFQQ(rq);
  1368. if (cfqq->next_rq == rq)
  1369. cfqq->next_rq = cfq_find_next_rq(cfqq->cfqd, cfqq, rq);
  1370. list_del_init(&rq->queuelist);
  1371. cfq_del_rq_rb(rq);
  1372. cfqq->cfqd->rq_queued--;
  1373. cfq_blkiocg_update_io_remove_stats(&(RQ_CFQG(rq))->blkg,
  1374. rq_data_dir(rq), rq_is_sync(rq));
  1375. if (rq->cmd_flags & REQ_PRIO) {
  1376. WARN_ON(!cfqq->prio_pending);
  1377. cfqq->prio_pending--;
  1378. }
  1379. }
  1380. static int cfq_merge(struct request_queue *q, struct request **req,
  1381. struct bio *bio)
  1382. {
  1383. struct cfq_data *cfqd = q->elevator->elevator_data;
  1384. struct request *__rq;
  1385. __rq = cfq_find_rq_fmerge(cfqd, bio);
  1386. if (__rq && elv_rq_merge_ok(__rq, bio)) {
  1387. *req = __rq;
  1388. return ELEVATOR_FRONT_MERGE;
  1389. }
  1390. return ELEVATOR_NO_MERGE;
  1391. }
  1392. static void cfq_merged_request(struct request_queue *q, struct request *req,
  1393. int type)
  1394. {
  1395. if (type == ELEVATOR_FRONT_MERGE) {
  1396. struct cfq_queue *cfqq = RQ_CFQQ(req);
  1397. cfq_reposition_rq_rb(cfqq, req);
  1398. }
  1399. }
  1400. static void cfq_bio_merged(struct request_queue *q, struct request *req,
  1401. struct bio *bio)
  1402. {
  1403. cfq_blkiocg_update_io_merged_stats(&(RQ_CFQG(req))->blkg,
  1404. bio_data_dir(bio), cfq_bio_sync(bio));
  1405. }
  1406. static void
  1407. cfq_merged_requests(struct request_queue *q, struct request *rq,
  1408. struct request *next)
  1409. {
  1410. struct cfq_queue *cfqq = RQ_CFQQ(rq);
  1411. struct cfq_data *cfqd = q->elevator->elevator_data;
  1412. /*
  1413. * reposition in fifo if next is older than rq
  1414. */
  1415. if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&
  1416. time_before(rq_fifo_time(next), rq_fifo_time(rq))) {
  1417. list_move(&rq->queuelist, &next->queuelist);
  1418. rq_set_fifo_time(rq, rq_fifo_time(next));
  1419. }
  1420. if (cfqq->next_rq == next)
  1421. cfqq->next_rq = rq;
  1422. cfq_remove_request(next);
  1423. cfq_blkiocg_update_io_merged_stats(&(RQ_CFQG(rq))->blkg,
  1424. rq_data_dir(next), rq_is_sync(next));
  1425. cfqq = RQ_CFQQ(next);
  1426. /*
  1427. * all requests of this queue are merged to other queues, delete it
  1428. * from the service tree. If it's the active_queue,
  1429. * cfq_dispatch_requests() will choose to expire it or do idle
  1430. */
  1431. if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list) &&
  1432. cfqq != cfqd->active_queue)
  1433. cfq_del_cfqq_rr(cfqd, cfqq);
  1434. }
  1435. static int cfq_allow_merge(struct request_queue *q, struct request *rq,
  1436. struct bio *bio)
  1437. {
  1438. struct cfq_data *cfqd = q->elevator->elevator_data;
  1439. struct cfq_io_cq *cic;
  1440. struct cfq_queue *cfqq;
  1441. /*
  1442. * Disallow merge of a sync bio into an async request.
  1443. */
  1444. if (cfq_bio_sync(bio) && !rq_is_sync(rq))
  1445. return false;
  1446. /*
  1447. * Lookup the cfqq that this bio will be queued with and allow
  1448. * merge only if rq is queued there.
  1449. */
  1450. cic = cfq_cic_lookup(cfqd, current->io_context);
  1451. if (!cic)
  1452. return false;
  1453. cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
  1454. return cfqq == RQ_CFQQ(rq);
  1455. }
  1456. static inline void cfq_del_timer(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  1457. {
  1458. del_timer(&cfqd->idle_slice_timer);
  1459. cfq_blkiocg_update_idle_time_stats(&cfqq->cfqg->blkg);
  1460. }
  1461. static void __cfq_set_active_queue(struct cfq_data *cfqd,
  1462. struct cfq_queue *cfqq)
  1463. {
  1464. if (cfqq) {
  1465. cfq_log_cfqq(cfqd, cfqq, "set_active wl_prio:%d wl_type:%d",
  1466. cfqd->serving_prio, cfqd->serving_type);
  1467. cfq_blkiocg_update_avg_queue_size_stats(&cfqq->cfqg->blkg);
  1468. cfqq->slice_start = 0;
  1469. cfqq->dispatch_start = jiffies;
  1470. cfqq->allocated_slice = 0;
  1471. cfqq->slice_end = 0;
  1472. cfqq->slice_dispatch = 0;
  1473. cfqq->nr_sectors = 0;
  1474. cfq_clear_cfqq_wait_request(cfqq);
  1475. cfq_clear_cfqq_must_dispatch(cfqq);
  1476. cfq_clear_cfqq_must_alloc_slice(cfqq);
  1477. cfq_clear_cfqq_fifo_expire(cfqq);
  1478. cfq_mark_cfqq_slice_new(cfqq);
  1479. cfq_del_timer(cfqd, cfqq);
  1480. }
  1481. cfqd->active_queue = cfqq;
  1482. }
  1483. /*
  1484. * current cfqq expired its slice (or was too idle), select new one
  1485. */
  1486. static void
  1487. __cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
  1488. bool timed_out)
  1489. {
  1490. cfq_log_cfqq(cfqd, cfqq, "slice expired t=%d", timed_out);
  1491. if (cfq_cfqq_wait_request(cfqq))
  1492. cfq_del_timer(cfqd, cfqq);
  1493. cfq_clear_cfqq_wait_request(cfqq);
  1494. cfq_clear_cfqq_wait_busy(cfqq);
  1495. /*
  1496. * If this cfqq is shared between multiple processes, check to
  1497. * make sure that those processes are still issuing I/Os within
  1498. * the mean seek distance. If not, it may be time to break the
  1499. * queues apart again.
  1500. */
  1501. if (cfq_cfqq_coop(cfqq) && CFQQ_SEEKY(cfqq))
  1502. cfq_mark_cfqq_split_coop(cfqq);
  1503. /*
  1504. * store what was left of this slice, if the queue idled/timed out
  1505. */
  1506. if (timed_out) {
  1507. if (cfq_cfqq_slice_new(cfqq))
  1508. cfqq->slice_resid = cfq_scaled_cfqq_slice(cfqd, cfqq);
  1509. else
  1510. cfqq->slice_resid = cfqq->slice_end - jiffies;
  1511. cfq_log_cfqq(cfqd, cfqq, "resid=%ld", cfqq->slice_resid);
  1512. }
  1513. cfq_group_served(cfqd, cfqq->cfqg, cfqq);
  1514. if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list))
  1515. cfq_del_cfqq_rr(cfqd, cfqq);
  1516. cfq_resort_rr_list(cfqd, cfqq);
  1517. if (cfqq == cfqd->active_queue)
  1518. cfqd->active_queue = NULL;
  1519. if (cfqd->active_cic) {
  1520. put_io_context(cfqd->active_cic->icq.ioc);
  1521. cfqd->active_cic = NULL;
  1522. }
  1523. }
  1524. static inline void cfq_slice_expired(struct cfq_data *cfqd, bool timed_out)
  1525. {
  1526. struct cfq_queue *cfqq = cfqd->active_queue;
  1527. if (cfqq)
  1528. __cfq_slice_expired(cfqd, cfqq, timed_out);
  1529. }
  1530. /*
  1531. * Get next queue for service. Unless we have a queue preemption,
  1532. * we'll simply select the first cfqq in the service tree.
  1533. */
  1534. static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
  1535. {
  1536. struct cfq_rb_root *service_tree =
  1537. service_tree_for(cfqd->serving_group, cfqd->serving_prio,
  1538. cfqd->serving_type);
  1539. if (!cfqd->rq_queued)
  1540. return NULL;
  1541. /* There is nothing to dispatch */
  1542. if (!service_tree)
  1543. return NULL;
  1544. if (RB_EMPTY_ROOT(&service_tree->rb))
  1545. return NULL;
  1546. return cfq_rb_first(service_tree);
  1547. }
  1548. static struct cfq_queue *cfq_get_next_queue_forced(struct cfq_data *cfqd)
  1549. {
  1550. struct cfq_group *cfqg;
  1551. struct cfq_queue *cfqq;
  1552. int i, j;
  1553. struct cfq_rb_root *st;
  1554. if (!cfqd->rq_queued)
  1555. return NULL;
  1556. cfqg = cfq_get_next_cfqg(cfqd);
  1557. if (!cfqg)
  1558. return NULL;
  1559. for_each_cfqg_st(cfqg, i, j, st)
  1560. if ((cfqq = cfq_rb_first(st)) != NULL)
  1561. return cfqq;
  1562. return NULL;
  1563. }
  1564. /*
  1565. * Get and set a new active queue for service.
  1566. */
  1567. static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd,
  1568. struct cfq_queue *cfqq)
  1569. {
  1570. if (!cfqq)
  1571. cfqq = cfq_get_next_queue(cfqd);
  1572. __cfq_set_active_queue(cfqd, cfqq);
  1573. return cfqq;
  1574. }
  1575. static inline sector_t cfq_dist_from_last(struct cfq_data *cfqd,
  1576. struct request *rq)
  1577. {
  1578. if (blk_rq_pos(rq) >= cfqd->last_position)
  1579. return blk_rq_pos(rq) - cfqd->last_position;
  1580. else
  1581. return cfqd->last_position - blk_rq_pos(rq);
  1582. }
  1583. static inline int cfq_rq_close(struct cfq_data *cfqd, struct cfq_queue *cfqq,
  1584. struct request *rq)
  1585. {
  1586. return cfq_dist_from_last(cfqd, rq) <= CFQQ_CLOSE_THR;
  1587. }
  1588. static struct cfq_queue *cfqq_close(struct cfq_data *cfqd,
  1589. struct cfq_queue *cur_cfqq)
  1590. {
  1591. struct rb_root *root = &cfqd->prio_trees[cur_cfqq->org_ioprio];
  1592. struct rb_node *parent, *node;
  1593. struct cfq_queue *__cfqq;
  1594. sector_t sector = cfqd->last_position;
  1595. if (RB_EMPTY_ROOT(root))
  1596. return NULL;
  1597. /*
  1598. * First, if we find a request starting at the end of the last
  1599. * request, choose it.
  1600. */
  1601. __cfqq = cfq_prio_tree_lookup(cfqd, root, sector, &parent, NULL);
  1602. if (__cfqq)
  1603. return __cfqq;
  1604. /*
  1605. * If the exact sector wasn't found, the parent of the NULL leaf
  1606. * will contain the closest sector.
  1607. */
  1608. __cfqq = rb_entry(parent, struct cfq_queue, p_node);
  1609. if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq))
  1610. return __cfqq;
  1611. if (blk_rq_pos(__cfqq->next_rq) < sector)
  1612. node = rb_next(&__cfqq->p_node);
  1613. else
  1614. node = rb_prev(&__cfqq->p_node);
  1615. if (!node)
  1616. return NULL;
  1617. __cfqq = rb_entry(node, struct cfq_queue, p_node);
  1618. if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq))
  1619. return __cfqq;
  1620. return NULL;
  1621. }
  1622. /*
  1623. * cfqd - obvious
  1624. * cur_cfqq - passed in so that we don't decide that the current queue is
  1625. * closely cooperating with itself.
  1626. *
  1627. * So, basically we're assuming that that cur_cfqq has dispatched at least
  1628. * one request, and that cfqd->last_position reflects a position on the disk
  1629. * associated with the I/O issued by cur_cfqq. I'm not sure this is a valid
  1630. * assumption.
  1631. */
  1632. static struct cfq_queue *cfq_close_cooperator(struct cfq_data *cfqd,
  1633. struct cfq_queue *cur_cfqq)
  1634. {
  1635. struct cfq_queue *cfqq;
  1636. if (cfq_class_idle(cur_cfqq))
  1637. return NULL;
  1638. if (!cfq_cfqq_sync(cur_cfqq))
  1639. return NULL;
  1640. if (CFQQ_SEEKY(cur_cfqq))
  1641. return NULL;
  1642. /*
  1643. * Don't search priority tree if it's the only queue in the group.
  1644. */
  1645. if (cur_cfqq->cfqg->nr_cfqq == 1)
  1646. return NULL;
  1647. /*
  1648. * We should notice if some of the queues are cooperating, eg
  1649. * working closely on the same area of the disk. In that case,
  1650. * we can group them together and don't waste time idling.
  1651. */
  1652. cfqq = cfqq_close(cfqd, cur_cfqq);
  1653. if (!cfqq)
  1654. return NULL;
  1655. /* If new queue belongs to different cfq_group, don't choose it */
  1656. if (cur_cfqq->cfqg != cfqq->cfqg)
  1657. return NULL;
  1658. /*
  1659. * It only makes sense to merge sync queues.
  1660. */
  1661. if (!cfq_cfqq_sync(cfqq))
  1662. return NULL;
  1663. if (CFQQ_SEEKY(cfqq))
  1664. return NULL;
  1665. /*
  1666. * Do not merge queues of different priority classes
  1667. */
  1668. if (cfq_class_rt(cfqq) != cfq_class_rt(cur_cfqq))
  1669. return NULL;
  1670. return cfqq;
  1671. }
  1672. /*
  1673. * Determine whether we should enforce idle window for this queue.
  1674. */
  1675. static bool cfq_should_idle(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  1676. {
  1677. enum wl_prio_t prio = cfqq_prio(cfqq);
  1678. struct cfq_rb_root *service_tree = cfqq->service_tree;
  1679. BUG_ON(!service_tree);
  1680. BUG_ON(!service_tree->count);
  1681. if (!cfqd->cfq_slice_idle)
  1682. return false;
  1683. /* We never do for idle class queues. */
  1684. if (prio == IDLE_WORKLOAD)
  1685. return false;
  1686. /* We do for queues that were marked with idle window flag. */
  1687. if (cfq_cfqq_idle_window(cfqq) &&
  1688. !(blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag))
  1689. return true;
  1690. /*
  1691. * Otherwise, we do only if they are the last ones
  1692. * in their service tree.
  1693. */
  1694. if (service_tree->count == 1 && cfq_cfqq_sync(cfqq) &&
  1695. !cfq_io_thinktime_big(cfqd, &service_tree->ttime, false))
  1696. return true;
  1697. cfq_log_cfqq(cfqd, cfqq, "Not idling. st->count:%d",
  1698. service_tree->count);
  1699. return false;
  1700. }
  1701. static void cfq_arm_slice_timer(struct cfq_data *cfqd)
  1702. {
  1703. struct cfq_queue *cfqq = cfqd->active_queue;
  1704. struct cfq_io_cq *cic;
  1705. unsigned long sl, group_idle = 0;
  1706. /*
  1707. * SSD device without seek penalty, disable idling. But only do so
  1708. * for devices that support queuing, otherwise we still have a problem
  1709. * with sync vs async workloads.
  1710. */
  1711. if (blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag)
  1712. return;
  1713. WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list));
  1714. WARN_ON(cfq_cfqq_slice_new(cfqq));
  1715. /*
  1716. * idle is disabled, either manually or by past process history
  1717. */
  1718. if (!cfq_should_idle(cfqd, cfqq)) {
  1719. /* no queue idling. Check for group idling */
  1720. if (cfqd->cfq_group_idle)
  1721. group_idle = cfqd->cfq_group_idle;
  1722. else
  1723. return;
  1724. }
  1725. /*
  1726. * still active requests from this queue, don't idle
  1727. */
  1728. if (cfqq->dispatched)
  1729. return;
  1730. /*
  1731. * task has exited, don't wait
  1732. */
  1733. cic = cfqd->active_cic;
  1734. if (!cic || !atomic_read(&cic->icq.ioc->nr_tasks))
  1735. return;
  1736. /*
  1737. * If our average think time is larger than the remaining time
  1738. * slice, then don't idle. This avoids overrunning the allotted
  1739. * time slice.
  1740. */
  1741. if (sample_valid(cic->ttime.ttime_samples) &&
  1742. (cfqq->slice_end - jiffies < cic->ttime.ttime_mean)) {
  1743. cfq_log_cfqq(cfqd, cfqq, "Not idling. think_time:%lu",
  1744. cic->ttime.ttime_mean);
  1745. return;
  1746. }
  1747. /* There are other queues in the group, don't do group idle */
  1748. if (group_idle && cfqq->cfqg->nr_cfqq > 1)
  1749. return;
  1750. cfq_mark_cfqq_wait_request(cfqq);
  1751. if (group_idle)
  1752. sl = cfqd->cfq_group_idle;
  1753. else
  1754. sl = cfqd->cfq_slice_idle;
  1755. mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
  1756. cfq_blkiocg_update_set_idle_time_stats(&cfqq->cfqg->blkg);
  1757. cfq_log_cfqq(cfqd, cfqq, "arm_idle: %lu group_idle: %d", sl,
  1758. group_idle ? 1 : 0);
  1759. }
  1760. /*
  1761. * Move request from internal lists to the request queue dispatch list.
  1762. */
  1763. static void cfq_dispatch_insert(struct request_queue *q, struct request *rq)
  1764. {
  1765. struct cfq_data *cfqd = q->elevator->elevator_data;
  1766. struct cfq_queue *cfqq = RQ_CFQQ(rq);
  1767. cfq_log_cfqq(cfqd, cfqq, "dispatch_insert");
  1768. cfqq->next_rq = cfq_find_next_rq(cfqd, cfqq, rq);
  1769. cfq_remove_request(rq);
  1770. cfqq->dispatched++;
  1771. (RQ_CFQG(rq))->dispatched++;
  1772. elv_dispatch_sort(q, rq);
  1773. cfqd->rq_in_flight[cfq_cfqq_sync(cfqq)]++;
  1774. cfqq->nr_sectors += blk_rq_sectors(rq);
  1775. cfq_blkiocg_update_dispatch_stats(&cfqq->cfqg->blkg, blk_rq_bytes(rq),
  1776. rq_data_dir(rq), rq_is_sync(rq));
  1777. }
  1778. /*
  1779. * return expired entry, or NULL to just start from scratch in rbtree
  1780. */
  1781. static struct request *cfq_check_fifo(struct cfq_queue *cfqq)
  1782. {
  1783. struct request *rq = NULL;
  1784. if (cfq_cfqq_fifo_expire(cfqq))
  1785. return NULL;
  1786. cfq_mark_cfqq_fifo_expire(cfqq);
  1787. if (list_empty(&cfqq->fifo))
  1788. return NULL;
  1789. rq = rq_entry_fifo(cfqq->fifo.next);
  1790. if (time_before(jiffies, rq_fifo_time(rq)))
  1791. rq = NULL;
  1792. cfq_log_cfqq(cfqq->cfqd, cfqq, "fifo=%p", rq);
  1793. return rq;
  1794. }
  1795. static inline int
  1796. cfq_prio_to_maxrq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  1797. {
  1798. const int base_rq = cfqd->cfq_slice_async_rq;
  1799. WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);
  1800. return 2 * base_rq * (IOPRIO_BE_NR - cfqq->ioprio);
  1801. }
  1802. /*
  1803. * Must be called with the queue_lock held.
  1804. */
  1805. static int cfqq_process_refs(struct cfq_queue *cfqq)
  1806. {
  1807. int process_refs, io_refs;
  1808. io_refs = cfqq->allocated[READ] + cfqq->allocated[WRITE];
  1809. process_refs = cfqq->ref - io_refs;
  1810. BUG_ON(process_refs < 0);
  1811. return process_refs;
  1812. }
  1813. static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq)
  1814. {
  1815. int process_refs, new_process_refs;
  1816. struct cfq_queue *__cfqq;
  1817. /*
  1818. * If there are no process references on the new_cfqq, then it is
  1819. * unsafe to follow the ->new_cfqq chain as other cfqq's in the
  1820. * chain may have dropped their last reference (not just their
  1821. * last process reference).
  1822. */
  1823. if (!cfqq_process_refs(new_cfqq))
  1824. return;
  1825. /* Avoid a circular list and skip interim queue merges */
  1826. while ((__cfqq = new_cfqq->new_cfqq)) {
  1827. if (__cfqq == cfqq)
  1828. return;
  1829. new_cfqq = __cfqq;
  1830. }
  1831. process_refs = cfqq_process_refs(cfqq);
  1832. new_process_refs = cfqq_process_refs(new_cfqq);
  1833. /*
  1834. * If the process for the cfqq has gone away, there is no
  1835. * sense in merging the queues.
  1836. */
  1837. if (process_refs == 0 || new_process_refs == 0)
  1838. return;
  1839. /*
  1840. * Merge in the direction of the lesser amount of work.
  1841. */
  1842. if (new_process_refs >= process_refs) {
  1843. cfqq->new_cfqq = new_cfqq;
  1844. new_cfqq->ref += process_refs;
  1845. } else {
  1846. new_cfqq->new_cfqq = cfqq;
  1847. cfqq->ref += new_process_refs;
  1848. }
  1849. }
  1850. static enum wl_type_t cfq_choose_wl(struct cfq_data *cfqd,
  1851. struct cfq_group *cfqg, enum wl_prio_t prio)
  1852. {
  1853. struct cfq_queue *queue;
  1854. int i;
  1855. bool key_valid = false;
  1856. unsigned long lowest_key = 0;
  1857. enum wl_type_t cur_best = SYNC_NOIDLE_WORKLOAD;
  1858. for (i = 0; i <= SYNC_WORKLOAD; ++i) {
  1859. /* select the one with lowest rb_key */
  1860. queue = cfq_rb_first(service_tree_for(cfqg, prio, i));
  1861. if (queue &&
  1862. (!key_valid || time_before(queue->rb_key, lowest_key))) {
  1863. lowest_key = queue->rb_key;
  1864. cur_best = i;
  1865. key_valid = true;
  1866. }
  1867. }
  1868. return cur_best;
  1869. }
  1870. static void choose_service_tree(struct cfq_data *cfqd, struct cfq_group *cfqg)
  1871. {
  1872. unsigned slice;
  1873. unsigned count;
  1874. struct cfq_rb_root *st;
  1875. unsigned group_slice;
  1876. enum wl_prio_t original_prio = cfqd->serving_prio;
  1877. /* Choose next priority. RT > BE > IDLE */
  1878. if (cfq_group_busy_queues_wl(RT_WORKLOAD, cfqd, cfqg))
  1879. cfqd->serving_prio = RT_WORKLOAD;
  1880. else if (cfq_group_busy_queues_wl(BE_WORKLOAD, cfqd, cfqg))
  1881. cfqd->serving_prio = BE_WORKLOAD;
  1882. else {
  1883. cfqd->serving_prio = IDLE_WORKLOAD;
  1884. cfqd->workload_expires = jiffies + 1;
  1885. return;
  1886. }
  1887. if (original_prio != cfqd->serving_prio)
  1888. goto new_workload;
  1889. /*
  1890. * For RT and BE, we have to choose also the type
  1891. * (SYNC, SYNC_NOIDLE, ASYNC), and to compute a workload
  1892. * expiration time
  1893. */
  1894. st = service_tree_for(cfqg, cfqd->serving_prio, cfqd->serving_type);
  1895. count = st->count;
  1896. /*
  1897. * check workload expiration, and that we still have other queues ready
  1898. */
  1899. if (count && !time_after(jiffies, cfqd->workload_expires))
  1900. return;
  1901. new_workload:
  1902. /* otherwise select new workload type */
  1903. cfqd->serving_type =
  1904. cfq_choose_wl(cfqd, cfqg, cfqd->serving_prio);
  1905. st = service_tree_for(cfqg, cfqd->serving_prio, cfqd->serving_type);
  1906. count = st->count;
  1907. /*
  1908. * the workload slice is computed as a fraction of target latency
  1909. * proportional to the number of queues in that workload, over
  1910. * all the queues in the same priority class
  1911. */
  1912. group_slice = cfq_group_slice(cfqd, cfqg);
  1913. slice = group_slice * count /
  1914. max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_prio],
  1915. cfq_group_busy_queues_wl(cfqd->serving_prio, cfqd, cfqg));
  1916. if (cfqd->serving_type == ASYNC_WORKLOAD) {
  1917. unsigned int tmp;
  1918. /*
  1919. * Async queues are currently system wide. Just taking
  1920. * proportion of queues with-in same group will lead to higher
  1921. * async ratio system wide as generally root group is going
  1922. * to have higher weight. A more accurate thing would be to
  1923. * calculate system wide asnc/sync ratio.
  1924. */
  1925. tmp = cfq_target_latency * cfqg_busy_async_queues(cfqd, cfqg);
  1926. tmp = tmp/cfqd->busy_queues;
  1927. slice = min_t(unsigned, slice, tmp);
  1928. /* async workload slice is scaled down according to
  1929. * the sync/async slice ratio. */
  1930. slice = slice * cfqd->cfq_slice[0] / cfqd->cfq_slice[1];
  1931. } else
  1932. /* sync workload slice is at least 2 * cfq_slice_idle */
  1933. slice = max(slice, 2 * cfqd->cfq_slice_idle);
  1934. slice = max_t(unsigned, slice, CFQ_MIN_TT);
  1935. cfq_log(cfqd, "workload slice:%d", slice);
  1936. cfqd->workload_expires = jiffies + slice;
  1937. }
  1938. static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd)
  1939. {
  1940. struct cfq_rb_root *st = &cfqd->grp_service_tree;
  1941. struct cfq_group *cfqg;
  1942. if (RB_EMPTY_ROOT(&st->rb))
  1943. return NULL;
  1944. cfqg = cfq_rb_first_group(st);
  1945. update_min_vdisktime(st);
  1946. return cfqg;
  1947. }
  1948. static void cfq_choose_cfqg(struct cfq_data *cfqd)
  1949. {
  1950. struct cfq_group *cfqg = cfq_get_next_cfqg(cfqd);
  1951. cfqd->serving_group = cfqg;
  1952. /* Restore the workload type data */
  1953. if (cfqg->saved_workload_slice) {
  1954. cfqd->workload_expires = jiffies + cfqg->saved_workload_slice;
  1955. cfqd->serving_type = cfqg->saved_workload;
  1956. cfqd->serving_prio = cfqg->saved_serving_prio;
  1957. } else
  1958. cfqd->workload_expires = jiffies - 1;
  1959. choose_service_tree(cfqd, cfqg);
  1960. }
  1961. /*
  1962. * Select a queue for service. If we have a current active queue,
  1963. * check whether to continue servicing it, or retrieve and set a new one.
  1964. */
  1965. static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
  1966. {
  1967. struct cfq_queue *cfqq, *new_cfqq = NULL;
  1968. cfqq = cfqd->active_queue;
  1969. if (!cfqq)
  1970. goto new_queue;
  1971. if (!cfqd->rq_queued)
  1972. return NULL;
  1973. /*
  1974. * We were waiting for group to get backlogged. Expire the queue
  1975. */
  1976. if (cfq_cfqq_wait_busy(cfqq) && !RB_EMPTY_ROOT(&cfqq->sort_list))
  1977. goto expire;
  1978. /*
  1979. * The active queue has run out of time, expire it and select new.
  1980. */
  1981. if (cfq_slice_used(cfqq) && !cfq_cfqq_must_dispatch(cfqq)) {
  1982. /*
  1983. * If slice had not expired at the completion of last request
  1984. * we might not have turned on wait_busy flag. Don't expire
  1985. * the queue yet. Allow the group to get backlogged.
  1986. *
  1987. * The very fact that we have used the slice, that means we
  1988. * have been idling all along on this queue and it should be
  1989. * ok to wait for this request to complete.
  1990. */
  1991. if (cfqq->cfqg->nr_cfqq == 1 && RB_EMPTY_ROOT(&cfqq->sort_list)
  1992. && cfqq->dispatched && cfq_should_idle(cfqd, cfqq)) {
  1993. cfqq = NULL;
  1994. goto keep_queue;
  1995. } else
  1996. goto check_group_idle;
  1997. }
  1998. /*
  1999. * The active queue has requests and isn't expired, allow it to
  2000. * dispatch.
  2001. */
  2002. if (!RB_EMPTY_ROOT(&cfqq->sort_list))
  2003. goto keep_queue;
  2004. /*
  2005. * If another queue has a request waiting within our mean seek
  2006. * distance, let it run. The expire code will check for close
  2007. * cooperators and put the close queue at the front of the service
  2008. * tree. If possible, merge the expiring queue with the new cfqq.
  2009. */
  2010. new_cfqq = cfq_close_cooperator(cfqd, cfqq);
  2011. if (new_cfqq) {
  2012. if (!cfqq->new_cfqq)
  2013. cfq_setup_merge(cfqq, new_cfqq);
  2014. goto expire;
  2015. }
  2016. /*
  2017. * No requests pending. If the active queue still has requests in
  2018. * flight or is idling for a new request, allow either of these
  2019. * conditions to happen (or time out) before selecting a new queue.
  2020. */
  2021. if (timer_pending(&cfqd->idle_slice_timer)) {
  2022. cfqq = NULL;
  2023. goto keep_queue;
  2024. }
  2025. /*
  2026. * This is a deep seek queue, but the device is much faster than
  2027. * the queue can deliver, don't idle
  2028. **/
  2029. if (CFQQ_SEEKY(cfqq) && cfq_cfqq_idle_window(cfqq) &&
  2030. (cfq_cfqq_slice_new(cfqq) ||
  2031. (cfqq->slice_end - jiffies > jiffies - cfqq->slice_start))) {
  2032. cfq_clear_cfqq_deep(cfqq);
  2033. cfq_clear_cfqq_idle_window(cfqq);
  2034. }
  2035. if (cfqq->dispatched && cfq_should_idle(cfqd, cfqq)) {
  2036. cfqq = NULL;
  2037. goto keep_queue;
  2038. }
  2039. /*
  2040. * If group idle is enabled and there are requests dispatched from
  2041. * this group, wait for requests to complete.
  2042. */
  2043. check_group_idle:
  2044. if (cfqd->cfq_group_idle && cfqq->cfqg->nr_cfqq == 1 &&
  2045. cfqq->cfqg->dispatched &&
  2046. !cfq_io_thinktime_big(cfqd, &cfqq->cfqg->ttime, true)) {
  2047. cfqq = NULL;
  2048. goto keep_queue;
  2049. }
  2050. expire:
  2051. cfq_slice_expired(cfqd, 0);
  2052. new_queue:
  2053. /*
  2054. * Current queue expired. Check if we have to switch to a new
  2055. * service tree
  2056. */
  2057. if (!new_cfqq)
  2058. cfq_choose_cfqg(cfqd);
  2059. cfqq = cfq_set_active_queue(cfqd, new_cfqq);
  2060. keep_queue:
  2061. return cfqq;
  2062. }
  2063. static int __cfq_forced_dispatch_cfqq(struct cfq_queue *cfqq)
  2064. {
  2065. int dispatched = 0;
  2066. while (cfqq->next_rq) {
  2067. cfq_dispatch_insert(cfqq->cfqd->queue, cfqq->next_rq);
  2068. dispatched++;
  2069. }
  2070. BUG_ON(!list_empty(&cfqq->fifo));
  2071. /* By default cfqq is not expired if it is empty. Do it explicitly */
  2072. __cfq_slice_expired(cfqq->cfqd, cfqq, 0);
  2073. return dispatched;
  2074. }
  2075. /*
  2076. * Drain our current requests. Used for barriers and when switching
  2077. * io schedulers on-the-fly.
  2078. */
  2079. static int cfq_forced_dispatch(struct cfq_data *cfqd)
  2080. {
  2081. struct cfq_queue *cfqq;
  2082. int dispatched = 0;
  2083. /* Expire the timeslice of the current active queue first */
  2084. cfq_slice_expired(cfqd, 0);
  2085. while ((cfqq = cfq_get_next_queue_forced(cfqd)) != NULL) {
  2086. __cfq_set_active_queue(cfqd, cfqq);
  2087. dispatched += __cfq_forced_dispatch_cfqq(cfqq);
  2088. }
  2089. BUG_ON(cfqd->busy_queues);
  2090. cfq_log(cfqd, "forced_dispatch=%d", dispatched);
  2091. return dispatched;
  2092. }
  2093. static inline bool cfq_slice_used_soon(struct cfq_data *cfqd,
  2094. struct cfq_queue *cfqq)
  2095. {
  2096. /* the queue hasn't finished any request, can't estimate */
  2097. if (cfq_cfqq_slice_new(cfqq))
  2098. return true;
  2099. if (time_after(jiffies + cfqd->cfq_slice_idle * cfqq->dispatched,
  2100. cfqq->slice_end))
  2101. return true;
  2102. return false;
  2103. }
  2104. static bool cfq_may_dispatch(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  2105. {
  2106. unsigned int max_dispatch;
  2107. /*
  2108. * Drain async requests before we start sync IO
  2109. */
  2110. if (cfq_should_idle(cfqd, cfqq) && cfqd->rq_in_flight[BLK_RW_ASYNC])
  2111. return false;
  2112. /*
  2113. * If this is an async queue and we have sync IO in flight, let it wait
  2114. */
  2115. if (cfqd->rq_in_flight[BLK_RW_SYNC] && !cfq_cfqq_sync(cfqq))
  2116. return false;
  2117. max_dispatch = max_t(unsigned int, cfqd->cfq_quantum / 2, 1);
  2118. if (cfq_class_idle(cfqq))
  2119. max_dispatch = 1;
  2120. /*
  2121. * Does this cfqq already have too much IO in flight?
  2122. */
  2123. if (cfqq->dispatched >= max_dispatch) {
  2124. bool promote_sync = false;
  2125. /*
  2126. * idle queue must always only have a single IO in flight
  2127. */
  2128. if (cfq_class_idle(cfqq))
  2129. return false;
  2130. /*
  2131. * If there is only one sync queue
  2132. * we can ignore async queue here and give the sync
  2133. * queue no dispatch limit. The reason is a sync queue can
  2134. * preempt async queue, limiting the sync queue doesn't make
  2135. * sense. This is useful for aiostress test.
  2136. */
  2137. if (cfq_cfqq_sync(cfqq) && cfqd->busy_sync_queues == 1)
  2138. promote_sync = true;
  2139. /*
  2140. * We have other queues, don't allow more IO from this one
  2141. */
  2142. if (cfqd->busy_queues > 1 && cfq_slice_used_soon(cfqd, cfqq) &&
  2143. !promote_sync)
  2144. return false;
  2145. /*
  2146. * Sole queue user, no limit
  2147. */
  2148. if (cfqd->busy_queues == 1 || promote_sync)
  2149. max_dispatch = -1;
  2150. else
  2151. /*
  2152. * Normally we start throttling cfqq when cfq_quantum/2
  2153. * requests have been dispatched. But we can drive
  2154. * deeper queue depths at the beginning of slice
  2155. * subjected to upper limit of cfq_quantum.
  2156. * */
  2157. max_dispatch = cfqd->cfq_quantum;
  2158. }
  2159. /*
  2160. * Async queues must wait a bit before being allowed dispatch.
  2161. * We also ramp up the dispatch depth gradually for async IO,
  2162. * based on the last sync IO we serviced
  2163. */
  2164. if (!cfq_cfqq_sync(cfqq) && cfqd->cfq_latency) {
  2165. unsigned long last_sync = jiffies - cfqd->last_delayed_sync;
  2166. unsigned int depth;
  2167. depth = last_sync / cfqd->cfq_slice[1];
  2168. if (!depth && !cfqq->dispatched)
  2169. depth = 1;
  2170. if (depth < max_dispatch)
  2171. max_dispatch = depth;
  2172. }
  2173. /*
  2174. * If we're below the current max, allow a dispatch
  2175. */
  2176. return cfqq->dispatched < max_dispatch;
  2177. }
  2178. /*
  2179. * Dispatch a request from cfqq, moving them to the request queue
  2180. * dispatch list.
  2181. */
  2182. static bool cfq_dispatch_request(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  2183. {
  2184. struct request *rq;
  2185. BUG_ON(RB_EMPTY_ROOT(&cfqq->sort_list));
  2186. if (!cfq_may_dispatch(cfqd, cfqq))
  2187. return false;
  2188. /*
  2189. * follow expired path, else get first next available
  2190. */
  2191. rq = cfq_check_fifo(cfqq);
  2192. if (!rq)
  2193. rq = cfqq->next_rq;
  2194. /*
  2195. * insert request into driver dispatch list
  2196. */
  2197. cfq_dispatch_insert(cfqd->queue, rq);
  2198. if (!cfqd->active_cic) {
  2199. struct cfq_io_cq *cic = RQ_CIC(rq);
  2200. atomic_long_inc(&cic->icq.ioc->refcount);
  2201. cfqd->active_cic = cic;
  2202. }
  2203. return true;
  2204. }
  2205. /*
  2206. * Find the cfqq that we need to service and move a request from that to the
  2207. * dispatch list
  2208. */
  2209. static int cfq_dispatch_requests(struct request_queue *q, int force)
  2210. {
  2211. struct cfq_data *cfqd = q->elevator->elevator_data;
  2212. struct cfq_queue *cfqq;
  2213. if (!cfqd->busy_queues)
  2214. return 0;
  2215. if (unlikely(force))
  2216. return cfq_forced_dispatch(cfqd);
  2217. cfqq = cfq_select_queue(cfqd);
  2218. if (!cfqq)
  2219. return 0;
  2220. /*
  2221. * Dispatch a request from this cfqq, if it is allowed
  2222. */
  2223. if (!cfq_dispatch_request(cfqd, cfqq))
  2224. return 0;
  2225. cfqq->slice_dispatch++;
  2226. cfq_clear_cfqq_must_dispatch(cfqq);
  2227. /*
  2228. * expire an async queue immediately if it has used up its slice. idle
  2229. * queue always expire after 1 dispatch round.
  2230. */
  2231. if (cfqd->busy_queues > 1 && ((!cfq_cfqq_sync(cfqq) &&
  2232. cfqq->slice_dispatch >= cfq_prio_to_maxrq(cfqd, cfqq)) ||
  2233. cfq_class_idle(cfqq))) {
  2234. cfqq->slice_end = jiffies + 1;
  2235. cfq_slice_expired(cfqd, 0);
  2236. }
  2237. cfq_log_cfqq(cfqd, cfqq, "dispatched a request");
  2238. return 1;
  2239. }
  2240. /*
  2241. * task holds one reference to the queue, dropped when task exits. each rq
  2242. * in-flight on this queue also holds a reference, dropped when rq is freed.
  2243. *
  2244. * Each cfq queue took a reference on the parent group. Drop it now.
  2245. * queue lock must be held here.
  2246. */
  2247. static void cfq_put_queue(struct cfq_queue *cfqq)
  2248. {
  2249. struct cfq_data *cfqd = cfqq->cfqd;
  2250. struct cfq_group *cfqg;
  2251. BUG_ON(cfqq->ref <= 0);
  2252. cfqq->ref--;
  2253. if (cfqq->ref)
  2254. return;
  2255. cfq_log_cfqq(cfqd, cfqq, "put_queue");
  2256. BUG_ON(rb_first(&cfqq->sort_list));
  2257. BUG_ON(cfqq->allocated[READ] + cfqq->allocated[WRITE]);
  2258. cfqg = cfqq->cfqg;
  2259. if (unlikely(cfqd->active_queue == cfqq)) {
  2260. __cfq_slice_expired(cfqd, cfqq, 0);
  2261. cfq_schedule_dispatch(cfqd);
  2262. }
  2263. BUG_ON(cfq_cfqq_on_rr(cfqq));
  2264. kmem_cache_free(cfq_pool, cfqq);
  2265. cfq_put_cfqg(cfqg);
  2266. }
  2267. static void cfq_put_cooperator(struct cfq_queue *cfqq)
  2268. {
  2269. struct cfq_queue *__cfqq, *next;
  2270. /*
  2271. * If this queue was scheduled to merge with another queue, be
  2272. * sure to drop the reference taken on that queue (and others in
  2273. * the merge chain). See cfq_setup_merge and cfq_merge_cfqqs.
  2274. */
  2275. __cfqq = cfqq->new_cfqq;
  2276. while (__cfqq) {
  2277. if (__cfqq == cfqq) {
  2278. WARN(1, "cfqq->new_cfqq loop detected\n");
  2279. break;
  2280. }
  2281. next = __cfqq->new_cfqq;
  2282. cfq_put_queue(__cfqq);
  2283. __cfqq = next;
  2284. }
  2285. }
  2286. static void cfq_exit_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  2287. {
  2288. if (unlikely(cfqq == cfqd->active_queue)) {
  2289. __cfq_slice_expired(cfqd, cfqq, 0);
  2290. cfq_schedule_dispatch(cfqd);
  2291. }
  2292. cfq_put_cooperator(cfqq);
  2293. cfq_put_queue(cfqq);
  2294. }
  2295. static void cfq_init_icq(struct io_cq *icq)
  2296. {
  2297. struct cfq_io_cq *cic = icq_to_cic(icq);
  2298. cic->ttime.last_end_request = jiffies;
  2299. }
  2300. static void cfq_exit_icq(struct io_cq *icq)
  2301. {
  2302. struct cfq_io_cq *cic = icq_to_cic(icq);
  2303. struct cfq_data *cfqd = cic_to_cfqd(cic);
  2304. if (cic->cfqq[BLK_RW_ASYNC]) {
  2305. cfq_exit_cfqq(cfqd, cic->cfqq[BLK_RW_ASYNC]);
  2306. cic->cfqq[BLK_RW_ASYNC] = NULL;
  2307. }
  2308. if (cic->cfqq[BLK_RW_SYNC]) {
  2309. cfq_exit_cfqq(cfqd, cic->cfqq[BLK_RW_SYNC]);
  2310. cic->cfqq[BLK_RW_SYNC] = NULL;
  2311. }
  2312. }
  2313. static void cfq_init_prio_data(struct cfq_queue *cfqq, struct io_context *ioc)
  2314. {
  2315. struct task_struct *tsk = current;
  2316. int ioprio_class;
  2317. if (!cfq_cfqq_prio_changed(cfqq))
  2318. return;
  2319. ioprio_class = IOPRIO_PRIO_CLASS(ioc->ioprio);
  2320. switch (ioprio_class) {
  2321. default:
  2322. printk(KERN_ERR "cfq: bad prio %x\n", ioprio_class);
  2323. case IOPRIO_CLASS_NONE:
  2324. /*
  2325. * no prio set, inherit CPU scheduling settings
  2326. */
  2327. cfqq->ioprio = task_nice_ioprio(tsk);
  2328. cfqq->ioprio_class = task_nice_ioclass(tsk);
  2329. break;
  2330. case IOPRIO_CLASS_RT:
  2331. cfqq->ioprio = task_ioprio(ioc);
  2332. cfqq->ioprio_class = IOPRIO_CLASS_RT;
  2333. break;
  2334. case IOPRIO_CLASS_BE:
  2335. cfqq->ioprio = task_ioprio(ioc);
  2336. cfqq->ioprio_class = IOPRIO_CLASS_BE;
  2337. break;
  2338. case IOPRIO_CLASS_IDLE:
  2339. cfqq->ioprio_class = IOPRIO_CLASS_IDLE;
  2340. cfqq->ioprio = 7;
  2341. cfq_clear_cfqq_idle_window(cfqq);
  2342. break;
  2343. }
  2344. /*
  2345. * keep track of original prio settings in case we have to temporarily
  2346. * elevate the priority of this queue
  2347. */
  2348. cfqq->org_ioprio = cfqq->ioprio;
  2349. cfq_clear_cfqq_prio_changed(cfqq);
  2350. }
  2351. static void changed_ioprio(struct cfq_io_cq *cic)
  2352. {
  2353. struct cfq_data *cfqd = cic_to_cfqd(cic);
  2354. struct cfq_queue *cfqq;
  2355. if (unlikely(!cfqd))
  2356. return;
  2357. cfqq = cic->cfqq[BLK_RW_ASYNC];
  2358. if (cfqq) {
  2359. struct cfq_queue *new_cfqq;
  2360. new_cfqq = cfq_get_queue(cfqd, BLK_RW_ASYNC, cic->icq.ioc,
  2361. GFP_ATOMIC);
  2362. if (new_cfqq) {
  2363. cic->cfqq[BLK_RW_ASYNC] = new_cfqq;
  2364. cfq_put_queue(cfqq);
  2365. }
  2366. }
  2367. cfqq = cic->cfqq[BLK_RW_SYNC];
  2368. if (cfqq)
  2369. cfq_mark_cfqq_prio_changed(cfqq);
  2370. }
  2371. static void cfq_init_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
  2372. pid_t pid, bool is_sync)
  2373. {
  2374. RB_CLEAR_NODE(&cfqq->rb_node);
  2375. RB_CLEAR_NODE(&cfqq->p_node);
  2376. INIT_LIST_HEAD(&cfqq->fifo);
  2377. cfqq->ref = 0;
  2378. cfqq->cfqd = cfqd;
  2379. cfq_mark_cfqq_prio_changed(cfqq);
  2380. if (is_sync) {
  2381. if (!cfq_class_idle(cfqq))
  2382. cfq_mark_cfqq_idle_window(cfqq);
  2383. cfq_mark_cfqq_sync(cfqq);
  2384. }
  2385. cfqq->pid = pid;
  2386. }
  2387. #ifdef CONFIG_CFQ_GROUP_IOSCHED
  2388. static void changed_cgroup(struct cfq_io_cq *cic)
  2389. {
  2390. struct cfq_queue *sync_cfqq = cic_to_cfqq(cic, 1);
  2391. struct cfq_data *cfqd = cic_to_cfqd(cic);
  2392. struct request_queue *q;
  2393. if (unlikely(!cfqd))
  2394. return;
  2395. q = cfqd->queue;
  2396. if (sync_cfqq) {
  2397. /*
  2398. * Drop reference to sync queue. A new sync queue will be
  2399. * assigned in new group upon arrival of a fresh request.
  2400. */
  2401. cfq_log_cfqq(cfqd, sync_cfqq, "changed cgroup");
  2402. cic_set_cfqq(cic, NULL, 1);
  2403. cfq_put_queue(sync_cfqq);
  2404. }
  2405. }
  2406. #endif /* CONFIG_CFQ_GROUP_IOSCHED */
  2407. static struct cfq_queue *
  2408. cfq_find_alloc_queue(struct cfq_data *cfqd, bool is_sync,
  2409. struct io_context *ioc, gfp_t gfp_mask)
  2410. {
  2411. struct cfq_queue *cfqq, *new_cfqq = NULL;
  2412. struct cfq_io_cq *cic;
  2413. struct cfq_group *cfqg;
  2414. retry:
  2415. cfqg = cfq_get_cfqg(cfqd);
  2416. cic = cfq_cic_lookup(cfqd, ioc);
  2417. /* cic always exists here */
  2418. cfqq = cic_to_cfqq(cic, is_sync);
  2419. /*
  2420. * Always try a new alloc if we fell back to the OOM cfqq
  2421. * originally, since it should just be a temporary situation.
  2422. */
  2423. if (!cfqq || cfqq == &cfqd->oom_cfqq) {
  2424. cfqq = NULL;
  2425. if (new_cfqq) {
  2426. cfqq = new_cfqq;
  2427. new_cfqq = NULL;
  2428. } else if (gfp_mask & __GFP_WAIT) {
  2429. spin_unlock_irq(cfqd->queue->queue_lock);
  2430. new_cfqq = kmem_cache_alloc_node(cfq_pool,
  2431. gfp_mask | __GFP_ZERO,
  2432. cfqd->queue->node);
  2433. spin_lock_irq(cfqd->queue->queue_lock);
  2434. if (new_cfqq)
  2435. goto retry;
  2436. } else {
  2437. cfqq = kmem_cache_alloc_node(cfq_pool,
  2438. gfp_mask | __GFP_ZERO,
  2439. cfqd->queue->node);
  2440. }
  2441. if (cfqq) {
  2442. cfq_init_cfqq(cfqd, cfqq, current->pid, is_sync);
  2443. cfq_init_prio_data(cfqq, ioc);
  2444. cfq_link_cfqq_cfqg(cfqq, cfqg);
  2445. cfq_log_cfqq(cfqd, cfqq, "alloced");
  2446. } else
  2447. cfqq = &cfqd->oom_cfqq;
  2448. }
  2449. if (new_cfqq)
  2450. kmem_cache_free(cfq_pool, new_cfqq);
  2451. return cfqq;
  2452. }
  2453. static struct cfq_queue **
  2454. cfq_async_queue_prio(struct cfq_data *cfqd, int ioprio_class, int ioprio)
  2455. {
  2456. switch (ioprio_class) {
  2457. case IOPRIO_CLASS_RT:
  2458. return &cfqd->async_cfqq[0][ioprio];
  2459. case IOPRIO_CLASS_BE:
  2460. return &cfqd->async_cfqq[1][ioprio];
  2461. case IOPRIO_CLASS_IDLE:
  2462. return &cfqd->async_idle_cfqq;
  2463. default:
  2464. BUG();
  2465. }
  2466. }
  2467. static struct cfq_queue *
  2468. cfq_get_queue(struct cfq_data *cfqd, bool is_sync, struct io_context *ioc,
  2469. gfp_t gfp_mask)
  2470. {
  2471. const int ioprio = task_ioprio(ioc);
  2472. const int ioprio_class = task_ioprio_class(ioc);
  2473. struct cfq_queue **async_cfqq = NULL;
  2474. struct cfq_queue *cfqq = NULL;
  2475. if (!is_sync) {
  2476. async_cfqq = cfq_async_queue_prio(cfqd, ioprio_class, ioprio);
  2477. cfqq = *async_cfqq;
  2478. }
  2479. if (!cfqq)
  2480. cfqq = cfq_find_alloc_queue(cfqd, is_sync, ioc, gfp_mask);
  2481. /*
  2482. * pin the queue now that it's allocated, scheduler exit will prune it
  2483. */
  2484. if (!is_sync && !(*async_cfqq)) {
  2485. cfqq->ref++;
  2486. *async_cfqq = cfqq;
  2487. }
  2488. cfqq->ref++;
  2489. return cfqq;
  2490. }
  2491. static void
  2492. __cfq_update_io_thinktime(struct cfq_ttime *ttime, unsigned long slice_idle)
  2493. {
  2494. unsigned long elapsed = jiffies - ttime->last_end_request;
  2495. elapsed = min(elapsed, 2UL * slice_idle);
  2496. ttime->ttime_samples = (7*ttime->ttime_samples + 256) / 8;
  2497. ttime->ttime_total = (7*ttime->ttime_total + 256*elapsed) / 8;
  2498. ttime->ttime_mean = (ttime->ttime_total + 128) / ttime->ttime_samples;
  2499. }
  2500. static void
  2501. cfq_update_io_thinktime(struct cfq_data *cfqd, struct cfq_queue *cfqq,
  2502. struct cfq_io_cq *cic)
  2503. {
  2504. if (cfq_cfqq_sync(cfqq)) {
  2505. __cfq_update_io_thinktime(&cic->ttime, cfqd->cfq_slice_idle);
  2506. __cfq_update_io_thinktime(&cfqq->service_tree->ttime,
  2507. cfqd->cfq_slice_idle);
  2508. }
  2509. #ifdef CONFIG_CFQ_GROUP_IOSCHED
  2510. __cfq_update_io_thinktime(&cfqq->cfqg->ttime, cfqd->cfq_group_idle);
  2511. #endif
  2512. }
  2513. static void
  2514. cfq_update_io_seektime(struct cfq_data *cfqd, struct cfq_queue *cfqq,
  2515. struct request *rq)
  2516. {
  2517. sector_t sdist = 0;
  2518. sector_t n_sec = blk_rq_sectors(rq);
  2519. if (cfqq->last_request_pos) {
  2520. if (cfqq->last_request_pos < blk_rq_pos(rq))
  2521. sdist = blk_rq_pos(rq) - cfqq->last_request_pos;
  2522. else
  2523. sdist = cfqq->last_request_pos - blk_rq_pos(rq);
  2524. }
  2525. cfqq->seek_history <<= 1;
  2526. if (blk_queue_nonrot(cfqd->queue))
  2527. cfqq->seek_history |= (n_sec < CFQQ_SECT_THR_NONROT);
  2528. else
  2529. cfqq->seek_history |= (sdist > CFQQ_SEEK_THR);
  2530. }
  2531. /*
  2532. * Disable idle window if the process thinks too long or seeks so much that
  2533. * it doesn't matter
  2534. */
  2535. static void
  2536. cfq_update_idle_window(struct cfq_data *cfqd, struct cfq_queue *cfqq,
  2537. struct cfq_io_cq *cic)
  2538. {
  2539. int old_idle, enable_idle;
  2540. /*
  2541. * Don't idle for async or idle io prio class
  2542. */
  2543. if (!cfq_cfqq_sync(cfqq) || cfq_class_idle(cfqq))
  2544. return;
  2545. enable_idle = old_idle = cfq_cfqq_idle_window(cfqq);
  2546. if (cfqq->queued[0] + cfqq->queued[1] >= 4)
  2547. cfq_mark_cfqq_deep(cfqq);
  2548. if (cfqq->next_rq && (cfqq->next_rq->cmd_flags & REQ_NOIDLE))
  2549. enable_idle = 0;
  2550. else if (!atomic_read(&cic->icq.ioc->nr_tasks) ||
  2551. !cfqd->cfq_slice_idle ||
  2552. (!cfq_cfqq_deep(cfqq) && CFQQ_SEEKY(cfqq)))
  2553. enable_idle = 0;
  2554. else if (sample_valid(cic->ttime.ttime_samples)) {
  2555. if (cic->ttime.ttime_mean > cfqd->cfq_slice_idle)
  2556. enable_idle = 0;
  2557. else
  2558. enable_idle = 1;
  2559. }
  2560. if (old_idle != enable_idle) {
  2561. cfq_log_cfqq(cfqd, cfqq, "idle=%d", enable_idle);
  2562. if (enable_idle)
  2563. cfq_mark_cfqq_idle_window(cfqq);
  2564. else
  2565. cfq_clear_cfqq_idle_window(cfqq);
  2566. }
  2567. }
  2568. /*
  2569. * Check if new_cfqq should preempt the currently active queue. Return 0 for
  2570. * no or if we aren't sure, a 1 will cause a preempt.
  2571. */
  2572. static bool
  2573. cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
  2574. struct request *rq)
  2575. {
  2576. struct cfq_queue *cfqq;
  2577. cfqq = cfqd->active_queue;
  2578. if (!cfqq)
  2579. return false;
  2580. if (cfq_class_idle(new_cfqq))
  2581. return false;
  2582. if (cfq_class_idle(cfqq))
  2583. return true;
  2584. /*
  2585. * Don't allow a non-RT request to preempt an ongoing RT cfqq timeslice.
  2586. */
  2587. if (cfq_class_rt(cfqq) && !cfq_class_rt(new_cfqq))
  2588. return false;
  2589. /*
  2590. * if the new request is sync, but the currently running queue is
  2591. * not, let the sync request have priority.
  2592. */
  2593. if (rq_is_sync(rq) && !cfq_cfqq_sync(cfqq))
  2594. return true;
  2595. if (new_cfqq->cfqg != cfqq->cfqg)
  2596. return false;
  2597. if (cfq_slice_used(cfqq))
  2598. return true;
  2599. /* Allow preemption only if we are idling on sync-noidle tree */
  2600. if (cfqd->serving_type == SYNC_NOIDLE_WORKLOAD &&
  2601. cfqq_type(new_cfqq) == SYNC_NOIDLE_WORKLOAD &&
  2602. new_cfqq->service_tree->count == 2 &&
  2603. RB_EMPTY_ROOT(&cfqq->sort_list))
  2604. return true;
  2605. /*
  2606. * So both queues are sync. Let the new request get disk time if
  2607. * it's a metadata request and the current queue is doing regular IO.
  2608. */
  2609. if ((rq->cmd_flags & REQ_PRIO) && !cfqq->prio_pending)
  2610. return true;
  2611. /*
  2612. * Allow an RT request to pre-empt an ongoing non-RT cfqq timeslice.
  2613. */
  2614. if (cfq_class_rt(new_cfqq) && !cfq_class_rt(cfqq))
  2615. return true;
  2616. /* An idle queue should not be idle now for some reason */
  2617. if (RB_EMPTY_ROOT(&cfqq->sort_list) && !cfq_should_idle(cfqd, cfqq))
  2618. return true;
  2619. if (!cfqd->active_cic || !cfq_cfqq_wait_request(cfqq))
  2620. return false;
  2621. /*
  2622. * if this request is as-good as one we would expect from the
  2623. * current cfqq, let it preempt
  2624. */
  2625. if (cfq_rq_close(cfqd, cfqq, rq))
  2626. return true;
  2627. return false;
  2628. }
  2629. /*
  2630. * cfqq preempts the active queue. if we allowed preempt with no slice left,
  2631. * let it have half of its nominal slice.
  2632. */
  2633. static void cfq_preempt_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  2634. {
  2635. enum wl_type_t old_type = cfqq_type(cfqd->active_queue);
  2636. cfq_log_cfqq(cfqd, cfqq, "preempt");
  2637. cfq_slice_expired(cfqd, 1);
  2638. /*
  2639. * workload type is changed, don't save slice, otherwise preempt
  2640. * doesn't happen
  2641. */
  2642. if (old_type != cfqq_type(cfqq))
  2643. cfqq->cfqg->saved_workload_slice = 0;
  2644. /*
  2645. * Put the new queue at the front of the of the current list,
  2646. * so we know that it will be selected next.
  2647. */
  2648. BUG_ON(!cfq_cfqq_on_rr(cfqq));
  2649. cfq_service_tree_add(cfqd, cfqq, 1);
  2650. cfqq->slice_end = 0;
  2651. cfq_mark_cfqq_slice_new(cfqq);
  2652. }
  2653. /*
  2654. * Called when a new fs request (rq) is added (to cfqq). Check if there's
  2655. * something we should do about it
  2656. */
  2657. static void
  2658. cfq_rq_enqueued(struct cfq_data *cfqd, struct cfq_queue *cfqq,
  2659. struct request *rq)
  2660. {
  2661. struct cfq_io_cq *cic = RQ_CIC(rq);
  2662. cfqd->rq_queued++;
  2663. if (rq->cmd_flags & REQ_PRIO)
  2664. cfqq->prio_pending++;
  2665. cfq_update_io_thinktime(cfqd, cfqq, cic);
  2666. cfq_update_io_seektime(cfqd, cfqq, rq);
  2667. cfq_update_idle_window(cfqd, cfqq, cic);
  2668. cfqq->last_request_pos = blk_rq_pos(rq) + blk_rq_sectors(rq);
  2669. if (cfqq == cfqd->active_queue) {
  2670. /*
  2671. * Remember that we saw a request from this process, but
  2672. * don't start queuing just yet. Otherwise we risk seeing lots
  2673. * of tiny requests, because we disrupt the normal plugging
  2674. * and merging. If the request is already larger than a single
  2675. * page, let it rip immediately. For that case we assume that
  2676. * merging is already done. Ditto for a busy system that
  2677. * has other work pending, don't risk delaying until the
  2678. * idle timer unplug to continue working.
  2679. */
  2680. if (cfq_cfqq_wait_request(cfqq)) {
  2681. if (blk_rq_bytes(rq) > PAGE_CACHE_SIZE ||
  2682. cfqd->busy_queues > 1) {
  2683. cfq_del_timer(cfqd, cfqq);
  2684. cfq_clear_cfqq_wait_request(cfqq);
  2685. __blk_run_queue(cfqd->queue);
  2686. } else {
  2687. cfq_blkiocg_update_idle_time_stats(
  2688. &cfqq->cfqg->blkg);
  2689. cfq_mark_cfqq_must_dispatch(cfqq);
  2690. }
  2691. }
  2692. } else if (cfq_should_preempt(cfqd, cfqq, rq)) {
  2693. /*
  2694. * not the active queue - expire current slice if it is
  2695. * idle and has expired it's mean thinktime or this new queue
  2696. * has some old slice time left and is of higher priority or
  2697. * this new queue is RT and the current one is BE
  2698. */
  2699. cfq_preempt_queue(cfqd, cfqq);
  2700. __blk_run_queue(cfqd->queue);
  2701. }
  2702. }
  2703. static void cfq_insert_request(struct request_queue *q, struct request *rq)
  2704. {
  2705. struct cfq_data *cfqd = q->elevator->elevator_data;
  2706. struct cfq_queue *cfqq = RQ_CFQQ(rq);
  2707. cfq_log_cfqq(cfqd, cfqq, "insert_request");
  2708. cfq_init_prio_data(cfqq, RQ_CIC(rq)->icq.ioc);
  2709. rq_set_fifo_time(rq, jiffies + cfqd->cfq_fifo_expire[rq_is_sync(rq)]);
  2710. list_add_tail(&rq->queuelist, &cfqq->fifo);
  2711. cfq_add_rq_rb(rq);
  2712. cfq_blkiocg_update_io_add_stats(&(RQ_CFQG(rq))->blkg,
  2713. &cfqd->serving_group->blkg, rq_data_dir(rq),
  2714. rq_is_sync(rq));
  2715. cfq_rq_enqueued(cfqd, cfqq, rq);
  2716. }
  2717. /*
  2718. * Update hw_tag based on peak queue depth over 50 samples under
  2719. * sufficient load.
  2720. */
  2721. static void cfq_update_hw_tag(struct cfq_data *cfqd)
  2722. {
  2723. struct cfq_queue *cfqq = cfqd->active_queue;
  2724. if (cfqd->rq_in_driver > cfqd->hw_tag_est_depth)
  2725. cfqd->hw_tag_est_depth = cfqd->rq_in_driver;
  2726. if (cfqd->hw_tag == 1)
  2727. return;
  2728. if (cfqd->rq_queued <= CFQ_HW_QUEUE_MIN &&
  2729. cfqd->rq_in_driver <= CFQ_HW_QUEUE_MIN)
  2730. return;
  2731. /*
  2732. * If active queue hasn't enough requests and can idle, cfq might not
  2733. * dispatch sufficient requests to hardware. Don't zero hw_tag in this
  2734. * case
  2735. */
  2736. if (cfqq && cfq_cfqq_idle_window(cfqq) &&
  2737. cfqq->dispatched + cfqq->queued[0] + cfqq->queued[1] <
  2738. CFQ_HW_QUEUE_MIN && cfqd->rq_in_driver < CFQ_HW_QUEUE_MIN)
  2739. return;
  2740. if (cfqd->hw_tag_samples++ < 50)
  2741. return;
  2742. if (cfqd->hw_tag_est_depth >= CFQ_HW_QUEUE_MIN)
  2743. cfqd->hw_tag = 1;
  2744. else
  2745. cfqd->hw_tag = 0;
  2746. }
  2747. static bool cfq_should_wait_busy(struct cfq_data *cfqd, struct cfq_queue *cfqq)
  2748. {
  2749. struct cfq_io_cq *cic = cfqd->active_cic;
  2750. /* If the queue already has requests, don't wait */
  2751. if (!RB_EMPTY_ROOT(&cfqq->sort_list))
  2752. return false;
  2753. /* If there are other queues in the group, don't wait */
  2754. if (cfqq->cfqg->nr_cfqq > 1)
  2755. return false;
  2756. /* the only queue in the group, but think time is big */
  2757. if (cfq_io_thinktime_big(cfqd, &cfqq->cfqg->ttime, true))
  2758. return false;
  2759. if (cfq_slice_used(cfqq))
  2760. return true;
  2761. /* if slice left is less than think time, wait busy */
  2762. if (cic && sample_valid(cic->ttime.ttime_samples)
  2763. && (cfqq->slice_end - jiffies < cic->ttime.ttime_mean))
  2764. return true;
  2765. /*
  2766. * If think times is less than a jiffy than ttime_mean=0 and above
  2767. * will not be true. It might happen that slice has not expired yet
  2768. * but will expire soon (4-5 ns) during select_queue(). To cover the
  2769. * case where think time is less than a jiffy, mark the queue wait
  2770. * busy if only 1 jiffy is left in the slice.
  2771. */
  2772. if (cfqq->slice_end - jiffies == 1)
  2773. return true;
  2774. return false;
  2775. }
  2776. static void cfq_completed_request(struct request_queue *q, struct request *rq)
  2777. {
  2778. struct cfq_queue *cfqq = RQ_CFQQ(rq);
  2779. struct cfq_data *cfqd = cfqq->cfqd;
  2780. const int sync = rq_is_sync(rq);
  2781. unsigned long now;
  2782. now = jiffies;
  2783. cfq_log_cfqq(cfqd, cfqq, "complete rqnoidle %d",
  2784. !!(rq->cmd_flags & REQ_NOIDLE));
  2785. cfq_update_hw_tag(cfqd);
  2786. WARN_ON(!cfqd->rq_in_driver);
  2787. WARN_ON(!cfqq->dispatched);
  2788. cfqd->rq_in_driver--;
  2789. cfqq->dispatched--;
  2790. (RQ_CFQG(rq))->dispatched--;
  2791. cfq_blkiocg_update_completion_stats(&cfqq->cfqg->blkg,
  2792. rq_start_time_ns(rq), rq_io_start_time_ns(rq),
  2793. rq_data_dir(rq), rq_is_sync(rq));
  2794. cfqd->rq_in_flight[cfq_cfqq_sync(cfqq)]--;
  2795. if (sync) {
  2796. struct cfq_rb_root *service_tree;
  2797. RQ_CIC(rq)->ttime.last_end_request = now;
  2798. if (cfq_cfqq_on_rr(cfqq))
  2799. service_tree = cfqq->service_tree;
  2800. else
  2801. service_tree = service_tree_for(cfqq->cfqg,
  2802. cfqq_prio(cfqq), cfqq_type(cfqq));
  2803. service_tree->ttime.last_end_request = now;
  2804. if (!time_after(rq->start_time + cfqd->cfq_fifo_expire[1], now))
  2805. cfqd->last_delayed_sync = now;
  2806. }
  2807. #ifdef CONFIG_CFQ_GROUP_IOSCHED
  2808. cfqq->cfqg->ttime.last_end_request = now;
  2809. #endif
  2810. /*
  2811. * If this is the active queue, check if it needs to be expired,
  2812. * or if we want to idle in case it has no pending requests.
  2813. */
  2814. if (cfqd->active_queue == cfqq) {
  2815. const bool cfqq_empty = RB_EMPTY_ROOT(&cfqq->sort_list);
  2816. if (cfq_cfqq_slice_new(cfqq)) {
  2817. cfq_set_prio_slice(cfqd, cfqq);
  2818. cfq_clear_cfqq_slice_new(cfqq);
  2819. }
  2820. /*
  2821. * Should we wait for next request to come in before we expire
  2822. * the queue.
  2823. */
  2824. if (cfq_should_wait_busy(cfqd, cfqq)) {
  2825. unsigned long extend_sl = cfqd->cfq_slice_idle;
  2826. if (!cfqd->cfq_slice_idle)
  2827. extend_sl = cfqd->cfq_group_idle;
  2828. cfqq->slice_end = jiffies + extend_sl;
  2829. cfq_mark_cfqq_wait_busy(cfqq);
  2830. cfq_log_cfqq(cfqd, cfqq, "will busy wait");
  2831. }
  2832. /*
  2833. * Idling is not enabled on:
  2834. * - expired queues
  2835. * - idle-priority queues
  2836. * - async queues
  2837. * - queues with still some requests queued
  2838. * - when there is a close cooperator
  2839. */
  2840. if (cfq_slice_used(cfqq) || cfq_class_idle(cfqq))
  2841. cfq_slice_expired(cfqd, 1);
  2842. else if (sync && cfqq_empty &&
  2843. !cfq_close_cooperator(cfqd, cfqq)) {
  2844. cfq_arm_slice_timer(cfqd);
  2845. }
  2846. }
  2847. if (!cfqd->rq_in_driver)
  2848. cfq_schedule_dispatch(cfqd);
  2849. }
  2850. static inline int __cfq_may_queue(struct cfq_queue *cfqq)
  2851. {
  2852. if (cfq_cfqq_wait_request(cfqq) && !cfq_cfqq_must_alloc_slice(cfqq)) {
  2853. cfq_mark_cfqq_must_alloc_slice(cfqq);
  2854. return ELV_MQUEUE_MUST;
  2855. }
  2856. return ELV_MQUEUE_MAY;
  2857. }
  2858. static int cfq_may_queue(struct request_queue *q, int rw)
  2859. {
  2860. struct cfq_data *cfqd = q->elevator->elevator_data;
  2861. struct task_struct *tsk = current;
  2862. struct cfq_io_cq *cic;
  2863. struct cfq_queue *cfqq;
  2864. /*
  2865. * don't force setup of a queue from here, as a call to may_queue
  2866. * does not necessarily imply that a request actually will be queued.
  2867. * so just lookup a possibly existing queue, or return 'may queue'
  2868. * if that fails
  2869. */
  2870. cic = cfq_cic_lookup(cfqd, tsk->io_context);
  2871. if (!cic)
  2872. return ELV_MQUEUE_MAY;
  2873. cfqq = cic_to_cfqq(cic, rw_is_sync(rw));
  2874. if (cfqq) {
  2875. cfq_init_prio_data(cfqq, cic->icq.ioc);
  2876. return __cfq_may_queue(cfqq);
  2877. }
  2878. return ELV_MQUEUE_MAY;
  2879. }
  2880. /*
  2881. * queue lock held here
  2882. */
  2883. static void cfq_put_request(struct request *rq)
  2884. {
  2885. struct cfq_queue *cfqq = RQ_CFQQ(rq);
  2886. if (cfqq) {
  2887. const int rw = rq_data_dir(rq);
  2888. BUG_ON(!cfqq->allocated[rw]);
  2889. cfqq->allocated[rw]--;
  2890. /* Put down rq reference on cfqg */
  2891. cfq_put_cfqg(RQ_CFQG(rq));
  2892. rq->elv.priv[0] = NULL;
  2893. rq->elv.priv[1] = NULL;
  2894. cfq_put_queue(cfqq);
  2895. }
  2896. }
  2897. static struct cfq_queue *
  2898. cfq_merge_cfqqs(struct cfq_data *cfqd, struct cfq_io_cq *cic,
  2899. struct cfq_queue *cfqq)
  2900. {
  2901. cfq_log_cfqq(cfqd, cfqq, "merging with queue %p", cfqq->new_cfqq);
  2902. cic_set_cfqq(cic, cfqq->new_cfqq, 1);
  2903. cfq_mark_cfqq_coop(cfqq->new_cfqq);
  2904. cfq_put_queue(cfqq);
  2905. return cic_to_cfqq(cic, 1);
  2906. }
  2907. /*
  2908. * Returns NULL if a new cfqq should be allocated, or the old cfqq if this
  2909. * was the last process referring to said cfqq.
  2910. */
  2911. static struct cfq_queue *
  2912. split_cfqq(struct cfq_io_cq *cic, struct cfq_queue *cfqq)
  2913. {
  2914. if (cfqq_process_refs(cfqq) == 1) {
  2915. cfqq->pid = current->pid;
  2916. cfq_clear_cfqq_coop(cfqq);
  2917. cfq_clear_cfqq_split_coop(cfqq);
  2918. return cfqq;
  2919. }
  2920. cic_set_cfqq(cic, NULL, 1);
  2921. cfq_put_cooperator(cfqq);
  2922. cfq_put_queue(cfqq);
  2923. return NULL;
  2924. }
  2925. /*
  2926. * Allocate cfq data structures associated with this request.
  2927. */
  2928. static int
  2929. cfq_set_request(struct request_queue *q, struct request *rq, gfp_t gfp_mask)
  2930. {
  2931. struct cfq_data *cfqd = q->elevator->elevator_data;
  2932. struct cfq_io_cq *cic = icq_to_cic(rq->elv.icq);
  2933. const int rw = rq_data_dir(rq);
  2934. const bool is_sync = rq_is_sync(rq);
  2935. struct cfq_queue *cfqq;
  2936. unsigned int changed;
  2937. might_sleep_if(gfp_mask & __GFP_WAIT);
  2938. spin_lock_irq(q->queue_lock);
  2939. /* handle changed notifications */
  2940. changed = icq_get_changed(&cic->icq);
  2941. if (unlikely(changed & ICQ_IOPRIO_CHANGED))
  2942. changed_ioprio(cic);
  2943. #ifdef CONFIG_CFQ_GROUP_IOSCHED
  2944. if (unlikely(changed & ICQ_CGROUP_CHANGED))
  2945. changed_cgroup(cic);
  2946. #endif
  2947. new_queue:
  2948. cfqq = cic_to_cfqq(cic, is_sync);
  2949. if (!cfqq || cfqq == &cfqd->oom_cfqq) {
  2950. cfqq = cfq_get_queue(cfqd, is_sync, cic->icq.ioc, gfp_mask);
  2951. cic_set_cfqq(cic, cfqq, is_sync);
  2952. } else {
  2953. /*
  2954. * If the queue was seeky for too long, break it apart.
  2955. */
  2956. if (cfq_cfqq_coop(cfqq) && cfq_cfqq_split_coop(cfqq)) {
  2957. cfq_log_cfqq(cfqd, cfqq, "breaking apart cfqq");
  2958. cfqq = split_cfqq(cic, cfqq);
  2959. if (!cfqq)
  2960. goto new_queue;
  2961. }
  2962. /*
  2963. * Check to see if this queue is scheduled to merge with
  2964. * another, closely cooperating queue. The merging of
  2965. * queues happens here as it must be done in process context.
  2966. * The reference on new_cfqq was taken in merge_cfqqs.
  2967. */
  2968. if (cfqq->new_cfqq)
  2969. cfqq = cfq_merge_cfqqs(cfqd, cic, cfqq);
  2970. }
  2971. cfqq->allocated[rw]++;
  2972. cfqq->ref++;
  2973. rq->elv.priv[0] = cfqq;
  2974. rq->elv.priv[1] = cfq_ref_get_cfqg(cfqq->cfqg);
  2975. spin_unlock_irq(q->queue_lock);
  2976. return 0;
  2977. }
  2978. static void cfq_kick_queue(struct work_struct *work)
  2979. {
  2980. struct cfq_data *cfqd =
  2981. container_of(work, struct cfq_data, unplug_work);
  2982. struct request_queue *q = cfqd->queue;
  2983. spin_lock_irq(q->queue_lock);
  2984. __blk_run_queue(cfqd->queue);
  2985. spin_unlock_irq(q->queue_lock);
  2986. }
  2987. /*
  2988. * Timer running if the active_queue is currently idling inside its time slice
  2989. */
  2990. static void cfq_idle_slice_timer(unsigned long data)
  2991. {
  2992. struct cfq_data *cfqd = (struct cfq_data *) data;
  2993. struct cfq_queue *cfqq;
  2994. unsigned long flags;
  2995. int timed_out = 1;
  2996. cfq_log(cfqd, "idle timer fired");
  2997. spin_lock_irqsave(cfqd->queue->queue_lock, flags);
  2998. cfqq = cfqd->active_queue;
  2999. if (cfqq) {
  3000. timed_out = 0;
  3001. /*
  3002. * We saw a request before the queue expired, let it through
  3003. */
  3004. if (cfq_cfqq_must_dispatch(cfqq))
  3005. goto out_kick;
  3006. /*
  3007. * expired
  3008. */
  3009. if (cfq_slice_used(cfqq))
  3010. goto expire;
  3011. /*
  3012. * only expire and reinvoke request handler, if there are
  3013. * other queues with pending requests
  3014. */
  3015. if (!cfqd->busy_queues)
  3016. goto out_cont;
  3017. /*
  3018. * not expired and it has a request pending, let it dispatch
  3019. */
  3020. if (!RB_EMPTY_ROOT(&cfqq->sort_list))
  3021. goto out_kick;
  3022. /*
  3023. * Queue depth flag is reset only when the idle didn't succeed
  3024. */
  3025. cfq_clear_cfqq_deep(cfqq);
  3026. }
  3027. expire:
  3028. cfq_slice_expired(cfqd, timed_out);
  3029. out_kick:
  3030. cfq_schedule_dispatch(cfqd);
  3031. out_cont:
  3032. spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
  3033. }
  3034. static void cfq_shutdown_timer_wq(struct cfq_data *cfqd)
  3035. {
  3036. del_timer_sync(&cfqd->idle_slice_timer);
  3037. cancel_work_sync(&cfqd->unplug_work);
  3038. }
  3039. static void cfq_put_async_queues(struct cfq_data *cfqd)
  3040. {
  3041. int i;
  3042. for (i = 0; i < IOPRIO_BE_NR; i++) {
  3043. if (cfqd->async_cfqq[0][i])
  3044. cfq_put_queue(cfqd->async_cfqq[0][i]);
  3045. if (cfqd->async_cfqq[1][i])
  3046. cfq_put_queue(cfqd->async_cfqq[1][i]);
  3047. }
  3048. if (cfqd->async_idle_cfqq)
  3049. cfq_put_queue(cfqd->async_idle_cfqq);
  3050. }
  3051. static void cfq_exit_queue(struct elevator_queue *e)
  3052. {
  3053. struct cfq_data *cfqd = e->elevator_data;
  3054. struct request_queue *q = cfqd->queue;
  3055. bool wait = false;
  3056. cfq_shutdown_timer_wq(cfqd);
  3057. spin_lock_irq(q->queue_lock);
  3058. if (cfqd->active_queue)
  3059. __cfq_slice_expired(cfqd, cfqd->active_queue, 0);
  3060. cfq_put_async_queues(cfqd);
  3061. cfq_release_cfq_groups(cfqd);
  3062. /*
  3063. * If there are groups which we could not unlink from blkcg list,
  3064. * wait for a rcu period for them to be freed.
  3065. */
  3066. if (cfqd->nr_blkcg_linked_grps)
  3067. wait = true;
  3068. spin_unlock_irq(q->queue_lock);
  3069. cfq_shutdown_timer_wq(cfqd);
  3070. /*
  3071. * Wait for cfqg->blkg->key accessors to exit their grace periods.
  3072. * Do this wait only if there are other unlinked groups out
  3073. * there. This can happen if cgroup deletion path claimed the
  3074. * responsibility of cleaning up a group before queue cleanup code
  3075. * get to the group.
  3076. *
  3077. * Do not call synchronize_rcu() unconditionally as there are drivers
  3078. * which create/delete request queue hundreds of times during scan/boot
  3079. * and synchronize_rcu() can take significant time and slow down boot.
  3080. */
  3081. if (wait)
  3082. synchronize_rcu();
  3083. #ifdef CONFIG_CFQ_GROUP_IOSCHED
  3084. /* Free up per cpu stats for root group */
  3085. free_percpu(cfqd->root_group.blkg.stats_cpu);
  3086. #endif
  3087. kfree(cfqd);
  3088. }
  3089. static void *cfq_init_queue(struct request_queue *q)
  3090. {
  3091. struct cfq_data *cfqd;
  3092. int i, j;
  3093. struct cfq_group *cfqg;
  3094. struct cfq_rb_root *st;
  3095. cfqd = kmalloc_node(sizeof(*cfqd), GFP_KERNEL | __GFP_ZERO, q->node);
  3096. if (!cfqd)
  3097. return NULL;
  3098. /* Init root service tree */
  3099. cfqd->grp_service_tree = CFQ_RB_ROOT;
  3100. /* Init root group */
  3101. cfqg = &cfqd->root_group;
  3102. for_each_cfqg_st(cfqg, i, j, st)
  3103. *st = CFQ_RB_ROOT;
  3104. RB_CLEAR_NODE(&cfqg->rb_node);
  3105. /* Give preference to root group over other groups */
  3106. cfqg->weight = 2*BLKIO_WEIGHT_DEFAULT;
  3107. #ifdef CONFIG_CFQ_GROUP_IOSCHED
  3108. /*
  3109. * Set root group reference to 2. One reference will be dropped when
  3110. * all groups on cfqd->cfqg_list are being deleted during queue exit.
  3111. * Other reference will remain there as we don't want to delete this
  3112. * group as it is statically allocated and gets destroyed when
  3113. * throtl_data goes away.
  3114. */
  3115. cfqg->ref = 2;
  3116. if (blkio_alloc_blkg_stats(&cfqg->blkg)) {
  3117. kfree(cfqg);
  3118. kfree(cfqd);
  3119. return NULL;
  3120. }
  3121. rcu_read_lock();
  3122. cfq_blkiocg_add_blkio_group(&blkio_root_cgroup, &cfqg->blkg,
  3123. (void *)cfqd, 0);
  3124. rcu_read_unlock();
  3125. cfqd->nr_blkcg_linked_grps++;
  3126. /* Add group on cfqd->cfqg_list */
  3127. hlist_add_head(&cfqg->cfqd_node, &cfqd->cfqg_list);
  3128. #endif
  3129. /*
  3130. * Not strictly needed (since RB_ROOT just clears the node and we
  3131. * zeroed cfqd on alloc), but better be safe in case someone decides
  3132. * to add magic to the rb code
  3133. */
  3134. for (i = 0; i < CFQ_PRIO_LISTS; i++)
  3135. cfqd->prio_trees[i] = RB_ROOT;
  3136. /*
  3137. * Our fallback cfqq if cfq_find_alloc_queue() runs into OOM issues.
  3138. * Grab a permanent reference to it, so that the normal code flow
  3139. * will not attempt to free it.
  3140. */
  3141. cfq_init_cfqq(cfqd, &cfqd->oom_cfqq, 1, 0);
  3142. cfqd->oom_cfqq.ref++;
  3143. cfq_link_cfqq_cfqg(&cfqd->oom_cfqq, &cfqd->root_group);
  3144. cfqd->queue = q;
  3145. init_timer(&cfqd->idle_slice_timer);
  3146. cfqd->idle_slice_timer.function = cfq_idle_slice_timer;
  3147. cfqd->idle_slice_timer.data = (unsigned long) cfqd;
  3148. INIT_WORK(&cfqd->unplug_work, cfq_kick_queue);
  3149. cfqd->cfq_quantum = cfq_quantum;
  3150. cfqd->cfq_fifo_expire[0] = cfq_fifo_expire[0];
  3151. cfqd->cfq_fifo_expire[1] = cfq_fifo_expire[1];
  3152. cfqd->cfq_back_max = cfq_back_max;
  3153. cfqd->cfq_back_penalty = cfq_back_penalty;
  3154. cfqd->cfq_slice[0] = cfq_slice_async;
  3155. cfqd->cfq_slice[1] = cfq_slice_sync;
  3156. cfqd->cfq_slice_async_rq = cfq_slice_async_rq;
  3157. cfqd->cfq_slice_idle = cfq_slice_idle;
  3158. cfqd->cfq_group_idle = cfq_group_idle;
  3159. cfqd->cfq_latency = 1;
  3160. cfqd->hw_tag = -1;
  3161. /*
  3162. * we optimistically start assuming sync ops weren't delayed in last
  3163. * second, in order to have larger depth for async operations.
  3164. */
  3165. cfqd->last_delayed_sync = jiffies - HZ;
  3166. return cfqd;
  3167. }
  3168. /*
  3169. * sysfs parts below -->
  3170. */
  3171. static ssize_t
  3172. cfq_var_show(unsigned int var, char *page)
  3173. {
  3174. return sprintf(page, "%d\n", var);
  3175. }
  3176. static ssize_t
  3177. cfq_var_store(unsigned int *var, const char *page, size_t count)
  3178. {
  3179. char *p = (char *) page;
  3180. *var = simple_strtoul(p, &p, 10);
  3181. return count;
  3182. }
  3183. #define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \
  3184. static ssize_t __FUNC(struct elevator_queue *e, char *page) \
  3185. { \
  3186. struct cfq_data *cfqd = e->elevator_data; \
  3187. unsigned int __data = __VAR; \
  3188. if (__CONV) \
  3189. __data = jiffies_to_msecs(__data); \
  3190. return cfq_var_show(__data, (page)); \
  3191. }
  3192. SHOW_FUNCTION(cfq_quantum_show, cfqd->cfq_quantum, 0);
  3193. SHOW_FUNCTION(cfq_fifo_expire_sync_show, cfqd->cfq_fifo_expire[1], 1);
  3194. SHOW_FUNCTION(cfq_fifo_expire_async_show, cfqd->cfq_fifo_expire[0], 1);
  3195. SHOW_FUNCTION(cfq_back_seek_max_show, cfqd->cfq_back_max, 0);
  3196. SHOW_FUNCTION(cfq_back_seek_penalty_show, cfqd->cfq_back_penalty, 0);
  3197. SHOW_FUNCTION(cfq_slice_idle_show, cfqd->cfq_slice_idle, 1);
  3198. SHOW_FUNCTION(cfq_group_idle_show, cfqd->cfq_group_idle, 1);
  3199. SHOW_FUNCTION(cfq_slice_sync_show, cfqd->cfq_slice[1], 1);
  3200. SHOW_FUNCTION(cfq_slice_async_show, cfqd->cfq_slice[0], 1);
  3201. SHOW_FUNCTION(cfq_slice_async_rq_show, cfqd->cfq_slice_async_rq, 0);
  3202. SHOW_FUNCTION(cfq_low_latency_show, cfqd->cfq_latency, 0);
  3203. #undef SHOW_FUNCTION
  3204. #define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \
  3205. static ssize_t __FUNC(struct elevator_queue *e, const char *page, size_t count) \
  3206. { \
  3207. struct cfq_data *cfqd = e->elevator_data; \
  3208. unsigned int __data; \
  3209. int ret = cfq_var_store(&__data, (page), count); \
  3210. if (__data < (MIN)) \
  3211. __data = (MIN); \
  3212. else if (__data > (MAX)) \
  3213. __data = (MAX); \
  3214. if (__CONV) \
  3215. *(__PTR) = msecs_to_jiffies(__data); \
  3216. else \
  3217. *(__PTR) = __data; \
  3218. return ret; \
  3219. }
  3220. STORE_FUNCTION(cfq_quantum_store, &cfqd->cfq_quantum, 1, UINT_MAX, 0);
  3221. STORE_FUNCTION(cfq_fifo_expire_sync_store, &cfqd->cfq_fifo_expire[1], 1,
  3222. UINT_MAX, 1);
  3223. STORE_FUNCTION(cfq_fifo_expire_async_store, &cfqd->cfq_fifo_expire[0], 1,
  3224. UINT_MAX, 1);
  3225. STORE_FUNCTION(cfq_back_seek_max_store, &cfqd->cfq_back_max, 0, UINT_MAX, 0);
  3226. STORE_FUNCTION(cfq_back_seek_penalty_store, &cfqd->cfq_back_penalty, 1,
  3227. UINT_MAX, 0);
  3228. STORE_FUNCTION(cfq_slice_idle_store, &cfqd->cfq_slice_idle, 0, UINT_MAX, 1);
  3229. STORE_FUNCTION(cfq_group_idle_store, &cfqd->cfq_group_idle, 0, UINT_MAX, 1);
  3230. STORE_FUNCTION(cfq_slice_sync_store, &cfqd->cfq_slice[1], 1, UINT_MAX, 1);
  3231. STORE_FUNCTION(cfq_slice_async_store, &cfqd->cfq_slice[0], 1, UINT_MAX, 1);
  3232. STORE_FUNCTION(cfq_slice_async_rq_store, &cfqd->cfq_slice_async_rq, 1,
  3233. UINT_MAX, 0);
  3234. STORE_FUNCTION(cfq_low_latency_store, &cfqd->cfq_latency, 0, 1, 0);
  3235. #undef STORE_FUNCTION
  3236. #define CFQ_ATTR(name) \
  3237. __ATTR(name, S_IRUGO|S_IWUSR, cfq_##name##_show, cfq_##name##_store)
  3238. static struct elv_fs_entry cfq_attrs[] = {
  3239. CFQ_ATTR(quantum),
  3240. CFQ_ATTR(fifo_expire_sync),
  3241. CFQ_ATTR(fifo_expire_async),
  3242. CFQ_ATTR(back_seek_max),
  3243. CFQ_ATTR(back_seek_penalty),
  3244. CFQ_ATTR(slice_sync),
  3245. CFQ_ATTR(slice_async),
  3246. CFQ_ATTR(slice_async_rq),
  3247. CFQ_ATTR(slice_idle),
  3248. CFQ_ATTR(group_idle),
  3249. CFQ_ATTR(low_latency),
  3250. __ATTR_NULL
  3251. };
  3252. static struct elevator_type iosched_cfq = {
  3253. .ops = {
  3254. .elevator_merge_fn = cfq_merge,
  3255. .elevator_merged_fn = cfq_merged_request,
  3256. .elevator_merge_req_fn = cfq_merged_requests,
  3257. .elevator_allow_merge_fn = cfq_allow_merge,
  3258. .elevator_bio_merged_fn = cfq_bio_merged,
  3259. .elevator_dispatch_fn = cfq_dispatch_requests,
  3260. .elevator_add_req_fn = cfq_insert_request,
  3261. .elevator_activate_req_fn = cfq_activate_request,
  3262. .elevator_deactivate_req_fn = cfq_deactivate_request,
  3263. .elevator_completed_req_fn = cfq_completed_request,
  3264. .elevator_former_req_fn = elv_rb_former_request,
  3265. .elevator_latter_req_fn = elv_rb_latter_request,
  3266. .elevator_init_icq_fn = cfq_init_icq,
  3267. .elevator_exit_icq_fn = cfq_exit_icq,
  3268. .elevator_set_req_fn = cfq_set_request,
  3269. .elevator_put_req_fn = cfq_put_request,
  3270. .elevator_may_queue_fn = cfq_may_queue,
  3271. .elevator_init_fn = cfq_init_queue,
  3272. .elevator_exit_fn = cfq_exit_queue,
  3273. },
  3274. .icq_size = sizeof(struct cfq_io_cq),
  3275. .icq_align = __alignof__(struct cfq_io_cq),
  3276. .elevator_attrs = cfq_attrs,
  3277. .elevator_name = "cfq",
  3278. .elevator_owner = THIS_MODULE,
  3279. };
  3280. #ifdef CONFIG_CFQ_GROUP_IOSCHED
  3281. static struct blkio_policy_type blkio_policy_cfq = {
  3282. .ops = {
  3283. .blkio_unlink_group_fn = cfq_unlink_blkio_group,
  3284. .blkio_update_group_weight_fn = cfq_update_blkio_group_weight,
  3285. },
  3286. .plid = BLKIO_POLICY_PROP,
  3287. };
  3288. #else
  3289. static struct blkio_policy_type blkio_policy_cfq;
  3290. #endif
  3291. static int __init cfq_init(void)
  3292. {
  3293. int ret;
  3294. /*
  3295. * could be 0 on HZ < 1000 setups
  3296. */
  3297. if (!cfq_slice_async)
  3298. cfq_slice_async = 1;
  3299. if (!cfq_slice_idle)
  3300. cfq_slice_idle = 1;
  3301. #ifdef CONFIG_CFQ_GROUP_IOSCHED
  3302. if (!cfq_group_idle)
  3303. cfq_group_idle = 1;
  3304. #else
  3305. cfq_group_idle = 0;
  3306. #endif
  3307. cfq_pool = KMEM_CACHE(cfq_queue, 0);
  3308. if (!cfq_pool)
  3309. return -ENOMEM;
  3310. ret = elv_register(&iosched_cfq);
  3311. if (ret) {
  3312. kmem_cache_destroy(cfq_pool);
  3313. return ret;
  3314. }
  3315. blkio_policy_register(&blkio_policy_cfq);
  3316. return 0;
  3317. }
  3318. static void __exit cfq_exit(void)
  3319. {
  3320. blkio_policy_unregister(&blkio_policy_cfq);
  3321. elv_unregister(&iosched_cfq);
  3322. kmem_cache_destroy(cfq_pool);
  3323. }
  3324. module_init(cfq_init);
  3325. module_exit(cfq_exit);
  3326. MODULE_AUTHOR("Jens Axboe");
  3327. MODULE_LICENSE("GPL");
  3328. MODULE_DESCRIPTION("Completely Fair Queueing IO scheduler");