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.

18/07/2005

(Note that most code is common to all versions of FreeBSD, although the 4.x branch can use some simplifications due to the different locking model in the kernel.)BR

Disk I/O requests (bio) are stored into a queue (bioq), one per device, sorted by a 'disksort' routine. Manipulations of the data structure 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. XXX check if this is always the result of the previous bioq_first; it would be very strange otherwise.

Our work virtualizes this interface through function pointers or wrappers, depending on the needs, so that different disk schedulers can be loaded and possibly switched at runtime.

Clearly, depending on the 'sorting' (or 'scheduling') algorithm, the queue must be extended with additional information. The native disk scheduler in FreeBSD implements an algorithm called C-LOOK, and the bioq contains a TAILQ plus specific fields to support this algorithm. In a perfect world, the bioq should contain fields which are different for each algorithm. To miminize code differences and ease implementation, we will try to minimize the differences with the existing code.

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 */

        disksched_fun_t *disksort;
        disksched_fun_t *remove;
        disksched_fun2_t *get_first;
        disksched_init_t *init;
        disksched_flush_t *flush;
        void (*load)(void);     /* load scheduler */
        void (*unload)(void);   /* unload scheduler */
};

initialized with pointers to the various functions. 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 either through a direct pointer in the *bioq, or through a lookup table (the number of devices is typically small so the cost of the lookup should be reasonably small). The struct is then deallocated when *flush() is called.

sysctl vfs.scheduler.name=foo selects the disk scheduler named foo. This is implemented, roughly speaking, by looking up a matching name, replacing the bioq_* function pointers with pointers to the functions of the new scheduler, and requeueing pending bios from the old to the new queue. We say 'roughly speaking' because there are locking issues to be considered that have different solutions between RELENG_4 and other releases.

In RELENG_4, locking is achieved simply by using splbio(). So we can do everything without changing the bioq - when the sysctl to switch the scheduler is issued, we run its handler in an splbio()/splx() section where we perform all the required operations.

In newer releases, bioq's are locked by each driver, and the scheduler does not know the type or address of the lock. Thus, the sysctl handler does not have a chance to lock the individual queues. To solve this problem we do as follows.

The bioq is extended with a pointer to a _disk_sched_interface (api), representing the scheduler currently active on the device. The sysctl does supdate the pointer to the new (globally selected) scheduler but it does not touch the individual bioq's. Individual scheduler switching is deferred to the next requests to the scheduler. This simplifies the problem a lot because these requests are issued with the queue locked so we do not have to worry about it ourselves. When the requests arrive, the scheduler can quickly determine if there is a pending scheduler switch on that device. If there is none, then the appropriate function is called. Otherwise we have these possible calls:

• bioq_disksort(). If the queue is empty we can switch the queue to the new scheduler and run the new disksort(). Otherwise, store the request in a temporary queue, in FIFO order, to resubmit them later. Because the queue is not empty, the driver (which will expect to find something in the queue) will be happy anyways.
• bioq_first(). If the queue is empty we can switch the queue to the new scheduler, and possibly requeue requests from the temporary queue calling the new disksort. Then return the result of the new *get_first().BR If the queue is not empty, return the result of the old *get_first().
• bioq_remove(). Remove the specified element, then if the queue becomes empty switch to the new scheduler and requeue any requests from the temporary queue.

This approach works even with multiple sysctl issued while a scheduler switching is pending on a given device.

Given that we need to modify the bioq to store the API, we can also add there a pointer to the scheduler-specific info, thus making the lookup process even cheaper.

17/07/2005: Hybrid scheduler is now implemented and works on FreeBSD 4.x (working on performance testing now). Implementation can only insure 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