/******************************************************************************
 * Flash File System (ffs)
 * Idea, design and coding by Mads Meisner-Jensen, mmj@ti.com
 *
 * FFS core reclaim functionality
 *
 * $Id: reclaim.c 1.4.1.28 Thu, 08 Jan 2004 15:05:23 +0100 tsj $
 *
 ******************************************************************************/

#ifndef TARGET
#include "ffs.cfg"
#endif

#include "ffs/ffs.h"
#include "ffs/board/core.h"
#include "ffs/board/drv.h"
#include "ffs/board/ffstrace.h"

#include <stdlib.h>  // rand()

/******************************************************************************
 * Inodes Reclaim
 ******************************************************************************/

void inodes_recurse(iref_t i)
{
    iref_t pi;
    struct inode_s *ip, *newip;

    tw(tr(TR_BEGIN, TrReclaimLow, "inodes_recurse(%d) {\n", i));

    ip    = inode_addr(i);
    newip = (struct inode_s *) offset2addr(dev.binfo[fs.newinodes].offset) + i;
    
    // copy inode dir to new block, except child, sibling and copied
    ffsdrv.write((uint32*) &newip->location, (uint32*) &ip->location, sizeof(location_t));
    ffsdrv.write_halfword((uint16*) &newip->size,     ip->size);
    ffsdrv_write_byte    (&newip->flags,    ip->flags);
    ffsdrv.write_halfword((uint16*) &newip->sequence, ip->sequence);
    ffsdrv.write_halfword((uint16*) &newip->updates,  ip->updates);
    bstat[fs.newinodes].used++;

    // if no children of this dir, we have no more work to do
    if (get_child(ip) == (iref_t) IREF_NULL) {
        tw(tr(TR_END, TrReclaimLow, "}\n"));
        return;
    }

    pi = -i;
    i = get_child(ip);
    ip = inode_addr(i);

    do {
        tw(tr(TR_FUNC, TrReclaimLow, "pi = %d, i = %d", pi, i));

        tw(tr(TR_NULL, TrReclaimLow, ", size = %d, location = 0x%x", ip->size, 
              ip->location));
        
        tw(tr(TR_NULL, TrReclaimLow, ", name_addr = 0x%x",
              addr2name(offset2addr(location2offset(ip->location)))));
        
        if (is_object(ip, OTE_SEGMENT)) 
            tw(tr(TR_NULL, TrReclaimLow, ", (segment)\n"));
        
        else
            tw(tr(TR_NULL, TrReclaimLow, ", '%s'\n",
                  (ip->size ? addr2name(offset2addr(location2offset(ip->location)))
                   : "(cleaned)")));

        if (is_object_valid(ip))
        {
            if (is_object(ip, OTE_DIR)) {
                tw(tr(TR_NULL, TrReclaimLow, "recursing...\n", i));
                inodes_recurse(i);
            }
            else {
                tw(tr(TR_NULL, TrReclaimLow, "copying...\n"));
                // copy inode to new block, except child, sibling and copied
                newip = (struct inode_s *)
                    offset2addr(dev.binfo[fs.newinodes].offset) + i;
                ffsdrv.write((uint32*) &newip->location, (uint32*) &ip->location, sizeof(location_t));
                ffsdrv.write_halfword((uint16*) &newip->size,     ip->size);
                ffsdrv_write_byte    (&newip->flags,    ip->flags);
                ffsdrv.write_halfword((uint16*) &newip->sequence, ip->sequence);
                ffsdrv.write_halfword((uint16*) &newip->updates,  ip->updates);
                bstat[fs.newinodes].used++;
            }

            tw(tr(TR_FUNC, TrReclaimLow, "Linking: %d->%d\n",pi, i));
            // now write the child or sibling link of previous inode
            newip = (struct inode_s *)
                offset2addr(dev.binfo[fs.newinodes].offset);
            if (pi > 0)
                ffsdrv.write_halfword((uint16*) &(newip + pi)->sibling, i);
            else
                ffsdrv.write_halfword((uint16*) &(newip + (-pi))->child, i);
            
            pi = i; // save index of previous inode
            
            if (get_child(ip) != (iref_t) IREF_NULL && is_object(ip, OTE_FILE)) {
                iref_t pis, is;
                struct inode_s *ips;
                pis = i;
                ips = ip;

                tw(tr(TR_FUNC, TrReclaimLow, "Follow segment head\n"));
                // While child is valid
                while ((is = get_child(ips)) != (iref_t) IREF_NULL) {

                    // Get child
                    is = get_child(ips);
                    ips = inode_addr(is);
                    tw(tr(TR_FUNC, TrReclaimLow, "Child ok, got new child i = %d\n", is));
                    // While object not is valid
                    while (!is_object_valid(ips)) {
                        tw(tr(TR_FUNC, TrReclaimLow, "pi = %d, i = %d c(cleaned)\n", pis, is));
                        // If sibling are valid
                        if (get_sibling(ips) != (iref_t) IREF_NULL) {  
                            // Get sibling
                            is = get_sibling(ips);
                            ips = inode_addr(is);
                            tw(tr(TR_FUNC, TrReclaimLow, "Sibling ok, got new sibling i = %d\n", is));
                        }
                        else {
                            tw(tr(TR_FUNC, TrReclaimLow, "Sibling = FF (%d)\n", ips->sibling));
                            break;  // Nothing more todo, child and sibling = FF
                        }
                    }
                    // If object is valid
                    if (is_object_valid(ips)) {
                        tw(tr(TR_NULL, TrReclaimLow, "copying...\n"));
                        // copy inode to new block, except child, sibling and copied
                        newip = (struct inode_s *)
                            offset2addr(dev.binfo[fs.newinodes].offset) + is;
                        ffsdrv.write((uint32*) &newip->location, (uint32*) &ips->location, sizeof(location_t));
                        ffsdrv.write_halfword((uint16*) &newip->size,     ips->size);
                        ffsdrv_write_byte    (&newip->flags,              ips->flags);
                        ffsdrv.write_halfword((uint16*) &newip->sequence, ips->sequence);
                        ffsdrv.write_halfword((uint16*) &newip->updates,  ips->updates);
                        bstat[fs.newinodes].used++;
                        
                        tw(tr(TR_FUNC, TrReclaimLow, "Linking child: %d->%d\n",pis, is));
                        // now write the child link of previous inode
                        newip = (struct inode_s *)
                            offset2addr(dev.binfo[fs.newinodes].offset);
                        ffsdrv.write_halfword((uint16*) &(newip + (pis))->child, is);
                        
                        pis = is; // save index of previous inode   
               
                    }     
                    else {
                        tw(tr(TR_FUNC, TrReclaimLow, "Sibling = FF (%d, %d)\n", 
                              ips->sibling, ips->child));
                    }

                }
            }
        }       
        else {
            tw(tr(TR_NULL, TrReclaimLow, "(ignoring)\n"));
        }
        i = get_sibling(ip);
        ip = inode_addr(i);
            
    } while (i != (iref_t) IREF_NULL);
    
    tw(tr(TR_END, TrReclaimLow, "}\n"));
}

