1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Copyright (c) 2000-2003,2005 Silicon Graphics, Inc. 4 * Copyright (c) 2013 Red Hat, Inc. 5 * All Rights Reserved. 6 */ 7 #include "xfs.h" 8 #include "xfs_fs.h" 9 #include "xfs_shared.h" 10 #include "xfs_format.h" 11 #include "xfs_log_format.h" 12 #include "xfs_trans_resv.h" 13 #include "xfs_mount.h" 14 #include "xfs_inode.h" 15 #include "xfs_bmap.h" 16 #include "xfs_dir2.h" 17 #include "xfs_dir2_priv.h" 18 #include "xfs_error.h" 19 #include "xfs_trace.h" 20 #include "xfs_trans.h" 21 #include "xfs_buf_item.h" 22 23 /* 24 * Local function declarations. 25 */ 26 static int xfs_dir2_leaf_lookup_int(xfs_da_args_t *args, struct xfs_buf **lbpp, 27 int *indexp, struct xfs_buf **dbpp, 28 struct xfs_dir3_icleaf_hdr *leafhdr); 29 static void xfs_dir3_leaf_log_bests(struct xfs_da_args *args, 30 struct xfs_buf *bp, int first, int last); 31 static void xfs_dir3_leaf_log_tail(struct xfs_da_args *args, 32 struct xfs_buf *bp); 33 34 void 35 xfs_dir2_leaf_hdr_from_disk( 36 struct xfs_mount *mp, 37 struct xfs_dir3_icleaf_hdr *to, 38 struct xfs_dir2_leaf *from) 39 { 40 if (xfs_sb_version_hascrc(&mp->m_sb)) { 41 struct xfs_dir3_leaf *from3 = (struct xfs_dir3_leaf *)from; 42 43 to->forw = be32_to_cpu(from3->hdr.info.hdr.forw); 44 to->back = be32_to_cpu(from3->hdr.info.hdr.back); 45 to->magic = be16_to_cpu(from3->hdr.info.hdr.magic); 46 to->count = be16_to_cpu(from3->hdr.count); 47 to->stale = be16_to_cpu(from3->hdr.stale); 48 to->ents = from3->__ents; 49 50 ASSERT(to->magic == XFS_DIR3_LEAF1_MAGIC || 51 to->magic == XFS_DIR3_LEAFN_MAGIC); 52 } else { 53 to->forw = be32_to_cpu(from->hdr.info.forw); 54 to->back = be32_to_cpu(from->hdr.info.back); 55 to->magic = be16_to_cpu(from->hdr.info.magic); 56 to->count = be16_to_cpu(from->hdr.count); 57 to->stale = be16_to_cpu(from->hdr.stale); 58 to->ents = from->__ents; 59 60 ASSERT(to->magic == XFS_DIR2_LEAF1_MAGIC || 61 to->magic == XFS_DIR2_LEAFN_MAGIC); 62 } 63 } 64 65 void 66 xfs_dir2_leaf_hdr_to_disk( 67 struct xfs_mount *mp, 68 struct xfs_dir2_leaf *to, 69 struct xfs_dir3_icleaf_hdr *from) 70 { 71 if (xfs_sb_version_hascrc(&mp->m_sb)) { 72 struct xfs_dir3_leaf *to3 = (struct xfs_dir3_leaf *)to; 73 74 ASSERT(from->magic == XFS_DIR3_LEAF1_MAGIC || 75 from->magic == XFS_DIR3_LEAFN_MAGIC); 76 77 to3->hdr.info.hdr.forw = cpu_to_be32(from->forw); 78 to3->hdr.info.hdr.back = cpu_to_be32(from->back); 79 to3->hdr.info.hdr.magic = cpu_to_be16(from->magic); 80 to3->hdr.count = cpu_to_be16(from->count); 81 to3->hdr.stale = cpu_to_be16(from->stale); 82 } else { 83 ASSERT(from->magic == XFS_DIR2_LEAF1_MAGIC || 84 from->magic == XFS_DIR2_LEAFN_MAGIC); 85 86 to->hdr.info.forw = cpu_to_be32(from->forw); 87 to->hdr.info.back = cpu_to_be32(from->back); 88 to->hdr.info.magic = cpu_to_be16(from->magic); 89 to->hdr.count = cpu_to_be16(from->count); 90 to->hdr.stale = cpu_to_be16(from->stale); 91 } 92 } 93 94 /* 95 * Check the internal consistency of a leaf1 block. 96 * Pop an assert if something is wrong. 97 */ 98 #ifdef DEBUG 99 static xfs_failaddr_t 100 xfs_dir3_leaf1_check( 101 struct xfs_inode *dp, 102 struct xfs_buf *bp) 103 { 104 struct xfs_dir2_leaf *leaf = bp->b_addr; 105 struct xfs_dir3_icleaf_hdr leafhdr; 106 107 xfs_dir2_leaf_hdr_from_disk(dp->i_mount, &leafhdr, leaf); 108 109 if (leafhdr.magic == XFS_DIR3_LEAF1_MAGIC) { 110 struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr; 111 if (be64_to_cpu(leaf3->info.blkno) != bp->b_bn) 112 return __this_address; 113 } else if (leafhdr.magic != XFS_DIR2_LEAF1_MAGIC) 114 return __this_address; 115 116 return xfs_dir3_leaf_check_int(dp->i_mount, &leafhdr, leaf); 117 } 118 119 static inline void 120 xfs_dir3_leaf_check( 121 struct xfs_inode *dp, 122 struct xfs_buf *bp) 123 { 124 xfs_failaddr_t fa; 125 126 fa = xfs_dir3_leaf1_check(dp, bp); 127 if (!fa) 128 return; 129 xfs_corruption_error(__func__, XFS_ERRLEVEL_LOW, dp->i_mount, 130 bp->b_addr, BBTOB(bp->b_length), __FILE__, __LINE__, 131 fa); 132 ASSERT(0); 133 } 134 #else 135 #define xfs_dir3_leaf_check(dp, bp) 136 #endif 137 138 xfs_failaddr_t 139 xfs_dir3_leaf_check_int( 140 struct xfs_mount *mp, 141 struct xfs_dir3_icleaf_hdr *hdr, 142 struct xfs_dir2_leaf *leaf) 143 { 144 xfs_dir2_leaf_tail_t *ltp; 145 int stale; 146 int i; 147 struct xfs_dir3_icleaf_hdr leafhdr; 148 struct xfs_da_geometry *geo = mp->m_dir_geo; 149 150 if (!hdr) { 151 xfs_dir2_leaf_hdr_from_disk(mp, &leafhdr, leaf); 152 hdr = &leafhdr; 153 } 154 155 ltp = xfs_dir2_leaf_tail_p(geo, leaf); 156 157 /* 158 * XXX (dgc): This value is not restrictive enough. 159 * Should factor in the size of the bests table as well. 160 * We can deduce a value for that from di_size. 161 */ 162 if (hdr->count > geo->leaf_max_ents) 163 return __this_address; 164 165 /* Leaves and bests don't overlap in leaf format. */ 166 if ((hdr->magic == XFS_DIR2_LEAF1_MAGIC || 167 hdr->magic == XFS_DIR3_LEAF1_MAGIC) && 168 (char *)&hdr->ents[hdr->count] > (char *)xfs_dir2_leaf_bests_p(ltp)) 169 return __this_address; 170 171 /* Check hash value order, count stale entries. */ 172 for (i = stale = 0; i < hdr->count; i++) { 173 if (i + 1 < hdr->count) { 174 if (be32_to_cpu(hdr->ents[i].hashval) > 175 be32_to_cpu(hdr->ents[i + 1].hashval)) 176 return __this_address; 177 } 178 if (hdr->ents[i].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) 179 stale++; 180 } 181 if (hdr->stale != stale) 182 return __this_address; 183 return NULL; 184 } 185 186 /* 187 * We verify the magic numbers before decoding the leaf header so that on debug 188 * kernels we don't get assertion failures in xfs_dir3_leaf_hdr_from_disk() due 189 * to incorrect magic numbers. 190 */ 191 static xfs_failaddr_t 192 xfs_dir3_leaf_verify( 193 struct xfs_buf *bp) 194 { 195 struct xfs_mount *mp = bp->b_mount; 196 struct xfs_dir2_leaf *leaf = bp->b_addr; 197 xfs_failaddr_t fa; 198 199 fa = xfs_da3_blkinfo_verify(bp, bp->b_addr); 200 if (fa) 201 return fa; 202 203 return xfs_dir3_leaf_check_int(mp, NULL, leaf); 204 } 205 206 static void 207 xfs_dir3_leaf_read_verify( 208 struct xfs_buf *bp) 209 { 210 struct xfs_mount *mp = bp->b_mount; 211 xfs_failaddr_t fa; 212 213 if (xfs_sb_version_hascrc(&mp->m_sb) && 214 !xfs_buf_verify_cksum(bp, XFS_DIR3_LEAF_CRC_OFF)) 215 xfs_verifier_error(bp, -EFSBADCRC, __this_address); 216 else { 217 fa = xfs_dir3_leaf_verify(bp); 218 if (fa) 219 xfs_verifier_error(bp, -EFSCORRUPTED, fa); 220 } 221 } 222 223 static void 224 xfs_dir3_leaf_write_verify( 225 struct xfs_buf *bp) 226 { 227 struct xfs_mount *mp = bp->b_mount; 228 struct xfs_buf_log_item *bip = bp->b_log_item; 229 struct xfs_dir3_leaf_hdr *hdr3 = bp->b_addr; 230 xfs_failaddr_t fa; 231 232 fa = xfs_dir3_leaf_verify(bp); 233 if (fa) { 234 xfs_verifier_error(bp, -EFSCORRUPTED, fa); 235 return; 236 } 237 238 if (!xfs_sb_version_hascrc(&mp->m_sb)) 239 return; 240 241 if (bip) 242 hdr3->info.lsn = cpu_to_be64(bip->bli_item.li_lsn); 243 244 xfs_buf_update_cksum(bp, XFS_DIR3_LEAF_CRC_OFF); 245 } 246 247 const struct xfs_buf_ops xfs_dir3_leaf1_buf_ops = { 248 .name = "xfs_dir3_leaf1", 249 .magic16 = { cpu_to_be16(XFS_DIR2_LEAF1_MAGIC), 250 cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) }, 251 .verify_read = xfs_dir3_leaf_read_verify, 252 .verify_write = xfs_dir3_leaf_write_verify, 253 .verify_struct = xfs_dir3_leaf_verify, 254 }; 255 256 const struct xfs_buf_ops xfs_dir3_leafn_buf_ops = { 257 .name = "xfs_dir3_leafn", 258 .magic16 = { cpu_to_be16(XFS_DIR2_LEAFN_MAGIC), 259 cpu_to_be16(XFS_DIR3_LEAFN_MAGIC) }, 260 .verify_read = xfs_dir3_leaf_read_verify, 261 .verify_write = xfs_dir3_leaf_write_verify, 262 .verify_struct = xfs_dir3_leaf_verify, 263 }; 264 265 int 266 xfs_dir3_leaf_read( 267 struct xfs_trans *tp, 268 struct xfs_inode *dp, 269 xfs_dablk_t fbno, 270 xfs_daddr_t mappedbno, 271 struct xfs_buf **bpp) 272 { 273 int err; 274 275 err = xfs_da_read_buf(tp, dp, fbno, mappedbno, bpp, 276 XFS_DATA_FORK, &xfs_dir3_leaf1_buf_ops); 277 if (!err && tp && *bpp) 278 xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_LEAF1_BUF); 279 return err; 280 } 281 282 int 283 xfs_dir3_leafn_read( 284 struct xfs_trans *tp, 285 struct xfs_inode *dp, 286 xfs_dablk_t fbno, 287 xfs_daddr_t mappedbno, 288 struct xfs_buf **bpp) 289 { 290 int err; 291 292 err = xfs_da_read_buf(tp, dp, fbno, mappedbno, bpp, 293 XFS_DATA_FORK, &xfs_dir3_leafn_buf_ops); 294 if (!err && tp && *bpp) 295 xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_LEAFN_BUF); 296 return err; 297 } 298 299 /* 300 * Initialize a new leaf block, leaf1 or leafn magic accepted. 301 */ 302 static void 303 xfs_dir3_leaf_init( 304 struct xfs_mount *mp, 305 struct xfs_trans *tp, 306 struct xfs_buf *bp, 307 xfs_ino_t owner, 308 uint16_t type) 309 { 310 struct xfs_dir2_leaf *leaf = bp->b_addr; 311 312 ASSERT(type == XFS_DIR2_LEAF1_MAGIC || type == XFS_DIR2_LEAFN_MAGIC); 313 314 if (xfs_sb_version_hascrc(&mp->m_sb)) { 315 struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr; 316 317 memset(leaf3, 0, sizeof(*leaf3)); 318 319 leaf3->info.hdr.magic = (type == XFS_DIR2_LEAF1_MAGIC) 320 ? cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) 321 : cpu_to_be16(XFS_DIR3_LEAFN_MAGIC); 322 leaf3->info.blkno = cpu_to_be64(bp->b_bn); 323 leaf3->info.owner = cpu_to_be64(owner); 324 uuid_copy(&leaf3->info.uuid, &mp->m_sb.sb_meta_uuid); 325 } else { 326 memset(leaf, 0, sizeof(*leaf)); 327 leaf->hdr.info.magic = cpu_to_be16(type); 328 } 329 330 /* 331 * If it's a leaf-format directory initialize the tail. 332 * Caller is responsible for initialising the bests table. 333 */ 334 if (type == XFS_DIR2_LEAF1_MAGIC) { 335 struct xfs_dir2_leaf_tail *ltp; 336 337 ltp = xfs_dir2_leaf_tail_p(mp->m_dir_geo, leaf); 338 ltp->bestcount = 0; 339 bp->b_ops = &xfs_dir3_leaf1_buf_ops; 340 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAF1_BUF); 341 } else { 342 bp->b_ops = &xfs_dir3_leafn_buf_ops; 343 xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAFN_BUF); 344 } 345 } 346 347 int 348 xfs_dir3_leaf_get_buf( 349 xfs_da_args_t *args, 350 xfs_dir2_db_t bno, 351 struct xfs_buf **bpp, 352 uint16_t magic) 353 { 354 struct xfs_inode *dp = args->dp; 355 struct xfs_trans *tp = args->trans; 356 struct xfs_mount *mp = dp->i_mount; 357 struct xfs_buf *bp; 358 int error; 359 360 ASSERT(magic == XFS_DIR2_LEAF1_MAGIC || magic == XFS_DIR2_LEAFN_MAGIC); 361 ASSERT(bno >= xfs_dir2_byte_to_db(args->geo, XFS_DIR2_LEAF_OFFSET) && 362 bno < xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET)); 363 364 error = xfs_da_get_buf(tp, dp, xfs_dir2_db_to_da(args->geo, bno), 365 -1, &bp, XFS_DATA_FORK); 366 if (error) 367 return error; 368 369 xfs_dir3_leaf_init(mp, tp, bp, dp->i_ino, magic); 370 xfs_dir3_leaf_log_header(args, bp); 371 if (magic == XFS_DIR2_LEAF1_MAGIC) 372 xfs_dir3_leaf_log_tail(args, bp); 373 *bpp = bp; 374 return 0; 375 } 376 377 /* 378 * Convert a block form directory to a leaf form directory. 379 */ 380 int /* error */ 381 xfs_dir2_block_to_leaf( 382 xfs_da_args_t *args, /* operation arguments */ 383 struct xfs_buf *dbp) /* input block's buffer */ 384 { 385 __be16 *bestsp; /* leaf's bestsp entries */ 386 xfs_dablk_t blkno; /* leaf block's bno */ 387 xfs_dir2_data_hdr_t *hdr; /* block header */ 388 xfs_dir2_leaf_entry_t *blp; /* block's leaf entries */ 389 xfs_dir2_block_tail_t *btp; /* block's tail */ 390 xfs_inode_t *dp; /* incore directory inode */ 391 int error; /* error return code */ 392 struct xfs_buf *lbp; /* leaf block's buffer */ 393 xfs_dir2_db_t ldb; /* leaf block's bno */ 394 xfs_dir2_leaf_t *leaf; /* leaf structure */ 395 xfs_dir2_leaf_tail_t *ltp; /* leaf's tail */ 396 int needlog; /* need to log block header */ 397 int needscan; /* need to rescan bestfree */ 398 xfs_trans_t *tp; /* transaction pointer */ 399 struct xfs_dir2_data_free *bf; 400 struct xfs_dir3_icleaf_hdr leafhdr; 401 402 trace_xfs_dir2_block_to_leaf(args); 403 404 dp = args->dp; 405 tp = args->trans; 406 /* 407 * Add the leaf block to the inode. 408 * This interface will only put blocks in the leaf/node range. 409 * Since that's empty now, we'll get the root (block 0 in range). 410 */ 411 if ((error = xfs_da_grow_inode(args, &blkno))) { 412 return error; 413 } 414 ldb = xfs_dir2_da_to_db(args->geo, blkno); 415 ASSERT(ldb == xfs_dir2_byte_to_db(args->geo, XFS_DIR2_LEAF_OFFSET)); 416 /* 417 * Initialize the leaf block, get a buffer for it. 418 */ 419 error = xfs_dir3_leaf_get_buf(args, ldb, &lbp, XFS_DIR2_LEAF1_MAGIC); 420 if (error) 421 return error; 422 423 leaf = lbp->b_addr; 424 hdr = dbp->b_addr; 425 xfs_dir3_data_check(dp, dbp); 426 btp = xfs_dir2_block_tail_p(args->geo, hdr); 427 blp = xfs_dir2_block_leaf_p(btp); 428 bf = dp->d_ops->data_bestfree_p(hdr); 429 430 /* 431 * Set the counts in the leaf header. 432 */ 433 xfs_dir2_leaf_hdr_from_disk(dp->i_mount, &leafhdr, leaf); 434 leafhdr.count = be32_to_cpu(btp->count); 435 leafhdr.stale = be32_to_cpu(btp->stale); 436 xfs_dir2_leaf_hdr_to_disk(dp->i_mount, leaf, &leafhdr); 437 xfs_dir3_leaf_log_header(args, lbp); 438 439 /* 440 * Could compact these but I think we always do the conversion 441 * after squeezing out stale entries. 442 */ 443 memcpy(leafhdr.ents, blp, 444 be32_to_cpu(btp->count) * sizeof(struct xfs_dir2_leaf_entry)); 445 xfs_dir3_leaf_log_ents(args, &leafhdr, lbp, 0, leafhdr.count - 1); 446 needscan = 0; 447 needlog = 1; 448 /* 449 * Make the space formerly occupied by the leaf entries and block 450 * tail be free. 451 */ 452 xfs_dir2_data_make_free(args, dbp, 453 (xfs_dir2_data_aoff_t)((char *)blp - (char *)hdr), 454 (xfs_dir2_data_aoff_t)((char *)hdr + args->geo->blksize - 455 (char *)blp), 456 &needlog, &needscan); 457 /* 458 * Fix up the block header, make it a data block. 459 */ 460 dbp->b_ops = &xfs_dir3_data_buf_ops; 461 xfs_trans_buf_set_type(tp, dbp, XFS_BLFT_DIR_DATA_BUF); 462 if (hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC)) 463 hdr->magic = cpu_to_be32(XFS_DIR2_DATA_MAGIC); 464 else 465 hdr->magic = cpu_to_be32(XFS_DIR3_DATA_MAGIC); 466 467 if (needscan) 468 xfs_dir2_data_freescan(dp, hdr, &needlog); 469 /* 470 * Set up leaf tail and bests table. 471 */ 472 ltp = xfs_dir2_leaf_tail_p(args->geo, leaf); 473 ltp->bestcount = cpu_to_be32(1); 474 bestsp = xfs_dir2_leaf_bests_p(ltp); 475 bestsp[0] = bf[0].length; 476 /* 477 * Log the data header and leaf bests table. 478 */ 479 if (needlog) 480 xfs_dir2_data_log_header(args, dbp); 481 xfs_dir3_leaf_check(dp, lbp); 482 xfs_dir3_data_check(dp, dbp); 483 xfs_dir3_leaf_log_bests(args, lbp, 0, 0); 484 return 0; 485 } 486 487 STATIC void 488 xfs_dir3_leaf_find_stale( 489 struct xfs_dir3_icleaf_hdr *leafhdr, 490 struct xfs_dir2_leaf_entry *ents, 491 int index, 492 int *lowstale, 493 int *highstale) 494 { 495 /* 496 * Find the first stale entry before our index, if any. 497 */ 498 for (*lowstale = index - 1; *lowstale >= 0; --*lowstale) { 499 if (ents[*lowstale].address == 500 cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) 501 break; 502 } 503 504 /* 505 * Find the first stale entry at or after our index, if any. 506 * Stop if the result would require moving more entries than using 507 * lowstale. 508 */ 509 for (*highstale = index; *highstale < leafhdr->count; ++*highstale) { 510 if (ents[*highstale].address == 511 cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) 512 break; 513 if (*lowstale >= 0 && index - *lowstale <= *highstale - index) 514 break; 515 } 516 } 517 518 struct xfs_dir2_leaf_entry * 519 xfs_dir3_leaf_find_entry( 520 struct xfs_dir3_icleaf_hdr *leafhdr, 521 struct xfs_dir2_leaf_entry *ents, 522 int index, /* leaf table position */ 523 int compact, /* need to compact leaves */ 524 int lowstale, /* index of prev stale leaf */ 525 int highstale, /* index of next stale leaf */ 526 int *lfloglow, /* low leaf logging index */ 527 int *lfloghigh) /* high leaf logging index */ 528 { 529 if (!leafhdr->stale) { 530 xfs_dir2_leaf_entry_t *lep; /* leaf entry table pointer */ 531 532 /* 533 * Now we need to make room to insert the leaf entry. 534 * 535 * If there are no stale entries, just insert a hole at index. 536 */ 537 lep = &ents[index]; 538 if (index < leafhdr->count) 539 memmove(lep + 1, lep, 540 (leafhdr->count - index) * sizeof(*lep)); 541 542 /* 543 * Record low and high logging indices for the leaf. 544 */ 545 *lfloglow = index; 546 *lfloghigh = leafhdr->count++; 547 return lep; 548 } 549 550 /* 551 * There are stale entries. 552 * 553 * We will use one of them for the new entry. It's probably not at 554 * the right location, so we'll have to shift some up or down first. 555 * 556 * If we didn't compact before, we need to find the nearest stale 557 * entries before and after our insertion point. 558 */ 559 if (compact == 0) 560 xfs_dir3_leaf_find_stale(leafhdr, ents, index, 561 &lowstale, &highstale); 562 563 /* 564 * If the low one is better, use it. 565 */ 566 if (lowstale >= 0 && 567 (highstale == leafhdr->count || 568 index - lowstale - 1 < highstale - index)) { 569 ASSERT(index - lowstale - 1 >= 0); 570 ASSERT(ents[lowstale].address == 571 cpu_to_be32(XFS_DIR2_NULL_DATAPTR)); 572 573 /* 574 * Copy entries up to cover the stale entry and make room 575 * for the new entry. 576 */ 577 if (index - lowstale - 1 > 0) { 578 memmove(&ents[lowstale], &ents[lowstale + 1], 579 (index - lowstale - 1) * 580 sizeof(xfs_dir2_leaf_entry_t)); 581 } 582 *lfloglow = min(lowstale, *lfloglow); 583 *lfloghigh = max(index - 1, *lfloghigh); 584 leafhdr->stale--; 585 return &ents[index - 1]; 586 } 587 588 /* 589 * The high one is better, so use that one. 590 */ 591 ASSERT(highstale - index >= 0); 592 ASSERT(ents[highstale].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR)); 593 594 /* 595 * Copy entries down to cover the stale entry and make room for the 596 * new entry. 597 */ 598 if (highstale - index > 0) { 599 memmove(&ents[index + 1], &ents[index], 600 (highstale - index) * sizeof(xfs_dir2_leaf_entry_t)); 601 } 602 *lfloglow = min(index, *lfloglow); 603 *lfloghigh = max(highstale, *lfloghigh); 604 leafhdr->stale--; 605 return &ents[index]; 606 } 607 608 /* 609 * Add an entry to a leaf form directory. 610 */ 611 int /* error */ 612 xfs_dir2_leaf_addname( 613 struct xfs_da_args *args) /* operation arguments */ 614 { 615 struct xfs_dir3_icleaf_hdr leafhdr; 616 struct xfs_trans *tp = args->trans; 617 __be16 *bestsp; /* freespace table in leaf */ 618 __be16 *tagp; /* end of data entry */ 619 struct xfs_buf *dbp; /* data block buffer */ 620 struct xfs_buf *lbp; /* leaf's buffer */ 621 struct xfs_dir2_leaf *leaf; /* leaf structure */ 622 struct xfs_inode *dp = args->dp; /* incore directory inode */ 623 struct xfs_dir2_data_hdr *hdr; /* data block header */ 624 struct xfs_dir2_data_entry *dep; /* data block entry */ 625 struct xfs_dir2_leaf_entry *lep; /* leaf entry table pointer */ 626 struct xfs_dir2_leaf_entry *ents; 627 struct xfs_dir2_data_unused *dup; /* data unused entry */ 628 struct xfs_dir2_leaf_tail *ltp; /* leaf tail pointer */ 629 struct xfs_dir2_data_free *bf; /* bestfree table */ 630 int compact; /* need to compact leaves */ 631 int error; /* error return value */ 632 int grown; /* allocated new data block */ 633 int highstale = 0; /* index of next stale leaf */ 634 int i; /* temporary, index */ 635 int index; /* leaf table position */ 636 int length; /* length of new entry */ 637 int lfloglow; /* low leaf logging index */ 638 int lfloghigh; /* high leaf logging index */ 639 int lowstale = 0; /* index of prev stale leaf */ 640 int needbytes; /* leaf block bytes needed */ 641 int needlog; /* need to log data header */ 642 int needscan; /* need to rescan data free */ 643 xfs_dir2_db_t use_block; /* data block number */ 644 645 trace_xfs_dir2_leaf_addname(args); 646 647 error = xfs_dir3_leaf_read(tp, dp, args->geo->leafblk, -1, &lbp); 648 if (error) 649 return error; 650 651 /* 652 * Look up the entry by hash value and name. 653 * We know it's not there, our caller has already done a lookup. 654 * So the index is of the entry to insert in front of. 655 * But if there are dup hash values the index is of the first of those. 656 */ 657 index = xfs_dir2_leaf_search_hash(args, lbp); 658 leaf = lbp->b_addr; 659 ltp = xfs_dir2_leaf_tail_p(args->geo, leaf); 660 xfs_dir2_leaf_hdr_from_disk(dp->i_mount, &leafhdr, leaf); 661 ents = leafhdr.ents; 662 bestsp = xfs_dir2_leaf_bests_p(ltp); 663 length = dp->d_ops->data_entsize(args->namelen); 664 665 /* 666 * See if there are any entries with the same hash value 667 * and space in their block for the new entry. 668 * This is good because it puts multiple same-hash value entries 669 * in a data block, improving the lookup of those entries. 670 */ 671 for (use_block = -1, lep = &ents[index]; 672 index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval; 673 index++, lep++) { 674 if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR) 675 continue; 676 i = xfs_dir2_dataptr_to_db(args->geo, be32_to_cpu(lep->address)); 677 ASSERT(i < be32_to_cpu(ltp->bestcount)); 678 ASSERT(bestsp[i] != cpu_to_be16(NULLDATAOFF)); 679 if (be16_to_cpu(bestsp[i]) >= length) { 680 use_block = i; 681 break; 682 } 683 } 684 /* 685 * Didn't find a block yet, linear search all the data blocks. 686 */ 687 if (use_block == -1) { 688 for (i = 0; i < be32_to_cpu(ltp->bestcount); i++) { 689 /* 690 * Remember a block we see that's missing. 691 */ 692 if (bestsp[i] == cpu_to_be16(NULLDATAOFF) && 693 use_block == -1) 694 use_block = i; 695 else if (be16_to_cpu(bestsp[i]) >= length) { 696 use_block = i; 697 break; 698 } 699 } 700 } 701 /* 702 * How many bytes do we need in the leaf block? 703 */ 704 needbytes = 0; 705 if (!leafhdr.stale) 706 needbytes += sizeof(xfs_dir2_leaf_entry_t); 707 if (use_block == -1) 708 needbytes += sizeof(xfs_dir2_data_off_t); 709 710 /* 711 * Now kill use_block if it refers to a missing block, so we 712 * can use it as an indication of allocation needed. 713 */ 714 if (use_block != -1 && bestsp[use_block] == cpu_to_be16(NULLDATAOFF)) 715 use_block = -1; 716 /* 717 * If we don't have enough free bytes but we can make enough 718 * by compacting out stale entries, we'll do that. 719 */ 720 if ((char *)bestsp - (char *)&ents[leafhdr.count] < needbytes && 721 leafhdr.stale > 1) 722 compact = 1; 723 724 /* 725 * Otherwise if we don't have enough free bytes we need to 726 * convert to node form. 727 */ 728 else if ((char *)bestsp - (char *)&ents[leafhdr.count] < needbytes) { 729 /* 730 * Just checking or no space reservation, give up. 731 */ 732 if ((args->op_flags & XFS_DA_OP_JUSTCHECK) || 733 args->total == 0) { 734 xfs_trans_brelse(tp, lbp); 735 return -ENOSPC; 736 } 737 /* 738 * Convert to node form. 739 */ 740 error = xfs_dir2_leaf_to_node(args, lbp); 741 if (error) 742 return error; 743 /* 744 * Then add the new entry. 745 */ 746 return xfs_dir2_node_addname(args); 747 } 748 /* 749 * Otherwise it will fit without compaction. 750 */ 751 else 752 compact = 0; 753 /* 754 * If just checking, then it will fit unless we needed to allocate 755 * a new data block. 756 */ 757 if (args->op_flags & XFS_DA_OP_JUSTCHECK) { 758 xfs_trans_brelse(tp, lbp); 759 return use_block == -1 ? -ENOSPC : 0; 760 } 761 /* 762 * If no allocations are allowed, return now before we've 763 * changed anything. 764 */ 765 if (args->total == 0 && use_block == -1) { 766 xfs_trans_brelse(tp, lbp); 767 return -ENOSPC; 768 } 769 /* 770 * Need to compact the leaf entries, removing stale ones. 771 * Leave one stale entry behind - the one closest to our 772 * insertion index - and we'll shift that one to our insertion 773 * point later. 774 */ 775 if (compact) { 776 xfs_dir3_leaf_compact_x1(&leafhdr, ents, &index, &lowstale, 777 &highstale, &lfloglow, &lfloghigh); 778 } 779 /* 780 * There are stale entries, so we'll need log-low and log-high 781 * impossibly bad values later. 782 */ 783 else if (leafhdr.stale) { 784 lfloglow = leafhdr.count; 785 lfloghigh = -1; 786 } 787 /* 788 * If there was no data block space found, we need to allocate 789 * a new one. 790 */ 791 if (use_block == -1) { 792 /* 793 * Add the new data block. 794 */ 795 if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_DATA_SPACE, 796 &use_block))) { 797 xfs_trans_brelse(tp, lbp); 798 return error; 799 } 800 /* 801 * Initialize the block. 802 */ 803 if ((error = xfs_dir3_data_init(args, use_block, &dbp))) { 804 xfs_trans_brelse(tp, lbp); 805 return error; 806 } 807 /* 808 * If we're adding a new data block on the end we need to 809 * extend the bests table. Copy it up one entry. 810 */ 811 if (use_block >= be32_to_cpu(ltp->bestcount)) { 812 bestsp--; 813 memmove(&bestsp[0], &bestsp[1], 814 be32_to_cpu(ltp->bestcount) * sizeof(bestsp[0])); 815 be32_add_cpu(<p->bestcount, 1); 816 xfs_dir3_leaf_log_tail(args, lbp); 817 xfs_dir3_leaf_log_bests(args, lbp, 0, 818 be32_to_cpu(ltp->bestcount) - 1); 819 } 820 /* 821 * If we're filling in a previously empty block just log it. 822 */ 823 else 824 xfs_dir3_leaf_log_bests(args, lbp, use_block, use_block); 825 hdr = dbp->b_addr; 826 bf = dp->d_ops->data_bestfree_p(hdr); 827 bestsp[use_block] = bf[0].length; 828 grown = 1; 829 } else { 830 /* 831 * Already had space in some data block. 832 * Just read that one in. 833 */ 834 error = xfs_dir3_data_read(tp, dp, 835 xfs_dir2_db_to_da(args->geo, use_block), 836 -1, &dbp); 837 if (error) { 838 xfs_trans_brelse(tp, lbp); 839 return error; 840 } 841 hdr = dbp->b_addr; 842 bf = dp->d_ops->data_bestfree_p(hdr); 843 grown = 0; 844 } 845 /* 846 * Point to the biggest freespace in our data block. 847 */ 848 dup = (xfs_dir2_data_unused_t *) 849 ((char *)hdr + be16_to_cpu(bf[0].offset)); 850 needscan = needlog = 0; 851 /* 852 * Mark the initial part of our freespace in use for the new entry. 853 */ 854 error = xfs_dir2_data_use_free(args, dbp, dup, 855 (xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr), 856 length, &needlog, &needscan); 857 if (error) { 858 xfs_trans_brelse(tp, lbp); 859 return error; 860 } 861 /* 862 * Initialize our new entry (at last). 863 */ 864 dep = (xfs_dir2_data_entry_t *)dup; 865 dep->inumber = cpu_to_be64(args->inumber); 866 dep->namelen = args->namelen; 867 memcpy(dep->name, args->name, dep->namelen); 868 dp->d_ops->data_put_ftype(dep, args->filetype); 869 tagp = dp->d_ops->data_entry_tag_p(dep); 870 *tagp = cpu_to_be16((char *)dep - (char *)hdr); 871 /* 872 * Need to scan fix up the bestfree table. 873 */ 874 if (needscan) 875 xfs_dir2_data_freescan(dp, hdr, &needlog); 876 /* 877 * Need to log the data block's header. 878 */ 879 if (needlog) 880 xfs_dir2_data_log_header(args, dbp); 881 xfs_dir2_data_log_entry(args, dbp, dep); 882 /* 883 * If the bests table needs to be changed, do it. 884 * Log the change unless we've already done that. 885 */ 886 if (be16_to_cpu(bestsp[use_block]) != be16_to_cpu(bf[0].length)) { 887 bestsp[use_block] = bf[0].length; 888 if (!grown) 889 xfs_dir3_leaf_log_bests(args, lbp, use_block, use_block); 890 } 891 892 lep = xfs_dir3_leaf_find_entry(&leafhdr, ents, index, compact, lowstale, 893 highstale, &lfloglow, &lfloghigh); 894 895 /* 896 * Fill in the new leaf entry. 897 */ 898 lep->hashval = cpu_to_be32(args->hashval); 899 lep->address = cpu_to_be32( 900 xfs_dir2_db_off_to_dataptr(args->geo, use_block, 901 be16_to_cpu(*tagp))); 902 /* 903 * Log the leaf fields and give up the buffers. 904 */ 905 xfs_dir2_leaf_hdr_to_disk(dp->i_mount, leaf, &leafhdr); 906 xfs_dir3_leaf_log_header(args, lbp); 907 xfs_dir3_leaf_log_ents(args, &leafhdr, lbp, lfloglow, lfloghigh); 908 xfs_dir3_leaf_check(dp, lbp); 909 xfs_dir3_data_check(dp, dbp); 910 return 0; 911 } 912 913 /* 914 * Compact out any stale entries in the leaf. 915 * Log the header and changed leaf entries, if any. 916 */ 917 void 918 xfs_dir3_leaf_compact( 919 xfs_da_args_t *args, /* operation arguments */ 920 struct xfs_dir3_icleaf_hdr *leafhdr, 921 struct xfs_buf *bp) /* leaf buffer */ 922 { 923 int from; /* source leaf index */ 924 xfs_dir2_leaf_t *leaf; /* leaf structure */ 925 int loglow; /* first leaf entry to log */ 926 int to; /* target leaf index */ 927 struct xfs_inode *dp = args->dp; 928 929 leaf = bp->b_addr; 930 if (!leafhdr->stale) 931 return; 932 933 /* 934 * Compress out the stale entries in place. 935 */ 936 for (from = to = 0, loglow = -1; from < leafhdr->count; from++) { 937 if (leafhdr->ents[from].address == 938 cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) 939 continue; 940 /* 941 * Only actually copy the entries that are different. 942 */ 943 if (from > to) { 944 if (loglow == -1) 945 loglow = to; 946 leafhdr->ents[to] = leafhdr->ents[from]; 947 } 948 to++; 949 } 950 /* 951 * Update and log the header, log the leaf entries. 952 */ 953 ASSERT(leafhdr->stale == from - to); 954 leafhdr->count -= leafhdr->stale; 955 leafhdr->stale = 0; 956 957 xfs_dir2_leaf_hdr_to_disk(dp->i_mount, leaf, leafhdr); 958 xfs_dir3_leaf_log_header(args, bp); 959 if (loglow != -1) 960 xfs_dir3_leaf_log_ents(args, leafhdr, bp, loglow, to - 1); 961 } 962 963 /* 964 * Compact the leaf entries, removing stale ones. 965 * Leave one stale entry behind - the one closest to our 966 * insertion index - and the caller will shift that one to our insertion 967 * point later. 968 * Return new insertion index, where the remaining stale entry is, 969 * and leaf logging indices. 970 */ 971 void 972 xfs_dir3_leaf_compact_x1( 973 struct xfs_dir3_icleaf_hdr *leafhdr, 974 struct xfs_dir2_leaf_entry *ents, 975 int *indexp, /* insertion index */ 976 int *lowstalep, /* out: stale entry before us */ 977 int *highstalep, /* out: stale entry after us */ 978 int *lowlogp, /* out: low log index */ 979 int *highlogp) /* out: high log index */ 980 { 981 int from; /* source copy index */ 982 int highstale; /* stale entry at/after index */ 983 int index; /* insertion index */ 984 int keepstale; /* source index of kept stale */ 985 int lowstale; /* stale entry before index */ 986 int newindex=0; /* new insertion index */ 987 int to; /* destination copy index */ 988 989 ASSERT(leafhdr->stale > 1); 990 index = *indexp; 991 992 xfs_dir3_leaf_find_stale(leafhdr, ents, index, &lowstale, &highstale); 993 994 /* 995 * Pick the better of lowstale and highstale. 996 */ 997 if (lowstale >= 0 && 998 (highstale == leafhdr->count || 999 index - lowstale <= highstale - index)) 1000 keepstale = lowstale; 1001 else 1002 keepstale = highstale; 1003 /* 1004 * Copy the entries in place, removing all the stale entries 1005 * except keepstale. 1006 */ 1007 for (from = to = 0; from < leafhdr->count; from++) { 1008 /* 1009 * Notice the new value of index. 1010 */ 1011 if (index == from) 1012 newindex = to; 1013 if (from != keepstale && 1014 ents[from].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) { 1015 if (from == to) 1016 *lowlogp = to; 1017 continue; 1018 } 1019 /* 1020 * Record the new keepstale value for the insertion. 1021 */ 1022 if (from == keepstale) 1023 lowstale = highstale = to; 1024 /* 1025 * Copy only the entries that have moved. 1026 */ 1027 if (from > to) 1028 ents[to] = ents[from]; 1029 to++; 1030 } 1031 ASSERT(from > to); 1032 /* 1033 * If the insertion point was past the last entry, 1034 * set the new insertion point accordingly. 1035 */ 1036 if (index == from) 1037 newindex = to; 1038 *indexp = newindex; 1039 /* 1040 * Adjust the leaf header values. 1041 */ 1042 leafhdr->count -= from - to; 1043 leafhdr->stale = 1; 1044 /* 1045 * Remember the low/high stale value only in the "right" 1046 * direction. 1047 */ 1048 if (lowstale >= newindex) 1049 lowstale = -1; 1050 else 1051 highstale = leafhdr->count; 1052 *highlogp = leafhdr->count - 1; 1053 *lowstalep = lowstale; 1054 *highstalep = highstale; 1055 } 1056 1057 /* 1058 * Log the bests entries indicated from a leaf1 block. 1059 */ 1060 static void 1061 xfs_dir3_leaf_log_bests( 1062 struct xfs_da_args *args, 1063 struct xfs_buf *bp, /* leaf buffer */ 1064 int first, /* first entry to log */ 1065 int last) /* last entry to log */ 1066 { 1067 __be16 *firstb; /* pointer to first entry */ 1068 __be16 *lastb; /* pointer to last entry */ 1069 struct xfs_dir2_leaf *leaf = bp->b_addr; 1070 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */ 1071 1072 ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) || 1073 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC)); 1074 1075 ltp = xfs_dir2_leaf_tail_p(args->geo, leaf); 1076 firstb = xfs_dir2_leaf_bests_p(ltp) + first; 1077 lastb = xfs_dir2_leaf_bests_p(ltp) + last; 1078 xfs_trans_log_buf(args->trans, bp, 1079 (uint)((char *)firstb - (char *)leaf), 1080 (uint)((char *)lastb - (char *)leaf + sizeof(*lastb) - 1)); 1081 } 1082 1083 /* 1084 * Log the leaf entries indicated from a leaf1 or leafn block. 1085 */ 1086 void 1087 xfs_dir3_leaf_log_ents( 1088 struct xfs_da_args *args, 1089 struct xfs_dir3_icleaf_hdr *hdr, 1090 struct xfs_buf *bp, 1091 int first, 1092 int last) 1093 { 1094 xfs_dir2_leaf_entry_t *firstlep; /* pointer to first entry */ 1095 xfs_dir2_leaf_entry_t *lastlep; /* pointer to last entry */ 1096 struct xfs_dir2_leaf *leaf = bp->b_addr; 1097 1098 ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) || 1099 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) || 1100 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) || 1101 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)); 1102 1103 firstlep = &hdr->ents[first]; 1104 lastlep = &hdr->ents[last]; 1105 xfs_trans_log_buf(args->trans, bp, 1106 (uint)((char *)firstlep - (char *)leaf), 1107 (uint)((char *)lastlep - (char *)leaf + sizeof(*lastlep) - 1)); 1108 } 1109 1110 /* 1111 * Log the header of the leaf1 or leafn block. 1112 */ 1113 void 1114 xfs_dir3_leaf_log_header( 1115 struct xfs_da_args *args, 1116 struct xfs_buf *bp) 1117 { 1118 struct xfs_dir2_leaf *leaf = bp->b_addr; 1119 1120 ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) || 1121 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) || 1122 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) || 1123 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)); 1124 1125 xfs_trans_log_buf(args->trans, bp, 1126 (uint)((char *)&leaf->hdr - (char *)leaf), 1127 args->geo->leaf_hdr_size - 1); 1128 } 1129 1130 /* 1131 * Log the tail of the leaf1 block. 1132 */ 1133 STATIC void 1134 xfs_dir3_leaf_log_tail( 1135 struct xfs_da_args *args, 1136 struct xfs_buf *bp) 1137 { 1138 struct xfs_dir2_leaf *leaf = bp->b_addr; 1139 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */ 1140 1141 ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) || 1142 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) || 1143 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) || 1144 leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)); 1145 1146 ltp = xfs_dir2_leaf_tail_p(args->geo, leaf); 1147 xfs_trans_log_buf(args->trans, bp, (uint)((char *)ltp - (char *)leaf), 1148 (uint)(args->geo->blksize - 1)); 1149 } 1150 1151 /* 1152 * Look up the entry referred to by args in the leaf format directory. 1153 * Most of the work is done by the xfs_dir2_leaf_lookup_int routine which 1154 * is also used by the node-format code. 1155 */ 1156 int 1157 xfs_dir2_leaf_lookup( 1158 xfs_da_args_t *args) /* operation arguments */ 1159 { 1160 struct xfs_buf *dbp; /* data block buffer */ 1161 xfs_dir2_data_entry_t *dep; /* data block entry */ 1162 xfs_inode_t *dp; /* incore directory inode */ 1163 int error; /* error return code */ 1164 int index; /* found entry index */ 1165 struct xfs_buf *lbp; /* leaf buffer */ 1166 xfs_dir2_leaf_entry_t *lep; /* leaf entry */ 1167 xfs_trans_t *tp; /* transaction pointer */ 1168 struct xfs_dir3_icleaf_hdr leafhdr; 1169 1170 trace_xfs_dir2_leaf_lookup(args); 1171 1172 /* 1173 * Look up name in the leaf block, returning both buffers and index. 1174 */ 1175 error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp, &leafhdr); 1176 if (error) 1177 return error; 1178 1179 tp = args->trans; 1180 dp = args->dp; 1181 xfs_dir3_leaf_check(dp, lbp); 1182 1183 /* 1184 * Get to the leaf entry and contained data entry address. 1185 */ 1186 lep = &leafhdr.ents[index]; 1187 1188 /* 1189 * Point to the data entry. 1190 */ 1191 dep = (xfs_dir2_data_entry_t *) 1192 ((char *)dbp->b_addr + 1193 xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address))); 1194 /* 1195 * Return the found inode number & CI name if appropriate 1196 */ 1197 args->inumber = be64_to_cpu(dep->inumber); 1198 args->filetype = dp->d_ops->data_get_ftype(dep); 1199 error = xfs_dir_cilookup_result(args, dep->name, dep->namelen); 1200 xfs_trans_brelse(tp, dbp); 1201 xfs_trans_brelse(tp, lbp); 1202 return error; 1203 } 1204 1205 /* 1206 * Look up name/hash in the leaf block. 1207 * Fill in indexp with the found index, and dbpp with the data buffer. 1208 * If not found dbpp will be NULL, and ENOENT comes back. 1209 * lbpp will always be filled in with the leaf buffer unless there's an error. 1210 */ 1211 static int /* error */ 1212 xfs_dir2_leaf_lookup_int( 1213 xfs_da_args_t *args, /* operation arguments */ 1214 struct xfs_buf **lbpp, /* out: leaf buffer */ 1215 int *indexp, /* out: index in leaf block */ 1216 struct xfs_buf **dbpp, /* out: data buffer */ 1217 struct xfs_dir3_icleaf_hdr *leafhdr) 1218 { 1219 xfs_dir2_db_t curdb = -1; /* current data block number */ 1220 struct xfs_buf *dbp = NULL; /* data buffer */ 1221 xfs_dir2_data_entry_t *dep; /* data entry */ 1222 xfs_inode_t *dp; /* incore directory inode */ 1223 int error; /* error return code */ 1224 int index; /* index in leaf block */ 1225 struct xfs_buf *lbp; /* leaf buffer */ 1226 xfs_dir2_leaf_entry_t *lep; /* leaf entry */ 1227 xfs_dir2_leaf_t *leaf; /* leaf structure */ 1228 xfs_mount_t *mp; /* filesystem mount point */ 1229 xfs_dir2_db_t newdb; /* new data block number */ 1230 xfs_trans_t *tp; /* transaction pointer */ 1231 xfs_dir2_db_t cidb = -1; /* case match data block no. */ 1232 enum xfs_dacmp cmp; /* name compare result */ 1233 1234 dp = args->dp; 1235 tp = args->trans; 1236 mp = dp->i_mount; 1237 1238 error = xfs_dir3_leaf_read(tp, dp, args->geo->leafblk, -1, &lbp); 1239 if (error) 1240 return error; 1241 1242 *lbpp = lbp; 1243 leaf = lbp->b_addr; 1244 xfs_dir3_leaf_check(dp, lbp); 1245 xfs_dir2_leaf_hdr_from_disk(mp, leafhdr, leaf); 1246 1247 /* 1248 * Look for the first leaf entry with our hash value. 1249 */ 1250 index = xfs_dir2_leaf_search_hash(args, lbp); 1251 /* 1252 * Loop over all the entries with the right hash value 1253 * looking to match the name. 1254 */ 1255 for (lep = &leafhdr->ents[index]; 1256 index < leafhdr->count && 1257 be32_to_cpu(lep->hashval) == args->hashval; 1258 lep++, index++) { 1259 /* 1260 * Skip over stale leaf entries. 1261 */ 1262 if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR) 1263 continue; 1264 /* 1265 * Get the new data block number. 1266 */ 1267 newdb = xfs_dir2_dataptr_to_db(args->geo, 1268 be32_to_cpu(lep->address)); 1269 /* 1270 * If it's not the same as the old data block number, 1271 * need to pitch the old one and read the new one. 1272 */ 1273 if (newdb != curdb) { 1274 if (dbp) 1275 xfs_trans_brelse(tp, dbp); 1276 error = xfs_dir3_data_read(tp, dp, 1277 xfs_dir2_db_to_da(args->geo, newdb), 1278 -1, &dbp); 1279 if (error) { 1280 xfs_trans_brelse(tp, lbp); 1281 return error; 1282 } 1283 curdb = newdb; 1284 } 1285 /* 1286 * Point to the data entry. 1287 */ 1288 dep = (xfs_dir2_data_entry_t *)((char *)dbp->b_addr + 1289 xfs_dir2_dataptr_to_off(args->geo, 1290 be32_to_cpu(lep->address))); 1291 /* 1292 * Compare name and if it's an exact match, return the index 1293 * and buffer. If it's the first case-insensitive match, store 1294 * the index and buffer and continue looking for an exact match. 1295 */ 1296 cmp = mp->m_dirnameops->compname(args, dep->name, dep->namelen); 1297 if (cmp != XFS_CMP_DIFFERENT && cmp != args->cmpresult) { 1298 args->cmpresult = cmp; 1299 *indexp = index; 1300 /* case exact match: return the current buffer. */ 1301 if (cmp == XFS_CMP_EXACT) { 1302 *dbpp = dbp; 1303 return 0; 1304 } 1305 cidb = curdb; 1306 } 1307 } 1308 ASSERT(args->op_flags & XFS_DA_OP_OKNOENT); 1309 /* 1310 * Here, we can only be doing a lookup (not a rename or remove). 1311 * If a case-insensitive match was found earlier, re-read the 1312 * appropriate data block if required and return it. 1313 */ 1314 if (args->cmpresult == XFS_CMP_CASE) { 1315 ASSERT(cidb != -1); 1316 if (cidb != curdb) { 1317 xfs_trans_brelse(tp, dbp); 1318 error = xfs_dir3_data_read(tp, dp, 1319 xfs_dir2_db_to_da(args->geo, cidb), 1320 -1, &dbp); 1321 if (error) { 1322 xfs_trans_brelse(tp, lbp); 1323 return error; 1324 } 1325 } 1326 *dbpp = dbp; 1327 return 0; 1328 } 1329 /* 1330 * No match found, return -ENOENT. 1331 */ 1332 ASSERT(cidb == -1); 1333 if (dbp) 1334 xfs_trans_brelse(tp, dbp); 1335 xfs_trans_brelse(tp, lbp); 1336 return -ENOENT; 1337 } 1338 1339 /* 1340 * Remove an entry from a leaf format directory. 1341 */ 1342 int /* error */ 1343 xfs_dir2_leaf_removename( 1344 xfs_da_args_t *args) /* operation arguments */ 1345 { 1346 __be16 *bestsp; /* leaf block best freespace */ 1347 xfs_dir2_data_hdr_t *hdr; /* data block header */ 1348 xfs_dir2_db_t db; /* data block number */ 1349 struct xfs_buf *dbp; /* data block buffer */ 1350 xfs_dir2_data_entry_t *dep; /* data entry structure */ 1351 xfs_inode_t *dp; /* incore directory inode */ 1352 int error; /* error return code */ 1353 xfs_dir2_db_t i; /* temporary data block # */ 1354 int index; /* index into leaf entries */ 1355 struct xfs_buf *lbp; /* leaf buffer */ 1356 xfs_dir2_leaf_t *leaf; /* leaf structure */ 1357 xfs_dir2_leaf_entry_t *lep; /* leaf entry */ 1358 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */ 1359 int needlog; /* need to log data header */ 1360 int needscan; /* need to rescan data frees */ 1361 xfs_dir2_data_off_t oldbest; /* old value of best free */ 1362 struct xfs_dir2_data_free *bf; /* bestfree table */ 1363 struct xfs_dir3_icleaf_hdr leafhdr; 1364 1365 trace_xfs_dir2_leaf_removename(args); 1366 1367 /* 1368 * Lookup the leaf entry, get the leaf and data blocks read in. 1369 */ 1370 error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp, &leafhdr); 1371 if (error) 1372 return error; 1373 1374 dp = args->dp; 1375 leaf = lbp->b_addr; 1376 hdr = dbp->b_addr; 1377 xfs_dir3_data_check(dp, dbp); 1378 bf = dp->d_ops->data_bestfree_p(hdr); 1379 1380 /* 1381 * Point to the leaf entry, use that to point to the data entry. 1382 */ 1383 lep = &leafhdr.ents[index]; 1384 db = xfs_dir2_dataptr_to_db(args->geo, be32_to_cpu(lep->address)); 1385 dep = (xfs_dir2_data_entry_t *)((char *)hdr + 1386 xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address))); 1387 needscan = needlog = 0; 1388 oldbest = be16_to_cpu(bf[0].length); 1389 ltp = xfs_dir2_leaf_tail_p(args->geo, leaf); 1390 bestsp = xfs_dir2_leaf_bests_p(ltp); 1391 if (be16_to_cpu(bestsp[db]) != oldbest) { 1392 xfs_buf_corruption_error(lbp); 1393 return -EFSCORRUPTED; 1394 } 1395 /* 1396 * Mark the former data entry unused. 1397 */ 1398 xfs_dir2_data_make_free(args, dbp, 1399 (xfs_dir2_data_aoff_t)((char *)dep - (char *)hdr), 1400 dp->d_ops->data_entsize(dep->namelen), &needlog, &needscan); 1401 /* 1402 * We just mark the leaf entry stale by putting a null in it. 1403 */ 1404 leafhdr.stale++; 1405 xfs_dir2_leaf_hdr_to_disk(dp->i_mount, leaf, &leafhdr); 1406 xfs_dir3_leaf_log_header(args, lbp); 1407 1408 lep->address = cpu_to_be32(XFS_DIR2_NULL_DATAPTR); 1409 xfs_dir3_leaf_log_ents(args, &leafhdr, lbp, index, index); 1410 1411 /* 1412 * Scan the freespace in the data block again if necessary, 1413 * log the data block header if necessary. 1414 */ 1415 if (needscan) 1416 xfs_dir2_data_freescan(dp, hdr, &needlog); 1417 if (needlog) 1418 xfs_dir2_data_log_header(args, dbp); 1419 /* 1420 * If the longest freespace in the data block has changed, 1421 * put the new value in the bests table and log that. 1422 */ 1423 if (be16_to_cpu(bf[0].length) != oldbest) { 1424 bestsp[db] = bf[0].length; 1425 xfs_dir3_leaf_log_bests(args, lbp, db, db); 1426 } 1427 xfs_dir3_data_check(dp, dbp); 1428 /* 1429 * If the data block is now empty then get rid of the data block. 1430 */ 1431 if (be16_to_cpu(bf[0].length) == 1432 args->geo->blksize - dp->d_ops->data_entry_offset) { 1433 ASSERT(db != args->geo->datablk); 1434 if ((error = xfs_dir2_shrink_inode(args, db, dbp))) { 1435 /* 1436 * Nope, can't get rid of it because it caused 1437 * allocation of a bmap btree block to do so. 1438 * Just go on, returning success, leaving the 1439 * empty block in place. 1440 */ 1441 if (error == -ENOSPC && args->total == 0) 1442 error = 0; 1443 xfs_dir3_leaf_check(dp, lbp); 1444 return error; 1445 } 1446 dbp = NULL; 1447 /* 1448 * If this is the last data block then compact the 1449 * bests table by getting rid of entries. 1450 */ 1451 if (db == be32_to_cpu(ltp->bestcount) - 1) { 1452 /* 1453 * Look for the last active entry (i). 1454 */ 1455 for (i = db - 1; i > 0; i--) { 1456 if (bestsp[i] != cpu_to_be16(NULLDATAOFF)) 1457 break; 1458 } 1459 /* 1460 * Copy the table down so inactive entries at the 1461 * end are removed. 1462 */ 1463 memmove(&bestsp[db - i], bestsp, 1464 (be32_to_cpu(ltp->bestcount) - (db - i)) * sizeof(*bestsp)); 1465 be32_add_cpu(<p->bestcount, -(db - i)); 1466 xfs_dir3_leaf_log_tail(args, lbp); 1467 xfs_dir3_leaf_log_bests(args, lbp, 0, 1468 be32_to_cpu(ltp->bestcount) - 1); 1469 } else 1470 bestsp[db] = cpu_to_be16(NULLDATAOFF); 1471 } 1472 /* 1473 * If the data block was not the first one, drop it. 1474 */ 1475 else if (db != args->geo->datablk) 1476 dbp = NULL; 1477 1478 xfs_dir3_leaf_check(dp, lbp); 1479 /* 1480 * See if we can convert to block form. 1481 */ 1482 return xfs_dir2_leaf_to_block(args, lbp, dbp); 1483 } 1484 1485 /* 1486 * Replace the inode number in a leaf format directory entry. 1487 */ 1488 int /* error */ 1489 xfs_dir2_leaf_replace( 1490 xfs_da_args_t *args) /* operation arguments */ 1491 { 1492 struct xfs_buf *dbp; /* data block buffer */ 1493 xfs_dir2_data_entry_t *dep; /* data block entry */ 1494 xfs_inode_t *dp; /* incore directory inode */ 1495 int error; /* error return code */ 1496 int index; /* index of leaf entry */ 1497 struct xfs_buf *lbp; /* leaf buffer */ 1498 xfs_dir2_leaf_entry_t *lep; /* leaf entry */ 1499 xfs_trans_t *tp; /* transaction pointer */ 1500 struct xfs_dir3_icleaf_hdr leafhdr; 1501 1502 trace_xfs_dir2_leaf_replace(args); 1503 1504 /* 1505 * Look up the entry. 1506 */ 1507 error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp, &leafhdr); 1508 if (error) 1509 return error; 1510 1511 dp = args->dp; 1512 /* 1513 * Point to the leaf entry, get data address from it. 1514 */ 1515 lep = &leafhdr.ents[index]; 1516 /* 1517 * Point to the data entry. 1518 */ 1519 dep = (xfs_dir2_data_entry_t *) 1520 ((char *)dbp->b_addr + 1521 xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address))); 1522 ASSERT(args->inumber != be64_to_cpu(dep->inumber)); 1523 /* 1524 * Put the new inode number in, log it. 1525 */ 1526 dep->inumber = cpu_to_be64(args->inumber); 1527 dp->d_ops->data_put_ftype(dep, args->filetype); 1528 tp = args->trans; 1529 xfs_dir2_data_log_entry(args, dbp, dep); 1530 xfs_dir3_leaf_check(dp, lbp); 1531 xfs_trans_brelse(tp, lbp); 1532 return 0; 1533 } 1534 1535 /* 1536 * Return index in the leaf block (lbp) which is either the first 1537 * one with this hash value, or if there are none, the insert point 1538 * for that hash value. 1539 */ 1540 int /* index value */ 1541 xfs_dir2_leaf_search_hash( 1542 xfs_da_args_t *args, /* operation arguments */ 1543 struct xfs_buf *lbp) /* leaf buffer */ 1544 { 1545 xfs_dahash_t hash=0; /* hash from this entry */ 1546 xfs_dahash_t hashwant; /* hash value looking for */ 1547 int high; /* high leaf index */ 1548 int low; /* low leaf index */ 1549 xfs_dir2_leaf_entry_t *lep; /* leaf entry */ 1550 int mid=0; /* current leaf index */ 1551 struct xfs_dir3_icleaf_hdr leafhdr; 1552 1553 xfs_dir2_leaf_hdr_from_disk(args->dp->i_mount, &leafhdr, lbp->b_addr); 1554 1555 /* 1556 * Note, the table cannot be empty, so we have to go through the loop. 1557 * Binary search the leaf entries looking for our hash value. 1558 */ 1559 for (lep = leafhdr.ents, low = 0, high = leafhdr.count - 1, 1560 hashwant = args->hashval; 1561 low <= high; ) { 1562 mid = (low + high) >> 1; 1563 if ((hash = be32_to_cpu(lep[mid].hashval)) == hashwant) 1564 break; 1565 if (hash < hashwant) 1566 low = mid + 1; 1567 else 1568 high = mid - 1; 1569 } 1570 /* 1571 * Found one, back up through all the equal hash values. 1572 */ 1573 if (hash == hashwant) { 1574 while (mid > 0 && be32_to_cpu(lep[mid - 1].hashval) == hashwant) { 1575 mid--; 1576 } 1577 } 1578 /* 1579 * Need to point to an entry higher than ours. 1580 */ 1581 else if (hash < hashwant) 1582 mid++; 1583 return mid; 1584 } 1585 1586 /* 1587 * Trim off a trailing data block. We know it's empty since the leaf 1588 * freespace table says so. 1589 */ 1590 int /* error */ 1591 xfs_dir2_leaf_trim_data( 1592 xfs_da_args_t *args, /* operation arguments */ 1593 struct xfs_buf *lbp, /* leaf buffer */ 1594 xfs_dir2_db_t db) /* data block number */ 1595 { 1596 __be16 *bestsp; /* leaf bests table */ 1597 struct xfs_buf *dbp; /* data block buffer */ 1598 xfs_inode_t *dp; /* incore directory inode */ 1599 int error; /* error return value */ 1600 xfs_dir2_leaf_t *leaf; /* leaf structure */ 1601 xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */ 1602 xfs_trans_t *tp; /* transaction pointer */ 1603 1604 dp = args->dp; 1605 tp = args->trans; 1606 /* 1607 * Read the offending data block. We need its buffer. 1608 */ 1609 error = xfs_dir3_data_read(tp, dp, xfs_dir2_db_to_da(args->geo, db), 1610 -1, &dbp); 1611 if (error) 1612 return error; 1613 1614 leaf = lbp->b_addr; 1615 ltp = xfs_dir2_leaf_tail_p(args->geo, leaf); 1616 1617 #ifdef DEBUG 1618 { 1619 struct xfs_dir2_data_hdr *hdr = dbp->b_addr; 1620 struct xfs_dir2_data_free *bf = dp->d_ops->data_bestfree_p(hdr); 1621 1622 ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) || 1623 hdr->magic == cpu_to_be32(XFS_DIR3_DATA_MAGIC)); 1624 ASSERT(be16_to_cpu(bf[0].length) == 1625 args->geo->blksize - dp->d_ops->data_entry_offset); 1626 ASSERT(db == be32_to_cpu(ltp->bestcount) - 1); 1627 } 1628 #endif 1629 1630 /* 1631 * Get rid of the data block. 1632 */ 1633 if ((error = xfs_dir2_shrink_inode(args, db, dbp))) { 1634 ASSERT(error != -ENOSPC); 1635 xfs_trans_brelse(tp, dbp); 1636 return error; 1637 } 1638 /* 1639 * Eliminate the last bests entry from the table. 1640 */ 1641 bestsp = xfs_dir2_leaf_bests_p(ltp); 1642 be32_add_cpu(<p->bestcount, -1); 1643 memmove(&bestsp[1], &bestsp[0], be32_to_cpu(ltp->bestcount) * sizeof(*bestsp)); 1644 xfs_dir3_leaf_log_tail(args, lbp); 1645 xfs_dir3_leaf_log_bests(args, lbp, 0, be32_to_cpu(ltp->bestcount) - 1); 1646 return 0; 1647 } 1648 1649 static inline size_t 1650 xfs_dir3_leaf_size( 1651 struct xfs_dir3_icleaf_hdr *hdr, 1652 int counts) 1653 { 1654 int entries; 1655 int hdrsize; 1656 1657 entries = hdr->count - hdr->stale; 1658 if (hdr->magic == XFS_DIR2_LEAF1_MAGIC || 1659 hdr->magic == XFS_DIR2_LEAFN_MAGIC) 1660 hdrsize = sizeof(struct xfs_dir2_leaf_hdr); 1661 else 1662 hdrsize = sizeof(struct xfs_dir3_leaf_hdr); 1663 1664 return hdrsize + entries * sizeof(xfs_dir2_leaf_entry_t) 1665 + counts * sizeof(xfs_dir2_data_off_t) 1666 + sizeof(xfs_dir2_leaf_tail_t); 1667 } 1668 1669 /* 1670 * Convert node form directory to leaf form directory. 1671 * The root of the node form dir needs to already be a LEAFN block. 1672 * Just return if we can't do anything. 1673 */ 1674 int /* error */ 1675 xfs_dir2_node_to_leaf( 1676 xfs_da_state_t *state) /* directory operation state */ 1677 { 1678 xfs_da_args_t *args; /* operation arguments */ 1679 xfs_inode_t *dp; /* incore directory inode */ 1680 int error; /* error return code */ 1681 struct xfs_buf *fbp; /* buffer for freespace block */ 1682 xfs_fileoff_t fo; /* freespace file offset */ 1683 struct xfs_buf *lbp; /* buffer for leaf block */ 1684 xfs_dir2_leaf_tail_t *ltp; /* tail of leaf structure */ 1685 xfs_dir2_leaf_t *leaf; /* leaf structure */ 1686 xfs_mount_t *mp; /* filesystem mount point */ 1687 int rval; /* successful free trim? */ 1688 xfs_trans_t *tp; /* transaction pointer */ 1689 struct xfs_dir3_icleaf_hdr leafhdr; 1690 struct xfs_dir3_icfree_hdr freehdr; 1691 1692 /* 1693 * There's more than a leaf level in the btree, so there must 1694 * be multiple leafn blocks. Give up. 1695 */ 1696 if (state->path.active > 1) 1697 return 0; 1698 args = state->args; 1699 1700 trace_xfs_dir2_node_to_leaf(args); 1701 1702 mp = state->mp; 1703 dp = args->dp; 1704 tp = args->trans; 1705 /* 1706 * Get the last offset in the file. 1707 */ 1708 if ((error = xfs_bmap_last_offset(dp, &fo, XFS_DATA_FORK))) { 1709 return error; 1710 } 1711 fo -= args->geo->fsbcount; 1712 /* 1713 * If there are freespace blocks other than the first one, 1714 * take this opportunity to remove trailing empty freespace blocks 1715 * that may have been left behind during no-space-reservation 1716 * operations. 1717 */ 1718 while (fo > args->geo->freeblk) { 1719 if ((error = xfs_dir2_node_trim_free(args, fo, &rval))) { 1720 return error; 1721 } 1722 if (rval) 1723 fo -= args->geo->fsbcount; 1724 else 1725 return 0; 1726 } 1727 /* 1728 * Now find the block just before the freespace block. 1729 */ 1730 if ((error = xfs_bmap_last_before(tp, dp, &fo, XFS_DATA_FORK))) { 1731 return error; 1732 } 1733 /* 1734 * If it's not the single leaf block, give up. 1735 */ 1736 if (XFS_FSB_TO_B(mp, fo) > XFS_DIR2_LEAF_OFFSET + args->geo->blksize) 1737 return 0; 1738 lbp = state->path.blk[0].bp; 1739 leaf = lbp->b_addr; 1740 xfs_dir2_leaf_hdr_from_disk(mp, &leafhdr, leaf); 1741 1742 ASSERT(leafhdr.magic == XFS_DIR2_LEAFN_MAGIC || 1743 leafhdr.magic == XFS_DIR3_LEAFN_MAGIC); 1744 1745 /* 1746 * Read the freespace block. 1747 */ 1748 error = xfs_dir2_free_read(tp, dp, args->geo->freeblk, &fbp); 1749 if (error) 1750 return error; 1751 xfs_dir2_free_hdr_from_disk(mp, &freehdr, fbp->b_addr); 1752 1753 ASSERT(!freehdr.firstdb); 1754 1755 /* 1756 * Now see if the leafn and free data will fit in a leaf1. 1757 * If not, release the buffer and give up. 1758 */ 1759 if (xfs_dir3_leaf_size(&leafhdr, freehdr.nvalid) > args->geo->blksize) { 1760 xfs_trans_brelse(tp, fbp); 1761 return 0; 1762 } 1763 1764 /* 1765 * If the leaf has any stale entries in it, compress them out. 1766 */ 1767 if (leafhdr.stale) 1768 xfs_dir3_leaf_compact(args, &leafhdr, lbp); 1769 1770 lbp->b_ops = &xfs_dir3_leaf1_buf_ops; 1771 xfs_trans_buf_set_type(tp, lbp, XFS_BLFT_DIR_LEAF1_BUF); 1772 leafhdr.magic = (leafhdr.magic == XFS_DIR2_LEAFN_MAGIC) 1773 ? XFS_DIR2_LEAF1_MAGIC 1774 : XFS_DIR3_LEAF1_MAGIC; 1775 1776 /* 1777 * Set up the leaf tail from the freespace block. 1778 */ 1779 ltp = xfs_dir2_leaf_tail_p(args->geo, leaf); 1780 ltp->bestcount = cpu_to_be32(freehdr.nvalid); 1781 1782 /* 1783 * Set up the leaf bests table. 1784 */ 1785 memcpy(xfs_dir2_leaf_bests_p(ltp), freehdr.bests, 1786 freehdr.nvalid * sizeof(xfs_dir2_data_off_t)); 1787 1788 xfs_dir2_leaf_hdr_to_disk(mp, leaf, &leafhdr); 1789 xfs_dir3_leaf_log_header(args, lbp); 1790 xfs_dir3_leaf_log_bests(args, lbp, 0, be32_to_cpu(ltp->bestcount) - 1); 1791 xfs_dir3_leaf_log_tail(args, lbp); 1792 xfs_dir3_leaf_check(dp, lbp); 1793 1794 /* 1795 * Get rid of the freespace block. 1796 */ 1797 error = xfs_dir2_shrink_inode(args, 1798 xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET), 1799 fbp); 1800 if (error) { 1801 /* 1802 * This can't fail here because it can only happen when 1803 * punching out the middle of an extent, and this is an 1804 * isolated block. 1805 */ 1806 ASSERT(error != -ENOSPC); 1807 return error; 1808 } 1809 fbp = NULL; 1810 /* 1811 * Now see if we can convert the single-leaf directory 1812 * down to a block form directory. 1813 * This routine always kills the dabuf for the leaf, so 1814 * eliminate it from the path. 1815 */ 1816 error = xfs_dir2_leaf_to_block(args, lbp, NULL); 1817 state->path.blk[0].bp = NULL; 1818 return error; 1819 } 1820