FreeCalypso > hg > fc-tourmaline
diff src/cs/drivers/drv_app/ffs/board/reclaim.c @ 0:4e78acac3d88
src/{condat,cs,gpf,nucleus}: import from Selenite
author | Mychaela Falconia <falcon@freecalypso.org> |
---|---|
date | Fri, 16 Oct 2020 06:23:26 +0000 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/cs/drivers/drv_app/ffs/board/reclaim.c Fri Oct 16 06:23:26 2020 +0000 @@ -0,0 +1,883 @@ +/****************************************************************************** + * 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 (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) +{ + 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_COMMIT_TEST(BLOCK_COMMIT_BEFORE, "Oops before commit"); + + block_flags_write(oldinodes, 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); + + bstat[fs.newinodes].lost = 0; + bstat[fs.newinodes].objects = 1; + inodes_set(fs.newinodes); + + // Free old inodes block + block_free(oldinodes); + + BLOCK_COMMIT_TEST(BLOCK_COMMIT_OLD_FREE, "Oops after freeing old block"); + + BLOCK_COMMIT_TEST(BLOCK_COMMIT_AFTER, "Oops after commit"); + + 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(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; + 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 { + // 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 this is 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) && + lower <= ip->location && ip->location < upper) + { + if ((result = object_relocate(i)) < 0) { + tw(tr(TR_FUNC, TrAll, "FATAL object_relocate failed\n")); + break; + } + + // If we reclaim a segment head or wch that is in use we must + // update the file descriptor as well + for (j = 0; j < fs.fd_max; j++) { + if (i == fs.fd[j].seghead) { + tw(tr(TR_FUNC, TrDReclaim, + "Updated seghead %d -> %d \n", + fs.fd[j].seghead, result)); + fs.fd[j].seghead = result; + } + if (i == fs.fd[j].wch) { + tw(tr(TR_FUNC, TrDReclaim, + "Updated wch %d -> %d \n", + fs.fd[j].wch, result)); + fs.fd[j].wch = result; + } + } + + // If we have just reclaimed an object which we started on + // updating we must also update ojournal + if (i == fs.ojournal.oldi) { + struct inode_s *ip = inode_addr(result); + tw(tr(TR_FUNC, TrDReclaim, + "Updated ojournal oldi %d -> %d \n", + fs.ojournal.oldi, result)); + fs.ojournal.oldi = result; + fs.ojournal.location = ip->location; + } + + if (i == fs.ojournal.diri || i == -fs.ojournal.diri) { + fs.ojournal.diri = (fs.ojournal.diri < 0 ? -result : result); + tw(tr(TR_FUNC, TrDReclaim, + "Updated ojournal: diri %d -> %d \n", + i, fs.ojournal.diri)); + } + + if (i == fs.ojournal.repli || i == -fs.ojournal.repli) { + fs.ojournal.repli = (fs.ojournal.repli < 0 ? -result : result); + tw(tr(TR_FUNC, TrDReclaim, + "Updated ojournal: repli %d -> %d \n", + i, fs.ojournal.repli)); + } + + if (i == fs.i_backup || i == -fs.i_backup) { + fs.i_backup = (fs.i_backup < 0 ? -result : result); + tw(tr(TR_FUNC, TrDReclaim, + "Updated i_backup: %d -> %d \n", i, fs.i_backup)); + } + + n++; + } + } + + fs.block_files_reserved = org_block_files_reserved; // Restore + fs.reserved_space = org_res_space; + + tw(tr(TR_FUNC, TrDReclaim, "Reclaimed %d objects\n", n)); + if (result >= 0) + result = n; // We return number of objects relocated + + if (i < fs.inodes_max) { + // We did not finish, so restore the old bstat[].used of the block. + bstat[b].used = used_old; + tw(tr(TR_FUNC, TrAll, + "WARNING: data_block_reclaim() not completed\n")); + result = EFFS_DBR; + } + + // Restore the saved journal state + if (journal_pop() != EFFS_OK) { + is_reclaim_running = 0; // NOTEME: change to goto? + return EFFS_CORRUPTED; + } + } + BLOCK_RECLAIM_TEST(BLOCK_RECLAIM_NO_CLEAN, "Oops before clean old data block"); + + if (result >= 0) { + // Clean the block (remove all inodes that refer to this block) + block_flags_write(b, BF_CLEANING); + block_clean(b); + + statistics_update_drec(used_old - lost_old, lost_old, candidate); + + BLOCK_RECLAIM_TEST(BLOCK_RECLAIM_CLEANING, "Oops before free old data block"); + + // Free the old block + block_free(b); + } + + is_reclaim_running = 0; + + tw(tr(TR_END, TrDReclaim, "} (data_block_reclaim) %d\n", result)); + ttw(ttr(TTrRec, "} %d" NL, result)); + + return result; +} + +// Relocate object represented by inode reference <i>. +iref_t object_relocate(iref_t oldi) +{ + iref_t newi; + struct inode_s *oldip; + char *olddata, *oldname; + int oldsize; + + tw(tr(TR_BEGIN, TrReclaimLow, "object_relocate(%d) {\n", oldi)); + + journal_begin(oldi); + + oldip = inode_addr(oldi); + + oldsize = segment_datasize(oldip); + olddata = offset2addr(location2offset(oldip->location)); + oldname = addr2name(olddata); + olddata = addr2data(olddata, oldip); + + if (is_object(oldip, OT_SEGMENT)) + newi = segment_create(olddata, oldsize, -oldi); + else { + // root inode is a special case + if (*oldname == '/') + newi = object_create(oldname, olddata, oldsize, 0); + else + newi = object_create(oldname, olddata, oldsize, oldi); + } + + if (newi < 0) { + tw(tr(TR_END, TrReclaimLow, "} %d\n", newi)); + return newi; + } + + // root inode is a special case + if ((*oldname == '/') && !is_object(oldip, OT_SEGMENT)) { + tw(tr(TR_FUNC, TrDReclaim, "Relocating fs.root: %d->%d\n", oldi, newi)); + fs.root = newi; + } + + journal_end(0); + + tw(tr(TR_END, TrReclaimLow, "} %d\n", newi)); + + return newi; +} + +// Clean a block, eg. erase all inodes that refer to this block. +iref_t block_clean(bref_t b) +{ + iref_t i, n; + struct inode_s *ip; + offset_t lower, upper; + + tw(tr(TR_FUNC, TrDReclaim, "block_clean(%d) { ", b)); + + // 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, "offset range = 0x%X..0x%X: ", lower, upper)); + + ip = inode_addr(1); + for (i = 1, n = 0; i < fs.inodes_max; i++, ip++) + { + // Ensure object is within the block to be reclaimed. Note: if ffs + // is conf. with 1MB or above will all not used inodes default have + // the location to FFFF which will trigger a clean and make a error! + if (lower <= ip->location && upper > ip->location) + { + tw(tr(TR_NULL, TrReclaimLow, "%d ", i)); + // Set the size to zero so it won't be counted in ffs_initialize() + ffsdrv.write_halfword((uint16 *) &ip->size, 0); + n++; + } + } + tw(tr(TR_NULL, TrDReclaim, "} %d\n", n)); + + return n; +} + + +/****************************************************************************** + * Main and block reclaim + ******************************************************************************/ + +// Reclaim (erase) all blocks that are marked as invalid/reclaimable. Each +// time a block is erased, its age is incremented so as to support wear +// levelling. Also, the global age limits are updated. FIXME: Should we +// avoid having ffs_initialize() do a block_reclaim() because it delays reboot?. +int blocks_reclaim(void) +{ + bref_t b, n, b_lost_space; + int blocks_free = 0, lost_space; + + int free_space, b_free_space; + + tw(tr(TR_BEGIN, TrBlock, "blocks_reclaim() {\n")); + ttw(str(TTrRec, "blocks_reclaim() {" NL)); + + // Testing of fs.testflags is for the sake of testing block_commit() + if ((fs.testflags & BLOCK_COMMIT_BASE) != 0) { + tw(tr(TR_FUNC, TrBlock, "Bailing out because fs.testflags = 0x%X\n", + fs.testflags)); + } + else { + for (b = 0, n = 0; b < dev.numblocks; b++) { + if (is_block_flag(b, BF_LOST)) { + block_reclaim(b); + n++; + } + if (is_block(b, BF_IS_FREE)) { + blocks_free++; + } + } + } + + // If the number of free blocks is less than fs.blocks_free_min we + // call data_block_reclaim(). We will reclaim the block with most lost + // space. This should only happend if we got a sudden power off/reset + // while we reclaimed a block. + if (blocks_free < fs.blocks_free_min) { + lost_space = 0; + free_space = 0; + + // We most never reclaim the block with most free space because this + // is the only block we can relocate the objects to. + for (b = 0; b < dev.numblocks; b++) { + if (is_block_flag(b, BF_DATA)) { + if ((dev.blocksize - bstat[b].used) > free_space) { + free_space = dev.blocksize - bstat[b].used; + b_free_space = b; + } + } + } + tw(tr(TR_FUNC, TrBlock, "most free space: %d in block: %d \n", + free_space, b_free_space)); + + for (b = 0; b < dev.numblocks; b++) { + if (is_block_flag(b, BF_DATA) && b != b_free_space) { + if (bstat[b].lost > lost_space) { + lost_space = bstat[b].lost; + b_lost_space = b; + } + } + } + tw(tr(TR_FUNC, TrBlock, "most lost space: %d in block: %d \n", + lost_space, b_lost_space)); + + data_block_reclaim(b_lost_space, MOST_LOST); + } + tw(tr(TR_END, TrBlock, "} %d\n", n)); + ttw(ttr(TTrRec, "} %d" NL, n)); + + return n; +} + +int block_reclaim(bref_t b) +{ + age_t age; + struct block_header_s *bhp; + + tw(tr(TR_BEGIN, TrBlock, "block_reclaim(%d) {\n", b)); + + // In ffs_initialize() we set fs.initerror = EFFS_INVALID while we call + // blocks_fsck(). We test for that condition now, in order to avoid + // doing sector erases that will delay the whole target boot process. + if (fs.initerror == EFFS_INVALID) { + tw(tr(TR_END, TrBlock, "} %d\n", fs.initerror)); + return fs.initerror; + } + + // Testing of fs.testflags is for the sake of testing block_commit() + if ((fs.testflags & BLOCK_COMMIT_BASE) != 0 && + fs.testflags != BLOCK_COMMIT_OLD_FREE) { + tw(tr(TR_FUNC, TrBlock, "Bailing out because fs.testflags = 0x%X\n", + fs.testflags)); + } + else { + // We must read block's age before we erase it. + bhp = (struct block_header_s *) offset2addr(dev.binfo[b].offset); + age = bhp->age; + ffsdrv.erase(b); + block_preformat(b, age); + } + + tw(tr(TR_END, TrBlock, "} %d\n", 0)); + + return 0; +}