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.14 2008/06/08 18:16:26 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 * Backend big-block allocation
53 hammer_freemap_alloc(hammer_transaction_t trans, hammer_off_t owner,
56 hammer_volume_ondisk_t ondisk;
57 hammer_off_t layer1_offset;
58 hammer_off_t layer2_offset;
59 hammer_off_t result_offset;
60 hammer_blockmap_t blockmap;
61 hammer_buffer_t buffer1 = NULL;
62 hammer_buffer_t buffer2 = NULL;
63 struct hammer_blockmap_layer1 *layer1;
64 struct hammer_blockmap_layer2 *layer2;
69 ondisk = trans->rootvol->ondisk;
71 hammer_lock_ex(&trans->hmp->free_lock);
73 blockmap = &trans->hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
74 result_offset = blockmap->next_offset;
75 vol_no = HAMMER_VOL_DECODE(result_offset);
77 layer1_offset = blockmap->phys_offset +
78 HAMMER_BLOCKMAP_LAYER1_OFFSET(result_offset);
80 layer1 = hammer_bread(trans->hmp, layer1_offset, errorp, &buffer1);
81 if (layer1->phys_offset == HAMMER_BLOCKMAP_UNAVAIL) {
83 * End-of-volume, try next volume.
87 if (vol_no >= trans->hmp->nvolumes)
89 result_offset = HAMMER_ENCODE_RAW_BUFFER(vol_no, 0);
90 if (vol_no == 0 && ++loops == 2) {
96 layer2_offset = layer1->phys_offset +
97 HAMMER_BLOCKMAP_LAYER2_OFFSET(result_offset);
98 layer2 = hammer_bread(trans->hmp, layer2_offset, errorp,
100 if (layer2->u.owner == HAMMER_BLOCKMAP_FREE) {
101 hammer_modify_buffer(trans, buffer2,
102 layer2, sizeof(*layer2));
103 layer2->u.owner = owner &
104 ~HAMMER_LARGEBLOCK_MASK64;
105 hammer_modify_buffer_done(buffer2);
106 hammer_modify_buffer(trans, buffer1,
107 layer1, sizeof(*layer1));
108 --layer1->blocks_free;
109 hammer_modify_buffer_done(buffer1);
110 hammer_modify_volume_field(trans,
112 vol0_stat_freebigblocks);
113 --ondisk->vol0_stat_freebigblocks;
114 trans->hmp->copy_stat_freebigblocks =
115 ondisk->vol0_stat_freebigblocks;
116 hammer_modify_volume_done(trans->rootvol);
119 if (layer1->blocks_free == 0 ||
120 layer2->u.owner == HAMMER_BLOCKMAP_UNAVAIL) {
122 * layer2 has no free blocks remaining,
123 * skip to the next layer.
125 result_offset = (result_offset + HAMMER_BLOCKMAP_LAYER2) & ~HAMMER_BLOCKMAP_LAYER2_MASK;
126 if (HAMMER_VOL_DECODE(result_offset) != vol_no)
129 result_offset += HAMMER_LARGEBLOCK_SIZE;
130 if (HAMMER_VOL_DECODE(result_offset) != vol_no)
135 hammer_modify_volume(trans, trans->rootvol, NULL, 0);
136 blockmap->next_offset = result_offset + HAMMER_LARGEBLOCK_SIZE;
137 hammer_modify_volume_done(trans->rootvol);
139 hammer_unlock(&trans->hmp->free_lock);
141 hammer_rel_buffer(buffer1, 0);
143 hammer_rel_buffer(buffer2, 0);
144 return(result_offset);
148 * Backend big-block free
151 hammer_freemap_free(hammer_transaction_t trans, hammer_off_t phys_offset,
152 hammer_off_t owner, int *errorp)
154 hammer_volume_ondisk_t ondisk;
155 hammer_off_t layer1_offset;
156 hammer_off_t layer2_offset;
157 hammer_blockmap_t blockmap;
158 hammer_buffer_t buffer1 = NULL;
159 hammer_buffer_t buffer2 = NULL;
160 struct hammer_blockmap_layer1 *layer1;
161 struct hammer_blockmap_layer2 *layer2;
163 KKASSERT((phys_offset & HAMMER_LARGEBLOCK_MASK64) == 0);
166 ondisk = trans->rootvol->ondisk;
168 hammer_lock_ex(&trans->hmp->free_lock);
170 blockmap = &trans->hmp->blockmap[HAMMER_ZONE_FREEMAP_INDEX];
171 layer1_offset = blockmap->phys_offset +
172 HAMMER_BLOCKMAP_LAYER1_OFFSET(phys_offset);
173 layer1 = hammer_bread(trans->hmp, layer1_offset, errorp, &buffer1);
175 KKASSERT(layer1->phys_offset != HAMMER_BLOCKMAP_UNAVAIL);
177 layer2_offset = layer1->phys_offset +
178 HAMMER_BLOCKMAP_LAYER2_OFFSET(phys_offset);
179 layer2 = hammer_bread(trans->hmp, layer2_offset, errorp, &buffer2);
181 KKASSERT(layer2->u.owner == (owner & ~HAMMER_LARGEBLOCK_MASK64));
182 hammer_modify_buffer(trans, buffer1, layer1, sizeof(*layer1));
183 ++layer1->blocks_free;
184 hammer_modify_buffer_done(buffer1);
185 hammer_modify_buffer(trans, buffer2, layer2, sizeof(*layer2));
186 layer2->u.owner = HAMMER_BLOCKMAP_FREE;
187 hammer_modify_buffer_done(buffer2);
189 hammer_modify_volume_field(trans, trans->rootvol,
190 vol0_stat_freebigblocks);
191 ++ondisk->vol0_stat_freebigblocks;
192 hammer_modify_volume_done(trans->rootvol);
193 trans->hmp->copy_stat_freebigblocks = ondisk->vol0_stat_freebigblocks;
195 hammer_unlock(&trans->hmp->free_lock);
198 hammer_rel_buffer(buffer1, 0);
200 hammer_rel_buffer(buffer2, 0);
204 * Check space availability
207 hammer_checkspace(hammer_mount_t hmp)
209 const int in_size = sizeof(struct hammer_inode_data) +
210 sizeof(union hammer_btree_elm);
211 const int rec_size = (sizeof(union hammer_btree_elm) * 2);
212 const int blkconv = HAMMER_LARGEBLOCK_SIZE / HAMMER_BUFSIZE;
213 const int limit_inodes = HAMMER_LARGEBLOCK_SIZE / in_size;
214 const int limit_recs = HAMMER_LARGEBLOCK_SIZE / rec_size;
218 * Quick and very dirty, not even using the right units (bigblocks
219 * vs 16K buffers), but this catches almost everything.
221 if (hmp->copy_stat_freebigblocks >= hmp->rsv_databufs + 8 &&
222 hmp->rsv_inodes < limit_inodes &&
223 hmp->rsv_recs < limit_recs &&
224 hmp->rsv_databytes < HAMMER_LARGEBLOCK_SIZE) {
229 * Do a more involved check
231 usedbigblocks = (hmp->rsv_inodes * in_size / HAMMER_LARGEBLOCK_SIZE) +
232 (hmp->rsv_recs * rec_size / HAMMER_LARGEBLOCK_SIZE) +
233 hmp->rsv_databufs / blkconv + 6;
234 if (hmp->copy_stat_freebigblocks >= usedbigblocks)