rtems/rfs/rtems-rfs-bitmaps.h

0001 /* SPDX-License-Identifier: BSD-2-Clause */
0002
0003 /**
0004  * @file
0005  *
0006  * @brief RTEMS File Systems Bitmap Routines
0007  *
0008  * @ingroup rtems_rfs
0009  *
0010  * RTEMS File Systems Bitmap Routines.
0011  *
0012  * These functions manage bit maps. A bit map consists of the map of bit
0013  * allocated in a block and a search map where a bit represents 32 actual
0014  * bits. The search map allows for a faster search for an available bit as 32
0015  * search bits can checked in a test.
0016  */
0017
0018 /*
0019  *  COPYRIGHT (c) 2010 Chris Johns <chrisj@rtems.org>
0020  *
0021  * Redistribution and use in source and binary forms, with or without
0022  * modification, are permitted provided that the following conditions
0023  * are met:
0024  * 1. Redistributions of source code must retain the above copyright
0025  *    notice, this list of conditions and the following disclaimer.
0026  * 2. Redistributions in binary form must reproduce the above copyright
0027  *    notice, this list of conditions and the following disclaimer in the
0028  *    documentation and/or other materials provided with the distribution.
0029  *
0030  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
0031  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
0032  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
0033  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
0034  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
0035  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
0036  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
0037  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
0038  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
0039  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
0040  * POSSIBILITY OF SUCH DAMAGE.
0041  */
0042
0043
0044 #if !defined (_RTEMS_RFS_BITMAPS_H_)
0045 #define _RTEMS_RFS_BITMAPS_H_
0046
0047 #include <rtems/rfs/rtems-rfs-buffer.h>
0048 #include <rtems/rfs/rtems-rfs-file-system-fwd.h>
0049 #include <rtems/rfs/rtems-rfs-trace.h>
0050
0051 /**
0052  * Define the way the bits are configured. We can have them configured as clear
0053  * being 0 or clear being 1. This does not effect how masks are defined. A mask
0054  * always has a 1 for set and 0 for clear.
0055  */
0056 #define RTEMS_RFS_BITMAP_CLEAR_ZERO 0
0057
0058 #if RTEMS_RFS_BITMAP_CLEAR_ZERO
0059 /*
0060  * Bit set is a 1 and clear is 0.
0061  */
0062 #define RTEMS_RFS_BITMAP_BIT_CLEAR          0
0063 #define RTEMS_RFS_BITMAP_BIT_SET            1
0064 #define RTEMS_RFS_BITMAP_ELEMENT_SET        (RTEMS_RFS_BITMAP_ELEMENT_FULL_MASK)
0065 #define RTEMS_RFS_BITMAP_ELEMENT_CLEAR      (0)
0066 #define RTEMS_RFS_BITMAP_SET_BITS(_t, _b)   ((_t) | (_b))
0067 #define RTEMS_RFS_BITMAP_CLEAR_BITS(_t, _b) ((_t) & ~(_b))
0068 #define RTEMS_RFS_BITMAP_TEST_BIT(_t, _b)   (((_t) & (1 << (_b))) != 0 ? true : false)
0069 #else
0070 /*
0071  * Bit set is a 0 and clear is 1.
0072  */
0073 #define RTEMS_RFS_BITMAP_BIT_CLEAR          1
0074 #define RTEMS_RFS_BITMAP_BIT_SET            0
0075 #define RTEMS_RFS_BITMAP_ELEMENT_SET        (0)
0076 #define RTEMS_RFS_BITMAP_ELEMENT_CLEAR      (RTEMS_RFS_BITMAP_ELEMENT_FULL_MASK)
0077 #define RTEMS_RFS_BITMAP_SET_BITS(_t, _b)   ((_t) & ~(_b))
0078 #define RTEMS_RFS_BITMAP_CLEAR_BITS(_t, _b) ((_t) | (_b))
0079 #define RTEMS_RFS_BITMAP_TEST_BIT(_t, _b)   (((_t) & (1 << (_b))) == 0 ? true : false)
0080 #endif
0081
0082 /**
0083  * Invert a mask. Masks are always 1 for set and 0 for clear.
0084  */
0085 #define RTEMS_RFS_BITMAP_INVERT_MASK(_mask) (~(_mask))
0086
0087 /**
0088  * This is the full mask of the length of the element. A mask is always a 1 for
0089  * set and 0 for clear. It is not effected by the state of
0090  * RTEMS_RFS_BITMAP_CLEAR_ZERO.
0091  */
0092 #define RTEMS_RFS_BITMAP_ELEMENT_FULL_MASK (0xffffffffUL)
0093
0094 /**
0095  * The bitmap search window. Searches occur around a seed in either direction
0096  * for half the window.
0097  */
0098 #define RTEMS_RFS_BITMAP_SEARCH_WINDOW (rtems_rfs_bitmap_element_bits () * 64)
0099
0100 /**
0101  * A bit in a map.
0102  */
0103 typedef int32_t rtems_rfs_bitmap_bit;
0104
0105 /**
0106  * The basic element of a bitmap. A bitmap is manipulated by elements.
0107  */
0108 typedef uint32_t rtems_rfs_bitmap_element;
0109
0110 /**
0111  * The power of 2 number of bits in the element.
0112  */
0113 #define RTEMS_RFS_ELEMENT_BITS_POWER_2 (5)
0114
0115 /**
0116  * A bitmap or map is an array of bitmap elements.
0117  */
0118 typedef rtems_rfs_bitmap_element* rtems_rfs_bitmap_map;
0119
0120 /**
0121  * The bitmap control is a simple way to manage the various parts of a bitmap.
0122  */
0123 typedef struct rtems_rfs_bitmap_control_s
0124 {
0125   rtems_rfs_buffer_handle* buffer;      //< Handle the to buffer with the bit
0126                                         //map.
0127   rtems_rfs_file_system*   fs;          //< The map's file system.
0128   rtems_rfs_buffer_block   block;       //< The map's block number on disk.
0129   size_t                   size;        //< Number of bits in the map. Passed
0130                                         //to create.
0131   size_t                   free;        //< Number of bits in the map that are
0132                                         //free (clear).
0133   rtems_rfs_bitmap_map     search_bits; //< The search bit map memory.
0134 } rtems_rfs_bitmap_control;
0135
0136 /**
0137  * Return the number of bits for the number of bytes provided.
0138  */
0139 #define rtems_rfs_bitmap_numof_bits(_bytes) (8 * (_bytes))
0140
0141 /**
0142  * Return the number of bits for the number of bytes provided.  The search
0143  * element and the element must have the same number of bits.
0144  */
0145 #define rtems_rfs_bitmap_element_bits() \
0146   rtems_rfs_bitmap_numof_bits (sizeof (rtems_rfs_bitmap_element))
0147
0148 /**
0149  * Return the number of bits a search element covers.
0150  */
0151 #define rtems_rfs_bitmap_search_element_bits() \
0152   (rtems_rfs_bitmap_element_bits() * rtems_rfs_bitmap_element_bits())
0153
0154 /**
0155  * Return the number of elements for a given number of bits.
0156  */
0157 #define rtems_rfs_bitmap_elements(_bits) \
0158   ((((_bits) - 1) / rtems_rfs_bitmap_element_bits()) + 1)
0159
0160 /**
0161  * Release the bitmap buffer back to the buffer pool or cache.
0162  */
0163 #define rtems_rfs_bitmap_release_buffer(_fs, _bm)    \
0164   rtems_rfs_buffer_handle_release (_fs, (_bm)->buffer)
0165
0166 /**
0167  * Return the element index for a given bit. We use a macro to hide any
0168  * implementation assuptions. Typically this would be calculated by dividing
0169  * the bit index by the number of bits in an element. Given we have a power of
0170  * 2 as the number of bits we can avoid the division by using a shift. A good
0171  * compiler should figure this out but I would rather enforce this than rely on
0172  * the specific backend of a compiler to do the right thing.
0173  */
0174 #define rtems_rfs_bitmap_map_index(_b) \
0175   ((_b) >> RTEMS_RFS_ELEMENT_BITS_POWER_2)
0176
0177 /**
0178  * Return the bit offset for a given bit in an element in a map. See @ref
0179  * rtems_rfs_bitmap_map_index for a detailed reason why.
0180  */
0181 #define rtems_rfs_bitmap_map_offset(_b) \
0182   ((_b) & ((1 << RTEMS_RFS_ELEMENT_BITS_POWER_2) - 1))
0183
0184 /**
0185  * Return the size of the bitmap.
0186  */
0187 #define rtems_rfs_bitmap_map_size(_c) ((_c)->size)
0188
0189 /**
0190  * Return the number of free bits in the bitmap.
0191  */
0192 #define rtems_rfs_bitmap_map_free(_c) ((_c)->free)
0193
0194 /**
0195  * Return the buffer handle.
0196  */
0197 #define rtems_rfs_bitmap_map_handle(_c) ((_c)->buffer)
0198
0199 /**
0200  * Return the bitmap map block.
0201  */
0202 #define rtems_rfs_bitmap_map_block(_c) ((_c)->block)
0203
0204 /**
0205  * Create a bit mask with the specified number of bits up to an element's
0206  * size. The mask is aligned to bit 0 of the element.
0207  *
0208  * @param[in] size is the number of bits in the mask.
0209  *
0210  * @return The mask of the argument size number of bits.
0211  */
0212 rtems_rfs_bitmap_element rtems_rfs_bitmap_mask (unsigned int size);
0213
0214 /**
0215  * Create a bit mask section. A mask section is a mask that is not aligned to
0216  * an end of the element.
0217  *
0218  * @param[in] start is the first bit of the mask numbered from 0.
0219  * @param[in] end is the end bit of the mask numbered from 0.
0220  *
0221  * @return Mask section as defined by the start and end arguments.
0222  */
0223 rtems_rfs_bitmap_element rtems_rfs_bitmap_mask_section (unsigned int start,
0224                                                         unsigned int end);
0225
0226 /**
0227  * Set a bit in a map and if all the bits are set, set the search map bit as
0228  * well.
0229  *
0230  * @param[in] control is the control for the map.
0231  * @param[in] bit is the bit in the map to set.
0232  *
0233  * @retval 0 Successful operation.
0234  * @retval error_code An error occurred.
0235  */
0236 int rtems_rfs_bitmap_map_set (rtems_rfs_bitmap_control* control,
0237                               rtems_rfs_bitmap_bit      bit);
0238
0239 /**
0240  * Clear a bit in a map and make sure the search map bit is clear so a search
0241  * will find this bit available.
0242  *
0243  * @param[in] control is the control for the map.
0244  * @param[in] bit is the bit in the map to clear.
0245  *
0246  * @retval 0 Successful operation.
0247  * @retval error_code An error occurred.
0248  */
0249 int rtems_rfs_bitmap_map_clear (rtems_rfs_bitmap_control* control,
0250                                 rtems_rfs_bitmap_bit      bit);
0251
0252 /**
0253  * Test a bit in the map.
0254  *
0255  * @param[in] control is the bitmap control.
0256  * @param[in] bit is the bit to test.
0257  * @param[in] state is the state of the bit if no error is returned.
0258  *
0259  * @retval 0 Successful operation.
0260  * @retval error_code An error occurred.
0261  */
0262 int
0263 rtems_rfs_bitmap_map_test (rtems_rfs_bitmap_control* control,
0264                            rtems_rfs_bitmap_bit      bit,
0265                            bool*                     state);
0266
0267 /**
0268  * Set all bits in the bitmap and set the dirty bit.
0269  *
0270  * @param[in] control is the bitmap control.
0271  *
0272  * @retval 0 Successful operation.
0273  * @retval error_code An error occurred.
0274  */
0275 int rtems_rfs_bitmap_map_set_all (rtems_rfs_bitmap_control* control);
0276
0277 /**
0278  * Clear all bits in the bitmap and set the dirty bit.
0279  *
0280  * @param[in] control is the bitmap control.
0281  *
0282  * @retval 0 Successful operation.
0283  * @retval error_code An error occurred.
0284  */
0285 int rtems_rfs_bitmap_map_clear_all (rtems_rfs_bitmap_control* control);
0286
0287 /**
0288  * Find a free bit searching from the seed up and down until found. The search
0289  * is performing by moving up from the seed for the window distance then to
0290  * search down from the seed for the window distance. This is repeated out
0291  * from the seed for each window until a free bit is found. The search is
0292  * performed by checking the search map to see if the map has a free bit.
0293  *
0294  * @param[in] control is the map control.
0295  * @param[in] seed is the bit to search out from.
0296  * @param[out] allocate A bit was allocated.
0297  * @param[out] bit will contain the bit found free if true is returned.
0298  *
0299  * @retval 0 Successful operation.
0300  * @retval error_code An error occurred.
0301  */
0302 int rtems_rfs_bitmap_map_alloc (rtems_rfs_bitmap_control* control,
0303                                 rtems_rfs_bitmap_bit      seed,
0304                                 bool*                     allocate,
0305                                 rtems_rfs_bitmap_bit*     bit);
0306
0307 /**
0308  * Create a search bit map from the actual bit map.
0309  *
0310  * @param[in] control is the map control.
0311  *
0312  * @retval 0 Successful operation.
0313  * @retval error_code An error occurred.
0314  */
0315 int rtems_rfs_bitmap_create_search (rtems_rfs_bitmap_control* control);
0316
0317 /**
0318  * Open a bitmap control with a map and search map.
0319  *
0320  * @param[in] control is the map control.
0321  * @param[in] fs is the file system data.
0322  * @param[in]  buffer is a pointer to the buffer handle the map is
0323  *           stored in.
0324  * @param[in] size is the number of bits in the map.
0325  *
0326  * @retval 0 Successful operation.
0327  * @retval error_code An error occurred.
0328  */
0329 int rtems_rfs_bitmap_open (rtems_rfs_bitmap_control* control,
0330                            rtems_rfs_file_system*    fs,
0331                            rtems_rfs_buffer_handle*  buffer,
0332                            size_t                    size,
0333                            rtems_rfs_buffer_block    block);
0334
0335 /**
0336  * Close a bitmap.
0337  *
0338  * @param[in] control is the bit map control.
0339  *
0340  * @retval 0 Successful operation.
0341  * @retval error_code An error occurred.
0342  */
0343 int rtems_rfs_bitmap_close (rtems_rfs_bitmap_control* control);
0344
0345 #endif