1 | /* space_bitmap.c
2 | --------------
3 | Simple space allocator using a bitmap
4 |
5 | $Id: space_bitmap.c,v 1.11 2003/10/20 07:18:11 stewart Exp $
6 |
7 | (C)2003 Stewart Smith
8 | Distributed under the GNU Public License
9 | */
10 |
11 | #include <stdio.h>
12 | #include <stdlib.h>
13 | #include "testkit/block_dev.h"
14 | #include "testkit/bitops.h"
15 | #include "super_block.h"
16 | #include "disk.h"
17 | #include "space_bitmap.h"
18 |
19 | #define MAX_DIV(a,b) (((a%b)==0)?(a/b):(a/b)+1)
20 |
21 | u64 next_free = 300;
22 |
23 | u32 space_bitmap_size(struct fcfs_sb *sb, int ag)
24 | {
25 | /* if last ag, is remaining no. of blocks */
26 | if(ag == sb->allocation_groupsnr-1)
27 | return MAX_DIV(MAX_DIV((sb->ag_blocksnr+(sb->blocksnr%sb->allocation_groupsnr)),8),sb->bsize);
28 | else
29 | /* 1 bit per block */
30 | return MAX_DIV(MAX_DIV(sb->ag_blocksnr,8),sb->bsize);
31 | }
32 |
33 | int space_bitmap_allocate_block(struct fcfs_disk *disk, u32 allocation_group,u32 block)
34 | {
35 | struct fcfs_disk_block *b;
36 |
37 | #ifdef DEBUG_SPACE_BITMAP
38 | printf("ALLOC %u %u\n",allocation_group,block);
39 | #endif
40 |
41 | b = disk_getblock(disk,
42 | (allocation_group)*disk->sb->ag_blocksnr
43 | +(block/(disk->sb->bsize*8))
44 | +1);
45 | set_bit(block%8,
46 | (b->data+((block%(disk->sb->bsize*8))/8)));
47 |
48 | disk_writeblock(b);
49 | disk_freeblock(b);
50 | return 0;
51 | }
52 |
53 | struct fcfs_block_run *ag_allocate_block(struct fcfs_disk *disk, u32 allocation_group, u32 near, u32 blocksnr)
54 | {
55 | struct fcfs_block_run *br;
56 | int i;
57 |
58 | #ifdef DEBUG_SPACE_BITMAP
59 | printf("%u %u\n",allocation_group,near);
60 | #endif
61 |
62 | br = (struct fcfs_block_run*)malloc(sizeof(struct fcfs_block_run));
63 | if(!br)
64 | {
65 | fprintf(stderr,"ag_allocate_block: Unable to allocate block_run\n");
66 | abort();
67 | }
68 |
69 | br->start = 0;
70 | br->len = 0;
71 |
72 | if(near+blocksnr > disk->sb->ag_blocksnr)
73 | blocksnr = disk->sb->ag_blocksnr - near;
74 |
75 | for(i=1;i<=blocksnr+1;i++)
76 | {
77 | if(near+i>=disk->sb->ag_blocksnr)
78 | {allocation_group++;near=0;i=0; br->start=0;br->len=0;/*printf("RESTARTING BLOCK SEARCH IN NEW ALLOCATION GROUP\n");*/}
79 | if(ag_block_free(disk,allocation_group,near+i))
80 | {
81 | #ifdef DEBUG_SPACE_BITMAP
82 | fprintf(stderr,"BLOCK %lu %lu is free\n",allocation_group,near+i);
83 | #endif
84 | if(br->start==0)
85 | { br->start=near+i; br->len=1;}
86 | else
87 | if((br->start+br->len)==(near+i-1))
88 | br->len++;
89 | }
90 | else
91 | {
92 | //fprintf(stderr,"BLOCK %lu %lu isn't free\n",allocation_group,near+i);
93 | near++;
94 | i=0;
95 | }
96 | }
97 |
98 | br->allocation_group = allocation_group;
99 |
100 | for(i=0;i<br->len;i++)
101 | space_bitmap_allocate_block(disk,br->allocation_group,br->start+i);
102 |
103 | next_free = br->start + br->len;
104 |
105 | return br;
106 | }
107 |
108 | u64 ag_block_free_last;
109 | struct fcfs_disk_block *ag_block_free_last_block;
110 |
111 | int ag_block_free(struct fcfs_disk *disk,u32 allocation_group, u32 block)
112 | {
113 | struct fcfs_disk_block *b;
114 | int retval;
115 |
116 | #ifdef DEBUG_SPACE_BITMAP
117 | printf("\t%u %u\n",allocation_group,block);
118 | #endif
119 |
120 | if(block > disk->sb->ag_blocksnr)
121 | {
122 | fprintf(stderr,"ERROR: ag_black_free() can't check block that's out of this AG\n");
123 | abort();
124 | }
125 |
126 | if(ag_block_free_last==0 ||
127 | ag_block_free_last!=
128 | (allocation_group)*disk->sb->ag_blocksnr+(block/(disk->sb->bsize*8))+1
129 | )
130 | {
131 | if(ag_block_free_last!=0) disk_freeblock(ag_block_free_last_block);
132 | ag_block_free_last = (allocation_group)*disk->sb->ag_blocksnr
133 | +(block/(disk->sb->bsize*8))
134 | +1;
135 | ag_block_free_last_block = b = disk_getblock(disk,ag_block_free_last);
136 | }
137 | else
138 | {
139 | b = ag_block_free_last_block;
140 | }
141 |
142 |
143 | retval = !test_bit(block%8,
144 | (b->data+((block%(disk->sb->bsize*8))/8)));
145 |
146 |
147 | return retval;
148 | }