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/)
33 * \brief BattFS: a filesystem for embedded platforms (implementation).
37 * \author Francesco Sacchi <batt@develer.com>
43 #include <cfg/debug.h>
44 #include <cfg/macros.h> /* MIN, MAX */
45 #include <cpu/byteorder.h> /* cpu_to_xx */
47 #define LOG_LEVEL LOG_LVL_INFO
48 #define LOG_FORMAT LOG_FMT_VERBOSE
51 #include <string.h> /* memset, memmove */
55 * Convert from memory representation to disk structure.
56 * \note filesystem is in little-endian format.
58 INLINE void battfs_to_disk(struct BattFsPageHeader *hdr, uint8_t *buf)
60 STATIC_ASSERT(BATTFS_HEADER_LEN == 10);
64 buf[2] = hdr->fill >> 8;
67 buf[4] = hdr->pgoff >> 8;
70 * Sequence number is at least 1 bit longer than page address.
71 * Needed to take care of wraparonds.
74 buf[6] = hdr->seq >> 8;
77 * First bit used by seq.
78 * Unused bits are set to 1.
80 buf[7] = (hdr->seq >> 16) ? 0xFF : 0xFE;
83 * This field must be the last one!
84 * This is needed because if the page is only partially
85 * written, we can use this to detect it.
88 buf[9] = hdr->fcs >> 8;
92 * Convert from disk structure to memory representation.
93 * \note filesystem is in little-endian format.
95 INLINE void disk_to_battfs(uint8_t *buf, struct BattFsPageHeader *hdr)
97 STATIC_ASSERT(BATTFS_HEADER_LEN == 10);
99 hdr->fill = buf[2] << 8 | buf[1];
100 hdr->pgoff = buf[4] << 8 | buf[3];
101 hdr->seq = (seq_t)(buf[7] & 0x01) << 16 | buf[6] << 8 | buf[5];
102 hdr->fcs = buf[9] << 8 | buf[8];
106 * Compute the fcs of the header.
108 static fcs_t computeFcs(struct BattFsPageHeader *hdr)
110 uint8_t buf[BATTFS_HEADER_LEN];
113 battfs_to_disk(hdr, buf);
115 /* fcs is at the end of whole header */
116 rotating_update(buf, BATTFS_HEADER_LEN - sizeof(fcs_t), &cks);
122 * Read header of page \a page.
123 * \return true on success, false otherwise.
125 static bool battfs_readHeader(struct BattFsSuper *disk, pgcnt_t page, struct BattFsPageHeader *hdr)
127 uint8_t buf[BATTFS_HEADER_LEN];
129 * Read header from disk.
130 * Header is actually a footer, and so
131 * resides at page end.
133 if (disk->read(disk, page, disk->page_size - BATTFS_HEADER_LEN, buf, BATTFS_HEADER_LEN)
134 != BATTFS_HEADER_LEN)
136 LOG_ERR("Error: page[%d]\n", page);
141 disk_to_battfs(buf, hdr);
147 * Write header of page \a page.
148 * \return true on success, false otherwise.
150 static bool battfs_writeHeader(struct BattFsSuper *disk, pgcnt_t page, struct BattFsPageHeader *hdr)
152 uint8_t buf[BATTFS_HEADER_LEN];
155 battfs_to_disk(hdr, buf);
158 * write header to disk.
159 * Header is actually a footer, and so
160 * resides at page end.
162 if (disk->write(disk, page, disk->page_size - BATTFS_HEADER_LEN, buf, BATTFS_HEADER_LEN)
163 != BATTFS_HEADER_LEN)
165 LOG_ERR("Error: page[%d]\n", page);
172 * Count the number of pages from
173 * inode 0 to \a inode in \a filelen_table.
175 static pgcnt_t countPages(pgoff_t *filelen_table, inode_t inode)
179 for (inode_t i = 0; i < inode; i++)
180 cnt += filelen_table[i];
186 * Move all pages in page allocation array from \a src to \a src + \a offset.
187 * The number of pages moved is page_count - MAX(dst, src).
189 static void movePages(struct BattFsSuper *disk, pgcnt_t src, int offset)
191 pgcnt_t dst = src + offset;
192 memmove(&disk->page_array[dst], &disk->page_array[src], (disk->page_count - MAX(dst, src)) * sizeof(pgcnt_t));
196 /* Fill empty space in array with sentinel */
197 for (pgcnt_t page = disk->page_count + offset; page < disk->page_count; page++)
198 disk->page_array[page] = PAGE_UNSET_SENTINEL;
203 * Count number of pages per file on \a disk.
204 * This information is registered in \a filelen_table.
205 * Array index represent file inode, while value contained
206 * is the number of pages used by that file.
208 * \return true if ok, false on disk read errors.
209 * \note The whole disk is scanned once.
211 static bool countDiskFilePages(struct BattFsSuper *disk, pgoff_t *filelen_table)
213 BattFsPageHeader hdr;
214 disk->free_page_start = 0;
216 /* Count the number of disk page per file */
217 for (pgcnt_t page = 0; page < disk->page_count; page++)
219 if (!battfs_readHeader(disk, page, &hdr))
222 /* Increase free space */
223 disk->free_bytes += disk->page_size - BATTFS_HEADER_LEN;
225 /* Check header FCS */
226 if (hdr.fcs == computeFcs(&hdr))
228 ASSERT(hdr.fill <= disk->page_size - BATTFS_HEADER_LEN);
230 /* Page is valid and is owned by a file */
231 filelen_table[hdr.inode]++;
233 /* Keep trace of free space */
234 disk->free_bytes -= hdr.fill;
235 disk->free_page_start++;
238 LOG_INFO("free_bytes:%d, free_page_start:%d\n", disk->free_bytes, disk->free_page_start);
244 * Fill page allocation array of \a disk
245 * using file lenghts in \a filelen_table.
247 * The page allocation array is an array containings all file infos.
248 * Is ordered by file, and within each file is ordered by page offset
250 * e.g. : at page array[0] you will find page address of the first page
251 * of the first file (if present).
252 * Free blocks are allocated after the last file, starting from invalid ones
253 * and continuing with the marked free ones.
255 * \return true if ok, false on disk read errors.
256 * \note The whole disk is scanned once.
258 static bool fillPageArray(struct BattFsSuper *disk, pgoff_t *filelen_table)
260 BattFsPageHeader hdr;
261 pgcnt_t curr_free_page = disk->free_page_start;
262 /* Fill page allocation array */
263 for (pgcnt_t page = 0; page < disk->page_count; page++)
265 if (!battfs_readHeader(disk, page, &hdr))
268 /* Check header FCS */
269 if (hdr.fcs == computeFcs(&hdr))
271 /* Compute array position */
272 pgcnt_t array_pos_start = countPages(filelen_table, hdr.inode);
273 pgcnt_t array_pos = array_pos_start + hdr.pgoff;
275 /* Find the first free position */
276 while (disk->page_array[array_pos] != PAGE_UNSET_SENTINEL)
278 ASSERT(array_pos < array_pos_start + filelen_table[hdr.inode] + filelen_table[hdr.inode + 1]);
282 disk->page_array[array_pos] = page;
286 /* Invalid page, keep as free */
287 ASSERT(disk->page_array[curr_free_page] == PAGE_UNSET_SENTINEL);
288 LOG_INFO("Page %d invalid, keeping as free\n", page);
289 disk->page_array[curr_free_page++] = page;
296 * Find the latest version of a page, starting from the
297 * page supplied by \a page_array.
298 * The pages are read from the disk until a different
299 * inode or page offset is found.
300 * The lastest version of the page is moved in the first
301 * position of \a page_array.
302 * \return the number of old versions of the page or PAGE_ERROR
303 * on disk read errors.
305 static pgcnt_t findLastVersion(struct BattFsSuper *disk, pgcnt_t *page_array)
307 pgcnt_t *array_start = page_array;
308 BattFsPageHeader hdr;
309 if (!battfs_readHeader(disk, *page_array++, &hdr))
312 /* Free space: early bailout */
313 if (hdr.fcs != computeFcs(&hdr))
317 * If the first page is valid,
318 * inode and pg_off in the array are taken
319 * as the current page markers.
321 inode_t curr_inode = hdr.inode;
322 pgoff_t curr_pgoff = hdr.pgoff;
324 /* Temps used to find the sequence number range */
325 seq_t minl = HALF_SEQ - 1;
327 seq_t minh = MAX_SEQ;
328 seq_t maxh = MAX_SEQ;
329 pgcnt_t lpos = 0, hpos = 0, dup_cnt = 0;
332 * Find min and max values for the two
333 * half of seq_num range.
334 * With this we can find seqnum wraparounds.
335 * seq_t is a type that has at least 1 bit more than
336 * pgaddr_t. So all version of a page blocks can be numbered using
337 * at most half numbers of a seq_t type.
338 * The sequence number algorithm increments by 1 the previous seq_num
339 * every time a page is rewritten. So the sequence is
340 * guaranteed to be countiguous.
341 * Only wrap arounds may happen, but due to half size sequence limitation,
342 * there are only 4 possible situations:
345 * |------lower half------|-------upper half-------|
347 * 1) |------minl*****maxl---|------------------------|
348 * 2) |------minl********maxl|minh******maxh----------|
349 * 3) |----------------------|----minh*******maxh-----|
350 * 4) |minl******maxl--------|------------minh****maxh|
353 * Situations 1 and 3 are easy to detect, while 2 and 4 require more care.
357 if (hdr.seq < HALF_SEQ)
359 minl = MIN(minl, hdr.seq);
368 minh = MIN(minh, hdr.seq);
376 if (!battfs_readHeader(disk, *page_array++, &hdr))
380 while (curr_inode == hdr.inode && curr_pgoff == hdr.pgoff && hdr.fcs == computeFcs(&hdr));
383 /* Return early if there is only one version of the current page */
387 /* Find the position in the array of the last version of the page */
388 pgcnt_t last_ver = hpos;
391 /* Valid interval found in lower half */
394 /* Valid interval also found in upper half */
395 if (maxl != minh - 1)
397 /* Interval starts in upper half and ends in lower */
399 ASSERT(maxh == MAX_SEQ);
406 * Upper interval is invalid.
412 /* Put last page version at array start position */
413 SWAP(array_start[0], array_start[last_ver]);
419 * Collect old pages, removing empty spaces from \a pg_array, for a maximum len of \a pg_len.
420 * Once the collect task is completed, copy \a old_cnt pages from \a old_pages at the
421 * end of free space in pg_array.
423 void collectOldPages(pgcnt_t *pg_array, pgcnt_t pg_len, pgcnt_t *old_pages, pgcnt_t old_cnt)
428 for (pgcnt_t curr_page = 0; curr_page < pg_len; curr_page++)
432 if (pg_array[curr_page] == PAGE_UNSET_SENTINEL)
436 pg_array[curr_page - gap] = pg_array[curr_page];
442 if (pg_array[curr_page] != PAGE_UNSET_SENTINEL)
443 pg_array[curr_page - gap] = pg_array[curr_page];
451 ASSERT(gap == old_cnt);
452 pg_array += pg_len - old_cnt;
454 memcpy(pg_array, old_pages, old_cnt * sizeof(pgcnt_t));
458 * This function scan the page array of \a disk looking for
459 * old versions of the same page.
461 * Only the last version is kept as valid, the old ones are inserted
462 * in the free blocks heap.
463 * \return true if ok, false on disk read errors.
464 * \note The whole disk is scanned once.
466 static bool dropOldPages(struct BattFsSuper *disk)
468 #define OLD_PAGE_BUFLEN 64
469 pgcnt_t old_pages[OLD_PAGE_BUFLEN];
472 pgcnt_t *curr_page = disk->page_array;
473 pgcnt_t *collect_start = disk->page_array;
474 pgcnt_t collect_len = disk->page_count;
479 dup_pages = findLastVersion(disk, curr_page);
480 if (dup_pages == PAGE_ERROR)
482 /* The first page is the last version */
486 if (old_cnt >= OLD_PAGE_BUFLEN)
488 collectOldPages(collect_start, collect_len, old_pages, old_cnt);
489 collect_len -= old_cnt;
490 disk->free_bytes += old_cnt * (disk->page_size - BATTFS_HEADER_LEN);
491 disk->free_page_start -= old_cnt;
492 curr_page -= old_cnt;
493 collect_start = curr_page;
497 old_pages[old_cnt++] = *curr_page;
498 *curr_page++ = PAGE_UNSET_SENTINEL;
501 while (curr_page < disk->page_array + disk->free_page_start);
503 collectOldPages(collect_start, collect_len, old_pages, old_cnt);
504 disk->free_bytes += old_cnt * (disk->page_size - BATTFS_HEADER_LEN);
505 disk->free_page_start -= old_cnt;
512 * Initialize and mount disk described by
514 * \return false on errors, true otherwise.
516 bool battfs_init(struct BattFsSuper *disk)
518 pgoff_t filelen_table[BATTFS_MAX_FILES];
523 /* Init disk device */
524 if (!disk->open(disk))
526 LOG_ERR("open error\n");
530 /* Disk open must set all of these */
535 ASSERT(disk->page_size);
536 ASSERT(disk->page_count);
537 ASSERT(disk->page_count < PAGE_UNSET_SENTINEL - 1);
538 ASSERT(disk->page_array);
540 memset(filelen_table, 0, BATTFS_MAX_FILES * sizeof(pgoff_t));
542 disk->free_bytes = 0;
543 disk->disk_size = (disk_size_t)(disk->page_size - BATTFS_HEADER_LEN) * disk->page_count;
545 /* Count pages per file */
546 if (!countDiskFilePages(disk, filelen_table))
548 LOG_ERR("error counting file pages\n");
552 /* Once here, we have filelen_table filled with file lengths */
554 /* Fill page array with sentinel */
555 for (pgcnt_t page = 0; page < disk->page_count; page++)
556 disk->page_array[page] = PAGE_UNSET_SENTINEL;
558 /* Fill page allocation array using filelen_table */
559 if (!fillPageArray(disk, filelen_table))
561 LOG_ERR("error filling page array\n");
565 if (!dropOldPages(disk))
567 LOG_ERR("error dropping old pages\n");
571 /* Init list for opened files. */
572 LIST_INIT(&disk->file_opened_list);
578 * \return 0 if ok, EOF on errors.
580 static int battfs_flush(struct KFile *fd)
589 * \return 0 if ok, EOF on errors.
591 static int battfs_fileclose(struct KFile *fd)
593 BattFs *fdb = BATTFS_CAST(fd);
601 * Read from file \a fd \a size bytes in \a buf.
602 * \return The number of bytes read.
604 static size_t battfs_read(struct KFile *fd, void *_buf, size_t size)
606 BattFs *fdb = BATTFS_CAST(fd);
607 uint8_t *buf = (uint8_t *)_buf;
609 size_t total_read = 0;
611 pgaddr_t addr_offset;
614 size = MIN((kfile_off_t)size, fd->size - fd->seek_pos);
618 pg_offset = fd->seek_pos / (fdb->disk->page_size - BATTFS_HEADER_LEN);
619 addr_offset = fd->seek_pos % (fdb->disk->page_size - BATTFS_HEADER_LEN);
620 read_len = MIN(size, (size_t)(fdb->disk->page_size - BATTFS_HEADER_LEN - addr_offset));
623 if (fdb->disk->read(fdb->disk, fdb->start[pg_offset], addr_offset, buf, read_len) != read_len)
625 #warning TODO set error?
629 fd->seek_pos += read_len;
630 total_read += read_len;
638 * Search file \a inode in \a disk using a binary search.
639 * \return pointer to file start in disk->page_array
640 * if file exists, NULL otherwise.
642 static pgcnt_t *findFile(BattFsSuper *disk, inode_t inode)
644 BattFsPageHeader hdr;
645 pgcnt_t first = 0, page, last = disk->page_count -1;
648 while (first <= last)
650 page = (first + last) / 2;
652 if (!battfs_readHeader(disk, disk->page_array[page], &hdr))
655 fcs = computeFcs(&hdr);
656 if (hdr.fcs == fcs && hdr.inode == inode)
657 return (&disk->page_array[page]) - hdr.pgoff;
658 else if (hdr.fcs == fcs && hdr.inode < inode)
668 * \return true if file \a inode exists on \a disk, false otherwise.
670 bool battfs_fileExists(BattFsSuper *disk, inode_t inode)
672 return findFile(disk, inode) != NULL;
676 * Count size of file \a inode on \a disk, starting at pointer \a start
677 * in disk->page_array. Size is written in \a size.
678 * \return true if all s ok, false on disk read errors.
680 static bool countFileSize(BattFsSuper *disk, pgcnt_t *start, inode_t inode, file_size_t *size)
683 BattFsPageHeader hdr;
687 if (!battfs_readHeader(disk, *start++, &hdr))
689 if (hdr.fcs == computeFcs(&hdr) && hdr.inode == inode)
697 * Open file \a inode from \a disk in \a mode.
698 * File context is stored in \a fd.
699 * \return true if ok, false otherwise.
701 bool battfs_fileopen(BattFsSuper *disk, BattFs *fd, inode_t inode, filemode_t mode)
705 memset(fd, 0, sizeof(*fd));
707 /* Search file start point in disk page array */
708 fd->start = findFile(disk, inode);
709 if (fd->start == NULL)
711 if (!(mode & BATTFS_CREATE))
714 /* File does not exist, create it */
715 BattFsPageHeader hdr;
720 hdr.fcs = computeFcs(&hdr);
721 #warning TODO: get a free block and write on disk!
725 if (!countFileSize(disk, fd->start, inode, &fd->fd.size))
728 /* Reset seek position */
731 /* Insert file handle in list, ordered by inode, ascending. */
732 FOREACH_NODE(n, &disk->file_opened_list)
734 BattFs *file = containerof(n, BattFs, link);
735 if (file->inode >= inode)
738 INSERT_BEFORE(&fd->link, n);
745 fd->fd.close = battfs_fileclose;
746 fd->fd.flush = battfs_flush;
747 fd->fd.read = battfs_read;
748 fd->fd.reopen = kfile_genericReopen;
749 fd->fd.seek = kfile_genericSeek;
751 #warning TODO battfs_write, battfs_error, battfs_clearerr
753 fd->fd.write = battfs_write;
754 fd->fd.error = battfs_error;
755 fd->fd.clearerr = battfs_clearerr;
758 DB(fd->fd._type = KFT_BATTFS);
766 bool battfs_close(struct BattFsSuper *disk)
771 /* Close all open files */
772 FOREACH_NODE(n, &disk->file_opened_list)
774 BattFs *file = containerof(n, BattFs, link);
775 res += battfs_fileclose(&file->fd);
779 return disk->close(disk) && (res == 0);
782 bool battfs_writeTestBlock(struct BattFsSuper *disk, pgcnt_t page, inode_t inode, seq_t seq, fill_t fill, pgoff_t pgoff)
784 BattFsPageHeader hdr;
790 hdr.fcs = computeFcs(&hdr);
792 if (!battfs_writeHeader(disk, page, &hdr))
794 LOG_ERR("error writing hdr\n");