Operating Systems 2019W: Assignment 3
Please submit the answers to the following questions via CULearn by 11:55 PM on Tuesday, March 26, 2019. There are 20 points in 9 questions.
Submit your answers as a single text file named "<username>-comp3000-assign3.txt" (where username is your MyCarletonOne username). The first four lines of this file should be "COMP 3000 Assignment 3", your name, student number, and the date of submission. You may wish to format your answers in Markdown to improve their appearance.
No other formats will be accepted. Submitting in another format will likely result in your assignment not being graded and you receiving no marks for this assignment. In particular do not submit an MS Word or OpenOffice file as your answers document!
Don't forget to include what outside resources you used to complete each of your answers, including other students, man pages, and web resources. You do not need to list help from the instructor, TA, or information found in the textbook.
Please make your best effort to do a proper implementation where required. There will be times where you may be tempted to copy large portions of code from other parts of the kernel. While you may have to copy a small number of lines, avoid duplicating significant functionality.
When an answer asks for modifications to the remember module, please give your code as a "diff -c" versus the original remember.c or versus the code for a previous answer. Points may be deducted for code in improper form. (Note that by using diff -c it is easily possible to automatically apply your changes to the original code in order to get a full working version.)
Questions
- [2] What are two reasons Linux kernel code doesn't make system calls?
- [2] What code could we use to get the information returned by getuid and geteuid system calls in the kernel? How do you know your code is correct?
- [2] When you unload a kernel module, can the kernel automatically deallocate the resources that were used by the module? Explain.
- [2] If you remove the remember module while a process is accessing it, what happens to the process? Please give your test program and appropriate output from ps. What happens if you try to reload the remember module?
- [2] What happens if you call class_create() in a module using a class name that already exists in the kernel? Describe the process by which you figured out your answer.
- [2] Fix the remember module so that it returns EFAULT to userspace when given an invalid pointer. Describe the process by which you figured out your answer.
- [2] In the remember module, modify remember_read() so it uses a non-zero offset properly rather than simply logging an error. Describe the process by which you figured out your answer.
- [2] Modify the remember module so llseek system calls work as they do on regular files, for whence values of SEEK_CUR and SEEK_SET. You should not allow the offset to be set to a value past the current end of file. Describe the process by which you figured out your answer.
- [4] Modify the remember module so the behavior of writes change as follows. Explain how you verified each.
- [1] Increase the allocation size to 16K of storage.
- [1] Allocate memory when data is first written to /dev/remember and free memory when zero bytes are written to /dev/remember or when the remember module is unloaded.
- [1] Preserve data across writes such that a shorter write preserves data from a previous longer write.
- [1] Allow writes to non-zero offsets (subject to the maximum size of /dev/remember).
Test Code
For the programming questions, you should create tests. Here's a fragment of a test program that test for null pointer access when reading.
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
#include <sys/stat.h>
#include <fcntl.h>
int open_remember(void) {
int fd;
fd = open("/dev/remember", O_RDWR);
if (fd < 0) {
fprintf(stderr, "Could not open the remember device.\n");
exit(-1);
}
return fd;
}
void read_null_test(void)
{
ssize_t c;
int fd;
fd = open_remember();
c = read(fd, NULL, 1024);
if (c >= 0) {
printf("read with NULL buffer succeeded\n");
} else {
perror("Error reading remember in NULL buffer test");
}
close(fd);
}
int main(int argc, char *argv)
{
read_null_test();
return 0;
}
Solutions
COMP 3000 Winter 2019
Assignment 3 solutions
1. [2] What are two reasons Linux kernel code doesn't make system
calls?
A: One reason is making a system call requires using a special
instruction that switches the CPU between user and supervisor mode.
Since kernel code already runs in supervisor mode, it doesn't need the
CPU to switch modes.
Another is that system calls assume the context of a specific
userspace process, with its own memory map, user ID, open files, etc.
Kernel code implements that context, thus it normally cannot assume
it.
If the kernel needs system call-level functionality, it can either
call the underlying functions directly or it can spawn a process that
could then make normal system calls. (Indeed, when the Linux kernel
needs to do things like load configuration files it relies upon
userspace helper programs.)
===========================================================================
2. [2] What code could we use to get the information returned by
getuid and geteuid system calls in the kernel? How do you know your
code is correct?
A: We could use the following:
getuid: from_kuid_munged(current_user_ns(), current_uid());
geteuid: from_kuid_munged(current_user_ns(), current_euid());
We know this code is correct because it is how the Linux kernel itself
implements the getuid and geteuid system calls in kernel/sys.c. See
https://elixir.bootlin.com/linux/v5.0.2/source/kernel/sys.c#L919
===========================================================================
3. [2] When you unload a kernel module, can the kernel automatically
deallocate the resources that were used by the module? Explain.
A: The kernel cannot automatically deallocate the resources used by a
module because modules are just linked in to the kernel - there is no
explicit boundary/packaging that would allow a module's resources to
be cleanly de-allocated. (We have processes for that!) Thus modules
must de-allocate all resources on module exit, as we have seen in the
modules used in class.
===========================================================================
4. [2] If you remove the remember module while a process is accessing
it, what happens to the process? Please give your test program and
appropriate output from ps. What happens if you try to reload the
remember module?
A: Below is a simple test program that continuously reads from
/dev/remember. You could do much the same by just calling tail -f on
/dev/remember.
*****
/* remember-test.c */
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
#include <sys/stat.h>
#include <fcntl.h>
int main(int argc, char *argv)
{
int fd, c;
char buf[1024];
fd = open("/dev/remember", O_RDONLY);
if (fd < 0) {
fprintf(stderr, "Could not open the remember device.\n");
exit(-1);
}
while (1) {
c = read(fd, buf, 1024);
if (c > 0) {
printf("%s", buf);
}
}
exit(0);
}
*****
If you run this program and remove the remember module while it is
running, it will put remember-test into an uninterruptable sleep,
something like this:
student 5807 4.3 0.0 0 0 pts/1 D+ 22:02 0:02 [remember-test]
Also, it will generate kernel oops's in the log - essentially, the
kernel encounters memory access errors with the module removed and
then needs to be rebooted to properly recover. (Your instance may
need a hard reboot.)
===========================================================================
5. [2] What happens if you call class_create() in a module using a
class name that already exists in the kernel? Describe the process by
which you figured out your answer.
If you use a class name that already exists, the call to
class_create() will fail outputting an error message to the kernel log
(oops followed my messages) and the module will fail to load. You can
observe this by changing line 29 in remember.c to be an existing
class, such as:
#define CLASS_NAME "ppp"
After recompiling the module and installing it, it produces the
following error:
Mar 17 12:03:42 soma-1 kernel: [ 24.335105] sysfs: cannot create
duplicate fil ename '/class/ppp'
[ LONG CALL TRACE HERE INCLUDING KERNEL STACK DUMP AND REGISTERS ]
Mar 17 12:03:42 soma-1 kernel: [ 24.335457] kobject_add_internal
failed for ppp with -EEXIST, don't try to register things with the
same name in the same directory.
Mar 17 12:03:42 soma-1 kernel: [ 24.335463] Remember: failed to
register device class 'ppp'
===========================================================================
6. [2] Fix the remember module so that it returns EFAULT to userspace
when given an invalid pointer. Describe the process by which you
figured out your answer.
A: Below is the diff that adds support for EFAULT. If you look in the
kernel source for copy_to_user() and copy_from_user(), they both
return an unsigned long. It was not clear to me what they returned,
but after logging their return values it was clear that they return 0
on success and a nonzero value on error. To return EFAULT, a search
of the kernel source finds many instances of system calls returning
-EFAULT. Combining these two results in changes to remember_read()
and remember_write().
Below is also a test program showing these programs return EFAULT (Bad
address) as they should when given an invalid buffer.
*** remember-orig/remember.c 2018-11-04 10:51:12.000000000 -0500
--- remember-q6/remember.c 2019-03-17 12:43:44.000000000 -0400
***************
*** 46,52 ****
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");
--- 46,52 ----
static ssize_t remember_read(struct file *f, char *buf, size_t len, loff_t *offset)
{
! unsigned long n, retval;
char *error_msg = "Buffer too small.";
pr_info("Remember: read started\n");
***************
*** 62,77 ****
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);
! copy_to_user(buf, saved_data, saved_data_len);
! *offset = saved_data_len;
!
! return saved_data_len;
}
}
--- 62,83 ----
if (n > len) {
n = len;
}
! retval = copy_to_user(buf, error_msg, n);
! if (retval) {
! return -EFAULT;
! } else {
! return n;
! }
} else {
pr_info("Remember: read returning data, %ld bytes\n",
saved_data_len);
! retval = copy_to_user(buf, saved_data, saved_data_len);
! if (retval) {
! return -EFAULT;
! } else {
! *offset = saved_data_len;
! return saved_data_len;
! }
}
}
***************
*** 126,136 ****
pr_info("Remember: write saving data, %ld bytes", len);
result = copy_from_user(saved_data, buf, len);
! saved_data_len = len;
!
! *offset = len;
!
! return len;
}
static int remember_release(struct inode *the_inode, struct file *f)
--- 132,144 ----
pr_info("Remember: write saving data, %ld bytes", len);
result = copy_from_user(saved_data, buf, len);
! if (result) {
! return -EFAULT;
! } else {
! saved_data_len = len;
! *offset = len;
! return len;
! }
}
static int remember_release(struct inode *the_inode, struct file *f)
/* test program for question 6 */
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
#include <sys/stat.h>
#include <fcntl.h>
int open_remember(void) {
int fd;
fd = open("/dev/remember", O_RDWR);
if (fd < 0) {
fprintf(stderr, "Could not open the remember device.\n");
exit(-1);
}
return fd;
}
void read_null_test(void)
{
ssize_t c;
int fd;
fd = open_remember();
c = read(fd, NULL, 1024);
if (c >= 0) {
printf("read with NULL buffer succeeded\n");
} else {
perror("Error reading remember in NULL buffer test");
}
close(fd);
}
void read_valid_test(void)
{
ssize_t c;
char buf[1024];
int fd;
fd = open_remember();
c = read(fd, buf, 1024);
if (c >= 0) {
printf("read with valid buffer succeeded: %s\n", buf);
} else {
perror("Error reading remember in valid buffer test");
}
close(fd);
}
void write_null_test(void)
{
ssize_t c;
int fd;
fd = open_remember();
c = write(fd, NULL, 1024);
if (c >= 0) {
printf("write with NULL buffer succeeded\n");
} else {
perror("Error writing remember in NULL buffer test");
}
close(fd);
}
void write_valid_test(void)
{
ssize_t c;
int fd;
fd = open_remember();
c = write(fd, "This is a test string.", 22);
if (c >= 0) {
printf("write with valid buffer succeeded\n");
} else {
perror("Error writing remember in valid buffer test");
}
close(fd);
}
int main(int argc, char *argv)
{
int fd;
write_valid_test();
read_valid_test();
read_null_test();
write_null_test();
read_valid_test();
exit(0);
}
===========================================================================
7. [2] In the remember module, modify remember_read() so it uses a
non-zero offset properly rather than simply logging an error.
Describe the process by which you figured out your answer.
A: Diff below is versus the code for question 6. Answering this
question didn't require going to the kernel source; instead, I just
needed to calculate the appropriate range to copy by taking into
account the offset, keeping in mind the start or end could be past the
end of the stored data. The bookkeeping is a bit tricky but no more
difficult than (manual) C string manipulation.
After the diff is a simple test function (designed to be added to the
test program for Q6) that does a series of short reads to make sure
the offsets are being calculated properly.
*** remember-q6/remember.c 2019-03-17 12:43:44.000000000 -0400
--- remember-q7/remember.c 2019-03-17 16:42:54.000000000 -0400
***************
*** 46,83 ****
static ssize_t remember_read(struct file *f, char *buf, size_t len, loff_t *offset)
{
! unsigned long n, retval;
! 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;
! }
! retval = copy_to_user(buf, error_msg, n);
! if (retval) {
! return -EFAULT;
! } else {
! return n;
! }
} else {
! pr_info("Remember: read returning data, %ld bytes\n",
! saved_data_len);
! retval = copy_to_user(buf, saved_data, saved_data_len);
! if (retval) {
! return -EFAULT;
! } else {
! *offset = saved_data_len;
! return saved_data_len;
! }
}
}
--- 46,78 ----
static ssize_t remember_read(struct file *f, char *buf, size_t len, loff_t *offset)
{
! unsigned long retval;
! loff_t start, end;
!
pr_info("Remember: read started\n");
+
+ start = *offset;
+ end = start + len;
+
+ if (start > saved_data_len) {
+ len = 0;
+ } else if (end > saved_data_len) {
+ len = saved_data_len - start;
+ }
! pr_info("Remember: read returning data, %ld bytes\n",
! len);
!
! if (len == 0) {
return 0;
}
!
! retval = copy_to_user(buf, saved_data+start, len);
! if (retval) {
! return -EFAULT;
} else {
! *offset = end;
! return len;
}
}
void read_small_test(void)
{
const int bufsize = 5;
ssize_t c;
char buf[bufsize+1];
int fd, retval;
fd = open_remember();
do {
c = read(fd, buf, bufsize);
if (c >= 0) {
buf[c] = '\0';
printf("read with small buffer succeeded: %s\n", buf);
} else {
perror("Error reading remember in small buffer test");
}
} while (c == bufsize);
close(fd);
}
===========================================================================
8. [2] Modify the remember module so llseek system calls work as they
do on regular files, for whence values of SEEK_CUR and SEEK_SET. You
should not allow the offset to be set to a value past the current end
of file. Describe the process by which you figured out your answer.
A: In order to answer this question I had to look to see how llseek is
implemented in other filesystems. It turns out searching for SEEK_CUR
in the kernel source finds a number of examples. In the regular
filesystems the offset is changed in the inode, but in the driver
files we see changes to ->f_pos in the file struct, so that is what
needs to be changed here. In these places we can also see the
function definition for the function. (As before, diff and test
function follow.)
*** remember-q7/remember.c 2019-03-17 16:42:54.000000000 -0400
--- remember-q8/remember.c 2019-03-17 20:47:13.000000000 -0400
***************
*** 143,152 ****
--- 143,175 ----
}
+ static loff_t remember_llseek(struct file *f, loff_t offset, int whence)
+ {
+ loff_t result = -EINVAL;
+
+ switch (whence) {
+ case SEEK_CUR:
+ if (offset + f->f_pos <= saved_data_len) {
+ f->f_pos = offset + f->f_pos;
+ result = f->f_pos;
+ }
+ break;
+ case SEEK_SET:
+ if (offset <= saved_data_len) {
+ f->f_pos = offset;
+ result = offset;
+ }
+ break;
+ }
+
+ return result;
+ }
+
static struct file_operations remember_fops = {
.open = remember_open,
.read = remember_read,
.write = remember_write,
+ .llseek = remember_llseek,
.release = remember_release,
};
void lseek_test(void) {
ssize_t c;
char buf[1024];
int fd;
off_t result;
fd = open_remember();
result = lseek(fd, 4, SEEK_SET);
if (result < 0) {
perror("Error seeking with SEEK_SET");
close(fd);
return;
}
result = lseek(fd, 2, SEEK_CUR);
if (result < 0) {
perror("Error seeking with SEEK_SET");
close(fd);
return;
}
c = read(fd, buf, 1024);
if (c >= 0) {
buf[c] = '\0';
printf("read with seeks succeeded: %s\n", buf);
} else {
perror("Error reading remember in seek test");
}
close(fd);
}
===========================================================================
9. [4] Modify the remember module so the behavior of writes change as follows:
a) [1] Increase the allocation size to 16K of storage.
b) [1] Allocate memory when data is first written to /dev/remember
and free memory when zero bytes are written to /dev/remember or
when the remember module is unloaded.
c) [1] Preserve data across writes such that a shorter write
preserves data from a previous longer write.
d) [1] Allow writes to non-zero offsets (subject to the maximum size
of /dev/remember).
A: Code is below. Note that this work required no references to the
rest of the kernel, everything necessary is in the existing code.
Key changes and tests to verify:
a) Change saved_data_order and saved_data_max. To test, run dd:
dd if=/dev/urandom of=/dev/remember bs=128 count=1000
It should say that it can write 16384 bytes. This also tests writes to
non-zero offsets as the writes happen one after the other (part d).
b) Add a test for zero writes and free data then. Use this test
function to make sure data is deallocated on zero:
void write_zero_test(void)
{
ssize_t c;
int fd;
fd = open_remember();
c = write(fd, NULL, 0);
if (c >= 0) {
printf("zero write succeeded\n");
} else {
perror("Error in zero write test");
}
close(fd);
}
c) Make sure whe don't free data on every write and never shrink
saved_data_len. To test, just do a long write followed by a short
write.
echo "Hello! this is a test" > /dev/remember
echo -n "Goodbye" > /dev/remember
cat /dev/remember
This should output:
Goodbye this is a test
d) Again, like remember_read, we just have to keep track of the
offsets in the same way as handling C strings manually. Tests for a) cover
this case.
*** remember-q8/remember.c 2019-03-17 20:47:13.000000000 -0400
--- remember-q9/remember.c 2019-03-17 23:30:59.000000000 -0400
***************
*** 35,42 ****
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 int remember_open(struct inode *the_inode, struct file *f)
{
--- 35,42 ----
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 * 4;
! static int saved_data_order = 2; /* Assuming 4K pages, this is 16K */
static int remember_open(struct inode *the_inode, struct file *f)
{
***************
*** 110,137 ****
loff_t *offset)
{
unsigned long result;
! if (*offset > 0) {
! pr_info("Remember: write nonzero offset, aborting");
!
return 0;
}
! free_saved_data();
! init_saved_data();
!
! if (len > saved_data_max) {
! len = saved_data_max;
}
pr_info("Remember: write saving data, %ld bytes", len);
! result = copy_from_user(saved_data, buf, len);
if (result) {
return -EFAULT;
} else {
! saved_data_len = len;
! *offset = len;
return len;
}
}
--- 110,151 ----
loff_t *offset)
{
unsigned long result;
+ loff_t start, end;
! /* free storage with a write of zero bytes */
! if (len == 0) {
! free_saved_data();
! *offset = 0;
return 0;
}
+
+ /* only allocate if not previously allocated */
+ if (!saved_data) {
+ init_saved_data();
+ }
+
+ start = *offset;
+ end = start + len;
+
+ if (start > saved_data_max) {
+ return -EINVAL;
+ }
! if (end > saved_data_max) {
! end = saved_data_max;
! len = end - start;
}
pr_info("Remember: write saving data, %ld bytes", len);
! result = copy_from_user(saved_data + start, buf, len);
if (result) {
return -EFAULT;
} else {
! if (saved_data_len < end) {
! saved_data_len = end;
! }
! *offset += len;
return len;
}
}