Operating Systems 2018F Lecture 19

Video

Video for the lecture given on November 16, 2018 is now available.

Notes

Linux source code links:

• use of spin_lock() and spin_unlock()
• spinlock declaration
• spinlock init

Question re Pages for Assignment

• Pages are virtual
• Put into a frame which is physical memory
• when allocating memory: allocating frames & putting pages into these frames
• Page is a chunk of process memory

Remember Module from Tutorial 7

1. What happens when more than one process is trying to write to dev/remember at same time?
   • Get race condition
   • Race condition located in remember_write()
   • Condition is basically the whole function
   • Conflict in free_saved_data(), init_saved_date(), and when writing to it.
     • Examples: freeing twice, first time will work but will try to free pages again, but nothing to free

1. How can we fix in order to allow for concurrency?
   • One solution: add locking mechanism, mutual exclusion to access data structures (lines 35-39 need to be locked)
   • Using sleep not a good idea

1. Simplest Solution: Prevent Crashing Kernel
   • Real problem for kernel crashing is freeing and allocating memory
   • Can’t use mmap, which is user-space command, in the kernel
   • Why does remember allocate data on every write?
     • Every time freeing memory, then initializing new, but its the same size
     • Why throw away? Just erase it, or replace with zeros
   • So, move allocation into remember_init()
   • Move deallocation into the remember_exit() (when kernel module unloaded)
   • Can still have problems, but avoids crashing!
   • From here we can then add locking mechanisms

1. Another Solution: Exclusivity
   • Make it exclusive
   • Only have concurrency problems with shared data
   • Make data exclusive to a process, or a user, etc.
   • If can avoid locks, should, because they can cause problems
   • Locks are error prone

1. Locks in Kernel Space
   • We have to rely on kernel based mechanism, can't rely on man page
   • There is Documentation online for kernel locking mechanism, but be careful, some info outdated
   • Multiple kinds of locking, can’t just search lock in source code for "lock" because accessing primitive info
   • Need an example to follow & base code on
   • INODE uses spinlock_t & rw_semaphore

1. 1. spinlock.h
   • What does it do?
   • Similar to loop structure from Test 1
   • Creates a do-while loop to lock
   • A bunch of implementations, spinlock_up.h

1. 1. Question: How do normal files handle locking?
   • Checks in Fs.h for struct inode
   • Uses spin_lock

1. Concurrent Remember Module
   • First: move allocation & deallocation to remember_init() & remember_exit()
   • Add: static spinlock_t saved_data_lock to initialized structures (line 41)
   • In init_saved_data(), add initialization of spinlock
     • spin_lock_init(&saved_data_lock); (line 94)
   • In remember_write(), add lock & unlock
     • spin_lock(&saved_data_lock) (line 131)
     • spin_unlock(&saved_data_lock) (line 134)

1. 1. Do we need lock around read as well?
   • Yes, otherwise inconsistent data if someone reading while writing
   • In remember_read()
     • spin_lock(&saved_data_lock) (line 74)
     • spin_unlock(&saved_data_lock) (line 77)

1. 1. Now build module, but not load directly on device
   • Will it compile? It did!
   • Now test in SSH/VM
     • Uses rsync to copy file to vm, make & then loads modules into kernel
   • Test 1: echo “hello there” > /dev/remember
     • cat dev/remember Works properly, & prints out hello there
   • But we need to test concurrency
   • How?
     • Make child-parent program that just keeps writing with whatever is writen to the command line
     • From command line just keep adding & check with what have
     • Not a definitive test, but passible

Remember Write Test

1. Version 1
   • Opens file, writes first argument from command line to file, seeks back to beginning, then loops
   • Need seek to reset offset back to beginning, otherwise would keep writing same thing instead of writing over
   • Works, but printing result and new command line on same line

1. Version 2
   • Adds a new line char to end of dev/remember
   • Works

1. Final Version
   • Counter i (line 21)
     • Used because otherwise printing out the same thing every time, no way of knowing if actually working properly

1. ERROR: Filled up log file
   • Clean out journal log
     • sudo journalctl --flush --rotate
     • sudo journalctl --vacuum-size=1M

1. Remember-WriteTest on Remember Module
   • Run 3 processes in background
   • ./remember-writetest p1 &
     • works
   • ./remember-writetest p2 &
     • get segmentation fault
   • ./remember-writetest p3 &
     • process 1 killed
   • cat /dev/remember
     • works
   • So kernel not crashing, but still getting errors
   • Locking successful

Code

Download remember-concurrent.zip

remember.c (concurrent version)

/* 
  remember.c

  remember module COMP 3000, Carleton University
  remembers what is written to it, returns in when read along with
  info about how it is stored

  License: GPLv2 or later
  Author: Anil Somayaji
  November 3, 2018

  device driver and module code derived from:
  https://appusajeev.wordpress.com/2011/06/18/writing-a-linux-character-device-driver/
  and
  http://pete.akeo.ie/2011/08/writing-linux-device-driver-for-kernels.html
*/

#include <linux/module.h>
#include <linux/string.h>
#include <linux/fs.h>
#include <linux/device.h>
#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/sched.h>
#include <linux/uaccess.h>
#include <linux/mm.h>

#define DEVICE_NAME "remember"
#define CLASS_NAME "comp3000"

static struct class* remember_class = NULL;
static struct device* remember_device = NULL;
static int remember_major;

