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

Changeset 64f3d3b in mainline


Ignore:
Timestamp:
2013-09-12T00:47:42Z (8 years ago)
Author:
Martin Decky <martin@…>
Branches:
lfn, master
Children:
3a0a4d8, 4a5f2b0
Parents:
33c058fe
Message:

basic optimizations of the bitmap allocator
(still not using the 2nd level bitmap)

Location:
kernel/generic
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • kernel/generic/include/adt/bitmap.h

    r33c058fe r64f3d3b  
    9191
    9292extern int bitmap_allocate_range(bitmap_t *, size_t, size_t, size_t, size_t *);
    93 extern void bitmap_free_range(bitmap_t *, size_t, size_t);
    9493extern void bitmap_copy(bitmap_t *, bitmap_t *, size_t);
    9594
  • kernel/generic/src/adt/bitmap.c

    r33c058fe r64f3d3b  
    5656#define ALL_ZEROES  0x00
    5757
     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 */
     68static 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 */
     90static 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
     103/** Unchecked version of bitmap_get()
     104 *
     105 * This version of bitmap_get() does not do any boundary checks.
     106 *
     107 * @param bitmap  Bitmap to access.
     108 * @param element Element to access.
     109 *
     110 * @return Bit value of the element in the bitmap.
     111 *
     112 */
     113static unsigned int bitmap_get_fast(bitmap_t *bitmap, size_t element)
     114{
     115        return !!((bitmap->bits)[element / BITMAP_ELEMENT] &
     116            (1 << (element & BITMAP_REMAINER)));
     117}
     118
    58119/** Get bitmap size
    59120 *
     
    69130size_t bitmap_size(size_t elements, size_t block_size)
    70131{
    71         size_t size = elements / BITMAP_ELEMENT;
    72        
    73         if ((elements % BITMAP_ELEMENT) != 0)
    74                 size++;
    75        
    76         if (block_size > 0) {
    77                 size += elements / block_size;
    78                
    79                 if ((elements % block_size) != 0)
    80                         size++;
    81         }
    82        
    83         return size;
     132        size_t blocks = bitmap_blocks(elements, block_size);
     133       
     134        return (bitmap_bytes(elements) + bitmap_bytes(blocks));
    84135}
    85136
     
    316367                return false;
    317368       
    318         /*
    319          * This is a trivial implementation that should be
    320          * optimized further.
    321          */
    322        
    323         for (size_t i = 0; i < bitmap->elements; i++) {
    324                 if (!constraint_satisfy(i, base, constraint))
     369        size_t bytes = bitmap_bytes(bitmap->elements);
     370       
     371        for (size_t byte = 0; byte < bytes; byte++) {
     372                /* Skip if the current byte has all bits set */
     373                if (bitmap->bits[byte] == ALL_ONES)
    325374                        continue;
    326375               
    327                 if (!bitmap_get(bitmap, i)) {
    328                         bool continuous = true;
     376                size_t byte_bit = byte * BITMAP_ELEMENT;
     377               
     378                for (size_t bit = 0; bit < BITMAP_ELEMENT; bit++) {
     379                        size_t i = byte_bit + bit;
    329380                       
    330                         for (size_t j = 1; j < count; j++) {
    331                                 if ((i + j >= bitmap->elements) ||
    332                                     (bitmap_get(bitmap, i + j))) {
    333                                         continuous = false;
    334                                         break;
     381                        if (i >= bitmap->elements)
     382                                break;
     383                       
     384                        if (!constraint_satisfy(i, base, constraint))
     385                                continue;
     386                       
     387                        if (!bitmap_get_fast(bitmap, i)) {
     388                                bool continuous = true;
     389                               
     390                                for (size_t j = 1; j < count; j++) {
     391                                        if ((i + j >= bitmap->elements) ||
     392                                            (bitmap_get_fast(bitmap, i + j))) {
     393                                                continuous = false;
     394                                                break;
     395                                        }
     396                                }
     397                               
     398                                if (continuous) {
     399                                        if (index != NULL) {
     400                                                bitmap_set_range(bitmap, i, count);
     401                                                *index = i;
     402                                        }
     403                                       
     404                                        return true;
    335405                                }
    336406                        }
    337                        
    338                         if (continuous) {
    339                                 if (index != NULL) {
    340                                         bitmap_set_range(bitmap, i, count);
    341                                         *index = i;
    342                                 }
    343                                
    344                                 return true;
    345                         }
    346407                }
    347                
    348408        }
    349409       
     
    351411}
    352412
    353 /** Clear range of set bits.
    354  *
    355  * This is essentially bitmap_clear_range(), but it also
    356  * checks whether all the cleared bits are actually set.
    357  *
    358  * @param bitmap Bitmap structure.
    359  * @param start  Starting bit.
    360  * @param count  Number of bits to clear.
    361  *
    362  */
    363 void bitmap_free_range(bitmap_t *bitmap, size_t start, size_t count)
    364 {
    365         /*
    366          * This is a trivial implementation that should be
    367          * optimized further.
    368          */
    369        
    370         for (size_t i = 0; i < count; i++) {
    371                 if (!bitmap_get(bitmap, start + i))
    372                         panic("Freeing a bitmap range that is not set");
    373         }
    374        
    375         bitmap_clear_range(bitmap, start, count);
    376 }
    377 
    378413/** @}
    379414 */
  • kernel/generic/src/mm/frame.c

    r33c058fe r64f3d3b  
    6161#include <str.h>
    6262
    63 #define BITMAP_BLOCK_SIZE  1024
     63#define BITMAP_BLOCK_SIZE  128
    6464
    6565zones_t zones;
     
    352352       
    353353        if (!--frame->refcount) {
    354                 bitmap_free_range(&zone->bitmap, index, 1);
     354                bitmap_set(&zone->bitmap, index, 0);
    355355               
    356356                /* Update zone information. */
Note: See TracChangeset for help on using the changeset viewer.