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