graphene/LibOS/shim/src/fs/shim_dcache.c

/* -*- mode:c; c-file-style:"k&r"; c-basic-offset: 4; tab-width:4; indent-tabs-mode:nil; mode:auto-fill; fill-column:78; -*- */
/* vim: set ts=4 sw=4 et tw=78 fo=cqt wm=0: */

/* Copyright (C) 2014 OSCAR lab, Stony Brook University
   This file is part of Graphene Library OS.

   Graphene Library OS is free software: you can redistribute it and/or
   modify it under the terms of the GNU General Public License
   as published by the Free Software Foundation, either version 3 of the
   License, or (at your option) any later version.

   Graphene Library OS 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.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */

/*
 * shim_dcache.c
 *
 * This file contains codes for maintaining directory cache in library OS.
 * The source codes are imported from Linux kernel, but simplified according
 * to the characteristic of library OS.
 */

#include <shim_types.h>
#include <shim_internal.h>
#include <shim_handle.h>
#include <shim_fs.h>
#include <shim_checkpoint.h>

#include <linux_list.h>

static LIST_HEAD(dcache_list);
static LIST_HEAD(unused);
static LIST_HEAD(persistent);

static struct hlist_head dcache_htable[DCACHE_HASH_SIZE] = { HLIST_HEAD_INIT };

LOCKTYPE dcache_lock;

struct shim_dcache_stats {
    long memsize;
    long nentries;
};

static struct shim_dcache_stats dcache_stats;

long get_dcache_stats (const char * name)
{
    if (memcmp(name, "memsize", 8) == 0)
        return dcache_stats.memsize;

    if (memcmp(name, "nentries", 9) == 0)
        return dcache_stats.nentries;

    return 0;
}

#define DCACHE_MGR_ALLOC    64
#define PAGE_SIZE           allocsize

#define OBJ_TYPE struct shim_dentry
#include <memmgr.h>

static MEM_MGR dentry_mgr = NULL;

struct shim_dentry * dentry_root = NULL;

//#define DEBUG_DCACHE
//#define DEBUG_REF

static struct shim_dentry * alloc_dentry (void)
{
    struct shim_dentry * dent =
                get_mem_obj_from_mgr_enlarge(dentry_mgr,
                                             size_align_up(DCACHE_MGR_ALLOC));
    if (!dent)
        return NULL;

    dcache_stats.memsize += sizeof(struct shim_dentry);
    dcache_stats.nentries++;

    memset(dent, 0, sizeof(struct shim_dentry));

    dent->mode = NO_MODE;

    INIT_HLIST_NODE(&dent->hlist);
    INIT_LIST_HEAD(&dent->list);
    INIT_LIST_HEAD(&dent->children);
    INIT_LIST_HEAD(&dent->siblings);
    INIT_LIST_HEAD(&dent->alias);

    return dent;
}

DEFINE_PROFILE_CATAGORY(dcache, );
DEFINE_PROFILE_INTERVAL(total_init_dcache, dcache);
DEFINE_PROFILE_CATAGORY(init_dcache, dcache);
DEFINE_PROFILE_INTERVAL(dcache_init_memory, init_dcache);
DEFINE_PROFILE_INTERVAL(dcache_init_hash_table, init_dcache);
DEFINE_PROFILE_INTERVAL(dcache_init_lock, init_dcache);
DEFINE_PROFILE_INTERVAL(dcache_init_root_entry, init_dcache);

int init_dcache (void)
{
#ifdef PROFILE
    unsigned long begin_time = GET_PROFILE_INTERVAL();
    BEGIN_PROFILE_INTERVAL_SET(begin_time);
#endif

    dentry_mgr = create_mem_mgr(init_align_up(DCACHE_MGR_ALLOC));
    SAVE_PROFILE_INTERVAL(dcache_init_memory);

    for (int i = 0 ; i < DCACHE_HASH_SIZE ; i++)
        INIT_HLIST_HEAD(&dcache_htable[i]);
    SAVE_PROFILE_INTERVAL(dcache_init_hash_table);

    create_lock(dcache_lock);
    SAVE_PROFILE_INTERVAL(dcache_init_lock);

    dentry_root = alloc_dentry();

    qstrsetstr(&dentry_root->rel_path, "", 0);
    qstrsetstr(&dentry_root->name,     "", 0);

    get_dentry(dentry_root);
    SAVE_PROFILE_INTERVAL(dcache_init_root_entry);

    SAVE_PROFILE_INTERVAL_SINCE(total_init_dcache, begin_time);
    return 0;
}

