Operating Systems 2018F Lecture 19: Difference between revisions

From Soma-notes
 
(3 intermediate revisions by one other user not shown)
Line 4: Line 4:


==Notes==
==Notes==
Linux source code links:
* [https://elixir.bootlin.com/linux/v4.19.2/source/fs/read_write.c#L107 use of spin_lock() and spin_unlock()]
* [https://elixir.bootlin.com/linux/v4.19.2/source/include/linux/fs.h#L895 spinlock declaration]
* [https://elixir.bootlin.com/linux/v4.19.2/source/include/linux/spinlock.h#L321 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 ==
#What happens when more than one process is trying to write to dev/remember at same time?
#*Get race condition
#*Race condition located in <code>remember_write()</code>
#*Condition is basically the whole function
#*Conflict in <code>free_saved_data()</code>, <code>init_saved_date()</code>, and when writing to it.
#**Examples: freeing twice, first time will work but will try to free pages again, but nothing to free
#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
#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 <code>remember</code> 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 <code>remember_init()</code>
#*Move deallocation into the <code>remember_exit()</code> (when kernel module unloaded)
#*Can still have problems, but avoids crashing!
#*From here we can then add locking mechanisms
#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
#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 <code>spinlock_t</code> & <code>rw_semaphore</code>
## <code>spinlock.h</code>
#*What does it do?
#*Similar to loop structure from '''Test 1'''
#*Creates a do-while loop to lock
#*A bunch of implementations, <code>spinlock_up.h</code>
## Question: How do normal files handle locking?
#*Checks in <code>Fs.h<code> for struct inode
#*Uses <code>spin_lock</code>
#Concurrent Remember Module
#*First: move allocation & deallocation to <code>remember_init()</code> & <code>remember_exit()</code>
#*Add: <code>static spinlock_t saved_data_lock</code> to initialized structures (line 41)
#*In <code>init_saved_data()</code>, add initialization of spinlock
#** <code>spin_lock_init(&saved_data_lock);</code> (line 94)
#*In <code>remember_write()</code>, add lock & unlock
#**<code>spin_lock(&saved_data_lock)</code> (line 131)
#**<code>spin_unlock(&saved_data_lock)</code> (line 134)
##Do we need lock around read as well?
#*Yes, otherwise inconsistent data if someone reading while writing
#*In <code>remember_read()</code>
#**<code>spin_lock(&saved_data_lock)</code> (line 74)
#**<code>spin_unlock(&saved_data_lock)</code> (line 77)
##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, <code>make</code> & then loads modules into kernel
#*Test 1: <code>echo “hello there” > /dev/remember </code>
#**<code>cat dev/remember</code> 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 ==
#Version 1
#*Opens file, writes first argument from command line to file, seeks back to beginning, then loops
#*Need <code>seek</code> 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
#Version 2
#*Adds a new line char to end of <code>dev/remember</code>
#*Works
#Final Version
#*Counter <code>i</code> (line 21)
#**Used because otherwise printing out the same thing every time, no way of knowing if actually working properly
#ERROR: Filled up log file
#*Clean out journal log
#**<code>sudo journalctl --flush --rotate</code>
#**<code>sudo journalctl --vacuum-size=1M</code>
#Remember-WriteTest on Remember Module
#*Run 3 processes in background
#* <code>./remember-writetest p1 &</code>
#**works
#* <code>./remember-writetest p2 &</code>
#**get segmentation fault
#* <code>./remember-writetest p3 &</code>
#**process 1 killed
#*<code>cat /dev/remember<code>
#** works
#*So kernel not crashing, but still getting errors
#*Locking successful


==Code==
==Code==
'''[https://homeostasis.scs.carleton.ca/~soma/os-2018f/code/lec19/remember-concurrent.zip Download remember-concurrent.zip]'''


===remember.c (concurrent version)===
===remember.c (concurrent version)===

Latest revision as of 08:50, 23 November 2018

Video

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

Notes

Linux source code links:

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. 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. 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. 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. 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;
}