Store ownership and c/m/atime

[rojer]

Would be nice to be able to store these metadata fields, like the big boys :)

[geky]

Yes! I agree. It's also a good time with littlefs3, to minimize the risk of attr-number conflicts. (littlefs3 reserves attrs 0x80-0xbf for "standard attrs" (littlefs-project/littlefs#1111 (comment)), though looking at it now, the note is likely lost in the noise).

But there is still the issue of deciding on the exact formats, which deserve wider discussion.

My current thinking is a sort of RFC-period for each "standard attr" via GitHub issues on the core repo, but to wait to commit to the exact format until some time after littlefs3 stabilization (at least on-disk, v3-beta?). I think that is a time period where a lot of eyes will be on the repo. Unfortunately very few users pay attention to things until after stabilization, which is humorously the worst time to discuss things (though maybe this is also a documentation issue).

---

But to toss around some ideas (sorry for the wall of text, I may have gotten nerd-sniped):

1. LFS3_SATTR_CTIME/LFS3_SATTR_MTIME/LFS3_SATTR_ATIME/LFS3_SATTR_BTIME

   Time is always tricky, three immediate ideas:

   1. 1 leb128 nanoseconds since 1970
   2. 1 leb128 seconds, 1 leb128 nanoseconds (optional)
   3. 1 leb128 seconds, 1 leb128 bit-reversed subsecond precision (optional)

   iii. would be the most flexible, but also the most confusing. Maybe one big nanosecond leb128 is a better idea since using 64-bits for time is a good idea even on MCUs. With nanoseconds 64-bits overflows in the year 2554, but maybe we'll have uint128_t support by then.

   Also, actually using atime is a bad IMO, but there's no reason to not reserve the attr. Though I don't think lfs-fuse should update it by default.

2. LFS3_SATTR_PERM

   Specifically for POSIX compatibility:

   1. 1 leb128 permission bits, 1 leb128 uid (optional), 1 leb128 gid (optional)

      Where permission bits is just a 1-to-1 map to the lower 12-bits of POSIX's st_mode:

      ugxr wxrw xrwx
      ^^^'-.''-.''.'
      '||--|---|--|-- setuid bit
       '|--|---|--|-- setgid bit
        '--|---|--|-- sticky bit
           '---|--|-- owner permissions
               '--|-- group permissions
                  '-- other permissions
      

   POSIX is not perfect (I also need to read up on the subtleties of setuid/setgid/sticky), but the nice thing about littlefs's attr system is users/OSs are welcome to experiment with non-standard permission models without much penalty.

3. LFS3_SATTR_TYPE

   It would also be useful to have a type field for OS-specific types littlefs otherwise treats as regular files (sockets, devices, etc):

   1. 1 leb128 type

      Maybe broken down to match uattrs/sattrs in littlefs3?

      • 0x00-0x7f - Free for user-types (utypes)
      • 0x80-0xbf - Reserved for standard-types (stypes)
      • 0xc0-0xff - Encouraged for system-types (ytypes)
      • >0xff - Reserved

