Concurrent Access to Resources Driver Development

Concurrent access to resources

•       Concurrency arises because of

•       Interrupts, which interrupts the current thread to execute an interrupt handler. They may be using shared resources.

•       Kernel pre-emption, if enabled, causes the kernel to switch from the execution of one system call to another. They may be using shared resources.

•       Multiprocessing, in which case code is really executed in parallel on different processors, and they may be using shared resources as well.

•       The solution is to keep as much local state as possible and for the shared resources, use locking.

•       In terms of concurrency, the kernel has the same constraint has a multi-threaded program: all its state is global and visible in all executions contexts

Concurrency protection with locks

Linux mutexes

•       The main locking primitive since Linux 2.6.16.

•       The kernel used to have semaphores only, and mutexes have been introduced as a simplification of binary semaphores.

•       The process requesting the lock blocks when the lock is already held. Mutexes can therefore only be used in contexts where sleeping is allowed.

•       Mutex definition:

#include <linux/mutex.h>

•       Initializing a mutex statically:

•       DEFINE_MUTEX(name);

•       Or initializing a mutex dynamically:

•       void mutex_init(struct mutex *lock);

Locking and unlocking mutexes

•       void mutex_lock(struct mutex *lock);

–      Tries to lock the mutex, sleeps otherwise.

–      Caution: can't be interrupted, resulting in processes you cannot kill!

•       int mutex_lock_killable(struct mutex *lock);

–      Same, but can be interrupted by a fatal (SIGKILL) signal. If interrupted, returns a non zero value and doesn't hold the lock. Test the return value!!!

•       int mutex_lock_interruptible(struct mutex *lock);

–      Same, but can be interrupted by any signal.

•       int mutex_trylock(struct mutex *lock);

–      Never waits. Returns a non zero value if the mutex is not available.

•       int mutex_is_locked(struct mutex *lock);

–      Just tells whether the mutex is locked or not.

•       void mutex_unlock(struct mutex *lock);

–      Releases the lock. Do it as soon as you leave the critical section.

Spinlocks

•       Locks to be used for code that is not allowed to sleep (interrupt handlers), or that doesn't want to sleep (critical sections). Be very careful not to call functions which can sleep!

•       Originally intended for multiprocessor systems

•       Spinlocks never sleep and keep spinning in a loop until the lock is available.

•       Spinlocks cause kernel preemption to be disabled on the CPU executing them.

•       The critical section protected by a spinlock is not allowed to sleep.

•       Initializing spinlocks

•       static

•       DEFINE_SPINLOCK (my_lock);

•       Dynamic

•       void spin_lock_init (spinlock_t *lock);

•       Several variants, depending on where the spinlock is called:

•       void spin_[un]lock(spinlock_t *lock);

•       Doesn't disable interrupts. Used for locking in process context (critical sections in  which you do not want to sleep).

•       void spin_lock_irqsave / spin_unlock_irqrestore (spinlock_t *lock, unsigned long flags);

•       Disables / restores IRQs on the local CPU. Typically used when the lock can be accessed in both process and interrupt context, to prevent preemption by interrupts.

•       void spin_[un]lock_bh(spinlock_t *lock);

•       Disables software interrupts, but not hardware ones. Useful to protect shared data accessed in process context and in a soft interrupt (“bottom half”). No need to disable hardware interrupts in this case.

•       Note that reader / writer spinlocks also exist.

Deadlock situations

•       They can lock up your system. Make sure they never happen.

•       Don’t call a function that can try to access the same lock

•       Hold multiple locks.

•       Mixing order of locks while acquiring.

Atomic variables

•       Useful when the shared resource is an integer value

•       Even an instruction like n++ is not guaranteed to be atomic on all processors!

•       Header

–      #include <asm/atomic.h>

•       Type

–      atomic_t

–      contains a signed integer (at least 24 bits)

•       Atomic operations (main ones)

•       Set or read the counter:

–      atomic_set(atomic_t *v, int i);

–      int atomic_read(atomic_t *v);

•       Operations without return value:

–      void atomic_inc(atomic_t *v);

–      void atomic_dec(atomic_t *v);

–      void atomic_add(int i, atomic_t *v);

–      void atomic_sub(int i, atomic_t *v);

•       Similar functions testing the result:

–      int atomic_inc_and_test(...);

–      int atomic_dec_and_test(...);

–      int atomic_sub_and_test(...);

•       Functions returning the new value:

–      int atomic_inc_and_return(...);

