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