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

[Fan Deng]

Thanks Chris!

First of all let's make sure a few points are clarified:

1) What should rtems_rfs_bitmap_map_set(control, bit) do?
- 'control' is a handle to the bitmap.
- 'bit' is the offset of the bit to set in the bitmap. 'bit' should be in
the range of [0, control->size - 1].

2) How does the bitmap store bits?
By storing bits in an array of rtems_rfs_bitmap_element objects.
Each rtems_rfs_bitmap_element is 32bit. So the number of elements is
control->size / 32.

3) What is map[index]?
'index' is calculated as 'bit / 32' and is the offset into the block buffer
of the element that contains the 'bit'. So map[index] is the value of the
element that contains the 'bit'.

4) What is 'offset'?
'offset' is calculated as 'bit % 32'. It locates the 'bit' in the element
that contains it.

5) What is RTEMS_RFS_BITMAP_ELEMENT_SET
This is a constant. If map[index] == RTEMS_RFS_BITMAP_ELEMENT_SET, all bits
in this element (map[index]) are set. It is used to check that condition
and *update the search map*.

Now let's see what your change does:

 -  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))
    {

Your change:
1. First updates map[index] to set the bit.
2. Compares the updated map[index] with RTEMS_RFS_BITMAP_ELEMENT_SET. Note
this:
    - *DOES NOT* check whether the original bit was set.
    - *DOES NOT* have a way to check if the bit was previously set, as
map[index] has already been overwritten.
    - *DOES* check whether all bits in map[index] are set.

Please let me know if you agree with my assertions in #2 above. Note the
name of "RTEMS_RFS_BITMAP_ELEMENT_SET" is slightly misleading. See my
points #5 for a clarification.

Thanks,
Fan

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

> On 12/10/17 10:05 am, Fan Deng wrote:
> > Hi Chris,
> >
>
> Thanks for quick response.
>
> > 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.
>
> Your change has:
>
>  -  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;
>
> The change gets a copy of the uint32_t value from the map and then updates
> the
> map setting the bit. The change then checks to see if the original bit in
> the
> map is set (match returns true) and if set you exit the function. I see
> this
> being the same as the code in my patch where I only proceed to do anything
> if
> the bit is not set in the map:
>
>  -  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))
>     {
>
> If the bit is not set you enter the code to handle a map bit being set.
> You have:
>
>  +  control->free--;
>  +  rtems_rfs_buffer_mark_dirty (control->buffer);
>     if (rtems_rfs_bitmap_match(map[index], RTEMS_RFS_BITMAP_ELEMENT_SET))
>     {
>
> Given you have set the `map[index]` earlier the if test will always pass
> and I
> suspect the compiler will know this and dead code eliminate it.
>
> > This is not quite right, as we are explicitly updating the 'offset' bit
> in
> > map[index]. That bit should be updated regardless.
>
> Why update the bit if it is already set? I seem to be missing something
> here.
> The map is just an array of 32bit unsigned ints.
>
> >
> > 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.
>
> Sure, once we agree on the set the clear should fall out of it.
>
> Chris
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20171012/21452c23/attachment-0002.html>