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.17 2008/06/10 00:40:31 dillon Exp $
42 static hammer_off_t hammer_find_hole(hammer_mount_t hmp,
43 hammer_holes_t holes, int bytes);
44 static void hammer_add_hole(hammer_mount_t hmp, hammer_holes_t holes,
45 hammer_off_t zone_offset, int bytes);
46 static void hammer_clean_holes(hammer_mount_t hmp, hammer_holes_t holes,
47 hammer_off_t base_offset);
48 static int hammer_res_rb_compare(hammer_reserve_t res1, hammer_reserve_t res2);
51 * Reserved big-blocks red-black tree support
53 RB_GENERATE2(hammer_res_rb_tree, hammer_reserve, rb_node,
54 hammer_res_rb_compare, hammer_off_t, zone_offset);
57 hammer_res_rb_compare(hammer_reserve_t res1, hammer_reserve_t res2)
59 if (res1->zone_offset < res2->zone_offset)
61 if (res1->zone_offset > res2->zone_offset)
67 * Allocate a big-block from the freemap and stuff it into the blockmap
71 hammer_blockmap_llalloc(hammer_transaction_t trans,
72 hammer_off_t zone_offset, int *errorp,
73 hammer_buffer_t buffer1, hammer_blockmap_layer1_t layer1,
74 hammer_buffer_t buffer2, hammer_blockmap_layer2_t layer2)
76 hammer_off_t zone2_offset;
78 zone2_offset = hammer_freemap_alloc(trans, zone_offset, errorp);
81 hammer_modify_buffer(trans, buffer1, layer1, sizeof(*layer1));
82 KKASSERT(layer1->blocks_free);
83 --layer1->blocks_free;
84 layer1->layer1_crc = crc32(layer1, HAMMER_LAYER1_CRCSIZE);
85 hammer_modify_buffer_done(buffer1);
86 hammer_modify_buffer(trans, buffer2, layer2, sizeof(*layer2));
87 bzero(layer2, sizeof(*layer2));
88 layer2->u.phys_offset = zone2_offset;
89 layer2->bytes_free = HAMMER_LARGEBLOCK_SIZE;
90 layer2->entry_crc = crc32(layer2, HAMMER_LAYER2_CRCSIZE);
91 hammer_modify_buffer_done(buffer2);
96 * Allocate bytes from a zone
99 hammer_blockmap_alloc(hammer_transaction_t trans, int zone,
100 int bytes, int *errorp)
103 hammer_volume_t root_volume;
104 hammer_blockmap_t rootmap;
105 hammer_reserve_t resv;
106 struct hammer_blockmap_layer1 *layer1;
107 struct hammer_blockmap_layer2 *layer2;
108 hammer_buffer_t buffer1 = NULL;
109 hammer_buffer_t buffer2 = NULL;
110 hammer_buffer_t buffer3 = NULL;
111 hammer_off_t tmp_offset;
112 hammer_off_t next_offset;
113 hammer_off_t result_offset;
114 hammer_off_t layer1_offset;
115 hammer_off_t layer2_offset;
122 * Deal with alignment and buffer-boundary issues.
124 * Be careful, certain primary alignments are used below to allocate
125 * new blockmap blocks.
127 bytes = (bytes + 15) & ~15;
128 KKASSERT(bytes > 0 && bytes <= HAMMER_BUFSIZE);
129 KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
132 * Try to use a known-free hole.
134 result_offset = hammer_find_hole(hmp, &trans->hmp->holes[zone], bytes);
137 hammer_blockmap_free(trans, result_offset, -bytes);
138 return(result_offset);
142 * Otherwise scan for space
144 root_volume = hammer_get_root_volume(hmp, errorp);
147 rootmap = &hmp->blockmap[zone];
148 KKASSERT(rootmap->phys_offset != 0);
149 KKASSERT(HAMMER_ZONE_DECODE(rootmap->phys_offset) ==
150 HAMMER_ZONE_RAW_BUFFER_INDEX);
151 KKASSERT(HAMMER_ZONE_DECODE(rootmap->alloc_offset) == zone);
152 KKASSERT(HAMMER_ZONE_DECODE(rootmap->next_offset) == zone);
154 lockmgr(&hmp->blockmap_lock, LK_EXCLUSIVE|LK_RETRY);
155 next_offset = rootmap->next_offset;
158 * The allocation request may not cross a buffer boundary.
160 tmp_offset = next_offset + bytes - 1;
161 if ((next_offset ^ tmp_offset) & ~HAMMER_BUFMASK64) {
162 skip_amount = HAMMER_BUFSIZE -
163 ((int)next_offset & HAMMER_BUFMASK);
164 hammer_add_hole(hmp, &hmp->holes[zone],
165 next_offset, skip_amount);
166 next_offset = tmp_offset & ~HAMMER_BUFMASK64;
170 * Dive layer 1. If we are starting a new layer 1 entry,
171 * allocate a layer 2 block for it.
173 layer1_offset = rootmap->phys_offset +
174 HAMMER_BLOCKMAP_LAYER1_OFFSET(next_offset);
175 layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer1);
176 KKASSERT(*errorp == 0);
177 KKASSERT(next_offset <= rootmap->alloc_offset);
180 * Check CRC if not allocating into uninitialized space
182 if ((next_offset != rootmap->alloc_offset) ||
183 (next_offset & HAMMER_BLOCKMAP_LAYER2_MASK)) {
184 if (layer1->layer1_crc != crc32(layer1,
185 HAMMER_LAYER1_CRCSIZE)) {
186 Debugger("CRC FAILED: LAYER1");
191 * Allocate layer2 backing store in layer1 if necessary. next_offset
192 * can skip to a bigblock boundary but alloc_offset is at least
193 * bigblock-aligned so that's ok.
195 if ((next_offset == rootmap->alloc_offset &&
196 (next_offset & HAMMER_BLOCKMAP_LAYER2_MASK) == 0) ||
197 layer1->phys_offset == HAMMER_BLOCKMAP_FREE
199 KKASSERT((next_offset & HAMMER_BLOCKMAP_LAYER2_MASK) == 0);
200 hammer_modify_buffer(trans, buffer1, layer1, sizeof(*layer1));
201 bzero(layer1, sizeof(*layer1));
202 layer1->phys_offset =
203 hammer_freemap_alloc(trans, next_offset, errorp);
204 layer1->blocks_free = HAMMER_BLOCKMAP_RADIX2;
205 layer1->layer1_crc = crc32(layer1, HAMMER_LAYER1_CRCSIZE);
206 hammer_modify_buffer_done(buffer1);
207 KKASSERT(*errorp == 0);
209 KKASSERT(layer1->phys_offset);
212 * If layer1 indicates no free blocks in layer2 and our alloc_offset
213 * is not in layer2, skip layer2 entirely.
215 if (layer1->blocks_free == 0 &&
216 ((next_offset ^ rootmap->alloc_offset) & ~HAMMER_BLOCKMAP_LAYER2_MASK) != 0) {
217 next_offset = (next_offset + HAMMER_BLOCKMAP_LAYER2_MASK) &
218 ~HAMMER_BLOCKMAP_LAYER2_MASK;
219 if (next_offset >= hmp->zone_limits[zone]) {
220 hkprintf("blockmap wrap1\n");
221 next_offset = HAMMER_ZONE_ENCODE(zone, 0);
222 if (++loops == 2) { /* XXX poor-man's */
232 * Dive layer 2, each entry represents a large-block.
234 layer2_offset = layer1->phys_offset +
235 HAMMER_BLOCKMAP_LAYER2_OFFSET(next_offset);
236 layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer2);
237 KKASSERT(*errorp == 0);
240 * Check CRC if not allocating into uninitialized space
242 if (next_offset != rootmap->alloc_offset ||
243 (next_offset & HAMMER_LARGEBLOCK_MASK64)) {
244 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
245 Debugger("CRC FAILED: LAYER2");
249 if ((next_offset & HAMMER_LARGEBLOCK_MASK64) == 0) {
251 * We are at the beginning of a new bigblock
253 resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root,
254 next_offset & ~HAMMER_LARGEBLOCK_MASK64);
258 } else if (next_offset == rootmap->alloc_offset ||
259 layer2->u.phys_offset == HAMMER_BLOCKMAP_FREE) {
261 * Allocate the bigblock in layer2 if diving into
262 * uninitialized space or if the block was previously
265 hammer_blockmap_llalloc(trans,
269 KKASSERT(layer2->u.phys_offset != HAMMER_BLOCKMAP_FREE);
270 } else if (layer2->bytes_free != HAMMER_LARGEBLOCK_SIZE) {
272 * We have encountered a block that is already
273 * partially allocated. We must skip this block.
276 next_offset += HAMMER_LARGEBLOCK_SIZE;
277 if (next_offset >= trans->hmp->zone_limits[zone]) {
278 next_offset = HAMMER_ZONE_ENCODE(zone, 0);
279 hkprintf("blockmap wrap2\n");
280 if (++loops == 2) { /* XXX poor-man's */
290 * We are appending within a bigblock. It is possible that
291 * the blockmap has been marked completely free via a prior
292 * pruning operation. We no longer reset the append index
293 * for that case because it compromises the UNDO by allowing
297 KKASSERT(layer2->u.phys_offset != HAMMER_BLOCKMAP_FREE);
301 hammer_modify_buffer(trans, buffer2, layer2, sizeof(*layer2));
302 layer2->bytes_free -= bytes;
303 layer2->entry_crc = crc32(layer2, HAMMER_LAYER2_CRCSIZE);
304 hammer_modify_buffer_done(buffer2);
305 KKASSERT(layer2->bytes_free >= 0);
308 * If we are allocating from the base of a new buffer we can avoid
309 * a disk read by calling hammer_bnew().
311 if ((next_offset & HAMMER_BUFMASK) == 0) {
312 hammer_bnew(trans->hmp, next_offset, errorp, &buffer3);
314 result_offset = next_offset;
317 * Process allocated result_offset
320 hammer_modify_volume(NULL, root_volume, NULL, 0);
322 if (result_offset == next_offset) {
323 rootmap->next_offset = next_offset + bytes;
325 rootmap->next_offset = next_offset;
328 rootmap->next_offset = next_offset;
330 if (rootmap->alloc_offset < rootmap->next_offset) {
331 rootmap->alloc_offset =
332 (rootmap->next_offset + HAMMER_LARGEBLOCK_MASK) &
333 ~HAMMER_LARGEBLOCK_MASK64;
335 hammer_modify_volume_done(root_volume);
336 lockmgr(&trans->hmp->blockmap_lock, LK_RELEASE);
342 hammer_rel_buffer(buffer1, 0);
344 hammer_rel_buffer(buffer2, 0);
346 hammer_rel_buffer(buffer3, 0);
347 hammer_rel_volume(root_volume, 0);
349 return(result_offset);
353 * Front-end blockmap reservation
355 * This code reserves bytes out of a blockmap without committing to any
356 * meta-data modifications, allowing the front-end to issue disk write I/O
357 * for large blocks of data without having to queue the BIOs to the back-end.
358 * If the reservation winds up not being used, for example due to a crash,
359 * the reblocker should eventually come along and clean it up.
361 * This code will attempt to assign free big-blocks to the blockmap to
362 * accomodate the request.
364 * If we return 0 a reservation was not possible and the caller must queue
365 * the I/O to the backend.
368 hammer_blockmap_reserve(hammer_mount_t hmp, int zone, int bytes,
369 hammer_off_t *zone_offp, int *errorp)
371 hammer_volume_t root_volume;
372 hammer_blockmap_t rootmap;
373 struct hammer_blockmap_layer1 *layer1;
374 struct hammer_blockmap_layer2 *layer2;
375 hammer_buffer_t buffer1 = NULL;
376 hammer_buffer_t buffer2 = NULL;
377 hammer_buffer_t buffer3 = NULL;
378 hammer_off_t tmp_offset;
379 hammer_off_t next_offset;
380 hammer_off_t layer1_offset;
381 hammer_off_t layer2_offset;
382 hammer_reserve_t resv;
389 KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
390 root_volume = hammer_get_root_volume(hmp, errorp);
393 rootmap = &hmp->blockmap[zone];
394 KKASSERT(rootmap->phys_offset != 0);
395 KKASSERT(HAMMER_ZONE_DECODE(rootmap->phys_offset) ==
396 HAMMER_ZONE_RAW_BUFFER_INDEX);
397 KKASSERT(HAMMER_ZONE_DECODE(rootmap->alloc_offset) == zone);
398 KKASSERT(HAMMER_ZONE_DECODE(rootmap->next_offset) == zone);
401 * Deal with alignment and buffer-boundary issues.
403 * Be careful, certain primary alignments are used below to allocate
404 * new blockmap blocks.
406 bytes = (bytes + 15) & ~15;
407 KKASSERT(bytes > 0 && bytes <= HAMMER_BUFSIZE);
409 lockmgr(&hmp->blockmap_lock, LK_EXCLUSIVE|LK_RETRY);
412 * Starting zoneX offset. The reservation code always wraps at the
413 * alloc_offset (the allocation code is allowed to go through to the
416 next_offset = rootmap->next_offset;
419 if (next_offset >= rootmap->alloc_offset) {
420 if (++loops == 2) { /* XXX poor-man's */
424 next_offset = HAMMER_ZONE_ENCODE(zone, 0);
428 * The allocation request may not cross a buffer boundary.
430 tmp_offset = next_offset + bytes - 1;
431 if ((next_offset ^ tmp_offset) & ~HAMMER_BUFMASK64) {
432 skip_amount = HAMMER_BUFSIZE -
433 ((int)next_offset & HAMMER_BUFMASK);
434 hammer_add_hole(hmp, &hmp->holes[zone],
435 next_offset, skip_amount);
436 next_offset = tmp_offset & ~HAMMER_BUFMASK64;
442 layer1_offset = rootmap->phys_offset +
443 HAMMER_BLOCKMAP_LAYER1_OFFSET(next_offset);
444 layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer1);
445 KKASSERT(*errorp == 0);
446 KKASSERT(next_offset <= rootmap->alloc_offset);
449 * Check CRC if not allocating into uninitialized space
451 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
452 Debugger("CRC FAILED: LAYER1");
454 KKASSERT(layer1->phys_offset);
457 * If layer1 indicates no free blocks in layer2 and our alloc_offset
458 * is not in layer2, skip layer2 entirely.
460 if (layer1->blocks_free == 0 &&
461 ((next_offset ^ rootmap->alloc_offset) & ~HAMMER_BLOCKMAP_LAYER2_MASK) != 0) {
462 next_offset = (next_offset + HAMMER_BLOCKMAP_LAYER2_MASK) &
463 ~HAMMER_BLOCKMAP_LAYER2_MASK;
468 * Dive layer 2, each entry represents a large-block.
470 layer2_offset = layer1->phys_offset +
471 HAMMER_BLOCKMAP_LAYER2_OFFSET(next_offset);
472 layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer2);
473 KKASSERT(*errorp == 0);
476 * Check CRC if not allocating into uninitialized space (which we
477 * aren't when reserving space).
479 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
480 Debugger("CRC FAILED: LAYER2");
484 * Acquire the related reservation structure. If it exists we can
485 * only use the bigblock if our current next_offset is already in
488 resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root,
489 next_offset & ~HAMMER_LARGEBLOCK_MASK64);
491 if ((next_offset & HAMMER_LARGEBLOCK_MASK64) == 0) {
493 * We are at the beginning of a new bigblock.
495 * (1) If the bigblock has already been reserved do not
496 * try to use it, skip it.
498 * (2) If the bigblock has not been allocated then allocate
501 * (3) If the bigblock is not completely free we have no
502 * visibility into what portions may have been allocated,
507 next_offset += HAMMER_LARGEBLOCK_SIZE;
509 } else if (layer2->u.phys_offset == HAMMER_BLOCKMAP_FREE) {
510 struct hammer_transaction trans;
512 hammer_start_transaction(&trans, hmp);
513 if (hammer_sync_lock_sh_try(&trans) == 0) {
514 hammer_blockmap_llalloc(&trans,
518 hammer_sync_unlock(&trans);
520 hammer_sync_lock_sh(&trans);
521 hammer_blockmap_llalloc(&trans,
525 hammer_sync_unlock(&trans);
526 /* *errorp = EDEADLK; */
528 hammer_done_transaction(&trans);
529 if (layer2->u.phys_offset == HAMMER_BLOCKMAP_FREE) {
533 } else if (layer2->bytes_free != HAMMER_LARGEBLOCK_SIZE) {
535 * We have encountered a block that is already
536 * partially allocated. We must skip this block.
538 next_offset += HAMMER_LARGEBLOCK_SIZE;
543 * We are appending within a bigblock. It is possible that
544 * the blockmap has been marked completely free via a prior
545 * pruning operation. We no longer reset the append index
546 * for that case because it compromises the UNDO by allowing
549 KKASSERT(layer2->u.phys_offset != HAMMER_BLOCKMAP_FREE);
550 KKASSERT(layer2->bytes_free >= HAMMER_LARGEBLOCK_SIZE - (int)(next_offset & HAMMER_LARGEBLOCK_MASK64));
554 * The reservation code does not modify layer2->bytes_free, it
555 * simply adjusts next_offset.
557 KKASSERT(layer2->bytes_free >= 0);
560 * If we are not reserving a whole buffer but are at the start of
561 * a new block, call hammer_bnew() to avoid a disk read.
563 * If we are reserving a whole buffer the caller will probably use
564 * a direct read, so do nothing.
566 if (bytes < HAMMER_BUFSIZE && (next_offset & HAMMER_BUFMASK) == 0) {
567 hammer_bnew(hmp, next_offset, errorp, &buffer3);
571 * Make the reservation
576 resv = kmalloc(sizeof(*resv), M_HAMMER, M_WAITOK|M_ZERO);
578 resv->zone_offset = next_offset & ~HAMMER_LARGEBLOCK_MASK64;
579 RB_INSERT(hammer_res_rb_tree, &hmp->rb_resv_root, resv);
580 ++hammer_count_reservations;
584 * Adjust our iterator and alloc_offset. The layer1 and layer2
585 * space beyond alloc_offset is uninitialized. alloc_offset must
586 * be big-block aligned.
590 hammer_modify_volume(NULL, root_volume, NULL, 0);
591 rootmap->next_offset = next_offset + bytes;
592 hammer_modify_volume_done(root_volume);
593 } else if (rootmap->next_offset != next_offset) {
594 hammer_modify_volume(NULL, root_volume, NULL, 0);
595 rootmap->next_offset = next_offset;
596 hammer_modify_volume_done(root_volume);
600 hammer_rel_buffer(buffer1, 0);
602 hammer_rel_buffer(buffer2, 0);
604 hammer_rel_buffer(buffer3, 0);
605 hammer_rel_volume(root_volume, 0);
606 lockmgr(&hmp->blockmap_lock, LK_RELEASE);
607 *zone_offp = next_offset;
613 * A record with a storage resolution calls this function when it is
614 * being freed. The storage may or may not have actually been allocated.
617 hammer_blockmap_reserve_complete(hammer_mount_t hmp, hammer_reserve_t resv)
619 KKASSERT(resv->refs > 0);
620 if (--resv->refs == 0) {
621 RB_REMOVE(hammer_res_rb_tree, &hmp->rb_resv_root, resv);
622 kfree(resv, M_HAMMER);
623 --hammer_count_reservations;
628 * Free (offset,bytes) in a zone.
630 * If bytes is negative we are actually allocating previously reserved
634 hammer_blockmap_free(hammer_transaction_t trans,
635 hammer_off_t bmap_off, int bytes)
638 hammer_volume_t root_volume;
639 hammer_reserve_t resv;
640 hammer_blockmap_t rootmap;
641 struct hammer_blockmap_layer1 *layer1;
642 struct hammer_blockmap_layer2 *layer2;
643 hammer_buffer_t buffer1 = NULL;
644 hammer_buffer_t buffer2 = NULL;
645 hammer_off_t layer1_offset;
646 hammer_off_t layer2_offset;
653 bytes = (bytes + 15) & ~15;
654 KKASSERT(bytes <= HAMMER_BUFSIZE);
655 KKASSERT(((bmap_off ^ (bmap_off + (bytes - 1))) &
656 ~HAMMER_LARGEBLOCK_MASK64) == 0);
658 bytes = -((-bytes + 15) & ~15);
659 KKASSERT(bytes >= -HAMMER_BUFSIZE);
661 zone = HAMMER_ZONE_DECODE(bmap_off);
662 KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
663 root_volume = hammer_get_root_volume(hmp, &error);
667 lockmgr(&hmp->blockmap_lock, LK_EXCLUSIVE|LK_RETRY);
669 rootmap = &hmp->blockmap[zone];
670 KKASSERT(rootmap->phys_offset != 0);
671 KKASSERT(HAMMER_ZONE_DECODE(rootmap->phys_offset) ==
672 HAMMER_ZONE_RAW_BUFFER_INDEX);
673 KKASSERT(HAMMER_ZONE_DECODE(rootmap->alloc_offset) == zone);
675 if (bmap_off >= rootmap->alloc_offset) {
676 panic("hammer_blockmap_lookup: %016llx beyond EOF %016llx",
677 bmap_off, rootmap->alloc_offset);
684 layer1_offset = rootmap->phys_offset +
685 HAMMER_BLOCKMAP_LAYER1_OFFSET(bmap_off);
686 layer1 = hammer_bread(hmp, layer1_offset, &error, &buffer1);
687 KKASSERT(error == 0);
688 KKASSERT(layer1->phys_offset);
689 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
690 Debugger("CRC FAILED: LAYER1");
694 * Dive layer 2, each entry represents a large-block.
696 layer2_offset = layer1->phys_offset +
697 HAMMER_BLOCKMAP_LAYER2_OFFSET(bmap_off);
698 layer2 = hammer_bread(hmp, layer2_offset, &error, &buffer2);
699 KKASSERT(error == 0);
700 KKASSERT(layer2->u.phys_offset);
701 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
702 Debugger("CRC FAILED: LAYER2");
705 hammer_modify_buffer(trans, buffer2, layer2, sizeof(*layer2));
706 layer2->bytes_free += bytes;
707 KKASSERT(layer2->bytes_free <= HAMMER_LARGEBLOCK_SIZE);
710 * If the big-block is free, return it to the free pool. The layer2
711 * infrastructure is left intact even if the entire layer2 becomes
714 * At the moment if our iterator is in a bigblock that becomes
715 * wholely free, we have to leave the block allocated and we cannot
716 * reset the iterator because there may be UNDOs on-disk that
717 * reference areas of that block and we cannot overwrite those areas.
719 if (layer2->bytes_free == HAMMER_LARGEBLOCK_SIZE) {
720 hammer_off_t base_off;
722 base_off = bmap_off & ~HAMMER_LARGEBLOCK_MASK64;
723 resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root,
728 * Portions of this block have been reserved, do
731 } else if ((rootmap->next_offset ^ bmap_off) &
732 ~HAMMER_LARGEBLOCK_MASK64) {
734 * Our iterator is not in the now-free big-block
735 * and we can release it.
737 hammer_clean_holes(hmp, &trans->hmp->holes[zone],
739 hammer_del_buffers(hmp, base_off,
740 layer2->u.phys_offset,
741 HAMMER_LARGEBLOCK_SIZE);
742 hammer_freemap_free(trans, layer2->u.phys_offset,
744 layer2->u.phys_offset = HAMMER_BLOCKMAP_FREE;
746 hammer_modify_buffer(trans, buffer1,
747 layer1, sizeof(*layer1));
748 ++layer1->blocks_free;
751 * This commented out code would release the layer2
752 * bigblock. We do not want to do this, at least
755 * This also may be incomplete.
757 if (layer1->blocks_free == HAMMER_BLOCKMAP_RADIX2) {
759 trans, layer1->phys_offset,
760 bmap_off & ~HAMMER_BLOCKMAP_LAYER2_MASK,
762 layer1->phys_offset = HAMMER_BLOCKMAP_FREE;
765 layer1->layer1_crc = crc32(layer1,
766 HAMMER_LAYER1_CRCSIZE);
767 hammer_modify_buffer_done(buffer1);
771 * This commented out code would reset the iterator,
772 * which we cannot do at the moment as it could cause
773 * new allocations to overwrite deleted data still
774 * subject to undo on reboot.
776 hammer_modify_volume(trans, root_volume,
778 rootmap->next_offset &= ~HAMMER_LARGEBLOCK_MASK64;
779 hammer_modify_volume_done(root_volume);
783 layer2->entry_crc = crc32(layer2, HAMMER_LAYER2_CRCSIZE);
784 hammer_modify_buffer_done(buffer2);
786 lockmgr(&hmp->blockmap_lock, LK_RELEASE);
789 hammer_rel_buffer(buffer1, 0);
791 hammer_rel_buffer(buffer2, 0);
792 hammer_rel_volume(root_volume, 0);
796 * Return the number of free bytes in the big-block containing the
797 * specified blockmap offset.
800 hammer_blockmap_getfree(hammer_mount_t hmp, hammer_off_t bmap_off,
801 int *curp, int *errorp)
803 hammer_volume_t root_volume;
804 hammer_blockmap_t rootmap;
805 struct hammer_blockmap_layer1 *layer1;
806 struct hammer_blockmap_layer2 *layer2;
807 hammer_buffer_t buffer = NULL;
808 hammer_off_t layer1_offset;
809 hammer_off_t layer2_offset;
813 zone = HAMMER_ZONE_DECODE(bmap_off);
814 KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
815 root_volume = hammer_get_root_volume(hmp, errorp);
820 rootmap = &hmp->blockmap[zone];
821 KKASSERT(rootmap->phys_offset != 0);
822 KKASSERT(HAMMER_ZONE_DECODE(rootmap->phys_offset) ==
823 HAMMER_ZONE_RAW_BUFFER_INDEX);
824 KKASSERT(HAMMER_ZONE_DECODE(rootmap->alloc_offset) == zone);
826 if (bmap_off >= rootmap->alloc_offset) {
827 panic("hammer_blockmap_lookup: %016llx beyond EOF %016llx",
828 bmap_off, rootmap->alloc_offset);
837 layer1_offset = rootmap->phys_offset +
838 HAMMER_BLOCKMAP_LAYER1_OFFSET(bmap_off);
839 layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer);
840 KKASSERT(*errorp == 0);
841 KKASSERT(layer1->phys_offset);
842 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
843 Debugger("CRC FAILED: LAYER1");
847 * Dive layer 2, each entry represents a large-block.
849 layer2_offset = layer1->phys_offset +
850 HAMMER_BLOCKMAP_LAYER2_OFFSET(bmap_off);
851 layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer);
852 KKASSERT(*errorp == 0);
853 KKASSERT(layer2->u.phys_offset);
854 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
855 Debugger("CRC FAILED: LAYER2");
858 bytes = layer2->bytes_free;
860 if ((rootmap->next_offset ^ bmap_off) & ~HAMMER_LARGEBLOCK_MASK64)
866 hammer_rel_buffer(buffer, 0);
867 hammer_rel_volume(root_volume, 0);
868 if (hammer_debug_general & 0x0800) {
869 kprintf("hammer_blockmap_getfree: %016llx -> %d\n",
877 * Lookup a blockmap offset.
880 hammer_blockmap_lookup(hammer_mount_t hmp, hammer_off_t bmap_off, int *errorp)
882 hammer_volume_t root_volume;
883 hammer_blockmap_t rootmap;
884 struct hammer_blockmap_layer1 *layer1;
885 struct hammer_blockmap_layer2 *layer2;
886 hammer_buffer_t buffer = NULL;
887 hammer_off_t layer1_offset;
888 hammer_off_t layer2_offset;
889 hammer_off_t result_offset;
892 zone = HAMMER_ZONE_DECODE(bmap_off);
893 KKASSERT(zone >= HAMMER_ZONE_BTREE_INDEX && zone < HAMMER_MAX_ZONES);
894 root_volume = hammer_get_root_volume(hmp, errorp);
897 rootmap = &hmp->blockmap[zone];
898 KKASSERT(rootmap->phys_offset != 0);
899 KKASSERT(HAMMER_ZONE_DECODE(rootmap->phys_offset) ==
900 HAMMER_ZONE_RAW_BUFFER_INDEX);
901 KKASSERT(HAMMER_ZONE_DECODE(rootmap->alloc_offset) == zone);
903 if (bmap_off >= rootmap->alloc_offset) {
904 panic("hammer_blockmap_lookup: %016llx beyond EOF %016llx",
905 bmap_off, rootmap->alloc_offset);
913 layer1_offset = rootmap->phys_offset +
914 HAMMER_BLOCKMAP_LAYER1_OFFSET(bmap_off);
915 layer1 = hammer_bread(hmp, layer1_offset, errorp, &buffer);
916 KKASSERT(*errorp == 0);
917 KKASSERT(layer1->phys_offset);
918 if (layer1->layer1_crc != crc32(layer1, HAMMER_LAYER1_CRCSIZE)) {
919 Debugger("CRC FAILED: LAYER1");
923 * Dive layer 2, each entry represents a large-block.
925 layer2_offset = layer1->phys_offset +
926 HAMMER_BLOCKMAP_LAYER2_OFFSET(bmap_off);
927 layer2 = hammer_bread(hmp, layer2_offset, errorp, &buffer);
929 KKASSERT(*errorp == 0);
930 KKASSERT(layer2->u.phys_offset);
931 if (layer2->entry_crc != crc32(layer2, HAMMER_LAYER2_CRCSIZE)) {
932 Debugger("CRC FAILED: LAYER2");
935 result_offset = layer2->u.phys_offset +
936 (bmap_off & HAMMER_LARGEBLOCK_MASK64);
939 hammer_rel_buffer(buffer, 0);
940 hammer_rel_volume(root_volume, 0);
941 if (hammer_debug_general & 0x0800) {
942 kprintf("hammer_blockmap_lookup: %016llx -> %016llx\n",
943 bmap_off, result_offset);
945 return(result_offset);
948 /************************************************************************
949 * IN-CORE TRACKING OF ALLOCATION HOLES *
950 ************************************************************************
952 * This is a temporary shim in need of a more permanent solution.
954 * As we allocate space holes are created due to having to align to a new
955 * 16K buffer when an allocation would otherwise cross the buffer boundary.
956 * These holes are recorded here and used to fullfill smaller requests as
957 * much as possible. Only a limited number of holes are recorded and these
958 * functions operate somewhat like a heuristic, where information is allowed
963 hammer_init_holes(hammer_mount_t hmp, hammer_holes_t holes)
965 TAILQ_INIT(&holes->list);
970 hammer_free_holes(hammer_mount_t hmp, hammer_holes_t holes)
974 while ((hole = TAILQ_FIRST(&holes->list)) != NULL) {
975 TAILQ_REMOVE(&holes->list, hole, entry);
977 hammer_blockmap_reserve_complete(hmp, hole->resv);
980 kfree(hole, M_HAMMER);
986 * Attempt to locate a hole with sufficient free space to accomodate the
987 * requested allocation. Return the offset or 0 if no hole could be found.
990 hammer_find_hole(hammer_mount_t hmp, hammer_holes_t holes, int bytes)
993 hammer_off_t result_off = 0;
995 TAILQ_FOREACH(hole, &holes->list, entry) {
996 if (bytes <= hole->bytes) {
997 result_off = hole->zone_offset;
998 hole->zone_offset += bytes;
999 hole->bytes -= bytes;
1007 * If a newly created hole is reasonably sized then record it. We only
1008 * keep track of a limited number of holes. Lost holes are recovered by
1011 * offset is a zone-N offset.
1014 hammer_add_hole(hammer_mount_t hmp, hammer_holes_t holes,
1015 hammer_off_t zone_offset, int bytes)
1018 hammer_reserve_t resv;
1024 * Allocate or reuse a hole structure
1026 if (holes->count < HAMMER_MAX_HOLES) {
1027 hole = kmalloc(sizeof(*hole), M_HAMMER, M_WAITOK);
1030 hole = TAILQ_FIRST(&holes->list);
1031 TAILQ_REMOVE(&holes->list, hole, entry);
1033 hammer_blockmap_reserve_complete(hmp, hole->resv);
1039 * Associate the structure with the appropriate reservation so the
1040 * bigblock does not get freed or reused while we have cached holes,
1043 hole->zone_offset = zone_offset;
1044 hole->bytes = bytes;
1046 zone_offset &= ~HAMMER_LARGEBLOCK_MASK64;
1048 resv = RB_LOOKUP(hammer_res_rb_tree, &hmp->rb_resv_root, zone_offset);
1050 resv = kmalloc(sizeof(*resv), M_HAMMER, M_WAITOK|M_ZERO);
1051 resv->zone_offset = zone_offset;
1053 RB_INSERT(hammer_res_rb_tree, &hmp->rb_resv_root, resv);
1054 ++hammer_count_reservations;
1059 TAILQ_INSERT_TAIL(&holes->list, hole, entry);
1063 * Clean out any holes cached for the bigblock we are about to release back
1067 hammer_clean_holes(hammer_mount_t hmp, hammer_holes_t holes,
1068 hammer_off_t base_offset)
1073 TAILQ_FOREACH(hole, &holes->list, entry) {
1074 if ((hole->zone_offset & ~HAMMER_LARGEBLOCK_MASK64) ==
1076 TAILQ_REMOVE(&holes->list, hole, entry);
1078 hammer_blockmap_reserve_complete(hmp,
1083 kfree(hole, M_HAMMER);