Changeset 7de18418 in mainline


Ignore:
Timestamp:
2013-09-08T10:34:41Z (11 years ago)
Author:
Martin Decky <martin@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
29a3886
Parents:
063a74b9
Message:

partial implementation of a two-level bitmap data structure

Location:
kernel
Files:
7 edited

Legend:

Unmodified
Added
Removed

  • kernel/arch/amd64/src/ddi/ddi.c

    r063a74b9 r7de18418  
    4242#include <errno.h>
    4343#include <arch/cpu.h>
     44#include <cpu.h>
    4445#include <arch.h>
    4546#include <align.h>
    … …  
    5859int ddi_iospace_enable_arch(task_t *task, uintptr_t ioaddr, size_t size)
    5960{
    60         size_t bits = ioaddr + size;
    61         if (bits > IO_PORTS)
     61        size_t elements = ioaddr + size;
     62        if (elements > IO_PORTS)
    6263                return ENOENT;
    6364       
    64         if (task->arch.iomap.bits < bits) {
     65        if (task->arch.iomap.elements < elements) {
    6566                /*
    6667                 * The I/O permission bitmap is too small and needs to be grown.
    6768                 */
    6869               
    69                 uint8_t *newmap = (uint8_t *) malloc(BITS2BYTES(bits), FRAME_ATOMIC);
    70                 if (!newmap)
     70                void *store = malloc(bitmap_size(elements, 0), FRAME_ATOMIC);
     71                if (!store)
    7172                        return ENOMEM;
    7273               
    7374                bitmap_t oldiomap;
    74                 bitmap_initialize(&oldiomap, task->arch.iomap.map,
     75                bitmap_initialize(&oldiomap, task->arch.iomap.elements, 0,
    7576                    task->arch.iomap.bits);
    76                 bitmap_initialize(&task->arch.iomap, newmap, bits);
     77               
     78                bitmap_initialize(&task->arch.iomap, elements, 0, store);
    7779               
    7880                /*
    7981                 * Mark the new range inaccessible.
    8082                 */
    81                 bitmap_set_range(&task->arch.iomap, oldiomap.bits,
    82                     bits - oldiomap.bits);
     83                bitmap_set_range(&task->arch.iomap, oldiomap.elements,
     84                    elements - oldiomap.elements);
    8385               
    8486                /*
    … …  
    8890                if (oldiomap.bits) {
    8991                        bitmap_copy(&task->arch.iomap, &oldiomap,
    90                             oldiomap.bits);
    91                         free(oldiomap.map);
     92                            oldiomap.elements);
     93                       
     94                        free(oldiomap.bits);
    9295                }
    9396        }
    … …  
    9699         * Enable the range and we are done.
    97100         */
    98         bitmap_clear_range(&task->arch.iomap, (size_t) ioaddr, (size_t) size);
     101        bitmap_clear_range(&task->arch.iomap, (size_t) ioaddr, size);
    99102       
    100103        /*
    … …  
    118121        /* First, copy the I/O Permission Bitmap. */
    119122        irq_spinlock_lock(&TASK->lock, false);
     123       
    120124        size_t ver = TASK->arch.iomapver;
    121         size_t bits = TASK->arch.iomap.bits;
    122         if (bits) {
    123                 ASSERT(TASK->arch.iomap.map);
     125        size_t elements = TASK->arch.iomap.elements;
     126       
     127        if (elements > 0) {
     128                ASSERT(TASK->arch.iomap.bits);
    124129               
    125130                bitmap_t iomap;
    126                 bitmap_initialize(&iomap, CPU->arch.tss->iomap,
    127                     TSS_IOMAP_SIZE * 8);
    128                 bitmap_copy(&iomap, &TASK->arch.iomap, bits);
     131                bitmap_initialize(&iomap, TSS_IOMAP_SIZE * 8, 0,
     132                    CPU->arch.tss->iomap);
     133                bitmap_copy(&iomap, &TASK->arch.iomap, elements);
    129134               
    130135                /*
    … …  
    132137                 * I/O access.
    133138                 */
    134                 bitmap_set_range(&iomap, bits, ALIGN_UP(bits, 8) - bits);
     139                bitmap_set_range(&iomap, elements,
     140                    ALIGN_UP(elements, 8) - elements);
     141               
    135142                /*
    136143                 * It is safe to set the trailing eight bits because of the
    137144                 * extra convenience byte in TSS_IOMAP_SIZE.
    138145                 */
    139                 bitmap_set_range(&iomap, ALIGN_UP(bits, 8), 8);
     146                bitmap_set_range(&iomap, ALIGN_UP(elements, 8), 8);
    140147        }
     148       
    141149        irq_spinlock_unlock(&TASK->lock, false);
    142150       
    143151        /*
    144152         * Second, adjust TSS segment limit.
    145          * Take the extra ending byte will all bits set into account.
     153         * Take the extra ending byte with all bits set into account.
    146154         */
    147155        ptr_16_64_t cpugdtr;
    … …  
    149157       
    150158        descriptor_t *gdt_p = (descriptor_t *) cpugdtr.base;
    151         gdt_tss_setlimit(&gdt_p[TSS_DES], TSS_BASIC_SIZE + BITS2BYTES(bits));
     159        size_t size = bitmap_size(elements, 0);
     160        gdt_tss_setlimit(&gdt_p[TSS_DES], TSS_BASIC_SIZE + size);
    152161        gdtr_load(&cpugdtr);
    153162       

  • kernel/arch/amd64/src/proc/task.c

    r063a74b9 r7de18418  
    3434
    3535#include <proc/task.h>
     36#include <typedefs.h>
     37#include <adt/bitmap.h>
    3638#include <mm/slab.h>
    37 #include <typedefs.h>
    3839
    3940/** Perform amd64 specific task initialization.
    … …  
    4546{
    4647        task->arch.iomapver = 0;
    47         bitmap_initialize(&task->arch.iomap, NULL, 0);
     48        bitmap_initialize(&task->arch.iomap, 0, 0, NULL);
    4849}
    4950
    … …  
    5556void task_destroy_arch(task_t *task)
    5657{
    57         if (task->arch.iomap.map)
    58                 free(task->arch.iomap.map);
     58        if (task->arch.iomap.bits != NULL)
     59                free(task->arch.iomap.bits);
    5960}
    6061

  • kernel/arch/ia32/src/ddi/ddi.c

    r063a74b9 r7de18418  
    5959int ddi_iospace_enable_arch(task_t *task, uintptr_t ioaddr, size_t size)
    6060{
    61         size_t bits = ioaddr + size;
    62         if (bits > IO_PORTS)
     61        size_t elements = ioaddr + size;
     62        if (elements > IO_PORTS)
    6363                return ENOENT;
    6464       
    65         if (task->arch.iomap.bits < bits) {
     65        if (task->arch.iomap.elements < elements) {
    6666                /*
    6767                 * The I/O permission bitmap is too small and needs to be grown.
    6868                 */
    6969               
    70                 uint8_t *newmap = (uint8_t *) malloc(BITS2BYTES(bits), FRAME_ATOMIC);
    71                 if (!newmap)
     70                void *store = malloc(bitmap_size(elements, 0), FRAME_ATOMIC);
     71                if (!store)
    7272                        return ENOMEM;
    7373               
    7474                bitmap_t oldiomap;
    75                 bitmap_initialize(&oldiomap, task->arch.iomap.map,
     75                bitmap_initialize(&oldiomap, task->arch.iomap.elements, 0,
    7676                    task->arch.iomap.bits);
    77                 bitmap_initialize(&task->arch.iomap, newmap, bits);
     77               
     78                bitmap_initialize(&task->arch.iomap, elements, 0, store);
    7879               
    7980                /*
    8081                 * Mark the new range inaccessible.
    8182                 */
    82                 bitmap_set_range(&task->arch.iomap, oldiomap.bits,
    83                     bits - oldiomap.bits);
     83                bitmap_set_range(&task->arch.iomap, oldiomap.elements,
     84                    elements - oldiomap.elements);
    8485               
    8586                /*
    … …  
    8990                if (oldiomap.bits) {
    9091                        bitmap_copy(&task->arch.iomap, &oldiomap,
    91                             oldiomap.bits);
    92                         free(oldiomap.map);
     92                            oldiomap.elements);
     93                       
     94                        free(oldiomap.bits);
    9395                }
    9496        }
    … …  
    9799         * Enable the range and we are done.
    98100         */
    99         bitmap_clear_range(&task->arch.iomap, (size_t) ioaddr, (size_t) size);
     101        bitmap_clear_range(&task->arch.iomap, (size_t) ioaddr, size);
    100102       
    101103        /*
    … …  
    119121        /* First, copy the I/O Permission Bitmap. */
    120122        irq_spinlock_lock(&TASK->lock, false);
     123       
    121124        size_t ver = TASK->arch.iomapver;
    122         size_t bits = TASK->arch.iomap.bits;
    123         if (bits) {
    124                 ASSERT(TASK->arch.iomap.map);
     125        size_t elements = TASK->arch.iomap.elements;
     126       
     127        if (elements > 0) {
     128                ASSERT(TASK->arch.iomap.bits);
    125129               
    126130                bitmap_t iomap;
    127                 bitmap_initialize(&iomap, CPU->arch.tss->iomap,
    128                     TSS_IOMAP_SIZE * 8);
    129                 bitmap_copy(&iomap, &TASK->arch.iomap, bits);
     131                bitmap_initialize(&iomap, TSS_IOMAP_SIZE * 8, 0,
     132                    CPU->arch.tss->iomap);
     133                bitmap_copy(&iomap, &TASK->arch.iomap, elements);
    130134               
    131135                /*
    … …  
    133137                 * I/O access.
    134138                 */
    135                 bitmap_set_range(&iomap, bits, ALIGN_UP(bits, 8) - bits);
     139                bitmap_set_range(&iomap, elements,
     140                    ALIGN_UP(elements, 8) - elements);
     141               
    136142                /*
    137143                 * It is safe to set the trailing eight bits because of the
    138144                 * extra convenience byte in TSS_IOMAP_SIZE.
    139145                 */
    140                 bitmap_set_range(&iomap, ALIGN_UP(bits, 8), 8);
     146                bitmap_set_range(&iomap, ALIGN_UP(elements, 8), 8);
    141147        }
     148       
    142149        irq_spinlock_unlock(&TASK->lock, false);
    143150       
    … …  
    150157       
    151158        descriptor_t *gdt_p = (descriptor_t *) cpugdtr.base;
    152         gdt_setlimit(&gdt_p[TSS_DES], TSS_BASIC_SIZE + BITS2BYTES(bits));
     159        size_t size = bitmap_size(elements, 0);
     160        gdt_setlimit(&gdt_p[TSS_DES], TSS_BASIC_SIZE + size);
    153161        gdtr_load(&cpugdtr);
    154162       

  • kernel/arch/ia32/src/proc/task.c

    r063a74b9 r7de18418  
    4040/** Perform ia32 specific task initialization.
    4141 *
    42  * @param t Task to be initialized.
     42 * @param task Task to be initialized.
     43 *
    4344 */
    44 void task_create_arch(task_t *t)
     45void task_create_arch(task_t *task)
    4546{
    46         t->arch.iomapver = 0;
    47         bitmap_initialize(&t->arch.iomap, NULL, 0);
     47        task->arch.iomapver = 0;
     48        bitmap_initialize(&task->arch.iomap, 0, 0, NULL);
    4849}
    4950
    5051/** Perform ia32 specific task destruction.
    5152 *
    52  * @param t Task to be initialized.
     53 * @param task Task to be initialized.
     54 *
    5355 */
    54 void task_destroy_arch(task_t *t)
     56void task_destroy_arch(task_t *task)
    5557{
    56         if (t->arch.iomap.map)
    57                 free(t->arch.iomap.map);
     58        if (task->arch.iomap.bits != NULL)
     59                free(task->arch.iomap.bits);
    5860}
    5961

  • kernel/arch/ia64/src/ddi/ddi.c

    r063a74b9 r7de18418  
    5656{
    5757        if (!task->arch.iomap) {
    58                 uint8_t *map;
    59 
    6058                task->arch.iomap = malloc(sizeof(bitmap_t), 0);
    61                 map = malloc(BITS2BYTES(IO_MEMMAP_PAGES), 0);
    62                 if(!map)
     59                if (task->arch.iomap == NULL)
    6360                        return ENOMEM;
    64                 bitmap_initialize(task->arch.iomap, map, IO_MEMMAP_PAGES);
     61               
     62                void *store = malloc(bitmap_size(IO_MEMMAP_PAGES, 0), 0);
     63                if (store == NULL)
     64                        return ENOMEM;
     65               
     66                bitmap_initialize(task->arch.iomap, IO_MEMMAP_PAGES, 0, store);
    6567                bitmap_clear_range(task->arch.iomap, 0, IO_MEMMAP_PAGES);
    6668        }
    … …  
    6971        size = ALIGN_UP(size + ioaddr - 4 * iopage, PORTS_PER_PAGE);
    7072        bitmap_set_range(task->arch.iomap, iopage, size / 4);
    71 
     73       
    7274        return 0;
    7375}

  • kernel/generic/include/adt/bitmap.h

    r063a74b9 r7de18418  
    3838#include <typedefs.h>
    3939
    40 #define BITS2BYTES(bits)        (bits ? ((((bits)-1)>>3)+1) : 0)
     40#define BITMAP_ELEMENT   8
     41#define BITMAP_REMAINER  7
    4142
    4243typedef struct {
    43         uint8_t *map;
    44         size_t bits;
     44        size_t elements;
     45        uint8_t *bits;
     46       
     47        size_t block_size;
     48        uint8_t *blocks;
    4549} bitmap_t;
    4650
    47 extern void bitmap_initialize(bitmap_t *bitmap, uint8_t *map, size_t bits);
    48 extern void bitmap_set_range(bitmap_t *bitmap, size_t start, size_t bits);
    49 extern void bitmap_clear_range(bitmap_t *bitmap, size_t start, size_t bits);
    50 extern void bitmap_copy(bitmap_t *dst, bitmap_t *src, size_t bits);
     51static inline void bitmap_set(bitmap_t *bitmap, size_t element,
     52    unsigned int value)
     53{
     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                }
     74        }
     75}
    5176
    52 static inline int bitmap_get(bitmap_t *bitmap, size_t bit)
     77static inline unsigned int bitmap_get(bitmap_t *bitmap, size_t element)
    5378{
    54         if(bit >= bitmap->bits)
     79        if (element >= bitmap->elements)
    5580                return 0;
    5681       
    57         return !! ((bitmap->map)[bit/8] & (1 << (bit & 7)));
     82        return !!((bitmap->bits)[element / BITMAP_ELEMENT] &
     83            (1 << (element & BITMAP_REMAINER)));
    5884}
    5985
     86extern size_t bitmap_size(size_t, size_t);
     87extern void bitmap_initialize(bitmap_t *, size_t, size_t, void *);
     88
     89extern void bitmap_set_range(bitmap_t *, size_t, size_t);
     90extern void bitmap_clear_range(bitmap_t *, size_t, size_t);
     91
     92extern int bitmap_find_range(bitmap_t *, size_t, size_t, size_t);
     93extern int bitmap_allocate_range(bitmap_t *, size_t, size_t, size_t, size_t *);
     94extern void bitmap_free_range(bitmap_t *, size_t, size_t);
     95extern void bitmap_copy(bitmap_t *, bitmap_t *, size_t);
    6096
    6197#endif

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

    r063a74b9 r7de18418  
    3535 *
    3636 * This file implements bitmap ADT and provides functions for
    37  * setting and clearing ranges of bits.
     37 * setting and clearing ranges of bits and for finding ranges
     38 * 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 *
    3847 */
    3948
    … …  
    4453#include <macros.h>
    4554
    46 #define ALL_ONES        0xff
    47 #define ALL_ZEROES      0x00
     55#define ALL_ONES    0xff
     56#define ALL_ZEROES  0x00
     57
     58/** Get bitmap size
     59 *
     60 * Return the size (in bytes) required for the bitmap.
     61 *
     62 * @param elements   Number bits stored in bitmap.
     63 * @param block_size Block size of the 2nd level bitmap.
     64 *                   If set to zero, no 2nd level is used.
     65 *
     66 * @return Size (in bytes) required for the bitmap.
     67 *
     68 */
     69size_t bitmap_size(size_t elements, size_t block_size)
     70{
     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;
     84}
    4885
    4986/** Initialize bitmap.
    … …  
    5188 * No portion of the bitmap is set or cleared by this function.
    5289 *
    53  * @param bitmap        Bitmap structure.
    54  * @param map           Address of the memory used to hold the map.
    55  * @param bits          Number of bits stored in bitmap.
    56  */
    57 void bitmap_initialize(bitmap_t *bitmap, uint8_t *map, size_t bits)
    58 {
    59         bitmap->map = map;
    60         bitmap->bits = bits;
    61 }
    62 
    63 /** Set range of bits.
    64  *
    65  * @param bitmap        Bitmap structure.
    66  * @param start         Starting bit.
    67  * @param bits          Number of bits to set.
    68  */
    69 void bitmap_set_range(bitmap_t *bitmap, size_t start, size_t bits)
    70 {
    71         size_t i = 0;
    72         size_t aligned_start;
    73         size_t lub;     /* leading unaligned bits */
    74         size_t amb;     /* aligned middle bits */
    75         size_t tab;     /* trailing aligned bits */
    76        
    77         ASSERT(start + bits <= bitmap->bits);
    78        
    79         aligned_start = ALIGN_UP(start, 8);
    80         lub = min(aligned_start - start, bits);
    81         amb = bits > lub ? bits - lub : 0;
    82         tab = amb % 8;
    83        
    84         if (!bits)
    85                 return;
    86 
    87         if (start + bits < aligned_start) {
     90 * @param bitmap     Bitmap structure.
     91 * @param elements   Number of bits stored in bitmap.
     92 * @param block_size Block size of the 2nd level bitmap.
     93 *                   If set to zero, no 2nd level is used.
     94 * @param data       Address of the memory used to hold the map.
     95 *                   The optional 2nd level bitmap follows the 1st
     96 *                   level bitmap.
     97 *
     98 */
     99void bitmap_initialize(bitmap_t *bitmap, size_t elements, size_t block_size,
     100    void *data)
     101{
     102        bitmap->elements = elements;
     103        bitmap->bits = (uint8_t *) data;
     104       
     105        if (block_size > 0) {
     106                bitmap->block_size = block_size;
     107                bitmap->blocks = bitmap->bits +
     108                    bitmap_size(elements, 0);
     109        } else {
     110                bitmap->block_size = 0;
     111                bitmap->blocks = NULL;
     112        }
     113}
     114
     115static void bitmap_set_range_internal(uint8_t *bits, size_t start, size_t count)
     116{
     117        if (count == 0)
     118                return;
     119       
     120        size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT);
     121       
     122        /* Leading unaligned bits */
     123        size_t lub = min(aligned_start - start, count);
     124       
     125        /* Aligned middle bits */
     126        size_t amb = (count > lub) ? (count - lub) : 0;
     127       
     128        /* Trailing aligned bits */
     129        size_t tab = amb % BITMAP_ELEMENT;
     130       
     131        if (start + count < aligned_start) {
    88132                /* Set bits in the middle of byte. */
    89                 bitmap->map[start / 8] |= ((1 << lub) - 1) << (start & 7);
     133                bits[start / BITMAP_ELEMENT] |=
     134                    ((1 << lub) - 1) << (start & BITMAP_REMAINER);
    90135                return;
    91136        }
    … …  
    93138        if (lub) {
    94139                /* Make sure to set any leading unaligned bits. */
    95                 bitmap->map[start / 8] |= ~((1 << (8 - lub)) - 1);
    96         }
    97         for (i = 0; i < amb / 8; i++) {
     140                bits[start / BITMAP_ELEMENT] |=
     141                    ~((1 << (BITMAP_ELEMENT - lub)) - 1);
     142        }
     143       
     144        size_t i;
     145       
     146        for (i = 0; i < amb / BITMAP_ELEMENT; i++) {
    98147                /* The middle bits can be set byte by byte. */
    99                 bitmap->map[aligned_start / 8 + i] = ALL_ONES;
    100         }
     148                bits[aligned_start / BITMAP_ELEMENT + i] = ALL_ONES;
     149        }
     150       
    101151        if (tab) {
    102152                /* Make sure to set any trailing aligned bits. */
    103                 bitmap->map[aligned_start / 8 + i] |= (1 << tab) - 1;
    104         }
    105        
    106 }
    107 
    108 /** Clear range of bits.
    109  *
    110  * @param bitmap        Bitmap structure.
    111  * @param start         Starting bit.
    112  * @param bits          Number of bits to clear.
    113  */
    114 void bitmap_clear_range(bitmap_t *bitmap, size_t start, size_t bits)
    115 {
    116         size_t i = 0;
    117         size_t aligned_start;
    118         size_t lub;     /* leading unaligned bits */
    119         size_t amb;     /* aligned middle bits */
    120         size_t tab;     /* trailing aligned bits */
    121        
    122         ASSERT(start + bits <= bitmap->bits);
    123        
    124         aligned_start = ALIGN_UP(start, 8);
    125         lub = min(aligned_start - start, bits);
    126         amb = bits > lub ? bits - lub : 0;
    127         tab = amb % 8;
    128 
    129         if (!bits)
    130                 return;
    131 
    132         if (start + bits < aligned_start) {
     153                bits[aligned_start / BITMAP_ELEMENT + i] |= (1 << tab) - 1;
     154        }
     155}
     156
     157/** Set range of bits.
     158 *
     159 * @param bitmap Bitmap structure.
     160 * @param start  Starting bit.
     161 * @param count  Number of bits to set.
     162 *
     163 */
     164void bitmap_set_range(bitmap_t *bitmap, size_t start, size_t count)
     165{
     166        ASSERT(start + count <= bitmap->elements);
     167       
     168        bitmap_set_range_internal(bitmap->bits, start, count);
     169       
     170        if (bitmap->block_size > 0) {
     171                size_t aligned_start = ALIGN_UP(start, bitmap->block_size);
     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                size_t aligned_size = amb / bitmap->block_size;
     180               
     181                bitmap_set_range_internal(bitmap->blocks, aligned_start,
     182                    aligned_size);
     183        }
     184}
     185
     186static void bitmap_clear_range_internal(uint8_t *bits, size_t start,
     187    size_t count)
     188{
     189        if (count == 0)
     190                return;
     191       
     192        size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT);
     193       
     194        /* Leading unaligned bits */
     195        size_t lub = min(aligned_start - start, count);
     196       
     197        /* Aligned middle bits */
     198        size_t amb = (count > lub) ? (count - lub) : 0;
     199       
     200        /* Trailing aligned bits */
     201        size_t tab = amb % BITMAP_ELEMENT;
     202       
     203        if (start + count < aligned_start) {
    133204                /* Set bits in the middle of byte */
    134                 bitmap->map[start / 8] &= ~(((1 << lub) - 1) << (start & 7));
    135                 return;
    136         }
    137 
     205                bits[start / BITMAP_ELEMENT] &=
     206                    ~(((1 << lub) - 1) << (start & BITMAP_REMAINER));
     207                return;
     208        }
     209       
    138210        if (lub) {
    139211                /* Make sure to clear any leading unaligned bits. */
    140                 bitmap->map[start / 8] &= (1 << (8 - lub)) - 1;
    141         }
    142         for (i = 0; i < amb / 8; i++) {
     212                bits[start / BITMAP_ELEMENT] &=
     213                    (1 << (BITMAP_ELEMENT - lub)) - 1;
     214        }
     215       
     216        size_t i;
     217       
     218        for (i = 0; i < amb / BITMAP_ELEMENT; i++) {
    143219                /* The middle bits can be cleared byte by byte. */
    144                 bitmap->map[aligned_start / 8 + i] = ALL_ZEROES;
    145         }
     220                bits[aligned_start / BITMAP_ELEMENT + i] = ALL_ZEROES;
     221        }
     222       
    146223        if (tab) {
    147224                /* Make sure to clear any trailing aligned bits. */
    148                 bitmap->map[aligned_start / 8 + i] &= ~((1 << tab) - 1);
    149         }
    150 
     225                bits[aligned_start / BITMAP_ELEMENT + i] &= ~((1 << tab) - 1);
     226        }
     227}
     228
     229/** Clear range of bits.
     230 *
     231 * @param bitmap Bitmap structure.
     232 * @param start  Starting bit.
     233 * @param count  Number of bits to clear.
     234 *
     235 */
     236void bitmap_clear_range(bitmap_t *bitmap, size_t start, size_t count)
     237{
     238        ASSERT(start + count <= bitmap->elements);
     239       
     240        bitmap_clear_range_internal(bitmap->bits, start, count);
     241       
     242        if (bitmap->block_size > 0) {
     243                size_t aligned_start = start / bitmap->block_size;
     244               
     245                size_t aligned_end = (start + count) / bitmap->block_size;
     246               
     247                if (((start + count) % bitmap->block_size) != 0)
     248                        aligned_end++;
     249               
     250                size_t aligned_size = aligned_end - aligned_start;
     251               
     252                bitmap_clear_range_internal(bitmap->blocks, aligned_start,
     253                    aligned_size);
     254        }
    151255}
    152256
    153257/** Copy portion of one bitmap into another bitmap.
    154258 *
    155  * @param dst           Destination bitmap.
    156  * @param src           Source bitmap.
    157  * @param bits          Number of bits to copy.
    158  */
    159 void bitmap_copy(bitmap_t *dst, bitmap_t *src, size_t bits)
    160 {
     259 * @param dst   Destination bitmap.
     260 * @param src   Source bitmap.
     261 * @param count Number of bits to copy.
     262 *
     263 */
     264void bitmap_copy(bitmap_t *dst, bitmap_t *src, size_t count)
     265{
     266        ASSERT(count <= dst->elements);
     267        ASSERT(count <= src->elements);
     268       
    161269        size_t i;
    162270       
    163         ASSERT(bits <= dst->bits);
    164         ASSERT(bits <= src->bits);
    165        
    166         for (i = 0; i < bits / 8; i++)
    167                 dst->map[i] = src->map[i];
    168        
    169         if (bits % 8) {
    170                 bitmap_clear_range(dst, i * 8, bits % 8);
    171                 dst->map[i] |= src->map[i] & ((1 << (bits % 8)) - 1);
     271        for (i = 0; i < count / BITMAP_ELEMENT; i++)
     272                dst->bits[i] = src->bits[i];
     273       
     274        if (count % BITMAP_ELEMENT) {
     275                bitmap_clear_range(dst, i * BITMAP_ELEMENT,
     276                    count % BITMAP_ELEMENT);
     277                dst->bits[i] |= src->bits[i] &
     278                    ((1 << (count % BITMAP_ELEMENT)) - 1);
    172279        }
    173280}
Note: See TracChangeset for help on using the changeset viewer.