elevator.c 25 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153
  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/delay.h>
  35. #include <linux/blktrace_api.h>
  36. #include <linux/hash.h>
  37. #include <asm/uaccess.h>
  38. static DEFINE_SPINLOCK(elv_list_lock);
  39. static LIST_HEAD(elv_list);
  40. /*
  41. * Merge hash stuff.
  42. */
  43. static const int elv_hash_shift = 6;
  44. #define ELV_HASH_BLOCK(sec) ((sec) >> 3)
  45. #define ELV_HASH_FN(sec) (hash_long(ELV_HASH_BLOCK((sec)), elv_hash_shift))
  46. #define ELV_HASH_ENTRIES (1 << elv_hash_shift)
  47. #define rq_hash_key(rq) ((rq)->sector + (rq)->nr_sectors)
  48. #define ELV_ON_HASH(rq) (!hlist_unhashed(&(rq)->hash))
  49. /*
  50. * Query io scheduler to see if the current process issuing bio may be
  51. * merged with rq.
  52. */
  53. static int elv_iosched_allow_merge(struct request *rq, struct bio *bio)
  54. {
  55. request_queue_t *q = rq->q;
  56. elevator_t *e = q->elevator;
  57. if (e->ops->elevator_allow_merge_fn)
  58. return e->ops->elevator_allow_merge_fn(q, rq, bio);
  59. return 1;
  60. }
  61. /*
  62. * can we safely merge with this request?
  63. */
  64. inline int elv_rq_merge_ok(struct request *rq, struct bio *bio)
  65. {
  66. if (!rq_mergeable(rq))
  67. return 0;
  68. /*
  69. * different data direction or already started, don't merge
  70. */
  71. if (bio_data_dir(bio) != rq_data_dir(rq))
  72. return 0;
  73. /*
  74. * must be same device and not a special request
  75. */
  76. if (rq->rq_disk != bio->bi_bdev->bd_disk || rq->special)
  77. return 0;
  78. if (!elv_iosched_allow_merge(rq, bio))
  79. return 0;
  80. return 1;
  81. }
  82. EXPORT_SYMBOL(elv_rq_merge_ok);
  83. static inline int elv_try_merge(struct request *__rq, struct bio *bio)
  84. {
  85. int ret = ELEVATOR_NO_MERGE;
  86. /*
  87. * we can merge and sequence is ok, check if it's possible
  88. */
  89. if (elv_rq_merge_ok(__rq, bio)) {
  90. if (__rq->sector + __rq->nr_sectors == bio->bi_sector)
  91. ret = ELEVATOR_BACK_MERGE;
  92. else if (__rq->sector - bio_sectors(bio) == bio->bi_sector)
  93. ret = ELEVATOR_FRONT_MERGE;
  94. }
  95. return ret;
  96. }
  97. static struct elevator_type *elevator_find(const char *name)
  98. {
  99. struct elevator_type *e;
  100. list_for_each_entry(e, &elv_list, list) {
  101. if (!strcmp(e->elevator_name, name))
  102. return e;
  103. }
  104. return NULL;
  105. }
  106. static void elevator_put(struct elevator_type *e)
  107. {
  108. module_put(e->elevator_owner);
  109. }
  110. static struct elevator_type *elevator_get(const char *name)
  111. {
  112. struct elevator_type *e;
  113. spin_lock(&elv_list_lock);
  114. e = elevator_find(name);
  115. if (e && !try_module_get(e->elevator_owner))
  116. e = NULL;
  117. spin_unlock(&elv_list_lock);
  118. return e;
  119. }
  120. static void *elevator_init_queue(request_queue_t *q, struct elevator_queue *eq)
  121. {
  122. return eq->ops->elevator_init_fn(q);
  123. }
  124. static void elevator_attach(request_queue_t *q, struct elevator_queue *eq,
  125. void *data)
  126. {
  127. q->elevator = eq;
  128. eq->elevator_data = data;
  129. }
  130. static char chosen_elevator[16];
  131. static int __init elevator_setup(char *str)
  132. {
  133. /*
  134. * Be backwards-compatible with previous kernels, so users
  135. * won't get the wrong elevator.
  136. */
  137. if (!strcmp(str, "as"))
  138. strcpy(chosen_elevator, "anticipatory");
  139. else
  140. strncpy(chosen_elevator, str, sizeof(chosen_elevator) - 1);
  141. return 1;
  142. }
  143. __setup("elevator=", elevator_setup);
  144. static struct kobj_type elv_ktype;
  145. static elevator_t *elevator_alloc(request_queue_t *q, struct elevator_type *e)
  146. {
  147. elevator_t *eq;
  148. int i;
  149. eq = kmalloc_node(sizeof(elevator_t), GFP_KERNEL, q->node);
  150. if (unlikely(!eq))
  151. goto err;
  152. memset(eq, 0, sizeof(*eq));
  153. eq->ops = &e->ops;
  154. eq->elevator_type = e;
  155. kobject_init(&eq->kobj);
  156. snprintf(eq->kobj.name, KOBJ_NAME_LEN, "%s", "iosched");
  157. eq->kobj.ktype = &elv_ktype;
  158. mutex_init(&eq->sysfs_lock);
  159. eq->hash = kmalloc_node(sizeof(struct hlist_head) * ELV_HASH_ENTRIES,
  160. GFP_KERNEL, q->node);
  161. if (!eq->hash)
  162. goto err;
  163. for (i = 0; i < ELV_HASH_ENTRIES; i++)
  164. INIT_HLIST_HEAD(&eq->hash[i]);
  165. return eq;
  166. err:
  167. kfree(eq);
  168. elevator_put(e);
  169. return NULL;
  170. }
  171. static void elevator_release(struct kobject *kobj)
  172. {
  173. elevator_t *e = container_of(kobj, elevator_t, kobj);
  174. elevator_put(e->elevator_type);
  175. kfree(e->hash);
  176. kfree(e);
  177. }
  178. int elevator_init(request_queue_t *q, char *name)
  179. {
  180. struct elevator_type *e = NULL;
  181. struct elevator_queue *eq;
  182. int ret = 0;
  183. void *data;
  184. INIT_LIST_HEAD(&q->queue_head);
  185. q->last_merge = NULL;
  186. q->end_sector = 0;
  187. q->boundary_rq = NULL;
  188. if (name && !(e = elevator_get(name)))
  189. return -EINVAL;
  190. if (!e && *chosen_elevator && !(e = elevator_get(chosen_elevator)))
  191. printk("I/O scheduler %s not found\n", chosen_elevator);
  192. if (!e && !(e = elevator_get(CONFIG_DEFAULT_IOSCHED))) {
  193. printk("Default I/O scheduler not found, using no-op\n");
  194. e = elevator_get("noop");
  195. }
  196. eq = elevator_alloc(q, e);
  197. if (!eq)
  198. return -ENOMEM;
  199. data = elevator_init_queue(q, eq);
  200. if (!data) {
  201. kobject_put(&eq->kobj);
  202. return -ENOMEM;
  203. }
  204. elevator_attach(q, eq, data);
  205. return ret;
  206. }
  207. EXPORT_SYMBOL(elevator_init);
  208. void elevator_exit(elevator_t *e)
  209. {
  210. mutex_lock(&e->sysfs_lock);
  211. if (e->ops->elevator_exit_fn)
  212. e->ops->elevator_exit_fn(e);
  213. e->ops = NULL;
  214. mutex_unlock(&e->sysfs_lock);
  215. kobject_put(&e->kobj);
  216. }
  217. EXPORT_SYMBOL(elevator_exit);
  218. static void elv_activate_rq(request_queue_t *q, struct request *rq)
  219. {
  220. elevator_t *e = q->elevator;
  221. if (e->ops->elevator_activate_req_fn)
  222. e->ops->elevator_activate_req_fn(q, rq);
  223. }
  224. static void elv_deactivate_rq(request_queue_t *q, struct request *rq)
  225. {
  226. elevator_t *e = q->elevator;
  227. if (e->ops->elevator_deactivate_req_fn)
  228. e->ops->elevator_deactivate_req_fn(q, rq);
  229. }
  230. static inline void __elv_rqhash_del(struct request *rq)
  231. {
  232. hlist_del_init(&rq->hash);
  233. }
  234. static void elv_rqhash_del(request_queue_t *q, struct request *rq)
  235. {
  236. if (ELV_ON_HASH(rq))
  237. __elv_rqhash_del(rq);
  238. }
  239. static void elv_rqhash_add(request_queue_t *q, struct request *rq)
  240. {
  241. elevator_t *e = q->elevator;
  242. BUG_ON(ELV_ON_HASH(rq));
  243. hlist_add_head(&rq->hash, &e->hash[ELV_HASH_FN(rq_hash_key(rq))]);
  244. }
  245. static void elv_rqhash_reposition(request_queue_t *q, struct request *rq)
  246. {
  247. __elv_rqhash_del(rq);
  248. elv_rqhash_add(q, rq);
  249. }
  250. static struct request *elv_rqhash_find(request_queue_t *q, sector_t offset)
  251. {
  252. elevator_t *e = q->elevator;
  253. struct hlist_head *hash_list = &e->hash[ELV_HASH_FN(offset)];
  254. struct hlist_node *entry, *next;
  255. struct request *rq;
  256. hlist_for_each_entry_safe(rq, entry, next, hash_list, hash) {
  257. BUG_ON(!ELV_ON_HASH(rq));
  258. if (unlikely(!rq_mergeable(rq))) {
  259. __elv_rqhash_del(rq);
  260. continue;
  261. }
  262. if (rq_hash_key(rq) == offset)
  263. return rq;
  264. }
  265. return NULL;
  266. }
  267. /*
  268. * RB-tree support functions for inserting/lookup/removal of requests
  269. * in a sorted RB tree.
  270. */
  271. struct request *elv_rb_add(struct rb_root *root, struct request *rq)
  272. {
  273. struct rb_node **p = &root->rb_node;
  274. struct rb_node *parent = NULL;
  275. struct request *__rq;
  276. while (*p) {
  277. parent = *p;
  278. __rq = rb_entry(parent, struct request, rb_node);
  279. if (rq->sector < __rq->sector)
  280. p = &(*p)->rb_left;
  281. else if (rq->sector > __rq->sector)
  282. p = &(*p)->rb_right;
  283. else
  284. return __rq;
  285. }
  286. rb_link_node(&rq->rb_node, parent, p);
  287. rb_insert_color(&rq->rb_node, root);
  288. return NULL;
  289. }
  290. EXPORT_SYMBOL(elv_rb_add);
  291. void elv_rb_del(struct rb_root *root, struct request *rq)
  292. {
  293. BUG_ON(RB_EMPTY_NODE(&rq->rb_node));
  294. rb_erase(&rq->rb_node, root);
  295. RB_CLEAR_NODE(&rq->rb_node);
  296. }
  297. EXPORT_SYMBOL(elv_rb_del);
  298. struct request *elv_rb_find(struct rb_root *root, sector_t sector)
  299. {
  300. struct rb_node *n = root->rb_node;
  301. struct request *rq;
  302. while (n) {
  303. rq = rb_entry(n, struct request, rb_node);
  304. if (sector < rq->sector)
  305. n = n->rb_left;
  306. else if (sector > rq->sector)
  307. n = n->rb_right;
  308. else
  309. return rq;
  310. }
  311. return NULL;
  312. }
  313. EXPORT_SYMBOL(elv_rb_find);
  314. /*
  315. * Insert rq into dispatch queue of q. Queue lock must be held on
  316. * entry. rq is sort insted into the dispatch queue. To be used by
  317. * specific elevators.
  318. */
  319. void elv_dispatch_sort(request_queue_t *q, struct request *rq)
  320. {
  321. sector_t boundary;
  322. struct list_head *entry;
  323. if (q->last_merge == rq)
  324. q->last_merge = NULL;
  325. elv_rqhash_del(q, rq);
  326. q->nr_sorted--;
  327. boundary = q->end_sector;
  328. list_for_each_prev(entry, &q->queue_head) {
  329. struct request *pos = list_entry_rq(entry);
  330. if (rq_data_dir(rq) != rq_data_dir(pos))
  331. break;
  332. if (pos->cmd_flags & (REQ_SOFTBARRIER|REQ_HARDBARRIER|REQ_STARTED))
  333. break;
  334. if (rq->sector >= boundary) {
  335. if (pos->sector < boundary)
  336. continue;
  337. } else {
  338. if (pos->sector >= boundary)
  339. break;
  340. }
  341. if (rq->sector >= pos->sector)
  342. break;
  343. }
  344. list_add(&rq->queuelist, entry);
  345. }
  346. EXPORT_SYMBOL(elv_dispatch_sort);
  347. /*
  348. * Insert rq into dispatch queue of q. Queue lock must be held on
  349. * entry. rq is added to the back of the dispatch queue. To be used by
  350. * specific elevators.
  351. */
  352. void elv_dispatch_add_tail(struct request_queue *q, struct request *rq)
  353. {
  354. if (q->last_merge == rq)
  355. q->last_merge = NULL;
  356. elv_rqhash_del(q, rq);
  357. q->nr_sorted--;
  358. q->end_sector = rq_end_sector(rq);
  359. q->boundary_rq = rq;
  360. list_add_tail(&rq->queuelist, &q->queue_head);
  361. }
  362. EXPORT_SYMBOL(elv_dispatch_add_tail);
  363. int elv_merge(request_queue_t *q, struct request **req, struct bio *bio)
  364. {
  365. elevator_t *e = q->elevator;
  366. struct request *__rq;
  367. int ret;
  368. /*
  369. * First try one-hit cache.
  370. */
  371. if (q->last_merge) {
  372. ret = elv_try_merge(q->last_merge, bio);
  373. if (ret != ELEVATOR_NO_MERGE) {
  374. *req = q->last_merge;
  375. return ret;
  376. }
  377. }
  378. /*
  379. * See if our hash lookup can find a potential backmerge.
  380. */
  381. __rq = elv_rqhash_find(q, bio->bi_sector);
  382. if (__rq && elv_rq_merge_ok(__rq, bio)) {
  383. *req = __rq;
  384. return ELEVATOR_BACK_MERGE;
  385. }
  386. if (e->ops->elevator_merge_fn)
  387. return e->ops->elevator_merge_fn(q, req, bio);
  388. return ELEVATOR_NO_MERGE;
  389. }
  390. void elv_merged_request(request_queue_t *q, struct request *rq, int type)
  391. {
  392. elevator_t *e = q->elevator;
  393. if (e->ops->elevator_merged_fn)
  394. e->ops->elevator_merged_fn(q, rq, type);
  395. if (type == ELEVATOR_BACK_MERGE)
  396. elv_rqhash_reposition(q, rq);
  397. q->last_merge = rq;
  398. }
  399. void elv_merge_requests(request_queue_t *q, struct request *rq,
  400. struct request *next)
  401. {
  402. elevator_t *e = q->elevator;
  403. if (e->ops->elevator_merge_req_fn)
  404. e->ops->elevator_merge_req_fn(q, rq, next);
  405. elv_rqhash_reposition(q, rq);
  406. elv_rqhash_del(q, next);
  407. q->nr_sorted--;
  408. q->last_merge = rq;
  409. }
  410. void elv_requeue_request(request_queue_t *q, struct request *rq)
  411. {
  412. /*
  413. * it already went through dequeue, we need to decrement the
  414. * in_flight count again
  415. */
  416. if (blk_account_rq(rq)) {
  417. q->in_flight--;
  418. if (blk_sorted_rq(rq))
  419. elv_deactivate_rq(q, rq);
  420. }
  421. rq->cmd_flags &= ~REQ_STARTED;
  422. elv_insert(q, rq, ELEVATOR_INSERT_REQUEUE);
  423. }
  424. static void elv_drain_elevator(request_queue_t *q)
  425. {
  426. static int printed;
  427. while (q->elevator->ops->elevator_dispatch_fn(q, 1))
  428. ;
  429. if (q->nr_sorted == 0)
  430. return;
  431. if (printed++ < 10) {
  432. printk(KERN_ERR "%s: forced dispatching is broken "
  433. "(nr_sorted=%u), please report this\n",
  434. q->elevator->elevator_type->elevator_name, q->nr_sorted);
  435. }
  436. }
  437. void elv_insert(request_queue_t *q, struct request *rq, int where)
  438. {
  439. struct list_head *pos;
  440. unsigned ordseq;
  441. int unplug_it = 1;
  442. blk_add_trace_rq(q, rq, BLK_TA_INSERT);
  443. rq->q = q;
  444. switch (where) {
  445. case ELEVATOR_INSERT_FRONT:
  446. rq->cmd_flags |= REQ_SOFTBARRIER;
  447. list_add(&rq->queuelist, &q->queue_head);
  448. break;
  449. case ELEVATOR_INSERT_BACK:
  450. rq->cmd_flags |= REQ_SOFTBARRIER;
  451. elv_drain_elevator(q);
  452. list_add_tail(&rq->queuelist, &q->queue_head);
  453. /*
  454. * We kick the queue here for the following reasons.
  455. * - The elevator might have returned NULL previously
  456. * to delay requests and returned them now. As the
  457. * queue wasn't empty before this request, ll_rw_blk
  458. * won't run the queue on return, resulting in hang.
  459. * - Usually, back inserted requests won't be merged
  460. * with anything. There's no point in delaying queue
  461. * processing.
  462. */
  463. blk_remove_plug(q);
  464. q->request_fn(q);
  465. break;
  466. case ELEVATOR_INSERT_SORT:
  467. BUG_ON(!blk_fs_request(rq));
  468. rq->cmd_flags |= REQ_SORTED;
  469. q->nr_sorted++;
  470. if (rq_mergeable(rq)) {
  471. elv_rqhash_add(q, rq);
  472. if (!q->last_merge)
  473. q->last_merge = rq;
  474. }
  475. /*
  476. * Some ioscheds (cfq) run q->request_fn directly, so
  477. * rq cannot be accessed after calling
  478. * elevator_add_req_fn.
  479. */
  480. q->elevator->ops->elevator_add_req_fn(q, rq);
  481. break;
  482. case ELEVATOR_INSERT_REQUEUE:
  483. /*
  484. * If ordered flush isn't in progress, we do front
  485. * insertion; otherwise, requests should be requeued
  486. * in ordseq order.
  487. */
  488. rq->cmd_flags |= REQ_SOFTBARRIER;
  489. /*
  490. * Most requeues happen because of a busy condition,
  491. * don't force unplug of the queue for that case.
  492. */
  493. unplug_it = 0;
  494. if (q->ordseq == 0) {
  495. list_add(&rq->queuelist, &q->queue_head);
  496. break;
  497. }
  498. ordseq = blk_ordered_req_seq(rq);
  499. list_for_each(pos, &q->queue_head) {
  500. struct request *pos_rq = list_entry_rq(pos);
  501. if (ordseq <= blk_ordered_req_seq(pos_rq))
  502. break;
  503. }
  504. list_add_tail(&rq->queuelist, pos);
  505. break;
  506. default:
  507. printk(KERN_ERR "%s: bad insertion point %d\n",
  508. __FUNCTION__, where);
  509. BUG();
  510. }
  511. if (unplug_it && blk_queue_plugged(q)) {
  512. int nrq = q->rq.count[READ] + q->rq.count[WRITE]
  513. - q->in_flight;
  514. if (nrq >= q->unplug_thresh)
  515. __generic_unplug_device(q);
  516. }
  517. }
  518. void __elv_add_request(request_queue_t *q, struct request *rq, int where,
  519. int plug)
  520. {
  521. if (q->ordcolor)
  522. rq->cmd_flags |= REQ_ORDERED_COLOR;
  523. if (rq->cmd_flags & (REQ_SOFTBARRIER | REQ_HARDBARRIER)) {
  524. /*
  525. * toggle ordered color
  526. */
  527. if (blk_barrier_rq(rq))
  528. q->ordcolor ^= 1;
  529. /*
  530. * barriers implicitly indicate back insertion
  531. */
  532. if (where == ELEVATOR_INSERT_SORT)
  533. where = ELEVATOR_INSERT_BACK;
  534. /*
  535. * this request is scheduling boundary, update
  536. * end_sector
  537. */
  538. if (blk_fs_request(rq)) {
  539. q->end_sector = rq_end_sector(rq);
  540. q->boundary_rq = rq;
  541. }
  542. } else if (!(rq->cmd_flags & REQ_ELVPRIV) && where == ELEVATOR_INSERT_SORT)
  543. where = ELEVATOR_INSERT_BACK;
  544. if (plug)
  545. blk_plug_device(q);
  546. elv_insert(q, rq, where);
  547. }
  548. EXPORT_SYMBOL(__elv_add_request);
  549. void elv_add_request(request_queue_t *q, struct request *rq, int where,
  550. int plug)
  551. {
  552. unsigned long flags;
  553. spin_lock_irqsave(q->queue_lock, flags);
  554. __elv_add_request(q, rq, where, plug);
  555. spin_unlock_irqrestore(q->queue_lock, flags);
  556. }
  557. EXPORT_SYMBOL(elv_add_request);
  558. static inline struct request *__elv_next_request(request_queue_t *q)
  559. {
  560. struct request *rq;
  561. while (1) {
  562. while (!list_empty(&q->queue_head)) {
  563. rq = list_entry_rq(q->queue_head.next);
  564. if (blk_do_ordered(q, &rq))
  565. return rq;
  566. }
  567. if (!q->elevator->ops->elevator_dispatch_fn(q, 0))
  568. return NULL;
  569. }
  570. }
  571. struct request *elv_next_request(request_queue_t *q)
  572. {
  573. struct request *rq;
  574. int ret;
  575. while ((rq = __elv_next_request(q)) != NULL) {
  576. if (!(rq->cmd_flags & REQ_STARTED)) {
  577. /*
  578. * This is the first time the device driver
  579. * sees this request (possibly after
  580. * requeueing). Notify IO scheduler.
  581. */
  582. if (blk_sorted_rq(rq))
  583. elv_activate_rq(q, rq);
  584. /*
  585. * just mark as started even if we don't start
  586. * it, a request that has been delayed should
  587. * not be passed by new incoming requests
  588. */
  589. rq->cmd_flags |= REQ_STARTED;
  590. blk_add_trace_rq(q, rq, BLK_TA_ISSUE);
  591. }
  592. if (!q->boundary_rq || q->boundary_rq == rq) {
  593. q->end_sector = rq_end_sector(rq);
  594. q->boundary_rq = NULL;
  595. }
  596. if ((rq->cmd_flags & REQ_DONTPREP) || !q->prep_rq_fn)
  597. break;
  598. ret = q->prep_rq_fn(q, rq);
  599. if (ret == BLKPREP_OK) {
  600. break;
  601. } else if (ret == BLKPREP_DEFER) {
  602. /*
  603. * the request may have been (partially) prepped.
  604. * we need to keep this request in the front to
  605. * avoid resource deadlock. REQ_STARTED will
  606. * prevent other fs requests from passing this one.
  607. */
  608. rq = NULL;
  609. break;
  610. } else if (ret == BLKPREP_KILL) {
  611. int nr_bytes = rq->hard_nr_sectors << 9;
  612. if (!nr_bytes)
  613. nr_bytes = rq->data_len;
  614. blkdev_dequeue_request(rq);
  615. rq->cmd_flags |= REQ_QUIET;
  616. end_that_request_chunk(rq, 0, nr_bytes);
  617. end_that_request_last(rq, 0);
  618. } else {
  619. printk(KERN_ERR "%s: bad return=%d\n", __FUNCTION__,
  620. ret);
  621. break;
  622. }
  623. }
  624. return rq;
  625. }
  626. EXPORT_SYMBOL(elv_next_request);
  627. void elv_dequeue_request(request_queue_t *q, struct request *rq)
  628. {
  629. BUG_ON(list_empty(&rq->queuelist));
  630. BUG_ON(ELV_ON_HASH(rq));
  631. list_del_init(&rq->queuelist);
  632. /*
  633. * the time frame between a request being removed from the lists
  634. * and to it is freed is accounted as io that is in progress at
  635. * the driver side.
  636. */
  637. if (blk_account_rq(rq))
  638. q->in_flight++;
  639. }
  640. EXPORT_SYMBOL(elv_dequeue_request);
  641. int elv_queue_empty(request_queue_t *q)
  642. {
  643. elevator_t *e = q->elevator;
  644. if (!list_empty(&q->queue_head))
  645. return 0;
  646. if (e->ops->elevator_queue_empty_fn)
  647. return e->ops->elevator_queue_empty_fn(q);
  648. return 1;
  649. }
  650. EXPORT_SYMBOL(elv_queue_empty);
  651. struct request *elv_latter_request(request_queue_t *q, struct request *rq)
  652. {
  653. elevator_t *e = q->elevator;
  654. if (e->ops->elevator_latter_req_fn)
  655. return e->ops->elevator_latter_req_fn(q, rq);
  656. return NULL;
  657. }
  658. struct request *elv_former_request(request_queue_t *q, struct request *rq)
  659. {
  660. elevator_t *e = q->elevator;
  661. if (e->ops->elevator_former_req_fn)
  662. return e->ops->elevator_former_req_fn(q, rq);
  663. return NULL;
  664. }
  665. int elv_set_request(request_queue_t *q, struct request *rq, gfp_t gfp_mask)
  666. {
  667. elevator_t *e = q->elevator;
  668. if (e->ops->elevator_set_req_fn)
  669. return e->ops->elevator_set_req_fn(q, rq, gfp_mask);
  670. rq->elevator_private = NULL;
  671. return 0;
  672. }
  673. void elv_put_request(request_queue_t *q, struct request *rq)
  674. {
  675. elevator_t *e = q->elevator;
  676. if (e->ops->elevator_put_req_fn)
  677. e->ops->elevator_put_req_fn(rq);
  678. }
  679. int elv_may_queue(request_queue_t *q, int rw)
  680. {
  681. elevator_t *e = q->elevator;
  682. if (e->ops->elevator_may_queue_fn)
  683. return e->ops->elevator_may_queue_fn(q, rw);
  684. return ELV_MQUEUE_MAY;
  685. }
  686. void elv_completed_request(request_queue_t *q, struct request *rq)
  687. {
  688. elevator_t *e = q->elevator;
  689. /*
  690. * request is released from the driver, io must be done
  691. */
  692. if (blk_account_rq(rq)) {
  693. q->in_flight--;
  694. if (blk_sorted_rq(rq) && e->ops->elevator_completed_req_fn)
  695. e->ops->elevator_completed_req_fn(q, rq);
  696. }
  697. /*
  698. * Check if the queue is waiting for fs requests to be
  699. * drained for flush sequence.
  700. */
  701. if (unlikely(q->ordseq)) {
  702. struct request *first_rq = list_entry_rq(q->queue_head.next);
  703. if (q->in_flight == 0 &&
  704. blk_ordered_cur_seq(q) == QUEUE_ORDSEQ_DRAIN &&
  705. blk_ordered_req_seq(first_rq) > QUEUE_ORDSEQ_DRAIN) {
  706. blk_ordered_complete_seq(q, QUEUE_ORDSEQ_DRAIN, 0);
  707. q->request_fn(q);
  708. }
  709. }
  710. }
  711. #define to_elv(atr) container_of((atr), struct elv_fs_entry, attr)
  712. static ssize_t
  713. elv_attr_show(struct kobject *kobj, struct attribute *attr, char *page)
  714. {
  715. elevator_t *e = container_of(kobj, elevator_t, kobj);
  716. struct elv_fs_entry *entry = to_elv(attr);
  717. ssize_t error;
  718. if (!entry->show)
  719. return -EIO;
  720. mutex_lock(&e->sysfs_lock);
  721. error = e->ops ? 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. elevator_t *e = container_of(kobj, elevator_t, kobj);
  730. struct elv_fs_entry *entry = to_elv(attr);
  731. ssize_t error;
  732. if (!entry->store)
  733. return -EIO;
  734. mutex_lock(&e->sysfs_lock);
  735. error = e->ops ? entry->store(e, page, length) : -ENOENT;
  736. mutex_unlock(&e->sysfs_lock);
  737. return error;
  738. }
  739. static struct sysfs_ops elv_sysfs_ops = {
  740. .show = elv_attr_show,
  741. .store = elv_attr_store,
  742. };
  743. static struct kobj_type elv_ktype = {
  744. .sysfs_ops = &elv_sysfs_ops,
  745. .release = elevator_release,
  746. };
  747. int elv_register_queue(struct request_queue *q)
  748. {
  749. elevator_t *e = q->elevator;
  750. int error;
  751. e->kobj.parent = &q->kobj;
  752. error = kobject_add(&e->kobj);
  753. if (!error) {
  754. struct elv_fs_entry *attr = e->elevator_type->elevator_attrs;
  755. if (attr) {
  756. while (attr->attr.name) {
  757. if (sysfs_create_file(&e->kobj, &attr->attr))
  758. break;
  759. attr++;
  760. }
  761. }
  762. kobject_uevent(&e->kobj, KOBJ_ADD);
  763. }
  764. return error;
  765. }
  766. static void __elv_unregister_queue(elevator_t *e)
  767. {
  768. kobject_uevent(&e->kobj, KOBJ_REMOVE);
  769. kobject_del(&e->kobj);
  770. }
  771. void elv_unregister_queue(struct request_queue *q)
  772. {
  773. if (q)
  774. __elv_unregister_queue(q->elevator);
  775. }
  776. int elv_register(struct elevator_type *e)
  777. {
  778. char *def = "";
  779. spin_lock(&elv_list_lock);
  780. BUG_ON(elevator_find(e->elevator_name));
  781. list_add_tail(&e->list, &elv_list);
  782. spin_unlock(&elv_list_lock);
  783. if (!strcmp(e->elevator_name, chosen_elevator) ||
  784. (!*chosen_elevator &&
  785. !strcmp(e->elevator_name, CONFIG_DEFAULT_IOSCHED)))
  786. def = " (default)";
  787. printk(KERN_INFO "io scheduler %s registered%s\n", e->elevator_name, def);
  788. return 0;
  789. }
  790. EXPORT_SYMBOL_GPL(elv_register);
  791. void elv_unregister(struct elevator_type *e)
  792. {
  793. struct task_struct *g, *p;
  794. /*
  795. * Iterate every thread in the process to remove the io contexts.
  796. */
  797. if (e->ops.trim) {
  798. read_lock(&tasklist_lock);
  799. do_each_thread(g, p) {
  800. task_lock(p);
  801. if (p->io_context)
  802. e->ops.trim(p->io_context);
  803. task_unlock(p);
  804. } while_each_thread(g, p);
  805. read_unlock(&tasklist_lock);
  806. }
  807. spin_lock(&elv_list_lock);
  808. list_del_init(&e->list);
  809. spin_unlock(&elv_list_lock);
  810. }
  811. EXPORT_SYMBOL_GPL(elv_unregister);
  812. /*
  813. * switch to new_e io scheduler. be careful not to introduce deadlocks -
  814. * we don't free the old io scheduler, before we have allocated what we
  815. * need for the new one. this way we have a chance of going back to the old
  816. * one, if the new one fails init for some reason.
  817. */
  818. static int elevator_switch(request_queue_t *q, struct elevator_type *new_e)
  819. {
  820. elevator_t *old_elevator, *e;
  821. void *data;
  822. /*
  823. * Allocate new elevator
  824. */
  825. e = elevator_alloc(q, new_e);
  826. if (!e)
  827. return 0;
  828. data = elevator_init_queue(q, e);
  829. if (!data) {
  830. kobject_put(&e->kobj);
  831. return 0;
  832. }
  833. /*
  834. * Turn on BYPASS and drain all requests w/ elevator private data
  835. */
  836. spin_lock_irq(q->queue_lock);
  837. set_bit(QUEUE_FLAG_ELVSWITCH, &q->queue_flags);
  838. elv_drain_elevator(q);
  839. while (q->rq.elvpriv) {
  840. blk_remove_plug(q);
  841. q->request_fn(q);
  842. spin_unlock_irq(q->queue_lock);
  843. msleep(10);
  844. spin_lock_irq(q->queue_lock);
  845. elv_drain_elevator(q);
  846. }
  847. /*
  848. * Remember old elevator.
  849. */
  850. old_elevator = q->elevator;
  851. /*
  852. * attach and start new elevator
  853. */
  854. elevator_attach(q, e, data);
  855. spin_unlock_irq(q->queue_lock);
  856. __elv_unregister_queue(old_elevator);
  857. if (elv_register_queue(q))
  858. goto fail_register;
  859. /*
  860. * finally exit old elevator and turn off BYPASS.
  861. */
  862. elevator_exit(old_elevator);
  863. clear_bit(QUEUE_FLAG_ELVSWITCH, &q->queue_flags);
  864. return 1;
  865. fail_register:
  866. /*
  867. * switch failed, exit the new io scheduler and reattach the old
  868. * one again (along with re-adding the sysfs dir)
  869. */
  870. elevator_exit(e);
  871. q->elevator = old_elevator;
  872. elv_register_queue(q);
  873. clear_bit(QUEUE_FLAG_ELVSWITCH, &q->queue_flags);
  874. return 0;
  875. }
  876. ssize_t elv_iosched_store(request_queue_t *q, const char *name, size_t count)
  877. {
  878. char elevator_name[ELV_NAME_MAX];
  879. size_t len;
  880. struct elevator_type *e;
  881. elevator_name[sizeof(elevator_name) - 1] = '\0';
  882. strncpy(elevator_name, name, sizeof(elevator_name) - 1);
  883. len = strlen(elevator_name);
  884. if (len && elevator_name[len - 1] == '\n')
  885. elevator_name[len - 1] = '\0';
  886. e = elevator_get(elevator_name);
  887. if (!e) {
  888. printk(KERN_ERR "elevator: type %s not found\n", elevator_name);
  889. return -EINVAL;
  890. }
  891. if (!strcmp(elevator_name, q->elevator->elevator_type->elevator_name)) {
  892. elevator_put(e);
  893. return count;
  894. }
  895. if (!elevator_switch(q, e))
  896. printk(KERN_ERR "elevator: switch to %s failed\n",elevator_name);
  897. return count;
  898. }
  899. ssize_t elv_iosched_show(request_queue_t *q, char *name)
  900. {
  901. elevator_t *e = q->elevator;
  902. struct elevator_type *elv = e->elevator_type;
  903. struct elevator_type *__e;
  904. int len = 0;
  905. spin_lock(&elv_list_lock);
  906. list_for_each_entry(__e, &elv_list, list) {
  907. if (!strcmp(elv->elevator_name, __e->elevator_name))
  908. len += sprintf(name+len, "[%s] ", elv->elevator_name);
  909. else
  910. len += sprintf(name+len, "%s ", __e->elevator_name);
  911. }
  912. spin_unlock(&elv_list_lock);
  913. len += sprintf(len+name, "\n");
  914. return len;
  915. }
  916. struct request *elv_rb_former_request(request_queue_t *q, struct request *rq)
  917. {
  918. struct rb_node *rbprev = rb_prev(&rq->rb_node);
  919. if (rbprev)
  920. return rb_entry_rq(rbprev);
  921. return NULL;
  922. }
  923. EXPORT_SYMBOL(elv_rb_former_request);
  924. struct request *elv_rb_latter_request(request_queue_t *q, struct request *rq)
  925. {
  926. struct rb_node *rbnext = rb_next(&rq->rb_node);
  927. if (rbnext)
  928. return rb_entry_rq(rbnext);
  929. return NULL;
  930. }
  931. EXPORT_SYMBOL(elv_rb_latter_request);