fs/omfs/dir.c

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 /*
0003  * OMFS (as used by RIO Karma) directory operations.
0004  * Copyright (C) 2005 Bob Copeland <me@bobcopeland.com>
0005  */
0006
0007 #include <linux/fs.h>
0008 #include <linux/ctype.h>
0009 #include <linux/buffer_head.h>
0010 #include "omfs.h"
0011
0012 static int omfs_hash(const char *name, int namelen, int mod)
0013 {
0014     int i, hash = 0;
0015     for (i = 0; i < namelen; i++)
0016         hash ^= tolower(name[i]) << (i % 24);
0017     return hash % mod;
0018 }
0019
0020 /*
0021  * Finds the bucket for a given name and reads the containing block;
0022  * *ofs is set to the offset of the first list entry.
0023  */
0024 static struct buffer_head *omfs_get_bucket(struct inode *dir,
0025         const char *name, int namelen, int *ofs)
0026 {
0027     int nbuckets = (dir->i_size - OMFS_DIR_START)/8;
0028     int bucket = omfs_hash(name, namelen, nbuckets);
0029
0030     *ofs = OMFS_DIR_START + bucket * 8;
0031     return omfs_bread(dir->i_sb, dir->i_ino);
0032 }
0033
0034 static struct buffer_head *omfs_scan_list(struct inode *dir, u64 block,
0035                 const char *name, int namelen,
0036                 u64 *prev_block)
0037 {
0038     struct buffer_head *bh;
0039     struct omfs_inode *oi;
0040     int err = -ENOENT;
0041     *prev_block = ~0;
0042
0043     while (block != ~0) {
0044         bh = omfs_bread(dir->i_sb, block);
0045         if (!bh) {
0046             err = -EIO;
0047             goto err;
0048         }
0049
0050         oi = (struct omfs_inode *) bh->b_data;
0051         if (omfs_is_bad(OMFS_SB(dir->i_sb), &oi->i_head, block)) {
0052             brelse(bh);
0053             goto err;
0054         }
0055
0056         if (strncmp(oi->i_name, name, namelen) == 0)
0057             return bh;
0058
0059         *prev_block = block;
0060         block = be64_to_cpu(oi->i_sibling);
0061         brelse(bh);
0062     }
0063 err:
0064     return ERR_PTR(err);
0065 }
0066
0067 static struct buffer_head *omfs_find_entry(struct inode *dir,
0068                        const char *name, int namelen)
0069 {
0070     struct buffer_head *bh;
0071     int ofs;
0072     u64 block, dummy;
0073
0074     bh = omfs_get_bucket(dir, name, namelen, &ofs);
0075     if (!bh)
0076         return ERR_PTR(-EIO);
0077
0078     block = be64_to_cpu(*((__be64 *) &bh->b_data[ofs]));
0079     brelse(bh);
0080
0081     return omfs_scan_list(dir, block, name, namelen, &dummy);
0082 }
0083
0084 int omfs_make_empty(struct inode *inode, struct super_block *sb)
0085 {
0086     struct omfs_sb_info *sbi = OMFS_SB(sb);
0087     struct buffer_head *bh;
0088     struct omfs_inode *oi;
0089
0090     bh = omfs_bread(sb, inode->i_ino);
0091     if (!bh)
0092         return -ENOMEM;
0093
0094     memset(bh->b_data, 0, sizeof(struct omfs_inode));
0095
0096     if (S_ISDIR(inode->i_mode)) {
0097         memset(&bh->b_data[OMFS_DIR_START], 0xff,
0098             sbi->s_sys_blocksize - OMFS_DIR_START);
0099     } else
0100         omfs_make_empty_table(bh, OMFS_EXTENT_START);
0101
0102     oi = (struct omfs_inode *) bh->b_data;
0103     oi->i_head.h_self = cpu_to_be64(inode->i_ino);
0104     oi->i_sibling = ~cpu_to_be64(0ULL);
0105
0106     mark_buffer_dirty(bh);
0107     brelse(bh);
0108     return 0;
0109 }
0110
0111 static int omfs_add_link(struct dentry *dentry, struct inode *inode)
0112 {
0113     struct inode *dir = d_inode(dentry->d_parent);
0114     const char *name = dentry->d_name.name;
0115     int namelen = dentry->d_name.len;
0116     struct omfs_inode *oi;
0117     struct buffer_head *bh;
0118     u64 block;
0119     __be64 *entry;
0120     int ofs;
0121
0122     /* just prepend to head of queue in proper bucket */
0123     bh = omfs_get_bucket(dir, name, namelen, &ofs);
0124     if (!bh)
0125         goto out;
0126
0127     entry = (__be64 *) &bh->b_data[ofs];
0128     block = be64_to_cpu(*entry);
0129     *entry = cpu_to_be64(inode->i_ino);
0130     mark_buffer_dirty(bh);
0131     brelse(bh);
0132
0133     /* now set the sibling and parent pointers on the new inode */
0134     bh = omfs_bread(dir->i_sb, inode->i_ino);
0135     if (!bh)
0136         goto out;
0137
0138     oi = (struct omfs_inode *) bh->b_data;
0139     memcpy(oi->i_name, name, namelen);
0140     memset(oi->i_name + namelen, 0, OMFS_NAMELEN - namelen);
0141     oi->i_sibling = cpu_to_be64(block);
0142     oi->i_parent = cpu_to_be64(dir->i_ino);
0143     mark_buffer_dirty(bh);
0144     brelse(bh);
0145
0146     dir->i_ctime = current_time(dir);
0147
0148     /* mark affected inodes dirty to rebuild checksums */
0149     mark_inode_dirty(dir);
0150     mark_inode_dirty(inode);
0151     return 0;
0152 out:
0153     return -ENOMEM;
0154 }
0155
0156 static int omfs_delete_entry(struct dentry *dentry)
0157 {
0158     struct inode *dir = d_inode(dentry->d_parent);
0159     struct inode *dirty;
0160     const char *name = dentry->d_name.name;
0161     int namelen = dentry->d_name.len;
0162     struct omfs_inode *oi;
0163     struct buffer_head *bh, *bh2;
0164     __be64 *entry, next;
0165     u64 block, prev;
0166     int ofs;
0167     int err = -ENOMEM;
0168
0169     /* delete the proper node in the bucket's linked list */
0170     bh = omfs_get_bucket(dir, name, namelen, &ofs);
0171     if (!bh)
0172         goto out;
0173
0174     entry = (__be64 *) &bh->b_data[ofs];
0175     block = be64_to_cpu(*entry);
0176
0177     bh2 = omfs_scan_list(dir, block, name, namelen, &prev);
0178     if (IS_ERR(bh2)) {
0179         err = PTR_ERR(bh2);
0180         goto out_free_bh;
0181     }
0182
0183     oi = (struct omfs_inode *) bh2->b_data;
0184     next = oi->i_sibling;
0185     brelse(bh2);
0186
0187     if (prev != ~0) {
0188         /* found in middle of list, get list ptr */
0189         brelse(bh);
0190         bh = omfs_bread(dir->i_sb, prev);
0191         if (!bh)
0192             goto out;
0193
0194         oi = (struct omfs_inode *) bh->b_data;
0195         entry = &oi->i_sibling;
0196     }
0197
0198     *entry = next;
0199     mark_buffer_dirty(bh);
0200
0201     if (prev != ~0) {
0202         dirty = omfs_iget(dir->i_sb, prev);
0203         if (!IS_ERR(dirty)) {
0204             mark_inode_dirty(dirty);
0205             iput(dirty);
0206         }
0207     }
0208
0209     err = 0;
0210 out_free_bh:
0211     brelse(bh);
0212 out:
0213     return err;
0214 }
0215
0216 static int omfs_dir_is_empty(struct inode *inode)
0217 {
0218     int nbuckets = (inode->i_size - OMFS_DIR_START) / 8;
0219     struct buffer_head *bh;
0220     u64 *ptr;
0221     int i;
0222
0223     bh = omfs_bread(inode->i_sb, inode->i_ino);
0224
0225     if (!bh)
0226         return 0;
0227
0228     ptr = (u64 *) &bh->b_data[OMFS_DIR_START];
0229
0230     for (i = 0; i < nbuckets; i++, ptr++)
0231         if (*ptr != ~0)
0232             break;
0233
0234     brelse(bh);
0235     return *ptr != ~0;
0236 }
0237
0238 static int omfs_remove(struct inode *dir, struct dentry *dentry)
0239 {
0240     struct inode *inode = d_inode(dentry);
0241     int ret;
0242
0243
0244     if (S_ISDIR(inode->i_mode) &&
0245         !omfs_dir_is_empty(inode))
0246         return -ENOTEMPTY;
0247
0248     ret = omfs_delete_entry(dentry);
0249     if (ret)
0250         return ret;
0251
0252     clear_nlink(inode);
0253     mark_inode_dirty(inode);
0254     mark_inode_dirty(dir);
0255     return 0;
0256 }
0257
0258 static int omfs_add_node(struct inode *dir, struct dentry *dentry, umode_t mode)
0259 {
0260     int err;
0261     struct inode *inode = omfs_new_inode(dir, mode);
0262
0263     if (IS_ERR(inode))
0264         return PTR_ERR(inode);
0265
0266     err = omfs_make_empty(inode, dir->i_sb);
0267     if (err)
0268         goto out_free_inode;
0269
0270     err = omfs_add_link(dentry, inode);
0271     if (err)
0272         goto out_free_inode;
0273
0274     d_instantiate(dentry, inode);
0275     return 0;
0276
0277 out_free_inode:
0278     iput(inode);
0279     return err;
0280 }
0281
0282 static int omfs_mkdir(struct user_namespace *mnt_userns, struct inode *dir,
0283               struct dentry *dentry, umode_t mode)
0284 {
0285     return omfs_add_node(dir, dentry, mode | S_IFDIR);
0286 }
0287
0288 static int omfs_create(struct user_namespace *mnt_userns, struct inode *dir,
0289                struct dentry *dentry, umode_t mode, bool excl)
0290 {
0291     return omfs_add_node(dir, dentry, mode | S_IFREG);
0292 }
0293
0294 static struct dentry *omfs_lookup(struct inode *dir, struct dentry *dentry,
0295                   unsigned int flags)
0296 {
0297     struct buffer_head *bh;
0298     struct inode *inode = NULL;
0299
0300     if (dentry->d_name.len > OMFS_NAMELEN)
0301         return ERR_PTR(-ENAMETOOLONG);
0302
0303     bh = omfs_find_entry(dir, dentry->d_name.name, dentry->d_name.len);
0304     if (!IS_ERR(bh)) {
0305         struct omfs_inode *oi = (struct omfs_inode *)bh->b_data;
0306         ino_t ino = be64_to_cpu(oi->i_head.h_self);
0307         brelse(bh);
0308         inode = omfs_iget(dir->i_sb, ino);
0309     } else if (bh != ERR_PTR(-ENOENT)) {
0310         inode = ERR_CAST(bh);
0311     }
0312     return d_splice_alias(inode, dentry);
0313 }
0314
0315 /* sanity check block's self pointer */
0316 int omfs_is_bad(struct omfs_sb_info *sbi, struct omfs_header *header,
0317     u64 fsblock)
0318 {
0319     int is_bad;
0320     u64 ino = be64_to_cpu(header->h_self);
0321     is_bad = ((ino != fsblock) || (ino < sbi->s_root_ino) ||
0322         (ino > sbi->s_num_blocks));
0323
0324     if (is_bad)
0325         printk(KERN_WARNING "omfs: bad hash chain detected\n");
0326
0327     return is_bad;
0328 }
0329
0330 static bool omfs_fill_chain(struct inode *dir, struct dir_context *ctx,
0331         u64 fsblock, int hindex)
0332 {
0333     /* follow chain in this bucket */
0334     while (fsblock != ~0) {
0335         struct buffer_head *bh = omfs_bread(dir->i_sb, fsblock);
0336         struct omfs_inode *oi;
0337         u64 self;
0338         unsigned char d_type;
0339
0340         if (!bh)
0341             return true;
0342
0343         oi = (struct omfs_inode *) bh->b_data;
0344         if (omfs_is_bad(OMFS_SB(dir->i_sb), &oi->i_head, fsblock)) {
0345             brelse(bh);
0346             return true;
0347         }
0348
0349         self = fsblock;
0350         fsblock = be64_to_cpu(oi->i_sibling);
0351
0352         /* skip visited nodes */
0353         if (hindex) {
0354             hindex--;
0355             brelse(bh);
0356             continue;
0357         }
0358
0359         d_type = (oi->i_type == OMFS_DIR) ? DT_DIR : DT_REG;
0360
0361         if (!dir_emit(ctx, oi->i_name,
0362                   strnlen(oi->i_name, OMFS_NAMELEN),
0363                   self, d_type)) {
0364             brelse(bh);
0365             return false;
0366         }
0367         brelse(bh);
0368         ctx->pos++;
0369     }
0370     return true;
0371 }
0372
0373 static int omfs_rename(struct user_namespace *mnt_userns, struct inode *old_dir,
0374                struct dentry *old_dentry, struct inode *new_dir,
0375                struct dentry *new_dentry, unsigned int flags)
0376 {
0377     struct inode *new_inode = d_inode(new_dentry);
0378     struct inode *old_inode = d_inode(old_dentry);
0379     int err;
0380
0381     if (flags & ~RENAME_NOREPLACE)
0382         return -EINVAL;
0383
0384     if (new_inode) {
0385         /* overwriting existing file/dir */
0386         err = omfs_remove(new_dir, new_dentry);
0387         if (err)
0388             goto out;
0389     }
0390
0391     /* since omfs locates files by name, we need to unlink _before_
0392      * adding the new link or we won't find the old one */
0393     err = omfs_delete_entry(old_dentry);
0394     if (err)
0395         goto out;
0396
0397     mark_inode_dirty(old_dir);
0398     err = omfs_add_link(new_dentry, old_inode);
0399     if (err)
0400         goto out;
0401
0402     old_inode->i_ctime = current_time(old_inode);
0403     mark_inode_dirty(old_inode);
0404 out:
0405     return err;
0406 }
0407
0408 static int omfs_readdir(struct file *file, struct dir_context *ctx)
0409 {
0410     struct inode *dir = file_inode(file);
0411     struct buffer_head *bh;
0412     __be64 *p;
0413     unsigned int hchain, hindex;
0414     int nbuckets;
0415
0416     if (ctx->pos >> 32)
0417         return -EINVAL;
0418
0419     if (ctx->pos < 1 << 20) {
0420         if (!dir_emit_dots(file, ctx))
0421             return 0;
0422         ctx->pos = 1 << 20;
0423     }
0424
0425     nbuckets = (dir->i_size - OMFS_DIR_START) / 8;
0426
0427     /* high 12 bits store bucket + 1 and low 20 bits store hash index */
0428     hchain = (ctx->pos >> 20) - 1;
0429     hindex = ctx->pos & 0xfffff;
0430
0431     bh = omfs_bread(dir->i_sb, dir->i_ino);
0432     if (!bh)
0433         return -EINVAL;
0434
0435     p = (__be64 *)(bh->b_data + OMFS_DIR_START) + hchain;
0436
0437     for (; hchain < nbuckets; hchain++) {
0438         __u64 fsblock = be64_to_cpu(*p++);
0439         if (!omfs_fill_chain(dir, ctx, fsblock, hindex))
0440             break;
0441         hindex = 0;
0442         ctx->pos = (hchain+2) << 20;
0443     }
0444     brelse(bh);
0445     return 0;
0446 }
0447
0448 const struct inode_operations omfs_dir_inops = {
0449     .lookup = omfs_lookup,
0450     .mkdir = omfs_mkdir,
0451     .rename = omfs_rename,
0452     .create = omfs_create,
0453     .unlink = omfs_remove,
0454     .rmdir = omfs_remove,
0455 };
0456
0457 const struct file_operations omfs_dir_operations = {
0458     .read = generic_read_dir,
0459     .iterate_shared = omfs_readdir,
0460     .llseek = generic_file_llseek,
0461 };