Multigrain Timestamps

Coarse timestamp의 장단점과 NFS 문제

역사적으로 kernel은 inode timestamp에 coarse time 값을 사용했습니다. 이 값은 jiffy마다 한 번 갱신되므로 같은 jiffy 안에서 일어난 변경은 모두 같은 timestamp를 갖습니다.

Read나 write 때문에 inode를 stamp할 때 kernel은 먼저 현재 시간을 얻고 기존 timestamp와 비교하여 실제 값이 달라지는지 확인합니다. 바뀌지 않는다면 inode metadata update를 피할 수 있습니다.

따라서 coarse timestamp는 metadata update 필요성을 줄여 성능에는 좋지만, 한 jiffy 안에 많은 일이 일어날 수 있어 변경 여부를 판단하는 데는 좋지 않습니다.

특히 NFSv3에서는 timestamp가 그대로이면 cache를 invalidate해야 하는지 판단하기 어렵습니다. NFSv4에는 항상 눈에 보이는 변화를 나타내야 하는 전용 change attribute가 있지만 모든 파일시스템이 이를 올바르게 구현하지 않아 NFS server가 많은 경우 `ctime`을 대신 사용합니다.

Multigrain timestamp는 파일 timestamp가 최근 조회되었고 현재 coarse time으로는 값이 바뀌지 않을 때만 선택적으로 fine-grained timestamp를 사용해 이 문제를 해결합니다.

.. SPDX-License-Identifier: GPL-2.0

=====================
Multigrain Timestamps
=====================

Introduction
============
Historically, the kernel has always used coarse time values to stamp inodes.
This value is updated every jiffy, so any change that happens within that jiffy
will end up with the same timestamp.

When the kernel goes to stamp an inode (due to a read or write), it first gets
the current time and then compares it to the existing timestamp(s) to see
whether anything will change. If nothing changed, then it can avoid updating
the inode's metadata.

Coarse timestamps are therefore good from a performance standpoint, since they
reduce the need for metadata updates, but bad from the standpoint of
determining whether anything has changed, since a lot of things can happen in a
jiffy.

They are particularly troublesome with NFSv3, where unchanging timestamps can
make it difficult to tell whether to invalidate caches. NFSv4 provides a
dedicated change attribute that should always show a visible change, but not
all filesystems implement this properly, causing the NFS server to substitute
the ctime in many cases.

Multigrain timestamps aim to remedy this by selectively using fine-grained
timestamps when a file has had its timestamps queried recently, and the current
coarse-grained time does not cause a change.

ctime·mtime·atime의 의미와 적용 범위

Inode에는 서로 다른 activity에서 현재 wallclock time으로 갱신되는 timestamp 세 개가 있습니다.

`ctime`은 inode change time입니다. Inode metadata가 바뀔 때마다 현재 시간으로 stamp되며 userspace에서 직접 설정할 수 없습니다.

`mtime`은 inode modification time입니다. 파일 내용이 바뀔 때마다 현재 시간으로 stamp됩니다. `atime`은 inode access time이며 내용을 읽을 때 stamp됩니다. 널리 좋지 않은 설계로 여겨지고 보통 `noatime`이나 `relatime` option으로 갱신을 피합니다.

`mtime` 갱신은 항상 `ctime` 변경도 뜻하지만 read request에 따른 `atime` 갱신은 `ctime` 변경을 뜻하지 않습니다.

Multigrain timestamp는 `ctime`과 `mtime`만 추적합니다. `atime`은 영향을 받지 않으며 floor 조건을 적용받는 coarse-grained 값만 사용합니다.

Inode Timestamps
================
There are currently 3 timestamps in the inode that are updated to the current
wallclock time on different activity:

ctime:
  The inode change time. This is stamped with the current time whenever
  the inode's metadata is changed. Note that this value is not settable
  from userland.

mtime:
  The inode modification time. This is stamped with the current time
  any time a file's contents change.

atime:
  The inode access time. This is stamped whenever an inode's contents are
  read. Widely considered to be a terrible mistake. Usually avoided with
  options like noatime or relatime.

Updating the mtime always implies a change to the ctime, but updating the
atime due to a read request does not.

Multigrain timestamps are only tracked for the ctime and the mtime. atimes are
not affected and always use the coarse-grained value (subject to the floor).

Userspace가 관찰할 수 있는 timestamp 순서

File timestamp는 개별 파일의 변경 정보뿐 아니라 `make` 같은 application에서 중요한 ordering 기준입니다. 이러한 프로그램은 source file이 cached object보다 새 것인지 timestamp로 판단합니다.

Userspace application은 operation boundary를 기준으로만 순서를 판단할 수 있습니다. Syscall에서는 entry와 exit, io_uring 또는 nfsd operation에서는 request submission과 response가 경계입니다. Concurrent operation의 실제 발생 순서는 userspace가 판단할 수 없습니다.

단일 thread가 한 파일을 수정한 뒤 순서대로 다른 파일을 수정하면 두 번째 파일의 `mtime`은 첫 번째와 같거나 더 늦어야 합니다. 시간상 겹치지 않는 두 thread의 유사 operation에도 같은 보장이 적용됩니다.

반대로 두 thread의 syscall이 시간상 겹쳐 race하면 이런 보장은 없습니다. 어느 요청이 먼저 제출되었든 두 번째 파일은 첫 번째보다 이전, 이후, 같은 시각에 수정된 것으로 보일 수 있습니다.