// Reclaim inodes, eg. move inodes to another block and erase old one.
effs_t inodes_reclaim(void)
{
    tw(tr(TR_BEGIN, TrIReclaim, "inodes_reclaim() {\n"));
    ttw(str(TTrRec, "irec{"));

    if (fs.initerror != EFFS_OK) {
        tw(tr(TR_END, TrIReclaim, "} %d\n", fs.initerror));
        ttw(ttr(TTrRec, "} %d" NL, fs.initerror));
        return fs.initerror;
    }

    if ((fs.newinodes = block_alloc(1, BF_COPYING)) < 0) {
        tw(tr(TR_END, TrIReclaim, "} %d\n", EFFS_NOBLOCKS));
        ttw(ttr(TTrRec, "} %d" NL, EFFS_NOBLOCKS));
        return EFFS_NOBLOCKS;
    }

    statistics_update_irec(bstat[fs.inodes].used - bstat[fs.inodes].lost, 
                           bstat[fs.inodes].lost);

    // copy all inodes...
    bstat[fs.newinodes].used = 0;
    inodes_recurse(fs.root);

    // The replacement inodes are not copied to the new block thus the table
    // must be cleaned
    memset(fs.repi_table, 0, sizeof(fs.repi_table));

    block_commit();

    tw(tr(TR_END, TrIReclaim, "} 0\n"));
    ttw(str(TTrRec, "} 0" NL));

    return EFFS_OK;
}

