xref: /openbmc/linux/fs/jfs/jfs_dmap.c (revision d5cb9783536a41df9f9cba5b0a1d78047ed787f7)
1 /*
2  *   Copyright (C) International Business Machines Corp., 2000-2004
3  *
4  *   This program is free software;  you can redistribute it and/or modify
5  *   it under the terms of the GNU General Public License as published by
6  *   the Free Software Foundation; either version 2 of the License, or
7  *   (at your option) any later version.
8  *
9  *   This program is distributed in the hope that it will be useful,
10  *   but WITHOUT ANY WARRANTY;  without even the implied warranty of
11  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See
12  *   the 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 to the Free Software
16  *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17  */
18 
19 #include <linux/fs.h>
20 #include "jfs_incore.h"
21 #include "jfs_superblock.h"
22 #include "jfs_dmap.h"
23 #include "jfs_imap.h"
24 #include "jfs_lock.h"
25 #include "jfs_metapage.h"
26 #include "jfs_debug.h"
27 
28 /*
29  *	SERIALIZATION of the Block Allocation Map.
30  *
31  *	the working state of the block allocation map is accessed in
32  *	two directions:
33  *
34  *	1) allocation and free requests that start at the dmap
35  *	   level and move up through the dmap control pages (i.e.
36  *	   the vast majority of requests).
37  *
38  * 	2) allocation requests that start at dmap control page
39  *	   level and work down towards the dmaps.
40  *
41  *	the serialization scheme used here is as follows.
42  *
43  *	requests which start at the bottom are serialized against each
44  *	other through buffers and each requests holds onto its buffers
45  *	as it works it way up from a single dmap to the required level
46  *	of dmap control page.
47  *	requests that start at the top are serialized against each other
48  *	and request that start from the bottom by the multiple read/single
49  *	write inode lock of the bmap inode. requests starting at the top
50  *	take this lock in write mode while request starting at the bottom
51  *	take the lock in read mode.  a single top-down request may proceed
52  *	exclusively while multiple bottoms-up requests may proceed
53  * 	simultaneously (under the protection of busy buffers).
54  *
55  *	in addition to information found in dmaps and dmap control pages,
56  *	the working state of the block allocation map also includes read/
57  *	write information maintained in the bmap descriptor (i.e. total
58  *	free block count, allocation group level free block counts).
59  *	a single exclusive lock (BMAP_LOCK) is used to guard this information
60  *	in the face of multiple-bottoms up requests.
61  *	(lock ordering: IREAD_LOCK, BMAP_LOCK);
62  *
63  *	accesses to the persistent state of the block allocation map (limited
64  *	to the persistent bitmaps in dmaps) is guarded by (busy) buffers.
65  */
66 
67 #define BMAP_LOCK_INIT(bmp)	init_MUTEX(&bmp->db_bmaplock)
68 #define BMAP_LOCK(bmp)		down(&bmp->db_bmaplock)
69 #define BMAP_UNLOCK(bmp)	up(&bmp->db_bmaplock)
70 
71 /*
72  * forward references
73  */
74 static void dbAllocBits(struct bmap * bmp, struct dmap * dp, s64 blkno,
75 			int nblocks);
76 static void dbSplit(dmtree_t * tp, int leafno, int splitsz, int newval);
77 static int dbBackSplit(dmtree_t * tp, int leafno);
78 static int dbJoin(dmtree_t * tp, int leafno, int newval);
79 static void dbAdjTree(dmtree_t * tp, int leafno, int newval);
80 static int dbAdjCtl(struct bmap * bmp, s64 blkno, int newval, int alloc,
81 		    int level);
82 static int dbAllocAny(struct bmap * bmp, s64 nblocks, int l2nb, s64 * results);
83 static int dbAllocNext(struct bmap * bmp, struct dmap * dp, s64 blkno,
84 		       int nblocks);
85 static int dbAllocNear(struct bmap * bmp, struct dmap * dp, s64 blkno,
86 		       int nblocks,
87 		       int l2nb, s64 * results);
88 static int dbAllocDmap(struct bmap * bmp, struct dmap * dp, s64 blkno,
89 		       int nblocks);
90 static int dbAllocDmapLev(struct bmap * bmp, struct dmap * dp, int nblocks,
91 			  int l2nb,
92 			  s64 * results);
93 static int dbAllocAG(struct bmap * bmp, int agno, s64 nblocks, int l2nb,
94 		     s64 * results);
95 static int dbAllocCtl(struct bmap * bmp, s64 nblocks, int l2nb, s64 blkno,
96 		      s64 * results);
97 static int dbExtend(struct inode *ip, s64 blkno, s64 nblocks, s64 addnblocks);
98 static int dbFindBits(u32 word, int l2nb);
99 static int dbFindCtl(struct bmap * bmp, int l2nb, int level, s64 * blkno);
100 static int dbFindLeaf(dmtree_t * tp, int l2nb, int *leafidx);
101 static int dbFreeBits(struct bmap * bmp, struct dmap * dp, s64 blkno,
102 		      int nblocks);
103 static int dbFreeDmap(struct bmap * bmp, struct dmap * dp, s64 blkno,
104 		      int nblocks);
105 static int dbMaxBud(u8 * cp);
106 s64 dbMapFileSizeToMapSize(struct inode *ipbmap);
107 static int blkstol2(s64 nb);
108 
109 static int cntlz(u32 value);
110 static int cnttz(u32 word);
111 
112 static int dbAllocDmapBU(struct bmap * bmp, struct dmap * dp, s64 blkno,
113 			 int nblocks);
114 static int dbInitDmap(struct dmap * dp, s64 blkno, int nblocks);
115 static int dbInitDmapTree(struct dmap * dp);
116 static int dbInitTree(struct dmaptree * dtp);
117 static int dbInitDmapCtl(struct dmapctl * dcp, int level, int i);
118 static int dbGetL2AGSize(s64 nblocks);
119 
120 /*
121  *	buddy table
122  *
123  * table used for determining buddy sizes within characters of
124  * dmap bitmap words.  the characters themselves serve as indexes
125  * into the table, with the table elements yielding the maximum
126  * binary buddy of free bits within the character.
127  */
128 static s8 budtab[256] = {
129 	3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
130 	2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
131 	2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
132 	2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
133 	2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
134 	2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
135 	2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
136 	2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
137 	2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
138 	2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
139 	2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
140 	2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
141 	2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
142 	2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
143 	2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
144 	2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, -1
145 };
146 
147 
148 /*
149  * NAME:    	dbMount()
150  *
151  * FUNCTION:	initializate the block allocation map.
152  *
153  *		memory is allocated for the in-core bmap descriptor and
154  *		the in-core descriptor is initialized from disk.
155  *
156  * PARAMETERS:
157  *      ipbmap	-  pointer to in-core inode for the block map.
158  *
159  * RETURN VALUES:
160  *      0	- success
161  *      -ENOMEM	- insufficient memory
162  *      -EIO	- i/o error
163  */
164 int dbMount(struct inode *ipbmap)
165 {
166 	struct bmap *bmp;
167 	struct dbmap_disk *dbmp_le;
168 	struct metapage *mp;
169 	int i;
170 
171 	/*
172 	 * allocate/initialize the in-memory bmap descriptor
173 	 */
174 	/* allocate memory for the in-memory bmap descriptor */
175 	bmp = kmalloc(sizeof(struct bmap), GFP_KERNEL);
176 	if (bmp == NULL)
177 		return -ENOMEM;
178 
179 	/* read the on-disk bmap descriptor. */
180 	mp = read_metapage(ipbmap,
181 			   BMAPBLKNO << JFS_SBI(ipbmap->i_sb)->l2nbperpage,
182 			   PSIZE, 0);
183 	if (mp == NULL) {
184 		kfree(bmp);
185 		return -EIO;
186 	}
187 
188 	/* copy the on-disk bmap descriptor to its in-memory version. */
189 	dbmp_le = (struct dbmap_disk *) mp->data;
190 	bmp->db_mapsize = le64_to_cpu(dbmp_le->dn_mapsize);
191 	bmp->db_nfree = le64_to_cpu(dbmp_le->dn_nfree);
192 	bmp->db_l2nbperpage = le32_to_cpu(dbmp_le->dn_l2nbperpage);
193 	bmp->db_numag = le32_to_cpu(dbmp_le->dn_numag);
194 	bmp->db_maxlevel = le32_to_cpu(dbmp_le->dn_maxlevel);
195 	bmp->db_maxag = le32_to_cpu(dbmp_le->dn_maxag);
196 	bmp->db_agpref = le32_to_cpu(dbmp_le->dn_agpref);
197 	bmp->db_aglevel = le32_to_cpu(dbmp_le->dn_aglevel);
198 	bmp->db_agheigth = le32_to_cpu(dbmp_le->dn_agheigth);
199 	bmp->db_agwidth = le32_to_cpu(dbmp_le->dn_agwidth);
200 	bmp->db_agstart = le32_to_cpu(dbmp_le->dn_agstart);
201 	bmp->db_agl2size = le32_to_cpu(dbmp_le->dn_agl2size);
202 	for (i = 0; i < MAXAG; i++)
203 		bmp->db_agfree[i] = le64_to_cpu(dbmp_le->dn_agfree[i]);
204 	bmp->db_agsize = le64_to_cpu(dbmp_le->dn_agsize);
205 	bmp->db_maxfreebud = dbmp_le->dn_maxfreebud;
206 
207 	/* release the buffer. */
208 	release_metapage(mp);
209 
210 	/* bind the bmap inode and the bmap descriptor to each other. */
211 	bmp->db_ipbmap = ipbmap;
212 	JFS_SBI(ipbmap->i_sb)->bmap = bmp;
213 
214 	memset(bmp->db_active, 0, sizeof(bmp->db_active));
215 
216 	/*
217 	 * allocate/initialize the bmap lock
218 	 */
219 	BMAP_LOCK_INIT(bmp);
220 
221 	return (0);
222 }
223 
224 
225 /*
226  * NAME:    	dbUnmount()
227  *
228  * FUNCTION:	terminate the block allocation map in preparation for
229  *		file system unmount.
230  *
231  * 		the in-core bmap descriptor is written to disk and
232  *		the memory for this descriptor is freed.
233  *
234  * PARAMETERS:
235  *      ipbmap	-  pointer to in-core inode for the block map.
236  *
237  * RETURN VALUES:
238  *      0	- success
239  *      -EIO	- i/o error
240  */
241 int dbUnmount(struct inode *ipbmap, int mounterror)
242 {
243 	struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap;
244 
245 	if (!(mounterror || isReadOnly(ipbmap)))
246 		dbSync(ipbmap);
247 
248 	/*
249 	 * Invalidate the page cache buffers
250 	 */
251 	truncate_inode_pages(ipbmap->i_mapping, 0);
252 
253 	/* free the memory for the in-memory bmap. */
254 	kfree(bmp);
255 
256 	return (0);
257 }
258 
259 /*
260  *	dbSync()
261  */
262 int dbSync(struct inode *ipbmap)
263 {
264 	struct dbmap_disk *dbmp_le;
265 	struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap;
266 	struct metapage *mp;
267 	int i;
268 
269 	/*
270 	 * write bmap global control page
271 	 */
272 	/* get the buffer for the on-disk bmap descriptor. */
273 	mp = read_metapage(ipbmap,
274 			   BMAPBLKNO << JFS_SBI(ipbmap->i_sb)->l2nbperpage,
275 			   PSIZE, 0);
276 	if (mp == NULL) {
277 		jfs_err("dbSync: read_metapage failed!");
278 		return -EIO;
279 	}
280 	/* copy the in-memory version of the bmap to the on-disk version */
281 	dbmp_le = (struct dbmap_disk *) mp->data;
282 	dbmp_le->dn_mapsize = cpu_to_le64(bmp->db_mapsize);
283 	dbmp_le->dn_nfree = cpu_to_le64(bmp->db_nfree);
284 	dbmp_le->dn_l2nbperpage = cpu_to_le32(bmp->db_l2nbperpage);
285 	dbmp_le->dn_numag = cpu_to_le32(bmp->db_numag);
286 	dbmp_le->dn_maxlevel = cpu_to_le32(bmp->db_maxlevel);
287 	dbmp_le->dn_maxag = cpu_to_le32(bmp->db_maxag);
288 	dbmp_le->dn_agpref = cpu_to_le32(bmp->db_agpref);
289 	dbmp_le->dn_aglevel = cpu_to_le32(bmp->db_aglevel);
290 	dbmp_le->dn_agheigth = cpu_to_le32(bmp->db_agheigth);
291 	dbmp_le->dn_agwidth = cpu_to_le32(bmp->db_agwidth);
292 	dbmp_le->dn_agstart = cpu_to_le32(bmp->db_agstart);
293 	dbmp_le->dn_agl2size = cpu_to_le32(bmp->db_agl2size);
294 	for (i = 0; i < MAXAG; i++)
295 		dbmp_le->dn_agfree[i] = cpu_to_le64(bmp->db_agfree[i]);
296 	dbmp_le->dn_agsize = cpu_to_le64(bmp->db_agsize);
297 	dbmp_le->dn_maxfreebud = bmp->db_maxfreebud;
298 
299 	/* write the buffer */
300 	write_metapage(mp);
301 
302 	/*
303 	 * write out dirty pages of bmap
304 	 */
305 	filemap_fdatawrite(ipbmap->i_mapping);
306 	filemap_fdatawait(ipbmap->i_mapping);
307 
308 	diWriteSpecial(ipbmap, 0);
309 
310 	return (0);
311 }
312 
313 
314 /*
315  * NAME:    	dbFree()
316  *
317  * FUNCTION:	free the specified block range from the working block
318  *		allocation map.
319  *
320  *		the blocks will be free from the working map one dmap
321  *		at a time.
322  *
323  * PARAMETERS:
324  *      ip	-  pointer to in-core inode;
325  *      blkno	-  starting block number to be freed.
326  *      nblocks	-  number of blocks to be freed.
327  *
328  * RETURN VALUES:
329  *      0	- success
330  *      -EIO	- i/o error
331  */
332 int dbFree(struct inode *ip, s64 blkno, s64 nblocks)
333 {
334 	struct metapage *mp;
335 	struct dmap *dp;
336 	int nb, rc;
337 	s64 lblkno, rem;
338 	struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap;
339 	struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap;
340 
341 	IREAD_LOCK(ipbmap);
342 
343 	/* block to be freed better be within the mapsize. */
344 	if (unlikely((blkno == 0) || (blkno + nblocks > bmp->db_mapsize))) {
345 		IREAD_UNLOCK(ipbmap);
346 		printk(KERN_ERR "blkno = %Lx, nblocks = %Lx\n",
347 		       (unsigned long long) blkno,
348 		       (unsigned long long) nblocks);
349 		jfs_error(ip->i_sb,
350 			  "dbFree: block to be freed is outside the map");
351 		return -EIO;
352 	}
353 
354 	/*
355 	 * free the blocks a dmap at a time.
356 	 */
357 	mp = NULL;
358 	for (rem = nblocks; rem > 0; rem -= nb, blkno += nb) {
359 		/* release previous dmap if any */
360 		if (mp) {
361 			write_metapage(mp);
362 		}
363 
364 		/* get the buffer for the current dmap. */
365 		lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
366 		mp = read_metapage(ipbmap, lblkno, PSIZE, 0);
367 		if (mp == NULL) {
368 			IREAD_UNLOCK(ipbmap);
369 			return -EIO;
370 		}
371 		dp = (struct dmap *) mp->data;
372 
373 		/* determine the number of blocks to be freed from
374 		 * this dmap.
375 		 */
376 		nb = min(rem, BPERDMAP - (blkno & (BPERDMAP - 1)));
377 
378 		/* free the blocks. */
379 		if ((rc = dbFreeDmap(bmp, dp, blkno, nb))) {
380 			jfs_error(ip->i_sb, "dbFree: error in block map\n");
381 			release_metapage(mp);
382 			IREAD_UNLOCK(ipbmap);
383 			return (rc);
384 		}
385 	}
386 
387 	/* write the last buffer. */
388 	write_metapage(mp);
389 
390 	IREAD_UNLOCK(ipbmap);
391 
392 	return (0);
393 }
394 
395 
396 /*
397  * NAME:	dbUpdatePMap()
398  *
399  * FUNCTION:    update the allocation state (free or allocate) of the
400  *		specified block range in the persistent block allocation map.
401  *
402  *		the blocks will be updated in the persistent map one
403  *		dmap at a time.
404  *
405  * PARAMETERS:
406  *      ipbmap	-  pointer to in-core inode for the block map.
407  *      free	- TRUE if block range is to be freed from the persistent
408  *		  map; FALSE if it is to   be allocated.
409  *      blkno	-  starting block number of the range.
410  *      nblocks	-  number of contiguous blocks in the range.
411  *      tblk	-  transaction block;
412  *
413  * RETURN VALUES:
414  *      0	- success
415  *      -EIO	- i/o error
416  */
417 int
418 dbUpdatePMap(struct inode *ipbmap,
419 	     int free, s64 blkno, s64 nblocks, struct tblock * tblk)
420 {
421 	int nblks, dbitno, wbitno, rbits;
422 	int word, nbits, nwords;
423 	struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap;
424 	s64 lblkno, rem, lastlblkno;
425 	u32 mask;
426 	struct dmap *dp;
427 	struct metapage *mp;
428 	struct jfs_log *log;
429 	int lsn, difft, diffp;
430 	unsigned long flags;
431 
432 	/* the blocks better be within the mapsize. */
433 	if (blkno + nblocks > bmp->db_mapsize) {
434 		printk(KERN_ERR "blkno = %Lx, nblocks = %Lx\n",
435 		       (unsigned long long) blkno,
436 		       (unsigned long long) nblocks);
437 		jfs_error(ipbmap->i_sb,
438 			  "dbUpdatePMap: blocks are outside the map");
439 		return -EIO;
440 	}
441 
442 	/* compute delta of transaction lsn from log syncpt */
443 	lsn = tblk->lsn;
444 	log = (struct jfs_log *) JFS_SBI(tblk->sb)->log;
445 	logdiff(difft, lsn, log);
446 
447 	/*
448 	 * update the block state a dmap at a time.
449 	 */
450 	mp = NULL;
451 	lastlblkno = 0;
452 	for (rem = nblocks; rem > 0; rem -= nblks, blkno += nblks) {
453 		/* get the buffer for the current dmap. */
454 		lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
455 		if (lblkno != lastlblkno) {
456 			if (mp) {
457 				write_metapage(mp);
458 			}
459 
460 			mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE,
461 					   0);
462 			if (mp == NULL)
463 				return -EIO;
464 			metapage_wait_for_io(mp);
465 		}
466 		dp = (struct dmap *) mp->data;
467 
468 		/* determine the bit number and word within the dmap of
469 		 * the starting block.  also determine how many blocks
470 		 * are to be updated within this dmap.
471 		 */
472 		dbitno = blkno & (BPERDMAP - 1);
473 		word = dbitno >> L2DBWORD;
474 		nblks = min(rem, (s64)BPERDMAP - dbitno);
475 
476 		/* update the bits of the dmap words. the first and last
477 		 * words may only have a subset of their bits updated. if
478 		 * this is the case, we'll work against that word (i.e.
479 		 * partial first and/or last) only in a single pass.  a
480 		 * single pass will also be used to update all words that
481 		 * are to have all their bits updated.
482 		 */
483 		for (rbits = nblks; rbits > 0;
484 		     rbits -= nbits, dbitno += nbits) {
485 			/* determine the bit number within the word and
486 			 * the number of bits within the word.
487 			 */
488 			wbitno = dbitno & (DBWORD - 1);
489 			nbits = min(rbits, DBWORD - wbitno);
490 
491 			/* check if only part of the word is to be updated. */
492 			if (nbits < DBWORD) {
493 				/* update (free or allocate) the bits
494 				 * in this word.
495 				 */
496 				mask =
497 				    (ONES << (DBWORD - nbits) >> wbitno);
498 				if (free)
499 					dp->pmap[word] &=
500 					    cpu_to_le32(~mask);
501 				else
502 					dp->pmap[word] |=
503 					    cpu_to_le32(mask);
504 
505 				word += 1;
506 			} else {
507 				/* one or more words are to have all
508 				 * their bits updated.  determine how
509 				 * many words and how many bits.
510 				 */
511 				nwords = rbits >> L2DBWORD;
512 				nbits = nwords << L2DBWORD;
513 
514 				/* update (free or allocate) the bits
515 				 * in these words.
516 				 */
517 				if (free)
518 					memset(&dp->pmap[word], 0,
519 					       nwords * 4);
520 				else
521 					memset(&dp->pmap[word], (int) ONES,
522 					       nwords * 4);
523 
524 				word += nwords;
525 			}
526 		}
527 
528 		/*
529 		 * update dmap lsn
530 		 */
531 		if (lblkno == lastlblkno)
532 			continue;
533 
534 		lastlblkno = lblkno;
535 
536 		if (mp->lsn != 0) {
537 			/* inherit older/smaller lsn */
538 			logdiff(diffp, mp->lsn, log);
539 			LOGSYNC_LOCK(log, flags);
540 			if (difft < diffp) {
541 				mp->lsn = lsn;
542 
543 				/* move bp after tblock in logsync list */
544 				list_move(&mp->synclist, &tblk->synclist);
545 			}
546 
547 			/* inherit younger/larger clsn */
548 			logdiff(difft, tblk->clsn, log);
549 			logdiff(diffp, mp->clsn, log);
550 			if (difft > diffp)
551 				mp->clsn = tblk->clsn;
552 			LOGSYNC_UNLOCK(log, flags);
553 		} else {
554 			mp->log = log;
555 			mp->lsn = lsn;
556 
557 			/* insert bp after tblock in logsync list */
558 			LOGSYNC_LOCK(log, flags);
559 
560 			log->count++;
561 			list_add(&mp->synclist, &tblk->synclist);
562 
563 			mp->clsn = tblk->clsn;
564 			LOGSYNC_UNLOCK(log, flags);
565 		}
566 	}
567 
568 	/* write the last buffer. */
569 	if (mp) {
570 		write_metapage(mp);
571 	}
572 
573 	return (0);
574 }
575 
576 
577 /*
578  * NAME:	dbNextAG()
579  *
580  * FUNCTION:    find the preferred allocation group for new allocations.
581  *
582  *		Within the allocation groups, we maintain a preferred
583  *		allocation group which consists of a group with at least
584  *		average free space.  It is the preferred group that we target
585  *		new inode allocation towards.  The tie-in between inode
586  *		allocation and block allocation occurs as we allocate the
587  *		first (data) block of an inode and specify the inode (block)
588  *		as the allocation hint for this block.
589  *
590  *		We try to avoid having more than one open file growing in
591  *		an allocation group, as this will lead to fragmentation.
592  *		This differs from the old OS/2 method of trying to keep
593  *		empty ags around for large allocations.
594  *
595  * PARAMETERS:
596  *      ipbmap	-  pointer to in-core inode for the block map.
597  *
598  * RETURN VALUES:
599  *      the preferred allocation group number.
600  */
601 int dbNextAG(struct inode *ipbmap)
602 {
603 	s64 avgfree;
604 	int agpref;
605 	s64 hwm = 0;
606 	int i;
607 	int next_best = -1;
608 	struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap;
609 
610 	BMAP_LOCK(bmp);
611 
612 	/* determine the average number of free blocks within the ags. */
613 	avgfree = (u32)bmp->db_nfree / bmp->db_numag;
614 
615 	/*
616 	 * if the current preferred ag does not have an active allocator
617 	 * and has at least average freespace, return it
618 	 */
619 	agpref = bmp->db_agpref;
620 	if ((atomic_read(&bmp->db_active[agpref]) == 0) &&
621 	    (bmp->db_agfree[agpref] >= avgfree))
622 		goto unlock;
623 
624 	/* From the last preferred ag, find the next one with at least
625 	 * average free space.
626 	 */
627 	for (i = 0 ; i < bmp->db_numag; i++, agpref++) {
628 		if (agpref == bmp->db_numag)
629 			agpref = 0;
630 
631 		if (atomic_read(&bmp->db_active[agpref]))
632 			/* open file is currently growing in this ag */
633 			continue;
634 		if (bmp->db_agfree[agpref] >= avgfree) {
635 			/* Return this one */
636 			bmp->db_agpref = agpref;
637 			goto unlock;
638 		} else if (bmp->db_agfree[agpref] > hwm) {
639 			/* Less than avg. freespace, but best so far */
640 			hwm = bmp->db_agfree[agpref];
641 			next_best = agpref;
642 		}
643 	}
644 
645 	/*
646 	 * If no inactive ag was found with average freespace, use the
647 	 * next best
648 	 */
649 	if (next_best != -1)
650 		bmp->db_agpref = next_best;
651 	/* else leave db_agpref unchanged */
652 unlock:
653 	BMAP_UNLOCK(bmp);
654 
655 	/* return the preferred group.
656 	 */
657 	return (bmp->db_agpref);
658 }
659 
660 /*
661  * NAME:	dbAlloc()
662  *
663  * FUNCTION:    attempt to allocate a specified number of contiguous free
664  *		blocks from the working allocation block map.
665  *
666  *		the block allocation policy uses hints and a multi-step
667  *		approach.
668  *
669  *	  	for allocation requests smaller than the number of blocks
670  *		per dmap, we first try to allocate the new blocks
671  *		immediately following the hint.  if these blocks are not
672  *		available, we try to allocate blocks near the hint.  if
673  *		no blocks near the hint are available, we next try to
674  *		allocate within the same dmap as contains the hint.
675  *
676  *		if no blocks are available in the dmap or the allocation
677  *		request is larger than the dmap size, we try to allocate
678  *		within the same allocation group as contains the hint. if
679  *		this does not succeed, we finally try to allocate anywhere
680  *		within the aggregate.
681  *
682  *		we also try to allocate anywhere within the aggregate for
683  *		for allocation requests larger than the allocation group
684  *		size or requests that specify no hint value.
685  *
686  * PARAMETERS:
687  *      ip	-  pointer to in-core inode;
688  *      hint	- allocation hint.
689  *      nblocks	- number of contiguous blocks in the range.
690  *      results	- on successful return, set to the starting block number
691  *		  of the newly allocated contiguous range.
692  *
693  * RETURN VALUES:
694  *      0	- success
695  *      -ENOSPC	- insufficient disk resources
696  *      -EIO	- i/o error
697  */
698 int dbAlloc(struct inode *ip, s64 hint, s64 nblocks, s64 * results)
699 {
700 	int rc, agno;
701 	struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap;
702 	struct bmap *bmp;
703 	struct metapage *mp;
704 	s64 lblkno, blkno;
705 	struct dmap *dp;
706 	int l2nb;
707 	s64 mapSize;
708 	int writers;
709 
710 	/* assert that nblocks is valid */
711 	assert(nblocks > 0);
712 
713 #ifdef _STILL_TO_PORT
714 	/* DASD limit check                                     F226941 */
715 	if (OVER_LIMIT(ip, nblocks))
716 		return -ENOSPC;
717 #endif				/* _STILL_TO_PORT */
718 
719 	/* get the log2 number of blocks to be allocated.
720 	 * if the number of blocks is not a log2 multiple,
721 	 * it will be rounded up to the next log2 multiple.
722 	 */
723 	l2nb = BLKSTOL2(nblocks);
724 
725 	bmp = JFS_SBI(ip->i_sb)->bmap;
726 
727 //retry:        /* serialize w.r.t.extendfs() */
728 	mapSize = bmp->db_mapsize;
729 
730 	/* the hint should be within the map */
731 	if (hint >= mapSize) {
732 		jfs_error(ip->i_sb, "dbAlloc: the hint is outside the map");
733 		return -EIO;
734 	}
735 
736 	/* if the number of blocks to be allocated is greater than the
737 	 * allocation group size, try to allocate anywhere.
738 	 */
739 	if (l2nb > bmp->db_agl2size) {
740 		IWRITE_LOCK(ipbmap);
741 
742 		rc = dbAllocAny(bmp, nblocks, l2nb, results);
743 
744 		goto write_unlock;
745 	}
746 
747 	/*
748 	 * If no hint, let dbNextAG recommend an allocation group
749 	 */
750 	if (hint == 0)
751 		goto pref_ag;
752 
753 	/* we would like to allocate close to the hint.  adjust the
754 	 * hint to the block following the hint since the allocators
755 	 * will start looking for free space starting at this point.
756 	 */
757 	blkno = hint + 1;
758 
759 	if (blkno >= bmp->db_mapsize)
760 		goto pref_ag;
761 
762 	agno = blkno >> bmp->db_agl2size;
763 
764 	/* check if blkno crosses over into a new allocation group.
765 	 * if so, check if we should allow allocations within this
766 	 * allocation group.
767 	 */
768 	if ((blkno & (bmp->db_agsize - 1)) == 0)
769 		/* check if the AG is currenly being written to.
770 		 * if so, call dbNextAG() to find a non-busy
771 		 * AG with sufficient free space.
772 		 */
773 		if (atomic_read(&bmp->db_active[agno]))
774 			goto pref_ag;
775 
776 	/* check if the allocation request size can be satisfied from a
777 	 * single dmap.  if so, try to allocate from the dmap containing
778 	 * the hint using a tiered strategy.
779 	 */
780 	if (nblocks <= BPERDMAP) {
781 		IREAD_LOCK(ipbmap);
782 
783 		/* get the buffer for the dmap containing the hint.
784 		 */
785 		rc = -EIO;
786 		lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
787 		mp = read_metapage(ipbmap, lblkno, PSIZE, 0);
788 		if (mp == NULL)
789 			goto read_unlock;
790 
791 		dp = (struct dmap *) mp->data;
792 
793 		/* first, try to satisfy the allocation request with the
794 		 * blocks beginning at the hint.
795 		 */
796 		if ((rc = dbAllocNext(bmp, dp, blkno, (int) nblocks))
797 		    != -ENOSPC) {
798 			if (rc == 0) {
799 				*results = blkno;
800 				mark_metapage_dirty(mp);
801 			}
802 
803 			release_metapage(mp);
804 			goto read_unlock;
805 		}
806 
807 		writers = atomic_read(&bmp->db_active[agno]);
808 		if ((writers > 1) ||
809 		    ((writers == 1) && (JFS_IP(ip)->active_ag != agno))) {
810 			/*
811 			 * Someone else is writing in this allocation
812 			 * group.  To avoid fragmenting, try another ag
813 			 */
814 			release_metapage(mp);
815 			IREAD_UNLOCK(ipbmap);
816 			goto pref_ag;
817 		}
818 
819 		/* next, try to satisfy the allocation request with blocks
820 		 * near the hint.
821 		 */
822 		if ((rc =
823 		     dbAllocNear(bmp, dp, blkno, (int) nblocks, l2nb, results))
824 		    != -ENOSPC) {
825 			if (rc == 0)
826 				mark_metapage_dirty(mp);
827 
828 			release_metapage(mp);
829 			goto read_unlock;
830 		}
831 
832 		/* try to satisfy the allocation request with blocks within
833 		 * the same dmap as the hint.
834 		 */
835 		if ((rc = dbAllocDmapLev(bmp, dp, (int) nblocks, l2nb, results))
836 		    != -ENOSPC) {
837 			if (rc == 0)
838 				mark_metapage_dirty(mp);
839 
840 			release_metapage(mp);
841 			goto read_unlock;
842 		}
843 
844 		release_metapage(mp);
845 		IREAD_UNLOCK(ipbmap);
846 	}
847 
848 	/* try to satisfy the allocation request with blocks within
849 	 * the same allocation group as the hint.
850 	 */
851 	IWRITE_LOCK(ipbmap);
852 	if ((rc = dbAllocAG(bmp, agno, nblocks, l2nb, results)) != -ENOSPC)
853 		goto write_unlock;
854 
855 	IWRITE_UNLOCK(ipbmap);
856 
857 
858       pref_ag:
859 	/*
860 	 * Let dbNextAG recommend a preferred allocation group
861 	 */
862 	agno = dbNextAG(ipbmap);
863 	IWRITE_LOCK(ipbmap);
864 
865 	/* Try to allocate within this allocation group.  if that fails, try to
866 	 * allocate anywhere in the map.
867 	 */
868 	if ((rc = dbAllocAG(bmp, agno, nblocks, l2nb, results)) == -ENOSPC)
869 		rc = dbAllocAny(bmp, nblocks, l2nb, results);
870 
871       write_unlock:
872 	IWRITE_UNLOCK(ipbmap);
873 
874 	return (rc);
875 
876       read_unlock:
877 	IREAD_UNLOCK(ipbmap);
878 
879 	return (rc);
880 }
881 
882 #ifdef _NOTYET
883 /*
884  * NAME:	dbAllocExact()
885  *
886  * FUNCTION:    try to allocate the requested extent;
887  *
888  * PARAMETERS:
889  *      ip	- pointer to in-core inode;
890  *      blkno	- extent address;
891  *      nblocks	- extent length;
892  *
893  * RETURN VALUES:
894  *      0	- success
895  *      -ENOSPC	- insufficient disk resources
896  *      -EIO	- i/o error
897  */
898 int dbAllocExact(struct inode *ip, s64 blkno, int nblocks)
899 {
900 	int rc;
901 	struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap;
902 	struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap;
903 	struct dmap *dp;
904 	s64 lblkno;
905 	struct metapage *mp;
906 
907 	IREAD_LOCK(ipbmap);
908 
909 	/*
910 	 * validate extent request:
911 	 *
912 	 * note: defragfs policy:
913 	 *  max 64 blocks will be moved.
914 	 *  allocation request size must be satisfied from a single dmap.
915 	 */
916 	if (nblocks <= 0 || nblocks > BPERDMAP || blkno >= bmp->db_mapsize) {
917 		IREAD_UNLOCK(ipbmap);
918 		return -EINVAL;
919 	}
920 
921 	if (nblocks > ((s64) 1 << bmp->db_maxfreebud)) {
922 		/* the free space is no longer available */
923 		IREAD_UNLOCK(ipbmap);
924 		return -ENOSPC;
925 	}
926 
927 	/* read in the dmap covering the extent */
928 	lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
929 	mp = read_metapage(ipbmap, lblkno, PSIZE, 0);
930 	if (mp == NULL) {
931 		IREAD_UNLOCK(ipbmap);
932 		return -EIO;
933 	}
934 	dp = (struct dmap *) mp->data;
935 
936 	/* try to allocate the requested extent */
937 	rc = dbAllocNext(bmp, dp, blkno, nblocks);
938 
939 	IREAD_UNLOCK(ipbmap);
940 
941 	if (rc == 0)
942 		mark_metapage_dirty(mp);
943 
944 	release_metapage(mp);
945 
946 	return (rc);
947 }
948 #endif /* _NOTYET */
949 
950 /*
951  * NAME:	dbReAlloc()
952  *
953  * FUNCTION:    attempt to extend a current allocation by a specified
954  *		number of blocks.
955  *
956  *		this routine attempts to satisfy the allocation request
957  *		by first trying to extend the existing allocation in
958  *		place by allocating the additional blocks as the blocks
959  *		immediately following the current allocation.  if these
960  *		blocks are not available, this routine will attempt to
961  *		allocate a new set of contiguous blocks large enough
962  *		to cover the existing allocation plus the additional
963  *		number of blocks required.
964  *
965  * PARAMETERS:
966  *      ip	    -  pointer to in-core inode requiring allocation.
967  *      blkno	    -  starting block of the current allocation.
968  *      nblocks	    -  number of contiguous blocks within the current
969  *		       allocation.
970  *      addnblocks  -  number of blocks to add to the allocation.
971  *      results	-      on successful return, set to the starting block number
972  *		       of the existing allocation if the existing allocation
973  *		       was extended in place or to a newly allocated contiguous
974  *		       range if the existing allocation could not be extended
975  *		       in place.
976  *
977  * RETURN VALUES:
978  *      0	- success
979  *      -ENOSPC	- insufficient disk resources
980  *      -EIO	- i/o error
981  */
982 int
983 dbReAlloc(struct inode *ip,
984 	  s64 blkno, s64 nblocks, s64 addnblocks, s64 * results)
985 {
986 	int rc;
987 
988 	/* try to extend the allocation in place.
989 	 */
990 	if ((rc = dbExtend(ip, blkno, nblocks, addnblocks)) == 0) {
991 		*results = blkno;
992 		return (0);
993 	} else {
994 		if (rc != -ENOSPC)
995 			return (rc);
996 	}
997 
998 	/* could not extend the allocation in place, so allocate a
999 	 * new set of blocks for the entire request (i.e. try to get
1000 	 * a range of contiguous blocks large enough to cover the
1001 	 * existing allocation plus the additional blocks.)
1002 	 */
1003 	return (dbAlloc
1004 		(ip, blkno + nblocks - 1, addnblocks + nblocks, results));
1005 }
1006 
1007 
1008 /*
1009  * NAME:	dbExtend()
1010  *
1011  * FUNCTION:    attempt to extend a current allocation by a specified
1012  *		number of blocks.
1013  *
1014  *		this routine attempts to satisfy the allocation request
1015  *		by first trying to extend the existing allocation in
1016  *		place by allocating the additional blocks as the blocks
1017  *		immediately following the current allocation.
1018  *
1019  * PARAMETERS:
1020  *      ip	    -  pointer to in-core inode requiring allocation.
1021  *      blkno	    -  starting block of the current allocation.
1022  *      nblocks	    -  number of contiguous blocks within the current
1023  *		       allocation.
1024  *      addnblocks  -  number of blocks to add to the allocation.
1025  *
1026  * RETURN VALUES:
1027  *      0	- success
1028  *      -ENOSPC	- insufficient disk resources
1029  *      -EIO	- i/o error
1030  */
1031 static int dbExtend(struct inode *ip, s64 blkno, s64 nblocks, s64 addnblocks)
1032 {
1033 	struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb);
1034 	s64 lblkno, lastblkno, extblkno;
1035 	uint rel_block;
1036 	struct metapage *mp;
1037 	struct dmap *dp;
1038 	int rc;
1039 	struct inode *ipbmap = sbi->ipbmap;
1040 	struct bmap *bmp;
1041 
1042 	/*
1043 	 * We don't want a non-aligned extent to cross a page boundary
1044 	 */
1045 	if (((rel_block = blkno & (sbi->nbperpage - 1))) &&
1046 	    (rel_block + nblocks + addnblocks > sbi->nbperpage))
1047 		return -ENOSPC;
1048 
1049 	/* get the last block of the current allocation */
1050 	lastblkno = blkno + nblocks - 1;
1051 
1052 	/* determine the block number of the block following
1053 	 * the existing allocation.
1054 	 */
1055 	extblkno = lastblkno + 1;
1056 
1057 	IREAD_LOCK(ipbmap);
1058 
1059 	/* better be within the file system */
1060 	bmp = sbi->bmap;
1061 	if (lastblkno < 0 || lastblkno >= bmp->db_mapsize) {
1062 		IREAD_UNLOCK(ipbmap);
1063 		jfs_error(ip->i_sb,
1064 			  "dbExtend: the block is outside the filesystem");
1065 		return -EIO;
1066 	}
1067 
1068 	/* we'll attempt to extend the current allocation in place by
1069 	 * allocating the additional blocks as the blocks immediately
1070 	 * following the current allocation.  we only try to extend the
1071 	 * current allocation in place if the number of additional blocks
1072 	 * can fit into a dmap, the last block of the current allocation
1073 	 * is not the last block of the file system, and the start of the
1074 	 * inplace extension is not on an allocation group boundary.
1075 	 */
1076 	if (addnblocks > BPERDMAP || extblkno >= bmp->db_mapsize ||
1077 	    (extblkno & (bmp->db_agsize - 1)) == 0) {
1078 		IREAD_UNLOCK(ipbmap);
1079 		return -ENOSPC;
1080 	}
1081 
1082 	/* get the buffer for the dmap containing the first block
1083 	 * of the extension.
1084 	 */
1085 	lblkno = BLKTODMAP(extblkno, bmp->db_l2nbperpage);
1086 	mp = read_metapage(ipbmap, lblkno, PSIZE, 0);
1087 	if (mp == NULL) {
1088 		IREAD_UNLOCK(ipbmap);
1089 		return -EIO;
1090 	}
1091 
1092 	dp = (struct dmap *) mp->data;
1093 
1094 	/* try to allocate the blocks immediately following the
1095 	 * current allocation.
1096 	 */
1097 	rc = dbAllocNext(bmp, dp, extblkno, (int) addnblocks);
1098 
1099 	IREAD_UNLOCK(ipbmap);
1100 
1101 	/* were we successful ? */
1102 	if (rc == 0)
1103 		write_metapage(mp);
1104 	else
1105 		/* we were not successful */
1106 		release_metapage(mp);
1107 
1108 
1109 	return (rc);
1110 }
1111 
1112 
1113 /*
1114  * NAME:	dbAllocNext()
1115  *
1116  * FUNCTION:    attempt to allocate the blocks of the specified block
1117  *		range within a dmap.
1118  *
1119  * PARAMETERS:
1120  *      bmp	-  pointer to bmap descriptor
1121  *      dp	-  pointer to dmap.
1122  *      blkno	-  starting block number of the range.
1123  *      nblocks	-  number of contiguous free blocks of the range.
1124  *
1125  * RETURN VALUES:
1126  *      0	- success
1127  *      -ENOSPC	- insufficient disk resources
1128  *      -EIO	- i/o error
1129  *
1130  * serialization: IREAD_LOCK(ipbmap) held on entry/exit;
1131  */
1132 static int dbAllocNext(struct bmap * bmp, struct dmap * dp, s64 blkno,
1133 		       int nblocks)
1134 {
1135 	int dbitno, word, rembits, nb, nwords, wbitno, nw;
1136 	int l2size;
1137 	s8 *leaf;
1138 	u32 mask;
1139 
1140 	if (dp->tree.leafidx != cpu_to_le32(LEAFIND)) {
1141 		jfs_error(bmp->db_ipbmap->i_sb,
1142 			  "dbAllocNext: Corrupt dmap page");
1143 		return -EIO;
1144 	}
1145 
1146 	/* pick up a pointer to the leaves of the dmap tree.
1147 	 */
1148 	leaf = dp->tree.stree + le32_to_cpu(dp->tree.leafidx);
1149 
1150 	/* determine the bit number and word within the dmap of the
1151 	 * starting block.
1152 	 */
1153 	dbitno = blkno & (BPERDMAP - 1);
1154 	word = dbitno >> L2DBWORD;
1155 
1156 	/* check if the specified block range is contained within
1157 	 * this dmap.
1158 	 */
1159 	if (dbitno + nblocks > BPERDMAP)
1160 		return -ENOSPC;
1161 
1162 	/* check if the starting leaf indicates that anything
1163 	 * is free.
1164 	 */
1165 	if (leaf[word] == NOFREE)
1166 		return -ENOSPC;
1167 
1168 	/* check the dmaps words corresponding to block range to see
1169 	 * if the block range is free.  not all bits of the first and
1170 	 * last words may be contained within the block range.  if this
1171 	 * is the case, we'll work against those words (i.e. partial first
1172 	 * and/or last) on an individual basis (a single pass) and examine
1173 	 * the actual bits to determine if they are free.  a single pass
1174 	 * will be used for all dmap words fully contained within the
1175 	 * specified range.  within this pass, the leaves of the dmap
1176 	 * tree will be examined to determine if the blocks are free. a
1177 	 * single leaf may describe the free space of multiple dmap
1178 	 * words, so we may visit only a subset of the actual leaves
1179 	 * corresponding to the dmap words of the block range.
1180 	 */
1181 	for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) {
1182 		/* determine the bit number within the word and
1183 		 * the number of bits within the word.
1184 		 */
1185 		wbitno = dbitno & (DBWORD - 1);
1186 		nb = min(rembits, DBWORD - wbitno);
1187 
1188 		/* check if only part of the word is to be examined.
1189 		 */
1190 		if (nb < DBWORD) {
1191 			/* check if the bits are free.
1192 			 */
1193 			mask = (ONES << (DBWORD - nb) >> wbitno);
1194 			if ((mask & ~le32_to_cpu(dp->wmap[word])) != mask)
1195 				return -ENOSPC;
1196 
1197 			word += 1;
1198 		} else {
1199 			/* one or more dmap words are fully contained
1200 			 * within the block range.  determine how many
1201 			 * words and how many bits.
1202 			 */
1203 			nwords = rembits >> L2DBWORD;
1204 			nb = nwords << L2DBWORD;
1205 
1206 			/* now examine the appropriate leaves to determine
1207 			 * if the blocks are free.
1208 			 */
1209 			while (nwords > 0) {
1210 				/* does the leaf describe any free space ?
1211 				 */
1212 				if (leaf[word] < BUDMIN)
1213 					return -ENOSPC;
1214 
1215 				/* determine the l2 number of bits provided
1216 				 * by this leaf.
1217 				 */
1218 				l2size =
1219 				    min((int)leaf[word], NLSTOL2BSZ(nwords));
1220 
1221 				/* determine how many words were handled.
1222 				 */
1223 				nw = BUDSIZE(l2size, BUDMIN);
1224 
1225 				nwords -= nw;
1226 				word += nw;
1227 			}
1228 		}
1229 	}
1230 
1231 	/* allocate the blocks.
1232 	 */
1233 	return (dbAllocDmap(bmp, dp, blkno, nblocks));
1234 }
1235 
1236 
1237 /*
1238  * NAME:	dbAllocNear()
1239  *
1240  * FUNCTION:    attempt to allocate a number of contiguous free blocks near
1241  *		a specified block (hint) within a dmap.
1242  *
1243  *		starting with the dmap leaf that covers the hint, we'll
1244  *		check the next four contiguous leaves for sufficient free
1245  *		space.  if sufficient free space is found, we'll allocate
1246  *		the desired free space.
1247  *
1248  * PARAMETERS:
1249  *      bmp	-  pointer to bmap descriptor
1250  *      dp	-  pointer to dmap.
1251  *      blkno	-  block number to allocate near.
1252  *      nblocks	-  actual number of contiguous free blocks desired.
1253  *      l2nb	-  log2 number of contiguous free blocks desired.
1254  *      results	-  on successful return, set to the starting block number
1255  *		   of the newly allocated range.
1256  *
1257  * RETURN VALUES:
1258  *      0	- success
1259  *      -ENOSPC	- insufficient disk resources
1260  *      -EIO	- i/o error
1261  *
1262  * serialization: IREAD_LOCK(ipbmap) held on entry/exit;
1263  */
1264 static int
1265 dbAllocNear(struct bmap * bmp,
1266 	    struct dmap * dp, s64 blkno, int nblocks, int l2nb, s64 * results)
1267 {
1268 	int word, lword, rc;
1269 	s8 *leaf;
1270 
1271 	if (dp->tree.leafidx != cpu_to_le32(LEAFIND)) {
1272 		jfs_error(bmp->db_ipbmap->i_sb,
1273 			  "dbAllocNear: Corrupt dmap page");
1274 		return -EIO;
1275 	}
1276 
1277 	leaf = dp->tree.stree + le32_to_cpu(dp->tree.leafidx);
1278 
1279 	/* determine the word within the dmap that holds the hint
1280 	 * (i.e. blkno).  also, determine the last word in the dmap
1281 	 * that we'll include in our examination.
1282 	 */
1283 	word = (blkno & (BPERDMAP - 1)) >> L2DBWORD;
1284 	lword = min(word + 4, LPERDMAP);
1285 
1286 	/* examine the leaves for sufficient free space.
1287 	 */
1288 	for (; word < lword; word++) {
1289 		/* does the leaf describe sufficient free space ?
1290 		 */
1291 		if (leaf[word] < l2nb)
1292 			continue;
1293 
1294 		/* determine the block number within the file system
1295 		 * of the first block described by this dmap word.
1296 		 */
1297 		blkno = le64_to_cpu(dp->start) + (word << L2DBWORD);
1298 
1299 		/* if not all bits of the dmap word are free, get the
1300 		 * starting bit number within the dmap word of the required
1301 		 * string of free bits and adjust the block number with the
1302 		 * value.
1303 		 */
1304 		if (leaf[word] < BUDMIN)
1305 			blkno +=
1306 			    dbFindBits(le32_to_cpu(dp->wmap[word]), l2nb);
1307 
1308 		/* allocate the blocks.
1309 		 */
1310 		if ((rc = dbAllocDmap(bmp, dp, blkno, nblocks)) == 0)
1311 			*results = blkno;
1312 
1313 		return (rc);
1314 	}
1315 
1316 	return -ENOSPC;
1317 }
1318 
1319 
1320 /*
1321  * NAME:	dbAllocAG()
1322  *
1323  * FUNCTION:    attempt to allocate the specified number of contiguous
1324  *		free blocks within the specified allocation group.
1325  *
1326  *		unless the allocation group size is equal to the number
1327  *		of blocks per dmap, the dmap control pages will be used to
1328  *		find the required free space, if available.  we start the
1329  *		search at the highest dmap control page level which
1330  *		distinctly describes the allocation group's free space
1331  *		(i.e. the highest level at which the allocation group's
1332  *		free space is not mixed in with that of any other group).
1333  *		in addition, we start the search within this level at a
1334  *		height of the dmapctl dmtree at which the nodes distinctly
1335  *		describe the allocation group's free space.  at this height,
1336  *		the allocation group's free space may be represented by 1
1337  *		or two sub-trees, depending on the allocation group size.
1338  *		we search the top nodes of these subtrees left to right for
1339  *		sufficient free space.  if sufficient free space is found,
1340  *		the subtree is searched to find the leftmost leaf that
1341  *		has free space.  once we have made it to the leaf, we
1342  *		move the search to the next lower level dmap control page
1343  *		corresponding to this leaf.  we continue down the dmap control
1344  *		pages until we find the dmap that contains or starts the
1345  *		sufficient free space and we allocate at this dmap.
1346  *
1347  *		if the allocation group size is equal to the dmap size,
1348  *		we'll start at the dmap corresponding to the allocation
1349  *		group and attempt the allocation at this level.
1350  *
1351  *		the dmap control page search is also not performed if the
1352  *		allocation group is completely free and we go to the first
1353  *		dmap of the allocation group to do the allocation.  this is
1354  *		done because the allocation group may be part (not the first
1355  *		part) of a larger binary buddy system, causing the dmap
1356  *		control pages to indicate no free space (NOFREE) within
1357  *		the allocation group.
1358  *
1359  * PARAMETERS:
1360  *      bmp	-  pointer to bmap descriptor
1361  *	agno	- allocation group number.
1362  *      nblocks	-  actual number of contiguous free blocks desired.
1363  *      l2nb	-  log2 number of contiguous free blocks desired.
1364  *      results	-  on successful return, set to the starting block number
1365  *		   of the newly allocated range.
1366  *
1367  * RETURN VALUES:
1368  *      0	- success
1369  *      -ENOSPC	- insufficient disk resources
1370  *      -EIO	- i/o error
1371  *
1372  * note: IWRITE_LOCK(ipmap) held on entry/exit;
1373  */
1374 static int
1375 dbAllocAG(struct bmap * bmp, int agno, s64 nblocks, int l2nb, s64 * results)
1376 {
1377 	struct metapage *mp;
1378 	struct dmapctl *dcp;
1379 	int rc, ti, i, k, m, n, agperlev;
1380 	s64 blkno, lblkno;
1381 	int budmin;
1382 
1383 	/* allocation request should not be for more than the
1384 	 * allocation group size.
1385 	 */
1386 	if (l2nb > bmp->db_agl2size) {
1387 		jfs_error(bmp->db_ipbmap->i_sb,
1388 			  "dbAllocAG: allocation request is larger than the "
1389 			  "allocation group size");
1390 		return -EIO;
1391 	}
1392 
1393 	/* determine the starting block number of the allocation
1394 	 * group.
1395 	 */
1396 	blkno = (s64) agno << bmp->db_agl2size;
1397 
1398 	/* check if the allocation group size is the minimum allocation
1399 	 * group size or if the allocation group is completely free. if
1400 	 * the allocation group size is the minimum size of BPERDMAP (i.e.
1401 	 * 1 dmap), there is no need to search the dmap control page (below)
1402 	 * that fully describes the allocation group since the allocation
1403 	 * group is already fully described by a dmap.  in this case, we
1404 	 * just call dbAllocCtl() to search the dmap tree and allocate the
1405 	 * required space if available.
1406 	 *
1407 	 * if the allocation group is completely free, dbAllocCtl() is
1408 	 * also called to allocate the required space.  this is done for
1409 	 * two reasons.  first, it makes no sense searching the dmap control
1410 	 * pages for free space when we know that free space exists.  second,
1411 	 * the dmap control pages may indicate that the allocation group
1412 	 * has no free space if the allocation group is part (not the first
1413 	 * part) of a larger binary buddy system.
1414 	 */
1415 	if (bmp->db_agsize == BPERDMAP
1416 	    || bmp->db_agfree[agno] == bmp->db_agsize) {
1417 		rc = dbAllocCtl(bmp, nblocks, l2nb, blkno, results);
1418 		if ((rc == -ENOSPC) &&
1419 		    (bmp->db_agfree[agno] == bmp->db_agsize)) {
1420 			printk(KERN_ERR "blkno = %Lx, blocks = %Lx\n",
1421 			       (unsigned long long) blkno,
1422 			       (unsigned long long) nblocks);
1423 			jfs_error(bmp->db_ipbmap->i_sb,
1424 				  "dbAllocAG: dbAllocCtl failed in free AG");
1425 		}
1426 		return (rc);
1427 	}
1428 
1429 	/* the buffer for the dmap control page that fully describes the
1430 	 * allocation group.
1431 	 */
1432 	lblkno = BLKTOCTL(blkno, bmp->db_l2nbperpage, bmp->db_aglevel);
1433 	mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
1434 	if (mp == NULL)
1435 		return -EIO;
1436 	dcp = (struct dmapctl *) mp->data;
1437 	budmin = dcp->budmin;
1438 
1439 	if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) {
1440 		jfs_error(bmp->db_ipbmap->i_sb,
1441 			  "dbAllocAG: Corrupt dmapctl page");
1442 		release_metapage(mp);
1443 		return -EIO;
1444 	}
1445 
1446 	/* search the subtree(s) of the dmap control page that describes
1447 	 * the allocation group, looking for sufficient free space.  to begin,
1448 	 * determine how many allocation groups are represented in a dmap
1449 	 * control page at the control page level (i.e. L0, L1, L2) that
1450 	 * fully describes an allocation group. next, determine the starting
1451 	 * tree index of this allocation group within the control page.
1452 	 */
1453 	agperlev =
1454 	    (1 << (L2LPERCTL - (bmp->db_agheigth << 1))) / bmp->db_agwidth;
1455 	ti = bmp->db_agstart + bmp->db_agwidth * (agno & (agperlev - 1));
1456 
1457 	/* dmap control page trees fan-out by 4 and a single allocation
1458 	 * group may be described by 1 or 2 subtrees within the ag level
1459 	 * dmap control page, depending upon the ag size. examine the ag's
1460 	 * subtrees for sufficient free space, starting with the leftmost
1461 	 * subtree.
1462 	 */
1463 	for (i = 0; i < bmp->db_agwidth; i++, ti++) {
1464 		/* is there sufficient free space ?
1465 		 */
1466 		if (l2nb > dcp->stree[ti])
1467 			continue;
1468 
1469 		/* sufficient free space found in a subtree. now search down
1470 		 * the subtree to find the leftmost leaf that describes this
1471 		 * free space.
1472 		 */
1473 		for (k = bmp->db_agheigth; k > 0; k--) {
1474 			for (n = 0, m = (ti << 2) + 1; n < 4; n++) {
1475 				if (l2nb <= dcp->stree[m + n]) {
1476 					ti = m + n;
1477 					break;
1478 				}
1479 			}
1480 			if (n == 4) {
1481 				jfs_error(bmp->db_ipbmap->i_sb,
1482 					  "dbAllocAG: failed descending stree");
1483 				release_metapage(mp);
1484 				return -EIO;
1485 			}
1486 		}
1487 
1488 		/* determine the block number within the file system
1489 		 * that corresponds to this leaf.
1490 		 */
1491 		if (bmp->db_aglevel == 2)
1492 			blkno = 0;
1493 		else if (bmp->db_aglevel == 1)
1494 			blkno &= ~(MAXL1SIZE - 1);
1495 		else		/* bmp->db_aglevel == 0 */
1496 			blkno &= ~(MAXL0SIZE - 1);
1497 
1498 		blkno +=
1499 		    ((s64) (ti - le32_to_cpu(dcp->leafidx))) << budmin;
1500 
1501 		/* release the buffer in preparation for going down
1502 		 * the next level of dmap control pages.
1503 		 */
1504 		release_metapage(mp);
1505 
1506 		/* check if we need to continue to search down the lower
1507 		 * level dmap control pages.  we need to if the number of
1508 		 * blocks required is less than maximum number of blocks
1509 		 * described at the next lower level.
1510 		 */
1511 		if (l2nb < budmin) {
1512 
1513 			/* search the lower level dmap control pages to get
1514 			 * the starting block number of the the dmap that
1515 			 * contains or starts off the free space.
1516 			 */
1517 			if ((rc =
1518 			     dbFindCtl(bmp, l2nb, bmp->db_aglevel - 1,
1519 				       &blkno))) {
1520 				if (rc == -ENOSPC) {
1521 					jfs_error(bmp->db_ipbmap->i_sb,
1522 						  "dbAllocAG: control page "
1523 						  "inconsistent");
1524 					return -EIO;
1525 				}
1526 				return (rc);
1527 			}
1528 		}
1529 
1530 		/* allocate the blocks.
1531 		 */
1532 		rc = dbAllocCtl(bmp, nblocks, l2nb, blkno, results);
1533 		if (rc == -ENOSPC) {
1534 			jfs_error(bmp->db_ipbmap->i_sb,
1535 				  "dbAllocAG: unable to allocate blocks");
1536 			rc = -EIO;
1537 		}
1538 		return (rc);
1539 	}
1540 
1541 	/* no space in the allocation group.  release the buffer and
1542 	 * return -ENOSPC.
1543 	 */
1544 	release_metapage(mp);
1545 
1546 	return -ENOSPC;
1547 }
1548 
1549 
1550 /*
1551  * NAME:	dbAllocAny()
1552  *
1553  * FUNCTION:    attempt to allocate the specified number of contiguous
1554  *		free blocks anywhere in the file system.
1555  *
1556  *		dbAllocAny() attempts to find the sufficient free space by
1557  *		searching down the dmap control pages, starting with the
1558  *		highest level (i.e. L0, L1, L2) control page.  if free space
1559  *		large enough to satisfy the desired free space is found, the
1560  *		desired free space is allocated.
1561  *
1562  * PARAMETERS:
1563  *      bmp	-  pointer to bmap descriptor
1564  *      nblocks	 -  actual number of contiguous free blocks desired.
1565  *      l2nb	 -  log2 number of contiguous free blocks desired.
1566  *      results	-  on successful return, set to the starting block number
1567  *		   of the newly allocated range.
1568  *
1569  * RETURN VALUES:
1570  *      0	- success
1571  *      -ENOSPC	- insufficient disk resources
1572  *      -EIO	- i/o error
1573  *
1574  * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1575  */
1576 static int dbAllocAny(struct bmap * bmp, s64 nblocks, int l2nb, s64 * results)
1577 {
1578 	int rc;
1579 	s64 blkno = 0;
1580 
1581 	/* starting with the top level dmap control page, search
1582 	 * down the dmap control levels for sufficient free space.
1583 	 * if free space is found, dbFindCtl() returns the starting
1584 	 * block number of the dmap that contains or starts off the
1585 	 * range of free space.
1586 	 */
1587 	if ((rc = dbFindCtl(bmp, l2nb, bmp->db_maxlevel, &blkno)))
1588 		return (rc);
1589 
1590 	/* allocate the blocks.
1591 	 */
1592 	rc = dbAllocCtl(bmp, nblocks, l2nb, blkno, results);
1593 	if (rc == -ENOSPC) {
1594 		jfs_error(bmp->db_ipbmap->i_sb,
1595 			  "dbAllocAny: unable to allocate blocks");
1596 		return -EIO;
1597 	}
1598 	return (rc);
1599 }
1600 
1601 
1602 /*
1603  * NAME:	dbFindCtl()
1604  *
1605  * FUNCTION:    starting at a specified dmap control page level and block
1606  *		number, search down the dmap control levels for a range of
1607  *	        contiguous free blocks large enough to satisfy an allocation
1608  *		request for the specified number of free blocks.
1609  *
1610  *		if sufficient contiguous free blocks are found, this routine
1611  *		returns the starting block number within a dmap page that
1612  *		contains or starts a range of contiqious free blocks that
1613  *		is sufficient in size.
1614  *
1615  * PARAMETERS:
1616  *      bmp	-  pointer to bmap descriptor
1617  *      level	-  starting dmap control page level.
1618  *      l2nb	-  log2 number of contiguous free blocks desired.
1619  *      *blkno	-  on entry, starting block number for conducting the search.
1620  *		   on successful return, the first block within a dmap page
1621  *		   that contains or starts a range of contiguous free blocks.
1622  *
1623  * RETURN VALUES:
1624  *      0	- success
1625  *      -ENOSPC	- insufficient disk resources
1626  *      -EIO	- i/o error
1627  *
1628  * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1629  */
1630 static int dbFindCtl(struct bmap * bmp, int l2nb, int level, s64 * blkno)
1631 {
1632 	int rc, leafidx, lev;
1633 	s64 b, lblkno;
1634 	struct dmapctl *dcp;
1635 	int budmin;
1636 	struct metapage *mp;
1637 
1638 	/* starting at the specified dmap control page level and block
1639 	 * number, search down the dmap control levels for the starting
1640 	 * block number of a dmap page that contains or starts off
1641 	 * sufficient free blocks.
1642 	 */
1643 	for (lev = level, b = *blkno; lev >= 0; lev--) {
1644 		/* get the buffer of the dmap control page for the block
1645 		 * number and level (i.e. L0, L1, L2).
1646 		 */
1647 		lblkno = BLKTOCTL(b, bmp->db_l2nbperpage, lev);
1648 		mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
1649 		if (mp == NULL)
1650 			return -EIO;
1651 		dcp = (struct dmapctl *) mp->data;
1652 		budmin = dcp->budmin;
1653 
1654 		if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) {
1655 			jfs_error(bmp->db_ipbmap->i_sb,
1656 				  "dbFindCtl: Corrupt dmapctl page");
1657 			release_metapage(mp);
1658 			return -EIO;
1659 		}
1660 
1661 		/* search the tree within the dmap control page for
1662 		 * sufficent free space.  if sufficient free space is found,
1663 		 * dbFindLeaf() returns the index of the leaf at which
1664 		 * free space was found.
1665 		 */
1666 		rc = dbFindLeaf((dmtree_t *) dcp, l2nb, &leafidx);
1667 
1668 		/* release the buffer.
1669 		 */
1670 		release_metapage(mp);
1671 
1672 		/* space found ?
1673 		 */
1674 		if (rc) {
1675 			if (lev != level) {
1676 				jfs_error(bmp->db_ipbmap->i_sb,
1677 					  "dbFindCtl: dmap inconsistent");
1678 				return -EIO;
1679 			}
1680 			return -ENOSPC;
1681 		}
1682 
1683 		/* adjust the block number to reflect the location within
1684 		 * the dmap control page (i.e. the leaf) at which free
1685 		 * space was found.
1686 		 */
1687 		b += (((s64) leafidx) << budmin);
1688 
1689 		/* we stop the search at this dmap control page level if
1690 		 * the number of blocks required is greater than or equal
1691 		 * to the maximum number of blocks described at the next
1692 		 * (lower) level.
1693 		 */
1694 		if (l2nb >= budmin)
1695 			break;
1696 	}
1697 
1698 	*blkno = b;
1699 	return (0);
1700 }
1701 
1702 
1703 /*
1704  * NAME:	dbAllocCtl()
1705  *
1706  * FUNCTION:    attempt to allocate a specified number of contiguous
1707  *		blocks starting within a specific dmap.
1708  *
1709  *		this routine is called by higher level routines that search
1710  *		the dmap control pages above the actual dmaps for contiguous
1711  *		free space.  the result of successful searches by these
1712  * 		routines are the starting block numbers within dmaps, with
1713  *		the dmaps themselves containing the desired contiguous free
1714  *		space or starting a contiguous free space of desired size
1715  *		that is made up of the blocks of one or more dmaps. these
1716  *		calls should not fail due to insufficent resources.
1717  *
1718  *		this routine is called in some cases where it is not known
1719  *		whether it will fail due to insufficient resources.  more
1720  *		specifically, this occurs when allocating from an allocation
1721  *		group whose size is equal to the number of blocks per dmap.
1722  *		in this case, the dmap control pages are not examined prior
1723  *		to calling this routine (to save pathlength) and the call
1724  *		might fail.
1725  *
1726  *		for a request size that fits within a dmap, this routine relies
1727  *		upon the dmap's dmtree to find the requested contiguous free
1728  *		space.  for request sizes that are larger than a dmap, the
1729  *		requested free space will start at the first block of the
1730  *		first dmap (i.e. blkno).
1731  *
1732  * PARAMETERS:
1733  *      bmp	-  pointer to bmap descriptor
1734  *      nblocks	 -  actual number of contiguous free blocks to allocate.
1735  *      l2nb	 -  log2 number of contiguous free blocks to allocate.
1736  *      blkno	 -  starting block number of the dmap to start the allocation
1737  *		    from.
1738  *      results	-  on successful return, set to the starting block number
1739  *		   of the newly allocated range.
1740  *
1741  * RETURN VALUES:
1742  *      0	- success
1743  *      -ENOSPC	- insufficient disk resources
1744  *      -EIO	- i/o error
1745  *
1746  * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
1747  */
1748 static int
1749 dbAllocCtl(struct bmap * bmp, s64 nblocks, int l2nb, s64 blkno, s64 * results)
1750 {
1751 	int rc, nb;
1752 	s64 b, lblkno, n;
1753 	struct metapage *mp;
1754 	struct dmap *dp;
1755 
1756 	/* check if the allocation request is confined to a single dmap.
1757 	 */
1758 	if (l2nb <= L2BPERDMAP) {
1759 		/* get the buffer for the dmap.
1760 		 */
1761 		lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
1762 		mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
1763 		if (mp == NULL)
1764 			return -EIO;
1765 		dp = (struct dmap *) mp->data;
1766 
1767 		/* try to allocate the blocks.
1768 		 */
1769 		rc = dbAllocDmapLev(bmp, dp, (int) nblocks, l2nb, results);
1770 		if (rc == 0)
1771 			mark_metapage_dirty(mp);
1772 
1773 		release_metapage(mp);
1774 
1775 		return (rc);
1776 	}
1777 
1778 	/* allocation request involving multiple dmaps. it must start on
1779 	 * a dmap boundary.
1780 	 */
1781 	assert((blkno & (BPERDMAP - 1)) == 0);
1782 
1783 	/* allocate the blocks dmap by dmap.
1784 	 */
1785 	for (n = nblocks, b = blkno; n > 0; n -= nb, b += nb) {
1786 		/* get the buffer for the dmap.
1787 		 */
1788 		lblkno = BLKTODMAP(b, bmp->db_l2nbperpage);
1789 		mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
1790 		if (mp == NULL) {
1791 			rc = -EIO;
1792 			goto backout;
1793 		}
1794 		dp = (struct dmap *) mp->data;
1795 
1796 		/* the dmap better be all free.
1797 		 */
1798 		if (dp->tree.stree[ROOT] != L2BPERDMAP) {
1799 			release_metapage(mp);
1800 			jfs_error(bmp->db_ipbmap->i_sb,
1801 				  "dbAllocCtl: the dmap is not all free");
1802 			rc = -EIO;
1803 			goto backout;
1804 		}
1805 
1806 		/* determine how many blocks to allocate from this dmap.
1807 		 */
1808 		nb = min(n, (s64)BPERDMAP);
1809 
1810 		/* allocate the blocks from the dmap.
1811 		 */
1812 		if ((rc = dbAllocDmap(bmp, dp, b, nb))) {
1813 			release_metapage(mp);
1814 			goto backout;
1815 		}
1816 
1817 		/* write the buffer.
1818 		 */
1819 		write_metapage(mp);
1820 	}
1821 
1822 	/* set the results (starting block number) and return.
1823 	 */
1824 	*results = blkno;
1825 	return (0);
1826 
1827 	/* something failed in handling an allocation request involving
1828 	 * multiple dmaps.  we'll try to clean up by backing out any
1829 	 * allocation that has already happened for this request.  if
1830 	 * we fail in backing out the allocation, we'll mark the file
1831 	 * system to indicate that blocks have been leaked.
1832 	 */
1833       backout:
1834 
1835 	/* try to backout the allocations dmap by dmap.
1836 	 */
1837 	for (n = nblocks - n, b = blkno; n > 0;
1838 	     n -= BPERDMAP, b += BPERDMAP) {
1839 		/* get the buffer for this dmap.
1840 		 */
1841 		lblkno = BLKTODMAP(b, bmp->db_l2nbperpage);
1842 		mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
1843 		if (mp == NULL) {
1844 			/* could not back out.  mark the file system
1845 			 * to indicate that we have leaked blocks.
1846 			 */
1847 			jfs_error(bmp->db_ipbmap->i_sb,
1848 				  "dbAllocCtl: I/O Error: Block Leakage.");
1849 			continue;
1850 		}
1851 		dp = (struct dmap *) mp->data;
1852 
1853 		/* free the blocks is this dmap.
1854 		 */
1855 		if (dbFreeDmap(bmp, dp, b, BPERDMAP)) {
1856 			/* could not back out.  mark the file system
1857 			 * to indicate that we have leaked blocks.
1858 			 */
1859 			release_metapage(mp);
1860 			jfs_error(bmp->db_ipbmap->i_sb,
1861 				  "dbAllocCtl: Block Leakage.");
1862 			continue;
1863 		}
1864 
1865 		/* write the buffer.
1866 		 */
1867 		write_metapage(mp);
1868 	}
1869 
1870 	return (rc);
1871 }
1872 
1873 
1874 /*
1875  * NAME:	dbAllocDmapLev()
1876  *
1877  * FUNCTION:    attempt to allocate a specified number of contiguous blocks
1878  *		from a specified dmap.
1879  *
1880  *		this routine checks if the contiguous blocks are available.
1881  *		if so, nblocks of blocks are allocated; otherwise, ENOSPC is
1882  *		returned.
1883  *
1884  * PARAMETERS:
1885  *      mp	-  pointer to bmap descriptor
1886  *      dp	-  pointer to dmap to attempt to allocate blocks from.
1887  *      l2nb	-  log2 number of contiguous block desired.
1888  *      nblocks	-  actual number of contiguous block desired.
1889  *      results	-  on successful return, set to the starting block number
1890  *		   of the newly allocated range.
1891  *
1892  * RETURN VALUES:
1893  *      0	- success
1894  *      -ENOSPC	- insufficient disk resources
1895  *      -EIO	- i/o error
1896  *
1897  * serialization: IREAD_LOCK(ipbmap), e.g., from dbAlloc(), or
1898  *	IWRITE_LOCK(ipbmap), e.g., dbAllocCtl(), held on entry/exit;
1899  */
1900 static int
1901 dbAllocDmapLev(struct bmap * bmp,
1902 	       struct dmap * dp, int nblocks, int l2nb, s64 * results)
1903 {
1904 	s64 blkno;
1905 	int leafidx, rc;
1906 
1907 	/* can't be more than a dmaps worth of blocks */
1908 	assert(l2nb <= L2BPERDMAP);
1909 
1910 	/* search the tree within the dmap page for sufficient
1911 	 * free space.  if sufficient free space is found, dbFindLeaf()
1912 	 * returns the index of the leaf at which free space was found.
1913 	 */
1914 	if (dbFindLeaf((dmtree_t *) & dp->tree, l2nb, &leafidx))
1915 		return -ENOSPC;
1916 
1917 	/* determine the block number within the file system corresponding
1918 	 * to the leaf at which free space was found.
1919 	 */
1920 	blkno = le64_to_cpu(dp->start) + (leafidx << L2DBWORD);
1921 
1922 	/* if not all bits of the dmap word are free, get the starting
1923 	 * bit number within the dmap word of the required string of free
1924 	 * bits and adjust the block number with this value.
1925 	 */
1926 	if (dp->tree.stree[leafidx + LEAFIND] < BUDMIN)
1927 		blkno += dbFindBits(le32_to_cpu(dp->wmap[leafidx]), l2nb);
1928 
1929 	/* allocate the blocks */
1930 	if ((rc = dbAllocDmap(bmp, dp, blkno, nblocks)) == 0)
1931 		*results = blkno;
1932 
1933 	return (rc);
1934 }
1935 
1936 
1937 /*
1938  * NAME:	dbAllocDmap()
1939  *
1940  * FUNCTION:    adjust the disk allocation map to reflect the allocation
1941  *		of a specified block range within a dmap.
1942  *
1943  *		this routine allocates the specified blocks from the dmap
1944  *		through a call to dbAllocBits(). if the allocation of the
1945  *		block range causes the maximum string of free blocks within
1946  *		the dmap to change (i.e. the value of the root of the dmap's
1947  *		dmtree), this routine will cause this change to be reflected
1948  *		up through the appropriate levels of the dmap control pages
1949  *		by a call to dbAdjCtl() for the L0 dmap control page that
1950  *		covers this dmap.
1951  *
1952  * PARAMETERS:
1953  *      bmp	-  pointer to bmap descriptor
1954  *      dp	-  pointer to dmap to allocate the block range from.
1955  *      blkno	-  starting block number of the block to be allocated.
1956  *      nblocks	-  number of blocks to be allocated.
1957  *
1958  * RETURN VALUES:
1959  *      0	- success
1960  *      -EIO	- i/o error
1961  *
1962  * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
1963  */
1964 static int dbAllocDmap(struct bmap * bmp, struct dmap * dp, s64 blkno,
1965 		       int nblocks)
1966 {
1967 	s8 oldroot;
1968 	int rc;
1969 
1970 	/* save the current value of the root (i.e. maximum free string)
1971 	 * of the dmap tree.
1972 	 */
1973 	oldroot = dp->tree.stree[ROOT];
1974 
1975 	/* allocate the specified (blocks) bits */
1976 	dbAllocBits(bmp, dp, blkno, nblocks);
1977 
1978 	/* if the root has not changed, done. */
1979 	if (dp->tree.stree[ROOT] == oldroot)
1980 		return (0);
1981 
1982 	/* root changed. bubble the change up to the dmap control pages.
1983 	 * if the adjustment of the upper level control pages fails,
1984 	 * backout the bit allocation (thus making everything consistent).
1985 	 */
1986 	if ((rc = dbAdjCtl(bmp, blkno, dp->tree.stree[ROOT], 1, 0)))
1987 		dbFreeBits(bmp, dp, blkno, nblocks);
1988 
1989 	return (rc);
1990 }
1991 
1992 
1993 /*
1994  * NAME:	dbFreeDmap()
1995  *
1996  * FUNCTION:    adjust the disk allocation map to reflect the allocation
1997  *		of a specified block range within a dmap.
1998  *
1999  *		this routine frees the specified blocks from the dmap through
2000  *		a call to dbFreeBits(). if the deallocation of the block range
2001  *		causes the maximum string of free blocks within the dmap to
2002  *		change (i.e. the value of the root of the dmap's dmtree), this
2003  *		routine will cause this change to be reflected up through the
2004  *	        appropriate levels of the dmap control pages by a call to
2005  *		dbAdjCtl() for the L0 dmap control page that covers this dmap.
2006  *
2007  * PARAMETERS:
2008  *      bmp	-  pointer to bmap descriptor
2009  *      dp	-  pointer to dmap to free the block range from.
2010  *      blkno	-  starting block number of the block to be freed.
2011  *      nblocks	-  number of blocks to be freed.
2012  *
2013  * RETURN VALUES:
2014  *      0	- success
2015  *      -EIO	- i/o error
2016  *
2017  * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2018  */
2019 static int dbFreeDmap(struct bmap * bmp, struct dmap * dp, s64 blkno,
2020 		      int nblocks)
2021 {
2022 	s8 oldroot;
2023 	int rc = 0, word;
2024 
2025 	/* save the current value of the root (i.e. maximum free string)
2026 	 * of the dmap tree.
2027 	 */
2028 	oldroot = dp->tree.stree[ROOT];
2029 
2030 	/* free the specified (blocks) bits */
2031 	rc = dbFreeBits(bmp, dp, blkno, nblocks);
2032 
2033 	/* if error or the root has not changed, done. */
2034 	if (rc || (dp->tree.stree[ROOT] == oldroot))
2035 		return (rc);
2036 
2037 	/* root changed. bubble the change up to the dmap control pages.
2038 	 * if the adjustment of the upper level control pages fails,
2039 	 * backout the deallocation.
2040 	 */
2041 	if ((rc = dbAdjCtl(bmp, blkno, dp->tree.stree[ROOT], 0, 0))) {
2042 		word = (blkno & (BPERDMAP - 1)) >> L2DBWORD;
2043 
2044 		/* as part of backing out the deallocation, we will have
2045 		 * to back split the dmap tree if the deallocation caused
2046 		 * the freed blocks to become part of a larger binary buddy
2047 		 * system.
2048 		 */
2049 		if (dp->tree.stree[word] == NOFREE)
2050 			dbBackSplit((dmtree_t *) & dp->tree, word);
2051 
2052 		dbAllocBits(bmp, dp, blkno, nblocks);
2053 	}
2054 
2055 	return (rc);
2056 }
2057 
2058 
2059 /*
2060  * NAME:	dbAllocBits()
2061  *
2062  * FUNCTION:    allocate a specified block range from a dmap.
2063  *
2064  *		this routine updates the dmap to reflect the working
2065  *		state allocation of the specified block range. it directly
2066  *		updates the bits of the working map and causes the adjustment
2067  *		of the binary buddy system described by the dmap's dmtree
2068  *		leaves to reflect the bits allocated.  it also causes the
2069  *		dmap's dmtree, as a whole, to reflect the allocated range.
2070  *
2071  * PARAMETERS:
2072  *      bmp	-  pointer to bmap descriptor
2073  *      dp	-  pointer to dmap to allocate bits from.
2074  *      blkno	-  starting block number of the bits to be allocated.
2075  *      nblocks	-  number of bits to be allocated.
2076  *
2077  * RETURN VALUES: none
2078  *
2079  * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2080  */
2081 static void dbAllocBits(struct bmap * bmp, struct dmap * dp, s64 blkno,
2082 			int nblocks)
2083 {
2084 	int dbitno, word, rembits, nb, nwords, wbitno, nw, agno;
2085 	dmtree_t *tp = (dmtree_t *) & dp->tree;
2086 	int size;
2087 	s8 *leaf;
2088 
2089 	/* pick up a pointer to the leaves of the dmap tree */
2090 	leaf = dp->tree.stree + LEAFIND;
2091 
2092 	/* determine the bit number and word within the dmap of the
2093 	 * starting block.
2094 	 */
2095 	dbitno = blkno & (BPERDMAP - 1);
2096 	word = dbitno >> L2DBWORD;
2097 
2098 	/* block range better be within the dmap */
2099 	assert(dbitno + nblocks <= BPERDMAP);
2100 
2101 	/* allocate the bits of the dmap's words corresponding to the block
2102 	 * range. not all bits of the first and last words may be contained
2103 	 * within the block range.  if this is the case, we'll work against
2104 	 * those words (i.e. partial first and/or last) on an individual basis
2105 	 * (a single pass), allocating the bits of interest by hand and
2106 	 * updating the leaf corresponding to the dmap word. a single pass
2107 	 * will be used for all dmap words fully contained within the
2108 	 * specified range.  within this pass, the bits of all fully contained
2109 	 * dmap words will be marked as free in a single shot and the leaves
2110 	 * will be updated. a single leaf may describe the free space of
2111 	 * multiple dmap words, so we may update only a subset of the actual
2112 	 * leaves corresponding to the dmap words of the block range.
2113 	 */
2114 	for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) {
2115 		/* determine the bit number within the word and
2116 		 * the number of bits within the word.
2117 		 */
2118 		wbitno = dbitno & (DBWORD - 1);
2119 		nb = min(rembits, DBWORD - wbitno);
2120 
2121 		/* check if only part of a word is to be allocated.
2122 		 */
2123 		if (nb < DBWORD) {
2124 			/* allocate (set to 1) the appropriate bits within
2125 			 * this dmap word.
2126 			 */
2127 			dp->wmap[word] |= cpu_to_le32(ONES << (DBWORD - nb)
2128 						      >> wbitno);
2129 
2130 			/* update the leaf for this dmap word. in addition
2131 			 * to setting the leaf value to the binary buddy max
2132 			 * of the updated dmap word, dbSplit() will split
2133 			 * the binary system of the leaves if need be.
2134 			 */
2135 			dbSplit(tp, word, BUDMIN,
2136 				dbMaxBud((u8 *) & dp->wmap[word]));
2137 
2138 			word += 1;
2139 		} else {
2140 			/* one or more dmap words are fully contained
2141 			 * within the block range.  determine how many
2142 			 * words and allocate (set to 1) the bits of these
2143 			 * words.
2144 			 */
2145 			nwords = rembits >> L2DBWORD;
2146 			memset(&dp->wmap[word], (int) ONES, nwords * 4);
2147 
2148 			/* determine how many bits.
2149 			 */
2150 			nb = nwords << L2DBWORD;
2151 
2152 			/* now update the appropriate leaves to reflect
2153 			 * the allocated words.
2154 			 */
2155 			for (; nwords > 0; nwords -= nw) {
2156 			        if (leaf[word] < BUDMIN) {
2157 					jfs_error(bmp->db_ipbmap->i_sb,
2158 						  "dbAllocBits: leaf page "
2159 						  "corrupt");
2160 					break;
2161 				}
2162 
2163 				/* determine what the leaf value should be
2164 				 * updated to as the minimum of the l2 number
2165 				 * of bits being allocated and the l2 number
2166 				 * of bits currently described by this leaf.
2167 				 */
2168 				size = min((int)leaf[word], NLSTOL2BSZ(nwords));
2169 
2170 				/* update the leaf to reflect the allocation.
2171 				 * in addition to setting the leaf value to
2172 				 * NOFREE, dbSplit() will split the binary
2173 				 * system of the leaves to reflect the current
2174 				 * allocation (size).
2175 				 */
2176 				dbSplit(tp, word, size, NOFREE);
2177 
2178 				/* get the number of dmap words handled */
2179 				nw = BUDSIZE(size, BUDMIN);
2180 				word += nw;
2181 			}
2182 		}
2183 	}
2184 
2185 	/* update the free count for this dmap */
2186 	dp->nfree = cpu_to_le32(le32_to_cpu(dp->nfree) - nblocks);
2187 
2188 	BMAP_LOCK(bmp);
2189 
2190 	/* if this allocation group is completely free,
2191 	 * update the maximum allocation group number if this allocation
2192 	 * group is the new max.
2193 	 */
2194 	agno = blkno >> bmp->db_agl2size;
2195 	if (agno > bmp->db_maxag)
2196 		bmp->db_maxag = agno;
2197 
2198 	/* update the free count for the allocation group and map */
2199 	bmp->db_agfree[agno] -= nblocks;
2200 	bmp->db_nfree -= nblocks;
2201 
2202 	BMAP_UNLOCK(bmp);
2203 }
2204 
2205 
2206 /*
2207  * NAME:	dbFreeBits()
2208  *
2209  * FUNCTION:    free a specified block range from a dmap.
2210  *
2211  *		this routine updates the dmap to reflect the working
2212  *		state allocation of the specified block range. it directly
2213  *		updates the bits of the working map and causes the adjustment
2214  *		of the binary buddy system described by the dmap's dmtree
2215  *		leaves to reflect the bits freed.  it also causes the dmap's
2216  *		dmtree, as a whole, to reflect the deallocated range.
2217  *
2218  * PARAMETERS:
2219  *      bmp	-  pointer to bmap descriptor
2220  *      dp	-  pointer to dmap to free bits from.
2221  *      blkno	-  starting block number of the bits to be freed.
2222  *      nblocks	-  number of bits to be freed.
2223  *
2224  * RETURN VALUES: 0 for success
2225  *
2226  * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2227  */
2228 static int dbFreeBits(struct bmap * bmp, struct dmap * dp, s64 blkno,
2229 		       int nblocks)
2230 {
2231 	int dbitno, word, rembits, nb, nwords, wbitno, nw, agno;
2232 	dmtree_t *tp = (dmtree_t *) & dp->tree;
2233 	int rc = 0;
2234 	int size;
2235 
2236 	/* determine the bit number and word within the dmap of the
2237 	 * starting block.
2238 	 */
2239 	dbitno = blkno & (BPERDMAP - 1);
2240 	word = dbitno >> L2DBWORD;
2241 
2242 	/* block range better be within the dmap.
2243 	 */
2244 	assert(dbitno + nblocks <= BPERDMAP);
2245 
2246 	/* free the bits of the dmaps words corresponding to the block range.
2247 	 * not all bits of the first and last words may be contained within
2248 	 * the block range.  if this is the case, we'll work against those
2249 	 * words (i.e. partial first and/or last) on an individual basis
2250 	 * (a single pass), freeing the bits of interest by hand and updating
2251 	 * the leaf corresponding to the dmap word. a single pass will be used
2252 	 * for all dmap words fully contained within the specified range.
2253 	 * within this pass, the bits of all fully contained dmap words will
2254 	 * be marked as free in a single shot and the leaves will be updated. a
2255 	 * single leaf may describe the free space of multiple dmap words,
2256 	 * so we may update only a subset of the actual leaves corresponding
2257 	 * to the dmap words of the block range.
2258 	 *
2259 	 * dbJoin() is used to update leaf values and will join the binary
2260 	 * buddy system of the leaves if the new leaf values indicate this
2261 	 * should be done.
2262 	 */
2263 	for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) {
2264 		/* determine the bit number within the word and
2265 		 * the number of bits within the word.
2266 		 */
2267 		wbitno = dbitno & (DBWORD - 1);
2268 		nb = min(rembits, DBWORD - wbitno);
2269 
2270 		/* check if only part of a word is to be freed.
2271 		 */
2272 		if (nb < DBWORD) {
2273 			/* free (zero) the appropriate bits within this
2274 			 * dmap word.
2275 			 */
2276 			dp->wmap[word] &=
2277 			    cpu_to_le32(~(ONES << (DBWORD - nb)
2278 					  >> wbitno));
2279 
2280 			/* update the leaf for this dmap word.
2281 			 */
2282 			rc = dbJoin(tp, word,
2283 				    dbMaxBud((u8 *) & dp->wmap[word]));
2284 			if (rc)
2285 				return rc;
2286 
2287 			word += 1;
2288 		} else {
2289 			/* one or more dmap words are fully contained
2290 			 * within the block range.  determine how many
2291 			 * words and free (zero) the bits of these words.
2292 			 */
2293 			nwords = rembits >> L2DBWORD;
2294 			memset(&dp->wmap[word], 0, nwords * 4);
2295 
2296 			/* determine how many bits.
2297 			 */
2298 			nb = nwords << L2DBWORD;
2299 
2300 			/* now update the appropriate leaves to reflect
2301 			 * the freed words.
2302 			 */
2303 			for (; nwords > 0; nwords -= nw) {
2304 				/* determine what the leaf value should be
2305 				 * updated to as the minimum of the l2 number
2306 				 * of bits being freed and the l2 (max) number
2307 				 * of bits that can be described by this leaf.
2308 				 */
2309 				size =
2310 				    min(LITOL2BSZ
2311 					(word, L2LPERDMAP, BUDMIN),
2312 					NLSTOL2BSZ(nwords));
2313 
2314 				/* update the leaf.
2315 				 */
2316 				rc = dbJoin(tp, word, size);
2317 				if (rc)
2318 					return rc;
2319 
2320 				/* get the number of dmap words handled.
2321 				 */
2322 				nw = BUDSIZE(size, BUDMIN);
2323 				word += nw;
2324 			}
2325 		}
2326 	}
2327 
2328 	/* update the free count for this dmap.
2329 	 */
2330 	dp->nfree = cpu_to_le32(le32_to_cpu(dp->nfree) + nblocks);
2331 
2332 	BMAP_LOCK(bmp);
2333 
2334 	/* update the free count for the allocation group and
2335 	 * map.
2336 	 */
2337 	agno = blkno >> bmp->db_agl2size;
2338 	bmp->db_nfree += nblocks;
2339 	bmp->db_agfree[agno] += nblocks;
2340 
2341 	/* check if this allocation group is not completely free and
2342 	 * if it is currently the maximum (rightmost) allocation group.
2343 	 * if so, establish the new maximum allocation group number by
2344 	 * searching left for the first allocation group with allocation.
2345 	 */
2346 	if ((bmp->db_agfree[agno] == bmp->db_agsize && agno == bmp->db_maxag) ||
2347 	    (agno == bmp->db_numag - 1 &&
2348 	     bmp->db_agfree[agno] == (bmp-> db_mapsize & (BPERDMAP - 1)))) {
2349 		while (bmp->db_maxag > 0) {
2350 			bmp->db_maxag -= 1;
2351 			if (bmp->db_agfree[bmp->db_maxag] !=
2352 			    bmp->db_agsize)
2353 				break;
2354 		}
2355 
2356 		/* re-establish the allocation group preference if the
2357 		 * current preference is right of the maximum allocation
2358 		 * group.
2359 		 */
2360 		if (bmp->db_agpref > bmp->db_maxag)
2361 			bmp->db_agpref = bmp->db_maxag;
2362 	}
2363 
2364 	BMAP_UNLOCK(bmp);
2365 
2366 	return 0;
2367 }
2368 
2369 
2370 /*
2371  * NAME:	dbAdjCtl()
2372  *
2373  * FUNCTION:	adjust a dmap control page at a specified level to reflect
2374  *		the change in a lower level dmap or dmap control page's
2375  *		maximum string of free blocks (i.e. a change in the root
2376  *		of the lower level object's dmtree) due to the allocation
2377  *		or deallocation of a range of blocks with a single dmap.
2378  *
2379  *		on entry, this routine is provided with the new value of
2380  *		the lower level dmap or dmap control page root and the
2381  *		starting block number of the block range whose allocation
2382  *		or deallocation resulted in the root change.  this range
2383  *		is respresented by a single leaf of the current dmapctl
2384  *		and the leaf will be updated with this value, possibly
2385  *		causing a binary buddy system within the leaves to be
2386  *		split or joined.  the update may also cause the dmapctl's
2387  *		dmtree to be updated.
2388  *
2389  *		if the adjustment of the dmap control page, itself, causes its
2390  *		root to change, this change will be bubbled up to the next dmap
2391  *		control level by a recursive call to this routine, specifying
2392  *		the new root value and the next dmap control page level to
2393  *		be adjusted.
2394  * PARAMETERS:
2395  *      bmp	-  pointer to bmap descriptor
2396  *      blkno	-  the first block of a block range within a dmap.  it is
2397  *		   the allocation or deallocation of this block range that
2398  *		   requires the dmap control page to be adjusted.
2399  *      newval	-  the new value of the lower level dmap or dmap control
2400  *		   page root.
2401  *      alloc	-  TRUE if adjustment is due to an allocation.
2402  *      level	-  current level of dmap control page (i.e. L0, L1, L2) to
2403  *		   be adjusted.
2404  *
2405  * RETURN VALUES:
2406  *      0	- success
2407  *      -EIO	- i/o error
2408  *
2409  * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2410  */
2411 static int
2412 dbAdjCtl(struct bmap * bmp, s64 blkno, int newval, int alloc, int level)
2413 {
2414 	struct metapage *mp;
2415 	s8 oldroot;
2416 	int oldval;
2417 	s64 lblkno;
2418 	struct dmapctl *dcp;
2419 	int rc, leafno, ti;
2420 
2421 	/* get the buffer for the dmap control page for the specified
2422 	 * block number and control page level.
2423 	 */
2424 	lblkno = BLKTOCTL(blkno, bmp->db_l2nbperpage, level);
2425 	mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
2426 	if (mp == NULL)
2427 		return -EIO;
2428 	dcp = (struct dmapctl *) mp->data;
2429 
2430 	if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) {
2431 		jfs_error(bmp->db_ipbmap->i_sb,
2432 			  "dbAdjCtl: Corrupt dmapctl page");
2433 		release_metapage(mp);
2434 		return -EIO;
2435 	}
2436 
2437 	/* determine the leaf number corresponding to the block and
2438 	 * the index within the dmap control tree.
2439 	 */
2440 	leafno = BLKTOCTLLEAF(blkno, dcp->budmin);
2441 	ti = leafno + le32_to_cpu(dcp->leafidx);
2442 
2443 	/* save the current leaf value and the current root level (i.e.
2444 	 * maximum l2 free string described by this dmapctl).
2445 	 */
2446 	oldval = dcp->stree[ti];
2447 	oldroot = dcp->stree[ROOT];
2448 
2449 	/* check if this is a control page update for an allocation.
2450 	 * if so, update the leaf to reflect the new leaf value using
2451 	 * dbSplit(); otherwise (deallocation), use dbJoin() to udpate
2452 	 * the leaf with the new value.  in addition to updating the
2453 	 * leaf, dbSplit() will also split the binary buddy system of
2454 	 * the leaves, if required, and bubble new values within the
2455 	 * dmapctl tree, if required.  similarly, dbJoin() will join
2456 	 * the binary buddy system of leaves and bubble new values up
2457 	 * the dmapctl tree as required by the new leaf value.
2458 	 */
2459 	if (alloc) {
2460 		/* check if we are in the middle of a binary buddy
2461 		 * system.  this happens when we are performing the
2462 		 * first allocation out of an allocation group that
2463 		 * is part (not the first part) of a larger binary
2464 		 * buddy system.  if we are in the middle, back split
2465 		 * the system prior to calling dbSplit() which assumes
2466 		 * that it is at the front of a binary buddy system.
2467 		 */
2468 		if (oldval == NOFREE) {
2469 			rc = dbBackSplit((dmtree_t *) dcp, leafno);
2470 			if (rc)
2471 				return rc;
2472 			oldval = dcp->stree[ti];
2473 		}
2474 		dbSplit((dmtree_t *) dcp, leafno, dcp->budmin, newval);
2475 	} else {
2476 		rc = dbJoin((dmtree_t *) dcp, leafno, newval);
2477 		if (rc)
2478 			return rc;
2479 	}
2480 
2481 	/* check if the root of the current dmap control page changed due
2482 	 * to the update and if the current dmap control page is not at
2483 	 * the current top level (i.e. L0, L1, L2) of the map.  if so (i.e.
2484 	 * root changed and this is not the top level), call this routine
2485 	 * again (recursion) for the next higher level of the mapping to
2486 	 * reflect the change in root for the current dmap control page.
2487 	 */
2488 	if (dcp->stree[ROOT] != oldroot) {
2489 		/* are we below the top level of the map.  if so,
2490 		 * bubble the root up to the next higher level.
2491 		 */
2492 		if (level < bmp->db_maxlevel) {
2493 			/* bubble up the new root of this dmap control page to
2494 			 * the next level.
2495 			 */
2496 			if ((rc =
2497 			     dbAdjCtl(bmp, blkno, dcp->stree[ROOT], alloc,
2498 				      level + 1))) {
2499 				/* something went wrong in bubbling up the new
2500 				 * root value, so backout the changes to the
2501 				 * current dmap control page.
2502 				 */
2503 				if (alloc) {
2504 					dbJoin((dmtree_t *) dcp, leafno,
2505 					       oldval);
2506 				} else {
2507 					/* the dbJoin() above might have
2508 					 * caused a larger binary buddy system
2509 					 * to form and we may now be in the
2510 					 * middle of it.  if this is the case,
2511 					 * back split the buddies.
2512 					 */
2513 					if (dcp->stree[ti] == NOFREE)
2514 						dbBackSplit((dmtree_t *)
2515 							    dcp, leafno);
2516 					dbSplit((dmtree_t *) dcp, leafno,
2517 						dcp->budmin, oldval);
2518 				}
2519 
2520 				/* release the buffer and return the error.
2521 				 */
2522 				release_metapage(mp);
2523 				return (rc);
2524 			}
2525 		} else {
2526 			/* we're at the top level of the map. update
2527 			 * the bmap control page to reflect the size
2528 			 * of the maximum free buddy system.
2529 			 */
2530 			assert(level == bmp->db_maxlevel);
2531 			if (bmp->db_maxfreebud != oldroot) {
2532 				jfs_error(bmp->db_ipbmap->i_sb,
2533 					  "dbAdjCtl: the maximum free buddy is "
2534 					  "not the old root");
2535 			}
2536 			bmp->db_maxfreebud = dcp->stree[ROOT];
2537 		}
2538 	}
2539 
2540 	/* write the buffer.
2541 	 */
2542 	write_metapage(mp);
2543 
2544 	return (0);
2545 }
2546 
2547 
2548 /*
2549  * NAME:	dbSplit()
2550  *
2551  * FUNCTION:    update the leaf of a dmtree with a new value, splitting
2552  *		the leaf from the binary buddy system of the dmtree's
2553  *		leaves, as required.
2554  *
2555  * PARAMETERS:
2556  *      tp	- pointer to the tree containing the leaf.
2557  *      leafno	- the number of the leaf to be updated.
2558  *      splitsz	- the size the binary buddy system starting at the leaf
2559  *		  must be split to, specified as the log2 number of blocks.
2560  *      newval	- the new value for the leaf.
2561  *
2562  * RETURN VALUES: none
2563  *
2564  * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2565  */
2566 static void dbSplit(dmtree_t * tp, int leafno, int splitsz, int newval)
2567 {
2568 	int budsz;
2569 	int cursz;
2570 	s8 *leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx);
2571 
2572 	/* check if the leaf needs to be split.
2573 	 */
2574 	if (leaf[leafno] > tp->dmt_budmin) {
2575 		/* the split occurs by cutting the buddy system in half
2576 		 * at the specified leaf until we reach the specified
2577 		 * size.  pick up the starting split size (current size
2578 		 * - 1 in l2) and the corresponding buddy size.
2579 		 */
2580 		cursz = leaf[leafno] - 1;
2581 		budsz = BUDSIZE(cursz, tp->dmt_budmin);
2582 
2583 		/* split until we reach the specified size.
2584 		 */
2585 		while (cursz >= splitsz) {
2586 			/* update the buddy's leaf with its new value.
2587 			 */
2588 			dbAdjTree(tp, leafno ^ budsz, cursz);
2589 
2590 			/* on to the next size and buddy.
2591 			 */
2592 			cursz -= 1;
2593 			budsz >>= 1;
2594 		}
2595 	}
2596 
2597 	/* adjust the dmap tree to reflect the specified leaf's new
2598 	 * value.
2599 	 */
2600 	dbAdjTree(tp, leafno, newval);
2601 }
2602 
2603 
2604 /*
2605  * NAME:	dbBackSplit()
2606  *
2607  * FUNCTION:    back split the binary buddy system of dmtree leaves
2608  *		that hold a specified leaf until the specified leaf
2609  *		starts its own binary buddy system.
2610  *
2611  *		the allocators typically perform allocations at the start
2612  *		of binary buddy systems and dbSplit() is used to accomplish
2613  *		any required splits.  in some cases, however, allocation
2614  *		may occur in the middle of a binary system and requires a
2615  *		back split, with the split proceeding out from the middle of
2616  *		the system (less efficient) rather than the start of the
2617  *		system (more efficient).  the cases in which a back split
2618  *		is required are rare and are limited to the first allocation
2619  *		within an allocation group which is a part (not first part)
2620  *		of a larger binary buddy system and a few exception cases
2621  *		in which a previous join operation must be backed out.
2622  *
2623  * PARAMETERS:
2624  *      tp	- pointer to the tree containing the leaf.
2625  *      leafno	- the number of the leaf to be updated.
2626  *
2627  * RETURN VALUES: none
2628  *
2629  * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
2630  */
2631 static int dbBackSplit(dmtree_t * tp, int leafno)
2632 {
2633 	int budsz, bud, w, bsz, size;
2634 	int cursz;
2635 	s8 *leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx);
2636 
2637 	/* leaf should be part (not first part) of a binary
2638 	 * buddy system.
2639 	 */
2640 	assert(leaf[leafno] == NOFREE);
2641 
2642 	/* the back split is accomplished by iteratively finding the leaf
2643 	 * that starts the buddy system that contains the specified leaf and
2644 	 * splitting that system in two.  this iteration continues until
2645 	 * the specified leaf becomes the start of a buddy system.
2646 	 *
2647 	 * determine maximum possible l2 size for the specified leaf.
2648 	 */
2649 	size =
2650 	    LITOL2BSZ(leafno, le32_to_cpu(tp->dmt_l2nleafs),
2651 		      tp->dmt_budmin);
2652 
2653 	/* determine the number of leaves covered by this size.  this
2654 	 * is the buddy size that we will start with as we search for
2655 	 * the buddy system that contains the specified leaf.
2656 	 */
2657 	budsz = BUDSIZE(size, tp->dmt_budmin);
2658 
2659 	/* back split.
2660 	 */
2661 	while (leaf[leafno] == NOFREE) {
2662 		/* find the leftmost buddy leaf.
2663 		 */
2664 		for (w = leafno, bsz = budsz;; bsz <<= 1,
2665 		     w = (w < bud) ? w : bud) {
2666 			if (bsz >= le32_to_cpu(tp->dmt_nleafs)) {
2667 				jfs_err("JFS: block map error in dbBackSplit");
2668 				return -EIO;
2669 			}
2670 
2671 			/* determine the buddy.
2672 			 */
2673 			bud = w ^ bsz;
2674 
2675 			/* check if this buddy is the start of the system.
2676 			 */
2677 			if (leaf[bud] != NOFREE) {
2678 				/* split the leaf at the start of the
2679 				 * system in two.
2680 				 */
2681 				cursz = leaf[bud] - 1;
2682 				dbSplit(tp, bud, cursz, cursz);
2683 				break;
2684 			}
2685 		}
2686 	}
2687 
2688 	if (leaf[leafno] != size) {
2689 		jfs_err("JFS: wrong leaf value in dbBackSplit");
2690 		return -EIO;
2691 	}
2692 	return 0;
2693 }
2694 
2695 
2696 /*
2697  * NAME:	dbJoin()
2698  *
2699  * FUNCTION:    update the leaf of a dmtree with a new value, joining
2700  *		the leaf with other leaves of the dmtree into a multi-leaf
2701  *		binary buddy system, as required.
2702  *
2703  * PARAMETERS:
2704  *      tp	- pointer to the tree containing the leaf.
2705  *      leafno	- the number of the leaf to be updated.
2706  *      newval	- the new value for the leaf.
2707  *
2708  * RETURN VALUES: none
2709  */
2710 static int dbJoin(dmtree_t * tp, int leafno, int newval)
2711 {
2712 	int budsz, buddy;
2713 	s8 *leaf;
2714 
2715 	/* can the new leaf value require a join with other leaves ?
2716 	 */
2717 	if (newval >= tp->dmt_budmin) {
2718 		/* pickup a pointer to the leaves of the tree.
2719 		 */
2720 		leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx);
2721 
2722 		/* try to join the specified leaf into a large binary
2723 		 * buddy system.  the join proceeds by attempting to join
2724 		 * the specified leafno with its buddy (leaf) at new value.
2725 		 * if the join occurs, we attempt to join the left leaf
2726 		 * of the joined buddies with its buddy at new value + 1.
2727 		 * we continue to join until we find a buddy that cannot be
2728 		 * joined (does not have a value equal to the size of the
2729 		 * last join) or until all leaves have been joined into a
2730 		 * single system.
2731 		 *
2732 		 * get the buddy size (number of words covered) of
2733 		 * the new value.
2734 		 */
2735 		budsz = BUDSIZE(newval, tp->dmt_budmin);
2736 
2737 		/* try to join.
2738 		 */
2739 		while (budsz < le32_to_cpu(tp->dmt_nleafs)) {
2740 			/* get the buddy leaf.
2741 			 */
2742 			buddy = leafno ^ budsz;
2743 
2744 			/* if the leaf's new value is greater than its
2745 			 * buddy's value, we join no more.
2746 			 */
2747 			if (newval > leaf[buddy])
2748 				break;
2749 
2750 			/* It shouldn't be less */
2751 			if (newval < leaf[buddy])
2752 				return -EIO;
2753 
2754 			/* check which (leafno or buddy) is the left buddy.
2755 			 * the left buddy gets to claim the blocks resulting
2756 			 * from the join while the right gets to claim none.
2757 			 * the left buddy is also eligable to participate in
2758 			 * a join at the next higher level while the right
2759 			 * is not.
2760 			 *
2761 			 */
2762 			if (leafno < buddy) {
2763 				/* leafno is the left buddy.
2764 				 */
2765 				dbAdjTree(tp, buddy, NOFREE);
2766 			} else {
2767 				/* buddy is the left buddy and becomes
2768 				 * leafno.
2769 				 */
2770 				dbAdjTree(tp, leafno, NOFREE);
2771 				leafno = buddy;
2772 			}
2773 
2774 			/* on to try the next join.
2775 			 */
2776 			newval += 1;
2777 			budsz <<= 1;
2778 		}
2779 	}
2780 
2781 	/* update the leaf value.
2782 	 */
2783 	dbAdjTree(tp, leafno, newval);
2784 
2785 	return 0;
2786 }
2787 
2788 
2789 /*
2790  * NAME:	dbAdjTree()
2791  *
2792  * FUNCTION:    update a leaf of a dmtree with a new value, adjusting
2793  *		the dmtree, as required, to reflect the new leaf value.
2794  *		the combination of any buddies must already be done before
2795  *		this is called.
2796  *
2797  * PARAMETERS:
2798  *      tp	- pointer to the tree to be adjusted.
2799  *      leafno	- the number of the leaf to be updated.
2800  *      newval	- the new value for the leaf.
2801  *
2802  * RETURN VALUES: none
2803  */
2804 static void dbAdjTree(dmtree_t * tp, int leafno, int newval)
2805 {
2806 	int lp, pp, k;
2807 	int max;
2808 
2809 	/* pick up the index of the leaf for this leafno.
2810 	 */
2811 	lp = leafno + le32_to_cpu(tp->dmt_leafidx);
2812 
2813 	/* is the current value the same as the old value ?  if so,
2814 	 * there is nothing to do.
2815 	 */
2816 	if (tp->dmt_stree[lp] == newval)
2817 		return;
2818 
2819 	/* set the new value.
2820 	 */
2821 	tp->dmt_stree[lp] = newval;
2822 
2823 	/* bubble the new value up the tree as required.
2824 	 */
2825 	for (k = 0; k < le32_to_cpu(tp->dmt_height); k++) {
2826 		/* get the index of the first leaf of the 4 leaf
2827 		 * group containing the specified leaf (leafno).
2828 		 */
2829 		lp = ((lp - 1) & ~0x03) + 1;
2830 
2831 		/* get the index of the parent of this 4 leaf group.
2832 		 */
2833 		pp = (lp - 1) >> 2;
2834 
2835 		/* determine the maximum of the 4 leaves.
2836 		 */
2837 		max = TREEMAX(&tp->dmt_stree[lp]);
2838 
2839 		/* if the maximum of the 4 is the same as the
2840 		 * parent's value, we're done.
2841 		 */
2842 		if (tp->dmt_stree[pp] == max)
2843 			break;
2844 
2845 		/* parent gets new value.
2846 		 */
2847 		tp->dmt_stree[pp] = max;
2848 
2849 		/* parent becomes leaf for next go-round.
2850 		 */
2851 		lp = pp;
2852 	}
2853 }
2854 
2855 
2856 /*
2857  * NAME:	dbFindLeaf()
2858  *
2859  * FUNCTION:    search a dmtree_t for sufficient free blocks, returning
2860  *		the index of a leaf describing the free blocks if
2861  *		sufficient free blocks are found.
2862  *
2863  *		the search starts at the top of the dmtree_t tree and
2864  *		proceeds down the tree to the leftmost leaf with sufficient
2865  *		free space.
2866  *
2867  * PARAMETERS:
2868  *      tp	- pointer to the tree to be searched.
2869  *      l2nb	- log2 number of free blocks to search for.
2870  *	leafidx	- return pointer to be set to the index of the leaf
2871  *		  describing at least l2nb free blocks if sufficient
2872  *		  free blocks are found.
2873  *
2874  * RETURN VALUES:
2875  *      0	- success
2876  *      -ENOSPC	- insufficient free blocks.
2877  */
2878 static int dbFindLeaf(dmtree_t * tp, int l2nb, int *leafidx)
2879 {
2880 	int ti, n = 0, k, x = 0;
2881 
2882 	/* first check the root of the tree to see if there is
2883 	 * sufficient free space.
2884 	 */
2885 	if (l2nb > tp->dmt_stree[ROOT])
2886 		return -ENOSPC;
2887 
2888 	/* sufficient free space available. now search down the tree
2889 	 * starting at the next level for the leftmost leaf that
2890 	 * describes sufficient free space.
2891 	 */
2892 	for (k = le32_to_cpu(tp->dmt_height), ti = 1;
2893 	     k > 0; k--, ti = ((ti + n) << 2) + 1) {
2894 		/* search the four nodes at this level, starting from
2895 		 * the left.
2896 		 */
2897 		for (x = ti, n = 0; n < 4; n++) {
2898 			/* sufficient free space found.  move to the next
2899 			 * level (or quit if this is the last level).
2900 			 */
2901 			if (l2nb <= tp->dmt_stree[x + n])
2902 				break;
2903 		}
2904 
2905 		/* better have found something since the higher
2906 		 * levels of the tree said it was here.
2907 		 */
2908 		assert(n < 4);
2909 	}
2910 
2911 	/* set the return to the leftmost leaf describing sufficient
2912 	 * free space.
2913 	 */
2914 	*leafidx = x + n - le32_to_cpu(tp->dmt_leafidx);
2915 
2916 	return (0);
2917 }
2918 
2919 
2920 /*
2921  * NAME:	dbFindBits()
2922  *
2923  * FUNCTION:    find a specified number of binary buddy free bits within a
2924  *		dmap bitmap word value.
2925  *
2926  *		this routine searches the bitmap value for (1 << l2nb) free
2927  *		bits at (1 << l2nb) alignments within the value.
2928  *
2929  * PARAMETERS:
2930  *      word	-  dmap bitmap word value.
2931  *      l2nb	-  number of free bits specified as a log2 number.
2932  *
2933  * RETURN VALUES:
2934  *      starting bit number of free bits.
2935  */
2936 static int dbFindBits(u32 word, int l2nb)
2937 {
2938 	int bitno, nb;
2939 	u32 mask;
2940 
2941 	/* get the number of bits.
2942 	 */
2943 	nb = 1 << l2nb;
2944 	assert(nb <= DBWORD);
2945 
2946 	/* complement the word so we can use a mask (i.e. 0s represent
2947 	 * free bits) and compute the mask.
2948 	 */
2949 	word = ~word;
2950 	mask = ONES << (DBWORD - nb);
2951 
2952 	/* scan the word for nb free bits at nb alignments.
2953 	 */
2954 	for (bitno = 0; mask != 0; bitno += nb, mask >>= nb) {
2955 		if ((mask & word) == mask)
2956 			break;
2957 	}
2958 
2959 	ASSERT(bitno < 32);
2960 
2961 	/* return the bit number.
2962 	 */
2963 	return (bitno);
2964 }
2965 
2966 
2967 /*
2968  * NAME:	dbMaxBud(u8 *cp)
2969  *
2970  * FUNCTION:    determine the largest binary buddy string of free
2971  *		bits within 32-bits of the map.
2972  *
2973  * PARAMETERS:
2974  *      cp	-  pointer to the 32-bit value.
2975  *
2976  * RETURN VALUES:
2977  *      largest binary buddy of free bits within a dmap word.
2978  */
2979 static int dbMaxBud(u8 * cp)
2980 {
2981 	signed char tmp1, tmp2;
2982 
2983 	/* check if the wmap word is all free. if so, the
2984 	 * free buddy size is BUDMIN.
2985 	 */
2986 	if (*((uint *) cp) == 0)
2987 		return (BUDMIN);
2988 
2989 	/* check if the wmap word is half free. if so, the
2990 	 * free buddy size is BUDMIN-1.
2991 	 */
2992 	if (*((u16 *) cp) == 0 || *((u16 *) cp + 1) == 0)
2993 		return (BUDMIN - 1);
2994 
2995 	/* not all free or half free. determine the free buddy
2996 	 * size thru table lookup using quarters of the wmap word.
2997 	 */
2998 	tmp1 = max(budtab[cp[2]], budtab[cp[3]]);
2999 	tmp2 = max(budtab[cp[0]], budtab[cp[1]]);
3000 	return (max(tmp1, tmp2));
3001 }
3002 
3003 
3004 /*
3005  * NAME:	cnttz(uint word)
3006  *
3007  * FUNCTION:    determine the number of trailing zeros within a 32-bit
3008  *		value.
3009  *
3010  * PARAMETERS:
3011  *      value	-  32-bit value to be examined.
3012  *
3013  * RETURN VALUES:
3014  *      count of trailing zeros
3015  */
3016 static int cnttz(u32 word)
3017 {
3018 	int n;
3019 
3020 	for (n = 0; n < 32; n++, word >>= 1) {
3021 		if (word & 0x01)
3022 			break;
3023 	}
3024 
3025 	return (n);
3026 }
3027 
3028 
3029 /*
3030  * NAME:	cntlz(u32 value)
3031  *
3032  * FUNCTION:    determine the number of leading zeros within a 32-bit
3033  *		value.
3034  *
3035  * PARAMETERS:
3036  *      value	-  32-bit value to be examined.
3037  *
3038  * RETURN VALUES:
3039  *      count of leading zeros
3040  */
3041 static int cntlz(u32 value)
3042 {
3043 	int n;
3044 
3045 	for (n = 0; n < 32; n++, value <<= 1) {
3046 		if (value & HIGHORDER)
3047 			break;
3048 	}
3049 	return (n);
3050 }
3051 
3052 
3053 /*
3054  * NAME:	blkstol2(s64 nb)
3055  *
3056  * FUNCTION:	convert a block count to its log2 value. if the block
3057  *	        count is not a l2 multiple, it is rounded up to the next
3058  *		larger l2 multiple.
3059  *
3060  * PARAMETERS:
3061  *      nb	-  number of blocks
3062  *
3063  * RETURN VALUES:
3064  *      log2 number of blocks
3065  */
3066 static int blkstol2(s64 nb)
3067 {
3068 	int l2nb;
3069 	s64 mask;		/* meant to be signed */
3070 
3071 	mask = (s64) 1 << (64 - 1);
3072 
3073 	/* count the leading bits.
3074 	 */
3075 	for (l2nb = 0; l2nb < 64; l2nb++, mask >>= 1) {
3076 		/* leading bit found.
3077 		 */
3078 		if (nb & mask) {
3079 			/* determine the l2 value.
3080 			 */
3081 			l2nb = (64 - 1) - l2nb;
3082 
3083 			/* check if we need to round up.
3084 			 */
3085 			if (~mask & nb)
3086 				l2nb++;
3087 
3088 			return (l2nb);
3089 		}
3090 	}
3091 	assert(0);
3092 	return 0;		/* fix compiler warning */
3093 }
3094 
3095 
3096 /*
3097  * NAME:    	dbAllocBottomUp()
3098  *
3099  * FUNCTION:	alloc the specified block range from the working block
3100  *		allocation map.
3101  *
3102  *		the blocks will be alloc from the working map one dmap
3103  *		at a time.
3104  *
3105  * PARAMETERS:
3106  *      ip	-  pointer to in-core inode;
3107  *      blkno	-  starting block number to be freed.
3108  *      nblocks	-  number of blocks to be freed.
3109  *
3110  * RETURN VALUES:
3111  *      0	- success
3112  *      -EIO	- i/o error
3113  */
3114 int dbAllocBottomUp(struct inode *ip, s64 blkno, s64 nblocks)
3115 {
3116 	struct metapage *mp;
3117 	struct dmap *dp;
3118 	int nb, rc;
3119 	s64 lblkno, rem;
3120 	struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap;
3121 	struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap;
3122 
3123 	IREAD_LOCK(ipbmap);
3124 
3125 	/* block to be allocated better be within the mapsize. */
3126 	ASSERT(nblocks <= bmp->db_mapsize - blkno);
3127 
3128 	/*
3129 	 * allocate the blocks a dmap at a time.
3130 	 */
3131 	mp = NULL;
3132 	for (rem = nblocks; rem > 0; rem -= nb, blkno += nb) {
3133 		/* release previous dmap if any */
3134 		if (mp) {
3135 			write_metapage(mp);
3136 		}
3137 
3138 		/* get the buffer for the current dmap. */
3139 		lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
3140 		mp = read_metapage(ipbmap, lblkno, PSIZE, 0);
3141 		if (mp == NULL) {
3142 			IREAD_UNLOCK(ipbmap);
3143 			return -EIO;
3144 		}
3145 		dp = (struct dmap *) mp->data;
3146 
3147 		/* determine the number of blocks to be allocated from
3148 		 * this dmap.
3149 		 */
3150 		nb = min(rem, BPERDMAP - (blkno & (BPERDMAP - 1)));
3151 
3152 		/* allocate the blocks. */
3153 		if ((rc = dbAllocDmapBU(bmp, dp, blkno, nb))) {
3154 			release_metapage(mp);
3155 			IREAD_UNLOCK(ipbmap);
3156 			return (rc);
3157 		}
3158 	}
3159 
3160 	/* write the last buffer. */
3161 	write_metapage(mp);
3162 
3163 	IREAD_UNLOCK(ipbmap);
3164 
3165 	return (0);
3166 }
3167 
3168 
3169 static int dbAllocDmapBU(struct bmap * bmp, struct dmap * dp, s64 blkno,
3170 			 int nblocks)
3171 {
3172 	int rc;
3173 	int dbitno, word, rembits, nb, nwords, wbitno, agno;
3174 	s8 oldroot, *leaf;
3175 	struct dmaptree *tp = (struct dmaptree *) & dp->tree;
3176 
3177 	/* save the current value of the root (i.e. maximum free string)
3178 	 * of the dmap tree.
3179 	 */
3180 	oldroot = tp->stree[ROOT];
3181 
3182 	/* pick up a pointer to the leaves of the dmap tree */
3183 	leaf = tp->stree + LEAFIND;
3184 
3185 	/* determine the bit number and word within the dmap of the
3186 	 * starting block.
3187 	 */
3188 	dbitno = blkno & (BPERDMAP - 1);
3189 	word = dbitno >> L2DBWORD;
3190 
3191 	/* block range better be within the dmap */
3192 	assert(dbitno + nblocks <= BPERDMAP);
3193 
3194 	/* allocate the bits of the dmap's words corresponding to the block
3195 	 * range. not all bits of the first and last words may be contained
3196 	 * within the block range.  if this is the case, we'll work against
3197 	 * those words (i.e. partial first and/or last) on an individual basis
3198 	 * (a single pass), allocating the bits of interest by hand and
3199 	 * updating the leaf corresponding to the dmap word. a single pass
3200 	 * will be used for all dmap words fully contained within the
3201 	 * specified range.  within this pass, the bits of all fully contained
3202 	 * dmap words will be marked as free in a single shot and the leaves
3203 	 * will be updated. a single leaf may describe the free space of
3204 	 * multiple dmap words, so we may update only a subset of the actual
3205 	 * leaves corresponding to the dmap words of the block range.
3206 	 */
3207 	for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) {
3208 		/* determine the bit number within the word and
3209 		 * the number of bits within the word.
3210 		 */
3211 		wbitno = dbitno & (DBWORD - 1);
3212 		nb = min(rembits, DBWORD - wbitno);
3213 
3214 		/* check if only part of a word is to be allocated.
3215 		 */
3216 		if (nb < DBWORD) {
3217 			/* allocate (set to 1) the appropriate bits within
3218 			 * this dmap word.
3219 			 */
3220 			dp->wmap[word] |= cpu_to_le32(ONES << (DBWORD - nb)
3221 						      >> wbitno);
3222 
3223 			word++;
3224 		} else {
3225 			/* one or more dmap words are fully contained
3226 			 * within the block range.  determine how many
3227 			 * words and allocate (set to 1) the bits of these
3228 			 * words.
3229 			 */
3230 			nwords = rembits >> L2DBWORD;
3231 			memset(&dp->wmap[word], (int) ONES, nwords * 4);
3232 
3233 			/* determine how many bits */
3234 			nb = nwords << L2DBWORD;
3235 			word += nwords;
3236 		}
3237 	}
3238 
3239 	/* update the free count for this dmap */
3240 	dp->nfree = cpu_to_le32(le32_to_cpu(dp->nfree) - nblocks);
3241 
3242 	/* reconstruct summary tree */
3243 	dbInitDmapTree(dp);
3244 
3245 	BMAP_LOCK(bmp);
3246 
3247 	/* if this allocation group is completely free,
3248 	 * update the highest active allocation group number
3249 	 * if this allocation group is the new max.
3250 	 */
3251 	agno = blkno >> bmp->db_agl2size;
3252 	if (agno > bmp->db_maxag)
3253 		bmp->db_maxag = agno;
3254 
3255 	/* update the free count for the allocation group and map */
3256 	bmp->db_agfree[agno] -= nblocks;
3257 	bmp->db_nfree -= nblocks;
3258 
3259 	BMAP_UNLOCK(bmp);
3260 
3261 	/* if the root has not changed, done. */
3262 	if (tp->stree[ROOT] == oldroot)
3263 		return (0);
3264 
3265 	/* root changed. bubble the change up to the dmap control pages.
3266 	 * if the adjustment of the upper level control pages fails,
3267 	 * backout the bit allocation (thus making everything consistent).
3268 	 */
3269 	if ((rc = dbAdjCtl(bmp, blkno, tp->stree[ROOT], 1, 0)))
3270 		dbFreeBits(bmp, dp, blkno, nblocks);
3271 
3272 	return (rc);
3273 }
3274 
3275 
3276 /*
3277  * NAME:	dbExtendFS()
3278  *
3279  * FUNCTION:	extend bmap from blkno for nblocks;
3280  * 		dbExtendFS() updates bmap ready for dbAllocBottomUp();
3281  *
3282  * L2
3283  *  |
3284  *   L1---------------------------------L1
3285  *    |                                  |
3286  *     L0---------L0---------L0           L0---------L0---------L0
3287  *      |          |          |            |          |          |
3288  *       d0,...,dn  d0,...,dn  d0,...,dn    d0,...,dn  d0,...,dn  d0,.,dm;
3289  * L2L1L0d0,...,dnL0d0,...,dnL0d0,...,dnL1L0d0,...,dnL0d0,...,dnL0d0,..dm
3290  *
3291  * <---old---><----------------------------extend----------------------->
3292  */
3293 int dbExtendFS(struct inode *ipbmap, s64 blkno,	s64 nblocks)
3294 {
3295 	struct jfs_sb_info *sbi = JFS_SBI(ipbmap->i_sb);
3296 	int nbperpage = sbi->nbperpage;
3297 	int i, i0 = TRUE, j, j0 = TRUE, k, n;
3298 	s64 newsize;
3299 	s64 p;
3300 	struct metapage *mp, *l2mp, *l1mp = NULL, *l0mp = NULL;
3301 	struct dmapctl *l2dcp, *l1dcp, *l0dcp;
3302 	struct dmap *dp;
3303 	s8 *l0leaf, *l1leaf, *l2leaf;
3304 	struct bmap *bmp = sbi->bmap;
3305 	int agno, l2agsize, oldl2agsize;
3306 	s64 ag_rem;
3307 
3308 	newsize = blkno + nblocks;
3309 
3310 	jfs_info("dbExtendFS: blkno:%Ld nblocks:%Ld newsize:%Ld",
3311 		 (long long) blkno, (long long) nblocks, (long long) newsize);
3312 
3313 	/*
3314 	 *      initialize bmap control page.
3315 	 *
3316 	 * all the data in bmap control page should exclude
3317 	 * the mkfs hidden dmap page.
3318 	 */
3319 
3320 	/* update mapsize */
3321 	bmp->db_mapsize = newsize;
3322 	bmp->db_maxlevel = BMAPSZTOLEV(bmp->db_mapsize);
3323 
3324 	/* compute new AG size */
3325 	l2agsize = dbGetL2AGSize(newsize);
3326 	oldl2agsize = bmp->db_agl2size;
3327 
3328 	bmp->db_agl2size = l2agsize;
3329 	bmp->db_agsize = 1 << l2agsize;
3330 
3331 	/* compute new number of AG */
3332 	agno = bmp->db_numag;
3333 	bmp->db_numag = newsize >> l2agsize;
3334 	bmp->db_numag += ((u32) newsize % (u32) bmp->db_agsize) ? 1 : 0;
3335 
3336 	/*
3337 	 *      reconfigure db_agfree[]
3338 	 * from old AG configuration to new AG configuration;
3339 	 *
3340 	 * coalesce contiguous k (newAGSize/oldAGSize) AGs;
3341 	 * i.e., (AGi, ..., AGj) where i = k*n and j = k*(n+1) - 1 to AGn;
3342 	 * note: new AG size = old AG size * (2**x).
3343 	 */
3344 	if (l2agsize == oldl2agsize)
3345 		goto extend;
3346 	k = 1 << (l2agsize - oldl2agsize);
3347 	ag_rem = bmp->db_agfree[0];	/* save agfree[0] */
3348 	for (i = 0, n = 0; i < agno; n++) {
3349 		bmp->db_agfree[n] = 0;	/* init collection point */
3350 
3351 		/* coalesce cotiguous k AGs; */
3352 		for (j = 0; j < k && i < agno; j++, i++) {
3353 			/* merge AGi to AGn */
3354 			bmp->db_agfree[n] += bmp->db_agfree[i];
3355 		}
3356 	}
3357 	bmp->db_agfree[0] += ag_rem;	/* restore agfree[0] */
3358 
3359 	for (; n < MAXAG; n++)
3360 		bmp->db_agfree[n] = 0;
3361 
3362 	/*
3363 	 * update highest active ag number
3364 	 */
3365 
3366 	bmp->db_maxag = bmp->db_maxag / k;
3367 
3368 	/*
3369 	 *      extend bmap
3370 	 *
3371 	 * update bit maps and corresponding level control pages;
3372 	 * global control page db_nfree, db_agfree[agno], db_maxfreebud;
3373 	 */
3374       extend:
3375 	/* get L2 page */
3376 	p = BMAPBLKNO + nbperpage;	/* L2 page */
3377 	l2mp = read_metapage(ipbmap, p, PSIZE, 0);
3378 	if (!l2mp) {
3379 		jfs_error(ipbmap->i_sb, "dbExtendFS: L2 page could not be read");
3380 		return -EIO;
3381 	}
3382 	l2dcp = (struct dmapctl *) l2mp->data;
3383 
3384 	/* compute start L1 */
3385 	k = blkno >> L2MAXL1SIZE;
3386 	l2leaf = l2dcp->stree + CTLLEAFIND + k;
3387 	p = BLKTOL1(blkno, sbi->l2nbperpage);	/* L1 page */
3388 
3389 	/*
3390 	 * extend each L1 in L2
3391 	 */
3392 	for (; k < LPERCTL; k++, p += nbperpage) {
3393 		/* get L1 page */
3394 		if (j0) {
3395 			/* read in L1 page: (blkno & (MAXL1SIZE - 1)) */
3396 			l1mp = read_metapage(ipbmap, p, PSIZE, 0);
3397 			if (l1mp == NULL)
3398 				goto errout;
3399 			l1dcp = (struct dmapctl *) l1mp->data;
3400 
3401 			/* compute start L0 */
3402 			j = (blkno & (MAXL1SIZE - 1)) >> L2MAXL0SIZE;
3403 			l1leaf = l1dcp->stree + CTLLEAFIND + j;
3404 			p = BLKTOL0(blkno, sbi->l2nbperpage);
3405 			j0 = FALSE;
3406 		} else {
3407 			/* assign/init L1 page */
3408 			l1mp = get_metapage(ipbmap, p, PSIZE, 0);
3409 			if (l1mp == NULL)
3410 				goto errout;
3411 
3412 			l1dcp = (struct dmapctl *) l1mp->data;
3413 
3414 			/* compute start L0 */
3415 			j = 0;
3416 			l1leaf = l1dcp->stree + CTLLEAFIND;
3417 			p += nbperpage;	/* 1st L0 of L1.k  */
3418 		}
3419 
3420 		/*
3421 		 * extend each L0 in L1
3422 		 */
3423 		for (; j < LPERCTL; j++) {
3424 			/* get L0 page */
3425 			if (i0) {
3426 				/* read in L0 page: (blkno & (MAXL0SIZE - 1)) */
3427 
3428 				l0mp = read_metapage(ipbmap, p, PSIZE, 0);
3429 				if (l0mp == NULL)
3430 					goto errout;
3431 				l0dcp = (struct dmapctl *) l0mp->data;
3432 
3433 				/* compute start dmap */
3434 				i = (blkno & (MAXL0SIZE - 1)) >>
3435 				    L2BPERDMAP;
3436 				l0leaf = l0dcp->stree + CTLLEAFIND + i;
3437 				p = BLKTODMAP(blkno,
3438 					      sbi->l2nbperpage);
3439 				i0 = FALSE;
3440 			} else {
3441 				/* assign/init L0 page */
3442 				l0mp = get_metapage(ipbmap, p, PSIZE, 0);
3443 				if (l0mp == NULL)
3444 					goto errout;
3445 
3446 				l0dcp = (struct dmapctl *) l0mp->data;
3447 
3448 				/* compute start dmap */
3449 				i = 0;
3450 				l0leaf = l0dcp->stree + CTLLEAFIND;
3451 				p += nbperpage;	/* 1st dmap of L0.j */
3452 			}
3453 
3454 			/*
3455 			 * extend each dmap in L0
3456 			 */
3457 			for (; i < LPERCTL; i++) {
3458 				/*
3459 				 * reconstruct the dmap page, and
3460 				 * initialize corresponding parent L0 leaf
3461 				 */
3462 				if ((n = blkno & (BPERDMAP - 1))) {
3463 					/* read in dmap page: */
3464 					mp = read_metapage(ipbmap, p,
3465 							   PSIZE, 0);
3466 					if (mp == NULL)
3467 						goto errout;
3468 					n = min(nblocks, (s64)BPERDMAP - n);
3469 				} else {
3470 					/* assign/init dmap page */
3471 					mp = read_metapage(ipbmap, p,
3472 							   PSIZE, 0);
3473 					if (mp == NULL)
3474 						goto errout;
3475 
3476 					n = min(nblocks, (s64)BPERDMAP);
3477 				}
3478 
3479 				dp = (struct dmap *) mp->data;
3480 				*l0leaf = dbInitDmap(dp, blkno, n);
3481 
3482 				bmp->db_nfree += n;
3483 				agno = le64_to_cpu(dp->start) >> l2agsize;
3484 				bmp->db_agfree[agno] += n;
3485 
3486 				write_metapage(mp);
3487 
3488 				l0leaf++;
3489 				p += nbperpage;
3490 
3491 				blkno += n;
3492 				nblocks -= n;
3493 				if (nblocks == 0)
3494 					break;
3495 			}	/* for each dmap in a L0 */
3496 
3497 			/*
3498 			 * build current L0 page from its leaves, and
3499 			 * initialize corresponding parent L1 leaf
3500 			 */
3501 			*l1leaf = dbInitDmapCtl(l0dcp, 0, ++i);
3502 			write_metapage(l0mp);
3503 			l0mp = NULL;
3504 
3505 			if (nblocks)
3506 				l1leaf++;	/* continue for next L0 */
3507 			else {
3508 				/* more than 1 L0 ? */
3509 				if (j > 0)
3510 					break;	/* build L1 page */
3511 				else {
3512 					/* summarize in global bmap page */
3513 					bmp->db_maxfreebud = *l1leaf;
3514 					release_metapage(l1mp);
3515 					release_metapage(l2mp);
3516 					goto finalize;
3517 				}
3518 			}
3519 		}		/* for each L0 in a L1 */
3520 
3521 		/*
3522 		 * build current L1 page from its leaves, and
3523 		 * initialize corresponding parent L2 leaf
3524 		 */
3525 		*l2leaf = dbInitDmapCtl(l1dcp, 1, ++j);
3526 		write_metapage(l1mp);
3527 		l1mp = NULL;
3528 
3529 		if (nblocks)
3530 			l2leaf++;	/* continue for next L1 */
3531 		else {
3532 			/* more than 1 L1 ? */
3533 			if (k > 0)
3534 				break;	/* build L2 page */
3535 			else {
3536 				/* summarize in global bmap page */
3537 				bmp->db_maxfreebud = *l2leaf;
3538 				release_metapage(l2mp);
3539 				goto finalize;
3540 			}
3541 		}
3542 	}			/* for each L1 in a L2 */
3543 
3544 	jfs_error(ipbmap->i_sb,
3545 		  "dbExtendFS: function has not returned as expected");
3546 errout:
3547 	if (l0mp)
3548 		release_metapage(l0mp);
3549 	if (l1mp)
3550 		release_metapage(l1mp);
3551 	release_metapage(l2mp);
3552 	return -EIO;
3553 
3554 	/*
3555 	 *      finalize bmap control page
3556 	 */
3557 finalize:
3558 
3559 	return 0;
3560 }
3561 
3562 
3563 /*
3564  *	dbFinalizeBmap()
3565  */
3566 void dbFinalizeBmap(struct inode *ipbmap)
3567 {
3568 	struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap;
3569 	int actags, inactags, l2nl;
3570 	s64 ag_rem, actfree, inactfree, avgfree;
3571 	int i, n;
3572 
3573 	/*
3574 	 *      finalize bmap control page
3575 	 */
3576 //finalize:
3577 	/*
3578 	 * compute db_agpref: preferred ag to allocate from
3579 	 * (the leftmost ag with average free space in it);
3580 	 */
3581 //agpref:
3582 	/* get the number of active ags and inacitve ags */
3583 	actags = bmp->db_maxag + 1;
3584 	inactags = bmp->db_numag - actags;
3585 	ag_rem = bmp->db_mapsize & (bmp->db_agsize - 1);	/* ??? */
3586 
3587 	/* determine how many blocks are in the inactive allocation
3588 	 * groups. in doing this, we must account for the fact that
3589 	 * the rightmost group might be a partial group (i.e. file
3590 	 * system size is not a multiple of the group size).
3591 	 */
3592 	inactfree = (inactags && ag_rem) ?
3593 	    ((inactags - 1) << bmp->db_agl2size) + ag_rem
3594 	    : inactags << bmp->db_agl2size;
3595 
3596 	/* determine how many free blocks are in the active
3597 	 * allocation groups plus the average number of free blocks
3598 	 * within the active ags.
3599 	 */
3600 	actfree = bmp->db_nfree - inactfree;
3601 	avgfree = (u32) actfree / (u32) actags;
3602 
3603 	/* if the preferred allocation group has not average free space.
3604 	 * re-establish the preferred group as the leftmost
3605 	 * group with average free space.
3606 	 */
3607 	if (bmp->db_agfree[bmp->db_agpref] < avgfree) {
3608 		for (bmp->db_agpref = 0; bmp->db_agpref < actags;
3609 		     bmp->db_agpref++) {
3610 			if (bmp->db_agfree[bmp->db_agpref] >= avgfree)
3611 				break;
3612 		}
3613 		if (bmp->db_agpref >= bmp->db_numag) {
3614 			jfs_error(ipbmap->i_sb,
3615 				  "cannot find ag with average freespace");
3616 		}
3617 	}
3618 
3619 	/*
3620 	 * compute db_aglevel, db_agheigth, db_width, db_agstart:
3621 	 * an ag is covered in aglevel dmapctl summary tree,
3622 	 * at agheight level height (from leaf) with agwidth number of nodes
3623 	 * each, which starts at agstart index node of the smmary tree node
3624 	 * array;
3625 	 */
3626 	bmp->db_aglevel = BMAPSZTOLEV(bmp->db_agsize);
3627 	l2nl =
3628 	    bmp->db_agl2size - (L2BPERDMAP + bmp->db_aglevel * L2LPERCTL);
3629 	bmp->db_agheigth = l2nl >> 1;
3630 	bmp->db_agwidth = 1 << (l2nl - (bmp->db_agheigth << 1));
3631 	for (i = 5 - bmp->db_agheigth, bmp->db_agstart = 0, n = 1; i > 0;
3632 	     i--) {
3633 		bmp->db_agstart += n;
3634 		n <<= 2;
3635 	}
3636 
3637 }
3638 
3639 
3640 /*
3641  * NAME:	dbInitDmap()/ujfs_idmap_page()
3642  *
3643  * FUNCTION:	initialize working/persistent bitmap of the dmap page
3644  *		for the specified number of blocks:
3645  *
3646  *		at entry, the bitmaps had been initialized as free (ZEROS);
3647  *		The number of blocks will only account for the actually
3648  *		existing blocks. Blocks which don't actually exist in
3649  *		the aggregate will be marked as allocated (ONES);
3650  *
3651  * PARAMETERS:
3652  *	dp	- pointer to page of map
3653  *	nblocks	- number of blocks this page
3654  *
3655  * RETURNS: NONE
3656  */
3657 static int dbInitDmap(struct dmap * dp, s64 Blkno, int nblocks)
3658 {
3659 	int blkno, w, b, r, nw, nb, i;
3660 
3661 	/* starting block number within the dmap */
3662 	blkno = Blkno & (BPERDMAP - 1);
3663 
3664 	if (blkno == 0) {
3665 		dp->nblocks = dp->nfree = cpu_to_le32(nblocks);
3666 		dp->start = cpu_to_le64(Blkno);
3667 
3668 		if (nblocks == BPERDMAP) {
3669 			memset(&dp->wmap[0], 0, LPERDMAP * 4);
3670 			memset(&dp->pmap[0], 0, LPERDMAP * 4);
3671 			goto initTree;
3672 		}
3673 	} else {
3674 		dp->nblocks =
3675 		    cpu_to_le32(le32_to_cpu(dp->nblocks) + nblocks);
3676 		dp->nfree = cpu_to_le32(le32_to_cpu(dp->nfree) + nblocks);
3677 	}
3678 
3679 	/* word number containing start block number */
3680 	w = blkno >> L2DBWORD;
3681 
3682 	/*
3683 	 * free the bits corresponding to the block range (ZEROS):
3684 	 * note: not all bits of the first and last words may be contained
3685 	 * within the block range.
3686 	 */
3687 	for (r = nblocks; r > 0; r -= nb, blkno += nb) {
3688 		/* number of bits preceding range to be freed in the word */
3689 		b = blkno & (DBWORD - 1);
3690 		/* number of bits to free in the word */
3691 		nb = min(r, DBWORD - b);
3692 
3693 		/* is partial word to be freed ? */
3694 		if (nb < DBWORD) {
3695 			/* free (set to 0) from the bitmap word */
3696 			dp->wmap[w] &= cpu_to_le32(~(ONES << (DBWORD - nb)
3697 						     >> b));
3698 			dp->pmap[w] &= cpu_to_le32(~(ONES << (DBWORD - nb)
3699 						     >> b));
3700 
3701 			/* skip the word freed */
3702 			w++;
3703 		} else {
3704 			/* free (set to 0) contiguous bitmap words */
3705 			nw = r >> L2DBWORD;
3706 			memset(&dp->wmap[w], 0, nw * 4);
3707 			memset(&dp->pmap[w], 0, nw * 4);
3708 
3709 			/* skip the words freed */
3710 			nb = nw << L2DBWORD;
3711 			w += nw;
3712 		}
3713 	}
3714 
3715 	/*
3716 	 * mark bits following the range to be freed (non-existing
3717 	 * blocks) as allocated (ONES)
3718 	 */
3719 
3720 	if (blkno == BPERDMAP)
3721 		goto initTree;
3722 
3723 	/* the first word beyond the end of existing blocks */
3724 	w = blkno >> L2DBWORD;
3725 
3726 	/* does nblocks fall on a 32-bit boundary ? */
3727 	b = blkno & (DBWORD - 1);
3728 	if (b) {
3729 		/* mark a partial word allocated */
3730 		dp->wmap[w] = dp->pmap[w] = cpu_to_le32(ONES >> b);
3731 		w++;
3732 	}
3733 
3734 	/* set the rest of the words in the page to allocated (ONES) */
3735 	for (i = w; i < LPERDMAP; i++)
3736 		dp->pmap[i] = dp->wmap[i] = cpu_to_le32(ONES);
3737 
3738 	/*
3739 	 * init tree
3740 	 */
3741       initTree:
3742 	return (dbInitDmapTree(dp));
3743 }
3744 
3745 
3746 /*
3747  * NAME:	dbInitDmapTree()/ujfs_complete_dmap()
3748  *
3749  * FUNCTION:	initialize summary tree of the specified dmap:
3750  *
3751  *		at entry, bitmap of the dmap has been initialized;
3752  *
3753  * PARAMETERS:
3754  *	dp	- dmap to complete
3755  *	blkno	- starting block number for this dmap
3756  *	treemax	- will be filled in with max free for this dmap
3757  *
3758  * RETURNS:	max free string at the root of the tree
3759  */
3760 static int dbInitDmapTree(struct dmap * dp)
3761 {
3762 	struct dmaptree *tp;
3763 	s8 *cp;
3764 	int i;
3765 
3766 	/* init fixed info of tree */
3767 	tp = &dp->tree;
3768 	tp->nleafs = cpu_to_le32(LPERDMAP);
3769 	tp->l2nleafs = cpu_to_le32(L2LPERDMAP);
3770 	tp->leafidx = cpu_to_le32(LEAFIND);
3771 	tp->height = cpu_to_le32(4);
3772 	tp->budmin = BUDMIN;
3773 
3774 	/* init each leaf from corresponding wmap word:
3775 	 * note: leaf is set to NOFREE(-1) if all blocks of corresponding
3776 	 * bitmap word are allocated.
3777 	 */
3778 	cp = tp->stree + le32_to_cpu(tp->leafidx);
3779 	for (i = 0; i < LPERDMAP; i++)
3780 		*cp++ = dbMaxBud((u8 *) & dp->wmap[i]);
3781 
3782 	/* build the dmap's binary buddy summary tree */
3783 	return (dbInitTree(tp));
3784 }
3785 
3786 
3787 /*
3788  * NAME:	dbInitTree()/ujfs_adjtree()
3789  *
3790  * FUNCTION:	initialize binary buddy summary tree of a dmap or dmapctl.
3791  *
3792  *		at entry, the leaves of the tree has been initialized
3793  *		from corresponding bitmap word or root of summary tree
3794  *		of the child control page;
3795  *		configure binary buddy system at the leaf level, then
3796  *		bubble up the values of the leaf nodes up the tree.
3797  *
3798  * PARAMETERS:
3799  *	cp	- Pointer to the root of the tree
3800  *	l2leaves- Number of leaf nodes as a power of 2
3801  *	l2min	- Number of blocks that can be covered by a leaf
3802  *		  as a power of 2
3803  *
3804  * RETURNS: max free string at the root of the tree
3805  */
3806 static int dbInitTree(struct dmaptree * dtp)
3807 {
3808 	int l2max, l2free, bsize, nextb, i;
3809 	int child, parent, nparent;
3810 	s8 *tp, *cp, *cp1;
3811 
3812 	tp = dtp->stree;
3813 
3814 	/* Determine the maximum free string possible for the leaves */
3815 	l2max = le32_to_cpu(dtp->l2nleafs) + dtp->budmin;
3816 
3817 	/*
3818 	 * configure the leaf levevl into binary buddy system
3819 	 *
3820 	 * Try to combine buddies starting with a buddy size of 1
3821 	 * (i.e. two leaves). At a buddy size of 1 two buddy leaves
3822 	 * can be combined if both buddies have a maximum free of l2min;
3823 	 * the combination will result in the left-most buddy leaf having
3824 	 * a maximum free of l2min+1.
3825 	 * After processing all buddies for a given size, process buddies
3826 	 * at the next higher buddy size (i.e. current size * 2) and
3827 	 * the next maximum free (current free + 1).
3828 	 * This continues until the maximum possible buddy combination
3829 	 * yields maximum free.
3830 	 */
3831 	for (l2free = dtp->budmin, bsize = 1; l2free < l2max;
3832 	     l2free++, bsize = nextb) {
3833 		/* get next buddy size == current buddy pair size */
3834 		nextb = bsize << 1;
3835 
3836 		/* scan each adjacent buddy pair at current buddy size */
3837 		for (i = 0, cp = tp + le32_to_cpu(dtp->leafidx);
3838 		     i < le32_to_cpu(dtp->nleafs);
3839 		     i += nextb, cp += nextb) {
3840 			/* coalesce if both adjacent buddies are max free */
3841 			if (*cp == l2free && *(cp + bsize) == l2free) {
3842 				*cp = l2free + 1;	/* left take right */
3843 				*(cp + bsize) = -1;	/* right give left */
3844 			}
3845 		}
3846 	}
3847 
3848 	/*
3849 	 * bubble summary information of leaves up the tree.
3850 	 *
3851 	 * Starting at the leaf node level, the four nodes described by
3852 	 * the higher level parent node are compared for a maximum free and
3853 	 * this maximum becomes the value of the parent node.
3854 	 * when all lower level nodes are processed in this fashion then
3855 	 * move up to the next level (parent becomes a lower level node) and
3856 	 * continue the process for that level.
3857 	 */
3858 	for (child = le32_to_cpu(dtp->leafidx),
3859 	     nparent = le32_to_cpu(dtp->nleafs) >> 2;
3860 	     nparent > 0; nparent >>= 2, child = parent) {
3861 		/* get index of 1st node of parent level */
3862 		parent = (child - 1) >> 2;
3863 
3864 		/* set the value of the parent node as the maximum
3865 		 * of the four nodes of the current level.
3866 		 */
3867 		for (i = 0, cp = tp + child, cp1 = tp + parent;
3868 		     i < nparent; i++, cp += 4, cp1++)
3869 			*cp1 = TREEMAX(cp);
3870 	}
3871 
3872 	return (*tp);
3873 }
3874 
3875 
3876 /*
3877  *	dbInitDmapCtl()
3878  *
3879  * function: initialize dmapctl page
3880  */
3881 static int dbInitDmapCtl(struct dmapctl * dcp, int level, int i)
3882 {				/* start leaf index not covered by range */
3883 	s8 *cp;
3884 
3885 	dcp->nleafs = cpu_to_le32(LPERCTL);
3886 	dcp->l2nleafs = cpu_to_le32(L2LPERCTL);
3887 	dcp->leafidx = cpu_to_le32(CTLLEAFIND);
3888 	dcp->height = cpu_to_le32(5);
3889 	dcp->budmin = L2BPERDMAP + L2LPERCTL * level;
3890 
3891 	/*
3892 	 * initialize the leaves of current level that were not covered
3893 	 * by the specified input block range (i.e. the leaves have no
3894 	 * low level dmapctl or dmap).
3895 	 */
3896 	cp = &dcp->stree[CTLLEAFIND + i];
3897 	for (; i < LPERCTL; i++)
3898 		*cp++ = NOFREE;
3899 
3900 	/* build the dmap's binary buddy summary tree */
3901 	return (dbInitTree((struct dmaptree *) dcp));
3902 }
3903 
3904 
3905 /*
3906  * NAME:	dbGetL2AGSize()/ujfs_getagl2size()
3907  *
3908  * FUNCTION:	Determine log2(allocation group size) from aggregate size
3909  *
3910  * PARAMETERS:
3911  *	nblocks	- Number of blocks in aggregate
3912  *
3913  * RETURNS: log2(allocation group size) in aggregate blocks
3914  */
3915 static int dbGetL2AGSize(s64 nblocks)
3916 {
3917 	s64 sz;
3918 	s64 m;
3919 	int l2sz;
3920 
3921 	if (nblocks < BPERDMAP * MAXAG)
3922 		return (L2BPERDMAP);
3923 
3924 	/* round up aggregate size to power of 2 */
3925 	m = ((u64) 1 << (64 - 1));
3926 	for (l2sz = 64; l2sz >= 0; l2sz--, m >>= 1) {
3927 		if (m & nblocks)
3928 			break;
3929 	}
3930 
3931 	sz = (s64) 1 << l2sz;
3932 	if (sz < nblocks)
3933 		l2sz += 1;
3934 
3935 	/* agsize = roundupSize/max_number_of_ag */
3936 	return (l2sz - L2MAXAG);
3937 }
3938 
3939 
3940 /*
3941  * NAME:	dbMapFileSizeToMapSize()
3942  *
3943  * FUNCTION:	compute number of blocks the block allocation map file
3944  *		can cover from the map file size;
3945  *
3946  * RETURNS:	Number of blocks which can be covered by this block map file;
3947  */
3948 
3949 /*
3950  * maximum number of map pages at each level including control pages
3951  */
3952 #define MAXL0PAGES	(1 + LPERCTL)
3953 #define MAXL1PAGES	(1 + LPERCTL * MAXL0PAGES)
3954 #define MAXL2PAGES	(1 + LPERCTL * MAXL1PAGES)
3955 
3956 /*
3957  * convert number of map pages to the zero origin top dmapctl level
3958  */
3959 #define BMAPPGTOLEV(npages)	\
3960 	(((npages) <= 3 + MAXL0PAGES) ? 0 \
3961        : ((npages) <= 2 + MAXL1PAGES) ? 1 : 2)
3962 
3963 s64 dbMapFileSizeToMapSize(struct inode * ipbmap)
3964 {
3965 	struct super_block *sb = ipbmap->i_sb;
3966 	s64 nblocks;
3967 	s64 npages, ndmaps;
3968 	int level, i;
3969 	int complete, factor;
3970 
3971 	nblocks = ipbmap->i_size >> JFS_SBI(sb)->l2bsize;
3972 	npages = nblocks >> JFS_SBI(sb)->l2nbperpage;
3973 	level = BMAPPGTOLEV(npages);
3974 
3975 	/* At each level, accumulate the number of dmap pages covered by
3976 	 * the number of full child levels below it;
3977 	 * repeat for the last incomplete child level.
3978 	 */
3979 	ndmaps = 0;
3980 	npages--;		/* skip the first global control page */
3981 	/* skip higher level control pages above top level covered by map */
3982 	npages -= (2 - level);
3983 	npages--;		/* skip top level's control page */
3984 	for (i = level; i >= 0; i--) {
3985 		factor =
3986 		    (i == 2) ? MAXL1PAGES : ((i == 1) ? MAXL0PAGES : 1);
3987 		complete = (u32) npages / factor;
3988 		ndmaps += complete * ((i == 2) ? LPERCTL * LPERCTL
3989 				      : ((i == 1) ? LPERCTL : 1));
3990 
3991 		/* pages in last/incomplete child */
3992 		npages = (u32) npages % factor;
3993 		/* skip incomplete child's level control page */
3994 		npages--;
3995 	}
3996 
3997 	/* convert the number of dmaps into the number of blocks
3998 	 * which can be covered by the dmaps;
3999 	 */
4000 	nblocks = ndmaps << L2BPERDMAP;
4001 
4002 	return (nblocks);
4003 }
4004