reclaim.c

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

                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;
}


// Try to reclaim at least <space> bytes of data space. On success, return
// the number of bytes actually reclaimed. Otherwise, on failure, return a
// (negative) error.
int data_reclaim_try(int space)
{
    // 1. Find a suitable block to reclaim.
    //
    // 2. Relocate each valid object from old block (to another block). An
    // object relocation is similar to a normal file update, e.g. similar to
    // fupdate().
    //
    // 3. If there is not enough space to relocate a file, we must alloc a
    // new block then data_format() it.
    //
    // 4. set BF_CLEANING flag of old block.
    //
    // 5. ALL inodes (also invalid an erased ones) referring into reclaimed
    // block must now be totally wiped out.
    //
    // 6. Free (invalidate) old block.

    int result = 0, reserved_ok = 0;
    bref_t b, blocks_free;
    bref_t brc_young_b, brc_lost_b, brc_unused_b;

    blocksize_t brc_lost_lost,   brc_lost_unused;
    blocksize_t brc_unused_unused;
    blocksize_t unused, unused_total, 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(%d) {\n", space));
    ttw(str(TTrRec, "drec{" NL));

    // While searching for a block to reclaim, we maintain three block
    // reclaim candidates (brc): One with the maximum number of lost bytes,
    // one with the maximum number of unused bytes and another for the
    // youngest block, e.g. the one with the largest age distance to
    // fs.age_max. The candidates are tried in the order mentioned.
    
    // 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_unused   = 0; brc_lost_lost   = 0;
    brc_unused_b = -1; brc_unused_unused = 0; 

    brc_young_b  = -1; brc_young_dage = 0;  free_dage  = 0;

    lost_total   = 0;
    unused_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;
            unused_total += unused;

            if (free >= RESERVED_LOW) 
                reserved_ok = 1;
            if (lost > brc_lost_lost) {
                brc_lost_b = b;
                brc_lost_lost = lost;
                brc_lost_unused = unused;
            }
            if (unused > brc_unused_unused) {
                brc_unused_b = b;
                brc_unused_unused = unused;
            }

            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)) {
            unused_total += dev.blocksize;

            // 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 %7d\n", unused_total, 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
  
    if (space > unused_total) {
        // We will never be able to reclaim this amount...
        result = 0;
    }
    else {
        // Any spare blocks?
        if (blocks_free - fs.blocks_free_min > 0) {
            tw(tr(TR_FUNC, TrDReclaim, "Allocating new block\n"));
            if ((result = block_alloc(1, BF_DATA)) >= 0)
                result = 1;  // Allocated new block
        }
        else {
            // No additional blocks (apart from spare block) are free...
            tw(tr(TR_FUNC, TrDReclaim,
                  "brc_young_dage = %d, brc_lost_unused = %d, brc_unused_unused = %d\n",
                  brc_young_dage, brc_lost_unused, brc_unused_unused));
    
            if (reserved_ok == 0) {
                tw(tr(TR_FUNC, TrDReclaim, 
                      "No reserved, reclaim most-lost block (%d)\n", brc_unused_b));
                result = data_block_reclaim(brc_lost_b, MOST_LOST);
            }
            else if (dage_max_reached(brc_young_dage, age_gain) > 0 ) {
                tw(tr(TR_FUNC, TrDReclaim, "Reclaiming youngest block (%d)\n",
                      brc_young_b));
                result = data_block_reclaim(brc_young_b, YOUNGEST);
            }
            else if (brc_lost_unused >= space) {
                tw(tr(TR_FUNC, TrDReclaim, "Reclaiming most-lost block (%d)\n",
                      brc_lost_b));
                result = data_block_reclaim(brc_lost_b, MOST_LOST);
            }
            else if (brc_unused_unused >= space) {
                tw(tr(TR_FUNC, TrDReclaim, "Reclaiming most-unused block (%d)\n",
                      brc_unused_b));
                result = data_block_reclaim(brc_unused_b, MOST_UNUSED);
            }
            else {
                tw(tr(TR_FUNC, TrDReclaim, "Reclaiming most-lost blockx (%d)\n",
                      brc_lost_b));
                result = data_block_reclaim(brc_lost_b, MOST_LOST);
                if (result >= 0)
                    result = 0;  // We reclaimed a block but we still need more space
            }
        }
    }
    tw(tr(TR_END, TrDReclaim, "} (data_reclaim_try) %d\n", result));

    return result;
}


#if (FFS_TEST == 0)
#define BLOCK_RECLAIM_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_RECLAIM_TEST(testcase, text) if (fs.testflags == testcase) { tw(tr(TR_FUNC, TrTestHigh, "(" text ")\n")); tw(tr(TR_END, TrDReclaim, "} (Test) -100\n", result));return -100; }
#else
#define BLOCK_RECLAIM_TEST(testcase, text) if (fs.testflags == testcase) { ttw(ttr(TTrData, "} (" text ")"NL)); ttw(ttr(TTrRec, "} (Test) -100" NL));return -100; }
#endif
#endif

