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