1 files changed, 78 insertions, 89 deletions
diff --git a/drivers/staging/erofs/namei.c b/drivers/staging/erofs/namei.c
index a1300c420e63..5596c52e246d 100644
--- a/drivers/staging/erofs/namei.c
+++ b/drivers/staging/erofs/namei.c
@@ -15,76 +15,74 @@
 #include <trace/events/erofs.h>
-struct erofs_qstr {
+/* based on the value of qn->len is accurate */
-        const unsigned char *name;
+static inline int dirnamecmp(struct qstr *qn,
-        const unsigned char *end;
+        struct qstr *qd, unsigned int *matched)
-};
-/* 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;
+        unsigned int i = *matched, len = min(qn->len, qd->len);
+loop:
-        /*
+        if (unlikely(i >= len)) {
-         * on-disk error, let's only BUG_ON in the debugging mode.
+                *matched = i;
-         * otherwise, it will return 1 to just skip the invalid name
+                if (qn->len < qd->len) {
-         * and go on (in consideration of the lookup performance).
+                        /*
-         */
+                         * actually (qn->len == qd->len)
-        DBG_BUGON(qd->name > qd->end);
+                         * when qd->name[i] == '\0'
+                         */
-        /* qd could not have trailing '\0' */
+                        return qd->name[i] == '\0' ? 0 : -1;
-        /* 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;
+                return (qn->len > qd->len);
+        }
+        if (qn->name[i] != qd->name[i]) {
+                *matched = i;
+                return qn->name[i] > qd->name[i] ? 1 : -1;
        }
-        *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))
+        ++i;
+        goto loop;
+}
-static struct erofs_dirent *find_target_dirent(struct erofs_qstr *name,
+static struct erofs_dirent *find_target_dirent(
-                                               u8 *data,
+        struct qstr *name,
-                                               unsigned int dirblksize,
+        u8 *data, int maxsize)
-                                               const int ndirents)
 {
-        int head, back;
+        unsigned int ndirents, 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;
        back = ndirents - 1;
        startprfx = endprfx = 0;
        while (head <= back) {
-                const int mid = head + (back - head) / 2;
+                unsigned int mid = head + (back - head) / 2;
-                const int nameoff = nameoff_from_disk(de[mid].nameoff,
+                unsigned int nameoff = le16_to_cpu(de[mid].nameoff);
-                                                      dirblksize);
                unsigned int matched = min(startprfx, endprfx);
-                struct erofs_qstr dname = {
-                        .name = data + nameoff,
+                struct qstr dname = QSTR_INIT(data + nameoff,
-                        .end = unlikely(mid >= ndirents - 1) ?
+                        unlikely(mid >= ndirents - 1) ?
-                                data + dirblksize :
+                                maxsize - nameoff :
-                                data + nameoff_from_disk(de[mid + 1].nameoff,
+                                le16_to_cpu(de[mid + 1].nameoff) - 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 {
+                } else if (unlikely(mid < 1))   /* fix "mid" overflow */
+                        break;
+                else {
                        back = mid - 1;
                        endprfx = matched;
                }
@@ -93,13 +91,12 @@ static struct erofs_dirent *find_target_dirent(struct erofs_qstr *name,
        return ERR_PTR(-ENOENT);
 }
