aboutsummaryrefslogtreecommitdiffstats
path: root/drivers/block/elevator.c
diff options
context:
space:
mode:
authorTejun Heo <htejun@gmail.com>2005-10-20 10:23:44 -0400
committerJens Axboe <axboe@nelson.home.kernel.dk>2005-10-28 02:44:24 -0400
commit8922e16cf6269e668123acb1ae1fdc62b7a3a4fc (patch)
tree272bff0b53bf6fe4a7787728a45a26a282ba2976 /drivers/block/elevator.c
parent2824bc9328467127083c1325f54b67d298c333b2 (diff)
[PATCH] 01/05 Implement generic dispatch queue
Implements generic dispatch queue which can replace all dispatch queues implemented by each iosched. This reduces code duplication, eases enforcing semantics over dispatch queue, and simplifies specific ioscheds. Signed-off-by: Tejun Heo <htejun@gmail.com> Signed-off-by: Jens Axboe <axboe@suse.de>
Diffstat (limited to 'drivers/block/elevator.c')
-rw-r--r--drivers/block/elevator.c242
1 files changed, 170 insertions, 72 deletions
diff --git a/drivers/block/elevator.c b/drivers/block/elevator.c
index 4144f30d82a9..a27555908d35 100644
--- a/drivers/block/elevator.c
+++ b/drivers/block/elevator.c
@@ -40,6 +40,11 @@
40static DEFINE_SPINLOCK(elv_list_lock); 40static DEFINE_SPINLOCK(elv_list_lock);
41static LIST_HEAD(elv_list); 41static LIST_HEAD(elv_list);
42 42
43static inline sector_t rq_last_sector(struct request *rq)
44{
45 return rq->sector + rq->nr_sectors;
46}
47
43/* 48/*
44 * can we safely merge with this request? 49 * can we safely merge with this request?
45 */ 50 */
@@ -143,6 +148,9 @@ static int elevator_attach(request_queue_t *q, struct elevator_type *e,
143 INIT_LIST_HEAD(&q->queue_head); 148 INIT_LIST_HEAD(&q->queue_head);
144 q->last_merge = NULL; 149 q->last_merge = NULL;
145 q->elevator = eq; 150 q->elevator = eq;
151 q->last_sector = 0;
152 q->boundary_rq = NULL;
153 q->max_back_kb = 0;
146 154
147 if (eq->ops->elevator_init_fn) 155 if (eq->ops->elevator_init_fn)
148 ret = eq->ops->elevator_init_fn(q, eq); 156 ret = eq->ops->elevator_init_fn(q, eq);
@@ -225,6 +233,48 @@ void elevator_exit(elevator_t *e)
225 kfree(e); 233 kfree(e);
226} 234}
227 235
236/*
237 * Insert rq into dispatch queue of q. Queue lock must be held on
238 * entry. If sort != 0, rq is sort-inserted; otherwise, rq will be
239 * appended to the dispatch queue. To be used by specific elevators.
240 */
241void elv_dispatch_insert(request_queue_t *q, struct request *rq, int sort)
242{
243 sector_t boundary;
244 unsigned max_back;
245 struct list_head *entry;
246
247 if (!sort) {
248 /* Specific elevator is performing sort. Step away. */
249 q->last_sector = rq_last_sector(rq);
250 q->boundary_rq = rq;
251 list_add_tail(&rq->queuelist, &q->queue_head);
252 return;
253 }
254
255 boundary = q->last_sector;
256 max_back = q->max_back_kb * 2;
257 boundary = boundary > max_back ? boundary - max_back : 0;
258
259 list_for_each_prev(entry, &q->queue_head) {
260 struct request *pos = list_entry_rq(entry);
261
262 if (pos->flags & (REQ_SOFTBARRIER|REQ_HARDBARRIER|REQ_STARTED))
263 break;
264 if (rq->sector >= boundary) {
265 if (pos->sector < boundary)
266 continue;
267 } else {
268 if (pos->sector >= boundary)
269 break;
270 }
271 if (rq->sector >= pos->sector)
272 break;
273 }
274
275 list_add(&rq->queuelist, entry);
276}
277
228int elv_merge(request_queue_t *q, struct request **req, struct bio *bio) 278int elv_merge(request_queue_t *q, struct request **req, struct bio *bio)
229{ 279{
230 elevator_t *e = q->elevator; 280 elevator_t *e = q->elevator;
@@ -255,13 +305,7 @@ void elv_merge_requests(request_queue_t *q, struct request *rq,
255 e->ops->elevator_merge_req_fn(q, rq, next); 305 e->ops->elevator_merge_req_fn(q, rq, next);
256} 306}
257 307
258/* 308void elv_requeue_request(request_queue_t *q, struct request *rq)
259 * For careful internal use by the block layer. Essentially the same as
260 * a requeue in that it tells the io scheduler that this request is not
261 * active in the driver or hardware anymore, but we don't want the request
262 * added back to the scheduler. Function is not exported.
263 */
264void elv_deactivate_request(request_queue_t *q, struct request *rq)
265{ 309{
266 elevator_t *e = q->elevator; 310 elevator_t *e = q->elevator;
267 311
@@ -269,19 +313,14 @@ void elv_deactivate_request(request_queue_t *q, struct request *rq)
269 * it already went through dequeue, we need to decrement the 313 * it already went through dequeue, we need to decrement the
270 * in_flight count again 314 * in_flight count again
271 */ 315 */
272 if (blk_account_rq(rq)) 316 if (blk_account_rq(rq)) {
273 q->in_flight--; 317 q->in_flight--;
318 if (blk_sorted_rq(rq) && e->ops->elevator_deactivate_req_fn)
319 e->ops->elevator_deactivate_req_fn(q, rq);
320 }
274 321
275 rq->flags &= ~REQ_STARTED; 322 rq->flags &= ~REQ_STARTED;
276 323
277 if (e->ops->elevator_deactivate_req_fn)
278 e->ops->elevator_deactivate_req_fn(q, rq);
279}
280
281void elv_requeue_request(request_queue_t *q, struct request *rq)
282{
283 elv_deactivate_request(q, rq);
284
285 /* 324 /*
286 * if this is the flush, requeue the original instead and drop the flush 325 * if this is the flush, requeue the original instead and drop the flush
287 */ 326 */
@@ -290,55 +329,89 @@ void elv_requeue_request(request_queue_t *q, struct request *rq)
290 rq = rq->end_io_data; 329 rq = rq->end_io_data;
291 } 330 }
292 331
293 /* 332 __elv_add_request(q, rq, ELEVATOR_INSERT_FRONT, 0);
294 * the request is prepped and may have some resources allocated.
295 * allowing unprepped requests to pass this one may cause resource
296 * deadlock. turn on softbarrier.
297 */
298 rq->flags |= REQ_SOFTBARRIER;
299
300 /*
301 * if iosched has an explicit requeue hook, then use that. otherwise
302 * just put the request at the front of the queue
303 */
304 if (q->elevator->ops->elevator_requeue_req_fn)
305 q->elevator->ops->elevator_requeue_req_fn(q, rq);
306 else
307 __elv_add_request(q, rq, ELEVATOR_INSERT_FRONT, 0);
308} 333}
309 334
310void __elv_add_request(request_queue_t *q, struct request *rq, int where, 335void __elv_add_request(request_queue_t *q, struct request *rq, int where,
311 int plug) 336 int plug)
312{ 337{
313 /* 338 if (rq->flags & (REQ_SOFTBARRIER | REQ_HARDBARRIER)) {
314 * barriers implicitly indicate back insertion 339 /*
315 */ 340 * barriers implicitly indicate back insertion
316 if (rq->flags & (REQ_SOFTBARRIER | REQ_HARDBARRIER) && 341 */
317 where == ELEVATOR_INSERT_SORT) 342 if (where == ELEVATOR_INSERT_SORT)
318 where = ELEVATOR_INSERT_BACK; 343 where = ELEVATOR_INSERT_BACK;
344
345 /*
346 * this request is scheduling boundary, update last_sector
347 */
348 if (blk_fs_request(rq)) {
349 q->last_sector = rq_last_sector(rq);
350 q->boundary_rq = rq;
351 }
352 }
319 353
320 if (plug) 354 if (plug)
321 blk_plug_device(q); 355 blk_plug_device(q);
322 356
323 rq->q = q; 357 rq->q = q;
324 358
325 if (!test_bit(QUEUE_FLAG_DRAIN, &q->queue_flags)) { 359 if (unlikely(test_bit(QUEUE_FLAG_DRAIN, &q->queue_flags))) {
326 q->elevator->ops->elevator_add_req_fn(q, rq, where);
327
328 if (blk_queue_plugged(q)) {
329 int nrq = q->rq.count[READ] + q->rq.count[WRITE]
330 - q->in_flight;
331
332 if (nrq >= q->unplug_thresh)
333 __generic_unplug_device(q);
334 }
335 } else
336 /* 360 /*
337 * if drain is set, store the request "locally". when the drain 361 * if drain is set, store the request "locally". when the drain
338 * is finished, the requests will be handed ordered to the io 362 * is finished, the requests will be handed ordered to the io
339 * scheduler 363 * scheduler
340 */ 364 */
341 list_add_tail(&rq->queuelist, &q->drain_list); 365 list_add_tail(&rq->queuelist, &q->drain_list);
366 return;
367 }
368
369 switch (where) {
370 case ELEVATOR_INSERT_FRONT:
371 rq->flags |= REQ_SOFTBARRIER;
372
373 list_add(&rq->queuelist, &q->queue_head);
374 break;
375
376 case ELEVATOR_INSERT_BACK:
377 rq->flags |= REQ_SOFTBARRIER;
378
379 while (q->elevator->ops->elevator_dispatch_fn(q, 1))
380 ;
381 list_add_tail(&rq->queuelist, &q->queue_head);
382 /*
383 * We kick the queue here for the following reasons.
384 * - The elevator might have returned NULL previously
385 * to delay requests and returned them now. As the
386 * queue wasn't empty before this request, ll_rw_blk
387 * won't run the queue on return, resulting in hang.
388 * - Usually, back inserted requests won't be merged
389 * with anything. There's no point in delaying queue
390 * processing.
391 */
392 blk_remove_plug(q);
393 q->request_fn(q);
394 break;
395
396 case ELEVATOR_INSERT_SORT:
397 BUG_ON(!blk_fs_request(rq));
398 rq->flags |= REQ_SORTED;
399 q->elevator->ops->elevator_add_req_fn(q, rq);
400 break;
401
402 default:
403 printk(KERN_ERR "%s: bad insertion point %d\n",
404 __FUNCTION__, where);
405 BUG();
406 }
407
408 if (blk_queue_plugged(q)) {
409 int nrq = q->rq.count[READ] + q->rq.count[WRITE]
410 - q->in_flight;
411
412 if (nrq >= q->unplug_thresh)
413 __generic_unplug_device(q);
414 }
342} 415}
343 416
344void elv_add_request(request_queue_t *q, struct request *rq, int where, 417void elv_add_request(request_queue_t *q, struct request *rq, int where,
@@ -353,13 +426,19 @@ void elv_add_request(request_queue_t *q, struct request *rq, int where,
353 426
354static inline struct request *__elv_next_request(request_queue_t *q) 427static inline struct request *__elv_next_request(request_queue_t *q)
355{ 428{
356 struct request *rq = q->elevator->ops->elevator_next_req_fn(q); 429 struct request *rq;
430
431 if (unlikely(list_empty(&q->queue_head) &&
432 !q->elevator->ops->elevator_dispatch_fn(q, 0)))
433 return NULL;
434
435 rq = list_entry_rq(q->queue_head.next);
357 436
358 /* 437 /*
359 * if this is a barrier write and the device has to issue a 438 * if this is a barrier write and the device has to issue a
360 * flush sequence to support it, check how far we are 439 * flush sequence to support it, check how far we are
361 */ 440 */
362 if (rq && blk_fs_request(rq) && blk_barrier_rq(rq)) { 441 if (blk_fs_request(rq) && blk_barrier_rq(rq)) {
363 BUG_ON(q->ordered == QUEUE_ORDERED_NONE); 442 BUG_ON(q->ordered == QUEUE_ORDERED_NONE);
364 443
365 if (q->ordered == QUEUE_ORDERED_FLUSH && 444 if (q->ordered == QUEUE_ORDERED_FLUSH &&
@@ -376,16 +455,34 @@ struct request *elv_next_request(request_queue_t *q)
376 int ret; 455 int ret;
377 456
378 while ((rq = __elv_next_request(q)) != NULL) { 457 while ((rq = __elv_next_request(q)) != NULL) {
379 /* 458 if (!(rq->flags & REQ_STARTED)) {
380 * just mark as started even if we don't start it, a request 459 elevator_t *e = q->elevator;
381 * that has been delayed should not be passed by new incoming 460
382 * requests 461 /*
383 */ 462 * This is the first time the device driver
384 rq->flags |= REQ_STARTED; 463 * sees this request (possibly after
464 * requeueing). Notify IO scheduler.
465 */
466 if (blk_sorted_rq(rq) &&
467 e->ops->elevator_activate_req_fn)
468 e->ops->elevator_activate_req_fn(q, rq);
469
470 /*
471 * just mark as started even if we don't start
472 * it, a request that has been delayed should
473 * not be passed by new incoming requests
474 */
475 rq->flags |= REQ_STARTED;
476 }
385 477
386 if (rq == q->last_merge) 478 if (rq == q->last_merge)
387 q->last_merge = NULL; 479 q->last_merge = NULL;
388 480
481 if (!q->boundary_rq || q->boundary_rq == rq) {
482 q->last_sector = rq_last_sector(rq);
483 q->boundary_rq = NULL;
484 }
485
389 if ((rq->flags & REQ_DONTPREP) || !q->prep_rq_fn) 486 if ((rq->flags & REQ_DONTPREP) || !q->prep_rq_fn)
390 break; 487 break;
391 488
@@ -396,9 +493,9 @@ struct request *elv_next_request(request_queue_t *q)
396 /* 493 /*
397 * the request may have been (partially) prepped. 494 * the request may have been (partially) prepped.
398 * we need to keep this request in the front to 495 * we need to keep this request in the front to
399 * avoid resource deadlock. turn on softbarrier. 496 * avoid resource deadlock. REQ_STARTED will
497 * prevent other fs requests from passing this one.
400 */ 498 */
401 rq->flags |= REQ_SOFTBARRIER;
402 rq = NULL; 499 rq = NULL;
403 break; 500 break;
404 } else if (ret == BLKPREP_KILL) { 501 } else if (ret == BLKPREP_KILL) {
@@ -421,16 +518,16 @@ struct request *elv_next_request(request_queue_t *q)
421 return rq; 518 return rq;
422} 519}
423 520
424void elv_remove_request(request_queue_t *q, struct request *rq) 521void elv_dequeue_request(request_queue_t *q, struct request *rq)
425{ 522{
426 elevator_t *e = q->elevator; 523 BUG_ON(list_empty(&rq->queuelist));
524
525 list_del_init(&rq->queuelist);
427 526
428 /* 527 /*
429 * the time frame between a request being removed from the lists 528 * the time frame between a request being removed from the lists
430 * and to it is freed is accounted as io that is in progress at 529 * and to it is freed is accounted as io that is in progress at
431 * the driver side. note that we only account requests that the 530 * the driver side.
432 * driver has seen (REQ_STARTED set), to avoid false accounting
433 * for request-request merges
434 */ 531 */
435 if (blk_account_rq(rq)) 532 if (blk_account_rq(rq))
436 q->in_flight++; 533 q->in_flight++;
@@ -444,19 +541,19 @@ void elv_remove_request(request_queue_t *q, struct request *rq)
444 */ 541 */
445 if (rq == q->last_merge) 542 if (rq == q->last_merge)
446 q->last_merge = NULL; 543 q->last_merge = NULL;
447
448 if (e->ops->elevator_remove_req_fn)
449 e->ops->elevator_remove_req_fn(q, rq);
450} 544}
451 545
452int elv_queue_empty(request_queue_t *q) 546int elv_queue_empty(request_queue_t *q)
453{ 547{
454 elevator_t *e = q->elevator; 548 elevator_t *e = q->elevator;
455 549
550 if (!list_empty(&q->queue_head))
551 return 0;
552
456 if (e->ops->elevator_queue_empty_fn) 553 if (e->ops->elevator_queue_empty_fn)
457 return e->ops->elevator_queue_empty_fn(q); 554 return e->ops->elevator_queue_empty_fn(q);
458 555
459 return list_empty(&q->queue_head); 556 return 1;
460} 557}
461 558
462struct request *elv_latter_request(request_queue_t *q, struct request *rq) 559struct request *elv_latter_request(request_queue_t *q, struct request *rq)
@@ -528,11 +625,11 @@ void elv_completed_request(request_queue_t *q, struct request *rq)
528 /* 625 /*
529 * request is released from the driver, io must be done 626 * request is released from the driver, io must be done
530 */ 627 */
531 if (blk_account_rq(rq)) 628 if (blk_account_rq(rq)) {
532 q->in_flight--; 629 q->in_flight--;
533 630 if (blk_sorted_rq(rq) && e->ops->elevator_completed_req_fn)
534 if (e->ops->elevator_completed_req_fn) 631 e->ops->elevator_completed_req_fn(q, rq);
535 e->ops->elevator_completed_req_fn(q, rq); 632 }
536} 633}
537 634
538int elv_register_queue(struct request_queue *q) 635int elv_register_queue(struct request_queue *q)
@@ -705,11 +802,12 @@ ssize_t elv_iosched_show(request_queue_t *q, char *name)
705 return len; 802 return len;
706} 803}
707 804
805EXPORT_SYMBOL(elv_dispatch_insert);
708EXPORT_SYMBOL(elv_add_request); 806EXPORT_SYMBOL(elv_add_request);
709EXPORT_SYMBOL(__elv_add_request); 807EXPORT_SYMBOL(__elv_add_request);
710EXPORT_SYMBOL(elv_requeue_request); 808EXPORT_SYMBOL(elv_requeue_request);
711EXPORT_SYMBOL(elv_next_request); 809EXPORT_SYMBOL(elv_next_request);
712EXPORT_SYMBOL(elv_remove_request); 810EXPORT_SYMBOL(elv_dequeue_request);
713EXPORT_SYMBOL(elv_queue_empty); 811EXPORT_SYMBOL(elv_queue_empty);
714EXPORT_SYMBOL(elv_completed_request); 812EXPORT_SYMBOL(elv_completed_request);
715EXPORT_SYMBOL(elevator_exit); 813EXPORT_SYMBOL(elevator_exit);