contrib/ksmtpproxy: Fix typo

[navymail.git] / fs.c

/* filesystem interface to navymail store
 * Copyright (C) 2011  Kirill Smelkov <kirr@navytux.spb.ru>
 *
 * This program is free software: you can Use, Study, Modify and Redistribute it
 * under the terms of the GNU General Public License version 2. This program is
 * distributed WITHOUT ANY WARRANTY. See COPYING file for full License terms.
 *
 *
 * XXX what about threading/locking?
 */

#include "git-compat-util.h"
#include "parse-options.h"
#include "argv-array.h"
#include "refs.h"
#include "navymail/navymail.h"
#include "navymail/gbox-walk.h"

#define FUSE_USE_VERSION 26
#include <fuse.h>

static const char * const  mount_usage[] = {
        "navymail mount <mountpoint> [-- fuse-options]",
        NULL
};

static const struct option mount_options[] = {
        OPT_END()
};



/* just tell for_each_ref* caller, we were here, i.e. there were non-zero refs
 * iterated */
static int __refs_nonempty(const char *refname, const unsigned char *sha1,
                int flags, void *cb_data)
{
        return 1;
}

static int navymailfs_getattr(const char *path, struct stat *st)
{
        int ret = 0;

        memset(st, 0, sizeof(*st));

        /* XXX dumb */
        /* XXX what about st_nlink?
         * XXX what about st_uid/st_gid, st_{a,m,c}time ?
         */
        if (!strcmp(path, "/")) {
                st->st_mode  = S_IFDIR | 0755;
                /* st->st_nlink = 2; */
        }
        else if (!strcmp(path, "/mail")) {
                st->st_mode  = S_IFDIR | 0755;
                /* st_nlink */
        }
        else if (!prefixcmp(path, "/mail/")) {
                struct strbuf refname = STRBUF_INIT;
                strbuf_addf(&refname, "refs%s", path);

                /* XXX what to do if there are e.g.
                 *
                 *      refs/mail/x  and  refs/mail/x/y
                 *
                 * ? i.e. here x is both file and directory - Git allows such refs...
                 */

                /* a file? */
                if (ref_exists(refname.buf)) {
                        st->st_mode  = S_IFREG | 0444;
                        /* don't waste resources computing st_size. but then
                         * this needs direct_io=1 for file to be readable */
                        st->st_size  = 0;
                }

                /* it could be a dir still */
                else {
                        /* ensure there is / at tail */
                        if (refname.buf[refname.len - 1] != '/')
                                strbuf_addch(&refname, '/');

                        /* read refs with refname as prefix -- if there are
                         * some, then refname is a dir */
                        if (for_each_ref_in(refname.buf, __refs_nonempty, NULL)) {
                                st->st_mode = S_IFDIR | 0755;
                                /* st_nlink */
                        }
                        else
                                ret = -ENOENT;
                }

                strbuf_release(&refname);
        }
        else
                ret = -ENOENT;

        return ret;
}


struct readdir_ctx {
        void *buf;
        fuse_fill_dir_t filler;

        /* previous added entry. empty if no entries were added yet */
        struct strbuf prev_entry;
};

static int __readdir_handle_ref(const char *refname, const unsigned char *sha1,
                int flags, void *cb_data)
{
        struct readdir_ctx *ctx = (struct readdir_ctx *)cb_data;
        struct strbuf entry = STRBUF_INIT;
        const char *subdir_mark;

        /* extract entry-name from this refname - a file or a subdirectory
         * (potentially from sub-sub-sub...directory */
        if ((subdir_mark = strchr(refname, '/')))
                strbuf_add(&entry, refname, subdir_mark-refname);
        else
                strbuf_addf(&entry, "%s", refname);

        /* refs come here in sorted order, so we can avoid duplicates simply
         * checking against previous entry */
        if (!strbuf_cmp(&entry, &ctx->prev_entry))
                goto out;

        /* now we know this dir is not empty - emit . and .. before first entry */
        if (!ctx->prev_entry.len) {
                ctx->filler(ctx->buf, ".",      NULL, 0);
                ctx->filler(ctx->buf, "..",     NULL, 0);
        }

        /* ctx->prev_entry = entry */
        strbuf_reset(&ctx->prev_entry);
        strbuf_addbuf(&ctx->prev_entry, &entry);

        /* emit entry */
        ctx->filler(ctx->buf, entry.buf,  NULL, 0);

out:
        strbuf_release(&entry);
        return 0;
}