int reinit_dcache (void)
{
    create_lock(dcache_lock);

    return 0;
}

/* remove from the hash table, so that a lookup will fail. */
void __del_dcache (struct shim_dentry * dent)
{
    if (!(dent->state & DENTRY_HASHED))
        return;

    dent->state &= ~DENTRY_HASHED;
    hlist_del_init(&dent->hlist);

#ifdef DEBUG_DCACHE
    debug("del dcache %p(%s/%s) (mount = %p)\n",
          dent, dent->fs ? qstrgetstr(&dent->fs->path) : "",
          qstrgetstr(&dent->rel_path), dent->fs);
#endif
}

static int __internal_put_dentry (struct shim_dentry * dent);

void del_dcache (struct shim_dentry * dent)
{
    lock(dcache_lock);
    __del_dcache(dent);
    unlock(dcache_lock);
}

static inline void __dput_dentry (struct shim_dentry * dent)
{
    while (1) {
        /* if the dentry is never in the hash table, we are happy to
           drop it */
        if (!(dent->state & DENTRY_HASHED))
            goto kill;

        /* move the node to unused list unless it is persistent */
        if (!(dent->state & DENTRY_PERSIST)) {
            dent->state |= DENTRY_RECENTLY;
            list_del(&dent->list);
            INIT_LIST_HEAD(&dent->list);
            list_add(&dent->list, &unused);
        }

        /* we don't delete the dentry from dcache because it might
           be acquired and used again, unless it gets recycled due
           to memory pressure */
        break;

kill:   {
            if (dent->fs && dent->fs->d_ops && dent->fs->d_ops->dput)
                dent->fs->d_ops->dput(dent);

            struct shim_dentry * parent = dent->parent;

            if (!parent)
                break;

            list_del(&dent->siblings); /* remove from parent's list of children */
            dent->parent = NULL;
            dent = parent;

            if (__internal_put_dentry(dent))
                break;
        }
    }
}

static int __internal_put_dentry (struct shim_dentry * dent)
{
    int count = REF_DEC(dent->ref_count);

#ifdef DEBUG_REF
    debug("put dentry %p(%s/%s) (ref_count = %d)\n", dent,
          dent->fs ?
          qstrgetstr(&dent->fs->path) : "",
          qstrgetstr(&dent->rel_path), count);
#endif

    return count;
}

void get_dentry (struct shim_dentry * dent)
{
#ifdef DEBUG_REF
    int count = REF_INC(dent->ref_count);

    debug("get dentry %p(%s/%s) (ref_count = %d)\n", dent,
          dent->fs ?
          qstrgetstr(&dent->fs->path) : "",
          qstrgetstr(&dent->rel_path), count);
#else
    REF_INC(dent->ref_count);
#endif
}

void put_dentry (struct shim_dentry * dent)
{
    if (__internal_put_dentry(dent))
        return;

    if (locked(dcache_lock)) {
        __dput_dentry(dent);
    } else {
        lock(dcache_lock);
        __dput_dentry(dent);
        unlock(dcache_lock);
    }
}

struct shim_dentry * get_new_dentry (struct shim_dentry * parent,
                                     const char * name, int namelen)
{
    struct shim_dentry * dent = alloc_dentry();

    if (!dent)
        return NULL;

    REF_SET(dent->ref_count, 0);
    qstrsetstr(&dent->name, name, namelen);

    if (!parent) {
        qstrsetstr(&dent->rel_path, name, namelen);
        return dent;
    }

    if (!qstrempty(&parent->rel_path)) {
        const char * strs[] = { qstrgetstr(&parent->rel_path), "/", name };
        size_t lens[] = { parent->rel_path.len, 1, namelen };
        qstrsetstrs(&dent->rel_path, 3, strs, lens);
    } else
        qstrsetstr(&dent->rel_path, name, namelen);

    return dent;
}

void __set_parent_dentry (struct shim_dentry * child,
                          struct shim_dentry * parent)
{
    if (child->parent == parent)
        return;

    assert(!child->parent);
    get_dentry(parent);
    list_add_tail(&child->siblings, &parent->children);
    child->parent = parent;
    parent->nchildren++;
}

void __unset_parent_dentry (struct shim_dentry * child,
                            struct shim_dentry * parent)
{
    if (child->parent != parent)
        return;

    assert(child->parent);
    child->parent = NULL;
    list_del_init(&child->siblings);
    parent->nchildren--;
    put_dentry(parent);
}

