Changeset b0c2075 in mainline for kernel/generic/src/mm/frame.c


Ignore:
Timestamp:
2013-09-10T17:48:57Z (11 years ago)
Author:
Martin Decky <martin@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
85147f3
Parents:
86733f3
Message:

new physical memory allocator supporting physical address constrains
the buddy allocator framework is retired and replaced by a two-level bitmap
the allocator can allocate an arbitrary number of frames, not only a power-of-two count

Caution: Change of semantics
The physical memory allocator no longer allocates naturally aligned blocks. If you require an aligned block, specify it as the constraint.

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r86733f3 rb0c2075  
    3838 *
    3939 * This file contains the physical frame allocator and memory zone management.
    40  * The frame allocator is built on top of the buddy allocator.
    41  *
    42  * @see buddy.c
     40 * The frame allocator is built on top of the two-level bitmap structure.
     41 *
    4342 */
    4443
    … …  
    6261#include <str.h>
    6362
     63#define BITMAP_BLOCK_SIZE  1024
     64
    6465zones_t zones;
    6566
    … …  
    9293}
    9394
    94 NO_TRACE static inline size_t make_frame_index(zone_t *zone, frame_t *frame)
    95 {
    96         return (frame - zone->frames);
    97 }
    98 
    9995/** Initialize frame structure.
    10096 *
    … …  
    104100NO_TRACE static void frame_initialize(frame_t *frame)
    105101{
    106         frame->refcount = 1;
    107         frame->buddy_order = 0;
     102        frame->refcount = 0;
     103        frame->parent = NULL;
    108104}
    109105
    … …  
    161157       
    162158        /* Move other zones up */
    163         size_t j;
    164         for (j = zones.count; j > i; j--) {
     159        for (size_t j = zones.count; j > i; j--)
    165160                zones.info[j] = zones.info[j - 1];
    166                 if (zones.info[j].buddy_system != NULL)
    167                         zones.info[j].buddy_system->data =
    168                             (void *) &zones.info[j];
    169         }
    170161       
    171162        zones.count++;
    … …  
    237228}
    238229
    239 /** @return True if zone can allocate specified order */
    240 NO_TRACE static bool zone_can_alloc(zone_t *zone, uint8_t order)
    241 {
     230/** @return True if zone can allocate specified number of frames */
     231NO_TRACE static bool zone_can_alloc(zone_t *zone, size_t count,
     232    pfn_t constraint)
     233{
     234        /*
     235         * The function bitmap_allocate_range() does not modify
     236         * the bitmap if the last argument is NULL.
     237         */
    242238        return ((zone->flags & ZONE_AVAILABLE) &&
    243             buddy_system_can_alloc(zone->buddy_system, order));
    244 }
    245 
    246 /** Find a zone that can allocate order frames.
     239            bitmap_allocate_range(&zone->bitmap, count, zone->base,
     240            constraint, NULL));
     241}
     242
     243/** Find a zone that can allocate specified number of frames
    247244 *
    248245 * Assume interrupts are disabled and zones lock is
    249246 * locked.
    250247 *
    251  * @param order Size (2^order) of free space we are trying to find.
    252  * @param flags Required flags of the target zone.
    253  * @param hind  Preferred zone.
    254  *
    255  */
    256 NO_TRACE static size_t find_free_zone(uint8_t order, zone_flags_t flags,
    257     size_t hint)
     248 * @param count      Number of free frames we are trying to find.
     249 * @param flags      Required flags of the target zone.
     250 * @param constraint Indication of bits that cannot be set in the
     251 *                   physical frame number of the first allocated frame.
     252 * @param hind       Preferred zone.
     253 *
     254 */
     255NO_TRACE static size_t find_free_zone(size_t count, zone_flags_t flags,
     256    pfn_t constraint, size_t hint)
    258257{
    259258        if (hint >= zones.count)
    … …  
    267266                if (ZONE_FLAGS_MATCH(zones.info[i].flags, flags)) {
    268267                        /*
    269                          * Check if the zone has 2^order frames area available.
     268                         * Check if the zone can satisfy the allocation request.
    270269                         */
    271                         if (zone_can_alloc(&zones.info[i], order))
     270                        if (zone_can_alloc(&zones.info[i], count, constraint))
    272271                                return i;
    273272                }
    … …  
    282281}
    283282
    284 /**************************/
    285 /* Buddy system functions */
    286 /**************************/
    287 
    288 /** Buddy system find_block implementation.
    289  *
    290  * Find block that is parent of current list.
    291  * That means go to lower addresses, until such block is found
    292  *
    293  * @param order Order of parent must be different then this
    294  *              parameter!!
    295  *
    296  */
    297 NO_TRACE static link_t *zone_buddy_find_block(buddy_system_t *buddy,
    298     link_t *child, uint8_t order)
    299 {
    300         frame_t *frame = list_get_instance(child, frame_t, buddy_link);
    301         zone_t *zone = (zone_t *) buddy->data;
    302        
    303         size_t index = frame_index(zone, frame);
    304         do {
    305                 if (zone->frames[index].buddy_order != order)
    306                         return &zone->frames[index].buddy_link;
    307         } while (index-- > 0);
    308        
    309         return NULL;
    310 }
    311 
    312 /** Buddy system find_buddy implementation.
    313  *
    314  * @param buddy Buddy system.
    315  * @param block Block for which buddy should be found.
    316  *
    317  * @return Buddy for given block if found.
    318  *
    319  */
    320 NO_TRACE static link_t *zone_buddy_find_buddy(buddy_system_t *buddy,
    321     link_t *block)
    322 {
    323         frame_t *frame = list_get_instance(block, frame_t, buddy_link);
    324         zone_t *zone = (zone_t *) buddy->data;
    325         ASSERT(IS_BUDDY_ORDER_OK(frame_index_abs(zone, frame),
    326             frame->buddy_order));
    327        
    328         bool is_left = IS_BUDDY_LEFT_BLOCK_ABS(zone, frame);
    329        
    330         size_t index;
    331         if (is_left) {
    332                 index = (frame_index(zone, frame)) +
    333                     (1 << frame->buddy_order);
    334         } else {  /* is_right */
    335                 index = (frame_index(zone, frame)) -
    336                     (1 << frame->buddy_order);
    337         }
    338        
    339         if (frame_index_valid(zone, index)) {
    340                 if ((zone->frames[index].buddy_order == frame->buddy_order) &&
    341                     (zone->frames[index].refcount == 0)) {
    342                         return &zone->frames[index].buddy_link;
    343                 }
    344         }
    345        
    346         return NULL;
    347 }
    348 
    349 /** Buddy system bisect implementation.
    350  *
    351  * @param buddy Buddy system.
    352  * @param block Block to bisect.
    353  *
    354  * @return Right block.
    355  *
    356  */
    357 NO_TRACE static link_t *zone_buddy_bisect(buddy_system_t *buddy, link_t *block)
    358 {
    359         frame_t *frame_l = list_get_instance(block, frame_t, buddy_link);
    360         frame_t *frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));
    361        
    362         return &frame_r->buddy_link;
    363 }
    364 
    365 /** Buddy system coalesce implementation.
    366  *
    367  * @param buddy   Buddy system.
    368  * @param block_1 First block.
    369  * @param block_2 First block's buddy.
    370  *
    371  * @return Coalesced block (actually block that represents lower
    372  *         address).
    373  *
    374  */
    375 NO_TRACE static link_t *zone_buddy_coalesce(buddy_system_t *buddy,
    376     link_t *block_1, link_t *block_2)
    377 {
    378         frame_t *frame1 = list_get_instance(block_1, frame_t, buddy_link);
    379         frame_t *frame2 = list_get_instance(block_2, frame_t, buddy_link);
    380        
    381         return ((frame1 < frame2) ? block_1 : block_2);
    382 }
    383 
    384 /** Buddy system set_order implementation.
    385  *
    386  * @param buddy Buddy system.
    387  * @param block Buddy system block.
    388  * @param order Order to set.
    389  *
    390  */
    391 NO_TRACE static void zone_buddy_set_order(buddy_system_t *buddy, link_t *block,
    392     uint8_t order)
    393 {
    394         list_get_instance(block, frame_t, buddy_link)->buddy_order = order;
    395 }
    396 
    397 /** Buddy system get_order implementation.
    398  *
    399  * @param buddy Buddy system.
    400  * @param block Buddy system block.
    401  *
    402  * @return Order of block.
    403  *
    404  */
    405 NO_TRACE static uint8_t zone_buddy_get_order(buddy_system_t *buddy,
    406     link_t *block)
    407 {
    408         return list_get_instance(block, frame_t, buddy_link)->buddy_order;
    409 }
    410 
    411 /** Buddy system mark_busy implementation.
    412  *
    413  * @param buddy Buddy system.
    414  * @param block Buddy system block.
    415  *
    416  */
    417 NO_TRACE static void zone_buddy_mark_busy(buddy_system_t *buddy, link_t *block)
    418 {
    419         list_get_instance(block, frame_t, buddy_link)->refcount = 1;
    420 }
    421 
    422 /** Buddy system mark_available implementation.
    423  *
    424  * @param buddy Buddy system.
    425  * @param block Buddy system block.
    426  *
    427  */
    428 NO_TRACE static void zone_buddy_mark_available(buddy_system_t *buddy,
    429     link_t *block)
    430 {
    431         list_get_instance(block, frame_t, buddy_link)->refcount = 0;
    432 }
    433 
    434 static buddy_system_operations_t zone_buddy_system_operations = {
    435         .find_buddy = zone_buddy_find_buddy,
    436         .bisect = zone_buddy_bisect,
    437         .coalesce = zone_buddy_coalesce,
    438         .set_order = zone_buddy_set_order,
    439         .get_order = zone_buddy_get_order,
    440         .mark_busy = zone_buddy_mark_busy,
    441         .mark_available = zone_buddy_mark_available,
    442         .find_block = zone_buddy_find_block
    443 };
    444 
    445283/******************/
    446284/* Zone functions */
    447285/******************/
    448286
     287/** Return frame from zone. */
     288NO_TRACE static frame_t *zone_get_frame(zone_t *zone, size_t index)
     289{
     290        ASSERT(index < zone->count);
     291       
     292        return &zone->frames[index];
     293}
     294
    449295/** Allocate frame in particular zone.
    450296 *
    … …  
    452298 * Panics if allocation is impossible.
    453299 *
    454  * @param zone  Zone to allocate from.
    455  * @param order Allocate exactly 2^order frames.
     300 * @param zone       Zone to allocate from.
     301 * @param count      Number of frames to allocate
     302 * @param constraint Indication of bits that cannot be set in the
     303 *                   physical frame number of the first allocated frame.
    456304 *
    457305 * @return Frame index in zone.
    458306 *
    459307 */
    460 NO_TRACE static pfn_t zone_frame_alloc(zone_t *zone, uint8_t order)
     308NO_TRACE static size_t zone_frame_alloc(zone_t *zone, size_t count,
     309    pfn_t constraint)
    461310{
    462311        ASSERT(zone->flags & ZONE_AVAILABLE);
    463312       
    464         /* Allocate frames from zone buddy system */
    465         link_t *link = buddy_system_alloc(zone->buddy_system, order);
    466        
    467         ASSERT(link);
     313        /* Allocate frames from zone */
     314        size_t index;
     315        int avail = bitmap_allocate_range(&zone->bitmap, count, zone->base,
     316            constraint, &index);
     317       
     318        ASSERT(avail);
     319       
     320        /* Update frame reference count */
     321        for (size_t i = 0; i < count; i++) {
     322                frame_t *frame = zone_get_frame(zone, index + i);
     323               
     324                ASSERT(frame->refcount == 0);
     325                frame->refcount = 1;
     326        }
    468327       
    469328        /* Update zone information. */
    470         zone->free_count -= (1 << order);
    471         zone->busy_count += (1 << order);
    472        
    473         /* Frame will be actually a first frame of the block. */
    474         frame_t *frame = list_get_instance(link, frame_t, buddy_link);
    475        
    476         /* Get frame address */
    477         return make_frame_index(zone, frame);
     329        zone->free_count -= count;
     330        zone->busy_count += count;
     331       
     332        return index;
    478333}
    479334
    … …  
    482337 * Assume zone is locked and is available for deallocation.
    483338 *
    484  * @param zone      Pointer to zone from which the frame is to be freed.
    485  * @param frame_idx Frame index relative to zone.
    486  *
    487  * @return          Number of freed frames.
    488  *
    489  */
    490 NO_TRACE static size_t zone_frame_free(zone_t *zone, size_t frame_idx)
     339 * @param zone  Pointer to zone from which the frame is to be freed.
     340 * @param index Frame index relative to zone.
     341 *
     342 * @return Number of freed frames.
     343 *
     344 */
     345NO_TRACE static size_t zone_frame_free(zone_t *zone, size_t index)
    491346{
    492347        ASSERT(zone->flags & ZONE_AVAILABLE);
    493348       
    494         frame_t *frame = &zone->frames[frame_idx];
     349        frame_t *frame = zone_get_frame(zone, index);
    495350        size_t size = 0;
    496351       
    497         ASSERT(frame->refcount);
     352        ASSERT(frame->refcount > 0);
    498353       
    499354        if (!--frame->refcount) {
    500                 size = 1 << frame->buddy_order;
    501                 buddy_system_free(zone->buddy_system, &frame->buddy_link);             
     355                bitmap_free_range(&zone->bitmap, index, 1);
     356               
    502357                /* Update zone information. */
    503                 zone->free_count += size;
    504                 zone->busy_count -= size;
     358                zone->free_count++;
     359                zone->busy_count--;
     360               
     361                size = FRAME_SIZE;
    505362        }
    506363       
    … …  
    508365}
    509366
    510 /** Return frame from zone. */
    511 NO_TRACE static frame_t *zone_get_frame(zone_t *zone, size_t frame_idx)
    512 {
    513         ASSERT(frame_idx < zone->count);
    514         return &zone->frames[frame_idx];
    515 }
    516 
    517367/** Mark frame in zone unavailable to allocation. */
    518 NO_TRACE static void zone_mark_unavailable(zone_t *zone, size_t frame_idx)
     368NO_TRACE static void zone_mark_unavailable(zone_t *zone, size_t index)
    519369{
    520370        if (!(zone->flags & ZONE_AVAILABLE))
    521371                return;
    522 //      ASSERT(zone->flags & ZONE_AVAILABLE);
    523        
    524         frame_t *frame = zone_get_frame(zone, frame_idx);
    525         if (frame->refcount)
     372       
     373        frame_t *frame = zone_get_frame(zone, index);
     374        if (frame->refcount > 0)
    526375                return;
    527376       
    528         link_t *link __attribute__ ((unused));
    529        
    530         link = buddy_system_alloc_block(zone->buddy_system,
    531             &frame->buddy_link);
    532        
    533         ASSERT(link);
     377        bitmap_set_range(&zone->bitmap, index, 1);
     378       
    534379        zone->free_count--;
    535380        reserve_force_alloc(1);
    … …  
    538383/** Merge two zones.
    539384 *
    540  * Expect buddy to point to space at least zone_conf_size large.
    541385 * Assume z1 & z2 are locked and compatible and zones lock is
    542386 * locked.
    543387 *
    544  * @param z1     First zone to merge.
    545  * @param z2     Second zone to merge.
    546  * @param old_z1 Original date of the first zone.
    547  * @param buddy  Merged zone buddy.
     388 * @param z1       First zone to merge.
     389 * @param z2       Second zone to merge.
     390 * @param old_z1   Original data of the first zone.
     391 * @param confdata Merged zone configuration data.
    548392 *
    549393 */
    550394NO_TRACE static void zone_merge_internal(size_t z1, size_t z2, zone_t *old_z1,
    551     buddy_system_t *buddy)
     395    void *confdata)
    552396{
    553397        ASSERT(zones.info[z1].flags & ZONE_AVAILABLE);
    … …  
    564408        zones.info[z1].free_count += zones.info[z2].free_count;
    565409        zones.info[z1].busy_count += zones.info[z2].busy_count;
    566         zones.info[z1].buddy_system = buddy;
    567        
    568         uint8_t order = fnzb(zones.info[z1].count);
    569         buddy_system_create(zones.info[z1].buddy_system, order,
    570             &zone_buddy_system_operations, (void *) &zones.info[z1]);
    571        
    572         zones.info[z1].frames =
    573             (frame_t *) ((uint8_t *) zones.info[z1].buddy_system
    574             + buddy_conf_size(order));
    575        
    576         /* This marks all frames busy */
    577         size_t i;
    578         for (i = 0; i < zones.info[z1].count; i++)
    579                 frame_initialize(&zones.info[z1].frames[i]);
    580        
    581         /* Copy frames from both zones to preserve full frame orders,
    582          * parents etc. Set all free frames with refcount = 0 to 1, because
    583          * we add all free frames to buddy allocator later again, clearing
    584          * order to 0. Don't set busy frames with refcount = 0, as they
    585          * will not be reallocated during merge and it would make later
    586          * problems with allocation/free.
     410       
     411        bitmap_initialize(&zones.info[z1].bitmap, zones.info[z1].count,
     412            BITMAP_BLOCK_SIZE, confdata +
     413            (sizeof(frame_t) * zones.info[z1].count));
     414       
     415        zones.info[z1].frames = (frame_t *) confdata;
     416       
     417        /*
     418         * Copy frames and bits from both zones to preserve parents, etc.
    587419         */
    588         for (i = 0; i < old_z1->count; i++)
     420       
     421        for (size_t i = 0; i < old_z1->count; i++) {
     422                bitmap_set(&zones.info[z1].bitmap, i,
     423                    bitmap_get(&old_z1->bitmap, i));
    589424                zones.info[z1].frames[i] = old_z1->frames[i];
    590        
    591         for (i = 0; i < zones.info[z2].count; i++)
    592                 zones.info[z1].frames[base_diff + i]
    593                     = zones.info[z2].frames[i];
    594        
    595         i = 0;
    596         while (i < zones.info[z1].count) {
    597                 if (zones.info[z1].frames[i].refcount) {
    598                         /* Skip busy frames */
    599                         i += 1 << zones.info[z1].frames[i].buddy_order;
    600                 } else {
    601                         /* Free frames, set refcount = 1
    602                          * (all free frames have refcount == 0, we need not
    603                          * to check the order)
    604                          */
    605                         zones.info[z1].frames[i].refcount = 1;
    606                         zones.info[z1].frames[i].buddy_order = 0;
    607                         i++;
    608                 }
    609         }
    610        
    611         /* Add free blocks from the original zone z1 */
    612         while (zone_can_alloc(old_z1, 0)) {
    613                 /* Allocate from the original zone */
    614                 pfn_t frame_idx = zone_frame_alloc(old_z1, 0);
    615                
    616                 /* Free the frame from the merged zone */
    617                 frame_t *frame = &zones.info[z1].frames[frame_idx];
    618                 frame->refcount = 0;
    619                 buddy_system_free(zones.info[z1].buddy_system, &frame->buddy_link);
    620         }
    621        
    622         /* Add free blocks from the original zone z2 */
    623         while (zone_can_alloc(&zones.info[z2], 0)) {
    624                 /* Allocate from the original zone */
    625                 pfn_t frame_idx = zone_frame_alloc(&zones.info[z2], 0);
    626                
    627                 /* Free the frame from the merged zone */
    628                 frame_t *frame = &zones.info[z1].frames[base_diff + frame_idx];
    629                 frame->refcount = 0;
    630                 buddy_system_free(zones.info[z1].buddy_system, &frame->buddy_link);
     425        }
     426       
     427        for (size_t i = 0; i < zones.info[z2].count; i++) {
     428                bitmap_set(&zones.info[z1].bitmap, base_diff + i,
     429                    bitmap_get(&zones.info[z2].bitmap, i));
     430                zones.info[z1].frames[base_diff + i] =
     431                    zones.info[z2].frames[i];
    631432        }
    632433}
    … …  
    651452        size_t cframes = SIZE2FRAMES(zone_conf_size(count));
    652453       
    653         if ((pfn < zones.info[znum].base)
    654             || (pfn >= zones.info[znum].base + zones.info[znum].count))
     454        if ((pfn < zones.info[znum].base) ||
     455            (pfn >= zones.info[znum].base + zones.info[znum].count))
    655456                return;
    656457       
    657         frame_t *frame __attribute__ ((unused));
    658 
    659         frame = &zones.info[znum].frames[pfn - zones.info[znum].base];
    660         ASSERT(!frame->buddy_order);
    661        
    662         size_t i;
    663         for (i = 0; i < cframes; i++) {
    664                 zones.info[znum].busy_count++;
     458        for (size_t i = 0; i < cframes; i++)
    665459                (void) zone_frame_free(&zones.info[znum],
    666460                    pfn - zones.info[znum].base + i);
    667         }
    668 }
    669 
    670 /** Reduce allocated block to count of order 0 frames.
    671  *
    672  * The allocated block needs 2^order frames. Reduce all frames
    673  * in the block to order 0 and free the unneeded frames. This means that
    674  * when freeing the previously allocated block starting with frame_idx,
    675  * you have to free every frame.
    676  *
    677  * @param znum      Zone.
    678  * @param frame_idx Index the first frame of the block.
    679  * @param count     Allocated frames in block.
    680  *
    681  */
    682 NO_TRACE static void zone_reduce_region(size_t znum, pfn_t frame_idx,
    683     size_t count)
    684 {
    685         ASSERT(zones.info[znum].flags & ZONE_AVAILABLE);
    686         ASSERT(frame_idx + count < zones.info[znum].count);
    687        
    688         uint8_t order = zones.info[znum].frames[frame_idx].buddy_order;
    689         ASSERT((size_t) (1 << order) >= count);
    690        
    691         /* Reduce all blocks to order 0 */
    692         size_t i;
    693         for (i = 0; i < (size_t) (1 << order); i++) {
    694                 frame_t *frame = &zones.info[znum].frames[i + frame_idx];
    695                 frame->buddy_order = 0;
    696                 if (!frame->refcount)
    697                         frame->refcount = 1;
    698                 ASSERT(frame->refcount == 1);
    699         }
    700        
    701         /* Free unneeded frames */
    702         for (i = count; i < (size_t) (1 << order); i++)
    703                 (void) zone_frame_free(&zones.info[znum], i + frame_idx);
    704461}
    705462
    … …  
    721478        bool ret = true;
    722479       
    723         /* We can join only 2 zones with none existing inbetween,
     480        /*
     481         * We can join only 2 zones with none existing inbetween,
    724482         * the zones have to be available and with the same
    725483         * set of flags
    … …  
    735493            + zones.info[z2].count));
    736494       
    737         uint8_t order;
    738         if (cframes == 1)
    739                 order = 0;
    740         else
    741                 order = fnzb(cframes - 1) + 1;
    742        
    743495        /* Allocate merged zone data inside one of the zones */
    744496        pfn_t pfn;
    745         if (zone_can_alloc(&zones.info[z1], order)) {
    746                 pfn = zones.info[z1].base + zone_frame_alloc(&zones.info[z1], order);
    747         } else if (zone_can_alloc(&zones.info[z2], order)) {
    748                 pfn = zones.info[z2].base + zone_frame_alloc(&zones.info[z2], order);
     497        if (zone_can_alloc(&zones.info[z1], cframes, 0)) {
     498                pfn = zones.info[z1].base +
     499                    zone_frame_alloc(&zones.info[z1], cframes, 0);
     500        } else if (zone_can_alloc(&zones.info[z2], cframes, 0)) {
     501                pfn = zones.info[z2].base +
     502                    zone_frame_alloc(&zones.info[z2], cframes, 0);
    749503        } else {
    750504                ret = false;
    … …  
    754508        /* Preserve original data from z1 */
    755509        zone_t old_z1 = zones.info[z1];
    756         old_z1.buddy_system->data = (void *) &old_z1;
    757510       
    758511        /* Do zone merging */
    759         buddy_system_t *buddy = (buddy_system_t *) PA2KA(PFN2ADDR(pfn));
    760         zone_merge_internal(z1, z2, &old_z1, buddy);
    761        
    762         /* Free unneeded config frames */
    763         zone_reduce_region(z1, pfn - zones.info[z1].base, cframes);
     512        zone_merge_internal(z1, z2, &old_z1, (void *) PA2KA(PFN2ADDR(pfn)));
    764513       
    765514        /* Subtract zone information from busy frames */
    … …  
    774523       
    775524        /* Move zones down */
    776         size_t i;
    777         for (i = z2 + 1; i < zones.count; i++) {
     525        for (size_t i = z2 + 1; i < zones.count; i++)
    778526                zones.info[i - 1] = zones.info[i];
    779                 if (zones.info[i - 1].buddy_system != NULL)
    780                         zones.info[i - 1].buddy_system->data =
    781                             (void *) &zones.info[i - 1];
    782         }
    783527       
    784528        zones.count--;
    … …  
    799543void zone_merge_all(void)
    800544{
    801         size_t i = 0;
     545        size_t i = 1;
     546       
    802547        while (i < zones.count) {
    803                 if (!zone_merge(i, i + 1))
     548                if (!zone_merge(i - 1, i))
    804549                        i++;
    805550        }
    … …  
    808553/** Create new frame zone.
    809554 *
    810  * @param zone  Zone to construct.
    811  * @param buddy Address of buddy system configuration information.
    812  * @param start Physical address of the first frame within the zone.
    813  * @param count Count of frames in zone.
    814  * @param flags Zone flags.
     555 * @param zone     Zone to construct.
     556 * @param start    Physical address of the first frame within the zone.
     557 * @param count    Count of frames in zone.
     558 * @param flags    Zone flags.
     559 * @param confdata Configuration data of the zone.
    815560 *
    816561 * @return Initialized zone.
    817562 *
    818563 */
    819 NO_TRACE static void zone_construct(zone_t *zone, buddy_system_t *buddy,
    820     pfn_t start, size_t count, zone_flags_t flags)
     564NO_TRACE static void zone_construct(zone_t *zone, pfn_t start, size_t count,
     565    zone_flags_t flags, void *confdata)
    821566{
    822567        zone->base = start;
    … …  
    825570        zone->free_count = count;
    826571        zone->busy_count = 0;
    827         zone->buddy_system = buddy;
    828572       
    829573        if (flags & ZONE_AVAILABLE) {
    830574                /*
    831                  * Compute order for buddy system and initialize
     575                 * Initialize frame bitmap (located after the array of
     576                 * frame_t structures in the configuration space).
    832577                 */
    833                 uint8_t order = fnzb(count);
    834                 buddy_system_create(zone->buddy_system, order,
    835                     &zone_buddy_system_operations, (void *) zone);
    836                
    837                 /* Allocate frames _after_ the confframe */
    838                
    839                 /* Check sizes */
    840                 zone->frames = (frame_t *) ((uint8_t *) zone->buddy_system +
    841                     buddy_conf_size(order));
    842                
    843                 size_t i;
    844                 for (i = 0; i < count; i++)
     578               
     579                bitmap_initialize(&zone->bitmap, count, BITMAP_BLOCK_SIZE,
     580                    confdata + (sizeof(frame_t) * count));
     581               
     582                /*
     583                 * Initialize the array of frame_t structures.
     584                 */
     585               
     586                zone->frames = (frame_t *) confdata;
     587               
     588                for (size_t i = 0; i < count; i++)
    845589                        frame_initialize(&zone->frames[i]);
    846                
    847                 /* Stuffing frames */
    848                 for (i = 0; i < count; i++) {
    849                         zone->frames[i].refcount = 0;
    850                         buddy_system_free(zone->buddy_system, &zone->frames[i].buddy_link);
    851                 }
    852         } else
     590        } else {
     591                bitmap_initialize(&zone->bitmap, 0, 0, NULL);
    853592                zone->frames = NULL;
     593        }
    854594}
    855595
    … …  
    863603size_t zone_conf_size(size_t count)
    864604{
    865         return (count * sizeof(frame_t) + buddy_conf_size(fnzb(count)));
     605        return (count * sizeof(frame_t) +
     606            bitmap_size(count, BITMAP_BLOCK_SIZE));
    866607}
    867608
    … …  
    869610pfn_t zone_external_conf_alloc(size_t count)
    870611{
    871         size_t size = zone_conf_size(count);
    872         size_t order = ispwr2(size) ? fnzb(size) : (fnzb(size) + 1);
    873 
    874         return ADDR2PFN((uintptr_t) frame_alloc(order - FRAME_WIDTH,
    875             FRAME_LOWMEM | FRAME_ATOMIC, 0));
     612        size_t frames = SIZE2FRAMES(zone_conf_size(count));
     613       
     614        return ADDR2PFN((uintptr_t)
     615            frame_alloc(frames, FRAME_LOWMEM | FRAME_ATOMIC, 0));
    876616}
    877617
    … …  
    881621 * @param count     Size of zone in frames.
    882622 * @param confframe Where configuration frames are supposed to be.
    883  *                  Automatically checks, that we will not disturb the
     623 *                  Automatically checks that we will not disturb the
    884624 *                  kernel and possibly init. If confframe is given
    885625 *                  _outside_ this zone, it is expected, that the area is
    … …  
    898638       
    899639        if (flags & ZONE_AVAILABLE) {  /* Create available zone */
    900                 /* Theoretically we could have NULL here, practically make sure
     640                /*
     641                 * Theoretically we could have NULL here, practically make sure
    901642                 * nobody tries to do that. If some platform requires, remove
    902643                 * the assert
    903644                 */
    904645                ASSERT(confframe != ADDR2PFN((uintptr_t ) NULL));
    905 
     646               
    906647                /* Update the known end of physical memory. */
    907648                config.physmem_end = max(config.physmem_end, PFN2ADDR(start + count));
    908649               
    909                 /* If confframe is supposed to be inside our zone, then make sure
     650                /*
     651                 * If confframe is supposed to be inside our zone, then make sure
    910652                 * it does not span kernel & init
    911653                 */
    912654                size_t confcount = SIZE2FRAMES(zone_conf_size(count));
     655               
    913656                if ((confframe >= start) && (confframe < start + count)) {
    914657                        for (; confframe < start + count; confframe++) {
    … …  
    923666                               
    924667                                bool overlap = false;
    925                                 size_t i;
    926                                 for (i = 0; i < init.cnt; i++)
     668                                for (size_t i = 0; i < init.cnt; i++) {
    927669                                        if (overlaps(addr, PFN2ADDR(confcount),
    928670                                            init.tasks[i].paddr,
    … …  
    931673                                                break;
    932674                                        }
     675                                }
     676                               
    933677                                if (overlap)
    934678                                        continue;
    … …  
    937681                        }
    938682                       
    939                         if (confframe >= start + count) {
    940                                 flags &= ~ZONE_AVAILABLE;
    941                                 goto nonavail;
    942 //                              panic("Cannot find configuration data for zone.");
    943                         }
     683                        if (confframe >= start + count)
     684                                panic("Cannot find configuration data for zone.");
    944685                }
    945686               
    … …  
    950691                }
    951692               
    952                 buddy_system_t *buddy = (buddy_system_t *) PA2KA(PFN2ADDR(confframe));
    953                 zone_construct(&zones.info[znum], buddy, start, count, flags);
     693                void *confdata = (void *) PA2KA(PFN2ADDR(confframe));
     694                zone_construct(&zones.info[znum], start, count, flags, confdata);
    954695               
    955696                /* If confdata in zone, mark as unavailable */
    956697                if ((confframe >= start) && (confframe < start + count)) {
    957                         size_t i;
    958                         for (i = confframe; i < confframe + confcount; i++)
     698                        for (size_t i = confframe; i < confframe + confcount; i++)
    959699                                zone_mark_unavailable(&zones.info[znum],
    960700                                    i - zones.info[znum].base);
    … …  
    965705                return znum;
    966706        }
    967 nonavail:
    968         (void)0; // label trick
     707       
    969708        /* Non-available zone */
    970709        size_t znum = zones_insert_zone(start, count, flags);
    … …  
    973712                return (size_t) -1;
    974713        }
    975         zone_construct(&zones.info[znum], NULL, start, count, flags);
     714       
     715        zone_construct(&zones.info[znum], start, count, flags, NULL);
    976716       
    977717        irq_spinlock_unlock(&zones.lock, true);
    … …  
    1015755}
    1016756
    1017 /** Allocate power-of-two frames of physical memory.
    1018  *
    1019  * @param order Allocate exactly 2^order frames.
    1020  * @param flags Flags for host zone selection and address processing.
    1021  * @param pzone Preferred zone.
     757/** Allocate frames of physical memory.
     758 *
     759 * @param count      Number of continuous frames to allocate.
     760 * @param flags      Flags for host zone selection and address processing.
     761 * @param constraint Indication of physical address bits that cannot be
     762 *                   set in the address of the first allocated frame.
     763 * @param pzone      Preferred zone.
    1022764 *
    1023765 * @return Physical address of the allocated frame.
    1024766 *
    1025767 */
    1026 uintptr_t frame_alloc_generic(uint8_t order, frame_flags_t flags,
     768uintptr_t frame_alloc_generic(size_t count, frame_flags_t flags,
    1027769    uintptr_t constraint, size_t *pzone)
    1028770{
    1029         size_t size = ((size_t) 1) << order;
     771        ASSERT(count > 0);
     772       
    1030773        size_t hint = pzone ? (*pzone) : 0;
     774        pfn_t frame_constraint = ADDR2PFN(constraint);
    1031775       
    1032776        /*
    1033777         * If not told otherwise, we must first reserve the memory.
    1034778         */
    1035         if (!(flags & FRAME_NO_RESERVE)) 
    1036                 reserve_force_alloc(size);
    1037 
     779        if (!(flags & FRAME_NO_RESERVE))
     780                reserve_force_alloc(count);
     781       
    1038782loop:
    1039783        irq_spinlock_lock(&zones.lock, true);
    … …  
    1042786         * First, find suitable frame zone.
    1043787         */
    1044         size_t znum = find_free_zone(order,
    1045             FRAME_TO_ZONE_FLAGS(flags), hint);
    1046        
    1047         /* If no memory, reclaim some slab memory,
    1048            if it does not help, reclaim all */
     788        size_t znum = find_free_zone(count, FRAME_TO_ZONE_FLAGS(flags),
     789            frame_constraint, hint);
     790       
     791        /*
     792         * If no memory, reclaim some slab memory,
     793         * if it does not help, reclaim all.
     794         */
    1049795        if ((znum == (size_t) -1) && (!(flags & FRAME_NO_RECLAIM))) {
    1050796                irq_spinlock_unlock(&zones.lock, true);
    … …  
    1053799               
    1054800                if (freed > 0)
    1055                         znum = find_free_zone(order,
    1056                             FRAME_TO_ZONE_FLAGS(flags), hint);
     801                        znum = find_free_zone(count, FRAME_TO_ZONE_FLAGS(flags),
     802                            frame_constraint, hint);
    1057803               
    1058804                if (znum == (size_t) -1) {
    … …  
    1062808                       
    1063809                        if (freed > 0)
    1064                                 znum = find_free_zone(order,
    1065                                     FRAME_TO_ZONE_FLAGS(flags), hint);
     810                                znum = find_free_zone(count, FRAME_TO_ZONE_FLAGS(flags),
     811                                    frame_constraint, hint);
    1066812                }
    1067813        }
    … …  
    1070816                if (flags & FRAME_ATOMIC) {
    1071817                        irq_spinlock_unlock(&zones.lock, true);
     818                       
    1072819                        if (!(flags & FRAME_NO_RESERVE))
    1073                                 reserve_free(size);
     820                                reserve_free(count);
     821                       
    1074822                        return 0;
    1075823                }
    … …  
    1090838#ifdef CONFIG_DEBUG
    1091839                printf("Thread %" PRIu64 " waiting for %zu frames, "
    1092                     "%zu available.\n", THREAD->tid, size, avail);
     840                    "%zu available.\n", THREAD->tid, count, avail);
    1093841#endif
    1094842               
    1095843                /*
    1096                  * Since the mem_avail_mtx is an active mutex, we need to disable interrupts
    1097                  * to prevent deadlock with TLB shootdown.
     844                 * Since the mem_avail_mtx is an active mutex, we need to
     845                 * disable interrupts to prevent deadlock with TLB shootdown.
    1098846                 */
    1099847                ipl_t ipl = interrupts_disable();
    … …  
    1101849               
    1102850                if (mem_avail_req > 0)
    1103                         mem_avail_req = min(mem_avail_req, size);
     851                        mem_avail_req = min(mem_avail_req, count);
    1104852                else
    1105                         mem_avail_req = size;
     853                        mem_avail_req = count;
     854               
    1106855                size_t gen = mem_avail_gen;
    1107856               
    … …  
    1119868        }
    1120869       
    1121         pfn_t pfn = zone_frame_alloc(&zones.info[znum], order)
    1122             + zones.info[znum].base;
     870        pfn_t pfn = zone_frame_alloc(&zones.info[znum], count,
     871            frame_constraint) + zones.info[znum].base;
    1123872       
    1124873        irq_spinlock_unlock(&zones.lock, true);
    … …  
    1130879}
    1131880
    1132 uintptr_t frame_alloc(uint8_t order, frame_flags_t flags, uintptr_t constraint)
    1133 {
    1134         return frame_alloc_generic(order, flags, constraint, NULL);
    1135 }
    1136 
    1137 uintptr_t frame_alloc_noreserve(uint8_t order, frame_flags_t flags,
     881uintptr_t frame_alloc(size_t count, frame_flags_t flags, uintptr_t constraint)
     882{
     883        return frame_alloc_generic(count, flags, constraint, NULL);
     884}
     885
     886uintptr_t frame_alloc_noreserve(size_t count, frame_flags_t flags,
    1138887    uintptr_t constraint)
    1139888{
    1140         return frame_alloc_generic(order, flags | FRAME_NO_RESERVE, constraint,
     889        return frame_alloc_generic(count, flags | FRAME_NO_RESERVE, constraint,
    1141890            NULL);
    1142891}
    … …  
    1154903void frame_free_generic(uintptr_t frame, frame_flags_t flags)
    1155904{
    1156         size_t size;
    1157        
    1158905        irq_spinlock_lock(&zones.lock, true);
    1159906       
    … …  
    1163910        pfn_t pfn = ADDR2PFN(frame);
    1164911        size_t znum = find_zone(pfn, 1, 0);
    1165 
     912       
    1166913        ASSERT(znum != (size_t) -1);
    1167914       
    1168         size = zone_frame_free(&zones.info[znum], pfn - zones.info[znum].base);
     915        size_t size =
     916            zone_frame_free(&zones.info[znum], pfn - zones.info[znum].base);
    1169917       
    1170918        irq_spinlock_unlock(&zones.lock, true);
    … …  
    1173921         * Signal that some memory has been freed.
    1174922         */
    1175 
     923       
    1176924       
    1177925        /*
    … …  
    1179927         * to prevent deadlock with TLB shootdown.
    1180928         */
     929       
    1181930        ipl_t ipl = interrupts_disable();
    1182931        mutex_lock(&mem_avail_mtx);
     932       
    1183933        if (mem_avail_req > 0)
    1184934                mem_avail_req -= min(mem_avail_req, size);
    … …  
    1188938                condvar_broadcast(&mem_avail_cv);
    1189939        }
     940       
    1190941        mutex_unlock(&mem_avail_mtx);
    1191942        interrupts_restore(ipl);
    … …  
    1236987        irq_spinlock_lock(&zones.lock, true);
    1237988       
    1238         size_t i;
    1239         for (i = 0; i < count; i++) {
     989        for (size_t i = 0; i < count; i++) {
    1240990                size_t znum = find_zone(start + i, 1, 0);
     991               
    1241992                if (znum == (size_t) -1)  /* PFN not found */
    1242993                        continue;
    … …  
    12631014        /* Tell the architecture to create some memory */
    12641015        frame_low_arch_init();
     1016       
    12651017        if (config.cpu_active == 1) {
    12661018                frame_mark_unavailable(ADDR2PFN(KA2PA(config.base)),
    … …  
    12691021                    SIZE2FRAMES(config.stack_size));
    12701022               
    1271                 size_t i;
    1272                 for (i = 0; i < init.cnt; i++) {
    1273                         pfn_t pfn = ADDR2PFN(init.tasks[i].paddr);
    1274                         frame_mark_unavailable(pfn,
     1023                for (size_t i = 0; i < init.cnt; i++)
     1024                        frame_mark_unavailable(ADDR2PFN(init.tasks[i].paddr),
    12751025                            SIZE2FRAMES(init.tasks[i].size));
    1276                 }
    12771026               
    12781027                if (ballocs.size)
    … …  
    12801029                            SIZE2FRAMES(ballocs.size));
    12811030               
    1282                 /* Black list first frame, as allocating NULL would
     1031                /*
     1032                 * Blacklist first frame, as allocating NULL would
    12831033                 * fail in some places
    12841034                 */
    12851035                frame_mark_unavailable(0, 1);
    12861036        }
     1037       
    12871038        frame_high_arch_init();
    12881039}
    … …  
    12901041/** Adjust bounds of physical memory region according to low/high memory split.
    12911042 *
    1292  * @param low[in]       If true, the adjustment is performed to make the region
    1293  *                      fit in the low memory. Otherwise the adjustment is
    1294  *                      performed to make the region fit in the high memory.
    1295  * @param basep[inout]  Pointer to a variable which contains the region's base
    1296  *                      address and which may receive the adjusted base address.
    1297  * @param sizep[inout]  Pointer to a variable which contains the region's size
    1298  *                      and which may receive the adjusted size.
    1299  * @retun               True if the region still exists even after the
    1300  *                      adjustment, false otherwise.
     1043 * @param low[in]      If true, the adjustment is performed to make the region
     1044 *                     fit in the low memory. Otherwise the adjustment is
     1045 *                     performed to make the region fit in the high memory.
     1046 * @param basep[inout] Pointer to a variable which contains the region's base
     1047 *                     address and which may receive the adjusted base address.
     1048 * @param sizep[inout] Pointer to a variable which contains the region's size
     1049 *                     and which may receive the adjusted size.
     1050 *
     1051 * @return True if the region still exists even after the adjustment.
     1052 * @return False otherwise.
     1053 *
    13011054 */
    13021055bool frame_adjust_zone_bounds(bool low, uintptr_t *basep, size_t *sizep)
    13031056{
    13041057        uintptr_t limit = KA2PA(config.identity_base) + config.identity_size;
    1305 
     1058       
    13061059        if (low) {
    13071060                if (*basep > limit)
    13081061                        return false;
     1062               
    13091063                if (*basep + *sizep > limit)
    13101064                        *sizep = limit - *basep;
    … …  
    13121066                if (*basep + *sizep <= limit)
    13131067                        return false;
     1068               
    13141069                if (*basep <= limit) {
    13151070                        *sizep -= limit - *basep;
    … …  
    13171072                }
    13181073        }
     1074       
    13191075        return true;
    13201076}
    … …  
    13281084       
    13291085        uint64_t total = 0;
    1330         size_t i;
    1331         for (i = 0; i < zones.count; i++)
     1086       
     1087        for (size_t i = 0; i < zones.count; i++)
    13321088                total += (uint64_t) FRAMES2SIZE(zones.info[i].count);
    13331089       
    … …  
    13521108        *free = 0;
    13531109       
    1354         size_t i;
    1355         for (i = 0; i < zones.count; i++) {
     1110        for (size_t i = 0; i < zones.count; i++) {
    13561111                *total += (uint64_t) FRAMES2SIZE(zones.info[i].count);
    13571112               
    … …  
    13901145         */
    13911146       
    1392         size_t i;
    1393         for (i = 0;; i++) {
     1147        for (size_t i = 0;; i++) {
    13941148                irq_spinlock_lock(&zones.lock, true);
    13951149               
    … …  
    14441198        size_t znum = (size_t) -1;
    14451199       
    1446         size_t i;
    1447         for (i = 0; i < zones.count; i++) {
     1200        for (size_t i = 0; i < zones.count; i++) {
    14481201                if ((i == num) || (PFN2ADDR(zones.info[i].base) == num)) {
    14491202                        znum = i;
    … …  
    14581211        }
    14591212       
    1460         uintptr_t base = PFN2ADDR(zones.info[i].base);
    1461         zone_flags_t flags = zones.info[i].flags;
    1462         size_t count = zones.info[i].count;
    1463         size_t free_count = zones.info[i].free_count;
    1464         size_t busy_count = zones.info[i].busy_count;
     1213        uintptr_t base = PFN2ADDR(zones.info[znum].base);
     1214        zone_flags_t flags = zones.info[znum].flags;
     1215        size_t count = zones.info[znum].count;
     1216        size_t free_count = zones.info[znum].free_count;
     1217        size_t busy_count = zones.info[znum].busy_count;
    14651218       
    14661219        irq_spinlock_unlock(&zones.lock, true);
Note: See TracChangeset for help on using the changeset viewer.