요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.
1. 요약·해설
원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.
2. 영어 원문 전체
번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.
원문 전체 펼치기
.. SPDX-License-Identifier: GPL-2.0
.. _xfs_self_describing_metadata:
============================
XFS Self Describing Metadata
============================
Introduction
============
The largest scalability problem facing XFS is not one of algorithmic
scalability, but of verification of the filesystem structure. Scalabilty of the
structures and indexes on disk and the algorithms for iterating them are
adequate for supporting PB scale filesystems with billions of inodes, however it
is this very scalability that causes the verification problem.
Almost all metadata on XFS is dynamically allocated. The only fixed location
metadata is the allocation group headers (SB, AGF, AGFL and AGI), while all
other metadata structures need to be discovered by walking the filesystem
structure in different ways. While this is already done by userspace tools for
validating and repairing the structure, there are limits to what they can
verify, and this in turn limits the supportable size of an XFS filesystem.
For example, it is entirely possible to manually use xfs_db and a bit of
scripting to analyse the structure of a 100TB filesystem when trying to
determine the root cause of a corruption problem, but it is still mainly a
manual task of verifying that things like single bit errors or misplaced writes
weren't the ultimate cause of a corruption event. It may take a few hours to a
few days to perform such forensic analysis, so for at this scale root cause
analysis is entirely possible.
However, if we scale the filesystem up to 1PB, we now have 10x as much metadata
to analyse and so that analysis blows out towards weeks/months of forensic work.
Most of the analysis work is slow and tedious, so as the amount of analysis goes
up, the more likely that the cause will be lost in the noise. Hence the primary
concern for supporting PB scale filesystems is minimising the time and effort
required for basic forensic analysis of the filesystem structure.
Self Describing Metadata
========================
One of the problems with the current metadata format is that apart from the
magic number in the metadata block, we have no other way of identifying what it
is supposed to be. We can't even identify if it is the right place. Put simply,
you can't look at a single metadata block in isolation and say "yes, it is
supposed to be there and the contents are valid".
Hence most of the time spent on forensic analysis is spent doing basic
verification of metadata values, looking for values that are in range (and hence
not detected by automated verification checks) but are not correct. Finding and
understanding how things like cross linked block lists (e.g. sibling
pointers in a btree end up with loops in them) are the key to understanding what
went wrong, but it is impossible to tell what order the blocks were linked into
each other or written to disk after the fact.
Hence we need to record more information into the metadata to allow us to
quickly determine if the metadata is intact and can be ignored for the purpose
of analysis. We can't protect against every possible type of error, but we can
ensure that common types of errors are easily detectable. Hence the concept of
self describing metadata.
The first, fundamental requirement of self describing metadata is that the
metadata object contains some form of unique identifier in a well known
location. This allows us to identify the expected contents of the block and
hence parse and verify the metadata object. IF we can't independently identify
the type of metadata in the object, then the metadata doesn't describe itself
very well at all!
Luckily, almost all XFS metadata has magic numbers embedded already - only the
AGFL, remote symlinks and remote attribute blocks do not contain identifying
magic numbers. Hence we can change the on-disk format of all these objects to
add more identifying information and detect this simply by changing the magic
numbers in the metadata objects. That is, if it has the current magic number,
the metadata isn't self identifying. If it contains a new magic number, it is
self identifying and we can do much more expansive automated verification of the
metadata object at runtime, during forensic analysis or repair.
As a primary concern, self describing metadata needs some form of overall
integrity checking. We cannot trust the metadata if we cannot verify that it has
not been changed as a result of external influences. Hence we need some form of
integrity check, and this is done by adding CRC32c validation to the metadata
block. If we can verify the block contains the metadata it was intended to
contain, a large amount of the manual verification work can be skipped.
CRC32c was selected as metadata cannot be more than 64k in length in XFS and
hence a 32 bit CRC is more than sufficient to detect multi-bit errors in
metadata blocks. CRC32c is also now hardware accelerated on common CPUs so it is
fast. So while CRC32c is not the strongest of possible integrity checks that
could be used, it is more than sufficient for our needs and has relatively
little overhead. Adding support for larger integrity fields and/or algorithms
does really provide any extra value over CRC32c, but it does add a lot of
complexity and so there is no provision for changing the integrity checking
mechanism.
Self describing metadata needs to contain enough information so that the
metadata block can be verified as being in the correct place without needing to
look at any other metadata. This means it needs to contain location information.
Just adding a block number to the metadata is not sufficient to protect against
mis-directed writes - a write might be misdirected to the wrong LUN and so be
written to the "correct block" of the wrong filesystem. Hence location
information must contain a filesystem identifier as well as a block number.
Another key information point in forensic analysis is knowing who the metadata
block belongs to. We already know the type, the location, that it is valid
and/or corrupted, and how long ago that it was last modified. Knowing the owner
of the block is important as it allows us to find other related metadata to
determine the scope of the corruption. For example, if we have a extent btree
object, we don't know what inode it belongs to and hence have to walk the entire
filesystem to find the owner of the block. Worse, the corruption could mean that
no owner can be found (i.e. it's an orphan block), and so without an owner field
in the metadata we have no idea of the scope of the corruption. If we have an
owner field in the metadata object, we can immediately do top down validation to
determine the scope of the problem.
Different types of metadata have different owner identifiers. For example,
directory, attribute and extent tree blocks are all owned by an inode, while
freespace btree blocks are owned by an allocation group. Hence the size and
contents of the owner field are determined by the type of metadata object we are
looking at. The owner information can also identify misplaced writes (e.g.
freespace btree block written to the wrong AG).
Self describing metadata also needs to contain some indication of when it was
written to the filesystem. One of the key information points when doing forensic
analysis is how recently the block was modified. Correlation of set of corrupted
metadata blocks based on modification times is important as it can indicate
whether the corruptions are related, whether there's been multiple corruption
events that lead to the eventual failure, and even whether there are corruptions
present that the run-time verification is not detecting.
For example, we can determine whether a metadata object is supposed to be free
space or still allocated if it is still referenced by its owner by looking at
when the free space btree block that contains the block was last written
compared to when the metadata object itself was last written. If the free space
block is more recent than the object and the object's owner, then there is a
very good chance that the block should have been removed from the owner.
To provide this "written timestamp", each metadata block gets the Log Sequence
Number (LSN) of the most recent transaction it was modified on written into it.
This number will always increase over the life of the filesystem, and the only
thing that resets it is running xfs_repair on the filesystem. Further, by use of
the LSN we can tell if the corrupted metadata all belonged to the same log
checkpoint and hence have some idea of how much modification occurred between
the first and last instance of corrupt metadata on disk and, further, how much
modification occurred between the corruption being written and when it was
detected.
Runtime Validation
==================
Validation of self-describing metadata takes place at runtime in two places:
- immediately after a successful read from disk
- immediately prior to write IO submission
The verification is completely stateless - it is done independently of the
modification process, and seeks only to check that the metadata is what it says
it is and that the metadata fields are within bounds and internally consistent.
As such, we cannot catch all types of corruption that can occur within a block
as there may be certain limitations that operational state enforces of the
metadata, or there may be corruption of interblock relationships (e.g. corrupted
sibling pointer lists). Hence we still need stateful checking in the main code
body, but in general most of the per-field validation is handled by the
verifiers.
For read verification, the caller needs to specify the expected type of metadata
that it should see, and the IO completion process verifies that the metadata
object matches what was expected. If the verification process fails, then it
marks the object being read as EFSCORRUPTED. The caller needs to catch this
error (same as for IO errors), and if it needs to take special action due to a
verification error it can do so by catching the EFSCORRUPTED error value. If we
need more discrimination of error type at higher levels, we can define new
error numbers for different errors as necessary.
The first step in read verification is checking the magic number and determining
whether CRC validating is necessary. If it is, the CRC32c is calculated and
compared against the value stored in the object itself. Once this is validated,
further checks are made against the location information, followed by extensive
object specific metadata validation. If any of these checks fail, then the
buffer is considered corrupt and the EFSCORRUPTED error is set appropriately.
Write verification is the opposite of the read verification - first the object
is extensively verified and if it is OK we then update the LSN from the last
modification made to the object, After this, we calculate the CRC and insert it
into the object. Once this is done the write IO is allowed to continue. If any
error occurs during this process, the buffer is again marked with a EFSCORRUPTED
error for the higher layers to catch.
Structures
==========
A typical on-disk structure needs to contain the following information::
struct xfs_ondisk_hdr {
__be32 magic; /* magic number */
__be32 crc; /* CRC, not logged */
uuid_t uuid; /* filesystem identifier */
__be64 owner; /* parent object */
__be64 blkno; /* location on disk */
__be64 lsn; /* last modification in log, not logged */
};
Depending on the metadata, this information may be part of a header structure
separate to the metadata contents, or may be distributed through an existing
structure. The latter occurs with metadata that already contains some of this
information, such as the superblock and AG headers.
Other metadata may have different formats for the information, but the same
level of information is generally provided. For example:
- short btree blocks have a 32 bit owner (ag number) and a 32 bit block
number for location. The two of these combined provide the same
information as @owner and @blkno in eh above structure, but using 8
bytes less space on disk.
- directory/attribute node blocks have a 16 bit magic number, and the
header that contains the magic number has other information in it as
well. hence the additional metadata headers change the overall format
of the metadata.
A typical buffer read verifier is structured as follows::
#define XFS_FOO_CRC_OFF offsetof(struct xfs_ondisk_hdr, crc)
static void
xfs_foo_read_verify(
struct xfs_buf *bp)
{
struct xfs_mount *mp = bp->b_mount;
if ((xfs_sb_version_hascrc(&mp->m_sb) &&
!xfs_verify_cksum(bp->b_addr, BBTOB(bp->b_length),
XFS_FOO_CRC_OFF)) ||
!xfs_foo_verify(bp)) {
XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, mp, bp->b_addr);
xfs_buf_ioerror(bp, EFSCORRUPTED);
}
}
The code ensures that the CRC is only checked if the filesystem has CRCs enabled
by checking the superblock of the feature bit, and then if the CRC verifies OK
(or is not needed) it verifies the actual contents of the block.
The verifier function will take a couple of different forms, depending on
whether the magic number can be used to determine the format of the block. In
the case it can't, the code is structured as follows::
static bool
xfs_foo_verify(
struct xfs_buf *bp)
{
struct xfs_mount *mp = bp->b_mount;
struct xfs_ondisk_hdr *hdr = bp->b_addr;
if (hdr->magic != cpu_to_be32(XFS_FOO_MAGIC))
return false;
if (!xfs_sb_version_hascrc(&mp->m_sb)) {
if (!uuid_equal(&hdr->uuid, &mp->m_sb.sb_uuid))
return false;
if (bp->b_bn != be64_to_cpu(hdr->blkno))
return false;
if (hdr->owner == 0)
return false;
}
/* object specific verification checks here */
return true;
}
If there are different magic numbers for the different formats, the verifier
will look like::
static bool
xfs_foo_verify(
struct xfs_buf *bp)
{
struct xfs_mount *mp = bp->b_mount;
struct xfs_ondisk_hdr *hdr = bp->b_addr;
if (hdr->magic == cpu_to_be32(XFS_FOO_CRC_MAGIC)) {
if (!uuid_equal(&hdr->uuid, &mp->m_sb.sb_uuid))
return false;
if (bp->b_bn != be64_to_cpu(hdr->blkno))
return false;
if (hdr->owner == 0)
return false;
} else if (hdr->magic != cpu_to_be32(XFS_FOO_MAGIC))
return false;
/* object specific verification checks here */
return true;
}
Write verifiers are very similar to the read verifiers, they just do things in
the opposite order to the read verifiers. A typical write verifier::
static void
xfs_foo_write_verify(
struct xfs_buf *bp)
{
struct xfs_mount *mp = bp->b_mount;
struct xfs_buf_log_item *bip = bp->b_fspriv;
if (!xfs_foo_verify(bp)) {
XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, mp, bp->b_addr);
xfs_buf_ioerror(bp, EFSCORRUPTED);
return;
}
if (!xfs_sb_version_hascrc(&mp->m_sb))
return;
if (bip) {
struct xfs_ondisk_hdr *hdr = bp->b_addr;
hdr->lsn = cpu_to_be64(bip->bli_item.li_lsn);
}
xfs_update_cksum(bp->b_addr, BBTOB(bp->b_length), XFS_FOO_CRC_OFF);
}
This will verify the internal structure of the metadata before we go any
further, detecting corruptions that have occurred as the metadata has been
modified in memory. If the metadata verifies OK, and CRCs are enabled, we then
update the LSN field (when it was last modified) and calculate the CRC on the
metadata. Once this is done, we can issue the IO.
Inodes and Dquots
=================
Inodes and dquots are special snowflakes. They have per-object CRC and
self-identifiers, but they are packed so that there are multiple objects per
buffer. Hence we do not use per-buffer verifiers to do the work of per-object
verification and CRC calculations. The per-buffer verifiers simply perform basic
identification of the buffer - that they contain inodes or dquots, and that
there are magic numbers in all the expected spots. All further CRC and
verification checks are done when each inode is read from or written back to the
buffer.
The structure of the verifiers and the identifiers checks is very similar to the
buffer code described above. The only difference is where they are called. For
example, inode read verification is done in xfs_inode_from_disk() when the inode
is first read out of the buffer and the struct xfs_inode is instantiated. The
inode is already extensively verified during writeback in xfs_iflush_int, so the
only addition here is to add the LSN and CRC to the inode as it is copied back
into the buffer.
XXX: inode unlinked list modification doesn't recalculate the inode CRC! None of
the unlinked list modifications check or update CRCs, neither during unlink nor
log recovery. So, it's gone unnoticed until now. This won't matter immediately -
repair will probably complain about it - but it needs to be fixed.
3. 한국어 전문 번역
영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.
Introduction
1-39XFS가 직면한 가장 큰 scalability 문제는 algorithm의 확장성이 아니라 filesystem structure를 검증하는 일입니다. Ondisk structure와 index, 이를 순회하는 algorithm은 수십억 inode를 가진 PB-scale filesystem을 지원할 만큼 충분하지만, 바로 그 확장성이 verification 문제를 일으킵니다.
XFS metadata는 거의 모두 동적으로 할당됩니다. 고정 위치에 있는 metadata는 allocation-group header인 SB, AGF, AGFL, AGI뿐이며, 나머지 metadata structure는 filesystem structure를 여러 방식으로 순회해 찾아야 합니다. Userspace tool이 validation과 repair를 위해 이미 이 작업을 수행하지만 검증할 수 있는 범위에는 한계가 있고, 이 한계가 지원 가능한 XFS filesystem 크기도 제한합니다.
Metadata 양이 늘 때 수동 구조 분석의 시간과 root-cause 식별 가능성이 어떻게 달라지는지 원문의 두 규모를 비교합니다.
따라서 PB-scale filesystem을 지원할 때 가장 중요한 관심사는 filesystem structure의 기본 forensic analysis에 필요한 시간과 노력을 최소화하는 것입니다.
.. SPDX-License-Identifier: GPL-2.0
.. _xfs_self_describing_metadata:
============================
XFS Self Describing Metadata
============================
Introduction
============
The largest scalability problem facing XFS is not one of algorithmic
scalability, but of verification of the filesystem structure. Scalabilty of the
structures and indexes on disk and the algorithms for iterating them are
adequate for supporting PB scale filesystems with billions of inodes, however it
is this very scalability that causes the verification problem.
Almost all metadata on XFS is dynamically allocated. The only fixed location
metadata is the allocation group headers (SB, AGF, AGFL and AGI), while all
other metadata structures need to be discovered by walking the filesystem
structure in different ways. While this is already done by userspace tools for
validating and repairing the structure, there are limits to what they can
verify, and this in turn limits the supportable size of an XFS filesystem.
For example, it is entirely possible to manually use xfs_db and a bit of
scripting to analyse the structure of a 100TB filesystem when trying to
determine the root cause of a corruption problem, but it is still mainly a
manual task of verifying that things like single bit errors or misplaced writes
weren't the ultimate cause of a corruption event. It may take a few hours to a
few days to perform such forensic analysis, so for at this scale root cause
analysis is entirely possible.
However, if we scale the filesystem up to 1PB, we now have 10x as much metadata
to analyse and so that analysis blows out towards weeks/months of forensic work.
Most of the analysis work is slow and tedious, so as the amount of analysis goes
up, the more likely that the cause will be lost in the noise. Hence the primary
concern for supporting PB scale filesystems is minimising the time and effort
required for basic forensic analysis of the filesystem structure.
Self-describing metadata: 식별과 무결성
40-95기존 metadata format의 문제는 metadata block의 magic number 외에는 그 block이 무엇이어야 하는지 식별할 방법이 없다는 점입니다. 심지어 올바른 위치에 있는지도 알 수 없습니다. 즉 metadata block 하나를 고립시켜 보고 '이곳에 있어야 하며 content가 유효하다'고 판단할 수 없습니다.
Forensic analysis 시간 대부분은 metadata value가 범위 안에는 있어 자동 검사를 통과하지만 실제로는 올바르지 않은 경우를 찾는 기본 검증에 쓰입니다. Btree sibling pointer가 loop를 만드는 것과 같은 cross-linked block list의 형성 과정을 이해하는 일이 corruption 원인을 파악하는 핵심이지만, 사후에는 block이 서로 어떤 순서로 연결되었거나 disk에 기록되었는지 알 수 없습니다.
그러므로 분석에서 무시해도 될 만큼 metadata가 온전한지를 빠르게 판단할 수 있도록 더 많은 정보를 metadata에 기록해야 합니다. 모든 오류를 막을 수는 없지만 흔한 오류 유형을 쉽게 탐지할 수는 있으며, 이것이 self-describing metadata의 개념입니다.
Block 자체만으로 type과 integrity를 판정하기 위해 필요한 식별·format·checksum 정보를 정리합니다.
Self-describing metadata의 첫 번째 근본 요구사항은 metadata object가 well-known location에 어떤 형태의 unique identifier를 포함하는 것입니다. 이를 통해 block의 예상 content를 식별하고 object를 parse·verify할 수 있습니다. Object 안의 metadata type을 독립적으로 식별할 수 없다면 metadata가 자신을 제대로 설명한다고 할 수 없습니다.
다행히 대부분의 XFS metadata에는 이미 magic number가 있습니다. 식별 magic이 없는 것은 AGFL, remote symlink, remote attribute block뿐입니다. 이 object들의 ondisk format에 식별 정보를 추가하고 magic number를 바꾸면 self-identifying format을 구분할 수 있습니다. 기존 magic number면 self-identifying metadata가 아니고, 새 magic number면 runtime·forensic analysis·repair에서 훨씬 폭넓은 자동 검증을 수행할 수 있습니다.
Self-describing metadata는 무엇보다 전체 integrity check를 갖춰야 합니다. 외부 영향으로 metadata가 변경되지 않았음을 확인할 수 없다면 신뢰할 수 없으므로 metadata block에 CRC32c validation을 추가합니다. Block이 의도한 metadata를 담고 있음을 확인하면 많은 수동 검증 작업을 생략할 수 있습니다.
XFS metadata의 최대 길이는 64KiB이므로 32-bit CRC는 metadata block의 multi-bit error를 탐지하기에 충분합니다. CRC32c는 일반 CPU에서 hardware acceleration도 지원되어 빠릅니다. 가능한 가장 강한 integrity check는 아니지만 요구에 충분하고 overhead가 작습니다. 더 큰 integrity field나 다른 algorithm은 CRC32c보다 실질적인 이점을 주지 않으면서 복잡성만 크게 늘리므로 integrity-checking mechanism을 변경하는 장치는 두지 않습니다.
Self Describing Metadata
========================
One of the problems with the current metadata format is that apart from the
magic number in the metadata block, we have no other way of identifying what it
is supposed to be. We can't even identify if it is the right place. Put simply,
you can't look at a single metadata block in isolation and say "yes, it is
supposed to be there and the contents are valid".
Hence most of the time spent on forensic analysis is spent doing basic
verification of metadata values, looking for values that are in range (and hence
not detected by automated verification checks) but are not correct. Finding and
understanding how things like cross linked block lists (e.g. sibling
pointers in a btree end up with loops in them) are the key to understanding what
went wrong, but it is impossible to tell what order the blocks were linked into
each other or written to disk after the fact.
Hence we need to record more information into the metadata to allow us to
quickly determine if the metadata is intact and can be ignored for the purpose
of analysis. We can't protect against every possible type of error, but we can
ensure that common types of errors are easily detectable. Hence the concept of
self describing metadata.
The first, fundamental requirement of self describing metadata is that the
metadata object contains some form of unique identifier in a well known
location. This allows us to identify the expected contents of the block and
hence parse and verify the metadata object. IF we can't independently identify
the type of metadata in the object, then the metadata doesn't describe itself
very well at all!
Luckily, almost all XFS metadata has magic numbers embedded already - only the
AGFL, remote symlinks and remote attribute blocks do not contain identifying
magic numbers. Hence we can change the on-disk format of all these objects to
add more identifying information and detect this simply by changing the magic
numbers in the metadata objects. That is, if it has the current magic number,
the metadata isn't self identifying. If it contains a new magic number, it is
self identifying and we can do much more expansive automated verification of the
metadata object at runtime, during forensic analysis or repair.
As a primary concern, self describing metadata needs some form of overall
integrity checking. We cannot trust the metadata if we cannot verify that it has
not been changed as a result of external influences. Hence we need some form of
integrity check, and this is done by adding CRC32c validation to the metadata
block. If we can verify the block contains the metadata it was intended to
contain, a large amount of the manual verification work can be skipped.
CRC32c was selected as metadata cannot be more than 64k in length in XFS and
hence a 32 bit CRC is more than sufficient to detect multi-bit errors in
metadata blocks. CRC32c is also now hardware accelerated on common CPUs so it is
fast. So while CRC32c is not the strongest of possible integrity checks that
could be used, it is more than sufficient for our needs and has relatively
little overhead. Adding support for larger integrity fields and/or algorithms
does really provide any extra value over CRC32c, but it does add a lot of
complexity and so there is no provision for changing the integrity checking
mechanism.
Location, owner, LSN 정보
96-147Self-describing metadata는 다른 metadata를 보지 않고도 block이 올바른 위치에 있는지 검증할 만큼 충분한 location information을 포함해야 합니다. Block number만으로는 misdirected write를 막기에 부족합니다. Write가 잘못된 LUN으로 향하면 다른 filesystem의 '올바른 block'에 기록될 수 있으므로 location information에는 block number와 filesystem identifier가 모두 필요합니다.
Forensic analysis에서 또 하나의 핵심은 metadata block의 owner를 아는 것입니다. Type·location·유효성·최근 수정 시점을 알아도 owner가 없으면 연관 metadata를 찾아 corruption 범위를 결정하기 어렵습니다. 예를 들어 extent-btree object가 어느 inode 소유인지 모르면 filesystem 전체를 순회해야 하고, corruption 때문에 owner를 찾을 수 없는 orphan block이면 영향 범위를 알 수 없습니다. Owner field가 있으면 즉시 top-down validation으로 문제 범위를 판단할 수 있습니다.
Metadata type마다 owner identifier가 다릅니다. Directory, attribute, extent-tree block은 inode가 소유하지만 free-space btree block은 allocation group이 소유합니다. 따라서 owner field의 크기와 content는 metadata-object type에 따라 결정됩니다. Owner information은 free-space btree block이 잘못된 AG에 기록된 것과 같은 misplaced write도 식별할 수 있습니다.
Block 자체가 제공해야 하는 위치·소유권·시간 정보와 이를 통해 탐지하는 문제입니다.
Self-describing metadata에는 filesystem에 기록된 시점의 표시도 필요합니다. Corrupted metadata block 집합의 modification time을 연관시키면 corruption들이 서로 관련되었는지, 최종 failure까지 여러 corruption event가 있었는지, runtime verification이 놓친 corruption이 있는지를 판단할 수 있습니다.
예를 들어 owner가 metadata object를 아직 참조할 때 해당 block이 free space여야 하는지 allocated 상태여야 하는지는, 그 block을 포함한 free-space btree block과 metadata object 자체의 마지막 write 시점을 비교해 판단할 수 있습니다. Free-space block이 object와 owner보다 최근이면 그 block은 owner에서 제거됐어야 할 가능성이 매우 큽니다.
이 written timestamp를 제공하기 위해 각 metadata block에는 자신을 가장 최근에 수정한 transaction의 Log Sequence Number(LSN)를 기록합니다. LSN은 filesystem 수명 동안 계속 증가하고 `xfs_repair`를 실행할 때만 reset됩니다. LSN으로 corrupted metadata가 같은 log checkpoint에 속했는지, disk의 첫 corruption과 마지막 corruption 사이에 얼마나 많은 modification이 있었는지, corruption 기록과 탐지 사이에 얼마나 수정되었는지를 추정할 수 있습니다.
Self describing metadata needs to contain enough information so that the
metadata block can be verified as being in the correct place without needing to
look at any other metadata. This means it needs to contain location information.
Just adding a block number to the metadata is not sufficient to protect against
mis-directed writes - a write might be misdirected to the wrong LUN and so be
written to the "correct block" of the wrong filesystem. Hence location
information must contain a filesystem identifier as well as a block number.
Another key information point in forensic analysis is knowing who the metadata
block belongs to. We already know the type, the location, that it is valid
and/or corrupted, and how long ago that it was last modified. Knowing the owner
of the block is important as it allows us to find other related metadata to
determine the scope of the corruption. For example, if we have a extent btree
object, we don't know what inode it belongs to and hence have to walk the entire
filesystem to find the owner of the block. Worse, the corruption could mean that
no owner can be found (i.e. it's an orphan block), and so without an owner field
in the metadata we have no idea of the scope of the corruption. If we have an
owner field in the metadata object, we can immediately do top down validation to
determine the scope of the problem.
Different types of metadata have different owner identifiers. For example,
directory, attribute and extent tree blocks are all owned by an inode, while
freespace btree blocks are owned by an allocation group. Hence the size and
contents of the owner field are determined by the type of metadata object we are
looking at. The owner information can also identify misplaced writes (e.g.
freespace btree block written to the wrong AG).
Self describing metadata also needs to contain some indication of when it was
written to the filesystem. One of the key information points when doing forensic
analysis is how recently the block was modified. Correlation of set of corrupted
metadata blocks based on modification times is important as it can indicate
whether the corruptions are related, whether there's been multiple corruption
events that lead to the eventual failure, and even whether there are corruptions
present that the run-time verification is not detecting.
For example, we can determine whether a metadata object is supposed to be free
space or still allocated if it is still referenced by its owner by looking at
when the free space btree block that contains the block was last written
compared to when the metadata object itself was last written. If the free space
block is more recent than the object and the object's owner, then there is a
very good chance that the block should have been removed from the owner.
To provide this "written timestamp", each metadata block gets the Log Sequence
Number (LSN) of the most recent transaction it was modified on written into it.
This number will always increase over the life of the filesystem, and the only
thing that resets it is running xfs_repair on the filesystem. Further, by use of
the LSN we can tell if the corrupted metadata all belonged to the same log
checkpoint and hence have some idea of how much modification occurred between
the first and last instance of corrupt metadata on disk and, further, how much
modification occurred between the corruption being written and when it was
detected.
Runtime validation
148-188Self-describing metadata validation은 runtime의 두 지점, 즉 disk read가 성공한 직후와 write I/O를 제출하기 직전에 수행됩니다.
Verification은 modification process와 독립적으로 수행되는 완전한 stateless 검사입니다. Metadata가 자신이 주장하는 type인지, field가 범위 안에 있고 내부적으로 일관적인지만 확인합니다. Operational state가 강제하는 제한이나 block 사이 관계의 corruption, 예를 들어 손상된 sibling-pointer list까지 모두 잡을 수는 없습니다. 따라서 main code에는 여전히 stateful checking이 필요하지만 대부분의 per-field validation은 verifier가 담당합니다.
Caller의 expected type에서 object-specific validation까지 진행하며 실패를 EFSCORRUPTED로 전달합니다.
Read verification이 실패하면 읽은 object를 `EFSCORRUPTED`로 표시합니다. Caller는 I/O error와 마찬가지로 이 error를 받아야 하며, verification error에 특별한 조치가 필요하면 `EFSCORRUPTED` 값을 구분해 처리할 수 있습니다. 상위 layer에서 더 세밀한 error 분류가 필요하면 서로 다른 error number를 추가할 수 있습니다.
Write verification은 read verification의 반대 순서입니다. 먼저 object를 폭넓게 검증하고 정상이라면 마지막 modification의 LSN을 갱신합니다. 그다음 CRC를 계산해 object에 넣은 후에만 write I/O를 계속합니다. 이 과정에서 error가 발생하면 상위 layer가 처리할 수 있도록 buffer를 다시 `EFSCORRUPTED`로 표시합니다.
Runtime Validation
==================
Validation of self-describing metadata takes place at runtime in two places:
- immediately after a successful read from disk
- immediately prior to write IO submission
The verification is completely stateless - it is done independently of the
modification process, and seeks only to check that the metadata is what it says
it is and that the metadata fields are within bounds and internally consistent.
As such, we cannot catch all types of corruption that can occur within a block
as there may be certain limitations that operational state enforces of the
metadata, or there may be corruption of interblock relationships (e.g. corrupted
sibling pointer lists). Hence we still need stateful checking in the main code
body, but in general most of the per-field validation is handled by the
verifiers.
For read verification, the caller needs to specify the expected type of metadata
that it should see, and the IO completion process verifies that the metadata
object matches what was expected. If the verification process fails, then it
marks the object being read as EFSCORRUPTED. The caller needs to catch this
error (same as for IO errors), and if it needs to take special action due to a
verification error it can do so by catching the EFSCORRUPTED error value. If we
need more discrimination of error type at higher levels, we can define new
error numbers for different errors as necessary.
The first step in read verification is checking the magic number and determining
whether CRC validating is necessary. If it is, the CRC32c is calculated and
compared against the value stored in the object itself. Once this is validated,
further checks are made against the location information, followed by extensive
object specific metadata validation. If any of these checks fail, then the
buffer is considered corrupt and the EFSCORRUPTED error is set appropriately.
Write verification is the opposite of the read verification - first the object
is extensively verified and if it is OK we then update the LSN from the last
modification made to the object, After this, we calculate the CRC and insert it
into the object. Once this is done the write IO is allowed to continue. If any
error occurs during this process, the buffer is again marked with a EFSCORRUPTED
error for the higher layers to catch.
Ondisk structure와 verifier
189-329일반적인 ondisk structure는 `struct xfs_ondisk_hdr`와 같은 정보를 포함해야 합니다.
원문 C structure의 여섯 field와 logging 여부·의미를 보존합니다.
Metadata에 따라 이 정보는 content와 분리된 header structure에 들어갈 수도 있고 기존 structure 곳곳에 분산될 수도 있습니다. Superblock과 AG header처럼 이미 일부 정보를 가진 metadata에는 후자의 방식이 적용됩니다.
다른 metadata는 형식이 달라도 일반적으로 같은 수준의 정보를 제공합니다. Short-btree block은 32-bit owner인 AG number와 32-bit location block number를 사용합니다. 둘을 합치면 위 structure의 `owner`와 `blkno`와 같은 정보를 제공하면서 disk 공간을 8 byte 덜 씁니다. Directory·attribute node block은 16-bit magic number를 쓰며, magic이 든 header에 다른 정보도 있으므로 추가 metadata header가 전체 format을 바꿉니다.
일반적인 buffer read verifier인 `xfs_foo_read_verify`는 `XFS_FOO_CRC_OFF`로 CRC field offset을 정의합니다. Superblock feature bit로 filesystem의 CRC 활성화 여부를 확인하고, CRC가 필요하면 `xfs_verify_cksum`으로 검증합니다. CRC가 정상이거나 필요하지 않을 때 `xfs_foo_verify`로 block의 실제 content를 검사합니다. 실패하면 `XFS_CORRUPTION_ERROR`를 기록하고 `xfs_buf_ioerror`로 `EFSCORRUPTED`를 설정합니다.
Block format을 magic number 하나로 구분할 수 있는지에 따른 두 `xfs_foo_verify` 형태를 비교합니다.
Verifier 형태는 magic number로 block format을 판정할 수 있는지에 따라 달라집니다. Format을 별도 magic으로 구분하지 않는 경우 superblock CRC feature를 참고하고, 서로 다른 magic number가 있다면 object의 magic 자체로 CRC-era format과 legacy format을 나눕니다. 어느 경우든 magic·UUID·location·owner를 확인한 뒤 object-specific check를 수행합니다.
Write verifier `xfs_foo_write_verify`는 read verifier와 매우 비슷하지만 순서가 반대입니다. 먼저 `xfs_foo_verify`로 object를 검사하고 실패하면 corruption을 기록해 `EFSCORRUPTED`를 설정한 뒤 반환합니다. CRC가 비활성화되어 있으면 그대로 끝내며, 활성화되어 있고 buffer log item `bip`가 있으면 `bip->bli_item.li_lsn`을 ondisk header의 `lsn`에 넣습니다. 마지막으로 `xfs_update_cksum`으로 CRC를 갱신합니다.
따라서 metadata를 더 진행하기 전에 memory에서 수정되는 동안 생긴 corruption까지 internal structure 검증으로 탐지합니다. Metadata가 정상이고 CRC가 활성화되어 있으면 마지막 modification LSN과 CRC를 갱신한 뒤 I/O를 발행할 수 있습니다.
Structures
==========
A typical on-disk structure needs to contain the following information::
struct xfs_ondisk_hdr {
__be32 magic; /* magic number */
__be32 crc; /* CRC, not logged */
uuid_t uuid; /* filesystem identifier */
__be64 owner; /* parent object */
__be64 blkno; /* location on disk */
__be64 lsn; /* last modification in log, not logged */
};
Depending on the metadata, this information may be part of a header structure
separate to the metadata contents, or may be distributed through an existing
structure. The latter occurs with metadata that already contains some of this
information, such as the superblock and AG headers.
Other metadata may have different formats for the information, but the same
level of information is generally provided. For example:
- short btree blocks have a 32 bit owner (ag number) and a 32 bit block
number for location. The two of these combined provide the same
information as @owner and @blkno in eh above structure, but using 8
bytes less space on disk.
- directory/attribute node blocks have a 16 bit magic number, and the
header that contains the magic number has other information in it as
well. hence the additional metadata headers change the overall format
of the metadata.
A typical buffer read verifier is structured as follows::
#define XFS_FOO_CRC_OFF offsetof(struct xfs_ondisk_hdr, crc)
static void
xfs_foo_read_verify(
struct xfs_buf *bp)
{
struct xfs_mount *mp = bp->b_mount;
if ((xfs_sb_version_hascrc(&mp->m_sb) &&
!xfs_verify_cksum(bp->b_addr, BBTOB(bp->b_length),
XFS_FOO_CRC_OFF)) ||
!xfs_foo_verify(bp)) {
XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, mp, bp->b_addr);
xfs_buf_ioerror(bp, EFSCORRUPTED);
}
}
The code ensures that the CRC is only checked if the filesystem has CRCs enabled
by checking the superblock of the feature bit, and then if the CRC verifies OK
(or is not needed) it verifies the actual contents of the block.
The verifier function will take a couple of different forms, depending on
whether the magic number can be used to determine the format of the block. In
the case it can't, the code is structured as follows::
static bool
xfs_foo_verify(
struct xfs_buf *bp)
{
struct xfs_mount *mp = bp->b_mount;
struct xfs_ondisk_hdr *hdr = bp->b_addr;
if (hdr->magic != cpu_to_be32(XFS_FOO_MAGIC))
return false;
if (!xfs_sb_version_hascrc(&mp->m_sb)) {
if (!uuid_equal(&hdr->uuid, &mp->m_sb.sb_uuid))
return false;
if (bp->b_bn != be64_to_cpu(hdr->blkno))
return false;
if (hdr->owner == 0)
return false;
}
/* object specific verification checks here */
return true;
}
If there are different magic numbers for the different formats, the verifier
will look like::
static bool
xfs_foo_verify(
struct xfs_buf *bp)
{
struct xfs_mount *mp = bp->b_mount;
struct xfs_ondisk_hdr *hdr = bp->b_addr;
if (hdr->magic == cpu_to_be32(XFS_FOO_CRC_MAGIC)) {
if (!uuid_equal(&hdr->uuid, &mp->m_sb.sb_uuid))
return false;
if (bp->b_bn != be64_to_cpu(hdr->blkno))
return false;
if (hdr->owner == 0)
return false;
} else if (hdr->magic != cpu_to_be32(XFS_FOO_MAGIC))
return false;
/* object specific verification checks here */
return true;
}
Write verifiers are very similar to the read verifiers, they just do things in
the opposite order to the read verifiers. A typical write verifier::
static void
xfs_foo_write_verify(
struct xfs_buf *bp)
{
struct xfs_mount *mp = bp->b_mount;
struct xfs_buf_log_item *bip = bp->b_fspriv;
if (!xfs_foo_verify(bp)) {
XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, mp, bp->b_addr);
xfs_buf_ioerror(bp, EFSCORRUPTED);
return;
}
if (!xfs_sb_version_hascrc(&mp->m_sb))
return;
if (bip) {
struct xfs_ondisk_hdr *hdr = bp->b_addr;
hdr->lsn = cpu_to_be64(bip->bli_item.li_lsn);
}
xfs_update_cksum(bp->b_addr, BBTOB(bp->b_length), XFS_FOO_CRC_OFF);
}
This will verify the internal structure of the metadata before we go any
further, detecting corruptions that have occurred as the metadata has been
modified in memory. If the metadata verifies OK, and CRCs are enabled, we then
update the LSN field (when it was last modified) and calculate the CRC on the
metadata. Once this is done, we can issue the IO.
Inode와 dquot
330-353Inode와 dquot는 특별한 경우입니다. Object별 CRC와 self-identifier를 갖지만 buffer 하나에 여러 object가 packed되어 있습니다. 따라서 object별 verification과 CRC 계산에 per-buffer verifier를 사용하지 않습니다. Per-buffer verifier는 buffer가 inode 또는 dquot를 담는지, 예상 위치마다 magic number가 있는지만 기본적으로 식별합니다. 나머지 CRC와 verification은 각 inode를 buffer에서 읽거나 다시 쓸 때 수행합니다.
Verifier와 identifier check의 구조는 앞의 buffer code와 매우 비슷하고 호출 위치만 다릅니다. 예를 들어 inode read verification은 buffer에서 inode를 처음 꺼내 `struct xfs_inode`를 생성할 때 `xfs_inode_from_disk()`에서 수행됩니다. Writeback 시 inode는 이미 `xfs_iflush_int`에서 폭넓게 검증되므로, 여기서는 buffer로 다시 copy할 때 inode에 LSN과 CRC를 추가하기만 하면 됩니다.
주의할 미해결 문제도 있습니다. Inode unlinked-list modification은 inode CRC를 다시 계산하지 않으며, unlink 중에도 log recovery 중에도 unlinked-list 변경은 CRC를 검사하거나 갱신하지 않습니다. 지금까지 발견되지 않았고 즉각적인 문제는 아닐 수 있으며 repair가 불평할 가능성이 있지만, 수정해야 합니다.
Inodes and Dquots
=================
Inodes and dquots are special snowflakes. They have per-object CRC and
self-identifiers, but they are packed so that there are multiple objects per
buffer. Hence we do not use per-buffer verifiers to do the work of per-object
verification and CRC calculations. The per-buffer verifiers simply perform basic
identification of the buffer - that they contain inodes or dquots, and that
there are magic numbers in all the expected spots. All further CRC and
verification checks are done when each inode is read from or written back to the
buffer.
The structure of the verifiers and the identifiers checks is very similar to the
buffer code described above. The only difference is where they are called. For
example, inode read verification is done in xfs_inode_from_disk() when the inode
is first read out of the buffer and the struct xfs_inode is instantiated. The
inode is already extensively verified during writeback in xfs_iflush_int, so the
only addition here is to add the LSN and CRC to the inode as it is copied back
into the buffer.
XXX: inode unlinked list modification doesn't recalculate the inode CRC! None of
the unlinked list modifications check or update CRCs, neither during unlink nor
log recovery. So, it's gone unnoticed until now. This won't matter immediately -
repair will probably complain about it - but it needs to be fixed.
요약·해설
xfs-self-describing-metadata.rst:1-353PB-scale XFS에서는 metadata 양 때문에 corruption의 root cause를 수동 분석하는 시간이 급격히 늘어납니다. Self-describing metadata는 각 block이 다른 structure를 참조하지 않고도 자신의 type, filesystem, 위치, owner, 최근 modification과 integrity를 설명하게 해 이 비용을 줄입니다.
Runtime verifier는 read 직후 CRC·location·object field를 검사하고, write 직전에는 internal structure를 검증한 뒤 LSN과 CRC를 갱신합니다. Inode와 dquot처럼 buffer 하나에 여러 object가 들어가는 형식은 per-object verifier를 사용합니다.
Block 자체만으로 식별·위치·소유권·시간·무결성을 검증하기 위한 정보입니다.