ext2_subr.c revision 261235
1139778Simp/*- 212115Sdyson * modified for Lites 1.1 312115Sdyson * 412115Sdyson * Aug 1995, Godmar Back (gback@cs.utah.edu) 512115Sdyson * University of Utah, Department of Computer Science 612115Sdyson */ 7139778Simp/*- 812115Sdyson * Copyright (c) 1982, 1986, 1989, 1993 912115Sdyson * The Regents of the University of California. All rights reserved. 1012115Sdyson * 1112115Sdyson * Redistribution and use in source and binary forms, with or without 1212115Sdyson * modification, are permitted provided that the following conditions 1312115Sdyson * are met: 1412115Sdyson * 1. Redistributions of source code must retain the above copyright 1512115Sdyson * notice, this list of conditions and the following disclaimer. 1612115Sdyson * 2. Redistributions in binary form must reproduce the above copyright 1712115Sdyson * notice, this list of conditions and the following disclaimer in the 1812115Sdyson * documentation and/or other materials provided with the distribution. 1912115Sdyson * 4. Neither the name of the University nor the names of its contributors 2012115Sdyson * may be used to endorse or promote products derived from this software 2112115Sdyson * without specific prior written permission. 2212115Sdyson * 2312115Sdyson * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 2412115Sdyson * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2512115Sdyson * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2612115Sdyson * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2712115Sdyson * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2812115Sdyson * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2912115Sdyson * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 3012115Sdyson * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 3112115Sdyson * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 3212115Sdyson * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3312115Sdyson * SUCH DAMAGE. 3412115Sdyson * 3593015Sbde * @(#)ffs_subr.c 8.2 (Berkeley) 9/21/93 3660041Sphk * $FreeBSD: head/sys/fs/ext2fs/ext2_subr.c 261235 2014-01-28 14:39:05Z pfg $ 3712115Sdyson */ 3812115Sdyson 3912115Sdyson#include <sys/param.h> 4012115Sdyson 4176166Smarkm#include <sys/proc.h> 4276166Smarkm#include <sys/systm.h> 4376166Smarkm#include <sys/bio.h> 4476166Smarkm#include <sys/buf.h> 4531561Sbde#include <sys/lock.h> 4669517Sbde#include <sys/ucred.h> 4712115Sdyson#include <sys/vnode.h> 4876166Smarkm 49202283Slulf#include <fs/ext2fs/inode.h> 50202283Slulf#include <fs/ext2fs/ext2_extern.h> 51202283Slulf#include <fs/ext2fs/ext2fs.h> 52202283Slulf#include <fs/ext2fs/fs.h> 53254260Spfg#include <fs/ext2fs/ext2_extents.h> 54254260Spfg#include <fs/ext2fs/ext2_mount.h> 55254260Spfg#include <fs/ext2fs/ext2_dinode.h> 5676166Smarkm 57131925Smarcel#ifdef KDB 5892728Salfredvoid ext2_checkoverlap(struct buf *, struct inode *); 5941591Sarchie#endif 6033291Sbde 6112115Sdyson/* 6212115Sdyson * Return buffer with the contents of block "offset" from the beginning of 6312115Sdyson * directory "ip". If "res" is non-zero, fill it in with a pointer to the 6412115Sdyson * remaining space in the directory. 6512115Sdyson */ 6612115Sdysonint 67246634Spfgext2_blkatoff(struct vnode *vp, off_t offset, char **res, struct buf **bpp) 6812115Sdyson{ 6912115Sdyson struct inode *ip; 70202283Slulf struct m_ext2fs *fs; 7112115Sdyson struct buf *bp; 72252103Spfg e2fs_lbn_t lbn; 7312115Sdyson int bsize, error; 74254260Spfg daddr_t newblk; 75254260Spfg struct ext4_extent *ep; 76254260Spfg struct ext4_extent_path path; 7712115Sdyson 7830474Sphk ip = VTOI(vp); 7912115Sdyson fs = ip->i_e2fs; 8030474Sphk lbn = lblkno(fs, offset); 8112115Sdyson bsize = blksize(fs, ip, lbn); 82254260Spfg *bpp = NULL; 8312115Sdyson 84254260Spfg /* 85261235Spfg * IN_E4EXTENTS requires special treatment as we can otherwise fall 86260988Spfg * back to the normal path. 87254260Spfg */ 88261235Spfg if (!(ip->i_flag & IN_E4EXTENTS)) 89254260Spfg goto normal; 90254260Spfg 91254260Spfg memset(&path, 0, sizeof(path)); 92254260Spfg if (ext4_ext_find_extent(fs, ip, lbn, &path) == NULL) 93254260Spfg goto normal; 94254260Spfg ep = path.ep_ext; 95254260Spfg if (ep == NULL) 96254260Spfg goto normal; 97254260Spfg 98254260Spfg newblk = lbn - ep->e_blk + 99254260Spfg (ep->e_start_lo | (daddr_t)ep->e_start_hi << 32); 100254260Spfg 101254260Spfg if (path.ep_bp != NULL) { 102254260Spfg brelse(path.ep_bp); 103254260Spfg path.ep_bp = NULL; 104254260Spfg } 105254260Spfg error = bread(ip->i_devvp, fsbtodb(fs, newblk), bsize, NOCRED, &bp); 106254260Spfg if (error != 0) { 10712115Sdyson brelse(bp); 10812115Sdyson return (error); 10912115Sdyson } 11030474Sphk if (res) 11130474Sphk *res = (char *)bp->b_data + blkoff(fs, offset); 112254260Spfg /* 113261235Spfg * If IN_E4EXTENTS is enabled we would get a wrong offset so 114254260Spfg * reset b_offset here. 115254260Spfg */ 116254260Spfg bp->b_offset = lbn * bsize; 11730474Sphk *bpp = bp; 11812115Sdyson return (0); 119254260Spfg 120254260Spfgnormal: 121254260Spfg if (*bpp == NULL) { 122254260Spfg if ((error = bread(vp, lbn, bsize, NOCRED, &bp)) != 0) { 123254260Spfg brelse(bp); 124254260Spfg return (error); 125254260Spfg } 126254260Spfg if (res) 127254260Spfg *res = (char *)bp->b_data + blkoff(fs, offset); 128254260Spfg *bpp = bp; 129254260Spfg } 130254260Spfg return (0); 13112115Sdyson} 13212115Sdyson 133131925Smarcel#ifdef KDB 13442539Seivindvoid 135246634Spfgext2_checkoverlap(struct buf *bp, struct inode *ip) 13612115Sdyson{ 13796752Siedowse struct buf *ebp, *ep; 138254283Spfg e4fs_daddr_t start, last; 13912115Sdyson struct vnode *vp; 14012115Sdyson 14112115Sdyson ebp = &buf[nbuf]; 14212115Sdyson start = bp->b_blkno; 14312115Sdyson last = start + btodb(bp->b_bcount) - 1; 14412115Sdyson for (ep = buf; ep < ebp; ep++) { 145136991Sphk if (ep == bp || (ep->b_flags & B_INVAL)) 14612115Sdyson continue; 147217582Sjhb vp = ip->i_ump->um_devvp; 14812115Sdyson /* look for overlap */ 14912115Sdyson if (ep->b_bcount == 0 || ep->b_blkno > last || 15012115Sdyson ep->b_blkno + btodb(ep->b_bcount) <= start) 15112115Sdyson continue; 15212115Sdyson vprint("Disk overlap", vp); 153254326Spfg printf("\tstart %jd, end %jd overlap start %jd, end %jd\n", 154254326Spfg (intmax_t)start, (intmax_t)last, (intmax_t)ep->b_blkno, 155254326Spfg (intmax_t)(ep->b_blkno + btodb(ep->b_bcount) - 1)); 156254326Spfg panic("ext2_checkoverlap: Disk buffer overlap"); 15712115Sdyson } 15812115Sdyson} 159131925Smarcel#endif /* KDB */ 160228539Spfg 161228539Spfg/* 162228539Spfg * Update the cluster map because of an allocation of free like ffs. 163228539Spfg * 164228539Spfg * Cnt == 1 means free; cnt == -1 means allocating. 165228539Spfg */ 166228539Spfgvoid 167228539Spfgext2_clusteracct(struct m_ext2fs *fs, char *bbp, int cg, daddr_t bno, int cnt) 168228539Spfg{ 169228539Spfg int32_t *sump = fs->e2fs_clustersum[cg].cs_sum; 170228539Spfg int32_t *lp; 171228539Spfg int back, bit, end, forw, i, loc, start; 172228539Spfg 173228539Spfg /* Initialize the cluster summary array. */ 174228539Spfg if (fs->e2fs_clustersum[cg].cs_init == 0) { 175228539Spfg int run = 0; 176228539Spfg bit = 1; 177228539Spfg loc = 0; 178228539Spfg 179228539Spfg for (i = 0; i < fs->e2fs->e2fs_fpg; i++) { 180228539Spfg if ((bbp[loc] & bit) == 0) 181228539Spfg run++; 182228539Spfg else if (run != 0) { 183228539Spfg if (run > fs->e2fs_contigsumsize) 184228539Spfg run = fs->e2fs_contigsumsize; 185228539Spfg sump[run]++; 186228539Spfg run = 0; 187228539Spfg } 188228539Spfg if ((i & (NBBY - 1)) != (NBBY - 1)) 189228539Spfg bit <<= 1; 190228539Spfg else { 191228539Spfg loc++; 192228539Spfg bit = 1; 193228539Spfg } 194228539Spfg } 195228539Spfg if (run != 0) { 196228539Spfg if (run > fs->e2fs_contigsumsize) 197228539Spfg run = fs->e2fs_contigsumsize; 198228539Spfg sump[run]++; 199228539Spfg } 200228539Spfg fs->e2fs_clustersum[cg].cs_init = 1; 201228539Spfg } 202228539Spfg 203228539Spfg if (fs->e2fs_contigsumsize <= 0) 204228539Spfg return; 205228539Spfg 206228539Spfg /* Find the size of the cluster going forward. */ 207228539Spfg start = bno + 1; 208228539Spfg end = start + fs->e2fs_contigsumsize; 209228539Spfg if (end > fs->e2fs->e2fs_fpg) 210228539Spfg end = fs->e2fs->e2fs_fpg; 211228539Spfg loc = start / NBBY; 212228539Spfg bit = 1 << (start % NBBY); 213228539Spfg for (i = start; i < end; i++) { 214228539Spfg if ((bbp[loc] & bit) != 0) 215228539Spfg break; 216228539Spfg if ((i & (NBBY - 1)) != (NBBY - 1)) 217228539Spfg bit <<= 1; 218228539Spfg else { 219228539Spfg loc++; 220228539Spfg bit = 1; 221228539Spfg } 222228539Spfg } 223228539Spfg forw = i - start; 224228539Spfg 225228539Spfg /* Find the size of the cluster going backward. */ 226228539Spfg start = bno - 1; 227228539Spfg end = start - fs->e2fs_contigsumsize; 228228539Spfg if (end < 0) 229228539Spfg end = -1; 230228539Spfg loc = start / NBBY; 231228539Spfg bit = 1 << (start % NBBY); 232228539Spfg for (i = start; i > end; i--) { 233228539Spfg if ((bbp[loc] & bit) != 0) 234228539Spfg break; 235228539Spfg if ((i & (NBBY - 1)) != 0) 236228539Spfg bit >>= 1; 237228539Spfg else { 238228539Spfg loc--; 239228539Spfg bit = 1 << (NBBY - 1); 240228539Spfg } 241228539Spfg } 242228539Spfg back = start - i; 243228539Spfg 244228539Spfg /* 245228539Spfg * Account for old cluster and the possibly new forward and 246228539Spfg * back clusters. 247228539Spfg */ 248228539Spfg i = back + forw + 1; 249228539Spfg if (i > fs->e2fs_contigsumsize) 250228539Spfg i = fs->e2fs_contigsumsize; 251228539Spfg sump[i] += cnt; 252228539Spfg if (back > 0) 253228539Spfg sump[back] -= cnt; 254228539Spfg if (forw > 0) 255228539Spfg sump[forw] -= cnt; 256228539Spfg 257228539Spfg /* Update cluster summary information. */ 258228539Spfg lp = &sump[fs->e2fs_contigsumsize]; 259228539Spfg for (i = fs->e2fs_contigsumsize; i > 0; i--) 260228539Spfg if (*lp-- > 0) 261228539Spfg break; 262228539Spfg fs->e2fs_maxcluster[cg] = i; 263228539Spfg} 264