fatfs_ncache.c

该工程是从ecos嵌入式系统下移植过来的一个小型的fat16文件系统

node_hash_check(fatfs_hash_table_t *tbl)
{
    int i, n;

    n = 0;
    for (i = 0; i < tbl->size; i++)
    {
        fatfs_node_t *lnode, *pnode;

        pnode = NULL;
        lnode = tbl->nodes[i];

        while (lnode != NULL)
        {
            if (pnode != NULL)
            {
                int c = strcasecmp(pnode->filename, lnode->filename);
                CYG_ASSERT(c <= 0, "hash table not sorted");
                CYG_ASSERT(pnode->parent_cluster != lnode->parent_cluster ||
                           0 != c, "duplicated node in hash table");
            }
            n++;
            pnode = lnode;
            lnode = lnode->hash_next;
        }
    }
    CYG_ASSERTC(tbl->n == n);
}

static void
node_hash_not_found_check(fatfs_disk_t *disk, 
                          const char   *name,
                          unsigned int  namelen,
                          unsigned int  parent_cluster)
{
    fatfs_node_t* node;

    node = node_list_get_head(&disk->live_nlist);
    while (NULL != node)
    {
        if (node->parent_cluster == parent_cluster          &&
            namelen == strlen(node->filename)               &&
            0 == strncasecmp(name, node->filename, namelen))
            CYG_ASSERT(false, "node not found in hash, "
                              "but exists in live list");
        node = node_list_get_next(node);
    }

    node = node_list_get_head(&disk->dead_nlist);
    while (NULL != node)
    {
        if (node->parent_cluster == parent_cluster          &&
            namelen == strlen(node->filename)               &&
            0 == strncasecmp(name, node->filename, namelen))
            CYG_ASSERT(false, "node not found in hash, "
                              "but exists in dead list");
        node = node_list_get_next(node);
    }   
}

static void
node_hash_found_check(fatfs_disk_t *disk, 
                      const char   *name,
                      unsigned int  namelen,
                      unsigned int  parent_cluster,
                      fatfs_node_t* node)
{
    fatfs_node_t* n;

    n = node_list_get_head(&disk->live_nlist);
    while (NULL != n)
    {
        if (n == node) 
        {
            if (node->parent_cluster != parent_cluster ||
                namelen != strlen(node->filename)      ||
                0 != strncasecmp(name, node->filename, namelen))
                CYG_ASSERT(false, "node_hash_find returned wrong node");
            return;
        }
        n = node_list_get_next(n);
    }

    n = node_list_get_head(&disk->dead_nlist);
    while (NULL != n)
    {
        if (n == node)
        {
            if (node->parent_cluster != parent_cluster ||
                namelen != strlen(node->filename)      ||
                0 != strncasecmp(name, node->filename, namelen))
                CYG_ASSERT(false, "node_hash_find returned wrong node");
            return;
        } 
        n = node_list_get_next(n);
    }

    CYG_ASSERT(false, "node not found in dead or live lists, "
                      "but exists in hash.");
}
#endif // USE_XCHECKS
    
//--------------------------------------------------------------------------

#ifdef USE_XCHECKS

# define SANITY_CHECK()                                                     \
    CYG_MACRO_START                                                         \
        node_lists_check(disk);                                             \
        node_hash_check(&disk->node_hash);                                  \
        CYG_ASSERTC((disk->live_nlist.size + disk->dead_nlist.size) ==      \
                    disk->node_hash.n);                                     \
    CYG_MACRO_END    

# define NODE_FIND_CHECK()                                                    \
    CYG_MACRO_START                                                           \
        if (NULL == node)                                                     \
            node_hash_not_found_check(disk, name, namelen, parent_cluster);   \
        else                                                                  \
            node_hash_found_check(disk, name, namelen, parent_cluster, node); \
    CYG_MACRO_END

#else // USE_XCHECKS
# define SANITY_CHECK()    CYG_EMPTY_STATEMENT
# define NODE_FIND_CHECK() CYG_EMPTY_STATEMENT
#endif // not USE_XCHECKS

//==========================================================================
//==========================================================================
// Exported functions 

//--------------------------------------------------------------------------
// fatfs_node_cache_init()
// Initializes node cache of given disk.

void
fatfs_node_cache_init(fatfs_disk_t *disk)
{
    CYG_CHECK_DATA_PTRC(disk);
    
    node_list_init(&disk->live_nlist);
    node_list_init(&disk->dead_nlist);
    node_hash_init(&disk->node_hash);

    SANITY_CHECK();
}

//--------------------------------------------------------------------------
// fatfs_node_cache_flush()
// Frees all node cache of given disk.

