4 * Copyright (C) 1992, 1993, 1994, 1995
5 * Remy Card (card@masi.ibp.fr)
6 * Laboratoire MASI - Institut Blaise Pascal
7 * Universite Pierre et Marie Curie (Paris VI)
11 * linux/fs/minix/dir.c
13 * Copyright (C) 1991, 1992 Linus Torvalds
15 * ext2 directory handling functions
17 * Big-endian to little-endian byte-swapping/bitmaps by
18 * David S. Miller (davem@caip.rutgers.edu), 1995
20 * All code that works with directory layout had been switched to pagecache
25 #include <linux/ext2_fs.h>
26 #include <linux/pagemap.h>
28 typedef struct ext2_dir_entry_2 ext2_dirent;
31 * ext2 uses block-sized chunks. Arguably, sector-sized ones would be
32 * more robust, but we have what we have
34 static inline unsigned ext2_chunk_size(struct inode *inode)
36 return inode->i_sb->s_blocksize;
39 static inline void ext2_put_page(struct page *page)
42 page_cache_release(page);
45 static inline unsigned long dir_pages(struct inode *inode)
47 return (inode->i_size+PAGE_CACHE_SIZE-1)>>PAGE_CACHE_SHIFT;
50 static int ext2_commit_chunk(struct page *page, unsigned from, unsigned to)
52 struct inode *dir = page->mapping->host;
54 dir->i_version = ++event;
55 page->mapping->a_ops->commit_write(NULL, page, from, to);
58 err = writeout_one_page(page);
59 err2 = waitfor_one_page(page);
66 static void ext2_check_page(struct page *page)
68 struct inode *dir = page->mapping->host;
69 struct super_block *sb = dir->i_sb;
70 unsigned chunk_size = ext2_chunk_size(dir);
71 char *kaddr = page_address(page);
72 u32 max_inumber = le32_to_cpu(sb->u.ext2_sb.s_es->s_inodes_count);
73 unsigned offs, rec_len;
74 unsigned limit = PAGE_CACHE_SIZE;
78 if ((dir->i_size >> PAGE_CACHE_SHIFT) == page->index) {
79 limit = dir->i_size & ~PAGE_CACHE_MASK;
80 if (limit & (chunk_size - 1))
82 for (offs = limit; offs<PAGE_CACHE_SIZE; offs += chunk_size) {
83 ext2_dirent *p = (ext2_dirent*)(kaddr + offs);
84 p->rec_len = cpu_to_le16(chunk_size);
89 for (offs = 0; offs <= limit - EXT2_DIR_REC_LEN(1); offs += rec_len) {
90 p = (ext2_dirent *)(kaddr + offs);
91 rec_len = le16_to_cpu(p->rec_len);
93 if (rec_len < EXT2_DIR_REC_LEN(1))
97 if (rec_len < EXT2_DIR_REC_LEN(p->name_len))
99 if (((offs + rec_len - 1) ^ offs) & ~(chunk_size-1))
101 if (le32_to_cpu(p->inode) > max_inumber)
107 SetPageChecked(page);
110 /* Too bad, we had an error */
113 ext2_error(sb, "ext2_check_page",
114 "size of directory #%lu is not a multiple of chunk size",
119 error = "rec_len is smaller than minimal";
122 error = "unaligned directory entry";
125 error = "rec_len is too small for name_len";
128 error = "directory entry across blocks";
131 error = "inode out of bounds";
133 ext2_error (sb, "ext2_check_page", "bad entry in directory #%lu: %s - "
134 "offset=%lu, inode=%lu, rec_len=%d, name_len=%d",
135 dir->i_ino, error, (page->index<<PAGE_CACHE_SHIFT)+offs,
136 (unsigned long) le32_to_cpu(p->inode),
137 rec_len, p->name_len);
140 p = (ext2_dirent *)(kaddr + offs);
141 ext2_error (sb, "ext2_check_page",
142 "entry in directory #%lu spans the page boundary"
143 "offset=%lu, inode=%lu",
144 dir->i_ino, (page->index<<PAGE_CACHE_SHIFT)+offs,
145 (unsigned long) le32_to_cpu(p->inode));
147 SetPageChecked(page);
151 static struct page * ext2_get_page(struct inode *dir, unsigned long n)
153 struct address_space *mapping = dir->i_mapping;
154 struct page *page = read_cache_page(mapping, n,
155 (filler_t*)mapping->a_ops->readpage, NULL);
159 if (!Page_Uptodate(page))
161 if (!PageChecked(page))
162 ext2_check_page(page);
170 return ERR_PTR(-EIO);
174 * NOTE! unlike strncmp, ext2_match returns 1 for success, 0 for failure.
176 * len <= EXT2_NAME_LEN and de != NULL are guaranteed by caller.
178 static inline int ext2_match (int len, const char * const name,
179 struct ext2_dir_entry_2 * de)
181 if (len != de->name_len)
185 return !memcmp(name, de->name, len);
189 * p is at least 6 bytes before the end of page
191 static inline ext2_dirent *ext2_next_entry(ext2_dirent *p)
193 return (ext2_dirent *)((char*)p + le16_to_cpu(p->rec_len));
196 static inline unsigned
197 ext2_validate_entry(char *base, unsigned offset, unsigned mask)
199 ext2_dirent *de = (ext2_dirent*)(base + offset);
200 ext2_dirent *p = (ext2_dirent*)(base + (offset&mask));
201 while ((char*)p < (char*)de)
202 p = ext2_next_entry(p);
203 return (char *)p - base;
206 static unsigned char ext2_filetype_table[EXT2_FT_MAX] = {
207 [EXT2_FT_UNKNOWN] DT_UNKNOWN,
208 [EXT2_FT_REG_FILE] DT_REG,
209 [EXT2_FT_DIR] DT_DIR,
210 [EXT2_FT_CHRDEV] DT_CHR,
211 [EXT2_FT_BLKDEV] DT_BLK,
212 [EXT2_FT_FIFO] DT_FIFO,
213 [EXT2_FT_SOCK] DT_SOCK,
214 [EXT2_FT_SYMLINK] DT_LNK,
218 static unsigned char ext2_type_by_mode[S_IFMT >> S_SHIFT] = {
219 [S_IFREG >> S_SHIFT] EXT2_FT_REG_FILE,
220 [S_IFDIR >> S_SHIFT] EXT2_FT_DIR,
221 [S_IFCHR >> S_SHIFT] EXT2_FT_CHRDEV,
222 [S_IFBLK >> S_SHIFT] EXT2_FT_BLKDEV,
223 [S_IFIFO >> S_SHIFT] EXT2_FT_FIFO,
224 [S_IFSOCK >> S_SHIFT] EXT2_FT_SOCK,
225 [S_IFLNK >> S_SHIFT] EXT2_FT_SYMLINK,
228 static inline void ext2_set_de_type(ext2_dirent *de, struct inode *inode)
230 mode_t mode = inode->i_mode;
231 if (EXT2_HAS_INCOMPAT_FEATURE(inode->i_sb, EXT2_FEATURE_INCOMPAT_FILETYPE))
232 de->file_type = ext2_type_by_mode[(mode & S_IFMT)>>S_SHIFT];
238 ext2_readdir (struct file * filp, void * dirent, filldir_t filldir)
240 loff_t pos = filp->f_pos;
241 struct inode *inode = filp->f_dentry->d_inode;
242 struct super_block *sb = inode->i_sb;
243 unsigned offset = pos & ~PAGE_CACHE_MASK;
244 unsigned long n = pos >> PAGE_CACHE_SHIFT;
245 unsigned long npages = dir_pages(inode);
246 unsigned chunk_mask = ~(ext2_chunk_size(inode)-1);
247 unsigned char *types = NULL;
248 int need_revalidate = (filp->f_version != inode->i_version);
250 if (pos > inode->i_size - EXT2_DIR_REC_LEN(1))
253 if (EXT2_HAS_INCOMPAT_FEATURE(sb, EXT2_FEATURE_INCOMPAT_FILETYPE))
254 types = ext2_filetype_table;
256 for ( ; n < npages; n++, offset = 0) {
259 struct page *page = ext2_get_page(inode, n);
263 kaddr = page_address(page);
264 if (need_revalidate) {
265 offset = ext2_validate_entry(kaddr, offset, chunk_mask);
268 de = (ext2_dirent *)(kaddr+offset);
269 limit = kaddr + PAGE_CACHE_SIZE - EXT2_DIR_REC_LEN(1);
270 for ( ;(char*)de <= limit; de = ext2_next_entry(de))
273 unsigned char d_type = DT_UNKNOWN;
275 if (types && de->file_type < EXT2_FT_MAX)
276 d_type = types[de->file_type];
278 offset = (char *)de - kaddr;
279 over = filldir(dirent, de->name, de->name_len,
280 (n<<PAGE_CACHE_SHIFT) | offset,
281 le32_to_cpu(de->inode), d_type);
291 filp->f_pos = (n << PAGE_CACHE_SHIFT) | offset;
292 filp->f_version = inode->i_version;
300 * finds an entry in the specified directory with the wanted name. It
301 * returns the page in which the entry was found, and the entry itself
302 * (as a parameter - res_dir). Page is returned mapped and unlocked.
303 * Entry is guaranteed to be valid.
305 struct ext2_dir_entry_2 * ext2_find_entry (struct inode * dir,
306 struct dentry *dentry, struct page ** res_page)
308 const char *name = dentry->d_name.name;
309 int namelen = dentry->d_name.len;
310 unsigned reclen = EXT2_DIR_REC_LEN(namelen);
311 unsigned long start, n;
312 unsigned long npages = dir_pages(dir);
313 struct page *page = NULL;
319 start = dir->u.ext2_i.i_dir_start_lookup;
325 page = ext2_get_page(dir, n);
327 kaddr = page_address(page);
328 de = (ext2_dirent *) kaddr;
329 kaddr += PAGE_CACHE_SIZE - reclen;
330 while ((char *) de <= kaddr) {
331 if (ext2_match (namelen, name, de))
333 de = ext2_next_entry(de);
339 } while (n != start);
344 dir->u.ext2_i.i_dir_start_lookup = n;
348 struct ext2_dir_entry_2 * ext2_dotdot (struct inode *dir, struct page **p)
350 struct page *page = ext2_get_page(dir, 0);
351 ext2_dirent *de = NULL;
354 de = ext2_next_entry((ext2_dirent *) page_address(page));
360 ino_t ext2_inode_by_name(struct inode * dir, struct dentry *dentry)
363 struct ext2_dir_entry_2 * de;
366 de = ext2_find_entry (dir, dentry, &page);
368 res = le32_to_cpu(de->inode);
370 page_cache_release(page);
375 /* Releases the page */
376 void ext2_set_link(struct inode *dir, struct ext2_dir_entry_2 *de,
377 struct page *page, struct inode *inode)
379 unsigned from = (char *) de - (char *) page_address(page);
380 unsigned to = from + le16_to_cpu(de->rec_len);
384 err = page->mapping->a_ops->prepare_write(NULL, page, from, to);
387 de->inode = cpu_to_le32(inode->i_ino);
388 ext2_set_de_type (de, inode);
389 err = ext2_commit_chunk(page, from, to);
392 dir->i_mtime = dir->i_ctime = CURRENT_TIME;
393 dir->u.ext2_i.i_flags &= ~EXT2_BTREE_FL;
394 mark_inode_dirty(dir);
400 int ext2_add_link (struct dentry *dentry, struct inode *inode)
402 struct inode *dir = dentry->d_parent->d_inode;
403 const char *name = dentry->d_name.name;
404 int namelen = dentry->d_name.len;
405 unsigned reclen = EXT2_DIR_REC_LEN(namelen);
406 unsigned short rec_len, name_len;
407 struct page *page = NULL;
409 unsigned long npages = dir_pages(dir);
415 /* We take care of directory expansion in the same loop */
416 for (n = 0; n <= npages; n++) {
417 page = ext2_get_page(dir, n);
421 kaddr = page_address(page);
422 de = (ext2_dirent *)kaddr;
423 kaddr += PAGE_CACHE_SIZE - reclen;
424 while ((char *)de <= kaddr) {
426 if (ext2_match (namelen, name, de))
428 name_len = EXT2_DIR_REC_LEN(de->name_len);
429 rec_len = le16_to_cpu(de->rec_len);
430 if (!de->inode && rec_len >= reclen)
432 if (rec_len >= name_len + reclen)
434 de = (ext2_dirent *) ((char *) de + rec_len);
442 from = (char*)de - (char*)page_address(page);
445 err = page->mapping->a_ops->prepare_write(NULL, page, from, to);
449 ext2_dirent *de1 = (ext2_dirent *) ((char *) de + name_len);
450 de1->rec_len = cpu_to_le16(rec_len - name_len);
451 de->rec_len = cpu_to_le16(name_len);
454 de->name_len = namelen;
455 memcpy (de->name, name, namelen);
456 de->inode = cpu_to_le32(inode->i_ino);
457 ext2_set_de_type (de, inode);
458 err = ext2_commit_chunk(page, from, to);
459 dir->i_mtime = dir->i_ctime = CURRENT_TIME;
460 dir->u.ext2_i.i_flags &= ~EXT2_BTREE_FL;
461 mark_inode_dirty(dir);
472 * ext2_delete_entry deletes a directory entry by merging it with the
473 * previous entry. Page is up-to-date. Releases the page.
475 int ext2_delete_entry (struct ext2_dir_entry_2 * dir, struct page * page )
477 struct address_space *mapping = page->mapping;
478 struct inode *inode = mapping->host;
479 char *kaddr = page_address(page);
480 unsigned from = ((char*)dir - kaddr) & ~(ext2_chunk_size(inode)-1);
481 unsigned to = ((char*)dir - kaddr) + le16_to_cpu(dir->rec_len);
482 ext2_dirent * pde = NULL;
483 ext2_dirent * de = (ext2_dirent *) (kaddr + from);
486 while ((char*)de < (char*)dir) {
488 de = ext2_next_entry(de);
491 from = (char*)pde - (char*)page_address(page);
493 err = mapping->a_ops->prepare_write(NULL, page, from, to);
497 pde->rec_len = cpu_to_le16(to-from);
499 err = ext2_commit_chunk(page, from, to);
502 inode->i_ctime = inode->i_mtime = CURRENT_TIME;
503 inode->u.ext2_i.i_flags &= ~EXT2_BTREE_FL;
504 mark_inode_dirty(inode);
509 * Set the first fragment of directory.
511 int ext2_make_empty(struct inode *inode, struct inode *parent)
513 struct address_space *mapping = inode->i_mapping;
514 struct page *page = grab_cache_page(mapping, 0);
515 unsigned chunk_size = ext2_chunk_size(inode);
516 struct ext2_dir_entry_2 * de;
522 err = mapping->a_ops->prepare_write(NULL, page, 0, chunk_size);
526 base = page_address(page);
528 de = (struct ext2_dir_entry_2 *) base;
530 de->rec_len = cpu_to_le16(EXT2_DIR_REC_LEN(1));
531 memcpy (de->name, ".\0\0", 4);
532 de->inode = cpu_to_le32(inode->i_ino);
533 ext2_set_de_type (de, inode);
535 de = (struct ext2_dir_entry_2 *) (base + EXT2_DIR_REC_LEN(1));
537 de->rec_len = cpu_to_le16(chunk_size - EXT2_DIR_REC_LEN(1));
538 de->inode = cpu_to_le32(parent->i_ino);
539 memcpy (de->name, "..\0", 4);
540 ext2_set_de_type (de, inode);
542 err = ext2_commit_chunk(page, 0, chunk_size);
545 page_cache_release(page);
550 * routine to check that the specified directory is empty (for rmdir)
552 int ext2_empty_dir (struct inode * inode)
554 struct page *page = NULL;
555 unsigned long i, npages = dir_pages(inode);
557 for (i = 0; i < npages; i++) {
560 page = ext2_get_page(inode, i);
565 kaddr = page_address(page);
566 de = (ext2_dirent *)kaddr;
567 kaddr += PAGE_CACHE_SIZE-EXT2_DIR_REC_LEN(1);
569 while ((char *)de <= kaddr) {
570 if (de->inode != 0) {
571 /* check for . and .. */
572 if (de->name[0] != '.')
574 if (de->name_len > 2)
576 if (de->name_len < 2) {
578 cpu_to_le32(inode->i_ino))
580 } else if (de->name[1] != '.')
583 de = ext2_next_entry(de);
594 struct file_operations ext2_dir_operations = {
595 read: generic_read_dir,
596 readdir: ext2_readdir,
598 fsync: ext2_sync_file,