Subversion Repositories HelenOS

Rev

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

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