4 * This file is part of BeRTOS.
6 * Bertos is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 * As a special exception, you may use this file as part of a free software
21 * library without restriction. Specifically, if other files instantiate
22 * templates or use macros or inline functions from this file, or you compile
23 * this file and link it with other files to produce an executable, this
24 * file does not by itself cause the resulting executable to be covered by
25 * the GNU General Public License. This exception does not however
26 * invalidate any other reasons why the executable file might be covered by
27 * the GNU General Public License.
29 * Copyright 2007 Develer S.r.l. (http://www.develer.com/)
35 * \author Francesco Sacchi <batt@develer.com>
37 * \brief BattFS: a filesystem for embedded platforms (implementation).
42 #include <cfg/debug.h>
43 #include <cfg/macros.h> /* MIN, MAX */
44 #include <mware/byteorder.h> /* cpu_to_xx */
47 #include <string.h> /* memset, memmove */
51 * Convert from memory representation to disk structure.
52 * \note filesystem is in little-endian format.
54 INLINE void battfs_to_disk(struct BattFsPageHeader *hdr, uint8_t *buf)
56 STATIC_ASSERT(BATTFS_HEADER_LEN == 12);
60 buf[2] = hdr->fill >> 8;
63 buf[4] = hdr->pgoff >> 8;
66 * Mark is at least 1 bit longer than page address.
67 * Needed to take care of wraparonds.
70 buf[6] = hdr->mark >> 8;
73 * First bit used by mark, last 2 bits used by seq.
74 * Since only 2 pages with the same inode and pgoff
75 * can exist at the same time, 2 bit for seq are enough.
76 * Unused bits are set to 1.
78 buf[7] = ((hdr->mark >> 16) & 0x01) | (hdr->seq << 6) | ~(BV(7) | BV(6) | BV(0));
81 * This field must be the before the last one!
83 buf[8] = hdr->fcs_free;
84 buf[9] = hdr->fcs_free >> 8;
87 * This field must be the last one!
88 * This is needed because if the page is only partially
89 * written, we can use this to detect it.
92 buf[11] = hdr->fcs >> 8;
96 * Convert from disk structure to memory representation.
97 * \note filesystem is in little-endian format.
99 INLINE void disk_to_battfs(uint8_t *buf, struct BattFsPageHeader *hdr)
101 STATIC_ASSERT(BATTFS_HEADER_LEN == 12);
103 hdr->fill = buf[2] << 8 | buf[1];
104 hdr->pgoff = buf[4] << 8 | buf[3];
105 hdr->mark = (mark_t)(buf[7] & 0x01) << 16 | buf[6] << 8 | buf[5];
106 hdr->seq = buf[7] >> 6;
107 hdr->fcs_free = buf[9] << 8 | buf[8];
108 hdr->fcs = buf[11] << 8 | buf[10];
112 * Compute the fcs of the header.
114 static fcs_t computeFcs(struct BattFsPageHeader *hdr)
116 uint8_t buf[BATTFS_HEADER_LEN];
119 battfs_to_disk(hdr, buf);
121 /* fcs is at the end of whole header */
122 rotating_update(buf, BATTFS_HEADER_LEN - sizeof(fcs_t), &cks);
127 * Compute the fcs of the header marked as free.
129 static fcs_t computeFcsFree(struct BattFsPageHeader *hdr)
131 uint8_t buf[BATTFS_HEADER_LEN];
134 battfs_to_disk(hdr, buf);
136 /* fcs_free is just before fcs of whole header */
137 rotating_update(buf, BATTFS_HEADER_LEN - 2 * sizeof(fcs_t), &cks);
143 * Read header of page \a page.
144 * \return true on success, false otherwise.
145 * \note \a hdr is dirtyed even on errors.
147 static bool battfs_readHeader(struct BattFsSuper *disk, pgcnt_t page, struct BattFsPageHeader *hdr)
149 uint8_t buf[BATTFS_HEADER_LEN];
151 * Read header from disk.
152 * Header is actually a footer, and so
153 * resides at page end.
155 if (disk->read(disk, page, disk->page_size - BATTFS_HEADER_LEN, buf, BATTFS_HEADER_LEN)
156 != BATTFS_HEADER_LEN)
158 TRACEMSG("Error: page[%d]\n", page);
163 disk_to_battfs(buf, hdr);
169 * Write header of page \a page.
170 * \return true on success, false otherwise.
171 * \note \a hdr is dirtyed even on errors.
173 static bool battfs_writeHeader(struct BattFsSuper *disk, pgcnt_t page, struct BattFsPageHeader *hdr)
175 uint8_t buf[BATTFS_HEADER_LEN];
178 battfs_to_disk(hdr, buf);
181 * write header to disk.
182 * Header is actually a footer, and so
183 * resides at page end.
185 if (disk->write(disk, page, disk->page_size - BATTFS_HEADER_LEN, buf, BATTFS_HEADER_LEN)
186 != BATTFS_HEADER_LEN)
188 TRACEMSG("Error: page[%d]\n", page);
195 * Count the number of pages from
196 * inode 0 to \a inode in \a filelen_table.
198 static pgcnt_t countPages(pgoff_t *filelen_table, inode_t inode)
202 for (inode_t i = 0; i < inode; i++)
203 cnt += filelen_table[i];
209 * Move all pages in page allocation array from \a src to \a src + \a offset.
210 * The number of pages moved is page_count - MAX(dst, src).
212 static void movePages(struct BattFsSuper *disk, pgcnt_t src, int offset)
214 pgcnt_t dst = src + offset;
215 memmove(&disk->page_array[dst], &disk->page_array[src], (disk->page_count - MAX(dst, src)) * sizeof(pgcnt_t));
219 /* Fill empty space in array with sentinel */
220 for (pgcnt_t page = disk->page_count + offset; page < disk->page_count; page++)
221 disk->page_array[page] = PAGE_UNSET_SENTINEL;
226 * Insert \a page into page allocation array of \a disk,
227 * using \a mark to compute position.
229 static void insertFreePage(struct BattFsSuper *disk, mark_t mark, pgcnt_t page)
231 ASSERT(mark - disk->free_start < disk->free_next - disk->free_start);
233 pgcnt_t free_pos = disk->page_count - disk->free_next + mark;
234 ASSERT(free_pos < disk->page_count);
236 TRACEMSG("mark:%u, page:%u, free_start:%u, free_next:%u, free_pos:%u\n",
237 mark, page, disk->free_start, disk->free_next, free_pos);
239 ASSERT(disk->page_array[free_pos] == PAGE_UNSET_SENTINEL);
240 disk->page_array[free_pos] = page;
244 * Mark \a page of \a disk as free.
245 * \note free_next of \a disk is used as \a page free marker
246 * and is increased by 1.
248 static bool battfs_markFree(struct BattFsSuper *disk, struct BattFsPageHeader *hdr, pgcnt_t page)
250 uint8_t buf[BATTFS_HEADER_LEN];
252 hdr->mark = disk->free_next;
253 hdr->fcs_free = computeFcsFree(hdr);
254 battfs_to_disk(hdr, buf);
256 if (!disk->write(disk, page, disk->page_size - BATTFS_HEADER_LEN, buf, BATTFS_HEADER_LEN))
258 TRACEMSG("error marking page [%d]\n", page);
269 * Determine free_start and free_next blocks for \a disk
270 * using \a minl, \a maxl, \a minh, \a maxh.
272 * Mark_t is a type that has at least 1 bit more than
273 * pgaddr_t. So all free blocks can be numbered using
274 * at most half numbers of a mark_t type.
275 * The free blocks algorithm increments by 1 the disk->free_next
276 * every time a page becomes free. So the free block sequence is
277 * guaranteed to be countiguous.
278 * Only wrap arounds may happen, but due to half size sequence limitation,
279 * there are only 4 possible situations:
282 * |------lower half------|-------upper half-------|
284 * 1) |------minl*****maxl---|------------------------|
285 * 2) |------minl********maxl|minh******maxh----------|
286 * 3) |----------------------|----minh*******maxh-----|
287 * 4) |minl******maxl--------|------------minh****maxh|
290 * Situations 1 and 3 are easy to detect, while 2 and 4 require more care.
292 static void findFreeStartNext(struct BattFsSuper *disk, mark_t minl, mark_t maxl, mark_t minh, mark_t maxh)
294 /* Determine free_start & free_next */
297 /* Valid interval found in lower half */
300 /* Valid interval also found in upper half */
301 if (maxl == minh - 1)
303 /* Interval starts in lower half and ends in upper */
304 disk->free_start = minl;
305 disk->free_next = maxh;
309 /* Interval starts in upper half and ends in lower */
311 ASSERT(maxh == (MAX_PAGE_ADDR | MARK_HALF_SIZE));
313 disk->free_start = minh;
314 disk->free_next = maxl;
320 * Upper interval is invalid.
324 disk->free_start = minl;
325 disk->free_next = maxl;
328 else if (maxh >= minh)
331 * Lower interval is invalid.
334 disk->free_start = minh;
335 disk->free_next = maxh;
340 * No valid interval found.
341 * Hopefully the disk is brand new (or full).
343 TRACEMSG("No valid marked free block found, new disk or disk full\n");
344 disk->free_start = 0;
345 disk->free_next = -1; //to be increased later
348 /* free_next should contain the first usable address */
351 TRACEMSG("Free markers:\n minl %u\n maxl %u\n minh %u\n maxh %u\n free_start %u\n free_next %u\n",
352 minl, maxl, minh, maxh, disk->free_start, disk->free_next);
356 * Count number of pages per file on \a disk.
357 * This information is registered in \a filelen_table.
358 * Array index represent file inode, while value contained
359 * is the number of pages used by that file.
361 * \return true if ok, false on disk read errors.
362 * \note The whole disk is scanned once.
364 static bool countDiskFilePages(struct BattFsSuper *disk, pgoff_t *filelen_table)
366 BattFsPageHeader hdr;
367 mark_t minl, maxl, minh, maxh;
369 /* Initialize min and max counters to keep trace od free blocks */
370 minl = MAX_PAGE_ADDR;
372 minh = MAX_PAGE_ADDR | MARK_HALF_SIZE;
373 maxh = 0 | MARK_HALF_SIZE;
376 /* Count the number of disk page per file */
377 for (pgcnt_t page = 0; page < disk->page_count; page++)
379 if (!battfs_readHeader(disk, page, &hdr))
382 /* Check header FCS */
383 if (hdr.fcs == computeFcs(&hdr))
385 ASSERT(hdr.mark == MARK_PAGE_VALID);
386 ASSERT(hdr.fcs_free == FCS_FREE_VALID);
387 ASSERT(hdr.fill <= disk->page_size - BATTFS_HEADER_LEN);
389 /* Page is valid and is owned by a file */
390 filelen_table[hdr.inode]++;
392 /* Keep trace of free space */
393 disk->free_bytes += disk->page_size - BATTFS_HEADER_LEN - hdr.fill;
397 /* Increase free space */
398 disk->free_bytes += disk->page_size - BATTFS_HEADER_LEN;
400 /* Check if page is marked free */
401 if (hdr.fcs_free == computeFcsFree(&hdr))
404 * This page is a valid and marked free page.
405 * Update min and max free page markers.
407 if (hdr.mark < MARK_HALF_SIZE)
409 minl = MIN(minl, hdr.mark);
410 maxl = MAX(maxl, hdr.mark);
414 minh = MIN(minh, hdr.mark);
415 maxh = MAX(maxh, hdr.mark);
419 TRACEMSG("page [%d] invalid, keeping as free\n", page);
422 findFreeStartNext(disk, minl, maxl, minh, maxh);
427 * Fill page allocation array of \a disk
428 * using file lenghts in \a filelen_table.
430 * The page allocation array is an array containings all file infos.
431 * Is ordered by file, and within each file is ordered by page offset
433 * e.g. : at page array[0] you will find page address of the first page
434 * of the first file (if present).
435 * Free blocks are allocated after the last file, starting from invalid ones
436 * and continuing with the marked free ones.
438 * \return true if ok, false on disk read errors.
439 * \note The whole disk is scanned once.
441 static bool fillPageArray(struct BattFsSuper *disk, pgoff_t *filelen_table)
443 BattFsPageHeader hdr;
444 /* Fill page allocation array */
445 for (pgcnt_t page = 0; page < disk->page_count; page++)
447 if (!battfs_readHeader(disk, page, &hdr))
450 /* Check header FCS */
451 if (hdr.fcs == computeFcs(&hdr))
453 /* Page is valid and is owned by a file */
454 ASSERT(hdr.mark == MARK_PAGE_VALID);
455 ASSERT(hdr.fcs_free == FCS_FREE_VALID);
457 /* Compute array position */
458 pgcnt_t array_pos = countPages(filelen_table, hdr.inode);
459 array_pos += hdr.pgoff;
461 /* Check if position is already used by another page of the same file */
462 if (LIKELY(disk->page_array[array_pos] == PAGE_UNSET_SENTINEL))
463 disk->page_array[array_pos] = page;
466 BattFsPageHeader hdr_old;
468 if (!battfs_readHeader(disk, disk->page_array[array_pos], &hdr_old))
471 /* Check header FCS */
472 ASSERT(hdr_old.fcs == computeFcs(&hdr_old));
474 /* Only the very same page with a different seq number can be here */
475 ASSERT(hdr.inode == hdr_old.inode);
476 ASSERT(hdr.pgoff == hdr_old.pgoff);
477 ASSERT(hdr.mark == hdr_old.mark);
478 ASSERT(hdr.fcs_free == hdr_old.fcs_free);
479 ASSERT(hdr.seq != hdr_old.seq);
481 pgcnt_t new_page, old_page;
484 /* Fancy check to handle seq wraparound (2 bits only) */
485 if (((hdr.seq - hdr_old.seq) & 0x03) < 2)
487 /* Current header is newer than the previuos one */
488 old_page = disk->page_array[array_pos];
490 old_fill = hdr_old.fill;
494 /* Previous header is newer than the current one */
496 new_page = disk->page_array[array_pos];
501 disk->page_array[array_pos] = new_page;
504 disk->free_bytes += old_fill;
506 /* Shift all array one position to the left, overwriting duplicate page */
507 array_pos -= hdr.pgoff;
508 array_pos += filelen_table[hdr.inode];
509 movePages(disk, array_pos, -1);
511 /* Decrease file page count */
512 filelen_table[hdr.inode]--;
514 /* Add old page to free pages pool */
515 if (!battfs_markFree(disk, &hdr, old_page))
518 insertFreePage(disk, hdr.mark, old_page);
523 /* Check if page is free */
524 if (hdr.fcs_free != computeFcsFree(&hdr))
525 /* Page is not a valid marked page, insert at list beginning */
526 hdr.mark = --disk->free_start;
528 insertFreePage(disk, hdr.mark, page);
535 * Initialize and mount disk described by
537 * \return false on errors, true otherwise.
539 bool battfs_init(struct BattFsSuper *disk)
541 pgoff_t filelen_table[BATTFS_MAX_FILES];
546 /* Init disk device */
547 if (!disk->open(disk))
549 TRACEMSG("open error\n");
553 /* Disk open must set all of these */
558 ASSERT(disk->page_size);
559 ASSERT(disk->page_count);
560 ASSERT(disk->page_count < PAGE_UNSET_SENTINEL - 1);
561 ASSERT(disk->page_array);
563 memset(filelen_table, 0, BATTFS_MAX_FILES * sizeof(pgoff_t));
565 disk->free_bytes = 0;
566 disk->disk_size = (disk_size_t)(disk->page_size - BATTFS_HEADER_LEN) * disk->page_count;
568 /* Count pages per file */
569 if (!countDiskFilePages(disk, filelen_table))
571 TRACEMSG("error counting file pages\n");
575 /* Once here, we have filelen_table filled with file lengths */
577 /* Fill page array with sentinel */
578 for (pgcnt_t page = 0; page < disk->page_count; page++)
579 disk->page_array[page] = PAGE_UNSET_SENTINEL;
581 /* Fill page allocation array using filelen_table */
582 if (!fillPageArray(disk, filelen_table))
584 TRACEMSG("error filling page array\n");
588 /* Init list for opened files. */
589 LIST_INIT(&disk->file_opened_list);
595 * \return 0 if ok, EOF on errors.
597 static int battfs_flush(struct KFile *fd)
606 * \return 0 if ok, EOF on errors.
608 static int battfs_fileclose(struct KFile *fd)
610 KFileBattFs *fdb = KFILEBATTFS(fd);
618 * Read from file \a fd \a size bytes in \a buf.
619 * \return The number of bytes read.
621 static size_t battfs_read(struct KFile *fd, void *_buf, size_t size)
623 KFileBattFs *fdb = KFILEBATTFS(fd);
624 uint8_t *buf = (uint8_t *)_buf;
626 size_t total_read = 0;
628 pgaddr_t addr_offset;
631 size = MIN(size, fd->size - fd->seek_pos);
635 pg_offset = fd->seek_pos / (fdb->disk->page_size - BATTFS_HEADER_LEN);
636 addr_offset = fd->seek_pos % (fdb->disk->page_size - BATTFS_HEADER_LEN);
637 read_len = MIN(size, (size_t)(fdb->disk->page_size - BATTFS_HEADER_LEN - addr_offset));
640 if (fdb->disk->read(fdb->disk, fdb->start[pg_offset], addr_offset, buf, read_len) != read_len)
642 #warning TODO set error?
646 fd->seek_pos += read_len;
647 total_read += read_len;
655 * Search file \a inode in \a disk using a binary search.
656 * \return pointer to file start in disk->page_array
657 * if file exists, NULL otherwise.
659 static pgcnt_t *findFile(BattFsSuper *disk, inode_t inode)
661 BattFsPageHeader hdr;
662 pgcnt_t first = 0, page, last = disk->page_count -1;
665 while (first <= last)
667 page = (first + last) / 2;
669 if (!battfs_readHeader(disk, disk->page_array[page], &hdr))
672 fcs = computeFcs(&hdr);
673 if (hdr.fcs == fcs && hdr.inode == inode)
674 return (&disk->page_array[page]) - hdr.pgoff;
675 else if (hdr.fcs == fcs && hdr.inode < inode)
685 * \return true if file \a inode exists on \a disk, false otherwise.
687 bool battfs_fileExists(BattFsSuper *disk, inode_t inode)
689 return findFile(disk, inode) != NULL;
693 * Count size of file \a inode on \a disk, starting at pointer \a start
694 * in disk->page_array. Size is written in \a size.
695 * \return true if all s ok, false on disk read errors.
697 static bool countFileSize(BattFsSuper *disk, pgcnt_t *start, inode_t inode, file_size_t *size)
700 BattFsPageHeader hdr;
704 if (!battfs_readHeader(disk, *start++, &hdr))
706 if (hdr.fcs == computeFcs(&hdr) && hdr.inode == inode)
714 * Open file \a inode from \a disk in \a mode.
715 * File context is stored in \a fd.
716 * \return true if ok, false otherwise.
718 bool battfs_fileopen(BattFsSuper *disk, KFileBattFs *fd, inode_t inode, filemode_t mode)
722 memset(fd, 0, sizeof(*fd));
724 /* Search file start point in disk page array */
725 fd->start = findFile(disk, inode);
726 if (fd->start == NULL)
728 if (!(mode & BATTFS_CREATE))
731 /* File does not exist, create it */
732 BattFsPageHeader hdr;
737 hdr.mark = MARK_PAGE_VALID;
738 hdr.fcs_free = FCS_FREE_VALID;
739 hdr.fcs = computeFcs(&hdr);
740 #warning TODO: get a free block and write on disk!
744 if (!countFileSize(disk, fd->start, inode, &fd->fd.size))
747 /* Reset seek position */
750 /* Insert file handle in list, ordered by inode, ascending. */
751 FOREACH_NODE(n, &disk->file_opened_list)
753 KFileBattFs *file = containerof(n, KFileBattFs, link);
754 if (file->inode >= inode)
757 INSERT_BEFORE(&fd->link, n);
764 fd->fd.close = battfs_fileclose;
765 fd->fd.flush = battfs_flush;
766 fd->fd.read = battfs_read;
767 fd->fd.reopen = kfile_genericReopen;
768 fd->fd.seek = kfile_genericSeek;
770 #warning TODO battfs_write, battfs_error, battfs_clearerr
772 fd->fd.write = battfs_write;
773 fd->fd.error = battfs_error;
774 fd->fd.clearerr = battfs_clearerr;
777 DB(fd->fd._type = KFT_BATTFS);
785 bool battfs_close(struct BattFsSuper *disk)
790 /* Close all open files */
791 FOREACH_NODE(n, &disk->file_opened_list)
793 KFileBattFs *file = containerof(n, KFileBattFs, link);
794 res += battfs_fileclose(&file->fd);
798 return disk->close(disk) && (res == 0);
802 bool battfs_writeTestBlock(struct BattFsSuper *disk, pgcnt_t page, inode_t inode, seq_t seq, fill_t fill, pgoff_t pgoff, mark_t mark)
804 BattFsPageHeader hdr;
810 hdr.mark = MARK_PAGE_VALID;
811 hdr.fcs_free = FCS_FREE_VALID;
812 hdr.fcs = computeFcs(&hdr);
813 if (mark != MARK_PAGE_VALID)
816 hdr.fcs_free = computeFcsFree(&hdr);
819 if (!battfs_writeHeader(disk, page, &hdr))
821 TRACEMSG("error writing hdr\n");