static inline
HASHTYPE hash_dentry (struct shim_dentry * start, const char * path, int len)
{
    return rehash_path(start ? start->rel_path.hash : 0,
                       path, len, NULL);
}

void __add_dcache (struct shim_dentry * dent, HASHTYPE * hashptr)
{
    struct hlist_head * head;

    if (hashptr) {
        dent->rel_path.hash = *hashptr;
        goto add_hash;
    }

    if (!dent->parent) {
        dent->rel_path.hash = dent->fs ? dent->fs->path.hash : 0;
        goto add_hash;
    }

    dent->rel_path.hash = hash_dentry(dent->parent, dentry_get_name(dent),
                                      dent->name.len);

add_hash:
    head = &dcache_htable[DCACHE_HASH(dent->rel_path.hash)];
    hlist_add_head(&dent->hlist, head);
    dent->state |= DENTRY_HASHED;

#ifdef DEBUG_DCACHE
    debug("add dcache %p(%s/%s) (mount = %p)\n",
          dent, dent->fs ? qstrgetstr(&dent->fs->path) : "",
          qstrgetstr(&dent->rel_path), dent->fs);
#endif
}

void add_dcache (struct shim_dentry * dent, HASHTYPE * hashptr)
{
    lock(dcache_lock);
    __add_dcache(dent, hashptr);
    unlock(dcache_lock);
}

struct shim_dentry *
__lookup_dcache (struct shim_dentry * start, const char * name, int namelen,
                 const char * path, int pathlen, HASHTYPE * hashptr)
{
    HASHTYPE hash = hash_dentry(start, name, namelen);
    struct shim_dentry * dent, * found = NULL;
    struct hlist_node * node;
    struct hlist_head * head = &dcache_htable[DCACHE_HASH(hash)];

    /* walk through all the nodes in the hash bucket, find the droids we're
       looking for */
    hlist_for_each_entry(dent, node, head, hlist) {
        if ((dent->state & DENTRY_MOUNTPOINT) ||
            dent->rel_path.hash != hash)
            continue;

        /* first we compare the filename */
        const char * filename = get_file_name(name, namelen);
        if (memcmp(dentry_get_name(dent), filename, name + namelen - filename))
            continue;

        if (filename == name) {
            struct shim_dentry * d = dent;
            while (d && !d->parent && d->fs)
                d = d->fs->mount_point;
            if (d && d->parent && d->parent != start)
                continue;
        }

        if (path && pathlen && filename != path) {
            const char * fullpath;
            int fullpathlen;
            fullpath = dentry_get_path(dent, true, &fullpathlen);
            if (pathlen > fullpathlen)
                continue;
            fullpath += fullpathlen - pathlen;
            if (fullpath[-1] != '/')
                continue;
            if (memcmp(fullpath, path, pathlen))
                continue;
        }

        get_dentry(dent);
        found = dent;
        break;
    }

    if (hashptr)
        *hashptr = hash;

    return found;
}

/* after lookup_dcache, the dentry is popped to prevent recycling */
struct shim_dentry *
lookup_dcache (struct shim_dentry * start, const char * name, int namelen,
               const char * path, int pathlen, HASHTYPE * hashptr)
{
    lock(dcache_lock);
    struct shim_dentry * dent = __lookup_dcache(start, name, namelen, path,
                                                pathlen, hashptr);
    unlock(dcache_lock);
    return dent;
}

int __del_dentry_tree (struct shim_dentry * root)
{
    struct shim_dentry * this_parent = root;
    struct list_head * next;

repeat:
    next = this_parent->children.next;

resume:
    while (next != &this_parent->children) {
        struct list_head * tmp = next;
        struct shim_dentry * d = list_entry(tmp, struct shim_dentry,
                                            siblings);
        next = tmp->next;
        if (d->state & DENTRY_MOUNTPOINT) {
            this_parent = d->mounted->root;
            goto repeat;
        }

        if (!list_empty(&d->children)) {
            this_parent = d;
            goto repeat;
        }

        __unset_parent_dentry(d, this_parent);
        __del_dcache(d);
    }

    if (this_parent != root) {
        struct shim_dentry * child = this_parent;
        if (!this_parent->parent) {
            this_parent = this_parent->fs->mount_point;
            __del_dcache(child);
            child = this_parent;
        }
        this_parent = this_parent->parent;
        next = child->siblings.next;
        __del_dcache(child);
        __unset_parent_dentry(child, this_parent);
        goto resume;
    }

    return 0;
}