HW5: Fridge

Part 1: The Fridge, a Kernel Key-Value Store (80 points)

In this part, we will implement an in-kernel key-value store, aka the 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, and -1 on failure. 
 * The flags parameter is currently unused.
 *
 * The result of initializing twice (without an intervening 
 * kvv_destroy() call) is undefined.
 */
int kkv_init(int flags);

/*
 * Destroy the Kernel Key-Value store, removing all entries 
 * and deallocating all memories.
 *
 * Returns the number of entries removed on success, and -1 on failure.
 * 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" pointer will 
 * be copied.  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, and -1 on failure. 
 * 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);

The fridge will use a hash table defined as follows. You must use the data structures as given. Please do not modify them in any way. The fridge_data_structures.h file, provided as skeleton code, contains the structure definitions.

#define HASH_TABLE_LENGTH 17

/*
 * 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:

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

  2. Install libfridge.so, the user space wrapper library for the fridge system calls.

  3. Implement the 4 system calls. Initially, don’t worry about locking. Make it work for single-thread 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. Make sure that you are holding the lock only when necessary.

  5. In this part, you can assume that, while the kkv_put() and kkv_get() are crazy concurrent, the kkv_init() and kkv_destroy() are called in an orderly manner. That is, only a single call to kkv_init() is made in the beginning, and only a single call to kvv_destroy() is made at the end. We will deal with concurrency and misuse of init and destroy in the next part.

Requirements

Deliverables

  1. A working version of fridge.c that passes the given test programs.

  2. Your own test programs to further test your implementation. The graders will use additional test programs. Test your system calls as rigorously as you can!

  3. The following info in your README.txt:

Part 2: Undefined? Yes. Crash? No Way! (40 points)

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 all possible uses and misuses. A user program should never be able to crash the 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 with errno set to EPERM is a reasonable course of action in those cases.

Requirements

Deliverables

  1. A new version of fridge.c.

  2. Your own test program to stress-test your system calls. The graders will use additional test programs. Test your system calls as rigorously as you can!

  3. The following info in your README.txt:

Part 3: Using the SLAB allocator (20 points)

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

Deliverables

  1. A new version of fridge.c that correctly uses SLAB layer while preserving all of the previous parts’ functionality.

  2. Test driver to compare the performances between the previous version from part 2 and the SLAB version from this part.

  3. The following info in your README.txt:

Part 4: Empty Fridge (80 points)

In this part, we will modify the fridge implementation so that kkv_get() system call supports blocking.

The following was the API documentation for kkv_get() from part 1:

/*
 * 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);

Now, we will use the flags parameter to specify blocking behavior. When flags == 0, kkv_get() will behave exactly the same as before, as described in the API documentation above.

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

  1. Returns 0 if a key-value pair was found, removed and returned. 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 it 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() will happen without an intervening removal of the key-value pair. 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 with errno set to EINTR in that case.

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().

Here are some requirements and hints:

Deliverables

  1. A new version of fridge.c that passes the given test programs.

  2. Your own test programs to further test your implementation.
    The graders will use additional test programs. Test your system calls as rigorously as you can!

  3. The following info in your README.txt:

Good luck!

Acknowledgment

The initial Fridge API and the test drivers are 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 drivers are written by the following TAs of COMS W4118 Operating Systems I, Spring 2016, Columbia University:

Last updated: 2017–03–09