Back to home page

LXR

 
 

    


0001 /*
0002  *  Block device elevator/IO-scheduler.
0003  *
0004  *  Copyright (C) 2000 Andrea Arcangeli <andrea@suse.de> SuSE
0005  *
0006  * 30042000 Jens Axboe <axboe@kernel.dk> :
0007  *
0008  * Split the elevator a bit so that it is possible to choose a different
0009  * one or even write a new "plug in". There are three pieces:
0010  * - elevator_fn, inserts a new request in the queue list
0011  * - elevator_merge_fn, decides whether a new buffer can be merged with
0012  *   an existing request
0013  * - elevator_dequeue_fn, called when a request is taken off the active list
0014  *
0015  * 20082000 Dave Jones <davej@suse.de> :
0016  * Removed tests for max-bomb-segments, which was breaking elvtune
0017  *  when run without -bN
0018  *
0019  * Jens:
0020  * - Rework again to work with bio instead of buffer_heads
0021  * - loose bi_dev comparisons, partition handling is right now
0022  * - completely modularize elevator setup and teardown
0023  *
0024  */
0025 #include <linux/kernel.h>
0026 #include <linux/fs.h>
0027 #include <linux/blkdev.h>
0028 #include <linux/elevator.h>
0029 #include <linux/bio.h>
0030 #include <linux/module.h>
0031 #include <linux/slab.h>
0032 #include <linux/init.h>
0033 #include <linux/compiler.h>
0034 #include <linux/blktrace_api.h>
0035 #include <linux/hash.h>
0036 #include <linux/uaccess.h>
0037 #include <linux/pm_runtime.h>
0038 #include <linux/blk-cgroup.h>
0039 
0040 #include <trace/events/block.h>
0041 
0042 #include "blk.h"
0043 
0044 static DEFINE_SPINLOCK(elv_list_lock);
0045 static LIST_HEAD(elv_list);
0046 
0047 /*
0048  * Merge hash stuff.
0049  */
0050 #define rq_hash_key(rq)     (blk_rq_pos(rq) + blk_rq_sectors(rq))
0051 
0052 /*
0053  * Query io scheduler to see if the current process issuing bio may be
0054  * merged with rq.
0055  */
0056 static int elv_iosched_allow_bio_merge(struct request *rq, struct bio *bio)
0057 {
0058     struct request_queue *q = rq->q;
0059     struct elevator_queue *e = q->elevator;
0060 
0061     if (e->type->ops.elevator_allow_bio_merge_fn)
0062         return e->type->ops.elevator_allow_bio_merge_fn(q, rq, bio);
0063 
0064     return 1;
0065 }
0066 
0067 /*
0068  * can we safely merge with this request?
0069  */
0070 bool elv_bio_merge_ok(struct request *rq, struct bio *bio)
0071 {
0072     if (!blk_rq_merge_ok(rq, bio))
0073         return false;
0074 
0075     if (!elv_iosched_allow_bio_merge(rq, bio))
0076         return false;
0077 
0078     return true;
0079 }
0080 EXPORT_SYMBOL(elv_bio_merge_ok);
0081 
0082 static struct elevator_type *elevator_find(const char *name)
0083 {
0084     struct elevator_type *e;
0085 
0086     list_for_each_entry(e, &elv_list, list) {
0087         if (!strcmp(e->elevator_name, name))
0088             return e;
0089     }
0090 
0091     return NULL;
0092 }
0093 
0094 static void elevator_put(struct elevator_type *e)
0095 {
0096     module_put(e->elevator_owner);
0097 }
0098 
0099 static struct elevator_type *elevator_get(const char *name, bool try_loading)
0100 {
0101     struct elevator_type *e;
0102 
0103     spin_lock(&elv_list_lock);
0104 
0105     e = elevator_find(name);
0106     if (!e && try_loading) {
0107         spin_unlock(&elv_list_lock);
0108         request_module("%s-iosched", name);
0109         spin_lock(&elv_list_lock);
0110         e = elevator_find(name);
0111     }
0112 
0113     if (e && !try_module_get(e->elevator_owner))
0114         e = NULL;
0115 
0116     spin_unlock(&elv_list_lock);
0117 
0118     return e;
0119 }
0120 
0121 static char chosen_elevator[ELV_NAME_MAX];
0122 
0123 static int __init elevator_setup(char *str)
0124 {
0125     /*
0126      * Be backwards-compatible with previous kernels, so users
0127      * won't get the wrong elevator.
0128      */
0129     strncpy(chosen_elevator, str, sizeof(chosen_elevator) - 1);
0130     return 1;
0131 }
0132 
0133 __setup("elevator=", elevator_setup);
0134 
0135 /* called during boot to load the elevator chosen by the elevator param */
0136 void __init load_default_elevator_module(void)
0137 {
0138     struct elevator_type *e;
0139 
0140     if (!chosen_elevator[0])
0141         return;
0142 
0143     spin_lock(&elv_list_lock);
0144     e = elevator_find(chosen_elevator);
0145     spin_unlock(&elv_list_lock);
0146 
0147     if (!e)
0148         request_module("%s-iosched", chosen_elevator);
0149 }
0150 
0151 static struct kobj_type elv_ktype;
0152 
0153 struct elevator_queue *elevator_alloc(struct request_queue *q,
0154                   struct elevator_type *e)
0155 {
0156     struct elevator_queue *eq;
0157 
0158     eq = kzalloc_node(sizeof(*eq), GFP_KERNEL, q->node);
0159     if (unlikely(!eq))
0160         return NULL;
0161 
0162     eq->type = e;
0163     kobject_init(&eq->kobj, &elv_ktype);
0164     mutex_init(&eq->sysfs_lock);
0165     hash_init(eq->hash);
0166 
0167     return eq;
0168 }
0169 EXPORT_SYMBOL(elevator_alloc);
0170 
0171 static void elevator_release(struct kobject *kobj)
0172 {
0173     struct elevator_queue *e;
0174 
0175     e = container_of(kobj, struct elevator_queue, kobj);
0176     elevator_put(e->type);
0177     kfree(e);
0178 }
0179 
0180 int elevator_init(struct request_queue *q, char *name)
0181 {
0182     struct elevator_type *e = NULL;
0183     int err;
0184 
0185     /*
0186      * q->sysfs_lock must be held to provide mutual exclusion between
0187      * elevator_switch() and here.
0188      */
0189     lockdep_assert_held(&q->sysfs_lock);
0190 
0191     if (unlikely(q->elevator))
0192         return 0;
0193 
0194     INIT_LIST_HEAD(&q->queue_head);
0195     q->last_merge = NULL;
0196     q->end_sector = 0;
0197     q->boundary_rq = NULL;
0198 
0199     if (name) {
0200         e = elevator_get(name, true);
0201         if (!e)
0202             return -EINVAL;
0203     }
0204 
0205     /*
0206      * Use the default elevator specified by config boot param or
0207      * config option.  Don't try to load modules as we could be running
0208      * off async and request_module() isn't allowed from async.
0209      */
0210     if (!e && *chosen_elevator) {
0211         e = elevator_get(chosen_elevator, false);
0212         if (!e)
0213             printk(KERN_ERR "I/O scheduler %s not found\n",
0214                             chosen_elevator);
0215     }
0216 
0217     if (!e) {
0218         e = elevator_get(CONFIG_DEFAULT_IOSCHED, false);
0219         if (!e) {
0220             printk(KERN_ERR
0221                 "Default I/O scheduler not found. " \
0222                 "Using noop.\n");
0223             e = elevator_get("noop", false);
0224         }
0225     }
0226 
0227     err = e->ops.elevator_init_fn(q, e);
0228     if (err)
0229         elevator_put(e);
0230     return err;
0231 }
0232 EXPORT_SYMBOL(elevator_init);
0233 
0234 void elevator_exit(struct elevator_queue *e)
0235 {
0236     mutex_lock(&e->sysfs_lock);
0237     if (e->type->ops.elevator_exit_fn)
0238         e->type->ops.elevator_exit_fn(e);
0239     mutex_unlock(&e->sysfs_lock);
0240 
0241     kobject_put(&e->kobj);
0242 }
0243 EXPORT_SYMBOL(elevator_exit);
0244 
0245 static inline void __elv_rqhash_del(struct request *rq)
0246 {
0247     hash_del(&rq->hash);
0248     rq->rq_flags &= ~RQF_HASHED;
0249 }
0250 
0251 void elv_rqhash_del(struct request_queue *q, struct request *rq)
0252 {
0253     if (ELV_ON_HASH(rq))
0254         __elv_rqhash_del(rq);
0255 }
0256 
0257 void elv_rqhash_add(struct request_queue *q, struct request *rq)
0258 {
0259     struct elevator_queue *e = q->elevator;
0260 
0261     BUG_ON(ELV_ON_HASH(rq));
0262     hash_add(e->hash, &rq->hash, rq_hash_key(rq));
0263     rq->rq_flags |= RQF_HASHED;
0264 }
0265 
0266 void elv_rqhash_reposition(struct request_queue *q, struct request *rq)
0267 {
0268     __elv_rqhash_del(rq);
0269     elv_rqhash_add(q, rq);
0270 }
0271 
0272 struct request *elv_rqhash_find(struct request_queue *q, sector_t offset)
0273 {
0274     struct elevator_queue *e = q->elevator;
0275     struct hlist_node *next;
0276     struct request *rq;
0277 
0278     hash_for_each_possible_safe(e->hash, rq, next, hash, offset) {
0279         BUG_ON(!ELV_ON_HASH(rq));
0280 
0281         if (unlikely(!rq_mergeable(rq))) {
0282             __elv_rqhash_del(rq);
0283             continue;
0284         }
0285 
0286         if (rq_hash_key(rq) == offset)
0287             return rq;
0288     }
0289 
0290     return NULL;
0291 }
0292 
0293 /*
0294  * RB-tree support functions for inserting/lookup/removal of requests
0295  * in a sorted RB tree.
0296  */
0297 void elv_rb_add(struct rb_root *root, struct request *rq)
0298 {
0299     struct rb_node **p = &root->rb_node;
0300     struct rb_node *parent = NULL;
0301     struct request *__rq;
0302 
0303     while (*p) {
0304         parent = *p;
0305         __rq = rb_entry(parent, struct request, rb_node);
0306 
0307         if (blk_rq_pos(rq) < blk_rq_pos(__rq))
0308             p = &(*p)->rb_left;
0309         else if (blk_rq_pos(rq) >= blk_rq_pos(__rq))
0310             p = &(*p)->rb_right;
0311     }
0312 
0313     rb_link_node(&rq->rb_node, parent, p);
0314     rb_insert_color(&rq->rb_node, root);
0315 }
0316 EXPORT_SYMBOL(elv_rb_add);
0317 
0318 void elv_rb_del(struct rb_root *root, struct request *rq)
0319 {
0320     BUG_ON(RB_EMPTY_NODE(&rq->rb_node));
0321     rb_erase(&rq->rb_node, root);
0322     RB_CLEAR_NODE(&rq->rb_node);
0323 }
0324 EXPORT_SYMBOL(elv_rb_del);
0325 
0326 struct request *elv_rb_find(struct rb_root *root, sector_t sector)
0327 {
0328     struct rb_node *n = root->rb_node;
0329     struct request *rq;
0330 
0331     while (n) {
0332         rq = rb_entry(n, struct request, rb_node);
0333 
0334         if (sector < blk_rq_pos(rq))
0335             n = n->rb_left;
0336         else if (sector > blk_rq_pos(rq))
0337             n = n->rb_right;
0338         else
0339             return rq;
0340     }
0341 
0342     return NULL;
0343 }
0344 EXPORT_SYMBOL(elv_rb_find);
0345 
0346 /*
0347  * Insert rq into dispatch queue of q.  Queue lock must be held on
0348  * entry.  rq is sort instead into the dispatch queue. To be used by
0349  * specific elevators.
0350  */
0351 void elv_dispatch_sort(struct request_queue *q, struct request *rq)
0352 {
0353     sector_t boundary;
0354     struct list_head *entry;
0355 
0356     if (q->last_merge == rq)
0357         q->last_merge = NULL;
0358 
0359     elv_rqhash_del(q, rq);
0360 
0361     q->nr_sorted--;
0362 
0363     boundary = q->end_sector;
0364     list_for_each_prev(entry, &q->queue_head) {
0365         struct request *pos = list_entry_rq(entry);
0366 
0367         if (req_op(rq) != req_op(pos))
0368             break;
0369         if (rq_data_dir(rq) != rq_data_dir(pos))
0370             break;
0371         if (pos->rq_flags & (RQF_STARTED | RQF_SOFTBARRIER))
0372             break;
0373         if (blk_rq_pos(rq) >= boundary) {
0374             if (blk_rq_pos(pos) < boundary)
0375                 continue;
0376         } else {
0377             if (blk_rq_pos(pos) >= boundary)
0378                 break;
0379         }
0380         if (blk_rq_pos(rq) >= blk_rq_pos(pos))
0381             break;
0382     }
0383 
0384     list_add(&rq->queuelist, entry);
0385 }
0386 EXPORT_SYMBOL(elv_dispatch_sort);
0387 
0388 /*
0389  * Insert rq into dispatch queue of q.  Queue lock must be held on
0390  * entry.  rq is added to the back of the dispatch queue. To be used by
0391  * specific elevators.
0392  */
0393 void elv_dispatch_add_tail(struct request_queue *q, struct request *rq)
0394 {
0395     if (q->last_merge == rq)
0396         q->last_merge = NULL;
0397 
0398     elv_rqhash_del(q, rq);
0399 
0400     q->nr_sorted--;
0401 
0402     q->end_sector = rq_end_sector(rq);
0403     q->boundary_rq = rq;
0404     list_add_tail(&rq->queuelist, &q->queue_head);
0405 }
0406 EXPORT_SYMBOL(elv_dispatch_add_tail);
0407 
0408 int elv_merge(struct request_queue *q, struct request **req, struct bio *bio)
0409 {
0410     struct elevator_queue *e = q->elevator;
0411     struct request *__rq;
0412     int ret;
0413 
0414     /*
0415      * Levels of merges:
0416      *  nomerges:  No merges at all attempted
0417      *  noxmerges: Only simple one-hit cache try
0418      *  merges:    All merge tries attempted
0419      */
0420     if (blk_queue_nomerges(q) || !bio_mergeable(bio))
0421         return ELEVATOR_NO_MERGE;
0422 
0423     /*
0424      * First try one-hit cache.
0425      */
0426     if (q->last_merge && elv_bio_merge_ok(q->last_merge, bio)) {
0427         ret = blk_try_merge(q->last_merge, bio);
0428         if (ret != ELEVATOR_NO_MERGE) {
0429             *req = q->last_merge;
0430             return ret;
0431         }
0432     }
0433 
0434     if (blk_queue_noxmerges(q))
0435         return ELEVATOR_NO_MERGE;
0436 
0437     /*
0438      * See if our hash lookup can find a potential backmerge.
0439      */
0440     __rq = elv_rqhash_find(q, bio->bi_iter.bi_sector);
0441     if (__rq && elv_bio_merge_ok(__rq, bio)) {
0442         *req = __rq;
0443         return ELEVATOR_BACK_MERGE;
0444     }
0445 
0446     if (e->type->ops.elevator_merge_fn)
0447         return e->type->ops.elevator_merge_fn(q, req, bio);
0448 
0449     return ELEVATOR_NO_MERGE;
0450 }
0451 
0452 /*
0453  * Attempt to do an insertion back merge. Only check for the case where
0454  * we can append 'rq' to an existing request, so we can throw 'rq' away
0455  * afterwards.
0456  *
0457  * Returns true if we merged, false otherwise
0458  */
0459 static bool elv_attempt_insert_merge(struct request_queue *q,
0460                      struct request *rq)
0461 {
0462     struct request *__rq;
0463     bool ret;
0464 
0465     if (blk_queue_nomerges(q))
0466         return false;
0467 
0468     /*
0469      * First try one-hit cache.
0470      */
0471     if (q->last_merge && blk_attempt_req_merge(q, q->last_merge, rq))
0472         return true;
0473 
0474     if (blk_queue_noxmerges(q))
0475         return false;
0476 
0477     ret = false;
0478     /*
0479      * See if our hash lookup can find a potential backmerge.
0480      */
0481     while (1) {
0482         __rq = elv_rqhash_find(q, blk_rq_pos(rq));
0483         if (!__rq || !blk_attempt_req_merge(q, __rq, rq))
0484             break;
0485 
0486         /* The merged request could be merged with others, try again */
0487         ret = true;
0488         rq = __rq;
0489     }
0490 
0491     return ret;
0492 }
0493 
0494 void elv_merged_request(struct request_queue *q, struct request *rq, int type)
0495 {
0496     struct elevator_queue *e = q->elevator;
0497 
0498     if (e->type->ops.elevator_merged_fn)
0499         e->type->ops.elevator_merged_fn(q, rq, type);
0500 
0501     if (type == ELEVATOR_BACK_MERGE)
0502         elv_rqhash_reposition(q, rq);
0503 
0504     q->last_merge = rq;
0505 }
0506 
0507 void elv_merge_requests(struct request_queue *q, struct request *rq,
0508                  struct request *next)
0509 {
0510     struct elevator_queue *e = q->elevator;
0511     const int next_sorted = next->rq_flags & RQF_SORTED;
0512 
0513     if (next_sorted && e->type->ops.elevator_merge_req_fn)
0514         e->type->ops.elevator_merge_req_fn(q, rq, next);
0515 
0516     elv_rqhash_reposition(q, rq);
0517 
0518     if (next_sorted) {
0519         elv_rqhash_del(q, next);
0520         q->nr_sorted--;
0521     }
0522 
0523     q->last_merge = rq;
0524 }
0525 
0526 void elv_bio_merged(struct request_queue *q, struct request *rq,
0527             struct bio *bio)
0528 {
0529     struct elevator_queue *e = q->elevator;
0530 
0531     if (e->type->ops.elevator_bio_merged_fn)
0532         e->type->ops.elevator_bio_merged_fn(q, rq, bio);
0533 }
0534 
0535 #ifdef CONFIG_PM
0536 static void blk_pm_requeue_request(struct request *rq)
0537 {
0538     if (rq->q->dev && !(rq->rq_flags & RQF_PM))
0539         rq->q->nr_pending--;
0540 }
0541 
0542 static void blk_pm_add_request(struct request_queue *q, struct request *rq)
0543 {
0544     if (q->dev && !(rq->rq_flags & RQF_PM) && q->nr_pending++ == 0 &&
0545         (q->rpm_status == RPM_SUSPENDED || q->rpm_status == RPM_SUSPENDING))
0546         pm_request_resume(q->dev);
0547 }
0548 #else
0549 static inline void blk_pm_requeue_request(struct request *rq) {}
0550 static inline void blk_pm_add_request(struct request_queue *q,
0551                       struct request *rq)
0552 {
0553 }
0554 #endif
0555 
0556 void elv_requeue_request(struct request_queue *q, struct request *rq)
0557 {
0558     /*
0559      * it already went through dequeue, we need to decrement the
0560      * in_flight count again
0561      */
0562     if (blk_account_rq(rq)) {
0563         q->in_flight[rq_is_sync(rq)]--;
0564         if (rq->rq_flags & RQF_SORTED)
0565             elv_deactivate_rq(q, rq);
0566     }
0567 
0568     rq->rq_flags &= ~RQF_STARTED;
0569 
0570     blk_pm_requeue_request(rq);
0571 
0572     __elv_add_request(q, rq, ELEVATOR_INSERT_REQUEUE);
0573 }
0574 
0575 void elv_drain_elevator(struct request_queue *q)
0576 {
0577     static int printed;
0578 
0579     lockdep_assert_held(q->queue_lock);
0580 
0581     while (q->elevator->type->ops.elevator_dispatch_fn(q, 1))
0582         ;
0583     if (q->nr_sorted && printed++ < 10) {
0584         printk(KERN_ERR "%s: forced dispatching is broken "
0585                "(nr_sorted=%u), please report this\n",
0586                q->elevator->type->elevator_name, q->nr_sorted);
0587     }
0588 }
0589 
0590 void __elv_add_request(struct request_queue *q, struct request *rq, int where)
0591 {
0592     trace_block_rq_insert(q, rq);
0593 
0594     blk_pm_add_request(q, rq);
0595 
0596     rq->q = q;
0597 
0598     if (rq->rq_flags & RQF_SOFTBARRIER) {
0599         /* barriers are scheduling boundary, update end_sector */
0600         if (rq->cmd_type == REQ_TYPE_FS) {
0601             q->end_sector = rq_end_sector(rq);
0602             q->boundary_rq = rq;
0603         }
0604     } else if (!(rq->rq_flags & RQF_ELVPRIV) &&
0605             (where == ELEVATOR_INSERT_SORT ||
0606              where == ELEVATOR_INSERT_SORT_MERGE))
0607         where = ELEVATOR_INSERT_BACK;
0608 
0609     switch (where) {
0610     case ELEVATOR_INSERT_REQUEUE:
0611     case ELEVATOR_INSERT_FRONT:
0612         rq->rq_flags |= RQF_SOFTBARRIER;
0613         list_add(&rq->queuelist, &q->queue_head);
0614         break;
0615 
0616     case ELEVATOR_INSERT_BACK:
0617         rq->rq_flags |= RQF_SOFTBARRIER;
0618         elv_drain_elevator(q);
0619         list_add_tail(&rq->queuelist, &q->queue_head);
0620         /*
0621          * We kick the queue here for the following reasons.
0622          * - The elevator might have returned NULL previously
0623          *   to delay requests and returned them now.  As the
0624          *   queue wasn't empty before this request, ll_rw_blk
0625          *   won't run the queue on return, resulting in hang.
0626          * - Usually, back inserted requests won't be merged
0627          *   with anything.  There's no point in delaying queue
0628          *   processing.
0629          */
0630         __blk_run_queue(q);
0631         break;
0632 
0633     case ELEVATOR_INSERT_SORT_MERGE:
0634         /*
0635          * If we succeed in merging this request with one in the
0636          * queue already, we are done - rq has now been freed,
0637          * so no need to do anything further.
0638          */
0639         if (elv_attempt_insert_merge(q, rq))
0640             break;
0641     case ELEVATOR_INSERT_SORT:
0642         BUG_ON(rq->cmd_type != REQ_TYPE_FS);
0643         rq->rq_flags |= RQF_SORTED;
0644         q->nr_sorted++;
0645         if (rq_mergeable(rq)) {
0646             elv_rqhash_add(q, rq);
0647             if (!q->last_merge)
0648                 q->last_merge = rq;
0649         }
0650 
0651         /*
0652          * Some ioscheds (cfq) run q->request_fn directly, so
0653          * rq cannot be accessed after calling
0654          * elevator_add_req_fn.
0655          */
0656         q->elevator->type->ops.elevator_add_req_fn(q, rq);
0657         break;
0658 
0659     case ELEVATOR_INSERT_FLUSH:
0660         rq->rq_flags |= RQF_SOFTBARRIER;
0661         blk_insert_flush(rq);
0662         break;
0663     default:
0664         printk(KERN_ERR "%s: bad insertion point %d\n",
0665                __func__, where);
0666         BUG();
0667     }
0668 }
0669 EXPORT_SYMBOL(__elv_add_request);
0670 
0671 void elv_add_request(struct request_queue *q, struct request *rq, int where)
0672 {
0673     unsigned long flags;
0674 
0675     spin_lock_irqsave(q->queue_lock, flags);
0676     __elv_add_request(q, rq, where);
0677     spin_unlock_irqrestore(q->queue_lock, flags);
0678 }
0679 EXPORT_SYMBOL(elv_add_request);
0680 
0681 struct request *elv_latter_request(struct request_queue *q, struct request *rq)
0682 {
0683     struct elevator_queue *e = q->elevator;
0684 
0685     if (e->type->ops.elevator_latter_req_fn)
0686         return e->type->ops.elevator_latter_req_fn(q, rq);
0687     return NULL;
0688 }
0689 
0690 struct request *elv_former_request(struct request_queue *q, struct request *rq)
0691 {
0692     struct elevator_queue *e = q->elevator;
0693 
0694     if (e->type->ops.elevator_former_req_fn)
0695         return e->type->ops.elevator_former_req_fn(q, rq);
0696     return NULL;
0697 }
0698 
0699 int elv_set_request(struct request_queue *q, struct request *rq,
0700             struct bio *bio, gfp_t gfp_mask)
0701 {
0702     struct elevator_queue *e = q->elevator;
0703 
0704     if (e->type->ops.elevator_set_req_fn)
0705         return e->type->ops.elevator_set_req_fn(q, rq, bio, gfp_mask);
0706     return 0;
0707 }
0708 
0709 void elv_put_request(struct request_queue *q, struct request *rq)
0710 {
0711     struct elevator_queue *e = q->elevator;
0712 
0713     if (e->type->ops.elevator_put_req_fn)
0714         e->type->ops.elevator_put_req_fn(rq);
0715 }
0716 
0717 int elv_may_queue(struct request_queue *q, unsigned int op)
0718 {
0719     struct elevator_queue *e = q->elevator;
0720 
0721     if (e->type->ops.elevator_may_queue_fn)
0722         return e->type->ops.elevator_may_queue_fn(q, op);
0723 
0724     return ELV_MQUEUE_MAY;
0725 }
0726 
0727 void elv_completed_request(struct request_queue *q, struct request *rq)
0728 {
0729     struct elevator_queue *e = q->elevator;
0730 
0731     /*
0732      * request is released from the driver, io must be done
0733      */
0734     if (blk_account_rq(rq)) {
0735         q->in_flight[rq_is_sync(rq)]--;
0736         if ((rq->rq_flags & RQF_SORTED) &&
0737             e->type->ops.elevator_completed_req_fn)
0738             e->type->ops.elevator_completed_req_fn(q, rq);
0739     }
0740 }
0741 
0742 #define to_elv(atr) container_of((atr), struct elv_fs_entry, attr)
0743 
0744 static ssize_t
0745 elv_attr_show(struct kobject *kobj, struct attribute *attr, char *page)
0746 {
0747     struct elv_fs_entry *entry = to_elv(attr);
0748     struct elevator_queue *e;
0749     ssize_t error;
0750 
0751     if (!entry->show)
0752         return -EIO;
0753 
0754     e = container_of(kobj, struct elevator_queue, kobj);
0755     mutex_lock(&e->sysfs_lock);
0756     error = e->type ? entry->show(e, page) : -ENOENT;
0757     mutex_unlock(&e->sysfs_lock);
0758     return error;
0759 }
0760 
0761 static ssize_t
0762 elv_attr_store(struct kobject *kobj, struct attribute *attr,
0763            const char *page, size_t length)
0764 {
0765     struct elv_fs_entry *entry = to_elv(attr);
0766     struct elevator_queue *e;
0767     ssize_t error;
0768 
0769     if (!entry->store)
0770         return -EIO;
0771 
0772     e = container_of(kobj, struct elevator_queue, kobj);
0773     mutex_lock(&e->sysfs_lock);
0774     error = e->type ? entry->store(e, page, length) : -ENOENT;
0775     mutex_unlock(&e->sysfs_lock);
0776     return error;
0777 }
0778 
0779 static const struct sysfs_ops elv_sysfs_ops = {
0780     .show   = elv_attr_show,
0781     .store  = elv_attr_store,
0782 };
0783 
0784 static struct kobj_type elv_ktype = {
0785     .sysfs_ops  = &elv_sysfs_ops,
0786     .release    = elevator_release,
0787 };
0788 
0789 int elv_register_queue(struct request_queue *q)
0790 {
0791     struct elevator_queue *e = q->elevator;
0792     int error;
0793 
0794     error = kobject_add(&e->kobj, &q->kobj, "%s", "iosched");
0795     if (!error) {
0796         struct elv_fs_entry *attr = e->type->elevator_attrs;
0797         if (attr) {
0798             while (attr->attr.name) {
0799                 if (sysfs_create_file(&e->kobj, &attr->attr))
0800                     break;
0801                 attr++;
0802             }
0803         }
0804         kobject_uevent(&e->kobj, KOBJ_ADD);
0805         e->registered = 1;
0806         if (e->type->ops.elevator_registered_fn)
0807             e->type->ops.elevator_registered_fn(q);
0808     }
0809     return error;
0810 }
0811 EXPORT_SYMBOL(elv_register_queue);
0812 
0813 void elv_unregister_queue(struct request_queue *q)
0814 {
0815     if (q) {
0816         struct elevator_queue *e = q->elevator;
0817 
0818         kobject_uevent(&e->kobj, KOBJ_REMOVE);
0819         kobject_del(&e->kobj);
0820         e->registered = 0;
0821     }
0822 }
0823 EXPORT_SYMBOL(elv_unregister_queue);
0824 
0825 int elv_register(struct elevator_type *e)
0826 {
0827     char *def = "";
0828 
0829     /* create icq_cache if requested */
0830     if (e->icq_size) {
0831         if (WARN_ON(e->icq_size < sizeof(struct io_cq)) ||
0832             WARN_ON(e->icq_align < __alignof__(struct io_cq)))
0833             return -EINVAL;
0834 
0835         snprintf(e->icq_cache_name, sizeof(e->icq_cache_name),
0836              "%s_io_cq", e->elevator_name);
0837         e->icq_cache = kmem_cache_create(e->icq_cache_name, e->icq_size,
0838                          e->icq_align, 0, NULL);
0839         if (!e->icq_cache)
0840             return -ENOMEM;
0841     }
0842 
0843     /* register, don't allow duplicate names */
0844     spin_lock(&elv_list_lock);
0845     if (elevator_find(e->elevator_name)) {
0846         spin_unlock(&elv_list_lock);
0847         if (e->icq_cache)
0848             kmem_cache_destroy(e->icq_cache);
0849         return -EBUSY;
0850     }
0851     list_add_tail(&e->list, &elv_list);
0852     spin_unlock(&elv_list_lock);
0853 
0854     /* print pretty message */
0855     if (!strcmp(e->elevator_name, chosen_elevator) ||
0856             (!*chosen_elevator &&
0857              !strcmp(e->elevator_name, CONFIG_DEFAULT_IOSCHED)))
0858                 def = " (default)";
0859 
0860     printk(KERN_INFO "io scheduler %s registered%s\n", e->elevator_name,
0861                                 def);
0862     return 0;
0863 }
0864 EXPORT_SYMBOL_GPL(elv_register);
0865 
0866 void elv_unregister(struct elevator_type *e)
0867 {
0868     /* unregister */
0869     spin_lock(&elv_list_lock);
0870     list_del_init(&e->list);
0871     spin_unlock(&elv_list_lock);
0872 
0873     /*
0874      * Destroy icq_cache if it exists.  icq's are RCU managed.  Make
0875      * sure all RCU operations are complete before proceeding.
0876      */
0877     if (e->icq_cache) {
0878         rcu_barrier();
0879         kmem_cache_destroy(e->icq_cache);
0880         e->icq_cache = NULL;
0881     }
0882 }
0883 EXPORT_SYMBOL_GPL(elv_unregister);
0884 
0885 /*
0886  * switch to new_e io scheduler. be careful not to introduce deadlocks -
0887  * we don't free the old io scheduler, before we have allocated what we
0888  * need for the new one. this way we have a chance of going back to the old
0889  * one, if the new one fails init for some reason.
0890  */
0891 static int elevator_switch(struct request_queue *q, struct elevator_type *new_e)
0892 {
0893     struct elevator_queue *old = q->elevator;
0894     bool registered = old->registered;
0895     int err;
0896 
0897     /*
0898      * Turn on BYPASS and drain all requests w/ elevator private data.
0899      * Block layer doesn't call into a quiesced elevator - all requests
0900      * are directly put on the dispatch list without elevator data
0901      * using INSERT_BACK.  All requests have SOFTBARRIER set and no
0902      * merge happens either.
0903      */
0904     blk_queue_bypass_start(q);
0905 
0906     /* unregister and clear all auxiliary data of the old elevator */
0907     if (registered)
0908         elv_unregister_queue(q);
0909 
0910     spin_lock_irq(q->queue_lock);
0911     ioc_clear_queue(q);
0912     spin_unlock_irq(q->queue_lock);
0913 
0914     /* allocate, init and register new elevator */
0915     err = new_e->ops.elevator_init_fn(q, new_e);
0916     if (err)
0917         goto fail_init;
0918 
0919     if (registered) {
0920         err = elv_register_queue(q);
0921         if (err)
0922             goto fail_register;
0923     }
0924 
0925     /* done, kill the old one and finish */
0926     elevator_exit(old);
0927     blk_queue_bypass_end(q);
0928 
0929     blk_add_trace_msg(q, "elv switch: %s", new_e->elevator_name);
0930 
0931     return 0;
0932 
0933 fail_register:
0934     elevator_exit(q->elevator);
0935 fail_init:
0936     /* switch failed, restore and re-register old elevator */
0937     q->elevator = old;
0938     elv_register_queue(q);
0939     blk_queue_bypass_end(q);
0940 
0941     return err;
0942 }
0943 
0944 /*
0945  * Switch this queue to the given IO scheduler.
0946  */
0947 static int __elevator_change(struct request_queue *q, const char *name)
0948 {
0949     char elevator_name[ELV_NAME_MAX];
0950     struct elevator_type *e;
0951 
0952     if (!q->elevator)
0953         return -ENXIO;
0954 
0955     strlcpy(elevator_name, name, sizeof(elevator_name));
0956     e = elevator_get(strstrip(elevator_name), true);
0957     if (!e) {
0958         printk(KERN_ERR "elevator: type %s not found\n", elevator_name);
0959         return -EINVAL;
0960     }
0961 
0962     if (!strcmp(elevator_name, q->elevator->type->elevator_name)) {
0963         elevator_put(e);
0964         return 0;
0965     }
0966 
0967     return elevator_switch(q, e);
0968 }
0969 
0970 int elevator_change(struct request_queue *q, const char *name)
0971 {
0972     int ret;
0973 
0974     /* Protect q->elevator from elevator_init() */
0975     mutex_lock(&q->sysfs_lock);
0976     ret = __elevator_change(q, name);
0977     mutex_unlock(&q->sysfs_lock);
0978 
0979     return ret;
0980 }
0981 EXPORT_SYMBOL(elevator_change);
0982 
0983 ssize_t elv_iosched_store(struct request_queue *q, const char *name,
0984               size_t count)
0985 {
0986     int ret;
0987 
0988     if (!q->elevator)
0989         return count;
0990 
0991     ret = __elevator_change(q, name);
0992     if (!ret)
0993         return count;
0994 
0995     printk(KERN_ERR "elevator: switch to %s failed\n", name);
0996     return ret;
0997 }
0998 
0999 ssize_t elv_iosched_show(struct request_queue *q, char *name)
1000 {
1001     struct elevator_queue *e = q->elevator;
1002     struct elevator_type *elv;
1003     struct elevator_type *__e;
1004     int len = 0;
1005 
1006     if (!q->elevator || !blk_queue_stackable(q))
1007         return sprintf(name, "none\n");
1008 
1009     elv = e->type;
1010 
1011     spin_lock(&elv_list_lock);
1012     list_for_each_entry(__e, &elv_list, list) {
1013         if (!strcmp(elv->elevator_name, __e->elevator_name))
1014             len += sprintf(name+len, "[%s] ", elv->elevator_name);
1015         else
1016             len += sprintf(name+len, "%s ", __e->elevator_name);
1017     }
1018     spin_unlock(&elv_list_lock);
1019 
1020     len += sprintf(len+name, "\n");
1021     return len;
1022 }
1023 
1024 struct request *elv_rb_former_request(struct request_queue *q,
1025                       struct request *rq)
1026 {
1027     struct rb_node *rbprev = rb_prev(&rq->rb_node);
1028 
1029     if (rbprev)
1030         return rb_entry_rq(rbprev);
1031 
1032     return NULL;
1033 }
1034 EXPORT_SYMBOL(elv_rb_former_request);
1035 
1036 struct request *elv_rb_latter_request(struct request_queue *q,
1037                       struct request *rq)
1038 {
1039     struct rb_node *rbnext = rb_next(&rq->rb_node);
1040 
1041     if (rbnext)
1042         return rb_entry_rq(rbnext);
1043 
1044     return NULL;
1045 }
1046 EXPORT_SYMBOL(elv_rb_latter_request);