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_freemap.c,v 1.10 2008/05/04 09:06:45 dillon Exp $
38 * HAMMER freemap - bigblock allocator. The freemap is a 2-layer blockmap
39 * with one layer2 entry for each big-block in the filesystem. Big blocks
42 * Our allocator is fairly straightforward, we just iterate through available
43 * blocks looking for a free one. We shortcut the iteration based on
44 * layer1 availability.
50 hammer_freemap_alloc(hammer_transaction_t trans, hammer_off_t owner,
53 hammer_volume_ondisk_t ondisk;
54 hammer_off_t layer1_offset;
55 hammer_off_t layer2_offset;
56 hammer_off_t result_offset;
57 hammer_blockmap_t blockmap;
58 hammer_buffer_t buffer1 = NULL;
59 hammer_buffer_t buffer2 = NULL;
60 struct hammer_blockmap_layer1 *layer1;
61 struct hammer_blockmap_layer2 *layer2;
66 ondisk = trans->rootvol->ondisk;
68 hammer_lock_ex(&trans->hmp->free_lock);
70 blockmap = &trans->hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
71 result_offset = blockmap->next_offset;
72 vol_no = HAMMER_VOL_DECODE(result_offset);
74 layer1_offset = blockmap->phys_offset +
75 HAMMER_BLOCKMAP_LAYER1_OFFSET(result_offset);
77 layer1 = hammer_bread(trans->hmp, layer1_offset, errorp, &buffer1);
78 if (layer1->phys_offset == HAMMER_BLOCKMAP_UNAVAIL) {
80 * End-of-volume, try next volume.
84 if (vol_no >= trans->hmp->nvolumes)
86 result_offset = HAMMER_ENCODE_RAW_BUFFER(vol_no, 0);
87 if (vol_no == 0 && ++loops == 2) {
93 layer2_offset = layer1->phys_offset +
94 HAMMER_BLOCKMAP_LAYER2_OFFSET(result_offset);
95 layer2 = hammer_bread(trans->hmp, layer2_offset, errorp,
97 if (layer2->u.owner == HAMMER_BLOCKMAP_FREE) {
98 hammer_modify_buffer(trans, buffer2,
99 layer2, sizeof(*layer2));
100 layer2->u.owner = owner &
101 ~HAMMER_LARGEBLOCK_MASK64;
102 hammer_modify_buffer_done(buffer2);
103 hammer_modify_buffer(trans, buffer1,
104 layer1, sizeof(*layer1));
105 --layer1->blocks_free;
106 hammer_modify_buffer_done(buffer1);
107 hammer_modify_volume_field(trans,
109 vol0_stat_freebigblocks);
110 --ondisk->vol0_stat_freebigblocks;
111 hammer_modify_volume_done(trans->rootvol);
114 if (layer1->blocks_free == 0 ||
115 layer2->u.owner == HAMMER_BLOCKMAP_UNAVAIL) {
117 * layer2 has no free blocks remaining,
118 * skip to the next layer.
120 result_offset = (result_offset + HAMMER_BLOCKMAP_LAYER2_MASK) & ~HAMMER_BLOCKMAP_LAYER2_MASK;
121 if (HAMMER_VOL_DECODE(result_offset) != vol_no)
124 result_offset += HAMMER_LARGEBLOCK_SIZE;
125 if (HAMMER_VOL_DECODE(result_offset) != vol_no)
130 hammer_modify_volume(trans, trans->rootvol, NULL, 0);
131 blockmap->next_offset = result_offset + HAMMER_LARGEBLOCK_SIZE;
132 hammer_modify_volume_done(trans->rootvol);
134 hammer_unlock(&trans->hmp->free_lock);
136 hammer_rel_buffer(buffer1, 0);
138 hammer_rel_buffer(buffer2, 0);
139 return(result_offset);
143 hammer_freemap_free(hammer_transaction_t trans, hammer_off_t phys_offset,
144 hammer_off_t owner, int *errorp)
146 hammer_volume_ondisk_t ondisk;
147 hammer_off_t layer1_offset;
148 hammer_off_t layer2_offset;
149 hammer_blockmap_t blockmap;
150 hammer_buffer_t buffer1 = NULL;
151 hammer_buffer_t buffer2 = NULL;
152 struct hammer_blockmap_layer1 *layer1;
153 struct hammer_blockmap_layer2 *layer2;
155 KKASSERT((phys_offset & HAMMER_LARGEBLOCK_MASK64) == 0);
157 hammer_uncache_buffer(trans->hmp, phys_offset);
159 ondisk = trans->rootvol->ondisk;
161 blockmap = &trans->hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
162 layer1_offset = blockmap->phys_offset +
163 HAMMER_BLOCKMAP_LAYER1_OFFSET(phys_offset);
164 layer1 = hammer_bread(trans->hmp, layer1_offset, errorp, &buffer1);
166 KKASSERT(layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
168 layer2_offset = layer1->phys_offset +
169 HAMMER_BLOCKMAP_LAYER2_OFFSET(phys_offset);
170 layer2 = hammer_bread(trans->hmp, layer2_offset, errorp, &buffer2);
172 KKASSERT(layer2->u.owner == (owner & ~HAMMER_LARGEBLOCK_MASK64));
173 hammer_modify_buffer(trans, buffer1, layer1, sizeof(*layer1));
174 ++layer1->blocks_free;
175 hammer_modify_buffer_done(buffer1);
176 hammer_modify_buffer(trans, buffer2, layer2, sizeof(*layer2));
177 layer2->u.owner = HAMMER_BLOCKMAP_FREE;
178 hammer_modify_buffer_done(buffer2);
180 hammer_modify_volume_field(trans, trans->rootvol,
181 vol0_stat_freebigblocks);
182 ++ondisk->vol0_stat_freebigblocks;
183 hammer_modify_volume_done(trans->rootvol);
186 hammer_rel_buffer(buffer1, 0);
188 hammer_rel_buffer(buffer2, 0);