이 설명은 system realtime clock이 뒤로 뛰지 않는다고 가정합니다. 부적절한 시점에 backward jump가 일어나면 정상 동작 중인 시스템에서도 timestamp가 뒤로 간 것처럼 보일 수 있습니다.

Inode Timestamp Ordering
========================

In addition to just providing info about changes to individual files, file
timestamps also serve an important purpose in applications like "make". These
programs measure timestamps in order to determine whether source files might be
newer than cached objects.

Userland applications like make can only determine ordering based on
operational boundaries. For a syscall those are the syscall entry and exit
points. For io_uring or nfsd operations, that's the request submission and
response. In the case of concurrent operations, userland can make no
determination about the order in which things will occur.

For instance, if a single thread modifies one file, and then another file in
sequence, the second file must show an equal or later mtime than the first. The
same is true if two threads are issuing similar operations that do not overlap
in time.

If however, two threads have racing syscalls that overlap in time, then there
is no such guarantee, and the second file may appear to have been modified
before, after or at the same time as the first, regardless of which one was
submitted first.

Note that the above assumes that the system doesn't experience a backward jump
of the realtime clock. If that occurs at an inopportune time, then timestamps
can appear to go backward, even on a properly functioning system.

조회 bit와 monotonic ctime floor

Multigrain timestamp의 목표는 서로 다른 여러 파일의 ordering guarantee를 깨뜨리지 않으면서 한 파일의 변경을 항상 식별할 수 있게 하는 것입니다. `mtime`과 `ctime`에 적용하고 `atime`은 항상 coarse-grained 값을 사용합니다.

구현은 `i_ctime_nsec` field의 사용하지 않는 bit를 이용해 `mtime` 또는 `ctime`이 조회되었는지 표시합니다. 둘 중 하나라도 조회되었으면 다음 timestamp update에서 눈에 보이는 변화가 생기도록 kernel이 특별히 처리합니다.

이 방식은 감시되지 않는 파일의 metadata update 감소 이점을 유지하면서 NFS 같은 사용 사례에 엄격한 cache coherency를 제공합니다.

조회 여부만으로 fine 또는 coarse timestamp를 고르는 것으로는 충분하지 않습니다. 첫 파일이 fine-grained timestamp를 받은 뒤 나중에 수정된 두 번째 파일이 더 이르게 보이는 coarse timestamp를 받으면 kernel의 ordering guarantee가 깨집니다.

이를 막기 위해 전역 floor 값을 유지합니다. 이 경우 두 파일이 같은 시각에 수정된 것처럼 보일 수는 있지만 역순으로 보이지는 않습니다. Realtime clock jump 문제를 피하도록 floor는 monotonic `ktime_t`로 관리하고 필요할 때 realtime clock 값으로 변환합니다.

Multigrain Timestamp Implementation
===================================
Multigrain timestamps are aimed at ensuring that changes to a single file are
always recognizable, without violating the ordering guarantees when multiple
different files are modified. This affects the mtime and the ctime, but the
atime will always use coarse-grained timestamps.

It uses an unused bit in the i_ctime_nsec field to indicate whether the mtime
or ctime has been queried. If either or both have, then the kernel takes
special care to ensure the next timestamp update will display a visible change.
This ensures tight cache coherency for use-cases like NFS, without sacrificing
the benefits of reduced metadata updates when files aren't being watched.

The Ctime Floor Value
=====================
It's not sufficient to simply use fine or coarse-grained timestamps based on
whether the mtime or ctime has been queried. A file could get a fine grained
timestamp, and then a second file modified later could get a coarse-grained one
that appears earlier than the first, which would break the kernel's timestamp
ordering guarantees.

To mitigate this problem, maintain a global floor value that ensures that
this can't happen. The two files in the above example may appear to have been
modified at the same time in such a case, but they will never show the reverse
order. To avoid problems with realtime clock jumps, the floor is managed as a
monotonic ktime_t, and the values are converted to realtime clock values as
needed.

파일시스템 구현과 FS_MGTIME opt-in

Multigrain timestamp는 local clock에서 `ctime`을 얻는 local filesystem용입니다. Server timestamp를 그대로 반영하는 network filesystem 등과는 사용 모델이 다릅니다.

대부분의 파일시스템은 `ctime`을 오직 `inode_set_ctime_current()`로만 설정한다는 조건에서 `fstype->fs_flags`에 `FS_MGTIME` flag를 넣는 것만으로 opt-in할 수 있습니다.

파일시스템의 `->getattr` routine이 `generic_fillattr`를 호출하지 않는다면 `fill_mg_cmtime()`로 `ctime`과 `mtime` 값을 채워야 합니다. `setattr`에서는 `setattr_copy()`로 timestamp를 갱신하거나 그 동작을 정확히 모방해야 합니다.

Implementation Notes
====================
Multigrain timestamps are intended for use by local filesystems that get
ctime values from the local clock. This is in contrast to network filesystems
and the like that just mirror timestamp values from a server.

For most filesystems, it's sufficient to just set the FS_MGTIME flag in the
fstype->fs_flags in order to opt-in, providing the ctime is only ever set via
inode_set_ctime_current(). If the filesystem has a ->getattr routine that
doesn't call generic_fillattr, then it should call fill_mg_cmtime() to
fill those values. For setattr, it should use setattr_copy() to update the
timestamps, or otherwise mimic its behavior.