1/*-
2 *  modified for Lites 1.1
3 *
4 *  Aug 1995, Godmar Back (gback@cs.utah.edu)
5 *  University of Utah, Department of Computer Science
6 */
7/*-
8 * Copyright (c) 1982, 1986, 1989, 1993
9 *	The Regents of the University of California.  All rights reserved.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 *    notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 *    notice, this list of conditions and the following disclaimer in the
18 *    documentation and/or other materials provided with the distribution.
19 * 4. Neither the name of the University nor the names of its contributors
20 *    may be used to endorse or promote products derived from this software
21 *    without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * SUCH DAMAGE.
34 *
35 *	@(#)ffs_subr.c	8.2 (Berkeley) 9/21/93
36 * $FreeBSD$
37 */
38
39#include <sys/param.h>
40
41#include <sys/proc.h>
42#include <sys/systm.h>
43#include <sys/bio.h>
44#include <sys/buf.h>
45#include <sys/lock.h>
46#include <sys/ucred.h>
47#include <sys/vnode.h>
48
49#include <fs/ext2fs/inode.h>
50#include <fs/ext2fs/ext2_extern.h>
51#include <fs/ext2fs/ext2fs.h>
52#include <fs/ext2fs/fs.h>
53#include <fs/ext2fs/ext2_extents.h>
54#include <fs/ext2fs/ext2_mount.h>
55#include <fs/ext2fs/ext2_dinode.h>
56
57#ifdef KDB
58void	ext2_checkoverlap(struct buf *, struct inode *);
59#endif
60
61/*
62 * Return buffer with the contents of block "offset" from the beginning of
63 * directory "ip".  If "res" is non-zero, fill it in with a pointer to the
64 * remaining space in the directory.
65 */
66int
67ext2_blkatoff(struct vnode *vp, off_t offset, char **res, struct buf **bpp)
68{
69	struct inode *ip;
70	struct m_ext2fs *fs;
71	struct buf *bp;
72	e2fs_lbn_t lbn;
73	int bsize, error;
74	daddr_t newblk;
75	struct ext4_extent *ep;
76	struct ext4_extent_path path;
77
78	ip = VTOI(vp);
79	fs = ip->i_e2fs;
80	lbn = lblkno(fs, offset);
81	bsize = blksize(fs, ip, lbn);
82	*bpp = NULL;
83
84	/*
85	 * IN_E4EXTENTS requires special treatment as we can otherwise fall
86	 * back to the normal path.
87	 */
88	if (!(ip->i_flag & IN_E4EXTENTS))
89		goto normal;
90
91	memset(&path, 0, sizeof(path));
92	if (ext4_ext_find_extent(fs, ip, lbn, &path) == NULL)
93		goto normal;
94	ep = path.ep_ext;
95	if (ep == NULL)
96		goto normal;
97
98	newblk = lbn - ep->e_blk +
99	    (ep->e_start_lo | (daddr_t)ep->e_start_hi << 32);
100
101	if (path.ep_bp != NULL) {
102		brelse(path.ep_bp);
103		path.ep_bp = NULL;
104	}
105	error = bread(ip->i_devvp, fsbtodb(fs, newblk), bsize, NOCRED, &bp);
106	if (error != 0) {
107		brelse(bp);
108		return (error);
109	}
110	if (res)
111		*res = (char *)bp->b_data + blkoff(fs, offset);
112	/*
113	 * If IN_E4EXTENTS is enabled we would get a wrong offset so
114	 * reset b_offset here.
115	 */
116	bp->b_offset = lbn * bsize;
117	*bpp = bp;
118	return (0);
119
120normal:
121	if (*bpp == NULL) {
122		if ((error = bread(vp, lbn, bsize, NOCRED, &bp)) != 0) {
123			brelse(bp);
124			return (error);
125		}
126		if (res)
127			*res = (char *)bp->b_data + blkoff(fs, offset);
128		*bpp = bp;
129	}
130	return (0);
131}
132
133#ifdef KDB
134void
135ext2_checkoverlap(struct buf *bp, struct inode *ip)
136{
137	struct buf *ebp, *ep;
138	e4fs_daddr_t start, last;
139	struct vnode *vp;
140
141	ebp = &buf[nbuf];
142	start = bp->b_blkno;
143	last = start + btodb(bp->b_bcount) - 1;
144	for (ep = buf; ep < ebp; ep++) {
145		if (ep == bp || (ep->b_flags & B_INVAL))
146			continue;
147		vp = ip->i_ump->um_devvp;
148		/* look for overlap */
149		if (ep->b_bcount == 0 || ep->b_blkno > last ||
150		    ep->b_blkno + btodb(ep->b_bcount) <= start)
151			continue;
152		vprint("Disk overlap", vp);
153		printf("\tstart %jd, end %jd overlap start %jd, end %jd\n",
154		    (intmax_t)start, (intmax_t)last, (intmax_t)ep->b_blkno,
155		    (intmax_t)(ep->b_blkno + btodb(ep->b_bcount) - 1));
156		panic("ext2_checkoverlap: Disk buffer overlap");
157	}
158}
159#endif /* KDB */
160
161/*
162 * Update the cluster map because of an allocation of free like ffs.
163 *
164 * Cnt == 1 means free; cnt == -1 means allocating.
165 */
166void
167ext2_clusteracct(struct m_ext2fs *fs, char *bbp, int cg, daddr_t bno, int cnt)
168{
169	int32_t *sump = fs->e2fs_clustersum[cg].cs_sum;
170	int32_t *lp;
171	int back, bit, end, forw, i, loc, start;
172
173	/* Initialize the cluster summary array. */
174	if (fs->e2fs_clustersum[cg].cs_init == 0) {
175		int run = 0;
176		bit = 1;
177		loc = 0;
178
179		for (i = 0; i < fs->e2fs->e2fs_fpg; i++) {
180			if ((bbp[loc] & bit) == 0)
181				run++;
182			else if (run != 0) {
183				if (run > fs->e2fs_contigsumsize)
184					run = fs->e2fs_contigsumsize;
185				sump[run]++;
186				run = 0;
187			}
188			if ((i & (NBBY - 1)) != (NBBY - 1))
189				bit <<= 1;
190			else {
191				loc++;
192				bit = 1;
193			}
194		}
195		if (run != 0) {
196			if (run > fs->e2fs_contigsumsize)
197				run = fs->e2fs_contigsumsize;
198			sump[run]++;
199		}
200		fs->e2fs_clustersum[cg].cs_init = 1;
201	}
202
203	if (fs->e2fs_contigsumsize <= 0)
204		return;
205
206	/* Find the size of the cluster going forward. */
207	start = bno + 1;
208	end = start + fs->e2fs_contigsumsize;
209	if (end > fs->e2fs->e2fs_fpg)
210		end = fs->e2fs->e2fs_fpg;
211	loc = start / NBBY;
212	bit = 1 << (start % NBBY);
213	for (i = start; i < end; i++) {
214		if ((bbp[loc] & bit) != 0)
215			break;
216		if ((i & (NBBY - 1)) != (NBBY - 1))
217			bit <<= 1;
218		else {
219			loc++;
220			bit = 1;
221		}
222	}
223	forw = i - start;
224
225	/* Find the size of the cluster going backward. */
226	start = bno - 1;
227	end = start - fs->e2fs_contigsumsize;
228	if (end < 0)
229		end = -1;
230	loc = start / NBBY;
231	bit = 1 << (start % NBBY);
232	for (i = start; i > end; i--) {
233		if ((bbp[loc] & bit) != 0)
234			break;
235		if ((i & (NBBY - 1)) != 0)
236			bit >>= 1;
237		else {
238			loc--;
239			bit = 1 << (NBBY - 1);
240		}
241	}
242	back = start - i;
243
244	/*
245	 * Account for old cluster and the possibly new forward and
246	 * back clusters.
247	 */
248	i = back + forw + 1;
249	if (i > fs->e2fs_contigsumsize)
250		i = fs->e2fs_contigsumsize;
251	sump[i] += cnt;
252	if (back > 0)
253		sump[back] -= cnt;
254	if (forw > 0)
255		sump[forw] -= cnt;
256
257	/* Update cluster summary information. */
258	lp = &sump[fs->e2fs_contigsumsize];
259	for (i = fs->e2fs_contigsumsize; i > 0; i--)
260		if (*lp-- > 0)
261			break;
262	fs->e2fs_maxcluster[cg] = i;
263}
264