Lines Matching +full:rc +full:- +full:map +full:- +full:name
1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * Copyright (C) International Business Machines Corp., 2000-2004
19 * SERIALIZATION of the Block Allocation Map.
21 * the working state of the block allocation map is accessed in
41 * take the lock in read mode. a single top-down request may proceed
42 * exclusively while multiple bottoms-up requests may proceed
46 * the working state of the block allocation map also includes read/
50 * in the face of multiple-bottoms up requests.
53 * accesses to the persistent state of the block allocation map (limited
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)
133 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, -1
137 * NAME: dbMount()
139 * FUNCTION: initializate the block allocation map.
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()
174 return -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()
181 bmp->db_l2nbperpage = le32_to_cpu(dbmp_le->dn_l2nbperpage); in dbMount()
182 bmp->db_numag = le32_to_cpu(dbmp_le->dn_numag); in dbMount()
183 if (!bmp->db_numag) { in dbMount()
186 return -EINVAL; in dbMount()
189 bmp->db_maxlevel = le32_to_cpu(dbmp_le->dn_maxlevel); in dbMount()
190 bmp->db_maxag = le32_to_cpu(dbmp_le->dn_maxag); in dbMount()
191 bmp->db_agpref = le32_to_cpu(dbmp_le->dn_agpref); in dbMount()
192 bmp->db_aglevel = le32_to_cpu(dbmp_le->dn_aglevel); in dbMount()
193 bmp->db_agheight = le32_to_cpu(dbmp_le->dn_agheight); in dbMount()
194 bmp->db_agwidth = le32_to_cpu(dbmp_le->dn_agwidth); in dbMount()
195 bmp->db_agstart = le32_to_cpu(dbmp_le->dn_agstart); in dbMount()
196 bmp->db_agl2size = le32_to_cpu(dbmp_le->dn_agl2size); in dbMount()
198 bmp->db_agfree[i] = le64_to_cpu(dbmp_le->dn_agfree[i]); in dbMount()
199 bmp->db_agsize = le64_to_cpu(dbmp_le->dn_agsize); in dbMount()
200 bmp->db_maxfreebud = dbmp_le->dn_maxfreebud; in dbMount()
206 bmp->db_ipbmap = ipbmap; in dbMount()
207 JFS_SBI(ipbmap->i_sb)->bmap = bmp; in dbMount()
209 memset(bmp->db_active, 0, sizeof(bmp->db_active)); in dbMount()
221 * NAME: dbUnmount()
223 * FUNCTION: terminate the block allocation map in preparation for
226 * the in-core bmap descriptor is written to disk and
230 * ipbmap - pointer to in-core inode for the block map.
233 * 0 - success
234 * -EIO - i/o error
238 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap; in dbUnmount()
246 truncate_inode_pages(ipbmap->i_mapping, 0); in dbUnmount()
248 /* free the memory for the in-memory bmap. */ in dbUnmount()
260 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap; in dbSync()
267 /* get the buffer for the on-disk bmap descriptor. */ in dbSync()
269 BMAPBLKNO << JFS_SBI(ipbmap->i_sb)->l2nbperpage, in dbSync()
273 return -EIO; in dbSync()
275 /* copy the in-memory version of the bmap to the on-disk version */ in dbSync()
276 dbmp_le = (struct dbmap_disk *) mp->data; in dbSync()
277 dbmp_le->dn_mapsize = cpu_to_le64(bmp->db_mapsize); in dbSync()
278 dbmp_le->dn_nfree = cpu_to_le64(bmp->db_nfree); in dbSync()
279 dbmp_le->dn_l2nbperpage = cpu_to_le32(bmp->db_l2nbperpage); in dbSync()
280 dbmp_le->dn_numag = cpu_to_le32(bmp->db_numag); in dbSync()
281 dbmp_le->dn_maxlevel = cpu_to_le32(bmp->db_maxlevel); in dbSync()
282 dbmp_le->dn_maxag = cpu_to_le32(bmp->db_maxag); in dbSync()
283 dbmp_le->dn_agpref = cpu_to_le32(bmp->db_agpref); in dbSync()
284 dbmp_le->dn_aglevel = cpu_to_le32(bmp->db_aglevel); in dbSync()
285 dbmp_le->dn_agheight = cpu_to_le32(bmp->db_agheight); in dbSync()
286 dbmp_le->dn_agwidth = cpu_to_le32(bmp->db_agwidth); in dbSync()
287 dbmp_le->dn_agstart = cpu_to_le32(bmp->db_agstart); in dbSync()
288 dbmp_le->dn_agl2size = cpu_to_le32(bmp->db_agl2size); in dbSync()
290 dbmp_le->dn_agfree[i] = cpu_to_le64(bmp->db_agfree[i]); in dbSync()
291 dbmp_le->dn_agsize = cpu_to_le64(bmp->db_agsize); in dbSync()
292 dbmp_le->dn_maxfreebud = bmp->db_maxfreebud; in dbSync()
300 filemap_write_and_wait(ipbmap->i_mapping); in dbSync()
308 * NAME: dbFree()
311 * allocation map.
313 * the blocks will be free from the working map one dmap
317 * ip - pointer to in-core inode;
318 * blkno - starting block number to be freed.
319 * nblocks - number of blocks to be freed.
322 * 0 - success
323 * -EIO - i/o error
329 int nb, rc; in dbFree() local
331 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap; in dbFree()
332 struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap; in dbFree()
333 struct super_block *sb = ipbmap->i_sb; in dbFree()
338 if (unlikely((blkno == 0) || (blkno + nblocks > bmp->db_mapsize))) { in dbFree()
343 jfs_error(ip->i_sb, "block to be freed is outside the map\n"); in dbFree()
344 return -EIO; in dbFree()
350 if (JFS_SBI(sb)->flag & JFS_DISCARD) in dbFree()
351 if (JFS_SBI(sb)->minblks_trim <= nblocks) in dbFree()
358 for (rem = nblocks; rem > 0; rem -= nb, blkno += nb) { in dbFree()
365 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); in dbFree()
369 return -EIO; in dbFree()
371 dp = (struct dmap *) mp->data; in dbFree()
376 nb = min(rem, BPERDMAP - (blkno & (BPERDMAP - 1))); in dbFree()
379 if ((rc = dbFreeDmap(bmp, dp, blkno, nb))) { in dbFree()
380 jfs_error(ip->i_sb, "error in block map\n"); in dbFree()
383 return (rc); in dbFree()
398 * NAME: dbUpdatePMap()
401 * specified block range in the persistent block allocation map.
403 * the blocks will be updated in the persistent map one
407 * ipbmap - pointer to in-core inode for the block map.
408 * free - 'true' if block range is to be freed from the persistent
409 * map; 'false' if it is to be allocated.
410 * blkno - starting block number of the range.
411 * nblocks - number of contiguous blocks in the range.
412 * tblk - transaction block;
415 * 0 - success
416 * -EIO - i/o error
424 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap; in dbUpdatePMap()
434 if (blkno + nblocks > bmp->db_mapsize) { in dbUpdatePMap()
438 jfs_error(ipbmap->i_sb, "blocks are outside the map\n"); in dbUpdatePMap()
439 return -EIO; in dbUpdatePMap()
443 lsn = tblk->lsn; in dbUpdatePMap()
444 log = (struct jfs_log *) JFS_SBI(tblk->sb)->log; in dbUpdatePMap()
452 for (rem = nblocks; rem > 0; rem -= nblks, blkno += nblks) { in dbUpdatePMap()
454 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); in dbUpdatePMap()
460 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, in dbUpdatePMap()
463 return -EIO; in dbUpdatePMap()
466 dp = (struct dmap *) mp->data; in dbUpdatePMap()
472 dbitno = blkno & (BPERDMAP - 1); in dbUpdatePMap()
474 nblks = min(rem, (s64)BPERDMAP - dbitno); in dbUpdatePMap()
484 rbits -= nbits, dbitno += nbits) { in dbUpdatePMap()
488 wbitno = dbitno & (DBWORD - 1); in dbUpdatePMap()
489 nbits = min(rbits, DBWORD - wbitno); in dbUpdatePMap()
497 (ONES << (DBWORD - nbits) >> wbitno); in dbUpdatePMap()
499 dp->pmap[word] &= in dbUpdatePMap()
502 dp->pmap[word] |= in dbUpdatePMap()
518 memset(&dp->pmap[word], 0, in dbUpdatePMap()
521 memset(&dp->pmap[word], (int) ONES, in dbUpdatePMap()
537 if (mp->lsn != 0) { in dbUpdatePMap()
539 logdiff(diffp, mp->lsn, log); in dbUpdatePMap()
541 mp->lsn = lsn; in dbUpdatePMap()
544 list_move(&mp->synclist, &tblk->synclist); in dbUpdatePMap()
548 logdiff(difft, tblk->clsn, log); in dbUpdatePMap()
549 logdiff(diffp, mp->clsn, log); in dbUpdatePMap()
551 mp->clsn = tblk->clsn; in dbUpdatePMap()
553 mp->log = log; in dbUpdatePMap()
554 mp->lsn = lsn; in dbUpdatePMap()
557 log->count++; in dbUpdatePMap()
558 list_add(&mp->synclist, &tblk->synclist); in dbUpdatePMap()
560 mp->clsn = tblk->clsn; in dbUpdatePMap()
575 * NAME: dbNextAG()
582 * new inode allocation towards. The tie-in between inode
593 * ipbmap - pointer to in-core inode for the block map.
604 int next_best = -1; in dbNextAG()
605 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap; in dbNextAG()
610 avgfree = (u32)bmp->db_nfree / bmp->db_numag; in dbNextAG()
616 agpref = bmp->db_agpref; in dbNextAG()
617 if ((atomic_read(&bmp->db_active[agpref]) == 0) && in dbNextAG()
618 (bmp->db_agfree[agpref] >= avgfree)) in dbNextAG()
624 for (i = 0 ; i < bmp->db_numag; i++, agpref++) { in dbNextAG()
625 if (agpref == bmp->db_numag) in dbNextAG()
628 if (atomic_read(&bmp->db_active[agpref])) in dbNextAG()
631 if (bmp->db_agfree[agpref] >= avgfree) { in dbNextAG()
633 bmp->db_agpref = agpref; in dbNextAG()
635 } else if (bmp->db_agfree[agpref] > hwm) { in dbNextAG()
637 hwm = bmp->db_agfree[agpref]; in dbNextAG()
646 if (next_best != -1) in dbNextAG()
647 bmp->db_agpref = next_best; in dbNextAG()
654 return (bmp->db_agpref); in dbNextAG()
658 * NAME: dbAlloc()
661 * blocks from the working allocation block map.
663 * the block allocation policy uses hints and a multi-step
684 * ip - pointer to in-core inode;
685 * hint - allocation hint.
686 * nblocks - number of contiguous blocks in the range.
687 * results - on successful return, set to the starting block number
691 * 0 - success
692 * -ENOSPC - insufficient disk resources
693 * -EIO - i/o error
697 int rc, agno; in dbAlloc() local
698 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap; in dbAlloc()
716 bmp = JFS_SBI(ip->i_sb)->bmap; in dbAlloc()
718 mapSize = bmp->db_mapsize; in dbAlloc()
720 /* the hint should be within the map */ in dbAlloc()
722 jfs_error(ip->i_sb, "the hint is outside the map\n"); in dbAlloc()
723 return -EIO; in dbAlloc()
729 if (l2nb > bmp->db_agl2size) { in dbAlloc()
732 rc = dbAllocAny(bmp, nblocks, l2nb, results); in dbAlloc()
749 if (blkno >= bmp->db_mapsize) in dbAlloc()
752 agno = blkno >> bmp->db_agl2size; in dbAlloc()
758 if ((blkno & (bmp->db_agsize - 1)) == 0) in dbAlloc()
760 * if so, call dbNextAG() to find a non-busy in dbAlloc()
763 if (atomic_read(&bmp->db_active[agno])) in dbAlloc()
775 rc = -EIO; in dbAlloc()
776 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); in dbAlloc()
781 dp = (struct dmap *) mp->data; in dbAlloc()
786 if ((rc = dbAllocNext(bmp, dp, blkno, (int) nblocks)) in dbAlloc()
787 != -ENOSPC) { in dbAlloc()
788 if (rc == 0) { in dbAlloc()
797 writers = atomic_read(&bmp->db_active[agno]); in dbAlloc()
799 ((writers == 1) && (JFS_IP(ip)->active_ag != agno))) { in dbAlloc()
812 if ((rc = in dbAlloc()
814 != -ENOSPC) { in dbAlloc()
815 if (rc == 0) in dbAlloc()
825 if ((rc = dbAllocDmapLev(bmp, dp, (int) nblocks, l2nb, results)) in dbAlloc()
826 != -ENOSPC) { in dbAlloc()
827 if (rc == 0) in dbAlloc()
842 if ((rc = dbAllocAG(bmp, agno, nblocks, l2nb, results)) != -ENOSPC) in dbAlloc()
856 * allocate anywhere in the map. in dbAlloc()
858 if ((rc = dbAllocAG(bmp, agno, nblocks, l2nb, results)) == -ENOSPC) in dbAlloc()
859 rc = dbAllocAny(bmp, nblocks, l2nb, results); in dbAlloc()
864 return (rc); in dbAlloc()
869 return (rc); in dbAlloc()
874 * NAME: dbAllocExact()
879 * ip - pointer to in-core inode;
880 * blkno - extent address;
881 * nblocks - extent length;
884 * 0 - success
885 * -ENOSPC - insufficient disk resources
886 * -EIO - i/o error
890 int rc; in dbAllocExact() local
891 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap; in dbAllocExact()
892 struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap; in dbAllocExact()
906 if (nblocks <= 0 || nblocks > BPERDMAP || blkno >= bmp->db_mapsize) { in dbAllocExact()
908 return -EINVAL; in dbAllocExact()
911 if (nblocks > ((s64) 1 << bmp->db_maxfreebud)) { in dbAllocExact()
914 return -ENOSPC; in dbAllocExact()
918 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); in dbAllocExact()
922 return -EIO; in dbAllocExact()
924 dp = (struct dmap *) mp->data; in dbAllocExact()
927 rc = dbAllocNext(bmp, dp, blkno, nblocks); in dbAllocExact()
931 if (rc == 0) in dbAllocExact()
936 return (rc); in dbAllocExact()
941 * NAME: dbReAlloc()
956 * ip - pointer to in-core inode requiring allocation.
957 * blkno - starting block of the current allocation.
958 * nblocks - number of contiguous blocks within the current
960 * addnblocks - number of blocks to add to the allocation.
961 * results - on successful return, set to the starting block number
968 * 0 - success
969 * -ENOSPC - insufficient disk resources
970 * -EIO - i/o error
976 int rc; in dbReAlloc() local
980 if ((rc = dbExtend(ip, blkno, nblocks, addnblocks)) == 0) { in dbReAlloc()
984 if (rc != -ENOSPC) in dbReAlloc()
985 return (rc); in dbReAlloc()
994 (ip, blkno + nblocks - 1, addnblocks + nblocks, results)); in dbReAlloc()
999 * NAME: dbExtend()
1010 * ip - pointer to in-core inode requiring allocation.
1011 * blkno - starting block of the current allocation.
1012 * nblocks - number of contiguous blocks within the current
1014 * addnblocks - number of blocks to add to the allocation.
1017 * 0 - success
1018 * -ENOSPC - insufficient disk resources
1019 * -EIO - i/o error
1023 struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb); in dbExtend()
1028 int rc; in dbExtend() local
1029 struct inode *ipbmap = sbi->ipbmap; in dbExtend()
1033 * We don't want a non-aligned extent to cross a page boundary in dbExtend()
1035 if (((rel_block = blkno & (sbi->nbperpage - 1))) && in dbExtend()
1036 (rel_block + nblocks + addnblocks > sbi->nbperpage)) in dbExtend()
1037 return -ENOSPC; in dbExtend()
1040 lastblkno = blkno + nblocks - 1; in dbExtend()
1050 bmp = sbi->bmap; in dbExtend()
1051 if (lastblkno < 0 || lastblkno >= bmp->db_mapsize) { in dbExtend()
1053 jfs_error(ip->i_sb, "the block is outside the filesystem\n"); in dbExtend()
1054 return -EIO; in dbExtend()
1065 if (addnblocks > BPERDMAP || extblkno >= bmp->db_mapsize || in dbExtend()
1066 (extblkno & (bmp->db_agsize - 1)) == 0) { in dbExtend()
1068 return -ENOSPC; in dbExtend()
1074 lblkno = BLKTODMAP(extblkno, bmp->db_l2nbperpage); in dbExtend()
1078 return -EIO; in dbExtend()
1081 dp = (struct dmap *) mp->data; in dbExtend()
1086 rc = dbAllocNext(bmp, dp, extblkno, (int) addnblocks); in dbExtend()
1091 if (rc == 0) in dbExtend()
1097 return (rc); in dbExtend()
1102 * NAME: dbAllocNext()
1108 * bmp - pointer to bmap descriptor
1109 * dp - pointer to dmap.
1110 * blkno - starting block number of the range.
1111 * nblocks - number of contiguous free blocks of the range.
1114 * 0 - success
1115 * -ENOSPC - insufficient disk resources
1116 * -EIO - i/o error
1128 if (dp->tree.leafidx != cpu_to_le32(LEAFIND)) { in dbAllocNext()
1129 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmap page\n"); in dbAllocNext()
1130 return -EIO; in dbAllocNext()
1135 leaf = dp->tree.stree + le32_to_cpu(dp->tree.leafidx); in dbAllocNext()
1140 dbitno = blkno & (BPERDMAP - 1); in dbAllocNext()
1147 return -ENOSPC; in dbAllocNext()
1153 return -ENOSPC; in dbAllocNext()
1168 for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) { in dbAllocNext()
1172 wbitno = dbitno & (DBWORD - 1); in dbAllocNext()
1173 nb = min(rembits, DBWORD - wbitno); in dbAllocNext()
1180 mask = (ONES << (DBWORD - nb) >> wbitno); in dbAllocNext()
1181 if ((mask & ~le32_to_cpu(dp->wmap[word])) != mask) in dbAllocNext()
1182 return -ENOSPC; in dbAllocNext()
1200 return -ENOSPC; in dbAllocNext()
1212 nwords -= nw; in dbAllocNext()
1225 * NAME: dbAllocNear()
1236 * bmp - pointer to bmap descriptor
1237 * dp - pointer to dmap.
1238 * blkno - block number to allocate near.
1239 * nblocks - actual number of contiguous free blocks desired.
1240 * l2nb - log2 number of contiguous free blocks desired.
1241 * results - on successful return, set to the starting block number
1245 * 0 - success
1246 * -ENOSPC - insufficient disk resources
1247 * -EIO - i/o error
1255 int word, lword, rc; in dbAllocNear() local
1258 if (dp->tree.leafidx != cpu_to_le32(LEAFIND)) { in dbAllocNear()
1259 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmap page\n"); in dbAllocNear()
1260 return -EIO; in dbAllocNear()
1263 leaf = dp->tree.stree + le32_to_cpu(dp->tree.leafidx); in dbAllocNear()
1269 word = (blkno & (BPERDMAP - 1)) >> L2DBWORD; in dbAllocNear()
1283 blkno = le64_to_cpu(dp->start) + (word << L2DBWORD); in dbAllocNear()
1292 dbFindBits(le32_to_cpu(dp->wmap[word]), l2nb); in dbAllocNear()
1296 if ((rc = dbAllocDmap(bmp, dp, blkno, nblocks)) == 0) in dbAllocNear()
1299 return (rc); in dbAllocNear()
1302 return -ENOSPC; in dbAllocNear()
1307 * NAME: dbAllocAG()
1323 * or two sub-trees, depending on the allocation group size.
1346 * bmp - pointer to bmap descriptor
1347 * agno - allocation group number.
1348 * nblocks - actual number of contiguous free blocks desired.
1349 * l2nb - log2 number of contiguous free blocks desired.
1350 * results - on successful return, set to the starting block number
1354 * 0 - success
1355 * -ENOSPC - insufficient disk resources
1356 * -EIO - i/o error
1365 int rc, ti, i, k, m, n, agperlev; in dbAllocAG() local
1372 if (l2nb > bmp->db_agl2size) { in dbAllocAG()
1373 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocAG()
1375 return -EIO; in dbAllocAG()
1381 blkno = (s64) agno << bmp->db_agl2size; in dbAllocAG()
1400 if (bmp->db_agsize == BPERDMAP in dbAllocAG()
1401 || bmp->db_agfree[agno] == bmp->db_agsize) { in dbAllocAG()
1402 rc = dbAllocCtl(bmp, nblocks, l2nb, blkno, results); in dbAllocAG()
1403 if ((rc == -ENOSPC) && in dbAllocAG()
1404 (bmp->db_agfree[agno] == bmp->db_agsize)) { in dbAllocAG()
1408 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocAG()
1411 return (rc); in dbAllocAG()
1417 lblkno = BLKTOCTL(blkno, bmp->db_l2nbperpage, bmp->db_aglevel); in dbAllocAG()
1418 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); in dbAllocAG()
1420 return -EIO; in dbAllocAG()
1421 dcp = (struct dmapctl *) mp->data; in dbAllocAG()
1422 budmin = dcp->budmin; in dbAllocAG()
1424 if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) { in dbAllocAG()
1425 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmapctl page\n"); in dbAllocAG()
1427 return -EIO; in dbAllocAG()
1438 (1 << (L2LPERCTL - (bmp->db_agheight << 1))) / bmp->db_agwidth; in dbAllocAG()
1439 ti = bmp->db_agstart + bmp->db_agwidth * (agno & (agperlev - 1)); in dbAllocAG()
1441 /* dmap control page trees fan-out by 4 and a single allocation in dbAllocAG()
1447 for (i = 0; i < bmp->db_agwidth; i++, ti++) { in dbAllocAG()
1450 if (l2nb > dcp->stree[ti]) in dbAllocAG()
1457 for (k = bmp->db_agheight; k > 0; k--) { in dbAllocAG()
1459 if (l2nb <= dcp->stree[m + n]) { in dbAllocAG()
1465 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocAG()
1468 return -EIO; in dbAllocAG()
1475 if (bmp->db_aglevel == 2) in dbAllocAG()
1477 else if (bmp->db_aglevel == 1) in dbAllocAG()
1478 blkno &= ~(MAXL1SIZE - 1); in dbAllocAG()
1479 else /* bmp->db_aglevel == 0 */ in dbAllocAG()
1480 blkno &= ~(MAXL0SIZE - 1); in dbAllocAG()
1483 ((s64) (ti - le32_to_cpu(dcp->leafidx))) << budmin; in dbAllocAG()
1501 if ((rc = in dbAllocAG()
1502 dbFindCtl(bmp, l2nb, bmp->db_aglevel - 1, in dbAllocAG()
1504 if (rc == -ENOSPC) { in dbAllocAG()
1505 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocAG()
1507 return -EIO; in dbAllocAG()
1509 return (rc); in dbAllocAG()
1515 rc = dbAllocCtl(bmp, nblocks, l2nb, blkno, results); in dbAllocAG()
1516 if (rc == -ENOSPC) { in dbAllocAG()
1517 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocAG()
1519 rc = -EIO; in dbAllocAG()
1521 return (rc); in dbAllocAG()
1525 * return -ENOSPC. in dbAllocAG()
1529 return -ENOSPC; in dbAllocAG()
1534 * NAME: dbAllocAny()
1546 * bmp - pointer to bmap descriptor
1547 * nblocks - actual number of contiguous free blocks desired.
1548 * l2nb - log2 number of contiguous free blocks desired.
1549 * results - on successful return, set to the starting block number
1553 * 0 - success
1554 * -ENOSPC - insufficient disk resources
1555 * -EIO - i/o error
1561 int rc; in dbAllocAny() local
1570 if ((rc = dbFindCtl(bmp, l2nb, bmp->db_maxlevel, &blkno))) in dbAllocAny()
1571 return (rc); in dbAllocAny()
1575 rc = dbAllocCtl(bmp, nblocks, l2nb, blkno, results); in dbAllocAny()
1576 if (rc == -ENOSPC) { in dbAllocAny()
1577 jfs_error(bmp->db_ipbmap->i_sb, "unable to allocate blocks\n"); in dbAllocAny()
1578 return -EIO; in dbAllocAny()
1580 return (rc); in dbAllocAny()
1585 * NAME: dbDiscardAG()
1596 * - we work only on one ag at some time, minimizing how long we
1598 * - reading / writing the fs is possible most time, even on
1602 * - we write two times to the dmapctl and dmap pages
1603 * - but for me, this seems the best way, better ideas?
1607 * ip - pointer to in-core inode
1608 * agno - ag to trim
1609 * minlen - minimum value of contiguous blocks
1612 * s64 - actual number of blocks trimmed
1616 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap; in dbDiscardAG()
1617 struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap; in dbDiscardAG()
1620 int rc, l2nb; in dbDiscardAG() local
1621 struct super_block *sb = ipbmap->i_sb; in dbDiscardAG()
1635 nblocks = bmp->db_agfree[agno]; in dbDiscardAG()
1641 jfs_error(bmp->db_ipbmap->i_sb, "no memory for trim array\n"); in dbDiscardAG()
1650 /* 0 = okay, -EIO = fatal, -ENOSPC -> try smaller block */ in dbDiscardAG()
1651 rc = dbAllocAG(bmp, agno, nblocks, l2nb, &blkno); in dbDiscardAG()
1652 if (rc == 0) { in dbDiscardAG()
1653 tt->blkno = blkno; in dbDiscardAG()
1654 tt->nblocks = nblocks; in dbDiscardAG()
1658 if (bmp->db_agfree[agno] == 0) in dbDiscardAG()
1662 nblocks = bmp->db_agfree[agno]; in dbDiscardAG()
1664 } else if (rc == -ENOSPC) { in dbDiscardAG()
1666 l2nb = BLKSTOL2(nblocks) - 1; in dbDiscardAG()
1670 jfs_error(bmp->db_ipbmap->i_sb, "-EIO\n"); in dbDiscardAG()
1675 if (unlikely(count >= range_cnt - 1)) in dbDiscardAG()
1680 tt->nblocks = 0; /* mark the current end */ in dbDiscardAG()
1681 for (tt = totrim; tt->nblocks != 0; tt++) { in dbDiscardAG()
1684 if (!(JFS_SBI(sb)->flag & JFS_DISCARD)) in dbDiscardAG()
1685 jfs_issue_discard(ip, tt->blkno, tt->nblocks); in dbDiscardAG()
1686 dbFree(ip, tt->blkno, tt->nblocks); in dbDiscardAG()
1687 trimmed += tt->nblocks; in dbDiscardAG()
1695 * NAME: dbFindCtl()
1708 * bmp - pointer to bmap descriptor
1709 * level - starting dmap control page level.
1710 * l2nb - log2 number of contiguous free blocks desired.
1711 * *blkno - on entry, starting block number for conducting the search.
1716 * 0 - success
1717 * -ENOSPC - insufficient disk resources
1718 * -EIO - i/o error
1724 int rc, leafidx, lev; in dbFindCtl() local
1735 for (lev = level, b = *blkno; lev >= 0; lev--) { in dbFindCtl()
1739 lblkno = BLKTOCTL(b, bmp->db_l2nbperpage, lev); in dbFindCtl()
1740 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); in dbFindCtl()
1742 return -EIO; in dbFindCtl()
1743 dcp = (struct dmapctl *) mp->data; in dbFindCtl()
1744 budmin = dcp->budmin; in dbFindCtl()
1746 if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) { in dbFindCtl()
1747 jfs_error(bmp->db_ipbmap->i_sb, in dbFindCtl()
1750 return -EIO; in dbFindCtl()
1758 rc = dbFindLeaf((dmtree_t *) dcp, l2nb, &leafidx); in dbFindCtl()
1766 if (rc) { in dbFindCtl()
1768 jfs_error(bmp->db_ipbmap->i_sb, in dbFindCtl()
1770 return -EIO; in dbFindCtl()
1772 return -ENOSPC; in dbFindCtl()
1796 * NAME: dbAllocCtl()
1825 * bmp - pointer to bmap descriptor
1826 * nblocks - actual number of contiguous free blocks to allocate.
1827 * l2nb - log2 number of contiguous free blocks to allocate.
1828 * blkno - starting block number of the dmap to start the allocation
1830 * results - on successful return, set to the starting block number
1834 * 0 - success
1835 * -ENOSPC - insufficient disk resources
1836 * -EIO - i/o error
1843 int rc, nb; in dbAllocCtl() local
1853 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); in dbAllocCtl()
1854 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); in dbAllocCtl()
1856 return -EIO; in dbAllocCtl()
1857 dp = (struct dmap *) mp->data; in dbAllocCtl()
1861 rc = dbAllocDmapLev(bmp, dp, (int) nblocks, l2nb, results); in dbAllocCtl()
1862 if (rc == 0) in dbAllocCtl()
1867 return (rc); in dbAllocCtl()
1873 assert((blkno & (BPERDMAP - 1)) == 0); in dbAllocCtl()
1877 for (n = nblocks, b = blkno; n > 0; n -= nb, b += nb) { in dbAllocCtl()
1880 lblkno = BLKTODMAP(b, bmp->db_l2nbperpage); in dbAllocCtl()
1881 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); in dbAllocCtl()
1883 rc = -EIO; in dbAllocCtl()
1886 dp = (struct dmap *) mp->data; in dbAllocCtl()
1890 if (dp->tree.stree[ROOT] != L2BPERDMAP) { in dbAllocCtl()
1892 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocCtl()
1894 rc = -EIO; in dbAllocCtl()
1904 if ((rc = dbAllocDmap(bmp, dp, b, nb))) { in dbAllocCtl()
1929 for (n = nblocks - n, b = blkno; n > 0; in dbAllocCtl()
1930 n -= BPERDMAP, b += BPERDMAP) { in dbAllocCtl()
1933 lblkno = BLKTODMAP(b, bmp->db_l2nbperpage); in dbAllocCtl()
1934 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); in dbAllocCtl()
1939 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocCtl()
1943 dp = (struct dmap *) mp->data; in dbAllocCtl()
1952 jfs_error(bmp->db_ipbmap->i_sb, "Block Leakage\n"); in dbAllocCtl()
1961 return (rc); in dbAllocCtl()
1966 * NAME: dbAllocDmapLev()
1976 * mp - pointer to bmap descriptor
1977 * dp - pointer to dmap to attempt to allocate blocks from.
1978 * l2nb - log2 number of contiguous block desired.
1979 * nblocks - actual number of contiguous block desired.
1980 * results - on successful return, set to the starting block number
1984 * 0 - success
1985 * -ENOSPC - insufficient disk resources
1986 * -EIO - i/o error
1996 int leafidx, rc; in dbAllocDmapLev() local
2005 if (dbFindLeaf((dmtree_t *) & dp->tree, l2nb, &leafidx)) in dbAllocDmapLev()
2006 return -ENOSPC; in dbAllocDmapLev()
2011 blkno = le64_to_cpu(dp->start) + (leafidx << L2DBWORD); in dbAllocDmapLev()
2017 if (dp->tree.stree[leafidx + LEAFIND] < BUDMIN) in dbAllocDmapLev()
2018 blkno += dbFindBits(le32_to_cpu(dp->wmap[leafidx]), l2nb); in dbAllocDmapLev()
2021 if ((rc = dbAllocDmap(bmp, dp, blkno, nblocks)) == 0) in dbAllocDmapLev()
2024 return (rc); in dbAllocDmapLev()
2029 * NAME: dbAllocDmap()
2031 * FUNCTION: adjust the disk allocation map to reflect the allocation
2044 * bmp - pointer to bmap descriptor
2045 * dp - pointer to dmap to allocate the block range from.
2046 * blkno - starting block number of the block to be allocated.
2047 * nblocks - number of blocks to be allocated.
2050 * 0 - success
2051 * -EIO - i/o error
2059 int rc; in dbAllocDmap() local
2064 oldroot = dp->tree.stree[ROOT]; in dbAllocDmap()
2070 if (dp->tree.stree[ROOT] == oldroot) in dbAllocDmap()
2077 if ((rc = dbAdjCtl(bmp, blkno, dp->tree.stree[ROOT], 1, 0))) in dbAllocDmap()
2080 return (rc); in dbAllocDmap()
2085 * NAME: dbFreeDmap()
2087 * FUNCTION: adjust the disk allocation map to reflect the allocation
2099 * bmp - pointer to bmap descriptor
2100 * dp - pointer to dmap to free the block range from.
2101 * blkno - starting block number of the block to be freed.
2102 * nblocks - number of blocks to be freed.
2105 * 0 - success
2106 * -EIO - i/o error
2114 int rc = 0, word; in dbFreeDmap() local
2119 oldroot = dp->tree.stree[ROOT]; in dbFreeDmap()
2122 rc = dbFreeBits(bmp, dp, blkno, nblocks); in dbFreeDmap()
2125 if (rc || (dp->tree.stree[ROOT] == oldroot)) in dbFreeDmap()
2126 return (rc); in dbFreeDmap()
2132 if ((rc = dbAdjCtl(bmp, blkno, dp->tree.stree[ROOT], 0, 0))) { in dbFreeDmap()
2133 word = (blkno & (BPERDMAP - 1)) >> L2DBWORD; in dbFreeDmap()
2140 if (dp->tree.stree[word] == NOFREE) in dbFreeDmap()
2141 dbBackSplit((dmtree_t *) & dp->tree, word); in dbFreeDmap()
2146 return (rc); in dbFreeDmap()
2151 * NAME: dbAllocBits()
2157 * updates the bits of the working map and causes the adjustment
2163 * bmp - pointer to bmap descriptor
2164 * dp - pointer to dmap to allocate bits from.
2165 * blkno - starting block number of the bits to be allocated.
2166 * nblocks - number of bits to be allocated.
2176 dmtree_t *tp = (dmtree_t *) & dp->tree; in dbAllocBits()
2181 leaf = dp->tree.stree + LEAFIND; in dbAllocBits()
2186 dbitno = blkno & (BPERDMAP - 1); in dbAllocBits()
2205 for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) { in dbAllocBits()
2209 wbitno = dbitno & (DBWORD - 1); in dbAllocBits()
2210 nb = min(rembits, DBWORD - wbitno); in dbAllocBits()
2218 dp->wmap[word] |= cpu_to_le32(ONES << (DBWORD - nb) in dbAllocBits()
2227 dbMaxBud((u8 *) & dp->wmap[word])); in dbAllocBits()
2237 memset(&dp->wmap[word], (int) ONES, nwords * 4); in dbAllocBits()
2246 for (; nwords > 0; nwords -= nw) { in dbAllocBits()
2248 jfs_error(bmp->db_ipbmap->i_sb, in dbAllocBits()
2277 le32_add_cpu(&dp->nfree, -nblocks); in dbAllocBits()
2285 agno = blkno >> bmp->db_agl2size; in dbAllocBits()
2286 if (agno > bmp->db_maxag) in dbAllocBits()
2287 bmp->db_maxag = agno; in dbAllocBits()
2289 /* update the free count for the allocation group and map */ in dbAllocBits()
2290 bmp->db_agfree[agno] -= nblocks; in dbAllocBits()
2291 bmp->db_nfree -= nblocks; in dbAllocBits()
2298 * NAME: dbFreeBits()
2304 * updates the bits of the working map and causes the adjustment
2310 * bmp - pointer to bmap descriptor
2311 * dp - pointer to dmap to free bits from.
2312 * blkno - starting block number of the bits to be freed.
2313 * nblocks - number of bits to be freed.
2323 dmtree_t *tp = (dmtree_t *) & dp->tree; in dbFreeBits()
2324 int rc = 0; in dbFreeBits() local
2330 dbitno = blkno & (BPERDMAP - 1); in dbFreeBits()
2354 for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) { in dbFreeBits()
2358 wbitno = dbitno & (DBWORD - 1); in dbFreeBits()
2359 nb = min(rembits, DBWORD - wbitno); in dbFreeBits()
2367 dp->wmap[word] &= in dbFreeBits()
2368 cpu_to_le32(~(ONES << (DBWORD - nb) in dbFreeBits()
2373 rc = dbJoin(tp, word, in dbFreeBits()
2374 dbMaxBud((u8 *) & dp->wmap[word])); in dbFreeBits()
2375 if (rc) in dbFreeBits()
2376 return rc; in dbFreeBits()
2385 memset(&dp->wmap[word], 0, nwords * 4); in dbFreeBits()
2394 for (; nwords > 0; nwords -= nw) { in dbFreeBits()
2407 rc = dbJoin(tp, word, size); in dbFreeBits()
2408 if (rc) in dbFreeBits()
2409 return rc; in dbFreeBits()
2421 le32_add_cpu(&dp->nfree, nblocks); in dbFreeBits()
2426 * map. in dbFreeBits()
2428 agno = blkno >> bmp->db_agl2size; in dbFreeBits()
2429 bmp->db_nfree += nblocks; in dbFreeBits()
2430 bmp->db_agfree[agno] += nblocks; in dbFreeBits()
2437 if ((bmp->db_agfree[agno] == bmp->db_agsize && agno == bmp->db_maxag) || in dbFreeBits()
2438 (agno == bmp->db_numag - 1 && in dbFreeBits()
2439 bmp->db_agfree[agno] == (bmp-> db_mapsize & (BPERDMAP - 1)))) { in dbFreeBits()
2440 while (bmp->db_maxag > 0) { in dbFreeBits()
2441 bmp->db_maxag -= 1; in dbFreeBits()
2442 if (bmp->db_agfree[bmp->db_maxag] != in dbFreeBits()
2443 bmp->db_agsize) in dbFreeBits()
2447 /* re-establish the allocation group preference if the in dbFreeBits()
2451 if (bmp->db_agpref > bmp->db_maxag) in dbFreeBits()
2452 bmp->db_agpref = bmp->db_maxag; in dbFreeBits()
2462 * NAME: dbAdjCtl()
2486 * bmp - pointer to bmap descriptor
2487 * blkno - the first block of a block range within a dmap. it is
2490 * newval - the new value of the lower level dmap or dmap control
2492 * alloc - 'true' if adjustment is due to an allocation.
2493 * level - current level of dmap control page (i.e. L0, L1, L2) to
2497 * 0 - success
2498 * -EIO - i/o error
2510 int rc, leafno, ti; in dbAdjCtl() local
2515 lblkno = BLKTOCTL(blkno, bmp->db_l2nbperpage, level); in dbAdjCtl()
2516 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0); in dbAdjCtl()
2518 return -EIO; in dbAdjCtl()
2519 dcp = (struct dmapctl *) mp->data; in dbAdjCtl()
2521 if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) { in dbAdjCtl()
2522 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmapctl page\n"); in dbAdjCtl()
2524 return -EIO; in dbAdjCtl()
2530 leafno = BLKTOCTLLEAF(blkno, dcp->budmin); in dbAdjCtl()
2531 ti = leafno + le32_to_cpu(dcp->leafidx); in dbAdjCtl()
2536 oldval = dcp->stree[ti]; in dbAdjCtl()
2537 oldroot = dcp->stree[ROOT]; in dbAdjCtl()
2559 rc = dbBackSplit((dmtree_t *) dcp, leafno); in dbAdjCtl()
2560 if (rc) in dbAdjCtl()
2561 return rc; in dbAdjCtl()
2562 oldval = dcp->stree[ti]; in dbAdjCtl()
2564 dbSplit((dmtree_t *) dcp, leafno, dcp->budmin, newval); in dbAdjCtl()
2566 rc = dbJoin((dmtree_t *) dcp, leafno, newval); in dbAdjCtl()
2567 if (rc) in dbAdjCtl()
2568 return rc; in dbAdjCtl()
2573 * the current top level (i.e. L0, L1, L2) of the map. if so (i.e. in dbAdjCtl()
2578 if (dcp->stree[ROOT] != oldroot) { in dbAdjCtl()
2579 /* are we below the top level of the map. if so, in dbAdjCtl()
2582 if (level < bmp->db_maxlevel) { in dbAdjCtl()
2586 if ((rc = in dbAdjCtl()
2587 dbAdjCtl(bmp, blkno, dcp->stree[ROOT], alloc, in dbAdjCtl()
2603 if (dcp->stree[ti] == NOFREE) in dbAdjCtl()
2607 dcp->budmin, oldval); in dbAdjCtl()
2613 return (rc); in dbAdjCtl()
2616 /* we're at the top level of the map. update in dbAdjCtl()
2620 assert(level == bmp->db_maxlevel); in dbAdjCtl()
2621 if (bmp->db_maxfreebud != oldroot) { in dbAdjCtl()
2622 jfs_error(bmp->db_ipbmap->i_sb, in dbAdjCtl()
2625 bmp->db_maxfreebud = dcp->stree[ROOT]; in dbAdjCtl()
2638 * NAME: dbSplit()
2645 * tp - pointer to the tree containing the leaf.
2646 * leafno - the number of the leaf to be updated.
2647 * splitsz - the size the binary buddy system starting at the leaf
2649 * newval - the new value for the leaf.
2659 s8 *leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx); in dbSplit()
2663 if (leaf[leafno] > tp->dmt_budmin) { in dbSplit()
2667 * - 1 in l2) and the corresponding buddy size. in dbSplit()
2669 cursz = leaf[leafno] - 1; in dbSplit()
2670 budsz = BUDSIZE(cursz, tp->dmt_budmin); in dbSplit()
2681 cursz -= 1; in dbSplit()
2694 * NAME: dbBackSplit()
2713 * tp - pointer to the tree containing the leaf.
2714 * leafno - the number of the leaf to be updated.
2724 s8 *leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx); in dbBackSplit()
2739 LITOL2BSZ(leafno, le32_to_cpu(tp->dmt_l2nleafs), in dbBackSplit()
2740 tp->dmt_budmin); in dbBackSplit()
2746 budsz = BUDSIZE(size, tp->dmt_budmin); in dbBackSplit()
2755 if (bsz >= le32_to_cpu(tp->dmt_nleafs)) { in dbBackSplit()
2756 jfs_err("JFS: block map error in dbBackSplit"); in dbBackSplit()
2757 return -EIO; in dbBackSplit()
2770 cursz = leaf[bud] - 1; in dbBackSplit()
2779 return -EIO; in dbBackSplit()
2786 * NAME: dbJoin()
2789 * the leaf with other leaves of the dmtree into a multi-leaf
2793 * tp - pointer to the tree containing the leaf.
2794 * leafno - the number of the leaf to be updated.
2795 * newval - the new value for the leaf.
2806 if (newval >= tp->dmt_budmin) { in dbJoin()
2809 leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx); in dbJoin()
2824 budsz = BUDSIZE(newval, tp->dmt_budmin); in dbJoin()
2828 while (budsz < le32_to_cpu(tp->dmt_nleafs)) { in dbJoin()
2841 return -EIO; in dbJoin()
2879 * NAME: dbAdjTree()
2887 * tp - pointer to the tree to be adjusted.
2888 * leafno - the number of the leaf to be updated.
2889 * newval - the new value for the leaf.
2900 lp = leafno + le32_to_cpu(tp->dmt_leafidx); in dbAdjTree()
2905 if (tp->dmt_stree[lp] == newval) in dbAdjTree()
2910 tp->dmt_stree[lp] = newval; in dbAdjTree()
2914 for (k = 0; k < le32_to_cpu(tp->dmt_height); k++) { in dbAdjTree()
2918 lp = ((lp - 1) & ~0x03) + 1; in dbAdjTree()
2922 pp = (lp - 1) >> 2; in dbAdjTree()
2926 max = TREEMAX(&tp->dmt_stree[lp]); in dbAdjTree()
2931 if (tp->dmt_stree[pp] == max) in dbAdjTree()
2936 tp->dmt_stree[pp] = max; in dbAdjTree()
2938 /* parent becomes leaf for next go-round. in dbAdjTree()
2946 * NAME: dbFindLeaf()
2957 * tp - pointer to the tree to be searched.
2958 * l2nb - log2 number of free blocks to search for.
2959 * leafidx - return pointer to be set to the index of the leaf
2964 * 0 - success
2965 * -ENOSPC - insufficient free blocks.
2974 if (l2nb > tp->dmt_stree[ROOT]) in dbFindLeaf()
2975 return -ENOSPC; in dbFindLeaf()
2981 for (k = le32_to_cpu(tp->dmt_height), ti = 1; in dbFindLeaf()
2982 k > 0; k--, ti = ((ti + n) << 2) + 1) { in dbFindLeaf()
2990 if (l2nb <= tp->dmt_stree[x + n]) in dbFindLeaf()
3003 *leafidx = x + n - le32_to_cpu(tp->dmt_leafidx); in dbFindLeaf()
3010 * NAME: dbFindBits()
3019 * word - dmap bitmap word value.
3020 * l2nb - number of free bits specified as a log2 number.
3039 mask = ONES << (DBWORD - nb); in dbFindBits()
3057 * NAME: dbMaxBud(u8 *cp)
3060 * bits within 32-bits of the map.
3063 * cp - pointer to the 32-bit value.
3079 * free buddy size is BUDMIN-1. in dbMaxBud()
3082 return (BUDMIN - 1); in dbMaxBud()
3094 * NAME: cnttz(uint word)
3096 * FUNCTION: determine the number of trailing zeros within a 32-bit
3100 * value - 32-bit value to be examined.
3119 * NAME: cntlz(u32 value)
3121 * FUNCTION: determine the number of leading zeros within a 32-bit
3125 * value - 32-bit value to be examined.
3143 * NAME: blkstol2(s64 nb)
3150 * nb - number of blocks
3160 mask = (s64) 1 << (64 - 1); in blkstol2()
3170 l2nb = (64 - 1) - l2nb; in blkstol2()
3186 * NAME: dbAllocBottomUp()
3189 * allocation map.
3191 * the blocks will be alloc from the working map one dmap
3195 * ip - pointer to in-core inode;
3196 * blkno - starting block number to be freed.
3197 * nblocks - number of blocks to be freed.
3200 * 0 - success
3201 * -EIO - i/o error
3207 int nb, rc; in dbAllocBottomUp() local
3209 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap; in dbAllocBottomUp()
3210 struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap; in dbAllocBottomUp()
3215 ASSERT(nblocks <= bmp->db_mapsize - blkno); in dbAllocBottomUp()
3221 for (rem = nblocks; rem > 0; rem -= nb, blkno += nb) { in dbAllocBottomUp()
3228 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage); in dbAllocBottomUp()
3232 return -EIO; in dbAllocBottomUp()
3234 dp = (struct dmap *) mp->data; in dbAllocBottomUp()
3239 nb = min(rem, BPERDMAP - (blkno & (BPERDMAP - 1))); in dbAllocBottomUp()
3242 if ((rc = dbAllocDmapBU(bmp, dp, blkno, nb))) { in dbAllocBottomUp()
3245 return (rc); in dbAllocBottomUp()
3261 int rc; in dbAllocDmapBU() local
3264 struct dmaptree *tp = (struct dmaptree *) & dp->tree; in dbAllocDmapBU()
3269 oldroot = tp->stree[ROOT]; in dbAllocDmapBU()
3274 dbitno = blkno & (BPERDMAP - 1); in dbAllocDmapBU()
3293 for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) { in dbAllocDmapBU()
3297 wbitno = dbitno & (DBWORD - 1); in dbAllocDmapBU()
3298 nb = min(rembits, DBWORD - wbitno); in dbAllocDmapBU()
3306 dp->wmap[word] |= cpu_to_le32(ONES << (DBWORD - nb) in dbAllocDmapBU()
3317 memset(&dp->wmap[word], (int) ONES, nwords * 4); in dbAllocDmapBU()
3326 le32_add_cpu(&dp->nfree, -nblocks); in dbAllocDmapBU()
3337 agno = blkno >> bmp->db_agl2size; in dbAllocDmapBU()
3338 if (agno > bmp->db_maxag) in dbAllocDmapBU()
3339 bmp->db_maxag = agno; in dbAllocDmapBU()
3341 /* update the free count for the allocation group and map */ in dbAllocDmapBU()
3342 bmp->db_agfree[agno] -= nblocks; in dbAllocDmapBU()
3343 bmp->db_nfree -= nblocks; in dbAllocDmapBU()
3348 if (tp->stree[ROOT] == oldroot) in dbAllocDmapBU()
3355 if ((rc = dbAdjCtl(bmp, blkno, tp->stree[ROOT], 1, 0))) in dbAllocDmapBU()
3358 return (rc); in dbAllocDmapBU()
3363 * NAME: dbExtendFS()
3370 * L1---------------------------------L1
3372 * L0---------L0---------L0 L0---------L0---------L0
3377 * <---old---><----------------------------extend----------------------->
3381 struct jfs_sb_info *sbi = JFS_SBI(ipbmap->i_sb); in dbExtendFS()
3382 int nbperpage = sbi->nbperpage; in dbExtendFS()
3390 struct bmap *bmp = sbi->bmap; in dbExtendFS()
3407 bmp->db_mapsize = newsize; in dbExtendFS()
3408 bmp->db_maxlevel = BMAPSZTOLEV(bmp->db_mapsize); in dbExtendFS()
3412 oldl2agsize = bmp->db_agl2size; in dbExtendFS()
3414 bmp->db_agl2size = l2agsize; in dbExtendFS()
3415 bmp->db_agsize = 1 << l2agsize; in dbExtendFS()
3418 agno = bmp->db_numag; in dbExtendFS()
3419 bmp->db_numag = newsize >> l2agsize; in dbExtendFS()
3420 bmp->db_numag += ((u32) newsize % (u32) bmp->db_agsize) ? 1 : 0; in dbExtendFS()
3427 * i.e., (AGi, ..., AGj) where i = k*n and j = k*(n+1) - 1 to AGn; in dbExtendFS()
3432 k = 1 << (l2agsize - oldl2agsize); in dbExtendFS()
3433 ag_rem = bmp->db_agfree[0]; /* save agfree[0] */ in dbExtendFS()
3435 bmp->db_agfree[n] = 0; /* init collection point */ in dbExtendFS()
3440 bmp->db_agfree[n] += bmp->db_agfree[i]; in dbExtendFS()
3443 bmp->db_agfree[0] += ag_rem; /* restore agfree[0] */ in dbExtendFS()
3446 bmp->db_agfree[n] = 0; in dbExtendFS()
3452 bmp->db_maxag = bmp->db_maxag / k; in dbExtendFS()
3465 jfs_error(ipbmap->i_sb, "L2 page could not be read\n"); in dbExtendFS()
3466 return -EIO; in dbExtendFS()
3468 l2dcp = (struct dmapctl *) l2mp->data; in dbExtendFS()
3472 l2leaf = l2dcp->stree + CTLLEAFIND + k; in dbExtendFS()
3473 p = BLKTOL1(blkno, sbi->l2nbperpage); /* L1 page */ in dbExtendFS()
3481 /* read in L1 page: (blkno & (MAXL1SIZE - 1)) */ in dbExtendFS()
3485 l1dcp = (struct dmapctl *) l1mp->data; in dbExtendFS()
3488 j = (blkno & (MAXL1SIZE - 1)) >> L2MAXL0SIZE; in dbExtendFS()
3489 l1leaf = l1dcp->stree + CTLLEAFIND + j; in dbExtendFS()
3490 p = BLKTOL0(blkno, sbi->l2nbperpage); in dbExtendFS()
3498 l1dcp = (struct dmapctl *) l1mp->data; in dbExtendFS()
3502 l1leaf = l1dcp->stree + CTLLEAFIND; in dbExtendFS()
3512 /* read in L0 page: (blkno & (MAXL0SIZE - 1)) */ in dbExtendFS()
3517 l0dcp = (struct dmapctl *) l0mp->data; in dbExtendFS()
3520 i = (blkno & (MAXL0SIZE - 1)) >> in dbExtendFS()
3522 l0leaf = l0dcp->stree + CTLLEAFIND + i; in dbExtendFS()
3524 sbi->l2nbperpage); in dbExtendFS()
3532 l0dcp = (struct dmapctl *) l0mp->data; in dbExtendFS()
3536 l0leaf = l0dcp->stree + CTLLEAFIND; in dbExtendFS()
3548 if ((n = blkno & (BPERDMAP - 1))) { in dbExtendFS()
3554 n = min(nblocks, (s64)BPERDMAP - n); in dbExtendFS()
3565 dp = (struct dmap *) mp->data; in dbExtendFS()
3568 bmp->db_nfree += n; in dbExtendFS()
3569 agno = le64_to_cpu(dp->start) >> l2agsize; in dbExtendFS()
3570 bmp->db_agfree[agno] += n; in dbExtendFS()
3578 nblocks -= n; in dbExtendFS()
3599 bmp->db_maxfreebud = *l1leaf; in dbExtendFS()
3623 bmp->db_maxfreebud = *l2leaf; in dbExtendFS()
3630 jfs_error(ipbmap->i_sb, "function has not returned as expected\n"); in dbExtendFS()
3637 return -EIO; in dbExtendFS()
3653 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap; in dbFinalizeBmap()
3668 actags = bmp->db_maxag + 1; in dbFinalizeBmap()
3669 inactags = bmp->db_numag - actags; in dbFinalizeBmap()
3670 ag_rem = bmp->db_mapsize & (bmp->db_agsize - 1); /* ??? */ in dbFinalizeBmap()
3678 ((inactags - 1) << bmp->db_agl2size) + ag_rem in dbFinalizeBmap()
3679 : inactags << bmp->db_agl2size; in dbFinalizeBmap()
3685 actfree = bmp->db_nfree - inactfree; in dbFinalizeBmap()
3689 * re-establish the preferred group as the leftmost in dbFinalizeBmap()
3692 if (bmp->db_agfree[bmp->db_agpref] < avgfree) { in dbFinalizeBmap()
3693 for (bmp->db_agpref = 0; bmp->db_agpref < actags; in dbFinalizeBmap()
3694 bmp->db_agpref++) { in dbFinalizeBmap()
3695 if (bmp->db_agfree[bmp->db_agpref] >= avgfree) in dbFinalizeBmap()
3698 if (bmp->db_agpref >= bmp->db_numag) { in dbFinalizeBmap()
3699 jfs_error(ipbmap->i_sb, in dbFinalizeBmap()
3711 bmp->db_aglevel = BMAPSZTOLEV(bmp->db_agsize); in dbFinalizeBmap()
3713 bmp->db_agl2size - (L2BPERDMAP + bmp->db_aglevel * L2LPERCTL); in dbFinalizeBmap()
3714 bmp->db_agheight = l2nl >> 1; in dbFinalizeBmap()
3715 bmp->db_agwidth = 1 << (l2nl - (bmp->db_agheight << 1)); in dbFinalizeBmap()
3716 for (i = 5 - bmp->db_agheight, bmp->db_agstart = 0, n = 1; i > 0; in dbFinalizeBmap()
3717 i--) { in dbFinalizeBmap()
3718 bmp->db_agstart += n; in dbFinalizeBmap()
3726 * NAME: dbInitDmap()/ujfs_idmap_page()
3737 * dp - pointer to page of map
3738 * nblocks - number of blocks this page
3747 blkno = Blkno & (BPERDMAP - 1); in dbInitDmap()
3750 dp->nblocks = dp->nfree = cpu_to_le32(nblocks); in dbInitDmap()
3751 dp->start = cpu_to_le64(Blkno); in dbInitDmap()
3754 memset(&dp->wmap[0], 0, LPERDMAP * 4); in dbInitDmap()
3755 memset(&dp->pmap[0], 0, LPERDMAP * 4); in dbInitDmap()
3759 le32_add_cpu(&dp->nblocks, nblocks); in dbInitDmap()
3760 le32_add_cpu(&dp->nfree, nblocks); in dbInitDmap()
3771 for (r = nblocks; r > 0; r -= nb, blkno += nb) { in dbInitDmap()
3773 b = blkno & (DBWORD - 1); in dbInitDmap()
3775 nb = min(r, DBWORD - b); in dbInitDmap()
3780 dp->wmap[w] &= cpu_to_le32(~(ONES << (DBWORD - nb) in dbInitDmap()
3782 dp->pmap[w] &= cpu_to_le32(~(ONES << (DBWORD - nb) in dbInitDmap()
3790 memset(&dp->wmap[w], 0, nw * 4); in dbInitDmap()
3791 memset(&dp->pmap[w], 0, nw * 4); in dbInitDmap()
3800 * mark bits following the range to be freed (non-existing in dbInitDmap()
3810 /* does nblocks fall on a 32-bit boundary ? */ in dbInitDmap()
3811 b = blkno & (DBWORD - 1); in dbInitDmap()
3814 dp->wmap[w] = dp->pmap[w] = cpu_to_le32(ONES >> b); in dbInitDmap()
3820 dp->pmap[i] = dp->wmap[i] = cpu_to_le32(ONES); in dbInitDmap()
3831 * NAME: dbInitDmapTree()/ujfs_complete_dmap()
3838 * dp - dmap to complete
3839 * blkno - starting block number for this dmap
3840 * treemax - will be filled in with max free for this dmap
3851 tp = &dp->tree; in dbInitDmapTree()
3852 tp->nleafs = cpu_to_le32(LPERDMAP); in dbInitDmapTree()
3853 tp->l2nleafs = cpu_to_le32(L2LPERDMAP); in dbInitDmapTree()
3854 tp->leafidx = cpu_to_le32(LEAFIND); in dbInitDmapTree()
3855 tp->height = cpu_to_le32(4); in dbInitDmapTree()
3856 tp->budmin = BUDMIN; in dbInitDmapTree()
3859 * note: leaf is set to NOFREE(-1) if all blocks of corresponding in dbInitDmapTree()
3862 cp = tp->stree + le32_to_cpu(tp->leafidx); in dbInitDmapTree()
3864 *cp++ = dbMaxBud((u8 *) & dp->wmap[i]); in dbInitDmapTree()
3872 * NAME: dbInitTree()/ujfs_adjtree()
3883 * cp - Pointer to the root of the tree
3884 * l2leaves- Number of leaf nodes as a power of 2
3885 * l2min - Number of blocks that can be covered by a leaf
3896 tp = dtp->stree; in dbInitTree()
3899 l2max = le32_to_cpu(dtp->l2nleafs) + dtp->budmin; in dbInitTree()
3907 * the combination will result in the left-most buddy leaf having in dbInitTree()
3915 for (l2free = dtp->budmin, bsize = 1; l2free < l2max; in dbInitTree()
3921 for (i = 0, cp = tp + le32_to_cpu(dtp->leafidx); in dbInitTree()
3922 i < le32_to_cpu(dtp->nleafs); in dbInitTree()
3927 *(cp + bsize) = -1; /* right give left */ in dbInitTree()
3942 for (child = le32_to_cpu(dtp->leafidx), in dbInitTree()
3943 nparent = le32_to_cpu(dtp->nleafs) >> 2; in dbInitTree()
3946 parent = (child - 1) >> 2; in dbInitTree()
3969 dcp->nleafs = cpu_to_le32(LPERCTL); in dbInitDmapCtl()
3970 dcp->l2nleafs = cpu_to_le32(L2LPERCTL); in dbInitDmapCtl()
3971 dcp->leafidx = cpu_to_le32(CTLLEAFIND); in dbInitDmapCtl()
3972 dcp->height = cpu_to_le32(5); in dbInitDmapCtl()
3973 dcp->budmin = L2BPERDMAP + L2LPERCTL * level; in dbInitDmapCtl()
3980 cp = &dcp->stree[CTLLEAFIND + i]; in dbInitDmapCtl()
3990 * NAME: dbGetL2AGSize()/ujfs_getagl2size()
3995 * nblocks - Number of blocks in aggregate
4009 m = ((u64) 1 << (64 - 1)); in dbGetL2AGSize()
4010 for (l2sz = 64; l2sz >= 0; l2sz--, m >>= 1) { in dbGetL2AGSize()
4020 return (l2sz - L2MAXAG); in dbGetL2AGSize()
4025 * NAME: dbMapFileSizeToMapSize()
4027 * FUNCTION: compute number of blocks the block allocation map file
4028 * can cover from the map file size;
4030 * RETURNS: Number of blocks which can be covered by this block map file;
4034 * maximum number of map pages at each level including control pages
4040 * convert number of map pages to the zero origin top dmapctl level
4048 struct super_block *sb = ipbmap->i_sb; in dbMapFileSizeToMapSize()
4054 nblocks = ipbmap->i_size >> JFS_SBI(sb)->l2bsize; in dbMapFileSizeToMapSize()
4055 npages = nblocks >> JFS_SBI(sb)->l2nbperpage; in dbMapFileSizeToMapSize()
4063 npages--; /* skip the first global control page */ in dbMapFileSizeToMapSize()
4064 /* skip higher level control pages above top level covered by map */ in dbMapFileSizeToMapSize()
4065 npages -= (2 - level); in dbMapFileSizeToMapSize()
4066 npages--; /* skip top level's control page */ in dbMapFileSizeToMapSize()
4067 for (i = level; i >= 0; i--) { in dbMapFileSizeToMapSize()
4077 npages--; in dbMapFileSizeToMapSize()