Changeset 575:4ece9d9962f1

Timestamp:

06/03/08 08:53:55 (7 months ago)

Author:

Maxime Petazzoni <maxime.petazzoni@…>

Children:

576:59253836afad, 581:2d38c2b64075

Branch:

default

Message:

Merge _fs.[ch] and defrag.[ch] into fs.[ch] since the separation is not actually required.

Location:

nxos/base

Files:

• _fs.c (deleted)
• _fs.h (deleted)
• defrag.c (deleted)
• defrag.h (deleted)
• fs.c (modified) (21 diffs)
• fs.h (modified) (3 diffs)

nxos/base/fs.c

@@ -1 @@
-/* Copyright (C) 2008 the NxOS developers
+/* Copyright (c) 2008 the NxOS developers
  *
  * See AUTHORS for a full list of the developers.
@@ -15 +15 @@
 #include "base/util.h"
 #include "base/fs.h"
-#include "base/_fs.h"
 #include "base/drivers/_efc.h"
 
-#include "base/display.h"
-
-extern fs_file_t fdset[FS_MAX_OPENED_FILES];
+/** Magic marker. */
+#define FS_FILE_ORIGIN_MARKER 0x42
+
+/** File metadata size, in U32s. */
+#define FS_FILE_METADATA_SIZE 10
+
+/** File metadata size, in bytes. */
+#define FS_FILE_METADATA_BYTES (FS_FILE_METADATA_SIZE * sizeof(U32))
+
+#define FS_FILE_ORIGIN_MASK 0xFF000000
+#define FS_FILE_PERMS_MASK 0x00F00000
+#define FS_FILE_SIZE_MASK 0x000FFFFF
+
+#define FS_FILE_PERM_MASK_READWRITE (1 << 0)
+#define FS_FILE_PERM_MASK_EXECUTABLE (1 << 1)
+
+#define FS_FILENAME_OFFSET 2
+
+/** U32 <-> char conversion union for filenames. */
+union U32tochar {
+  char chars[FS_FILENAME_LENGTH];
+  U32 integers[FS_FILENAME_SIZE];
+};
+
+/** FD-set. */
+static fs_file_t fdset[FS_MAX_OPENED_FILES];
+
+/* Returns a file info structure given its file descriptor,
+ * or NULL if the fd is invalid.
+ */
+static fs_file_t *nx_fs_get_file(fs_fd_t fd) {
+  NX_ASSERT(fd < FS_MAX_OPENED_FILES);
+
+  if (!fdset[fd].used) {
+    return NULL;
+  }
+
+  return &(fdset[fd]);
+}
+
+/* Determines if the given page contains a file origin marker.
+ */
+inline static bool nx_fs_page_has_magic(U32 page) {
+  return ((FLASH_BASE_PTR[page*EFC_PAGE_WORDS] & FS_FILE_ORIGIN_MASK) >> 24)
+    == FS_FILE_ORIGIN_MARKER;
+}
+
+/* Returns the number of pages used by a file, given its size.
+ */
+static U32 nx_fs_get_file_page_count(size_t size) {
+  U32 pages;
+
+  /* Compute page occupation. */
+  size += FS_FILE_METADATA_BYTES;
+  pages = size / EFC_PAGE_BYTES;
+  if (size % EFC_PAGE_BYTES) {
+    pages++;
+  }
+
+  return pages;
+}
+
+inline static size_t nx_fs_get_file_size_from_metadata(volatile U32 *metadata) {
+  return *metadata & FS_FILE_SIZE_MASK;
+}
+
+static fs_perm_t nx_fs_get_file_perms_from_metadata(volatile U32 *metadata) {
+  U8 perms = (*metadata & FS_FILE_PERMS_MASK) >> 20;
+
+  if (perms & FS_FILE_PERM_MASK_READWRITE) {
+    return FS_PERM_READWRITE;
+  } else if (perms & FS_FILE_PERM_MASK_EXECUTABLE) {
+    return FS_PERM_EXECUTABLE;
+  }
+
+  /* Defaults to read-only. */
+  return FS_PERM_READONLY;
+}
+
+/* Find a file's origin on the file system by its name.
+ */
+static fs_err_t nx_fs_find_file_origin(char *name, U32 *origin) {
+  U32 i;
+
+  for (i=FS_PAGE_START; i<FS_PAGE_END; i++) {
+    if (nx_fs_page_has_magic(i)) {
+      volatile U32 *metadata = &(FLASH_BASE_PTR[i*EFC_PAGE_WORDS]);
+      union U32tochar nameconv;
+
+      memcpy(nameconv.integers,
+             (void *)(metadata + FS_FILENAME_OFFSET),
+             FS_FILENAME_LENGTH);
+
+      if (streq(nameconv.chars, name)) {
+        *origin = i;
+        return FS_ERR_NO_ERROR;
+      }
+
+      /* Otherwise jump over the file and continue searching. */
+      else {
+        i += nx_fs_get_file_page_count(
+          nx_fs_get_file_size_from_metadata(metadata)) - 1;
+      }
+    }
+  }
+
+  return FS_ERR_FILE_NOT_FOUND;
+}
+
+/* Finds the last file origin on the flash.
+ */
+static fs_err_t nx_fs_find_last_origin(U32 *origin) {
+  U32 candidate = 0, i;
+
+  for (i=FS_PAGE_START; i<FS_PAGE_END; i++) {
+    if (nx_fs_page_has_magic(i)) {
+      volatile U32 *metadata = &(FLASH_BASE_PTR[i*EFC_PAGE_WORDS]);
+
+      candidate = i;
+      i += nx_fs_get_file_page_count(
+        nx_fs_get_file_size_from_metadata(metadata)) - 1;
+    }
+  }
+
+  if (candidate) {
+    *origin = candidate;
+    return FS_ERR_NO_ERROR;
+  }
+
+  return FS_ERR_FILE_NOT_FOUND;
+}
+
+static fs_err_t nx_fs_find_next_origin(U32 start, U32 *origin) {
+  U32 i;
+
+  for (i=start; i<FS_PAGE_END; i++) {
+    if (nx_fs_page_has_magic(i)) {
+      *origin = i;
+      return FS_ERR_NO_ERROR;
+    }
+  }
+
+  return FS_ERR_FILE_NOT_FOUND;
+}
+
+/* Serialize a file's metadata using the provided values and returns
+ * the resulting U32s, ready to be stored on flash.
+ */
+static void nx_fs_create_metadata(fs_perm_t perms, char *name, size_t size,
+                                  U32 *metadata) {
+  union U32tochar nameconv;
+
+  memset(metadata, 0, FS_FILE_METADATA_BYTES);
+
+  memset(nameconv.chars, 0, 32);
+  memcpy(nameconv.chars, name, MIN(strlen(name), 31));
+
+  /* Magic marker. */
+  metadata[0] = (FS_FILE_ORIGIN_MARKER << 24);
+
+  /* File permissions. */
+  switch (perms) {
+    case FS_PERM_READWRITE:
+      metadata[0] += (FS_FILE_PERM_MASK_READWRITE << 20);
+      break;
+    case FS_PERM_EXECUTABLE:
+      metadata[0] += (FS_FILE_PERM_MASK_EXECUTABLE << 20);
+      break;
+    default:
+      break;
+  }
+
+  /* File size. */
+  metadata[0] += (size & FS_FILE_SIZE_MASK);
+
+  /* Insert here in metadata[1] what would be relevant (future). */
+
+  /* File name. */
+  memcpy(metadata + FS_FILENAME_OFFSET, nameconv.integers, FS_FILENAME_LENGTH);
+}
+
+/* Move a @a len long flash region starting at page @a source to @a dest.
+ * Since pages are moved one after another, regions may overlap if the
+ * destination is lower in the flash than the source, but not the other
+ * way around. Note that this is asserted anyway to avoid data loss.
+ * It is the responsibility of the caller to clean up the remaining
+ * source region of any data he doesn't want to leave there (file origin
+ * markers for example).
+ *
+ * @param source The source page number.
+ * @param dest The destination page number.
+ * @param len The region length.
+ */
+static fs_err_t nx_fs_move_region(U32 source, U32 dest, U32 len) {
+  U32 data;
+
+  NX_ASSERT(source < EFC_PAGES);
+  NX_ASSERT(dest < EFC_PAGES);
+  NX_ASSERT(len < EFC_PAGES);
+  NX_ASSERT(dest - source <= len);
+
+  while (len--) {
+    data = FLASH_BASE_PTR[source*EFC_PAGE_WORDS];
+    if (!nx__efc_write_page(&data, dest)) {
+      return FS_ERR_FLASH_ERROR;
+    }
+
+    /* TODO: erase the source page ? */
+
+    source++;
+    dest++;
+  }
+
+  return FS_ERR_NO_ERROR;
+}
+
+/* Relocate the given file to @a origin.
+ */
+static fs_err_t nx_fs_relocate_to_page(fs_file_t *file, U32 origin) {
+  U32 page_data[EFC_PAGE_WORDS], null_data[EFC_PAGE_WORDS] = {0};
+  U32 diff, i;
+  size_t size;
+
+  diff = origin - file->origin;
+
+  /* Move the file's data. */
+  size = nx_fs_get_file_page_count(file->size);
+
+  /* TODO: use nx_fs_move_region? */
+  for (i=file->origin; i<size; i++) {
+    nx__efc_read_page(i, page_data);
+    /* TODO: figure out if we want to erase the source page now or later. */
+    if (!nx__efc_write_page(page_data, i + diff)
+      || !nx__efc_write_page(null_data, i)) {
+      return FS_ERR_FLASH_ERROR;
+    }
+  }
+
+  file->origin = origin;
+  file->rbuf.page += diff;
+  file->wbuf.page += diff;
+
+  return FS_ERR_NO_ERROR;
+}
+
+static fs_err_t nx_fs_relocate(fs_file_t *file) {
+  U32 origin, start;
+  size_t size;
+
+  size = nx_fs_get_file_page_count(file->size);
+
+  /* First, look at the end of the flash for free space. */
+  if (nx_fs_find_last_origin(&origin) == FS_ERR_NO_ERROR) {
+    origin += nx_fs_get_file_page_count(
+                nx_fs_get_file_size_from_metadata(
+                  &(FLASH_BASE_PTR[origin*EFC_PAGE_WORDS])));
+
+    if (size < FS_PAGE_END - origin) {
+      return nx_fs_relocate_to_page(file, origin);
+    }
+  }
+
+  start = FS_PAGE_START;
+  while (nx_fs_find_next_origin(start, &origin) != FS_ERR_FILE_NOT_FOUND) {
+    if (size < origin - start || (origin == file->origin && file->origin - start > 0)) {
+      return nx_fs_relocate_to_page(file, origin);
+    }
+
+    start = origin + nx_fs_get_file_page_count(
+                nx_fs_get_file_size_from_metadata(
+                  &(FLASH_BASE_PTR[origin*EFC_PAGE_WORDS])));
+  }
+
+  return FS_ERR_NO_SPACE_LEFT_ON_DEVICE;
+}
 
 /* Initialize the file system, most importantly check for file system
@@ -34 +305 @@
   fs_file_t *file;
 
-  file = nx__fs_get_file(fd);
+  file = nx_fs_get_file(fd);
   NX_ASSERT(file != NULL);
 
   file->origin = origin;
-  file->size = nx__fs_get_file_size_from_metadata(metadata);
-  file->perms = nx__fs_get_file_perms_from_metadata(metadata);
+  file->size = nx_fs_get_file_size_from_metadata(metadata);
+  file->perms = nx_fs_get_file_perms_from_metadata(metadata);
 
   file->rbuf.page = file->rbuf.pos = 0;
@@ -54 +325 @@
   fs_err_t err;
 
-  err = nx__fs_find_file_origin(name, &origin);
+  err = nx_fs_find_file_origin(name, &origin);
   if (err != FS_ERR_NO_ERROR) {
     return err;
@@ -69 +340 @@
 
   /* Check that a file by that name does not already exists. */
