From 0a08cd291277f26da98d3266911afd57ccfbe698 Mon Sep 17 00:00:00 2001 From: batt Date: Mon, 15 Sep 2008 17:28:29 +0000 Subject: [PATCH] Very preliminary: remove from BattFS the LRU of free blocks; now the old blocks are left on the disk with an old seq number. git-svn-id: https://src.develer.com/svnoss/bertos/trunk@1805 38d2e660-2303-0410-9eaa-f027e97ec537 --- bertos/fs/battfs.c | 403 ++++++++++++++++++++++++++++----------------- bertos/fs/battfs.h | 59 +++---- 2 files changed, 276 insertions(+), 186 deletions(-) diff --git a/bertos/fs/battfs.c b/bertos/fs/battfs.c index aeacb9cd..eb2523ea 100644 --- a/bertos/fs/battfs.c +++ b/bertos/fs/battfs.c @@ -54,7 +54,7 @@ */ INLINE void battfs_to_disk(struct BattFsPageHeader *hdr, uint8_t *buf) { - STATIC_ASSERT(BATTFS_HEADER_LEN == 12); + STATIC_ASSERT(BATTFS_HEADER_LEN == 10); buf[0] = hdr->inode; buf[1] = hdr->fill; @@ -64,33 +64,25 @@ INLINE void battfs_to_disk(struct BattFsPageHeader *hdr, uint8_t *buf) buf[4] = hdr->pgoff >> 8; /* - * Mark is at least 1 bit longer than page address. + * Sequence number is at least 1 bit longer than page address. * Needed to take care of wraparonds. */ - buf[5] = hdr->mark; - buf[6] = hdr->mark >> 8; + buf[5] = hdr->seq; + buf[6] = hdr->seq >> 8; /* - * First bit used by mark, last 2 bits used by seq. - * Since only 2 pages with the same inode and pgoff - * can exist at the same time, 2 bit for seq are enough. + * First bit used by seq. * Unused bits are set to 1. */ - buf[7] = ((hdr->mark >> 16) & 0x01) | (hdr->seq << 6) | ~(BV(7) | BV(6) | BV(0)); - - /* - * This field must be the before the last one! - */ - buf[8] = hdr->fcs_free; - buf[9] = hdr->fcs_free >> 8; + buf[7] = (hdr->seq >> 16) ? 0xFF : 0xFE; /* * 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[10] = hdr->fcs; - buf[11] = hdr->fcs >> 8; + buf[8] = hdr->fcs; + buf[9] = hdr->fcs >> 8; } /** @@ -99,14 +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 == 12); + STATIC_ASSERT(BATTFS_HEADER_LEN == 10); hdr->inode = buf[0]; hdr->fill = buf[2] << 8 | buf[1]; hdr->pgoff = buf[4] << 8 | buf[3]; - hdr->mark = (mark_t)(buf[7] & 0x01) << 16 | buf[6] << 8 | buf[5]; - hdr->seq = buf[7] >> 6; - hdr->fcs_free = buf[9] << 8 | buf[8]; - hdr->fcs = buf[11] << 8 | buf[10]; + hdr->seq = (seq_t)(buf[7] & 0x01) << 16 | buf[6] << 8 | buf[5]; + hdr->fcs = buf[9] << 8 | buf[8]; } /** @@ -124,21 +114,6 @@ static fcs_t computeFcs(struct BattFsPageHeader *hdr) return cks; } -/** - * Compute the fcs of the header marked as free. - */ -static fcs_t computeFcsFree(struct BattFsPageHeader *hdr) -{ - uint8_t buf[BATTFS_HEADER_LEN]; - fcs_t cks; - - battfs_to_disk(hdr, buf); - rotating_init(&cks); - /* fcs_free is just before fcs of whole header */ - rotating_update(buf, BATTFS_HEADER_LEN - 2 * sizeof(fcs_t), &cks); - return cks; -} - /** * Read header of page \a page. @@ -221,21 +196,17 @@ static void movePages(struct BattFsSuper *disk, pgcnt_t src, int offset) } } +#if 0 + /** - * Insert \a page into page allocation array of \a disk, - * using \a mark to compute position. + * Insert \a page at the bottom of page allocation array of \a disk. */ -static void insertFreePage(struct BattFsSuper *disk, mark_t mark, pgcnt_t page) +static void insertFreePage(struct BattFsSuper *disk, pgcnt_t page) { - ASSERT(mark - disk->free_start < disk->free_next - disk->free_start); - - pgcnt_t free_pos = disk->page_count - disk->free_next + mark; - ASSERT(free_pos < disk->page_count); - - TRACEMSG("mark:%u, page:%u, free_start:%u, free_next:%u, free_pos:%u\n", - mark, page, disk->free_start, disk->free_next, free_pos); - + pgcnt_t free_pos = disk->page_count - 1; ASSERT(disk->page_array[free_pos] == PAGE_UNSET_SENTINEL); + ASSERT(page <= free_pos); + disk->page_array[free_pos] = page; } @@ -350,6 +321,7 @@ static void findFreeStartNext(struct BattFsSuper *disk, mark_t minl, mark_t maxl TRACEMSG("Free markers:\n minl %u\n maxl %u\n minh %u\n maxh %u\n free_start %u\n free_next %u\n", minl, maxl, minh, maxh, disk->free_start, disk->free_next); } +#endif /** * Count number of pages per file on \a disk. @@ -363,14 +335,7 @@ static void findFreeStartNext(struct BattFsSuper *disk, mark_t minl, mark_t maxl static bool countDiskFilePages(struct BattFsSuper *disk, pgoff_t *filelen_table) { BattFsPageHeader hdr; - mark_t minl, maxl, minh, maxh; - - /* Initialize min and max counters to keep trace od free blocks */ - minl = MAX_PAGE_ADDR; - maxl = 0; - minh = MAX_PAGE_ADDR | MARK_HALF_SIZE; - maxh = 0 | MARK_HALF_SIZE; - + disk->free_page_start = 0; /* Count the number of disk page per file */ for (pgcnt_t page = 0; page < disk->page_count; page++) @@ -384,8 +349,6 @@ static bool countDiskFilePages(struct BattFsSuper *disk, pgoff_t *filelen_table) /* Check header FCS */ if (hdr.fcs == computeFcs(&hdr)) { - ASSERT(hdr.mark == MARK_PAGE_VALID); - ASSERT(hdr.fcs_free == FCS_FREE_VALID); ASSERT(hdr.fill <= disk->page_size - BATTFS_HEADER_LEN); /* Page is valid and is owned by a file */ @@ -393,32 +356,10 @@ static bool countDiskFilePages(struct BattFsSuper *disk, pgoff_t *filelen_table) /* Keep trace of free space */ disk->free_bytes -= hdr.fill; - } - else - { - /* Check if page is marked free */ - if (hdr.fcs_free == computeFcsFree(&hdr)) - { - /* - * This page is a valid and marked free page. - * Update min and max free page markers. - */ - if (hdr.mark < MARK_HALF_SIZE) - { - minl = MIN(minl, hdr.mark); - maxl = MAX(maxl, hdr.mark); - } - else - { - minh = MIN(minh, hdr.mark); - maxh = MAX(maxh, hdr.mark); - } - } - else - TRACEMSG("page [%d] invalid, keeping as free\n", page); + disk->free_page_start++; } } - findFreeStartNext(disk, minl, maxl, minh, maxh); + return true; } @@ -440,6 +381,7 @@ static bool countDiskFilePages(struct BattFsSuper *disk, pgoff_t *filelen_table) static bool fillPageArray(struct BattFsSuper *disk, pgoff_t *filelen_table) { BattFsPageHeader hdr; + pgcnt_t curr_free_page = disk->free_page_start; /* Fill page allocation array */ for (pgcnt_t page = 0; page < disk->page_count; page++) { @@ -449,87 +391,246 @@ static bool fillPageArray(struct BattFsSuper *disk, pgoff_t *filelen_table) /* Check header FCS */ if (hdr.fcs == computeFcs(&hdr)) { - /* Page is valid and is owned by a file */ - ASSERT(hdr.mark == MARK_PAGE_VALID); - ASSERT(hdr.fcs_free == FCS_FREE_VALID); - /* Compute array position */ - pgcnt_t array_pos = countPages(filelen_table, hdr.inode); - array_pos += hdr.pgoff; + pgcnt_t array_pos_start = countPages(filelen_table, hdr.inode); + pgcnt_t array_pos = array_pos_start + hdr.pgoff; + + /* Find the first free position */ + while (disk->page_array[array_pos] != PAGE_UNSET_SENTINEL) + { + ASSERT(array_pos < array_pos_start + filelen_table[hdr.inode + 1]); + array_pos++; + } + + disk->page_array[array_pos] = page; + } + else + { + /* Invalid page, keep as free */ + ASSERT(disk->page_array[curr_free_page] == PAGE_UNSET_SENTINEL); + LOG_INFO("Page %d invalid, keeping as free\n", page); + disk->page_array[curr_free_page++] = page; + } + } + return true; +} + +/** + * Find the latest version of a page, starting from the + * page supplied by \a page_array. + * The pages are read from the disk until a different + * inode or page offset is found. + * The lastest version of the page is moved in the first + * position of \a page_array. + * \return the number of old versions of the page or PAGE_ERROR + * on disk read errors. + */ +static pgcnt_t findLastVersion(pgcnt_t *page_array) +{ + pgcnt_t *array_start = page_array; + BattFsPageHeader hdr; + if (!battfs_readHeader(disk, *page_array++, &hdr)) + return PAGE_ERROR; + + /* Free space: early bailout */ + if (hdr.fcs != computeFcs(&hdr)) + return 0; + + /* + * If the first page is valid, + * inode and pg_off in the array are taken + * as the current page markers. + */ + inode_t curr_inode = hdr.inode; + pgoff_t curr_pgoff = hdr.pgoff; + + /* Temps used to find the sequence number range */ + seq_t minl = HALF_SEQ - 1; + seq_t maxl = 0; + seq_t minh = FULL_SEQ; + seq_t maxh = HALF_SEQ; + pgcnt_t lpos = 0, hpos = 0, dup_cnt = 0; + + /* + * Find min and max values for the two + * half of seq_num range. + * With this we can find seqnum wraparounds. + * seq_t is a type that has at least 1 bit more than + * pgaddr_t. So all version of a page blocks can be numbered using + * at most half numbers of a seq_t type. + * The sequence number algorithm increments by 1 the previous seq_num + * every time a page is rewritten. So the sequence is + * guaranteed to be countiguous. + * Only wrap arounds may happen, but due to half size sequence limitation, + * there are only 4 possible situations: + * + * \verbatim + * |------lower half------|-------upper half-------| + * + * 1) |------minl*****maxl---|------------------------| + * 2) |------minl********maxl|minh******maxh----------| + * 3) |----------------------|----minh*******maxh-----| + * 4) |minl******maxl--------|------------minh****maxh| + * \endverbatim + * + * Situations 1 and 3 are easy to detect, while 2 and 4 require more care. + */ + do + { + if (hdr.seq < SEQ_HALF_SIZE) + { + minl = MIN(minl, hdr.seq); + if (hdr.seq > maxl) + { + maxl = hdr.seq; + lpos = dup_cnt; + } + } + else + { + minh = MIN(minh, hdr.seq); + if (hdr.seq > maxh) + { + maxh = hdr.seq; + hpos = dup_cnt; + } + } + + if (!battfs_readHeader(disk, *page_array++, &hdr)) + return PAGE_ERROR; + dup_cnt++; + } + while (curr_inode == hdr.inode && curr_pgoff == hdr.pgoff && hdr.fcs == computeFcs(&hdr)) + + + /* Return early if there is only one version of the current page */ + if (dup_cnt == 1) + return 0; + + /* Find the position in the array of the last version of the page */ + pgcnt_t last_ver = hpos; + if (maxl >= minl) + { + /* Valid interval found in lower half */ + if (maxh >= minh) + { + /* Valid interval also found in upper half */ + if (maxl != minh - 1) + { + /* Interval starts in upper half and ends in lower */ + ASSERT(minl == 0); + ASSERT(maxh == FULL_SEQ); + + last_ver = lpos; + } + } + else + /* + * Upper interval is invalid. + * Use lower values. + */ + last_ver = lpos; + } + + /* Put last page version at array start position */ + SWAP(array_start[0], array_start[last_ver]); + + return dup_cnt - 1; +} - /* Check if position is already used by another page of the same file */ - if (LIKELY(disk->page_array[array_pos] == PAGE_UNSET_SENTINEL)) - disk->page_array[array_pos] = page; +/** + * Collect old pages, removing empty spaces from \a pg_array, for a maximum len of \a pg_len. + * Once the collect task is completed, copy \a old_cnt pages from \a old_pages at the + * end of free space in pg_array. + */ +void collectOldPages(pgcnt_t *pg_array, pgcnt_t pg_len, pgcnt_t *old_pages, pgcnt_t old_cnt) +{ + bool copy = false; + pgcnt_t gap = 0; + + for (pgcnt_t curr_page = 0; curr_page < pg_len; pg_len++) + { + if (!copy) + { + if (pg_array[curr_page] == PAGE_UNSET_SENTINEL) + gap++; else { - BattFsPageHeader hdr_old; - - if (!battfs_readHeader(disk, disk->page_array[array_pos], &hdr_old)) - return false; - - /* Check header FCS */ - ASSERT(hdr_old.fcs == computeFcs(&hdr_old)); - - /* Only the very same page with a different seq number can be here */ - ASSERT(hdr.inode == hdr_old.inode); - ASSERT(hdr.pgoff == hdr_old.pgoff); - ASSERT(hdr.mark == hdr_old.mark); - ASSERT(hdr.fcs_free == hdr_old.fcs_free); - ASSERT(hdr.seq != hdr_old.seq); - - pgcnt_t new_page, old_page; - fill_t old_fill; - - /* Fancy check to handle seq wraparound (2 bits only) */ - if (((hdr.seq - hdr_old.seq) & 0x03) < 2) - { - /* Current header is newer than the previuos one */ - old_page = disk->page_array[array_pos]; - new_page = page; - old_fill = hdr_old.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); - - /* Decrease file page count */ - filelen_table[hdr.inode]--; - - /* Add old page to free pages pool */ - if (!battfs_markFree(disk, &hdr, old_page)) - return false; - - insertFreePage(disk, hdr.mark, old_page); + pg_array[curr_page - gap] = pg_array[curr_page]; + copy = true; } } else { - /* Check if page is free */ - if (hdr.fcs_free != computeFcsFree(&hdr)) - /* Page is not a valid marked page, insert at list beginning */ - hdr.mark = --disk->free_start; + if (pg_array[curr_page] != PAGE_UNSET_SENTINEL) + pg_array[curr_page - gap] = pg_array[curr_page]; + else + { + gap++; + copy = false; + } + } + } + ASSERT(gap == old_cnt); + pg_array += pg_len - old_cnt; - insertFreePage(disk, hdr.mark, page); + memcpy(pg_array, old_pages, old_cnt * sizeof(pgcnt_t)); +} + +/** + * This function scan the page array of \a disk looking for + * old versions of the same page. + * + * Only the last version is kept as valid, the old ones are inserted + * in the free blocks heap. + * \return true if ok, false on disk read errors. + * \note The whole disk is scanned once. + */ +static bool dropOldPages(struct BattFsSuper *disk) +{ + #define OLD_PAGE_BUFLEN 64 + pgcnt_t old_pages[OLD_PAGE_BUFLEN]; + pgcnt_t old_cnt = 0; + + pgcnt_t *curr_page = disk->page_array; + pgcnt_t *collect_start = disk->page_array; + pgcnt_t collect_len = disk->page_count; + pgcnt_t dup_pages; + + do + { + dup_pages = findLastVersion(curr_page); + if (dup_pages == PAGE_ERROR) + return false; + /* The first page is the last version */ + curr_page++; + while (dup_pages--) + { + if (old_cnt >= OLD_PAGE_BUFLEN) + { + collectOldPages(collect_start, collect_len, old_pages, old_cnt); + collect_len -= old_cnt; + disk->free_bytes += old_cnt * (disk->page_size - BATTFS_HEADER_LEN); + disk->free_page_start -= old_cnt; + curr_page -= old_cnt; + collect_start = curr_page; + old_cnt = 0; + } + + old_pages[old_cnt++] = *curr_page; + *curr_page++ = PAGE_UNSET_SENTINEL; } } + while (curr_page < disk->page_array + disk->free_page_start); + + collectOldPages(collect_start, collect_len, old_pages, old_cnt); + disk->free_bytes += old_cnt * (disk->page_size - BATTFS_HEADER_LEN); + disk->free_page_start -= old_cnt; + return true; } + /** * Initialize and mount disk described by * \a disk. @@ -584,6 +685,12 @@ 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 d75bd645..0422c43a 100644 --- a/bertos/fs/battfs.h +++ b/bertos/fs/battfs.h @@ -51,7 +51,6 @@ typedef uint16_t fill_t; ///< Type for keeping trace of space filled inside a 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 uint32_t mark_t; ///< Type for marking pages as free typedef uint8_t inode_t; ///< Type for file inodes typedef uint8_t seq_t; ///< Type for page seq number typedef rotating_t fcs_t; ///< Type for header FCS. @@ -60,7 +59,7 @@ 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(mark_t) > sizeof(pgcnt_t)); +STATIC_ASSERT(sizeof(seq_t) > sizeof(pgcnt_t)); /** * BattFS page header, used to represent a page @@ -72,16 +71,9 @@ STATIC_ASSERT(sizeof(mark_t) > sizeof(pgcnt_t)); typedef struct BattFsPageHeader { inode_t inode; ///< File inode (file identifier). - seq_t seq; ///< Page sequence number. fill_t fill; ///< Filled bytes in page. pgoff_t pgoff; ///< Page offset inside file. - mark_t mark; ///< Marker used to keep trace of free/used pages. - - /** - * FCS (Frame Check Sequence) of the page header once the page - * as been marked as free. - */ - fcs_t fcs_free; + seq_t seq; ///< Page sequence number. /** * FCS (Frame Check Sequence) of the page header. @@ -94,23 +86,18 @@ typedef struct BattFsPageHeader * \see battfs_to_disk * \see disk_to_battfs */ -#define BATTFS_HEADER_LEN 12 +#define BATTFS_HEADER_LEN 10 /** - * Marks for valid pages. - * Simply set to 1 all field bits. - * \{ + * Half-size of page sequence numer. */ -#define MARK_PAGE_VALID ((1 << (CPU_BITS_PER_CHAR * sizeof(pgcnt_t) + 1)) - 1) -#define FCS_FREE_VALID ((1 << (CPU_BITS_PER_CHAR * sizeof(fcs_t))) - 1) -/* \} */ - +#define HALF_SEQ (1 << (CPU_BITS_PER_CHAR * sizeof(pgcnt_t))) /** - * Half-size of free page marker. - * Used to keep trace of free marker wrap-arounds. + * Max sequence number. */ -#define MARK_HALF_SIZE (1 << (CPU_BITS_PER_CHAR * sizeof(pgcnt_t) + 1)) +#define MAX_SEQ ((1 << (CPU_BITS_PER_CHAR * sizeof(pgcnt_t) + 1)) - 1) + /** * Maximum page address. @@ -130,6 +117,9 @@ 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. @@ -193,17 +183,11 @@ typedef struct BattFsSuper */ pgcnt_t *page_array; - /** - * Lowest free page counter. - * This is the counter of the first availble free page. - */ - mark_t free_start; - - /** - * Highest free page counter. - * This value is the next to be used to mark a block as free. + /** + * Lowest address, in page array, for free pages. + * Pages above this element are free for use. */ - mark_t free_next; + pgcnt_t free_page_start; disk_size_t disk_size; ///< Size of the disk, in bytes (page_count * page_size). disk_size_t free_bytes; ///< Free space on the disk. @@ -228,7 +212,7 @@ typedef uint32_t file_size_t; ///< Type for file sizes. /** * Describe a BattFs file usign a KFile. */ -typedef struct BattFS +typedef struct BattFs { KFile fd; ///< KFile context Node link; ///< Link for inserting in opened file list @@ -236,7 +220,7 @@ typedef struct BattFS BattFsSuper *disk; ///< Disk context filemode_t mode; ///< File open mode pgcnt_t *start; ///< Pointer to page_array file start position. -} BattFS; +} BattFs; /** * Id for battfs file descriptors. @@ -247,18 +231,17 @@ typedef struct BattFS * Macro used to cast a KFile to a BattFS. * Also perform dynamic type check. */ -INLINE BattFS * BATTFSKFILE(KFile *fd) +INLINE BattFs * BATTFS_CAST(KFile *fd) { ASSERT(fd->_type == KFT_BATTFS); - return (BattFS *)fd; + return (BattFs *)fd; } bool battfs_init(struct BattFsSuper *d); bool battfs_close(struct BattFsSuper *disk); bool battfs_fileExists(BattFsSuper *disk, inode_t inode); -bool battfs_fileopen(BattFsSuper *disk, BattFS *fd, inode_t inode, filemode_t mode); - -bool battfs_writeTestBlock(struct BattFsSuper *disk, pgcnt_t page, inode_t inode, seq_t seq, fill_t fill, pgoff_t pgoff, mark_t mark); +bool battfs_fileopen(BattFsSuper *disk, BattFs *fd, inode_t inode, filemode_t mode); +bool battfs_writeTestBlock(struct BattFsSuper *disk, pgcnt_t page, inode_t inode, seq_t seq, fill_t fill, pgoff_t pgoff, seq_t seq); #endif /* FS_BATTFS_H */ -- 2.25.1