/*
 *      vfsv0 quota IO operations on file
 */

#include <linux/errno.h>
#include <linux/fs.h>
#include <linux/mount.h>
#include <linux/dqblk_v2.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/quotaops.h>

#include <asm/byteorder.h>

#include "quota_tree.h"

MODULE_AUTHOR("Jan Kara");
MODULE_DESCRIPTION("Quota trie support");
MODULE_LICENSE("GPL");

#define __QUOTA_QT_PARANOIA

static int get_index(struct qtree_mem_dqinfo *info, qid_t id, int depth)
{
        unsigned int epb = info->dqi_usable_bs >> 2;

        depth = info->dqi_qtree_depth - depth - 1;
        while (depth--)
                id /= epb;
        return id % epb;
}

/* Number of entries in one blocks */
static int qtree_dqstr_in_blk(struct qtree_mem_dqinfo *info)
{
        return (info->dqi_usable_bs - sizeof(struct qt_disk_dqdbheader))
               / info->dqi_entry_size;
}

static char *getdqbuf(size_t size)
{
        char *buf = kmalloc(size, GFP_NOFS);
        if (!buf)
                printk(KERN_WARNING
                       "VFS: Not enough memory for quota buffers.\n");
        return buf;
}

static ssize_t read_blk(struct qtree_mem_dqinfo *info, uint blk, char *buf)
{
        struct super_block *sb = info->dqi_sb;

        memset(buf, 0, info->dqi_usable_bs);
        return sb->s_op->quota_read(sb, info->dqi_type, buf,
               info->dqi_usable_bs, blk << info->dqi_blocksize_bits);
}

static ssize_t write_blk(struct qtree_mem_dqinfo *info, uint blk, char *buf)
{
        struct super_block *sb = info->dqi_sb;
        ssize_t ret;

        ret = sb->s_op->quota_write(sb, info->dqi_type, buf,
               info->dqi_usable_bs, blk << info->dqi_blocksize_bits);
        if (ret != info->dqi_usable_bs) {
                quota_error(sb, "dquota write failed");
                if (ret >= 0)
                        ret = -EIO;
        }
        return ret;
}

/* Remove empty block from list and return it */
static int get_free_dqblk(struct qtree_mem_dqinfo *info)
{
        char *buf = getdqbuf(info->dqi_usable_bs);
        struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
        int ret, blk;

        if (!buf)
                return -ENOMEM;
        if (info->dqi_free_blk) {
                blk = info->dqi_free_blk;
                ret = read_blk(info, blk, buf);
                if (ret < 0)
                        goto out_buf;
                info->dqi_free_blk = le32_to_cpu(dh->dqdh_next_free);
        }
        else {
                memset(buf, 0, info->dqi_usable_bs);
                /* Assure block allocation... */
                ret = write_blk(info, info->dqi_blocks, buf);
                if (ret < 0)
                        goto out_buf;
                blk = info->dqi_blocks++;
        }
        mark_info_dirty(info->dqi_sb, info->dqi_type);
        ret = blk;
out_buf:
        kfree(buf);
        return ret;
}

/* Insert empty block to the list */
static int put_free_dqblk(struct qtree_mem_dqinfo *info, char *buf, uint blk)
{
        struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
        int err;

        dh->dqdh_next_free = cpu_to_le32(info->dqi_free_blk);
        dh->dqdh_prev_free = cpu_to_le32(0);
        dh->dqdh_entries = cpu_to_le16(0);
        err = write_blk(info, blk, buf);
        if (err < 0)
                return err;
        info->dqi_free_blk = blk;
        mark_info_dirty(info->dqi_sb, info->dqi_type);
        return 0;
}

/* Remove given block from the list of blocks with free entries */
static int remove_free_dqentry(struct qtree_mem_dqinfo *info, char *buf,
                               uint blk)
{
        char *tmpbuf = getdqbuf(info->dqi_usable_bs);
        struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
        uint nextblk = le32_to_cpu(dh->dqdh_next_free);
        uint prevblk = le32_to_cpu(dh->dqdh_prev_free);
        int err;

        if (!tmpbuf)
                return -ENOMEM;
        if (nextblk) {
                err = read_blk(info, nextblk, tmpbuf);
                if (err < 0)
                        goto out_buf;
                ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_prev_free =
                                                        dh->dqdh_prev_free;
                err = write_blk(info, nextblk, tmpbuf);
                if (err < 0)
                        goto out_buf;
        }
        if (prevblk) {
                err = read_blk(info, prevblk, tmpbuf);
                if (err < 0)
                        goto out_buf;
                ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_next_free =
                                                        dh->dqdh_next_free;
                err = write_blk(info, prevblk, tmpbuf);
                if (err < 0)
                        goto out_buf;
        } else {
                info->dqi_free_entry = nextblk;
                mark_info_dirty(info->dqi_sb, info->dqi_type);
        }
        kfree(tmpbuf);
        dh->dqdh_next_free = dh->dqdh_prev_free = cpu_to_le32(0);
        /* No matter whether write succeeds block is out of list */
        if (write_blk(info, blk, buf) < 0)
                quota_error(info->dqi_sb, "Can't write block (%u) "
                            "with free entries", blk);
        return 0;
out_buf:
        kfree(tmpbuf);
        return err;
}