static int navymailfs_readdir(const char *path, void *buf, fuse_fill_dir_t
                filler, off_t offset, struct fuse_file_info *fi)
{
        int ret = 0;
        struct readdir_ctx ctx = { .buf = buf,  .filler = filler,  .prev_entry = STRBUF_INIT };

        (void) offset;
        (void) fi;


        /* XXX dumb */
        if (!strcmp(path, "/")) {
                filler(buf, ".",        NULL, 0);
                filler(buf, "..",       NULL, 0);
                filler(buf, "mail",     NULL, 0);
        }
        else if (!strcmp(path, "/mail") || !prefixcmp(path, "/mail/")) {
                struct strbuf refprefix = STRBUF_INIT;
                strbuf_addf(&refprefix, "refs%s", path);
                if (refprefix.buf[refprefix.len - 1] != '/')
                        strbuf_addch(&refprefix, '/');  /* ensure there is / at tail */

                /* read refs from refprefix (e.g. /refs/mail/dir/) */
                for_each_ref_in(refprefix.buf, __readdir_handle_ref, &ctx);

                if (!ctx.prev_entry.len)
                        ret = -ENOENT;  /* no entries for refprefix */

                strbuf_release(&refprefix);
        }
        else
                ret = -ENOENT;


        strbuf_release(&ctx.prev_entry);
        return ret;
}




/* index for looking up messages in gbox by offset */
struct msgmap_index {
        off_t *sumsize;                 /* Si = sum_{j=0..i} size(msg_j) */
        unsigned char (*sha1)[20];      /* sha1_i */

        int nr;
        int alloc;
};

struct gbox_ctx {
        struct strbuf refname;
        struct gbox_walk gbox_walk;
        struct msgmap_index msgmap;

        /* last read msg */
        char *msg_buf;
        unsigned long msg_size;
        int msg_idx;    /* index in msgmap */
};

static int navymailfs_open(const char *path, struct fuse_file_info *fi)
{
        int ret = 0;
        struct strbuf refname = STRBUF_INIT;
        struct gbox_ctx *ctx = NULL;

        /* XXX dumb */
        if (!!prefixcmp(path, "/mail/")) {
                ret = -ENOENT;
                goto out;
        }

        strbuf_addf(&refname, "refs%s", path);

        if (!ref_exists(refname.buf)) {
                ret = -ENOENT;
                goto out;
        }

        if ((fi->flags & (O_RDONLY | O_WRONLY | O_RDWR)) != O_RDONLY) {
                ret = -ENOENT;
                goto out;
        }

        /*
         * direct_io is used so that files with st_size=0 could be read
         * XXX how this affects performance?
         * XXX what about fi->keep_cache ?
         */
        fi->direct_io = 1;

        ctx = xcalloc(1, sizeof(*ctx));
        strbuf_init(&ctx->refname, 0);
        strbuf_addbuf(&ctx->refname, &refname);
        ctx->gbox_walk.gbox = ctx->refname.buf;
        ctx->gbox_walk.original_order = 1;
        prepare_gbox_walk(&ctx->gbox_walk);

        ctx->msg_idx = -1;

        fi->fh = (intptr_t)ctx;

out:
        strbuf_release(&refname);
        return ret;
}


static int navymailfs_release(const char *path, struct fuse_file_info *fi)
{
        struct gbox_ctx *ctx = (struct gbox_ctx *)(intptr_t)fi->fh;

        strbuf_release(&ctx->refname);
        free(ctx->msgmap.sumsize);
        free(ctx->msgmap.sha1);

        if (ctx->msg_idx != -1) {
                free(ctx->msg_buf);
                ctx->msg_buf  = NULL;
                ctx->msg_size = 0;
                ctx->msg_idx  = -1;
        }

        free(ctx);

        return 0;
}


/* compute a*b/c  correctly handling overflow in a*b
 *
 * b = q*c+r    -> a*b/c = a*q + a*r/c
 */
