fs/ufs/dir.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  *  linux/fs/ufs/ufs_dir.c
0004  *
0005  * Copyright (C) 1996
0006  * Adrian Rodriguez (adrian@franklins-tower.rutgers.edu)
0007  * Laboratory for Computer Science Research Computing Facility
0008  * Rutgers, The State University of New Jersey
0009  *
0010  * swab support by Francois-Rene Rideau <fare@tunes.org> 19970406
0011  *
0012  * 4.4BSD (FreeBSD) support added on February 1st 1998 by
0013  * Niels Kristian Bech Jensen <nkbj@image.dk> partially based
0014  * on code by Martin von Loewis <martin@mira.isdn.cs.tu-berlin.de>.
0015  *
0016  * Migration to usage of "page cache" on May 2006 by
0017  * Evgeniy Dushistov <dushistov@mail.ru> based on ext2 code base.
0018  */
0019
0020 #include <linux/time.h>
0021 #include <linux/fs.h>
0022 #include <linux/swap.h>
0023 #include <linux/iversion.h>
0024
0025 #include "ufs_fs.h"
0026 #include "ufs.h"
0027 #include "swab.h"
0028 #include "util.h"
0029
0030 /*
0031  * NOTE! unlike strncmp, ufs_match returns 1 for success, 0 for failure.
0032  *
0033  * len <= UFS_MAXNAMLEN and de != NULL are guaranteed by caller.
0034  */
0035 static inline int ufs_match(struct super_block *sb, int len,
0036         const unsigned char *name, struct ufs_dir_entry *de)
0037 {
0038     if (len != ufs_get_de_namlen(sb, de))
0039         return 0;
0040     if (!de->d_ino)
0041         return 0;
0042     return !memcmp(name, de->d_name, len);
0043 }
0044
0045 static int ufs_commit_chunk(struct page *page, loff_t pos, unsigned len)
0046 {
0047     struct address_space *mapping = page->mapping;
0048     struct inode *dir = mapping->host;
0049     int err = 0;
0050
0051     inode_inc_iversion(dir);
0052     block_write_end(NULL, mapping, pos, len, len, page, NULL);
0053     if (pos+len > dir->i_size) {
0054         i_size_write(dir, pos+len);
0055         mark_inode_dirty(dir);
0056     }
0057     if (IS_DIRSYNC(dir))
0058         err = write_one_page(page);
0059     else
0060         unlock_page(page);
0061     return err;
0062 }
0063
0064 static inline void ufs_put_page(struct page *page)
0065 {
0066     kunmap(page);
0067     put_page(page);
0068 }
0069
0070 ino_t ufs_inode_by_name(struct inode *dir, const struct qstr *qstr)
0071 {
0072     ino_t res = 0;
0073     struct ufs_dir_entry *de;
0074     struct page *page;
0075
0076     de = ufs_find_entry(dir, qstr, &page);
0077     if (de) {
0078         res = fs32_to_cpu(dir->i_sb, de->d_ino);
0079         ufs_put_page(page);
0080     }
0081     return res;
0082 }
0083
0084
0085 /* Releases the page */
0086 void ufs_set_link(struct inode *dir, struct ufs_dir_entry *de,
0087           struct page *page, struct inode *inode,
0088           bool update_times)
0089 {
0090     loff_t pos = page_offset(page) +
0091             (char *) de - (char *) page_address(page);
0092     unsigned len = fs16_to_cpu(dir->i_sb, de->d_reclen);
0093     int err;
0094
0095     lock_page(page);
0096     err = ufs_prepare_chunk(page, pos, len);
0097     BUG_ON(err);
0098
0099     de->d_ino = cpu_to_fs32(dir->i_sb, inode->i_ino);
0100     ufs_set_de_type(dir->i_sb, de, inode->i_mode);
0101
0102     err = ufs_commit_chunk(page, pos, len);
0103     ufs_put_page(page);
0104     if (update_times)
0105         dir->i_mtime = dir->i_ctime = current_time(dir);
0106     mark_inode_dirty(dir);
0107 }
0108
0109
0110 static bool ufs_check_page(struct page *page)
0111 {
0112     struct inode *dir = page->mapping->host;
0113     struct super_block *sb = dir->i_sb;
0114     char *kaddr = page_address(page);
0115     unsigned offs, rec_len;
0116     unsigned limit = PAGE_SIZE;
0117     const unsigned chunk_mask = UFS_SB(sb)->s_uspi->s_dirblksize - 1;
0118     struct ufs_dir_entry *p;
0119     char *error;
0120
0121     if ((dir->i_size >> PAGE_SHIFT) == page->index) {
0122         limit = dir->i_size & ~PAGE_MASK;
0123         if (limit & chunk_mask)
0124             goto Ebadsize;
0125         if (!limit)
0126             goto out;
0127     }
0128     for (offs = 0; offs <= limit - UFS_DIR_REC_LEN(1); offs += rec_len) {
0129         p = (struct ufs_dir_entry *)(kaddr + offs);
0130         rec_len = fs16_to_cpu(sb, p->d_reclen);
0131
0132         if (rec_len < UFS_DIR_REC_LEN(1))
0133             goto Eshort;
0134         if (rec_len & 3)
0135             goto Ealign;
0136         if (rec_len < UFS_DIR_REC_LEN(ufs_get_de_namlen(sb, p)))
0137             goto Enamelen;
0138         if (((offs + rec_len - 1) ^ offs) & ~chunk_mask)
0139             goto Espan;
0140         if (fs32_to_cpu(sb, p->d_ino) > (UFS_SB(sb)->s_uspi->s_ipg *
0141                           UFS_SB(sb)->s_uspi->s_ncg))
0142             goto Einumber;
0143     }
0144     if (offs != limit)
0145         goto Eend;
0146 out:
0147     SetPageChecked(page);
0148     return true;
0149
0150     /* Too bad, we had an error */
0151
0152 Ebadsize:
0153     ufs_error(sb, "ufs_check_page",
0154           "size of directory #%lu is not a multiple of chunk size",
0155           dir->i_ino
0156     );
0157     goto fail;
0158 Eshort:
0159     error = "rec_len is smaller than minimal";
0160     goto bad_entry;
0161 Ealign:
0162     error = "unaligned directory entry";
0163     goto bad_entry;
0164 Enamelen:
0165     error = "rec_len is too small for name_len";
0166     goto bad_entry;
0167 Espan:
0168     error = "directory entry across blocks";
0169     goto bad_entry;
0170 Einumber:
0171     error = "inode out of bounds";
0172 bad_entry:
0173     ufs_error (sb, "ufs_check_page", "bad entry in directory #%lu: %s - "
0174            "offset=%lu, rec_len=%d, name_len=%d",
0175            dir->i_ino, error, (page->index<<PAGE_SHIFT)+offs,
0176            rec_len, ufs_get_de_namlen(sb, p));
0177     goto fail;
0178 Eend:
0179     p = (struct ufs_dir_entry *)(kaddr + offs);
0180     ufs_error(sb, __func__,
0181            "entry in directory #%lu spans the page boundary"
0182            "offset=%lu",
0183            dir->i_ino, (page->index<<PAGE_SHIFT)+offs);
0184 fail:
0185     SetPageError(page);
0186     return false;
0187 }
0188
0189 static struct page *ufs_get_page(struct inode *dir, unsigned long n)
0190 {
0191     struct address_space *mapping = dir->i_mapping;
0192     struct page *page = read_mapping_page(mapping, n, NULL);
0193     if (!IS_ERR(page)) {
0194         kmap(page);
0195         if (unlikely(!PageChecked(page))) {
0196             if (!ufs_check_page(page))
0197                 goto fail;
0198         }
0199     }
0200     return page;
0201
0202 fail:
0203     ufs_put_page(page);
0204     return ERR_PTR(-EIO);
0205 }
0206
0207 /*
0208  * Return the offset into page `page_nr' of the last valid
0209  * byte in that page, plus one.
0210  */
0211 static unsigned
0212 ufs_last_byte(struct inode *inode, unsigned long page_nr)
0213 {
0214     unsigned last_byte = inode->i_size;
0215
0216     last_byte -= page_nr << PAGE_SHIFT;
0217     if (last_byte > PAGE_SIZE)
0218         last_byte = PAGE_SIZE;
0219     return last_byte;
0220 }
0221
0222 static inline struct ufs_dir_entry *
0223 ufs_next_entry(struct super_block *sb, struct ufs_dir_entry *p)
0224 {
0225     return (struct ufs_dir_entry *)((char *)p +
0226                     fs16_to_cpu(sb, p->d_reclen));
0227 }
0228
0229 struct ufs_dir_entry *ufs_dotdot(struct inode *dir, struct page **p)
0230 {
0231     struct page *page = ufs_get_page(dir, 0);
0232     struct ufs_dir_entry *de = NULL;
0233
0234     if (!IS_ERR(page)) {
0235         de = ufs_next_entry(dir->i_sb,
0236                     (struct ufs_dir_entry *)page_address(page));
0237         *p = page;
0238     }
0239     return de;
0240 }
0241
0242 /*
0243  *  ufs_find_entry()
0244  *
0245  * finds an entry in the specified directory with the wanted name. It
0246  * returns the page in which the entry was found, and the entry itself
0247  * (as a parameter - res_dir). Page is returned mapped and unlocked.
0248  * Entry is guaranteed to be valid.
0249  */
0250 struct ufs_dir_entry *ufs_find_entry(struct inode *dir, const struct qstr *qstr,
0251                      struct page **res_page)
0252 {
0253     struct super_block *sb = dir->i_sb;
0254     const unsigned char *name = qstr->name;
0255     int namelen = qstr->len;
0256     unsigned reclen = UFS_DIR_REC_LEN(namelen);
0257     unsigned long start, n;
0258     unsigned long npages = dir_pages(dir);
0259     struct page *page = NULL;
0260     struct ufs_inode_info *ui = UFS_I(dir);
0261     struct ufs_dir_entry *de;
0262
0263     UFSD("ENTER, dir_ino %lu, name %s, namlen %u\n", dir->i_ino, name, namelen);
0264
0265     if (npages == 0 || namelen > UFS_MAXNAMLEN)
0266         goto out;
0267
0268     /* OFFSET_CACHE */
0269     *res_page = NULL;
0270
0271     start = ui->i_dir_start_lookup;
0272
0273     if (start >= npages)
0274         start = 0;
0275     n = start;
0276     do {
0277         char *kaddr;
0278         page = ufs_get_page(dir, n);
0279         if (!IS_ERR(page)) {
0280             kaddr = page_address(page);
0281             de = (struct ufs_dir_entry *) kaddr;
0282             kaddr += ufs_last_byte(dir, n) - reclen;
0283             while ((char *) de <= kaddr) {
0284                 if (ufs_match(sb, namelen, name, de))
0285                     goto found;
0286                 de = ufs_next_entry(sb, de);
0287             }
0288             ufs_put_page(page);
0289         }
0290         if (++n >= npages)
0291             n = 0;
0292     } while (n != start);
0293 out:
0294     return NULL;
0295
0296 found:
0297     *res_page = page;
0298     ui->i_dir_start_lookup = n;
0299     return de;
0300 }
0301
0302 /*
0303  *  Parent is locked.
0304  */
0305 int ufs_add_link(struct dentry *dentry, struct inode *inode)
0306 {
0307     struct inode *dir = d_inode(dentry->d_parent);
0308     const unsigned char *name = dentry->d_name.name;
0309     int namelen = dentry->d_name.len;
0310     struct super_block *sb = dir->i_sb;
0311     unsigned reclen = UFS_DIR_REC_LEN(namelen);
0312     const unsigned int chunk_size = UFS_SB(sb)->s_uspi->s_dirblksize;
0313     unsigned short rec_len, name_len;
0314     struct page *page = NULL;
0315     struct ufs_dir_entry *de;
0316     unsigned long npages = dir_pages(dir);
0317     unsigned long n;
0318     char *kaddr;
0319     loff_t pos;
0320     int err;
0321
0322     UFSD("ENTER, name %s, namelen %u\n", name, namelen);
0323
0324     /*
0325      * We take care of directory expansion in the same loop.
0326      * This code plays outside i_size, so it locks the page
0327      * to protect that region.
0328      */
0329     for (n = 0; n <= npages; n++) {
0330         char *dir_end;
0331
0332         page = ufs_get_page(dir, n);
0333         err = PTR_ERR(page);
0334         if (IS_ERR(page))
0335             goto out;
0336         lock_page(page);
0337         kaddr = page_address(page);
0338         dir_end = kaddr + ufs_last_byte(dir, n);
0339         de = (struct ufs_dir_entry *)kaddr;
0340         kaddr += PAGE_SIZE - reclen;
0341         while ((char *)de <= kaddr) {
0342             if ((char *)de == dir_end) {
0343                 /* We hit i_size */
0344                 name_len = 0;
0345                 rec_len = chunk_size;
0346                 de->d_reclen = cpu_to_fs16(sb, chunk_size);
0347                 de->d_ino = 0;
0348                 goto got_it;
0349             }
0350             if (de->d_reclen == 0) {
0351                 ufs_error(dir->i_sb, __func__,
0352                       "zero-length directory entry");
0353                 err = -EIO;
0354                 goto out_unlock;
0355             }
0356             err = -EEXIST;
0357             if (ufs_match(sb, namelen, name, de))
0358                 goto out_unlock;
0359             name_len = UFS_DIR_REC_LEN(ufs_get_de_namlen(sb, de));
0360             rec_len = fs16_to_cpu(sb, de->d_reclen);
0361             if (!de->d_ino && rec_len >= reclen)
0362                 goto got_it;
0363             if (rec_len >= name_len + reclen)
0364                 goto got_it;
0365             de = (struct ufs_dir_entry *) ((char *) de + rec_len);
0366         }
0367         unlock_page(page);
0368         ufs_put_page(page);
0369     }
0370     BUG();
0371     return -EINVAL;
0372
0373 got_it:
0374     pos = page_offset(page) +
0375             (char*)de - (char*)page_address(page);
0376     err = ufs_prepare_chunk(page, pos, rec_len);
0377     if (err)
0378         goto out_unlock;
0379     if (de->d_ino) {
0380         struct ufs_dir_entry *de1 =
0381             (struct ufs_dir_entry *) ((char *) de + name_len);
0382         de1->d_reclen = cpu_to_fs16(sb, rec_len - name_len);
0383         de->d_reclen = cpu_to_fs16(sb, name_len);
0384
0385         de = de1;
0386     }
0387
0388     ufs_set_de_namlen(sb, de, namelen);
0389     memcpy(de->d_name, name, namelen + 1);
0390     de->d_ino = cpu_to_fs32(sb, inode->i_ino);
0391     ufs_set_de_type(sb, de, inode->i_mode);
0392
0393     err = ufs_commit_chunk(page, pos, rec_len);
0394     dir->i_mtime = dir->i_ctime = current_time(dir);
0395
0396     mark_inode_dirty(dir);
0397     /* OFFSET_CACHE */
0398 out_put:
0399     ufs_put_page(page);
0400 out:
0401     return err;
0402 out_unlock:
0403     unlock_page(page);
0404     goto out_put;
0405 }
0406
0407 static inline unsigned
0408 ufs_validate_entry(struct super_block *sb, char *base,
0409            unsigned offset, unsigned mask)
0410 {
0411     struct ufs_dir_entry *de = (struct ufs_dir_entry*)(base + offset);
0412     struct ufs_dir_entry *p = (struct ufs_dir_entry*)(base + (offset&mask));
0413     while ((char*)p < (char*)de)
0414         p = ufs_next_entry(sb, p);
0415     return (char *)p - base;
0416 }
0417
0418
0419 /*
0420  * This is blatantly stolen from ext2fs
0421  */
0422 static int
0423 ufs_readdir(struct file *file, struct dir_context *ctx)
0424 {
0425     loff_t pos = ctx->pos;
0426     struct inode *inode = file_inode(file);
0427     struct super_block *sb = inode->i_sb;
0428     unsigned int offset = pos & ~PAGE_MASK;
0429     unsigned long n = pos >> PAGE_SHIFT;
0430     unsigned long npages = dir_pages(inode);
0431     unsigned chunk_mask = ~(UFS_SB(sb)->s_uspi->s_dirblksize - 1);
0432     bool need_revalidate = !inode_eq_iversion(inode, file->f_version);
0433     unsigned flags = UFS_SB(sb)->s_flags;
0434
0435     UFSD("BEGIN\n");
0436
0437     if (pos > inode->i_size - UFS_DIR_REC_LEN(1))
0438         return 0;
0439
0440     for ( ; n < npages; n++, offset = 0) {
0441         char *kaddr, *limit;
0442         struct ufs_dir_entry *de;
0443
0444         struct page *page = ufs_get_page(inode, n);
0445
0446         if (IS_ERR(page)) {
0447             ufs_error(sb, __func__,
0448                   "bad page in #%lu",
0449                   inode->i_ino);
0450             ctx->pos += PAGE_SIZE - offset;
0451             return -EIO;
0452         }
0453         kaddr = page_address(page);
0454         if (unlikely(need_revalidate)) {
0455             if (offset) {
0456                 offset = ufs_validate_entry(sb, kaddr, offset, chunk_mask);
0457                 ctx->pos = (n<<PAGE_SHIFT) + offset;
0458             }
0459             file->f_version = inode_query_iversion(inode);
0460             need_revalidate = false;
0461         }
0462         de = (struct ufs_dir_entry *)(kaddr+offset);
0463         limit = kaddr + ufs_last_byte(inode, n) - UFS_DIR_REC_LEN(1);
0464         for ( ;(char*)de <= limit; de = ufs_next_entry(sb, de)) {
0465             if (de->d_ino) {
0466                 unsigned char d_type = DT_UNKNOWN;
0467
0468                 UFSD("filldir(%s,%u)\n", de->d_name,
0469                       fs32_to_cpu(sb, de->d_ino));
0470                 UFSD("namlen %u\n", ufs_get_de_namlen(sb, de));
0471
0472                 if ((flags & UFS_DE_MASK) == UFS_DE_44BSD)
0473                     d_type = de->d_u.d_44.d_type;
0474
0475                 if (!dir_emit(ctx, de->d_name,
0476                            ufs_get_de_namlen(sb, de),
0477                            fs32_to_cpu(sb, de->d_ino),
0478                            d_type)) {
0479                     ufs_put_page(page);
0480                     return 0;
0481                 }
0482             }
0483             ctx->pos += fs16_to_cpu(sb, de->d_reclen);
0484         }
0485         ufs_put_page(page);
0486     }
0487     return 0;
0488 }
0489
0490
0491 /*
0492  * ufs_delete_entry deletes a directory entry by merging it with the
0493  * previous entry.
0494  */
0495 int ufs_delete_entry(struct inode *inode, struct ufs_dir_entry *dir,
0496              struct page * page)
0497 {
0498     struct super_block *sb = inode->i_sb;
0499     char *kaddr = page_address(page);
0500     unsigned from = ((char*)dir - kaddr) & ~(UFS_SB(sb)->s_uspi->s_dirblksize - 1);
0501     unsigned to = ((char*)dir - kaddr) + fs16_to_cpu(sb, dir->d_reclen);
0502     loff_t pos;
0503     struct ufs_dir_entry *pde = NULL;
0504     struct ufs_dir_entry *de = (struct ufs_dir_entry *) (kaddr + from);
0505     int err;
0506
0507     UFSD("ENTER\n");
0508
0509     UFSD("ino %u, reclen %u, namlen %u, name %s\n",
0510           fs32_to_cpu(sb, de->d_ino),
0511           fs16_to_cpu(sb, de->d_reclen),
0512           ufs_get_de_namlen(sb, de), de->d_name);
0513
0514     while ((char*)de < (char*)dir) {
0515         if (de->d_reclen == 0) {
0516             ufs_error(inode->i_sb, __func__,
0517                   "zero-length directory entry");
0518             err = -EIO;
0519             goto out;
0520         }
0521         pde = de;
0522         de = ufs_next_entry(sb, de);
0523     }
0524     if (pde)
0525         from = (char*)pde - (char*)page_address(page);
0526
0527     pos = page_offset(page) + from;
0528     lock_page(page);
0529     err = ufs_prepare_chunk(page, pos, to - from);
0530     BUG_ON(err);
0531     if (pde)
0532         pde->d_reclen = cpu_to_fs16(sb, to - from);
0533     dir->d_ino = 0;
0534     err = ufs_commit_chunk(page, pos, to - from);
0535     inode->i_ctime = inode->i_mtime = current_time(inode);
0536     mark_inode_dirty(inode);
0537 out:
0538     ufs_put_page(page);
0539     UFSD("EXIT\n");
0540     return err;
0541 }
0542
0543 int ufs_make_empty(struct inode * inode, struct inode *dir)
0544 {
0545     struct super_block * sb = dir->i_sb;
0546     struct address_space *mapping = inode->i_mapping;
0547     struct page *page = grab_cache_page(mapping, 0);
0548     const unsigned int chunk_size = UFS_SB(sb)->s_uspi->s_dirblksize;
0549     struct ufs_dir_entry * de;
0550     char *base;
0551     int err;
0552
0553     if (!page)
0554         return -ENOMEM;
0555
0556     err = ufs_prepare_chunk(page, 0, chunk_size);
0557     if (err) {
0558         unlock_page(page);
0559         goto fail;
0560     }
0561
0562     kmap(page);
0563     base = (char*)page_address(page);
0564     memset(base, 0, PAGE_SIZE);
0565
0566     de = (struct ufs_dir_entry *) base;
0567
0568     de->d_ino = cpu_to_fs32(sb, inode->i_ino);
0569     ufs_set_de_type(sb, de, inode->i_mode);
0570     ufs_set_de_namlen(sb, de, 1);
0571     de->d_reclen = cpu_to_fs16(sb, UFS_DIR_REC_LEN(1));
0572     strcpy (de->d_name, ".");
0573     de = (struct ufs_dir_entry *)
0574         ((char *)de + fs16_to_cpu(sb, de->d_reclen));
0575     de->d_ino = cpu_to_fs32(sb, dir->i_ino);
0576     ufs_set_de_type(sb, de, dir->i_mode);
0577     de->d_reclen = cpu_to_fs16(sb, chunk_size - UFS_DIR_REC_LEN(1));
0578     ufs_set_de_namlen(sb, de, 2);
0579     strcpy (de->d_name, "..");
0580     kunmap(page);
0581
0582     err = ufs_commit_chunk(page, 0, chunk_size);
0583 fail:
0584     put_page(page);
0585     return err;
0586 }
0587
0588 /*
0589  * routine to check that the specified directory is empty (for rmdir)
0590  */
0591 int ufs_empty_dir(struct inode * inode)
0592 {
0593     struct super_block *sb = inode->i_sb;
0594     struct page *page = NULL;
0595     unsigned long i, npages = dir_pages(inode);
0596
0597     for (i = 0; i < npages; i++) {
0598         char *kaddr;
0599         struct ufs_dir_entry *de;
0600         page = ufs_get_page(inode, i);
0601
0602         if (IS_ERR(page))
0603             continue;
0604
0605         kaddr = page_address(page);
0606         de = (struct ufs_dir_entry *)kaddr;
0607         kaddr += ufs_last_byte(inode, i) - UFS_DIR_REC_LEN(1);
0608
0609         while ((char *)de <= kaddr) {
0610             if (de->d_reclen == 0) {
0611                 ufs_error(inode->i_sb, __func__,
0612                     "zero-length directory entry: "
0613                     "kaddr=%p, de=%p\n", kaddr, de);
0614                 goto not_empty;
0615             }
0616             if (de->d_ino) {
0617                 u16 namelen=ufs_get_de_namlen(sb, de);
0618                 /* check for . and .. */
0619                 if (de->d_name[0] != '.')
0620                     goto not_empty;
0621                 if (namelen > 2)
0622                     goto not_empty;
0623                 if (namelen < 2) {
0624                     if (inode->i_ino !=
0625                         fs32_to_cpu(sb, de->d_ino))
0626                         goto not_empty;
0627                 } else if (de->d_name[1] != '.')
0628                     goto not_empty;
0629             }
0630             de = ufs_next_entry(sb, de);
0631         }
0632         ufs_put_page(page);
0633     }
0634     return 1;
0635
0636 not_empty:
0637     ufs_put_page(page);
0638     return 0;
0639 }
0640
0641 const struct file_operations ufs_dir_operations = {
0642     .read       = generic_read_dir,
0643     .iterate_shared = ufs_readdir,
0644     .fsync      = generic_file_fsync,
0645     .llseek     = generic_file_llseek,
0646 };