Switched to strongly ordered directories

Instead of storing files in an arbitrary order, we now store files in
ascending lexicographical order by filename.

Although a big change, this actually has little impact on how littlefs
works internally. We need to support file insertion, and compare file
names to find our position. But since we already need to scan the entire
directory block, this adds relatively little overhead.

What this does allow, is the potential to add B-tree support in the
future in a backwards compatible manner.

How could you add B-trees to littlefs?
1. Add an optional "child" tag with a pointer that allows you to skip to
   a position in the metadata-pair list that composes the directory
2. When splitting a metadata-pair (sound familiar?), we either insert a
   second child tag in our parent, or we create a new root containing
   the child tags.
3. Each layer needs a bit stored in the tail-pointer to indicate if
   we're going to the next layer. This can be created trivially when we
   create a new root.
4. During lookup we keep two pointers containing the bounds of our
   search. We may need to iterate through multiple metadata-pairs in our
   linked-list, but this gives us a O(log n) lookup cost in a balanced
   tree.
5. During deletion we also delete any children pointers. Note that
   children pointers must come before the actual file entry.

This gives us a B-tree implementation that is compatible with the
current directory layout (assuming the files are ordered). This means
that B-trees could be supported by a host PC and ignored on a small
device. And during power-loss, we never end up with a broken filesystem,
just a less-than-optimal tree.

Note that we don't handle removes, so it's possible for a tree to become
unbalanced. But worst case that's the same as the current linked-list
implementation.

All we need to do now is keep directories ordered. If we decide to drop
B-tree support in the future or the B-tree implementation turns out
inherently flawed, we can just drop the ordered requirement without
breaking compatibility and recover the code cost.

6 files changed, 165 insertions, 165 deletions

diff --git a/lfs.c b/lfs.c
index 8759f83..9ba52f7 100644
--- a/lfs.c
+++ b/lfs.c
@@ -128,11 +128,11 @@ static int lfs_bd_cmp(lfs_t *lfs,
         }
 
         if (dat != data[i]) {
-            return false;
+            return (dat < data[i]) ? 1 : 2;
         }
     }
 
