| blob | d1a27cda984f10811fb66fe7a7a53e76f6036d34 |
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 {
1063 }
1069 }
1074 }
1090 i,
1094 }
1106 }
1107 }
1108 }
1110 cleanup:
1116 }
1124 {
1130 };
1133 };
1153 }
1155 /* ocfs2_xattr_get()
1156 *
1157 * Copy an extended attribute into the buffer provided.
1158 * Buffer is NULL to compute the size of buffer required.
1159 */
1165 {
1173 }
1182 }
1189 {
1195 u64 blkno;
1206 }
1215 }
1218 inode,
1219 bh,
1220 OCFS2_JOURNAL_ACCESS_WRITE);
1224 }
1238 }
1242 /*
1243 * XXX: do we need to empty all the following
1244 * blocks in this cluster?
1245 */
1248 }
1250 }
1251 out:
1255 }
1263 {
1270 OCFS2_JOURNAL_ACCESS_WRITE);
1274 }
1275 /* Decrease xattr count */
1277 /* Remove the xattr entry and tree root which has already be set*/
1284 out:
1286 }
1294 {
1298 OCFS2_JOURNAL_ACCESS_WRITE);
1302 }
1308 else
1315 out:
1317 }
1319 /*
1320 * ocfs2_xattr_set_value_outside()
1321 *
1322 * Set large size value in B tree.
1323 */
1330 {
1352 }
1357 }
1364 }
1366 /*
1367 * ocfs2_xattr_set_entry_local()
1368 *
1369 * Set, replace or remove extended attribute in local.
1370 */
1376 {
1381 /* Insert the new xattr entry. */
1396 OCFS2_XATTR_INLINE_SIZE)
1398 OCFS2_XATTR_ROOT_SIZE;
1399 else
1405 /* The old and the new value have the
1406 same size. Just replace the value. */
1409 /* Clear value bytes. */
1417 }
1418 /* Remove the old name+value. */
1428 /* Adjust all value offsets. */
1436 }
1439 /* Remove the old entry. */
1445 }
1446 }
1448 /* Insert the new name+value. */
1462 }
1465 }
1467 /*
1468 * ocfs2_xattr_set_entry()
1469 *
1470 * Set extended attribute entry into inode or block.
1471 *
1472 * If extended attribute value size > OCFS2_XATTR_INLINE_SIZE,
1473 * We first insert tree root(ocfs2_xattr_value_root) with set_entry_local(),
1474 * then set value in B tree with set_value_outside().
1475 */
1481 {
1494 };
1498 };
1506 /* Compute min_offs, last and free space. */
1514 }
1525 else
1527 OCFS2_XATTR_ROOT_SIZE;
1529 }
1530 /* Check free space in inode or block */
1534 OCFS2_XATTR_ROOT_SIZE) {
1537 }
1547 }
1548 }
1551 /* For existing extended attribute */
1558 /* Replace existing local xattr with tree root */
1565 /* For existing xattr which has value outside */
1570 /*
1571 * If new value need set outside also,
1572 * first truncate old value to new value,
1573 * then set new value with set_value_outside().
1574 */
1578 ctxt);
1582 }
1585 handle,
1586 xi,
1587 xs,
1589 offs);
1593 }
1596 handle,
1604 /*
1605 * If new value need set in local,
1606 * just trucate old value to zero.
1607 */
1611 ctxt);
1614 }
1615 }
1616 }
1619 OCFS2_JOURNAL_ACCESS_WRITE);
1623 }
1627 OCFS2_JOURNAL_ACCESS_WRITE);
1631 }
1632 }
1634 /*
1635 * Set value in local, include set tree root in local.
1636 * This is the first step for value size >INLINE_SIZE.
1637 */
1645 }
1646 }
1653 /*
1654 * Adjust extent record count or inline data size
1655 * to reserve space for extended attribute.
1656 */
1664 }
1666 }
1667 /* Update xattr flag */
1678 /*
1679 * Set value outside in B tree.
1680 * This is the second step for value size > INLINE_SIZE.
1681 */
1689 /*
1690 * If set value outside failed, we have to clean
1691 * the junk tree root we have already set in local.
1692 */
1697 }
1698 }
1699 out:
1701 }
1706 {
1719 }
1735 }
1736 }
1737 }
1742 out:
1744 }
1748 {
1756 };
1765 }
1769 {
1775 };
1785 }
1788 u64 block)
1789 {
1798 u16 bit;
1804 }
1810 }
1818 EXTENT_ALLOC_SYSTEM_INODE,
1824 }
1831 }
1838 }
1846 out_unlock:
1849 out_mutex:
1852 out:
1855 }
1857 /*
1858 * ocfs2_xattr_remove()
1859 *
1860 * Free extended attribute resources associated with this inode.
1861 */
1863 {
1880 }
1881 }
1889 }
1890 }
1893 OCFS2_INODE_UPDATE_CREDITS);
1898 }
1900 OCFS2_JOURNAL_ACCESS_WRITE);
1904 }
1916 out_commit:
1918 out:
1920 }
1924 {
1943 }
1948 }
1950 /*
1951 * ocfs2_xattr_ibody_find()
1952 *
1953 * Find extended attribute in inode block and
1954 * fill search info into struct ocfs2_xattr_search.
1955 */
1960 {
1975 }
1982 else
1988 /* Find the named attribute. */
1994 }
1997 }
1999 /*
2000 * ocfs2_xattr_ibody_set()
2001 *
2002 * Set, replace or remove an extended attribute into inode block.
2003 *
2004 */
2009 {
2022 }
2023 }
2027 out:
2031 }
2033 /*
2034 * ocfs2_xattr_block_find()
2035 *
2036 * Find extended attribute in external block and
2037 * fill search info into struct ocfs2_xattr_search.
2038 */
2043 {
2057 }
2071 name_index,
2077 }
2080 cleanup:
2084 }
2086 /*
2087 * ocfs2_xattr_block_set()
2088 *
2089 * Set, replace or remove an extended attribute into external block.
2090 *
2091 */
2096 {
2102 u16 suballoc_bit_start;
2103 u32 num_got;
2104 u64 first_blkno;
2109 OCFS2_JOURNAL_ACCESS_CREATE);
2113 }
2121 }
2127 OCFS2_JOURNAL_ACCESS_CREATE);
2131 }
2133 /* Initialize ocfs2_xattr_block */
2152 }
2159 /* Set extended attribute into external block */
2161 OCFS2_HAS_XATTR_FL);
2168 }
2172 end:
2175 }
2177 /* Check whether the new xattr can be inserted into the inode. */
2181 {
2182 u64 value_size;
2197 }
2207 else
2215 }
2225 {
2236 u64 value_size;
2238 /*
2239 * Calculate the clusters we need to write.
2240 * No matter whether we replace an old one or add a new one,
2241 * we need this for writing.
2242 */
2254 new_clusters);
2255 }
2258 }
2285 }
2286 }
2288 /*
2289 * delete a xattr doesn't need metadata and cluster allocation.
2290 * so just calculate the credits and return.
2291 *
2292 * The credits for removing the value tree will be extended
2293 * by ocfs2_remove_extent itself.
2294 */
2300 }
2302 /* do cluster allocation guess first. */
2306 /*
2307 * In xattr set, we always try to set the xe in inode first,
2308 * so if it can be inserted into inode successfully, the old
2309 * one will be removed from the xattr block, and this xattr
2310 * will be inserted into inode as a new xattr in inode.
2311 */
2315 OCFS2_INODE_UPDATE_CREDITS;
2320 new_clusters);
2322 }
2323 }
2326 /* the new values will be stored outside. */
2331 value_size);
2346 new_clusters -
2347 old_clusters);
2350 }
2352 /*
2353 * Now the new value will be stored inside. So if the new
2354 * value is smaller than the size of value root or the old
2355 * value, we don't need any allocation, otherwise we have
2356 * to guess metadata allocation.
2357 */
2362 }
2364 meta_guess:
2365 /* calculate metadata allocation. */
2374 }
2380 /*
2381 * If there is already an xattr tree, good, we can calculate
2382 * like other b-trees. Otherwise we may have the chance of
2383 * create a tree, the credit calculation is borrowed from
2384 * ocfs2_calc_extend_credits with root_el = NULL. And the
2385 * new tree will be cluster based, so no meta is needed.
2386 */
2396 /*
2397 * This cluster will be used either for new bucket or for
2398 * new xattr block.
2399 * If the cluster size is the same as the bucket size, one
2400 * more is needed since we may need to extend the bucket
2401 * also.
2402 */
2409 }
2413 }
2414 out:
2423 }
2432 {
2445 }
2456 }
2457 }
2463 }
2464 out:
2469 }
2471 /*
2472 * We cannot have an error and a non null ctxt->data_ac.
2473 */
2474 }
2477 }
2485 {
2489 /* Remove existing extended attribute */
2495 /* We always try to set extended attribute into inode first*/
2498 /*
2499 * If succeed and that extended attribute existing in
2500 * external block, then we will remove it.
2501 */
2508 di,
2509 xi,
2510 xis,
2511 xbs,
2512 NULL,
2513 NULL,
2519 }
2526 }
2539 di,
2540 xi,
2541 xis,
2542 xbs,
2543 NULL,
2544 NULL,
2550 }
2557 }
2558 }
2559 /*
2560 * If no space in inode, we will set extended attribute
2561 * into external block.
2562 */
2567 /*
2568 * If succeed and that extended attribute
2569 * existing in inode, we will remove it.
2570 */
2575 di,
2576 xi,
2577 xis,
2578 xbs,
2579 NULL,
2580 NULL,
2585 }
2592 }
2595 }
2596 }
2597 }
2600 /* Update inode ctime. */
2603 OCFS2_JOURNAL_ACCESS_WRITE);
2607 }
2613 }
2614 out:
2616 }
2618 /*
2619 * This function only called duing creating inode
2620 * for init security/acl xattrs of the new inode.
2621 * All transanction credits have been reserved in mknod.
2622 */
2633 {
2642 };
2646 };
2650 };
2656 };
2661 /*
2662 * In extreme situation, may need xattr bucket when
2663 * block size is too small. And we have already reserved
2664 * the credits for bucket in mknod.
2665 */
2671 }
2672 }
2686 }
2690 cleanup:
2696 }
2698 /*
2699 * ocfs2_xattr_set()
2700 *
2701 * Set, replace or remove an extended attribute for this inode.
2702 * value is NULL to remove an existing extended attribute, else either
2703 * create or replace an extended attribute.
2704 */
2711 {
2724 };
2728 };
2732 };
2737 /*
2738 * Only xbs will be used on indexed trees. xis doesn't need a
2739 * bucket.
2740 */
2745 }
2751 }
2756 /*
2757 * Scan inode and external block to find the same name
2758 * extended attribute and collect search infomation.
2759 */
2767 }
2780 }
2791 }
2792 }
2800 }
2802 /* we need to update inode's ctime field, so add credit for it. */
2809 }
2822 cleanup:
2825 cleanup_nolock:
2831 }
2833 /*
2834 * Find the xattr extent rec which may contains name_hash.
2835 * e_cpos will be the first name hash of the xattr rec.
2836 * el must be the ocfs2_xattr_header.xb_attrs.xb_root.xt_list.
2837 */
2839 u32 name_hash,
2844 {
2856 }
2863 "Inode %lu has non zero tree depth in "
2868 }
2869 }
2877 }
2878 }
2887 }
2893 out:
2896 }
2906 u32 name_hash,
2909 {
2916 /*
2917 * We don't use binary search in the bucket because there
2918 * may be multiple entries with the same name hash.
2919 */
2935 xh,
2936 i,
2942 }
2951 }
2952 }
2955 }
2957 /*
2958 * Find the specified xattr entry in a series of buckets.
2959 * This series start from p_blkno and last for num_clusters.
2960 * The ocfs2_xattr_header.xh_num_buckets of the first bucket contains
2961 * the num of the valid buckets.
2962 *
2963 * Return the buffer_head this xattr should reside in. And if the xattr's
2964 * hash is in the gap of 2 buckets, return the lower bucket.
2965 */
2969 u32 name_hash,
2970 u64 p_blkno,
2971 u32 first_hash,
2972 u32 num_clusters,
2974 {
2982 u32 last_hash;
2990 }
2996 }
3009 }
3016 }
3018 /*
3019 * Check whether the hash of the last entry in our
3020 * bucket is larger than the search one. for an empty
3021 * bucket, the last one is also the first one.
3022 */
3028 /* record lower_blkno which may be the insert place. */
3034 }
3036 /* the searched xattr should reside in this bucket if exists. */
3043 }
3045 }
3047 /*
3048 * Record the bucket we have found.
3049 * When the xattr's hash value is in the gap of 2 buckets, we will
3050 * always set it to the previous bucket.
3051 */
3055 /* This should be in cache - we just read it during the search */
3060 }
3073 out:
3076 }
3083 {
3104 }
3110 first_hash);
3115 out:
3117 }
3120 u64 blkno,
3121 u32 clusters,
3124 {
3134 }
3144 }
3146 /*
3147 * The real bucket num in this series of blocks is stored
3148 * in the 1st bucket.
3149 */
3160 /* Fall through to bucket_relse() */
3161 }
3166 }
3170 }
3176 };
3183 {
3184 u16 name_offset;
3195 }
3200 {
3214 i,
3221 new_offset;
3229 }
3230 }
3233 }
3239 {
3248 };
3259 }
3262 ocfs2_list_xattr_bucket,
3268 }
3274 }
3277 out:
3279 }
3282 {
3292 }
3295 {
3301 }
3303 /*
3304 * When the ocfs2_xattr_block is filled up, new bucket will be created
3305 * and all the xattr entries will be moved to the new bucket.
3306 * The header goes at the start of the bucket, and the names+values are
3307 * filled from the end. This is why *target starts as the last buffer.
3308 * Note: we need to sort the entries since they are not saved in order
3309 * in the ocfs2_xattr_block.
3310 */
3314 {
3334 /*
3335 * Since the xe_name_offset is based on ocfs2_xattr_header,
3336 * there is a offset change corresponding to the change of
3337 * ocfs2_xattr_header's position.
3338 */
3344 /* copy all the names and values. */
3347 /* Init new header now. */
3353 /* copy all the entries. */
3359 /* Change the xe offset for all the xe because of the move. */
3370 }
3372 /*
3373 * After we move xattr from block to index btree, we have to
3374 * update ocfs2_xattr_search to the new xe and base.
3375 *
3376 * When the entry is in xattr block, xattr_bh indicates the storage place.
3377 * While if the entry is in index b-tree, "bucket" indicates the
3378 * real place of the xattr.
3379 */
3383 {
3398 }
3403 {
3406 u64 blkno;
3422 /*
3423 * XXX:
3424 * We can use this lock for now, and maybe move to a dedicated mutex
3425 * if performance becomes a problem later.
3426 */
3430 OCFS2_JOURNAL_ACCESS_WRITE);
3434 }
3441 }
3443 /*
3444 * The bucket may spread in many blocks, and
3445 * we will only touch the 1st block and the last block
3446 * in the whole bucket(one for entry and one for data).
3447 */
3457 }
3460 OCFS2_JOURNAL_ACCESS_CREATE);
3464 }
3471 /* Change from ocfs2_xattr_header to ocfs2_xattr_tree_root */
3490 out:
3494 }
3497 {
3507 }
3509 /*
3510 * defrag a xattr bucket if we find that the bucket has some
3511 * holes beteen name/value pairs.
3512 * We will move all the name/value pairs to the end of the bucket
3513 * so that we can spare some space for insertion.
3514 */
3518 {
3524 u16 xh_free_start;
3528 /*
3529 * In order to make the operation more efficient and generic,
3530 * we copy all the blocks into a contiguous memory and do the
3531 * defragment there, so if anything is error, we will not touch
3532 * the real block.
3533 */
3538 }
3545 OCFS2_JOURNAL_ACCESS_WRITE);
3549 }
3560 /*
3561 * sort all the entries by their offset.
3562 * the largest will be the first, so that we can
3563 * move them to the end one by one.
3564 */
3569 /* Move all name/values to the end of the bucket. */
3577 else
3581 /*
3582 * We must make sure that the name/value pair
3583 * exist in the same block. So adjust end to
3584 * the previous block end if needed.
3585 */
3594 }
3600 }
3611 /* sort the entries by their name_hash. */
3621 out:
3624 }
3626 /*
3627 * prev_blkno points to the start of an existing extent. new_blkno
3628 * points to a newly allocated extent. Because we know each of our
3629 * clusters contains more than bucket, we can easily split one cluster
3630 * at a bucket boundary. So we take the last cluster of the existing
3631 * extent and split it down the middle. We move the last half of the
3632 * buckets in the last cluster of the existing extent over to the new
3633 * extent.
3634 *
3635 * first_bh is the buffer at prev_blkno so we can update the existing
3636 * extent's bucket count. header_bh is the bucket were we were hoping
3637 * to insert our xattr. If the bucket move places the target in the new
3638 * extent, we'll update first_bh and header_bh after modifying the old
3639 * extent.
3640 *
3641 * first_hash will be set as the 1st xe's name_hash in the new extent.
3642 */
3647 u64 new_blkno,
3648 u32 num_clusters,
3650 {
3656 u64 src_blkno;
3672 }
3674 /* This is the first bucket that got moved */
3677 /*
3678 * If the target bucket was part of the moved buckets, we need to
3679 * update first and target.
3680 */
3682 /* Find the block for the new target bucket */
3689 /*
3690 * These shouldn't fail - the buffers are in the
3691 * journal from ocfs2_cp_xattr_bucket().
3692 */
3697 }
3702 }
3704 out:
3706 }
3708 /*
3709 * Find the suitable pos when we divide a bucket into 2.
3710 * We have to make sure the xattrs with the same hash value exist
3711 * in the same bucket.
3712 *
3713 * If this ocfs2_xattr_header covers more than one hash value, find a
3714 * place where the hash value changes. Try to find the most even split.
3715 * The most common case is that all entries have different hash values,
3716 * and the first check we make will find a place to split.
3717 */
3719 {
3724 /*
3725 * We start at the middle. Each step gets farther away in both
3726 * directions. We therefore hit the change in hash value
3727 * nearest to the middle. Note that this loop does not execute for
3728 * count < 2.
3729 */
3731 /* Let's check delta earlier than middle */
3736 /* For even counts, don't walk off the end */
3740 /* Now try delta past middle */
3744 }
3746 /* Every entry had the same hash */
3748 }
3750 /*
3751 * Move some xattrs in old bucket(blk) to new bucket(new_blk).
3752 * first_hash will record the 1st hash of the new bucket.
3753 *
3754 * Normally half of the xattrs will be moved. But we have to make
3755 * sure that the xattrs with the same hash value are stored in the
3756 * same bucket. If all the xattrs in this bucket have the same hash
3757 * value, the new bucket will be initialized as an empty one and the
3758 * first_hash will be initialized as (hash_value+1).
3759 */
3762 u64 blk,
3763 u64 new_blk,
3766 {
3783 }
3789 }
3792 OCFS2_JOURNAL_ACCESS_WRITE);
3796 }
3798 /*
3799 * Even if !new_bucket_head, we're overwriting t_bucket. Thus,
3800 * there's no need to read it.
3801 */
3806 }
3808 /*
3809 * Hey, if we're overwriting t_bucket, what difference does
3810 * ACCESS_CREATE vs ACCESS_WRITE make? See the comment in the
3811 * same part of ocfs2_cp_xattr_bucket().
3812 */
3814 new_bucket_head ?
3815 OCFS2_JOURNAL_ACCESS_CREATE :
3816 OCFS2_JOURNAL_ACCESS_WRITE);
3820 }
3829 /*
3830 * initialized a new empty bucket here.
3831 * The hash value is set as one larger than
3832 * that of the last entry in the previous bucket.
3833 */
3843 }
3845 /* copy the whole bucket to the new first. */
3848 /* update the new bucket. */
3851 /*
3852 * Calculate the total name/value len and xh_free_start for
3853 * the old bucket first.
3854 */
3861 xe_len +=
3863 else
3868 }
3870 /*
3871 * Now begin the modification to the new bucket.
3872 *
3873 * In the new bucket, We just move the xattr entry to the beginning
3874 * and don't touch the name/value. So there will be some holes in the
3875 * bucket, and they will be removed when ocfs2_defrag_xattr_bucket is
3876 * called.
3877 */
3891 /* Calculate xh_free_start for the new bucket. */
3897 xe_len +=
3899 else
3904 }
3906 set_num_buckets:
3907 /* set xh->xh_num_buckets for the new xh. */
3910 else
3915 /* store the first_hash of the new bucket. */
3919 /*
3920 * Now only update the 1st block of the old bucket. If we
3921 * just added a new empty bucket, there is no need to modify
3922 * it.
3923 */
3936 out:
3941 }
3943 /*
3944 * Copy xattr from one bucket to another bucket.
3945 *
3946 * The caller must make sure that the journal transaction
3947 * has enough space for journaling.
3948 */
3951 u64 s_blkno,
3952 u64 t_blkno,
3954 {
3962 t_is_new);
3970 }
3976 /*
3977 * Even if !t_is_new, we're overwriting t_bucket. Thus,
3978 * there's no need to read it.
3979 */
3984 /*
3985 * Hey, if we're overwriting t_bucket, what difference does
3986 * ACCESS_CREATE vs ACCESS_WRITE make? Well, if we allocated a new
3987 * cluster to fill, we came here from
3988 * ocfs2_mv_xattr_buckets(), and it is really new -
3989 * ACCESS_CREATE is required. But we also might have moved data
3990 * out of t_bucket before extending back into it.
3991 * ocfs2_add_new_xattr_bucket() can do this - its call to
3992 * ocfs2_add_new_xattr_cluster() may have created a new extent
3993 * and copied out the end of the old extent. Then it re-extends
3994 * the old extent back to create space for new xattrs. That's
3995 * how we get here, and the bucket isn't really new.
3996 */
3998 t_is_new ?
3999 OCFS2_JOURNAL_ACCESS_CREATE :
4000 OCFS2_JOURNAL_ACCESS_WRITE);
4007 out:
4012 }
4014 /*
4015 * src_blk points to the start of an existing extent. last_blk points to
4016 * last cluster in that extent. to_blk points to a newly allocated
4017 * extent. We copy the buckets from the cluster at last_blk to the new
4018 * extent. If start_bucket is non-zero, we skip that many buckets before
4019 * we start copying. The new extent's xh_num_buckets gets set to the
4020 * number of buckets we copied. The old extent's xh_num_buckets shrinks
4021 * by the same amount.
4022 */
4027 {
4041 }
4043 /* The first bucket of the original extent */
4045 /* The first bucket of the new extent */
4051 }
4057 }
4059 /*
4060 * We need to update the first bucket of the old extent and all
4061 * the buckets going to the new extent.
4062 */
4069 }
4072 OCFS2_JOURNAL_ACCESS_WRITE);
4076 }
4086 }
4087 }
4089 /*
4090 * Get the new bucket ready before we dirty anything
4091 * (This actually shouldn't fail, because we already dirtied
4092 * it once in ocfs2_cp_xattr_bucket()).
4093 */
4098 }
4100 OCFS2_JOURNAL_ACCESS_WRITE);
4104 }
4106 /* Now update the headers */
4116 out:
4120 }
4122 /*
4123 * Move some xattrs in this cluster to the new cluster.
4124 * This function should only be called when bucket size == cluster size.
4125 * Otherwise ocfs2_mv_xattr_bucket_cross_cluster should be used instead.
4126 */
4129 u64 prev_blk,
4130 u64 new_blk,
4132 {
4142 }
4144 /* Move half of the xattr in start_blk to the next bucket. */
4147 }
4149 /*
4150 * Move some xattrs from the old cluster to the new one since they are not
4151 * contiguous in ocfs2 xattr tree.
4152 *
4153 * new_blk starts a new separate cluster, and we will move some xattrs from
4154 * prev_blk to it. v_start will be set as the first name hash value in this
4155 * new cluster so that it can be used as e_cpos during tree insertion and
4156 * don't collide with our original b-tree operations. first_bh and header_bh
4157 * will also be updated since they will be used in ocfs2_extend_xattr_bucket
4158 * to extend the insert bucket.
4159 *
4160 * The problem is how much xattr should we move to the new one and when should
4161 * we update first_bh and header_bh?
4162 * 1. If cluster size > bucket size, that means the previous cluster has more
4163 * than 1 bucket, so just move half nums of bucket into the new cluster and
4164 * update the first_bh and header_bh if the insert bucket has been moved
4165 * to the new cluster.
4166 * 2. If cluster_size == bucket_size:
4167 * a) If the previous extent rec has more than one cluster and the insert
4168 * place isn't in the last cluster, copy the entire last cluster to the
4169 * new one. This time, we don't need to upate the first_bh and header_bh
4170 * since they will not be moved into the new cluster.
4171 * b) Otherwise, move the bottom half of the xattrs in the last cluster into
4172 * the new one. And we set the extend flag to zero if the insert place is
4173 * moved into the new allocated cluster since no extend is needed.
4174 */
4179 u64 new_blk,
4180 u32 prev_clusters,
4183 {
4192 handle,
4194 new_blk,
4195 prev_clusters,
4196 v_start);
4200 /* The start of the last cluster in the first extent */
4209 v_start);
4215 v_start);
4221 }
4222 }
4225 }
4227 /*
4228 * Add a new cluster for xattr storage.
4229 *
4230 * If the new cluster is contiguous with the previous one, it will be
4231 * appended to the same extent record, and num_clusters will be updated.
4232 * If not, we will insert a new extent for it and move some xattrs in
4233 * the last cluster into the new allocated one.
4234 * We also need to limit the maximum size of a btree leaf, otherwise we'll
4235 * lose the benefits of hashing because we'll have to search large leaves.
4236 * So now the maximum size is OCFS2_MAX_XATTR_TREE_LEAF_SIZE(or clustersize,
4237 * if it's bigger).
4238 *
4239 * first_bh is the first block of the previous extent rec and header_bh
4240 * indicates the bucket we will insert the new xattrs. They will be updated
4241 * when the header_bh is moved into the new cluster.
4242 */
4248 u32 prev_cpos,
4251 {
4256 u64 block;
4269 OCFS2_JOURNAL_ACCESS_WRITE);
4273 }
4281 }
4291 OCFS2_MAX_XATTR_TREE_LEAF_SIZE) {
4292 /*
4293 * If this cluster is contiguous with the old one and
4294 * adding this new cluster, we don't surpass the limit of
4295 * OCFS2_MAX_XATTR_TREE_LEAF_SIZE, cool. We will let it be
4296 * initialized and used like other buckets in the previous
4297 * cluster.
4298 * So add it as a contiguous one. The caller will handle
4299 * its init process.
4300 */
4304 num_bits);
4307 handle,
4308 first,
4309 target,
4310 block,
4311 prev_clusters,
4313 extend);
4317 }
4318 }
4327 }
4333 leave:
4335 }
4337 /*
4338 * We are given an extent. 'first' is the bucket at the very front of
4339 * the extent. The extent has space for an additional bucket past
4340 * bucket_xh(first)->xh_num_buckets. 'target_blkno' is the block number
4341 * of the target bucket. We wish to shift every bucket past the target
4342 * down one, filling in that additional space. When we get back to the
4343 * target, we split the target between itself and the now-empty bucket
4344 * at target+1 (aka, target_blkno + blks_per_bucket).
4345 */
4349 u64 target_blk,
4350 u32 num_clusters)
4351 {
4355 u64 end_blk;
4362 /* The extent must have room for an additional bucket */
4366 /* end_blk points to the last existing bucket */
4369 /*
4370 * end_blk is the start of the last existing bucket.
4371 * Thus, (end_blk - target_blk) covers the target bucket and
4372 * every bucket after it up to, but not including, the last
4373 * existing bucket. Then we add the last existing bucket, the
4374 * new bucket, and the first bucket (3 * blk_per_bucket).
4375 */
4382 }
4385 OCFS2_JOURNAL_ACCESS_WRITE);
4389 }
4397 }
4399 /* Move half of the xattr in target_blkno to the next bucket. */
4406 out:
4408 }
4410 /*
4411 * Add new xattr bucket in an extent record and adjust the buckets
4412 * accordingly. xb_bh is the ocfs2_xattr_block, and target is the
4413 * bucket we want to insert into.
4414 *
4415 * In the easy case, we will move all the buckets after target down by
4416 * one. Half of target's xattrs will be moved to the next bucket.
4417 *
4418 * If current cluster is full, we'll allocate a new one. This may not
4419 * be contiguous. The underlying calls will make sure that there is
4420 * space for the insert, shifting buckets around if necessary.
4421 * 'target' may be moved by those calls.
4422 */
4427 {
4432 u32 name_hash =
4436 u64 p_blkno;
4438 /* The bucket at the front of the extent */
4444 /* The first bucket of the original extent */
4450 }
4457 }
4463 }
4467 /*
4468 * This can move first+target if the target bucket moves
4469 * to the new extent.
4470 */
4472 xb_bh,
4473 first,
4474 target,
4476 e_cpos,
4478 ctxt);
4482 }
4483 }
4488 first,
4490 num_clusters);
4493 }
4495 out:
4499 }
4504 {
4509 }
4511 /*
4512 * Handle the normal xattr set, including replace, delete and new.
4513 *
4514 * Note: "local" indicates the real data's locality. So we can't
4515 * just its bucket locality by its length.
4516 */
4520 u32 name_hash,
4522 {
4538 else
4542 /*
4543 * If the new value will be stored outside, xi->value has been
4544 * initalized as an empty ocfs2_xattr_value_root, and the same
4545 * goes with xi->value_len, so we can set new_size safely here.
4546 * See ocfs2_xattr_set_in_bucket.
4547 */
4556 /* Now replace the old value with new one. */
4559 else
4574 /*
4575 * Remove the old entry if there is more than one.
4576 * We don't remove the last entry so that we can
4577 * use it to indicate the hash value of the empty
4578 * bucket.
4579 */
4592 }
4594 /* find a new entry for insert. */
4610 }
4611 }
4622 }
4624 set_new_name_value:
4625 /* Insert the new name+value. */
4628 /*
4629 * We must make sure that the name/value pair
4630 * exists in the same block.
4631 */
4639 }
4655 }
4657 /*
4658 * Set the xattr entry in the specified bucket.
4659 * The bucket is indicated by xs->bucket and it should have the enough
4660 * space for the xattr insertion.
4661 */
4666 u32 name_hash,
4668 {
4670 u64 blkno;
4683 }
4684 }
4687 OCFS2_JOURNAL_ACCESS_WRITE);
4691 }
4696 out:
4698 }
4700 /*
4701 * Truncate the specified xe_off entry in xattr bucket.
4702 * bucket is indicated by header_bh and len is the new length.
4703 * Both the ocfs2_xattr_value_root and the entry will be updated here.
4704 *
4705 * Copy the new updated xe and xe_value_root to new_xe and new_xv if needed.
4706 */
4712 {
4714 u64 value_blk;
4720 };
4731 /* We don't allow ocfs2_xattr_value to be stored in different block. */
4740 /*
4741 * From here on out we have to dirty the bucket. The generic
4742 * value calls only modify one of the bucket's bhs, but we need
4743 * to send the bucket at once. So if they error, they *could* have
4744 * modified something. We have to assume they did, and dirty
4745 * the whole bucket. This leaves us in a consistent state.
4746 */
4753 }
4756 OCFS2_JOURNAL_ACCESS_WRITE);
4760 }
4766 out:
4768 }
4774 {
4788 }
4795 {
4811 }
4821 out:
4823 }
4827 u64 blkno,
4828 u32 cpos,
4829 u32 len)
4830 {
4854 }
4863 }
4864 }
4871 }
4874 OCFS2_JOURNAL_ACCESS_WRITE);
4878 }
4885 }
4893 }
4899 out_commit:
4901 out:
4912 }
4917 {
4924 OCFS2_JOURNAL_ACCESS_WRITE);
4928 }
4930 /* Remove the old entry. */
4937 }
4939 /*
4940 * Set the xattr name/value in the bucket specified in xs.
4941 *
4942 * As the new value in xi may be stored in the bucket or in an outside cluster,
4943 * we divide the whole process into 3 steps:
4944 * 1. insert name/value in the bucket(ocfs2_xattr_set_entry_in_bucket)
4945 * 2. truncate of the outside cluster(ocfs2_xattr_bucket_value_truncate_xs)
4946 * 3. Set the value to the outside cluster(ocfs2_xattr_bucket_set_value_outside)
4947 * 4. If the clusters for the new outside value can't be allocated, we need
4948 * to free the xattr we allocated in set.
4949 */
4954 {
4963 /*
4964 * We need to truncate the xattr storage first.
4965 *
4966 * If both the old and new value are stored to
4967 * outside block, we only need to truncate
4968 * the storage and then set the value outside.
4969 *
4970 * If the new value should be stored within block,
4971 * we should free all the outside block first and
4972 * the modification to the xattr block will be done
4973 * by following steps.
4974 */
4977 else
4981 value_len,
4982 ctxt);
4988 }
4991 /* So we have to handle the inside block change now. */
4993 /*
4994 * If the new value will be stored outside of block,
4995 * initalize a new empty value root and insert it first.
4996 */
5000 }
5007 }
5012 /* allocate the space now for the outside block storage. */
5019 /*
5020 * We can't allocate enough clusters for outside
5021 * storage and we have allocated xattr already,
5022 * so need to remove it.
5023 */
5025 }
5027 }
5029 set_value_outside:
5032 out:
5034 }
5036 /*
5037 * check whether the xattr bucket is filled up with the same hash value.
5038 * If we want to insert the xattr with the same hash, return -ENOSPC.
5039 * If we want to insert a xattr with different hash value, go ahead
5040 * and ocfs2_divide_xattr_bucket will handle this.
5041 */
5045 {
5059 }
5062 }
5068 {
5079 try_again:
5091 header_size);
5104 /*
5105 * We only replace the old value if the new length is smaller
5106 * than the old one. Otherwise we will allocate new space in the
5107 * bucket to store it.
5108 */
5112 else
5117 }
5120 /*
5121 * We need to make sure the new name/value pair
5122 * can exist in the same block.
5123 */
5128 "need = %d, max_free = %d, xh_free_start = %u, xh_name_value_len ="
5139 /*
5140 * We can create the space by defragment. Since only the
5141 * name/value will be moved, the xe shouldn't be changed
5142 * in xs.
5143 */
5149 }
5161 "defragment. Need %u bytes, but we have %d, so "
5163 }
5165 /*
5166 * We have to add new buckets or clusters and one
5167 * allocation should leave us enough space for insert.
5168 */
5171 /*
5172 * We do not allow for overlapping ranges between buckets. And
5173 * the maximum number of collisions we will allow for then is
5174 * one bucket's worth, so check it here whether we need to
5175 * add a new bucket for the insert.
5176 */
5183 }
5188 ctxt);
5192 }
5194 /*
5195 * ocfs2_add_new_xattr_bucket() will have updated
5196 * xs->bucket if it moved, but it will not have updated
5197 * any of the other search fields. Thus, we drop it and
5198 * re-search. Everything should be cached, so it'll be
5199 * quick.
5200 */
5210 }
5212 xattr_set:
5214 out:
5217 }
5222 {
5225 u16 i;
5245 }
5254 }
5255 }
5260 }
5264 {
5270 u64 p_blkno;
5281 }
5284 ocfs2_delete_xattr_in_bucket,
5285 NULL);
5289 }
5296 }
5302 }
5304 out:
5306 }
5308 /*
5309 * 'security' attributes support
5310 */
5314 {
5322 }
5324 }
5328 {
5333 }
5337 {
5343 }
5348 {
5349 /* check whether ocfs2 support feature xattr */
5354 }
5362 {
5364 OCFS2_XATTR_INDEX_SECURITY,
5367 }
5374 };
5376 /*
5377 * 'trusted' attributes support
5378 */
5382 {
5390 }
5392 }
5396 {
5401 }
5405 {
5411 }
5418 };
5420 /*
5421 * 'user' attributes support
5422 */
5426 {
5438 }
5440 }
5444 {
5453 }
5457 {
5467 }
5474 };