reclaim.c

是一个手机功能的模拟程序

/******************************************************************************
 * Flash File System (ffs)
 * Idea, design and coding by Mads Meisner-Jensen, [e-mail]
 *
 * FFS core reclaim functionality
 *
 * $Id: reclaim.c,v 1.1.1.1 2004/06/19 06:00:30 root Exp $
 *
 ******************************************************************************/

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

#include "ffs.h"
#include "core.h"
#include "drv.h"
#include "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 (ip->child == (iref_t) IREF_NULL) {
        tw(tr(TR_END, TrReclaimLow, "}\n"));
        return;
    }

    pi = -i;
    i = ip->child;
    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, OT_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, OT_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 (ip->child != (iref_t) IREF_NULL && is_object(ip, OT_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 = ips->child) != (iref_t) IREF_NULL) {

                    // Get child
                    is = ips->child;
                    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 (ips->sibling != (iref_t) IREF_NULL) {  
                            // Get sibling
                            is = ips->sibling;
                            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 = ip->sibling;
        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);

    block_commit();

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

    return EFFS_OK;
}

#if (FFS_TEST == 0)
#define BLOCK_COMMIT_TEST(testcase, text)
#else
#if (TARGET == 0)
// NOTEME: We have compressed the macro code because it will NOT compile on
// Unix otherwise. So until we find out why, we use this as a work-around.
#define BLOCK_COMMIT_TEST(testcase, text) if (fs.testflags == testcase) { tw(tr(TR_FUNC, TrData, "} (" text ")\n")); return; }
#else
#define BLOCK_COMMIT_TEST(testcase, text) if (fs.testflags == testcase) { ttw(ttr(TTrData, "} (" text ")\n")); return; }
#endif
#endif

// Inode -> Lost, Copying -> Inode, Lost -> Free
void block_commit(void)
{
    tw(tr(TR_BEGIN, TrIReclaim, "block_commit(%d -> %d) {\n", 
       fs.inodes, fs.newinodes));
    ttw(ttr(TTrData, "block_commit(%d -> %d) {\n" NL, 
       fs.inodes, fs.newinodes)); 

    BLOCK_COMMIT_TEST(BLOCK_COMMIT_BEFORE, "Oops before commit");

	block_flags_write(fs.inodes, BF_LOST);
 
	BLOCK_COMMIT_TEST(BLOCK_COMMIT_NO_VALID, "Oops no valid inode block");

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

	BLOCK_COMMIT_TEST(BLOCK_COMMIT_OLD_FREE, "Oops after freeing old block");

	// Free old inodes block
    block_free(fs.inodes);

    BLOCK_COMMIT_TEST(BLOCK_COMMIT_AFTER, "Oops after commit");
    
    bstat[fs.newinodes].lost = 0;
    bstat[fs.newinodes].objects = 1;
    inodes_set(fs.newinodes);

    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(int space)
{
    iref_t error;

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

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

    error = data_reclaim_try(space);

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

    return error;
}

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;