-  err = nx__fs_find_file_origin(name, &origin);
+  err = nx_fs_find_file_origin(name, &origin);
   if (err != FS_ERR_FILE_NOT_FOUND) {
     return FS_ERR_FILE_ALREADY_EXISTS;
@@ -75 +346 @@
 
   /* Find an origin page. */
-  if (nx__fs_find_last_origin(&origin) == FS_ERR_NO_ERROR) {
-    origin += nx__fs_get_file_page_count(
-                nx__fs_get_file_size_from_metadata(
+  if (nx_fs_find_last_origin(&origin) == FS_ERR_NO_ERROR) {
+    origin += nx_fs_get_file_page_count(
+                nx_fs_get_file_size_from_metadata(
                   &(FLASH_BASE_PTR[origin*EFC_PAGE_WORDS])));
   } else {
@@ -90 +361 @@
 
   /* Bootstrap the metadata to the flash page. */
-  nx__fs_create_metadata(FS_PERM_READWRITE, name, 0, metadata);
+  nx_fs_create_metadata(FS_PERM_READWRITE, name, 0, metadata);
 
   /* Write metadata to flash. */
@@ -157 +428 @@
       /* Put writing position at the end of the file. */
       file->wbuf.page = file->origin
-        + nx__fs_get_file_page_count(file->size) - 1;
+        + nx_fs_get_file_page_count(file->size) - 1;
       nx__efc_read_page(file->wbuf.page, file->wbuf.data.raw);
       file->wbuf.pos = (FS_FILE_METADATA_BYTES + file->size) % EFC_PAGE_BYTES;
@@ -185 +456 @@
   fs_file_t *file;
 
-  file = nx__fs_get_file(fd);
+  file = nx_fs_get_file(fd);
   if (!file) {
     return -1;
@@ -197 +468 @@
   fs_file_t *file;
 
-  file = nx__fs_get_file(fd);
+  file = nx_fs_get_file(fd);
   if (!file) {
     return FS_ERR_INVALID_FD;
@@ -227 +498 @@
   U32 pages;
 
-  file = nx__fs_get_file(fd);
+  file = nx_fs_get_file(fd);
   if (!file) {
     return FS_ERR_INVALID_FD;
   }
 
-  pages = nx__fs_get_file_page_count(file->size) - 1;
+  pages = nx_fs_get_file_page_count(file->size) - 1;
 
   /* Check that the page we will be writing to is available,
@@ -240 +511 @@
   if (file->wbuf.pos == 0 &&
     file->wbuf.page > file->origin + pages &&
-    nx__fs_page_has_magic(file->wbuf.page)) {
+    nx_fs_page_has_magic(file->wbuf.page)) {
     /* If the page we want to use is not available relocate the file. */
-    err = nx__fs_relocate(file);
+    err = nx_fs_relocate(file);
     if (err != FS_ERR_NO_ERROR) {
       return err;
@@ -279 +550 @@
   fs_file_t *file;
 
-  file = nx__fs_get_file(fd);
+  file = nx_fs_get_file(fd);
   if (!file) {
     return FS_ERR_INVALID_FD;
@@ -304 +575 @@
   fs_err_t err;
 
-  file = nx__fs_get_file(fd);
+  file = nx_fs_get_file(fd);
   if (!file) {
     return FS_ERR_INVALID_FD;
@@ -316 +587 @@
   /* Update the file's metadata. */
   nx__efc_read_page(file->origin, firstpage);
-  nx__fs_create_metadata(file->perms, file->name, file->size, firstpage);
+  nx_fs_create_metadata(file->perms, file->name, file->size, firstpage);
   if (!nx__efc_write_page(firstpage, file->origin)) {
     return FS_ERR_FLASH_ERROR;
@@ -328 +599 @@
   fs_file_t *file;
 
-  file = nx__fs_get_file(fd);
+  file = nx_fs_get_file(fd);
   if (!file) {
     return FS_ERR_INVALID_FD;
@@ -339 +610 @@
   fs_file_t *file;
 
-  file = nx__fs_get_file(fd);
+  file = nx_fs_get_file(fd);
   if (!file) {
     return FS_ERR_INVALID_FD;
@@ -355 +626 @@
   U32 erase[EFC_PAGE_WORDS] = {0};
 
-  file = nx__fs_get_file(fd);
+  file = nx_fs_get_file(fd);
   if (!file) {
     return FS_ERR_INVALID_FD;
@@ -361 +632 @@
 
   /* Remove file marker and potential in-file marker-alike. */
-  end = file->origin + nx__fs_get_file_page_count(file->size);
+  end = file->origin + nx_fs_get_file_page_count(file->size);
   for (page = file->origin; page < end; page++) {
-    if (nx__fs_page_has_magic(page)) {
+    if (nx_fs_page_has_magic(page)) {
       /* Erase marker. */
       if (!nx__efc_write_page(erase, page)) {
@@ -378 +649 @@
  */
 fs_err_t nx_fs_seek(fs_fd_t fd, size_t position) {
-        fs_file_t *file;
-        U32 page;
+  fs_file_t *file;
+  U32 page;
   U32 pos;
 
-        file = nx__fs_get_file(fd);
-        if (!file) {
-                return FS_ERR_INVALID_FD;
-        }
-        
-        if (position > file->size) {
-                return FS_ERR_INCORRECT_SEEK;
-        }
-        
+  file = nx_fs_get_file(fd);
+  if (!file) {
+    return FS_ERR_INVALID_FD;
+  }
+
+  if (position > file->size) {
+    return FS_ERR_INCORRECT_SEEK;
+  }
+
   position += FS_FILE_METADATA_BYTES;
 
@@ -421 +692 @@
   }
 }
+
+/** Defrag functions. */
+
+fs_err_t nx_fs_defrag_simple(void) {
+  return FS_ERR_NO_ERROR;
+}
+
+fs_err_t nx_fs_defrag_for_file_by_name(char *name) {
+  U32 origin;
+  fs_err_t err;
+
+  err = nx_fs_find_file_origin(name, &origin);
+  if (err == FS_ERR_NO_ERROR) {
+    return nx_fs_defrag_for_file_by_origin(origin);
+  }
+
+  /* Fall back to simple defrag. */
+  return nx_fs_defrag_simple();
+}
+
+fs_err_t nx_fs_defrag_for_file_by_origin(U32 origin) {
+  nx_fs_move_region(origin, 1, 1); // TBR
+
+  return FS_ERR_NO_ERROR;
+}
+
+fs_err_t nx_fs_defrag_best_overall(void) {
+  return FS_ERR_NO_ERROR;
+}
+

nxos/base/fs.h

@@ -5 +5 @@
  */
 
-/* Copyright (C) 2008 the NxOS developers
+/* Copyright (c) 2008 the NxOS developers
  *
  * See AUTHORS for a full list of the developers.
@@ -24 +24 @@
 /** @defgroup fs Flash file system */
 /*@{*/
+
+/** File-system first page number. */
+#define FS_PAGE_START 128
+
+/** File-system last page number. */
+#define FS_PAGE_END 1024
 
 /** Maximum number of files that can be stored by the filesystem.
@@ -184 +190 @@
                           U32 *wasted);
 
+/** Perform a simple defragmentation of the flash filesystem.
+ *
+ * This type of defragmentation only tries to collate files towards
+ * the beginning of the flash medium, maximizing free space at the end of
+ * the flash.
+ *
+ * @return A @a fs_err_t describing the outcome of the operation.
+ */
+fs_err_t nx_fs_defrag_simple(void);
+
+/** Perform a simple, file oriented defragmentation of the flash.
+ *
+ * This defragmentation type is similar to the simple one, but
+ * with the objective of making subsequent writes to the given file
+ * (by its name) faster by putting it at the end of the flash medium.
+ *
+ * @return A @a fs_err_t describing the outcome of the operation.
+ */
+fs_err_t nx_fs_defrag_for_file_by_name(char *name);
+
+/** Same as @a nx_defrag_for_file_by_name but takes a file origin
+ * instead. This function is called by @a nx_defrag_for_file_by_name
+ * once it has found the requested file's origin.
+ *
+ * @return A @a fs_err_t describing the outcome of the operation.
+ */
+fs_err_t nx_fs_defrag_for_file_by_origin(U32 origin);
+
+/** Tries to optimize the placement of the files on the filesystem
+ * to make write operations faster for all files by putting as much
+ * space as possible between each file and thus avoid a costy file
+ * relocation.
+ *
+ * @return A @a fs_err_t describing the outcome of the operation.
+ */
+fs_err_t nx_fs_defrag_best_overall(void);
+
 /*@}*/
 /*@}*/