Hi xiang,
On 2019/2/15 16:58, Gao Xiang wrote:
> Hi Chao,
>
> On 2019/2/15 15:02, Chao Yu wrote:
>> 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?
>
> Make sense, it is only used for debugging mode, let me send another patch later...
>
>>
>> So will it be better to return directly here?
>>
>> if (unlikely(qd->name >= qd->end)) {
>> DBG_BUGON(1);
>> return 1;
>> }
>
> Corrupted image is rare happened in normal systems, I tend to only use
> DBG_BUGON here, and qn->name[i] is of course not '\0', so it will return 1;
If the image is corrupted, qn->name[i] may be anything, as you commented
above DBG_BUGON(), we really don't need to go through any later codes, it
can avoid potentially encoutnering wrong condition.
* otherwise, it will return 1 to just skip the invalid name
>
>>
>>> +
>>> + /* 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()?
>
> Yes, you are right. However, find_target_dirent is now totally designed in page unit
> because of get_meta_page usage, but find_target_dirent doesn't.
>
> I think if we support sub-page feature later (by using iomap or someelse), it
> could be added later.
No problem, it's not a big deal. :)
Thanks,
>
> Thanks,
> Gao Xiang
>
>
>>
>> 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;
>>> }
>>>
>>
>
> .
>
