*
* \brief BattFS: a filesystem for embedded platforms (implementation).
*
- * \version $Id:$
*
* \author Francesco Sacchi <batt@develer.com>
*
*/
#include "battfs.h"
-
+#include "cfg/cfg_battfs.h"
#include <cfg/debug.h>
#include <cfg/macros.h> /* MIN, MAX */
+#include <cfg/test.h>
#include <cpu/byteorder.h> /* cpu_to_xx */
+#define LOG_LEVEL BATTFS_LOG_LEVEL
+#define LOG_FORMAT BATTFS_LOG_FORMAT
+#include <cfg/log.h>
#include <string.h> /* memset, memmove */
+#if LOG_LEVEL >= LOG_LVL_INFO
+static void dumpPageArray(struct BattFsSuper *disk)
+{
+ kprintf("Page array dump, free_page_start %d:", disk->free_page_start);
+ for (pgcnt_t i = 0; i < disk->dev->blk_cnt; i++)
+ {
+ if (!(i % 16))
+ kputchar('\n');
+ kprintf("%04d ", disk->page_array[i]);
+ }
+ kputchar('\n');
+}
+#endif
/**
* Convert from memory representation to disk structure.
*/
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];
}
/**
return cks;
}
-
/**
- * Read header of page \a page.
+ * Read header of \a page in \a hdr.
* \return true on success, false otherwise.
*/
-static bool battfs_readHeader(struct BattFsSuper *disk, pgcnt_t page, struct BattFsPageHeader *hdr)
+static bool readHdr(struct BattFsSuper *disk, pgcnt_t page, struct BattFsPageHeader *hdr)
{
uint8_t buf[BATTFS_HEADER_LEN];
+
/*
* Read header from disk.
* Header is actually a footer, and so
* resides at page end.
*/
- if (disk->read(disk, page, disk->page_size - BATTFS_HEADER_LEN, buf, BATTFS_HEADER_LEN)
+ if (kblock_read(disk->dev, page, buf, disk->data_size, BATTFS_HEADER_LEN)
!= BATTFS_HEADER_LEN)
{
- TRACEMSG("Error: page[%d]\n", page);
+ LOG_ERR("page[%d]\n", page);
return false;
}
return true;
}
-/**
- * Write header of page \a page.
- * \return true on success, false otherwise.
- */
-static bool battfs_writeHeader(struct BattFsSuper *disk, pgcnt_t page, struct BattFsPageHeader *hdr)
+static bool writeHdr(struct BattFsSuper *disk, pgcnt_t page, struct BattFsPageHeader *hdr)
{
uint8_t buf[BATTFS_HEADER_LEN];
+ #warning FIXME:refactor computeFcs to save time and stack
+ hdr->fcs = computeFcs(hdr);
/* Fill buffer */
battfs_to_disk(hdr, buf);
* Header is actually a footer, and so
* resides at page end.
*/
- if (disk->write(disk, page, disk->page_size - BATTFS_HEADER_LEN, buf, BATTFS_HEADER_LEN)
+ if (kblock_write(disk->dev, page, buf, disk->data_size, BATTFS_HEADER_LEN)
!= BATTFS_HEADER_LEN)
{
- TRACEMSG("Error: page[%d]\n", page);
+ LOG_ERR("writing to buffer\n");
return false;
}
return true;
}
+
/**
* Count the number of pages from
* inode 0 to \a inode in \a filelen_table.
static void movePages(struct BattFsSuper *disk, pgcnt_t src, int offset)
{
pgcnt_t dst = src + offset;
- memmove(&disk->page_array[dst], &disk->page_array[src], (disk->page_count - MAX(dst, src)) * sizeof(pgcnt_t));
+ LOG_INFO("src %d, offset %d, size %d\n", src, offset, (unsigned int)((disk->dev->blk_cnt - MAX(dst, src)) * sizeof(pgcnt_t)));
+ memmove(&disk->page_array[dst], &disk->page_array[src], (disk->dev->blk_cnt - MAX(dst, src)) * sizeof(pgcnt_t));
if (offset < 0)
{
/* Fill empty space in array with sentinel */
- for (pgcnt_t page = disk->page_count + offset; page < disk->page_count; page++)
+ for (pgcnt_t page = disk->dev->blk_cnt + offset; page < disk->dev->blk_cnt; page++)
disk->page_array[page] = PAGE_UNSET_SENTINEL;
}
}
-#if 0
-
-/**
- * Insert \a page at the bottom of page allocation array of \a disk.
- */
-static void insertFreePage(struct BattFsSuper *disk, pgcnt_t page)
-{
- 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;
-}
-
-/**
- * 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);
-}
-#endif
-
/**
* Count number of pages per file on \a disk.
* This information is registered in \a filelen_table.
disk->free_page_start = 0;
/* Count the number of disk page per file */
- for (pgcnt_t page = 0; page < disk->page_count; page++)
+ for (pgcnt_t page = 0; page < disk->dev->blk_cnt; page++)
{
- if (!battfs_readHeader(disk, page, &hdr))
+ if (!readHdr(disk, page, &hdr))
return false;
/* Increase free space */
- disk->free_bytes += disk->page_size - BATTFS_HEADER_LEN;
+ disk->free_bytes += disk->data_size;
/* Check header FCS */
if (hdr.fcs == computeFcs(&hdr))
{
- ASSERT(hdr.fill <= disk->page_size - BATTFS_HEADER_LEN);
+ ASSERT(hdr.fill <= disk->data_size);
/* Page is valid and is owned by a file */
filelen_table[hdr.inode]++;
disk->free_page_start++;
}
}
+ LOG_INFO("free_bytes:%ld, free_page_start:%d\n", (long)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++)
+ for (pgcnt_t page = 0; page < disk->dev->blk_cnt; page++)
{
- if (!battfs_readHeader(disk, page, &hdr))
+ if (!readHdr(disk, page, &hdr))
return false;
/* Check header FCS */
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 + 1]);
- array_pos++;
- }
+ BattFsPageHeader hdr_prv;
+
+ if (!readHdr(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
{
/* 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);
+ //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.
+ * Initialize and mount disk described by
+ * \a disk.
+ * \return false on errors, true otherwise.
*/
-static pgcnt_t findLastVersion(pgcnt_t *page_array)
+bool battfs_mount(struct BattFsSuper *disk, struct KBlock *dev, pgcnt_t *page_array, size_t array_size)
{
- pgcnt_t *array_start = page_array;
- BattFsPageHeader hdr;
- if (!battfs_readHeader(disk, *page_array++, &hdr))
- return PAGE_ERROR;
+ pgoff_t filelen_table[BATTFS_MAX_FILES];
- /* Free space: early bailout */
- if (hdr.fcs != computeFcs(&hdr))
- return 0;
+ ASSERT(dev);
+ ASSERT(kblock_partialWrite(dev));
+ disk->dev = dev;
- /*
- * 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;
+ ASSERT(disk->dev->blk_size > BATTFS_HEADER_LEN);
+ /* Fill page_size with the usable space */
+ disk->data_size = disk->dev->blk_size - BATTFS_HEADER_LEN;
+ ASSERT(disk->dev->blk_cnt);
+ ASSERT(disk->dev->blk_cnt < PAGE_UNSET_SENTINEL - 1);
+ ASSERT(page_array);
+ disk->page_array = page_array;
+ ASSERT(array_size >= disk->dev->blk_cnt * sizeof(pgcnt_t));
- /* 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;
+ memset(filelen_table, 0, BATTFS_MAX_FILES * sizeof(pgoff_t));
- /*
- * 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;
- }
- }
+ disk->free_bytes = 0;
+ disk->disk_size = (disk_size_t)disk->data_size * disk->dev->blk_cnt;
- if (!battfs_readHeader(disk, *page_array++, &hdr))
- return PAGE_ERROR;
- dup_cnt++;
+ /* Count pages per file */
+ if (!countDiskFilePages(disk, filelen_table))
+ {
+ LOG_ERR("counting file pages\n");
+ return false;
}
- while (curr_inode == hdr.inode && curr_pgoff == hdr.pgoff && hdr.fcs == computeFcs(&hdr))
+ /* Once here, we have filelen_table filled with file lengths */
- /* Return early if there is only one version of the current page */
- if (dup_cnt == 1)
- return 0;
+ /* Fill page array with sentinel */
+ for (pgcnt_t page = 0; page < disk->dev->blk_cnt; page++)
+ disk->page_array[page] = PAGE_UNSET_SENTINEL;
- /* Find the position in the array of the last version of the page */
- pgcnt_t last_ver = hpos;
- if (maxl >= minl)
+ /* Fill page allocation array using filelen_table */
+ if (!fillPageArray(disk, filelen_table))
{
- /* 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;
+ LOG_ERR("filling page array\n");
+ return false;
}
-
- /* Put last page version at array start position */
- SWAP(array_start[0], array_start[last_ver]);
-
- return dup_cnt - 1;
+ #if LOG_LEVEL >= LOG_LVL_INFO
+ dumpPageArray(disk);
+ #endif
+ #if CONFIG_BATTFS_SHUFFLE_FREE_PAGES
+ SHUFFLE(&disk->page_array[disk->free_page_start], disk->dev->blk_cnt - disk->free_page_start);
+
+ LOG_INFO("Page array after shuffle:\n");
+ #if LOG_LEVEL >= LOG_LVL_INFO
+ dumpPageArray(disk);
+ #endif
+ #endif
+ /* Init list for opened files. */
+ LIST_INIT(&disk->file_opened_list);
+ return true;
}
/**
- * 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.
+ * Check the filesystem.
+ * \return true if ok, false on errors.
*/
-void collectOldPages(pgcnt_t *pg_array, pgcnt_t pg_len, pgcnt_t *old_pages, pgcnt_t old_cnt)
+bool battfs_fsck(struct BattFsSuper *disk)
{
- bool copy = false;
- pgcnt_t gap = 0;
+ #define FSCHECK(cond) do { if(!(cond)) { LOG_ERR("\"" #cond "\"\n"); return false; } } while (0)
+
+ FSCHECK(disk->free_page_start <= disk->dev->blk_cnt);
+ FSCHECK(disk->data_size < disk->dev->blk_size);
+ FSCHECK(disk->free_bytes <= disk->disk_size);
+
+ disk_size_t free_bytes = 0;
+ BattFsPageHeader hdr, prev_hdr;
+ inode_t files = 0;
+ pgcnt_t page_used = 0;
- for (pgcnt_t curr_page = 0; curr_page < pg_len; pg_len++)
+ bool start = true;
+
+ /* Uneeded, the first time will be overwritten but useful to silence
+ * the warning for uninitialized value */
+ FSCHECK(readHdr(disk, 0, &prev_hdr));
+ for (pgcnt_t page = 0; page < disk->dev->blk_cnt; page++)
{
- if (!copy)
+ FSCHECK(readHdr(disk, disk->page_array[page], &hdr));
+ free_bytes += disk->data_size;
+
+ if (page < disk->free_page_start)
{
- if (pg_array[curr_page] == PAGE_UNSET_SENTINEL)
- gap++;
- else
+ FSCHECK(computeFcs(&hdr) == hdr.fcs);
+ page_used++;
+ free_bytes -= hdr.fill;
+ if (hdr.inode != prev_hdr.inode || start)
{
- pg_array[curr_page - gap] = pg_array[curr_page];
- copy = true;
+ if (LIKELY(!start))
+ FSCHECK(hdr.inode > prev_hdr.inode);
+ else
+ start = false;
+
+ FSCHECK(hdr.pgoff == 0);
+ files++;
}
- }
- else
- {
- if (pg_array[curr_page] != PAGE_UNSET_SENTINEL)
- pg_array[curr_page - gap] = pg_array[curr_page];
else
{
- gap++;
- copy = false;
+ FSCHECK(hdr.fill != 0);
+ FSCHECK(prev_hdr.fill == disk->data_size);
+ FSCHECK(hdr.pgoff == prev_hdr.pgoff + 1);
}
+ prev_hdr = hdr;
}
}
- ASSERT(gap == old_cnt);
- pg_array += pg_len - old_cnt;
- memcpy(pg_array, old_pages, old_cnt * sizeof(pgcnt_t));
+ FSCHECK(page_used == disk->free_page_start);
+ FSCHECK(free_bytes == disk->free_bytes);
+
+ return true;
}
/**
- * 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.
+ * Flush file \a fd.
+ * \return 0 if ok, EOF on errors.
*/
-static bool dropOldPages(struct BattFsSuper *disk)
+static int battfs_flush(struct KFile *fd)
{
- #define OLD_PAGE_BUFLEN 64
- pgcnt_t old_pages[OLD_PAGE_BUFLEN];
- pgcnt_t old_cnt = 0;
+ BattFs *fdb = BATTFS_CAST(fd);
- 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;
+ if (kblock_flush(fdb->disk->dev) == 0)
+ return 0;
+ else
+ {
+ fdb->errors |= BATTFS_DISK_FLUSHBUF_ERR;
+ return EOF;
+ }
+}
- do
+/**
+ * Close file \a fd.
+ * \return 0 if ok, EOF on errors.
+ */
+static int battfs_fileclose(struct KFile *fd)
+{
+ BattFs *fdb = BATTFS_CAST(fd);
+
+ if (battfs_flush(fd) == 0)
{
- 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;
- }
+ REMOVE(&fdb->link);
+ return 0;
+ }
+ else
+ return EOF;
+}
- old_pages[old_cnt++] = *curr_page;
- *curr_page++ = PAGE_UNSET_SENTINEL;
- }
+#define NO_SPACE PAGE_UNSET_SENTINEL
+
+static pgcnt_t allocateNewPage(struct BattFsSuper *disk, pgcnt_t new_pos, inode_t inode)
+{
+ if (SPACE_OVER(disk))
+ {
+ LOG_ERR("No disk space available!\n");
+ return NO_SPACE;
}
- 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;
+ LOG_INFO("Getting new page %d, pos %d\n", disk->page_array[disk->free_page_start], new_pos);
+ pgcnt_t new_page = disk->page_array[disk->free_page_start++];
+ memmove(&disk->page_array[new_pos + 1], &disk->page_array[new_pos], (disk->free_page_start - new_pos - 1) * sizeof(pgcnt_t));
- return true;
+ Node *n;
+ /* Move following file start point one position ahead. */
+ FOREACH_NODE(n, &disk->file_opened_list)
+ {
+ BattFs *file = containerof(n, BattFs, link);
+ if (file->inode > inode)
+ {
+ LOG_INFO("Move file %d start pos\n", file->inode);
+ file->start++;
+ }
+ }
+
+ disk->page_array[new_pos] = new_page;
+ return new_page;
}
+static pgcnt_t renewPage(struct BattFsSuper *disk, pgcnt_t old_pos)
+{
+ if (SPACE_OVER(disk))
+ {
+ LOG_ERR("No disk space available!\n");
+ return NO_SPACE;
+ }
+
+ /* Get a free page */
+ pgcnt_t new_page = disk->page_array[disk->free_page_start];
+ movePages(disk, disk->free_page_start + 1, -1);
+
+ /* Insert previous page in free blocks list */
+ LOG_INFO("Setting page %d as free\n", old_pos);
+ disk->page_array[disk->dev->blk_cnt - 1] = old_pos;
+ return new_page;
+}
/**
- * Initialize and mount disk described by
- * \a disk.
- * \return false on errors, true otherwise.
+ * Write to file \a fd \a size bytes from \a buf.
+ * \return The number of bytes written.
*/
-bool battfs_init(struct BattFsSuper *disk)
+static size_t battfs_write(struct KFile *fd, const void *_buf, size_t size)
{
- pgoff_t filelen_table[BATTFS_MAX_FILES];
+ BattFs *fdb = BATTFS_CAST(fd);
+ BattFsSuper *disk = fdb->disk;
+ const uint8_t *buf = (const uint8_t *)_buf;
- /* Sanity check */
- ASSERT(disk->open);
+ size_t total_write = 0;
+ pgoff_t pg_offset;
+ pgaddr_t addr_offset;
+ pgaddr_t wr_len;
+ BattFsPageHeader curr_hdr;
+ pgcnt_t new_page;
- /* Init disk device */
- if (!disk->open(disk))
+ if (fd->seek_pos < 0)
{
- TRACEMSG("open error\n");
- return false;
+ fdb->errors |= BATTFS_NEGATIVE_SEEK_ERR;
+ return total_write;
}
- /* Disk open must set all of these */
- ASSERT(disk->read);
- ASSERT(disk->write);
- ASSERT(disk->erase);
- ASSERT(disk->close);
- ASSERT(disk->page_size);
- ASSERT(disk->page_count);
- ASSERT(disk->page_count < PAGE_UNSET_SENTINEL - 1);
- ASSERT(disk->page_array);
+ if (fd->seek_pos > fd->size)
+ {
+ if (!readHdr(disk, fdb->start[fdb->max_off], &curr_hdr))
+ {
+ fdb->errors |= BATTFS_DISK_READ_ERR;
+ return total_write;
+ }
- memset(filelen_table, 0, BATTFS_MAX_FILES * sizeof(pgoff_t));
+ /*
+ * Renew page only if is not in cache.
+ * This avoids rewriting the same page continuously
+ * if the user code keeps writing in the same portion
+ * of the file.
+ */
+ if (kblock_buffered(disk->dev)
+ && ((fdb->start[fdb->max_off] != kblock_cachedBlock(disk->dev)) || !kblock_cacheDirty(disk->dev)))
+ {
+ new_page = renewPage(disk, fdb->start[fdb->max_off]);
+ if (new_page == NO_SPACE)
+ {
+ fdb->errors |= BATTFS_DISK_SPACEOVER_ERR;
+ return total_write;
+ }
- disk->free_bytes = 0;
- disk->disk_size = (disk_size_t)(disk->page_size - BATTFS_HEADER_LEN) * disk->page_count;
+ kblock_copy(disk->dev, fdb->start[fdb->max_off], new_page);
+ fdb->start[fdb->max_off] = new_page;
+ }
+ else
+ new_page = fdb->start[fdb->max_off];
- /* Count pages per file */
- if (!countDiskFilePages(disk, filelen_table))
- {
- TRACEMSG("error counting file pages\n");
- return false;
- }
+ /* Fill unused space of first page with 0s */
+ uint8_t dummy = 0;
+ // TODO: write in blocks to speed up things
+ pgaddr_t zero_bytes = MIN(fd->seek_pos - fd->size, (kfile_off_t)(disk->data_size - curr_hdr.fill));
+ while (zero_bytes--)
+ {
+ if (kblock_write(disk->dev, new_page, &dummy, curr_hdr.fill, 1) != 1)
+ {
+ fdb->errors |= BATTFS_DISK_WRITE_ERR;
+ return total_write;
+ }
+ curr_hdr.fill++;
+ fd->size++;
+ disk->free_bytes--;
+ }
+ curr_hdr.seq++;
+ if (!writeHdr(disk, new_page, &curr_hdr))
+ {
+ fdb->errors |= BATTFS_DISK_WRITE_ERR;
+ return total_write;
+ }
- /* Once here, we have filelen_table filled with file lengths */
+ /* Allocate the missing pages first. */
+ pgoff_t missing_pages = fd->seek_pos / disk->data_size - fdb->max_off;
- /* Fill page array with sentinel */
- for (pgcnt_t page = 0; page < disk->page_count; page++)
- disk->page_array[page] = PAGE_UNSET_SENTINEL;
+ LOG_INFO("missing pages: %d\n", missing_pages);
- /* Fill page allocation array using filelen_table */
- if (!fillPageArray(disk, filelen_table))
- {
- TRACEMSG("error filling page array\n");
- return false;
+ while (missing_pages--)
+ {
+ zero_bytes = MIN((kfile_off_t)disk->data_size, fd->seek_pos - fd->size);
+
+ new_page = allocateNewPage(disk, (fdb->start - disk->page_array) + fdb->max_off + 1, fdb->inode);
+ if (new_page == NO_SPACE)
+ {
+ fdb->errors |= BATTFS_DISK_SPACEOVER_ERR;
+ return total_write;
+ }
+
+
+ // TODO: write in blocks to speed up things
+ /* Fill page buffer with 0 to avoid filling unused pages with garbage */
+ for (pgaddr_t off = 0; off < disk->data_size; off++)
+ {
+ if (kblock_write(disk->dev, new_page, &dummy, off, 1) != 1)
+ {
+ fdb->errors |= BATTFS_DISK_WRITE_ERR;
+ return total_write;
+ }
+ }
+ curr_hdr.inode = fdb->inode;
+ curr_hdr.pgoff = ++fdb->max_off;
+ curr_hdr.fill = zero_bytes;
+ curr_hdr.seq = 0;
+
+ if (!writeHdr(disk, new_page, &curr_hdr))
+ {
+ fdb->errors |= BATTFS_DISK_WRITE_ERR;
+ return total_write;
+ }
+
+ /* Update size and free space left */
+ fd->size += zero_bytes;
+ disk->free_bytes -= zero_bytes;
+ }
}
- if (!dropOldPages(disk))
+ while (size)
{
- LOG_ERR("error dropping old pages\n");
- return false;
- }
+ pg_offset = fd->seek_pos / disk->data_size;
+ addr_offset = fd->seek_pos % disk->data_size;
+ wr_len = MIN(size, (size_t)(disk->data_size - addr_offset));
- /* Init list for opened files. */
- LIST_INIT(&disk->file_opened_list);
- return true;
-}
+ /* Handle write outside EOF */
+ if (pg_offset > fdb->max_off)
+ {
+ LOG_INFO("New page needed, pg_offset %d, pos %d\n", pg_offset, (int)((fdb->start - disk->page_array) + pg_offset));
-/**
- * Flush file \a fd.
- * \return 0 if ok, EOF on errors.
- */
-static int battfs_flush(struct KFile *fd)
-{
- (void)fd;
- #warning TODO
- return 0;
-}
+ new_page = allocateNewPage(disk, (fdb->start - disk->page_array) + pg_offset, fdb->inode);
+ if (new_page == NO_SPACE)
+ {
+ fdb->errors |= BATTFS_DISK_SPACEOVER_ERR;
+ return total_write;
+ }
-/**
- * Close file \a fd.
- * \return 0 if ok, EOF on errors.
- */
-static int battfs_fileclose(struct KFile *fd)
-{
- BattFS *fdb = BATTFSKFILE(fd);
+ curr_hdr.inode = fdb->inode;
+ curr_hdr.pgoff = pg_offset;
+ curr_hdr.fill = 0;
+ curr_hdr.seq = 0;
+ fdb->max_off = pg_offset;
+ }
+ else
+ {
+ if (!readHdr(disk, fdb->start[pg_offset], &curr_hdr))
+ {
+ fdb->errors |= BATTFS_DISK_READ_ERR;
+ return total_write;
+ }
- battfs_flush(fd);
- REMOVE(&fdb->link);
- return 0;
+ /* Renew page only if is not in cache. */
+ if (kblock_buffered(disk->dev)
+ && ((fdb->start[fdb->max_off] != kblock_cachedBlock(disk->dev)) || !kblock_cacheDirty(disk->dev)))
+ {
+ new_page = renewPage(disk, fdb->start[pg_offset]);
+ if (new_page == NO_SPACE)
+ {
+ fdb->errors |= BATTFS_DISK_SPACEOVER_ERR;
+ return total_write;
+ }
+
+ LOG_INFO("Re-writing page %d to %d\n", fdb->start[pg_offset], new_page);
+ if (kblock_copy(disk->dev, fdb->start[pg_offset], new_page) != 0)
+ {
+ fdb->errors |= BATTFS_DISK_WRITE_ERR;
+ return total_write;
+ }
+ fdb->start[pg_offset] = new_page;
+ }
+ else
+ {
+ LOG_INFO("Using cached block %d\n", fdb->start[pg_offset]);
+ new_page = fdb->start[pg_offset];
+ }
+
+ curr_hdr.seq++;
+ }
+ //LOG_INFO("writing to buffer for page %d, offset %d, size %d\n", disk->curr_page, addr_offset, wr_len);
+ if (kblock_write(disk->dev, new_page, buf, addr_offset, wr_len) != wr_len)
+ {
+ fdb->errors |= BATTFS_DISK_WRITE_ERR;
+ return total_write;
+ }
+
+ size -= wr_len;
+ fd->seek_pos += wr_len;
+ total_write += wr_len;
+ buf += wr_len;
+ fill_t fill_delta = MAX((int32_t)(addr_offset + wr_len) - curr_hdr.fill, (int32_t)0);
+ disk->free_bytes -= fill_delta;
+ fd->size += fill_delta;
+ curr_hdr.fill += fill_delta;
+
+ if (!writeHdr(disk, new_page, &curr_hdr))
+ {
+ fdb->errors |= BATTFS_DISK_WRITE_ERR;
+ return total_write;
+ }
+
+ //LOG_INFO("free_bytes %d, seek_pos %d, size %d, curr_hdr.fill %d\n", disk->free_bytes, fd->seek_pos, fd->size, curr_hdr.fill);
+ }
+ return total_write;
}
+
/**
* Read from file \a fd \a size bytes in \a buf.
* \return The number of bytes read.
*/
static size_t battfs_read(struct KFile *fd, void *_buf, size_t size)
{
- BattFS *fdb = BATTFSKFILE(fd);
+ BattFs *fdb = BATTFS_CAST(fd);
+ BattFsSuper *disk = fdb->disk;
uint8_t *buf = (uint8_t *)_buf;
size_t total_read = 0;
pgaddr_t addr_offset;
pgaddr_t read_len;
- size = MIN((kfile_off_t)size, fd->size - fd->seek_pos);
+ if (fd->seek_pos < 0)
+ {
+ fdb->errors |= BATTFS_NEGATIVE_SEEK_ERR;
+ return total_read;
+ }
+
+ size = MIN((kfile_off_t)size, MAX(fd->size - fd->seek_pos, (kfile_off_t)0));
while (size)
{
- pg_offset = fd->seek_pos / (fdb->disk->page_size - BATTFS_HEADER_LEN);
- addr_offset = fd->seek_pos % (fdb->disk->page_size - BATTFS_HEADER_LEN);
- read_len = MIN(size, (size_t)(fdb->disk->page_size - BATTFS_HEADER_LEN - addr_offset));
+ pg_offset = fd->seek_pos / disk->data_size;
+ addr_offset = fd->seek_pos % disk->data_size;
+ read_len = MIN(size, (size_t)(disk->data_size - addr_offset));
+ //LOG_INFO("reading from page %d, offset %d, size %d\n", fdb->start[pg_offset], addr_offset, read_len);
/* Read from disk */
- if (fdb->disk->read(fdb->disk, fdb->start[pg_offset], addr_offset, buf, read_len) != read_len)
+ if (kblock_read(disk->dev, fdb->start[pg_offset], buf, addr_offset, read_len) != read_len)
{
- #warning TODO set error?
+ fdb->errors |= BATTFS_DISK_READ_ERR;
+ return total_read;
}
+ #ifdef _DEBUG
+ BattFsPageHeader hdr;
+ readHdr(disk, fdb->start[pg_offset], &hdr);
+ ASSERT(hdr.inode == fdb->inode);
+ #endif
+
size -= read_len;
fd->seek_pos += read_len;
total_read += read_len;
/**
* Search file \a inode in \a disk using a binary search.
- * \return pointer to file start in disk->page_array
- * if file exists, NULL otherwise.
+ * \a last is filled with array offset of file start
+ * in disk->page_array if file is found, otherwise
+ * \a last is filled with the correct insert position
+ * for creating a file with the given \a inode.
+ * \return true if file is found, false otherwisr.
*/
-static pgcnt_t *findFile(BattFsSuper *disk, inode_t inode)
+static bool findFile(BattFsSuper *disk, inode_t inode, pgcnt_t *last)
{
BattFsPageHeader hdr;
- pgcnt_t first = 0, page, last = disk->page_count -1;
+ pgcnt_t first = 0, page;
+ *last = disk->free_page_start;
fcs_t fcs;
- while (first <= last)
+ while (first < *last)
{
- page = (first + last) / 2;
-
- if (!battfs_readHeader(disk, disk->page_array[page], &hdr))
- return NULL;
-
+ page = (first + *last) / 2;
+ LOG_INFO("first %d, last %d, page %d\n", first, *last, page);
+ if (!readHdr(disk, disk->page_array[page], &hdr))
+ return false;
+ LOG_INFO("inode read: %d\n", hdr.inode);
fcs = computeFcs(&hdr);
if (hdr.fcs == fcs && hdr.inode == inode)
- return (&disk->page_array[page]) - hdr.pgoff;
+ {
+ *last = page - hdr.pgoff;
+ LOG_INFO("Found: %d\n", *last);
+ return true;
+ }
else if (hdr.fcs == fcs && hdr.inode < inode)
first = page + 1;
else
- last = page - 1;
+ *last = page;
}
-
- return NULL;
+ LOG_INFO("Not found: last %d\n", *last);
+ return false;
}
/**
*/
bool battfs_fileExists(BattFsSuper *disk, inode_t inode)
{
- return findFile(disk, inode) != NULL;
+ pgcnt_t dummy;
+ return findFile(disk, inode, &dummy);
}
/**
* in disk->page_array. Size is written in \a size.
* \return true if all s ok, false on disk read errors.
*/
-static bool countFileSize(BattFsSuper *disk, pgcnt_t *start, inode_t inode, file_size_t *size)
+static file_size_t countFileSize(BattFsSuper *disk, pgcnt_t *start, inode_t inode)
{
- *size = 0;
+ file_size_t size = 0;
BattFsPageHeader hdr;
- for (;;)
+ while (start < &disk->page_array[disk->free_page_start])
{
- if (!battfs_readHeader(disk, *start++, &hdr))
- return false;
+ if (!readHdr(disk, *start++, &hdr))
+ return EOF;
if (hdr.fcs == computeFcs(&hdr) && hdr.inode == inode)
- *size += hdr.fill;
+ size += hdr.fill;
else
- return true;
+ break;
}
+ return size;
+}
+
+static int battfs_error(struct KFile *fd)
+{
+ BattFs *fdb = BATTFS_CAST(fd);
+ return fdb->errors;
+}
+
+
+static void battfs_clearerr(struct KFile *fd)
+{
+ BattFs *fdb = BATTFS_CAST(fd);
+ fdb->errors = 0;
}
/**
* File context is stored in \a fd.
* \return true if ok, false otherwise.
*/
-bool battfs_fileopen(BattFsSuper *disk, BattFS *fd, inode_t inode, filemode_t mode)
+bool battfs_fileopen(BattFsSuper *disk, BattFs *fd, inode_t inode, filemode_t mode)
{
Node *n;
memset(fd, 0, sizeof(*fd));
/* Search file start point in disk page array */
- fd->start = findFile(disk, inode);
- if (fd->start == NULL)
+ pgcnt_t start_pos;
+ if (!findFile(disk, inode, &start_pos))
{
+ LOG_INFO("file %d not found\n", inode);
if (!(mode & BATTFS_CREATE))
+ {
+ fd->errors |= BATTFS_FILE_NOT_FOUND_ERR;
return false;
-
- /* File does not exist, create it */
+ }
+ /* Create the file */
BattFsPageHeader hdr;
+
+ if (allocateNewPage(disk, start_pos, inode) == NO_SPACE)
+ {
+ fd->errors |= BATTFS_DISK_SPACEOVER_ERR;
+ return false;
+ }
+
hdr.inode = inode;
- 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!
+ hdr.fill = 0;
+ hdr.seq = 0;
+ if (!writeHdr(disk, disk->page_array[start_pos], &hdr))
+ {
+ fd->errors |= BATTFS_DISK_WRITE_ERR;
+ return false;
+ }
}
+ fd->start = &disk->page_array[start_pos];
+ LOG_INFO("Start pos %d\n", start_pos);
/* Fill file size */
- if (!countFileSize(disk, fd->start, inode, &fd->fd.size))
+ if ((fd->fd.size = countFileSize(disk, fd->start, inode)) == EOF)
+ {
+ fd->errors |= BATTFS_DISK_READ_ERR;
return false;
+ }
+ fd->max_off = fd->fd.size / disk->data_size;
/* Reset seek position */
fd->fd.seek_pos = 0;
/* Insert file handle in list, ordered by inode, ascending. */
FOREACH_NODE(n, &disk->file_opened_list)
{
- BattFS *file = containerof(n, BattFS, 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;
+
fd->fd.error = battfs_error;
fd->fd.clearerr = battfs_clearerr;
-#endif
DB(fd->fd._type = KFT_BATTFS);
return true;
}
+
/**
- * Close \a disk.
+ * Umount \a disk.
*/
-bool battfs_close(struct BattFsSuper *disk)
+bool battfs_umount(struct BattFsSuper *disk)
{
Node *n;
int res = 0;
/* Close all open files */
FOREACH_NODE(n, &disk->file_opened_list)
{
- BattFS *file = containerof(n, BattFS, link);
+ BattFs *file = containerof(n, BattFs, link);
res += battfs_fileclose(&file->fd);
}
/* Close disk */
- return disk->close(disk) && (res == 0);
+ return (kblock_flush(disk->dev) == 0) && (kblock_close(disk->dev) == 0) && (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, mark_t mark)
+void battfs_writeTestBlock(KBlock *dev, pgcnt_t page, inode_t inode, seq_t seq, fill_t fill, pgoff_t pgoff)
{
- BattFsPageHeader hdr;
+ uint8_t buf[BATTFS_HEADER_LEN];
+ battfs_eraseBlock(dev, page);
+ 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");
- return false;
- }
+ battfs_to_disk(&hdr, buf);
- return true;
+ ASSERT(kblock_write(dev, page, buf, dev->blk_size - BATTFS_HEADER_LEN, BATTFS_HEADER_LEN) == BATTFS_HEADER_LEN);
+ ASSERT(kblock_flush(dev) == 0);
}
+
+void battfs_eraseBlock(KBlock *dev, pgcnt_t page)
+{
+ /* Reset page to all 0xff */
+ uint8_t buf[dev->blk_size];
+ memset(buf, 0xFF, dev->blk_size);
+ ASSERT(kblock_write(dev, page, buf, 0, dev->blk_size) == dev->blk_size);
+ ASSERT(kblock_flush(dev) == 0);
+}
+
+#endif