aboutsummaryrefslogtreecommitdiff
path: root/fs/jfs/jfs_dmap.h
blob: 32e25884e7e84ca44113192b52bf4691c5c2c6e4 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
/*
 *   Copyright (c) International Business Machines Corp., 2000-2002
 *
 *   This program is free software;  you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 2 of the License, or 
 *   (at your option) any later version.
 * 
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY;  without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See
 *   the GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program;  if not, write to the Free Software 
 *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */
#ifndef	_H_JFS_DMAP
#define _H_JFS_DMAP

#include "jfs_txnmgr.h"

#define BMAPVERSION	1	/* version number */
#define	TREESIZE	(256+64+16+4+1)	/* size of a dmap tree */
#define	LEAFIND		(64+16+4+1)	/* index of 1st leaf of a dmap tree */
#define LPERDMAP	256	/* num leaves per dmap tree */
#define L2LPERDMAP	8	/* l2 number of leaves per dmap tree */
#define	DBWORD		32	/* # of blks covered by a map word */
#define	L2DBWORD	5	/* l2 # of blks covered by a mword */
#define BUDMIN  	L2DBWORD	/* max free string in a map word */
#define BPERDMAP	(LPERDMAP * DBWORD)	/* num of blks per dmap */
#define L2BPERDMAP	13	/* l2 num of blks per dmap */
#define CTLTREESIZE	(1024+256+64+16+4+1)	/* size of a dmapctl tree */
#define CTLLEAFIND	(256+64+16+4+1)	/* idx of 1st leaf of a dmapctl tree */
#define LPERCTL		1024	/* num of leaves per dmapctl tree */
#define L2LPERCTL	10	/* l2 num of leaves per dmapctl tree */
#define	ROOT		0	/* index of the root of a tree */
#define	NOFREE		((s8) -1)	/* no blocks free */
#define	MAXAG		128	/* max number of allocation groups */
#define L2MAXAG		7	/* l2 max num of AG */
#define L2MINAGSZ	25	/* l2 of minimum AG size in bytes */
#define	BMAPBLKNO	0	/* lblkno of bmap within the map */

/*
 * maximum l2 number of disk blocks at the various dmapctl levels.
 */
#define	L2MAXL0SIZE	(L2BPERDMAP + 1 * L2LPERCTL)
#define	L2MAXL1SIZE	(L2BPERDMAP + 2 * L2LPERCTL)
#define	L2MAXL2SIZE	(L2BPERDMAP + 3 * L2LPERCTL)

/*
 * maximum number of disk blocks at the various dmapctl levels.
 */
#define	MAXL0SIZE	((s64)1 << L2MAXL0SIZE)
#define	MAXL1SIZE	((s64)1 << L2MAXL1SIZE)
#define	MAXL2SIZE	((s64)1 << L2MAXL2SIZE)

#define	MAXMAPSIZE	MAXL2SIZE	/* maximum aggregate map size */

/* 
 * determine the maximum free string for four (lower level) nodes
 * of the tree.
 */
static __inline signed char TREEMAX(signed char *cp)
{
	signed char tmp1, tmp2;

	tmp1 = max(*(cp+2), *(cp+3));
	tmp2 = max(*(cp), *(cp+1));

	return max(tmp1, tmp2);
}

/*
 * convert disk block number to the logical block number of the dmap
 * describing the disk block.  s is the log2(number of logical blocks per page)
 *
 * The calculation figures out how many logical pages are in front of the dmap.
 *	- the number of dmaps preceding it
 *	- the number of L0 pages preceding its L0 page
 *	- the number of L1 pages preceding its L1 page
 *	- 3 is added to account for the L2, L1, and L0 page for this dmap
 *	- 1 is added to account for the control page of the map.
 */
#define BLKTODMAP(b,s)    \
        ((((b) >> 13) + ((b) >> 23) + ((b) >> 33) + 3 + 1) << (s))

/*
 * convert disk block number to the logical block number of the LEVEL 0
 * dmapctl describing the disk block.  s is the log2(number of logical blocks
 * per page)
 *
 * The calculation figures out how many logical pages are in front of the L0.
 *	- the number of dmap pages preceding it
 *	- the number of L0 pages preceding it
 *	- the number of L1 pages preceding its L1 page
 *	- 2 is added to account for the L2, and L1 page for this L0
 *	- 1 is added to account for the control page of the map.
 */
#define BLKTOL0(b,s)      \
        (((((b) >> 23) << 10) + ((b) >> 23) + ((b) >> 33) + 2 + 1) << (s))

/*
 * convert disk block number to the logical block number of the LEVEL 1
 * dmapctl describing the disk block.  s is the log2(number of logical blocks
 * per page)
 *
 * The calculation figures out how many logical pages are in front of the L1.
 *	- the number of dmap pages preceding it
 *	- the number of L0 pages preceding it
 *	- the number of L1 pages preceding it
 *	- 1 is added to account for the L2 page
 *	- 1 is added to account for the control page of the map.
 */
