Changeset 616:2a0cd6574d1c

Timestamp:

06/14/08 17:07:24 (7 months ago)

Author:

Maxime Petazzoni <maxime.petazzoni@…>

Branch:

default

Message:

Working on the defrag_for_file() method.

Location:

nxos

Files:

• base/drivers/_efc.c (modified) (1 diff)
• base/lib/fs/fs.c (modified) (17 diffs)
• base/lib/fs/fs.h (modified) (2 diffs)
• systems/tests/fs.c (modified) (2 diffs)
• systems/tests/fs.h (modified) (1 diff)
• systems/tests/tests.c (modified) (1 diff)

nxos/base/drivers/_efc.c

@@ -20 +20 @@
 
 #define EFC_WRITE ((EFC_WRITE_KEY << 24) + EFC_CMD_WP)
-#define EFC_THROTTLE_TIMER 1
+#define EFC_THROTTLE_TIMER 2
 
 void nx__efc_init(void) {

nxos/base/lib/fs/fs.c

@@ -210 +210 @@
 
   while (len--) {
-    memcpy((void *) data,
-           (void *) &(FLASH_BASE_PTR[source*EFC_PAGE_WORDS]),
-           EFC_PAGE_BYTES);
+    nx__efc_read_page(source, data);
+
     if (!nx__efc_write_page(data, dest)) {
       return FS_ERR_FLASH_ERROR;
@@ -232 +231 @@
 
   while (len--) {
-    memcpy((void *) data,
-           (void *) &(FLASH_BASE_PTR[(source + len)*EFC_PAGE_WORDS]),
-           EFC_PAGE_BYTES);
+    nx__efc_read_page(source + len, data);
+
     if (!nx__efc_write_page(data, dest + len)) {
       return FS_ERR_FLASH_ERROR;
@@ -306 +304 @@
   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])));
+        nx_fs_get_file_size_from_metadata(
+          &(FLASH_BASE_PTR[origin*EFC_PAGE_WORDS])));
 
     if (size < FS_PAGE_END - origin) {
@@ -321 +319 @@
 
     start = origin + nx_fs_get_file_page_count(
-                nx_fs_get_file_size_from_metadata(
-                  &(FLASH_BASE_PTR[origin*EFC_PAGE_WORDS])));
+        nx_fs_get_file_size_from_metadata(
+          &(FLASH_BASE_PTR[origin*EFC_PAGE_WORDS])));
   }
 
@@ -389 +387 @@
   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])));
+        nx_fs_get_file_size_from_metadata(
+          &(FLASH_BASE_PTR[origin*EFC_PAGE_WORDS])));
   } else {
-     origin = FS_PAGE_START;
+    origin = FS_PAGE_START;
   }
 
@@ -425 +423 @@
   /* First, make sure we have an avaliable slot for this file. */
   while (slot < FS_MAX_OPENED_FILES && fdset[slot].used) {
-   slot++;
+    slot++;
   }
 