static struct page *saved_data_page = NULL;
static char *saved_data = NULL;
static unsigned long saved_data_len = 0;
static int saved_data_max = PAGE_SIZE;
static int saved_data_order = 0;

static spinlock_t saved_data_lock;

static int remember_open(struct inode *the_inode, struct file *f)
{
        pr_info("Remember: device opened\n");
        return 0;
}

static ssize_t remember_read(struct file *f, char *buf, size_t len, loff_t *offset)
{
        unsigned long n;
        char *error_msg = "Buffer too small.";
        
        pr_info("Remember: read started\n");
        
        if (*offset > 0) {
                pr_info("Remember: read non-zero offset, aborting\n");
                return 0;
        }

        if (len < saved_data_len) {
                pr_info("Remember: read short buffer\n");
                n = strlen(error_msg) + 1;  // Include terminating null byte
                if (n > len) {
                        n = len;
                }
                copy_to_user(buf, error_msg, n);
                
                return n;
        } else {
                pr_info("Remember: read returning data, %ld bytes\n",
                        saved_data_len);
                
                spin_lock(&saved_data_lock);
                copy_to_user(buf, saved_data, saved_data_len);
                *offset = saved_data_len;
                spin_unlock(&saved_data_lock);

                return saved_data_len;
        }
}

void init_saved_data(void)
{
        pr_info("Remember: allocating data page");

        if (saved_data) {
                pr_err("Remember: saved_data already initialized!");
        } else {       
                saved_data_page = alloc_pages(GFP_KERNEL,
                                              saved_data_order);
                saved_data = (char *) page_address(saved_data_page);
                saved_data_len = 0;
                spin_lock_init(&saved_data_lock);

                pr_info("saved_data at kernel virtual address %lx",
                        (unsigned long) saved_data);
                pr_info("saved_data_page page struct at address %lx",
                        (unsigned long) saved_data_page);
        }
}

void free_saved_data(void)
{
        if (saved_data_page) {
                pr_info("Remember: freeing old data page");
                __free_pages(saved_data_page, saved_data_order);
                saved_data_page = NULL;
                saved_data = NULL;
                saved_data_len = 0;
        }
}

static ssize_t remember_write(struct file *f, const char *buf, size_t len,
                           loff_t *offset)
{
        unsigned long result;

        if (*offset > 0) {
                pr_info("Remember: write nonzero offset, aborting");

                return 0;
        }
                
        if (len > saved_data_max) {
                len = saved_data_max;
        }
        
        pr_info("Remember: write saving data, %ld bytes", len);

        spin_lock(&saved_data_lock);
        result = copy_from_user(saved_data, buf, len);
        saved_data_len = len;
        spin_unlock(&saved_data_lock);

        *offset = len;
        
        return len;
}

static int remember_release(struct inode *the_inode, struct file *f)
{        
        pr_info("Remember: device closed\n");
        return 0;
}


static struct file_operations remember_fops = {
        .open = remember_open,
        .read = remember_read,
        .write = remember_write,
        .release = remember_release,
};


static char *remember_devnode(struct device *dev, umode_t *mode)
{
        if (mode)
                *mode = 0666;
        return NULL;
}

static int __init remember_init(void)
{
        int retval;
  
        remember_major = register_chrdev(0, DEVICE_NAME, &remember_fops);
        if (remember_major < 0) {
                pr_err("failed to register device: error %d\n", remember_major);
                retval = remember_major;
                goto failed_chrdevreg;
        }
 
        remember_class = class_create(THIS_MODULE, CLASS_NAME);
        if (IS_ERR(remember_class)) {
                pr_err("Remember: failed to register device class '%s'\n",
                       CLASS_NAME);
                retval = PTR_ERR(remember_class);
                goto failed_classreg;
        }
 
        remember_class->devnode = remember_devnode;

        remember_device = device_create(remember_class, NULL,
                                        MKDEV(remember_major, 0),
                                        NULL, DEVICE_NAME);

        if (IS_ERR(remember_device)) {
                pr_err("Remember: failed to create device '%s'\n", DEVICE_NAME);
                retval = PTR_ERR(remember_device);
                goto failed_devreg;
        }

        init_saved_data();
        
        pr_info("Remember: device registered using major %d.\n",
                remember_major);
        
        return 0;
        
 failed_devreg:
        class_unregister(remember_class);
        class_destroy(remember_class);
 failed_classreg:
        unregister_chrdev(remember_major, DEVICE_NAME);
 failed_chrdevreg:
        return -1;
}

static void __exit remember_exit(void)
{
        free_saved_data();

        device_destroy(remember_class, MKDEV(remember_major, 0));
        class_unregister(remember_class);
        class_destroy(remember_class);
        unregister_chrdev(remember_major, "remember");
        pr_info("Unloading Remember module.\n");
        return;
}

module_init(remember_init);
module_exit(remember_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Anil Somayaji <soma@scs.carleton.ca>");
MODULE_DESCRIPTION("A remember character device module");

remember-writetest.c

#include <unistd.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>

#define BUFSIZE 8192

int main(int argc, char *argv[])
{
        int fd, result, count;
        int i = 0;
        char buf[BUFSIZE];
        
        while(1) {
                count = snprintf(buf, BUFSIZE, "%s: %d\n", argv[1], i);
                fd = open("/dev/remember", O_WRONLY);
                result = write(fd, buf, count);
                close(fd);
                i++;
        }

        /* will never run */
        return 0;
}