#define BLKTOL1(b,s)      \
     (((((b) >> 33) << 20) + (((b) >> 33) << 10) + ((b) >> 33) + 1 + 1) << (s))

/*
 * convert disk block number to the logical block number of the dmapctl
 * at the specified level which describes the disk block.
 */
#define BLKTOCTL(b,s,l)   \
        (((l) == 2) ? 1 : ((l) == 1) ? BLKTOL1((b),(s)) : BLKTOL0((b),(s)))

/* 
 * convert aggregate map size to the zero origin dmapctl level of the
 * top dmapctl.
 */
#define	BMAPSZTOLEV(size)	\
	(((size) <= MAXL0SIZE) ? 0 : ((size) <= MAXL1SIZE) ? 1 : 2)

/* convert disk block number to allocation group number.
 */
#define BLKTOAG(b,sbi)	((b) >> ((sbi)->bmap->db_agl2size))

/* convert allocation group number to starting disk block
 * number.
 */
#define AGTOBLK(a,ip)	\
	((s64)(a) << (JFS_SBI((ip)->i_sb)->bmap->db_agl2size))

/*
 *	dmap summary tree
 *
 * dmaptree must be consistent with dmapctl.
 */
struct dmaptree {
	__le32 nleafs;		/* 4: number of tree leafs      */
	__le32 l2nleafs;	/* 4: l2 number of tree leafs   */
	__le32 leafidx;		/* 4: index of first tree leaf  */
	__le32 height;		/* 4: height of the tree        */
	s8 budmin;		/* 1: min l2 tree leaf value to combine */
	s8 stree[TREESIZE];	/* TREESIZE: tree               */
	u8 pad[2];		/* 2: pad to word boundary      */
};				/* - 360 -                      */

/*
 *	dmap page per 8K blocks bitmap
 */
struct dmap {
	__le32 nblocks;		/* 4: num blks covered by this dmap     */
	__le32 nfree;		/* 4: num of free blks in this dmap     */
	__le64 start;		/* 8: starting blkno for this dmap      */
	struct dmaptree tree;	/* 360: dmap tree                       */
	u8 pad[1672];		/* 1672: pad to 2048 bytes              */
	__le32 wmap[LPERDMAP];	/* 1024: bits of the working map        */
	__le32 pmap[LPERDMAP];	/* 1024: bits of the persistent map     */
};				/* - 4096 -                             */

/*
 *	disk map control page per level.
 *
 * dmapctl must be consistent with dmaptree.
 */
struct dmapctl {
	__le32 nleafs;		/* 4: number of tree leafs      */
	__le32 l2nleafs;	/* 4: l2 number of tree leafs   */
	__le32 leafidx;		/* 4: index of the first tree leaf      */
	__le32 height;		/* 4: height of tree            */
	s8 budmin;		/* 1: minimum l2 tree leaf value        */
	s8 stree[CTLTREESIZE];	/* CTLTREESIZE: dmapctl tree    */
	u8 pad[2714];		/* 2714: pad to 4096            */
};				/* - 4096 -                     */

/*
 *	common definition for dmaptree within dmap and dmapctl
 */
typedef union dmtree {
	struct dmaptree t1;
	struct dmapctl t2;
} dmtree_t;

/* macros for accessing fields within dmtree */
#define	dmt_nleafs	t1.nleafs
#define	dmt_l2nleafs 	t1.l2nleafs
#define	dmt_leafidx 	t1.leafidx
#define	dmt_height 	t1.height
#define	dmt_budmin 	t1.budmin
#define	dmt_stree 	t1.stree

/* 
 *	on-disk aggregate disk allocation map descriptor.
 */
struct dbmap_disk {
	__le64 dn_mapsize;	/* 8: number of blocks in aggregate     */
	__le64 dn_nfree;	/* 8: num free blks in aggregate map    */
	__le32 dn_l2nbperpage;	/* 4: number of blks per page           */
	__le32 dn_numag;	/* 4: total number of ags               */
	__le32 dn_maxlevel;	/* 4: number of active ags              */
	__le32 dn_maxag;	/* 4: max active alloc group number     */
	__le32 dn_agpref;	/* 4: preferred alloc group (hint)      */
	__le32 dn_aglevel;	/* 4: dmapctl level holding the AG      */
	__le32 dn_agheigth;	/* 4: height in dmapctl of the AG       */
	__le32 dn_agwidth;	/* 4: width in dmapctl of the AG        */
	__le32 dn_agstart;	/* 4: start tree index at AG height     */
	__le32 dn_agl2size;	/* 4: l2 num of blks per alloc group    */
	__le64 dn_agfree[MAXAG];/* 8*MAXAG: per AG free count           */
	__le64 dn_agsize;	/* 8: num of blks per alloc group       */
	s8 dn_maxfreebud;	/* 1: max free buddy system             */
	u8 pad[3007];		/* 3007: pad to 4096                    */
};				/* - 4096 -                             */

