OpenCores
URL https://opencores.org/ocsvn/test_project/test_project/trunk

Subversion Repositories test_project

[/] [test_project/] [trunk/] [linux_sd_driver/] [fs/] [affs/] [bitmap.c] - Blame information for rev 62

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 62 marcus.erl
/*
2
 *  linux/fs/affs/bitmap.c
3
 *
4
 *  (c) 1996 Hans-Joachim Widmaier
5
 *
6
 *  bitmap.c contains the code that handles all bitmap related stuff -
7
 *  block allocation, deallocation, calculation of free space.
8
 */
9
 
10
#include "affs.h"
11
 
12
/* This is, of course, shamelessly stolen from fs/minix */
13
 
14
static const int nibblemap[] = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4 };
15
 
16
static u32
17
affs_count_free_bits(u32 blocksize, const void *data)
18
{
19
        const u32 *map;
20
        u32 free;
21
        u32 tmp;
22
 
23
        map = data;
24
        free = 0;
25
        for (blocksize /= 4; blocksize > 0; blocksize--) {
26
                tmp = *map++;
27
                while (tmp) {
28
                        free += nibblemap[tmp & 0xf];
29
                        tmp >>= 4;
30
                }
31
        }
32
 
33
        return free;
34
}
35
 
36
u32
37
affs_count_free_blocks(struct super_block *sb)
38
{
39
        struct affs_bm_info *bm;
40
        u32 free;
41
        int i;
42
 
43
        pr_debug("AFFS: count_free_blocks()\n");
44
 
45
        if (sb->s_flags & MS_RDONLY)
46
                return 0;
47
 
48
        down(&AFFS_SB(sb)->s_bmlock);
49
 
50
        bm = AFFS_SB(sb)->s_bitmap;
51
        free = 0;
52
        for (i = AFFS_SB(sb)->s_bmap_count; i > 0; bm++, i--)
53
                free += bm->bm_free;
54
 
55
        up(&AFFS_SB(sb)->s_bmlock);
56
 
57
        return free;
58
}
59
 
60
void
61
affs_free_block(struct super_block *sb, u32 block)
62
{
63
        struct affs_sb_info *sbi = AFFS_SB(sb);
64
        struct affs_bm_info *bm;
65
        struct buffer_head *bh;
66
        u32 blk, bmap, bit, mask, tmp;
67
        __be32 *data;
68
 
69
        pr_debug("AFFS: free_block(%u)\n", block);
70
 
71
        if (block > sbi->s_partition_size)
72
                goto err_range;
73
 
74
        blk     = block - sbi->s_reserved;
75
        bmap    = blk / sbi->s_bmap_bits;
76
        bit     = blk % sbi->s_bmap_bits;
77
        bm      = &sbi->s_bitmap[bmap];
78
 
79
        down(&sbi->s_bmlock);
80
 
81
        bh = sbi->s_bmap_bh;
82
        if (sbi->s_last_bmap != bmap) {
83
                affs_brelse(bh);
84
                bh = affs_bread(sb, bm->bm_key);
85
                if (!bh)
86
                        goto err_bh_read;
87
                sbi->s_bmap_bh = bh;
88
                sbi->s_last_bmap = bmap;
89
        }
90
 
91
        mask = 1 << (bit & 31);
92
        data = (__be32 *)bh->b_data + bit / 32 + 1;
93
 
94
        /* mark block free */
95
        tmp = be32_to_cpu(*data);
96
        if (tmp & mask)
97
                goto err_free;
98
        *data = cpu_to_be32(tmp | mask);
99
 
100
        /* fix checksum */
101
        tmp = be32_to_cpu(*(__be32 *)bh->b_data);
102
        *(__be32 *)bh->b_data = cpu_to_be32(tmp - mask);
103
 
104
        mark_buffer_dirty(bh);
105
        sb->s_dirt = 1;
106
        bm->bm_free++;
107
 
108
        up(&sbi->s_bmlock);
109
        return;
110
 
111
err_free:
112
        affs_warning(sb,"affs_free_block","Trying to free block %u which is already free", block);
113
        up(&sbi->s_bmlock);
114
        return;
115
 
116
err_bh_read:
117
        affs_error(sb,"affs_free_block","Cannot read bitmap block %u", bm->bm_key);
118
        sbi->s_bmap_bh = NULL;
119
        sbi->s_last_bmap = ~0;
120
        up(&sbi->s_bmlock);
121
        return;
122
 
123
err_range:
124
        affs_error(sb, "affs_free_block","Block %u outside partition", block);
125
        return;
126
}
127
 
