*/
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;
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;
}
/**
*/
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];
}
/**
* inside file.
* e.g. : at page array[0] you will find page address of the first page
* of the first file (if present).
- * Free blocks are allocated after the last file, starting from invalid ones
- * and continuing with the marked free ones.
+ * Free blocks are allocated after the last file.
*
* \return true if ok, false on disk read errors.
- * \note The whole disk is scanned once.
+ * \note The whole disk is scanned at max twice.
*/
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
{
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(struct BattFsSuper *disk, 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 = MAX_SEQ;
- seq_t maxh = MAX_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 < HALF_SEQ)
- {
- 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 == MAX_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;
-}
-
-/**
- * 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; curr_page++)
- {
- if (!copy)
- {
- if (pg_array[curr_page] == PAGE_UNSET_SENTINEL)
- gap++;
- else
- {
- pg_array[curr_page - gap] = pg_array[curr_page];
- copy = true;
- }
- }
- else
- {
- 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;
-
- 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(disk, 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.
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;
return disk->close(disk) && (res == 0);
}
+#if UNIT_TEST
bool battfs_writeTestBlock(struct BattFsSuper *disk, pgcnt_t page, inode_t inode, seq_t seq, fill_t fill, pgoff_t pgoff)
{
BattFsPageHeader hdr;
return true;
}
+#endif
projects / bertos.git / blobdiff