4. LFS3_SATTR_COMPR

   One of the missing pieces in littlefs is transparent compression (Will littfs support compression in the future？ littlefs#672 (comment)). I think this could be implemented via a standard attr:

   1. 1 leb128 compression type, trailing bytes are per-type config

      Maybe also broken down into u/s/y compr types:

      • 0x00-0x7f - Free for user-comprs (ucomprs)
      • 0x80-0xbf - Reserved for standard-comprs (scomprs)
      • 0xc0-0xff - Encouraged for system-comprs (ycomprs)
      • >0xff - Reserved

   Though there's a lot of details to hammer out around transparent compression, so it will probably be out-of-scope for a while.

EDIT: Added LFS3_SATTR_BTIME

[rojer]

i have a project for which we are going with littlefs on linux via littlefs-fuse (fs itself is still relatively small), so i doodled a bit and have something that atg least appears to work. here's a small snippet:

#define LFS_ATTR_UTIMENS 0x54 // 'T'

struct lfs_timens {
    uint32_t sec;
    uint32_t nsec;
} __attribute__((packed));

struct lfs_attr_utimens {
    struct lfs_timens ctime;
    struct lfs_timens mtime;
    struct lfs_timens atime;
} __attribute__((packed));

static void lfs_ts_to_tns(const struct timespec *ts, struct lfs_timens *tns) {
  tns->sec = ts->tv_sec;
  tns->nsec = ts->tv_nsec;
}

static void lfs_tv_to_tns(const struct timeval *tv, struct lfs_timens *tns) {
  tns->sec = tv->tv_sec;
  tns->nsec = tv->tv_usec * 1000;
}

static bool lfs_get_utimens(lfs_t *lfs, const char *path, struct lfs_attr_utimens *ut) {
  return (lfs_getattr(lfs, path, LFS_ATTR_UTIMENS, ut, sizeof(*ut)) == sizeof(*ut));
}

...

#define LFS_ATTR_UNIX 0x55 // 'U'

struct lfs_attr_unix {
    uint32_t uid;
    uint32_t gid;
    uint32_t mode;
} __attribute__((packed));

static bool lfs_get_unix(lfs_t *lfs, const char *path, struct lfs_attr_unix *ua) {
  return (lfs_getattr(lfs, path, LFS_ATTR_UNIX, ua, sizeof(*ua)) == sizeof(*ua));
}

i went with u32+u32 for times because it's easiest to translate to and from both timeval and timespec, with only one multiplication.
atime is not so bad, as long as it's relatime, so - why not. we should also reserve space for btime - available via statx(2) and coming with fuse v3.

[rojer]

My WIP branch is here: https://github.com/rojer/littlefs-fuse/tree/shelly
I also found it useful to have lfs_file_get/setattr() - to be able to update utimes on read/write via lfs_file_t, without a path lookup.

[geky]

i went with u32+u32 for times because it's easiest to translate to and from both timeval and timespec, with only one multiplication.

The concern I have with split seconds + nanoseconds, is what do you do if there's >1e9 nanoseconds? Add to seconds? I'm a bit concerned about the potential for incompatibilities across OSs if we adopt it as the standard.

Though the option to ignore nanoseconds and just store seconds is nice.

atime is not so bad, as long as it's relatime, so - why not.

Ah, does relatime basically make atime == mtime? I guess to me that's the same as disabling atime :) Though it makes sense as the default behavior of atime violating read != write is pretty terrible.

I need to read up on common mount flag names, this is likely a well-tread path at this point.

we should also reserve space for btime

Good point! Edited. I did read something on btime but forgot about it.

I also found it useful to have lfs_file_get/setattr() - to be able to update utimes on read/write via lfs_file_t, without a path lookup.

What are your thoughts on lfs_file_getattr/setattr but requiring a per-file attr_buffer to hold all attrs in RAM? (littlefs-project/littlefs#1076 (comment))

This seems like the only way to provide such an API without breaking littlefs's file-level snapshotting semantics. But lfs_file_getattr/setattr has been heavily requested.

[rojer]

nsec > 1e9? consider invalid, i guess. set to 0, round down to seconds.

one other idea i had wrt storing tiime more compactly is to limit to milliseconds and store u32_t seconds + 10-bit field for ms:

u32_t ctime_sec;
u32_t mtime_sec;
u32_t atime_sec;
u32_t ctime_ms : 10;
u32_t mtime_ms : 10;
u32_t atime_ms : 10;

because surely ms precision should be enough for everyone, right? :)
and it packs nicely into 4 u32s. btime kinda screws it up though.

does relatime basically make atime == mtime? I guess to me that's the same as disabling atime :)

not quite, it's still useful to find ancient files not accessed for days. it just makes it coarse to 24h

per-file attr_buffer to hold all attrs in RAM?

seems reasonable, also makes stuff like utimes cheap to update without too much i/o overhead (flushed on file close and/or fsync).

lfs_file_getattr/setattr has been heavily requested.

and almost trivial to implement, too (unless i misunderstood something) - does this look reasonable to you? (edit: GH sucks at linking, look at changes to lfs.c, basically)

[geky]

and almost trivial to implement, too (unless i misunderstood something) - does this look reasonable to you? (edit: GH sucks at linking, look at changes to lfs.c, basically)

This seems like the obvious solution, and avoids the need for RAM, but it unfortunately makes a mess of littlefs's sync model, i.e. the idea that file changes have no affect on-disk until sync/close is called (this exists in littlefs2, but is more rigorously defined in littlefs3).

This sync model works by relying on CoW snapshotting for file data, and RAM for file metadata.
Though before custom attributes, a file's metadata is roughly 2 integers.

Without the sync model, some issues start to poke through:

1. It's impossible to atomically update a file's attributes with the file data, at least without rename shenanigans.

2. Deleting an open file drifts further from POSIX expectations:

   lfs_file_open(&lfs, &file, "apricot") => 0;
   lfs_file_setattr(&lfs, &file, 'a', "hi", 2) => 0;
   lfs_remove(&lfs, "apricot") => 0;
   lfs_file_getattr(&lfs, &file, 'a', buffer, size) => ?;

In theory it's possible to also back user attributes with a CoW data structure, but it would introduce significant overhead.

seems reasonable, also makes stuff like utimes cheap to update without too much i/o overhead (flushed on file close and/or fsync).

Good point! RAM-backed attrs also maximize the work that is accomplished in a single mdir commit.

not quite, it's still useful to find ancient files not accessed for days. it just makes it coarse to 24h

Hmmm, it seems like noatime would be a preferable default to avoid surprising users with write operations during reads.

Though we can always provide other atime behaviors behind flags. I'll have to see if FUSE already models this for us, it's been a helpful library.

[geky]

because surely ms precision should be enough for everyone, right? :)
and it packs nicely into 4 u32s. btime kinda screws it up though.

