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