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

[Fan Deng]

Yes the physical state can vary depending on the configuration of the RFS.
But that is not my point here.

Let's see an example:

Assuming
- set = physical 1, so RTEMS_RFS_BITMAP_ELEMENT_SET = UINT32_MAX
- map[index]=0b1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111
1111 1111 1111 1111 1110   (only the bit at offset=0 is clear)
- calling rtems_rfs_bitmap_map_set with the bit: index=0 offset=1

In rtems_rfs_bitmap_map_set()
- The if condition rtems_rfs_bitmap_match(map[index],
RTEMS_RFS_BITMAP_ELEMENT_SET) is *false*
- the following if body executes:
    map[index] = rtems_rfs_bitmap_set (map[index], 1 << offset);   //
map[index] *remains the same* because the bit at offset=1 was set before
the call.
    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--;         // *WRONG, because map[index] did not change.*
    rtems_rfs_buffer_mark_dirty (control->buffer);  // UNNECESSARY, because
map[index] did not change.



On Thu, Oct 12, 2017 at 12:19 PM, Chris Johns <chrisj at rtems.org> wrote:

> On 12/10/17 11:46 am, Fan Deng wrote:
> > 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_.
>
> Yes the match is doing something like this. The actual match is made more
> complicated because the physical state of a set bit can be controlled.
>
> > 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.
>
> I moved the set which is a bug in the code in master in my patch I posed.
> I did
> not paste that bit to the next post, I am sorry about that. Here is the
> fragment
> with the moved set included:
>
> -  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);
>
> > 2. Compares the updated map[index] with RTEMS_RFS_BITMAP_ELEMENT_SET.
> Note this:
> >     - *DOES NOT* check whether the original bit was set.
>
> It does because the set was moved.
>
> >     - *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.
>
> As above the set state of a bit can be a physical 0 or 1 depending on the
> build
> configuration of the RFS.
>
> Chris
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20171012/bfaa80e6/attachment-0002.html>