Messages in this thread Patch in this message | | | Date | Wed, 12 Aug 1998 04:51:59 +0200 (MET DST) | From | Andries.Brouwer@cwi ... | Subject | [PATCH] quadratic behaviour in ext2 |
| |
Below a patch on fs/ext2/namei.c. People have been complaining about the large number of calls of ext2_check_dir_entry. The patch below changes the number of calls for "du -s ." in my home directory from 7239339 to 74725. Discussion below the patch.
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
| |