Lines Matching +full:ip +full:- +full:blocks
1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * Copyright (C) International Business Machines Corp., 2000-2004
41 * take the lock in read mode. a single top-down request may proceed
42 * exclusively while multiple bottoms-up requests may proceed
50 * in the face of multiple-bottoms up requests.
57 #define BMAP_LOCK_INIT(bmp) mutex_init(&bmp->db_bmaplock)
58 #define BMAP_LOCK(bmp) mutex_lock(&bmp->db_bmaplock)
59 #define BMAP_UNLOCK(bmp) mutex_unlock(&bmp->db_bmaplock)
87 static int dbExtend(struct inode *ip, s64 blkno, s64 nblocks, s64 addnblocks);
133 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, -1
141 * memory is allocated for the in-core bmap descriptor and
142 * the in-core descriptor is initialized from disk.
145 * ipbmap - pointer to in-core inode for the block map.
148 * 0 - success
149 * -ENOMEM - insufficient memory
150 * -EIO - i/o error
160 * allocate/initialize the in-memory bmap descriptor in dbMount()
162 /* allocate memory for the in-memory bmap descriptor */ in dbMount()
165 return -ENOMEM; in dbMount()
167 /* read the on-disk bmap descriptor. */ in dbMount()
169 BMAPBLKNO << JFS_SBI(ipbmap->i_sb)->l2nbperpage, in dbMount()
173 return -EIO; in dbMount()
176 /* copy the on-disk bmap descriptor to its in-memory version. */ in dbMount()
177 dbmp_le = (struct dbmap_disk *) mp->data; in dbMount()
178 bmp->db_mapsize = le64_to_cpu(dbmp_le->dn_mapsize); in dbMount()
179 bmp->db_nfree = le64_to_cpu(dbmp_le->dn_nfree); in dbMount()
180 bmp->db_l2nbperpage = le32_to_cpu(dbmp_le->dn_l2nbperpage); in dbMount()
181 bmp->db_numag = le32_to_cpu(dbmp_le->dn_numag); in dbMount()
182 bmp->db_maxlevel = le32_to_cpu(dbmp_le->dn_maxlevel); in dbMount()
183 bmp->db_maxag = le32_to_cpu(dbmp_le->dn_maxag); in dbMount()
184 bmp->db_agpref = le32_to_cpu(dbmp_le->dn_agpref); in dbMount()
185 bmp->db_aglevel = le32_to_cpu(dbmp_le->dn_aglevel); in dbMount()
186 bmp->db_agheight = le32_to_cpu(dbmp_le->dn_agheight); in dbMount()
187 bmp->db_agwidth = le32_to_cpu(dbmp_le->dn_agwidth); in dbMount()
188 bmp->db_agstart = le32_to_cpu(dbmp_le->dn_agstart); in dbMount()
189 bmp->db_agl2size = le32_to_cpu(dbmp_le->dn_agl2size); in dbMount()
191 bmp->db_agfree[i] = le64_to_cpu(dbmp_le->dn_agfree[i]); in dbMount()
192 bmp->db_agsize = le64_to_cpu(dbmp_le->dn_agsize); in dbMount()
193 bmp->db_maxfreebud = dbmp_le->dn_maxfreebud; in dbMount()
199 bmp->db_ipbmap = ipbmap; in dbMount()
200 JFS_SBI(ipbmap->i_sb)->bmap = bmp; in dbMount()
202 memset(bmp->db_active, 0, sizeof(bmp->db_active)); in dbMount()
219 * the in-core bmap descriptor is written to disk and
223 * ipbmap - pointer to in-core inode for the block map.
226 * 0 - success
227 * -EIO - i/o error
231 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap; in dbUnmount()
239 truncate_inode_pages(ipbmap->i_mapping, 0); in dbUnmount()
241 /* free the memory for the in-memory bmap. */ in dbUnmount()
253 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap; in dbSync()
260 /* get the buffer for the on-disk bmap descriptor. */ in dbSync()
262 BMAPBLKNO << JFS_SBI(ipbmap->i_sb)->l2nbperpage, in dbSync()
266 return -EIO; in dbSync()
268 /* copy the in-memory version of the bmap to the on-disk version */ in dbSync()
269 dbmp_le = (struct dbmap_disk *) mp->data; in dbSync()
270 dbmp_le->dn_mapsize = cpu_to_le64(bmp->db_mapsize); in dbSync()
271 dbmp_le->dn_nfree = cpu_to_le64(bmp->db_nfree); in dbSync()
272 dbmp_le->dn_l2nbperpage = cpu_to_le32(bmp->db_l2nbperpage); in dbSync()
273 dbmp_le->dn_numag = cpu_to_le32(bmp->db_numag); in dbSync()
274 dbmp_le->dn_maxlevel = cpu_to_le32(bmp->db_maxlevel); in dbSync()
275 dbmp_le->dn_maxag = cpu_to_le32(bmp->db_maxag); in dbSync()
276 dbmp_le->dn_agpref = cpu_to_le32(bmp->db_agpref); in dbSync()
277 dbmp_le->dn_aglevel = cpu_to_le32(bmp->db_aglevel); in dbSync()
278 dbmp_le->dn_agheight = cpu_to_le32(bmp->db_agheight); in dbSync()
279 dbmp_le->dn_agwidth = cpu_to_le32(bmp->db_agwidth); in dbSync()
280 dbmp_le->dn_agstart = cpu_to_le32(bmp->db_agstart); in dbSync()
281 dbmp_le->dn_agl2size = cpu_to_le32(bmp->db_agl2size); in dbSync()
283 dbmp_le->dn_agfree[i] = cpu_to_le64(bmp->db_agfree[i]); in dbSync()
284 dbmp_le->dn_agsize = cpu_to_le64(bmp->db_agsize); in dbSync()
285 dbmp_le->dn_maxfreebud = bmp->db_maxfreebud; in dbSync()
293 filemap_write_and_wait(ipbmap->i_mapping); in dbSync()
306 * the blocks will be free from the working map one dmap
310 * ip - pointer to in-core inode;
311 * blkno - starting block number to be freed.
312 * nblocks - number of blocks to be freed.
315 * 0 - success
316 * -EIO - i/o error
318 int dbFree(struct inode *ip, s64 blkno, s64 nblocks) in dbFree() argument
324 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap; in dbFree()
325 struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap; in dbFree()
326 struct super_block *sb = ipbmap->i_sb; in dbFree()
331 if (unlikely((blkno == 0) || (blkno + nblocks > bmp->db_mapsize))) { in dbFree()
336 jfs_error(ip->i_sb, "block to be freed is outside the map\n"); in dbFree()
337 return -EIO; in dbFree()
341 * TRIM the blocks, when mounted with discard option in dbFree()
343 if (JFS_SBI(sb)->flag & JFS_DISCARD) in dbFree()
344 if (JFS_SBI(sb)->minblks_trim <= nblocks) in dbFree()
348 * free the blocks a dmap at a time. in dbFree()
351 for (rem = nblocks; rem > 0; rem -= nb, blkno += nb) { in dbFree()
358 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); in dbFree()
362 return -EIO; in dbFree()
364 dp = (struct dmap *) mp->data; in dbFree()
366 /* determine the number of blocks to be freed from in dbFree()
369 nb = min(rem, BPERDMAP - (blkno & (BPERDMAP - 1))); in dbFree()
371 /* free the blocks. */ in dbFree()
373 jfs_error(ip->i_sb, "error in block map\n"); in dbFree()
395 * the blocks will be updated in the persistent map one
399 * ipbmap - pointer to in-core inode for the block map.
400 * free - 'true' if block range is to be freed from the persistent
402 * blkno - starting block number of the range.
403 * nblocks - number of contiguous blocks in the range.
404 * tblk - transaction block;
407 * 0 - success
408 * -EIO - i/o error
416 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap; in dbUpdatePMap()
425 /* the blocks better be within the mapsize. */ in dbUpdatePMap()
426 if (blkno + nblocks > bmp->db_mapsize) { in dbUpdatePMap()
430 jfs_error(ipbmap->i_sb, "blocks are outside the map\n"); in dbUpdatePMap()
431 return -EIO; in dbUpdatePMap()
435 lsn = tblk->lsn; in dbUpdatePMap()
436 log = (struct jfs_log *) JFS_SBI(tblk->sb)->log; in dbUpdatePMap()
444 for (rem = nblocks; rem > 0; rem -= nblks, blkno += nblks) { in dbUpdatePMap()
446 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); in dbUpdatePMap()
452 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, in dbUpdatePMap()
455 return -EIO; in dbUpdatePMap()
458 dp = (struct dmap *) mp->data; in dbUpdatePMap()
461 * the starting block. also determine how many blocks in dbUpdatePMap()
464 dbitno = blkno & (BPERDMAP - 1); in dbUpdatePMap()
466 nblks = min(rem, (s64)BPERDMAP - dbitno); in dbUpdatePMap()
476 rbits -= nbits, dbitno += nbits) { in dbUpdatePMap()
480 wbitno = dbitno & (DBWORD - 1); in dbUpdatePMap()
481 nbits = min(rbits, DBWORD - wbitno); in dbUpdatePMap()
489 (ONES << (DBWORD - nbits) >> wbitno); in dbUpdatePMap()
491 dp->pmap[word] &= in dbUpdatePMap()
494 dp->pmap[word] |= in dbUpdatePMap()
510 memset(&dp->pmap[word], 0, in dbUpdatePMap()
513 memset(&dp->pmap[word], (int) ONES, in dbUpdatePMap()
529 if (mp->lsn != 0) { in dbUpdatePMap()
531 logdiff(diffp, mp->lsn, log); in dbUpdatePMap()
533 mp->lsn = lsn; in dbUpdatePMap()
536 list_move(&mp->synclist, &tblk->synclist); in dbUpdatePMap()
540 logdiff(difft, tblk->clsn, log); in dbUpdatePMap()
541 logdiff(diffp, mp->clsn, log); in dbUpdatePMap()
543 mp->clsn = tblk->clsn; in dbUpdatePMap()
545 mp->log = log; in dbUpdatePMap()
546 mp->lsn = lsn; in dbUpdatePMap()
549 log->count++; in dbUpdatePMap()
550 list_add(&mp->synclist, &tblk->synclist); in dbUpdatePMap()
552 mp->clsn = tblk->clsn; in dbUpdatePMap()
574 * new inode allocation towards. The tie-in between inode
585 * ipbmap - pointer to in-core inode for the block map.
596 int next_best = -1; in dbNextAG()
597 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap; in dbNextAG()
601 /* determine the average number of free blocks within the ags. */ in dbNextAG()
602 avgfree = (u32)bmp->db_nfree / bmp->db_numag; in dbNextAG()
608 agpref = bmp->db_agpref; in dbNextAG()
609 if ((atomic_read(&bmp->db_active[agpref]) == 0) && in dbNextAG()
610 (bmp->db_agfree[agpref] >= avgfree)) in dbNextAG()
616 for (i = 0 ; i < bmp->db_numag; i++, agpref++) { in dbNextAG()
617 if (agpref == bmp->db_numag) in dbNextAG()
620 if (atomic_read(&bmp->db_active[agpref])) in dbNextAG()
623 if (bmp->db_agfree[agpref] >= avgfree) { in dbNextAG()
625 bmp->db_agpref = agpref; in dbNextAG()
627 } else if (bmp->db_agfree[agpref] > hwm) { in dbNextAG()
629 hwm = bmp->db_agfree[agpref]; in dbNextAG()
638 if (next_best != -1) in dbNextAG()
639 bmp->db_agpref = next_best; in dbNextAG()
646 return (bmp->db_agpref); in dbNextAG()
653 * blocks from the working allocation block map.
655 * the block allocation policy uses hints and a multi-step
658 * for allocation requests smaller than the number of blocks
659 * per dmap, we first try to allocate the new blocks
660 * immediately following the hint. if these blocks are not
661 * available, we try to allocate blocks near the hint. if
662 * no blocks near the hint are available, we next try to
665 * if no blocks are available in the dmap or the allocation
676 * ip - pointer to in-core inode;
677 * hint - allocation hint.
678 * nblocks - number of contiguous blocks in the range.
679 * results - on successful return, set to the starting block number
683 * 0 - success
684 * -ENOSPC - insufficient disk resources
685 * -EIO - i/o error
687 int dbAlloc(struct inode *ip, s64 hint, s64 nblocks, s64 * results) in dbAlloc() argument
690 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap; in dbAlloc()
702 /* get the log2 number of blocks to be allocated. in dbAlloc()
703 * if the number of blocks is not a log2 multiple, in dbAlloc()
708 bmp = JFS_SBI(ip->i_sb)->bmap; in dbAlloc()
710 mapSize = bmp->db_mapsize; in dbAlloc()
714 jfs_error(ip->i_sb, "the hint is outside the map\n"); in dbAlloc()
715 return -EIO; in dbAlloc()
718 /* if the number of blocks to be allocated is greater than the in dbAlloc()
721 if (l2nb > bmp->db_agl2size) { in dbAlloc()
741 if (blkno >= bmp->db_mapsize) in dbAlloc()
744 agno = blkno >> bmp->db_agl2size; in dbAlloc()
750 if ((blkno & (bmp->db_agsize - 1)) == 0) in dbAlloc()
752 * if so, call dbNextAG() to find a non-busy in dbAlloc()
755 if (atomic_read(&bmp->db_active[agno])) in dbAlloc()
767 rc = -EIO; in dbAlloc()
768 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); in dbAlloc()
773 dp = (struct dmap *) mp->data; in dbAlloc()
776 * blocks beginning at the hint. in dbAlloc()
779 != -ENOSPC) { in dbAlloc()
789 writers = atomic_read(&bmp->db_active[agno]); in dbAlloc()
791 ((writers == 1) && (JFS_IP(ip)->active_ag != agno))) { in dbAlloc()
801 /* next, try to satisfy the allocation request with blocks in dbAlloc()
806 != -ENOSPC) { in dbAlloc()
814 /* try to satisfy the allocation request with blocks within in dbAlloc()
818 != -ENOSPC) { in dbAlloc()
830 /* try to satisfy the allocation request with blocks within in dbAlloc()
834 if ((rc = dbAllocAG(bmp, agno, nblocks, l2nb, results)) != -ENOSPC) in dbAlloc()
850 if ((rc = dbAllocAG(bmp, agno, nblocks, l2nb, results)) == -ENOSPC) in dbAlloc()
871 * ip - pointer to in-core inode;
872 * blkno - extent address;
873 * nblocks - extent length;
876 * 0 - success
877 * -ENOSPC - insufficient disk resources
878 * -EIO - i/o error
880 int dbAllocExact(struct inode *ip, s64 blkno, int nblocks) in dbAllocExact() argument
883 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap; in dbAllocExact()
884 struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap; in dbAllocExact()
895 * max 64 blocks will be moved. in dbAllocExact()
898 if (nblocks <= 0 || nblocks > BPERDMAP || blkno >= bmp->db_mapsize) { in dbAllocExact()
900 return -EINVAL; in dbAllocExact()
903 if (nblocks > ((s64) 1 << bmp->db_maxfreebud)) { in dbAllocExact()
906 return -ENOSPC; in dbAllocExact()
910 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); in dbAllocExact()
914 return -EIO; in dbAllocExact()
916 dp = (struct dmap *) mp->data; in dbAllocExact()
936 * number of blocks.
940 * place by allocating the additional blocks as the blocks
942 * blocks are not available, this routine will attempt to
943 * allocate a new set of contiguous blocks large enough
945 * number of blocks required.
948 * ip - pointer to in-core inode requiring allocation.
949 * blkno - starting block of the current allocation.
950 * nblocks - number of contiguous blocks within the current
952 * addnblocks - number of blocks to add to the allocation.
953 * results - on successful return, set to the starting block number
960 * 0 - success
961 * -ENOSPC - insufficient disk resources
962 * -EIO - i/o error
965 dbReAlloc(struct inode *ip, in dbReAlloc() argument
972 if ((rc = dbExtend(ip, blkno, nblocks, addnblocks)) == 0) { in dbReAlloc()
976 if (rc != -ENOSPC) in dbReAlloc()
981 * new set of blocks for the entire request (i.e. try to get in dbReAlloc()
982 * a range of contiguous blocks large enough to cover the in dbReAlloc()
983 * existing allocation plus the additional blocks.) in dbReAlloc()
986 (ip, blkno + nblocks - 1, addnblocks + nblocks, results)); in dbReAlloc()
994 * number of blocks.
998 * place by allocating the additional blocks as the blocks
1002 * ip - pointer to in-core inode requiring allocation.
1003 * blkno - starting block of the current allocation.
1004 * nblocks - number of contiguous blocks within the current
1006 * addnblocks - number of blocks to add to the allocation.
1009 * 0 - success
1010 * -ENOSPC - insufficient disk resources
1011 * -EIO - i/o error
1013 static int dbExtend(struct inode *ip, s64 blkno, s64 nblocks, s64 addnblocks) in dbExtend() argument
1015 struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb); in dbExtend()
1021 struct inode *ipbmap = sbi->ipbmap; in dbExtend()
1025 * We don't want a non-aligned extent to cross a page boundary in dbExtend()
1027 if (((rel_block = blkno & (sbi->nbperpage - 1))) && in dbExtend()
1028 (rel_block + nblocks + addnblocks > sbi->nbperpage)) in dbExtend()
1029 return -ENOSPC; in dbExtend()
1032 lastblkno = blkno + nblocks - 1; in dbExtend()
1042 bmp = sbi->bmap; in dbExtend()
1043 if (lastblkno < 0 || lastblkno >= bmp->db_mapsize) { in dbExtend()
1045 jfs_error(ip->i_sb, "the block is outside the filesystem\n"); in dbExtend()
1046 return -EIO; in dbExtend()
1050 * allocating the additional blocks as the blocks immediately in dbExtend()
1052 * current allocation in place if the number of additional blocks in dbExtend()
1057 if (addnblocks > BPERDMAP || extblkno >= bmp->db_mapsize || in dbExtend()
1058 (extblkno & (bmp->db_agsize - 1)) == 0) { in dbExtend()
1060 return -ENOSPC; in dbExtend()
1066 lblkno = BLKTODMAP(extblkno, bmp->db_l2nbperpage); in dbExtend()
1070 return -EIO; in dbExtend()
1073 dp = (struct dmap *) mp->data; in dbExtend()
1075 /* try to allocate the blocks immediately following the in dbExtend()
1096 * FUNCTION: attempt to allocate the blocks of the specified block
1100 * bmp - pointer to bmap descriptor
1101 * dp - pointer to dmap.
1102 * blkno - starting block number of the range.
1103 * nblocks - number of contiguous free blocks of the range.
1106 * 0 - success
1107 * -ENOSPC - insufficient disk resources
1108 * -EIO - i/o error
1120 if (dp->tree.leafidx != cpu_to_le32(LEAFIND)) { in dbAllocNext()
1121 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmap page\n"); in dbAllocNext()
1122 return -EIO; in dbAllocNext()
1127 leaf = dp->tree.stree + le32_to_cpu(dp->tree.leafidx); in dbAllocNext()
1132 dbitno = blkno & (BPERDMAP - 1); in dbAllocNext()
1139 return -ENOSPC; in dbAllocNext()
1145 return -ENOSPC; in dbAllocNext()
1155 * tree will be examined to determine if the blocks are free. a in dbAllocNext()
1160 for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) { in dbAllocNext()
1164 wbitno = dbitno & (DBWORD - 1); in dbAllocNext()
1165 nb = min(rembits, DBWORD - wbitno); in dbAllocNext()
1172 mask = (ONES << (DBWORD - nb) >> wbitno); in dbAllocNext()
1173 if ((mask & ~le32_to_cpu(dp->wmap[word])) != mask) in dbAllocNext()
1174 return -ENOSPC; in dbAllocNext()
1186 * if the blocks are free. in dbAllocNext()
1192 return -ENOSPC; in dbAllocNext()
1204 nwords -= nw; in dbAllocNext()
1210 /* allocate the blocks. in dbAllocNext()
1219 * FUNCTION: attempt to allocate a number of contiguous free blocks near
1228 * bmp - pointer to bmap descriptor
1229 * dp - pointer to dmap.
1230 * blkno - block number to allocate near.
1231 * nblocks - actual number of contiguous free blocks desired.
1232 * l2nb - log2 number of contiguous free blocks desired.
1233 * results - on successful return, set to the starting block number
1237 * 0 - success
1238 * -ENOSPC - insufficient disk resources
1239 * -EIO - i/o error
1250 if (dp->tree.leafidx != cpu_to_le32(LEAFIND)) { in dbAllocNear()
1251 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmap page\n"); in dbAllocNear()
1252 return -EIO; in dbAllocNear()
1255 leaf = dp->tree.stree + le32_to_cpu(dp->tree.leafidx); in dbAllocNear()
1261 word = (blkno & (BPERDMAP - 1)) >> L2DBWORD; in dbAllocNear()
1275 blkno = le64_to_cpu(dp->start) + (word << L2DBWORD); in dbAllocNear()
1284 dbFindBits(le32_to_cpu(dp->wmap[word]), l2nb); in dbAllocNear()
1286 /* allocate the blocks. in dbAllocNear()
1294 return -ENOSPC; in dbAllocNear()
1302 * free blocks within the specified allocation group.
1305 * of blocks per dmap, the dmap control pages will be used to
1315 * or two sub-trees, depending on the allocation group size.
1338 * bmp - pointer to bmap descriptor
1339 * agno - allocation group number.
1340 * nblocks - actual number of contiguous free blocks desired.
1341 * l2nb - log2 number of contiguous free blocks desired.
1342 * results - on successful return, set to the starting block number
1346 * 0 - success
1347 * -ENOSPC - insufficient disk resources
1348 * -EIO - i/o error
1364 if (l2nb > bmp->db_agl2size) { in dbAllocAG()
1365 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocAG()
1367 return -EIO; in dbAllocAG()
1373 blkno = (s64) agno << bmp->db_agl2size; in dbAllocAG()
1392 if (bmp->db_agsize == BPERDMAP in dbAllocAG()
1393 || bmp->db_agfree[agno] == bmp->db_agsize) { in dbAllocAG()
1395 if ((rc == -ENOSPC) && in dbAllocAG()
1396 (bmp->db_agfree[agno] == bmp->db_agsize)) { in dbAllocAG()
1397 printk(KERN_ERR "blkno = %Lx, blocks = %Lx\n", in dbAllocAG()
1400 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocAG()
1409 lblkno = BLKTOCTL(blkno, bmp->db_l2nbperpage, bmp->db_aglevel); in dbAllocAG()
1410 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); in dbAllocAG()
1412 return -EIO; in dbAllocAG()
1413 dcp = (struct dmapctl *) mp->data; in dbAllocAG()
1414 budmin = dcp->budmin; in dbAllocAG()
1416 if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) { in dbAllocAG()
1417 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmapctl page\n"); in dbAllocAG()
1419 return -EIO; in dbAllocAG()
1430 (1 << (L2LPERCTL - (bmp->db_agheight << 1))) / bmp->db_agwidth; in dbAllocAG()
1431 ti = bmp->db_agstart + bmp->db_agwidth * (agno & (agperlev - 1)); in dbAllocAG()
1433 /* dmap control page trees fan-out by 4 and a single allocation in dbAllocAG()
1439 for (i = 0; i < bmp->db_agwidth; i++, ti++) { in dbAllocAG()
1442 if (l2nb > dcp->stree[ti]) in dbAllocAG()
1449 for (k = bmp->db_agheight; k > 0; k--) { in dbAllocAG()
1451 if (l2nb <= dcp->stree[m + n]) { in dbAllocAG()
1457 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocAG()
1460 return -EIO; in dbAllocAG()
1467 if (bmp->db_aglevel == 2) in dbAllocAG()
1469 else if (bmp->db_aglevel == 1) in dbAllocAG()
1470 blkno &= ~(MAXL1SIZE - 1); in dbAllocAG()
1471 else /* bmp->db_aglevel == 0 */ in dbAllocAG()
1472 blkno &= ~(MAXL0SIZE - 1); in dbAllocAG()
1475 ((s64) (ti - le32_to_cpu(dcp->leafidx))) << budmin; in dbAllocAG()
1484 * blocks required is less than maximum number of blocks in dbAllocAG()
1494 dbFindCtl(bmp, l2nb, bmp->db_aglevel - 1, in dbAllocAG()
1496 if (rc == -ENOSPC) { in dbAllocAG()
1497 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocAG()
1499 return -EIO; in dbAllocAG()
1505 /* allocate the blocks. in dbAllocAG()
1508 if (rc == -ENOSPC) { in dbAllocAG()
1509 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocAG()
1510 "unable to allocate blocks\n"); in dbAllocAG()
1511 rc = -EIO; in dbAllocAG()
1517 * return -ENOSPC. in dbAllocAG()
1521 return -ENOSPC; in dbAllocAG()
1529 * free blocks anywhere in the file system.
1538 * bmp - pointer to bmap descriptor
1539 * nblocks - actual number of contiguous free blocks desired.
1540 * l2nb - log2 number of contiguous free blocks desired.
1541 * results - on successful return, set to the starting block number
1545 * 0 - success
1546 * -ENOSPC - insufficient disk resources
1547 * -EIO - i/o error
1562 if ((rc = dbFindCtl(bmp, l2nb, bmp->db_maxlevel, &blkno))) in dbAllocAny()
1565 /* allocate the blocks. in dbAllocAny()
1568 if (rc == -ENOSPC) { in dbAllocAny()
1569 jfs_error(bmp->db_ipbmap->i_sb, "unable to allocate blocks\n"); in dbAllocAny()
1570 return -EIO; in dbAllocAny()
1579 * FUNCTION: attempt to discard (TRIM) all free blocks of specific AG
1582 * 1) allocate blocks, as large as possible and save them
1585 * 3) mark the blocks free again
1588 * - we work only on one ag at some time, minimizing how long we
1590 * - reading / writing the fs is possible most time, even on
1594 * - we write two times to the dmapctl and dmap pages
1595 * - but for me, this seems the best way, better ideas?
1599 * ip - pointer to in-core inode
1600 * agno - ag to trim
1601 * minlen - minimum value of contiguous blocks
1604 * s64 - actual number of blocks trimmed
1606 s64 dbDiscardAG(struct inode *ip, int agno, s64 minlen) in dbDiscardAG() argument
1608 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap; in dbDiscardAG()
1609 struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap; in dbDiscardAG()
1613 struct super_block *sb = ipbmap->i_sb; in dbDiscardAG()
1627 nblocks = bmp->db_agfree[agno]; in dbDiscardAG()
1633 jfs_error(bmp->db_ipbmap->i_sb, "no memory for trim array\n"); in dbDiscardAG()
1642 /* 0 = okay, -EIO = fatal, -ENOSPC -> try smaller block */ in dbDiscardAG()
1645 tt->blkno = blkno; in dbDiscardAG()
1646 tt->nblocks = nblocks; in dbDiscardAG()
1650 if (bmp->db_agfree[agno] == 0) in dbDiscardAG()
1654 nblocks = bmp->db_agfree[agno]; in dbDiscardAG()
1656 } else if (rc == -ENOSPC) { in dbDiscardAG()
1658 l2nb = BLKSTOL2(nblocks) - 1; in dbDiscardAG()
1661 /* Trim any already allocated blocks */ in dbDiscardAG()
1662 jfs_error(bmp->db_ipbmap->i_sb, "-EIO\n"); in dbDiscardAG()
1667 if (unlikely(count >= range_cnt - 1)) in dbDiscardAG()
1672 tt->nblocks = 0; /* mark the current end */ in dbDiscardAG()
1673 for (tt = totrim; tt->nblocks != 0; tt++) { in dbDiscardAG()
1676 if (!(JFS_SBI(sb)->flag & JFS_DISCARD)) in dbDiscardAG()
1677 jfs_issue_discard(ip, tt->blkno, tt->nblocks); in dbDiscardAG()
1678 dbFree(ip, tt->blkno, tt->nblocks); in dbDiscardAG()
1679 trimmed += tt->nblocks; in dbDiscardAG()
1691 * contiguous free blocks large enough to satisfy an allocation
1692 * request for the specified number of free blocks.
1694 * if sufficient contiguous free blocks are found, this routine
1696 * contains or starts a range of contiqious free blocks that
1700 * bmp - pointer to bmap descriptor
1701 * level - starting dmap control page level.
1702 * l2nb - log2 number of contiguous free blocks desired.
1703 * *blkno - on entry, starting block number for conducting the search.
1705 * that contains or starts a range of contiguous free blocks.
1708 * 0 - success
1709 * -ENOSPC - insufficient disk resources
1710 * -EIO - i/o error
1725 * sufficient free blocks. in dbFindCtl()
1727 for (lev = level, b = *blkno; lev >= 0; lev--) { in dbFindCtl()
1731 lblkno = BLKTOCTL(b, bmp->db_l2nbperpage, lev); in dbFindCtl()
1732 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); in dbFindCtl()
1734 return -EIO; in dbFindCtl()
1735 dcp = (struct dmapctl *) mp->data; in dbFindCtl()
1736 budmin = dcp->budmin; in dbFindCtl()
1738 if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) { in dbFindCtl()
1739 jfs_error(bmp->db_ipbmap->i_sb, in dbFindCtl()
1742 return -EIO; in dbFindCtl()
1760 jfs_error(bmp->db_ipbmap->i_sb, in dbFindCtl()
1762 return -EIO; in dbFindCtl()
1764 return -ENOSPC; in dbFindCtl()
1774 * the number of blocks required is greater than or equal in dbFindCtl()
1775 * to the maximum number of blocks described at the next in dbFindCtl()
1791 * blocks starting within a specific dmap.
1799 * that is made up of the blocks of one or more dmaps. these
1805 * group whose size is equal to the number of blocks per dmap.
1817 * bmp - pointer to bmap descriptor
1818 * nblocks - actual number of contiguous free blocks to allocate.
1819 * l2nb - log2 number of contiguous free blocks to allocate.
1820 * blkno - starting block number of the dmap to start the allocation
1822 * results - on successful return, set to the starting block number
1826 * 0 - success
1827 * -ENOSPC - insufficient disk resources
1828 * -EIO - i/o error
1845 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); in dbAllocCtl()
1846 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); in dbAllocCtl()
1848 return -EIO; in dbAllocCtl()
1849 dp = (struct dmap *) mp->data; in dbAllocCtl()
1851 /* try to allocate the blocks. in dbAllocCtl()
1865 assert((blkno & (BPERDMAP - 1)) == 0); in dbAllocCtl()
1867 /* allocate the blocks dmap by dmap. in dbAllocCtl()
1869 for (n = nblocks, b = blkno; n > 0; n -= nb, b += nb) { in dbAllocCtl()
1872 lblkno = BLKTODMAP(b, bmp->db_l2nbperpage); in dbAllocCtl()
1873 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); in dbAllocCtl()
1875 rc = -EIO; in dbAllocCtl()
1878 dp = (struct dmap *) mp->data; in dbAllocCtl()
1882 if (dp->tree.stree[ROOT] != L2BPERDMAP) { in dbAllocCtl()
1884 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocCtl()
1886 rc = -EIO; in dbAllocCtl()
1890 /* determine how many blocks to allocate from this dmap. in dbAllocCtl()
1894 /* allocate the blocks from the dmap. in dbAllocCtl()
1915 * system to indicate that blocks have been leaked. in dbAllocCtl()
1921 for (n = nblocks - n, b = blkno; n > 0; in dbAllocCtl()
1922 n -= BPERDMAP, b += BPERDMAP) { in dbAllocCtl()
1925 lblkno = BLKTODMAP(b, bmp->db_l2nbperpage); in dbAllocCtl()
1926 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); in dbAllocCtl()
1929 * to indicate that we have leaked blocks. in dbAllocCtl()
1931 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocCtl()
1935 dp = (struct dmap *) mp->data; in dbAllocCtl()
1937 /* free the blocks is this dmap. in dbAllocCtl()
1941 * to indicate that we have leaked blocks. in dbAllocCtl()
1944 jfs_error(bmp->db_ipbmap->i_sb, "Block Leakage\n"); in dbAllocCtl()
1960 * FUNCTION: attempt to allocate a specified number of contiguous blocks
1963 * this routine checks if the contiguous blocks are available.
1964 * if so, nblocks of blocks are allocated; otherwise, ENOSPC is
1968 * mp - pointer to bmap descriptor
1969 * dp - pointer to dmap to attempt to allocate blocks from.
1970 * l2nb - log2 number of contiguous block desired.
1971 * nblocks - actual number of contiguous block desired.
1972 * results - on successful return, set to the starting block number
1976 * 0 - success
1977 * -ENOSPC - insufficient disk resources
1978 * -EIO - i/o error
1990 /* can't be more than a dmaps worth of blocks */ in dbAllocDmapLev()
1997 if (dbFindLeaf((dmtree_t *) & dp->tree, l2nb, &leafidx)) in dbAllocDmapLev()
1998 return -ENOSPC; in dbAllocDmapLev()
2003 blkno = le64_to_cpu(dp->start) + (leafidx << L2DBWORD); in dbAllocDmapLev()
2009 if (dp->tree.stree[leafidx + LEAFIND] < BUDMIN) in dbAllocDmapLev()
2010 blkno += dbFindBits(le32_to_cpu(dp->wmap[leafidx]), l2nb); in dbAllocDmapLev()
2012 /* allocate the blocks */ in dbAllocDmapLev()
2026 * this routine allocates the specified blocks from the dmap
2028 * block range causes the maximum string of free blocks within
2036 * bmp - pointer to bmap descriptor
2037 * dp - pointer to dmap to allocate the block range from.
2038 * blkno - starting block number of the block to be allocated.
2039 * nblocks - number of blocks to be allocated.
2042 * 0 - success
2043 * -EIO - i/o error
2056 oldroot = dp->tree.stree[ROOT]; in dbAllocDmap()
2058 /* allocate the specified (blocks) bits */ in dbAllocDmap()
2062 if (dp->tree.stree[ROOT] == oldroot) in dbAllocDmap()
2069 if ((rc = dbAdjCtl(bmp, blkno, dp->tree.stree[ROOT], 1, 0))) in dbAllocDmap()
2082 * this routine frees the specified blocks from the dmap through
2084 * causes the maximum string of free blocks within the dmap to
2091 * bmp - pointer to bmap descriptor
2092 * dp - pointer to dmap to free the block range from.
2093 * blkno - starting block number of the block to be freed.
2094 * nblocks - number of blocks to be freed.
2097 * 0 - success
2098 * -EIO - i/o error
2111 oldroot = dp->tree.stree[ROOT]; in dbFreeDmap()
2113 /* free the specified (blocks) bits */ in dbFreeDmap()
2117 if (rc || (dp->tree.stree[ROOT] == oldroot)) in dbFreeDmap()
2124 if ((rc = dbAdjCtl(bmp, blkno, dp->tree.stree[ROOT], 0, 0))) { in dbFreeDmap()
2125 word = (blkno & (BPERDMAP - 1)) >> L2DBWORD; in dbFreeDmap()
2129 * the freed blocks to become part of a larger binary buddy in dbFreeDmap()
2132 if (dp->tree.stree[word] == NOFREE) in dbFreeDmap()
2133 dbBackSplit((dmtree_t *) & dp->tree, word); in dbFreeDmap()
2155 * bmp - pointer to bmap descriptor
2156 * dp - pointer to dmap to allocate bits from.
2157 * blkno - starting block number of the bits to be allocated.
2158 * nblocks - number of bits to be allocated.
2168 dmtree_t *tp = (dmtree_t *) & dp->tree; in dbAllocBits()
2173 leaf = dp->tree.stree + LEAFIND; in dbAllocBits()
2178 dbitno = blkno & (BPERDMAP - 1); in dbAllocBits()
2197 for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) { in dbAllocBits()
2201 wbitno = dbitno & (DBWORD - 1); in dbAllocBits()
2202 nb = min(rembits, DBWORD - wbitno); in dbAllocBits()
2210 dp->wmap[word] |= cpu_to_le32(ONES << (DBWORD - nb) in dbAllocBits()
2219 dbMaxBud((u8 *) & dp->wmap[word])); in dbAllocBits()
2229 memset(&dp->wmap[word], (int) ONES, nwords * 4); in dbAllocBits()
2238 for (; nwords > 0; nwords -= nw) { in dbAllocBits()
2240 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocBits()
2269 le32_add_cpu(&dp->nfree, -nblocks); in dbAllocBits()
2277 agno = blkno >> bmp->db_agl2size; in dbAllocBits()
2278 if (agno > bmp->db_maxag) in dbAllocBits()
2279 bmp->db_maxag = agno; in dbAllocBits()
2282 bmp->db_agfree[agno] -= nblocks; in dbAllocBits()
2283 bmp->db_nfree -= nblocks; in dbAllocBits()
2302 * bmp - pointer to bmap descriptor
2303 * dp - pointer to dmap to free bits from.
2304 * blkno - starting block number of the bits to be freed.
2305 * nblocks - number of bits to be freed.
2315 dmtree_t *tp = (dmtree_t *) & dp->tree; in dbFreeBits()
2322 dbitno = blkno & (BPERDMAP - 1); in dbFreeBits()
2346 for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) { in dbFreeBits()
2350 wbitno = dbitno & (DBWORD - 1); in dbFreeBits()
2351 nb = min(rembits, DBWORD - wbitno); in dbFreeBits()
2359 dp->wmap[word] &= in dbFreeBits()
2360 cpu_to_le32(~(ONES << (DBWORD - nb) in dbFreeBits()
2366 dbMaxBud((u8 *) & dp->wmap[word])); in dbFreeBits()
2377 memset(&dp->wmap[word], 0, nwords * 4); in dbFreeBits()
2386 for (; nwords > 0; nwords -= nw) { in dbFreeBits()
2413 le32_add_cpu(&dp->nfree, nblocks); in dbFreeBits()
2420 agno = blkno >> bmp->db_agl2size; in dbFreeBits()
2421 bmp->db_nfree += nblocks; in dbFreeBits()
2422 bmp->db_agfree[agno] += nblocks; in dbFreeBits()
2429 if ((bmp->db_agfree[agno] == bmp->db_agsize && agno == bmp->db_maxag) || in dbFreeBits()
2430 (agno == bmp->db_numag - 1 && in dbFreeBits()
2431 bmp->db_agfree[agno] == (bmp-> db_mapsize & (BPERDMAP - 1)))) { in dbFreeBits()
2432 while (bmp->db_maxag > 0) { in dbFreeBits()
2433 bmp->db_maxag -= 1; in dbFreeBits()
2434 if (bmp->db_agfree[bmp->db_maxag] != in dbFreeBits()
2435 bmp->db_agsize) in dbFreeBits()
2439 /* re-establish the allocation group preference if the in dbFreeBits()
2443 if (bmp->db_agpref > bmp->db_maxag) in dbFreeBits()
2444 bmp->db_agpref = bmp->db_maxag; in dbFreeBits()
2458 * maximum string of free blocks (i.e. a change in the root
2460 * or deallocation of a range of blocks with a single dmap.
2478 * bmp - pointer to bmap descriptor
2479 * blkno - the first block of a block range within a dmap. it is
2482 * newval - the new value of the lower level dmap or dmap control
2484 * alloc - 'true' if adjustment is due to an allocation.
2485 * level - current level of dmap control page (i.e. L0, L1, L2) to
2489 * 0 - success
2490 * -EIO - i/o error
2507 lblkno = BLKTOCTL(blkno, bmp->db_l2nbperpage, level); in dbAdjCtl()
2508 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); in dbAdjCtl()
2510 return -EIO; in dbAdjCtl()
2511 dcp = (struct dmapctl *) mp->data; in dbAdjCtl()
2513 if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) { in dbAdjCtl()
2514 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmapctl page\n"); in dbAdjCtl()
2516 return -EIO; in dbAdjCtl()
2522 leafno = BLKTOCTLLEAF(blkno, dcp->budmin); in dbAdjCtl()
2523 ti = leafno + le32_to_cpu(dcp->leafidx); in dbAdjCtl()
2528 oldval = dcp->stree[ti]; in dbAdjCtl()
2529 oldroot = dcp->stree[ROOT]; in dbAdjCtl()
2554 oldval = dcp->stree[ti]; in dbAdjCtl()
2556 dbSplit((dmtree_t *) dcp, leafno, dcp->budmin, newval); in dbAdjCtl()
2570 if (dcp->stree[ROOT] != oldroot) { in dbAdjCtl()
2574 if (level < bmp->db_maxlevel) { in dbAdjCtl()
2579 dbAdjCtl(bmp, blkno, dcp->stree[ROOT], alloc, in dbAdjCtl()
2595 if (dcp->stree[ti] == NOFREE) in dbAdjCtl()
2599 dcp->budmin, oldval); in dbAdjCtl()
2612 assert(level == bmp->db_maxlevel); in dbAdjCtl()
2613 if (bmp->db_maxfreebud != oldroot) { in dbAdjCtl()
2614 jfs_error(bmp->db_ipbmap->i_sb, in dbAdjCtl()
2617 bmp->db_maxfreebud = dcp->stree[ROOT]; in dbAdjCtl()
2637 * tp - pointer to the tree containing the leaf.
2638 * leafno - the number of the leaf to be updated.
2639 * splitsz - the size the binary buddy system starting at the leaf
2640 * must be split to, specified as the log2 number of blocks.
2641 * newval - the new value for the leaf.
2651 s8 *leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx); in dbSplit()
2655 if (leaf[leafno] > tp->dmt_budmin) { in dbSplit()
2659 * - 1 in l2) and the corresponding buddy size. in dbSplit()
2661 cursz = leaf[leafno] - 1; in dbSplit()
2662 budsz = BUDSIZE(cursz, tp->dmt_budmin); in dbSplit()
2673 cursz -= 1; in dbSplit()
2705 * tp - pointer to the tree containing the leaf.
2706 * leafno - the number of the leaf to be updated.
2716 s8 *leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx); in dbBackSplit()
2731 LITOL2BSZ(leafno, le32_to_cpu(tp->dmt_l2nleafs), in dbBackSplit()
2732 tp->dmt_budmin); in dbBackSplit()
2738 budsz = BUDSIZE(size, tp->dmt_budmin); in dbBackSplit()
2747 if (bsz >= le32_to_cpu(tp->dmt_nleafs)) { in dbBackSplit()
2749 return -EIO; in dbBackSplit()
2762 cursz = leaf[bud] - 1; in dbBackSplit()
2771 return -EIO; in dbBackSplit()
2781 * the leaf with other leaves of the dmtree into a multi-leaf
2785 * tp - pointer to the tree containing the leaf.
2786 * leafno - the number of the leaf to be updated.
2787 * newval - the new value for the leaf.
2798 if (newval >= tp->dmt_budmin) { in dbJoin()
2801 leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx); in dbJoin()
2816 budsz = BUDSIZE(newval, tp->dmt_budmin); in dbJoin()
2820 while (budsz < le32_to_cpu(tp->dmt_nleafs)) { in dbJoin()
2833 return -EIO; in dbJoin()
2836 * the left buddy gets to claim the blocks resulting in dbJoin()
2879 * tp - pointer to the tree to be adjusted.
2880 * leafno - the number of the leaf to be updated.
2881 * newval - the new value for the leaf.
2892 lp = leafno + le32_to_cpu(tp->dmt_leafidx); in dbAdjTree()
2897 if (tp->dmt_stree[lp] == newval) in dbAdjTree()
2902 tp->dmt_stree[lp] = newval; in dbAdjTree()
2906 for (k = 0; k < le32_to_cpu(tp->dmt_height); k++) { in dbAdjTree()
2910 lp = ((lp - 1) & ~0x03) + 1; in dbAdjTree()
2914 pp = (lp - 1) >> 2; in dbAdjTree()
2918 max = TREEMAX(&tp->dmt_stree[lp]); in dbAdjTree()
2923 if (tp->dmt_stree[pp] == max) in dbAdjTree()
2928 tp->dmt_stree[pp] = max; in dbAdjTree()
2930 /* parent becomes leaf for next go-round. in dbAdjTree()
2940 * FUNCTION: search a dmtree_t for sufficient free blocks, returning
2941 * the index of a leaf describing the free blocks if
2942 * sufficient free blocks are found.
2949 * tp - pointer to the tree to be searched.
2950 * l2nb - log2 number of free blocks to search for.
2951 * leafidx - return pointer to be set to the index of the leaf
2952 * describing at least l2nb free blocks if sufficient
2953 * free blocks are found.
2956 * 0 - success
2957 * -ENOSPC - insufficient free blocks.
2966 if (l2nb > tp->dmt_stree[ROOT]) in dbFindLeaf()
2967 return -ENOSPC; in dbFindLeaf()
2973 for (k = le32_to_cpu(tp->dmt_height), ti = 1; in dbFindLeaf()
2974 k > 0; k--, ti = ((ti + n) << 2) + 1) { in dbFindLeaf()
2982 if (l2nb <= tp->dmt_stree[x + n]) in dbFindLeaf()
2995 *leafidx = x + n - le32_to_cpu(tp->dmt_leafidx); in dbFindLeaf()
3011 * word - dmap bitmap word value.
3012 * l2nb - number of free bits specified as a log2 number.
3031 mask = ONES << (DBWORD - nb); in dbFindBits()
3052 * bits within 32-bits of the map.
3055 * cp - pointer to the 32-bit value.
3071 * free buddy size is BUDMIN-1. in dbMaxBud()
3074 return (BUDMIN - 1); in dbMaxBud()
3088 * FUNCTION: determine the number of trailing zeros within a 32-bit
3092 * value - 32-bit value to be examined.
3113 * FUNCTION: determine the number of leading zeros within a 32-bit
3117 * value - 32-bit value to be examined.
3142 * nb - number of blocks
3145 * log2 number of blocks
3152 mask = (s64) 1 << (64 - 1); in blkstol2()
3162 l2nb = (64 - 1) - l2nb; in blkstol2()
3183 * the blocks will be alloc from the working map one dmap
3187 * ip - pointer to in-core inode;
3188 * blkno - starting block number to be freed.
3189 * nblocks - number of blocks to be freed.
3192 * 0 - success
3193 * -EIO - i/o error
3195 int dbAllocBottomUp(struct inode *ip, s64 blkno, s64 nblocks) in dbAllocBottomUp() argument
3201 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap; in dbAllocBottomUp()
3202 struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap; in dbAllocBottomUp()
3207 ASSERT(nblocks <= bmp->db_mapsize - blkno); in dbAllocBottomUp()
3210 * allocate the blocks a dmap at a time. in dbAllocBottomUp()
3213 for (rem = nblocks; rem > 0; rem -= nb, blkno += nb) { in dbAllocBottomUp()
3220 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); in dbAllocBottomUp()
3224 return -EIO; in dbAllocBottomUp()
3226 dp = (struct dmap *) mp->data; in dbAllocBottomUp()
3228 /* determine the number of blocks to be allocated from in dbAllocBottomUp()
3231 nb = min(rem, BPERDMAP - (blkno & (BPERDMAP - 1))); in dbAllocBottomUp()
3233 /* allocate the blocks. */ in dbAllocBottomUp()
3256 struct dmaptree *tp = (struct dmaptree *) & dp->tree; in dbAllocDmapBU()
3261 oldroot = tp->stree[ROOT]; in dbAllocDmapBU()
3266 dbitno = blkno & (BPERDMAP - 1); in dbAllocDmapBU()
3285 for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) { in dbAllocDmapBU()
3289 wbitno = dbitno & (DBWORD - 1); in dbAllocDmapBU()
3290 nb = min(rembits, DBWORD - wbitno); in dbAllocDmapBU()
3298 dp->wmap[word] |= cpu_to_le32(ONES << (DBWORD - nb) in dbAllocDmapBU()
3309 memset(&dp->wmap[word], (int) ONES, nwords * 4); in dbAllocDmapBU()
3318 le32_add_cpu(&dp->nfree, -nblocks); in dbAllocDmapBU()
3329 agno = blkno >> bmp->db_agl2size; in dbAllocDmapBU()
3330 if (agno > bmp->db_maxag) in dbAllocDmapBU()
3331 bmp->db_maxag = agno; in dbAllocDmapBU()
3334 bmp->db_agfree[agno] -= nblocks; in dbAllocDmapBU()
3335 bmp->db_nfree -= nblocks; in dbAllocDmapBU()
3340 if (tp->stree[ROOT] == oldroot) in dbAllocDmapBU()
3347 if ((rc = dbAdjCtl(bmp, blkno, tp->stree[ROOT], 1, 0))) in dbAllocDmapBU()
3362 * L1---------------------------------L1
3364 * L0---------L0---------L0 L0---------L0---------L0
3369 * <---old---><----------------------------extend----------------------->
3373 struct jfs_sb_info *sbi = JFS_SBI(ipbmap->i_sb); in dbExtendFS()
3374 int nbperpage = sbi->nbperpage; in dbExtendFS()
3382 struct bmap *bmp = sbi->bmap; in dbExtendFS()
3399 bmp->db_mapsize = newsize; in dbExtendFS()
3400 bmp->db_maxlevel = BMAPSZTOLEV(bmp->db_mapsize); in dbExtendFS()
3404 oldl2agsize = bmp->db_agl2size; in dbExtendFS()
3406 bmp->db_agl2size = l2agsize; in dbExtendFS()
3407 bmp->db_agsize = 1 << l2agsize; in dbExtendFS()
3410 agno = bmp->db_numag; in dbExtendFS()
3411 bmp->db_numag = newsize >> l2agsize; in dbExtendFS()
3412 bmp->db_numag += ((u32) newsize % (u32) bmp->db_agsize) ? 1 : 0; in dbExtendFS()
3419 * i.e., (AGi, ..., AGj) where i = k*n and j = k*(n+1) - 1 to AGn; in dbExtendFS()
3424 k = 1 << (l2agsize - oldl2agsize); in dbExtendFS()
3425 ag_rem = bmp->db_agfree[0]; /* save agfree[0] */ in dbExtendFS()
3427 bmp->db_agfree[n] = 0; /* init collection point */ in dbExtendFS()
3432 bmp->db_agfree[n] += bmp->db_agfree[i]; in dbExtendFS()
3435 bmp->db_agfree[0] += ag_rem; /* restore agfree[0] */ in dbExtendFS()
3438 bmp->db_agfree[n] = 0; in dbExtendFS()
3444 bmp->db_maxag = bmp->db_maxag / k; in dbExtendFS()
3457 jfs_error(ipbmap->i_sb, "L2 page could not be read\n"); in dbExtendFS()
3458 return -EIO; in dbExtendFS()
3460 l2dcp = (struct dmapctl *) l2mp->data; in dbExtendFS()
3464 l2leaf = l2dcp->stree + CTLLEAFIND + k; in dbExtendFS()
3465 p = BLKTOL1(blkno, sbi->l2nbperpage); /* L1 page */ in dbExtendFS()
3473 /* read in L1 page: (blkno & (MAXL1SIZE - 1)) */ in dbExtendFS()
3477 l1dcp = (struct dmapctl *) l1mp->data; in dbExtendFS()
3480 j = (blkno & (MAXL1SIZE - 1)) >> L2MAXL0SIZE; in dbExtendFS()
3481 l1leaf = l1dcp->stree + CTLLEAFIND + j; in dbExtendFS()
3482 p = BLKTOL0(blkno, sbi->l2nbperpage); in dbExtendFS()
3490 l1dcp = (struct dmapctl *) l1mp->data; in dbExtendFS()
3494 l1leaf = l1dcp->stree + CTLLEAFIND; in dbExtendFS()
3504 /* read in L0 page: (blkno & (MAXL0SIZE - 1)) */ in dbExtendFS()
3509 l0dcp = (struct dmapctl *) l0mp->data; in dbExtendFS()
3512 i = (blkno & (MAXL0SIZE - 1)) >> in dbExtendFS()
3514 l0leaf = l0dcp->stree + CTLLEAFIND + i; in dbExtendFS()
3516 sbi->l2nbperpage); in dbExtendFS()
3524 l0dcp = (struct dmapctl *) l0mp->data; in dbExtendFS()
3528 l0leaf = l0dcp->stree + CTLLEAFIND; in dbExtendFS()
3540 if ((n = blkno & (BPERDMAP - 1))) { in dbExtendFS()
3546 n = min(nblocks, (s64)BPERDMAP - n); in dbExtendFS()
3557 dp = (struct dmap *) mp->data; in dbExtendFS()
3560 bmp->db_nfree += n; in dbExtendFS()
3561 agno = le64_to_cpu(dp->start) >> l2agsize; in dbExtendFS()
3562 bmp->db_agfree[agno] += n; in dbExtendFS()
3570 nblocks -= n; in dbExtendFS()
3591 bmp->db_maxfreebud = *l1leaf; in dbExtendFS()
3615 bmp->db_maxfreebud = *l2leaf; in dbExtendFS()
3622 jfs_error(ipbmap->i_sb, "function has not returned as expected\n"); in dbExtendFS()
3629 return -EIO; in dbExtendFS()
3645 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap; in dbFinalizeBmap()
3660 actags = bmp->db_maxag + 1; in dbFinalizeBmap()
3661 inactags = bmp->db_numag - actags; in dbFinalizeBmap()
3662 ag_rem = bmp->db_mapsize & (bmp->db_agsize - 1); /* ??? */ in dbFinalizeBmap()
3664 /* determine how many blocks are in the inactive allocation in dbFinalizeBmap()
3670 ((inactags - 1) << bmp->db_agl2size) + ag_rem in dbFinalizeBmap()
3671 : inactags << bmp->db_agl2size; in dbFinalizeBmap()
3673 /* determine how many free blocks are in the active in dbFinalizeBmap()
3674 * allocation groups plus the average number of free blocks in dbFinalizeBmap()
3677 actfree = bmp->db_nfree - inactfree; in dbFinalizeBmap()
3681 * re-establish the preferred group as the leftmost in dbFinalizeBmap()
3684 if (bmp->db_agfree[bmp->db_agpref] < avgfree) { in dbFinalizeBmap()
3685 for (bmp->db_agpref = 0; bmp->db_agpref < actags; in dbFinalizeBmap()
3686 bmp->db_agpref++) { in dbFinalizeBmap()
3687 if (bmp->db_agfree[bmp->db_agpref] >= avgfree) in dbFinalizeBmap()
3690 if (bmp->db_agpref >= bmp->db_numag) { in dbFinalizeBmap()
3691 jfs_error(ipbmap->i_sb, in dbFinalizeBmap()
3703 bmp->db_aglevel = BMAPSZTOLEV(bmp->db_agsize); in dbFinalizeBmap()
3705 bmp->db_agl2size - (L2BPERDMAP + bmp->db_aglevel * L2LPERCTL); in dbFinalizeBmap()
3706 bmp->db_agheight = l2nl >> 1; in dbFinalizeBmap()
3707 bmp->db_agwidth = 1 << (l2nl - (bmp->db_agheight << 1)); in dbFinalizeBmap()
3708 for (i = 5 - bmp->db_agheight, bmp->db_agstart = 0, n = 1; i > 0; in dbFinalizeBmap()
3709 i--) { in dbFinalizeBmap()
3710 bmp->db_agstart += n; in dbFinalizeBmap()
3721 * for the specified number of blocks:
3724 * The number of blocks will only account for the actually
3725 * existing blocks. Blocks which don't actually exist in
3729 * dp - pointer to page of map
3730 * nblocks - number of blocks this page
3739 blkno = Blkno & (BPERDMAP - 1); in dbInitDmap()
3742 dp->nblocks = dp->nfree = cpu_to_le32(nblocks); in dbInitDmap()
3743 dp->start = cpu_to_le64(Blkno); in dbInitDmap()
3746 memset(&dp->wmap[0], 0, LPERDMAP * 4); in dbInitDmap()
3747 memset(&dp->pmap[0], 0, LPERDMAP * 4); in dbInitDmap()
3751 le32_add_cpu(&dp->nblocks, nblocks); in dbInitDmap()
3752 le32_add_cpu(&dp->nfree, nblocks); in dbInitDmap()
3763 for (r = nblocks; r > 0; r -= nb, blkno += nb) { in dbInitDmap()
3765 b = blkno & (DBWORD - 1); in dbInitDmap()
3767 nb = min(r, DBWORD - b); in dbInitDmap()
3772 dp->wmap[w] &= cpu_to_le32(~(ONES << (DBWORD - nb) in dbInitDmap()
3774 dp->pmap[w] &= cpu_to_le32(~(ONES << (DBWORD - nb) in dbInitDmap()
3782 memset(&dp->wmap[w], 0, nw * 4); in dbInitDmap()
3783 memset(&dp->pmap[w], 0, nw * 4); in dbInitDmap()
3792 * mark bits following the range to be freed (non-existing in dbInitDmap()
3793 * blocks) as allocated (ONES) in dbInitDmap()
3799 /* the first word beyond the end of existing blocks */ in dbInitDmap()
3802 /* does nblocks fall on a 32-bit boundary ? */ in dbInitDmap()
3803 b = blkno & (DBWORD - 1); in dbInitDmap()
3806 dp->wmap[w] = dp->pmap[w] = cpu_to_le32(ONES >> b); in dbInitDmap()
3812 dp->pmap[i] = dp->wmap[i] = cpu_to_le32(ONES); in dbInitDmap()
3830 * dp - dmap to complete
3831 * blkno - starting block number for this dmap
3832 * treemax - will be filled in with max free for this dmap
3843 tp = &dp->tree; in dbInitDmapTree()
3844 tp->nleafs = cpu_to_le32(LPERDMAP); in dbInitDmapTree()
3845 tp->l2nleafs = cpu_to_le32(L2LPERDMAP); in dbInitDmapTree()
3846 tp->leafidx = cpu_to_le32(LEAFIND); in dbInitDmapTree()
3847 tp->height = cpu_to_le32(4); in dbInitDmapTree()
3848 tp->budmin = BUDMIN; in dbInitDmapTree()
3851 * note: leaf is set to NOFREE(-1) if all blocks of corresponding in dbInitDmapTree()
3854 cp = tp->stree + le32_to_cpu(tp->leafidx); in dbInitDmapTree()
3856 *cp++ = dbMaxBud((u8 *) & dp->wmap[i]); in dbInitDmapTree()
3875 * cp - Pointer to the root of the tree
3876 * l2leaves- Number of leaf nodes as a power of 2
3877 * l2min - Number of blocks that can be covered by a leaf
3888 tp = dtp->stree; in dbInitTree()
3891 l2max = le32_to_cpu(dtp->l2nleafs) + dtp->budmin; in dbInitTree()
3899 * the combination will result in the left-most buddy leaf having in dbInitTree()
3907 for (l2free = dtp->budmin, bsize = 1; l2free < l2max; in dbInitTree()
3913 for (i = 0, cp = tp + le32_to_cpu(dtp->leafidx); in dbInitTree()
3914 i < le32_to_cpu(dtp->nleafs); in dbInitTree()
3919 *(cp + bsize) = -1; /* right give left */ in dbInitTree()
3934 for (child = le32_to_cpu(dtp->leafidx), in dbInitTree()
3935 nparent = le32_to_cpu(dtp->nleafs) >> 2; in dbInitTree()
3938 parent = (child - 1) >> 2; in dbInitTree()
3961 dcp->nleafs = cpu_to_le32(LPERCTL); in dbInitDmapCtl()
3962 dcp->l2nleafs = cpu_to_le32(L2LPERCTL); in dbInitDmapCtl()
3963 dcp->leafidx = cpu_to_le32(CTLLEAFIND); in dbInitDmapCtl()
3964 dcp->height = cpu_to_le32(5); in dbInitDmapCtl()
3965 dcp->budmin = L2BPERDMAP + L2LPERCTL * level; in dbInitDmapCtl()
3972 cp = &dcp->stree[CTLLEAFIND + i]; in dbInitDmapCtl()
3987 * nblocks - Number of blocks in aggregate
3989 * RETURNS: log2(allocation group size) in aggregate blocks
4001 m = ((u64) 1 << (64 - 1)); in dbGetL2AGSize()
4002 for (l2sz = 64; l2sz >= 0; l2sz--, m >>= 1) { in dbGetL2AGSize()
4012 return (l2sz - L2MAXAG); in dbGetL2AGSize()
4019 * FUNCTION: compute number of blocks the block allocation map file
4022 * RETURNS: Number of blocks which can be covered by this block map file;
4040 struct super_block *sb = ipbmap->i_sb; in dbMapFileSizeToMapSize()
4046 nblocks = ipbmap->i_size >> JFS_SBI(sb)->l2bsize; in dbMapFileSizeToMapSize()
4047 npages = nblocks >> JFS_SBI(sb)->l2nbperpage; in dbMapFileSizeToMapSize()
4055 npages--; /* skip the first global control page */ in dbMapFileSizeToMapSize()
4057 npages -= (2 - level); in dbMapFileSizeToMapSize()
4058 npages--; /* skip top level's control page */ in dbMapFileSizeToMapSize()
4059 for (i = level; i >= 0; i--) { in dbMapFileSizeToMapSize()
4069 npages--; in dbMapFileSizeToMapSize()
4072 /* convert the number of dmaps into the number of blocks in dbMapFileSizeToMapSize()