1 /* $OpenBSD: ffs_subr.c,v 1.6 2022/01/11 05:34:33 jsg Exp $ */ 2 /* $NetBSD: ffs_subr.c,v 1.49 2016/05/07 11:59:08 maxv Exp $ */ 3 4 /* 5 * Copyright (c) 1982, 1986, 1989, 1993 6 * The Regents of the University of California. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. Neither the name of the University nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30 * SUCH DAMAGE. 31 * 32 * @(#)ffs_subr.c 8.5 (Berkeley) 3/21/95 33 */ 34 35 #include <sys/param.h> /* setbit clrbit NBBY */ 36 #include <sys/types.h> 37 #include <ufs/ufs/dinode.h> 38 #include <ufs/ffs/fs.h> 39 40 #include <limits.h> 41 #include <err.h> 42 43 #include "ffs/ffs_extern.h" 44 45 46 /* 47 * block operations 48 * 49 * check if a block is available 50 * returns true if all the corresponding bits in the free map are 1 51 * returns false if any corresponding bit in the free map is 0 52 */ 53 int 54 ffs_isblock(struct fs *fs, u_char *cp, int32_t h) 55 { 56 u_char mask; 57 58 switch ((int)fs->fs_fragshift) { 59 case 3: 60 return (cp[h] == 0xff); 61 case 2: 62 mask = 0x0f << ((h & 0x1) << 2); 63 return ((cp[h >> 1] & mask) == mask); 64 case 1: 65 mask = 0x03 << ((h & 0x3) << 1); 66 return ((cp[h >> 2] & mask) == mask); 67 case 0: 68 mask = 0x01 << (h & 0x7); 69 return ((cp[h >> 3] & mask) == mask); 70 default: 71 errx(1, "ffs_isblock: unknown fs_fragshift %d", 72 (int)fs->fs_fragshift); 73 } 74 } 75 76 /* 77 * take a block out of the map 78 */ 79 void 80 ffs_clrblock(struct fs *fs, u_char *cp, int32_t h) 81 { 82 83 switch ((int)fs->fs_fragshift) { 84 case 3: 85 cp[h] = 0; 86 return; 87 case 2: 88 cp[h >> 1] &= ~(0x0f << ((h & 0x1) << 2)); 89 return; 90 case 1: 91 cp[h >> 2] &= ~(0x03 << ((h & 0x3) << 1)); 92 return; 93 case 0: 94 cp[h >> 3] &= ~(0x01 << (h & 0x7)); 95 return; 96 default: 97 errx(1, "ffs_clrblock: unknown fs_fragshift %d", 98 (int)fs->fs_fragshift); 99 } 100 } 101 102 /* 103 * put a block into the map 104 */ 105 void 106 ffs_setblock(struct fs *fs, u_char *cp, int32_t h) 107 { 108 109 switch ((int)fs->fs_fragshift) { 110 case 3: 111 cp[h] = 0xff; 112 return; 113 case 2: 114 cp[h >> 1] |= (0x0f << ((h & 0x1) << 2)); 115 return; 116 case 1: 117 cp[h >> 2] |= (0x03 << ((h & 0x3) << 1)); 118 return; 119 case 0: 120 cp[h >> 3] |= (0x01 << (h & 0x7)); 121 return; 122 default: 123 errx(1, "ffs_setblock: unknown fs_fragshift %d", 124 (int)fs->fs_fragshift); 125 } 126 } 127 128 /* 129 * Update the cluster map because of an allocation or free. 130 * 131 * Cnt == 1 means free; cnt == -1 means allocating. 132 */ 133 void 134 ffs_clusteracct(struct fs *fs, struct cg *cgp, int32_t blkno, int cnt) 135 { 136 int32_t *sump; 137 int32_t *lp; 138 u_char *freemapp, *mapp; 139 int i, start, end, forw, back, map, bit; 140 141 /* KASSERT(mutex_owned(&ump->um_lock)); */ 142 143 if (fs->fs_contigsumsize <= 0) 144 return; 145 freemapp = cg_clustersfree(cgp); 146 sump = cg_clustersum(cgp); 147 /* 148 * Allocate or clear the actual block. 149 */ 150 if (cnt > 0) 151 setbit(freemapp, blkno); 152 else 153 clrbit(freemapp, blkno); 154 /* 155 * Find the size of the cluster going forward. 156 */ 157 start = blkno + 1; 158 end = start + fs->fs_contigsumsize; 159 if ((uint32_t)end >= cgp->cg_nclusterblks) 160 end = cgp->cg_nclusterblks; 161 mapp = &freemapp[start / NBBY]; 162 map = *mapp++; 163 bit = 1 << (start % NBBY); 164 for (i = start; i < end; i++) { 165 if ((map & bit) == 0) 166 break; 167 if ((i & (NBBY - 1)) != (NBBY - 1)) { 168 bit <<= 1; 169 } else { 170 map = *mapp++; 171 bit = 1; 172 } 173 } 174 forw = i - start; 175 /* 176 * Find the size of the cluster going backward. 177 */ 178 start = blkno - 1; 179 end = start - fs->fs_contigsumsize; 180 if (end < 0) 181 end = -1; 182 mapp = &freemapp[start / NBBY]; 183 map = *mapp--; 184 bit = 1 << (start % NBBY); 185 for (i = start; i > end; i--) { 186 if ((map & bit) == 0) 187 break; 188 if ((i & (NBBY - 1)) != 0) { 189 bit >>= 1; 190 } else { 191 map = *mapp--; 192 bit = 1 << (NBBY - 1); 193 } 194 } 195 back = start - i; 196 /* 197 * Account for old cluster and the possibly new forward and 198 * back clusters. 199 */ 200 i = back + forw + 1; 201 if (i > fs->fs_contigsumsize) 202 i = fs->fs_contigsumsize; 203 sump[i] += cnt; 204 if (back > 0) 205 sump[back] -= cnt; 206 if (forw > 0) 207 sump[forw] -= cnt; 208 209 /* 210 * Update cluster summary information. 211 */ 212 lp = &sump[fs->fs_contigsumsize]; 213 for (i = fs->fs_contigsumsize; i > 0; i--) 214 if (*lp-- > 0) 215 break; 216 } 217