Time to make centiseconds popular!

This is one benefit of the bit-reversed leb128 approach, in theory it could scale to whatever resolution is used by the system.

Another option is leb128 + optional leb128 scale (nanoseconds? power-of-two? power-of-ten?). At which point we've basically reinvented floating point numbers, which isn't necessary a bad thing.

One assumption I have is that most devices will write timestamps much more frequently than reading timestamps, so allowing devices to write whatever resolution is available is useful, even if it means more work to parse.

[rojer]

wrt units for storing time - i think they should either be prescribed once and for all, or there should be a way to select them: users can then choose the granularity - s/ms/us/ns and make a trade-off that makes sense for their application. it can be specified in the fs config, so as not to waste space in each attr entry. additionally, differential encoding could be employed within the entry itself: for example, btime becomes the baseline and c/m/atime are represented as diffs wrt btime. in this case variable length encoding will really shine.

Without the sync model, some issues start to poke through

true, though it's no worse than posix/linux, is it? that said, i'm not claiming completeness, this truly was a quick hack to get ownerhip and utimes on lfsv2 work, just about.

[geky]

true, though it's no worse than posix/linux, is it?

Yes, but the goal is to be better than POSIX/linux :)

At least when it comes to power-loss safety. Being able to bend the POSIX rules in this regard is not something most filesystem devs get to do.

wrt units for storing time - i think they should either be prescribed once and for all, or there should be a way to select them: users can then choose the granularity - s/ms/us/ns and make a trade-off that makes sense for their application. it can be specified in the fs config, so as not to waste space in each attr entry.

Quick side-note: filesystem-config is supported with lfs_setattr(&lfs, "/", type, buffer, size). Though it's an easy feature to miss.

Maybe I shouldn't have mentioned the leb128 encoding. It's true it generally reduces storage usage, but that isn't really the goal (the motivation for leb128 is removing device integer limits). If anything the problem in littlefs is that we generally have too much storage.

Something to keep in mind is each attr has a ~40 byte overhead when you include the cost of the rbyd tree. So I'm not sure we care about the ~1-2 byte overhead of encoding a timescale for each attr. The benefit being that libraries implementing timestamps don't need to keep track of the global timescale and hopefully minimizing the risk of libraries supporting only a preconfigured timescale.

One challenge of deciding on a standard attr is we need libraries from different authors to get along.

