1 /* $OpenBSD: ffs_subr.c,v 1.4 2016/10/22 19:43:50 natano 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> 36 37 #include <ufs/ufs/dinode.h> 38 #include <ufs/ffs/fs.h> 39 40 #include <err.h> 41 42 #include "ffs/ffs_extern.h" 43 44 45 /* 46 * block operations 47 * 48 * check if a block is available 49 * returns true if all the correponding bits in the free map are 1 50 * returns false if any corresponding bit in the free map is 0 51 */ 52 int 53 ffs_isblock(struct fs *fs, u_char *cp, int32_t h) 54 { 55 u_char mask; 56 57 switch ((int)fs->fs_fragshift) { 58 case 3: 59 return (cp[h] == 0xff); 60 case 2: 61 mask = 0x0f << ((h & 0x1) << 2); 62 return ((cp[h >> 1] & mask) == mask); 63 case 1: 64 mask = 0x03 << ((h & 0x3) << 1); 65 return ((cp[h >> 2] & mask) == mask); 66 case 0: 67 mask = 0x01 << (h & 0x7); 68 return ((cp[h >> 3] & mask) == mask); 69 default: 70 errx(1, "ffs_isblock: unknown fs_fragshift %d", 71 (int)fs->fs_fragshift); 72 } 73 } 74 75 /* 76 * take a block out of the map 77 */ 78 void 79 ffs_clrblock(struct fs *fs, u_char *cp, int32_t h) 80 { 81 82 switch ((int)fs->fs_fragshift) { 83 case 3: 84 cp[h] = 0; 85 return; 86 case 2: 87 cp[h >> 1] &= ~(0x0f << ((h & 0x1) << 2)); 88 return; 89 case 1: 90 cp[h >> 2] &= ~(0x03 << ((h & 0x3) << 1)); 91 return; 92 case 0: 93 cp[h >> 3] &= ~(0x01 << (h & 0x7)); 94 return; 95 default: 96 errx(1, "ffs_clrblock: unknown fs_fragshift %d", 97 (int)fs->fs_fragshift); 98 } 99 } 100 101 /* 102 * put a block into the map 103 */ 104 void 105 ffs_setblock(struct fs *fs, u_char *cp, int32_t h) 106 { 107 108 switch ((int)fs->fs_fragshift) { 109 case 3: 110 cp[h] = 0xff; 111 return; 112 case 2: 113 cp[h >> 1] |= (0x0f << ((h & 0x1) << 2)); 114 return; 115 case 1: 116 cp[h >> 2] |= (0x03 << ((h & 0x3) << 1)); 117 return; 118 case 0: 119 cp[h >> 3] |= (0x01 << (h & 0x7)); 120 return; 121 default: 122 errx(1, "ffs_setblock: unknown fs_fragshift %d", 123 (int)fs->fs_fragshift); 124 } 125 } 126 127 /* 128 * Update the cluster map because of an allocation or free. 129 * 130 * Cnt == 1 means free; cnt == -1 means allocating. 131 */ 132 void 133 ffs_clusteracct(struct fs *fs, struct cg *cgp, int32_t blkno, int cnt) 134 { 135 int32_t *sump; 136 int32_t *lp; 137 u_char *freemapp, *mapp; 138 int i, start, end, forw, back, map, bit; 139 140 /* KASSERT(mutex_owned(&ump->um_lock)); */ 141 142 if (fs->fs_contigsumsize <= 0) 143 return; 144 freemapp = cg_clustersfree(cgp); 145 sump = cg_clustersum(cgp); 146 /* 147 * Allocate or clear the actual block. 148 */ 149 if (cnt > 0) 150 setbit(freemapp, blkno); 151 else 152 clrbit(freemapp, blkno); 153 /* 154 * Find the size of the cluster going forward. 155 */ 156 start = blkno + 1; 157 end = start + fs->fs_contigsumsize; 158 if ((uint32_t)end >= cgp->cg_nclusterblks) 159 end = cgp->cg_nclusterblks; 160 mapp = &freemapp[start / NBBY]; 161 map = *mapp++; 162 bit = 1 << (start % NBBY); 163 for (i = start; i < end; i++) { 164 if ((map & bit) == 0) 165 break; 166 if ((i & (NBBY - 1)) != (NBBY - 1)) { 167 bit <<= 1; 168 } else { 169 map = *mapp++; 170 bit = 1; 171 } 172 } 173 forw = i - start; 174 /* 175 * Find the size of the cluster going backward. 176 */ 177 start = blkno - 1; 178 end = start - fs->fs_contigsumsize; 179 if (end < 0) 180 end = -1; 181 mapp = &freemapp[start / NBBY]; 182 map = *mapp--; 183 bit = 1 << (start % NBBY); 184 for (i = start; i > end; i--) { 185 if ((map & bit) == 0) 186 break; 187 if ((i & (NBBY - 1)) != 0) { 188 bit >>= 1; 189 } else { 190 map = *mapp--; 191 bit = 1 << (NBBY - 1); 192 } 193 } 194 back = start - i; 195 /* 196 * Account for old cluster and the possibly new forward and 197 * back clusters. 198 */ 199 i = back + forw + 1; 200 if (i > fs->fs_contigsumsize) 201 i = fs->fs_contigsumsize; 202 sump[i] += cnt; 203 if (back > 0) 204 sump[back] -= cnt; 205 if (forw > 0) 206 sump[forw] -= cnt; 207 208 /* 209 * Update cluster summary information. 210 */ 211 lp = &sump[fs->fs_contigsumsize]; 212 for (i = fs->fs_contigsumsize; i > 0; i--) 213 if (*lp-- > 0) 214 break; 215 } 216