aboutsummaryrefslogtreecommitdiffstats
path: root/Documentation/block
diff options
context:
space:
mode:
Diffstat (limited to 'Documentation/block')
-rw-r--r--Documentation/block/biodoc.txt113
1 files changed, 52 insertions, 61 deletions
diff --git a/Documentation/block/biodoc.txt b/Documentation/block/biodoc.txt
index 6dd274d7e1cf..2d65c2182161 100644
--- a/Documentation/block/biodoc.txt
+++ b/Documentation/block/biodoc.txt
@@ -906,9 +906,20 @@ Aside:
906 906
907 907
9084. The I/O scheduler 9084. The I/O scheduler
909I/O schedulers are now per queue. They should be runtime switchable and modular 909I/O scheduler, a.k.a. elevator, is implemented in two layers. Generic dispatch
910but aren't yet. Jens has most bits to do this, but the sysfs implementation is 910queue and specific I/O schedulers. Unless stated otherwise, elevator is used
911missing. 911to refer to both parts and I/O scheduler to specific I/O schedulers.
912
913Block layer implements generic dispatch queue in ll_rw_blk.c and elevator.c.
914The generic dispatch queue is responsible for properly ordering barrier
915requests, requeueing, handling non-fs requests and all other subtleties.
916
917Specific I/O schedulers are responsible for ordering normal filesystem
918requests. They can also choose to delay certain requests to improve
919throughput or whatever purpose. As the plural form indicates, there are
920multiple I/O schedulers. They can be built as modules but at least one should
921be built inside the kernel. Each queue can choose different one and can also
922change to another one dynamically.
912 923
913A block layer call to the i/o scheduler follows the convention elv_xxx(). This 924A block layer call to the i/o scheduler follows the convention elv_xxx(). This
914calls elevator_xxx_fn in the elevator switch (drivers/block/elevator.c). Oh, 925calls elevator_xxx_fn in the elevator switch (drivers/block/elevator.c). Oh,
@@ -921,44 +932,36 @@ keeping work.
921The functions an elevator may implement are: (* are mandatory) 932The functions an elevator may implement are: (* are mandatory)
922elevator_merge_fn called to query requests for merge with a bio 933elevator_merge_fn called to query requests for merge with a bio
923 934
924elevator_merge_req_fn " " " with another request 935elevator_merge_req_fn called when two requests get merged. the one
936 which gets merged into the other one will be
937 never seen by I/O scheduler again. IOW, after
938 being merged, the request is gone.
925 939
926elevator_merged_fn called when a request in the scheduler has been 940elevator_merged_fn called when a request in the scheduler has been
927 involved in a merge. It is used in the deadline 941 involved in a merge. It is used in the deadline
928 scheduler for example, to reposition the request 942 scheduler for example, to reposition the request
929 if its sorting order has changed. 943 if its sorting order has changed.
930 944
931*elevator_next_req_fn returns the next scheduled request, or NULL 945elevator_dispatch_fn fills the dispatch queue with ready requests.
932 if there are none (or none are ready). 946 I/O schedulers are free to postpone requests by
947 not filling the dispatch queue unless @force
948 is non-zero. Once dispatched, I/O schedulers
949 are not allowed to manipulate the requests -
950 they belong to generic dispatch queue.
933 951
934*elevator_add_req_fn called to add a new request into the scheduler 952elevator_add_req_fn called to add a new request into the scheduler
935 953
936elevator_queue_empty_fn returns true if the merge queue is empty. 954elevator_queue_empty_fn returns true if the merge queue is empty.
937 Drivers shouldn't use this, but rather check 955 Drivers shouldn't use this, but rather check
938 if elv_next_request is NULL (without losing the 956 if elv_next_request is NULL (without losing the
939 request if one exists!) 957 request if one exists!)
940 958
941elevator_remove_req_fn This is called when a driver claims ownership of
942 the target request - it now belongs to the
943 driver. It must not be modified or merged.
944 Drivers must not lose the request! A subsequent
945 call of elevator_next_req_fn must return the
946 _next_ request.
947
948elevator_requeue_req_fn called to add a request to the scheduler. This
949 is used when the request has alrnadebeen
950 returned by elv_next_request, but hasn't
951 completed. If this is not implemented then
952 elevator_add_req_fn is called instead.
953
954elevator_former_req_fn 959elevator_former_req_fn
955elevator_latter_req_fn These return the request before or after the 960elevator_latter_req_fn These return the request before or after the
956 one specified in disk sort order. Used by the 961 one specified in disk sort order. Used by the
957 block layer to find merge possibilities. 962 block layer to find merge possibilities.
958 963
959elevator_completed_req_fn called when a request is completed. This might 964elevator_completed_req_fn called when a request is completed.
960 come about due to being merged with another or
961 when the device completes the request.
962 965
963elevator_may_queue_fn returns true if the scheduler wants to allow the 966elevator_may_queue_fn returns true if the scheduler wants to allow the
964 current context to queue a new request even if 967 current context to queue a new request even if
@@ -967,13 +970,33 @@ elevator_may_queue_fn returns true if the scheduler wants to allow the
967 970
968elevator_set_req_fn 971elevator_set_req_fn
969elevator_put_req_fn Must be used to allocate and free any elevator 972elevator_put_req_fn Must be used to allocate and free any elevator
970 specific storate for a request. 973 specific storage for a request.
974
975elevator_activate_req_fn Called when device driver first sees a request.
976 I/O schedulers can use this callback to
977 determine when actual execution of a request
978 starts.
979elevator_deactivate_req_fn Called when device driver decides to delay
980 a request by requeueing it.
971 981
972elevator_init_fn 982elevator_init_fn
973elevator_exit_fn Allocate and free any elevator specific storage 983elevator_exit_fn Allocate and free any elevator specific storage
974 for a queue. 984 for a queue.
975 985
9764.2 I/O scheduler implementation 9864.2 Request flows seen by I/O schedulers
987All requests seens by I/O schedulers strictly follow one of the following three
988flows.
989
990 set_req_fn ->
991
992 i. add_req_fn -> (merged_fn ->)* -> dispatch_fn -> activate_req_fn ->
993 (deactivate_req_fn -> activate_req_fn ->)* -> completed_req_fn
994 ii. add_req_fn -> (merged_fn ->)* -> merge_req_fn
995 iii. [none]
996
997 -> put_req_fn
998
9994.3 I/O scheduler implementation
977The generic i/o scheduler algorithm attempts to sort/merge/batch requests for 1000The generic i/o scheduler algorithm attempts to sort/merge/batch requests for
978optimal disk scan and request servicing performance (based on generic 1001optimal disk scan and request servicing performance (based on generic
979principles and device capabilities), optimized for: 1002principles and device capabilities), optimized for:
@@ -993,18 +1016,7 @@ request in sort order to prevent binary tree lookups.
993This arrangement is not a generic block layer characteristic however, so 1016This arrangement is not a generic block layer characteristic however, so
994elevators may implement queues as they please. 1017elevators may implement queues as they please.
995 1018
996ii. Last merge hint 1019ii. Merge hash
997The last merge hint is part of the generic queue layer. I/O schedulers must do
998some management on it. For the most part, the most important thing is to make
999sure q->last_merge is cleared (set to NULL) when the request on it is no longer
1000a candidate for merging (for example if it has been sent to the driver).
1001
1002The last merge performed is cached as a hint for the subsequent request. If
1003sequential data is being submitted, the hint is used to perform merges without
1004any scanning. This is not sufficient when there are multiple processes doing
1005I/O though, so a "merge hash" is used by some schedulers.
1006
1007iii. Merge hash
1008AS and deadline use a hash table indexed by the last sector of a request. This 1020AS and deadline use a hash table indexed by the last sector of a request. This
1009enables merging code to quickly look up "back merge" candidates, even when 1021enables merging code to quickly look up "back merge" candidates, even when
1010multiple I/O streams are being performed at once on one disk. 1022multiple I/O streams are being performed at once on one disk.
@@ -1013,29 +1025,8 @@ multiple I/O streams are being performed at once on one disk.
1013are far less common than "back merges" due to the nature of most I/O patterns. 1025are far less common than "back merges" due to the nature of most I/O patterns.
1014Front merges are handled by the binary trees in AS and deadline schedulers. 1026Front merges are handled by the binary trees in AS and deadline schedulers.
1015 1027
1016iv. Handling barrier cases 1028iii. Plugging the queue to batch requests in anticipation of opportunities for
1017A request with flags REQ_HARDBARRIER or REQ_SOFTBARRIER must not be ordered 1029 merge/sort optimizations
1018around. That is, they must be processed after all older requests, and before
1019any newer ones. This includes merges!
1020
1021In AS and deadline schedulers, barriers have the effect of flushing the reorder
1022queue. The performance cost of this will vary from nothing to a lot depending
1023on i/o patterns and device characteristics. Obviously they won't improve
1024performance, so their use should be kept to a minimum.
1025
1026v. Handling insertion position directives
1027A request may be inserted with a position directive. The directives are one of
1028ELEVATOR_INSERT_BACK, ELEVATOR_INSERT_FRONT, ELEVATOR_INSERT_SORT.
1029
1030ELEVATOR_INSERT_SORT is a general directive for non-barrier requests.
1031ELEVATOR_INSERT_BACK is used to insert a barrier to the back of the queue.
1032ELEVATOR_INSERT_FRONT is used to insert a barrier to the front of the queue, and
1033overrides the ordering requested by any previous barriers. In practice this is
1034harmless and required, because it is used for SCSI requeueing. This does not
1035require flushing the reorder queue, so does not impose a performance penalty.
1036
1037vi. Plugging the queue to batch requests in anticipation of opportunities for
1038 merge/sort optimizations
1039 1030
1040This is just the same as in 2.4 so far, though per-device unplugging 1031This is just the same as in 2.4 so far, though per-device unplugging
1041support is anticipated for 2.5. Also with a priority-based i/o scheduler, 1032support is anticipated for 2.5. Also with a priority-based i/o scheduler,
@@ -1069,7 +1060,7 @@ Aside:
1069 blk_kick_queue() to unplug a specific queue (right away ?) 1060 blk_kick_queue() to unplug a specific queue (right away ?)
1070 or optionally, all queues, is in the plan. 1061 or optionally, all queues, is in the plan.
1071 1062
10724.3 I/O contexts 10634.4 I/O contexts
1073I/O contexts provide a dynamically allocated per process data area. They may 1064I/O contexts provide a dynamically allocated per process data area. They may
1074be used in I/O schedulers, and in the block layer (could be used for IO statis, 1065be used in I/O schedulers, and in the block layer (could be used for IO statis,
1075priorities for example). See *io_context in drivers/block/ll_rw_blk.c, and 1066priorities for example). See *io_context in drivers/block/ll_rw_blk.c, and