1 /* 2 * Copyright (C) Sistina Software, Inc. 1997-2003 All rights reserved. 3 * Copyright (C) 2004-2006 Red Hat, Inc. All rights reserved. 4 * 5 * This copyrighted material is made available to anyone wishing to use, 6 * modify, copy, or redistribute it subject to the terms and conditions 7 * of the GNU General Public License version 2. 8 */ 9 10 /* 11 * Implements Extendible Hashing as described in: 12 * "Extendible Hashing" by Fagin, et al in 13 * __ACM Trans. on Database Systems__, Sept 1979. 14 * 15 * 16 * Here's the layout of dirents which is essentially the same as that of ext2 17 * within a single block. The field de_name_len is the number of bytes 18 * actually required for the name (no null terminator). The field de_rec_len 19 * is the number of bytes allocated to the dirent. The offset of the next 20 * dirent in the block is (dirent + dirent->de_rec_len). When a dirent is 21 * deleted, the preceding dirent inherits its allocated space, ie 22 * prev->de_rec_len += deleted->de_rec_len. Since the next dirent is obtained 23 * by adding de_rec_len to the current dirent, this essentially causes the 24 * deleted dirent to get jumped over when iterating through all the dirents. 25 * 26 * When deleting the first dirent in a block, there is no previous dirent so 27 * the field de_ino is set to zero to designate it as deleted. When allocating 28 * a dirent, gfs2_dirent_alloc iterates through the dirents in a block. If the 29 * first dirent has (de_ino == 0) and de_rec_len is large enough, this first 30 * dirent is allocated. Otherwise it must go through all the 'used' dirents 31 * searching for one in which the amount of total space minus the amount of 32 * used space will provide enough space for the new dirent. 33 * 34 * There are two types of blocks in which dirents reside. In a stuffed dinode, 35 * the dirents begin at offset sizeof(struct gfs2_dinode) from the beginning of 36 * the block. In leaves, they begin at offset sizeof(struct gfs2_leaf) from the 37 * beginning of the leaf block. The dirents reside in leaves when 38 * 39 * dip->i_di.di_flags & GFS2_DIF_EXHASH is true 40 * 41 * Otherwise, the dirents are "linear", within a single stuffed dinode block. 42 * 43 * When the dirents are in leaves, the actual contents of the directory file are 44 * used as an array of 64-bit block pointers pointing to the leaf blocks. The 45 * dirents are NOT in the directory file itself. There can be more than one 46 * block pointer in the array that points to the same leaf. In fact, when a 47 * directory is first converted from linear to exhash, all of the pointers 48 * point to the same leaf. 49 * 50 * When a leaf is completely full, the size of the hash table can be 51 * doubled unless it is already at the maximum size which is hard coded into 52 * GFS2_DIR_MAX_DEPTH. After that, leaves are chained together in a linked list, 53 * but never before the maximum hash table size has been reached. 54 */ 55 56 #include <linux/slab.h> 57 #include <linux/spinlock.h> 58 #include <linux/buffer_head.h> 59 #include <linux/sort.h> 60 #include <linux/gfs2_ondisk.h> 61 #include <linux/crc32.h> 62 #include <linux/vmalloc.h> 63 #include <linux/lm_interface.h> 64 65 #include "gfs2.h" 66 #include "incore.h" 67 #include "dir.h" 68 #include "glock.h" 69 #include "inode.h" 70 #include "meta_io.h" 71 #include "quota.h" 72 #include "rgrp.h" 73 #include "trans.h" 74 #include "bmap.h" 75 #include "util.h" 76 77 #define IS_LEAF 1 /* Hashed (leaf) directory */ 78 #define IS_DINODE 2 /* Linear (stuffed dinode block) directory */ 79 80 #define gfs2_disk_hash2offset(h) (((u64)(h)) >> 1) 81 #define gfs2_dir_offset2hash(p) ((u32)(((u64)(p)) << 1)) 82 83 typedef int (*leaf_call_t) (struct gfs2_inode *dip, u32 index, u32 len, 84 u64 leaf_no, void *data); 85 typedef int (*gfs2_dscan_t)(const struct gfs2_dirent *dent, 86 const struct qstr *name, void *opaque); 87 88 89 int gfs2_dir_get_new_buffer(struct gfs2_inode *ip, u64 block, 90 struct buffer_head **bhp) 91 { 92 struct buffer_head *bh; 93 94 bh = gfs2_meta_new(ip->i_gl, block); 95 gfs2_trans_add_bh(ip->i_gl, bh, 1); 96 gfs2_metatype_set(bh, GFS2_METATYPE_JD, GFS2_FORMAT_JD); 97 gfs2_buffer_clear_tail(bh, sizeof(struct gfs2_meta_header)); 98 *bhp = bh; 99 return 0; 100 } 101 102 static int gfs2_dir_get_existing_buffer(struct gfs2_inode *ip, u64 block, 103 struct buffer_head **bhp) 104 { 105 struct buffer_head *bh; 106 int error; 107 108 error = gfs2_meta_read(ip->i_gl, block, DIO_WAIT, &bh); 109 if (error) 110 return error; 111 if (gfs2_metatype_check(GFS2_SB(&ip->i_inode), bh, GFS2_METATYPE_JD)) { 112 brelse(bh); 113 return -EIO; 114 } 115 *bhp = bh; 116 return 0; 117 } 118 119 static int gfs2_dir_write_stuffed(struct gfs2_inode *ip, const char *buf, 120 unsigned int offset, unsigned int size) 121 { 122 struct buffer_head *dibh; 123 int error; 124 125 error = gfs2_meta_inode_buffer(ip, &dibh); 126 if (error) 127 return error; 128 129 gfs2_trans_add_bh(ip->i_gl, dibh, 1); 130 memcpy(dibh->b_data + offset + sizeof(struct gfs2_dinode), buf, size); 131 if (ip->i_di.di_size < offset + size) 132 ip->i_di.di_size = offset + size; 133 ip->i_inode.i_mtime = ip->i_inode.i_ctime = CURRENT_TIME; 134 gfs2_dinode_out(ip, dibh->b_data); 135 136 brelse(dibh); 137 138 return size; 139 } 140 141 142 143 /** 144 * gfs2_dir_write_data - Write directory information to the inode 145 * @ip: The GFS2 inode 146 * @buf: The buffer containing information to be written 147 * @offset: The file offset to start writing at 148 * @size: The amount of data to write 149 * 150 * Returns: The number of bytes correctly written or error code 151 */ 152 static int gfs2_dir_write_data(struct gfs2_inode *ip, const char *buf, 153 u64 offset, unsigned int size) 154 { 155 struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode); 156 struct buffer_head *dibh; 157 u64 lblock, dblock; 158 u32 extlen = 0; 159 unsigned int o; 160 int copied = 0; 161 int error = 0; 162 int new = 0; 163 164 if (!size) 165 return 0; 166 167 if (gfs2_is_stuffed(ip) && 168 offset + size <= sdp->sd_sb.sb_bsize - sizeof(struct gfs2_dinode)) 169 return gfs2_dir_write_stuffed(ip, buf, (unsigned int)offset, 170 size); 171 172 if (gfs2_assert_warn(sdp, gfs2_is_jdata(ip))) 173 return -EINVAL; 174 175 if (gfs2_is_stuffed(ip)) { 176 error = gfs2_unstuff_dinode(ip, NULL); 177 if (error) 178 return error; 179 } 180 181 lblock = offset; 182 o = do_div(lblock, sdp->sd_jbsize) + sizeof(struct gfs2_meta_header); 183 184 while (copied < size) { 185 unsigned int amount; 186 struct buffer_head *bh; 187 188 amount = size - copied; 189 if (amount > sdp->sd_sb.sb_bsize - o) 190 amount = sdp->sd_sb.sb_bsize - o; 191 192 if (!extlen) { 193 new = 1; 194 error = gfs2_extent_map(&ip->i_inode, lblock, &new, 195 &dblock, &extlen); 196 if (error) 197 goto fail; 198 error = -EIO; 199 if (gfs2_assert_withdraw(sdp, dblock)) 200 goto fail; 201 } 202 203 if (amount == sdp->sd_jbsize || new) 204 error = gfs2_dir_get_new_buffer(ip, dblock, &bh); 205 else 206 error = gfs2_dir_get_existing_buffer(ip, dblock, &bh); 207 208 if (error) 209 goto fail; 210 211 gfs2_trans_add_bh(ip->i_gl, bh, 1); 212 memcpy(bh->b_data + o, buf, amount); 213 brelse(bh); 214 215 buf += amount; 216 copied += amount; 217 lblock++; 218 dblock++; 219 extlen--; 220 221 o = sizeof(struct gfs2_meta_header); 222 } 223 224 out: 225 error = gfs2_meta_inode_buffer(ip, &dibh); 226 if (error) 227 return error; 228 229 if (ip->i_di.di_size < offset + copied) 230 ip->i_di.di_size = offset + copied; 231 ip->i_inode.i_mtime = ip->i_inode.i_ctime = CURRENT_TIME; 232 233 gfs2_trans_add_bh(ip->i_gl, dibh, 1); 234 gfs2_dinode_out(ip, dibh->b_data); 235 brelse(dibh); 236 237 return copied; 238 fail: 239 if (copied) 240 goto out; 241 return error; 242 } 243 244 static int gfs2_dir_read_stuffed(struct gfs2_inode *ip, char *buf, 245 u64 offset, unsigned int size) 246 { 247 struct buffer_head *dibh; 248 int error; 249 250 error = gfs2_meta_inode_buffer(ip, &dibh); 251 if (!error) { 252 offset += sizeof(struct gfs2_dinode); 253 memcpy(buf, dibh->b_data + offset, size); 254 brelse(dibh); 255 } 256 257 return (error) ? error : size; 258 } 259 260 261 /** 262 * gfs2_dir_read_data - Read a data from a directory inode 263 * @ip: The GFS2 Inode 264 * @buf: The buffer to place result into 265 * @offset: File offset to begin jdata_readng from 266 * @size: Amount of data to transfer 267 * 268 * Returns: The amount of data actually copied or the error 269 */ 270 static int gfs2_dir_read_data(struct gfs2_inode *ip, char *buf, u64 offset, 271 unsigned int size, unsigned ra) 272 { 273 struct gfs2_sbd *sdp = GFS2_SB(&ip->i_inode); 274 u64 lblock, dblock; 275 u32 extlen = 0; 276 unsigned int o; 277 int copied = 0; 278 int error = 0; 279 280 if (offset >= ip->i_di.di_size) 281 return 0; 282 283 if (offset + size > ip->i_di.di_size) 284 size = ip->i_di.di_size - offset; 285 286 if (!size) 287 return 0; 288 289 if (gfs2_is_stuffed(ip)) 290 return gfs2_dir_read_stuffed(ip, buf, offset, size); 291 292 if (gfs2_assert_warn(sdp, gfs2_is_jdata(ip))) 293 return -EINVAL; 294 295 lblock = offset; 296 o = do_div(lblock, sdp->sd_jbsize) + sizeof(struct gfs2_meta_header); 297 298 while (copied < size) { 299 unsigned int amount; 300 struct buffer_head *bh; 301 int new; 302 303 amount = size - copied; 304 if (amount > sdp->sd_sb.sb_bsize - o) 305 amount = sdp->sd_sb.sb_bsize - o; 306 307 if (!extlen) { 308 new = 0; 309 error = gfs2_extent_map(&ip->i_inode, lblock, &new, 310 &dblock, &extlen); 311 if (error || !dblock) 312 goto fail; 313 BUG_ON(extlen < 1); 314 if (!ra) 315 extlen = 1; 316 bh = gfs2_meta_ra(ip->i_gl, dblock, extlen); 317 } else { 318 error = gfs2_meta_read(ip->i_gl, dblock, DIO_WAIT, &bh); 319 if (error) 320 goto fail; 321 } 322 error = gfs2_metatype_check(sdp, bh, GFS2_METATYPE_JD); 323 if (error) { 324 brelse(bh); 325 goto fail; 326 } 327 dblock++; 328 extlen--; 329 memcpy(buf, bh->b_data + o, amount); 330 brelse(bh); 331 buf += amount; 332 copied += amount; 333 lblock++; 334 o = sizeof(struct gfs2_meta_header); 335 } 336 337 return copied; 338 fail: 339 return (copied) ? copied : error; 340 } 341 342 static inline int gfs2_dirent_sentinel(const struct gfs2_dirent *dent) 343 { 344 return dent->de_inum.no_addr == 0 || dent->de_inum.no_formal_ino == 0; 345 } 346 347 static inline int __gfs2_dirent_find(const struct gfs2_dirent *dent, 348 const struct qstr *name, int ret) 349 { 350 if (!gfs2_dirent_sentinel(dent) && 351 be32_to_cpu(dent->de_hash) == name->hash && 352 be16_to_cpu(dent->de_name_len) == name->len && 353 memcmp(dent+1, name->name, name->len) == 0) 354 return ret; 355 return 0; 356 } 357 358 static int gfs2_dirent_find(const struct gfs2_dirent *dent, 359 const struct qstr *name, 360 void *opaque) 361 { 362 return __gfs2_dirent_find(dent, name, 1); 363 } 364 365 static int gfs2_dirent_prev(const struct gfs2_dirent *dent, 366 const struct qstr *name, 367 void *opaque) 368 { 369 return __gfs2_dirent_find(dent, name, 2); 370 } 371 372 /* 373 * name->name holds ptr to start of block. 374 * name->len holds size of block. 375 */ 376 static int gfs2_dirent_last(const struct gfs2_dirent *dent, 377 const struct qstr *name, 378 void *opaque) 379 { 380 const char *start = name->name; 381 const char *end = (const char *)dent + be16_to_cpu(dent->de_rec_len); 382 if (name->len == (end - start)) 383 return 1; 384 return 0; 385 } 386 387 static int gfs2_dirent_find_space(const struct gfs2_dirent *dent, 388 const struct qstr *name, 389 void *opaque) 390 { 391 unsigned required = GFS2_DIRENT_SIZE(name->len); 392 unsigned actual = GFS2_DIRENT_SIZE(be16_to_cpu(dent->de_name_len)); 393 unsigned totlen = be16_to_cpu(dent->de_rec_len); 394 395 if (gfs2_dirent_sentinel(dent)) 396 actual = GFS2_DIRENT_SIZE(0); 397 if (totlen - actual >= required) 398 return 1; 399 return 0; 400 } 401 402 struct dirent_gather { 403 const struct gfs2_dirent **pdent; 404 unsigned offset; 405 }; 406 407 static int gfs2_dirent_gather(const struct gfs2_dirent *dent, 408 const struct qstr *name, 409 void *opaque) 410 { 411 struct dirent_gather *g = opaque; 412 if (!gfs2_dirent_sentinel(dent)) { 413 g->pdent[g->offset++] = dent; 414 } 415 return 0; 416 } 417 418 /* 419 * Other possible things to check: 420 * - Inode located within filesystem size (and on valid block) 421 * - Valid directory entry type 422 * Not sure how heavy-weight we want to make this... could also check 423 * hash is correct for example, but that would take a lot of extra time. 424 * For now the most important thing is to check that the various sizes 425 * are correct. 426 */ 427 static int gfs2_check_dirent(struct gfs2_dirent *dent, unsigned int offset, 428 unsigned int size, unsigned int len, int first) 429 { 430 const char *msg = "gfs2_dirent too small"; 431 if (unlikely(size < sizeof(struct gfs2_dirent))) 432 goto error; 433 msg = "gfs2_dirent misaligned"; 434 if (unlikely(offset & 0x7)) 435 goto error; 436 msg = "gfs2_dirent points beyond end of block"; 437 if (unlikely(offset + size > len)) 438 goto error; 439 msg = "zero inode number"; 440 if (unlikely(!first && gfs2_dirent_sentinel(dent))) 441 goto error; 442 msg = "name length is greater than space in dirent"; 443 if (!gfs2_dirent_sentinel(dent) && 444 unlikely(sizeof(struct gfs2_dirent)+be16_to_cpu(dent->de_name_len) > 445 size)) 446 goto error; 447 return 0; 448 error: 449 printk(KERN_WARNING "gfs2_check_dirent: %s (%s)\n", msg, 450 first ? "first in block" : "not first in block"); 451 return -EIO; 452 } 453 454 static int gfs2_dirent_offset(const void *buf) 455 { 456 const struct gfs2_meta_header *h = buf; 457 int offset; 458 459 BUG_ON(buf == NULL); 460 461 switch(be32_to_cpu(h->mh_type)) { 462 case GFS2_METATYPE_LF: 463 offset = sizeof(struct gfs2_leaf); 464 break; 465 case GFS2_METATYPE_DI: 466 offset = sizeof(struct gfs2_dinode); 467 break; 468 default: 469 goto wrong_type; 470 } 471 return offset; 472 wrong_type: 473 printk(KERN_WARNING "gfs2_scan_dirent: wrong block type %u\n", 474 be32_to_cpu(h->mh_type)); 475 return -1; 476 } 477 478 static struct gfs2_dirent *gfs2_dirent_scan(struct inode *inode, void *buf, 479 unsigned int len, gfs2_dscan_t scan, 480 const struct qstr *name, 481 void *opaque) 482 { 483 struct gfs2_dirent *dent, *prev; 484 unsigned offset; 485 unsigned size; 486 int ret = 0; 487 488 ret = gfs2_dirent_offset(buf); 489 if (ret < 0) 490 goto consist_inode; 491 492 offset = ret; 493 prev = NULL; 494 dent = buf + offset; 495 size = be16_to_cpu(dent->de_rec_len); 496 if (gfs2_check_dirent(dent, offset, size, len, 1)) 497 goto consist_inode; 498 do { 499 ret = scan(dent, name, opaque); 500 if (ret) 501 break; 502 offset += size; 503 if (offset == len) 504 break; 505 prev = dent; 506 dent = buf + offset; 507 size = be16_to_cpu(dent->de_rec_len); 508 if (gfs2_check_dirent(dent, offset, size, len, 0)) 509 goto consist_inode; 510 } while(1); 511 512 switch(ret) { 513 case 0: 514 return NULL; 515 case 1: 516 return dent; 517 case 2: 518 return prev ? prev : dent; 519 default: 520 BUG_ON(ret > 0); 521 return ERR_PTR(ret); 522 } 523 524 consist_inode: 525 gfs2_consist_inode(GFS2_I(inode)); 526 return ERR_PTR(-EIO); 527 } 528 529 530 /** 531 * dirent_first - Return the first dirent 532 * @dip: the directory 533 * @bh: The buffer 534 * @dent: Pointer to list of dirents 535 * 536 * return first dirent whether bh points to leaf or stuffed dinode 537 * 538 * Returns: IS_LEAF, IS_DINODE, or -errno 539 */ 540 541 static int dirent_first(struct gfs2_inode *dip, struct buffer_head *bh, 542 struct gfs2_dirent **dent) 543 { 544 struct gfs2_meta_header *h = (struct gfs2_meta_header *)bh->b_data; 545 546 if (be32_to_cpu(h->mh_type) == GFS2_METATYPE_LF) { 547 if (gfs2_meta_check(GFS2_SB(&dip->i_inode), bh)) 548 return -EIO; 549 *dent = (struct gfs2_dirent *)(bh->b_data + 550 sizeof(struct gfs2_leaf)); 551 return IS_LEAF; 552 } else { 553 if (gfs2_metatype_check(GFS2_SB(&dip->i_inode), bh, GFS2_METATYPE_DI)) 554 return -EIO; 555 *dent = (struct gfs2_dirent *)(bh->b_data + 556 sizeof(struct gfs2_dinode)); 557 return IS_DINODE; 558 } 559 } 560 561 static int dirent_check_reclen(struct gfs2_inode *dip, 562 const struct gfs2_dirent *d, const void *end_p) 563 { 564 const void *ptr = d; 565 u16 rec_len = be16_to_cpu(d->de_rec_len); 566 567 if (unlikely(rec_len < sizeof(struct gfs2_dirent))) 568 goto broken; 569 ptr += rec_len; 570 if (ptr < end_p) 571 return rec_len; 572 if (ptr == end_p) 573 return -ENOENT; 574 broken: 575 gfs2_consist_inode(dip); 576 return -EIO; 577 } 578 579 /** 580 * dirent_next - Next dirent 581 * @dip: the directory 582 * @bh: The buffer 583 * @dent: Pointer to list of dirents 584 * 585 * Returns: 0 on success, error code otherwise 586 */ 587 588 static int dirent_next(struct gfs2_inode *dip, struct buffer_head *bh, 589 struct gfs2_dirent **dent) 590 { 591 struct gfs2_dirent *cur = *dent, *tmp; 592 char *bh_end = bh->b_data + bh->b_size; 593 int ret; 594 595 ret = dirent_check_reclen(dip, cur, bh_end); 596 if (ret < 0) 597 return ret; 598 599 tmp = (void *)cur + ret; 600 ret = dirent_check_reclen(dip, tmp, bh_end); 601 if (ret == -EIO) 602 return ret; 603 604 /* Only the first dent could ever have de_inum.no_addr == 0 */ 605 if (gfs2_dirent_sentinel(tmp)) { 606 gfs2_consist_inode(dip); 607 return -EIO; 608 } 609 610 *dent = tmp; 611 return 0; 612 } 613 614 /** 615 * dirent_del - Delete a dirent 616 * @dip: The GFS2 inode 617 * @bh: The buffer 618 * @prev: The previous dirent 619 * @cur: The current dirent 620 * 621 */ 622 623 static void dirent_del(struct gfs2_inode *dip, struct buffer_head *bh, 624 struct gfs2_dirent *prev, struct gfs2_dirent *cur) 625 { 626 u16 cur_rec_len, prev_rec_len; 627 628 if (gfs2_dirent_sentinel(cur)) { 629 gfs2_consist_inode(dip); 630 return; 631 } 632 633 gfs2_trans_add_bh(dip->i_gl, bh, 1); 634 635 /* If there is no prev entry, this is the first entry in the block. 636 The de_rec_len is already as big as it needs to be. Just zero 637 out the inode number and return. */ 638 639 if (!prev) { 640 cur->de_inum.no_addr = 0; 641 cur->de_inum.no_formal_ino = 0; 642 return; 643 } 644 645 /* Combine this dentry with the previous one. */ 646 647 prev_rec_len = be16_to_cpu(prev->de_rec_len); 648 cur_rec_len = be16_to_cpu(cur->de_rec_len); 649 650 if ((char *)prev + prev_rec_len != (char *)cur) 651 gfs2_consist_inode(dip); 652 if ((char *)cur + cur_rec_len > bh->b_data + bh->b_size) 653 gfs2_consist_inode(dip); 654 655 prev_rec_len += cur_rec_len; 656 prev->de_rec_len = cpu_to_be16(prev_rec_len); 657 } 658 659 /* 660 * Takes a dent from which to grab space as an argument. Returns the 661 * newly created dent. 662 */ 663 static struct gfs2_dirent *gfs2_init_dirent(struct inode *inode, 664 struct gfs2_dirent *dent, 665 const struct qstr *name, 666 struct buffer_head *bh) 667 { 668 struct gfs2_inode *ip = GFS2_I(inode); 669 struct gfs2_dirent *ndent; 670 unsigned offset = 0, totlen; 671 672 if (!gfs2_dirent_sentinel(dent)) 673 offset = GFS2_DIRENT_SIZE(be16_to_cpu(dent->de_name_len)); 674 totlen = be16_to_cpu(dent->de_rec_len); 675 BUG_ON(offset + name->len > totlen); 676 gfs2_trans_add_bh(ip->i_gl, bh, 1); 677 ndent = (struct gfs2_dirent *)((char *)dent + offset); 678 dent->de_rec_len = cpu_to_be16(offset); 679 gfs2_qstr2dirent(name, totlen - offset, ndent); 680 return ndent; 681 } 682 683 static struct gfs2_dirent *gfs2_dirent_alloc(struct inode *inode, 684 struct buffer_head *bh, 685 const struct qstr *name) 686 { 687 struct gfs2_dirent *dent; 688 dent = gfs2_dirent_scan(inode, bh->b_data, bh->b_size, 689 gfs2_dirent_find_space, name, NULL); 690 if (!dent || IS_ERR(dent)) 691 return dent; 692 return gfs2_init_dirent(inode, dent, name, bh); 693 } 694 695 static int get_leaf(struct gfs2_inode *dip, u64 leaf_no, 696 struct buffer_head **bhp) 697 { 698 int error; 699 700 error = gfs2_meta_read(dip->i_gl, leaf_no, DIO_WAIT, bhp); 701 if (!error && gfs2_metatype_check(GFS2_SB(&dip->i_inode), *bhp, GFS2_METATYPE_LF)) { 702 /* printk(KERN_INFO "block num=%llu\n", leaf_no); */ 703 error = -EIO; 704 } 705 706 return error; 707 } 708 709 /** 710 * get_leaf_nr - Get a leaf number associated with the index 711 * @dip: The GFS2 inode 712 * @index: 713 * @leaf_out: 714 * 715 * Returns: 0 on success, error code otherwise 716 */ 717 718 static int get_leaf_nr(struct gfs2_inode *dip, u32 index, 719 u64 *leaf_out) 720 { 721 __be64 leaf_no; 722 int error; 723 724 error = gfs2_dir_read_data(dip, (char *)&leaf_no, 725 index * sizeof(__be64), 726 sizeof(__be64), 0); 727 if (error != sizeof(u64)) 728 return (error < 0) ? error : -EIO; 729 730 *leaf_out = be64_to_cpu(leaf_no); 731 732 return 0; 733 } 734 735 static int get_first_leaf(struct gfs2_inode *dip, u32 index, 736 struct buffer_head **bh_out) 737 { 738 u64 leaf_no; 739 int error; 740 741 error = get_leaf_nr(dip, index, &leaf_no); 742 if (!error) 743 error = get_leaf(dip, leaf_no, bh_out); 744 745 return error; 746 } 747 748 static struct gfs2_dirent *gfs2_dirent_search(struct inode *inode, 749 const struct qstr *name, 750 gfs2_dscan_t scan, 751 struct buffer_head **pbh) 752 { 753 struct buffer_head *bh; 754 struct gfs2_dirent *dent; 755 struct gfs2_inode *ip = GFS2_I(inode); 756 int error; 757 758 if (ip->i_di.di_flags & GFS2_DIF_EXHASH) { 759 struct gfs2_leaf *leaf; 760 unsigned hsize = 1 << ip->i_depth; 761 unsigned index; 762 u64 ln; 763 if (hsize * sizeof(u64) != ip->i_di.di_size) { 764 gfs2_consist_inode(ip); 765 return ERR_PTR(-EIO); 766 } 767 768 index = name->hash >> (32 - ip->i_depth); 769 error = get_first_leaf(ip, index, &bh); 770 if (error) 771 return ERR_PTR(error); 772 do { 773 dent = gfs2_dirent_scan(inode, bh->b_data, bh->b_size, 774 scan, name, NULL); 775 if (dent) 776 goto got_dent; 777 leaf = (struct gfs2_leaf *)bh->b_data; 778 ln = be64_to_cpu(leaf->lf_next); 779 brelse(bh); 780 if (!ln) 781 break; 782 783 error = get_leaf(ip, ln, &bh); 784 } while(!error); 785 786 return error ? ERR_PTR(error) : NULL; 787 } 788 789 790 error = gfs2_meta_inode_buffer(ip, &bh); 791 if (error) 792 return ERR_PTR(error); 793 dent = gfs2_dirent_scan(inode, bh->b_data, bh->b_size, scan, name, NULL); 794 got_dent: 795 if (unlikely(dent == NULL || IS_ERR(dent))) { 796 brelse(bh); 797 bh = NULL; 798 } 799 *pbh = bh; 800 return dent; 801 } 802 803 static struct gfs2_leaf *new_leaf(struct inode *inode, struct buffer_head **pbh, u16 depth) 804 { 805 struct gfs2_inode *ip = GFS2_I(inode); 806 unsigned int n = 1; 807 u64 bn = gfs2_alloc_block(ip, &n); 808 struct buffer_head *bh = gfs2_meta_new(ip->i_gl, bn); 809 struct gfs2_leaf *leaf; 810 struct gfs2_dirent *dent; 811 struct qstr name = { .name = "", .len = 0, .hash = 0 }; 812 if (!bh) 813 return NULL; 814 gfs2_trans_add_unrevoke(GFS2_SB(inode), bn, 1); 815 gfs2_trans_add_bh(ip->i_gl, bh, 1); 816 gfs2_metatype_set(bh, GFS2_METATYPE_LF, GFS2_FORMAT_LF); 817 leaf = (struct gfs2_leaf *)bh->b_data; 818 leaf->lf_depth = cpu_to_be16(depth); 819 leaf->lf_entries = 0; 820 leaf->lf_dirent_format = cpu_to_be32(GFS2_FORMAT_DE); 821 leaf->lf_next = 0; 822 memset(leaf->lf_reserved, 0, sizeof(leaf->lf_reserved)); 823 dent = (struct gfs2_dirent *)(leaf+1); 824 gfs2_qstr2dirent(&name, bh->b_size - sizeof(struct gfs2_leaf), dent); 825 *pbh = bh; 826 return leaf; 827 } 828 829 /** 830 * dir_make_exhash - Convert a stuffed directory into an ExHash directory 831 * @dip: The GFS2 inode 832 * 833 * Returns: 0 on success, error code otherwise 834 */ 835 836 static int dir_make_exhash(struct inode *inode) 837 { 838 struct gfs2_inode *dip = GFS2_I(inode); 839 struct gfs2_sbd *sdp = GFS2_SB(inode); 840 struct gfs2_dirent *dent; 841 struct qstr args; 842 struct buffer_head *bh, *dibh; 843 struct gfs2_leaf *leaf; 844 int y; 845 u32 x; 846 __be64 *lp; 847 u64 bn; 848 int error; 849 850 error = gfs2_meta_inode_buffer(dip, &dibh); 851 if (error) 852 return error; 853 854 /* Turn over a new leaf */ 855 856 leaf = new_leaf(inode, &bh, 0); 857 if (!leaf) 858 return -ENOSPC; 859 bn = bh->b_blocknr; 860 861 gfs2_assert(sdp, dip->i_di.di_entries < (1 << 16)); 862 leaf->lf_entries = cpu_to_be16(dip->i_di.di_entries); 863 864 /* Copy dirents */ 865 866 gfs2_buffer_copy_tail(bh, sizeof(struct gfs2_leaf), dibh, 867 sizeof(struct gfs2_dinode)); 868 869 /* Find last entry */ 870 871 x = 0; 872 args.len = bh->b_size - sizeof(struct gfs2_dinode) + 873 sizeof(struct gfs2_leaf); 874 args.name = bh->b_data; 875 dent = gfs2_dirent_scan(&dip->i_inode, bh->b_data, bh->b_size, 876 gfs2_dirent_last, &args, NULL); 877 if (!dent) { 878 brelse(bh); 879 brelse(dibh); 880 return -EIO; 881 } 882 if (IS_ERR(dent)) { 883 brelse(bh); 884 brelse(dibh); 885 return PTR_ERR(dent); 886 } 887 888 /* Adjust the last dirent's record length 889 (Remember that dent still points to the last entry.) */ 890 891 dent->de_rec_len = cpu_to_be16(be16_to_cpu(dent->de_rec_len) + 892 sizeof(struct gfs2_dinode) - 893 sizeof(struct gfs2_leaf)); 894 895 brelse(bh); 896 897 /* We're done with the new leaf block, now setup the new 898 hash table. */ 899 900 gfs2_trans_add_bh(dip->i_gl, dibh, 1); 901 gfs2_buffer_clear_tail(dibh, sizeof(struct gfs2_dinode)); 902 903 lp = (__be64 *)(dibh->b_data + sizeof(struct gfs2_dinode)); 904 905 for (x = sdp->sd_hash_ptrs; x--; lp++) 906 *lp = cpu_to_be64(bn); 907 908 dip->i_di.di_size = sdp->sd_sb.sb_bsize / 2; 909 gfs2_add_inode_blocks(&dip->i_inode, 1); 910 dip->i_di.di_flags |= GFS2_DIF_EXHASH; 911 912 for (x = sdp->sd_hash_ptrs, y = -1; x; x >>= 1, y++) ; 913 dip->i_depth = y; 914 915 gfs2_dinode_out(dip, dibh->b_data); 916 917 brelse(dibh); 918 919 return 0; 920 } 921 922 /** 923 * dir_split_leaf - Split a leaf block into two 924 * @dip: The GFS2 inode 925 * @index: 926 * @leaf_no: 927 * 928 * Returns: 0 on success, error code on failure 929 */ 930 931 static int dir_split_leaf(struct inode *inode, const struct qstr *name) 932 { 933 struct gfs2_inode *dip = GFS2_I(inode); 934 struct buffer_head *nbh, *obh, *dibh; 935 struct gfs2_leaf *nleaf, *oleaf; 936 struct gfs2_dirent *dent = NULL, *prev = NULL, *next = NULL, *new; 937 u32 start, len, half_len, divider; 938 u64 bn, leaf_no; 939 __be64 *lp; 940 u32 index; 941 int x, moved = 0; 942 int error; 943 944 index = name->hash >> (32 - dip->i_depth); 945 error = get_leaf_nr(dip, index, &leaf_no); 946 if (error) 947 return error; 948 949 /* Get the old leaf block */ 950 error = get_leaf(dip, leaf_no, &obh); 951 if (error) 952 return error; 953 954 oleaf = (struct gfs2_leaf *)obh->b_data; 955 if (dip->i_depth == be16_to_cpu(oleaf->lf_depth)) { 956 brelse(obh); 957 return 1; /* can't split */ 958 } 959 960 gfs2_trans_add_bh(dip->i_gl, obh, 1); 961 962 nleaf = new_leaf(inode, &nbh, be16_to_cpu(oleaf->lf_depth) + 1); 963 if (!nleaf) { 964 brelse(obh); 965 return -ENOSPC; 966 } 967 bn = nbh->b_blocknr; 968 969 /* Compute the start and len of leaf pointers in the hash table. */ 970 len = 1 << (dip->i_depth - be16_to_cpu(oleaf->lf_depth)); 971 half_len = len >> 1; 972 if (!half_len) { 973 printk(KERN_WARNING "i_depth %u lf_depth %u index %u\n", dip->i_depth, be16_to_cpu(oleaf->lf_depth), index); 974 gfs2_consist_inode(dip); 975 error = -EIO; 976 goto fail_brelse; 977 } 978 979 start = (index & ~(len - 1)); 980 981 /* Change the pointers. 982 Don't bother distinguishing stuffed from non-stuffed. 983 This code is complicated enough already. */ 984 lp = kmalloc(half_len * sizeof(__be64), GFP_NOFS | __GFP_NOFAIL); 985 /* Change the pointers */ 986 for (x = 0; x < half_len; x++) 987 lp[x] = cpu_to_be64(bn); 988 989 error = gfs2_dir_write_data(dip, (char *)lp, start * sizeof(u64), 990 half_len * sizeof(u64)); 991 if (error != half_len * sizeof(u64)) { 992 if (error >= 0) 993 error = -EIO; 994 goto fail_lpfree; 995 } 996 997 kfree(lp); 998 999 /* Compute the divider */ 1000 divider = (start + half_len) << (32 - dip->i_depth); 1001 1002 /* Copy the entries */ 1003 dirent_first(dip, obh, &dent); 1004 1005 do { 1006 next = dent; 1007 if (dirent_next(dip, obh, &next)) 1008 next = NULL; 1009 1010 if (!gfs2_dirent_sentinel(dent) && 1011 be32_to_cpu(dent->de_hash) < divider) { 1012 struct qstr str; 1013 str.name = (char*)(dent+1); 1014 str.len = be16_to_cpu(dent->de_name_len); 1015 str.hash = be32_to_cpu(dent->de_hash); 1016 new = gfs2_dirent_alloc(inode, nbh, &str); 1017 if (IS_ERR(new)) { 1018 error = PTR_ERR(new); 1019 break; 1020 } 1021 1022 new->de_inum = dent->de_inum; /* No endian worries */ 1023 new->de_type = dent->de_type; /* No endian worries */ 1024 be16_add_cpu(&nleaf->lf_entries, 1); 1025 1026 dirent_del(dip, obh, prev, dent); 1027 1028 if (!oleaf->lf_entries) 1029 gfs2_consist_inode(dip); 1030 be16_add_cpu(&oleaf->lf_entries, -1); 1031 1032 if (!prev) 1033 prev = dent; 1034 1035 moved = 1; 1036 } else { 1037 prev = dent; 1038 } 1039 dent = next; 1040 } while (dent); 1041 1042 oleaf->lf_depth = nleaf->lf_depth; 1043 1044 error = gfs2_meta_inode_buffer(dip, &dibh); 1045 if (!gfs2_assert_withdraw(GFS2_SB(&dip->i_inode), !error)) { 1046 gfs2_trans_add_bh(dip->i_gl, dibh, 1); 1047 gfs2_add_inode_blocks(&dip->i_inode, 1); 1048 gfs2_dinode_out(dip, dibh->b_data); 1049 brelse(dibh); 1050 } 1051 1052 brelse(obh); 1053 brelse(nbh); 1054 1055 return error; 1056 1057 fail_lpfree: 1058 kfree(lp); 1059 1060 fail_brelse: 1061 brelse(obh); 1062 brelse(nbh); 1063 return error; 1064 } 1065 1066 /** 1067 * dir_double_exhash - Double size of ExHash table 1068 * @dip: The GFS2 dinode 1069 * 1070 * Returns: 0 on success, error code on failure 1071 */ 1072 1073 static int dir_double_exhash(struct gfs2_inode *dip) 1074 { 1075 struct gfs2_sbd *sdp = GFS2_SB(&dip->i_inode); 1076 struct buffer_head *dibh; 1077 u32 hsize; 1078 u64 *buf; 1079 u64 *from, *to; 1080 u64 block; 1081 int x; 1082 int error = 0; 1083 1084 hsize = 1 << dip->i_depth; 1085 if (hsize * sizeof(u64) != dip->i_di.di_size) { 1086 gfs2_consist_inode(dip); 1087 return -EIO; 1088 } 1089 1090 /* Allocate both the "from" and "to" buffers in one big chunk */ 1091 1092 buf = kcalloc(3, sdp->sd_hash_bsize, GFP_NOFS | __GFP_NOFAIL); 1093 1094 for (block = dip->i_di.di_size >> sdp->sd_hash_bsize_shift; block--;) { 1095 error = gfs2_dir_read_data(dip, (char *)buf, 1096 block * sdp->sd_hash_bsize, 1097 sdp->sd_hash_bsize, 1); 1098 if (error != sdp->sd_hash_bsize) { 1099 if (error >= 0) 1100 error = -EIO; 1101 goto fail; 1102 } 1103 1104 from = buf; 1105 to = (u64 *)((char *)buf + sdp->sd_hash_bsize); 1106 1107 for (x = sdp->sd_hash_ptrs; x--; from++) { 1108 *to++ = *from; /* No endianess worries */ 1109 *to++ = *from; 1110 } 1111 1112 error = gfs2_dir_write_data(dip, 1113 (char *)buf + sdp->sd_hash_bsize, 1114 block * sdp->sd_sb.sb_bsize, 1115 sdp->sd_sb.sb_bsize); 1116 if (error != sdp->sd_sb.sb_bsize) { 1117 if (error >= 0) 1118 error = -EIO; 1119 goto fail; 1120 } 1121 } 1122 1123 kfree(buf); 1124 1125 error = gfs2_meta_inode_buffer(dip, &dibh); 1126 if (!gfs2_assert_withdraw(sdp, !error)) { 1127 dip->i_depth++; 1128 gfs2_dinode_out(dip, dibh->b_data); 1129 brelse(dibh); 1130 } 1131 1132 return error; 1133 1134 fail: 1135 kfree(buf); 1136 return error; 1137 } 1138 1139 /** 1140 * compare_dents - compare directory entries by hash value 1141 * @a: first dent 1142 * @b: second dent 1143 * 1144 * When comparing the hash entries of @a to @b: 1145 * gt: returns 1 1146 * lt: returns -1 1147 * eq: returns 0 1148 */ 1149 1150 static int compare_dents(const void *a, const void *b) 1151 { 1152 const struct gfs2_dirent *dent_a, *dent_b; 1153 u32 hash_a, hash_b; 1154 int ret = 0; 1155 1156 dent_a = *(const struct gfs2_dirent **)a; 1157 hash_a = be32_to_cpu(dent_a->de_hash); 1158 1159 dent_b = *(const struct gfs2_dirent **)b; 1160 hash_b = be32_to_cpu(dent_b->de_hash); 1161 1162 if (hash_a > hash_b) 1163 ret = 1; 1164 else if (hash_a < hash_b) 1165 ret = -1; 1166 else { 1167 unsigned int len_a = be16_to_cpu(dent_a->de_name_len); 1168 unsigned int len_b = be16_to_cpu(dent_b->de_name_len); 1169 1170 if (len_a > len_b) 1171 ret = 1; 1172 else if (len_a < len_b) 1173 ret = -1; 1174 else 1175 ret = memcmp(dent_a + 1, dent_b + 1, len_a); 1176 } 1177 1178 return ret; 1179 } 1180 1181 /** 1182 * do_filldir_main - read out directory entries 1183 * @dip: The GFS2 inode 1184 * @offset: The offset in the file to read from 1185 * @opaque: opaque data to pass to filldir 1186 * @filldir: The function to pass entries to 1187 * @darr: an array of struct gfs2_dirent pointers to read 1188 * @entries: the number of entries in darr 1189 * @copied: pointer to int that's non-zero if a entry has been copied out 1190 * 1191 * Jump through some hoops to make sure that if there are hash collsions, 1192 * they are read out at the beginning of a buffer. We want to minimize 1193 * the possibility that they will fall into different readdir buffers or 1194 * that someone will want to seek to that location. 1195 * 1196 * Returns: errno, >0 on exception from filldir 1197 */ 1198 1199 static int do_filldir_main(struct gfs2_inode *dip, u64 *offset, 1200 void *opaque, filldir_t filldir, 1201 const struct gfs2_dirent **darr, u32 entries, 1202 int *copied) 1203 { 1204 const struct gfs2_dirent *dent, *dent_next; 1205 u64 off, off_next; 1206 unsigned int x, y; 1207 int run = 0; 1208 int error = 0; 1209 1210 sort(darr, entries, sizeof(struct gfs2_dirent *), compare_dents, NULL); 1211 1212 dent_next = darr[0]; 1213 off_next = be32_to_cpu(dent_next->de_hash); 1214 off_next = gfs2_disk_hash2offset(off_next); 1215 1216 for (x = 0, y = 1; x < entries; x++, y++) { 1217 dent = dent_next; 1218 off = off_next; 1219 1220 if (y < entries) { 1221 dent_next = darr[y]; 1222 off_next = be32_to_cpu(dent_next->de_hash); 1223 off_next = gfs2_disk_hash2offset(off_next); 1224 1225 if (off < *offset) 1226 continue; 1227 *offset = off; 1228 1229 if (off_next == off) { 1230 if (*copied && !run) 1231 return 1; 1232 run = 1; 1233 } else 1234 run = 0; 1235 } else { 1236 if (off < *offset) 1237 continue; 1238 *offset = off; 1239 } 1240 1241 error = filldir(opaque, (const char *)(dent + 1), 1242 be16_to_cpu(dent->de_name_len), 1243 off, be64_to_cpu(dent->de_inum.no_addr), 1244 be16_to_cpu(dent->de_type)); 1245 if (error) 1246 return 1; 1247 1248 *copied = 1; 1249 } 1250 1251 /* Increment the *offset by one, so the next time we come into the 1252 do_filldir fxn, we get the next entry instead of the last one in the 1253 current leaf */ 1254 1255 (*offset)++; 1256 1257 return 0; 1258 } 1259 1260 static int gfs2_dir_read_leaf(struct inode *inode, u64 *offset, void *opaque, 1261 filldir_t filldir, int *copied, unsigned *depth, 1262 u64 leaf_no) 1263 { 1264 struct gfs2_inode *ip = GFS2_I(inode); 1265 struct gfs2_sbd *sdp = GFS2_SB(inode); 1266 struct buffer_head *bh; 1267 struct gfs2_leaf *lf; 1268 unsigned entries = 0, entries2 = 0; 1269 unsigned leaves = 0; 1270 const struct gfs2_dirent **darr, *dent; 1271 struct dirent_gather g; 1272 struct buffer_head **larr; 1273 int leaf = 0; 1274 int error, i; 1275 u64 lfn = leaf_no; 1276 1277 do { 1278 error = get_leaf(ip, lfn, &bh); 1279 if (error) 1280 goto out; 1281 lf = (struct gfs2_leaf *)bh->b_data; 1282 if (leaves == 0) 1283 *depth = be16_to_cpu(lf->lf_depth); 1284 entries += be16_to_cpu(lf->lf_entries); 1285 leaves++; 1286 lfn = be64_to_cpu(lf->lf_next); 1287 brelse(bh); 1288 } while(lfn); 1289 1290 if (!entries) 1291 return 0; 1292 1293 error = -ENOMEM; 1294 /* 1295 * The extra 99 entries are not normally used, but are a buffer 1296 * zone in case the number of entries in the leaf is corrupt. 1297 * 99 is the maximum number of entries that can fit in a single 1298 * leaf block. 1299 */ 1300 larr = vmalloc((leaves + entries + 99) * sizeof(void *)); 1301 if (!larr) 1302 goto out; 1303 darr = (const struct gfs2_dirent **)(larr + leaves); 1304 g.pdent = darr; 1305 g.offset = 0; 1306 lfn = leaf_no; 1307 1308 do { 1309 error = get_leaf(ip, lfn, &bh); 1310 if (error) 1311 goto out_kfree; 1312 lf = (struct gfs2_leaf *)bh->b_data; 1313 lfn = be64_to_cpu(lf->lf_next); 1314 if (lf->lf_entries) { 1315 entries2 += be16_to_cpu(lf->lf_entries); 1316 dent = gfs2_dirent_scan(inode, bh->b_data, bh->b_size, 1317 gfs2_dirent_gather, NULL, &g); 1318 error = PTR_ERR(dent); 1319 if (IS_ERR(dent)) 1320 goto out_kfree; 1321 if (entries2 != g.offset) { 1322 fs_warn(sdp, "Number of entries corrupt in dir " 1323 "leaf %llu, entries2 (%u) != " 1324 "g.offset (%u)\n", 1325 (unsigned long long)bh->b_blocknr, 1326 entries2, g.offset); 1327 1328 error = -EIO; 1329 goto out_kfree; 1330 } 1331 error = 0; 1332 larr[leaf++] = bh; 1333 } else { 1334 brelse(bh); 1335 } 1336 } while(lfn); 1337 1338 BUG_ON(entries2 != entries); 1339 error = do_filldir_main(ip, offset, opaque, filldir, darr, 1340 entries, copied); 1341 out_kfree: 1342 for(i = 0; i < leaf; i++) 1343 brelse(larr[i]); 1344 vfree(larr); 1345 out: 1346 return error; 1347 } 1348 1349 /** 1350 * dir_e_read - Reads the entries from a directory into a filldir buffer 1351 * @dip: dinode pointer 1352 * @offset: the hash of the last entry read shifted to the right once 1353 * @opaque: buffer for the filldir function to fill 1354 * @filldir: points to the filldir function to use 1355 * 1356 * Returns: errno 1357 */ 1358 1359 static int dir_e_read(struct inode *inode, u64 *offset, void *opaque, 1360 filldir_t filldir) 1361 { 1362 struct gfs2_inode *dip = GFS2_I(inode); 1363 struct gfs2_sbd *sdp = GFS2_SB(inode); 1364 u32 hsize, len = 0; 1365 u32 ht_offset, lp_offset, ht_offset_cur = -1; 1366 u32 hash, index; 1367 __be64 *lp; 1368 int copied = 0; 1369 int error = 0; 1370 unsigned depth = 0; 1371 1372 hsize = 1 << dip->i_depth; 1373 if (hsize * sizeof(u64) != dip->i_di.di_size) { 1374 gfs2_consist_inode(dip); 1375 return -EIO; 1376 } 1377 1378 hash = gfs2_dir_offset2hash(*offset); 1379 index = hash >> (32 - dip->i_depth); 1380 1381 lp = kmalloc(sdp->sd_hash_bsize, GFP_NOFS); 1382 if (!lp) 1383 return -ENOMEM; 1384 1385 while (index < hsize) { 1386 lp_offset = index & (sdp->sd_hash_ptrs - 1); 1387 ht_offset = index - lp_offset; 1388 1389 if (ht_offset_cur != ht_offset) { 1390 error = gfs2_dir_read_data(dip, (char *)lp, 1391 ht_offset * sizeof(__be64), 1392 sdp->sd_hash_bsize, 1); 1393 if (error != sdp->sd_hash_bsize) { 1394 if (error >= 0) 1395 error = -EIO; 1396 goto out; 1397 } 1398 ht_offset_cur = ht_offset; 1399 } 1400 1401 error = gfs2_dir_read_leaf(inode, offset, opaque, filldir, 1402 &copied, &depth, 1403 be64_to_cpu(lp[lp_offset])); 1404 if (error) 1405 break; 1406 1407 len = 1 << (dip->i_depth - depth); 1408 index = (index & ~(len - 1)) + len; 1409 } 1410 1411 out: 1412 kfree(lp); 1413 if (error > 0) 1414 error = 0; 1415 return error; 1416 } 1417 1418 int gfs2_dir_read(struct inode *inode, u64 *offset, void *opaque, 1419 filldir_t filldir) 1420 { 1421 struct gfs2_inode *dip = GFS2_I(inode); 1422 struct gfs2_sbd *sdp = GFS2_SB(inode); 1423 struct dirent_gather g; 1424 const struct gfs2_dirent **darr, *dent; 1425 struct buffer_head *dibh; 1426 int copied = 0; 1427 int error; 1428 1429 if (!dip->i_di.di_entries) 1430 return 0; 1431 1432 if (dip->i_di.di_flags & GFS2_DIF_EXHASH) 1433 return dir_e_read(inode, offset, opaque, filldir); 1434 1435 if (!gfs2_is_stuffed(dip)) { 1436 gfs2_consist_inode(dip); 1437 return -EIO; 1438 } 1439 1440 error = gfs2_meta_inode_buffer(dip, &dibh); 1441 if (error) 1442 return error; 1443 1444 error = -ENOMEM; 1445 /* 96 is max number of dirents which can be stuffed into an inode */ 1446 darr = kmalloc(96 * sizeof(struct gfs2_dirent *), GFP_NOFS); 1447 if (darr) { 1448 g.pdent = darr; 1449 g.offset = 0; 1450 dent = gfs2_dirent_scan(inode, dibh->b_data, dibh->b_size, 1451 gfs2_dirent_gather, NULL, &g); 1452 if (IS_ERR(dent)) { 1453 error = PTR_ERR(dent); 1454 goto out; 1455 } 1456 if (dip->i_di.di_entries != g.offset) { 1457 fs_warn(sdp, "Number of entries corrupt in dir %llu, " 1458 "ip->i_di.di_entries (%u) != g.offset (%u)\n", 1459 (unsigned long long)dip->i_no_addr, 1460 dip->i_di.di_entries, 1461 g.offset); 1462 error = -EIO; 1463 goto out; 1464 } 1465 error = do_filldir_main(dip, offset, opaque, filldir, darr, 1466 dip->i_di.di_entries, &copied); 1467 out: 1468 kfree(darr); 1469 } 1470 1471 if (error > 0) 1472 error = 0; 1473 1474 brelse(dibh); 1475 1476 return error; 1477 } 1478 1479 /** 1480 * gfs2_dir_search - Search a directory 1481 * @dip: The GFS2 inode 1482 * @filename: 1483 * @inode: 1484 * 1485 * This routine searches a directory for a file or another directory. 1486 * Assumes a glock is held on dip. 1487 * 1488 * Returns: errno 1489 */ 1490 1491 struct inode *gfs2_dir_search(struct inode *dir, const struct qstr *name) 1492 { 1493 struct buffer_head *bh; 1494 struct gfs2_dirent *dent; 1495 struct inode *inode; 1496 1497 dent = gfs2_dirent_search(dir, name, gfs2_dirent_find, &bh); 1498 if (dent) { 1499 if (IS_ERR(dent)) 1500 return ERR_CAST(dent); 1501 inode = gfs2_inode_lookup(dir->i_sb, 1502 be16_to_cpu(dent->de_type), 1503 be64_to_cpu(dent->de_inum.no_addr), 1504 be64_to_cpu(dent->de_inum.no_formal_ino), 0); 1505 brelse(bh); 1506 return inode; 1507 } 1508 return ERR_PTR(-ENOENT); 1509 } 1510 1511 int gfs2_dir_check(struct inode *dir, const struct qstr *name, 1512 const struct gfs2_inode *ip) 1513 { 1514 struct buffer_head *bh; 1515 struct gfs2_dirent *dent; 1516 int ret = -ENOENT; 1517 1518 dent = gfs2_dirent_search(dir, name, gfs2_dirent_find, &bh); 1519 if (dent) { 1520 if (IS_ERR(dent)) 1521 return PTR_ERR(dent); 1522 if (ip) { 1523 if (be64_to_cpu(dent->de_inum.no_addr) != ip->i_no_addr) 1524 goto out; 1525 if (be64_to_cpu(dent->de_inum.no_formal_ino) != 1526 ip->i_no_formal_ino) 1527 goto out; 1528 if (unlikely(IF2DT(ip->i_inode.i_mode) != 1529 be16_to_cpu(dent->de_type))) { 1530 gfs2_consist_inode(GFS2_I(dir)); 1531 ret = -EIO; 1532 goto out; 1533 } 1534 } 1535 ret = 0; 1536 out: 1537 brelse(bh); 1538 } 1539 return ret; 1540 } 1541 1542 static int dir_new_leaf(struct inode *inode, const struct qstr *name) 1543 { 1544 struct buffer_head *bh, *obh; 1545 struct gfs2_inode *ip = GFS2_I(inode); 1546 struct gfs2_leaf *leaf, *oleaf; 1547 int error; 1548 u32 index; 1549 u64 bn; 1550 1551 index = name->hash >> (32 - ip->i_depth); 1552 error = get_first_leaf(ip, index, &obh); 1553 if (error) 1554 return error; 1555 do { 1556 oleaf = (struct gfs2_leaf *)obh->b_data; 1557 bn = be64_to_cpu(oleaf->lf_next); 1558 if (!bn) 1559 break; 1560 brelse(obh); 1561 error = get_leaf(ip, bn, &obh); 1562 if (error) 1563 return error; 1564 } while(1); 1565 1566 gfs2_trans_add_bh(ip->i_gl, obh, 1); 1567 1568 leaf = new_leaf(inode, &bh, be16_to_cpu(oleaf->lf_depth)); 1569 if (!leaf) { 1570 brelse(obh); 1571 return -ENOSPC; 1572 } 1573 oleaf->lf_next = cpu_to_be64(bh->b_blocknr); 1574 brelse(bh); 1575 brelse(obh); 1576 1577 error = gfs2_meta_inode_buffer(ip, &bh); 1578 if (error) 1579 return error; 1580 gfs2_trans_add_bh(ip->i_gl, bh, 1); 1581 gfs2_add_inode_blocks(&ip->i_inode, 1); 1582 gfs2_dinode_out(ip, bh->b_data); 1583 brelse(bh); 1584 return 0; 1585 } 1586 1587 /** 1588 * gfs2_dir_add - Add new filename into directory 1589 * @dip: The GFS2 inode 1590 * @filename: The new name 1591 * @inode: The inode number of the entry 1592 * @type: The type of the entry 1593 * 1594 * Returns: 0 on success, error code on failure 1595 */ 1596 1597 int gfs2_dir_add(struct inode *inode, const struct qstr *name, 1598 const struct gfs2_inode *nip, unsigned type) 1599 { 1600 struct gfs2_inode *ip = GFS2_I(inode); 1601 struct buffer_head *bh; 1602 struct gfs2_dirent *dent; 1603 struct gfs2_leaf *leaf; 1604 int error; 1605 1606 while(1) { 1607 dent = gfs2_dirent_search(inode, name, gfs2_dirent_find_space, 1608 &bh); 1609 if (dent) { 1610 if (IS_ERR(dent)) 1611 return PTR_ERR(dent); 1612 dent = gfs2_init_dirent(inode, dent, name, bh); 1613 gfs2_inum_out(nip, dent); 1614 dent->de_type = cpu_to_be16(type); 1615 if (ip->i_di.di_flags & GFS2_DIF_EXHASH) { 1616 leaf = (struct gfs2_leaf *)bh->b_data; 1617 be16_add_cpu(&leaf->lf_entries, 1); 1618 } 1619 brelse(bh); 1620 error = gfs2_meta_inode_buffer(ip, &bh); 1621 if (error) 1622 break; 1623 gfs2_trans_add_bh(ip->i_gl, bh, 1); 1624 ip->i_di.di_entries++; 1625 ip->i_inode.i_mtime = ip->i_inode.i_ctime = CURRENT_TIME; 1626 gfs2_dinode_out(ip, bh->b_data); 1627 brelse(bh); 1628 error = 0; 1629 break; 1630 } 1631 if (!(ip->i_di.di_flags & GFS2_DIF_EXHASH)) { 1632 error = dir_make_exhash(inode); 1633 if (error) 1634 break; 1635 continue; 1636 } 1637 error = dir_split_leaf(inode, name); 1638 if (error == 0) 1639 continue; 1640 if (error < 0) 1641 break; 1642 if (ip->i_depth < GFS2_DIR_MAX_DEPTH) { 1643 error = dir_double_exhash(ip); 1644 if (error) 1645 break; 1646 error = dir_split_leaf(inode, name); 1647 if (error < 0) 1648 break; 1649 if (error == 0) 1650 continue; 1651 } 1652 error = dir_new_leaf(inode, name); 1653 if (!error) 1654 continue; 1655 error = -ENOSPC; 1656 break; 1657 } 1658 return error; 1659 } 1660 1661 1662 /** 1663 * gfs2_dir_del - Delete a directory entry 1664 * @dip: The GFS2 inode 1665 * @filename: The filename 1666 * 1667 * Returns: 0 on success, error code on failure 1668 */ 1669 1670 int gfs2_dir_del(struct gfs2_inode *dip, const struct qstr *name) 1671 { 1672 struct gfs2_dirent *dent, *prev = NULL; 1673 struct buffer_head *bh; 1674 int error; 1675 1676 /* Returns _either_ the entry (if its first in block) or the 1677 previous entry otherwise */ 1678 dent = gfs2_dirent_search(&dip->i_inode, name, gfs2_dirent_prev, &bh); 1679 if (!dent) { 1680 gfs2_consist_inode(dip); 1681 return -EIO; 1682 } 1683 if (IS_ERR(dent)) { 1684 gfs2_consist_inode(dip); 1685 return PTR_ERR(dent); 1686 } 1687 /* If not first in block, adjust pointers accordingly */ 1688 if (gfs2_dirent_find(dent, name, NULL) == 0) { 1689 prev = dent; 1690 dent = (struct gfs2_dirent *)((char *)dent + be16_to_cpu(prev->de_rec_len)); 1691 } 1692 1693 dirent_del(dip, bh, prev, dent); 1694 if (dip->i_di.di_flags & GFS2_DIF_EXHASH) { 1695 struct gfs2_leaf *leaf = (struct gfs2_leaf *)bh->b_data; 1696 u16 entries = be16_to_cpu(leaf->lf_entries); 1697 if (!entries) 1698 gfs2_consist_inode(dip); 1699 leaf->lf_entries = cpu_to_be16(--entries); 1700 } 1701 brelse(bh); 1702 1703 error = gfs2_meta_inode_buffer(dip, &bh); 1704 if (error) 1705 return error; 1706 1707 if (!dip->i_di.di_entries) 1708 gfs2_consist_inode(dip); 1709 gfs2_trans_add_bh(dip->i_gl, bh, 1); 1710 dip->i_di.di_entries--; 1711 dip->i_inode.i_mtime = dip->i_inode.i_ctime = CURRENT_TIME; 1712 gfs2_dinode_out(dip, bh->b_data); 1713 brelse(bh); 1714 mark_inode_dirty(&dip->i_inode); 1715 1716 return error; 1717 } 1718 1719 /** 1720 * gfs2_dir_mvino - Change inode number of directory entry 1721 * @dip: The GFS2 inode 1722 * @filename: 1723 * @new_inode: 1724 * 1725 * This routine changes the inode number of a directory entry. It's used 1726 * by rename to change ".." when a directory is moved. 1727 * Assumes a glock is held on dvp. 1728 * 1729 * Returns: errno 1730 */ 1731 1732 int gfs2_dir_mvino(struct gfs2_inode *dip, const struct qstr *filename, 1733 const struct gfs2_inode *nip, unsigned int new_type) 1734 { 1735 struct buffer_head *bh; 1736 struct gfs2_dirent *dent; 1737 int error; 1738 1739 dent = gfs2_dirent_search(&dip->i_inode, filename, gfs2_dirent_find, &bh); 1740 if (!dent) { 1741 gfs2_consist_inode(dip); 1742 return -EIO; 1743 } 1744 if (IS_ERR(dent)) 1745 return PTR_ERR(dent); 1746 1747 gfs2_trans_add_bh(dip->i_gl, bh, 1); 1748 gfs2_inum_out(nip, dent); 1749 dent->de_type = cpu_to_be16(new_type); 1750 1751 if (dip->i_di.di_flags & GFS2_DIF_EXHASH) { 1752 brelse(bh); 1753 error = gfs2_meta_inode_buffer(dip, &bh); 1754 if (error) 1755 return error; 1756 gfs2_trans_add_bh(dip->i_gl, bh, 1); 1757 } 1758 1759 dip->i_inode.i_mtime = dip->i_inode.i_ctime = CURRENT_TIME; 1760 gfs2_dinode_out(dip, bh->b_data); 1761 brelse(bh); 1762 return 0; 1763 } 1764 1765 /** 1766 * foreach_leaf - call a function for each leaf in a directory 1767 * @dip: the directory 1768 * @lc: the function to call for each each 1769 * @data: private data to pass to it 1770 * 1771 * Returns: errno 1772 */ 1773 1774 static int foreach_leaf(struct gfs2_inode *dip, leaf_call_t lc, void *data) 1775 { 1776 struct gfs2_sbd *sdp = GFS2_SB(&dip->i_inode); 1777 struct buffer_head *bh; 1778 struct gfs2_leaf *leaf; 1779 u32 hsize, len; 1780 u32 ht_offset, lp_offset, ht_offset_cur = -1; 1781 u32 index = 0; 1782 __be64 *lp; 1783 u64 leaf_no; 1784 int error = 0; 1785 1786 hsize = 1 << dip->i_depth; 1787 if (hsize * sizeof(u64) != dip->i_di.di_size) { 1788 gfs2_consist_inode(dip); 1789 return -EIO; 1790 } 1791 1792 lp = kmalloc(sdp->sd_hash_bsize, GFP_NOFS); 1793 if (!lp) 1794 return -ENOMEM; 1795 1796 while (index < hsize) { 1797 lp_offset = index & (sdp->sd_hash_ptrs - 1); 1798 ht_offset = index - lp_offset; 1799 1800 if (ht_offset_cur != ht_offset) { 1801 error = gfs2_dir_read_data(dip, (char *)lp, 1802 ht_offset * sizeof(__be64), 1803 sdp->sd_hash_bsize, 1); 1804 if (error != sdp->sd_hash_bsize) { 1805 if (error >= 0) 1806 error = -EIO; 1807 goto out; 1808 } 1809 ht_offset_cur = ht_offset; 1810 } 1811 1812 leaf_no = be64_to_cpu(lp[lp_offset]); 1813 if (leaf_no) { 1814 error = get_leaf(dip, leaf_no, &bh); 1815 if (error) 1816 goto out; 1817 leaf = (struct gfs2_leaf *)bh->b_data; 1818 len = 1 << (dip->i_depth - be16_to_cpu(leaf->lf_depth)); 1819 brelse(bh); 1820 1821 error = lc(dip, index, len, leaf_no, data); 1822 if (error) 1823 goto out; 1824 1825 index = (index & ~(len - 1)) + len; 1826 } else 1827 index++; 1828 } 1829 1830 if (index != hsize) { 1831 gfs2_consist_inode(dip); 1832 error = -EIO; 1833 } 1834 1835 out: 1836 kfree(lp); 1837 1838 return error; 1839 } 1840 1841 /** 1842 * leaf_dealloc - Deallocate a directory leaf 1843 * @dip: the directory 1844 * @index: the hash table offset in the directory 1845 * @len: the number of pointers to this leaf 1846 * @leaf_no: the leaf number 1847 * @data: not used 1848 * 1849 * Returns: errno 1850 */ 1851 1852 static int leaf_dealloc(struct gfs2_inode *dip, u32 index, u32 len, 1853 u64 leaf_no, void *data) 1854 { 1855 struct gfs2_sbd *sdp = GFS2_SB(&dip->i_inode); 1856 struct gfs2_leaf *tmp_leaf; 1857 struct gfs2_rgrp_list rlist; 1858 struct buffer_head *bh, *dibh; 1859 u64 blk, nblk; 1860 unsigned int rg_blocks = 0, l_blocks = 0; 1861 char *ht; 1862 unsigned int x, size = len * sizeof(u64); 1863 int error; 1864 1865 memset(&rlist, 0, sizeof(struct gfs2_rgrp_list)); 1866 1867 ht = kzalloc(size, GFP_NOFS); 1868 if (!ht) 1869 return -ENOMEM; 1870 1871 if (!gfs2_alloc_get(dip)) { 1872 error = -ENOMEM; 1873 goto out; 1874 } 1875 1876 error = gfs2_quota_hold(dip, NO_QUOTA_CHANGE, NO_QUOTA_CHANGE); 1877 if (error) 1878 goto out_put; 1879 1880 error = gfs2_rindex_hold(sdp, &dip->i_alloc->al_ri_gh); 1881 if (error) 1882 goto out_qs; 1883 1884 /* Count the number of leaves */ 1885 1886 for (blk = leaf_no; blk; blk = nblk) { 1887 error = get_leaf(dip, blk, &bh); 1888 if (error) 1889 goto out_rlist; 1890 tmp_leaf = (struct gfs2_leaf *)bh->b_data; 1891 nblk = be64_to_cpu(tmp_leaf->lf_next); 1892 brelse(bh); 1893 1894 gfs2_rlist_add(sdp, &rlist, blk); 1895 l_blocks++; 1896 } 1897 1898 gfs2_rlist_alloc(&rlist, LM_ST_EXCLUSIVE); 1899 1900 for (x = 0; x < rlist.rl_rgrps; x++) { 1901 struct gfs2_rgrpd *rgd; 1902 rgd = rlist.rl_ghs[x].gh_gl->gl_object; 1903 rg_blocks += rgd->rd_length; 1904 } 1905 1906 error = gfs2_glock_nq_m(rlist.rl_rgrps, rlist.rl_ghs); 1907 if (error) 1908 goto out_rlist; 1909 1910 error = gfs2_trans_begin(sdp, 1911 rg_blocks + (DIV_ROUND_UP(size, sdp->sd_jbsize) + 1) + 1912 RES_DINODE + RES_STATFS + RES_QUOTA, l_blocks); 1913 if (error) 1914 goto out_rg_gunlock; 1915 1916 for (blk = leaf_no; blk; blk = nblk) { 1917 error = get_leaf(dip, blk, &bh); 1918 if (error) 1919 goto out_end_trans; 1920 tmp_leaf = (struct gfs2_leaf *)bh->b_data; 1921 nblk = be64_to_cpu(tmp_leaf->lf_next); 1922 brelse(bh); 1923 1924 gfs2_free_meta(dip, blk, 1); 1925 gfs2_add_inode_blocks(&dip->i_inode, -1); 1926 } 1927 1928 error = gfs2_dir_write_data(dip, ht, index * sizeof(u64), size); 1929 if (error != size) { 1930 if (error >= 0) 1931 error = -EIO; 1932 goto out_end_trans; 1933 } 1934 1935 error = gfs2_meta_inode_buffer(dip, &dibh); 1936 if (error) 1937 goto out_end_trans; 1938 1939 gfs2_trans_add_bh(dip->i_gl, dibh, 1); 1940 gfs2_dinode_out(dip, dibh->b_data); 1941 brelse(dibh); 1942 1943 out_end_trans: 1944 gfs2_trans_end(sdp); 1945 out_rg_gunlock: 1946 gfs2_glock_dq_m(rlist.rl_rgrps, rlist.rl_ghs); 1947 out_rlist: 1948 gfs2_rlist_free(&rlist); 1949 gfs2_glock_dq_uninit(&dip->i_alloc->al_ri_gh); 1950 out_qs: 1951 gfs2_quota_unhold(dip); 1952 out_put: 1953 gfs2_alloc_put(dip); 1954 out: 1955 kfree(ht); 1956 return error; 1957 } 1958 1959 /** 1960 * gfs2_dir_exhash_dealloc - free all the leaf blocks in a directory 1961 * @dip: the directory 1962 * 1963 * Dealloc all on-disk directory leaves to FREEMETA state 1964 * Change on-disk inode type to "regular file" 1965 * 1966 * Returns: errno 1967 */ 1968 1969 int gfs2_dir_exhash_dealloc(struct gfs2_inode *dip) 1970 { 1971 struct gfs2_sbd *sdp = GFS2_SB(&dip->i_inode); 1972 struct buffer_head *bh; 1973 int error; 1974 1975 /* Dealloc on-disk leaves to FREEMETA state */ 1976 error = foreach_leaf(dip, leaf_dealloc, NULL); 1977 if (error) 1978 return error; 1979 1980 /* Make this a regular file in case we crash. 1981 (We don't want to free these blocks a second time.) */ 1982 1983 error = gfs2_trans_begin(sdp, RES_DINODE, 0); 1984 if (error) 1985 return error; 1986 1987 error = gfs2_meta_inode_buffer(dip, &bh); 1988 if (!error) { 1989 gfs2_trans_add_bh(dip->i_gl, bh, 1); 1990 ((struct gfs2_dinode *)bh->b_data)->di_mode = 1991 cpu_to_be32(S_IFREG); 1992 brelse(bh); 1993 } 1994 1995 gfs2_trans_end(sdp); 1996 1997 return error; 1998 } 1999 2000 /** 2001 * gfs2_diradd_alloc_required - find if adding entry will require an allocation 2002 * @ip: the file being written to 2003 * @filname: the filename that's going to be added 2004 * 2005 * Returns: 1 if alloc required, 0 if not, -ve on error 2006 */ 2007 2008 int gfs2_diradd_alloc_required(struct inode *inode, const struct qstr *name) 2009 { 2010 struct gfs2_dirent *dent; 2011 struct buffer_head *bh; 2012 2013 dent = gfs2_dirent_search(inode, name, gfs2_dirent_find_space, &bh); 2014 if (!dent) { 2015 return 1; 2016 } 2017 if (IS_ERR(dent)) 2018 return PTR_ERR(dent); 2019 brelse(bh); 2020 return 0; 2021 } 2022 2023