← Back to branch summary

~ubuntu-branches/debian/stretch/jfsutils/stretch

« back to all changes in this revision

Viewing changes to libfs/diskmap.c

  • Committer: Bazaar Package Importer
  • Author(s): Stefan Hornburg (Racke)
  • Date: 2005-01-07 10:12:20 UTC
  • mfrom: (1.2.1 upstream) (2.1.2 hoary)
  • Revision ID: james.westby@ubuntu.com-20050107101220-ka3f7smw42zysmk1
Tags: 1.1.7-1
http://bugs.debian.org/289106
* new upstream release (Closes: #289106)
* start synopsis with lowercase

Show diffs side-by-side

added added

removed removed

Lines of Context:
libfs/diskmap.c
1
 
/* 
2
 
 *  Copyright (c) International Business Machines  Corp., 2000
3
 
 *
4
 
 *  This program is free software;  you can redistribute it and/or modify
5
 
 *  it under the terms of the GNU General Public License as published by
6
 
 *  the Free Software Foundation; either version 2 of the License, or 
7
 
 *  (at your option) any later version.
8
 
 *
9
 
 *  This program is distributed in the hope that it will be useful,
10
 
 *  but WITHOUT ANY WARRANTY;  without even the implied warranty of
11
 
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See
12
 
 *  the GNU General Public License for more details.
13
 
 *
14
 
 *  You should have received a copy of the GNU General Public License
15
 
 *  along with this program;  if not, write to the Free Software 
16
 
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 
1
/*
 
2
 *   Copyright (c) International Business Machines Corp., 2000-2002
 
3
 *
 
4
 *   This program is free software;  you can redistribute it and/or modify
 
5
 *   it under the terms of the GNU General Public License as published by
 
6
 *   the Free Software Foundation; either version 2 of the License, or 
 
7
 *   (at your option) any later version.
 
8
 * 
 
9
 *   This program is distributed in the hope that it will be useful,
 
10
 *   but WITHOUT ANY WARRANTY;  without even the implied warranty of
 
11
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See
 
12
 *   the GNU General Public License for more details.
 
13
 *
 
14
 *   You should have received a copy of the GNU General Public License
 
15
 *   along with this program;  if not, write to the Free Software 
 
16
 *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17
17
 */
18
 
 
19
18
#include "jfs_types.h"
20
19
#include "jfs_dmap.h"
21
20
#include "diskmap.h"
30
29
 *
31
30
 */
32
31
static int8_t budtab[256] = {
33
 
  3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
34
 
  2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
35
 
  2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
36
 
  2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
37
 
  2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
38
 
  2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
39
 
  2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
40
 
  2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
41
 
  2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
42
 
  2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
43
 
  2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
44
 
  2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
45
 
  2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
46
 
  2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
47
 
  2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
48
 
  2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, -1};
49
 
 
 
32
        3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 
33
        2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 
34
        2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 
35
        2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 
36
        2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 
37
        2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
 
38
        2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
 
39
        2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
 
40
        2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 
41
        2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
 
42
        2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
 
43
        2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
 
44
        2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 
45
        2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
 
46
        2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
 
47
        2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, -1
 
48
};
50
49
 
51
50
/*
52
51
 * NAME: ujfs_maxbuddy
67
66
 *
68
67
 * RETURNS: Maximum string of free blocks within word.
69
68
 */
70
 
int8_t ujfs_maxbuddy( unsigned char  *cp )
 
