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

Fan Deng enetor at gmail.com
Thu Oct 12 17:05:46 UTC 2017


Hi Chris,

Based on my understanding, the patch in your email is different:

1) rtems_rfs_bitmap_map_set:
By changing negating the if condition, the updated logic only modifies the
element map[index] when the original value of map[index] is
RTEMS_RFS_BITMAP_ELEMENT_SET.

This is not quite right, as we are explicitly updating the 'offset' bit in
map[index]. That bit should be updated regardless.

2) rtems_rfs_bitmap_map_clear:
Same problem, whether we modify map[index] should not depend on if
map[index] == RTEMS_RFS_BITMAP_ELEMENT_SET.

I believe my patch corrects the logic flaw and is the right fix. Please let
me know if you have any further questions, and I will be happy to explain
in detail.

Thanks,
Fan

On Thu, Oct 12, 2017 at 9:48 AM, Chris Johns <chrisj at rtems.org> wrote:

> 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);
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20171012/691f638c/attachment-0002.html>


More information about the devel mailing list