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