–      int atomic_dec_and_return(...);

–      int atomic_add_and_return(...);

–      int atomic_sub_and_return(...);

Atomic bit operations

•       Supply very fast, atomic operations

•       On most platforms, apply to an unsigned long type.

•       Apply to a void type on a few others.

•       Set, clear, toggle a given bit:

•       void set_bit(int nr, unsigned long * addr);

•       void clear_bit(int nr, unsigned long * addr);

•       Test bit value:

•       int test_bit(int nr, unsigned long *addr);

•       Test and modify (return the previous value):

•       int test_and_set_bit(...);

•       int test_and_clear_bit(...);

•       int test_and_change_bit(...);

Sleep Driver development

•       Execution of a system call

•       Sleeping

•       Waking up

•       Example

Blocking I/O

•       In previous session we looked at how to implement the read and write driver methods.

•       At that point, however, we skipped over one important issue: how does a driver respond if it cannot immediately satisfy the request?

•       A call to read may come when no data is available, but more is expected in the future. Or a process could attempt to write, but your device is not ready to accept the data, because your output buffer is full. The calling process usually does not care about such issues; the programmer simply expects to call read or write and have the call return after the necessary work has been done.

•       So, in such cases, your driver should (by default) block the process, putting it to sleep until the request can proceed.

•       This section shows how to put a process to sleep and wake it up again later on.

•       Lest look at a few concepts first.

Introduction to sleeping

•       What does it mean for a process to “sleep”? When a process is put to sleep, it is marked as being in a special state and removed from the scheduler’s run queue. Until something comes along to change that state, the process will not be scheduled on any CPU and, therefore, will not run.

Rules

•       A couple of rules that you must keep in mind to be able to code sleeps in a safe manner.

•       The first of these rules is: never sleep when you are running in an atomic context.

•       An Atomic context is simply a state where multiple steps must be performed without any sort of concurrent access.

•       It means your driver cannot sleep while holding a spinlock, seqlock, or RCU lock.

•       Another thing to remember with sleeping is that, when you wake up, you never know how long your process may have been out of the CPU or what may have changed in the mean time. You also do not usually know if another process may have been sleeping for the same event; that process may wake before you and grab whatever resource you were waiting for. The end result is that you can make no assumptions about the state of the system after you wake up, and you must check to ensure that the condition you were waiting for is, indeed, true.

•       Another point is that your process cannot sleep unless it is assured that somebody else, somewhere, will wake it up.

How to sleep

•       Linux kernel uses data structure called “wait queues” to accomplish process sleeping.

•       A wait queue is a list of processes waiting for a specific event to occur.

•       In Linux, a wait queue is managed by means of a “wait queue head,” a structure of type wait_queue_head_t, which is defined in <linux/wait.h>. A wait queue head can be defined and initialized

•       Statically (useful to declare as global variable)

–      DECLARE_WAIT_QUEUE_HEAD(name);

•       Dynamically (useful to embed wait queue inside another data structure)

–      wait_queue_head_t my_queue;

–      init_waitqueue_head(&my_queue);

•       A process sleeps with an expectation that some condition will become true in the future

•       Several ways to make a kernel process sleep

•       wait_event(queue, condition);

–      Sleeps until the task is woken up and the given C expression is true.

–      Caution: can't be interrupted (can't kill the user-space process!)

•       int wait_event_interruptible(queue, condition);

–      Can be interrupted by any signal. Returns -ERESTARTSYS if interrupted.

•       int wait_event_timeout(queue, condition, timeout);

–      Wait for limited time(expressed in jiffies); after that time period expires, the macro returns with the value of “0” regardless of how condition evaluates. Reurns non-zero if the condition was met.

•       int wait_event_interruptible_timeout(queue, condition,

•       timeout);

–      Same as above, interruptible. Returns 0 if the timeout elapsed, -ERESTARTSYS if interrupted, positive value if the condition was met.

•       “Condition” is arbitary boolean expression that is evaluated. Until condition is evaluated to a true value, the process continues to sleep.

Waking up

•       Typically the processes are woken up by some other thread of execution (a different process, or an interrupt handler)

•       wake_up(&queue);

–      Wakes up all processes in the wait queue

•       wake_up_interruptible(&queue);

–      Wakes up all processes waiting in an interruptible sleep on the given queue

Example

•       Process sleep in read() for data to become availabe

static ssize_t sample_char_read(struct file * file, char __user * buf,

                       size_t count, loff_t *ppos)

