ext2_extents.c revision 317532 
1/*-
2 * Copyright (c) 2010 Zheng Liu <lz@freebsd.org>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in the
12 *    documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 *
26 * $FreeBSD: stable/10/sys/fs/ext2fs/ext2_extents.c 317532 2017-04-27 23:14:01Z pfg $
27 */
28
29#include <sys/param.h>
30#include <sys/systm.h>
31#include <sys/types.h>
32#include <sys/kernel.h>
33#include <sys/malloc.h>
34#include <sys/vnode.h>
35#include <sys/bio.h>
36#include <sys/buf.h>
37#include <sys/conf.h>
38
39#include <fs/ext2fs/ext2_mount.h>
40#include <fs/ext2fs/fs.h>
41#include <fs/ext2fs/inode.h>
42#include <fs/ext2fs/ext2fs.h>
43#include <fs/ext2fs/ext2_extents.h>
44#include <fs/ext2fs/ext2_extern.h>
45
46static void ext4_ext_binsearch_index(struct inode *ip, struct ext4_extent_path
47		*path, daddr_t lbn)
48{
49	struct ext4_extent_header *ehp = path->ep_header;
50	struct ext4_extent_index *l, *r, *m;
51
52	l = (struct ext4_extent_index *)(char *)(ehp + 1);
53	r = (struct ext4_extent_index *)(char *)(ehp + 1) + ehp->eh_ecount - 1;
54	while (l <= r) {
55		m = l + (r - l) / 2;
56		if (lbn < m->ei_blk)
57			r = m - 1;
58		else
59			l = m + 1;
60	}
61
62	path->ep_index = l - 1;
63}
64
65static void
66ext4_ext_binsearch(struct inode *ip, struct ext4_extent_path *path, daddr_t lbn)
67{
68	struct ext4_extent_header *ehp = path->ep_header;
69	struct ext4_extent *l, *r, *m;
70
71	if (ehp->eh_ecount == 0)
72		return;
73
74	l = (struct ext4_extent *)(char *)(ehp + 1);
75	r = (struct ext4_extent *)(char *)(ehp + 1) + ehp->eh_ecount - 1;
76	while (l <= r) {
77		m = l + (r - l) / 2;
78		if (lbn < m->e_blk)
79			r = m - 1;
80		else
81			l = m + 1;
82	}
83
84	path->ep_ext = l - 1;
85}
86
87/*
88 * Find a block in ext4 extent cache.
89 */
90int
91ext4_ext_in_cache(struct inode *ip, daddr_t lbn, struct ext4_extent *ep)
92{
93	struct ext4_extent_cache *ecp;
94	int ret = EXT4_EXT_CACHE_NO;
95
96	ecp = &ip->i_ext_cache;
97
98	/* cache is invalid */
99	if (ecp->ec_type == EXT4_EXT_CACHE_NO)
100		return (ret);
101
102	if (lbn >= ecp->ec_blk && lbn < ecp->ec_blk + ecp->ec_len) {
103		ep->e_blk = ecp->ec_blk;
104		ep->e_start_lo = ecp->ec_start & 0xffffffff;
105		ep->e_start_hi = ecp->ec_start >> 32 & 0xffff;
106		ep->e_len = ecp->ec_len;
107		ret = ecp->ec_type;
108	}
109	return (ret);
110}
111
112/*
113 * Put an ext4_extent structure in ext4 cache.
114 */
115void
116ext4_ext_put_cache(struct inode *ip, struct ext4_extent *ep, int type)
117{
118	struct ext4_extent_cache *ecp;
119
120	ecp = &ip->i_ext_cache;
121	ecp->ec_type = type;
122	ecp->ec_blk = ep->e_blk;
123	ecp->ec_len = ep->e_len;
124	ecp->ec_start = (daddr_t)ep->e_start_hi << 32 | ep->e_start_lo;
125}
126
127/*
128 * Find an extent.
129 */
130struct ext4_extent_path *
131ext4_ext_find_extent(struct m_ext2fs *fs, struct inode *ip,
132    daddr_t lbn, struct ext4_extent_path *path)
133{
134	struct ext4_extent_header *ehp;
135	uint16_t i;
136	int error, size;
137	daddr_t nblk;
138
139	ehp = (struct ext4_extent_header *)(char *)ip->i_db;
140
141	if (ehp->eh_magic != EXT4_EXT_MAGIC)
142		return (NULL);
143
144	path->ep_header = ehp;
145
146	for (i = ehp->eh_depth; i != 0; --i) {
147		ext4_ext_binsearch_index(ip, path, lbn);
148		path->ep_depth = 0;
149		path->ep_ext = NULL;
150
151		nblk = (daddr_t)path->ep_index->ei_leaf_hi << 32 |
152		    path->ep_index->ei_leaf_lo;
153		size = blksize(fs, ip, nblk);
154		if (path->ep_bp != NULL) {
155			brelse(path->ep_bp);
156			path->ep_bp = NULL;
157		}
158		error = bread(ip->i_devvp, fsbtodb(fs, nblk), size, NOCRED,
159		    &path->ep_bp);
160		if (error) {
161			brelse(path->ep_bp);
162			path->ep_bp = NULL;
163			return (NULL);
164		}
165		ehp = (struct ext4_extent_header *)path->ep_bp->b_data;
166		path->ep_header = ehp;
167	}
168
169	path->ep_depth = i;
170	path->ep_ext = NULL;
171	path->ep_index = NULL;
172
173	ext4_ext_binsearch(ip, path, lbn);
174	return (path);
175}
176