#if (FFS_TEST == 0)
#define BLOCK_RECOVER_TEST_INIT(testcase, text)
#define BLOCK_RECOVER_TEST(testcase, text)
#else
#if (TARGET == 0)
#define BLOCK_RECOVER_TEST_INIT(testcase, text) int rand_object; if (fs.testflags == testcase) { rand_object = rand() % bstat[b].objects; tw(tr(TR_FUNC, TrTestHigh, "Fail when object nr %d is relocated\n", rand_object)); }

#define BLOCK_RECOVER_TEST(testcase, text) if (fs.testflags == testcase) {if (rand_object == n) { tw(tr(TR_FUNC, TrTestHigh, "(" text ")\n")); tw(tr(TR_END, TrDReclaim, "} (Test) -101\n", result)); return -101; } }

#else   
#define BLOCK_RECOVER_TEST_INIT(testcase, text) int rand_object; if (fs.testflags == testcase) { rand_object = rand() % bstat[b].objects; ttw(ttr(TTrData, "Fail when object nr %d is relocated" NL, rand_object)); }
#define BLOCK_RECOVER_TEST(testcase, text) if (fs.testflags == testcase) {if (rand_object == n) { ttw(ttr(TTrData, "(" text ")" NL)); ttw(ttr(TTrRec, "} (Test) -101" NL, result)); return -101; } }
#endif
#endif

iref_t data_block_reclaim(bref_t b, int candidate)
{
    iref_t i, n, j;
    blocksize_t used_old, lost_old;
	int org_res_space, result = 0;
	iref_t org_block_files_reserved;
    offset_t lower, upper;
    struct inode_s *ip;
	static int is_reclaim_running = 0;

    tw(tr(TR_BEGIN, TrDReclaim, "data_block_reclaim(%d) {\n", b));

// In case of no free blocks (after sudden power off) or if the file system
// is near full we risk to be reentered (infinity recursively loop) and
// we can not allow that, so just return.
	if (is_reclaim_running == 1) {
		tw(tr(TR_END, TrDReclaim, "} (reenteret skip reclaim) 0\n"));
		return EFFS_RECLAIMLOOP;
	}

	is_reclaim_running = 1;

    // If there are more objects in this block than there are remaining
    // free inodes, we have to make an inodes_reclaim() first.
    tw(tr(TR_FUNC, TrDReclaim,
          "block_objects, fs.inodes_max, inodes: used, free\n"));
    tw(tr(TR_FUNC, TrDReclaim,
          "%10d, %13d, %15d, %4d\n",
          bstat[b].objects,
          fs.inodes_max, bstat[fs.inodes].used,
          fs.inodes_max - (bstat[fs.inodes].used + bstat[fs.inodes].lost)));

    if (bstat[b].objects >= (fs.inodes_max - (bstat[fs.inodes].used + 
							 bstat[fs.inodes].lost + FFS_INODES_MARGIN))) {
        tw(tr(TR_FUNC, TrInode, "NOTE: Will run out of free inodes...\n"));
        inodes_reclaim();
    }

    // Allocate a new block. NOTE: we don't return an error because if we
	// get in the situation where we don't have any free blocks is this the
	// only way to recover.
    if ((result = block_alloc(1, BF_DATA)) < 0) {
        tw(tr(TR_FUNC, TrAll, "WARNING: block_alloc failed\n"));
    }

	BLOCK_RECLAIM_TEST(BLOCK_RECLAIM_ALLOC, "Oops after ffs_block_alloc()");

    // If there are any objects at all to reclaim...
    if (bstat[b].objects > 0)
    {
		BLOCK_RECOVER_TEST_INIT(BLOCK_RECOVER_OBJECTS, "Dummy")
        // Save the current journal state
        if (journal_push() != EFFS_OK) {
			is_reclaim_running = 0;       // NOTEME: change to goto?
			return EFFS_CORRUPTED;
		}

        // We simulate that this block is completely full, such that we
        // don't relocate files to the end of the block
        used_old = bstat[b].used;
        lost_old = bstat[b].lost;  // For statistics
        bstat[b].used = dev.blocksize - 1;


        // Compute lower (inclusive) and upper (exclusive) bounds of the
        // location of files in this block
        lower = offset2location(dev.binfo[b].offset);
        upper = offset2location(dev.binfo[b].offset + dev.blocksize);

        tw(tr(TR_FUNC, TrDReclaim, "Block addr range = 0x%X..0x%X\n",
              location2offset(lower), location2offset(upper)));

		// This is the only time we are allowed to use the reserved 
		org_block_files_reserved= fs.block_files_reserved;
		fs.block_files_reserved = 0;

		org_res_space = fs.reserved_space;
        fs.reserved_space = RESERVED_NONE;

		ip = inode_addr(1);
        for (i = 1, n = 0; i < fs.inodes_max; i++, ip++)
        {
			BLOCK_RECOVER_TEST(BLOCK_RECOVER_OBJECTS, "Oops before relocate all objects")
            // Ensure object is valid and within the block to be reclaimed
            if (is_object_valid(ip) &&