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