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 */
50 * Convert mark_t from cpu endianess to filesystem endianness.
51 * \note filesystem is in little-endian format.
53 INLINE mark_t cpu_to_mark_t(mark_t mark)
55 STATIC_ASSERT(sizeof(mark_t) == 2);
56 return cpu_to_le16(mark);
60 * Convert mark_t from filesystem endianness to cpu endianess.
61 * \note filesystem is in little-endian format.
63 INLINE mark_t mark_t_to_cpu(mark_t mark)
65 STATIC_ASSERT(sizeof(mark_t) == 2);
66 return le16_to_cpu(mark);
70 * Convert from cpu endianess to filesystem endianness.
71 * \note filesystem is in little-endian format.
73 INLINE void cpu_to_battfs(struct BattFsPageHeader *hdr)
75 STATIC_ASSERT(sizeof(hdr->inode) == 1);
76 STATIC_ASSERT(sizeof(hdr->seq) == 1);
78 hdr->mark = cpu_to_mark_t(hdr->mark);
80 STATIC_ASSERT(sizeof(hdr->fill) == 2);
81 hdr->fill = cpu_to_le16(hdr->fill);
83 STATIC_ASSERT(sizeof(hdr->pgoff) == 2);
84 hdr->pgoff = cpu_to_le16(hdr->pgoff);
86 STATIC_ASSERT(sizeof(hdr->fcs) == 2);
87 hdr->fcs = cpu_to_le16(hdr->fcs);
89 STATIC_ASSERT(sizeof(hdr->rfu) == 2);
90 hdr->rfu = cpu_to_le16(hdr->rfu);
95 * Convert from filesystem endianness to cpu endianess.
96 * \note filesystem is in little-endian format.
98 INLINE void battfs_to_cpu(struct BattFsPageHeader *hdr)
100 STATIC_ASSERT(sizeof(hdr->inode) == 1);
101 STATIC_ASSERT(sizeof(hdr->seq) == 1);
103 hdr->mark = mark_t_to_cpu(hdr->mark);
105 STATIC_ASSERT(sizeof(hdr->fill) == 2);
106 hdr->fill = le16_to_cpu(hdr->fill);
108 STATIC_ASSERT(sizeof(hdr->pgoff) == 2);
109 hdr->pgoff = le16_to_cpu(hdr->pgoff);
111 STATIC_ASSERT(sizeof(hdr->fcs) == 2);
112 hdr->fcs = le16_to_cpu(hdr->fcs);
114 STATIC_ASSERT(sizeof(hdr->rfu) == 2);
115 hdr->rfu = le16_to_cpu(hdr->rfu);
120 * Read header of page \a page.
121 * \return true on success, false otherwise.
122 * \note \a hdr is dirtyed even on errors.
124 static bool battfs_readHeader(struct BattFsSuper *disk, pgcnt_t page, struct BattFsPageHeader *hdr)
127 * Read header from disk.
128 * header is actually a footer, and so
129 * resides at page end.
131 if (disk->read(disk, page, disk->page_size - sizeof(BattFsPageHeader), hdr, sizeof(BattFsPageHeader))
132 != sizeof(BattFsPageHeader))
134 TRACEMSG("Error: page[%d]\n", page);
145 * Count the number of pages from
146 * inode 0 to \a inode in \a filelen_table.
148 static pgcnt_t countPages(pgoff_t *filelen_table, inode_t inode)
152 for (inode_t i = 0; i < inode; i++)
153 cnt += filelen_table[i];
159 * Move all pages in page allocation array from \a src to \a src + \a offset.
160 * The number of pages moved is page_count - MAX(dst, src).
162 static void movePages(struct BattFsSuper *disk, pgcnt_t src, int offset)
164 pgcnt_t dst = src + offset;
165 memmove(&disk->page_array[dst], &disk->page_array[src], disk->page_count - MAX(dst, src) * sizeof(pgcnt_t));
169 /* Fill empty space in array with sentinel */
170 for (pgcnt_t page = disk->page_count + offset; page < disk->page_count; page++)
171 disk->page_array[page] = PAGE_UNSET_SENTINEL;
176 * Insert \a page into page allocation array of \a disk, using \a filelen_table and
177 * \a free_number to compute position.
179 static void insertFreePage(struct BattFsSuper *disk, pgoff_t *filelen_table, mark_t free_number, pgcnt_t page)
181 ASSERT(free_number >= disk->min_free);
182 ASSERT(free_number <= disk->max_free);
184 pgcnt_t free_pos = countPages(filelen_table, BATTFS_MAX_FILES - 1);
185 free_pos += free_number - disk->min_free;
186 ASSERT(disk->page_array[free_pos] == PAGE_UNSET_SENTINEL);
187 disk->page_array[free_pos] = page;
191 * Mark \a page of \a disk as free.
192 * \note max_free of \a disk is increased by 1 and is used as
193 * \a page free marker.
195 static bool battfs_markFree(struct BattFsSuper *disk, pgcnt_t page)
197 pgaddr_t addr = disk->page_size - sizeof(BattFsPageHeader) + offsetof(BattFsPageHeader, mark);
198 mark_t mark = cpu_to_mark_t(++disk->max_free);
199 if (!disk->write(disk, page, addr, &mark, sizeof(mark)))
201 TRACEMSG("error marking page [%d]\n", page);
210 * Initialize and mount disk described by
212 * \return false on errors, true otherwise.
214 bool battfs_init(struct BattFsSuper *disk)
216 BattFsPageHeader hdr;
218 pgoff_t filelen_table[BATTFS_MAX_FILES];
226 ASSERT(disk->page_size);
227 ASSERT(disk->page_count);
228 ASSERT(disk->page_count < PAGE_UNSET_SENTINEL - 1);
229 ASSERT(disk->page_array);
231 /* Init disk device */
232 if (!disk->open(disk))
234 TRACEMSG("open error\n");
238 memset(filelen_table, 0, BATTFS_MAX_FILES * sizeof(pgoff_t));
240 /* Initialize min free sequence number to max value */
241 disk->min_free = MARK_PAGE_VALID;
242 /* Initialize max free sequence number to min value */
245 disk->free_bytes = 0;
246 disk->disk_size = (disk_size_t)(disk->page_size - sizeof(BattFsPageHeader)) * disk->page_count;
248 /* Count the number of disk page per files */
249 for (pgcnt_t page = 0; page < disk->page_count; page++)
251 if (!battfs_readHeader(disk, page, &hdr))
254 /* Check header FCS */
256 rotating_update(&hdr, sizeof(BattFsPageHeader) - sizeof(rotating_t), &cks);
259 /* Page is valid and is owned by a file */
260 filelen_table[hdr.inode]++;
262 ASSERT(hdr.mark == MARK_PAGE_VALID);
263 ASSERT(hdr.fill <= disk->page_size - sizeof(BattFsPageHeader));
264 /* Keep trace of free space */
265 disk->free_bytes += disk->page_size - sizeof(BattFsPageHeader) - hdr.fill;
269 /* Increase free space */
270 disk->free_bytes += disk->page_size - sizeof(BattFsPageHeader);
272 /* Check if setting mark to MARK_PAGE_VALID makes fcs correct */
273 mark_t old_mark = hdr.mark;
274 hdr.mark = MARK_PAGE_VALID;
276 rotating_update(&hdr, sizeof(BattFsPageHeader) - sizeof(rotating_t), &cks);
280 * This page is a valid and marked free page.
281 * Update min and max free page sequence numbers.
283 disk->min_free = MIN(disk->min_free, old_mark);
284 disk->max_free = MAX(disk->max_free, old_mark);
287 TRACEMSG("page [%d] invalid, keeping as free\n", page);
291 /* Once here, we have filelen_table filled with file lengths */
293 /* Fill page array with sentinel */
294 for (pgcnt_t page = 0; page < disk->page_count; page++)
295 disk->page_array[page] = PAGE_UNSET_SENTINEL;
297 /* Fill page allocation array */
298 for (pgcnt_t page = 0; page < disk->page_count; page++)
300 if (!battfs_readHeader(disk, page, &hdr))
303 /* Check header FCS */
305 rotating_update(&hdr, sizeof(BattFsPageHeader) - sizeof(rotating_t), &cks);
308 /* Page is valid and is owned by a file */
309 ASSERT(hdr.mark == MARK_PAGE_VALID);
311 /* Compute array position */
312 pgcnt_t array_pos = countPages(filelen_table, hdr.inode);
313 array_pos += hdr.pgoff;
315 /* Check if position is already used by another page of the same file */
316 if (disk->page_array[array_pos] == PAGE_UNSET_SENTINEL)
317 disk->page_array[array_pos] = page;
320 BattFsPageHeader hdr_old;
322 if (!battfs_readHeader(disk, disk->page_array[array_pos], &hdr_old))
326 /* Check header FCS */
328 rotating_init(&cks_old);
329 rotating_update(&hdr_old, sizeof(BattFsPageHeader) - sizeof(rotating_t), &cks_old);
330 ASSERT(cks_old == hdr_old.fcs);
333 /* Only the very same page with a different seq number can be here */
334 ASSERT(hdr.inode == hdr_old.inode);
335 ASSERT(hdr.pgoff == hdr_old.pgoff);
336 ASSERT(hdr.mark == hdr_old.mark);
337 ASSERT(hdr.seq != hdr_old.seq);
339 pgcnt_t new_page, old_page;
342 /* Fancy check to handle seq wraparound */
343 #define HALF_SEQ (1 << ((sizeof(seq_t) * CPU_BITS_PER_CHAR) - 1))
344 if ((hdr.seq - hdr_old.seq) < HALF_SEQ)
346 /* Actual header is newer than the previuos one */
347 old_page = disk->page_array[array_pos];
349 old_fill = hdr_old.fill;
353 /* Previous header is newer than the current one */
355 new_page = disk->page_array[array_pos];
360 disk->page_array[array_pos] = new_page;
363 disk->free_bytes += old_fill;
365 /* Shift all array one position to the left, overwriting duplicate page */
366 array_pos -= hdr.pgoff;
367 array_pos += filelen_table[hdr.inode];
368 movePages(disk, array_pos, -1);
370 /* Decrease file page count */
371 filelen_table[hdr.inode]--;
373 /* Add old page to free pages pool */
374 if (!battfs_markFree(disk, old_page))
377 insertFreePage(disk, filelen_table, disk->max_free, old_page);
382 /* Check if setting mark to MARK_PAGE_VALID makes fcs correct */
383 mark_t mark = hdr.mark;
384 hdr.mark = MARK_PAGE_VALID;
386 rotating_update(&hdr, sizeof(BattFsPageHeader) - sizeof(rotating_t), &cks);
388 /* Page is not a valid marked page, insert at the end of list */
389 mark = ++disk->max_free;
391 insertFreePage(disk, filelen_table, mark, page);