/*      $NetBSD: freeblock.c,v 1.2 2011/07/17 12:47:38 uch Exp $        */

/*-
 * Copyright (c) 2011 The NetBSD Foundation, Inc.
 * All rights reserved.
 *
 * This code is derived from software contributed to The NetBSD Foundation
 * by UCHIYAMA Yasushi.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include <sys/cdefs.h>
#ifndef lint
__RCSID("$NetBSD: freeblock.c,v 1.2 2011/07/17 12:47:38 uch Exp $");
#endif /* not lint */

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#include "v7fs.h"
#include "v7fs_superblock.h"
#include "v7fs_inode.h"
#include "v7fs_impl.h"
#include "v7fs_datablock.h"
#include "fsck_v7fs.h"

struct freeblock_arg {
        v7fs_daddr_t i;
        v7fs_daddr_t j;
        v7fs_daddr_t blk;
};

static int
freeblock_subr_cnt(struct v7fs_self *fs __unused, void *ctx,
    v7fs_daddr_t blk __unused)
{
        ((struct freeblock_arg *)ctx)->blk++;
        progress(0);

        return 0;
}

static int
freeblock_subr_j(struct v7fs_self *fs, void *ctx, v7fs_daddr_t blk)
{
        struct freeblock_arg *arg = (struct freeblock_arg *)ctx;

        if (!datablock_number_sanity(fs, blk)) {
                pwarn("invalid block#%d in freeblock", blk);
                /* This problem should be fixed at freeblock_check(). */
                return FSCK_EXIT_CHECK_FAILED;
        }

        if (arg->j >= arg->i)
                return V7FS_ITERATOR_BREAK;

        progress(0);

        if (arg->blk == blk) {
                pwarn("freeblock duplicate %d %d blk=%d", arg->i, arg->j, blk);
                if (reply("CORRECT?")) {
                        freeblock_dup_remove(fs, blk);
                }
                return FSCK_EXIT_UNRESOLVED; /* Rescan needed. */
        }

        arg->j++;

        return 0;       /*continue */
}

static int
freeblock_subr_i(struct v7fs_self *fs, void *ctx, v7fs_daddr_t blk)
{
        struct freeblock_arg *arg = (struct freeblock_arg *)ctx;
        int ret;

        if (!datablock_number_sanity(fs, blk)) {
                pwarn("invalid block#%d in freeblock", blk);
                /* This problem should be fixed at freeblock_check(). */
                return FSCK_EXIT_CHECK_FAILED;
        }

        arg->j = 0;
        arg->blk = blk;
        ret = v7fs_freeblock_foreach(fs, freeblock_subr_j, ctx);
        if (!((ret == 0) || (ret == V7FS_ITERATOR_BREAK)))
                return ret;

        arg->i++;

        return 0;
}

int
freeblock_vs_freeblock_check(struct v7fs_self *fs)
{
        struct v7fs_superblock *sb = &fs->superblock;
        int n = sb->total_freeblock;

        progress(&(struct progress_arg){ .label = "free-free", .tick = (n / 2)
            * ((n - 1) / PROGRESS_BAR_GRANULE) });

        return v7fs_freeblock_foreach(fs, freeblock_subr_i,
            &(struct freeblock_arg){ .i = 0 });
}

/*
 * Remove duplicated block.
 */
