ufs_bmap.c revision 331722 
1/*	$NetBSD: ufs_bmap.c,v 1.14 2004/06/20 22:20:18 jmc Exp $	*/
2/* From: NetBSD: ufs_bmap.c,v 1.14 2001/11/08 05:00:51 chs Exp */
3
4/*
5 * Copyright (c) 1989, 1991, 1993
6 *	The Regents of the University of California.  All rights reserved.
7 * (c) UNIX System Laboratories, Inc.
8 * All or some portions of this file are derived from material licensed
9 * to the University of California by American Telephone and Telegraph
10 * Co. or Unix System Laboratories, Inc. and are reproduced herein with
11 * the permission of UNIX System Laboratories, Inc.
12 *
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions
15 * are met:
16 * 1. Redistributions of source code must retain the above copyright
17 *    notice, this list of conditions and the following disclaimer.
18 * 2. Redistributions in binary form must reproduce the above copyright
19 *    notice, this list of conditions and the following disclaimer in the
20 *    documentation and/or other materials provided with the distribution.
21 * 3. Neither the name of the University nor the names of its contributors
22 *    may be used to endorse or promote products derived from this software
23 *    without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 * SUCH DAMAGE.
36 *
37 *	@(#)ufs_bmap.c	8.8 (Berkeley) 8/11/95
38 */
39
40#include <sys/cdefs.h>
41__FBSDID("$FreeBSD: stable/11/usr.sbin/makefs/ffs/ufs_bmap.c 331722 2018-03-29 02:50:57Z eadler $");
42
43#include <sys/param.h>
44#include <sys/time.h>
45
46#include <assert.h>
47#include <errno.h>
48#include <strings.h>
49
50#include "makefs.h"
51
52#include <ufs/ufs/dinode.h>
53#include <ufs/ffs/fs.h>
54
55#include "ffs/ufs_bswap.h"
56#include "ffs/ufs_inode.h"
57#include "ffs/ffs_extern.h"
58
59/*
60 * Create an array of logical block number/offset pairs which represent the
61 * path of indirect blocks required to access a data block.  The first "pair"
62 * contains the logical block number of the appropriate single, double or
63 * triple indirect block and the offset into the inode indirect block array.
64 * Note, the logical block number of the inode single/double/triple indirect
65 * block appears twice in the array, once with the offset into the i_ffs_ib and
66 * once with the offset into the page itself.
67 */
68int
69ufs_getlbns(struct inode *ip, daddr_t bn, struct indir *ap, int *nump)
70{
71	daddr_t metalbn, realbn;
72	int64_t blockcnt;
73	int lbc;
74	int i, numlevels, off;
75	u_long lognindir;
76
77	lognindir = ffs(NINDIR(ip->i_fs)) - 1;
78	if (nump)
79		*nump = 0;
80	numlevels = 0;
81	realbn = bn;
82	if ((long)bn < 0)
83		bn = -(long)bn;
84
85	assert (bn >= NDADDR);
86
87	/*
88	 * Determine the number of levels of indirection.  After this loop
89	 * is done, blockcnt indicates the number of data blocks possible
90	 * at the given level of indirection, and NIADDR - i is the number
91	 * of levels of indirection needed to locate the requested block.
92	 */
93
94	bn -= NDADDR;
95	for (lbc = 0, i = NIADDR;; i--, bn -= blockcnt) {
96		if (i == 0)
97			return (EFBIG);
98
99		lbc += lognindir;
100		blockcnt = (int64_t)1 << lbc;
101
102		if (bn < blockcnt)
103			break;
104	}
105
106	/* Calculate the address of the first meta-block. */
107	if (realbn >= 0)
108		metalbn = -(realbn - bn + NIADDR - i);
109	else
110		metalbn = -(-realbn - bn + NIADDR - i);
111
112	/*
113	 * At each iteration, off is the offset into the bap array which is
114	 * an array of disk addresses at the current level of indirection.
115	 * The logical block number and the offset in that block are stored
116	 * into the argument array.
117	 */
118	ap->in_lbn = metalbn;
119	ap->in_off = off = NIADDR - i;
120	ap++;
121	for (++numlevels; i <= NIADDR; i++) {
122		/* If searching for a meta-data block, quit when found. */
123		if (metalbn == realbn)
124			break;
125
126		lbc -= lognindir;
127		blockcnt = (int64_t)1 << lbc;
128		off = (bn >> lbc) & (NINDIR(ip->i_fs) - 1);
129
130		++numlevels;
131		ap->in_lbn = metalbn;
132		ap->in_off = off;
133		++ap;
134
135		metalbn -= -1 + (off << lbc);
136	}
137	if (nump)
138		*nump = numlevels;
139	return (0);
140}
141