2 * Copyright (c) 2008 The DragonFly Project. All rights reserved.
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@backplane.com>
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * 3. Neither the name of The DragonFly Project nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific, prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * $DragonFly: src/sys/vfs/hammer/hammer_blockmap.c,v 1.27 2008/07/31 22:30:33 dillon Exp $
42 static int hammer_res_rb_compare(hammer_reserve_t res1
, hammer_reserve_t res2
);
43 static void hammer_reserve_setdelay_offset(hammer_mount_t hmp
,
44 hammer_off_t base_offset
, int zone
,
45 struct hammer_blockmap_layer2
*layer2
);
46 static void hammer_reserve_setdelay(hammer_mount_t hmp
, hammer_reserve_t resv
);
49 * Reserved big-blocks red-black tree support
51 RB_GENERATE2(hammer_res_rb_tree
, hammer_reserve
, rb_node
,
52 hammer_res_rb_compare
, hammer_off_t
, zone_offset
);
55 hammer_res_rb_compare(hammer_reserve_t res1
, hammer_reserve_t res2
)
57 if (res1
->zone_offset
< res2
->zone_offset
)
59 if (res1
->zone_offset
> res2
->zone_offset
)
65 * Allocate bytes from a zone
68 hammer_blockmap_alloc(hammer_transaction_t trans
, int zone
, int bytes
,
69 hammer_off_t hint
, int *errorp
)
72 hammer_volume_t root_volume
;
73 hammer_blockmap_t blockmap
;
74 hammer_blockmap_t freemap
;
75 hammer_reserve_t resv
;
76 struct hammer_blockmap_layer1
*layer1
;
77 struct hammer_blockmap_layer2
*layer2
;
78 hammer_buffer_t buffer1
= NULL
;
79 hammer_buffer_t buffer2
= NULL
;
80 hammer_buffer_t buffer3
= NULL
;
81 hammer_off_t tmp_offset
;
82 hammer_off_t next_offset
;
83 hammer_off_t result_offset
;
84 hammer_off_t layer1_offset
;
85 hammer_off_t layer2_offset
;
86 hammer_off_t base_off
;
88 int offset
; /* offset within big-block */
94 * Deal with alignment and buffer-boundary issues.
96 * Be careful, certain primary alignments are used below to allocate
97 * new blockmap blocks.
99 bytes
= (bytes
+ 15) & ~15;
100 KKASSERT(bytes
> 0 && bytes
<= HAMMER_XBUFSIZE
);
101 KKASSERT(zone
>= HAMMER_ZONE_BTREE_INDEX
&& zone
< HAMMER_MAX_ZONES
);
106 root_volume
= trans
->rootvol
;
108 blockmap
= &hmp
->blockmap
[zone
];
109 freemap
= &hmp
->blockmap
[HAMMER_ZONE_FREEMAP_INDEX
];
110 KKASSERT(HAMMER_ZONE_DECODE(blockmap
->next_offset
) == zone
);
113 * Use the hint if we have one.
115 if (hint
&& HAMMER_ZONE_DECODE(hint
) == zone
) {
116 next_offset
= (hint
+ 15) & ~(hammer_off_t
)15;
119 next_offset
= blockmap
->next_offset
;
125 * use_hint is turned off if we leave the hinted big-block.
127 if (use_hint
&& ((next_offset
^ hint
) & ~HAMMER_HINTBLOCK_MASK64
)) {
128 next_offset
= blockmap
->next_offset
;
135 if (next_offset
== HAMMER_ZONE_ENCODE(zone
+ 1, 0)) {
141 next_offset
= HAMMER_ZONE_ENCODE(zone
, 0);
145 * The allocation request may not cross a buffer boundary. Special
146 * large allocations must not cross a large-block boundary.
148 tmp_offset
= next_offset
+ bytes
- 1;
149 if (bytes
<= HAMMER_BUFSIZE
) {
150 if ((next_offset
^ tmp_offset
) & ~HAMMER_BUFMASK64
) {
151 next_offset
= tmp_offset
& ~HAMMER_BUFMASK64
;
155 if ((next_offset
^ tmp_offset
) & ~HAMMER_LARGEBLOCK_MASK64
) {
156 next_offset
= tmp_offset
& ~HAMMER_LARGEBLOCK_MASK64
;
160 offset
= (int)next_offset
& HAMMER_LARGEBLOCK_MASK
;
165 layer1_offset
= freemap
->phys_offset
+
166 HAMMER_BLOCKMAP_LAYER1_OFFSET(next_offset
);
169 * Skip this block if it is belonging to a volume that we are
170 * currently trying to remove from the file-system.
172 if ((int)HAMMER_VOL_DECODE(layer1_offset
) == hmp
->volume_to_remove
) {
173 next_offset
= (next_offset
+ HAMMER_BLOCKMAP_LAYER2
) &
174 ~HAMMER_BLOCKMAP_LAYER2_MASK
;
178 layer1
= hammer_bread(hmp
, layer1_offset
, errorp
, &buffer1
);
187 if (layer1
->layer1_crc
!= crc32(layer1
, HAMMER_LAYER1_CRCSIZE
)) {
188 hammer_lock_ex(&hmp
->blkmap_lock
);
189 if (layer1
->layer1_crc
!= crc32(layer1
, HAMMER_LAYER1_CRCSIZE
))
190 panic("CRC FAILED: LAYER1");
191 hammer_unlock(&hmp
->blkmap_lock
);
195 * If we are at a big-block boundary and layer1 indicates no
196 * free big-blocks, then we cannot allocate a new bigblock in
197 * layer2, skip to the next layer1 entry.
199 if (offset
== 0 && layer1
->blocks_free
== 0) {
200 next_offset
= (next_offset
+ HAMMER_BLOCKMAP_LAYER2
) &
201 ~HAMMER_BLOCKMAP_LAYER2_MASK
;
204 KKASSERT(layer1
->phys_offset
!= HAMMER_BLOCKMAP_UNAVAIL
);
207 * Dive layer 2, each entry represents a large-block.
209 layer2_offset
= layer1
->phys_offset
+
210 HAMMER_BLOCKMAP_LAYER2_OFFSET(next_offset
);
211 layer2
= hammer_bread(hmp
, layer2_offset
, errorp
, &buffer2
);
218 * Check CRC. This can race another thread holding the lock
219 * and in the middle of modifying layer2.
221 if (layer2
->entry_crc
!= crc32(layer2
, HAMMER_LAYER2_CRCSIZE
)) {
222 hammer_lock_ex(&hmp
->blkmap_lock
);
223 if (layer2
->entry_crc
!= crc32(layer2
, HAMMER_LAYER2_CRCSIZE
))
224 panic("CRC FAILED: LAYER2");
225 hammer_unlock(&hmp
->blkmap_lock
);
229 * Skip the layer if the zone is owned by someone other then us.
231 if (layer2
->zone
&& layer2
->zone
!= zone
) {
232 next_offset
+= (HAMMER_LARGEBLOCK_SIZE
- offset
);
235 if (offset
< layer2
->append_off
) {
236 next_offset
+= layer2
->append_off
- offset
;
241 * If operating in the current non-hint blockmap block, do not
242 * allow it to get over-full. Also drop any active hinting so
243 * blockmap->next_offset is updated at the end.
245 * We do this for B-Tree and meta-data allocations to provide
246 * localization for updates.
248 if ((zone
== HAMMER_ZONE_BTREE_INDEX
||
249 zone
== HAMMER_ZONE_META_INDEX
) &&
250 offset
>= HAMMER_LARGEBLOCK_OVERFILL
&&
251 !((next_offset
^ blockmap
->next_offset
) & ~HAMMER_LARGEBLOCK_MASK64
)
253 if (offset
>= HAMMER_LARGEBLOCK_OVERFILL
) {
254 next_offset
+= (HAMMER_LARGEBLOCK_SIZE
- offset
);
261 * We need the lock from this point on. We have to re-check zone
262 * ownership after acquiring the lock and also check for reservations.
264 hammer_lock_ex(&hmp
->blkmap_lock
);
266 if (layer2
->zone
&& layer2
->zone
!= zone
) {
267 hammer_unlock(&hmp
->blkmap_lock
);
268 next_offset
+= (HAMMER_LARGEBLOCK_SIZE
- offset
);
271 if (offset
< layer2
->append_off
) {
272 hammer_unlock(&hmp
->blkmap_lock
);
273 next_offset
+= layer2
->append_off
- offset
;
278 * The bigblock might be reserved by another zone. If it is reserved
279 * by our zone we may have to move next_offset past the append_off.
281 base_off
= (next_offset
&
282 (~HAMMER_LARGEBLOCK_MASK64
& ~HAMMER_OFF_ZONE_MASK
)) |
283 HAMMER_ZONE_RAW_BUFFER
;
284 resv
= RB_LOOKUP(hammer_res_rb_tree
, &hmp
->rb_resv_root
, base_off
);
286 if (resv
->zone
!= zone
) {
287 hammer_unlock(&hmp
->blkmap_lock
);
288 next_offset
= (next_offset
+ HAMMER_LARGEBLOCK_SIZE
) &
289 ~HAMMER_LARGEBLOCK_MASK64
;
292 if (offset
< resv
->append_off
) {
293 hammer_unlock(&hmp
->blkmap_lock
);
294 next_offset
+= resv
->append_off
- offset
;
301 * Ok, we can allocate out of this layer2 big-block. Assume ownership
302 * of the layer for real. At this point we've validated any
303 * reservation that might exist and can just ignore resv.
305 if (layer2
->zone
== 0) {
307 * Assign the bigblock to our zone
309 hammer_modify_buffer(trans
, buffer1
,
310 layer1
, sizeof(*layer1
));
311 --layer1
->blocks_free
;
312 layer1
->layer1_crc
= crc32(layer1
,
313 HAMMER_LAYER1_CRCSIZE
);
314 hammer_modify_buffer_done(buffer1
);
315 hammer_modify_buffer(trans
, buffer2
,
316 layer2
, sizeof(*layer2
));
318 KKASSERT(layer2
->bytes_free
== HAMMER_LARGEBLOCK_SIZE
);
319 KKASSERT(layer2
->append_off
== 0);
320 hammer_modify_volume_field(trans
, trans
->rootvol
,
321 vol0_stat_freebigblocks
);
322 --root_volume
->ondisk
->vol0_stat_freebigblocks
;
323 hmp
->copy_stat_freebigblocks
=
324 root_volume
->ondisk
->vol0_stat_freebigblocks
;
325 hammer_modify_volume_done(trans
->rootvol
);
327 hammer_modify_buffer(trans
, buffer2
,
328 layer2
, sizeof(*layer2
));
330 KKASSERT(layer2
->zone
== zone
);
332 layer2
->bytes_free
-= bytes
;
333 KKASSERT(layer2
->append_off
<= offset
);
334 layer2
->append_off
= offset
+ bytes
;
335 layer2
->entry_crc
= crc32(layer2
, HAMMER_LAYER2_CRCSIZE
);
336 hammer_modify_buffer_done(buffer2
);
337 KKASSERT(layer2
->bytes_free
>= 0);
340 * We hold the blockmap lock and should be the only ones
341 * capable of modifying resv->append_off. Track the allocation
344 KKASSERT(bytes
!= 0);
346 KKASSERT(resv
->append_off
<= offset
);
347 resv
->append_off
= offset
+ bytes
;
348 resv
->flags
&= ~HAMMER_RESF_LAYER2FREE
;
349 hammer_blockmap_reserve_complete(hmp
, resv
);
353 * If we are allocating from the base of a new buffer we can avoid
354 * a disk read by calling hammer_bnew().
356 if ((next_offset
& HAMMER_BUFMASK
) == 0) {
357 hammer_bnew_ext(trans
->hmp
, next_offset
, bytes
,
360 result_offset
= next_offset
;
363 * If we weren't supplied with a hint or could not use the hint
364 * then we wound up using blockmap->next_offset as the hint and
368 hammer_modify_volume(NULL
, root_volume
, NULL
, 0);
369 blockmap
->next_offset
= next_offset
+ bytes
;
370 hammer_modify_volume_done(root_volume
);
372 hammer_unlock(&hmp
->blkmap_lock
);
379 hammer_rel_buffer(buffer1
, 0);
381 hammer_rel_buffer(buffer2
, 0);
383 hammer_rel_buffer(buffer3
, 0);
385 return(result_offset
);
389 * Frontend function - Reserve bytes in a zone.
391 * This code reserves bytes out of a blockmap without committing to any
392 * meta-data modifications, allowing the front-end to directly issue disk
393 * write I/O for large blocks of data
395 * The backend later finalizes the reservation with hammer_blockmap_finalize()
396 * upon committing the related record.
399 hammer_blockmap_reserve(hammer_mount_t hmp
, int zone
, int bytes
,
400 hammer_off_t
*zone_offp
, int *errorp
)
402 hammer_volume_t root_volume
;
403 hammer_blockmap_t blockmap
;
404 hammer_blockmap_t freemap
;
405 struct hammer_blockmap_layer1
*layer1
;
406 struct hammer_blockmap_layer2
*layer2
;
407 hammer_buffer_t buffer1
= NULL
;
408 hammer_buffer_t buffer2
= NULL
;
409 hammer_buffer_t buffer3
= NULL
;
410 hammer_off_t tmp_offset
;
411 hammer_off_t next_offset
;
412 hammer_off_t layer1_offset
;
413 hammer_off_t layer2_offset
;
414 hammer_off_t base_off
;
415 hammer_reserve_t resv
;
416 hammer_reserve_t resx
;
423 KKASSERT(zone
>= HAMMER_ZONE_BTREE_INDEX
&& zone
< HAMMER_MAX_ZONES
);
424 root_volume
= hammer_get_root_volume(hmp
, errorp
);
427 blockmap
= &hmp
->blockmap
[zone
];
428 freemap
= &hmp
->blockmap
[HAMMER_ZONE_FREEMAP_INDEX
];
429 KKASSERT(HAMMER_ZONE_DECODE(blockmap
->next_offset
) == zone
);
432 * Deal with alignment and buffer-boundary issues.
434 * Be careful, certain primary alignments are used below to allocate
435 * new blockmap blocks.
437 bytes
= (bytes
+ 15) & ~15;
438 KKASSERT(bytes
> 0 && bytes
<= HAMMER_XBUFSIZE
);
440 next_offset
= blockmap
->next_offset
;
446 if (next_offset
== HAMMER_ZONE_ENCODE(zone
+ 1, 0)) {
451 next_offset
= HAMMER_ZONE_ENCODE(zone
, 0);
455 * The allocation request may not cross a buffer boundary. Special
456 * large allocations must not cross a large-block boundary.
458 tmp_offset
= next_offset
+ bytes
- 1;
459 if (bytes
<= HAMMER_BUFSIZE
) {
460 if ((next_offset
^ tmp_offset
) & ~HAMMER_BUFMASK64
) {
461 next_offset
= tmp_offset
& ~HAMMER_BUFMASK64
;
465 if ((next_offset
^ tmp_offset
) & ~HAMMER_LARGEBLOCK_MASK64
) {
466 next_offset
= tmp_offset
& ~HAMMER_LARGEBLOCK_MASK64
;
470 offset
= (int)next_offset
& HAMMER_LARGEBLOCK_MASK
;
475 layer1_offset
= freemap
->phys_offset
+
476 HAMMER_BLOCKMAP_LAYER1_OFFSET(next_offset
);
477 layer1
= hammer_bread(hmp
, layer1_offset
, errorp
, &buffer1
);
484 if (layer1
->layer1_crc
!= crc32(layer1
, HAMMER_LAYER1_CRCSIZE
)) {
485 hammer_lock_ex(&hmp
->blkmap_lock
);
486 if (layer1
->layer1_crc
!= crc32(layer1
, HAMMER_LAYER1_CRCSIZE
))
487 panic("CRC FAILED: LAYER1");
488 hammer_unlock(&hmp
->blkmap_lock
);
492 * If we are at a big-block boundary and layer1 indicates no
493 * free big-blocks, then we cannot allocate a new bigblock in
494 * layer2, skip to the next layer1 entry.
496 if ((next_offset
& HAMMER_LARGEBLOCK_MASK
) == 0 &&
497 layer1
->blocks_free
== 0) {
498 next_offset
= (next_offset
+ HAMMER_BLOCKMAP_LAYER2
) &
499 ~HAMMER_BLOCKMAP_LAYER2_MASK
;
502 KKASSERT(layer1
->phys_offset
!= HAMMER_BLOCKMAP_UNAVAIL
);
505 * Dive layer 2, each entry represents a large-block.
507 layer2_offset
= layer1
->phys_offset
+
508 HAMMER_BLOCKMAP_LAYER2_OFFSET(next_offset
);
509 layer2
= hammer_bread(hmp
, layer2_offset
, errorp
, &buffer2
);
514 * Check CRC if not allocating into uninitialized space (which we
515 * aren't when reserving space).
517 if (layer2
->entry_crc
!= crc32(layer2
, HAMMER_LAYER2_CRCSIZE
)) {
518 hammer_lock_ex(&hmp
->blkmap_lock
);
519 if (layer2
->entry_crc
!= crc32(layer2
, HAMMER_LAYER2_CRCSIZE
))
520 panic("CRC FAILED: LAYER2");
521 hammer_unlock(&hmp
->blkmap_lock
);
525 * Skip the layer if the zone is owned by someone other then us.
527 if (layer2
->zone
&& layer2
->zone
!= zone
) {
528 next_offset
+= (HAMMER_LARGEBLOCK_SIZE
- offset
);
531 if (offset
< layer2
->append_off
) {
532 next_offset
+= layer2
->append_off
- offset
;
537 * We need the lock from this point on. We have to re-check zone
538 * ownership after acquiring the lock and also check for reservations.
540 hammer_lock_ex(&hmp
->blkmap_lock
);
542 if (layer2
->zone
&& layer2
->zone
!= zone
) {
543 hammer_unlock(&hmp
->blkmap_lock
);
544 next_offset
+= (HAMMER_LARGEBLOCK_SIZE
- offset
);
547 if (offset
< layer2
->append_off
) {
548 hammer_unlock(&hmp
->blkmap_lock
);
549 next_offset
+= layer2
->append_off
- offset
;
554 * The bigblock might be reserved by another zone. If it is reserved
555 * by our zone we may have to move next_offset past the append_off.
557 base_off
= (next_offset
&
558 (~HAMMER_LARGEBLOCK_MASK64
& ~HAMMER_OFF_ZONE_MASK
)) |
559 HAMMER_ZONE_RAW_BUFFER
;
560 resv
= RB_LOOKUP(hammer_res_rb_tree
, &hmp
->rb_resv_root
, base_off
);
562 if (resv
->zone
!= zone
) {
563 hammer_unlock(&hmp
->blkmap_lock
);
564 next_offset
= (next_offset
+ HAMMER_LARGEBLOCK_SIZE
) &
565 ~HAMMER_LARGEBLOCK_MASK64
;
568 if (offset
< resv
->append_off
) {
569 hammer_unlock(&hmp
->blkmap_lock
);
570 next_offset
+= resv
->append_off
- offset
;
576 resx
= kmalloc(sizeof(*resv
), hmp
->m_misc
,
577 M_WAITOK
| M_ZERO
| M_USE_RESERVE
);
580 resx
->zone_offset
= base_off
;
581 if (layer2
->bytes_free
== HAMMER_LARGEBLOCK_SIZE
)
582 resx
->flags
|= HAMMER_RESF_LAYER2FREE
;
583 resv
= RB_INSERT(hammer_res_rb_tree
, &hmp
->rb_resv_root
, resx
);
584 KKASSERT(resv
== NULL
);
586 ++hammer_count_reservations
;
588 resv
->append_off
= offset
+ bytes
;
591 * If we are not reserving a whole buffer but are at the start of
592 * a new block, call hammer_bnew() to avoid a disk read.
594 * If we are reserving a whole buffer (or more), the caller will
595 * probably use a direct read, so do nothing.
597 if (bytes
< HAMMER_BUFSIZE
&& (next_offset
& HAMMER_BUFMASK
) == 0) {
598 hammer_bnew(hmp
, next_offset
, errorp
, &buffer3
);
602 * Adjust our iterator and alloc_offset. The layer1 and layer2
603 * space beyond alloc_offset is uninitialized. alloc_offset must
604 * be big-block aligned.
606 blockmap
->next_offset
= next_offset
+ bytes
;
607 hammer_unlock(&hmp
->blkmap_lock
);
611 hammer_rel_buffer(buffer1
, 0);
613 hammer_rel_buffer(buffer2
, 0);
615 hammer_rel_buffer(buffer3
, 0);
616 hammer_rel_volume(root_volume
, 0);
617 *zone_offp
= next_offset
;
623 * Dereference a reservation structure. Upon the final release the
624 * underlying big-block is checked and if it is entirely free we delete
625 * any related HAMMER buffers to avoid potential conflicts with future
626 * reuse of the big-block.
629 hammer_blockmap_reserve_complete(hammer_mount_t hmp
, hammer_reserve_t resv
)
631 hammer_off_t base_offset
;
634 KKASSERT(resv
->refs
> 0);
635 KKASSERT((resv
->zone_offset
& HAMMER_OFF_ZONE_MASK
) ==
636 HAMMER_ZONE_RAW_BUFFER
);
639 * Setting append_off to the max prevents any new allocations
640 * from occuring while we are trying to dispose of the reservation,
641 * allowing us to safely delete any related HAMMER buffers.
643 * If we are unable to clean out all related HAMMER buffers we
646 if (resv
->refs
== 1 && (resv
->flags
& HAMMER_RESF_LAYER2FREE
)) {
647 resv
->append_off
= HAMMER_LARGEBLOCK_SIZE
;
648 base_offset
= resv
->zone_offset
& ~HAMMER_OFF_ZONE_MASK
;
649 base_offset
= HAMMER_ZONE_ENCODE(resv
->zone
, base_offset
);
650 error
= hammer_del_buffers(hmp
, base_offset
,
652 HAMMER_LARGEBLOCK_SIZE
,
655 hammer_reserve_setdelay(hmp
, resv
);
657 if (--resv
->refs
== 0) {
658 KKASSERT((resv
->flags
& HAMMER_RESF_ONDELAY
) == 0);
659 RB_REMOVE(hammer_res_rb_tree
, &hmp
->rb_resv_root
, resv
);
660 kfree(resv
, hmp
->m_misc
);
661 --hammer_count_reservations
;
666 * Prevent a potentially free big-block from being reused until after
667 * the related flushes have completely cycled, otherwise crash recovery
668 * could resurrect a data block that was already reused and overwritten.
670 * The caller might reset the underlying layer2 entry's append_off to 0, so
671 * our covering append_off must be set to max to prevent any reallocation
672 * until after the flush delays complete, not to mention proper invalidation
673 * of any underlying cached blocks.
676 hammer_reserve_setdelay_offset(hammer_mount_t hmp
, hammer_off_t base_offset
,
677 int zone
, struct hammer_blockmap_layer2
*layer2
)
679 hammer_reserve_t resv
;
682 * Allocate the reservation if necessary.
684 * NOTE: need lock in future around resv lookup/allocation and
685 * the setdelay call, currently refs is not bumped until the call.
688 resv
= RB_LOOKUP(hammer_res_rb_tree
, &hmp
->rb_resv_root
, base_offset
);
690 resv
= kmalloc(sizeof(*resv
), hmp
->m_misc
,
691 M_WAITOK
| M_ZERO
| M_USE_RESERVE
);
693 resv
->zone_offset
= base_offset
;
695 resv
->append_off
= HAMMER_LARGEBLOCK_SIZE
;
697 if (layer2
->bytes_free
== HAMMER_LARGEBLOCK_SIZE
)
698 resv
->flags
|= HAMMER_RESF_LAYER2FREE
;
699 if (RB_INSERT(hammer_res_rb_tree
, &hmp
->rb_resv_root
, resv
)) {
700 kfree(resv
, hmp
->m_misc
);
703 ++hammer_count_reservations
;
705 if (layer2
->bytes_free
== HAMMER_LARGEBLOCK_SIZE
)
706 resv
->flags
|= HAMMER_RESF_LAYER2FREE
;
708 hammer_reserve_setdelay(hmp
, resv
);
712 * Enter the reservation on the on-delay list, or move it if it
713 * is already on the list.
716 hammer_reserve_setdelay(hammer_mount_t hmp
, hammer_reserve_t resv
)
718 if (resv
->flags
& HAMMER_RESF_ONDELAY
) {
719 TAILQ_REMOVE(&hmp
->delay_list
, resv
, delay_entry
);
720 resv
->flush_group
= hmp
->flusher
.next
+ 1;
721 TAILQ_INSERT_TAIL(&hmp
->delay_list
, resv
, delay_entry
);
724 ++hmp
->rsv_fromdelay
;
725 resv
->flags
|= HAMMER_RESF_ONDELAY
;
726 resv
->flush_group
= hmp
->flusher
.next
+ 1;
727 TAILQ_INSERT_TAIL(&hmp
->delay_list
, resv
, delay_entry
);
732 hammer_reserve_clrdelay(hammer_mount_t hmp
, hammer_reserve_t resv
)
734 KKASSERT(resv
->flags
& HAMMER_RESF_ONDELAY
);
735 resv
->flags
&= ~HAMMER_RESF_ONDELAY
;
736 TAILQ_REMOVE(&hmp
->delay_list
, resv
, delay_entry
);
737 --hmp
->rsv_fromdelay
;
738 hammer_blockmap_reserve_complete(hmp
, resv
);
742 * Backend function - free (offset, bytes) in a zone.
747 hammer_blockmap_free(hammer_transaction_t trans
,
748 hammer_off_t zone_offset
, int bytes
)
751 hammer_volume_t root_volume
;
752 hammer_blockmap_t blockmap
;
753 hammer_blockmap_t freemap
;
754 struct hammer_blockmap_layer1
*layer1
;
755 struct hammer_blockmap_layer2
*layer2
;
756 hammer_buffer_t buffer1
= NULL
;
757 hammer_buffer_t buffer2
= NULL
;
758 hammer_off_t layer1_offset
;
759 hammer_off_t layer2_offset
;
760 hammer_off_t base_off
;
771 bytes
= (bytes
+ 15) & ~15;
772 KKASSERT(bytes
<= HAMMER_XBUFSIZE
);
773 KKASSERT(((zone_offset
^ (zone_offset
+ (bytes
- 1))) &
774 ~HAMMER_LARGEBLOCK_MASK64
) == 0);
777 * Basic zone validation & locking
779 zone
= HAMMER_ZONE_DECODE(zone_offset
);
780 KKASSERT(zone
>= HAMMER_ZONE_BTREE_INDEX
&& zone
< HAMMER_MAX_ZONES
);
781 root_volume
= trans
->rootvol
;
784 blockmap
= &hmp
->blockmap
[zone
];
785 freemap
= &hmp
->blockmap
[HAMMER_ZONE_FREEMAP_INDEX
];
790 layer1_offset
= freemap
->phys_offset
+
791 HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset
);
792 layer1
= hammer_bread(hmp
, layer1_offset
, &error
, &buffer1
);
795 KKASSERT(layer1
->phys_offset
&&
796 layer1
->phys_offset
!= HAMMER_BLOCKMAP_UNAVAIL
);
797 if (layer1
->layer1_crc
!= crc32(layer1
, HAMMER_LAYER1_CRCSIZE
)) {
798 hammer_lock_ex(&hmp
->blkmap_lock
);
799 if (layer1
->layer1_crc
!= crc32(layer1
, HAMMER_LAYER1_CRCSIZE
))
800 panic("CRC FAILED: LAYER1");
801 hammer_unlock(&hmp
->blkmap_lock
);
805 * Dive layer 2, each entry represents a large-block.
807 layer2_offset
= layer1
->phys_offset
+
808 HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset
);
809 layer2
= hammer_bread(hmp
, layer2_offset
, &error
, &buffer2
);
812 if (layer2
->entry_crc
!= crc32(layer2
, HAMMER_LAYER2_CRCSIZE
)) {
813 hammer_lock_ex(&hmp
->blkmap_lock
);
814 if (layer2
->entry_crc
!= crc32(layer2
, HAMMER_LAYER2_CRCSIZE
))
815 panic("CRC FAILED: LAYER2");
816 hammer_unlock(&hmp
->blkmap_lock
);
819 hammer_lock_ex(&hmp
->blkmap_lock
);
821 hammer_modify_buffer(trans
, buffer2
, layer2
, sizeof(*layer2
));
824 * Free space previously allocated via blockmap_alloc().
826 KKASSERT(layer2
->zone
== zone
);
827 layer2
->bytes_free
+= bytes
;
828 KKASSERT(layer2
->bytes_free
<= HAMMER_LARGEBLOCK_SIZE
);
831 * If a big-block becomes entirely free we must create a covering
832 * reservation to prevent premature reuse. Note, however, that
833 * the big-block and/or reservation may still have an append_off
834 * that allows further (non-reused) allocations.
836 * Once the reservation has been made we re-check layer2 and if
837 * the big-block is still entirely free we reset the layer2 entry.
838 * The reservation will prevent premature reuse.
840 * NOTE: hammer_buffer's are only invalidated when the reservation
841 * is completed, if the layer2 entry is still completely free at
842 * that time. Any allocations from the reservation that may have
843 * occured in the mean time, or active references on the reservation
844 * from new pending allocations, will prevent the invalidation from
847 if (layer2
->bytes_free
== HAMMER_LARGEBLOCK_SIZE
) {
848 base_off
= (zone_offset
& (~HAMMER_LARGEBLOCK_MASK64
& ~HAMMER_OFF_ZONE_MASK
)) | HAMMER_ZONE_RAW_BUFFER
;
850 hammer_reserve_setdelay_offset(hmp
, base_off
, zone
, layer2
);
851 if (layer2
->bytes_free
== HAMMER_LARGEBLOCK_SIZE
) {
853 layer2
->append_off
= 0;
854 hammer_modify_buffer(trans
, buffer1
,
855 layer1
, sizeof(*layer1
));
856 ++layer1
->blocks_free
;
857 layer1
->layer1_crc
= crc32(layer1
,
858 HAMMER_LAYER1_CRCSIZE
);
859 hammer_modify_buffer_done(buffer1
);
860 hammer_modify_volume_field(trans
,
862 vol0_stat_freebigblocks
);
863 ++root_volume
->ondisk
->vol0_stat_freebigblocks
;
864 hmp
->copy_stat_freebigblocks
=
865 root_volume
->ondisk
->vol0_stat_freebigblocks
;
866 hammer_modify_volume_done(trans
->rootvol
);
869 layer2
->entry_crc
= crc32(layer2
, HAMMER_LAYER2_CRCSIZE
);
870 hammer_modify_buffer_done(buffer2
);
871 hammer_unlock(&hmp
->blkmap_lock
);
875 hammer_rel_buffer(buffer1
, 0);
877 hammer_rel_buffer(buffer2
, 0);
881 * Backend function - finalize (offset, bytes) in a zone.
883 * Allocate space that was previously reserved by the frontend.
886 hammer_blockmap_finalize(hammer_transaction_t trans
,
887 hammer_reserve_t resv
,
888 hammer_off_t zone_offset
, int bytes
)
891 hammer_volume_t root_volume
;
892 hammer_blockmap_t blockmap
;
893 hammer_blockmap_t freemap
;
894 struct hammer_blockmap_layer1
*layer1
;
895 struct hammer_blockmap_layer2
*layer2
;
896 hammer_buffer_t buffer1
= NULL
;
897 hammer_buffer_t buffer2
= NULL
;
898 hammer_off_t layer1_offset
;
899 hammer_off_t layer2_offset
;
911 bytes
= (bytes
+ 15) & ~15;
912 KKASSERT(bytes
<= HAMMER_XBUFSIZE
);
915 * Basic zone validation & locking
917 zone
= HAMMER_ZONE_DECODE(zone_offset
);
918 KKASSERT(zone
>= HAMMER_ZONE_BTREE_INDEX
&& zone
< HAMMER_MAX_ZONES
);
919 root_volume
= trans
->rootvol
;
922 blockmap
= &hmp
->blockmap
[zone
];
923 freemap
= &hmp
->blockmap
[HAMMER_ZONE_FREEMAP_INDEX
];
928 layer1_offset
= freemap
->phys_offset
+
929 HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset
);
930 layer1
= hammer_bread(hmp
, layer1_offset
, &error
, &buffer1
);
933 KKASSERT(layer1
->phys_offset
&&
934 layer1
->phys_offset
!= HAMMER_BLOCKMAP_UNAVAIL
);
935 if (layer1
->layer1_crc
!= crc32(layer1
, HAMMER_LAYER1_CRCSIZE
)) {
936 hammer_lock_ex(&hmp
->blkmap_lock
);
937 if (layer1
->layer1_crc
!= crc32(layer1
, HAMMER_LAYER1_CRCSIZE
))
938 panic("CRC FAILED: LAYER1");
939 hammer_unlock(&hmp
->blkmap_lock
);
943 * Dive layer 2, each entry represents a large-block.
945 layer2_offset
= layer1
->phys_offset
+
946 HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset
);
947 layer2
= hammer_bread(hmp
, layer2_offset
, &error
, &buffer2
);
950 if (layer2
->entry_crc
!= crc32(layer2
, HAMMER_LAYER2_CRCSIZE
)) {
951 hammer_lock_ex(&hmp
->blkmap_lock
);
952 if (layer2
->entry_crc
!= crc32(layer2
, HAMMER_LAYER2_CRCSIZE
))
953 panic("CRC FAILED: LAYER2");
954 hammer_unlock(&hmp
->blkmap_lock
);
957 hammer_lock_ex(&hmp
->blkmap_lock
);
959 hammer_modify_buffer(trans
, buffer2
, layer2
, sizeof(*layer2
));
962 * Finalize some or all of the space covered by a current
963 * reservation. An allocation in the same layer may have
964 * already assigned ownership.
966 if (layer2
->zone
== 0) {
967 hammer_modify_buffer(trans
, buffer1
,
968 layer1
, sizeof(*layer1
));
969 --layer1
->blocks_free
;
970 layer1
->layer1_crc
= crc32(layer1
,
971 HAMMER_LAYER1_CRCSIZE
);
972 hammer_modify_buffer_done(buffer1
);
974 KKASSERT(layer2
->bytes_free
== HAMMER_LARGEBLOCK_SIZE
);
975 KKASSERT(layer2
->append_off
== 0);
976 hammer_modify_volume_field(trans
,
978 vol0_stat_freebigblocks
);
979 --root_volume
->ondisk
->vol0_stat_freebigblocks
;
980 hmp
->copy_stat_freebigblocks
=
981 root_volume
->ondisk
->vol0_stat_freebigblocks
;
982 hammer_modify_volume_done(trans
->rootvol
);
984 if (layer2
->zone
!= zone
)
985 kprintf("layer2 zone mismatch %d %d\n", layer2
->zone
, zone
);
986 KKASSERT(layer2
->zone
== zone
);
987 KKASSERT(bytes
!= 0);
988 layer2
->bytes_free
-= bytes
;
990 resv
->flags
&= ~HAMMER_RESF_LAYER2FREE
;
993 * Finalizations can occur out of order, or combined with allocations.
994 * append_off must be set to the highest allocated offset.
996 offset
= ((int)zone_offset
& HAMMER_LARGEBLOCK_MASK
) + bytes
;
997 if (layer2
->append_off
< offset
)
998 layer2
->append_off
= offset
;
1000 layer2
->entry_crc
= crc32(layer2
, HAMMER_LAYER2_CRCSIZE
);
1001 hammer_modify_buffer_done(buffer2
);
1002 hammer_unlock(&hmp
->blkmap_lock
);
1006 hammer_rel_buffer(buffer1
, 0);
1008 hammer_rel_buffer(buffer2
, 0);
1013 * Return the number of free bytes in the big-block containing the
1014 * specified blockmap offset.
1017 hammer_blockmap_getfree(hammer_mount_t hmp
, hammer_off_t zone_offset
,
1018 int *curp
, int *errorp
)
1020 hammer_volume_t root_volume
;
1021 hammer_blockmap_t blockmap
;
1022 hammer_blockmap_t freemap
;
1023 struct hammer_blockmap_layer1
*layer1
;
1024 struct hammer_blockmap_layer2
*layer2
;
1025 hammer_buffer_t buffer
= NULL
;
1026 hammer_off_t layer1_offset
;
1027 hammer_off_t layer2_offset
;
1031 zone
= HAMMER_ZONE_DECODE(zone_offset
);
1032 KKASSERT(zone
>= HAMMER_ZONE_BTREE_INDEX
&& zone
< HAMMER_MAX_ZONES
);
1033 root_volume
= hammer_get_root_volume(hmp
, errorp
);
1038 blockmap
= &hmp
->blockmap
[zone
];
1039 freemap
= &hmp
->blockmap
[HAMMER_ZONE_FREEMAP_INDEX
];
1044 layer1_offset
= freemap
->phys_offset
+
1045 HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset
);
1046 layer1
= hammer_bread(hmp
, layer1_offset
, errorp
, &buffer
);
1051 KKASSERT(layer1
->phys_offset
);
1052 if (layer1
->layer1_crc
!= crc32(layer1
, HAMMER_LAYER1_CRCSIZE
)) {
1053 hammer_lock_ex(&hmp
->blkmap_lock
);
1054 if (layer1
->layer1_crc
!= crc32(layer1
, HAMMER_LAYER1_CRCSIZE
))
1055 panic("CRC FAILED: LAYER1");
1056 hammer_unlock(&hmp
->blkmap_lock
);
1060 * Dive layer 2, each entry represents a large-block.
1062 * (reuse buffer, layer1 pointer becomes invalid)
1064 layer2_offset
= layer1
->phys_offset
+
1065 HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset
);
1066 layer2
= hammer_bread(hmp
, layer2_offset
, errorp
, &buffer
);
1071 if (layer2
->entry_crc
!= crc32(layer2
, HAMMER_LAYER2_CRCSIZE
)) {
1072 hammer_lock_ex(&hmp
->blkmap_lock
);
1073 if (layer2
->entry_crc
!= crc32(layer2
, HAMMER_LAYER2_CRCSIZE
))
1074 panic("CRC FAILED: LAYER2");
1075 hammer_unlock(&hmp
->blkmap_lock
);
1077 KKASSERT(layer2
->zone
== zone
);
1079 bytes
= layer2
->bytes_free
;
1081 if ((blockmap
->next_offset
^ zone_offset
) & ~HAMMER_LARGEBLOCK_MASK64
)
1087 hammer_rel_buffer(buffer
, 0);
1088 hammer_rel_volume(root_volume
, 0);
1089 if (hammer_debug_general
& 0x0800) {
1090 kprintf("hammer_blockmap_getfree: %016llx -> %d\n",
1091 (long long)zone_offset
, bytes
);
1098 * Lookup a blockmap offset.
1101 hammer_blockmap_lookup(hammer_mount_t hmp
, hammer_off_t zone_offset
,
1104 hammer_volume_t root_volume
;
1105 hammer_blockmap_t freemap
;
1106 struct hammer_blockmap_layer1
*layer1
;
1107 struct hammer_blockmap_layer2
*layer2
;
1108 hammer_buffer_t buffer
= NULL
;
1109 hammer_off_t layer1_offset
;
1110 hammer_off_t layer2_offset
;
1111 hammer_off_t result_offset
;
1112 hammer_off_t base_off
;
1113 hammer_reserve_t resv
;
1117 * Calculate the zone-2 offset.
1119 zone
= HAMMER_ZONE_DECODE(zone_offset
);
1120 KKASSERT(zone
>= HAMMER_ZONE_BTREE_INDEX
&& zone
< HAMMER_MAX_ZONES
);
1122 result_offset
= (zone_offset
& ~HAMMER_OFF_ZONE_MASK
) |
1123 HAMMER_ZONE_RAW_BUFFER
;
1126 * We can actually stop here, normal blockmaps are now direct-mapped
1127 * onto the freemap and so represent zone-2 addresses.
1129 if (hammer_verify_zone
== 0) {
1131 return(result_offset
);
1135 * Validate the allocation zone
1137 root_volume
= hammer_get_root_volume(hmp
, errorp
);
1140 freemap
= &hmp
->blockmap
[HAMMER_ZONE_FREEMAP_INDEX
];
1141 KKASSERT(freemap
->phys_offset
!= 0);
1146 layer1_offset
= freemap
->phys_offset
+
1147 HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset
);
1148 layer1
= hammer_bread(hmp
, layer1_offset
, errorp
, &buffer
);
1151 KKASSERT(layer1
->phys_offset
!= HAMMER_BLOCKMAP_UNAVAIL
);
1152 if (layer1
->layer1_crc
!= crc32(layer1
, HAMMER_LAYER1_CRCSIZE
)) {
1153 hammer_lock_ex(&hmp
->blkmap_lock
);
1154 if (layer1
->layer1_crc
!= crc32(layer1
, HAMMER_LAYER1_CRCSIZE
))
1155 panic("CRC FAILED: LAYER1");
1156 hammer_unlock(&hmp
->blkmap_lock
);
1160 * Dive layer 2, each entry represents a large-block.
1162 layer2_offset
= layer1
->phys_offset
+
1163 HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset
);
1164 layer2
= hammer_bread(hmp
, layer2_offset
, errorp
, &buffer
);
1168 if (layer2
->zone
== 0) {
1169 base_off
= (zone_offset
& (~HAMMER_LARGEBLOCK_MASK64
& ~HAMMER_OFF_ZONE_MASK
)) | HAMMER_ZONE_RAW_BUFFER
;
1170 resv
= RB_LOOKUP(hammer_res_rb_tree
, &hmp
->rb_resv_root
,
1172 KKASSERT(resv
&& resv
->zone
== zone
);
1174 } else if (layer2
->zone
!= zone
) {
1175 panic("hammer_blockmap_lookup: bad zone %d/%d\n",
1176 layer2
->zone
, zone
);
1178 if (layer2
->entry_crc
!= crc32(layer2
, HAMMER_LAYER2_CRCSIZE
)) {
1179 hammer_lock_ex(&hmp
->blkmap_lock
);
1180 if (layer2
->entry_crc
!= crc32(layer2
, HAMMER_LAYER2_CRCSIZE
))
1181 panic("CRC FAILED: LAYER2");
1182 hammer_unlock(&hmp
->blkmap_lock
);
1187 hammer_rel_buffer(buffer
, 0);
1188 hammer_rel_volume(root_volume
, 0);
1189 if (hammer_debug_general
& 0x0800) {
1190 kprintf("hammer_blockmap_lookup: %016llx -> %016llx\n",
1191 (long long)zone_offset
, (long long)result_offset
);
1193 return(result_offset
);
1198 * Check space availability
1201 _hammer_checkspace(hammer_mount_t hmp
, int slop
, int64_t *resp
)
1203 const int in_size
= sizeof(struct hammer_inode_data
) +
1204 sizeof(union hammer_btree_elm
);
1205 const int rec_size
= (sizeof(union hammer_btree_elm
) * 2);
1208 usedbytes
= hmp
->rsv_inodes
* in_size
+
1209 hmp
->rsv_recs
* rec_size
+
1210 hmp
->rsv_databytes
+
1211 ((int64_t)hmp
->rsv_fromdelay
<< HAMMER_LARGEBLOCK_BITS
) +
1212 ((int64_t)hidirtybufspace
<< 2) +
1213 (slop
<< HAMMER_LARGEBLOCK_BITS
);
1215 hammer_count_extra_space_used
= usedbytes
; /* debugging */
1219 if (hmp
->copy_stat_freebigblocks
>=
1220 (usedbytes
>> HAMMER_LARGEBLOCK_BITS
)) {