-    return true;
+    return 0;
 }
 
 static int lfs_bd_flush(lfs_t *lfs,
@@ -152,12 +152,8 @@ static int lfs_bd_flush(lfs_t *lfs,
             int res = lfs_bd_cmp(lfs,
                     NULL, rcache, diff,
                     pcache->block, pcache->off, pcache->buffer, diff);
-            if (res < 0) {
-                return res;
-            }
-
-            if (!res) {
-                return LFS_ERR_CORRUPT;
+            if (res) {
+                return (res < 0) ? res : LFS_ERR_CORRUPT;
             }
         }
 
@@ -688,7 +684,8 @@ static lfs_stag_t lfs_dir_fetchmatch(lfs_t *lfs,
                     LFS_ASSERT(temp.count > 0);
                     temp.count -= 1;
 
-                    if (lfs_tag_id(tag) == lfs_tag_id(tempfoundtag)) {
+                    if (tempfoundtag &&
+                            lfs_tag_id(tag) == lfs_tag_id(tempfoundtag)) {
                         tempfoundtag = 0;
                     } else if (tempfoundtag &&
                             lfs_tag_id(tag) < lfs_tag_id(tempfoundtag)) {
@@ -724,11 +721,10 @@ static lfs_stag_t lfs_dir_fetchmatch(lfs_t *lfs,
                             return res;
                         }
 
-                        if (res) {
-                            tempfoundtag = tag;
+                        if (res && (!tempfoundtag ||
+                                lfs_tag_id(res) <= lfs_tag_id(tempfoundtag))) {
+                            tempfoundtag = res;
                         }
-                    } else {
-                        tempfoundtag = tag;
                     }
                 }
             }
@@ -740,12 +736,12 @@ static lfs_stag_t lfs_dir_fetchmatch(lfs_t *lfs,
         // consider what we have good enough
         if (dir->off > 0) {
             // synthetic move
-            if (lfs->globals.hasmove &&
+            if (foundtag &&
+                    lfs->globals.hasmove &&
                     lfs_pair_cmp(dir->pair, lfs->globals.pair) == 0) {
                 if (lfs->globals.id == lfs_tag_id(foundtag)) {
                     foundtag = 0;
-                } else if (foundtag &&
-                        lfs->globals.id < lfs_tag_id(foundtag)) {
+                } else if (lfs->globals.id < lfs_tag_id(foundtag)) {
                     foundtag -= LFS_MKTAG(0, 1, 0);
                 }
             }
@@ -876,24 +872,6 @@ static int lfs_dir_getinfo(lfs_t *lfs, lfs_mdir_t *dir,
     return 0;
 }
 
-static lfs_stag_t lfs_dir_findmatch(lfs_t *lfs,
-        lfs_mdir_t *dir, const lfs_block_t pair[2], bool fs,
-        lfs_tag_t findmask, lfs_tag_t findtag,
-        int (*cb)(void *data, lfs_tag_t tag, const void *buffer), void *data) {
-    dir->split = true;
-    dir->tail[0] = pair[0];
-    dir->tail[1] = pair[1];
-    while ((dir->split || fs) && !lfs_pair_isnull(dir->tail)) {
-        lfs_stag_t tag = lfs_dir_fetchmatch(lfs, dir, dir->tail,
-                findmask, findtag, cb, data);
-        if (tag) {
-            return tag;
-        }
-    }
-
-    return LFS_ERR_NOENT;
-}
-
 struct lfs_dir_find_match {
     lfs_t *lfs;
     const void *name;
@@ -905,22 +883,39 @@ static int lfs_dir_find_match(void *data,
     struct lfs_dir_find_match *name = data;
     lfs_t *lfs = name->lfs;
     const struct lfs_diskoff *disk = buffer;
-    (void)tag;
 
-    return lfs_bd_cmp(lfs,
-            NULL, &lfs->rcache, name->size,
-            disk->block, disk->off, name->name, name->size);
+    lfs_size_t diff = lfs_min(name->size, lfs_tag_size(tag));
+    int res = lfs_bd_cmp(lfs,
+            NULL, &lfs->rcache, diff,
+            disk->block, disk->off, name->name, diff);
+    if (res < 0) {
+        return res;
+    }
+
+    // found match?
+    if (res == 0 && (name->size == lfs_tag_size(tag) ||
+            lfs_tag_type(tag) == LFS_TYPE_SUPERBLOCK)) {
+        return tag;
+    }
+
+    // a greater name found, exit early
+    if (res == 2 && lfs_tag_type(tag) != LFS_TYPE_SUPERBLOCK) {
+        return tag | 0x1fff;
+    }
+
+    // no match keep looking
+    return 0;
 }
 
-static lfs_stag_t lfs_dir_find(lfs_t *lfs,
-        lfs_mdir_t *dir, const char **path) {
+static int lfs_dir_find(lfs_t *lfs, lfs_mdir_t *dir,
+        const char **path, uint16_t *id) {
     // we reduce path to a single name if we can find it
     const char *name = *path;
-    *path = NULL;
 
     // default to root dir
     lfs_stag_t tag = LFS_MKTAG(LFS_TYPE_DIR, 0x1ff, 0);
-    lfs_block_t pair[2] = {lfs->root[0], lfs->root[1]};
+    dir->tail[0] = lfs->root[0];
+    dir->tail[1] = lfs->root[1];
 
     while (true) {
 nextname:
@@ -964,10 +959,8 @@ nextname:
             return tag;
         }
 
-        // update what we've found if path is only a name
-        if (strchr(name, '/') == NULL) {
-            *path = name;
-        }
+        // update what we've found so far
+        *path = name;
 
         // only continue if we hit a directory
         if (lfs_tag_type(tag) != LFS_TYPE_DIR) {
@@ -977,20 +970,42 @@ nextname:
         // grab the entry data
         if (lfs_tag_id(tag) != 0x1ff) {
             lfs_stag_t res = lfs_dir_get(lfs, dir, 0x7c3fe000,
-                    LFS_MKTAG(LFS_TYPE_STRUCT, lfs_tag_id(tag), 8), pair);
+                    LFS_MKTAG(LFS_TYPE_STRUCT, lfs_tag_id(tag), 8), dir->tail);
             if (res < 0) {
                 return res;
             }
-            lfs_pair_fromle32(pair);
+            lfs_pair_fromle32(dir->tail);
         }
 
         // find entry matching name
-        tag = lfs_dir_findmatch(lfs, dir, pair, false, 0x7c001fff,
-                LFS_MKTAG(LFS_TYPE_NAME, 0, namelen),
-                lfs_dir_find_match, &(struct lfs_dir_find_match){
-                    lfs, name, namelen});
-        if (tag < 0) {
-            return tag;
+        while (true) {
+            tag = lfs_dir_fetchmatch(lfs, dir, dir->tail,
+                    0x7c000000, LFS_MKTAG(LFS_TYPE_NAME, 0, namelen),
+                    lfs_dir_find_match, &(struct lfs_dir_find_match){
+                        lfs, name, namelen});
+            if (tag < 0) {
+                return tag;
+            }
+
+            if (id) {
+                if (strchr(name, '/') != NULL) {
+                    // if path is not only name we're not valid candidate
+                    // for creation
+                    *id = 0x1ff;
+                } else if (tag) {
+                    *id = lfs_tag_id(tag);
+                } else {
+                    *id = dir->count;
+                }
+            }
+
+            if (tag && !lfs_tag_isdelete(tag)) {
+                break;
+            }
+
+            if (lfs_tag_isdelete(tag) || !dir->split) {
+                return LFS_ERR_NOENT;
+            }
         }
 
         // to next name
@@ -1560,10 +1575,12 @@ static int lfs_dir_commit(lfs_t *lfs, lfs_mdir_t *dir,
 
     // calculate new directory size
     lfs_tag_t deletetag = 0xffffffff;
+    lfs_tag_t createtag = 0xffffffff;
     int attrcount = 0;
     for (const struct lfs_mattr *a = attrs; a; a = a->next) {
         if (lfs_tag_subtype(a->tag) == LFS_TYPE_NAME) {
             dir->count += 1;
+            createtag = a->tag;
         } else if (lfs_tag_subtype(a->tag) == LFS_TYPE_DELETE) {
             LFS_ASSERT(dir->count > 0);
             dir->count -= 1;
@@ -1685,6 +1702,11 @@ compact:
                 if (d->type == LFS_TYPE_DIR) {
                     ((lfs_dir_t*)d)->pos -= 1;
                 }
+            } else if (&d->m != dir && d->id >= lfs_tag_id(createtag)) {
+                d->id += 1;
+                if (d->type == LFS_TYPE_DIR) {
+                    ((lfs_dir_t*)d)->pos += 1;
+                }
             }
 
             while (d->id >= d->m.count && d->m.split) {
@@ -1711,9 +1733,10 @@ int lfs_mkdir(lfs_t *lfs, const char *path) {
     }
 
     lfs_mdir_t cwd;
-    lfs_stag_t res = lfs_dir_find(lfs, &cwd, &path);
-    if (!(res == LFS_ERR_NOENT && path)) {
-        return (res < 0) ? res : LFS_ERR_EXIST;
+    uint16_t id;
+    err = lfs_dir_find(lfs, &cwd, &path, &id);
+    if (!(err == LFS_ERR_NOENT && id != 0x1ff)) {
+        return (err < 0) ? err : LFS_ERR_EXIST;
     }
 
     // check that name fits
@@ -1739,7 +1762,6 @@ int lfs_mkdir(lfs_t *lfs, const char *path) {
     }
 
     // get next slot and commit
-    uint16_t id = cwd.count;
     cwd.tail[0] = dir.pair[0];
     cwd.tail[1] = dir.pair[1];
     lfs_pair_tole32(dir.pair);
@@ -1757,7 +1779,7 @@ int lfs_mkdir(lfs_t *lfs, const char *path) {
 }
 
 int lfs_dir_open(lfs_t *lfs, lfs_dir_t *dir, const char *path) {
-    lfs_stag_t tag = lfs_dir_find(lfs, &dir->m, &path);
+    lfs_stag_t tag = lfs_dir_find(lfs, &dir->m, &path, NULL);
     if (tag < 0) {
         return tag;
     }
@@ -2114,21 +2136,20 @@ int lfs_file_opencfg(lfs_t *lfs, lfs_file_t *file,
     }
 
     // setup simple file details
-    int err = 0;
+    int err;
     file->cfg = cfg;
     file->flags = flags;
     file->pos = 0;
     file->cache.buffer = NULL;
 
     // allocate entry for file if it doesn't exist
-    lfs_stag_t tag = lfs_dir_find(lfs, &file->m, &path);
-    if (tag < 0 && !(tag == LFS_ERR_NOENT && path)) {
+    lfs_stag_t tag = lfs_dir_find(lfs, &file->m, &path, &file->id);
+    if (tag < 0 && !(tag == LFS_ERR_NOENT && file->id != 0x1ff)) {
         err = tag;
         goto cleanup;
     }
 
     // get id, add to list of mdirs to catch update changes
-    file->id = lfs_tag_id(tag);
     file->type = LFS_TYPE_REG;
     file->next = (lfs_file_t*)lfs->mlist;
     lfs->mlist = (struct lfs_mlist*)file;
@@ -2147,7 +2168,6 @@ int lfs_file_opencfg(lfs_t *lfs, lfs_file_t *file,
         }
 
         // get next slot and create entry to remember name
-        file->id = file->m.count;
         err = lfs_dir_commit(lfs, &file->m,
                 LFS_MKATTR(LFS_TYPE_INLINESTRUCT, file->id, NULL, 0,
                 LFS_MKATTR(LFS_TYPE_REG, file->id, path, nlen,
@@ -2755,7 +2775,7 @@ lfs_soff_t lfs_file_size(lfs_t *lfs, lfs_file_t *file) {
 /// General fs operations ///
 int lfs_stat(lfs_t *lfs, const char *path, struct lfs_info *info) {
     lfs_mdir_t cwd;
-    lfs_stag_t tag = lfs_dir_find(lfs, &cwd, &path);
+    lfs_stag_t tag = lfs_dir_find(lfs, &cwd, &path, NULL);
     if (tag < 0) {
         return tag;
     }
@@ -2771,12 +2791,7 @@ int lfs_remove(lfs_t *lfs, const char *path) {
     }
 
     lfs_mdir_t cwd;
-    err = lfs_dir_fetch(lfs, &cwd, lfs->root);
-    if (err) {
-        return err;
-    }
-
-    lfs_stag_t tag = lfs_dir_find(lfs, &cwd, &path);
+    lfs_stag_t tag = lfs_dir_find(lfs, &cwd, &path, NULL);
     if (tag < 0) {
         return tag;
     }
@@ -2840,20 +2855,19 @@ int lfs_rename(lfs_t *lfs, const char *oldpath, const char *newpath) {
 
     // find old entry
     lfs_mdir_t oldcwd;
-    lfs_stag_t oldtag = lfs_dir_find(lfs, &oldcwd, &oldpath);
+    lfs_stag_t oldtag = lfs_dir_find(lfs, &oldcwd, &oldpath, NULL);
     if (oldtag < 0) {
         return oldtag;
     }
 
     // find new entry
     lfs_mdir_t newcwd;
-    lfs_stag_t prevtag = lfs_dir_find(lfs, &newcwd, &newpath);
-    if (prevtag < 0 && prevtag != LFS_ERR_NOENT) {
-        return prevtag;
+    uint16_t newid;
+    lfs_stag_t prevtag = lfs_dir_find(lfs, &newcwd, &newpath, &newid);
+    if (prevtag < 0 && !(prevtag == LFS_ERR_NOENT && newid != 0x1ff)) {
+        return err;
     }
 
-    uint16_t newid = lfs_tag_id(prevtag);
-
     lfs_mdir_t prevdir;
     if (prevtag == LFS_ERR_NOENT) {
         // check that name fits
@@ -2861,9 +2875,6 @@ int lfs_rename(lfs_t *lfs, const char *oldpath, const char *newpath) {
         if (nlen > lfs->name_max) {
             return LFS_ERR_NAMETOOLONG;
         }
-
-        // get next id
-        newid = newcwd.count;
     } else if (lfs_tag_type(prevtag) != lfs_tag_type(oldtag)) {
         return LFS_ERR_ISDIR;
     } else if (lfs_tag_type(prevtag) == LFS_TYPE_DIR) {
@@ -2934,12 +2945,12 @@ int lfs_rename(lfs_t *lfs, const char *oldpath, const char *newpath) {
 lfs_ssize_t lfs_getattr(lfs_t *lfs, const char *path,
         uint8_t type, void *buffer, lfs_size_t size) {
     lfs_mdir_t cwd;
-    lfs_stag_t res = lfs_dir_find(lfs, &cwd, &path);
-    if (res < 0) {
-        return res;
+    lfs_stag_t tag = lfs_dir_find(lfs, &cwd, &path, NULL);
+    if (tag < 0) {
+        return tag;
     }
 
-    uint16_t id = lfs_tag_id(res);
+    uint16_t id = lfs_tag_id(tag);
     if (id == 0x1ff) {
         // special case for root
         id = 0;
@@ -2949,28 +2960,28 @@ lfs_ssize_t lfs_getattr(lfs_t *lfs, const char *path,
         }
     }
 
-    res = lfs_dir_get(lfs, &cwd, 0x7fffe000,
+    tag = lfs_dir_get(lfs, &cwd, 0x7fffe000,
             LFS_MKTAG(0x100 | type, id, lfs_min(size, lfs->attr_max)),
             buffer);
-    if (res < 0) {
-        if (res == LFS_ERR_NOENT) {
+    if (tag < 0) {
+        if (tag == LFS_ERR_NOENT) {
             return LFS_ERR_NOATTR;
         }
-        return res;
+        return tag;
     }
 
-    return lfs_tag_size(res);
+    return lfs_tag_size(tag);
 }
 
 static int lfs_commitattr(lfs_t *lfs, const char *path,
         uint8_t type, const void *buffer, lfs_size_t size) {
     lfs_mdir_t cwd;
-    lfs_stag_t res = lfs_dir_find(lfs, &cwd, &path);
-    if (res < 0) {
-        return res;
+    lfs_stag_t tag = lfs_dir_find(lfs, &cwd, &path, NULL);
+    if (tag < 0) {
+        return tag;
     }
 
-    uint16_t id = lfs_tag_id(res);
+    uint16_t id = lfs_tag_id(tag);
     if (id == 0x1ff) {
         // special case for root
         id = 0;
@@ -3167,28 +3178,28 @@ int lfs_mount(lfs_t *lfs, const struct lfs_config *cfg) {
     lfs_mdir_t dir = {.tail = {0, 1}};
     while (!lfs_pair_isnull(dir.tail)) {
         // fetch next block in tail list
-        lfs_stag_t res = lfs_dir_fetchmatch(lfs, &dir, dir.tail, 0x7fc00000,
+        lfs_stag_t tag = lfs_dir_fetchmatch(lfs, &dir, dir.tail, 0x7fc00000,
                 LFS_MKTAG(LFS_TYPE_SUPERBLOCK, 0, 8),
                 lfs_dir_find_match, &(struct lfs_dir_find_match){
                     lfs, "littlefs", 8});
-        if (res < 0) {
-            err = res;
+        if (tag < 0) {
+            err = tag;
             goto cleanup;
         }
 
         // has superblock?
-        if (res) {
+        if (tag && !lfs_tag_isdelete(tag)) {
             // update root
             lfs->root[0] = dir.pair[0];
             lfs->root[1] = dir.pair[1];
 
             // grab superblock
             lfs_superblock_t superblock;
-            res = lfs_dir_get(lfs, &dir, 0x7f800000,
+            tag = lfs_dir_get(lfs, &dir, 0x7f800000,
                     LFS_MKTAG(LFS_TYPE_SUPERBLOCK, 0, sizeof(superblock)),
                     &superblock);
-            if (res < 0) {
-                err = res;
+            if (tag < 0) {
+                err = tag;
                 goto cleanup;
             }
             lfs_superblock_fromle32(&superblock);
@@ -3277,10 +3288,6 @@ int lfs_unmount(lfs_t *lfs) {
 /// Filesystem filesystem operations ///
 int lfs_fs_traverse(lfs_t *lfs,
         int (*cb)(void *data, lfs_block_t block), void *data) {
-    if (lfs_pair_isnull(lfs->root)) {
-        return 0;
-    }
-
     // iterate over metadata pairs
     lfs_mdir_t dir = {.tail = {0, 1}};
     while (!lfs_pair_isnull(dir.tail)) {
@@ -3347,10 +3354,6 @@ int lfs_fs_traverse(lfs_t *lfs,
 
 static int lfs_fs_pred(lfs_t *lfs,
         const lfs_block_t pair[2], lfs_mdir_t *pdir) {
-    if (lfs_pair_isnull(lfs->root)) {
-        return LFS_ERR_NOENT;
-    }
-
     // iterate over all directory directory entries
     pdir->tail[0] = 0;
     pdir->tail[1] = 1;
@@ -3389,23 +3392,20 @@ static int lfs_fs_parent_match(void *data,
     }
 
     lfs_pair_fromle32(child);
-    return (lfs_pair_cmp(child, find->pair) == 0);
+    return (lfs_pair_cmp(child, find->pair) == 0) ? tag : 0;
 }
 
 static lfs_stag_t lfs_fs_parent(lfs_t *lfs, const lfs_block_t pair[2],
         lfs_mdir_t *parent) {
-    if (lfs_pair_isnull(lfs->root)) {
-        return LFS_ERR_NOENT;
-    }
-
-    // search for both orderings so we can reuse the find function
-    for (int i = 0; i < 2; i++) {
-        struct lfs_fs_parent_match match = {lfs, {pair[0], pair[1]}};
-        lfs_stag_t tag = lfs_dir_findmatch(lfs, parent,
-                (const lfs_block_t[2]){0, 1}, true, 0x7fc01fff,
-                LFS_MKTAG(LFS_TYPE_DIRSTRUCT, 0, 8),
-                lfs_fs_parent_match, &match);
-        if (tag != LFS_ERR_NOENT) {
+    // use fetchmatch with callback to find pairs
+    parent->tail[0] = 0;
+    parent->tail[1] = 1;
+    while (!lfs_pair_isnull(parent->tail)) {
+        lfs_stag_t tag = lfs_dir_fetchmatch(lfs, parent, parent->tail,
+                0x7fc01fff, LFS_MKTAG(LFS_TYPE_DIRSTRUCT, 0, 8),
+                lfs_fs_parent_match, &(struct lfs_fs_parent_match){
+                    lfs, {pair[0], pair[1]}});
+        if (tag) {
             return tag;
         }
     }
diff --git a/lfs.h b/lfs.h
index dae59ed..0dd1c2f 100644
--- a/lfs.h
+++ b/lfs.h
@@ -92,7 +92,7 @@ enum lfs_type {
     LFS_TYPE_DIR            = 0x003,
 
     // internally used types
-    LFS_TYPE_USER           = 0x100,
+    LFS_TYPE_USERATTR       = 0x100,
     LFS_TYPE_NAME           = 0x000,
     LFS_TYPE_DELETE         = 0x020,
     LFS_TYPE_STRUCT         = 0x040,
diff --git a/tests/test_dirs.sh b/tests/test_dirs.sh
index 53d76f7..4aac945 100755
--- a/tests/test_dirs.sh
+++ b/tests/test_dirs.sh
@@ -43,11 +43,11 @@ tests/test.py << TEST
     strcmp(info.name, "..") => 0;
     info.type => LFS_TYPE_DIR;
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
-    strcmp(info.name, "potato") => 0;
-    info.type => LFS_TYPE_DIR;
-    lfs_dir_read(&lfs, &dir[0], &info) => 1;
     strcmp(info.name, "burito") => 0;
     info.type => LFS_TYPE_REG;
+    lfs_dir_read(&lfs, &dir[0], &info) => 1;
+    strcmp(info.name, "potato") => 0;
+    info.type => LFS_TYPE_DIR;
     lfs_dir_read(&lfs, &dir[0], &info) => 0;
     lfs_dir_close(&lfs, &dir[0]) => 0;
     lfs_unmount(&lfs) => 0;
@@ -85,10 +85,10 @@ tests/test.py << TEST
     strcmp(info.name, "baked") => 0;
     info.type => LFS_TYPE_DIR;
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
-    strcmp(info.name, "sweet") => 0;
+    strcmp(info.name, "fried") => 0;
     info.type => LFS_TYPE_DIR;
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
-    strcmp(info.name, "fried") => 0;
+    strcmp(info.name, "sweet") => 0;
     info.type => LFS_TYPE_DIR;
     lfs_dir_read(&lfs, &dir[0], &info) => 0;
     lfs_dir_close(&lfs, &dir[0]) => 0;
@@ -100,7 +100,7 @@ tests/test.py << TEST
     lfs_mount(&lfs, &cfg) => 0;
     lfs_mkdir(&lfs, "cactus") => 0;
     for (int i = 0; i < $LARGESIZE; i++) {
-        sprintf((char*)buffer, "cactus/test%d", i);
+        sprintf((char*)buffer, "cactus/test%03d", i);
         lfs_mkdir(&lfs, (char*)buffer) => 0;
     }
     lfs_unmount(&lfs) => 0;
@@ -115,7 +115,7 @@ tests/test.py << TEST
     strcmp(info.name, "..") => 0;
     info.type => LFS_TYPE_DIR;
     for (int i = 0; i < $LARGESIZE; i++) {
-        sprintf((char*)buffer, "test%d", i);
+        sprintf((char*)buffer, "test%03d", i);
         lfs_dir_read(&lfs, &dir[0], &info) => 1;
         strcmp(info.name, (char*)buffer) => 0;
         info.type => LFS_TYPE_DIR;
@@ -208,10 +208,10 @@ tests/test.py << TEST
     strcmp(info.name, "baked") => 0;
     info.type => LFS_TYPE_DIR;
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
-    strcmp(info.name, "sweet") => 0;
+    strcmp(info.name, "fried") => 0;
     info.type => LFS_TYPE_DIR;
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
-    strcmp(info.name, "fried") => 0;
+    strcmp(info.name, "sweet") => 0;
     info.type => LFS_TYPE_DIR;
     lfs_dir_read(&lfs, &dir[0], &info) => 0;
     lfs_dir_close(&lfs, &dir[0]) => 0;
@@ -241,10 +241,10 @@ tests/test.py << TEST
     strcmp(info.name, "baked") => 0;
     info.type => LFS_TYPE_DIR;
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
-    strcmp(info.name, "sweet") => 0;
+    strcmp(info.name, "fried") => 0;
     info.type => LFS_TYPE_DIR;
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
-    strcmp(info.name, "fried") => 0;
+    strcmp(info.name, "sweet") => 0;
     info.type => LFS_TYPE_DIR;
     lfs_dir_read(&lfs, &dir[0], &info) => 0;
     lfs_dir_close(&lfs, &dir[0]) => 0;
@@ -273,10 +273,10 @@ tests/test.py << TEST
     strcmp(info.name, "baked") => 0;
     info.type => LFS_TYPE_DIR;
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
-    strcmp(info.name, "sweet") => 0;
+    strcmp(info.name, "fried") => 0;
     info.type => LFS_TYPE_DIR;
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
-    strcmp(info.name, "fried") => 0;
+    strcmp(info.name, "sweet") => 0;
     info.type => LFS_TYPE_DIR;
     lfs_dir_read(&lfs, &dir[0], &info) => 0;
     lfs_dir_close(&lfs, &dir[0]) => 0;
@@ -332,7 +332,7 @@ tests/test.py << TEST
     lfs_remove(&lfs, "cactus") => LFS_ERR_NOTEMPTY;
 
     for (int i = 0; i < $LARGESIZE; i++) {
-        sprintf((char*)buffer, "cactus/test%d", i);
+        sprintf((char*)buffer, "cactus/test%03d", i);
         lfs_remove(&lfs, (char*)buffer) => 0;
     }
 
@@ -361,7 +361,7 @@ tests/test.py << TEST
     lfs_mount(&lfs, &cfg) => 0;
     lfs_mkdir(&lfs, "prickly-pear") => 0;
     for (int i = 0; i < $LARGESIZE; i++) {
-        sprintf((char*)buffer, "prickly-pear/test%d", i);
+        sprintf((char*)buffer, "prickly-pear/test%03d", i);
         lfs_file_open(&lfs, &file[0], (char*)buffer,
                 LFS_O_WRONLY | LFS_O_CREAT) => 0;
         size = 6;
@@ -381,7 +381,7 @@ tests/test.py << TEST
     strcmp(info.name, "..") => 0;
     info.type => LFS_TYPE_DIR;
     for (int i = 0; i < $LARGESIZE; i++) {
-        sprintf((char*)buffer, "test%d", i);
+        sprintf((char*)buffer, "test%03d", i);
         lfs_dir_read(&lfs, &dir[0], &info) => 1;
         strcmp(info.name, (char*)buffer) => 0;
         info.type => LFS_TYPE_REG;
@@ -397,7 +397,7 @@ tests/test.py << TEST
     lfs_remove(&lfs, "prickly-pear") => LFS_ERR_NOTEMPTY;
 
     for (int i = 0; i < $LARGESIZE; i++) {
-        sprintf((char*)buffer, "prickly-pear/test%d", i);
+        sprintf((char*)buffer, "prickly-pear/test%03d", i);
         lfs_remove(&lfs, (char*)buffer) => 0;
     }
 
diff --git a/tests/test_files.sh b/tests/test_files.sh
index bbecea9..5251c61 100755
--- a/tests/test_files.sh
+++ b/tests/test_files.sh
@@ -29,7 +29,7 @@ tests/test.py << TEST
 TEST
 
 w_test() {
-tests/test.py << TEST
+tests/test.py ${4:-} << TEST
     size = $1;
     lfs_size_t chunk = 31;
     srand(0);
@@ -115,21 +115,21 @@ tests/test.py << TEST
     info.type => LFS_TYPE_REG;
     info.size => strlen("Hello World!\n");
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
-    strcmp(info.name, "smallavacado") => 0;
+    strcmp(info.name, "largeavacado") => 0;
     info.type => LFS_TYPE_REG;
-    info.size => $SMALLSIZE;
+    info.size => $LARGESIZE;
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
     strcmp(info.name, "mediumavacado") => 0;
     info.type => LFS_TYPE_REG;
     info.size => $MEDIUMSIZE;
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
-    strcmp(info.name, "largeavacado") => 0;
-    info.type => LFS_TYPE_REG;
-    info.size => $LARGESIZE;
-    lfs_dir_read(&lfs, &dir[0], &info) => 1;
     strcmp(info.name, "noavacado") => 0;
     info.type => LFS_TYPE_REG;
     info.size => 0;
+    lfs_dir_read(&lfs, &dir[0], &info) => 1;
+    strcmp(info.name, "smallavacado") => 0;
+    info.type => LFS_TYPE_REG;
+    info.size => $SMALLSIZE;
     lfs_dir_read(&lfs, &dir[0], &info) => 0;
     lfs_dir_close(&lfs, &dir[0]) => 0;
     lfs_unmount(&lfs) => 0;
diff --git a/tests/test_move.sh b/tests/test_move.sh
index 53f7e15..458ca1e 100755
--- a/tests/test_move.sh
+++ b/tests/test_move.sh
@@ -257,10 +257,10 @@ tests/test.py << TEST
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
     strcmp(info.name, "..") => 0;
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
-    strcmp(info.name, "hola") => 0;
-    lfs_dir_read(&lfs, &dir[0], &info) => 1;
     strcmp(info.name, "bonjour") => 0;
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
+    strcmp(info.name, "hola") => 0;
+    lfs_dir_read(&lfs, &dir[0], &info) => 1;
     strcmp(info.name, "ohayo") => 0;
     lfs_dir_read(&lfs, &dir[0], &info) => 0;
     lfs_dir_close(&lfs, &dir[0]) => 0;
@@ -303,10 +303,10 @@ tests/test.py << TEST
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
     strcmp(info.name, "..") => 0;
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
-    strcmp(info.name, "hola") => 0;
-    lfs_dir_read(&lfs, &dir[0], &info) => 1;
     strcmp(info.name, "bonjour") => 0;
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
+    strcmp(info.name, "hola") => 0;
+    lfs_dir_read(&lfs, &dir[0], &info) => 1;
     strcmp(info.name, "ohayo") => 0;
     lfs_dir_read(&lfs, &dir[0], &info) => 0;
     lfs_dir_close(&lfs, &dir[0]) => 0;
diff --git a/tests/test_seek.sh b/tests/test_seek.sh
index 0084d42..609c250 100755
--- a/tests/test_seek.sh
+++ b/tests/test_seek.sh
@@ -12,7 +12,7 @@ tests/test.py << TEST
     lfs_mount(&lfs, &cfg) => 0;
     lfs_mkdir(&lfs, "hello") => 0;
     for (int i = 0; i < $LARGESIZE; i++) {
-        sprintf((char*)buffer, "hello/kitty%d", i);
+        sprintf((char*)buffer, "hello/kitty%03d", i);
         lfs_file_open(&lfs, &file[0], (char*)buffer,
                 LFS_O_WRONLY | LFS_O_CREAT | LFS_O_APPEND) => 0;
 
@@ -39,7 +39,7 @@ tests/test.py << TEST
     lfs_soff_t pos;
     int i;
     for (i = 0; i < $SMALLSIZE; i++) {
-        sprintf((char*)buffer, "kitty%d", i);
+        sprintf((char*)buffer, "kitty%03d", i);
         lfs_dir_read(&lfs, &dir[0], &info) => 1;
         strcmp(info.name, (char*)buffer) => 0;
         pos = lfs_dir_tell(&lfs, &dir[0]);
@@ -47,12 +47,12 @@ tests/test.py << TEST
     pos >= 0 => 1;
 
     lfs_dir_seek(&lfs, &dir[0], pos) => 0;
-    sprintf((char*)buffer, "kitty%d", i);
+    sprintf((char*)buffer, "kitty%03d", i);
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
     strcmp(info.name, (char*)buffer) => 0;
 
     lfs_dir_rewind(&lfs, &dir[0]) => 0;
-    sprintf((char*)buffer, "kitty%d", 0);
+    sprintf((char*)buffer, "kitty%03d", 0);
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
     strcmp(info.name, ".") => 0;
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
@@ -61,7 +61,7 @@ tests/test.py << TEST
     strcmp(info.name, (char*)buffer) => 0;
 
     lfs_dir_seek(&lfs, &dir[0], pos) => 0;
-    sprintf((char*)buffer, "kitty%d", i);
+    sprintf((char*)buffer, "kitty%03d", i);
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
     strcmp(info.name, (char*)buffer) => 0;
 
@@ -81,7 +81,7 @@ tests/test.py << TEST
     lfs_soff_t pos;
     int i;
     for (i = 0; i < $MEDIUMSIZE; i++) {
-        sprintf((char*)buffer, "kitty%d", i);
+        sprintf((char*)buffer, "kitty%03d", i);
         lfs_dir_read(&lfs, &dir[0], &info) => 1;
         strcmp(info.name, (char*)buffer) => 0;
         pos = lfs_dir_tell(&lfs, &dir[0]);
@@ -89,12 +89,12 @@ tests/test.py << TEST
     pos >= 0 => 1;
 
     lfs_dir_seek(&lfs, &dir[0], pos) => 0;
-    sprintf((char*)buffer, "kitty%d", i);
+    sprintf((char*)buffer, "kitty%03d", i);
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
     strcmp(info.name, (char*)buffer) => 0;
 
     lfs_dir_rewind(&lfs, &dir[0]) => 0;
-    sprintf((char*)buffer, "kitty%d", 0);
+    sprintf((char*)buffer, "kitty%03d", 0);
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
     strcmp(info.name, ".") => 0;
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
@@ -103,7 +103,7 @@ tests/test.py << TEST
     strcmp(info.name, (char*)buffer) => 0;
 
     lfs_dir_seek(&lfs, &dir[0], pos) => 0;
-    sprintf((char*)buffer, "kitty%d", i);
+    sprintf((char*)buffer, "kitty%03d", i);
     lfs_dir_read(&lfs, &dir[0], &info) => 1;
     strcmp(info.name, (char*)buffer) => 0;
 
@@ -114,7 +114,7 @@ TEST
 echo "--- Simple file seek ---"
 tests/test.py << TEST
     lfs_mount(&lfs, &cfg) => 0;
-    lfs_file_open(&lfs, &file[0], "hello/kitty42", LFS_O_RDONLY) => 0;
+    lfs_file_open(&lfs, &file[0], "hello/kitty042", LFS_O_RDONLY) => 0;
 
     lfs_soff_t pos;
     size = strlen("kittycatcat");
@@ -163,7 +163,7 @@ TEST
 echo "--- Large file seek ---"
 tests/test.py << TEST
     lfs_mount(&lfs, &cfg) => 0;
-    lfs_file_open(&lfs, &file[0], "hello/kitty42", LFS_O_RDONLY) => 0;
+    lfs_file_open(&lfs, &file[0], "hello/kitty042", LFS_O_RDONLY) => 0;
 
     lfs_soff_t pos;
     size = strlen("kittycatcat");
@@ -212,7 +212,7 @@ TEST
 echo "--- Simple file seek and write ---"
 tests/test.py << TEST
     lfs_mount(&lfs, &cfg) => 0;
-    lfs_file_open(&lfs, &file[0], "hello/kitty42", LFS_O_RDWR) => 0;
+    lfs_file_open(&lfs, &file[0], "hello/kitty042", LFS_O_RDWR) => 0;
 
     lfs_soff_t pos;
     size = strlen("kittycatcat");
@@ -253,7 +253,7 @@ TEST
 echo "--- Large file seek and write ---"
 tests/test.py << TEST
     lfs_mount(&lfs, &cfg) => 0;
-    lfs_file_open(&lfs, &file[0], "hello/kitty42", LFS_O_RDWR) => 0;
+    lfs_file_open(&lfs, &file[0], "hello/kitty042", LFS_O_RDWR) => 0;
 
     lfs_soff_t pos;
     size = strlen("kittycatcat");
@@ -296,7 +296,7 @@ TEST
 echo "--- Boundary seek and write ---"
 tests/test.py << TEST
     lfs_mount(&lfs, &cfg) => 0;
-    lfs_file_open(&lfs, &file[0], "hello/kitty42", LFS_O_RDWR) => 0;
+    lfs_file_open(&lfs, &file[0], "hello/kitty042", LFS_O_RDWR) => 0;
 
     size = strlen("hedgehoghog");
     const lfs_soff_t offsets[] = {512, 1020, 513, 1021, 511, 1019};
@@ -324,7 +324,7 @@ TEST
 echo "--- Out-of-bounds seek ---"
 tests/test.py << TEST
     lfs_mount(&lfs, &cfg) => 0;
-    lfs_file_open(&lfs, &file[0], "hello/kitty42", LFS_O_RDWR) => 0;
+    lfs_file_open(&lfs, &file[0], "hello/kitty042", LFS_O_RDWR) => 0;
 
     size = strlen("kittycatcat");
     lfs_file_size(&lfs, &file[0]) => $LARGESIZE*size;