1 /* 2 * OMFS (as used by RIO Karma) directory operations. 3 * Copyright (C) 2005 Bob Copeland <me@bobcopeland.com> 4 * Released under GPL v2. 5 */ 6 7 #include <linux/fs.h> 8 #include <linux/ctype.h> 9 #include <linux/buffer_head.h> 10 #include "omfs.h" 11 12 static int omfs_hash(const char *name, int namelen, int mod) 13 { 14 int i, hash = 0; 15 for (i = 0; i < namelen; i++) 16 hash ^= tolower(name[i]) << (i % 24); 17 return hash % mod; 18 } 19 20 /* 21 * Finds the bucket for a given name and reads the containing block; 22 * *ofs is set to the offset of the first list entry. 23 */ 24 static struct buffer_head *omfs_get_bucket(struct inode *dir, 25 const char *name, int namelen, int *ofs) 26 { 27 int nbuckets = (dir->i_size - OMFS_DIR_START)/8; 28 int bucket = omfs_hash(name, namelen, nbuckets); 29 30 *ofs = OMFS_DIR_START + bucket * 8; 31 return omfs_bread(dir->i_sb, dir->i_ino); 32 } 33 34 static struct buffer_head *omfs_scan_list(struct inode *dir, u64 block, 35 const char *name, int namelen, 36 u64 *prev_block) 37 { 38 struct buffer_head *bh; 39 struct omfs_inode *oi; 40 int err = -ENOENT; 41 *prev_block = ~0; 42 43 while (block != ~0) { 44 bh = omfs_bread(dir->i_sb, block); 45 if (!bh) { 46 err = -EIO; 47 goto err; 48 } 49 50 oi = (struct omfs_inode *) bh->b_data; 51 if (omfs_is_bad(OMFS_SB(dir->i_sb), &oi->i_head, block)) { 52 brelse(bh); 53 goto err; 54 } 55 56 if (strncmp(oi->i_name, name, namelen) == 0) 57 return bh; 58 59 *prev_block = block; 60 block = be64_to_cpu(oi->i_sibling); 61 brelse(bh); 62 } 63 err: 64 return ERR_PTR(err); 65 } 66 67 static struct buffer_head *omfs_find_entry(struct inode *dir, 68 const char *name, int namelen) 69 { 70 struct buffer_head *bh; 71 int ofs; 72 u64 block, dummy; 73 74 bh = omfs_get_bucket(dir, name, namelen, &ofs); 75 if (!bh) 76 return ERR_PTR(-EIO); 77 78 block = be64_to_cpu(*((__be64 *) &bh->b_data[ofs])); 79 brelse(bh); 80 81 return omfs_scan_list(dir, block, name, namelen, &dummy); 82 } 83 84 int omfs_make_empty(struct inode *inode, struct super_block *sb) 85 { 86 struct omfs_sb_info *sbi = OMFS_SB(sb); 87 struct buffer_head *bh; 88 struct omfs_inode *oi; 89 90 bh = omfs_bread(sb, inode->i_ino); 91 if (!bh) 92 return -ENOMEM; 93 94 memset(bh->b_data, 0, sizeof(struct omfs_inode)); 95 96 if (inode->i_mode & S_IFDIR) { 97 memset(&bh->b_data[OMFS_DIR_START], 0xff, 98 sbi->s_sys_blocksize - OMFS_DIR_START); 99 } else 100 omfs_make_empty_table(bh, OMFS_EXTENT_START); 101 102 oi = (struct omfs_inode *) bh->b_data; 103 oi->i_head.h_self = cpu_to_be64(inode->i_ino); 104 oi->i_sibling = ~cpu_to_be64(0ULL); 105 106 mark_buffer_dirty(bh); 107 brelse(bh); 108 return 0; 109 } 110 111 static int omfs_add_link(struct dentry *dentry, struct inode *inode) 112 { 113 struct inode *dir = dentry->d_parent->d_inode; 114 const char *name = dentry->d_name.name; 115 int namelen = dentry->d_name.len; 116 struct omfs_inode *oi; 117 struct buffer_head *bh; 118 u64 block; 119 __be64 *entry; 120 int ofs; 121 122 /* just prepend to head of queue in proper bucket */ 123 bh = omfs_get_bucket(dir, name, namelen, &ofs); 124 if (!bh) 125 goto out; 126 127 entry = (__be64 *) &bh->b_data[ofs]; 128 block = be64_to_cpu(*entry); 129 *entry = cpu_to_be64(inode->i_ino); 130 mark_buffer_dirty(bh); 131 brelse(bh); 132 133 /* now set the sibling and parent pointers on the new inode */ 134 bh = omfs_bread(dir->i_sb, inode->i_ino); 135 if (!bh) 136 goto out; 137 138 oi = (struct omfs_inode *) bh->b_data; 139 memcpy(oi->i_name, name, namelen); 140 memset(oi->i_name + namelen, 0, OMFS_NAMELEN - namelen); 141 oi->i_sibling = cpu_to_be64(block); 142 oi->i_parent = cpu_to_be64(dir->i_ino); 143 mark_buffer_dirty(bh); 144 brelse(bh); 145 146 dir->i_ctime = CURRENT_TIME_SEC; 147 148 /* mark affected inodes dirty to rebuild checksums */ 149 mark_inode_dirty(dir); 150 mark_inode_dirty(inode); 151 return 0; 152 out: 153 return -ENOMEM; 154 } 155 156 static int omfs_delete_entry(struct dentry *dentry) 157 { 158 struct inode *dir = dentry->d_parent->d_inode; 159 struct inode *dirty; 160 const char *name = dentry->d_name.name; 161 int namelen = dentry->d_name.len; 162 struct omfs_inode *oi; 163 struct buffer_head *bh, *bh2; 164 __be64 *entry, next; 165 u64 block, prev; 166 int ofs; 167 int err = -ENOMEM; 168 169 /* delete the proper node in the bucket's linked list */ 170 bh = omfs_get_bucket(dir, name, namelen, &ofs); 171 if (!bh) 172 goto out; 173 174 entry = (__be64 *) &bh->b_data[ofs]; 175 block = be64_to_cpu(*entry); 176 177 bh2 = omfs_scan_list(dir, block, name, namelen, &prev); 178 if (IS_ERR(bh2)) { 179 err = PTR_ERR(bh2); 180 goto out_free_bh; 181 } 182 183 oi = (struct omfs_inode *) bh2->b_data; 184 next = oi->i_sibling; 185 brelse(bh2); 186 187 if (prev != ~0) { 188 /* found in middle of list, get list ptr */ 189 brelse(bh); 190 bh = omfs_bread(dir->i_sb, prev); 191 if (!bh) 192 goto out; 193 194 oi = (struct omfs_inode *) bh->b_data; 195 entry = &oi->i_sibling; 196 } 197 198 *entry = next; 199 mark_buffer_dirty(bh); 200 201 if (prev != ~0) { 202 dirty = omfs_iget(dir->i_sb, prev); 203 if (!IS_ERR(dirty)) { 204 mark_inode_dirty(dirty); 205 iput(dirty); 206 } 207 } 208 209 err = 0; 210 out_free_bh: 211 brelse(bh); 212 out: 213 return err; 214 } 215 216 static int omfs_dir_is_empty(struct inode *inode) 217 { 218 int nbuckets = (inode->i_size - OMFS_DIR_START) / 8; 219 struct buffer_head *bh; 220 u64 *ptr; 221 int i; 222 223 bh = omfs_bread(inode->i_sb, inode->i_ino); 224 225 if (!bh) 226 return 0; 227 228 ptr = (u64 *) &bh->b_data[OMFS_DIR_START]; 229 230 for (i = 0; i < nbuckets; i++, ptr++) 231 if (*ptr != ~0) 232 break; 233 234 brelse(bh); 235 return *ptr != ~0; 236 } 237 238 static int omfs_unlink(struct inode *dir, struct dentry *dentry) 239 { 240 int ret; 241 struct inode *inode = dentry->d_inode; 242 243 ret = omfs_delete_entry(dentry); 244 if (ret) 245 goto end_unlink; 246 247 inode_dec_link_count(inode); 248 mark_inode_dirty(dir); 249 250 end_unlink: 251 return ret; 252 } 253 254 static int omfs_rmdir(struct inode *dir, struct dentry *dentry) 255 { 256 int err = -ENOTEMPTY; 257 struct inode *inode = dentry->d_inode; 258 259 if (omfs_dir_is_empty(inode)) { 260 err = omfs_unlink(dir, dentry); 261 if (!err) 262 inode_dec_link_count(inode); 263 } 264 return err; 265 } 266 267 static int omfs_add_node(struct inode *dir, struct dentry *dentry, int mode) 268 { 269 int err; 270 struct inode *inode = omfs_new_inode(dir, mode); 271 272 if (IS_ERR(inode)) 273 return PTR_ERR(inode); 274 275 err = omfs_make_empty(inode, dir->i_sb); 276 if (err) 277 goto out_free_inode; 278 279 err = omfs_add_link(dentry, inode); 280 if (err) 281 goto out_free_inode; 282 283 d_instantiate(dentry, inode); 284 return 0; 285 286 out_free_inode: 287 iput(inode); 288 return err; 289 } 290 291 static int omfs_mkdir(struct inode *dir, struct dentry *dentry, int mode) 292 { 293 return omfs_add_node(dir, dentry, mode | S_IFDIR); 294 } 295 296 static int omfs_create(struct inode *dir, struct dentry *dentry, int mode, 297 struct nameidata *nd) 298 { 299 return omfs_add_node(dir, dentry, mode | S_IFREG); 300 } 301 302 static struct dentry *omfs_lookup(struct inode *dir, struct dentry *dentry, 303 struct nameidata *nd) 304 { 305 struct buffer_head *bh; 306 struct inode *inode = NULL; 307 308 if (dentry->d_name.len > OMFS_NAMELEN) 309 return ERR_PTR(-ENAMETOOLONG); 310 311 bh = omfs_find_entry(dir, dentry->d_name.name, dentry->d_name.len); 312 if (!IS_ERR(bh)) { 313 struct omfs_inode *oi = (struct omfs_inode *)bh->b_data; 314 ino_t ino = be64_to_cpu(oi->i_head.h_self); 315 brelse(bh); 316 inode = omfs_iget(dir->i_sb, ino); 317 if (IS_ERR(inode)) 318 return ERR_CAST(inode); 319 } 320 d_add(dentry, inode); 321 return NULL; 322 } 323 324 /* sanity check block's self pointer */ 325 int omfs_is_bad(struct omfs_sb_info *sbi, struct omfs_header *header, 326 u64 fsblock) 327 { 328 int is_bad; 329 u64 ino = be64_to_cpu(header->h_self); 330 is_bad = ((ino != fsblock) || (ino < sbi->s_root_ino) || 331 (ino > sbi->s_num_blocks)); 332 333 if (is_bad) 334 printk(KERN_WARNING "omfs: bad hash chain detected\n"); 335 336 return is_bad; 337 } 338 339 static int omfs_fill_chain(struct file *filp, void *dirent, filldir_t filldir, 340 u64 fsblock, int hindex) 341 { 342 struct inode *dir = filp->f_dentry->d_inode; 343 struct buffer_head *bh; 344 struct omfs_inode *oi; 345 u64 self; 346 int res = 0; 347 unsigned char d_type; 348 349 /* follow chain in this bucket */ 350 while (fsblock != ~0) { 351 bh = omfs_bread(dir->i_sb, fsblock); 352 if (!bh) 353 goto out; 354 355 oi = (struct omfs_inode *) bh->b_data; 356 if (omfs_is_bad(OMFS_SB(dir->i_sb), &oi->i_head, fsblock)) { 357 brelse(bh); 358 goto out; 359 } 360 361 self = fsblock; 362 fsblock = be64_to_cpu(oi->i_sibling); 363 364 /* skip visited nodes */ 365 if (hindex) { 366 hindex--; 367 brelse(bh); 368 continue; 369 } 370 371 d_type = (oi->i_type == OMFS_DIR) ? DT_DIR : DT_REG; 372 373 res = filldir(dirent, oi->i_name, strnlen(oi->i_name, 374 OMFS_NAMELEN), filp->f_pos, self, d_type); 375 if (res == 0) 376 filp->f_pos++; 377 brelse(bh); 378 } 379 out: 380 return res; 381 } 382 383 static int omfs_rename(struct inode *old_dir, struct dentry *old_dentry, 384 struct inode *new_dir, struct dentry *new_dentry) 385 { 386 struct inode *new_inode = new_dentry->d_inode; 387 struct inode *old_inode = old_dentry->d_inode; 388 struct buffer_head *bh; 389 int is_dir; 390 int err; 391 392 is_dir = S_ISDIR(old_inode->i_mode); 393 394 if (new_inode) { 395 /* overwriting existing file/dir */ 396 err = -ENOTEMPTY; 397 if (is_dir && !omfs_dir_is_empty(new_inode)) 398 goto out; 399 400 err = -ENOENT; 401 bh = omfs_find_entry(new_dir, new_dentry->d_name.name, 402 new_dentry->d_name.len); 403 if (IS_ERR(bh)) 404 goto out; 405 brelse(bh); 406 407 err = omfs_unlink(new_dir, new_dentry); 408 if (err) 409 goto out; 410 } 411 412 /* since omfs locates files by name, we need to unlink _before_ 413 * adding the new link or we won't find the old one */ 414 inode_inc_link_count(old_inode); 415 err = omfs_unlink(old_dir, old_dentry); 416 if (err) { 417 inode_dec_link_count(old_inode); 418 goto out; 419 } 420 421 err = omfs_add_link(new_dentry, old_inode); 422 if (err) 423 goto out; 424 425 old_inode->i_ctime = CURRENT_TIME_SEC; 426 out: 427 return err; 428 } 429 430 static int omfs_readdir(struct file *filp, void *dirent, filldir_t filldir) 431 { 432 struct inode *dir = filp->f_dentry->d_inode; 433 struct buffer_head *bh; 434 loff_t offset, res; 435 unsigned int hchain, hindex; 436 int nbuckets; 437 u64 fsblock; 438 int ret = -EINVAL; 439 440 if (filp->f_pos >> 32) 441 goto success; 442 443 switch ((unsigned long) filp->f_pos) { 444 case 0: 445 if (filldir(dirent, ".", 1, 0, dir->i_ino, DT_DIR) < 0) 446 goto success; 447 filp->f_pos++; 448 /* fall through */ 449 case 1: 450 if (filldir(dirent, "..", 2, 1, 451 parent_ino(filp->f_dentry), DT_DIR) < 0) 452 goto success; 453 filp->f_pos = 1 << 20; 454 /* fall through */ 455 } 456 457 nbuckets = (dir->i_size - OMFS_DIR_START) / 8; 458 459 /* high 12 bits store bucket + 1 and low 20 bits store hash index */ 460 hchain = (filp->f_pos >> 20) - 1; 461 hindex = filp->f_pos & 0xfffff; 462 463 bh = omfs_bread(dir->i_sb, dir->i_ino); 464 if (!bh) 465 goto out; 466 467 offset = OMFS_DIR_START + hchain * 8; 468 469 for (; hchain < nbuckets; hchain++, offset += 8) { 470 fsblock = be64_to_cpu(*((__be64 *) &bh->b_data[offset])); 471 472 res = omfs_fill_chain(filp, dirent, filldir, fsblock, hindex); 473 hindex = 0; 474 if (res < 0) 475 break; 476 477 filp->f_pos = (hchain+2) << 20; 478 } 479 brelse(bh); 480 success: 481 ret = 0; 482 out: 483 return ret; 484 } 485 486 const struct inode_operations omfs_dir_inops = { 487 .lookup = omfs_lookup, 488 .mkdir = omfs_mkdir, 489 .rename = omfs_rename, 490 .create = omfs_create, 491 .unlink = omfs_unlink, 492 .rmdir = omfs_rmdir, 493 }; 494 495 const struct file_operations omfs_dir_operations = { 496 .read = generic_read_dir, 497 .readdir = omfs_readdir, 498 .llseek = generic_file_llseek, 499 }; 500