Lines Matching +full:max +full:- +full:bits +full:- +full:per +full:- +full:word
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)
88 static int dbFindBits(u32 word, int l2nb);
99 static int cnttz(u32 word);
115 * binary buddy of free bits within the character.
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
151 * -EINVAL - wrong bmap data
161 * allocate/initialize the in-memory bmap descriptor in dbMount()
163 /* allocate memory for the in-memory bmap descriptor */ in dbMount()
166 return -ENOMEM; in dbMount()
168 /* read the on-disk bmap descriptor. */ in dbMount()
170 BMAPBLKNO << JFS_SBI(ipbmap->i_sb)->l2nbperpage, in dbMount()
173 err = -EIO; in dbMount()
177 /* copy the on-disk bmap descriptor to its in-memory version. */ in dbMount()
178 dbmp_le = (struct dbmap_disk *) mp->data; in dbMount()
179 bmp->db_mapsize = le64_to_cpu(dbmp_le->dn_mapsize); in dbMount()
180 bmp->db_nfree = le64_to_cpu(dbmp_le->dn_nfree); in dbMount()
182 bmp->db_l2nbperpage = le32_to_cpu(dbmp_le->dn_l2nbperpage); in dbMount()
183 if (bmp->db_l2nbperpage > L2PSIZE - L2MINBLOCKSIZE) { in dbMount()
184 err = -EINVAL; in dbMount()
188 bmp->db_numag = le32_to_cpu(dbmp_le->dn_numag); in dbMount()
189 if (!bmp->db_numag) { in dbMount()
190 err = -EINVAL; in dbMount()
194 bmp->db_maxlevel = le32_to_cpu(dbmp_le->dn_maxlevel); in dbMount()
195 bmp->db_maxag = le32_to_cpu(dbmp_le->dn_maxag); in dbMount()
196 bmp->db_agpref = le32_to_cpu(dbmp_le->dn_agpref); in dbMount()
197 bmp->db_aglevel = le32_to_cpu(dbmp_le->dn_aglevel); in dbMount()
198 bmp->db_agheight = le32_to_cpu(dbmp_le->dn_agheight); in dbMount()
199 bmp->db_agwidth = le32_to_cpu(dbmp_le->dn_agwidth); in dbMount()
200 bmp->db_agstart = le32_to_cpu(dbmp_le->dn_agstart); in dbMount()
201 bmp->db_agl2size = le32_to_cpu(dbmp_le->dn_agl2size); in dbMount()
202 if (bmp->db_agl2size > L2MAXL2SIZE - L2MAXAG || in dbMount()
203 bmp->db_agl2size < 0) { in dbMount()
204 err = -EINVAL; in dbMount()
208 if (((bmp->db_mapsize - 1) >> bmp->db_agl2size) > MAXAG) { in dbMount()
209 err = -EINVAL; in dbMount()
214 bmp->db_agfree[i] = le64_to_cpu(dbmp_le->dn_agfree[i]); in dbMount()
215 bmp->db_agsize = le64_to_cpu(dbmp_le->dn_agsize); in dbMount()
216 bmp->db_maxfreebud = dbmp_le->dn_maxfreebud; in dbMount()
222 bmp->db_ipbmap = ipbmap; in dbMount()
223 JFS_SBI(ipbmap->i_sb)->bmap = bmp; in dbMount()
225 memset(bmp->db_active, 0, sizeof(bmp->db_active)); in dbMount()
248 * the in-core bmap descriptor is written to disk and
252 * ipbmap - pointer to in-core inode for the block map.
255 * 0 - success
256 * -EIO - i/o error
260 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap; in dbUnmount()
268 truncate_inode_pages(ipbmap->i_mapping, 0); in dbUnmount()
270 /* free the memory for the in-memory bmap. */ in dbUnmount()
272 JFS_SBI(ipbmap->i_sb)->bmap = NULL; in dbUnmount()
283 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap; in dbSync()
290 /* get the buffer for the on-disk bmap descriptor. */ in dbSync()
292 BMAPBLKNO << JFS_SBI(ipbmap->i_sb)->l2nbperpage, in dbSync()
296 return -EIO; in dbSync()
298 /* copy the in-memory version of the bmap to the on-disk version */ in dbSync()
299 dbmp_le = (struct dbmap_disk *) mp->data; in dbSync()
300 dbmp_le->dn_mapsize = cpu_to_le64(bmp->db_mapsize); in dbSync()
301 dbmp_le->dn_nfree = cpu_to_le64(bmp->db_nfree); in dbSync()
302 dbmp_le->dn_l2nbperpage = cpu_to_le32(bmp->db_l2nbperpage); in dbSync()
303 dbmp_le->dn_numag = cpu_to_le32(bmp->db_numag); in dbSync()
304 dbmp_le->dn_maxlevel = cpu_to_le32(bmp->db_maxlevel); in dbSync()
305 dbmp_le->dn_maxag = cpu_to_le32(bmp->db_maxag); in dbSync()
306 dbmp_le->dn_agpref = cpu_to_le32(bmp->db_agpref); in dbSync()
307 dbmp_le->dn_aglevel = cpu_to_le32(bmp->db_aglevel); in dbSync()
308 dbmp_le->dn_agheight = cpu_to_le32(bmp->db_agheight); in dbSync()
309 dbmp_le->dn_agwidth = cpu_to_le32(bmp->db_agwidth); in dbSync()
310 dbmp_le->dn_agstart = cpu_to_le32(bmp->db_agstart); in dbSync()
311 dbmp_le->dn_agl2size = cpu_to_le32(bmp->db_agl2size); in dbSync()
313 dbmp_le->dn_agfree[i] = cpu_to_le64(bmp->db_agfree[i]); in dbSync()
314 dbmp_le->dn_agsize = cpu_to_le64(bmp->db_agsize); in dbSync()
315 dbmp_le->dn_maxfreebud = bmp->db_maxfreebud; in dbSync()
323 filemap_write_and_wait(ipbmap->i_mapping); in dbSync()
340 * ip - pointer to in-core inode;
341 * blkno - starting block number to be freed.
342 * nblocks - number of blocks to be freed.
345 * 0 - success
346 * -EIO - i/o error
354 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap; in dbFree()
355 struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap; in dbFree()
356 struct super_block *sb = ipbmap->i_sb; in dbFree()
361 if (unlikely((blkno == 0) || (blkno + nblocks > bmp->db_mapsize))) { in dbFree()
366 jfs_error(ip->i_sb, "block to be freed is outside the map\n"); in dbFree()
367 return -EIO; in dbFree()
373 if (JFS_SBI(sb)->flag & JFS_DISCARD) in dbFree()
374 if (JFS_SBI(sb)->minblks_trim <= nblocks) in dbFree()
381 for (rem = nblocks; rem > 0; rem -= nb, blkno += nb) { in dbFree()
388 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); in dbFree()
392 return -EIO; in dbFree()
394 dp = (struct dmap *) mp->data; in dbFree()
399 nb = min(rem, BPERDMAP - (blkno & (BPERDMAP - 1))); in dbFree()
403 jfs_error(ip->i_sb, "error in block map\n"); in dbFree()
430 * ipbmap - pointer to in-core inode for the block map.
431 * free - 'true' if block range is to be freed from the persistent
433 * blkno - starting block number of the range.
434 * nblocks - number of contiguous blocks in the range.
435 * tblk - transaction block;
438 * 0 - success
439 * -EIO - i/o error
446 int word, nbits, nwords; in dbUpdatePMap() local
447 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap; in dbUpdatePMap()
457 if (blkno + nblocks > bmp->db_mapsize) { in dbUpdatePMap()
461 jfs_error(ipbmap->i_sb, "blocks are outside the map\n"); in dbUpdatePMap()
462 return -EIO; in dbUpdatePMap()
466 lsn = tblk->lsn; in dbUpdatePMap()
467 log = (struct jfs_log *) JFS_SBI(tblk->sb)->log; in dbUpdatePMap()
475 for (rem = nblocks; rem > 0; rem -= nblks, blkno += nblks) { in dbUpdatePMap()
477 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); in dbUpdatePMap()
483 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, in dbUpdatePMap()
486 return -EIO; in dbUpdatePMap()
489 dp = (struct dmap *) mp->data; in dbUpdatePMap()
491 /* determine the bit number and word within the dmap of in dbUpdatePMap()
495 dbitno = blkno & (BPERDMAP - 1); in dbUpdatePMap()
496 word = dbitno >> L2DBWORD; in dbUpdatePMap()
497 nblks = min(rem, (s64)BPERDMAP - dbitno); in dbUpdatePMap()
499 /* update the bits of the dmap words. the first and last in dbUpdatePMap()
500 * words may only have a subset of their bits updated. if in dbUpdatePMap()
501 * this is the case, we'll work against that word (i.e. in dbUpdatePMap()
504 * are to have all their bits updated. in dbUpdatePMap()
507 rbits -= nbits, dbitno += nbits) { in dbUpdatePMap()
508 /* determine the bit number within the word and in dbUpdatePMap()
509 * the number of bits within the word. in dbUpdatePMap()
511 wbitno = dbitno & (DBWORD - 1); in dbUpdatePMap()
512 nbits = min(rbits, DBWORD - wbitno); in dbUpdatePMap()
514 /* check if only part of the word is to be updated. */ in dbUpdatePMap()
516 /* update (free or allocate) the bits in dbUpdatePMap()
517 * in this word. in dbUpdatePMap()
520 (ONES << (DBWORD - nbits) >> wbitno); in dbUpdatePMap()
522 dp->pmap[word] &= in dbUpdatePMap()
525 dp->pmap[word] |= in dbUpdatePMap()
528 word += 1; in dbUpdatePMap()
531 * their bits updated. determine how in dbUpdatePMap()
532 * many words and how many bits. in dbUpdatePMap()
537 /* update (free or allocate) the bits in dbUpdatePMap()
541 memset(&dp->pmap[word], 0, in dbUpdatePMap()
544 memset(&dp->pmap[word], (int) ONES, in dbUpdatePMap()
547 word += nwords; in dbUpdatePMap()
560 if (mp->lsn != 0) { in dbUpdatePMap()
562 logdiff(diffp, mp->lsn, log); in dbUpdatePMap()
564 mp->lsn = lsn; in dbUpdatePMap()
567 list_move(&mp->synclist, &tblk->synclist); in dbUpdatePMap()
571 logdiff(difft, tblk->clsn, log); in dbUpdatePMap()
572 logdiff(diffp, mp->clsn, log); in dbUpdatePMap()
574 mp->clsn = tblk->clsn; in dbUpdatePMap()
576 mp->log = log; in dbUpdatePMap()
577 mp->lsn = lsn; in dbUpdatePMap()
580 log->count++; in dbUpdatePMap()
581 list_add(&mp->synclist, &tblk->synclist); in dbUpdatePMap()
583 mp->clsn = tblk->clsn; in dbUpdatePMap()
605 * new inode allocation towards. The tie-in between inode
616 * ipbmap - pointer to in-core inode for the block map.
627 int next_best = -1; in dbNextAG()
628 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap; in dbNextAG()
633 avgfree = (u32)bmp->db_nfree / bmp->db_numag; in dbNextAG()
639 agpref = bmp->db_agpref; in dbNextAG()
640 if ((atomic_read(&bmp->db_active[agpref]) == 0) && in dbNextAG()
641 (bmp->db_agfree[agpref] >= avgfree)) in dbNextAG()
647 for (i = 0 ; i < bmp->db_numag; i++, agpref++) { in dbNextAG()
648 if (agpref == bmp->db_numag) in dbNextAG()
651 if (atomic_read(&bmp->db_active[agpref])) in dbNextAG()
654 if (bmp->db_agfree[agpref] >= avgfree) { in dbNextAG()
656 bmp->db_agpref = agpref; in dbNextAG()
658 } else if (bmp->db_agfree[agpref] > hwm) { in dbNextAG()
660 hwm = bmp->db_agfree[agpref]; in dbNextAG()
669 if (next_best != -1) in dbNextAG()
670 bmp->db_agpref = next_best; in dbNextAG()
677 return (bmp->db_agpref); in dbNextAG()
686 * the block allocation policy uses hints and a multi-step
690 * per dmap, we first try to allocate the new blocks
707 * ip - pointer to in-core inode;
708 * hint - allocation hint.
709 * nblocks - number of contiguous blocks in the range.
710 * results - on successful return, set to the starting block number
714 * 0 - success
715 * -ENOSPC - insufficient disk resources
716 * -EIO - i/o error
721 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap; in dbAlloc()
739 bmp = JFS_SBI(ip->i_sb)->bmap; in dbAlloc()
741 mapSize = bmp->db_mapsize; in dbAlloc()
745 jfs_error(ip->i_sb, "the hint is outside the map\n"); in dbAlloc()
746 return -EIO; in dbAlloc()
752 if (l2nb > bmp->db_agl2size) { in dbAlloc()
772 if (blkno >= bmp->db_mapsize) in dbAlloc()
775 agno = blkno >> bmp->db_agl2size; in dbAlloc()
781 if ((blkno & (bmp->db_agsize - 1)) == 0) in dbAlloc()
783 * if so, call dbNextAG() to find a non-busy in dbAlloc()
786 if (atomic_read(&bmp->db_active[agno])) in dbAlloc()
798 rc = -EIO; in dbAlloc()
799 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); in dbAlloc()
804 dp = (struct dmap *) mp->data; in dbAlloc()
810 != -ENOSPC) { in dbAlloc()
820 writers = atomic_read(&bmp->db_active[agno]); in dbAlloc()
822 ((writers == 1) && (JFS_IP(ip)->active_ag != agno))) { in dbAlloc()
837 != -ENOSPC) { in dbAlloc()
849 != -ENOSPC) { in dbAlloc()
865 if ((rc = dbAllocAG(bmp, agno, nblocks, l2nb, results)) != -ENOSPC) in dbAlloc()
881 if ((rc = dbAllocAG(bmp, agno, nblocks, l2nb, results)) == -ENOSPC) in dbAlloc()
911 * ip - pointer to in-core inode requiring allocation.
912 * blkno - starting block of the current allocation.
913 * nblocks - number of contiguous blocks within the current
915 * addnblocks - number of blocks to add to the allocation.
916 * results - on successful return, set to the starting block number
923 * 0 - success
924 * -ENOSPC - insufficient disk resources
925 * -EIO - i/o error
939 if (rc != -ENOSPC) in dbReAlloc()
949 (ip, blkno + nblocks - 1, addnblocks + nblocks, results)); in dbReAlloc()
965 * ip - pointer to in-core inode requiring allocation.
966 * blkno - starting block of the current allocation.
967 * nblocks - number of contiguous blocks within the current
969 * addnblocks - number of blocks to add to the allocation.
972 * 0 - success
973 * -ENOSPC - insufficient disk resources
974 * -EIO - i/o error
978 struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb); in dbExtend()
984 struct inode *ipbmap = sbi->ipbmap; in dbExtend()
988 * We don't want a non-aligned extent to cross a page boundary in dbExtend()
990 if (((rel_block = blkno & (sbi->nbperpage - 1))) && in dbExtend()
991 (rel_block + nblocks + addnblocks > sbi->nbperpage)) in dbExtend()
992 return -ENOSPC; in dbExtend()
995 lastblkno = blkno + nblocks - 1; in dbExtend()
1005 bmp = sbi->bmap; in dbExtend()
1006 if (lastblkno < 0 || lastblkno >= bmp->db_mapsize) { in dbExtend()
1008 jfs_error(ip->i_sb, "the block is outside the filesystem\n"); in dbExtend()
1009 return -EIO; in dbExtend()
1020 if (addnblocks > BPERDMAP || extblkno >= bmp->db_mapsize || in dbExtend()
1021 (extblkno & (bmp->db_agsize - 1)) == 0) { in dbExtend()
1023 return -ENOSPC; in dbExtend()
1029 lblkno = BLKTODMAP(extblkno, bmp->db_l2nbperpage); in dbExtend()
1033 return -EIO; in dbExtend()
1036 dp = (struct dmap *) mp->data; in dbExtend()
1063 * bmp - pointer to bmap descriptor
1064 * dp - pointer to dmap.
1065 * blkno - starting block number of the range.
1066 * nblocks - number of contiguous free blocks of the range.
1069 * 0 - success
1070 * -ENOSPC - insufficient disk resources
1071 * -EIO - i/o error
1078 int dbitno, word, rembits, nb, nwords, wbitno, nw; in dbAllocNext() local
1083 if (dp->tree.leafidx != cpu_to_le32(LEAFIND)) { in dbAllocNext()
1084 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmap page\n"); in dbAllocNext()
1085 return -EIO; in dbAllocNext()
1090 leaf = dp->tree.stree + le32_to_cpu(dp->tree.leafidx); in dbAllocNext()
1092 /* determine the bit number and word within the dmap of the in dbAllocNext()
1095 dbitno = blkno & (BPERDMAP - 1); in dbAllocNext()
1096 word = dbitno >> L2DBWORD; in dbAllocNext()
1102 return -ENOSPC; in dbAllocNext()
1107 if (leaf[word] == NOFREE) in dbAllocNext()
1108 return -ENOSPC; in dbAllocNext()
1111 * if the block range is free. not all bits of the first and in dbAllocNext()
1115 * the actual bits to determine if they are free. a single pass in dbAllocNext()
1123 for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) { in dbAllocNext()
1124 /* determine the bit number within the word and in dbAllocNext()
1125 * the number of bits within the word. in dbAllocNext()
1127 wbitno = dbitno & (DBWORD - 1); in dbAllocNext()
1128 nb = min(rembits, DBWORD - wbitno); in dbAllocNext()
1130 /* check if only part of the word is to be examined. in dbAllocNext()
1133 /* check if the bits are free. in dbAllocNext()
1135 mask = (ONES << (DBWORD - nb) >> wbitno); in dbAllocNext()
1136 if ((mask & ~le32_to_cpu(dp->wmap[word])) != mask) in dbAllocNext()
1137 return -ENOSPC; in dbAllocNext()
1139 word += 1; in dbAllocNext()
1143 * words and how many bits. in dbAllocNext()
1154 if (leaf[word] < BUDMIN) in dbAllocNext()
1155 return -ENOSPC; in dbAllocNext()
1157 /* determine the l2 number of bits provided in dbAllocNext()
1161 min_t(int, leaf[word], NLSTOL2BSZ(nwords)); in dbAllocNext()
1167 nwords -= nw; in dbAllocNext()
1168 word += nw; in dbAllocNext()
1191 * bmp - pointer to bmap descriptor
1192 * dp - pointer to dmap.
1193 * blkno - block number to allocate near.
1194 * nblocks - actual number of contiguous free blocks desired.
1195 * l2nb - log2 number of contiguous free blocks desired.
1196 * results - on successful return, set to the starting block number
1200 * 0 - success
1201 * -ENOSPC - insufficient disk resources
1202 * -EIO - i/o error
1210 int word, lword, rc; in dbAllocNear() local
1213 if (dp->tree.leafidx != cpu_to_le32(LEAFIND)) { in dbAllocNear()
1214 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmap page\n"); in dbAllocNear()
1215 return -EIO; in dbAllocNear()
1218 leaf = dp->tree.stree + le32_to_cpu(dp->tree.leafidx); in dbAllocNear()
1220 /* determine the word within the dmap that holds the hint in dbAllocNear()
1221 * (i.e. blkno). also, determine the last word in the dmap in dbAllocNear()
1224 word = (blkno & (BPERDMAP - 1)) >> L2DBWORD; in dbAllocNear()
1225 lword = min(word + 4, LPERDMAP); in dbAllocNear()
1229 for (; word < lword; word++) { in dbAllocNear()
1232 if (leaf[word] < l2nb) in dbAllocNear()
1236 * of the first block described by this dmap word. in dbAllocNear()
1238 blkno = le64_to_cpu(dp->start) + (word << L2DBWORD); in dbAllocNear()
1240 /* if not all bits of the dmap word are free, get the in dbAllocNear()
1241 * starting bit number within the dmap word of the required in dbAllocNear()
1242 * string of free bits and adjust the block number with the in dbAllocNear()
1245 if (leaf[word] < BUDMIN) in dbAllocNear()
1247 dbFindBits(le32_to_cpu(dp->wmap[word]), l2nb); in dbAllocNear()
1257 return -ENOSPC; in dbAllocNear()
1268 * of blocks per dmap, the dmap control pages will be used to
1278 * or two sub-trees, depending on the allocation group size.
1301 * bmp - pointer to bmap descriptor
1302 * agno - allocation group number.
1303 * nblocks - actual number of contiguous free blocks desired.
1304 * l2nb - log2 number of contiguous free blocks desired.
1305 * results - on successful return, set to the starting block number
1309 * 0 - success
1310 * -ENOSPC - insufficient disk resources
1311 * -EIO - i/o error
1327 if (l2nb > bmp->db_agl2size) { in dbAllocAG()
1328 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocAG()
1330 return -EIO; in dbAllocAG()
1336 blkno = (s64) agno << bmp->db_agl2size; in dbAllocAG()
1355 if (bmp->db_agsize == BPERDMAP in dbAllocAG()
1356 || bmp->db_agfree[agno] == bmp->db_agsize) { in dbAllocAG()
1358 if ((rc == -ENOSPC) && in dbAllocAG()
1359 (bmp->db_agfree[agno] == bmp->db_agsize)) { in dbAllocAG()
1363 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocAG()
1372 lblkno = BLKTOCTL(blkno, bmp->db_l2nbperpage, bmp->db_aglevel); in dbAllocAG()
1373 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); in dbAllocAG()
1375 return -EIO; in dbAllocAG()
1376 dcp = (struct dmapctl *) mp->data; in dbAllocAG()
1377 budmin = dcp->budmin; in dbAllocAG()
1379 if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) { in dbAllocAG()
1380 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmapctl page\n"); in dbAllocAG()
1382 return -EIO; in dbAllocAG()
1393 (1 << (L2LPERCTL - (bmp->db_agheight << 1))) / bmp->db_agwidth; in dbAllocAG()
1394 ti = bmp->db_agstart + bmp->db_agwidth * (agno & (agperlev - 1)); in dbAllocAG()
1396 /* dmap control page trees fan-out by 4 and a single allocation in dbAllocAG()
1402 for (i = 0; i < bmp->db_agwidth; i++, ti++) { in dbAllocAG()
1405 if (l2nb > dcp->stree[ti]) in dbAllocAG()
1412 for (k = bmp->db_agheight; k > 0; k--) { in dbAllocAG()
1414 if (l2nb <= dcp->stree[m + n]) { in dbAllocAG()
1420 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocAG()
1423 return -EIO; in dbAllocAG()
1430 if (bmp->db_aglevel == 2) in dbAllocAG()
1432 else if (bmp->db_aglevel == 1) in dbAllocAG()
1433 blkno &= ~(MAXL1SIZE - 1); in dbAllocAG()
1434 else /* bmp->db_aglevel == 0 */ in dbAllocAG()
1435 blkno &= ~(MAXL0SIZE - 1); in dbAllocAG()
1438 ((s64) (ti - le32_to_cpu(dcp->leafidx))) << budmin; in dbAllocAG()
1457 dbFindCtl(bmp, l2nb, bmp->db_aglevel - 1, in dbAllocAG()
1459 if (rc == -ENOSPC) { in dbAllocAG()
1460 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocAG()
1462 return -EIO; in dbAllocAG()
1471 if (rc == -ENOSPC) { in dbAllocAG()
1472 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocAG()
1474 rc = -EIO; in dbAllocAG()
1480 * return -ENOSPC. in dbAllocAG()
1484 return -ENOSPC; in dbAllocAG()
1501 * bmp - pointer to bmap descriptor
1502 * nblocks - actual number of contiguous free blocks desired.
1503 * l2nb - log2 number of contiguous free blocks desired.
1504 * results - on successful return, set to the starting block number
1508 * 0 - success
1509 * -ENOSPC - insufficient disk resources
1510 * -EIO - i/o error
1525 if ((rc = dbFindCtl(bmp, l2nb, bmp->db_maxlevel, &blkno))) in dbAllocAny()
1531 if (rc == -ENOSPC) { in dbAllocAny()
1532 jfs_error(bmp->db_ipbmap->i_sb, "unable to allocate blocks\n"); in dbAllocAny()
1533 return -EIO; in dbAllocAny()
1551 * - we work only on one ag at some time, minimizing how long we
1553 * - reading / writing the fs is possible most time, even on
1557 * - we write two times to the dmapctl and dmap pages
1558 * - but for me, this seems the best way, better ideas?
1562 * ip - pointer to in-core inode
1563 * agno - ag to trim
1564 * minlen - minimum value of contiguous blocks
1567 * s64 - actual number of blocks trimmed
1571 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap; in dbDiscardAG()
1572 struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap; in dbDiscardAG()
1576 struct super_block *sb = ipbmap->i_sb; in dbDiscardAG()
1583 /* max blkno / nblocks pairs to trim */ in dbDiscardAG()
1590 nblocks = bmp->db_agfree[agno]; in dbDiscardAG()
1596 jfs_error(bmp->db_ipbmap->i_sb, "no memory for trim array\n"); in dbDiscardAG()
1605 /* 0 = okay, -EIO = fatal, -ENOSPC -> try smaller block */ in dbDiscardAG()
1608 tt->blkno = blkno; in dbDiscardAG()
1609 tt->nblocks = nblocks; in dbDiscardAG()
1613 if (bmp->db_agfree[agno] == 0) in dbDiscardAG()
1617 nblocks = bmp->db_agfree[agno]; in dbDiscardAG()
1619 } else if (rc == -ENOSPC) { in dbDiscardAG()
1621 l2nb = BLKSTOL2(nblocks) - 1; in dbDiscardAG()
1625 jfs_error(bmp->db_ipbmap->i_sb, "-EIO\n"); in dbDiscardAG()
1630 if (unlikely(count >= range_cnt - 1)) in dbDiscardAG()
1635 tt->nblocks = 0; /* mark the current end */ in dbDiscardAG()
1636 for (tt = totrim; tt->nblocks != 0; tt++) { in dbDiscardAG()
1639 if (!(JFS_SBI(sb)->flag & JFS_DISCARD)) in dbDiscardAG()
1640 jfs_issue_discard(ip, tt->blkno, tt->nblocks); in dbDiscardAG()
1641 dbFree(ip, tt->blkno, tt->nblocks); in dbDiscardAG()
1642 trimmed += tt->nblocks; in dbDiscardAG()
1663 * bmp - pointer to bmap descriptor
1664 * level - starting dmap control page level.
1665 * l2nb - log2 number of contiguous free blocks desired.
1666 * *blkno - on entry, starting block number for conducting the search.
1671 * 0 - success
1672 * -ENOSPC - insufficient disk resources
1673 * -EIO - i/o error
1690 for (lev = level, b = *blkno; lev >= 0; lev--) { in dbFindCtl()
1694 lblkno = BLKTOCTL(b, bmp->db_l2nbperpage, lev); in dbFindCtl()
1695 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); in dbFindCtl()
1697 return -EIO; in dbFindCtl()
1698 dcp = (struct dmapctl *) mp->data; in dbFindCtl()
1699 budmin = dcp->budmin; in dbFindCtl()
1701 if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) { in dbFindCtl()
1702 jfs_error(bmp->db_ipbmap->i_sb, in dbFindCtl()
1705 return -EIO; in dbFindCtl()
1723 jfs_error(bmp->db_ipbmap->i_sb, in dbFindCtl()
1725 return -EIO; in dbFindCtl()
1727 return -ENOSPC; in dbFindCtl()
1768 * group whose size is equal to the number of blocks per dmap.
1780 * bmp - pointer to bmap descriptor
1781 * nblocks - actual number of contiguous free blocks to allocate.
1782 * l2nb - log2 number of contiguous free blocks to allocate.
1783 * blkno - starting block number of the dmap to start the allocation
1785 * results - on successful return, set to the starting block number
1789 * 0 - success
1790 * -ENOSPC - insufficient disk resources
1791 * -EIO - i/o error
1808 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); in dbAllocCtl()
1809 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); in dbAllocCtl()
1811 return -EIO; in dbAllocCtl()
1812 dp = (struct dmap *) mp->data; in dbAllocCtl()
1828 assert((blkno & (BPERDMAP - 1)) == 0); in dbAllocCtl()
1832 for (n = nblocks, b = blkno; n > 0; n -= nb, b += nb) { in dbAllocCtl()
1835 lblkno = BLKTODMAP(b, bmp->db_l2nbperpage); in dbAllocCtl()
1836 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); in dbAllocCtl()
1838 rc = -EIO; in dbAllocCtl()
1841 dp = (struct dmap *) mp->data; in dbAllocCtl()
1845 if (dp->tree.stree[ROOT] != L2BPERDMAP) { in dbAllocCtl()
1847 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocCtl()
1849 rc = -EIO; in dbAllocCtl()
1884 for (n = nblocks - n, b = blkno; n > 0; in dbAllocCtl()
1885 n -= BPERDMAP, b += BPERDMAP) { in dbAllocCtl()
1888 lblkno = BLKTODMAP(b, bmp->db_l2nbperpage); in dbAllocCtl()
1889 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); in dbAllocCtl()
1894 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocCtl()
1898 dp = (struct dmap *) mp->data; in dbAllocCtl()
1907 jfs_error(bmp->db_ipbmap->i_sb, "Block Leakage\n"); in dbAllocCtl()
1931 * mp - pointer to bmap descriptor
1932 * dp - pointer to dmap to attempt to allocate blocks from.
1933 * l2nb - log2 number of contiguous block desired.
1934 * nblocks - actual number of contiguous block desired.
1935 * results - on successful return, set to the starting block number
1939 * 0 - success
1940 * -ENOSPC - insufficient disk resources
1941 * -EIO - i/o error
1960 if (dbFindLeaf((dmtree_t *) & dp->tree, l2nb, &leafidx)) in dbAllocDmapLev()
1961 return -ENOSPC; in dbAllocDmapLev()
1964 return -EIO; in dbAllocDmapLev()
1969 blkno = le64_to_cpu(dp->start) + (leafidx << L2DBWORD); in dbAllocDmapLev()
1971 /* if not all bits of the dmap word are free, get the starting in dbAllocDmapLev()
1972 * bit number within the dmap word of the required string of free in dbAllocDmapLev()
1973 * bits and adjust the block number with this value. in dbAllocDmapLev()
1975 if (dp->tree.stree[leafidx + LEAFIND] < BUDMIN) in dbAllocDmapLev()
1976 blkno += dbFindBits(le32_to_cpu(dp->wmap[leafidx]), l2nb); in dbAllocDmapLev()
2002 * bmp - pointer to bmap descriptor
2003 * dp - pointer to dmap to allocate the block range from.
2004 * blkno - starting block number of the block to be allocated.
2005 * nblocks - number of blocks to be allocated.
2008 * 0 - success
2009 * -EIO - i/o error
2022 oldroot = dp->tree.stree[ROOT]; in dbAllocDmap()
2024 /* allocate the specified (blocks) bits */ in dbAllocDmap()
2028 if (dp->tree.stree[ROOT] == oldroot) in dbAllocDmap()
2035 if ((rc = dbAdjCtl(bmp, blkno, dp->tree.stree[ROOT], 1, 0))) in dbAllocDmap()
2057 * bmp - pointer to bmap descriptor
2058 * dp - pointer to dmap to free the block range from.
2059 * blkno - starting block number of the block to be freed.
2060 * nblocks - number of blocks to be freed.
2063 * 0 - success
2064 * -EIO - i/o error
2072 int rc = 0, word; in dbFreeDmap() local
2077 oldroot = dp->tree.stree[ROOT]; in dbFreeDmap()
2079 /* free the specified (blocks) bits */ in dbFreeDmap()
2083 if (rc || (dp->tree.stree[ROOT] == oldroot)) in dbFreeDmap()
2090 if ((rc = dbAdjCtl(bmp, blkno, dp->tree.stree[ROOT], 0, 0))) { in dbFreeDmap()
2091 word = (blkno & (BPERDMAP - 1)) >> L2DBWORD; in dbFreeDmap()
2098 if (dp->tree.stree[word] == NOFREE) in dbFreeDmap()
2099 dbBackSplit((dmtree_t *) & dp->tree, word); in dbFreeDmap()
2115 * updates the bits of the working map and causes the adjustment
2117 * leaves to reflect the bits allocated. it also causes the
2121 * bmp - pointer to bmap descriptor
2122 * dp - pointer to dmap to allocate bits from.
2123 * blkno - starting block number of the bits to be allocated.
2124 * nblocks - number of bits to be allocated.
2133 int dbitno, word, rembits, nb, nwords, wbitno, nw, agno; in dbAllocBits() local
2134 dmtree_t *tp = (dmtree_t *) & dp->tree; in dbAllocBits()
2139 leaf = dp->tree.stree + LEAFIND; in dbAllocBits()
2141 /* determine the bit number and word within the dmap of the in dbAllocBits()
2144 dbitno = blkno & (BPERDMAP - 1); in dbAllocBits()
2145 word = dbitno >> L2DBWORD; in dbAllocBits()
2150 /* allocate the bits of the dmap's words corresponding to the block in dbAllocBits()
2151 * range. not all bits of the first and last words may be contained in dbAllocBits()
2154 * (a single pass), allocating the bits of interest by hand and in dbAllocBits()
2155 * updating the leaf corresponding to the dmap word. a single pass in dbAllocBits()
2157 * specified range. within this pass, the bits of all fully contained in dbAllocBits()
2163 for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) { in dbAllocBits()
2164 /* determine the bit number within the word and in dbAllocBits()
2165 * the number of bits within the word. in dbAllocBits()
2167 wbitno = dbitno & (DBWORD - 1); in dbAllocBits()
2168 nb = min(rembits, DBWORD - wbitno); in dbAllocBits()
2170 /* check if only part of a word is to be allocated. in dbAllocBits()
2173 /* allocate (set to 1) the appropriate bits within in dbAllocBits()
2174 * this dmap word. in dbAllocBits()
2176 dp->wmap[word] |= cpu_to_le32(ONES << (DBWORD - nb) in dbAllocBits()
2179 /* update the leaf for this dmap word. in addition in dbAllocBits()
2180 * to setting the leaf value to the binary buddy max in dbAllocBits()
2181 * of the updated dmap word, dbSplit() will split in dbAllocBits()
2184 dbSplit(tp, word, BUDMIN, in dbAllocBits()
2185 dbMaxBud((u8 *) & dp->wmap[word])); in dbAllocBits()
2187 word += 1; in dbAllocBits()
2191 * words and allocate (set to 1) the bits of these in dbAllocBits()
2195 memset(&dp->wmap[word], (int) ONES, nwords * 4); in dbAllocBits()
2197 /* determine how many bits. in dbAllocBits()
2204 for (; nwords > 0; nwords -= nw) { in dbAllocBits()
2205 if (leaf[word] < BUDMIN) { in dbAllocBits()
2206 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocBits()
2213 * of bits being allocated and the l2 number in dbAllocBits()
2214 * of bits currently described by this leaf. in dbAllocBits()
2216 size = min_t(int, leaf[word], in dbAllocBits()
2225 dbSplit(tp, word, size, NOFREE); in dbAllocBits()
2229 word += nw; in dbAllocBits()
2235 le32_add_cpu(&dp->nfree, -nblocks); in dbAllocBits()
2241 * group is the new max. in dbAllocBits()
2243 agno = blkno >> bmp->db_agl2size; in dbAllocBits()
2244 if (agno > bmp->db_maxag) in dbAllocBits()
2245 bmp->db_maxag = agno; in dbAllocBits()
2248 bmp->db_agfree[agno] -= nblocks; in dbAllocBits()
2249 bmp->db_nfree -= nblocks; in dbAllocBits()
2262 * updates the bits of the working map and causes the adjustment
2264 * leaves to reflect the bits freed. it also causes the dmap's
2268 * bmp - pointer to bmap descriptor
2269 * dp - pointer to dmap to free bits from.
2270 * blkno - starting block number of the bits to be freed.
2271 * nblocks - number of bits to be freed.
2280 int dbitno, word, rembits, nb, nwords, wbitno, nw, agno; in dbFreeBits() local
2281 dmtree_t *tp = (dmtree_t *) & dp->tree; in dbFreeBits()
2285 /* determine the bit number and word within the dmap of the in dbFreeBits()
2288 dbitno = blkno & (BPERDMAP - 1); in dbFreeBits()
2289 word = dbitno >> L2DBWORD; in dbFreeBits()
2295 /* free the bits of the dmaps words corresponding to the block range. in dbFreeBits()
2296 * not all bits of the first and last words may be contained within in dbFreeBits()
2299 * (a single pass), freeing the bits of interest by hand and updating in dbFreeBits()
2300 * the leaf corresponding to the dmap word. a single pass will be used in dbFreeBits()
2302 * within this pass, the bits of all fully contained dmap words will in dbFreeBits()
2312 for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) { in dbFreeBits()
2313 /* determine the bit number within the word and in dbFreeBits()
2314 * the number of bits within the word. in dbFreeBits()
2316 wbitno = dbitno & (DBWORD - 1); in dbFreeBits()
2317 nb = min(rembits, DBWORD - wbitno); in dbFreeBits()
2319 /* check if only part of a word is to be freed. in dbFreeBits()
2322 /* free (zero) the appropriate bits within this in dbFreeBits()
2323 * dmap word. in dbFreeBits()
2325 dp->wmap[word] &= in dbFreeBits()
2326 cpu_to_le32(~(ONES << (DBWORD - nb) in dbFreeBits()
2329 /* update the leaf for this dmap word. in dbFreeBits()
2331 rc = dbJoin(tp, word, in dbFreeBits()
2332 dbMaxBud((u8 *) & dp->wmap[word])); in dbFreeBits()
2336 word += 1; in dbFreeBits()
2340 * words and free (zero) the bits of these words. in dbFreeBits()
2343 memset(&dp->wmap[word], 0, nwords * 4); in dbFreeBits()
2345 /* determine how many bits. in dbFreeBits()
2352 for (; nwords > 0; nwords -= nw) { in dbFreeBits()
2355 * of bits being freed and the l2 (max) number in dbFreeBits()
2356 * of bits that can be described by this leaf. in dbFreeBits()
2360 (word, L2LPERDMAP, BUDMIN), in dbFreeBits()
2365 rc = dbJoin(tp, word, size); in dbFreeBits()
2372 word += nw; in dbFreeBits()
2379 le32_add_cpu(&dp->nfree, nblocks); in dbFreeBits()
2386 agno = blkno >> bmp->db_agl2size; in dbFreeBits()
2387 bmp->db_nfree += nblocks; in dbFreeBits()
2388 bmp->db_agfree[agno] += nblocks; in dbFreeBits()
2395 if ((bmp->db_agfree[agno] == bmp->db_agsize && agno == bmp->db_maxag) || in dbFreeBits()
2396 (agno == bmp->db_numag - 1 && in dbFreeBits()
2397 bmp->db_agfree[agno] == (bmp-> db_mapsize & (BPERDMAP - 1)))) { in dbFreeBits()
2398 while (bmp->db_maxag > 0) { in dbFreeBits()
2399 bmp->db_maxag -= 1; in dbFreeBits()
2400 if (bmp->db_agfree[bmp->db_maxag] != in dbFreeBits()
2401 bmp->db_agsize) in dbFreeBits()
2405 /* re-establish the allocation group preference if the in dbFreeBits()
2409 if (bmp->db_agpref > bmp->db_maxag) in dbFreeBits()
2410 bmp->db_agpref = bmp->db_maxag; in dbFreeBits()
2444 * bmp - pointer to bmap descriptor
2445 * blkno - the first block of a block range within a dmap. it is
2448 * newval - the new value of the lower level dmap or dmap control
2450 * alloc - 'true' if adjustment is due to an allocation.
2451 * level - current level of dmap control page (i.e. L0, L1, L2) to
2455 * 0 - success
2456 * -EIO - i/o error
2473 lblkno = BLKTOCTL(blkno, bmp->db_l2nbperpage, level); in dbAdjCtl()
2474 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); in dbAdjCtl()
2476 return -EIO; in dbAdjCtl()
2477 dcp = (struct dmapctl *) mp->data; in dbAdjCtl()
2479 if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) { in dbAdjCtl()
2480 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmapctl page\n"); in dbAdjCtl()
2482 return -EIO; in dbAdjCtl()
2488 leafno = BLKTOCTLLEAF(blkno, dcp->budmin); in dbAdjCtl()
2489 ti = leafno + le32_to_cpu(dcp->leafidx); in dbAdjCtl()
2494 oldval = dcp->stree[ti]; in dbAdjCtl()
2495 oldroot = dcp->stree[ROOT]; in dbAdjCtl()
2522 oldval = dcp->stree[ti]; in dbAdjCtl()
2524 dbSplit((dmtree_t *) dcp, leafno, dcp->budmin, newval); in dbAdjCtl()
2540 if (dcp->stree[ROOT] != oldroot) { in dbAdjCtl()
2544 if (level < bmp->db_maxlevel) { in dbAdjCtl()
2549 dbAdjCtl(bmp, blkno, dcp->stree[ROOT], alloc, in dbAdjCtl()
2565 if (dcp->stree[ti] == NOFREE) in dbAdjCtl()
2569 dcp->budmin, oldval); in dbAdjCtl()
2582 assert(level == bmp->db_maxlevel); in dbAdjCtl()
2583 if (bmp->db_maxfreebud != oldroot) { in dbAdjCtl()
2584 jfs_error(bmp->db_ipbmap->i_sb, in dbAdjCtl()
2587 bmp->db_maxfreebud = dcp->stree[ROOT]; in dbAdjCtl()
2607 * tp - pointer to the tree containing the leaf.
2608 * leafno - the number of the leaf to be updated.
2609 * splitsz - the size the binary buddy system starting at the leaf
2611 * newval - the new value for the leaf.
2621 s8 *leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx); in dbSplit()
2625 if (leaf[leafno] > tp->dmt_budmin) { in dbSplit()
2629 * - 1 in l2) and the corresponding buddy size. in dbSplit()
2631 cursz = leaf[leafno] - 1; in dbSplit()
2632 budsz = BUDSIZE(cursz, tp->dmt_budmin); in dbSplit()
2643 cursz -= 1; in dbSplit()
2675 * tp - pointer to the tree containing the leaf.
2676 * leafno - the number of the leaf to be updated.
2686 s8 *leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx); in dbBackSplit()
2701 LITOL2BSZ(leafno, le32_to_cpu(tp->dmt_l2nleafs), in dbBackSplit()
2702 tp->dmt_budmin); in dbBackSplit()
2708 budsz = BUDSIZE(size, tp->dmt_budmin); in dbBackSplit()
2717 if (bsz >= le32_to_cpu(tp->dmt_nleafs)) { in dbBackSplit()
2719 return -EIO; in dbBackSplit()
2732 cursz = leaf[bud] - 1; in dbBackSplit()
2741 return -EIO; in dbBackSplit()
2751 * the leaf with other leaves of the dmtree into a multi-leaf
2755 * tp - pointer to the tree containing the leaf.
2756 * leafno - the number of the leaf to be updated.
2757 * newval - the new value for the leaf.
2768 if (newval >= tp->dmt_budmin) { in dbJoin()
2771 leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx); in dbJoin()
2786 budsz = BUDSIZE(newval, tp->dmt_budmin); in dbJoin()
2790 while (budsz < le32_to_cpu(tp->dmt_nleafs)) { in dbJoin()
2803 return -EIO; in dbJoin()
2849 * tp - pointer to the tree to be adjusted.
2850 * leafno - the number of the leaf to be updated.
2851 * newval - the new value for the leaf.
2858 int max; in dbAdjTree() local
2862 lp = leafno + le32_to_cpu(tp->dmt_leafidx); in dbAdjTree()
2867 if (tp->dmt_stree[lp] == newval) in dbAdjTree()
2872 tp->dmt_stree[lp] = newval; in dbAdjTree()
2876 for (k = 0; k < le32_to_cpu(tp->dmt_height); k++) { in dbAdjTree()
2880 lp = ((lp - 1) & ~0x03) + 1; in dbAdjTree()
2884 pp = (lp - 1) >> 2; in dbAdjTree()
2888 max = TREEMAX(&tp->dmt_stree[lp]); in dbAdjTree()
2893 if (tp->dmt_stree[pp] == max) in dbAdjTree()
2898 tp->dmt_stree[pp] = max; in dbAdjTree()
2900 /* parent becomes leaf for next go-round. in dbAdjTree()
2919 * tp - pointer to the tree to be searched.
2920 * l2nb - log2 number of free blocks to search for.
2921 * leafidx - return pointer to be set to the index of the leaf
2926 * 0 - success
2927 * -ENOSPC - insufficient free blocks.
2936 if (l2nb > tp->dmt_stree[ROOT]) in dbFindLeaf()
2937 return -ENOSPC; in dbFindLeaf()
2943 for (k = le32_to_cpu(tp->dmt_height), ti = 1; in dbFindLeaf()
2944 k > 0; k--, ti = ((ti + n) << 2) + 1) { in dbFindLeaf()
2952 if (l2nb <= tp->dmt_stree[x + n]) in dbFindLeaf()
2965 *leafidx = x + n - le32_to_cpu(tp->dmt_leafidx); in dbFindLeaf()
2974 * FUNCTION: find a specified number of binary buddy free bits within a
2975 * dmap bitmap word value.
2978 * bits at (1 << l2nb) alignments within the value.
2981 * word - dmap bitmap word value.
2982 * l2nb - number of free bits specified as a log2 number.
2985 * starting bit number of free bits.
2987 static int dbFindBits(u32 word, int l2nb) in dbFindBits() argument
2992 /* get the number of bits. in dbFindBits()
2997 /* complement the word so we can use a mask (i.e. 0s represent in dbFindBits()
2998 * free bits) and compute the mask. in dbFindBits()
3000 word = ~word; in dbFindBits()
3001 mask = ONES << (DBWORD - nb); in dbFindBits()
3003 /* scan the word for nb free bits at nb alignments. in dbFindBits()
3006 if ((mask & word) == mask) in dbFindBits()
3022 * bits within 32-bits of the map.
3025 * cp - pointer to the 32-bit value.
3028 * largest binary buddy of free bits within a dmap word.
3034 /* check if the wmap word is all free. if so, the in dbMaxBud()
3040 /* check if the wmap word is half free. if so, the in dbMaxBud()
3041 * free buddy size is BUDMIN-1. in dbMaxBud()
3044 return (BUDMIN - 1); in dbMaxBud()
3047 * size thru table lookup using quarters of the wmap word. in dbMaxBud()
3049 tmp1 = max(budtab[cp[2]], budtab[cp[3]]); in dbMaxBud()
3050 tmp2 = max(budtab[cp[0]], budtab[cp[1]]); in dbMaxBud()
3051 return (max(tmp1, tmp2)); in dbMaxBud()
3056 * NAME: cnttz(uint word)
3058 * FUNCTION: determine the number of trailing zeros within a 32-bit
3062 * value - 32-bit value to be examined.
3067 static int cnttz(u32 word) in cnttz() argument
3071 for (n = 0; n < 32; n++, word >>= 1) { in cnttz()
3072 if (word & 0x01) in cnttz()
3083 * FUNCTION: determine the number of leading zeros within a 32-bit
3087 * value - 32-bit value to be examined.
3112 * nb - number of blocks
3122 mask = (s64) 1 << (64 - 1); in blkstol2()
3124 /* count the leading bits. in blkstol2()
3132 l2nb = (64 - 1) - l2nb; in blkstol2()
3157 * ip - pointer to in-core inode;
3158 * blkno - starting block number to be freed.
3159 * nblocks - number of blocks to be freed.
3162 * 0 - success
3163 * -EIO - i/o error
3171 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap; in dbAllocBottomUp()
3172 struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap; in dbAllocBottomUp()
3177 ASSERT(nblocks <= bmp->db_mapsize - blkno); in dbAllocBottomUp()
3183 for (rem = nblocks; rem > 0; rem -= nb, blkno += nb) { in dbAllocBottomUp()
3190 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); in dbAllocBottomUp()
3194 return -EIO; in dbAllocBottomUp()
3196 dp = (struct dmap *) mp->data; in dbAllocBottomUp()
3201 nb = min(rem, BPERDMAP - (blkno & (BPERDMAP - 1))); in dbAllocBottomUp()
3224 int dbitno, word, rembits, nb, nwords, wbitno, agno; in dbAllocDmapBU() local
3226 struct dmaptree *tp = (struct dmaptree *) & dp->tree; in dbAllocDmapBU()
3231 oldroot = tp->stree[ROOT]; in dbAllocDmapBU()
3233 /* determine the bit number and word within the dmap of the in dbAllocDmapBU()
3236 dbitno = blkno & (BPERDMAP - 1); in dbAllocDmapBU()
3237 word = dbitno >> L2DBWORD; in dbAllocDmapBU()
3242 /* allocate the bits of the dmap's words corresponding to the block in dbAllocDmapBU()
3243 * range. not all bits of the first and last words may be contained in dbAllocDmapBU()
3246 * (a single pass), allocating the bits of interest by hand and in dbAllocDmapBU()
3247 * updating the leaf corresponding to the dmap word. a single pass in dbAllocDmapBU()
3249 * specified range. within this pass, the bits of all fully contained in dbAllocDmapBU()
3255 for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) { in dbAllocDmapBU()
3256 /* determine the bit number within the word and in dbAllocDmapBU()
3257 * the number of bits within the word. in dbAllocDmapBU()
3259 wbitno = dbitno & (DBWORD - 1); in dbAllocDmapBU()
3260 nb = min(rembits, DBWORD - wbitno); in dbAllocDmapBU()
3262 /* check if only part of a word is to be allocated. in dbAllocDmapBU()
3265 /* allocate (set to 1) the appropriate bits within in dbAllocDmapBU()
3266 * this dmap word. in dbAllocDmapBU()
3268 dp->wmap[word] |= cpu_to_le32(ONES << (DBWORD - nb) in dbAllocDmapBU()
3271 word++; in dbAllocDmapBU()
3275 * words and allocate (set to 1) the bits of these in dbAllocDmapBU()
3279 memset(&dp->wmap[word], (int) ONES, nwords * 4); in dbAllocDmapBU()
3281 /* determine how many bits */ in dbAllocDmapBU()
3283 word += nwords; in dbAllocDmapBU()
3288 le32_add_cpu(&dp->nfree, -nblocks); in dbAllocDmapBU()
3297 * if this allocation group is the new max. in dbAllocDmapBU()
3299 agno = blkno >> bmp->db_agl2size; in dbAllocDmapBU()
3300 if (agno > bmp->db_maxag) in dbAllocDmapBU()
3301 bmp->db_maxag = agno; in dbAllocDmapBU()
3304 bmp->db_agfree[agno] -= nblocks; in dbAllocDmapBU()
3305 bmp->db_nfree -= nblocks; in dbAllocDmapBU()
3310 if (tp->stree[ROOT] == oldroot) in dbAllocDmapBU()
3317 if ((rc = dbAdjCtl(bmp, blkno, tp->stree[ROOT], 1, 0))) in dbAllocDmapBU()
3332 * L1---------------------------------L1
3334 * L0---------L0---------L0 L0---------L0---------L0
3339 * <---old---><----------------------------extend----------------------->
3343 struct jfs_sb_info *sbi = JFS_SBI(ipbmap->i_sb); in dbExtendFS()
3344 int nbperpage = sbi->nbperpage; in dbExtendFS()
3352 struct bmap *bmp = sbi->bmap; in dbExtendFS()
3369 bmp->db_mapsize = newsize; in dbExtendFS()
3370 bmp->db_maxlevel = BMAPSZTOLEV(bmp->db_mapsize); in dbExtendFS()
3374 oldl2agsize = bmp->db_agl2size; in dbExtendFS()
3376 bmp->db_agl2size = l2agsize; in dbExtendFS()
3377 bmp->db_agsize = 1 << l2agsize; in dbExtendFS()
3380 agno = bmp->db_numag; in dbExtendFS()
3381 bmp->db_numag = newsize >> l2agsize; in dbExtendFS()
3382 bmp->db_numag += ((u32) newsize % (u32) bmp->db_agsize) ? 1 : 0; in dbExtendFS()
3389 * i.e., (AGi, ..., AGj) where i = k*n and j = k*(n+1) - 1 to AGn; in dbExtendFS()
3394 k = 1 << (l2agsize - oldl2agsize); in dbExtendFS()
3395 ag_rem = bmp->db_agfree[0]; /* save agfree[0] */ in dbExtendFS()
3397 bmp->db_agfree[n] = 0; /* init collection point */ in dbExtendFS()
3402 bmp->db_agfree[n] += bmp->db_agfree[i]; in dbExtendFS()
3405 bmp->db_agfree[0] += ag_rem; /* restore agfree[0] */ in dbExtendFS()
3408 bmp->db_agfree[n] = 0; in dbExtendFS()
3414 bmp->db_maxag = bmp->db_maxag / k; in dbExtendFS()
3427 jfs_error(ipbmap->i_sb, "L2 page could not be read\n"); in dbExtendFS()
3428 return -EIO; in dbExtendFS()
3430 l2dcp = (struct dmapctl *) l2mp->data; in dbExtendFS()
3434 l2leaf = l2dcp->stree + CTLLEAFIND + k; in dbExtendFS()
3435 p = BLKTOL1(blkno, sbi->l2nbperpage); /* L1 page */ in dbExtendFS()
3443 /* read in L1 page: (blkno & (MAXL1SIZE - 1)) */ in dbExtendFS()
3447 l1dcp = (struct dmapctl *) l1mp->data; in dbExtendFS()
3450 j = (blkno & (MAXL1SIZE - 1)) >> L2MAXL0SIZE; in dbExtendFS()
3451 l1leaf = l1dcp->stree + CTLLEAFIND + j; in dbExtendFS()
3452 p = BLKTOL0(blkno, sbi->l2nbperpage); in dbExtendFS()
3460 l1dcp = (struct dmapctl *) l1mp->data; in dbExtendFS()
3464 l1leaf = l1dcp->stree + CTLLEAFIND; in dbExtendFS()
3474 /* read in L0 page: (blkno & (MAXL0SIZE - 1)) */ in dbExtendFS()
3479 l0dcp = (struct dmapctl *) l0mp->data; in dbExtendFS()
3482 i = (blkno & (MAXL0SIZE - 1)) >> in dbExtendFS()
3484 l0leaf = l0dcp->stree + CTLLEAFIND + i; in dbExtendFS()
3486 sbi->l2nbperpage); in dbExtendFS()
3494 l0dcp = (struct dmapctl *) l0mp->data; in dbExtendFS()
3498 l0leaf = l0dcp->stree + CTLLEAFIND; in dbExtendFS()
3510 if ((n = blkno & (BPERDMAP - 1))) { in dbExtendFS()
3516 n = min(nblocks, (s64)BPERDMAP - n); in dbExtendFS()
3527 dp = (struct dmap *) mp->data; in dbExtendFS()
3530 bmp->db_nfree += n; in dbExtendFS()
3531 agno = le64_to_cpu(dp->start) >> l2agsize; in dbExtendFS()
3532 bmp->db_agfree[agno] += n; in dbExtendFS()
3540 nblocks -= n; in dbExtendFS()
3561 bmp->db_maxfreebud = *l1leaf; in dbExtendFS()
3585 bmp->db_maxfreebud = *l2leaf; in dbExtendFS()
3592 jfs_error(ipbmap->i_sb, "function has not returned as expected\n"); in dbExtendFS()
3599 return -EIO; in dbExtendFS()
3615 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap; in dbFinalizeBmap()
3630 actags = bmp->db_maxag + 1; in dbFinalizeBmap()
3631 inactags = bmp->db_numag - actags; in dbFinalizeBmap()
3632 ag_rem = bmp->db_mapsize & (bmp->db_agsize - 1); /* ??? */ in dbFinalizeBmap()
3640 ((inactags - 1) << bmp->db_agl2size) + ag_rem in dbFinalizeBmap()
3641 : inactags << bmp->db_agl2size; in dbFinalizeBmap()
3647 actfree = bmp->db_nfree - inactfree; in dbFinalizeBmap()
3651 * re-establish the preferred group as the leftmost in dbFinalizeBmap()
3654 if (bmp->db_agfree[bmp->db_agpref] < avgfree) { in dbFinalizeBmap()
3655 for (bmp->db_agpref = 0; bmp->db_agpref < actags; in dbFinalizeBmap()
3656 bmp->db_agpref++) { in dbFinalizeBmap()
3657 if (bmp->db_agfree[bmp->db_agpref] >= avgfree) in dbFinalizeBmap()
3660 if (bmp->db_agpref >= bmp->db_numag) { in dbFinalizeBmap()
3661 jfs_error(ipbmap->i_sb, in dbFinalizeBmap()
3673 bmp->db_aglevel = BMAPSZTOLEV(bmp->db_agsize); in dbFinalizeBmap()
3675 bmp->db_agl2size - (L2BPERDMAP + bmp->db_aglevel * L2LPERCTL); in dbFinalizeBmap()
3676 bmp->db_agheight = l2nl >> 1; in dbFinalizeBmap()
3677 bmp->db_agwidth = 1 << (l2nl - (bmp->db_agheight << 1)); in dbFinalizeBmap()
3678 for (i = 5 - bmp->db_agheight, bmp->db_agstart = 0, n = 1; i > 0; in dbFinalizeBmap()
3679 i--) { in dbFinalizeBmap()
3680 bmp->db_agstart += n; in dbFinalizeBmap()
3699 * dp - pointer to page of map
3700 * nblocks - number of blocks this page
3709 blkno = Blkno & (BPERDMAP - 1); in dbInitDmap()
3712 dp->nblocks = dp->nfree = cpu_to_le32(nblocks); in dbInitDmap()
3713 dp->start = cpu_to_le64(Blkno); in dbInitDmap()
3716 memset(&dp->wmap[0], 0, LPERDMAP * 4); in dbInitDmap()
3717 memset(&dp->pmap[0], 0, LPERDMAP * 4); in dbInitDmap()
3721 le32_add_cpu(&dp->nblocks, nblocks); in dbInitDmap()
3722 le32_add_cpu(&dp->nfree, nblocks); in dbInitDmap()
3725 /* word number containing start block number */ in dbInitDmap()
3729 * free the bits corresponding to the block range (ZEROS): in dbInitDmap()
3730 * note: not all bits of the first and last words may be contained in dbInitDmap()
3733 for (r = nblocks; r > 0; r -= nb, blkno += nb) { in dbInitDmap()
3734 /* number of bits preceding range to be freed in the word */ in dbInitDmap()
3735 b = blkno & (DBWORD - 1); in dbInitDmap()
3736 /* number of bits to free in the word */ in dbInitDmap()
3737 nb = min(r, DBWORD - b); in dbInitDmap()
3739 /* is partial word to be freed ? */ in dbInitDmap()
3741 /* free (set to 0) from the bitmap word */ in dbInitDmap()
3742 dp->wmap[w] &= cpu_to_le32(~(ONES << (DBWORD - nb) in dbInitDmap()
3744 dp->pmap[w] &= cpu_to_le32(~(ONES << (DBWORD - nb) in dbInitDmap()
3747 /* skip the word freed */ in dbInitDmap()
3752 memset(&dp->wmap[w], 0, nw * 4); in dbInitDmap()
3753 memset(&dp->pmap[w], 0, nw * 4); in dbInitDmap()
3762 * mark bits following the range to be freed (non-existing in dbInitDmap()
3769 /* the first word beyond the end of existing blocks */ in dbInitDmap()
3772 /* does nblocks fall on a 32-bit boundary ? */ in dbInitDmap()
3773 b = blkno & (DBWORD - 1); in dbInitDmap()
3775 /* mark a partial word allocated */ in dbInitDmap()
3776 dp->wmap[w] = dp->pmap[w] = cpu_to_le32(ONES >> b); in dbInitDmap()
3782 dp->pmap[i] = dp->wmap[i] = cpu_to_le32(ONES); in dbInitDmap()
3800 * dp - dmap to complete
3801 * blkno - starting block number for this dmap
3802 * treemax - will be filled in with max free for this dmap
3804 * RETURNS: max free string at the root of the tree
3813 tp = &dp->tree; in dbInitDmapTree()
3814 tp->nleafs = cpu_to_le32(LPERDMAP); in dbInitDmapTree()
3815 tp->l2nleafs = cpu_to_le32(L2LPERDMAP); in dbInitDmapTree()
3816 tp->leafidx = cpu_to_le32(LEAFIND); in dbInitDmapTree()
3817 tp->height = cpu_to_le32(4); in dbInitDmapTree()
3818 tp->budmin = BUDMIN; in dbInitDmapTree()
3820 /* init each leaf from corresponding wmap word: in dbInitDmapTree()
3821 * note: leaf is set to NOFREE(-1) if all blocks of corresponding in dbInitDmapTree()
3822 * bitmap word are allocated. in dbInitDmapTree()
3824 cp = tp->stree + le32_to_cpu(tp->leafidx); in dbInitDmapTree()
3826 *cp++ = dbMaxBud((u8 *) & dp->wmap[i]); in dbInitDmapTree()
3839 * from corresponding bitmap word or root of summary tree
3845 * cp - Pointer to the root of the tree
3846 * l2leaves- Number of leaf nodes as a power of 2
3847 * l2min - Number of blocks that can be covered by a leaf
3850 * RETURNS: max free string at the root of the tree
3858 tp = dtp->stree; in dbInitTree()
3861 l2max = le32_to_cpu(dtp->l2nleafs) + dtp->budmin; in dbInitTree()
3869 * the combination will result in the left-most buddy leaf having in dbInitTree()
3877 for (l2free = dtp->budmin, bsize = 1; l2free < l2max; in dbInitTree()
3883 for (i = 0, cp = tp + le32_to_cpu(dtp->leafidx); in dbInitTree()
3884 i < le32_to_cpu(dtp->nleafs); in dbInitTree()
3886 /* coalesce if both adjacent buddies are max free */ in dbInitTree()
3889 *(cp + bsize) = -1; /* right give left */ in dbInitTree()
3904 for (child = le32_to_cpu(dtp->leafidx), in dbInitTree()
3905 nparent = le32_to_cpu(dtp->nleafs) >> 2; in dbInitTree()
3908 parent = (child - 1) >> 2; in dbInitTree()
3931 dcp->nleafs = cpu_to_le32(LPERCTL); in dbInitDmapCtl()
3932 dcp->l2nleafs = cpu_to_le32(L2LPERCTL); in dbInitDmapCtl()
3933 dcp->leafidx = cpu_to_le32(CTLLEAFIND); in dbInitDmapCtl()
3934 dcp->height = cpu_to_le32(5); in dbInitDmapCtl()
3935 dcp->budmin = L2BPERDMAP + L2LPERCTL * level; in dbInitDmapCtl()
3942 cp = &dcp->stree[CTLLEAFIND + i]; in dbInitDmapCtl()
3957 * nblocks - Number of blocks in aggregate
3971 m = ((u64) 1 << (64 - 1)); in dbGetL2AGSize()
3972 for (l2sz = 64; l2sz >= 0; l2sz--, m >>= 1) { in dbGetL2AGSize()
3982 return (l2sz - L2MAXAG); in dbGetL2AGSize()
4010 struct super_block *sb = ipbmap->i_sb; in dbMapFileSizeToMapSize()
4016 nblocks = ipbmap->i_size >> JFS_SBI(sb)->l2bsize; in dbMapFileSizeToMapSize()
4017 npages = nblocks >> JFS_SBI(sb)->l2nbperpage; in dbMapFileSizeToMapSize()
4025 npages--; /* skip the first global control page */ in dbMapFileSizeToMapSize()
4027 npages -= (2 - level); in dbMapFileSizeToMapSize()
4028 npages--; /* skip top level's control page */ in dbMapFileSizeToMapSize()
4029 for (i = level; i >= 0; i--) { in dbMapFileSizeToMapSize()
4039 npages--; in dbMapFileSizeToMapSize()