/* Insert given block to the beginning of list with free entries */
static int insert_free_dqentry(struct qtree_mem_dqinfo *info, char *buf,
                               uint blk)
{
        char *tmpbuf = getdqbuf(info->dqi_usable_bs);
        struct qt_disk_dqdbheader *dh = (struct qt_disk_dqdbheader *)buf;
        int err;

        if (!tmpbuf)
                return -ENOMEM;
        dh->dqdh_next_free = cpu_to_le32(info->dqi_free_entry);
        dh->dqdh_prev_free = cpu_to_le32(0);
        err = write_blk(info, blk, buf);
        if (err < 0)
                goto out_buf;
        if (info->dqi_free_entry) {
                err = read_blk(info, info->dqi_free_entry, tmpbuf);
                if (err < 0)
                        goto out_buf;
                ((struct qt_disk_dqdbheader *)tmpbuf)->dqdh_prev_free =
                                                        cpu_to_le32(blk);
                err = write_blk(info, info->dqi_free_entry, tmpbuf);
                if (err < 0)
                        goto out_buf;
        }
        kfree(tmpbuf);
        info->dqi_free_entry = blk;
        mark_info_dirty(info->dqi_sb, info->dqi_type);
        return 0;
out_buf:
        kfree(tmpbuf);
        return err;
}

/* Is the entry in the block free? */
int qtree_entry_unused(struct qtree_mem_dqinfo *info, char *disk)
{
        int i;

        for (i = 0; i < info->dqi_entry_size; i++)
                if (disk[i])
                        return 0;
        return 1;
}
EXPORT_SYMBOL(qtree_entry_unused);

/* Find space for dquot */
static uint find_free_dqentry(struct qtree_mem_dqinfo *info,
                              struct dquot *dquot, int *err)
{
        uint blk, i;
        struct qt_disk_dqdbheader *dh;
        char *buf = getdqbuf(info->dqi_usable_bs);
        char *ddquot;

        *err = 0;
        if (!buf) {
                *err = -ENOMEM;
                return 0;
        }
        dh = (struct qt_disk_dqdbheader *)buf;
        if (info->dqi_free_entry) {
                blk = info->dqi_free_entry;
                *err = read_blk(info, blk, buf);
                if (*err < 0)
                        goto out_buf;
        } else {
                blk = get_free_dqblk(info);
                if ((int)blk < 0) {
                        *err = blk;
                        kfree(buf);
                        return 0;
                }
                memset(buf, 0, info->dqi_usable_bs);
                /* This is enough as the block is already zeroed and the entry
                 * list is empty... */
                info->dqi_free_entry = blk;
                mark_info_dirty(dquot->dq_sb, dquot->dq_type);
        }
        /* Block will be full? */
        if (le16_to_cpu(dh->dqdh_entries) + 1 >= qtree_dqstr_in_blk(info)) {
                *err = remove_free_dqentry(info, buf, blk);
                if (*err < 0) {
                        quota_error(dquot->dq_sb, "Can't remove block (%u) "
                                    "from entry free list", blk);
                        goto out_buf;
                }
        }
        le16_add_cpu(&dh->dqdh_entries, 1);
        /* Find free structure in block */
        ddquot = buf + sizeof(struct qt_disk_dqdbheader);
        for (i = 0; i < qtree_dqstr_in_blk(info); i++) {
                if (qtree_entry_unused(info, ddquot))
                        break;
                ddquot += info->dqi_entry_size;
        }
#ifdef __QUOTA_QT_PARANOIA
        if (i == qtree_dqstr_in_blk(info)) {
                quota_error(dquot->dq_sb, "Data block full but it shouldn't");
                *err = -EIO;
                goto out_buf;
        }
#endif
        *err = write_blk(info, blk, buf);
        if (*err < 0) {
                quota_error(dquot->dq_sb, "Can't write quota data block %u",
                            blk);
                goto out_buf;
        }
        dquot->dq_off = (blk << info->dqi_blocksize_bits) +
                        sizeof(struct qt_disk_dqdbheader) +
                        i * info->dqi_entry_size;
        kfree(buf);
        return blk;
out_buf:
        kfree(buf);
        return 0;
}

