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