Pluggable disk scheduler for FreeBSD

The FreeBSD disk scheduler is the standard “elevator”, also known as C-LOOK, which is designed to maximize throughput, but cannot grant fairness among clients of the disk subsystem. In fact, large sequential I/O requests, or certain access patterns from one or a few processes, might almost completely starve other processes. This is particularly critical for applications with soft real time requirements such as audio/video players (or, to some degree, recorders).BR The problem could be solved by: BR 1) Implementing support for pluggable (ie. run-time selectable) disk schedulers, and BR 2) Implementing some of the disk schedulers presented in the literature that give better fairness guarantees. This would not only allow users with specific requirements to fulfill them, but also help experimenting with new proposals in this area. Our choice will be one called Hybrid, which is a variant of a proportional share scheduler.

26/08/2005 RELENG_4 and RELENG_5 were under heavy testing on August. Release candidate code can be found at http://www.happyemi.org/hybrid/ BR The following things were made:

• Added credentials to requests (bio) for the ATA, MFS and AIO drivers (see below the “credentials” section)
• A lot of bugs have been fixed.
• Added the “credentials” section to the architectural overview below.

26/07/2005 improved architectural overview below. Fixed some bugs. Posted current version of the code at http://info.iet.unipi.it/~luigi/hybrid/

• completed coding of scheduler switch and one sample scheduler, HYBRID;
• modified 'nice' to implement per-process I/O priorities;
• implemented a sysctl interface to provide per-uid and per-gid priorities;
• tested under RELENG_4 and RELENG_5.

• struct bioq changed to support extra fields;
• struct proc changed to add per-proc I/O weights (temporary)
• nice -d x … runs a process with I/O weight x
• sysctl vfs.scheduler.name=hybrid selects a new scheduler
• sysctl vfs.scheduler.classifier={PID|UID|GID} selects the way I/O is classified.

• add manpages;
• scheduler should be less verbose.

18/07/2005 first draft of the architectural overview (matching the code).

[Note that most code is common to all versions of FreeBSD. The 4.x branch could use some simplifications due to the different locking model in the kernel, but we decided to use the same architecture in all branches to ease debugging.]BR

Disk I/O requests (bio) are stored into a queue (bioq), one per device, sorted by a 'disksort' routine. Manipulations of the queue occur through the following routines

• bioq_init(bioq) initializes the queue. Typically called at device attach time.
• bioq_flush(bioq, …) flushes the queue. Typically called at device detach time.
• bioq_disksort(bioq, bio) adds the new request to the queue.
• bioq_first(bioq) returns the address of the next request to serve, or NULL if the queue is empty.
• bioq_remove(bioq, bio) removes the specified request from the queue.

Note that, while not exactly specified, once bioq_first() returns a non-null value, all subsequent calls must return the same value until bioq_remove() is called, even if there are bioq_disksort() calls in the middle. This is because there is no way to notify the scheduler that a block is under service. With the native disk scheduler this is not an issue because the request at the head cannot be changed by subsequent requests, but different scheduling algorithms could have different effects on the ordering of requests.

Our work virtualizes this interface and extends the queue so that different disk schedulers can be loaded and possibly switched at runtime.

Each disk scheduling algorithm implements a disk scheduler API which is exported through a structure

struct _disk_sched_interface {
       struct _disk_sched_interface *next;
       char *name;     /* symbolic name */
       int refcount;   /* users of this scheduler */

       void (*disksort)(struct buf_queue_head *head, struct buf *bp);
       void (*remove)(struct buf_queue_head *head, struct buf *bp);
       struct buf *(*get_first)(struct buf_queue_head *head);
       void (*init)(struct buf_queue_head *head);
       void (*delete)(struct buf_queue_head *head);
       void (*load)(void);     /* load scheduler */
       void (*unload)(void);   /* unload scheduler */
};

Typically, for each *init() call, the scheduler will allocate a struct containing extra device information to complement those in the bioq. The link to this struct will be through a direct pointer in the *bioq, which also contains a pointer to the _disk_sched_interface in use for the sysctl vfs.scheduler.name=foo selects the disk scheduler named foo. The extra info is deleted by calling *delete() at appropriate times, typically at the end of the bioq_flush() routine, or when a scheduler switch is performed. *disksort(), *get_first() and *remove() are simply pointers to the scheduler- specific parts of the bioq_*() calls.

The bioq is extended with a pointer to the _disk_sched_interface currently in use for the queue, a version number, a pointer to the scheduler-specific info, and little more.

Normal operation simply dispatches the bioq_*() call to the scheduler-specific function. These accesses are protected by the individual device locks.

Scheduler switch requests are issued through a sysctl. Not knowing how/if the queues are in use, all the sysctl handler can do is record the request through an increment of a version number and an update of the pointer to the requested scheduler. At the next useful bioq_*() request, individual queues will detect the change, try to cleanup pending requests, and switch to the new scheduler. At the moment the process is implemented by diverting all requests to a 'suspend' queue until the scheduler is empty, then performing the switch and requeueing all pending requests with the new scheduler. This will be optimized in the future.

