2 * Copyright (C) International Business Machines Corp., 2000-2004
3 * Portions Copyright (C) Tino Reichardt, 2012
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
13 * the GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21 #include <linux/slab.h>
22 #include "jfs_incore.h"
23 #include "jfs_superblock.h"
27 #include "jfs_metapage.h"
28 #include "jfs_debug.h"
29 #include "jfs_discard.h"
32 * SERIALIZATION of the Block Allocation Map.
34 * the working state of the block allocation map is accessed in
37 * 1) allocation and free requests that start at the dmap
38 * level and move up through the dmap control pages (i.e.
39 * the vast majority of requests).
41 * 2) allocation requests that start at dmap control page
42 * level and work down towards the dmaps.
44 * the serialization scheme used here is as follows.
46 * requests which start at the bottom are serialized against each
47 * other through buffers and each requests holds onto its buffers
48 * as it works it way up from a single dmap to the required level
49 * of dmap control page.
50 * requests that start at the top are serialized against each other
51 * and request that start from the bottom by the multiple read/single
52 * write inode lock of the bmap inode. requests starting at the top
53 * take this lock in write mode while request starting at the bottom
54 * take the lock in read mode. a single top-down request may proceed
55 * exclusively while multiple bottoms-up requests may proceed
56 * simultaneously (under the protection of busy buffers).
58 * in addition to information found in dmaps and dmap control pages,
59 * the working state of the block allocation map also includes read/
60 * write information maintained in the bmap descriptor (i.e. total
61 * free block count, allocation group level free block counts).
62 * a single exclusive lock (BMAP_LOCK) is used to guard this information
63 * in the face of multiple-bottoms up requests.
64 * (lock ordering: IREAD_LOCK, BMAP_LOCK);
66 * accesses to the persistent state of the block allocation map (limited
67 * to the persistent bitmaps in dmaps) is guarded by (busy) buffers.
70 #define BMAP_LOCK_INIT(bmp) mutex_init(&bmp->db_bmaplock)
71 #define BMAP_LOCK(bmp) mutex_lock(&bmp->db_bmaplock)
72 #define BMAP_UNLOCK(bmp) mutex_unlock(&bmp->db_bmaplock)
77 static void dbAllocBits(struct bmap * bmp, struct dmap * dp, s64 blkno,
79 static void dbSplit(dmtree_t * tp, int leafno, int splitsz, int newval);
80 static int dbBackSplit(dmtree_t * tp, int leafno);
81 static int dbJoin(dmtree_t * tp, int leafno, int newval);
82 static void dbAdjTree(dmtree_t * tp, int leafno, int newval);
83 static int dbAdjCtl(struct bmap * bmp, s64 blkno, int newval, int alloc,
85 static int dbAllocAny(struct bmap * bmp, s64 nblocks, int l2nb, s64 * results);
86 static int dbAllocNext(struct bmap * bmp, struct dmap * dp, s64 blkno,
88 static int dbAllocNear(struct bmap * bmp, struct dmap * dp, s64 blkno,
90 int l2nb, s64 * results);
91 static int dbAllocDmap(struct bmap * bmp, struct dmap * dp, s64 blkno,
93 static int dbAllocDmapLev(struct bmap * bmp, struct dmap * dp, int nblocks,
96 static int dbAllocAG(struct bmap * bmp, int agno, s64 nblocks, int l2nb,
98 static int dbAllocCtl(struct bmap * bmp, s64 nblocks, int l2nb, s64 blkno,
100 static int dbExtend(struct inode *ip, s64 blkno, s64 nblocks, s64 addnblocks);
101 static int dbFindBits(u32 word, int l2nb);
102 static int dbFindCtl(struct bmap * bmp, int l2nb, int level, s64 * blkno);
103 static int dbFindLeaf(dmtree_t * tp, int l2nb, int *leafidx);
104 static int dbFreeBits(struct bmap * bmp, struct dmap * dp, s64 blkno,
106 static int dbFreeDmap(struct bmap * bmp, struct dmap * dp, s64 blkno,
108 static int dbMaxBud(u8 * cp);
109 static int blkstol2(s64 nb);
111 static int cntlz(u32 value);
112 static int cnttz(u32 word);
114 static int dbAllocDmapBU(struct bmap * bmp, struct dmap * dp, s64 blkno,
116 static int dbInitDmap(struct dmap * dp, s64 blkno, int nblocks);
117 static int dbInitDmapTree(struct dmap * dp);
118 static int dbInitTree(struct dmaptree * dtp);
119 static int dbInitDmapCtl(struct dmapctl * dcp, int level, int i);
120 static int dbGetL2AGSize(s64 nblocks);
125 * table used for determining buddy sizes within characters of
126 * dmap bitmap words. the characters themselves serve as indexes
127 * into the table, with the table elements yielding the maximum
128 * binary buddy of free bits within the character.
130 static const s8 budtab[256] = {
131 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
132 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
133 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
134 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
135 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
136 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
137 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
138 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
139 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
140 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
141 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
142 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
143 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
144 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
145 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
146 2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, -1
152 * FUNCTION: initializate the block allocation map.
154 * memory is allocated for the in-core bmap descriptor and
155 * the in-core descriptor is initialized from disk.
158 * ipbmap - pointer to in-core inode for the block map.
162 * -ENOMEM - insufficient memory
164 * -EINVAL - wrong bmap data
166 int dbMount(struct inode *ipbmap)
169 struct dbmap_disk *dbmp_le;
174 * allocate/initialize the in-memory bmap descriptor
176 /* allocate memory for the in-memory bmap descriptor */
177 bmp = kmalloc(sizeof(struct bmap), GFP_KERNEL);
181 /* read the on-disk bmap descriptor. */
182 mp = read_metapage(ipbmap,
183 BMAPBLKNO << JFS_SBI(ipbmap->i_sb)->l2nbperpage,
190 /* copy the on-disk bmap descriptor to its in-memory version. */
191 dbmp_le = (struct dbmap_disk *) mp->data;
192 bmp->db_mapsize = le64_to_cpu(dbmp_le->dn_mapsize);
193 bmp->db_nfree = le64_to_cpu(dbmp_le->dn_nfree);
194 bmp->db_l2nbperpage = le32_to_cpu(dbmp_le->dn_l2nbperpage);
195 bmp->db_numag = le32_to_cpu(dbmp_le->dn_numag);
196 if (!bmp->db_numag) {
197 release_metapage(mp);
202 bmp->db_maxlevel = le32_to_cpu(dbmp_le->dn_maxlevel);
203 bmp->db_maxag = le32_to_cpu(dbmp_le->dn_maxag);
204 bmp->db_agpref = le32_to_cpu(dbmp_le->dn_agpref);
205 bmp->db_aglevel = le32_to_cpu(dbmp_le->dn_aglevel);
206 bmp->db_agheight = le32_to_cpu(dbmp_le->dn_agheight);
207 bmp->db_agwidth = le32_to_cpu(dbmp_le->dn_agwidth);
208 bmp->db_agstart = le32_to_cpu(dbmp_le->dn_agstart);
209 bmp->db_agl2size = le32_to_cpu(dbmp_le->dn_agl2size);
210 for (i = 0; i < MAXAG; i++)
211 bmp->db_agfree[i] = le64_to_cpu(dbmp_le->dn_agfree[i]);
212 bmp->db_agsize = le64_to_cpu(dbmp_le->dn_agsize);
213 bmp->db_maxfreebud = dbmp_le->dn_maxfreebud;
215 /* release the buffer. */
216 release_metapage(mp);
218 /* bind the bmap inode and the bmap descriptor to each other. */
219 bmp->db_ipbmap = ipbmap;
220 JFS_SBI(ipbmap->i_sb)->bmap = bmp;
222 memset(bmp->db_active, 0, sizeof(bmp->db_active));
225 * allocate/initialize the bmap lock
236 * FUNCTION: terminate the block allocation map in preparation for
237 * file system unmount.
239 * the in-core bmap descriptor is written to disk and
240 * the memory for this descriptor is freed.
243 * ipbmap - pointer to in-core inode for the block map.
249 int dbUnmount(struct inode *ipbmap, int mounterror)
251 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap;
253 if (!(mounterror || isReadOnly(ipbmap)))
257 * Invalidate the page cache buffers
259 truncate_inode_pages(ipbmap->i_mapping, 0);
261 /* free the memory for the in-memory bmap. */
270 int dbSync(struct inode *ipbmap)
272 struct dbmap_disk *dbmp_le;
273 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap;
278 * write bmap global control page
280 /* get the buffer for the on-disk bmap descriptor. */
281 mp = read_metapage(ipbmap,
282 BMAPBLKNO << JFS_SBI(ipbmap->i_sb)->l2nbperpage,
285 jfs_err("dbSync: read_metapage failed!");
288 /* copy the in-memory version of the bmap to the on-disk version */
289 dbmp_le = (struct dbmap_disk *) mp->data;
290 dbmp_le->dn_mapsize = cpu_to_le64(bmp->db_mapsize);
291 dbmp_le->dn_nfree = cpu_to_le64(bmp->db_nfree);
292 dbmp_le->dn_l2nbperpage = cpu_to_le32(bmp->db_l2nbperpage);
293 dbmp_le->dn_numag = cpu_to_le32(bmp->db_numag);
294 dbmp_le->dn_maxlevel = cpu_to_le32(bmp->db_maxlevel);
295 dbmp_le->dn_maxag = cpu_to_le32(bmp->db_maxag);
296 dbmp_le->dn_agpref = cpu_to_le32(bmp->db_agpref);
297 dbmp_le->dn_aglevel = cpu_to_le32(bmp->db_aglevel);
298 dbmp_le->dn_agheight = cpu_to_le32(bmp->db_agheight);
299 dbmp_le->dn_agwidth = cpu_to_le32(bmp->db_agwidth);
300 dbmp_le->dn_agstart = cpu_to_le32(bmp->db_agstart);
301 dbmp_le->dn_agl2size = cpu_to_le32(bmp->db_agl2size);
302 for (i = 0; i < MAXAG; i++)
303 dbmp_le->dn_agfree[i] = cpu_to_le64(bmp->db_agfree[i]);
304 dbmp_le->dn_agsize = cpu_to_le64(bmp->db_agsize);
305 dbmp_le->dn_maxfreebud = bmp->db_maxfreebud;
307 /* write the buffer */
311 * write out dirty pages of bmap
313 filemap_write_and_wait(ipbmap->i_mapping);
315 diWriteSpecial(ipbmap, 0);
323 * FUNCTION: free the specified block range from the working block
326 * the blocks will be free from the working map one dmap
330 * ip - pointer to in-core inode;
331 * blkno - starting block number to be freed.
332 * nblocks - number of blocks to be freed.
338 int dbFree(struct inode *ip, s64 blkno, s64 nblocks)
344 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap;
345 struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap;
346 struct super_block *sb = ipbmap->i_sb;
348 IREAD_LOCK(ipbmap, RDWRLOCK_DMAP);
350 /* block to be freed better be within the mapsize. */
351 if (unlikely((blkno == 0) || (blkno + nblocks > bmp->db_mapsize))) {
352 IREAD_UNLOCK(ipbmap);
353 printk(KERN_ERR "blkno = %Lx, nblocks = %Lx\n",
354 (unsigned long long) blkno,
355 (unsigned long long) nblocks);
356 jfs_error(ip->i_sb, "block to be freed is outside the map\n");
361 * TRIM the blocks, when mounted with discard option
363 if (JFS_SBI(sb)->flag & JFS_DISCARD)
364 if (JFS_SBI(sb)->minblks_trim <= nblocks)
365 jfs_issue_discard(ipbmap, blkno, nblocks);
368 * free the blocks a dmap at a time.
371 for (rem = nblocks; rem > 0; rem -= nb, blkno += nb) {
372 /* release previous dmap if any */
377 /* get the buffer for the current dmap. */
378 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
379 mp = read_metapage(ipbmap, lblkno, PSIZE, 0);
381 IREAD_UNLOCK(ipbmap);
384 dp = (struct dmap *) mp->data;
386 /* determine the number of blocks to be freed from
389 nb = min(rem, BPERDMAP - (blkno & (BPERDMAP - 1)));
391 /* free the blocks. */
392 if ((rc = dbFreeDmap(bmp, dp, blkno, nb))) {
393 jfs_error(ip->i_sb, "error in block map\n");
394 release_metapage(mp);
395 IREAD_UNLOCK(ipbmap);
400 /* write the last buffer. */
403 IREAD_UNLOCK(ipbmap);
410 * NAME: dbUpdatePMap()
412 * FUNCTION: update the allocation state (free or allocate) of the
413 * specified block range in the persistent block allocation map.
415 * the blocks will be updated in the persistent map one
419 * ipbmap - pointer to in-core inode for the block map.
420 * free - 'true' if block range is to be freed from the persistent
421 * map; 'false' if it is to be allocated.
422 * blkno - starting block number of the range.
423 * nblocks - number of contiguous blocks in the range.
424 * tblk - transaction block;
431 dbUpdatePMap(struct inode *ipbmap,
432 int free, s64 blkno, s64 nblocks, struct tblock * tblk)
434 int nblks, dbitno, wbitno, rbits;
435 int word, nbits, nwords;
436 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap;
437 s64 lblkno, rem, lastlblkno;
442 int lsn, difft, diffp;
445 /* the blocks better be within the mapsize. */
446 if (blkno + nblocks > bmp->db_mapsize) {
447 printk(KERN_ERR "blkno = %Lx, nblocks = %Lx\n",
448 (unsigned long long) blkno,
449 (unsigned long long) nblocks);
450 jfs_error(ipbmap->i_sb, "blocks are outside the map\n");
454 /* compute delta of transaction lsn from log syncpt */
456 log = (struct jfs_log *) JFS_SBI(tblk->sb)->log;
457 logdiff(difft, lsn, log);
460 * update the block state a dmap at a time.
464 for (rem = nblocks; rem > 0; rem -= nblks, blkno += nblks) {
465 /* get the buffer for the current dmap. */
466 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
467 if (lblkno != lastlblkno) {
472 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE,
476 metapage_wait_for_io(mp);
478 dp = (struct dmap *) mp->data;
480 /* determine the bit number and word within the dmap of
481 * the starting block. also determine how many blocks
482 * are to be updated within this dmap.
484 dbitno = blkno & (BPERDMAP - 1);
485 word = dbitno >> L2DBWORD;
486 nblks = min(rem, (s64)BPERDMAP - dbitno);
488 /* update the bits of the dmap words. the first and last
489 * words may only have a subset of their bits updated. if
490 * this is the case, we'll work against that word (i.e.
491 * partial first and/or last) only in a single pass. a
492 * single pass will also be used to update all words that
493 * are to have all their bits updated.
495 for (rbits = nblks; rbits > 0;
496 rbits -= nbits, dbitno += nbits) {
497 /* determine the bit number within the word and
498 * the number of bits within the word.
500 wbitno = dbitno & (DBWORD - 1);
501 nbits = min(rbits, DBWORD - wbitno);
503 /* check if only part of the word is to be updated. */
504 if (nbits < DBWORD) {
505 /* update (free or allocate) the bits
509 (ONES << (DBWORD - nbits) >> wbitno);
519 /* one or more words are to have all
520 * their bits updated. determine how
521 * many words and how many bits.
523 nwords = rbits >> L2DBWORD;
524 nbits = nwords << L2DBWORD;
526 /* update (free or allocate) the bits
530 memset(&dp->pmap[word], 0,
533 memset(&dp->pmap[word], (int) ONES,
543 if (lblkno == lastlblkno)
548 LOGSYNC_LOCK(log, flags);
550 /* inherit older/smaller lsn */
551 logdiff(diffp, mp->lsn, log);
555 /* move bp after tblock in logsync list */
556 list_move(&mp->synclist, &tblk->synclist);
559 /* inherit younger/larger clsn */
560 logdiff(difft, tblk->clsn, log);
561 logdiff(diffp, mp->clsn, log);
563 mp->clsn = tblk->clsn;
568 /* insert bp after tblock in logsync list */
570 list_add(&mp->synclist, &tblk->synclist);
572 mp->clsn = tblk->clsn;
574 LOGSYNC_UNLOCK(log, flags);
577 /* write the last buffer. */
589 * FUNCTION: find the preferred allocation group for new allocations.
591 * Within the allocation groups, we maintain a preferred
592 * allocation group which consists of a group with at least
593 * average free space. It is the preferred group that we target
594 * new inode allocation towards. The tie-in between inode
595 * allocation and block allocation occurs as we allocate the
596 * first (data) block of an inode and specify the inode (block)
597 * as the allocation hint for this block.
599 * We try to avoid having more than one open file growing in
600 * an allocation group, as this will lead to fragmentation.
601 * This differs from the old OS/2 method of trying to keep
602 * empty ags around for large allocations.
605 * ipbmap - pointer to in-core inode for the block map.
608 * the preferred allocation group number.
610 int dbNextAG(struct inode *ipbmap)
617 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap;
621 /* determine the average number of free blocks within the ags. */
622 avgfree = (u32)bmp->db_nfree / bmp->db_numag;
625 * if the current preferred ag does not have an active allocator
626 * and has at least average freespace, return it
628 agpref = bmp->db_agpref;
629 if ((atomic_read(&bmp->db_active[agpref]) == 0) &&
630 (bmp->db_agfree[agpref] >= avgfree))
633 /* From the last preferred ag, find the next one with at least
634 * average free space.
636 for (i = 0 ; i < bmp->db_numag; i++, agpref++) {
637 if (agpref == bmp->db_numag)
640 if (atomic_read(&bmp->db_active[agpref]))
641 /* open file is currently growing in this ag */
643 if (bmp->db_agfree[agpref] >= avgfree) {
644 /* Return this one */
645 bmp->db_agpref = agpref;
647 } else if (bmp->db_agfree[agpref] > hwm) {
648 /* Less than avg. freespace, but best so far */
649 hwm = bmp->db_agfree[agpref];
655 * If no inactive ag was found with average freespace, use the
659 bmp->db_agpref = next_best;
660 /* else leave db_agpref unchanged */
664 /* return the preferred group.
666 return (bmp->db_agpref);
672 * FUNCTION: attempt to allocate a specified number of contiguous free
673 * blocks from the working allocation block map.
675 * the block allocation policy uses hints and a multi-step
678 * for allocation requests smaller than the number of blocks
679 * per dmap, we first try to allocate the new blocks
680 * immediately following the hint. if these blocks are not
681 * available, we try to allocate blocks near the hint. if
682 * no blocks near the hint are available, we next try to
683 * allocate within the same dmap as contains the hint.
685 * if no blocks are available in the dmap or the allocation
686 * request is larger than the dmap size, we try to allocate
687 * within the same allocation group as contains the hint. if
688 * this does not succeed, we finally try to allocate anywhere
689 * within the aggregate.
691 * we also try to allocate anywhere within the aggregate for
692 * for allocation requests larger than the allocation group
693 * size or requests that specify no hint value.
696 * ip - pointer to in-core inode;
697 * hint - allocation hint.
698 * nblocks - number of contiguous blocks in the range.
699 * results - on successful return, set to the starting block number
700 * of the newly allocated contiguous range.
704 * -ENOSPC - insufficient disk resources
707 int dbAlloc(struct inode *ip, s64 hint, s64 nblocks, s64 * results)
710 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap;
719 /* assert that nblocks is valid */
722 /* get the log2 number of blocks to be allocated.
723 * if the number of blocks is not a log2 multiple,
724 * it will be rounded up to the next log2 multiple.
726 l2nb = BLKSTOL2(nblocks);
728 bmp = JFS_SBI(ip->i_sb)->bmap;
730 mapSize = bmp->db_mapsize;
732 /* the hint should be within the map */
733 if (hint >= mapSize) {
734 jfs_error(ip->i_sb, "the hint is outside the map\n");
738 /* if the number of blocks to be allocated is greater than the
739 * allocation group size, try to allocate anywhere.
741 if (l2nb > bmp->db_agl2size) {
742 IWRITE_LOCK(ipbmap, RDWRLOCK_DMAP);
744 rc = dbAllocAny(bmp, nblocks, l2nb, results);
750 * If no hint, let dbNextAG recommend an allocation group
755 /* we would like to allocate close to the hint. adjust the
756 * hint to the block following the hint since the allocators
757 * will start looking for free space starting at this point.
761 if (blkno >= bmp->db_mapsize)
764 agno = blkno >> bmp->db_agl2size;
766 /* check if blkno crosses over into a new allocation group.
767 * if so, check if we should allow allocations within this
770 if ((blkno & (bmp->db_agsize - 1)) == 0)
771 /* check if the AG is currently being written to.
772 * if so, call dbNextAG() to find a non-busy
773 * AG with sufficient free space.
775 if (atomic_read(&bmp->db_active[agno]))
778 /* check if the allocation request size can be satisfied from a
779 * single dmap. if so, try to allocate from the dmap containing
780 * the hint using a tiered strategy.
782 if (nblocks <= BPERDMAP) {
783 IREAD_LOCK(ipbmap, RDWRLOCK_DMAP);
785 /* get the buffer for the dmap containing the hint.
788 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
789 mp = read_metapage(ipbmap, lblkno, PSIZE, 0);
793 dp = (struct dmap *) mp->data;
795 /* first, try to satisfy the allocation request with the
796 * blocks beginning at the hint.
798 if ((rc = dbAllocNext(bmp, dp, blkno, (int) nblocks))
802 mark_metapage_dirty(mp);
805 release_metapage(mp);
809 writers = atomic_read(&bmp->db_active[agno]);
811 ((writers == 1) && (JFS_IP(ip)->active_ag != agno))) {
813 * Someone else is writing in this allocation
814 * group. To avoid fragmenting, try another ag
816 release_metapage(mp);
817 IREAD_UNLOCK(ipbmap);
821 /* next, try to satisfy the allocation request with blocks
825 dbAllocNear(bmp, dp, blkno, (int) nblocks, l2nb, results))
828 mark_metapage_dirty(mp);
830 release_metapage(mp);
834 /* try to satisfy the allocation request with blocks within
835 * the same dmap as the hint.
837 if ((rc = dbAllocDmapLev(bmp, dp, (int) nblocks, l2nb, results))
840 mark_metapage_dirty(mp);
842 release_metapage(mp);
846 release_metapage(mp);
847 IREAD_UNLOCK(ipbmap);
850 /* try to satisfy the allocation request with blocks within
851 * the same allocation group as the hint.
853 IWRITE_LOCK(ipbmap, RDWRLOCK_DMAP);
854 if ((rc = dbAllocAG(bmp, agno, nblocks, l2nb, results)) != -ENOSPC)
857 IWRITE_UNLOCK(ipbmap);
862 * Let dbNextAG recommend a preferred allocation group
864 agno = dbNextAG(ipbmap);
865 IWRITE_LOCK(ipbmap, RDWRLOCK_DMAP);
867 /* Try to allocate within this allocation group. if that fails, try to
868 * allocate anywhere in the map.
870 if ((rc = dbAllocAG(bmp, agno, nblocks, l2nb, results)) == -ENOSPC)
871 rc = dbAllocAny(bmp, nblocks, l2nb, results);
874 IWRITE_UNLOCK(ipbmap);
879 IREAD_UNLOCK(ipbmap);
886 * NAME: dbAllocExact()
888 * FUNCTION: try to allocate the requested extent;
891 * ip - pointer to in-core inode;
892 * blkno - extent address;
893 * nblocks - extent length;
897 * -ENOSPC - insufficient disk resources
900 int dbAllocExact(struct inode *ip, s64 blkno, int nblocks)
903 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap;
904 struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap;
909 IREAD_LOCK(ipbmap, RDWRLOCK_DMAP);
912 * validate extent request:
914 * note: defragfs policy:
915 * max 64 blocks will be moved.
916 * allocation request size must be satisfied from a single dmap.
918 if (nblocks <= 0 || nblocks > BPERDMAP || blkno >= bmp->db_mapsize) {
919 IREAD_UNLOCK(ipbmap);
923 if (nblocks > ((s64) 1 << bmp->db_maxfreebud)) {
924 /* the free space is no longer available */
925 IREAD_UNLOCK(ipbmap);
929 /* read in the dmap covering the extent */
930 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
931 mp = read_metapage(ipbmap, lblkno, PSIZE, 0);
933 IREAD_UNLOCK(ipbmap);
936 dp = (struct dmap *) mp->data;
938 /* try to allocate the requested extent */
939 rc = dbAllocNext(bmp, dp, blkno, nblocks);
941 IREAD_UNLOCK(ipbmap);
944 mark_metapage_dirty(mp);
946 release_metapage(mp);
955 * FUNCTION: attempt to extend a current allocation by a specified
958 * this routine attempts to satisfy the allocation request
959 * by first trying to extend the existing allocation in
960 * place by allocating the additional blocks as the blocks
961 * immediately following the current allocation. if these
962 * blocks are not available, this routine will attempt to
963 * allocate a new set of contiguous blocks large enough
964 * to cover the existing allocation plus the additional
965 * number of blocks required.
968 * ip - pointer to in-core inode requiring allocation.
969 * blkno - starting block of the current allocation.
970 * nblocks - number of contiguous blocks within the current
972 * addnblocks - number of blocks to add to the allocation.
973 * results - on successful return, set to the starting block number
974 * of the existing allocation if the existing allocation
975 * was extended in place or to a newly allocated contiguous
976 * range if the existing allocation could not be extended
981 * -ENOSPC - insufficient disk resources
985 dbReAlloc(struct inode *ip,
986 s64 blkno, s64 nblocks, s64 addnblocks, s64 * results)
990 /* try to extend the allocation in place.
992 if ((rc = dbExtend(ip, blkno, nblocks, addnblocks)) == 0) {
1000 /* could not extend the allocation in place, so allocate a
1001 * new set of blocks for the entire request (i.e. try to get
1002 * a range of contiguous blocks large enough to cover the
1003 * existing allocation plus the additional blocks.)
1006 (ip, blkno + nblocks - 1, addnblocks + nblocks, results));
1013 * FUNCTION: attempt to extend a current allocation by a specified
1016 * this routine attempts to satisfy the allocation request
1017 * by first trying to extend the existing allocation in
1018 * place by allocating the additional blocks as the blocks
1019 * immediately following the current allocation.
1022 * ip - pointer to in-core inode requiring allocation.
1023 * blkno - starting block of the current allocation.
1024 * nblocks - number of contiguous blocks within the current
1026 * addnblocks - number of blocks to add to the allocation.
1030 * -ENOSPC - insufficient disk resources
1033 static int dbExtend(struct inode *ip, s64 blkno, s64 nblocks, s64 addnblocks)
1035 struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb);
1036 s64 lblkno, lastblkno, extblkno;
1038 struct metapage *mp;
1041 struct inode *ipbmap = sbi->ipbmap;
1045 * We don't want a non-aligned extent to cross a page boundary
1047 if (((rel_block = blkno & (sbi->nbperpage - 1))) &&
1048 (rel_block + nblocks + addnblocks > sbi->nbperpage))
1051 /* get the last block of the current allocation */
1052 lastblkno = blkno + nblocks - 1;
1054 /* determine the block number of the block following
1055 * the existing allocation.
1057 extblkno = lastblkno + 1;
1059 IREAD_LOCK(ipbmap, RDWRLOCK_DMAP);
1061 /* better be within the file system */
1063 if (lastblkno < 0 || lastblkno >= bmp->db_mapsize) {
1064 IREAD_UNLOCK(ipbmap);
1065 jfs_error(ip->i_sb, "the block is outside the filesystem\n");
1069 /* we'll attempt to extend the current allocation in place by
1070 * allocating the additional blocks as the blocks immediately
1071 * following the current allocation. we only try to extend the
1072 * current allocation in place if the number of additional blocks
1073 * can fit into a dmap, the last block of the current allocation
1074 * is not the last block of the file system, and the start of the
1075 * inplace extension is not on an allocation group boundary.
1077 if (addnblocks > BPERDMAP || extblkno >= bmp->db_mapsize ||
1078 (extblkno & (bmp->db_agsize - 1)) == 0) {
1079 IREAD_UNLOCK(ipbmap);
1083 /* get the buffer for the dmap containing the first block
1086 lblkno = BLKTODMAP(extblkno, bmp->db_l2nbperpage);
1087 mp = read_metapage(ipbmap, lblkno, PSIZE, 0);
1089 IREAD_UNLOCK(ipbmap);
1093 dp = (struct dmap *) mp->data;
1095 /* try to allocate the blocks immediately following the
1096 * current allocation.
1098 rc = dbAllocNext(bmp, dp, extblkno, (int) addnblocks);
1100 IREAD_UNLOCK(ipbmap);
1102 /* were we successful ? */
1106 /* we were not successful */
1107 release_metapage(mp);
1114 * NAME: dbAllocNext()
1116 * FUNCTION: attempt to allocate the blocks of the specified block
1117 * range within a dmap.
1120 * bmp - pointer to bmap descriptor
1121 * dp - pointer to dmap.
1122 * blkno - starting block number of the range.
1123 * nblocks - number of contiguous free blocks of the range.
1127 * -ENOSPC - insufficient disk resources
1130 * serialization: IREAD_LOCK(ipbmap) held on entry/exit;
1132 static int dbAllocNext(struct bmap * bmp, struct dmap * dp, s64 blkno,
1135 int dbitno, word, rembits, nb, nwords, wbitno, nw;
1140 if (dp->tree.leafidx != cpu_to_le32(LEAFIND)) {
1141 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmap page\n");
1145 /* pick up a pointer to the leaves of the dmap tree.
1147 leaf = dp->tree.stree + le32_to_cpu(dp->tree.leafidx);
1149 /* determine the bit number and word within the dmap of the
1152 dbitno = blkno & (BPERDMAP - 1);
1153 word = dbitno >> L2DBWORD;
1155 /* check if the specified block range is contained within
1158 if (dbitno + nblocks > BPERDMAP)
1161 /* check if the starting leaf indicates that anything
1164 if (leaf[word] == NOFREE)
1167 /* check the dmaps words corresponding to block range to see
1168 * if the block range is free. not all bits of the first and
1169 * last words may be contained within the block range. if this
1170 * is the case, we'll work against those words (i.e. partial first
1171 * and/or last) on an individual basis (a single pass) and examine
1172 * the actual bits to determine if they are free. a single pass
1173 * will be used for all dmap words fully contained within the
1174 * specified range. within this pass, the leaves of the dmap
1175 * tree will be examined to determine if the blocks are free. a
1176 * single leaf may describe the free space of multiple dmap
1177 * words, so we may visit only a subset of the actual leaves
1178 * corresponding to the dmap words of the block range.
1180 for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) {
1181 /* determine the bit number within the word and
1182 * the number of bits within the word.
1184 wbitno = dbitno & (DBWORD - 1);
1185 nb = min(rembits, DBWORD - wbitno);
1187 /* check if only part of the word is to be examined.
1190 /* check if the bits are free.
1192 mask = (ONES << (DBWORD - nb) >> wbitno);
1193 if ((mask & ~le32_to_cpu(dp->wmap[word])) != mask)
1198 /* one or more dmap words are fully contained
1199 * within the block range. determine how many
1200 * words and how many bits.
1202 nwords = rembits >> L2DBWORD;
1203 nb = nwords << L2DBWORD;
1205 /* now examine the appropriate leaves to determine
1206 * if the blocks are free.
1208 while (nwords > 0) {
1209 /* does the leaf describe any free space ?
1211 if (leaf[word] < BUDMIN)
1214 /* determine the l2 number of bits provided
1218 min_t(int, leaf[word], NLSTOL2BSZ(nwords));
1220 /* determine how many words were handled.
1222 nw = BUDSIZE(l2size, BUDMIN);
1230 /* allocate the blocks.
1232 return (dbAllocDmap(bmp, dp, blkno, nblocks));
1237 * NAME: dbAllocNear()
1239 * FUNCTION: attempt to allocate a number of contiguous free blocks near
1240 * a specified block (hint) within a dmap.
1242 * starting with the dmap leaf that covers the hint, we'll
1243 * check the next four contiguous leaves for sufficient free
1244 * space. if sufficient free space is found, we'll allocate
1245 * the desired free space.
1248 * bmp - pointer to bmap descriptor
1249 * dp - pointer to dmap.
1250 * blkno - block number to allocate near.
1251 * nblocks - actual number of contiguous free blocks desired.
1252 * l2nb - log2 number of contiguous free blocks desired.
1253 * results - on successful return, set to the starting block number
1254 * of the newly allocated range.
1258 * -ENOSPC - insufficient disk resources
1261 * serialization: IREAD_LOCK(ipbmap) held on entry/exit;
1264 dbAllocNear(struct bmap * bmp,
1265 struct dmap * dp, s64 blkno, int nblocks, int l2nb, s64 * results)
1267 int word, lword, rc;
1270 if (dp->tree.leafidx != cpu_to_le32(LEAFIND)) {
1271 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmap page\n");
1275 leaf = dp->tree.stree + le32_to_cpu(dp->tree.leafidx);
1277 /* determine the word within the dmap that holds the hint
1278 * (i.e. blkno). also, determine the last word in the dmap
1279 * that we'll include in our examination.
1281 word = (blkno & (BPERDMAP - 1)) >> L2DBWORD;
1282 lword = min(word + 4, LPERDMAP);
1284 /* examine the leaves for sufficient free space.
1286 for (; word < lword; word++) {
1287 /* does the leaf describe sufficient free space ?
1289 if (leaf[word] < l2nb)
1292 /* determine the block number within the file system
1293 * of the first block described by this dmap word.
1295 blkno = le64_to_cpu(dp->start) + (word << L2DBWORD);
1297 /* if not all bits of the dmap word are free, get the
1298 * starting bit number within the dmap word of the required
1299 * string of free bits and adjust the block number with the
1302 if (leaf[word] < BUDMIN)
1304 dbFindBits(le32_to_cpu(dp->wmap[word]), l2nb);
1306 /* allocate the blocks.
1308 if ((rc = dbAllocDmap(bmp, dp, blkno, nblocks)) == 0)
1321 * FUNCTION: attempt to allocate the specified number of contiguous
1322 * free blocks within the specified allocation group.
1324 * unless the allocation group size is equal to the number
1325 * of blocks per dmap, the dmap control pages will be used to
1326 * find the required free space, if available. we start the
1327 * search at the highest dmap control page level which
1328 * distinctly describes the allocation group's free space
1329 * (i.e. the highest level at which the allocation group's
1330 * free space is not mixed in with that of any other group).
1331 * in addition, we start the search within this level at a
1332 * height of the dmapctl dmtree at which the nodes distinctly
1333 * describe the allocation group's free space. at this height,
1334 * the allocation group's free space may be represented by 1
1335 * or two sub-trees, depending on the allocation group size.
1336 * we search the top nodes of these subtrees left to right for
1337 * sufficient free space. if sufficient free space is found,
1338 * the subtree is searched to find the leftmost leaf that
1339 * has free space. once we have made it to the leaf, we
1340 * move the search to the next lower level dmap control page
1341 * corresponding to this leaf. we continue down the dmap control
1342 * pages until we find the dmap that contains or starts the
1343 * sufficient free space and we allocate at this dmap.
1345 * if the allocation group size is equal to the dmap size,
1346 * we'll start at the dmap corresponding to the allocation
1347 * group and attempt the allocation at this level.
1349 * the dmap control page search is also not performed if the
1350 * allocation group is completely free and we go to the first
1351 * dmap of the allocation group to do the allocation. this is
1352 * done because the allocation group may be part (not the first
1353 * part) of a larger binary buddy system, causing the dmap
1354 * control pages to indicate no free space (NOFREE) within
1355 * the allocation group.
1358 * bmp - pointer to bmap descriptor
1359 * agno - allocation group number.
1360 * nblocks - actual number of contiguous free blocks desired.
1361 * l2nb - log2 number of contiguous free blocks desired.
1362 * results - on successful return, set to the starting block number
1363 * of the newly allocated range.
1367 * -ENOSPC - insufficient disk resources
1370 * note: IWRITE_LOCK(ipmap) held on entry/exit;
1373 dbAllocAG(struct bmap * bmp, int agno, s64 nblocks, int l2nb, s64 * results)
1375 struct metapage *mp;
1376 struct dmapctl *dcp;
1377 int rc, ti, i, k, m, n, agperlev;
1381 /* allocation request should not be for more than the
1382 * allocation group size.
1384 if (l2nb > bmp->db_agl2size) {
1385 jfs_error(bmp->db_ipbmap->i_sb,
1386 "allocation request is larger than the allocation group size\n");
1390 /* determine the starting block number of the allocation
1393 blkno = (s64) agno << bmp->db_agl2size;
1395 /* check if the allocation group size is the minimum allocation
1396 * group size or if the allocation group is completely free. if
1397 * the allocation group size is the minimum size of BPERDMAP (i.e.
1398 * 1 dmap), there is no need to search the dmap control page (below)
1399 * that fully describes the allocation group since the allocation
1400 * group is already fully described by a dmap. in this case, we
1401 * just call dbAllocCtl() to search the dmap tree and allocate the
1402 * required space if available.
1404 * if the allocation group is completely free, dbAllocCtl() is
1405 * also called to allocate the required space. this is done for
1406 * two reasons. first, it makes no sense searching the dmap control
1407 * pages for free space when we know that free space exists. second,
1408 * the dmap control pages may indicate that the allocation group
1409 * has no free space if the allocation group is part (not the first
1410 * part) of a larger binary buddy system.
1412 if (bmp->db_agsize == BPERDMAP
1413 || bmp->db_agfree[agno] == bmp->db_agsize) {
1414 rc = dbAllocCtl(bmp, nblocks, l2nb, blkno, results);
1415 if ((rc == -ENOSPC) &&
1416 (bmp->db_agfree[agno] == bmp->db_agsize)) {
1417 printk(KERN_ERR "blkno = %Lx, blocks = %Lx\n",
1418 (unsigned long long) blkno,
1419 (unsigned long long) nblocks);
1420 jfs_error(bmp->db_ipbmap->i_sb,
1421 "dbAllocCtl failed in free AG\n");
1426 /* the buffer for the dmap control page that fully describes the
1429 lblkno = BLKTOCTL(blkno, bmp->db_l2nbperpage, bmp->db_aglevel);
1430 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
1433 dcp = (struct dmapctl *) mp->data;
1434 budmin = dcp->budmin;
1436 if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) {
1437 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmapctl page\n");
1438 release_metapage(mp);
1442 /* search the subtree(s) of the dmap control page that describes
1443 * the allocation group, looking for sufficient free space. to begin,
1444 * determine how many allocation groups are represented in a dmap
1445 * control page at the control page level (i.e. L0, L1, L2) that
1446 * fully describes an allocation group. next, determine the starting
1447 * tree index of this allocation group within the control page.
1450 (1 << (L2LPERCTL - (bmp->db_agheight << 1))) / bmp->db_agwidth;
1451 ti = bmp->db_agstart + bmp->db_agwidth * (agno & (agperlev - 1));
1453 /* dmap control page trees fan-out by 4 and a single allocation
1454 * group may be described by 1 or 2 subtrees within the ag level
1455 * dmap control page, depending upon the ag size. examine the ag's
1456 * subtrees for sufficient free space, starting with the leftmost
1459 for (i = 0; i < bmp->db_agwidth; i++, ti++) {
1460 /* is there sufficient free space ?
1462 if (l2nb > dcp->stree[ti])
1465 /* sufficient free space found in a subtree. now search down
1466 * the subtree to find the leftmost leaf that describes this
1469 for (k = bmp->db_agheight; k > 0; k--) {
1470 for (n = 0, m = (ti << 2) + 1; n < 4; n++) {
1471 if (l2nb <= dcp->stree[m + n]) {
1477 jfs_error(bmp->db_ipbmap->i_sb,
1478 "failed descending stree\n");
1479 release_metapage(mp);
1484 /* determine the block number within the file system
1485 * that corresponds to this leaf.
1487 if (bmp->db_aglevel == 2)
1489 else if (bmp->db_aglevel == 1)
1490 blkno &= ~(MAXL1SIZE - 1);
1491 else /* bmp->db_aglevel == 0 */
1492 blkno &= ~(MAXL0SIZE - 1);
1495 ((s64) (ti - le32_to_cpu(dcp->leafidx))) << budmin;
1497 /* release the buffer in preparation for going down
1498 * the next level of dmap control pages.
1500 release_metapage(mp);
1502 /* check if we need to continue to search down the lower
1503 * level dmap control pages. we need to if the number of
1504 * blocks required is less than maximum number of blocks
1505 * described at the next lower level.
1507 if (l2nb < budmin) {
1509 /* search the lower level dmap control pages to get
1510 * the starting block number of the dmap that
1511 * contains or starts off the free space.
1514 dbFindCtl(bmp, l2nb, bmp->db_aglevel - 1,
1516 if (rc == -ENOSPC) {
1517 jfs_error(bmp->db_ipbmap->i_sb,
1518 "control page inconsistent\n");
1525 /* allocate the blocks.
1527 rc = dbAllocCtl(bmp, nblocks, l2nb, blkno, results);
1528 if (rc == -ENOSPC) {
1529 jfs_error(bmp->db_ipbmap->i_sb,
1530 "unable to allocate blocks\n");
1536 /* no space in the allocation group. release the buffer and
1539 release_metapage(mp);
1546 * NAME: dbAllocAny()
1548 * FUNCTION: attempt to allocate the specified number of contiguous
1549 * free blocks anywhere in the file system.
1551 * dbAllocAny() attempts to find the sufficient free space by
1552 * searching down the dmap control pages, starting with the
1553 * highest level (i.e. L0, L1, L2) control page. if free space
1554 * large enough to satisfy the desired free space is found, the
1555 * desired free space is allocated.
1558 * bmp - pointer to bmap descriptor
1559 * nblocks - actual number of contiguous free blocks desired.
1560 * l2nb - log2 number of contiguous free blocks desired.
1561 * results - on successful return, set to the starting block number
1562 * of the newly allocated range.
1566 * -ENOSPC - insufficient disk resources
1569 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1571 static int dbAllocAny(struct bmap * bmp, s64 nblocks, int l2nb, s64 * results)
1576 /* starting with the top level dmap control page, search
1577 * down the dmap control levels for sufficient free space.
1578 * if free space is found, dbFindCtl() returns the starting
1579 * block number of the dmap that contains or starts off the
1580 * range of free space.
1582 if ((rc = dbFindCtl(bmp, l2nb, bmp->db_maxlevel, &blkno)))
1585 /* allocate the blocks.
1587 rc = dbAllocCtl(bmp, nblocks, l2nb, blkno, results);
1588 if (rc == -ENOSPC) {
1589 jfs_error(bmp->db_ipbmap->i_sb, "unable to allocate blocks\n");
1597 * NAME: dbDiscardAG()
1599 * FUNCTION: attempt to discard (TRIM) all free blocks of specific AG
1602 * 1) allocate blocks, as large as possible and save them
1603 * while holding IWRITE_LOCK on ipbmap
1604 * 2) trim all these saved block/length values
1605 * 3) mark the blocks free again
1608 * - we work only on one ag at some time, minimizing how long we
1609 * need to lock ipbmap
1610 * - reading / writing the fs is possible most time, even on
1614 * - we write two times to the dmapctl and dmap pages
1615 * - but for me, this seems the best way, better ideas?
1619 * ip - pointer to in-core inode
1621 * minlen - minimum value of contiguous blocks
1624 * s64 - actual number of blocks trimmed
1626 s64 dbDiscardAG(struct inode *ip, int agno, s64 minlen)
1628 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap;
1629 struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap;
1633 struct super_block *sb = ipbmap->i_sb;
1640 /* max blkno / nblocks pairs to trim */
1641 int count = 0, range_cnt;
1644 /* prevent others from writing new stuff here, while trimming */
1645 IWRITE_LOCK(ipbmap, RDWRLOCK_DMAP);
1647 nblocks = bmp->db_agfree[agno];
1648 max_ranges = nblocks;
1649 do_div(max_ranges, minlen);
1650 range_cnt = min_t(u64, max_ranges + 1, 32 * 1024);
1651 totrim = kmalloc(sizeof(struct range2trim) * range_cnt, GFP_NOFS);
1652 if (totrim == NULL) {
1653 jfs_error(bmp->db_ipbmap->i_sb, "no memory for trim array\n");
1654 IWRITE_UNLOCK(ipbmap);
1659 while (nblocks >= minlen) {
1660 l2nb = BLKSTOL2(nblocks);
1662 /* 0 = okay, -EIO = fatal, -ENOSPC -> try smaller block */
1663 rc = dbAllocAG(bmp, agno, nblocks, l2nb, &blkno);
1666 tt->nblocks = nblocks;
1669 /* the whole ag is free, trim now */
1670 if (bmp->db_agfree[agno] == 0)
1673 /* give a hint for the next while */
1674 nblocks = bmp->db_agfree[agno];
1676 } else if (rc == -ENOSPC) {
1677 /* search for next smaller log2 block */
1678 l2nb = BLKSTOL2(nblocks) - 1;
1679 nblocks = 1LL << l2nb;
1681 /* Trim any already allocated blocks */
1682 jfs_error(bmp->db_ipbmap->i_sb, "-EIO\n");
1686 /* check, if our trim array is full */
1687 if (unlikely(count >= range_cnt - 1))
1690 IWRITE_UNLOCK(ipbmap);
1692 tt->nblocks = 0; /* mark the current end */
1693 for (tt = totrim; tt->nblocks != 0; tt++) {
1694 /* when mounted with online discard, dbFree() will
1695 * call jfs_issue_discard() itself */
1696 if (!(JFS_SBI(sb)->flag & JFS_DISCARD))
1697 jfs_issue_discard(ip, tt->blkno, tt->nblocks);
1698 dbFree(ip, tt->blkno, tt->nblocks);
1699 trimmed += tt->nblocks;
1709 * FUNCTION: starting at a specified dmap control page level and block
1710 * number, search down the dmap control levels for a range of
1711 * contiguous free blocks large enough to satisfy an allocation
1712 * request for the specified number of free blocks.
1714 * if sufficient contiguous free blocks are found, this routine
1715 * returns the starting block number within a dmap page that
1716 * contains or starts a range of contiqious free blocks that
1717 * is sufficient in size.
1720 * bmp - pointer to bmap descriptor
1721 * level - starting dmap control page level.
1722 * l2nb - log2 number of contiguous free blocks desired.
1723 * *blkno - on entry, starting block number for conducting the search.
1724 * on successful return, the first block within a dmap page
1725 * that contains or starts a range of contiguous free blocks.
1729 * -ENOSPC - insufficient disk resources
1732 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1734 static int dbFindCtl(struct bmap * bmp, int l2nb, int level, s64 * blkno)
1736 int rc, leafidx, lev;
1738 struct dmapctl *dcp;
1740 struct metapage *mp;
1742 /* starting at the specified dmap control page level and block
1743 * number, search down the dmap control levels for the starting
1744 * block number of a dmap page that contains or starts off
1745 * sufficient free blocks.
1747 for (lev = level, b = *blkno; lev >= 0; lev--) {
1748 /* get the buffer of the dmap control page for the block
1749 * number and level (i.e. L0, L1, L2).
1751 lblkno = BLKTOCTL(b, bmp->db_l2nbperpage, lev);
1752 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
1755 dcp = (struct dmapctl *) mp->data;
1756 budmin = dcp->budmin;
1758 if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) {
1759 jfs_error(bmp->db_ipbmap->i_sb,
1760 "Corrupt dmapctl page\n");
1761 release_metapage(mp);
1765 /* search the tree within the dmap control page for
1766 * sufficient free space. if sufficient free space is found,
1767 * dbFindLeaf() returns the index of the leaf at which
1768 * free space was found.
1770 rc = dbFindLeaf((dmtree_t *) dcp, l2nb, &leafidx);
1772 /* release the buffer.
1774 release_metapage(mp);
1780 jfs_error(bmp->db_ipbmap->i_sb,
1781 "dmap inconsistent\n");
1787 /* adjust the block number to reflect the location within
1788 * the dmap control page (i.e. the leaf) at which free
1791 b += (((s64) leafidx) << budmin);
1793 /* we stop the search at this dmap control page level if
1794 * the number of blocks required is greater than or equal
1795 * to the maximum number of blocks described at the next
1808 * NAME: dbAllocCtl()
1810 * FUNCTION: attempt to allocate a specified number of contiguous
1811 * blocks starting within a specific dmap.
1813 * this routine is called by higher level routines that search
1814 * the dmap control pages above the actual dmaps for contiguous
1815 * free space. the result of successful searches by these
1816 * routines are the starting block numbers within dmaps, with
1817 * the dmaps themselves containing the desired contiguous free
1818 * space or starting a contiguous free space of desired size
1819 * that is made up of the blocks of one or more dmaps. these
1820 * calls should not fail due to insufficent resources.
1822 * this routine is called in some cases where it is not known
1823 * whether it will fail due to insufficient resources. more
1824 * specifically, this occurs when allocating from an allocation
1825 * group whose size is equal to the number of blocks per dmap.
1826 * in this case, the dmap control pages are not examined prior
1827 * to calling this routine (to save pathlength) and the call
1830 * for a request size that fits within a dmap, this routine relies
1831 * upon the dmap's dmtree to find the requested contiguous free
1832 * space. for request sizes that are larger than a dmap, the
1833 * requested free space will start at the first block of the
1834 * first dmap (i.e. blkno).
1837 * bmp - pointer to bmap descriptor
1838 * nblocks - actual number of contiguous free blocks to allocate.
1839 * l2nb - log2 number of contiguous free blocks to allocate.
1840 * blkno - starting block number of the dmap to start the allocation
1842 * results - on successful return, set to the starting block number
1843 * of the newly allocated range.
1847 * -ENOSPC - insufficient disk resources
1850 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1853 dbAllocCtl(struct bmap * bmp, s64 nblocks, int l2nb, s64 blkno, s64 * results)
1857 struct metapage *mp;
1860 /* check if the allocation request is confined to a single dmap.
1862 if (l2nb <= L2BPERDMAP) {
1863 /* get the buffer for the dmap.
1865 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
1866 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
1869 dp = (struct dmap *) mp->data;
1871 /* try to allocate the blocks.
1873 rc = dbAllocDmapLev(bmp, dp, (int) nblocks, l2nb, results);
1875 mark_metapage_dirty(mp);
1877 release_metapage(mp);
1882 /* allocation request involving multiple dmaps. it must start on
1885 assert((blkno & (BPERDMAP - 1)) == 0);
1887 /* allocate the blocks dmap by dmap.
1889 for (n = nblocks, b = blkno; n > 0; n -= nb, b += nb) {
1890 /* get the buffer for the dmap.
1892 lblkno = BLKTODMAP(b, bmp->db_l2nbperpage);
1893 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
1898 dp = (struct dmap *) mp->data;
1900 /* the dmap better be all free.
1902 if (dp->tree.stree[ROOT] != L2BPERDMAP) {
1903 release_metapage(mp);
1904 jfs_error(bmp->db_ipbmap->i_sb,
1905 "the dmap is not all free\n");
1910 /* determine how many blocks to allocate from this dmap.
1912 nb = min_t(s64, n, BPERDMAP);
1914 /* allocate the blocks from the dmap.
1916 if ((rc = dbAllocDmap(bmp, dp, b, nb))) {
1917 release_metapage(mp);
1921 /* write the buffer.
1926 /* set the results (starting block number) and return.
1931 /* something failed in handling an allocation request involving
1932 * multiple dmaps. we'll try to clean up by backing out any
1933 * allocation that has already happened for this request. if
1934 * we fail in backing out the allocation, we'll mark the file
1935 * system to indicate that blocks have been leaked.
1939 /* try to backout the allocations dmap by dmap.
1941 for (n = nblocks - n, b = blkno; n > 0;
1942 n -= BPERDMAP, b += BPERDMAP) {
1943 /* get the buffer for this dmap.
1945 lblkno = BLKTODMAP(b, bmp->db_l2nbperpage);
1946 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
1948 /* could not back out. mark the file system
1949 * to indicate that we have leaked blocks.
1951 jfs_error(bmp->db_ipbmap->i_sb,
1952 "I/O Error: Block Leakage\n");
1955 dp = (struct dmap *) mp->data;
1957 /* free the blocks is this dmap.
1959 if (dbFreeDmap(bmp, dp, b, BPERDMAP)) {
1960 /* could not back out. mark the file system
1961 * to indicate that we have leaked blocks.
1963 release_metapage(mp);
1964 jfs_error(bmp->db_ipbmap->i_sb, "Block Leakage\n");
1968 /* write the buffer.
1978 * NAME: dbAllocDmapLev()
1980 * FUNCTION: attempt to allocate a specified number of contiguous blocks
1981 * from a specified dmap.
1983 * this routine checks if the contiguous blocks are available.
1984 * if so, nblocks of blocks are allocated; otherwise, ENOSPC is
1988 * mp - pointer to bmap descriptor
1989 * dp - pointer to dmap to attempt to allocate blocks from.
1990 * l2nb - log2 number of contiguous block desired.
1991 * nblocks - actual number of contiguous block desired.
1992 * results - on successful return, set to the starting block number
1993 * of the newly allocated range.
1997 * -ENOSPC - insufficient disk resources
2000 * serialization: IREAD_LOCK(ipbmap), e.g., from dbAlloc(), or
2001 * IWRITE_LOCK(ipbmap), e.g., dbAllocCtl(), held on entry/exit;
2004 dbAllocDmapLev(struct bmap * bmp,
2005 struct dmap * dp, int nblocks, int l2nb, s64 * results)
2010 /* can't be more than a dmaps worth of blocks */
2011 assert(l2nb <= L2BPERDMAP);
2013 /* search the tree within the dmap page for sufficient
2014 * free space. if sufficient free space is found, dbFindLeaf()
2015 * returns the index of the leaf at which free space was found.
2017 if (dbFindLeaf((dmtree_t *) & dp->tree, l2nb, &leafidx))
2020 /* determine the block number within the file system corresponding
2021 * to the leaf at which free space was found.
2023 blkno = le64_to_cpu(dp->start) + (leafidx << L2DBWORD);
2025 /* if not all bits of the dmap word are free, get the starting
2026 * bit number within the dmap word of the required string of free
2027 * bits and adjust the block number with this value.
2029 if (dp->tree.stree[leafidx + LEAFIND] < BUDMIN)
2030 blkno += dbFindBits(le32_to_cpu(dp->wmap[leafidx]), l2nb);
2032 /* allocate the blocks */
2033 if ((rc = dbAllocDmap(bmp, dp, blkno, nblocks)) == 0)
2041 * NAME: dbAllocDmap()
2043 * FUNCTION: adjust the disk allocation map to reflect the allocation
2044 * of a specified block range within a dmap.
2046 * this routine allocates the specified blocks from the dmap
2047 * through a call to dbAllocBits(). if the allocation of the
2048 * block range causes the maximum string of free blocks within
2049 * the dmap to change (i.e. the value of the root of the dmap's
2050 * dmtree), this routine will cause this change to be reflected
2051 * up through the appropriate levels of the dmap control pages
2052 * by a call to dbAdjCtl() for the L0 dmap control page that
2056 * bmp - pointer to bmap descriptor
2057 * dp - pointer to dmap to allocate the block range from.
2058 * blkno - starting block number of the block to be allocated.
2059 * nblocks - number of blocks to be allocated.
2065 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2067 static int dbAllocDmap(struct bmap * bmp, struct dmap * dp, s64 blkno,
2073 /* save the current value of the root (i.e. maximum free string)
2076 oldroot = dp->tree.stree[ROOT];
2078 /* allocate the specified (blocks) bits */
2079 dbAllocBits(bmp, dp, blkno, nblocks);
2081 /* if the root has not changed, done. */
2082 if (dp->tree.stree[ROOT] == oldroot)
2085 /* root changed. bubble the change up to the dmap control pages.
2086 * if the adjustment of the upper level control pages fails,
2087 * backout the bit allocation (thus making everything consistent).
2089 if ((rc = dbAdjCtl(bmp, blkno, dp->tree.stree[ROOT], 1, 0)))
2090 dbFreeBits(bmp, dp, blkno, nblocks);
2097 * NAME: dbFreeDmap()
2099 * FUNCTION: adjust the disk allocation map to reflect the allocation
2100 * of a specified block range within a dmap.
2102 * this routine frees the specified blocks from the dmap through
2103 * a call to dbFreeBits(). if the deallocation of the block range
2104 * causes the maximum string of free blocks within the dmap to
2105 * change (i.e. the value of the root of the dmap's dmtree), this
2106 * routine will cause this change to be reflected up through the
2107 * appropriate levels of the dmap control pages by a call to
2108 * dbAdjCtl() for the L0 dmap control page that covers this dmap.
2111 * bmp - pointer to bmap descriptor
2112 * dp - pointer to dmap to free the block range from.
2113 * blkno - starting block number of the block to be freed.
2114 * nblocks - number of blocks to be freed.
2120 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2122 static int dbFreeDmap(struct bmap * bmp, struct dmap * dp, s64 blkno,
2128 /* save the current value of the root (i.e. maximum free string)
2131 oldroot = dp->tree.stree[ROOT];
2133 /* free the specified (blocks) bits */
2134 rc = dbFreeBits(bmp, dp, blkno, nblocks);
2136 /* if error or the root has not changed, done. */
2137 if (rc || (dp->tree.stree[ROOT] == oldroot))
2140 /* root changed. bubble the change up to the dmap control pages.
2141 * if the adjustment of the upper level control pages fails,
2142 * backout the deallocation.
2144 if ((rc = dbAdjCtl(bmp, blkno, dp->tree.stree[ROOT], 0, 0))) {
2145 word = (blkno & (BPERDMAP - 1)) >> L2DBWORD;
2147 /* as part of backing out the deallocation, we will have
2148 * to back split the dmap tree if the deallocation caused
2149 * the freed blocks to become part of a larger binary buddy
2152 if (dp->tree.stree[word] == NOFREE)
2153 dbBackSplit((dmtree_t *) & dp->tree, word);
2155 dbAllocBits(bmp, dp, blkno, nblocks);
2163 * NAME: dbAllocBits()
2165 * FUNCTION: allocate a specified block range from a dmap.
2167 * this routine updates the dmap to reflect the working
2168 * state allocation of the specified block range. it directly
2169 * updates the bits of the working map and causes the adjustment
2170 * of the binary buddy system described by the dmap's dmtree
2171 * leaves to reflect the bits allocated. it also causes the
2172 * dmap's dmtree, as a whole, to reflect the allocated range.
2175 * bmp - pointer to bmap descriptor
2176 * dp - pointer to dmap to allocate bits from.
2177 * blkno - starting block number of the bits to be allocated.
2178 * nblocks - number of bits to be allocated.
2180 * RETURN VALUES: none
2182 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2184 static void dbAllocBits(struct bmap * bmp, struct dmap * dp, s64 blkno,
2187 int dbitno, word, rembits, nb, nwords, wbitno, nw, agno;
2188 dmtree_t *tp = (dmtree_t *) & dp->tree;
2192 /* pick up a pointer to the leaves of the dmap tree */
2193 leaf = dp->tree.stree + LEAFIND;
2195 /* determine the bit number and word within the dmap of the
2198 dbitno = blkno & (BPERDMAP - 1);
2199 word = dbitno >> L2DBWORD;
2201 /* block range better be within the dmap */
2202 assert(dbitno + nblocks <= BPERDMAP);
2204 /* allocate the bits of the dmap's words corresponding to the block
2205 * range. not all bits of the first and last words may be contained
2206 * within the block range. if this is the case, we'll work against
2207 * those words (i.e. partial first and/or last) on an individual basis
2208 * (a single pass), allocating the bits of interest by hand and
2209 * updating the leaf corresponding to the dmap word. a single pass
2210 * will be used for all dmap words fully contained within the
2211 * specified range. within this pass, the bits of all fully contained
2212 * dmap words will be marked as free in a single shot and the leaves
2213 * will be updated. a single leaf may describe the free space of
2214 * multiple dmap words, so we may update only a subset of the actual
2215 * leaves corresponding to the dmap words of the block range.
2217 for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) {
2218 /* determine the bit number within the word and
2219 * the number of bits within the word.
2221 wbitno = dbitno & (DBWORD - 1);
2222 nb = min(rembits, DBWORD - wbitno);
2224 /* check if only part of a word is to be allocated.
2227 /* allocate (set to 1) the appropriate bits within
2230 dp->wmap[word] |= cpu_to_le32(ONES << (DBWORD - nb)
2233 /* update the leaf for this dmap word. in addition
2234 * to setting the leaf value to the binary buddy max
2235 * of the updated dmap word, dbSplit() will split
2236 * the binary system of the leaves if need be.
2238 dbSplit(tp, word, BUDMIN,
2239 dbMaxBud((u8 *) & dp->wmap[word]));
2243 /* one or more dmap words are fully contained
2244 * within the block range. determine how many
2245 * words and allocate (set to 1) the bits of these
2248 nwords = rembits >> L2DBWORD;
2249 memset(&dp->wmap[word], (int) ONES, nwords * 4);
2251 /* determine how many bits.
2253 nb = nwords << L2DBWORD;
2255 /* now update the appropriate leaves to reflect
2256 * the allocated words.
2258 for (; nwords > 0; nwords -= nw) {
2259 if (leaf[word] < BUDMIN) {
2260 jfs_error(bmp->db_ipbmap->i_sb,
2261 "leaf page corrupt\n");
2265 /* determine what the leaf value should be
2266 * updated to as the minimum of the l2 number
2267 * of bits being allocated and the l2 number
2268 * of bits currently described by this leaf.
2270 size = min_t(int, leaf[word],
2271 NLSTOL2BSZ(nwords));
2273 /* update the leaf to reflect the allocation.
2274 * in addition to setting the leaf value to
2275 * NOFREE, dbSplit() will split the binary
2276 * system of the leaves to reflect the current
2277 * allocation (size).
2279 dbSplit(tp, word, size, NOFREE);
2281 /* get the number of dmap words handled */
2282 nw = BUDSIZE(size, BUDMIN);
2288 /* update the free count for this dmap */
2289 le32_add_cpu(&dp->nfree, -nblocks);
2293 /* if this allocation group is completely free,
2294 * update the maximum allocation group number if this allocation
2295 * group is the new max.
2297 agno = blkno >> bmp->db_agl2size;
2298 if (agno > bmp->db_maxag)
2299 bmp->db_maxag = agno;
2301 /* update the free count for the allocation group and map */
2302 bmp->db_agfree[agno] -= nblocks;
2303 bmp->db_nfree -= nblocks;
2310 * NAME: dbFreeBits()
2312 * FUNCTION: free a specified block range from a dmap.
2314 * this routine updates the dmap to reflect the working
2315 * state allocation of the specified block range. it directly
2316 * updates the bits of the working map and causes the adjustment
2317 * of the binary buddy system described by the dmap's dmtree
2318 * leaves to reflect the bits freed. it also causes the dmap's
2319 * dmtree, as a whole, to reflect the deallocated range.
2322 * bmp - pointer to bmap descriptor
2323 * dp - pointer to dmap to free bits from.
2324 * blkno - starting block number of the bits to be freed.
2325 * nblocks - number of bits to be freed.
2327 * RETURN VALUES: 0 for success
2329 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2331 static int dbFreeBits(struct bmap * bmp, struct dmap * dp, s64 blkno,
2334 int dbitno, word, rembits, nb, nwords, wbitno, nw, agno;
2335 dmtree_t *tp = (dmtree_t *) & dp->tree;
2339 /* determine the bit number and word within the dmap of the
2342 dbitno = blkno & (BPERDMAP - 1);
2343 word = dbitno >> L2DBWORD;
2345 /* block range better be within the dmap.
2347 assert(dbitno + nblocks <= BPERDMAP);
2349 /* free the bits of the dmaps words corresponding to the block range.
2350 * not all bits of the first and last words may be contained within
2351 * the block range. if this is the case, we'll work against those
2352 * words (i.e. partial first and/or last) on an individual basis
2353 * (a single pass), freeing the bits of interest by hand and updating
2354 * the leaf corresponding to the dmap word. a single pass will be used
2355 * for all dmap words fully contained within the specified range.
2356 * within this pass, the bits of all fully contained dmap words will
2357 * be marked as free in a single shot and the leaves will be updated. a
2358 * single leaf may describe the free space of multiple dmap words,
2359 * so we may update only a subset of the actual leaves corresponding
2360 * to the dmap words of the block range.
2362 * dbJoin() is used to update leaf values and will join the binary
2363 * buddy system of the leaves if the new leaf values indicate this
2366 for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) {
2367 /* determine the bit number within the word and
2368 * the number of bits within the word.
2370 wbitno = dbitno & (DBWORD - 1);
2371 nb = min(rembits, DBWORD - wbitno);
2373 /* check if only part of a word is to be freed.
2376 /* free (zero) the appropriate bits within this
2380 cpu_to_le32(~(ONES << (DBWORD - nb)
2383 /* update the leaf for this dmap word.
2385 rc = dbJoin(tp, word,
2386 dbMaxBud((u8 *) & dp->wmap[word]));
2392 /* one or more dmap words are fully contained
2393 * within the block range. determine how many
2394 * words and free (zero) the bits of these words.
2396 nwords = rembits >> L2DBWORD;
2397 memset(&dp->wmap[word], 0, nwords * 4);
2399 /* determine how many bits.
2401 nb = nwords << L2DBWORD;
2403 /* now update the appropriate leaves to reflect
2406 for (; nwords > 0; nwords -= nw) {
2407 /* determine what the leaf value should be
2408 * updated to as the minimum of the l2 number
2409 * of bits being freed and the l2 (max) number
2410 * of bits that can be described by this leaf.
2414 (word, L2LPERDMAP, BUDMIN),
2415 NLSTOL2BSZ(nwords));
2419 rc = dbJoin(tp, word, size);
2423 /* get the number of dmap words handled.
2425 nw = BUDSIZE(size, BUDMIN);
2431 /* update the free count for this dmap.
2433 le32_add_cpu(&dp->nfree, nblocks);
2437 /* update the free count for the allocation group and
2440 agno = blkno >> bmp->db_agl2size;
2441 bmp->db_nfree += nblocks;
2442 bmp->db_agfree[agno] += nblocks;
2444 /* check if this allocation group is not completely free and
2445 * if it is currently the maximum (rightmost) allocation group.
2446 * if so, establish the new maximum allocation group number by
2447 * searching left for the first allocation group with allocation.
2449 if ((bmp->db_agfree[agno] == bmp->db_agsize && agno == bmp->db_maxag) ||
2450 (agno == bmp->db_numag - 1 &&
2451 bmp->db_agfree[agno] == (bmp-> db_mapsize & (BPERDMAP - 1)))) {
2452 while (bmp->db_maxag > 0) {
2454 if (bmp->db_agfree[bmp->db_maxag] !=
2459 /* re-establish the allocation group preference if the
2460 * current preference is right of the maximum allocation
2463 if (bmp->db_agpref > bmp->db_maxag)
2464 bmp->db_agpref = bmp->db_maxag;
2476 * FUNCTION: adjust a dmap control page at a specified level to reflect
2477 * the change in a lower level dmap or dmap control page's
2478 * maximum string of free blocks (i.e. a change in the root
2479 * of the lower level object's dmtree) due to the allocation
2480 * or deallocation of a range of blocks with a single dmap.
2482 * on entry, this routine is provided with the new value of
2483 * the lower level dmap or dmap control page root and the
2484 * starting block number of the block range whose allocation
2485 * or deallocation resulted in the root change. this range
2486 * is respresented by a single leaf of the current dmapctl
2487 * and the leaf will be updated with this value, possibly
2488 * causing a binary buddy system within the leaves to be
2489 * split or joined. the update may also cause the dmapctl's
2490 * dmtree to be updated.
2492 * if the adjustment of the dmap control page, itself, causes its
2493 * root to change, this change will be bubbled up to the next dmap
2494 * control level by a recursive call to this routine, specifying
2495 * the new root value and the next dmap control page level to
2498 * bmp - pointer to bmap descriptor
2499 * blkno - the first block of a block range within a dmap. it is
2500 * the allocation or deallocation of this block range that
2501 * requires the dmap control page to be adjusted.
2502 * newval - the new value of the lower level dmap or dmap control
2504 * alloc - 'true' if adjustment is due to an allocation.
2505 * level - current level of dmap control page (i.e. L0, L1, L2) to
2512 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2515 dbAdjCtl(struct bmap * bmp, s64 blkno, int newval, int alloc, int level)
2517 struct metapage *mp;
2521 struct dmapctl *dcp;
2524 /* get the buffer for the dmap control page for the specified
2525 * block number and control page level.
2527 lblkno = BLKTOCTL(blkno, bmp->db_l2nbperpage, level);
2528 mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
2531 dcp = (struct dmapctl *) mp->data;
2533 if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) {
2534 jfs_error(bmp->db_ipbmap->i_sb, "Corrupt dmapctl page\n");
2535 release_metapage(mp);
2539 /* determine the leaf number corresponding to the block and
2540 * the index within the dmap control tree.
2542 leafno = BLKTOCTLLEAF(blkno, dcp->budmin);
2543 ti = leafno + le32_to_cpu(dcp->leafidx);
2545 /* save the current leaf value and the current root level (i.e.
2546 * maximum l2 free string described by this dmapctl).
2548 oldval = dcp->stree[ti];
2549 oldroot = dcp->stree[ROOT];
2551 /* check if this is a control page update for an allocation.
2552 * if so, update the leaf to reflect the new leaf value using
2553 * dbSplit(); otherwise (deallocation), use dbJoin() to update
2554 * the leaf with the new value. in addition to updating the
2555 * leaf, dbSplit() will also split the binary buddy system of
2556 * the leaves, if required, and bubble new values within the
2557 * dmapctl tree, if required. similarly, dbJoin() will join
2558 * the binary buddy system of leaves and bubble new values up
2559 * the dmapctl tree as required by the new leaf value.
2562 /* check if we are in the middle of a binary buddy
2563 * system. this happens when we are performing the
2564 * first allocation out of an allocation group that
2565 * is part (not the first part) of a larger binary
2566 * buddy system. if we are in the middle, back split
2567 * the system prior to calling dbSplit() which assumes
2568 * that it is at the front of a binary buddy system.
2570 if (oldval == NOFREE) {
2571 rc = dbBackSplit((dmtree_t *) dcp, leafno);
2574 oldval = dcp->stree[ti];
2576 dbSplit((dmtree_t *) dcp, leafno, dcp->budmin, newval);
2578 rc = dbJoin((dmtree_t *) dcp, leafno, newval);
2583 /* check if the root of the current dmap control page changed due
2584 * to the update and if the current dmap control page is not at
2585 * the current top level (i.e. L0, L1, L2) of the map. if so (i.e.
2586 * root changed and this is not the top level), call this routine
2587 * again (recursion) for the next higher level of the mapping to
2588 * reflect the change in root for the current dmap control page.
2590 if (dcp->stree[ROOT] != oldroot) {
2591 /* are we below the top level of the map. if so,
2592 * bubble the root up to the next higher level.
2594 if (level < bmp->db_maxlevel) {
2595 /* bubble up the new root of this dmap control page to
2599 dbAdjCtl(bmp, blkno, dcp->stree[ROOT], alloc,
2601 /* something went wrong in bubbling up the new
2602 * root value, so backout the changes to the
2603 * current dmap control page.
2606 dbJoin((dmtree_t *) dcp, leafno,
2609 /* the dbJoin() above might have
2610 * caused a larger binary buddy system
2611 * to form and we may now be in the
2612 * middle of it. if this is the case,
2613 * back split the buddies.
2615 if (dcp->stree[ti] == NOFREE)
2616 dbBackSplit((dmtree_t *)
2618 dbSplit((dmtree_t *) dcp, leafno,
2619 dcp->budmin, oldval);
2622 /* release the buffer and return the error.
2624 release_metapage(mp);
2628 /* we're at the top level of the map. update
2629 * the bmap control page to reflect the size
2630 * of the maximum free buddy system.
2632 assert(level == bmp->db_maxlevel);
2633 if (bmp->db_maxfreebud != oldroot) {
2634 jfs_error(bmp->db_ipbmap->i_sb,
2635 "the maximum free buddy is not the old root\n");
2637 bmp->db_maxfreebud = dcp->stree[ROOT];
2641 /* write the buffer.
2652 * FUNCTION: update the leaf of a dmtree with a new value, splitting
2653 * the leaf from the binary buddy system of the dmtree's
2654 * leaves, as required.
2657 * tp - pointer to the tree containing the leaf.
2658 * leafno - the number of the leaf to be updated.
2659 * splitsz - the size the binary buddy system starting at the leaf
2660 * must be split to, specified as the log2 number of blocks.
2661 * newval - the new value for the leaf.
2663 * RETURN VALUES: none
2665 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2667 static void dbSplit(dmtree_t * tp, int leafno, int splitsz, int newval)
2671 s8 *leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx);
2673 /* check if the leaf needs to be split.
2675 if (leaf[leafno] > tp->dmt_budmin) {
2676 /* the split occurs by cutting the buddy system in half
2677 * at the specified leaf until we reach the specified
2678 * size. pick up the starting split size (current size
2679 * - 1 in l2) and the corresponding buddy size.
2681 cursz = leaf[leafno] - 1;
2682 budsz = BUDSIZE(cursz, tp->dmt_budmin);
2684 /* split until we reach the specified size.
2686 while (cursz >= splitsz) {
2687 /* update the buddy's leaf with its new value.
2689 dbAdjTree(tp, leafno ^ budsz, cursz);
2691 /* on to the next size and buddy.
2698 /* adjust the dmap tree to reflect the specified leaf's new
2701 dbAdjTree(tp, leafno, newval);
2706 * NAME: dbBackSplit()
2708 * FUNCTION: back split the binary buddy system of dmtree leaves
2709 * that hold a specified leaf until the specified leaf
2710 * starts its own binary buddy system.
2712 * the allocators typically perform allocations at the start
2713 * of binary buddy systems and dbSplit() is used to accomplish
2714 * any required splits. in some cases, however, allocation
2715 * may occur in the middle of a binary system and requires a
2716 * back split, with the split proceeding out from the middle of
2717 * the system (less efficient) rather than the start of the
2718 * system (more efficient). the cases in which a back split
2719 * is required are rare and are limited to the first allocation
2720 * within an allocation group which is a part (not first part)
2721 * of a larger binary buddy system and a few exception cases
2722 * in which a previous join operation must be backed out.
2725 * tp - pointer to the tree containing the leaf.
2726 * leafno - the number of the leaf to be updated.
2728 * RETURN VALUES: none
2730 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2732 static int dbBackSplit(dmtree_t * tp, int leafno)
2734 int budsz, bud, w, bsz, size;
2736 s8 *leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx);
2738 /* leaf should be part (not first part) of a binary
2741 assert(leaf[leafno] == NOFREE);
2743 /* the back split is accomplished by iteratively finding the leaf
2744 * that starts the buddy system that contains the specified leaf and
2745 * splitting that system in two. this iteration continues until
2746 * the specified leaf becomes the start of a buddy system.
2748 * determine maximum possible l2 size for the specified leaf.
2751 LITOL2BSZ(leafno, le32_to_cpu(tp->dmt_l2nleafs),
2754 /* determine the number of leaves covered by this size. this
2755 * is the buddy size that we will start with as we search for
2756 * the buddy system that contains the specified leaf.
2758 budsz = BUDSIZE(size, tp->dmt_budmin);
2762 while (leaf[leafno] == NOFREE) {
2763 /* find the leftmost buddy leaf.
2765 for (w = leafno, bsz = budsz;; bsz <<= 1,
2766 w = (w < bud) ? w : bud) {
2767 if (bsz >= le32_to_cpu(tp->dmt_nleafs)) {
2768 jfs_err("JFS: block map error in dbBackSplit");
2772 /* determine the buddy.
2776 /* check if this buddy is the start of the system.
2778 if (leaf[bud] != NOFREE) {
2779 /* split the leaf at the start of the
2782 cursz = leaf[bud] - 1;
2783 dbSplit(tp, bud, cursz, cursz);
2789 if (leaf[leafno] != size) {
2790 jfs_err("JFS: wrong leaf value in dbBackSplit");
2800 * FUNCTION: update the leaf of a dmtree with a new value, joining
2801 * the leaf with other leaves of the dmtree into a multi-leaf
2802 * binary buddy system, as required.
2805 * tp - pointer to the tree containing the leaf.
2806 * leafno - the number of the leaf to be updated.
2807 * newval - the new value for the leaf.
2809 * RETURN VALUES: none
2811 static int dbJoin(dmtree_t * tp, int leafno, int newval)
2816 /* can the new leaf value require a join with other leaves ?
2818 if (newval >= tp->dmt_budmin) {
2819 /* pickup a pointer to the leaves of the tree.
2821 leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx);
2823 /* try to join the specified leaf into a large binary
2824 * buddy system. the join proceeds by attempting to join
2825 * the specified leafno with its buddy (leaf) at new value.
2826 * if the join occurs, we attempt to join the left leaf
2827 * of the joined buddies with its buddy at new value + 1.
2828 * we continue to join until we find a buddy that cannot be
2829 * joined (does not have a value equal to the size of the
2830 * last join) or until all leaves have been joined into a
2833 * get the buddy size (number of words covered) of
2836 budsz = BUDSIZE(newval, tp->dmt_budmin);
2840 while (budsz < le32_to_cpu(tp->dmt_nleafs)) {
2841 /* get the buddy leaf.
2843 buddy = leafno ^ budsz;
2845 /* if the leaf's new value is greater than its
2846 * buddy's value, we join no more.
2848 if (newval > leaf[buddy])
2851 /* It shouldn't be less */
2852 if (newval < leaf[buddy])
2855 /* check which (leafno or buddy) is the left buddy.
2856 * the left buddy gets to claim the blocks resulting
2857 * from the join while the right gets to claim none.
2858 * the left buddy is also eligible to participate in
2859 * a join at the next higher level while the right
2863 if (leafno < buddy) {
2864 /* leafno is the left buddy.
2866 dbAdjTree(tp, buddy, NOFREE);
2868 /* buddy is the left buddy and becomes
2871 dbAdjTree(tp, leafno, NOFREE);
2875 /* on to try the next join.
2882 /* update the leaf value.
2884 dbAdjTree(tp, leafno, newval);
2893 * FUNCTION: update a leaf of a dmtree with a new value, adjusting
2894 * the dmtree, as required, to reflect the new leaf value.
2895 * the combination of any buddies must already be done before
2899 * tp - pointer to the tree to be adjusted.
2900 * leafno - the number of the leaf to be updated.
2901 * newval - the new value for the leaf.
2903 * RETURN VALUES: none
2905 static void dbAdjTree(dmtree_t * tp, int leafno, int newval)
2910 /* pick up the index of the leaf for this leafno.
2912 lp = leafno + le32_to_cpu(tp->dmt_leafidx);
2914 /* is the current value the same as the old value ? if so,
2915 * there is nothing to do.
2917 if (tp->dmt_stree[lp] == newval)
2920 /* set the new value.
2922 tp->dmt_stree[lp] = newval;
2924 /* bubble the new value up the tree as required.
2926 for (k = 0; k < le32_to_cpu(tp->dmt_height); k++) {
2927 /* get the index of the first leaf of the 4 leaf
2928 * group containing the specified leaf (leafno).
2930 lp = ((lp - 1) & ~0x03) + 1;
2932 /* get the index of the parent of this 4 leaf group.
2936 /* determine the maximum of the 4 leaves.
2938 max = TREEMAX(&tp->dmt_stree[lp]);
2940 /* if the maximum of the 4 is the same as the
2941 * parent's value, we're done.
2943 if (tp->dmt_stree[pp] == max)
2946 /* parent gets new value.
2948 tp->dmt_stree[pp] = max;
2950 /* parent becomes leaf for next go-round.
2958 * NAME: dbFindLeaf()
2960 * FUNCTION: search a dmtree_t for sufficient free blocks, returning
2961 * the index of a leaf describing the free blocks if
2962 * sufficient free blocks are found.
2964 * the search starts at the top of the dmtree_t tree and
2965 * proceeds down the tree to the leftmost leaf with sufficient
2969 * tp - pointer to the tree to be searched.
2970 * l2nb - log2 number of free blocks to search for.
2971 * leafidx - return pointer to be set to the index of the leaf
2972 * describing at least l2nb free blocks if sufficient
2973 * free blocks are found.
2977 * -ENOSPC - insufficient free blocks.
2979 static int dbFindLeaf(dmtree_t * tp, int l2nb, int *leafidx)
2981 int ti, n = 0, k, x = 0;
2983 /* first check the root of the tree to see if there is
2984 * sufficient free space.
2986 if (l2nb > tp->dmt_stree[ROOT])
2989 /* sufficient free space available. now search down the tree
2990 * starting at the next level for the leftmost leaf that
2991 * describes sufficient free space.
2993 for (k = le32_to_cpu(tp->dmt_height), ti = 1;
2994 k > 0; k--, ti = ((ti + n) << 2) + 1) {
2995 /* search the four nodes at this level, starting from
2998 for (x = ti, n = 0; n < 4; n++) {
2999 /* sufficient free space found. move to the next
3000 * level (or quit if this is the last level).
3002 if (l2nb <= tp->dmt_stree[x + n])
3006 /* better have found something since the higher
3007 * levels of the tree said it was here.
3012 /* set the return to the leftmost leaf describing sufficient
3015 *leafidx = x + n - le32_to_cpu(tp->dmt_leafidx);
3022 * NAME: dbFindBits()
3024 * FUNCTION: find a specified number of binary buddy free bits within a
3025 * dmap bitmap word value.
3027 * this routine searches the bitmap value for (1 << l2nb) free
3028 * bits at (1 << l2nb) alignments within the value.
3031 * word - dmap bitmap word value.
3032 * l2nb - number of free bits specified as a log2 number.
3035 * starting bit number of free bits.
3037 static int dbFindBits(u32 word, int l2nb)
3042 /* get the number of bits.
3045 assert(nb <= DBWORD);
3047 /* complement the word so we can use a mask (i.e. 0s represent
3048 * free bits) and compute the mask.
3051 mask = ONES << (DBWORD - nb);
3053 /* scan the word for nb free bits at nb alignments.
3055 for (bitno = 0; mask != 0; bitno += nb, mask >>= nb) {
3056 if ((mask & word) == mask)
3062 /* return the bit number.
3069 * NAME: dbMaxBud(u8 *cp)
3071 * FUNCTION: determine the largest binary buddy string of free
3072 * bits within 32-bits of the map.
3075 * cp - pointer to the 32-bit value.
3078 * largest binary buddy of free bits within a dmap word.
3080 static int dbMaxBud(u8 * cp)
3082 signed char tmp1, tmp2;
3084 /* check if the wmap word is all free. if so, the
3085 * free buddy size is BUDMIN.
3087 if (*((uint *) cp) == 0)
3090 /* check if the wmap word is half free. if so, the
3091 * free buddy size is BUDMIN-1.
3093 if (*((u16 *) cp) == 0 || *((u16 *) cp + 1) == 0)
3094 return (BUDMIN - 1);
3096 /* not all free or half free. determine the free buddy
3097 * size thru table lookup using quarters of the wmap word.
3099 tmp1 = max(budtab[cp[2]], budtab[cp[3]]);
3100 tmp2 = max(budtab[cp[0]], budtab[cp[1]]);
3101 return (max(tmp1, tmp2));
3106 * NAME: cnttz(uint word)
3108 * FUNCTION: determine the number of trailing zeros within a 32-bit
3112 * value - 32-bit value to be examined.
3115 * count of trailing zeros
3117 static int cnttz(u32 word)
3121 for (n = 0; n < 32; n++, word >>= 1) {
3131 * NAME: cntlz(u32 value)
3133 * FUNCTION: determine the number of leading zeros within a 32-bit
3137 * value - 32-bit value to be examined.
3140 * count of leading zeros
3142 static int cntlz(u32 value)
3146 for (n = 0; n < 32; n++, value <<= 1) {
3147 if (value & HIGHORDER)
3155 * NAME: blkstol2(s64 nb)
3157 * FUNCTION: convert a block count to its log2 value. if the block
3158 * count is not a l2 multiple, it is rounded up to the next
3159 * larger l2 multiple.
3162 * nb - number of blocks
3165 * log2 number of blocks
3167 static int blkstol2(s64 nb)
3170 s64 mask; /* meant to be signed */
3172 mask = (s64) 1 << (64 - 1);
3174 /* count the leading bits.
3176 for (l2nb = 0; l2nb < 64; l2nb++, mask >>= 1) {
3177 /* leading bit found.
3180 /* determine the l2 value.
3182 l2nb = (64 - 1) - l2nb;
3184 /* check if we need to round up.
3193 return 0; /* fix compiler warning */
3198 * NAME: dbAllocBottomUp()
3200 * FUNCTION: alloc the specified block range from the working block
3203 * the blocks will be alloc from the working map one dmap
3207 * ip - pointer to in-core inode;
3208 * blkno - starting block number to be freed.
3209 * nblocks - number of blocks to be freed.
3215 int dbAllocBottomUp(struct inode *ip, s64 blkno, s64 nblocks)
3217 struct metapage *mp;
3221 struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap;
3222 struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap;
3224 IREAD_LOCK(ipbmap, RDWRLOCK_DMAP);
3226 /* block to be allocated better be within the mapsize. */
3227 ASSERT(nblocks <= bmp->db_mapsize - blkno);
3230 * allocate the blocks a dmap at a time.
3233 for (rem = nblocks; rem > 0; rem -= nb, blkno += nb) {
3234 /* release previous dmap if any */
3239 /* get the buffer for the current dmap. */
3240 lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
3241 mp = read_metapage(ipbmap, lblkno, PSIZE, 0);
3243 IREAD_UNLOCK(ipbmap);
3246 dp = (struct dmap *) mp->data;
3248 /* determine the number of blocks to be allocated from
3251 nb = min(rem, BPERDMAP - (blkno & (BPERDMAP - 1)));
3253 /* allocate the blocks. */
3254 if ((rc = dbAllocDmapBU(bmp, dp, blkno, nb))) {
3255 release_metapage(mp);
3256 IREAD_UNLOCK(ipbmap);
3261 /* write the last buffer. */
3264 IREAD_UNLOCK(ipbmap);
3270 static int dbAllocDmapBU(struct bmap * bmp, struct dmap * dp, s64 blkno,
3274 int dbitno, word, rembits, nb, nwords, wbitno, agno;
3276 struct dmaptree *tp = (struct dmaptree *) & dp->tree;
3278 /* save the current value of the root (i.e. maximum free string)
3281 oldroot = tp->stree[ROOT];
3283 /* determine the bit number and word within the dmap of the
3286 dbitno = blkno & (BPERDMAP - 1);
3287 word = dbitno >> L2DBWORD;
3289 /* block range better be within the dmap */
3290 assert(dbitno + nblocks <= BPERDMAP);
3292 /* allocate the bits of the dmap's words corresponding to the block
3293 * range. not all bits of the first and last words may be contained
3294 * within the block range. if this is the case, we'll work against
3295 * those words (i.e. partial first and/or last) on an individual basis
3296 * (a single pass), allocating the bits of interest by hand and
3297 * updating the leaf corresponding to the dmap word. a single pass
3298 * will be used for all dmap words fully contained within the
3299 * specified range. within this pass, the bits of all fully contained
3300 * dmap words will be marked as free in a single shot and the leaves
3301 * will be updated. a single leaf may describe the free space of
3302 * multiple dmap words, so we may update only a subset of the actual
3303 * leaves corresponding to the dmap words of the block range.
3305 for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) {
3306 /* determine the bit number within the word and
3307 * the number of bits within the word.
3309 wbitno = dbitno & (DBWORD - 1);
3310 nb = min(rembits, DBWORD - wbitno);
3312 /* check if only part of a word is to be allocated.
3315 /* allocate (set to 1) the appropriate bits within
3318 dp->wmap[word] |= cpu_to_le32(ONES << (DBWORD - nb)
3323 /* one or more dmap words are fully contained
3324 * within the block range. determine how many
3325 * words and allocate (set to 1) the bits of these
3328 nwords = rembits >> L2DBWORD;
3329 memset(&dp->wmap[word], (int) ONES, nwords * 4);
3331 /* determine how many bits */
3332 nb = nwords << L2DBWORD;
3337 /* update the free count for this dmap */
3338 le32_add_cpu(&dp->nfree, -nblocks);
3340 /* reconstruct summary tree */
3345 /* if this allocation group is completely free,
3346 * update the highest active allocation group number
3347 * if this allocation group is the new max.
3349 agno = blkno >> bmp->db_agl2size;
3350 if (agno > bmp->db_maxag)
3351 bmp->db_maxag = agno;
3353 /* update the free count for the allocation group and map */
3354 bmp->db_agfree[agno] -= nblocks;
3355 bmp->db_nfree -= nblocks;
3359 /* if the root has not changed, done. */
3360 if (tp->stree[ROOT] == oldroot)
3363 /* root changed. bubble the change up to the dmap control pages.
3364 * if the adjustment of the upper level control pages fails,
3365 * backout the bit allocation (thus making everything consistent).
3367 if ((rc = dbAdjCtl(bmp, blkno, tp->stree[ROOT], 1, 0)))
3368 dbFreeBits(bmp, dp, blkno, nblocks);
3375 * NAME: dbExtendFS()
3377 * FUNCTION: extend bmap from blkno for nblocks;
3378 * dbExtendFS() updates bmap ready for dbAllocBottomUp();
3382 * L1---------------------------------L1
3384 * L0---------L0---------L0 L0---------L0---------L0
3386 * d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,...,dn d0,.,dm;
3387 * L2L1L0d0,...,dnL0d0,...,dnL0d0,...,dnL1L0d0,...,dnL0d0,...,dnL0d0,..dm
3389 * <---old---><----------------------------extend----------------------->
3391 int dbExtendFS(struct inode *ipbmap, s64 blkno, s64 nblocks)
3393 struct jfs_sb_info *sbi = JFS_SBI(ipbmap->i_sb);
3394 int nbperpage = sbi->nbperpage;
3395 int i, i0 = true, j, j0 = true, k, n;
3398 struct metapage *mp, *l2mp, *l1mp = NULL, *l0mp = NULL;
3399 struct dmapctl *l2dcp, *l1dcp, *l0dcp;
3401 s8 *l0leaf, *l1leaf, *l2leaf;
3402 struct bmap *bmp = sbi->bmap;
3403 int agno, l2agsize, oldl2agsize;
3406 newsize = blkno + nblocks;
3408 jfs_info("dbExtendFS: blkno:%Ld nblocks:%Ld newsize:%Ld",
3409 (long long) blkno, (long long) nblocks, (long long) newsize);
3412 * initialize bmap control page.
3414 * all the data in bmap control page should exclude
3415 * the mkfs hidden dmap page.
3418 /* update mapsize */
3419 bmp->db_mapsize = newsize;
3420 bmp->db_maxlevel = BMAPSZTOLEV(bmp->db_mapsize);
3422 /* compute new AG size */
3423 l2agsize = dbGetL2AGSize(newsize);
3424 oldl2agsize = bmp->db_agl2size;
3426 bmp->db_agl2size = l2agsize;
3427 bmp->db_agsize = 1 << l2agsize;
3429 /* compute new number of AG */
3430 agno = bmp->db_numag;
3431 bmp->db_numag = newsize >> l2agsize;
3432 bmp->db_numag += ((u32) newsize % (u32) bmp->db_agsize) ? 1 : 0;
3435 * reconfigure db_agfree[]
3436 * from old AG configuration to new AG configuration;
3438 * coalesce contiguous k (newAGSize/oldAGSize) AGs;
3439 * i.e., (AGi, ..., AGj) where i = k*n and j = k*(n+1) - 1 to AGn;
3440 * note: new AG size = old AG size * (2**x).
3442 if (l2agsize == oldl2agsize)
3444 k = 1 << (l2agsize - oldl2agsize);
3445 ag_rem = bmp->db_agfree[0]; /* save agfree[0] */
3446 for (i = 0, n = 0; i < agno; n++) {
3447 bmp->db_agfree[n] = 0; /* init collection point */
3449 /* coalesce contiguous k AGs; */
3450 for (j = 0; j < k && i < agno; j++, i++) {
3451 /* merge AGi to AGn */
3452 bmp->db_agfree[n] += bmp->db_agfree[i];
3455 bmp->db_agfree[0] += ag_rem; /* restore agfree[0] */
3457 for (; n < MAXAG; n++)
3458 bmp->db_agfree[n] = 0;
3461 * update highest active ag number
3464 bmp->db_maxag = bmp->db_maxag / k;
3469 * update bit maps and corresponding level control pages;
3470 * global control page db_nfree, db_agfree[agno], db_maxfreebud;
3474 p = BMAPBLKNO + nbperpage; /* L2 page */
3475 l2mp = read_metapage(ipbmap, p, PSIZE, 0);
3477 jfs_error(ipbmap->i_sb, "L2 page could not be read\n");
3480 l2dcp = (struct dmapctl *) l2mp->data;
3482 /* compute start L1 */
3483 k = blkno >> L2MAXL1SIZE;
3484 l2leaf = l2dcp->stree + CTLLEAFIND + k;
3485 p = BLKTOL1(blkno, sbi->l2nbperpage); /* L1 page */
3488 * extend each L1 in L2
3490 for (; k < LPERCTL; k++, p += nbperpage) {
3493 /* read in L1 page: (blkno & (MAXL1SIZE - 1)) */
3494 l1mp = read_metapage(ipbmap, p, PSIZE, 0);
3497 l1dcp = (struct dmapctl *) l1mp->data;
3499 /* compute start L0 */
3500 j = (blkno & (MAXL1SIZE - 1)) >> L2MAXL0SIZE;
3501 l1leaf = l1dcp->stree + CTLLEAFIND + j;
3502 p = BLKTOL0(blkno, sbi->l2nbperpage);
3505 /* assign/init L1 page */
3506 l1mp = get_metapage(ipbmap, p, PSIZE, 0);
3510 l1dcp = (struct dmapctl *) l1mp->data;
3512 /* compute start L0 */
3514 l1leaf = l1dcp->stree + CTLLEAFIND;
3515 p += nbperpage; /* 1st L0 of L1.k */
3519 * extend each L0 in L1
3521 for (; j < LPERCTL; j++) {
3524 /* read in L0 page: (blkno & (MAXL0SIZE - 1)) */
3526 l0mp = read_metapage(ipbmap, p, PSIZE, 0);
3529 l0dcp = (struct dmapctl *) l0mp->data;
3531 /* compute start dmap */
3532 i = (blkno & (MAXL0SIZE - 1)) >>
3534 l0leaf = l0dcp->stree + CTLLEAFIND + i;
3535 p = BLKTODMAP(blkno,
3539 /* assign/init L0 page */
3540 l0mp = get_metapage(ipbmap, p, PSIZE, 0);
3544 l0dcp = (struct dmapctl *) l0mp->data;
3546 /* compute start dmap */
3548 l0leaf = l0dcp->stree + CTLLEAFIND;
3549 p += nbperpage; /* 1st dmap of L0.j */
3553 * extend each dmap in L0
3555 for (; i < LPERCTL; i++) {
3557 * reconstruct the dmap page, and
3558 * initialize corresponding parent L0 leaf
3560 if ((n = blkno & (BPERDMAP - 1))) {
3561 /* read in dmap page: */
3562 mp = read_metapage(ipbmap, p,
3566 n = min(nblocks, (s64)BPERDMAP - n);
3568 /* assign/init dmap page */
3569 mp = read_metapage(ipbmap, p,
3574 n = min_t(s64, nblocks, BPERDMAP);
3577 dp = (struct dmap *) mp->data;
3578 *l0leaf = dbInitDmap(dp, blkno, n);
3581 agno = le64_to_cpu(dp->start) >> l2agsize;
3582 bmp->db_agfree[agno] += n;
3593 } /* for each dmap in a L0 */
3596 * build current L0 page from its leaves, and
3597 * initialize corresponding parent L1 leaf
3599 *l1leaf = dbInitDmapCtl(l0dcp, 0, ++i);
3600 write_metapage(l0mp);
3604 l1leaf++; /* continue for next L0 */
3606 /* more than 1 L0 ? */
3608 break; /* build L1 page */
3610 /* summarize in global bmap page */
3611 bmp->db_maxfreebud = *l1leaf;
3612 release_metapage(l1mp);
3613 release_metapage(l2mp);
3617 } /* for each L0 in a L1 */
3620 * build current L1 page from its leaves, and
3621 * initialize corresponding parent L2 leaf
3623 *l2leaf = dbInitDmapCtl(l1dcp, 1, ++j);
3624 write_metapage(l1mp);
3628 l2leaf++; /* continue for next L1 */
3630 /* more than 1 L1 ? */
3632 break; /* build L2 page */
3634 /* summarize in global bmap page */
3635 bmp->db_maxfreebud = *l2leaf;
3636 release_metapage(l2mp);
3640 } /* for each L1 in a L2 */
3642 jfs_error(ipbmap->i_sb, "function has not returned as expected\n");
3645 release_metapage(l0mp);
3647 release_metapage(l1mp);
3648 release_metapage(l2mp);
3652 * finalize bmap control page
3663 void dbFinalizeBmap(struct inode *ipbmap)
3665 struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap;
3666 int actags, inactags, l2nl;
3667 s64 ag_rem, actfree, inactfree, avgfree;
3671 * finalize bmap control page
3675 * compute db_agpref: preferred ag to allocate from
3676 * (the leftmost ag with average free space in it);
3679 /* get the number of active ags and inacitve ags */
3680 actags = bmp->db_maxag + 1;
3681 inactags = bmp->db_numag - actags;
3682 ag_rem = bmp->db_mapsize & (bmp->db_agsize - 1); /* ??? */
3684 /* determine how many blocks are in the inactive allocation
3685 * groups. in doing this, we must account for the fact that
3686 * the rightmost group might be a partial group (i.e. file
3687 * system size is not a multiple of the group size).
3689 inactfree = (inactags && ag_rem) ?
3690 ((inactags - 1) << bmp->db_agl2size) + ag_rem
3691 : inactags << bmp->db_agl2size;
3693 /* determine how many free blocks are in the active
3694 * allocation groups plus the average number of free blocks
3695 * within the active ags.
3697 actfree = bmp->db_nfree - inactfree;
3698 avgfree = (u32) actfree / (u32) actags;
3700 /* if the preferred allocation group has not average free space.
3701 * re-establish the preferred group as the leftmost
3702 * group with average free space.
3704 if (bmp->db_agfree[bmp->db_agpref] < avgfree) {
3705 for (bmp->db_agpref = 0; bmp->db_agpref < actags;
3707 if (bmp->db_agfree[bmp->db_agpref] >= avgfree)
3710 if (bmp->db_agpref >= bmp->db_numag) {
3711 jfs_error(ipbmap->i_sb,
3712 "cannot find ag with average freespace\n");
3717 * compute db_aglevel, db_agheight, db_width, db_agstart:
3718 * an ag is covered in aglevel dmapctl summary tree,
3719 * at agheight level height (from leaf) with agwidth number of nodes
3720 * each, which starts at agstart index node of the smmary tree node
3723 bmp->db_aglevel = BMAPSZTOLEV(bmp->db_agsize);
3725 bmp->db_agl2size - (L2BPERDMAP + bmp->db_aglevel * L2LPERCTL);
3726 bmp->db_agheight = l2nl >> 1;
3727 bmp->db_agwidth = 1 << (l2nl - (bmp->db_agheight << 1));
3728 for (i = 5 - bmp->db_agheight, bmp->db_agstart = 0, n = 1; i > 0;
3730 bmp->db_agstart += n;
3738 * NAME: dbInitDmap()/ujfs_idmap_page()
3740 * FUNCTION: initialize working/persistent bitmap of the dmap page
3741 * for the specified number of blocks:
3743 * at entry, the bitmaps had been initialized as free (ZEROS);
3744 * The number of blocks will only account for the actually
3745 * existing blocks. Blocks which don't actually exist in
3746 * the aggregate will be marked as allocated (ONES);
3749 * dp - pointer to page of map
3750 * nblocks - number of blocks this page
3754 static int dbInitDmap(struct dmap * dp, s64 Blkno, int nblocks)
3756 int blkno, w, b, r, nw, nb, i;
3758 /* starting block number within the dmap */
3759 blkno = Blkno & (BPERDMAP - 1);
3762 dp->nblocks = dp->nfree = cpu_to_le32(nblocks);
3763 dp->start = cpu_to_le64(Blkno);
3765 if (nblocks == BPERDMAP) {
3766 memset(&dp->wmap[0], 0, LPERDMAP * 4);
3767 memset(&dp->pmap[0], 0, LPERDMAP * 4);
3771 le32_add_cpu(&dp->nblocks, nblocks);
3772 le32_add_cpu(&dp->nfree, nblocks);
3775 /* word number containing start block number */
3776 w = blkno >> L2DBWORD;
3779 * free the bits corresponding to the block range (ZEROS):
3780 * note: not all bits of the first and last words may be contained
3781 * within the block range.
3783 for (r = nblocks; r > 0; r -= nb, blkno += nb) {
3784 /* number of bits preceding range to be freed in the word */
3785 b = blkno & (DBWORD - 1);
3786 /* number of bits to free in the word */
3787 nb = min(r, DBWORD - b);
3789 /* is partial word to be freed ? */
3791 /* free (set to 0) from the bitmap word */
3792 dp->wmap[w] &= cpu_to_le32(~(ONES << (DBWORD - nb)
3794 dp->pmap[w] &= cpu_to_le32(~(ONES << (DBWORD - nb)
3797 /* skip the word freed */
3800 /* free (set to 0) contiguous bitmap words */
3802 memset(&dp->wmap[w], 0, nw * 4);
3803 memset(&dp->pmap[w], 0, nw * 4);
3805 /* skip the words freed */
3806 nb = nw << L2DBWORD;
3812 * mark bits following the range to be freed (non-existing
3813 * blocks) as allocated (ONES)
3816 if (blkno == BPERDMAP)
3819 /* the first word beyond the end of existing blocks */
3820 w = blkno >> L2DBWORD;
3822 /* does nblocks fall on a 32-bit boundary ? */
3823 b = blkno & (DBWORD - 1);
3825 /* mark a partial word allocated */
3826 dp->wmap[w] = dp->pmap[w] = cpu_to_le32(ONES >> b);
3830 /* set the rest of the words in the page to allocated (ONES) */
3831 for (i = w; i < LPERDMAP; i++)
3832 dp->pmap[i] = dp->wmap[i] = cpu_to_le32(ONES);
3838 return (dbInitDmapTree(dp));
3843 * NAME: dbInitDmapTree()/ujfs_complete_dmap()
3845 * FUNCTION: initialize summary tree of the specified dmap:
3847 * at entry, bitmap of the dmap has been initialized;
3850 * dp - dmap to complete
3851 * blkno - starting block number for this dmap
3852 * treemax - will be filled in with max free for this dmap
3854 * RETURNS: max free string at the root of the tree
3856 static int dbInitDmapTree(struct dmap * dp)
3858 struct dmaptree *tp;
3862 /* init fixed info of tree */
3864 tp->nleafs = cpu_to_le32(LPERDMAP);
3865 tp->l2nleafs = cpu_to_le32(L2LPERDMAP);
3866 tp->leafidx = cpu_to_le32(LEAFIND);
3867 tp->height = cpu_to_le32(4);
3868 tp->budmin = BUDMIN;
3870 /* init each leaf from corresponding wmap word:
3871 * note: leaf is set to NOFREE(-1) if all blocks of corresponding
3872 * bitmap word are allocated.
3874 cp = tp->stree + le32_to_cpu(tp->leafidx);
3875 for (i = 0; i < LPERDMAP; i++)
3876 *cp++ = dbMaxBud((u8 *) & dp->wmap[i]);
3878 /* build the dmap's binary buddy summary tree */
3879 return (dbInitTree(tp));
3884 * NAME: dbInitTree()/ujfs_adjtree()
3886 * FUNCTION: initialize binary buddy summary tree of a dmap or dmapctl.
3888 * at entry, the leaves of the tree has been initialized
3889 * from corresponding bitmap word or root of summary tree
3890 * of the child control page;
3891 * configure binary buddy system at the leaf level, then
3892 * bubble up the values of the leaf nodes up the tree.
3895 * cp - Pointer to the root of the tree
3896 * l2leaves- Number of leaf nodes as a power of 2
3897 * l2min - Number of blocks that can be covered by a leaf
3900 * RETURNS: max free string at the root of the tree
3902 static int dbInitTree(struct dmaptree * dtp)
3904 int l2max, l2free, bsize, nextb, i;
3905 int child, parent, nparent;
3910 /* Determine the maximum free string possible for the leaves */
3911 l2max = le32_to_cpu(dtp->l2nleafs) + dtp->budmin;
3914 * configure the leaf levevl into binary buddy system
3916 * Try to combine buddies starting with a buddy size of 1
3917 * (i.e. two leaves). At a buddy size of 1 two buddy leaves
3918 * can be combined if both buddies have a maximum free of l2min;
3919 * the combination will result in the left-most buddy leaf having
3920 * a maximum free of l2min+1.
3921 * After processing all buddies for a given size, process buddies
3922 * at the next higher buddy size (i.e. current size * 2) and
3923 * the next maximum free (current free + 1).
3924 * This continues until the maximum possible buddy combination
3925 * yields maximum free.
3927 for (l2free = dtp->budmin, bsize = 1; l2free < l2max;
3928 l2free++, bsize = nextb) {
3929 /* get next buddy size == current buddy pair size */
3932 /* scan each adjacent buddy pair at current buddy size */
3933 for (i = 0, cp = tp + le32_to_cpu(dtp->leafidx);
3934 i < le32_to_cpu(dtp->nleafs);
3935 i += nextb, cp += nextb) {
3936 /* coalesce if both adjacent buddies are max free */
3937 if (*cp == l2free && *(cp + bsize) == l2free) {
3938 *cp = l2free + 1; /* left take right */
3939 *(cp + bsize) = -1; /* right give left */
3945 * bubble summary information of leaves up the tree.
3947 * Starting at the leaf node level, the four nodes described by
3948 * the higher level parent node are compared for a maximum free and
3949 * this maximum becomes the value of the parent node.
3950 * when all lower level nodes are processed in this fashion then
3951 * move up to the next level (parent becomes a lower level node) and
3952 * continue the process for that level.
3954 for (child = le32_to_cpu(dtp->leafidx),
3955 nparent = le32_to_cpu(dtp->nleafs) >> 2;
3956 nparent > 0; nparent >>= 2, child = parent) {
3957 /* get index of 1st node of parent level */
3958 parent = (child - 1) >> 2;
3960 /* set the value of the parent node as the maximum
3961 * of the four nodes of the current level.
3963 for (i = 0, cp = tp + child, cp1 = tp + parent;
3964 i < nparent; i++, cp += 4, cp1++)
3975 * function: initialize dmapctl page
3977 static int dbInitDmapCtl(struct dmapctl * dcp, int level, int i)
3978 { /* start leaf index not covered by range */
3981 dcp->nleafs = cpu_to_le32(LPERCTL);
3982 dcp->l2nleafs = cpu_to_le32(L2LPERCTL);
3983 dcp->leafidx = cpu_to_le32(CTLLEAFIND);
3984 dcp->height = cpu_to_le32(5);
3985 dcp->budmin = L2BPERDMAP + L2LPERCTL * level;
3988 * initialize the leaves of current level that were not covered
3989 * by the specified input block range (i.e. the leaves have no
3990 * low level dmapctl or dmap).
3992 cp = &dcp->stree[CTLLEAFIND + i];
3993 for (; i < LPERCTL; i++)
3996 /* build the dmap's binary buddy summary tree */
3997 return (dbInitTree((struct dmaptree *) dcp));
4002 * NAME: dbGetL2AGSize()/ujfs_getagl2size()
4004 * FUNCTION: Determine log2(allocation group size) from aggregate size
4007 * nblocks - Number of blocks in aggregate
4009 * RETURNS: log2(allocation group size) in aggregate blocks
4011 static int dbGetL2AGSize(s64 nblocks)
4017 if (nblocks < BPERDMAP * MAXAG)
4018 return (L2BPERDMAP);
4020 /* round up aggregate size to power of 2 */
4021 m = ((u64) 1 << (64 - 1));
4022 for (l2sz = 64; l2sz >= 0; l2sz--, m >>= 1) {
4027 sz = (s64) 1 << l2sz;
4031 /* agsize = roundupSize/max_number_of_ag */
4032 return (l2sz - L2MAXAG);
4037 * NAME: dbMapFileSizeToMapSize()
4039 * FUNCTION: compute number of blocks the block allocation map file
4040 * can cover from the map file size;
4042 * RETURNS: Number of blocks which can be covered by this block map file;
4046 * maximum number of map pages at each level including control pages
4048 #define MAXL0PAGES (1 + LPERCTL)
4049 #define MAXL1PAGES (1 + LPERCTL * MAXL0PAGES)
4050 #define MAXL2PAGES (1 + LPERCTL * MAXL1PAGES)
4053 * convert number of map pages to the zero origin top dmapctl level
4055 #define BMAPPGTOLEV(npages) \
4056 (((npages) <= 3 + MAXL0PAGES) ? 0 : \
4057 ((npages) <= 2 + MAXL1PAGES) ? 1 : 2)
4059 s64 dbMapFileSizeToMapSize(struct inode * ipbmap)
4061 struct super_block *sb = ipbmap->i_sb;
4065 int complete, factor;
4067 nblocks = ipbmap->i_size >> JFS_SBI(sb)->l2bsize;
4068 npages = nblocks >> JFS_SBI(sb)->l2nbperpage;
4069 level = BMAPPGTOLEV(npages);
4071 /* At each level, accumulate the number of dmap pages covered by
4072 * the number of full child levels below it;
4073 * repeat for the last incomplete child level.
4076 npages--; /* skip the first global control page */
4077 /* skip higher level control pages above top level covered by map */
4078 npages -= (2 - level);
4079 npages--; /* skip top level's control page */
4080 for (i = level; i >= 0; i--) {
4082 (i == 2) ? MAXL1PAGES : ((i == 1) ? MAXL0PAGES : 1);
4083 complete = (u32) npages / factor;
4084 ndmaps += complete * ((i == 2) ? LPERCTL * LPERCTL :
4085 ((i == 1) ? LPERCTL : 1));
4087 /* pages in last/incomplete child */
4088 npages = (u32) npages % factor;
4089 /* skip incomplete child's level control page */
4093 /* convert the number of dmaps into the number of blocks
4094 * which can be covered by the dmaps;
4096 nblocks = ndmaps << L2BPERDMAP;