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 4532824 : xbitmap_init(&bitmap->agbitmap);
48 15249 : }
49 :
50 : static inline void xagb_bitmap_destroy(struct xagb_bitmap *bitmap)
51 : {
52 4549005 : 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 14854400 : 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 71396767 : return xbitmap_set(&bitmap->agbitmap, start, len);
64 : }
65 :
66 : static inline bool
67 5100856 : xagb_bitmap_test(
68 : struct xagb_bitmap *bitmap,
69 : xfs_agblock_t start,
70 : xfs_extlen_t *len)
71 : {
72 5100856 : uint64_t biglen = *len;
73 5100856 : bool ret;
74 :
75 5100856 : ret = xbitmap_test(&bitmap->agbitmap, start, &biglen);
76 :
77 5100742 : if (start + biglen >= UINT_MAX) {
78 0 : ASSERT(0);
79 0 : biglen = UINT_MAX - start;
80 : }
81 :
82 5100742 : *len = biglen;
83 5100742 : return ret;
84 : }
85 :
86 : static inline int xagb_bitmap_disunion(struct xagb_bitmap *bitmap,
87 : struct xagb_bitmap *sub)
88 : {
89 326806 : 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 15854 : return xbitmap_count_set_regions(&bitmap->agbitmap);
95 : }
96 : static inline uint32_t xagb_bitmap_hweight(struct xagb_bitmap *bitmap)
97 : {
98 273513 : return xbitmap_hweight(&bitmap->agbitmap);
99 : }
100 : static inline bool xagb_bitmap_empty(struct xagb_bitmap *bitmap)
101 : {
102 15534 : 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 4361895 : 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_fsblock_t */
117 :
118 : struct xfsb_bitmap {
119 : struct xbitmap fsbitmap;
120 : };
121 :
122 : static inline void xfsb_bitmap_init(struct xfsb_bitmap *bitmap)
123 : {
124 2628411 : xbitmap_init(&bitmap->fsbitmap);
125 : }
126 :
127 : static inline void xfsb_bitmap_destroy(struct xfsb_bitmap *bitmap)
128 : {
129 2629688 : xbitmap_destroy(&bitmap->fsbitmap);
130 : }
131 :
132 : static inline int xfsb_bitmap_set(struct xfsb_bitmap *bitmap,
133 : xfs_fsblock_t start, xfs_filblks_t len)
134 : {
135 83961 : return xbitmap_set(&bitmap->fsbitmap, start, len);
136 : }
137 :
138 : static inline int xfsb_bitmap_walk(struct xfsb_bitmap *bitmap,
139 : xbitmap_walk_fn fn, void *priv)
140 : {
141 2629676 : return xbitmap_walk(&bitmap->fsbitmap, fn, priv);
142 : }
143 :
144 : /* Bitmaps, but for type-checked for xfs_ino_t */
145 :
146 : struct xino_bitmap {
147 : struct xbitmap inobitmap;
148 : };
149 :
150 : static inline void xino_bitmap_init(struct xino_bitmap *bitmap)
151 : {
152 21345294 : xbitmap_init(&bitmap->inobitmap);
153 : }
154 :
155 : static inline void xino_bitmap_destroy(struct xino_bitmap *bitmap)
156 : {
157 21607342 : xbitmap_destroy(&bitmap->inobitmap);
158 : }
159 :
160 : static inline int xino_bitmap_set(struct xino_bitmap *bitmap, xfs_ino_t ino)
161 : {
162 1705417908 : return xbitmap_set(&bitmap->inobitmap, ino, 1);
163 : }
164 :
165 : static inline int xino_bitmap_test(struct xino_bitmap *bitmap, xfs_ino_t ino)
166 : {
167 1724654814 : uint64_t len = 1;
168 :
169 1724654814 : return xbitmap_test(&bitmap->inobitmap, ino, &len);
170 : }
171 :
172 : #endif /* __XFS_SCRUB_BITMAP_H__ */
|
