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,
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,
69 int bytes, 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 */
93 * Deal with alignment and buffer-boundary issues.
95 * Be careful, certain primary alignments are used below to allocate
96 * new blockmap blocks.
98 bytes = (bytes + 15) & ~15;
99 KKASSERT(bytes > 0 && bytes <= HAMMER_XBUFSIZE);
100 KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
105 root_volume = trans->rootvol;
107 blockmap = &hmp->blockmap[zone];
108 freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
109 KKASSERT(HAMMER_ZONE_DECODE(blockmap->next_offset) == zone);
111 next_offset = blockmap->next_offset;
116 if (next_offset == HAMMER_ZONE_ENCODE(zone + 1, 0)) {
122 next_offset = HAMMER_ZONE_ENCODE(zone, 0);
126 * The allocation request may not cross a buffer boundary. Special
127 * large allocations must not cross a large-block boundary.
129 tmp_offset = next_offset + bytes - 1;
130 if (bytes <= HAMMER_BUFSIZE) {
131 if ((next_offset ^ tmp_offset) & ~HAMMER_BUFMASK64) {
132 next_offset = tmp_offset & ~HAMMER_BUFMASK64;
136 if ((next_offset ^ tmp_offset) & ~HAMMER_LARGEBLOCK_MASK64) {
137 next_offset = tmp_offset & ~HAMMER_LARGEBLOCK_MASK64;
141 offset = (int)next_offset & HAMMER_LARGEBLOCK_MASK;
146 layer1_offset = freemap->phys_offset +
147 HAMMER_BLOCKMAP_LAYER1_OFFSET(next_offset);
148 layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer1);
157 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
158 hammer_lock_ex(&hmp->blkmap_lock);
159 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE))
160 panic("CRC FAILED: LAYER1");
161 hammer_unlock(&hmp->blkmap_lock);
165 * If we are at a big-block boundary and layer1 indicates no
166 * free big-blocks, then we cannot allocate a new bigblock in
167 * layer2, skip to the next layer1 entry.
169 if (offset == 0 && layer1->blocks_free == 0) {
170 next_offset = (next_offset + HAMMER_BLOCKMAP_LAYER2) &
171 ~HAMMER_BLOCKMAP_LAYER2_MASK;
174 KKASSERT(layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
177 * Dive layer 2, each entry represents a large-block.
179 layer2_offset = layer1->phys_offset +
180 HAMMER_BLOCKMAP_LAYER2_OFFSET(next_offset);
181 layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer2);
188 * Check CRC. This can race another thread holding the lock
189 * and in the middle of modifying layer2.
191 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
192 hammer_lock_ex(&hmp->blkmap_lock);
193 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE))
194 panic("CRC FAILED: LAYER2");
195 hammer_unlock(&hmp->blkmap_lock);
199 * Skip the layer if the zone is owned by someone other then us.
201 if (layer2->zone && layer2->zone != zone) {
202 next_offset += (HAMMER_LARGEBLOCK_SIZE - offset);
205 if (offset < layer2->append_off) {
206 next_offset += layer2->append_off - offset;
211 * We need the lock from this point on. We have to re-check zone
212 * ownership after acquiring the lock and also check for reservations.
214 hammer_lock_ex(&hmp->blkmap_lock);
216 if (layer2->zone && layer2->zone != zone) {
217 hammer_unlock(&hmp->blkmap_lock);
218 next_offset += (HAMMER_LARGEBLOCK_SIZE - offset);
221 if (offset < layer2->append_off) {
222 hammer_unlock(&hmp->blkmap_lock);
223 next_offset += layer2->append_off - offset;
228 * The bigblock might be reserved by another zone. If it is reserved
229 * by our zone we may have to move next_offset past the append_off.
231 base_off = (next_offset &
232 (~HAMMER_LARGEBLOCK_MASK64 & ~HAMMER_OFF_ZONE_MASK)) |
233 HAMMER_ZONE_RAW_BUFFER;
234 resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root, base_off);
236 if (resv->zone != zone) {
237 hammer_unlock(&hmp->blkmap_lock);
238 next_offset = (next_offset + HAMMER_LARGEBLOCK_SIZE) &
239 ~HAMMER_LARGEBLOCK_MASK64;
242 if (offset < resv->append_off) {
243 hammer_unlock(&hmp->blkmap_lock);
244 next_offset += resv->append_off - offset;
250 * Ok, we can allocate out of this layer2 big-block. Assume ownership
251 * of the layer for real. At this point we've validated any
252 * reservation that might exist and can just ignore resv.
254 if (layer2->zone == 0) {
256 * Assign the bigblock to our zone
258 hammer_modify_buffer(trans, buffer1,
259 layer1, sizeof(*layer1));
260 --layer1->blocks_free;
261 layer1->layer1_crc = crc32(layer1,
262 HAMMER_LAYER1_CRCSIZE);
263 hammer_modify_buffer_done(buffer1);
264 hammer_modify_buffer(trans, buffer2,
265 layer2, sizeof(*layer2));
267 KKASSERT(layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE);
268 KKASSERT(layer2->append_off == 0);
269 hammer_modify_volume_field(trans, trans->rootvol,
270 vol0_stat_freebigblocks);
271 --root_volume->ondisk->vol0_stat_freebigblocks;
272 hmp->copy_stat_freebigblocks =
273 root_volume->ondisk->vol0_stat_freebigblocks;
274 hammer_modify_volume_done(trans->rootvol);
276 hammer_modify_buffer(trans, buffer2,
277 layer2, sizeof(*layer2));
279 KKASSERT(layer2->zone == zone);
281 layer2->bytes_free -= bytes;
282 KKASSERT(layer2->append_off <= offset);
283 layer2->append_off = offset + bytes;
284 layer2->entry_crc = crc32(layer2, HAMMER_LAYER2_CRCSIZE);
285 hammer_modify_buffer_done(buffer2);
286 KKASSERT(layer2->bytes_free >= 0);
289 KKASSERT(resv->append_off <= offset);
290 resv->append_off = offset + bytes;
291 resv->flags &= ~HAMMER_RESF_LAYER2FREE;
295 * If we are allocating from the base of a new buffer we can avoid
296 * a disk read by calling hammer_bnew().
298 if ((next_offset & HAMMER_BUFMASK) == 0) {
299 hammer_bnew_ext(trans->hmp, next_offset, bytes,
302 result_offset = next_offset;
305 * Process allocated result_offset
307 hammer_modify_volume(NULL, root_volume, NULL, 0);
308 blockmap->next_offset = next_offset + bytes;
309 hammer_modify_volume_done(root_volume);
310 hammer_unlock(&hmp->blkmap_lock);
317 hammer_rel_buffer(buffer1, 0);
319 hammer_rel_buffer(buffer2, 0);
321 hammer_rel_buffer(buffer3, 0);
323 return(result_offset);
327 * Frontend function - Reserve bytes in a zone.
329 * This code reserves bytes out of a blockmap without committing to any
330 * meta-data modifications, allowing the front-end to directly issue disk
331 * write I/O for large blocks of data
333 * The backend later finalizes the reservation with hammer_blockmap_finalize()
334 * upon committing the related record.
337 hammer_blockmap_reserve(hammer_mount_t hmp, int zone, int bytes,
338 hammer_off_t *zone_offp, int *errorp)
340 hammer_volume_t root_volume;
341 hammer_blockmap_t blockmap;
342 hammer_blockmap_t freemap;
343 struct hammer_blockmap_layer1 *layer1;
344 struct hammer_blockmap_layer2 *layer2;
345 hammer_buffer_t buffer1 = NULL;
346 hammer_buffer_t buffer2 = NULL;
347 hammer_buffer_t buffer3 = NULL;
348 hammer_off_t tmp_offset;
349 hammer_off_t next_offset;
350 hammer_off_t layer1_offset;
351 hammer_off_t layer2_offset;
352 hammer_off_t base_off;
353 hammer_reserve_t resv;
354 hammer_reserve_t resx;
361 KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
362 root_volume = hammer_get_root_volume(hmp, errorp);
365 blockmap = &hmp->blockmap[zone];
366 freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
367 KKASSERT(HAMMER_ZONE_DECODE(blockmap->next_offset) == zone);
370 * Deal with alignment and buffer-boundary issues.
372 * Be careful, certain primary alignments are used below to allocate
373 * new blockmap blocks.
375 bytes = (bytes + 15) & ~15;
376 KKASSERT(bytes > 0 && bytes <= HAMMER_XBUFSIZE);
378 next_offset = blockmap->next_offset;
384 if (next_offset == HAMMER_ZONE_ENCODE(zone + 1, 0)) {
389 next_offset = HAMMER_ZONE_ENCODE(zone, 0);
393 * The allocation request may not cross a buffer boundary. Special
394 * large allocations must not cross a large-block boundary.
396 tmp_offset = next_offset + bytes - 1;
397 if (bytes <= HAMMER_BUFSIZE) {
398 if ((next_offset ^ tmp_offset) & ~HAMMER_BUFMASK64) {
399 next_offset = tmp_offset & ~HAMMER_BUFMASK64;
403 if ((next_offset ^ tmp_offset) & ~HAMMER_LARGEBLOCK_MASK64) {
404 next_offset = tmp_offset & ~HAMMER_LARGEBLOCK_MASK64;
408 offset = (int)next_offset & HAMMER_LARGEBLOCK_MASK;
413 layer1_offset = freemap->phys_offset +
414 HAMMER_BLOCKMAP_LAYER1_OFFSET(next_offset);
415 layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer1);
422 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
423 hammer_lock_ex(&hmp->blkmap_lock);
424 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE))
425 panic("CRC FAILED: LAYER1");
426 hammer_unlock(&hmp->blkmap_lock);
430 * If we are at a big-block boundary and layer1 indicates no
431 * free big-blocks, then we cannot allocate a new bigblock in
432 * layer2, skip to the next layer1 entry.
434 if ((next_offset & HAMMER_LARGEBLOCK_MASK) == 0 &&
435 layer1->blocks_free == 0) {
436 next_offset = (next_offset + HAMMER_BLOCKMAP_LAYER2) &
437 ~HAMMER_BLOCKMAP_LAYER2_MASK;
440 KKASSERT(layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
443 * Dive layer 2, each entry represents a large-block.
445 layer2_offset = layer1->phys_offset +
446 HAMMER_BLOCKMAP_LAYER2_OFFSET(next_offset);
447 layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer2);
452 * Check CRC if not allocating into uninitialized space (which we
453 * aren't when reserving space).
455 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
456 hammer_lock_ex(&hmp->blkmap_lock);
457 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE))
458 panic("CRC FAILED: LAYER2");
459 hammer_unlock(&hmp->blkmap_lock);
463 * Skip the layer if the zone is owned by someone other then us.
465 if (layer2->zone && layer2->zone != zone) {
466 next_offset += (HAMMER_LARGEBLOCK_SIZE - offset);
469 if (offset < layer2->append_off) {
470 next_offset += layer2->append_off - offset;
475 * We need the lock from this point on. We have to re-check zone
476 * ownership after acquiring the lock and also check for reservations.
478 hammer_lock_ex(&hmp->blkmap_lock);
480 if (layer2->zone && layer2->zone != zone) {
481 hammer_unlock(&hmp->blkmap_lock);
482 next_offset += (HAMMER_LARGEBLOCK_SIZE - offset);
485 if (offset < layer2->append_off) {
486 hammer_unlock(&hmp->blkmap_lock);
487 next_offset += layer2->append_off - offset;
492 * The bigblock might be reserved by another zone. If it is reserved
493 * by our zone we may have to move next_offset past the append_off.
495 base_off = (next_offset &
496 (~HAMMER_LARGEBLOCK_MASK64 & ~HAMMER_OFF_ZONE_MASK)) |
497 HAMMER_ZONE_RAW_BUFFER;
498 resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root, base_off);
500 if (resv->zone != zone) {
501 hammer_unlock(&hmp->blkmap_lock);
502 next_offset = (next_offset + HAMMER_LARGEBLOCK_SIZE) &
503 ~HAMMER_LARGEBLOCK_MASK64;
506 if (offset < resv->append_off) {
507 hammer_unlock(&hmp->blkmap_lock);
508 next_offset += resv->append_off - offset;
514 resx = kmalloc(sizeof(*resv), hmp->m_misc,
515 M_WAITOK | M_ZERO | M_USE_RESERVE);
518 resx->zone_offset = base_off;
519 if (layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE)
520 resx->flags |= HAMMER_RESF_LAYER2FREE;
521 resv = RB_INSERT(hammer_res_rb_tree, &hmp->rb_resv_root, resx);
522 KKASSERT(resv == NULL);
524 ++hammer_count_reservations;
526 resv->append_off = offset + bytes;
529 * If we are not reserving a whole buffer but are at the start of
530 * a new block, call hammer_bnew() to avoid a disk read.
532 * If we are reserving a whole buffer (or more), the caller will
533 * probably use a direct read, so do nothing.
535 if (bytes < HAMMER_BUFSIZE && (next_offset & HAMMER_BUFMASK) == 0) {
536 hammer_bnew(hmp, next_offset, errorp, &buffer3);
540 * Adjust our iterator and alloc_offset. The layer1 and layer2
541 * space beyond alloc_offset is uninitialized. alloc_offset must
542 * be big-block aligned.
544 blockmap->next_offset = next_offset + bytes;
545 hammer_unlock(&hmp->blkmap_lock);
549 hammer_rel_buffer(buffer1, 0);
551 hammer_rel_buffer(buffer2, 0);
553 hammer_rel_buffer(buffer3, 0);
554 hammer_rel_volume(root_volume, 0);
555 *zone_offp = next_offset;
562 * Backend function - undo a portion of a reservation.
565 hammer_blockmap_reserve_undo(hammer_mount_t hmp, hammer_reserve_t resv,
566 hammer_off_t zone_offset, int bytes)
568 resv->bytes_freed += bytes;
574 * Dereference a reservation structure. Upon the final release the
575 * underlying big-block is checked and if it is entirely free we delete
576 * any related HAMMER buffers to avoid potential conflicts with future
577 * reuse of the big-block.
580 hammer_blockmap_reserve_complete(hammer_mount_t hmp, hammer_reserve_t resv)
582 hammer_off_t base_offset;
585 KKASSERT(resv->refs > 0);
586 KKASSERT((resv->zone_offset & HAMMER_OFF_ZONE_MASK) ==
587 HAMMER_ZONE_RAW_BUFFER);
590 * Setting append_off to the max prevents any new allocations
591 * from occuring while we are trying to dispose of the reservation,
592 * allowing us to safely delete any related HAMMER buffers.
594 * If we are unable to clean out all related HAMMER buffers we
597 if (resv->refs == 1 && (resv->flags & HAMMER_RESF_LAYER2FREE)) {
598 resv->append_off = HAMMER_LARGEBLOCK_SIZE;
599 resv->flags &= ~HAMMER_RESF_LAYER2FREE;
600 base_offset = resv->zone_offset & ~HAMMER_ZONE_RAW_BUFFER;
601 base_offset = HAMMER_ZONE_ENCODE(base_offset, resv->zone);
602 error = hammer_del_buffers(hmp, base_offset,
604 HAMMER_LARGEBLOCK_SIZE,
607 hammer_reserve_setdelay(hmp, resv);
609 if (--resv->refs == 0) {
610 KKASSERT((resv->flags & HAMMER_RESF_ONDELAY) == 0);
611 RB_REMOVE(hammer_res_rb_tree, &hmp->rb_resv_root, resv);
612 kfree(resv, hmp->m_misc);
613 --hammer_count_reservations;
618 * Prevent a potentially free big-block from being reused until after
619 * the related flushes have completely cycled, otherwise crash recovery
620 * could resurrect a data block that was already reused and overwritten.
622 * Return 0 if the layer2 entry is still completely free after the
623 * reservation has been allocated.
626 hammer_reserve_setdelay_offset(hammer_mount_t hmp, hammer_off_t base_offset,
627 struct hammer_blockmap_layer2 *layer2)
629 hammer_reserve_t resv;
632 * Allocate the reservation if necessary.
635 resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root, base_offset);
637 resv = kmalloc(sizeof(*resv), hmp->m_misc,
638 M_WAITOK | M_ZERO | M_USE_RESERVE);
639 resv->zone_offset = base_offset;
641 /* XXX inherent lock until refs bumped later on */
642 if (layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE)
643 resv->flags |= HAMMER_RESF_LAYER2FREE;
644 if (RB_INSERT(hammer_res_rb_tree, &hmp->rb_resv_root, resv)) {
645 kfree(resv, hmp->m_misc);
648 ++hammer_count_reservations;
653 * Enter the reservation on the on-delay list, or move it if it
654 * is already on the list.
657 hammer_reserve_setdelay(hammer_mount_t hmp, hammer_reserve_t resv)
659 if (resv->flags & HAMMER_RESF_ONDELAY) {
660 TAILQ_REMOVE(&hmp->delay_list, resv, delay_entry);
661 resv->flush_group = hmp->flusher.next + 1;
662 TAILQ_INSERT_TAIL(&hmp->delay_list, resv, delay_entry);
665 ++hmp->rsv_fromdelay;
666 resv->flags |= HAMMER_RESF_ONDELAY;
667 resv->flush_group = hmp->flusher.next + 1;
668 TAILQ_INSERT_TAIL(&hmp->delay_list, resv, delay_entry);
673 hammer_reserve_clrdelay(hammer_mount_t hmp, hammer_reserve_t resv)
675 KKASSERT(resv->flags & HAMMER_RESF_ONDELAY);
676 resv->flags &= ~HAMMER_RESF_ONDELAY;
677 TAILQ_REMOVE(&hmp->delay_list, resv, delay_entry);
678 --hmp->rsv_fromdelay;
679 hammer_blockmap_reserve_complete(hmp, resv);
683 * Backend function - free (offset, bytes) in a zone.
688 hammer_blockmap_free(hammer_transaction_t trans,
689 hammer_off_t zone_offset, int bytes)
692 hammer_volume_t root_volume;
693 hammer_blockmap_t blockmap;
694 hammer_blockmap_t freemap;
695 struct hammer_blockmap_layer1 *layer1;
696 struct hammer_blockmap_layer2 *layer2;
697 hammer_buffer_t buffer1 = NULL;
698 hammer_buffer_t buffer2 = NULL;
699 hammer_off_t layer1_offset;
700 hammer_off_t layer2_offset;
701 hammer_off_t base_off;
712 bytes = (bytes + 15) & ~15;
713 KKASSERT(bytes <= HAMMER_XBUFSIZE);
714 KKASSERT(((zone_offset ^ (zone_offset + (bytes - 1))) &
715 ~HAMMER_LARGEBLOCK_MASK64) == 0);
718 * Basic zone validation & locking
720 zone = HAMMER_ZONE_DECODE(zone_offset);
721 KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
722 root_volume = trans->rootvol;
725 blockmap = &hmp->blockmap[zone];
726 freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
731 layer1_offset = freemap->phys_offset +
732 HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
733 layer1 = hammer_bread(hmp, layer1_offset, &error, &buffer1);
736 KKASSERT(layer1->phys_offset &&
737 layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
738 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
739 hammer_lock_ex(&hmp->blkmap_lock);
740 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE))
741 panic("CRC FAILED: LAYER1");
742 hammer_unlock(&hmp->blkmap_lock);
746 * Dive layer 2, each entry represents a large-block.
748 layer2_offset = layer1->phys_offset +
749 HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
750 layer2 = hammer_bread(hmp, layer2_offset, &error, &buffer2);
753 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
754 hammer_lock_ex(&hmp->blkmap_lock);
755 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE))
756 panic("CRC FAILED: LAYER2");
757 hammer_unlock(&hmp->blkmap_lock);
760 hammer_lock_ex(&hmp->blkmap_lock);
762 hammer_modify_buffer(trans, buffer2, layer2, sizeof(*layer2));
765 * Free space previously allocated via blockmap_alloc().
767 KKASSERT(layer2->zone == zone);
768 layer2->bytes_free += bytes;
769 KKASSERT(layer2->bytes_free <= HAMMER_LARGEBLOCK_SIZE);
772 * If a big-block becomes entirely free we must create a covering
773 * reservation to prevent premature reuse. Note, however, that
774 * the big-block and/or reservation may still have an append_off
775 * that allows further (non-reused) allocations.
777 * Once the reservation has been made we re-check layer2 and if
778 * the big-block is still entirely free we reset the layer2 entry.
779 * The reservation will prevent premature reuse.
781 * NOTE: hammer_buffer's are only invalidated when the reservation
782 * is completed, if the layer2 entry is still completely free at
783 * that time. Any allocations from the reservation that may have
784 * occured in the mean time, or active references on the reservation
785 * from new pending allocations, will prevent the invalidation from
788 if (layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE) {
789 base_off = (zone_offset & (~HAMMER_LARGEBLOCK_MASK64 & ~HAMMER_OFF_ZONE_MASK)) | HAMMER_ZONE_RAW_BUFFER;
791 hammer_reserve_setdelay_offset(hmp, base_off, layer2);
792 if (layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE) {
794 layer2->append_off = 0;
795 hammer_modify_buffer(trans, buffer1,
796 layer1, sizeof(*layer1));
797 ++layer1->blocks_free;
798 layer1->layer1_crc = crc32(layer1,
799 HAMMER_LAYER1_CRCSIZE);
800 hammer_modify_buffer_done(buffer1);
801 hammer_modify_volume_field(trans,
803 vol0_stat_freebigblocks);
804 ++root_volume->ondisk->vol0_stat_freebigblocks;
805 hmp->copy_stat_freebigblocks =
806 root_volume->ondisk->vol0_stat_freebigblocks;
807 hammer_modify_volume_done(trans->rootvol);
810 layer2->entry_crc = crc32(layer2, HAMMER_LAYER2_CRCSIZE);
811 hammer_modify_buffer_done(buffer2);
812 hammer_unlock(&hmp->blkmap_lock);
816 hammer_rel_buffer(buffer1, 0);
818 hammer_rel_buffer(buffer2, 0);
822 * Backend function - finalize (offset, bytes) in a zone.
824 * Allocate space that was previously reserved by the frontend.
827 hammer_blockmap_finalize(hammer_transaction_t trans,
828 hammer_reserve_t resv,
829 hammer_off_t zone_offset, int bytes)
832 hammer_volume_t root_volume;
833 hammer_blockmap_t blockmap;
834 hammer_blockmap_t freemap;
835 struct hammer_blockmap_layer1 *layer1;
836 struct hammer_blockmap_layer2 *layer2;
837 hammer_buffer_t buffer1 = NULL;
838 hammer_buffer_t buffer2 = NULL;
839 hammer_off_t layer1_offset;
840 hammer_off_t layer2_offset;
852 bytes = (bytes + 15) & ~15;
853 KKASSERT(bytes <= HAMMER_XBUFSIZE);
856 * Basic zone validation & locking
858 zone = HAMMER_ZONE_DECODE(zone_offset);
859 KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
860 root_volume = trans->rootvol;
863 blockmap = &hmp->blockmap[zone];
864 freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
869 layer1_offset = freemap->phys_offset +
870 HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
871 layer1 = hammer_bread(hmp, layer1_offset, &error, &buffer1);
874 KKASSERT(layer1->phys_offset &&
875 layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
876 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
877 hammer_lock_ex(&hmp->blkmap_lock);
878 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE))
879 panic("CRC FAILED: LAYER1");
880 hammer_unlock(&hmp->blkmap_lock);
884 * Dive layer 2, each entry represents a large-block.
886 layer2_offset = layer1->phys_offset +
887 HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
888 layer2 = hammer_bread(hmp, layer2_offset, &error, &buffer2);
891 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
892 hammer_lock_ex(&hmp->blkmap_lock);
893 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE))
894 panic("CRC FAILED: LAYER2");
895 hammer_unlock(&hmp->blkmap_lock);
898 hammer_lock_ex(&hmp->blkmap_lock);
900 hammer_modify_buffer(trans, buffer2, layer2, sizeof(*layer2));
903 * Finalize some or all of the space covered by a current
904 * reservation. An allocation in the same layer may have
905 * already assigned ownership.
907 if (layer2->zone == 0) {
908 hammer_modify_buffer(trans, buffer1,
909 layer1, sizeof(*layer1));
910 --layer1->blocks_free;
911 layer1->layer1_crc = crc32(layer1,
912 HAMMER_LAYER1_CRCSIZE);
913 hammer_modify_buffer_done(buffer1);
915 KKASSERT(layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE);
916 KKASSERT(layer2->append_off == 0);
917 hammer_modify_volume_field(trans,
919 vol0_stat_freebigblocks);
920 --root_volume->ondisk->vol0_stat_freebigblocks;
921 hmp->copy_stat_freebigblocks =
922 root_volume->ondisk->vol0_stat_freebigblocks;
923 hammer_modify_volume_done(trans->rootvol);
925 if (layer2->zone != zone)
926 kprintf("layer2 zone mismatch %d %d\n", layer2->zone, zone);
927 KKASSERT(layer2->zone == zone);
928 layer2->bytes_free -= bytes;
930 resv->flags &= ~HAMMER_RESF_LAYER2FREE;
933 * Finalizations can occur out of order, or combined with allocations.
934 * append_off must be set to the highest allocated offset.
936 offset = ((int)zone_offset & HAMMER_LARGEBLOCK_MASK) + bytes;
937 if (layer2->append_off < offset)
938 layer2->append_off = offset;
940 layer2->entry_crc = crc32(layer2, HAMMER_LAYER2_CRCSIZE);
941 hammer_modify_buffer_done(buffer2);
942 hammer_unlock(&hmp->blkmap_lock);
946 hammer_rel_buffer(buffer1, 0);
948 hammer_rel_buffer(buffer2, 0);
953 * Return the number of free bytes in the big-block containing the
954 * specified blockmap offset.
957 hammer_blockmap_getfree(hammer_mount_t hmp, hammer_off_t zone_offset,
958 int *curp, int *errorp)
960 hammer_volume_t root_volume;
961 hammer_blockmap_t blockmap;
962 hammer_blockmap_t freemap;
963 struct hammer_blockmap_layer1 *layer1;
964 struct hammer_blockmap_layer2 *layer2;
965 hammer_buffer_t buffer = NULL;
966 hammer_off_t layer1_offset;
967 hammer_off_t layer2_offset;
971 zone = HAMMER_ZONE_DECODE(zone_offset);
972 KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
973 root_volume = hammer_get_root_volume(hmp, errorp);
978 blockmap = &hmp->blockmap[zone];
979 freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
984 layer1_offset = freemap->phys_offset +
985 HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
986 layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer);
991 KKASSERT(layer1->phys_offset);
992 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
993 hammer_lock_ex(&hmp->blkmap_lock);
994 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE))
995 panic("CRC FAILED: LAYER1");
996 hammer_unlock(&hmp->blkmap_lock);
1000 * Dive layer 2, each entry represents a large-block.
1002 * (reuse buffer, layer1 pointer becomes invalid)
1004 layer2_offset = layer1->phys_offset +
1005 HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
1006 layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer);
1011 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
1012 hammer_lock_ex(&hmp->blkmap_lock);
1013 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE))
1014 panic("CRC FAILED: LAYER2");
1015 hammer_unlock(&hmp->blkmap_lock);
1017 KKASSERT(layer2->zone == zone);
1019 bytes = layer2->bytes_free;
1021 if ((blockmap->next_offset ^ zone_offset) & ~HAMMER_LARGEBLOCK_MASK64)
1027 hammer_rel_buffer(buffer, 0);
1028 hammer_rel_volume(root_volume, 0);
1029 if (hammer_debug_general & 0x0800) {
1030 kprintf("hammer_blockmap_getfree: %016llx -> %d\n",
1031 zone_offset, bytes);
1038 * Lookup a blockmap offset.
1041 hammer_blockmap_lookup(hammer_mount_t hmp, hammer_off_t zone_offset,
1044 hammer_volume_t root_volume;
1045 hammer_blockmap_t freemap;
1046 struct hammer_blockmap_layer1 *layer1;
1047 struct hammer_blockmap_layer2 *layer2;
1048 hammer_buffer_t buffer = NULL;
1049 hammer_off_t layer1_offset;
1050 hammer_off_t layer2_offset;
1051 hammer_off_t result_offset;
1052 hammer_off_t base_off;
1053 hammer_reserve_t resv;
1057 * Calculate the zone-2 offset.
1059 zone = HAMMER_ZONE_DECODE(zone_offset);
1060 KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
1062 result_offset = (zone_offset & ~HAMMER_OFF_ZONE_MASK) |
1063 HAMMER_ZONE_RAW_BUFFER;
1066 * We can actually stop here, normal blockmaps are now direct-mapped
1067 * onto the freemap and so represent zone-2 addresses.
1069 if (hammer_verify_zone == 0) {
1071 return(result_offset);
1075 * Validate the allocation zone
1077 root_volume = hammer_get_root_volume(hmp, errorp);
1080 freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
1081 KKASSERT(freemap->phys_offset != 0);
1086 layer1_offset = freemap->phys_offset +
1087 HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
1088 layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer);
1091 KKASSERT(layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
1092 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
1093 hammer_lock_ex(&hmp->blkmap_lock);
1094 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE))
1095 panic("CRC FAILED: LAYER1");
1096 hammer_unlock(&hmp->blkmap_lock);
1100 * Dive layer 2, each entry represents a large-block.
1102 layer2_offset = layer1->phys_offset +
1103 HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
1104 layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer);
1108 if (layer2->zone == 0) {
1109 base_off = (zone_offset & (~HAMMER_LARGEBLOCK_MASK64 & ~HAMMER_OFF_ZONE_MASK)) | HAMMER_ZONE_RAW_BUFFER;
1110 resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root,
1112 KKASSERT(resv && resv->zone == zone);
1114 } else if (layer2->zone != zone) {
1115 panic("hammer_blockmap_lookup: bad zone %d/%d\n",
1116 layer2->zone, zone);
1118 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
1119 hammer_lock_ex(&hmp->blkmap_lock);
1120 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE))
1121 panic("CRC FAILED: LAYER2");
1122 hammer_unlock(&hmp->blkmap_lock);
1127 hammer_rel_buffer(buffer, 0);
1128 hammer_rel_volume(root_volume, 0);
1129 if (hammer_debug_general & 0x0800) {
1130 kprintf("hammer_blockmap_lookup: %016llx -> %016llx\n",
1131 zone_offset, result_offset);
1133 return(result_offset);
1138 * Check space availability
1141 hammer_checkspace(hammer_mount_t hmp, int slop)
1143 const int in_size = sizeof(struct hammer_inode_data) +
1144 sizeof(union hammer_btree_elm);
1145 const int rec_size = (sizeof(union hammer_btree_elm) * 2);
1148 usedbytes = hmp->rsv_inodes * in_size +
1149 hmp->rsv_recs * rec_size +
1150 hmp->rsv_databytes +
1151 ((int64_t)hmp->rsv_fromdelay << HAMMER_LARGEBLOCK_BITS) +
1152 ((int64_t)hidirtybufspace << 2) +
1153 (slop << HAMMER_LARGEBLOCK_BITS);
1155 hammer_count_extra_space_used = usedbytes; /* debugging */
1157 if (hmp->copy_stat_freebigblocks >=
1158 (usedbytes >> HAMMER_LARGEBLOCK_BITS)) {