Ext4 Encoding and Case-insensitive support
Subsystems (5)
v5 cover Ext4 Encoding and Case-insensitive support
Hi Ted,
Following Linus comments, this version is back as an RFC, in order to discuss the normalization method used. At a first glance, you will notice the series got a lot smaller, with the separation of unicode code from the NLS subsystem, as Linus requested. The ext4 parts are pretty much the same, with only the addition of a verification in ext4_feature_set_ok() to fail encoding mounts when without CONFIG_UNICODE on newer kernels.
The main change presented here is a proposal to migrate the normalization method from NFKD to NFD. After our discussions, and reviewing other operating systems and languages aspects, I am more convinced that canonical decomposition is more viable solution than compatibility decomposition, because it doesn't ignore eliminate any semantic meaning, like the definitive case of superscript numbers. NFD is also the documented method used by HFS+ and APFS, so there is precedent. Notice however, that as far as my research goes, APFS doesn't completely follows NFD, and in some cases, like <compat> flags, it actually does NFKD, but not in others (<fraction>), where it applies the canonical form. We take a more consistent approach and always do plain NFD.
This RFC, therefore, aims to resume/start conversation with some stalkeholders that may have something to say regarding the normalization method used. I added people from SMB, NFS and FS development who might be interested on this.
Regarding Casefold, I am unsure whether Casefold Common + Full still makes sense after migrating from the compatibility to the canonical form. While Casefold Full, by definition, addresses cases where the casefolding grows in size, like the casefold of the german eszett to SS, it also is responsible for folding smallcase ligatures without a corresponding uppercase to their compatible counterpart. Which means that on -F directories, o_f_f_i_c_e and o_ff_i_c_e will differ, while on +F directories they will match. This seems unaceptable to me, suggesting that we should start to use Common + Simple instead of Common
+ Full, but I would like more input on what seems more reasonable to you.
After we decide on this, I will be sending new patches to update e2fsprogs to the agreed method and remove the normalization/casefold type flags (EXT4_UTF8_NORMALIZATION_TYPE_NFKD, EXT4_UTF8_CASEFOLD_TYPE_NFKDCF), before actually proposing the current patch series for inclusion in the kernel.
Practical things, w.r.t. this patch series:
- As usual, the UCD files are not part of the series, because they would bounce. To test this one would need to fetch the files as explained in the commit message.
- If you prefer, you can checkout from
https://gitlab.collabora.com/krisman/linux -b ext4-ci-directory-no-nls
- More details on the design decisions restricted to ext4 are available in the corresponding commit messages.
Thanks for keeping up with this.
Gabriel Krisman Bertazi (7):
unicode: Implement higher level API for string handling
unicode: Introduce test module for normalized utf8 implementation
MAINTAINERS: Add Unicode subsystem entry
ext4: Include encoding information in the superblock
ext4: Support encoding-aware file name lookups
ext4: Implement EXT4_CASEFOLD_FL flag
docs: ext4.rst: Document encoding and case-insensitive
Olaf Weber (4):
unicode: Add unicode character database files
scripts: add trie generator for UTF-8
unicode: Introduce code for UTF-8 normalization
unicode: reduce the size of utf8data[]
Documentation/admin-guide/ext4.rst | 41 + MAINTAINERS | 6 + fs/Kconfig | 1 + fs/Makefile | 1 + fs/ext4/dir.c | 43 + fs/ext4/ext4.h | 42 +- fs/ext4/hash.c | 38 +- fs/ext4/ialloc.c | 2 +- fs/ext4/inline.c | 2 +- fs/ext4/inode.c | 4 +- fs/ext4/ioctl.c | 18 + fs/ext4/namei.c | 104 +- fs/ext4/super.c | 91 + fs/unicode/Kconfig | 13 + fs/unicode/Makefile | 22 + fs/unicode/ucd/README | 33 + fs/unicode/utf8-core.c | 183 ++ fs/unicode/utf8-norm.c | 797 +++++++ fs/unicode/utf8-selftest.c | 320 +++ fs/unicode/utf8n.h | 117 + include/linux/fs.h | 2 + include/linux/unicode.h | 30 + scripts/Makefile | 1 + scripts/mkutf8data.c | 3418 ++++++++++++++++++++++++++++ 24 files changed, 5307 insertions(+), 22 deletions(-) create mode 100644 fs/unicode/Kconfig create mode 100644 fs/unicode/Makefile create mode 100644 fs/unicode/ucd/README create mode 100644 fs/unicode/utf8-core.c create mode 100644 fs/unicode/utf8-norm.c create mode 100644 fs/unicode/utf8-selftest.c create mode 100644 fs/unicode/utf8n.h create mode 100644 include/linux/unicode.h create mode 100644 scripts/mkutf8data.c
Signature · 1 line
2.20.1
RFC PATCH v5 1/11 unicode: Add unicode character database files
From: Olaf Weber <[email protected]>
Add files from the Unicode Character Database, version 11.0, to the source. A helper program that generates a trie used for normalization from these files is part of a separate commit.
- Notes on the update from 8.0.0 and 11.0:
The structure of ucd files and special cases have not experienced any changes between versions 8.0.0 and 11.0.0. 8.0.0 saw the addition of Cherokee LC characters, which is an interesting case for case-folding. The update is accompanied by new tests on the test_ucd module to catch specific cases. No changes to mkutf8data script was required for the update.
The actual files are not part of the commit submitted to the list because they are to big and would bounce. Still, they can be obtained by the following script:
FILES="CaseFolding.txt DerivedAge.txt extracted/DerivedCombiningClass.txt
DerivedCoreProperties.txt NormalizationCorrections.txt NormalizationTest.txt UnicodeData.txt"
VERSION=11.0.0 BASE=http://www.unicode.org/Public/${VERSION}/ucd
for i in ${FILES} ; do
wget "${BASE}/$i" -O fs/unicode/ucd/$(basename ${i} .txt)-${VERSION}.txt
done
--- fs/unicode/ucd/README | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+) create mode 100644 fs/unicode/ucd/README
fs/unicode/ucd/README new file +33 -0
@@ -0,0 +1,33 @@ +The files in this directory are part of the Unicode Character Database +for version 11.0.0 of the Unicode standard. + +The full set of files can be found here: + + http://www.unicode.org/Public/11.0.0/ucd/ + +The latest released version of the UCD can be found here: + + http://www.unicode.org/Public/UCD/latest/ + +The files in this directory are identical, except that they have been +renamed with a suffix indicating the unicode version. + +Individual source links: + + http://www.unicode.org/Public/11.0.0/ucd/CaseFolding.txt + http://www.unicode.org/Public/11.0.0/ucd/DerivedAge.txt + http://www.unicode.org/Public/11.0.0/ucd/extracted/DerivedCombiningClass.txt + http://www.unicode.org/Public/11.0.0/ucd/DerivedCoreProperties.txt + http://www.unicode.org/Public/11.0.0/ucd/NormalizationCorrections.txt + http://www.unicode.org/Public/11.0.0/ucd/NormalizationTest.txt + http://www.unicode.org/Public/11.0.0/ucd/UnicodeData.txt + +md5sums + + 414436796cf097df55f798e1585448ee CaseFolding-11.0.0.txt + 6032a595fbb782694456491d86eecfac DerivedAge-11.0.0.txt + 3240997d671297ac754ab0d27577acf7 DerivedCombiningClass-11.0.0.txt + 2a4fe257d9d8184518e036194d2248ec DerivedCoreProperties-11.0.0.txt + 4e7d383fa0dd3cd9d49d64e5b7b7c9e0 NormalizationCorrections-11.0.0.txt + c9500c5b8b88e584469f056023ecc3f2 NormalizationTest-11.0.0.txt + acc291106c3758d2025f8d7bd5518bee UnicodeData-11.0.0.txt
Signature · 1 line
2.20.1
RFC PATCH v5 2/11 scripts: add trie generator for UTF-8
In reply to Gabriel Krisman BertaziFrom: Olaf Weber <[email protected]>
mkutf8data.c is the source for a program that generates utf8data.h, which contains the trie that utf8norm.c uses. The trie is generated from the Unicode 11.0.0 data files. The format of the utf8data[] table is described in utf8norm.c, which is added in the next patch.
--- fs/Kconfig | 1 + fs/Makefile | 1 + fs/unicode/Kconfig | 8 + fs/unicode/Makefile | 16 + scripts/Makefile | 1 + scripts/mkutf8data.c | 3189 ++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 3216 insertions(+) create mode 100644 fs/unicode/Kconfig create mode 100644 fs/unicode/Makefile create mode 100644 scripts/mkutf8data.c
fs/Kconfig +1 -0
@@ -313,5 +313,6 @@ endif # NETWORK_FILESYSTEMS source "fs/nls/Kconfig" source "fs/dlm/Kconfig" +source "fs/unicode/Kconfig" endmenu
fs/Makefile +1 -0
@@ -90,6 +90,7 @@ obj-$(CONFIG_EXPORTFS) += exportfs/ obj-$(CONFIG_NFSD) += nfsd/ obj-$(CONFIG_LOCKD) += lockd/ obj-$(CONFIG_NLS) += nls/ +obj-$(CONFIG_UNICODE) += unicode/ obj-$(CONFIG_SYSV_FS) += sysv/ obj-$(CONFIG_CIFS) += cifs/ obj-$(CONFIG_HPFS_FS) += hpfs/
fs/unicode/Kconfig new file +8 -0
@@ -0,0 +1,8 @@ +# +# UTF-8 normalization +# +config UNICODE + bool "UTF-8 normalization and casefolding support" + help + Say Y here to enable UTF-8 NFD normalization and NFD+CF casefolding + support.
fs/unicode/Makefile new file +16 -0
@@ -0,0 +1,16 @@ +# SPDX-License-Identifier: GPL-2.0 + +UNICODE_VERSION=11.0.0 + +$(obj)/utf8data.h: $(srctree)/$(src)/ucd/*.txt $(objtree)/scripts/mkutf8data FORCE + $(call cmd,mkutf8data) +quiet_cmd_mkutf8data = MKUTF8DATA $@ + cmd_mkutf8data = $(objtree)/scripts/mkutf8data \ + -a $(srctree)/$(src)/ucd/DerivedAge-$(UNICODE_VERSION).txt \ + -c $(srctree)/$(src)/ucd/DerivedCombiningClass-$(UNICODE_VERSION).txt \ + -p $(srctree)/$(src)/ucd/DerivedCoreProperties-$(UNICODE_VERSION).txt \ + -d $(srctree)/$(src)/ucd/UnicodeData-$(UNICODE_VERSION).txt \ + -f $(srctree)/$(src)/ucd/CaseFolding-$(UNICODE_VERSION).txt \ + -n $(srctree)/$(src)/ucd/NormalizationCorrections-$(UNICODE_VERSION).txt \ + -t $(srctree)/$(src)/ucd/NormalizationTest-$(UNICODE_VERSION).txt \ + -o $@
scripts/Makefile +1 -0
@@ -20,6 +20,7 @@ hostprogs-$(CONFIG_ASN1) += asn1_compiler hostprogs-$(CONFIG_MODULE_SIG) += sign-file hostprogs-$(CONFIG_SYSTEM_TRUSTED_KEYRING) += extract-cert hostprogs-$(CONFIG_SYSTEM_EXTRA_CERTIFICATE) += insert-sys-cert +hostprogs-$(CONFIG_UNICODE) += mkutf8data HOSTCFLAGS_sortextable.o = -I$(srctree)/tools/include HOSTCFLAGS_asn1_compiler.o = -I$(srctree)/include
scripts/mkutf8data.c new file +3189 -0
2,956 lines not on this page · raw message
The rest of this diff is not shown. View the raw message.
Signature · 1 line
2.20.1
Part of the diff is not shown here. View the raw message.
RFC PATCH v5 3/11 unicode: Introduce code for UTF-8 normalization
In reply to Gabriel Krisman BertaziFrom: Olaf Weber <[email protected]>
Supporting functions for UTF-8 normalization are in utf8norm.c with the header utf8norm.h. Two normalization forms are supported: nfdi and nfdicf.
nfdi:
- Apply unicode normalization form NFD.
- Remove any Default_Ignorable_Code_Point.
nfdicf:
- Apply unicode normalization form NFD.
- Remove any Default_Ignorable_Code_Point.
- Apply a full casefold (C + F).
For the purposes of the code, a string is valid UTF-8 if:
- The values encoded are 0x1..0x10FFFF.
- The surrogate codepoints 0xD800..0xDFFFF are not encoded.
- The shortest possible encoding is used for all values.
The supporting functions work on null-terminated strings (utf8 prefix) and on length-limited strings (utf8n prefix).
From the original SGI patch and for conformity with coding standards, the utf8data_t typedef was dropped, since it was just masking the struct keyword. On other occasions, namely utf8leaf_t and utf8trie_t, I decided to keep it, since they are simple pointers to memory buffers, and using uchars here wouldn't provide any more meaningful information.
From the original submission, we also converted from the compatibility form to canonical.
Changes since v4:
- Convert to canonical decomposition form.
Changes since RFC v1:
- utf8_version_is_supported receives maj, min and rev as separate arguments. (Olaf Weber)
--- fs/unicode/Makefile | 3 + fs/unicode/utf8-norm.c | 640 +++++++++++++++++++++++++++++++++++++++++ fs/unicode/utf8n.h | 112 ++++++++ 3 files changed, 755 insertions(+) create mode 100644 fs/unicode/utf8-norm.c create mode 100644 fs/unicode/utf8n.h
fs/unicode/Makefile +3 -0
@@ -2,6 +2,9 @@ UNICODE_VERSION=11.0.0 +obj-$(CONFIG_UNICODE) += utf8-norm.o + +$(obj)/utf8-norm.o: $(obj)/utf8data.h $(obj)/utf8data.h: $(srctree)/$(src)/ucd/*.txt $(objtree)/scripts/mkutf8data FORCE $(call cmd,mkutf8data) quiet_cmd_mkutf8data = MKUTF8DATA $@
fs/unicode/utf8-norm.c new file +640 -0
640 lines not on this page · raw message
fs/unicode/utf8n.h new file +112 -0
112 lines not on this page · raw message
Signature · 1 line
2.20.1
RFC PATCH v5 4/11 unicode: reduce the size of utf8data[]
In reply to Gabriel Krisman BertaziFrom: Olaf Weber <[email protected]>
Remove the Hangul decompositions from the utf8data trie, and do algorithmic decomposition to calculate them on the fly. To store the decomposition the caller of utf8lookup()/utf8nlookup() must provide a 12-byte buffer, which is used to synthesize a leaf with the decomposition. Trie size is reduced from 245kB to 90kB.
[Extract robustness fixes and merge back to original mkutf8data.c patch]
--- fs/unicode/utf8-norm.c | 191 ++++++++++++++++++++++--- fs/unicode/utf8n.h | 4 + scripts/mkutf8data.c | 307 +++++++++++++++++++++++++++++++++++------ 3 files changed, 443 insertions(+), 59 deletions(-)
fs/unicode/utf8-norm.c +171 -20
@@ -98,6 +98,38 @@ static inline int utf8clen(const char *s)return 1 + (c >=0xC0 ) + (c >=0xE0 ) + (c >=0xF0 ); } +/* +* Decode a 3-byte UTF-8 sequence. +*/ +static unsigned int +utf8decode3 (const char *str) +{ +unsigned int uc; + + uc = *str++ &0x0F ; + uc <<=6 ; + uc |= *str++ &0x3F ; + uc <<=6 ; + uc |= *str++ &0x3F ; + +return uc; +} + +/* +* Encode a 3-byte UTF-8 sequence. +*/ +static int +utf8encode3 (char *str,unsigned int val) +{ + str[2 ] = (val &0x3F ) |0x80 ; + val >>=6 ; + str[1 ] = (val &0x3F ) |0x80 ; + val >>=6 ; + str[0 ] = val |0xE0 ; + +return 3 ; +} +/* * utf8trie_t *
@@ -159,7 +191,8 @@ typedef const unsigned char utf8trie_t;* characters with the Default_Ignorable_Code_Point property. * These do affect normalization, as they all have CCC 0. * -* The decompositions in the trie have been fully expanded. +* The decompositions in the trie have been fully expanded, with the +* exception of Hangul syllables, which are decomposed algorithmically. * * Casefolding, if applicable, is also done using decompositions. *
@@ -179,6 +212,105 @@ typedef const unsigned char utf8leaf_t;#define STOPPER (0)#define DECOMPOSE (255) +/* Marker for hangul syllable decomposition. */ +#define HANGUL ((char)(255)) +/* Size of the synthesized leaf used for Hangul syllable decomposition. */ +#define UTF8HANGULLEAF (12) + +/* +* Hangul decomposition (algorithm from Section 3.12 of Unicode 6.3.0) +* +* AC00;<Hangul Syllable, First>;Lo;0;L;;;;;N;;;;; +* D7A3;<Hangul Syllable, Last>;Lo;0;L;;;;;N;;;;; +* +* SBase = 0xAC00 +* LBase = 0x1100 +* VBase = 0x1161 +* TBase = 0x11A7 +* LCount = 19 +* VCount = 21 +* TCount = 28 +* NCount = 588 (VCount * TCount) +* SCount = 11172 (LCount * NCount) +* +* Decomposition: +* SIndex = s - SBase +* +* LV (Canonical/Full) +* LIndex = SIndex / NCount +* VIndex = (Sindex % NCount) / TCount +* LPart = LBase + LIndex +* VPart = VBase + VIndex +* +* LVT (Canonical) +* LVIndex = (SIndex / TCount) * TCount +* TIndex = (Sindex % TCount) +* LVPart = SBase + LVIndex +* TPart = TBase + TIndex +* +* LVT (Full) +* LIndex = SIndex / NCount +* VIndex = (Sindex % NCount) / TCount +* TIndex = (Sindex % TCount) +* LPart = LBase + LIndex +* VPart = VBase + VIndex +* if (TIndex == 0) { +* d = <LPart, VPart> +* } else { +* TPart = TBase + TIndex +* d = <LPart, TPart, VPart> +* } +*/ + +/* Constants */ +#define SB (0xAC00) +#define LB (0x1100) +#define VB (0x1161) +#define TB (0x11A7) +#define LC (19) +#define VC (21) +#define TC (28) +#define NC (VC * TC) +#define SC (LC * NC) + +/* Algorithmic decomposition of hangul syllable. */ +static utf8leaf_t * +utf8hangul (const char *str,unsigned char *hangul) +{ +unsigned int si; +unsigned int li; +unsigned int vi; +unsigned int ti; +unsigned char *h; + +/* Calculate the SI, LI, VI, and TI values. */ + si =utf8decode3 (str) -SB ; + li = si /NC ; + vi = (si %NC ) /TC ; + ti = si %TC ; + +/* Fill in base of leaf. */ + h = hangul; +LEAF_GEN (h) =2 ; +LEAF_CCC (h) =DECOMPOSE ; + h +=2 ; + +/* Add LPart, a 3-byte UTF-8 sequence. */ + h +=utf8encode3 ((char *)h, li +LB ); + +/* Add VPart, a 3-byte UTF-8 sequence. */ + h +=utf8encode3 ((char *)h, vi +VB ); + +/* Add TPart if required, also a 3-byte UTF-8 sequence. */ +if (ti) + h +=utf8encode3 ((char *)h, ti +TB ); + +/* Terminate string. */ + h[0 ] ='\0' ; + +return hangul; +} +/* * Use trie to scan s, touching at most len bytes. * Returns the leaf if one exists, NULL otherwise.
@@ -187,8 +319,8 @@ typedef const unsigned char utf8leaf_t;* is well-formed and corresponds to a known unicode code point. The * shorthand for this will be "is valid UTF-8 unicode". */ -static utf8leaf_t *utf8nlookup (const struct utf8data *data,const char *s, -size_t len) +static utf8leaf_t *utf8nlookup (const struct utf8data *data, +unsigned char *hangul,const char *s,size_t len) {utf8trie_t *trie = utf8data + data->offset;int offlen;
@@ -226,8 +358,7 @@ static utf8leaf_t *utf8nlookup(const struct utf8data *data, const char *s, trie++; }else {/* No right node. */ - node =0 ; - trie =NULL ; +return NULL ; } }else {/* Left leg */
@@ -237,8 +368,7 @@ static utf8leaf_t *utf8nlookup(const struct utf8data *data, const char *s, trie += offlen +1 ; }else if (*trie &RIGHTPATH ) {/* No left node. */ - node =0 ; - trie =NULL ; +return NULL ; }else {/* Left node after this node */ node = (*trie &TRIENODE );
@@ -246,6 +376,14 @@ static utf8leaf_t *utf8nlookup(const struct utf8data *data, const char *s, } } } +/* +* Hangul decomposition is done algorithmically. These are the +* codepoints >= 0xAC00 and <= 0xD7A3. Their UTF-8 encoding is +* always 3 bytes long, so s has been advanced twice, and the +* start of the sequence is at s-2. +*/ +if (LEAF_CCC (trie) ==DECOMPOSE &&LEAF_STR (trie)[0 ] ==HANGUL ) + trie =utf8hangul (s -2 , hangul);return trie; }
@@ -255,9 +393,10 @@ static utf8leaf_t *utf8nlookup(const struct utf8data *data, const char *s,* * Forwards to utf8nlookup(). */ -static utf8leaf_t *utf8lookup (const struct utf8data *data,const char *s) +static utf8leaf_t *utf8lookup (const struct utf8data *data, +unsigned char *hangul,const char *s) { -return utf8nlookup (data, s, (size_t )-1 ); +return utf8nlookup (data, hangul, s, (size_t )-1 ); }/*
@@ -270,11 +409,13 @@ int utf8agemax(const struct utf8data *data, const char *s)utf8leaf_t *leaf;int age =0 ;int leaf_age; +unsigned char hangul[UTF8HANGULLEAF ];if (!data)return -1 ; +while (*s) { - leaf =utf8lookup (data, s); + leaf =utf8lookup (data, hangul, s);if (!leaf)return -1 ;
@@ -297,12 +438,13 @@ int utf8agemin(const struct utf8data *data, const char *s)utf8leaf_t *leaf;int age;int leaf_age; +unsigned char hangul[UTF8HANGULLEAF ];if (!data)return -1 ; age = data->maxage;while (*s) { - leaf =utf8lookup (data, s); + leaf =utf8lookup (data, hangul, s);if (!leaf)return -1 ; leaf_age = utf8agetab[LEAF_GEN (leaf)];
@@ -323,11 +465,13 @@ int utf8nagemax(const struct utf8data *data, const char *s, size_t len)utf8leaf_t *leaf;int age =0 ;int leaf_age; +unsigned char hangul[UTF8HANGULLEAF ];if (!data)return -1 ; +while (len && *s) { - leaf =utf8nlookup (data, s, len); + leaf =utf8nlookup (data, hangul, s, len);if (!leaf)return -1 ; leaf_age = utf8agetab[LEAF_GEN (leaf)];
@@ -349,12 +493,13 @@ int utf8nagemin(const struct utf8data *data, const char *s, size_t len)utf8leaf_t *leaf;int leaf_age;int age; +unsigned char hangul[UTF8HANGULLEAF ];if (!data)return -1 ; age = data->maxage;while (len && *s) { - leaf =utf8nlookup (data, s, len); + leaf =utf8nlookup (data, hangul, s, len);if (!leaf)return -1 ; leaf_age = utf8agetab[LEAF_GEN (leaf)];
@@ -377,11 +522,12 @@ ssize_t utf8len(const struct utf8data *data, const char *s) {utf8leaf_t *leaf;size_t ret =0 ; +unsigned char hangul[UTF8HANGULLEAF ];if (!data)return -1 ;while (*s) { - leaf =utf8lookup (data, s); + leaf =utf8lookup (data, hangul, s);if (!leaf)return -1 ;if (utf8agetab[LEAF_GEN (leaf)] > data->maxage)
@@ -404,11 +550,12 @@ ssize_t utf8nlen(const struct utf8data *data, const char *s, size_t len) {utf8leaf_t *leaf;size_t ret =0 ; +unsigned char hangul[UTF8HANGULLEAF ];if (!data)return -1 ;while (len && *s) { - leaf =utf8nlookup (data, s, len); + leaf =utf8nlookup (data, hangul, s, len);if (!leaf)return -1 ;if (utf8agetab[LEAF_GEN (leaf)] > data->maxage)
@@ -531,10 +678,12 @@ int utf8byte(struct utf8cursor *u8c) }/* Look up the data for the current character. */ -if (u8c->p) - leaf =utf8lookup (u8c->data, u8c->s); -else - leaf =utf8nlookup (u8c->data, u8c->s, u8c->len); +if (u8c->p) { + leaf =utf8lookup (u8c->data, u8c->hangul, u8c->s); + }else { + leaf =utf8nlookup (u8c->data, u8c->hangul, + u8c->s, u8c->len); + }/* No leaf found implies that the input is a binary blob. */ if (!leaf)
@@ -555,7 +704,9 @@ int utf8byte(struct utf8cursor *u8c) ccc =STOPPER ; goto ccc_mismatch; } - leaf =utf8lookup (u8c->data, u8c->s); + + leaf =utf8lookup (u8c->data, u8c->hangul, u8c->s); + ccc =LEAF_CCC (leaf); }/*
fs/unicode/utf8n.h +4 -0
@@ -76,6 +76,9 @@ extern int utf8nagemin(const struct utf8data *data, const char *s, size_t len);extern ssize_t utf8len (const struct utf8data *data,const char *s);extern ssize_t utf8nlen (const struct utf8data *data,const char *s,size_t len); +/* Needed in struct utf8cursor below. */ +#define UTF8HANGULLEAF (12) +/* * Cursor structure used by the normalizer. */
@@ -89,6 +92,7 @@ struct utf8cursor {unsigned int slen;short int ccc;short int nccc; +unsigned char hangul[UTF8HANGULLEAF ]; };/*
scripts/mkutf8data.c +268 -39
615 lines not on this page · raw message
Signature · 1 line
2.20.1
RFC PATCH v5 5/11 unicode: Implement higher level API for string handling
In reply to Gabriel Krisman BertaziFrom: Gabriel Krisman Bertazi <[email protected]>
This patch integrates the utf8n patches with some higher level API to perform UTF-8 string comparison, normalization and casefolding operations. Implemented is a variation of NFD, and casefold is performed by doing full casefold on top of NFD. These algorithms are based on the core implemented by Olaf Weber from SGI.
Changes since v4:
- integrate in fs/unicode
Changes since RFC v1:
- Change error return code from EIO to EINVAL. (Olaf Weber)
- Fix issues with strncmp/strcmp. (Olaf Weber)
- Remove stack buffer in normalization/casefold. (Olaf Weber)
- Include length parameter for second string on comparison functions.
- Change length type to size_t.
--- fs/unicode/Makefile | 4 +- fs/unicode/utf8-core.c | 183 ++++++++++++++++++++++++++++++++++++++++ fs/unicode/utf8-norm.c | 6 ++ fs/unicode/utf8n.h | 1 + include/linux/unicode.h | 30 +++++++ 5 files changed, 223 insertions(+), 1 deletion(-) create mode 100644 fs/unicode/utf8-core.c create mode 100644 include/linux/unicode.h
fs/unicode/Makefile +3 -1
@@ -2,7 +2,9 @@ UNICODE_VERSION=11.0.0 -obj-$(CONFIG_UNICODE) += utf8-norm.o +obj-$(CONFIG_UNICODE) += unicode.o + +unicode-y := utf8-norm.o utf8-core.o $(obj)/utf8-norm.o: $(obj)/utf8data.h $(obj)/utf8data.h: $(srctree)/$(src)/ucd/*.txt $(objtree)/scripts/mkutf8data FORCE
fs/unicode/utf8-core.c new file +183 -0
183 lines not on this page · raw message
fs/unicode/utf8-norm.c +6 -0
@@ -38,6 +38,12 @@ int utf8version_is_supported(u8 maj, u8 min, u8 rev) }EXPORT_SYMBOL (utf8version_is_supported); +int utf8version_latest () +{ +return utf8vers; +} +EXPORT_SYMBOL (utf8version_latest); +/* * UTF-8 valid ranges. *
fs/unicode/utf8n.h +1 -0
@@ -32,6 +32,7 @@/* Highest unicode version supported by the data tables. */ extern int utf8version_is_supported (u8 maj,u8 min,u8 rev); +extern int utf8version_latest (void );/* * Look for the correct const struct utf8data for a unicode version.
include/linux/unicode.h new file +30 -0
@@ -0,0 +1,30 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _LINUX_UNICODE_H +#define _LINUX_UNICODE_H + +#include <linux/init.h> +#include <linux/dcache.h> + +struct unicode_map { +const char *charset; +int version; +}; + +int utf8_validate (const struct unicode_map *um,const struct qstr *str); + +int utf8_strncmp (const struct unicode_map *um, +const struct qstr *s1,const struct qstr *s2); + +int utf8_strncasecmp (const struct unicode_map *um, +const struct qstr *s1,const struct qstr *s2); + +int utf8_normalize (const struct unicode_map *um,const struct qstr *str, +unsigned char *dest,size_t dlen); + +int utf8_casefold (const struct unicode_map *um,const struct qstr *str, +unsigned char *dest,size_t dlen); + +struct unicode_map *utf8_load (const char *version); +void utf8_unload (struct unicode_map *um); + +#endif /* _LINUX_UNICODE_H */
Signature · 1 line
2.20.1
RFC PATCH v5 6/11 unicode: Introduce test module for normalized utf8 implementation
In reply to Gabriel Krisman BertaziFrom: Gabriel Krisman Bertazi <[email protected]>
This implements a in-kernel sanity test module for the utf8 normalization core. At probe time, it will run basic sequences through the utf8n core, to identify problems will equivalent sequences and normalization/casefold code. This is supposed to be useful for regression testing when adding support for a new version of utf8 to linux.
Changes since v4:
- integrate with fs/unicode
Changes since RFC v1:
- Include comparison tests for matching strings with different lengths.
- Include tests for characters included in unicode 8.0.0, 9.0.0 and 10.0.0.
--- fs/unicode/Kconfig | 5 + fs/unicode/Makefile | 1 + fs/unicode/utf8-selftest.c | 320 +++++++++++++++++++++++++++++++++++++ 3 files changed, 326 insertions(+) create mode 100644 fs/unicode/utf8-selftest.c
fs/unicode/Kconfig +5 -0
@@ -6,3 +6,8 @@ config UNICODE help Say Y here to enable UTF-8 NFD normalization and NFD+CF casefolding support. + +config UNICODE_NORMALIZATION_SELFTEST + tristate "Test UTF-8 normalization support" + depends on UNICODE + default n
fs/unicode/Makefile +1 -0
@@ -3,6 +3,7 @@ UNICODE_VERSION=11.0.0 obj-$(CONFIG_UNICODE) += unicode.o +obj-$(CONFIG_UNICODE_NORMALIZATION_SELFTEST) += utf8-selftest.o unicode-y := utf8-norm.o utf8-core.o
fs/unicode/utf8-selftest.c new file +320 -0
320 lines not on this page · raw message
Signature · 1 line
2.20.1
RFC PATCH v5 7/11 MAINTAINERS: Add Unicode subsystem entry
In reply to Gabriel Krisman Bertazi--- MAINTAINERS | 6 ++++++ 1 file changed, 6 insertions(+)
MAINTAINERS +6 -0
@@ -15337,6 +15337,12 @@ F: drivers/uwb/ F: include/linux/uwb.h F: include/linux/uwb/ +UNICODE SUBSYSTEM: +M: Gabriel Krisman Bertazi <[email protected]> +L: [email protected] +S: Supported +F: fs/unicode/ + UNICORE32 ARCHITECTURE: M: Guan Xuetao <[email protected]> W: http://mprc.pku.edu.cn/~guanxuetao/linux
Signature · 1 line
2.20.1
RFC PATCH v5 8/11 ext4: Include encoding information in the superblock
In reply to Gabriel Krisman BertaziFrom: Gabriel Krisman Bertazi <[email protected]>
Support for encoding is considered an incompatible feature, since it has potential to create collisions of file names in existing filesystems. If the feature flag is not enabled, the entire filesystem will operate on opaque byte sequences, respecting the original behavior.
The s_encoding field stores a magic number indicating the encoding format and version used globally by file and directory names in the filesystem. The s_encoding_flags defines policies for using the charset encoding, like how to handle invalid sequences. The magic number is mapped to the exact charset table, but the mapping is specific to ext4. Since we don't have any commitment to support old encodings, the only encoding I am supporting right now is utf8-11.0.
The current implementation prevents the user from enabling encoding and per-directory encryption on the same filesystem at the same time. The incompatibility between these features lies in how we do efficient directory searches when we cannot be sure the encryption of the user provided fname will match the actual hash stored in the disk without decrypting every directory entry, because of normalization cases. My quickest solution is to simply block the concurrent use of these features for now, and enable it later, once we have a better solution.
Changes since v4:
- Move from fs/nls to fs/unicode
Changes since v2:
- Split superblock bitfield reservation into another patch.
- Rename s_ioencoding -> s_encoding
- Remove encoding_info from in-memory superblock.
Changes since v1:
- Guard code with CONFIG_NLS.
- Use 16 bits for s_ioencoding.
- Split mount option from this patch
--- fs/ext4/ext4.h | 21 +++++++++++- fs/ext4/super.c | 85 +++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 105 insertions(+), 1 deletion(-)
fs/ext4/ext4.h +20 -1
@@ -1311,7 +1311,9 @@ struct ext4_super_block {__u8 s_first_error_time_hi;__u8 s_last_error_time_hi;__u8 s_pad[2 ]; -__le32 s_reserved[96 ];/* Padding to the end of the block */ +__le16 s_encoding;/* Filename charset encoding */ +__le16 s_encoding_flags;/* Filename charset encoding flags */ +__le32 s_reserved[95 ];/* Padding to the end of the block */ __le32 s_checksum;/* crc32c(superblock) */ };
@@ -1336,6 +1338,16 @@ struct ext4_super_block {/* Number of quota types we support */ #define EXT4_MAXQUOTAS 3 +#define EXT4_ENC_UTF8_11_0 1 + +/* +* Flags for ext4_sb_info.s_encoding_flags. +*/ +#define EXT4_ENC_STRICT_MODE_FL (1 << 0) + +#define ext4_has_strict_mode (sbi) \ + (sbi->s_encoding_flags & EXT4_ENC_STRICT_MODE_FL) +/* * fourth extended-fs super-block data in memory */
@@ -1385,6 +1397,10 @@ struct ext4_sb_info {struct kobject s_kobj;struct completion s_kobj_unregister;struct super_block *s_sb; +#ifdef CONFIG_UNICODE +struct unicode_map *s_encoding; +__u16 s_encoding_flags; +#endif /* Journaling */ struct journal_s *s_journal;
@@ -1661,6 +1677,7 @@ static inline void ext4_clear_state_flags(struct ext4_inode_info *ei)#define EXT4_FEATURE_INCOMPAT_LARGEDIR 0x4000/* >2GB or 3-lvl htree */ #define EXT4_FEATURE_INCOMPAT_INLINE_DATA 0x8000/* data in inode */ #define EXT4_FEATURE_INCOMPAT_ENCRYPT 0x10000 +#define EXT4_FEATURE_INCOMPAT_FNAME_ENCODING 0x20000#define EXT4_FEATURE_COMPAT_FUNCS (name, flagname) \ static inline bool ext4_has_feature_##name(struct super_block *sb) \
@@ -1749,6 +1766,7 @@ EXT4_FEATURE_INCOMPAT_FUNCS(csum_seed, CSUM_SEED) EXT4_FEATURE_INCOMPAT_FUNCS(largedir, LARGEDIR) EXT4_FEATURE_INCOMPAT_FUNCS(inline_data, INLINE_DATA) EXT4_FEATURE_INCOMPAT_FUNCS(encrypt, ENCRYPT) +EXT4_FEATURE_INCOMPAT_FUNCS(fname_encoding, FNAME_ENCODING)#define EXT2_FEATURE_COMPAT_SUPP EXT4_FEATURE_COMPAT_EXT_ATTR#define EXT2_FEATURE_INCOMPAT_SUPP (EXT4_FEATURE_INCOMPAT_FILETYPE| \
@@ -1776,6 +1794,7 @@ EXT4_FEATURE_INCOMPAT_FUNCS(encrypt, ENCRYPT) EXT4_FEATURE_INCOMPAT_MMP | \ EXT4_FEATURE_INCOMPAT_INLINE_DATA | \ EXT4_FEATURE_INCOMPAT_ENCRYPT | \ + EXT4_FEATURE_INCOMPAT_FNAME_ENCODING | \ EXT4_FEATURE_INCOMPAT_CSUM_SEED | \ EXT4_FEATURE_INCOMPAT_LARGEDIR)#define EXT4_FEATURE_RO_COMPAT_SUPP (EXT4_FEATURE_RO_COMPAT_SPARSE_SUPER| \
fs/ext4/super.c +85 -0
121 lines not on this page · raw message
Signature · 1 line
2.20.1
RFC PATCH v5 9/11 ext4: Support encoding-aware file name lookups
In reply to Gabriel Krisman BertaziFrom: Gabriel Krisman Bertazi <[email protected]>
This patch implements the actual support for encoding-aware file name lookups in ext4, based on the feature bit and the encoding stored in the superblock.
A filesystem that has the fname_encoding feature set is able to find files even if the name used by userspace is not a byte per byte match, but is an equivalent unicode string. This operation will be called and inexact-match name search.
* dcache handling:
Ext4 only stores the first equivalent name dentry used in the dcache. This is done to prevent unintentional duplication of dentries in the dcache, while also allowing the VFS code to quickly find the right entry in the cache despite what equivalent string was used without resorting to ->lookup().
d_hash() is implemented as the hash of the normalized string, such that we always have a well-known bucket for all the equivalencies of the same string. d_compare uses the nls_strncmp() infrastructure, which should handle the comparison of equivalent names as well. If the filesystem's normalization type is PLAIN, though, we can just reuse the VFS hash.
For now, negative lookups are not inserted in the dcache, since they would need to be invalidated anyway, because we can't trust missing file dentries. This is bad for performance but requires some leveraging of the vfs layer to fix. We can live without that for now, and so does everyone else.
* on-disk data:
Despite using a specific version of the name as the internal representation within the dcache, the name stored and fetch from the disk is a byte-per-byte match with what the user requested, making this implementation Name-preserving. i.e. no actual information is lost when writing to the storage.
DX is supported by modifying the hashes to make them encoding-aware. The new disk hashes are also calculated as the hash of the normalized string, instead of the string directly. This allows us to efficiently search for file names in the htree without requiring the user to provide the exact name.
* Dealing with invalid sequences:
By default, when a invalid UTF-8 sequence is identified, ext4 will treat it as an opaque byte sequence, ignoring the encoding and reverting to the old behavior for that unique file. This means that inexact-match lookups and (future) casefold will not work for that file only. An optional bit can be set in the superblock telling the filesystem code and userspace tools to enforce the encoding. When that flag is set, any attempt to create a file name using an invalid UTF-8 sequence will fail.
* Normalization algorithm:
The UTF-8 algorithm used to lookup and compare strings in ext4 is implemented by fs/unicode, and is based on a previous developed by SGI. It implements the Canonical decomposition (NFD) algorithm described by the Unicode specification 11.0, or higher, combined with the elimination of ignorable code points (NFDi) as documented in fs/unicode/utf8_norm.c.
NFD seems to be the best normalization method because:
- It has a lower cost than NFC/NFKC (which requires decomposing to NFD as an intermediary step)
- It doesn't eliminate important semantic meaning like NFKD.
But:
- It ignores valid equivalent sequences in some languages, which would be invalid on anothers: the ff ligature, in o_ff_i_c_e, and the usual spelling o_f_f_i_c_e, for instance, will no longer match. On the other hand, the ash grapheme (formed by a ligature of AE ) can be represented as a different letter than A plus E, which is correct in Danish, Norwegian, Icelandic, and Faroese.
- This implementation is not linguistic accurate, because different languages have conflicting rules, which would require the specialization of the filesystem to a given locale, which brings all sorts of problems for removable media and for users who use more than one language.
Changes since v4:
- Migrate NFKD -> NFD
Changes since v2:
- Don't use d_add_ci.
- Squash the dcache hooks into this patch.
- Rename sbi->encoding -> sbi->s_encoding.
Changes since v1:
- Support normalized htree hashes.
- Guard code with CONFIG_NLS.
- Use qstr->len instead of strlen in dcache hookups.
--- fs/ext4/dir.c | 40 +++++++++++++++++++ fs/ext4/ext4.h | 12 +++++- fs/ext4/hash.c | 35 ++++++++++++++++- fs/ext4/ialloc.c | 2 +- fs/ext4/inline.c | 2 +- fs/ext4/namei.c | 100 +++++++++++++++++++++++++++++++++++++++++------ fs/ext4/super.c | 6 +++ 7 files changed, 181 insertions(+), 16 deletions(-)
fs/ext4/dir.c +40 -0
@@ -26,6 +26,7 @@#include <linux/buffer_head.h> #include <linux/slab.h> #include <linux/iversion.h> +#include <linux/unicode.h> #include "ext4.h" #include "xattr.h"
@@ -662,3 +663,42 @@ const struct file_operations ext4_dir_operations = { .open = ext4_dir_open, .release = ext4_release_dir, }; + +#ifdef CONFIG_UNICODE +static int ext4_d_compare (const struct dentry *dentry,unsigned int len, +const char *str,const struct qstr *name) +{ +struct qstr qstr = {.name = str, .len = len }; + +return ext4_encoding_cmp (dentry->d_parent->d_inode, name, &qstr); +} + +static int ext4_d_hash (const struct dentry *dentry,struct qstr *str) +{ +const struct ext4_sb_info *sbi =EXT4_SB (dentry->d_sb); +const struct unicode_map *um = sbi->s_encoding; +unsigned char *norm; +int len, ret =0 ; + + norm =kmalloc (PATH_MAX ,GFP_ATOMIC ); +if (!norm) +return -ENOMEM ; + + len =utf8_normalize (um, str, norm,PATH_MAX ); + +if (len <0 ) { +if (ext4_has_strict_mode (sbi)) + ret = -EINVAL ; + goto out; + } + str->hash =full_name_hash (dentry, norm, len); +out: +kfree (norm); +return ret; +} + +const struct dentry_operations ext4_dentry_ops = { + .d_hash = ext4_d_hash, + .d_compare = ext4_d_compare, +}; +#endif
fs/ext4/ext4.h +10 -2
@@ -2394,8 +2394,8 @@ extern int ext4_check_all_de(struct inode *dir, struct buffer_head *bh,extern int ext4_sync_file (struct file *,loff_t ,loff_t ,int );/* hash.c */ -extern int ext4fs_dirhash (const char *name,int len,struct -dx_hash_info *hinfo); +extern int ext4fs_dirhash (const struct inode *dir,const char *name,int len, +struct dx_hash_info *hinfo);/* ialloc.c */ extern struct inode *__ext4_new_inode(handle_t *, struct inode *, umode_t,
@@ -2979,6 +2979,10 @@ static inline void ext4_unlock_group(struct super_block *sb,/* dir.c */ extern const struct file_operations ext4_dir_operations; +#ifdef CONFIG_UNICODE +extern const struct dentry_operations ext4_dentry_ops; +#endif +/* file.c */ extern const struct inode_operations ext4_file_inode_operations;extern const struct file_operations ext4_file_operations;
@@ -3071,6 +3075,10 @@ extern void initialize_dirent_tail(struct ext4_dir_entry_tail *t,extern int ext4_handle_dirty_dirent_node (handle_t *handle,struct inode *inode,struct buffer_head *bh); +extern int ext4_encoding_cmp (const struct inode *parent, +const struct qstr *name, +const struct qstr *entry); +#define S_SHIFT 12static const unsigned char ext4_type_by_mode[(S_IFMT >>S_SHIFT ) +1 ] = { [S_IFREG >>S_SHIFT ] =EXT4_FT_REG_FILE ,
fs/ext4/hash.c +34 -1
@@ -6,6 +6,7 @@*/ #include <linux/fs.h> +#include <linux/unicode.h> #include <linux/compiler.h> #include <linux/bitops.h> #include "ext4.h"
@@ -196,7 +197,8 @@ static void str2hashbuf_unsigned(const char *msg, int len, __u32 *buf, int num)* represented, and whether or not the returned hash is 32 bits or 64 * bits. 32 bit hashes will return 0 for the minor hash. */ -int ext4fs_dirhash (const char *name,int len,struct dx_hash_info *hinfo) +static int __ext4fs_dirhash (const char *name,int len, +struct dx_hash_info *hinfo) {__u32 hash;__u32 minor_hash =0 ;
@@ -266,3 +268,34 @@ int ext4fs_dirhash(const char *name, int len, struct dx_hash_info *hinfo) hinfo->minor_hash = minor_hash;return 0 ; } + +int ext4fs_dirhash (const struct inode *dir,const char *name,int len, +struct dx_hash_info *hinfo) +{ +#ifdef CONFIG_UNICODE +const struct unicode_map *um =EXT4_SB (dir->i_sb)->s_encoding; +int r, dlen; +unsigned char *buff; +struct qstr qstr = {.name = name, .len = len }; + +if (len && um) { + buff =kzalloc (sizeof (char ) *PATH_MAX ,GFP_KERNEL ); +if (!buff) +return -1 ; + + dlen =utf8_normalize (um, &qstr, buff,PATH_MAX ); + +if (dlen <0 ) { +kfree (buff); + goto opaque_seq; + } + + r =__ext4fs_dirhash (buff, dlen, hinfo); + +kfree (buff); +return r; + } +opaque_seq: +#endif +return __ext4fs_dirhash (name, len, hinfo); +}
fs/ext4/ialloc.c +1 -1
@@ -455,7 +455,7 @@ static int find_group_orlov(struct super_block *sb, struct inode *parent,if (qstr) { hinfo.hash_version =DX_HASH_HALF_MD4 ; hinfo.seed = sbi->s_hash_seed; -ext4fs_dirhash (qstr->name, qstr->len, &hinfo); +ext4fs_dirhash (parent, qstr->name, qstr->len, &hinfo); grp = hinfo.hash; }else grp =prandom_u32 ();
fs/ext4/inline.c +1 -1
@@ -1404,7 +1404,7 @@ int htree_inlinedir_to_tree(struct file *dir_file, } } -ext4fs_dirhash (de->name, de->name_len, hinfo); +ext4fs_dirhash (dir, de->name, de->name_len, hinfo);if ((hinfo->hash < start_hash) || ((hinfo->hash == start_hash) && (hinfo->minor_hash < start_minor_hash)))
fs/ext4/namei.c +89 -11
214 lines not on this page · raw message
fs/ext4/super.c +6 -0
@@ -4420,6 +4420,12 @@ static int ext4_fill_super(struct super_block *sb, void *data, int silent)iput (root); goto failed_mount4; } + +#ifdef CONFIG_UNICODE +if (sbi->s_encoding) + sb->s_d_op = &ext4_dentry_ops; +#endif + sb->s_root =d_make_root (root);if (!sb->s_root) {ext4_msg (sb,KERN_ERR ,"get root dentry failed" );
Signature · 1 line
2.20.1
RFC PATCH v5 10/11 ext4: Implement EXT4_CASEFOLD_FL flag
In reply to Gabriel Krisman BertaziFrom: Gabriel Krisman Bertazi <[email protected]>
Casefold is implemented as a special case of the fname_encoding feature, thus requiring it to be enabled. This design mechanism works semantically fine, because we consider that without an specified encoding the casefold operation cannot be defined.
Despite the common core implementation, the Casefold setting can be applied to directories individually, making entire subtrees of the filesystem case-insensitive or not. The flag is set as an inode attribute applied to directories and inherited by its children which states that the directory requires case-insensitive searches. This flag can only be enabled on empty directories for filesystems that support the encoding feature, thus preventing collision of file names that only differ by case.
Changes since v2:
- Rename sbi->encoding -> sbi->s_encoding.
Changes since v1:
- Moved the CASEFOLD_FL to prevent collision with reserved verity flag.
--- fs/ext4/dir.c | 5 ++++- fs/ext4/ext4.h | 9 +++++---- fs/ext4/hash.c | 5 ++++- fs/ext4/inode.c | 4 +++- fs/ext4/ioctl.c | 18 ++++++++++++++++++ fs/ext4/namei.c | 6 +++++- include/linux/fs.h | 2 ++ 7 files changed, 41 insertions(+), 8 deletions(-)
fs/ext4/dir.c +4 -1
@@ -684,7 +684,10 @@ static int ext4_d_hash(const struct dentry *dentry, struct qstr *str)if (!norm)return -ENOMEM ; - len =utf8_normalize (um, str, norm,PATH_MAX ); +if (!IS_CASEFOLDED (dentry->d_inode)) + len =utf8_normalize (um, str, norm,PATH_MAX ); +else + len =utf8_casefold (um, str, norm,PATH_MAX );if (len <0 ) {if (ext4_has_strict_mode (sbi))
fs/ext4/ext4.h +5 -4
@@ -400,10 +400,11 @@ struct flex_groups {#define EXT4_EOFBLOCKS_FL 0x00400000/* Blocks allocated beyond EOF */ #define EXT4_INLINE_DATA_FL 0x10000000/* Inode has inline data. */ #define EXT4_PROJINHERIT_FL 0x20000000/* Create with parents projid */ +#define EXT4_CASEFOLD_FL 0x40000000/* Casefolded file */ #define EXT4_RESERVED_FL 0x80000000/* reserved for ext4 lib */ -#define EXT4_FL_USER_VISIBLE 0x304BDFFF/* User visible flags */ -#define EXT4_FL_USER_MODIFIABLE 0x204BC0FF/* User modifiable flags */ +#define EXT4_FL_USER_VISIBLE 0x704BDFFF/* User visible flags */ +#define EXT4_FL_USER_MODIFIABLE 0x604BC0FF/* User modifiable flags */ /* Flags we can manipulate with through EXT4_IOC_FSSETXATTR */ #define EXT4_FL_XFLAG_VISIBLE (EXT4_SYNC_FL | \
@@ -418,10 +419,10 @@ struct flex_groups { EXT4_SYNC_FL | EXT4_NODUMP_FL | EXT4_NOATIME_FL |\ EXT4_NOCOMPR_FL | EXT4_JOURNAL_DATA_FL |\ EXT4_NOTAIL_FL | EXT4_DIRSYNC_FL |\ - EXT4_PROJINHERIT_FL) + EXT4_PROJINHERIT_FL | EXT4_CASEFOLD_FL)/* Flags that are appropriate for regular files (all but dir-specific ones). */ -#define EXT4_REG_FLMASK (~(EXT4_DIRSYNC_FL | EXT4_TOPDIR_FL)) +#define EXT4_REG_FLMASK (~(EXT4_DIRSYNC_FL | EXT4_TOPDIR_FL | EXT4_CASEFOLD_FL))/* Flags that are appropriate for non-directories/regular files. */ #define EXT4_OTHER_FLMASK (EXT4_NODUMP_FL | EXT4_NOATIME_FL)
fs/ext4/hash.c +4 -1
@@ -283,7 +283,10 @@ int ext4fs_dirhash(const struct inode *dir, const char *name, int len,if (!buff)return -1 ; - dlen =utf8_normalize (um, &qstr, buff,PATH_MAX ); +if (!IS_CASEFOLDED (dir)) + dlen =utf8_normalize (um, &qstr, buff,PATH_MAX ); +else + dlen =utf8_casefold (um, &qstr, buff,PATH_MAX );if (dlen <0 ) {kfree (buff);
fs/ext4/inode.c +3 -1
@@ -4745,9 +4745,11 @@ void ext4_set_inode_flags(struct inode *inode) new_fl |=S_DAX ;if (flags &EXT4_ENCRYPT_FL ) new_fl |=S_ENCRYPTED ; +if (flags &EXT4_CASEFOLD_FL ) + new_fl |=S_CASEFOLD ;inode_set_flags (inode, new_fl,S_SYNC |S_APPEND |S_IMMUTABLE |S_NOATIME |S_DIRSYNC |S_DAX | -S_ENCRYPTED ); +S_ENCRYPTED |S_CASEFOLD ); } static blkcnt_t ext4_inode_blocks(struct ext4_inode *raw_inode,
fs/ext4/ioctl.c +18 -0
@@ -231,6 +231,7 @@ static int ext4_ioctl_setflags(struct inode *inode,struct ext4_iloc iloc;unsigned int oldflags, mask, i;unsigned int jflag; +struct super_block *sb = inode->i_sb;/* Is it quota file? Do not allow user to mess with it */ if (ext4_is_quota_file (inode))
@@ -275,6 +276,23 @@ static int ext4_ioctl_setflags(struct inode *inode, goto flags_out; } +if ((flags ^ oldflags) &EXT4_CASEFOLD_FL ) { +if (!ext4_has_feature_fname_encoding (sb)) { + err = -EOPNOTSUPP ; + goto flags_out; + } + +if (!S_ISDIR (inode->i_mode)) { + err = -ENOTDIR ; + goto flags_out; + } + +if (!ext4_empty_dir (inode)) { + err = -ENOTEMPTY ; + goto flags_out; + } + } + handle =ext4_journal_start (inode,EXT4_HT_INODE ,1 );if (IS_ERR (handle)) { err =PTR_ERR (handle);
fs/ext4/namei.c +5 -1
@@ -1261,7 +1261,11 @@ int ext4_encoding_cmp(const struct inode *parent, const struct qstr *name,const struct unicode_map *um = sbi->s_encoding;int ret; - ret =utf8_strncmp (um, name, entry); +if (!IS_CASEFOLDED (parent)) + ret =utf8_strncmp (um, name, entry); +else + ret =utf8_strncasecmp (um, name, entry); +if (ret <0 ) {/* Handle invalid character sequence as either an error * or as an opaque byte sequence.
include/linux/fs.h +2 -0
@@ -1947,6 +1947,7 @@ struct super_operations {#define S_DAX 0/* Make all the DAX code disappear */ #endif #define S_ENCRYPTED 16384/* Encrypted file (using fs/crypto/) */ +#define S_CASEFOLD 32768/* Casefolded file */ /* * Note that nosuid etc flags are inode-specific: setting some file-system
@@ -1987,6 +1988,7 @@ static inline bool sb_rdonly(const struct super_block *sb) { return sb->s_flags#define IS_NOSEC (inode) ((inode)->i_flags & S_NOSEC)#define IS_DAX (inode) ((inode)->i_flags & S_DAX)#define IS_ENCRYPTED (inode) ((inode)->i_flags & S_ENCRYPTED) +#define IS_CASEFOLDED (inode) ((inode)->i_flags & S_CASEFOLD)#define IS_WHITEOUT (inode) (S_ISCHR(inode->i_mode) && \ (inode)->i_rdev == WHITEOUT_DEV)
Signature · 1 line
2.20.1
RFC PATCH v5 11/11 docs: ext4.rst: Document encoding and case-insensitive
In reply to Gabriel Krisman BertaziFrom: Gabriel Krisman Bertazi <[email protected]>
Introduces the encoding-awareness and case-insensitive features on ext4 for system administrators. Explain the minimum of design decisions that are important for sysadmins wanting to enable this feature.
--- Documentation/admin-guide/ext4.rst | 41 ++++++++++++++++++++++++++++++ 1 file changed, 41 insertions(+)
Documentation/admin-guide/ext4.rst +41 -0
@@ -91,10 +91,51 @@ Currently Available * large block (up to pagesize) support * efficient new ordered mode in JBD2 and ext4 (avoid using buffer head to force the ordering) +* Encoding aware file names +* Case insensitive file name lookups [1] Filesystems with a block size of 1k may see a limit imposed by the directory hash tree having a maximum depth of two. +Encoding-aware file names and case-insensitive lookups +====================================================== + +Ext4 optionally supports filesystem-wide charset knowledge when handling +file names, which allows the user to perform file system lookups using +charset equivalent versions of the same file name, and optionally ensure +that no invalid names are held by the filesystem. charset encoding +awareness is also essential for performing case-insensitive lookups, +because it is what defines the casefold operation. + +The case-insensitive file name lookup feature is supported in a smaller +granularity, on a per-directory basis, allowing the user to mix +case-insensitive and case-sensitive directories in the same filesystem. +It is enabled by flipping a file attribute on an empty directory. For +the reason stated above, the filesystem must have encoding enabled to +use this feature. + +Both encoding-awareness and case-awareness are name-preserving on the +disk, meaning that the file name provided by userspace is a +byte-per-byte match to what is actually written in the disk. The +Unicode normalization format used by the kernel is thus an internal +representation, and not exposed to the userspace nor to the disk, with +the important exception of disk hashes, used on large directories with +DX feature. On DX directories, the hash must be calculated using the +normalized version of the filename, meaning that the normalization +format used actually has an impact on where the directory entry is +stored. + +When we change from viewing filenames as opaque byte sequences to seeing +them as encoded strings we need to address what happens when a program +tries to create a file with an invalid name. The Unicode subsystem +within the kernel leaves the decision of what to do in this case to the +filesystem, which select its preferred behavior by enabling/disabling +the strict mode. When Ext4 encounters one of those strings and the +filesystem did not require strict mode, it falls back to considering the +entire string as an opaque byte sequence, which still allows the user to +operate on that file but the case-insensitive and equivalent sequence +lookups won't work. + Options =======
Signature · 1 line
2.20.1
Quoted 20 lines · Gabriel Krisman Bertazi
Following Linus comments, this version is back as an RFC, in order to discuss the normalization method used. At a first glance, you will notice the series got a lot smaller, with the separation of unicode code from the NLS subsystem, as Linus requested. The ext4 parts are pretty much the same, with only the addition of a verification in
ext4_feature_set_ok()to fail encoding mounts when withoutCONFIG_UNICODEon newer kernels.The main change presented here is a proposal to migrate the normalization method from NFKD to NFD. After our discussions, and reviewing other operating systems and languages aspects, I am more convinced that canonical decomposition is more viable solution than compatibility decomposition, because it doesn't ignore eliminate any semantic meaning, like the definitive case of superscript numbers. NFD is also the documented method used by HFS+ and APFS, so there is precedent. Notice however, that as far as my research goes, APFS doesn't completely follows NFD, and in some cases, like <compat> flags, it actually does NFKD, but not in others (<fraction>), where it applies the canonical form. We take a more consistent approach and always do plain NFD.
Quoted 4 lines
This RFC, therefore, aims to resume/start conversation with some stalkeholders that may have something to say regarding the normalization method used. I added people from SMB, NFS and FS development who might be interested on this.
For what it's worth, knfsd will just pass through pathnames unchanged the client, and the Linux client will pass them on to applications unchanged. I don't know what other clients might do. But it's hard for NFS clients and servers to do anything more clever, because behavior of exported filesystems varies, users have preexisting filesystems with random encodings, and on the client side in the Linux case, the kernel doesn't know about process locales. So, whatever behavior ext4 implements is likely the same behavior that will be seen by an application on a client accessing an ext4 filesystem over NFS.
--b.
Quoted 85 lines
Regarding Casefold, I am unsure whether Casefold Common + Full still makes sense after migrating from the compatibility to the canonical form. While Casefold Full, by definition, addresses cases where the casefolding grows in size, like the casefold of the german eszett to SS, it also is responsible for folding smallcase ligatures without a corresponding uppercase to their compatible counterpart. Which means that on -F directories,
o_f_f_i_c_eando_ff_i_c_ewill differ, while on +F directories they will match. This seems unaceptable to me, suggesting that we should start to use Common + Simple instead of Common
+ Full, but I would like more input on what seems more reasonable to you.After we decide on this, I will be sending new patches to update e2fsprogs to the agreed method and remove the normalization/casefold type flags (
EXT4_UTF8_NORMALIZATION_TYPE_NFKD,EXT4_UTF8_CASEFOLD_TYPE_NFKDCF), before actually proposing the current patch series for inclusion in the kernel.Practical things, w.r.t. this patch series:
- As usual, the UCD files are not part of the series, because they would bounce. To test this one would need to fetch the files as explained in the commit message.
- If you prefer, you can checkout from
https://gitlab.collabora.com/krisman/linux -b ext4-ci-directory-no-nls- More details on the design decisions restricted to ext4 are available in the corresponding commit messages.
Thanks for keeping up with this.
Gabriel Krisman Bertazi (7):
unicode: Implement higher level API for string handling
unicode: Introduce test module for normalized utf8 implementation
MAINTAINERS: Add Unicode subsystem entry
ext4: Include encoding information in the superblock
ext4: Support encoding-aware file name lookups
ext4: ImplementEXT4_CASEFOLD_FLflag
docs:ext4.rst: Document encoding and case-insensitiveOlaf Weber (4):
unicode: Add unicode character database files
scripts: add trie generator for UTF-8
unicode: Introduce code for UTF-8 normalization
unicode: reduce the size of utf8data[]Documentation/admin-guide/ext4.rst | 41 + MAINTAINERS | 6 + fs/Kconfig | 1 + fs/Makefile | 1 + fs/ext4/dir.c | 43 + fs/ext4/ext4.h | 42 +- fs/ext4/hash.c | 38 +- fs/ext4/ialloc.c | 2 +- fs/ext4/inline.c | 2 +- fs/ext4/inode.c | 4 +- fs/ext4/ioctl.c | 18 + fs/ext4/namei.c | 104 +- fs/ext4/super.c | 91 + fs/unicode/Kconfig | 13 + fs/unicode/Makefile | 22 + fs/unicode/ucd/README | 33 + fs/unicode/utf8-core.c | 183 ++ fs/unicode/utf8-norm.c | 797 +++++++ fs/unicode/utf8-selftest.c | 320 +++ fs/unicode/utf8n.h | 117 + include/linux/fs.h | 2 + include/linux/unicode.h | 30 + scripts/Makefile | 1 + scripts/mkutf8data.c | 3418 ++++++++++++++++++++++++++++ 24 files changed, 5307 insertions(+), 22 deletions(-) create mode 100644 fs/unicode/Kconfig create mode 100644 fs/unicode/Makefile create mode 100644 fs/unicode/ucd/README create mode 100644 fs/unicode/utf8-core.c create mode 100644 fs/unicode/utf8-norm.c create mode 100644 fs/unicode/utf8-selftest.c create mode 100644 fs/unicode/utf8n.h create mode 100644 include/linux/unicode.h create mode 100644 scripts/mkutf8data.cSignature · 1 line
2.20.1
Quoted 12 lines · On Monday 28 January 2019 16:32:12 Gabriel Krisman Bertazi wrote:
The main change presented here is a proposal to migrate the normalization method from NFKD to NFD. After our discussions, and reviewing other operating systems and languages aspects, I am more convinced that canonical decomposition is more viable solution than compatibility decomposition, because it doesn't ignore eliminate any semantic meaning, like the definitive case of superscript numbers. NFD is also the documented method used by HFS+ and APFS, so there is precedent. Notice however, that as far as my research goes, APFS doesn't completely follows NFD, and in some cases, like <compat> flags, it actually does NFKD, but not in others (<fraction>), where it applies the canonical form. We take a more consistent approach and always do plain NFD.
Quoted 4 lines
This RFC, therefore, aims to resume/start conversation with some stalkeholders that may have something to say regarding the normalization method used. I added people from SMB, NFS and FS development who might be interested on this.
Hello! I think that choice of NFD normalization is not right decision. Some reasons:
1) NFD is not widely used. Even Apple does not use it (as you wrote Apple has own normalization form).
2) All filesystems which I known either do not use any normalization or use NFC.
3) Lot of existing Linux application generate file names in NFC.
4) Linux GUI libraries like Qt and Gtk generate strings from key strokes in NFC. So if user type file name in Qt/Gtk box it would be in NFC.
So why to use NFD in ext4 filesystem if Linux userspace ecosystem already uses NFC?
NFD here just makes another layer of problems, unexpected things and make it somehow different.
Why not rather choose NFS? It would be more compatible with Linux GUI applications and also with Microsoft Windows systems, which uses NFC too.
Please, really consider to not use NFD. Most Linux applications really do not do any normalization or do NFC. And usage of decomposition form for application which do not implement full Unicode grapheme algorithms just make for them another problems.
Yes, there are still lot of legacy application which expect that one code point = one visible symbol (therefore one Unicode grapheme). And because GUI in most cases generates NFC strings, also existing file names are in NFC, these application works in most cases without problem. Force usage of NFD filenames just break them.
(PS: I think that only 2 programming languages implements Unicode grapheme algorithms correctly: Elixir and Perl 6; which is not so much)
Signature · 2 lines
Pali Rohár [email protected]
Quoted 18 lines · Pali Rohár
Quoted 12 lines · On Monday 28 January 2019 16:32:12 Gabriel Krisman Bertazi wrote:
The main change presented here is a proposal to migrate the normalization method from NFKD to NFD. After our discussions, and reviewing other operating systems and languages aspects, I am more convinced that canonical decomposition is more viable solution than compatibility decomposition, because it doesn't ignore eliminate any semantic meaning, like the definitive case of superscript numbers. NFD is also the documented method used by HFS+ and APFS, so there is precedent. Notice however, that as far as my research goes, APFS doesn't completely follows NFD, and in some cases, like <compat> flags, it actually does NFKD, but not in others (<fraction>), where it applies the canonical form. We take a more consistent approach and always do plain NFD.
Quoted 4 lines
This RFC, therefore, aims to resume/start conversation with some stalkeholders that may have something to say regarding the normalization method used. I added people from SMB, NFS and FS development who might be interested on this.
Quoted 5 lines
Hello! I think that choice of NFD normalization is not right decision. Some reasons:
1) NFD is not widely used. Even Apple does not use it (as you wrote Apple has own normalization form).
To be exact, Apple claims to use NFD in their specification [1] . What I observed is that they don't ignore some types of compatibility characters correctly as they should. For instance, the ff ligature is decomposed into f + f.
Quoted 4 lines
2) All filesystems which I known either do not use any normalization or use NFC.
3) Lot of existing Linux application generate file names in NFC.
Most do use NFC. But this is an internal representation for ext4 and it is name preserving. We only use the normalization when comparing if names matches and to calculate dcache and dx hashes. The unicode standard recomends the D forms for internal representation.
Quoted 5 lines
4) Linux GUI libraries like Qt and Gtk generate strings from key strokes in NFC. So if user type file name in Qt/Gtk box it would be in NFC.
So why to use NFD in ext4 filesystem if Linux userspace ecosystem already uses NFC?
NFC is costlier to calculate, usually requiring an intermediate NFD step. Whether it is prohibitively expensive to do in the dcache path, I don't know, but since it is a critical path, any gain matters.
Quoted 2 lines
NFD here just makes another layer of problems, unexpected things and make it somehow different.
Is there any case where
NFC(x) == NFC(y) && NFD(x) != NFD(y) , or
NFC(x) != NFC(y) && NFD(x) == NFD(y)
I am having a hard time thinking of an example. This is the main (only?) scenario where choosing C or D form for an internal representation would affect userspace.
Quoted 10 lines
Why not rather choose NFS? It would be more compatible with Linux GUI applications and also with Microsoft Windows systems, which uses NFC too.
Please, really consider to not use NFD. Most Linux applications really do not do any normalization or do NFC. And usage of decomposition form for application which do not implement full Unicode grapheme algorithms just make for them another problems.
Quoted 5 lines
Yes, there are still lot of legacy application which expect that one code point = one visible symbol (therefore one Unicode grapheme). And because GUI in most cases generates NFC strings, also existing file names are in NFC, these application works in most cases without problem. Force usage of NFD filenames just break them.
As I said, this shouldn't be a problem because what the application creates and retrieves is the exact name that was used before, we'd only use this format for internal metadata on the disk (hashes) and for in-kernel comparisons.
Quoted 3 lines
(PS: I think that only 2 programming languages implements Unicode grapheme algorithms correctly: Elixir and Perl 6; which is not so much)
[1] https://developer.apple.com/support/apple-file-system/Apple-File-System-Reference.pdf
Signature · 1 line
Gabriel Krisman Bertazi
Quoted 20 lines · On Tuesday 05 February 2019 14:08:00 Gabriel Krisman Bertazi wrote:
Quoted 18 lines · Pali Rohár
Quoted 16 lines · On Monday 28 January 2019 16:32:12 Gabriel Krisman Bertazi wrote:
The main change presented here is a proposal to migrate the normalization method from NFKD to NFD. After our discussions, and reviewing other operating systems and languages aspects, I am more convinced that canonical decomposition is more viable solution than compatibility decomposition, because it doesn't ignore eliminate any semantic meaning, like the definitive case of superscript numbers. NFD is also the documented method used by HFS+ and APFS, so there is precedent. Notice however, that as far as my research goes, APFS doesn't completely follows NFD, and in some cases, like <compat> flags, it actually does NFKD, but not in others (<fraction>), where it applies the canonical form. We take a more consistent approach and always do plain NFD.
This RFC, therefore, aims to resume/start conversation with some stalkeholders that may have something to say regarding the normalization method used. I added people from SMB, NFS and FS development who might be interested on this.
Quoted 7 lines
Quoted 5 lines
Hello! I think that choice of NFD normalization is not right decision. Some reasons:
1) NFD is not widely used. Even Apple does not use it (as you wrote Apple has own normalization form).
To be exact, Apple claims to use NFD in their specification [1] .
Interesting...
Quoted 4 lines
What I
observed is that they don't ignore some types of compatibility characters correctly as they should. For instance, the ff ligature is decomposed into f + f.
I'm sure that Apple does not do NFD, but their own invented normal form. Some graphemes are decomposed, and some not.
Quoted 7 lines
Quoted 4 lines
2) All filesystems which I known either do not use any normalization or use NFC.
3) Lot of existing Linux application generate file names in NFC.Most do use NFC. But this is an internal representation for ext4 and it is name preserving.
Ok. I was in impression that it does not preserve original names, just like implementation in Apple's system, where char* passed to creat() does not appear in readdir().
Quoted 3 lines
We only use the normalization when comparing if names matches and to calculate dcache and dx hashes. The unicode standard recomends the D forms for internal representation.
Ok, this should be less destructive and less visible to userspace.
Quoted 10 lines
Quoted 5 lines
4) Linux GUI libraries like Qt and Gtk generate strings from key strokes in NFC. So if user type file name in Qt/Gtk box it would be in NFC.
So why to use NFD in ext4 filesystem if Linux userspace ecosystem already uses NFC?
NFC is costlier to calculate, usually requiring an intermediate NFD step. Whether it is prohibitively expensive to do in the dcache path, I don't know, but since it is a critical path, any gain matters.
Quoted 6 lines
Quoted 2 lines
NFD here just makes another layer of problems, unexpected things and make it somehow different.
Is there any case where
NFC(x) == NFC(y) && NFD(x) != NFD(y) , or
NFC(x) != NFC(y) && NFD(x) == NFD(y)
This is good question. And I think we should get definite answer for it prior inclusion of normalization into kernel.
Quoted 3 lines
I am having a hard time thinking of an example. This is the main (only?) scenario where choosing C or D form for an internal representation would affect userspace.
For decision between normal format, probably yes.
Quoted 16 lines
Quoted 10 lines
Why not rather choose NFS? It would be more compatible with Linux GUI applications and also with Microsoft Windows systems, which uses NFC too.
Please, really consider to not use NFD. Most Linux applications really do not do any normalization or do NFC. And usage of decomposition form for application which do not implement full Unicode grapheme algorithms just make for them another problems.
Quoted 5 lines
Yes, there are still lot of legacy application which expect that one code point = one visible symbol (therefore one Unicode grapheme). And because GUI in most cases generates NFC strings, also existing file names are in NFC, these application works in most cases without problem. Force usage of NFD filenames just break them.
Quoted 4 lines
As I said, this shouldn't be a problem because what the application creates and retrieves is the exact name that was used before, we'd only use this format for internal metadata on the disk (hashes) and for in-kernel comparisons.
There is another problem for userspace applications:
Currently ext4 accepts as file name any sequence of bytes which do not contain nul byte and '/'. So having Latin1 file name is perfectly correct.
What would happen if userspace application want to create following two file names? "\xDF" and "\F0"? First one is sharp S second one is eth (in Latin1). But file names are invalid UTF-8 sequences. Is it disallowed to create such file names? Or both file names are internally converted to "U+FFFD" (replacement character) and because NFD(first U+FFFD) == NFD(second U+FFFD) only first file would be created?
And what happen in general with invalid UTF-8 sequences? Because there are many different types of invalid UTF-8 sequences, like non-shortest sequence for valid code point, valid sequence for invalid code points (either surrogate pairs code points, or code points above U+10FFFF, ...), incorrect byte which should start new code point, incorrect byte when decoding of code point started, ...
Different (userspace) application handles these invalid UTF-8 sequences differently, some of them accept some kind of "incorrectness" (e.g. non-shortest form of code point representation), some not. Some applications replace invalid parts of UTF-8 sequence by sequence of UTF-8 replacement character, some not. Also it can be observed that some applications use just one replacement characters and some other replace invalid UTF-8 sequence by more replacement characters.
So trying to "recover" from invalid UTF-8 sequence to valid one is done in more ways... And usage of any existing way could cause problems... E.g. not possible to create two files "\xDF\xF0" and "\xF0\xDF"...
Quoted 6 lines
Quoted 3 lines
(PS: I think that only 2 programming languages implements Unicode grapheme algorithms correctly: Elixir and Perl 6; which is not so much)
[1] https://developer.apple.com/support/apple-file-system/Apple-File-System-Reference.pdf
Signature · 2 lines
Pali Rohár [email protected]
Quoted 132 lines · Pali Rohár
Quoted 20 lines · On Tuesday 05 February 2019 14:08:00 Gabriel Krisman Bertazi wrote:
Quoted 18 lines · Pali Rohár
Quoted 16 lines · On Monday 28 January 2019 16:32:12 Gabriel Krisman Bertazi wrote:
The main change presented here is a proposal to migrate the normalization method from NFKD to NFD. After our discussions, and reviewing other operating systems and languages aspects, I am more convinced that canonical decomposition is more viable solution than compatibility decomposition, because it doesn't ignore eliminate any semantic meaning, like the definitive case of superscript numbers. NFD is also the documented method used by HFS+ and APFS, so there is precedent. Notice however, that as far as my research goes, APFS doesn't completely follows NFD, and in some cases, like <compat> flags, it actually does NFKD, but not in others (<fraction>), where it applies the canonical form. We take a more consistent approach and always do plain NFD.
This RFC, therefore, aims to resume/start conversation with some stalkeholders that may have something to say regarding the normalization method used. I added people from SMB, NFS and FS development who might be interested on this.
Quoted 7 lines
Quoted 5 lines
Hello! I think that choice of NFD normalization is not right decision. Some reasons:
1) NFD is not widely used. Even Apple does not use it (as you wrote Apple has own normalization form).
To be exact, Apple claims to use NFD in their specification [1] .
Interesting...
Quoted 4 lines
What I
observed is that they don't ignore some types of compatibility characters correctly as they should. For instance, the ff ligature is decomposed into f + f.I'm sure that Apple does not do NFD, but their own invented normal form. Some graphemes are decomposed, and some not.
Quoted 7 lines
Quoted 4 lines
2) All filesystems which I known either do not use any normalization or use NFC.
3) Lot of existing Linux application generate file names in NFC.Most do use NFC. But this is an internal representation for ext4 and it is name preserving.
Ok. I was in impression that it does not preserve original names, just like implementation in Apple's system, where char* passed to
creat()does not appear inreaddir().Quoted 3 lines
We only use the normalization when comparing if names matches and to calculate dcache and dx hashes. The unicode standard recomends the D forms for internal representation.
Ok, this should be less destructive and less visible to userspace.
Quoted 10 lines
Quoted 5 lines
4) Linux GUI libraries like Qt and Gtk generate strings from key strokes in NFC. So if user type file name in Qt/Gtk box it would be in NFC.
So why to use NFD in ext4 filesystem if Linux userspace ecosystem already uses NFC?
NFC is costlier to calculate, usually requiring an intermediate NFD step. Whether it is prohibitively expensive to do in the dcache path, I don't know, but since it is a critical path, any gain matters.
Quoted 6 lines
Quoted 2 lines
NFD here just makes another layer of problems, unexpected things and make it somehow different.
Is there any case where
NFC(x) == NFC(y) && NFD(x) != NFD(y) , or
NFC(x) != NFC(y) && NFD(x) == NFD(y)This is good question. And I think we should get definite answer for it prior inclusion of normalization into kernel.
Quoted 3 lines
I am having a hard time thinking of an example. This is the main (only?) scenario where choosing C or D form for an internal representation would affect userspace.
For decision between normal format, probably yes.
Quoted 16 lines
Quoted 10 lines
Why not rather choose NFS? It would be more compatible with Linux GUI applications and also with Microsoft Windows systems, which uses NFC too.
Please, really consider to not use NFD. Most Linux applications really do not do any normalization or do NFC. And usage of decomposition form for application which do not implement full Unicode grapheme algorithms just make for them another problems.
Quoted 5 lines
Yes, there are still lot of legacy application which expect that one code point = one visible symbol (therefore one Unicode grapheme). And because GUI in most cases generates NFC strings, also existing file names are in NFC, these application works in most cases without problem. Force usage of NFD filenames just break them.
Quoted 4 lines
As I said, this shouldn't be a problem because what the application creates and retrieves is the exact name that was used before, we'd only use this format for internal metadata on the disk (hashes) and for in-kernel comparisons.
There is another problem for userspace applications:
Currently ext4 accepts as file name any sequence of bytes which do not contain nul byte and '/'. So having Latin1 file name is perfectly correct.
What would happen if userspace application want to create following two file names? "\xDF" and "\F0"? First one is sharp S second one is eth (in Latin1). But file names are invalid UTF-8 sequences. Is it disallowed to create such file names? Or both file names are internally converted to "U+FFFD" (replacement character) and because NFD(first U+FFFD) == NFD(second U+FFFD) only first file would be created?
And what happen in general with invalid UTF-8 sequences? Because there are many different types of invalid UTF-8 sequences, like non-shortest sequence for valid code point, valid sequence for invalid code points (either surrogate pairs code points, or code points above U+10FFFF, ...), incorrect byte which should start new code point, incorrect byte when decoding of code point started, ...
Different (userspace) application handles these invalid UTF-8 sequences differently, some of them accept some kind of "incorrectness" (e.g. non-shortest form of code point representation), some not. Some applications replace invalid parts of UTF-8 sequence by sequence of UTF-8 replacement character, some not. Also it can be observed that some applications use just one replacement characters and some other replace invalid UTF-8 sequence by more replacement characters.
Quoted 3 lines
So trying to "recover" from invalid UTF-8 sequence to valid one is done in more ways... And usage of any existing way could cause problems... E.g. not possible to create two files "\xDF\xF0" and "\xF0\xDF"...
Basically there are 2 ways to sanely handle invalid utf-8 sequences inside the kernel. I don't see much gain in handling different levels of incorrectness. Opening up to "we now accept surrogate characters, but reject unmapped code points (which we must do, because of stability of future unicode versions)", makes everything much more unpredictable.
Anyway, two ways to handle invalid sequences...
- 1. An invalid filename can't exist in the disk. This means reject the sequence and fail the syscall when coming from the userspace, and flagging it as an error to be fixed by fsck when identifying any of these sequences already on the disk. This has obvious backward compatibility problems with applications that want to create filenames with invalid sequences.
- 2. An invalid filename can exist in the disk as a unique sequence. In this case, we must decide how to handle invalid sequences that eventually will appear. The only sane way is to consider the entire sequence an opaque byte sequence, essentially falling back to the old behavior, which prevents userspace breakage. We loose the normalization/casefold feature for that directory entry only, but the file is still accessible when using the exact match.
Any variant of these, like trying to fix invalid sequences or trying to do a partial normalization/casefold as a best effort are insane to do in kernel space.
Patch 09 already implements both of the sane behaviors. Through a flag in the file system, which defaults to the second case, ext4 will either reject or treat invalid sequences as opaque byte sequences.
There are more details about handling of invalid sequences in the patch description.
Signature · 1 line
Gabriel Krisman Bertazi
Quoted 138 lines · On Wednesday 06 February 2019 11:04:24 Gabriel Krisman Bertazi wrote:
Quoted 132 lines · Pali Rohár
Quoted 20 lines · On Tuesday 05 February 2019 14:08:00 Gabriel Krisman Bertazi wrote:
Quoted 18 lines · Pali Rohár
Quoted 16 lines · On Monday 28 January 2019 16:32:12 Gabriel Krisman Bertazi wrote:
The main change presented here is a proposal to migrate the normalization method from NFKD to NFD. After our discussions, and reviewing other operating systems and languages aspects, I am more convinced that canonical decomposition is more viable solution than compatibility decomposition, because it doesn't ignore eliminate any semantic meaning, like the definitive case of superscript numbers. NFD is also the documented method used by HFS+ and APFS, so there is precedent. Notice however, that as far as my research goes, APFS doesn't completely follows NFD, and in some cases, like <compat> flags, it actually does NFKD, but not in others (<fraction>), where it applies the canonical form. We take a more consistent approach and always do plain NFD.
This RFC, therefore, aims to resume/start conversation with some stalkeholders that may have something to say regarding the normalization method used. I added people from SMB, NFS and FS development who might be interested on this.
Quoted 7 lines
Quoted 5 lines
Hello! I think that choice of NFD normalization is not right decision. Some reasons:
1) NFD is not widely used. Even Apple does not use it (as you wrote Apple has own normalization form).
To be exact, Apple claims to use NFD in their specification [1] .
Interesting...
Quoted 4 lines
What I
observed is that they don't ignore some types of compatibility characters correctly as they should. For instance, the ff ligature is decomposed into f + f.I'm sure that Apple does not do NFD, but their own invented normal form. Some graphemes are decomposed, and some not.
Quoted 7 lines
Quoted 4 lines
2) All filesystems which I known either do not use any normalization or use NFC.
3) Lot of existing Linux application generate file names in NFC.Most do use NFC. But this is an internal representation for ext4 and it is name preserving.
Ok. I was in impression that it does not preserve original names, just like implementation in Apple's system, where char* passed to
creat()does not appear inreaddir().Quoted 3 lines
We only use the normalization when comparing if names matches and to calculate dcache and dx hashes. The unicode standard recomends the D forms for internal representation.
Ok, this should be less destructive and less visible to userspace.
Quoted 10 lines
Quoted 5 lines
4) Linux GUI libraries like Qt and Gtk generate strings from key strokes in NFC. So if user type file name in Qt/Gtk box it would be in NFC.
So why to use NFD in ext4 filesystem if Linux userspace ecosystem already uses NFC?
NFC is costlier to calculate, usually requiring an intermediate NFD step. Whether it is prohibitively expensive to do in the dcache path, I don't know, but since it is a critical path, any gain matters.
Quoted 6 lines
Quoted 2 lines
NFD here just makes another layer of problems, unexpected things and make it somehow different.
Is there any case where
NFC(x) == NFC(y) && NFD(x) != NFD(y) , or
NFC(x) != NFC(y) && NFD(x) == NFD(y)This is good question. And I think we should get definite answer for it prior inclusion of normalization into kernel.
Quoted 3 lines
I am having a hard time thinking of an example. This is the main (only?) scenario where choosing C or D form for an internal representation would affect userspace.
For decision between normal format, probably yes.
Quoted 16 lines
Quoted 10 lines
Why not rather choose NFS? It would be more compatible with Linux GUI applications and also with Microsoft Windows systems, which uses NFC too.
Please, really consider to not use NFD. Most Linux applications really do not do any normalization or do NFC. And usage of decomposition form for application which do not implement full Unicode grapheme algorithms just make for them another problems.
Quoted 5 lines
Yes, there are still lot of legacy application which expect that one code point = one visible symbol (therefore one Unicode grapheme). And because GUI in most cases generates NFC strings, also existing file names are in NFC, these application works in most cases without problem. Force usage of NFD filenames just break them.
Quoted 4 lines
As I said, this shouldn't be a problem because what the application creates and retrieves is the exact name that was used before, we'd only use this format for internal metadata on the disk (hashes) and for in-kernel comparisons.
There is another problem for userspace applications:
Currently ext4 accepts as file name any sequence of bytes which do not contain nul byte and '/'. So having Latin1 file name is perfectly correct.
What would happen if userspace application want to create following two file names? "\xDF" and "\F0"? First one is sharp S second one is eth (in Latin1). But file names are invalid UTF-8 sequences. Is it disallowed to create such file names? Or both file names are internally converted to "U+FFFD" (replacement character) and because NFD(first U+FFFD) == NFD(second U+FFFD) only first file would be created?
And what happen in general with invalid UTF-8 sequences? Because there are many different types of invalid UTF-8 sequences, like non-shortest sequence for valid code point, valid sequence for invalid code points (either surrogate pairs code points, or code points above U+10FFFF, ...), incorrect byte which should start new code point, incorrect byte when decoding of code point started, ...
Different (userspace) application handles these invalid UTF-8 sequences differently, some of them accept some kind of "incorrectness" (e.g. non-shortest form of code point representation), some not. Some applications replace invalid parts of UTF-8 sequence by sequence of UTF-8 replacement character, some not. Also it can be observed that some applications use just one replacement characters and some other replace invalid UTF-8 sequence by more replacement characters.
Quoted 3 lines
So trying to "recover" from invalid UTF-8 sequence to valid one is done in more ways... And usage of any existing way could cause problems... E.g. not possible to create two files "\xDF\xF0" and "\xF0\xDF"...
Quoted 5 lines
Basically there are 2 ways to sanely handle invalid utf-8 sequences inside the kernel. I don't see much gain in handling different levels of incorrectness. Opening up to "we now accept surrogate characters, but reject unmapped code points (which we must do, because of stability of future unicode versions)", makes everything much more unpredictable.
Yes, this just make lot of mess.
Quoted 8 lines
Anyway, two ways to handle invalid sequences...
- 1. An invalid filename can't exist in the disk. This means reject the sequence and fail the syscall when coming from the userspace, and flagging it as an error to be fixed by fsck when identifying any of these sequences already on the disk. This has obvious backward compatibility problems with applications that want to create filenames with invalid sequences.
Personally I'm for this variant. If directory is marked as "Unicode" I would expect that file names in that directory are in Unicode. And not mix of garbage (bytes, Latin1) and Unicode.
If directory is marked as Unicode and some application wants to store into that directory Latin1, I think it should be really prohibited. Otherwise, why such "Unicode" flag is there if it cannot be enforced?
Quoted 11 lines
- 2. An invalid filename can exist in the disk as a unique sequence. In this case, we must decide how to handle invalid sequences that eventually will appear. The only sane way is to consider the entire sequence an opaque byte sequence, essentially falling back to the old behavior, which prevents userspace breakage. We loose the normalization/casefold feature for that directory entry only, but the file is still accessible when using the exact match.
Any variant of these, like trying to fix invalid sequences or trying to do a partial normalization/casefold as a best effort are insane to do in kernel space.
+1
Quoted 7 lines
Patch 09 already implements both of the sane behaviors. Through a flag in the file system, which defaults to the second case, ext4 will either reject or treat invalid sequences as opaque byte sequences.
There are more details about handling of invalid sequences in the patch description.
Signature · 2 lines
Pali Rohár [email protected]
Quoted 12 lines · Gabriel Krisman Bertazi
Regarding Casefold, I am unsure whether Casefold Common + Full still makes sense after migrating from the compatibility to the canonical form. While Casefold Full, by definition, addresses cases where the casefolding grows in size, like the casefold of the german eszett to SS, it also is responsible for folding smallcase ligatures without a corresponding uppercase to their compatible counterpart. Which means that on -F directories,
o_f_f_i_c_eando_ff_i_c_ewill differ, while on +F directories they will match. This seems unaceptable to me, suggesting that we should start to use Common + Simple instead of Common
+ Full, but I would like more input on what seems more reasonable to you.
Quoted 5 lines
After we decide on this, I will be sending new patches to update e2fsprogs to the agreed method and remove the normalization/casefold type flags (
EXT4_UTF8_NORMALIZATION_TYPE_NFKD,EXT4_UTF8_CASEFOLD_TYPE_NFKDCF), before actually proposing the current patch series for inclusion in the kernel.
Hey Ted,
Any comments about this bit before I move on and propose a new version?
Signature · 1 line
Gabriel Krisman Bertazi