elevator.c 25 KB

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