69
int8_t ujfs_maxbuddy(unsigned char *cp)
71
70
{
72
 
  /*
73
 
   * Check if the wmap or pmap word is all free. If so, the free buddy size is
74
 
   * BUDMIN.
75
 
   */
76
 
  if ( *((uint32_t *)cp) == 0 ) {
77
 
    return(BUDMIN);
78
 
  }
79
 
 
80
 
  /*
81
 
   * Check if the wmap or pmap word is half free. If so, the free buddy size
82
 
   * is BUDMIN-1.
83
 
   */
84
 
  if ( *((uint16_t *)cp) == 0 || *((uint16_t *)cp+1) == 0 ) {
85
 
    return(BUDMIN-1);
86
 
  }
87
 
 
88
 
  /*
89
 
   * Not all free or half free. Determine the free buddy size through table
90
 
   * lookup using quarters of the wmap or pmap word.
91
 
   */
92
 
  return( MAX( MAX( budtab[*cp], budtab[*(cp+1)]),
93
 
               MAX( budtab[*(cp+2)], budtab[*(cp+3)] )));     
 
71
        /*
 
72
         * Check if the wmap or pmap word is all free. If so, the free buddy size is
 
73
         * BUDMIN.
 
74
         */
 
75
        if (*((uint32_t *) cp) == 0) {
 
76
                return (BUDMIN);
 
77
        }
 
78
 
 
79
        /*
 
80
         * Check if the wmap or pmap word is half free. If so, the free buddy size
 
81
         * is BUDMIN-1.
 
82
         */
 
83
        if (*((uint16_t *) cp) == 0 || *((uint16_t *) cp + 1) == 0) {
 
84
                return (BUDMIN - 1);
 
85
        }
 
86
 
 
87
        /*
 
88
         * Not all free or half free. Determine the free buddy size through table
 
89
         * lookup using quarters of the wmap or pmap word.
 
90
         */
 
91
        return (MAX(MAX(budtab[*cp], budtab[*(cp + 1)]),
 
92
                    MAX(budtab[*(cp + 2)], budtab[*(cp + 3)])));
94
93
}
95
94
 
96
 
 
97
95
/*
98
96
 * NAME: ujfs_adjtree
99
97
 *                                                                    
117
115
 *
118
116
 * RETURNS:
119
117
 */
120
 
int8_t ujfs_adjtree( int8_t   *treep,
121
 
                     int32_t  l2leaves,
122
 
                     int32_t  l2min    )
 
