| blob | ba320e250747fd01dedcd06a85df0d2e867dbe44 |
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 */
559 }
565 }
567 /*
568 * reserve credits and clusters for xattrs which has large value
569 * and have to be set outside
570 */
575 new_clusters);
577 }
580 /* for directory, it has DEFAULT and ACCESS two types of acls */
584 new_clusters);
586 }
589 }
592 u32 clusters_to_add,
595 {
608 OCFS2_JOURNAL_ACCESS_WRITE);
612 }
616 inode,
618 clusters_to_add,
621 handle,
628 }
634 }
638 /*
639 * We should have already allocated enough space before the transaction,
640 * so no need to restart.
641 */
644 leave:
647 }
653 {
662 OCFS2_JOURNAL_ACCESS_WRITE);
666 }
673 }
681 }
687 out:
689 }
692 u32 old_clusters,
693 u32 new_clusters,
696 {
699 u64 block;
713 }
720 ctxt);
724 }
728 alloc_size);
731 }
733 out:
735 }
741 {
753 else
759 }
764 {
771 /* we are just looking for how big our buffer needs to be */
783 }
788 {
807 }
808 }
811 }
817 {
832 }
838 {
851 }
862 }
867 }
872 {
888 }
900 }
905 }
912 }
917 {
934 name_len);
938 }
942 }
948 {
950 u64 blkno;
968 }
971 /* Copy ocfs2_xattr_value */
977 }
988 }
990 }
991 out:
993 }
1001 {
1038 }
1039 }
1040 }
1043 }
1051 {
1062 }
1068 }
1073 }
1089 i,
1093 }
1105 }
1106 }
1107 }
1109 cleanup:
1115 }
1123 {
1129 };
1132 };
1152 }
1154 /* ocfs2_xattr_get()
1155 *
1156 * Copy an extended attribute into the buffer provided.
1157 * Buffer is NULL to compute the size of buffer required.
1158 */
1164 {
1172 }
1181 }
1188 {
1194 u64 blkno;
1205 }
1214 }
1217 inode,
1218 bh,
1219 OCFS2_JOURNAL_ACCESS_WRITE);
1223 }
1237 }
1241 /*
1242 * XXX: do we need to empty all the following
1243 * blocks in this cluster?
1244 */
1247 }
1249 }
1250 out:
1254 }
1262 {
1269 OCFS2_JOURNAL_ACCESS_WRITE);
1273 }
1274 /* Decrease xattr count */
1276 /* Remove the xattr entry and tree root which has already be set*/
1283 out:
1285 }
1293 {
1297 OCFS2_JOURNAL_ACCESS_WRITE);
1301 }
1307 else
1314 out:
1316 }
1318 /*
1319 * ocfs2_xattr_set_value_outside()
1320 *
1321 * Set large size value in B tree.
1322 */
1329 {
1351 }
1356 }
1363 }
1365 /*
1366 * ocfs2_xattr_set_entry_local()
1367 *
1368 * Set, replace or remove extended attribute in local.
1369 */
1375 {
1380 /* Insert the new xattr entry. */
1395 OCFS2_XATTR_INLINE_SIZE)
1397 OCFS2_XATTR_ROOT_SIZE;
1398 else
1404 /* The old and the new value have the
1405 same size. Just replace the value. */
1408 /* Clear value bytes. */
1416 }
1417 /* Remove the old name+value. */
1427 /* Adjust all value offsets. */
1435 }
1438 /* Remove the old entry. */
1444 }
1445 }
1447 /* Insert the new name+value. */
1461 }
1464 }
1466 /*
1467 * ocfs2_xattr_set_entry()
1468 *
1469 * Set extended attribute entry into inode or block.
1470 *
1471 * If extended attribute value size > OCFS2_XATTR_INLINE_SIZE,
1472 * We first insert tree root(ocfs2_xattr_value_root) with set_entry_local(),
1473 * then set value in B tree with set_value_outside().
1474 */
1480 {
1493 };
1497 };
1505 /* Compute min_offs, last and free space. */
1513 }
1524 else
1526 OCFS2_XATTR_ROOT_SIZE;
1528 }
1529 /* Check free space in inode or block */
1533 OCFS2_XATTR_ROOT_SIZE) {
1536 }
1546 }
1547 }
1550 /* For existing extended attribute */
1557 /* Replace existing local xattr with tree root */
1564 /* For existing xattr which has value outside */
1569 /*
1570 * If new value need set outside also,
1571 * first truncate old value to new value,
1572 * then set new value with set_value_outside().
1573 */
1577 ctxt);
1581 }
1584 handle,
1585 xi,
1586 xs,
1588 offs);
1592 }
1595 handle,
1603 /*
1604 * If new value need set in local,
1605 * just trucate old value to zero.
1606 */
1610 ctxt);
1613 }
1614 }
1615 }
1618 OCFS2_JOURNAL_ACCESS_WRITE);
1622 }
1626 OCFS2_JOURNAL_ACCESS_WRITE);
1630 }
1631 }
1633 /*
1634 * Set value in local, include set tree root in local.
1635 * This is the first step for value size >INLINE_SIZE.
1636 */
1644 }
1645 }
1652 /*
1653 * Adjust extent record count or inline data size
1654 * to reserve space for extended attribute.
1655 */
1663 }
1665 }
1666 /* Update xattr flag */
1677 /*
1678 * Set value outside in B tree.
1679 * This is the second step for value size > INLINE_SIZE.
1680 */
1688 /*
1689 * If set value outside failed, we have to clean
1690 * the junk tree root we have already set in local.
1691 */
1696 }
1697 }
1698 out:
1700 }
1705 {
1718 }
1734 }
1735 }
1736 }
1741 out:
1743 }
1747 {
1755 };
1764 }
1768 {
1774 };
1784 }
1787 u64 block)
1788 {
1797 u16 bit;
1803 }
1809 }
1817 EXTENT_ALLOC_SYSTEM_INODE,
1823 }
1830 }
1837 }
1845 out_unlock:
1848 out_mutex:
1851 out:
1854 }
1856 /*
1857 * ocfs2_xattr_remove()
1858 *
1859 * Free extended attribute resources associated with this inode.
1860 */
1862 {
1879 }
1880 }
1888 }
1889 }
1892 OCFS2_INODE_UPDATE_CREDITS);
1897 }
1899 OCFS2_JOURNAL_ACCESS_WRITE);
1903 }
1915 out_commit:
1917 out:
1919 }
1923 {
1942 }
1947 }
1949 /*
1950 * ocfs2_xattr_ibody_find()
1951 *
1952 * Find extended attribute in inode block and
1953 * fill search info into struct ocfs2_xattr_search.
1954 */
1959 {
1974 }
1981 else
1987 /* Find the named attribute. */
1993 }
1996 }
1998 /*
1999 * ocfs2_xattr_ibody_set()
2000 *
2001 * Set, replace or remove an extended attribute into inode block.
2002 *
2003 */
2008 {
2021 }
2022 }
2026 out:
2030 }
2032 /*
2033 * ocfs2_xattr_block_find()
2034 *
2035 * Find extended attribute in external block and
2036 * fill search info into struct ocfs2_xattr_search.
2037 */
2042 {
2056 }
2070 name_index,
2076 }
2079 cleanup:
2083 }
2085 /*
2086 * ocfs2_xattr_block_set()
2087 *
2088 * Set, replace or remove an extended attribute into external block.
2089 *
2090 */
2095 {
2101 u16 suballoc_bit_start;
2102 u32 num_got;
2103 u64 first_blkno;
2108 OCFS2_JOURNAL_ACCESS_CREATE);
2112 }
2120 }
2126 OCFS2_JOURNAL_ACCESS_CREATE);
2130 }
2132 /* Initialize ocfs2_xattr_block */
2151 }
2158 /* Set extended attribute into external block */
2160 OCFS2_HAS_XATTR_FL);
2167 }
2171 end:
2174 }
2176 /* Check whether the new xattr can be inserted into the inode. */
2180 {
2181 u64 value_size;
2196 }
2206 else
2214 }
2224 {
2235 u64 value_size;
2237 /*
2238 * Calculate the clusters we need to write.
2239 * No matter whether we replace an old one or add a new one,
2240 * we need this for writing.
2241 */
2253 new_clusters);
2254 }
2257 }
2284 }
2285 }
2287 /*
2288 * delete a xattr doesn't need metadata and cluster allocation.
2289 * so just calculate the credits and return.
2290 *
2291 * The credits for removing the value tree will be extended
2292 * by ocfs2_remove_extent itself.
2293 */
2299 }
2301 /* do cluster allocation guess first. */
2305 /*
2306 * In xattr set, we always try to set the xe in inode first,
2307 * so if it can be inserted into inode successfully, the old
2308 * one will be removed from the xattr block, and this xattr
2309 * will be inserted into inode as a new xattr in inode.
2310 */
2314 OCFS2_INODE_UPDATE_CREDITS;
2319 new_clusters);
2321 }
2322 }
2325 /* the new values will be stored outside. */
2330 value_size);
2345 new_clusters -
2346 old_clusters);
2349 }
2351 /*
2352 * Now the new value will be stored inside. So if the new
2353 * value is smaller than the size of value root or the old
2354 * value, we don't need any allocation, otherwise we have
2355 * to guess metadata allocation.
2356 */
2361 }
2363 meta_guess:
2364 /* calculate metadata allocation. */
2373 }
2379 /*
2380 * If there is already an xattr tree, good, we can calculate
2381 * like other b-trees. Otherwise we may have the chance of
2382 * create a tree, the credit calculation is borrowed from
2383 * ocfs2_calc_extend_credits with root_el = NULL. And the
2384 * new tree will be cluster based, so no meta is needed.
2385 */
2395 /*
2396 * This cluster will be used either for new bucket or for
2397 * new xattr block.
2398 * If the cluster size is the same as the bucket size, one
2399 * more is needed since we may need to extend the bucket
2400 * also.
2401 */
2408 }
2412 }
2413 out:
2422 }
2431 {
2444 }
2455 }
2456 }
2462 }
2463 out:
2468 }
2470 /*
2471 * We cannot have an error and a non null ctxt->data_ac.
2472 */
2473 }
2476 }
2484 {
2488 /* Remove existing extended attribute */
2494 /* We always try to set extended attribute into inode first*/
2497 /*
2498 * If succeed and that extended attribute existing in
2499 * external block, then we will remove it.
2500 */
2507 di,
2508 xi,
2509 xis,
2510 xbs,
2511 NULL,
2512 NULL,
2518 }
2525 }
2538 di,
2539 xi,
2540 xis,
2541 xbs,
2542 NULL,
2543 NULL,
2549 }
2556 }
2557 }
2558 /*
2559 * If no space in inode, we will set extended attribute
2560 * into external block.
2561 */
2566 /*
2567 * If succeed and that extended attribute
2568 * existing in inode, we will remove it.
2569 */
2574 di,
2575 xi,
2576 xis,
2577 xbs,
2578 NULL,
2579 NULL,
2584 }
2591 }
2594 }
2595 }
2596 }
2599 /* Update inode ctime. */
2602 OCFS2_JOURNAL_ACCESS_WRITE);
2606 }
2612 }
2613 out:
2615 }
2617 /*
2618 * This function only called duing creating inode
2619 * for init security/acl xattrs of the new inode.
2620 * All transanction credits have been reserved in mknod.
2621 */
2632 {
2641 };
2645 };
2649 };
2655 };
2660 /*
2661 * In extreme situation, may need xattr bucket when
2662 * block size is too small. And we have already reserved
2663 * the credits for bucket in mknod.
2664 */
2670 }
2671 }
2685 }
2689 cleanup:
2695 }
2697 /*
2698 * ocfs2_xattr_set()
2699 *
2700 * Set, replace or remove an extended attribute for this inode.
2701 * value is NULL to remove an existing extended attribute, else either
2702 * create or replace an extended attribute.
2703 */
2710 {
2723 };
2727 };
2731 };
2736 /*
2737 * Only xbs will be used on indexed trees. xis doesn't need a
2738 * bucket.
2739 */
2744 }
2750 }
2755 /*
2756 * Scan inode and external block to find the same name
2757 * extended attribute and collect search infomation.
2758 */
2766 }
2779 }
2790 }
2791 }
2799 }
2801 /* we need to update inode's ctime field, so add credit for it. */
2808 }
2821 cleanup:
2824 cleanup_nolock:
2830 }
2832 /*
2833 * Find the xattr extent rec which may contains name_hash.
2834 * e_cpos will be the first name hash of the xattr rec.
2835 * el must be the ocfs2_xattr_header.xb_attrs.xb_root.xt_list.
2836 */
2838 u32 name_hash,
2843 {
2855 }
2862 "Inode %lu has non zero tree depth in "
2867 }
2868 }
2876 }
2877 }
2886 }
2892 out:
2895 }
2905 u32 name_hash,
2908 {
2915 /*
2916 * We don't use binary search in the bucket because there
2917 * may be multiple entries with the same name hash.
2918 */
2934 xh,
2935 i,
2941 }
2950 }
2951 }
2954 }
2956 /*
2957 * Find the specified xattr entry in a series of buckets.
2958 * This series start from p_blkno and last for num_clusters.
2959 * The ocfs2_xattr_header.xh_num_buckets of the first bucket contains
2960 * the num of the valid buckets.
2961 *
2962 * Return the buffer_head this xattr should reside in. And if the xattr's
2963 * hash is in the gap of 2 buckets, return the lower bucket.
2964 */
2968 u32 name_hash,
2969 u64 p_blkno,
2970 u32 first_hash,
2971 u32 num_clusters,
2973 {
2981 u32 last_hash;
2989 }
2995 }
3008 }
3015 }
3017 /*
3018 * Check whether the hash of the last entry in our
3019 * bucket is larger than the search one. for an empty
3020 * bucket, the last one is also the first one.
3021 */
3027 /* record lower_blkno which may be the insert place. */
3033 }
3035 /* the searched xattr should reside in this bucket if exists. */
3042 }
3044 }
3046 /*
3047 * Record the bucket we have found.
3048 * When the xattr's hash value is in the gap of 2 buckets, we will
3049 * always set it to the previous bucket.
3050 */
3054 /* This should be in cache - we just read it during the search */
3059 }
3072 out:
3075 }
3082 {
3103 }
3109 first_hash);
3114 out:
3116 }
3119 u64 blkno,
3120 u32 clusters,
3123 {
3133 }
3143 }
3145 /*
3146 * The real bucket num in this series of blocks is stored
3147 * in the 1st bucket.
3148 */
3159 /* Fall through to bucket_relse() */
3160 }
3165 }
3169 }
3175 };
3182 {
3183 u16 name_offset;
3194 }
3199 {
3213 i,
3220 new_offset;
3228 }
3229 }
3232 }
3238 {
3247 };
3258 }
3261 ocfs2_list_xattr_bucket,
3267 }
3273 }
3276 out:
3278 }
3281 {
3291 }
3294 {
3300 }
3302 /*
3303 * When the ocfs2_xattr_block is filled up, new bucket will be created
3304 * and all the xattr entries will be moved to the new bucket.
3305 * The header goes at the start of the bucket, and the names+values are
3306 * filled from the end. This is why *target starts as the last buffer.
3307 * Note: we need to sort the entries since they are not saved in order
3308 * in the ocfs2_xattr_block.
3309 */
3313 {
3333 /*
3334 * Since the xe_name_offset is based on ocfs2_xattr_header,
3335 * there is a offset change corresponding to the change of
3336 * ocfs2_xattr_header's position.
3337 */
3343 /* copy all the names and values. */
3346 /* Init new header now. */
3352 /* copy all the entries. */
3358 /* Change the xe offset for all the xe because of the move. */
3369 }
3371 /*
3372 * After we move xattr from block to index btree, we have to
3373 * update ocfs2_xattr_search to the new xe and base.
3374 *
3375 * When the entry is in xattr block, xattr_bh indicates the storage place.
3376 * While if the entry is in index b-tree, "bucket" indicates the
3377 * real place of the xattr.
3378 */
3382 {
3397 }
3402 {
3405 u64 blkno;
3421 /*
3422 * XXX:
3423 * We can use this lock for now, and maybe move to a dedicated mutex
3424 * if performance becomes a problem later.
3425 */
3429 OCFS2_JOURNAL_ACCESS_WRITE);
3433 }
3440 }
3442 /*
3443 * The bucket may spread in many blocks, and
3444 * we will only touch the 1st block and the last block
3445 * in the whole bucket(one for entry and one for data).
3446 */
3456 }
3459 OCFS2_JOURNAL_ACCESS_CREATE);
3463 }
3470 /* Change from ocfs2_xattr_header to ocfs2_xattr_tree_root */
3489 out:
3493 }
3496 {
3506 }
3508 /*
3509 * defrag a xattr bucket if we find that the bucket has some
3510 * holes beteen name/value pairs.
3511 * We will move all the name/value pairs to the end of the bucket
3512 * so that we can spare some space for insertion.
3513 */
3517 {
3523 u16 xh_free_start;
3527 /*
3528 * In order to make the operation more efficient and generic,
3529 * we copy all the blocks into a contiguous memory and do the
3530 * defragment there, so if anything is error, we will not touch
3531 * the real block.
3532 */
3537 }
3544 OCFS2_JOURNAL_ACCESS_WRITE);
3548 }
3559 /*
3560 * sort all the entries by their offset.
3561 * the largest will be the first, so that we can
3562 * move them to the end one by one.
3563 */
3568 /* Move all name/values to the end of the bucket. */
3576 else
3580 /*
3581 * We must make sure that the name/value pair
3582 * exist in the same block. So adjust end to
3583 * the previous block end if needed.
3584 */
3593 }
3599 }
3610 /* sort the entries by their name_hash. */
3620 out:
3623 }
3625 /*
3626 * prev_blkno points to the start of an existing extent. new_blkno
3627 * points to a newly allocated extent. Because we know each of our
3628 * clusters contains more than bucket, we can easily split one cluster
3629 * at a bucket boundary. So we take the last cluster of the existing
3630 * extent and split it down the middle. We move the last half of the
3631 * buckets in the last cluster of the existing extent over to the new
3632 * extent.
3633 *
3634 * first_bh is the buffer at prev_blkno so we can update the existing
3635 * extent's bucket count. header_bh is the bucket were we were hoping
3636 * to insert our xattr. If the bucket move places the target in the new
3637 * extent, we'll update first_bh and header_bh after modifying the old
3638 * extent.
3639 *
3640 * first_hash will be set as the 1st xe's name_hash in the new extent.
3641 */
3646 u64 new_blkno,
3647 u32 num_clusters,
3649 {
3655 u64 src_blkno;
3671 }
3673 /* This is the first bucket that got moved */
3676 /*
3677 * If the target bucket was part of the moved buckets, we need to
3678 * update first and target.
3679 */
3681 /* Find the block for the new target bucket */
3688 /*
3689 * These shouldn't fail - the buffers are in the
3690 * journal from ocfs2_cp_xattr_bucket().
3691 */
3696 }
3701 }
3703 out:
3705 }
3707 /*
3708 * Find the suitable pos when we divide a bucket into 2.
3709 * We have to make sure the xattrs with the same hash value exist
3710 * in the same bucket.
3711 *
3712 * If this ocfs2_xattr_header covers more than one hash value, find a
3713 * place where the hash value changes. Try to find the most even split.
3714 * The most common case is that all entries have different hash values,
3715 * and the first check we make will find a place to split.
3716 */
3718 {
3723 /*
3724 * We start at the middle. Each step gets farther away in both
3725 * directions. We therefore hit the change in hash value
3726 * nearest to the middle. Note that this loop does not execute for
3727 * count < 2.
3728 */
3730 /* Let's check delta earlier than middle */
3735 /* For even counts, don't walk off the end */
3739 /* Now try delta past middle */
3743 }
3745 /* Every entry had the same hash */
3747 }
3749 /*
3750 * Move some xattrs in old bucket(blk) to new bucket(new_blk).
3751 * first_hash will record the 1st hash of the new bucket.
3752 *
3753 * Normally half of the xattrs will be moved. But we have to make
3754 * sure that the xattrs with the same hash value are stored in the
3755 * same bucket. If all the xattrs in this bucket have the same hash
3756 * value, the new bucket will be initialized as an empty one and the
3757 * first_hash will be initialized as (hash_value+1).
3758 */
3761 u64 blk,
3762 u64 new_blk,
3765 {
3782 }
3788 }
3791 OCFS2_JOURNAL_ACCESS_WRITE);
3795 }
3797 /*
3798 * Even if !new_bucket_head, we're overwriting t_bucket. Thus,
3799 * there's no need to read it.
3800 */
3805 }
3807 /*
3808 * Hey, if we're overwriting t_bucket, what difference does
3809 * ACCESS_CREATE vs ACCESS_WRITE make? See the comment in the
3810 * same part of ocfs2_cp_xattr_bucket().
3811 */
3813 new_bucket_head ?
3814 OCFS2_JOURNAL_ACCESS_CREATE :
3815 OCFS2_JOURNAL_ACCESS_WRITE);
3819 }
3828 /*
3829 * initialized a new empty bucket here.
3830 * The hash value is set as one larger than
3831 * that of the last entry in the previous bucket.
3832 */
3842 }
3844 /* copy the whole bucket to the new first. */
3847 /* update the new bucket. */
3850 /*
3851 * Calculate the total name/value len and xh_free_start for
3852 * the old bucket first.
3853 */
3860 xe_len +=
3862 else
3867 }
3869 /*
3870 * Now begin the modification to the new bucket.
3871 *
3872 * In the new bucket, We just move the xattr entry to the beginning
3873 * and don't touch the name/value. So there will be some holes in the
3874 * bucket, and they will be removed when ocfs2_defrag_xattr_bucket is
3875 * called.
3876 */
3890 /* Calculate xh_free_start for the new bucket. */
3896 xe_len +=
3898 else
3903 }
3905 set_num_buckets:
3906 /* set xh->xh_num_buckets for the new xh. */
3909 else
3914 /* store the first_hash of the new bucket. */
3918 /*
3919 * Now only update the 1st block of the old bucket. If we
3920 * just added a new empty bucket, there is no need to modify
3921 * it.
3922 */
3935 out:
3940 }
3942 /*
3943 * Copy xattr from one bucket to another bucket.
3944 *
3945 * The caller must make sure that the journal transaction
3946 * has enough space for journaling.
3947 */
3950 u64 s_blkno,
3951 u64 t_blkno,
3953 {
3961 t_is_new);
3969 }
3975 /*
3976 * Even if !t_is_new, we're overwriting t_bucket. Thus,
3977 * there's no need to read it.
3978 */
3983 /*
3984 * Hey, if we're overwriting t_bucket, what difference does
3985 * ACCESS_CREATE vs ACCESS_WRITE make? Well, if we allocated a new
3986 * cluster to fill, we came here from
3987 * ocfs2_mv_xattr_buckets(), and it is really new -
3988 * ACCESS_CREATE is required. But we also might have moved data
3989 * out of t_bucket before extending back into it.
3990 * ocfs2_add_new_xattr_bucket() can do this - its call to
3991 * ocfs2_add_new_xattr_cluster() may have created a new extent
3992 * and copied out the end of the old extent. Then it re-extends
3993 * the old extent back to create space for new xattrs. That's
3994 * how we get here, and the bucket isn't really new.
3995 */
3997 t_is_new ?
3998 OCFS2_JOURNAL_ACCESS_CREATE :
3999 OCFS2_JOURNAL_ACCESS_WRITE);
4006 out:
4011 }
4013 /*
4014 * src_blk points to the start of an existing extent. last_blk points to
4015 * last cluster in that extent. to_blk points to a newly allocated
4016 * extent. We copy the buckets from the cluster at last_blk to the new
4017 * extent. If start_bucket is non-zero, we skip that many buckets before
4018 * we start copying. The new extent's xh_num_buckets gets set to the
4019 * number of buckets we copied. The old extent's xh_num_buckets shrinks
4020 * by the same amount.
4021 */
4026 {
4040 }
4042 /* The first bucket of the original extent */
4044 /* The first bucket of the new extent */
4050 }
4056 }
4058 /*
4059 * We need to update the first bucket of the old extent and all
4060 * the buckets going to the new extent.
4061 */
4068 }
4071 OCFS2_JOURNAL_ACCESS_WRITE);
4075 }
4085 }
4086 }
4088 /*
4089 * Get the new bucket ready before we dirty anything
4090 * (This actually shouldn't fail, because we already dirtied
4091 * it once in ocfs2_cp_xattr_bucket()).
4092 */
4097 }
4099 OCFS2_JOURNAL_ACCESS_WRITE);
4103 }
4105 /* Now update the headers */
4115 out:
4119 }
4121 /*
4122 * Move some xattrs in this cluster to the new cluster.
4123 * This function should only be called when bucket size == cluster size.
4124 * Otherwise ocfs2_mv_xattr_bucket_cross_cluster should be used instead.
4125 */
4128 u64 prev_blk,
4129 u64 new_blk,
4131 {
4141 }
4143 /* Move half of the xattr in start_blk to the next bucket. */
4146 }
4148 /*
4149 * Move some xattrs from the old cluster to the new one since they are not
4150 * contiguous in ocfs2 xattr tree.
4151 *
4152 * new_blk starts a new separate cluster, and we will move some xattrs from
4153 * prev_blk to it. v_start will be set as the first name hash value in this
4154 * new cluster so that it can be used as e_cpos during tree insertion and
4155 * don't collide with our original b-tree operations. first_bh and header_bh
4156 * will also be updated since they will be used in ocfs2_extend_xattr_bucket
4157 * to extend the insert bucket.
4158 *
4159 * The problem is how much xattr should we move to the new one and when should
4160 * we update first_bh and header_bh?
4161 * 1. If cluster size > bucket size, that means the previous cluster has more
4162 * than 1 bucket, so just move half nums of bucket into the new cluster and
4163 * update the first_bh and header_bh if the insert bucket has been moved
4164 * to the new cluster.
4165 * 2. If cluster_size == bucket_size:
4166 * a) If the previous extent rec has more than one cluster and the insert
4167 * place isn't in the last cluster, copy the entire last cluster to the
4168 * new one. This time, we don't need to upate the first_bh and header_bh
4169 * since they will not be moved into the new cluster.
4170 * b) Otherwise, move the bottom half of the xattrs in the last cluster into
4171 * the new one. And we set the extend flag to zero if the insert place is
4172 * moved into the new allocated cluster since no extend is needed.
4173 */
4178 u64 new_blk,
4179 u32 prev_clusters,
4182 {
4191 handle,
4193 new_blk,
4194 prev_clusters,
4195 v_start);
4199 /* The start of the last cluster in the first extent */
4208 v_start);
4214 v_start);
4220 }
4221 }
4224 }
4226 /*
4227 * Add a new cluster for xattr storage.
4228 *
4229 * If the new cluster is contiguous with the previous one, it will be
4230 * appended to the same extent record, and num_clusters will be updated.
4231 * If not, we will insert a new extent for it and move some xattrs in
4232 * the last cluster into the new allocated one.
4233 * We also need to limit the maximum size of a btree leaf, otherwise we'll
4234 * lose the benefits of hashing because we'll have to search large leaves.
4235 * So now the maximum size is OCFS2_MAX_XATTR_TREE_LEAF_SIZE(or clustersize,
4236 * if it's bigger).
4237 *
4238 * first_bh is the first block of the previous extent rec and header_bh
4239 * indicates the bucket we will insert the new xattrs. They will be updated
4240 * when the header_bh is moved into the new cluster.
4241 */
4247 u32 prev_cpos,
4250 {
4255 u64 block;
4268 OCFS2_JOURNAL_ACCESS_WRITE);
4272 }
4280 }
4290 OCFS2_MAX_XATTR_TREE_LEAF_SIZE) {
4291 /*
4292 * If this cluster is contiguous with the old one and
4293 * adding this new cluster, we don't surpass the limit of
4294 * OCFS2_MAX_XATTR_TREE_LEAF_SIZE, cool. We will let it be
4295 * initialized and used like other buckets in the previous
4296 * cluster.
4297 * So add it as a contiguous one. The caller will handle
4298 * its init process.
4299 */
4303 num_bits);
4306 handle,
4307 first,
4308 target,
4309 block,
4310 prev_clusters,
4312 extend);
4316 }
4317 }
4326 }
4332 leave:
4334 }
4336 /*
4337 * We are given an extent. 'first' is the bucket at the very front of
4338 * the extent. The extent has space for an additional bucket past
4339 * bucket_xh(first)->xh_num_buckets. 'target_blkno' is the block number
4340 * of the target bucket. We wish to shift every bucket past the target
4341 * down one, filling in that additional space. When we get back to the
4342 * target, we split the target between itself and the now-empty bucket
4343 * at target+1 (aka, target_blkno + blks_per_bucket).
4344 */
4348 u64 target_blk,
4349 u32 num_clusters)
4350 {
4354 u64 end_blk;
4361 /* The extent must have room for an additional bucket */
4365 /* end_blk points to the last existing bucket */
4368 /*
4369 * end_blk is the start of the last existing bucket.
4370 * Thus, (end_blk - target_blk) covers the target bucket and
4371 * every bucket after it up to, but not including, the last
4372 * existing bucket. Then we add the last existing bucket, the
4373 * new bucket, and the first bucket (3 * blk_per_bucket).
4374 */
4381 }
4384 OCFS2_JOURNAL_ACCESS_WRITE);
4388 }
4396 }
4398 /* Move half of the xattr in target_blkno to the next bucket. */
4405 out:
4407 }
4409 /*
4410 * Add new xattr bucket in an extent record and adjust the buckets
4411 * accordingly. xb_bh is the ocfs2_xattr_block, and target is the
4412 * bucket we want to insert into.
4413 *
4414 * In the easy case, we will move all the buckets after target down by
4415 * one. Half of target's xattrs will be moved to the next bucket.
4416 *
4417 * If current cluster is full, we'll allocate a new one. This may not
4418 * be contiguous. The underlying calls will make sure that there is
4419 * space for the insert, shifting buckets around if necessary.
4420 * 'target' may be moved by those calls.
4421 */
4426 {
4431 u32 name_hash =
4435 u64 p_blkno;
4437 /* The bucket at the front of the extent */
4443 /* The first bucket of the original extent */
4449 }
4456 }
4462 }
4466 /*
4467 * This can move first+target if the target bucket moves
4468 * to the new extent.
4469 */
4471 xb_bh,
4472 first,
4473 target,
4475 e_cpos,
4477 ctxt);
4481 }
4482 }
4487 first,
4489 num_clusters);
4492 }
4494 out:
4498 }
4503 {
4508 }
4510 /*
4511 * Handle the normal xattr set, including replace, delete and new.
4512 *
4513 * Note: "local" indicates the real data's locality. So we can't
4514 * just its bucket locality by its length.
4515 */
4519 u32 name_hash,
4521 {
4537 else
4541 /*
4542 * If the new value will be stored outside, xi->value has been
4543 * initalized as an empty ocfs2_xattr_value_root, and the same
4544 * goes with xi->value_len, so we can set new_size safely here.
4545 * See ocfs2_xattr_set_in_bucket.
4546 */
4555 /* Now replace the old value with new one. */
4558 else
4573 /*
4574 * Remove the old entry if there is more than one.
4575 * We don't remove the last entry so that we can
4576 * use it to indicate the hash value of the empty
4577 * bucket.
4578 */
4591 }
4593 /* find a new entry for insert. */
4609 }
4610 }
4621 }
4623 set_new_name_value:
4624 /* Insert the new name+value. */
4627 /*
4628 * We must make sure that the name/value pair
4629 * exists in the same block.
4630 */
4638 }
4654 }
4656 /*
4657 * Set the xattr entry in the specified bucket.
4658 * The bucket is indicated by xs->bucket and it should have the enough
4659 * space for the xattr insertion.
4660 */
4665 u32 name_hash,
4667 {
4669 u64 blkno;
4682 }
4683 }
4686 OCFS2_JOURNAL_ACCESS_WRITE);
4690 }
4695 out:
4697 }
4699 /*
4700 * Truncate the specified xe_off entry in xattr bucket.
4701 * bucket is indicated by header_bh and len is the new length.
4702 * Both the ocfs2_xattr_value_root and the entry will be updated here.
4703 *
4704 * Copy the new updated xe and xe_value_root to new_xe and new_xv if needed.
4705 */
4711 {
4713 u64 value_blk;
4719 };
4730 /* We don't allow ocfs2_xattr_value to be stored in different block. */
4739 /*
4740 * From here on out we have to dirty the bucket. The generic
4741 * value calls only modify one of the bucket's bhs, but we need
4742 * to send the bucket at once. So if they error, they *could* have
4743 * modified something. We have to assume they did, and dirty
4744 * the whole bucket. This leaves us in a consistent state.
4745 */
4752 }
4755 OCFS2_JOURNAL_ACCESS_WRITE);
4759 }
4765 out:
4767 }
4773 {
4787 }
4794 {
4810 }
4820 out:
4822 }
4826 u64 blkno,
4827 u32 cpos,
4828 u32 len)
4829 {
4853 }
4862 }
4863 }
4870 }
4873 OCFS2_JOURNAL_ACCESS_WRITE);
4877 }
4884 }
4892 }
4898 out_commit:
4900 out:
4911 }
4916 {
4923 OCFS2_JOURNAL_ACCESS_WRITE);
4927 }
4929 /* Remove the old entry. */
4936 }
4938 /*
4939 * Set the xattr name/value in the bucket specified in xs.
4940 *
4941 * As the new value in xi may be stored in the bucket or in an outside cluster,
4942 * we divide the whole process into 3 steps:
4943 * 1. insert name/value in the bucket(ocfs2_xattr_set_entry_in_bucket)
4944 * 2. truncate of the outside cluster(ocfs2_xattr_bucket_value_truncate_xs)
4945 * 3. Set the value to the outside cluster(ocfs2_xattr_bucket_set_value_outside)
4946 * 4. If the clusters for the new outside value can't be allocated, we need
4947 * to free the xattr we allocated in set.
4948 */
4953 {
4962 /*
4963 * We need to truncate the xattr storage first.
4964 *
4965 * If both the old and new value are stored to
4966 * outside block, we only need to truncate
4967 * the storage and then set the value outside.
4968 *
4969 * If the new value should be stored within block,
4970 * we should free all the outside block first and
4971 * the modification to the xattr block will be done
4972 * by following steps.
4973 */
4976 else
4980 value_len,
4981 ctxt);
4987 }
4990 /* So we have to handle the inside block change now. */
4992 /*
4993 * If the new value will be stored outside of block,
4994 * initalize a new empty value root and insert it first.
4995 */
4999 }
5006 }
5011 /* allocate the space now for the outside block storage. */
5018 /*
5019 * We can't allocate enough clusters for outside
5020 * storage and we have allocated xattr already,
5021 * so need to remove it.
5022 */
5024 }
5026 }
5028 set_value_outside:
5031 out:
5033 }
5035 /*
5036 * check whether the xattr bucket is filled up with the same hash value.
5037 * If we want to insert the xattr with the same hash, return -ENOSPC.
5038 * If we want to insert a xattr with different hash value, go ahead
5039 * and ocfs2_divide_xattr_bucket will handle this.
5040 */
5044 {
5058 }
5061 }
5067 {
5078 try_again:
5090 header_size);
5103 /*
5104 * We only replace the old value if the new length is smaller
5105 * than the old one. Otherwise we will allocate new space in the
5106 * bucket to store it.
5107 */
5111 else
5116 }
5119 /*
5120 * We need to make sure the new name/value pair
5121 * can exist in the same block.
5122 */
5127 "need = %d, max_free = %d, xh_free_start = %u, xh_name_value_len ="
5138 /*
5139 * We can create the space by defragment. Since only the
5140 * name/value will be moved, the xe shouldn't be changed
5141 * in xs.
5142 */
5148 }
5160 "defragment. Need %u bytes, but we have %d, so "
5162 }
5164 /*
5165 * We have to add new buckets or clusters and one
5166 * allocation should leave us enough space for insert.
5167 */
5170 /*
5171 * We do not allow for overlapping ranges between buckets. And
5172 * the maximum number of collisions we will allow for then is
5173 * one bucket's worth, so check it here whether we need to
5174 * add a new bucket for the insert.
5175 */
5182 }
5187 ctxt);
5191 }
5193 /*
5194 * ocfs2_add_new_xattr_bucket() will have updated
5195 * xs->bucket if it moved, but it will not have updated
5196 * any of the other search fields. Thus, we drop it and
5197 * re-search. Everything should be cached, so it'll be
5198 * quick.
5199 */
5209 }
5211 xattr_set:
5213 out:
5216 }
5221 {
5224 u16 i;
5244 }
5253 }
5254 }
5259 }
5263 {
5269 u64 p_blkno;
5280 }
5283 ocfs2_delete_xattr_in_bucket,
5284 NULL);
5288 }
5295 }
5301 }
5303 out:
5305 }
5307 /*
5308 * 'security' attributes support
5309 */
5313 {
5321 }
5323 }
5327 {
5332 }
5336 {
5342 }
5347 {
5348 /* check whether ocfs2 support feature xattr */
5353 }
5361 {
5363 OCFS2_XATTR_INDEX_SECURITY,
5366 }
5373 };
5375 /*
5376 * 'trusted' attributes support
5377 */
5381 {
5389 }
5391 }
5395 {
5400 }
5404 {
5410 }
5417 };
5419 /*
5420 * 'user' attributes support
5421 */
5425 {
5437 }
5439 }
5443 {
5452 }
5456 {
5466 }
5473 };