15c23d7f1SMatthew Dillon /* 28138a154SMatthew Dillon * Copyright (c) 2011-2014 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/fcntl.h> 395c23d7f1SMatthew Dillon #include <sys/buf.h> 405c23d7f1SMatthew Dillon #include <sys/proc.h> 415c23d7f1SMatthew Dillon #include <sys/namei.h> 425c23d7f1SMatthew Dillon #include <sys/mount.h> 435c23d7f1SMatthew Dillon #include <sys/vnode.h> 445c23d7f1SMatthew Dillon #include <sys/mountctl.h> 455c23d7f1SMatthew Dillon 465c23d7f1SMatthew Dillon #include "hammer2.h" 475c23d7f1SMatthew Dillon 488138a154SMatthew Dillon #define FREEMAP_DEBUG 0 498138a154SMatthew Dillon 5091abd410SMatthew Dillon struct hammer2_fiterate { 5191abd410SMatthew Dillon hammer2_off_t bpref; 5291abd410SMatthew Dillon hammer2_off_t bnext; 5391abd410SMatthew Dillon int loops; 5491abd410SMatthew Dillon }; 5591abd410SMatthew Dillon 5691abd410SMatthew Dillon typedef struct hammer2_fiterate hammer2_fiterate_t; 5791abd410SMatthew Dillon 58c603b86bSMatthew Dillon static int hammer2_freemap_try_alloc(hammer2_chain_t **parentp, 59e2163f5bSMatthew Dillon hammer2_blockref_t *bref, int radix, 60e2163f5bSMatthew Dillon hammer2_fiterate_t *iter, hammer2_tid_t mtid); 61c603b86bSMatthew Dillon static void hammer2_freemap_init(hammer2_dev_t *hmp, 62a5913bdfSMatthew Dillon hammer2_key_t key, hammer2_chain_t *chain); 63c603b86bSMatthew Dillon static int hammer2_bmap_alloc(hammer2_dev_t *hmp, 6491abd410SMatthew Dillon hammer2_bmap_data_t *bmap, uint16_t class, 6593f3933aSMatthew Dillon int n, int radix, hammer2_key_t *basep); 66c603b86bSMatthew Dillon static int hammer2_freemap_iterate(hammer2_chain_t **parentp, 67c603b86bSMatthew Dillon hammer2_chain_t **chainp, 6891abd410SMatthew Dillon hammer2_fiterate_t *iter); 691a7cfe5aSMatthew Dillon 70a98aa0b0SMatthew Dillon static __inline 71a98aa0b0SMatthew Dillon int 72a98aa0b0SMatthew Dillon hammer2_freemapradix(int radix) 73a98aa0b0SMatthew Dillon { 74a98aa0b0SMatthew Dillon return(radix); 75a98aa0b0SMatthew Dillon } 76a98aa0b0SMatthew Dillon 771a7cfe5aSMatthew Dillon /* 781a7cfe5aSMatthew Dillon * Calculate the device offset for the specified FREEMAP_NODE or FREEMAP_LEAF 791a7cfe5aSMatthew Dillon * bref. Return a combined media offset and physical size radix. Freemap 801a7cfe5aSMatthew Dillon * chains use fixed storage offsets in the 4MB reserved area at the 811a7cfe5aSMatthew Dillon * beginning of each 2GB zone 821a7cfe5aSMatthew Dillon * 831a7cfe5aSMatthew Dillon * Rotate between four possibilities. Theoretically this means we have three 841a7cfe5aSMatthew Dillon * good freemaps in case of a crash which we can use as a base for the fixup 851a7cfe5aSMatthew Dillon * scan at mount-time. 861a7cfe5aSMatthew Dillon */ 871a7cfe5aSMatthew Dillon #define H2FMBASE(key, radix) ((key) & ~(((hammer2_off_t)1 << (radix)) - 1)) 881a7cfe5aSMatthew Dillon #define H2FMSHIFT(radix) ((hammer2_off_t)1 << (radix)) 891a7cfe5aSMatthew Dillon 901a7cfe5aSMatthew Dillon static 911a7cfe5aSMatthew Dillon int 92c603b86bSMatthew Dillon hammer2_freemap_reserve(hammer2_chain_t *chain, int radix) 931a7cfe5aSMatthew Dillon { 94623d43d4SMatthew Dillon hammer2_blockref_t *bref = &chain->bref; 951a7cfe5aSMatthew Dillon hammer2_off_t off; 96a3fd5153SMatthew Dillon int index; 975cebbe36SMatthew Dillon int index_inc; 981a7cfe5aSMatthew Dillon size_t bytes; 991a7cfe5aSMatthew Dillon 1001a7cfe5aSMatthew Dillon /* 1015cebbe36SMatthew Dillon * Physical allocation size. 1021a7cfe5aSMatthew Dillon */ 1035cebbe36SMatthew Dillon bytes = (size_t)1 << radix; 1041a7cfe5aSMatthew Dillon 1051a7cfe5aSMatthew Dillon /* 106a71db85dSMatthew Dillon * Calculate block selection index 0..7 of current block. If this 107a71db85dSMatthew Dillon * is the first allocation of the block (verses a modification of an 108a71db85dSMatthew Dillon * existing block), we use index 0, otherwise we use the next rotating 109a71db85dSMatthew Dillon * index. 1101a7cfe5aSMatthew Dillon */ 1111a7cfe5aSMatthew Dillon if ((bref->data_off & ~HAMMER2_OFF_MASK_RADIX) == 0) { 112a3fd5153SMatthew Dillon index = 0; 1131a7cfe5aSMatthew Dillon } else { 1141a7cfe5aSMatthew Dillon off = bref->data_off & ~HAMMER2_OFF_MASK_RADIX & 115a71db85dSMatthew Dillon (((hammer2_off_t)1 << 116a71db85dSMatthew Dillon HAMMER2_FREEMAP_LEVEL1_RADIX) - 1); 1171a7cfe5aSMatthew Dillon off = off / HAMMER2_PBUFSIZE; 118a3fd5153SMatthew Dillon KKASSERT(off >= HAMMER2_ZONE_FREEMAP_00 && 1193148f677SMatthew Dillon off < HAMMER2_ZONE_FREEMAP_END); 1205031809dSMatthew Dillon index = (int)(off - HAMMER2_ZONE_FREEMAP_00) / 1215031809dSMatthew Dillon HAMMER2_ZONE_FREEMAP_INC; 1223148f677SMatthew Dillon KKASSERT(index >= 0 && index < HAMMER2_NFREEMAPS); 1233148f677SMatthew Dillon if (++index == HAMMER2_NFREEMAPS) 124a71db85dSMatthew Dillon index = 0; 125623d43d4SMatthew Dillon } 126623d43d4SMatthew Dillon 1271a7cfe5aSMatthew Dillon /* 1281a7cfe5aSMatthew Dillon * Calculate the block offset of the reserved block. This will 1291a7cfe5aSMatthew Dillon * point into the 4MB reserved area at the base of the appropriate 1301a7cfe5aSMatthew Dillon * 2GB zone, once added to the FREEMAP_x selection above. 1311a7cfe5aSMatthew Dillon */ 1325cebbe36SMatthew Dillon index_inc = index * HAMMER2_ZONE_FREEMAP_INC; 1335cebbe36SMatthew Dillon 1341a7cfe5aSMatthew Dillon switch(bref->keybits) { 1355cebbe36SMatthew Dillon /* case HAMMER2_FREEMAP_LEVEL6_RADIX: not applicable */ 1365cebbe36SMatthew Dillon case HAMMER2_FREEMAP_LEVEL5_RADIX: /* 2EB */ 1375cebbe36SMatthew Dillon KKASSERT(bref->type == HAMMER2_BREF_TYPE_FREEMAP_NODE); 1385cebbe36SMatthew Dillon KKASSERT(bytes == HAMMER2_FREEMAP_LEVELN_PSIZE); 1395cebbe36SMatthew Dillon off = H2FMBASE(bref->key, HAMMER2_FREEMAP_LEVEL5_RADIX) + 1405cebbe36SMatthew Dillon (index_inc + HAMMER2_ZONE_FREEMAP_00 + 1415cebbe36SMatthew Dillon HAMMER2_ZONEFM_LEVEL5) * HAMMER2_PBUFSIZE; 1425cebbe36SMatthew Dillon break; 1431a7cfe5aSMatthew Dillon case HAMMER2_FREEMAP_LEVEL4_RADIX: /* 2EB */ 1441a7cfe5aSMatthew Dillon KKASSERT(bref->type == HAMMER2_BREF_TYPE_FREEMAP_NODE); 1451a7cfe5aSMatthew Dillon KKASSERT(bytes == HAMMER2_FREEMAP_LEVELN_PSIZE); 146a3fd5153SMatthew Dillon off = H2FMBASE(bref->key, HAMMER2_FREEMAP_LEVEL4_RADIX) + 1475cebbe36SMatthew Dillon (index_inc + HAMMER2_ZONE_FREEMAP_00 + 148ba8a9be0SMatthew Dillon HAMMER2_ZONEFM_LEVEL4) * HAMMER2_PBUFSIZE; 1491a7cfe5aSMatthew Dillon break; 1501a7cfe5aSMatthew Dillon case HAMMER2_FREEMAP_LEVEL3_RADIX: /* 2PB */ 1511a7cfe5aSMatthew Dillon KKASSERT(bref->type == HAMMER2_BREF_TYPE_FREEMAP_NODE); 1521a7cfe5aSMatthew Dillon KKASSERT(bytes == HAMMER2_FREEMAP_LEVELN_PSIZE); 153a3fd5153SMatthew Dillon off = H2FMBASE(bref->key, HAMMER2_FREEMAP_LEVEL3_RADIX) + 1545cebbe36SMatthew Dillon (index_inc + HAMMER2_ZONE_FREEMAP_00 + 155ba8a9be0SMatthew Dillon HAMMER2_ZONEFM_LEVEL3) * HAMMER2_PBUFSIZE; 1561a7cfe5aSMatthew Dillon break; 1571a7cfe5aSMatthew Dillon case HAMMER2_FREEMAP_LEVEL2_RADIX: /* 2TB */ 1581a7cfe5aSMatthew Dillon KKASSERT(bref->type == HAMMER2_BREF_TYPE_FREEMAP_NODE); 1591a7cfe5aSMatthew Dillon KKASSERT(bytes == HAMMER2_FREEMAP_LEVELN_PSIZE); 160a3fd5153SMatthew Dillon off = H2FMBASE(bref->key, HAMMER2_FREEMAP_LEVEL2_RADIX) + 1615cebbe36SMatthew Dillon (index_inc + HAMMER2_ZONE_FREEMAP_00 + 162ba8a9be0SMatthew Dillon HAMMER2_ZONEFM_LEVEL2) * HAMMER2_PBUFSIZE; 1631a7cfe5aSMatthew Dillon break; 1641a7cfe5aSMatthew Dillon case HAMMER2_FREEMAP_LEVEL1_RADIX: /* 2GB */ 16593f3933aSMatthew Dillon KKASSERT(bref->type == HAMMER2_BREF_TYPE_FREEMAP_LEAF); 1661a7cfe5aSMatthew Dillon KKASSERT(bytes == HAMMER2_FREEMAP_LEVELN_PSIZE); 167a3fd5153SMatthew Dillon off = H2FMBASE(bref->key, HAMMER2_FREEMAP_LEVEL1_RADIX) + 1685cebbe36SMatthew Dillon (index_inc + HAMMER2_ZONE_FREEMAP_00 + 169ba8a9be0SMatthew Dillon HAMMER2_ZONEFM_LEVEL1) * HAMMER2_PBUFSIZE; 1701a7cfe5aSMatthew Dillon break; 1711a7cfe5aSMatthew Dillon default: 1721a7cfe5aSMatthew Dillon panic("freemap: bad radix(2) %p %d\n", bref, bref->keybits); 1731a7cfe5aSMatthew Dillon /* NOT REACHED */ 174a3fd5153SMatthew Dillon off = (hammer2_off_t)-1; 1751a7cfe5aSMatthew Dillon break; 1761a7cfe5aSMatthew Dillon } 1771a7cfe5aSMatthew Dillon bref->data_off = off | radix; 1788138a154SMatthew Dillon #if FREEMAP_DEBUG 1798138a154SMatthew Dillon kprintf("FREEMAP BLOCK TYPE %d %016jx/%d DATA_OFF=%016jx\n", 1808138a154SMatthew Dillon bref->type, bref->key, bref->keybits, bref->data_off); 181623d43d4SMatthew Dillon #endif 1821a7cfe5aSMatthew Dillon return (0); 1831a7cfe5aSMatthew Dillon } 1841a7cfe5aSMatthew Dillon 1855c23d7f1SMatthew Dillon /* 1861a7cfe5aSMatthew Dillon * Normal freemap allocator 1871a7cfe5aSMatthew Dillon * 1881a7cfe5aSMatthew Dillon * Use available hints to allocate space using the freemap. Create missing 1891a7cfe5aSMatthew Dillon * freemap infrastructure on-the-fly as needed (including marking initial 1901a7cfe5aSMatthew Dillon * allocations using the iterator as allocated, instantiating new 2GB zones, 1911a7cfe5aSMatthew Dillon * and dealing with the end-of-media edge case). 1921a7cfe5aSMatthew Dillon * 1931a7cfe5aSMatthew Dillon * ip and bpref are only used as a heuristic to determine locality of 1941a7cfe5aSMatthew Dillon * reference. bref->key may also be used heuristically. 1951a7cfe5aSMatthew Dillon */ 1961a7cfe5aSMatthew Dillon int 197c603b86bSMatthew Dillon hammer2_freemap_alloc(hammer2_chain_t *chain, size_t bytes) 1981a7cfe5aSMatthew Dillon { 199506bd6d1SMatthew Dillon hammer2_dev_t *hmp = chain->hmp; 200623d43d4SMatthew Dillon hammer2_blockref_t *bref = &chain->bref; 2011a7cfe5aSMatthew Dillon hammer2_chain_t *parent; 202e2163f5bSMatthew Dillon hammer2_tid_t mtid; 2031a7cfe5aSMatthew Dillon int radix; 2041a7cfe5aSMatthew Dillon int error; 20591abd410SMatthew Dillon unsigned int hindex; 20691abd410SMatthew Dillon hammer2_fiterate_t iter; 2071a7cfe5aSMatthew Dillon 208e2163f5bSMatthew Dillon mtid = hammer2_trans_sub(hmp->spmp); 209e2163f5bSMatthew Dillon 2101a7cfe5aSMatthew Dillon /* 2111a7cfe5aSMatthew Dillon * Validate the allocation size. It must be a power of 2. 21293f3933aSMatthew Dillon * 21393f3933aSMatthew Dillon * For now require that the caller be aware of the minimum 21493f3933aSMatthew Dillon * allocation (1K). 2151a7cfe5aSMatthew Dillon */ 2161a7cfe5aSMatthew Dillon radix = hammer2_getradix(bytes); 2171a7cfe5aSMatthew Dillon KKASSERT((size_t)1 << radix == bytes); 2181a7cfe5aSMatthew Dillon 2191a7cfe5aSMatthew Dillon if (bref->type == HAMMER2_BREF_TYPE_FREEMAP_NODE || 2201a7cfe5aSMatthew Dillon bref->type == HAMMER2_BREF_TYPE_FREEMAP_LEAF) { 22150456506SMatthew Dillon /* 22250456506SMatthew Dillon * Freemap blocks themselves are assigned from the reserve 22350456506SMatthew Dillon * area, not allocated from the freemap. 22450456506SMatthew Dillon */ 225c603b86bSMatthew Dillon error = hammer2_freemap_reserve(chain, radix); 22650456506SMatthew Dillon return error; 2271a7cfe5aSMatthew Dillon } 2281a7cfe5aSMatthew Dillon 22950456506SMatthew Dillon KKASSERT(bytes >= HAMMER2_ALLOC_MIN && bytes <= HAMMER2_ALLOC_MAX); 23091abd410SMatthew Dillon 23101eabad4SMatthew Dillon /* 232a98aa0b0SMatthew Dillon * Calculate the starting point for our allocation search. 233a98aa0b0SMatthew Dillon * 234a98aa0b0SMatthew Dillon * Each freemap leaf is dedicated to a specific freemap_radix. 235a98aa0b0SMatthew Dillon * The freemap_radix can be more fine-grained than the device buffer 236a98aa0b0SMatthew Dillon * radix which results in inodes being grouped together in their 237a98aa0b0SMatthew Dillon * own segment, terminal-data (16K or less) and initial indirect 238a98aa0b0SMatthew Dillon * block being grouped together, and then full-indirect and full-data 239a98aa0b0SMatthew Dillon * blocks (64K) being grouped together. 240a98aa0b0SMatthew Dillon * 241a98aa0b0SMatthew Dillon * The single most important aspect of this is the inode grouping 242a98aa0b0SMatthew Dillon * because that is what allows 'find' and 'ls' and other filesystem 243a98aa0b0SMatthew Dillon * topology operations to run fast. 2441a7cfe5aSMatthew Dillon */ 245a98aa0b0SMatthew Dillon #if 0 2461a7cfe5aSMatthew Dillon if (bref->data_off & ~HAMMER2_OFF_MASK_RADIX) 2471a7cfe5aSMatthew Dillon bpref = bref->data_off & ~HAMMER2_OFF_MASK_RADIX; 2481a7cfe5aSMatthew Dillon else if (trans->tmp_bpref) 2491a7cfe5aSMatthew Dillon bpref = trans->tmp_bpref; 2501a7cfe5aSMatthew Dillon else if (trans->tmp_ip) 2511a7cfe5aSMatthew Dillon bpref = trans->tmp_ip->chain->bref.data_off; 2521a7cfe5aSMatthew Dillon else 2531a7cfe5aSMatthew Dillon #endif 25491abd410SMatthew Dillon /* 25591abd410SMatthew Dillon * Heuristic tracking index. We would like one for each distinct 25691abd410SMatthew Dillon * bref type if possible. heur_freemap[] has room for two classes 25791abd410SMatthew Dillon * for each type. At a minimum we have to break-up our heuristic 25891abd410SMatthew Dillon * by device block sizes. 25991abd410SMatthew Dillon */ 26091abd410SMatthew Dillon hindex = hammer2_devblkradix(radix) - HAMMER2_MINIORADIX; 26191abd410SMatthew Dillon KKASSERT(hindex < HAMMER2_FREEMAP_HEUR_NRADIX); 26291abd410SMatthew Dillon hindex += bref->type * HAMMER2_FREEMAP_HEUR_NRADIX; 26391abd410SMatthew Dillon hindex &= HAMMER2_FREEMAP_HEUR_TYPES * HAMMER2_FREEMAP_HEUR_NRADIX - 1; 264*3f01ebaaSMatthew Dillon KKASSERT(hindex < HAMMER2_FREEMAP_HEUR_SIZE); 26591abd410SMatthew Dillon 26691abd410SMatthew Dillon iter.bpref = hmp->heur_freemap[hindex]; 2671a7cfe5aSMatthew Dillon 2681a7cfe5aSMatthew Dillon /* 2691a7cfe5aSMatthew Dillon * Make sure bpref is in-bounds. It's ok if bpref covers a zone's 2701a7cfe5aSMatthew Dillon * reserved area, the try code will iterate past it. 2711a7cfe5aSMatthew Dillon */ 27291abd410SMatthew Dillon if (iter.bpref > hmp->voldata.volu_size) 27391abd410SMatthew Dillon iter.bpref = hmp->voldata.volu_size - 1; 2741a7cfe5aSMatthew Dillon 2751a7cfe5aSMatthew Dillon /* 2761a7cfe5aSMatthew Dillon * Iterate the freemap looking for free space before and after. 2771a7cfe5aSMatthew Dillon */ 2781a7cfe5aSMatthew Dillon parent = &hmp->fchain; 279e513e77eSMatthew Dillon hammer2_chain_ref(parent); 2801a7cfe5aSMatthew Dillon hammer2_chain_lock(parent, HAMMER2_RESOLVE_ALWAYS); 2811a7cfe5aSMatthew Dillon error = EAGAIN; 28291abd410SMatthew Dillon iter.bnext = iter.bpref; 28391abd410SMatthew Dillon iter.loops = 0; 2841a7cfe5aSMatthew Dillon 2851a7cfe5aSMatthew Dillon while (error == EAGAIN) { 286e2163f5bSMatthew Dillon error = hammer2_freemap_try_alloc(&parent, bref, radix, 287e2163f5bSMatthew Dillon &iter, mtid); 2881a7cfe5aSMatthew Dillon } 28991abd410SMatthew Dillon hmp->heur_freemap[hindex] = iter.bnext; 2901a7cfe5aSMatthew Dillon hammer2_chain_unlock(parent); 291e513e77eSMatthew Dillon hammer2_chain_drop(parent); 2921a7cfe5aSMatthew Dillon 2931a7cfe5aSMatthew Dillon return (error); 2941a7cfe5aSMatthew Dillon } 2951a7cfe5aSMatthew Dillon 2961a7cfe5aSMatthew Dillon static int 297c603b86bSMatthew Dillon hammer2_freemap_try_alloc(hammer2_chain_t **parentp, 2981a7cfe5aSMatthew Dillon hammer2_blockref_t *bref, int radix, 299e2163f5bSMatthew Dillon hammer2_fiterate_t *iter, hammer2_tid_t mtid) 3001a7cfe5aSMatthew Dillon { 301506bd6d1SMatthew Dillon hammer2_dev_t *hmp = (*parentp)->hmp; 3021a7cfe5aSMatthew Dillon hammer2_off_t l0size; 30393f3933aSMatthew Dillon hammer2_off_t l1size; 30493f3933aSMatthew Dillon hammer2_off_t l1mask; 3051897c66eSMatthew Dillon hammer2_key_t key_dummy; 3061a7cfe5aSMatthew Dillon hammer2_chain_t *chain; 3071a7cfe5aSMatthew Dillon hammer2_off_t key; 3081a7cfe5aSMatthew Dillon size_t bytes; 30991abd410SMatthew Dillon uint16_t class; 3101a7cfe5aSMatthew Dillon int error = 0; 3111897c66eSMatthew Dillon int cache_index = -1; 3121a7cfe5aSMatthew Dillon 3131a7cfe5aSMatthew Dillon /* 3141a7cfe5aSMatthew Dillon * Calculate the number of bytes being allocated, the number 3151a7cfe5aSMatthew Dillon * of contiguous bits of bitmap being allocated, and the bitmap 3161a7cfe5aSMatthew Dillon * mask. 31701eabad4SMatthew Dillon * 3181a7cfe5aSMatthew Dillon * WARNING! cpu hardware may mask bits == 64 -> 0 and blow up the 3191a7cfe5aSMatthew Dillon * mask calculation. 3201a7cfe5aSMatthew Dillon */ 3211a7cfe5aSMatthew Dillon bytes = (size_t)1 << radix; 32291abd410SMatthew Dillon class = (bref->type << 8) | hammer2_devblkradix(radix); 323a98aa0b0SMatthew Dillon 3241a7cfe5aSMatthew Dillon /* 32593f3933aSMatthew Dillon * Lookup the level1 freemap chain, creating and initializing one 3261a7cfe5aSMatthew Dillon * if necessary. Intermediate levels will be created automatically 3271a7cfe5aSMatthew Dillon * when necessary by hammer2_chain_create(). 3281a7cfe5aSMatthew Dillon */ 32991abd410SMatthew Dillon key = H2FMBASE(iter->bnext, HAMMER2_FREEMAP_LEVEL1_RADIX); 3301a7cfe5aSMatthew Dillon l0size = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX); 33193f3933aSMatthew Dillon l1size = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX); 33293f3933aSMatthew Dillon l1mask = l1size - 1; 3331a7cfe5aSMatthew Dillon 3341897c66eSMatthew Dillon chain = hammer2_chain_lookup(parentp, &key_dummy, key, key + l1mask, 3351897c66eSMatthew Dillon &cache_index, 3361a7cfe5aSMatthew Dillon HAMMER2_LOOKUP_ALWAYS | 337b8ba9690SMatthew Dillon HAMMER2_LOOKUP_MATCHIND); 338623d43d4SMatthew Dillon 3391a7cfe5aSMatthew Dillon if (chain == NULL) { 3401a7cfe5aSMatthew Dillon /* 3411a7cfe5aSMatthew Dillon * Create the missing leaf, be sure to initialize 3421a7cfe5aSMatthew Dillon * the auxillary freemap tracking information in 3431a7cfe5aSMatthew Dillon * the bref.check.freemap structure. 3441a7cfe5aSMatthew Dillon */ 3451a7cfe5aSMatthew Dillon #if 0 34693f3933aSMatthew Dillon kprintf("freemap create L1 @ %016jx bpref %016jx\n", 34791abd410SMatthew Dillon key, iter->bpref); 3481a7cfe5aSMatthew Dillon #endif 349c603b86bSMatthew Dillon error = hammer2_chain_create(parentp, &chain, hmp->spmp, 35093f3933aSMatthew Dillon key, HAMMER2_FREEMAP_LEVEL1_RADIX, 3511a7cfe5aSMatthew Dillon HAMMER2_BREF_TYPE_FREEMAP_LEAF, 352b3659de2SMatthew Dillon HAMMER2_FREEMAP_LEVELN_PSIZE, 353*3f01ebaaSMatthew Dillon mtid, 0, 0); 3540924b3f8SMatthew Dillon KKASSERT(error == 0); 3551a7cfe5aSMatthew Dillon if (error == 0) { 356*3f01ebaaSMatthew Dillon hammer2_chain_modify(chain, mtid, 0, 0); 35793f3933aSMatthew Dillon bzero(&chain->data->bmdata[0], 35893f3933aSMatthew Dillon HAMMER2_FREEMAP_LEVELN_PSIZE); 35993f3933aSMatthew Dillon chain->bref.check.freemap.bigmask = (uint32_t)-1; 36093f3933aSMatthew Dillon chain->bref.check.freemap.avail = l1size; 36193f3933aSMatthew Dillon /* bref.methods should already be inherited */ 3621a7cfe5aSMatthew Dillon 363c603b86bSMatthew Dillon hammer2_freemap_init(hmp, key, chain); 3641a7cfe5aSMatthew Dillon } 365b93cc2e0SMatthew Dillon } else if (chain->error) { 366b93cc2e0SMatthew Dillon /* 367b93cc2e0SMatthew Dillon * Error during lookup. 368b93cc2e0SMatthew Dillon */ 369b93cc2e0SMatthew Dillon kprintf("hammer2_freemap_try_alloc: %016jx: error %s\n", 370b93cc2e0SMatthew Dillon (intmax_t)bref->data_off, 371b93cc2e0SMatthew Dillon hammer2_error_str(chain->error)); 372b93cc2e0SMatthew Dillon error = EIO; 3735cebbe36SMatthew Dillon } else if ((chain->bref.check.freemap.bigmask & 3745cebbe36SMatthew Dillon ((size_t)1 << radix)) == 0) { 3751a7cfe5aSMatthew Dillon /* 3761a7cfe5aSMatthew Dillon * Already flagged as not having enough space 3771a7cfe5aSMatthew Dillon */ 3781a7cfe5aSMatthew Dillon error = ENOSPC; 3791a7cfe5aSMatthew Dillon } else { 3801a7cfe5aSMatthew Dillon /* 3811a7cfe5aSMatthew Dillon * Modify existing chain to setup for adjustment. 3821a7cfe5aSMatthew Dillon */ 383*3f01ebaaSMatthew Dillon hammer2_chain_modify(chain, mtid, 0, 0); 3841a7cfe5aSMatthew Dillon } 3851a7cfe5aSMatthew Dillon 3861a7cfe5aSMatthew Dillon /* 38793f3933aSMatthew Dillon * Scan 2MB entries. 3881a7cfe5aSMatthew Dillon */ 38993f3933aSMatthew Dillon if (error == 0) { 39093f3933aSMatthew Dillon hammer2_bmap_data_t *bmap; 39193f3933aSMatthew Dillon hammer2_key_t base_key; 39293f3933aSMatthew Dillon int count; 39393f3933aSMatthew Dillon int start; 39493f3933aSMatthew Dillon int n; 3951a7cfe5aSMatthew Dillon 39610136ab6SMatthew Dillon KKASSERT(chain->bref.type == HAMMER2_BREF_TYPE_FREEMAP_LEAF); 39791abd410SMatthew Dillon start = (int)((iter->bnext - key) >> 39891abd410SMatthew Dillon HAMMER2_FREEMAP_LEVEL0_RADIX); 39993f3933aSMatthew Dillon KKASSERT(start >= 0 && start < HAMMER2_FREEMAP_COUNT); 400*3f01ebaaSMatthew Dillon hammer2_chain_modify(chain, mtid, 0, 0); 4011a7cfe5aSMatthew Dillon 4021a7cfe5aSMatthew Dillon error = ENOSPC; 40393f3933aSMatthew Dillon for (count = 0; count < HAMMER2_FREEMAP_COUNT; ++count) { 404271568b1SMatthew Dillon int availchk; 405271568b1SMatthew Dillon 40693f3933aSMatthew Dillon if (start + count >= HAMMER2_FREEMAP_COUNT && 40793f3933aSMatthew Dillon start - count < 0) { 40893f3933aSMatthew Dillon break; 40993f3933aSMatthew Dillon } 410271568b1SMatthew Dillon 411271568b1SMatthew Dillon /* 412271568b1SMatthew Dillon * Calculate bmap pointer 413271568b1SMatthew Dillon * 414271568b1SMatthew Dillon * NOTE: bmap pointer is invalid if n >= FREEMAP_COUNT. 415271568b1SMatthew Dillon */ 41693f3933aSMatthew Dillon n = start + count; 41793f3933aSMatthew Dillon bmap = &chain->data->bmdata[n]; 418271568b1SMatthew Dillon 419271568b1SMatthew Dillon if (n >= HAMMER2_FREEMAP_COUNT) { 420271568b1SMatthew Dillon availchk = 0; 421271568b1SMatthew Dillon } else if (bmap->avail) { 422271568b1SMatthew Dillon availchk = 1; 423271568b1SMatthew Dillon } else if (radix < HAMMER2_FREEMAP_BLOCK_RADIX && 424271568b1SMatthew Dillon (bmap->linear & HAMMER2_FREEMAP_BLOCK_MASK)) { 425271568b1SMatthew Dillon availchk = 1; 426271568b1SMatthew Dillon } else { 427271568b1SMatthew Dillon availchk = 0; 428271568b1SMatthew Dillon } 429271568b1SMatthew Dillon 430271568b1SMatthew Dillon if (availchk && 43191abd410SMatthew Dillon (bmap->class == 0 || bmap->class == class)) { 43293f3933aSMatthew Dillon base_key = key + n * l0size; 433c603b86bSMatthew Dillon error = hammer2_bmap_alloc(hmp, bmap, 43491abd410SMatthew Dillon class, n, radix, 43591abd410SMatthew Dillon &base_key); 43693f3933aSMatthew Dillon if (error != ENOSPC) { 43793f3933aSMatthew Dillon key = base_key; 43893f3933aSMatthew Dillon break; 43993f3933aSMatthew Dillon } 44093f3933aSMatthew Dillon } 441271568b1SMatthew Dillon 442271568b1SMatthew Dillon /* 443271568b1SMatthew Dillon * Must recalculate after potentially having called 444271568b1SMatthew Dillon * hammer2_bmap_alloc() above in case chain was 445271568b1SMatthew Dillon * reallocated. 446271568b1SMatthew Dillon * 447271568b1SMatthew Dillon * NOTE: bmap pointer is invalid if n < 0. 448271568b1SMatthew Dillon */ 44993f3933aSMatthew Dillon n = start - count; 45093f3933aSMatthew Dillon bmap = &chain->data->bmdata[n]; 451271568b1SMatthew Dillon if (n < 0) { 452271568b1SMatthew Dillon availchk = 0; 453271568b1SMatthew Dillon } else if (bmap->avail) { 454271568b1SMatthew Dillon availchk = 1; 455271568b1SMatthew Dillon } else if (radix < HAMMER2_FREEMAP_BLOCK_RADIX && 456271568b1SMatthew Dillon (bmap->linear & HAMMER2_FREEMAP_BLOCK_MASK)) { 457271568b1SMatthew Dillon availchk = 1; 458271568b1SMatthew Dillon } else { 459271568b1SMatthew Dillon availchk = 0; 460271568b1SMatthew Dillon } 461271568b1SMatthew Dillon 462271568b1SMatthew Dillon if (availchk && 46391abd410SMatthew Dillon (bmap->class == 0 || bmap->class == class)) { 46493f3933aSMatthew Dillon base_key = key + n * l0size; 465c603b86bSMatthew Dillon error = hammer2_bmap_alloc(hmp, bmap, 46691abd410SMatthew Dillon class, n, radix, 46791abd410SMatthew Dillon &base_key); 46893f3933aSMatthew Dillon if (error != ENOSPC) { 46993f3933aSMatthew Dillon key = base_key; 47093f3933aSMatthew Dillon break; 47193f3933aSMatthew Dillon } 47293f3933aSMatthew Dillon } 47393f3933aSMatthew Dillon } 4745cebbe36SMatthew Dillon if (error == ENOSPC) { 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 && 4891a7cfe5aSMatthew Dillon key + bytes <= hmp->voldata.volu_size); 4901a7cfe5aSMatthew Dillon KKASSERT((key & HAMMER2_ZONE_MASK64) >= HAMMER2_ZONE_SEG); 4911a7cfe5aSMatthew Dillon bref->data_off = key | radix; 4921a7cfe5aSMatthew Dillon 4931a7cfe5aSMatthew Dillon #if 0 49493f3933aSMatthew Dillon kprintf("alloc cp=%p %016jx %016jx using %016jx\n", 4951a7cfe5aSMatthew Dillon chain, 49693f3933aSMatthew Dillon bref->key, bref->data_off, chain->bref.data_off); 4971a7cfe5aSMatthew Dillon #endif 4981a7cfe5aSMatthew Dillon } else if (error == ENOSPC) { 4991a7cfe5aSMatthew Dillon /* 50091abd410SMatthew Dillon * Return EAGAIN with next iteration in iter->bnext, or 5011a7cfe5aSMatthew Dillon * return ENOSPC if the allocation map has been exhausted. 5021a7cfe5aSMatthew Dillon */ 503c603b86bSMatthew Dillon error = hammer2_freemap_iterate(parentp, &chain, iter); 5041a7cfe5aSMatthew Dillon } 5051a7cfe5aSMatthew Dillon 5061a7cfe5aSMatthew Dillon /* 5071a7cfe5aSMatthew Dillon * Cleanup 5081a7cfe5aSMatthew Dillon */ 509e513e77eSMatthew Dillon if (chain) { 5101a7cfe5aSMatthew Dillon hammer2_chain_unlock(chain); 511e513e77eSMatthew Dillon hammer2_chain_drop(chain); 512e513e77eSMatthew Dillon } 5131a7cfe5aSMatthew Dillon return (error); 5141a7cfe5aSMatthew Dillon } 5151a7cfe5aSMatthew Dillon 51693f3933aSMatthew Dillon /* 51793f3933aSMatthew Dillon * Allocate (1<<radix) bytes from the bmap whos base data offset is (*basep). 51893f3933aSMatthew Dillon * 51993f3933aSMatthew Dillon * If the linear iterator is mid-block we use it directly (the bitmap should 52093f3933aSMatthew Dillon * already be marked allocated), otherwise we search for a block in the bitmap 52193f3933aSMatthew Dillon * that fits the allocation request. 52293f3933aSMatthew Dillon * 52393f3933aSMatthew Dillon * A partial bitmap allocation sets the minimum bitmap granularity (16KB) 52493f3933aSMatthew Dillon * to fully allocated and adjusts the linear allocator to allow the 52593f3933aSMatthew Dillon * remaining space to be allocated. 52693f3933aSMatthew Dillon */ 52793f3933aSMatthew Dillon static 52893f3933aSMatthew Dillon int 529c603b86bSMatthew Dillon hammer2_bmap_alloc(hammer2_dev_t *hmp, hammer2_bmap_data_t *bmap, 53091abd410SMatthew Dillon uint16_t class, int n, int radix, hammer2_key_t *basep) 53193f3933aSMatthew Dillon { 532fdf62707SMatthew Dillon hammer2_io_t *dio; 53393f3933aSMatthew Dillon size_t size; 534271568b1SMatthew Dillon size_t bgsize; 53593f3933aSMatthew Dillon int bmradix; 5365cebbe36SMatthew Dillon hammer2_bitmap_t bmmask; 53793f3933aSMatthew Dillon int offset; 538fdf62707SMatthew Dillon int error; 53993f3933aSMatthew Dillon int i; 54093f3933aSMatthew Dillon int j; 54193f3933aSMatthew Dillon 54293f3933aSMatthew Dillon /* 54393f3933aSMatthew Dillon * Take into account 2-bits per block when calculating bmradix. 54493f3933aSMatthew Dillon */ 54593f3933aSMatthew Dillon size = (size_t)1 << radix; 54691abd410SMatthew Dillon 54793f3933aSMatthew Dillon if (radix <= HAMMER2_FREEMAP_BLOCK_RADIX) { 54893f3933aSMatthew Dillon bmradix = 2; 54993f3933aSMatthew Dillon /* (16K) 2 bits per allocation block */ 55093f3933aSMatthew Dillon } else { 5515cebbe36SMatthew Dillon bmradix = (hammer2_bitmap_t)2 << 5525cebbe36SMatthew Dillon (radix - HAMMER2_FREEMAP_BLOCK_RADIX); 55393f3933aSMatthew Dillon /* (32K-256K) 4, 8, 16, 32 bits per allocation block */ 55493f3933aSMatthew Dillon } 55593f3933aSMatthew Dillon 55693f3933aSMatthew Dillon /* 55791abd410SMatthew Dillon * Use the linear iterator to pack small allocations, otherwise 55891abd410SMatthew Dillon * fall-back to finding a free 16KB chunk. The linear iterator 55991abd410SMatthew Dillon * is only valid when *NOT* on a freemap chunking boundary (16KB). 56091abd410SMatthew Dillon * If it is the bitmap must be scanned. It can become invalid 56191abd410SMatthew Dillon * once we pack to the boundary. We adjust it after a bitmap 56291abd410SMatthew Dillon * allocation only for sub-16KB allocations (so the perfectly good 56391abd410SMatthew Dillon * previous value can still be used for fragments when 16KB+ 56491abd410SMatthew Dillon * allocations are made). 56591abd410SMatthew Dillon * 5665cebbe36SMatthew Dillon * Beware of hardware artifacts when bmradix == 64 (intermediate 56791abd410SMatthew Dillon * result can wind up being '1' instead of '0' if hardware masks 56891abd410SMatthew Dillon * bit-count & 31). 56993f3933aSMatthew Dillon * 57093f3933aSMatthew Dillon * NOTE: j needs to be even in the j= calculation. As an artifact 57193f3933aSMatthew Dillon * of the /2 division, our bitmask has to clear bit 0. 57291abd410SMatthew Dillon * 57391abd410SMatthew Dillon * NOTE: TODO this can leave little unallocatable fragments lying 57491abd410SMatthew Dillon * around. 57593f3933aSMatthew Dillon */ 57691abd410SMatthew Dillon if (((uint32_t)bmap->linear & HAMMER2_FREEMAP_BLOCK_MASK) + size <= 57791abd410SMatthew Dillon HAMMER2_FREEMAP_BLOCK_SIZE && 5782c6f594dSMatthew Dillon (bmap->linear & HAMMER2_FREEMAP_BLOCK_MASK) && 57991abd410SMatthew Dillon bmap->linear < HAMMER2_SEGSIZE) { 58093f3933aSMatthew Dillon KKASSERT(bmap->linear >= 0 && 58191abd410SMatthew Dillon bmap->linear + size <= HAMMER2_SEGSIZE && 58250456506SMatthew Dillon (bmap->linear & (HAMMER2_ALLOC_MIN - 1)) == 0); 58393f3933aSMatthew Dillon offset = bmap->linear; 58493f3933aSMatthew Dillon i = offset / (HAMMER2_SEGSIZE / 8); 58593f3933aSMatthew Dillon j = (offset / (HAMMER2_FREEMAP_BLOCK_SIZE / 2)) & 30; 5865cebbe36SMatthew Dillon bmmask = (bmradix == HAMMER2_BMAP_BITS_PER_ELEMENT) ? 5875cebbe36SMatthew Dillon HAMMER2_BMAP_ALLONES : 5885cebbe36SMatthew Dillon ((hammer2_bitmap_t)1 << bmradix) - 1; 58993f3933aSMatthew Dillon bmmask <<= j; 59091abd410SMatthew Dillon bmap->linear = offset + size; 59193f3933aSMatthew Dillon } else { 5925cebbe36SMatthew Dillon for (i = 0; i < HAMMER2_BMAP_ELEMENTS; ++i) { 5935cebbe36SMatthew Dillon bmmask = (bmradix == HAMMER2_BMAP_BITS_PER_ELEMENT) ? 5945cebbe36SMatthew Dillon HAMMER2_BMAP_ALLONES : 5955cebbe36SMatthew Dillon ((hammer2_bitmap_t)1 << bmradix) - 1; 5965cebbe36SMatthew Dillon for (j = 0; 5975cebbe36SMatthew Dillon j < HAMMER2_BMAP_BITS_PER_ELEMENT; 5985cebbe36SMatthew Dillon j += bmradix) { 5995cebbe36SMatthew Dillon if ((bmap->bitmapq[i] & bmmask) == 0) 60093f3933aSMatthew Dillon goto success; 60193f3933aSMatthew Dillon bmmask <<= bmradix; 60293f3933aSMatthew Dillon } 60393f3933aSMatthew Dillon } 60491abd410SMatthew Dillon /*fragments might remain*/ 60591abd410SMatthew Dillon /*KKASSERT(bmap->avail == 0);*/ 60693f3933aSMatthew Dillon return (ENOSPC); 60793f3933aSMatthew Dillon success: 6085cebbe36SMatthew Dillon offset = i * (HAMMER2_SEGSIZE / HAMMER2_BMAP_ELEMENTS) + 60993f3933aSMatthew Dillon (j * (HAMMER2_FREEMAP_BLOCK_SIZE / 2)); 61091abd410SMatthew Dillon if (size & HAMMER2_FREEMAP_BLOCK_MASK) 61191abd410SMatthew Dillon bmap->linear = offset + size; 61293f3933aSMatthew Dillon } 61393f3933aSMatthew Dillon 6145cebbe36SMatthew Dillon /* 8 x (64/2) -> 256 x 16K -> 4MB */ 6155cebbe36SMatthew Dillon KKASSERT(i >= 0 && i < HAMMER2_BMAP_ELEMENTS); 61693f3933aSMatthew Dillon 61793f3933aSMatthew Dillon /* 61893f3933aSMatthew Dillon * Optimize the buffer cache to avoid unnecessary read-before-write 61993f3933aSMatthew Dillon * operations. 62091abd410SMatthew Dillon * 62191abd410SMatthew Dillon * The device block size could be larger than the allocation size 62291abd410SMatthew Dillon * so the actual bitmap test is somewhat more involved. We have 62391abd410SMatthew Dillon * to use a compatible buffer size for this operation. 62493f3933aSMatthew Dillon */ 6255cebbe36SMatthew Dillon if ((bmap->bitmapq[i] & bmmask) == 0 && 6262c6f594dSMatthew Dillon hammer2_devblksize(size) != size) { 62791abd410SMatthew Dillon size_t psize = hammer2_devblksize(size); 62891abd410SMatthew Dillon hammer2_off_t pmask = (hammer2_off_t)psize - 1; 6295cebbe36SMatthew Dillon int pbmradix = (hammer2_bitmap_t)2 << 6305cebbe36SMatthew Dillon (hammer2_devblkradix(radix) - 63191abd410SMatthew Dillon HAMMER2_FREEMAP_BLOCK_RADIX); 6325cebbe36SMatthew Dillon hammer2_bitmap_t pbmmask; 633fdf62707SMatthew Dillon int pradix = hammer2_getradix(psize); 63491abd410SMatthew Dillon 6355cebbe36SMatthew Dillon pbmmask = (pbmradix == HAMMER2_BMAP_BITS_PER_ELEMENT) ? 6365cebbe36SMatthew Dillon HAMMER2_BMAP_ALLONES : 6375cebbe36SMatthew Dillon ((hammer2_bitmap_t)1 << pbmradix) - 1; 63891abd410SMatthew Dillon while ((pbmmask & bmmask) == 0) 63991abd410SMatthew Dillon pbmmask <<= pbmradix; 64091abd410SMatthew Dillon 6412c6f594dSMatthew Dillon #if 0 6425cebbe36SMatthew Dillon kprintf("%016jx mask %016jx %016jx %016jx (%zd/%zd)\n", 6435cebbe36SMatthew Dillon *basep + offset, bmap->bitmapq[i], 6442c6f594dSMatthew Dillon pbmmask, bmmask, size, psize); 6452c6f594dSMatthew Dillon #endif 6462c6f594dSMatthew Dillon 6475cebbe36SMatthew Dillon if ((bmap->bitmapq[i] & pbmmask) == 0) { 648fdf62707SMatthew Dillon error = hammer2_io_newq(hmp, 649fdf62707SMatthew Dillon (*basep + (offset & ~pmask)) | 650fdf62707SMatthew Dillon pradix, 651fdf62707SMatthew Dillon psize, &dio); 652fdf62707SMatthew Dillon hammer2_io_bqrelse(&dio); 65393f3933aSMatthew Dillon } 65491abd410SMatthew Dillon } 65593f3933aSMatthew Dillon 65693f3933aSMatthew Dillon #if 0 65793f3933aSMatthew Dillon /* 65893f3933aSMatthew Dillon * When initializing a new inode segment also attempt to initialize 65993f3933aSMatthew Dillon * an adjacent segment. Be careful not to index beyond the array 66093f3933aSMatthew Dillon * bounds. 66193f3933aSMatthew Dillon * 66293f3933aSMatthew Dillon * We do this to try to localize inode accesses to improve 66393f3933aSMatthew Dillon * directory scan rates. XXX doesn't improve scan rates. 66493f3933aSMatthew Dillon */ 66593f3933aSMatthew Dillon if (size == HAMMER2_INODE_BYTES) { 66693f3933aSMatthew Dillon if (n & 1) { 66793f3933aSMatthew Dillon if (bmap[-1].radix == 0 && bmap[-1].avail) 66893f3933aSMatthew Dillon bmap[-1].radix = radix; 66993f3933aSMatthew Dillon } else { 67093f3933aSMatthew Dillon if (bmap[1].radix == 0 && bmap[1].avail) 67193f3933aSMatthew Dillon bmap[1].radix = radix; 67293f3933aSMatthew Dillon } 67393f3933aSMatthew Dillon } 67493f3933aSMatthew Dillon #endif 675271568b1SMatthew Dillon /* 676271568b1SMatthew Dillon * Calculate the bitmap-granular change in bgsize for the volume 677271568b1SMatthew Dillon * header. We cannot use the fine-grained change here because 678271568b1SMatthew Dillon * the bulkfree code can't undo it. If the bitmap element is already 679271568b1SMatthew Dillon * marked allocated it has already been accounted for. 680271568b1SMatthew Dillon */ 681271568b1SMatthew Dillon if (radix < HAMMER2_FREEMAP_BLOCK_RADIX) { 6825cebbe36SMatthew Dillon if (bmap->bitmapq[i] & bmmask) 683271568b1SMatthew Dillon bgsize = 0; 684271568b1SMatthew Dillon else 685271568b1SMatthew Dillon bgsize = HAMMER2_FREEMAP_BLOCK_SIZE; 686271568b1SMatthew Dillon } else { 687271568b1SMatthew Dillon bgsize = size; 688271568b1SMatthew Dillon } 68993f3933aSMatthew Dillon 69093f3933aSMatthew Dillon /* 691271568b1SMatthew Dillon * Adjust the bitmap, set the class (it might have been 0), 692271568b1SMatthew Dillon * and available bytes, update the allocation offset (*basep) 693271568b1SMatthew Dillon * from the L0 base to the actual offset. 694271568b1SMatthew Dillon * 695271568b1SMatthew Dillon * avail must reflect the bitmap-granular availability. The allocator 696271568b1SMatthew Dillon * tests will also check the linear iterator. 69793f3933aSMatthew Dillon */ 6985cebbe36SMatthew Dillon bmap->bitmapq[i] |= bmmask; 69991abd410SMatthew Dillon bmap->class = class; 700271568b1SMatthew Dillon bmap->avail -= bgsize; 70193f3933aSMatthew Dillon *basep += offset; 70293f3933aSMatthew Dillon 703271568b1SMatthew Dillon /* 704271568b1SMatthew Dillon * Adjust the volume header's allocator_free parameter. This 705271568b1SMatthew Dillon * parameter has to be fixed up by bulkfree which has no way to 706271568b1SMatthew Dillon * figure out sub-16K chunking, so it must be adjusted by the 707271568b1SMatthew Dillon * bitmap-granular size. 708271568b1SMatthew Dillon */ 709271568b1SMatthew Dillon if (bgsize) { 7109f604b01SMatthew Dillon hammer2_voldata_lock(hmp); 71150456506SMatthew Dillon hammer2_voldata_modify(hmp); 712271568b1SMatthew Dillon hmp->voldata.allocator_free -= bgsize; 71350456506SMatthew Dillon hammer2_voldata_unlock(hmp); 714271568b1SMatthew Dillon } 7159f604b01SMatthew Dillon 71693f3933aSMatthew Dillon return(0); 71793f3933aSMatthew Dillon } 71893f3933aSMatthew Dillon 71993f3933aSMatthew Dillon static 72093f3933aSMatthew Dillon void 721c603b86bSMatthew Dillon hammer2_freemap_init(hammer2_dev_t *hmp, hammer2_key_t key, 722c603b86bSMatthew Dillon hammer2_chain_t *chain) 72393f3933aSMatthew Dillon { 72493f3933aSMatthew Dillon hammer2_off_t l1size; 72593f3933aSMatthew Dillon hammer2_off_t lokey; 72693f3933aSMatthew Dillon hammer2_off_t hikey; 72793f3933aSMatthew Dillon hammer2_bmap_data_t *bmap; 72893f3933aSMatthew Dillon int count; 72993f3933aSMatthew Dillon 73093f3933aSMatthew Dillon l1size = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX); 73193f3933aSMatthew Dillon 73293f3933aSMatthew Dillon /* 73393f3933aSMatthew Dillon * Calculate the portion of the 2GB map that should be initialized 73493f3933aSMatthew Dillon * as free. Portions below or after will be initialized as allocated. 73593f3933aSMatthew Dillon * SEGMASK-align the areas so we don't have to worry about sub-scans 73693f3933aSMatthew Dillon * or endianess when using memset. 73793f3933aSMatthew Dillon * 73893f3933aSMatthew Dillon * (1) Ensure that all statically allocated space from newfs_hammer2 73993f3933aSMatthew Dillon * is marked allocated. 74093f3933aSMatthew Dillon * 74193f3933aSMatthew Dillon * (2) Ensure that the reserved area is marked allocated (typically 74293f3933aSMatthew Dillon * the first 4MB of the 2GB area being represented). 74393f3933aSMatthew Dillon * 74493f3933aSMatthew Dillon * (3) Ensure that any trailing space at the end-of-volume is marked 74593f3933aSMatthew Dillon * allocated. 74693f3933aSMatthew Dillon * 74793f3933aSMatthew Dillon * WARNING! It is possible for lokey to be larger than hikey if the 74893f3933aSMatthew Dillon * entire 2GB segment is within the static allocation. 74993f3933aSMatthew Dillon */ 750a5913bdfSMatthew Dillon lokey = (hmp->voldata.allocator_beg + HAMMER2_SEGMASK64) & 75193f3933aSMatthew Dillon ~HAMMER2_SEGMASK64; 75293f3933aSMatthew Dillon 75393f3933aSMatthew Dillon if (lokey < H2FMBASE(key, HAMMER2_FREEMAP_LEVEL1_RADIX) + 75493f3933aSMatthew Dillon HAMMER2_ZONE_SEG64) { 75593f3933aSMatthew Dillon lokey = H2FMBASE(key, HAMMER2_FREEMAP_LEVEL1_RADIX) + 75693f3933aSMatthew Dillon HAMMER2_ZONE_SEG64; 75793f3933aSMatthew Dillon } 75893f3933aSMatthew Dillon 75993f3933aSMatthew Dillon hikey = key + H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX); 760a5913bdfSMatthew Dillon if (hikey > hmp->voldata.volu_size) { 761a5913bdfSMatthew Dillon hikey = hmp->voldata.volu_size & ~HAMMER2_SEGMASK64; 76293f3933aSMatthew Dillon } 76393f3933aSMatthew Dillon 76493f3933aSMatthew Dillon chain->bref.check.freemap.avail = 76593f3933aSMatthew Dillon H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX); 76693f3933aSMatthew Dillon bmap = &chain->data->bmdata[0]; 76793f3933aSMatthew Dillon 76893f3933aSMatthew Dillon for (count = 0; count < HAMMER2_FREEMAP_COUNT; ++count) { 76993f3933aSMatthew Dillon if (key < lokey || key >= hikey) { 7705cebbe36SMatthew Dillon memset(bmap->bitmapq, -1, 7715cebbe36SMatthew Dillon sizeof(bmap->bitmapq)); 77293f3933aSMatthew Dillon bmap->avail = 0; 7732c6f594dSMatthew Dillon bmap->linear = HAMMER2_SEGSIZE; 77493f3933aSMatthew Dillon chain->bref.check.freemap.avail -= 77593f3933aSMatthew Dillon H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX); 77693f3933aSMatthew Dillon } else { 77793f3933aSMatthew Dillon bmap->avail = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX); 77893f3933aSMatthew Dillon } 77993f3933aSMatthew Dillon key += H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX); 78093f3933aSMatthew Dillon ++bmap; 78193f3933aSMatthew Dillon } 78293f3933aSMatthew Dillon } 78393f3933aSMatthew Dillon 78493f3933aSMatthew Dillon /* 78593f3933aSMatthew Dillon * The current Level 1 freemap has been exhausted, iterate to the next 78693f3933aSMatthew Dillon * one, return ENOSPC if no freemaps remain. 78793f3933aSMatthew Dillon * 78893f3933aSMatthew Dillon * XXX this should rotate back to the beginning to handle freed-up space 78993f3933aSMatthew Dillon * XXX or use intermediate entries to locate free space. TODO 79093f3933aSMatthew Dillon */ 7911a7cfe5aSMatthew Dillon static int 792c603b86bSMatthew Dillon hammer2_freemap_iterate(hammer2_chain_t **parentp, hammer2_chain_t **chainp, 793c603b86bSMatthew Dillon hammer2_fiterate_t *iter) 7941a7cfe5aSMatthew Dillon { 795506bd6d1SMatthew Dillon hammer2_dev_t *hmp = (*parentp)->hmp; 796a5913bdfSMatthew Dillon 79791abd410SMatthew Dillon iter->bnext &= ~(H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX) - 1); 79891abd410SMatthew Dillon iter->bnext += H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX); 79991abd410SMatthew Dillon if (iter->bnext >= hmp->voldata.volu_size) { 80091abd410SMatthew Dillon iter->bnext = 0; 80191abd410SMatthew Dillon if (++iter->loops == 2) 8021a7cfe5aSMatthew Dillon return (ENOSPC); 80391abd410SMatthew Dillon } 8041a7cfe5aSMatthew Dillon return(EAGAIN); 80537aa19dfSMatthew Dillon } 8061a7cfe5aSMatthew Dillon 80791abd410SMatthew Dillon /* 808877eacb6SMatthew Dillon * Adjust the bit-pattern for data in the freemap bitmap according to 809877eacb6SMatthew Dillon * (how). This code is called from on-mount recovery to fixup (mark 810877eacb6SMatthew Dillon * as allocated) blocks whos freemap upates might not have been committed 811877eacb6SMatthew Dillon * in the last crash and is used by the bulk freemap scan to stage frees. 81291abd410SMatthew Dillon * 81391abd410SMatthew Dillon * XXX currently disabled when how == 0 (the normal real-time case). At 81491abd410SMatthew Dillon * the moment we depend on the bulk freescan to actually free blocks. It 81591abd410SMatthew Dillon * will still call this routine with a non-zero how to stage possible frees 81691abd410SMatthew Dillon * and to do the actual free. 81791abd410SMatthew Dillon */ 818004f88b4SMatthew Dillon void 819e2163f5bSMatthew Dillon hammer2_freemap_adjust(hammer2_dev_t *hmp, hammer2_blockref_t *bref, 820e2163f5bSMatthew Dillon int how) 821004f88b4SMatthew Dillon { 82291abd410SMatthew Dillon hammer2_off_t data_off = bref->data_off; 82391abd410SMatthew Dillon hammer2_chain_t *chain; 82491abd410SMatthew Dillon hammer2_chain_t *parent; 82591abd410SMatthew Dillon hammer2_bmap_data_t *bmap; 82691abd410SMatthew Dillon hammer2_key_t key; 8271897c66eSMatthew Dillon hammer2_key_t key_dummy; 82891abd410SMatthew Dillon hammer2_off_t l0size; 82991abd410SMatthew Dillon hammer2_off_t l1size; 83091abd410SMatthew Dillon hammer2_off_t l1mask; 831e2163f5bSMatthew Dillon hammer2_tid_t mtid; 8325cebbe36SMatthew Dillon hammer2_bitmap_t *bitmap; 8335cebbe36SMatthew Dillon const hammer2_bitmap_t bmmask00 = 0; 8345cebbe36SMatthew Dillon hammer2_bitmap_t bmmask01; 8355cebbe36SMatthew Dillon hammer2_bitmap_t bmmask10; 8365cebbe36SMatthew Dillon hammer2_bitmap_t bmmask11; 83791abd410SMatthew Dillon size_t bytes; 83891abd410SMatthew Dillon uint16_t class; 839004f88b4SMatthew Dillon int radix; 84091abd410SMatthew Dillon int start; 84191abd410SMatthew Dillon int count; 84291abd410SMatthew Dillon int modified = 0; 8431897c66eSMatthew Dillon int cache_index = -1; 84410136ab6SMatthew Dillon int error; 845004f88b4SMatthew Dillon 846271568b1SMatthew Dillon KKASSERT(how == HAMMER2_FREEMAP_DORECOVER); 847271568b1SMatthew Dillon 848e2163f5bSMatthew Dillon mtid = hammer2_trans_sub(hmp->spmp); 849e2163f5bSMatthew Dillon 850004f88b4SMatthew Dillon radix = (int)data_off & HAMMER2_OFF_MASK_RADIX; 851004f88b4SMatthew Dillon data_off &= ~HAMMER2_OFF_MASK_RADIX; 85250456506SMatthew Dillon KKASSERT(radix <= HAMMER2_RADIX_MAX); 853004f88b4SMatthew Dillon 85491abd410SMatthew Dillon bytes = (size_t)1 << radix; 85591abd410SMatthew Dillon class = (bref->type << 8) | hammer2_devblkradix(radix); 856004f88b4SMatthew Dillon 8575c23d7f1SMatthew Dillon /* 85810136ab6SMatthew Dillon * We can't adjust thre freemap for data allocations made by 85910136ab6SMatthew Dillon * newfs_hammer2. 860355d67fcSMatthew Dillon */ 861355d67fcSMatthew Dillon if (data_off < hmp->voldata.allocator_beg) 862355d67fcSMatthew Dillon return; 863355d67fcSMatthew Dillon 86410136ab6SMatthew Dillon KKASSERT((data_off & HAMMER2_ZONE_MASK64) >= HAMMER2_ZONE_SEG); 865a7720be7SMatthew Dillon 866355d67fcSMatthew Dillon /* 86791abd410SMatthew Dillon * Lookup the level1 freemap chain. The chain must exist. 8685c23d7f1SMatthew Dillon */ 86991abd410SMatthew Dillon key = H2FMBASE(data_off, HAMMER2_FREEMAP_LEVEL1_RADIX); 87091abd410SMatthew Dillon l0size = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL0_RADIX); 87191abd410SMatthew Dillon l1size = H2FMSHIFT(HAMMER2_FREEMAP_LEVEL1_RADIX); 87291abd410SMatthew Dillon l1mask = l1size - 1; 87391abd410SMatthew Dillon 87491abd410SMatthew Dillon parent = &hmp->fchain; 875e513e77eSMatthew Dillon hammer2_chain_ref(parent); 87691abd410SMatthew Dillon hammer2_chain_lock(parent, HAMMER2_RESOLVE_ALWAYS); 87791abd410SMatthew Dillon 8781897c66eSMatthew Dillon chain = hammer2_chain_lookup(&parent, &key_dummy, key, key + l1mask, 8791897c66eSMatthew Dillon &cache_index, 88091abd410SMatthew Dillon HAMMER2_LOOKUP_ALWAYS | 881b8ba9690SMatthew Dillon HAMMER2_LOOKUP_MATCHIND); 88210136ab6SMatthew Dillon 88310136ab6SMatthew Dillon /* 88410136ab6SMatthew Dillon * Stop early if we are trying to free something but no leaf exists. 88510136ab6SMatthew Dillon */ 88610136ab6SMatthew Dillon if (chain == NULL && how != HAMMER2_FREEMAP_DORECOVER) { 88710136ab6SMatthew Dillon kprintf("hammer2_freemap_adjust: %016jx: no chain\n", 88891abd410SMatthew Dillon (intmax_t)bref->data_off); 889623d43d4SMatthew Dillon goto done; 89091abd410SMatthew Dillon } 891b93cc2e0SMatthew Dillon if (chain->error) { 892b93cc2e0SMatthew Dillon kprintf("hammer2_freemap_adjust: %016jx: error %s\n", 893b93cc2e0SMatthew Dillon (intmax_t)bref->data_off, 894b93cc2e0SMatthew Dillon hammer2_error_str(chain->error)); 895b93cc2e0SMatthew Dillon hammer2_chain_unlock(chain); 896e513e77eSMatthew Dillon hammer2_chain_drop(chain); 897b93cc2e0SMatthew Dillon chain = NULL; 898b93cc2e0SMatthew Dillon goto done; 899b93cc2e0SMatthew Dillon } 90091abd410SMatthew Dillon 90191abd410SMatthew Dillon /* 90210136ab6SMatthew Dillon * Create any missing leaf(s) if we are doing a recovery (marking 90310136ab6SMatthew Dillon * the block(s) as being allocated instead of being freed). Be sure 90410136ab6SMatthew Dillon * to initialize the auxillary freemap tracking info in the 90510136ab6SMatthew Dillon * bref.check.freemap structure. 90691abd410SMatthew Dillon */ 90710136ab6SMatthew Dillon if (chain == NULL && how == HAMMER2_FREEMAP_DORECOVER) { 908c603b86bSMatthew Dillon error = hammer2_chain_create(&parent, &chain, hmp->spmp, 90910136ab6SMatthew Dillon key, HAMMER2_FREEMAP_LEVEL1_RADIX, 91010136ab6SMatthew Dillon HAMMER2_BREF_TYPE_FREEMAP_LEAF, 911b3659de2SMatthew Dillon HAMMER2_FREEMAP_LEVELN_PSIZE, 912*3f01ebaaSMatthew Dillon mtid, 0, 0); 9131fca819aSMatthew Dillon 9141fca819aSMatthew Dillon if (hammer2_debug & 0x0040) { 9151fca819aSMatthew Dillon kprintf("fixup create chain %p %016jx:%d\n", 9161fca819aSMatthew Dillon chain, chain->bref.key, chain->bref.keybits); 9171fca819aSMatthew Dillon } 91891abd410SMatthew Dillon 91910136ab6SMatthew Dillon if (error == 0) { 920*3f01ebaaSMatthew Dillon hammer2_chain_modify(chain, mtid, 0, 0); 92110136ab6SMatthew Dillon bzero(&chain->data->bmdata[0], 92210136ab6SMatthew Dillon HAMMER2_FREEMAP_LEVELN_PSIZE); 92310136ab6SMatthew Dillon chain->bref.check.freemap.bigmask = (uint32_t)-1; 92410136ab6SMatthew Dillon chain->bref.check.freemap.avail = l1size; 92510136ab6SMatthew Dillon /* bref.methods should already be inherited */ 92610136ab6SMatthew Dillon 927c603b86bSMatthew Dillon hammer2_freemap_init(hmp, key, chain); 92810136ab6SMatthew Dillon } 92910136ab6SMatthew Dillon /* XXX handle error */ 93010136ab6SMatthew Dillon } 93110136ab6SMatthew Dillon 9328138a154SMatthew Dillon #if FREEMAP_DEBUG 9338138a154SMatthew Dillon kprintf("FREEMAP ADJUST TYPE %d %016jx/%d DATA_OFF=%016jx\n", 9348138a154SMatthew Dillon chain->bref.type, chain->bref.key, 9358138a154SMatthew Dillon chain->bref.keybits, chain->bref.data_off); 9368138a154SMatthew Dillon #endif 9378138a154SMatthew Dillon 93810136ab6SMatthew Dillon /* 93910136ab6SMatthew Dillon * Calculate the bitmask (runs in 2-bit pairs). 94010136ab6SMatthew Dillon */ 94191abd410SMatthew Dillon start = ((int)(data_off >> HAMMER2_FREEMAP_BLOCK_RADIX) & 15) * 2; 9425cebbe36SMatthew Dillon bmmask01 = (hammer2_bitmap_t)1 << start; 9435cebbe36SMatthew Dillon bmmask10 = (hammer2_bitmap_t)2 << start; 9445cebbe36SMatthew Dillon bmmask11 = (hammer2_bitmap_t)3 << start; 94591abd410SMatthew Dillon 94691abd410SMatthew Dillon /* 94710136ab6SMatthew Dillon * Fixup the bitmap. Partial blocks cannot be fully freed unless 94810136ab6SMatthew Dillon * a bulk scan is able to roll them up. 94991abd410SMatthew Dillon */ 95091abd410SMatthew Dillon if (radix < HAMMER2_FREEMAP_BLOCK_RADIX) { 95191abd410SMatthew Dillon count = 1; 95210136ab6SMatthew Dillon if (how == HAMMER2_FREEMAP_DOREALFREE) 95310136ab6SMatthew Dillon how = HAMMER2_FREEMAP_DOMAYFREE; 95491abd410SMatthew Dillon } else { 95591abd410SMatthew Dillon count = 1 << (radix - HAMMER2_FREEMAP_BLOCK_RADIX); 9565c23d7f1SMatthew Dillon } 9575c23d7f1SMatthew Dillon 95810136ab6SMatthew Dillon /* 95910136ab6SMatthew Dillon * [re]load the bmap and bitmap pointers. Each bmap entry covers 96010136ab6SMatthew Dillon * a 2MB swath. The bmap itself (LEVEL1) covers 2GB. 9618138a154SMatthew Dillon * 9628138a154SMatthew Dillon * Be sure to reset the linear iterator to ensure that the adjustment 9638138a154SMatthew Dillon * is not ignored. 96410136ab6SMatthew Dillon */ 96510136ab6SMatthew Dillon again: 96691abd410SMatthew Dillon bmap = &chain->data->bmdata[(int)(data_off >> HAMMER2_SEGRADIX) & 96791abd410SMatthew Dillon (HAMMER2_FREEMAP_COUNT - 1)]; 9685cebbe36SMatthew Dillon bitmap = &bmap->bitmapq[(int)(data_off >> (HAMMER2_SEGRADIX - 3)) & 7]; 969a71db85dSMatthew Dillon 970a71db85dSMatthew Dillon if (modified) 9718138a154SMatthew Dillon bmap->linear = 0; 97210136ab6SMatthew Dillon 97310136ab6SMatthew Dillon while (count) { 97410136ab6SMatthew Dillon KKASSERT(bmmask11); 97510136ab6SMatthew Dillon if (how == HAMMER2_FREEMAP_DORECOVER) { 97610136ab6SMatthew Dillon /* 97710136ab6SMatthew Dillon * Recovery request, mark as allocated. 97810136ab6SMatthew Dillon */ 97910136ab6SMatthew Dillon if ((*bitmap & bmmask11) != bmmask11) { 98010136ab6SMatthew Dillon if (modified == 0) { 981*3f01ebaaSMatthew Dillon hammer2_chain_modify(chain, mtid, 0, 0); 98210136ab6SMatthew Dillon modified = 1; 98310136ab6SMatthew Dillon goto again; 98491abd410SMatthew Dillon } 985271568b1SMatthew Dillon if ((*bitmap & bmmask11) == bmmask00) { 986271568b1SMatthew Dillon bmap->avail -= 987271568b1SMatthew Dillon HAMMER2_FREEMAP_BLOCK_SIZE; 988271568b1SMatthew Dillon } 98910136ab6SMatthew Dillon if (bmap->class == 0) 99010136ab6SMatthew Dillon bmap->class = class; 99110136ab6SMatthew Dillon *bitmap |= bmmask11; 9921fca819aSMatthew Dillon if (hammer2_debug & 0x0040) { 9931fca819aSMatthew Dillon kprintf("hammer2_freemap_recover: " 9941fca819aSMatthew Dillon "fixup type=%02x " 9951fca819aSMatthew Dillon "block=%016jx/%zd\n", 99610136ab6SMatthew Dillon bref->type, data_off, bytes); 9971fca819aSMatthew Dillon } 99810136ab6SMatthew Dillon } else { 99910136ab6SMatthew Dillon /* 100010136ab6SMatthew Dillon kprintf("hammer2_freemap_recover: good " 100110136ab6SMatthew Dillon "type=%02x block=%016jx/%zd\n", 100210136ab6SMatthew Dillon bref->type, data_off, bytes); 100310136ab6SMatthew Dillon */ 100410136ab6SMatthew Dillon } 1005271568b1SMatthew Dillon } 1006271568b1SMatthew Dillon #if 0 1007271568b1SMatthew Dillon /* 1008271568b1SMatthew Dillon * XXX this stuff doesn't work, avail is miscalculated and 1009271568b1SMatthew Dillon * code 10 means something else now. 1010271568b1SMatthew Dillon */ 1011271568b1SMatthew Dillon else if ((*bitmap & bmmask11) == bmmask11) { 101210136ab6SMatthew Dillon /* 101310136ab6SMatthew Dillon * Mayfree/Realfree request and bitmap is currently 101410136ab6SMatthew Dillon * marked as being fully allocated. 101510136ab6SMatthew Dillon */ 101610136ab6SMatthew Dillon if (!modified) { 1017c603b86bSMatthew Dillon hammer2_chain_modify(chain, 0); 101810136ab6SMatthew Dillon modified = 1; 101910136ab6SMatthew Dillon goto again; 102010136ab6SMatthew Dillon } 102110136ab6SMatthew Dillon if (how == HAMMER2_FREEMAP_DOREALFREE) 102291abd410SMatthew Dillon *bitmap &= ~bmmask11; 102391abd410SMatthew Dillon else 102491abd410SMatthew Dillon *bitmap = (*bitmap & ~bmmask11) | bmmask10; 102591abd410SMatthew Dillon } else if ((*bitmap & bmmask11) == bmmask10) { 102610136ab6SMatthew Dillon /* 102710136ab6SMatthew Dillon * Mayfree/Realfree request and bitmap is currently 102810136ab6SMatthew Dillon * marked as being possibly freeable. 102910136ab6SMatthew Dillon */ 103010136ab6SMatthew Dillon if (how == HAMMER2_FREEMAP_DOREALFREE) { 103191abd410SMatthew Dillon if (!modified) { 1032c603b86bSMatthew Dillon hammer2_chain_modify(chain, 0); 103391abd410SMatthew Dillon modified = 1; 103410136ab6SMatthew Dillon goto again; 103591abd410SMatthew Dillon } 103691abd410SMatthew Dillon *bitmap &= ~bmmask11; 103791abd410SMatthew Dillon } 103810136ab6SMatthew Dillon } else { 103910136ab6SMatthew Dillon /* 104010136ab6SMatthew Dillon * 01 - Not implemented, currently illegal state 104110136ab6SMatthew Dillon * 00 - Not allocated at all, illegal free. 104210136ab6SMatthew Dillon */ 104310136ab6SMatthew Dillon panic("hammer2_freemap_adjust: " 104410136ab6SMatthew Dillon "Illegal state %08x(%08x)", 104510136ab6SMatthew Dillon *bitmap, *bitmap & bmmask11); 104691abd410SMatthew Dillon } 1047271568b1SMatthew Dillon #endif 104891abd410SMatthew Dillon --count; 104991abd410SMatthew Dillon bmmask01 <<= 2; 105091abd410SMatthew Dillon bmmask10 <<= 2; 105191abd410SMatthew Dillon bmmask11 <<= 2; 105291abd410SMatthew Dillon } 10535cebbe36SMatthew Dillon #if HAMMER2_BMAP_ELEMENTS != 8 10545cebbe36SMatthew Dillon #error "hammer2_freemap.c: HAMMER2_BMAP_ELEMENTS expected to be 8" 10555cebbe36SMatthew Dillon #endif 105610136ab6SMatthew Dillon if (how == HAMMER2_FREEMAP_DOREALFREE && modified) { 105791abd410SMatthew Dillon bmap->avail += 1 << radix; 105891abd410SMatthew Dillon KKASSERT(bmap->avail <= HAMMER2_SEGSIZE); 105991abd410SMatthew Dillon if (bmap->avail == HAMMER2_SEGSIZE && 10605cebbe36SMatthew Dillon bmap->bitmapq[0] == 0 && 10615cebbe36SMatthew Dillon bmap->bitmapq[1] == 0 && 10625cebbe36SMatthew Dillon bmap->bitmapq[2] == 0 && 10635cebbe36SMatthew Dillon bmap->bitmapq[3] == 0 && 10645cebbe36SMatthew Dillon bmap->bitmapq[4] == 0 && 10655cebbe36SMatthew Dillon bmap->bitmapq[5] == 0 && 10665cebbe36SMatthew Dillon bmap->bitmapq[6] == 0 && 10675cebbe36SMatthew Dillon bmap->bitmapq[7] == 0) { 106891abd410SMatthew Dillon key = H2FMBASE(data_off, HAMMER2_FREEMAP_LEVEL0_RADIX); 106991abd410SMatthew Dillon kprintf("Freeseg %016jx\n", (intmax_t)key); 107091abd410SMatthew Dillon bmap->class = 0; 107191abd410SMatthew Dillon } 107291abd410SMatthew Dillon } 107391abd410SMatthew Dillon 107491abd410SMatthew Dillon /* 107591abd410SMatthew Dillon * chain->bref.check.freemap.bigmask (XXX) 107610136ab6SMatthew Dillon * 107710136ab6SMatthew Dillon * Setting bigmask is a hint to the allocation code that there might 107810136ab6SMatthew Dillon * be something allocatable. We also set this in recovery... it 107910136ab6SMatthew Dillon * doesn't hurt and we might want to use the hint for other validation 108010136ab6SMatthew Dillon * operations later on. 108191abd410SMatthew Dillon */ 108291abd410SMatthew Dillon if (modified) 108391abd410SMatthew Dillon chain->bref.check.freemap.bigmask |= 1 << radix; 108491abd410SMatthew Dillon 108591abd410SMatthew Dillon hammer2_chain_unlock(chain); 1086e513e77eSMatthew Dillon hammer2_chain_drop(chain); 1087623d43d4SMatthew Dillon done: 108891abd410SMatthew Dillon hammer2_chain_unlock(parent); 1089e513e77eSMatthew Dillon hammer2_chain_drop(parent); 109091abd410SMatthew Dillon } 1091bca9f8e6SMatthew Dillon 1092bca9f8e6SMatthew Dillon /* 1093bca9f8e6SMatthew Dillon * Validate the freemap, in three stages. 1094bca9f8e6SMatthew Dillon * 1095bca9f8e6SMatthew Dillon * stage-1 ALLOCATED -> POSSIBLY FREE 1096bca9f8e6SMatthew Dillon * POSSIBLY FREE -> POSSIBLY FREE (type corrected) 1097bca9f8e6SMatthew Dillon * 1098bca9f8e6SMatthew Dillon * This transitions bitmap entries from ALLOCATED to POSSIBLY FREE. 1099bca9f8e6SMatthew Dillon * The POSSIBLY FREE state does not mean that a block is actually free 1100bca9f8e6SMatthew Dillon * and may be transitioned back to ALLOCATED in stage-2. 1101bca9f8e6SMatthew Dillon * 1102bca9f8e6SMatthew Dillon * This is typically done during normal filesystem operations when 1103bca9f8e6SMatthew Dillon * something is deleted or a block is replaced. 1104bca9f8e6SMatthew Dillon * 1105bca9f8e6SMatthew Dillon * This is done by bulkfree in-bulk after a memory-bounded meta-data 1106bca9f8e6SMatthew Dillon * scan to try to determine what might be freeable. 1107bca9f8e6SMatthew Dillon * 1108bca9f8e6SMatthew Dillon * This can be done unconditionally through a freemap scan when the 1109bca9f8e6SMatthew Dillon * intention is to brute-force recover the proper state of the freemap. 1110bca9f8e6SMatthew Dillon * 1111bca9f8e6SMatthew Dillon * stage-2 POSSIBLY FREE -> ALLOCATED (scan metadata topology) 1112bca9f8e6SMatthew Dillon * 1113bca9f8e6SMatthew Dillon * This is done by bulkfree during a meta-data scan to ensure that 1114bca9f8e6SMatthew Dillon * all blocks still actually allocated by the filesystem are marked 1115bca9f8e6SMatthew Dillon * as such. 1116bca9f8e6SMatthew Dillon * 1117bca9f8e6SMatthew Dillon * NOTE! Live filesystem transitions to POSSIBLY FREE can occur while 1118bca9f8e6SMatthew Dillon * the bulkfree stage-2 and stage-3 is running. The live filesystem 1119bca9f8e6SMatthew Dillon * will use the alternative POSSIBLY FREE type (2) to prevent 1120bca9f8e6SMatthew Dillon * stage-3 from improperly transitioning unvetted possibly-free 1121bca9f8e6SMatthew Dillon * blocks to FREE. 1122bca9f8e6SMatthew Dillon * 1123bca9f8e6SMatthew Dillon * stage-3 POSSIBLY FREE (type 1) -> FREE (scan freemap) 1124bca9f8e6SMatthew Dillon * 1125bca9f8e6SMatthew Dillon * This is done by bulkfree to finalize POSSIBLY FREE states. 1126bca9f8e6SMatthew Dillon * 1127bca9f8e6SMatthew Dillon */ 1128