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_SEC; 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 163 if (!size) 164 return 0; 165 166 if (gfs2_is_stuffed(ip) && 167 offset + size <= sdp->sd_sb.sb_bsize - sizeof(struct gfs2_dinode)) 168 return gfs2_dir_write_stuffed(ip, buf, (unsigned int)offset, 169 size); 170 171 if (gfs2_assert_warn(sdp, gfs2_is_jdata(ip))) 172 return -EINVAL; 173 174 if (gfs2_is_stuffed(ip)) { 175 error = gfs2_unstuff_dinode(ip, NULL); 176 if (error) 177 return error; 178 } 179 180 lblock = offset; 181 o = do_div(lblock, sdp->sd_jbsize) + sizeof(struct gfs2_meta_header); 182 183 while (copied < size) { 184 unsigned int amount; 185 struct buffer_head *bh; 186 int new = 0; 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_SEC; 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_di.di_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_di.di_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 u64 bn = gfs2_alloc_meta(ip); 807 struct buffer_head *bh = gfs2_meta_new(ip->i_gl, bn); 808 struct gfs2_leaf *leaf; 809 struct gfs2_dirent *dent; 810 struct qstr name = { .name = "", .len = 0, .hash = 0 }; 811 if (!bh) 812 return NULL; 813 814 gfs2_trans_add_bh(ip->i_gl, bh, 1); 815 gfs2_metatype_set(bh, GFS2_METATYPE_LF, GFS2_FORMAT_LF); 816 leaf = (struct gfs2_leaf *)bh->b_data; 817 leaf->lf_depth = cpu_to_be16(depth); 818 leaf->lf_entries = 0; 819 leaf->lf_dirent_format = cpu_to_be32(GFS2_FORMAT_DE); 820 leaf->lf_next = 0; 821 memset(leaf->lf_reserved, 0, sizeof(leaf->lf_reserved)); 822 dent = (struct gfs2_dirent *)(leaf+1); 823 gfs2_qstr2dirent(&name, bh->b_size - sizeof(struct gfs2_leaf), dent); 824 *pbh = bh; 825 return leaf; 826 } 827 828 /** 829 * dir_make_exhash - Convert a stuffed directory into an ExHash directory 830 * @dip: The GFS2 inode 831 * 832 * Returns: 0 on success, error code otherwise 833 */ 834 835 static int dir_make_exhash(struct inode *inode) 836 { 837 struct gfs2_inode *dip = GFS2_I(inode); 838 struct gfs2_sbd *sdp = GFS2_SB(inode); 839 struct gfs2_dirent *dent; 840 struct qstr args; 841 struct buffer_head *bh, *dibh; 842 struct gfs2_leaf *leaf; 843 int y; 844 u32 x; 845 __be64 *lp; 846 u64 bn; 847 int error; 848 849 error = gfs2_meta_inode_buffer(dip, &dibh); 850 if (error) 851 return error; 852 853 /* Turn over a new leaf */ 854 855 leaf = new_leaf(inode, &bh, 0); 856 if (!leaf) 857 return -ENOSPC; 858 bn = bh->b_blocknr; 859 860 gfs2_assert(sdp, dip->i_di.di_entries < (1 << 16)); 861 leaf->lf_entries = cpu_to_be16(dip->i_di.di_entries); 862 863 /* Copy dirents */ 864 865 gfs2_buffer_copy_tail(bh, sizeof(struct gfs2_leaf), dibh, 866 sizeof(struct gfs2_dinode)); 867 868 /* Find last entry */ 869 870 x = 0; 871 args.len = bh->b_size - sizeof(struct gfs2_dinode) + 872 sizeof(struct gfs2_leaf); 873 args.name = bh->b_data; 874 dent = gfs2_dirent_scan(&dip->i_inode, bh->b_data, bh->b_size, 875 gfs2_dirent_last, &args, NULL); 876 if (!dent) { 877 brelse(bh); 878 brelse(dibh); 879 return -EIO; 880 } 881 if (IS_ERR(dent)) { 882 brelse(bh); 883 brelse(dibh); 884 return PTR_ERR(dent); 885 } 886 887 /* Adjust the last dirent's record length 888 (Remember that dent still points to the last entry.) */ 889 890 dent->de_rec_len = cpu_to_be16(be16_to_cpu(dent->de_rec_len) + 891 sizeof(struct gfs2_dinode) - 892 sizeof(struct gfs2_leaf)); 893 894 brelse(bh); 895 896 /* We're done with the new leaf block, now setup the new 897 hash table. */ 898 899 gfs2_trans_add_bh(dip->i_gl, dibh, 1); 900 gfs2_buffer_clear_tail(dibh, sizeof(struct gfs2_dinode)); 901 902 lp = (__be64 *)(dibh->b_data + sizeof(struct gfs2_dinode)); 903 904 for (x = sdp->sd_hash_ptrs; x--; lp++) 905 *lp = cpu_to_be64(bn); 906 907 dip->i_di.di_size = sdp->sd_sb.sb_bsize / 2; 908 dip->i_di.di_blocks++; 909 gfs2_set_inode_blocks(&dip->i_inode); 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_di.di_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_di.di_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_di.di_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_di.di_depth - be16_to_cpu(oleaf->lf_depth)); 971 half_len = len >> 1; 972 if (!half_len) { 973 printk(KERN_WARNING "di_depth %u lf_depth %u index %u\n", dip->i_di.di_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_di.di_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 nleaf->lf_entries = cpu_to_be16(be16_to_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 oleaf->lf_entries = cpu_to_be16(be16_to_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 dip->i_di.di_blocks++; 1047 gfs2_set_inode_blocks(&dip->i_inode); 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_di.di_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_KERNEL | __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_di.di_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_di.di_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_di.di_depth); 1380 1381 lp = kmalloc(sdp->sd_hash_bsize, GFP_KERNEL); 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_di.di_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_KERNEL); 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_num.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 int gfs2_dir_search(struct inode *dir, const struct qstr *name, 1492 struct gfs2_inum_host *inum, unsigned int *type) 1493 { 1494 struct buffer_head *bh; 1495 struct gfs2_dirent *dent; 1496 1497 dent = gfs2_dirent_search(dir, name, gfs2_dirent_find, &bh); 1498 if (dent) { 1499 if (IS_ERR(dent)) 1500 return PTR_ERR(dent); 1501 if (inum) 1502 gfs2_inum_in(inum, (char *)&dent->de_inum); 1503 if (type) 1504 *type = be16_to_cpu(dent->de_type); 1505 brelse(bh); 1506 return 0; 1507 } 1508 return -ENOENT; 1509 } 1510 1511 static int dir_new_leaf(struct inode *inode, const struct qstr *name) 1512 { 1513 struct buffer_head *bh, *obh; 1514 struct gfs2_inode *ip = GFS2_I(inode); 1515 struct gfs2_leaf *leaf, *oleaf; 1516 int error; 1517 u32 index; 1518 u64 bn; 1519 1520 index = name->hash >> (32 - ip->i_di.di_depth); 1521 error = get_first_leaf(ip, index, &obh); 1522 if (error) 1523 return error; 1524 do { 1525 oleaf = (struct gfs2_leaf *)obh->b_data; 1526 bn = be64_to_cpu(oleaf->lf_next); 1527 if (!bn) 1528 break; 1529 brelse(obh); 1530 error = get_leaf(ip, bn, &obh); 1531 if (error) 1532 return error; 1533 } while(1); 1534 1535 gfs2_trans_add_bh(ip->i_gl, obh, 1); 1536 1537 leaf = new_leaf(inode, &bh, be16_to_cpu(oleaf->lf_depth)); 1538 if (!leaf) { 1539 brelse(obh); 1540 return -ENOSPC; 1541 } 1542 oleaf->lf_next = cpu_to_be64(bh->b_blocknr); 1543 brelse(bh); 1544 brelse(obh); 1545 1546 error = gfs2_meta_inode_buffer(ip, &bh); 1547 if (error) 1548 return error; 1549 gfs2_trans_add_bh(ip->i_gl, bh, 1); 1550 ip->i_di.di_blocks++; 1551 gfs2_set_inode_blocks(&ip->i_inode); 1552 gfs2_dinode_out(ip, bh->b_data); 1553 brelse(bh); 1554 return 0; 1555 } 1556 1557 /** 1558 * gfs2_dir_add - Add new filename into directory 1559 * @dip: The GFS2 inode 1560 * @filename: The new name 1561 * @inode: The inode number of the entry 1562 * @type: The type of the entry 1563 * 1564 * Returns: 0 on success, error code on failure 1565 */ 1566 1567 int gfs2_dir_add(struct inode *inode, const struct qstr *name, 1568 const struct gfs2_inum_host *inum, unsigned type) 1569 { 1570 struct gfs2_inode *ip = GFS2_I(inode); 1571 struct buffer_head *bh; 1572 struct gfs2_dirent *dent; 1573 struct gfs2_leaf *leaf; 1574 int error; 1575 1576 while(1) { 1577 dent = gfs2_dirent_search(inode, name, gfs2_dirent_find_space, 1578 &bh); 1579 if (dent) { 1580 if (IS_ERR(dent)) 1581 return PTR_ERR(dent); 1582 dent = gfs2_init_dirent(inode, dent, name, bh); 1583 gfs2_inum_out(inum, (char *)&dent->de_inum); 1584 dent->de_type = cpu_to_be16(type); 1585 if (ip->i_di.di_flags & GFS2_DIF_EXHASH) { 1586 leaf = (struct gfs2_leaf *)bh->b_data; 1587 leaf->lf_entries = cpu_to_be16(be16_to_cpu(leaf->lf_entries) + 1); 1588 } 1589 brelse(bh); 1590 error = gfs2_meta_inode_buffer(ip, &bh); 1591 if (error) 1592 break; 1593 gfs2_trans_add_bh(ip->i_gl, bh, 1); 1594 ip->i_di.di_entries++; 1595 ip->i_inode.i_mtime = ip->i_inode.i_ctime = CURRENT_TIME_SEC; 1596 gfs2_dinode_out(ip, bh->b_data); 1597 brelse(bh); 1598 error = 0; 1599 break; 1600 } 1601 if (!(ip->i_di.di_flags & GFS2_DIF_EXHASH)) { 1602 error = dir_make_exhash(inode); 1603 if (error) 1604 break; 1605 continue; 1606 } 1607 error = dir_split_leaf(inode, name); 1608 if (error == 0) 1609 continue; 1610 if (error < 0) 1611 break; 1612 if (ip->i_di.di_depth < GFS2_DIR_MAX_DEPTH) { 1613 error = dir_double_exhash(ip); 1614 if (error) 1615 break; 1616 error = dir_split_leaf(inode, name); 1617 if (error < 0) 1618 break; 1619 if (error == 0) 1620 continue; 1621 } 1622 error = dir_new_leaf(inode, name); 1623 if (!error) 1624 continue; 1625 error = -ENOSPC; 1626 break; 1627 } 1628 return error; 1629 } 1630 1631 1632 /** 1633 * gfs2_dir_del - Delete a directory entry 1634 * @dip: The GFS2 inode 1635 * @filename: The filename 1636 * 1637 * Returns: 0 on success, error code on failure 1638 */ 1639 1640 int gfs2_dir_del(struct gfs2_inode *dip, const struct qstr *name) 1641 { 1642 struct gfs2_dirent *dent, *prev = NULL; 1643 struct buffer_head *bh; 1644 int error; 1645 1646 /* Returns _either_ the entry (if its first in block) or the 1647 previous entry otherwise */ 1648 dent = gfs2_dirent_search(&dip->i_inode, name, gfs2_dirent_prev, &bh); 1649 if (!dent) { 1650 gfs2_consist_inode(dip); 1651 return -EIO; 1652 } 1653 if (IS_ERR(dent)) { 1654 gfs2_consist_inode(dip); 1655 return PTR_ERR(dent); 1656 } 1657 /* If not first in block, adjust pointers accordingly */ 1658 if (gfs2_dirent_find(dent, name, NULL) == 0) { 1659 prev = dent; 1660 dent = (struct gfs2_dirent *)((char *)dent + be16_to_cpu(prev->de_rec_len)); 1661 } 1662 1663 dirent_del(dip, bh, prev, dent); 1664 if (dip->i_di.di_flags & GFS2_DIF_EXHASH) { 1665 struct gfs2_leaf *leaf = (struct gfs2_leaf *)bh->b_data; 1666 u16 entries = be16_to_cpu(leaf->lf_entries); 1667 if (!entries) 1668 gfs2_consist_inode(dip); 1669 leaf->lf_entries = cpu_to_be16(--entries); 1670 } 1671 brelse(bh); 1672 1673 error = gfs2_meta_inode_buffer(dip, &bh); 1674 if (error) 1675 return error; 1676 1677 if (!dip->i_di.di_entries) 1678 gfs2_consist_inode(dip); 1679 gfs2_trans_add_bh(dip->i_gl, bh, 1); 1680 dip->i_di.di_entries--; 1681 dip->i_inode.i_mtime = dip->i_inode.i_ctime = CURRENT_TIME_SEC; 1682 gfs2_dinode_out(dip, bh->b_data); 1683 brelse(bh); 1684 mark_inode_dirty(&dip->i_inode); 1685 1686 return error; 1687 } 1688 1689 /** 1690 * gfs2_dir_mvino - Change inode number of directory entry 1691 * @dip: The GFS2 inode 1692 * @filename: 1693 * @new_inode: 1694 * 1695 * This routine changes the inode number of a directory entry. It's used 1696 * by rename to change ".." when a directory is moved. 1697 * Assumes a glock is held on dvp. 1698 * 1699 * Returns: errno 1700 */ 1701 1702 int gfs2_dir_mvino(struct gfs2_inode *dip, const struct qstr *filename, 1703 struct gfs2_inum_host *inum, unsigned int new_type) 1704 { 1705 struct buffer_head *bh; 1706 struct gfs2_dirent *dent; 1707 int error; 1708 1709 dent = gfs2_dirent_search(&dip->i_inode, filename, gfs2_dirent_find, &bh); 1710 if (!dent) { 1711 gfs2_consist_inode(dip); 1712 return -EIO; 1713 } 1714 if (IS_ERR(dent)) 1715 return PTR_ERR(dent); 1716 1717 gfs2_trans_add_bh(dip->i_gl, bh, 1); 1718 gfs2_inum_out(inum, (char *)&dent->de_inum); 1719 dent->de_type = cpu_to_be16(new_type); 1720 1721 if (dip->i_di.di_flags & GFS2_DIF_EXHASH) { 1722 brelse(bh); 1723 error = gfs2_meta_inode_buffer(dip, &bh); 1724 if (error) 1725 return error; 1726 gfs2_trans_add_bh(dip->i_gl, bh, 1); 1727 } 1728 1729 dip->i_inode.i_mtime = dip->i_inode.i_ctime = CURRENT_TIME_SEC; 1730 gfs2_dinode_out(dip, bh->b_data); 1731 brelse(bh); 1732 return 0; 1733 } 1734 1735 /** 1736 * foreach_leaf - call a function for each leaf in a directory 1737 * @dip: the directory 1738 * @lc: the function to call for each each 1739 * @data: private data to pass to it 1740 * 1741 * Returns: errno 1742 */ 1743 1744 static int foreach_leaf(struct gfs2_inode *dip, leaf_call_t lc, void *data) 1745 { 1746 struct gfs2_sbd *sdp = GFS2_SB(&dip->i_inode); 1747 struct buffer_head *bh; 1748 struct gfs2_leaf *leaf; 1749 u32 hsize, len; 1750 u32 ht_offset, lp_offset, ht_offset_cur = -1; 1751 u32 index = 0; 1752 __be64 *lp; 1753 u64 leaf_no; 1754 int error = 0; 1755 1756 hsize = 1 << dip->i_di.di_depth; 1757 if (hsize * sizeof(u64) != dip->i_di.di_size) { 1758 gfs2_consist_inode(dip); 1759 return -EIO; 1760 } 1761 1762 lp = kmalloc(sdp->sd_hash_bsize, GFP_KERNEL); 1763 if (!lp) 1764 return -ENOMEM; 1765 1766 while (index < hsize) { 1767 lp_offset = index & (sdp->sd_hash_ptrs - 1); 1768 ht_offset = index - lp_offset; 1769 1770 if (ht_offset_cur != ht_offset) { 1771 error = gfs2_dir_read_data(dip, (char *)lp, 1772 ht_offset * sizeof(__be64), 1773 sdp->sd_hash_bsize, 1); 1774 if (error != sdp->sd_hash_bsize) { 1775 if (error >= 0) 1776 error = -EIO; 1777 goto out; 1778 } 1779 ht_offset_cur = ht_offset; 1780 } 1781 1782 leaf_no = be64_to_cpu(lp[lp_offset]); 1783 if (leaf_no) { 1784 error = get_leaf(dip, leaf_no, &bh); 1785 if (error) 1786 goto out; 1787 leaf = (struct gfs2_leaf *)bh->b_data; 1788 len = 1 << (dip->i_di.di_depth - be16_to_cpu(leaf->lf_depth)); 1789 brelse(bh); 1790 1791 error = lc(dip, index, len, leaf_no, data); 1792 if (error) 1793 goto out; 1794 1795 index = (index & ~(len - 1)) + len; 1796 } else 1797 index++; 1798 } 1799 1800 if (index != hsize) { 1801 gfs2_consist_inode(dip); 1802 error = -EIO; 1803 } 1804 1805 out: 1806 kfree(lp); 1807 1808 return error; 1809 } 1810 1811 /** 1812 * leaf_dealloc - Deallocate a directory leaf 1813 * @dip: the directory 1814 * @index: the hash table offset in the directory 1815 * @len: the number of pointers to this leaf 1816 * @leaf_no: the leaf number 1817 * @data: not used 1818 * 1819 * Returns: errno 1820 */ 1821 1822 static int leaf_dealloc(struct gfs2_inode *dip, u32 index, u32 len, 1823 u64 leaf_no, void *data) 1824 { 1825 struct gfs2_sbd *sdp = GFS2_SB(&dip->i_inode); 1826 struct gfs2_leaf *tmp_leaf; 1827 struct gfs2_rgrp_list rlist; 1828 struct buffer_head *bh, *dibh; 1829 u64 blk, nblk; 1830 unsigned int rg_blocks = 0, l_blocks = 0; 1831 char *ht; 1832 unsigned int x, size = len * sizeof(u64); 1833 int error; 1834 1835 memset(&rlist, 0, sizeof(struct gfs2_rgrp_list)); 1836 1837 ht = kzalloc(size, GFP_KERNEL); 1838 if (!ht) 1839 return -ENOMEM; 1840 1841 gfs2_alloc_get(dip); 1842 1843 error = gfs2_quota_hold(dip, NO_QUOTA_CHANGE, NO_QUOTA_CHANGE); 1844 if (error) 1845 goto out; 1846 1847 error = gfs2_rindex_hold(sdp, &dip->i_alloc.al_ri_gh); 1848 if (error) 1849 goto out_qs; 1850 1851 /* Count the number of leaves */ 1852 1853 for (blk = leaf_no; blk; blk = nblk) { 1854 error = get_leaf(dip, blk, &bh); 1855 if (error) 1856 goto out_rlist; 1857 tmp_leaf = (struct gfs2_leaf *)bh->b_data; 1858 nblk = be64_to_cpu(tmp_leaf->lf_next); 1859 brelse(bh); 1860 1861 gfs2_rlist_add(sdp, &rlist, blk); 1862 l_blocks++; 1863 } 1864 1865 gfs2_rlist_alloc(&rlist, LM_ST_EXCLUSIVE, 0); 1866 1867 for (x = 0; x < rlist.rl_rgrps; x++) { 1868 struct gfs2_rgrpd *rgd; 1869 rgd = rlist.rl_ghs[x].gh_gl->gl_object; 1870 rg_blocks += rgd->rd_ri.ri_length; 1871 } 1872 1873 error = gfs2_glock_nq_m(rlist.rl_rgrps, rlist.rl_ghs); 1874 if (error) 1875 goto out_rlist; 1876 1877 error = gfs2_trans_begin(sdp, 1878 rg_blocks + (DIV_ROUND_UP(size, sdp->sd_jbsize) + 1) + 1879 RES_DINODE + RES_STATFS + RES_QUOTA, l_blocks); 1880 if (error) 1881 goto out_rg_gunlock; 1882 1883 for (blk = leaf_no; blk; blk = nblk) { 1884 error = get_leaf(dip, blk, &bh); 1885 if (error) 1886 goto out_end_trans; 1887 tmp_leaf = (struct gfs2_leaf *)bh->b_data; 1888 nblk = be64_to_cpu(tmp_leaf->lf_next); 1889 brelse(bh); 1890 1891 gfs2_free_meta(dip, blk, 1); 1892 1893 if (!dip->i_di.di_blocks) 1894 gfs2_consist_inode(dip); 1895 dip->i_di.di_blocks--; 1896 gfs2_set_inode_blocks(&dip->i_inode); 1897 } 1898 1899 error = gfs2_dir_write_data(dip, ht, index * sizeof(u64), size); 1900 if (error != size) { 1901 if (error >= 0) 1902 error = -EIO; 1903 goto out_end_trans; 1904 } 1905 1906 error = gfs2_meta_inode_buffer(dip, &dibh); 1907 if (error) 1908 goto out_end_trans; 1909 1910 gfs2_trans_add_bh(dip->i_gl, dibh, 1); 1911 gfs2_dinode_out(dip, dibh->b_data); 1912 brelse(dibh); 1913 1914 out_end_trans: 1915 gfs2_trans_end(sdp); 1916 out_rg_gunlock: 1917 gfs2_glock_dq_m(rlist.rl_rgrps, rlist.rl_ghs); 1918 out_rlist: 1919 gfs2_rlist_free(&rlist); 1920 gfs2_glock_dq_uninit(&dip->i_alloc.al_ri_gh); 1921 out_qs: 1922 gfs2_quota_unhold(dip); 1923 out: 1924 gfs2_alloc_put(dip); 1925 kfree(ht); 1926 return error; 1927 } 1928 1929 /** 1930 * gfs2_dir_exhash_dealloc - free all the leaf blocks in a directory 1931 * @dip: the directory 1932 * 1933 * Dealloc all on-disk directory leaves to FREEMETA state 1934 * Change on-disk inode type to "regular file" 1935 * 1936 * Returns: errno 1937 */ 1938 1939 int gfs2_dir_exhash_dealloc(struct gfs2_inode *dip) 1940 { 1941 struct gfs2_sbd *sdp = GFS2_SB(&dip->i_inode); 1942 struct buffer_head *bh; 1943 int error; 1944 1945 /* Dealloc on-disk leaves to FREEMETA state */ 1946 error = foreach_leaf(dip, leaf_dealloc, NULL); 1947 if (error) 1948 return error; 1949 1950 /* Make this a regular file in case we crash. 1951 (We don't want to free these blocks a second time.) */ 1952 1953 error = gfs2_trans_begin(sdp, RES_DINODE, 0); 1954 if (error) 1955 return error; 1956 1957 error = gfs2_meta_inode_buffer(dip, &bh); 1958 if (!error) { 1959 gfs2_trans_add_bh(dip->i_gl, bh, 1); 1960 ((struct gfs2_dinode *)bh->b_data)->di_mode = 1961 cpu_to_be32(S_IFREG); 1962 brelse(bh); 1963 } 1964 1965 gfs2_trans_end(sdp); 1966 1967 return error; 1968 } 1969 1970 /** 1971 * gfs2_diradd_alloc_required - find if adding entry will require an allocation 1972 * @ip: the file being written to 1973 * @filname: the filename that's going to be added 1974 * 1975 * Returns: 1 if alloc required, 0 if not, -ve on error 1976 */ 1977 1978 int gfs2_diradd_alloc_required(struct inode *inode, const struct qstr *name) 1979 { 1980 struct gfs2_dirent *dent; 1981 struct buffer_head *bh; 1982 1983 dent = gfs2_dirent_search(inode, name, gfs2_dirent_find_space, &bh); 1984 if (!dent) { 1985 return 1; 1986 } 1987 if (IS_ERR(dent)) 1988 return PTR_ERR(dent); 1989 brelse(bh); 1990 return 0; 1991 } 1992 1993