cfq-iosched.c 107 KB

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