1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* 3 * Copyright (C) International Business Machines Corp., 2000-2004 4 * Portions Copyright (C) Tino Reichardt, 2012 5 */ 6 7 #include <linux/fs.h> 8 #include <linux/slab.h> 9 #include "jfs_incore.h" 10 #include "jfs_superblock.h" 11 #include "jfs_dmap.h" 12 #include "jfs_imap.h" 13 #include "jfs_lock.h" 14 #include "jfs_metapage.h" 15 #include "jfs_debug.h" 16 #include "jfs_discard.h" 17 18 /* 19 * SERIALIZATION of the Block Allocation Map. 20 * 21 * the working state of the block allocation map is accessed in 22 * two directions: 23 * 24 * 1) allocation and free requests that start at the dmap 25 * level and move up through the dmap control pages (i.e. 26 * the vast majority of requests). 27 * 28 * 2) allocation requests that start at dmap control page 29 * level and work down towards the dmaps. 30 * 31 * the serialization scheme used here is as follows. 32 * 33 * requests which start at the bottom are serialized against each 34 * other through buffers and each requests holds onto its buffers 35 * as it works it way up from a single dmap to the required level 36 * of dmap control page. 37 * requests that start at the top are serialized against each other 38 * and request that start from the bottom by the multiple read/single 39 * write inode lock of the bmap inode. requests starting at the top 40 * take this lock in write mode while request starting at the bottom 41 * take the lock in read mode. a single top-down request may proceed 42 * exclusively while multiple bottoms-up requests may proceed 43 * simultaneously (under the protection of busy buffers). 44 * 45 * in addition to information found in dmaps and dmap control pages, 46 * the working state of the block allocation map also includes read/ 47 * write information maintained in the bmap descriptor (i.e. total 48 * free block count, allocation group level free block counts). 49 * a single exclusive lock (BMAP_LOCK) is used to guard this information 50 * in the face of multiple-bottoms up requests. 51 * (lock ordering: IREAD_LOCK, BMAP_LOCK); 52 * 53 * accesses to the persistent state of the block allocation map (limited 54 * to the persistent bitmaps in dmaps) is guarded by (busy) buffers. 55 */ 56 57 #define BMAP_LOCK_INIT(bmp) mutex_init(&bmp->db_bmaplock) 58 #define BMAP_LOCK(bmp) mutex_lock(&bmp->db_bmaplock) 59 #define BMAP_UNLOCK(bmp) mutex_unlock(&bmp->db_bmaplock) 60 61 /* 62 * forward references 63 */ 64 static void dbAllocBits(struct bmap * bmp, struct dmap * dp, s64 blkno, 65 int nblocks); 66 static void dbSplit(dmtree_t * tp, int leafno, int splitsz, int newval); 67 static int dbBackSplit(dmtree_t * tp, int leafno); 68 static int dbJoin(dmtree_t * tp, int leafno, int newval); 69 static void dbAdjTree(dmtree_t * tp, int leafno, int newval); 70 static int dbAdjCtl(struct bmap * bmp, s64 blkno, int newval, int alloc, 71 int level); 72 static int dbAllocAny(struct bmap * bmp, s64 nblocks, int l2nb, s64 * results); 73 static int dbAllocNext(struct bmap * bmp, struct dmap * dp, s64 blkno, 74 int nblocks); 75 static int dbAllocNear(struct bmap * bmp, struct dmap * dp, s64 blkno, 76 int nblocks, 77 int l2nb, s64 * results); 78 static int dbAllocDmap(struct bmap * bmp, struct dmap * dp, s64 blkno, 79 int nblocks); 80 static int dbAllocDmapLev(struct bmap * bmp, struct dmap * dp, int nblocks, 81 int l2nb, 82 s64 * results); 83 static int dbAllocAG(struct bmap * bmp, int agno, s64 nblocks, int l2nb, 84 s64 * results); 85 static int dbAllocCtl(struct bmap * bmp, s64 nblocks, int l2nb, s64 blkno, 86 s64 * results); 87 static int dbExtend(struct inode *ip, s64 blkno, s64 nblocks, s64 addnblocks); 88 static int dbFindBits(u32 word, int l2nb); 89 static int dbFindCtl(struct bmap * bmp, int l2nb, int level, s64 * blkno); 90 static int dbFindLeaf(dmtree_t * tp, int l2nb, int *leafidx); 91 static int dbFreeBits(struct bmap * bmp, struct dmap * dp, s64 blkno, 92 int nblocks); 93 static int dbFreeDmap(struct bmap * bmp, struct dmap * dp, s64 blkno, 94 int nblocks); 95 static int dbMaxBud(u8 * cp); 96 static int blkstol2(s64 nb); 97 98 static int cntlz(u32 value); 99 static int cnttz(u32 word); 100 101 static int dbAllocDmapBU(struct bmap * bmp, struct dmap * dp, s64 blkno, 102 int nblocks); 103 static int dbInitDmap(struct dmap * dp, s64 blkno, int nblocks); 104 static int dbInitDmapTree(struct dmap * dp); 105 static int dbInitTree(struct dmaptree * dtp); 106 static int dbInitDmapCtl(struct dmapctl * dcp, int level, int i); 107 static int dbGetL2AGSize(s64 nblocks); 108 109 /* 110 * buddy table 111 * 112 * table used for determining buddy sizes within characters of 113 * dmap bitmap words. the characters themselves serve as indexes 114 * into the table, with the table elements yielding the maximum 115 * binary buddy of free bits within the character. 116 */ 117 static const s8 budtab[256] = { 118 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 119 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 120 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 121 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 122 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 123 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 124 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 125 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 126 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 127 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 128 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 129 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 130 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 131 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 132 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 133 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, -1 134 }; 135 136 /* 137 * NAME: dbMount() 138 * 139 * FUNCTION: initializate the block allocation map. 140 * 141 * memory is allocated for the in-core bmap descriptor and 142 * the in-core descriptor is initialized from disk. 143 * 144 * PARAMETERS: 145 * ipbmap - pointer to in-core inode for the block map. 146 * 147 * RETURN VALUES: 148 * 0 - success 149 * -ENOMEM - insufficient memory 150 * -EIO - i/o error 151 */ 152 int dbMount(struct inode *ipbmap) 153 { 154 struct bmap *bmp; 155 struct dbmap_disk *dbmp_le; 156 struct metapage *mp; 157 int i; 158 159 /* 160 * allocate/initialize the in-memory bmap descriptor 161 */ 162 /* allocate memory for the in-memory bmap descriptor */ 163 bmp = kmalloc(sizeof(struct bmap), GFP_KERNEL); 164 if (bmp == NULL) 165 return -ENOMEM; 166 167 /* read the on-disk bmap descriptor. */ 168 mp = read_metapage(ipbmap, 169 BMAPBLKNO << JFS_SBI(ipbmap->i_sb)->l2nbperpage, 170 PSIZE, 0); 171 if (mp == NULL) { 172 kfree(bmp); 173 return -EIO; 174 } 175 176 /* copy the on-disk bmap descriptor to its in-memory version. */ 177 dbmp_le = (struct dbmap_disk *) mp->data; 178 bmp->db_mapsize = le64_to_cpu(dbmp_le->dn_mapsize); 179 bmp->db_nfree = le64_to_cpu(dbmp_le->dn_nfree); 180 bmp->db_l2nbperpage = le32_to_cpu(dbmp_le->dn_l2nbperpage); 181 bmp->db_numag = le32_to_cpu(dbmp_le->dn_numag); 182 bmp->db_maxlevel = le32_to_cpu(dbmp_le->dn_maxlevel); 183 bmp->db_maxag = le32_to_cpu(dbmp_le->dn_maxag); 184 bmp->db_agpref = le32_to_cpu(dbmp_le->dn_agpref); 185 bmp->db_aglevel = le32_to_cpu(dbmp_le->dn_aglevel); 186 bmp->db_agheight = le32_to_cpu(dbmp_le->dn_agheight); 187 bmp->db_agwidth = le32_to_cpu(dbmp_le->dn_agwidth); 188 bmp->db_agstart = le32_to_cpu(dbmp_le->dn_agstart); 189 bmp->db_agl2size = le32_to_cpu(dbmp_le->dn_agl2size); 190 for (i = 0; i < MAXAG; i++) 191 bmp->db_agfree[i] = le64_to_cpu(dbmp_le->dn_agfree[i]); 192 bmp->db_agsize = le64_to_cpu(dbmp_le->dn_agsize); 193 bmp->db_maxfreebud = dbmp_le->dn_maxfreebud; 194 195 /* release the buffer. */ 196 release_metapage(mp); 197 198 /* bind the bmap inode and the bmap descriptor to each other. */ 199 bmp->db_ipbmap = ipbmap; 200 JFS_SBI(ipbmap->i_sb)->bmap = bmp; 201 202 memset(bmp->db_active, 0, sizeof(bmp->db_active)); 203 204 /* 205 * allocate/initialize the bmap lock 206 */ 207 BMAP_LOCK_INIT(bmp); 208 209 return (0); 210 } 211 212 213 /* 214 * NAME: dbUnmount() 215 * 216 * FUNCTION: terminate the block allocation map in preparation for 217 * file system unmount. 218 * 219 * the in-core bmap descriptor is written to disk and 220 * the memory for this descriptor is freed. 221 * 222 * PARAMETERS: 223 * ipbmap - pointer to in-core inode for the block map. 224 * 225 * RETURN VALUES: 226 * 0 - success 227 * -EIO - i/o error 228 */ 229 int dbUnmount(struct inode *ipbmap, int mounterror) 230 { 231 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap; 232 233 if (!(mounterror || isReadOnly(ipbmap))) 234 dbSync(ipbmap); 235 236 /* 237 * Invalidate the page cache buffers 238 */ 239 truncate_inode_pages(ipbmap->i_mapping, 0); 240 241 /* free the memory for the in-memory bmap. */ 242 kfree(bmp); 243 244 return (0); 245 } 246 247 /* 248 * dbSync() 249 */ 250 int dbSync(struct inode *ipbmap) 251 { 252 struct dbmap_disk *dbmp_le; 253 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap; 254 struct metapage *mp; 255 int i; 256 257 /* 258 * write bmap global control page 259 */ 260 /* get the buffer for the on-disk bmap descriptor. */ 261 mp = read_metapage(ipbmap, 262 BMAPBLKNO << JFS_SBI(ipbmap->i_sb)->l2nbperpage, 263 PSIZE, 0); 264 if (mp == NULL) { 265 jfs_err("dbSync: read_metapage failed!"); 266 return -EIO; 267 } 268 /* copy the in-memory version of the bmap to the on-disk version */ 269 dbmp_le = (struct dbmap_disk *) mp->data; 270 dbmp_le->dn_mapsize = cpu_to_le64(bmp->db_mapsize); 271 dbmp_le->dn_nfree = cpu_to_le64(bmp->db_nfree); 272 dbmp_le->dn_l2nbperpage = cpu_to_le32(bmp->db_l2nbperpage); 273 dbmp_le->dn_numag = cpu_to_le32(bmp->db_numag); 274 dbmp_le->dn_maxlevel = cpu_to_le32(bmp->db_maxlevel); 275 dbmp_le->dn_maxag = cpu_to_le32(bmp->db_maxag); 276 dbmp_le->dn_agpref = cpu_to_le32(bmp->db_agpref); 277 dbmp_le->dn_aglevel = cpu_to_le32(bmp->db_aglevel); 278 dbmp_le->dn_agheight = cpu_to_le32(bmp->db_agheight); 279 dbmp_le->dn_agwidth = cpu_to_le32(bmp->db_agwidth); 280 dbmp_le->dn_agstart = cpu_to_le32(bmp->db_agstart); 281 dbmp_le->dn_agl2size = cpu_to_le32(bmp->db_agl2size); 282 for (i = 0; i < MAXAG; i++) 283 dbmp_le->dn_agfree[i] = cpu_to_le64(bmp->db_agfree[i]); 284 dbmp_le->dn_agsize = cpu_to_le64(bmp->db_agsize); 285 dbmp_le->dn_maxfreebud = bmp->db_maxfreebud; 286 287 /* write the buffer */ 288 write_metapage(mp); 289 290 /* 291 * write out dirty pages of bmap 292 */ 293 filemap_write_and_wait(ipbmap->i_mapping); 294 295 diWriteSpecial(ipbmap, 0); 296 297 return (0); 298 } 299 300 /* 301 * NAME: dbFree() 302 * 303 * FUNCTION: free the specified block range from the working block 304 * allocation map. 305 * 306 * the blocks will be free from the working map one dmap 307 * at a time. 308 * 309 * PARAMETERS: 310 * ip - pointer to in-core inode; 311 * blkno - starting block number to be freed. 312 * nblocks - number of blocks to be freed. 313 * 314 * RETURN VALUES: 315 * 0 - success 316 * -EIO - i/o error 317 */ 318 int dbFree(struct inode *ip, s64 blkno, s64 nblocks) 319 { 320 struct metapage *mp; 321 struct dmap *dp; 322 int nb, rc; 323 s64 lblkno, rem; 324 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap; 325 struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap; 326 struct super_block *sb = ipbmap->i_sb; 327 328 IREAD_LOCK(ipbmap, RDWRLOCK_DMAP); 329 330 /* block to be freed better be within the mapsize. */ 331 if (unlikely((blkno == 0) || (blkno + nblocks > bmp->db_mapsize))) { 332 IREAD_UNLOCK(ipbmap); 333 printk(KERN_ERR "blkno = %Lx, nblocks = %Lx\n", 334 (unsigned long long) blkno, 335 (unsigned long long) nblocks); 336 jfs_error(ip->i_sb, "block to be freed is outside the map\n"); 337 return -EIO; 338 } 339 340 /** 341 * TRIM the blocks, when mounted with discard option 342 */ 343 if (JFS_SBI(sb)->flag & JFS_DISCARD) 344 if (JFS_SBI(sb)->minblks_trim <= nblocks) 345 jfs_issue_discard(ipbmap, blkno, nblocks); 346 347 /* 348 * free the blocks a dmap at a time. 349 */ 350 mp = NULL; 351 for (rem = nblocks; rem > 0; rem -= nb, blkno += nb) { 352 /* release previous dmap if any */ 353 if (mp) { 354 write_metapage(mp); 355 } 356 357 /* get the buffer for the current dmap. */ 358 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); 359 mp = read_metapage(ipbmap, lblkno, PSIZE, 0); 360 if (mp == NULL) { 361 IREAD_UNLOCK(ipbmap); 362 return -EIO; 363 } 364 dp = (struct dmap *) mp->data; 365 366 /* determine the number of blocks to be freed from 367 * this dmap. 368 */ 369 nb = min(rem, BPERDMAP - (blkno & (BPERDMAP - 1))); 370 371 /* free the blocks. */ 372 if ((rc = dbFreeDmap(bmp, dp, blkno, nb))) { 373 jfs_error(ip->i_sb, "error in block map\n"); 374 release_metapage(mp); 375 IREAD_UNLOCK(ipbmap); 376 return (rc); 377 } 378 } 379 380 /* write the last buffer. */ 381 write_metapage(mp); 382 383 IREAD_UNLOCK(ipbmap); 384 385 return (0); 386 } 387 388 389 /* 390 * NAME: dbUpdatePMap() 391 * 392 * FUNCTION: update the allocation state (free or allocate) of the 393 * specified block range in the persistent block allocation map. 394 * 395 * the blocks will be updated in the persistent map one 396 * dmap at a time. 397 * 398 * PARAMETERS: 399 * ipbmap - pointer to in-core inode for the block map. 400 * free - 'true' if block range is to be freed from the persistent 401 * map; 'false' if it is to be allocated. 402 * blkno - starting block number of the range. 403 * nblocks - number of contiguous blocks in the range. 404 * tblk - transaction block; 405 * 406 * RETURN VALUES: 407 * 0 - success 408 * -EIO - i/o error 409 */ 410 int 411 dbUpdatePMap(struct inode *ipbmap, 412 int free, s64 blkno, s64 nblocks, struct tblock * tblk) 413 { 414 int nblks, dbitno, wbitno, rbits; 415 int word, nbits, nwords; 416 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap; 417 s64 lblkno, rem, lastlblkno; 418 u32 mask; 419 struct dmap *dp; 420 struct metapage *mp; 421 struct jfs_log *log; 422 int lsn, difft, diffp; 423 unsigned long flags; 424 425 /* the blocks better be within the mapsize. */ 426 if (blkno + nblocks > bmp->db_mapsize) { 427 printk(KERN_ERR "blkno = %Lx, nblocks = %Lx\n", 428 (unsigned long long) blkno, 429 (unsigned long long) nblocks); 430 jfs_error(ipbmap->i_sb, "blocks are outside the map\n"); 431 return -EIO; 432 } 433 434 /* compute delta of transaction lsn from log syncpt */ 435 lsn = tblk->lsn; 436 log = (struct jfs_log *) JFS_SBI(tblk->sb)->log; 437 logdiff(difft, lsn, log); 438 439 /* 440 * update the block state a dmap at a time. 441 */ 442 mp = NULL; 443 lastlblkno = 0; 444 for (rem = nblocks; rem > 0; rem -= nblks, blkno += nblks) { 445 /* get the buffer for the current dmap. */ 446 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); 447 if (lblkno != lastlblkno) { 448 if (mp) { 449 write_metapage(mp); 450 } 451 452 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 453 0); 454 if (mp == NULL) 455 return -EIO; 456 metapage_wait_for_io(mp); 457 } 458 dp = (struct dmap *) mp->data; 459 460 /* determine the bit number and word within the dmap of 461 * the starting block. also determine how many blocks 462 * are to be updated within this dmap. 463 */ 464 dbitno = blkno & (BPERDMAP - 1); 465 word = dbitno >> L2DBWORD; 466 nblks = min(rem, (s64)BPERDMAP - dbitno); 467 468 /* update the bits of the dmap words. the first and last 469 * words may only have a subset of their bits updated. if 470 * this is the case, we'll work against that word (i.e. 471 * partial first and/or last) only in a single pass. a 472 * single pass will also be used to update all words that 473 * are to have all their bits updated. 474 */ 475 for (rbits = nblks; rbits > 0; 476 rbits -= nbits, dbitno += nbits) { 477 /* determine the bit number within the word and 478 * the number of bits within the word. 479 */ 480 wbitno = dbitno & (DBWORD - 1); 481 nbits = min(rbits, DBWORD - wbitno); 482 483 /* check if only part of the word is to be updated. */ 484 if (nbits < DBWORD) { 485 /* update (free or allocate) the bits 486 * in this word. 487 */ 488 mask = 489 (ONES << (DBWORD - nbits) >> wbitno); 490 if (free) 491 dp->pmap[word] &= 492 cpu_to_le32(~mask); 493 else 494 dp->pmap[word] |= 495 cpu_to_le32(mask); 496 497 word += 1; 498 } else { 499 /* one or more words are to have all 500 * their bits updated. determine how 501 * many words and how many bits. 502 */ 503 nwords = rbits >> L2DBWORD; 504 nbits = nwords << L2DBWORD; 505 506 /* update (free or allocate) the bits 507 * in these words. 508 */ 509 if (free) 510 memset(&dp->pmap[word], 0, 511 nwords * 4); 512 else 513 memset(&dp->pmap[word], (int) ONES, 514 nwords * 4); 515 516 word += nwords; 517 } 518 } 519 520 /* 521 * update dmap lsn 522 */ 523 if (lblkno == lastlblkno) 524 continue; 525 526 lastlblkno = lblkno; 527 528 LOGSYNC_LOCK(log, flags); 529 if (mp->lsn != 0) { 530 /* inherit older/smaller lsn */ 531 logdiff(diffp, mp->lsn, log); 532 if (difft < diffp) { 533 mp->lsn = lsn; 534 535 /* move bp after tblock in logsync list */ 536 list_move(&mp->synclist, &tblk->synclist); 537 } 538 539 /* inherit younger/larger clsn */ 540 logdiff(difft, tblk->clsn, log); 541 logdiff(diffp, mp->clsn, log); 542 if (difft > diffp) 543 mp->clsn = tblk->clsn; 544 } else { 545 mp->log = log; 546 mp->lsn = lsn; 547 548 /* insert bp after tblock in logsync list */ 549 log->count++; 550 list_add(&mp->synclist, &tblk->synclist); 551 552 mp->clsn = tblk->clsn; 553 } 554 LOGSYNC_UNLOCK(log, flags); 555 } 556 557 /* write the last buffer. */ 558 if (mp) { 559 write_metapage(mp); 560 } 561 562 return (0); 563 } 564 565 566 /* 567 * NAME: dbNextAG() 568 * 569 * FUNCTION: find the preferred allocation group for new allocations. 570 * 571 * Within the allocation groups, we maintain a preferred 572 * allocation group which consists of a group with at least 573 * average free space. It is the preferred group that we target 574 * new inode allocation towards. The tie-in between inode 575 * allocation and block allocation occurs as we allocate the 576 * first (data) block of an inode and specify the inode (block) 577 * as the allocation hint for this block. 578 * 579 * We try to avoid having more than one open file growing in 580 * an allocation group, as this will lead to fragmentation. 581 * This differs from the old OS/2 method of trying to keep 582 * empty ags around for large allocations. 583 * 584 * PARAMETERS: 585 * ipbmap - pointer to in-core inode for the block map. 586 * 587 * RETURN VALUES: 588 * the preferred allocation group number. 589 */ 590 int dbNextAG(struct inode *ipbmap) 591 { 592 s64 avgfree; 593 int agpref; 594 s64 hwm = 0; 595 int i; 596 int next_best = -1; 597 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap; 598 599 BMAP_LOCK(bmp); 600 601 /* determine the average number of free blocks within the ags. */ 602 avgfree = (u32)bmp->db_nfree / bmp->db_numag; 603 604 /* 605 * if the current preferred ag does not have an active allocator 606 * and has at least average freespace, return it 607 */ 608 agpref = bmp->db_agpref; 609 if ((atomic_read(&bmp->db_active[agpref]) == 0) && 610 (bmp->db_agfree[agpref] >= avgfree)) 611 goto unlock; 612 613 /* From the last preferred ag, find the next one with at least 614 * average free space. 615 */ 616 for (i = 0 ; i < bmp->db_numag; i++, agpref++) { 617 if (agpref == bmp->db_numag) 618 agpref = 0; 619 620 if (atomic_read(&bmp->db_active[agpref])) 621 /* open file is currently growing in this ag */ 622 continue; 623 if (bmp->db_agfree[agpref] >= avgfree) { 624 /* Return this one */ 625 bmp->db_agpref = agpref; 626 goto unlock; 627 } else if (bmp->db_agfree[agpref] > hwm) { 628 /* Less than avg. freespace, but best so far */ 629 hwm = bmp->db_agfree[agpref]; 630 next_best = agpref; 631 } 632 } 633 634 /* 635 * If no inactive ag was found with average freespace, use the 636 * next best 637 */ 638 if (next_best != -1) 639 bmp->db_agpref = next_best; 640 /* else leave db_agpref unchanged */ 641 unlock: 642 BMAP_UNLOCK(bmp); 643 644 /* return the preferred group. 645 */ 646 return (bmp->db_agpref); 647 } 648 649 /* 650 * NAME: dbAlloc() 651 * 652 * FUNCTION: attempt to allocate a specified number of contiguous free 653 * blocks from the working allocation block map. 654 * 655 * the block allocation policy uses hints and a multi-step 656 * approach. 657 * 658 * for allocation requests smaller than the number of blocks 659 * per dmap, we first try to allocate the new blocks 660 * immediately following the hint. if these blocks are not 661 * available, we try to allocate blocks near the hint. if 662 * no blocks near the hint are available, we next try to 663 * allocate within the same dmap as contains the hint. 664 * 665 * if no blocks are available in the dmap or the allocation 666 * request is larger than the dmap size, we try to allocate 667 * within the same allocation group as contains the hint. if 668 * this does not succeed, we finally try to allocate anywhere 669 * within the aggregate. 670 * 671 * we also try to allocate anywhere within the aggregate 672 * for allocation requests larger than the allocation group 673 * size or requests that specify no hint value. 674 * 675 * PARAMETERS: 676 * ip - pointer to in-core inode; 677 * hint - allocation hint. 678 * nblocks - number of contiguous blocks in the range. 679 * results - on successful return, set to the starting block number 680 * of the newly allocated contiguous range. 681 * 682 * RETURN VALUES: 683 * 0 - success 684 * -ENOSPC - insufficient disk resources 685 * -EIO - i/o error 686 */ 687 int dbAlloc(struct inode *ip, s64 hint, s64 nblocks, s64 * results) 688 { 689 int rc, agno; 690 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap; 691 struct bmap *bmp; 692 struct metapage *mp; 693 s64 lblkno, blkno; 694 struct dmap *dp; 695 int l2nb; 696 s64 mapSize; 697 int writers; 698 699 /* assert that nblocks is valid */ 700 assert(nblocks > 0); 701 702 /* get the log2 number of blocks to be allocated. 703 * if the number of blocks is not a log2 multiple, 704 * it will be rounded up to the next log2 multiple. 705 */ 706 l2nb = BLKSTOL2(nblocks); 707 708 bmp = JFS_SBI(ip->i_sb)->bmap; 709 710 mapSize = bmp->db_mapsize; 711 712 /* the hint should be within the map */ 713 if (hint >= mapSize) { 714 jfs_error(ip->i_sb, "the hint is outside the map\n"); 715 return -EIO; 716 } 717 718 /* if the number of blocks to be allocated is greater than the 719 * allocation group size, try to allocate anywhere. 720 */ 721 if (l2nb > bmp->db_agl2size) { 722 IWRITE_LOCK(ipbmap, RDWRLOCK_DMAP); 723 724 rc = dbAllocAny(bmp, nblocks, l2nb, results); 725 726 goto write_unlock; 727 } 728 729 /* 730 * If no hint, let dbNextAG recommend an allocation group 731 */ 732 if (hint == 0) 733 goto pref_ag; 734 735 /* we would like to allocate close to the hint. adjust the 736 * hint to the block following the hint since the allocators 737 * will start looking for free space starting at this point. 738 */ 739 blkno = hint + 1; 740 741 if (blkno >= bmp->db_mapsize) 742 goto pref_ag; 743 744 agno = blkno >> bmp->db_agl2size; 745 746 /* check if blkno crosses over into a new allocation group. 747 * if so, check if we should allow allocations within this 748 * allocation group. 749 */ 750 if ((blkno & (bmp->db_agsize - 1)) == 0) 751 /* check if the AG is currently being written to. 752 * if so, call dbNextAG() to find a non-busy 753 * AG with sufficient free space. 754 */ 755 if (atomic_read(&bmp->db_active[agno])) 756 goto pref_ag; 757 758 /* check if the allocation request size can be satisfied from a 759 * single dmap. if so, try to allocate from the dmap containing 760 * the hint using a tiered strategy. 761 */ 762 if (nblocks <= BPERDMAP) { 763 IREAD_LOCK(ipbmap, RDWRLOCK_DMAP); 764 765 /* get the buffer for the dmap containing the hint. 766 */ 767 rc = -EIO; 768 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); 769 mp = read_metapage(ipbmap, lblkno, PSIZE, 0); 770 if (mp == NULL) 771 goto read_unlock; 772 773 dp = (struct dmap *) mp->data; 774 775 /* first, try to satisfy the allocation request with the 776 * blocks beginning at the hint. 777 */ 778 if ((rc = dbAllocNext(bmp, dp, blkno, (int) nblocks)) 779 != -ENOSPC) { 780 if (rc == 0) { 781 *results = blkno; 782 mark_metapage_dirty(mp); 783 } 784 785 release_metapage(mp); 786 goto read_unlock; 787 } 788 789 writers = atomic_read(&bmp->db_active[agno]); 790 if ((writers > 1) || 791 ((writers == 1) && (JFS_IP(ip)->active_ag != agno))) { 792 /* 793 * Someone else is writing in this allocation 794 * group. To avoid fragmenting, try another ag 795 */ 796 release_metapage(mp); 797 IREAD_UNLOCK(ipbmap); 798 goto pref_ag; 799 } 800 801 /* next, try to satisfy the allocation request with blocks 802 * near the hint. 803 */ 804 if ((rc = 805 dbAllocNear(bmp, dp, blkno, (int) nblocks, l2nb, results)) 806 != -ENOSPC) { 807 if (rc == 0) 808 mark_metapage_dirty(mp); 809 810 release_metapage(mp); 811 goto read_unlock; 812 } 813 814 /* try to satisfy the allocation request with blocks within 815 * the same dmap as the hint. 816 */ 817 if ((rc = dbAllocDmapLev(bmp, dp, (int) nblocks, l2nb, results)) 818 != -ENOSPC) { 819 if (rc == 0) 820 mark_metapage_dirty(mp); 821 822 release_metapage(mp); 823 goto read_unlock; 824 } 825 826 release_metapage(mp); 827 IREAD_UNLOCK(ipbmap); 828 } 829 830 /* try to satisfy the allocation request with blocks within 831 * the same allocation group as the hint. 832 */ 833 IWRITE_LOCK(ipbmap, RDWRLOCK_DMAP); 834 if ((rc = dbAllocAG(bmp, agno, nblocks, l2nb, results)) != -ENOSPC) 835 goto write_unlock; 836 837 IWRITE_UNLOCK(ipbmap); 838 839 840 pref_ag: 841 /* 842 * Let dbNextAG recommend a preferred allocation group 843 */ 844 agno = dbNextAG(ipbmap); 845 IWRITE_LOCK(ipbmap, RDWRLOCK_DMAP); 846 847 /* Try to allocate within this allocation group. if that fails, try to 848 * allocate anywhere in the map. 849 */ 850 if ((rc = dbAllocAG(bmp, agno, nblocks, l2nb, results)) == -ENOSPC) 851 rc = dbAllocAny(bmp, nblocks, l2nb, results); 852 853 write_unlock: 854 IWRITE_UNLOCK(ipbmap); 855 856 return (rc); 857 858 read_unlock: 859 IREAD_UNLOCK(ipbmap); 860 861 return (rc); 862 } 863 864 #ifdef _NOTYET 865 /* 866 * NAME: dbAllocExact() 867 * 868 * FUNCTION: try to allocate the requested extent; 869 * 870 * PARAMETERS: 871 * ip - pointer to in-core inode; 872 * blkno - extent address; 873 * nblocks - extent length; 874 * 875 * RETURN VALUES: 876 * 0 - success 877 * -ENOSPC - insufficient disk resources 878 * -EIO - i/o error 879 */ 880 int dbAllocExact(struct inode *ip, s64 blkno, int nblocks) 881 { 882 int rc; 883 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap; 884 struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap; 885 struct dmap *dp; 886 s64 lblkno; 887 struct metapage *mp; 888 889 IREAD_LOCK(ipbmap, RDWRLOCK_DMAP); 890 891 /* 892 * validate extent request: 893 * 894 * note: defragfs policy: 895 * max 64 blocks will be moved. 896 * allocation request size must be satisfied from a single dmap. 897 */ 898 if (nblocks <= 0 || nblocks > BPERDMAP || blkno >= bmp->db_mapsize) { 899 IREAD_UNLOCK(ipbmap); 900 return -EINVAL; 901 } 902 903 if (nblocks > ((s64) 1 << bmp->db_maxfreebud)) { 904 /* the free space is no longer available */ 905 IREAD_UNLOCK(ipbmap); 906 return -ENOSPC; 907 } 908 909 /* read in the dmap covering the extent */ 910 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); 911 mp = read_metapage(ipbmap, lblkno, PSIZE, 0); 912 if (mp == NULL) { 913 IREAD_UNLOCK(ipbmap); 914 return -EIO; 915 } 916 dp = (struct dmap *) mp->data; 917 918 /* try to allocate the requested extent */ 919 rc = dbAllocNext(bmp, dp, blkno, nblocks); 920 921 IREAD_UNLOCK(ipbmap); 922 923 if (rc == 0) 924 mark_metapage_dirty(mp); 925 926 release_metapage(mp); 927 928 return (rc); 929 } 930 #endif /* _NOTYET */ 931 932 /* 933 * NAME: dbReAlloc() 934 * 935 * FUNCTION: attempt to extend a current allocation by a specified 936 * number of blocks. 937 * 938 * this routine attempts to satisfy the allocation request 939 * by first trying to extend the existing allocation in 940 * place by allocating the additional blocks as the blocks 941 * immediately following the current allocation. if these 942 * blocks are not available, this routine will attempt to 943 * allocate a new set of contiguous blocks large enough 944 * to cover the existing allocation plus the additional 945 * number of blocks required. 946 * 947 * PARAMETERS: 948 * ip - pointer to in-core inode requiring allocation. 949 * blkno - starting block of the current allocation. 950 * nblocks - number of contiguous blocks within the current 951 * allocation. 952 * addnblocks - number of blocks to add to the allocation. 953 * results - on successful return, set to the starting block number 954 * of the existing allocation if the existing allocation 955 * was extended in place or to a newly allocated contiguous 956 * range if the existing allocation could not be extended 957 * in place. 958 * 959 * RETURN VALUES: 960 * 0 - success 961 * -ENOSPC - insufficient disk resources 962 * -EIO - i/o error 963 */ 964 int 965 dbReAlloc(struct inode *ip, 966 s64 blkno, s64 nblocks, s64 addnblocks, s64 * results) 967 { 968 int rc; 969 970 /* try to extend the allocation in place. 971 */ 972 if ((rc = dbExtend(ip, blkno, nblocks, addnblocks)) == 0) { 973 *results = blkno; 974 return (0); 975 } else { 976 if (rc != -ENOSPC) 977 return (rc); 978 } 979 980 /* could not extend the allocation in place, so allocate a 981 * new set of blocks for the entire request (i.e. try to get 982 * a range of contiguous blocks large enough to cover the 983 * existing allocation plus the additional blocks.) 984 */ 985 return (dbAlloc 986 (ip, blkno + nblocks - 1, addnblocks + nblocks, results)); 987 } 988 989 990 /* 991 * NAME: dbExtend() 992 * 993 * FUNCTION: attempt to extend a current allocation by a specified 994 * number of blocks. 995 * 996 * this routine attempts to satisfy the allocation request 997 * by first trying to extend the existing allocation in 998 * place by allocating the additional blocks as the blocks 999 * immediately following the current allocation. 1000 * 1001 * PARAMETERS: 1002 * ip - pointer to in-core inode requiring allocation. 1003 * blkno - starting block of the current allocation. 1004 * nblocks - number of contiguous blocks within the current 1005 * allocation. 1006 * addnblocks - number of blocks to add to the allocation. 1007 * 1008 * RETURN VALUES: 1009 * 0 - success 1010 * -ENOSPC - insufficient disk resources 1011 * -EIO - i/o error 1012 */ 1013 static int dbExtend(struct inode *ip, s64 blkno, s64 nblocks, s64 addnblocks) 1014 { 1015 struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb); 1016 s64 lblkno, lastblkno, extblkno; 1017 uint rel_block; 1018 struct metapage *mp; 1019 struct dmap *dp; 1020 int rc; 1021 struct inode *ipbmap = sbi->ipbmap; 1022 struct bmap *bmp; 1023 1024 /* 1025 * We don't want a non-aligned extent to cross a page boundary 1026 */ 1027 if (((rel_block = blkno & (sbi->nbperpage - 1))) && 1028 (rel_block + nblocks + addnblocks > sbi->nbperpage)) 1029 return -ENOSPC; 1030 1031 /* get the last block of the current allocation */ 1032 lastblkno = blkno + nblocks - 1; 1033 1034 /* determine the block number of the block following 1035 * the existing allocation. 1036 */ 1037 extblkno = lastblkno + 1; 1038 1039 IREAD_LOCK(ipbmap, RDWRLOCK_DMAP); 1040 1041 /* better be within the file system */ 1042 bmp = sbi->bmap; 1043 if (lastblkno < 0 || lastblkno >= bmp->db_mapsize) { 1044 IREAD_UNLOCK(ipbmap); 1045 jfs_error(ip->i_sb, "the block is outside the filesystem\n"); 1046 return -EIO; 1047 } 1048 1049 /* we'll attempt to extend the current allocation in place by 1050 * allocating the additional blocks as the blocks immediately 1051 * following the current allocation. we only try to extend the 1052 * current allocation in place if the number of additional blocks 1053 * can fit into a dmap, the last block of the current allocation 1054 * is not the last block of the file system, and the start of the 1055 * inplace extension is not on an allocation group boundary. 1056 */ 1057 if (addnblocks > BPERDMAP || extblkno >= bmp->db_mapsize || 1058 (extblkno & (bmp->db_agsize - 1)) == 0) { 1059 IREAD_UNLOCK(ipbmap); 1060 return -ENOSPC; 1061 } 1062 1063 /* get the buffer for the dmap containing the first block 1064 * of the extension. 1065 */ 1066 lblkno = BLKTODMAP(extblkno, bmp->db_l2nbperpage); 1067 mp = read_metapage(ipbmap, lblkno, PSIZE, 0); 1068 if (mp == NULL) { 1069 IREAD_UNLOCK(ipbmap); 1070 return -EIO; 1071 } 1072 1073 dp = (struct dmap *) mp->data; 1074 1075 /* try to allocate the blocks immediately following the 1076 * current allocation. 1077 */ 1078 rc = dbAllocNext(bmp, dp, extblkno, (int) addnblocks); 1079 1080 IREAD_UNLOCK(ipbmap); 1081 1082 /* were we successful ? */ 1083 if (rc == 0) 1084 write_metapage(mp); 1085 else 1086 /* we were not successful */ 1087 release_metapage(mp); 1088 1089 return (rc); 1090 } 1091 1092 1093 /* 1094 * NAME: dbAllocNext() 1095 * 1096 * FUNCTION: attempt to allocate the blocks of the specified block 1097 * range within a dmap. 1098 * 1099 * PARAMETERS: 1100 * bmp - pointer to bmap descriptor 1101 * dp - pointer to dmap. 1102 * blkno - starting block number of the range. 1103 * nblocks - number of contiguous free blocks of the range. 1104 * 1105 * RETURN VALUES: 1106 * 0 - success 1107 * -ENOSPC - insufficient disk resources 1108 * -EIO - i/o error 1109 * 1110 * serialization: IREAD_LOCK(ipbmap) held on entry/exit; 1111 */ 1112 static int dbAllocNext(struct bmap * bmp, struct dmap * dp, s64 blkno, 1113 int nblocks) 1114 { 1115 int dbitno, word, rembits, nb, nwords, wbitno, nw; 1116 int l2size; 1117 s8 *leaf; 1118 u32 mask; 1119 1120 if (dp->tree.leafidx != cpu_to_le32(LEAFIND)) { 1121 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmap page\n"); 1122 return -EIO; 1123 } 1124 1125 /* pick up a pointer to the leaves of the dmap tree. 1126 */ 1127 leaf = dp->tree.stree + le32_to_cpu(dp->tree.leafidx); 1128 1129 /* determine the bit number and word within the dmap of the 1130 * starting block. 1131 */ 1132 dbitno = blkno & (BPERDMAP - 1); 1133 word = dbitno >> L2DBWORD; 1134 1135 /* check if the specified block range is contained within 1136 * this dmap. 1137 */ 1138 if (dbitno + nblocks > BPERDMAP) 1139 return -ENOSPC; 1140 1141 /* check if the starting leaf indicates that anything 1142 * is free. 1143 */ 1144 if (leaf[word] == NOFREE) 1145 return -ENOSPC; 1146 1147 /* check the dmaps words corresponding to block range to see 1148 * if the block range is free. not all bits of the first and 1149 * last words may be contained within the block range. if this 1150 * is the case, we'll work against those words (i.e. partial first 1151 * and/or last) on an individual basis (a single pass) and examine 1152 * the actual bits to determine if they are free. a single pass 1153 * will be used for all dmap words fully contained within the 1154 * specified range. within this pass, the leaves of the dmap 1155 * tree will be examined to determine if the blocks are free. a 1156 * single leaf may describe the free space of multiple dmap 1157 * words, so we may visit only a subset of the actual leaves 1158 * corresponding to the dmap words of the block range. 1159 */ 1160 for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) { 1161 /* determine the bit number within the word and 1162 * the number of bits within the word. 1163 */ 1164 wbitno = dbitno & (DBWORD - 1); 1165 nb = min(rembits, DBWORD - wbitno); 1166 1167 /* check if only part of the word is to be examined. 1168 */ 1169 if (nb < DBWORD) { 1170 /* check if the bits are free. 1171 */ 1172 mask = (ONES << (DBWORD - nb) >> wbitno); 1173 if ((mask & ~le32_to_cpu(dp->wmap[word])) != mask) 1174 return -ENOSPC; 1175 1176 word += 1; 1177 } else { 1178 /* one or more dmap words are fully contained 1179 * within the block range. determine how many 1180 * words and how many bits. 1181 */ 1182 nwords = rembits >> L2DBWORD; 1183 nb = nwords << L2DBWORD; 1184 1185 /* now examine the appropriate leaves to determine 1186 * if the blocks are free. 1187 */ 1188 while (nwords > 0) { 1189 /* does the leaf describe any free space ? 1190 */ 1191 if (leaf[word] < BUDMIN) 1192 return -ENOSPC; 1193 1194 /* determine the l2 number of bits provided 1195 * by this leaf. 1196 */ 1197 l2size = 1198 min_t(int, leaf[word], NLSTOL2BSZ(nwords)); 1199 1200 /* determine how many words were handled. 1201 */ 1202 nw = BUDSIZE(l2size, BUDMIN); 1203 1204 nwords -= nw; 1205 word += nw; 1206 } 1207 } 1208 } 1209 1210 /* allocate the blocks. 1211 */ 1212 return (dbAllocDmap(bmp, dp, blkno, nblocks)); 1213 } 1214 1215 1216 /* 1217 * NAME: dbAllocNear() 1218 * 1219 * FUNCTION: attempt to allocate a number of contiguous free blocks near 1220 * a specified block (hint) within a dmap. 1221 * 1222 * starting with the dmap leaf that covers the hint, we'll 1223 * check the next four contiguous leaves for sufficient free 1224 * space. if sufficient free space is found, we'll allocate 1225 * the desired free space. 1226 * 1227 * PARAMETERS: 1228 * bmp - pointer to bmap descriptor 1229 * dp - pointer to dmap. 1230 * blkno - block number to allocate near. 1231 * nblocks - actual number of contiguous free blocks desired. 1232 * l2nb - log2 number of contiguous free blocks desired. 1233 * results - on successful return, set to the starting block number 1234 * of the newly allocated range. 1235 * 1236 * RETURN VALUES: 1237 * 0 - success 1238 * -ENOSPC - insufficient disk resources 1239 * -EIO - i/o error 1240 * 1241 * serialization: IREAD_LOCK(ipbmap) held on entry/exit; 1242 */ 1243 static int 1244 dbAllocNear(struct bmap * bmp, 1245 struct dmap * dp, s64 blkno, int nblocks, int l2nb, s64 * results) 1246 { 1247 int word, lword, rc; 1248 s8 *leaf; 1249 1250 if (dp->tree.leafidx != cpu_to_le32(LEAFIND)) { 1251 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmap page\n"); 1252 return -EIO; 1253 } 1254 1255 leaf = dp->tree.stree + le32_to_cpu(dp->tree.leafidx); 1256 1257 /* determine the word within the dmap that holds the hint 1258 * (i.e. blkno). also, determine the last word in the dmap 1259 * that we'll include in our examination. 1260 */ 1261 word = (blkno & (BPERDMAP - 1)) >> L2DBWORD; 1262 lword = min(word + 4, LPERDMAP); 1263 1264 /* examine the leaves for sufficient free space. 1265 */ 1266 for (; word < lword; word++) { 1267 /* does the leaf describe sufficient free space ? 1268 */ 1269 if (leaf[word] < l2nb) 1270 continue; 1271 1272 /* determine the block number within the file system 1273 * of the first block described by this dmap word. 1274 */ 1275 blkno = le64_to_cpu(dp->start) + (word << L2DBWORD); 1276 1277 /* if not all bits of the dmap word are free, get the 1278 * starting bit number within the dmap word of the required 1279 * string of free bits and adjust the block number with the 1280 * value. 1281 */ 1282 if (leaf[word] < BUDMIN) 1283 blkno += 1284 dbFindBits(le32_to_cpu(dp->wmap[word]), l2nb); 1285 1286 /* allocate the blocks. 1287 */ 1288 if ((rc = dbAllocDmap(bmp, dp, blkno, nblocks)) == 0) 1289 *results = blkno; 1290 1291 return (rc); 1292 } 1293 1294 return -ENOSPC; 1295 } 1296 1297 1298 /* 1299 * NAME: dbAllocAG() 1300 * 1301 * FUNCTION: attempt to allocate the specified number of contiguous 1302 * free blocks within the specified allocation group. 1303 * 1304 * unless the allocation group size is equal to the number 1305 * of blocks per dmap, the dmap control pages will be used to 1306 * find the required free space, if available. we start the 1307 * search at the highest dmap control page level which 1308 * distinctly describes the allocation group's free space 1309 * (i.e. the highest level at which the allocation group's 1310 * free space is not mixed in with that of any other group). 1311 * in addition, we start the search within this level at a 1312 * height of the dmapctl dmtree at which the nodes distinctly 1313 * describe the allocation group's free space. at this height, 1314 * the allocation group's free space may be represented by 1 1315 * or two sub-trees, depending on the allocation group size. 1316 * we search the top nodes of these subtrees left to right for 1317 * sufficient free space. if sufficient free space is found, 1318 * the subtree is searched to find the leftmost leaf that 1319 * has free space. once we have made it to the leaf, we 1320 * move the search to the next lower level dmap control page 1321 * corresponding to this leaf. we continue down the dmap control 1322 * pages until we find the dmap that contains or starts the 1323 * sufficient free space and we allocate at this dmap. 1324 * 1325 * if the allocation group size is equal to the dmap size, 1326 * we'll start at the dmap corresponding to the allocation 1327 * group and attempt the allocation at this level. 1328 * 1329 * the dmap control page search is also not performed if the 1330 * allocation group is completely free and we go to the first 1331 * dmap of the allocation group to do the allocation. this is 1332 * done because the allocation group may be part (not the first 1333 * part) of a larger binary buddy system, causing the dmap 1334 * control pages to indicate no free space (NOFREE) within 1335 * the allocation group. 1336 * 1337 * PARAMETERS: 1338 * bmp - pointer to bmap descriptor 1339 * agno - allocation group number. 1340 * nblocks - actual number of contiguous free blocks desired. 1341 * l2nb - log2 number of contiguous free blocks desired. 1342 * results - on successful return, set to the starting block number 1343 * of the newly allocated range. 1344 * 1345 * RETURN VALUES: 1346 * 0 - success 1347 * -ENOSPC - insufficient disk resources 1348 * -EIO - i/o error 1349 * 1350 * note: IWRITE_LOCK(ipmap) held on entry/exit; 1351 */ 1352 static int 1353 dbAllocAG(struct bmap * bmp, int agno, s64 nblocks, int l2nb, s64 * results) 1354 { 1355 struct metapage *mp; 1356 struct dmapctl *dcp; 1357 int rc, ti, i, k, m, n, agperlev; 1358 s64 blkno, lblkno; 1359 int budmin; 1360 1361 /* allocation request should not be for more than the 1362 * allocation group size. 1363 */ 1364 if (l2nb > bmp->db_agl2size) { 1365 jfs_error(bmp->db_ipbmap->i_sb, 1366 "allocation request is larger than the allocation group size\n"); 1367 return -EIO; 1368 } 1369 1370 /* determine the starting block number of the allocation 1371 * group. 1372 */ 1373 blkno = (s64) agno << bmp->db_agl2size; 1374 1375 /* check if the allocation group size is the minimum allocation 1376 * group size or if the allocation group is completely free. if 1377 * the allocation group size is the minimum size of BPERDMAP (i.e. 1378 * 1 dmap), there is no need to search the dmap control page (below) 1379 * that fully describes the allocation group since the allocation 1380 * group is already fully described by a dmap. in this case, we 1381 * just call dbAllocCtl() to search the dmap tree and allocate the 1382 * required space if available. 1383 * 1384 * if the allocation group is completely free, dbAllocCtl() is 1385 * also called to allocate the required space. this is done for 1386 * two reasons. first, it makes no sense searching the dmap control 1387 * pages for free space when we know that free space exists. second, 1388 * the dmap control pages may indicate that the allocation group 1389 * has no free space if the allocation group is part (not the first 1390 * part) of a larger binary buddy system. 1391 */ 1392 if (bmp->db_agsize == BPERDMAP 1393 || bmp->db_agfree[agno] == bmp->db_agsize) { 1394 rc = dbAllocCtl(bmp, nblocks, l2nb, blkno, results); 1395 if ((rc == -ENOSPC) && 1396 (bmp->db_agfree[agno] == bmp->db_agsize)) { 1397 printk(KERN_ERR "blkno = %Lx, blocks = %Lx\n", 1398 (unsigned long long) blkno, 1399 (unsigned long long) nblocks); 1400 jfs_error(bmp->db_ipbmap->i_sb, 1401 "dbAllocCtl failed in free AG\n"); 1402 } 1403 return (rc); 1404 } 1405 1406 /* the buffer for the dmap control page that fully describes the 1407 * allocation group. 1408 */ 1409 lblkno = BLKTOCTL(blkno, bmp->db_l2nbperpage, bmp->db_aglevel); 1410 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); 1411 if (mp == NULL) 1412 return -EIO; 1413 dcp = (struct dmapctl *) mp->data; 1414 budmin = dcp->budmin; 1415 1416 if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) { 1417 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmapctl page\n"); 1418 release_metapage(mp); 1419 return -EIO; 1420 } 1421 1422 /* search the subtree(s) of the dmap control page that describes 1423 * the allocation group, looking for sufficient free space. to begin, 1424 * determine how many allocation groups are represented in a dmap 1425 * control page at the control page level (i.e. L0, L1, L2) that 1426 * fully describes an allocation group. next, determine the starting 1427 * tree index of this allocation group within the control page. 1428 */ 1429 agperlev = 1430 (1 << (L2LPERCTL - (bmp->db_agheight << 1))) / bmp->db_agwidth; 1431 ti = bmp->db_agstart + bmp->db_agwidth * (agno & (agperlev - 1)); 1432 1433 /* dmap control page trees fan-out by 4 and a single allocation 1434 * group may be described by 1 or 2 subtrees within the ag level 1435 * dmap control page, depending upon the ag size. examine the ag's 1436 * subtrees for sufficient free space, starting with the leftmost 1437 * subtree. 1438 */ 1439 for (i = 0; i < bmp->db_agwidth; i++, ti++) { 1440 /* is there sufficient free space ? 1441 */ 1442 if (l2nb > dcp->stree[ti]) 1443 continue; 1444 1445 /* sufficient free space found in a subtree. now search down 1446 * the subtree to find the leftmost leaf that describes this 1447 * free space. 1448 */ 1449 for (k = bmp->db_agheight; k > 0; k--) { 1450 for (n = 0, m = (ti << 2) + 1; n < 4; n++) { 1451 if (l2nb <= dcp->stree[m + n]) { 1452 ti = m + n; 1453 break; 1454 } 1455 } 1456 if (n == 4) { 1457 jfs_error(bmp->db_ipbmap->i_sb, 1458 "failed descending stree\n"); 1459 release_metapage(mp); 1460 return -EIO; 1461 } 1462 } 1463 1464 /* determine the block number within the file system 1465 * that corresponds to this leaf. 1466 */ 1467 if (bmp->db_aglevel == 2) 1468 blkno = 0; 1469 else if (bmp->db_aglevel == 1) 1470 blkno &= ~(MAXL1SIZE - 1); 1471 else /* bmp->db_aglevel == 0 */ 1472 blkno &= ~(MAXL0SIZE - 1); 1473 1474 blkno += 1475 ((s64) (ti - le32_to_cpu(dcp->leafidx))) << budmin; 1476 1477 /* release the buffer in preparation for going down 1478 * the next level of dmap control pages. 1479 */ 1480 release_metapage(mp); 1481 1482 /* check if we need to continue to search down the lower 1483 * level dmap control pages. we need to if the number of 1484 * blocks required is less than maximum number of blocks 1485 * described at the next lower level. 1486 */ 1487 if (l2nb < budmin) { 1488 1489 /* search the lower level dmap control pages to get 1490 * the starting block number of the dmap that 1491 * contains or starts off the free space. 1492 */ 1493 if ((rc = 1494 dbFindCtl(bmp, l2nb, bmp->db_aglevel - 1, 1495 &blkno))) { 1496 if (rc == -ENOSPC) { 1497 jfs_error(bmp->db_ipbmap->i_sb, 1498 "control page inconsistent\n"); 1499 return -EIO; 1500 } 1501 return (rc); 1502 } 1503 } 1504 1505 /* allocate the blocks. 1506 */ 1507 rc = dbAllocCtl(bmp, nblocks, l2nb, blkno, results); 1508 if (rc == -ENOSPC) { 1509 jfs_error(bmp->db_ipbmap->i_sb, 1510 "unable to allocate blocks\n"); 1511 rc = -EIO; 1512 } 1513 return (rc); 1514 } 1515 1516 /* no space in the allocation group. release the buffer and 1517 * return -ENOSPC. 1518 */ 1519 release_metapage(mp); 1520 1521 return -ENOSPC; 1522 } 1523 1524 1525 /* 1526 * NAME: dbAllocAny() 1527 * 1528 * FUNCTION: attempt to allocate the specified number of contiguous 1529 * free blocks anywhere in the file system. 1530 * 1531 * dbAllocAny() attempts to find the sufficient free space by 1532 * searching down the dmap control pages, starting with the 1533 * highest level (i.e. L0, L1, L2) control page. if free space 1534 * large enough to satisfy the desired free space is found, the 1535 * desired free space is allocated. 1536 * 1537 * PARAMETERS: 1538 * bmp - pointer to bmap descriptor 1539 * nblocks - actual number of contiguous free blocks desired. 1540 * l2nb - log2 number of contiguous free blocks desired. 1541 * results - on successful return, set to the starting block number 1542 * of the newly allocated range. 1543 * 1544 * RETURN VALUES: 1545 * 0 - success 1546 * -ENOSPC - insufficient disk resources 1547 * -EIO - i/o error 1548 * 1549 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit; 1550 */ 1551 static int dbAllocAny(struct bmap * bmp, s64 nblocks, int l2nb, s64 * results) 1552 { 1553 int rc; 1554 s64 blkno = 0; 1555 1556 /* starting with the top level dmap control page, search 1557 * down the dmap control levels for sufficient free space. 1558 * if free space is found, dbFindCtl() returns the starting 1559 * block number of the dmap that contains or starts off the 1560 * range of free space. 1561 */ 1562 if ((rc = dbFindCtl(bmp, l2nb, bmp->db_maxlevel, &blkno))) 1563 return (rc); 1564 1565 /* allocate the blocks. 1566 */ 1567 rc = dbAllocCtl(bmp, nblocks, l2nb, blkno, results); 1568 if (rc == -ENOSPC) { 1569 jfs_error(bmp->db_ipbmap->i_sb, "unable to allocate blocks\n"); 1570 return -EIO; 1571 } 1572 return (rc); 1573 } 1574 1575 1576 /* 1577 * NAME: dbDiscardAG() 1578 * 1579 * FUNCTION: attempt to discard (TRIM) all free blocks of specific AG 1580 * 1581 * algorithm: 1582 * 1) allocate blocks, as large as possible and save them 1583 * while holding IWRITE_LOCK on ipbmap 1584 * 2) trim all these saved block/length values 1585 * 3) mark the blocks free again 1586 * 1587 * benefit: 1588 * - we work only on one ag at some time, minimizing how long we 1589 * need to lock ipbmap 1590 * - reading / writing the fs is possible most time, even on 1591 * trimming 1592 * 1593 * downside: 1594 * - we write two times to the dmapctl and dmap pages 1595 * - but for me, this seems the best way, better ideas? 1596 * /TR 2012 1597 * 1598 * PARAMETERS: 1599 * ip - pointer to in-core inode 1600 * agno - ag to trim 1601 * minlen - minimum value of contiguous blocks 1602 * 1603 * RETURN VALUES: 1604 * s64 - actual number of blocks trimmed 1605 */ 1606 s64 dbDiscardAG(struct inode *ip, int agno, s64 minlen) 1607 { 1608 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap; 1609 struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap; 1610 s64 nblocks, blkno; 1611 u64 trimmed = 0; 1612 int rc, l2nb; 1613 struct super_block *sb = ipbmap->i_sb; 1614 1615 struct range2trim { 1616 u64 blkno; 1617 u64 nblocks; 1618 } *totrim, *tt; 1619 1620 /* max blkno / nblocks pairs to trim */ 1621 int count = 0, range_cnt; 1622 u64 max_ranges; 1623 1624 /* prevent others from writing new stuff here, while trimming */ 1625 IWRITE_LOCK(ipbmap, RDWRLOCK_DMAP); 1626 1627 nblocks = bmp->db_agfree[agno]; 1628 max_ranges = nblocks; 1629 do_div(max_ranges, minlen); 1630 range_cnt = min_t(u64, max_ranges + 1, 32 * 1024); 1631 totrim = kmalloc_array(range_cnt, sizeof(struct range2trim), GFP_NOFS); 1632 if (totrim == NULL) { 1633 jfs_error(bmp->db_ipbmap->i_sb, "no memory for trim array\n"); 1634 IWRITE_UNLOCK(ipbmap); 1635 return 0; 1636 } 1637 1638 tt = totrim; 1639 while (nblocks >= minlen) { 1640 l2nb = BLKSTOL2(nblocks); 1641 1642 /* 0 = okay, -EIO = fatal, -ENOSPC -> try smaller block */ 1643 rc = dbAllocAG(bmp, agno, nblocks, l2nb, &blkno); 1644 if (rc == 0) { 1645 tt->blkno = blkno; 1646 tt->nblocks = nblocks; 1647 tt++; count++; 1648 1649 /* the whole ag is free, trim now */ 1650 if (bmp->db_agfree[agno] == 0) 1651 break; 1652 1653 /* give a hint for the next while */ 1654 nblocks = bmp->db_agfree[agno]; 1655 continue; 1656 } else if (rc == -ENOSPC) { 1657 /* search for next smaller log2 block */ 1658 l2nb = BLKSTOL2(nblocks) - 1; 1659 nblocks = 1LL << l2nb; 1660 } else { 1661 /* Trim any already allocated blocks */ 1662 jfs_error(bmp->db_ipbmap->i_sb, "-EIO\n"); 1663 break; 1664 } 1665 1666 /* check, if our trim array is full */ 1667 if (unlikely(count >= range_cnt - 1)) 1668 break; 1669 } 1670 IWRITE_UNLOCK(ipbmap); 1671 1672 tt->nblocks = 0; /* mark the current end */ 1673 for (tt = totrim; tt->nblocks != 0; tt++) { 1674 /* when mounted with online discard, dbFree() will 1675 * call jfs_issue_discard() itself */ 1676 if (!(JFS_SBI(sb)->flag & JFS_DISCARD)) 1677 jfs_issue_discard(ip, tt->blkno, tt->nblocks); 1678 dbFree(ip, tt->blkno, tt->nblocks); 1679 trimmed += tt->nblocks; 1680 } 1681 kfree(totrim); 1682 1683 return trimmed; 1684 } 1685 1686 /* 1687 * NAME: dbFindCtl() 1688 * 1689 * FUNCTION: starting at a specified dmap control page level and block 1690 * number, search down the dmap control levels for a range of 1691 * contiguous free blocks large enough to satisfy an allocation 1692 * request for the specified number of free blocks. 1693 * 1694 * if sufficient contiguous free blocks are found, this routine 1695 * returns the starting block number within a dmap page that 1696 * contains or starts a range of contiqious free blocks that 1697 * is sufficient in size. 1698 * 1699 * PARAMETERS: 1700 * bmp - pointer to bmap descriptor 1701 * level - starting dmap control page level. 1702 * l2nb - log2 number of contiguous free blocks desired. 1703 * *blkno - on entry, starting block number for conducting the search. 1704 * on successful return, the first block within a dmap page 1705 * that contains or starts a range of contiguous free blocks. 1706 * 1707 * RETURN VALUES: 1708 * 0 - success 1709 * -ENOSPC - insufficient disk resources 1710 * -EIO - i/o error 1711 * 1712 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit; 1713 */ 1714 static int dbFindCtl(struct bmap * bmp, int l2nb, int level, s64 * blkno) 1715 { 1716 int rc, leafidx, lev; 1717 s64 b, lblkno; 1718 struct dmapctl *dcp; 1719 int budmin; 1720 struct metapage *mp; 1721 1722 /* starting at the specified dmap control page level and block 1723 * number, search down the dmap control levels for the starting 1724 * block number of a dmap page that contains or starts off 1725 * sufficient free blocks. 1726 */ 1727 for (lev = level, b = *blkno; lev >= 0; lev--) { 1728 /* get the buffer of the dmap control page for the block 1729 * number and level (i.e. L0, L1, L2). 1730 */ 1731 lblkno = BLKTOCTL(b, bmp->db_l2nbperpage, lev); 1732 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); 1733 if (mp == NULL) 1734 return -EIO; 1735 dcp = (struct dmapctl *) mp->data; 1736 budmin = dcp->budmin; 1737 1738 if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) { 1739 jfs_error(bmp->db_ipbmap->i_sb, 1740 "Corrupt dmapctl page\n"); 1741 release_metapage(mp); 1742 return -EIO; 1743 } 1744 1745 /* search the tree within the dmap control page for 1746 * sufficient free space. if sufficient free space is found, 1747 * dbFindLeaf() returns the index of the leaf at which 1748 * free space was found. 1749 */ 1750 rc = dbFindLeaf((dmtree_t *) dcp, l2nb, &leafidx); 1751 1752 /* release the buffer. 1753 */ 1754 release_metapage(mp); 1755 1756 /* space found ? 1757 */ 1758 if (rc) { 1759 if (lev != level) { 1760 jfs_error(bmp->db_ipbmap->i_sb, 1761 "dmap inconsistent\n"); 1762 return -EIO; 1763 } 1764 return -ENOSPC; 1765 } 1766 1767 /* adjust the block number to reflect the location within 1768 * the dmap control page (i.e. the leaf) at which free 1769 * space was found. 1770 */ 1771 b += (((s64) leafidx) << budmin); 1772 1773 /* we stop the search at this dmap control page level if 1774 * the number of blocks required is greater than or equal 1775 * to the maximum number of blocks described at the next 1776 * (lower) level. 1777 */ 1778 if (l2nb >= budmin) 1779 break; 1780 } 1781 1782 *blkno = b; 1783 return (0); 1784 } 1785 1786 1787 /* 1788 * NAME: dbAllocCtl() 1789 * 1790 * FUNCTION: attempt to allocate a specified number of contiguous 1791 * blocks starting within a specific dmap. 1792 * 1793 * this routine is called by higher level routines that search 1794 * the dmap control pages above the actual dmaps for contiguous 1795 * free space. the result of successful searches by these 1796 * routines are the starting block numbers within dmaps, with 1797 * the dmaps themselves containing the desired contiguous free 1798 * space or starting a contiguous free space of desired size 1799 * that is made up of the blocks of one or more dmaps. these 1800 * calls should not fail due to insufficent resources. 1801 * 1802 * this routine is called in some cases where it is not known 1803 * whether it will fail due to insufficient resources. more 1804 * specifically, this occurs when allocating from an allocation 1805 * group whose size is equal to the number of blocks per dmap. 1806 * in this case, the dmap control pages are not examined prior 1807 * to calling this routine (to save pathlength) and the call 1808 * might fail. 1809 * 1810 * for a request size that fits within a dmap, this routine relies 1811 * upon the dmap's dmtree to find the requested contiguous free 1812 * space. for request sizes that are larger than a dmap, the 1813 * requested free space will start at the first block of the 1814 * first dmap (i.e. blkno). 1815 * 1816 * PARAMETERS: 1817 * bmp - pointer to bmap descriptor 1818 * nblocks - actual number of contiguous free blocks to allocate. 1819 * l2nb - log2 number of contiguous free blocks to allocate. 1820 * blkno - starting block number of the dmap to start the allocation 1821 * from. 1822 * results - on successful return, set to the starting block number 1823 * of the newly allocated range. 1824 * 1825 * RETURN VALUES: 1826 * 0 - success 1827 * -ENOSPC - insufficient disk resources 1828 * -EIO - i/o error 1829 * 1830 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit; 1831 */ 1832 static int 1833 dbAllocCtl(struct bmap * bmp, s64 nblocks, int l2nb, s64 blkno, s64 * results) 1834 { 1835 int rc, nb; 1836 s64 b, lblkno, n; 1837 struct metapage *mp; 1838 struct dmap *dp; 1839 1840 /* check if the allocation request is confined to a single dmap. 1841 */ 1842 if (l2nb <= L2BPERDMAP) { 1843 /* get the buffer for the dmap. 1844 */ 1845 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); 1846 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); 1847 if (mp == NULL) 1848 return -EIO; 1849 dp = (struct dmap *) mp->data; 1850 1851 /* try to allocate the blocks. 1852 */ 1853 rc = dbAllocDmapLev(bmp, dp, (int) nblocks, l2nb, results); 1854 if (rc == 0) 1855 mark_metapage_dirty(mp); 1856 1857 release_metapage(mp); 1858 1859 return (rc); 1860 } 1861 1862 /* allocation request involving multiple dmaps. it must start on 1863 * a dmap boundary. 1864 */ 1865 assert((blkno & (BPERDMAP - 1)) == 0); 1866 1867 /* allocate the blocks dmap by dmap. 1868 */ 1869 for (n = nblocks, b = blkno; n > 0; n -= nb, b += nb) { 1870 /* get the buffer for the dmap. 1871 */ 1872 lblkno = BLKTODMAP(b, bmp->db_l2nbperpage); 1873 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); 1874 if (mp == NULL) { 1875 rc = -EIO; 1876 goto backout; 1877 } 1878 dp = (struct dmap *) mp->data; 1879 1880 /* the dmap better be all free. 1881 */ 1882 if (dp->tree.stree[ROOT] != L2BPERDMAP) { 1883 release_metapage(mp); 1884 jfs_error(bmp->db_ipbmap->i_sb, 1885 "the dmap is not all free\n"); 1886 rc = -EIO; 1887 goto backout; 1888 } 1889 1890 /* determine how many blocks to allocate from this dmap. 1891 */ 1892 nb = min_t(s64, n, BPERDMAP); 1893 1894 /* allocate the blocks from the dmap. 1895 */ 1896 if ((rc = dbAllocDmap(bmp, dp, b, nb))) { 1897 release_metapage(mp); 1898 goto backout; 1899 } 1900 1901 /* write the buffer. 1902 */ 1903 write_metapage(mp); 1904 } 1905 1906 /* set the results (starting block number) and return. 1907 */ 1908 *results = blkno; 1909 return (0); 1910 1911 /* something failed in handling an allocation request involving 1912 * multiple dmaps. we'll try to clean up by backing out any 1913 * allocation that has already happened for this request. if 1914 * we fail in backing out the allocation, we'll mark the file 1915 * system to indicate that blocks have been leaked. 1916 */ 1917 backout: 1918 1919 /* try to backout the allocations dmap by dmap. 1920 */ 1921 for (n = nblocks - n, b = blkno; n > 0; 1922 n -= BPERDMAP, b += BPERDMAP) { 1923 /* get the buffer for this dmap. 1924 */ 1925 lblkno = BLKTODMAP(b, bmp->db_l2nbperpage); 1926 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); 1927 if (mp == NULL) { 1928 /* could not back out. mark the file system 1929 * to indicate that we have leaked blocks. 1930 */ 1931 jfs_error(bmp->db_ipbmap->i_sb, 1932 "I/O Error: Block Leakage\n"); 1933 continue; 1934 } 1935 dp = (struct dmap *) mp->data; 1936 1937 /* free the blocks is this dmap. 1938 */ 1939 if (dbFreeDmap(bmp, dp, b, BPERDMAP)) { 1940 /* could not back out. mark the file system 1941 * to indicate that we have leaked blocks. 1942 */ 1943 release_metapage(mp); 1944 jfs_error(bmp->db_ipbmap->i_sb, "Block Leakage\n"); 1945 continue; 1946 } 1947 1948 /* write the buffer. 1949 */ 1950 write_metapage(mp); 1951 } 1952 1953 return (rc); 1954 } 1955 1956 1957 /* 1958 * NAME: dbAllocDmapLev() 1959 * 1960 * FUNCTION: attempt to allocate a specified number of contiguous blocks 1961 * from a specified dmap. 1962 * 1963 * this routine checks if the contiguous blocks are available. 1964 * if so, nblocks of blocks are allocated; otherwise, ENOSPC is 1965 * returned. 1966 * 1967 * PARAMETERS: 1968 * mp - pointer to bmap descriptor 1969 * dp - pointer to dmap to attempt to allocate blocks from. 1970 * l2nb - log2 number of contiguous block desired. 1971 * nblocks - actual number of contiguous block desired. 1972 * results - on successful return, set to the starting block number 1973 * of the newly allocated range. 1974 * 1975 * RETURN VALUES: 1976 * 0 - success 1977 * -ENOSPC - insufficient disk resources 1978 * -EIO - i/o error 1979 * 1980 * serialization: IREAD_LOCK(ipbmap), e.g., from dbAlloc(), or 1981 * IWRITE_LOCK(ipbmap), e.g., dbAllocCtl(), held on entry/exit; 1982 */ 1983 static int 1984 dbAllocDmapLev(struct bmap * bmp, 1985 struct dmap * dp, int nblocks, int l2nb, s64 * results) 1986 { 1987 s64 blkno; 1988 int leafidx, rc; 1989 1990 /* can't be more than a dmaps worth of blocks */ 1991 assert(l2nb <= L2BPERDMAP); 1992 1993 /* search the tree within the dmap page for sufficient 1994 * free space. if sufficient free space is found, dbFindLeaf() 1995 * returns the index of the leaf at which free space was found. 1996 */ 1997 if (dbFindLeaf((dmtree_t *) & dp->tree, l2nb, &leafidx)) 1998 return -ENOSPC; 1999 2000 /* determine the block number within the file system corresponding 2001 * to the leaf at which free space was found. 2002 */ 2003 blkno = le64_to_cpu(dp->start) + (leafidx << L2DBWORD); 2004 2005 /* if not all bits of the dmap word are free, get the starting 2006 * bit number within the dmap word of the required string of free 2007 * bits and adjust the block number with this value. 2008 */ 2009 if (dp->tree.stree[leafidx + LEAFIND] < BUDMIN) 2010 blkno += dbFindBits(le32_to_cpu(dp->wmap[leafidx]), l2nb); 2011 2012 /* allocate the blocks */ 2013 if ((rc = dbAllocDmap(bmp, dp, blkno, nblocks)) == 0) 2014 *results = blkno; 2015 2016 return (rc); 2017 } 2018 2019 2020 /* 2021 * NAME: dbAllocDmap() 2022 * 2023 * FUNCTION: adjust the disk allocation map to reflect the allocation 2024 * of a specified block range within a dmap. 2025 * 2026 * this routine allocates the specified blocks from the dmap 2027 * through a call to dbAllocBits(). if the allocation of the 2028 * block range causes the maximum string of free blocks within 2029 * the dmap to change (i.e. the value of the root of the dmap's 2030 * dmtree), this routine will cause this change to be reflected 2031 * up through the appropriate levels of the dmap control pages 2032 * by a call to dbAdjCtl() for the L0 dmap control page that 2033 * covers this dmap. 2034 * 2035 * PARAMETERS: 2036 * bmp - pointer to bmap descriptor 2037 * dp - pointer to dmap to allocate the block range from. 2038 * blkno - starting block number of the block to be allocated. 2039 * nblocks - number of blocks to be allocated. 2040 * 2041 * RETURN VALUES: 2042 * 0 - success 2043 * -EIO - i/o error 2044 * 2045 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit; 2046 */ 2047 static int dbAllocDmap(struct bmap * bmp, struct dmap * dp, s64 blkno, 2048 int nblocks) 2049 { 2050 s8 oldroot; 2051 int rc; 2052 2053 /* save the current value of the root (i.e. maximum free string) 2054 * of the dmap tree. 2055 */ 2056 oldroot = dp->tree.stree[ROOT]; 2057 2058 /* allocate the specified (blocks) bits */ 2059 dbAllocBits(bmp, dp, blkno, nblocks); 2060 2061 /* if the root has not changed, done. */ 2062 if (dp->tree.stree[ROOT] == oldroot) 2063 return (0); 2064 2065 /* root changed. bubble the change up to the dmap control pages. 2066 * if the adjustment of the upper level control pages fails, 2067 * backout the bit allocation (thus making everything consistent). 2068 */ 2069 if ((rc = dbAdjCtl(bmp, blkno, dp->tree.stree[ROOT], 1, 0))) 2070 dbFreeBits(bmp, dp, blkno, nblocks); 2071 2072 return (rc); 2073 } 2074 2075 2076 /* 2077 * NAME: dbFreeDmap() 2078 * 2079 * FUNCTION: adjust the disk allocation map to reflect the allocation 2080 * of a specified block range within a dmap. 2081 * 2082 * this routine frees the specified blocks from the dmap through 2083 * a call to dbFreeBits(). if the deallocation of the block range 2084 * causes the maximum string of free blocks within the dmap to 2085 * change (i.e. the value of the root of the dmap's dmtree), this 2086 * routine will cause this change to be reflected up through the 2087 * appropriate levels of the dmap control pages by a call to 2088 * dbAdjCtl() for the L0 dmap control page that covers this dmap. 2089 * 2090 * PARAMETERS: 2091 * bmp - pointer to bmap descriptor 2092 * dp - pointer to dmap to free the block range from. 2093 * blkno - starting block number of the block to be freed. 2094 * nblocks - number of blocks to be freed. 2095 * 2096 * RETURN VALUES: 2097 * 0 - success 2098 * -EIO - i/o error 2099 * 2100 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit; 2101 */ 2102 static int dbFreeDmap(struct bmap * bmp, struct dmap * dp, s64 blkno, 2103 int nblocks) 2104 { 2105 s8 oldroot; 2106 int rc = 0, word; 2107 2108 /* save the current value of the root (i.e. maximum free string) 2109 * of the dmap tree. 2110 */ 2111 oldroot = dp->tree.stree[ROOT]; 2112 2113 /* free the specified (blocks) bits */ 2114 rc = dbFreeBits(bmp, dp, blkno, nblocks); 2115 2116 /* if error or the root has not changed, done. */ 2117 if (rc || (dp->tree.stree[ROOT] == oldroot)) 2118 return (rc); 2119 2120 /* root changed. bubble the change up to the dmap control pages. 2121 * if the adjustment of the upper level control pages fails, 2122 * backout the deallocation. 2123 */ 2124 if ((rc = dbAdjCtl(bmp, blkno, dp->tree.stree[ROOT], 0, 0))) { 2125 word = (blkno & (BPERDMAP - 1)) >> L2DBWORD; 2126 2127 /* as part of backing out the deallocation, we will have 2128 * to back split the dmap tree if the deallocation caused 2129 * the freed blocks to become part of a larger binary buddy 2130 * system. 2131 */ 2132 if (dp->tree.stree[word] == NOFREE) 2133 dbBackSplit((dmtree_t *) & dp->tree, word); 2134 2135 dbAllocBits(bmp, dp, blkno, nblocks); 2136 } 2137 2138 return (rc); 2139 } 2140 2141 2142 /* 2143 * NAME: dbAllocBits() 2144 * 2145 * FUNCTION: allocate a specified block range from a dmap. 2146 * 2147 * this routine updates the dmap to reflect the working 2148 * state allocation of the specified block range. it directly 2149 * updates the bits of the working map and causes the adjustment 2150 * of the binary buddy system described by the dmap's dmtree 2151 * leaves to reflect the bits allocated. it also causes the 2152 * dmap's dmtree, as a whole, to reflect the allocated range. 2153 * 2154 * PARAMETERS: 2155 * bmp - pointer to bmap descriptor 2156 * dp - pointer to dmap to allocate bits from. 2157 * blkno - starting block number of the bits to be allocated. 2158 * nblocks - number of bits to be allocated. 2159 * 2160 * RETURN VALUES: none 2161 * 2162 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit; 2163 */ 2164 static void dbAllocBits(struct bmap * bmp, struct dmap * dp, s64 blkno, 2165 int nblocks) 2166 { 2167 int dbitno, word, rembits, nb, nwords, wbitno, nw, agno; 2168 dmtree_t *tp = (dmtree_t *) & dp->tree; 2169 int size; 2170 s8 *leaf; 2171 2172 /* pick up a pointer to the leaves of the dmap tree */ 2173 leaf = dp->tree.stree + LEAFIND; 2174 2175 /* determine the bit number and word within the dmap of the 2176 * starting block. 2177 */ 2178 dbitno = blkno & (BPERDMAP - 1); 2179 word = dbitno >> L2DBWORD; 2180 2181 /* block range better be within the dmap */ 2182 assert(dbitno + nblocks <= BPERDMAP); 2183 2184 /* allocate the bits of the dmap's words corresponding to the block 2185 * range. not all bits of the first and last words may be contained 2186 * within the block range. if this is the case, we'll work against 2187 * those words (i.e. partial first and/or last) on an individual basis 2188 * (a single pass), allocating the bits of interest by hand and 2189 * updating the leaf corresponding to the dmap word. a single pass 2190 * will be used for all dmap words fully contained within the 2191 * specified range. within this pass, the bits of all fully contained 2192 * dmap words will be marked as free in a single shot and the leaves 2193 * will be updated. a single leaf may describe the free space of 2194 * multiple dmap words, so we may update only a subset of the actual 2195 * leaves corresponding to the dmap words of the block range. 2196 */ 2197 for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) { 2198 /* determine the bit number within the word and 2199 * the number of bits within the word. 2200 */ 2201 wbitno = dbitno & (DBWORD - 1); 2202 nb = min(rembits, DBWORD - wbitno); 2203 2204 /* check if only part of a word is to be allocated. 2205 */ 2206 if (nb < DBWORD) { 2207 /* allocate (set to 1) the appropriate bits within 2208 * this dmap word. 2209 */ 2210 dp->wmap[word] |= cpu_to_le32(ONES << (DBWORD - nb) 2211 >> wbitno); 2212 2213 /* update the leaf for this dmap word. in addition 2214 * to setting the leaf value to the binary buddy max 2215 * of the updated dmap word, dbSplit() will split 2216 * the binary system of the leaves if need be. 2217 */ 2218 dbSplit(tp, word, BUDMIN, 2219 dbMaxBud((u8 *) & dp->wmap[word])); 2220 2221 word += 1; 2222 } else { 2223 /* one or more dmap words are fully contained 2224 * within the block range. determine how many 2225 * words and allocate (set to 1) the bits of these 2226 * words. 2227 */ 2228 nwords = rembits >> L2DBWORD; 2229 memset(&dp->wmap[word], (int) ONES, nwords * 4); 2230 2231 /* determine how many bits. 2232 */ 2233 nb = nwords << L2DBWORD; 2234 2235 /* now update the appropriate leaves to reflect 2236 * the allocated words. 2237 */ 2238 for (; nwords > 0; nwords -= nw) { 2239 if (leaf[word] < BUDMIN) { 2240 jfs_error(bmp->db_ipbmap->i_sb, 2241 "leaf page corrupt\n"); 2242 break; 2243 } 2244 2245 /* determine what the leaf value should be 2246 * updated to as the minimum of the l2 number 2247 * of bits being allocated and the l2 number 2248 * of bits currently described by this leaf. 2249 */ 2250 size = min_t(int, leaf[word], 2251 NLSTOL2BSZ(nwords)); 2252 2253 /* update the leaf to reflect the allocation. 2254 * in addition to setting the leaf value to 2255 * NOFREE, dbSplit() will split the binary 2256 * system of the leaves to reflect the current 2257 * allocation (size). 2258 */ 2259 dbSplit(tp, word, size, NOFREE); 2260 2261 /* get the number of dmap words handled */ 2262 nw = BUDSIZE(size, BUDMIN); 2263 word += nw; 2264 } 2265 } 2266 } 2267 2268 /* update the free count for this dmap */ 2269 le32_add_cpu(&dp->nfree, -nblocks); 2270 2271 BMAP_LOCK(bmp); 2272 2273 /* if this allocation group is completely free, 2274 * update the maximum allocation group number if this allocation 2275 * group is the new max. 2276 */ 2277 agno = blkno >> bmp->db_agl2size; 2278 if (agno > bmp->db_maxag) 2279 bmp->db_maxag = agno; 2280 2281 /* update the free count for the allocation group and map */ 2282 bmp->db_agfree[agno] -= nblocks; 2283 bmp->db_nfree -= nblocks; 2284 2285 BMAP_UNLOCK(bmp); 2286 } 2287 2288 2289 /* 2290 * NAME: dbFreeBits() 2291 * 2292 * FUNCTION: free a specified block range from a dmap. 2293 * 2294 * this routine updates the dmap to reflect the working 2295 * state allocation of the specified block range. it directly 2296 * updates the bits of the working map and causes the adjustment 2297 * of the binary buddy system described by the dmap's dmtree 2298 * leaves to reflect the bits freed. it also causes the dmap's 2299 * dmtree, as a whole, to reflect the deallocated range. 2300 * 2301 * PARAMETERS: 2302 * bmp - pointer to bmap descriptor 2303 * dp - pointer to dmap to free bits from. 2304 * blkno - starting block number of the bits to be freed. 2305 * nblocks - number of bits to be freed. 2306 * 2307 * RETURN VALUES: 0 for success 2308 * 2309 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit; 2310 */ 2311 static int dbFreeBits(struct bmap * bmp, struct dmap * dp, s64 blkno, 2312 int nblocks) 2313 { 2314 int dbitno, word, rembits, nb, nwords, wbitno, nw, agno; 2315 dmtree_t *tp = (dmtree_t *) & dp->tree; 2316 int rc = 0; 2317 int size; 2318 2319 /* determine the bit number and word within the dmap of the 2320 * starting block. 2321 */ 2322 dbitno = blkno & (BPERDMAP - 1); 2323 word = dbitno >> L2DBWORD; 2324 2325 /* block range better be within the dmap. 2326 */ 2327 assert(dbitno + nblocks <= BPERDMAP); 2328 2329 /* free the bits of the dmaps words corresponding to the block range. 2330 * not all bits of the first and last words may be contained within 2331 * the block range. if this is the case, we'll work against those 2332 * words (i.e. partial first and/or last) on an individual basis 2333 * (a single pass), freeing the bits of interest by hand and updating 2334 * the leaf corresponding to the dmap word. a single pass will be used 2335 * for all dmap words fully contained within the specified range. 2336 * within this pass, the bits of all fully contained dmap words will 2337 * be marked as free in a single shot and the leaves will be updated. a 2338 * single leaf may describe the free space of multiple dmap words, 2339 * so we may update only a subset of the actual leaves corresponding 2340 * to the dmap words of the block range. 2341 * 2342 * dbJoin() is used to update leaf values and will join the binary 2343 * buddy system of the leaves if the new leaf values indicate this 2344 * should be done. 2345 */ 2346 for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) { 2347 /* determine the bit number within the word and 2348 * the number of bits within the word. 2349 */ 2350 wbitno = dbitno & (DBWORD - 1); 2351 nb = min(rembits, DBWORD - wbitno); 2352 2353 /* check if only part of a word is to be freed. 2354 */ 2355 if (nb < DBWORD) { 2356 /* free (zero) the appropriate bits within this 2357 * dmap word. 2358 */ 2359 dp->wmap[word] &= 2360 cpu_to_le32(~(ONES << (DBWORD - nb) 2361 >> wbitno)); 2362 2363 /* update the leaf for this dmap word. 2364 */ 2365 rc = dbJoin(tp, word, 2366 dbMaxBud((u8 *) & dp->wmap[word])); 2367 if (rc) 2368 return rc; 2369 2370 word += 1; 2371 } else { 2372 /* one or more dmap words are fully contained 2373 * within the block range. determine how many 2374 * words and free (zero) the bits of these words. 2375 */ 2376 nwords = rembits >> L2DBWORD; 2377 memset(&dp->wmap[word], 0, nwords * 4); 2378 2379 /* determine how many bits. 2380 */ 2381 nb = nwords << L2DBWORD; 2382 2383 /* now update the appropriate leaves to reflect 2384 * the freed words. 2385 */ 2386 for (; nwords > 0; nwords -= nw) { 2387 /* determine what the leaf value should be 2388 * updated to as the minimum of the l2 number 2389 * of bits being freed and the l2 (max) number 2390 * of bits that can be described by this leaf. 2391 */ 2392 size = 2393 min(LITOL2BSZ 2394 (word, L2LPERDMAP, BUDMIN), 2395 NLSTOL2BSZ(nwords)); 2396 2397 /* update the leaf. 2398 */ 2399 rc = dbJoin(tp, word, size); 2400 if (rc) 2401 return rc; 2402 2403 /* get the number of dmap words handled. 2404 */ 2405 nw = BUDSIZE(size, BUDMIN); 2406 word += nw; 2407 } 2408 } 2409 } 2410 2411 /* update the free count for this dmap. 2412 */ 2413 le32_add_cpu(&dp->nfree, nblocks); 2414 2415 BMAP_LOCK(bmp); 2416 2417 /* update the free count for the allocation group and 2418 * map. 2419 */ 2420 agno = blkno >> bmp->db_agl2size; 2421 bmp->db_nfree += nblocks; 2422 bmp->db_agfree[agno] += nblocks; 2423 2424 /* check if this allocation group is not completely free and 2425 * if it is currently the maximum (rightmost) allocation group. 2426 * if so, establish the new maximum allocation group number by 2427 * searching left for the first allocation group with allocation. 2428 */ 2429 if ((bmp->db_agfree[agno] == bmp->db_agsize && agno == bmp->db_maxag) || 2430 (agno == bmp->db_numag - 1 && 2431 bmp->db_agfree[agno] == (bmp-> db_mapsize & (BPERDMAP - 1)))) { 2432 while (bmp->db_maxag > 0) { 2433 bmp->db_maxag -= 1; 2434 if (bmp->db_agfree[bmp->db_maxag] != 2435 bmp->db_agsize) 2436 break; 2437 } 2438 2439 /* re-establish the allocation group preference if the 2440 * current preference is right of the maximum allocation 2441 * group. 2442 */ 2443 if (bmp->db_agpref > bmp->db_maxag) 2444 bmp->db_agpref = bmp->db_maxag; 2445 } 2446 2447 BMAP_UNLOCK(bmp); 2448 2449 return 0; 2450 } 2451 2452 2453 /* 2454 * NAME: dbAdjCtl() 2455 * 2456 * FUNCTION: adjust a dmap control page at a specified level to reflect 2457 * the change in a lower level dmap or dmap control page's 2458 * maximum string of free blocks (i.e. a change in the root 2459 * of the lower level object's dmtree) due to the allocation 2460 * or deallocation of a range of blocks with a single dmap. 2461 * 2462 * on entry, this routine is provided with the new value of 2463 * the lower level dmap or dmap control page root and the 2464 * starting block number of the block range whose allocation 2465 * or deallocation resulted in the root change. this range 2466 * is respresented by a single leaf of the current dmapctl 2467 * and the leaf will be updated with this value, possibly 2468 * causing a binary buddy system within the leaves to be 2469 * split or joined. the update may also cause the dmapctl's 2470 * dmtree to be updated. 2471 * 2472 * if the adjustment of the dmap control page, itself, causes its 2473 * root to change, this change will be bubbled up to the next dmap 2474 * control level by a recursive call to this routine, specifying 2475 * the new root value and the next dmap control page level to 2476 * be adjusted. 2477 * PARAMETERS: 2478 * bmp - pointer to bmap descriptor 2479 * blkno - the first block of a block range within a dmap. it is 2480 * the allocation or deallocation of this block range that 2481 * requires the dmap control page to be adjusted. 2482 * newval - the new value of the lower level dmap or dmap control 2483 * page root. 2484 * alloc - 'true' if adjustment is due to an allocation. 2485 * level - current level of dmap control page (i.e. L0, L1, L2) to 2486 * be adjusted. 2487 * 2488 * RETURN VALUES: 2489 * 0 - success 2490 * -EIO - i/o error 2491 * 2492 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit; 2493 */ 2494 static int 2495 dbAdjCtl(struct bmap * bmp, s64 blkno, int newval, int alloc, int level) 2496 { 2497 struct metapage *mp; 2498 s8 oldroot; 2499 int oldval; 2500 s64 lblkno; 2501 struct dmapctl *dcp; 2502 int rc, leafno, ti; 2503 2504 /* get the buffer for the dmap control page for the specified 2505 * block number and control page level. 2506 */ 2507 lblkno = BLKTOCTL(blkno, bmp->db_l2nbperpage, level); 2508 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); 2509 if (mp == NULL) 2510 return -EIO; 2511 dcp = (struct dmapctl *) mp->data; 2512 2513 if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) { 2514 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmapctl page\n"); 2515 release_metapage(mp); 2516 return -EIO; 2517 } 2518 2519 /* determine the leaf number corresponding to the block and 2520 * the index within the dmap control tree. 2521 */ 2522 leafno = BLKTOCTLLEAF(blkno, dcp->budmin); 2523 ti = leafno + le32_to_cpu(dcp->leafidx); 2524 2525 /* save the current leaf value and the current root level (i.e. 2526 * maximum l2 free string described by this dmapctl). 2527 */ 2528 oldval = dcp->stree[ti]; 2529 oldroot = dcp->stree[ROOT]; 2530 2531 /* check if this is a control page update for an allocation. 2532 * if so, update the leaf to reflect the new leaf value using 2533 * dbSplit(); otherwise (deallocation), use dbJoin() to update 2534 * the leaf with the new value. in addition to updating the 2535 * leaf, dbSplit() will also split the binary buddy system of 2536 * the leaves, if required, and bubble new values within the 2537 * dmapctl tree, if required. similarly, dbJoin() will join 2538 * the binary buddy system of leaves and bubble new values up 2539 * the dmapctl tree as required by the new leaf value. 2540 */ 2541 if (alloc) { 2542 /* check if we are in the middle of a binary buddy 2543 * system. this happens when we are performing the 2544 * first allocation out of an allocation group that 2545 * is part (not the first part) of a larger binary 2546 * buddy system. if we are in the middle, back split 2547 * the system prior to calling dbSplit() which assumes 2548 * that it is at the front of a binary buddy system. 2549 */ 2550 if (oldval == NOFREE) { 2551 rc = dbBackSplit((dmtree_t *) dcp, leafno); 2552 if (rc) { 2553 release_metapage(mp); 2554 return rc; 2555 } 2556 oldval = dcp->stree[ti]; 2557 } 2558 dbSplit((dmtree_t *) dcp, leafno, dcp->budmin, newval); 2559 } else { 2560 rc = dbJoin((dmtree_t *) dcp, leafno, newval); 2561 if (rc) { 2562 release_metapage(mp); 2563 return rc; 2564 } 2565 } 2566 2567 /* check if the root of the current dmap control page changed due 2568 * to the update and if the current dmap control page is not at 2569 * the current top level (i.e. L0, L1, L2) of the map. if so (i.e. 2570 * root changed and this is not the top level), call this routine 2571 * again (recursion) for the next higher level of the mapping to 2572 * reflect the change in root for the current dmap control page. 2573 */ 2574 if (dcp->stree[ROOT] != oldroot) { 2575 /* are we below the top level of the map. if so, 2576 * bubble the root up to the next higher level. 2577 */ 2578 if (level < bmp->db_maxlevel) { 2579 /* bubble up the new root of this dmap control page to 2580 * the next level. 2581 */ 2582 if ((rc = 2583 dbAdjCtl(bmp, blkno, dcp->stree[ROOT], alloc, 2584 level + 1))) { 2585 /* something went wrong in bubbling up the new 2586 * root value, so backout the changes to the 2587 * current dmap control page. 2588 */ 2589 if (alloc) { 2590 dbJoin((dmtree_t *) dcp, leafno, 2591 oldval); 2592 } else { 2593 /* the dbJoin() above might have 2594 * caused a larger binary buddy system 2595 * to form and we may now be in the 2596 * middle of it. if this is the case, 2597 * back split the buddies. 2598 */ 2599 if (dcp->stree[ti] == NOFREE) 2600 dbBackSplit((dmtree_t *) 2601 dcp, leafno); 2602 dbSplit((dmtree_t *) dcp, leafno, 2603 dcp->budmin, oldval); 2604 } 2605 2606 /* release the buffer and return the error. 2607 */ 2608 release_metapage(mp); 2609 return (rc); 2610 } 2611 } else { 2612 /* we're at the top level of the map. update 2613 * the bmap control page to reflect the size 2614 * of the maximum free buddy system. 2615 */ 2616 assert(level == bmp->db_maxlevel); 2617 if (bmp->db_maxfreebud != oldroot) { 2618 jfs_error(bmp->db_ipbmap->i_sb, 2619 "the maximum free buddy is not the old root\n"); 2620 } 2621 bmp->db_maxfreebud = dcp->stree[ROOT]; 2622 } 2623 } 2624 2625 /* write the buffer. 2626 */ 2627 write_metapage(mp); 2628 2629 return (0); 2630 } 2631 2632 2633 /* 2634 * NAME: dbSplit() 2635 * 2636 * FUNCTION: update the leaf of a dmtree with a new value, splitting 2637 * the leaf from the binary buddy system of the dmtree's 2638 * leaves, as required. 2639 * 2640 * PARAMETERS: 2641 * tp - pointer to the tree containing the leaf. 2642 * leafno - the number of the leaf to be updated. 2643 * splitsz - the size the binary buddy system starting at the leaf 2644 * must be split to, specified as the log2 number of blocks. 2645 * newval - the new value for the leaf. 2646 * 2647 * RETURN VALUES: none 2648 * 2649 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit; 2650 */ 2651 static void dbSplit(dmtree_t * tp, int leafno, int splitsz, int newval) 2652 { 2653 int budsz; 2654 int cursz; 2655 s8 *leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx); 2656 2657 /* check if the leaf needs to be split. 2658 */ 2659 if (leaf[leafno] > tp->dmt_budmin) { 2660 /* the split occurs by cutting the buddy system in half 2661 * at the specified leaf until we reach the specified 2662 * size. pick up the starting split size (current size 2663 * - 1 in l2) and the corresponding buddy size. 2664 */ 2665 cursz = leaf[leafno] - 1; 2666 budsz = BUDSIZE(cursz, tp->dmt_budmin); 2667 2668 /* split until we reach the specified size. 2669 */ 2670 while (cursz >= splitsz) { 2671 /* update the buddy's leaf with its new value. 2672 */ 2673 dbAdjTree(tp, leafno ^ budsz, cursz); 2674 2675 /* on to the next size and buddy. 2676 */ 2677 cursz -= 1; 2678 budsz >>= 1; 2679 } 2680 } 2681 2682 /* adjust the dmap tree to reflect the specified leaf's new 2683 * value. 2684 */ 2685 dbAdjTree(tp, leafno, newval); 2686 } 2687 2688 2689 /* 2690 * NAME: dbBackSplit() 2691 * 2692 * FUNCTION: back split the binary buddy system of dmtree leaves 2693 * that hold a specified leaf until the specified leaf 2694 * starts its own binary buddy system. 2695 * 2696 * the allocators typically perform allocations at the start 2697 * of binary buddy systems and dbSplit() is used to accomplish 2698 * any required splits. in some cases, however, allocation 2699 * may occur in the middle of a binary system and requires a 2700 * back split, with the split proceeding out from the middle of 2701 * the system (less efficient) rather than the start of the 2702 * system (more efficient). the cases in which a back split 2703 * is required are rare and are limited to the first allocation 2704 * within an allocation group which is a part (not first part) 2705 * of a larger binary buddy system and a few exception cases 2706 * in which a previous join operation must be backed out. 2707 * 2708 * PARAMETERS: 2709 * tp - pointer to the tree containing the leaf. 2710 * leafno - the number of the leaf to be updated. 2711 * 2712 * RETURN VALUES: none 2713 * 2714 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit; 2715 */ 2716 static int dbBackSplit(dmtree_t * tp, int leafno) 2717 { 2718 int budsz, bud, w, bsz, size; 2719 int cursz; 2720 s8 *leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx); 2721 2722 /* leaf should be part (not first part) of a binary 2723 * buddy system. 2724 */ 2725 assert(leaf[leafno] == NOFREE); 2726 2727 /* the back split is accomplished by iteratively finding the leaf 2728 * that starts the buddy system that contains the specified leaf and 2729 * splitting that system in two. this iteration continues until 2730 * the specified leaf becomes the start of a buddy system. 2731 * 2732 * determine maximum possible l2 size for the specified leaf. 2733 */ 2734 size = 2735 LITOL2BSZ(leafno, le32_to_cpu(tp->dmt_l2nleafs), 2736 tp->dmt_budmin); 2737 2738 /* determine the number of leaves covered by this size. this 2739 * is the buddy size that we will start with as we search for 2740 * the buddy system that contains the specified leaf. 2741 */ 2742 budsz = BUDSIZE(size, tp->dmt_budmin); 2743 2744 /* back split. 2745 */ 2746 while (leaf[leafno] == NOFREE) { 2747 /* find the leftmost buddy leaf. 2748 */ 2749 for (w = leafno, bsz = budsz;; bsz <<= 1, 2750 w = (w < bud) ? w : bud) { 2751 if (bsz >= le32_to_cpu(tp->dmt_nleafs)) { 2752 jfs_err("JFS: block map error in dbBackSplit"); 2753 return -EIO; 2754 } 2755 2756 /* determine the buddy. 2757 */ 2758 bud = w ^ bsz; 2759 2760 /* check if this buddy is the start of the system. 2761 */ 2762 if (leaf[bud] != NOFREE) { 2763 /* split the leaf at the start of the 2764 * system in two. 2765 */ 2766 cursz = leaf[bud] - 1; 2767 dbSplit(tp, bud, cursz, cursz); 2768 break; 2769 } 2770 } 2771 } 2772 2773 if (leaf[leafno] != size) { 2774 jfs_err("JFS: wrong leaf value in dbBackSplit"); 2775 return -EIO; 2776 } 2777 return 0; 2778 } 2779 2780 2781 /* 2782 * NAME: dbJoin() 2783 * 2784 * FUNCTION: update the leaf of a dmtree with a new value, joining 2785 * the leaf with other leaves of the dmtree into a multi-leaf 2786 * binary buddy system, as required. 2787 * 2788 * PARAMETERS: 2789 * tp - pointer to the tree containing the leaf. 2790 * leafno - the number of the leaf to be updated. 2791 * newval - the new value for the leaf. 2792 * 2793 * RETURN VALUES: none 2794 */ 2795 static int dbJoin(dmtree_t * tp, int leafno, int newval) 2796 { 2797 int budsz, buddy; 2798 s8 *leaf; 2799 2800 /* can the new leaf value require a join with other leaves ? 2801 */ 2802 if (newval >= tp->dmt_budmin) { 2803 /* pickup a pointer to the leaves of the tree. 2804 */ 2805 leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx); 2806 2807 /* try to join the specified leaf into a large binary 2808 * buddy system. the join proceeds by attempting to join 2809 * the specified leafno with its buddy (leaf) at new value. 2810 * if the join occurs, we attempt to join the left leaf 2811 * of the joined buddies with its buddy at new value + 1. 2812 * we continue to join until we find a buddy that cannot be 2813 * joined (does not have a value equal to the size of the 2814 * last join) or until all leaves have been joined into a 2815 * single system. 2816 * 2817 * get the buddy size (number of words covered) of 2818 * the new value. 2819 */ 2820 budsz = BUDSIZE(newval, tp->dmt_budmin); 2821 2822 /* try to join. 2823 */ 2824 while (budsz < le32_to_cpu(tp->dmt_nleafs)) { 2825 /* get the buddy leaf. 2826 */ 2827 buddy = leafno ^ budsz; 2828 2829 /* if the leaf's new value is greater than its 2830 * buddy's value, we join no more. 2831 */ 2832 if (newval > leaf[buddy]) 2833 break; 2834 2835 /* It shouldn't be less */ 2836 if (newval < leaf[buddy]) 2837 return -EIO; 2838 2839 /* check which (leafno or buddy) is the left buddy. 2840 * the left buddy gets to claim the blocks resulting 2841 * from the join while the right gets to claim none. 2842 * the left buddy is also eligible to participate in 2843 * a join at the next higher level while the right 2844 * is not. 2845 * 2846 */ 2847 if (leafno < buddy) { 2848 /* leafno is the left buddy. 2849 */ 2850 dbAdjTree(tp, buddy, NOFREE); 2851 } else { 2852 /* buddy is the left buddy and becomes 2853 * leafno. 2854 */ 2855 dbAdjTree(tp, leafno, NOFREE); 2856 leafno = buddy; 2857 } 2858 2859 /* on to try the next join. 2860 */ 2861 newval += 1; 2862 budsz <<= 1; 2863 } 2864 } 2865 2866 /* update the leaf value. 2867 */ 2868 dbAdjTree(tp, leafno, newval); 2869 2870 return 0; 2871 } 2872 2873 2874 /* 2875 * NAME: dbAdjTree() 2876 * 2877 * FUNCTION: update a leaf of a dmtree with a new value, adjusting 2878 * the dmtree, as required, to reflect the new leaf value. 2879 * the combination of any buddies must already be done before 2880 * this is called. 2881 * 2882 * PARAMETERS: 2883 * tp - pointer to the tree to be adjusted. 2884 * leafno - the number of the leaf to be updated. 2885 * newval - the new value for the leaf. 2886 * 2887 * RETURN VALUES: none 2888 */ 2889 static void dbAdjTree(dmtree_t * tp, int leafno, int newval) 2890 { 2891 int lp, pp, k; 2892 int max; 2893 2894 /* pick up the index of the leaf for this leafno. 2895 */ 2896 lp = leafno + le32_to_cpu(tp->dmt_leafidx); 2897 2898 /* is the current value the same as the old value ? if so, 2899 * there is nothing to do. 2900 */ 2901 if (tp->dmt_stree[lp] == newval) 2902 return; 2903 2904 /* set the new value. 2905 */ 2906 tp->dmt_stree[lp] = newval; 2907 2908 /* bubble the new value up the tree as required. 2909 */ 2910 for (k = 0; k < le32_to_cpu(tp->dmt_height); k++) { 2911 /* get the index of the first leaf of the 4 leaf 2912 * group containing the specified leaf (leafno). 2913 */ 2914 lp = ((lp - 1) & ~0x03) + 1; 2915 2916 /* get the index of the parent of this 4 leaf group. 2917 */ 2918 pp = (lp - 1) >> 2; 2919 2920 /* determine the maximum of the 4 leaves. 2921 */ 2922 max = TREEMAX(&tp->dmt_stree[lp]); 2923 2924 /* if the maximum of the 4 is the same as the 2925 * parent's value, we're done. 2926 */ 2927 if (tp->dmt_stree[pp] == max) 2928 break; 2929 2930 /* parent gets new value. 2931 */ 2932 tp->dmt_stree[pp] = max; 2933 2934 /* parent becomes leaf for next go-round. 2935 */ 2936 lp = pp; 2937 } 2938 } 2939 2940 2941 /* 2942 * NAME: dbFindLeaf() 2943 * 2944 * FUNCTION: search a dmtree_t for sufficient free blocks, returning 2945 * the index of a leaf describing the free blocks if 2946 * sufficient free blocks are found. 2947 * 2948 * the search starts at the top of the dmtree_t tree and 2949 * proceeds down the tree to the leftmost leaf with sufficient 2950 * free space. 2951 * 2952 * PARAMETERS: 2953 * tp - pointer to the tree to be searched. 2954 * l2nb - log2 number of free blocks to search for. 2955 * leafidx - return pointer to be set to the index of the leaf 2956 * describing at least l2nb free blocks if sufficient 2957 * free blocks are found. 2958 * 2959 * RETURN VALUES: 2960 * 0 - success 2961 * -ENOSPC - insufficient free blocks. 2962 */ 2963 static int dbFindLeaf(dmtree_t * tp, int l2nb, int *leafidx) 2964 { 2965 int ti, n = 0, k, x = 0; 2966 2967 /* first check the root of the tree to see if there is 2968 * sufficient free space. 2969 */ 2970 if (l2nb > tp->dmt_stree[ROOT]) 2971 return -ENOSPC; 2972 2973 /* sufficient free space available. now search down the tree 2974 * starting at the next level for the leftmost leaf that 2975 * describes sufficient free space. 2976 */ 2977 for (k = le32_to_cpu(tp->dmt_height), ti = 1; 2978 k > 0; k--, ti = ((ti + n) << 2) + 1) { 2979 /* search the four nodes at this level, starting from 2980 * the left. 2981 */ 2982 for (x = ti, n = 0; n < 4; n++) { 2983 /* sufficient free space found. move to the next 2984 * level (or quit if this is the last level). 2985 */ 2986 if (l2nb <= tp->dmt_stree[x + n]) 2987 break; 2988 } 2989 2990 /* better have found something since the higher 2991 * levels of the tree said it was here. 2992 */ 2993 assert(n < 4); 2994 } 2995 2996 /* set the return to the leftmost leaf describing sufficient 2997 * free space. 2998 */ 2999 *leafidx = x + n - le32_to_cpu(tp->dmt_leafidx); 3000 3001 return (0); 3002 } 3003 3004 3005 /* 3006 * NAME: dbFindBits() 3007 * 3008 * FUNCTION: find a specified number of binary buddy free bits within a 3009 * dmap bitmap word value. 3010 * 3011 * this routine searches the bitmap value for (1 << l2nb) free 3012 * bits at (1 << l2nb) alignments within the value. 3013 * 3014 * PARAMETERS: 3015 * word - dmap bitmap word value. 3016 * l2nb - number of free bits specified as a log2 number. 3017 * 3018 * RETURN VALUES: 3019 * starting bit number of free bits. 3020 */ 3021 static int dbFindBits(u32 word, int l2nb) 3022 { 3023 int bitno, nb; 3024 u32 mask; 3025 3026 /* get the number of bits. 3027 */ 3028 nb = 1 << l2nb; 3029 assert(nb <= DBWORD); 3030 3031 /* complement the word so we can use a mask (i.e. 0s represent 3032 * free bits) and compute the mask. 3033 */ 3034 word = ~word; 3035 mask = ONES << (DBWORD - nb); 3036 3037 /* scan the word for nb free bits at nb alignments. 3038 */ 3039 for (bitno = 0; mask != 0; bitno += nb, mask >>= nb) { 3040 if ((mask & word) == mask) 3041 break; 3042 } 3043 3044 ASSERT(bitno < 32); 3045 3046 /* return the bit number. 3047 */ 3048 return (bitno); 3049 } 3050 3051 3052 /* 3053 * NAME: dbMaxBud(u8 *cp) 3054 * 3055 * FUNCTION: determine the largest binary buddy string of free 3056 * bits within 32-bits of the map. 3057 * 3058 * PARAMETERS: 3059 * cp - pointer to the 32-bit value. 3060 * 3061 * RETURN VALUES: 3062 * largest binary buddy of free bits within a dmap word. 3063 */ 3064 static int dbMaxBud(u8 * cp) 3065 { 3066 signed char tmp1, tmp2; 3067 3068 /* check if the wmap word is all free. if so, the 3069 * free buddy size is BUDMIN. 3070 */ 3071 if (*((uint *) cp) == 0) 3072 return (BUDMIN); 3073 3074 /* check if the wmap word is half free. if so, the 3075 * free buddy size is BUDMIN-1. 3076 */ 3077 if (*((u16 *) cp) == 0 || *((u16 *) cp + 1) == 0) 3078 return (BUDMIN - 1); 3079 3080 /* not all free or half free. determine the free buddy 3081 * size thru table lookup using quarters of the wmap word. 3082 */ 3083 tmp1 = max(budtab[cp[2]], budtab[cp[3]]); 3084 tmp2 = max(budtab[cp[0]], budtab[cp[1]]); 3085 return (max(tmp1, tmp2)); 3086 } 3087 3088 3089 /* 3090 * NAME: cnttz(uint word) 3091 * 3092 * FUNCTION: determine the number of trailing zeros within a 32-bit 3093 * value. 3094 * 3095 * PARAMETERS: 3096 * value - 32-bit value to be examined. 3097 * 3098 * RETURN VALUES: 3099 * count of trailing zeros 3100 */ 3101 static int cnttz(u32 word) 3102 { 3103 int n; 3104 3105 for (n = 0; n < 32; n++, word >>= 1) { 3106 if (word & 0x01) 3107 break; 3108 } 3109 3110 return (n); 3111 } 3112 3113 3114 /* 3115 * NAME: cntlz(u32 value) 3116 * 3117 * FUNCTION: determine the number of leading zeros within a 32-bit 3118 * value. 3119 * 3120 * PARAMETERS: 3121 * value - 32-bit value to be examined. 3122 * 3123 * RETURN VALUES: 3124 * count of leading zeros 3125 */ 3126 static int cntlz(u32 value) 3127 { 3128 int n; 3129 3130 for (n = 0; n < 32; n++, value <<= 1) { 3131 if (value & HIGHORDER) 3132 break; 3133 } 3134 return (n); 3135 } 3136 3137 3138 /* 3139 * NAME: blkstol2(s64 nb) 3140 * 3141 * FUNCTION: convert a block count to its log2 value. if the block 3142 * count is not a l2 multiple, it is rounded up to the next 3143 * larger l2 multiple. 3144 * 3145 * PARAMETERS: 3146 * nb - number of blocks 3147 * 3148 * RETURN VALUES: 3149 * log2 number of blocks 3150 */ 3151 static int blkstol2(s64 nb) 3152 { 3153 int l2nb; 3154 s64 mask; /* meant to be signed */ 3155 3156 mask = (s64) 1 << (64 - 1); 3157 3158 /* count the leading bits. 3159 */ 3160 for (l2nb = 0; l2nb < 64; l2nb++, mask >>= 1) { 3161 /* leading bit found. 3162 */ 3163 if (nb & mask) { 3164 /* determine the l2 value. 3165 */ 3166 l2nb = (64 - 1) - l2nb; 3167 3168 /* check if we need to round up. 3169 */ 3170 if (~mask & nb) 3171 l2nb++; 3172 3173 return (l2nb); 3174 } 3175 } 3176 assert(0); 3177 return 0; /* fix compiler warning */ 3178 } 3179 3180 3181 /* 3182 * NAME: dbAllocBottomUp() 3183 * 3184 * FUNCTION: alloc the specified block range from the working block 3185 * allocation map. 3186 * 3187 * the blocks will be alloc from the working map one dmap 3188 * at a time. 3189 * 3190 * PARAMETERS: 3191 * ip - pointer to in-core inode; 3192 * blkno - starting block number to be freed. 3193 * nblocks - number of blocks to be freed. 3194 * 3195 * RETURN VALUES: 3196 * 0 - success 3197 * -EIO - i/o error 3198 */ 3199 int dbAllocBottomUp(struct inode *ip, s64 blkno, s64 nblocks) 3200 { 3201 struct metapage *mp; 3202 struct dmap *dp; 3203 int nb, rc; 3204 s64 lblkno, rem; 3205 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap; 3206 struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap; 3207 3208 IREAD_LOCK(ipbmap, RDWRLOCK_DMAP); 3209 3210 /* block to be allocated better be within the mapsize. */ 3211 ASSERT(nblocks <= bmp->db_mapsize - blkno); 3212 3213 /* 3214 * allocate the blocks a dmap at a time. 3215 */ 3216 mp = NULL; 3217 for (rem = nblocks; rem > 0; rem -= nb, blkno += nb) { 3218 /* release previous dmap if any */ 3219 if (mp) { 3220 write_metapage(mp); 3221 } 3222 3223 /* get the buffer for the current dmap. */ 3224 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); 3225 mp = read_metapage(ipbmap, lblkno, PSIZE, 0); 3226 if (mp == NULL) { 3227 IREAD_UNLOCK(ipbmap); 3228 return -EIO; 3229 } 3230 dp = (struct dmap *) mp->data; 3231 3232 /* determine the number of blocks to be allocated from 3233 * this dmap. 3234 */ 3235 nb = min(rem, BPERDMAP - (blkno & (BPERDMAP - 1))); 3236 3237 /* allocate the blocks. */ 3238 if ((rc = dbAllocDmapBU(bmp, dp, blkno, nb))) { 3239 release_metapage(mp); 3240 IREAD_UNLOCK(ipbmap); 3241 return (rc); 3242 } 3243 } 3244 3245 /* write the last buffer. */ 3246 write_metapage(mp); 3247 3248 IREAD_UNLOCK(ipbmap); 3249 3250 return (0); 3251 } 3252 3253 3254 static int dbAllocDmapBU(struct bmap * bmp, struct dmap * dp, s64 blkno, 3255 int nblocks) 3256 { 3257 int rc; 3258 int dbitno, word, rembits, nb, nwords, wbitno, agno; 3259 s8 oldroot; 3260 struct dmaptree *tp = (struct dmaptree *) & dp->tree; 3261 3262 /* save the current value of the root (i.e. maximum free string) 3263 * of the dmap tree. 3264 */ 3265 oldroot = tp->stree[ROOT]; 3266 3267 /* determine the bit number and word within the dmap of the 3268 * starting block. 3269 */ 3270 dbitno = blkno & (BPERDMAP - 1); 3271 word = dbitno >> L2DBWORD; 3272 3273 /* block range better be within the dmap */ 3274 assert(dbitno + nblocks <= BPERDMAP); 3275 3276 /* allocate the bits of the dmap's words corresponding to the block 3277 * range. not all bits of the first and last words may be contained 3278 * within the block range. if this is the case, we'll work against 3279 * those words (i.e. partial first and/or last) on an individual basis 3280 * (a single pass), allocating the bits of interest by hand and 3281 * updating the leaf corresponding to the dmap word. a single pass 3282 * will be used for all dmap words fully contained within the 3283 * specified range. within this pass, the bits of all fully contained 3284 * dmap words will be marked as free in a single shot and the leaves 3285 * will be updated. a single leaf may describe the free space of 3286 * multiple dmap words, so we may update only a subset of the actual 3287 * leaves corresponding to the dmap words of the block range. 3288 */ 3289 for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) { 3290 /* determine the bit number within the word and 3291 * the number of bits within the word. 3292 */ 3293 wbitno = dbitno & (DBWORD - 1); 3294 nb = min(rembits, DBWORD - wbitno); 3295 3296 /* check if only part of a word is to be allocated. 3297 */ 3298 if (nb < DBWORD) { 3299 /* allocate (set to 1) the appropriate bits within 3300 * this dmap word. 3301 */ 3302 dp->wmap[word] |= cpu_to_le32(ONES << (DBWORD - nb) 3303 >> wbitno); 3304 3305 word++; 3306 } else { 3307 /* one or more dmap words are fully contained 3308 * within the block range. determine how many 3309 * words and allocate (set to 1) the bits of these 3310 * words. 3311 */ 3312 nwords = rembits >> L2DBWORD; 3313 memset(&dp->wmap[word], (int) ONES, nwords * 4); 3314 3315 /* determine how many bits */ 3316 nb = nwords << L2DBWORD; 3317 word += nwords; 3318 } 3319 } 3320 3321 /* update the free count for this dmap */ 3322 le32_add_cpu(&dp->nfree, -nblocks); 3323 3324 /* reconstruct summary tree */ 3325 dbInitDmapTree(dp); 3326 3327 BMAP_LOCK(bmp); 3328 3329 /* if this allocation group is completely free, 3330 * update the highest active allocation group number 3331 * if this allocation group is the new max. 3332 */ 3333 agno = blkno >> bmp->db_agl2size; 3334 if (agno > bmp->db_maxag) 3335 bmp->db_maxag = agno; 3336 3337 /* update the free count for the allocation group and map */ 3338 bmp->db_agfree[agno] -= nblocks; 3339 bmp->db_nfree -= nblocks; 3340 3341 BMAP_UNLOCK(bmp); 3342 3343 /* if the root has not changed, done. */ 3344 if (tp->stree[ROOT] == oldroot) 3345 return (0); 3346 3347 /* root changed. bubble the change up to the dmap control pages. 3348 * if the adjustment of the upper level control pages fails, 3349 * backout the bit allocation (thus making everything consistent). 3350 */ 3351 if ((rc = dbAdjCtl(bmp, blkno, tp->stree[ROOT], 1, 0))) 3352 dbFreeBits(bmp, dp, blkno, nblocks); 3353 3354 return (rc); 3355 } 3356 3357 3358 /* 3359 * NAME: dbExtendFS() 3360 * 3361 * FUNCTION: extend bmap from blkno for nblocks; 3362 * dbExtendFS() updates bmap ready for dbAllocBottomUp(); 3363 * 3364 * L2 3365 * | 3366 * L1---------------------------------L1 3367 * | | 3368 * L0---------L0---------L0 L0---------L0---------L0 3369 * | | | | | | 3370 * d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,.,dm; 3371 * L2L1L0d0,...,dnL0d0,...,dnL0d0,...,dnL1L0d0,...,dnL0d0,...,dnL0d0,..dm 3372 * 3373 * <---old---><----------------------------extend-----------------------> 3374 */ 3375 int dbExtendFS(struct inode *ipbmap, s64 blkno, s64 nblocks) 3376 { 3377 struct jfs_sb_info *sbi = JFS_SBI(ipbmap->i_sb); 3378 int nbperpage = sbi->nbperpage; 3379 int i, i0 = true, j, j0 = true, k, n; 3380 s64 newsize; 3381 s64 p; 3382 struct metapage *mp, *l2mp, *l1mp = NULL, *l0mp = NULL; 3383 struct dmapctl *l2dcp, *l1dcp, *l0dcp; 3384 struct dmap *dp; 3385 s8 *l0leaf, *l1leaf, *l2leaf; 3386 struct bmap *bmp = sbi->bmap; 3387 int agno, l2agsize, oldl2agsize; 3388 s64 ag_rem; 3389 3390 newsize = blkno + nblocks; 3391 3392 jfs_info("dbExtendFS: blkno:%Ld nblocks:%Ld newsize:%Ld", 3393 (long long) blkno, (long long) nblocks, (long long) newsize); 3394 3395 /* 3396 * initialize bmap control page. 3397 * 3398 * all the data in bmap control page should exclude 3399 * the mkfs hidden dmap page. 3400 */ 3401 3402 /* update mapsize */ 3403 bmp->db_mapsize = newsize; 3404 bmp->db_maxlevel = BMAPSZTOLEV(bmp->db_mapsize); 3405 3406 /* compute new AG size */ 3407 l2agsize = dbGetL2AGSize(newsize); 3408 oldl2agsize = bmp->db_agl2size; 3409 3410 bmp->db_agl2size = l2agsize; 3411 bmp->db_agsize = 1 << l2agsize; 3412 3413 /* compute new number of AG */ 3414 agno = bmp->db_numag; 3415 bmp->db_numag = newsize >> l2agsize; 3416 bmp->db_numag += ((u32) newsize % (u32) bmp->db_agsize) ? 1 : 0; 3417 3418 /* 3419 * reconfigure db_agfree[] 3420 * from old AG configuration to new AG configuration; 3421 * 3422 * coalesce contiguous k (newAGSize/oldAGSize) AGs; 3423 * i.e., (AGi, ..., AGj) where i = k*n and j = k*(n+1) - 1 to AGn; 3424 * note: new AG size = old AG size * (2**x). 3425 */ 3426 if (l2agsize == oldl2agsize) 3427 goto extend; 3428 k = 1 << (l2agsize - oldl2agsize); 3429 ag_rem = bmp->db_agfree[0]; /* save agfree[0] */ 3430 for (i = 0, n = 0; i < agno; n++) { 3431 bmp->db_agfree[n] = 0; /* init collection point */ 3432 3433 /* coalesce contiguous k AGs; */ 3434 for (j = 0; j < k && i < agno; j++, i++) { 3435 /* merge AGi to AGn */ 3436 bmp->db_agfree[n] += bmp->db_agfree[i]; 3437 } 3438 } 3439 bmp->db_agfree[0] += ag_rem; /* restore agfree[0] */ 3440 3441 for (; n < MAXAG; n++) 3442 bmp->db_agfree[n] = 0; 3443 3444 /* 3445 * update highest active ag number 3446 */ 3447 3448 bmp->db_maxag = bmp->db_maxag / k; 3449 3450 /* 3451 * extend bmap 3452 * 3453 * update bit maps and corresponding level control pages; 3454 * global control page db_nfree, db_agfree[agno], db_maxfreebud; 3455 */ 3456 extend: 3457 /* get L2 page */ 3458 p = BMAPBLKNO + nbperpage; /* L2 page */ 3459 l2mp = read_metapage(ipbmap, p, PSIZE, 0); 3460 if (!l2mp) { 3461 jfs_error(ipbmap->i_sb, "L2 page could not be read\n"); 3462 return -EIO; 3463 } 3464 l2dcp = (struct dmapctl *) l2mp->data; 3465 3466 /* compute start L1 */ 3467 k = blkno >> L2MAXL1SIZE; 3468 l2leaf = l2dcp->stree + CTLLEAFIND + k; 3469 p = BLKTOL1(blkno, sbi->l2nbperpage); /* L1 page */ 3470 3471 /* 3472 * extend each L1 in L2 3473 */ 3474 for (; k < LPERCTL; k++, p += nbperpage) { 3475 /* get L1 page */ 3476 if (j0) { 3477 /* read in L1 page: (blkno & (MAXL1SIZE - 1)) */ 3478 l1mp = read_metapage(ipbmap, p, PSIZE, 0); 3479 if (l1mp == NULL) 3480 goto errout; 3481 l1dcp = (struct dmapctl *) l1mp->data; 3482 3483 /* compute start L0 */ 3484 j = (blkno & (MAXL1SIZE - 1)) >> L2MAXL0SIZE; 3485 l1leaf = l1dcp->stree + CTLLEAFIND + j; 3486 p = BLKTOL0(blkno, sbi->l2nbperpage); 3487 j0 = false; 3488 } else { 3489 /* assign/init L1 page */ 3490 l1mp = get_metapage(ipbmap, p, PSIZE, 0); 3491 if (l1mp == NULL) 3492 goto errout; 3493 3494 l1dcp = (struct dmapctl *) l1mp->data; 3495 3496 /* compute start L0 */ 3497 j = 0; 3498 l1leaf = l1dcp->stree + CTLLEAFIND; 3499 p += nbperpage; /* 1st L0 of L1.k */ 3500 } 3501 3502 /* 3503 * extend each L0 in L1 3504 */ 3505 for (; j < LPERCTL; j++) { 3506 /* get L0 page */ 3507 if (i0) { 3508 /* read in L0 page: (blkno & (MAXL0SIZE - 1)) */ 3509 3510 l0mp = read_metapage(ipbmap, p, PSIZE, 0); 3511 if (l0mp == NULL) 3512 goto errout; 3513 l0dcp = (struct dmapctl *) l0mp->data; 3514 3515 /* compute start dmap */ 3516 i = (blkno & (MAXL0SIZE - 1)) >> 3517 L2BPERDMAP; 3518 l0leaf = l0dcp->stree + CTLLEAFIND + i; 3519 p = BLKTODMAP(blkno, 3520 sbi->l2nbperpage); 3521 i0 = false; 3522 } else { 3523 /* assign/init L0 page */ 3524 l0mp = get_metapage(ipbmap, p, PSIZE, 0); 3525 if (l0mp == NULL) 3526 goto errout; 3527 3528 l0dcp = (struct dmapctl *) l0mp->data; 3529 3530 /* compute start dmap */ 3531 i = 0; 3532 l0leaf = l0dcp->stree + CTLLEAFIND; 3533 p += nbperpage; /* 1st dmap of L0.j */ 3534 } 3535 3536 /* 3537 * extend each dmap in L0 3538 */ 3539 for (; i < LPERCTL; i++) { 3540 /* 3541 * reconstruct the dmap page, and 3542 * initialize corresponding parent L0 leaf 3543 */ 3544 if ((n = blkno & (BPERDMAP - 1))) { 3545 /* read in dmap page: */ 3546 mp = read_metapage(ipbmap, p, 3547 PSIZE, 0); 3548 if (mp == NULL) 3549 goto errout; 3550 n = min(nblocks, (s64)BPERDMAP - n); 3551 } else { 3552 /* assign/init dmap page */ 3553 mp = read_metapage(ipbmap, p, 3554 PSIZE, 0); 3555 if (mp == NULL) 3556 goto errout; 3557 3558 n = min_t(s64, nblocks, BPERDMAP); 3559 } 3560 3561 dp = (struct dmap *) mp->data; 3562 *l0leaf = dbInitDmap(dp, blkno, n); 3563 3564 bmp->db_nfree += n; 3565 agno = le64_to_cpu(dp->start) >> l2agsize; 3566 bmp->db_agfree[agno] += n; 3567 3568 write_metapage(mp); 3569 3570 l0leaf++; 3571 p += nbperpage; 3572 3573 blkno += n; 3574 nblocks -= n; 3575 if (nblocks == 0) 3576 break; 3577 } /* for each dmap in a L0 */ 3578 3579 /* 3580 * build current L0 page from its leaves, and 3581 * initialize corresponding parent L1 leaf 3582 */ 3583 *l1leaf = dbInitDmapCtl(l0dcp, 0, ++i); 3584 write_metapage(l0mp); 3585 l0mp = NULL; 3586 3587 if (nblocks) 3588 l1leaf++; /* continue for next L0 */ 3589 else { 3590 /* more than 1 L0 ? */ 3591 if (j > 0) 3592 break; /* build L1 page */ 3593 else { 3594 /* summarize in global bmap page */ 3595 bmp->db_maxfreebud = *l1leaf; 3596 release_metapage(l1mp); 3597 release_metapage(l2mp); 3598 goto finalize; 3599 } 3600 } 3601 } /* for each L0 in a L1 */ 3602 3603 /* 3604 * build current L1 page from its leaves, and 3605 * initialize corresponding parent L2 leaf 3606 */ 3607 *l2leaf = dbInitDmapCtl(l1dcp, 1, ++j); 3608 write_metapage(l1mp); 3609 l1mp = NULL; 3610 3611 if (nblocks) 3612 l2leaf++; /* continue for next L1 */ 3613 else { 3614 /* more than 1 L1 ? */ 3615 if (k > 0) 3616 break; /* build L2 page */ 3617 else { 3618 /* summarize in global bmap page */ 3619 bmp->db_maxfreebud = *l2leaf; 3620 release_metapage(l2mp); 3621 goto finalize; 3622 } 3623 } 3624 } /* for each L1 in a L2 */ 3625 3626 jfs_error(ipbmap->i_sb, "function has not returned as expected\n"); 3627 errout: 3628 if (l0mp) 3629 release_metapage(l0mp); 3630 if (l1mp) 3631 release_metapage(l1mp); 3632 release_metapage(l2mp); 3633 return -EIO; 3634 3635 /* 3636 * finalize bmap control page 3637 */ 3638 finalize: 3639 3640 return 0; 3641 } 3642 3643 3644 /* 3645 * dbFinalizeBmap() 3646 */ 3647 void dbFinalizeBmap(struct inode *ipbmap) 3648 { 3649 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap; 3650 int actags, inactags, l2nl; 3651 s64 ag_rem, actfree, inactfree, avgfree; 3652 int i, n; 3653 3654 /* 3655 * finalize bmap control page 3656 */ 3657 //finalize: 3658 /* 3659 * compute db_agpref: preferred ag to allocate from 3660 * (the leftmost ag with average free space in it); 3661 */ 3662 //agpref: 3663 /* get the number of active ags and inacitve ags */ 3664 actags = bmp->db_maxag + 1; 3665 inactags = bmp->db_numag - actags; 3666 ag_rem = bmp->db_mapsize & (bmp->db_agsize - 1); /* ??? */ 3667 3668 /* determine how many blocks are in the inactive allocation 3669 * groups. in doing this, we must account for the fact that 3670 * the rightmost group might be a partial group (i.e. file 3671 * system size is not a multiple of the group size). 3672 */ 3673 inactfree = (inactags && ag_rem) ? 3674 ((inactags - 1) << bmp->db_agl2size) + ag_rem 3675 : inactags << bmp->db_agl2size; 3676 3677 /* determine how many free blocks are in the active 3678 * allocation groups plus the average number of free blocks 3679 * within the active ags. 3680 */ 3681 actfree = bmp->db_nfree - inactfree; 3682 avgfree = (u32) actfree / (u32) actags; 3683 3684 /* if the preferred allocation group has not average free space. 3685 * re-establish the preferred group as the leftmost 3686 * group with average free space. 3687 */ 3688 if (bmp->db_agfree[bmp->db_agpref] < avgfree) { 3689 for (bmp->db_agpref = 0; bmp->db_agpref < actags; 3690 bmp->db_agpref++) { 3691 if (bmp->db_agfree[bmp->db_agpref] >= avgfree) 3692 break; 3693 } 3694 if (bmp->db_agpref >= bmp->db_numag) { 3695 jfs_error(ipbmap->i_sb, 3696 "cannot find ag with average freespace\n"); 3697 } 3698 } 3699 3700 /* 3701 * compute db_aglevel, db_agheight, db_width, db_agstart: 3702 * an ag is covered in aglevel dmapctl summary tree, 3703 * at agheight level height (from leaf) with agwidth number of nodes 3704 * each, which starts at agstart index node of the smmary tree node 3705 * array; 3706 */ 3707 bmp->db_aglevel = BMAPSZTOLEV(bmp->db_agsize); 3708 l2nl = 3709 bmp->db_agl2size - (L2BPERDMAP + bmp->db_aglevel * L2LPERCTL); 3710 bmp->db_agheight = l2nl >> 1; 3711 bmp->db_agwidth = 1 << (l2nl - (bmp->db_agheight << 1)); 3712 for (i = 5 - bmp->db_agheight, bmp->db_agstart = 0, n = 1; i > 0; 3713 i--) { 3714 bmp->db_agstart += n; 3715 n <<= 2; 3716 } 3717 3718 } 3719 3720 3721 /* 3722 * NAME: dbInitDmap()/ujfs_idmap_page() 3723 * 3724 * FUNCTION: initialize working/persistent bitmap of the dmap page 3725 * for the specified number of blocks: 3726 * 3727 * at entry, the bitmaps had been initialized as free (ZEROS); 3728 * The number of blocks will only account for the actually 3729 * existing blocks. Blocks which don't actually exist in 3730 * the aggregate will be marked as allocated (ONES); 3731 * 3732 * PARAMETERS: 3733 * dp - pointer to page of map 3734 * nblocks - number of blocks this page 3735 * 3736 * RETURNS: NONE 3737 */ 3738 static int dbInitDmap(struct dmap * dp, s64 Blkno, int nblocks) 3739 { 3740 int blkno, w, b, r, nw, nb, i; 3741 3742 /* starting block number within the dmap */ 3743 blkno = Blkno & (BPERDMAP - 1); 3744 3745 if (blkno == 0) { 3746 dp->nblocks = dp->nfree = cpu_to_le32(nblocks); 3747 dp->start = cpu_to_le64(Blkno); 3748 3749 if (nblocks == BPERDMAP) { 3750 memset(&dp->wmap[0], 0, LPERDMAP * 4); 3751 memset(&dp->pmap[0], 0, LPERDMAP * 4); 3752 goto initTree; 3753 } 3754 } else { 3755 le32_add_cpu(&dp->nblocks, nblocks); 3756 le32_add_cpu(&dp->nfree, nblocks); 3757 } 3758 3759 /* word number containing start block number */ 3760 w = blkno >> L2DBWORD; 3761 3762 /* 3763 * free the bits corresponding to the block range (ZEROS): 3764 * note: not all bits of the first and last words may be contained 3765 * within the block range. 3766 */ 3767 for (r = nblocks; r > 0; r -= nb, blkno += nb) { 3768 /* number of bits preceding range to be freed in the word */ 3769 b = blkno & (DBWORD - 1); 3770 /* number of bits to free in the word */ 3771 nb = min(r, DBWORD - b); 3772 3773 /* is partial word to be freed ? */ 3774 if (nb < DBWORD) { 3775 /* free (set to 0) from the bitmap word */ 3776 dp->wmap[w] &= cpu_to_le32(~(ONES << (DBWORD - nb) 3777 >> b)); 3778 dp->pmap[w] &= cpu_to_le32(~(ONES << (DBWORD - nb) 3779 >> b)); 3780 3781 /* skip the word freed */ 3782 w++; 3783 } else { 3784 /* free (set to 0) contiguous bitmap words */ 3785 nw = r >> L2DBWORD; 3786 memset(&dp->wmap[w], 0, nw * 4); 3787 memset(&dp->pmap[w], 0, nw * 4); 3788 3789 /* skip the words freed */ 3790 nb = nw << L2DBWORD; 3791 w += nw; 3792 } 3793 } 3794 3795 /* 3796 * mark bits following the range to be freed (non-existing 3797 * blocks) as allocated (ONES) 3798 */ 3799 3800 if (blkno == BPERDMAP) 3801 goto initTree; 3802 3803 /* the first word beyond the end of existing blocks */ 3804 w = blkno >> L2DBWORD; 3805 3806 /* does nblocks fall on a 32-bit boundary ? */ 3807 b = blkno & (DBWORD - 1); 3808 if (b) { 3809 /* mark a partial word allocated */ 3810 dp->wmap[w] = dp->pmap[w] = cpu_to_le32(ONES >> b); 3811 w++; 3812 } 3813 3814 /* set the rest of the words in the page to allocated (ONES) */ 3815 for (i = w; i < LPERDMAP; i++) 3816 dp->pmap[i] = dp->wmap[i] = cpu_to_le32(ONES); 3817 3818 /* 3819 * init tree 3820 */ 3821 initTree: 3822 return (dbInitDmapTree(dp)); 3823 } 3824 3825 3826 /* 3827 * NAME: dbInitDmapTree()/ujfs_complete_dmap() 3828 * 3829 * FUNCTION: initialize summary tree of the specified dmap: 3830 * 3831 * at entry, bitmap of the dmap has been initialized; 3832 * 3833 * PARAMETERS: 3834 * dp - dmap to complete 3835 * blkno - starting block number for this dmap 3836 * treemax - will be filled in with max free for this dmap 3837 * 3838 * RETURNS: max free string at the root of the tree 3839 */ 3840 static int dbInitDmapTree(struct dmap * dp) 3841 { 3842 struct dmaptree *tp; 3843 s8 *cp; 3844 int i; 3845 3846 /* init fixed info of tree */ 3847 tp = &dp->tree; 3848 tp->nleafs = cpu_to_le32(LPERDMAP); 3849 tp->l2nleafs = cpu_to_le32(L2LPERDMAP); 3850 tp->leafidx = cpu_to_le32(LEAFIND); 3851 tp->height = cpu_to_le32(4); 3852 tp->budmin = BUDMIN; 3853 3854 /* init each leaf from corresponding wmap word: 3855 * note: leaf is set to NOFREE(-1) if all blocks of corresponding 3856 * bitmap word are allocated. 3857 */ 3858 cp = tp->stree + le32_to_cpu(tp->leafidx); 3859 for (i = 0; i < LPERDMAP; i++) 3860 *cp++ = dbMaxBud((u8 *) & dp->wmap[i]); 3861 3862 /* build the dmap's binary buddy summary tree */ 3863 return (dbInitTree(tp)); 3864 } 3865 3866 3867 /* 3868 * NAME: dbInitTree()/ujfs_adjtree() 3869 * 3870 * FUNCTION: initialize binary buddy summary tree of a dmap or dmapctl. 3871 * 3872 * at entry, the leaves of the tree has been initialized 3873 * from corresponding bitmap word or root of summary tree 3874 * of the child control page; 3875 * configure binary buddy system at the leaf level, then 3876 * bubble up the values of the leaf nodes up the tree. 3877 * 3878 * PARAMETERS: 3879 * cp - Pointer to the root of the tree 3880 * l2leaves- Number of leaf nodes as a power of 2 3881 * l2min - Number of blocks that can be covered by a leaf 3882 * as a power of 2 3883 * 3884 * RETURNS: max free string at the root of the tree 3885 */ 3886 static int dbInitTree(struct dmaptree * dtp) 3887 { 3888 int l2max, l2free, bsize, nextb, i; 3889 int child, parent, nparent; 3890 s8 *tp, *cp, *cp1; 3891 3892 tp = dtp->stree; 3893 3894 /* Determine the maximum free string possible for the leaves */ 3895 l2max = le32_to_cpu(dtp->l2nleafs) + dtp->budmin; 3896 3897 /* 3898 * configure the leaf levevl into binary buddy system 3899 * 3900 * Try to combine buddies starting with a buddy size of 1 3901 * (i.e. two leaves). At a buddy size of 1 two buddy leaves 3902 * can be combined if both buddies have a maximum free of l2min; 3903 * the combination will result in the left-most buddy leaf having 3904 * a maximum free of l2min+1. 3905 * After processing all buddies for a given size, process buddies 3906 * at the next higher buddy size (i.e. current size * 2) and 3907 * the next maximum free (current free + 1). 3908 * This continues until the maximum possible buddy combination 3909 * yields maximum free. 3910 */ 3911 for (l2free = dtp->budmin, bsize = 1; l2free < l2max; 3912 l2free++, bsize = nextb) { 3913 /* get next buddy size == current buddy pair size */ 3914 nextb = bsize << 1; 3915 3916 /* scan each adjacent buddy pair at current buddy size */ 3917 for (i = 0, cp = tp + le32_to_cpu(dtp->leafidx); 3918 i < le32_to_cpu(dtp->nleafs); 3919 i += nextb, cp += nextb) { 3920 /* coalesce if both adjacent buddies are max free */ 3921 if (*cp == l2free && *(cp + bsize) == l2free) { 3922 *cp = l2free + 1; /* left take right */ 3923 *(cp + bsize) = -1; /* right give left */ 3924 } 3925 } 3926 } 3927 3928 /* 3929 * bubble summary information of leaves up the tree. 3930 * 3931 * Starting at the leaf node level, the four nodes described by 3932 * the higher level parent node are compared for a maximum free and 3933 * this maximum becomes the value of the parent node. 3934 * when all lower level nodes are processed in this fashion then 3935 * move up to the next level (parent becomes a lower level node) and 3936 * continue the process for that level. 3937 */ 3938 for (child = le32_to_cpu(dtp->leafidx), 3939 nparent = le32_to_cpu(dtp->nleafs) >> 2; 3940 nparent > 0; nparent >>= 2, child = parent) { 3941 /* get index of 1st node of parent level */ 3942 parent = (child - 1) >> 2; 3943 3944 /* set the value of the parent node as the maximum 3945 * of the four nodes of the current level. 3946 */ 3947 for (i = 0, cp = tp + child, cp1 = tp + parent; 3948 i < nparent; i++, cp += 4, cp1++) 3949 *cp1 = TREEMAX(cp); 3950 } 3951 3952 return (*tp); 3953 } 3954 3955 3956 /* 3957 * dbInitDmapCtl() 3958 * 3959 * function: initialize dmapctl page 3960 */ 3961 static int dbInitDmapCtl(struct dmapctl * dcp, int level, int i) 3962 { /* start leaf index not covered by range */ 3963 s8 *cp; 3964 3965 dcp->nleafs = cpu_to_le32(LPERCTL); 3966 dcp->l2nleafs = cpu_to_le32(L2LPERCTL); 3967 dcp->leafidx = cpu_to_le32(CTLLEAFIND); 3968 dcp->height = cpu_to_le32(5); 3969 dcp->budmin = L2BPERDMAP + L2LPERCTL * level; 3970 3971 /* 3972 * initialize the leaves of current level that were not covered 3973 * by the specified input block range (i.e. the leaves have no 3974 * low level dmapctl or dmap). 3975 */ 3976 cp = &dcp->stree[CTLLEAFIND + i]; 3977 for (; i < LPERCTL; i++) 3978 *cp++ = NOFREE; 3979 3980 /* build the dmap's binary buddy summary tree */ 3981 return (dbInitTree((struct dmaptree *) dcp)); 3982 } 3983 3984 3985 /* 3986 * NAME: dbGetL2AGSize()/ujfs_getagl2size() 3987 * 3988 * FUNCTION: Determine log2(allocation group size) from aggregate size 3989 * 3990 * PARAMETERS: 3991 * nblocks - Number of blocks in aggregate 3992 * 3993 * RETURNS: log2(allocation group size) in aggregate blocks 3994 */ 3995 static int dbGetL2AGSize(s64 nblocks) 3996 { 3997 s64 sz; 3998 s64 m; 3999 int l2sz; 4000 4001 if (nblocks < BPERDMAP * MAXAG) 4002 return (L2BPERDMAP); 4003 4004 /* round up aggregate size to power of 2 */ 4005 m = ((u64) 1 << (64 - 1)); 4006 for (l2sz = 64; l2sz >= 0; l2sz--, m >>= 1) { 4007 if (m & nblocks) 4008 break; 4009 } 4010 4011 sz = (s64) 1 << l2sz; 4012 if (sz < nblocks) 4013 l2sz += 1; 4014 4015 /* agsize = roundupSize/max_number_of_ag */ 4016 return (l2sz - L2MAXAG); 4017 } 4018 4019 4020 /* 4021 * NAME: dbMapFileSizeToMapSize() 4022 * 4023 * FUNCTION: compute number of blocks the block allocation map file 4024 * can cover from the map file size; 4025 * 4026 * RETURNS: Number of blocks which can be covered by this block map file; 4027 */ 4028 4029 /* 4030 * maximum number of map pages at each level including control pages 4031 */ 4032 #define MAXL0PAGES (1 + LPERCTL) 4033 #define MAXL1PAGES (1 + LPERCTL * MAXL0PAGES) 4034 4035 /* 4036 * convert number of map pages to the zero origin top dmapctl level 4037 */ 4038 #define BMAPPGTOLEV(npages) \ 4039 (((npages) <= 3 + MAXL0PAGES) ? 0 : \ 4040 ((npages) <= 2 + MAXL1PAGES) ? 1 : 2) 4041 4042 s64 dbMapFileSizeToMapSize(struct inode * ipbmap) 4043 { 4044 struct super_block *sb = ipbmap->i_sb; 4045 s64 nblocks; 4046 s64 npages, ndmaps; 4047 int level, i; 4048 int complete, factor; 4049 4050 nblocks = ipbmap->i_size >> JFS_SBI(sb)->l2bsize; 4051 npages = nblocks >> JFS_SBI(sb)->l2nbperpage; 4052 level = BMAPPGTOLEV(npages); 4053 4054 /* At each level, accumulate the number of dmap pages covered by 4055 * the number of full child levels below it; 4056 * repeat for the last incomplete child level. 4057 */ 4058 ndmaps = 0; 4059 npages--; /* skip the first global control page */ 4060 /* skip higher level control pages above top level covered by map */ 4061 npages -= (2 - level); 4062 npages--; /* skip top level's control page */ 4063 for (i = level; i >= 0; i--) { 4064 factor = 4065 (i == 2) ? MAXL1PAGES : ((i == 1) ? MAXL0PAGES : 1); 4066 complete = (u32) npages / factor; 4067 ndmaps += complete * ((i == 2) ? LPERCTL * LPERCTL : 4068 ((i == 1) ? LPERCTL : 1)); 4069 4070 /* pages in last/incomplete child */ 4071 npages = (u32) npages % factor; 4072 /* skip incomplete child's level control page */ 4073 npages--; 4074 } 4075 4076 /* convert the number of dmaps into the number of blocks 4077 * which can be covered by the dmaps; 4078 */ 4079 nblocks = ndmaps << L2BPERDMAP; 4080 4081 return (nblocks); 4082 } 4083