bertos/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  * \brief BattFS: a filesystem for embedded platforms (implementation).
  34  *
  35  * \version $Id:$
  36  *
  37  * \author Francesco Sacchi <batt@develer.com>
  38  *
  39  */
  40
  41 #include "battfs.h"
  42
  43 #include <cfg/debug.h>
  44 #include <cfg/macros.h> /* MIN, MAX */
  45 #include <cpu/byteorder.h> /* cpu_to_xx */
  46
  47
  48 #include <string.h> /* memset, memmove */
  49
  50
  51 /**
  52  * Convert from memory representation to disk structure.
  53  * \note filesystem is in little-endian format.
  54  */
  55 INLINE void battfs_to_disk(struct BattFsPageHeader *hdr, uint8_t *buf)
  56 {
  57         STATIC_ASSERT(BATTFS_HEADER_LEN == 10);
  58         buf[0] = hdr->inode;
  59
  60         buf[1] = hdr->fill;
  61         buf[2] = hdr->fill >> 8;
  62
  63         buf[3] = hdr->pgoff;
  64         buf[4] = hdr->pgoff >> 8;
  65
  66         /*
  67          * Sequence number is at least 1 bit longer than page address.
  68          * Needed to take care of wraparonds.
  69          */
  70         buf[5] = hdr->seq;
  71         buf[6] = hdr->seq >> 8;
  72
  73         /*
  74          * First bit used by seq.
  75          * Unused bits are set to 1.
  76          */
  77         buf[7] = (hdr->seq >> 16) ? 0xFF : 0xFE;
  78
  79         /*
  80          * This field must be the last one!
  81          * This is needed because if the page is only partially
  82          * written, we can use this to detect it.
  83          */
  84         buf[8] = hdr->fcs;
  85         buf[9] = hdr->fcs >> 8;
  86 }
  87
  88 /**
  89  * Convert from disk structure to memory representation.
  90  * \note filesystem is in little-endian format.
  91  */
  92 INLINE void disk_to_battfs(uint8_t *buf, struct BattFsPageHeader *hdr)
  93 {
  94         STATIC_ASSERT(BATTFS_HEADER_LEN == 10);
  95         hdr->inode = buf[0];
  96         hdr->fill = buf[2] << 8 | buf[1];
  97         hdr->pgoff = buf[4] << 8 | buf[3];
  98         hdr->seq = (seq_t)(buf[7] & 0x01) << 16 | buf[6] << 8 | buf[5];
  99         hdr->fcs = buf[9] << 8 | buf[8];
 100 }
 101
 102 /**
 103  * Compute the fcs of the header.
 104  */
 105 static fcs_t computeFcs(struct BattFsPageHeader *hdr)
 106 {
 107         uint8_t buf[BATTFS_HEADER_LEN];
 108         fcs_t cks;
 109
 110         battfs_to_disk(hdr, buf);
 111         rotating_init(&cks);
 112         /* fcs is at the end of whole header */
 113         rotating_update(buf, BATTFS_HEADER_LEN - sizeof(fcs_t), &cks);
 114         return cks;
 115 }
 116
 117
 118 /**
 119  * Read header of page \a page.
 120  * \return true on success, false otherwise.
 121  */
 122 static bool battfs_readHeader(struct BattFsSuper *disk, pgcnt_t page, struct BattFsPageHeader *hdr)
 123 {
 124         uint8_t buf[BATTFS_HEADER_LEN];
 125         /*
 126          * Read header from disk.
 127          * Header is actually a footer, and so
 128          * resides at page end.
 129          */
 130         if (disk->read(disk, page, disk->page_size - BATTFS_HEADER_LEN, buf, BATTFS_HEADER_LEN)
 131             != BATTFS_HEADER_LEN)
 132         {
 133                 TRACEMSG("Error: page[%d]\n", page);
 134                 return false;
 135         }
 136
 137         /* Fill header */
 138         disk_to_battfs(buf, hdr);
 139
 140         return true;
 141 }
 142
 143 /**
 144  * Write header of page \a page.
 145  * \return true on success, false otherwise.
 146  */
 147 static bool battfs_writeHeader(struct BattFsSuper *disk, pgcnt_t page, struct BattFsPageHeader *hdr)
 148 {
 149         uint8_t buf[BATTFS_HEADER_LEN];
 150
 151         /* Fill buffer */
 152         battfs_to_disk(hdr, buf);
 153
 154         /*
 155          * write header to disk.
 156          * Header is actually a footer, and so
 157          * resides at page end.
 158          */
 159         if (disk->write(disk, page, disk->page_size - BATTFS_HEADER_LEN, buf, BATTFS_HEADER_LEN)
 160             != BATTFS_HEADER_LEN)
 161         {
 162                 TRACEMSG("Error: page[%d]\n", page);
 163                 return false;
 164         }
 165         return true;
 166 }
 167
 168 /**
 169  * Count the number of pages from
 170  * inode 0 to \a inode in \a filelen_table.
 171  */
 172 static pgcnt_t countPages(pgoff_t *filelen_table, inode_t inode)
 173 {
 174         pgcnt_t cnt = 0;
 175
 176         for (inode_t i = 0; i < inode; i++)
 177                 cnt += filelen_table[i];
 178
 179         return cnt;
 180 }
 181
 182 /**
 183  * Move all pages in page allocation array from \a src to \a src + \a offset.
 184  * The number of pages moved is page_count - MAX(dst, src).
 185  */
 186 static void movePages(struct BattFsSuper *disk, pgcnt_t src, int offset)
 187 {
 188         pgcnt_t dst = src + offset;
 189         memmove(&disk->page_array[dst], &disk->page_array[src], (disk->page_count - MAX(dst, src)) * sizeof(pgcnt_t));
 190
 191         if (offset < 0)
 192         {
 193                 /* Fill empty space in array with sentinel */
 194                 for (pgcnt_t page = disk->page_count + offset; page < disk->page_count; page++)
 195                         disk->page_array[page] = PAGE_UNSET_SENTINEL;
 196         }
 197 }
 198
 199 #if 0
 200
 201 /**
 202  * Insert \a page at the bottom of page allocation array of \a disk.
 203  */
 204 static void insertFreePage(struct BattFsSuper *disk, pgcnt_t page)
 205 {
 206         pgcnt_t free_pos = disk->page_count - 1;
 207         ASSERT(disk->page_array[free_pos] == PAGE_UNSET_SENTINEL);
 208         ASSERT(page <= free_pos);
 209
 210         disk->page_array[free_pos] = page;
 211 }
 212
 213 /**
 214  * Mark \a page of \a disk as free.
 215  * \note free_next of \a disk is used as \a page free marker
 216  * and is increased by 1.
 217  */
 218 static bool battfs_markFree(struct BattFsSuper *disk, struct BattFsPageHeader *hdr, pgcnt_t page)
 219 {
 220         uint8_t buf[BATTFS_HEADER_LEN];
 221
 222         hdr->mark = disk->free_next;
 223         hdr->fcs_free = computeFcsFree(hdr);
 224         battfs_to_disk(hdr, buf);
 225
 226         if (!disk->write(disk, page, disk->page_size - BATTFS_HEADER_LEN, buf, BATTFS_HEADER_LEN))
 227         {
 228                 TRACEMSG("error marking page [%d]\n", page);
 229                 return false;
 230         }
 231         else
 232         {
 233                 disk->free_next++;
 234                 return true;
 235         }
 236 }
 237
 238 /**
 239  * Determine free_start and free_next blocks for \a disk
 240  * using \a minl, \a maxl, \a minh, \a maxh.
 241  *
 242  * Mark_t is a type that has at least 1 bit more than
 243  * pgaddr_t. So all free blocks can be numbered using
 244  * at most half numbers of a mark_t type.
 245  * The free blocks algorithm increments by 1 the disk->free_next
 246  * every time a page becomes free. So the free block sequence is
 247  * guaranteed to be countiguous.
 248  * Only wrap arounds may happen, but due to half size sequence limitation,
 249  * there are only 4 possible situations:
 250  *
 251  * \verbatim
 252  *    |------lower half------|-------upper half-------|
 253  *
 254  * 1) |------minl*****maxl---|------------------------|
 255  * 2) |------minl********maxl|minh******maxh----------|
 256  * 3) |----------------------|----minh*******maxh-----|
 257  * 4) |minl******maxl--------|------------minh****maxh|
 258  * \endverbatim
 259  *
 260  * Situations 1 and 3 are easy to detect, while 2 and 4 require more care.
 261  */
 262 static void findFreeStartNext(struct BattFsSuper *disk, mark_t minl, mark_t maxl, mark_t minh, mark_t maxh)
 263 {
 264         /* Determine free_start & free_next */
 265         if (maxl >= minl)
 266         {
 267                 /* Valid interval found in lower half */
 268                 if (maxh >= minh)
 269                 {
 270                         /* Valid interval also found in upper half */
 271                         if (maxl == minh - 1)
 272                         {
 273                                 /* Interval starts in lower half and ends in upper */
 274                                 disk->free_start = minl;
 275                                 disk->free_next = maxh;
 276                         }
 277                         else
 278                         {
 279                                 /* Interval starts in upper half and ends in lower */
 280                                 ASSERT(minl == 0);
 281                                 ASSERT(maxh == (MAX_PAGE_ADDR | MARK_HALF_SIZE));
 282
 283                                 disk->free_start = minh;
 284                                 disk->free_next = maxl;
 285                         }
 286                 }
 287                 else
 288                 {
 289                         /*
 290                          * Upper interval is invalid.
 291                          * Use lower values.
 292                          */
 293
 294                         disk->free_start = minl;
 295                         disk->free_next = maxl;
 296                 }
 297         }
 298         else if (maxh >= minh)
 299         {
 300                 /*
 301                  * Lower interval is invalid.
 302                  * Use upper values.
 303                  */
 304                 disk->free_start = minh;
 305                 disk->free_next = maxh;
 306         }
 307         else
 308         {
 309                 /*
 310                  * No valid interval found.
 311                  * Hopefully the disk is brand new (or full).
 312                  */
 313                 TRACEMSG("No valid marked free block found, new disk or disk full\n");
 314                 disk->free_start = 0;
 315                 disk->free_next = -1; //to be increased later
 316         }
 317
 318         /* free_next should contain the first usable address */
 319         disk->free_next++;
 320
 321         TRACEMSG("Free markers:\n minl %u\n maxl %u\n minh %u\n maxh %u\n free_start %u\n free_next %u\n",
 322                 minl, maxl, minh, maxh, disk->free_start, disk->free_next);
 323 }
 324 #endif
 325
 326 /**
 327  * Count number of pages per file on \a disk.
 328  * This information is registered in \a filelen_table.
 329  * Array index represent file inode, while value contained
 330  * is the number of pages used by that file.
 331  *
 332  * \return true if ok, false on disk read errors.
 333  * \note The whole disk is scanned once.
 334  */
 335 static bool countDiskFilePages(struct BattFsSuper *disk, pgoff_t *filelen_table)
 336 {
 337         BattFsPageHeader hdr;
 338         disk->free_page_start = 0;
 339
 340         /* Count the number of disk page per file */
 341         for (pgcnt_t page = 0; page < disk->page_count; page++)
 342         {
 343                 if (!battfs_readHeader(disk, page, &hdr))
 344                         return false;
 345
 346                 /* Increase free space */
 347                 disk->free_bytes += disk->page_size - BATTFS_HEADER_LEN;
 348
 349                 /* Check header FCS */
 350                 if (hdr.fcs == computeFcs(&hdr))
 351                 {
 352                         ASSERT(hdr.fill <= disk->page_size - BATTFS_HEADER_LEN);
 353
 354                         /* Page is valid and is owned by a file */
 355                         filelen_table[hdr.inode]++;
 356
 357                         /* Keep trace of free space */
 358                         disk->free_bytes -= hdr.fill;
 359                         disk->free_page_start++;
 360                 }
 361         }
 362
 363         return true;
 364 }
 365
 366 /**
 367  * Fill page allocation array of \a disk
 368  * using file lenghts in \a filelen_table.
 369  *
 370  * The page allocation array is an array containings all file infos.
 371  * Is ordered by file, and within each file is ordered by page offset
 372  * inside file.
 373  * e.g. : at page array[0] you will find page address of the first page
 374  * of the first file (if present).
 375  * Free blocks are allocated after the last file, starting from invalid ones
 376  * and continuing with the marked free ones.
 377  *
 378  * \return true if ok, false on disk read errors.
 379  * \note The whole disk is scanned once.
 380  */
 381 static bool fillPageArray(struct BattFsSuper *disk, pgoff_t *filelen_table)
 382 {
 383         BattFsPageHeader hdr;
 384         pgcnt_t curr_free_page = disk->free_page_start;
 385         /* Fill page allocation array */
 386         for (pgcnt_t page = 0; page < disk->page_count; page++)
 387         {
 388                 if (!battfs_readHeader(disk, page, &hdr))
 389                         return false;
 390
 391                 /* Check header FCS */
 392                 if (hdr.fcs == computeFcs(&hdr))
 393                 {
 394                         /* Compute array position */
 395                         pgcnt_t array_pos_start = countPages(filelen_table, hdr.inode);
 396                         pgcnt_t array_pos = array_pos_start + hdr.pgoff;
 397
 398                         /* Find the first free position */
 399                         while (disk->page_array[array_pos] != PAGE_UNSET_SENTINEL)
 400                         {
 401                                 ASSERT(array_pos < array_pos_start + filelen_table[hdr.inode + 1]);
 402                                 array_pos++;
 403                         }
 404
 405                         disk->page_array[array_pos] = page;
 406                 }
 407                 else
 408                 {
 409                         /* Invalid page, keep as free */
 410                         ASSERT(disk->page_array[curr_free_page] == PAGE_UNSET_SENTINEL);
 411                         LOG_INFO("Page %d invalid, keeping as free\n", page);
 412                         disk->page_array[curr_free_page++] = page;
 413                 }
 414         }
 415         return true;
 416 }
 417
 418 /**
 419  * Find the latest version of a page, starting from the
 420  * page supplied by \a page_array.
 421  * The pages are read from the disk until a different
 422  * inode or page offset is found.
 423  * The lastest version of the page is moved in the first
 424  * position of \a page_array.
 425  * \return the number of old versions of the page or PAGE_ERROR
 426  *         on disk read errors.
 427  */
 428 static pgcnt_t findLastVersion(pgcnt_t *page_array)
 429 {
 430         pgcnt_t *array_start = page_array;
 431         BattFsPageHeader hdr;
 432         if (!battfs_readHeader(disk, *page_array++, &hdr))
 433                 return PAGE_ERROR;
 434
 435         /* Free space: early bailout */
 436         if (hdr.fcs != computeFcs(&hdr))
 437                 return 0;
 438
 439         /*
 440          * If the first page is valid,
 441          * inode and pg_off in the array are taken
 442          * as the current page markers.
 443          */
 444         inode_t curr_inode = hdr.inode;
 445         pgoff_t curr_pgoff = hdr.pgoff;
 446
 447         /* Temps used to find the sequence number range */
 448         seq_t minl = HALF_SEQ - 1;
 449         seq_t maxl = 0;
 450         seq_t minh = FULL_SEQ;
 451         seq_t maxh = HALF_SEQ;
 452         pgcnt_t lpos = 0, hpos = 0, dup_cnt = 0;
 453
 454         /*
 455          * Find min and max values for the two
 456          * half of seq_num range.
 457          * With this we can find seqnum wraparounds.
 458          * seq_t is a type that has at least 1 bit more than
 459          * pgaddr_t. So all version of a page blocks can be numbered using
 460          * at most half numbers of a seq_t type.
 461          * The sequence number algorithm increments by 1 the previous seq_num
 462          * every time a page is rewritten. So the sequence is
 463          * guaranteed to be countiguous.
 464          * Only wrap arounds may happen, but due to half size sequence limitation,
 465          * there are only 4 possible situations:
 466          *
 467          * \verbatim
 468          *    |------lower half------|-------upper half-------|
 469          *
 470          * 1) |------minl*****maxl---|------------------------|
 471          * 2) |------minl********maxl|minh******maxh----------|
 472          * 3) |----------------------|----minh*******maxh-----|
 473          * 4) |minl******maxl--------|------------minh****maxh|
 474          * \endverbatim
 475          *
 476          * Situations 1 and 3 are easy to detect, while 2 and 4 require more care.
 477          */
 478         do
 479         {
 480                 if (hdr.seq < SEQ_HALF_SIZE)
 481                 {
 482                         minl = MIN(minl, hdr.seq);
 483                         if (hdr.seq > maxl)
 484                         {
 485                                 maxl = hdr.seq;
 486                                 lpos = dup_cnt;
 487                         }
 488                 }
 489                 else
 490                 {
 491                         minh = MIN(minh, hdr.seq);
 492                         if (hdr.seq > maxh)
 493                         {
 494                                 maxh = hdr.seq;
 495                                 hpos = dup_cnt;
 496                         }
 497                 }
 498
 499                 if (!battfs_readHeader(disk, *page_array++, &hdr))
 500                         return PAGE_ERROR;
 501                 dup_cnt++;
 502         }
 503         while (curr_inode == hdr.inode && curr_pgoff == hdr.pgoff && hdr.fcs == computeFcs(&hdr))
 504
 505
 506         /* Return early if there is only one version of the current page */
 507         if (dup_cnt == 1)
 508                 return 0;
 509
 510         /* Find the position in the array of the last version of the page */
 511         pgcnt_t last_ver = hpos;
 512         if (maxl >= minl)
 513         {
 514                 /* Valid interval found in lower half */
 515                 if (maxh >= minh)
 516                 {
 517                         /* Valid interval also found in upper half */
 518                         if (maxl != minh - 1)
 519                         {
 520                                 /* Interval starts in upper half and ends in lower */
 521                                 ASSERT(minl == 0);
 522                                 ASSERT(maxh == FULL_SEQ);
 523
 524                                 last_ver = lpos;
 525                         }
 526                 }
 527                 else
 528                         /*
 529                          * Upper interval is invalid.
 530                          * Use lower values.
 531                          */
 532                         last_ver = lpos;
 533         }
 534
 535         /* Put last page version at array start position */
 536         SWAP(array_start[0], array_start[last_ver]);
 537
 538         return dup_cnt - 1;
 539 }
 540
 541 /**
 542  * Collect old pages, removing empty spaces from \a pg_array, for a maximum len of \a pg_len.
 543  * Once the collect task is completed, copy \a old_cnt pages from \a old_pages at the
 544  * end of free space in pg_array.
 545  */
 546 void collectOldPages(pgcnt_t *pg_array, pgcnt_t pg_len, pgcnt_t *old_pages, pgcnt_t old_cnt)
 547 {
 548         bool copy = false;
 549         pgcnt_t gap = 0;
 550
 551         for (pgcnt_t curr_page = 0; curr_page < pg_len; pg_len++)
 552         {
 553                 if (!copy)
 554                 {
 555                         if (pg_array[curr_page] == PAGE_UNSET_SENTINEL)
 556                                 gap++;
 557                         else
 558                         {
 559                                 pg_array[curr_page - gap] = pg_array[curr_page];
 560                                 copy = true;
 561                         }
 562                 }
 563                 else
 564                 {
 565                         if (pg_array[curr_page] != PAGE_UNSET_SENTINEL)
 566                                 pg_array[curr_page - gap] = pg_array[curr_page];
 567                         else
 568                         {
 569                                 gap++;
 570                                 copy = false;
 571                         }
 572                 }
 573         }
 574         ASSERT(gap == old_cnt);
 575         pg_array += pg_len - old_cnt;
 576
 577         memcpy(pg_array, old_pages, old_cnt * sizeof(pgcnt_t));
 578 }
 579
 580 /**
 581  * This function scan the page array of \a disk looking for
 582  * old versions of the same page.
 583  *
 584  * Only the last version is kept as valid, the old ones are inserted
 585  * in the free blocks heap.
 586  * \return true if ok, false on disk read errors.
 587  * \note The whole disk is scanned once.
 588  */
 589 static bool dropOldPages(struct BattFsSuper *disk)
 590 {
 591         #define OLD_PAGE_BUFLEN 64
 592         pgcnt_t old_pages[OLD_PAGE_BUFLEN];
 593         pgcnt_t old_cnt = 0;
 594
 595         pgcnt_t *curr_page = disk->page_array;
 596         pgcnt_t *collect_start = disk->page_array;
 597         pgcnt_t collect_len = disk->page_count;
 598         pgcnt_t dup_pages;
 599
 600         do
 601         {
 602                 dup_pages = findLastVersion(curr_page);
 603                 if (dup_pages == PAGE_ERROR)
 604                         return false;
 605                 /* The first page is the last version */
 606                 curr_page++;
 607                 while (dup_pages--)
 608                 {
 609                         if (old_cnt >= OLD_PAGE_BUFLEN)
 610                         {
 611                                 collectOldPages(collect_start, collect_len, old_pages, old_cnt);
 612                                 collect_len -= old_cnt;
 613                                 disk->free_bytes += old_cnt * (disk->page_size - BATTFS_HEADER_LEN);
 614                                 disk->free_page_start -= old_cnt;
 615                                 curr_page -= old_cnt;
 616                                 collect_start = curr_page;
 617                                 old_cnt = 0;
 618                         }
 619
 620                         old_pages[old_cnt++] = *curr_page;
 621                         *curr_page++ = PAGE_UNSET_SENTINEL;
 622                 }
 623         }
 624         while (curr_page < disk->page_array + disk->free_page_start);
 625
 626         collectOldPages(collect_start, collect_len, old_pages, old_cnt);
 627         disk->free_bytes += old_cnt * (disk->page_size - BATTFS_HEADER_LEN);
 628         disk->free_page_start -= old_cnt;
 629
 630         return true;
 631 }
 632
 633
 634 /**
 635  * Initialize and mount disk described by
 636  * \a disk.
 637  * \return false on errors, true otherwise.
 638  */
 639 bool battfs_init(struct BattFsSuper *disk)
 640 {
 641         pgoff_t filelen_table[BATTFS_MAX_FILES];
 642
 643         /* Sanity check */
 644         ASSERT(disk->open);
 645
 646         /* Init disk device */
 647         if (!disk->open(disk))
 648         {
 649                 TRACEMSG("open error\n");
 650                 return false;
 651         }
 652
 653         /* Disk open must set all of these */
 654         ASSERT(disk->read);
 655         ASSERT(disk->write);
 656         ASSERT(disk->erase);
 657         ASSERT(disk->close);
 658         ASSERT(disk->page_size);
 659         ASSERT(disk->page_count);
 660         ASSERT(disk->page_count < PAGE_UNSET_SENTINEL - 1);
 661         ASSERT(disk->page_array);
 662
 663         memset(filelen_table, 0, BATTFS_MAX_FILES * sizeof(pgoff_t));
 664
 665         disk->free_bytes = 0;
 666         disk->disk_size = (disk_size_t)(disk->page_size - BATTFS_HEADER_LEN) * disk->page_count;
 667
 668         /* Count pages per file */
 669         if (!countDiskFilePages(disk, filelen_table))
 670         {
 671                 TRACEMSG("error counting file pages\n");
 672                 return false;
 673         }
 674
 675         /* Once here, we have filelen_table filled with file lengths */
 676
 677         /* Fill page array with sentinel */
 678         for (pgcnt_t page = 0; page < disk->page_count; page++)
 679                 disk->page_array[page] = PAGE_UNSET_SENTINEL;
 680
 681         /* Fill page allocation array using filelen_table */
 682         if (!fillPageArray(disk, filelen_table))
 683         {
 684                 TRACEMSG("error filling page array\n");
 685                 return false;
 686         }
 687
 688         if (!dropOldPages(disk))
 689         {
 690                 LOG_ERR("error dropping old pages\n");
 691                 return false;
 692         }
 693
 694         /* Init list for opened files. */
 695         LIST_INIT(&disk->file_opened_list);
 696         return true;
 697 }
 698
 699 /**
 700  * Flush file \a fd.
 701  * \return 0 if ok, EOF on errors.
 702  */
 703 static int battfs_flush(struct KFile *fd)
 704 {
 705         (void)fd;
 706         #warning TODO
 707         return 0;
 708 }
 709
 710 /**
 711  * Close file \a fd.
 712  * \return 0 if ok, EOF on errors.
 713  */
 714 static int battfs_fileclose(struct KFile *fd)
 715 {
 716         BattFS *fdb = BATTFSKFILE(fd);
 717
 718         battfs_flush(fd);
 719         REMOVE(&fdb->link);
 720         return 0;
 721 }
 722
 723 /**
 724  * Read from file \a fd \a size bytes in \a buf.
 725  * \return The number of bytes read.
 726  */
 727 static size_t battfs_read(struct KFile *fd, void *_buf, size_t size)
 728 {
 729         BattFS *fdb = BATTFSKFILE(fd);
 730         uint8_t *buf = (uint8_t *)_buf;
 731
 732         size_t total_read = 0;
 733         pgoff_t pg_offset;
 734         pgaddr_t addr_offset;
 735         pgaddr_t read_len;
 736
 737         size = MIN((kfile_off_t)size, fd->size - fd->seek_pos);
 738
 739         while (size)
 740         {
 741                 pg_offset = fd->seek_pos / (fdb->disk->page_size - BATTFS_HEADER_LEN);
 742                 addr_offset = fd->seek_pos % (fdb->disk->page_size - BATTFS_HEADER_LEN);
 743                 read_len = MIN(size, (size_t)(fdb->disk->page_size - BATTFS_HEADER_LEN - addr_offset));
 744
 745                 /* Read from disk */
 746                 if (fdb->disk->read(fdb->disk, fdb->start[pg_offset], addr_offset, buf, read_len) != read_len)
 747                 {
 748                         #warning TODO set error?
 749                 }
 750
 751                 size -= read_len;
 752                 fd->seek_pos += read_len;
 753                 total_read += read_len;
 754                 buf += read_len;
 755         }
 756         return total_read;
 757 }
 758
 759
 760 /**
 761  * Search file \a inode in \a disk using a binary search.
 762  * \return pointer to file start in disk->page_array
 763  * if file exists, NULL otherwise.
 764  */
 765 static pgcnt_t *findFile(BattFsSuper *disk, inode_t inode)
 766 {
 767         BattFsPageHeader hdr;
 768         pgcnt_t first = 0, page, last = disk->page_count -1;
 769         fcs_t fcs;
 770
 771         while (first <= last)
 772         {
 773                 page = (first + last) / 2;
 774
 775                 if (!battfs_readHeader(disk, disk->page_array[page], &hdr))
 776                         return NULL;
 777
 778                 fcs = computeFcs(&hdr);
 779                 if (hdr.fcs == fcs && hdr.inode == inode)
 780                         return (&disk->page_array[page]) - hdr.pgoff;
 781                 else if (hdr.fcs == fcs && hdr.inode < inode)
 782                         first = page + 1;
 783                 else
 784                         last = page - 1;
 785         }
 786
 787         return NULL;
 788 }
 789
 790 /**
 791  * \return true if file \a inode exists on \a disk, false otherwise.
 792  */
 793 bool battfs_fileExists(BattFsSuper *disk, inode_t inode)
 794 {
 795         return findFile(disk, inode) != NULL;
 796 }
 797
 798 /**
 799  * Count size of file \a inode on \a disk, starting at pointer \a start
 800  * in disk->page_array. Size is written in \a size.
 801  * \return true if all s ok, false on disk read errors.
 802  */
 803 static bool countFileSize(BattFsSuper *disk, pgcnt_t *start, inode_t inode, file_size_t *size)
 804 {
 805         *size = 0;
 806         BattFsPageHeader hdr;
 807
 808         for (;;)
 809         {
 810                 if (!battfs_readHeader(disk, *start++, &hdr))
 811                         return false;
 812                 if (hdr.fcs == computeFcs(&hdr) && hdr.inode == inode)
 813                         *size += hdr.fill;
 814                 else
 815                         return true;
 816         }
 817 }
 818
 819 /**
 820  * Open file \a inode from \a disk in \a mode.
 821  * File context is stored in \a fd.
 822  * \return true if ok, false otherwise.
 823  */
 824 bool battfs_fileopen(BattFsSuper *disk, BattFS *fd, inode_t inode, filemode_t mode)
 825 {
 826         Node *n;
 827
 828         memset(fd, 0, sizeof(*fd));
 829
 830         /* Search file start point in disk page array */
 831         fd->start = findFile(disk, inode);
 832         if (fd->start == NULL)
 833         {
 834                 if (!(mode & BATTFS_CREATE))
 835                         return false;
 836
 837                 /* File does not exist, create it */
 838                 BattFsPageHeader hdr;
 839                 hdr.inode = inode;
 840                 hdr.seq = 0;
 841                 hdr.fill = 0;
 842                 hdr.pgoff = 0;
 843                 hdr.mark = MARK_PAGE_VALID;
 844                 hdr.fcs_free = FCS_FREE_VALID;
 845                 hdr.fcs = computeFcs(&hdr);
 846                 #warning TODO: get a free block and write on disk!
 847         }
 848
 849         /* Fill file size */
 850         if (!countFileSize(disk, fd->start, inode, &fd->fd.size))
 851                 return false;
 852
 853         /* Reset seek position */
 854         fd->fd.seek_pos = 0;
 855
 856         /* Insert file handle in list, ordered by inode, ascending. */
 857         FOREACH_NODE(n, &disk->file_opened_list)
 858         {
 859                 BattFS *file = containerof(n, BattFS, link);
 860                 if (file->inode >= inode)
 861                         break;
 862         }
 863         INSERT_BEFORE(&fd->link, n);
 864
 865         /* Fill in data */
 866         fd->inode = inode;
 867         fd->mode = mode;
 868         fd->disk = disk;
 869
 870         fd->fd.close = battfs_fileclose;
 871         fd->fd.flush = battfs_flush;
 872         fd->fd.read = battfs_read;
 873         fd->fd.reopen = kfile_genericReopen;
 874         fd->fd.seek = kfile_genericSeek;
 875
 876 #warning TODO battfs_write, battfs_error, battfs_clearerr
 877 #if 0
 878         fd->fd.write = battfs_write;
 879         fd->fd.error = battfs_error;
 880         fd->fd.clearerr = battfs_clearerr;
 881 #endif
 882
 883         DB(fd->fd._type = KFT_BATTFS);
 884
 885         return true;
 886 }
 887
 888 /**
 889  * Close \a disk.
 890  */
 891 bool battfs_close(struct BattFsSuper *disk)
 892 {
 893         Node *n;
 894         int res = 0;
 895
 896         /* Close all open files */
 897         FOREACH_NODE(n, &disk->file_opened_list)
 898         {
 899                 BattFS *file = containerof(n, BattFS, link);
 900                 res += battfs_fileclose(&file->fd);
 901         }
 902
 903         /* Close disk */
 904         return disk->close(disk) && (res == 0);
 905 }
 906
 907
 908 bool battfs_writeTestBlock(struct BattFsSuper *disk, pgcnt_t page, inode_t inode, seq_t seq, fill_t fill, pgoff_t pgoff, mark_t mark)
 909 {
 910         BattFsPageHeader hdr;
 911
 912         hdr.inode = inode;
 913         hdr.seq = seq;
 914         hdr.fill = fill;
 915         hdr.pgoff = pgoff;
 916         hdr.mark = MARK_PAGE_VALID;
 917         hdr.fcs_free = FCS_FREE_VALID;
 918         hdr.fcs = computeFcs(&hdr);
 919         if (mark != MARK_PAGE_VALID)
 920         {
 921                 hdr.mark = mark;
 922                 hdr.fcs_free = computeFcsFree(&hdr);
 923         }
 924
 925         if (!battfs_writeHeader(disk, page, &hdr))
 926         {
 927                 TRACEMSG("error writing hdr\n");
 928                 return false;
 929         }
 930
 931         return true;
 932 }