1 | /* |
---|
2 | * COPYRIGHT (c) 2010 Chris Johns <chrisj@rtems.org> |
---|
3 | * |
---|
4 | * The license and distribution terms for this file may be |
---|
5 | * found in the file LICENSE in this distribution or at |
---|
6 | * http://www.rtems.com/license/LICENSE. |
---|
7 | * |
---|
8 | * $Id$ |
---|
9 | */ |
---|
10 | /** |
---|
11 | * @file |
---|
12 | * |
---|
13 | * @ingroup rtems-rfs |
---|
14 | * |
---|
15 | * RTEMS File Systems Bitmap Routines. |
---|
16 | * |
---|
17 | * These functions manage bit maps. A bit map consists of the map of bit |
---|
18 | * allocated in a block and a search map where a bit represents 32 actual |
---|
19 | * bits. The search map allows for a faster search for an available bit as 32 |
---|
20 | * search bits can checked in a test. |
---|
21 | */ |
---|
22 | |
---|
23 | #if !defined (_RTEMS_RFS_BITMAPS_H_) |
---|
24 | #define _RTEMS_RFS_BITMAPS_H_ |
---|
25 | |
---|
26 | #include <rtems/rfs/rtems-rfs-buffer.h> |
---|
27 | #include <rtems/rfs/rtems-rfs-file-system-fwd.h> |
---|
28 | #include <rtems/rfs/rtems-rfs-trace.h> |
---|
29 | |
---|
30 | /** |
---|
31 | * Define the way the bits are configured. We can have them configured as clear |
---|
32 | * being 0 or clear being 1. This does not effect how masks are defined. A mask |
---|
33 | * always has a 1 for set and 0 for clear. |
---|
34 | */ |
---|
35 | #define RTEMS_RFS_BITMAP_CLEAR_ZERO 0 |
---|
36 | |
---|
37 | #if RTEMS_RFS_BITMAP_CLEAR_ZERO |
---|
38 | /* |
---|
39 | * Bit set is a 1 and clear is 0. |
---|
40 | */ |
---|
41 | #define RTEMS_RFS_BITMAP_BIT_CLEAR 0 |
---|
42 | #define RTEMS_RFS_BITMAP_BIT_SET 1 |
---|
43 | #define RTEMS_RFS_BITMAP_ELEMENT_SET (RTEMS_RFS_BITMAP_ELEMENT_FULL_MASK) |
---|
44 | #define RTEMS_RFS_BITMAP_ELEMENT_CLEAR (0) |
---|
45 | #define RTEMS_RFS_BITMAP_SET_BITS(_t, _b) ((_t) | (_b)) |
---|
46 | #define RTEMS_RFS_BITMAP_CLEAR_BITS(_t, _b) ((_t) & ~(_b)) |
---|
47 | #define RTEMS_RFS_BITMAP_TEST_BIT(_t, _b) (((_t) & (1 << (_b))) != 0 ? true : false) |
---|
48 | #else |
---|
49 | /* |
---|
50 | * Bit set is a 0 and clear is 1. |
---|
51 | */ |
---|
52 | #define RTEMS_RFS_BITMAP_BIT_CLEAR 1 |
---|
53 | #define RTEMS_RFS_BITMAP_BIT_SET 0 |
---|
54 | #define RTEMS_RFS_BITMAP_ELEMENT_SET (0) |
---|
55 | #define RTEMS_RFS_BITMAP_ELEMENT_CLEAR (RTEMS_RFS_BITMAP_ELEMENT_FULL_MASK) |
---|
56 | #define RTEMS_RFS_BITMAP_SET_BITS(_t, _b) ((_t) & ~(_b)) |
---|
57 | #define RTEMS_RFS_BITMAP_CLEAR_BITS(_t, _b) ((_t) | (_b)) |
---|
58 | #define RTEMS_RFS_BITMAP_TEST_BIT(_t, _b) (((_t) & (1 << (_b))) == 0 ? true : false) |
---|
59 | #endif |
---|
60 | |
---|
61 | /** |
---|
62 | * Invert a mask. Masks are always 1 for set and 0 for clear. |
---|
63 | */ |
---|
64 | #define RTEMS_RFS_BITMAP_INVERT_MASK(_mask) (~(_mask)) |
---|
65 | |
---|
66 | /** |
---|
67 | * This is the full mask of the length of the element. A mask is always a 1 for |
---|
68 | * set and 0 for clear. It is not effected by the state of |
---|
69 | * RTEMS_RFS_BITMAP_CLEAR_ZERO. |
---|
70 | */ |
---|
71 | #define RTEMS_RFS_BITMAP_ELEMENT_FULL_MASK (0xffffffffUL) |
---|
72 | |
---|
73 | /** |
---|
74 | * The bitmap search window. Searches occur around a seed in either direction |
---|
75 | * for half the window. |
---|
76 | */ |
---|
77 | #define RTEMS_RFS_BITMAP_SEARCH_WINDOW (rtems_rfs_bitmap_element_bits () * 64) |
---|
78 | |
---|
79 | /** |
---|
80 | * A bit in a map. |
---|
81 | */ |
---|
82 | typedef int32_t rtems_rfs_bitmap_bit; |
---|
83 | |
---|
84 | /** |
---|
85 | * The basic element of a bitmap. A bitmap is manipulated by elements. |
---|
86 | */ |
---|
87 | typedef uint32_t rtems_rfs_bitmap_element; |
---|
88 | |
---|
89 | /** |
---|
90 | * The power of 2 number of bits in the element. |
---|
91 | */ |
---|
92 | #define RTEMS_RFS_ELEMENT_BITS_POWER_2 (5) |
---|
93 | |
---|
94 | /** |
---|
95 | * A bitmap or map is an array of bitmap elements. |
---|
96 | */ |
---|
97 | typedef rtems_rfs_bitmap_element* rtems_rfs_bitmap_map; |
---|
98 | |
---|
99 | /** |
---|
100 | * The bitmap control is a simple way to manage the various parts of a bitmap. |
---|
101 | */ |
---|
102 | struct rtems_rfs_bitmap_control_t |
---|
103 | { |
---|
104 | rtems_rfs_buffer_handle* buffer; //< Handle the to buffer with the bit |
---|
105 | //map. |
---|
106 | rtems_rfs_file_system* fs; //< The map's file system. |
---|
107 | rtems_rfs_buffer_block block; //< The map's block number on disk. |
---|
108 | size_t size; //< Number of bits in the map. Passed |
---|
109 | //to create. |
---|
110 | size_t free; //< Number of bits in the map that are |
---|
111 | //free (clear). |
---|
112 | rtems_rfs_bitmap_map search_bits; //< The search bit map memory. |
---|
113 | }; |
---|
114 | |
---|
115 | typedef struct rtems_rfs_bitmap_control_t rtems_rfs_bitmap_control; |
---|
116 | |
---|
117 | /** |
---|
118 | * Return the number of bits for the number of bytes provided. |
---|
119 | */ |
---|
120 | #define rtems_rfs_bitmap_numof_bits(_bytes) (8 * (_bytes)) |
---|
121 | |
---|
122 | /** |
---|
123 | * Return the number of bits for the number of bytes provided. The search |
---|
124 | * element and the element must have the same number of bits. |
---|
125 | */ |
---|
126 | #define rtems_rfs_bitmap_element_bits() \ |
---|
127 | rtems_rfs_bitmap_numof_bits (sizeof (rtems_rfs_bitmap_element)) |
---|
128 | |
---|
129 | /** |
---|
130 | * Return the number of bits a search element covers. |
---|
131 | */ |
---|
132 | #define rtems_rfs_bitmap_search_element_bits() \ |
---|
133 | (rtems_rfs_bitmap_element_bits() * rtems_rfs_bitmap_element_bits()) |
---|
134 | |
---|
135 | /** |
---|
136 | * Return the number of elements for a given number of bits. |
---|
137 | */ |
---|
138 | #define rtems_rfs_bitmap_elements(_bits) \ |
---|
139 | ((((_bits) - 1) / rtems_rfs_bitmap_element_bits()) + 1) |
---|
140 | |
---|
141 | /** |
---|
142 | * Release the bitmap buffer back to the buffer pool or cache. |
---|
143 | */ |
---|
144 | #define rtems_rfs_bitmap_release_buffer(_fs, _bm) \ |
---|
145 | rtems_rfs_buffer_handle_release (_fs, (_bm)->buffer) |
---|
146 | |
---|
147 | /** |
---|
148 | * Return the element index for a given bit. We use a macro to hide any |
---|
149 | * implementation assuptions. Typically this would be calculated by dividing |
---|
150 | * the bit index by the number of bits in an element. Given we have a power of |
---|
151 | * 2 as the number of bits we can avoid the division by using a shift. A good |
---|
152 | * compiler should figure this out but I would rather enforce this than rely on |
---|
153 | * the specific backend of a compiler to do the right thing. |
---|
154 | */ |
---|
155 | #define rtems_rfs_bitmap_map_index(_b) \ |
---|
156 | ((_b) >> RTEMS_RFS_ELEMENT_BITS_POWER_2) |
---|
157 | |
---|
158 | /** |
---|
159 | * Return the bit offset for a given bit in an element in a map. See @ref |
---|
160 | * rtems_rfs_bitmap_map_index for a detailed reason why. |
---|
161 | */ |
---|
162 | #define rtems_rfs_bitmap_map_offset(_b) \ |
---|
163 | ((_b) & ((1 << RTEMS_RFS_ELEMENT_BITS_POWER_2) - 1)) |
---|
164 | |
---|
165 | /** |
---|
166 | * Return the size of the bitmap. |
---|
167 | */ |
---|
168 | #define rtems_rfs_bitmap_map_size(_c) ((_c)->size) |
---|
169 | |
---|
170 | /** |
---|
171 | * Return the number of free bits in the bitmap. |
---|
172 | */ |
---|
173 | #define rtems_rfs_bitmap_map_free(_c) ((_c)->free) |
---|
174 | |
---|
175 | /** |
---|
176 | * Return the buffer handle. |
---|
177 | */ |
---|
178 | #define rtems_rfs_bitmap_map_handle(_c) ((_c)->buffer) |
---|
179 | |
---|
180 | /** |
---|
181 | * Return the bitmap map block. |
---|
182 | */ |
---|
183 | #define rtems_rfs_bitmap_map_block(_c) ((_c)->block) |
---|
184 | |
---|
185 | /** |
---|
186 | * Create a bit mask with the specified number of bits up to an element's |
---|
187 | * size. The mask is aligned to bit 0 of the element. |
---|
188 | * |
---|
189 | * @param size The number of bits in the mask. |
---|
190 | * @return The mask of the argument size number of bits. |
---|
191 | */ |
---|
192 | rtems_rfs_bitmap_element rtems_rfs_bitmap_mask (unsigned int size); |
---|
193 | |
---|
194 | /** |
---|
195 | * Create a bit mask section. A mask section is a mask that is not aligned to |
---|
196 | * an end of the element. |
---|
197 | * |
---|
198 | * @param start The first bit of the mask numbered from 0. |
---|
199 | * @param end The end bit of the mask numbered from 0. |
---|
200 | * @return Mask section as defined by the start and end arguments. |
---|
201 | */ |
---|
202 | rtems_rfs_bitmap_element rtems_rfs_bitmap_mask_section (unsigned int start, |
---|
203 | unsigned int end); |
---|
204 | |
---|
205 | /** |
---|
206 | * Set a bit in a map and if all the bits are set, set the search map bit as |
---|
207 | * well. |
---|
208 | * |
---|
209 | * @param control The control for the map. |
---|
210 | * @param bit The bit in the map to set. |
---|
211 | * @return int The error number (errno). No error if 0. |
---|
212 | */ |
---|
213 | int rtems_rfs_bitmap_map_set (rtems_rfs_bitmap_control* control, |
---|
214 | rtems_rfs_bitmap_bit bit); |
---|
215 | |
---|
216 | /** |
---|
217 | * Clear a bit in a map and make sure the search map bit is clear so a search |
---|
218 | * will find this bit available. |
---|
219 | * |
---|
220 | * @param control The control for the map. |
---|
221 | * @param bit The bit in the map to clear. |
---|
222 | * @return int The error number (errno). No error if 0. |
---|
223 | */ |
---|
224 | int rtems_rfs_bitmap_map_clear (rtems_rfs_bitmap_control* control, |
---|
225 | rtems_rfs_bitmap_bit bit); |
---|
226 | |
---|
227 | /** |
---|
228 | * Test a bit in the map. |
---|
229 | * |
---|
230 | * @param control The bitmap control. |
---|
231 | * @param bit The bit to test. |
---|
232 | * @param state The state of the bit if no error is returned. |
---|
233 | * @return int The error number (errno). No error if 0. |
---|
234 | */ |
---|
235 | int |
---|
236 | rtems_rfs_bitmap_map_test (rtems_rfs_bitmap_control* control, |
---|
237 | rtems_rfs_bitmap_bit bit, |
---|
238 | bool* state); |
---|
239 | |
---|
240 | /** |
---|
241 | * Set all bits in the bitmap and set the dirty bit. |
---|
242 | * |
---|
243 | * @param control The bitmap control. |
---|
244 | * @return int The error number (errno). No error if 0. |
---|
245 | */ |
---|
246 | int rtems_rfs_bitmap_map_set_all (rtems_rfs_bitmap_control* control); |
---|
247 | |
---|
248 | /** |
---|
249 | * Clear all bits in the bitmap and set the dirty bit. |
---|
250 | * |
---|
251 | * @param control The bitmap control. |
---|
252 | * @return int The error number (errno). No error if 0. |
---|
253 | */ |
---|
254 | int rtems_rfs_bitmap_map_clear_all (rtems_rfs_bitmap_control* control); |
---|
255 | |
---|
256 | /** |
---|
257 | * Find a free bit searching from the seed up and down until found. The search |
---|
258 | * is performing by moving up from the seed for the window distance then to |
---|
259 | * search down from the seed for the window distance. This is repeated out from |
---|
260 | * the seed for each window until a free bit is found. The search is performed |
---|
261 | * by checking the search map to see if the map has a free bit. |
---|
262 | * |
---|
263 | * @param control The map control. |
---|
264 | * @param seed The bit to search out from. |
---|
265 | * @param allocate A bit was allocated. |
---|
266 | * @param bit Returns the bit found free if true is returned. |
---|
267 | * @return int The error number (errno). No error if 0. |
---|
268 | */ |
---|
269 | int rtems_rfs_bitmap_map_alloc (rtems_rfs_bitmap_control* control, |
---|
270 | rtems_rfs_bitmap_bit seed, |
---|
271 | bool* allocate, |
---|
272 | rtems_rfs_bitmap_bit* bit); |
---|
273 | |
---|
274 | /** |
---|
275 | * Create a search bit map from the actual bit map. |
---|
276 | * |
---|
277 | * @param control The map control. |
---|
278 | * @return int The error number (errno). No error if 0. |
---|
279 | */ |
---|
280 | int rtems_rfs_bitmap_create_search (rtems_rfs_bitmap_control* control); |
---|
281 | |
---|
282 | /** |
---|
283 | * Open a bitmap control with a map and search map. |
---|
284 | * |
---|
285 | * @param control The map control. |
---|
286 | * @param fs The file system data. |
---|
287 | * @param buffer The buffer handle the map is stored in. |
---|
288 | * @param size The number of bits in the map. |
---|
289 | * @return int The error number (errno). No error if 0. |
---|
290 | */ |
---|
291 | int rtems_rfs_bitmap_open (rtems_rfs_bitmap_control* control, |
---|
292 | rtems_rfs_file_system* fs, |
---|
293 | rtems_rfs_buffer_handle* buffer, |
---|
294 | size_t size, |
---|
295 | rtems_rfs_buffer_block block); |
---|
296 | |
---|
297 | /** |
---|
298 | * Close a bitmap. |
---|
299 | * |
---|
300 | * @param control The bit map control. |
---|
301 | * @return int The error number (errno). No error if 0. |
---|
302 | */ |
---|
303 | int rtems_rfs_bitmap_close (rtems_rfs_bitmap_control* control); |
---|
304 | |
---|
305 | #endif |
---|