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