There are a few things your multitasking kernel will have to handle before you can actually start writing a good multitasked disk driver.

1. be able to suspend and resume threads. This will be mandatory so that the system can continue doing useful job while a requestor thread is waiting for I/O operation to complete.
2. be able to perform dynamic memory allocation. As we'll need request queues, buffer pages list, etc. it is mandatory that the kernel programming interface provide a efficient way to allocate and free small structures on demand.
   
3. be able to allocate memory that suits I/O needs. As a first step, we'll just use programmed I/O modes for ATA disks, which have no special needs in what memory buffers are used, but floppies (which use ISA DMA) and ultra-dma mode (which uses PCI-DMA) behave differently and will require for instance the guarantee that memory buffers are in the lowest 16MB of physical memory and do not cross a 64KB barrier.
4. be able to lock I/O regions for a given driver. For instance, you must ensure that only one software component may attemp to perform I/O operations on the disk controller, to ensure operations coherency. If you're in a monolithic kernel that doesn't support any kind of dynamic loading of kernel-level code, it's just a compile-time problem. If you have microkernel or modular kernel approach, you'll probably need a centralized IO map that tells which IO region is free and who use locked regions. io/ioman/ioman.c does something like this.
5. be able to access buffer memory whatever the current address space is. As the IO operation is likely to complete while the CPU is running another process than the requestor process, something will have to be done to modify the requestor process's address space from another process (at kernel level, of course). We'll see later how this can be done.

How disks work

Rough overview

A hard disk can be seen as a large array of sectors, every sector having the very same byte size (usually 512 bytes for PC-compatible systems). Sectors are identified either geographically (with head-positionning, disk orientation and head selection informations -- this is known as Cylinder-Head-Sector addressing) or logically (the disk takes care of translating O..N-1 sector address into geographic information).
Requests can be done to read up to M sectors in memory or to write memory data in M contiguous sectors. The notion of "contiguous" depends on the disk, but usually, it is designed so that latency to access the next sector is minimized, which is:

1. the next sector is on the same "track", i.e. it just uses the same head position and selection - but the disk must rotate so that it can be accessed. As the disks are usually continuously rotating, this make the next sector readable almost immediately after the current one.
2. the next sector is on the next "track", but in the same "cylinder", i.e. another head must be selected, but the heads do not need to move. Because the hardware usually uses only one head at a time, it may need some extra time for the head to synchronize bit starts and ends (see docs on bits encoding for more explanation), but it can roughly be assumed that the access time is close to case 1.
3. the next sector is on the next cylinder, i.e. the heads have to move to another physical position to perform the read/write operation. Heads displacement are usually the slowest part of disk access, because it involves mechanical moves, while almost everything was electronic only, so far.

To achieve good performance, it is critical that related data are kept on close cylinders -- or better, on the same cylinder. The more the heads move, the lower your throughput is. FAT system that have fragmented files and concentrate every disk management structures at the head of the disk are one of the worst possible organisation, from a performance point of view...

Programming a disk access - the PIO approach

In Programmed I/O mode, the following things need to be done:

1. make sure the controller is ready to receive a new request.
   
2. select disk on which we operate (if there are several disks for the same controller -- which is the case for ATA)
3. write the sector address and the amount of sectors to be transferred in the controller's registers.
4. issue the command (read or write, with the proper mode selection)

Once the command has been issued, the disk will move heads to the given address (if needed) and starts reading the data in its internal buffer. As soon as one sector has been completely read, an interrupt is sent to the processor, which will:

1. check the status of the controller, making sure the request has been successful (for instance, if we ask for reading a sector that is not a valid address for this disk, an error code will be present).
2. read datas out of the controller's buffer and writing them in their final location.

For ATA disks in legacy PIO mode, having read the last data word means that you're ready to receive the next interrupt (as soon  as the disk is ready too). What is important to note is that the disk's internal buffer allow us to decouple CPU and disk logic -- i.e. if for some reason, reading the data from the controller is slower than reading the data from the disk into the controller, we just don't have to worry.

Writing requests are handled a very similar manner, except that you must fill the controller buffer with the data for one sector before the interrupt is raised, but after making sure the command has been accepted by the disk (i.e. the controller status returns to "not BUSY").

Multi-space Buffer issues

Basically, we have two options when handling buffers for disk I/O: either the buffer memory belongs to the driver or it belongs to the requestor. The former approach requires a copy of the data from the buffer to the final target place, while the latter one allow us to use the final target (or source) place immediately.
If the device allow us to do it (i.e. if this is not a ISA-DMA device), we will chose the latter approach for it gives better performances.

However, this implies that the interrupt (which may appear at any time, thus in any process) will have to access the requestor address space from the interrupt-handler space. Dealing with this kind of situation means that we'll need a memory-manager service that allow its client to say "please map the following page frames on some virtual addresses of your choice", while the usual approach is "please fill the given virtual addresses with page frames of your choice".

The problem is solved by a two-step model: the buffer provided by the application is first lockedand a page list is build from it, then the page list (or more likely parts of it) is mapped in the handler's address space, as depicted on the following picture.



so far, i have nothing to offer for people that want to lock the same pages several times... any attempt to do so in Clicker will result in a "locked pages" error returned by the disk driver.

Our design

Dealing with Mutual Exclusion

Of course, as several thread could possibly be sending requests at the same time, we must ensure that the state of the controller and of the queue remains consistent by a proper mutual exclusion scheme. However, as we're also coding in interrupt handlers, we cannot afford things like making the thread sleep until the object get unlocked.
We must also make sure that we minimize the amount of time while the interrupts are locked. calling ataDoRead() or ataDoWrite() for instance may be fairly long and we don't wish to block high-priority events (like clock or keyboard interrupt).

