15c23d7f1SMatthew Dillon /*
268b321c1SMatthew Dillon * Copyright (c) 2011-2018 The DragonFly Project. All rights reserved.
35c23d7f1SMatthew Dillon *
45c23d7f1SMatthew Dillon * This code is derived from software contributed to The DragonFly Project
55c23d7f1SMatthew Dillon * by Matthew Dillon <dillon@dragonflybsd.org>
65c23d7f1SMatthew Dillon * by Venkatesh Srinivas <vsrinivas@dragonflybsd.org>
75c23d7f1SMatthew Dillon *
85c23d7f1SMatthew Dillon * Redistribution and use in source and binary forms, with or without
95c23d7f1SMatthew Dillon * modification, are permitted provided that the following conditions
105c23d7f1SMatthew Dillon * are met:
115c23d7f1SMatthew Dillon *
125c23d7f1SMatthew Dillon * 1. Redistributions of source code must retain the above copyright
135c23d7f1SMatthew Dillon * notice, this list of conditions and the following disclaimer.
145c23d7f1SMatthew Dillon * 2. Redistributions in binary form must reproduce the above copyright
155c23d7f1SMatthew Dillon * notice, this list of conditions and the following disclaimer in
165c23d7f1SMatthew Dillon * the documentation and/or other materials provided with the
175c23d7f1SMatthew Dillon * distribution.
185c23d7f1SMatthew Dillon * 3. Neither the name of The DragonFly Project nor the names of its
195c23d7f1SMatthew Dillon * contributors may be used to endorse or promote products derived
205c23d7f1SMatthew Dillon * from this software without specific, prior written permission.
215c23d7f1SMatthew Dillon *
225c23d7f1SMatthew Dillon * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
235c23d7f1SMatthew Dillon * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
245c23d7f1SMatthew Dillon * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
255c23d7f1SMatthew Dillon * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
265c23d7f1SMatthew Dillon * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
275c23d7f1SMatthew Dillon * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
285c23d7f1SMatthew Dillon * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
295c23d7f1SMatthew Dillon * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
305c23d7f1SMatthew Dillon * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
315c23d7f1SMatthew Dillon * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
325c23d7f1SMatthew Dillon * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
335c23d7f1SMatthew Dillon * SUCH DAMAGE.
345c23d7f1SMatthew Dillon */
355c23d7f1SMatthew Dillon #include <sys/param.h>
365c23d7f1SMatthew Dillon #include <sys/systm.h>
375c23d7f1SMatthew Dillon #include <sys/kernel.h>
385c23d7f1SMatthew Dillon #include <sys/proc.h>
395c23d7f1SMatthew Dillon #include <sys/mount.h>
405c23d7f1SMatthew Dillon
415c23d7f1SMatthew Dillon #include "hammer2.h"
425c23d7f1SMatthew Dillon
438138a154SMatthew Dillon #define FREEMAP_DEBUG 0
448138a154SMatthew Dillon
4591abd410SMatthew Dillon struct hammer2_fiterate {
4691abd410SMatthew Dillon hammer2_off_t bpref;
4791abd410SMatthew Dillon hammer2_off_t bnext;
4891abd410SMatthew Dillon int loops;
4965cacacfSMatthew Dillon int relaxed;
5091abd410SMatthew Dillon };
5191abd410SMatthew Dillon
5291abd410SMatthew Dillon typedef struct hammer2_fiterate hammer2_fiterate_t;
5391abd410SMatthew Dillon
54c603b86bSMatthew Dillon static int hammer2_freemap_try_alloc(hammer2_chain_t **parentp,
55e2163f5bSMatthew Dillon hammer2_blockref_t *bref, int radix,
56e2163f5bSMatthew Dillon hammer2_fiterate_t *iter, hammer2_tid_t mtid);
57c603b86bSMatthew Dillon static void hammer2_freemap_init(hammer2_dev_t *hmp,
58a5913bdfSMatthew Dillon hammer2_key_t key, hammer2_chain_t *chain);
59c603b86bSMatthew Dillon static int hammer2_bmap_alloc(hammer2_dev_t *hmp,
6091abd410SMatthew Dillon hammer2_bmap_data_t *bmap, uint16_t class,
61aff72996SMatthew Dillon int n, int sub_key, int radix, hammer2_key_t *basep);
62c603b86bSMatthew Dillon static int hammer2_freemap_iterate(hammer2_chain_t **parentp,
63c603b86bSMatthew Dillon hammer2_chain_t **chainp,
6491abd410SMatthew Dillon hammer2_fiterate_t *iter);
651a7cfe5aSMatthew Dillon
661a7cfe5aSMatthew Dillon /*
671a7cfe5aSMatthew Dillon * Calculate the device offset for the specified FREEMAP_NODE or FREEMAP_LEAF
681a7cfe5aSMatthew Dillon * bref. Return a combined media offset and physical size radix. Freemap
691a7cfe5aSMatthew Dillon * chains use fixed storage offsets in the 4MB reserved area at the
70641a6901STomohiro Kusumi * beginning of each 1GB zone.
711a7cfe5aSMatthew Dillon *
72641a6901STomohiro Kusumi * Rotate between eight possibilities. Theoretically this means we have seven
731a7cfe5aSMatthew Dillon * good freemaps in case of a crash which we can use as a base for the fixup
741a7cfe5aSMatthew Dillon * scan at mount-time.
751a7cfe5aSMatthew Dillon */
761a7cfe5aSMatthew Dillon static
771a7cfe5aSMatthew Dillon int
hammer2_freemap_reserve(hammer2_chain_t * chain,int radix)78c603b86bSMatthew Dillon hammer2_freemap_reserve(hammer2_chain_t *chain, int radix)
791a7cfe5aSMatthew Dillon {
80623d43d4SMatthew Dillon hammer2_blockref_t *bref = &chain->bref;
811a7cfe5aSMatthew Dillon hammer2_off_t off;
82a3fd5153SMatthew Dillon int index;
835cebbe36SMatthew Dillon int index_inc;
841a7cfe5aSMatthew Dillon size_t bytes;
851a7cfe5aSMatthew Dillon
861a7cfe5aSMatthew Dillon /*
875cebbe36SMatthew Dillon * Physical allocation size.
881a7cfe5aSMatthew Dillon */
895cebbe36SMatthew Dillon bytes = (size_t)1 << radix;
901a7cfe5aSMatthew Dillon
911a7cfe5aSMatthew Dillon /*
92a71db85dSMatthew Dillon * Calculate block selection index 0..7 of current block. If this
93a71db85dSMatthew Dillon * is the first allocation of the block (verses a modification of an
94a71db85dSMatthew Dillon * existing block), we use index 0, otherwise we use the next rotating
95a71db85dSMatthew Dillon * index.
961a7cfe5aSMatthew Dillon */
971a7cfe5aSMatthew Dillon if ((bref->data_off & ~HAMMER2_OFF_MASK_RADIX) == 0) {
98a3fd5153SMatthew Dillon index = 0;
991a7cfe5aSMatthew Dillon } else {
1001a7cfe5aSMatthew Dillon off = bref->data_off & ~HAMMER2_OFF_MASK_RADIX &
101cef11e5aSTomohiro Kusumi HAMMER2_SEGMASK;
1021a7cfe5aSMatthew Dillon off = off / HAMMER2_PBUFSIZE;
103a3fd5153SMatthew Dillon KKASSERT(off >= HAMMER2_ZONE_FREEMAP_00 &&
1043148f677SMatthew Dillon off < HAMMER2_ZONE_FREEMAP_END);
1055031809dSMatthew Dillon index = (int)(off - HAMMER2_ZONE_FREEMAP_00) /
1065031809dSMatthew Dillon HAMMER2_ZONE_FREEMAP_INC;
1073148f677SMatthew Dillon KKASSERT(index >= 0 && index < HAMMER2_NFREEMAPS);
1083148f677SMatthew Dillon if (++index == HAMMER2_NFREEMAPS)
109a71db85dSMatthew Dillon index = 0;
110623d43d4SMatthew Dillon }
111623d43d4SMatthew Dillon
1121a7cfe5aSMatthew Dillon /*
1131a7cfe5aSMatthew Dillon * Calculate the block offset of the reserved block. This will
1141a7cfe5aSMatthew Dillon * point into the 4MB reserved area at the base of the appropriate
1151a7cfe5aSMatthew Dillon * 2GB zone, once added to the FREEMAP_x selection above.
1161a7cfe5aSMatthew Dillon */
1175cebbe36SMatthew Dillon index_inc = index * HAMMER2_ZONE_FREEMAP_INC;
1185cebbe36SMatthew Dillon
1191a7cfe5aSMatthew Dillon switch(bref->keybits) {
1205cebbe36SMatthew Dillon /* case HAMMER2_FREEMAP_LEVEL6_RADIX: not applicable */
12118a3521fSTomohiro Kusumi case HAMMER2_FREEMAP_LEVEL5_RADIX: /* 4EB */
1225cebbe36SMatthew Dillon KKASSERT(bref->type == HAMMER2_BREF_TYPE_FREEMAP_NODE);
1235cebbe36SMatthew Dillon KKASSERT(bytes == HAMMER2_FREEMAP_LEVELN_PSIZE);
1245cebbe36SMatthew Dillon off = H2FMBASE(bref->key, HAMMER2_FREEMAP_LEVEL5_RADIX) +
1255cebbe36SMatthew Dillon (index_inc + HAMMER2_ZONE_FREEMAP_00 +
1265cebbe36SMatthew Dillon HAMMER2_ZONEFM_LEVEL5) * HAMMER2_PBUFSIZE;
1275cebbe36SMatthew Dillon break;
12818a3521fSTomohiro Kusumi case HAMMER2_FREEMAP_LEVEL4_RADIX: /* 16PB */
1291a7cfe5aSMatthew Dillon KKASSERT(bref->type == HAMMER2_BREF_TYPE_FREEMAP_NODE);
1301a7cfe5aSMatthew Dillon KKASSERT(bytes == HAMMER2_FREEMAP_LEVELN_PSIZE);
131a3fd5153SMatthew Dillon off = H2FMBASE(bref->key, HAMMER2_FREEMAP_LEVEL4_RADIX) +
1325cebbe36SMatthew Dillon (index_inc + HAMMER2_ZONE_FREEMAP_00 +
133ba8a9be0SMatthew Dillon HAMMER2_ZONEFM_LEVEL4) * HAMMER2_PBUFSIZE;
1341a7cfe5aSMatthew Dillon break;
13518a3521fSTomohiro Kusumi case HAMMER2_FREEMAP_LEVEL3_RADIX: /* 64TB */
1361a7cfe5aSMatthew Dillon KKASSERT(bref->type == HAMMER2_BREF_TYPE_FREEMAP_NODE);
1371a7cfe5aSMatthew Dillon KKASSERT(bytes == HAMMER2_FREEMAP_LEVELN_PSIZE);
138a3fd5153SMatthew Dillon off = H2FMBASE(bref->key, HAMMER2_FREEMAP_LEVEL3_RADIX) +
1395cebbe36SMatthew Dillon (index_inc + HAMMER2_ZONE_FREEMAP_00 +
140ba8a9be0SMatthew Dillon HAMMER2_ZONEFM_LEVEL3) * HAMMER2_PBUFSIZE;
1411a7cfe5aSMatthew Dillon break;
14218a3521fSTomohiro Kusumi case HAMMER2_FREEMAP_LEVEL2_RADIX: /* 256GB */
1431a7cfe5aSMatthew Dillon KKASSERT(bref->type == HAMMER2_BREF_TYPE_FREEMAP_NODE);
1441a7cfe5aSMatthew Dillon KKASSERT(bytes == HAMMER2_FREEMAP_LEVELN_PSIZE);
145a3fd5153SMatthew Dillon off = H2FMBASE(bref->key, HAMMER2_FREEMAP_LEVEL2_RADIX) +
1465cebbe36SMatthew Dillon (index_inc + HAMMER2_ZONE_FREEMAP_00 +
147ba8a9be0SMatthew Dillon HAMMER2_ZONEFM_LEVEL2) * HAMMER2_PBUFSIZE;
1481a7cfe5aSMatthew Dillon break;
14918a3521fSTomohiro Kusumi case HAMMER2_FREEMAP_LEVEL1_RADIX: /* 1GB */
15093f3933aSMatthew Dillon KKASSERT(bref->type == HAMMER2_BREF_TYPE_FREEMAP_LEAF);
1511a7cfe5aSMatthew Dillon KKASSERT(bytes == HAMMER2_FREEMAP_LEVELN_PSIZE);
152a3fd5153SMatthew Dillon off = H2FMBASE(bref->key, HAMMER2_FREEMAP_LEVEL1_RADIX) +
1535cebbe36SMatthew Dillon (index_inc + HAMMER2_ZONE_FREEMAP_00 +
154ba8a9be0SMatthew Dillon HAMMER2_ZONEFM_LEVEL1) * HAMMER2_PBUFSIZE;
1551a7cfe5aSMatthew Dillon break;
1561a7cfe5aSMatthew Dillon default:
1571a7cfe5aSMatthew Dillon panic("freemap: bad radix(2) %p %d\n", bref, bref->keybits);
1581a7cfe5aSMatthew Dillon /* NOT REACHED */
159a3fd5153SMatthew Dillon off = (hammer2_off_t)-1;
1601a7cfe5aSMatthew Dillon break;
1611a7cfe5aSMatthew Dillon }
1621a7cfe5aSMatthew Dillon bref->data_off = off | radix;
1638138a154SMatthew Dillon #if FREEMAP_DEBUG
1648138a154SMatthew Dillon kprintf("FREEMAP BLOCK TYPE %d %016jx/%d DATA_OFF=%016jx\n",
1658138a154SMatthew Dillon bref->type, bref->key, bref->keybits, bref->data_off);
166623d43d4SMatthew Dillon #endif
1671a7cfe5aSMatthew Dillon return (0);
1681a7cfe5aSMatthew Dillon }
1691a7cfe5aSMatthew Dillon
1705c23d7f1SMatthew Dillon /*
1711a7cfe5aSMatthew Dillon * Normal freemap allocator
1721a7cfe5aSMatthew Dillon *
1731a7cfe5aSMatthew Dillon * Use available hints to allocate space using the freemap. Create missing
1741a7cfe5aSMatthew Dillon * freemap infrastructure on-the-fly as needed (including marking initial
1751a7cfe5aSMatthew Dillon * allocations using the iterator as allocated, instantiating new 2GB zones,
1761a7cfe5aSMatthew Dillon * and dealing with the end-of-media edge case).
1771a7cfe5aSMatthew Dillon *
1788d920968STomohiro Kusumi * bpref is only used as a heuristic to determine locality of reference.
179da0cdd33SMatthew Dillon *
180da0cdd33SMatthew Dillon * This function is a NOP if bytes is 0.
1811a7cfe5aSMatthew Dillon */
1821a7cfe5aSMatthew Dillon int
hammer2_freemap_alloc(hammer2_chain_t * chain,size_t bytes)183c603b86bSMatthew Dillon hammer2_freemap_alloc(hammer2_chain_t *chain, size_t bytes)
1841a7cfe5aSMatthew Dillon {
185506bd6d1SMatthew Dillon hammer2_dev_t *hmp = chain->hmp;
186623d43d4SMatthew Dillon hammer2_blockref_t *bref = &chain->bref;
1871a7cfe5aSMatthew Dillon hammer2_chain_t *parent;
188e2163f5bSMatthew Dillon hammer2_tid_t mtid;
1891a7cfe5aSMatthew Dillon int radix;
1901a7cfe5aSMatthew Dillon int error;
19191abd410SMatthew Dillon unsigned int hindex;
19291abd410SMatthew Dillon hammer2_fiterate_t iter;
1931a7cfe5aSMatthew Dillon
194da0cdd33SMatthew Dillon /*
195da0cdd33SMatthew Dillon * If allocating or downsizing to zero we just get rid of whatever
196da0cdd33SMatthew Dillon * data_off we had.
197da0cdd33SMatthew Dillon */
198da0cdd33SMatthew Dillon if (bytes == 0) {
199da0cdd33SMatthew Dillon chain->bref.data_off = 0;
200da0cdd33SMatthew Dillon return 0;
201da0cdd33SMatthew Dillon }
202da0cdd33SMatthew Dillon
20365c894ffSMatthew Dillon KKASSERT(hmp->spmp);
204e2163f5bSMatthew Dillon mtid = hammer2_trans_sub(hmp->spmp);
205e2163f5bSMatthew Dillon
2061a7cfe5aSMatthew Dillon /*
2071a7cfe5aSMatthew Dillon * Validate the allocation size. It must be a power of 2.
20893f3933aSMatthew Dillon *
20993f3933aSMatthew Dillon * For now require that the caller be aware of the minimum
21093f3933aSMatthew Dillon * allocation (1K).
2111a7cfe5aSMatthew Dillon */
2121a7cfe5aSMatthew Dillon radix = hammer2_getradix(bytes);
2131a7cfe5aSMatthew Dillon KKASSERT((size_t)1 << radix == bytes);
2141a7cfe5aSMatthew Dillon
2151a7cfe5aSMatthew Dillon if (bref->type == HAMMER2_BREF_TYPE_FREEMAP_NODE ||
2161a7cfe5aSMatthew Dillon bref->type == HAMMER2_BREF_TYPE_FREEMAP_LEAF) {
21750456506SMatthew Dillon /*
21850456506SMatthew Dillon * Freemap blocks themselves are assigned from the reserve
21950456506SMatthew Dillon * area, not allocated from the freemap.
22050456506SMatthew Dillon */
221c603b86bSMatthew Dillon error = hammer2_freemap_reserve(chain, radix);
222470dad14SMatthew Dillon
22350456506SMatthew Dillon return error;
2241a7cfe5aSMatthew Dillon }
2251a7cfe5aSMatthew Dillon
22650456506SMatthew Dillon KKASSERT(bytes >= HAMMER2_ALLOC_MIN && bytes <= HAMMER2_ALLOC_MAX);
22791abd410SMatthew Dillon
22801eabad4SMatthew Dillon /*
22991abd410SMatthew Dillon * Heuristic tracking index. We would like one for each distinct
23091abd410SMatthew Dillon * bref type if possible. heur_freemap[] has room for two classes
23191abd410SMatthew Dillon * for each type. At a minimum we have to break-up our heuristic
23291abd410SMatthew Dillon * by device block sizes.
23391abd410SMatthew Dillon */
234ee78054eSTomohiro Kusumi hindex = HAMMER2_PBUFRADIX - HAMMER2_LBUFRADIX;
23591abd410SMatthew Dillon KKASSERT(hindex < HAMMER2_FREEMAP_HEUR_NRADIX);
23691abd410SMatthew Dillon hindex += bref->type * HAMMER2_FREEMAP_HEUR_NRADIX;
23791abd410SMatthew Dillon hindex &= HAMMER2_FREEMAP_HEUR_TYPES * HAMMER2_FREEMAP_HEUR_NRADIX - 1;
2383f01ebaaSMatthew Dillon KKASSERT(hindex < HAMMER2_FREEMAP_HEUR_SIZE);
23991abd410SMatthew Dillon
24091abd410SMatthew Dillon iter.bpref = hmp->heur_freemap[hindex];
24165cacacfSMatthew Dillon iter.relaxed = hmp->freemap_relaxed;
2421a7cfe5aSMatthew Dillon
2431a7cfe5aSMatthew Dillon /*
2441a7cfe5aSMatthew Dillon * Make sure bpref is in-bounds. It's ok if bpref covers a zone's
2451a7cfe5aSMatthew Dillon * reserved area, the try code will iterate past it.
2461a7cfe5aSMatthew Dillon */
2470b738157STomohiro Kusumi if (iter.bpref > hmp->total_size)
2480b738157STomohiro Kusumi iter.bpref = hmp->total_size - 1;
2491a7cfe5aSMatthew Dillon
2501a7cfe5aSMatthew Dillon /*
2511a7cfe5aSMatthew Dillon * Iterate the freemap looking for free space before and after.
2521a7cfe5aSMatthew Dillon */
2531a7cfe5aSMatthew Dillon parent = &hmp->fchain;
254e513e77eSMatthew Dillon hammer2_chain_ref(parent);
2551a7cfe5aSMatthew Dillon hammer2_chain_lock(parent, HAMMER2_RESOLVE_ALWAYS);
25665cacacfSMatthew Dillon error = HAMMER2_ERROR_EAGAIN;
25791abd410SMatthew Dillon iter.bnext = iter.bpref;
25891abd410SMatthew Dillon iter.loops = 0;
2591a7cfe5aSMatthew Dillon
26065cacacfSMatthew Dillon while (error == HAMMER2_ERROR_EAGAIN) {
261e2163f5bSMatthew Dillon error = hammer2_freemap_try_alloc(&parent, bref, radix,
262e2163f5bSMatthew Dillon &iter, mtid);
2631a7cfe5aSMatthew Dillon }
26465cacacfSMatthew Dillon hmp->freemap_relaxed |= iter.relaxed; /* heuristical, SMP race ok */
26591abd410SMatthew Dillon hmp->heur_freemap[hindex] = iter.bnext;
2661a7cfe5aSMatthew Dillon hammer2_chain_unlock(parent);
267e513e77eSMatthew Dillon hammer2_chain_drop(parent);
2681a7cfe5aSMatthew Dillon
2691a7cfe5aSMatthew Dillon return (error);
2701a7cfe5aSMatthew Dillon }
2711a7cfe5aSMatthew Dillon
2721a7cfe5aSMatthew Dillon static int
hammer2_freemap_try_alloc(hammer2_chain_t ** parentp,hammer2_blockref_t * bref,int radix,hammer2_fiterate_t * iter,hammer2_tid_t mtid)273c603b86bSMatthew Dillon hammer2_freemap_try_alloc(hammer2_chain_t **parentp,
2741a7cfe5aSMatthew Dillon hammer2_blockref_t *bref, int radix,
275e2163f5bSMatthew Dillon hammer2_fiterate_t *iter, hammer2_tid_t mtid)
2761a7cfe5aSMatthew Dillon {
277506bd6d1SMatthew Dillon hammer2_dev_t *hmp = (*parentp)->hmp;
2781a7cfe5aSMatthew Dillon hammer2_off_t l0size;
27993f3933aSMatthew Dillon hammer2_off_t l1size;
28093f3933aSMatthew Dillon hammer2_off_t l1mask;
2811897c66eSMatthew Dillon hammer2_key_t key_dummy;
2821a7cfe5aSMatthew Dillon hammer2_chain_t *chain;
2831a7cfe5aSMatthew Dillon hammer2_off_t key;
2841a7cfe5aSMatthew Dillon size_t bytes;
28591abd410SMatthew Dillon uint16_t class;
286c8c0a18aSMatthew Dillon int error;
2871a7cfe5aSMatthew Dillon
2881a7cfe5aSMatthew Dillon /*
2898d920968STomohiro Kusumi * Calculate the number of bytes being allocated.
2901a7cfe5aSMatthew Dillon */
2911a7cfe5aSMatthew Dillon bytes = (size_t)1 << radix;
292ee78054eSTomohiro Kusumi class = (bref->type << 8) | HAMMER2_PBUFRADIX;
293a98aa0b0SMatthew Dillon
2941a7cfe5aSMatthew Dillon /*
29593f3933aSMatthew Dillon * Lookup the level1 freemap chain, creating and initializing one
2961a7cfe5aSMatthew Dillon * if necessary. Intermediate levels will be created automatically
2971a7cfe5aSMatthew Dillon * when necessary by hammer2_chain_create().
2981a7cfe5aSMatthew Dillon */
29991abd410SMatthew Dillon key = H2FMBASE(iter->bnext, HAMMER2_FREEMAP_LEVEL1_RADIX);
3004e47c34eSTomohiro Kusumi l0size = HAMMER2_FREEMAP_LEVEL0_SIZE;
3014e47c34eSTomohiro Kusumi l1size = HAMMER2_FREEMAP_LEVEL1_SIZE;
30293f3933aSMatthew Dillon l1mask = l1size - 1;
3031a7cfe5aSMatthew Dillon
3041897c66eSMatthew Dillon chain = hammer2_chain_lookup(parentp, &key_dummy, key, key + l1mask,
305c8c0a18aSMatthew Dillon &error,
3061a7cfe5aSMatthew Dillon HAMMER2_LOOKUP_ALWAYS |
307b8ba9690SMatthew Dillon HAMMER2_LOOKUP_MATCHIND);
308623d43d4SMatthew Dillon
3091a7cfe5aSMatthew Dillon if (chain == NULL) {
3101a7cfe5aSMatthew Dillon /*
3111a7cfe5aSMatthew Dillon * Create the missing leaf, be sure to initialize
3121a7cfe5aSMatthew Dillon * the auxillary freemap tracking information in
3131a7cfe5aSMatthew Dillon * the bref.check.freemap structure.
3141a7cfe5aSMatthew Dillon */
3151a7cfe5aSMatthew Dillon #if 0
31693f3933aSMatthew Dillon kprintf("freemap create L1 @ %016jx bpref %016jx\n",
31791abd410SMatthew Dillon key, iter->bpref);
3181a7cfe5aSMatthew Dillon #endif
319ecfe89b8SMatthew Dillon error = hammer2_chain_create(parentp, &chain, NULL, hmp->spmp,
320ecfe89b8SMatthew Dillon HAMMER2_METH_DEFAULT,
32193f3933aSMatthew Dillon key, HAMMER2_FREEMAP_LEVEL1_RADIX,
3221a7cfe5aSMatthew Dillon HAMMER2_BREF_TYPE_FREEMAP_LEAF,
323b3659de2SMatthew Dillon HAMMER2_FREEMAP_LEVELN_PSIZE,
3243f01ebaaSMatthew Dillon mtid, 0, 0);
3250924b3f8SMatthew Dillon KKASSERT(error == 0);
3261a7cfe5aSMatthew Dillon if (error == 0) {
3273f01ebaaSMatthew Dillon hammer2_chain_modify(chain, mtid, 0, 0);
32893f3933aSMatthew Dillon bzero(&chain->data->bmdata[0],
32993f3933aSMatthew Dillon HAMMER2_FREEMAP_LEVELN_PSIZE);
33093f3933aSMatthew Dillon chain->bref.check.freemap.bigmask = (uint32_t)-1;
33193f3933aSMatthew Dillon chain->bref.check.freemap.avail = l1size;
33293f3933aSMatthew Dillon /* bref.methods should already be inherited */
3331a7cfe5aSMatthew Dillon
334c603b86bSMatthew Dillon hammer2_freemap_init(hmp, key, chain);
3351a7cfe5aSMatthew Dillon }
336b93cc2e0SMatthew Dillon } else if (chain->error) {
337b93cc2e0SMatthew Dillon /*
338b93cc2e0SMatthew Dillon * Error during lookup.
339b93cc2e0SMatthew Dillon */
340b93cc2e0SMatthew Dillon kprintf("hammer2_freemap_try_alloc: %016jx: error %s\n",
341b93cc2e0SMatthew Dillon (intmax_t)bref->data_off,
342b93cc2e0SMatthew Dillon hammer2_error_str(chain->error));
34365cacacfSMatthew Dillon error = HAMMER2_ERROR_EIO;
3445cebbe36SMatthew Dillon } else if ((chain->bref.check.freemap.bigmask &
3455cebbe36SMatthew Dillon ((size_t)1 << radix)) == 0) {
3461a7cfe5aSMatthew Dillon /*
3471a7cfe5aSMatthew Dillon * Already flagged as not having enough space
3481a7cfe5aSMatthew Dillon */
34965cacacfSMatthew Dillon error = HAMMER2_ERROR_ENOSPC;
3501a7cfe5aSMatthew Dillon } else {
3511a7cfe5aSMatthew Dillon /*
3521a7cfe5aSMatthew Dillon * Modify existing chain to setup for adjustment.
3531a7cfe5aSMatthew Dillon */
3543f01ebaaSMatthew Dillon hammer2_chain_modify(chain, mtid, 0, 0);
3551a7cfe5aSMatthew Dillon }
3561a7cfe5aSMatthew Dillon
3571a7cfe5aSMatthew Dillon /*
35830b0abf3SMatthew Dillon * Scan 4MB entries.
3591a7cfe5aSMatthew Dillon */
36093f3933aSMatthew Dillon if (error == 0) {
36193f3933aSMatthew Dillon hammer2_bmap_data_t *bmap;
36293f3933aSMatthew Dillon hammer2_key_t base_key;
36393f3933aSMatthew Dillon int count;
36493f3933aSMatthew Dillon int start;
36593f3933aSMatthew Dillon int n;
3661a7cfe5aSMatthew Dillon
36710136ab6SMatthew Dillon KKASSERT(chain->bref.type == HAMMER2_BREF_TYPE_FREEMAP_LEAF);
36891abd410SMatthew Dillon start = (int)((iter->bnext - key) >>
36991abd410SMatthew Dillon HAMMER2_FREEMAP_LEVEL0_RADIX);
37093f3933aSMatthew Dillon KKASSERT(start >= 0 && start < HAMMER2_FREEMAP_COUNT);
3713f01ebaaSMatthew Dillon hammer2_chain_modify(chain, mtid, 0, 0);
3721a7cfe5aSMatthew Dillon
37365cacacfSMatthew Dillon error = HAMMER2_ERROR_ENOSPC;
37493f3933aSMatthew Dillon for (count = 0; count < HAMMER2_FREEMAP_COUNT; ++count) {
375271568b1SMatthew Dillon int availchk;
376271568b1SMatthew Dillon
37793f3933aSMatthew Dillon if (start + count >= HAMMER2_FREEMAP_COUNT &&
37893f3933aSMatthew Dillon start - count < 0) {
37993f3933aSMatthew Dillon break;
38093f3933aSMatthew Dillon }
381271568b1SMatthew Dillon
382271568b1SMatthew Dillon /*
38365cacacfSMatthew Dillon * Calculate bmap pointer from thart starting index
38465cacacfSMatthew Dillon * forwards.
385271568b1SMatthew Dillon *
386271568b1SMatthew Dillon * NOTE: bmap pointer is invalid if n >= FREEMAP_COUNT.
387271568b1SMatthew Dillon */
38893f3933aSMatthew Dillon n = start + count;
38993f3933aSMatthew Dillon bmap = &chain->data->bmdata[n];
390271568b1SMatthew Dillon
391271568b1SMatthew Dillon if (n >= HAMMER2_FREEMAP_COUNT) {
392271568b1SMatthew Dillon availchk = 0;
393271568b1SMatthew Dillon } else if (bmap->avail) {
394271568b1SMatthew Dillon availchk = 1;
395271568b1SMatthew Dillon } else if (radix < HAMMER2_FREEMAP_BLOCK_RADIX &&
396271568b1SMatthew Dillon (bmap->linear & HAMMER2_FREEMAP_BLOCK_MASK)) {
397271568b1SMatthew Dillon availchk = 1;
398271568b1SMatthew Dillon } else {
399271568b1SMatthew Dillon availchk = 0;
400271568b1SMatthew Dillon }
401271568b1SMatthew Dillon
40265cacacfSMatthew Dillon /*
40365cacacfSMatthew Dillon * Try to allocate from a matching freemap class
40465cacacfSMatthew Dillon * superblock. If we are in relaxed mode we allocate
40565cacacfSMatthew Dillon * from any freemap class superblock.
40665cacacfSMatthew Dillon */
407271568b1SMatthew Dillon if (availchk &&
40865cacacfSMatthew Dillon (bmap->class == 0 || bmap->class == class ||
40965cacacfSMatthew Dillon iter->relaxed)) {
41093f3933aSMatthew Dillon base_key = key + n * l0size;
411c603b86bSMatthew Dillon error = hammer2_bmap_alloc(hmp, bmap,
412aff72996SMatthew Dillon class, n,
413aff72996SMatthew Dillon (int)bref->key,
414aff72996SMatthew Dillon radix,
41591abd410SMatthew Dillon &base_key);
41665cacacfSMatthew Dillon if (error != HAMMER2_ERROR_ENOSPC) {
41793f3933aSMatthew Dillon key = base_key;
41893f3933aSMatthew Dillon break;
41993f3933aSMatthew Dillon }
42093f3933aSMatthew Dillon }
421271568b1SMatthew Dillon
422271568b1SMatthew Dillon /*
423c4fd5af3SMatthew Dillon * Calculate bmap pointer from the starting index
42465cacacfSMatthew Dillon * backwards (locality).
42565cacacfSMatthew Dillon *
426271568b1SMatthew Dillon * Must recalculate after potentially having called
427271568b1SMatthew Dillon * hammer2_bmap_alloc() above in case chain was
428271568b1SMatthew Dillon * reallocated.
429271568b1SMatthew Dillon *
430271568b1SMatthew Dillon * NOTE: bmap pointer is invalid if n < 0.
431271568b1SMatthew Dillon */
43293f3933aSMatthew Dillon n = start - count;
43393f3933aSMatthew Dillon bmap = &chain->data->bmdata[n];
434271568b1SMatthew Dillon if (n < 0) {
435271568b1SMatthew Dillon availchk = 0;
436271568b1SMatthew Dillon } else if (bmap->avail) {
437271568b1SMatthew Dillon availchk = 1;
438271568b1SMatthew Dillon } else if (radix < HAMMER2_FREEMAP_BLOCK_RADIX &&
439271568b1SMatthew Dillon (bmap->linear & HAMMER2_FREEMAP_BLOCK_MASK)) {
440271568b1SMatthew Dillon availchk = 1;
441271568b1SMatthew Dillon } else {
442271568b1SMatthew Dillon availchk = 0;
443271568b1SMatthew Dillon }
444271568b1SMatthew Dillon
44565cacacfSMatthew Dillon /*
44665cacacfSMatthew Dillon * Try to allocate from a matching freemap class
44765cacacfSMatthew Dillon * superblock. If we are in relaxed mode we allocate
44865cacacfSMatthew Dillon * from any freemap class superblock.
44965cacacfSMatthew Dillon */
450271568b1SMatthew Dillon if (availchk &&
45165cacacfSMatthew Dillon (bmap->class == 0 || bmap->class == class ||
45265cacacfSMatthew Dillon iter->relaxed)) {
45393f3933aSMatthew Dillon base_key = key + n * l0size;
454c603b86bSMatthew Dillon error = hammer2_bmap_alloc(hmp, bmap,
455aff72996SMatthew Dillon class, n,
456aff72996SMatthew Dillon (int)bref->key,
457aff72996SMatthew Dillon radix,
45891abd410SMatthew Dillon &base_key);
45965cacacfSMatthew Dillon if (error != HAMMER2_ERROR_ENOSPC) {
46093f3933aSMatthew Dillon key = base_key;
46193f3933aSMatthew Dillon break;
46293f3933aSMatthew Dillon }
46393f3933aSMatthew Dillon }
46493f3933aSMatthew Dillon }
46565cacacfSMatthew Dillon
46665cacacfSMatthew Dillon /*
46765cacacfSMatthew Dillon * We only know for sure that we can clear the bitmap bit
468c4fd5af3SMatthew Dillon * if we scanned the entire array (start == 0) in relaxed
469c4fd5af3SMatthew Dillon * mode.
47065cacacfSMatthew Dillon */
471c4fd5af3SMatthew Dillon if (error == HAMMER2_ERROR_ENOSPC &&
472c4fd5af3SMatthew Dillon start == 0 &&
473c4fd5af3SMatthew Dillon iter->relaxed)
474c4fd5af3SMatthew Dillon {
4755cebbe36SMatthew Dillon chain->bref.check.freemap.bigmask &=
4765cebbe36SMatthew Dillon (uint32_t)~((size_t)1 << radix);
4775cebbe36SMatthew Dillon }
47893f3933aSMatthew Dillon /* XXX also scan down from original count */
47993f3933aSMatthew Dillon }
4801a7cfe5aSMatthew Dillon
4811a7cfe5aSMatthew Dillon if (error == 0) {
4821a7cfe5aSMatthew Dillon /*
4831a7cfe5aSMatthew Dillon * Assert validity. Must be beyond the static allocator used
4841a7cfe5aSMatthew Dillon * by newfs_hammer2 (and thus also beyond the aux area),
4851a7cfe5aSMatthew Dillon * not go past the volume size, and must not be in the
4861a7cfe5aSMatthew Dillon * reserved segment area for a zone.
4871a7cfe5aSMatthew Dillon */
4881a7cfe5aSMatthew Dillon KKASSERT(key >= hmp->voldata.allocator_beg &&
4890b738157STomohiro Kusumi key + bytes <= hmp->total_size);
4901a7cfe5aSMatthew Dillon KKASSERT((key & HAMMER2_ZONE_MASK64) >= HAMMER2_ZONE_SEG);
4911a7cfe5aSMatthew Dillon bref->data_off = key | radix;
4920b8efeb7SMatthew Dillon
4930b8efeb7SMatthew Dillon /*
4940b8efeb7SMatthew Dillon * Record dedupability. The dedup bits are cleared
4950b8efeb7SMatthew Dillon * when bulkfree transitions the freemap from 11->10,
4960b8efeb7SMatthew Dillon * and asserted to be clear on the 10->00 transition.
4970b8efeb7SMatthew Dillon *
4980b8efeb7SMatthew Dillon * We must record the bitmask with the chain locked
4990b8efeb7SMatthew Dillon * at the time we set the allocation bits to avoid
5000b8efeb7SMatthew Dillon * racing a bulkfree.
5010b8efeb7SMatthew Dillon */
5020b8efeb7SMatthew Dillon if (bref->type == HAMMER2_BREF_TYPE_DATA)
5030b8efeb7SMatthew Dillon hammer2_io_dedup_set(hmp, bref);
5041a7cfe5aSMatthew Dillon #if 0
50593f3933aSMatthew Dillon kprintf("alloc cp=%p %016jx %016jx using %016jx\n",
5061a7cfe5aSMatthew Dillon chain,
50793f3933aSMatthew Dillon bref->key, bref->data_off, chain->bref.data_off);
5081a7cfe5aSMatthew Dillon #endif
50965cacacfSMatthew Dillon } else if (error == HAMMER2_ERROR_ENOSPC) {
5101a7cfe5aSMatthew Dillon /*
51191abd410SMatthew Dillon * Return EAGAIN with next iteration in iter->bnext, or
5121a7cfe5aSMatthew Dillon * return ENOSPC if the allocation map has been exhausted.
5131a7cfe5aSMatthew Dillon */
514c603b86bSMatthew Dillon error = hammer2_freemap_iterate(parentp, &chain, iter);
5151a7cfe5aSMatthew Dillon }
5161a7cfe5aSMatthew Dillon
5171a7cfe5aSMatthew Dillon /*
5181a7cfe5aSMatthew Dillon * Cleanup
5191a7cfe5aSMatthew Dillon */
520e513e77eSMatthew Dillon if (chain) {
5211a7cfe5aSMatthew Dillon hammer2_chain_unlock(chain);
522e513e77eSMatthew Dillon hammer2_chain_drop(chain);
523e513e77eSMatthew Dillon }
5241a7cfe5aSMatthew Dillon return (error);
5251a7cfe5aSMatthew Dillon }
5261a7cfe5aSMatthew Dillon
52793f3933aSMatthew Dillon /*
52893f3933aSMatthew Dillon * Allocate (1<<radix) bytes from the bmap whos base data offset is (*basep).
52993f3933aSMatthew Dillon *
53093f3933aSMatthew Dillon * If the linear iterator is mid-block we use it directly (the bitmap should
531aff72996SMatthew Dillon * already be marked allocated), otherwise we search for a block in the
532aff72996SMatthew Dillon * bitmap that fits the allocation request.
53393f3933aSMatthew Dillon *
53493f3933aSMatthew Dillon * A partial bitmap allocation sets the minimum bitmap granularity (16KB)
53593f3933aSMatthew Dillon * to fully allocated and adjusts the linear allocator to allow the
53693f3933aSMatthew Dillon * remaining space to be allocated.
537aff72996SMatthew Dillon *
538aff72996SMatthew Dillon * sub_key is the lower 32 bits of the chain->bref.key for the chain whos
539aff72996SMatthew Dillon * bref is being allocated. If the radix represents an allocation >= 16KB
540aff72996SMatthew Dillon * (aka HAMMER2_FREEMAP_BLOCK_RADIX) we try to use this key to select the
541aff72996SMatthew Dillon * blocks directly out of the bmap.
54293f3933aSMatthew Dillon */
54393f3933aSMatthew Dillon static
54493f3933aSMatthew Dillon int
hammer2_bmap_alloc(hammer2_dev_t * hmp,hammer2_bmap_data_t * bmap,uint16_t class,int n,int sub_key,int radix,hammer2_key_t * basep)545c603b86bSMatthew Dillon hammer2_bmap_alloc(hammer2_dev_t *hmp, hammer2_bmap_data_t *bmap,
546aff72996SMatthew Dillon uint16_t class, int n, int sub_key,
547aff72996SMatthew Dillon int radix, hammer2_key_t *basep)
54893f3933aSMatthew Dillon {
54993f3933aSMatthew Dillon size_t size;
550271568b1SMatthew Dillon size_t bgsize;
55193f3933aSMatthew Dillon int bmradix;
5525cebbe36SMatthew Dillon hammer2_bitmap_t bmmask;
55393f3933aSMatthew Dillon int offset;
55493f3933aSMatthew Dillon int i;
55593f3933aSMatthew Dillon int j;
55693f3933aSMatthew Dillon
55793f3933aSMatthew Dillon /*
55893f3933aSMatthew Dillon * Take into account 2-bits per block when calculating bmradix.
55993f3933aSMatthew Dillon */
56093f3933aSMatthew Dillon size = (size_t)1 << radix;
56191abd410SMatthew Dillon
56293f3933aSMatthew Dillon if (radix <= HAMMER2_FREEMAP_BLOCK_RADIX) {
56393f3933aSMatthew Dillon bmradix = 2;
56493f3933aSMatthew Dillon /* (16K) 2 bits per allocation block */
56593f3933aSMatthew Dillon } else {
5665cebbe36SMatthew Dillon bmradix = (hammer2_bitmap_t)2 <<
5675cebbe36SMatthew Dillon (radix - HAMMER2_FREEMAP_BLOCK_RADIX);
568*e12df3bcSTomohiro Kusumi /* (32K-64K) 4, 8 bits per allocation block */
56993f3933aSMatthew Dillon }
57093f3933aSMatthew Dillon
57193f3933aSMatthew Dillon /*
57291abd410SMatthew Dillon * Use the linear iterator to pack small allocations, otherwise
57391abd410SMatthew Dillon * fall-back to finding a free 16KB chunk. The linear iterator
57491abd410SMatthew Dillon * is only valid when *NOT* on a freemap chunking boundary (16KB).
57591abd410SMatthew Dillon * If it is the bitmap must be scanned. It can become invalid
57691abd410SMatthew Dillon * once we pack to the boundary. We adjust it after a bitmap
57791abd410SMatthew Dillon * allocation only for sub-16KB allocations (so the perfectly good
57891abd410SMatthew Dillon * previous value can still be used for fragments when 16KB+
579b49f72c3SMatthew Dillon * allocations are made inbetween fragmentary allocations).
58091abd410SMatthew Dillon *
5815cebbe36SMatthew Dillon * Beware of hardware artifacts when bmradix == 64 (intermediate
58291abd410SMatthew Dillon * result can wind up being '1' instead of '0' if hardware masks
583b49f72c3SMatthew Dillon * bit-count & 63).
58493f3933aSMatthew Dillon *
58593f3933aSMatthew Dillon * NOTE: j needs to be even in the j= calculation. As an artifact
58693f3933aSMatthew Dillon * of the /2 division, our bitmask has to clear bit 0.
58791abd410SMatthew Dillon *
58891abd410SMatthew Dillon * NOTE: TODO this can leave little unallocatable fragments lying
58991abd410SMatthew Dillon * around.
59093f3933aSMatthew Dillon */
59191abd410SMatthew Dillon if (((uint32_t)bmap->linear & HAMMER2_FREEMAP_BLOCK_MASK) + size <=
59291abd410SMatthew Dillon HAMMER2_FREEMAP_BLOCK_SIZE &&
5932c6f594dSMatthew Dillon (bmap->linear & HAMMER2_FREEMAP_BLOCK_MASK) &&
59491abd410SMatthew Dillon bmap->linear < HAMMER2_SEGSIZE) {
595aff72996SMatthew Dillon /*
596aff72996SMatthew Dillon * Use linear iterator if it is not block-aligned to avoid
597aff72996SMatthew Dillon * wasting space.
59883815ec6SMatthew Dillon *
59983815ec6SMatthew Dillon * Calculate the bitmapq[] index (i) and calculate the
60083815ec6SMatthew Dillon * shift count within the 64-bit bitmapq[] entry.
60183815ec6SMatthew Dillon *
60283815ec6SMatthew Dillon * The freemap block size is 16KB, but each bitmap
60383815ec6SMatthew Dillon * entry is two bits so use a little trick to get
60483815ec6SMatthew Dillon * a (j) shift of 0, 2, 4, ... 62 in 16KB chunks.
605aff72996SMatthew Dillon */
60693f3933aSMatthew Dillon KKASSERT(bmap->linear >= 0 &&
60791abd410SMatthew Dillon bmap->linear + size <= HAMMER2_SEGSIZE &&
60850456506SMatthew Dillon (bmap->linear & (HAMMER2_ALLOC_MIN - 1)) == 0);
60993f3933aSMatthew Dillon offset = bmap->linear;
61083815ec6SMatthew Dillon i = offset / (HAMMER2_SEGSIZE / HAMMER2_BMAP_ELEMENTS);
61183815ec6SMatthew Dillon j = (offset / (HAMMER2_FREEMAP_BLOCK_SIZE / 2)) & 62;
6125cebbe36SMatthew Dillon bmmask = (bmradix == HAMMER2_BMAP_BITS_PER_ELEMENT) ?
6135cebbe36SMatthew Dillon HAMMER2_BMAP_ALLONES :
6145cebbe36SMatthew Dillon ((hammer2_bitmap_t)1 << bmradix) - 1;
61593f3933aSMatthew Dillon bmmask <<= j;
61691abd410SMatthew Dillon bmap->linear = offset + size;
61793f3933aSMatthew Dillon } else {
618aff72996SMatthew Dillon /*
619aff72996SMatthew Dillon * Try to index a starting point based on sub_key. This
620aff72996SMatthew Dillon * attempts to restore sequential block ordering on-disk
621aff72996SMatthew Dillon * whenever possible, even if data is committed out of
622aff72996SMatthew Dillon * order.
623aff72996SMatthew Dillon *
624aff72996SMatthew Dillon * i - Index bitmapq[], full data range represented is
625aff72996SMatthew Dillon * HAMMER2_BMAP_SIZE.
626aff72996SMatthew Dillon *
627aff72996SMatthew Dillon * j - Index within bitmapq[i], full data range represented is
628aff72996SMatthew Dillon * HAMMER2_BMAP_INDEX_SIZE.
629aff72996SMatthew Dillon *
630aff72996SMatthew Dillon * WARNING!
631aff72996SMatthew Dillon */
632aff72996SMatthew Dillon i = -1;
633aff72996SMatthew Dillon j = -1;
634aff72996SMatthew Dillon
635aff72996SMatthew Dillon switch(class >> 8) {
636aff72996SMatthew Dillon case HAMMER2_BREF_TYPE_DATA:
637aff72996SMatthew Dillon if (radix >= HAMMER2_FREEMAP_BLOCK_RADIX) {
638aff72996SMatthew Dillon i = (sub_key & HAMMER2_BMAP_MASK) /
639aff72996SMatthew Dillon (HAMMER2_BMAP_SIZE / HAMMER2_BMAP_ELEMENTS);
640aff72996SMatthew Dillon j = (sub_key & HAMMER2_BMAP_INDEX_MASK) /
641aff72996SMatthew Dillon (HAMMER2_BMAP_INDEX_SIZE /
642aff72996SMatthew Dillon HAMMER2_BMAP_BLOCKS_PER_ELEMENT);
643aff72996SMatthew Dillon j = j * 2;
644aff72996SMatthew Dillon }
645aff72996SMatthew Dillon break;
646aff72996SMatthew Dillon case HAMMER2_BREF_TYPE_INODE:
647aff72996SMatthew Dillon break;
648aff72996SMatthew Dillon default:
649aff72996SMatthew Dillon break;
650aff72996SMatthew Dillon }
651aff72996SMatthew Dillon if (i >= 0) {
652aff72996SMatthew Dillon KKASSERT(i < HAMMER2_BMAP_ELEMENTS &&
653aff72996SMatthew Dillon j < 2 * HAMMER2_BMAP_BLOCKS_PER_ELEMENT);
654aff72996SMatthew Dillon KKASSERT(j + bmradix <= HAMMER2_BMAP_BITS_PER_ELEMENT);
655aff72996SMatthew Dillon bmmask = (bmradix == HAMMER2_BMAP_BITS_PER_ELEMENT) ?
656aff72996SMatthew Dillon HAMMER2_BMAP_ALLONES :
657aff72996SMatthew Dillon ((hammer2_bitmap_t)1 << bmradix) - 1;
658aff72996SMatthew Dillon bmmask <<= j;
659aff72996SMatthew Dillon
660aff72996SMatthew Dillon if ((bmap->bitmapq[i] & bmmask) == 0)
661aff72996SMatthew Dillon goto success;
662aff72996SMatthew Dillon }
663aff72996SMatthew Dillon
664aff72996SMatthew Dillon /*
665aff72996SMatthew Dillon * General element scan.
666aff72996SMatthew Dillon *
667aff72996SMatthew Dillon * WARNING: (j) is iterating a bit index (by 2's)
668aff72996SMatthew Dillon */
6695cebbe36SMatthew Dillon for (i = 0; i < HAMMER2_BMAP_ELEMENTS; ++i) {
6705cebbe36SMatthew Dillon bmmask = (bmradix == HAMMER2_BMAP_BITS_PER_ELEMENT) ?
6715cebbe36SMatthew Dillon HAMMER2_BMAP_ALLONES :
6725cebbe36SMatthew Dillon ((hammer2_bitmap_t)1 << bmradix) - 1;
6735cebbe36SMatthew Dillon for (j = 0;
6745cebbe36SMatthew Dillon j < HAMMER2_BMAP_BITS_PER_ELEMENT;
6755cebbe36SMatthew Dillon j += bmradix) {
6765cebbe36SMatthew Dillon if ((bmap->bitmapq[i] & bmmask) == 0)
67793f3933aSMatthew Dillon goto success;
67893f3933aSMatthew Dillon bmmask <<= bmradix;
67993f3933aSMatthew Dillon }
68093f3933aSMatthew Dillon }
68191abd410SMatthew Dillon /*fragments might remain*/
68291abd410SMatthew Dillon /*KKASSERT(bmap->avail == 0);*/
68365cacacfSMatthew Dillon return (HAMMER2_ERROR_ENOSPC);
68493f3933aSMatthew Dillon success:
6855cebbe36SMatthew Dillon offset = i * (HAMMER2_SEGSIZE / HAMMER2_BMAP_ELEMENTS) +
68693f3933aSMatthew Dillon (j * (HAMMER2_FREEMAP_BLOCK_SIZE / 2));
68791abd410SMatthew Dillon if (size & HAMMER2_FREEMAP_BLOCK_MASK)
68891abd410SMatthew Dillon bmap->linear = offset + size;
68993f3933aSMatthew Dillon }
69093f3933aSMatthew Dillon
6915cebbe36SMatthew Dillon /* 8 x (64/2) -> 256 x 16K -> 4MB */
6925cebbe36SMatthew Dillon KKASSERT(i >= 0 && i < HAMMER2_BMAP_ELEMENTS);
69393f3933aSMatthew Dillon
69493f3933aSMatthew Dillon /*
69593f3933aSMatthew Dillon * Optimize the buffer cache to avoid unnecessary read-before-write
69693f3933aSMatthew Dillon * operations.
69791abd410SMatthew Dillon *
69891abd410SMatthew Dillon * The device block size could be larger than the allocation size
69991abd410SMatthew Dillon * so the actual bitmap test is somewhat more involved. We have
70091abd410SMatthew Dillon * to use a compatible buffer size for this operation.
70193f3933aSMatthew Dillon */
7025cebbe36SMatthew Dillon if ((bmap->bitmapq[i] & bmmask) == 0 &&
703ee78054eSTomohiro Kusumi HAMMER2_PBUFSIZE != size) {
704ee78054eSTomohiro Kusumi size_t psize = HAMMER2_PBUFSIZE;
70591abd410SMatthew Dillon hammer2_off_t pmask = (hammer2_off_t)psize - 1;
7065cebbe36SMatthew Dillon int pbmradix = (hammer2_bitmap_t)2 <<
707ee78054eSTomohiro Kusumi (HAMMER2_PBUFRADIX -
70891abd410SMatthew Dillon HAMMER2_FREEMAP_BLOCK_RADIX);
7095cebbe36SMatthew Dillon hammer2_bitmap_t pbmmask;
710fdf62707SMatthew Dillon int pradix = hammer2_getradix(psize);
71191abd410SMatthew Dillon
7125cebbe36SMatthew Dillon pbmmask = (pbmradix == HAMMER2_BMAP_BITS_PER_ELEMENT) ?
7135cebbe36SMatthew Dillon HAMMER2_BMAP_ALLONES :
7145cebbe36SMatthew Dillon ((hammer2_bitmap_t)1 << pbmradix) - 1;
71591abd410SMatthew Dillon while ((pbmmask & bmmask) == 0)
71691abd410SMatthew Dillon pbmmask <<= pbmradix;
71791abd410SMatthew Dillon
7182c6f594dSMatthew Dillon #if 0
7195cebbe36SMatthew Dillon kprintf("%016jx mask %016jx %016jx %016jx (%zd/%zd)\n",
7205cebbe36SMatthew Dillon *basep + offset, bmap->bitmapq[i],
7212c6f594dSMatthew Dillon pbmmask, bmmask, size, psize);
7222c6f594dSMatthew Dillon #endif
7232c6f594dSMatthew Dillon
7245cebbe36SMatthew Dillon if ((bmap->bitmapq[i] & pbmmask) == 0) {
72585b1f267SMatthew Dillon hammer2_io_t *dio;
72685b1f267SMatthew Dillon
72785b1f267SMatthew Dillon hammer2_io_newnz(hmp, class >> 8,
728fdf62707SMatthew Dillon (*basep + (offset & ~pmask)) |
72985b1f267SMatthew Dillon pradix, psize, &dio);
73085b1f267SMatthew Dillon hammer2_io_putblk(&dio);
73193f3933aSMatthew Dillon }
73291abd410SMatthew Dillon }
73393f3933aSMatthew Dillon
73493f3933aSMatthew Dillon #if 0
73593f3933aSMatthew Dillon /*
73693f3933aSMatthew Dillon * When initializing a new inode segment also attempt to initialize
73793f3933aSMatthew Dillon * an adjacent segment. Be careful not to index beyond the array
73893f3933aSMatthew Dillon * bounds.
73993f3933aSMatthew Dillon *
74093f3933aSMatthew Dillon * We do this to try to localize inode accesses to improve
74193f3933aSMatthew Dillon * directory scan rates. XXX doesn't improve scan rates.
74293f3933aSMatthew Dillon */
74393f3933aSMatthew Dillon if (size == HAMMER2_INODE_BYTES) {
74493f3933aSMatthew Dillon if (n & 1) {
74593f3933aSMatthew Dillon if (bmap[-1].radix == 0 && bmap[-1].avail)
74693f3933aSMatthew Dillon bmap[-1].radix = radix;
74793f3933aSMatthew Dillon } else {
74893f3933aSMatthew Dillon if (bmap[1].radix == 0 && bmap[1].avail)
74993f3933aSMatthew Dillon bmap[1].radix = radix;
75093f3933aSMatthew Dillon }
75193f3933aSMatthew Dillon }
75293f3933aSMatthew Dillon #endif
753271568b1SMatthew Dillon /*
754271568b1SMatthew Dillon * Calculate the bitmap-granular change in bgsize for the volume
755271568b1SMatthew Dillon * header. We cannot use the fine-grained change here because
756271568b1SMatthew Dillon * the bulkfree code can't undo it. If the bitmap element is already
757271568b1SMatthew Dillon * marked allocated it has already been accounted for.
758271568b1SMatthew Dillon */
759271568b1SMatthew Dillon if (radix < HAMMER2_FREEMAP_BLOCK_RADIX) {
7605cebbe36SMatthew Dillon if (bmap->bitmapq[i] & bmmask)
761271568b1SMatthew Dillon bgsize = 0;
762271568b1SMatthew Dillon else
763271568b1SMatthew Dillon bgsize = HAMMER2_FREEMAP_BLOCK_SIZE;
764271568b1SMatthew Dillon } else {
765271568b1SMatthew Dillon bgsize = size;
766271568b1SMatthew Dillon }
76793f3933aSMatthew Dillon
76893f3933aSMatthew Dillon /*
769271568b1SMatthew Dillon * Adjust the bitmap, set the class (it might have been 0),
770271568b1SMatthew Dillon * and available bytes, update the allocation offset (*basep)
771271568b1SMatthew Dillon * from the L0 base to the actual offset.
772271568b1SMatthew Dillon *
77365cacacfSMatthew Dillon * Do not override the class if doing a relaxed class allocation.
77465cacacfSMatthew Dillon *
775271568b1SMatthew Dillon * avail must reflect the bitmap-granular availability. The allocator
776271568b1SMatthew Dillon * tests will also check the linear iterator.
77793f3933aSMatthew Dillon */
7785cebbe36SMatthew Dillon bmap->bitmapq[i] |= bmmask;
77965cacacfSMatthew Dillon if (bmap->class == 0)
78091abd410SMatthew Dillon bmap->class = class;
781271568b1SMatthew Dillon bmap->avail -= bgsize;
78293f3933aSMatthew Dillon *basep += offset;
78393f3933aSMatthew Dillon
784271568b1SMatthew Dillon /*
785271568b1SMatthew Dillon * Adjust the volume header's allocator_free parameter. This
786271568b1SMatthew Dillon * parameter has to be fixed up by bulkfree which has no way to
787271568b1SMatthew Dillon * figure out sub-16K chunking, so it must be adjusted by the
788271568b1SMatthew Dillon * bitmap-granular size.
789271568b1SMatthew Dillon */
790271568b1SMatthew Dillon if (bgsize) {
7919f604b01SMatthew Dillon hammer2_voldata_lock(hmp);
79250456506SMatthew Dillon hammer2_voldata_modify(hmp);
793271568b1SMatthew Dillon hmp->voldata.allocator_free -= bgsize;
79450456506SMatthew Dillon hammer2_voldata_unlock(hmp);
795271568b1SMatthew Dillon }
7969f604b01SMatthew Dillon
79793f3933aSMatthew Dillon return(0);
79893f3933aSMatthew Dillon }
79993f3933aSMatthew Dillon
80065cacacfSMatthew Dillon /*
80165cacacfSMatthew Dillon * Initialize a freemap for the storage area (in bytes) that begins at (key).
80265cacacfSMatthew Dillon */
80393f3933aSMatthew Dillon static
80493f3933aSMatthew Dillon void
hammer2_freemap_init(hammer2_dev_t * hmp,hammer2_key_t key,hammer2_chain_t * chain)805c603b86bSMatthew Dillon hammer2_freemap_init(hammer2_dev_t *hmp, hammer2_key_t key,
806c603b86bSMatthew Dillon hammer2_chain_t *chain)
80793f3933aSMatthew Dillon {
80893f3933aSMatthew Dillon hammer2_off_t lokey;
80993f3933aSMatthew Dillon hammer2_off_t hikey;
81093f3933aSMatthew Dillon hammer2_bmap_data_t *bmap;
81193f3933aSMatthew Dillon int count;
81293f3933aSMatthew Dillon
81365cacacfSMatthew Dillon /*
81465cacacfSMatthew Dillon * Calculate the portion of the 1GB map that should be initialized
81593f3933aSMatthew Dillon * as free. Portions below or after will be initialized as allocated.
81693f3933aSMatthew Dillon * SEGMASK-align the areas so we don't have to worry about sub-scans
81793f3933aSMatthew Dillon * or endianess when using memset.
81893f3933aSMatthew Dillon *
81993f3933aSMatthew Dillon * WARNING! It is possible for lokey to be larger than hikey if the
82093f3933aSMatthew Dillon * entire 2GB segment is within the static allocation.
82193f3933aSMatthew Dillon */
82265cacacfSMatthew Dillon /*
82365cacacfSMatthew Dillon * (1) Ensure that all statically allocated space from newfs_hammer2
82465cacacfSMatthew Dillon * is marked allocated, and take it up to the level1 base for
82565cacacfSMatthew Dillon * this key.
82665cacacfSMatthew Dillon */
827a5913bdfSMatthew Dillon lokey = (hmp->voldata.allocator_beg + HAMMER2_SEGMASK64) &
82893f3933aSMatthew Dillon ~HAMMER2_SEGMASK64;
82965cacacfSMatthew Dillon if (lokey < H2FMBASE(key, HAMMER2_FREEMAP_LEVEL1_RADIX))
83065cacacfSMatthew Dillon lokey = H2FMBASE(key, HAMMER2_FREEMAP_LEVEL1_RADIX);
83193f3933aSMatthew Dillon
83265cacacfSMatthew Dillon /*
83365cacacfSMatthew Dillon * (2) Ensure that the reserved area is marked allocated (typically
83465cacacfSMatthew Dillon * the first 4MB of each 2GB area being represented). Since
83565cacacfSMatthew Dillon * each LEAF represents 1GB of storage and the zone is 2GB, we
83665cacacfSMatthew Dillon * have to adjust lowkey upward every other LEAF sequentially.
83765cacacfSMatthew Dillon */
83865cacacfSMatthew Dillon if (lokey < H2FMZONEBASE(key) + HAMMER2_ZONE_SEG64)
83965cacacfSMatthew Dillon lokey = H2FMZONEBASE(key) + HAMMER2_ZONE_SEG64;
84093f3933aSMatthew Dillon
84165cacacfSMatthew Dillon /*
84265cacacfSMatthew Dillon * (3) Ensure that any trailing space at the end-of-volume is marked
84365cacacfSMatthew Dillon * allocated.
84465cacacfSMatthew Dillon */
8454e47c34eSTomohiro Kusumi hikey = key + HAMMER2_FREEMAP_LEVEL1_SIZE;
8460b738157STomohiro Kusumi if (hikey > hmp->total_size) {
8470b738157STomohiro Kusumi hikey = hmp->total_size & ~HAMMER2_SEGMASK64;
84893f3933aSMatthew Dillon }
84993f3933aSMatthew Dillon
85065cacacfSMatthew Dillon /*
85165cacacfSMatthew Dillon * Heuristic highest possible value
85265cacacfSMatthew Dillon */
8534e47c34eSTomohiro Kusumi chain->bref.check.freemap.avail = HAMMER2_FREEMAP_LEVEL1_SIZE;
85493f3933aSMatthew Dillon bmap = &chain->data->bmdata[0];
85593f3933aSMatthew Dillon
85665cacacfSMatthew Dillon /*
85765cacacfSMatthew Dillon * Initialize bitmap (bzero'd by caller)
85865cacacfSMatthew Dillon */
85993f3933aSMatthew Dillon for (count = 0; count < HAMMER2_FREEMAP_COUNT; ++count) {
86093f3933aSMatthew Dillon if (key < lokey || key >= hikey) {
8615cebbe36SMatthew Dillon memset(bmap->bitmapq, -1,
8625cebbe36SMatthew Dillon sizeof(bmap->bitmapq));
86393f3933aSMatthew Dillon bmap->avail = 0;
8642c6f594dSMatthew Dillon bmap->linear = HAMMER2_SEGSIZE;
86593f3933aSMatthew Dillon chain->bref.check.freemap.avail -=
8664e47c34eSTomohiro Kusumi HAMMER2_FREEMAP_LEVEL0_SIZE;
86793f3933aSMatthew Dillon } else {
8684e47c34eSTomohiro Kusumi bmap->avail = HAMMER2_FREEMAP_LEVEL0_SIZE;
86993f3933aSMatthew Dillon }
8704e47c34eSTomohiro Kusumi key += HAMMER2_FREEMAP_LEVEL0_SIZE;
87193f3933aSMatthew Dillon ++bmap;
87293f3933aSMatthew Dillon }
87393f3933aSMatthew Dillon }
87493f3933aSMatthew Dillon
87593f3933aSMatthew Dillon /*
87693f3933aSMatthew Dillon * The current Level 1 freemap has been exhausted, iterate to the next
87793f3933aSMatthew Dillon * one, return ENOSPC if no freemaps remain.
87893f3933aSMatthew Dillon *
87965cacacfSMatthew Dillon * At least two loops are required. If we are not in relaxed mode and
88065cacacfSMatthew Dillon * we run out of storage we enter relaxed mode and do a third loop.
88165cacacfSMatthew Dillon * The relaxed mode is recorded back in the hmp so once we enter the mode
88265cacacfSMatthew Dillon * we remain relaxed until stuff begins to get freed and only do 2 loops.
88365cacacfSMatthew Dillon *
88493f3933aSMatthew Dillon * XXX this should rotate back to the beginning to handle freed-up space
88593f3933aSMatthew Dillon * XXX or use intermediate entries to locate free space. TODO
88693f3933aSMatthew Dillon */
8871a7cfe5aSMatthew Dillon static int
hammer2_freemap_iterate(hammer2_chain_t ** parentp,hammer2_chain_t ** chainp,hammer2_fiterate_t * iter)888c603b86bSMatthew Dillon hammer2_freemap_iterate(hammer2_chain_t **parentp, hammer2_chain_t **chainp,
889c603b86bSMatthew Dillon hammer2_fiterate_t *iter)
8901a7cfe5aSMatthew Dillon {
891506bd6d1SMatthew Dillon hammer2_dev_t *hmp = (*parentp)->hmp;
892a5913bdfSMatthew Dillon
89320a886d5STomohiro Kusumi iter->bnext &= ~HAMMER2_FREEMAP_LEVEL1_MASK;
8944e47c34eSTomohiro Kusumi iter->bnext += HAMMER2_FREEMAP_LEVEL1_SIZE;
8950b738157STomohiro Kusumi if (iter->bnext >= hmp->total_size) {
89691abd410SMatthew Dillon iter->bnext = 0;
89765cacacfSMatthew Dillon if (++iter->loops >= 2) {
89865cacacfSMatthew Dillon if (iter->relaxed == 0)
89965cacacfSMatthew Dillon iter->relaxed = 1;
90065cacacfSMatthew Dillon else
90165cacacfSMatthew Dillon return (HAMMER2_ERROR_ENOSPC);
90291abd410SMatthew Dillon }
90365cacacfSMatthew Dillon }
90465cacacfSMatthew Dillon return(HAMMER2_ERROR_EAGAIN);
90537aa19dfSMatthew Dillon }
9061a7cfe5aSMatthew Dillon
90791abd410SMatthew Dillon /*
908877eacb6SMatthew Dillon * Adjust the bit-pattern for data in the freemap bitmap according to
909877eacb6SMatthew Dillon * (how). This code is called from on-mount recovery to fixup (mark
910877eacb6SMatthew Dillon * as allocated) blocks whos freemap upates might not have been committed
911877eacb6SMatthew Dillon * in the last crash and is used by the bulk freemap scan to stage frees.
91291abd410SMatthew Dillon *
913da0cdd33SMatthew Dillon * WARNING! Cannot be called with a empty-data bref (radix == 0).
914da0cdd33SMatthew Dillon *
91591abd410SMatthew Dillon * XXX currently disabled when how == 0 (the normal real-time case). At
91691abd410SMatthew Dillon * the moment we depend on the bulk freescan to actually free blocks. It
91791abd410SMatthew Dillon * will still call this routine with a non-zero how to stage possible frees
91891abd410SMatthew Dillon * and to do the actual free.
91991abd410SMatthew Dillon */
920004f88b4SMatthew Dillon void
hammer2_freemap_adjust(hammer2_dev_t * hmp,hammer2_blockref_t * bref,int how)921e2163f5bSMatthew Dillon hammer2_freemap_adjust(hammer2_dev_t *hmp, hammer2_blockref_t *bref,
922e2163f5bSMatthew Dillon int how)
923004f88b4SMatthew Dillon {
92491abd410SMatthew Dillon hammer2_off_t data_off = bref->data_off;
92591abd410SMatthew Dillon hammer2_chain_t *chain;
92691abd410SMatthew Dillon hammer2_chain_t *parent;
92791abd410SMatthew Dillon hammer2_bmap_data_t *bmap;
92891abd410SMatthew Dillon hammer2_key_t key;
9291897c66eSMatthew Dillon hammer2_key_t key_dummy;
93091abd410SMatthew Dillon hammer2_off_t l1size;
93191abd410SMatthew Dillon hammer2_off_t l1mask;
932e2163f5bSMatthew Dillon hammer2_tid_t mtid;
9335cebbe36SMatthew Dillon hammer2_bitmap_t *bitmap;
9345cebbe36SMatthew Dillon const hammer2_bitmap_t bmmask00 = 0;
9350a7ab006STomohiro Kusumi //hammer2_bitmap_t bmmask01;
9360a7ab006STomohiro Kusumi //hammer2_bitmap_t bmmask10;
9375cebbe36SMatthew Dillon hammer2_bitmap_t bmmask11;
93891abd410SMatthew Dillon size_t bytes;
93991abd410SMatthew Dillon uint16_t class;
940004f88b4SMatthew Dillon int radix;
94191abd410SMatthew Dillon int start;
94291abd410SMatthew Dillon int count;
94391abd410SMatthew Dillon int modified = 0;
94410136ab6SMatthew Dillon int error;
945470dad14SMatthew Dillon size_t bgsize = 0;
946004f88b4SMatthew Dillon
947271568b1SMatthew Dillon KKASSERT(how == HAMMER2_FREEMAP_DORECOVER);
948271568b1SMatthew Dillon
94965c894ffSMatthew Dillon KKASSERT(hmp->spmp);
950e2163f5bSMatthew Dillon mtid = hammer2_trans_sub(hmp->spmp);
951e2163f5bSMatthew Dillon
952004f88b4SMatthew Dillon radix = (int)data_off & HAMMER2_OFF_MASK_RADIX;
953da0cdd33SMatthew Dillon KKASSERT(radix != 0);
954004f88b4SMatthew Dillon data_off &= ~HAMMER2_OFF_MASK_RADIX;
95550456506SMatthew Dillon KKASSERT(radix <= HAMMER2_RADIX_MAX);
956004f88b4SMatthew Dillon
957da0cdd33SMatthew Dillon if (radix)
95891abd410SMatthew Dillon bytes = (size_t)1 << radix;
959da0cdd33SMatthew Dillon else
960da0cdd33SMatthew Dillon bytes = 0;
961ee78054eSTomohiro Kusumi class = (bref->type << 8) | HAMMER2_PBUFRADIX;
962004f88b4SMatthew Dillon
9635c23d7f1SMatthew Dillon /*
964da0cdd33SMatthew Dillon * We can't adjust the freemap for data allocations made by
96510136ab6SMatthew Dillon * newfs_hammer2.
966355d67fcSMatthew Dillon */
967355d67fcSMatthew Dillon if (data_off < hmp->voldata.allocator_beg)
968355d67fcSMatthew Dillon return;
969355d67fcSMatthew Dillon
97010136ab6SMatthew Dillon KKASSERT((data_off & HAMMER2_ZONE_MASK64) >= HAMMER2_ZONE_SEG);
971a7720be7SMatthew Dillon
972355d67fcSMatthew Dillon /*
97391abd410SMatthew Dillon * Lookup the level1 freemap chain. The chain must exist.
9745c23d7f1SMatthew Dillon */
97591abd410SMatthew Dillon key = H2FMBASE(data_off, HAMMER2_FREEMAP_LEVEL1_RADIX);
9764e47c34eSTomohiro Kusumi l1size = HAMMER2_FREEMAP_LEVEL1_SIZE;
97791abd410SMatthew Dillon l1mask = l1size - 1;
97891abd410SMatthew Dillon
97991abd410SMatthew Dillon parent = &hmp->fchain;
980e513e77eSMatthew Dillon hammer2_chain_ref(parent);
98191abd410SMatthew Dillon hammer2_chain_lock(parent, HAMMER2_RESOLVE_ALWAYS);
98291abd410SMatthew Dillon
9831897c66eSMatthew Dillon chain = hammer2_chain_lookup(&parent, &key_dummy, key, key + l1mask,
984c8c0a18aSMatthew Dillon &error,
98591abd410SMatthew Dillon HAMMER2_LOOKUP_ALWAYS |
986b8ba9690SMatthew Dillon HAMMER2_LOOKUP_MATCHIND);
98710136ab6SMatthew Dillon
98810136ab6SMatthew Dillon /*
98910136ab6SMatthew Dillon * Stop early if we are trying to free something but no leaf exists.
99010136ab6SMatthew Dillon */
99110136ab6SMatthew Dillon if (chain == NULL && how != HAMMER2_FREEMAP_DORECOVER) {
99210136ab6SMatthew Dillon kprintf("hammer2_freemap_adjust: %016jx: no chain\n",
99391abd410SMatthew Dillon (intmax_t)bref->data_off);
994623d43d4SMatthew Dillon goto done;
99591abd410SMatthew Dillon }
996b93cc2e0SMatthew Dillon if (chain->error) {
997b93cc2e0SMatthew Dillon kprintf("hammer2_freemap_adjust: %016jx: error %s\n",
998b93cc2e0SMatthew Dillon (intmax_t)bref->data_off,
999b93cc2e0SMatthew Dillon hammer2_error_str(chain->error));
1000b93cc2e0SMatthew Dillon hammer2_chain_unlock(chain);
1001e513e77eSMatthew Dillon hammer2_chain_drop(chain);
1002b93cc2e0SMatthew Dillon chain = NULL;
1003b93cc2e0SMatthew Dillon goto done;
1004b93cc2e0SMatthew Dillon }
100591abd410SMatthew Dillon
100691abd410SMatthew Dillon /*
100710136ab6SMatthew Dillon * Create any missing leaf(s) if we are doing a recovery (marking
100810136ab6SMatthew Dillon * the block(s) as being allocated instead of being freed). Be sure
100910136ab6SMatthew Dillon * to initialize the auxillary freemap tracking info in the
101010136ab6SMatthew Dillon * bref.check.freemap structure.
101191abd410SMatthew Dillon */
101210136ab6SMatthew Dillon if (chain == NULL && how == HAMMER2_FREEMAP_DORECOVER) {
1013ecfe89b8SMatthew Dillon error = hammer2_chain_create(&parent, &chain, NULL, hmp->spmp,
1014ecfe89b8SMatthew Dillon HAMMER2_METH_DEFAULT,
101510136ab6SMatthew Dillon key, HAMMER2_FREEMAP_LEVEL1_RADIX,
101610136ab6SMatthew Dillon HAMMER2_BREF_TYPE_FREEMAP_LEAF,
1017b3659de2SMatthew Dillon HAMMER2_FREEMAP_LEVELN_PSIZE,
10183f01ebaaSMatthew Dillon mtid, 0, 0);
10191fca819aSMatthew Dillon
10201fca819aSMatthew Dillon if (hammer2_debug & 0x0040) {
10211fca819aSMatthew Dillon kprintf("fixup create chain %p %016jx:%d\n",
10221fca819aSMatthew Dillon chain, chain->bref.key, chain->bref.keybits);
10231fca819aSMatthew Dillon }
102491abd410SMatthew Dillon
102510136ab6SMatthew Dillon if (error == 0) {
102665cacacfSMatthew Dillon error = hammer2_chain_modify(chain, mtid, 0, 0);
102765cacacfSMatthew Dillon KKASSERT(error == 0);
102810136ab6SMatthew Dillon bzero(&chain->data->bmdata[0],
102910136ab6SMatthew Dillon HAMMER2_FREEMAP_LEVELN_PSIZE);
103010136ab6SMatthew Dillon chain->bref.check.freemap.bigmask = (uint32_t)-1;
103110136ab6SMatthew Dillon chain->bref.check.freemap.avail = l1size;
103210136ab6SMatthew Dillon /* bref.methods should already be inherited */
103310136ab6SMatthew Dillon
1034c603b86bSMatthew Dillon hammer2_freemap_init(hmp, key, chain);
103510136ab6SMatthew Dillon }
103610136ab6SMatthew Dillon /* XXX handle error */
103710136ab6SMatthew Dillon }
103810136ab6SMatthew Dillon
10398138a154SMatthew Dillon #if FREEMAP_DEBUG
10408138a154SMatthew Dillon kprintf("FREEMAP ADJUST TYPE %d %016jx/%d DATA_OFF=%016jx\n",
10418138a154SMatthew Dillon chain->bref.type, chain->bref.key,
10428138a154SMatthew Dillon chain->bref.keybits, chain->bref.data_off);
10438138a154SMatthew Dillon #endif
10448138a154SMatthew Dillon
104510136ab6SMatthew Dillon /*
104610136ab6SMatthew Dillon * Calculate the bitmask (runs in 2-bit pairs).
104710136ab6SMatthew Dillon */
104891abd410SMatthew Dillon start = ((int)(data_off >> HAMMER2_FREEMAP_BLOCK_RADIX) & 15) * 2;
10490a7ab006STomohiro Kusumi //bmmask01 = (hammer2_bitmap_t)1 << start;
10500a7ab006STomohiro Kusumi //bmmask10 = (hammer2_bitmap_t)2 << start;
10515cebbe36SMatthew Dillon bmmask11 = (hammer2_bitmap_t)3 << start;
105291abd410SMatthew Dillon
105391abd410SMatthew Dillon /*
105410136ab6SMatthew Dillon * Fixup the bitmap. Partial blocks cannot be fully freed unless
105510136ab6SMatthew Dillon * a bulk scan is able to roll them up.
105691abd410SMatthew Dillon */
105791abd410SMatthew Dillon if (radix < HAMMER2_FREEMAP_BLOCK_RADIX) {
105891abd410SMatthew Dillon count = 1;
1059cfde0144STomohiro Kusumi #if 0
106010136ab6SMatthew Dillon if (how == HAMMER2_FREEMAP_DOREALFREE)
106110136ab6SMatthew Dillon how = HAMMER2_FREEMAP_DOMAYFREE;
1062cfde0144STomohiro Kusumi #endif
106391abd410SMatthew Dillon } else {
106491abd410SMatthew Dillon count = 1 << (radix - HAMMER2_FREEMAP_BLOCK_RADIX);
10655c23d7f1SMatthew Dillon }
10665c23d7f1SMatthew Dillon
106710136ab6SMatthew Dillon /*
106810136ab6SMatthew Dillon * [re]load the bmap and bitmap pointers. Each bmap entry covers
106930b0abf3SMatthew Dillon * a 4MB swath. The bmap itself (LEVEL1) covers 2GB.
10708138a154SMatthew Dillon *
10718138a154SMatthew Dillon * Be sure to reset the linear iterator to ensure that the adjustment
10728138a154SMatthew Dillon * is not ignored.
107310136ab6SMatthew Dillon */
107410136ab6SMatthew Dillon again:
107591abd410SMatthew Dillon bmap = &chain->data->bmdata[(int)(data_off >> HAMMER2_SEGRADIX) &
107691abd410SMatthew Dillon (HAMMER2_FREEMAP_COUNT - 1)];
10775cebbe36SMatthew Dillon bitmap = &bmap->bitmapq[(int)(data_off >> (HAMMER2_SEGRADIX - 3)) & 7];
1078a71db85dSMatthew Dillon
1079a71db85dSMatthew Dillon if (modified)
10808138a154SMatthew Dillon bmap->linear = 0;
108110136ab6SMatthew Dillon
108210136ab6SMatthew Dillon while (count) {
108310136ab6SMatthew Dillon KKASSERT(bmmask11);
108410136ab6SMatthew Dillon if (how == HAMMER2_FREEMAP_DORECOVER) {
108510136ab6SMatthew Dillon /*
108610136ab6SMatthew Dillon * Recovery request, mark as allocated.
108710136ab6SMatthew Dillon */
108810136ab6SMatthew Dillon if ((*bitmap & bmmask11) != bmmask11) {
108910136ab6SMatthew Dillon if (modified == 0) {
10903f01ebaaSMatthew Dillon hammer2_chain_modify(chain, mtid, 0, 0);
109110136ab6SMatthew Dillon modified = 1;
109210136ab6SMatthew Dillon goto again;
109391abd410SMatthew Dillon }
1094271568b1SMatthew Dillon if ((*bitmap & bmmask11) == bmmask00) {
1095271568b1SMatthew Dillon bmap->avail -=
1096271568b1SMatthew Dillon HAMMER2_FREEMAP_BLOCK_SIZE;
1097470dad14SMatthew Dillon bgsize += HAMMER2_FREEMAP_BLOCK_SIZE;
1098271568b1SMatthew Dillon }
109910136ab6SMatthew Dillon if (bmap->class == 0)
110010136ab6SMatthew Dillon bmap->class = class;
110110136ab6SMatthew Dillon *bitmap |= bmmask11;
11021fca819aSMatthew Dillon if (hammer2_debug & 0x0040) {
11039670fc90STomohiro Kusumi kprintf("hammer2_freemap_adjust: "
11041fca819aSMatthew Dillon "fixup type=%02x "
11051fca819aSMatthew Dillon "block=%016jx/%zd\n",
110610136ab6SMatthew Dillon bref->type, data_off, bytes);
11071fca819aSMatthew Dillon }
110810136ab6SMatthew Dillon } else {
110910136ab6SMatthew Dillon /*
11109670fc90STomohiro Kusumi kprintf("hammer2_freemap_adjust: good "
111110136ab6SMatthew Dillon "type=%02x block=%016jx/%zd\n",
111210136ab6SMatthew Dillon bref->type, data_off, bytes);
111310136ab6SMatthew Dillon */
111410136ab6SMatthew Dillon }
1115271568b1SMatthew Dillon }
1116271568b1SMatthew Dillon #if 0
1117271568b1SMatthew Dillon /*
1118271568b1SMatthew Dillon * XXX this stuff doesn't work, avail is miscalculated and
1119271568b1SMatthew Dillon * code 10 means something else now.
1120271568b1SMatthew Dillon */
1121271568b1SMatthew Dillon else if ((*bitmap & bmmask11) == bmmask11) {
112210136ab6SMatthew Dillon /*
112310136ab6SMatthew Dillon * Mayfree/Realfree request and bitmap is currently
112410136ab6SMatthew Dillon * marked as being fully allocated.
112510136ab6SMatthew Dillon */
112610136ab6SMatthew Dillon if (!modified) {
1127c603b86bSMatthew Dillon hammer2_chain_modify(chain, 0);
112810136ab6SMatthew Dillon modified = 1;
112910136ab6SMatthew Dillon goto again;
113010136ab6SMatthew Dillon }
113110136ab6SMatthew Dillon if (how == HAMMER2_FREEMAP_DOREALFREE)
113291abd410SMatthew Dillon *bitmap &= ~bmmask11;
113391abd410SMatthew Dillon else
113491abd410SMatthew Dillon *bitmap = (*bitmap & ~bmmask11) | bmmask10;
113591abd410SMatthew Dillon } else if ((*bitmap & bmmask11) == bmmask10) {
113610136ab6SMatthew Dillon /*
113710136ab6SMatthew Dillon * Mayfree/Realfree request and bitmap is currently
113810136ab6SMatthew Dillon * marked as being possibly freeable.
113910136ab6SMatthew Dillon */
114010136ab6SMatthew Dillon if (how == HAMMER2_FREEMAP_DOREALFREE) {
114191abd410SMatthew Dillon if (!modified) {
1142c603b86bSMatthew Dillon hammer2_chain_modify(chain, 0);
114391abd410SMatthew Dillon modified = 1;
114410136ab6SMatthew Dillon goto again;
114591abd410SMatthew Dillon }
114691abd410SMatthew Dillon *bitmap &= ~bmmask11;
114791abd410SMatthew Dillon }
114810136ab6SMatthew Dillon } else {
114910136ab6SMatthew Dillon /*
115010136ab6SMatthew Dillon * 01 - Not implemented, currently illegal state
115110136ab6SMatthew Dillon * 00 - Not allocated at all, illegal free.
115210136ab6SMatthew Dillon */
115310136ab6SMatthew Dillon panic("hammer2_freemap_adjust: "
115410136ab6SMatthew Dillon "Illegal state %08x(%08x)",
115510136ab6SMatthew Dillon *bitmap, *bitmap & bmmask11);
115691abd410SMatthew Dillon }
1157271568b1SMatthew Dillon #endif
115891abd410SMatthew Dillon --count;
11590a7ab006STomohiro Kusumi //bmmask01 <<= 2;
11600a7ab006STomohiro Kusumi //bmmask10 <<= 2;
116191abd410SMatthew Dillon bmmask11 <<= 2;
116291abd410SMatthew Dillon }
1163cfde0144STomohiro Kusumi #if 0
11645cebbe36SMatthew Dillon #if HAMMER2_BMAP_ELEMENTS != 8
11655cebbe36SMatthew Dillon #error "hammer2_freemap.c: HAMMER2_BMAP_ELEMENTS expected to be 8"
11665cebbe36SMatthew Dillon #endif
116710136ab6SMatthew Dillon if (how == HAMMER2_FREEMAP_DOREALFREE && modified) {
116891abd410SMatthew Dillon bmap->avail += 1 << radix;
116991abd410SMatthew Dillon KKASSERT(bmap->avail <= HAMMER2_SEGSIZE);
117091abd410SMatthew Dillon if (bmap->avail == HAMMER2_SEGSIZE &&
11715cebbe36SMatthew Dillon bmap->bitmapq[0] == 0 &&
11725cebbe36SMatthew Dillon bmap->bitmapq[1] == 0 &&
11735cebbe36SMatthew Dillon bmap->bitmapq[2] == 0 &&
11745cebbe36SMatthew Dillon bmap->bitmapq[3] == 0 &&
11755cebbe36SMatthew Dillon bmap->bitmapq[4] == 0 &&
11765cebbe36SMatthew Dillon bmap->bitmapq[5] == 0 &&
11775cebbe36SMatthew Dillon bmap->bitmapq[6] == 0 &&
11785cebbe36SMatthew Dillon bmap->bitmapq[7] == 0) {
117991abd410SMatthew Dillon key = H2FMBASE(data_off, HAMMER2_FREEMAP_LEVEL0_RADIX);
118091abd410SMatthew Dillon kprintf("Freeseg %016jx\n", (intmax_t)key);
118191abd410SMatthew Dillon bmap->class = 0;
118291abd410SMatthew Dillon }
118391abd410SMatthew Dillon }
1184cfde0144STomohiro Kusumi #endif
118591abd410SMatthew Dillon
118691abd410SMatthew Dillon /*
118791abd410SMatthew Dillon * chain->bref.check.freemap.bigmask (XXX)
118810136ab6SMatthew Dillon *
118910136ab6SMatthew Dillon * Setting bigmask is a hint to the allocation code that there might
119010136ab6SMatthew Dillon * be something allocatable. We also set this in recovery... it
119110136ab6SMatthew Dillon * doesn't hurt and we might want to use the hint for other validation
119210136ab6SMatthew Dillon * operations later on.
119365cacacfSMatthew Dillon *
119465cacacfSMatthew Dillon * We could calculate the largest possible allocation and set the
1195a4cea70eSTomohiro Kusumi * radixes that could fit, but its easier just to set bigmask to -1.
119691abd410SMatthew Dillon */
119765cacacfSMatthew Dillon if (modified) {
119865cacacfSMatthew Dillon chain->bref.check.freemap.bigmask = -1;
119965cacacfSMatthew Dillon hmp->freemap_relaxed = 0; /* reset heuristic */
120065cacacfSMatthew Dillon }
120191abd410SMatthew Dillon
120291abd410SMatthew Dillon hammer2_chain_unlock(chain);
1203e513e77eSMatthew Dillon hammer2_chain_drop(chain);
1204623d43d4SMatthew Dillon done:
120591abd410SMatthew Dillon hammer2_chain_unlock(parent);
1206e513e77eSMatthew Dillon hammer2_chain_drop(parent);
1207470dad14SMatthew Dillon
1208470dad14SMatthew Dillon if (bgsize) {
1209470dad14SMatthew Dillon hammer2_voldata_lock(hmp);
1210470dad14SMatthew Dillon hammer2_voldata_modify(hmp);
1211470dad14SMatthew Dillon hmp->voldata.allocator_free -= bgsize;
1212470dad14SMatthew Dillon hammer2_voldata_unlock(hmp);
1213470dad14SMatthew Dillon }
121491abd410SMatthew Dillon }
1215bca9f8e6SMatthew Dillon
1216bca9f8e6SMatthew Dillon /*
1217bca9f8e6SMatthew Dillon * Validate the freemap, in three stages.
1218bca9f8e6SMatthew Dillon *
1219bca9f8e6SMatthew Dillon * stage-1 ALLOCATED -> POSSIBLY FREE
1220bca9f8e6SMatthew Dillon * POSSIBLY FREE -> POSSIBLY FREE (type corrected)
1221bca9f8e6SMatthew Dillon *
1222bca9f8e6SMatthew Dillon * This transitions bitmap entries from ALLOCATED to POSSIBLY FREE.
1223bca9f8e6SMatthew Dillon * The POSSIBLY FREE state does not mean that a block is actually free
1224bca9f8e6SMatthew Dillon * and may be transitioned back to ALLOCATED in stage-2.
1225bca9f8e6SMatthew Dillon *
1226bca9f8e6SMatthew Dillon * This is typically done during normal filesystem operations when
1227bca9f8e6SMatthew Dillon * something is deleted or a block is replaced.
1228bca9f8e6SMatthew Dillon *
1229bca9f8e6SMatthew Dillon * This is done by bulkfree in-bulk after a memory-bounded meta-data
1230bca9f8e6SMatthew Dillon * scan to try to determine what might be freeable.
1231bca9f8e6SMatthew Dillon *
1232bca9f8e6SMatthew Dillon * This can be done unconditionally through a freemap scan when the
1233bca9f8e6SMatthew Dillon * intention is to brute-force recover the proper state of the freemap.
1234bca9f8e6SMatthew Dillon *
1235bca9f8e6SMatthew Dillon * stage-2 POSSIBLY FREE -> ALLOCATED (scan metadata topology)
1236bca9f8e6SMatthew Dillon *
1237bca9f8e6SMatthew Dillon * This is done by bulkfree during a meta-data scan to ensure that
1238bca9f8e6SMatthew Dillon * all blocks still actually allocated by the filesystem are marked
1239bca9f8e6SMatthew Dillon * as such.
1240bca9f8e6SMatthew Dillon *
1241bca9f8e6SMatthew Dillon * NOTE! Live filesystem transitions to POSSIBLY FREE can occur while
1242bca9f8e6SMatthew Dillon * the bulkfree stage-2 and stage-3 is running. The live filesystem
1243bca9f8e6SMatthew Dillon * will use the alternative POSSIBLY FREE type (2) to prevent
1244bca9f8e6SMatthew Dillon * stage-3 from improperly transitioning unvetted possibly-free
1245bca9f8e6SMatthew Dillon * blocks to FREE.
1246bca9f8e6SMatthew Dillon *
1247bca9f8e6SMatthew Dillon * stage-3 POSSIBLY FREE (type 1) -> FREE (scan freemap)
1248bca9f8e6SMatthew Dillon *
1249bca9f8e6SMatthew Dillon * This is done by bulkfree to finalize POSSIBLY FREE states.
1250bca9f8e6SMatthew Dillon *
1251bca9f8e6SMatthew Dillon */
1252