Determine whether a directory is empty or not for ext2 file system

How do we determine whether a directory is empty or not for ext2 file system?

first,let’s take a look at a implementation in linux kernel(2.6.11):

/*
 * routine to check that the specified directory is empty (for rmdir)
 */
int ext2_empty_dir (struct inode * inode)
{
	struct page *page = NULL;
	unsigned long i, npages = dir_pages(inode);

	for (i = 0; i < npages; i++) {
		char *kaddr;
		ext2_dirent * de;
		page = ext2_get_page(inode, i);

		if (IS_ERR(page))
			continue;

		kaddr = page_address(page);
		de = (ext2_dirent *)kaddr;
		kaddr += ext2_last_byte(inode, i) - EXT2_DIR_REC_LEN(1);

		while ((char *)de <= kaddr) { if (de->rec_len == 0) {
				ext2_error(inode->i_sb, __FUNCTION__,
					"zero-length directory entry");
				printk("kaddr=%p, de=%p\n", kaddr, de);
				goto not_empty;
			}
			if (de->inode != 0) {
				/* check for . and .. */
				if (de->name[0] != '.')
					goto not_empty;
				if (de->name_len > 2)
					goto not_empty;
				if (de->name_len < 2) { if (de->inode !=
					    cpu_to_le32(inode->i_ino))
						goto not_empty;
				} else if (de->name[1] != '.')
					goto not_empty;
			}
			de = ext2_next_entry(de);
		}
		ext2_put_page(page);
	}
	return 1;

not_empty:
	ext2_put_page(page);
	return 0;
}

the code is easy to understand, it iterates all entries of a directory inode, if an inode number is not zero, and its name is not ‘.’ or ‘..’, that means this directory is not empty. it is a way that can solve the problem, but i think it is not the best, or efficient.

in ext2 spec, there is a variable called i_links_count in struct ext2_inode, why don’t we use it? some one may argue that it stands for the hard link number of this inode, but in fact, this value is updated when you create or delete an entry in this directory every time. so, we can use it to determine whether it is an empty directory or not:

	if (inode->i_link_cnt > 2){
		return -1;
	}

and i use it in my ext2 driver, it works so pretty fast.

UPDATE: in Linux world, this value is updated when a sub-directory is created in a directory, thus in order to be compatible with it, i updated my code.

/*
 * -1 not empty
 *
 */
int ext2_dir_empty(vnode_t *vnode, ext2_i_t *inode, int inode_no)
{
	ext2_fs_t *fs = (ext2_fs_t *)vnode->v_mp->fsdata;
	char *block_buf = NULL;
	int retval, i, offset;
	int block_nr;
	ext2_dir_t *de;

	/*
	 * this is a hack when a directory
	 * has a sub-directory. not empty
	 */
	if (inode->i_link_cnt > 2){
		return -1;	//not empty
	}

	i = inode->i_size / fs->blksize;

	block_buf = (char *)kmalloc(fs->blksize);
	assert(block_buf != NULL);

	for (block_nr=0; block_nr < i; block_nr++) {
		offset = 0;
		retval = ext2_inode_read_block(vnode, inode, block_nr, block_buf);
		if (retval <= 0){
			goto END;
		}
		de = (ext2_dir_t *)block_buf;
		for (;;){
			if (de->d_inode != 0){
				if (de->d_name[0] != '.')
					goto not_empty;
				if (de->d_name_len > 2)
					goto not_empty;
				if (de->d_name_len < 2){
					if (de->d_inode != inode_no)
						goto not_empty;
				} else if (de->d_name[1] != '.')
					goto not_empty;

			}
			offset += de->d_reclen;
			//BugFix:2014.06.25
			//de = (ext2_dir_t *)((char *)de + EXT2_DIR_REAL_LEN(de->d_name_len));
			de = ext2_next_entry(de);
			if (offset > fs->blksize) {
				break;
			}
		}
	}

	retval = 0;
	goto END;

not_empty:
	retval = -1;
END:
	kfree(block_buf);
	return retval;
}

Leave a Reply

Your email address will not be published.