*
* -->
*
+ * \brief BattFS: a filesystem for embedded platforms (implementation).
+ *
* \version $Id:$
*
* \author Francesco Sacchi <batt@develer.com>
*
- * \brief BattFS: a filesystem for embedded platforms (implementation).
*/
#include "battfs.h"
#include <cfg/debug.h>
#include <cfg/macros.h> /* MIN, MAX */
-#include <mware/byteorder.h> /* cpu_to_xx */
+#include <cpu/byteorder.h> /* cpu_to_xx */
+#define LOG_LEVEL LOG_LVL_INFO
+#define LOG_FORMAT LOG_FMT_VERBOSE
+#include <cfg/log.h>
#include <string.h> /* memset, memmove */
buf[4] = hdr->pgoff >> 8;
/*
- * Mark is at least 1 bit longer than page address.
- * Needed to take care of wraparonds.
- */
- buf[5] = hdr->mark;
- buf[6] = hdr->mark >> 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.
- * 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!
+ * Sequence number is 40 bits long.
+ * No need to take care of wraparonds: the memory will die first!
*/
- buf[8] = hdr->fcs_free;
- buf[9] = hdr->fcs_free >> 8;
+ buf[5] = hdr->seq;
+ buf[6] = hdr->seq >> 8;
+ buf[7] = hdr->seq >> 16;
+ buf[8] = hdr->seq >> 24;
+ buf[9] = hdr->seq >> 32;
/*
* This field must be the last one!
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->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];
}
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.
* \return true on success, false otherwise.
- * \note \a hdr is dirtyed even on errors.
*/
static bool battfs_readHeader(struct BattFsSuper *disk, pgcnt_t page, struct BattFsPageHeader *hdr)
{
if (disk->read(disk, page, disk->page_size - BATTFS_HEADER_LEN, buf, BATTFS_HEADER_LEN)
!= BATTFS_HEADER_LEN)
{
- TRACEMSG("Error: page[%d]\n", page);
+ LOG_ERR("Error: page[%d]\n", page);
return false;
}
/**
* Write header of page \a page.
* \return true on success, false otherwise.
- * \note \a hdr is dirtyed even on errors.
*/
static bool battfs_writeHeader(struct BattFsSuper *disk, pgcnt_t page, struct BattFsPageHeader *hdr)
{
if (disk->write(disk, page, disk->page_size - BATTFS_HEADER_LEN, buf, BATTFS_HEADER_LEN)
!= BATTFS_HEADER_LEN)
{
- TRACEMSG("Error: page[%d]\n", page);
+ LOG_ERR("Error: page[%d]\n", page);
return false;
}
return true;
{
pgcnt_t dst = src + offset;
memmove(&disk->page_array[dst], &disk->page_array[src], (disk->page_count - MAX(dst, src)) * sizeof(pgcnt_t));
-
+
if (offset < 0)
{
/* Fill empty space in array with sentinel */
}
}
-/**
- * Insert \a page into page allocation array of \a disk,
- * using \a mark to compute position.
- */
-static void insertFreePage(struct BattFsSuper *disk, mark_t mark, 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);
-
- ASSERT(disk->page_array[free_pos] == PAGE_UNSET_SENTINEL);
- disk->page_array[free_pos] = page;
-}
-
-/**
- * Mark \a page of \a disk as free.
- * \note free_next of \a disk is used as \a page free marker
- * and is increased by 1.
- */
-static bool battfs_markFree(struct BattFsSuper *disk, struct BattFsPageHeader *hdr, pgcnt_t page)
-{
- uint8_t buf[BATTFS_HEADER_LEN];
-
- hdr->mark = disk->free_next;
- hdr->fcs_free = computeFcsFree(hdr);
- battfs_to_disk(hdr, buf);
-
- if (!disk->write(disk, page, disk->page_size - BATTFS_HEADER_LEN, buf, BATTFS_HEADER_LEN))
- {
- TRACEMSG("error marking page [%d]\n", page);
- return false;
- }
- else
- {
- disk->free_next++;
- return true;
- }
-}
-
-/**
- * Determine free_start and free_next blocks for \a disk
- * using \a minl, \a maxl, \a minh, \a maxh.
- *
- * Mark_t is a type that has at least 1 bit more than
- * pgaddr_t. So all free blocks can be numbered using
- * at most half numbers of a mark_t type.
- * The free blocks algorithm increments by 1 the disk->free_next
- * every time a page becomes free. So the free block 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.
- */
-static void findFreeStartNext(struct BattFsSuper *disk, mark_t minl, mark_t maxl, mark_t minh, mark_t maxh)
-{
- /* Determine free_start & free_next */
- 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 lower half and ends in upper */
- disk->free_start = minl;
- disk->free_next = maxh;
- }
- else
- {
- /* Interval starts in upper half and ends in lower */
- ASSERT(minl == 0);
- ASSERT(maxh == (MAX_PAGE_ADDR | MARK_HALF_SIZE));
-
- disk->free_start = minh;
- disk->free_next = maxl;
- }
- }
- else
- {
- /*
- * Upper interval is invalid.
- * Use lower values.
- */
-
- disk->free_start = minl;
- disk->free_next = maxl;
- }
- }
- else if (maxh >= minh)
- {
- /*
- * Lower interval is invalid.
- * Use upper values.
- */
- disk->free_start = minh;
- disk->free_next = maxh;
- }
- else
- {
- /*
- * No valid interval found.
- * Hopefully the disk is brand new (or full).
- */
- TRACEMSG("No valid marked free block found, new disk or disk full\n");
- disk->free_start = 0;
- disk->free_next = -1; //to be increased later
- }
-
- /* free_next should contain the first usable address */
- disk->free_next++;
-
- 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);
-}
-
/**
* Count number of pages per file on \a disk.
* This information is registered in \a filelen_table.
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++)
if (!battfs_readHeader(disk, page, &hdr))
return false;
+ /* Increase free space */
+ disk->free_bytes += disk->page_size - BATTFS_HEADER_LEN;
+
/* 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 */
filelen_table[hdr.inode]++;
/* Keep trace of free space */
- disk->free_bytes += disk->page_size - BATTFS_HEADER_LEN - hdr.fill;
- }
- else
- {
- /* Increase free space */
- disk->free_bytes += disk->page_size - BATTFS_HEADER_LEN;
-
- /* 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_bytes -= hdr.fill;
+ disk->free_page_start++;
}
}
- findFreeStartNext(disk, minl, maxl, minh, maxh);
+ LOG_INFO("free_bytes:%d, free_page_start:%d\n", disk->free_bytes, disk->free_page_start);
+
return true;
}
* 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)
{
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++)
{
/* 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;
+
/* Check if position is already used by another page of the same file */
- if (LIKELY(disk->page_array[array_pos] == PAGE_UNSET_SENTINEL))
+ if (disk->page_array[array_pos] == PAGE_UNSET_SENTINEL)
disk->page_array[array_pos] = page;
else
{
- BattFsPageHeader hdr_old;
-
- if (!battfs_readHeader(disk, disk->page_array[array_pos], &hdr_old))
+ BattFsPageHeader hdr_prv;
+
+ if (!battfs_readHeader(disk, disk->page_array[array_pos], &hdr_prv))
return false;
/* Check header FCS */
- ASSERT(hdr_old.fcs == computeFcs(&hdr_old));
+ ASSERT(hdr_prv.fcs == computeFcs(&hdr_prv));
/* 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);
+ 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;
- /* Fancy check to handle seq wraparound (2 bits only) */
- if (((hdr.seq - hdr_old.seq) & 0x03) < 2)
+ /*
+ * 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_old.fill;
+ old_fill = hdr_prv.fill;
}
else
{
/* 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 */
+ /* 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;
- /* Add old page to free pages pool */
- if (!battfs_markFree(disk, &hdr, old_page))
- return false;
-
- insertFreePage(disk, hdr.mark, old_page);
}
}
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;
-
- insertFreePage(disk, hdr.mark, page);
+ /* 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;
/* Init disk device */
if (!disk->open(disk))
{
- TRACEMSG("open error\n");
+ LOG_ERR("open error\n");
return false;
}
/* Count pages per file */
if (!countDiskFilePages(disk, filelen_table))
{
- TRACEMSG("error counting file pages\n");
+ LOG_ERR("error counting file pages\n");
return false;
}
/* Fill page allocation array using filelen_table */
if (!fillPageArray(disk, filelen_table))
{
- TRACEMSG("error filling page array\n");
+ LOG_ERR("error filling page array\n");
return false;
}
/* Init list for opened files. */
LIST_INIT(&disk->file_opened_list);
- return true;
+ return true;
}
/**
*/
static int battfs_fileclose(struct KFile *fd)
{
- KFileBattFs *fdb = KFILEBATTFS(fd);
+ BattFs *fdb = BATTFS_CAST(fd);
battfs_flush(fd);
REMOVE(&fdb->link);
*/
static size_t battfs_read(struct KFile *fd, void *_buf, size_t size)
{
- KFileBattFs *fdb = KFILEBATTFS(fd);
+ BattFs *fdb = BATTFS_CAST(fd);
uint8_t *buf = (uint8_t *)_buf;
size_t total_read = 0;
pgaddr_t addr_offset;
pgaddr_t read_len;
- size = MIN(size, fd->size - fd->seek_pos);
+ size = MIN((kfile_off_t)size, fd->size - fd->seek_pos);
while (size)
{
while (first <= last)
{
- page = (first + last) / 2;
+ page = (first + last) / 2;
if (!battfs_readHeader(disk, disk->page_array[page], &hdr))
return NULL;
fcs = computeFcs(&hdr);
if (hdr.fcs == fcs && hdr.inode == inode)
- return (&disk->page_array[page]) - hdr.pgoff;
- else if (hdr.fcs == fcs && hdr.inode < inode)
- first = page + 1;
- else
- last = page - 1;
+ return (&disk->page_array[page]) - hdr.pgoff;
+ else if (hdr.fcs == fcs && hdr.inode < inode)
+ first = page + 1;
+ else
+ last = page - 1;
}
return NULL;
* File context is stored in \a fd.
* \return true if ok, false otherwise.
*/
-bool battfs_fileopen(BattFsSuper *disk, KFileBattFs *fd, inode_t inode, filemode_t mode)
+bool battfs_fileopen(BattFsSuper *disk, BattFs *fd, inode_t inode, filemode_t mode)
{
Node *n;
hdr.seq = 0;
hdr.fill = 0;
hdr.pgoff = 0;
- hdr.mark = MARK_PAGE_VALID;
- hdr.fcs_free = FCS_FREE_VALID;
hdr.fcs = computeFcs(&hdr);
#warning TODO: get a free block and write on disk!
}
/* Insert file handle in list, ordered by inode, ascending. */
FOREACH_NODE(n, &disk->file_opened_list)
{
- KFileBattFs *file = containerof(n, KFileBattFs, link);
+ BattFs *file = containerof(n, BattFs, link);
if (file->inode >= inode)
break;
}
fd->fd.read = battfs_read;
fd->fd.reopen = kfile_genericReopen;
fd->fd.seek = kfile_genericSeek;
-
+
#warning TODO battfs_write, battfs_error, battfs_clearerr
#if 0
fd->fd.write = battfs_write;
/* Close all open files */
FOREACH_NODE(n, &disk->file_opened_list)
{
- KFileBattFs *file = containerof(n, KFileBattFs, link);
+ BattFs *file = containerof(n, BattFs, link);
res += battfs_fileclose(&file->fd);
}
return disk->close(disk) && (res == 0);
}
-
-bool battfs_writeTestBlock(struct BattFsSuper *disk, pgcnt_t page, inode_t inode, seq_t seq, fill_t fill, pgoff_t pgoff, mark_t mark)
+#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;
hdr.inode = inode;
- hdr.seq = seq;
hdr.fill = fill;
hdr.pgoff = pgoff;
- hdr.mark = MARK_PAGE_VALID;
- hdr.fcs_free = FCS_FREE_VALID;
+ hdr.seq = seq;
hdr.fcs = computeFcs(&hdr);
- if (mark != MARK_PAGE_VALID)
- {
- hdr.mark = mark;
- hdr.fcs_free = computeFcsFree(&hdr);
- }
if (!battfs_writeHeader(disk, page, &hdr))
{
- TRACEMSG("error writing hdr\n");
+ LOG_ERR("error writing hdr\n");
return false;
}
return true;
}
+#endif
projects / bertos.git / blobdiff