2 * Copyright (c) 2011-2015 The DragonFly Project. All rights reserved.
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@dragonflybsd.org>
6 * and Venkatesh Srinivas <vsrinivas@dragonflybsd.org>
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in
16 * the documentation and/or other materials provided with the
18 * 3. Neither the name of The DragonFly Project nor the names of its
19 * contributors may be used to endorse or promote products derived
20 * from this software without specific, prior written permission.
22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
25 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
26 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
27 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
28 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
29 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
30 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
31 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
32 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36 * This subsystem implements most of the core support functions for
37 * the hammer2_chain structure.
39 * Chains are the in-memory version on media objects (volume header, inodes,
40 * indirect blocks, data blocks, etc). Chains represent a portion of the
43 * Chains are no-longer delete-duplicated. Instead, the original in-memory
44 * chain will be moved along with its block reference (e.g. for things like
45 * renames, hardlink operations, modifications, etc), and will be indexed
46 * on a secondary list for flush handling instead of propagating a flag
49 * Concurrent front-end operations can still run against backend flushes
50 * as long as they do not cross the current flush boundary. An operation
51 * running above the current flush (in areas not yet flushed) can become
52 * part of the current flush while ano peration running below the current
53 * flush can become part of the next flush.
55 #include <sys/cdefs.h>
56 #include <sys/param.h>
57 #include <sys/systm.h>
58 #include <sys/types.h>
60 #include <sys/kern_syscall.h>
63 #include <crypto/sha2/sha2.h>
67 static hammer2_chain_t
*hammer2_chain_create_indirect(
68 hammer2_chain_t
*parent
,
69 hammer2_key_t key
, int keybits
,
70 hammer2_tid_t mtid
, int for_type
, int *errorp
);
71 static hammer2_io_t
*hammer2_chain_drop_data(hammer2_chain_t
*chain
,
73 static hammer2_chain_t
*hammer2_combined_find(
74 hammer2_chain_t
*parent
,
75 hammer2_blockref_t
*base
, int count
,
76 int *cache_indexp
, hammer2_key_t
*key_nextp
,
77 hammer2_key_t key_beg
, hammer2_key_t key_end
,
78 hammer2_blockref_t
**bresp
);
81 * Basic RBTree for chains (core->rbtree and core->dbtree). Chains cannot
82 * overlap in the RB trees. Deleted chains are moved from rbtree to either
85 * Chains in delete-duplicate sequences can always iterate through core_entry
86 * to locate the live version of the chain.
88 RB_GENERATE(hammer2_chain_tree
, hammer2_chain
, rbnode
, hammer2_chain_cmp
);
90 extern int h2timer
[32];
94 #define TIMER(which) do { \
96 h2timer[h2lid] += (int)(ticks - h2last);\
102 hammer2_chain_cmp(hammer2_chain_t
*chain1
, hammer2_chain_t
*chain2
)
104 hammer2_key_t c1_beg
;
105 hammer2_key_t c1_end
;
106 hammer2_key_t c2_beg
;
107 hammer2_key_t c2_end
;
110 * Compare chains. Overlaps are not supposed to happen and catch
111 * any software issues early we count overlaps as a match.
113 c1_beg
= chain1
->bref
.key
;
114 c1_end
= c1_beg
+ ((hammer2_key_t
)1 << chain1
->bref
.keybits
) - 1;
115 c2_beg
= chain2
->bref
.key
;
116 c2_end
= c2_beg
+ ((hammer2_key_t
)1 << chain2
->bref
.keybits
) - 1;
118 if (c1_end
< c2_beg
) /* fully to the left */
120 if (c1_beg
> c2_end
) /* fully to the right */
122 return(0); /* overlap (must not cross edge boundary) */
126 * Make a chain visible to the flusher. The flusher needs to be able to
127 * do flushes of subdirectory chains or single files so it does a top-down
128 * recursion using the ONFLUSH flag for the recursion. It locates MODIFIED
129 * or UPDATE chains and flushes back up the chain to the volume root.
131 * This routine sets ONFLUSH upward until it hits the volume root. For
132 * simplicity we ignore PFSROOT boundaries whos rules can be complex.
133 * Extra ONFLUSH flagging doesn't hurt the filesystem.
136 hammer2_chain_setflush(hammer2_chain_t
*chain
)
138 hammer2_chain_t
*parent
;
140 if ((chain
->flags
& HAMMER2_CHAIN_ONFLUSH
) == 0) {
141 hammer2_spin_sh(&chain
->core
.spin
);
142 while ((chain
->flags
& HAMMER2_CHAIN_ONFLUSH
) == 0) {
143 atomic_set_int(&chain
->flags
, HAMMER2_CHAIN_ONFLUSH
);
144 if ((parent
= chain
->parent
) == NULL
)
146 hammer2_spin_sh(&parent
->core
.spin
);
147 hammer2_spin_unsh(&chain
->core
.spin
);
150 hammer2_spin_unsh(&chain
->core
.spin
);
155 * Allocate a new disconnected chain element representing the specified
156 * bref. chain->refs is set to 1 and the passed bref is copied to
157 * chain->bref. chain->bytes is derived from the bref.
159 * chain->pmp inherits pmp unless the chain is an inode (other than the
162 * NOTE: Returns a referenced but unlocked (because there is no core) chain.
165 hammer2_chain_alloc(hammer2_dev_t
*hmp
, hammer2_pfs_t
*pmp
,
166 hammer2_blockref_t
*bref
)
168 hammer2_chain_t
*chain
;
172 * Special case - radix of 0 indicates a chain that does not
173 * need a data reference (context is completely embedded in the
176 if ((int)(bref
->data_off
& HAMMER2_OFF_MASK_RADIX
))
177 bytes
= 1U << (int)(bref
->data_off
& HAMMER2_OFF_MASK_RADIX
);
181 atomic_add_long(&hammer2_chain_allocs
, 1);
184 * Construct the appropriate system structure.
187 case HAMMER2_BREF_TYPE_DIRENT
:
188 case HAMMER2_BREF_TYPE_INODE
:
189 case HAMMER2_BREF_TYPE_INDIRECT
:
190 case HAMMER2_BREF_TYPE_FREEMAP_NODE
:
191 case HAMMER2_BREF_TYPE_DATA
:
192 case HAMMER2_BREF_TYPE_FREEMAP_LEAF
:
194 * Chain's are really only associated with the hmp but we
195 * maintain a pmp association for per-mount memory tracking
196 * purposes. The pmp can be NULL.
198 chain
= kmalloc(sizeof(*chain
), hmp
->mchain
, M_WAITOK
| M_ZERO
);
200 case HAMMER2_BREF_TYPE_VOLUME
:
201 case HAMMER2_BREF_TYPE_FREEMAP
:
203 * Only hammer2_chain_bulksnap() calls this function with these
206 chain
= kmalloc(sizeof(*chain
), hmp
->mchain
, M_WAITOK
| M_ZERO
);
210 panic("hammer2_chain_alloc: unrecognized blockref type: %d",
215 * Initialize the new chain structure. pmp must be set to NULL for
216 * chains belonging to the super-root topology of a device mount.
218 if (pmp
== hmp
->spmp
)
224 chain
->bytes
= bytes
;
226 chain
->flags
= HAMMER2_CHAIN_ALLOCATED
;
229 * Set the PFS boundary flag if this chain represents a PFS root.
231 if (bref
->flags
& HAMMER2_BREF_FLAG_PFSROOT
)
232 atomic_set_int(&chain
->flags
, HAMMER2_CHAIN_PFSBOUNDARY
);
233 hammer2_chain_core_init(chain
);
239 * Initialize a chain's core structure. This structure used to be allocated
240 * but is now embedded.
242 * The core is not locked. No additional refs on the chain are made.
243 * (trans) must not be NULL if (core) is not NULL.
246 hammer2_chain_core_init(hammer2_chain_t
*chain
)
249 * Fresh core under nchain (no multi-homing of ochain's
252 RB_INIT(&chain
->core
.rbtree
); /* live chains */
253 hammer2_mtx_init(&chain
->lock
, "h2chain");
257 * Add a reference to a chain element, preventing its destruction.
259 * (can be called with spinlock held)
262 hammer2_chain_ref(hammer2_chain_t
*chain
)
264 if (atomic_fetchadd_int(&chain
->refs
, 1) == 0) {
266 * 0->non-zero transition must ensure that chain is removed
269 * NOTE: Already holding lru_spin here so we cannot call
270 * hammer2_chain_ref() to get it off lru_list, do
273 if (chain
->flags
& HAMMER2_CHAIN_ONLRU
) {
274 hammer2_pfs_t
*pmp
= chain
->pmp
;
275 hammer2_spin_ex(&pmp
->lru_spin
);
276 if (chain
->flags
& HAMMER2_CHAIN_ONLRU
) {
277 atomic_add_int(&pmp
->lru_count
, -1);
278 atomic_clear_int(&chain
->flags
,
279 HAMMER2_CHAIN_ONLRU
);
280 TAILQ_REMOVE(&pmp
->lru_list
, chain
, lru_node
);
282 hammer2_spin_unex(&pmp
->lru_spin
);
286 kprintf("REFC %p %d %08x\n", chain
, chain
->refs
- 1, chain
->flags
);
292 * Ref a locked chain and force the data to be held across an unlock.
293 * Chain must be currently locked. The user of the chain who desires
294 * to release the hold must call hammer2_chain_lock_unhold() to relock
295 * and unhold the chain, then unlock normally, or may simply call
296 * hammer2_chain_drop_unhold() (which is safer against deadlocks).
299 hammer2_chain_ref_hold(hammer2_chain_t
*chain
)
301 atomic_add_int(&chain
->lockcnt
, 1);
302 hammer2_chain_ref(chain
);
306 * Insert the chain in the core rbtree.
308 * Normal insertions are placed in the live rbtree. Insertion of a deleted
309 * chain is a special case used by the flush code that is placed on the
310 * unstaged deleted list to avoid confusing the live view.
312 #define HAMMER2_CHAIN_INSERT_SPIN 0x0001
313 #define HAMMER2_CHAIN_INSERT_LIVE 0x0002
314 #define HAMMER2_CHAIN_INSERT_RACE 0x0004
318 hammer2_chain_insert(hammer2_chain_t
*parent
, hammer2_chain_t
*chain
,
319 int flags
, int generation
)
321 hammer2_chain_t
*xchain
;
324 if (flags
& HAMMER2_CHAIN_INSERT_SPIN
)
325 hammer2_spin_ex(&parent
->core
.spin
);
328 * Interlocked by spinlock, check for race
330 if ((flags
& HAMMER2_CHAIN_INSERT_RACE
) &&
331 parent
->core
.generation
!= generation
) {
339 xchain
= RB_INSERT(hammer2_chain_tree
, &parent
->core
.rbtree
, chain
);
340 KASSERT(xchain
== NULL
,
341 ("hammer2_chain_insert: collision %p %p (key=%016jx)",
342 chain
, xchain
, chain
->bref
.key
));
343 atomic_set_int(&chain
->flags
, HAMMER2_CHAIN_ONRBTREE
);
344 chain
->parent
= parent
;
345 ++parent
->core
.chain_count
;
346 ++parent
->core
.generation
; /* XXX incs for _get() too, XXX */
349 * We have to keep track of the effective live-view blockref count
350 * so the create code knows when to push an indirect block.
352 if (flags
& HAMMER2_CHAIN_INSERT_LIVE
)
353 atomic_add_int(&parent
->core
.live_count
, 1);
355 if (flags
& HAMMER2_CHAIN_INSERT_SPIN
)
356 hammer2_spin_unex(&parent
->core
.spin
);
361 * Drop the caller's reference to the chain. When the ref count drops to
362 * zero this function will try to disassociate the chain from its parent and
363 * deallocate it, then recursely drop the parent using the implied ref
364 * from the chain's chain->parent.
366 static hammer2_chain_t
*hammer2_chain_lastdrop(hammer2_chain_t
*chain
);
369 hammer2_chain_drop(hammer2_chain_t
*chain
)
373 if (hammer2_debug
& 0x200000)
376 kprintf("DROP %p %d %08x\n", chain
, chain
->refs
- 1, chain
->flags
);
380 KKASSERT(chain
->refs
> 0);
388 chain
= hammer2_chain_lastdrop(chain
);
390 if (atomic_cmpset_int(&chain
->refs
, refs
, refs
- 1))
392 /* retry the same chain */
398 * Unhold a held and probably not-locked chain, ensure that the data is
399 * dropped on the 1->0 transition of lockcnt by obtaing an exclusive
400 * lock and then simply unlocking the chain.
403 hammer2_chain_drop_unhold(hammer2_chain_t
*chain
)
409 lockcnt
= chain
->lockcnt
;
412 if (atomic_cmpset_int(&chain
->lockcnt
,
413 lockcnt
, lockcnt
- 1)) {
416 } else if (mtx_lock_ex_try(&chain
->lock
) == 0) {
417 hammer2_chain_unlock(chain
);
421 * This situation can easily occur on SMP due to
422 * the gap inbetween the 1->0 transition and the
423 * final unlock. We cannot safely block on the
424 * mutex because lockcnt might go above 1.
426 * XXX Sleep for one tick if it takes too long.
429 if (iter
> 1000 + hz
) {
430 kprintf("hammer2: h2race1 %p\n", chain
);
433 tsleep(&iter
, 0, "h2race1", 1);
438 hammer2_chain_drop(chain
);
442 * Safe handling of the 1->0 transition on chain. Returns a chain for
443 * recursive drop or NULL, possibly returning the same chain if the atomic
446 * When two chains need to be recursively dropped we use the chain we
447 * would otherwise free to placehold the additional chain. It's a bit
448 * convoluted but we can't just recurse without potentially blowing out
451 * The chain cannot be freed if it has any children.
452 * The chain cannot be freed if flagged MODIFIED unless we can dispose of that.
453 * The chain cannot be freed if flagged UPDATE unless we can dispose of that.
455 * The core spinlock is allowed nest child-to-parent (not parent-to-child).
459 hammer2_chain_lastdrop(hammer2_chain_t
*chain
)
463 hammer2_chain_t
*parent
;
464 hammer2_chain_t
*rdrop
;
468 * On last drop if there is no parent and data_off is good (at
469 * least does not represent the volume root), the modified chain
470 * is probably going to be destroyed. We have to make sure that
471 * the data area is not registered for dedup.
473 if (chain
->parent
== NULL
&&
474 (chain
->flags
& HAMMER2_CHAIN_MODIFIED
) &&
475 (chain
->bref
.data_off
& ~HAMMER2_OFF_MASK_RADIX
)) {
477 hammer2_io_dedup_delete(hmp
, chain
->bref
.type
,
478 chain
->bref
.data_off
, chain
->bytes
);
482 * Critical field access.
484 hammer2_spin_ex(&chain
->core
.spin
);
486 if ((parent
= chain
->parent
) != NULL
) {
488 * If the chain has a parent the UPDATE bit prevents scrapping
489 * as the chain is needed to properly flush the parent. Try
490 * to complete the 1->0 transition and return NULL. Retry
491 * (return chain) if we are unable to complete the 1->0
492 * transition, else return NULL (nothing more to do).
494 * If the chain has a parent the MODIFIED bit prevents
497 * Chains with UPDATE/MODIFIED are *not* put on the LRU list!
499 if (chain
->flags
& (HAMMER2_CHAIN_UPDATE
|
500 HAMMER2_CHAIN_MODIFIED
)) {
501 if (atomic_cmpset_int(&chain
->refs
, 1, 0)) {
502 dio
= hammer2_chain_drop_data(chain
, 0);
503 hammer2_spin_unex(&chain
->core
.spin
);
505 hammer2_io_bqrelse(&dio
);
508 hammer2_spin_unex(&chain
->core
.spin
);
512 /* spinlock still held */
515 * The chain has no parent and can be flagged for destruction.
516 * Since it has no parent, UPDATE can also be cleared.
518 atomic_set_int(&chain
->flags
, HAMMER2_CHAIN_DESTROY
);
519 if (chain
->flags
& HAMMER2_CHAIN_UPDATE
)
520 atomic_clear_int(&chain
->flags
, HAMMER2_CHAIN_UPDATE
);
523 * If the chain has children we must still flush the chain.
524 * Any dedup is already handled by the underlying DIO, so
525 * we do not have to specifically flush it here.
527 * In the case where it has children, the DESTROY flag test
528 * in the flush code will prevent unnecessary flushes of
529 * MODIFIED chains that are not flagged DEDUP so don't worry
532 if (chain
->core
.chain_count
) {
534 * Put on flushq (should ensure refs > 1), retry
537 hammer2_spin_unex(&chain
->core
.spin
);
538 hammer2_delayed_flush(chain
);
539 return(chain
); /* retry drop */
543 * Otherwise we can scrap the MODIFIED bit if it is set,
544 * and continue along the freeing path.
546 * Be sure to clean-out any dedup bits. Without a parent
547 * this chain will no longer be visible to the flush code.
548 * Easy check data_off to avoid the volume root.
550 if (chain
->flags
& HAMMER2_CHAIN_MODIFIED
) {
551 atomic_clear_int(&chain
->flags
, HAMMER2_CHAIN_MODIFIED
);
552 atomic_add_long(&hammer2_count_modified_chains
, -1);
554 hammer2_pfs_memory_wakeup(chain
->pmp
);
556 /* spinlock still held */
559 /* spinlock still held */
563 * If any children exist we must leave the chain intact with refs == 0.
564 * They exist because chains are retained below us which have refs or
565 * may require flushing. This case can occur when parent != NULL.
567 * Retry (return chain) if we fail to transition the refs to 0, else
568 * return NULL indication nothing more to do.
570 * Chains with children are NOT put on the LRU list.
572 if (chain
->core
.chain_count
) {
574 hammer2_spin_ex(&parent
->core
.spin
);
575 if (atomic_cmpset_int(&chain
->refs
, 1, 0)) {
576 dio
= hammer2_chain_drop_data(chain
, 1);
577 hammer2_spin_unex(&chain
->core
.spin
);
579 hammer2_spin_unex(&parent
->core
.spin
);
582 hammer2_io_bqrelse(&dio
);
584 hammer2_spin_unex(&chain
->core
.spin
);
586 hammer2_spin_unex(&parent
->core
.spin
);
590 /* spinlock still held */
591 /* no chains left under us */
594 * chain->core has no children left so no accessors can get to our
595 * chain from there. Now we have to lock the parent core to interlock
596 * remaining possible accessors that might bump chain's refs before
597 * we can safely drop chain's refs with intent to free the chain.
600 pmp
= chain
->pmp
; /* can be NULL */
603 parent
= chain
->parent
;
606 * WARNING! chain's spin lock is still held here, and other spinlocks
607 * will be acquired and released in the code below. We
608 * cannot be making fancy procedure calls!
612 * We can cache the chain if it is associated with a pmp
613 * and not flagged as being destroyed or requesting a full
614 * release. In this situation the chain is not removed
615 * from its parent, i.e. it can still be looked up.
617 * We intentionally do not cache DATA chains because these
618 * were likely used to load data into the logical buffer cache
619 * and will not be accessed again for some time.
622 (HAMMER2_CHAIN_DESTROY
| HAMMER2_CHAIN_RELEASE
)) == 0 &&
624 chain
->bref
.type
!= HAMMER2_BREF_TYPE_DATA
) {
626 hammer2_spin_ex(&parent
->core
.spin
);
627 if (atomic_cmpset_int(&chain
->refs
, 1, 0) == 0) {
629 * 1->0 transition failed, retry. Do not drop
630 * the chain's data yet!
633 hammer2_spin_unex(&parent
->core
.spin
);
634 hammer2_spin_unex(&chain
->core
.spin
);
640 * Success, be sure to clean out the chain's data
641 * before putting it on a queue that it might be
644 dio
= hammer2_chain_drop_data(chain
, 1);
646 KKASSERT((chain
->flags
& HAMMER2_CHAIN_ONLRU
) == 0);
647 hammer2_spin_ex(&pmp
->lru_spin
);
648 atomic_set_int(&chain
->flags
, HAMMER2_CHAIN_ONLRU
);
649 TAILQ_INSERT_TAIL(&pmp
->lru_list
, chain
, lru_node
);
652 * If we are over the LRU limit we need to drop something.
654 if (pmp
->lru_count
> HAMMER2_LRU_LIMIT
) {
655 rdrop
= TAILQ_FIRST(&pmp
->lru_list
);
656 atomic_clear_int(&rdrop
->flags
, HAMMER2_CHAIN_ONLRU
);
657 TAILQ_REMOVE(&pmp
->lru_list
, rdrop
, lru_node
);
658 atomic_add_int(&rdrop
->refs
, 1);
659 atomic_set_int(&rdrop
->flags
, HAMMER2_CHAIN_RELEASE
);
661 atomic_add_int(&pmp
->lru_count
, 1);
663 hammer2_spin_unex(&pmp
->lru_spin
);
665 hammer2_spin_unex(&parent
->core
.spin
);
666 parent
= NULL
; /* safety */
668 hammer2_spin_unex(&chain
->core
.spin
);
670 hammer2_io_bqrelse(&dio
);
677 * Spinlock the parent and try to drop the last ref on chain.
678 * On success determine if we should dispose of the chain
679 * (remove the chain from its parent, etc).
681 * (normal core locks are top-down recursive but we define
682 * core spinlocks as bottom-up recursive, so this is safe).
685 hammer2_spin_ex(&parent
->core
.spin
);
686 if (atomic_cmpset_int(&chain
->refs
, 1, 0) == 0) {
688 /* XXX remove, don't try to drop data on fail */
689 hammer2_spin_unex(&parent
->core
.spin
);
690 dio
= hammer2_chain_drop_data(chain
, 0);
691 hammer2_spin_unex(&chain
->core
.spin
);
693 hammer2_io_bqrelse(&dio
);
696 * 1->0 transition failed, retry.
698 hammer2_spin_unex(&parent
->core
.spin
);
699 hammer2_spin_unex(&chain
->core
.spin
);
705 * 1->0 transition successful, remove chain from the
708 if (chain
->flags
& HAMMER2_CHAIN_ONRBTREE
) {
709 RB_REMOVE(hammer2_chain_tree
,
710 &parent
->core
.rbtree
, chain
);
711 atomic_clear_int(&chain
->flags
, HAMMER2_CHAIN_ONRBTREE
);
712 --parent
->core
.chain_count
;
713 chain
->parent
= NULL
;
717 * If our chain was the last chain in the parent's core the
718 * core is now empty and its parent might have to be
719 * re-dropped if it has 0 refs.
721 if (parent
->core
.chain_count
== 0) {
723 atomic_add_int(&rdrop
->refs
, 1);
725 if (atomic_cmpset_int(&rdrop->refs, 0, 1) == 0)
729 hammer2_spin_unex(&parent
->core
.spin
);
730 parent
= NULL
; /* safety */
735 * Successful 1->0 transition and the chain can be destroyed now.
737 * We still have the core spinlock, and core's chain_count is 0.
738 * Any parent spinlock is gone.
740 hammer2_spin_unex(&chain
->core
.spin
);
741 KKASSERT(RB_EMPTY(&chain
->core
.rbtree
) &&
742 chain
->core
.chain_count
== 0);
745 * All spin locks are gone, no pointers remain to the chain, finish
748 KKASSERT((chain
->flags
& (HAMMER2_CHAIN_UPDATE
|
749 HAMMER2_CHAIN_MODIFIED
)) == 0);
750 dio
= hammer2_chain_drop_data(chain
, 1);
752 hammer2_io_bqrelse(&dio
);
755 * Once chain resources are gone we can use the now dead chain
756 * structure to placehold what might otherwise require a recursive
757 * drop, because we have potentially two things to drop and can only
758 * return one directly.
760 if (chain
->flags
& HAMMER2_CHAIN_ALLOCATED
) {
761 atomic_clear_int(&chain
->flags
, HAMMER2_CHAIN_ALLOCATED
);
763 kfree(chain
, hmp
->mchain
);
767 * Possible chaining loop when parent re-drop needed.
773 * On either last lock release or last drop
775 static hammer2_io_t
*
776 hammer2_chain_drop_data(hammer2_chain_t
*chain
, int lastdrop
)
780 if ((dio
= chain
->dio
) != NULL
) {
784 switch(chain
->bref
.type
) {
785 case HAMMER2_BREF_TYPE_VOLUME
:
786 case HAMMER2_BREF_TYPE_FREEMAP
:
791 if (chain
->data
!= NULL
) {
792 hammer2_spin_unex(&chain
->core
.spin
);
793 panic("chain data not null");
795 KKASSERT(chain
->data
== NULL
);
803 * Lock a referenced chain element, acquiring its data with I/O if necessary,
804 * and specify how you would like the data to be resolved.
806 * If an I/O or other fatal error occurs, chain->error will be set to non-zero.
808 * The lock is allowed to recurse, multiple locking ops will aggregate
809 * the requested resolve types. Once data is assigned it will not be
810 * removed until the last unlock.
812 * HAMMER2_RESOLVE_NEVER - Do not resolve the data element.
813 * (typically used to avoid device/logical buffer
816 * HAMMER2_RESOLVE_MAYBE - Do not resolve data elements for chains in
817 * the INITIAL-create state (indirect blocks only).
819 * Do not resolve data elements for DATA chains.
820 * (typically used to avoid device/logical buffer
823 * HAMMER2_RESOLVE_ALWAYS- Always resolve the data element.
825 * HAMMER2_RESOLVE_SHARED- (flag) The chain is locked shared, otherwise
826 * it will be locked exclusive.
828 * NOTE: Embedded elements (volume header, inodes) are always resolved
831 * NOTE: Specifying HAMMER2_RESOLVE_ALWAYS on a newly-created non-embedded
832 * element will instantiate and zero its buffer, and flush it on
835 * NOTE: (data) elements are normally locked RESOLVE_NEVER or RESOLVE_MAYBE
836 * so as not to instantiate a device buffer, which could alias against
837 * a logical file buffer. However, if ALWAYS is specified the
838 * device buffer will be instantiated anyway.
840 * WARNING! This function blocks on I/O if data needs to be fetched. This
841 * blocking can run concurrent with other compatible lock holders
842 * who do not need data returning. The lock is not upgraded to
843 * exclusive during a data fetch, a separate bit is used to
844 * interlock I/O. However, an exclusive lock holder can still count
845 * on being interlocked against an I/O fetch managed by a shared
849 hammer2_chain_lock(hammer2_chain_t
*chain
, int how
)
852 * Ref and lock the element. Recursive locks are allowed.
854 KKASSERT(chain
->refs
> 0);
855 atomic_add_int(&chain
->lockcnt
, 1);
860 * Get the appropriate lock. If LOCKAGAIN is flagged with SHARED
861 * the caller expects a shared lock to already be present and we
862 * are giving it another ref. This case must importantly not block
863 * if there is a pending exclusive lock request.
865 if (how
& HAMMER2_RESOLVE_SHARED
) {
866 if (how
& HAMMER2_RESOLVE_LOCKAGAIN
) {
867 hammer2_mtx_sh_again(&chain
->lock
);
869 hammer2_mtx_sh(&chain
->lock
);
872 hammer2_mtx_ex(&chain
->lock
);
874 ++curthread
->td_tracker
;
878 * If we already have a valid data pointer no further action is
886 * Do we have to resolve the data? This is generally only
887 * applicable to HAMMER2_BREF_TYPE_DATA which is special-cased.
888 * Other BREF types expects the data to be there.
890 switch(how
& HAMMER2_RESOLVE_MASK
) {
891 case HAMMER2_RESOLVE_NEVER
:
893 case HAMMER2_RESOLVE_MAYBE
:
894 if (chain
->flags
& HAMMER2_CHAIN_INITIAL
)
896 if (chain
->bref
.type
== HAMMER2_BREF_TYPE_DATA
)
899 if (chain
->bref
.type
== HAMMER2_BREF_TYPE_FREEMAP_NODE
)
901 if (chain
->bref
.type
== HAMMER2_BREF_TYPE_FREEMAP_LEAF
)
905 case HAMMER2_RESOLVE_ALWAYS
:
911 * Caller requires data
913 hammer2_chain_load_data(chain
);
917 * Lock the chain, retain the hold, and drop the data persistence count.
918 * The data should remain valid because we never transitioned lockcnt
922 hammer2_chain_lock_unhold(hammer2_chain_t
*chain
, int how
)
924 hammer2_chain_lock(chain
, how
);
925 atomic_add_int(&chain
->lockcnt
, -1);
930 * Downgrade an exclusive chain lock to a shared chain lock.
932 * NOTE: There is no upgrade equivalent due to the ease of
933 * deadlocks in that direction.
936 hammer2_chain_lock_downgrade(hammer2_chain_t
*chain
)
938 hammer2_mtx_downgrade(&chain
->lock
);
944 * Obtains a second shared lock on the chain, does not account the second
945 * shared lock as being owned by the current thread.
947 * Caller must already own a shared lock on this chain.
949 * The lock function is required to obtain the second shared lock without
950 * blocking on pending exclusive requests.
953 hammer2_chain_push_shared_lock(hammer2_chain_t
*chain
)
955 hammer2_mtx_sh_again(&chain
->lock
);
956 atomic_add_int(&chain
->lockcnt
, 1);
957 /* do not count in td_tracker for this thread */
961 * Accounts for a shared lock that was pushed to us as being owned by our
965 hammer2_chain_pull_shared_lock(hammer2_chain_t
*chain
)
967 ++curthread
->td_tracker
;
972 * Issue I/O and install chain->data. Caller must hold a chain lock, lock
973 * may be of any type.
975 * Once chain->data is set it cannot be disposed of until all locks are
979 hammer2_chain_load_data(hammer2_chain_t
*chain
)
981 hammer2_blockref_t
*bref
;
988 * Degenerate case, data already present, or chain is not expected
993 if ((chain
->bref
.data_off
& HAMMER2_OFF_MASK_RADIX
) == 0)
998 KKASSERT(hmp
!= NULL
);
1001 * Gain the IOINPROG bit, interlocked block.
1007 oflags
= chain
->flags
;
1009 if (oflags
& HAMMER2_CHAIN_IOINPROG
) {
1010 nflags
= oflags
| HAMMER2_CHAIN_IOSIGNAL
;
1011 tsleep_interlock(&chain
->flags
, 0);
1012 if (atomic_cmpset_int(&chain
->flags
, oflags
, nflags
)) {
1013 tsleep(&chain
->flags
, PINTERLOCKED
,
1018 nflags
= oflags
| HAMMER2_CHAIN_IOINPROG
;
1019 if (atomic_cmpset_int(&chain
->flags
, oflags
, nflags
)) {
1028 * We own CHAIN_IOINPROG
1030 * Degenerate case if we raced another load.
1036 * We must resolve to a device buffer, either by issuing I/O or
1037 * by creating a zero-fill element. We do not mark the buffer
1038 * dirty when creating a zero-fill element (the hammer2_chain_modify()
1039 * API must still be used to do that).
1041 * The device buffer is variable-sized in powers of 2 down
1042 * to HAMMER2_MIN_ALLOC (typically 1K). A 64K physical storage
1043 * chunk always contains buffers of the same size. (XXX)
1045 * The minimum physical IO size may be larger than the variable
1048 bref
= &chain
->bref
;
1051 * The getblk() optimization can only be used on newly created
1052 * elements if the physical block size matches the request.
1054 if (chain
->flags
& HAMMER2_CHAIN_INITIAL
) {
1055 error
= hammer2_io_new(hmp
, bref
->type
,
1056 bref
->data_off
, chain
->bytes
,
1059 error
= hammer2_io_bread(hmp
, bref
->type
,
1060 bref
->data_off
, chain
->bytes
,
1062 hammer2_adjreadcounter(&chain
->bref
, chain
->bytes
);
1066 chain
->error
= HAMMER2_ERROR_IO
;
1067 kprintf("hammer2_chain_lock: I/O error %016jx: %d\n",
1068 (intmax_t)bref
->data_off
, error
);
1069 hammer2_io_bqrelse(&chain
->dio
);
1075 * This isn't perfect and can be ignored on OSs which do not have
1076 * an indication as to whether a buffer is coming from cache or
1077 * if I/O was actually issued for the read. TESTEDGOOD will work
1078 * pretty well without the B_IOISSUED logic because chains are
1081 * If the underlying kernel buffer covers the entire chain we can
1082 * use the B_IOISSUED indication to determine if we have to re-run
1083 * the CRC on chain data for chains that managed to stay cached
1084 * across the kernel disposal of the original buffer.
1086 if ((dio
= chain
->dio
) != NULL
&& dio
->bp
) {
1087 struct buf
*bp
= dio
->bp
;
1089 if (dio
->psize
== chain
->bytes
&&
1090 (bp
->b_flags
& B_IOISSUED
)) {
1091 atomic_clear_int(&chain
->flags
,
1092 HAMMER2_CHAIN_TESTEDGOOD
);
1093 bp
->b_flags
&= ~B_IOISSUED
;
1098 * NOTE: A locked chain's data cannot be modified without first
1099 * calling hammer2_chain_modify().
1103 * Clear INITIAL. In this case we used io_new() and the buffer has
1104 * been zero'd and marked dirty.
1106 bdata
= hammer2_io_data(chain
->dio
, chain
->bref
.data_off
);
1108 if (chain
->flags
& HAMMER2_CHAIN_INITIAL
) {
1109 atomic_clear_int(&chain
->flags
, HAMMER2_CHAIN_INITIAL
);
1110 chain
->bref
.flags
|= HAMMER2_BREF_FLAG_ZERO
;
1111 } else if (chain
->flags
& HAMMER2_CHAIN_MODIFIED
) {
1113 * check data not currently synchronized due to
1114 * modification. XXX assumes data stays in the buffer
1115 * cache, which might not be true (need biodep on flush
1116 * to calculate crc? or simple crc?).
1118 } else if ((chain
->flags
& HAMMER2_CHAIN_TESTEDGOOD
) == 0) {
1120 if (hammer2_chain_testcheck(chain
, bdata
) == 0) {
1121 chain
->error
= HAMMER2_ERROR_CHECK
;
1123 atomic_set_int(&chain
->flags
, HAMMER2_CHAIN_TESTEDGOOD
);
1129 * Setup the data pointer, either pointing it to an embedded data
1130 * structure and copying the data from the buffer, or pointing it
1133 * The buffer is not retained when copying to an embedded data
1134 * structure in order to avoid potential deadlocks or recursions
1135 * on the same physical buffer.
1137 * WARNING! Other threads can start using the data the instant we
1138 * set chain->data non-NULL.
1140 switch (bref
->type
) {
1141 case HAMMER2_BREF_TYPE_VOLUME
:
1142 case HAMMER2_BREF_TYPE_FREEMAP
:
1144 * Copy data from bp to embedded buffer
1146 panic("hammer2_chain_load_data: unresolved volume header");
1148 case HAMMER2_BREF_TYPE_DIRENT
:
1149 KKASSERT(chain
->bytes
!= 0);
1151 case HAMMER2_BREF_TYPE_INODE
:
1152 case HAMMER2_BREF_TYPE_FREEMAP_LEAF
:
1153 case HAMMER2_BREF_TYPE_INDIRECT
:
1154 case HAMMER2_BREF_TYPE_DATA
:
1155 case HAMMER2_BREF_TYPE_FREEMAP_NODE
:
1158 * Point data at the device buffer and leave dio intact.
1160 chain
->data
= (void *)bdata
;
1165 * Release HAMMER2_CHAIN_IOINPROG and signal waiters if requested.
1172 oflags
= chain
->flags
;
1173 nflags
= oflags
& ~(HAMMER2_CHAIN_IOINPROG
|
1174 HAMMER2_CHAIN_IOSIGNAL
);
1175 KKASSERT(oflags
& HAMMER2_CHAIN_IOINPROG
);
1176 if (atomic_cmpset_int(&chain
->flags
, oflags
, nflags
)) {
1177 if (oflags
& HAMMER2_CHAIN_IOSIGNAL
)
1178 wakeup(&chain
->flags
);
1186 * Unlock and deref a chain element.
1188 * Remember that the presence of children under chain prevent the chain's
1189 * destruction but do not add additional references, so the dio will still
1193 hammer2_chain_unlock(hammer2_chain_t
*chain
)
1199 --curthread
->td_tracker
;
1202 * If multiple locks are present (or being attempted) on this
1203 * particular chain we can just unlock, drop refs, and return.
1205 * Otherwise fall-through on the 1->0 transition.
1208 lockcnt
= chain
->lockcnt
;
1209 KKASSERT(lockcnt
> 0);
1212 if (atomic_cmpset_int(&chain
->lockcnt
,
1213 lockcnt
, lockcnt
- 1)) {
1214 hammer2_mtx_unlock(&chain
->lock
);
1217 } else if (hammer2_mtx_upgrade_try(&chain
->lock
) == 0) {
1218 /* while holding the mutex exclusively */
1219 if (atomic_cmpset_int(&chain
->lockcnt
, 1, 0))
1223 * This situation can easily occur on SMP due to
1224 * the gap inbetween the 1->0 transition and the
1225 * final unlock. We cannot safely block on the
1226 * mutex because lockcnt might go above 1.
1228 * XXX Sleep for one tick if it takes too long.
1230 if (++iter
> 1000) {
1231 if (iter
> 1000 + hz
) {
1232 kprintf("hammer2: h2race2 %p\n", chain
);
1235 tsleep(&iter
, 0, "h2race2", 1);
1243 * Disassociate the data on the last unlock. Requires that we hold
1244 * the mutex exclusively.
1246 dio
= hammer2_chain_drop_data(chain
, 0);
1248 hammer2_io_bqrelse(&dio
);
1249 hammer2_mtx_unlock(&chain
->lock
);
1253 * Unlock and hold chain data intact
1256 hammer2_chain_unlock_hold(hammer2_chain_t
*chain
)
1258 atomic_add_int(&chain
->lockcnt
, 1);
1259 hammer2_chain_unlock(chain
);
1263 * Helper to obtain the blockref[] array base and count for a chain.
1265 * XXX Not widely used yet, various use cases need to be validated and
1266 * converted to use this function.
1269 hammer2_blockref_t
*
1270 hammer2_chain_base_and_count(hammer2_chain_t
*parent
, int *countp
)
1272 hammer2_blockref_t
*base
;
1275 if (parent
->flags
& HAMMER2_CHAIN_INITIAL
) {
1278 switch(parent
->bref
.type
) {
1279 case HAMMER2_BREF_TYPE_INODE
:
1280 count
= HAMMER2_SET_COUNT
;
1282 case HAMMER2_BREF_TYPE_INDIRECT
:
1283 case HAMMER2_BREF_TYPE_FREEMAP_NODE
:
1284 count
= parent
->bytes
/ sizeof(hammer2_blockref_t
);
1286 case HAMMER2_BREF_TYPE_VOLUME
:
1287 count
= HAMMER2_SET_COUNT
;
1289 case HAMMER2_BREF_TYPE_FREEMAP
:
1290 count
= HAMMER2_SET_COUNT
;
1293 panic("hammer2_chain_create_indirect: "
1294 "unrecognized blockref type: %d",
1300 switch(parent
->bref
.type
) {
1301 case HAMMER2_BREF_TYPE_INODE
:
1302 base
= &parent
->data
->ipdata
.u
.blockset
.blockref
[0];
1303 count
= HAMMER2_SET_COUNT
;
1305 case HAMMER2_BREF_TYPE_INDIRECT
:
1306 case HAMMER2_BREF_TYPE_FREEMAP_NODE
:
1307 base
= &parent
->data
->npdata
[0];
1308 count
= parent
->bytes
/ sizeof(hammer2_blockref_t
);
1310 case HAMMER2_BREF_TYPE_VOLUME
:
1311 base
= &parent
->data
->voldata
.
1312 sroot_blockset
.blockref
[0];
1313 count
= HAMMER2_SET_COUNT
;
1315 case HAMMER2_BREF_TYPE_FREEMAP
:
1316 base
= &parent
->data
->blkset
.blockref
[0];
1317 count
= HAMMER2_SET_COUNT
;
1320 panic("hammer2_chain_create_indirect: "
1321 "unrecognized blockref type: %d",
1333 * This counts the number of live blockrefs in a block array and
1334 * also calculates the point at which all remaining blockrefs are empty.
1335 * This routine can only be called on a live chain.
1337 * NOTE: Flag is not set until after the count is complete, allowing
1338 * callers to test the flag without holding the spinlock.
1340 * NOTE: If base is NULL the related chain is still in the INITIAL
1341 * state and there are no blockrefs to count.
1343 * NOTE: live_count may already have some counts accumulated due to
1344 * creation and deletion and could even be initially negative.
1347 hammer2_chain_countbrefs(hammer2_chain_t
*chain
,
1348 hammer2_blockref_t
*base
, int count
)
1350 hammer2_spin_ex(&chain
->core
.spin
);
1351 if ((chain
->flags
& HAMMER2_CHAIN_COUNTEDBREFS
) == 0) {
1353 while (--count
>= 0) {
1354 if (base
[count
].type
)
1357 chain
->core
.live_zero
= count
+ 1;
1358 while (count
>= 0) {
1359 if (base
[count
].type
)
1360 atomic_add_int(&chain
->core
.live_count
,
1365 chain
->core
.live_zero
= 0;
1367 /* else do not modify live_count */
1368 atomic_set_int(&chain
->flags
, HAMMER2_CHAIN_COUNTEDBREFS
);
1370 hammer2_spin_unex(&chain
->core
.spin
);
1374 * Resize the chain's physical storage allocation in-place. This function does
1375 * not usually adjust the data pointer and must be followed by (typically) a
1376 * hammer2_chain_modify() call to copy any old data over and adjust the
1379 * Chains can be resized smaller without reallocating the storage. Resizing
1380 * larger will reallocate the storage. Excess or prior storage is reclaimed
1381 * asynchronously at a later time.
1383 * An nradix value of 0 is special-cased to mean that the storage should
1384 * be disassociated, that is the chain is being resized to 0 bytes (not 1
1387 * Must be passed an exclusively locked parent and chain.
1389 * This function is mostly used with DATA blocks locked RESOLVE_NEVER in order
1390 * to avoid instantiating a device buffer that conflicts with the vnode data
1391 * buffer. However, because H2 can compress or encrypt data, the chain may
1392 * have a dio assigned to it in those situations, and they do not conflict.
1394 * XXX return error if cannot resize.
1397 hammer2_chain_resize(hammer2_chain_t
*chain
,
1398 hammer2_tid_t mtid
, hammer2_off_t dedup_off
,
1399 int nradix
, int flags
)
1408 * Only data and indirect blocks can be resized for now.
1409 * (The volu root, inodes, and freemap elements use a fixed size).
1411 KKASSERT(chain
!= &hmp
->vchain
);
1412 KKASSERT(chain
->bref
.type
== HAMMER2_BREF_TYPE_DATA
||
1413 chain
->bref
.type
== HAMMER2_BREF_TYPE_INDIRECT
||
1414 chain
->bref
.type
== HAMMER2_BREF_TYPE_DIRENT
);
1417 * Nothing to do if the element is already the proper size
1419 obytes
= chain
->bytes
;
1420 nbytes
= (nradix
) ? (1U << nradix
) : 0;
1421 if (obytes
== nbytes
)
1425 * Make sure the old data is instantiated so we can copy it. If this
1426 * is a data block, the device data may be superfluous since the data
1427 * might be in a logical block, but compressed or encrypted data is
1430 * NOTE: The modify will set BMAPUPD for us if BMAPPED is set.
1432 hammer2_chain_modify(chain
, mtid
, dedup_off
, 0);
1435 * Relocate the block, even if making it smaller (because different
1436 * block sizes may be in different regions).
1438 * NOTE: Operation does not copy the data and may only be used
1439 * to resize data blocks in-place, or directory entry blocks
1440 * which are about to be modified in some manner.
1442 hammer2_freemap_alloc(chain
, nbytes
);
1443 chain
->bytes
= nbytes
;
1446 * We don't want the followup chain_modify() to try to copy data
1447 * from the old (wrong-sized) buffer. It won't know how much to
1448 * copy. This case should only occur during writes when the
1449 * originator already has the data to write in-hand.
1452 KKASSERT(chain
->bref
.type
== HAMMER2_BREF_TYPE_DATA
||
1453 chain
->bref
.type
== HAMMER2_BREF_TYPE_DIRENT
);
1454 hammer2_io_brelse(&chain
->dio
);
1460 * Helper for chains already flagged as MODIFIED. A new allocation may
1461 * still be required if the existing one has already been used in a de-dup.
1465 modified_needs_new_allocation(hammer2_chain_t
*chain
)
1468 * We only live-dedup data, we do not live-dedup meta-data.
1470 if (chain
->bref
.type
!= HAMMER2_BREF_TYPE_DATA
&&
1471 chain
->bref
.type
!= HAMMER2_BREF_TYPE_DIRENT
) {
1476 * If chain has no data, then there is nothing to live-dedup.
1478 if (chain
->bytes
== 0)
1486 * If this flag is not set the current modification has not been
1487 * recorded for dedup so a new allocation is not needed. The
1488 * recording occurs when dirty file data is flushed from the frontend
1491 if (chain
->flags
& HAMMER2_CHAIN_DEDUP
)
1495 * If the DEDUP flag is set we have one final line of defense to
1496 * allow re-use of a modified buffer, and that is if the DIO_INVALOK
1497 * flag is still set on the underlying DIO. This flag is only set
1498 * for hammer2_io_new() buffers which cover the whole buffer (64KB),
1499 * and is cleared when a dedup operation actually decides to use
1503 if ((dio
= chain
->dio
) != NULL
) {
1504 if (dio
->refs
& HAMMER2_DIO_INVALOK
)
1507 dio
= hammer2_io_getquick(chain
->hmp
, chain
->bref
.data_off
,
1510 if (dio
->refs
& HAMMER2_DIO_INVALOK
) {
1511 hammer2_io_putblk(&dio
);
1514 hammer2_io_putblk(&dio
);
1522 * Set the chain modified so its data can be changed by the caller.
1524 * Sets bref.modify_tid to mtid only if mtid != 0. Note that bref.modify_tid
1525 * is a CLC (cluster level change) field and is not updated by parent
1526 * propagation during a flush.
1528 * If the caller passes a non-zero dedup_off we assign data_off to that
1529 * instead of allocating a ne block. Caller must not modify the data already
1530 * present at the target offset.
1533 hammer2_chain_modify(hammer2_chain_t
*chain
, hammer2_tid_t mtid
,
1534 hammer2_off_t dedup_off
, int flags
)
1536 hammer2_blockref_t obref
;
1545 obref
= chain
->bref
;
1546 KKASSERT((chain
->flags
& HAMMER2_CHAIN_FICTITIOUS
) == 0);
1549 * Data is not optional for freemap chains (we must always be sure
1550 * to copy the data on COW storage allocations).
1552 if (chain
->bref
.type
== HAMMER2_BREF_TYPE_FREEMAP_NODE
||
1553 chain
->bref
.type
== HAMMER2_BREF_TYPE_FREEMAP_LEAF
) {
1554 KKASSERT((chain
->flags
& HAMMER2_CHAIN_INITIAL
) ||
1555 (flags
& HAMMER2_MODIFY_OPTDATA
) == 0);
1559 * Data must be resolved if already assigned, unless explicitly
1560 * flagged otherwise.
1562 if (chain
->data
== NULL
&& chain
->bytes
!= 0 &&
1563 (flags
& HAMMER2_MODIFY_OPTDATA
) == 0 &&
1564 (chain
->bref
.data_off
& ~HAMMER2_OFF_MASK_RADIX
)) {
1565 hammer2_chain_load_data(chain
);
1569 * Set MODIFIED to indicate that the chain has been modified.
1570 * Set UPDATE to ensure that the blockref is updated in the parent.
1572 * If MODIFIED is already set determine if we can reuse the assigned
1573 * data block or if we need a new data block. The assigned data block
1574 * can be reused if HAMMER2_DIO_INVALOK is set on the dio.
1576 if ((chain
->flags
& HAMMER2_CHAIN_MODIFIED
) &&
1577 modified_needs_new_allocation(chain
)) {
1579 } else if ((chain
->flags
& HAMMER2_CHAIN_MODIFIED
) == 0) {
1581 * Must set modified bit.
1583 atomic_add_long(&hammer2_count_modified_chains
, 1);
1584 atomic_set_int(&chain
->flags
, HAMMER2_CHAIN_MODIFIED
);
1585 hammer2_pfs_memory_inc(chain
->pmp
); /* can be NULL */
1588 * We may be able to avoid a copy-on-write if the chain's
1589 * check mode is set to NONE and the chain's current
1590 * modify_tid is beyond the last explicit snapshot tid.
1592 * This implements HAMMER2's overwrite-in-place feature.
1594 * NOTE! This data-block cannot be used as a de-duplication
1595 * source when the check mode is set to NONE.
1597 if ((chain
->bref
.type
== HAMMER2_BREF_TYPE_DATA
||
1598 chain
->bref
.type
== HAMMER2_BREF_TYPE_DIRENT
) &&
1599 (chain
->flags
& HAMMER2_CHAIN_INITIAL
) == 0 &&
1600 HAMMER2_DEC_CHECK(chain
->bref
.methods
) ==
1601 HAMMER2_CHECK_NONE
&&
1603 chain
->bref
.modify_tid
>
1604 chain
->pmp
->iroot
->meta
.pfs_lsnap_tid
&&
1605 modified_needs_new_allocation(chain
) == 0) {
1607 * Sector overwrite allowed.
1612 * Sector overwrite not allowed, must copy-on-write.
1618 * Already flagged modified, no new allocation is needed.
1624 * Flag parent update required.
1626 if ((chain
->flags
& HAMMER2_CHAIN_UPDATE
) == 0)
1627 atomic_set_int(&chain
->flags
, HAMMER2_CHAIN_UPDATE
);
1630 * The modification or re-modification requires an allocation and
1633 * If dedup_off is non-zero, caller already has a data offset
1634 * containing the caller's desired data. The dedup offset is
1635 * allowed to be in a partially free state and we must be sure
1636 * to reset it to a fully allocated state to force two bulkfree
1637 * passes to free it again. The chain will not be marked MODIFIED
1638 * in the dedup case, as the dedup data cannot be changed without
1641 * NOTE: Only applicable when chain->bytes != 0.
1643 * XXX can a chain already be marked MODIFIED without a data
1644 * assignment? If not, assert here instead of testing the case.
1646 if (chain
!= &hmp
->vchain
&& chain
!= &hmp
->fchain
&&
1648 if ((chain
->bref
.data_off
& ~HAMMER2_OFF_MASK_RADIX
) == 0 ||
1651 hammer2_io_dedup_delete(chain
->hmp
,
1653 chain
->bref
.data_off
,
1656 chain
->bref
.data_off
= dedup_off
;
1657 chain
->bytes
= 1 << (dedup_off
&
1658 HAMMER2_OFF_MASK_RADIX
);
1659 atomic_clear_int(&chain
->flags
,
1660 HAMMER2_CHAIN_MODIFIED
);
1661 atomic_add_long(&hammer2_count_modified_chains
,
1664 hammer2_pfs_memory_wakeup(chain
->pmp
);
1665 hammer2_freemap_adjust(hmp
, &chain
->bref
,
1666 HAMMER2_FREEMAP_DORECOVER
);
1668 hammer2_freemap_alloc(chain
, chain
->bytes
);
1670 /* XXX failed allocation */
1675 * Update mirror_tid and modify_tid. modify_tid is only updated
1676 * if not passed as zero (during flushes, parent propagation passes
1679 * NOTE: chain->pmp could be the device spmp.
1681 chain
->bref
.mirror_tid
= hmp
->voldata
.mirror_tid
+ 1;
1683 chain
->bref
.modify_tid
= mtid
;
1686 * Set BMAPUPD to tell the flush code that an existing blockmap entry
1687 * requires updating as well as to tell the delete code that the
1688 * chain's blockref might not exactly match (in terms of physical size
1689 * or block offset) the one in the parent's blocktable. The base key
1690 * of course will still match.
1692 if (chain
->flags
& HAMMER2_CHAIN_BMAPPED
)
1693 atomic_set_int(&chain
->flags
, HAMMER2_CHAIN_BMAPUPD
);
1696 * Short-cut data blocks which the caller does not need an actual
1697 * data reference to (aka OPTDATA), as long as the chain does not
1698 * already have a data pointer to the data. This generally means
1699 * that the modifications are being done via the logical buffer cache.
1700 * The INITIAL flag relates only to the device data buffer and thus
1701 * remains unchange in this situation.
1703 * This code also handles bytes == 0 (most dirents).
1705 if (chain
->bref
.type
== HAMMER2_BREF_TYPE_DATA
&&
1706 (flags
& HAMMER2_MODIFY_OPTDATA
) &&
1707 chain
->data
== NULL
) {
1708 KKASSERT(chain
->dio
== NULL
);
1713 * Clearing the INITIAL flag (for indirect blocks) indicates that
1714 * we've processed the uninitialized storage allocation.
1716 * If this flag is already clear we are likely in a copy-on-write
1717 * situation but we have to be sure NOT to bzero the storage if
1718 * no data is present.
1720 if (chain
->flags
& HAMMER2_CHAIN_INITIAL
) {
1721 atomic_clear_int(&chain
->flags
, HAMMER2_CHAIN_INITIAL
);
1728 * Instantiate data buffer and possibly execute COW operation
1730 switch(chain
->bref
.type
) {
1731 case HAMMER2_BREF_TYPE_VOLUME
:
1732 case HAMMER2_BREF_TYPE_FREEMAP
:
1734 * The data is embedded, no copy-on-write operation is
1737 KKASSERT(chain
->dio
== NULL
);
1739 case HAMMER2_BREF_TYPE_DIRENT
:
1741 * The data might be fully embedded.
1743 if (chain
->bytes
== 0) {
1744 KKASSERT(chain
->dio
== NULL
);
1748 case HAMMER2_BREF_TYPE_INODE
:
1749 case HAMMER2_BREF_TYPE_FREEMAP_LEAF
:
1750 case HAMMER2_BREF_TYPE_DATA
:
1751 case HAMMER2_BREF_TYPE_INDIRECT
:
1752 case HAMMER2_BREF_TYPE_FREEMAP_NODE
:
1754 * Perform the copy-on-write operation
1756 * zero-fill or copy-on-write depending on whether
1757 * chain->data exists or not and set the dirty state for
1758 * the new buffer. hammer2_io_new() will handle the
1761 * If a dedup_off was supplied this is an existing block
1762 * and no COW, copy, or further modification is required.
1764 KKASSERT(chain
!= &hmp
->vchain
&& chain
!= &hmp
->fchain
);
1766 if (wasinitial
&& dedup_off
== 0) {
1767 error
= hammer2_io_new(hmp
, chain
->bref
.type
,
1768 chain
->bref
.data_off
,
1769 chain
->bytes
, &dio
);
1771 error
= hammer2_io_bread(hmp
, chain
->bref
.type
,
1772 chain
->bref
.data_off
,
1773 chain
->bytes
, &dio
);
1775 hammer2_adjreadcounter(&chain
->bref
, chain
->bytes
);
1778 * If an I/O error occurs make sure callers cannot accidently
1779 * modify the old buffer's contents and corrupt the filesystem.
1782 kprintf("hammer2_chain_modify: hmp=%p I/O error\n",
1784 chain
->error
= HAMMER2_ERROR_IO
;
1785 hammer2_io_brelse(&dio
);
1786 hammer2_io_brelse(&chain
->dio
);
1791 bdata
= hammer2_io_data(dio
, chain
->bref
.data_off
);
1795 * COW (unless a dedup).
1797 KKASSERT(chain
->dio
!= NULL
);
1798 if (chain
->data
!= (void *)bdata
&& dedup_off
== 0) {
1799 bcopy(chain
->data
, bdata
, chain
->bytes
);
1801 } else if (wasinitial
== 0) {
1803 * We have a problem. We were asked to COW but
1804 * we don't have any data to COW with!
1806 panic("hammer2_chain_modify: having a COW %p\n",
1811 * Retire the old buffer, replace with the new. Dirty or
1812 * redirty the new buffer.
1814 * WARNING! The system buffer cache may have already flushed
1815 * the buffer, so we must be sure to [re]dirty it
1816 * for further modification.
1818 * If dedup_off was supplied, the caller is not
1819 * expected to make any further modification to the
1823 hammer2_io_bqrelse(&chain
->dio
);
1824 chain
->data
= (void *)bdata
;
1827 hammer2_io_setdirty(dio
);
1830 panic("hammer2_chain_modify: illegal non-embedded type %d",
1837 * setflush on parent indicating that the parent must recurse down
1838 * to us. Do not call on chain itself which might already have it
1842 hammer2_chain_setflush(chain
->parent
);
1846 * Modify the chain associated with an inode.
1849 hammer2_chain_modify_ip(hammer2_inode_t
*ip
, hammer2_chain_t
*chain
,
1850 hammer2_tid_t mtid
, int flags
)
1852 hammer2_inode_modify(ip
);
1853 hammer2_chain_modify(chain
, mtid
, 0, flags
);
1857 * Volume header data locks
1860 hammer2_voldata_lock(hammer2_dev_t
*hmp
)
1862 lockmgr(&hmp
->vollk
, LK_EXCLUSIVE
);
1866 hammer2_voldata_unlock(hammer2_dev_t
*hmp
)
1868 lockmgr(&hmp
->vollk
, LK_RELEASE
);
1872 hammer2_voldata_modify(hammer2_dev_t
*hmp
)
1874 if ((hmp
->vchain
.flags
& HAMMER2_CHAIN_MODIFIED
) == 0) {
1875 atomic_add_long(&hammer2_count_modified_chains
, 1);
1876 atomic_set_int(&hmp
->vchain
.flags
, HAMMER2_CHAIN_MODIFIED
);
1877 hammer2_pfs_memory_inc(hmp
->vchain
.pmp
);
1882 * This function returns the chain at the nearest key within the specified
1883 * range. The returned chain will be referenced but not locked.
1885 * This function will recurse through chain->rbtree as necessary and will
1886 * return a *key_nextp suitable for iteration. *key_nextp is only set if
1887 * the iteration value is less than the current value of *key_nextp.
1889 * The caller should use (*key_nextp) to calculate the actual range of
1890 * the returned element, which will be (key_beg to *key_nextp - 1), because
1891 * there might be another element which is superior to the returned element
1894 * (*key_nextp) can be passed as key_beg in an iteration only while non-NULL
1895 * chains continue to be returned. On EOF (*key_nextp) may overflow since
1896 * it will wind up being (key_end + 1).
1898 * WARNING! Must be called with child's spinlock held. Spinlock remains
1899 * held through the operation.
1901 struct hammer2_chain_find_info
{
1902 hammer2_chain_t
*best
;
1903 hammer2_key_t key_beg
;
1904 hammer2_key_t key_end
;
1905 hammer2_key_t key_next
;
1908 static int hammer2_chain_find_cmp(hammer2_chain_t
*child
, void *data
);
1909 static int hammer2_chain_find_callback(hammer2_chain_t
*child
, void *data
);
1913 hammer2_chain_find(hammer2_chain_t
*parent
, hammer2_key_t
*key_nextp
,
1914 hammer2_key_t key_beg
, hammer2_key_t key_end
)
1916 struct hammer2_chain_find_info info
;
1919 info
.key_beg
= key_beg
;
1920 info
.key_end
= key_end
;
1921 info
.key_next
= *key_nextp
;
1923 RB_SCAN(hammer2_chain_tree
, &parent
->core
.rbtree
,
1924 hammer2_chain_find_cmp
, hammer2_chain_find_callback
,
1926 *key_nextp
= info
.key_next
;
1928 kprintf("chain_find %p %016jx:%016jx next=%016jx\n",
1929 parent
, key_beg
, key_end
, *key_nextp
);
1937 hammer2_chain_find_cmp(hammer2_chain_t
*child
, void *data
)
1939 struct hammer2_chain_find_info
*info
= data
;
1940 hammer2_key_t child_beg
;
1941 hammer2_key_t child_end
;
1943 child_beg
= child
->bref
.key
;
1944 child_end
= child_beg
+ ((hammer2_key_t
)1 << child
->bref
.keybits
) - 1;
1946 if (child_end
< info
->key_beg
)
1948 if (child_beg
> info
->key_end
)
1955 hammer2_chain_find_callback(hammer2_chain_t
*child
, void *data
)
1957 struct hammer2_chain_find_info
*info
= data
;
1958 hammer2_chain_t
*best
;
1959 hammer2_key_t child_end
;
1962 * WARNING! Layerq is scanned forwards, exact matches should keep
1963 * the existing info->best.
1965 if ((best
= info
->best
) == NULL
) {
1967 * No previous best. Assign best
1970 } else if (best
->bref
.key
<= info
->key_beg
&&
1971 child
->bref
.key
<= info
->key_beg
) {
1976 /*info->best = child;*/
1977 } else if (child
->bref
.key
< best
->bref
.key
) {
1979 * Child has a nearer key and best is not flush with key_beg.
1980 * Set best to child. Truncate key_next to the old best key.
1983 if (info
->key_next
> best
->bref
.key
|| info
->key_next
== 0)
1984 info
->key_next
= best
->bref
.key
;
1985 } else if (child
->bref
.key
== best
->bref
.key
) {
1987 * If our current best is flush with the child then this
1988 * is an illegal overlap.
1990 * key_next will automatically be limited to the smaller of
1991 * the two end-points.
1997 * Keep the current best but truncate key_next to the child's
2000 * key_next will also automatically be limited to the smaller
2001 * of the two end-points (probably not necessary for this case
2002 * but we do it anyway).
2004 if (info
->key_next
> child
->bref
.key
|| info
->key_next
== 0)
2005 info
->key_next
= child
->bref
.key
;
2009 * Always truncate key_next based on child's end-of-range.
2011 child_end
= child
->bref
.key
+ ((hammer2_key_t
)1 << child
->bref
.keybits
);
2012 if (child_end
&& (info
->key_next
> child_end
|| info
->key_next
== 0))
2013 info
->key_next
= child_end
;
2019 * Retrieve the specified chain from a media blockref, creating the
2020 * in-memory chain structure which reflects it.
2022 * To handle insertion races pass the INSERT_RACE flag along with the
2023 * generation number of the core. NULL will be returned if the generation
2024 * number changes before we have a chance to insert the chain. Insert
2025 * races can occur because the parent might be held shared.
2027 * Caller must hold the parent locked shared or exclusive since we may
2028 * need the parent's bref array to find our block.
2030 * WARNING! chain->pmp is always set to NULL for any chain representing
2031 * part of the super-root topology.
2034 hammer2_chain_get(hammer2_chain_t
*parent
, int generation
,
2035 hammer2_blockref_t
*bref
)
2037 hammer2_dev_t
*hmp
= parent
->hmp
;
2038 hammer2_chain_t
*chain
;
2042 * Allocate a chain structure representing the existing media
2043 * entry. Resulting chain has one ref and is not locked.
2045 if (bref
->flags
& HAMMER2_BREF_FLAG_PFSROOT
)
2046 chain
= hammer2_chain_alloc(hmp
, NULL
, bref
);
2048 chain
= hammer2_chain_alloc(hmp
, parent
->pmp
, bref
);
2049 /* ref'd chain returned */
2052 * Flag that the chain is in the parent's blockmap so delete/flush
2053 * knows what to do with it.
2055 atomic_set_int(&chain
->flags
, HAMMER2_CHAIN_BMAPPED
);
2058 * Link the chain into its parent. A spinlock is required to safely
2059 * access the RBTREE, and it is possible to collide with another
2060 * hammer2_chain_get() operation because the caller might only hold
2061 * a shared lock on the parent.
2063 * NOTE: Get races can occur quite often when we distribute
2064 * asynchronous read-aheads across multiple threads.
2066 KKASSERT(parent
->refs
> 0);
2067 error
= hammer2_chain_insert(parent
, chain
,
2068 HAMMER2_CHAIN_INSERT_SPIN
|
2069 HAMMER2_CHAIN_INSERT_RACE
,
2072 KKASSERT((chain
->flags
& HAMMER2_CHAIN_ONRBTREE
) == 0);
2073 /*kprintf("chain %p get race\n", chain);*/
2074 hammer2_chain_drop(chain
);
2077 KKASSERT(chain
->flags
& HAMMER2_CHAIN_ONRBTREE
);
2081 * Return our new chain referenced but not locked, or NULL if
2088 * Lookup initialization/completion API
2091 hammer2_chain_lookup_init(hammer2_chain_t
*parent
, int flags
)
2093 hammer2_chain_ref(parent
);
2094 if (flags
& HAMMER2_LOOKUP_SHARED
) {
2095 hammer2_chain_lock(parent
, HAMMER2_RESOLVE_ALWAYS
|
2096 HAMMER2_RESOLVE_SHARED
);
2098 hammer2_chain_lock(parent
, HAMMER2_RESOLVE_ALWAYS
);
2104 hammer2_chain_lookup_done(hammer2_chain_t
*parent
)
2107 hammer2_chain_unlock(parent
);
2108 hammer2_chain_drop(parent
);
2113 hammer2_chain_getparent(hammer2_chain_t
**parentp
, int how
)
2115 hammer2_chain_t
*oparent
;
2116 hammer2_chain_t
*nparent
;
2119 * Be careful of order, oparent must be unlocked before nparent
2120 * is locked below to avoid a deadlock.
2123 hammer2_spin_ex(&oparent
->core
.spin
);
2124 nparent
= oparent
->parent
;
2125 if (nparent
== NULL
) {
2126 hammer2_spin_unex(&oparent
->core
.spin
);
2127 panic("hammer2_chain_getparent: no parent");
2129 hammer2_chain_ref(nparent
);
2130 hammer2_spin_unex(&oparent
->core
.spin
);
2132 hammer2_chain_unlock(oparent
);
2133 hammer2_chain_drop(oparent
);
2137 hammer2_chain_lock(nparent
, how
);
2144 * Locate the first chain whos key range overlaps (key_beg, key_end) inclusive.
2145 * (*parentp) typically points to an inode but can also point to a related
2146 * indirect block and this function will recurse upwards and find the inode
2149 * (*parentp) must be exclusively locked and referenced and can be an inode
2150 * or an existing indirect block within the inode.
2152 * On return (*parentp) will be modified to point at the deepest parent chain
2153 * element encountered during the search, as a helper for an insertion or
2154 * deletion. The new (*parentp) will be locked and referenced and the old
2155 * will be unlocked and dereferenced (no change if they are both the same).
2157 * The matching chain will be returned exclusively locked. If NOLOCK is
2158 * requested the chain will be returned only referenced. Note that the
2159 * parent chain must always be locked shared or exclusive, matching the
2160 * HAMMER2_LOOKUP_SHARED flag. We can conceivably lock it SHARED temporarily
2161 * when NOLOCK is specified but that complicates matters if *parentp must
2162 * inherit the chain.
2164 * NOLOCK also implies NODATA, since an unlocked chain usually has a NULL
2165 * data pointer or can otherwise be in flux.
2167 * NULL is returned if no match was found, but (*parentp) will still
2168 * potentially be adjusted.
2170 * If a fatal error occurs (typically an I/O error), a dummy chain is
2171 * returned with chain->error and error-identifying information set. This
2172 * chain will assert if you try to do anything fancy with it.
2174 * XXX Depending on where the error occurs we should allow continued iteration.
2176 * On return (*key_nextp) will point to an iterative value for key_beg.
2177 * (If NULL is returned (*key_nextp) is set to (key_end + 1)).
2179 * This function will also recurse up the chain if the key is not within the
2180 * current parent's range. (*parentp) can never be set to NULL. An iteration
2181 * can simply allow (*parentp) to float inside the loop.
2183 * NOTE! chain->data is not always resolved. By default it will not be
2184 * resolved for BREF_TYPE_DATA, FREEMAP_NODE, or FREEMAP_LEAF. Use
2185 * HAMMER2_LOOKUP_ALWAYS to force resolution (but be careful w/
2186 * BREF_TYPE_DATA as the device buffer can alias the logical file
2191 hammer2_chain_lookup(hammer2_chain_t
**parentp
, hammer2_key_t
*key_nextp
,
2192 hammer2_key_t key_beg
, hammer2_key_t key_end
,
2193 int *cache_indexp
, int flags
)
2196 hammer2_chain_t
*parent
;
2197 hammer2_chain_t
*chain
;
2198 hammer2_blockref_t
*base
;
2199 hammer2_blockref_t
*bref
;
2200 hammer2_blockref_t bcopy
;
2201 hammer2_key_t scan_beg
;
2202 hammer2_key_t scan_end
;
2204 int how_always
= HAMMER2_RESOLVE_ALWAYS
;
2205 int how_maybe
= HAMMER2_RESOLVE_MAYBE
;
2208 int maxloops
= 300000;
2212 if (flags
& HAMMER2_LOOKUP_ALWAYS
) {
2213 how_maybe
= how_always
;
2214 how
= HAMMER2_RESOLVE_ALWAYS
;
2215 } else if (flags
& (HAMMER2_LOOKUP_NODATA
| HAMMER2_LOOKUP_NOLOCK
)) {
2216 how
= HAMMER2_RESOLVE_NEVER
;
2218 how
= HAMMER2_RESOLVE_MAYBE
;
2220 if (flags
& HAMMER2_LOOKUP_SHARED
) {
2221 how_maybe
|= HAMMER2_RESOLVE_SHARED
;
2222 how_always
|= HAMMER2_RESOLVE_SHARED
;
2223 how
|= HAMMER2_RESOLVE_SHARED
;
2227 * Recurse (*parentp) upward if necessary until the parent completely
2228 * encloses the key range or we hit the inode.
2230 * Handle races against the flusher deleting indirect nodes on its
2231 * way back up by continuing to recurse upward past the deletion.
2236 while (parent
->bref
.type
== HAMMER2_BREF_TYPE_INDIRECT
||
2237 parent
->bref
.type
== HAMMER2_BREF_TYPE_FREEMAP_NODE
) {
2238 scan_beg
= parent
->bref
.key
;
2239 scan_end
= scan_beg
+
2240 ((hammer2_key_t
)1 << parent
->bref
.keybits
) - 1;
2241 if (parent
->bref
.type
!= HAMMER2_BREF_TYPE_INDIRECT
||
2242 (parent
->flags
& HAMMER2_CHAIN_DELETED
) == 0) {
2243 if (key_beg
>= scan_beg
&& key_end
<= scan_end
)
2246 parent
= hammer2_chain_getparent(parentp
, how_maybe
);
2251 if (--maxloops
== 0)
2252 panic("hammer2_chain_lookup: maxloops");
2254 * Locate the blockref array. Currently we do a fully associative
2255 * search through the array.
2257 switch(parent
->bref
.type
) {
2258 case HAMMER2_BREF_TYPE_INODE
:
2260 * Special shortcut for embedded data returns the inode
2261 * itself. Callers must detect this condition and access
2262 * the embedded data (the strategy code does this for us).
2264 * This is only applicable to regular files and softlinks.
2266 * We need a second lock on parent. Since we already have
2267 * a lock we must pass LOCKAGAIN to prevent unexpected
2268 * blocking (we don't want to block on a second shared
2269 * ref if an exclusive lock is pending)
2271 if (parent
->data
->ipdata
.meta
.op_flags
&
2272 HAMMER2_OPFLAG_DIRECTDATA
) {
2273 if (flags
& HAMMER2_LOOKUP_NODIRECT
) {
2275 *key_nextp
= key_end
+ 1;
2278 hammer2_chain_ref(parent
);
2279 if ((flags
& HAMMER2_LOOKUP_NOLOCK
) == 0)
2280 hammer2_chain_lock(parent
,
2282 HAMMER2_RESOLVE_LOCKAGAIN
);
2283 *key_nextp
= key_end
+ 1;
2286 base
= &parent
->data
->ipdata
.u
.blockset
.blockref
[0];
2287 count
= HAMMER2_SET_COUNT
;
2289 case HAMMER2_BREF_TYPE_FREEMAP_NODE
:
2290 case HAMMER2_BREF_TYPE_INDIRECT
:
2292 * Handle MATCHIND on the parent
2294 if (flags
& HAMMER2_LOOKUP_MATCHIND
) {
2295 scan_beg
= parent
->bref
.key
;
2296 scan_end
= scan_beg
+
2297 ((hammer2_key_t
)1 << parent
->bref
.keybits
) - 1;
2298 if (key_beg
== scan_beg
&& key_end
== scan_end
) {
2300 hammer2_chain_ref(chain
);
2301 hammer2_chain_lock(chain
, how_maybe
);
2302 *key_nextp
= scan_end
+ 1;
2308 * Optimize indirect blocks in the INITIAL state to avoid
2311 if (parent
->flags
& HAMMER2_CHAIN_INITIAL
) {
2314 if (parent
->data
== NULL
) {
2315 kprintf("parent->data is NULL %p\n", parent
);
2317 tsleep(parent
, 0, "xxx", 0);
2319 base
= &parent
->data
->npdata
[0];
2321 count
= parent
->bytes
/ sizeof(hammer2_blockref_t
);
2323 case HAMMER2_BREF_TYPE_VOLUME
:
2324 base
= &parent
->data
->voldata
.sroot_blockset
.blockref
[0];
2325 count
= HAMMER2_SET_COUNT
;
2327 case HAMMER2_BREF_TYPE_FREEMAP
:
2328 base
= &parent
->data
->blkset
.blockref
[0];
2329 count
= HAMMER2_SET_COUNT
;
2332 kprintf("hammer2_chain_lookup: unrecognized "
2333 "blockref(B) type: %d",
2336 tsleep(&base
, 0, "dead", 0);
2337 panic("hammer2_chain_lookup: unrecognized "
2338 "blockref(B) type: %d",
2340 base
= NULL
; /* safety */
2341 count
= 0; /* safety */
2346 * Merged scan to find next candidate.
2348 * hammer2_base_*() functions require the parent->core.live_* fields
2349 * to be synchronized.
2351 * We need to hold the spinlock to access the block array and RB tree
2352 * and to interlock chain creation.
2354 if ((parent
->flags
& HAMMER2_CHAIN_COUNTEDBREFS
) == 0)
2355 hammer2_chain_countbrefs(parent
, base
, count
);
2362 hammer2_spin_ex(&parent
->core
.spin
);
2363 chain
= hammer2_combined_find(parent
, base
, count
,
2364 cache_indexp
, key_nextp
,
2367 generation
= parent
->core
.generation
;
2372 * Exhausted parent chain, iterate.
2376 hammer2_spin_unex(&parent
->core
.spin
);
2377 if (key_beg
== key_end
) /* short cut single-key case */
2381 * Stop if we reached the end of the iteration.
2383 if (parent
->bref
.type
!= HAMMER2_BREF_TYPE_INDIRECT
&&
2384 parent
->bref
.type
!= HAMMER2_BREF_TYPE_FREEMAP_NODE
) {
2389 * Calculate next key, stop if we reached the end of the
2390 * iteration, otherwise go up one level and loop.
2392 key_beg
= parent
->bref
.key
+
2393 ((hammer2_key_t
)1 << parent
->bref
.keybits
);
2394 if (key_beg
== 0 || key_beg
> key_end
)
2396 parent
= hammer2_chain_getparent(parentp
, how_maybe
);
2401 * Selected from blockref or in-memory chain.
2403 if (chain
== NULL
) {
2406 hammer2_spin_unex(&parent
->core
.spin
);
2407 chain
= hammer2_chain_get(parent
, generation
,
2409 if (chain
== NULL
) {
2411 kprintf("retry lookup parent %p keys %016jx:%016jx\n",
2412 parent, key_beg, key_end);
2416 if (bcmp(&bcopy
, bref
, sizeof(bcopy
))) {
2417 hammer2_chain_drop(chain
);
2422 hammer2_chain_ref(chain
);
2423 hammer2_spin_unex(&parent
->core
.spin
);
2428 * chain is referenced but not locked. We must lock the chain
2429 * to obtain definitive state.
2431 if (chain
->bref
.type
== HAMMER2_BREF_TYPE_INDIRECT
||
2432 chain
->bref
.type
== HAMMER2_BREF_TYPE_FREEMAP_NODE
) {
2433 hammer2_chain_lock(chain
, how_maybe
);
2435 hammer2_chain_lock(chain
, how
);
2437 KKASSERT(chain
->parent
== parent
);
2441 * Skip deleted chains (XXX cache 'i' end-of-block-array? XXX)
2443 * NOTE: Chain's key range is not relevant as there might be
2444 * one-offs within the range that are not deleted.
2446 * NOTE: Lookups can race delete-duplicate because
2447 * delete-duplicate does not lock the parent's core
2448 * (they just use the spinlock on the core).
2450 if (chain
->flags
& HAMMER2_CHAIN_DELETED
) {
2451 kprintf("skip deleted chain %016jx.%02x key=%016jx\n",
2452 chain
->bref
.data_off
, chain
->bref
.type
,
2454 hammer2_chain_unlock(chain
);
2455 hammer2_chain_drop(chain
);
2456 key_beg
= *key_nextp
;
2457 if (key_beg
== 0 || key_beg
> key_end
)
2464 * If the chain element is an indirect block it becomes the new
2465 * parent and we loop on it. We must maintain our top-down locks
2466 * to prevent the flusher from interfering (i.e. doing a
2467 * delete-duplicate and leaving us recursing down a deleted chain).
2469 * The parent always has to be locked with at least RESOLVE_MAYBE
2470 * so we can access its data. It might need a fixup if the caller
2471 * passed incompatible flags. Be careful not to cause a deadlock
2472 * as a data-load requires an exclusive lock.
2474 * If HAMMER2_LOOKUP_MATCHIND is set and the indirect block's key
2475 * range is within the requested key range we return the indirect
2476 * block and do NOT loop. This is usually only used to acquire
2479 if (chain
->bref
.type
== HAMMER2_BREF_TYPE_INDIRECT
||
2480 chain
->bref
.type
== HAMMER2_BREF_TYPE_FREEMAP_NODE
) {
2481 hammer2_chain_unlock(parent
);
2482 hammer2_chain_drop(parent
);
2483 *parentp
= parent
= chain
;
2489 * All done, return the chain.
2491 * If the caller does not want a locked chain, replace the lock with
2492 * a ref. Perhaps this can eventually be optimized to not obtain the
2493 * lock in the first place for situations where the data does not
2494 * need to be resolved.
2497 if (flags
& HAMMER2_LOOKUP_NOLOCK
)
2498 hammer2_chain_unlock(chain
);
2506 * After having issued a lookup we can iterate all matching keys.
2508 * If chain is non-NULL we continue the iteration from just after it's index.
2510 * If chain is NULL we assume the parent was exhausted and continue the
2511 * iteration at the next parent.
2513 * If a fatal error occurs (typically an I/O error), a dummy chain is
2514 * returned with chain->error and error-identifying information set. This
2515 * chain will assert if you try to do anything fancy with it.
2517 * XXX Depending on where the error occurs we should allow continued iteration.
2519 * parent must be locked on entry and remains locked throughout. chain's
2520 * lock status must match flags. Chain is always at least referenced.
2522 * WARNING! The MATCHIND flag does not apply to this function.
2525 hammer2_chain_next(hammer2_chain_t
**parentp
, hammer2_chain_t
*chain
,
2526 hammer2_key_t
*key_nextp
,
2527 hammer2_key_t key_beg
, hammer2_key_t key_end
,
2528 int *cache_indexp
, int flags
)
2530 hammer2_chain_t
*parent
;
2534 * Calculate locking flags for upward recursion.
2536 how_maybe
= HAMMER2_RESOLVE_MAYBE
;
2537 if (flags
& HAMMER2_LOOKUP_SHARED
)
2538 how_maybe
|= HAMMER2_RESOLVE_SHARED
;
2543 * Calculate the next index and recalculate the parent if necessary.
2546 key_beg
= chain
->bref
.key
+
2547 ((hammer2_key_t
)1 << chain
->bref
.keybits
);
2548 if ((flags
& (HAMMER2_LOOKUP_NOLOCK
|
2549 HAMMER2_LOOKUP_NOUNLOCK
)) == 0) {
2550 hammer2_chain_unlock(chain
);
2552 hammer2_chain_drop(chain
);
2555 * chain invalid past this point, but we can still do a
2556 * pointer comparison w/parent.
2558 * Any scan where the lookup returned degenerate data embedded
2559 * in the inode has an invalid index and must terminate.
2561 if (chain
== parent
)
2563 if (key_beg
== 0 || key_beg
> key_end
)
2566 } else if (parent
->bref
.type
!= HAMMER2_BREF_TYPE_INDIRECT
&&
2567 parent
->bref
.type
!= HAMMER2_BREF_TYPE_FREEMAP_NODE
) {
2569 * We reached the end of the iteration.
2574 * Continue iteration with next parent unless the current
2575 * parent covers the range.
2577 * (This also handles the case of a deleted, empty indirect
2580 key_beg
= parent
->bref
.key
+
2581 ((hammer2_key_t
)1 << parent
->bref
.keybits
);
2582 if (key_beg
== 0 || key_beg
> key_end
)
2584 parent
= hammer2_chain_getparent(parentp
, how_maybe
);
2590 return (hammer2_chain_lookup(parentp
, key_nextp
,
2592 cache_indexp
, flags
));
2596 * The raw scan function is similar to lookup/next but does not seek to a key.
2597 * Blockrefs are iterated via first_bref = (parent, NULL) and
2598 * next_chain = (parent, bref).
2600 * The passed-in parent must be locked and its data resolved. The function
2601 * nominally returns a locked and referenced *chainp != NULL for chains
2602 * the caller might need to recurse on (and will dipose of any *chainp passed
2603 * in). The caller must check the chain->bref.type either way.
2605 * *chainp is not set for leaf elements.
2607 * This function takes a pointer to a stack-based bref structure whos
2608 * contents is updated for each iteration. The same pointer is returned,
2609 * or NULL when the iteration is complete. *firstp must be set to 1 for
2610 * the first ieration. This function will set it to 0.
2612 hammer2_blockref_t
*
2613 hammer2_chain_scan(hammer2_chain_t
*parent
, hammer2_chain_t
**chainp
,
2614 hammer2_blockref_t
*bref
, int *firstp
,
2615 int *cache_indexp
, int flags
)
2618 hammer2_blockref_t
*base
;
2619 hammer2_blockref_t
*bref_ptr
;
2621 hammer2_key_t next_key
;
2622 hammer2_chain_t
*chain
= NULL
;
2624 int how_always
= HAMMER2_RESOLVE_ALWAYS
;
2625 int how_maybe
= HAMMER2_RESOLVE_MAYBE
;
2628 int maxloops
= 300000;
2633 * Scan flags borrowed from lookup.
2635 if (flags
& HAMMER2_LOOKUP_ALWAYS
) {
2636 how_maybe
= how_always
;
2637 how
= HAMMER2_RESOLVE_ALWAYS
;
2638 } else if (flags
& (HAMMER2_LOOKUP_NODATA
| HAMMER2_LOOKUP_NOLOCK
)) {
2639 how
= HAMMER2_RESOLVE_NEVER
;
2641 how
= HAMMER2_RESOLVE_MAYBE
;
2643 if (flags
& HAMMER2_LOOKUP_SHARED
) {
2644 how_maybe
|= HAMMER2_RESOLVE_SHARED
;
2645 how_always
|= HAMMER2_RESOLVE_SHARED
;
2646 how
|= HAMMER2_RESOLVE_SHARED
;
2650 * Calculate key to locate first/next element, unlocking the previous
2651 * element as we go. Be careful, the key calculation can overflow.
2653 * (also reset bref to NULL)
2659 key
= bref
->key
+ ((hammer2_key_t
)1 << bref
->keybits
);
2660 if ((chain
= *chainp
) != NULL
) {
2662 hammer2_chain_unlock(chain
);
2663 hammer2_chain_drop(chain
);
2673 KKASSERT(parent
->error
== 0); /* XXX case not handled yet */
2674 if (--maxloops
== 0)
2675 panic("hammer2_chain_scan: maxloops");
2677 * Locate the blockref array. Currently we do a fully associative
2678 * search through the array.
2680 switch(parent
->bref
.type
) {
2681 case HAMMER2_BREF_TYPE_INODE
:
2683 * An inode with embedded data has no sub-chains.
2685 * WARNING! Bulk scan code may pass a static chain marked
2686 * as BREF_TYPE_INODE with a copy of the volume
2687 * root blockset to snapshot the volume.
2689 if (parent
->data
->ipdata
.meta
.op_flags
&
2690 HAMMER2_OPFLAG_DIRECTDATA
) {
2694 base
= &parent
->data
->ipdata
.u
.blockset
.blockref
[0];
2695 count
= HAMMER2_SET_COUNT
;
2697 case HAMMER2_BREF_TYPE_FREEMAP_NODE
:
2698 case HAMMER2_BREF_TYPE_INDIRECT
:
2700 * Optimize indirect blocks in the INITIAL state to avoid
2703 if (parent
->flags
& HAMMER2_CHAIN_INITIAL
) {
2706 if (parent
->data
== NULL
)
2707 panic("parent->data is NULL");
2708 base
= &parent
->data
->npdata
[0];
2710 count
= parent
->bytes
/ sizeof(hammer2_blockref_t
);
2712 case HAMMER2_BREF_TYPE_VOLUME
:
2713 base
= &parent
->data
->voldata
.sroot_blockset
.blockref
[0];
2714 count
= HAMMER2_SET_COUNT
;
2716 case HAMMER2_BREF_TYPE_FREEMAP
:
2717 base
= &parent
->data
->blkset
.blockref
[0];
2718 count
= HAMMER2_SET_COUNT
;
2721 panic("hammer2_chain_lookup: unrecognized blockref type: %d",
2723 base
= NULL
; /* safety */
2724 count
= 0; /* safety */
2728 * Merged scan to find next candidate.
2730 * hammer2_base_*() functions require the parent->core.live_* fields
2731 * to be synchronized.
2733 * We need to hold the spinlock to access the block array and RB tree
2734 * and to interlock chain creation.
2736 if ((parent
->flags
& HAMMER2_CHAIN_COUNTEDBREFS
) == 0)
2737 hammer2_chain_countbrefs(parent
, base
, count
);
2741 hammer2_spin_ex(&parent
->core
.spin
);
2742 chain
= hammer2_combined_find(parent
, base
, count
,
2743 cache_indexp
, &next_key
,
2744 key
, HAMMER2_KEY_MAX
,
2746 generation
= parent
->core
.generation
;
2749 * Exhausted parent chain, we're done.
2751 if (bref_ptr
== NULL
) {
2752 hammer2_spin_unex(&parent
->core
.spin
);
2753 KKASSERT(chain
== NULL
);
2759 * Copy into the supplied stack-based blockref.
2764 * Selected from blockref or in-memory chain.
2766 if (chain
== NULL
) {
2767 switch(bref
->type
) {
2768 case HAMMER2_BREF_TYPE_INODE
:
2769 case HAMMER2_BREF_TYPE_FREEMAP_NODE
:
2770 case HAMMER2_BREF_TYPE_INDIRECT
:
2771 case HAMMER2_BREF_TYPE_VOLUME
:
2772 case HAMMER2_BREF_TYPE_FREEMAP
:
2774 * Recursion, always get the chain
2776 hammer2_spin_unex(&parent
->core
.spin
);
2777 chain
= hammer2_chain_get(parent
, generation
, bref
);
2778 if (chain
== NULL
) {
2779 kprintf("retry scan parent %p keys %016jx\n",
2783 if (bcmp(bref
, bref_ptr
, sizeof(*bref
))) {
2784 hammer2_chain_drop(chain
);
2791 * No recursion, do not waste time instantiating
2792 * a chain, just iterate using the bref.
2794 hammer2_spin_unex(&parent
->core
.spin
);
2799 * Recursion or not we need the chain in order to supply
2802 hammer2_chain_ref(chain
);
2803 hammer2_spin_unex(&parent
->core
.spin
);
2807 * chain is referenced but not locked. We must lock the chain
2808 * to obtain definitive state.
2811 hammer2_chain_lock(chain
, how
);
2814 * Skip deleted chains (XXX cache 'i' end-of-block-array? XXX)
2816 * NOTE: chain's key range is not relevant as there might be
2817 * one-offs within the range that are not deleted.
2819 * NOTE: XXX this could create problems with scans used in
2820 * situations other than mount-time recovery.
2822 * NOTE: Lookups can race delete-duplicate because
2823 * delete-duplicate does not lock the parent's core
2824 * (they just use the spinlock on the core).
2826 if (chain
&& (chain
->flags
& HAMMER2_CHAIN_DELETED
)) {
2827 hammer2_chain_unlock(chain
);
2828 hammer2_chain_drop(chain
);
2841 * All done, return the bref or NULL, supply chain if necessary.
2849 * Create and return a new hammer2 system memory structure of the specified
2850 * key, type and size and insert it under (*parentp). This is a full
2851 * insertion, based on the supplied key/keybits, and may involve creating
2852 * indirect blocks and moving other chains around via delete/duplicate.
2854 * THE CALLER MUST HAVE ALREADY PROPERLY SEEKED (*parentp) TO THE INSERTION
2855 * POINT SANS ANY REQUIRED INDIRECT BLOCK CREATIONS DUE TO THE ARRAY BEING
2856 * FULL. This typically means that the caller is creating the chain after
2857 * doing a hammer2_chain_lookup().
2859 * (*parentp) must be exclusive locked and may be replaced on return
2860 * depending on how much work the function had to do.
2862 * (*parentp) must not be errored or this function will assert.
2864 * (*chainp) usually starts out NULL and returns the newly created chain,
2865 * but if the caller desires the caller may allocate a disconnected chain
2866 * and pass it in instead.
2868 * This function should NOT be used to insert INDIRECT blocks. It is
2869 * typically used to create/insert inodes and data blocks.
2871 * Caller must pass-in an exclusively locked parent the new chain is to
2872 * be inserted under, and optionally pass-in a disconnected, exclusively
2873 * locked chain to insert (else we create a new chain). The function will
2874 * adjust (*parentp) as necessary, create or connect the chain, and
2875 * return an exclusively locked chain in *chainp.
2877 * When creating a PFSROOT inode under the super-root, pmp is typically NULL
2878 * and will be reassigned.
2881 hammer2_chain_create(hammer2_chain_t
**parentp
, hammer2_chain_t
**chainp
,
2882 hammer2_pfs_t
*pmp
, int methods
,
2883 hammer2_key_t key
, int keybits
, int type
, size_t bytes
,
2884 hammer2_tid_t mtid
, hammer2_off_t dedup_off
, int flags
)
2887 hammer2_chain_t
*chain
;
2888 hammer2_chain_t
*parent
;
2889 hammer2_blockref_t
*base
;
2890 hammer2_blockref_t dummy
;
2894 int maxloops
= 300000;
2897 * Topology may be crossing a PFS boundary.
2900 KKASSERT(hammer2_mtx_owned(&parent
->lock
));
2901 KKASSERT(parent
->error
== 0);
2905 if (chain
== NULL
) {
2907 * First allocate media space and construct the dummy bref,
2908 * then allocate the in-memory chain structure. Set the
2909 * INITIAL flag for fresh chains which do not have embedded
2912 * XXX for now set the check mode of the child based on
2913 * the parent or, if the parent is an inode, the
2914 * specification in the inode.
2916 bzero(&dummy
, sizeof(dummy
));
2919 dummy
.keybits
= keybits
;
2920 dummy
.data_off
= hammer2_getradix(bytes
);
2923 * Inherit methods from parent by default. Primarily used
2924 * for BREF_TYPE_DATA. Non-data types *must* be set to
2925 * a non-NONE check algorithm.
2928 dummy
.methods
= parent
->bref
.methods
;
2930 dummy
.methods
= (uint8_t)methods
;
2932 if (type
!= HAMMER2_BREF_TYPE_DATA
&&
2933 HAMMER2_DEC_CHECK(dummy
.methods
) == HAMMER2_CHECK_NONE
) {
2935 HAMMER2_ENC_CHECK(HAMMER2_CHECK_DEFAULT
);
2938 chain
= hammer2_chain_alloc(hmp
, pmp
, &dummy
);
2941 * Lock the chain manually, chain_lock will load the chain
2942 * which we do NOT want to do. (note: chain->refs is set
2943 * to 1 by chain_alloc() for us, but lockcnt is not).
2946 hammer2_mtx_ex(&chain
->lock
);
2948 ++curthread
->td_tracker
;
2951 * Set INITIAL to optimize I/O. The flag will generally be
2952 * processed when we call hammer2_chain_modify().
2954 * Recalculate bytes to reflect the actual media block
2955 * allocation. Handle special case radix 0 == 0 bytes.
2957 bytes
= (size_t)(chain
->bref
.data_off
& HAMMER2_OFF_MASK_RADIX
);
2959 bytes
= (hammer2_off_t
)1 << bytes
;
2960 chain
->bytes
= bytes
;
2963 case HAMMER2_BREF_TYPE_VOLUME
:
2964 case HAMMER2_BREF_TYPE_FREEMAP
:
2965 panic("hammer2_chain_create: called with volume type");
2967 case HAMMER2_BREF_TYPE_INDIRECT
:
2968 panic("hammer2_chain_create: cannot be used to"
2969 "create indirect block");
2971 case HAMMER2_BREF_TYPE_FREEMAP_NODE
:
2972 panic("hammer2_chain_create: cannot be used to"
2973 "create freemap root or node");
2975 case HAMMER2_BREF_TYPE_FREEMAP_LEAF
:
2976 KKASSERT(bytes
== sizeof(chain
->data
->bmdata
));
2978 case HAMMER2_BREF_TYPE_DIRENT
:
2979 case HAMMER2_BREF_TYPE_INODE
:
2980 case HAMMER2_BREF_TYPE_DATA
:
2983 * leave chain->data NULL, set INITIAL
2985 KKASSERT(chain
->data
== NULL
);
2986 atomic_set_int(&chain
->flags
, HAMMER2_CHAIN_INITIAL
);
2991 * We are reattaching a previously deleted chain, possibly
2992 * under a new parent and possibly with a new key/keybits.
2993 * The chain does not have to be in a modified state. The
2994 * UPDATE flag will be set later on in this routine.
2996 * Do NOT mess with the current state of the INITIAL flag.
2998 chain
->bref
.key
= key
;
2999 chain
->bref
.keybits
= keybits
;
3000 if (chain
->flags
& HAMMER2_CHAIN_DELETED
)
3001 atomic_clear_int(&chain
->flags
, HAMMER2_CHAIN_DELETED
);
3002 KKASSERT(chain
->parent
== NULL
);
3004 if (flags
& HAMMER2_INSERT_PFSROOT
)
3005 chain
->bref
.flags
|= HAMMER2_BREF_FLAG_PFSROOT
;
3007 chain
->bref
.flags
&= ~HAMMER2_BREF_FLAG_PFSROOT
;
3010 * Calculate how many entries we have in the blockref array and
3011 * determine if an indirect block is required.
3014 if (--maxloops
== 0)
3015 panic("hammer2_chain_create: maxloops");
3017 switch(parent
->bref
.type
) {
3018 case HAMMER2_BREF_TYPE_INODE
:
3019 if ((parent
->data
->ipdata
.meta
.op_flags
&
3020 HAMMER2_OPFLAG_DIRECTDATA
) != 0) {
3021 kprintf("hammer2: parent set for direct-data! "
3022 "pkey=%016jx ckey=%016jx\n",
3026 KKASSERT((parent
->data
->ipdata
.meta
.op_flags
&
3027 HAMMER2_OPFLAG_DIRECTDATA
) == 0);
3028 KKASSERT(parent
->data
!= NULL
);
3029 base
= &parent
->data
->ipdata
.u
.blockset
.blockref
[0];
3030 count
= HAMMER2_SET_COUNT
;
3032 case HAMMER2_BREF_TYPE_INDIRECT
:
3033 case HAMMER2_BREF_TYPE_FREEMAP_NODE
:
3034 if (parent
->flags
& HAMMER2_CHAIN_INITIAL
)
3037 base
= &parent
->data
->npdata
[0];
3038 count
= parent
->bytes
/ sizeof(hammer2_blockref_t
);
3040 case HAMMER2_BREF_TYPE_VOLUME
:
3041 KKASSERT(parent
->data
!= NULL
);
3042 base
= &parent
->data
->voldata
.sroot_blockset
.blockref
[0];
3043 count
= HAMMER2_SET_COUNT
;
3045 case HAMMER2_BREF_TYPE_FREEMAP
:
3046 KKASSERT(parent
->data
!= NULL
);
3047 base
= &parent
->data
->blkset
.blockref
[0];
3048 count
= HAMMER2_SET_COUNT
;
3051 panic("hammer2_chain_create: unrecognized blockref type: %d",
3059 * Make sure we've counted the brefs
3061 if ((parent
->flags
& HAMMER2_CHAIN_COUNTEDBREFS
) == 0)
3062 hammer2_chain_countbrefs(parent
, base
, count
);
3064 KASSERT(parent
->core
.live_count
>= 0 &&
3065 parent
->core
.live_count
<= count
,
3066 ("bad live_count %d/%d (%02x, %d)",
3067 parent
->core
.live_count
, count
,
3068 parent
->bref
.type
, parent
->bytes
));
3071 * If no free blockref could be found we must create an indirect
3072 * block and move a number of blockrefs into it. With the parent
3073 * locked we can safely lock each child in order to delete+duplicate
3074 * it without causing a deadlock.
3076 * This may return the new indirect block or the old parent depending
3077 * on where the key falls. NULL is returned on error.
3079 if (parent
->core
.live_count
== count
) {
3080 hammer2_chain_t
*nparent
;
3082 nparent
= hammer2_chain_create_indirect(parent
, key
, keybits
,
3083 mtid
, type
, &error
);
3084 if (nparent
== NULL
) {
3086 hammer2_chain_drop(chain
);
3090 if (parent
!= nparent
) {
3091 hammer2_chain_unlock(parent
);
3092 hammer2_chain_drop(parent
);
3093 parent
= *parentp
= nparent
;
3098 if (chain
->flags
& HAMMER2_CHAIN_DELETED
)
3099 kprintf("Inserting deleted chain @%016jx\n",
3103 * Link the chain into its parent.
3105 if (chain
->parent
!= NULL
)
3106 panic("hammer2: hammer2_chain_create: chain already connected");
3107 KKASSERT(chain
->parent
== NULL
);
3108 hammer2_chain_insert(parent
, chain
,
3109 HAMMER2_CHAIN_INSERT_SPIN
|
3110 HAMMER2_CHAIN_INSERT_LIVE
,
3115 * Mark the newly created chain modified. This will cause
3116 * UPDATE to be set and process the INITIAL flag.
3118 * Device buffers are not instantiated for DATA elements
3119 * as these are handled by logical buffers.
3121 * Indirect and freemap node indirect blocks are handled
3122 * by hammer2_chain_create_indirect() and not by this
3125 * Data for all other bref types is expected to be
3126 * instantiated (INODE, LEAF).
3128 switch(chain
->bref
.type
) {
3129 case HAMMER2_BREF_TYPE_DATA
:
3130 case HAMMER2_BREF_TYPE_FREEMAP_LEAF
:
3131 case HAMMER2_BREF_TYPE_DIRENT
:
3132 case HAMMER2_BREF_TYPE_INODE
:
3133 hammer2_chain_modify(chain
, mtid
, dedup_off
,
3134 HAMMER2_MODIFY_OPTDATA
);
3138 * Remaining types are not supported by this function.
3139 * In particular, INDIRECT and LEAF_NODE types are
3140 * handled by create_indirect().
3142 panic("hammer2_chain_create: bad type: %d",
3149 * When reconnecting a chain we must set UPDATE and
3150 * setflush so the flush recognizes that it must update
3151 * the bref in the parent.
3153 if ((chain
->flags
& HAMMER2_CHAIN_UPDATE
) == 0)
3154 atomic_set_int(&chain
->flags
, HAMMER2_CHAIN_UPDATE
);
3158 * We must setflush(parent) to ensure that it recurses through to
3159 * chain. setflush(chain) might not work because ONFLUSH is possibly
3160 * already set in the chain (so it won't recurse up to set it in the
3163 hammer2_chain_setflush(parent
);
3172 * Move the chain from its old parent to a new parent. The chain must have
3173 * already been deleted or already disconnected (or never associated) with
3174 * a parent. The chain is reassociated with the new parent and the deleted
3175 * flag will be cleared (no longer deleted). The chain's modification state
3178 * THE CALLER MUST HAVE ALREADY PROPERLY SEEKED (parent) TO THE INSERTION
3179 * POINT SANS ANY REQUIRED INDIRECT BLOCK CREATIONS DUE TO THE ARRAY BEING
3180 * FULL. This typically means that the caller is creating the chain after
3181 * doing a hammer2_chain_lookup().
3183 * A non-NULL bref is typically passed when key and keybits must be overridden.
3184 * Note that hammer2_cluster_duplicate() *ONLY* uses the key and keybits fields
3185 * from a passed-in bref and uses the old chain's bref for everything else.
3187 * Neither (parent) or (chain) can be errored.
3189 * If (parent) is non-NULL then the chain is inserted under the parent.
3191 * If (parent) is NULL then the newly duplicated chain is not inserted
3192 * anywhere, similar to if it had just been chain_alloc()'d (suitable for
3193 * passing into hammer2_chain_create() after this function returns).
3195 * WARNING! This function calls create which means it can insert indirect
3196 * blocks. This can cause other unrelated chains in the parent to
3197 * be moved to a newly inserted indirect block in addition to the
3201 hammer2_chain_rename(hammer2_blockref_t
*bref
,
3202 hammer2_chain_t
**parentp
, hammer2_chain_t
*chain
,
3203 hammer2_tid_t mtid
, int flags
)
3206 hammer2_chain_t
*parent
;
3210 * WARNING! We should never resolve DATA to device buffers
3211 * (XXX allow it if the caller did?), and since
3212 * we currently do not have the logical buffer cache
3213 * buffer in-hand to fix its cached physical offset
3214 * we also force the modify code to not COW it. XXX
3217 KKASSERT(chain
->parent
== NULL
);
3218 KKASSERT(chain
->error
== 0);
3221 * Now create a duplicate of the chain structure, associating
3222 * it with the same core, making it the same size, pointing it
3223 * to the same bref (the same media block).
3225 * NOTE: Handle special radix == 0 case (means 0 bytes).
3228 bref
= &chain
->bref
;
3229 bytes
= (size_t)(bref
->data_off
& HAMMER2_OFF_MASK_RADIX
);
3231 bytes
= (hammer2_off_t
)1 << bytes
;
3234 * If parent is not NULL the duplicated chain will be entered under
3235 * the parent and the UPDATE bit set to tell flush to update
3238 * We must setflush(parent) to ensure that it recurses through to
3239 * chain. setflush(chain) might not work because ONFLUSH is possibly
3240 * already set in the chain (so it won't recurse up to set it in the
3243 * Having both chains locked is extremely important for atomicy.
3245 if (parentp
&& (parent
= *parentp
) != NULL
) {
3246 KKASSERT(hammer2_mtx_owned(&parent
->lock
));
3247 KKASSERT(parent
->refs
> 0);
3248 KKASSERT(parent
->error
== 0);
3250 hammer2_chain_create(parentp
, &chain
,
3251 chain
->pmp
, HAMMER2_METH_DEFAULT
,
3252 bref
->key
, bref
->keybits
, bref
->type
,
3253 chain
->bytes
, mtid
, 0, flags
);
3254 KKASSERT(chain
->flags
& HAMMER2_CHAIN_UPDATE
);
3255 hammer2_chain_setflush(*parentp
);
3260 * Helper function for deleting chains.
3262 * The chain is removed from the live view (the RBTREE) as well as the parent's
3263 * blockmap. Both chain and its parent must be locked.
3265 * parent may not be errored. chain can be errored.
3268 _hammer2_chain_delete_helper(hammer2_chain_t
*parent
, hammer2_chain_t
*chain
,
3269 hammer2_tid_t mtid
, int flags
)
3273 KKASSERT((chain
->flags
& (HAMMER2_CHAIN_DELETED
|
3274 HAMMER2_CHAIN_FICTITIOUS
)) == 0);
3275 KKASSERT(chain
->parent
== parent
);
3278 if (chain
->flags
& HAMMER2_CHAIN_BMAPPED
) {
3280 * Chain is blockmapped, so there must be a parent.
3281 * Atomically remove the chain from the parent and remove
3282 * the blockmap entry. The parent must be set modified
3283 * to remove the blockmap entry.
3285 hammer2_blockref_t
*base
;
3288 KKASSERT(parent
!= NULL
);
3289 KKASSERT(parent
->error
== 0);
3290 KKASSERT((parent
->flags
& HAMMER2_CHAIN_INITIAL
) == 0);
3291 hammer2_chain_modify(parent
, mtid
, 0, HAMMER2_MODIFY_OPTDATA
);
3294 * Calculate blockmap pointer
3296 KKASSERT(chain
->flags
& HAMMER2_CHAIN_ONRBTREE
);
3297 hammer2_spin_ex(&parent
->core
.spin
);
3299 atomic_set_int(&chain
->flags
, HAMMER2_CHAIN_DELETED
);
3300 atomic_add_int(&parent
->core
.live_count
, -1);
3301 ++parent
->core
.generation
;
3302 RB_REMOVE(hammer2_chain_tree
, &parent
->core
.rbtree
, chain
);
3303 atomic_clear_int(&chain
->flags
, HAMMER2_CHAIN_ONRBTREE
);
3304 --parent
->core
.chain_count
;
3305 chain
->parent
= NULL
;
3307 switch(parent
->bref
.type
) {
3308 case HAMMER2_BREF_TYPE_INODE
:
3310 * Access the inode's block array. However, there
3311 * is no block array if the inode is flagged
3315 (parent
->data
->ipdata
.meta
.op_flags
&
3316 HAMMER2_OPFLAG_DIRECTDATA
) == 0) {
3318 &parent
->data
->ipdata
.u
.blockset
.blockref
[0];
3322 count
= HAMMER2_SET_COUNT
;
3324 case HAMMER2_BREF_TYPE_INDIRECT
:
3325 case HAMMER2_BREF_TYPE_FREEMAP_NODE
:
3327 base
= &parent
->data
->npdata
[0];
3330 count
= parent
->bytes
/ sizeof(hammer2_blockref_t
);
3332 case HAMMER2_BREF_TYPE_VOLUME
:
3333 base
= &parent
->data
->voldata
.
3334 sroot_blockset
.blockref
[0];
3335 count
= HAMMER2_SET_COUNT
;
3337 case HAMMER2_BREF_TYPE_FREEMAP
:
3338 base
= &parent
->data
->blkset
.blockref
[0];
3339 count
= HAMMER2_SET_COUNT
;
3344 panic("hammer2_flush_pass2: "
3345 "unrecognized blockref type: %d",
3350 * delete blockmapped chain from its parent.
3352 * The parent is not affected by any statistics in chain
3353 * which are pending synchronization. That is, there is
3354 * nothing to undo in the parent since they have not yet
3355 * been incorporated into the parent.
3357 * The parent is affected by statistics stored in inodes.
3358 * Those have already been synchronized, so they must be
3359 * undone. XXX split update possible w/delete in middle?
3362 int cache_index
= -1;
3363 hammer2_base_delete(parent
, base
, count
,
3364 &cache_index
, chain
);
3366 hammer2_spin_unex(&parent
->core
.spin
);
3367 } else if (chain
->flags
& HAMMER2_CHAIN_ONRBTREE
) {
3369 * Chain is not blockmapped but a parent is present.
3370 * Atomically remove the chain from the parent. There is
3371 * no blockmap entry to remove.
3373 * Because chain was associated with a parent but not
3374 * synchronized, the chain's *_count_up fields contain
3375 * inode adjustment statistics which must be undone.
3377 hammer2_spin_ex(&parent
->core
.spin
);
3378 atomic_set_int(&chain
->flags
, HAMMER2_CHAIN_DELETED
);
3379 atomic_add_int(&parent
->core
.live_count
, -1);
3380 ++parent
->core
.generation
;
3381 RB_REMOVE(hammer2_chain_tree
, &parent
->core
.rbtree
, chain
);
3382 atomic_clear_int(&chain
->flags
, HAMMER2_CHAIN_ONRBTREE
);
3383 --parent
->core
.chain_count
;
3384 chain
->parent
= NULL
;
3385 hammer2_spin_unex(&parent
->core
.spin
);
3388 * Chain is not blockmapped and has no parent. This
3389 * is a degenerate case.
3391 atomic_set_int(&chain
->flags
, HAMMER2_CHAIN_DELETED
);
3396 * Create an indirect block that covers one or more of the elements in the
3397 * current parent. Either returns the existing parent with no locking or
3398 * ref changes or returns the new indirect block locked and referenced
3399 * and leaving the original parent lock/ref intact as well.
3401 * If an error occurs, NULL is returned and *errorp is set to the error.
3403 * The returned chain depends on where the specified key falls.
3405 * The key/keybits for the indirect mode only needs to follow three rules:
3407 * (1) That all elements underneath it fit within its key space and
3409 * (2) That all elements outside it are outside its key space.
3411 * (3) When creating the new indirect block any elements in the current
3412 * parent that fit within the new indirect block's keyspace must be
3413 * moved into the new indirect block.
3415 * (4) The keyspace chosen for the inserted indirect block CAN cover a wider
3416 * keyspace the the current parent, but lookup/iteration rules will
3417 * ensure (and must ensure) that rule (2) for all parents leading up
3418 * to the nearest inode or the root volume header is adhered to. This
3419 * is accomplished by always recursing through matching keyspaces in
3420 * the hammer2_chain_lookup() and hammer2_chain_next() API.
3422 * The current implementation calculates the current worst-case keyspace by
3423 * iterating the current parent and then divides it into two halves, choosing
3424 * whichever half has the most elements (not necessarily the half containing
3425 * the requested key).
3427 * We can also opt to use the half with the least number of elements. This
3428 * causes lower-numbered keys (aka logical file offsets) to recurse through
3429 * fewer indirect blocks and higher-numbered keys to recurse through more.
3430 * This also has the risk of not moving enough elements to the new indirect
3431 * block and being forced to create several indirect blocks before the element
3434 * Must be called with an exclusively locked parent.
3436 static int hammer2_chain_indkey_freemap(hammer2_chain_t
*parent
,
3437 hammer2_key_t
*keyp
, int keybits
,
3438 hammer2_blockref_t
*base
, int count
);
3439 static int hammer2_chain_indkey_file(hammer2_chain_t
*parent
,
3440 hammer2_key_t
*keyp
, int keybits
,
3441 hammer2_blockref_t
*base
, int count
,
3443 static int hammer2_chain_indkey_dir(hammer2_chain_t
*parent
,
3444 hammer2_key_t
*keyp
, int keybits
,
3445 hammer2_blockref_t
*base
, int count
,
3449 hammer2_chain_create_indirect(hammer2_chain_t
*parent
,
3450 hammer2_key_t create_key
, int create_bits
,
3451 hammer2_tid_t mtid
, int for_type
, int *errorp
)
3454 hammer2_blockref_t
*base
;
3455 hammer2_blockref_t
*bref
;
3456 hammer2_blockref_t bcopy
;
3457 hammer2_chain_t
*chain
;
3458 hammer2_chain_t
*ichain
;
3459 hammer2_chain_t dummy
;
3460 hammer2_key_t key
= create_key
;
3461 hammer2_key_t key_beg
;
3462 hammer2_key_t key_end
;
3463 hammer2_key_t key_next
;
3464 int keybits
= create_bits
;
3472 int maxloops
= 300000;
3475 * Calculate the base blockref pointer or NULL if the chain
3476 * is known to be empty. We need to calculate the array count
3477 * for RB lookups either way.
3481 KKASSERT(hammer2_mtx_owned(&parent
->lock
));
3483 /*hammer2_chain_modify(&parent, HAMMER2_MODIFY_OPTDATA);*/
3484 base
= hammer2_chain_base_and_count(parent
, &count
);
3487 * dummy used in later chain allocation (no longer used for lookups).
3489 bzero(&dummy
, sizeof(dummy
));
3492 * How big should our new indirect block be? It has to be at least
3493 * as large as its parent for splits to work properly.
3495 * The freemap uses a specific indirect block size. The number of
3496 * levels are built dynamically and ultimately depend on the size
3497 * volume. Because freemap blocks are taken from the reserved areas
3498 * of the volume our goal is efficiency (fewer levels) and not so
3499 * much to save disk space.
3501 * The first indirect block level for a directory usually uses
3502 * HAMMER2_IND_BYTES_MIN (4KB = 32 directory entries). Due to
3503 * the hash mechanism, this typically gives us a nominal
3504 * 32 * 4 entries with one level of indirection.
3506 * We use HAMMER2_IND_BYTES_NOM (16KB = 128 blockrefs) for FILE
3507 * indirect blocks. The initial 4 entries in the inode gives us
3508 * 256KB. Up to 4 indirect blocks gives us 32MB. Three levels
3509 * of indirection gives us 137GB, and so forth. H2 can support
3510 * huge file sizes but they are not typical, so we try to stick
3511 * with compactness and do not use a larger indirect block size.
3513 * We could use 64KB (PBUFSIZE), giving us 512 blockrefs, but
3514 * due to the way indirect blocks are created this usually winds
3515 * up being extremely inefficient for small files. Even though
3516 * 16KB requires more levels of indirection for very large files,
3517 * the 16KB records can be ganged together into 64KB DIOs.
3519 if (for_type
== HAMMER2_BREF_TYPE_FREEMAP_NODE
||
3520 for_type
== HAMMER2_BREF_TYPE_FREEMAP_LEAF
) {
3521 nbytes
= HAMMER2_FREEMAP_LEVELN_PSIZE
;
3522 } else if (parent
->bref
.type
== HAMMER2_BREF_TYPE_INODE
) {
3523 if (parent
->data
->ipdata
.meta
.type
==
3524 HAMMER2_OBJTYPE_DIRECTORY
)
3525 nbytes
= HAMMER2_IND_BYTES_MIN
; /* 4KB = 32 entries */
3527 nbytes
= HAMMER2_IND_BYTES_NOM
; /* 16KB = ~8MB file */
3530 nbytes
= HAMMER2_IND_BYTES_NOM
;
3532 if (nbytes
< count
* sizeof(hammer2_blockref_t
)) {
3533 KKASSERT(for_type
!= HAMMER2_BREF_TYPE_FREEMAP_NODE
&&
3534 for_type
!= HAMMER2_BREF_TYPE_FREEMAP_LEAF
);
3535 nbytes
= count
* sizeof(hammer2_blockref_t
);
3537 ncount
= nbytes
/ sizeof(hammer2_blockref_t
);
3540 * When creating an indirect block for a freemap node or leaf
3541 * the key/keybits must be fitted to static radix levels because
3542 * particular radix levels use particular reserved blocks in the
3545 * This routine calculates the key/radix of the indirect block
3546 * we need to create, and whether it is on the high-side or the
3550 case HAMMER2_BREF_TYPE_FREEMAP_NODE
:
3551 case HAMMER2_BREF_TYPE_FREEMAP_LEAF
:
3552 keybits
= hammer2_chain_indkey_freemap(parent
, &key
, keybits
,
3555 case HAMMER2_BREF_TYPE_DATA
:
3556 keybits
= hammer2_chain_indkey_file(parent
, &key
, keybits
,
3557 base
, count
, ncount
);
3559 case HAMMER2_BREF_TYPE_DIRENT
:
3560 case HAMMER2_BREF_TYPE_INODE
:
3561 keybits
= hammer2_chain_indkey_dir(parent
, &key
, keybits
,
3562 base
, count
, ncount
);
3565 panic("illegal indirect block for bref type %d", for_type
);
3570 * Normalize the key for the radix being represented, keeping the
3571 * high bits and throwing away the low bits.
3573 key
&= ~(((hammer2_key_t
)1 << keybits
) - 1);
3576 * Ok, create our new indirect block
3578 if (for_type
== HAMMER2_BREF_TYPE_FREEMAP_NODE
||
3579 for_type
== HAMMER2_BREF_TYPE_FREEMAP_LEAF
) {
3580 dummy
.bref
.type
= HAMMER2_BREF_TYPE_FREEMAP_NODE
;
3582 dummy
.bref
.type
= HAMMER2_BREF_TYPE_INDIRECT
;
3584 dummy
.bref
.key
= key
;
3585 dummy
.bref
.keybits
= keybits
;
3586 dummy
.bref
.data_off
= hammer2_getradix(nbytes
);
3587 dummy
.bref
.methods
=
3588 HAMMER2_ENC_CHECK(HAMMER2_DEC_CHECK(parent
->bref
.methods
)) |
3589 HAMMER2_ENC_COMP(HAMMER2_COMP_NONE
);
3591 ichain
= hammer2_chain_alloc(hmp
, parent
->pmp
, &dummy
.bref
);
3592 atomic_set_int(&ichain
->flags
, HAMMER2_CHAIN_INITIAL
);
3593 hammer2_chain_lock(ichain
, HAMMER2_RESOLVE_MAYBE
);
3594 /* ichain has one ref at this point */
3597 * We have to mark it modified to allocate its block, but use
3598 * OPTDATA to allow it to remain in the INITIAL state. Otherwise
3599 * it won't be acted upon by the flush code.
3601 hammer2_chain_modify(ichain
, mtid
, 0, HAMMER2_MODIFY_OPTDATA
);
3604 * Iterate the original parent and move the matching brefs into
3605 * the new indirect block.
3607 * XXX handle flushes.
3610 key_end
= HAMMER2_KEY_MAX
;
3611 key_next
= 0; /* avoid gcc warnings */
3613 hammer2_spin_ex(&parent
->core
.spin
);
3619 * Parent may have been modified, relocating its block array.
3620 * Reload the base pointer.
3622 base
= hammer2_chain_base_and_count(parent
, &count
);
3624 if (++loops
> 100000) {
3625 hammer2_spin_unex(&parent
->core
.spin
);
3626 panic("excessive loops r=%d p=%p base/count %p:%d %016jx\n",
3627 reason
, parent
, base
, count
, key_next
);
3631 * NOTE: spinlock stays intact, returned chain (if not NULL)
3632 * is not referenced or locked which means that we
3633 * cannot safely check its flagged / deletion status
3636 chain
= hammer2_combined_find(parent
, base
, count
,
3637 &cache_index
, &key_next
,
3640 generation
= parent
->core
.generation
;
3643 key_next
= bref
->key
+ ((hammer2_key_t
)1 << bref
->keybits
);
3646 * Skip keys that are not within the key/radix of the new
3647 * indirect block. They stay in the parent.
3649 if ((~(((hammer2_key_t
)1 << keybits
) - 1) &
3650 (key
^ bref
->key
)) != 0) {
3651 goto next_key_spinlocked
;
3655 * Load the new indirect block by acquiring the related
3656 * chains (potentially from media as it might not be
3657 * in-memory). Then move it to the new parent (ichain).
3659 * chain is referenced but not locked. We must lock the
3660 * chain to obtain definitive state.
3664 * Use chain already present in the RBTREE
3666 hammer2_chain_ref(chain
);
3667 hammer2_spin_unex(&parent
->core
.spin
);
3668 hammer2_chain_lock(chain
, HAMMER2_RESOLVE_NEVER
);
3671 * Get chain for blockref element. _get returns NULL
3672 * on insertion race.
3675 hammer2_spin_unex(&parent
->core
.spin
);
3676 chain
= hammer2_chain_get(parent
, generation
, &bcopy
);
3677 if (chain
== NULL
) {
3679 hammer2_spin_ex(&parent
->core
.spin
);
3682 if (bcmp(&bcopy
, bref
, sizeof(bcopy
))) {
3683 kprintf("REASON 2\n");
3685 hammer2_chain_drop(chain
);
3686 hammer2_spin_ex(&parent
->core
.spin
);
3689 hammer2_chain_lock(chain
, HAMMER2_RESOLVE_NEVER
);
3693 * This is always live so if the chain has been deleted
3694 * we raced someone and we have to retry.
3696 * NOTE: Lookups can race delete-duplicate because
3697 * delete-duplicate does not lock the parent's core
3698 * (they just use the spinlock on the core).
3700 * (note reversed logic for this one)
3702 if (chain
->flags
& HAMMER2_CHAIN_DELETED
) {
3703 hammer2_chain_unlock(chain
);
3704 hammer2_chain_drop(chain
);
3709 * Shift the chain to the indirect block.
3711 * WARNING! No reason for us to load chain data, pass NOSTATS
3712 * to prevent delete/insert from trying to access
3713 * inode stats (and thus asserting if there is no
3714 * chain->data loaded).
3716 * WARNING! The (parent, chain) deletion may modify the parent
3717 * and invalidate the base pointer.
3719 hammer2_chain_delete(parent
, chain
, mtid
, 0);
3720 hammer2_chain_rename(NULL
, &ichain
, chain
, mtid
, 0);
3721 hammer2_chain_unlock(chain
);
3722 hammer2_chain_drop(chain
);
3723 KKASSERT(parent
->refs
> 0);
3725 base
= NULL
; /* safety */
3727 hammer2_spin_ex(&parent
->core
.spin
);
3728 next_key_spinlocked
:
3729 if (--maxloops
== 0)
3730 panic("hammer2_chain_create_indirect: maxloops");
3732 if (key_next
== 0 || key_next
> key_end
)
3737 hammer2_spin_unex(&parent
->core
.spin
);
3740 * Insert the new indirect block into the parent now that we've
3741 * cleared out some entries in the parent. We calculated a good
3742 * insertion index in the loop above (ichain->index).
3744 * We don't have to set UPDATE here because we mark ichain
3745 * modified down below (so the normal modified -> flush -> set-moved
3746 * sequence applies).
3748 * The insertion shouldn't race as this is a completely new block
3749 * and the parent is locked.
3751 base
= NULL
; /* safety, parent modify may change address */
3752 KKASSERT((ichain
->flags
& HAMMER2_CHAIN_ONRBTREE
) == 0);
3753 hammer2_chain_insert(parent
, ichain
,
3754 HAMMER2_CHAIN_INSERT_SPIN
|
3755 HAMMER2_CHAIN_INSERT_LIVE
,
3759 * Make sure flushes propogate after our manual insertion.
3761 hammer2_chain_setflush(ichain
);
3762 hammer2_chain_setflush(parent
);
3765 * Figure out what to return.
3767 if (~(((hammer2_key_t
)1 << keybits
) - 1) &
3768 (create_key
^ key
)) {
3770 * Key being created is outside the key range,
3771 * return the original parent.
3773 hammer2_chain_unlock(ichain
);
3774 hammer2_chain_drop(ichain
);
3777 * Otherwise its in the range, return the new parent.
3778 * (leave both the new and old parent locked).
3787 * Freemap indirect blocks
3789 * Calculate the keybits and highside/lowside of the freemap node the
3790 * caller is creating.
3792 * This routine will specify the next higher-level freemap key/radix
3793 * representing the lowest-ordered set. By doing so, eventually all
3794 * low-ordered sets will be moved one level down.
3796 * We have to be careful here because the freemap reserves a limited
3797 * number of blocks for a limited number of levels. So we can't just
3798 * push indiscriminately.
3801 hammer2_chain_indkey_freemap(hammer2_chain_t
*parent
, hammer2_key_t
*keyp
,
3802 int keybits
, hammer2_blockref_t
*base
, int count
)
3804 hammer2_chain_t
*chain
;
3805 hammer2_blockref_t
*bref
;
3807 hammer2_key_t key_beg
;
3808 hammer2_key_t key_end
;
3809 hammer2_key_t key_next
;
3813 int maxloops
= 300000;
3821 * Calculate the range of keys in the array being careful to skip
3822 * slots which are overridden with a deletion.
3825 key_end
= HAMMER2_KEY_MAX
;
3827 hammer2_spin_ex(&parent
->core
.spin
);
3830 if (--maxloops
== 0) {
3831 panic("indkey_freemap shit %p %p:%d\n",
3832 parent
, base
, count
);
3834 chain
= hammer2_combined_find(parent
, base
, count
,
3835 &cache_index
, &key_next
,
3846 * Skip deleted chains.
3848 if (chain
&& (chain
->flags
& HAMMER2_CHAIN_DELETED
)) {
3849 if (key_next
== 0 || key_next
> key_end
)
3856 * Use the full live (not deleted) element for the scan
3857 * iteration. HAMMER2 does not allow partial replacements.
3859 * XXX should be built into hammer2_combined_find().
3861 key_next
= bref
->key
+ ((hammer2_key_t
)1 << bref
->keybits
);
3863 if (keybits
> bref
->keybits
) {
3865 keybits
= bref
->keybits
;
3866 } else if (keybits
== bref
->keybits
&& bref
->key
< key
) {
3873 hammer2_spin_unex(&parent
->core
.spin
);
3876 * Return the keybits for a higher-level FREEMAP_NODE covering
3880 case HAMMER2_FREEMAP_LEVEL0_RADIX
:
3881 keybits
= HAMMER2_FREEMAP_LEVEL1_RADIX
;
3883 case HAMMER2_FREEMAP_LEVEL1_RADIX
:
3884 keybits
= HAMMER2_FREEMAP_LEVEL2_RADIX
;
3886 case HAMMER2_FREEMAP_LEVEL2_RADIX
:
3887 keybits
= HAMMER2_FREEMAP_LEVEL3_RADIX
;
3889 case HAMMER2_FREEMAP_LEVEL3_RADIX
:
3890 keybits
= HAMMER2_FREEMAP_LEVEL4_RADIX
;
3892 case HAMMER2_FREEMAP_LEVEL4_RADIX
:
3893 keybits
= HAMMER2_FREEMAP_LEVEL5_RADIX
;
3895 case HAMMER2_FREEMAP_LEVEL5_RADIX
:
3896 panic("hammer2_chain_indkey_freemap: level too high");
3899 panic("hammer2_chain_indkey_freemap: bad radix");
3908 * File indirect blocks
3910 * Calculate the key/keybits for the indirect block to create by scanning
3911 * existing keys. The key being created is also passed in *keyp and can be
3912 * inside or outside the indirect block. Regardless, the indirect block
3913 * must hold at least two keys in order to guarantee sufficient space.
3915 * We use a modified version of the freemap's fixed radix tree, but taylored
3916 * for file data. Basically we configure an indirect block encompassing the
3920 hammer2_chain_indkey_file(hammer2_chain_t
*parent
, hammer2_key_t
*keyp
,
3921 int keybits
, hammer2_blockref_t
*base
, int count
,
3924 hammer2_chain_t
*chain
;
3925 hammer2_blockref_t
*bref
;
3927 hammer2_key_t key_beg
;
3928 hammer2_key_t key_end
;
3929 hammer2_key_t key_next
;
3934 int maxloops
= 300000;
3942 * Calculate the range of keys in the array being careful to skip
3943 * slots which are overridden with a deletion.
3945 * Locate the smallest key.
3948 key_end
= HAMMER2_KEY_MAX
;
3950 hammer2_spin_ex(&parent
->core
.spin
);
3953 if (--maxloops
== 0) {
3954 panic("indkey_freemap shit %p %p:%d\n",
3955 parent
, base
, count
);
3957 chain
= hammer2_combined_find(parent
, base
, count
,
3958 &cache_index
, &key_next
,
3969 * Skip deleted chains.
3971 if (chain
&& (chain
->flags
& HAMMER2_CHAIN_DELETED
)) {
3972 if (key_next
== 0 || key_next
> key_end
)
3979 * Use the full live (not deleted) element for the scan
3980 * iteration. HAMMER2 does not allow partial replacements.
3982 * XXX should be built into hammer2_combined_find().
3984 key_next
= bref
->key
+ ((hammer2_key_t
)1 << bref
->keybits
);
3986 if (keybits
> bref
->keybits
) {
3988 keybits
= bref
->keybits
;
3989 } else if (keybits
== bref
->keybits
&& bref
->key
< key
) {
3996 hammer2_spin_unex(&parent
->core
.spin
);
3999 * Calculate the static keybits for a higher-level indirect block
4000 * that contains the key.
4005 case HAMMER2_IND_BYTES_MIN
/ sizeof(hammer2_blockref_t
):
4006 nradix
= HAMMER2_IND_RADIX_MIN
- HAMMER2_BLOCKREF_RADIX
;
4008 case HAMMER2_IND_BYTES_NOM
/ sizeof(hammer2_blockref_t
):
4009 nradix
= HAMMER2_IND_RADIX_NOM
- HAMMER2_BLOCKREF_RADIX
;
4011 case HAMMER2_IND_BYTES_MAX
/ sizeof(hammer2_blockref_t
):
4012 nradix
= HAMMER2_IND_RADIX_MAX
- HAMMER2_BLOCKREF_RADIX
;
4015 panic("bad ncount %d\n", ncount
);
4021 * The largest radix that can be returned for an indirect block is
4022 * 63 bits. (The largest practical indirect block radix is actually
4023 * 62 bits because the top-level inode or volume root contains four
4024 * entries, but allow 63 to be returned).
4029 return keybits
+ nradix
;
4035 * Directory indirect blocks.
4037 * Covers both the inode index (directory of inodes), and directory contents
4038 * (filenames hardlinked to inodes).
4040 * Because directory keys are hashed we generally try to cut the space in
4041 * half. We accomodate the inode index (which tends to have linearly
4042 * increasing inode numbers) by ensuring that the keyspace is at least large
4043 * enough to fill up the indirect block being created.
4046 hammer2_chain_indkey_dir(hammer2_chain_t
*parent
, hammer2_key_t
*keyp
,
4047 int keybits
, hammer2_blockref_t
*base
, int count
,
4050 hammer2_blockref_t
*bref
;
4051 hammer2_chain_t
*chain
;
4052 hammer2_key_t key_beg
;
4053 hammer2_key_t key_end
;
4054 hammer2_key_t key_next
;
4060 int maxloops
= 300000;
4063 * Shortcut if the parent is the inode. In this situation the
4064 * parent has 4+1 directory entries and we are creating an indirect
4065 * block capable of holding many more.
4067 if (parent
->bref
.type
== HAMMER2_BREF_TYPE_INODE
) {
4076 * Calculate the range of keys in the array being careful to skip
4077 * slots which are overridden with a deletion.
4080 key_end
= HAMMER2_KEY_MAX
;
4082 hammer2_spin_ex(&parent
->core
.spin
);
4085 if (--maxloops
== 0) {
4086 panic("indkey_freemap shit %p %p:%d\n",
4087 parent
, base
, count
);
4089 chain
= hammer2_combined_find(parent
, base
, count
,
4090 &cache_index
, &key_next
,
4103 if (chain
&& (chain
->flags
& HAMMER2_CHAIN_DELETED
)) {
4104 if (key_next
== 0 || key_next
> key_end
)
4111 * Use the full live (not deleted) element for the scan
4112 * iteration. HAMMER2 does not allow partial replacements.
4114 * XXX should be built into hammer2_combined_find().
4116 key_next
= bref
->key
+ ((hammer2_key_t
)1 << bref
->keybits
);
4119 * Expand our calculated key range (key, keybits) to fit
4120 * the scanned key. nkeybits represents the full range
4121 * that we will later cut in half (two halves @ nkeybits - 1).
4124 if (nkeybits
< bref
->keybits
) {
4125 if (bref
->keybits
> 64) {
4126 kprintf("bad bref chain %p bref %p\n",
4130 nkeybits
= bref
->keybits
;
4132 while (nkeybits
< 64 &&
4133 (~(((hammer2_key_t
)1 << nkeybits
) - 1) &
4134 (key
^ bref
->key
)) != 0) {
4139 * If the new key range is larger we have to determine
4140 * which side of the new key range the existing keys fall
4141 * under by checking the high bit, then collapsing the
4142 * locount into the hicount or vise-versa.
4144 if (keybits
!= nkeybits
) {
4145 if (((hammer2_key_t
)1 << (nkeybits
- 1)) & key
) {
4156 * The newly scanned key will be in the lower half or the
4157 * upper half of the (new) key range.
4159 if (((hammer2_key_t
)1 << (nkeybits
- 1)) & bref
->key
)
4168 hammer2_spin_unex(&parent
->core
.spin
);
4169 bref
= NULL
; /* now invalid (safety) */
4172 * Adjust keybits to represent half of the full range calculated
4173 * above (radix 63 max) for our new indirect block.
4178 * Expand keybits to hold at least ncount elements. ncount will be
4179 * a power of 2. This is to try to completely fill leaf nodes (at
4180 * least for keys which are not hashes).
4182 * We aren't counting 'in' or 'out', we are counting 'high side'
4183 * and 'low side' based on the bit at (1LL << keybits). We want
4184 * everything to be inside in these cases so shift it all to
4185 * the low or high side depending on the new high bit.
4187 while (((hammer2_key_t
)1 << keybits
) < ncount
) {
4189 if (key
& ((hammer2_key_t
)1 << keybits
)) {
4198 if (hicount
> locount
)
4199 key
|= (hammer2_key_t
)1 << keybits
;
4201 key
&= ~(hammer2_key_t
)1 << keybits
;
4211 * Directory indirect blocks.
4213 * Covers both the inode index (directory of inodes), and directory contents
4214 * (filenames hardlinked to inodes).
4216 * Because directory keys are hashed we generally try to cut the space in
4217 * half. We accomodate the inode index (which tends to have linearly
4218 * increasing inode numbers) by ensuring that the keyspace is at least large
4219 * enough to fill up the indirect block being created.
4222 hammer2_chain_indkey_dir(hammer2_chain_t
*parent
, hammer2_key_t
*keyp
,
4223 int keybits
, hammer2_blockref_t
*base
, int count
,
4226 hammer2_blockref_t
*bref
;
4227 hammer2_chain_t
*chain
;
4228 hammer2_key_t key_beg
;
4229 hammer2_key_t key_end
;
4230 hammer2_key_t key_next
;
4236 int maxloops
= 300000;
4239 * Shortcut if the parent is the inode. In this situation the
4240 * parent has 4+1 directory entries and we are creating an indirect
4241 * block capable of holding many more.
4243 if (parent
->bref
.type
== HAMMER2_BREF_TYPE_INODE
) {
4252 * Calculate the range of keys in the array being careful to skip
4253 * slots which are overridden with a deletion.
4256 key_end
= HAMMER2_KEY_MAX
;
4258 hammer2_spin_ex(&parent
->core
.spin
);
4261 if (--maxloops
== 0) {
4262 panic("indkey_freemap shit %p %p:%d\n",
4263 parent
, base
, count
);
4265 chain
= hammer2_combined_find(parent
, base
, count
,
4266 &cache_index
, &key_next
,
4279 if (chain
&& (chain
->flags
& HAMMER2_CHAIN_DELETED
)) {
4280 if (key_next
== 0 || key_next
> key_end
)
4287 * Use the full live (not deleted) element for the scan
4288 * iteration. HAMMER2 does not allow partial replacements.
4290 * XXX should be built into hammer2_combined_find().
4292 key_next
= bref
->key
+ ((hammer2_key_t
)1 << bref
->keybits
);
4295 * Expand our calculated key range (key, keybits) to fit
4296 * the scanned key. nkeybits represents the full range
4297 * that we will later cut in half (two halves @ nkeybits - 1).
4300 if (nkeybits
< bref
->keybits
) {
4301 if (bref
->keybits
> 64) {
4302 kprintf("bad bref chain %p bref %p\n",
4306 nkeybits
= bref
->keybits
;
4308 while (nkeybits
< 64 &&
4309 (~(((hammer2_key_t
)1 << nkeybits
) - 1) &
4310 (key
^ bref
->key
)) != 0) {
4315 * If the new key range is larger we have to determine
4316 * which side of the new key range the existing keys fall
4317 * under by checking the high bit, then collapsing the
4318 * locount into the hicount or vise-versa.
4320 if (keybits
!= nkeybits
) {
4321 if (((hammer2_key_t
)1 << (nkeybits
- 1)) & key
) {
4332 * The newly scanned key will be in the lower half or the
4333 * upper half of the (new) key range.
4335 if (((hammer2_key_t
)1 << (nkeybits
- 1)) & bref
->key
)
4344 hammer2_spin_unex(&parent
->core
.spin
);
4345 bref
= NULL
; /* now invalid (safety) */
4348 * Adjust keybits to represent half of the full range calculated
4349 * above (radix 63 max) for our new indirect block.
4354 * Expand keybits to hold at least ncount elements. ncount will be
4355 * a power of 2. This is to try to completely fill leaf nodes (at
4356 * least for keys which are not hashes).
4358 * We aren't counting 'in' or 'out', we are counting 'high side'
4359 * and 'low side' based on the bit at (1LL << keybits). We want
4360 * everything to be inside in these cases so shift it all to
4361 * the low or high side depending on the new high bit.
4363 while (((hammer2_key_t
)1 << keybits
) < ncount
) {
4365 if (key
& ((hammer2_key_t
)1 << keybits
)) {
4374 if (hicount
> locount
)
4375 key
|= (hammer2_key_t
)1 << keybits
;
4377 key
&= ~(hammer2_key_t
)1 << keybits
;
4387 * Sets CHAIN_DELETED and remove the chain's blockref from the parent if
4390 * Both parent and chain must be locked exclusively.
4392 * This function will modify the parent if the blockref requires removal
4393 * from the parent's block table.
4395 * This function is NOT recursive. Any entity already pushed into the
4396 * chain (such as an inode) may still need visibility into its contents,
4397 * as well as the ability to read and modify the contents. For example,
4398 * for an unlinked file which is still open.
4400 * Also note that the flusher is responsible for cleaning up empty
4404 hammer2_chain_delete(hammer2_chain_t
*parent
, hammer2_chain_t
*chain
,
4405 hammer2_tid_t mtid
, int flags
)
4407 KKASSERT(hammer2_mtx_owned(&chain
->lock
));
4410 * Nothing to do if already marked.
4412 * We need the spinlock on the core whos RBTREE contains chain
4413 * to protect against races.
4415 if ((chain
->flags
& HAMMER2_CHAIN_DELETED
) == 0) {
4416 KKASSERT((chain
->flags
& HAMMER2_CHAIN_DELETED
) == 0 &&
4417 chain
->parent
== parent
);
4418 _hammer2_chain_delete_helper(parent
, chain
, mtid
, flags
);
4422 * Permanent deletions mark the chain as destroyed.
4424 if (flags
& HAMMER2_DELETE_PERMANENT
) {
4425 atomic_set_int(&chain
->flags
, HAMMER2_CHAIN_DESTROY
);
4427 /* XXX might not be needed */
4428 hammer2_chain_setflush(chain
);
4433 * Returns the index of the nearest element in the blockref array >= elm.
4434 * Returns (count) if no element could be found.
4436 * Sets *key_nextp to the next key for loop purposes but does not modify
4437 * it if the next key would be higher than the current value of *key_nextp.
4438 * Note that *key_nexp can overflow to 0, which should be tested by the
4441 * (*cache_indexp) is a heuristic and can be any value without effecting
4444 * WARNING! Must be called with parent's spinlock held. Spinlock remains
4445 * held through the operation.
4448 hammer2_base_find(hammer2_chain_t
*parent
,
4449 hammer2_blockref_t
*base
, int count
,
4450 int *cache_indexp
, hammer2_key_t
*key_nextp
,
4451 hammer2_key_t key_beg
, hammer2_key_t key_end
)
4453 hammer2_blockref_t
*scan
;
4454 hammer2_key_t scan_end
;
4459 * Require the live chain's already have their core's counted
4460 * so we can optimize operations.
4462 KKASSERT(parent
->flags
& HAMMER2_CHAIN_COUNTEDBREFS
);
4467 if (count
== 0 || base
== NULL
)
4471 * Sequential optimization using *cache_indexp. This is the most
4474 * We can avoid trailing empty entries on live chains, otherwise
4475 * we might have to check the whole block array.
4479 limit
= parent
->core
.live_zero
;
4484 KKASSERT(i
< count
);
4490 while (i
> 0 && (scan
->type
== 0 || scan
->key
> key_beg
)) {
4497 * Search forwards, stop when we find a scan element which
4498 * encloses the key or until we know that there are no further
4502 if (scan
->type
!= 0) {
4503 scan_end
= scan
->key
+
4504 ((hammer2_key_t
)1 << scan
->keybits
) - 1;
4505 if (scan
->key
> key_beg
|| scan_end
>= key_beg
)
4518 scan_end
= scan
->key
+
4519 ((hammer2_key_t
)1 << scan
->keybits
);
4520 if (scan_end
&& (*key_nextp
> scan_end
||
4522 *key_nextp
= scan_end
;
4530 * Do a combined search and return the next match either from the blockref
4531 * array or from the in-memory chain. Sets *bresp to the returned bref in
4532 * both cases, or sets it to NULL if the search exhausted. Only returns
4533 * a non-NULL chain if the search matched from the in-memory chain.
4535 * When no in-memory chain has been found and a non-NULL bref is returned
4539 * The returned chain is not locked or referenced. Use the returned bref
4540 * to determine if the search exhausted or not. Iterate if the base find
4541 * is chosen but matches a deleted chain.
4543 * WARNING! Must be called with parent's spinlock held. Spinlock remains
4544 * held through the operation.
4546 static hammer2_chain_t
*
4547 hammer2_combined_find(hammer2_chain_t
*parent
,
4548 hammer2_blockref_t
*base
, int count
,
4549 int *cache_indexp
, hammer2_key_t
*key_nextp
,
4550 hammer2_key_t key_beg
, hammer2_key_t key_end
,
4551 hammer2_blockref_t
**bresp
)
4553 hammer2_blockref_t
*bref
;
4554 hammer2_chain_t
*chain
;
4558 * Lookup in block array and in rbtree.
4560 *key_nextp
= key_end
+ 1;
4561 i
= hammer2_base_find(parent
, base
, count
, cache_indexp
,
4562 key_nextp
, key_beg
, key_end
);
4563 chain
= hammer2_chain_find(parent
, key_nextp
, key_beg
, key_end
);
4568 if (i
== count
&& chain
== NULL
) {
4574 * Only chain matched.
4577 bref
= &chain
->bref
;
4582 * Only blockref matched.
4584 if (chain
== NULL
) {
4590 * Both in-memory and blockref matched, select the nearer element.
4592 * If both are flush with the left-hand side or both are the
4593 * same distance away, select the chain. In this situation the
4594 * chain must have been loaded from the matching blockmap.
4596 if ((chain
->bref
.key
<= key_beg
&& base
[i
].key
<= key_beg
) ||
4597 chain
->bref
.key
== base
[i
].key
) {
4598 KKASSERT(chain
->bref
.key
== base
[i
].key
);
4599 bref
= &chain
->bref
;
4604 * Select the nearer key
4606 if (chain
->bref
.key
< base
[i
].key
) {
4607 bref
= &chain
->bref
;
4614 * If the bref is out of bounds we've exhausted our search.
4617 if (bref
->key
> key_end
) {
4627 * Locate the specified block array element and delete it. The element
4630 * The spin lock on the related chain must be held.
4632 * NOTE: live_count was adjusted when the chain was deleted, so it does not
4633 * need to be adjusted when we commit the media change.
4636 hammer2_base_delete(hammer2_chain_t
*parent
,
4637 hammer2_blockref_t
*base
, int count
,
4638 int *cache_indexp
, hammer2_chain_t
*chain
)
4640 hammer2_blockref_t
*elm
= &chain
->bref
;
4641 hammer2_blockref_t
*scan
;
4642 hammer2_key_t key_next
;
4646 * Delete element. Expect the element to exist.
4648 * XXX see caller, flush code not yet sophisticated enough to prevent
4649 * re-flushed in some cases.
4651 key_next
= 0; /* max range */
4652 i
= hammer2_base_find(parent
, base
, count
, cache_indexp
,
4653 &key_next
, elm
->key
, elm
->key
);
4655 if (i
== count
|| scan
->type
== 0 ||
4656 scan
->key
!= elm
->key
||
4657 ((chain
->flags
& HAMMER2_CHAIN_BMAPUPD
) == 0 &&
4658 scan
->keybits
!= elm
->keybits
)) {
4659 hammer2_spin_unex(&parent
->core
.spin
);
4660 panic("delete base %p element not found at %d/%d elm %p\n",
4661 base
, i
, count
, elm
);
4666 * Update stats and zero the entry.
4668 * NOTE: Handle radix == 0 (0 bytes) case.
4670 if ((int)(scan
->data_off
& HAMMER2_OFF_MASK_RADIX
)) {
4671 parent
->bref
.embed
.stats
.data_count
-= (hammer2_off_t
)1 <<
4672 (int)(scan
->data_off
& HAMMER2_OFF_MASK_RADIX
);
4674 switch(scan
->type
) {
4675 case HAMMER2_BREF_TYPE_INODE
:
4676 parent
->bref
.embed
.stats
.inode_count
-= 1;
4678 case HAMMER2_BREF_TYPE_DATA
:
4679 case HAMMER2_BREF_TYPE_INDIRECT
:
4680 parent
->bref
.embed
.stats
.data_count
-=
4681 scan
->embed
.stats
.data_count
;
4682 parent
->bref
.embed
.stats
.inode_count
-=
4683 scan
->embed
.stats
.inode_count
;
4689 bzero(scan
, sizeof(*scan
));
4692 * We can only optimize parent->core.live_zero for live chains.
4694 if (parent
->core
.live_zero
== i
+ 1) {
4695 while (--i
>= 0 && base
[i
].type
== 0)
4697 parent
->core
.live_zero
= i
+ 1;
4701 * Clear appropriate blockmap flags in chain.
4703 atomic_clear_int(&chain
->flags
, HAMMER2_CHAIN_BMAPPED
|
4704 HAMMER2_CHAIN_BMAPUPD
);
4708 * Insert the specified element. The block array must not already have the
4709 * element and must have space available for the insertion.
4711 * The spin lock on the related chain must be held.
4713 * NOTE: live_count was adjusted when the chain was deleted, so it does not
4714 * need to be adjusted when we commit the media change.
4717 hammer2_base_insert(hammer2_chain_t
*parent
,
4718 hammer2_blockref_t
*base
, int count
,
4719 int *cache_indexp
, hammer2_chain_t
*chain
)
4721 hammer2_blockref_t
*elm
= &chain
->bref
;
4722 hammer2_key_t key_next
;
4731 * Insert new element. Expect the element to not already exist
4732 * unless we are replacing it.
4734 * XXX see caller, flush code not yet sophisticated enough to prevent
4735 * re-flushed in some cases.
4737 key_next
= 0; /* max range */
4738 i
= hammer2_base_find(parent
, base
, count
, cache_indexp
,
4739 &key_next
, elm
->key
, elm
->key
);
4742 * Shortcut fill optimization, typical ordered insertion(s) may not
4745 KKASSERT(i
>= 0 && i
<= count
);
4748 * Set appropriate blockmap flags in chain.
4750 atomic_set_int(&chain
->flags
, HAMMER2_CHAIN_BMAPPED
);
4753 * Update stats and zero the entry
4755 if ((int)(elm
->data_off
& HAMMER2_OFF_MASK_RADIX
)) {
4756 parent
->bref
.embed
.stats
.data_count
+= (hammer2_off_t
)1 <<
4757 (int)(elm
->data_off
& HAMMER2_OFF_MASK_RADIX
);
4760 case HAMMER2_BREF_TYPE_INODE
:
4761 parent
->bref
.embed
.stats
.inode_count
+= 1;
4763 case HAMMER2_BREF_TYPE_DATA
:
4764 case HAMMER2_BREF_TYPE_INDIRECT
:
4765 parent
->bref
.embed
.stats
.data_count
+=
4766 elm
->embed
.stats
.data_count
;
4767 parent
->bref
.embed
.stats
.inode_count
+=
4768 elm
->embed
.stats
.inode_count
;
4776 * We can only optimize parent->core.live_zero for live chains.
4778 if (i
== count
&& parent
->core
.live_zero
< count
) {
4779 i
= parent
->core
.live_zero
++;
4784 xkey
= elm
->key
+ ((hammer2_key_t
)1 << elm
->keybits
) - 1;
4785 if (i
!= count
&& (base
[i
].key
< elm
->key
|| xkey
>= base
[i
].key
)) {
4786 hammer2_spin_unex(&parent
->core
.spin
);
4787 panic("insert base %p overlapping elements at %d elm %p\n",
4792 * Try to find an empty slot before or after.
4796 while (j
> 0 || k
< count
) {
4798 if (j
>= 0 && base
[j
].type
== 0) {
4802 bcopy(&base
[j
+1], &base
[j
],
4803 (i
- j
- 1) * sizeof(*base
));
4809 if (k
< count
&& base
[k
].type
== 0) {
4810 bcopy(&base
[i
], &base
[i
+1],
4811 (k
- i
) * sizeof(hammer2_blockref_t
));
4815 * We can only update parent->core.live_zero for live
4818 if (parent
->core
.live_zero
<= k
)
4819 parent
->core
.live_zero
= k
+ 1;
4824 panic("hammer2_base_insert: no room!");
4831 for (l
= 0; l
< count
; ++l
) {
4833 key_next
= base
[l
].key
+
4834 ((hammer2_key_t
)1 << base
[l
].keybits
) - 1;
4838 while (++l
< count
) {
4840 if (base
[l
].key
<= key_next
)
4841 panic("base_insert %d %d,%d,%d fail %p:%d", u
, i
, j
, k
, base
, l
);
4842 key_next
= base
[l
].key
+
4843 ((hammer2_key_t
)1 << base
[l
].keybits
) - 1;
4853 * Sort the blockref array for the chain. Used by the flush code to
4854 * sort the blockref[] array.
4856 * The chain must be exclusively locked AND spin-locked.
4858 typedef hammer2_blockref_t
*hammer2_blockref_p
;
4862 hammer2_base_sort_callback(const void *v1
, const void *v2
)
4864 hammer2_blockref_p bref1
= *(const hammer2_blockref_p
*)v1
;
4865 hammer2_blockref_p bref2
= *(const hammer2_blockref_p
*)v2
;
4868 * Make sure empty elements are placed at the end of the array
4870 if (bref1
->type
== 0) {
4871 if (bref2
->type
== 0)
4874 } else if (bref2
->type
== 0) {
4881 if (bref1
->key
< bref2
->key
)
4883 if (bref1
->key
> bref2
->key
)
4889 hammer2_base_sort(hammer2_chain_t
*chain
)
4891 hammer2_blockref_t
*base
;
4894 switch(chain
->bref
.type
) {
4895 case HAMMER2_BREF_TYPE_INODE
:
4897 * Special shortcut for embedded data returns the inode
4898 * itself. Callers must detect this condition and access
4899 * the embedded data (the strategy code does this for us).
4901 * This is only applicable to regular files and softlinks.
4903 if (chain
->data
->ipdata
.meta
.op_flags
&
4904 HAMMER2_OPFLAG_DIRECTDATA
) {
4907 base
= &chain
->data
->ipdata
.u
.blockset
.blockref
[0];
4908 count
= HAMMER2_SET_COUNT
;
4910 case HAMMER2_BREF_TYPE_FREEMAP_NODE
:
4911 case HAMMER2_BREF_TYPE_INDIRECT
:
4913 * Optimize indirect blocks in the INITIAL state to avoid
4916 KKASSERT((chain
->flags
& HAMMER2_CHAIN_INITIAL
) == 0);
4917 base
= &chain
->data
->npdata
[0];
4918 count
= chain
->bytes
/ sizeof(hammer2_blockref_t
);
4920 case HAMMER2_BREF_TYPE_VOLUME
:
4921 base
= &chain
->data
->voldata
.sroot_blockset
.blockref
[0];
4922 count
= HAMMER2_SET_COUNT
;
4924 case HAMMER2_BREF_TYPE_FREEMAP
:
4925 base
= &chain
->data
->blkset
.blockref
[0];
4926 count
= HAMMER2_SET_COUNT
;
4929 kprintf("hammer2_chain_lookup: unrecognized "
4930 "blockref(A) type: %d",
4933 tsleep(&base
, 0, "dead", 0);
4934 panic("hammer2_chain_lookup: unrecognized "
4935 "blockref(A) type: %d",
4937 base
= NULL
; /* safety */
4938 count
= 0; /* safety */
4940 kqsort(base
, count
, sizeof(*base
), hammer2_base_sort_callback
);
4946 * Chain memory management
4949 hammer2_chain_wait(hammer2_chain_t
*chain
)
4951 tsleep(chain
, 0, "chnflw", 1);
4954 const hammer2_media_data_t
*
4955 hammer2_chain_rdata(hammer2_chain_t
*chain
)
4957 KKASSERT(chain
->data
!= NULL
);
4958 return (chain
->data
);
4961 hammer2_media_data_t
*
4962 hammer2_chain_wdata(hammer2_chain_t
*chain
)
4964 KKASSERT(chain
->data
!= NULL
);
4965 return (chain
->data
);
4969 * Set the check data for a chain. This can be a heavy-weight operation
4970 * and typically only runs on-flush. For file data check data is calculated
4971 * when the logical buffers are flushed.
4974 hammer2_chain_setcheck(hammer2_chain_t
*chain
, void *bdata
)
4976 chain
->bref
.flags
&= ~HAMMER2_BREF_FLAG_ZERO
;
4978 switch(HAMMER2_DEC_CHECK(chain
->bref
.methods
)) {
4979 case HAMMER2_CHECK_NONE
:
4981 case HAMMER2_CHECK_DISABLED
:
4983 case HAMMER2_CHECK_ISCSI32
:
4984 chain
->bref
.check
.iscsi32
.value
=
4985 hammer2_icrc32(bdata
, chain
->bytes
);
4987 case HAMMER2_CHECK_XXHASH64
:
4988 chain
->bref
.check
.xxhash64
.value
=
4989 XXH64(bdata
, chain
->bytes
, XXH_HAMMER2_SEED
);
4991 case HAMMER2_CHECK_SHA192
:
4993 SHA256_CTX hash_ctx
;
4995 uint8_t digest
[SHA256_DIGEST_LENGTH
];
4996 uint64_t digest64
[SHA256_DIGEST_LENGTH
/8];
4999 SHA256_Init(&hash_ctx
);
5000 SHA256_Update(&hash_ctx
, bdata
, chain
->bytes
);
5001 SHA256_Final(u
.digest
, &hash_ctx
);
5002 u
.digest64
[2] ^= u
.digest64
[3];
5004 chain
->bref
.check
.sha192
.data
,
5005 sizeof(chain
->bref
.check
.sha192
.data
));
5008 case HAMMER2_CHECK_FREEMAP
:
5009 chain
->bref
.check
.freemap
.icrc32
=
5010 hammer2_icrc32(bdata
, chain
->bytes
);
5013 kprintf("hammer2_chain_setcheck: unknown check type %02x\n",
5014 chain
->bref
.methods
);
5020 hammer2_chain_testcheck(hammer2_chain_t
*chain
, void *bdata
)
5026 if (chain
->bref
.flags
& HAMMER2_BREF_FLAG_ZERO
)
5029 switch(HAMMER2_DEC_CHECK(chain
->bref
.methods
)) {
5030 case HAMMER2_CHECK_NONE
:
5033 case HAMMER2_CHECK_DISABLED
:
5036 case HAMMER2_CHECK_ISCSI32
:
5037 check32
= hammer2_icrc32(bdata
, chain
->bytes
);
5038 r
= (chain
->bref
.check
.iscsi32
.value
== check32
);
5040 kprintf("chain %016jx.%02x meth=%02x CHECK FAIL "
5041 "(flags=%08x, bref/data %08x/%08x)\n",
5042 chain
->bref
.data_off
,
5044 chain
->bref
.methods
,
5046 chain
->bref
.check
.iscsi32
.value
,
5049 hammer2_check_icrc32
+= chain
->bytes
;
5051 case HAMMER2_CHECK_XXHASH64
:
5052 check64
= XXH64(bdata
, chain
->bytes
, XXH_HAMMER2_SEED
);
5053 r
= (chain
->bref
.check
.xxhash64
.value
== check64
);
5055 kprintf("chain %016jx.%02x key=%016jx "
5056 "meth=%02x CHECK FAIL "
5057 "(flags=%08x, bref/data %016jx/%016jx)\n",
5058 chain
->bref
.data_off
,
5061 chain
->bref
.methods
,
5063 chain
->bref
.check
.xxhash64
.value
,
5066 hammer2_check_xxhash64
+= chain
->bytes
;
5068 case HAMMER2_CHECK_SHA192
:
5070 SHA256_CTX hash_ctx
;
5072 uint8_t digest
[SHA256_DIGEST_LENGTH
];
5073 uint64_t digest64
[SHA256_DIGEST_LENGTH
/8];
5076 SHA256_Init(&hash_ctx
);
5077 SHA256_Update(&hash_ctx
, bdata
, chain
->bytes
);
5078 SHA256_Final(u
.digest
, &hash_ctx
);
5079 u
.digest64
[2] ^= u
.digest64
[3];
5081 chain
->bref
.check
.sha192
.data
,
5082 sizeof(chain
->bref
.check
.sha192
.data
)) == 0) {
5086 kprintf("chain %016jx.%02x meth=%02x "
5088 chain
->bref
.data_off
,
5090 chain
->bref
.methods
);
5094 case HAMMER2_CHECK_FREEMAP
:
5095 r
= (chain
->bref
.check
.freemap
.icrc32
==
5096 hammer2_icrc32(bdata
, chain
->bytes
));
5098 kprintf("chain %016jx.%02x meth=%02x "
5100 chain
->bref
.data_off
,
5102 chain
->bref
.methods
);
5103 kprintf("freemap.icrc %08x icrc32 %08x (%d)\n",
5104 chain
->bref
.check
.freemap
.icrc32
,
5105 hammer2_icrc32(bdata
, chain
->bytes
),
5108 kprintf("dio %p buf %016jx,%d bdata %p/%p\n",
5109 chain
->dio
, chain
->dio
->bp
->b_loffset
,
5110 chain
->dio
->bp
->b_bufsize
, bdata
,
5111 chain
->dio
->bp
->b_data
);
5116 kprintf("hammer2_chain_setcheck: unknown check type %02x\n",
5117 chain
->bref
.methods
);
5125 * Acquire the chain and parent representing the specified inode for the
5126 * device at the specified cluster index.
5128 * The flags passed in are LOOKUP flags, not RESOLVE flags.
5130 * If we are unable to locate the hardlink, INVAL is returned and *chainp
5131 * will be NULL. *parentp may still be set error or not, or NULL if the
5132 * parent itself could not be resolved.
5134 * Caller must pass-in a valid or NULL *parentp or *chainp. The passed-in
5135 * *parentp and *chainp will be unlocked if not NULL.
5138 hammer2_chain_inode_find(hammer2_pfs_t
*pmp
, hammer2_key_t inum
,
5139 int clindex
, int flags
,
5140 hammer2_chain_t
**parentp
, hammer2_chain_t
**chainp
)
5142 hammer2_chain_t
*parent
;
5143 hammer2_chain_t
*rchain
;
5144 hammer2_key_t key_dummy
;
5145 int cache_index
= -1;
5148 resolve_flags
= (flags
& HAMMER2_LOOKUP_SHARED
) ?
5149 HAMMER2_RESOLVE_SHARED
: 0;
5152 * Caller expects us to replace these.
5155 hammer2_chain_unlock(*chainp
);
5156 hammer2_chain_drop(*chainp
);
5160 hammer2_chain_unlock(*parentp
);
5161 hammer2_chain_drop(*parentp
);
5166 * Inodes hang off of the iroot (bit 63 is clear, differentiating
5167 * inodes from root directory entries in the key lookup).
5169 parent
= hammer2_inode_chain(pmp
->iroot
, clindex
, resolve_flags
);
5172 rchain
= hammer2_chain_lookup(&parent
, &key_dummy
,
5174 &cache_index
, flags
);
5179 return (rchain
? 0 : EINVAL
);
5183 * Used by the bulkscan code to snapshot the synchronized storage for
5184 * a volume, allowing it to be scanned concurrently against normal
5188 hammer2_chain_bulksnap(hammer2_dev_t
*hmp
)
5190 hammer2_chain_t
*copy
;
5192 copy
= hammer2_chain_alloc(hmp
, hmp
->spmp
, &hmp
->vchain
.bref
);
5193 copy
->data
= kmalloc(sizeof(copy
->data
->voldata
),
5196 hammer2_voldata_lock(hmp
);
5197 copy
->data
->voldata
= hmp
->volsync
;
5198 hammer2_voldata_unlock(hmp
);
5204 hammer2_chain_bulkdrop(hammer2_chain_t
*copy
)
5206 KKASSERT(copy
->bref
.type
== HAMMER2_BREF_TYPE_VOLUME
);
5207 KKASSERT(copy
->data
);
5208 kfree(copy
->data
, copy
->hmp
->mchain
);
5210 atomic_add_long(&hammer2_chain_allocs
, -1);
5211 hammer2_chain_drop(copy
);
5215 * Create a snapshot of the specified (chain) with the specified label.
5216 * The originating hammer2_inode must be exclusively locked for
5217 * safety. The device's bulklk should be held by the caller. The caller
5218 * is responsible for synchronizing the filesystem to storage before
5219 * taking the snapshot.
5222 hammer2_chain_snapshot(hammer2_chain_t
*chain
, hammer2_ioc_pfs_t
*pmp
,
5226 const hammer2_inode_data_t
*ripdata
;
5227 hammer2_inode_data_t
*wipdata
;
5228 hammer2_chain_t
*nchain
;
5229 hammer2_inode_t
*nip
;
5238 kprintf("snapshot %s\n", pmp
->name
);
5240 name_len
= strlen(pmp
->name
);
5241 lhc
= hammer2_dirhash(pmp
->name
, name_len
);
5246 ripdata
= &chain
->data
->ipdata
;
5248 opfs_clid
= ripdata
->meta
.pfs_clid
;
5253 * Create the snapshot directory under the super-root
5255 * Set PFS type, generate a unique filesystem id, and generate
5256 * a cluster id. Use the same clid when snapshotting a PFS root,
5257 * which theoretically allows the snapshot to be used as part of
5258 * the same cluster (perhaps as a cache).
5260 * Copy the (flushed) blockref array. Theoretically we could use
5261 * chain_duplicate() but it becomes difficult to disentangle
5262 * the shared core so for now just brute-force it.
5267 hammer2_chain_unlock(chain
);
5268 nip
= hammer2_inode_create(hmp
->spmp
->iroot
, hmp
->spmp
->iroot
,
5269 &vat
, proc0
.p_ucred
,
5270 pmp
->name
, name_len
, 0,
5272 HAMMER2_INSERT_PFSROOT
, &error
);
5273 hammer2_chain_lock(chain
, HAMMER2_RESOLVE_ALWAYS
);
5276 hammer2_inode_modify(nip
);
5277 nchain
= hammer2_inode_chain(nip
, 0, HAMMER2_RESOLVE_ALWAYS
);
5278 hammer2_chain_modify(nchain
, mtid
, 0, 0);
5279 wipdata
= &nchain
->data
->ipdata
;
5281 nip
->meta
.pfs_type
= HAMMER2_PFSTYPE_MASTER
;
5282 nip
->meta
.pfs_subtype
= HAMMER2_PFSSUBTYPE_SNAPSHOT
;
5283 nip
->meta
.op_flags
|= HAMMER2_OPFLAG_PFSROOT
;
5284 kern_uuidgen(&nip
->meta
.pfs_fsid
, 1);
5287 * Give the snapshot its own private cluster id. As a
5288 * snapshot no further synchronization with the original
5289 * cluster will be done.
5292 if (chain
->flags
& HAMMER2_CHAIN_PFSBOUNDARY
)
5293 nip
->meta
.pfs_clid
= opfs_clid
;
5295 kern_uuidgen(&nip
->meta
.pfs_clid
, 1);
5297 kern_uuidgen(&nip
->meta
.pfs_clid
, 1);
5298 nchain
->bref
.flags
|= HAMMER2_BREF_FLAG_PFSROOT
;
5300 /* XXX hack blockset copy */
5301 /* XXX doesn't work with real cluster */
5302 wipdata
->meta
= nip
->meta
;
5303 wipdata
->u
.blockset
= ripdata
->u
.blockset
;
5305 hammer2_flush(nchain
, 1);
5306 KKASSERT(wipdata
== &nchain
->data
->ipdata
);
5307 hammer2_pfsalloc(nchain
, wipdata
, nchain
->bref
.modify_tid
, 0);
5309 hammer2_chain_unlock(nchain
);
5310 hammer2_chain_drop(nchain
);
5311 hammer2_inode_chain_sync(nip
);
5312 hammer2_inode_unlock(nip
);
5313 hammer2_inode_run_sideq(hmp
->spmp
);
5319 * Returns non-zero if the chain (INODE or DIRENT) matches the
5323 hammer2_chain_dirent_test(hammer2_chain_t
*chain
, const char *name
,
5326 const hammer2_inode_data_t
*ripdata
;
5327 const hammer2_dirent_head_t
*den
;
5329 if (chain
->bref
.type
== HAMMER2_BREF_TYPE_INODE
) {
5330 ripdata
= &chain
->data
->ipdata
;
5331 if (ripdata
->meta
.name_len
== name_len
&&
5332 bcmp(ripdata
->filename
, name
, name_len
) == 0) {
5336 if (chain
->bref
.type
== HAMMER2_BREF_TYPE_DIRENT
&&
5337 chain
->bref
.embed
.dirent
.namlen
== name_len
) {
5338 den
= &chain
->bref
.embed
.dirent
;
5339 if (name_len
> sizeof(chain
->bref
.check
.buf
) &&
5340 bcmp(chain
->data
->buf
, name
, name_len
) == 0) {
5343 if (name_len
<= sizeof(chain
->bref
.check
.buf
) &&
5344 bcmp(chain
->bref
.check
.buf
, name
, name_len
) == 0) {