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