Changeset 64908df in rtems


Ignore:
Timestamp:
Oct 10, 2017, 11:28:34 PM (2 years ago)
Author:
Fan Deng <enetor@…>
Branches:
master
Children:
d869c182
Parents:
095a807
git-author:
Fan Deng <enetor@…> (10/10/17 23:28:34)
git-committer:
Chris Johns <chrisj@…> (04/11/18 01:51:57)
Message:

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

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.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • cpukit/libfs/src/rfs/rtems-rfs-bitmaps.c

    r095a807 r64908df  
    44 * @brief RTEMS File Systems Bitmap Routines
    55 * @ingroup rtems_rfs
    6  * 
     6 *
    77 * These functions manage bit maps. A bit map consists of the map of bit
    88 * allocated in a block and a search map where a bit represents 32 actual
     
    184184                          rtems_rfs_bitmap_bit      bit)
    185185{
    186   rtems_rfs_bitmap_map map;
    187   rtems_rfs_bitmap_map search_map;
    188   int                  index;
    189   int                  offset;
    190   int                 rc;
     186  rtems_rfs_bitmap_map     map;
     187  rtems_rfs_bitmap_map     search_map;
     188  int                      index;
     189  int                      offset;
     190  int                      rc;
     191  rtems_rfs_bitmap_element element;
     192
    191193  rc = rtems_rfs_bitmap_load_map (control, &map);
    192194  if (rc > 0)
    193195    return rc;
     196
    194197  if (bit >= control->size)
    195198    return EINVAL;
     199
    196200  search_map = control->search_bits;
    197201  index      = rtems_rfs_bitmap_map_index (bit);
    198202  offset     = rtems_rfs_bitmap_map_offset (bit);
    199   map[index] = rtems_rfs_bitmap_set (map[index], 1 << offset);
     203  element    = map[index];
     204  map[index] = rtems_rfs_bitmap_set (element, 1 << offset);
     205
     206  /*
     207   * If the element does not change, the bit was already set. There will be no
     208   * further action to take.
     209   */
     210  if (rtems_rfs_bitmap_match(element, map[index]))
     211      return 0;
     212
     213  control->free--;
     214
     215  rtems_rfs_buffer_mark_dirty (control->buffer);
    200216  if (rtems_rfs_bitmap_match(map[index], RTEMS_RFS_BITMAP_ELEMENT_SET))
    201217  {
     
    204220    offset = rtems_rfs_bitmap_map_offset (bit);
    205221    search_map[index] = rtems_rfs_bitmap_set (search_map[index], 1 << offset);
    206     control->free--;
    207     rtems_rfs_buffer_mark_dirty (control->buffer);
    208222  }
     223
    209224  return 0;
    210225}
     
    214229                            rtems_rfs_bitmap_bit      bit)
    215230{
    216   rtems_rfs_bitmap_map map;
    217   rtems_rfs_bitmap_map search_map;
    218   int                  index;
    219   int                  offset;
    220   int                  rc;
     231  rtems_rfs_bitmap_map     map;
     232  rtems_rfs_bitmap_map     search_map;
     233  int                      index;
     234  int                      offset;
     235  int                      rc;
     236  rtems_rfs_bitmap_element element;
     237
    221238  rc = rtems_rfs_bitmap_load_map (control, &map);
    222239  if (rc > 0)
    223240    return rc;
     241
    224242  if (bit >= control->size)
    225243    return EINVAL;
    226   search_map        = control->search_bits;
    227   index             = rtems_rfs_bitmap_map_index (bit);
    228   offset            = rtems_rfs_bitmap_map_offset (bit);
    229   map[index]        = rtems_rfs_bitmap_clear (map[index], 1 << offset);
     244
     245  search_map = control->search_bits;
     246  index      = rtems_rfs_bitmap_map_index (bit);
     247  offset     = rtems_rfs_bitmap_map_offset (bit);
     248  element    = map[index];
     249  map[index] = rtems_rfs_bitmap_clear (element, 1 << offset);
     250
     251  /*
     252   * If the element does not change, the bit was already clear. There will be
     253   * no further action to take.
     254   */
     255  if (rtems_rfs_bitmap_match(element, map[index]))
     256      return 0;
     257
    230258  bit               = index;
    231259  index             = rtems_rfs_bitmap_map_index (bit);
     
    234262  rtems_rfs_buffer_mark_dirty (control->buffer);
    235263  control->free++;
     264
    236265  return 0;
    237266}
Note: See TracChangeset for help on using the changeset viewer.