void
fatfs_node_cache_flush(fatfs_disk_t *disk)
{
    fatfs_node_t *node, *next_node;
 
    node = node_list_get_head(&disk->live_nlist);

    while (NULL != node)
    {
        next_node = node_list_get_next(node);
        node_list_remove(&disk->live_nlist, node);
        if (!node_hash_remove(&disk->node_hash, node))
            CYG_ASSERT(false, "Node not in hash");
        fatfs_tcache_flush(disk, &node->tcache);
        free(node);
        node = next_node;
    }

    node = node_list_get_head(&disk->dead_nlist);

    while (NULL != node)
    {
        next_node = node_list_get_next(node);
        node_list_remove(&disk->dead_nlist, node);
        if (!node_hash_remove(&disk->node_hash, node))
            CYG_ASSERT(false, "Node not in hash");
        fatfs_tcache_flush(disk, &node->tcache);
        free(node);
        node = next_node;
    }

    SANITY_CHECK();
}

//--------------------------------------------------------------------------
// fatfs_node_alloc()
// Allocates a new node.  

fatfs_node_t*
fatfs_node_alloc(fatfs_disk_t *disk, fatfs_node_t *node_data)
{
    int lsize, dsize;
    fatfs_node_t *anode;

    CYG_CHECK_DATA_PTRC(disk);
    CYG_CHECK_DATA_PTRC(node_data);
 
    lsize = node_list_get_size(&disk->live_nlist);
    dsize = node_list_get_size(&disk->dead_nlist);
   
    printf( "lsize=%d dsize=%d", lsize, dsize);
    
    // Allocate space for a new node if we haven't reached the 
    // allocation treshold or if we can't reuse dead nodes space
    if (dsize > DLIST_KEEP_NUM && (lsize + dsize) >= 
        (FATFS_NODE_ALLOC_THRESHOLD - 1))
        anode = NULL;
    else
        anode = (fatfs_node_t *)malloc(sizeof(fatfs_node_t));
        
    if (NULL == anode)
    {
        printf( "getting node from dead list");
        
        if (dsize <= DLIST_KEEP_NUM)
            return NULL;
        
        anode = node_list_tail_get(&disk->dead_nlist);
        if (NULL == anode)
            return NULL;
        
        printf( "recycling node='%s'", anode->filename); 

        // Flush FAT table cache
        fatfs_tcache_flush(disk, &anode->tcache);
        
        node_list_remove(&disk->dead_nlist, anode);
        if (!node_hash_remove(&disk->node_hash, anode))
            CYG_ASSERT(false, "Node not in hash");
    }     

    // Init new node    
    *anode = *node_data;
    anode->refcnt = 0;

    // Init FAT table cache
    fatfs_tcache_init(disk, &anode->tcache);

    node_list_head_add(&disk->dead_nlist, anode);
    if (!node_hash_add(&disk->node_hash, anode))
        CYG_ASSERT(false, "Node already in hash");

    SANITY_CHECK();

    return anode;
}

//--------------------------------------------------------------------------
// fatfs_node_touch()
// Moves given node to top of its list.
// (When reusing dead node it is always taken from the bottom of list) 

void
fatfs_node_touch(fatfs_disk_t *disk, fatfs_node_t *node)
{
    CYG_CHECK_DATA_PTRC(disk);
    CYG_CHECK_DATA_PTRC(node);
    printf( "node='%s' refcnt=%d", node->filename, node->refcnt);

    if (node->refcnt == 0)
    {
        node_list_remove(&disk->dead_nlist, node);
        node_list_head_add(&disk->dead_nlist, node);
    }
    else
    {
        node_list_remove(&disk->live_nlist, node);
        node_list_head_add(&disk->live_nlist, node);
    } 

    SANITY_CHECK();
}

//--------------------------------------------------------------------------
// fatfs_node_ref()
// Increases the given node reference count.
// If the reference goes from 0 to 1, than the node
// is moved from dead list to live list.

void
fatfs_node_ref(fatfs_disk_t *disk, fatfs_node_t *node)
{
    CYG_CHECK_DATA_PTRC(disk);
    CYG_CHECK_DATA_PTRC(node);
    printf( "node='%s' refcnt=%d", node->filename, node->refcnt);
    
    // Increase node reference counter
    node->refcnt++;    
    if (1 == node->refcnt)
    {
        printf( "node='%s' to live list", node->filename);
        // First reference - move node from dead to live list
        node_list_remove(&disk->dead_nlist, node);
        node_list_head_add(&disk->live_nlist, node);
    }

    SANITY_CHECK();
}

//--------------------------------------------------------------------------
// fatfs_node_unref()
// Decreases the given node reference count.
// If the reference goes from 1 to 0, than the node
// is moved from live list to top of dead list.
// (When reusing dead node it is always taken from the bottom of list)
// If we are over the allocation treshold the bottom node of
// dead list if freed.

