BE ENGINEERING INSIGHTS: Device Driver Idioms
By Dominic Giampaolo -

Every language, whether human or computer, has "idioms"; that is, a common way of expressing a concept or thought. In American English, the phrase "thanks a million" is a convenient way to express great thanks for something. In the C programming language, the idiom

  for(ptr=head; ptr; ptr=ptr>next) 
    ...

is a common way to iterate through a linked list. Cognizant listeners or readers easily recognize both of these idioms. The nice thing about idioms is that they don't require parsing the individual bits to recognize the meaning of the whole. Idioms are a type of shorthand that efficiently communicates an idea.

In writing device drivers one finds several common "idioms" for achieving a particular result. In this article I'd like to cover some common device driver idioms that BeOS device driver writers should know about. These idioms are a bit more complex than phrases like "thanks a million" but are still simple to recognize. This list is not exhaustive, but it should cover the more common idiomatic expressions in driverspeak (a language littered with hex constants, acronyms, bits, shifts, and bytes).

Starting Up

The first problem most device driver writers have is that they often want only one person to be able to open their device at a time. I've often seen the following code used to accomplish this:

  static long open_count = 0; 

  driver_open(const char *name, uint32 flags, void **cookie) 
  { 

    open_count++; 
    if (open_count > 1) 
      return EBUSY; 

    ... 
  }

That is the code equivalent of an English speaker saying "what can I do you for." It's just plain wrong. In this case the increment of open_count is not atomic (in a multiprocessor environment an increment of open_count could be lost) and the count is not decremented in the event that the open_count is greater than 1.

In proper driverspeak, the way to prevent multiple opens of a driver is this:

  static int open_count = 0; 

  driver_open(const char *name, uint32 flags, void **cookie) 
  { 
    if (atomic_add(&open_count, 1) > 0) { 
      atomic_add(&open_count, -1); 
      return EBUSY; 
    } 

    ... 
  }

The use of atomic_add() guarantees that open_count is indeed atomically updated. The return value of atomic_add is the previous value of open_count, which allows us to check whether we are the first person to increment open_count. If the "if" test succeeds we are not the first person to open the driver, so we have to decrement open_count to put it back to what it was before and return EBUSY.

This idiom extends to allow a maximum number of open()'s as well. Changing the "if" test to

    #define MAX_OPEN 4 

    if (atomic_add(&open_count, 1) >= MAX_OPEN)

allows only MAX_OPEN number of open calls to succeed.

Waiting for an Event

When a driver performs an I/O operation it usually must wait for that operation to complete. The obvious synchronization method is to use a semaphore. Normally a semaphore is created with a count of 1, which means that a call to acquire_sem() will acquire the semaphore and return immediately. A device driver, however, wants the acquire_sem() to block until an event happens. To accomplish this, we create the semaphore with a count of zero. Then in the device interrupt handler, we release the semaphore to unblock the I/O request. In code that looks something like this:

  /* in a driver initialization function */ 
  io_done_sem = create_sem(0, "device interrupt sem"); 


  /* in a driver I/O routine */ 
  ... set up an I/O operation that will 
      complete with an interrupt .... 
  ret = acquire_sem_etc(io_done_sem, 1, B_CAN_INTERRUPT, 0); 
  if (ret != B_OK) { 
    ... the I/O request did not complete successfully ... 
  } 


  /* in the interrupt handler, release the thread 
     blocked waiting */ 
  release_sem_etc(io_done_sem, 1, B_DO_NOT_RESCHEDULE);

The key parts here are that the driver I/O routine will initiate an I/O operation and then immediately block on the io_done_sem until the device interrupts and the driver interrupt handler is called. When the interrupt occurs and the kernel calls the driver interrupt handler, it will release the semaphore, unblocking the thread that requested the I/O. At the end of the sequence of events the semaphore is left again with a count of zero and the next I/O request will block as expected.

The idiom in this example is the use of semaphores to block until an interrupt occurs. This is different from typical application (sneef) level use of semaphores, because we create the semaphore in a way that will block on our first acquisition of the semaphore instead of immediately acquiring it.

More Initialization

We can combine the idiomatic use of atomic_add() in the first example with the second example to show how to initialize part of a driver once (and only once). Normally, one-time initialization is done in routines like init_hardware() or init_driver() that the kernel guarantees to be single-threaded. Sometimes, however, that is not possible. If the driver allows multiple open()'s, then we need a mechanism to insure that initialization only happens once and that any other threads doing an open at the same time will block until initialization is complete.

