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