struct dbmap {
	s64 dn_mapsize;		/* number of blocks in aggregate     */
	s64 dn_nfree;		/* num free blks in aggregate map    */
	int dn_l2nbperpage;	/* number of blks per page           */
	int dn_numag;		/* total number of ags               */
	int dn_maxlevel;	/* number of active ags              */
	int dn_maxag;		/* max active alloc group number     */
	int dn_agpref;		/* preferred alloc group (hint)      */
	int dn_aglevel;		/* dmapctl level holding the AG      */
	int dn_agheigth;	/* height in dmapctl of the AG       */
	int dn_agwidth;		/* width in dmapctl of the AG        */
	int dn_agstart;		/* start tree index at AG height     */
	int dn_agl2size;	/* l2 num of blks per alloc group    */
	s64 dn_agfree[MAXAG];	/* per AG free count           */
	s64 dn_agsize;		/* num of blks per alloc group       */
	signed char dn_maxfreebud;	/* max free buddy system             */
};				/* - 4096 -                             */
/* 
 *	in-memory aggregate disk allocation map descriptor.
 */
struct bmap {
	struct dbmap db_bmap;		/* on-disk aggregate map descriptor */
	struct inode *db_ipbmap;	/* ptr to aggregate map incore inode */
	struct semaphore db_bmaplock;	/* aggregate map lock */
	atomic_t db_active[MAXAG];	/* count of active, open files in AG */
	u32 *db_DBmap;
};

/* macros for accessing fields within in-memory aggregate map descriptor */
#define	db_mapsize	db_bmap.dn_mapsize
#define	db_nfree	db_bmap.dn_nfree
#define	db_agfree	db_bmap.dn_agfree
#define	db_agsize	db_bmap.dn_agsize
#define	db_agl2size	db_bmap.dn_agl2size
#define	db_agwidth	db_bmap.dn_agwidth
#define	db_agheigth	db_bmap.dn_agheigth
#define	db_agstart	db_bmap.dn_agstart
#define	db_numag	db_bmap.dn_numag
#define	db_maxlevel	db_bmap.dn_maxlevel
#define	db_aglevel	db_bmap.dn_aglevel
#define	db_agpref	db_bmap.dn_agpref
#define	db_maxag	db_bmap.dn_maxag
#define	db_maxfreebud	db_bmap.dn_maxfreebud
#define	db_l2nbperpage	db_bmap.dn_l2nbperpage

/*
 * macros for various conversions needed by the allocators.
 * blkstol2(), cntlz(), and cnttz() are operating system dependent functions.
 */
/* convert number of blocks to log2 number of blocks, rounding up to
 * the next log2 value if blocks is not a l2 multiple.
 */
#define	BLKSTOL2(d)		(blkstol2(d))

/* convert number of leafs to log2 leaf value */
#define	NLSTOL2BSZ(n)		(31 - cntlz((n)) + BUDMIN)

/* convert leaf index to log2 leaf value */
#define	LITOL2BSZ(n,m,b)	((((n) == 0) ? (m) : cnttz((n))) + (b))

/* convert a block number to a dmap control leaf index */
#define BLKTOCTLLEAF(b,m)	\
	(((b) & (((s64)1 << ((m) + L2LPERCTL)) - 1)) >> (m))

/* convert log2 leaf value to buddy size */
#define	BUDSIZE(s,m)		(1 << ((s) - (m)))

/*
 *	external references.
 */
extern int dbMount(struct inode *ipbmap);

extern int dbUnmount(struct inode *ipbmap, int mounterror);

extern int dbFree(struct inode *ipbmap, s64 blkno, s64 nblocks);

extern int dbUpdatePMap(struct inode *ipbmap,
			int free, s64 blkno, s64 nblocks, struct tblock * tblk);

extern int dbNextAG(struct inode *ipbmap);

extern int dbAlloc(struct inode *ipbmap, s64 hint, s64 nblocks, s64 * results);

extern int dbReAlloc(struct inode *ipbmap,
		     s64 blkno, s64 nblocks, s64 addnblocks, s64 * results);

extern int dbSync(struct inode *ipbmap);
extern int dbAllocBottomUp(struct inode *ip, s64 blkno, s64 nblocks);
extern int dbExtendFS(struct inode *ipbmap, s64 blkno, s64 nblocks);
extern void dbFinalizeBmap(struct inode *ipbmap);
extern s64 dbMapFileSizeToMapSize(struct inode *ipbmap);
#endif				/* _H_JFS_DMAP */