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,
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;
251 * Ok, we can allocate out of this layer2 big-block. Assume ownership
252 * of the layer for real. At this point we've validated any
253 * reservation that might exist and can just ignore resv.
255 if (layer2->zone == 0) {
257 * Assign the bigblock to our zone
259 hammer_modify_buffer(trans, buffer1,
260 layer1, sizeof(*layer1));
261 --layer1->blocks_free;
262 layer1->layer1_crc = crc32(layer1,
263 HAMMER_LAYER1_CRCSIZE);
264 hammer_modify_buffer_done(buffer1);
265 hammer_modify_buffer(trans, buffer2,
266 layer2, sizeof(*layer2));
268 KKASSERT(layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE);
269 KKASSERT(layer2->append_off == 0);
270 hammer_modify_volume_field(trans, trans->rootvol,
271 vol0_stat_freebigblocks);
272 --root_volume->ondisk->vol0_stat_freebigblocks;
273 hmp->copy_stat_freebigblocks =
274 root_volume->ondisk->vol0_stat_freebigblocks;
275 hammer_modify_volume_done(trans->rootvol);
277 hammer_modify_buffer(trans, buffer2,
278 layer2, sizeof(*layer2));
280 KKASSERT(layer2->zone == zone);
282 layer2->bytes_free -= bytes;
283 KKASSERT(layer2->append_off <= offset);
284 layer2->append_off = offset + bytes;
285 layer2->entry_crc = crc32(layer2, HAMMER_LAYER2_CRCSIZE);
286 hammer_modify_buffer_done(buffer2);
287 KKASSERT(layer2->bytes_free >= 0);
290 * We hold the blockmap lock and should be the only ones
291 * capable of modifying resv->append_off. Track the allocation
294 KKASSERT(bytes != 0);
296 KKASSERT(resv->append_off <= offset);
297 resv->append_off = offset + bytes;
298 resv->flags &= ~HAMMER_RESF_LAYER2FREE;
299 hammer_blockmap_reserve_complete(hmp, resv);
303 * If we are allocating from the base of a new buffer we can avoid
304 * a disk read by calling hammer_bnew().
306 if ((next_offset & HAMMER_BUFMASK) == 0) {
307 hammer_bnew_ext(trans->hmp, next_offset, bytes,
310 result_offset = next_offset;
313 * Process allocated result_offset
315 hammer_modify_volume(NULL, root_volume, NULL, 0);
316 blockmap->next_offset = next_offset + bytes;
317 hammer_modify_volume_done(root_volume);
318 hammer_unlock(&hmp->blkmap_lock);
325 hammer_rel_buffer(buffer1, 0);
327 hammer_rel_buffer(buffer2, 0);
329 hammer_rel_buffer(buffer3, 0);
331 return(result_offset);
335 * Frontend function - Reserve bytes in a zone.
337 * This code reserves bytes out of a blockmap without committing to any
338 * meta-data modifications, allowing the front-end to directly issue disk
339 * write I/O for large blocks of data
341 * The backend later finalizes the reservation with hammer_blockmap_finalize()
342 * upon committing the related record.
345 hammer_blockmap_reserve(hammer_mount_t hmp, int zone, int bytes,
346 hammer_off_t *zone_offp, int *errorp)
348 hammer_volume_t root_volume;
349 hammer_blockmap_t blockmap;
350 hammer_blockmap_t freemap;
351 struct hammer_blockmap_layer1 *layer1;
352 struct hammer_blockmap_layer2 *layer2;
353 hammer_buffer_t buffer1 = NULL;
354 hammer_buffer_t buffer2 = NULL;
355 hammer_buffer_t buffer3 = NULL;
356 hammer_off_t tmp_offset;
357 hammer_off_t next_offset;
358 hammer_off_t layer1_offset;
359 hammer_off_t layer2_offset;
360 hammer_off_t base_off;
361 hammer_reserve_t resv;
362 hammer_reserve_t resx;
369 KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
370 root_volume = hammer_get_root_volume(hmp, errorp);
373 blockmap = &hmp->blockmap[zone];
374 freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
375 KKASSERT(HAMMER_ZONE_DECODE(blockmap->next_offset) == zone);
378 * Deal with alignment and buffer-boundary issues.
380 * Be careful, certain primary alignments are used below to allocate
381 * new blockmap blocks.
383 bytes = (bytes + 15) & ~15;
384 KKASSERT(bytes > 0 && bytes <= HAMMER_XBUFSIZE);
386 next_offset = blockmap->next_offset;
392 if (next_offset == HAMMER_ZONE_ENCODE(zone + 1, 0)) {
397 next_offset = HAMMER_ZONE_ENCODE(zone, 0);
401 * The allocation request may not cross a buffer boundary. Special
402 * large allocations must not cross a large-block boundary.
404 tmp_offset = next_offset + bytes - 1;
405 if (bytes <= HAMMER_BUFSIZE) {
406 if ((next_offset ^ tmp_offset) & ~HAMMER_BUFMASK64) {
407 next_offset = tmp_offset & ~HAMMER_BUFMASK64;
411 if ((next_offset ^ tmp_offset) & ~HAMMER_LARGEBLOCK_MASK64) {
412 next_offset = tmp_offset & ~HAMMER_LARGEBLOCK_MASK64;
416 offset = (int)next_offset & HAMMER_LARGEBLOCK_MASK;
421 layer1_offset = freemap->phys_offset +
422 HAMMER_BLOCKMAP_LAYER1_OFFSET(next_offset);
423 layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer1);
430 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
431 hammer_lock_ex(&hmp->blkmap_lock);
432 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE))
433 panic("CRC FAILED: LAYER1");
434 hammer_unlock(&hmp->blkmap_lock);
438 * If we are at a big-block boundary and layer1 indicates no
439 * free big-blocks, then we cannot allocate a new bigblock in
440 * layer2, skip to the next layer1 entry.
442 if ((next_offset & HAMMER_LARGEBLOCK_MASK) == 0 &&
443 layer1->blocks_free == 0) {
444 next_offset = (next_offset + HAMMER_BLOCKMAP_LAYER2) &
445 ~HAMMER_BLOCKMAP_LAYER2_MASK;
448 KKASSERT(layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
451 * Dive layer 2, each entry represents a large-block.
453 layer2_offset = layer1->phys_offset +
454 HAMMER_BLOCKMAP_LAYER2_OFFSET(next_offset);
455 layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer2);
460 * Check CRC if not allocating into uninitialized space (which we
461 * aren't when reserving space).
463 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
464 hammer_lock_ex(&hmp->blkmap_lock);
465 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE))
466 panic("CRC FAILED: LAYER2");
467 hammer_unlock(&hmp->blkmap_lock);
471 * Skip the layer if the zone is owned by someone other then us.
473 if (layer2->zone && layer2->zone != zone) {
474 next_offset += (HAMMER_LARGEBLOCK_SIZE - offset);
477 if (offset < layer2->append_off) {
478 next_offset += layer2->append_off - offset;
483 * We need the lock from this point on. We have to re-check zone
484 * ownership after acquiring the lock and also check for reservations.
486 hammer_lock_ex(&hmp->blkmap_lock);
488 if (layer2->zone && layer2->zone != zone) {
489 hammer_unlock(&hmp->blkmap_lock);
490 next_offset += (HAMMER_LARGEBLOCK_SIZE - offset);
493 if (offset < layer2->append_off) {
494 hammer_unlock(&hmp->blkmap_lock);
495 next_offset += layer2->append_off - offset;
500 * The bigblock might be reserved by another zone. If it is reserved
501 * by our zone we may have to move next_offset past the append_off.
503 base_off = (next_offset &
504 (~HAMMER_LARGEBLOCK_MASK64 & ~HAMMER_OFF_ZONE_MASK)) |
505 HAMMER_ZONE_RAW_BUFFER;
506 resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root, base_off);
508 if (resv->zone != zone) {
509 hammer_unlock(&hmp->blkmap_lock);
510 next_offset = (next_offset + HAMMER_LARGEBLOCK_SIZE) &
511 ~HAMMER_LARGEBLOCK_MASK64;
514 if (offset < resv->append_off) {
515 hammer_unlock(&hmp->blkmap_lock);
516 next_offset += resv->append_off - offset;
522 resx = kmalloc(sizeof(*resv), hmp->m_misc,
523 M_WAITOK | M_ZERO | M_USE_RESERVE);
526 resx->zone_offset = base_off;
527 if (layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE)
528 resx->flags |= HAMMER_RESF_LAYER2FREE;
529 resv = RB_INSERT(hammer_res_rb_tree, &hmp->rb_resv_root, resx);
530 KKASSERT(resv == NULL);
532 ++hammer_count_reservations;
534 resv->append_off = offset + bytes;
537 * If we are not reserving a whole buffer but are at the start of
538 * a new block, call hammer_bnew() to avoid a disk read.
540 * If we are reserving a whole buffer (or more), the caller will
541 * probably use a direct read, so do nothing.
543 if (bytes < HAMMER_BUFSIZE && (next_offset & HAMMER_BUFMASK) == 0) {
544 hammer_bnew(hmp, next_offset, errorp, &buffer3);
548 * Adjust our iterator and alloc_offset. The layer1 and layer2
549 * space beyond alloc_offset is uninitialized. alloc_offset must
550 * be big-block aligned.
552 blockmap->next_offset = next_offset + bytes;
553 hammer_unlock(&hmp->blkmap_lock);
557 hammer_rel_buffer(buffer1, 0);
559 hammer_rel_buffer(buffer2, 0);
561 hammer_rel_buffer(buffer3, 0);
562 hammer_rel_volume(root_volume, 0);
563 *zone_offp = next_offset;
569 * Dereference a reservation structure. Upon the final release the
570 * underlying big-block is checked and if it is entirely free we delete
571 * any related HAMMER buffers to avoid potential conflicts with future
572 * reuse of the big-block.
575 hammer_blockmap_reserve_complete(hammer_mount_t hmp, hammer_reserve_t resv)
577 hammer_off_t base_offset;
580 KKASSERT(resv->refs > 0);
581 KKASSERT((resv->zone_offset & HAMMER_OFF_ZONE_MASK) ==
582 HAMMER_ZONE_RAW_BUFFER);
585 * Setting append_off to the max prevents any new allocations
586 * from occuring while we are trying to dispose of the reservation,
587 * allowing us to safely delete any related HAMMER buffers.
589 * If we are unable to clean out all related HAMMER buffers we
592 if (resv->refs == 1 && (resv->flags & HAMMER_RESF_LAYER2FREE)) {
593 resv->append_off = HAMMER_LARGEBLOCK_SIZE;
594 base_offset = resv->zone_offset & ~HAMMER_OFF_ZONE_MASK;
595 base_offset = HAMMER_ZONE_ENCODE(resv->zone, base_offset);
596 error = hammer_del_buffers(hmp, base_offset,
598 HAMMER_LARGEBLOCK_SIZE,
601 hammer_reserve_setdelay(hmp, resv);
603 if (--resv->refs == 0) {
604 KKASSERT((resv->flags & HAMMER_RESF_ONDELAY) == 0);
605 RB_REMOVE(hammer_res_rb_tree, &hmp->rb_resv_root, resv);
606 kfree(resv, hmp->m_misc);
607 --hammer_count_reservations;
612 * Prevent a potentially free big-block from being reused until after
613 * the related flushes have completely cycled, otherwise crash recovery
614 * could resurrect a data block that was already reused and overwritten.
616 * The caller might reset the underlying layer2 entry's append_off to 0, so
617 * our covering append_off must be set to max to prevent any reallocation
618 * until after the flush delays complete, not to mention proper invalidation
619 * of any underlying cached blocks.
622 hammer_reserve_setdelay_offset(hammer_mount_t hmp, hammer_off_t base_offset,
623 int zone, struct hammer_blockmap_layer2 *layer2)
625 hammer_reserve_t resv;
628 * Allocate the reservation if necessary.
630 * NOTE: need lock in future around resv lookup/allocation and
631 * the setdelay call, currently refs is not bumped until the call.
634 resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root, base_offset);
636 resv = kmalloc(sizeof(*resv), hmp->m_misc,
637 M_WAITOK | M_ZERO | M_USE_RESERVE);
639 resv->zone_offset = base_offset;
641 resv->append_off = HAMMER_LARGEBLOCK_SIZE;
643 if (layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE)
644 resv->flags |= HAMMER_RESF_LAYER2FREE;
645 if (RB_INSERT(hammer_res_rb_tree, &hmp->rb_resv_root, resv)) {
646 kfree(resv, hmp->m_misc);
649 ++hammer_count_reservations;
651 if (layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE)
652 resv->flags |= HAMMER_RESF_LAYER2FREE;
654 hammer_reserve_setdelay(hmp, resv);
658 * Enter the reservation on the on-delay list, or move it if it
659 * is already on the list.
662 hammer_reserve_setdelay(hammer_mount_t hmp, hammer_reserve_t resv)
664 if (resv->flags & HAMMER_RESF_ONDELAY) {
665 TAILQ_REMOVE(&hmp->delay_list, resv, delay_entry);
666 resv->flush_group = hmp->flusher.next + 1;
667 TAILQ_INSERT_TAIL(&hmp->delay_list, resv, delay_entry);
670 ++hmp->rsv_fromdelay;
671 resv->flags |= HAMMER_RESF_ONDELAY;
672 resv->flush_group = hmp->flusher.next + 1;
673 TAILQ_INSERT_TAIL(&hmp->delay_list, resv, delay_entry);
678 hammer_reserve_clrdelay(hammer_mount_t hmp, hammer_reserve_t resv)
680 KKASSERT(resv->flags & HAMMER_RESF_ONDELAY);
681 resv->flags &= ~HAMMER_RESF_ONDELAY;
682 TAILQ_REMOVE(&hmp->delay_list, resv, delay_entry);
683 --hmp->rsv_fromdelay;
684 hammer_blockmap_reserve_complete(hmp, resv);
688 * Backend function - free (offset, bytes) in a zone.
693 hammer_blockmap_free(hammer_transaction_t trans,
694 hammer_off_t zone_offset, int bytes)
697 hammer_volume_t root_volume;
698 hammer_blockmap_t blockmap;
699 hammer_blockmap_t freemap;
700 struct hammer_blockmap_layer1 *layer1;
701 struct hammer_blockmap_layer2 *layer2;
702 hammer_buffer_t buffer1 = NULL;
703 hammer_buffer_t buffer2 = NULL;
704 hammer_off_t layer1_offset;
705 hammer_off_t layer2_offset;
706 hammer_off_t base_off;
717 bytes = (bytes + 15) & ~15;
718 KKASSERT(bytes <= HAMMER_XBUFSIZE);
719 KKASSERT(((zone_offset ^ (zone_offset + (bytes - 1))) &
720 ~HAMMER_LARGEBLOCK_MASK64) == 0);
723 * Basic zone validation & locking
725 zone = HAMMER_ZONE_DECODE(zone_offset);
726 KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
727 root_volume = trans->rootvol;
730 blockmap = &hmp->blockmap[zone];
731 freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
736 layer1_offset = freemap->phys_offset +
737 HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
738 layer1 = hammer_bread(hmp, layer1_offset, &error, &buffer1);
741 KKASSERT(layer1->phys_offset &&
742 layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
743 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
744 hammer_lock_ex(&hmp->blkmap_lock);
745 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE))
746 panic("CRC FAILED: LAYER1");
747 hammer_unlock(&hmp->blkmap_lock);
751 * Dive layer 2, each entry represents a large-block.
753 layer2_offset = layer1->phys_offset +
754 HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
755 layer2 = hammer_bread(hmp, layer2_offset, &error, &buffer2);
758 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
759 hammer_lock_ex(&hmp->blkmap_lock);
760 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE))
761 panic("CRC FAILED: LAYER2");
762 hammer_unlock(&hmp->blkmap_lock);
765 hammer_lock_ex(&hmp->blkmap_lock);
767 hammer_modify_buffer(trans, buffer2, layer2, sizeof(*layer2));
770 * Free space previously allocated via blockmap_alloc().
772 KKASSERT(layer2->zone == zone);
773 layer2->bytes_free += bytes;
774 KKASSERT(layer2->bytes_free <= HAMMER_LARGEBLOCK_SIZE);
777 * If a big-block becomes entirely free we must create a covering
778 * reservation to prevent premature reuse. Note, however, that
779 * the big-block and/or reservation may still have an append_off
780 * that allows further (non-reused) allocations.
782 * Once the reservation has been made we re-check layer2 and if
783 * the big-block is still entirely free we reset the layer2 entry.
784 * The reservation will prevent premature reuse.
786 * NOTE: hammer_buffer's are only invalidated when the reservation
787 * is completed, if the layer2 entry is still completely free at
788 * that time. Any allocations from the reservation that may have
789 * occured in the mean time, or active references on the reservation
790 * from new pending allocations, will prevent the invalidation from
793 if (layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE) {
794 base_off = (zone_offset & (~HAMMER_LARGEBLOCK_MASK64 & ~HAMMER_OFF_ZONE_MASK)) | HAMMER_ZONE_RAW_BUFFER;
796 hammer_reserve_setdelay_offset(hmp, base_off, zone, layer2);
797 if (layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE) {
799 layer2->append_off = 0;
800 hammer_modify_buffer(trans, buffer1,
801 layer1, sizeof(*layer1));
802 ++layer1->blocks_free;
803 layer1->layer1_crc = crc32(layer1,
804 HAMMER_LAYER1_CRCSIZE);
805 hammer_modify_buffer_done(buffer1);
806 hammer_modify_volume_field(trans,
808 vol0_stat_freebigblocks);
809 ++root_volume->ondisk->vol0_stat_freebigblocks;
810 hmp->copy_stat_freebigblocks =
811 root_volume->ondisk->vol0_stat_freebigblocks;
812 hammer_modify_volume_done(trans->rootvol);
815 layer2->entry_crc = crc32(layer2, HAMMER_LAYER2_CRCSIZE);
816 hammer_modify_buffer_done(buffer2);
817 hammer_unlock(&hmp->blkmap_lock);
821 hammer_rel_buffer(buffer1, 0);
823 hammer_rel_buffer(buffer2, 0);
827 * Backend function - finalize (offset, bytes) in a zone.
829 * Allocate space that was previously reserved by the frontend.
832 hammer_blockmap_finalize(hammer_transaction_t trans,
833 hammer_reserve_t resv,
834 hammer_off_t zone_offset, int bytes)
837 hammer_volume_t root_volume;
838 hammer_blockmap_t blockmap;
839 hammer_blockmap_t freemap;
840 struct hammer_blockmap_layer1 *layer1;
841 struct hammer_blockmap_layer2 *layer2;
842 hammer_buffer_t buffer1 = NULL;
843 hammer_buffer_t buffer2 = NULL;
844 hammer_off_t layer1_offset;
845 hammer_off_t layer2_offset;
857 bytes = (bytes + 15) & ~15;
858 KKASSERT(bytes <= HAMMER_XBUFSIZE);
861 * Basic zone validation & locking
863 zone = HAMMER_ZONE_DECODE(zone_offset);
864 KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
865 root_volume = trans->rootvol;
868 blockmap = &hmp->blockmap[zone];
869 freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
874 layer1_offset = freemap->phys_offset +
875 HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
876 layer1 = hammer_bread(hmp, layer1_offset, &error, &buffer1);
879 KKASSERT(layer1->phys_offset &&
880 layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
881 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
882 hammer_lock_ex(&hmp->blkmap_lock);
883 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE))
884 panic("CRC FAILED: LAYER1");
885 hammer_unlock(&hmp->blkmap_lock);
889 * Dive layer 2, each entry represents a large-block.
891 layer2_offset = layer1->phys_offset +
892 HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
893 layer2 = hammer_bread(hmp, layer2_offset, &error, &buffer2);
896 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
897 hammer_lock_ex(&hmp->blkmap_lock);
898 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE))
899 panic("CRC FAILED: LAYER2");
900 hammer_unlock(&hmp->blkmap_lock);
903 hammer_lock_ex(&hmp->blkmap_lock);
905 hammer_modify_buffer(trans, buffer2, layer2, sizeof(*layer2));
908 * Finalize some or all of the space covered by a current
909 * reservation. An allocation in the same layer may have
910 * already assigned ownership.
912 if (layer2->zone == 0) {
913 hammer_modify_buffer(trans, buffer1,
914 layer1, sizeof(*layer1));
915 --layer1->blocks_free;
916 layer1->layer1_crc = crc32(layer1,
917 HAMMER_LAYER1_CRCSIZE);
918 hammer_modify_buffer_done(buffer1);
920 KKASSERT(layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE);
921 KKASSERT(layer2->append_off == 0);
922 hammer_modify_volume_field(trans,
924 vol0_stat_freebigblocks);
925 --root_volume->ondisk->vol0_stat_freebigblocks;
926 hmp->copy_stat_freebigblocks =
927 root_volume->ondisk->vol0_stat_freebigblocks;
928 hammer_modify_volume_done(trans->rootvol);
930 if (layer2->zone != zone)
931 kprintf("layer2 zone mismatch %d %d\n", layer2->zone, zone);
932 KKASSERT(layer2->zone == zone);
933 KKASSERT(bytes != 0);
934 layer2->bytes_free -= bytes;
936 resv->flags &= ~HAMMER_RESF_LAYER2FREE;
939 * Finalizations can occur out of order, or combined with allocations.
940 * append_off must be set to the highest allocated offset.
942 offset = ((int)zone_offset & HAMMER_LARGEBLOCK_MASK) + bytes;
943 if (layer2->append_off < offset)
944 layer2->append_off = offset;
946 layer2->entry_crc = crc32(layer2, HAMMER_LAYER2_CRCSIZE);
947 hammer_modify_buffer_done(buffer2);
948 hammer_unlock(&hmp->blkmap_lock);
952 hammer_rel_buffer(buffer1, 0);
954 hammer_rel_buffer(buffer2, 0);
959 * Return the number of free bytes in the big-block containing the
960 * specified blockmap offset.
963 hammer_blockmap_getfree(hammer_mount_t hmp, hammer_off_t zone_offset,
964 int *curp, int *errorp)
966 hammer_volume_t root_volume;
967 hammer_blockmap_t blockmap;
968 hammer_blockmap_t freemap;
969 struct hammer_blockmap_layer1 *layer1;
970 struct hammer_blockmap_layer2 *layer2;
971 hammer_buffer_t buffer = NULL;
972 hammer_off_t layer1_offset;
973 hammer_off_t layer2_offset;
977 zone = HAMMER_ZONE_DECODE(zone_offset);
978 KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
979 root_volume = hammer_get_root_volume(hmp, errorp);
984 blockmap = &hmp->blockmap[zone];
985 freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
990 layer1_offset = freemap->phys_offset +
991 HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
992 layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer);
997 KKASSERT(layer1->phys_offset);
998 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
999 hammer_lock_ex(&hmp->blkmap_lock);
1000 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE))
1001 panic("CRC FAILED: LAYER1");
1002 hammer_unlock(&hmp->blkmap_lock);
1006 * Dive layer 2, each entry represents a large-block.
1008 * (reuse buffer, layer1 pointer becomes invalid)
1010 layer2_offset = layer1->phys_offset +
1011 HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
1012 layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer);
1017 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
1018 hammer_lock_ex(&hmp->blkmap_lock);
1019 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE))
1020 panic("CRC FAILED: LAYER2");
1021 hammer_unlock(&hmp->blkmap_lock);
1023 KKASSERT(layer2->zone == zone);
1025 bytes = layer2->bytes_free;
1027 if ((blockmap->next_offset ^ zone_offset) & ~HAMMER_LARGEBLOCK_MASK64)
1033 hammer_rel_buffer(buffer, 0);
1034 hammer_rel_volume(root_volume, 0);
1035 if (hammer_debug_general & 0x0800) {
1036 kprintf("hammer_blockmap_getfree: %016llx -> %d\n",
1037 zone_offset, bytes);
1044 * Lookup a blockmap offset.
1047 hammer_blockmap_lookup(hammer_mount_t hmp, hammer_off_t zone_offset,
1050 hammer_volume_t root_volume;
1051 hammer_blockmap_t freemap;
1052 struct hammer_blockmap_layer1 *layer1;
1053 struct hammer_blockmap_layer2 *layer2;
1054 hammer_buffer_t buffer = NULL;
1055 hammer_off_t layer1_offset;
1056 hammer_off_t layer2_offset;
1057 hammer_off_t result_offset;
1058 hammer_off_t base_off;
1059 hammer_reserve_t resv;
1063 * Calculate the zone-2 offset.
1065 zone = HAMMER_ZONE_DECODE(zone_offset);
1066 KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
1068 result_offset = (zone_offset & ~HAMMER_OFF_ZONE_MASK) |
1069 HAMMER_ZONE_RAW_BUFFER;
1072 * We can actually stop here, normal blockmaps are now direct-mapped
1073 * onto the freemap and so represent zone-2 addresses.
1075 if (hammer_verify_zone == 0) {
1077 return(result_offset);
1081 * Validate the allocation zone
1083 root_volume = hammer_get_root_volume(hmp, errorp);
1086 freemap = &hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
1087 KKASSERT(freemap->phys_offset != 0);
1092 layer1_offset = freemap->phys_offset +
1093 HAMMER_BLOCKMAP_LAYER1_OFFSET(zone_offset);
1094 layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer);
1097 KKASSERT(layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
1098 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
1099 hammer_lock_ex(&hmp->blkmap_lock);
1100 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE))
1101 panic("CRC FAILED: LAYER1");
1102 hammer_unlock(&hmp->blkmap_lock);
1106 * Dive layer 2, each entry represents a large-block.
1108 layer2_offset = layer1->phys_offset +
1109 HAMMER_BLOCKMAP_LAYER2_OFFSET(zone_offset);
1110 layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer);
1114 if (layer2->zone == 0) {
1115 base_off = (zone_offset & (~HAMMER_LARGEBLOCK_MASK64 & ~HAMMER_OFF_ZONE_MASK)) | HAMMER_ZONE_RAW_BUFFER;
1116 resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root,
1118 KKASSERT(resv && resv->zone == zone);
1120 } else if (layer2->zone != zone) {
1121 panic("hammer_blockmap_lookup: bad zone %d/%d\n",
1122 layer2->zone, zone);
1124 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
1125 hammer_lock_ex(&hmp->blkmap_lock);
1126 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE))
1127 panic("CRC FAILED: LAYER2");
1128 hammer_unlock(&hmp->blkmap_lock);
1133 hammer_rel_buffer(buffer, 0);
1134 hammer_rel_volume(root_volume, 0);
1135 if (hammer_debug_general & 0x0800) {
1136 kprintf("hammer_blockmap_lookup: %016llx -> %016llx\n",
1137 zone_offset, result_offset);
1139 return(result_offset);
1144 * Check space availability
1147 hammer_checkspace(hammer_mount_t hmp, int slop)
1149 const int in_size = sizeof(struct hammer_inode_data) +
1150 sizeof(union hammer_btree_elm);
1151 const int rec_size = (sizeof(union hammer_btree_elm) * 2);
1154 usedbytes = hmp->rsv_inodes * in_size +
1155 hmp->rsv_recs * rec_size +
1156 hmp->rsv_databytes +
1157 ((int64_t)hmp->rsv_fromdelay << HAMMER_LARGEBLOCK_BITS) +
1158 ((int64_t)hidirtybufspace << 2) +
1159 (slop << HAMMER_LARGEBLOCK_BITS);
1161 hammer_count_extra_space_used = usedbytes; /* debugging */
1163 if (hmp->copy_stat_freebigblocks >=
1164 (usedbytes >> HAMMER_LARGEBLOCK_BITS)) {