diff options
Diffstat (limited to 'cpukit/libfs/src/rfs/rtems-rfs-bitmaps.c')
| -rw-r--r-- | cpukit/libfs/src/rfs/rtems-rfs-bitmaps.c | 642 |
1 files changed, 642 insertions, 0 deletions
diff --git a/cpukit/libfs/src/rfs/rtems-rfs-bitmaps.c b/cpukit/libfs/src/rfs/rtems-rfs-bitmaps.c new file mode 100644 index 0000000000..4de86342b0 --- /dev/null +++ b/cpukit/libfs/src/rfs/rtems-rfs-bitmaps.c @@ -0,0 +1,642 @@ +/* + * COPYRIGHT (c) 2010 Chris Johns <chrisj@rtems.org> + * + * The license and distribution terms for this file may be + * found in the file LICENSE in this distribution or at + * http://www.rtems.com/license/LICENSE. + * + * $Id$ + */ +/** + * @file + * + * @ingroup rtems-rfs + * + * RTEMS File Systems Bitmap Routines. + * + * These functions manage bit maps. A bit map consists of the map of bit + * allocated in a block and a search map where a bit represents 32 actual + * bits. The search map allows for a faster search for an available bit as 32 + * search bits can checked in a test. + */ + +/** + * Set to 1 to enable warnings when developing. + */ +#define RTEMS_RFS_BITMAP_WARNINGS 0 + +#if RTEMS_RFS_BITMAP_WARNINGS +#include <stdio.h> +#endif +#include <stdlib.h> +#include <rtems/rfs/rtems-rfs-bitmaps.h> + +/** + * Test a bit in an element. If set return true else return false. + * + * @param target The target to test the bit in. + * @param bit The bit to test. + * @retval true The bit is set. + * @retval false The bit is clear. + */ +static bool +rtems_rfs_bitmap_test (rtems_rfs_bitmap_element target, + rtems_rfs_bitmap_bit bit) +{ + return RTEMS_RFS_BITMAP_TEST_BIT (target, bit); +} + +/** + * Set the bits in the element. Bits not set in the bit argument are left + * unchanged. + * + * @param target The target element bits are set. + * @param bits The bits in the target to set. A 1 in the bits will set the + * same bit in the target. + */ +static rtems_rfs_bitmap_element +rtems_rfs_bitmap_set (rtems_rfs_bitmap_element target, + rtems_rfs_bitmap_element bits) +{ + return RTEMS_RFS_BITMAP_SET_BITS (target, bits); +} + +/** + * Clear the bits in the element. Bits not set in the bit argument are left + * unchanged. + * + * @param target The target element to clear the bits in. + * @param bits The bits in the target to clear. A 1 in the bits will clear the + * bit in the target. + */ +static rtems_rfs_bitmap_element +rtems_rfs_bitmap_clear (rtems_rfs_bitmap_element target, + rtems_rfs_bitmap_element bits) +{ + return RTEMS_RFS_BITMAP_CLEAR_BITS (target, bits); +} + +/** + * Merge the bits in 2 variables based on the mask. A set bit in the mask will + * merge the bits from bits1 and a clear bit will merge the bits from bits2. + * The mask is always defined as 1 being set and 0 being clear. + */ +static rtems_rfs_bitmap_element +rtems_rfs_bitmap_merge (rtems_rfs_bitmap_element bits1, + rtems_rfs_bitmap_element bits2, + rtems_rfs_bitmap_element mask) +{ + /* + * Use the normal bit operators because we do not change the bits just merge + * the 2 separate parts. + */ + bits1 &= mask; + bits2 &= RTEMS_RFS_BITMAP_INVERT_MASK (mask); + return bits1 | bits2; +} + +/** + * Match the bits of 2 elements and return true if they match else return + * false. + * + * @param bits1 One set of bits to match. + * @param bits2 The second set of bits to match. + * @retval true The bits match. + * @retval false The bits do not match. + */ +static bool +rtems_rfs_bitmap_match (rtems_rfs_bitmap_element bits1, + rtems_rfs_bitmap_element bits2) +{ + return bits1 ^ bits2 ? false : true; +} + +#if RTEMS_NOT_USED_BUT_KEPT +/** + * Match the bits of 2 elements within the mask and return true if they match + * else return false. + * + * @param mask The mask over which the match occurs. A 1 is a valid mask bit. + * @param bits1 One set of bits to match. + * @param bits2 The second set of bits to match. + * @retval true The bits match. + * @retval false The bits do not match. + */ +static bool +rtems_rfs_bitmap_match_masked (rtems_rfs_bitmap_element mask, + rtems_rfs_bitmap_element bits1, + rtems_rfs_bitmap_element bits2) +{ + return (bits1 ^ bits2) & mask ? false : true; +} +#endif + +/** + * Return the map after loading from disk if not already loaded. + * + * @param control The bitmap control. + * @param rtems_rfs_bitmap_map* Pointer to the bitmap map data if no error. + * @return int The error number (errno). No error if 0. + */ +static int +rtems_rfs_bitmap_load_map (rtems_rfs_bitmap_control* control, + rtems_rfs_bitmap_map* map) +{ + int rc; + + if (!control->buffer) + return ENXIO; + + *map = NULL; + + rc = rtems_rfs_buffer_handle_request (control->fs, + control->buffer, + control->block, + true); + if (rc) + return rc; + + *map = rtems_rfs_buffer_data (control->buffer); + return 0; +} + +rtems_rfs_bitmap_element +rtems_rfs_bitmap_mask (unsigned int size) +{ + rtems_rfs_bitmap_element mask = RTEMS_RFS_BITMAP_ELEMENT_FULL_MASK; + mask >>= (rtems_rfs_bitmap_element_bits () - size); + return mask; +} + +rtems_rfs_bitmap_element +rtems_rfs_bitmap_mask_section (unsigned int start, unsigned int end) +{ + rtems_rfs_bitmap_element mask = 0; + if (end > start) + mask = rtems_rfs_bitmap_mask (end - start) << start; + return mask; +} + +int +rtems_rfs_bitmap_map_set (rtems_rfs_bitmap_control* control, + rtems_rfs_bitmap_bit bit) +{ + rtems_rfs_bitmap_map map; + rtems_rfs_bitmap_map search_map; + int index; + int offset; + int rc; + rc = rtems_rfs_bitmap_load_map (control, &map); + if (rc > 0) + return rc; + if (bit >= control->size) + return EINVAL; + search_map = control->search_bits; + index = rtems_rfs_bitmap_map_index (bit); + offset = rtems_rfs_bitmap_map_offset (bit); + map[index] = rtems_rfs_bitmap_set (map[index], 1 << offset); + if (rtems_rfs_bitmap_match(map[index], RTEMS_RFS_BITMAP_ELEMENT_SET)) + { + bit = index; + index = rtems_rfs_bitmap_map_index (bit); + offset = rtems_rfs_bitmap_map_offset (bit); + search_map[index] = rtems_rfs_bitmap_set (search_map[index], 1 << offset); + control->free--; + rtems_rfs_buffer_mark_dirty (control->buffer); + } + return 0; +} + +int +rtems_rfs_bitmap_map_clear (rtems_rfs_bitmap_control* control, + rtems_rfs_bitmap_bit bit) +{ + rtems_rfs_bitmap_map map; + rtems_rfs_bitmap_map search_map; + int index; + int offset; + int rc; + rc = rtems_rfs_bitmap_load_map (control, &map); + if (rc > 0) + return rc; + if (bit >= control->size) + return EINVAL; + search_map = control->search_bits; + index = rtems_rfs_bitmap_map_index (bit); + offset = rtems_rfs_bitmap_map_offset (bit); + map[index] = rtems_rfs_bitmap_clear (map[index], 1 << offset); + bit = index; + index = rtems_rfs_bitmap_map_index (bit); + offset = rtems_rfs_bitmap_map_offset(bit); + search_map[index] = rtems_rfs_bitmap_clear (search_map[index], 1 << offset); + rtems_rfs_buffer_mark_dirty (control->buffer); + control->free++; + return 0; +} + +int +rtems_rfs_bitmap_map_test (rtems_rfs_bitmap_control* control, + rtems_rfs_bitmap_bit bit, + bool* state) +{ + rtems_rfs_bitmap_map map; + int index; + int rc; + rc = rtems_rfs_bitmap_load_map (control, &map); + if (rc > 0) + return rc; + if (bit >= control->size) + return EINVAL; + index = rtems_rfs_bitmap_map_index (bit); + *state = rtems_rfs_bitmap_test (map[index], bit); + return 0; +} + +int +rtems_rfs_bitmap_map_set_all (rtems_rfs_bitmap_control* control) +{ + rtems_rfs_bitmap_map map; + size_t elements; + int e; + int rc; + + rc = rtems_rfs_bitmap_load_map (control, &map); + if (rc > 0) + return rc; + + elements = rtems_rfs_bitmap_elements (control->size); + + control->free = 0; + + for (e = 0; e < elements; e++) + map[e] = RTEMS_RFS_BITMAP_ELEMENT_SET; + + elements = rtems_rfs_bitmap_elements (elements); + + for (e = 0; e < elements; e++) + control->search_bits[e] = RTEMS_RFS_BITMAP_ELEMENT_SET; + + rtems_rfs_buffer_mark_dirty (control->buffer); + + return 0; +} + +int +rtems_rfs_bitmap_map_clear_all (rtems_rfs_bitmap_control* control) +{ + rtems_rfs_bitmap_map map; + rtems_rfs_bitmap_bit last_search_bit; + size_t elements; + int e; + int rc; + + rc = rtems_rfs_bitmap_load_map (control, &map); + if (rc > 0) + return rc; + + elements = rtems_rfs_bitmap_elements (control->size); + + control->free = elements; + + for (e = 0; e < elements; e++) + map[e] = RTEMS_RFS_BITMAP_ELEMENT_CLEAR; + + /* + * Set the un-mapped bits in the last search element so the available logic + * works. + */ + last_search_bit = rtems_rfs_bitmap_map_offset (elements); + + if (last_search_bit == 0) + last_search_bit = rtems_rfs_bitmap_element_bits (); + + elements = rtems_rfs_bitmap_elements (elements); + + for (e = 0; e < (elements - 1); e++) + control->search_bits[e] = RTEMS_RFS_BITMAP_ELEMENT_CLEAR; + + control->search_bits[elements - 1] = + rtems_rfs_bitmap_merge (RTEMS_RFS_BITMAP_ELEMENT_CLEAR, + RTEMS_RFS_BITMAP_ELEMENT_SET, + rtems_rfs_bitmap_mask (last_search_bit)); + + rtems_rfs_buffer_mark_dirty (control->buffer); + + return 0; +} + +static int +rtems_rfs_search_map_for_clear_bit (rtems_rfs_bitmap_control* control, + rtems_rfs_bitmap_bit* bit, + bool* found, + size_t window, + int direction) +{ + rtems_rfs_bitmap_map map; + rtems_rfs_bitmap_bit test_bit; + rtems_rfs_bitmap_bit end_bit; + rtems_rfs_bitmap_element* search_bits; + int search_index; + int search_offset; + rtems_rfs_bitmap_element* map_bits; + int map_index; + int map_offset; + int rc; + + *found = false; + + /* + * Load the bitmap. + */ + rc = rtems_rfs_bitmap_load_map (control, &map); + if (rc > 0) + return rc; + + /* + * Calculate the bit we are testing plus the end point we search over. + */ + test_bit = *bit; + end_bit = test_bit + (window * direction); + + if (end_bit < 0) + end_bit = 0; + else if (end_bit >= control->size) + end_bit = control->size - 1; + + map_index = rtems_rfs_bitmap_map_index (test_bit); + map_offset = rtems_rfs_bitmap_map_offset (test_bit); + search_index = rtems_rfs_bitmap_map_index (map_index); + search_offset = rtems_rfs_bitmap_map_offset (map_index); + + search_bits = &control->search_bits[search_index]; + map_bits = &map[map_index]; + + /* + * Check each bit from the search map offset for a clear bit. + */ + do + { + /* + * If any bit is clear find that bit and then search the map element. If + * all bits are set there are no map bits so move to the next search + * element. + */ + if (!rtems_rfs_bitmap_match (*search_bits, RTEMS_RFS_BITMAP_ELEMENT_SET)) + { + while ((search_offset >= 0) + && (search_offset < rtems_rfs_bitmap_element_bits ())) + { + if (!rtems_rfs_bitmap_test (*search_bits, search_offset)) + { + /* + * Find the clear bit in the map. Update the search map and map if + * found. We may find none are spare if searching up from the seed. + */ + while ((map_offset >= 0) + && (map_offset < rtems_rfs_bitmap_element_bits ())) + { + if (!rtems_rfs_bitmap_test (*map_bits, map_offset)) + { + *map_bits = rtems_rfs_bitmap_set (*map_bits, 1 << map_offset); + if (rtems_rfs_bitmap_match(*map_bits, + RTEMS_RFS_BITMAP_ELEMENT_SET)) + *search_bits = rtems_rfs_bitmap_set (*search_bits, + 1 << search_offset); + control->free--; + *bit = test_bit; + *found = true; + rtems_rfs_buffer_mark_dirty (control->buffer); + return 0; + } + + if (test_bit == end_bit) + break; + + map_offset += direction; + test_bit += direction; + } + } + + map_bits += direction; + map_index += direction; + map_offset = direction > 0 ? 0 : rtems_rfs_bitmap_element_bits () - 1; + + test_bit = (map_index * rtems_rfs_bitmap_element_bits ()) + map_offset; + + search_offset += direction; + + if (((direction < 0) && (test_bit <= end_bit)) + || ((direction > 0) && (test_bit >= end_bit))) + break; + } + } + else + { + /* + * Move to the next search element. We need to determine the number of + * bits in the search offset that are being skipped so the map bits + * pointer can be updated. If we are moving down and we have a search + * offset of 0 then the search map adjustment is to the top bit of the + * pervious search bit's value. + * + * Align test_bit either up or down depending on the direction to next 32 + * bit boundary. + */ + rtems_rfs_bitmap_bit bits_skipped; + test_bit &= ~((1 << RTEMS_RFS_ELEMENT_BITS_POWER_2) - 1); + if (direction > 0) + { + bits_skipped = rtems_rfs_bitmap_element_bits () - search_offset; + test_bit += bits_skipped * rtems_rfs_bitmap_element_bits (); + map_offset = 0; + } + else + { + bits_skipped = search_offset + 1; + /* + * Need to remove 1 for the rounding up. The above rounds down and + * adds 1. Remember the logic is for subtraction. + */ + test_bit -= ((bits_skipped - 1) * rtems_rfs_bitmap_element_bits ()) + 1; + map_offset = rtems_rfs_bitmap_element_bits () - 1; + } + map_bits += direction * bits_skipped; + map_index += direction * bits_skipped; + } + + search_bits += direction; + search_offset = direction > 0 ? 0 : rtems_rfs_bitmap_element_bits () - 1; + } + while (((direction < 0) && (test_bit >= end_bit)) + || ((direction > 0) && (test_bit <= end_bit))); + + return 0; +} + +int +rtems_rfs_bitmap_map_alloc (rtems_rfs_bitmap_control* control, + rtems_rfs_bitmap_bit seed, + bool* allocated, + rtems_rfs_bitmap_bit* bit) +{ + rtems_rfs_bitmap_bit upper_seed; + rtems_rfs_bitmap_bit lower_seed; + rtems_rfs_bitmap_bit window; /* may become a parameter */ + int rc = 0; + + /* + * By default we assume the allocation failed. + */ + *allocated = false; + + /* + * The window is the number of bits we search over in either direction each + * time. + */ + window = RTEMS_RFS_BITMAP_SEARCH_WINDOW; + + /* + * Start from the seed and move in either direction. Search in window amounts + * of bits from the original seed above then below. That is search from the + * seed up then from the seed down a window number of bits, then repeat the + * process from the window distance from the seed, again above then + * below. Keep moving out until all bits have been searched. + */ + upper_seed = seed; + lower_seed = seed; + + /* + * If the upper and lower seed values have reached the limits of the bitmap + * we have searched all of the map. The seed may not be aligned to a window + * boundary so we may need to search a partial window and this may also not + * be balanced for the upper or lower seeds. We move to the limits, search + * then return false if no clear bits are found. + */ + while (((upper_seed >= 0) && (upper_seed < control->size)) + || ((lower_seed >= 0) && (lower_seed < control->size))) + { + /* + * Search up first so bits allocated in succession are grouped together. + */ + if (upper_seed < control->size) + { + *bit = upper_seed; + rc = rtems_rfs_search_map_for_clear_bit (control, bit, allocated, + window, 1); + if ((rc > 0) || *allocated) + break; + } + + if (lower_seed >= 0) + { + *bit = lower_seed; + rc = rtems_rfs_search_map_for_clear_bit (control, bit, allocated, + window, -1); + if ((rc > 0) || *allocated) + break; + } + + /* + * Do not bound the limits at the edges of the map. Do not update if an + * edge has been passed. + */ + if (upper_seed < control->size) + upper_seed += window; + if (lower_seed >= 0) + lower_seed -= window; + } + + return 0; +} + +int +rtems_rfs_bitmap_create_search (rtems_rfs_bitmap_control* control) +{ + rtems_rfs_bitmap_map search_map; + rtems_rfs_bitmap_map map; + size_t size; + rtems_rfs_bitmap_bit bit; + int rc; + + rc = rtems_rfs_bitmap_load_map (control, &map); + if (rc > 0) + return rc; + + control->free = 0; + search_map = control->search_bits; + size = control->size; + bit = 0; + + *search_map = RTEMS_RFS_BITMAP_ELEMENT_CLEAR; + while (size) + { + rtems_rfs_bitmap_element bits; + int available; + if (size < rtems_rfs_bitmap_element_bits ()) + { + bits = rtems_rfs_bitmap_merge (*map, + RTEMS_RFS_BITMAP_ELEMENT_SET, + rtems_rfs_bitmap_mask_section (0, size)); + available = size; + } + else + { + bits = *map; + available = rtems_rfs_bitmap_element_bits (); + } + + if (rtems_rfs_bitmap_match (bits, RTEMS_RFS_BITMAP_ELEMENT_SET)) + rtems_rfs_bitmap_set (*search_map, bit); + else + { + int b; + for (b = 0; b < available; b++) + if (!rtems_rfs_bitmap_test (bits, b)) + control->free++; + } + + size -= available; + + if (bit == rtems_rfs_bitmap_element_bits ()) + { + bit = 0; + search_map++; + *search_map = RTEMS_RFS_BITMAP_ELEMENT_CLEAR; + } + else + bit++; + map++; + } + + return 0; +} + +int +rtems_rfs_bitmap_open (rtems_rfs_bitmap_control* control, + rtems_rfs_file_system* fs, + rtems_rfs_buffer_handle* buffer, + size_t size, + rtems_rfs_buffer_block block) +{ + size_t elements = rtems_rfs_bitmap_elements (size); + + control->buffer = buffer; + control->fs = fs; + control->block = block; + control->size = size; + + elements = rtems_rfs_bitmap_elements (elements); + control->search_bits = malloc (elements * sizeof (rtems_rfs_bitmap_element)); + + if (!control->search_bits) + return ENOMEM; + + return rtems_rfs_bitmap_create_search (control); +} + +int +rtems_rfs_bitmap_close (rtems_rfs_bitmap_control* control) +{ + free (control->search_bits); + return 0; +} |