/* Insert reference to structure into the trie */
static int do_insert_tree(struct qtree_mem_dqinfo *info, struct dquot *dquot,
                          uint *treeblk, int depth)
{
        char *buf = getdqbuf(info->dqi_usable_bs);
        int ret = 0, newson = 0, newact = 0;
        __le32 *ref;
        uint newblk;

        if (!buf)
                return -ENOMEM;
        if (!*treeblk) {
                ret = get_free_dqblk(info);
                if (ret < 0)
                        goto out_buf;
                *treeblk = ret;
                memset(buf, 0, info->dqi_usable_bs);
                newact = 1;
        } else {
                ret = read_blk(info, *treeblk, buf);
                if (ret < 0) {
                        quota_error(dquot->dq_sb, "Can't read tree quota "
                                    "block %u", *treeblk);
                        goto out_buf;
                }
        }
        ref = (__le32 *)buf;
        newblk = le32_to_cpu(ref[get_index(info, dquot->dq_id, depth)]);
        if (!newblk)
                newson = 1;
        if (depth == info->dqi_qtree_depth - 1) {
#ifdef __QUOTA_QT_PARANOIA
                if (newblk) {
                        quota_error(dquot->dq_sb, "Inserting already present "
                                    "quota entry (block %u)",
                                    le32_to_cpu(ref[get_index(info,
                                                dquot->dq_id, depth)]));
                        ret = -EIO;
                        goto out_buf;
                }
#endif
                newblk = find_free_dqentry(info, dquot, &ret);
        } else {
                ret = do_insert_tree(info, dquot, &newblk, depth+1);
        }
        if (newson && ret >= 0) {
                ref[get_index(info, dquot->dq_id, depth)] =
                                                        cpu_to_le32(newblk);
                ret = write_blk(info, *treeblk, buf);
        } else if (newact && ret < 0) {
                put_free_dqblk(info, buf, *treeblk);
        }
out_buf:
        kfree(buf);
        return ret;
}

/* Wrapper for inserting quota structure into tree */
static inline int dq_insert_tree(struct qtree_mem_dqinfo *info,
                                 struct dquot *dquot)
{
        int tmp = QT_TREEOFF;
        return do_insert_tree(info, dquot, &tmp, 0);
}

/*
 * We don't have to be afraid of deadlocks as we never have quotas on quota
 * files...
 */
int qtree_write_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot)
{
        int type = dquot->dq_type;
        struct super_block *sb = dquot->dq_sb;
        ssize_t ret;
        char *ddquot = getdqbuf(info->dqi_entry_size);

        if (!ddquot)
                return -ENOMEM;

        /* dq_off is guarded by dqio_mutex */
        if (!dquot->dq_off) {
                ret = dq_insert_tree(info, dquot);
                if (ret < 0) {
                        quota_error(sb, "Error %zd occurred while creating "
                                    "quota", ret);
                        kfree(ddquot);
                        return ret;
                }
        }
        spin_lock(&dq_data_lock);
        info->dqi_ops->mem2disk_dqblk(ddquot, dquot);
        spin_unlock(&dq_data_lock);
        ret = sb->s_op->quota_write(sb, type, ddquot, info->dqi_entry_size,
                                    dquot->dq_off);
        if (ret != info->dqi_entry_size) {
                quota_error(sb, "dquota write failed");
                if (ret >= 0)
                        ret = -ENOSPC;
        } else {
                ret = 0;
        }
        dqstats_inc(DQST_WRITES);
        kfree(ddquot);

        return ret;
}
EXPORT_SYMBOL(qtree_write_dquot);

