bfq-wf2q.c 52 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712
  1. // SPDX-License-Identifier: GPL-2.0-or-later
  2. /*
  3. * Hierarchical Budget Worst-case Fair Weighted Fair Queueing
  4. * (B-WF2Q+): hierarchical scheduling algorithm by which the BFQ I/O
  5. * scheduler schedules generic entities. The latter can represent
  6. * either single bfq queues (associated with processes) or groups of
  7. * bfq queues (associated with cgroups).
  8. */
  9. #include "bfq-iosched.h"
  10. /**
  11. * bfq_gt - compare two timestamps.
  12. * @a: first ts.
  13. * @b: second ts.
  14. *
  15. * Return @a > @b, dealing with wrapping correctly.
  16. */
  17. static int bfq_gt(u64 a, u64 b)
  18. {
  19. return (s64)(a - b) > 0;
  20. }
  21. static struct bfq_entity *bfq_root_active_entity(struct rb_root *tree)
  22. {
  23. struct rb_node *node = tree->rb_node;
  24. return rb_entry(node, struct bfq_entity, rb_node);
  25. }
  26. static unsigned int bfq_class_idx(struct bfq_entity *entity)
  27. {
  28. struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
  29. return bfqq ? bfqq->ioprio_class - 1 :
  30. BFQ_DEFAULT_GRP_CLASS - 1;
  31. }
  32. unsigned int bfq_tot_busy_queues(struct bfq_data *bfqd)
  33. {
  34. return bfqd->busy_queues[0] + bfqd->busy_queues[1] +
  35. bfqd->busy_queues[2];
  36. }
  37. static struct bfq_entity *bfq_lookup_next_entity(struct bfq_sched_data *sd,
  38. bool expiration);
  39. static bool bfq_update_parent_budget(struct bfq_entity *next_in_service);
  40. /**
  41. * bfq_update_next_in_service - update sd->next_in_service
  42. * @sd: sched_data for which to perform the update.
  43. * @new_entity: if not NULL, pointer to the entity whose activation,
  44. * requeueing or repositioning triggered the invocation of
  45. * this function.
  46. * @expiration: id true, this function is being invoked after the
  47. * expiration of the in-service entity
  48. *
  49. * This function is called to update sd->next_in_service, which, in
  50. * its turn, may change as a consequence of the insertion or
  51. * extraction of an entity into/from one of the active trees of
  52. * sd. These insertions/extractions occur as a consequence of
  53. * activations/deactivations of entities, with some activations being
  54. * 'true' activations, and other activations being requeueings (i.e.,
  55. * implementing the second, requeueing phase of the mechanism used to
  56. * reposition an entity in its active tree; see comments on
  57. * __bfq_activate_entity and __bfq_requeue_entity for details). In
  58. * both the last two activation sub-cases, new_entity points to the
  59. * just activated or requeued entity.
  60. *
  61. * Returns true if sd->next_in_service changes in such a way that
  62. * entity->parent may become the next_in_service for its parent
  63. * entity.
  64. */
  65. static bool bfq_update_next_in_service(struct bfq_sched_data *sd,
  66. struct bfq_entity *new_entity,
  67. bool expiration)
  68. {
  69. struct bfq_entity *next_in_service = sd->next_in_service;
  70. bool parent_sched_may_change = false;
  71. bool change_without_lookup = false;
  72. /*
  73. * If this update is triggered by the activation, requeueing
  74. * or repositioning of an entity that does not coincide with
  75. * sd->next_in_service, then a full lookup in the active tree
  76. * can be avoided. In fact, it is enough to check whether the
  77. * just-modified entity has the same priority as
  78. * sd->next_in_service, is eligible and has a lower virtual
  79. * finish time than sd->next_in_service. If this compound
  80. * condition holds, then the new entity becomes the new
  81. * next_in_service. Otherwise no change is needed.
  82. */
  83. if (new_entity && new_entity != sd->next_in_service) {
  84. /*
  85. * Flag used to decide whether to replace
  86. * sd->next_in_service with new_entity. Tentatively
  87. * set to true, and left as true if
  88. * sd->next_in_service is NULL.
  89. */
  90. change_without_lookup = true;
  91. /*
  92. * If there is already a next_in_service candidate
  93. * entity, then compare timestamps to decide whether
  94. * to replace sd->service_tree with new_entity.
  95. */
  96. if (next_in_service) {
  97. unsigned int new_entity_class_idx =
  98. bfq_class_idx(new_entity);
  99. struct bfq_service_tree *st =
  100. sd->service_tree + new_entity_class_idx;
  101. change_without_lookup =
  102. (new_entity_class_idx ==
  103. bfq_class_idx(next_in_service)
  104. &&
  105. !bfq_gt(new_entity->start, st->vtime)
  106. &&
  107. bfq_gt(next_in_service->finish,
  108. new_entity->finish));
  109. }
  110. if (change_without_lookup)
  111. next_in_service = new_entity;
  112. }
  113. if (!change_without_lookup) /* lookup needed */
  114. next_in_service = bfq_lookup_next_entity(sd, expiration);
  115. if (next_in_service) {
  116. bool new_budget_triggers_change =
  117. bfq_update_parent_budget(next_in_service);
  118. parent_sched_may_change = !sd->next_in_service ||
  119. new_budget_triggers_change;
  120. }
  121. sd->next_in_service = next_in_service;
  122. if (!next_in_service)
  123. return parent_sched_may_change;
  124. return parent_sched_may_change;
  125. }
  126. #ifdef CONFIG_BFQ_GROUP_IOSCHED
  127. struct bfq_group *bfq_bfqq_to_bfqg(struct bfq_queue *bfqq)
  128. {
  129. struct bfq_entity *group_entity = bfqq->entity.parent;
  130. if (!group_entity)
  131. group_entity = &bfqq->bfqd->root_group->entity;
  132. return container_of(group_entity, struct bfq_group, entity);
  133. }
  134. /*
  135. * Returns true if this budget changes may let next_in_service->parent
  136. * become the next_in_service entity for its parent entity.
  137. */
  138. static bool bfq_update_parent_budget(struct bfq_entity *next_in_service)
  139. {
  140. struct bfq_entity *bfqg_entity;
  141. struct bfq_group *bfqg;
  142. struct bfq_sched_data *group_sd;
  143. bool ret = false;
  144. group_sd = next_in_service->sched_data;
  145. bfqg = container_of(group_sd, struct bfq_group, sched_data);
  146. /*
  147. * bfq_group's my_entity field is not NULL only if the group
  148. * is not the root group. We must not touch the root entity
  149. * as it must never become an in-service entity.
  150. */
  151. bfqg_entity = bfqg->my_entity;
  152. if (bfqg_entity) {
  153. if (bfqg_entity->budget > next_in_service->budget)
  154. ret = true;
  155. bfqg_entity->budget = next_in_service->budget;
  156. }
  157. return ret;
  158. }
  159. /*
  160. * This function tells whether entity stops being a candidate for next
  161. * service, according to the restrictive definition of the field
  162. * next_in_service. In particular, this function is invoked for an
  163. * entity that is about to be set in service.
  164. *
  165. * If entity is a queue, then the entity is no longer a candidate for
  166. * next service according to the that definition, because entity is
  167. * about to become the in-service queue. This function then returns
  168. * true if entity is a queue.
  169. *
  170. * In contrast, entity could still be a candidate for next service if
  171. * it is not a queue, and has more than one active child. In fact,
  172. * even if one of its children is about to be set in service, other
  173. * active children may still be the next to serve, for the parent
  174. * entity, even according to the above definition. As a consequence, a
  175. * non-queue entity is not a candidate for next-service only if it has
  176. * only one active child. And only if this condition holds, then this
  177. * function returns true for a non-queue entity.
  178. */
  179. static bool bfq_no_longer_next_in_service(struct bfq_entity *entity)
  180. {
  181. struct bfq_group *bfqg;
  182. if (bfq_entity_to_bfqq(entity))
  183. return true;
  184. bfqg = container_of(entity, struct bfq_group, entity);
  185. /*
  186. * The field active_entities does not always contain the
  187. * actual number of active children entities: it happens to
  188. * not account for the in-service entity in case the latter is
  189. * removed from its active tree (which may get done after
  190. * invoking the function bfq_no_longer_next_in_service in
  191. * bfq_get_next_queue). Fortunately, here, i.e., while
  192. * bfq_no_longer_next_in_service is not yet completed in
  193. * bfq_get_next_queue, bfq_active_extract has not yet been
  194. * invoked, and thus active_entities still coincides with the
  195. * actual number of active entities.
  196. */
  197. if (bfqg->active_entities == 1)
  198. return true;
  199. return false;
  200. }
  201. #else /* CONFIG_BFQ_GROUP_IOSCHED */
  202. struct bfq_group *bfq_bfqq_to_bfqg(struct bfq_queue *bfqq)
  203. {
  204. return bfqq->bfqd->root_group;
  205. }
  206. static bool bfq_update_parent_budget(struct bfq_entity *next_in_service)
  207. {
  208. return false;
  209. }
  210. static bool bfq_no_longer_next_in_service(struct bfq_entity *entity)
  211. {
  212. return true;
  213. }
  214. #endif /* CONFIG_BFQ_GROUP_IOSCHED */
  215. /*
  216. * Shift for timestamp calculations. This actually limits the maximum
  217. * service allowed in one timestamp delta (small shift values increase it),
  218. * the maximum total weight that can be used for the queues in the system
  219. * (big shift values increase it), and the period of virtual time
  220. * wraparounds.
  221. */
  222. #define WFQ_SERVICE_SHIFT 22
  223. struct bfq_queue *bfq_entity_to_bfqq(struct bfq_entity *entity)
  224. {
  225. struct bfq_queue *bfqq = NULL;
  226. if (!entity->my_sched_data)
  227. bfqq = container_of(entity, struct bfq_queue, entity);
  228. return bfqq;
  229. }
  230. /**
  231. * bfq_delta - map service into the virtual time domain.
  232. * @service: amount of service.
  233. * @weight: scale factor (weight of an entity or weight sum).
  234. */
  235. static u64 bfq_delta(unsigned long service, unsigned long weight)
  236. {
  237. return div64_ul((u64)service << WFQ_SERVICE_SHIFT, weight);
  238. }
  239. /**
  240. * bfq_calc_finish - assign the finish time to an entity.
  241. * @entity: the entity to act upon.
  242. * @service: the service to be charged to the entity.
  243. */
  244. static void bfq_calc_finish(struct bfq_entity *entity, unsigned long service)
  245. {
  246. struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
  247. entity->finish = entity->start +
  248. bfq_delta(service, entity->weight);
  249. if (bfqq) {
  250. bfq_log_bfqq(bfqq->bfqd, bfqq,
  251. "calc_finish: serv %lu, w %d",
  252. service, entity->weight);
  253. bfq_log_bfqq(bfqq->bfqd, bfqq,
  254. "calc_finish: start %llu, finish %llu, delta %llu",
  255. entity->start, entity->finish,
  256. bfq_delta(service, entity->weight));
  257. }
  258. }
  259. /**
  260. * bfq_entity_of - get an entity from a node.
  261. * @node: the node field of the entity.
  262. *
  263. * Convert a node pointer to the relative entity. This is used only
  264. * to simplify the logic of some functions and not as the generic
  265. * conversion mechanism because, e.g., in the tree walking functions,
  266. * the check for a %NULL value would be redundant.
  267. */
  268. struct bfq_entity *bfq_entity_of(struct rb_node *node)
  269. {
  270. struct bfq_entity *entity = NULL;
  271. if (node)
  272. entity = rb_entry(node, struct bfq_entity, rb_node);
  273. return entity;
  274. }
  275. /**
  276. * bfq_extract - remove an entity from a tree.
  277. * @root: the tree root.
  278. * @entity: the entity to remove.
  279. */
  280. static void bfq_extract(struct rb_root *root, struct bfq_entity *entity)
  281. {
  282. entity->tree = NULL;
  283. rb_erase(&entity->rb_node, root);
  284. }
  285. /**
  286. * bfq_idle_extract - extract an entity from the idle tree.
  287. * @st: the service tree of the owning @entity.
  288. * @entity: the entity being removed.
  289. */
  290. static void bfq_idle_extract(struct bfq_service_tree *st,
  291. struct bfq_entity *entity)
  292. {
  293. struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
  294. struct rb_node *next;
  295. if (entity == st->first_idle) {
  296. next = rb_next(&entity->rb_node);
  297. st->first_idle = bfq_entity_of(next);
  298. }
  299. if (entity == st->last_idle) {
  300. next = rb_prev(&entity->rb_node);
  301. st->last_idle = bfq_entity_of(next);
  302. }
  303. bfq_extract(&st->idle, entity);
  304. if (bfqq)
  305. list_del(&bfqq->bfqq_list);
  306. }
  307. /**
  308. * bfq_insert - generic tree insertion.
  309. * @root: tree root.
  310. * @entity: entity to insert.
  311. *
  312. * This is used for the idle and the active tree, since they are both
  313. * ordered by finish time.
  314. */
  315. static void bfq_insert(struct rb_root *root, struct bfq_entity *entity)
  316. {
  317. struct bfq_entity *entry;
  318. struct rb_node **node = &root->rb_node;
  319. struct rb_node *parent = NULL;
  320. while (*node) {
  321. parent = *node;
  322. entry = rb_entry(parent, struct bfq_entity, rb_node);
  323. if (bfq_gt(entry->finish, entity->finish))
  324. node = &parent->rb_left;
  325. else
  326. node = &parent->rb_right;
  327. }
  328. rb_link_node(&entity->rb_node, parent, node);
  329. rb_insert_color(&entity->rb_node, root);
  330. entity->tree = root;
  331. }
  332. /**
  333. * bfq_update_min - update the min_start field of a entity.
  334. * @entity: the entity to update.
  335. * @node: one of its children.
  336. *
  337. * This function is called when @entity may store an invalid value for
  338. * min_start due to updates to the active tree. The function assumes
  339. * that the subtree rooted at @node (which may be its left or its right
  340. * child) has a valid min_start value.
  341. */
  342. static void bfq_update_min(struct bfq_entity *entity, struct rb_node *node)
  343. {
  344. struct bfq_entity *child;
  345. if (node) {
  346. child = rb_entry(node, struct bfq_entity, rb_node);
  347. if (bfq_gt(entity->min_start, child->min_start))
  348. entity->min_start = child->min_start;
  349. }
  350. }
  351. /**
  352. * bfq_update_active_node - recalculate min_start.
  353. * @node: the node to update.
  354. *
  355. * @node may have changed position or one of its children may have moved,
  356. * this function updates its min_start value. The left and right subtrees
  357. * are assumed to hold a correct min_start value.
  358. */
  359. static void bfq_update_active_node(struct rb_node *node)
  360. {
  361. struct bfq_entity *entity = rb_entry(node, struct bfq_entity, rb_node);
  362. entity->min_start = entity->start;
  363. bfq_update_min(entity, node->rb_right);
  364. bfq_update_min(entity, node->rb_left);
  365. }
  366. /**
  367. * bfq_update_active_tree - update min_start for the whole active tree.
  368. * @node: the starting node.
  369. *
  370. * @node must be the deepest modified node after an update. This function
  371. * updates its min_start using the values held by its children, assuming
  372. * that they did not change, and then updates all the nodes that may have
  373. * changed in the path to the root. The only nodes that may have changed
  374. * are the ones in the path or their siblings.
  375. */
  376. static void bfq_update_active_tree(struct rb_node *node)
  377. {
  378. struct rb_node *parent;
  379. up:
  380. bfq_update_active_node(node);
  381. parent = rb_parent(node);
  382. if (!parent)
  383. return;
  384. if (node == parent->rb_left && parent->rb_right)
  385. bfq_update_active_node(parent->rb_right);
  386. else if (parent->rb_left)
  387. bfq_update_active_node(parent->rb_left);
  388. node = parent;
  389. goto up;
  390. }
  391. /**
  392. * bfq_active_insert - insert an entity in the active tree of its
  393. * group/device.
  394. * @st: the service tree of the entity.
  395. * @entity: the entity being inserted.
  396. *
  397. * The active tree is ordered by finish time, but an extra key is kept
  398. * per each node, containing the minimum value for the start times of
  399. * its children (and the node itself), so it's possible to search for
  400. * the eligible node with the lowest finish time in logarithmic time.
  401. */
  402. static void bfq_active_insert(struct bfq_service_tree *st,
  403. struct bfq_entity *entity)
  404. {
  405. struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
  406. struct rb_node *node = &entity->rb_node;
  407. #ifdef CONFIG_BFQ_GROUP_IOSCHED
  408. struct bfq_sched_data *sd = NULL;
  409. struct bfq_group *bfqg = NULL;
  410. struct bfq_data *bfqd = NULL;
  411. #endif
  412. bfq_insert(&st->active, entity);
  413. if (node->rb_left)
  414. node = node->rb_left;
  415. else if (node->rb_right)
  416. node = node->rb_right;
  417. bfq_update_active_tree(node);
  418. #ifdef CONFIG_BFQ_GROUP_IOSCHED
  419. sd = entity->sched_data;
  420. bfqg = container_of(sd, struct bfq_group, sched_data);
  421. bfqd = (struct bfq_data *)bfqg->bfqd;
  422. #endif
  423. if (bfqq)
  424. list_add(&bfqq->bfqq_list, &bfqq->bfqd->active_list);
  425. #ifdef CONFIG_BFQ_GROUP_IOSCHED
  426. if (bfqg != bfqd->root_group)
  427. bfqg->active_entities++;
  428. #endif
  429. }
  430. /**
  431. * bfq_ioprio_to_weight - calc a weight from an ioprio.
  432. * @ioprio: the ioprio value to convert.
  433. */
  434. unsigned short bfq_ioprio_to_weight(int ioprio)
  435. {
  436. return (IOPRIO_BE_NR - ioprio) * BFQ_WEIGHT_CONVERSION_COEFF;
  437. }
  438. /**
  439. * bfq_weight_to_ioprio - calc an ioprio from a weight.
  440. * @weight: the weight value to convert.
  441. *
  442. * To preserve as much as possible the old only-ioprio user interface,
  443. * 0 is used as an escape ioprio value for weights (numerically) equal or
  444. * larger than IOPRIO_BE_NR * BFQ_WEIGHT_CONVERSION_COEFF.
  445. */
  446. static unsigned short bfq_weight_to_ioprio(int weight)
  447. {
  448. return max_t(int, 0,
  449. IOPRIO_BE_NR * BFQ_WEIGHT_CONVERSION_COEFF - weight);
  450. }
  451. static void bfq_get_entity(struct bfq_entity *entity)
  452. {
  453. struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
  454. if (bfqq) {
  455. bfqq->ref++;
  456. bfq_log_bfqq(bfqq->bfqd, bfqq, "get_entity: %p %d",
  457. bfqq, bfqq->ref);
  458. }
  459. }
  460. /**
  461. * bfq_find_deepest - find the deepest node that an extraction can modify.
  462. * @node: the node being removed.
  463. *
  464. * Do the first step of an extraction in an rb tree, looking for the
  465. * node that will replace @node, and returning the deepest node that
  466. * the following modifications to the tree can touch. If @node is the
  467. * last node in the tree return %NULL.
  468. */
  469. static struct rb_node *bfq_find_deepest(struct rb_node *node)
  470. {
  471. struct rb_node *deepest;
  472. if (!node->rb_right && !node->rb_left)
  473. deepest = rb_parent(node);
  474. else if (!node->rb_right)
  475. deepest = node->rb_left;
  476. else if (!node->rb_left)
  477. deepest = node->rb_right;
  478. else {
  479. deepest = rb_next(node);
  480. if (deepest->rb_right)
  481. deepest = deepest->rb_right;
  482. else if (rb_parent(deepest) != node)
  483. deepest = rb_parent(deepest);
  484. }
  485. return deepest;
  486. }
  487. /**
  488. * bfq_active_extract - remove an entity from the active tree.
  489. * @st: the service_tree containing the tree.
  490. * @entity: the entity being removed.
  491. */
  492. static void bfq_active_extract(struct bfq_service_tree *st,
  493. struct bfq_entity *entity)
  494. {
  495. struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
  496. struct rb_node *node;
  497. #ifdef CONFIG_BFQ_GROUP_IOSCHED
  498. struct bfq_sched_data *sd = NULL;
  499. struct bfq_group *bfqg = NULL;
  500. struct bfq_data *bfqd = NULL;
  501. #endif
  502. node = bfq_find_deepest(&entity->rb_node);
  503. bfq_extract(&st->active, entity);
  504. if (node)
  505. bfq_update_active_tree(node);
  506. #ifdef CONFIG_BFQ_GROUP_IOSCHED
  507. sd = entity->sched_data;
  508. bfqg = container_of(sd, struct bfq_group, sched_data);
  509. bfqd = (struct bfq_data *)bfqg->bfqd;
  510. #endif
  511. if (bfqq)
  512. list_del(&bfqq->bfqq_list);
  513. #ifdef CONFIG_BFQ_GROUP_IOSCHED
  514. if (bfqg != bfqd->root_group)
  515. bfqg->active_entities--;
  516. #endif
  517. }
  518. /**
  519. * bfq_idle_insert - insert an entity into the idle tree.
  520. * @st: the service tree containing the tree.
  521. * @entity: the entity to insert.
  522. */
  523. static void bfq_idle_insert(struct bfq_service_tree *st,
  524. struct bfq_entity *entity)
  525. {
  526. struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
  527. struct bfq_entity *first_idle = st->first_idle;
  528. struct bfq_entity *last_idle = st->last_idle;
  529. if (!first_idle || bfq_gt(first_idle->finish, entity->finish))
  530. st->first_idle = entity;
  531. if (!last_idle || bfq_gt(entity->finish, last_idle->finish))
  532. st->last_idle = entity;
  533. bfq_insert(&st->idle, entity);
  534. if (bfqq)
  535. list_add(&bfqq->bfqq_list, &bfqq->bfqd->idle_list);
  536. }
  537. /**
  538. * bfq_forget_entity - do not consider entity any longer for scheduling
  539. * @st: the service tree.
  540. * @entity: the entity being removed.
  541. * @is_in_service: true if entity is currently the in-service entity.
  542. *
  543. * Forget everything about @entity. In addition, if entity represents
  544. * a queue, and the latter is not in service, then release the service
  545. * reference to the queue (the one taken through bfq_get_entity). In
  546. * fact, in this case, there is really no more service reference to
  547. * the queue, as the latter is also outside any service tree. If,
  548. * instead, the queue is in service, then __bfq_bfqd_reset_in_service
  549. * will take care of putting the reference when the queue finally
  550. * stops being served.
  551. */
  552. static void bfq_forget_entity(struct bfq_service_tree *st,
  553. struct bfq_entity *entity,
  554. bool is_in_service)
  555. {
  556. struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
  557. entity->on_st_or_in_serv = false;
  558. st->wsum -= entity->weight;
  559. if (bfqq && !is_in_service)
  560. bfq_put_queue(bfqq);
  561. }
  562. /**
  563. * bfq_put_idle_entity - release the idle tree ref of an entity.
  564. * @st: service tree for the entity.
  565. * @entity: the entity being released.
  566. */
  567. void bfq_put_idle_entity(struct bfq_service_tree *st, struct bfq_entity *entity)
  568. {
  569. bfq_idle_extract(st, entity);
  570. bfq_forget_entity(st, entity,
  571. entity == entity->sched_data->in_service_entity);
  572. }
  573. /**
  574. * bfq_forget_idle - update the idle tree if necessary.
  575. * @st: the service tree to act upon.
  576. *
  577. * To preserve the global O(log N) complexity we only remove one entry here;
  578. * as the idle tree will not grow indefinitely this can be done safely.
  579. */
  580. static void bfq_forget_idle(struct bfq_service_tree *st)
  581. {
  582. struct bfq_entity *first_idle = st->first_idle;
  583. struct bfq_entity *last_idle = st->last_idle;
  584. if (RB_EMPTY_ROOT(&st->active) && last_idle &&
  585. !bfq_gt(last_idle->finish, st->vtime)) {
  586. /*
  587. * Forget the whole idle tree, increasing the vtime past
  588. * the last finish time of idle entities.
  589. */
  590. st->vtime = last_idle->finish;
  591. }
  592. if (first_idle && !bfq_gt(first_idle->finish, st->vtime))
  593. bfq_put_idle_entity(st, first_idle);
  594. }
  595. struct bfq_service_tree *bfq_entity_service_tree(struct bfq_entity *entity)
  596. {
  597. struct bfq_sched_data *sched_data = entity->sched_data;
  598. unsigned int idx = bfq_class_idx(entity);
  599. return sched_data->service_tree + idx;
  600. }
  601. /*
  602. * Update weight and priority of entity. If update_class_too is true,
  603. * then update the ioprio_class of entity too.
  604. *
  605. * The reason why the update of ioprio_class is controlled through the
  606. * last parameter is as follows. Changing the ioprio class of an
  607. * entity implies changing the destination service trees for that
  608. * entity. If such a change occurred when the entity is already on one
  609. * of the service trees for its previous class, then the state of the
  610. * entity would become more complex: none of the new possible service
  611. * trees for the entity, according to bfq_entity_service_tree(), would
  612. * match any of the possible service trees on which the entity
  613. * is. Complex operations involving these trees, such as entity
  614. * activations and deactivations, should take into account this
  615. * additional complexity. To avoid this issue, this function is
  616. * invoked with update_class_too unset in the points in the code where
  617. * entity may happen to be on some tree.
  618. */
  619. struct bfq_service_tree *
  620. __bfq_entity_update_weight_prio(struct bfq_service_tree *old_st,
  621. struct bfq_entity *entity,
  622. bool update_class_too)
  623. {
  624. struct bfq_service_tree *new_st = old_st;
  625. if (entity->prio_changed) {
  626. struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
  627. unsigned int prev_weight, new_weight;
  628. struct bfq_data *bfqd = NULL;
  629. struct rb_root_cached *root;
  630. #ifdef CONFIG_BFQ_GROUP_IOSCHED
  631. struct bfq_sched_data *sd;
  632. struct bfq_group *bfqg;
  633. #endif
  634. if (bfqq)
  635. bfqd = bfqq->bfqd;
  636. #ifdef CONFIG_BFQ_GROUP_IOSCHED
  637. else {
  638. sd = entity->my_sched_data;
  639. bfqg = container_of(sd, struct bfq_group, sched_data);
  640. bfqd = (struct bfq_data *)bfqg->bfqd;
  641. }
  642. #endif
  643. /* Matches the smp_wmb() in bfq_group_set_weight. */
  644. smp_rmb();
  645. old_st->wsum -= entity->weight;
  646. if (entity->new_weight != entity->orig_weight) {
  647. if (entity->new_weight < BFQ_MIN_WEIGHT ||
  648. entity->new_weight > BFQ_MAX_WEIGHT) {
  649. pr_crit("update_weight_prio: new_weight %d\n",
  650. entity->new_weight);
  651. if (entity->new_weight < BFQ_MIN_WEIGHT)
  652. entity->new_weight = BFQ_MIN_WEIGHT;
  653. else
  654. entity->new_weight = BFQ_MAX_WEIGHT;
  655. }
  656. entity->orig_weight = entity->new_weight;
  657. if (bfqq)
  658. bfqq->ioprio =
  659. bfq_weight_to_ioprio(entity->orig_weight);
  660. }
  661. if (bfqq && update_class_too)
  662. bfqq->ioprio_class = bfqq->new_ioprio_class;
  663. /*
  664. * Reset prio_changed only if the ioprio_class change
  665. * is not pending any longer.
  666. */
  667. if (!bfqq || bfqq->ioprio_class == bfqq->new_ioprio_class)
  668. entity->prio_changed = 0;
  669. /*
  670. * NOTE: here we may be changing the weight too early,
  671. * this will cause unfairness. The correct approach
  672. * would have required additional complexity to defer
  673. * weight changes to the proper time instants (i.e.,
  674. * when entity->finish <= old_st->vtime).
  675. */
  676. new_st = bfq_entity_service_tree(entity);
  677. prev_weight = entity->weight;
  678. new_weight = entity->orig_weight *
  679. (bfqq ? bfqq->wr_coeff : 1);
  680. /*
  681. * If the weight of the entity changes, and the entity is a
  682. * queue, remove the entity from its old weight counter (if
  683. * there is a counter associated with the entity).
  684. */
  685. if (prev_weight != new_weight && bfqq) {
  686. root = &bfqd->queue_weights_tree;
  687. __bfq_weights_tree_remove(bfqd, bfqq, root);
  688. }
  689. entity->weight = new_weight;
  690. /*
  691. * Add the entity, if it is not a weight-raised queue,
  692. * to the counter associated with its new weight.
  693. */
  694. if (prev_weight != new_weight && bfqq && bfqq->wr_coeff == 1) {
  695. /* If we get here, root has been initialized. */
  696. bfq_weights_tree_add(bfqd, bfqq, root);
  697. }
  698. new_st->wsum += entity->weight;
  699. if (new_st != old_st)
  700. entity->start = new_st->vtime;
  701. }
  702. return new_st;
  703. }
  704. /**
  705. * bfq_bfqq_served - update the scheduler status after selection for
  706. * service.
  707. * @bfqq: the queue being served.
  708. * @served: bytes to transfer.
  709. *
  710. * NOTE: this can be optimized, as the timestamps of upper level entities
  711. * are synchronized every time a new bfqq is selected for service. By now,
  712. * we keep it to better check consistency.
  713. */
  714. void bfq_bfqq_served(struct bfq_queue *bfqq, int served)
  715. {
  716. struct bfq_entity *entity = &bfqq->entity;
  717. struct bfq_service_tree *st;
  718. if (!bfqq->service_from_backlogged)
  719. bfqq->first_IO_time = jiffies;
  720. if (bfqq->wr_coeff > 1)
  721. bfqq->service_from_wr += served;
  722. bfqq->service_from_backlogged += served;
  723. for_each_entity(entity) {
  724. st = bfq_entity_service_tree(entity);
  725. entity->service += served;
  726. st->vtime += bfq_delta(served, st->wsum);
  727. bfq_forget_idle(st);
  728. }
  729. bfq_log_bfqq(bfqq->bfqd, bfqq, "bfqq_served %d secs", served);
  730. }
  731. /**
  732. * bfq_bfqq_charge_time - charge an amount of service equivalent to the length
  733. * of the time interval during which bfqq has been in
  734. * service.
  735. * @bfqd: the device
  736. * @bfqq: the queue that needs a service update.
  737. * @time_ms: the amount of time during which the queue has received service
  738. *
  739. * If a queue does not consume its budget fast enough, then providing
  740. * the queue with service fairness may impair throughput, more or less
  741. * severely. For this reason, queues that consume their budget slowly
  742. * are provided with time fairness instead of service fairness. This
  743. * goal is achieved through the BFQ scheduling engine, even if such an
  744. * engine works in the service, and not in the time domain. The trick
  745. * is charging these queues with an inflated amount of service, equal
  746. * to the amount of service that they would have received during their
  747. * service slot if they had been fast, i.e., if their requests had
  748. * been dispatched at a rate equal to the estimated peak rate.
  749. *
  750. * It is worth noting that time fairness can cause important
  751. * distortions in terms of bandwidth distribution, on devices with
  752. * internal queueing. The reason is that I/O requests dispatched
  753. * during the service slot of a queue may be served after that service
  754. * slot is finished, and may have a total processing time loosely
  755. * correlated with the duration of the service slot. This is
  756. * especially true for short service slots.
  757. */
  758. void bfq_bfqq_charge_time(struct bfq_data *bfqd, struct bfq_queue *bfqq,
  759. unsigned long time_ms)
  760. {
  761. struct bfq_entity *entity = &bfqq->entity;
  762. unsigned long timeout_ms = jiffies_to_msecs(bfq_timeout);
  763. unsigned long bounded_time_ms = min(time_ms, timeout_ms);
  764. int serv_to_charge_for_time =
  765. (bfqd->bfq_max_budget * bounded_time_ms) / timeout_ms;
  766. int tot_serv_to_charge = max(serv_to_charge_for_time, entity->service);
  767. /* Increase budget to avoid inconsistencies */
  768. if (tot_serv_to_charge > entity->budget)
  769. entity->budget = tot_serv_to_charge;
  770. bfq_bfqq_served(bfqq,
  771. max_t(int, 0, tot_serv_to_charge - entity->service));
  772. }
  773. static void bfq_update_fin_time_enqueue(struct bfq_entity *entity,
  774. struct bfq_service_tree *st,
  775. bool backshifted)
  776. {
  777. struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
  778. /*
  779. * When this function is invoked, entity is not in any service
  780. * tree, then it is safe to invoke next function with the last
  781. * parameter set (see the comments on the function).
  782. */
  783. st = __bfq_entity_update_weight_prio(st, entity, true);
  784. bfq_calc_finish(entity, entity->budget);
  785. /*
  786. * If some queues enjoy backshifting for a while, then their
  787. * (virtual) finish timestamps may happen to become lower and
  788. * lower than the system virtual time. In particular, if
  789. * these queues often happen to be idle for short time
  790. * periods, and during such time periods other queues with
  791. * higher timestamps happen to be busy, then the backshifted
  792. * timestamps of the former queues can become much lower than
  793. * the system virtual time. In fact, to serve the queues with
  794. * higher timestamps while the ones with lower timestamps are
  795. * idle, the system virtual time may be pushed-up to much
  796. * higher values than the finish timestamps of the idle
  797. * queues. As a consequence, the finish timestamps of all new
  798. * or newly activated queues may end up being much larger than
  799. * those of lucky queues with backshifted timestamps. The
  800. * latter queues may then monopolize the device for a lot of
  801. * time. This would simply break service guarantees.
  802. *
  803. * To reduce this problem, push up a little bit the
  804. * backshifted timestamps of the queue associated with this
  805. * entity (only a queue can happen to have the backshifted
  806. * flag set): just enough to let the finish timestamp of the
  807. * queue be equal to the current value of the system virtual
  808. * time. This may introduce a little unfairness among queues
  809. * with backshifted timestamps, but it does not break
  810. * worst-case fairness guarantees.
  811. *
  812. * As a special case, if bfqq is weight-raised, push up
  813. * timestamps much less, to keep very low the probability that
  814. * this push up causes the backshifted finish timestamps of
  815. * weight-raised queues to become higher than the backshifted
  816. * finish timestamps of non weight-raised queues.
  817. */
  818. if (backshifted && bfq_gt(st->vtime, entity->finish)) {
  819. unsigned long delta = st->vtime - entity->finish;
  820. if (bfqq)
  821. delta /= bfqq->wr_coeff;
  822. entity->start += delta;
  823. entity->finish += delta;
  824. }
  825. bfq_active_insert(st, entity);
  826. }
  827. /**
  828. * __bfq_activate_entity - handle activation of entity.
  829. * @entity: the entity being activated.
  830. * @non_blocking_wait_rq: true if entity was waiting for a request
  831. *
  832. * Called for a 'true' activation, i.e., if entity is not active and
  833. * one of its children receives a new request.
  834. *
  835. * Basically, this function updates the timestamps of entity and
  836. * inserts entity into its active tree, after possibly extracting it
  837. * from its idle tree.
  838. */
  839. static void __bfq_activate_entity(struct bfq_entity *entity,
  840. bool non_blocking_wait_rq)
  841. {
  842. struct bfq_service_tree *st = bfq_entity_service_tree(entity);
  843. bool backshifted = false;
  844. unsigned long long min_vstart;
  845. /* See comments on bfq_fqq_update_budg_for_activation */
  846. if (non_blocking_wait_rq && bfq_gt(st->vtime, entity->finish)) {
  847. backshifted = true;
  848. min_vstart = entity->finish;
  849. } else
  850. min_vstart = st->vtime;
  851. if (entity->tree == &st->idle) {
  852. /*
  853. * Must be on the idle tree, bfq_idle_extract() will
  854. * check for that.
  855. */
  856. bfq_idle_extract(st, entity);
  857. entity->start = bfq_gt(min_vstart, entity->finish) ?
  858. min_vstart : entity->finish;
  859. } else {
  860. /*
  861. * The finish time of the entity may be invalid, and
  862. * it is in the past for sure, otherwise the queue
  863. * would have been on the idle tree.
  864. */
  865. entity->start = min_vstart;
  866. st->wsum += entity->weight;
  867. /*
  868. * entity is about to be inserted into a service tree,
  869. * and then set in service: get a reference to make
  870. * sure entity does not disappear until it is no
  871. * longer in service or scheduled for service.
  872. */
  873. bfq_get_entity(entity);
  874. entity->on_st_or_in_serv = true;
  875. }
  876. #ifdef CONFIG_BFQ_GROUP_IOSCHED
  877. if (!bfq_entity_to_bfqq(entity)) { /* bfq_group */
  878. struct bfq_group *bfqg =
  879. container_of(entity, struct bfq_group, entity);
  880. struct bfq_data *bfqd = bfqg->bfqd;
  881. if (!entity->in_groups_with_pending_reqs) {
  882. entity->in_groups_with_pending_reqs = true;
  883. bfqd->num_groups_with_pending_reqs++;
  884. }
  885. }
  886. #endif
  887. bfq_update_fin_time_enqueue(entity, st, backshifted);
  888. }
  889. /**
  890. * __bfq_requeue_entity - handle requeueing or repositioning of an entity.
  891. * @entity: the entity being requeued or repositioned.
  892. *
  893. * Requeueing is needed if this entity stops being served, which
  894. * happens if a leaf descendant entity has expired. On the other hand,
  895. * repositioning is needed if the next_inservice_entity for the child
  896. * entity has changed. See the comments inside the function for
  897. * details.
  898. *
  899. * Basically, this function: 1) removes entity from its active tree if
  900. * present there, 2) updates the timestamps of entity and 3) inserts
  901. * entity back into its active tree (in the new, right position for
  902. * the new values of the timestamps).
  903. */
  904. static void __bfq_requeue_entity(struct bfq_entity *entity)
  905. {
  906. struct bfq_sched_data *sd = entity->sched_data;
  907. struct bfq_service_tree *st = bfq_entity_service_tree(entity);
  908. if (entity == sd->in_service_entity) {
  909. /*
  910. * We are requeueing the current in-service entity,
  911. * which may have to be done for one of the following
  912. * reasons:
  913. * - entity represents the in-service queue, and the
  914. * in-service queue is being requeued after an
  915. * expiration;
  916. * - entity represents a group, and its budget has
  917. * changed because one of its child entities has
  918. * just been either activated or requeued for some
  919. * reason; the timestamps of the entity need then to
  920. * be updated, and the entity needs to be enqueued
  921. * or repositioned accordingly.
  922. *
  923. * In particular, before requeueing, the start time of
  924. * the entity must be moved forward to account for the
  925. * service that the entity has received while in
  926. * service. This is done by the next instructions. The
  927. * finish time will then be updated according to this
  928. * new value of the start time, and to the budget of
  929. * the entity.
  930. */
  931. bfq_calc_finish(entity, entity->service);
  932. entity->start = entity->finish;
  933. /*
  934. * In addition, if the entity had more than one child
  935. * when set in service, then it was not extracted from
  936. * the active tree. This implies that the position of
  937. * the entity in the active tree may need to be
  938. * changed now, because we have just updated the start
  939. * time of the entity, and we will update its finish
  940. * time in a moment (the requeueing is then, more
  941. * precisely, a repositioning in this case). To
  942. * implement this repositioning, we: 1) dequeue the
  943. * entity here, 2) update the finish time and requeue
  944. * the entity according to the new timestamps below.
  945. */
  946. if (entity->tree)
  947. bfq_active_extract(st, entity);
  948. } else { /* The entity is already active, and not in service */
  949. /*
  950. * In this case, this function gets called only if the
  951. * next_in_service entity below this entity has
  952. * changed, and this change has caused the budget of
  953. * this entity to change, which, finally implies that
  954. * the finish time of this entity must be
  955. * updated. Such an update may cause the scheduling,
  956. * i.e., the position in the active tree, of this
  957. * entity to change. We handle this change by: 1)
  958. * dequeueing the entity here, 2) updating the finish
  959. * time and requeueing the entity according to the new
  960. * timestamps below. This is the same approach as the
  961. * non-extracted-entity sub-case above.
  962. */
  963. bfq_active_extract(st, entity);
  964. }
  965. bfq_update_fin_time_enqueue(entity, st, false);
  966. }
  967. static void __bfq_activate_requeue_entity(struct bfq_entity *entity,
  968. struct bfq_sched_data *sd,
  969. bool non_blocking_wait_rq)
  970. {
  971. struct bfq_service_tree *st = bfq_entity_service_tree(entity);
  972. if (sd->in_service_entity == entity || entity->tree == &st->active)
  973. /*
  974. * in service or already queued on the active tree,
  975. * requeue or reposition
  976. */
  977. __bfq_requeue_entity(entity);
  978. else
  979. /*
  980. * Not in service and not queued on its active tree:
  981. * the activity is idle and this is a true activation.
  982. */
  983. __bfq_activate_entity(entity, non_blocking_wait_rq);
  984. }
  985. /**
  986. * bfq_activate_requeue_entity - activate or requeue an entity representing a
  987. * bfq_queue, and activate, requeue or reposition
  988. * all ancestors for which such an update becomes
  989. * necessary.
  990. * @entity: the entity to activate.
  991. * @non_blocking_wait_rq: true if this entity was waiting for a request
  992. * @requeue: true if this is a requeue, which implies that bfqq is
  993. * being expired; thus ALL its ancestors stop being served and must
  994. * therefore be requeued
  995. * @expiration: true if this function is being invoked in the expiration path
  996. * of the in-service queue
  997. */
  998. static void bfq_activate_requeue_entity(struct bfq_entity *entity,
  999. bool non_blocking_wait_rq,
  1000. bool requeue, bool expiration)
  1001. {
  1002. struct bfq_sched_data *sd;
  1003. for_each_entity(entity) {
  1004. sd = entity->sched_data;
  1005. __bfq_activate_requeue_entity(entity, sd, non_blocking_wait_rq);
  1006. if (!bfq_update_next_in_service(sd, entity, expiration) &&
  1007. !requeue)
  1008. break;
  1009. }
  1010. }
  1011. /**
  1012. * __bfq_deactivate_entity - update sched_data and service trees for
  1013. * entity, so as to represent entity as inactive
  1014. * @entity: the entity being deactivated.
  1015. * @ins_into_idle_tree: if false, the entity will not be put into the
  1016. * idle tree.
  1017. *
  1018. * If necessary and allowed, puts entity into the idle tree. NOTE:
  1019. * entity may be on no tree if in service.
  1020. */
  1021. bool __bfq_deactivate_entity(struct bfq_entity *entity, bool ins_into_idle_tree)
  1022. {
  1023. struct bfq_sched_data *sd = entity->sched_data;
  1024. struct bfq_service_tree *st;
  1025. bool is_in_service;
  1026. if (!entity->on_st_or_in_serv) /*
  1027. * entity never activated, or
  1028. * already inactive
  1029. */
  1030. return false;
  1031. /*
  1032. * If we get here, then entity is active, which implies that
  1033. * bfq_group_set_parent has already been invoked for the group
  1034. * represented by entity. Therefore, the field
  1035. * entity->sched_data has been set, and we can safely use it.
  1036. */
  1037. st = bfq_entity_service_tree(entity);
  1038. is_in_service = entity == sd->in_service_entity;
  1039. bfq_calc_finish(entity, entity->service);
  1040. if (is_in_service)
  1041. sd->in_service_entity = NULL;
  1042. else
  1043. /*
  1044. * Non in-service entity: nobody will take care of
  1045. * resetting its service counter on expiration. Do it
  1046. * now.
  1047. */
  1048. entity->service = 0;
  1049. if (entity->tree == &st->active)
  1050. bfq_active_extract(st, entity);
  1051. else if (!is_in_service && entity->tree == &st->idle)
  1052. bfq_idle_extract(st, entity);
  1053. if (!ins_into_idle_tree || !bfq_gt(entity->finish, st->vtime))
  1054. bfq_forget_entity(st, entity, is_in_service);
  1055. else
  1056. bfq_idle_insert(st, entity);
  1057. return true;
  1058. }
  1059. /**
  1060. * bfq_deactivate_entity - deactivate an entity representing a bfq_queue.
  1061. * @entity: the entity to deactivate.
  1062. * @ins_into_idle_tree: true if the entity can be put into the idle tree
  1063. * @expiration: true if this function is being invoked in the expiration path
  1064. * of the in-service queue
  1065. */
  1066. static void bfq_deactivate_entity(struct bfq_entity *entity,
  1067. bool ins_into_idle_tree,
  1068. bool expiration)
  1069. {
  1070. struct bfq_sched_data *sd;
  1071. struct bfq_entity *parent = NULL;
  1072. for_each_entity_safe(entity, parent) {
  1073. sd = entity->sched_data;
  1074. if (!__bfq_deactivate_entity(entity, ins_into_idle_tree)) {
  1075. /*
  1076. * entity is not in any tree any more, so
  1077. * this deactivation is a no-op, and there is
  1078. * nothing to change for upper-level entities
  1079. * (in case of expiration, this can never
  1080. * happen).
  1081. */
  1082. return;
  1083. }
  1084. if (sd->next_in_service == entity)
  1085. /*
  1086. * entity was the next_in_service entity,
  1087. * then, since entity has just been
  1088. * deactivated, a new one must be found.
  1089. */
  1090. bfq_update_next_in_service(sd, NULL, expiration);
  1091. if (sd->next_in_service || sd->in_service_entity) {
  1092. /*
  1093. * The parent entity is still active, because
  1094. * either next_in_service or in_service_entity
  1095. * is not NULL. So, no further upwards
  1096. * deactivation must be performed. Yet,
  1097. * next_in_service has changed. Then the
  1098. * schedule does need to be updated upwards.
  1099. *
  1100. * NOTE If in_service_entity is not NULL, then
  1101. * next_in_service may happen to be NULL,
  1102. * although the parent entity is evidently
  1103. * active. This happens if 1) the entity
  1104. * pointed by in_service_entity is the only
  1105. * active entity in the parent entity, and 2)
  1106. * according to the definition of
  1107. * next_in_service, the in_service_entity
  1108. * cannot be considered as
  1109. * next_in_service. See the comments on the
  1110. * definition of next_in_service for details.
  1111. */
  1112. break;
  1113. }
  1114. /*
  1115. * If we get here, then the parent is no more
  1116. * backlogged and we need to propagate the
  1117. * deactivation upwards. Thus let the loop go on.
  1118. */
  1119. /*
  1120. * Also let parent be queued into the idle tree on
  1121. * deactivation, to preserve service guarantees, and
  1122. * assuming that who invoked this function does not
  1123. * need parent entities too to be removed completely.
  1124. */
  1125. ins_into_idle_tree = true;
  1126. }
  1127. /*
  1128. * If the deactivation loop is fully executed, then there are
  1129. * no more entities to touch and next loop is not executed at
  1130. * all. Otherwise, requeue remaining entities if they are
  1131. * about to stop receiving service, or reposition them if this
  1132. * is not the case.
  1133. */
  1134. entity = parent;
  1135. for_each_entity(entity) {
  1136. /*
  1137. * Invoke __bfq_requeue_entity on entity, even if
  1138. * already active, to requeue/reposition it in the
  1139. * active tree (because sd->next_in_service has
  1140. * changed)
  1141. */
  1142. __bfq_requeue_entity(entity);
  1143. sd = entity->sched_data;
  1144. if (!bfq_update_next_in_service(sd, entity, expiration) &&
  1145. !expiration)
  1146. /*
  1147. * next_in_service unchanged or not causing
  1148. * any change in entity->parent->sd, and no
  1149. * requeueing needed for expiration: stop
  1150. * here.
  1151. */
  1152. break;
  1153. }
  1154. }
  1155. /**
  1156. * bfq_calc_vtime_jump - compute the value to which the vtime should jump,
  1157. * if needed, to have at least one entity eligible.
  1158. * @st: the service tree to act upon.
  1159. *
  1160. * Assumes that st is not empty.
  1161. */
  1162. static u64 bfq_calc_vtime_jump(struct bfq_service_tree *st)
  1163. {
  1164. struct bfq_entity *root_entity = bfq_root_active_entity(&st->active);
  1165. if (bfq_gt(root_entity->min_start, st->vtime))
  1166. return root_entity->min_start;
  1167. return st->vtime;
  1168. }
  1169. static void bfq_update_vtime(struct bfq_service_tree *st, u64 new_value)
  1170. {
  1171. if (new_value > st->vtime) {
  1172. st->vtime = new_value;
  1173. bfq_forget_idle(st);
  1174. }
  1175. }
  1176. /**
  1177. * bfq_first_active_entity - find the eligible entity with
  1178. * the smallest finish time
  1179. * @st: the service tree to select from.
  1180. * @vtime: the system virtual to use as a reference for eligibility
  1181. *
  1182. * This function searches the first schedulable entity, starting from the
  1183. * root of the tree and going on the left every time on this side there is
  1184. * a subtree with at least one eligible (start <= vtime) entity. The path on
  1185. * the right is followed only if a) the left subtree contains no eligible
  1186. * entities and b) no eligible entity has been found yet.
  1187. */
  1188. static struct bfq_entity *bfq_first_active_entity(struct bfq_service_tree *st,
  1189. u64 vtime)
  1190. {
  1191. struct bfq_entity *entry, *first = NULL;
  1192. struct rb_node *node = st->active.rb_node;
  1193. while (node) {
  1194. entry = rb_entry(node, struct bfq_entity, rb_node);
  1195. left:
  1196. if (!bfq_gt(entry->start, vtime))
  1197. first = entry;
  1198. if (node->rb_left) {
  1199. entry = rb_entry(node->rb_left,
  1200. struct bfq_entity, rb_node);
  1201. if (!bfq_gt(entry->min_start, vtime)) {
  1202. node = node->rb_left;
  1203. goto left;
  1204. }
  1205. }
  1206. if (first)
  1207. break;
  1208. node = node->rb_right;
  1209. }
  1210. return first;
  1211. }
  1212. /**
  1213. * __bfq_lookup_next_entity - return the first eligible entity in @st.
  1214. * @st: the service tree.
  1215. *
  1216. * If there is no in-service entity for the sched_data st belongs to,
  1217. * then return the entity that will be set in service if:
  1218. * 1) the parent entity this st belongs to is set in service;
  1219. * 2) no entity belonging to such parent entity undergoes a state change
  1220. * that would influence the timestamps of the entity (e.g., becomes idle,
  1221. * becomes backlogged, changes its budget, ...).
  1222. *
  1223. * In this first case, update the virtual time in @st too (see the
  1224. * comments on this update inside the function).
  1225. *
  1226. * In contrast, if there is an in-service entity, then return the
  1227. * entity that would be set in service if not only the above
  1228. * conditions, but also the next one held true: the currently
  1229. * in-service entity, on expiration,
  1230. * 1) gets a finish time equal to the current one, or
  1231. * 2) is not eligible any more, or
  1232. * 3) is idle.
  1233. */
  1234. static struct bfq_entity *
  1235. __bfq_lookup_next_entity(struct bfq_service_tree *st, bool in_service)
  1236. {
  1237. struct bfq_entity *entity;
  1238. u64 new_vtime;
  1239. if (RB_EMPTY_ROOT(&st->active))
  1240. return NULL;
  1241. /*
  1242. * Get the value of the system virtual time for which at
  1243. * least one entity is eligible.
  1244. */
  1245. new_vtime = bfq_calc_vtime_jump(st);
  1246. /*
  1247. * If there is no in-service entity for the sched_data this
  1248. * active tree belongs to, then push the system virtual time
  1249. * up to the value that guarantees that at least one entity is
  1250. * eligible. If, instead, there is an in-service entity, then
  1251. * do not make any such update, because there is already an
  1252. * eligible entity, namely the in-service one (even if the
  1253. * entity is not on st, because it was extracted when set in
  1254. * service).
  1255. */
  1256. if (!in_service)
  1257. bfq_update_vtime(st, new_vtime);
  1258. entity = bfq_first_active_entity(st, new_vtime);
  1259. return entity;
  1260. }
  1261. /**
  1262. * bfq_lookup_next_entity - return the first eligible entity in @sd.
  1263. * @sd: the sched_data.
  1264. * @expiration: true if we are on the expiration path of the in-service queue
  1265. *
  1266. * This function is invoked when there has been a change in the trees
  1267. * for sd, and we need to know what is the new next entity to serve
  1268. * after this change.
  1269. */
  1270. static struct bfq_entity *bfq_lookup_next_entity(struct bfq_sched_data *sd,
  1271. bool expiration)
  1272. {
  1273. struct bfq_service_tree *st = sd->service_tree;
  1274. struct bfq_service_tree *idle_class_st = st + (BFQ_IOPRIO_CLASSES - 1);
  1275. struct bfq_entity *entity = NULL;
  1276. int class_idx = 0;
  1277. /*
  1278. * Choose from idle class, if needed to guarantee a minimum
  1279. * bandwidth to this class (and if there is some active entity
  1280. * in idle class). This should also mitigate
  1281. * priority-inversion problems in case a low priority task is
  1282. * holding file system resources.
  1283. */
  1284. if (time_is_before_jiffies(sd->bfq_class_idle_last_service +
  1285. BFQ_CL_IDLE_TIMEOUT)) {
  1286. if (!RB_EMPTY_ROOT(&idle_class_st->active))
  1287. class_idx = BFQ_IOPRIO_CLASSES - 1;
  1288. /* About to be served if backlogged, or not yet backlogged */
  1289. sd->bfq_class_idle_last_service = jiffies;
  1290. }
  1291. /*
  1292. * Find the next entity to serve for the highest-priority
  1293. * class, unless the idle class needs to be served.
  1294. */
  1295. for (; class_idx < BFQ_IOPRIO_CLASSES; class_idx++) {
  1296. /*
  1297. * If expiration is true, then bfq_lookup_next_entity
  1298. * is being invoked as a part of the expiration path
  1299. * of the in-service queue. In this case, even if
  1300. * sd->in_service_entity is not NULL,
  1301. * sd->in_service_entity at this point is actually not
  1302. * in service any more, and, if needed, has already
  1303. * been properly queued or requeued into the right
  1304. * tree. The reason why sd->in_service_entity is still
  1305. * not NULL here, even if expiration is true, is that
  1306. * sd->in_service_entity is reset as a last step in the
  1307. * expiration path. So, if expiration is true, tell
  1308. * __bfq_lookup_next_entity that there is no
  1309. * sd->in_service_entity.
  1310. */
  1311. entity = __bfq_lookup_next_entity(st + class_idx,
  1312. sd->in_service_entity &&
  1313. !expiration);
  1314. if (entity)
  1315. break;
  1316. }
  1317. if (!entity)
  1318. return NULL;
  1319. return entity;
  1320. }
  1321. bool next_queue_may_preempt(struct bfq_data *bfqd)
  1322. {
  1323. struct bfq_sched_data *sd = &bfqd->root_group->sched_data;
  1324. return sd->next_in_service != sd->in_service_entity;
  1325. }
  1326. /*
  1327. * Get next queue for service.
  1328. */
  1329. struct bfq_queue *bfq_get_next_queue(struct bfq_data *bfqd)
  1330. {
  1331. struct bfq_entity *entity = NULL;
  1332. struct bfq_sched_data *sd;
  1333. struct bfq_queue *bfqq;
  1334. if (bfq_tot_busy_queues(bfqd) == 0)
  1335. return NULL;
  1336. /*
  1337. * Traverse the path from the root to the leaf entity to
  1338. * serve. Set in service all the entities visited along the
  1339. * way.
  1340. */
  1341. sd = &bfqd->root_group->sched_data;
  1342. for (; sd ; sd = entity->my_sched_data) {
  1343. /*
  1344. * WARNING. We are about to set the in-service entity
  1345. * to sd->next_in_service, i.e., to the (cached) value
  1346. * returned by bfq_lookup_next_entity(sd) the last
  1347. * time it was invoked, i.e., the last time when the
  1348. * service order in sd changed as a consequence of the
  1349. * activation or deactivation of an entity. In this
  1350. * respect, if we execute bfq_lookup_next_entity(sd)
  1351. * in this very moment, it may, although with low
  1352. * probability, yield a different entity than that
  1353. * pointed to by sd->next_in_service. This rare event
  1354. * happens in case there was no CLASS_IDLE entity to
  1355. * serve for sd when bfq_lookup_next_entity(sd) was
  1356. * invoked for the last time, while there is now one
  1357. * such entity.
  1358. *
  1359. * If the above event happens, then the scheduling of
  1360. * such entity in CLASS_IDLE is postponed until the
  1361. * service of the sd->next_in_service entity
  1362. * finishes. In fact, when the latter is expired,
  1363. * bfq_lookup_next_entity(sd) gets called again,
  1364. * exactly to update sd->next_in_service.
  1365. */
  1366. /* Make next_in_service entity become in_service_entity */
  1367. entity = sd->next_in_service;
  1368. sd->in_service_entity = entity;
  1369. /*
  1370. * If entity is no longer a candidate for next
  1371. * service, then it must be extracted from its active
  1372. * tree, so as to make sure that it won't be
  1373. * considered when computing next_in_service. See the
  1374. * comments on the function
  1375. * bfq_no_longer_next_in_service() for details.
  1376. */
  1377. if (bfq_no_longer_next_in_service(entity))
  1378. bfq_active_extract(bfq_entity_service_tree(entity),
  1379. entity);
  1380. /*
  1381. * Even if entity is not to be extracted according to
  1382. * the above check, a descendant entity may get
  1383. * extracted in one of the next iterations of this
  1384. * loop. Such an event could cause a change in
  1385. * next_in_service for the level of the descendant
  1386. * entity, and thus possibly back to this level.
  1387. *
  1388. * However, we cannot perform the resulting needed
  1389. * update of next_in_service for this level before the
  1390. * end of the whole loop, because, to know which is
  1391. * the correct next-to-serve candidate entity for each
  1392. * level, we need first to find the leaf entity to set
  1393. * in service. In fact, only after we know which is
  1394. * the next-to-serve leaf entity, we can discover
  1395. * whether the parent entity of the leaf entity
  1396. * becomes the next-to-serve, and so on.
  1397. */
  1398. }
  1399. bfqq = bfq_entity_to_bfqq(entity);
  1400. /*
  1401. * We can finally update all next-to-serve entities along the
  1402. * path from the leaf entity just set in service to the root.
  1403. */
  1404. for_each_entity(entity) {
  1405. struct bfq_sched_data *sd = entity->sched_data;
  1406. if (!bfq_update_next_in_service(sd, NULL, false))
  1407. break;
  1408. }
  1409. return bfqq;
  1410. }
  1411. /* returns true if the in-service queue gets freed */
  1412. bool __bfq_bfqd_reset_in_service(struct bfq_data *bfqd)
  1413. {
  1414. struct bfq_queue *in_serv_bfqq = bfqd->in_service_queue;
  1415. struct bfq_entity *in_serv_entity = &in_serv_bfqq->entity;
  1416. struct bfq_entity *entity = in_serv_entity;
  1417. bfq_clear_bfqq_wait_request(in_serv_bfqq);
  1418. hrtimer_try_to_cancel(&bfqd->idle_slice_timer);
  1419. bfqd->in_service_queue = NULL;
  1420. /*
  1421. * When this function is called, all in-service entities have
  1422. * been properly deactivated or requeued, so we can safely
  1423. * execute the final step: reset in_service_entity along the
  1424. * path from entity to the root.
  1425. */
  1426. for_each_entity(entity)
  1427. entity->sched_data->in_service_entity = NULL;
  1428. /*
  1429. * in_serv_entity is no longer in service, so, if it is in no
  1430. * service tree either, then release the service reference to
  1431. * the queue it represents (taken with bfq_get_entity).
  1432. */
  1433. if (!in_serv_entity->on_st_or_in_serv) {
  1434. /*
  1435. * If no process is referencing in_serv_bfqq any
  1436. * longer, then the service reference may be the only
  1437. * reference to the queue. If this is the case, then
  1438. * bfqq gets freed here.
  1439. */
  1440. int ref = in_serv_bfqq->ref;
  1441. bfq_put_queue(in_serv_bfqq);
  1442. if (ref == 1)
  1443. return true;
  1444. }
  1445. return false;
  1446. }
  1447. void bfq_deactivate_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq,
  1448. bool ins_into_idle_tree, bool expiration)
  1449. {
  1450. struct bfq_entity *entity = &bfqq->entity;
  1451. bfq_deactivate_entity(entity, ins_into_idle_tree, expiration);
  1452. }
  1453. void bfq_activate_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq)
  1454. {
  1455. struct bfq_entity *entity = &bfqq->entity;
  1456. bfq_activate_requeue_entity(entity, bfq_bfqq_non_blocking_wait_rq(bfqq),
  1457. false, false);
  1458. bfq_clear_bfqq_non_blocking_wait_rq(bfqq);
  1459. }
  1460. void bfq_requeue_bfqq(struct bfq_data *bfqd, struct bfq_queue *bfqq,
  1461. bool expiration)
  1462. {
  1463. struct bfq_entity *entity = &bfqq->entity;
  1464. bfq_activate_requeue_entity(entity, false,
  1465. bfqq == bfqd->in_service_queue, expiration);
  1466. }
  1467. /*
  1468. * Called when the bfqq no longer has requests pending, remove it from
  1469. * the service tree. As a special case, it can be invoked during an
  1470. * expiration.
  1471. */
  1472. void bfq_del_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq,
  1473. bool expiration)
  1474. {
  1475. bfq_log_bfqq(bfqd, bfqq, "del from busy");
  1476. bfq_clear_bfqq_busy(bfqq);
  1477. bfqd->busy_queues[bfqq->ioprio_class - 1]--;
  1478. if (bfqq->wr_coeff > 1)
  1479. bfqd->wr_busy_queues--;
  1480. bfqg_stats_update_dequeue(bfqq_group(bfqq));
  1481. bfq_deactivate_bfqq(bfqd, bfqq, true, expiration);
  1482. if (!bfqq->dispatched)
  1483. bfq_weights_tree_remove(bfqd, bfqq);
  1484. }
  1485. /*
  1486. * Called when an inactive queue receives a new request.
  1487. */
  1488. void bfq_add_bfqq_busy(struct bfq_data *bfqd, struct bfq_queue *bfqq)
  1489. {
  1490. bfq_log_bfqq(bfqd, bfqq, "add to busy");
  1491. bfq_activate_bfqq(bfqd, bfqq);
  1492. bfq_mark_bfqq_busy(bfqq);
  1493. bfqd->busy_queues[bfqq->ioprio_class - 1]++;
  1494. if (!bfqq->dispatched)
  1495. if (bfqq->wr_coeff == 1)
  1496. bfq_weights_tree_add(bfqd, bfqq,
  1497. &bfqd->queue_weights_tree);
  1498. if (bfqq->wr_coeff > 1)
  1499. bfqd->wr_busy_queues++;
  1500. }