HW5-fridge

HW5: Fridge

Submission

As with previous assignments, we wil be using GitHub to distribute skeleton code and collect submissions. Please refer to our Git Workflow guide for more details. Note that we will be using multiple tags for this assignment, for each deliverable part.

Part 0: Apply Kernel Syscall Stubs + Install libfridge

Kernel Syscall Stubs

In addition to the pristine Linux kernel source tree (now under linux/), we’ve provided a patch file which will create the syscall stubs for you. You will need to apply this patch to your repo.

The patch is under the following path:

patch/fridge.patch

You can use git apply to apply this patch. First, check which files will be modified by the patch:

$ git apply --stat patch/fridge.patch

You should also inspect what the patch is doing by reading the diffs inside. Finally, you can apply the patch with the following:

$ git apply patch/fridge.patch

Now, when you run git status, you should see some files modified, as well as a file added at linux/kernel/kkv.c. After verifying that these changes worked as intended, commit them.

Now, when you build your kernel, you should have the four fridge system call stubs in your kernel. Make sure you’re building with a local version that is different from your fallback (-cs4118), so you don’t overwrite it; set your local version to your UNI (i.e. -<uni>-HW5).

libfridge

For this assignment, you will be using libfridge, a user space wrapper library for the fridge system calls.

In your skeleton repo, you will find the source code for libfridge under the directory user/lib/libfridge/. You will building and installing this code. The library is implemented in fridge.h and libfridge.c; the many other files are mostly scripts and boilerplate used by GNU Autotools to build and install the library.

Build the library and install the library by following the instructions in the README. The last step, sudo make install, will copy fridge.h and libfridge.so into /usr/local/include/ and /usr/local/lib/, respectively. It will also invoke ldconfig, so that programs can find and link to the new library.

After you install libfridge, you should be able to #include <fridge.h> in your userspace programs when you compile, and link against libfridge by passing the -lfridge flag when you link.

Part 1: Fridge, a Kernel Key-Value Store

In this part, we will implement an in-kernel key-value store, Fridge. The fridge will be accessed using the following four systems calls that you will add to the Linux kernel:

/*
 * Initialize the Kernel Key-Value store.
 * 
 * Returns 0 on success.
 * Returns -1 on failure, with errno set accordingly.
 * The flags parameter is currently unused.
 *
 * The result of initializing twice (without an intervening 
 * kkv_destroy() call) is undefined.
 */
int kkv_init(int flags);

/*
 * Destroy the Kernel Key-Value store, removing all entries 
 * and deallocating all memory.
 *
 * Returns the number of entries removed on success.
 * Returns -1 on failure, with errno set accordingly.
 * The flags parameter is currently unused.
 *
 * After calling kkv_destroy(), the Kernel Key-Value store can be 
 * re-initialized by calling kkv_init() again.
 *
 * The result of destroying before initializing is undefined.
 */
int kkv_destroy(int flags);

/*
 * If a key-value pair is found for the given key, the pair is 
 * REMOVED from the Kernel Key-Value store.
 *
 * The value is copied into the buffer pointed to by the "value" parameter,
 * up to max_size bytes. Note that if the value was a string of
 * length >= max_size, the string will be truncated and it will not be
 * null-terminated.
 *
 * Returns 0 if a key-value pair was found, removed and returned.
 * Returns -1 with errno set to ENOENT if the key was not found.
 * Returns -1 on other failures, with errno set accordingly.
 * The flags parameter is currently unused.
 *
 * The result of calling kkv_get() before initializing the Kernel Key-Value
 * store is undefined.
 */
int kkv_get(uint32_t key, char *value, size_t max_size, int flags);

/*
 * Insert a new key-value pair. The previous value for the key, if any, is
 * replaced by the new value.
 *
 * The "size" bytes from the buffer pointed to by the "value" parameter
 * will be copied into the Kernel Key-Value store.
 *
 * If the value is a string, make sure that size == strlen(value) + 1,
 * so that the null character is stored as part of the value.
 *
 * Returns 0 on success.
 * Returns -1 on failure, with errno set accordingly.
 * The flags parameter is currently unused.
 *
 * The result of calling kkv_put() before initializing the Kernel
 * Key-Value store is undefined.
 */
int kkv_put(uint32_t key, char *value, size_t size, int flags);

Alongside a kernel module stub, we’ve provided a header file in your skeleton code which defines some hash table data structures. You must use these data structures in your fridge implementation; do not modify them in any way.

Note that some of the struct members are for part 4 only; you may leave these unused. The relevant fields for this part are the following:

#define HASH_TABLE_LENGTH 17
#define KKV_NONBLOCK 0

/*
 * A key-value pair.
 */
struct kkv_pair {
        char *value;
        uint32_t key;
        size_t size;
};

/*
 * A node in a linked list. Contains a key-value pair.
 */
struct kkv_ht_entry {
        struct list_head entries;
        struct kkv_pair kv_pair;
};

/*
 * A bucket in the hash table. 
 * The hash table is an array of HASH_TABLE_LENGTH buckets.
 */
struct kkv_ht_bucket {
        spinlock_t lock;
        struct list_head entries;
        uint32_t count;
};

Tasks

  1. Please read the following pages on kernel locks:

    • LKD chapter 10: pages 183 (from Spin Locks) - 202

    You will also want to refresh your memory on using kernel linked lists and allocating kernel memory using kmalloc(). We used them in HW2.

  2. Have a look at fridge.h and libfridge.c from the libfridge source code, and how they invoke the syscalls.

  3. Implement the four system calls.

    • Your implementation must work with the libfridge wrappers, which means your system call numbers must match those assumed in the library.

    • For this step, don’t worry about locking; just make it work for single-threaded test programs.

  4. Now implement locking, so that put and get work with concurrent puts and gets.

    • Use the spin lock embedded in each bucket. Spin locks should be grabbed and released as quickly as possible. Make sure to structure your code to minimize the locked region, and only hold locks only when necessary.

