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