File: /usr/src/linux/drivers/block/elevator.c
1 /*
2 * linux/drivers/block/elevator.c
3 *
4 * Block device elevator/IO-scheduler.
5 *
6 * Copyright (C) 2000 Andrea Arcangeli <andrea@suse.de> SuSE
7 *
8 * 30042000 Jens Axboe <axboe@suse.de> :
9 *
10 * Split the elevator a bit so that it is possible to choose a different
11 * one or even write a new "plug in". There are three pieces:
12 * - elevator_fn, inserts a new request in the queue list
13 * - elevator_merge_fn, decides whether a new buffer can be merged with
14 * an existing request
15 * - elevator_dequeue_fn, called when a request is taken off the active list
16 *
17 * 20082000 Dave Jones <davej@suse.de> :
18 * Removed tests for max-bomb-segments, which was breaking elvtune
19 * when run without -bN
20 *
21 */
22
23 #include <linux/fs.h>
24 #include <linux/blkdev.h>
25 #include <linux/elevator.h>
26 #include <linux/blk.h>
27 #include <linux/module.h>
28 #include <asm/uaccess.h>
29
30 /*
31 * This is a bit tricky. It's given that bh and rq are for the same
32 * device, but the next request might of course not be. Run through
33 * the tests below to check if we want to insert here if we can't merge
34 * bh into an existing request
35 */
36 inline int bh_rq_in_between(struct buffer_head *bh, struct request *rq,
37 struct list_head *head)
38 {
39 struct list_head *next;
40 struct request *next_rq;
41
42 next = rq->queue.next;
43 if (next == head)
44 return 0;
45
46 /*
47 * if the device is different (usually on a different partition),
48 * just check if bh is after rq
49 */
50 next_rq = blkdev_entry_to_request(next);
51 if (next_rq->rq_dev != rq->rq_dev)
52 return bh->b_rsector > rq->sector;
53
54 /*
55 * ok, rq, next_rq and bh are on the same device. if bh is in between
56 * the two, this is the sweet spot
57 */
58 if (bh->b_rsector < next_rq->sector && bh->b_rsector > rq->sector)
59 return 1;
60
61 /*
62 * next_rq is ordered wrt rq, but bh is not in between the two
63 */
64 if (next_rq->sector > rq->sector)
65 return 0;
66
67 /*
68 * next_rq and rq not ordered, if we happen to be either before
69 * next_rq or after rq insert here anyway
70 */
71 if (bh->b_rsector > rq->sector || bh->b_rsector < next_rq->sector)
72 return 1;
73
74 return 0;
75 }
76
77
78 int elevator_linus_merge(request_queue_t *q, struct request **req,
79 struct list_head * head,
80 struct buffer_head *bh, int rw,
81 int max_sectors)
82 {
83 struct list_head *entry = &q->queue_head;
84 unsigned int count = bh->b_size >> 9, ret = ELEVATOR_NO_MERGE;
85
86 while ((entry = entry->prev) != head) {
87 struct request *__rq = blkdev_entry_to_request(entry);
88
89 /*
90 * simply "aging" of requests in queue
91 */
92 if (__rq->elevator_sequence-- <= 0)
93 break;
94
95 if (__rq->waiting)
96 continue;
97 if (__rq->rq_dev != bh->b_rdev)
98 continue;
99 if (!*req && bh_rq_in_between(bh, __rq, &q->queue_head))
100 *req = __rq;
101 if (__rq->cmd != rw)
102 continue;
103 if (__rq->nr_sectors + count > max_sectors)
104 continue;
105 if (__rq->elevator_sequence < count)
106 break;
107 if (__rq->sector + __rq->nr_sectors == bh->b_rsector) {
108 ret = ELEVATOR_BACK_MERGE;
109 *req = __rq;
110 break;
111 } else if (__rq->sector - count == bh->b_rsector) {
112 ret = ELEVATOR_FRONT_MERGE;
113 __rq->elevator_sequence -= count;
114 *req = __rq;
115 break;
116 }
117 }
118
119 return ret;
120 }
121
122 void elevator_linus_merge_cleanup(request_queue_t *q, struct request *req, int count)
123 {
124 struct list_head *entry = &req->queue, *head = &q->queue_head;
125
126 /*
127 * second pass scan of requests that got passed over, if any
128 */
129 while ((entry = entry->next) != head) {
130 struct request *tmp = blkdev_entry_to_request(entry);
131 tmp->elevator_sequence -= count;
132 }
133 }
134
135 void elevator_linus_merge_req(struct request *req, struct request *next)
136 {
137 if (next->elevator_sequence < req->elevator_sequence)
138 req->elevator_sequence = next->elevator_sequence;
139 }
140
141 /*
142 * See if we can find a request that this buffer can be coalesced with.
143 */
144 int elevator_noop_merge(request_queue_t *q, struct request **req,
145 struct list_head * head,
146 struct buffer_head *bh, int rw,
147 int max_sectors)
148 {
149 struct list_head *entry;
150 unsigned int count = bh->b_size >> 9;
151
152 if (list_empty(&q->queue_head))
153 return ELEVATOR_NO_MERGE;
154
155 entry = &q->queue_head;
156 while ((entry = entry->prev) != head) {
157 struct request *__rq = blkdev_entry_to_request(entry);
158
159 if (__rq->cmd != rw)
160 continue;
161 if (__rq->rq_dev != bh->b_rdev)
162 continue;
163 if (__rq->nr_sectors + count > max_sectors)
164 continue;
165 if (__rq->waiting)
166 continue;
167 if (__rq->sector + __rq->nr_sectors == bh->b_rsector) {
168 *req = __rq;
169 return ELEVATOR_BACK_MERGE;
170 } else if (__rq->sector - count == bh->b_rsector) {
171 *req = __rq;
172 return ELEVATOR_FRONT_MERGE;
173 }
174 }
175
176 *req = blkdev_entry_to_request(q->queue_head.prev);
177 return ELEVATOR_NO_MERGE;
178 }
179
180 void elevator_noop_merge_cleanup(request_queue_t *q, struct request *req, int count) {}
181
182 void elevator_noop_merge_req(struct request *req, struct request *next) {}
183
184 int blkelvget_ioctl(elevator_t * elevator, blkelv_ioctl_arg_t * arg)
185 {
186 blkelv_ioctl_arg_t output;
187
188 output.queue_ID = elevator->queue_ID;
189 output.read_latency = elevator->read_latency;
190 output.write_latency = elevator->write_latency;
191 output.max_bomb_segments = 0;
192
193 if (copy_to_user(arg, &output, sizeof(blkelv_ioctl_arg_t)))
194 return -EFAULT;
195
196 return 0;
197 }
198
199 int blkelvset_ioctl(elevator_t * elevator, const blkelv_ioctl_arg_t * arg)
200 {
201 blkelv_ioctl_arg_t input;
202
203 if (copy_from_user(&input, arg, sizeof(blkelv_ioctl_arg_t)))
204 return -EFAULT;
205
206 if (input.read_latency < 0)
207 return -EINVAL;
208 if (input.write_latency < 0)
209 return -EINVAL;
210
211 elevator->read_latency = input.read_latency;
212 elevator->write_latency = input.write_latency;
213 return 0;
214 }
215
216 void elevator_init(elevator_t * elevator, elevator_t type)
217 {
218 static unsigned int queue_ID;
219
220 *elevator = type;
221 elevator->queue_ID = queue_ID++;
222 }
223