Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0-or-later
2 : /*
3 : * Copyright (C) 2018-2023 Oracle. All Rights Reserved.
4 : * Author: Darrick J. Wong <djwong@kernel.org>
5 : */
6 : #ifndef __XFS_SCRUB_BITMAP_H__
7 : #define __XFS_SCRUB_BITMAP_H__
8 :
9 : struct xbitmap {
10 : struct rb_root_cached xb_root;
11 : };
12 :
13 : void xbitmap_init(struct xbitmap *bitmap);
14 : void xbitmap_destroy(struct xbitmap *bitmap);
15 :
16 : int xbitmap_clear(struct xbitmap *bitmap, uint64_t start, uint64_t len);
17 : int xbitmap_set(struct xbitmap *bitmap, uint64_t start, uint64_t len);
18 : int xbitmap_disunion(struct xbitmap *bitmap, struct xbitmap *sub);
19 : uint64_t xbitmap_hweight(struct xbitmap *bitmap);
20 :
21 : /*
22 : * Return codes for the bitmap iterator functions are 0 to continue iterating,
23 : * and non-zero to stop iterating. Any non-zero value will be passed up to the
24 : * iteration caller. The special value -ECANCELED can be used to stop
25 : * iteration, because neither bitmap iterator ever generates that error code on
26 : * its own. Callers must not modify the bitmap while walking it.
27 : */
28 : typedef int (*xbitmap_walk_fn)(uint64_t start, uint64_t len, void *priv);
29 : int xbitmap_walk(struct xbitmap *bitmap, xbitmap_walk_fn fn,
30 : void *priv);
31 :
32 : bool xbitmap_empty(struct xbitmap *bitmap);
33 : bool xbitmap_test(struct xbitmap *bitmap, uint64_t start, uint64_t *len);
34 : uint64_t xbitmap_count_set_regions(struct xbitmap *bitmap);
35 :
36 : int xbitmap_take_first_set(struct xbitmap *bitmap, uint64_t start,
37 : uint64_t last, uint64_t *valp);
38 :
39 : /* Bitmaps, but for type-checked for xfs_agblock_t */
40 :
41 : struct xagb_bitmap {
42 : struct xbitmap agbitmap;
43 : };
44 :
45 : static inline void xagb_bitmap_init(struct xagb_bitmap *bitmap)
46 : {
47 9840361 : xbitmap_init(&bitmap->agbitmap);
48 9219 : }
49 :
50 : static inline void xagb_bitmap_destroy(struct xagb_bitmap *bitmap)
51 : {
52 9849801 : xbitmap_destroy(&bitmap->agbitmap);
53 : }
54 :
55 : static inline int xagb_bitmap_clear(struct xagb_bitmap *bitmap,
56 : xfs_agblock_t start, xfs_extlen_t len)
57 : {
58 7721152 : return xbitmap_clear(&bitmap->agbitmap, start, len);
59 : }
60 : static inline int xagb_bitmap_set(struct xagb_bitmap *bitmap,
61 : xfs_agblock_t start, xfs_extlen_t len)
62 : {
63 67954300 : return xbitmap_set(&bitmap->agbitmap, start, len);
64 : }
65 :
66 : static inline bool
67 6789556 : xagb_bitmap_test(
68 : struct xagb_bitmap *bitmap,
69 : xfs_agblock_t start,
70 : xfs_extlen_t *len)
71 : {
72 6789556 : uint64_t biglen = *len;
73 6789556 : bool ret;
74 :
75 6789556 : ret = xbitmap_test(&bitmap->agbitmap, start, &biglen);
76 :
77 6789555 : if (start + biglen >= UINT_MAX) {
78 0 : ASSERT(0);
79 0 : biglen = UINT_MAX - start;
80 : }
81 :
82 6789555 : *len = biglen;
83 6789555 : return ret;
84 : }
85 :
86 : static inline int xagb_bitmap_disunion(struct xagb_bitmap *bitmap,
87 : struct xagb_bitmap *sub)
88 : {
89 479356 : return xbitmap_disunion(&bitmap->agbitmap, &sub->agbitmap);
90 : }
91 :
92 : static inline uint32_t xagb_bitmap_count_set_regions(struct xagb_bitmap *bitmap)
93 : {
94 9418 : return xbitmap_count_set_regions(&bitmap->agbitmap);
95 : }
96 : static inline uint32_t xagb_bitmap_hweight(struct xagb_bitmap *bitmap)
97 : {
98 252261 : return xbitmap_hweight(&bitmap->agbitmap);
99 : }
100 : static inline bool xagb_bitmap_empty(struct xagb_bitmap *bitmap)
101 : {
102 9261 : return xbitmap_empty(&bitmap->agbitmap);
103 : }
104 :
105 : static inline int xagb_bitmap_walk(struct xagb_bitmap *bitmap,
106 : xbitmap_walk_fn fn, void *priv)
107 : {
108 9659406 : return xbitmap_walk(&bitmap->agbitmap, fn, priv);
109 : }
110 :
111 : int xagb_bitmap_set_btblocks(struct xagb_bitmap *bitmap,
112 : struct xfs_btree_cur *cur);
113 : int xagb_bitmap_set_btcur_path(struct xagb_bitmap *bitmap,
114 : struct xfs_btree_cur *cur);
115 :
116 : /* Bitmaps, but for type-checked for xfs_rgblock_t */
117 :
118 : struct xrgb_bitmap {
119 : struct xbitmap rgbitmap;
120 : };
121 :
122 : static inline void xrgb_bitmap_init(struct xrgb_bitmap *bitmap)
123 : {
124 3249 : xbitmap_init(&bitmap->rgbitmap);
125 : }
126 :
127 : static inline void xrgb_bitmap_destroy(struct xrgb_bitmap *bitmap)
128 : {
129 3249 : xbitmap_destroy(&bitmap->rgbitmap);
130 : }
131 :
132 : static inline int xrgb_bitmap_set(struct xrgb_bitmap *bitmap,
133 : xfs_rgblock_t start, xfs_extlen_t len)
134 : {
135 34838 : return xbitmap_set(&bitmap->rgbitmap, start, len);
136 : }
137 :
138 : static inline int xrgb_bitmap_walk(struct xrgb_bitmap *bitmap,
139 : xbitmap_walk_fn fn, void *priv)
140 : {
141 3249 : return xbitmap_walk(&bitmap->rgbitmap, fn, priv);
142 : }
143 :
144 : /* Bitmaps, but for type-checked for xfs_fsblock_t */
145 :
146 : struct xfsb_bitmap {
147 : struct xbitmap fsbitmap;
148 : };
149 :
150 : static inline void xfsb_bitmap_init(struct xfsb_bitmap *bitmap)
151 : {
152 175291 : xbitmap_init(&bitmap->fsbitmap);
153 23431 : }
154 :
155 : static inline void xfsb_bitmap_destroy(struct xfsb_bitmap *bitmap)
156 : {
157 175290 : xbitmap_destroy(&bitmap->fsbitmap);
158 23431 : }
159 :
160 : static inline int xfsb_bitmap_set(struct xfsb_bitmap *bitmap,
161 : xfs_fsblock_t start, xfs_filblks_t len)
162 : {
163 60343 : return xbitmap_set(&bitmap->fsbitmap, start, len);
164 : }
165 :
166 : static inline int xfsb_bitmap_walk(struct xfsb_bitmap *bitmap,
167 : xbitmap_walk_fn fn, void *priv)
168 : {
169 175230 : return xbitmap_walk(&bitmap->fsbitmap, fn, priv);
170 : }
171 :
172 : /* Bitmaps, but for type-checked for xfs_ino_t */
173 :
174 : struct xino_bitmap {
175 : struct xbitmap inobitmap;
176 : };
177 :
178 : static inline void xino_bitmap_init(struct xino_bitmap *bitmap)
179 : {
180 11444002 : xbitmap_init(&bitmap->inobitmap);
181 : }
182 :
183 : static inline void xino_bitmap_destroy(struct xino_bitmap *bitmap)
184 : {
185 11448986 : xbitmap_destroy(&bitmap->inobitmap);
186 : }
187 :
188 : static inline int xino_bitmap_set(struct xino_bitmap *bitmap, xfs_ino_t ino)
189 : {
190 1069472980 : return xbitmap_set(&bitmap->inobitmap, ino, 1);
191 : }
192 :
193 : static inline int xino_bitmap_test(struct xino_bitmap *bitmap, xfs_ino_t ino)
194 : {
195 1067483733 : uint64_t len = 1;
196 :
197 1067483733 : return xbitmap_test(&bitmap->inobitmap, ino, &len);
198 : }
199 :
200 : /* Bitmaps, but for type-checked for xfs_rtblock_t */
201 :
202 : struct xrtb_bitmap {
203 : struct xbitmap rtbitmap;
204 : };
205 :
206 : static inline void xrtb_bitmap_init(struct xrtb_bitmap *bitmap)
207 : {
208 13210 : xbitmap_init(&bitmap->rtbitmap);
209 13210 : }
210 :
211 : static inline void xrtb_bitmap_destroy(struct xrtb_bitmap *bitmap)
212 : {
213 13210 : xbitmap_destroy(&bitmap->rtbitmap);
214 13210 : }
215 :
216 : static inline int xrtb_bitmap_set(struct xrtb_bitmap *bitmap,
217 : xfs_rtblock_t start, xfs_filblks_t len)
218 : {
219 2732 : return xbitmap_set(&bitmap->rtbitmap, start, len);
220 : }
221 :
222 : static inline int xrtb_bitmap_walk(struct xrtb_bitmap *bitmap,
223 : xbitmap_walk_fn fn, void *priv)
224 : {
225 13210 : return xbitmap_walk(&bitmap->rtbitmap, fn, priv);
226 : }
227 :
228 : #endif /* __XFS_SCRUB_BITMAP_H__ */
|