Requirements

Submission

To submit this part, push the hw5p1handin tag with the following:

$ git tag -a -m "Completed hw5 part1." hw5p1handin
$ git push origin master
$ git push origin hw5p1handin

Part 2: Undefined? Yes. Crash? No Way!

What should happen when a user program misuses the system calls? What happens when kkv_init() gets called twice in a row? What happens when kkv_destroy() is called while the kernel is executing kkv_put()?

In the API function comments shown above, certain behaviors are left undefined. For user level library functions, an easy way to implement undefined behaviors is to not do anything special, and possibly let the program crash.

This is not the case for system calls. System calls must be robust against misuse and abuse. A user program should never be able to crash the operating system or corrupt kernel data structures no matter what it does.

Modify the code so that the four system calls can be called in any order and in any degree of concurrency between them. Of course, if a sequence of calls doesn’t make sense, they don’t have to succeed. Returning -1 and setting errno to EPERM is a reasonable course of action in those cases.

Requirements

Submission

To submit this part, push the hw5p2handin tag with the following:

$ git tag -a -m "Completed hw5 part2." hw5p2handin
$ git push origin master
$ git push origin hw5p2handin

Part 3: Using the SLAB allocator

The Linux kernel provides the SLAB layer (also called the SLAB allocator) as a more efficient way to manage memory for kernel-level data structures. It is specifically designed as a memory management interface to be used for repeated allocations and deallocations of the same structures, as we are doing here with kkv_ht_entry.

Tasks

  1. Read the following pages on the SLAB allocator:

    • LKD Chapter 12, pages 245 - 252
  2. Set up a SLAB cache for struct kkv_ht_entry, and replace calls to kmalloc() and kfree() with the appropriate SLAB allocator calls for this struct.

Requirements

Submission

To submit this part, push the hw5p3handin tag with the following:

$ git tag -a -m "Completed hw5 part3." hw5p3handin
$ git push origin master
$ git push origin hw5p3handin

Part 4: Empty Fridge

In this part, we will modify the fridge implementation so that kkv_get() system call supports blocking. We will now use the flags parameter to specify blocking behavior, which will be set to either KKV_NONBLOCK or KKV_BLOCK (both defined in fridge_data_structures.h.

When flags == KKV_NONBLOCK, kkv_get() will behave exactly the same as before, as described in the API documentation in part 1.

When flags == KKV_BLOCK, kkv_get() will change its behavior as follows:

  1. Returns 0 if a key-value pair was found, removed, and written to value. (This is the same behavior as the non-blocking case.)

  2. When a key-value pair for the given key is not present in the kernel key-value store, the calling process will block, waiting for a key-value pair for the key to be added to the key-value store.

    When another thread adds a key-value pair for the key by calling kkv_put(), the waiting process will then wake up, remove the key-value pair, copy the value to user land up to max_size bytes, and returns 0.

  3. When multiple threads are waiting for the same key, and another thread adds a key-value pair for the key by calling kkv_put(), only one of the waiting threads will wake up and remove the value. The other threads will keep waiting.

    • Those other threads might have woken up, found that there is no key-value pair for the key, and gone back to sleep, but that all happens in the kernel; those threads do not return from kkv_get().

    Note that when multiple threads are waiting on the same key, you should NOT expect that each kkv_put() will be matched by a waiting thread.

    • Recall that kkv_put() will replace an existing key-value pair. It is entirely possible that two consecutive kkv_put() calls will happen without an intervening removal of the key-value pair by another thread. Keep this in mind when you write your test driver.
  4. A thread blocked on kkv_get() should return when it receives a signal. kkv_get() returns -1 and sets errno to EINTR in that case.

    • The signal_pending() kernel function will come in handy here.
    • Make sure you are not holding a lock or leaking memory when you return because of signals.

The API descriptions for kkv_put(), kkv_init(), and kkv_destroy() remain the same. That is, they will behave exactly the same as in part 1. However, you may need to change their implementations to support the new behavior of kkv_get(). The flags parameter for the remaining three syscalls will remain unused.

You should now fully utilize the data structures defined in fridge_data_structures.h. The fields that were previosuly unsed are highlighted below:

#define KKV_NONBLOCK 0
#define KKV_BLOCK 1

/*
 * A node in a linked list. Contains a key-value pair.
 */
struct kkv_ht_entry {
    struct list_head entries;
    struct kkv_pair kv_pair;
    wait_queue_head_t q;        /* only for part 4 (empty fridge) */
    uint32_t q_count;           /* only for part 4 (empty fridge) */
};

Requirements

Submission

To submit this part, push the hw5p4handin tag with the following:

$ git tag -a -m "Completed hw5 part4." hw5p4handin
$ git push origin master
$ git push origin hw5p4handin

Acknowledgements

The initial Fridge API and test driver suite was designed and implemented by the following TAs of COMS W4118 Operating Systems I, Spring 2015, Columbia University:

The Empty Fridge extension to the original Fridge API and the test driver suite was written by the following TAs of COMS W4118 Operating Systems I, Spring 2016, Columbia University:

The Fridge assignment skeleton code, assignment, and solutions were updated to support 64-bit ArchLinux and GitHub-based repo management by the following TAs of COMS W4118 Operating Systems I, Spring 2018, Columbia University:


Last updated: 2018-03-09