@@ -551 +549 @@
    */
   if (file->wbuf.pos == 0 &&
-    file->wbuf.page > file->origin + pages &&
-    nx_fs_page_has_magic(file->wbuf.page)) {
+      file->wbuf.page > file->origin + pages &&
+      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);
@@ -579 +577 @@
   if (file->wbuf.page == file->origin + pages) {
     if (file->wbuf.pos > file->size + FS_FILE_METADATA_BYTES
-      - (pages * EFC_PAGE_BYTES)) {
+        - (pages * EFC_PAGE_BYTES)) {
       file->size++;
     }
@@ -748 +746 @@
 
 void nx_fs_get_occupation(U32 *files, U32 *used, U32 *free_pages,
-                          U32 *wasted) {
+    U32 *wasted) {
   U32 _files = 0, _used = 0, _free_pages = 0, _wasted = 0;
   U32 i;
@@ -840 +838 @@
  * is.
  */
-fs_err_t nx_fs_defrag_simple(void) {
-  U32 i = FS_PAGE_START;
+fs_err_t nx_fs_defrag_simple_zone(U32 zone_start, U32 zone_end) {
   U32 next_hole, next_file, first_next_file, hole_length = 0, end_of_block;
   U32 best_block_origin =0, best_block_size=0, block_size = 0;
+  U32 i;
   fs_err_t err = FS_ERR_NO_ERROR;
 
-  while (i < FS_PAGE_END) {
+  NX_ASSERT(zone_start >= FS_PAGE_START);
+  NX_ASSERT(zone_end <= FS_PAGE_END);
+  NX_ASSERT(zone_start <= zone_end);
+
+  i = zone_start;
+  nx_display_string("<<  ");
+  nx_display_uint(i);
+  nx_display_end_line();
+
+  while (i < zone_end) {
     /* Find the next hole, and its size. */
-
     err = nx_fs_find_next_hole(i, &next_hole);
     if (err != FS_ERR_NO_ERROR) {
@@ -880 +886 @@
 
       if (block_size != hole_length &&
-        nx_fs_find_next_origin(end_of_block, &next_file) != FS_ERR_NO_ERROR) {
+          nx_fs_find_next_origin(end_of_block, &next_file) != FS_ERR_NO_ERROR) {
         break;
       }
-    } while (next_file < FS_PAGE_END && block_size != hole_length);
+    } while (next_file < zone_end && block_size != hole_length);
 
     /* Move the block to fill the hole and move the search start
@@ -901 +907 @@
     /* Else, if a best match has been found, move it. */
     else if (best_block_origin != 0) {
+      nx_display_string("bmatch\n");
+      nx_display_uint(best_block_origin);
+      nx_display_string(">");
+      nx_display_uint(next_hole);
+      nx_display_string(" ");
+      nx_display_uint(best_block_size);
+      nx_display_end_line();
+
       err = nx_fs_move_region(best_block_origin, next_hole, best_block_size);
       if (err != FS_ERR_NO_ERROR) {
@@ -907 +921 @@
 
       i = next_hole + best_block_size;
+      nx_display_string("after ");
+      nx_display_uint(i);
+      nx_display_end_line();
+      return FS_ERR_NO_ERROR;
     }
 
@@ -915 +933 @@
       err = nx_fs_find_next_hole(first_next_file, &end_of_block);
       if (err != FS_ERR_NO_ERROR) {
-        end_of_block = FS_PAGE_END;
-      }
+        end_of_block = zone_end;
+      }
+
+      nx_display_string("pull\n");
 
       err = nx_fs_move_region(first_next_file, next_hole,
@@ -931 +951 @@
 }
 
+/* Simple defragmentation of the whole flash. */
+inline fs_err_t nx_fs_defrag_simple(void) {
+  return nx_fs_defrag_simple_zone(FS_PAGE_START, FS_PAGE_END);
+}
+
 fs_err_t nx_fs_defrag_for_file_by_name(char *name) {
   U32 origin;
@@ -940 +965 @@
   }
 
-  /* Fall back to simple defrag. */
-  return nx_fs_defrag_simple();
+  return FS_ERR_FILE_NOT_FOUND;
+}
+
+static fs_err_t nx_fs_swap_regions(U32 start1, U32 dest1, U32 len1,
+                                   U32 start2, U32 len2) {
+  U32 data[EFC_PAGE_WORDS] = {0};
+  fs_err_t err;
+  U32 i, j;
+
+  NX_ASSERT(len2 <= len1);
+
+  nx_display_string("swap\n");
+  nx_display_uint(start1);
+  nx_display_string("-");
+  nx_display_uint(dest1);
+  nx_display_string("-");
+  nx_display_uint(len1);
+  nx_display_end_line();
+
+  nx_display_uint(start2);
+  nx_display_string("-");
+  nx_display_uint(len2);
+  nx_display_end_line();
+
+  for (i=0, j=0; i<len1; i++, j++) {
+    if (j < len2) {
+      nx__efc_read_page(start2 + j, data);
+      nx__efc_erase_page(start2 + j, 0);
+    }
+
+    err = nx_fs_move_region(start1 + i, dest1 + i, 1);
+    if (err != FS_ERR_NO_ERROR) {
+      return err;
+    }
+
+    if (j < len2 && !nx__efc_write_page(data, start1 + j)) {
+      return FS_ERR_FLASH_ERROR;
+    }
+  }
+
+  return FS_ERR_NO_ERROR;
 }
 
 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;
+  U32 next_origin, next_hole, last_origin, last_npages, npages;
+  volatile U32 *metadata;
+  fs_err_t err;
+
+  /* First, trivial case: the file is already at the end of the flash.
+   * If it still has free space after him, job's done. Otherwise, launch
+   * a defrag simple.
+   */
+  err = nx_fs_find_last_origin(&last_origin);
+  if (err != FS_ERR_NO_ERROR) {
+    return err;
+  }
+
+  metadata = &(FLASH_BASE_PTR[origin*EFC_PAGE_WORDS]);
+  npages = nx_fs_get_file_page_count(
+    nx_fs_get_file_size_from_metadata(metadata));
+
+  metadata = &(FLASH_BASE_PTR[last_origin*EFC_PAGE_WORDS]);
+  last_npages = nx_fs_get_file_page_count(
+    nx_fs_get_file_size_from_metadata(metadata));
+
+  if (origin == last_origin) {
+    nx_display_string("case1\n");
+    return nx_fs_defrag_simple();
+  }
+
+  /* Second case: we can move our file to the end of the flash. If this
+   * is possible, move the file and call nx_fs_defrag_simple().
+   */
+  if (FS_PAGE_END - (last_origin + last_npages) > npages) {
+    nx_display_string("case2\n");
+
+    err = nx_fs_move_region(origin, last_origin + last_npages, npages);
+    if (err != FS_ERR_NO_ERROR) {
+      return err;
+    }
+
+    return nx_fs_defrag_simple();
+  }
+
+  /* Third case, trickier: if we can *swap* the file with the last one
+   * of the flash, do it and we're back into case 2).
+   */
+  do {
+    if (nx_fs_find_next_hole(origin, &next_hole) != FS_ERR_NO_ERROR) {
+      break;
+    }
+
+    if (nx_fs_find_next_origin(next_hole, &next_origin) !=
+      FS_ERR_NO_ERROR) {
+      break;
+    }
+  } while (next_origin != last_origin);
+
+  if (next_origin == last_origin && npages <= FS_PAGE_END - next_hole &&
+    last_npages <= npages) {
+    nx_display_string("case3\n");
+
+    /* Swap our file with the last one, if they fit. */
+    err = nx_fs_swap_regions(origin, next_hole, npages,
+                             last_origin, last_npages);
+    if (err != FS_ERR_NO_ERROR) {
+      return err;
+    }
+
+    return nx_fs_defrag_simple();
+  }
+
+  return FS_ERR_NO_SPACE_LEFT_ON_DEVICE;
 }
 
@@ -1015 +1145 @@
 
       hole_size = next_origin - (i + npages);
-
-      nx_display_uint(i);
-      nx_display_string(" ");
-      nx_display_uint(npages);
-      nx_display_string(" ");
-      nx_display_uint(hole_size);
-      nx_display_string(">");
-
       i += npages + mean_space_per_file;
-      nx_display_uint(i);
-      nx_display_end_line();
 
       /* First, trivial case: the hole size equals mean_space_per_file.

nxos/base/lib/fs/fs.h

@@ -210 +210 @@
 void nx_fs_dump(void);
 
+/** Perform a simple defragmentation of the flash filesystem on the
+ * given zone of the flash.
+ *
+ * @param zone_start Beginning of the zone to defragment.
+ * @param zone_end End of the zone.
+ * @return A @a fs_err_t describing the outcome of the operation.
+ */
+fs_err_t nx_fs_defrag_simple_zone(U32 zone_start, U32 zone_end);
+
 /** Perform a simple defragmentation of the flash filesystem.
  *
@@ -218 +227 @@
  * @return A @a fs_err_t describing the outcome of the operation.
  */
-fs_err_t nx_fs_defrag_simple(void);
+inline fs_err_t nx_fs_defrag_simple(void);
 
 /** Perform a simple, file oriented defragmentation of the flash.

nxos/systems/tests/fs.c

@@ -7 +7 @@
  */
 
+#include "base/types.h"
+#include "base/at91sam7s256.h"
 #include "base/display.h"
 #include "base/util.h"
@@ -148 +150 @@
 }
 
+void fs_test_defrag_for_file(void) {
+  U32 metadata[4*EFC_PAGE_WORDS] = {0};
+  union U32tochar nameconv;
+
+  setup();
+
+  metadata[0] = (0x42 << 24);
+  memcpy(nameconv.chars, (void *)"test42", 6);
+  memcpy(metadata+2, nameconv.integers, 32);
+
+  nx_display_string("Starting...\n");
+
+  spawn_file("test1", 3000);
+  //spawn_file("test2", 30000);
+  //spawn_file("test3", 3000);
+  //remove_file("test2");
+  nx__efc_write_page(metadata, 1020);
+
+  nx_fs_dump();
+  while (nx_avr_get_button() != BUTTON_OK);
+  nx_systick_wait_ms(500);
+
+  nx_display_clear();
+  nx_display_string("Defrag: ");
+  nx_display_uint(nx_fs_defrag_for_file_by_name("test1"));
+  nx_display_string(" done.\n");
+  while (nx_avr_get_button() != BUTTON_OK);
+  nx_systick_wait_ms(500);
+
+  nx_display_clear();
+  nx_fs_dump();
+  while (nx_avr_get_button() != BUTTON_OK);
+  nx_systick_wait_ms(500);
+
+  destroy();
+}
+
 void fs_test_defrag_best_overall(void) {
-  U32 data[256] = {0};
-  union U32tochar nameconv;
-
-  setup();
-
-  nx_display_string("Starting...\n");
-
-  data[0] = (0x42 << 24);
-  memcpy(nameconv.chars, (void *)"test42", 6);
-  memcpy(data+2, nameconv.integers, 32);
-
-  spawn_file("test1", 300);
-  spawn_file("test2", 300);
-  spawn_file("test3", 102360);
-  spawn_file("test4", 30);
-  spawn_file("test5", 102560);
+  setup();
+
+  nx_display_string("Starting...\n");
+
+  spawn_file("test1", 106968);
+  spawn_file("test2", 12750);
+  spawn_file("test3", 106968);
   remove_file("test2");
-  remove_file("test4");
 
   nx_fs_dump();

nxos/systems/tests/fs.h

@@ -14 +14 @@
 void fs_test_defrag_empty(void);
 void fs_test_defrag_simple(void);
+void fs_test_defrag_for_file(void);
 void fs_test_defrag_best_overall(void);
 

nxos/systems/tests/tests.c

@@ -869 +869 @@
   //fs_test_defrag_simple();
   //fs_test_defrag_empty();
-  fs_test_defrag_best_overall();
+  fs_test_defrag_for_file();
+  //fs_test_defrag_best_overall();
   goodbye();
 }