1 /*-
2  * SPDX-License-Identifier: BSD-3-Clause
57  * Bmap converts the logical block number of a file to its physical block
58  * number on the disk. The conversion is done by using the logical block
59  * number to index into the array of block pointers described by the dinode.
71 	if (ap->a_bop != NULL)  in ext2_bmap()
72 		*ap->a_bop = &VTOI(ap->a_vp)->i_devvp->v_bufobj;  in ext2_bmap()
73 	if (ap->a_bnp == NULL)  in ext2_bmap()
76 	if (VTOI(ap->a_vp)->i_flag & IN_E4EXTENTS)  in ext2_bmap()
77 		error = ext4_bmapext(ap->a_vp, ap->a_bn, &blkno,  in ext2_bmap()
78 		    ap->a_runp, ap->a_runb);  in ext2_bmap()
80 		error = ext2_bmaparray(ap->a_vp, ap->a_bn, &blkno,  in ext2_bmap()
81 		    ap->a_runp, ap->a_runb);  in ext2_bmap()
82 	*ap->a_bnp = blkno;  in ext2_bmap()
87  * Convert the logical block number of a file to its physical block number
93 	struct inode *ip;  in ext4_bmapext()  local
103 	ip = VTOI(vp);  in ext4_bmapext()
104 	fs = ip->i_e2fs;  in ext4_bmapext()
105 	mp = vp->v_mount;  in ext4_bmapext()
108 	ehp = (struct ext4_extent_header *)ip->i_data;  in ext4_bmapext()
109 	depth = le16toh(ehp->eh_depth);  in ext4_bmapext()
110 	bsize = EXT2_BLOCK_SIZE(ump->um_e2fs);  in ext4_bmapext()
112 	*bnp = -1;  in ext4_bmapext()
114 		maxrun = mp->mnt_iosize_max / bsize - 1;  in ext4_bmapext()
120 	error = ext4_ext_find_extent(ip, lbn, &path);  in ext4_bmapext()
126 		if (lbn < le32toh(ep->e_blk)) {  in ext4_bmapext()
128 				*runp = min(maxrun, le32toh(ep->e_blk) - lbn - 1);  in ext4_bmapext()
130 		} else if (le32toh(ep->e_blk) <= lbn &&  in ext4_bmapext()
131 			    lbn < le32toh(ep->e_blk) + le16toh(ep->e_len)) {  in ext4_bmapext()
132 			*bnp = fsbtodb(fs, lbn - le32toh(ep->e_blk) +  in ext4_bmapext()
133 			    (le32toh(ep->e_start_lo) |  in ext4_bmapext()
134 			    (daddr_t)le16toh(ep->e_start_hi) << 32));  in ext4_bmapext()
137 				    le16toh(ep->e_len) -  in ext4_bmapext()
138 				    (lbn - le32toh(ep->e_blk)) - 1);  in ext4_bmapext()
141 				*runb = min(maxrun, lbn - le32toh(ep->e_blk));  in ext4_bmapext()
144 				*runb = min(maxrun, le32toh(ep->e_blk) + lbn -  in ext4_bmapext()
145 				    le16toh(ep->e_len));  in ext4_bmapext()
162 	mp = vp->v_mount;  in readindir()
165 	bp = getblk(vp, lbn, mp->mnt_stat.f_iosize, 0, 0, 0);  in readindir()
166 	if ((bp->b_flags & B_CACHE) == 0) {  in readindir()
168 		    ("readindir: indirect block not in cache"));  in readindir()
170 		bp->b_blkno = blkptrtodb(ump, daddr);  in readindir()
171 		bp->b_iocmd = BIO_READ;  in readindir()
172 		bp->b_flags &= ~B_INVAL;  in readindir()
173 		bp->b_ioflags &= ~BIO_ERROR;  in readindir()
175 		bp->b_iooffset = dbtob(bp->b_blkno);  in readindir()
184 		curthread->td_ru.ru_inblock++;  in readindir()
197  * logical block numbers.  Indirect blocks are addressed by the negative
198  * address of the first data block to which they point.  Double indirect blocks
199  * are addressed by one less than the address of the first indirect block to
201  * the address of the first double indirect block to which they point.
204  * array of logical blocks which must be traversed to get to a block.
205  * Each entry contains the offset into that block that gets you to the
206  * next block and the disk address of the block (if it is assigned).
212 	struct inode *ip;  in ext2_bmaparray()  local
223 	ip = VTOI(vp);  in ext2_bmaparray()
224 	mp = vp->v_mount;  in ext2_bmaparray()
227 	bsize = EXT2_BLOCK_SIZE(ump->um_e2fs);  in ext2_bmaparray()
230 		maxrun = mp->mnt_iosize_max / bsize - 1;  in ext2_bmaparray()
244 		*bnp = blkptrtodb(ump, ip->i_db[bn]);  in ext2_bmaparray()
246 			*bnp = -1;  in ext2_bmaparray()
251 			    is_sequential(ump, ip->i_db[bn - 1], ip->i_db[bn]);  in ext2_bmaparray()
255 				for (--bn; (bn >= 0) && (*runb < maxrun) &&  in ext2_bmaparray()
256 					is_sequential(ump, ip->i_db[bn],  in ext2_bmaparray()
257 						ip->i_db[bn + 1]);  in ext2_bmaparray()
258 						--bn, ++*runb);  in ext2_bmaparray()
264 	/* Get disk address out of indirect block array */  in ext2_bmaparray()
265 	daddr = ip->i_ib[ap->in_off];  in ext2_bmaparray()
267 	for (bp = NULL, ++ap; --num; ++ap) {  in ext2_bmaparray()
270 		 * the indirect block isn't in the cache, or if we were  in ext2_bmaparray()
271 		 * looking for an indirect block and we've found it.  in ext2_bmaparray()
274 		metalbn = ap->in_lbn;  in ext2_bmaparray()
275 		if ((daddr == 0 && !incore(&vp->v_bufobj, metalbn)) || metalbn == bn)  in ext2_bmaparray()
278 		 * If we get here, we've either got the block in the cache  in ext2_bmaparray()
287 		daddr = le32toh(((e2fs_daddr_t *)bp->b_data)[ap->in_off]);  in ext2_bmaparray()
289 			for (bn = ap->in_off + 1;  in ext2_bmaparray()
292 			    ((e2fs_daddr_t *)bp->b_data)[bn - 1],  in ext2_bmaparray()
293 			    ((e2fs_daddr_t *)bp->b_data)[bn]);  in ext2_bmaparray()
295 			bn = ap->in_off;  in ext2_bmaparray()
297 				for (--bn; bn >= 0 && *runb < maxrun &&  in ext2_bmaparray()
299 					((e2fs_daddr_t *)bp->b_data)[bn],  in ext2_bmaparray()
300 					((e2fs_daddr_t *)bp->b_data)[bn + 1]);  in ext2_bmaparray()
301 					--bn, ++*runb);  in ext2_bmaparray()
310 		*bnp = -1;  in ext2_bmaparray()
321 	for (blockcnt = 1; level > 0; level--)  in lbn_count()
331 	struct inode *ip;  in ext2_bmap_seekdata()  local
341 	ip = VTOI(vp);  in ext2_bmap_seekdata()
342 	mp = vp->v_mount;  in ext2_bmap_seekdata()
345 	if (vp->v_type != VREG)  in ext2_bmap_seekdata()
347 	if (*offp < 0 || *offp >= ip->i_size)  in ext2_bmap_seekdata()
350 	bsize = mp->mnt_stat.f_iosize;  in ext2_bmap_seekdata()
351 	for (bn = *offp / bsize, numblks = howmany(ip->i_size, bsize);  in ext2_bmap_seekdata()
354 			daddr = ip->i_db[bn];  in ext2_bmap_seekdata()
366 		daddr = ip->i_ib[ap->in_off];  in ext2_bmap_seekdata()
367 		ap++, num--;  in ext2_bmap_seekdata()
368 		for (nextbn = EXT2_NDADDR, num1 = num - 1; num1 > 0; num1--)  in ext2_bmap_seekdata()
375 		for (; daddr != 0 && num > 0; ap++, num--) {  in ext2_bmap_seekdata()
378 			error = readindir(vp, ap->in_lbn, daddr, &bp);  in ext2_bmap_seekdata()
383 			 * Scan the indirect block until we find a non-zero  in ext2_bmap_seekdata()
386 			off = ap->in_off;  in ext2_bmap_seekdata()
388 				daddr = le32toh(((e2fs_daddr_t *)bp->b_data)[off]);  in ext2_bmap_seekdata()
390 			nextbn += off * lbn_count(ump, num - 1);  in ext2_bmap_seekdata()
394 			 * blocks, so restart with the updated block offset.  in ext2_bmap_seekdata()
396 			if (off != ap->in_off)  in ext2_bmap_seekdata()
401 			 * We found a data block.  in ext2_bmap_seekdata()
417  * Create an array of logical block number/offset pairs which represent the
418  * path of indirect blocks required to access a data block.  The first "pair"
419  * contains the logical block number of the appropriate single, double or
420  * triple indirect block and the offset into the inode indirect block array.
421  * Note, the logical block number of the inode single/double/triple indirect
422  * block appears twice in the array, once with the offset into the i_ib and
434 	ump = VFSTOEXT2(vp->v_mount);  in ext2_getlbns()
440 		bn = -(long)bn;  in ext2_getlbns()
449 	 * at the previous level of indirection, and EXT2_NIADDR - i is the  in ext2_getlbns()
450 	 * number of levels of indirection needed to locate the requested block.  in ext2_getlbns()
452 	for (blockcnt = 1, i = EXT2_NIADDR, bn -= EXT2_NDADDR; ;  in ext2_getlbns()
453 	    i--, bn -= blockcnt) {  in ext2_getlbns()
458 		 * blocks when longs have 32 bits and the block size is more  in ext2_getlbns()
467 	/* Calculate the address of the first meta-block. */  in ext2_getlbns()
469 		metalbn = -(realbn - bn + EXT2_NIADDR - i);  in ext2_getlbns()
471 		metalbn = -(-realbn - bn + EXT2_NIADDR - i);  in ext2_getlbns()
476 	 * The logical block number and the offset in that block are stored  in ext2_getlbns()
479 	ap->in_lbn = metalbn;  in ext2_getlbns()
480 	ap->in_off = off = EXT2_NIADDR - i;  in ext2_getlbns()
483 		/* If searching for a meta-data block, quit when found. */  in ext2_getlbns()
490 		ap->in_lbn = metalbn;  in ext2_getlbns()
491 		ap->in_off = off;  in ext2_getlbns()
494 		metalbn -= -1 + off * blockcnt;  in ext2_getlbns()