additionally, differential encoding could be employed within the entry itself: for example, btime becomes the baseline and c/m/atime are represented as diffs wrt btime. in this case variable length encoding will really shine.

The delta encoding is clever. You would lose the ability for things like atime < mtime, but I'm not sure that has a valid use.

For optimal cost you could have a one leb128 timescale followed by delta encoded leb128 btime < ctime < mtime < atime, crammed into a single attr. Though if this is worth the extra complexity I'm not sure.

For one, adding more timestamps in the future might be tricky (see btime). For two, libraries would need to calculate the new delta during updates, instead of just throwing the current clock at whatever *times changed. Will need to sleep on it...

[geky]

Consider this timestamp format:

0ttttttt ... 1ttttttt [0xxxxxxx ... 1xxxxxxs]
'---------.---------'  '---------.--------'^
          '----------------------|---------|-- leb128 time (default=seconds)
                                 '---------|-- optional leb128 scale
                                           '-- scale sign-bit
'---------.---------'  '---------.--------'|
          |      .---------------|---------'
          |      | .-------------'
          v      v v
   time = t * 2^(s*x) seconds

So current time in milliseconds: 1763417279.903:

   time    = 1763417279.903
   scale   = -11
=> scaled  = 3611478589241 * 2^-11
                   '-.          |
             .-------'-------.  v
=> encoded = b9 fe 97 e7 8d 69 17

Or when crammed:

0xxxxxxx ... 1xxxxxxs 0bbbbbbb ... 1bbbbbbb 0ccccccc ... 1ccccccc 0mmmmmmm ... 1mmmmmmm 0aaaaaaa ... 1aaaaaaa
'---------.--------'^ '---------.---------' '---------.---------' '---------.---------' '---------.---------'
          '---------|-----------|---------------------|---------------------|---------------------|-- leb128 scale
                    '-----------|---------------------|---------------------|---------------------|-- scale sign-bit
                                '---------------------|---------------------|---------------------|-- leb128 btime
                                                      '---------------------|---------------------|-- optional leb128 ctime delta
                                                                            '---------------------|-- optional leb128 mtime delta
                                                                                                  '-- optional leb128 atime delta
'---------.--------'| '---------.---------' '---------.---------' '---------.---------' '---------.---------'
          '---------|----.      |                     |                     |                     |
                    '--. |      |                     |                     |                     |
         .-------------|-|------|---------------------|---------------------|---------------------'
         | .-----------|-|------|---------------------|---------------------'
         | | .---------|-|------|---------------------'
         | | | .-------|-|------'
         v v v v       v v
atime = (b+c+m+a) * 2^(s*x) seconds

So current time in milliseconds: 1763417279.903:

   time    = 1763417279.903
   scale   = -11
=> scaled  = 3611478589241 * 2^-11
                   '-.          |
             .-------'-------.  v
=> encoded = b9 fe 97 e7 8d 69 17

I called the timescale a leb128, but I think realistically it'd never exceed a single byte (2^-64..2^64)... Maybe we just make it a int8_t to avoid the signed-leb128 awkwardness. Or u8-127 to keep the top-bit reserved for future leb128 extensions, at which point it'd really look like a floating point number.

[geky]

Something to keep in mind is each attr has a ~40 byte overhead

Correction: An optimization (littlefs-project/littlefs@7c8c7e6) reduced this to ~25 bytes per attr.

[rojer]

we generally have too much storage.

not the case for us! we ship 256K - 1M filesystems, generally. even our linux product has a 32M NOR flash chip and it gets very cozy there :) but yeah, 1 byte per attr is not an issue, nor is 25 bytes overhead per file.

atime = (b+c+m+a) * 2^(s*x) seconds

so, i guess, then we have

mtime = (b+c+m) * 2^(s*x) seconds
ctime = (b+c) * 2^(s*x) seconds
btime = (b) * 2^(s*x) seconds

yeah, something like that. my idea was to always compute delta from btime but actually, delta-to-delta is clever, as in many cases we have c=m, and c=m=a is also common, so they will collapse to 0. so, even cleverer :)

a function to parse/serialize this ahs to be provided, though, or there will be multiple broken implementations.