The Duet framework code: - bittree.c: red-black bitmap tree that keeps track of items of interest - debug.c: functions used to print information used to debug Duet - hash.c: implementation of the global hash table where page events are stored for all tasks - hook.c: the function invoked by the page cache hooks when Duet is online - init.c: routines used to bring Duet online or offline - path.c: routines performing resolution of UUIDs to paths using d_path - task.c: implementation of Duet task fd operations
Signed-off-by: George Amvrosiadis <[email protected]> --- init/Kconfig | 2 + mm/Makefile | 1 + mm/duet/Kconfig | 31 +++ mm/duet/Makefile | 7 + mm/duet/bittree.c | 537 +++++++++++++++++++++++++++++++++++++++++++++++++ mm/duet/common.h | 211 ++++++++++++++++++++ mm/duet/debug.c | 98 +++++++++ mm/duet/hash.c | 315 +++++++++++++++++++++++++++++ mm/duet/hook.c | 81 ++++++++ mm/duet/init.c | 172 ++++++++++++++++ mm/duet/path.c | 184 +++++++++++++++++ mm/duet/syscall.h | 61 ++++++ mm/duet/task.c | 584 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 13 files changed, 2284 insertions(+) create mode 100644 mm/duet/Kconfig create mode 100644 mm/duet/Makefile create mode 100644 mm/duet/bittree.c create mode 100644 mm/duet/common.h create mode 100644 mm/duet/debug.c create mode 100644 mm/duet/hash.c create mode 100644 mm/duet/hook.c create mode 100644 mm/duet/init.c create mode 100644 mm/duet/path.c create mode 100644 mm/duet/syscall.h create mode 100644 mm/duet/task.c diff --git a/init/Kconfig b/init/Kconfig index c02d897..6f94b5a 100644 --- a/init/Kconfig +++ b/init/Kconfig @@ -294,6 +294,8 @@ config USELIB earlier, you may need to enable this syscall. Current systems running glibc can safely disable this. +source mm/duet/Kconfig + config AUDIT bool "Auditing support" depends on NET diff --git a/mm/Makefile b/mm/Makefile index 78c6f7d..074c15f 100644 --- a/mm/Makefile +++ b/mm/Makefile @@ -99,3 +99,4 @@ obj-$(CONFIG_USERFAULTFD) += userfaultfd.o obj-$(CONFIG_IDLE_PAGE_TRACKING) += page_idle.o obj-$(CONFIG_FRAME_VECTOR) += frame_vector.o obj-$(CONFIG_DEBUG_PAGE_REF) += debug_page_ref.o +obj-$(CONFIG_DUET) += duet/ diff --git a/mm/duet/Kconfig b/mm/duet/Kconfig new file mode 100644 index 0000000..2f3a0c5 --- /dev/null +++ b/mm/duet/Kconfig @@ -0,0 +1,31 @@ +config DUET + bool "Duet framework support" + + help + Duet is a framework aiming to reduce the IO footprint of analytics + and maintenance work. By exposing page cache events to these tasks, + it allows them to adapt their data processing order, in order to + benefit from data available in the page cache. Duet's operation is + based on hooks into the page cache. + + To compile support for Duet, say Y. + +config DUET_STATS + bool "Duet statistics collection" + depends on DUET + help + This option enables support for the collection of statistics on the + operation of Duet. It will print information about the data structures + used internally, and profiling information about the framework. + + If unsure, say N. + +config DUET_DEBUG + bool "Duet debugging support" + depends on DUET + help + Enable runtime debugging support for the Duet framework. This may + enable additional and expensive checks with negative impact on + performance. + + To compile debugging support for Duet, say Y. If unsure, say N. diff --git a/mm/duet/Makefile b/mm/duet/Makefile new file mode 100644 index 0000000..c0c9e11 --- /dev/null +++ b/mm/duet/Makefile @@ -0,0 +1,7 @@ +# +# Makefile for the linux Duet framework. +# + +obj-$(CONFIG_DUET) += duet.o + +duet-y := init.o hash.o hook.o task.o bittree.o path.o debug.o diff --git a/mm/duet/bittree.c b/mm/duet/bittree.c new file mode 100644 index 0000000..3b20c35 --- /dev/null +++ b/mm/duet/bittree.c @@ -0,0 +1,537 @@ +/* + * Copyright (C) 2016 George Amvrosiadis. All rights reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License v2 as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + */ + +#include "common.h" + +#define BMAP_READ 0x01 /* Read bmaps (overrides other flags) */ +#define BMAP_CHECK 0x02 /* Check given bmap value expression */ + /* Sets bmaps to match expression if not set */ + +/* Bmap expressions can be formed using the following flags: */ +#define BMAP_DONE_SET 0x04 /* Set done bmap values */ +#define BMAP_DONE_RST 0x08 /* Reset done bmap values */ +#define BMAP_RELV_SET 0x10 /* Set relevant bmap values */ +#define BMAP_RELV_RST 0x20 /* Reset relevant bmap values */ +#define BMAP_SEEN_SET 0x40 /* Set seen bmap values */ +#define BMAP_SEEN_RST 0x80 /* Reset seen bmap values */ + +/* Some macros to make our life easier */ +#define BMAP_ALL_SET (BMAP_SEEN_SET | BMAP_RELV_SET | BMAP_DONE_SET) +#define BMAP_ALL_RST (BMAP_SEEN_RST | BMAP_RELV_RST | BMAP_DONE_RST) + +#define BITTREE_RANGE PAGE_SIZE /* Bytes per bitmap bit */ +#define BITS_PER_NODE (32768 * 8) /* 32KB bitmaps */ + +#define UUID_IDX(uuid) (((unsigned long long) uuid.gen << 32) | \ + (unsigned long long) uuid.ino) +/* + * The following functions are wrappers for the basic bitmap functions. + * A bitmap is characterized by a starting offset (bstart). The wrappers + * translate an arbitrary idx to the appropriate bit. + */ + +/* Sets (or resets) a single bit */ +static int bmap_set(unsigned long *bmap, __u64 start, __u64 idx, __u8 do_set) +{ + __u64 bofft = idx - start; + + if (bofft + 1 >= start + (BITS_PER_NODE * BITTREE_RANGE)) + return -1; + + /* Convert range to bitmap granularity */ + do_div(bofft, BITTREE_RANGE); + + if (do_set) + bitmap_set(bmap, (unsigned int)bofft, 1); + else + bitmap_clear(bmap, (unsigned int)bofft, 1); + + return 0; +} + +/* Returns value of bit at idx */ +static int bmap_read(unsigned long *bmap, __u64 start, __u64 idx) +{ + __u64 bofft64 = idx - start; + unsigned long *p, mask; + unsigned int bofft; + + if (bofft64 + 1 >= start + (BITS_PER_NODE * BITTREE_RANGE)) + return -1; + + /* Convert offset to bitmap granularity */ + do_div(bofft64, BITTREE_RANGE); + bofft = (unsigned int)bofft64; + + /* Check the bits */ + p = bmap + BIT_WORD(bofft); + mask = BITMAP_FIRST_WORD_MASK(bofft) & BITMAP_LAST_WORD_MASK(bofft + 1); + + if ((*p) & mask) + return 1; + + return 0; +} + +/* Checks whether a bit is set */ +static int bmap_chk(unsigned long *bmap, __u64 start, __u64 idx, __u8 do_set) +{ + __u64 bofft64 = idx - start; + unsigned long *p, mask; + unsigned int bofft; + + if (bofft64 + 1 >= start + (BITS_PER_NODE * BITTREE_RANGE)) + return -1; + + /* Convert range to bitmap granularity */ + do_div(bofft64, BITTREE_RANGE); + + /* Now it is safe to cast these variables */ + bofft = (unsigned int)bofft64; + + /* Check the bit */ + p = bmap + BIT_WORD(bofft); + mask = BITMAP_FIRST_WORD_MASK(bofft) & BITMAP_LAST_WORD_MASK(bofft + 1); + + if (do_set && !((*p) & mask)) + return 0; + else if (!do_set && !(~(*p) & mask)) + return 0; + + return 1; +} + +/* Initializes a bitmap tree node */ +static struct bmap_rbnode *bnode_init(struct duet_bittree *bt, __u64 idx) +{ + struct bmap_rbnode *bnode = NULL; + +#ifdef CONFIG_DUET_STATS + if (bt) { + (bt->statcur)++; + if (bt->statcur > bt->statmax) { + bt->statmax = bt->statcur; + pr_info("duet: %llu BitTree nodes (%llub)\n", + bt->statmax, bt->statmax * BITS_PER_NODE / 8); + } + } +#endif /* CONFIG_DUET_STATS */ + + bnode = kmalloc(sizeof(*bnode), GFP_NOWAIT); + if (!bnode) + return NULL; + + bnode->done = kzalloc(sizeof(unsigned long) * + BITS_TO_LONGS(BITS_PER_NODE), GFP_NOWAIT); + if (!bnode->done) { + kfree(bnode); + return NULL; + } + + /* Allocate relevant bitmap, if needed */ + bnode->relv = kzalloc(sizeof(unsigned long) * + BITS_TO_LONGS(BITS_PER_NODE), GFP_NOWAIT); + if (!bnode->relv) { + kfree(bnode->done); + kfree(bnode); + return NULL; + } + + bnode->seen = kzalloc(sizeof(unsigned long) * + BITS_TO_LONGS(BITS_PER_NODE), GFP_NOWAIT); + if (!bnode->seen) { + kfree(bnode->relv); + kfree(bnode->done); + kfree(bnode); + return NULL; + } + + RB_CLEAR_NODE(&bnode->node); + bnode->idx = idx; + return bnode; +} + +static void bnode_dispose(struct bmap_rbnode *bnode, struct rb_node *rbnode, + struct duet_bittree *bt) +{ +#ifdef CONFIG_DUET_STATS + if (bt) + (bt->statcur)--; +#endif /* CONFIG_DUET_STATS */ + rb_erase(rbnode, &bt->root); + kfree(bnode->relv); + kfree(bnode->seen); + kfree(bnode->done); + kfree(bnode); +} + +/* + * Traverses bitmap nodes to read/set/unset/check a specific bit across bitmaps. + * May insert/remove bitmap nodes as needed. + * + * If DUET_BMAP_READ is set: + * - the bitmap value for idx are read for one or all bitmaps + * Otherwise, if DUET_BMAP_CHECK flag is set: + * - return value 1 means the idx matches the given flags + * - return value 0 means the idx doesn't match the given flags + * Otherwise, if neither flag is set: + * - return value 0 means the idx was updated to match given flags + * + * In all cases, a return value -1 denotes an error. + */ +static int __update_tree(struct duet_bittree *bt, __u64 idx, __u8 flags) +{ + int found, ret, res; + __u64 node_offt, div_rem; + struct rb_node **link, *parent; + struct bmap_rbnode *bnode = NULL; + unsigned long iflags; + + local_irq_save(iflags); + spin_lock(&bt->lock); + + div64_u64_rem(idx, BITTREE_RANGE * BITS_PER_NODE, &div_rem); + node_offt = idx - div_rem; + + /* Look up BitTree node */ + found = 0; + link = &(bt->root).rb_node; + parent = NULL; + + while (*link) { + parent = *link; + bnode = rb_entry(parent, struct bmap_rbnode, node); + + if (bnode->idx > node_offt) { + link = &(*link)->rb_left; + } else if (bnode->idx < node_offt) { + link = &(*link)->rb_right; + } else { + found = 1; + break; + } + } + + /* If we're just reading bitmap values, return them now */ + if (flags & BMAP_READ) { + ret = 0; + + if (!found) + goto done; + + /* First read seen bit */ + res = bmap_read(bnode->seen, bnode->idx, idx); + if (res == -1) { + ret = -1; + goto done; + } + ret |= res << 2; + + /* Then read relevant bit */ + res = bmap_read(bnode->relv, bnode->idx, idx); + if (res == -1) { + ret = -1; + goto done; + } + ret |= res << 1; + + /* Read done bit */ + res = bmap_read(bnode->done, bnode->idx, idx); + if (res == -1) { + ret = -1; + goto done; + } + + ret |= res; + goto done; + } + + /* + * Take appropriate action based on whether we found the node + * and whether we plan to update (SET/RST), or only CHECK it. + * + * NULL | Found !Found | + * -------+------------------------------------+ + * SET | Set Bits | Init new node | + * |------------------+-----------------| + * RST | Clear (dispose?) | Nothing | + * -------+------------------------------------+ + * + * CHECK | Found !Found | + * -------+------------------------------------+ + * SET | Check Bits | Return false | + * |------------------+-----------------| + * RST | Check Bits | Continue | + * -------+------------------------------------+ + */ + + /* First handle setting (or checking set) bits */ + if (flags & BMAP_ALL_SET) { + if (!found && !(flags & BMAP_CHECK)) { + /* Insert the new node */ + bnode = bnode_init(bt, node_offt); + if (!bnode) { + ret = -1; + goto done; + } + + rb_link_node(&bnode->node, parent, link); + rb_insert_color(&bnode->node, &bt->root); + + } else if (!found && (flags & BMAP_CHECK)) { + /* Looking for set bits, node didn't exist */ + ret = 0; + goto done; + } + + /* Set the bits. Return -1 if something goes wrong. */ + if (!(flags & BMAP_CHECK)) { + if ((flags & BMAP_SEEN_SET) && + bmap_set(bnode->seen, bnode->idx, idx, 1)) { + ret = -1; + goto done; + } + + if ((flags & BMAP_RELV_SET) && + bmap_set(bnode->relv, bnode->idx, idx, 1)) { + ret = -1; + goto done; + } + + if ((flags & BMAP_DONE_SET) && + bmap_set(bnode->done, bnode->idx, idx, 1)) { + ret = -1; + goto done; + } + + /* Check the bits. Return if any bits are off */ + } else { + if (flags & BMAP_SEEN_SET) { + ret = bmap_chk(bnode->seen, bnode->idx, idx, 1); + if (ret != 1) + goto done; + } + + if (flags & BMAP_RELV_SET) { + ret = bmap_chk(bnode->relv, bnode->idx, idx, 1); + if (ret != 1) + goto done; + } + + ret = bmap_chk(bnode->done, bnode->idx, idx, 1); + if (ret != 1) + goto done; + } + } + + /* Now handle unsetting any bits */ + if (found && (flags & BMAP_ALL_RST)) { + /* Clear the bits. Return -1 if something goes wrong. */ + if (!(flags & BMAP_CHECK)) { + if ((flags & BMAP_SEEN_RST) && + bmap_set(bnode->seen, bnode->idx, idx, 0)) { + ret = -1; + goto done; + } + + if ((flags & BMAP_RELV_RST) && + bmap_set(bnode->relv, bnode->idx, idx, 0)) { + ret = -1; + goto done; + } + + if ((flags & BMAP_DONE_RST) && + bmap_set(bnode->done, bnode->idx, idx, 0)) { + ret = -1; + goto done; + } + + /* Check the bits. Return if any bits are off */ + } else { + if (flags & BMAP_SEEN_RST) { + ret = bmap_chk(bnode->seen, bnode->idx, idx, 0); + if (ret != 1) + goto done; + } + + if (flags & BMAP_RELV_RST) { + ret = bmap_chk(bnode->relv, bnode->idx, idx, 0); + if (ret != 1) + goto done; + } + + ret = bmap_chk(bnode->done, bnode->idx, idx, 0); + if (ret != 1) + goto done; + } + + /* Dispose of the node if empty */ + if (!(flags & BMAP_CHECK) && + bitmap_empty(bnode->done, BITS_PER_NODE) && + bitmap_empty(bnode->seen, BITS_PER_NODE) && + bitmap_empty(bnode->relv, BITS_PER_NODE)) + bnode_dispose(bnode, parent, bt); + } + + if (!(flags & BMAP_CHECK)) + ret = 0; + else + ret = 1; + +done: + if (ret == -1) + pr_err("duet: blocks were not %s\n", + (flags & BMAP_READ) ? "read" : + ((flags & BMAP_CHECK) ? "checked" : "modified")); + spin_unlock(&bt->lock); + local_irq_restore(iflags); + return ret; +} + +/* + * Check if we have seen this inode before. If not, check if it is relevant. + * Then, check whether it's done. + */ +static int do_bittree_check(struct duet_bittree *bt, struct duet_uuid uuid, + struct duet_task *task, struct inode *inode) +{ + int ret, bits; + unsigned long long idx = UUID_IDX(uuid); + + bits = __update_tree(bt, idx, BMAP_READ); + + if (!(bits & 0x4)) { + /* We have not seen this inode before */ + if (inode) { + ret = do_find_path(task, inode, 0, NULL, 0); + } else if (task) { + ret = duet_find_path(task, uuid, 0, NULL, 0); + } else { + pr_err("duet: check failed, no task/inode\n"); + return -1; + } + + if (!ret) { + /* Mark as relevant and return not done */ + ret = __update_tree(bt, idx, + BMAP_SEEN_SET | BMAP_RELV_SET); + if (ret != -1) + ret = 0; + + } else if (ret == -ENOENT) { + /* Mark as irrelevant and return done */ + ret = __update_tree(bt, idx, BMAP_SEEN_SET); + if (ret != -1) + ret = 1; + + } else { + pr_err("duet: inode relevance undetermined\n"); + return -1; + } + + } else { + /* We know this inode, return 1 if done, or irrelevant */ + ret = ((bits & 0x1) || !(bits & 0x2)) ? 1 : 0; + } + + return ret; +} + +/* Checks if a given inode is done. Skips inode lookup. */ +int bittree_check_inode(struct duet_bittree *bt, struct duet_task *task, + struct inode *inode) +{ + struct duet_uuid uuid; + + uuid.ino = inode->i_ino; + uuid.gen = inode->i_generation; + + return do_bittree_check(bt, uuid, task, inode); +} + +/* Checks if the given entries are done */ +int bittree_check(struct duet_bittree *bt, struct duet_uuid uuid, + struct duet_task *task) +{ + return do_bittree_check(bt, uuid, task, NULL); +} + +/* Mark done bit for given entries */ +int bittree_set(struct duet_bittree *bt, struct duet_uuid uuid) +{ + return __update_tree(bt, UUID_IDX(uuid), BMAP_DONE_SET); +} + +/* Unmark done bit for given entries */ +int bittree_reset(struct duet_bittree *bt, struct duet_uuid uuid) +{ + return __update_tree(bt, UUID_IDX(uuid), BMAP_DONE_RST); +} + +int bittree_print(struct duet_task *task) +{ + struct bmap_rbnode *bnode = NULL; + struct rb_node *node; + unsigned long iflags; + + local_irq_save(iflags); + spin_lock(&task->bittree.lock); + pr_info("duet: Printing task bittree\n"); + node = rb_first(&task->bittree.root); + while (node) { + bnode = rb_entry(node, struct bmap_rbnode, node); + + /* Print node information */ + pr_info("duet: Node key = %llu\n", bnode->idx); + pr_info("duet: Done bits set: %d out of %d\n", + bitmap_weight(bnode->done, BITS_PER_NODE), + BITS_PER_NODE); + pr_info("duet: Relv bits set: %d out of %d\n", + bitmap_weight(bnode->relv, BITS_PER_NODE), + BITS_PER_NODE); + pr_info("duet: Seen bits set: %d out of %d\n", + bitmap_weight(bnode->seen, BITS_PER_NODE), + BITS_PER_NODE); + + node = rb_next(node); + } + spin_unlock(&task->bittree.lock); + local_irq_restore(iflags); + + pr_info("duet: Task #%d bitmap has %d out of %lu bits set\n", + task->id, bitmap_weight(task->bucket_bmap, + duet_env.itm_hash_size), duet_env.itm_hash_size); + + return 0; +} + +void bittree_init(struct duet_bittree *bittree) +{ + spin_lock_init(&bittree->lock); + bittree->root = RB_ROOT; +#ifdef CONFIG_DUET_STATS + bittree->statcur = bittree->statmax = 0; +#endif /* CONFIG_DUET_STATS */ +} + +void bittree_destroy(struct duet_bittree *bittree) +{ + struct rb_node *rbnode; + struct bmap_rbnode *bnode; + + while (!RB_EMPTY_ROOT(&bittree->root)) { + rbnode = rb_first(&bittree->root); + bnode = rb_entry(rbnode, struct bmap_rbnode, node); + bnode_dispose(bnode, rbnode, bittree); + } +} diff --git a/mm/duet/common.h b/mm/duet/common.h new file mode 100644 index 0000000..1dac66b --- /dev/null +++ b/mm/duet/common.h @@ -0,0 +1,211 @@ +/* + * Copyright (C) 2016 George Amvrosiadis. All rights reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License v2 as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + */ +#ifndef _COMMON_H +#define _COMMON_H + +#include <linux/fs.h> +#include <linux/mount.h> +#include <linux/slab.h> +#include <linux/vmalloc.h> +#include <linux/bitmap.h> +#include <linux/rculist.h> +#include <linux/syscalls.h> +#include <linux/duet.h> + +#ifdef DUET_DEBUG +#define duet_dbg(...) pr_info(__VA_ARGS__) +#else +#define duet_dbg(...) +#endif + +/* + * Duet can be state-based, and/or event-based. + * + * Event-based Duet monitors events that occurred on a page, during its + * time in the page cache: ADDED, REMOVED, DIRTY, and FLUSHED. + * + * State-based Duet monitors changes in the page cache since the last time + * a notification was sent to the interested application. Registering for + * EXIST informs the application of page additions or removals from the cache + * (i.e. ADDED and REMOVED events cancel each other out if the application + * hasn't been told in the meantime). Registering for MODIFIED events is a + * similar model, where unreported DIRTY and FLUSHED events cancel each other. + */ +#define DUET_PAGE_ADDED 0x0001 +#define DUET_PAGE_REMOVED 0x0002 +#define DUET_PAGE_DIRTY 0x0004 +#define DUET_PAGE_FLUSHED 0x0008 +#define DUET_PAGE_MODIFIED 0x0010 +#define DUET_PAGE_EXISTS 0x0020 +#define DUET_FD_NONBLOCK 0x0040 + +/* Used only for page state */ +#define DUET_MASK_VALID 0x8000 + +/* Some useful flags for clearing bitmaps */ +#define BMAP_SEEN 0x1 +#define BMAP_RELV 0x2 +#define BMAP_DONE 0x4 + +#define DUET_DEF_NUMTASKS 8 +#define DUET_INODE_FREEING (I_WILL_FREE | I_FREEING | I_CLEAR) + +enum { + DUET_STATUS_OFF = 0, + DUET_STATUS_ON, + DUET_STATUS_INIT, + DUET_STATUS_CLEAN, +}; + +/* + * Item struct returned for processing. + * The UUID currently consists of the inode number, the inode generation + * (to help us identify cases of inode reuse), and the task id. + * For state-based duet, we mark a page if it EXISTS or is MODIFIED. + * For event-based duet, we mark a page added, removed, dirtied, and/or flushed. + * Acceptable event combinations will differ based on the task's subscription. + */ +struct duet_uuid { + unsigned long ino; + __u32 gen; + __u8 tid; +}; + +struct duet_item { + struct duet_uuid uuid; + unsigned long idx; + __u16 state; +}; + +/* + * Red-black bitmap tree node. + * Represents the range starting from idx. For block tasks, only the done + * bitmap is used. For file tasks, the seen and relv (relevant) bitmaps are + * also used. The semantics of different states are listed below, where an + * item can be in the unknown state due to a bitmap reset, or because it hasn't + * been encountered yet. + * - !SEEN && !RELV && !DONE: Item in unknown state + * - !SEEN && !RELV && DONE: Item processed, but in unknown state + * - SEEN && !RELV && !DONE: Item not relevant to the task + * - SEEN && RELV && !DONE: Item is relevant, but not processed + * - SEEN && RELV && DONE: Item is relevant, and has already been processed + */ +struct bmap_rbnode { + __u64 idx; + struct rb_node node; + unsigned long *seen; + unsigned long *relv; + unsigned long *done; +}; + +struct item_hnode { + struct hlist_bl_node node; + struct duet_item item; + __u8 refcount; + __u16 *state; /* One entry per task */ +}; + +struct duet_bittree { + spinlock_t lock; + struct rb_root root; +#ifdef CONFIG_DUET_STATS + __u64 statcur; /* Cur # of BitTree nodes */ + __u64 statmax; /* Max # of BitTree nodes */ +#endif /* CONFIG_DUET_STATS */ +}; + +struct duet_task { + __u8 id; /* Internal task ID */ + + int fd; + struct filename *name; + __u32 evtmask; /* Mask of subscribed events */ + struct path *regpath; /* Registered path */ + char *regpathname; /* Registered path name */ + __u16 regpathlen; /* Length of path name */ + + /* Data structures linking task to framework */ + struct list_head task_list; + wait_queue_head_t cleaner_queue; + atomic_t refcount; + char *pathbuf; /* Buffer for getpath */ + struct duet_bittree bittree; /* Progress bitmap */ + wait_queue_head_t event_queue; /* for read() and poll() */ + + /* Hash table bucket bitmap */ + spinlock_t bbmap_lock; + unsigned long *bucket_bmap; + unsigned long bmap_cursor; +}; + +struct duet_info { + atomic_t status; + __u8 numtasks; /* Number of concurrent tasks */ + + /* + * Access to the task list is synchronized via a mutex. However, any + * operations that are on-going for a task (e.g. fetch) will increase + * its refcount. This refcount is consulted when disposing of the task. + */ + struct mutex task_list_mutex; + struct list_head tasks; + + /* ItemTable -- Global page state hash table */ + struct hlist_bl_head *itm_hash_table; + unsigned long itm_hash_size; + unsigned long itm_hash_shift; + unsigned long itm_hash_mask; +}; + +extern struct duet_info duet_env; + +/* hook.c */ +void duet_hook(__u16 evtcode, void *data); + +/* hash.c */ +int hash_init(void); +int hash_add(struct duet_task *task, struct duet_uuid uuid, + unsigned long idx, __u16 evtmask, short in_scan); +int hash_fetch(struct duet_task *task, struct duet_item *itm); +void hash_print(struct duet_task *task); + +/* task.c -- not in linux/duet.h */ +struct duet_task *duet_find_task(__u8 id); +void duet_task_dispose(struct duet_task *task); + +/* path.c */ +int do_find_path(struct duet_task *task, struct inode *inode, + int getpath, char *buf, int bufsize); +int duet_find_path(struct duet_task *task, struct duet_uuid uuid, + int getpath, char *buf, int bufsize); + +/* bittree.c */ +int bittree_check_inode(struct duet_bittree *bt, struct duet_task *task, + struct inode *inode); +int bittree_check(struct duet_bittree *bt, struct duet_uuid uuid, + struct duet_task *task); +int bittree_set(struct duet_bittree *bt, struct duet_uuid uuid); +int bittree_reset(struct duet_bittree *bt, struct duet_uuid uuid); +int bittree_print(struct duet_task *task); +void bittree_init(struct duet_bittree *bittree); +void bittree_destroy(struct duet_bittree *bittree); + +/* init.c */ +int duet_online(void); + +/* debug.c */ +int duet_print_bmap(__u8 id); +int duet_print_item(__u8 id); +int duet_print_list(struct duet_status_args __user *arg); + +#endif /* _COMMON_H */ diff --git a/mm/duet/debug.c b/mm/duet/debug.c new file mode 100644 index 0000000..77a47b6 --- /dev/null +++ b/mm/duet/debug.c @@ -0,0 +1,98 @@ +/* + * Copyright (C) 2016 George Amvrosiadis. All rights reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License v2 as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + */ + +#include "common.h" +#include "syscall.h" + +/* Do a preorder print of the BitTree */ +int duet_print_bmap(__u8 id) +{ + struct duet_task *task; + + task = duet_find_task(id); + if (!task) + return -ENOENT; + + if (bittree_print(task)) { + pr_err("duet: failed to print BitTree for task #%d\n", + task->id); + return -1; + } + + /* decref and wake up cleaner if needed */ + if (atomic_dec_and_test(&task->refcount)) + wake_up(&task->cleaner_queue); + + return 0; +} + +/* Do a preorder print of the global hash table */ +int duet_print_item(__u8 id) +{ + struct duet_task *task; + + task = duet_find_task(id); + if (!task) + return -ENOENT; + + hash_print(task); + + /* decref and wake up cleaner if needed */ + if (atomic_dec_and_test(&task->refcount)) + wake_up(&task->cleaner_queue); + + return 0; +} + +int duet_print_list(struct duet_status_args __user *arg) +{ + int i = 0; + struct duet_task *cur; + struct duet_status_args argh, *argp; + + /* Copy in task list header (again) */ + if (copy_from_user(&argh, arg, sizeof(argh))) + return -EFAULT; + + /* Copy in entire task list */ + argp = memdup_user(arg, sizeof(*argp) + (argh.numtasks * + sizeof(struct duet_task_attrs))); + if (IS_ERR(argp)) + return PTR_ERR(argp); + + /* Copy the info for the first numtasks */ + mutex_lock(&duet_env.task_list_mutex); + list_for_each_entry(cur, &duet_env.tasks, task_list) { + argp->tasks[i].id = cur->id; + argp->tasks[i].fd = cur->fd; + memcpy(argp->tasks[i].name, cur->name->name, NAME_MAX); + argp->tasks[i].regmask = cur->evtmask; + memcpy(argp->tasks[i].path, cur->regpathname, cur->regpathlen); + i++; + if (i == argp->numtasks) + break; + } + mutex_unlock(&duet_env.task_list_mutex); + + /* Copy out entire task list */ + if (copy_to_user(arg, argp, sizeof(*argp) + (argp->numtasks * + sizeof(struct duet_task_attrs)))) { + pr_err("duet_print_list: failed to copy out list\n"); + kfree(argp); + return -EINVAL; + } + + duet_dbg("duet_print_list: success sending task list\n"); + kfree(argp); + return 0; +} diff --git a/mm/duet/hash.c b/mm/duet/hash.c new file mode 100644 index 0000000..c2644d6 --- /dev/null +++ b/mm/duet/hash.c @@ -0,0 +1,315 @@ +/* + * Copyright (C) 2016 George Amvrosiadis. All rights reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License v2 as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + */ + +#include <linux/hash.h> +#include "common.h" + +#define DUET_NEGATE_EXISTS (DUET_PAGE_ADDED | DUET_PAGE_REMOVED) +#define DUET_NEGATE_MODIFIED (DUET_PAGE_DIRTY | DUET_PAGE_FLUSHED) + +/* + * Page state is retained in a global hash table shared by all tasks. + * Indexing is based on the page's inode number and offset. + */ + +static unsigned long hash(unsigned long ino, unsigned long idx) +{ + unsigned long h; + + h = (idx * ino ^ (GOLDEN_RATIO_PRIME + idx)) / L1_CACHE_BYTES; + h = h ^ ((h ^ GOLDEN_RATIO_PRIME) >> duet_env.itm_hash_shift); + return h & duet_env.itm_hash_mask; +} + +int hash_init(void) +{ + /* Allocate power-of-2 number of buckets */ + duet_env.itm_hash_shift = ilog2(totalram_pages); + duet_env.itm_hash_size = 1 << duet_env.itm_hash_shift; + duet_env.itm_hash_mask = duet_env.itm_hash_size - 1; + + pr_debug("duet: allocated global hash table (%lu buckets)\n", + duet_env.itm_hash_size); + duet_env.itm_hash_table = vmalloc(sizeof(struct hlist_bl_head) * + duet_env.itm_hash_size); + if (!duet_env.itm_hash_table) + return 1; + + memset(duet_env.itm_hash_table, 0, sizeof(struct hlist_bl_head) * + duet_env.itm_hash_size); + return 0; +} + +/* Deallocate a hash table node */ +static void hnode_destroy(struct item_hnode *itnode) +{ + kfree(itnode->state); + kfree(itnode); +} + +/* Allocate and initialize a new hash table node */ +static struct item_hnode *hnode_init(struct duet_uuid uuid, unsigned long idx) +{ + struct item_hnode *itnode = NULL; + + itnode = kzalloc(sizeof(struct item_hnode), GFP_NOWAIT); + if (!itnode) + return NULL; + + itnode->state = kcalloc(duet_env.numtasks, sizeof(*(itnode->state)), + GFP_NOWAIT); + if (!(itnode->state)) { + pr_err("duet: failed to allocate hash node state\n"); + kfree(itnode); + return NULL; + } + + (itnode->item).uuid = uuid; + (itnode->item).idx = idx; + itnode->refcount++; + + return itnode; +} + +/* Add one event into the hash table */ +int hash_add(struct duet_task *task, struct duet_uuid uuid, unsigned long idx, + __u16 evtmask, short in_scan) +{ + __u16 curmask = 0; + short found = 0; + unsigned long bnum, flags; + struct hlist_bl_head *b; + struct hlist_bl_node *n; + struct item_hnode *itnode; + + evtmask &= task->evtmask; + + /* Get the bucket */ + bnum = hash(uuid.ino, idx); + b = duet_env.itm_hash_table + bnum; + local_irq_save(flags); + hlist_bl_lock(b); + + /* Lookup the item in the bucket */ + hlist_bl_for_each_entry(itnode, n, b, node) { + if ((itnode->item).uuid.ino == uuid.ino && + (itnode->item).uuid.gen == uuid.gen && + (itnode->item).idx == idx) { + found = 1; + break; + } + } + + duet_dbg("duet: %s hash node (tid %d, ino%lu, gen%lu, idx%lu)\n", + found ? (in_scan ? "replacing" : "updating") : "inserting", + uuid.tid, uuid.ino, uuid.gen, idx); + + if (found) { + curmask = itnode->state[task->id]; + + /* Only up the refcount if we are adding a new mask */ + if (!(curmask & DUET_MASK_VALID) || in_scan) { + if (!in_scan) + itnode->refcount++; + curmask = evtmask | DUET_MASK_VALID; + goto check_dispose; + } + + curmask |= evtmask | DUET_MASK_VALID; + + /* Negate previous events and remove if needed */ + if ((task->evtmask & DUET_PAGE_EXISTS) && + ((curmask & DUET_NEGATE_EXISTS) == DUET_NEGATE_EXISTS)) + curmask &= ~DUET_NEGATE_EXISTS; + + if ((task->evtmask & DUET_PAGE_MODIFIED) && + ((curmask & DUET_NEGATE_MODIFIED) == DUET_NEGATE_MODIFIED)) + curmask &= ~DUET_NEGATE_MODIFIED; + +check_dispose: + if ((curmask == DUET_MASK_VALID) && (itnode->refcount == 1)) { + if (itnode->refcount != 1) { + itnode->state[task->id] = 0; + } else { + hlist_bl_del(&itnode->node); + hnode_destroy(itnode); + } + + /* Are we still interested in this bucket? */ + hlist_bl_for_each_entry(itnode, n, b, node) { + if (itnode->state[task->id] & DUET_MASK_VALID) { + found = 1; + break; + } + } + + if (!found) + clear_bit(bnum, task->bucket_bmap); + } else { + itnode->state[task->id] = curmask; + + /* Update bitmap */ + set_bit(bnum, task->bucket_bmap); + } + } else if (!found) { + if (!evtmask) + goto done; + + itnode = hnode_init(uuid, idx); + if (!itnode) + return 1; + + itnode->state[task->id] = evtmask | DUET_MASK_VALID; + hlist_bl_add_head(&itnode->node, b); + + /* Update bitmap */ + set_bit(bnum, task->bucket_bmap); + } + +done: + hlist_bl_unlock(b); + local_irq_restore(flags); + return 0; +} + +/* Fetch one item for a given task. Return found (1), empty (0), error (-1) */ +int hash_fetch(struct duet_task *task, struct duet_item *itm) +{ + int found; + unsigned long bnum, flags; + struct hlist_bl_head *b; + struct hlist_bl_node *n; + struct item_hnode *itnode; + + local_irq_save(flags); +again: + spin_lock(&task->bbmap_lock); + bnum = find_next_bit(task->bucket_bmap, duet_env.itm_hash_size, + task->bmap_cursor); + + if (bnum == duet_env.itm_hash_size) { + /* Reached end of bitmap */ + found = 0; + + if (task->bmap_cursor != 0) { + /* Started part way, try again */ + bnum = find_next_bit(task->bucket_bmap, + task->bmap_cursor, 0); + + if (bnum != task->bmap_cursor) + found = 1; + } + + if (!found) { + spin_unlock(&task->bbmap_lock); + local_irq_restore(flags); + return 1; + } + } + + task->bmap_cursor = bnum; + clear_bit(bnum, task->bucket_bmap); + spin_unlock(&task->bbmap_lock); + b = duet_env.itm_hash_table + bnum; + + /* Grab first item from bucket */ + hlist_bl_lock(b); + if (!b->first) { + pr_err("duet: empty hash bucket marked in bitmap\n"); + hlist_bl_unlock(b); + goto again; + } + + found = 0; + hlist_bl_for_each_entry(itnode, n, b, node) { + if (itnode->state[task->id] & DUET_MASK_VALID) { + *itm = itnode->item; + itm->uuid.tid = task->id; + itm->state = itnode->state[task->id] & + (~DUET_MASK_VALID); + + itnode->refcount--; + /* Free or update node */ + if (!itnode->refcount) { + hlist_bl_del(n); + hnode_destroy(itnode); + } else { + itnode->state[task->id] = 0; + } + + found = 1; + break; + } + } + + if (!found) { + hlist_bl_unlock(b); + goto again; + } + + /* Are we still interested in this bucket? */ + found = 0; + hlist_bl_for_each_entry(itnode, n, b, node) { + if (itnode->state[task->id] & DUET_MASK_VALID) { + found = 1; + break; + } + } + + if (found) + set_bit(bnum, task->bucket_bmap); + + hlist_bl_unlock(b); + local_irq_restore(flags); + return 0; +} + +/* Warning: expensive printing function. Use with care. */ +void hash_print(struct duet_task *task) +{ + unsigned long loop, count, start, end, buckets, flags; + unsigned long long nodes, tnodes; + struct hlist_bl_head *b; + struct hlist_bl_node *n; + struct item_hnode *itnode; + + count = duet_env.itm_hash_size / 100; + tnodes = nodes = buckets = start = end = 0; + pr_info("duet: Printing hash table\n"); + for (loop = 0; loop < duet_env.itm_hash_size; loop++) { + if (loop - start >= count) { + pr_info("duet: Buckets %lu - %lu: %llu nodes (task: %llu)\n", + start, end, nodes, tnodes); + start = end = loop; + nodes = tnodes = 0; + } + + /* Count bucket nodes */ + b = duet_env.itm_hash_table + loop; + local_irq_save(flags); + hlist_bl_lock(b); + hlist_bl_for_each_entry(itnode, n, b, node) { + nodes++; + if (itnode->state[task->id] & DUET_MASK_VALID) + tnodes++; + } + hlist_bl_unlock(b); + local_irq_restore(flags); + + end = loop; + } + + if (start != loop - 1) + pr_info("duet: Buckets %lu - %lu: %llu nodes (task: %llu)\n", + start, end, nodes, tnodes); +} diff --git a/mm/duet/hook.c b/mm/duet/hook.c new file mode 100644 index 0000000..3ac89f5 --- /dev/null +++ b/mm/duet/hook.c @@ -0,0 +1,81 @@ +/* + * Copyright (C) 2016 George Amvrosiadis. All rights reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License v2 as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + */ + +#include "common.h" + +/* Handle an event. We're in RCU context so whatever happens, stay awake! */ +void duet_hook(__u16 evtcode, void *data) +{ + struct page *page = NULL; + struct inode *inode = NULL; + struct duet_task *cur; + unsigned long page_idx = 0; + struct duet_uuid uuid; + + /* Duet must be online */ + if (!duet_online()) + return; + + /* Handle page event */ + page = (struct page *)data; + + /* Duet must be online, and the page must belong to a valid mapping */ + if (!page || !page_mapping(page)) { + duet_dbg("duet: dropped event %x due to NULL mapping\n", + evtcode); + return; + } + + inode = page_mapping(page)->host; + page_idx = page->index; + + /* Check that we're referring to an actual inode and get its UUID */ + if (!inode) + return; + + uuid.ino = inode->i_ino; + uuid.gen = inode->i_generation; + + /* Verify that the inode does not belong to a special file */ + if (!S_ISREG(inode->i_mode) && !S_ISDIR(inode->i_mode)) + return; + + if (!inode->i_ino) { + pr_err("duet: inode not initialized\n"); + return; + } + + /* Look for tasks interested in this event type and invoke callbacks */ + rcu_read_lock(); + list_for_each_entry_rcu(cur, &duet_env.tasks, task_list) { + struct super_block *sb = cur->regpath->mnt->mnt_sb; + + /* Verify that the event refers to the fs we're interested in */ + if (sb && sb != inode->i_sb) + continue; + + duet_dbg("duet: rcvd event %x on (ino %lu, gen %lu, idx %lu)\n", + evtcode, uuid.ino, uuid.gen, page_idx); + + /* Use the inode bitmap to filter out event if applicable */ + if (bittree_check_inode(&cur->bittree, cur, inode) == 1) + continue; + + /* Update the hash table */ + if (hash_add(cur, uuid, page_idx, evtcode, 0)) + pr_err("duet: hash table add failed\n"); + + wake_up(&cur->event_queue); + } + rcu_read_unlock(); +} diff --git a/mm/duet/init.c b/mm/duet/init.c new file mode 100644 index 0000000..a9e5ea1 --- /dev/null +++ b/mm/duet/init.c @@ -0,0 +1,172 @@ +/* + * Copyright (C) 2016 George Amvrosiadis. All rights reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License v2 as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + */ + +#include "common.h" +#include "syscall.h" + +struct duet_info duet_env; +duet_hook_t *duet_hook_fp; +EXPORT_SYMBOL(duet_hook_fp); + +int duet_online(void) +{ + return (atomic_read(&duet_env.status) == DUET_STATUS_ON); +} + +int duet_bootstrap(__u16 numtasks) +{ + if (atomic_cmpxchg(&duet_env.status, DUET_STATUS_OFF, DUET_STATUS_INIT) + != DUET_STATUS_OFF) { + pr_err("duet: framework on, bootstrap aborted\n"); + return 1; + } + + duet_env.numtasks = (numtasks ? numtasks : DUET_DEF_NUMTASKS); + + /* Initialize global hash table */ + if (hash_init()) { + pr_err("duet: failed to initialize hash table\n"); + return 1; + } + + /* Initialize task list */ + INIT_LIST_HEAD(&duet_env.tasks); + mutex_init(&duet_env.task_list_mutex); + atomic_set(&duet_env.status, DUET_STATUS_ON); + + rcu_assign_pointer(duet_hook_fp, duet_hook); + synchronize_rcu(); + return 0; +} + +int duet_shutdown(void) +{ + struct duet_task *task; + + if (atomic_cmpxchg(&duet_env.status, DUET_STATUS_ON, DUET_STATUS_CLEAN) + != DUET_STATUS_ON) { + pr_err("duet: framework off, shutdown aborted\n"); + return 1; + } + + rcu_assign_pointer(duet_hook_fp, NULL); + synchronize_rcu(); + + /* Remove all tasks */ + mutex_lock(&duet_env.task_list_mutex); + while (!list_empty(&duet_env.tasks)) { + task = list_entry_rcu(duet_env.tasks.next, struct duet_task, + task_list); + list_del_rcu(&task->task_list); + mutex_unlock(&duet_env.task_list_mutex); + + /* Make sure everyone's let go before we free it */ + synchronize_rcu(); + wait_event(task->cleaner_queue, + atomic_read(&task->refcount) == 0); + duet_task_dispose(task); + + mutex_lock(&duet_env.task_list_mutex); + } + mutex_unlock(&duet_env.task_list_mutex); + + /* Destroy global hash table */ + vfree((void *)duet_env.itm_hash_table); + + INIT_LIST_HEAD(&duet_env.tasks); + mutex_destroy(&duet_env.task_list_mutex); + atomic_set(&duet_env.status, DUET_STATUS_OFF); + return 0; +} + +SYSCALL_DEFINE2(duet_status, u16, flags, struct duet_status_args __user *, arg) +{ + int ret = 0; + struct duet_status_args *sa; + + if (!capable(CAP_SYS_ADMIN)) + return -EPERM; + + sa = memdup_user(arg, sizeof(*sa)); + if (IS_ERR(sa)) + return PTR_ERR(sa); + + /* For now, we only support one struct size */ + if (sa->size != sizeof(*sa)) { + pr_err("duet_status: invalid args struct size (%u)\n", + sa->size); + ret = -EINVAL; + goto done; + } + + /* If we're cleaning up, only allow ops that affect Duet status */ + if (atomic_read(&duet_env.status) != DUET_STATUS_ON && !(flags & + (DUET_STATUS_START | DUET_STATUS_STOP | DUET_STATUS_REPORT))) { + pr_err("duet_status: ops rejected during shutdown\n"); + ret = -EINVAL; + goto done; + } + + switch (flags) { + case DUET_STATUS_START: + ret = duet_bootstrap(sa->maxtasks); + + if (ret) + pr_err("duet: failed to enable framework\n"); + else + pr_info("duet: framework enabled\n"); + + break; + + case DUET_STATUS_STOP: + ret = duet_shutdown(); + + if (ret) + pr_err("duet: failed to disable framework\n"); + else + pr_info("duet: framework disabled\n"); + + break; + + case DUET_STATUS_REPORT: + ret = duet_online(); + break; + + case DUET_STATUS_PRINT_BMAP: + ret = duet_print_bmap(sa->id); + break; + + case DUET_STATUS_PRINT_ITEM: + ret = duet_print_item(sa->id); + break; + + case DUET_STATUS_PRINT_LIST: + ret = duet_print_list(arg); + goto done; + + default: + pr_info("duet_status: invalid flags\n"); + ret = -EINVAL; + goto done; + } + + if (copy_to_user(arg, sa, sizeof(*sa))) { + pr_err("duet_status: copy_to_user failed\n"); + ret = -EINVAL; + goto done; + } + +done: + kfree(sa); + return ret; +} diff --git a/mm/duet/path.c b/mm/duet/path.c new file mode 100644 index 0000000..103ab42 --- /dev/null +++ b/mm/duet/path.c @@ -0,0 +1,184 @@ +/* + * Copyright (C) 2016 George Amvrosiadis. All rights reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License v2 as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + */ + +#include "common.h" +#include "syscall.h" + +/* Scan through the page cache for a given inode */ +static int find_get_inode(struct super_block *sb, struct duet_uuid c_uuid, + struct inode **c_inode) +{ + struct inode *inode = NULL; + + *c_inode = NULL; + spin_lock(&sb->s_inode_list_lock); + list_for_each_entry(inode, &sb->s_inodes, i_sb_list) { + spin_lock(&inode->i_lock); + if (!*c_inode && inode->i_ino == c_uuid.ino && + inode->i_generation == c_uuid.gen && + !(inode->i_state & DUET_INODE_FREEING)) { + atomic_inc(&inode->i_count); + *c_inode = inode; + spin_unlock(&inode->i_lock); + spin_unlock(&sb->s_inode_list_lock); + return 0; + } + spin_unlock(&inode->i_lock); + } + spin_unlock(&sb->s_inode_list_lock); + + /* We shouldn't get here unless we failed */ + return 1; +} + +int do_find_path(struct duet_task *task, struct inode *inode, int getpath, + char *buf, int bufsize) +{ + int len; + char *p; + struct path path; + struct dentry *alias, *i_dentry = NULL; + + if (!task) { + pr_err("do_find_path: invalid task\n"); + return -EINVAL; + } + + if (getpath) + buf[0] = '\0'; + + /* Get the path for at least one alias of the inode */ + if (hlist_empty(&inode->i_dentry)) + return -ENOENT; + + hlist_for_each_entry(alias, &inode->i_dentry, d_u.d_alias) { + if (IS_ROOT(alias) && (alias->d_flags & DCACHE_DISCONNECTED)) + continue; + + i_dentry = alias; + + /* Now get the path */ + len = PATH_MAX; + memset(task->pathbuf, 0, len); + path.mnt = task->regpath->mnt; + path.dentry = i_dentry; + + p = d_path(&path, task->pathbuf, len); + if (IS_ERR(p)) { + pr_err("do_find_path: d_path failed\n"); + continue; + } else if (!p) { + duet_dbg("do_find_path: dentry not found\n"); + continue; + } + + /* Is this path of interest? */ + if (memcmp(task->regpathname, p, task->regpathlen - 1)) { + duet_dbg("do_find_path: no common ancestor\n"); + continue; + } + + /* Got one. If it fits, return it */ + if (getpath && (bufsize < len - (p - task->pathbuf))) + return -ENOMEM; + + duet_dbg("do_find_path: got %s\n", p); + if (getpath) + memcpy(buf, p, len - (p - task->pathbuf)); + + return 0; + } + + /* We only get here if we got nothing */ + return -ENOENT; +} + +int duet_find_path(struct duet_task *task, struct duet_uuid uuid, int getpath, + char *buf, int bufsize) +{ + int ret = 0; + struct inode *ino; + + if (!task) { + pr_err("duet_find_path: invalid task\n"); + return -EINVAL; + } + + /* First, we need to find struct inode for child and parent */ + if (find_get_inode(task->regpath->mnt->mnt_sb, uuid, &ino)) { + duet_dbg("duet_find_path: child inode not found\n"); + return -ENOENT; + } + + ret = do_find_path(task, ino, getpath, buf, bufsize); + + iput(ino); + return ret; +} + +SYSCALL_DEFINE3(duet_get_path, struct duet_uuid_arg __user *, uuid, + char __user *, pathbuf, int, pathbufsize) +{ + int ret = 0; + struct duet_uuid_arg *ua; + struct duet_task *task; + char *buf; + + if (!capable(CAP_SYS_ADMIN)) + return -EPERM; + + if (!duet_online()) + return -ESRCH; + + /* Do some basic sanity checking */ + if (!uuid || pathbufsize <= 0) + return -EINVAL; + + buf = kcalloc(pathbufsize, sizeof(char), GFP_KERNEL); + if (!buf) + return -ENOMEM; + + ua = memdup_user(uuid, sizeof(*uuid)); + if (IS_ERR(ua)) { + kfree(buf); + return PTR_ERR(ua); + } + + /* For now, we only support one struct size */ + if (ua->size != sizeof(*ua)) { + pr_err("duet_get_path: invalid args struct size (%u)\n", + ua->size); + ret = -EINVAL; + goto done; + } + + task = duet_find_task(ua->uuid.tid); + if (!task) { + ret = -ENOENT; + goto done; + } + + ret = duet_find_path(task, ua->uuid, 1, buf, pathbufsize); + + if (!ret && copy_to_user(pathbuf, buf, pathbufsize)) + ret = -EFAULT; + + /* decref and wake up cleaner if needed */ + if (atomic_dec_and_test(&task->refcount)) + wake_up(&task->cleaner_queue); + +done: + kfree(ua); + kfree(buf); + return ret; +} diff --git a/mm/duet/syscall.h b/mm/duet/syscall.h new file mode 100644 index 0000000..1bc6830 --- /dev/null +++ b/mm/duet/syscall.h @@ -0,0 +1,61 @@ +/* + * Copyright (C) 2016 George Amvrosiadis. All rights reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License v2 as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + */ + +#include "common.h" + +/* Status syscall flags */ +#define DUET_STATUS_START 0x0001 +#define DUET_STATUS_STOP 0x0002 +#define DUET_STATUS_REPORT 0x0004 +#define DUET_STATUS_PRINT_BMAP 0x0008 +#define DUET_STATUS_PRINT_ITEM 0x0010 +#define DUET_STATUS_PRINT_LIST 0x0020 + +struct duet_task_attrs { + __u8 id; + int fd; + char name[NAME_MAX]; + __u32 regmask; + char path[PATH_MAX]; +}; + +struct duet_status_args { + __u32 size; /* in */ + union { + /* DUET_START args */ + struct { + __u16 maxtasks; /* in */ + }; + + /* DUET_PRINT_BIT, DUET_PRINT_ITEM args */ + struct { + __u8 id; /* in */ + }; + + /* DUET_PRINT_LIST args */ + struct { + __u16 numtasks; /* out */ + struct duet_task_attrs tasks[0]; /* out */ + }; + }; +}; + +/* Bmap syscall flags */ +#define DUET_BMAP_SET 0x0001 +#define DUET_BMAP_RESET 0x0002 +#define DUET_BMAP_CHECK 0x0004 + +struct duet_uuid_arg { + __u32 size; + struct duet_uuid uuid; +}; diff --git a/mm/duet/task.c b/mm/duet/task.c new file mode 100644 index 0000000..c91fad3 --- /dev/null +++ b/mm/duet/task.c @@ -0,0 +1,584 @@ +/* + * Copyright (C) 2016 George Amvrosiadis. All rights reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License v2 as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + */ + +#include <linux/namei.h> +#include <linux/anon_inodes.h> +#include "common.h" +#include "syscall.h" + +/* + * To synchronize access to the task list and structures without compromising + * scalability, a two-level approach is used. At the task list level, which is + * rarely updated, RCU is used. For the task structures, we use traditional + * reference counting. The two techniques are interweaved to achieve overall + * consistency. + */ + +static unsigned int duet_poll(struct file *file, poll_table *wait) +{ + __u8 *tid = file->private_data; + struct duet_task *task; + int ret = 0; + + task = duet_find_task(*tid); + if (!task) { + pr_err("duet_poll: task not found\n"); + return ret; + } + + poll_wait(file, &task->event_queue, wait); + if (bitmap_weight(task->bucket_bmap, duet_env.itm_hash_size)) + ret = POLLIN | POLLRDNORM; + + return ret; +} + +/* + * Copy an item to user space, returning how much we copied. + * + * We already checked that the event size is smaller than the + * buffer we had in duet_read() below. + */ +static ssize_t copy_item_to_user(struct duet_task *task, + struct duet_item *item, + char __user *buf) +{ + size_t item_size = sizeof(struct duet_item); + + /* Send the item */ + if (copy_to_user(buf, item, item_size)) + return -EFAULT; + + buf += item_size; + + duet_dbg("duet_read: sending (ino%lu, gen%u, idx%lu, %x)\n", + item->uuid.ino, item->uuid.gen, item->idx, item->state); + + return item_size; +} + +/* + * Sends out duet items. The number of bytes returned corresponds to the number + * of sizeof(struct duet_item) items fetched. Items are checked against the + * bitmap, and discarded if they have been marked; this can happen because an + * insertion can occur between the last read and the last bitmap set operation. + */ +static ssize_t duet_read(struct file *file, char __user *buf, + size_t count, loff_t *pos) +{ + struct duet_task *task; + struct duet_item item; + char __user *start; + int ret, err; + __u8 *tid; + DEFINE_WAIT_FUNC(wait, woken_wake_function); + + start = buf; + tid = file->private_data; + + task = duet_find_task(*tid); + if (!task) + return -ENOENT; + + add_wait_queue(&task->event_queue, &wait); + while (1) { + /* Fetch an item only if there's space to store it */ + if (sizeof(struct duet_item) > count) + err = -EINVAL; + else + err = hash_fetch(task, &item); + + if (!err) { + ret = copy_item_to_user(task, &item, buf); + if (ret < 0) + break; + buf += ret; + count -= ret; + continue; + } + + ret = -EAGAIN; + if (file->f_flags & O_NONBLOCK) + break; + ret = -ERESTARTSYS; + if (signal_pending(current)) + break; + + if (start != buf) + break; + + wait_woken(&wait, TASK_INTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT); + } + remove_wait_queue(&task->event_queue, &wait); + + if (start != buf && ret != -EFAULT) + ret = buf - start; + + /* Decref and wake up cleaner if needed */ + if (atomic_dec_and_test(&task->refcount)) + wake_up(&task->cleaner_queue); + + return ret; +} + +/* + * Properly dismantle and dispose of a task struct. + * At this point we've guaranteed that noone else is accessing the + * task struct, so we don't need any locks + */ +void duet_task_dispose(struct duet_task *task) +{ + int ret = 0; + struct duet_item itm; + + /* Dispose of the bitmap tree */ + bittree_destroy(&task->bittree); + + /* Dispose of hash table entries, bucket bitmap */ + while (!ret) + ret = hash_fetch(task, &itm); + kfree(task->bucket_bmap); + + putname(task->name); + path_put(task->regpath); + kfree(task->regpath); + kfree(task->regpathname); + kfree(task->pathbuf); + kfree(task); +} + +static int duet_release(struct inode *ignored, struct file *file) +{ + __u8 *tid = file->private_data; + struct duet_task *cur; + + /* Find the task in the list, then dispose of it */ + mutex_lock(&duet_env.task_list_mutex); + list_for_each_entry_rcu(cur, &duet_env.tasks, task_list) { + if (cur->id == *tid) { +#ifdef CONFIG_DUET_STATS + hash_print(cur); + bittree_print(cur); +#endif /* CONFIG_DUET_STATS */ + list_del_rcu(&cur->task_list); + mutex_unlock(&duet_env.task_list_mutex); + + /* Wait until everyone's done with it */ + synchronize_rcu(); + wait_event(cur->cleaner_queue, + atomic_read(&cur->refcount) == 0); + + pr_info("duet: deregistered task %d\n", cur->id); + + duet_task_dispose(cur); + kfree(tid); + return 0; + } + } + mutex_unlock(&duet_env.task_list_mutex); + + return -ENOENT; +} + +static const struct file_operations duet_fops = { + .show_fdinfo = NULL, + .poll = duet_poll, + .read = duet_read, + .fasync = NULL, + .release = duet_release, + .unlocked_ioctl = NULL, + .compat_ioctl = NULL, + .llseek = noop_llseek, +}; + +static int process_inode(struct duet_task *task, struct inode *inode) +{ + struct radix_tree_iter iter; + struct duet_uuid uuid; + void **slot; + __u16 state; + + /* Use the inode bitmap to decide whether to skip inode */ + if (bittree_check_inode(&task->bittree, task, inode) == 1) + return 0; + + /* Go through all pages of this inode */ + rcu_read_lock(); + radix_tree_for_each_slot(slot, &inode->i_mapping->page_tree, &iter, 0) { + struct page *page; + + page = radix_tree_deref_slot(slot); + if (unlikely(!page)) + continue; + + if (radix_tree_exception(page)) { + if (radix_tree_deref_retry(page)) { + slot = radix_tree_iter_retry(&iter); + continue; + } + /* + * Shadow entry of recently evicted page, or swap entry + * from shmem/tmpfs. Skip over it. + */ + continue; + } + + state = DUET_PAGE_ADDED; + if (PageDirty(page)) + state |= DUET_PAGE_DIRTY; + uuid.ino = inode->i_ino; + uuid.gen = inode->i_generation; + hash_add(task, uuid, page->index, state, 1); + } + rcu_read_unlock(); + + return 0; +} + +/* Scan through the page cache for events of interest to the task */ +static int scan_page_cache(struct duet_task *task) +{ + struct inode *inode, *prev = NULL; + struct super_block *sb = task->regpath->mnt->mnt_sb; + + pr_info("duet: page cache scan started\n"); + + spin_lock(&sb->s_inode_list_lock); + list_for_each_entry(inode, &sb->s_inodes, i_sb_list) { + struct address_space *mapping = inode->i_mapping; + + spin_lock(&inode->i_lock); + if (inode->i_state & DUET_INODE_FREEING || + mapping->nrpages == 0) { + spin_unlock(&inode->i_lock); + continue; + } + atomic_inc(&inode->i_count); + spin_unlock(&inode->i_lock); + spin_unlock(&sb->s_inode_list_lock); + + /* + * We are holding a reference to inode so it won't be removed + * from s_inodes list while we don't hold the s_inode_list_lock. + * We cannot iput the inode now, though, as we may be holding + * the last reference. We will iput it after the iteration is + * done. + */ + + iput(prev); + prev = inode; + + process_inode(task, inode); + + spin_lock(&sb->s_inode_list_lock); + } + spin_unlock(&sb->s_inode_list_lock); + iput(prev); + + pr_info("duet: page cache scan finished\n"); + + return 0; +} + +/* Find task and increment its refcount */ +struct duet_task *duet_find_task(__u8 id) +{ + struct duet_task *cur, *task = NULL; + + rcu_read_lock(); + list_for_each_entry_rcu(cur, &duet_env.tasks, task_list) { + if (cur->id == id) { + task = cur; + atomic_inc(&task->refcount); + break; + } + } + rcu_read_unlock(); + + return task; +} + +/* Allocate and initialize a task struct */ +static int duet_task_init(struct duet_task **task, struct filename *name, + __u32 regmask, struct path *path) +{ + int len; + char *p; + u32 evtmask = regmask; + + /* Do some sanity checking on event mask. */ + if (evtmask & DUET_PAGE_EXISTS) { + if (evtmask & (DUET_PAGE_ADDED | DUET_PAGE_REMOVED)) { + pr_debug("duet_task_init: invalid regmask\n"); + return -EINVAL; + } + evtmask |= (DUET_PAGE_ADDED | DUET_PAGE_REMOVED); + } + + if (evtmask & DUET_PAGE_MODIFIED) { + if (evtmask & (DUET_PAGE_DIRTY | DUET_PAGE_FLUSHED)) { + pr_debug("duet_task_init: invalid regmask\n"); + goto err; + } + evtmask |= (DUET_PAGE_DIRTY | DUET_PAGE_FLUSHED); + } + + /* Allocate task info struct */ + *task = kzalloc(sizeof(**task), GFP_KERNEL); + if (!(*task)) + return -ENOMEM; + + /* Allocate temporary space for getpath file paths */ + (*task)->pathbuf = kzalloc(PATH_MAX, GFP_KERNEL); + if (!(*task)->pathbuf) { + pr_err("duet_task_init: buffer allocation failed\n"); + kfree(*task); + return -ENOMEM; + } + + /* Find and store registered dir path */ + (*task)->regpathname = kzalloc(PATH_MAX, GFP_KERNEL); + if (!(*task)->regpathname) { + pr_err("duet_task_init: path allocation failed\n"); + kfree((*task)->pathbuf); + kfree(*task); + return -ENOMEM; + } + + /* Populate registered dir path buffer */ + len = PATH_MAX; + p = d_path(path, (*task)->pathbuf, len); + if (IS_ERR(p)) { + pr_err("duet_task_init: path registration failed\n"); + goto err; + } else if (!p) { + pr_err("duet_task_init: (null) registered path\n"); + goto err; + } + + (*task)->regpathlen = len - (p - (*task)->pathbuf); + memcpy((*task)->regpathname, p, (*task)->regpathlen); + + (*task)->id = 1; + (*task)->name = name; + (*task)->regpath = path; + (*task)->evtmask = (regmask & 0xffff); + atomic_set(&(*task)->refcount, 0); + INIT_LIST_HEAD(&(*task)->task_list); + init_waitqueue_head(&(*task)->cleaner_queue); + init_waitqueue_head(&(*task)->event_queue); + bittree_init(&(*task)->bittree); + + /* Initialize hash table bitmap */ + (*task)->bmap_cursor = 0; + spin_lock_init(&(*task)->bbmap_lock); + (*task)->bucket_bmap = kzalloc(sizeof(unsigned long) * + BITS_TO_LONGS(duet_env.itm_hash_size), GFP_KERNEL); + if (!(*task)->bucket_bmap) { + pr_err("duet_task_init: hash bitmap alloc failed\n"); + kfree((*task)->regpathname); + kfree((*task)->pathbuf); + kfree(*task); + return -ENOMEM; + } + + return 0; +err: + pr_err("duet_task_init: error registering task\n"); + kfree((*task)->regpathname); + kfree((*task)->pathbuf); + kfree(*task); + return -EINVAL; +} + +/* Register the task with Duet */ +int duet_register_task(struct filename *name, __u32 regmask, struct path *path) +{ + int ret; + __u8 *tid; + struct duet_task *cur, *task = NULL; + struct list_head *last; + + /* Do some sanity checking on the parameters passed */ + if (!path || !regmask) + return -EINVAL; + + if (!path->dentry || !path->dentry->d_inode) { + pr_err("duet_register_task: invalid path\n"); + return -EINVAL; + } + + if (!S_ISDIR(path->dentry->d_inode->i_mode)) { + pr_err("duet_register_task: path is not a dir\n"); + return -EINVAL; + } + + ret = duet_task_init(&task, name, regmask, path); + if (ret) { + pr_err("duet_register_task: initialization failed\n"); + return ret; + } + + /* Now get an anonymous inode to use for communication with Duet */ + tid = kzalloc(sizeof(__u8), GFP_KERNEL); + if (!tid) { + duet_task_dispose(task); + return -ENOMEM; + } + + ret = anon_inode_getfd("duet", &duet_fops, tid, + O_RDONLY | ((regmask & DUET_FD_NONBLOCK) ? O_NONBLOCK : 0)); + if (ret < 0) { + duet_task_dispose(task); + kfree(tid); + return ret; + } + + task->fd = ret; + + /* Find a free task id for the new task. Tasks are sorted by id. */ + mutex_lock(&duet_env.task_list_mutex); + last = &duet_env.tasks; + list_for_each_entry_rcu(cur, &duet_env.tasks, task_list) { + if (cur->id == task->id) + (task->id)++; + else if (cur->id > task->id) + break; + + last = &cur->task_list; + } + list_add_rcu(&task->task_list, last); + mutex_unlock(&duet_env.task_list_mutex); + + *tid = task->id; + + /* Before we return, scan the page cache for pages of interest */ + scan_page_cache(task); + + pr_info("duet: task %d (fd %d) registered %s(%d) with mask %x\n", + task->id, task->fd, task->regpathname, task->regpathlen, + task->evtmask); + + return ret; +} + +SYSCALL_DEFINE3(duet_init, const char __user *, taskname, u32, regmask, + const char __user *, pathname) +{ + int ret; + unsigned int lookup_flags = LOOKUP_DIRECTORY; + struct filename *name = NULL; + struct path *path = NULL; + + if (!capable(CAP_SYS_ADMIN)) + return -EPERM; + + if (!duet_online()) + return -ESRCH; + + /* Do some basic sanity checking */ + if (!pathname || !regmask) + return -EINVAL; + + if (taskname) { + name = getname(taskname); + if (IS_ERR(name)) + return PTR_ERR(name); + } + + path = kzalloc(sizeof(struct path), GFP_KERNEL); + if (!path) { + putname(name); + return -ENOMEM; + } + + ret = user_path_at(AT_FDCWD, pathname, lookup_flags, path); + if (ret) { + pr_err("duet_init: user_path_at failed\n"); + goto err; + } + + /* Register the task with the framework */ + ret = duet_register_task(name, regmask, path); + if (ret < 0) { + pr_err("duet_init: task registration failed\n"); + goto err; + } + + return ret; + +err: + putname(name); + path_put(path); + kfree(path); + return ret; +} + +SYSCALL_DEFINE2(duet_bmap, u16, flags, struct duet_uuid_arg __user *, arg) +{ + int ret = 0; + struct duet_uuid_arg *ua; + struct duet_task *task; + + if (!capable(CAP_SYS_ADMIN)) + return -EPERM; + + if (!duet_online()) + return -ESRCH; + + /* Do some basic sanity checking */ + if (!arg) + return -EINVAL; + + ua = memdup_user(arg, sizeof(*arg)); + if (IS_ERR(ua)) + return PTR_ERR(ua); + + /* For now, we only support one struct size */ + if (ua->size != sizeof(*ua)) { + pr_err("duet_bmap: invalid args struct size (%u)\n", ua->size); + ret = -EINVAL; + goto done; + } + + task = duet_find_task(ua->uuid.tid); + if (!task) + return -ENOENT; + + switch (flags) { + case DUET_BMAP_SET: + ret = bittree_set(&task->bittree, ua->uuid); + break; + + case DUET_BMAP_RESET: + ret = bittree_reset(&task->bittree, ua->uuid); + break; + + case DUET_BMAP_CHECK: + ret = bittree_check(&task->bittree, ua->uuid, task); + break; + + default: + pr_err("duet_bmap: invalid flags\n"); + ret = -EINVAL; + break; + } + + /* decreg and wake up cleaner if needed */ + if (atomic_dec_and_test(&task->refcount)) + wake_up(&task->cleaner_queue); + +done: + kfree(ua); + return ret; +} -- 2.7.4