128
/*
129
 * Allocate a block in the given allocation zone.
130
 * Since we have to byte-swap the bitmap on little-endian
131
 * machines, this is rather expensive. Therefor we will
132
 * preallocate up to 16 blocks from the same word, if
133
 * possible. We are not doing preallocations in the
134
 * header zone, though.
135
 */
136
 
137
u32
138
affs_alloc_block(struct inode *inode, u32 goal)
139
{
140
        struct super_block *sb;
141
        struct affs_sb_info *sbi;
142
        struct affs_bm_info *bm;
143
        struct buffer_head *bh;
144
        __be32 *data, *enddata;
145
        u32 blk, bmap, bit, mask, mask2, tmp;
146
        int i;
147
 
148
        sb = inode->i_sb;
149
        sbi = AFFS_SB(sb);
150
 
151
        pr_debug("AFFS: balloc(inode=%lu,goal=%u): ", inode->i_ino, goal);
152
 
153
        if (AFFS_I(inode)->i_pa_cnt) {
154
                pr_debug("%d\n", AFFS_I(inode)->i_lastalloc+1);
155
                AFFS_I(inode)->i_pa_cnt--;
156
                return ++AFFS_I(inode)->i_lastalloc;
157
        }
158
 
159
        if (!goal || goal > sbi->s_partition_size) {
160
                if (goal)
161
                        affs_warning(sb, "affs_balloc", "invalid goal %d", goal);
162
                //if (!AFFS_I(inode)->i_last_block)
163
                //      affs_warning(sb, "affs_balloc", "no last alloc block");
164
                goal = sbi->s_reserved;
165
        }
166
 
167
        blk = goal - sbi->s_reserved;
168
        bmap = blk / sbi->s_bmap_bits;
169
        bm = &sbi->s_bitmap[bmap];
170
 
171
        down(&sbi->s_bmlock);
172
 
173
        if (bm->bm_free)
174
                goto find_bmap_bit;
175
 
176
find_bmap:
177
        /* search for the next bmap buffer with free bits */
178
        i = sbi->s_bmap_count;
179
        do {
180
                if (--i < 0)
181
                        goto err_full;
182
                bmap++;
183
                bm++;
184
                if (bmap < sbi->s_bmap_count)
185
                        continue;
186
                /* restart search at zero */
187
                bmap = 0;
188
                bm = sbi->s_bitmap;
189
        } while (!bm->bm_free);
190
        blk = bmap * sbi->s_bmap_bits;
191
 
192
find_bmap_bit:
193
 
194
        bh = sbi->s_bmap_bh;
195
        if (sbi->s_last_bmap != bmap) {
196
                affs_brelse(bh);
197
                bh = affs_bread(sb, bm->bm_key);
198
                if (!bh)
199
                        goto err_bh_read;
200
                sbi->s_bmap_bh = bh;
201
                sbi->s_last_bmap = bmap;
202
        }
203
 
204
        /* find an unused block in this bitmap block */
205
        bit = blk % sbi->s_bmap_bits;
206
        data = (__be32 *)bh->b_data + bit / 32 + 1;
207
        enddata = (__be32 *)((u8 *)bh->b_data + sb->s_blocksize);
208
        mask = ~0UL << (bit & 31);
209
        blk &= ~31UL;
210
 
211
        tmp = be32_to_cpu(*data);
212
        if (tmp & mask)
213
                goto find_bit;
214
 
215
        /* scan the rest of the buffer */
216
        do {
217
                blk += 32;
218
                if (++data >= enddata)
219
                        /* didn't find something, can only happen
220
                         * if scan didn't start at 0, try next bmap
221
                         */
222
                        goto find_bmap;
223
        } while (!*data);
224
        tmp = be32_to_cpu(*data);
225
        mask = ~0;
226
 
227
find_bit:
228
        /* finally look for a free bit in the word */
229
        bit = ffs(tmp & mask) - 1;
230
        blk += bit + sbi->s_reserved;
231
        mask2 = mask = 1 << (bit & 31);
232
        AFFS_I(inode)->i_lastalloc = blk;
233
 
234
        /* prealloc as much as possible within this word */
235
        while ((mask2 <<= 1)) {
236
                if (!(tmp & mask2))
237
                        break;
238
                AFFS_I(inode)->i_pa_cnt++;
239
                mask |= mask2;
240
        }
241
        bm->bm_free -= AFFS_I(inode)->i_pa_cnt + 1;
242
 
243
        *data = cpu_to_be32(tmp & ~mask);
244
 
245
        /* fix checksum */
246
        tmp = be32_to_cpu(*(__be32 *)bh->b_data);
247
        *(__be32 *)bh->b_data = cpu_to_be32(tmp + mask);
248
 
249
        mark_buffer_dirty(bh);
250
        sb->s_dirt = 1;
251
 
252
        up(&sbi->s_bmlock);
253
 
254
        pr_debug("%d\n", blk);
255
        return blk;
256
 
257
err_bh_read:
258
        affs_error(sb,"affs_read_block","Cannot read bitmap block %u", bm->bm_key);
259
        sbi->s_bmap_bh = NULL;
260
        sbi->s_last_bmap = ~0;
261
err_full:
262
        up(&sbi->s_bmlock);
263
        pr_debug("failed\n");
264
        return 0;
265
}
266
 