Thus rather than keeping interrupts disabled during the whole handler, it is good practice to re-enable them as soon as possible (for instance, just after having read the status out of the controller). We will not, however, send the "clearance code" outb(0x20,0x20) to the interrupt controller, which means we're sure that no other interrupt will occur for this disk controller until we're done.

Available synchronization primitives

Two synchronization techniques have been used for handling mutual exclusion in this driver: semaphores and system locks. The semaphore implements the well-known abstraction: when the resource is available, ksemWait() gets it atomicly and if it is not, the current thread will sleep until it becomes available.

System locks (called "mutexes" internally) never put the thread in sleep state. On single-cpu system, they just lock interrupts (and thus task switching) for a short time period, while on multi-cpu, it is planned that they will additionnally do a busy-waiting loop on some memory value. This implies that system locks must be used with care and only for very short amount of time ...


This being said, let's see what kind of conflict we want to avoid ...

Current request modification

The controller has a "current request" field that no other code but the interrupt handler may change. This guarantee us that we can always handle an interrupt regardless of what the schedulers are doing once the "current request" has been issued.

The only operation that modifies the "current request" consist of picking the head of the pending list and setting it as the new "current" request. A system lock is used to make sure noone else will try to access the pending list during this time.

Modifying the request queue

Unlike picking the list head, modifying the request queue may be a long operation, especially when a complex policy is in place (i.e. we have to sweep the list to find where to add the new request to minimize some metric). It wouldn't be nice to lock interrupts during that time interval, and we can't use a semaphore either, because the interrupt handler that will try to read the queue may not sleep.

The technique used here consist of stealing the list to the controller: for the duration of the operation, the queue will be replaced by an empty list (the replacement's atomicity is guaranteed by the same system lock as the one used for reading). Once the insertion has been performed by the queue scheduler, the whole list is restored to the controller.

If the scheduler detects that the controller entered the "idle" state during the operation (that is, the current request is now null), it will also promote the head of the list as the new current request and issue it. There's no risk that this operation cause any kind of trouble as there's no longer pending interrupts at this point (no operation is being held).

Concurrent updates of the request queue

So far, we only made sure that the interrupt handlerof the ataController will not attemp to read the request queue while being modified, but we also need an additionnal mechanism to make sure there will not be several attempt to update the queue by different queueSchedulers. This is achieved by adding a semaphore that will control mutual access to the request list as a writer.

In the absence of this semaphore, the following nightmare could occur:

operator component	operation	ending state
QS1	steal the controller's queue for an update	current!=NULL pending==NULL
QS2	try to add a new request. No need to steal an empty queue.	current!=NULL pending=={rq}
QS1	restores the modified queue. {rq} is lost.

so we clearly see we need that semaphore to prevent the queue from being "stolen" twice. As the queue modification between a steal and a restore may be long and as the queue scheduler do not operate at interrupt-handling priority, we can safely use a semaphore for these two (or more) components.

Note that it's a common technique to use two distinct synchronizator objects for reading and writing access to a resource. What is a bit special here is the asymetry between the two synchronizators used.

typedef struct ioDiskList {   ioDiskRequest *head;   ioDiskRequest *tail;   kMutex lock;   kSemaphore *write;   ioDiskRequest *request; } ioDiskList; typedef struct ioDiskRequest {   struct ioDiskRequest *next;   struct ioDiskRequest *prev; ... } ioDiskRequest; typedef struct ioAtaController {   ioDiskList pending; ... };	a list of IO requests, as the disk queue scheduler can use it. the "lock" mutex is used to prevent the controller to access the list while a scheduler is actually accessing it. In addition, we have a semaphore that provides mutual exclusion between schedulers in the case of a shared controller. list.request is the current processed request.
ioDiskRequest *ioDiskListGet(ioDiskList *list) {   kSysLock(&list->lock);   if (( list->request=list->head )) {     if (list->head==list->tail) list->tail=NULL;     list->head=list->head->next;   }   kSysUnlock(&list->lock);   return list->request; }	get the first request of the list. We just use the "list lock" mutex.
ioDiskRequest *ioDiskListSteal(ioDiskList *list, ioDiskRequest **tail) {   ioDiskRequest *res=NULL;   ksemWait(list->write);   kSysLock(&list->lock);     res=list->head;   if (tail) *tail=list->tail;   list->head=NULL;   list->tail=NULL;   kSysUnlock(&list->lock);   return res; }	leaves an empty list on the controller while updating it. You need to "restore" the list later because any attemp to steal it again will be blocked. Note that the "sysLock" occurs *after* the semWait, so that we're not waiting for a semaphore in a sysLock region.
ioDiskRequest *ioDiskListRestore(ioDiskList *list, ioDiskRequest *head,                  ioDiskRequest *tail) {   void* current;   kSysLock(&list->lock);   list->head=head;   list->tail=tail;   current=list->request;   kSysUnlock(&list->lock);   if (!current) {     while (ioDiskListGet(list)) {       if (list->request->issue && list->request->issue(list, list->request))     break;     }   }   ksemSignal(list->write); }	restore the modified list. in the case of an idle controller at the time of the restore, the newly installed list is read and the new "current" request is issued. Note that because list->request is modified within the "syslock" region of Get(), we don't fear concurrent issue of several requests. Moreover, the controller is expected to be idle and therefore it will *not* interfere.