1/*
2 * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
3 * All Rights Reserved.
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope that it would be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write the Free Software Foundation,
16 * Inc.,  51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
17 */
18#include "xfs.h"
19#include "xfs_fs.h"
20#include "xfs_types.h"
21#include "xfs_bit.h"
22#include "xfs_log.h"
23#include "xfs_inum.h"
24#include "xfs_trans.h"
25#include "xfs_sb.h"
26#include "xfs_ag.h"
27#include "xfs_mount.h"
28#include "xfs_bmap_btree.h"
29#include "xfs_alloc_btree.h"
30#include "xfs_ialloc_btree.h"
31#include "xfs_dinode.h"
32#include "xfs_inode.h"
33#include "xfs_btree.h"
34#include "xfs_btree_trace.h"
35#include "xfs_ialloc.h"
36#include "xfs_alloc.h"
37#include "xfs_error.h"
38
39
40STATIC int
41xfs_inobt_get_minrecs(
42	struct xfs_btree_cur	*cur,
43	int			level)
44{
45	return cur->bc_mp->m_inobt_mnr[level != 0];
46}
47
48STATIC struct xfs_btree_cur *
49xfs_inobt_dup_cursor(
50	struct xfs_btree_cur	*cur)
51{
52	return xfs_inobt_init_cursor(cur->bc_mp, cur->bc_tp,
53			cur->bc_private.a.agbp, cur->bc_private.a.agno);
54}
55
56STATIC void
57xfs_inobt_set_root(
58	struct xfs_btree_cur	*cur,
59	union xfs_btree_ptr	*nptr,
60	int			inc)	/* level change */
61{
62	struct xfs_buf		*agbp = cur->bc_private.a.agbp;
63	struct xfs_agi		*agi = XFS_BUF_TO_AGI(agbp);
64
65	agi->agi_root = nptr->s;
66	be32_add_cpu(&agi->agi_level, inc);
67	xfs_ialloc_log_agi(cur->bc_tp, agbp, XFS_AGI_ROOT | XFS_AGI_LEVEL);
68}
69
70STATIC int
71xfs_inobt_alloc_block(
72	struct xfs_btree_cur	*cur,
73	union xfs_btree_ptr	*start,
74	union xfs_btree_ptr	*new,
75	int			length,
76	int			*stat)
77{
78	xfs_alloc_arg_t		args;		/* block allocation args */
79	int			error;		/* error return value */
80	xfs_agblock_t		sbno = be32_to_cpu(start->s);
81
82	XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
83
84	memset(&args, 0, sizeof(args));
85	args.tp = cur->bc_tp;
86	args.mp = cur->bc_mp;
87	args.fsbno = XFS_AGB_TO_FSB(args.mp, cur->bc_private.a.agno, sbno);
88	args.minlen = 1;
89	args.maxlen = 1;
90	args.prod = 1;
91	args.type = XFS_ALLOCTYPE_NEAR_BNO;
92
93	error = xfs_alloc_vextent(&args);
94	if (error) {
95		XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
96		return error;
97	}
98	if (args.fsbno == NULLFSBLOCK) {
99		XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
100		*stat = 0;
101		return 0;
102	}
103	ASSERT(args.len == 1);
104	XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
105
106	new->s = cpu_to_be32(XFS_FSB_TO_AGBNO(args.mp, args.fsbno));
107	*stat = 1;
108	return 0;
109}
110
111STATIC int
112xfs_inobt_free_block(
113	struct xfs_btree_cur	*cur,
114	struct xfs_buf		*bp)
115{
116	xfs_fsblock_t		fsbno;
117	int			error;
118
119	fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, XFS_BUF_ADDR(bp));
120	error = xfs_free_extent(cur->bc_tp, fsbno, 1);
121	if (error)
122		return error;
123
124	xfs_trans_binval(cur->bc_tp, bp);
125	return error;
126}
127
128STATIC int
129xfs_inobt_get_maxrecs(
130	struct xfs_btree_cur	*cur,
131	int			level)
132{
133	return cur->bc_mp->m_inobt_mxr[level != 0];
134}
135
136STATIC void
137xfs_inobt_init_key_from_rec(
138	union xfs_btree_key	*key,
139	union xfs_btree_rec	*rec)
140{
141	key->inobt.ir_startino = rec->inobt.ir_startino;
142}
143
144STATIC void
145xfs_inobt_init_rec_from_key(
146	union xfs_btree_key	*key,
147	union xfs_btree_rec	*rec)
148{
149	rec->inobt.ir_startino = key->inobt.ir_startino;
150}
151
152STATIC void
153xfs_inobt_init_rec_from_cur(
154	struct xfs_btree_cur	*cur,
155	union xfs_btree_rec	*rec)
156{
157	rec->inobt.ir_startino = cpu_to_be32(cur->bc_rec.i.ir_startino);
158	rec->inobt.ir_freecount = cpu_to_be32(cur->bc_rec.i.ir_freecount);
159	rec->inobt.ir_free = cpu_to_be64(cur->bc_rec.i.ir_free);
160}
161
162/*
163 * initial value of ptr for lookup
164 */
165STATIC void
166xfs_inobt_init_ptr_from_cur(
167	struct xfs_btree_cur	*cur,
168	union xfs_btree_ptr	*ptr)
169{
170	struct xfs_agi		*agi = XFS_BUF_TO_AGI(cur->bc_private.a.agbp);
171
172	ASSERT(cur->bc_private.a.agno == be32_to_cpu(agi->agi_seqno));
173
174	ptr->s = agi->agi_root;
175}
176
177STATIC __int64_t
178xfs_inobt_key_diff(
179	struct xfs_btree_cur	*cur,
180	union xfs_btree_key	*key)
181{
182	return (__int64_t)be32_to_cpu(key->inobt.ir_startino) -
183			  cur->bc_rec.i.ir_startino;
184}
185
186STATIC int
187xfs_inobt_kill_root(
188	struct xfs_btree_cur	*cur,
189	struct xfs_buf		*bp,
190	int			level,
191	union xfs_btree_ptr	*newroot)
192{
193	int			error;
194
195	XFS_BTREE_TRACE_CURSOR(cur, XBT_ENTRY);
196	XFS_BTREE_STATS_INC(cur, killroot);
197
198	/*
199	 * Update the root pointer, decreasing the level by 1 and then
200	 * free the old root.
201	 */
202	xfs_inobt_set_root(cur, newroot, -1);
203	error = xfs_inobt_free_block(cur, bp);
204	if (error) {
205		XFS_BTREE_TRACE_CURSOR(cur, XBT_ERROR);
206		return error;
207	}
208
209	XFS_BTREE_STATS_INC(cur, free);
210
211	cur->bc_bufs[level] = NULL;
212	cur->bc_nlevels--;
213
214	XFS_BTREE_TRACE_CURSOR(cur, XBT_EXIT);
215	return 0;
216}
217
218#ifdef DEBUG
219STATIC int
220xfs_inobt_keys_inorder(
221	struct xfs_btree_cur	*cur,
222	union xfs_btree_key	*k1,
223	union xfs_btree_key	*k2)
224{
225	return be32_to_cpu(k1->inobt.ir_startino) <
226		be32_to_cpu(k2->inobt.ir_startino);
227}
228
229STATIC int
230xfs_inobt_recs_inorder(
231	struct xfs_btree_cur	*cur,
232	union xfs_btree_rec	*r1,
233	union xfs_btree_rec	*r2)
234{
235	return be32_to_cpu(r1->inobt.ir_startino) + XFS_INODES_PER_CHUNK <=
236		be32_to_cpu(r2->inobt.ir_startino);
237}
238#endif	/* DEBUG */
239
240#ifdef XFS_BTREE_TRACE
241ktrace_t	*xfs_inobt_trace_buf;
242
243STATIC void
244xfs_inobt_trace_enter(
245	struct xfs_btree_cur	*cur,
246	const char		*func,
247	char			*s,
248	int			type,
249	int			line,
250	__psunsigned_t		a0,
251	__psunsigned_t		a1,
252	__psunsigned_t		a2,
253	__psunsigned_t		a3,
254	__psunsigned_t		a4,
255	__psunsigned_t		a5,
256	__psunsigned_t		a6,
257	__psunsigned_t		a7,
258	__psunsigned_t		a8,
259	__psunsigned_t		a9,
260	__psunsigned_t		a10)
261{
262	ktrace_enter(xfs_inobt_trace_buf, (void *)(__psint_t)type,
263		(void *)func, (void *)s, NULL, (void *)cur,
264		(void *)a0, (void *)a1, (void *)a2, (void *)a3,
265		(void *)a4, (void *)a5, (void *)a6, (void *)a7,
266		(void *)a8, (void *)a9, (void *)a10);
267}
268
269STATIC void
270xfs_inobt_trace_cursor(
271	struct xfs_btree_cur	*cur,
272	__uint32_t		*s0,
273	__uint64_t		*l0,
274	__uint64_t		*l1)
275{
276	*s0 = cur->bc_private.a.agno;
277	*l0 = cur->bc_rec.i.ir_startino;
278	*l1 = cur->bc_rec.i.ir_free;
279}
280
281STATIC void
282xfs_inobt_trace_key(
283	struct xfs_btree_cur	*cur,
284	union xfs_btree_key	*key,
285	__uint64_t		*l0,
286	__uint64_t		*l1)
287{
288	*l0 = be32_to_cpu(key->inobt.ir_startino);
289	*l1 = 0;
290}
291
292STATIC void
293xfs_inobt_trace_record(
294	struct xfs_btree_cur	*cur,
295	union xfs_btree_rec	*rec,
296	__uint64_t		*l0,
297	__uint64_t		*l1,
298	__uint64_t		*l2)
299{
300	*l0 = be32_to_cpu(rec->inobt.ir_startino);
301	*l1 = be32_to_cpu(rec->inobt.ir_freecount);
302	*l2 = be64_to_cpu(rec->inobt.ir_free);
303}
304#endif /* XFS_BTREE_TRACE */
305
306static const struct xfs_btree_ops xfs_inobt_ops = {
307	.rec_len		= sizeof(xfs_inobt_rec_t),
308	.key_len		= sizeof(xfs_inobt_key_t),
309
310	.dup_cursor		= xfs_inobt_dup_cursor,
311	.set_root		= xfs_inobt_set_root,
312	.kill_root		= xfs_inobt_kill_root,
313	.alloc_block		= xfs_inobt_alloc_block,
314	.free_block		= xfs_inobt_free_block,
315	.get_minrecs		= xfs_inobt_get_minrecs,
316	.get_maxrecs		= xfs_inobt_get_maxrecs,
317	.init_key_from_rec	= xfs_inobt_init_key_from_rec,
318	.init_rec_from_key	= xfs_inobt_init_rec_from_key,
319	.init_rec_from_cur	= xfs_inobt_init_rec_from_cur,
320	.init_ptr_from_cur	= xfs_inobt_init_ptr_from_cur,
321	.key_diff		= xfs_inobt_key_diff,
322
323#ifdef DEBUG
324	.keys_inorder		= xfs_inobt_keys_inorder,
325	.recs_inorder		= xfs_inobt_recs_inorder,
326#endif
327
328#ifdef XFS_BTREE_TRACE
329	.trace_enter		= xfs_inobt_trace_enter,
330	.trace_cursor		= xfs_inobt_trace_cursor,
331	.trace_key		= xfs_inobt_trace_key,
332	.trace_record		= xfs_inobt_trace_record,
333#endif
334};
335
336/*
337 * Allocate a new inode btree cursor.
338 */
339struct xfs_btree_cur *				/* new inode btree cursor */
340xfs_inobt_init_cursor(
341	struct xfs_mount	*mp,		/* file system mount point */
342	struct xfs_trans	*tp,		/* transaction pointer */
343	struct xfs_buf		*agbp,		/* buffer for agi structure */
344	xfs_agnumber_t		agno)		/* allocation group number */
345{
346	struct xfs_agi		*agi = XFS_BUF_TO_AGI(agbp);
347	struct xfs_btree_cur	*cur;
348
349	cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
350
351	cur->bc_tp = tp;
352	cur->bc_mp = mp;
353	cur->bc_nlevels = be32_to_cpu(agi->agi_level);
354	cur->bc_btnum = XFS_BTNUM_INO;
355	cur->bc_blocklog = mp->m_sb.sb_blocklog;
356
357	cur->bc_ops = &xfs_inobt_ops;
358
359	cur->bc_private.a.agbp = agbp;
360	cur->bc_private.a.agno = agno;
361
362	return cur;
363}
364
365/*
366 * Calculate number of records in an inobt btree block.
367 */
368int
369xfs_inobt_maxrecs(
370	struct xfs_mount	*mp,
371	int			blocklen,
372	int			leaf)
373{
374	blocklen -= XFS_INOBT_BLOCK_LEN(mp);
375
376	if (leaf)
377		return blocklen / sizeof(xfs_inobt_rec_t);
378	return blocklen / (sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t));
379}
380