LXR 6.1/​cpukit/​libfs/​src/​rfs/​rtems-rfs-bitmaps.c	Source navigation Diff markup Identifier search General search
	Version: 6.1 Revert   Change

File indexing completed on 2025-05-11 08:24:18

 /* SPDX-License-Identifier: BSD-2-Clause */
 
 /**
  * @file
  *
  * @ingroup rtems_rfs
  *
  * @brief 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.
  */
 
 /*
  *  COPYRIGHT (c) 2010 Chris Johns <chrisj@rtems.org>
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  * POSSIBILITY OF SUCH DAMAGE.
  */
 
 #ifdef HAVE_CONFIG_H
 #include "config.h"
 #endif
 
 /**
  * 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>
 
 #define rtems_rfs_bitmap_check(_c, _sm) \
    _Assert(_sm >= _c->search_bits && \
            _sm < (_c->search_bits + \
              rtems_rfs_bitmap_elements(rtems_rfs_bitmap_elements(_c->size))))
 
 
 /**
  * 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;
   rtems_rfs_bitmap_element element;
 
   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);
   element    = map[index];
   map[index] = rtems_rfs_bitmap_set (element, 1 << offset);
 
   /*
    * If the element does not change, the bit was already set. There will be no
    * further action to take.
    */
   if (rtems_rfs_bitmap_match(element, map[index]))
       return 0;
 
   control->free--;
 
   rtems_rfs_buffer_mark_dirty (control->buffer);
   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);
     rtems_rfs_bitmap_check(control, &search_map[index]);
   }
 
   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;
   rtems_rfs_bitmap_element element;
 
   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);
   element    = map[index];
   map[index] = rtems_rfs_bitmap_clear (element, 1 << offset);
 
   /*
    * If the element does not change, the bit was already clear. There will be
    * no further action to take.
    */
   if (rtems_rfs_bitmap_match(element, map[index]))
       return 0;
 
   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_bitmap_check(control, &search_map[index]);
   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 = control->size;
 
   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;
 
   rtems_rfs_bitmap_check(control, search_map);
   *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;
 
     /* Iterate from 0 to 1 less than the number of bits in an element */
     if (bit == (rtems_rfs_bitmap_element_bits () - 1))
     {
       bit = 0;
       if (size > 0)
       {
         search_map++;
         rtems_rfs_bitmap_check(control, 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;
 }

This page was automatically generated by the 2.3.7 LXR engine. The LXR team