cfq-iosched.c 101 KB

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