/* Free dquot entry in data block */
static int free_dqentry(struct qtree_mem_dqinfo *info, struct dquot *dquot,
                        uint blk)
{
        struct qt_disk_dqdbheader *dh;
        char *buf = getdqbuf(info->dqi_usable_bs);
        int ret = 0;

        if (!buf)
                return -ENOMEM;
        if (dquot->dq_off >> info->dqi_blocksize_bits != blk) {
                quota_error(dquot->dq_sb, "Quota structure has offset to "
                        "other block (%u) than it should (%u)", blk,
                        (uint)(dquot->dq_off >> info->dqi_blocksize_bits));
                goto out_buf;
        }
        ret = read_blk(info, blk, buf);
        if (ret < 0) {
                quota_error(dquot->dq_sb, "Can't read quota data block %u",
                            blk);
                goto out_buf;
        }
        dh = (struct qt_disk_dqdbheader *)buf;
        le16_add_cpu(&dh->dqdh_entries, -1);
        if (!le16_to_cpu(dh->dqdh_entries)) {   /* Block got free? */
                ret = remove_free_dqentry(info, buf, blk);
                if (ret >= 0)
                        ret = put_free_dqblk(info, buf, blk);
                if (ret < 0) {
                        quota_error(dquot->dq_sb, "Can't move quota data block "
                                    "(%u) to free list", blk);
                        goto out_buf;
                }
        } else {
                memset(buf +
                       (dquot->dq_off & ((1 << info->dqi_blocksize_bits) - 1)),
                       0, info->dqi_entry_size);
                if (le16_to_cpu(dh->dqdh_entries) ==
                    qtree_dqstr_in_blk(info) - 1) {
                        /* Insert will write block itself */
                        ret = insert_free_dqentry(info, buf, blk);
                        if (ret < 0) {
                                quota_error(dquot->dq_sb, "Can't insert quota "
                                    "data block (%u) to free entry list", blk);
                                goto out_buf;
                        }
                } else {
                        ret = write_blk(info, blk, buf);
                        if (ret < 0) {
                                quota_error(dquot->dq_sb, "Can't write quota "
                                            "data block %u", blk);
                                goto out_buf;
                        }
                }
        }
        dquot->dq_off = 0;      /* Quota is now unattached */
out_buf:
        kfree(buf);
        return ret;
}

/* Remove reference to dquot from tree */
static int remove_tree(struct qtree_mem_dqinfo *info, struct dquot *dquot,
                       uint *blk, int depth)
{
        char *buf = getdqbuf(info->dqi_usable_bs);
        int ret = 0;
        uint newblk;
        __le32 *ref = (__le32 *)buf;

        if (!buf)
                return -ENOMEM;
        ret = read_blk(info, *blk, buf);
        if (ret < 0) {
                quota_error(dquot->dq_sb, "Can't read quota data block %u",
                            *blk);
                goto out_buf;
        }
        newblk = le32_to_cpu(ref[get_index(info, dquot->dq_id, depth)]);
        if (depth == info->dqi_qtree_depth - 1) {
                ret = free_dqentry(info, dquot, newblk);
                newblk = 0;
        } else {
                ret = remove_tree(info, dquot, &newblk, depth+1);
        }
        if (ret >= 0 && !newblk) {
                int i;
                ref[get_index(info, dquot->dq_id, depth)] = cpu_to_le32(0);
                /* Block got empty? */
                for (i = 0; i < (info->dqi_usable_bs >> 2) && !ref[i]; i++)
                        ;
                /* Don't put the root block into the free block list */
                if (i == (info->dqi_usable_bs >> 2)
                    && *blk != QT_TREEOFF) {
                        put_free_dqblk(info, buf, *blk);
                        *blk = 0;
                } else {
                        ret = write_blk(info, *blk, buf);
                        if (ret < 0)
                                quota_error(dquot->dq_sb,
                                            "Can't write quota tree block %u",
                                            *blk);
                }
        }
out_buf:
        kfree(buf);
        return ret;
}

/* Delete dquot from tree */
int qtree_delete_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot)
{
        uint tmp = QT_TREEOFF;

        if (!dquot->dq_off)     /* Even not allocated? */
                return 0;
        return remove_tree(info, dquot, &tmp, 0);
}
EXPORT_SYMBOL(qtree_delete_dquot);

/* Find entry in block */
static loff_t find_block_dqentry(struct qtree_mem_dqinfo *info,
                                 struct dquot *dquot, uint blk)
{
        char *buf = getdqbuf(info->dqi_usable_bs);
        loff_t ret = 0;
        int i;
        char *ddquot;

        if (!buf)
                return -ENOMEM;
        ret = read_blk(info, blk, buf);
        if (ret < 0) {
                quota_error(dquot->dq_sb, "Can't read quota tree "
                            "block %u", blk);
                goto out_buf;
        }
        ddquot = buf + sizeof(struct qt_disk_dqdbheader);
        for (i = 0; i < qtree_dqstr_in_blk(info); i++) {
                if (info->dqi_ops->is_id(ddquot, dquot))
                        break;
                ddquot += info->dqi_entry_size;
        }
        if (i == qtree_dqstr_in_blk(info)) {
                quota_error(dquot->dq_sb, "Quota for id %u referenced "
                            "but not present", dquot->dq_id);
                ret = -EIO;
                goto out_buf;
        } else {
                ret = (blk << info->dqi_blocksize_bits) + sizeof(struct
                  qt_disk_dqdbheader) + i * info->dqi_entry_size;
        }
out_buf:
        kfree(buf);
        return ret;
}

