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