| Message ID | 20190813091326.84652-9-gaoxiang25@huawei.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | erofs: promote erofs from staging | expand |
Hi! > + /* > + * on-disk error, let's only BUG_ON in the debugging mode. > + * otherwise, it will return 1 to just skip the invalid name > + * and go on (in consideration of the lookup performance). > + */ > + DBG_BUGON(qd->name > qd->end); I believe you should check for errors in non-debug mode, too. > + if (unlikely(!ndirents)) { > + DBG_BUGON(1); > + kunmap_atomic(de); > + put_page(page); > + page = ERR_PTR(-EIO); > + goto out; > + } -EUCLEAN is right error code for corrupted filesystem. (And you probably want to print something to the syslog, too). Pavel
Hi Pavel, On Tue, Aug 13, 2019 at 01:48:21PM +0200, Pavel Machek wrote: > Hi! > > > + /* > > + * on-disk error, let's only BUG_ON in the debugging mode. > > + * otherwise, it will return 1 to just skip the invalid name > > + * and go on (in consideration of the lookup performance). > > + */ > > + DBG_BUGON(qd->name > qd->end); > > I believe you should check for errors in non-debug mode, too. Thanks for your kindly reply! The following is just my personal thought... If I am wrong, please kindly point out... As you can see, this is a new prefixed string binary search algorithm which can provide similar performance with hashed approach (but no need to store hash value at all), so I really care about its lookup performance. There is something needing to be concerned, is, whether namei() should report any potential on-disk issues or just return -ENOENT for these corrupted dirs, I think I tend to use the latter one. The reason (in my opinion) is if you consider another some another complicated non-transverse ondisk implementation, it cannot transverse all the entires so they could/couldn't report all potential issues in namei() (For such corrupted dir, they can return -ENOENT due to lack of information of course, just avoiding crashing the kernel is OK). Therefore, in my thought, such issue can be reported by fsck-like tools such as erofs.fsck. And actually readdir() will also report all issues as well, thus we can have performance gain on lookup. > > > > + if (unlikely(!ndirents)) { > > + DBG_BUGON(1); > > + kunmap_atomic(de); > > + put_page(page); > > + page = ERR_PTR(-EIO); > > + goto out; > > + } > > -EUCLEAN is right error code for corrupted filesystem. (And you > probably want to print something to the syslog, too). Yes, you are right :) -EUCLEAN/EFSCORRUPTED is actually for such thing, nowadays, EROFS treats all EFSCORRUPTED cases into EIO, and I will update that in one patch... (Yes, it needs to print something of course :)) Thanks, Gao Xiang > > Pavel > -- > DENX Software Engineering GmbH, Managing Director: Wolfgang Denk > HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
On Tue, Aug 13, 2019 at 08:23:32PM +0800, Gao Xiang wrote: > Hi Pavel, > > On Tue, Aug 13, 2019 at 01:48:21PM +0200, Pavel Machek wrote: [] > There is something needing to be concerned, is, whether namei() should > report any potential on-disk issues or just return -ENOENT for these > corrupted dirs, I think I tend to use the latter one. > Add a word, I didn't mean for any cases return -ENOENT, just this one only since this is the hottest path in every lookup. Other places should have reported any potential issues as much as possible if it finds. Thanks, Gao Xiang > > > > > Pavel > > -- > > DENX Software Engineering GmbH, Managing Director: Wolfgang Denk > > HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany > >
Hi! > > > + /* > > > + * on-disk error, let's only BUG_ON in the debugging mode. > > > + * otherwise, it will return 1 to just skip the invalid name > > > + * and go on (in consideration of the lookup performance). > > > + */ > > > + DBG_BUGON(qd->name > qd->end); > > > > I believe you should check for errors in non-debug mode, too. > > Thanks for your kindly reply! > > The following is just my personal thought... If I am wrong, please > kindly point out... > > As you can see, this is a new prefixed string binary search algorithm > which can provide similar performance with hashed approach (but no > need to store hash value at all), so I really care about its lookup > performance. > > There is something needing to be concerned, is, whether namei() should > report any potential on-disk issues or just return -ENOENT for these > corrupted dirs, I think I tend to use the latter one. -ENOENT is okay for corrupted directories, as long as corrupted directories do not cause some kind of security bugs (memory corruption, crashes, ...) Best regards, Pavel
Hi Pavel, On Thu, Aug 15, 2019 at 09:01:32AM +0200, Pavel Machek wrote: > Hi! > > > > > + /* > > > > + * on-disk error, let's only BUG_ON in the debugging mode. > > > > + * otherwise, it will return 1 to just skip the invalid name > > > > + * and go on (in consideration of the lookup performance). > > > > + */ > > > > + DBG_BUGON(qd->name > qd->end); > > > > > > I believe you should check for errors in non-debug mode, too. > > > > Thanks for your kindly reply! > > > > The following is just my personal thought... If I am wrong, please > > kindly point out... > > > > As you can see, this is a new prefixed string binary search algorithm > > which can provide similar performance with hashed approach (but no > > need to store hash value at all), so I really care about its lookup > > performance. > > > > There is something needing to be concerned, is, whether namei() should > > report any potential on-disk issues or just return -ENOENT for these > > corrupted dirs, I think I tend to use the latter one. > > -ENOENT is okay for corrupted directories, as long as corrupted > directories do not cause some kind of security bugs (memory > corruption, crashes, ...) Yes, I am certain that it will return -ENOENT for such corrupted directories and it will certainly not crash the kernel as well. I have fuzzed it for several months and it seems fine after commit 419d6efc50e9 ("staging: erofs: keep corrupted fs from crashing kernel in erofs_namei()") Don't worry about that :) Thanks, Gao Xiang > > > Best regards, > Pavel > -- > DENX Software Engineering GmbH, Managing Director: Wolfgang Denk > HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
diff --git a/fs/erofs/namei.c b/fs/erofs/namei.c new file mode 100644 index 000000000000..73bf61637907 --- /dev/null +++ b/fs/erofs/namei.c @@ -0,0 +1,247 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* + * linux/fs/erofs/namei.c + * + * Copyright (C) 2017-2018 HUAWEI, Inc. + * http://www.huawei.com/ + * Created by Gao Xiang <gaoxiang25@huawei.com> + */ +#include "internal.h" + +#include <trace/events/erofs.h> + +struct erofs_qstr { + const unsigned char *name; + const unsigned char *end; +}; + +/* based on the end of qn is accurate and it must have the trailing '\0' */ +static inline int dirnamecmp(const struct erofs_qstr *qn, + const struct erofs_qstr *qd, + unsigned int *matched) +{ + unsigned int i = *matched; + + /* + * on-disk error, let's only BUG_ON in the debugging mode. + * otherwise, it will return 1 to just skip the invalid name + * and go on (in consideration of the lookup performance). + */ + DBG_BUGON(qd->name > qd->end); + + /* qd could not have trailing '\0' */ + /* However it is absolutely safe if < qd->end */ + while (qd->name + i < qd->end && qd->name[i] != '\0') { + if (qn->name[i] != qd->name[i]) { + *matched = i; + return qn->name[i] > qd->name[i] ? 1 : -1; + } + ++i; + } + *matched = i; + /* See comments in __d_alloc on the terminating NUL character */ + return qn->name[i] == '\0' ? 0 : 1; +} + +#define nameoff_from_disk(off, sz) (le16_to_cpu(off) & ((sz) - 1)) + +static struct erofs_dirent *find_target_dirent(struct erofs_qstr *name, + u8 *data, + unsigned int dirblksize, + const int ndirents) +{ + int head, back; + unsigned int startprfx, endprfx; + struct erofs_dirent *const de = (struct erofs_dirent *)data; + + /* since the 1st dirent has been evaluated previously */ + head = 1; + back = ndirents - 1; + startprfx = endprfx = 0; + + while (head <= back) { + const int mid = head + (back - head) / 2; + const int nameoff = nameoff_from_disk(de[mid].nameoff, + dirblksize); + unsigned int matched = min(startprfx, endprfx); + struct erofs_qstr dname = { + .name = data + nameoff, + .end = unlikely(mid >= ndirents - 1) ? + data + dirblksize : + data + nameoff_from_disk(de[mid + 1].nameoff, + dirblksize) + }; + + /* string comparison without already matched prefix */ + int ret = dirnamecmp(name, &dname, &matched); + + if (unlikely(!ret)) { + return de + mid; + } else if (ret > 0) { + head = mid + 1; + startprfx = matched; + } else { + back = mid - 1; + endprfx = matched; + } + } + + return ERR_PTR(-ENOENT); +} + +static struct page *find_target_block_classic(struct inode *dir, + struct erofs_qstr *name, + int *_ndirents) +{ + unsigned int startprfx, endprfx; + int head, back; + struct address_space *const mapping = dir->i_mapping; + struct page *candidate = ERR_PTR(-ENOENT); + + startprfx = endprfx = 0; + head = 0; + back = inode_datablocks(dir) - 1; + + while (head <= back) { + const int mid = head + (back - head) / 2; + struct page *page = read_mapping_page(mapping, mid, NULL); + + if (!IS_ERR(page)) { + struct erofs_dirent *de = kmap_atomic(page); + const int nameoff = nameoff_from_disk(de->nameoff, + EROFS_BLKSIZ); + const int ndirents = nameoff / sizeof(*de); + int diff; + unsigned int matched; + struct erofs_qstr dname; + + if (unlikely(!ndirents)) { + DBG_BUGON(1); + kunmap_atomic(de); + put_page(page); + page = ERR_PTR(-EIO); + goto out; + } + + matched = min(startprfx, endprfx); + + dname.name = (u8 *)de + nameoff; + if (ndirents == 1) + dname.end = (u8 *)de + EROFS_BLKSIZ; + else + dname.end = (u8 *)de + + nameoff_from_disk(de[1].nameoff, + EROFS_BLKSIZ); + + /* string comparison without already matched prefix */ + diff = dirnamecmp(name, &dname, &matched); + kunmap_atomic(de); + + if (unlikely(!diff)) { + *_ndirents = 0; + goto out; + } else if (diff > 0) { + head = mid + 1; + startprfx = matched; + + if (!IS_ERR(candidate)) + put_page(candidate); + candidate = page; + *_ndirents = ndirents; + } else { + put_page(page); + + back = mid - 1; + endprfx = matched; + } + continue; + } +out: /* free if the candidate is valid */ + if (!IS_ERR(candidate)) + put_page(candidate); + return page; + } + return candidate; +} + +int erofs_namei(struct inode *dir, + struct qstr *name, + erofs_nid_t *nid, unsigned int *d_type) +{ + int ndirents; + struct page *page; + void *data; + struct erofs_dirent *de; + struct erofs_qstr qn; + + if (unlikely(!dir->i_size)) + return -ENOENT; + + qn.name = name->name; + qn.end = name->name + name->len; + + ndirents = 0; + page = find_target_block_classic(dir, &qn, &ndirents); + + if (IS_ERR(page)) + return PTR_ERR(page); + + data = kmap_atomic(page); + /* the target page has been mapped */ + if (ndirents) + de = find_target_dirent(&qn, data, EROFS_BLKSIZ, ndirents); + else + de = (struct erofs_dirent *)data; + + if (!IS_ERR(de)) { + *nid = le64_to_cpu(de->nid); + *d_type = de->file_type; + } + + kunmap_atomic(data); + put_page(page); + + return PTR_ERR_OR_ZERO(de); +} + +/* NOTE: i_mutex is already held by vfs */ +static struct dentry *erofs_lookup(struct inode *dir, + struct dentry *dentry, + unsigned int flags) +{ + int err; + erofs_nid_t nid; + unsigned int d_type; + struct inode *inode; + + DBG_BUGON(!d_really_is_negative(dentry)); + /* dentry must be unhashed in lookup, no need to worry about */ + DBG_BUGON(!d_unhashed(dentry)); + + trace_erofs_lookup(dir, dentry, flags); + + /* file name exceeds fs limit */ + if (unlikely(dentry->d_name.len > EROFS_NAME_LEN)) + return ERR_PTR(-ENAMETOOLONG); + + /* false uninitialized warnings on gcc 4.8.x */ + err = erofs_namei(dir, &dentry->d_name, &nid, &d_type); + + if (err == -ENOENT) { + /* negative dentry */ + inode = NULL; + } else if (unlikely(err)) { + inode = ERR_PTR(err); + } else { + debugln("%s, %s (nid %llu) found, d_type %u", __func__, + dentry->d_name.name, nid, d_type); + inode = erofs_iget(dir->i_sb, nid, d_type == EROFS_FT_DIR); + } + return d_splice_alias(inode, dentry); +} + +const struct inode_operations erofs_dir_iops = { + .lookup = erofs_lookup, + .getattr = erofs_getattr, +}; +
This commit adds functions that transfer names to inodes. Signed-off-by: Gao Xiang <gaoxiang25@huawei.com> --- fs/erofs/namei.c | 247 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 247 insertions(+) create mode 100644 fs/erofs/namei.c