// Inode -> Lost, Copying -> Inode, Lost -> Free
void block_commit(void)
{
    int oldinodes = fs.inodes;

    tw(tr(TR_BEGIN, TrIReclaim, "block_commit(%d -> %d) {\n", 
       oldinodes, fs.newinodes));
    ttw(ttr(TTrRec, "block_commit(%d -> %d) {\n" NL, 
       oldinodes, fs.newinodes)); 

    block_flags_write(oldinodes, BF_LOST);
 
    // Validate new block as an inodes block
    block_flags_write(fs.newinodes, BF_INODES);

    bstat[fs.newinodes].lost = 0;
    bstat[fs.newinodes].objects = 1;
    inodes_set(fs.newinodes);

    // Free old inodes block
    block_free(oldinodes);

    ttw(str(TTrRec, "} 0" NL));
    tw(tr(TR_END, TrIReclaim, "}\n"));
}


/******************************************************************************
 * Data Reclaim
 ******************************************************************************/

// Important note: We must NOT perform a data reclaim when we are in the
// process of creating the journal file!

// Reclaim a data block, eg. move files to other blocks and erase old one.
// When the reclaim is done, we must completely delete the old inodes which
// are pointing into the old data sector which is going to be erased now.
iref_t data_reclaim(void)
{
    iref_t error;

    tw(tr(TR_BEGIN, TrDReclaim, "data_reclaim() {\n"));

    if (fs.initerror != EFFS_OK) {
        tw(tr(TR_END, TrDReclaim, "} %d\n", fs.initerror));
        return fs.initerror;
    }

    error = data_reclaim_try();

    tw(tr(TR_END, TrDReclaim, "} (data_reclaim) %d\n", error));

    return error;
}

// This algorithm will reclaim a block when it exceeds a delta age of more
// than DAGE_MAX and the age gain is more than DAGE_MAX. When the block is
// younger than DAGE_MAX, the agegain needed (for accepting the reclaim) is
// decreased linearly with the block's increase in delta age.
//
// The algorithm is extended a wee bit in order to avoid data reclaim
// storms, i.e. when many static data blocks reach DAGE_MAX at the same
// time. What we do is that we allow a few early age based reclaims this
// way: The probability that a block is reclaimed early gets exponentially
// higher as the block's delta age is closing in on DAGE_MAX - provided that
// the agegain is good.
int dage_max_reached(int dage_blk, int agegain)
{
    int reclaim, early, log2, mask;

    tw(tr(TR_BEGIN, TrDReclaim, "young(%d, %d) {\n", dage_blk, agegain));
    
    // Simple algorithm
    reclaim = (dage_blk + agegain - 2 * FFS_DAGE_MAX >= 0);

    // Early exponential probability based reclaim
    early = FFS_DAGE_MAX - dage_blk;
    if (agegain > dage_blk - 4 && 0 < early && early <= FFS_DAGE_EARLY_WIDTH) {
        if (early < 4)
            early = 2;
        if (early < FFS_DAGE_EARLY_WIDTH) {
            // Now make an exponential probability distributon by
            // generating a bitmask of a size relative to (dage_blk
            // - DAGE_EARLY_WIDTH)
            log2 = -1;
            while (early > 0) {
                early >>= 1;
                log2++;
            }
            reclaim = log2;
            
            mask = (1 << (log2 + 1)) - 1;
            reclaim = ((rand() & mask) == 0);
        }
    }

    // Do not perform a reclaim unless we gain a certain minimum
    if (agegain < FFS_DAGE_GAIN_MIN)
        reclaim = 0;

    tw(tr(TR_END, TrDReclaim, "} (%d)\n", reclaim));
    return reclaim;
}