static intmax_t imaxmuldiv(intmax_t a, intmax_t b, intmax_t c)
{
        imaxdiv_t _;

        _ = imaxdiv(b, c);
        return a*_.quot + a*_.rem/c;
}


#define DEBUG_LOOKUP    0

#if DEBUG_LOOKUP
# define TRACE_LOOKUP(fmt...)   do { fprintf(stderr, fmt); } while (0)
#else
# define TRACE_LOOKUP(fmt...)   do {} while (0)
#endif


static int navymailfs_read(const char *path, char *buf, size_t size, off_t
                offset, struct fuse_file_info *fi)
{
        struct gbox_ctx *ctx = (struct gbox_ctx *)(intptr_t)fi->fh;

        int lo, hi, i, alloc;
        off_t Si, Si_1, Slo_, Shi;
        const unsigned char *sha1;
        enum object_type type;
        const char *read_start;
        int read_size, read_total;

        /* reading optimized for linear reads */

        TRACE_LOOKUP("READ %s\toffset: %llu\tsize: %u\n", path, offset, size);


        /* 1) lookup already-seen msg overlapping with offset.
         * after this phase, either
         *
         * - i indicates appropriate msg, or
         * - i points just-after msgmap tail    (i.e. we need to fetch next msgs)
         *
         *
         * ~~~~
         * some reminders before we begin:
         *
         *      Si = sum_{j=0..i} size(msg_j)
         *
         *      offset <  Si    <=> offset is in [0,i]          (1)
         *      offset >= Si    <=> offset is in [i+1,∞]      (2)
         *
         * in particular
         *
         *      Si_1 <= offset < Si     <=> offset is in i'th msg       (3)
         */
        lo = 0;
        hi = ctx->msgmap.nr - 1;

        /* if we are at tail - there is no chance to find appropriate chunk -
         * we'll have to skip search and start reading next msgs (see 2)
         */
        if (hi==-1 || offset >= ctx->msgmap.sumsize[hi])
                i = hi+1;

        else {
                /* now we know offset is somewhere in msgmap;
                 * start searching at last read */
                i = ctx->msg_idx != -1 ? ctx->msg_idx : hi;

                while (1) {
                        Si   =  ctx->msgmap.sumsize[i];
                        Si_1 =  i >= 1 ? ctx->msgmap.sumsize[i-1] : 0;

                        TRACE_LOOKUP("\tlo: %i\thi: %i\ti: %i\t Si: %llu\tSi_1: %llu\n", lo, hi, i, Si, Si_1);


                        if (offset < Si) {
                                if (offset >= Si_1)
                                        break;          /* found, see (3) */

                                /* offset < Si_1 , so because of (1) */
                                hi = i-1;
                        }
                        else
                                /* offset >= Si , see (2) */
                                lo = i+1;


                        /* now we know offset is somewhere in [lo,hi];
                         * estimate new i, assuming messages are of approximately equal size.
                         *
                         * ~~~~
                         * we have:
                         *
                         *                          offset
                         *                            |
                         *            lo              v        hi
                         *          |----|----|-- ... --|----|----|
                         *         Olo<                          Ohi>
                         *
                         *      Olo< = Slo_1
                         *      Ohi> = Shi - 1
                         *
                         *      Olo<  <= offset <= Ohi>         (4)     ,i.e.
                         *      Slo_1 <= offset <= Shi - 1      (5)
                         *
                         * then new guess, assuming uniformity would be as follows:
                         *
                         *      offset - Olo<      i - lo
                         *      -------------  =  -------       (6)
                         *       Ohi> - Olo<      hi - lo
                         *
                         * which gives
                         *
                         *                          offset - Slo_1
                         *      i = lo + (hi - lo)*-----------------    (7)
                         *                          Shi - Slo_1 - 1
                         *
                         * the ratio multiplier for (hi - lo) is in [0,1]
                         * because of (5), so new i should be always in [lo,hi].
                         *
                         * The process should converge regardless of sizes
                         * distribution, because at each step we tighten lo or
                         * high by 1 in the above block.
                         *
                         * XXX maybe detect pathological cases, and do plain
                         *     binary search then?
                         */

                        Slo_ = lo >= 1 ? ctx->msgmap.sumsize[lo-1] : 0;
                        Shi  = ctx->msgmap.sumsize[hi];

                        /* compute
                         *
                         *      i = lo + (offset - Slo_)*(hi-lo)/(Shi-Slo_-1);
                         *
                         * but avoid overflow on multiply
                         */
                        i = lo + imaxmuldiv( (offset - Slo_),(hi-lo),(Shi-Slo_-1) );
                }
        }


        /* 2) now linearly read messages, until all read request is done
         * NOTE: we'll maybe have to first skip some msgs, if offset >= Si  (see 2)
         */
        read_total = 0;

        for (;size != 0; ++i) {
                /* read i'th msg */
                if (i != ctx->msg_idx) {
                        if (ctx->msg_idx != -1) {
                                free(ctx->msg_buf);
                                ctx->msg_buf  = NULL;
                                ctx->msg_size = 0;
                                ctx->msg_idx  = -1;
                        }

                        if (i == ctx->msgmap.nr) {
                                /* fetch next msg from gbox */
                                sha1 = next_gbox_entry(&ctx->gbox_walk);
                                if (!sha1)
                                        break;  /* EOF */
                        }
                        else
                                sha1 = ctx->msgmap.sha1[i];

                        ctx->msg_buf = read_sha1_file(sha1, &type, &ctx->msg_size);
                        if (!ctx->msg_buf)
                                die("read_sha1_file(%s) -> NULL", sha1_to_hex(sha1));
                        if (type != OBJ_BLOB)
                                die("%s is not a blob", sha1_to_hex(sha1));


                        if (i == ctx->msgmap.nr) {
                                alloc = ctx->msgmap.alloc;
                                ALLOC_GROW(ctx->msgmap.sumsize, ctx->msgmap.nr +1, alloc);
                                ALLOC_GROW(ctx->msgmap.sha1,    ctx->msgmap.nr +1, ctx->msgmap.alloc);

                                ctx->msgmap.nr += 1;
                                ctx->msgmap.sumsize[i] = (i > 0 ? ctx->msgmap.sumsize[i-1] : 0)
                                                         + ctx->msg_size;
                                hashcpy(ctx->msgmap.sha1[i], sha1);
                        }

                        ctx->msg_idx = i;
                }

                Si = ctx->msgmap.sumsize[i];
                Si_1 =  i >= 1 ? ctx->msgmap.sumsize[i-1] : 0;


                /* i'th msg overlaps - use it */
                if (offset < Si) {
                        read_start = ctx->msg_buf  + (offset - Si_1);
                        read_size  = ctx->msg_size - (offset - Si_1);
                        read_size  = MIN(read_size, size);

                        memcpy(buf, read_start, read_size);
                        buf    += read_size;
                        size   -= read_size;
                        offset += read_size;
                        read_total += read_size;
                }
        }


        return read_total;
}

