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