Fork us on GitHub Follow us on Facebook Follow us on Twitter

Changeset c5396c1 in mainline


Ignore:
Timestamp:
2013-09-12T10:27:17Z (7 years ago)
Author:
Martin Decky <martin@…>
Branches:
master
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
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • kernel/arch/amd64/src/ddi/ddi.c

    r4a5f2b0 rc5396c1  
    6868                 */
    6969               
    70                 void *store = malloc(bitmap_size(elements, 0), FRAME_ATOMIC);
     70                void *store = malloc(bitmap_size(elements), FRAME_ATOMIC);
    7171                if (!store)
    7272                        return ENOMEM;
    7373               
    7474                bitmap_t oldiomap;
    75                 bitmap_initialize(&oldiomap, task->arch.iomap.elements, 0,
     75                bitmap_initialize(&oldiomap, task->arch.iomap.elements,
    7676                    task->arch.iomap.bits);
    7777               
    78                 bitmap_initialize(&task->arch.iomap, elements, 0, store);
     78                bitmap_initialize(&task->arch.iomap, elements, store);
    7979               
    8080                /*
     
    129129               
    130130                bitmap_t iomap;
    131                 bitmap_initialize(&iomap, TSS_IOMAP_SIZE * 8, 0,
     131                bitmap_initialize(&iomap, TSS_IOMAP_SIZE * 8,
    132132                    CPU->arch.tss->iomap);
    133133                bitmap_copy(&iomap, &TASK->arch.iomap, elements);
     
    157157       
    158158        descriptor_t *gdt_p = (descriptor_t *) cpugdtr.base;
    159         size_t size = bitmap_size(elements, 0);
     159        size_t size = bitmap_size(elements);
    160160        gdt_tss_setlimit(&gdt_p[TSS_DES], TSS_BASIC_SIZE + size);
    161161        gdtr_load(&cpugdtr);
  • kernel/arch/amd64/src/proc/task.c

    r4a5f2b0 rc5396c1  
    4646{
    4747        task->arch.iomapver = 0;
    48         bitmap_initialize(&task->arch.iomap, 0, 0, NULL);
     48        bitmap_initialize(&task->arch.iomap, 0, NULL);
    4949}
    5050
  • kernel/arch/ia32/src/ddi/ddi.c

    r4a5f2b0 rc5396c1  
    6868                 */
    6969               
    70                 void *store = malloc(bitmap_size(elements, 0), FRAME_ATOMIC);
     70                void *store = malloc(bitmap_size(elements), FRAME_ATOMIC);
    7171                if (!store)
    7272                        return ENOMEM;
    7373               
    7474                bitmap_t oldiomap;
    75                 bitmap_initialize(&oldiomap, task->arch.iomap.elements, 0,
     75                bitmap_initialize(&oldiomap, task->arch.iomap.elements,
    7676                    task->arch.iomap.bits);
    7777               
    78                 bitmap_initialize(&task->arch.iomap, elements, 0, store);
     78                bitmap_initialize(&task->arch.iomap, elements, store);
    7979               
    8080                /*
     
    129129               
    130130                bitmap_t iomap;
    131                 bitmap_initialize(&iomap, TSS_IOMAP_SIZE * 8, 0,
     131                bitmap_initialize(&iomap, TSS_IOMAP_SIZE * 8,
    132132                    CPU->arch.tss->iomap);
    133133                bitmap_copy(&iomap, &TASK->arch.iomap, elements);
     
    157157       
    158158        descriptor_t *gdt_p = (descriptor_t *) cpugdtr.base;
    159         size_t size = bitmap_size(elements, 0);
     159        size_t size = bitmap_size(elements);
    160160        gdt_setlimit(&gdt_p[TSS_DES], TSS_BASIC_SIZE + size);
    161161        gdtr_load(&cpugdtr);
  • kernel/arch/ia32/src/proc/task.c

    r4a5f2b0 rc5396c1  
    4646{
    4747        task->arch.iomapver = 0;
    48         bitmap_initialize(&task->arch.iomap, 0, 0, NULL);
     48        bitmap_initialize(&task->arch.iomap, 0, NULL);
    4949}
    5050
  • kernel/arch/ia64/src/ddi/ddi.c

    r4a5f2b0 rc5396c1  
    6060                        return ENOMEM;
    6161               
    62                 void *store = malloc(bitmap_size(IO_MEMMAP_PAGES, 0), 0);
     62                void *store = malloc(bitmap_size(IO_MEMMAP_PAGES), 0);
    6363                if (store == NULL)
    6464                        return ENOMEM;
    6565               
    66                 bitmap_initialize(task->arch.iomap, IO_MEMMAP_PAGES, 0, store);
     66                bitmap_initialize(task->arch.iomap, IO_MEMMAP_PAGES, store);
    6767                bitmap_clear_range(task->arch.iomap, 0, IO_MEMMAP_PAGES);
    6868        }
  • kernel/generic/include/adt/bitmap.h

    r4a5f2b0 rc5396c1  
    4444        size_t elements;
    4545        uint8_t *bits;
    46        
    47         size_t block_size;
    48         uint8_t *blocks;
    4946} bitmap_t;
    5047
     
    5249    unsigned int value)
    5350{
    54         if (element < bitmap->elements) {
    55                 /*
    56                  * The 2nd level bitmap is conservative.
    57                  * Make sure we update it properly.
    58                  */
    59                
    60                 if (value) {
    61                         bitmap->bits[element / BITMAP_ELEMENT] |=
    62                             (1 << (element & BITMAP_REMAINER));
    63                 } else {
    64                         bitmap->bits[element / BITMAP_ELEMENT] &=
    65                             ~(1 << (element & BITMAP_REMAINER));
    66                        
    67                         if (bitmap->block_size > 0) {
    68                                 size_t block = element / bitmap->block_size;
    69                                
    70                                 bitmap->blocks[block / BITMAP_ELEMENT] &=
    71                                     ~(1 << (block & BITMAP_REMAINER));
    72                         }
    73                 }
     51        if (element >= bitmap->elements)
     52                return;
     53       
     54        size_t byte = element / BITMAP_ELEMENT;
     55        uint8_t mask = 1 << (element & BITMAP_REMAINER);
     56       
     57        if (value) {
     58                bitmap->bits[byte] |= mask;
     59        } else {
     60                bitmap->bits[byte] &= ~mask;
    7461        }
    7562}
     
    8067                return 0;
    8168       
    82         return !!((bitmap->bits)[element / BITMAP_ELEMENT] &
    83             (1 << (element & BITMAP_REMAINER)));
     69        size_t byte = element / BITMAP_ELEMENT;
     70        uint8_t mask = 1 << (element & BITMAP_REMAINER);
     71       
     72        return !!((bitmap->bits)[byte] & mask);
    8473}
    8574
    86 extern size_t bitmap_size(size_t, size_t);
    87 extern void bitmap_initialize(bitmap_t *, size_t, size_t, void *);
     75extern size_t bitmap_size(size_t);
     76extern void bitmap_initialize(bitmap_t *, size_t, void *);
    8877
    8978extern void bitmap_set_range(bitmap_t *, size_t, size_t);
  • 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.