| blob | 2563df89fc2a0e60f28a2e8958ddfda525099fb4 |
1 /* -*- mode: c; c-basic-offset: 8; -*-
2 * vim: noexpandtab sw=8 ts=8 sts=0:
3 *
4 * xattr.c
5 *
6 * Copyright (C) 2004, 2008 Oracle. All rights reserved.
7 *
8 * CREDITS:
9 * Lots of code in this file is copy from linux/fs/ext3/xattr.c.
10 * Copyright (C) 2001-2003 Andreas Gruenbacher, <agruen@suse.de>
11 *
12 * This program is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU General Public
14 * License version 2 as published by the Free Software Foundation.
15 *
16 * This program is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 * General Public License for more details.
20 */
22 #include <linux/capability.h>
23 #include <linux/fs.h>
24 #include <linux/types.h>
25 #include <linux/slab.h>
26 #include <linux/highmem.h>
27 #include <linux/pagemap.h>
28 #include <linux/uio.h>
29 #include <linux/sched.h>
30 #include <linux/splice.h>
31 #include <linux/mount.h>
32 #include <linux/writeback.h>
33 #include <linux/falloc.h>
34 #include <linux/sort.h>
35 #include <linux/init.h>
36 #include <linux/module.h>
37 #include <linux/string.h>
38 #include <linux/security.h>
40 #define MLOG_MASK_PREFIX ML_XATTR
41 #include <cluster/masklog.h>
63 };
66 /* The inode these xattrs are associated with */
69 /* The actual buffers that make up the bucket */
72 /* How many blocks make up one bucket for this filesystem */
74 };
81 };
83 #define OCFS2_XATTR_ROOT_SIZE (sizeof(struct ocfs2_xattr_def_value_root))
84 #define OCFS2_XATTR_INLINE_SIZE 80
85 #define OCFS2_XATTR_HEADER_GAP 4
86 #define OCFS2_XATTR_FREE_IN_IBODY (OCFS2_MIN_XATTR_INLINE_SIZE \
87 - sizeof(struct ocfs2_xattr_header) \
88 - OCFS2_XATTR_HEADER_GAP)
89 #define OCFS2_XATTR_FREE_IN_BLOCK(ptr) ((ptr)->i_sb->s_blocksize \
90 - sizeof(struct ocfs2_xattr_block) \
91 - sizeof(struct ocfs2_xattr_header) \
92 - OCFS2_XATTR_HEADER_GAP)
96 };
100 #ifdef CONFIG_OCFS2_FS_POSIX_ACL
103 #endif
106 NULL
107 };
111 #ifdef CONFIG_OCFS2_FS_POSIX_ACL
116 #endif
119 };
126 };
130 /*
131 * xattr_bh point to the block buffer head which has extended attribute
132 * when extended attribute in inode, xattr_bh is equal to inode_bh.
133 */
141 };
181 {
183 }
186 {
188 }
191 {
196 }
198 #define bucket_blkno(_b) ((_b)->bu_bhs[0]->b_blocknr)
199 #define bucket_block(_b, _n) ((_b)->bu_bhs[(_n)]->b_data)
200 #define bucket_xh(_b) ((struct ocfs2_xattr_header *)bucket_block((_b), 0))
203 {
213 }
216 }
219 {
225 }
226 }
229 {
234 }
235 }
237 /*
238 * A bucket that has never been written to disk doesn't need to be
239 * read. We just need the buffer_heads. Don't call this for
240 * buckets that are already on disk. ocfs2_read_xattr_bucket() initializes
241 * them fully.
242 */
244 u64 xb_blkno)
245 {
255 }
261 }
266 }
268 /* Read the xattr bucket at xb_blkno */
270 u64 xb_blkno)
271 {
276 NULL);
286 }
291 }
296 {
305 }
306 }
309 }
313 {
324 }
328 {
337 blocksize);
338 }
339 }
343 {
353 /*
354 * If the ecc fails, we return the error but otherwise
355 * leave the filesystem running. We know any error is
356 * local to this block.
357 */
362 /*
363 * Errors after here are fatal
364 */
368 "Extended attribute block #%llu has bad "
373 }
377 "Extended attribute block #%llu has an "
382 }
386 "Extended attribute block #%llu has an invalid "
391 }
394 }
398 {
403 ocfs2_validate_xattr_block);
405 /* If ocfs2_read_block() got us a new bh, pass it up. */
410 }
413 {
420 }
425 {
426 /* Get hash value of uuid from super block */
430 /* hash extended attribute name */
435 }
438 }
440 /*
441 * ocfs2_xattr_hash_entry()
442 *
443 * Compute the hash of an extended attribute.
444 */
448 {
456 }
459 {
464 else
469 }
476 {
482 /*
483 * The max space of security xattr taken inline is
484 * 256(name) + 80(value) + 16(entry) = 352 bytes,
485 * So reserve one metadata block for it is ok.
486 */
493 }
495 }
497 /* reserve clusters for xattr value which will be set in B tree*/
503 new_clusters);
505 }
507 }
516 {
527 OCFS2_XATTR_INDEX_POSIX_ACL_DEFAULT,
536 }
537 }
542 /*
543 * The max space of security xattr taken inline is
544 * 256(name) + 80(value) + 16(entry) = 352 bytes,
545 * The max space of acl xattr taken inline is
546 * 80(value) + 16(entry) * 2(if directory) = 192 bytes,
547 * when blocksize = 512, may reserve one more cluser for
548 * xattr bucket, otherwise reserve one metadata block
549 * for them is ok.
550 * If this is a new directory with inline data,
551 * we choose to reserve the entire inline area for
552 * directory contents and force an external xattr block.
553 */
561 }
563 }
569 }
571 /*
572 * reserve credits and clusters for xattrs which has large value
573 * and have to be set outside
574 */
579 new_clusters);
581 }
584 /* for directory, it has DEFAULT and ACCESS two types of acls */
588 new_clusters);
590 }
593 }
596 u32 clusters_to_add,
599 {
612 OCFS2_JOURNAL_ACCESS_WRITE);
616 }
620 inode,
622 clusters_to_add,
625 handle,
632 }
638 }
642 /*
643 * We should have already allocated enough space before the transaction,
644 * so no need to restart.
645 */
648 leave:
651 }
657 {
666 OCFS2_JOURNAL_ACCESS_WRITE);
670 }
677 }
685 }
691 out:
693 }
696 u32 old_clusters,
697 u32 new_clusters,
700 {
703 u64 block;
717 }
724 ctxt);
728 }
732 alloc_size);
735 }
737 out:
739 }
745 {
757 else
763 }
768 {
775 /* we are just looking for how big our buffer needs to be */
787 }
792 {
811 }
812 }
815 }
821 {
836 }
842 {
855 }
866 }
871 }
876 {
892 }
904 }
909 }
916 }
921 {
938 name_len);
942 }
946 }
952 {
954 u64 blkno;
972 }
975 /* Copy ocfs2_xattr_value */
981 }
992 }
994 }
995 out:
997 }
1005 {
1042 }
1043 }
1044 }
1047 }
1055 {
1066 }
1072 }
1077 }
1093 i,
1097 }
1109 }
1110 }
1111 }
1113 cleanup:
1119 }
1127 {
1133 };
1136 };
1156 }
1158 /* ocfs2_xattr_get()
1159 *
1160 * Copy an extended attribute into the buffer provided.
1161 * Buffer is NULL to compute the size of buffer required.
1162 */
1168 {
1176 }
1185 }
1192 {
1198 u64 blkno;
1209 }
1218 }
1221 inode,
1222 bh,
1223 OCFS2_JOURNAL_ACCESS_WRITE);
1227 }
1241 }
1245 /*
1246 * XXX: do we need to empty all the following
1247 * blocks in this cluster?
1248 */
1251 }
1253 }
1254 out:
1258 }
1266 {
1273 OCFS2_JOURNAL_ACCESS_WRITE);
1277 }
1278 /* Decrease xattr count */
1280 /* Remove the xattr entry and tree root which has already be set*/
1287 out:
1289 }
1297 {
1301 OCFS2_JOURNAL_ACCESS_WRITE);
1305 }
1311 else
1318 out:
1320 }
1322 /*
1323 * ocfs2_xattr_set_value_outside()
1324 *
1325 * Set large size value in B tree.
1326 */
1333 {
1355 }
1360 }
1367 }
1369 /*
1370 * ocfs2_xattr_set_entry_local()
1371 *
1372 * Set, replace or remove extended attribute in local.
1373 */
1379 {
1384 /* Insert the new xattr entry. */
1399 OCFS2_XATTR_INLINE_SIZE)
1401 OCFS2_XATTR_ROOT_SIZE;
1402 else
1408 /* The old and the new value have the
1409 same size. Just replace the value. */
1412 /* Clear value bytes. */
1420 }
1421 /* Remove the old name+value. */
1431 /* Adjust all value offsets. */
1439 }
1442 /* Remove the old entry. */
1448 }
1449 }
1451 /* Insert the new name+value. */
1465 }
1468 }
1470 /*
1471 * ocfs2_xattr_set_entry()
1472 *
1473 * Set extended attribute entry into inode or block.
1474 *
1475 * If extended attribute value size > OCFS2_XATTR_INLINE_SIZE,
1476 * We first insert tree root(ocfs2_xattr_value_root) with set_entry_local(),
1477 * then set value in B tree with set_value_outside().
1478 */
1484 {
1497 };
1501 };
1509 /* Compute min_offs, last and free space. */
1517 }
1528 else
1530 OCFS2_XATTR_ROOT_SIZE;
1532 }
1533 /* Check free space in inode or block */
1537 OCFS2_XATTR_ROOT_SIZE) {
1540 }
1550 }
1551 }
1554 /* For existing extended attribute */
1561 /* Replace existing local xattr with tree root */
1568 /* For existing xattr which has value outside */
1573 /*
1574 * If new value need set outside also,
1575 * first truncate old value to new value,
1576 * then set new value with set_value_outside().
1577 */
1581 ctxt);
1585 }
1588 handle,
1589 xi,
1590 xs,
1592 offs);
1596 }
1599 handle,
1607 /*
1608 * If new value need set in local,
1609 * just trucate old value to zero.
1610 */
1614 ctxt);
1617 }
1618 }
1619 }
1622 OCFS2_JOURNAL_ACCESS_WRITE);
1626 }
1630 OCFS2_JOURNAL_ACCESS_WRITE);
1634 }
1635 }
1637 /*
1638 * Set value in local, include set tree root in local.
1639 * This is the first step for value size >INLINE_SIZE.
1640 */
1648 }
1649 }
1656 /*
1657 * Adjust extent record count or inline data size
1658 * to reserve space for extended attribute.
1659 */
1667 }
1669 }
1670 /* Update xattr flag */
1681 /*
1682 * Set value outside in B tree.
1683 * This is the second step for value size > INLINE_SIZE.
1684 */
1692 /*
1693 * If set value outside failed, we have to clean
1694 * the junk tree root we have already set in local.
1695 */
1700 }
1701 }
1702 out:
1704 }
1709 {
1722 }
1738 }
1739 }
1740 }
1745 out:
1747 }
1751 {
1759 };
1768 }
1772 {
1778 };
1788 }
1791 u64 block)
1792 {
1801 u16 bit;
1807 }
1813 }
1821 EXTENT_ALLOC_SYSTEM_INODE,
1827 }
1834 }
1841 }
1849 out_unlock:
1852 out_mutex:
1855 out:
1858 }
1860 /*
1861 * ocfs2_xattr_remove()
1862 *
1863 * Free extended attribute resources associated with this inode.
1864 */
1866 {
1883 }
1884 }
1892 }
1893 }
1896 OCFS2_INODE_UPDATE_CREDITS);
1901 }
1903 OCFS2_JOURNAL_ACCESS_WRITE);
1907 }
1919 out_commit:
1921 out:
1923 }
1927 {
1946 }
1951 }
1953 /*
1954 * ocfs2_xattr_ibody_find()
1955 *
1956 * Find extended attribute in inode block and
1957 * fill search info into struct ocfs2_xattr_search.
1958 */
1963 {
1978 }
1985 else
1991 /* Find the named attribute. */
1997 }
2000 }
2002 /*
2003 * ocfs2_xattr_ibody_set()
2004 *
2005 * Set, replace or remove an extended attribute into inode block.
2006 *
2007 */
2012 {
2025 }
2026 }
2030 out:
2034 }
2036 /*
2037 * ocfs2_xattr_block_find()
2038 *
2039 * Find extended attribute in external block and
2040 * fill search info into struct ocfs2_xattr_search.
2041 */
2046 {
2060 }
2074 name_index,
2080 }
2083 cleanup:
2087 }
2089 /*
2090 * ocfs2_xattr_block_set()
2091 *
2092 * Set, replace or remove an extended attribute into external block.
2093 *
2094 */
2099 {
2105 u16 suballoc_bit_start;
2106 u32 num_got;
2107 u64 first_blkno;
2112 OCFS2_JOURNAL_ACCESS_CREATE);
2116 }
2124 }
2130 OCFS2_JOURNAL_ACCESS_CREATE);
2134 }
2136 /* Initialize ocfs2_xattr_block */
2155 }
2162 /* Set extended attribute into external block */
2164 OCFS2_HAS_XATTR_FL);
2171 }
2175 end:
2178 }
2180 /* Check whether the new xattr can be inserted into the inode. */
2184 {
2185 u64 value_size;
2200 }
2210 else
2218 }
2228 {
2239 u64 value_size;
2241 /*
2242 * Calculate the clusters we need to write.
2243 * No matter whether we replace an old one or add a new one,
2244 * we need this for writing.
2245 */
2257 new_clusters);
2258 }
2261 }
2288 }
2289 }
2291 /*
2292 * delete a xattr doesn't need metadata and cluster allocation.
2293 * so just calculate the credits and return.
2294 *
2295 * The credits for removing the value tree will be extended
2296 * by ocfs2_remove_extent itself.
2297 */
2303 }
2305 /* do cluster allocation guess first. */
2309 /*
2310 * In xattr set, we always try to set the xe in inode first,
2311 * so if it can be inserted into inode successfully, the old
2312 * one will be removed from the xattr block, and this xattr
2313 * will be inserted into inode as a new xattr in inode.
2314 */
2318 OCFS2_INODE_UPDATE_CREDITS;
2323 new_clusters);
2325 }
2326 }
2329 /* the new values will be stored outside. */
2334 value_size);
2349 new_clusters -
2350 old_clusters);
2353 }
2355 /*
2356 * Now the new value will be stored inside. So if the new
2357 * value is smaller than the size of value root or the old
2358 * value, we don't need any allocation, otherwise we have
2359 * to guess metadata allocation.
2360 */
2365 }
2367 meta_guess:
2368 /* calculate metadata allocation. */
2377 }
2383 /*
2384 * If there is already an xattr tree, good, we can calculate
2385 * like other b-trees. Otherwise we may have the chance of
2386 * create a tree, the credit calculation is borrowed from
2387 * ocfs2_calc_extend_credits with root_el = NULL. And the
2388 * new tree will be cluster based, so no meta is needed.
2389 */
2399 /*
2400 * This cluster will be used either for new bucket or for
2401 * new xattr block.
2402 * If the cluster size is the same as the bucket size, one
2403 * more is needed since we may need to extend the bucket
2404 * also.
2405 */
2412 }
2416 }
2417 out:
2426 }
2435 {
2448 }
2459 }
2460 }
2466 }
2467 out:
2472 }
2474 /*
2475 * We cannot have an error and a non null ctxt->data_ac.
2476 */
2477 }
2480 }
2488 {
2492 /* Remove existing extended attribute */
2498 /* We always try to set extended attribute into inode first*/
2501 /*
2502 * If succeed and that extended attribute existing in
2503 * external block, then we will remove it.
2504 */
2511 di,
2512 xi,
2513 xis,
2514 xbs,
2515 NULL,
2516 NULL,
2522 }
2529 }
2542 di,
2543 xi,
2544 xis,
2545 xbs,
2546 NULL,
2547 NULL,
2553 }
2560 }
2561 }
2562 /*
2563 * If no space in inode, we will set extended attribute
2564 * into external block.
2565 */
2570 /*
2571 * If succeed and that extended attribute
2572 * existing in inode, we will remove it.
2573 */
2578 di,
2579 xi,
2580 xis,
2581 xbs,
2582 NULL,
2583 NULL,
2588 }
2595 }
2598 }
2599 }
2600 }
2603 /* Update inode ctime. */
2606 OCFS2_JOURNAL_ACCESS_WRITE);
2610 }
2616 }
2617 out:
2619 }
2621 /*
2622 * This function only called duing creating inode
2623 * for init security/acl xattrs of the new inode.
2624 * All transanction credits have been reserved in mknod.
2625 */
2636 {
2645 };
2649 };
2653 };
2659 };
2664 /*
2665 * In extreme situation, may need xattr bucket when
2666 * block size is too small. And we have already reserved
2667 * the credits for bucket in mknod.
2668 */
2674 }
2675 }
2689 }
2693 cleanup:
2699 }
2701 /*
2702 * ocfs2_xattr_set()
2703 *
2704 * Set, replace or remove an extended attribute for this inode.
2705 * value is NULL to remove an existing extended attribute, else either
2706 * create or replace an extended attribute.
2707 */
2714 {
2727 };
2731 };
2735 };
2740 /*
2741 * Only xbs will be used on indexed trees. xis doesn't need a
2742 * bucket.
2743 */
2748 }
2754 }
2759 /*
2760 * Scan inode and external block to find the same name
2761 * extended attribute and collect search infomation.
2762 */
2770 }
2783 }
2794 }
2795 }
2803 }
2805 /* we need to update inode's ctime field, so add credit for it. */
2812 }
2825 cleanup:
2828 cleanup_nolock:
2834 }
2836 /*
2837 * Find the xattr extent rec which may contains name_hash.
2838 * e_cpos will be the first name hash of the xattr rec.
2839 * el must be the ocfs2_xattr_header.xb_attrs.xb_root.xt_list.
2840 */
2842 u32 name_hash,
2847 {
2859 }
2866 "Inode %lu has non zero tree depth in "
2871 }
2872 }
2880 }
2881 }
2890 }
2896 out:
2899 }
2909 u32 name_hash,
2912 {
2919 /*
2920 * We don't use binary search in the bucket because there
2921 * may be multiple entries with the same name hash.
2922 */
2938 xh,
2939 i,
2945 }
2954 }
2955 }
2958 }
2960 /*
2961 * Find the specified xattr entry in a series of buckets.
2962 * This series start from p_blkno and last for num_clusters.
2963 * The ocfs2_xattr_header.xh_num_buckets of the first bucket contains
2964 * the num of the valid buckets.
2965 *
2966 * Return the buffer_head this xattr should reside in. And if the xattr's
2967 * hash is in the gap of 2 buckets, return the lower bucket.
2968 */
2972 u32 name_hash,
2973 u64 p_blkno,
2974 u32 first_hash,
2975 u32 num_clusters,
2977 {
2985 u32 last_hash;
2993 }
2999 }
3012 }
3019 }
3021 /*
3022 * Check whether the hash of the last entry in our
3023 * bucket is larger than the search one. for an empty
3024 * bucket, the last one is also the first one.
3025 */
3031 /* record lower_blkno which may be the insert place. */
3037 }
3039 /* the searched xattr should reside in this bucket if exists. */
3046 }
3048 }
3050 /*
3051 * Record the bucket we have found.
3052 * When the xattr's hash value is in the gap of 2 buckets, we will
3053 * always set it to the previous bucket.
3054 */
3058 /* This should be in cache - we just read it during the search */
3063 }
3076 out:
3079 }
3086 {
3107 }
3113 first_hash);
3118 out:
3120 }
3123 u64 blkno,
3124 u32 clusters,
3127 {
3137 }
3147 }
3149 /*
3150 * The real bucket num in this series of blocks is stored
3151 * in the 1st bucket.
3152 */
3163 /* Fall through to bucket_relse() */
3164 }
3169 }
3173 }
3179 };
3186 {
3187 u16 name_offset;
3198 }
3203 {
3217 i,
3224 new_offset;
3232 }
3233 }
3236 }
3242 {
3251 };
3262 }
3265 ocfs2_list_xattr_bucket,
3270 }
3276 }
3279 out:
3281 }
3284 {
3294 }
3297 {
3303 }
3305 /*
3306 * When the ocfs2_xattr_block is filled up, new bucket will be created
3307 * and all the xattr entries will be moved to the new bucket.
3308 * The header goes at the start of the bucket, and the names+values are
3309 * filled from the end. This is why *target starts as the last buffer.
3310 * Note: we need to sort the entries since they are not saved in order
3311 * in the ocfs2_xattr_block.
3312 */
3316 {
3336 /*
3337 * Since the xe_name_offset is based on ocfs2_xattr_header,
3338 * there is a offset change corresponding to the change of
3339 * ocfs2_xattr_header's position.
3340 */
3346 /* copy all the names and values. */
3349 /* Init new header now. */
3355 /* copy all the entries. */
3361 /* Change the xe offset for all the xe because of the move. */
3372 }
3374 /*
3375 * After we move xattr from block to index btree, we have to
3376 * update ocfs2_xattr_search to the new xe and base.
3377 *
3378 * When the entry is in xattr block, xattr_bh indicates the storage place.
3379 * While if the entry is in index b-tree, "bucket" indicates the
3380 * real place of the xattr.
3381 */
3385 {
3400 }
3405 {
3408 u64 blkno;
3424 /*
3425 * XXX:
3426 * We can use this lock for now, and maybe move to a dedicated mutex
3427 * if performance becomes a problem later.
3428 */
3432 OCFS2_JOURNAL_ACCESS_WRITE);
3436 }
3443 }
3445 /*
3446 * The bucket may spread in many blocks, and
3447 * we will only touch the 1st block and the last block
3448 * in the whole bucket(one for entry and one for data).
3449 */
3459 }
3462 OCFS2_JOURNAL_ACCESS_CREATE);
3466 }
3473 /* Change from ocfs2_xattr_header to ocfs2_xattr_tree_root */
3492 out:
3496 }
3499 {
3509 }
3511 /*
3512 * defrag a xattr bucket if we find that the bucket has some
3513 * holes beteen name/value pairs.
3514 * We will move all the name/value pairs to the end of the bucket
3515 * so that we can spare some space for insertion.
3516 */
3520 {
3526 u16 xh_free_start;
3530 /*
3531 * In order to make the operation more efficient and generic,
3532 * we copy all the blocks into a contiguous memory and do the
3533 * defragment there, so if anything is error, we will not touch
3534 * the real block.
3535 */
3540 }
3547 OCFS2_JOURNAL_ACCESS_WRITE);
3551 }
3562 /*
3563 * sort all the entries by their offset.
3564 * the largest will be the first, so that we can
3565 * move them to the end one by one.
3566 */
3571 /* Move all name/values to the end of the bucket. */
3579 else
3583 /*
3584 * We must make sure that the name/value pair
3585 * exist in the same block. So adjust end to
3586 * the previous block end if needed.
3587 */
3596 }
3602 }
3613 /* sort the entries by their name_hash. */
3623 out:
3626 }
3628 /*
3629 * prev_blkno points to the start of an existing extent. new_blkno
3630 * points to a newly allocated extent. Because we know each of our
3631 * clusters contains more than bucket, we can easily split one cluster
3632 * at a bucket boundary. So we take the last cluster of the existing
3633 * extent and split it down the middle. We move the last half of the
3634 * buckets in the last cluster of the existing extent over to the new
3635 * extent.
3636 *
3637 * first_bh is the buffer at prev_blkno so we can update the existing
3638 * extent's bucket count. header_bh is the bucket were we were hoping
3639 * to insert our xattr. If the bucket move places the target in the new
3640 * extent, we'll update first_bh and header_bh after modifying the old
3641 * extent.
3642 *
3643 * first_hash will be set as the 1st xe's name_hash in the new extent.
3644 */
3649 u64 new_blkno,
3650 u32 num_clusters,
3652 {
3658 u64 src_blkno;
3674 }
3676 /* This is the first bucket that got moved */
3679 /*
3680 * If the target bucket was part of the moved buckets, we need to
3681 * update first and target.
3682 */
3684 /* Find the block for the new target bucket */
3691 /*
3692 * These shouldn't fail - the buffers are in the
3693 * journal from ocfs2_cp_xattr_bucket().
3694 */
3699 }
3704 }
3706 out:
3708 }
3710 /*
3711 * Find the suitable pos when we divide a bucket into 2.
3712 * We have to make sure the xattrs with the same hash value exist
3713 * in the same bucket.
3714 *
3715 * If this ocfs2_xattr_header covers more than one hash value, find a
3716 * place where the hash value changes. Try to find the most even split.
3717 * The most common case is that all entries have different hash values,
3718 * and the first check we make will find a place to split.
3719 */
3721 {
3726 /*
3727 * We start at the middle. Each step gets farther away in both
3728 * directions. We therefore hit the change in hash value
3729 * nearest to the middle. Note that this loop does not execute for
3730 * count < 2.
3731 */
3733 /* Let's check delta earlier than middle */
3738 /* For even counts, don't walk off the end */
3742 /* Now try delta past middle */
3746 }
3748 /* Every entry had the same hash */
3750 }
3752 /*
3753 * Move some xattrs in old bucket(blk) to new bucket(new_blk).
3754 * first_hash will record the 1st hash of the new bucket.
3755 *
3756 * Normally half of the xattrs will be moved. But we have to make
3757 * sure that the xattrs with the same hash value are stored in the
3758 * same bucket. If all the xattrs in this bucket have the same hash
3759 * value, the new bucket will be initialized as an empty one and the
3760 * first_hash will be initialized as (hash_value+1).
3761 */
3764 u64 blk,
3765 u64 new_blk,
3768 {
3785 }
3791 }
3794 OCFS2_JOURNAL_ACCESS_WRITE);
3798 }
3800 /*
3801 * Even if !new_bucket_head, we're overwriting t_bucket. Thus,
3802 * there's no need to read it.
3803 */
3808 }
3810 /*
3811 * Hey, if we're overwriting t_bucket, what difference does
3812 * ACCESS_CREATE vs ACCESS_WRITE make? See the comment in the
3813 * same part of ocfs2_cp_xattr_bucket().
3814 */
3816 new_bucket_head ?
3817 OCFS2_JOURNAL_ACCESS_CREATE :
3818 OCFS2_JOURNAL_ACCESS_WRITE);
3822 }
3831 /*
3832 * initialized a new empty bucket here.
3833 * The hash value is set as one larger than
3834 * that of the last entry in the previous bucket.
3835 */
3845 }
3847 /* copy the whole bucket to the new first. */
3850 /* update the new bucket. */
3853 /*
3854 * Calculate the total name/value len and xh_free_start for
3855 * the old bucket first.
3856 */
3863 xe_len +=
3865 else
3870 }
3872 /*
3873 * Now begin the modification to the new bucket.
3874 *
3875 * In the new bucket, We just move the xattr entry to the beginning
3876 * and don't touch the name/value. So there will be some holes in the
3877 * bucket, and they will be removed when ocfs2_defrag_xattr_bucket is
3878 * called.
3879 */
3893 /* Calculate xh_free_start for the new bucket. */
3899 xe_len +=
3901 else
3906 }
3908 set_num_buckets:
3909 /* set xh->xh_num_buckets for the new xh. */
3912 else
3917 /* store the first_hash of the new bucket. */
3921 /*
3922 * Now only update the 1st block of the old bucket. If we
3923 * just added a new empty bucket, there is no need to modify
3924 * it.
3925 */
3938 out:
3943 }
3945 /*
3946 * Copy xattr from one bucket to another bucket.
3947 *
3948 * The caller must make sure that the journal transaction
3949 * has enough space for journaling.
3950 */
3953 u64 s_blkno,
3954 u64 t_blkno,
3956 {
3964 t_is_new);
3972 }
3978 /*
3979 * Even if !t_is_new, we're overwriting t_bucket. Thus,
3980 * there's no need to read it.
3981 */
3986 /*
3987 * Hey, if we're overwriting t_bucket, what difference does
3988 * ACCESS_CREATE vs ACCESS_WRITE make? Well, if we allocated a new
3989 * cluster to fill, we came here from
3990 * ocfs2_mv_xattr_buckets(), and it is really new -
3991 * ACCESS_CREATE is required. But we also might have moved data
3992 * out of t_bucket before extending back into it.
3993 * ocfs2_add_new_xattr_bucket() can do this - its call to
3994 * ocfs2_add_new_xattr_cluster() may have created a new extent
3995 * and copied out the end of the old extent. Then it re-extends
3996 * the old extent back to create space for new xattrs. That's
3997 * how we get here, and the bucket isn't really new.
3998 */
4000 t_is_new ?
4001 OCFS2_JOURNAL_ACCESS_CREATE :
4002 OCFS2_JOURNAL_ACCESS_WRITE);
4009 out:
4014 }
4016 /*
4017 * src_blk points to the start of an existing extent. last_blk points to
4018 * last cluster in that extent. to_blk points to a newly allocated
4019 * extent. We copy the buckets from the cluster at last_blk to the new
4020 * extent. If start_bucket is non-zero, we skip that many buckets before
4021 * we start copying. The new extent's xh_num_buckets gets set to the
4022 * number of buckets we copied. The old extent's xh_num_buckets shrinks
4023 * by the same amount.
4024 */
4029 {
4043 }
4045 /* The first bucket of the original extent */
4047 /* The first bucket of the new extent */
4053 }
4059 }
4061 /*
4062 * We need to update the first bucket of the old extent and all
4063 * the buckets going to the new extent.
4064 */
4071 }
4074 OCFS2_JOURNAL_ACCESS_WRITE);
4078 }
4088 }
4089 }
4091 /*
4092 * Get the new bucket ready before we dirty anything
4093 * (This actually shouldn't fail, because we already dirtied
4094 * it once in ocfs2_cp_xattr_bucket()).
4095 */
4100 }
4102 OCFS2_JOURNAL_ACCESS_WRITE);
4106 }
4108 /* Now update the headers */
4118 out:
4122 }
4124 /*
4125 * Move some xattrs in this cluster to the new cluster.
4126 * This function should only be called when bucket size == cluster size.
4127 * Otherwise ocfs2_mv_xattr_bucket_cross_cluster should be used instead.
4128 */
4131 u64 prev_blk,
4132 u64 new_blk,
4134 {
4144 }
4146 /* Move half of the xattr in start_blk to the next bucket. */
4149 }
4151 /*
4152 * Move some xattrs from the old cluster to the new one since they are not
4153 * contiguous in ocfs2 xattr tree.
4154 *
4155 * new_blk starts a new separate cluster, and we will move some xattrs from
4156 * prev_blk to it. v_start will be set as the first name hash value in this
4157 * new cluster so that it can be used as e_cpos during tree insertion and
4158 * don't collide with our original b-tree operations. first_bh and header_bh
4159 * will also be updated since they will be used in ocfs2_extend_xattr_bucket
4160 * to extend the insert bucket.
4161 *
4162 * The problem is how much xattr should we move to the new one and when should
4163 * we update first_bh and header_bh?
4164 * 1. If cluster size > bucket size, that means the previous cluster has more
4165 * than 1 bucket, so just move half nums of bucket into the new cluster and
4166 * update the first_bh and header_bh if the insert bucket has been moved
4167 * to the new cluster.
4168 * 2. If cluster_size == bucket_size:
4169 * a) If the previous extent rec has more than one cluster and the insert
4170 * place isn't in the last cluster, copy the entire last cluster to the
4171 * new one. This time, we don't need to upate the first_bh and header_bh
4172 * since they will not be moved into the new cluster.
4173 * b) Otherwise, move the bottom half of the xattrs in the last cluster into
4174 * the new one. And we set the extend flag to zero if the insert place is
4175 * moved into the new allocated cluster since no extend is needed.
4176 */
4181 u64 new_blk,
4182 u32 prev_clusters,
4185 {
4194 handle,
4196 new_blk,
4197 prev_clusters,
4198 v_start);
4202 /* The start of the last cluster in the first extent */
4211 v_start);
4217 v_start);
4223 }
4224 }
4227 }
4229 /*
4230 * Add a new cluster for xattr storage.
4231 *
4232 * If the new cluster is contiguous with the previous one, it will be
4233 * appended to the same extent record, and num_clusters will be updated.
4234 * If not, we will insert a new extent for it and move some xattrs in
4235 * the last cluster into the new allocated one.
4236 * We also need to limit the maximum size of a btree leaf, otherwise we'll
4237 * lose the benefits of hashing because we'll have to search large leaves.
4238 * So now the maximum size is OCFS2_MAX_XATTR_TREE_LEAF_SIZE(or clustersize,
4239 * if it's bigger).
4240 *
4241 * first_bh is the first block of the previous extent rec and header_bh
4242 * indicates the bucket we will insert the new xattrs. They will be updated
4243 * when the header_bh is moved into the new cluster.
4244 */
4250 u32 prev_cpos,
4253 {
4258 u64 block;
4271 OCFS2_JOURNAL_ACCESS_WRITE);
4275 }
4283 }
4293 OCFS2_MAX_XATTR_TREE_LEAF_SIZE) {
4294 /*
4295 * If this cluster is contiguous with the old one and
4296 * adding this new cluster, we don't surpass the limit of
4297 * OCFS2_MAX_XATTR_TREE_LEAF_SIZE, cool. We will let it be
4298 * initialized and used like other buckets in the previous
4299 * cluster.
4300 * So add it as a contiguous one. The caller will handle
4301 * its init process.
4302 */
4306 num_bits);
4309 handle,
4310 first,
4311 target,
4312 block,
4313 prev_clusters,
4315 extend);
4319 }
4320 }
4329 }
4335 leave:
4337 }
4339 /*
4340 * We are given an extent. 'first' is the bucket at the very front of
4341 * the extent. The extent has space for an additional bucket past
4342 * bucket_xh(first)->xh_num_buckets. 'target_blkno' is the block number
4343 * of the target bucket. We wish to shift every bucket past the target
4344 * down one, filling in that additional space. When we get back to the
4345 * target, we split the target between itself and the now-empty bucket
4346 * at target+1 (aka, target_blkno + blks_per_bucket).
4347 */
4351 u64 target_blk,
4352 u32 num_clusters)
4353 {
4357 u64 end_blk;
4364 /* The extent must have room for an additional bucket */
4368 /* end_blk points to the last existing bucket */
4371 /*
4372 * end_blk is the start of the last existing bucket.
4373 * Thus, (end_blk - target_blk) covers the target bucket and
4374 * every bucket after it up to, but not including, the last
4375 * existing bucket. Then we add the last existing bucket, the
4376 * new bucket, and the first bucket (3 * blk_per_bucket).
4377 */
4384 }
4387 OCFS2_JOURNAL_ACCESS_WRITE);
4391 }
4399 }
4401 /* Move half of the xattr in target_blkno to the next bucket. */
4408 out:
4410 }
4412 /*
4413 * Add new xattr bucket in an extent record and adjust the buckets
4414 * accordingly. xb_bh is the ocfs2_xattr_block, and target is the
4415 * bucket we want to insert into.
4416 *
4417 * In the easy case, we will move all the buckets after target down by
4418 * one. Half of target's xattrs will be moved to the next bucket.
4419 *
4420 * If current cluster is full, we'll allocate a new one. This may not
4421 * be contiguous. The underlying calls will make sure that there is
4422 * space for the insert, shifting buckets around if necessary.
4423 * 'target' may be moved by those calls.
4424 */
4429 {
4434 u32 name_hash =
4438 u64 p_blkno;
4440 /* The bucket at the front of the extent */
4446 /* The first bucket of the original extent */
4452 }
4459 }
4465 }
4469 /*
4470 * This can move first+target if the target bucket moves
4471 * to the new extent.
4472 */
4474 xb_bh,
4475 first,
4476 target,
4478 e_cpos,
4480 ctxt);
4484 }
4485 }
4490 first,
4492 num_clusters);
4495 }
4497 out:
4501 }
4506 {
4511 }
4513 /*
4514 * Handle the normal xattr set, including replace, delete and new.
4515 *
4516 * Note: "local" indicates the real data's locality. So we can't
4517 * just its bucket locality by its length.
4518 */
4522 u32 name_hash,
4524 {
4540 else
4544 /*
4545 * If the new value will be stored outside, xi->value has been
4546 * initalized as an empty ocfs2_xattr_value_root, and the same
4547 * goes with xi->value_len, so we can set new_size safely here.
4548 * See ocfs2_xattr_set_in_bucket.
4549 */
4558 /* Now replace the old value with new one. */
4561 else
4576 /*
4577 * Remove the old entry if there is more than one.
4578 * We don't remove the last entry so that we can
4579 * use it to indicate the hash value of the empty
4580 * bucket.
4581 */
4594 }
4596 /* find a new entry for insert. */
4612 }
4613 }
4624 }
4626 set_new_name_value:
4627 /* Insert the new name+value. */
4630 /*
4631 * We must make sure that the name/value pair
4632 * exists in the same block.
4633 */
4641 }
4657 }
4659 /*
4660 * Set the xattr entry in the specified bucket.
4661 * The bucket is indicated by xs->bucket and it should have the enough
4662 * space for the xattr insertion.
4663 */
4668 u32 name_hash,
4670 {
4672 u64 blkno;
4685 }
4686 }
4689 OCFS2_JOURNAL_ACCESS_WRITE);
4693 }
4698 out:
4700 }
4702 /*
4703 * Truncate the specified xe_off entry in xattr bucket.
4704 * bucket is indicated by header_bh and len is the new length.
4705 * Both the ocfs2_xattr_value_root and the entry will be updated here.
4706 *
4707 * Copy the new updated xe and xe_value_root to new_xe and new_xv if needed.
4708 */
4714 {
4716 u64 value_blk;
4722 };
4733 /* We don't allow ocfs2_xattr_value to be stored in different block. */
4742 /*
4743 * From here on out we have to dirty the bucket. The generic
4744 * value calls only modify one of the bucket's bhs, but we need
4745 * to send the bucket at once. So if they error, they *could* have
4746 * modified something. We have to assume they did, and dirty
4747 * the whole bucket. This leaves us in a consistent state.
4748 */
4755 }
4758 OCFS2_JOURNAL_ACCESS_WRITE);
4762 }
4768 out:
4770 }
4776 {
4790 }
4797 {
4813 }
4823 out:
4825 }
4829 u64 blkno,
4830 u32 cpos,
4831 u32 len)
4832 {
4856 }
4865 }
4866 }
4873 }
4876 OCFS2_JOURNAL_ACCESS_WRITE);
4880 }
4887 }
4895 }
4901 out_commit:
4903 out:
4914 }
4919 {
4926 OCFS2_JOURNAL_ACCESS_WRITE);
4930 }
4932 /* Remove the old entry. */
4939 }
4941 /*
4942 * Set the xattr name/value in the bucket specified in xs.
4943 *
4944 * As the new value in xi may be stored in the bucket or in an outside cluster,
4945 * we divide the whole process into 3 steps:
4946 * 1. insert name/value in the bucket(ocfs2_xattr_set_entry_in_bucket)
4947 * 2. truncate of the outside cluster(ocfs2_xattr_bucket_value_truncate_xs)
4948 * 3. Set the value to the outside cluster(ocfs2_xattr_bucket_set_value_outside)
4949 * 4. If the clusters for the new outside value can't be allocated, we need
4950 * to free the xattr we allocated in set.
4951 */
4956 {
4965 /*
4966 * We need to truncate the xattr storage first.
4967 *
4968 * If both the old and new value are stored to
4969 * outside block, we only need to truncate
4970 * the storage and then set the value outside.
4971 *
4972 * If the new value should be stored within block,
4973 * we should free all the outside block first and
4974 * the modification to the xattr block will be done
4975 * by following steps.
4976 */
4979 else
4983 value_len,
4984 ctxt);
4990 }
4993 /* So we have to handle the inside block change now. */
4995 /*
4996 * If the new value will be stored outside of block,
4997 * initalize a new empty value root and insert it first.
4998 */
5002 }
5009 }
5014 /* allocate the space now for the outside block storage. */
5021 /*
5022 * We can't allocate enough clusters for outside
5023 * storage and we have allocated xattr already,
5024 * so need to remove it.
5025 */
5027 }
5029 }
5031 set_value_outside:
5034 out:
5036 }
5038 /*
5039 * check whether the xattr bucket is filled up with the same hash value.
5040 * If we want to insert the xattr with the same hash, return -ENOSPC.
5041 * If we want to insert a xattr with different hash value, go ahead
5042 * and ocfs2_divide_xattr_bucket will handle this.
5043 */
5047 {
5061 }
5064 }
5070 {
5081 try_again:
5093 header_size);
5106 /*
5107 * We only replace the old value if the new length is smaller
5108 * than the old one. Otherwise we will allocate new space in the
5109 * bucket to store it.
5110 */
5114 else
5119 }
5122 /*
5123 * We need to make sure the new name/value pair
5124 * can exist in the same block.
5125 */
5130 "need = %d, max_free = %d, xh_free_start = %u, xh_name_value_len ="
5141 /*
5142 * We can create the space by defragment. Since only the
5143 * name/value will be moved, the xe shouldn't be changed
5144 * in xs.
5145 */
5151 }
5163 "defragment. Need %u bytes, but we have %d, so "
5165 }
5167 /*
5168 * We have to add new buckets or clusters and one
5169 * allocation should leave us enough space for insert.
5170 */
5173 /*
5174 * We do not allow for overlapping ranges between buckets. And
5175 * the maximum number of collisions we will allow for then is
5176 * one bucket's worth, so check it here whether we need to
5177 * add a new bucket for the insert.
5178 */
5185 }
5190 ctxt);
5194 }
5196 /*
5197 * ocfs2_add_new_xattr_bucket() will have updated
5198 * xs->bucket if it moved, but it will not have updated
5199 * any of the other search fields. Thus, we drop it and
5200 * re-search. Everything should be cached, so it'll be
5201 * quick.
5202 */
5212 }
5214 xattr_set:
5216 out:
5219 }
5224 {
5227 u16 i;
5247 }
5256 }
5257 }
5262 }
5266 {
5272 u64 p_blkno;
5283 }
5286 ocfs2_delete_xattr_in_bucket,
5287 NULL);
5291 }
5298 }
5304 }
5306 out:
5308 }
5310 /*
5311 * 'security' attributes support
5312 */
5316 {
5324 }
5326 }
5330 {
5335 }
5339 {
5345 }
5350 {
5351 /* check whether ocfs2 support feature xattr */
5356 }
5364 {
5366 OCFS2_XATTR_INDEX_SECURITY,
5369 }
5376 };
5378 /*
5379 * 'trusted' attributes support
5380 */
5384 {
5392 }
5394 }
5398 {
5403 }
5407 {
5413 }
5420 };
5422 /*
5423 * 'user' attributes support
5424 */
5428 {
5440 }
5442 }
5446 {
5455 }
5459 {
5469 }
5476 };