{

        wait_event_interruptible(queue, flag);

        printk("sample_char_read size(%ld)\n", count);

        return 0;

}

•       Write() wakes up the sleeping process

static ssize_t sample_char_write(struct file *filp, const char *buf,

                 size_t size, loff_t *offp)

{

        flag = 1;

        wake_up_interruptible(&queue);

        printk("sample_char_write size(%ld)\n", size);

        return size;

}

Quick Reference

•       #include <linux/wait.h>

•       typedef struct { /* ... */ } wait_queue_head_t;

•       void init_waitqueue_head(wait_queue_head_t *queue);

•       DECLARE_WAIT_QUEUE_HEAD(queue);

–      he defined type for Linux wait queues. A wait_queue_head_t must be explicitly initialized with either init_waitqueue_head at runtime or DECLARE_WAIT_ QUEUE_HEAD at compile time.

•       void wait_event(wait_queue_head_t q, int condition);

•       int wait_event_interruptible(wait_queue_head_t q, int condition);

•       int wait_event_timeout(wait_queue_head_t q, int condition, int time);

•       int  wait_event_interruptible_timeout(wait_queue_head_t q, int condition, int time);

–      Cause the process to sleep on the given queue until the given condition evaluates to a true value.          

•       void wake_up(struct wait_queue **q);

•       void wake_up_interruptible(struct wait_queue **q);

–      Wake processes that are sleeping on the queue q. The _interruptible form wakes only interruptible processes.

•        #include <linux/sched.h>

•       set_current_state(int state);

•       Sets the execution state of the current process. TASK_RUNNING means it is ready to run, while the sleep states are TASK_INTERRUPTIBLE and  TASK_UNINTERRUPTIBLE.

•       Void schedule (void)

–      Selects a runnable process from the run queue. The chosen process can be current or a different one.

Character Device Driver

Device files

•       In Linux kernel, most of the devices are presented to the user space applications through two different abstractions

•       Character device

•       Block device

•       Internally the kernel identifies each device by a triplet  of information

•       Type (character or block)

•       Major number (typically the category of devices)

•       Minor number (typically the identifier of the device)

Types of devices

•       Block devices

–      A device composed of fixed-sized blocks, that can be read and write to store data.

–      Used for hard disks, SD cards etc.

•       Character devices

–      An infinite stream of bytes, with no beginning, no end, no size. For e.g. serial port.

–      Used for serial ports, terminals etc.

–      Most of the devices that are not block devices are represented by linux kernel as character device.

Devices: Everything is a file

•       A very important Unix design decision was to represent most of the “system objects” as “files”

•       It allows applications to manipulate all “system objects” with the normal file API (open, read, write, close, etc.)

•       So, devices had to be represented as “files” to the applications

•       This is done through a special artefact called a device file

•       It a special type of file, that associates a file name visible to user space applications to the triplet (type, major, minor) that the kernel understands All device files are by convention stored in the /dev directory

•       Device files examples

$ ls -l /dev/ttyS0 /dev/tty1 /dev/sda1

brw-rw---- 1 root disk    8,  1 2012-02-13 18:49 /dev/sda1

crw------- 1 root root    4,  1 2012-02-27 15:58 /dev/tty1

crw-rw---- 1 root dialout 4, 64 2012-02-13 18:49 /dev/ttyS0

Example C code that uses the usual file API to write data to a serial port

int fd;

fd = open(“/dev/ttyS0”, O_RDWR);

write(fd, “Hello”, 5);

close(fd);

Creating device files

•       On a basic Linux system, the device files have to be created

manually using the mknod command

•       mknod /dev/<device> [c|b] major minor

•       Needs root privileges

•        Coherency between device files and devices handled by the kernel is left to the system developer

•       On more elaborate Linux systems, mechanisms can be added to

create/remove them automatically when devices appear and

disappear

•        devtmpfs virtual filesystem, since kernel 2.6.32

•        udev daemon, solution used by desktop and server Linux systems

•        mdev program, a lighter solution than udev

Anatomy of device driver

•       A device driver has three sides

–      One side talks to the rest of the kernel

–      One talks to the hardware and

–      One talks to the user

Kernel interface to the device driver

•       In order to talk to the kernel, the driver registers with subsystems to respond to events. Such an event might be the opening of a file, closing a file, a page fault, the plugging in of a new USB device, etc.

Character drivers

•       User-space needs