118
int8_t ujfs_adjtree(int8_t * treep, int32_t l2leaves, int32_t l2min)
123
119
{
124
 
  int32_t  nleaves, leaf_index, l2max, nextb, bsize, index;
125
 
  int32_t  l2free, leaf, num_this_level, nextp;
126
 
  int8_t   *cp0, *cp1, *cp = treep;
127
 
 
128
 
  /*
129
 
   * Determine the number of leaves of the tree and the
130
 
   * index of the first leaf.
131
 
   * Note: I don't know why the leaf_index calculation works, but it does.
132
 
   */
133
 
  nleaves = (1 << l2leaves);
134
 
  leaf_index = (nleaves - 1) / 3;
135
 
 
136
 
  /*
137
 
   * Determine the maximum free string possible for the leaves.
138
 
   */
139
 
  l2max = l2min + l2leaves;
140
 
 
141
 
  /*
142
 
   * Try to combine buddies starting with a buddy size of 1 (i.e. two leaves).
143
 
   * At a buddy size of 1 two buddy leaves can be combined if both buddies
144
 
   * have a maximum free of l2min; the combination will result in the
145
 
   * left-most buddy leaf having a maximum free of l2min+1.  After processing
146
 
   * all buddies for a certain size, process buddies at the next higher buddy
147
 
   * size (i.e. current size * 2) and the next maximum free
148
 
   * (current free + 1).  This continues until the maximum possible buddy
149
 
   * combination yields maximum free.
150
 
   */
151
 
  for ( l2free = l2min, bsize = 1; l2free < l2max; l2free++, bsize = nextb ) {
152
 
    nextb = bsize << 1;
153
 
 
154
 
    for ( cp0 = cp + leaf_index, index = 0; index < nleaves;
155
 
          index += nextb, cp0 += nextb ) {
156
 
      if ( *cp0 == l2free && *(cp0 + bsize) == l2free ) {
157
 
        *cp0 = l2free + 1;
158
 
        *(cp0 + bsize) = -1;
159
 
      }
160
 
    }
161
 
  }
162
 
 
163
 
  /*
164
 
   * With the leaves reflecting maximum free values bubble this information up
165
 
   * the tree.  Starting at the leaf node level, the four nodes described by
166
 
   * the higher level parent node are compared for a maximum free and this
167
 
   * maximum becomes the value of the parent node.  All lower level nodes are
168
 
   * processed in this fashion then we move up to the next level (parent
169
 
   * becomes a lower level node) and continue the process for that level.
170
 
   */
171
 
  for ( leaf = leaf_index, num_this_level = nleaves >> 2; num_this_level > 0;
172
 
        num_this_level >>= 2, leaf = nextp ) {
173
 
    nextp = (leaf - 1) >> 2;
174
 
 
175
 
    /*
176
 
     * Process all lower level nodes at this level setting the value of the
177
 
     * parent node as the maximum of the four lower level nodes.
178
 
     */
179
 
    for ( cp0 = cp + leaf, cp1 = cp + nextp, index = 0;
180
 
          index < num_this_level; index++, cp0 += 4, cp1++ ) {
181
 
      *cp1 = TREEMAX(cp0);
182
 
    }
183
 
  }
184
 
 
185
 
  return(*cp);
 
120
        int32_t nleaves, leaf_index, l2max, nextb, bsize, index;
 
121
        int32_t l2free, leaf, num_this_level, nextp;
 
122
        int8_t *cp0, *cp1, *cp = treep;
 
123
 
 
124
        /*
 
125
         * Determine the number of leaves of the tree and the
 
126
         * index of the first leaf.
 
127
         * Note: I don't know why the leaf_index calculation works, but it does.
 
128
         */
 
129
        nleaves = (1 << l2leaves);
 
130
        leaf_index = (nleaves - 1) / 3;
 
131
 
 
132
        /*
 
133
         * Determine the maximum free string possible for the leaves.
 
134
         */
 
135
        l2max = l2min + l2leaves;
 
136
 
 
137
        /*
 
138
         * Try to combine buddies starting with a buddy size of 1 (i.e. two leaves).
 
139
         * At a buddy size of 1 two buddy leaves can be combined if both buddies
 
140
         * have a maximum free of l2min; the combination will result in the
 
141
         * left-most buddy leaf having a maximum free of l2min+1.  After processing
 
142
         * all buddies for a certain size, process buddies at the next higher buddy
 
143
         * size (i.e. current size * 2) and the next maximum free
 
144
         * (current free + 1).  This continues until the maximum possible buddy
 
145
         * combination yields maximum free.
 
146
         */
 
147
        for (l2free = l2min, bsize = 1; l2free < l2max; l2free++, bsize = nextb) {
 
148
                nextb = bsize << 1;
 
149
 
 
150
                for (cp0 = cp + leaf_index, index = 0; index < nleaves;
 
151
                     index += nextb, cp0 += nextb) {
 
152
                        if (*cp0 == l2free && *(cp0 + bsize) == l2free) {
 
153
                                *cp0 = l2free + 1;
 
154
                                *(cp0 + bsize) = -1;
 
155
                        }
 
156
                }
 
157
        }
 
158
 
 
159
        /*
 
160
         * With the leaves reflecting maximum free values bubble this information up
 
161
         * the tree.  Starting at the leaf node level, the four nodes described by
 
162
         * the higher level parent node are compared for a maximum free and this
 
163
         * maximum becomes the value of the parent node.  All lower level nodes are
 
164
         * processed in this fashion then we move up to the next level (parent
 
165
         * becomes a lower level node) and continue the process for that level.
 
166
         */
 
167
        for (leaf = leaf_index, num_this_level = nleaves >> 2; num_this_level > 0;
 
168
             num_this_level >>= 2, leaf = nextp) {
 
169
                nextp = (leaf - 1) >> 2;
 
170
 
 
171
                /*
 
172
                 * Process all lower level nodes at this level setting the value of the
 
173
                 * parent node as the maximum of the four lower level nodes.
 
174
                 */
 
175
                for (cp0 = cp + leaf, cp1 = cp + nextp, index = 0;
 
176
                     index < num_this_level; index++, cp0 += 4, cp1++) {
 
177
                        *cp1 = TREEMAX(cp0);
 
178
                }
 
179
        }
 
180
 
 
181
        return (*cp);
186
182
}
187
183
 