// Find a suitable block to reclaim. On success, return the number of bytes
// actually reclaimed. Otherwise, on failure, return a (negative) error.
int data_reclaim_try(void)
{
    int result = 0, reserved_ok = 0;
    bref_t b, blocks_free;
    bref_t brc_young_b, brc_lost_b;

    blocksize_t brc_lost_lost;
    blocksize_t unused, lost, lost_total, free;

    age_t brc_young_dage, free_dage, dage;
    struct block_header_s *bhp;
    // Note gain can be negative if the free block is younger than the
    // youngest data block
    int age_gain; 

    tw(tr(TR_BEGIN, TrDReclaim, "data_reclaim_try() {\n"));
    ttw(str(TTrRec, "drec{" NL));
    // While searching for a block to reclaim, we maintain two block reclaim
    // candidates (brc): 
    //
    // 1- The youngest block, e.g. the one with the largest age distance to
    // fs.age_max. This is to ensure that blocks with a high amount of
    // static data are used for wear-leveling.
    //
    // 2- The block with the highest amount of lost bytes. Note this
    // candidate is also used if the amount of free space is below
    // RESERVED_LOW.
    
    // This counts free blocks, so we initialize to number of blocks minus
    // one for inodes.
    blocks_free = dev.numblocks - 1;

    // Initialize Block Reclaim Candidate (brc) variables
    brc_lost_b   = -1; brc_lost_lost   = 0;
    brc_young_b  = -1; brc_young_dage = 0;  free_dage  = 0;

    lost_total   = 0;

    tw(tr(TR_FUNC, TrDReclaim,
          "blk  unused    lost  w/age   age dist  objs\n"));
    for (b = 0; b < dev.numblocks; b++)
    {
        bhp = (struct block_header_s *) offset2addr(dev.binfo[b].offset);

        if (is_block(b, BF_IS_DATA))
        {
            // Record number of lost bytes and number of unused bytes,
            // eg. total space that would be freed if this block was
            // reclaimed
            lost   = bstat[b].lost;
            unused = dev.blocksize - (bstat[b].used - bstat[b].lost);
            free   = dev.blocksize - bstat[b].used;

            lost_total   += lost;

            if (free >= RESERVED_LOW) 
                reserved_ok = 1;
            if (lost > brc_lost_lost) {
                brc_lost_b = b;
                brc_lost_lost = lost;
            }
            tw(tr(TR_FUNC, TrDReclaim, "%3d %7d %7d ", b, unused, lost));

            dage = saturate_dage(fs.age_max - bhp->age);

            tw(tr(TR_NULL, TrDReclaim, "%6d %5d %4d   %3d\n",
                  lost, bhp->age, dage, bstat[b].objects));

            if (dage >= brc_young_dage) {
                brc_young_b = b;
                brc_young_dage = dage;
            }
            blocks_free--;
        }
        else if (is_block(b, BF_IS_FREE)) {
            // Find youngest free block (in must cases we will only have one free b)
            dage = saturate_dage(fs.age_max - bhp->age);

            if (dage >= free_dage)
                free_dage = dage;   // Delta age of youngest free block
        }
    }
    tw(tr(TR_FUNC, TrDReclaim, "sum %7d\n", lost_total));
    tw(tr(TR_FUNC, TrDReclaim, "blocks_free = %d, fs.age_max = %d\n", blocks_free, fs.age_max));

    age_gain = brc_young_dage - free_dage; // Same as free - block age