On 2019/2/1 20:16, Gao Xiang wrote:
> As Al pointed out, "
> ... and while we are at it, what happens to
> unsigned int nameoff = le16_to_cpu(de[mid].nameoff);
> unsigned int matched = min(startprfx, endprfx);
>
> struct qstr dname = QSTR_INIT(data + nameoff,
> unlikely(mid >= ndirents - 1) ?
> maxsize - nameoff :
> le16_to_cpu(de[mid + 1].nameoff) - nameoff);
>
> /* string comparison without already matched prefix */
> int ret = dirnamecmp(name, &dname, &matched);
> if le16_to_cpu(de[...].nameoff) is not monotonically increasing? I.e.
> what's to prevent e.g. (unsigned)-1 ending up in dname.len?
>
> Corrupted fs image shouldn't oops the kernel.. "
>
> Revisit the related lookup flow to address the issue.
>
> Fixes: d72d1ce60174 ("staging: erofs: add namei functions")
> Cc: <stable@xxxxxxxxxxxxxxx> # 4.19+
> Suggested-by: Al Viro <viro@xxxxxxxxxxxxxxxxxx>
> Signed-off-by: Gao Xiang <gaoxiang25@xxxxxxxxxx>
> ---
> [ It should be better get reviewed first and for linux-next... ]
>
> change log v2:
> - fix the missing "kunmap_atomic" pointed out by Dan;
> - minor cleanup;
>
> drivers/staging/erofs/namei.c | 187 ++++++++++++++++++++++--------------------
> 1 file changed, 99 insertions(+), 88 deletions(-)
>
> diff --git a/drivers/staging/erofs/namei.c b/drivers/staging/erofs/namei.c
> index 5596c52e246d..321c881d720f 100644
> --- a/drivers/staging/erofs/namei.c
> +++ b/drivers/staging/erofs/namei.c
> @@ -15,74 +15,77 @@
>
> #include <trace/events/erofs.h>
>
> -/* based on the value of qn->len is accurate */
> -static inline int dirnamecmp(struct qstr *qn,
> - struct qstr *qd, unsigned int *matched)
> +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, len = min(qn->len, qd->len);
> -loop:
> - if (unlikely(i >= len)) {
> - *matched = i;
> - if (qn->len < qd->len) {
> - /*
> - * actually (qn->len == qd->len)
> - * when qd->name[i] == '\0'
> - */
> - return qd->name[i] == '\0' ? 0 : -1;
> + 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->name == qd->end is not allowed as well?
So will it be better to return directly here?
if (unlikely(qd->name >= qd->end)) {
DBG_BUGON(1);
return 1;
}
> +
> + /* 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;
> }
> - return (qn->len > qd->len);
> + ++i;
> }
> -
> - if (qn->name[i] != qd->name[i]) {
> - *matched = i;
> - return qn->name[i] > qd->name[i] ? 1 : -1;
> - }
> -
> - ++i;
> - goto loop;
> + *matched = i;
> + /* See comments in __d_alloc on the terminating NUL character */
> + return qn->name[i] == '\0' ? 0 : 1;
> }
>
> -static struct erofs_dirent *find_target_dirent(
> - struct qstr *name,
> - u8 *data, int maxsize)
> +#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)
> {
> - unsigned int ndirents, head, back;
> + int head, back;
> unsigned int startprfx, endprfx;
> struct erofs_dirent *const de = (struct erofs_dirent *)data;
>
> - /* make sure that maxsize is valid */
> - BUG_ON(maxsize < sizeof(struct erofs_dirent));
> -
> - ndirents = le16_to_cpu(de->nameoff) / sizeof(*de);
> -
> - /* corrupted dir (may be unnecessary...) */
> - BUG_ON(!ndirents);
> -
> - head = 0;
> + /* since the 1st dirent has been evaluated previously */
> + head = 1;
> back = ndirents - 1;
> startprfx = endprfx = 0;
>
> while (head <= back) {
> - unsigned int mid = head + (back - head) / 2;
> - unsigned int nameoff = le16_to_cpu(de[mid].nameoff);
> + const int mid = head + (back - head) / 2;
> + const int nameoff = nameoff_from_disk(de[mid].nameoff,
> + dirblksize);
> unsigned int matched = min(startprfx, endprfx);
> -
> - struct qstr dname = QSTR_INIT(data + nameoff,
> - unlikely(mid >= ndirents - 1) ?
> - maxsize - nameoff :
> - le16_to_cpu(de[mid + 1].nameoff) - nameoff);
> + 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))
> + if (unlikely(!ret)) {
> return de + mid;
> - else if (ret > 0) {
> + } else if (ret > 0) {
> head = mid + 1;
> startprfx = matched;
> - } else if (unlikely(mid < 1)) /* fix "mid" overflow */
> - break;
> - else {
> + } else {
> back = mid - 1;
> endprfx = matched;
> }
> @@ -91,12 +94,12 @@ static struct erofs_dirent *find_target_dirent(
> return ERR_PTR(-ENOENT);
> }
>
> -static struct page *find_target_block_classic(
> - struct inode *dir,
> - struct qstr *name, int *_diff)
> +static struct page *find_target_block_classic(struct inode *dir,
> + struct erofs_qstr *name,
> + int *_ndirents)
> {
> unsigned int startprfx, endprfx;
> - unsigned int head, back;
> + int head, back;
> struct address_space *const mapping = dir->i_mapping;
> struct page *candidate = ERR_PTR(-ENOENT);
>
> @@ -105,41 +108,43 @@ static struct page *find_target_block_classic(
> back = inode_datablocks(dir) - 1;
>
> while (head <= back) {
> - unsigned int mid = head + (back - head) / 2;
> + const int mid = head + (back - head) / 2;
> struct page *page = read_mapping_page(mapping, mid, NULL);
>
> - if (IS_ERR(page)) {
> -exact_out:
> - if (!IS_ERR(candidate)) /* valid candidate */
> - put_page(candidate);
> - return page;
> - } else {
> - int diff;
> - unsigned int ndirents, matched;
> - struct qstr dname;
> + if (!IS_ERR(page)) {
> struct erofs_dirent *de = kmap_atomic(page);
> - unsigned int nameoff = le16_to_cpu(de->nameoff);
> -
> - ndirents = nameoff / sizeof(*de);
> + 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;
>
> - /* corrupted dir (should have one entry at least) */
> - BUG_ON(!ndirents || nameoff > PAGE_SIZE);
> + 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;
> - dname.len = ndirents == 1 ?
> - /* since the rest of the last page is 0 */
> - EROFS_BLKSIZ - nameoff
> - : le16_to_cpu(de[1].nameoff) - 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)) {
> - *_diff = 0;
> - goto exact_out;
> + *_ndirents = 0;
> + goto out;
> } else if (diff > 0) {
> head = mid + 1;
> startprfx = matched;
> @@ -147,47 +152,53 @@ static struct page *find_target_block_classic(
> if (likely(!IS_ERR(candidate)))
> put_page(candidate);
> candidate = page;
> + *_ndirents = ndirents;
> } else {
> put_page(page);
>
> - if (unlikely(mid < 1)) /* fix "mid" overflow */
> - break;
> -
> back = mid - 1;
> endprfx = matched;
> }
> + continue;
> }
> +out: /* free if the candidate is valid */
> + if (!IS_ERR(candidate))
> + put_page(candidate);
> + return page;
> }
> - *_diff = 1;
> return candidate;
> }
>
> int erofs_namei(struct inode *dir,
> - struct qstr *name,
> - erofs_nid_t *nid, unsigned int *d_type)
> + struct qstr *name,
> + erofs_nid_t *nid, unsigned int *d_type)
> {
> - int diff;
> + int ndirents;
> struct page *page;
> - u8 *data;
> + void *data;
> struct erofs_dirent *de;
> + struct erofs_qstr qn;
>
> if (unlikely(!dir->i_size))
> return -ENOENT;
>
> - diff = 1;
> - page = find_target_block_classic(dir, name, &diff);
> + qn.name = name->name;
> + qn.end = name->name + name->len;
> +
> + ndirents = 0;
> + page = find_target_block_classic(dir, &qn, &ndirents);
>
> - if (unlikely(IS_ERR(page)))
> + if (IS_ERR(page))
> return PTR_ERR(page);
>
> data = kmap_atomic(page);
> /* the target page has been mapped */
> - de = likely(diff) ?
> - /* since the rest of the last page is 0 */
> - find_target_dirent(name, data, EROFS_BLKSIZ) :
> - (struct erofs_dirent *)data;
> + if (ndirents)
> + de = find_target_dirent(&qn, data, EROFS_BLKSIZ, ndirents);
If we want to support different blksize during dirent lookup, how about
adding parameter for find_target_block_classic() as find_target_dirent()?
Thanks,
> + else
> + de = (struct erofs_dirent *)data;
>
> - if (likely(!IS_ERR(de))) {
> + if (!IS_ERR(de)) {
> *nid = le64_to_cpu(de->nid);
> *d_type = de->file_type;
> }
>
