fs/battfs.c

   1 /**
   2  * \file
   3  * <!--
   4  * This file is part of BeRTOS.
   5  *
   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.
  10  *
  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.
  15  *
  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
  19  *
  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.
  28  *
  29  * Copyright 2007 Develer S.r.l. (http://www.develer.com/)
  30  *
  31  * -->
  32  *
  33  * \version $Id:$
  34  *
  35  * \author Francesco Sacchi <batt@develer.com>
  36  *
  37  * \brief BattFS: a filesystem for embedded platforms (implementation).
  38  */
  39
  40 #include "battfs.h"
  41
  42 #include <cfg/debug.h>
  43 #include <cfg/macros.h> /* MIN, MAX */
  44 #include <mware/byteorder.h> /* cpu_to_xx */
  45
  46
  47 #include <string.h> /* memset, memmove */
  48
  49 /**
  50  * Convert mark_t from cpu endianess to filesystem endianness.
  51  * \note filesystem is in little-endian format.
  52  */
  53 INLINE mark_t cpu_to_mark_t(mark_t mark)
  54 {
  55         STATIC_ASSERT(sizeof(mark_t) == 2);
  56         return cpu_to_le16(mark);
  57 }
  58
  59 /**
  60  * Convert mark_t from filesystem endianness to cpu endianess.
  61  * \note filesystem is in little-endian format.
  62  */
  63 INLINE mark_t mark_t_to_cpu(mark_t mark)
  64 {
  65         STATIC_ASSERT(sizeof(mark_t) == 2);
  66         return le16_to_cpu(mark);
  67 }
  68
  69 /**
  70  * Convert from cpu endianess to filesystem endianness.
  71  * \note filesystem is in little-endian format.
  72  */
  73 INLINE void cpu_to_battfs(struct BattFsPageHeader *hdr)
  74 {
  75         STATIC_ASSERT(sizeof(hdr->inode) == 1);
  76         STATIC_ASSERT(sizeof(hdr->seq) == 1);
  77
  78         hdr->mark = cpu_to_mark_t(hdr->mark);
  79
  80         STATIC_ASSERT(sizeof(hdr->fill) == 2);
  81         hdr->fill = cpu_to_le16(hdr->fill);
  82
  83         STATIC_ASSERT(sizeof(hdr->pgoff) == 2);
  84         hdr->pgoff = cpu_to_le16(hdr->pgoff);
  85
  86         STATIC_ASSERT(sizeof(hdr->fcs) == 2);
  87         hdr->fcs = cpu_to_le16(hdr->fcs);
  88
  89         STATIC_ASSERT(sizeof(hdr->rfu) == 2);
  90         hdr->rfu = cpu_to_le16(hdr->rfu);
  91 }
  92
  93
  94 /**
  95  * Convert from filesystem endianness to cpu endianess.
  96  * \note filesystem is in little-endian format.
  97  */
  98 INLINE void battfs_to_cpu(struct BattFsPageHeader *hdr)
  99 {
 100         STATIC_ASSERT(sizeof(hdr->inode) == 1);
 101         STATIC_ASSERT(sizeof(hdr->seq) == 1);
 102
 103         hdr->mark = mark_t_to_cpu(hdr->mark);
 104
 105         STATIC_ASSERT(sizeof(hdr->fill) == 2);
 106         hdr->fill = le16_to_cpu(hdr->fill);
 107
 108         STATIC_ASSERT(sizeof(hdr->pgoff) == 2);
 109         hdr->pgoff = le16_to_cpu(hdr->pgoff);
 110
 111         STATIC_ASSERT(sizeof(hdr->fcs) == 2);
 112         hdr->fcs = le16_to_cpu(hdr->fcs);
 113
 114         STATIC_ASSERT(sizeof(hdr->rfu) == 2);
 115         hdr->rfu = le16_to_cpu(hdr->rfu);
 116 }
 117
 118
 119 /**
 120  * Read header of page \a page.
 121  * \return true on success, false otherwise.
 122  * \note \a hdr is dirtyed even on errors.
 123  */
 124 static bool battfs_readHeader(struct BattFsSuper *disk, pgcnt_t page, struct BattFsPageHeader *hdr)
 125 {
 126         /*
 127          * Read header from disk.
 128          * header is actually a footer, and so
 129          * resides at page end.
 130          */
 131         if (disk->read(disk, page, disk->page_size - sizeof(BattFsPageHeader), hdr, sizeof(BattFsPageHeader))
 132             != sizeof(BattFsPageHeader))
 133         {
 134                 TRACEMSG("Error: page[%d]\n", page);
 135                 return false;
 136         }
 137
 138         /* Fix endianess */
 139         battfs_to_cpu(hdr);
 140
 141         return true;
 142 }
 143
 144 /**
 145  * Count the number of pages from
 146  * inode 0 to \a inode in \a filelen_table.
 147  */
 148 static pgcnt_t countPages(pgoff_t *filelen_table, inode_t inode)
 149 {
 150         pgcnt_t cnt = 0;
 151
 152         for (inode_t i = 0; i < inode; i++)
 153                 cnt += filelen_table[i];
 154
 155         return cnt;
 156 }
 157
 158 /**
 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).
 161  */
 162 static void movePages(struct BattFsSuper *disk, pgcnt_t src, int offset)
 163 {
 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));
 166
 167         if (offset < 0)
 168         {
 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;
 172         }
 173 }
 174
 175 /**
 176  * Insert \a page into page allocation array of \a disk, using \a filelen_table and
 177  * \a free_number to compute position.
 178  */
 179 static void insertFreePage(struct BattFsSuper *disk, pgoff_t *filelen_table, mark_t free_number, pgcnt_t page)
 180 {
 181         ASSERT(mark >= disk->min_free);
 182         ASSERT(mark <= disk->max_free);
 183
 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;
 188 }
 189
 190 /**
 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.
 194  */
 195 static bool battfs_markFree(struct BattFsSuper *disk, pgcnt_t page)
 196 {
 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)))
 200         {
 201                 TRACEMSG("error marking page [%d]\n", page);
 202                 return false;
 203         }
 204         else
 205                 return true;
 206 }
 207
 208
 209 /**
 210  * Initialize and mount disk described by
 211  * \a d.
 212  * \return false on errors, true otherwise.
 213  */
 214 bool battfs_init(struct BattFsSuper *disk)
 215 {
 216         BattFsPageHeader hdr;
 217         rotating_t cks;
 218         pgoff_t filelen_table[BATTFS_MAX_FILES];
 219
 220         /* Sanity checks */
 221         ASSERT(disk->open);
 222         ASSERT(disk->read);
 223         ASSERT(disk->write);
 224         ASSERT(disk->erase);
 225         ASSERT(disk->close);
 226         ASSERT(disk->page_size);
 227         ASSERT(disk->page_count);
 228         ASSERT(disk->page_count < PAGE_UNSET_SENTINEL - 1);
 229         ASSERT(disk->page_array);
 230
 231         /* Init disk device */
 232         if (!disk->open(disk))
 233         {
 234                 TRACEMSG("open error\n");
 235                 return false;
 236         }
 237
 238         memset(filelen_table, 0, BATTFS_MAX_FILES * sizeof(pgoff_t));
 239
 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 */
 243         disk->max_free = 0;
 244
 245         disk->free_bytes = 0;
 246         disk->disk_size = (disk_size_t)(disk->page_size - sizeof(BattFsPageHeader)) * disk->page_count;
 247
 248         /* Count the number of disk page per files */
 249         for (pgcnt_t page = 0; page < disk->page_count; page++)
 250         {
 251                 if (!battfs_readHeader(disk, page, &hdr))
 252                         return false;
 253
 254                 /* Check header FCS */
 255                 rotating_init(&cks);
 256                 rotating_update(&hdr, sizeof(BattFsPageHeader) - sizeof(rotating_t), &cks);
 257                 if (cks == hdr.fcs)
 258                 {
 259                         /* Page is valid and is owned by a file */
 260                         filelen_table[hdr.inode]++;
 261
 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;
 266                 }
 267                 else
 268                 {
 269                         /* Increase free space */
 270                         disk->free_bytes += disk->page_size - sizeof(BattFsPageHeader);
 271
 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;
 275                         rotating_init(&cks);
 276                         rotating_update(&hdr, sizeof(BattFsPageHeader) - sizeof(rotating_t), &cks);
 277                         if (cks == hdr.fcs)
 278                         {
 279                                 /*
 280                                  * This page is a valid and marked free page.
 281                                  * Update min and max free page sequence numbers.
 282                                  */
 283                                 disk->min_free = MIN(disk->min_free, old_mark);
 284                                 disk->max_free = MAX(disk->max_free, old_mark);
 285                         }
 286                         else
 287                                 TRACEMSG("page [%d] invalid, keeping as free\n", page);
 288                 }
 289         }
 290
 291         /* Once here, we have filelen_table filled with file lengths */
 292
 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;
 296
 297         /* Fill page allocation array */
 298         for (pgcnt_t page = 0; page < disk->page_count; page++)
 299         {
 300                 if (!battfs_readHeader(disk, page, &hdr))
 301                         return false;
 302
 303                 /* Check header FCS */
 304                 rotating_init(&cks);
 305                 rotating_update(&hdr, sizeof(BattFsPageHeader) - sizeof(rotating_t), &cks);
 306                 if (cks == hdr.fcs)
 307                 {
 308                         /* Page is valid and is owned by a file */
 309                         ASSERT(hdr.mark == MARK_PAGE_VALID);
 310
 311                         /* Compute array position */
 312                         pgcnt_t array_pos = countPages(filelen_table, hdr.inode);
 313                         array_pos += hdr.pgoff;
 314
 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;
 318                         else
 319                         {
 320                                 BattFsPageHeader hdr_old;
 321
 322                                 if (!battfs_readHeader(disk, disk->page_array[array_pos], &hdr_old))
 323                                         return false;
 324
 325                                 #ifdef _DEBUG
 326                                 /* Check header FCS */
 327                                 rotating_t cks_old;
 328                                 rotating_init(&cks_old);
 329                                 rotating_update(&hdr_old, sizeof(BattFsPageHeader) - sizeof(rotating_t), &cks_old);
 330                                 ASSERT(cks_old == hdr_old.fcs);
 331                                 #endif
 332
 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);
 338
 339                                 pgcnt_t new_page, old_page;
 340                                 fill_t old_fill;
 341
 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)
 345                                 {
 346                                         /* Actual header is newer than the previuos one */
 347                                         old_page = disk->page_array[array_pos];
 348                                         new_page = page;
 349                                         old_fill = hdr_old.fill;
 350                                 }
 351                                 else
 352                                 {
 353                                         /* Previous header is newer than the current one */
 354                                         old_page = page;
 355                                         new_page = disk->page_array[array_pos];
 356                                         old_fill = hdr.fill;
 357                                 }
 358
 359                                 /* Set new page */
 360                                 disk->page_array[array_pos] = new_page;
 361
 362                                 /* Add free space */
 363                                 disk->free_bytes += old_fill;
 364
 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);
 369
 370                                 /* Decrease file page count */
 371                                 filelen_table[hdr.inode]--;
 372
 373                                 /* Add old page to free pages pool */
 374                                 if (!battfs_markFree(disk, old_page))
 375                                         return false;
 376
 377                                 insertFreePage(disk, filelen_table, disk->max_free, old_page);
 378                         }
 379                 }
 380                 else
 381                 {
 382                         /* Check if setting mark to MARK_PAGE_VALID makes fcs correct */
 383                         mark_t mark = hdr.mark;
 384                         hdr.mark = MARK_PAGE_VALID;
 385                         rotating_init(&cks);
 386                         rotating_update(&hdr, sizeof(BattFsPageHeader) - sizeof(rotating_t), &cks);
 387                         if (cks != hdr.fcs)
 388                                 /* Page is not a valid marked page, insert at the end of list */
 389                                 mark = ++disk->max_free;
 390
 391                         insertFreePage(disk, filelen_table, mark, page);
 392                 }
 393         }
 394
 395         #warning Test me!
 396         return true;
 397 }
 398
 399