[PATCH] Fixes bitmap allocation accounting logic in rtems-rfs-bitmaps.c

[Chris Johns]

Hi,

Many thanks for post the patches. The other patches look fine. I am wondering is this is equivalent to what you have?

diff --git a/cpukit/libfs/src/rfs/rtems-rfs-bitmaps.c b/cpukit/libfs/src/rfs/rtems-rfs-bitmaps.c
index 15a9050133..d14082691a 100644
--- a/cpukit/libfs/src/rfs/rtems-rfs-bitmaps.c
+++ b/cpukit/libfs/src/rfs/rtems-rfs-bitmaps.c
@@ -196,9 +196,9 @@ rtems_rfs_bitmap_map_set (rtems_rfs_bitmap_control* control,
   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))
+  if (!rtems_rfs_bitmap_match(map[index], RTEMS_RFS_BITMAP_ELEMENT_SET))
   {
+    map[index] = rtems_rfs_bitmap_set (map[index], 1 << offset);
     bit = index;
     index  = rtems_rfs_bitmap_map_index (bit);
     offset = rtems_rfs_bitmap_map_offset (bit);
@@ -226,6 +226,8 @@ rtems_rfs_bitmap_map_clear (rtems_rfs_bitmap_control* control,
   search_map        = control->search_bits;
   index             = rtems_rfs_bitmap_map_index (bit);
   offset            = rtems_rfs_bitmap_map_offset (bit);
+  if (rtems_rfs_bitmap_match(map[index], RTEMS_RFS_BITMAP_ELEMENT_SET))
+  {
     map[index]        = rtems_rfs_bitmap_clear (map[index], 1 << offset);
     bit               = index;
     index             = rtems_rfs_bitmap_map_index (bit);
@@ -233,6 +235,7 @@ rtems_rfs_bitmap_map_clear (rtems_rfs_bitmap_control* control,
     search_map[index] = rtems_rfs_bitmap_clear (search_map[index], 1 << offset);
     rtems_rfs_buffer_mark_dirty (control->buffer);
     control->free++;
+  }
   return 0;
 }
 
Chris

On 10/10/17 4:28 pm, Fan Deng wrote:
> The bitmap allocation accounting logic in rtems-rfs-bitmaps.c is flawed
> around control->free. Specifically:
> 
> In rtems_rfs_bitmap_map_set():
> control->free is only decremented when its corresponding search bit is
> toggled. This is wrong and will miss on average 31/32 set updates.
> 
> In rtems_rfs_bitmap_map_clear():
> control->free is incremented unconditionally.
> 
> The correct behavior is:
> When updating the map, check if the bit is already set/clear. Only update
> control->free when the bit is toggled.
> 
> This change enforced the correct behavior.
> 
> Tested by inspecting the internal data structure.
> ---
>  cpukit/libfs/src/rfs/rtems-rfs-bitmaps.c | 40 +++++++++++++++++++++-----------
>  1 file changed, 26 insertions(+), 14 deletions(-)
> 
> diff --git a/cpukit/libfs/src/rfs/rtems-rfs-bitmaps.c b/cpukit/libfs/src/rfs/rtems-rfs-bitmaps.c
> index 15a9050133..c0c6921db1 100644
> --- a/cpukit/libfs/src/rfs/rtems-rfs-bitmaps.c
> +++ b/cpukit/libfs/src/rfs/rtems-rfs-bitmaps.c
> @@ -183,11 +183,12 @@ 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_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;
> @@ -196,15 +197,20 @@ rtems_rfs_bitmap_map_set (rtems_rfs_bitmap_control* control,
>    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);
> +  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);
> -    control->free--;
> -    rtems_rfs_buffer_mark_dirty (control->buffer);
>    }
>    return 0;
>  }
> @@ -213,11 +219,12 @@ 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_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;
> @@ -226,7 +233,12 @@ rtems_rfs_bitmap_map_clear (rtems_rfs_bitmap_control* control,
>    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);
> +  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);
>