deadline-iosched.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485
  1. /*
  2. * Deadline i/o scheduler.
  3. *
  4. * Copyright (C) 2002 Jens Axboe <axboe@kernel.dk>
  5. */
  6. #include <linux/kernel.h>
  7. #include <linux/fs.h>
  8. #include <linux/blkdev.h>
  9. #include <linux/elevator.h>
  10. #include <linux/bio.h>
  11. #include <linux/module.h>
  12. #include <linux/slab.h>
  13. #include <linux/init.h>
  14. #include <linux/compiler.h>
  15. #include <linux/rbtree.h>
  16. /*
  17. * See Documentation/block/deadline-iosched.txt
  18. */
  19. static const int read_expire = HZ / 2; /* max time before a read is submitted. */
  20. static const int write_expire = 5 * HZ; /* ditto for writes, these limits are SOFT! */
  21. static const int writes_starved = 2; /* max times reads can starve a write */
  22. static const int fifo_batch = 16; /* # of sequential requests treated as one
  23. by the above parameters. For throughput. */
  24. struct deadline_data {
  25. /*
  26. * run time data
  27. */
  28. /*
  29. * requests (deadline_rq s) are present on both sort_list and fifo_list
  30. */
  31. struct rb_root sort_list[2];
  32. struct list_head fifo_list[2];
  33. /*
  34. * next in sort order. read, write or both are NULL
  35. */
  36. struct request *next_rq[2];
  37. unsigned int batching; /* number of sequential requests made */
  38. sector_t last_sector; /* head position */
  39. unsigned int starved; /* times reads have starved writes */
  40. /*
  41. * settings that change how the i/o scheduler behaves
  42. */
  43. int fifo_expire[2];
  44. int fifo_batch;
  45. int writes_starved;
  46. int front_merges;
  47. };
  48. static void deadline_move_request(struct deadline_data *, struct request *);
  49. #define RQ_RB_ROOT(dd, rq) (&(dd)->sort_list[rq_data_dir((rq))])
  50. static void
  51. deadline_add_rq_rb(struct deadline_data *dd, struct request *rq)
  52. {
  53. struct rb_root *root = RQ_RB_ROOT(dd, rq);
  54. struct request *__alias;
  55. retry:
  56. __alias = elv_rb_add(root, rq);
  57. if (unlikely(__alias)) {
  58. deadline_move_request(dd, __alias);
  59. goto retry;
  60. }
  61. }
  62. static inline void
  63. deadline_del_rq_rb(struct deadline_data *dd, struct request *rq)
  64. {
  65. const int data_dir = rq_data_dir(rq);
  66. if (dd->next_rq[data_dir] == rq) {
  67. struct rb_node *rbnext = rb_next(&rq->rb_node);
  68. dd->next_rq[data_dir] = NULL;
  69. if (rbnext)
  70. dd->next_rq[data_dir] = rb_entry_rq(rbnext);
  71. }
  72. elv_rb_del(RQ_RB_ROOT(dd, rq), rq);
  73. }
  74. /*
  75. * add rq to rbtree and fifo
  76. */
  77. static void
  78. deadline_add_request(struct request_queue *q, struct request *rq)
  79. {
  80. struct deadline_data *dd = q->elevator->elevator_data;
  81. const int data_dir = rq_data_dir(rq);
  82. deadline_add_rq_rb(dd, rq);
  83. /*
  84. * set expire time (only used for reads) and add to fifo list
  85. */
  86. rq_set_fifo_time(rq, jiffies + dd->fifo_expire[data_dir]);
  87. list_add_tail(&rq->queuelist, &dd->fifo_list[data_dir]);
  88. }
  89. /*
  90. * remove rq from rbtree and fifo.
  91. */
  92. static void deadline_remove_request(request_queue_t *q, struct request *rq)
  93. {
  94. struct deadline_data *dd = q->elevator->elevator_data;
  95. rq_fifo_clear(rq);
  96. deadline_del_rq_rb(dd, rq);
  97. }
  98. static int
  99. deadline_merge(request_queue_t *q, struct request **req, struct bio *bio)
  100. {
  101. struct deadline_data *dd = q->elevator->elevator_data;
  102. struct request *__rq;
  103. int ret;
  104. /*
  105. * check for front merge
  106. */
  107. if (dd->front_merges) {
  108. sector_t sector = bio->bi_sector + bio_sectors(bio);
  109. __rq = elv_rb_find(&dd->sort_list[bio_data_dir(bio)], sector);
  110. if (__rq) {
  111. BUG_ON(sector != __rq->sector);
  112. if (elv_rq_merge_ok(__rq, bio)) {
  113. ret = ELEVATOR_FRONT_MERGE;
  114. goto out;
  115. }
  116. }
  117. }
  118. return ELEVATOR_NO_MERGE;
  119. out:
  120. *req = __rq;
  121. return ret;
  122. }
  123. static void deadline_merged_request(request_queue_t *q, struct request *req,
  124. int type)
  125. {
  126. struct deadline_data *dd = q->elevator->elevator_data;
  127. /*
  128. * if the merge was a front merge, we need to reposition request
  129. */
  130. if (type == ELEVATOR_FRONT_MERGE) {
  131. elv_rb_del(RQ_RB_ROOT(dd, req), req);
  132. deadline_add_rq_rb(dd, req);
  133. }
  134. }
  135. static void
  136. deadline_merged_requests(request_queue_t *q, struct request *req,
  137. struct request *next)
  138. {
  139. /*
  140. * if next expires before rq, assign its expire time to rq
  141. * and move into next position (next will be deleted) in fifo
  142. */
  143. if (!list_empty(&req->queuelist) && !list_empty(&next->queuelist)) {
  144. if (time_before(rq_fifo_time(next), rq_fifo_time(req))) {
  145. list_move(&req->queuelist, &next->queuelist);
  146. rq_set_fifo_time(req, rq_fifo_time(next));
  147. }
  148. }
  149. /*
  150. * kill knowledge of next, this one is a goner
  151. */
  152. deadline_remove_request(q, next);
  153. }
  154. /*
  155. * move request from sort list to dispatch queue.
  156. */
  157. static inline void
  158. deadline_move_to_dispatch(struct deadline_data *dd, struct request *rq)
  159. {
  160. request_queue_t *q = rq->q;
  161. deadline_remove_request(q, rq);
  162. elv_dispatch_add_tail(q, rq);
  163. }
  164. /*
  165. * move an entry to dispatch queue
  166. */
  167. static void
  168. deadline_move_request(struct deadline_data *dd, struct request *rq)
  169. {
  170. const int data_dir = rq_data_dir(rq);
  171. struct rb_node *rbnext = rb_next(&rq->rb_node);
  172. dd->next_rq[READ] = NULL;
  173. dd->next_rq[WRITE] = NULL;
  174. if (rbnext)
  175. dd->next_rq[data_dir] = rb_entry_rq(rbnext);
  176. dd->last_sector = rq->sector + rq->nr_sectors;
  177. /*
  178. * take it off the sort and fifo list, move
  179. * to dispatch queue
  180. */
  181. deadline_move_to_dispatch(dd, rq);
  182. }
  183. /*
  184. * deadline_check_fifo returns 0 if there are no expired reads on the fifo,
  185. * 1 otherwise. Requires !list_empty(&dd->fifo_list[data_dir])
  186. */
  187. static inline int deadline_check_fifo(struct deadline_data *dd, int ddir)
  188. {
  189. struct request *rq = rq_entry_fifo(dd->fifo_list[ddir].next);
  190. /*
  191. * rq is expired!
  192. */
  193. if (time_after(jiffies, rq_fifo_time(rq)))
  194. return 1;
  195. return 0;
  196. }
  197. /*
  198. * deadline_dispatch_requests selects the best request according to
  199. * read/write expire, fifo_batch, etc
  200. */
  201. static int deadline_dispatch_requests(request_queue_t *q, int force)
  202. {
  203. struct deadline_data *dd = q->elevator->elevator_data;
  204. const int reads = !list_empty(&dd->fifo_list[READ]);
  205. const int writes = !list_empty(&dd->fifo_list[WRITE]);
  206. struct request *rq;
  207. int data_dir;
  208. /*
  209. * batches are currently reads XOR writes
  210. */
  211. if (dd->next_rq[WRITE])
  212. rq = dd->next_rq[WRITE];
  213. else
  214. rq = dd->next_rq[READ];
  215. if (rq) {
  216. /* we have a "next request" */
  217. if (dd->last_sector != rq->sector)
  218. /* end the batch on a non sequential request */
  219. dd->batching += dd->fifo_batch;
  220. if (dd->batching < dd->fifo_batch)
  221. /* we are still entitled to batch */
  222. goto dispatch_request;
  223. }
  224. /*
  225. * at this point we are not running a batch. select the appropriate
  226. * data direction (read / write)
  227. */
  228. if (reads) {
  229. BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[READ]));
  230. if (writes && (dd->starved++ >= dd->writes_starved))
  231. goto dispatch_writes;
  232. data_dir = READ;
  233. goto dispatch_find_request;
  234. }
  235. /*
  236. * there are either no reads or writes have been starved
  237. */
  238. if (writes) {
  239. dispatch_writes:
  240. BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[WRITE]));
  241. dd->starved = 0;
  242. data_dir = WRITE;
  243. goto dispatch_find_request;
  244. }
  245. return 0;
  246. dispatch_find_request:
  247. /*
  248. * we are not running a batch, find best request for selected data_dir
  249. */
  250. if (deadline_check_fifo(dd, data_dir)) {
  251. /* An expired request exists - satisfy it */
  252. dd->batching = 0;
  253. rq = rq_entry_fifo(dd->fifo_list[data_dir].next);
  254. } else if (dd->next_rq[data_dir]) {
  255. /*
  256. * The last req was the same dir and we have a next request in
  257. * sort order. No expired requests so continue on from here.
  258. */
  259. rq = dd->next_rq[data_dir];
  260. } else {
  261. struct rb_node *node;
  262. /*
  263. * The last req was the other direction or we have run out of
  264. * higher-sectored requests. Go back to the lowest sectored
  265. * request (1 way elevator) and start a new batch.
  266. */
  267. dd->batching = 0;
  268. node = rb_first(&dd->sort_list[data_dir]);
  269. if (node)
  270. rq = rb_entry_rq(node);
  271. }
  272. dispatch_request:
  273. /*
  274. * rq is the selected appropriate request.
  275. */
  276. dd->batching++;
  277. deadline_move_request(dd, rq);
  278. return 1;
  279. }
  280. static int deadline_queue_empty(request_queue_t *q)
  281. {
  282. struct deadline_data *dd = q->elevator->elevator_data;
  283. return list_empty(&dd->fifo_list[WRITE])
  284. && list_empty(&dd->fifo_list[READ]);
  285. }
  286. static void deadline_exit_queue(elevator_t *e)
  287. {
  288. struct deadline_data *dd = e->elevator_data;
  289. BUG_ON(!list_empty(&dd->fifo_list[READ]));
  290. BUG_ON(!list_empty(&dd->fifo_list[WRITE]));
  291. kfree(dd);
  292. }
  293. /*
  294. * initialize elevator private data (deadline_data).
  295. */
  296. static void *deadline_init_queue(request_queue_t *q)
  297. {
  298. struct deadline_data *dd;
  299. dd = kmalloc_node(sizeof(*dd), GFP_KERNEL, q->node);
  300. if (!dd)
  301. return NULL;
  302. memset(dd, 0, sizeof(*dd));
  303. INIT_LIST_HEAD(&dd->fifo_list[READ]);
  304. INIT_LIST_HEAD(&dd->fifo_list[WRITE]);
  305. dd->sort_list[READ] = RB_ROOT;
  306. dd->sort_list[WRITE] = RB_ROOT;
  307. dd->fifo_expire[READ] = read_expire;
  308. dd->fifo_expire[WRITE] = write_expire;
  309. dd->writes_starved = writes_starved;
  310. dd->front_merges = 1;
  311. dd->fifo_batch = fifo_batch;
  312. return dd;
  313. }
  314. /*
  315. * sysfs parts below
  316. */
  317. static ssize_t
  318. deadline_var_show(int var, char *page)
  319. {
  320. return sprintf(page, "%d\n", var);
  321. }
  322. static ssize_t
  323. deadline_var_store(int *var, const char *page, size_t count)
  324. {
  325. char *p = (char *) page;
  326. *var = simple_strtol(p, &p, 10);
  327. return count;
  328. }
  329. #define SHOW_FUNCTION(__FUNC, __VAR, __CONV) \
  330. static ssize_t __FUNC(elevator_t *e, char *page) \
  331. { \
  332. struct deadline_data *dd = e->elevator_data; \
  333. int __data = __VAR; \
  334. if (__CONV) \
  335. __data = jiffies_to_msecs(__data); \
  336. return deadline_var_show(__data, (page)); \
  337. }
  338. SHOW_FUNCTION(deadline_read_expire_show, dd->fifo_expire[READ], 1);
  339. SHOW_FUNCTION(deadline_write_expire_show, dd->fifo_expire[WRITE], 1);
  340. SHOW_FUNCTION(deadline_writes_starved_show, dd->writes_starved, 0);
  341. SHOW_FUNCTION(deadline_front_merges_show, dd->front_merges, 0);
  342. SHOW_FUNCTION(deadline_fifo_batch_show, dd->fifo_batch, 0);
  343. #undef SHOW_FUNCTION
  344. #define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV) \
  345. static ssize_t __FUNC(elevator_t *e, const char *page, size_t count) \
  346. { \
  347. struct deadline_data *dd = e->elevator_data; \
  348. int __data; \
  349. int ret = deadline_var_store(&__data, (page), count); \
  350. if (__data < (MIN)) \
  351. __data = (MIN); \
  352. else if (__data > (MAX)) \
  353. __data = (MAX); \
  354. if (__CONV) \
  355. *(__PTR) = msecs_to_jiffies(__data); \
  356. else \
  357. *(__PTR) = __data; \
  358. return ret; \
  359. }
  360. STORE_FUNCTION(deadline_read_expire_store, &dd->fifo_expire[READ], 0, INT_MAX, 1);
  361. STORE_FUNCTION(deadline_write_expire_store, &dd->fifo_expire[WRITE], 0, INT_MAX, 1);
  362. STORE_FUNCTION(deadline_writes_starved_store, &dd->writes_starved, INT_MIN, INT_MAX, 0);
  363. STORE_FUNCTION(deadline_front_merges_store, &dd->front_merges, 0, 1, 0);
  364. STORE_FUNCTION(deadline_fifo_batch_store, &dd->fifo_batch, 0, INT_MAX, 0);
  365. #undef STORE_FUNCTION
  366. #define DD_ATTR(name) \
  367. __ATTR(name, S_IRUGO|S_IWUSR, deadline_##name##_show, \
  368. deadline_##name##_store)
  369. static struct elv_fs_entry deadline_attrs[] = {
  370. DD_ATTR(read_expire),
  371. DD_ATTR(write_expire),
  372. DD_ATTR(writes_starved),
  373. DD_ATTR(front_merges),
  374. DD_ATTR(fifo_batch),
  375. __ATTR_NULL
  376. };
  377. static struct elevator_type iosched_deadline = {
  378. .ops = {
  379. .elevator_merge_fn = deadline_merge,
  380. .elevator_merged_fn = deadline_merged_request,
  381. .elevator_merge_req_fn = deadline_merged_requests,
  382. .elevator_dispatch_fn = deadline_dispatch_requests,
  383. .elevator_add_req_fn = deadline_add_request,
  384. .elevator_queue_empty_fn = deadline_queue_empty,
  385. .elevator_former_req_fn = elv_rb_former_request,
  386. .elevator_latter_req_fn = elv_rb_latter_request,
  387. .elevator_init_fn = deadline_init_queue,
  388. .elevator_exit_fn = deadline_exit_queue,
  389. },
  390. .elevator_attrs = deadline_attrs,
  391. .elevator_name = "deadline",
  392. .elevator_owner = THIS_MODULE,
  393. };
  394. static int __init deadline_init(void)
  395. {
  396. return elv_register(&iosched_deadline);
  397. }
  398. static void __exit deadline_exit(void)
  399. {
  400. elv_unregister(&iosched_deadline);
  401. }
  402. module_init(deadline_init);
  403. module_exit(deadline_exit);
  404. MODULE_AUTHOR("Jens Axboe");
  405. MODULE_LICENSE("GPL");
  406. MODULE_DESCRIPTION("deadline IO scheduler");