static struct fuse_operations navymailfs_ops = {
        .getattr        = navymailfs_getattr,

#if 0
        .opendir        =
        .releasedir     =
#endif
        .readdir        = navymailfs_readdir,

        .open           = navymailfs_open,
        .release        = navymailfs_release,
        .read           = navymailfs_read,

};


int cmd_mount(int argc, const char **argv, const char *prefix)
{
        int i, ret;
        struct argv_array argvf;

        argc = parse_options(argc, argv, NULL /*prefix?*/, mount_options, mount_usage, 0);

        /* git_config(git_default_config, NULL); ? */

        if (argc < 1)
                usage_with_options(mount_usage, mount_options);

        /* XXX only absolute NAVYMAIL_DIR path is ok, because when
         * daemonizing, fuse does chdir("/"). TODO make this automatically happen */
        if (!is_absolute_path(getenv(NAVYMAIL_DIR_ENVIRONMENT)))
                die("mount: TODO atm navymail-dir has to be absolute-path");

        /* tail to fuse main loop */
        argv_array_init(&argvf);
        argv_array_push(&argvf, "navymail-mount");
        for (i=0; i<argc; ++i)
                argv_array_push(&argvf, argv[i]);

        /* TODO hook fuse_session_exit to die (see exit_handler() in fuse_signals.c) */
        ret = fuse_main(argvf.argc, /* XXX can't we avoid cast? */(char **)argvf.argv, &navymailfs_ops, NULL);

        argv_array_clear(&argvf);
        return ret;
}