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