From 54cdb63007e4a3dac8cd50ecdb9e601e0302e62b Mon Sep 17 00:00:00 2001 From: batt Date: Tue, 16 Sep 2008 12:47:26 +0000 Subject: [PATCH] Simplify sequence numbering: now pages have a monotonically increasing sequence numnber. git-svn-id: https://src.develer.com/svnoss/bertos/trunk@1809 38d2e660-2303-0410-9eaa-f027e97ec537 --- bertos/fs/battfs.c | 104 ++++++++++++++++++++++++++++++++------------- bertos/fs/battfs.h | 36 ++++++---------- 2 files changed, 88 insertions(+), 52 deletions(-) diff --git a/bertos/fs/battfs.c b/bertos/fs/battfs.c index d1952050..73e3536a 100644 --- a/bertos/fs/battfs.c +++ b/bertos/fs/battfs.c @@ -57,7 +57,7 @@ */ INLINE void battfs_to_disk(struct BattFsPageHeader *hdr, uint8_t *buf) { - STATIC_ASSERT(BATTFS_HEADER_LEN == 10); + STATIC_ASSERT(BATTFS_HEADER_LEN == 12); buf[0] = hdr->inode; buf[1] = hdr->fill; @@ -67,25 +67,22 @@ INLINE void battfs_to_disk(struct BattFsPageHeader *hdr, uint8_t *buf) buf[4] = hdr->pgoff >> 8; /* - * Sequence number is at least 1 bit longer than page address. - * Needed to take care of wraparonds. + * Sequence number is 40 bits long. + * No need to take care of wraparonds: the memory will die first! */ buf[5] = hdr->seq; buf[6] = hdr->seq >> 8; - - /* - * First bit used by seq. - * Unused bits are set to 1. - */ - buf[7] = (hdr->seq >> 16) ? 0xFF : 0xFE; + buf[7] = hdr->seq >> 16; + buf[8] = hdr->seq >> 24; + buf[9] = hdr->seq >> 32; /* * This field must be the last one! * This is needed because if the page is only partially * written, we can use this to detect it. */ - buf[8] = hdr->fcs; - buf[9] = hdr->fcs >> 8; + buf[10] = hdr->fcs; + buf[11] = hdr->fcs >> 8; } /** @@ -94,12 +91,12 @@ INLINE void battfs_to_disk(struct BattFsPageHeader *hdr, uint8_t *buf) */ INLINE void disk_to_battfs(uint8_t *buf, struct BattFsPageHeader *hdr) { - STATIC_ASSERT(BATTFS_HEADER_LEN == 10); + STATIC_ASSERT(BATTFS_HEADER_LEN == 12); hdr->inode = buf[0]; hdr->fill = buf[2] << 8 | buf[1]; hdr->pgoff = buf[4] << 8 | buf[3]; - hdr->seq = (seq_t)(buf[7] & 0x01) << 16 | buf[6] << 8 | buf[5]; - hdr->fcs = buf[9] << 8 | buf[8]; + hdr->seq = (seq_t)buf[9] << 32 | (seq_t)buf[8] << 24 | (seq_t)buf[7] << 16 | buf[6] << 8 | buf[5]; + hdr->fcs = buf[11] << 8 | buf[10]; } /** @@ -269,17 +266,71 @@ static bool fillPageArray(struct BattFsSuper *disk, pgoff_t *filelen_table) if (hdr.fcs == computeFcs(&hdr)) { /* Compute array position */ - pgcnt_t array_pos_start = countPages(filelen_table, hdr.inode); - pgcnt_t array_pos = array_pos_start + hdr.pgoff; + pgcnt_t array_pos = countPages(filelen_table, hdr.inode); + array_pos += hdr.pgoff; + - /* Find the first free position */ - while (disk->page_array[array_pos] != PAGE_UNSET_SENTINEL) + /* Check if position is already used by another page of the same file */ + if (disk->page_array[array_pos] == PAGE_UNSET_SENTINEL) + disk->page_array[array_pos] = page; + else { - ASSERT(array_pos < array_pos_start + filelen_table[hdr.inode] + filelen_table[hdr.inode + 1]); - array_pos++; - } + BattFsPageHeader hdr_prv; + + if (!battfs_readHeader(disk, disk->page_array[array_pos], &hdr_prv)) + return false; + + /* Check header FCS */ + ASSERT(hdr_prv.fcs == computeFcs(&hdr_prv)); + + /* Only the very same page with a different seq number can be here */ + ASSERT(hdr.inode == hdr_prv.inode); + ASSERT(hdr.pgoff == hdr_prv.pgoff); + ASSERT(hdr.seq != hdr_prv.seq); + + pgcnt_t new_page, old_page; + fill_t old_fill; + + /* + * Sequence number comparison: since + * seq is 40 bits wide, it wraps once + * every 1.1E12 times. + * The memory will not live enough to + * see a wraparound, so we can use a simple + * compare here. + */ + if (hdr.seq > hdr_prv.seq) + { + /* Current header is newer than the previuos one */ + old_page = disk->page_array[array_pos]; + new_page = page; + old_fill = hdr_prv.fill; + } + else + { + /* Previous header is newer than the current one */ + old_page = page; + new_page = disk->page_array[array_pos]; + old_fill = hdr.fill; + } + + /* Set new page */ + disk->page_array[array_pos] = new_page; + /* Add free space */ + disk->free_bytes += old_fill; + /* Shift all array one position to the left, overwriting duplicate page */ + array_pos -= hdr.pgoff; + array_pos += filelen_table[hdr.inode]; + movePages(disk, array_pos, -1); + /* Move back all indexes */ + filelen_table[hdr.inode]--; + disk->free_page_start--; + curr_free_page--; + /* Set old page as free */ + ASSERT(disk->page_array[curr_free_page] == PAGE_UNSET_SENTINEL); + disk->page_array[curr_free_page++] = old_page; - disk->page_array[array_pos] = page; + } } else { @@ -292,6 +343,7 @@ static bool fillPageArray(struct BattFsSuper *disk, pgoff_t *filelen_table) return true; } +#if 0 /** * Find the latest version of a page, starting from the * page supplied by \a page_array. @@ -506,7 +558,7 @@ static bool dropOldPages(struct BattFsSuper *disk) return true; } - +#endif /** * Initialize and mount disk described by @@ -562,12 +614,6 @@ bool battfs_init(struct BattFsSuper *disk) return false; } - if (!dropOldPages(disk)) - { - LOG_ERR("error dropping old pages\n"); - return false; - } - /* Init list for opened files. */ LIST_INIT(&disk->file_opened_list); return true; diff --git a/bertos/fs/battfs.h b/bertos/fs/battfs.h index 9c60b9d5..ee104db8 100644 --- a/bertos/fs/battfs.h +++ b/bertos/fs/battfs.h @@ -52,14 +52,9 @@ typedef fill_t pgaddr_t; ///< Type for addressing space inside a page typedef uint16_t pgcnt_t; ///< Type for counting pages on disk typedef pgcnt_t pgoff_t; ///< Type for counting pages inside a file typedef uint8_t inode_t; ///< Type for file inodes -typedef uint32_t seq_t; ///< Type for page seq number +typedef uint64_t seq_t; ///< Type for page seq number, at least 40bits wide. typedef rotating_t fcs_t; ///< Type for header FCS. -/** - * Size required for free block allocation is at least 1 bit more - * than page addressing. - */ -STATIC_ASSERT(sizeof(seq_t) > sizeof(pgcnt_t)); /** * BattFS page header, used to represent a page @@ -73,7 +68,16 @@ typedef struct BattFsPageHeader inode_t inode; ///< File inode (file identifier). fill_t fill; ///< Filled bytes in page. pgoff_t pgoff; ///< Page offset inside file. - seq_t seq; ///< Page sequence number. + + /** + * Page sequence number. + * Every time a page is rewritten the seq number is + * increased by 1. seq_t is wide enough to not to perform + * a wrap around before the memory death. + * So it can be kept as it would be + * monotonically increasing for our needs. + */ + seq_t seq; /** * FCS (Frame Check Sequence) of the page header. @@ -86,18 +90,7 @@ typedef struct BattFsPageHeader * \see battfs_to_disk * \see disk_to_battfs */ -#define BATTFS_HEADER_LEN 10 - -/** - * Half-size of page sequence numer. - */ -#define HALF_SEQ (1 << (CPU_BITS_PER_CHAR * sizeof(pgcnt_t))) - -/** - * Max sequence number. - */ -#define MAX_SEQ ((1 << (CPU_BITS_PER_CHAR * sizeof(pgcnt_t) + 1)) - 1) - +#define BATTFS_HEADER_LEN 12 /** * Maximum page address. @@ -117,9 +110,6 @@ struct BattFsSuper; */ #define PAGE_UNSET_SENTINEL ((1 << (CPU_BITS_PER_CHAR * sizeof(pgcnt_t))) - 1) -/** Also used as an error marker sometimes */ -#define PAGE_ERROR PAGE_UNSET_SENTINEL - /** * Type interface for disk init function. * \return true if all is ok, false otherwise. @@ -196,7 +186,7 @@ typedef struct BattFsSuper /* TODO add other fields. */ } BattFsSuper; -typedef uint8_t filemode_t; ///< Type for file open modes. +typedef uint8_t filemode_t; ///< Type for file open modes. typedef int32_t file_size_t; ///< Type for file sizes. /** -- 2.25.1