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