/* Find entry for given id in the tree */
static loff_t find_tree_dqentry(struct qtree_mem_dqinfo *info,
                                struct dquot *dquot, uint blk, int depth)
{
        char *buf = getdqbuf(info->dqi_usable_bs);
        loff_t ret = 0;
        __le32 *ref = (__le32 *)buf;

        if (!buf)
                return -ENOMEM;
        ret = read_blk(info, blk, buf);
        if (ret < 0) {
                quota_error(dquot->dq_sb, "Can't read quota tree block %u",
                            blk);
                goto out_buf;
        }
        ret = 0;
        blk = le32_to_cpu(ref[get_index(info, dquot->dq_id, depth)]);
        if (!blk)       /* No reference? */
                goto out_buf;
        if (depth < info->dqi_qtree_depth - 1)
                ret = find_tree_dqentry(info, dquot, blk, depth+1);
        else
                ret = find_block_dqentry(info, dquot, blk);
out_buf:
        kfree(buf);
        return ret;
}

/* Find entry for given id in the tree - wrapper function */
static inline loff_t find_dqentry(struct qtree_mem_dqinfo *info,
                                  struct dquot *dquot)
{
        return find_tree_dqentry(info, dquot, QT_TREEOFF, 0);
}

int qtree_read_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot)
{
        int type = dquot->dq_type;
        struct super_block *sb = dquot->dq_sb;
        loff_t offset;
        char *ddquot;
        int ret = 0;

#ifdef __QUOTA_QT_PARANOIA
        /* Invalidated quota? */
        if (!sb_dqopt(dquot->dq_sb)->files[type]) {
                quota_error(sb, "Quota invalidated while reading!");
                return -EIO;
        }
#endif
        /* Do we know offset of the dquot entry in the quota file? */
        if (!dquot->dq_off) {
                offset = find_dqentry(info, dquot);
                if (offset <= 0) {      /* Entry not present? */
                        if (offset < 0)
                                quota_error(sb, "Can't read quota structure "
                                            "for id %u", dquot->dq_id);
                        dquot->dq_off = 0;
                        set_bit(DQ_FAKE_B, &dquot->dq_flags);
                        memset(&dquot->dq_dqb, 0, sizeof(struct mem_dqblk));
                        ret = offset;
                        goto out;
                }
                dquot->dq_off = offset;
        }
        ddquot = getdqbuf(info->dqi_entry_size);
        if (!ddquot)
                return -ENOMEM;
        ret = sb->s_op->quota_read(sb, type, ddquot, info->dqi_entry_size,
                                   dquot->dq_off);
        if (ret != info->dqi_entry_size) {
                if (ret >= 0)
                        ret = -EIO;
                quota_error(sb, "Error while reading quota structure for id %u",
                            dquot->dq_id);
                set_bit(DQ_FAKE_B, &dquot->dq_flags);
                memset(&dquot->dq_dqb, 0, sizeof(struct mem_dqblk));
                kfree(ddquot);
                goto out;
        }
        spin_lock(&dq_data_lock);
        info->dqi_ops->disk2mem_dqblk(dquot, ddquot);
        if (!dquot->dq_dqb.dqb_bhardlimit &&
            !dquot->dq_dqb.dqb_bsoftlimit &&
            !dquot->dq_dqb.dqb_ihardlimit &&
            !dquot->dq_dqb.dqb_isoftlimit)
                set_bit(DQ_FAKE_B, &dquot->dq_flags);
        spin_unlock(&dq_data_lock);
        kfree(ddquot);
out:
        dqstats_inc(DQST_READS);
        return ret;
}
EXPORT_SYMBOL(qtree_read_dquot);

/* Check whether dquot should not be deleted. We know we are
 * the only one operating on dquot (thanks to dq_lock) */
int qtree_release_dquot(struct qtree_mem_dqinfo *info, struct dquot *dquot)
{
        if (test_bit(DQ_FAKE_B, &dquot->dq_flags) &&
            !(dquot->dq_dqb.dqb_curinodes | dquot->dq_dqb.dqb_curspace))
                return qtree_delete_dquot(info, dquot);
        return 0;
}
EXPORT_SYMBOL(qtree_release_dquot);