This source file includes following definitions.
- xfs_bitmap_set
- xfs_bitmap_destroy
- xfs_bitmap_init
- xfs_bitmap_range_cmp
- xfs_bitmap_disunion
- xfs_bitmap_set_btcur_path
- xfs_bitmap_collect_btblock
- xfs_bitmap_set_btblocks
1
2
3
4
5
6 #include "xfs.h"
7 #include "xfs_fs.h"
8 #include "xfs_shared.h"
9 #include "xfs_format.h"
10 #include "xfs_trans_resv.h"
11 #include "xfs_mount.h"
12 #include "xfs_btree.h"
13 #include "scrub/bitmap.h"
14
15
16
17
18
19
20 int
21 xfs_bitmap_set(
22 struct xfs_bitmap *bitmap,
23 uint64_t start,
24 uint64_t len)
25 {
26 struct xfs_bitmap_range *bmr;
27
28 bmr = kmem_alloc(sizeof(struct xfs_bitmap_range), KM_MAYFAIL);
29 if (!bmr)
30 return -ENOMEM;
31
32 INIT_LIST_HEAD(&bmr->list);
33 bmr->start = start;
34 bmr->len = len;
35 list_add_tail(&bmr->list, &bitmap->list);
36
37 return 0;
38 }
39
40
41 void
42 xfs_bitmap_destroy(
43 struct xfs_bitmap *bitmap)
44 {
45 struct xfs_bitmap_range *bmr;
46 struct xfs_bitmap_range *n;
47
48 for_each_xfs_bitmap_extent(bmr, n, bitmap) {
49 list_del(&bmr->list);
50 kmem_free(bmr);
51 }
52 }
53
54
55 void
56 xfs_bitmap_init(
57 struct xfs_bitmap *bitmap)
58 {
59 INIT_LIST_HEAD(&bitmap->list);
60 }
61
62
63 static int
64 xfs_bitmap_range_cmp(
65 void *priv,
66 struct list_head *a,
67 struct list_head *b)
68 {
69 struct xfs_bitmap_range *ap;
70 struct xfs_bitmap_range *bp;
71
72 ap = container_of(a, struct xfs_bitmap_range, list);
73 bp = container_of(b, struct xfs_bitmap_range, list);
74
75 if (ap->start > bp->start)
76 return 1;
77 if (ap->start < bp->start)
78 return -1;
79 return 0;
80 }
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96 #define LEFT_ALIGNED (1 << 0)
97 #define RIGHT_ALIGNED (1 << 1)
98 int
99 xfs_bitmap_disunion(
100 struct xfs_bitmap *bitmap,
101 struct xfs_bitmap *sub)
102 {
103 struct list_head *lp;
104 struct xfs_bitmap_range *br;
105 struct xfs_bitmap_range *new_br;
106 struct xfs_bitmap_range *sub_br;
107 uint64_t sub_start;
108 uint64_t sub_len;
109 int state;
110 int error = 0;
111
112 if (list_empty(&bitmap->list) || list_empty(&sub->list))
113 return 0;
114 ASSERT(!list_empty(&sub->list));
115
116 list_sort(NULL, &bitmap->list, xfs_bitmap_range_cmp);
117 list_sort(NULL, &sub->list, xfs_bitmap_range_cmp);
118
119
120
121
122
123
124
125
126
127 sub_br = list_first_entry(&sub->list, struct xfs_bitmap_range,
128 list);
129 lp = bitmap->list.next;
130 while (lp != &bitmap->list) {
131 br = list_entry(lp, struct xfs_bitmap_range, list);
132
133
134
135
136
137 while (sub_br->start + sub_br->len <= br->start) {
138 if (list_is_last(&sub_br->list, &sub->list))
139 goto out;
140 sub_br = list_next_entry(sub_br, list);
141 }
142 if (sub_br->start >= br->start + br->len) {
143 lp = lp->next;
144 continue;
145 }
146
147
148 sub_start = sub_br->start;
149 sub_len = sub_br->len;
150 if (sub_br->start < br->start) {
151 sub_len -= br->start - sub_br->start;
152 sub_start = br->start;
153 }
154 if (sub_len > br->len)
155 sub_len = br->len;
156
157 state = 0;
158 if (sub_start == br->start)
159 state |= LEFT_ALIGNED;
160 if (sub_start + sub_len == br->start + br->len)
161 state |= RIGHT_ALIGNED;
162 switch (state) {
163 case LEFT_ALIGNED:
164
165 br->start += sub_len;
166 br->len -= sub_len;
167 break;
168 case RIGHT_ALIGNED:
169
170 br->len -= sub_len;
171 lp = lp->next;
172 break;
173 case LEFT_ALIGNED | RIGHT_ALIGNED:
174
175 lp = lp->next;
176 list_del(&br->list);
177 kmem_free(br);
178 break;
179 case 0:
180
181
182
183
184 new_br = kmem_alloc(sizeof(struct xfs_bitmap_range),
185 KM_MAYFAIL);
186 if (!new_br) {
187 error = -ENOMEM;
188 goto out;
189 }
190 INIT_LIST_HEAD(&new_br->list);
191 new_br->start = sub_start + sub_len;
192 new_br->len = br->start + br->len - new_br->start;
193 list_add(&new_br->list, &br->list);
194 br->len = sub_start - br->start;
195 lp = lp->next;
196 break;
197 default:
198 ASSERT(0);
199 break;
200 }
201 }
202
203 out:
204 return error;
205 }
206 #undef LEFT_ALIGNED
207 #undef RIGHT_ALIGNED
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249 int
250 xfs_bitmap_set_btcur_path(
251 struct xfs_bitmap *bitmap,
252 struct xfs_btree_cur *cur)
253 {
254 struct xfs_buf *bp;
255 xfs_fsblock_t fsb;
256 int i;
257 int error;
258
259 for (i = 0; i < cur->bc_nlevels && cur->bc_ptrs[i] == 1; i++) {
260 xfs_btree_get_block(cur, i, &bp);
261 if (!bp)
262 continue;
263 fsb = XFS_DADDR_TO_FSB(cur->bc_mp, bp->b_bn);
264 error = xfs_bitmap_set(bitmap, fsb, 1);
265 if (error)
266 return error;
267 }
268
269 return 0;
270 }
271
272
273 STATIC int
274 xfs_bitmap_collect_btblock(
275 struct xfs_btree_cur *cur,
276 int level,
277 void *priv)
278 {
279 struct xfs_bitmap *bitmap = priv;
280 struct xfs_buf *bp;
281 xfs_fsblock_t fsbno;
282
283 xfs_btree_get_block(cur, level, &bp);
284 if (!bp)
285 return 0;
286
287 fsbno = XFS_DADDR_TO_FSB(cur->bc_mp, bp->b_bn);
288 return xfs_bitmap_set(bitmap, fsbno, 1);
289 }
290
291
292 int
293 xfs_bitmap_set_btblocks(
294 struct xfs_bitmap *bitmap,
295 struct xfs_btree_cur *cur)
296 {
297 return xfs_btree_visit_blocks(cur, xfs_bitmap_collect_btblock, bitmap);
298 }