188
 
 
189
184
/*
190
185
 * NAME: ujfs_complete_dmap
191
186
 *                                                                    
198
193
 *
199
194
 * RETURNS: NONE
200
195
 */
201
 
void ujfs_complete_dmap( dmap_t   *dmap_page,
202
 
                         int64_t  blkno,
203
 
                         int8_t   *treemax )
 
196
void ujfs_complete_dmap(struct dmap *dmap_page, int64_t blkno, int8_t *treemax)
204
197
{
205
 
  dmaptree_t  *tp;
206
 
  int8_t      *cp;
207
 
  int32_t     index;
208
 
 
209
 
  dmap_page->start = blkno;
210
 
 
211
 
  tp = &dmap_page->tree;
212
 
  tp->height = 4;
213
 
  tp->leafidx = LEAFIND;
214
 
  tp->nleafs = LPERDMAP;
215
 
  tp->l2nleafs = L2LPERDMAP;
216
 
  tp->budmin = BUDMIN;
217
 
 
218
 
  /*
219
 
   * Pick up the pointer to the first leaf of the dmap tree.
220
 
   */
221
 
  cp = tp->stree + tp->leafidx;
222
 
 
223
 
  /*
224
 
   * Set the initial state for the leaves of the dmap tree.  They will reflect
225
 
   * the current allocation state of the wmap words.
226
 
   */
227
 
  for ( index = 0; index < LPERDMAP; index++ ) {
228
 
    *(cp + index) = ujfs_maxbuddy((unsigned char *)&dmap_page->wmap[index]);
229
 
  }
230
 
 
231
 
  /*
232
 
   * With the leaves of the dmap initialized adjust (initialize) the dmap's
233
 
   * tree.
234
 
   */
235
 
  *treemax = ujfs_adjtree( tp->stree, L2LPERDMAP, BUDMIN );
 
198
        struct dmaptree *tp;
 
199
        int8_t *cp;
 
200
        int32_t index;
 
201
 
 
202
        dmap_page->start = blkno;
 
203
 
 
204
        tp = &dmap_page->tree;
 
205
        tp->height = 4;
 
206
        tp->leafidx = LEAFIND;
 
207
        tp->nleafs = LPERDMAP;
 
208
        tp->l2nleafs = L2LPERDMAP;
 
209
        tp->budmin = BUDMIN;
 
210
 
 
211
        /*
 
212
         * Pick up the pointer to the first leaf of the dmap tree.
 
213
         */
 
214
        cp = tp->stree + tp->leafidx;
 
215
 
 
216
        /*
 
217
         * Set the initial state for the leaves of the dmap tree.  They will reflect
 
218
         * the current allocation state of the wmap words.
 
219
         */
 
220
        for (index = 0; index < LPERDMAP; index++) {
 
221
                *(cp + index) = ujfs_maxbuddy((unsigned char *) &dmap_page->wmap[index]);
 
222
        }
 
223
 
 
224
        /*
 
225
         * With the leaves of the dmap initialized adjust (initialize) the dmap's
 
226
         * tree.
 
227
         */
 
228
        *treemax = ujfs_adjtree(tp->stree, L2LPERDMAP, BUDMIN);
236
229
}
237
230
 
238
 
 
239
231
/*
240
232
 * NAME: ujfs_idmap_page
241
233
 *                                                                    
251
243
 *
252
244
 * RETURNS: NONE
253
245
 */
254
 
void ujfs_idmap_page( dmap_t    *map_page,
255
 
                      uint32_t  nblocks )
 
