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

Changeset 6e75f2d in mainline


Ignore:
Timestamp:
2013-09-12T11:45:34Z (7 years ago)
Author:
Martin Decky <martin@…>
Branches:
master
Children:
3731d31
Parents:
c5396c1
Message:

optimize bitmap allocation using the next-fit algorithm

Location:
kernel/generic
Files:
2 edited

Legend:

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

    rc5396c1 r6e75f2d  
    4444        size_t elements;
    4545        uint8_t *bits;
     46        size_t next_fit;
    4647} bitmap_t;
    4748
     
    5960        } else {
    6061                bitmap->bits[byte] &= ~mask;
     62                bitmap->next_fit = byte;
    6163        }
    6264}
  • kernel/generic/src/adt/bitmap.c

    rc5396c1 r6e75f2d  
    100100        bitmap->elements = elements;
    101101        bitmap->bits = (uint8_t *) data;
     102        bitmap->next_fit = 0;
    102103}
    103104
     
    116117                return;
    117118       
     119        size_t start_byte = start / BITMAP_ELEMENT;
    118120        size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT);
    119121       
     
    129131        if (start + count < aligned_start) {
    130132                /* Set bits in the middle of byte. */
    131                 bitmap->bits[start / BITMAP_ELEMENT] |=
     133                bitmap->bits[start_byte] |=
    132134                    ((1 << lub) - 1) << (start & BITMAP_REMAINER);
    133135                return;
     
    136138        if (lub) {
    137139                /* Make sure to set any leading unaligned bits. */
    138                 bitmap->bits[start / BITMAP_ELEMENT] |=
     140                bitmap->bits[start_byte] |=
    139141                    ~((1 << (BITMAP_ELEMENT - lub)) - 1);
    140142        }
     
    169171                return;
    170172       
     173        size_t start_byte = start / BITMAP_ELEMENT;
    171174        size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT);
    172175       
     
    182185        if (start + count < aligned_start) {
    183186                /* Set bits in the middle of byte */
    184                 bitmap->bits[start / BITMAP_ELEMENT] &=
     187                bitmap->bits[start_byte] &=
    185188                    ~(((1 << lub) - 1) << (start & BITMAP_REMAINER));
    186189                return;
     
    189192        if (lub) {
    190193                /* Make sure to clear any leading unaligned bits. */
    191                 bitmap->bits[start / BITMAP_ELEMENT] &=
     194                bitmap->bits[start_byte] &=
    192195                    (1 << (BITMAP_ELEMENT - lub)) - 1;
    193196        }
     
    206209                    ~((1 << tab) - 1);
    207210        }
     211       
     212        bitmap->next_fit = start_byte;
    208213}
    209214
     
    269274                return false;
    270275       
    271         size_t bytes = bitmap_size(bitmap->elements);
    272        
    273         for (size_t byte = 0; byte < bytes; byte++) {
     276        size_t size = bitmap_size(bitmap->elements);
     277       
     278        for (size_t pos = 0; pos < size; pos++) {
     279                size_t byte = (bitmap->next_fit + pos) % size;
     280               
    274281                /* Skip if the current byte has all bits set */
    275282                if (bitmap->bits[byte] == ALL_ONES)
     
    288295                       
    289296                        if (!bitmap_get_fast(bitmap, i)) {
    290                                 bool continuous = true;
     297                                size_t continuous = 1;
    291298                               
    292299                                for (size_t j = 1; j < count; j++) {
    293                                         if ((i + j >= bitmap->elements) ||
    294                                             (bitmap_get_fast(bitmap, i + j))) {
    295                                                 continuous = false;
     300                                        if ((i + j < bitmap->elements) &&
     301                                            (!bitmap_get_fast(bitmap, i + j)))
     302                                                continuous++;
     303                                        else
    296304                                                break;
    297                                         }
    298305                                }
    299306                               
    300                                 if (continuous) {
     307                                if (continuous == count) {
    301308                                        if (index != NULL) {
    302309                                                bitmap_set_range(bitmap, i, count);
     310                                                bitmap->next_fit = i / BITMAP_ELEMENT;
    303311                                                *index = i;
    304312                                        }
    305313                                       
    306314                                        return true;
    307                                 }
     315                                } else
     316                                        i += continuous;
    308317                        }
    309318                }
Note: See TracChangeset for help on using the changeset viewer.