void
fatfs_node_unref(fatfs_disk_t *disk, fatfs_node_t *node)
{
    CYG_CHECK_DATA_PTRC(disk);
    CYG_CHECK_DATA_PTRC(node);
    printf( "node='%s' refcnt=%d", node->filename, node->refcnt);
    CYG_ASSERT(node->refcnt > 0, "node->refcnt <= 0");

    node->refcnt--;
    if (node->refcnt == 0)
    {
        // No more references - move node from live to dead list
        printf( "node='%s' to dead list", node->filename);
        node_list_remove(&disk->live_nlist, node);
        node_list_head_add(&disk->dead_nlist, node);

        // Check the number of allocated nodes and free 
        // the last node in dead list if we are over 
        // the treshold and we have enough dead nodes
        {
            int lsize = node_list_get_size(&disk->live_nlist);
            int dsize = node_list_get_size(&disk->dead_nlist);
   
            if (dsize > DLIST_KEEP_NUM && 
                (lsize + dsize) >= FATFS_NODE_ALLOC_THRESHOLD) 
            {
                fatfs_node_t *n = node_list_get_tail(&disk->dead_nlist);
                printf( "freeing node='%s' - to satisfy "
                                "alloc treshold", n->filename);
                fatfs_node_free(disk, n);
            }
        }
    }

    SANITY_CHECK();
}

//--------------------------------------------------------------------------
// fatfs_node_free()
// Frees node memory and removes it from its list and hash. 
// This function must not be called on a referenced node.

void
fatfs_node_free(fatfs_disk_t *disk, fatfs_node_t *node)
{
    CYG_CHECK_DATA_PTRC(disk);
    CYG_CHECK_DATA_PTRC(node);
    printf( "node='%s' refcnt=%d", node->filename, node->refcnt);
    CYG_ASSERTC(node->refcnt == 0);
    CYG_ASSERTC(node != disk->root);

    // Flush FAT table cache    
    fatfs_tcache_flush(disk, &node->tcache);

    // Remove from dead list and from hash and free ptr
    node_list_remove(&disk->dead_nlist, node);
    if (!node_hash_remove(&disk->node_hash, node))
        CYG_ASSERT(false, "node not in hash");    
    free(node);

    SANITY_CHECK();
}

//--------------------------------------------------------------------------
// fatfs_node_rehash()
// Recalculates given node hash key. 

void
fatfs_node_rehash(fatfs_disk_t *disk, fatfs_node_t *node)
{
    CYG_CHECK_DATA_PTRC(disk);
    CYG_CHECK_DATA_PTRC(node);
    
    if (!node_hash_remove_keyless(&disk->node_hash, node))
        CYG_ASSERT(false, "Node not in hash");
    
    if (!node_hash_add(&disk->node_hash, node))
        CYG_ASSERT(false, "Node already in hash");
    
    SANITY_CHECK();
}

//--------------------------------------------------------------------------
// fatfs_node_find()
// Finds node in hash by its name and parent cluster. 
// If no node found NULL is returned.

fatfs_node_t*
fatfs_node_find(fatfs_disk_t *disk, 
                const char   *name, 
                unsigned int  namelen,
                unsigned int  parent_cluster)
{
    fatfs_node_t *node;

    CYG_CHECK_DATA_PTRC(disk);
    CYG_CHECK_DATA_PTRC(name);
 
    node = node_hash_find(&disk->node_hash, name, namelen, parent_cluster);

    NODE_FIND_CHECK();
    
    printf( "node name=%s pcluster=%d %s found in cache\n",
        name, parent_cluster, ((node != NULL) ? "" : "not"));
    
    return node;
}

//--------------------------------------------------------------------------
// fatfs_get_live_node_count()
// Gets the number of live nodes.

int
fatfs_get_live_node_count(fatfs_disk_t *disk)
{
    return node_list_get_size(&disk->live_nlist);
}

//--------------------------------------------------------------------------
// fatfs_get_dead_node_count()
// Gets the number of dead nodes.

int
fatfs_get_dead_node_count(fatfs_disk_t *disk)
{
    return node_list_get_size(&disk->dead_nlist);
}

//--------------------------------------------------------------------------
// fatfs_node_flush_dead_tcache()
// Flushes FAT table cache of dead nodes.

void
fatfs_node_flush_dead_tcache(fatfs_disk_t *disk)
{
    fatfs_node_t *node;
 
    CYG_CHECK_DATA_PTRC(disk);
    
    node = node_list_get_tail(&disk->dead_nlist);

    while (NULL != node)
    {
        printf( "node='%s'", node->filename);
        fatfs_tcache_flush(disk, &node->tcache);
        node = node_list_get_prev(node);
    }
}

// -------------------------------------------------------------------------
// EOF fatfs_ncache.c