The resulting idiom is a blend of the previous two idioms. It only depends on the init_driver() routine creating a semaphore with a count of zero. In code, the whole idiom is

  static long  init_count = 0; 
  static sem_id init_sem = -1; 


  /* in init_driver() */ 
  init_sem = create_sem(0, "init sem"); 


  /* in driver_open() */ 
  if (atomic_add(&init_count, 1) == 0) { 

    /* do the initialization */ 

    delete_sem(init_sem); 
  } else { 
    atomic_add(&init_count, -1); 

    /* now wait for the init sem */ 
    acquire_sem(init_sem); 
  }

This idiom is somewhat less common, but is necessary for some drivers. An alternative form (a dialect if you will) addresses the case in which it's not possible to first create the init_sem semaphore. This case is slightly more complex:

  static     long init_count = 0; 
  static volatile int init_done = 0; 

  /* in driver_open() */ 
  if (atomic_add(&init_count, 1) == 0) { 

    /* do the initialization */ 

    init_done = 1; 

  } else { 
    atomic_add(&init_count, -1); 

    /* now wait for the init sem */ 
    while(init_done == 0) 
      snooze(5000); 
  }

This form will loop while waiting for the variable init_done to be set. The snooze() call will prevent the looping thread from consuming too much CPU time.

Observant readers may ask why no protection is needed around the manipulation of the variable init_done. The answer is that the thread that performs the initialization is the only one to store to the variable and the other threads only ever read the variable. Hence, there is no race condition for who will update the init_done variable. A store to a variable is an atomic operation and if only one thread is storing and other threads are reading, there is no race condition.

Spinlocks

As the dreadnaught of synchronization primitives, the spinlock is a powerful and dangerous tool. And built around this sultan of synchronization primitives is an idiom that carries the strength of four-letter epithets in the English language.

Just like colloquial expressions involving expletives, spinlocks are not appropriate for all situations. The most obvious example of appropriate use of a spinlock is when an interrupt handler and regular driver code must both perform read-modify-write operations on the registers of a device. A spinlock is necessary in this case because in a multiprocessor environment a thread may execute an I/O operation on one CPU, while a different CPU handles an interrupt from the device.

The first question to ask is -- why not use a semaphore? The answer is simple: in the BeOS an interrupt handler cannot acquire a semaphore. Acquiring a semaphore can cause the calling code to block. An interrupt handler executes with interrupts disabled and, therefore, cannot block. Not to mention the fact that if an interrupt handler blocked, other devices that share the same interrupt would not be serviced for a very long time.

Now that we're convinced that there is a reason and our device requires the use of a semaphore to protect access to its registers, what is the proper idiom in driverspeak?

In the regular (top-half) of the driver, the following code works:

  cpu_status ps; 
  spinlock hwlock = 0; 

  ps = disable_interrupts(); 
  acquire_spinlock(&hwlock); 

    ... play with hw registers ... 

  release_spinlock(&hwlock); 
  restore_interrupts(ps);

The interrupt handler calls acquire_spinlock() directly, and may omit the calls to disable_interrupts() and restore_interrupts() because it already executes with interrupts disabled.

For code not executed in an interrupt handler, the calls to disable_interrupts and restore_interrupts are required for correct use of spinlocks. If interrupts were not disabled before acquiring the spinlock, the system could deadlock if the spinlock were held and an interrupt occurred that needed to lock the same spinlock. Consider it an absolute rule that whenever a driver wants to acquire a spinlock, it must first disable interrupts (and likewise, it must restore interrupts after it releases the spinlock).

The above idiomatic use of spinlocks is often wrapped in two functions that encapsulate the pair of function calls:

  static cpu_status 
  lock_hw(spinlock *lock) 
  { 
    cpu_status ps; 

    ps = disable_interrupts (); 
    acquire_spinlock(lock); 
    return ps; 
  } 


  static void 
  unlock_hw(spinlock *lock, cpu_status ps) 
  { 
    release_spinlock(lock); 
    restore_interrupts (ps); 
  }

The spinlock idiom of disable_interrupts/acquire_spinlock is a safe way to guard access to hardware from an interrupt handler and regular driver code.

Of course, no discussion of spinlocks can go without the two main postulates of spinlock usage:

Not following those two rules can cause the behavior of the BeOS to deteriorate (the first rule) or lock up (the second rule).

The End: It's Time for the Fat Lady to Sing

This quick tour of idiomatic expressions in driverspeak should be enough to get you talking about and understanding the code in most device drivers. Other more complex (and subtle) idioms exist that involve producers and consumers, but we'll leave those for another article.

Copyright ©1999 Be, Inc. Be is a registered trademark, and BeOS, BeBox, BeWare, GeekPort, the Be logo and the BeOS logo are trademarks of Be, Inc. All other trademarks mentioned are the property of their respective owners.