Subversion Repositories HelenOS

Rev

Rev 676 | Rev 683 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * Copyright (C) 2001-2005 Jakub Jermar
  3.  * Copyright (C) 2005 Sergey Bondari
  4.  * All rights reserved.
  5.  *
  6.  * Redistribution and use in source and binary forms, with or without
  7.  * modification, are permitted provided that the following conditions
  8.  * are met:
  9.  *
  10.  * - Redistributions of source code must retain the above copyright
  11.  *   notice, this list of conditions and the following disclaimer.
  12.  * - Redistributions in binary form must reproduce the above copyright
  13.  *   notice, this list of conditions and the following disclaimer in the
  14.  *   documentation and/or other materials provided with the distribution.
  15.  * - The name of the author may not be used to endorse or promote products
  16.  *   derived from this software without specific prior written permission.
  17.  *
  18.  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  19.  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  20.  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  21.  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  22.  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  23.  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24.  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25.  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26.  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  27.  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28.  */
  29.  
  30. #include <typedefs.h>
  31. #include <arch/types.h>
  32. #include <mm/heap.h>
  33. #include <mm/frame.h>
  34. #include <mm/vm.h>
  35. #include <panic.h>
  36. #include <debug.h>
  37. #include <list.h>
  38. #include <synch/spinlock.h>
  39. #include <arch/asm.h>
  40. #include <arch.h>
  41. #include <print.h>
  42. #include <align.h>
  43.  
  44. SPINLOCK_INITIALIZE(zone_head_lock);    /**< this lock protects zone_head list */
  45. LIST_INITIALIZE(zone_head);             /**< list of all zones in the system */
  46.  
  47. /** Blacklist containing non-available areas of memory.
  48.  *
  49.  * This blacklist is used to exclude frames that cannot be allocated
  50.  * (e.g. kernel memory) from available memory map.
  51.  */
  52. region_t zone_blacklist[ZONE_BLACKLIST_SIZE];
  53. count_t zone_blacklist_count = 0;
  54.  
  55. static struct buddy_system_operations  zone_buddy_system_operations = {
  56.     .find_buddy = zone_buddy_find_buddy,
  57.     .bisect = zone_buddy_bisect,
  58.     .coalesce = zone_buddy_coalesce,
  59.     .set_order = zone_buddy_set_order,
  60.     .get_order = zone_buddy_get_order,
  61.     .mark_busy = zone_buddy_mark_busy,
  62. };
  63.  
  64. /** Initialize physical memory management
  65.  *
  66.  * Initialize physical memory managemnt.
  67.  */
  68. void frame_init(void)
  69. {
  70.     if (config.cpu_active == 1) {
  71.         frame_region_not_free(KA2PA(config.base), config.kernel_size);
  72.         if (config.init_size > 0)
  73.             frame_region_not_free(KA2PA(config.init_addr), config.init_size);
  74.     }
  75.  
  76.     frame_arch_init();
  77. }
  78.  
  79. /** Allocate power-of-two frames of physical memory.
  80.  *
  81.  * @param flags Flags for host zone selection and address processing.
  82.  * @param order Allocate exactly 2^order frames.
  83.  *
  84.  * @return Allocated frame.
  85.  */
  86. __address frame_alloc(int flags, __u8 order)
  87. {
  88.     ipl_t ipl;
  89.     link_t *cur, *tmp;
  90.     zone_t *z;
  91.     zone_t *zone = NULL;
  92.     frame_t *frame = NULL;
  93.     __address v;
  94.    
  95. loop:
  96.     ipl = interrupts_disable();
  97.     spinlock_lock(&zone_head_lock);
  98.  
  99.     /*
  100.      * First, find suitable frame zone.
  101.      */
  102.     for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
  103.         z = list_get_instance(cur, zone_t, link);
  104.        
  105.         spinlock_lock(&z->lock);
  106.  
  107.         /* Check if the zone has 2^order frames area available  */
  108.         if (buddy_system_can_alloc(z->buddy_system, order)) {
  109.             zone = z;
  110.             break;
  111.         }
  112.        
  113.         spinlock_unlock(&z->lock);
  114.     }
  115.    
  116.     if (!zone) {
  117.         if (flags & FRAME_PANIC)
  118.             panic("Can't allocate frame.\n");
  119.        
  120.         /*
  121.          * TODO: Sleep until frames are available again.
  122.          */
  123.         spinlock_unlock(&zone_head_lock);
  124.         interrupts_restore(ipl);
  125.  
  126.         panic("Sleep not implemented.\n");
  127.         goto loop;
  128.     }
  129.        
  130.  
  131.     /* Allocate frames from zone buddy system */
  132.     tmp = buddy_system_alloc(zone->buddy_system, order);
  133.    
  134.     ASSERT(tmp);
  135.    
  136.     /* Update zone information. */
  137.     zone->free_count -= (1 << order);
  138.     zone->busy_count += (1 << order);
  139.  
  140.     /* Frame will be actually a first frame of the block. */
  141.     frame = list_get_instance(tmp, frame_t, buddy_link);
  142.    
  143.     /* get frame address */
  144.     v = FRAME2ADDR(zone, frame);
  145.  
  146.     spinlock_unlock(&zone->lock);
  147.     spinlock_unlock(&zone_head_lock);
  148.     interrupts_restore(ipl);
  149.  
  150.  
  151.     if (flags & FRAME_KA)
  152.         v = PA2KA(v);
  153.    
  154.     return v;
  155. }
  156.  
  157. /** Free a frame.
  158.  *
  159.  * Find respective frame structrue for supplied addr.
  160.  * Decrement frame reference count.
  161.  * If it drops to zero, move the frame structure to free list.
  162.  *
  163.  * @param addr Address of the frame to be freed. It must be a multiple of FRAME_SIZE.
  164.  */
  165. void frame_free(__address addr)
  166. {
  167.     ipl_t ipl;
  168.     link_t *cur;
  169.     zone_t *z;
  170.     zone_t *zone = NULL;
  171.     frame_t *frame;
  172.     ASSERT(addr % FRAME_SIZE == 0);
  173.    
  174.     ipl = interrupts_disable();
  175.     spinlock_lock(&zone_head_lock);
  176.    
  177.     /*
  178.      * First, find host frame zone for addr.
  179.      */
  180.     for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
  181.         z = list_get_instance(cur, zone_t, link);
  182.        
  183.         spinlock_lock(&z->lock);
  184.        
  185.         if (IS_KA(addr))
  186.             addr = KA2PA(addr);
  187.        
  188.         /*
  189.          * Check if addr belongs to z.
  190.          */
  191.         if ((addr >= z->base) && (addr <= z->base + (z->free_count + z->busy_count) * FRAME_SIZE)) {
  192.             zone = z;
  193.             break;
  194.         }
  195.         spinlock_unlock(&z->lock);
  196.     }
  197.    
  198.     ASSERT(zone != NULL);
  199.    
  200.     frame = ADDR2FRAME(zone, addr);
  201.  
  202.     ASSERT(frame->refcount);
  203.  
  204.     if (!--frame->refcount) {
  205.         buddy_system_free(zone->buddy_system, &frame->buddy_link);
  206.     }
  207.  
  208.     /* Update zone information. */
  209.     zone->free_count += (1 << frame->buddy_order);
  210.     zone->busy_count -= (1 << frame->buddy_order);
  211.    
  212.     spinlock_unlock(&zone->lock);
  213.     spinlock_unlock(&zone_head_lock);
  214.     interrupts_restore(ipl);
  215. }
  216.  
  217. /** Mark frame region not free.
  218.  *
  219.  * Mark frame region not free.
  220.  *
  221.  * @param base Base address of non-available region.
  222.  * @param size Size of non-available region.
  223.  */
  224. void frame_region_not_free(__address base, size_t size)
  225. {
  226.     index_t index;
  227.     index = zone_blacklist_count++;
  228.  
  229.     /* Force base to the nearest lower address frame boundary. */
  230.     base = ALIGN_DOWN(base, FRAME_SIZE);
  231.     /* Align size to frame boundary. */
  232.     size = ALIGN_UP(size, FRAME_SIZE);
  233.  
  234.     ASSERT(index < ZONE_BLACKLIST_SIZE);
  235.     zone_blacklist[index].base = base;
  236.     zone_blacklist[index].size = size;
  237. }
  238.  
  239. /** Create frame zones in region of available memory.
  240.  *
  241.  * Avoid any black listed areas of non-available memory.
  242.  * Assume that the black listed areas cannot overlap
  243.  * one another or cross available memory region boundaries.
  244.  *
  245.  * @param base Base address of available memory region.
  246.  * @param size Size of the region.
  247.  */
  248. void zone_create_in_region(__address base, size_t size) {
  249.     int i;
  250.     zone_t * z;
  251.     __address s;
  252.     size_t sz;
  253.    
  254.     ASSERT(base % FRAME_SIZE == 0);
  255.     ASSERT(size % FRAME_SIZE == 0);
  256.    
  257.     if (!size)
  258.         return;
  259.  
  260.     for (i = 0; i < zone_blacklist_count; i++) {
  261.         if (zone_blacklist[i].base >= base && zone_blacklist[i].base < base + size) {
  262.             s = base; sz = zone_blacklist[i].base - base;
  263.             ASSERT(base != s || sz != size);
  264.             zone_create_in_region(s, sz);
  265.            
  266.             s = zone_blacklist[i].base + zone_blacklist[i].size;
  267.             sz = (base + size) - (zone_blacklist[i].base + zone_blacklist[i].size);
  268.             ASSERT(base != s || sz != size);
  269.             zone_create_in_region(s, sz);
  270.             return;
  271.        
  272.         }
  273.     }
  274.    
  275.     z = zone_create(base, size, 0);
  276.  
  277.     if (!z) {
  278.         panic("Cannot allocate zone (base=%P, size=%d).\n", base, size);
  279.     }
  280.    
  281.     zone_attach(z);
  282. }
  283.  
  284.  
  285. /** Create frame zone
  286.  *
  287.  * Create new frame zone.
  288.  *
  289.  * @param start Physical address of the first frame within the zone.
  290.  * @param size Size of the zone. Must be a multiple of FRAME_SIZE.
  291.  * @param flags Zone flags.
  292.  *
  293.  * @return Initialized zone.
  294.  */
  295. zone_t * zone_create(__address start, size_t size, int flags)
  296. {
  297.     zone_t *z;
  298.     count_t cnt;
  299.     int i;
  300.     __u8 max_order;
  301.  
  302.     ASSERT(start % FRAME_SIZE == 0);
  303.     ASSERT(size % FRAME_SIZE == 0);
  304.    
  305.     cnt = size / FRAME_SIZE;
  306.    
  307.     z = (zone_t *) early_malloc(sizeof(zone_t));
  308.     if (z) {
  309.         link_initialize(&z->link);
  310.         spinlock_initialize(&z->lock, "zone_lock");
  311.    
  312.         z->base = start;
  313.         z->flags = flags;
  314.  
  315.         z->free_count = cnt;
  316.         z->busy_count = 0;
  317.        
  318.         z->frames = (frame_t *) early_malloc(cnt * sizeof(frame_t));
  319.         if (!z->frames) {
  320.             early_free(z);
  321.             return NULL;
  322.         }
  323.        
  324.         for (i = 0; i<cnt; i++) {
  325.             frame_initialize(&z->frames[i], z);
  326.         }
  327.        
  328.         /*
  329.          * Create buddy system for the zone
  330.          */
  331.         for (max_order = 0; cnt >> max_order; max_order++)
  332.             ;
  333.         z->buddy_system = buddy_system_create(max_order, &zone_buddy_system_operations, (void *) z);
  334.        
  335.         /* Stuffing frames */
  336.         for (i = 0; i<cnt; i++) {
  337.             z->frames[i].refcount = 0;
  338.             buddy_system_free(z->buddy_system, &z->frames[i].buddy_link);  
  339.         }
  340.     }
  341.     return z;
  342. }
  343.  
  344. /** Attach frame zone
  345.  *
  346.  * Attach frame zone to zone list.
  347.  *
  348.  * @param zone Zone to be attached.
  349.  */
  350. void zone_attach(zone_t *zone)
  351. {
  352.     ipl_t ipl;
  353.    
  354.     ipl = interrupts_disable();
  355.     spinlock_lock(&zone_head_lock);
  356.    
  357.     list_append(&zone->link, &zone_head);
  358.    
  359.     spinlock_unlock(&zone_head_lock);
  360.     interrupts_restore(ipl);
  361. }
  362.  
  363. /** Initialize frame structure
  364.  *
  365.  * Initialize frame structure.
  366.  *
  367.  * @param frame Frame structure to be initialized.
  368.  * @param zone Host frame zone.
  369.  */
  370. void frame_initialize(frame_t *frame, zone_t *zone)
  371. {
  372.     frame->refcount = 1;
  373.     frame->buddy_order = 0;
  374. }
  375.  
  376.  
  377. /** Buddy system find_buddy implementation
  378.  *
  379.  * @param b Buddy system.
  380.  * @param block Block for which buddy should be found
  381.  *
  382.  * @return Buddy for given block if found
  383.  */
  384. link_t * zone_buddy_find_buddy(buddy_system_t *b, link_t * block) {
  385.     frame_t * frame;
  386.     zone_t * zone;
  387.     index_t index;
  388.     bool is_left, is_right;
  389.  
  390.     frame = list_get_instance(block, frame_t, buddy_link);
  391.     zone = (zone_t *) b->data;
  392.    
  393.     ASSERT(IS_BUDDY_ORDER_OK(FRAME_INDEX(zone, frame), frame->buddy_order));
  394.    
  395.     is_left = IS_BUDDY_LEFT_BLOCK(zone, frame);
  396.     is_right = IS_BUDDY_RIGHT_BLOCK(zone, frame);
  397.    
  398.     ASSERT(is_left ^ is_right);
  399.    
  400.     if (is_left) {
  401.         index = (FRAME_INDEX(zone, frame)) + (1 << frame->buddy_order);
  402.     } else { // if (is_right)
  403.         index = (FRAME_INDEX(zone, frame)) - (1 << frame->buddy_order);
  404.     }
  405.    
  406.     if (FRAME_INDEX_VALID(zone, index)) {
  407.         if (    zone->frames[index].buddy_order == frame->buddy_order &&
  408.             zone->frames[index].refcount == 0) {
  409.             return &zone->frames[index].buddy_link;
  410.         }
  411.     }
  412.    
  413.     return NULL;   
  414. }
  415.  
  416. /** Buddy system bisect implementation
  417.  *
  418.  * @param b Buddy system.
  419.  * @param block Block to bisect
  420.  *
  421.  * @return right block
  422.  */
  423. link_t * zone_buddy_bisect(buddy_system_t *b, link_t * block) {
  424.     frame_t * frame_l, * frame_r;
  425.  
  426.     frame_l = list_get_instance(block, frame_t, buddy_link);
  427.     frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));
  428.    
  429.     return &frame_r->buddy_link;
  430. }
  431.  
  432. /** Buddy system coalesce implementation
  433.  *
  434.  * @param b Buddy system.
  435.  * @param block_1 First block
  436.  * @param block_2 First block's buddy
  437.  *
  438.  * @return Coalesced block (actually block that represents lower address)
  439.  */
  440. link_t * zone_buddy_coalesce(buddy_system_t *b, link_t * block_1, link_t * block_2) {
  441.     frame_t * frame1, * frame2;
  442.    
  443.     frame1 = list_get_instance(block_1, frame_t, buddy_link);
  444.     frame2 = list_get_instance(block_2, frame_t, buddy_link);
  445.    
  446.     return frame1 < frame2 ? block_1 : block_2;
  447. }
  448.  
  449. /** Buddy system set_order implementation
  450.  *
  451.  * @param b Buddy system.
  452.  * @param block Buddy system block
  453.  * @param order Order to set
  454.  */
  455. void zone_buddy_set_order(buddy_system_t *b, link_t * block, __u8 order) {
  456.     frame_t * frame;
  457.     frame = list_get_instance(block, frame_t, buddy_link);
  458.     frame->buddy_order = order;
  459. }
  460.  
  461. /** Buddy system get_order implementation
  462.  *
  463.  * @param b Buddy system.
  464.  * @param block Buddy system block
  465.  *
  466.  * @return Order of block
  467.  */
  468. __u8 zone_buddy_get_order(buddy_system_t *b, link_t * block) {
  469.     frame_t * frame;
  470.     frame = list_get_instance(block, frame_t, buddy_link);
  471.     return frame->buddy_order;
  472. }
  473.  
  474. /** Buddy system mark_busy implementation
  475.  *
  476.  * @param b Buddy system
  477.  * @param block Buddy system block
  478.  *
  479.  */
  480. void zone_buddy_mark_busy(buddy_system_t *b, link_t * block) {
  481.     frame_t * frame;
  482.     frame = list_get_instance(block, frame_t, buddy_link);
  483.     frame->refcount = 1;
  484. }
  485.  
  486. /** Prints list of zones
  487.  *
  488.  */
  489. void zone_print_list(void) {
  490.     zone_t *zone = NULL;
  491.     link_t *cur;
  492.     index_t i = 0;
  493.     printf("No.\tBase address\tFree Frames\tBusy Frames\n");
  494.     printf("---\t------------\t-----------\t-----------\n");
  495.     for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
  496.         zone = list_get_instance(cur, zone_t, link);
  497.         printf("%d\t%L\t%d\t\t%d\n",i++,zone->base, zone->free_count, zone->busy_count);
  498.     }
  499.  
  500. }
  501.  
  502. /** Prints zone details
  503.  *
  504.  * @param zone_index Zone order in zones list (0 is the first zone)
  505.  */
  506. void zone_print_one(index_t zone_index) {
  507.     zone_t *zone = NULL;
  508.     link_t *cur;
  509.     index_t i = 0;
  510.    
  511.     for (cur = zone_head.next; cur != &zone_head; cur = cur->next) {
  512.         if (i == zone_index) {
  513.             zone = list_get_instance(cur, zone_t, link);
  514.             break;
  515.         }
  516.         i++;
  517.     }
  518.    
  519.     if (!zone) {
  520.         printf("No zone with index %d\n", zone_index);
  521.         return;
  522.     }
  523.    
  524.     printf("Memory zone %d information\n\n", zone_index);
  525.     printf("Zone base address: %P\n", zone->base);
  526.     printf("Zone size: %d frames (%d kbytes)\n", zone->free_count + zone->busy_count, ((zone->free_count + zone->busy_count) * FRAME_SIZE) >> 10);
  527.     printf("Allocated space: %d frames (%d kbytes)\n", zone->busy_count, (zone->busy_count * FRAME_SIZE) >> 10);
  528.     printf("Available space: %d (%d kbytes)\n", zone->free_count, (zone->free_count * FRAME_SIZE) >> 10);
  529.     printf("Buddy allocator structures: not implemented\n");
  530. }
  531.  
  532.