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