void
freeblock_dup_remove(struct v7fs_self *fs, v7fs_daddr_t dupblk)
{
        struct v7fs_superblock *sb = &fs->superblock;
        struct v7fs_freeblock *fb;
        int i, total, n;
        void *buf;
        v7fs_daddr_t blk;

        n = sb->total_freeblock;

        /* Superblock cache. */
        total = 0;
        for (i = sb->nfreeblock - 1; (i > 0) && (n >= 0); i--, n--, total++) {
                if (sb->freeblock[i] == dupblk) {      /* Duplicate found. */
                        memmove(sb->freeblock + i, sb->freeblock + i + 1,
                            sb->nfreeblock - 1 - i);
                        sb->nfreeblock--;
                        sb->modified = 1;
                        v7fs_superblock_writeback(fs);
                        pwarn("remove duplicated freeblock %d"
                            "from superblock", dupblk);
                        return;
                }
        }
        if (!n)
                return;
        blk = sb->freeblock[0];

        do {
                if (!blk)
                        break;
                buf = scratch_read(fs, blk);
                fb = (struct v7fs_freeblock *)buf;
                v7fs_freeblock_endian_convert(fs, fb);

                if (blk == dupblk) {
                        /* This is difficult probrem. give up! */
                        /* or newly allocate block, and copy it and link. */
                        pwarn("duplicated block is freeblock list."
                            "Shortage freeblock %d->%d.",
                            sb->nfreeblock, total);
                        sb->nfreeblock = total; /*shotage freeblock list. */
                        sb->modified = 1;
                        v7fs_superblock_writeback(fs);
                        return;
                }
                total++;

                blk = fb->freeblock[0]; /* next freeblock list */

                for (i = fb->nfreeblock - 1; (i > 0) && (n >= 0);
                    i--, n--, total++) {
                        if (fb->freeblock[i] == dupblk) {
                                pwarn("remove duplicated freeblock"
                                    "%d from list %d", dupblk, blk);
                                memmove(fb->freeblock + i, fb->freeblock + i +
                                    1, fb->nfreeblock - 1 - i);
                                /* Writeback superblock. */
                                sb->nfreeblock--;
                                sb->modified = 1;
                                v7fs_superblock_writeback(fs);
                                /* Writeback freeblock list block. */
                                v7fs_freeblock_endian_convert(fs, fb);
                                fs->io.write(fs->io.cookie, buf, blk);
                                return;
                        }
                }
                scratch_free(fs, buf);
        } while (n);

        return;
}

int
v7fs_freeblock_foreach(struct v7fs_self *fs,
    int (*func)(struct v7fs_self *, void *, v7fs_daddr_t), void *ctx)
{
        struct v7fs_superblock *sb = &fs->superblock;
        struct v7fs_freeblock *fb;
        int i, n;
        void *buf;
        v7fs_daddr_t blk;
        int ret;

        n = sb->total_freeblock;

        /* Superblock cache. */
        for (i = sb->nfreeblock - 1; (i > 0) && (n >= 0); i--, n--) {
                if ((ret = func(fs, ctx, sb->freeblock[i])))
                        return ret;
        }
        if (!n)
                return 0;
        blk = sb->freeblock[0];
        if (!datablock_number_sanity(fs, blk)) {
                pwarn("invalid freeblock list block#%d.", blk);
                return 0;
        }
        do {
                if (!blk)
                        break;
                if (!(buf = scratch_read(fs, blk)))
                        return 0;
                fb = (struct v7fs_freeblock *)buf;

                if (v7fs_freeblock_endian_convert(fs, fb)) {
                        pwarn("***corrupt freeblock list blk#%d", blk);
                        return 0;
                }

                /* freeblock list is used as freeblock. */
                n--;
                if ((ret = func(fs, ctx, blk)))
                        return ret;

                blk = fb->freeblock[0]; /* next freeblock list */

                for (i = fb->nfreeblock - 1; (i > 0) && (n >= 0); i--, n--)
                        if ((ret = func(fs, ctx, fb->freeblock[i]))) {
                                scratch_free(fs, buf);
                                return ret;
                        }
                scratch_free(fs, buf);
        } while (n);

        return 0;
}

int
freeblock_check(struct v7fs_self *fs)
{
        struct v7fs_superblock *sb = &fs->superblock;
        struct freeblock_arg freeblock_arg = { .blk = 0 };
        v7fs_daddr_t blk;
        v7fs_daddr_t datablock_size = sb->volume_size -
            sb->datablock_start_sector;
        int error = 0;
        struct progress_arg progress_arg = { .label = "freeblock", .tick =
            sb->total_freeblock / PROGRESS_BAR_GRANULE };

        progress(&progress_arg);
        v7fs_freeblock_foreach(fs, freeblock_subr_cnt, &freeblock_arg);
        progress(&progress_arg);

        blk = freeblock_arg.blk;
        pwarn("\ndatablock usage: %d/%d (%d)\n",  datablock_size - blk,
            datablock_size, blk);

        if (sb->total_freeblock != blk) {
                pwarn("corrupt # of freeblocks. %d(sb) != %d(cnt)",
                    sb->total_freeblock, blk);
                if (reply_trivial("CORRECT?")) {
                        sb->total_freeblock = blk;
                        sb->modified = 1;
                        v7fs_superblock_writeback(fs);
                } else {
                        error = FSCK_EXIT_CHECK_FAILED;
                }
        }


        return error;
}