elevator.c 26 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168
  1. /*
  2. * Block device elevator/IO-scheduler.
  3. *
  4. * Copyright (C) 2000 Andrea Arcangeli <andrea@suse.de> SuSE
  5. *
  6. * 30042000 Jens Axboe <axboe@kernel.dk> :
  7. *
  8. * Split the elevator a bit so that it is possible to choose a different
  9. * one or even write a new "plug in". There are three pieces:
  10. * - elevator_fn, inserts a new request in the queue list
  11. * - elevator_merge_fn, decides whether a new buffer can be merged with
  12. * an existing request
  13. * - elevator_dequeue_fn, called when a request is taken off the active list
  14. *
  15. * 20082000 Dave Jones <davej@suse.de> :
  16. * Removed tests for max-bomb-segments, which was breaking elvtune
  17. * when run without -bN
  18. *
  19. * Jens:
  20. * - Rework again to work with bio instead of buffer_heads
  21. * - loose bi_dev comparisons, partition handling is right now
  22. * - completely modularize elevator setup and teardown
  23. *
  24. */
  25. #include <linux/kernel.h>
  26. #include <linux/fs.h>
  27. #include <linux/blkdev.h>
  28. #include <linux/elevator.h>
  29. #include <linux/bio.h>
  30. #include <linux/module.h>
  31. #include <linux/slab.h>
  32. #include <linux/init.h>
  33. #include <linux/compiler.h>
  34. #include <linux/blktrace_api.h>
  35. #include <linux/hash.h>
  36. #include <linux/uaccess.h>
  37. #include <linux/pm_runtime.h>
  38. #include <trace/events/block.h>
  39. #include "blk.h"
  40. static DEFINE_SPINLOCK(elv_list_lock);
  41. static LIST_HEAD(elv_list);
  42. /*
  43. * Merge hash stuff.
  44. */
  45. static const int elv_hash_shift = 6;
  46. #define ELV_HASH_BLOCK(sec) ((sec) >> 3)
  47. #define ELV_HASH_FN(sec) \
  48. (hash_long(ELV_HASH_BLOCK((sec)), elv_hash_shift))
  49. #define ELV_HASH_ENTRIES (1 << elv_hash_shift)
  50. #define rq_hash_key(rq) (blk_rq_pos(rq) + blk_rq_sectors(rq))
  51. /*
  52. * Query io scheduler to see if the current process issuing bio may be
  53. * merged with rq.
  54. */
  55. static int elv_iosched_allow_merge(struct request *rq, struct bio *bio)
  56. {
  57. struct request_queue *q = rq->q;
  58. struct elevator_queue *e = q->elevator;
  59. if (e->type->ops.elevator_allow_merge_fn)
  60. return e->type->ops.elevator_allow_merge_fn(q, rq, bio);
  61. return 1;
  62. }
  63. /*
  64. * can we safely merge with this request?
  65. */
  66. bool elv_rq_merge_ok(struct request *rq, struct bio *bio)
  67. {
  68. if (!rq_mergeable(rq))
  69. return 0;
  70. /*
  71. * Don't merge file system requests and discard requests
  72. */
  73. if ((bio->bi_rw & REQ_DISCARD) != (rq->bio->bi_rw & REQ_DISCARD))
  74. return 0;
  75. /*
  76. * Don't merge discard requests and secure discard requests
  77. */
  78. if ((bio->bi_rw & REQ_SECURE) != (rq->bio->bi_rw & REQ_SECURE))
  79. return 0;
  80. /*
  81. * Don't merge sanitize requests
  82. */
  83. if ((bio->bi_rw & REQ_SANITIZE) != (rq->bio->bi_rw & REQ_SANITIZE))
  84. return 0;
  85. /*
  86. * different data direction or already started, don't merge
  87. */
  88. if (bio_data_dir(bio) != rq_data_dir(rq))
  89. return 0;
  90. /*
  91. * must be same device and not a special request
  92. */
  93. if (rq->rq_disk != bio->bi_bdev->bd_disk || rq->special)
  94. return 0;
  95. /*
  96. * only merge integrity protected bio into ditto rq
  97. */
  98. if (bio_integrity(bio) != blk_integrity_rq(rq))
  99. return 0;
  100. if (!elv_iosched_allow_merge(rq, bio))
  101. return 0;
  102. return 1;
  103. }
  104. EXPORT_SYMBOL(elv_rq_merge_ok);
  105. static struct elevator_type *elevator_find(const char *name)
  106. {
  107. struct elevator_type *e;
  108. list_for_each_entry(e, &elv_list, list) {
  109. if (!strcmp(e->elevator_name, name))
  110. return e;
  111. }
  112. return NULL;
  113. }
  114. static void elevator_put(struct elevator_type *e)
  115. {
  116. module_put(e->elevator_owner);
  117. }
  118. static struct elevator_type *elevator_get(const char *name)
  119. {
  120. struct elevator_type *e;
  121. spin_lock(&elv_list_lock);
  122. e = elevator_find(name);
  123. if (!e) {
  124. spin_unlock(&elv_list_lock);
  125. request_module("%s-iosched", name);
  126. spin_lock(&elv_list_lock);
  127. e = elevator_find(name);
  128. }
  129. if (e && !try_module_get(e->elevator_owner))
  130. e = NULL;
  131. spin_unlock(&elv_list_lock);
  132. return e;
  133. }
  134. static int elevator_init_queue(struct request_queue *q,
  135. struct elevator_queue *eq)
  136. {
  137. eq->elevator_data = eq->type->ops.elevator_init_fn(q);
  138. if (eq->elevator_data)
  139. return 0;
  140. return -ENOMEM;
  141. }
  142. static char chosen_elevator[ELV_NAME_MAX];
  143. static int __init elevator_setup(char *str)
  144. {
  145. /*
  146. * Be backwards-compatible with previous kernels, so users
  147. * won't get the wrong elevator.
  148. */
  149. strncpy(chosen_elevator, str, sizeof(chosen_elevator) - 1);
  150. return 1;
  151. }
  152. __setup("elevator=", elevator_setup);
  153. static struct kobj_type elv_ktype;
  154. static struct elevator_queue *elevator_alloc(struct request_queue *q,
  155. struct elevator_type *e)
  156. {
  157. struct elevator_queue *eq;
  158. int i;
  159. eq = kmalloc_node(sizeof(*eq), GFP_KERNEL | __GFP_ZERO, q->node);
  160. if (unlikely(!eq))
  161. goto err;
  162. eq->type = e;
  163. kobject_init(&eq->kobj, &elv_ktype);
  164. mutex_init(&eq->sysfs_lock);
  165. eq->hash = kmalloc_node(sizeof(struct hlist_head) * ELV_HASH_ENTRIES,
  166. GFP_KERNEL, q->node);
  167. if (!eq->hash)
  168. goto err;
  169. for (i = 0; i < ELV_HASH_ENTRIES; i++)
  170. INIT_HLIST_HEAD(&eq->hash[i]);
  171. return eq;
  172. err:
  173. kfree(eq);
  174. elevator_put(e);
  175. return NULL;
  176. }
  177. static void elevator_release(struct kobject *kobj)
  178. {
  179. struct elevator_queue *e;
  180. e = container_of(kobj, struct elevator_queue, kobj);
  181. elevator_put(e->type);
  182. kfree(e->hash);
  183. kfree(e);
  184. }
  185. int elevator_init(struct request_queue *q, char *name)
  186. {
  187. struct elevator_type *e = NULL;
  188. struct elevator_queue *eq;
  189. int err;
  190. if (unlikely(q->elevator))
  191. return 0;
  192. INIT_LIST_HEAD(&q->queue_head);
  193. q->last_merge = NULL;
  194. q->end_sector = 0;
  195. q->boundary_rq = NULL;
  196. if (name) {
  197. e = elevator_get(name);
  198. if (!e)
  199. return -EINVAL;
  200. }
  201. if (!e && *chosen_elevator) {
  202. e = elevator_get(chosen_elevator);
  203. if (!e)
  204. printk(KERN_ERR "I/O scheduler %s not found\n",
  205. chosen_elevator);
  206. }
  207. if (!e) {
  208. e = elevator_get(CONFIG_DEFAULT_IOSCHED);
  209. if (!e) {
  210. printk(KERN_ERR
  211. "Default I/O scheduler not found. " \
  212. "Using noop.\n");
  213. e = elevator_get("noop");
  214. }
  215. }
  216. eq = elevator_alloc(q, e);
  217. if (!eq)
  218. return -ENOMEM;
  219. err = elevator_init_queue(q, eq);
  220. if (err) {
  221. kobject_put(&eq->kobj);
  222. return err;
  223. }
  224. q->elevator = eq;
  225. return 0;
  226. }
  227. EXPORT_SYMBOL(elevator_init);
  228. void elevator_exit(struct elevator_queue *e)
  229. {
  230. mutex_lock(&e->sysfs_lock);
  231. if (e->type->ops.elevator_exit_fn)
  232. e->type->ops.elevator_exit_fn(e);
  233. mutex_unlock(&e->sysfs_lock);
  234. kobject_put(&e->kobj);
  235. }
  236. EXPORT_SYMBOL(elevator_exit);
  237. static inline void __elv_rqhash_del(struct request *rq)
  238. {
  239. hlist_del_init(&rq->hash);
  240. }
  241. static void elv_rqhash_del(struct request_queue *q, struct request *rq)
  242. {
  243. if (ELV_ON_HASH(rq))
  244. __elv_rqhash_del(rq);
  245. }
  246. static void elv_rqhash_add(struct request_queue *q, struct request *rq)
  247. {
  248. struct elevator_queue *e = q->elevator;
  249. BUG_ON(ELV_ON_HASH(rq));
  250. hlist_add_head(&rq->hash, &e->hash[ELV_HASH_FN(rq_hash_key(rq))]);
  251. }
  252. static void elv_rqhash_reposition(struct request_queue *q, struct request *rq)
  253. {
  254. __elv_rqhash_del(rq);
  255. elv_rqhash_add(q, rq);
  256. }
  257. static struct request *elv_rqhash_find(struct request_queue *q, sector_t offset)
  258. {
  259. struct elevator_queue *e = q->elevator;
  260. struct hlist_head *hash_list = &e->hash[ELV_HASH_FN(offset)];
  261. struct hlist_node *entry, *next;
  262. struct request *rq;
  263. hlist_for_each_entry_safe(rq, entry, next, hash_list, hash) {
  264. BUG_ON(!ELV_ON_HASH(rq));
  265. if (unlikely(!rq_mergeable(rq))) {
  266. __elv_rqhash_del(rq);
  267. continue;
  268. }
  269. if (rq_hash_key(rq) == offset)
  270. return rq;
  271. }
  272. return NULL;
  273. }
  274. /*
  275. * RB-tree support functions for inserting/lookup/removal of requests
  276. * in a sorted RB tree.
  277. */
  278. void elv_rb_add(struct rb_root *root, struct request *rq)
  279. {
  280. struct rb_node **p = &root->rb_node;
  281. struct rb_node *parent = NULL;
  282. struct request *__rq;
  283. while (*p) {
  284. parent = *p;
  285. __rq = rb_entry(parent, struct request, rb_node);
  286. if (blk_rq_pos(rq) < blk_rq_pos(__rq))
  287. p = &(*p)->rb_left;
  288. else if (blk_rq_pos(rq) >= blk_rq_pos(__rq))
  289. p = &(*p)->rb_right;
  290. }
  291. rb_link_node(&rq->rb_node, parent, p);
  292. rb_insert_color(&rq->rb_node, root);
  293. }
  294. EXPORT_SYMBOL(elv_rb_add);
  295. void elv_rb_del(struct rb_root *root, struct request *rq)
  296. {
  297. BUG_ON(RB_EMPTY_NODE(&rq->rb_node));
  298. rb_erase(&rq->rb_node, root);
  299. RB_CLEAR_NODE(&rq->rb_node);
  300. }
  301. EXPORT_SYMBOL(elv_rb_del);
  302. struct request *elv_rb_find(struct rb_root *root, sector_t sector)
  303. {
  304. struct rb_node *n = root->rb_node;
  305. struct request *rq;
  306. while (n) {
  307. rq = rb_entry(n, struct request, rb_node);
  308. if (sector < blk_rq_pos(rq))
  309. n = n->rb_left;
  310. else if (sector > blk_rq_pos(rq))
  311. n = n->rb_right;
  312. else
  313. return rq;
  314. }
  315. return NULL;
  316. }
  317. EXPORT_SYMBOL(elv_rb_find);
  318. /*
  319. * Insert rq into dispatch queue of q. Queue lock must be held on
  320. * entry. rq is sort instead into the dispatch queue. To be used by
  321. * specific elevators.
  322. */
  323. void elv_dispatch_sort(struct request_queue *q, struct request *rq)
  324. {
  325. sector_t boundary;
  326. struct list_head *entry;
  327. int stop_flags;
  328. if (q->last_merge == rq)
  329. q->last_merge = NULL;
  330. elv_rqhash_del(q, rq);
  331. q->nr_sorted--;
  332. boundary = q->end_sector;
  333. stop_flags = REQ_SOFTBARRIER | REQ_STARTED;
  334. list_for_each_prev(entry, &q->queue_head) {
  335. struct request *pos = list_entry_rq(entry);
  336. if ((rq->cmd_flags & REQ_DISCARD) !=
  337. (pos->cmd_flags & REQ_DISCARD))
  338. break;
  339. if (rq_data_dir(rq) != rq_data_dir(pos))
  340. break;
  341. if (pos->cmd_flags & stop_flags)
  342. break;
  343. if (blk_rq_pos(rq) >= boundary) {
  344. if (blk_rq_pos(pos) < boundary)
  345. continue;
  346. } else {
  347. if (blk_rq_pos(pos) >= boundary)
  348. break;
  349. }
  350. if (blk_rq_pos(rq) >= blk_rq_pos(pos))
  351. break;
  352. }
  353. list_add(&rq->queuelist, entry);
  354. }
  355. EXPORT_SYMBOL(elv_dispatch_sort);
  356. /*
  357. * Insert rq into dispatch queue of q. Queue lock must be held on
  358. * entry. rq is added to the back of the dispatch queue. To be used by
  359. * specific elevators.
  360. */
  361. void elv_dispatch_add_tail(struct request_queue *q, struct request *rq)
  362. {
  363. if (q->last_merge == rq)
  364. q->last_merge = NULL;
  365. elv_rqhash_del(q, rq);
  366. q->nr_sorted--;
  367. q->end_sector = rq_end_sector(rq);
  368. q->boundary_rq = rq;
  369. list_add_tail(&rq->queuelist, &q->queue_head);
  370. }
  371. EXPORT_SYMBOL(elv_dispatch_add_tail);
  372. int elv_merge(struct request_queue *q, struct request **req, struct bio *bio)
  373. {
  374. struct elevator_queue *e = q->elevator;
  375. struct request *__rq;
  376. int ret;
  377. /*
  378. * Levels of merges:
  379. * nomerges: No merges at all attempted
  380. * noxmerges: Only simple one-hit cache try
  381. * merges: All merge tries attempted
  382. */
  383. if (blk_queue_nomerges(q))
  384. return ELEVATOR_NO_MERGE;
  385. /*
  386. * First try one-hit cache.
  387. */
  388. if (q->last_merge && elv_rq_merge_ok(q->last_merge, bio)) {
  389. ret = blk_try_merge(q->last_merge, bio);
  390. if (ret != ELEVATOR_NO_MERGE) {
  391. *req = q->last_merge;
  392. return ret;
  393. }
  394. }
  395. if (blk_queue_noxmerges(q))
  396. return ELEVATOR_NO_MERGE;
  397. /*
  398. * See if our hash lookup can find a potential backmerge.
  399. */
  400. __rq = elv_rqhash_find(q, bio->bi_sector);
  401. if (__rq && elv_rq_merge_ok(__rq, bio)) {
  402. *req = __rq;
  403. return ELEVATOR_BACK_MERGE;
  404. }
  405. if (e->type->ops.elevator_merge_fn)
  406. return e->type->ops.elevator_merge_fn(q, req, bio);
  407. return ELEVATOR_NO_MERGE;
  408. }
  409. /*
  410. * Attempt to do an insertion back merge. Only check for the case where
  411. * we can append 'rq' to an existing request, so we can throw 'rq' away
  412. * afterwards.
  413. *
  414. * Returns true if we merged, false otherwise
  415. */
  416. static bool elv_attempt_insert_merge(struct request_queue *q,
  417. struct request *rq)
  418. {
  419. struct request *__rq;
  420. if (blk_queue_nomerges(q))
  421. return false;
  422. /*
  423. * First try one-hit cache.
  424. */
  425. if (q->last_merge && blk_attempt_req_merge(q, q->last_merge, rq))
  426. return true;
  427. if (blk_queue_noxmerges(q))
  428. return false;
  429. /*
  430. * See if our hash lookup can find a potential backmerge.
  431. */
  432. __rq = elv_rqhash_find(q, blk_rq_pos(rq));
  433. if (__rq && blk_attempt_req_merge(q, __rq, rq))
  434. return true;
  435. return false;
  436. }
  437. void elv_merged_request(struct request_queue *q, struct request *rq, int type)
  438. {
  439. struct elevator_queue *e = q->elevator;
  440. if (e->type->ops.elevator_merged_fn)
  441. e->type->ops.elevator_merged_fn(q, rq, type);
  442. if (type == ELEVATOR_BACK_MERGE)
  443. elv_rqhash_reposition(q, rq);
  444. q->last_merge = rq;
  445. }
  446. void elv_merge_requests(struct request_queue *q, struct request *rq,
  447. struct request *next)
  448. {
  449. struct elevator_queue *e = q->elevator;
  450. const int next_sorted = next->cmd_flags & REQ_SORTED;
  451. if (next_sorted && e->type->ops.elevator_merge_req_fn)
  452. e->type->ops.elevator_merge_req_fn(q, rq, next);
  453. elv_rqhash_reposition(q, rq);
  454. if (next_sorted) {
  455. elv_rqhash_del(q, next);
  456. q->nr_sorted--;
  457. }
  458. q->last_merge = rq;
  459. }
  460. void elv_bio_merged(struct request_queue *q, struct request *rq,
  461. struct bio *bio)
  462. {
  463. struct elevator_queue *e = q->elevator;
  464. if (e->type->ops.elevator_bio_merged_fn)
  465. e->type->ops.elevator_bio_merged_fn(q, rq, bio);
  466. }
  467. #ifdef CONFIG_PM_RUNTIME
  468. static void blk_pm_requeue_request(struct request *rq)
  469. {
  470. if (rq->q->dev && !(rq->cmd_flags & REQ_PM))
  471. rq->q->nr_pending--;
  472. }
  473. static void blk_pm_add_request(struct request_queue *q, struct request *rq)
  474. {
  475. if (q->dev && !(rq->cmd_flags & REQ_PM) && q->nr_pending++ == 0 &&
  476. (q->rpm_status == RPM_SUSPENDED || q->rpm_status == RPM_SUSPENDING))
  477. pm_request_resume(q->dev);
  478. }
  479. #else
  480. static inline void blk_pm_requeue_request(struct request *rq) {}
  481. static inline void blk_pm_add_request(struct request_queue *q,
  482. struct request *rq)
  483. {
  484. }
  485. #endif
  486. void elv_requeue_request(struct request_queue *q, struct request *rq)
  487. {
  488. /*
  489. * it already went through dequeue, we need to decrement the
  490. * in_flight count again
  491. */
  492. if (blk_account_rq(rq)) {
  493. q->in_flight[rq_is_sync(rq)]--;
  494. if (rq->cmd_flags & REQ_SORTED)
  495. elv_deactivate_rq(q, rq);
  496. }
  497. rq->cmd_flags &= ~REQ_STARTED;
  498. blk_pm_requeue_request(rq);
  499. __elv_add_request(q, rq, ELEVATOR_INSERT_REQUEUE);
  500. }
  501. /**
  502. * elv_reinsert_request() - Insert a request back to the scheduler
  503. * @q: request queue where request should be inserted
  504. * @rq: request to be inserted
  505. *
  506. * This function returns the request back to the scheduler to be
  507. * inserted as if it was never dispatched
  508. *
  509. * Return: 0 on success, error code on failure
  510. */
  511. int elv_reinsert_request(struct request_queue *q, struct request *rq)
  512. {
  513. int res;
  514. if (!q->elevator->type->ops.elevator_reinsert_req_fn)
  515. return -EPERM;
  516. res = q->elevator->type->ops.elevator_reinsert_req_fn(q, rq);
  517. if (!res) {
  518. /*
  519. * it already went through dequeue, we need to decrement the
  520. * in_flight count again
  521. */
  522. if (blk_account_rq(rq)) {
  523. q->in_flight[rq_is_sync(rq)]--;
  524. if (rq->cmd_flags & REQ_SORTED)
  525. elv_deactivate_rq(q, rq);
  526. }
  527. rq->cmd_flags &= ~REQ_STARTED;
  528. q->nr_sorted++;
  529. }
  530. return res;
  531. }
  532. void elv_drain_elevator(struct request_queue *q)
  533. {
  534. static int printed;
  535. lockdep_assert_held(q->queue_lock);
  536. while (q->elevator->type->ops.elevator_dispatch_fn(q, 1))
  537. ;
  538. if (q->nr_sorted && printed++ < 10) {
  539. printk(KERN_ERR "%s: forced dispatching is broken "
  540. "(nr_sorted=%u), please report this\n",
  541. q->elevator->type->elevator_name, q->nr_sorted);
  542. }
  543. }
  544. void elv_quiesce_start(struct request_queue *q)
  545. {
  546. if (!q->elevator)
  547. return;
  548. spin_lock_irq(q->queue_lock);
  549. queue_flag_set(QUEUE_FLAG_ELVSWITCH, q);
  550. spin_unlock_irq(q->queue_lock);
  551. blk_drain_queue(q, false);
  552. }
  553. void elv_quiesce_end(struct request_queue *q)
  554. {
  555. spin_lock_irq(q->queue_lock);
  556. queue_flag_clear(QUEUE_FLAG_ELVSWITCH, q);
  557. spin_unlock_irq(q->queue_lock);
  558. }
  559. void __elv_add_request(struct request_queue *q, struct request *rq, int where)
  560. {
  561. trace_block_rq_insert(q, rq);
  562. blk_pm_add_request(q, rq);
  563. rq->q = q;
  564. if (rq->cmd_flags & REQ_SOFTBARRIER) {
  565. /* barriers are scheduling boundary, update end_sector */
  566. if (rq->cmd_type == REQ_TYPE_FS ||
  567. (rq->cmd_flags & (REQ_DISCARD | REQ_SANITIZE))) {
  568. q->end_sector = rq_end_sector(rq);
  569. q->boundary_rq = rq;
  570. }
  571. } else if (!(rq->cmd_flags & REQ_ELVPRIV) &&
  572. (where == ELEVATOR_INSERT_SORT ||
  573. where == ELEVATOR_INSERT_SORT_MERGE))
  574. where = ELEVATOR_INSERT_BACK;
  575. switch (where) {
  576. case ELEVATOR_INSERT_REQUEUE:
  577. case ELEVATOR_INSERT_FRONT:
  578. rq->cmd_flags |= REQ_SOFTBARRIER;
  579. list_add(&rq->queuelist, &q->queue_head);
  580. break;
  581. case ELEVATOR_INSERT_BACK:
  582. rq->cmd_flags |= REQ_SOFTBARRIER;
  583. elv_drain_elevator(q);
  584. list_add_tail(&rq->queuelist, &q->queue_head);
  585. /*
  586. * We kick the queue here for the following reasons.
  587. * - The elevator might have returned NULL previously
  588. * to delay requests and returned them now. As the
  589. * queue wasn't empty before this request, ll_rw_blk
  590. * won't run the queue on return, resulting in hang.
  591. * - Usually, back inserted requests won't be merged
  592. * with anything. There's no point in delaying queue
  593. * processing.
  594. */
  595. __blk_run_queue(q);
  596. break;
  597. case ELEVATOR_INSERT_SORT_MERGE:
  598. /*
  599. * If we succeed in merging this request with one in the
  600. * queue already, we are done - rq has now been freed,
  601. * so no need to do anything further.
  602. */
  603. if (elv_attempt_insert_merge(q, rq))
  604. break;
  605. case ELEVATOR_INSERT_SORT:
  606. BUG_ON(rq->cmd_type != REQ_TYPE_FS &&
  607. !(rq->cmd_flags & REQ_DISCARD));
  608. rq->cmd_flags |= REQ_SORTED;
  609. q->nr_sorted++;
  610. if (rq_mergeable(rq)) {
  611. elv_rqhash_add(q, rq);
  612. if (!q->last_merge)
  613. q->last_merge = rq;
  614. }
  615. /*
  616. * Some ioscheds (cfq) run q->request_fn directly, so
  617. * rq cannot be accessed after calling
  618. * elevator_add_req_fn.
  619. */
  620. q->elevator->type->ops.elevator_add_req_fn(q, rq);
  621. break;
  622. case ELEVATOR_INSERT_FLUSH:
  623. rq->cmd_flags |= REQ_SOFTBARRIER;
  624. blk_insert_flush(rq);
  625. break;
  626. default:
  627. printk(KERN_ERR "%s: bad insertion point %d\n",
  628. __func__, where);
  629. BUG();
  630. }
  631. }
  632. EXPORT_SYMBOL(__elv_add_request);
  633. void elv_add_request(struct request_queue *q, struct request *rq, int where)
  634. {
  635. unsigned long flags;
  636. spin_lock_irqsave(q->queue_lock, flags);
  637. __elv_add_request(q, rq, where);
  638. spin_unlock_irqrestore(q->queue_lock, flags);
  639. }
  640. EXPORT_SYMBOL(elv_add_request);
  641. struct request *elv_latter_request(struct request_queue *q, struct request *rq)
  642. {
  643. struct elevator_queue *e = q->elevator;
  644. if (e->type->ops.elevator_latter_req_fn)
  645. return e->type->ops.elevator_latter_req_fn(q, rq);
  646. return NULL;
  647. }
  648. struct request *elv_former_request(struct request_queue *q, struct request *rq)
  649. {
  650. struct elevator_queue *e = q->elevator;
  651. if (e->type->ops.elevator_former_req_fn)
  652. return e->type->ops.elevator_former_req_fn(q, rq);
  653. return NULL;
  654. }
  655. int elv_set_request(struct request_queue *q, struct request *rq, gfp_t gfp_mask)
  656. {
  657. struct elevator_queue *e = q->elevator;
  658. if (e->type->ops.elevator_set_req_fn)
  659. return e->type->ops.elevator_set_req_fn(q, rq, gfp_mask);
  660. return 0;
  661. }
  662. void elv_put_request(struct request_queue *q, struct request *rq)
  663. {
  664. struct elevator_queue *e = q->elevator;
  665. if (e->type->ops.elevator_put_req_fn)
  666. e->type->ops.elevator_put_req_fn(rq);
  667. }
  668. int elv_may_queue(struct request_queue *q, int rw)
  669. {
  670. struct elevator_queue *e = q->elevator;
  671. if (e->type->ops.elevator_may_queue_fn)
  672. return e->type->ops.elevator_may_queue_fn(q, rw);
  673. return ELV_MQUEUE_MAY;
  674. }
  675. void elv_abort_queue(struct request_queue *q)
  676. {
  677. struct request *rq;
  678. blk_abort_flushes(q);
  679. while (!list_empty(&q->queue_head)) {
  680. rq = list_entry_rq(q->queue_head.next);
  681. rq->cmd_flags |= REQ_QUIET;
  682. trace_block_rq_abort(q, rq);
  683. /*
  684. * Mark this request as started so we don't trigger
  685. * any debug logic in the end I/O path.
  686. */
  687. blk_start_request(rq);
  688. __blk_end_request_all(rq, -EIO);
  689. }
  690. }
  691. EXPORT_SYMBOL(elv_abort_queue);
  692. void elv_completed_request(struct request_queue *q, struct request *rq)
  693. {
  694. struct elevator_queue *e = q->elevator;
  695. if (rq->cmd_flags & REQ_URGENT) {
  696. q->notified_urgent = false;
  697. WARN_ON(!q->dispatched_urgent);
  698. q->dispatched_urgent = false;
  699. }
  700. /*
  701. * request is released from the driver, io must be done
  702. */
  703. if (blk_account_rq(rq)) {
  704. q->in_flight[rq_is_sync(rq)]--;
  705. if ((rq->cmd_flags & REQ_SORTED) &&
  706. e->type->ops.elevator_completed_req_fn)
  707. e->type->ops.elevator_completed_req_fn(q, rq);
  708. }
  709. }
  710. #define to_elv(atr) container_of((atr), struct elv_fs_entry, attr)
  711. static ssize_t
  712. elv_attr_show(struct kobject *kobj, struct attribute *attr, char *page)
  713. {
  714. struct elv_fs_entry *entry = to_elv(attr);
  715. struct elevator_queue *e;
  716. ssize_t error;
  717. if (!entry->show)
  718. return -EIO;
  719. e = container_of(kobj, struct elevator_queue, kobj);
  720. mutex_lock(&e->sysfs_lock);
  721. error = e->type ? entry->show(e, page) : -ENOENT;
  722. mutex_unlock(&e->sysfs_lock);
  723. return error;
  724. }
  725. static ssize_t
  726. elv_attr_store(struct kobject *kobj, struct attribute *attr,
  727. const char *page, size_t length)
  728. {
  729. struct elv_fs_entry *entry = to_elv(attr);
  730. struct elevator_queue *e;
  731. ssize_t error;
  732. if (!entry->store)
  733. return -EIO;
  734. e = container_of(kobj, struct elevator_queue, kobj);
  735. mutex_lock(&e->sysfs_lock);
  736. error = e->type ? entry->store(e, page, length) : -ENOENT;
  737. mutex_unlock(&e->sysfs_lock);
  738. return error;
  739. }
  740. static const struct sysfs_ops elv_sysfs_ops = {
  741. .show = elv_attr_show,
  742. .store = elv_attr_store,
  743. };
  744. static struct kobj_type elv_ktype = {
  745. .sysfs_ops = &elv_sysfs_ops,
  746. .release = elevator_release,
  747. };
  748. int __elv_register_queue(struct request_queue *q, struct elevator_queue *e)
  749. {
  750. int error;
  751. error = kobject_add(&e->kobj, &q->kobj, "%s", "iosched");
  752. if (!error) {
  753. struct elv_fs_entry *attr = e->type->elevator_attrs;
  754. if (attr) {
  755. while (attr->attr.name) {
  756. if (sysfs_create_file(&e->kobj, &attr->attr))
  757. break;
  758. attr++;
  759. }
  760. }
  761. kobject_uevent(&e->kobj, KOBJ_ADD);
  762. e->registered = 1;
  763. if (e->type->ops.elevator_registered_fn)
  764. e->type->ops.elevator_registered_fn(q);
  765. }
  766. return error;
  767. }
  768. int elv_register_queue(struct request_queue *q)
  769. {
  770. return __elv_register_queue(q, q->elevator);
  771. }
  772. EXPORT_SYMBOL(elv_register_queue);
  773. void elv_unregister_queue(struct request_queue *q)
  774. {
  775. if (q) {
  776. struct elevator_queue *e = q->elevator;
  777. kobject_uevent(&e->kobj, KOBJ_REMOVE);
  778. kobject_del(&e->kobj);
  779. e->registered = 0;
  780. }
  781. }
  782. EXPORT_SYMBOL(elv_unregister_queue);
  783. int elv_register(struct elevator_type *e)
  784. {
  785. char *def = "";
  786. /* create icq_cache if requested */
  787. if (e->icq_size) {
  788. if (WARN_ON(e->icq_size < sizeof(struct io_cq)) ||
  789. WARN_ON(e->icq_align < __alignof__(struct io_cq)))
  790. return -EINVAL;
  791. snprintf(e->icq_cache_name, sizeof(e->icq_cache_name),
  792. "%s_io_cq", e->elevator_name);
  793. e->icq_cache = kmem_cache_create(e->icq_cache_name, e->icq_size,
  794. e->icq_align, 0, NULL);
  795. if (!e->icq_cache)
  796. return -ENOMEM;
  797. }
  798. /* register, don't allow duplicate names */
  799. spin_lock(&elv_list_lock);
  800. if (elevator_find(e->elevator_name)) {
  801. spin_unlock(&elv_list_lock);
  802. if (e->icq_cache)
  803. kmem_cache_destroy(e->icq_cache);
  804. return -EBUSY;
  805. }
  806. list_add_tail(&e->list, &elv_list);
  807. spin_unlock(&elv_list_lock);
  808. /* print pretty message */
  809. if (!strcmp(e->elevator_name, chosen_elevator) ||
  810. (!*chosen_elevator &&
  811. !strcmp(e->elevator_name, CONFIG_DEFAULT_IOSCHED)))
  812. def = " (default)";
  813. printk(KERN_INFO "io scheduler %s registered%s\n", e->elevator_name,
  814. def);
  815. return 0;
  816. }
  817. EXPORT_SYMBOL_GPL(elv_register);
  818. void elv_unregister(struct elevator_type *e)
  819. {
  820. /* unregister */
  821. spin_lock(&elv_list_lock);
  822. list_del_init(&e->list);
  823. spin_unlock(&elv_list_lock);
  824. /*
  825. * Destroy icq_cache if it exists. icq's are RCU managed. Make
  826. * sure all RCU operations are complete before proceeding.
  827. */
  828. if (e->icq_cache) {
  829. rcu_barrier();
  830. kmem_cache_destroy(e->icq_cache);
  831. e->icq_cache = NULL;
  832. }
  833. }
  834. EXPORT_SYMBOL_GPL(elv_unregister);
  835. /*
  836. * switch to new_e io scheduler. be careful not to introduce deadlocks -
  837. * we don't free the old io scheduler, before we have allocated what we
  838. * need for the new one. this way we have a chance of going back to the old
  839. * one, if the new one fails init for some reason.
  840. */
  841. static int elevator_switch(struct request_queue *q, struct elevator_type *new_e)
  842. {
  843. struct elevator_queue *old_elevator, *e;
  844. int err;
  845. /* allocate new elevator */
  846. e = elevator_alloc(q, new_e);
  847. if (!e)
  848. return -ENOMEM;
  849. err = elevator_init_queue(q, e);
  850. if (err) {
  851. kobject_put(&e->kobj);
  852. return err;
  853. }
  854. /* turn on BYPASS and drain all requests w/ elevator private data */
  855. elv_quiesce_start(q);
  856. /* unregister old queue, register new one and kill old elevator */
  857. if (q->elevator->registered) {
  858. elv_unregister_queue(q);
  859. err = __elv_register_queue(q, e);
  860. if (err)
  861. goto fail_register;
  862. }
  863. /* done, clear io_cq's, switch elevators and turn off BYPASS */
  864. spin_lock_irq(q->queue_lock);
  865. ioc_clear_queue(q);
  866. old_elevator = q->elevator;
  867. q->elevator = e;
  868. spin_unlock_irq(q->queue_lock);
  869. elevator_exit(old_elevator);
  870. elv_quiesce_end(q);
  871. blk_add_trace_msg(q, "elv switch: %s", e->type->elevator_name);
  872. return 0;
  873. fail_register:
  874. /*
  875. * switch failed, exit the new io scheduler and reattach the old
  876. * one again (along with re-adding the sysfs dir)
  877. */
  878. elevator_exit(e);
  879. elv_register_queue(q);
  880. elv_quiesce_end(q);
  881. return err;
  882. }
  883. /*
  884. * Switch this queue to the given IO scheduler.
  885. */
  886. static int __elevator_change(struct request_queue *q, const char *name)
  887. {
  888. char elevator_name[ELV_NAME_MAX];
  889. struct elevator_type *e;
  890. if (!q->elevator)
  891. return -ENXIO;
  892. strlcpy(elevator_name, name, sizeof(elevator_name));
  893. e = elevator_get(strstrip(elevator_name));
  894. if (!e) {
  895. printk(KERN_ERR "elevator: type %s not found\n", elevator_name);
  896. return -EINVAL;
  897. }
  898. if (!strcmp(elevator_name, q->elevator->type->elevator_name)) {
  899. elevator_put(e);
  900. return 0;
  901. }
  902. return elevator_switch(q, e);
  903. }
  904. int elevator_change(struct request_queue *q, const char *name)
  905. {
  906. int ret;
  907. /* Protect q->elevator from elevator_init() */
  908. mutex_lock(&q->sysfs_lock);
  909. ret = __elevator_change(q, name);
  910. mutex_unlock(&q->sysfs_lock);
  911. return ret;
  912. }
  913. EXPORT_SYMBOL(elevator_change);
  914. ssize_t elv_iosched_store(struct request_queue *q, const char *name,
  915. size_t count)
  916. {
  917. int ret;
  918. if (!q->elevator)
  919. return count;
  920. ret = __elevator_change(q, name);
  921. if (!ret)
  922. return count;
  923. printk(KERN_ERR "elevator: switch to %s failed\n", name);
  924. return ret;
  925. }
  926. ssize_t elv_iosched_show(struct request_queue *q, char *name)
  927. {
  928. struct elevator_queue *e = q->elevator;
  929. struct elevator_type *elv;
  930. struct elevator_type *__e;
  931. int len = 0;
  932. if (!q->elevator || !blk_queue_stackable(q))
  933. return sprintf(name, "none\n");
  934. elv = e->type;
  935. spin_lock(&elv_list_lock);
  936. list_for_each_entry(__e, &elv_list, list) {
  937. if (!strcmp(elv->elevator_name, __e->elevator_name))
  938. len += sprintf(name+len, "[%s] ", elv->elevator_name);
  939. else
  940. len += sprintf(name+len, "%s ", __e->elevator_name);
  941. }
  942. spin_unlock(&elv_list_lock);
  943. len += sprintf(len+name, "\n");
  944. return len;
  945. }
  946. struct request *elv_rb_former_request(struct request_queue *q,
  947. struct request *rq)
  948. {
  949. struct rb_node *rbprev = rb_prev(&rq->rb_node);
  950. if (rbprev)
  951. return rb_entry_rq(rbprev);
  952. return NULL;
  953. }
  954. EXPORT_SYMBOL(elv_rb_former_request);
  955. struct request *elv_rb_latter_request(struct request_queue *q,
  956. struct request *rq)
  957. {
  958. struct rb_node *rbnext = rb_next(&rq->rb_node);
  959. if (rbnext)
  960. return rb_entry_rq(rbnext);
  961. return NULL;
  962. }
  963. EXPORT_SYMBOL(elv_rb_latter_request);