–      The name of a device file in /dev to interact with the device driver through regular file operations (open, read,  write, close...)

•       The kernel needs

–      To know which driver is in charge of device files with a given major / minor number pair

For a given driver, to have handlers (“file operations”) to execute when user- space opens, reads, writes or closes the device file.

Implementing a character driver

•       Four major steps

•       Implement operations corresponding to the system calls an application can apply to a file: file operations.

•       Define a “file_operations” structure containing function pointers to system call functions in your driver.

•       Reserve a set of major and minors for your driver

•       Tell the kernel to associate the reserved major and minor to your file operations

•       This is a very common design scheme in the Linux kernel

•       A common kernel infrastructure defines a set of operations to be implemented by a driver and functions to register your driver

•       Your driver only needs to implement this set of well-defined operations

File operations

•       Before registering character devices, you have to define file_operations (called fops) for the device files.

•       The file_operations structure is generic to all files handled by the Linux kernel. It contains many operations that aren't needed for character drivers.

•       Here are the most important operations for a character driver. All of them are optional. (include/linux/fs.h)

struct file_operations {

ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);

ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *);

long (*unlocked_ioctl) (struct file *, unsigned int, unsigned long);

int (*mmap) (struct file *, struct vm_area_struct *);

int (*open) (struct inode *, struct file *);

int (*release) (struct inode *, struct file *);

[...]

};

•       open: for opening the device(allocating resources)

•       release: for closing the device (releasing resources)

•       write: for writing data to the device

•       read : for reading data from the device

•       ioctl: for query the device statistics and passing configuration parameters to device

•       mmap: for potentially faster but more complex direct access to the device

Open() and release()

•       int open(struct inode *i, struct file *f)

–      Called when user-space opens the device file.

–      inode is a structure that uniquely represent a file in the system (be it a regular file, a directory, a symbolic link, a character or block device)

–      file is a structure created every time a file is opened. Several file structures can point to the same inode structure.

•       Contains information like the current position, the opening mode, etc.

•       Has a void *private_data pointer that one can freely use.

•       A pointer to the file structure is passed to all other operations

–      The open method is provided by the driver to do any initialization in preparation to later operations such as allocating memory resources.

•       int release(struct inode *i, struct file *f)

–      Called when user-space closes the file.

–      The role of release is reverse of open(). It performs all the operation to undo the tasks done in open() such as de-allocating the memory resources allocated at time of open().

Read()

•       ssize_t read (struct file *file, __user char *buf, size_t sz, loff_t *off)

–      Called when user-space uses the read() system call on the device.

–      Must read data from the device, write at most sz bytes in the user-space buffer buf, and update the current position in the file off. “f ile “ is a pointer to the same file structure that was passed in the open() operation

–      Must return the number of bytes read.

–      On UNIX/Linux, read() operations typically block when there isn't enough data to read from the device

Write()

•       ssize_t foo_write(struct file *file, __user const char *buf, size_t sz ,loff_t *off)

–      Called when user-space uses the write() system call on the device

–      The opposite of read, must read at most sz bytes from buf, write it to the device, update off and return the number of bytes written.

ioctl

•       static long ioctl(struct file *file, unsigned int cmd,  unsigned long arg)

–      Associated with the ioctl system call.

–      Allows to extend drivers capabilities beyond read/write API.

–      For example: changing the speed of a serial port, setting video output format, querying a device serial number.

–      cmd is a number identifying the operation to perform

–      arg is the optional argument passed as third argument of the ioctl() system call. Can be an integer, an address, etc.

–      The semantic of cmd and arg is driver-specific.

Kernel representation of device numbers

•       The kernel data type dev_t represent a malor/ minor number pair

–      Also called a device number.

–      Defined in <linux/kdev_t.h>

Linux 2.6: 32 bit size (major: 12 bits, minor: 20 bits)

–      Macro to compose the device number:

MKDEV(int major, int minor);

–      Macro to extract the minor and major numbers:

MAJOR(dev_t dev);

MINOR(dev_t dev);

Registering device numbers

•       #include <linux/fs.h>

int register_chrdev_region(

                dev_t from,                        /* Starting device number */

                unsigned count,               /* Number of device numbers */

                const char *name);         /* Registered name */

Returns 0 if the allocation was successful.

•       If you don't have fixed device numbers assigned to your driver

–      Better not to choose arbitrary ones. There could be conflicts with other drivers.

–      The kernel API offers an alloc_chrdev_region function to have the kernel allocate free ones for you. You can find the allocated major number in /proc/devices.