To have an accounting system (e.g. a way to provide fairness among processes) we have to “mark” a bio as owned by someone; so a new field must be added to the bio structure. The mark cannot be set into scheduler functions because we have no info about the process who created the request there, as curproc pointer may even be invalid. The only way to mark a bio with his real owner is when the bio itself is created. Unfortunetly, each driver (such as ATA driver, MFS driver, AIO driver, etc) seems to have its couple of functions to get a bio request, so we must add to each of these function a call which marks the new bio field.

Actually, ATA, MFS and AIO driver have been modified.

17/07/2005: Hybrid scheduler is now implemented and works on FreeBSD 4.x (working on performance testing now). Implementation can only ensure fairness among processes for now; I'm currently working to get fairness among users and groups, too (an accounting system).BR

Scheduler switching is the major issue now: we need a way to move requests from the old scheduler to the new one. On FreeBSD 4.x it is easy, because it does not use semaphores: we just disable interrupts and we can access without issues to the disk queues.BR On FreeBSD 5.x and 6.x however things are not so easy. Queues are protected with semaphores which are used by the ATA driver when needed. bio_* functions are always called with the queue locked so we can do what we want there. But during scheduler switching we need a way to obtain the lock to work on the queue. However this is neither easy nor clean: sempahore is a driver “private” member. Driver knows when lock and unlock it, and a direct access to the semaphore will break incapsulation; this means that we could cause deadlocks and others bad things.BR One way to address the problem may be the following:BR we know that each request is inserted invoking bioq_disksort and deleted calling bioq_remove. When a scheduler switching is involved we put all incoming requests in a support queue, which is different from the one used by the scheduler. Eventually, the scheduler queue will become empty after consequentially calls to bioq_remove. When this happens, we can do the very scheduler switching and insert requests from the support queue to the new sheduler queue. An important thing to say is that inserting requests is NOT done by calling the bio_disksort (as previously stated we should obtain a lock before calling disksort and we can't); instead we call the “strategy” function. strategy is generally called by the filesystem to read/write a request from/to the disk. Its work is to initialize the driver to accept requests (which among all things also means obtain the lock to the driver queue) and then calling bioq_disksort. If we call strategy to insert requests to the new driver we do not need to worry about the semaphore because strategy function will do this for us.

07/07/2005: What stated in the previous report is now implemented on FreeBSD 4.x. The 'id' is a string which is “cscan” for the default scheduler and will be “hybrid” for the new scheduler which I'm implementing just now. Scheduler switching can be done with a sysctl call like: “sysctl vfs.scheduler.name=foo”. On FreeBSD 5.x, default functions have little different names:

1. bio_disksort, called by filesystem to schedule disk requests
2. bio_first, called by phisical device to get the next request to serve
3. bio_remove, called by phisical device to remove a request from the queue (This is always called AFTER bufq_first).

Changes to FreeBSD 4.x should work in the same way in the 5.x branch, too, but are not implemented just now.BR Note: I shall decide what happens to pending requests when a scheduler switching is involved. Basic idea is to add two function pointers to the elements of the linked list, named “init” and “flush” respectively. When a scheduler switching in involved, we can call the “flush” function for the exiting scheduler and “init” for the starting one. There are to way to manage pending requests:

1. A scheduler should put all pending requests a data structure which is returned by “flush” and then passed to the starting scheduler using “init”. This method requires a bit of programming.
2. When exiting, a scheduler can put pending requests into the default queue (the one used by cscan) and the new one can read requests from there. There is no need to write code for this solution, but it's not a “clean” way to manage the issue

01/07/2005: FreeBSD 4.x scheduling interface exports three functions called by OS:

1. bufqdisksort, called by filesystem to schedule disk requests
2. bufq_first, called by phisical device to get the next request to serve
3. bufq_remove, called by phisical device to remove a request from the queue (This is always called AFTER bufq_first).

Whatever scheduler you'd like implementing, you need to rewrite the previous three functions to do the “dirty” job.BR Actually, FreeBSD has no support for scheduler switching, so the first thing to do is to add it.BR Basic idea is to make bufqdisksort, bufq_first and bufq_remove pointer functions so that they can “point” to the specific scheduler procedures.BR We will create a linked list, in which each element represets a scheduler. An element should have the following fields:

• An 'id', which is unique among all schedulers
• Function pointers to the scheduler specific bufqdisksort, bufq_first and bufq_remove

The default FreeBSD scheduler (aka. CLOOK) shall be added to this list, too. Using the 'sysctl' command (and passing it the 'id') at runtime is possible to select the current scheduler. Each time a scheduler is selected, we shall copy the functions pointer contained in the list element to the “global” bufqdisksort, bufq_first and bufq_remove. This also have a big advantage: we don't need to change parts in the kernel which contains call to those functions.

s223560@studenti.ing.unipi.it