267
int affs_init_bitmap(struct super_block *sb, int *flags)
268
{
269
        struct affs_bm_info *bm;
270
        struct buffer_head *bmap_bh = NULL, *bh = NULL;
271
        __be32 *bmap_blk;
272
        u32 size, blk, end, offset, mask;
273
        int i, res = 0;
274
        struct affs_sb_info *sbi = AFFS_SB(sb);
275
 
276
        if (*flags & MS_RDONLY)
277
                return 0;
278
 
279
        if (!AFFS_ROOT_TAIL(sb, sbi->s_root_bh)->bm_flag) {
280
                printk(KERN_NOTICE "AFFS: Bitmap invalid - mounting %s read only\n",
281
                        sb->s_id);
282
                *flags |= MS_RDONLY;
283
                return 0;
284
        }
285
 
286
        sbi->s_last_bmap = ~0;
287
        sbi->s_bmap_bh = NULL;
288
        sbi->s_bmap_bits = sb->s_blocksize * 8 - 32;
289
        sbi->s_bmap_count = (sbi->s_partition_size - sbi->s_reserved +
290
                                 sbi->s_bmap_bits - 1) / sbi->s_bmap_bits;
291
        size = sbi->s_bmap_count * sizeof(*bm);
292
        bm = sbi->s_bitmap = kzalloc(size, GFP_KERNEL);
293
        if (!sbi->s_bitmap) {
294
                printk(KERN_ERR "AFFS: Bitmap allocation failed\n");
295
                return -ENOMEM;
296
        }
297
 
298
        bmap_blk = (__be32 *)sbi->s_root_bh->b_data;
299
        blk = sb->s_blocksize / 4 - 49;
300
        end = blk + 25;
301
 
302
        for (i = sbi->s_bmap_count; i > 0; bm++, i--) {
303
                affs_brelse(bh);
304
 
305
                bm->bm_key = be32_to_cpu(bmap_blk[blk]);
306
                bh = affs_bread(sb, bm->bm_key);
307
                if (!bh) {
308
                        printk(KERN_ERR "AFFS: Cannot read bitmap\n");
309
                        res = -EIO;
310
                        goto out;
311
                }
312
                if (affs_checksum_block(sb, bh)) {
313
                        printk(KERN_WARNING "AFFS: Bitmap %u invalid - mounting %s read only.\n",
314
                               bm->bm_key, sb->s_id);
315
                        *flags |= MS_RDONLY;
316
                        goto out;
317
                }
318
                pr_debug("AFFS: read bitmap block %d: %d\n", blk, bm->bm_key);
319
                bm->bm_free = affs_count_free_bits(sb->s_blocksize - 4, bh->b_data + 4);
320
 
321
                /* Don't try read the extension if this is the last block,
322
                 * but we also need the right bm pointer below
323
                 */
324
                if (++blk < end || i == 1)
325
                        continue;
326
                if (bmap_bh)
327
                        affs_brelse(bmap_bh);
328
                bmap_bh = affs_bread(sb, be32_to_cpu(bmap_blk[blk]));
329
                if (!bmap_bh) {
330
                        printk(KERN_ERR "AFFS: Cannot read bitmap extension\n");
331
                        res = -EIO;
332
                        goto out;
333
                }
334
                bmap_blk = (__be32 *)bmap_bh->b_data;
335
                blk = 0;
336
                end = sb->s_blocksize / 4 - 1;
337
        }
338
 
339
        offset = (sbi->s_partition_size - sbi->s_reserved) % sbi->s_bmap_bits;
340
        mask = ~(0xFFFFFFFFU << (offset & 31));
341
        pr_debug("last word: %d %d %d\n", offset, offset / 32 + 1, mask);
342
        offset = offset / 32 + 1;
343
 
344
        if (mask) {
345
                u32 old, new;
346
 
347
                /* Mark unused bits in the last word as allocated */
348
                old = be32_to_cpu(((__be32 *)bh->b_data)[offset]);
349
                new = old & mask;
350
                //if (old != new) {
351
                        ((__be32 *)bh->b_data)[offset] = cpu_to_be32(new);
352
                        /* fix checksum */
353
                        //new -= old;
354
                        //old = be32_to_cpu(*(__be32 *)bh->b_data);
355
                        //*(__be32 *)bh->b_data = cpu_to_be32(old - new);
356
                        //mark_buffer_dirty(bh);
357
                //}
358
                /* correct offset for the bitmap count below */
359
                //offset++;
360
        }
361
        while (++offset < sb->s_blocksize / 4)
362
                ((__be32 *)bh->b_data)[offset] = 0;
363
        ((__be32 *)bh->b_data)[0] = 0;
364
        ((__be32 *)bh->b_data)[0] = cpu_to_be32(-affs_checksum_block(sb, bh));
365
        mark_buffer_dirty(bh);
366
 
367
        /* recalculate bitmap count for last block */
368
        bm--;
369
        bm->bm_free = affs_count_free_bits(sb->s_blocksize - 4, bh->b_data + 4);
370
 
371
out:
372
        affs_brelse(bh);
373
        affs_brelse(bmap_bh);
374
        return res;
375
}
376
 
377
void affs_free_bitmap(struct super_block *sb)
378
{
379
        struct affs_sb_info *sbi = AFFS_SB(sb);
380
 
381
        if (!sbi->s_bitmap)
382
                return;
383
 
384
        affs_brelse(sbi->s_bmap_bh);
385
        sbi->s_bmap_bh = NULL;
386
        sbi->s_last_bmap = ~0;
387
        kfree(sbi->s_bitmap);
388
        sbi->s_bitmap = NULL;
389
}

powered by: WebSVN 2.1.0

© copyright 1999-2025 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.