blob: bcdb2b4c1f12dcbe8213c2b121e3b8de9b341f93 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001 Notes on the Generic Block Layer Rewrite in Linux 2.5
2 =====================================================
3
4Notes Written on Jan 15, 2002:
Rob Landley26bbb292007-10-15 11:42:52 +02005 Jens Axboe <jens.axboe@oracle.com>
Linus Torvalds1da177e2005-04-16 15:20:36 -07006 Suparna Bhattacharya <suparna@in.ibm.com>
7
8Last Updated May 2, 2002
9September 2003: Updated I/O Scheduler portions
Nick Piggin6e575592010-08-05 21:08:09 +100010 Nick Piggin <npiggin@kernel.dk>
Linus Torvalds1da177e2005-04-16 15:20:36 -070011
12Introduction:
13
14These are some notes describing some aspects of the 2.5 block layer in the
15context of the bio rewrite. The idea is to bring out some of the key
16changes and a glimpse of the rationale behind those changes.
17
18Please mail corrections & suggestions to suparna@in.ibm.com.
19
20Credits:
21---------
22
232.5 bio rewrite:
Rob Landley26bbb292007-10-15 11:42:52 +020024 Jens Axboe <jens.axboe@oracle.com>
Linus Torvalds1da177e2005-04-16 15:20:36 -070025
26Many aspects of the generic block layer redesign were driven by and evolved
27over discussions, prior patches and the collective experience of several
28people. See sections 8 and 9 for a list of some related references.
29
30The following people helped with review comments and inputs for this
31document:
32 Christoph Hellwig <hch@infradead.org>
33 Arjan van de Ven <arjanv@redhat.com>
Adrian Bunkf4b09eb2006-01-03 13:37:51 +010034 Randy Dunlap <rdunlap@xenotime.net>
Linus Torvalds1da177e2005-04-16 15:20:36 -070035 Andre Hedrick <andre@linux-ide.org>
36
37The following people helped with fixes/contributions to the bio patches
38while it was still work-in-progress:
39 David S. Miller <davem@redhat.com>
40
41
42Description of Contents:
43------------------------
44
451. Scope for tuning of logic to various needs
46 1.1 Tuning based on device or low level driver capabilities
47 - Per-queue parameters
48 - Highmem I/O support
49 - I/O scheduler modularization
50 1.2 Tuning based on high level requirements/capabilities
Leonid V. Fedorenchik89627862015-03-13 23:53:22 +030051 1.2.1 Request Priority/Latency
Linus Torvalds1da177e2005-04-16 15:20:36 -070052 1.3 Direct access/bypass to lower layers for diagnostics and special
53 device operations
54 1.3.1 Pre-built commands
552. New flexible and generic but minimalist i/o structure or descriptor
56 (instead of using buffer heads at the i/o layer)
57 2.1 Requirements/Goals addressed
58 2.2 The bio struct in detail (multi-page io unit)
59 2.3 Changes in the request structure
603. Using bios
61 3.1 Setup/teardown (allocation, splitting)
62 3.2 Generic bio helper routines
63 3.2.1 Traversing segments and completion units in a request
64 3.2.2 Setting up DMA scatterlists
65 3.2.3 I/O completion
66 3.2.4 Implications for drivers that do not interpret bios (don't handle
67 multiple segments)
68 3.2.5 Request command tagging
69 3.3 I/O submission
704. The I/O scheduler
715. Scalability related changes
72 5.1 Granular locking: Removal of io_request_lock
73 5.2 Prepare for transition to 64 bit sector_t
746. Other Changes/Implications
75 6.1 Partition re-mapping handled by the generic block layer
767. A few tips on migration of older drivers
778. A list of prior/related/impacted patches/ideas
789. Other References/Discussion Threads
79
80---------------------------------------------------------------------------
81
82Bio Notes
83--------
84
85Let us discuss the changes in the context of how some overall goals for the
86block layer are addressed.
87
881. Scope for tuning the generic logic to satisfy various requirements
89
90The block layer design supports adaptable abstractions to handle common
91processing with the ability to tune the logic to an appropriate extent
92depending on the nature of the device and the requirements of the caller.
93One of the objectives of the rewrite was to increase the degree of tunability
94and to enable higher level code to utilize underlying device/driver
95capabilities to the maximum extent for better i/o performance. This is
96important especially in the light of ever improving hardware capabilities
97and application/middleware software designed to take advantage of these
98capabilities.
99
1001.1 Tuning based on low level device / driver capabilities
101
102Sophisticated devices with large built-in caches, intelligent i/o scheduling
103optimizations, high memory DMA support, etc may find some of the
104generic processing an overhead, while for less capable devices the
105generic functionality is essential for performance or correctness reasons.
106Knowledge of some of the capabilities or parameters of the device should be
107used at the generic block layer to take the right decisions on
108behalf of the driver.
109
110How is this achieved ?
111
112Tuning at a per-queue level:
113
114i. Per-queue limits/values exported to the generic layer by the driver
115
116Various parameters that the generic i/o scheduler logic uses are set at
117a per-queue level (e.g maximum request size, maximum number of segments in
118a scatter-gather list, hardsect size)
119
120Some parameters that were earlier available as global arrays indexed by
121major/minor are now directly associated with the queue. Some of these may
122move into the block device structure in the future. Some characteristics
123have been incorporated into a queue flags field rather than separate fields
124in themselves. There are blk_queue_xxx functions to set the parameters,
125rather than update the fields directly
126
127Some new queue property settings:
128
129 blk_queue_bounce_limit(q, u64 dma_address)
130 Enable I/O to highmem pages, dma_address being the
131 limit. No highmem default.
132
133 blk_queue_max_sectors(q, max_sectors)
Mike Christie28832e82006-03-08 11:19:51 +0100134 Sets two variables that limit the size of the request.
135
136 - The request queue's max_sectors, which is a soft size in
Paolo Ornati670e9f32006-10-03 22:57:56 +0200137 units of 512 byte sectors, and could be dynamically varied
Mike Christie28832e82006-03-08 11:19:51 +0100138 by the core kernel.
139
140 - The request queue's max_hw_sectors, which is a hard limit
141 and reflects the maximum size request a driver can handle
142 in units of 512 byte sectors.
143
144 The default for both max_sectors and max_hw_sectors is
145 255. The upper limit of max_sectors is 1024.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700146
147 blk_queue_max_phys_segments(q, max_segments)
148 Maximum physical segments you can handle in a request. 128
149 default (driver limit). (See 3.2.2)
150
151 blk_queue_max_hw_segments(q, max_segments)
152 Maximum dma segments the hardware can handle in a request. 128
153 default (host adapter limit, after dma remapping).
154 (See 3.2.2)
155
156 blk_queue_max_segment_size(q, max_seg_size)
157 Maximum size of a clustered segment, 64kB default.
158
159 blk_queue_hardsect_size(q, hardsect_size)
160 Lowest possible sector size that the hardware can operate
161 on, 512 bytes default.
162
163New queue flags:
164
165 QUEUE_FLAG_CLUSTER (see 3.2.2)
166 QUEUE_FLAG_QUEUED (see 3.2.4)
167
168
169ii. High-mem i/o capabilities are now considered the default
170
171The generic bounce buffer logic, present in 2.4, where the block layer would
172by default copyin/out i/o requests on high-memory buffers to low-memory buffers
173assuming that the driver wouldn't be able to handle it directly, has been
174changed in 2.5. The bounce logic is now applied only for memory ranges
175for which the device cannot handle i/o. A driver can specify this by
176setting the queue bounce limit for the request queue for the device
177(blk_queue_bounce_limit()). This avoids the inefficiencies of the copyin/out
178where a device is capable of handling high memory i/o.
179
180In order to enable high-memory i/o where the device is capable of supporting
181it, the pci dma mapping routines and associated data structures have now been
182modified to accomplish a direct page -> bus translation, without requiring
183a virtual address mapping (unlike the earlier scheme of virtual address
184-> bus translation). So this works uniformly for high-memory pages (which
Matt LaPlante5d3f0832006-11-30 05:21:10 +0100185do not have a corresponding kernel virtual address space mapping) and
Linus Torvalds1da177e2005-04-16 15:20:36 -0700186low-memory pages.
187
Paul Bolle395cf962011-08-15 02:02:26 +0200188Note: Please refer to Documentation/DMA-API-HOWTO.txt for a discussion
Randy Dunlap5872fb92009-01-29 16:28:02 -0800189on PCI high mem DMA aspects and mapping of scatter gather lists, and support
190for 64 bit PCI.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700191
192Special handling is required only for cases where i/o needs to happen on
193pages at physical memory addresses beyond what the device can support. In these
194cases, a bounce bio representing a buffer from the supported memory range
195is used for performing the i/o with copyin/copyout as needed depending on
196the type of the operation. For example, in case of a read operation, the
197data read has to be copied to the original buffer on i/o completion, so a
198callback routine is set up to do this, while for write, the data is copied
199from the original buffer to the bounce buffer prior to issuing the
200operation. Since an original buffer may be in a high memory area that's not
201mapped in kernel virtual addr, a kmap operation may be required for
202performing the copy, and special care may be needed in the completion path
203as it may not be in irq context. Special care is also required (by way of
204GFP flags) when allocating bounce buffers, to avoid certain highmem
205deadlock possibilities.
206
207It is also possible that a bounce buffer may be allocated from high-memory
208area that's not mapped in kernel virtual addr, but within the range that the
209device can use directly; so the bounce page may need to be kmapped during
210copy operations. [Note: This does not hold in the current implementation,
211though]
212
213There are some situations when pages from high memory may need to
214be kmapped, even if bounce buffers are not necessary. For example a device
215may need to abort DMA operations and revert to PIO for the transfer, in
216which case a virtual mapping of the page is required. For SCSI it is also
217done in some scenarios where the low level driver cannot be trusted to
218handle a single sg entry correctly. The driver is expected to perform the
219kmaps as needed on such occasions using the __bio_kmap_atomic and bio_kmap_irq
220routines as appropriate. A driver could also use the blk_queue_bounce()
221routine on its own to bounce highmem i/o to low memory for specific requests
222if so desired.
223
224iii. The i/o scheduler algorithm itself can be replaced/set as appropriate
225
226As in 2.4, it is possible to plugin a brand new i/o scheduler for a particular
227queue or pick from (copy) existing generic schedulers and replace/override
228certain portions of it. The 2.5 rewrite provides improved modularization
229of the i/o scheduler. There are more pluggable callbacks, e.g for init,
230add request, extract request, which makes it possible to abstract specific
231i/o scheduling algorithm aspects and details outside of the generic loop.
232It also makes it possible to completely hide the implementation details of
233the i/o scheduler from block drivers.
234
235I/O scheduler wrappers are to be used instead of accessing the queue directly.
236See section 4. The I/O scheduler for details.
237
2381.2 Tuning Based on High level code capabilities
239
240i. Application capabilities for raw i/o
241
242This comes from some of the high-performance database/middleware
243requirements where an application prefers to make its own i/o scheduling
244decisions based on an understanding of the access patterns and i/o
245characteristics
246
247ii. High performance filesystems or other higher level kernel code's
248capabilities
249
250Kernel components like filesystems could also take their own i/o scheduling
251decisions for optimizing performance. Journalling filesystems may need
252some control over i/o ordering.
253
254What kind of support exists at the generic block layer for this ?
255
256The flags and rw fields in the bio structure can be used for some tuning
Leonid V. Fedorenchik89627862015-03-13 23:53:22 +0300257from above e.g indicating that an i/o is just a readahead request, or priority
258settings (currently unused). As far as user applications are concerned they
259would need an additional mechanism either via open flags or ioctls, or some
260other upper level mechanism to communicate such settings to block.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700261
Leonid V. Fedorenchik89627862015-03-13 23:53:22 +03002621.2.1 Request Priority/Latency
Linus Torvalds1da177e2005-04-16 15:20:36 -0700263
264Todo/Under discussion:
265Arjan's proposed request priority scheme allows higher levels some broad
266 control (high/med/low) over the priority of an i/o request vs other pending
267 requests in the queue. For example it allows reads for bringing in an
268 executable page on demand to be given a higher priority over pending write
269 requests which haven't aged too much on the queue. Potentially this priority
270 could even be exposed to applications in some manner, providing higher level
271 tunability. Time based aging avoids starvation of lower priority
Jens Axboe1eff9d32016-08-05 15:35:16 -0600272 requests. Some bits in the bi_opf flags field in the bio structure are
Linus Torvalds1da177e2005-04-16 15:20:36 -0700273 intended to be used for this priority information.
274
275
2761.3 Direct Access to Low level Device/Driver Capabilities (Bypass mode)
277 (e.g Diagnostics, Systems Management)
278
279There are situations where high-level code needs to have direct access to
280the low level device capabilities or requires the ability to issue commands
281to the device bypassing some of the intermediate i/o layers.
282These could, for example, be special control commands issued through ioctl
283interfaces, or could be raw read/write commands that stress the drive's
284capabilities for certain kinds of fitness tests. Having direct interfaces at
285multiple levels without having to pass through upper layers makes
286it possible to perform bottom up validation of the i/o path, layer by
287layer, starting from the media.
288
289The normal i/o submission interfaces, e.g submit_bio, could be bypassed
290for specially crafted requests which such ioctl or diagnostics
291interfaces would typically use, and the elevator add_request routine
292can instead be used to directly insert such requests in the queue or preferably
293the blk_do_rq routine can be used to place the request on the queue and
294wait for completion. Alternatively, sometimes the caller might just
295invoke a lower level driver specific interface with the request as a
296parameter.
297
298If the request is a means for passing on special information associated with
299the command, then such information is associated with the request->special
300field (rather than misuse the request->buffer field which is meant for the
301request data buffer's virtual mapping).
302
303For passing request data, the caller must build up a bio descriptor
304representing the concerned memory buffer if the underlying driver interprets
305bio segments or uses the block layer end*request* functions for i/o
306completion. Alternatively one could directly use the request->buffer field to
307specify the virtual address of the buffer, if the driver expects buffer
308addresses passed in this way and ignores bio entries for the request type
309involved. In the latter case, the driver would modify and manage the
310request->buffer, request->sector and request->nr_sectors or
311request->current_nr_sectors fields itself rather than using the block layer
312end_request or end_that_request_first completion interfaces.
313(See 2.3 or Documentation/block/request.txt for a brief explanation of
314the request structure fields)
315
316[TBD: end_that_request_last should be usable even in this case;
317Perhaps an end_that_direct_request_first routine could be implemented to make
318handling direct requests easier for such drivers; Also for drivers that
319expect bios, a helper function could be provided for setting up a bio
320corresponding to a data buffer]
321
322<JENS: I dont understand the above, why is end_that_request_first() not
323usable? Or _last for that matter. I must be missing something>
324<SUP: What I meant here was that if the request doesn't have a bio, then
325 end_that_request_first doesn't modify nr_sectors or current_nr_sectors,
326 and hence can't be used for advancing request state settings on the
327 completion of partial transfers. The driver has to modify these fields
328 directly by hand.
329 This is because end_that_request_first only iterates over the bio list,
330 and always returns 0 if there are none associated with the request.
331 _last works OK in this case, and is not a problem, as I mentioned earlier
332>
333
3341.3.1 Pre-built Commands
335
336A request can be created with a pre-built custom command to be sent directly
337to the device. The cmd block in the request structure has room for filling
338in the command bytes. (i.e rq->cmd is now 16 bytes in size, and meant for
339command pre-building, and the type of the request is now indicated
340through rq->flags instead of via rq->cmd)
341
342The request structure flags can be set up to indicate the type of request
343in such cases (REQ_PC: direct packet command passed to driver, REQ_BLOCK_PC:
344packet command issued via blk_do_rq, REQ_SPECIAL: special request).
345
346It can help to pre-build device commands for requests in advance.
347Drivers can now specify a request prepare function (q->prep_rq_fn) that the
348block layer would invoke to pre-build device commands for a given request,
349or perform other preparatory processing for the request. This is routine is
350called by elv_next_request(), i.e. typically just before servicing a request.
351(The prepare function would not be called for requests that have REQ_DONTPREP
352enabled)
353
354Aside:
355 Pre-building could possibly even be done early, i.e before placing the
356 request on the queue, rather than construct the command on the fly in the
357 driver while servicing the request queue when it may affect latencies in
358 interrupt context or responsiveness in general. One way to add early
359 pre-building would be to do it whenever we fail to merge on a request.
360 Now REQ_NOMERGE is set in the request flags to skip this one in the future,
361 which means that it will not change before we feed it to the device. So
362 the pre-builder hook can be invoked there.
363
364
3652. Flexible and generic but minimalist i/o structure/descriptor.
366
3672.1 Reason for a new structure and requirements addressed
368
369Prior to 2.5, buffer heads were used as the unit of i/o at the generic block
370layer, and the low level request structure was associated with a chain of
371buffer heads for a contiguous i/o request. This led to certain inefficiencies
372when it came to large i/o requests and readv/writev style operations, as it
373forced such requests to be broken up into small chunks before being passed
374on to the generic block layer, only to be merged by the i/o scheduler
375when the underlying device was capable of handling the i/o in one shot.
376Also, using the buffer head as an i/o structure for i/os that didn't originate
Matt LaPlante4ae0edc2006-11-30 04:58:40 +0100377from the buffer cache unnecessarily added to the weight of the descriptors
Linus Torvalds1da177e2005-04-16 15:20:36 -0700378which were generated for each such chunk.
379
380The following were some of the goals and expectations considered in the
381redesign of the block i/o data structure in 2.5.
382
383i. Should be appropriate as a descriptor for both raw and buffered i/o -
384 avoid cache related fields which are irrelevant in the direct/page i/o path,
385 or filesystem block size alignment restrictions which may not be relevant
386 for raw i/o.
387ii. Ability to represent high-memory buffers (which do not have a virtual
388 address mapping in kernel address space).
Matt LaPlante4ae0edc2006-11-30 04:58:40 +0100389iii.Ability to represent large i/os w/o unnecessarily breaking them up (i.e
Linus Torvalds1da177e2005-04-16 15:20:36 -0700390 greater than PAGE_SIZE chunks in one shot)
391iv. At the same time, ability to retain independent identity of i/os from
392 different sources or i/o units requiring individual completion (e.g. for
393 latency reasons)
394v. Ability to represent an i/o involving multiple physical memory segments
395 (including non-page aligned page fragments, as specified via readv/writev)
Matt LaPlante4ae0edc2006-11-30 04:58:40 +0100396 without unnecessarily breaking it up, if the underlying device is capable of
Linus Torvalds1da177e2005-04-16 15:20:36 -0700397 handling it.
398vi. Preferably should be based on a memory descriptor structure that can be
399 passed around different types of subsystems or layers, maybe even
400 networking, without duplication or extra copies of data/descriptor fields
401 themselves in the process
402vii.Ability to handle the possibility of splits/merges as the structure passes
403 through layered drivers (lvm, md, evms), with minimal overhead.
404
405The solution was to define a new structure (bio) for the block layer,
406instead of using the buffer head structure (bh) directly, the idea being
407avoidance of some associated baggage and limitations. The bio structure
408is uniformly used for all i/o at the block layer ; it forms a part of the
409bh structure for buffered i/o, and in the case of raw/direct i/o kiobufs are
410mapped to bio structures.
411
4122.2 The bio struct
413
414The bio structure uses a vector representation pointing to an array of tuples
415of <page, offset, len> to describe the i/o buffer, and has various other
416fields describing i/o parameters and state that needs to be maintained for
417performing the i/o.
418
419Notice that this representation means that a bio has no virtual address
420mapping at all (unlike buffer heads).
421
422struct bio_vec {
423 struct page *bv_page;
424 unsigned short bv_len;
425 unsigned short bv_offset;
426};
427
428/*
429 * main unit of I/O for the block layer and lower layers (ie drivers)
430 */
431struct bio {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700432 struct bio *bi_next; /* request queue link */
433 struct block_device *bi_bdev; /* target device */
434 unsigned long bi_flags; /* status, command, etc */
Jens Axboe1eff9d32016-08-05 15:35:16 -0600435 unsigned long bi_opf; /* low bits: r/w, high: priority */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700436
437 unsigned int bi_vcnt; /* how may bio_vec's */
Kent Overstreet4f024f32013-10-11 15:44:27 -0700438 struct bvec_iter bi_iter; /* current index into bio_vec array */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700439
440 unsigned int bi_size; /* total size in bytes */
441 unsigned short bi_phys_segments; /* segments after physaddr coalesce*/
442 unsigned short bi_hw_segments; /* segments after DMA remapping */
443 unsigned int bi_max; /* max bio_vecs we can hold
444 used as index into pool */
445 struct bio_vec *bi_io_vec; /* the actual vec list */
446 bio_end_io_t *bi_end_io; /* bi_end_io (bio) */
447 atomic_t bi_cnt; /* pin count: free when it hits zero */
448 void *bi_private;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700449};
450
451With this multipage bio design:
452
453- Large i/os can be sent down in one go using a bio_vec list consisting
454 of an array of <page, offset, len> fragments (similar to the way fragments
455 are represented in the zero-copy network code)
456- Splitting of an i/o request across multiple devices (as in the case of
457 lvm or raid) is achieved by cloning the bio (where the clone points to
458 the same bi_io_vec array, but with the index and size accordingly modified)
459- A linked list of bios is used as before for unrelated merges (*) - this
460 avoids reallocs and makes independent completions easier to handle.
NeilBrown5705f702007-09-25 12:35:59 +0200461- Code that traverses the req list can find all the segments of a bio
462 by using rq_for_each_segment. This handles the fact that a request
463 has multiple bios, each of which can have multiple segments.
Kent Overstreet4f024f32013-10-11 15:44:27 -0700464- Drivers which can't process a large bio in one shot can use the bi_iter
Linus Torvalds1da177e2005-04-16 15:20:36 -0700465 field to keep track of the next bio_vec entry to process.
466 (e.g a 1MB bio_vec needs to be handled in max 128kB chunks for IDE)
467 [TBD: Should preferably also have a bi_voffset and bi_vlen to avoid modifying
468 bi_offset an len fields]
469
470(*) unrelated merges -- a request ends up containing two or more bios that
471 didn't originate from the same place.
472
473bi_end_io() i/o callback gets called on i/o completion of the entire bio.
474
475At a lower level, drivers build a scatter gather list from the merged bios.
476The scatter gather list is in the form of an array of <page, offset, len>
477entries with their corresponding dma address mappings filled in at the
478appropriate time. As an optimization, contiguous physical pages can be
479covered by a single entry where <page> refers to the first page and <len>
Lucas De Marchi25985ed2011-03-30 22:57:33 -0300480covers the range of pages (up to 16 contiguous pages could be covered this
Linus Torvalds1da177e2005-04-16 15:20:36 -0700481way). There is a helper routine (blk_rq_map_sg) which drivers can use to build
482the sg list.
483
484Note: Right now the only user of bios with more than one page is ll_rw_kio,
485which in turn means that only raw I/O uses it (direct i/o may not work
486right now). The intent however is to enable clustering of pages etc to
487become possible. The pagebuf abstraction layer from SGI also uses multi-page
488bios, but that is currently not included in the stock development kernels.
489The same is true of Andrew Morton's work-in-progress multipage bio writeout
490and readahead patches.
491
4922.3 Changes in the Request Structure
493
494The request structure is the structure that gets passed down to low level
495drivers. The block layer make_request function builds up a request structure,
496places it on the queue and invokes the drivers request_fn. The driver makes
497use of block layer helper routine elv_next_request to pull the next request
498off the queue. Control or diagnostic functions might bypass block and directly
499invoke underlying driver entry points passing in a specially constructed
500request structure.
501
502Only some relevant fields (mainly those which changed or may be referred
503to in some of the discussion here) are listed below, not necessarily in
504the order in which they occur in the structure (see include/linux/blkdev.h)
505Refer to Documentation/block/request.txt for details about all the request
506structure fields and a quick reference about the layers which are
507supposed to use or modify those fields.
508
509struct request {
510 struct list_head queuelist; /* Not meant to be directly accessed by
511 the driver.
512 Used by q->elv_next_request_fn
513 rq->queue is gone
514 */
515 .
516 .
517 unsigned char cmd[16]; /* prebuilt command data block */
518 unsigned long flags; /* also includes earlier rq->cmd settings */
519 .
520 .
521 sector_t sector; /* this field is now of type sector_t instead of int
522 preparation for 64 bit sectors */
523 .
524 .
525
526 /* Number of scatter-gather DMA addr+len pairs after
527 * physical address coalescing is performed.
528 */
529 unsigned short nr_phys_segments;
530
531 /* Number of scatter-gather addr+len pairs after
532 * physical and DMA remapping hardware coalescing is performed.
533 * This is the number of scatter-gather entries the driver
534 * will actually have to deal with after DMA mapping is done.
535 */
536 unsigned short nr_hw_segments;
537
538 /* Various sector counts */
539 unsigned long nr_sectors; /* no. of sectors left: driver modifiable */
540 unsigned long hard_nr_sectors; /* block internal copy of above */
541 unsigned int current_nr_sectors; /* no. of sectors left in the
542 current segment:driver modifiable */
543 unsigned long hard_cur_sectors; /* block internal copy of the above */
544 .
545 .
546 int tag; /* command tag associated with request */
547 void *special; /* same as before */
Lucas De Marchi25985ed2011-03-30 22:57:33 -0300548 char *buffer; /* valid only for low memory buffers up to
Linus Torvalds1da177e2005-04-16 15:20:36 -0700549 current_nr_sectors */
550 .
551 .
552 struct bio *bio, *biotail; /* bio list instead of bh */
553 struct request_list *rl;
554}
555
556See the rq_flag_bits definitions for an explanation of the various flags
557available. Some bits are used by the block layer or i/o scheduler.
558
559The behaviour of the various sector counts are almost the same as before,
560except that since we have multi-segment bios, current_nr_sectors refers
561to the numbers of sectors in the current segment being processed which could
562be one of the many segments in the current bio (i.e i/o completion unit).
563The nr_sectors value refers to the total number of sectors in the whole
564request that remain to be transferred (no change). The purpose of the
565hard_xxx values is for block to remember these counts every time it hands
566over the request to the driver. These values are updated by block on
567end_that_request_first, i.e. every time the driver completes a part of the
568transfer and invokes block end*request helpers to mark this. The
569driver should not modify these values. The block layer sets up the
570nr_sectors and current_nr_sectors fields (based on the corresponding
571hard_xxx values and the number of bytes transferred) and updates it on
572every transfer that invokes end_that_request_first. It does the same for the
Kent Overstreet4f024f32013-10-11 15:44:27 -0700573buffer, bio, bio->bi_iter fields too.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700574
575The buffer field is just a virtual address mapping of the current segment
576of the i/o buffer in cases where the buffer resides in low-memory. For high
577memory i/o, this field is not valid and must not be used by drivers.
578
579Code that sets up its own request structures and passes them down to
580a driver needs to be careful about interoperation with the block layer helper
581functions which the driver uses. (Section 1.3)
582
5833. Using bios
584
5853.1 Setup/Teardown
586
587There are routines for managing the allocation, and reference counting, and
588freeing of bios (bio_alloc, bio_get, bio_put).
589
590This makes use of Ingo Molnar's mempool implementation, which enables
591subsystems like bio to maintain their own reserve memory pools for guaranteed
592deadlock-free allocations during extreme VM load. For example, the VM
593subsystem makes use of the block layer to writeout dirty pages in order to be
594able to free up memory space, a case which needs careful handling. The
595allocation logic draws from the preallocated emergency reserve in situations
596where it cannot allocate through normal means. If the pool is empty and it
597can wait, then it would trigger action that would help free up memory or
598replenish the pool (without deadlocking) and wait for availability in the pool.
599If it is in IRQ context, and hence not in a position to do this, allocation
600could fail if the pool is empty. In general mempool always first tries to
601perform allocation without having to wait, even if it means digging into the
602pool as long it is not less that 50% full.
603
604On a free, memory is released to the pool or directly freed depending on
605the current availability in the pool. The mempool interface lets the
606subsystem specify the routines to be used for normal alloc and free. In the
607case of bio, these routines make use of the standard slab allocator.
608
609The caller of bio_alloc is expected to taken certain steps to avoid
610deadlocks, e.g. avoid trying to allocate more memory from the pool while
611already holding memory obtained from the pool.
612[TBD: This is a potential issue, though a rare possibility
613 in the bounce bio allocation that happens in the current code, since
614 it ends up allocating a second bio from the same pool while
615 holding the original bio ]
616
617Memory allocated from the pool should be released back within a limited
618amount of time (in the case of bio, that would be after the i/o is completed).
619This ensures that if part of the pool has been used up, some work (in this
620case i/o) must already be in progress and memory would be available when it
621is over. If allocating from multiple pools in the same code path, the order
622or hierarchy of allocation needs to be consistent, just the way one deals
623with multiple locks.
624
625The bio_alloc routine also needs to allocate the bio_vec_list (bvec_alloc())
626for a non-clone bio. There are the 6 pools setup for different size biovecs,
627so bio_alloc(gfp_mask, nr_iovecs) will allocate a vec_list of the
628given size from these slabs.
629
Linus Torvalds1da177e2005-04-16 15:20:36 -0700630The bio_get() routine may be used to hold an extra reference on a bio prior
631to i/o submission, if the bio fields are likely to be accessed after the
632i/o is issued (since the bio may otherwise get freed in case i/o completion
633happens in the meantime).
634
635The bio_clone() routine may be used to duplicate a bio, where the clone
636shares the bio_vec_list with the original bio (i.e. both point to the
637same bio_vec_list). This would typically be used for splitting i/o requests
638in lvm or md.
639
6403.2 Generic bio helper Routines
641
6423.2.1 Traversing segments and completion units in a request
643
NeilBrown5705f702007-09-25 12:35:59 +0200644The macro rq_for_each_segment() should be used for traversing the bios
645in the request list (drivers should avoid directly trying to do it
646themselves). Using these helpers should also make it easier to cope
647with block changes in the future.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700648
NeilBrown5705f702007-09-25 12:35:59 +0200649 struct req_iterator iter;
650 rq_for_each_segment(bio_vec, rq, iter)
651 /* bio_vec is now current segment */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700652
653I/O completion callbacks are per-bio rather than per-segment, so drivers
654that traverse bio chains on completion need to keep that in mind. Drivers
655which don't make a distinction between segments and completion units would
656need to be reorganized to support multi-segment bios.
657
6583.2.2 Setting up DMA scatterlists
659
660The blk_rq_map_sg() helper routine would be used for setting up scatter
661gather lists from a request, so a driver need not do it on its own.
662
663 nr_segments = blk_rq_map_sg(q, rq, scatterlist);
664
665The helper routine provides a level of abstraction which makes it easier
666to modify the internals of request to scatterlist conversion down the line
667without breaking drivers. The blk_rq_map_sg routine takes care of several
668things like collapsing physically contiguous segments (if QUEUE_FLAG_CLUSTER
669is set) and correct segment accounting to avoid exceeding the limits which
670the i/o hardware can handle, based on various queue properties.
671
672- Prevents a clustered segment from crossing a 4GB mem boundary
673- Avoids building segments that would exceed the number of physical
674 memory segments that the driver can handle (phys_segments) and the
675 number that the underlying hardware can handle at once, accounting for
676 DMA remapping (hw_segments) (i.e. IOMMU aware limits).
677
678Routines which the low level driver can use to set up the segment limits:
679
680blk_queue_max_hw_segments() : Sets an upper limit of the maximum number of
681hw data segments in a request (i.e. the maximum number of address/length
682pairs the host adapter can actually hand to the device at once)
683
684blk_queue_max_phys_segments() : Sets an upper limit on the maximum number
685of physical data segments in a request (i.e. the largest sized scatter list
686a driver could handle)
687
6883.2.3 I/O completion
689
690The existing generic block layer helper routines end_request,
691end_that_request_first and end_that_request_last can be used for i/o
692completion (and setting things up so the rest of the i/o or the next
693request can be kicked of) as before. With the introduction of multi-page
694bio support, end_that_request_first requires an additional argument indicating
695the number of sectors completed.
696
6973.2.4 Implications for drivers that do not interpret bios (don't handle
698 multiple segments)
699
700Drivers that do not interpret bios e.g those which do not handle multiple
701segments and do not support i/o into high memory addresses (require bounce
702buffers) and expect only virtually mapped buffers, can access the rq->buffer
703field. As before the driver should use current_nr_sectors to determine the
704size of remaining data in the current segment (that is the maximum it can
705transfer in one go unless it interprets segments), and rely on the block layer
706end_request, or end_that_request_first/last to take care of all accounting
707and transparent mapping of the next bio segment when a segment boundary
708is crossed on completion of a transfer. (The end*request* functions should
709be used if only if the request has come down from block/bio path, not for
710direct access requests which only specify rq->buffer without a valid rq->bio)
711
7123.2.5 Generic request command tagging
713
7143.2.5.1 Tag helpers
715
716Block now offers some simple generic functionality to help support command
717queueing (typically known as tagged command queueing), ie manage more than
718one outstanding command on a queue at any given time.
719
Jens Axboe165125e2007-07-24 09:28:11 +0200720 blk_queue_init_tags(struct request_queue *q, int depth)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700721
722 Initialize internal command tagging structures for a maximum
723 depth of 'depth'.
724
Jens Axboe165125e2007-07-24 09:28:11 +0200725 blk_queue_free_tags((struct request_queue *q)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700726
727 Teardown tag info associated with the queue. This will be done
728 automatically by block if blk_queue_cleanup() is called on a queue
729 that is using tagging.
730
731The above are initialization and exit management, the main helpers during
732normal operations are:
733
Jens Axboe165125e2007-07-24 09:28:11 +0200734 blk_queue_start_tag(struct request_queue *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700735
736 Start tagged operation for this request. A free tag number between
737 0 and 'depth' is assigned to the request (rq->tag holds this number),
738 and 'rq' is added to the internal tag management. If the maximum depth
739 for this queue is already achieved (or if the tag wasn't started for
740 some other reason), 1 is returned. Otherwise 0 is returned.
741
Jens Axboe165125e2007-07-24 09:28:11 +0200742 blk_queue_end_tag(struct request_queue *q, struct request *rq)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700743
744 End tagged operation on this request. 'rq' is removed from the internal
745 book keeping structures.
746
747To minimize struct request and queue overhead, the tag helpers utilize some
748of the same request members that are used for normal request queue management.
749This means that a request cannot both be an active tag and be on the queue
750list at the same time. blk_queue_start_tag() will remove the request, but
751the driver must remember to call blk_queue_end_tag() before signalling
752completion of the request to the block layer. This means ending tag
753operations before calling end_that_request_last()! For an example of a user
754of these helpers, see the IDE tagged command queueing support.
755
756Certain hardware conditions may dictate a need to invalidate the block tag
757queue. For instance, on IDE any tagged request error needs to clear both
758the hardware and software block queue and enable the driver to sanely restart
759all the outstanding requests. There's a third helper to do that:
760
Jens Axboe165125e2007-07-24 09:28:11 +0200761 blk_queue_invalidate_tags(struct request_queue *q)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700762
Matt LaPlanted6bc8ac2006-10-03 22:54:15 +0200763 Clear the internal block tag queue and re-add all the pending requests
Linus Torvalds1da177e2005-04-16 15:20:36 -0700764 to the request queue. The driver will receive them again on the
765 next request_fn run, just like it did the first time it encountered
766 them.
767
7683.2.5.2 Tag info
769
770Some block functions exist to query current tag status or to go from a
771tag number to the associated request. These are, in no particular order:
772
773 blk_queue_tagged(q)
774
775 Returns 1 if the queue 'q' is using tagging, 0 if not.
776
777 blk_queue_tag_request(q, tag)
778
779 Returns a pointer to the request associated with tag 'tag'.
780
781 blk_queue_tag_depth(q)
782
783 Return current queue depth.
784
785 blk_queue_tag_queue(q)
786
787 Returns 1 if the queue can accept a new queued command, 0 if we are
788 at the maximum depth already.
789
790 blk_queue_rq_tagged(rq)
791
792 Returns 1 if the request 'rq' is tagged.
793
7943.2.5.2 Internal structure
795
796Internally, block manages tags in the blk_queue_tag structure:
797
798 struct blk_queue_tag {
799 struct request **tag_index; /* array or pointers to rq */
800 unsigned long *tag_map; /* bitmap of free tags */
801 struct list_head busy_list; /* fifo list of busy tags */
802 int busy; /* queue depth */
803 int max_depth; /* max queue depth */
804 };
805
806Most of the above is simple and straight forward, however busy_list may need
807a bit of explaining. Normally we don't care too much about request ordering,
808but in the event of any barrier requests in the tag queue we need to ensure
809that requests are restarted in the order they were queue. This may happen
810if the driver needs to use blk_queue_invalidate_tags().
811
Linus Torvalds1da177e2005-04-16 15:20:36 -07008123.3 I/O Submission
813
814The routine submit_bio() is used to submit a single io. Higher level i/o
815routines make use of this:
816
817(a) Buffered i/o:
818The routine submit_bh() invokes submit_bio() on a bio corresponding to the
819bh, allocating the bio if required. ll_rw_block() uses submit_bh() as before.
820
821(b) Kiobuf i/o (for raw/direct i/o):
822The ll_rw_kio() routine breaks up the kiobuf into page sized chunks and
823maps the array to one or more multi-page bios, issuing submit_bio() to
824perform the i/o on each of these.
825
826The embedded bh array in the kiobuf structure has been removed and no
827preallocation of bios is done for kiobufs. [The intent is to remove the
828blocks array as well, but it's currently in there to kludge around direct i/o.]
829Thus kiobuf allocation has switched back to using kmalloc rather than vmalloc.
830
831Todo/Observation:
832
833 A single kiobuf structure is assumed to correspond to a contiguous range
834 of data, so brw_kiovec() invokes ll_rw_kio for each kiobuf in a kiovec.
835 So right now it wouldn't work for direct i/o on non-contiguous blocks.
836 This is to be resolved. The eventual direction is to replace kiobuf
837 by kvec's.
838
839 Badari Pulavarty has a patch to implement direct i/o correctly using
840 bio and kvec.
841
842
843(c) Page i/o:
844Todo/Under discussion:
845
846 Andrew Morton's multi-page bio patches attempt to issue multi-page
847 writeouts (and reads) from the page cache, by directly building up
848 large bios for submission completely bypassing the usage of buffer
849 heads. This work is still in progress.
850
851 Christoph Hellwig had some code that uses bios for page-io (rather than
852 bh). This isn't included in bio as yet. Christoph was also working on a
853 design for representing virtual/real extents as an entity and modifying
854 some of the address space ops interfaces to utilize this abstraction rather
855 than buffer_heads. (This is somewhat along the lines of the SGI XFS pagebuf
856 abstraction, but intended to be as lightweight as possible).
857
858(d) Direct access i/o:
859Direct access requests that do not contain bios would be submitted differently
860as discussed earlier in section 1.3.
861
862Aside:
863
864 Kvec i/o:
865
Matt LaPlante53cb4722006-10-03 22:55:17 +0200866 Ben LaHaise's aio code uses a slightly different structure instead
Linus Torvalds1da177e2005-04-16 15:20:36 -0700867 of kiobufs, called a kvec_cb. This contains an array of <page, offset, len>
868 tuples (very much like the networking code), together with a callback function
869 and data pointer. This is embedded into a brw_cb structure when passed
870 to brw_kvec_async().
871
872 Now it should be possible to directly map these kvecs to a bio. Just as while
873 cloning, in this case rather than PRE_BUILT bio_vecs, we set the bi_io_vec
874 array pointer to point to the veclet array in kvecs.
875
876 TBD: In order for this to work, some changes are needed in the way multi-page
877 bios are handled today. The values of the tuples in such a vector passed in
878 from higher level code should not be modified by the block layer in the course
879 of its request processing, since that would make it hard for the higher layer
880 to continue to use the vector descriptor (kvec) after i/o completes. Instead,
881 all such transient state should either be maintained in the request structure,
882 and passed on in some way to the endio completion routine.
883
884
8854. The I/O scheduler
Tejun Heo4c9f7832005-10-20 16:47:40 +0200886I/O scheduler, a.k.a. elevator, is implemented in two layers. Generic dispatch
887queue and specific I/O schedulers. Unless stated otherwise, elevator is used
888to refer to both parts and I/O scheduler to specific I/O schedulers.
889
Nikanth Karthikesan42364692008-11-24 10:46:29 +0100890Block layer implements generic dispatch queue in block/*.c.
Leonid V. Fedorenchik89627862015-03-13 23:53:22 +0300891The generic dispatch queue is responsible for requeueing, handling non-fs
892requests and all other subtleties.
Tejun Heo4c9f7832005-10-20 16:47:40 +0200893
894Specific I/O schedulers are responsible for ordering normal filesystem
895requests. They can also choose to delay certain requests to improve
896throughput or whatever purpose. As the plural form indicates, there are
897multiple I/O schedulers. They can be built as modules but at least one should
898be built inside the kernel. Each queue can choose different one and can also
899change to another one dynamically.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700900
901A block layer call to the i/o scheduler follows the convention elv_xxx(). This
Nikanth Karthikesan42364692008-11-24 10:46:29 +0100902calls elevator_xxx_fn in the elevator switch (block/elevator.c). Oh, xxx
903and xxx might not match exactly, but use your imagination. If an elevator
Linus Torvalds1da177e2005-04-16 15:20:36 -0700904doesn't implement a function, the switch does nothing or some minimal house
905keeping work.
906
9074.1. I/O scheduler API
908
909The functions an elevator may implement are: (* are mandatory)
910elevator_merge_fn called to query requests for merge with a bio
911
Tejun Heo4c9f7832005-10-20 16:47:40 +0200912elevator_merge_req_fn called when two requests get merged. the one
913 which gets merged into the other one will be
914 never seen by I/O scheduler again. IOW, after
915 being merged, the request is gone.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700916
917elevator_merged_fn called when a request in the scheduler has been
918 involved in a merge. It is used in the deadline
919 scheduler for example, to reposition the request
920 if its sorting order has changed.
921
Jens Axboe126ec9a62006-12-20 11:06:15 +0100922elevator_allow_merge_fn called whenever the block layer determines
923 that a bio can be merged into an existing
924 request safely. The io scheduler may still
925 want to stop a merge at this point if it
926 results in some sort of conflict internally,
Jan Karab8ab9562014-11-04 12:52:41 +0100927 this hook allows it to do that. Note however
928 that two *requests* can still be merged at later
929 time. Currently the io scheduler has no way to
930 prevent that. It can only learn about the fact
931 from elevator_merge_req_fn callback.
Jens Axboe126ec9a62006-12-20 11:06:15 +0100932
Nikanth Karthikesan75989092009-01-27 09:29:24 +0100933elevator_dispatch_fn* fills the dispatch queue with ready requests.
Tejun Heo4c9f7832005-10-20 16:47:40 +0200934 I/O schedulers are free to postpone requests by
935 not filling the dispatch queue unless @force
936 is non-zero. Once dispatched, I/O schedulers
937 are not allowed to manipulate the requests -
938 they belong to generic dispatch queue.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700939
Nikanth Karthikesan75989092009-01-27 09:29:24 +0100940elevator_add_req_fn* called to add a new request into the scheduler
Linus Torvalds1da177e2005-04-16 15:20:36 -0700941
Linus Torvalds1da177e2005-04-16 15:20:36 -0700942elevator_former_req_fn
943elevator_latter_req_fn These return the request before or after the
944 one specified in disk sort order. Used by the
945 block layer to find merge possibilities.
946
Tejun Heo4c9f7832005-10-20 16:47:40 +0200947elevator_completed_req_fn called when a request is completed.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700948
949elevator_may_queue_fn returns true if the scheduler wants to allow the
950 current context to queue a new request even if
951 it is over the queue limit. This must be used
952 very carefully!!
953
954elevator_set_req_fn
955elevator_put_req_fn Must be used to allocate and free any elevator
Tejun Heo4c9f7832005-10-20 16:47:40 +0200956 specific storage for a request.
957
958elevator_activate_req_fn Called when device driver first sees a request.
959 I/O schedulers can use this callback to
960 determine when actual execution of a request
961 starts.
962elevator_deactivate_req_fn Called when device driver decides to delay
963 a request by requeueing it.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700964
Nikanth Karthikesan75989092009-01-27 09:29:24 +0100965elevator_init_fn*
Linus Torvalds1da177e2005-04-16 15:20:36 -0700966elevator_exit_fn Allocate and free any elevator specific storage
967 for a queue.
968
Tejun Heo4c9f7832005-10-20 16:47:40 +02009694.2 Request flows seen by I/O schedulers
Matt LaPlante53cb4722006-10-03 22:55:17 +0200970All requests seen by I/O schedulers strictly follow one of the following three
Tejun Heo4c9f7832005-10-20 16:47:40 +0200971flows.
972
973 set_req_fn ->
974
975 i. add_req_fn -> (merged_fn ->)* -> dispatch_fn -> activate_req_fn ->
976 (deactivate_req_fn -> activate_req_fn ->)* -> completed_req_fn
977 ii. add_req_fn -> (merged_fn ->)* -> merge_req_fn
978 iii. [none]
979
980 -> put_req_fn
981
9824.3 I/O scheduler implementation
Linus Torvalds1da177e2005-04-16 15:20:36 -0700983The generic i/o scheduler algorithm attempts to sort/merge/batch requests for
984optimal disk scan and request servicing performance (based on generic
985principles and device capabilities), optimized for:
986i. improved throughput
987ii. improved latency
988iii. better utilization of h/w & CPU time
989
990Characteristics:
991
992i. Binary tree
993AS and deadline i/o schedulers use red black binary trees for disk position
994sorting and searching, and a fifo linked list for time-based searching. This
Matt LaPlante5d3f0832006-11-30 05:21:10 +0100995gives good scalability and good availability of information. Requests are
Linus Torvalds1da177e2005-04-16 15:20:36 -0700996almost always dispatched in disk sort order, so a cache is kept of the next
997request in sort order to prevent binary tree lookups.
998
999This arrangement is not a generic block layer characteristic however, so
1000elevators may implement queues as they please.
1001
Tejun Heo4c9f7832005-10-20 16:47:40 +02001002ii. Merge hash
Linus Torvalds1da177e2005-04-16 15:20:36 -07001003AS and deadline use a hash table indexed by the last sector of a request. This
1004enables merging code to quickly look up "back merge" candidates, even when
1005multiple I/O streams are being performed at once on one disk.
1006
1007"Front merges", a new request being merged at the front of an existing request,
1008are far less common than "back merges" due to the nature of most I/O patterns.
1009Front merges are handled by the binary trees in AS and deadline schedulers.
1010
Tejun Heo4c9f7832005-10-20 16:47:40 +02001011iii. Plugging the queue to batch requests in anticipation of opportunities for
1012 merge/sort optimizations
Linus Torvalds1da177e2005-04-16 15:20:36 -07001013
Linus Torvalds1da177e2005-04-16 15:20:36 -07001014Plugging is an approach that the current i/o scheduling algorithm resorts to so
1015that it collects up enough requests in the queue to be able to take
1016advantage of the sorting/merging logic in the elevator. If the
1017queue is empty when a request comes in, then it plugs the request queue
Jens Axboe329007c2009-04-08 11:38:50 +02001018(sort of like plugging the bath tub of a vessel to get fluid to build up)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001019till it fills up with a few more requests, before starting to service
1020the requests. This provides an opportunity to merge/sort the requests before
1021passing them down to the device. There are various conditions when the queue is
1022unplugged (to open up the flow again), either through a scheduled task or
1023could be on demand. For example wait_on_buffer sets the unplugging going
Jens Axboe329007c2009-04-08 11:38:50 +02001024through sync_buffer() running blk_run_address_space(mapping). Or the caller
1025can do it explicity through blk_unplug(bdev). So in the read case,
1026the queue gets explicitly unplugged as part of waiting for completion on that
Matthew Wilcoxf4e6d8442016-03-06 23:27:26 -05001027buffer.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001028
1029Aside:
1030 This is kind of controversial territory, as it's not clear if plugging is
1031 always the right thing to do. Devices typically have their own queues,
1032 and allowing a big queue to build up in software, while letting the device be
1033 idle for a while may not always make sense. The trick is to handle the fine
1034 balance between when to plug and when to open up. Also now that we have
1035 multi-page bios being queued in one shot, we may not need to wait to merge
1036 a big request from the broken up pieces coming by.
1037
Tejun Heo4c9f7832005-10-20 16:47:40 +020010384.4 I/O contexts
Linus Torvalds1da177e2005-04-16 15:20:36 -07001039I/O contexts provide a dynamically allocated per process data area. They may
1040be used in I/O schedulers, and in the block layer (could be used for IO statis,
Ben Collins1d193f42005-11-15 00:09:21 -08001041priorities for example). See *io_context in block/ll_rw_blk.c, and as-iosched.c
1042for an example of usage in an i/o scheduler.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001043
1044
10455. Scalability related changes
1046
10475.1 Granular Locking: io_request_lock replaced by a per-queue lock
1048
1049The global io_request_lock has been removed as of 2.5, to avoid
1050the scalability bottleneck it was causing, and has been replaced by more
1051granular locking. The request queue structure has a pointer to the
1052lock to be used for that queue. As a result, locking can now be
1053per-queue, with a provision for sharing a lock across queues if
1054necessary (e.g the scsi layer sets the queue lock pointers to the
1055corresponding adapter lock, which results in a per host locking
1056granularity). The locking semantics are the same, i.e. locking is
1057still imposed by the block layer, grabbing the lock before
1058request_fn execution which it means that lots of older drivers
1059should still be SMP safe. Drivers are free to drop the queue
1060lock themselves, if required. Drivers that explicitly used the
1061io_request_lock for serialization need to be modified accordingly.
1062Usually it's as easy as adding a global lock:
1063
Robert P. J. Dayc0d1f292008-04-21 22:44:50 +00001064 static DEFINE_SPINLOCK(my_driver_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001065
1066and passing the address to that lock to blk_init_queue().
1067
10685.2 64 bit sector numbers (sector_t prepares for 64 bit support)
1069
1070The sector number used in the bio structure has been changed to sector_t,
1071which could be defined as 64 bit in preparation for 64 bit sector support.
1072
10736. Other Changes/Implications
1074
10756.1 Partition re-mapping handled by the generic block layer
1076
1077In 2.5 some of the gendisk/partition related code has been reorganized.
1078Now the generic block layer performs partition-remapping early and thus
1079provides drivers with a sector number relative to whole device, rather than
1080having to take partition number into account in order to arrive at the true
1081sector number. The routine blk_partition_remap() is invoked by
1082generic_make_request even before invoking the queue specific make_request_fn,
1083so the i/o scheduler also gets to operate on whole disk sector numbers. This
1084should typically not require changes to block drivers, it just never gets
1085to invoke its own partition sector offset calculations since all bios
1086sent are offset from the beginning of the device.
1087
1088
10897. A Few Tips on Migration of older drivers
1090
1091Old-style drivers that just use CURRENT and ignores clustered requests,
1092may not need much change. The generic layer will automatically handle
1093clustered requests, multi-page bios, etc for the driver.
1094
1095For a low performance driver or hardware that is PIO driven or just doesn't
1096support scatter-gather changes should be minimal too.
1097
1098The following are some points to keep in mind when converting old drivers
1099to bio.
1100
1101Drivers should use elv_next_request to pick up requests and are no longer
1102supposed to handle looping directly over the request list.
1103(struct request->queue has been removed)
1104
1105Now end_that_request_first takes an additional number_of_sectors argument.
1106It used to handle always just the first buffer_head in a request, now
1107it will loop and handle as many sectors (on a bio-segment granularity)
1108as specified.
1109
1110Now bh->b_end_io is replaced by bio->bi_end_io, but most of the time the
Christoph Hellwig4246a0b2015-07-20 15:29:37 +02001111right thing to use is bio_endio(bio) instead.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001112
1113If the driver is dropping the io_request_lock from its request_fn strategy,
1114then it just needs to replace that with q->queue_lock instead.
1115
1116As described in Sec 1.1, drivers can set max sector size, max segment size
1117etc per queue now. Drivers that used to define their own merge functions i
1118to handle things like this can now just use the blk_queue_* functions at
1119blk_init_queue time.
1120
1121Drivers no longer have to map a {partition, sector offset} into the
1122correct absolute location anymore, this is done by the block layer, so
1123where a driver received a request ala this before:
1124
1125 rq->rq_dev = mk_kdev(3, 5); /* /dev/hda5 */
1126 rq->sector = 0; /* first sector on hda5 */
1127
1128 it will now see
1129
1130 rq->rq_dev = mk_kdev(3, 0); /* /dev/hda */
1131 rq->sector = 123128; /* offset from start of disk */
1132
1133As mentioned, there is no virtual mapping of a bio. For DMA, this is
1134not a problem as the driver probably never will need a virtual mapping.
FUJITA Tomonoric2282ad2010-03-08 09:11:07 +01001135Instead it needs a bus mapping (dma_map_page for a single segment or
1136use dma_map_sg for scatter gather) to be able to ship it to the driver. For
Linus Torvalds1da177e2005-04-16 15:20:36 -07001137PIO drivers (or drivers that need to revert to PIO transfer once in a
1138while (IDE for example)), where the CPU is doing the actual data
1139transfer a virtual mapping is needed. If the driver supports highmem I/O,
1140(Sec 1.1, (ii) ) it needs to use __bio_kmap_atomic and bio_kmap_irq to
1141temporarily map a bio into the virtual address space.
1142
1143
11448. Prior/Related/Impacted patches
1145
11468.1. Earlier kiobuf patches (sct/axboe/chait/hch/mkp)
1147- orig kiobuf & raw i/o patches (now in 2.4 tree)
1148- direct kiobuf based i/o to devices (no intermediate bh's)
1149- page i/o using kiobuf
1150- kiobuf splitting for lvm (mkp)
1151- elevator support for kiobuf request merging (axboe)
11528.2. Zero-copy networking (Dave Miller)
11538.3. SGI XFS - pagebuf patches - use of kiobufs
11548.4. Multi-page pioent patch for bio (Christoph Hellwig)
11558.5. Direct i/o implementation (Andrea Arcangeli) since 2.4.10-pre11
11568.6. Async i/o implementation patch (Ben LaHaise)
11578.7. EVMS layering design (IBM EVMS team)
11588.8. Larger page cache size patch (Ben LaHaise) and
1159 Large page size (Daniel Phillips)
1160 => larger contiguous physical memory buffers
11618.9. VM reservations patch (Ben LaHaise)
11628.10. Write clustering patches ? (Marcelo/Quintela/Riel ?)
11638.11. Block device in page cache patch (Andrea Archangeli) - now in 2.4.10+
11648.12. Multiple block-size transfers for faster raw i/o (Shailabh Nagar,
1165 Badari)
11668.13 Priority based i/o scheduler - prepatches (Arjan van de Ven)
11678.14 IDE Taskfile i/o patch (Andre Hedrick)
11688.15 Multi-page writeout and readahead patches (Andrew Morton)
11698.16 Direct i/o patches for 2.5 using kvec and bio (Badari Pulavarthy)
1170
11719. Other References:
1172
11739.1 The Splice I/O Model - Larry McVoy (and subsequent discussions on lkml,
1174and Linus' comments - Jan 2001)
11759.2 Discussions about kiobuf and bh design on lkml between sct, linus, alan
1176et al - Feb-March 2001 (many of the initial thoughts that led to bio were
Matt LaPlantefff92892006-10-03 22:47:42 +02001177brought up in this discussion thread)
Linus Torvalds1da177e2005-04-16 15:20:36 -070011789.3 Discussions on mempool on lkml - Dec 2001.
1179