-static struct page *find_target_block_classic(struct inode *dir,
+static struct page *find_target_block_classic(
-                                              struct erofs_qstr *name,
+        struct inode *dir,
-                                              int *_diff,
+        struct qstr *name, int *_diff)
-                                              int *_ndirents)
 {
        unsigned int startprfx, endprfx;
-        int head, back;
+        unsigned int head, back;
        struct address_space *const mapping = dir->i_mapping;
        struct page *candidate = ERR_PTR(-ENOENT);
@@ -108,34 +105,33 @@ static struct page *find_target_block_classic(struct inode *dir,
        back = inode_datablocks(dir) - 1;
        while (head <= back) {
-                const int mid = head + (back - head) / 2;
+                unsigned int mid = head + (back - head) / 2;
                struct page *page = read_mapping_page(mapping, mid, NULL);
-                if (!IS_ERR(page)) {
+                if (IS_ERR(page)) {
-                        struct erofs_dirent *de = kmap_atomic(page);
+exact_out:
-                        const int nameoff = nameoff_from_disk(de->nameoff,
+                        if (!IS_ERR(candidate)) /* valid candidate */
-                                                              EROFS_BLKSIZ);
+                                put_page(candidate);
-                        const int ndirents = nameoff / sizeof(*de);
+                        return page;
+                } else {
                        int diff;
-                        unsigned int matched;
+                        unsigned int ndirents, matched;
-                        struct erofs_qstr dname;
+                        struct qstr dname;
+                        struct erofs_dirent *de = kmap_atomic(page);
+                        unsigned int nameoff = le16_to_cpu(de->nameoff);
-                        if (unlikely(!ndirents)) {
+                        ndirents = nameoff / sizeof(*de);
-                                DBG_BUGON(1);
-                                put_page(page);
+                        /* corrupted dir (should have one entry at least) */
-                                page = ERR_PTR(-EIO);
+                        BUG_ON(!ndirents || nameoff > PAGE_SIZE);
-                                goto out;
-                        }
                        matched = min(startprfx, endprfx);
                        dname.name = (u8 *)de + nameoff;
-                        if (ndirents == 1)
+                        dname.len = ndirents == 1 ?
-                                dname.end = (u8 *)de + EROFS_BLKSIZ;
+                                /* since the rest of the last page is 0 */
-                        else
+                                EROFS_BLKSIZ - nameoff
-                                dname.end = (u8 *)de +
+                                : le16_to_cpu(de[1].nameoff) - nameoff;
-                                        nameoff_from_disk(de[1].nameoff,
-                                                          EROFS_BLKSIZ);
                        /* string comparison without already matched prefix */
                        diff = dirnamecmp(name, &dname, &matched);
@@ -143,7 +139,7 @@ static struct page *find_target_block_classic(struct inode *dir,
                        if (unlikely(!diff)) {
                                *_diff = 0;
-                                goto out;
+                                goto exact_out;
                        } else if (diff > 0) {
                                head = mid + 1;
                                startprfx = matched;
@@ -151,42 +147,35 @@ static struct page *find_target_block_classic(struct inode *dir,
                                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,
+        struct qstr *name,
-                erofs_nid_t *nid, unsigned int *d_type)
+        erofs_nid_t *nid, unsigned int *d_type)
 {
-        int diff, ndirents;
+        int diff;
        struct page *page;
        u8 *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;
        diff = 1;
-        page = find_target_block_classic(dir, &qn, &diff, &ndirents);
+        page = find_target_block_classic(dir, name, &diff);
        if (unlikely(IS_ERR(page)))
                return PTR_ERR(page);
@@ -195,7 +184,7 @@ int erofs_namei(struct inode *dir,
        /* the target page has been mapped */
        de = likely(diff) ?
                /* since the rest of the last page is 0 */
-                find_target_dirent(&qn, data, EROFS_BLKSIZ, ndirents) :
+                find_target_dirent(name, data, EROFS_BLKSIZ) :
                (struct erofs_dirent *)data;
        if (likely(!IS_ERR(de))) {

diff --git a/drivers/staging/erofs/namei.c b/drivers/staging/erofs/namei.c index a1300c420e63..5596c52e246d 100644 --- a/drivers/staging/erofs/namei.c +++ b/drivers/staging/erofs/namei.c
@@ -15,76 +15,74 @@
15		15
16	#include <trace/events/erofs.h>	16	#include <trace/events/erofs.h>
17		17
18	struct erofs_qstr {	18	/* based on the value of qn->len is accurate */
19	const unsigned char *name;	19	static inline int dirnamecmp(struct qstr *qn,
20	const unsigned char *end;	20	struct qstr qd, unsigned int matched)
21	};
22
23	/* based on the end of qn is accurate and it must have the trailing '\0' */
24	static inline int dirnamecmp(const struct erofs_qstr *qn,
25	const struct erofs_qstr *qd,
26	unsigned int *matched)
27	{	21	{
28	unsigned int i = *matched;	22	unsigned int i = *matched, len = min(qn->len, qd->len);
29		23	loop:
30	/*	24	if (unlikely(i >= len)) {
31	* on-disk error, let's only BUG_ON in the debugging mode.	25	*matched = i;
32	* otherwise, it will return 1 to just skip the invalid name	26	if (qn->len < qd->len) {
33	* and go on (in consideration of the lookup performance).	27	/*
34	*/	28	* actually (qn->len == qd->len)
35	DBG_BUGON(qd->name > qd->end);	29	* when qd->name[i] == '\0'
36		30	*/
37	/* qd could not have trailing '\0' */	31	return qd->name[i] == '\0' ? 0 : -1;
38	/* However it is absolutely safe if < qd->end */
39	while (qd->name + i < qd->end && qd->name[i] != '\0') {
40	if (qn->name[i] != qd->name[i]) {
41	*matched = i;
42	return qn->name[i] > qd->name[i] ? 1 : -1;
43	}	32	}
44	++i;	33	return (qn->len > qd->len);
		34	}
		35
		36	if (qn->name[i] != qd->name[i]) {
		37	*matched = i;
		38	return qn->name[i] > qd->name[i] ? 1 : -1;
45	}	39	}
46	*matched = i;
47	/* See comments in __d_alloc on the terminating NUL character */
48	return qn->name[i] == '\0' ? 0 : 1;
49	}
50		40
51	#define nameoff_from_disk(off, sz) (le16_to_cpu(off) & ((sz) - 1))	41	++i;
		42	goto loop;
		43	}
52		44
53	static struct erofs_dirent find_target_dirent(struct erofs_qstr name,	45	static struct erofs_dirent *find_target_dirent(
54	u8 *data,	46	struct qstr *name,
55	unsigned int dirblksize,	47	u8 *data, int maxsize)
56	const int ndirents)
57	{	48	{
58	int head, back;	49	unsigned int ndirents, head, back;
59	unsigned int startprfx, endprfx;	50	unsigned int startprfx, endprfx;
60	struct erofs_dirent const de = (struct erofs_dirent )data;	51	struct erofs_dirent const de = (struct erofs_dirent )data;
61		52
		53	/* make sure that maxsize is valid */
		54	BUG_ON(maxsize < sizeof(struct erofs_dirent));
		55
		56	ndirents = le16_to_cpu(de->nameoff) / sizeof(*de);
		57
		58	/* corrupted dir (may be unnecessary...) */
		59	BUG_ON(!ndirents);
		60
62	head = 0;	61	head = 0;
63	back = ndirents - 1;	62	back = ndirents - 1;
64	startprfx = endprfx = 0;	63	startprfx = endprfx = 0;
65		64
66	while (head <= back) {	65	while (head <= back) {
67	const int mid = head + (back - head) / 2;	66	unsigned int mid = head + (back - head) / 2;
68	const int nameoff = nameoff_from_disk(de[mid].nameoff,	67	unsigned int nameoff = le16_to_cpu(de[mid].nameoff);
69	dirblksize);
70	unsigned int matched = min(startprfx, endprfx);	68	unsigned int matched = min(startprfx, endprfx);
71	struct erofs_qstr dname = {	69
72	.name = data + nameoff,	70	struct qstr dname = QSTR_INIT(data + nameoff,
73	.end = unlikely(mid >= ndirents - 1) ?	71	unlikely(mid >= ndirents - 1) ?
74	data + dirblksize :	72	maxsize - nameoff :
75	data + nameoff_from_disk(de[mid + 1].nameoff,	73	le16_to_cpu(de[mid + 1].nameoff) - nameoff);
76	dirblksize)
77	};
78		74
79	/* string comparison without already matched prefix */	75	/* string comparison without already matched prefix */
80	int ret = dirnamecmp(name, &dname, &matched);	76	int ret = dirnamecmp(name, &dname, &matched);
81		77
82	if (unlikely(!ret)) {	78	if (unlikely(!ret))
83	return de + mid;	79	return de + mid;
84	} else if (ret > 0) {	80	else if (ret > 0) {
85	head = mid + 1;	81	head = mid + 1;
86	startprfx = matched;	82	startprfx = matched;
87	} else {	83	} else if (unlikely(mid < 1)) /* fix "mid" overflow */
		84	break;
		85	else {
88	back = mid - 1;	86	back = mid - 1;
89	endprfx = matched;	87	endprfx = matched;
90	}	88	}
@@ -93,13 +91,12 @@ static struct erofs_dirent find_target_dirent(struct erofs_qstr name,
93	return ERR_PTR(-ENOENT);	91	return ERR_PTR(-ENOENT);
94	}	92	}
95		93
96	static struct page find_target_block_classic(struct inode dir,	94	static struct page *find_target_block_classic(
97	struct erofs_qstr *name,	95	struct inode *dir,
98	int *_diff,	96	struct qstr name, int _diff)
99	int *_ndirents)
100	{	97	{
101	unsigned int startprfx, endprfx;	98	unsigned int startprfx, endprfx;
102	int head, back;	99	unsigned int head, back;
103	struct address_space *const mapping = dir->i_mapping;	100	struct address_space *const mapping = dir->i_mapping;
104	struct page *candidate = ERR_PTR(-ENOENT);	101	struct page *candidate = ERR_PTR(-ENOENT);
105		102
@@ -108,34 +105,33 @@ static struct page find_target_block_classic(struct inode dir,
108	back = inode_datablocks(dir) - 1;	105	back = inode_datablocks(dir) - 1;
109		106
110	while (head <= back) {	107	while (head <= back) {
111	const int mid = head + (back - head) / 2;	108	unsigned int mid = head + (back - head) / 2;
112	struct page *page = read_mapping_page(mapping, mid, NULL);	109	struct page *page = read_mapping_page(mapping, mid, NULL);
113		110
114	if (!IS_ERR(page)) {	111	if (IS_ERR(page)) {
115	struct erofs_dirent *de = kmap_atomic(page);	112	exact_out:
116	const int nameoff = nameoff_from_disk(de->nameoff,	113	if (!IS_ERR(candidate)) /* valid candidate */
117	EROFS_BLKSIZ);	114	put_page(candidate);
118	const int ndirents = nameoff / sizeof(*de);	115	return page;
		116	} else {
119	int diff;	117	int diff;
120	unsigned int matched;	118	unsigned int ndirents, matched;
121	struct erofs_qstr dname;	119	struct qstr dname;
		120	struct erofs_dirent *de = kmap_atomic(page);
		121	unsigned int nameoff = le16_to_cpu(de->nameoff);
122		122
123	if (unlikely(!ndirents)) {	123	ndirents = nameoff / sizeof(*de);
124	DBG_BUGON(1);	124
125	put_page(page);	125	/* corrupted dir (should have one entry at least) */
126	page = ERR_PTR(-EIO);	126	BUG_ON(!ndirents \|\| nameoff > PAGE_SIZE);
127	goto out;
128	}
129		127
130	matched = min(startprfx, endprfx);	128	matched = min(startprfx, endprfx);
131		129
132	dname.name = (u8 *)de + nameoff;	130	dname.name = (u8 *)de + nameoff;
133	if (ndirents == 1)	131	dname.len = ndirents == 1 ?
134	dname.end = (u8 *)de + EROFS_BLKSIZ;	132	/* since the rest of the last page is 0 */
135	else	133	EROFS_BLKSIZ - nameoff
136	dname.end = (u8 *)de +	134	: le16_to_cpu(de[1].nameoff) - nameoff;
137	nameoff_from_disk(de[1].nameoff,
138	EROFS_BLKSIZ);
139		135
140	/* string comparison without already matched prefix */	136	/* string comparison without already matched prefix */
141	diff = dirnamecmp(name, &dname, &matched);	137	diff = dirnamecmp(name, &dname, &matched);
@@ -143,7 +139,7 @@ static struct page find_target_block_classic(struct inode dir,
143		139
144	if (unlikely(!diff)) {	140	if (unlikely(!diff)) {
145	*_diff = 0;	141	*_diff = 0;
146	goto out;	142	goto exact_out;
147	} else if (diff > 0) {	143	} else if (diff > 0) {
148	head = mid + 1;	144	head = mid + 1;
149	startprfx = matched;	145	startprfx = matched;
@@ -151,42 +147,35 @@ static struct page find_target_block_classic(struct inode dir,
151	if (likely(!IS_ERR(candidate)))	147	if (likely(!IS_ERR(candidate)))
152	put_page(candidate);	148	put_page(candidate);
153	candidate = page;	149	candidate = page;
154	*_ndirents = ndirents;
155	} else {	150	} else {
156	put_page(page);	151	put_page(page);
157		152
		153	if (unlikely(mid < 1)) /* fix "mid" overflow */
		154	break;
		155
158	back = mid - 1;	156	back = mid - 1;
159	endprfx = matched;	157	endprfx = matched;
160	}	158	}
161	continue;
162	}	159	}
163	out: /* free if the candidate is valid */
164	if (!IS_ERR(candidate))
165	put_page(candidate);
166	return page;
167	}	160	}
168	*_diff = 1;	161	*_diff = 1;
169	return candidate;	162	return candidate;
170	}	163	}
171		164
172	int erofs_namei(struct inode *dir,	165	int erofs_namei(struct inode *dir,
173	struct qstr *name,	166	struct qstr *name,
174	erofs_nid_t nid, unsigned int d_type)	167	erofs_nid_t nid, unsigned int d_type)
175	{	168	{
176	int diff, ndirents;	169	int diff;
177	struct page *page;	170	struct page *page;
178	u8 *data;	171	u8 *data;
179	struct erofs_dirent *de;	172	struct erofs_dirent *de;
180	struct erofs_qstr qn;
181		173
182	if (unlikely(!dir->i_size))	174	if (unlikely(!dir->i_size))
183	return -ENOENT;	175	return -ENOENT;
184		176
185	qn.name = name->name;
186	qn.end = name->name + name->len;
187
188	diff = 1;	177	diff = 1;
189	page = find_target_block_classic(dir, &qn, &diff, &ndirents);	178	page = find_target_block_classic(dir, name, &diff);
190		179
191	if (unlikely(IS_ERR(page)))	180	if (unlikely(IS_ERR(page)))
192	return PTR_ERR(page);	181	return PTR_ERR(page);
@@ -195,7 +184,7 @@ int erofs_namei(struct inode *dir,
195	/* the target page has been mapped */	184	/* the target page has been mapped */
196	de = likely(diff) ?	185	de = likely(diff) ?
197	/* since the rest of the last page is 0 */	186	/* since the rest of the last page is 0 */
198	find_target_dirent(&qn, data, EROFS_BLKSIZ, ndirents) :	187	find_target_dirent(name, data, EROFS_BLKSIZ) :
199	(struct erofs_dirent *)data;	188	(struct erofs_dirent *)data;
200		189
201	if (likely(!IS_ERR(de))) {	190	if (likely(!IS_ERR(de))) {