246
void ujfs_idmap_page(struct dmap *map_page, uint32_t nblocks)
256
247
{
257
 
  uint32_t  index, nwords, bit;
258
 
 
259
 
  map_page->nblocks = map_page->nfree = nblocks;
260
 
 
261
 
  /*
262
 
   * Partial dmap page?
263
 
   * If there are not enough blocks to cover an entire dmap page the ones
264
 
   * which represent blocks which don't exist will be marked as allocated.
265
 
   *
266
 
   * nwords will indicate the first word beyond the end of existing blocks
267
 
   * bit will indicate if this block does not fall on a 32-bit boundary
268
 
   */
269
 
  nwords = nblocks/DBWORD;
270
 
  bit = nblocks % DBWORD;
271
 
 
272
 
  if ( bit ) {
273
 
    /*
274
 
     * Need to mark a partial word allocated
275
 
     */
276
 
    map_page->wmap[nwords] = map_page->pmap[nwords] = ONES >> bit;
277
 
    nwords++;
278
 
  }
279
 
 
280
 
  /*
281
 
   * Set the rest of the words in the page to ONES.
282
 
   */
283
 
  for ( index = nwords; index < LPERDMAP; index++ ) {
284
 
    map_page->pmap[index] = map_page->wmap[index] = ONES;
285
 
  }
 
248
        uint32_t index, nwords, bit;
 
249
 
 
250
        map_page->nblocks = map_page->nfree = nblocks;
 
251
 
 
252
        /*
 
253
         * Partial dmap page?
 
254
         * If there are not enough blocks to cover an entire dmap page the ones
 
255
         * which represent blocks which don't exist will be marked as allocated.
 
256
         *
 
257
         * nwords will indicate the first word beyond the end of existing blocks
 
258
         * bit will indicate if this block does not fall on a 32-bit boundary
 
259
         */
 
260
        nwords = nblocks / DBWORD;
 
261
        bit = nblocks % DBWORD;
 
262
 
 
263
        if (bit) {
 
264
                /*
 
265
                 * Need to mark a partial word allocated
 
266
                 */
 
267
                map_page->wmap[nwords] = map_page->pmap[nwords] = ONES >> bit;
 
268
                nwords++;
 
269
        }
 
270
 
 
271
        /*
 
272
         * Set the rest of the words in the page to ONES.
 
273
         */
 
274
        for (index = nwords; index < LPERDMAP; index++) {
 
275
                map_page->pmap[index] = map_page->wmap[index] = ONES;
 
276
        }
286
277
}
287
278
 
288
 
 
289
279
/*
290
280
 * NAME: ujfs_getagl2size
291
281
 *                                                                    
297
287
 *
298
288
 * RETURNS: log2(allocation group size) in aggregate blocks
299
289
 */
300
 
int32_t ujfs_getagl2size( int64_t  size,
301
 
                          int32_t  aggr_block_size )
 
290
int32_t ujfs_getagl2size(int64_t size, int32_t aggr_block_size)
302
291
{
303
 
  int64_t  sz;
304
 
  int64_t  m;
305
 
  int32_t  l2sz;
306
 
 
307
 
  if ( size < BPERDMAP * MAXAG ) {
308
 
    return(L2BPERDMAP);
309
 
  }
310
 
 
311
 
  m = ((uint64_t)1 << (64-1));
312
 
  for ( l2sz = 64; l2sz >= 0; l2sz--, m >>= 1 ) {
313
 
    if ( m & size ) {
314
 
      break;
315
 
    }
316
 
  }
317
 
 
318
 
  sz = (int64_t)1 << l2sz;
319
 
  if ( sz < size ) {
320
 
    l2sz += 1;
321
 
  }
322
 
 
323
 
  return(l2sz - L2MAXAG);
 
292
        int64_t sz;
 
293
        int64_t m;
 
294
        int32_t l2sz;
 
295
 
 
296
        if (size < BPERDMAP * MAXAG) {
 
297
                return (L2BPERDMAP);
 
298
        }
 
299
 
 
300
        m = ((uint64_t) 1 << (64 - 1));
 
301
        for (l2sz = 64; l2sz >= 0; l2sz--, m >>= 1) {
 
302
                if (m & size) {
 
303
                        break;
 
304
                }
 
305
        }
 
306
 
 
307
        sz = (int64_t) 1 << l2sz;
 
308
        if (sz < size) {
 
309
                l2sz += 1;
 
310
        }
 
311
 
 
312
        return (l2sz - L2MAXAG);
324
313
}