[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.html>
More information about the devel
mailing list