diff -u -r ../linux-2.1.115/linux/fs/ext2/namei.c linux/fs/ext2/namei.c
--- ../linux-2.1.115/linux/fs/ext2/namei.c Sat May 9 02:54:39 1998
+++ linux/fs/ext2/namei.c Wed Aug 12 03:30:53 1998
@@ -41,14 +41,17 @@
/*
* NOTE! unlike strncmp, ext2_match returns 1 for success, 0 for failure.
+ *
+ * `len <= EXT2_NAME_LEN' is guaranteed by caller.
+ * `de != NULL' is guaranteed by caller.
*/
static inline int ext2_match (int len, const char * const name,
struct ext2_dir_entry_2 * de)
{
- if (!de || !le32_to_cpu(de->inode) || len > EXT2_NAME_LEN)
- return 0;
if (len != de->name_len)
return 0;
+ if (!le32_to_cpu(de->inode))
+ return 0;
return !memcmp(name, de->name, len);
}
@@ -121,10 +124,17 @@
de = (struct ext2_dir_entry_2 *) bh->b_data;
dlimit = bh->b_data + sb->s_blocksize;
while ((char *) de < dlimit) {
- if (!ext2_check_dir_entry ("ext2_find_entry", dir,
- de, bh, offset))
- goto failure;
- if (ext2_match (namelen, name, de)) {
+ /* this code is executed quadratically often */
+ /* do minimal checking `by hand' */
+ int de_len;
+
+ if ((char *) de + namelen <= dlimit &&
+ ext2_match (namelen, name, de)) {
+ /* found a match -
+ just to be sure, do a full check */
+ if (!ext2_check_dir_entry("ext2_find_entry",
+ dir, de, bh, offset))
+ goto failure;
for (i = 0; i < NAMEI_RA_SIZE; ++i) {
if (bh_use[i] != bh)
brelse (bh_use[i]);
@@ -132,9 +142,13 @@
*res_dir = de;
return bh;
}
- offset += le16_to_cpu(de->rec_len);
+ /* prevent looping on a bad block */
+ de_len = le16_to_cpu(de->rec_len);
+ if (de_len <= 0)
+ goto failure;
+ offset += de_len;
de = (struct ext2_dir_entry_2 *)
- ((char *) de + le16_to_cpu(de->rec_len));
+ ((char *) de + de_len);
}
brelse (bh);
------------------------------------------------------------------------
Discussion.
The large number of calls of ext2_check_dir_entry() is entirely
due to the routine ext2_find_entry(). If some program needs
to find all entries in a directory with 1000 files, then for
the 1st file it calls ext2_check_dir_entry() once, for the 2nd
twice, ..., for the last file a thousand times, for a total of
half a million calls. In other words, quadratic behaviour.
Now each call takes a very short time, but quadratic always
wins over linear, so for sufficiently large directories the kernel
will spend more time on ext2_check_dir_entry() than on disk I/O.
What to do? Tell the user that she should not have large directories.
But there are these big news spool directories. Use B-trees or so.
But that is a project for a different file system. Hmm.
First of all there is some polishing one can do.
The routine ext2_match() is called precisely twice.
For both calls, reading the source reveals that we already
tested `namelen > EXT2_NAME_LEN', and we need not repeat this.
Both calls are preceded by calls of ext2_check_dir_entry(),
and these dereference de, so if the code was correct then we
know that de is non-NULL and testing that again is meaningless.
So far about ext2_match().
Next about this call of ext2_check_dir_entry() in ext2_find_entry().
It does not do anything. It is `just to be sure'. It will print
an error message if it detects a bad directory block, and do nothing
if all is OK.
Let us split this functionality. Suppose the directory block is rotten.
Preferably, that should not lead to a kernel crash. So we need a
minimal amount of checking to keep the kernel sane.
In the patch above these are the parts `(char *) de + namelen <= dlimit'
that guarantee that the following ext2_match will not touch memory
outside the block just read, and `de_len > 0' which guarantees that
we make progress, and cannot get stuck looping in a bad block.
What about bad directory entry detection?
Well, the patch above detects a bad directory entry only
if it is the one we were looking for. For a scan over all
files in the directory this means that each entry is tested
only once instead of many times. Moreover, ext2_readdir()
still does full checking.
So, it seems that we are not really less safe than before.
------------------------------------------------------------------------
Meta discussion.
Changing the ext2 filesystem code is a hazardous thing to do.
It is very important that this code is rock solid. That is
why I give my reasoning in such a detail. I hope that many
people who know ext2 will scrutinize the patch carefully
and make sure (i) that for a correct filesystem it is equivalent
to the old code, and (ii) that for an incorrect filesystem the
expected behaviour is not worse than it was before.
Of course the patch is meaningless if it does not bring
a measurable improvement. Above I gave a statistic on the number
of calls. I have no timing statistics.
Andries
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.altern.org/andrebalsa/doc/lkml-faq.html