Blame view
fs/ext3/dir.c
13.6 KB
1da177e4c Linux-2.6.12-rc2 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
/* * linux/fs/ext3/dir.c * * Copyright (C) 1992, 1993, 1994, 1995 * Remy Card (card@masi.ibp.fr) * Laboratoire MASI - Institut Blaise Pascal * Universite Pierre et Marie Curie (Paris VI) * * from * * linux/fs/minix/dir.c * * Copyright (C) 1991, 1992 Linus Torvalds * * ext3 directory handling functions * * Big-endian to little-endian byte-swapping/bitmaps by * David S. Miller (davem@caip.rutgers.edu), 1995 * * Hash Tree Directory indexing (c) 2001 Daniel Phillips * */ #include <linux/fs.h> #include <linux/jbd.h> #include <linux/ext3_fs.h> #include <linux/buffer_head.h> |
1da177e4c Linux-2.6.12-rc2 |
28 29 30 31 32 33 34 35 36 37 38 39 |
#include <linux/slab.h> #include <linux/rbtree.h> static unsigned char ext3_filetype_table[] = { DT_UNKNOWN, DT_REG, DT_DIR, DT_CHR, DT_BLK, DT_FIFO, DT_SOCK, DT_LNK }; static int ext3_readdir(struct file *, void *, filldir_t); static int ext3_dx_readdir(struct file * filp, void * dirent, filldir_t filldir); static int ext3_release_dir (struct inode * inode, struct file * filp); |
4b6f5d20b [PATCH] Make most... |
40 |
const struct file_operations ext3_dir_operations = { |
1da177e4c Linux-2.6.12-rc2 |
41 42 43 |
.llseek = generic_file_llseek, .read = generic_read_dir, .readdir = ext3_readdir, /* we take BKL. needed?*/ |
039fd8ce6 ext3: remove the ... |
44 |
.unlocked_ioctl = ext3_ioctl, |
52a700c56 [PATCH] BLOCK: Mo... |
45 46 47 |
#ifdef CONFIG_COMPAT .compat_ioctl = ext3_compat_ioctl, #endif |
1da177e4c Linux-2.6.12-rc2 |
48 |
.fsync = ext3_sync_file, /* BKL held */ |
1da177e4c Linux-2.6.12-rc2 |
49 |
.release = ext3_release_dir, |
1da177e4c Linux-2.6.12-rc2 |
50 51 52 53 54 55 56 57 58 59 60 |
}; static unsigned char get_dtype(struct super_block *sb, int filetype) { if (!EXT3_HAS_INCOMPAT_FEATURE(sb, EXT3_FEATURE_INCOMPAT_FILETYPE) || (filetype >= EXT3_FT_MAX)) return DT_UNKNOWN; return (ext3_filetype_table[filetype]); } |
ae6ddcc5f [PATCH] ext3 and ... |
61 |
|
1da177e4c Linux-2.6.12-rc2 |
62 63 64 65 66 67 68 |
int ext3_check_dir_entry (const char * function, struct inode * dir, struct ext3_dir_entry_2 * de, struct buffer_head * bh, unsigned long offset) { const char * error_msg = NULL; |
7c06a8dc6 Fix 64KB blocksiz... |
69 |
const int rlen = ext3_rec_len_from_disk(de->rec_len); |
1da177e4c Linux-2.6.12-rc2 |
70 |
|
a4ae30948 ext3: speed up fi... |
71 |
if (unlikely(rlen < EXT3_DIR_REC_LEN(1))) |
1da177e4c Linux-2.6.12-rc2 |
72 |
error_msg = "rec_len is smaller than minimal"; |
a4ae30948 ext3: speed up fi... |
73 |
else if (unlikely(rlen % 4 != 0)) |
1da177e4c Linux-2.6.12-rc2 |
74 |
error_msg = "rec_len % 4 != 0"; |
a4ae30948 ext3: speed up fi... |
75 |
else if (unlikely(rlen < EXT3_DIR_REC_LEN(de->name_len))) |
1da177e4c Linux-2.6.12-rc2 |
76 |
error_msg = "rec_len is too small for name_len"; |
a4ae30948 ext3: speed up fi... |
77 |
else if (unlikely((((char *) de - bh->b_data) + rlen > dir->i_sb->s_blocksize))) |
1da177e4c Linux-2.6.12-rc2 |
78 |
error_msg = "directory entry across blocks"; |
a4ae30948 ext3: speed up fi... |
79 80 |
else if (unlikely(le32_to_cpu(de->inode) > le32_to_cpu(EXT3_SB(dir->i_sb)->s_es->s_inodes_count))) |
1da177e4c Linux-2.6.12-rc2 |
81 |
error_msg = "inode out of bounds"; |
a4ae30948 ext3: speed up fi... |
82 |
if (unlikely(error_msg != NULL)) |
1da177e4c Linux-2.6.12-rc2 |
83 84 85 86 87 88 |
ext3_error (dir->i_sb, function, "bad entry in directory #%lu: %s - " "offset=%lu, inode=%lu, rec_len=%d, name_len=%d", dir->i_ino, error_msg, offset, (unsigned long) le32_to_cpu(de->inode), rlen, de->name_len); |
a4ae30948 ext3: speed up fi... |
89 |
|
1da177e4c Linux-2.6.12-rc2 |
90 91 92 93 94 95 96 |
return error_msg == NULL ? 1 : 0; } static int ext3_readdir(struct file * filp, void * dirent, filldir_t filldir) { int error = 0; |
d8733c295 [PATCH] ext3_read... |
97 98 99 100 |
unsigned long offset; int i, stored; struct ext3_dir_entry_2 *de; struct super_block *sb; |
1da177e4c Linux-2.6.12-rc2 |
101 |
int err; |
fe21a6938 [PATCH] ext3: cha... |
102 |
struct inode *inode = filp->f_path.dentry->d_inode; |
1da177e4c Linux-2.6.12-rc2 |
103 |
int ret = 0; |
cdbf6dba2 ext3: avoid print... |
104 |
int dir_has_error = 0; |
1da177e4c Linux-2.6.12-rc2 |
105 106 |
sb = inode->i_sb; |
1da177e4c Linux-2.6.12-rc2 |
107 108 109 110 111 112 113 114 115 116 117 118 119 |
if (EXT3_HAS_COMPAT_FEATURE(inode->i_sb, EXT3_FEATURE_COMPAT_DIR_INDEX) && ((EXT3_I(inode)->i_flags & EXT3_INDEX_FL) || ((inode->i_size >> sb->s_blocksize_bits) == 1))) { err = ext3_dx_readdir(filp, dirent, filldir); if (err != ERR_BAD_DX_DIR) { ret = err; goto out; } /* * We don't set the inode dirty flag since it's not * critical that it get flushed back to the disk. */ |
fe21a6938 [PATCH] ext3: cha... |
120 |
EXT3_I(filp->f_path.dentry->d_inode)->i_flags &= ~EXT3_INDEX_FL; |
1da177e4c Linux-2.6.12-rc2 |
121 |
} |
1da177e4c Linux-2.6.12-rc2 |
122 |
stored = 0; |
1da177e4c Linux-2.6.12-rc2 |
123 124 125 |
offset = filp->f_pos & (sb->s_blocksize - 1); while (!error && !stored && filp->f_pos < inode->i_size) { |
d8733c295 [PATCH] ext3_read... |
126 127 128 129 130 |
unsigned long blk = filp->f_pos >> EXT3_BLOCK_SIZE_BITS(sb); struct buffer_head map_bh; struct buffer_head *bh = NULL; map_bh.b_state = 0; |
43237b549 ext3: Get rid of ... |
131 |
err = ext3_get_blocks_handle(NULL, inode, blk, 1, &map_bh, 0); |
89747d369 [PATCH] ext3_get_... |
132 |
if (err > 0) { |
dc7868fcb readahead: conver... |
133 134 135 |
pgoff_t index = map_bh.b_blocknr >> (PAGE_CACHE_SHIFT - inode->i_blkbits); if (!ra_has_index(&filp->f_ra, index)) |
cf914a7d6 readahead: split ... |
136 |
page_cache_sync_readahead( |
dc7868fcb readahead: conver... |
137 138 |
sb->s_bdev->bd_inode->i_mapping, &filp->f_ra, filp, |
cf914a7d6 readahead: split ... |
139 |
index, 1); |
f4e6b498d readahead: combin... |
140 |
filp->f_ra.prev_pos = (loff_t)index << PAGE_CACHE_SHIFT; |
d8733c295 [PATCH] ext3_read... |
141 142 143 144 145 146 147 |
bh = ext3_bread(NULL, inode, blk, 0, &err); } /* * We ignore I/O errors on directories so users have a chance * of recovering data when there's a bad sector */ |
1da177e4c Linux-2.6.12-rc2 |
148 |
if (!bh) { |
cdbf6dba2 ext3: avoid print... |
149 150 151 152 153 154 |
if (!dir_has_error) { ext3_error(sb, __func__, "directory #%lu " "contains a hole at offset %lld", inode->i_ino, filp->f_pos); dir_has_error = 1; } |
40b851348 [PATCH] handle ex... |
155 156 157 |
/* corrupt size? Maybe no more blocks to read */ if (filp->f_pos > inode->i_blocks << 9) break; |
1da177e4c Linux-2.6.12-rc2 |
158 159 160 |
filp->f_pos += sb->s_blocksize - offset; continue; } |
1da177e4c Linux-2.6.12-rc2 |
161 162 163 164 165 166 167 |
revalidate: /* If the dir block has changed since the last call to * readdir(2), then we might be pointing to an invalid * dirent right now. Scan from the start of the block * to make sure. */ if (filp->f_version != inode->i_version) { for (i = 0; i < sb->s_blocksize && i < offset; ) { |
ae6ddcc5f [PATCH] ext3 and ... |
168 |
de = (struct ext3_dir_entry_2 *) |
1da177e4c Linux-2.6.12-rc2 |
169 170 171 172 173 174 175 |
(bh->b_data + i); /* It's too expensive to do a full * dirent test each time round this * loop, but we do have to test at * least that it is non-zero. A * failure will be detected in the * dirent test below. */ |
7c06a8dc6 Fix 64KB blocksiz... |
176 |
if (ext3_rec_len_from_disk(de->rec_len) < |
1da177e4c Linux-2.6.12-rc2 |
177 178 |
EXT3_DIR_REC_LEN(1)) break; |
7c06a8dc6 Fix 64KB blocksiz... |
179 |
i += ext3_rec_len_from_disk(de->rec_len); |
1da177e4c Linux-2.6.12-rc2 |
180 181 182 183 184 185 |
} offset = i; filp->f_pos = (filp->f_pos & ~(sb->s_blocksize - 1)) | offset; filp->f_version = inode->i_version; } |
ae6ddcc5f [PATCH] ext3 and ... |
186 |
while (!error && filp->f_pos < inode->i_size |
1da177e4c Linux-2.6.12-rc2 |
187 188 189 190 191 192 193 194 195 196 197 198 |
&& offset < sb->s_blocksize) { de = (struct ext3_dir_entry_2 *) (bh->b_data + offset); if (!ext3_check_dir_entry ("ext3_readdir", inode, de, bh, offset)) { /* On error, skip the f_pos to the next block. */ filp->f_pos = (filp->f_pos | (sb->s_blocksize - 1)) + 1; brelse (bh); ret = stored; goto out; } |
7c06a8dc6 Fix 64KB blocksiz... |
199 |
offset += ext3_rec_len_from_disk(de->rec_len); |
1da177e4c Linux-2.6.12-rc2 |
200 201 202 203 204 205 206 207 |
if (le32_to_cpu(de->inode)) { /* We might block in the next section * if the data destination is * currently swapped out. So, use a * version stamp to detect whether or * not the directory has been modified * during the copy operation. */ |
2b47c3611 Fix f_version typ... |
208 |
u64 version = filp->f_version; |
1da177e4c Linux-2.6.12-rc2 |
209 210 211 212 213 214 215 216 217 218 219 220 |
error = filldir(dirent, de->name, de->name_len, filp->f_pos, le32_to_cpu(de->inode), get_dtype(sb, de->file_type)); if (error) break; if (version != filp->f_version) goto revalidate; stored ++; } |
7c06a8dc6 Fix 64KB blocksiz... |
221 |
filp->f_pos += ext3_rec_len_from_disk(de->rec_len); |
1da177e4c Linux-2.6.12-rc2 |
222 223 224 225 226 227 228 |
} offset = 0; brelse (bh); } out: return ret; } |
1da177e4c Linux-2.6.12-rc2 |
229 230 231 |
/* * These functions convert from the major/minor hash to an f_pos * value. |
ae6ddcc5f [PATCH] ext3 and ... |
232 |
* |
1da177e4c Linux-2.6.12-rc2 |
233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 |
* Currently we only use major hash numer. This is unfortunate, but * on 32-bit machines, the same VFS interface is used for lseek and * llseek, so if we use the 64 bit offset, then the 32-bit versions of * lseek/telldir/seekdir will blow out spectacularly, and from within * the ext2 low-level routine, we don't know if we're being called by * a 64-bit version of the system call or the 32-bit version of the * system call. Worse yet, NFSv2 only allows for a 32-bit readdir * cookie. Sigh. */ #define hash2pos(major, minor) (major >> 1) #define pos2maj_hash(pos) ((pos << 1) & 0xffffffff) #define pos2min_hash(pos) (0) /* * This structure holds the nodes of the red-black tree used to store * the directory entry in hash order. */ struct fname { __u32 hash; __u32 minor_hash; |
ae6ddcc5f [PATCH] ext3 and ... |
253 |
struct rb_node rb_hash; |
1da177e4c Linux-2.6.12-rc2 |
254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 |
struct fname *next; __u32 inode; __u8 name_len; __u8 file_type; char name[0]; }; /* * This functoin implements a non-recursive way of freeing all of the * nodes in the red-black tree. */ static void free_rb_tree_fname(struct rb_root *root) { struct rb_node *n = root->rb_node; struct rb_node *parent; struct fname *fname; while (n) { /* Do the node's children first */ |
9ebfbe9f9 ext3: improve som... |
273 |
if (n->rb_left) { |
1da177e4c Linux-2.6.12-rc2 |
274 275 276 277 278 279 280 281 282 283 284 285 286 |
n = n->rb_left; continue; } if (n->rb_right) { n = n->rb_right; continue; } /* * The node has no children; free it, and then zero * out parent's link to it. Finally go to the * beginning of the loop and try to free the parent * node. */ |
52b5108ca [RBTREE] Update e... |
287 |
parent = rb_parent(n); |
1da177e4c Linux-2.6.12-rc2 |
288 289 290 291 292 293 294 |
fname = rb_entry(n, struct fname, rb_hash); while (fname) { struct fname * old = fname; fname = fname->next; kfree (old); } if (!parent) |
1513b02c8 ext3 uses rb_node... |
295 |
*root = RB_ROOT; |
1da177e4c Linux-2.6.12-rc2 |
296 297 298 299 300 301 |
else if (parent->rb_left == n) parent->rb_left = NULL; else if (parent->rb_right == n) parent->rb_right = NULL; n = parent; } |
1da177e4c Linux-2.6.12-rc2 |
302 |
} |
9ebfbe9f9 ext3: improve som... |
303 |
static struct dir_private_info *ext3_htree_create_dir_info(loff_t pos) |
1da177e4c Linux-2.6.12-rc2 |
304 305 |
{ struct dir_private_info *p; |
9ebfbe9f9 ext3: improve som... |
306 |
p = kzalloc(sizeof(struct dir_private_info), GFP_KERNEL); |
1da177e4c Linux-2.6.12-rc2 |
307 308 |
if (!p) return NULL; |
1da177e4c Linux-2.6.12-rc2 |
309 310 |
p->curr_hash = pos2maj_hash(pos); p->curr_minor_hash = pos2min_hash(pos); |
1da177e4c Linux-2.6.12-rc2 |
311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 |
return p; } void ext3_htree_free_dir_info(struct dir_private_info *p) { free_rb_tree_fname(&p->root); kfree(p); } /* * Given a directory entry, enter it into the fname rb tree. */ int ext3_htree_store_dirent(struct file *dir_file, __u32 hash, __u32 minor_hash, struct ext3_dir_entry_2 *dirent) { struct rb_node **p, *parent = NULL; struct fname * fname, *new_fn; struct dir_private_info *info; int len; info = (struct dir_private_info *) dir_file->private_data; p = &info->root.rb_node; /* Create and allocate the fname structure */ len = sizeof(struct fname) + dirent->name_len + 1; |
f8314dc60 [PATCH] fs: Conve... |
337 |
new_fn = kzalloc(len, GFP_KERNEL); |
1da177e4c Linux-2.6.12-rc2 |
338 339 |
if (!new_fn) return -ENOMEM; |
1da177e4c Linux-2.6.12-rc2 |
340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 |
new_fn->hash = hash; new_fn->minor_hash = minor_hash; new_fn->inode = le32_to_cpu(dirent->inode); new_fn->name_len = dirent->name_len; new_fn->file_type = dirent->file_type; memcpy(new_fn->name, dirent->name, dirent->name_len); new_fn->name[dirent->name_len] = 0; while (*p) { parent = *p; fname = rb_entry(parent, struct fname, rb_hash); /* * If the hash and minor hash match up, then we put * them on a linked list. This rarely happens... */ if ((new_fn->hash == fname->hash) && (new_fn->minor_hash == fname->minor_hash)) { new_fn->next = fname->next; fname->next = new_fn; return 0; } if (new_fn->hash < fname->hash) p = &(*p)->rb_left; else if (new_fn->hash > fname->hash) p = &(*p)->rb_right; else if (new_fn->minor_hash < fname->minor_hash) p = &(*p)->rb_left; else /* if (new_fn->minor_hash > fname->minor_hash) */ p = &(*p)->rb_right; } rb_link_node(&new_fn->rb_hash, parent, p); rb_insert_color(&new_fn->rb_hash, &info->root); return 0; } /* * This is a helper function for ext3_dx_readdir. It calls filldir * for all entres on the fname linked list. (Normally there is only * one entry on the linked list, unless there are 62 bit hash collisions.) */ static int call_filldir(struct file * filp, void * dirent, filldir_t filldir, struct fname *fname) { struct dir_private_info *info = filp->private_data; loff_t curr_pos; |
fe21a6938 [PATCH] ext3: cha... |
390 |
struct inode *inode = filp->f_path.dentry->d_inode; |
1da177e4c Linux-2.6.12-rc2 |
391 392 393 394 395 396 397 398 399 400 401 402 403 |
struct super_block * sb; int error; sb = inode->i_sb; if (!fname) { printk("call_filldir: called with null fname?!? "); return 0; } curr_pos = hash2pos(fname->hash, fname->minor_hash); while (fname) { error = filldir(dirent, fname->name, |
ae6ddcc5f [PATCH] ext3 and ... |
404 |
fname->name_len, curr_pos, |
1da177e4c Linux-2.6.12-rc2 |
405 406 407 408 |
fname->inode, get_dtype(sb, fname->file_type)); if (error) { filp->f_pos = curr_pos; |
6a897cf44 ext3: fix ext3_dx... |
409 |
info->extra_fname = fname; |
1da177e4c Linux-2.6.12-rc2 |
410 411 412 413 414 415 416 417 418 419 420 |
return error; } fname = fname->next; } return 0; } static int ext3_dx_readdir(struct file * filp, void * dirent, filldir_t filldir) { struct dir_private_info *info = filp->private_data; |
fe21a6938 [PATCH] ext3: cha... |
421 |
struct inode *inode = filp->f_path.dentry->d_inode; |
1da177e4c Linux-2.6.12-rc2 |
422 423 424 425 |
struct fname *fname; int ret; if (!info) { |
9ebfbe9f9 ext3: improve som... |
426 |
info = ext3_htree_create_dir_info(filp->f_pos); |
1da177e4c Linux-2.6.12-rc2 |
427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 |
if (!info) return -ENOMEM; filp->private_data = info; } if (filp->f_pos == EXT3_HTREE_EOF) return 0; /* EOF */ /* Some one has messed with f_pos; reset the world */ if (info->last_pos != filp->f_pos) { free_rb_tree_fname(&info->root); info->curr_node = NULL; info->extra_fname = NULL; info->curr_hash = pos2maj_hash(filp->f_pos); info->curr_minor_hash = pos2min_hash(filp->f_pos); } /* * If there are any leftover names on the hash collision * chain, return them first. */ |
6a897cf44 ext3: fix ext3_dx... |
448 449 450 |
if (info->extra_fname) { if (call_filldir(filp, dirent, filldir, info->extra_fname)) goto finished; |
6a897cf44 ext3: fix ext3_dx... |
451 |
info->extra_fname = NULL; |
8c9fa93d5 ext3: Fix duplica... |
452 |
goto next_node; |
6a897cf44 ext3: fix ext3_dx... |
453 |
} else if (!info->curr_node) |
1da177e4c Linux-2.6.12-rc2 |
454 455 456 457 458 459 |
info->curr_node = rb_first(&info->root); while (1) { /* * Fill the rbtree if we have no more entries, * or the inode has changed since we last read in the |
ae6ddcc5f [PATCH] ext3 and ... |
460 |
* cached entries. |
1da177e4c Linux-2.6.12-rc2 |
461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 |
*/ if ((!info->curr_node) || (filp->f_version != inode->i_version)) { info->curr_node = NULL; free_rb_tree_fname(&info->root); filp->f_version = inode->i_version; ret = ext3_htree_fill_tree(filp, info->curr_hash, info->curr_minor_hash, &info->next_hash); if (ret < 0) return ret; if (ret == 0) { filp->f_pos = EXT3_HTREE_EOF; break; } info->curr_node = rb_first(&info->root); } fname = rb_entry(info->curr_node, struct fname, rb_hash); info->curr_hash = fname->hash; info->curr_minor_hash = fname->minor_hash; if (call_filldir(filp, dirent, filldir, fname)) break; |
8c9fa93d5 ext3: Fix duplica... |
484 |
next_node: |
1da177e4c Linux-2.6.12-rc2 |
485 |
info->curr_node = rb_next(info->curr_node); |
8c9fa93d5 ext3: Fix duplica... |
486 487 488 489 490 491 |
if (info->curr_node) { fname = rb_entry(info->curr_node, struct fname, rb_hash); info->curr_hash = fname->hash; info->curr_minor_hash = fname->minor_hash; } else { |
1da177e4c Linux-2.6.12-rc2 |
492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 |
if (info->next_hash == ~0) { filp->f_pos = EXT3_HTREE_EOF; break; } info->curr_hash = info->next_hash; info->curr_minor_hash = 0; } } finished: info->last_pos = filp->f_pos; return 0; } static int ext3_release_dir (struct inode * inode, struct file * filp) { if (filp->private_data) ext3_htree_free_dir_info(filp->private_data); return 0; } |