Changeset c5396c1 in mainline for kernel/generic/src


Ignore:
Timestamp:
2013-09-12T10:27:17Z (12 years ago)
Author:
Martin Decky <martin@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
6e75f2d
Parents:
4a5f2b0
Message:

abandon the 2nd level bitmap
according to observations it is very rare to have allocation requests for more than 8 frames, therefore the conservative update of the 2nd level bitmap can hardly provide any benefits
the natural blocking of the bitmap (by bytes) should provide a reasonable performance

Location:
kernel/generic/src
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • kernel/generic/src/adt/bitmap.c

    r4a5f2b0 rc5396c1  
    3737 * setting and clearing ranges of bits and for finding ranges
    3838 * of unset bits.
    39  *
    40  * The bitmap ADT can optionally implement a two-level hierarchy
    41  * for faster range searches. The second level bitmap (of blocks)
    42  * is not precise, but conservative. This means that if the block
    43  * bit is set, it guarantees that all bits in the block are set.
    44  * But if the block bit is unset, nothing can be said about the
    45  * bits in the block.
    46  *
    4739 */
    4840
    … …  
    5648#define ALL_ZEROES  0x00
    5749
    58 /** Compute the size of a bitmap
    59  *
    60  * Compute the size of a bitmap that can store given number
    61  * of elements.
    62  *
    63  * @param elements Number of elements to store.
    64  *
    65  * @return Size of the bitmap (in units of BITMAP_ELEMENT bits).
    66  *
    67  */
    68 static size_t bitmap_bytes(size_t elements)
    69 {
    70         size_t bytes = elements / BITMAP_ELEMENT;
    71        
    72         if ((elements % BITMAP_ELEMENT) != 0)
    73                 bytes++;
    74        
    75         return bytes;
    76 }
    77 
    78 /** Compute the number of 2nd level blocks
    79  *
    80  * Compute the number of 2nd level blocks for a given number
    81  * of elements.
    82  *
    83  * @param elements   Number of elements.
    84  * @param block_size Number of elements in one block.
    85  *
    86  * @return Number of 2nd level blocks.
    87  * @return Zero if block_size is zero.
    88  *
    89  */
    90 static size_t bitmap_blocks(size_t elements, size_t block_size)
    91 {
    92         if (block_size == 0)
    93                 return 0;
    94        
    95         size_t blocks = elements / block_size;
    96        
    97         if ((elements % block_size) != 0)
    98                 blocks++;
    99        
    100         return blocks;
    101 }
    102 
    10350/** Unchecked version of bitmap_get()
    10451 *
    … …  
    11360static unsigned int bitmap_get_fast(bitmap_t *bitmap, size_t element)
    11461{
    115         return !!((bitmap->bits)[element / BITMAP_ELEMENT] &
    116             (1 << (element & BITMAP_REMAINER)));
     62        size_t byte = element / BITMAP_ELEMENT;
     63        uint8_t mask = 1 << (element & BITMAP_REMAINER);
     64       
     65        return !!((bitmap->bits)[byte] & mask);
    11766}
    11867
    … …  
    12271 *
    12372 * @param elements   Number bits stored in bitmap.
    124  * @param block_size Block size of the 2nd level bitmap.
    125  *                   If set to zero, no 2nd level is used.
    12673 *
    12774 * @return Size (in bytes) required for the bitmap.
    12875 *
    12976 */
    130 size_t bitmap_size(size_t elements, size_t block_size)
    131 {
    132         size_t blocks = bitmap_blocks(elements, block_size);
    133        
    134         return (bitmap_bytes(elements) + bitmap_bytes(blocks));
     77size_t bitmap_size(size_t elements)
     78{
     79        size_t size = elements / BITMAP_ELEMENT;
     80       
     81        if ((elements % BITMAP_ELEMENT) != 0)
     82                size++;
     83       
     84        return size;
    13585}
    13686
    … …  
    14191 * @param bitmap     Bitmap structure.
    14292 * @param elements   Number of bits stored in bitmap.
    143  * @param block_size Block size of the 2nd level bitmap.
    144  *                   If set to zero, no 2nd level is used.
    14593 * @param data       Address of the memory used to hold the map.
    14694 *                   The optional 2nd level bitmap follows the 1st
    … …  
    14896 *
    14997 */
    150 void bitmap_initialize(bitmap_t *bitmap, size_t elements, size_t block_size,
    151     void *data)
     98void bitmap_initialize(bitmap_t *bitmap, size_t elements, void *data)
    15299{
    153100        bitmap->elements = elements;
    154101        bitmap->bits = (uint8_t *) data;
    155        
    156         if (block_size > 0) {
    157                 bitmap->block_size = block_size;
    158                 bitmap->blocks = bitmap->bits +
    159                     bitmap_size(elements, 0);
    160         } else {
    161                 bitmap->block_size = 0;
    162                 bitmap->blocks = NULL;
    163         }
    164 }
    165 
    166 static void bitmap_set_range_internal(uint8_t *bits, size_t start, size_t count)
    167 {
    168         if (count == 0)
    169                 return;
    170        
    171         size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT);
    172        
    173         /* Leading unaligned bits */
    174         size_t lub = min(aligned_start - start, count);
    175        
    176         /* Aligned middle bits */
    177         size_t amb = (count > lub) ? (count - lub) : 0;
    178        
    179         /* Trailing aligned bits */
    180         size_t tab = amb % BITMAP_ELEMENT;
    181        
    182         if (start + count < aligned_start) {
    183                 /* Set bits in the middle of byte. */
    184                 bits[start / BITMAP_ELEMENT] |=
    185                     ((1 << lub) - 1) << (start & BITMAP_REMAINER);
    186                 return;
    187         }
    188        
    189         if (lub) {
    190                 /* Make sure to set any leading unaligned bits. */
    191                 bits[start / BITMAP_ELEMENT] |=
    192                     ~((1 << (BITMAP_ELEMENT - lub)) - 1);
    193         }
    194        
    195         size_t i;
    196        
    197         for (i = 0; i < amb / BITMAP_ELEMENT; i++) {
    198                 /* The middle bits can be set byte by byte. */
    199                 bits[aligned_start / BITMAP_ELEMENT + i] = ALL_ONES;
    200         }
    201        
    202         if (tab) {
    203                 /* Make sure to set any trailing aligned bits. */
    204                 bits[aligned_start / BITMAP_ELEMENT + i] |= (1 << tab) - 1;
    205         }
    206102}
    207103
    … …  
    217113        ASSERT(start + count <= bitmap->elements);
    218114       
    219         bitmap_set_range_internal(bitmap->bits, start, count);
    220        
    221         if (bitmap->block_size > 0) {
    222                 size_t aligned_start = ALIGN_UP(start, bitmap->block_size);
    223                
    224                 /* Leading unaligned bits */
    225                 size_t lub = min(aligned_start - start, count);
    226                
    227                 /* Aligned middle bits */
    228                 size_t amb = (count > lub) ? (count - lub) : 0;
    229                
    230                 size_t aligned_size = amb / bitmap->block_size;
    231                
    232                 bitmap_set_range_internal(bitmap->blocks, aligned_start,
    233                     aligned_size);
    234         }
    235 }
    236 
    237 static void bitmap_clear_range_internal(uint8_t *bits, size_t start,
    238     size_t count)
    239 {
    240115        if (count == 0)
    241116                return;
    … …  
    253128       
    254129        if (start + count < aligned_start) {
    255                 /* Set bits in the middle of byte */
    256                 bits[start / BITMAP_ELEMENT] &=
    257                     ~(((1 << lub) - 1) << (start & BITMAP_REMAINER));
     130                /* Set bits in the middle of byte. */
     131                bitmap->bits[start / BITMAP_ELEMENT] |=
     132                    ((1 << lub) - 1) << (start & BITMAP_REMAINER);
    258133                return;
    259134        }
    260135       
    261136        if (lub) {
    262                 /* Make sure to clear any leading unaligned bits. */
    263                 bits[start / BITMAP_ELEMENT] &=
    264                     (1 << (BITMAP_ELEMENT - lub)) - 1;
     137                /* Make sure to set any leading unaligned bits. */
     138                bitmap->bits[start / BITMAP_ELEMENT] |=
     139                    ~((1 << (BITMAP_ELEMENT - lub)) - 1);
    265140        }
    266141       
    … …  
    268143       
    269144        for (i = 0; i < amb / BITMAP_ELEMENT; i++) {
    270                 /* The middle bits can be cleared byte by byte. */
    271                 bits[aligned_start / BITMAP_ELEMENT + i] = ALL_ZEROES;
     145                /* The middle bits can be set byte by byte. */
     146                bitmap->bits[aligned_start / BITMAP_ELEMENT + i] =
     147                    ALL_ONES;
    272148        }
    273149       
    274150        if (tab) {
    275                 /* Make sure to clear any trailing aligned bits. */
    276                 bits[aligned_start / BITMAP_ELEMENT + i] &= ~((1 << tab) - 1);
     151                /* Make sure to set any trailing aligned bits. */
     152                bitmap->bits[aligned_start / BITMAP_ELEMENT + i] |=
     153                    (1 << tab) - 1;
    277154        }
    278155}
    … …  
    289166        ASSERT(start + count <= bitmap->elements);
    290167       
    291         bitmap_clear_range_internal(bitmap->bits, start, count);
    292        
    293         if (bitmap->block_size > 0) {
    294                 size_t aligned_start = start / bitmap->block_size;
    295                
    296                 size_t aligned_end = (start + count) / bitmap->block_size;
    297                
    298                 if (((start + count) % bitmap->block_size) != 0)
    299                         aligned_end++;
    300                
    301                 size_t aligned_size = aligned_end - aligned_start;
    302                
    303                 bitmap_clear_range_internal(bitmap->blocks, aligned_start,
    304                     aligned_size);
     168        if (count == 0)
     169                return;
     170       
     171        size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT);
     172       
     173        /* Leading unaligned bits */
     174        size_t lub = min(aligned_start - start, count);
     175       
     176        /* Aligned middle bits */
     177        size_t amb = (count > lub) ? (count - lub) : 0;
     178       
     179        /* Trailing aligned bits */
     180        size_t tab = amb % BITMAP_ELEMENT;
     181       
     182        if (start + count < aligned_start) {
     183                /* Set bits in the middle of byte */
     184                bitmap->bits[start / BITMAP_ELEMENT] &=
     185                    ~(((1 << lub) - 1) << (start & BITMAP_REMAINER));
     186                return;
     187        }
     188       
     189        if (lub) {
     190                /* Make sure to clear any leading unaligned bits. */
     191                bitmap->bits[start / BITMAP_ELEMENT] &=
     192                    (1 << (BITMAP_ELEMENT - lub)) - 1;
     193        }
     194       
     195        size_t i;
     196       
     197        for (i = 0; i < amb / BITMAP_ELEMENT; i++) {
     198                /* The middle bits can be cleared byte by byte. */
     199                bitmap->bits[aligned_start / BITMAP_ELEMENT + i] =
     200                    ALL_ZEROES;
     201        }
     202       
     203        if (tab) {
     204                /* Make sure to clear any trailing aligned bits. */
     205                bitmap->bits[aligned_start / BITMAP_ELEMENT + i] &=
     206                    ~((1 << tab) - 1);
    305207        }
    306208}
    … …  
    367269                return false;
    368270       
    369         size_t bytes = bitmap_bytes(bitmap->elements);
     271        size_t bytes = bitmap_size(bitmap->elements);
    370272       
    371273        for (size_t byte = 0; byte < bytes; byte++) {

  • kernel/generic/src/mm/frame.c

    r4a5f2b0 rc5396c1  
    6060#include <config.h>
    6161#include <str.h>
    62 
    63 #define BITMAP_BLOCK_SIZE  128
    6462
    6563zones_t zones;
    … …  
    410408       
    411409        bitmap_initialize(&zones.info[z1].bitmap, zones.info[z1].count,
    412             BITMAP_BLOCK_SIZE, confdata +
    413             (sizeof(frame_t) * zones.info[z1].count));
     410            confdata + (sizeof(frame_t) * zones.info[z1].count));
    414411        bitmap_clear_range(&zones.info[z1].bitmap, 0, zones.info[z1].count);
    415412       
    … …  
    578575                 */
    579576               
    580                 bitmap_initialize(&zone->bitmap, count, BITMAP_BLOCK_SIZE,
    581                     confdata + (sizeof(frame_t) * count));
     577                bitmap_initialize(&zone->bitmap, count, confdata +
     578                    (sizeof(frame_t) * count));
    582579                bitmap_clear_range(&zone->bitmap, 0, count);
    583580               
    … …  
    591588                        frame_initialize(&zone->frames[i]);
    592589        } else {
    593                 bitmap_initialize(&zone->bitmap, 0, 0, NULL);
     590                bitmap_initialize(&zone->bitmap, 0, NULL);
    594591                zone->frames = NULL;
    595592        }
    … …  
    605602size_t zone_conf_size(size_t count)
    606603{
    607         return (count * sizeof(frame_t) +
    608             bitmap_size(count, BITMAP_BLOCK_SIZE));
     604        return (count * sizeof(frame_t) + bitmap_size(count));
    609605}
    610606
Note: See TracChangeset for help on using the changeset viewer.