1 /* 2 * dir.c - NILFS directory entry operations 3 * 4 * Copyright (C) 2005-2008 Nippon Telegraph and Telephone Corporation. 5 * 6 * This program is free software; you can redistribute it and/or modify 7 * it under the terms of the GNU General Public License as published by 8 * the Free Software Foundation; either version 2 of the License, or 9 * (at your option) any later version. 10 * 11 * This program is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with this program; if not, write to the Free Software 18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 19 * 20 * Modified for NILFS by Amagai Yoshiji <amagai@osrg.net> 21 */ 22 /* 23 * linux/fs/ext2/dir.c 24 * 25 * Copyright (C) 1992, 1993, 1994, 1995 26 * Remy Card (card@masi.ibp.fr) 27 * Laboratoire MASI - Institut Blaise Pascal 28 * Universite Pierre et Marie Curie (Paris VI) 29 * 30 * from 31 * 32 * linux/fs/minix/dir.c 33 * 34 * Copyright (C) 1991, 1992 Linus Torvalds 35 * 36 * ext2 directory handling functions 37 * 38 * Big-endian to little-endian byte-swapping/bitmaps by 39 * David S. Miller (davem@caip.rutgers.edu), 1995 40 * 41 * All code that works with directory layout had been switched to pagecache 42 * and moved here. AV 43 */ 44 45 #include <linux/pagemap.h> 46 #include "nilfs.h" 47 #include "page.h" 48 49 /* 50 * nilfs uses block-sized chunks. Arguably, sector-sized ones would be 51 * more robust, but we have what we have 52 */ 53 static inline unsigned nilfs_chunk_size(struct inode *inode) 54 { 55 return inode->i_sb->s_blocksize; 56 } 57 58 static inline void nilfs_put_page(struct page *page) 59 { 60 kunmap(page); 61 page_cache_release(page); 62 } 63 64 /* 65 * Return the offset into page `page_nr' of the last valid 66 * byte in that page, plus one. 67 */ 68 static unsigned nilfs_last_byte(struct inode *inode, unsigned long page_nr) 69 { 70 unsigned last_byte = inode->i_size; 71 72 last_byte -= page_nr << PAGE_CACHE_SHIFT; 73 if (last_byte > PAGE_CACHE_SIZE) 74 last_byte = PAGE_CACHE_SIZE; 75 return last_byte; 76 } 77 78 static int nilfs_prepare_chunk(struct page *page, unsigned from, unsigned to) 79 { 80 loff_t pos = page_offset(page) + from; 81 return __block_write_begin(page, pos, to - from, nilfs_get_block); 82 } 83 84 static void nilfs_commit_chunk(struct page *page, 85 struct address_space *mapping, 86 unsigned from, unsigned to) 87 { 88 struct inode *dir = mapping->host; 89 loff_t pos = page_offset(page) + from; 90 unsigned len = to - from; 91 unsigned nr_dirty, copied; 92 int err; 93 94 nr_dirty = nilfs_page_count_clean_buffers(page, from, to); 95 copied = block_write_end(NULL, mapping, pos, len, len, page, NULL); 96 if (pos + copied > dir->i_size) 97 i_size_write(dir, pos + copied); 98 if (IS_DIRSYNC(dir)) 99 nilfs_set_transaction_flag(NILFS_TI_SYNC); 100 err = nilfs_set_file_dirty(dir, nr_dirty); 101 WARN_ON(err); /* do not happen */ 102 unlock_page(page); 103 } 104 105 static void nilfs_check_page(struct page *page) 106 { 107 struct inode *dir = page->mapping->host; 108 struct super_block *sb = dir->i_sb; 109 unsigned chunk_size = nilfs_chunk_size(dir); 110 char *kaddr = page_address(page); 111 unsigned offs, rec_len; 112 unsigned limit = PAGE_CACHE_SIZE; 113 struct nilfs_dir_entry *p; 114 char *error; 115 116 if ((dir->i_size >> PAGE_CACHE_SHIFT) == page->index) { 117 limit = dir->i_size & ~PAGE_CACHE_MASK; 118 if (limit & (chunk_size - 1)) 119 goto Ebadsize; 120 if (!limit) 121 goto out; 122 } 123 for (offs = 0; offs <= limit - NILFS_DIR_REC_LEN(1); offs += rec_len) { 124 p = (struct nilfs_dir_entry *)(kaddr + offs); 125 rec_len = nilfs_rec_len_from_disk(p->rec_len); 126 127 if (rec_len < NILFS_DIR_REC_LEN(1)) 128 goto Eshort; 129 if (rec_len & 3) 130 goto Ealign; 131 if (rec_len < NILFS_DIR_REC_LEN(p->name_len)) 132 goto Enamelen; 133 if (((offs + rec_len - 1) ^ offs) & ~(chunk_size-1)) 134 goto Espan; 135 } 136 if (offs != limit) 137 goto Eend; 138 out: 139 SetPageChecked(page); 140 return; 141 142 /* Too bad, we had an error */ 143 144 Ebadsize: 145 nilfs_error(sb, "nilfs_check_page", 146 "size of directory #%lu is not a multiple of chunk size", 147 dir->i_ino 148 ); 149 goto fail; 150 Eshort: 151 error = "rec_len is smaller than minimal"; 152 goto bad_entry; 153 Ealign: 154 error = "unaligned directory entry"; 155 goto bad_entry; 156 Enamelen: 157 error = "rec_len is too small for name_len"; 158 goto bad_entry; 159 Espan: 160 error = "directory entry across blocks"; 161 bad_entry: 162 nilfs_error(sb, "nilfs_check_page", "bad entry in directory #%lu: %s - " 163 "offset=%lu, inode=%lu, rec_len=%d, name_len=%d", 164 dir->i_ino, error, (page->index<<PAGE_CACHE_SHIFT)+offs, 165 (unsigned long) le64_to_cpu(p->inode), 166 rec_len, p->name_len); 167 goto fail; 168 Eend: 169 p = (struct nilfs_dir_entry *)(kaddr + offs); 170 nilfs_error(sb, "nilfs_check_page", 171 "entry in directory #%lu spans the page boundary" 172 "offset=%lu, inode=%lu", 173 dir->i_ino, (page->index<<PAGE_CACHE_SHIFT)+offs, 174 (unsigned long) le64_to_cpu(p->inode)); 175 fail: 176 SetPageChecked(page); 177 SetPageError(page); 178 } 179 180 static struct page *nilfs_get_page(struct inode *dir, unsigned long n) 181 { 182 struct address_space *mapping = dir->i_mapping; 183 struct page *page = read_mapping_page(mapping, n, NULL); 184 185 if (!IS_ERR(page)) { 186 kmap(page); 187 if (!PageChecked(page)) 188 nilfs_check_page(page); 189 if (PageError(page)) 190 goto fail; 191 } 192 return page; 193 194 fail: 195 nilfs_put_page(page); 196 return ERR_PTR(-EIO); 197 } 198 199 /* 200 * NOTE! unlike strncmp, nilfs_match returns 1 for success, 0 for failure. 201 * 202 * len <= NILFS_NAME_LEN and de != NULL are guaranteed by caller. 203 */ 204 static int 205 nilfs_match(int len, const unsigned char *name, struct nilfs_dir_entry *de) 206 { 207 if (len != de->name_len) 208 return 0; 209 if (!de->inode) 210 return 0; 211 return !memcmp(name, de->name, len); 212 } 213 214 /* 215 * p is at least 6 bytes before the end of page 216 */ 217 static struct nilfs_dir_entry *nilfs_next_entry(struct nilfs_dir_entry *p) 218 { 219 return (struct nilfs_dir_entry *)((char *)p + 220 nilfs_rec_len_from_disk(p->rec_len)); 221 } 222 223 static unsigned char 224 nilfs_filetype_table[NILFS_FT_MAX] = { 225 [NILFS_FT_UNKNOWN] = DT_UNKNOWN, 226 [NILFS_FT_REG_FILE] = DT_REG, 227 [NILFS_FT_DIR] = DT_DIR, 228 [NILFS_FT_CHRDEV] = DT_CHR, 229 [NILFS_FT_BLKDEV] = DT_BLK, 230 [NILFS_FT_FIFO] = DT_FIFO, 231 [NILFS_FT_SOCK] = DT_SOCK, 232 [NILFS_FT_SYMLINK] = DT_LNK, 233 }; 234 235 #define S_SHIFT 12 236 static unsigned char 237 nilfs_type_by_mode[S_IFMT >> S_SHIFT] = { 238 [S_IFREG >> S_SHIFT] = NILFS_FT_REG_FILE, 239 [S_IFDIR >> S_SHIFT] = NILFS_FT_DIR, 240 [S_IFCHR >> S_SHIFT] = NILFS_FT_CHRDEV, 241 [S_IFBLK >> S_SHIFT] = NILFS_FT_BLKDEV, 242 [S_IFIFO >> S_SHIFT] = NILFS_FT_FIFO, 243 [S_IFSOCK >> S_SHIFT] = NILFS_FT_SOCK, 244 [S_IFLNK >> S_SHIFT] = NILFS_FT_SYMLINK, 245 }; 246 247 static void nilfs_set_de_type(struct nilfs_dir_entry *de, struct inode *inode) 248 { 249 umode_t mode = inode->i_mode; 250 251 de->file_type = nilfs_type_by_mode[(mode & S_IFMT)>>S_SHIFT]; 252 } 253 254 static int nilfs_readdir(struct file *file, struct dir_context *ctx) 255 { 256 loff_t pos = ctx->pos; 257 struct inode *inode = file_inode(file); 258 struct super_block *sb = inode->i_sb; 259 unsigned int offset = pos & ~PAGE_CACHE_MASK; 260 unsigned long n = pos >> PAGE_CACHE_SHIFT; 261 unsigned long npages = dir_pages(inode); 262 /* unsigned chunk_mask = ~(nilfs_chunk_size(inode)-1); */ 263 264 if (pos > inode->i_size - NILFS_DIR_REC_LEN(1)) 265 return 0; 266 267 for ( ; n < npages; n++, offset = 0) { 268 char *kaddr, *limit; 269 struct nilfs_dir_entry *de; 270 struct page *page = nilfs_get_page(inode, n); 271 272 if (IS_ERR(page)) { 273 nilfs_error(sb, __func__, "bad page in #%lu", 274 inode->i_ino); 275 ctx->pos += PAGE_CACHE_SIZE - offset; 276 return -EIO; 277 } 278 kaddr = page_address(page); 279 de = (struct nilfs_dir_entry *)(kaddr + offset); 280 limit = kaddr + nilfs_last_byte(inode, n) - 281 NILFS_DIR_REC_LEN(1); 282 for ( ; (char *)de <= limit; de = nilfs_next_entry(de)) { 283 if (de->rec_len == 0) { 284 nilfs_error(sb, __func__, 285 "zero-length directory entry"); 286 nilfs_put_page(page); 287 return -EIO; 288 } 289 if (de->inode) { 290 unsigned char t; 291 292 if (de->file_type < NILFS_FT_MAX) 293 t = nilfs_filetype_table[de->file_type]; 294 else 295 t = DT_UNKNOWN; 296 297 if (!dir_emit(ctx, de->name, de->name_len, 298 le64_to_cpu(de->inode), t)) { 299 nilfs_put_page(page); 300 return 0; 301 } 302 } 303 ctx->pos += nilfs_rec_len_from_disk(de->rec_len); 304 } 305 nilfs_put_page(page); 306 } 307 return 0; 308 } 309 310 /* 311 * nilfs_find_entry() 312 * 313 * finds an entry in the specified directory with the wanted name. It 314 * returns the page in which the entry was found, and the entry itself 315 * (as a parameter - res_dir). Page is returned mapped and unlocked. 316 * Entry is guaranteed to be valid. 317 */ 318 struct nilfs_dir_entry * 319 nilfs_find_entry(struct inode *dir, const struct qstr *qstr, 320 struct page **res_page) 321 { 322 const unsigned char *name = qstr->name; 323 int namelen = qstr->len; 324 unsigned reclen = NILFS_DIR_REC_LEN(namelen); 325 unsigned long start, n; 326 unsigned long npages = dir_pages(dir); 327 struct page *page = NULL; 328 struct nilfs_inode_info *ei = NILFS_I(dir); 329 struct nilfs_dir_entry *de; 330 331 if (npages == 0) 332 goto out; 333 334 /* OFFSET_CACHE */ 335 *res_page = NULL; 336 337 start = ei->i_dir_start_lookup; 338 if (start >= npages) 339 start = 0; 340 n = start; 341 do { 342 char *kaddr; 343 page = nilfs_get_page(dir, n); 344 if (!IS_ERR(page)) { 345 kaddr = page_address(page); 346 de = (struct nilfs_dir_entry *)kaddr; 347 kaddr += nilfs_last_byte(dir, n) - reclen; 348 while ((char *) de <= kaddr) { 349 if (de->rec_len == 0) { 350 nilfs_error(dir->i_sb, __func__, 351 "zero-length directory entry"); 352 nilfs_put_page(page); 353 goto out; 354 } 355 if (nilfs_match(namelen, name, de)) 356 goto found; 357 de = nilfs_next_entry(de); 358 } 359 nilfs_put_page(page); 360 } 361 if (++n >= npages) 362 n = 0; 363 /* next page is past the blocks we've got */ 364 if (unlikely(n > (dir->i_blocks >> (PAGE_CACHE_SHIFT - 9)))) { 365 nilfs_error(dir->i_sb, __func__, 366 "dir %lu size %lld exceeds block count %llu", 367 dir->i_ino, dir->i_size, 368 (unsigned long long)dir->i_blocks); 369 goto out; 370 } 371 } while (n != start); 372 out: 373 return NULL; 374 375 found: 376 *res_page = page; 377 ei->i_dir_start_lookup = n; 378 return de; 379 } 380 381 struct nilfs_dir_entry *nilfs_dotdot(struct inode *dir, struct page **p) 382 { 383 struct page *page = nilfs_get_page(dir, 0); 384 struct nilfs_dir_entry *de = NULL; 385 386 if (!IS_ERR(page)) { 387 de = nilfs_next_entry( 388 (struct nilfs_dir_entry *)page_address(page)); 389 *p = page; 390 } 391 return de; 392 } 393 394 ino_t nilfs_inode_by_name(struct inode *dir, const struct qstr *qstr) 395 { 396 ino_t res = 0; 397 struct nilfs_dir_entry *de; 398 struct page *page; 399 400 de = nilfs_find_entry(dir, qstr, &page); 401 if (de) { 402 res = le64_to_cpu(de->inode); 403 kunmap(page); 404 page_cache_release(page); 405 } 406 return res; 407 } 408 409 /* Releases the page */ 410 void nilfs_set_link(struct inode *dir, struct nilfs_dir_entry *de, 411 struct page *page, struct inode *inode) 412 { 413 unsigned from = (char *) de - (char *) page_address(page); 414 unsigned to = from + nilfs_rec_len_from_disk(de->rec_len); 415 struct address_space *mapping = page->mapping; 416 int err; 417 418 lock_page(page); 419 err = nilfs_prepare_chunk(page, from, to); 420 BUG_ON(err); 421 de->inode = cpu_to_le64(inode->i_ino); 422 nilfs_set_de_type(de, inode); 423 nilfs_commit_chunk(page, mapping, from, to); 424 nilfs_put_page(page); 425 dir->i_mtime = dir->i_ctime = CURRENT_TIME; 426 } 427 428 /* 429 * Parent is locked. 430 */ 431 int nilfs_add_link(struct dentry *dentry, struct inode *inode) 432 { 433 struct inode *dir = d_inode(dentry->d_parent); 434 const unsigned char *name = dentry->d_name.name; 435 int namelen = dentry->d_name.len; 436 unsigned chunk_size = nilfs_chunk_size(dir); 437 unsigned reclen = NILFS_DIR_REC_LEN(namelen); 438 unsigned short rec_len, name_len; 439 struct page *page = NULL; 440 struct nilfs_dir_entry *de; 441 unsigned long npages = dir_pages(dir); 442 unsigned long n; 443 char *kaddr; 444 unsigned from, to; 445 int err; 446 447 /* 448 * We take care of directory expansion in the same loop. 449 * This code plays outside i_size, so it locks the page 450 * to protect that region. 451 */ 452 for (n = 0; n <= npages; n++) { 453 char *dir_end; 454 455 page = nilfs_get_page(dir, n); 456 err = PTR_ERR(page); 457 if (IS_ERR(page)) 458 goto out; 459 lock_page(page); 460 kaddr = page_address(page); 461 dir_end = kaddr + nilfs_last_byte(dir, n); 462 de = (struct nilfs_dir_entry *)kaddr; 463 kaddr += PAGE_CACHE_SIZE - reclen; 464 while ((char *)de <= kaddr) { 465 if ((char *)de == dir_end) { 466 /* We hit i_size */ 467 name_len = 0; 468 rec_len = chunk_size; 469 de->rec_len = nilfs_rec_len_to_disk(chunk_size); 470 de->inode = 0; 471 goto got_it; 472 } 473 if (de->rec_len == 0) { 474 nilfs_error(dir->i_sb, __func__, 475 "zero-length directory entry"); 476 err = -EIO; 477 goto out_unlock; 478 } 479 err = -EEXIST; 480 if (nilfs_match(namelen, name, de)) 481 goto out_unlock; 482 name_len = NILFS_DIR_REC_LEN(de->name_len); 483 rec_len = nilfs_rec_len_from_disk(de->rec_len); 484 if (!de->inode && rec_len >= reclen) 485 goto got_it; 486 if (rec_len >= name_len + reclen) 487 goto got_it; 488 de = (struct nilfs_dir_entry *)((char *)de + rec_len); 489 } 490 unlock_page(page); 491 nilfs_put_page(page); 492 } 493 BUG(); 494 return -EINVAL; 495 496 got_it: 497 from = (char *)de - (char *)page_address(page); 498 to = from + rec_len; 499 err = nilfs_prepare_chunk(page, from, to); 500 if (err) 501 goto out_unlock; 502 if (de->inode) { 503 struct nilfs_dir_entry *de1; 504 505 de1 = (struct nilfs_dir_entry *)((char *)de + name_len); 506 de1->rec_len = nilfs_rec_len_to_disk(rec_len - name_len); 507 de->rec_len = nilfs_rec_len_to_disk(name_len); 508 de = de1; 509 } 510 de->name_len = namelen; 511 memcpy(de->name, name, namelen); 512 de->inode = cpu_to_le64(inode->i_ino); 513 nilfs_set_de_type(de, inode); 514 nilfs_commit_chunk(page, page->mapping, from, to); 515 dir->i_mtime = dir->i_ctime = CURRENT_TIME; 516 nilfs_mark_inode_dirty(dir); 517 /* OFFSET_CACHE */ 518 out_put: 519 nilfs_put_page(page); 520 out: 521 return err; 522 out_unlock: 523 unlock_page(page); 524 goto out_put; 525 } 526 527 /* 528 * nilfs_delete_entry deletes a directory entry by merging it with the 529 * previous entry. Page is up-to-date. Releases the page. 530 */ 531 int nilfs_delete_entry(struct nilfs_dir_entry *dir, struct page *page) 532 { 533 struct address_space *mapping = page->mapping; 534 struct inode *inode = mapping->host; 535 char *kaddr = page_address(page); 536 unsigned from = ((char *)dir - kaddr) & ~(nilfs_chunk_size(inode) - 1); 537 unsigned to = ((char *)dir - kaddr) + 538 nilfs_rec_len_from_disk(dir->rec_len); 539 struct nilfs_dir_entry *pde = NULL; 540 struct nilfs_dir_entry *de = (struct nilfs_dir_entry *)(kaddr + from); 541 int err; 542 543 while ((char *)de < (char *)dir) { 544 if (de->rec_len == 0) { 545 nilfs_error(inode->i_sb, __func__, 546 "zero-length directory entry"); 547 err = -EIO; 548 goto out; 549 } 550 pde = de; 551 de = nilfs_next_entry(de); 552 } 553 if (pde) 554 from = (char *)pde - (char *)page_address(page); 555 lock_page(page); 556 err = nilfs_prepare_chunk(page, from, to); 557 BUG_ON(err); 558 if (pde) 559 pde->rec_len = nilfs_rec_len_to_disk(to - from); 560 dir->inode = 0; 561 nilfs_commit_chunk(page, mapping, from, to); 562 inode->i_ctime = inode->i_mtime = CURRENT_TIME; 563 out: 564 nilfs_put_page(page); 565 return err; 566 } 567 568 /* 569 * Set the first fragment of directory. 570 */ 571 int nilfs_make_empty(struct inode *inode, struct inode *parent) 572 { 573 struct address_space *mapping = inode->i_mapping; 574 struct page *page = grab_cache_page(mapping, 0); 575 unsigned chunk_size = nilfs_chunk_size(inode); 576 struct nilfs_dir_entry *de; 577 int err; 578 void *kaddr; 579 580 if (!page) 581 return -ENOMEM; 582 583 err = nilfs_prepare_chunk(page, 0, chunk_size); 584 if (unlikely(err)) { 585 unlock_page(page); 586 goto fail; 587 } 588 kaddr = kmap_atomic(page); 589 memset(kaddr, 0, chunk_size); 590 de = (struct nilfs_dir_entry *)kaddr; 591 de->name_len = 1; 592 de->rec_len = nilfs_rec_len_to_disk(NILFS_DIR_REC_LEN(1)); 593 memcpy(de->name, ".\0\0", 4); 594 de->inode = cpu_to_le64(inode->i_ino); 595 nilfs_set_de_type(de, inode); 596 597 de = (struct nilfs_dir_entry *)(kaddr + NILFS_DIR_REC_LEN(1)); 598 de->name_len = 2; 599 de->rec_len = nilfs_rec_len_to_disk(chunk_size - NILFS_DIR_REC_LEN(1)); 600 de->inode = cpu_to_le64(parent->i_ino); 601 memcpy(de->name, "..\0", 4); 602 nilfs_set_de_type(de, inode); 603 kunmap_atomic(kaddr); 604 nilfs_commit_chunk(page, mapping, 0, chunk_size); 605 fail: 606 page_cache_release(page); 607 return err; 608 } 609 610 /* 611 * routine to check that the specified directory is empty (for rmdir) 612 */ 613 int nilfs_empty_dir(struct inode *inode) 614 { 615 struct page *page = NULL; 616 unsigned long i, npages = dir_pages(inode); 617 618 for (i = 0; i < npages; i++) { 619 char *kaddr; 620 struct nilfs_dir_entry *de; 621 622 page = nilfs_get_page(inode, i); 623 if (IS_ERR(page)) 624 continue; 625 626 kaddr = page_address(page); 627 de = (struct nilfs_dir_entry *)kaddr; 628 kaddr += nilfs_last_byte(inode, i) - NILFS_DIR_REC_LEN(1); 629 630 while ((char *)de <= kaddr) { 631 if (de->rec_len == 0) { 632 nilfs_error(inode->i_sb, __func__, 633 "zero-length directory entry " 634 "(kaddr=%p, de=%p)\n", kaddr, de); 635 goto not_empty; 636 } 637 if (de->inode != 0) { 638 /* check for . and .. */ 639 if (de->name[0] != '.') 640 goto not_empty; 641 if (de->name_len > 2) 642 goto not_empty; 643 if (de->name_len < 2) { 644 if (de->inode != 645 cpu_to_le64(inode->i_ino)) 646 goto not_empty; 647 } else if (de->name[1] != '.') 648 goto not_empty; 649 } 650 de = nilfs_next_entry(de); 651 } 652 nilfs_put_page(page); 653 } 654 return 1; 655 656 not_empty: 657 nilfs_put_page(page); 658 return 0; 659 } 660 661 const struct file_operations nilfs_dir_operations = { 662 .llseek = generic_file_llseek, 663 .read = generic_read_dir, 664 .iterate = nilfs_readdir, 665 .unlocked_ioctl = nilfs_ioctl, 666 #ifdef CONFIG_COMPAT 667 .compat_ioctl = nilfs_compat_ioctl, 668 #endif /* CONFIG_COMPAT */ 669 .fsync = nilfs_sync_file, 670 671 }; 672