Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
FreeBSD/Linux Kernel Cross Reference
sys/fs/hpfs/alloc.c
Version:
- FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
SearchContext: - none - 3 - 10
1 /* 2 * linux/fs/hpfs/alloc.c 3 * 4 * Mikulas Patocka (mikulas@artax.karlin.mff.cuni.cz), 1998-1999 5 * 6 * HPFS bitmap operations 7 */ 8 9 #include "hpfs_fn.h" 10 11 /* 12 * Check if a sector is allocated in bitmap 13 * This is really slow. Turned on only if chk==2 14 */ 15 16 static int chk_if_allocated(struct super_block *s, secno sec, char *msg) 17 { 18 struct quad_buffer_head qbh; 19 unsigned *bmp; 20 if (!(bmp = hpfs_map_bitmap(s, sec >> 14, &qbh, "chk"))) goto fail; 21 if ((bmp[(sec & 0x3fff) >> 5] >> (sec & 0x1f)) & 1) { 22 hpfs_error(s, "sector '%s' - %08x not allocated in bitmap", msg, sec); 23 goto fail1; 24 } 25 hpfs_brelse4(&qbh); 26 if (sec >= s->s_hpfs_dirband_start && sec < s->s_hpfs_dirband_start + s->s_hpfs_dirband_size) { 27 unsigned ssec = (sec - s->s_hpfs_dirband_start) / 4; 28 if (!(bmp = hpfs_map_dnode_bitmap(s, &qbh))) goto fail; 29 if ((bmp[ssec >> 5] >> (ssec & 0x1f)) & 1) { 30 hpfs_error(s, "sector '%s' - %08x not allocated in directory bitmap", msg, sec); 31 goto fail1; 32 } 33 hpfs_brelse4(&qbh); 34 } 35 return 0; 36 fail1: 37 hpfs_brelse4(&qbh); 38 fail: 39 return 1; 40 } 41 42 /* 43 * Check if sector(s) have proper number and additionally check if they're 44 * allocated in bitmap. 45 */ 46 47 int hpfs_chk_sectors(struct super_block *s, secno start, int len, char *msg) 48 { 49 if (start + len < start || start < 0x12 || 50 start + len > s->s_hpfs_fs_size) { 51 hpfs_error(s, "sector(s) '%s' badly placed at %08x", msg, start); 52 return 1; 53 } 54 if (s->s_hpfs_chk>=2) { 55 int i; 56 for (i = 0; i < len; i++) 57 if (chk_if_allocated(s, start + i, msg)) return 1; 58 } 59 return 0; 60 } 61 62 static secno alloc_in_bmp(struct super_block *s, secno near, unsigned n, unsigned forward) 63 { 64 struct quad_buffer_head qbh; 65 unsigned *bmp; 66 unsigned bs = near & ~0x3fff; 67 unsigned nr = (near & 0x3fff) & ~(n - 1); 68 /*unsigned mnr;*/ 69 unsigned i, q; 70 int a, b; 71 secno ret = 0; 72 if (n != 1 && n != 4) { 73 hpfs_error(s, "Bad allocation size: %d", n); 74 return 0; 75 } 76 lock_super(s); 77 if (bs != ~0x3fff) { 78 if (!(bmp = hpfs_map_bitmap(s, near >> 14, &qbh, "aib"))) goto uls; 79 } else { 80 if (!(bmp = hpfs_map_dnode_bitmap(s, &qbh))) goto uls; 81 } 82 /*if (!tstbits(bmp, nr + n, n + forward)) { 83 ret = bs + nr; 84 goto rt; 85 } 86 if (!tstbits(bmp, nr + 2*n, n + forward)) { 87 ret = bs + nr + n; 88 goto rt; 89 }*/ 90 q = nr + n; b = 0; 91 while ((a = tstbits(bmp, q, n + forward))) { 92 q += a; 93 if (n != 1) q = ((q-1)&~(n-1))+n; 94 if (!b) { 95 if (q>>5 != nr>>5) { 96 b = 1; 97 q = nr & 0x1f; 98 } 99 } else if (q > nr) break; 100 } 101 if (!a) { 102 ret = bs + q; 103 goto rt; 104 } 105 nr >>= 5; 106 for (i = nr + 1; i != nr; i++, i &= 0x1ff) { 107 if (!bmp[i]) continue; 108 if (n + forward >= 0x3f && bmp[i] != -1) continue; 109 q = i<<5; 110 if (i > 0) { 111 unsigned k = bmp[i-1]; 112 while (k & 0x80000000) { 113 q--; k <<= 1; 114 } 115 } 116 if (n != 1) q = ((q-1)&~(n-1))+n; 117 while ((a = tstbits(bmp, q, n + forward))) { 118 q += a; 119 if (n != 1) q = ((q-1)&~(n-1))+n; 120 if (q>>5 > i) break; 121 } 122 if (!a) { 123 ret = bs + q; 124 goto rt; 125 } 126 } 127 rt: 128 if (ret) { 129 if (s->s_hpfs_chk && ((ret >> 14) != (bs >> 14) || (bmp[(ret & 0x3fff) >> 5] | ~(((1 << n) - 1) << (ret & 0x1f))) != 0xffffffff)) { 130 hpfs_error(s, "Allocation doesn't work! Wanted %d, allocated at %08x", n, ret); 131 ret = 0; 132 goto b; 133 } 134 bmp[(ret & 0x3fff) >> 5] &= ~(((1 << n) - 1) << (ret & 0x1f)); 135 hpfs_mark_4buffers_dirty(&qbh); 136 } 137 b: 138 hpfs_brelse4(&qbh); 139 uls: 140 unlock_super(s); 141 return ret; 142 } 143 144 /* 145 * Allocation strategy: 1) search place near the sector specified 146 * 2) search bitmap where free sectors last found 147 * 3) search all bitmaps 148 * 4) search all bitmaps ignoring number of pre-allocated 149 * sectors 150 */ 151 152 secno hpfs_alloc_sector(struct super_block *s, secno near, unsigned n, int forward, int lock) 153 { 154 secno sec; 155 unsigned i; 156 unsigned n_bmps; 157 int b = s->s_hpfs_c_bitmap; 158 int f_p = 0; 159 if (forward < 0) { 160 forward = -forward; 161 f_p = 1; 162 } 163 if (lock) hpfs_lock_creation(s); 164 if (near && near < s->s_hpfs_fs_size) 165 if ((sec = alloc_in_bmp(s, near, n, f_p ? forward : forward/4))) goto ret; 166 if (b != -1) { 167 if ((sec = alloc_in_bmp(s, b<<14, n, f_p ? forward : forward/2))) { 168 b &= 0x0fffffff; 169 goto ret; 170 } 171 if (b > 0x10000000) if ((sec = alloc_in_bmp(s, (b&0xfffffff)<<14, n, f_p ? forward : 0))) goto ret; 172 } 173 n_bmps = (s->s_hpfs_fs_size + 0x4000 - 1) >> 14; 174 for (i = 0; i < n_bmps / 2; i++) { 175 if ((sec = alloc_in_bmp(s, (n_bmps/2+i) << 14, n, forward))) { 176 s->s_hpfs_c_bitmap = n_bmps/2+i; 177 goto ret; 178 } 179 if ((sec = alloc_in_bmp(s, (n_bmps/2-i-1) << 14, n, forward))) { 180 s->s_hpfs_c_bitmap = n_bmps/2-i-1; 181 goto ret; 182 } 183 } 184 if ((sec = alloc_in_bmp(s, (n_bmps-1) << 14, n, forward))) { 185 s->s_hpfs_c_bitmap = n_bmps-1; 186 goto ret; 187 } 188 if (!f_p) { 189 for (i = 0; i < n_bmps; i++) 190 if ((sec = alloc_in_bmp(s, i << 14, n, 0))) { 191 s->s_hpfs_c_bitmap = 0x10000000 + i; 192 goto ret; 193 } 194 } 195 sec = 0; 196 ret: 197 if (sec && f_p) { 198 for (i = 0; i < forward; i++) { 199 if (!hpfs_alloc_if_possible_nolock(s, sec + i + 1)) { 200 hpfs_error(s, "Prealloc doesn't work! Wanted %d, allocated at %08x, can't allocate %d", forward, sec, i); 201 sec = 0; 202 break; 203 } 204 } 205 } 206 if (lock) hpfs_unlock_creation(s); 207 return sec; 208 } 209 210 static secno alloc_in_dirband(struct super_block *s, secno near, int lock) 211 { 212 unsigned nr = near; 213 secno sec; 214 if (nr < s->s_hpfs_dirband_start) 215 nr = s->s_hpfs_dirband_start; 216 if (nr >= s->s_hpfs_dirband_start + s->s_hpfs_dirband_size) 217 nr = s->s_hpfs_dirband_start + s->s_hpfs_dirband_size - 4; 218 nr -= s->s_hpfs_dirband_start; 219 nr >>= 2; 220 if (lock) hpfs_lock_creation(s); 221 sec = alloc_in_bmp(s, (~0x3fff) | nr, 1, 0); 222 if (lock) hpfs_unlock_creation(s); 223 if (!sec) return 0; 224 return ((sec & 0x3fff) << 2) + s->s_hpfs_dirband_start; 225 } 226 227 /* Alloc sector if it's free */ 228 229 int hpfs_alloc_if_possible_nolock(struct super_block *s, secno sec) 230 { 231 struct quad_buffer_head qbh; 232 unsigned *bmp; 233 lock_super(s); 234 if (!(bmp = hpfs_map_bitmap(s, sec >> 14, &qbh, "aip"))) goto end; 235 if (bmp[(sec & 0x3fff) >> 5] & (1 << (sec & 0x1f))) { 236 bmp[(sec & 0x3fff) >> 5] &= ~(1 << (sec & 0x1f)); 237 hpfs_mark_4buffers_dirty(&qbh); 238 hpfs_brelse4(&qbh); 239 unlock_super(s); 240 return 1; 241 } 242 hpfs_brelse4(&qbh); 243 end: 244 unlock_super(s); 245 return 0; 246 } 247 248 int hpfs_alloc_if_possible(struct super_block *s, secno sec) 249 { 250 int r; 251 hpfs_lock_creation(s); 252 r = hpfs_alloc_if_possible_nolock(s, sec); 253 hpfs_unlock_creation(s); 254 return r; 255 } 256 257 /* Free sectors in bitmaps */ 258 259 void hpfs_free_sectors(struct super_block *s, secno sec, unsigned n) 260 { 261 struct quad_buffer_head qbh; 262 unsigned *bmp; 263 /*printk("2 - ");*/ 264 if (!n) return; 265 if (sec < 0x12) { 266 hpfs_error(s, "Trying to free reserved sector %08x", sec); 267 return; 268 } 269 lock_super(s); 270 new_map: 271 if (!(bmp = hpfs_map_bitmap(s, sec >> 14, &qbh, "free"))) { 272 unlock_super(s); 273 return; 274 } 275 new_tst: 276 if ((bmp[(sec & 0x3fff) >> 5] >> (sec & 0x1f) & 1)) { 277 hpfs_error(s, "sector %08x not allocated", sec); 278 hpfs_brelse4(&qbh); 279 unlock_super(s); 280 return; 281 } 282 bmp[(sec & 0x3fff) >> 5] |= 1 << (sec & 0x1f); 283 if (!--n) { 284 hpfs_mark_4buffers_dirty(&qbh); 285 hpfs_brelse4(&qbh); 286 unlock_super(s); 287 return; 288 } 289 if (!(++sec & 0x3fff)) { 290 hpfs_mark_4buffers_dirty(&qbh); 291 hpfs_brelse4(&qbh); 292 goto new_map; 293 } 294 goto new_tst; 295 } 296 297 /* 298 * Check if there are at least n free dnodes on the filesystem. 299 * Called before adding to dnode. If we run out of space while 300 * splitting dnodes, it would corrupt dnode tree. 301 */ 302 303 int hpfs_check_free_dnodes(struct super_block *s, int n) 304 { 305 int n_bmps = (s->s_hpfs_fs_size + 0x4000 - 1) >> 14; 306 int b = s->s_hpfs_c_bitmap & 0x0fffffff; 307 int i, j; 308 unsigned *bmp; 309 struct quad_buffer_head qbh; 310 if ((bmp = hpfs_map_dnode_bitmap(s, &qbh))) { 311 for (j = 0; j < 512; j++) { 312 unsigned k; 313 if (!bmp[j]) continue; 314 for (k = bmp[j]; k; k >>= 1) if (k & 1) if (!--n) { 315 hpfs_brelse4(&qbh); 316 return 0; 317 } 318 } 319 } 320 hpfs_brelse4(&qbh); 321 i = 0; 322 if (s->s_hpfs_c_bitmap != -1 ) { 323 bmp = hpfs_map_bitmap(s, b, &qbh, "chkdn1"); 324 goto chk_bmp; 325 } 326 chk_next: 327 if (i == b) i++; 328 if (i >= n_bmps) return 1; 329 bmp = hpfs_map_bitmap(s, i, &qbh, "chkdn2"); 330 chk_bmp: 331 if (bmp) { 332 for (j = 0; j < 512; j++) { 333 unsigned k; 334 if (!bmp[j]) continue; 335 for (k = 0xf; k; k <<= 4) 336 if ((bmp[j] & k) == k) { 337 if (!--n) { 338 hpfs_brelse4(&qbh); 339 return 0; 340 } 341 } 342 } 343 hpfs_brelse4(&qbh); 344 } 345 i++; 346 goto chk_next; 347 } 348 349 void hpfs_free_dnode(struct super_block *s, dnode_secno dno) 350 { 351 if (s->s_hpfs_chk) if (dno & 3) { 352 hpfs_error(s, "hpfs_free_dnode: dnode %08x not aligned", dno); 353 return; 354 } 355 if (dno < s->s_hpfs_dirband_start || 356 dno >= s->s_hpfs_dirband_start + s->s_hpfs_dirband_size) { 357 hpfs_free_sectors(s, dno, 4); 358 } else { 359 struct quad_buffer_head qbh; 360 unsigned *bmp; 361 unsigned ssec = (dno - s->s_hpfs_dirband_start) / 4; 362 lock_super(s); 363 if (!(bmp = hpfs_map_dnode_bitmap(s, &qbh))) { 364 unlock_super(s); 365 return; 366 } 367 bmp[ssec >> 5] |= 1 << (ssec & 0x1f); 368 hpfs_mark_4buffers_dirty(&qbh); 369 hpfs_brelse4(&qbh); 370 unlock_super(s); 371 } 372 } 373 374 struct dnode *hpfs_alloc_dnode(struct super_block *s, secno near, 375 dnode_secno *dno, struct quad_buffer_head *qbh, 376 int lock) 377 { 378 struct dnode *d; 379 if (hpfs_count_one_bitmap(s, s->s_hpfs_dmap) > FREE_DNODES_ADD) { 380 if (!(*dno = alloc_in_dirband(s, near, lock))) 381 if (!(*dno = hpfs_alloc_sector(s, near, 4, 0, lock))) return NULL; 382 } else { 383 if (!(*dno = hpfs_alloc_sector(s, near, 4, 0, lock))) 384 if (!(*dno = alloc_in_dirband(s, near, lock))) return NULL; 385 } 386 if (!(d = hpfs_get_4sectors(s, *dno, qbh))) { 387 hpfs_free_dnode(s, *dno); 388 return NULL; 389 } 390 memset(d, 0, 2048); 391 d->magic = DNODE_MAGIC; 392 d->first_free = 52; 393 d->dirent[0] = 32; 394 d->dirent[2] = 8; 395 d->dirent[30] = 1; 396 d->dirent[31] = 255; 397 d->self = *dno; 398 return d; 399 } 400 401 struct fnode *hpfs_alloc_fnode(struct super_block *s, secno near, fnode_secno *fno, 402 struct buffer_head **bh) 403 { 404 struct fnode *f; 405 if (!(*fno = hpfs_alloc_sector(s, near, 1, FNODE_ALLOC_FWD, 1))) return NULL; 406 if (!(f = hpfs_get_sector(s, *fno, bh))) { 407 hpfs_free_sectors(s, *fno, 1); 408 return NULL; 409 } 410 memset(f, 0, 512); 411 f->magic = FNODE_MAGIC; 412 f->ea_offs = 0xc4; 413 f->btree.n_free_nodes = 8; 414 f->btree.first_free = 8; 415 return f; 416 } 417 418 struct anode *hpfs_alloc_anode(struct super_block *s, secno near, anode_secno *ano, 419 struct buffer_head **bh) 420 { 421 struct anode *a; 422 if (!(*ano = hpfs_alloc_sector(s, near, 1, ANODE_ALLOC_FWD, 1))) return NULL; 423 if (!(a = hpfs_get_sector(s, *ano, bh))) { 424 hpfs_free_sectors(s, *ano, 1); 425 return NULL; 426 } 427 memset(a, 0, 512); 428 a->magic = ANODE_MAGIC; 429 a->self = *ano; 430 a->btree.n_free_nodes = 40; 431 a->btree.n_used_nodes = 0; 432 a->btree.first_free = 8; 433 return a; 434 }
Cache object: c64db13a8d805ecf7b8264f46733f6c2
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]