Information of registered devices

•       Registered devices are visible in /proc/devices:

•       Character devices:

–        1 mem

–        4 /dev/vc/0

–        4 tty

–        4 ttyS

–        5 /dev/tty

–        5 /dev/console

–        5 /dev/ptmx

–        6 lp

•       Block devices:

–        1 ramdisk

–      259 blkext

–        7 loop

–        8 sd

–        9 md

–       11 sr

–       65 sd    

–       66 sd

Major  number Registered name

Character device registration

•       The kernel represents character drivers with a cdev structure

•       Declare this structure globally (within your module):

#include <linux/cdev.h>

static struct cdev char_cdev;

•       In the init function, initialize the structure

•       void cdev_init(struct cdev *cdev, struct file_operations *fops);

cdev_init(&char_cdev, &fops);

•       Then, now that your structure is ready, add it to the system:

int cdev_add(

                struct cdev *p,  /* Character device structure */

                dev_t dev,          /* Starting device major / minor number */

                unsigned count);              /* Number of devices */

If (cdev_add(&char_cdev, dev_no, device_count))

                printk(“Char device registration failed\n”);

•       After this function call, the kernel knows the association between

the major/minor numbers and the file operations. Your device is

ready to be used!.

Character device unregistration

•       First delete your character device:

void cdev_del(struct cdev *p);

•       Then, and only then, free the device number:

void unregister_chrdev_region(dev_t from, unsigned count);

•       Example :

cdev_del(&char_cdev);

unregister_chrdev_region(char_dev, count);

Exchanging data with user space

•       Kernel code isn't allowed to directly access user-space memory, using memcpy or direct pointer dereferencing

–      Doing so does not work on some architectures

–      If the address passed by the application was invalid, the application would segfault.

•       To keep the kernel code portable and have proper error handling, your driver must use special  kernel functions to exchange data with user-space.

•       A single value

–      get_user(v, p);

The kernel variable v gets the value pointed by the user-space pointer p

–      put_user(v, p);

The value pointed by the user-space pointer p is  set to the contents of the kernel variable v.

•       A buffer

–      unsigned long copy_to_user(void __user *to, const void *from, unsigned long n);

–      unsigned long copy_from_user(void *to, const void __user *from, unsigned long n);

•       The return value must be checked. Zero on success, non-zero on failure. If non-zero, the convention is to return -EFAULT.

Char driver example

•       Read operation example

–      Drivers/char/lp.c             

•       Ioctl operation example

–      drivers/char/lp.c

•       Write operation example

–      Drivers/char/lp.c

Linux error code

•       The kernel convention for error management is

•       Return 0 on success

•       return 0;

•       Return a negative error code on failure

•       return -EFAULT;

•       Error codes

•       include/asm-generic/errno-base.h

•       include/asm-generic/errno.h

General purpose kernel APIs

•       Memory/string utilities

•       In <linux/string.h>

–      Memory-related: memset, memcpy, memmove, memscan, memcmp, memchr

–      String-related: strcpy, strcat, strcmp, strchr, strrchr, strlen and variants

–      Allocate and copy a string:           kstrdup, kstrndup

–      Allocate and copy a memory area: kmemdup

•       In <linux/kernel.h>

–      String to int conversion: simple_strtoul, simple_strtol, simple_strtoull, simple_strtoll

•       Other string functions: sprintf, sscanf

•       Convenient linked-list facility in <linux/list.h>

–      Used in thousands of places in the kernel

•       Add a struct list_head member to the structure whose instances will be part of the linked list. It is usually named node when each instance needs to only be part of a single list.

•       Define the list with the LIST_HEAD macro for a global list, or define a struct list_head element and initialize it with INIT_LIST_HEAD for lists embedded in a structure.

•       Then use the list_*() API to manipulate the list

–      Add elements: list_add(), list_add_tail()

–      Remove, move or replace elements: list_del(), list_move(), list_move_tail(), list_replace()

–      Test the list: list_empty()

–      Iterate over the list: list_for_each_*() family of macros

Practical lab

•       Writing a simple character driver implementing the basic calls open, release, read, write

•       Write simple character driver implementing the 4 calls and ioctl call.

•       Write simple charater driver with open, release, read, write, ioctl with parameter passing passing.

•       Practicing with the character device driver API.

•       Exchanging data between user space and kernel space.

•       Using kernel standard error codes.

•       Using the general purpose APIs