• Jingbo Xu's avatar
    erofs: update on-disk format for xattr name filter · 3f339920
    Jingbo Xu authored
    The xattr name bloom filter feature is going to be introduced to speed
    up the negative xattr lookup, e.g. system.posix_acl_[access|default]
    lookup when running "ls -lR" workload.
    
    There are some commonly used extended attributes (n) and the total
    number of these is approximately 30.
    
    	trusted.overlay.opaque
    	trusted.overlay.redirect
    	trusted.overlay.origin
    	trusted.overlay.impure
    	trusted.overlay.nlink
    	trusted.overlay.upper
    	trusted.overlay.metacopy
    	trusted.overlay.protattr
    	user.overlay.opaque
    	user.overlay.redirect
    	user.overlay.origin
    	user.overlay.impure
    	user.overlay.nlink
    	user.overlay.upper
    	user.overlay.metacopy
    	user.overlay.protattr
    	security.evm
    	security.ima
    	security.selinux
    	security.SMACK64
    	security.SMACK64IPIN
    	security.SMACK64IPOUT
    	security.SMACK64EXEC
    	security.SMACK64TRANSMUTE
    	security.SMACK64MMAP
    	security.apparmor
    	security.capability
    	system.posix_acl_access
    	system.posix_acl_default
    	user.mime_type
    
    Given the number of bits of the bloom filter (m) is 32, the optimal
    value for the number of the hash functions (k) is 1 (ln2 * m/n = 0.74).
    
    The single hash function is implemented as:
    
    	xxh32(name, strlen(name), EROFS_XATTR_FILTER_SEED + index)
    
    where `index` represents the index of corresponding predefined short name
    prefix, while `name` represents the name string after stripping the above
    predefined name prefix.
    
    The constant magic number EROFS_XATTR_FILTER_SEED, i.e. 0x25BBE08F, is
    used to give a better spread when mapping these 30 extended attributes
    into 32-bit bloom filter as:
    
    	bit  0: security.ima
    	bit  1:
    	bit  2: trusted.overlay.nlink
    	bit  3:
    	bit  4: user.overlay.nlink
    	bit  5: trusted.overlay.upper
    	bit  6: user.overlay.origin
    	bit  7: trusted.overlay.protattr
    	bit  8: security.apparmor
    	bit  9: user.overlay.protattr
    	bit 10: user.overlay.opaque
    	bit 11: security.selinux
    	bit 12: security.SMACK64TRANSMUTE
    	bit 13: security.SMACK64
    	bit 14: security.SMACK64MMAP
    	bit 15: user.overlay.impure
    	bit 16: security.SMACK64IPIN
    	bit 17: trusted.overlay.redirect
    	bit 18: trusted.overlay.origin
    	bit 19: security.SMACK64IPOUT
    	bit 20: trusted.overlay.opaque
    	bit 21: system.posix_acl_default
    	bit 22:
    	bit 23: user.mime_type
    	bit 24: trusted.overlay.impure
    	bit 25: security.SMACK64EXEC
    	bit 26: user.overlay.redirect
    	bit 27: user.overlay.upper
    	bit 28: security.evm
    	bit 29: security.capability
    	bit 30: system.posix_acl_access
    	bit 31: trusted.overlay.metacopy, user.overlay.metacopy
    
    h_name_filter is introduced to the on-disk per-inode xattr header to
    place the corresponding xattr name filter, where bit value 1 indicates
    non-existence for compatibility.
    
    This feature is indicated by EROFS_FEATURE_COMPAT_XATTR_FILTER
    compatible feature bit.
    
    Reserve one byte in on-disk superblock as the on-disk format for xattr
    name filter may change in the future.  With this flag we don't need
    bothering these compatible bits again at that time.
    Suggested-by: default avatarAlexander Larsson <alexl@redhat.com>
    Signed-off-by: default avatarJingbo Xu <jefflexu@linux.alibaba.com>
    Reviewed-by: default avatarGao Xiang <hsiangkao@linux.alibaba.com>
    Reviewed-by: default avatarChao Yu <chao@kernel.org>
    Link: https://lore.kernel.org/r/20230722094538.11754-2-jefflexu@linux.alibaba.comSigned-off-by: default avatarGao Xiang <hsiangkao@linux.alibaba.com>
    3f339920
erofs_fs.h 14.7 KB