www.pudn.com > efs.rar > fs_pm_gc.c
/**********************************************************************
fs_pm_gc.c
Garbage collector.
Copyright (c) 2003 -- 2006 by QUALCOMM Incorporated. All Rights Reserved.
***********************************************************************/
/*===========================================================================
EDIT HISTORY FOR MODULE
This section contains comments describing changes made to the module.
Notice that changes are listed in reverse chronological order.
$Header: //depot/asic/MSMSHARED/services/efs/MSM_EFS.01.02/fs_pm_gc.c#4 $ $DateTime: 2006/09/20 14:10:00 $ $Author: davidb $
when who what, where, why
-------- --- ------------------------------------------------------
2006-09-20 dlb Lint cleanup.
2006-09-11 dlb Use flash driver wrappers.
2005-05-26 sd Compilation fixes for L4.
2004-10-15 dlb Update copyright line.
2004-10-07 dlb Whitespace cleanup.
2004-05-05 dlb Handle page write failures in data region.
2004-04-20 dlb Fix problem with startups and no transactions.
2003-06-17 bgc Added code to log garbage that was created during the
last bad powerdown.
2003-06-13 cr Change fs_gc_do_urgent if statment to a while statement
to fix assert(gc->free_count>0) failure in fs_gc_alloc().
2003-03-07 dlb Created file.
===========================================================================*/
#include
#ifdef FEATURE_IG_EFS_EXT_SERVER
#include "amssassert.h"
#else
#include "assert.h"
#endif
#include "fs_err.h"
#include "fs_pm_gc.h"
#include "fs_pm_types.h"
#ifdef FS_UNIT_TEST
#error code not present
#endif
/* If used by shared code, need to implement these parts. */
#define ISNAND 1
#define BUMP_PAGE(gc, pvar) \
do { \
(pvar)++; \
if ((pvar) >= (gc)->max_page) \
(pvar) = (gc)->min_page; \
} while (0)
#define BUMP_BLOCK(gc, pvar) \
do { \
(pvar) = ((pvar) & (gc)->super->block_mask) + \
(gc)->super->data.block_size; \
if ((pvar) >= (gc)->max_page) \
(pvar) = (gc)->min_page; \
} while (0)
void
fs_gc_init (
fs_gc_t gc,
int fresh_start
)
{
(void) fresh_start;
if (fresh_start) {
gc->gc_next = gc->min_page;
gc->alloc_next = gc->min_page;
gc->free_count = 0;
gc->state = FS_GC_HEAD;
if (ISNAND) {
/* XXX: For the ptable region, we do not need to pre-erase anything.
* This will need to be done to kick-start the GC once this code is
* shared with the data region. */
} else {
FS_ERR_FATAL ("NOR generic GC code not supported", 0, 0, 0);
}
} else {
/* Get the initial values from the superblock. They will be adjusted
* as logs are replayed. */
}
}
static int
fs_gc_urgency (fs_gc_t gc)
{
if (gc->free_count <
4 * gc->super->data.block_size + 2 + FS_MAX_TRANSACTION_SIZE)
return 80;
else
return 0;
}
static int
fs_gc_count_garbage (fs_gc_t gc, page_id base)
{
page_id limit = base + gc->super->data.block_size;
int count = 0;
for (; base < limit; base++) {
switch (gc->get_reverse (gc->priv, base)) {
case FS_RMAP_PAGE_GARBAGE:
case FS_RMAP_PAGE_LOG:
case FS_RMAP_PAGE_SUPER:
count++;
break;
default:
break;
}
}
return count;
}
static void
fs_gc_single (fs_gc_t gc)
{
page_id pstate;
page_id dest;
int count;
int result;
int moved;
uint32 args[3];
while (1) {
switch (gc->state) {
case FS_GC_HEAD:
/* The head state comes in only when the page is at the beginning
* of a block. */
pstate = gc->get_reverse (gc->priv, gc->gc_next);
switch (pstate) {
case FS_RMAP_BLOCK_UNKNOWN:
/* Check if this block is good. */
if (fs_flash_bad_block_check (gc->dev,
gc->gc_next >> gc->super->block_shift))
{
gc->set_reverse (gc->priv, gc->gc_next, FS_RMAP_BLOCK_BAD);
BUMP_BLOCK (gc, gc->gc_next);
} else {
gc->state = FS_GC_ERASE;
}
break;
case FS_RMAP_BLOCK_BAD:
BUMP_BLOCK (gc, gc->gc_next);
break;
default:
/* Count up the garbage in this page. */
count = fs_gc_count_garbage (gc, gc->gc_next);
if (count == 0)
BUMP_BLOCK (gc, gc->gc_next);
else
gc->state = FS_GC_MOVING;
}
break;
case FS_GC_MOVING:
pstate = gc->get_reverse (gc->priv, gc->gc_next);
moved = 0;
switch (pstate) {
case FS_RMAP_PAGE_GARBAGE:
break;
default:
if (FS_RMAP_IS_SPECIAL (pstate)) {
dest = fs_gc_alloc (gc);
result = fs_flash_read_page (gc->dev, gc->gc_next,
gc->realloc_buffer,
FS_FOP_PTABLE_GC_MOVE);
if (result != FS_DEVICE_OK)
FS_ERR_FATAL ("Error reading from device", 0, 0, 0);
result = fs_flash_write_page (gc->dev, dest, gc->realloc_buffer,
FS_FOP_PTABLE_GC_MOVE);
if (result != FS_DEVICE_OK)
FS_ERR_FATAL ("Error writing to device", 0, 0, 0);
gc->page_move (gc->priv, pstate, gc->gc_next, dest);
moved = 1;
} else {
FS_ERR_FATAL ("Unknown block encountered: %08x",
pstate, 0, 0);
}
}
if (((gc->gc_next + 1) & (~gc->super->block_mask)) == 0) {
gc->state = FS_GC_ERASE;
} else {
BUMP_PAGE (gc, gc->gc_next);
}
if (moved)
return;
break;
case FS_GC_ERASE:
fs_log_flush (gc->log);
args[0] = gc->gc_next >> gc->super->block_shift;
result = fs_flash_erase_block (gc->dev, args[0], FS_FOP_PTABLE);
if (result != FS_DEVICE_OK) {
(void) fs_flash_mark_block_bad (gc->dev, args[0]);
fs_log_add (gc->log, FS_LOG_ENTRY_ERASE_FAIL, args);
fs_log_flush (gc->log);
gc->set_reverse (gc->priv,
gc->gc_next & gc->super->block_mask,
FS_RMAP_BLOCK_BAD);
gc->state = FS_GC_HEAD;
BUMP_BLOCK (gc, gc->gc_next);
} else {
fs_log_add (gc->log, FS_LOG_ENTRY_ERASE_FINISH, args);
gc->state = FS_GC_HEAD;
/* XXX: What to bump the erase count by? These are quite
* intertwined. */
gc->free_count += gc->erase (gc->priv,
gc->gc_next >> gc->super->block_shift);
BUMP_BLOCK (gc, gc->gc_next);
/* A unit of work is done, so return. */
return;
}
break;
default:
FS_ERR_FATAL ("Internal state error", 0, 0, 0);
}
}
}
page_id
fs_gc_alloc (fs_gc_t gc)
{
page_id state;
page_id target;
ASSERT (gc->free_count > 0);
/* Loop until we return a result. */
while (1) {
state = gc->get_reverse (gc->priv, gc->alloc_next);
switch (state) {
case FS_RMAP_BLOCK_ERASED:
if (((gc->alloc_next & (~gc->super->block_mask)) == 0
&& 0))
{
FS_ERR_FATAL ("NOR CODE", 0, 0, 0);
} else {
gc->mark_alloc (gc->priv, gc->alloc_next);
target = gc->alloc_next;
BUMP_PAGE (gc, gc->alloc_next);
gc->free_count--;
return target;
}
break;
default:
BUMP_BLOCK (gc, gc->alloc_next);
}
}
}
int
fs_gc_do_urgent (fs_gc_t gc)
{
int did_something = 0;
while (fs_gc_urgency (gc) >= 80) {
fs_gc_single (gc);
did_something = 1;
}
return did_something;
}
void
fs_gc_visit_node (fs_gc_t gc, fs_log_code_t code, uint32 *args)
{
page_id page;
switch (code) {
case LOG_CODE_GROUP_END:
case FS_LOG_ENTRY_UPPER_DATA:
case FS_LOG_ENTRY_XACT_START:
case FS_LOG_ENTRY_XACT_END:
case FS_LOG_ENTRY_GC_MOVE:
case FS_LOG_ENTRY_PAGE_MOVE:
case FS_LOG_ENTRY_NEW_DATA:
case FS_LOG_ENTRY_KEYRANGE:
case FS_LOG_ENTRY_GC_DEALLOC:
break;
case FS_LOG_ENTRY_GARBAGE:
page = args[0];
if (page >= gc->min_page && page < gc->max_page) {
gc->set_reverse (gc->priv, page, FS_RMAP_PAGE_GARBAGE);
gc->alloc_next = page;
BUMP_PAGE (gc, gc->alloc_next);
}
break;
case FS_LOG_ENTRY_ERASE_FINISH:
/* args[0] = block */
(void) gc->erase (gc->priv, args[0]);
page = args[0] << gc->super->block_shift;
if (page >= gc->min_page && page < gc->max_page) {
gc->gc_next = page;
BUMP_BLOCK (gc, gc->gc_next);
}
break;
case FS_LOG_ENTRY_ERASE_FAIL:
/* args[0] = block */
page = args[0] << gc->super->block_shift;
if (page >= gc->min_page && page < gc->max_page) {
gc->set_reverse (gc->priv, page, FS_RMAP_BLOCK_BAD);
}
break;
case FS_LOG_ENTRY_WRITE_FAIL:
/* args[0] = page */
page = args[0];
if (page >= gc->min_page && page < gc->max_page) {
gc->set_reverse (gc->priv, page, FS_RMAP_BLOCK_BAD);
}
break;
case FS_LOG_ENTRY_PTABLE_MOVE:
/* args[0] = state
* args[1] = old_place
* args[2] = new_place
*/
if (args[2] >= gc->min_page && args[2] < gc->max_page) {
/* printf ("ptmove %04x %8x %8x\n",
args[0], args[1], args[2]); */
gc->page_move (gc->priv, args[0], args[1], args[2]);
gc->alloc_next = args[2];
BUMP_PAGE (gc, gc->alloc_next);
/*
gc->gc_next = args[1];
BUMP_PAGE (gc, gc->gc_next);
*/
} else
FS_ERR_FATAL ("Unknown region", 0, 0, 0);
break;
case FS_LOG_ENTRY_LOG_FLUSH:
break;
default:
FS_ERR_FATAL ("Unknown log code: 0x%02x", code, 0, 0);
break;
}
}
/* Note, this assumes it only gets called when we aren't doing a fresh
* start. */
void
fs_gc_init_finish (fs_gc_t gc)
{
page_id tmp_page, tmp_stop, state;
uint32 args[3];
/* Advance the alloc_next value past any partially written data. Only
* advance it possibly to the beginning of the next block, since the
* state will recover that situation ???. */
while (!fs_flash_is_erased (gc->dev, gc->alloc_next)) {
/* If we're at the start of a block, make sure we find a block that
* should be erased. */
while ((gc->alloc_next & ~gc->super->block_mask) == 0
&& gc->get_reverse (gc->priv, gc->alloc_next)
!= FS_RMAP_BLOCK_ERASED)
{
BUMP_BLOCK (gc, gc->alloc_next);
}
/* Mark it as garbage, then. */
gc->set_reverse (gc->priv, gc->alloc_next, FS_RMAP_PAGE_GARBAGE);
args[0] = gc->alloc_next;
fs_log_add (gc->log, FS_LOG_ENTRY_GARBAGE, args);
BUMP_PAGE (gc, gc->alloc_next);
}
/* Set the following page to be erased if necessary. Don't mark the
* state if we wrapped to the beginning of a new block. */
if ((gc->alloc_next & ~gc->super->block_mask) > 0) {
gc->set_reverse (gc->priv, gc->alloc_next,
FS_RMAP_BLOCK_ERASED);
}
/* Recompute the free count. */
gc->free_count = 0;
tmp_page = gc->alloc_next;
tmp_stop = gc->gc_next & gc->super->block_mask;
while (tmp_page != tmp_stop) {
state = gc->get_reverse (gc->priv, tmp_page);
if (state == FS_RMAP_BLOCK_ERASED) {
/* ASSUMES NAND. */
gc->free_count += gc->super->data.block_size -
(tmp_page & ~gc->super->block_mask);
}
BUMP_BLOCK (gc, tmp_page);
}
if ((gc->gc_next & ~gc->super->block_mask) == 0)
gc->state = FS_GC_HEAD;
else
gc->state = FS_GC_MOVING;
}