Subversion Repositories HelenOS

Rev

Rev 2128 | 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. /** @addtogroup genericmm
  31.  * @{
  32.  */
  33.  
  34. /**
  35.  * @file
  36.  * @brief   Physical frame allocator.
  37.  *
  38.  * This file contains the physical frame allocator and memory zone management.
  39.  * The frame allocator is built on top of the buddy allocator.
  40.  *
  41.  * @see buddy.c
  42.  */
  43.  
  44. /*
  45.  * Locking order
  46.  *
  47.  * In order to access particular zone, the process must first lock
  48.  * the zones.lock, then lock the zone and then unlock the zones.lock.
  49.  * This insures, that we can fiddle with the zones in runtime without
  50.  * affecting the processes.
  51.  *
  52.  */
  53.  
  54. #include <arch/types.h>
  55. #include <mm/frame.h>
  56. #include <mm/as.h>
  57. #include <panic.h>
  58. #include <debug.h>
  59. #include <adt/list.h>
  60. #include <synch/spinlock.h>
  61. #include <arch/asm.h>
  62. #include <arch.h>
  63. #include <print.h>
  64. #include <align.h>
  65. #include <mm/slab.h>
  66. #include <bitops.h>
  67. #include <macros.h>
  68. #include <config.h>
  69.  
  70. typedef struct {
  71.     count_t refcount;   /**< tracking of shared frames  */
  72.     uint8_t buddy_order;    /**< buddy system block order */
  73.     link_t buddy_link;  /**< link to the next free block inside one order */
  74.     void *parent;           /**< If allocated by slab, this points there */
  75. } frame_t;
  76.  
  77. typedef struct {
  78.     SPINLOCK_DECLARE(lock); /**< this lock protects everything below */
  79.     pfn_t base;     /**< frame_no of the first frame in the frames array */
  80.     count_t count;          /**< Size of zone */
  81.  
  82.     frame_t *frames;    /**< array of frame_t structures in this zone */
  83.     count_t free_count; /**< number of free frame_t structures */
  84.     count_t busy_count; /**< number of busy frame_t structures */
  85.    
  86.     buddy_system_t *buddy_system; /**< buddy system for the zone */
  87.     int flags;
  88. } zone_t;
  89.  
  90. /*
  91.  * The zoneinfo.lock must be locked when accessing zoneinfo structure.
  92.  * Some of the attributes in zone_t structures are 'read-only'
  93.  */
  94.  
  95. typedef struct {
  96.     SPINLOCK_DECLARE(lock);
  97.     unsigned int count;
  98.     zone_t *info[ZONES_MAX];
  99. } zones_t;
  100.  
  101. static zones_t zones;
  102.  
  103.  
  104. /*********************************/
  105. /* Helper functions */
  106. static inline index_t frame_index(zone_t *zone, frame_t *frame)
  107. {
  108.     return (index_t)(frame - zone->frames);
  109. }
  110. static inline index_t frame_index_abs(zone_t *zone, frame_t *frame)
  111. {
  112.     return (index_t)(frame - zone->frames) + zone->base;
  113. }
  114. static inline int frame_index_valid(zone_t *zone, index_t index)
  115. {
  116.     return index >= 0 && index < zone->count;
  117. }
  118.  
  119. /** Compute pfn_t from frame_t pointer & zone pointer */
  120. static index_t make_frame_index(zone_t *zone, frame_t *frame)
  121. {
  122.     return frame - zone->frames;
  123. }
  124.  
  125. /** Initialize frame structure
  126.  *
  127.  * Initialize frame structure.
  128.  *
  129.  * @param frame Frame structure to be initialized.
  130.  */
  131. static void frame_initialize(frame_t *frame)
  132. {
  133.     frame->refcount = 1;
  134.     frame->buddy_order = 0;
  135. }
  136.  
  137. /*************************************/
  138. /* Zoneinfo functions */
  139.  
  140. /**
  141.  * Insert-sort zone into zones list
  142.  *
  143.  * @param newzone New zone to be inserted into zone list
  144.  * @return zone number on success, -1 on error
  145.  */
  146. static int zones_add_zone(zone_t *newzone)
  147. {
  148.     unsigned int i, j;
  149.     ipl_t ipl;
  150.     zone_t *z;
  151.  
  152.     ipl = interrupts_disable();
  153.     spinlock_lock(&zones.lock);
  154.     /* Try to merge */
  155.     if (zones.count + 1 == ZONES_MAX)
  156.         panic("Maximum zone(%d) count exceeded.", ZONES_MAX);
  157.     for (i = 0; i < zones.count; i++) {
  158.         /* Check for overflow */
  159.         z = zones.info[i];
  160.         if (overlaps(newzone->base,newzone->count,
  161.                  z->base, z->count)) {
  162.             printf("Zones overlap!\n");
  163.             return -1;
  164.         }
  165.         if (newzone->base < z->base)
  166.             break;
  167.     }
  168.     /* Move other zones up */
  169.     for (j = i;j < zones.count; j++)
  170.         zones.info[j + 1] = zones.info[j];
  171.     zones.info[i] = newzone;
  172.     zones.count++;
  173.     spinlock_unlock(&zones.lock);
  174.     interrupts_restore(ipl);
  175.  
  176.     return i;
  177. }
  178.  
  179. /**
  180.  * Try to find a zone where can we find the frame
  181.  
  182.  * Assume interrupts are disabled.
  183.  
  184.  * @param frame Frame number contained in zone
  185.  * @param pzone If not null, it is used as zone hint. Zone index
  186.  *              is filled into the variable on success.
  187.  * @return Pointer to locked zone containing frame
  188.  */
  189. static zone_t * find_zone_and_lock(pfn_t frame, unsigned int *pzone)
  190. {
  191.     unsigned int i;
  192.     unsigned int hint = pzone ? *pzone : 0;
  193.     zone_t *z;
  194.    
  195.     spinlock_lock(&zones.lock);
  196.  
  197.     if (hint >= zones.count || hint < 0)
  198.         hint = 0;
  199.    
  200.     i = hint;
  201.     do {
  202.         z = zones.info[i];
  203.         spinlock_lock(&z->lock);
  204.         if (z->base <= frame && z->base + z->count > frame) {
  205.             spinlock_unlock(&zones.lock); /* Unlock the global lock */
  206.             if (pzone)
  207.                 *pzone = i;
  208.             return z;
  209.         }
  210.         spinlock_unlock(&z->lock);
  211.  
  212.         i++;
  213.         if (i >= zones.count)
  214.             i = 0;
  215.     } while(i != hint);
  216.  
  217.     spinlock_unlock(&zones.lock);
  218.     return NULL;
  219. }
  220.  
  221. /** @return True if zone can allocate specified order */
  222. static int zone_can_alloc(zone_t *z, uint8_t order)
  223. {
  224.     return buddy_system_can_alloc(z->buddy_system, order);
  225. }
  226.  
  227. /** Find and lock zone that can allocate order frames.
  228.  *
  229.  * Assume interrupts are disabled.
  230.  *
  231.  * @param order Size (2^order) of free space we are trying to find
  232.  * @param pzone Pointer to preferred zone or NULL, on return contains zone number
  233.  */
  234. static zone_t * find_free_zone_and_lock(uint8_t order, unsigned int *pzone)
  235. {
  236.     unsigned int i;
  237.     zone_t *z;
  238.     unsigned int hint = pzone ? *pzone : 0;
  239.    
  240.     spinlock_lock(&zones.lock);
  241.     if (hint >= zones.count)
  242.         hint = 0;
  243.     i = hint;
  244.     do {
  245.         z = zones.info[i];
  246.        
  247.         spinlock_lock(&z->lock);
  248.  
  249.         /* Check if the zone has 2^order frames area available  */
  250.         if (zone_can_alloc(z, order)) {
  251.             spinlock_unlock(&zones.lock);
  252.             if (pzone)
  253.                 *pzone = i;
  254.             return z;
  255.         }
  256.         spinlock_unlock(&z->lock);
  257.         if (++i >= zones.count)
  258.             i = 0;
  259.     } while(i != hint);
  260.     spinlock_unlock(&zones.lock);
  261.     return NULL;
  262. }
  263.  
  264. /**************************/
  265. /* Buddy system functions */
  266. /**************************/
  267.  
  268. /** Buddy system find_block implementation
  269.  *
  270.  * Find block that is parent of current list.
  271.  * That means go to lower addresses, until such block is found
  272.  *
  273.  * @param order - Order of parent must be different then this parameter!!
  274.  */
  275. static link_t *zone_buddy_find_block(buddy_system_t *b, link_t *child,
  276.                      uint8_t order)
  277. {
  278.     frame_t * frame;
  279.     zone_t * zone;
  280.     index_t index;
  281.    
  282.     frame = list_get_instance(child, frame_t, buddy_link);
  283.     zone = (zone_t *) b->data;
  284.  
  285.     index = frame_index(zone, frame);
  286.     do {
  287.         if (zone->frames[index].buddy_order != order) {
  288.             return &zone->frames[index].buddy_link;
  289.         }
  290.     } while(index-- > 0);
  291.     return NULL;
  292. }
  293.  
  294. static void zone_buddy_print_id(buddy_system_t *b, link_t *block)
  295. {
  296.     frame_t * frame;
  297.     zone_t * zone;
  298.     index_t index;
  299.  
  300.     frame = list_get_instance(block, frame_t, buddy_link);
  301.     zone = (zone_t *) b->data;
  302.     index = frame_index(zone, frame);
  303.     printf("%zd", index);
  304. }                    
  305.  
  306. /** Buddy system find_buddy implementation
  307.  *
  308.  * @param b Buddy system.
  309.  * @param block Block for which buddy should be found
  310.  *
  311.  * @return Buddy for given block if found
  312.  */
  313. static link_t * zone_buddy_find_buddy(buddy_system_t *b, link_t * block)
  314. {
  315.     frame_t * frame;
  316.     zone_t * zone;
  317.     index_t index;
  318.     bool is_left, is_right;
  319.  
  320.     frame = list_get_instance(block, frame_t, buddy_link);
  321.     zone = (zone_t *) b->data;
  322.     ASSERT(IS_BUDDY_ORDER_OK(frame_index_abs(zone, frame), frame->buddy_order));
  323.    
  324.     is_left = IS_BUDDY_LEFT_BLOCK_ABS(zone, frame);
  325.     is_right = IS_BUDDY_RIGHT_BLOCK_ABS(zone, frame);
  326.  
  327.     ASSERT(is_left ^ is_right);
  328.     if (is_left) {
  329.         index = (frame_index(zone, frame)) + (1 << frame->buddy_order);
  330.     } else {    /* if (is_right) */
  331.         index = (frame_index(zone, frame)) - (1 << frame->buddy_order);
  332.     }
  333.    
  334.     if (frame_index_valid(zone, index)) {
  335.         if (zone->frames[index].buddy_order == frame->buddy_order &&
  336.             zone->frames[index].refcount == 0) {
  337.             return &zone->frames[index].buddy_link;
  338.         }
  339.     }
  340.  
  341.     return NULL;   
  342. }
  343.  
  344. /** Buddy system bisect implementation
  345.  *
  346.  * @param b Buddy system.
  347.  * @param block Block to bisect
  348.  *
  349.  * @return right block
  350.  */
  351. static link_t * zone_buddy_bisect(buddy_system_t *b, link_t * block) {
  352.     frame_t * frame_l, * frame_r;
  353.  
  354.     frame_l = list_get_instance(block, frame_t, buddy_link);
  355.     frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));
  356.    
  357.     return &frame_r->buddy_link;
  358. }
  359.  
  360. /** Buddy system coalesce implementation
  361.  *
  362.  * @param b Buddy system.
  363.  * @param block_1 First block
  364.  * @param block_2 First block's buddy
  365.  *
  366.  * @return Coalesced block (actually block that represents lower address)
  367.  */
  368. static link_t * zone_buddy_coalesce(buddy_system_t *b, link_t * block_1,
  369.                     link_t * block_2)
  370. {
  371.     frame_t *frame1, *frame2;
  372.    
  373.     frame1 = list_get_instance(block_1, frame_t, buddy_link);
  374.     frame2 = list_get_instance(block_2, frame_t, buddy_link);
  375.    
  376.     return frame1 < frame2 ? block_1 : block_2;
  377. }
  378.  
  379. /** Buddy system set_order implementation
  380.  *
  381.  * @param b Buddy system.
  382.  * @param block Buddy system block
  383.  * @param order Order to set
  384.  */
  385. static void zone_buddy_set_order(buddy_system_t *b, link_t * block, uint8_t order) {
  386.     frame_t * frame;
  387.     frame = list_get_instance(block, frame_t, buddy_link);
  388.     frame->buddy_order = order;
  389. }
  390.  
  391. /** Buddy system get_order implementation
  392.  *
  393.  * @param b Buddy system.
  394.  * @param block Buddy system block
  395.  *
  396.  * @return Order of block
  397.  */
  398. static uint8_t zone_buddy_get_order(buddy_system_t *b, link_t * block) {
  399.     frame_t * frame;
  400.     frame = list_get_instance(block, frame_t, buddy_link);
  401.     return frame->buddy_order;
  402. }
  403.  
  404. /** Buddy system mark_busy implementation
  405.  *
  406.  * @param b Buddy system
  407.  * @param block Buddy system block
  408.  *
  409.  */
  410. static void zone_buddy_mark_busy(buddy_system_t *b, link_t * block) {
  411.     frame_t * frame;
  412.  
  413.     frame = list_get_instance(block, frame_t, buddy_link);
  414.     frame->refcount = 1;
  415. }
  416.  
  417. /** Buddy system mark_available implementation
  418.  *
  419.  * @param b Buddy system
  420.  * @param block Buddy system block
  421.  *
  422.  */
  423. static void zone_buddy_mark_available(buddy_system_t *b, link_t * block) {
  424.     frame_t * frame;
  425.     frame = list_get_instance(block, frame_t, buddy_link);
  426.     frame->refcount = 0;
  427. }
  428.  
  429. static buddy_system_operations_t zone_buddy_system_operations = {
  430.     .find_buddy = zone_buddy_find_buddy,
  431.     .bisect = zone_buddy_bisect,
  432.     .coalesce = zone_buddy_coalesce,
  433.     .set_order = zone_buddy_set_order,
  434.     .get_order = zone_buddy_get_order,
  435.     .mark_busy = zone_buddy_mark_busy,
  436.     .mark_available = zone_buddy_mark_available,
  437.     .find_block = zone_buddy_find_block,
  438.     .print_id = zone_buddy_print_id
  439. };
  440.  
  441. /******************/
  442. /* Zone functions */
  443. /******************/
  444.  
  445. /** Allocate frame in particular zone
  446.  *
  447.  * Assume zone is locked
  448.  * Panics if allocation is impossible.
  449.  *
  450.  * @param zone  Zone to allocate from.
  451.  * @param order Allocate exactly 2^order frames.
  452.  *
  453.  * @return Frame index in zone
  454.  *
  455.  */
  456. static pfn_t zone_frame_alloc(zone_t *zone, uint8_t order)
  457. {
  458.     pfn_t v;
  459.     link_t *tmp;
  460.     frame_t *frame;
  461.  
  462.     /* Allocate frames from zone buddy system */
  463.     tmp = buddy_system_alloc(zone->buddy_system, order);
  464.    
  465.     ASSERT(tmp);
  466.    
  467.     /* Update zone information. */
  468.     zone->free_count -= (1 << order);
  469.     zone->busy_count += (1 << order);
  470.  
  471.     /* Frame will be actually a first frame of the block. */
  472.     frame = list_get_instance(tmp, frame_t, buddy_link);
  473.    
  474.     /* get frame address */
  475.     v = make_frame_index(zone, frame);
  476.     return v;
  477. }
  478.  
  479. /** Free frame from zone
  480.  *
  481.  * Assume zone is locked
  482.  *
  483.  * @param zone Pointer to zone from which the frame is to be freed
  484.  * @param frame_idx Frame index relative to zone
  485.  */
  486. static void zone_frame_free(zone_t *zone, index_t frame_idx)
  487. {
  488.     frame_t *frame;
  489.     uint8_t order;
  490.  
  491.     frame = &zone->frames[frame_idx];
  492.    
  493.     /* remember frame order */
  494.     order = frame->buddy_order;
  495.  
  496.     ASSERT(frame->refcount);
  497.  
  498.     if (!--frame->refcount) {
  499.         buddy_system_free(zone->buddy_system, &frame->buddy_link);
  500.    
  501.         /* Update zone information. */
  502.         zone->free_count += (1 << order);
  503.         zone->busy_count -= (1 << order);
  504.     }
  505. }
  506.  
  507. /** Return frame from zone */
  508. static frame_t * zone_get_frame(zone_t *zone, index_t frame_idx)
  509. {
  510.     ASSERT(frame_idx < zone->count);
  511.     return &zone->frames[frame_idx];
  512. }
  513.  
  514. /** Mark frame in zone unavailable to allocation */
  515. static void zone_mark_unavailable(zone_t *zone, index_t frame_idx)
  516. {
  517.     frame_t *frame;
  518.     link_t *link;
  519.  
  520.     frame = zone_get_frame(zone, frame_idx);
  521.     if (frame->refcount)
  522.         return;
  523.     link = buddy_system_alloc_block(zone->buddy_system,
  524.                     &frame->buddy_link);
  525.     ASSERT(link);
  526.     zone->free_count--;
  527. }
  528.  
  529. /**
  530.  * Join 2 zones
  531.  *
  532.  * Expect zone_t *z to point to space at least zone_conf_size large
  533.  *
  534.  * Assume z1 & z2 are locked
  535.  *
  536.  * @param z Target zone structure pointer
  537.  * @param z1 Zone to merge
  538.  * @param z2 Zone to merge
  539.  */
  540. static void _zone_merge(zone_t *z, zone_t *z1, zone_t *z2)
  541. {
  542.     uint8_t max_order;
  543.     unsigned int i;
  544.     int z2idx;
  545.     pfn_t frame_idx;
  546.     frame_t *frame;
  547.  
  548.     ASSERT(!overlaps(z1->base,z1->count,z2->base,z2->count));
  549.     ASSERT(z1->base < z2->base);
  550.  
  551.     spinlock_initialize(&z->lock, "zone_lock");
  552.     z->base = z1->base;
  553.     z->count = z2->base+z2->count - z1->base;
  554.     z->flags = z1->flags & z2->flags;
  555.  
  556.     z->free_count = z1->free_count + z2->free_count;
  557.     z->busy_count = z1->busy_count + z2->busy_count;
  558.    
  559.     max_order = fnzb(z->count);
  560.  
  561.     z->buddy_system = (buddy_system_t *)&z[1];
  562.     buddy_system_create(z->buddy_system, max_order,
  563.                 &zone_buddy_system_operations,
  564.                 (void *) z);
  565.  
  566.     z->frames = (frame_t *)((uint8_t *) z->buddy_system + buddy_conf_size(max_order));
  567.     for (i = 0; i < z->count; i++) {
  568.         /* This marks all frames busy */
  569.         frame_initialize(&z->frames[i]);
  570.     }
  571.     /* Copy frames from both zones to preserve full frame orders,
  572.      * parents etc. Set all free frames with refcount=0 to 1, because
  573.      * we add all free frames to buddy allocator later again, clear
  574.      * order to 0. Don't set busy frames with refcount=0, as they
  575.      * will not be reallocated during merge and it would make later
  576.      * problems with allocation/free.
  577.      */
  578.     for (i = 0; i < z1->count; i++)
  579.         z->frames[i] = z1->frames[i];
  580.     for (i = 0; i < z2->count; i++) {
  581.         z2idx = i + (z2->base - z1->base);
  582.         z->frames[z2idx] = z2->frames[i];
  583.     }
  584.     i = 0;
  585.     while (i < z->count) {
  586.         if (z->frames[i].refcount) {
  587.             /* skip busy frames */
  588.             i += 1 << z->frames[i].buddy_order;
  589.         } else { /* Free frames, set refcount=1 */
  590.             /* All free frames have refcount=0, we need not
  591.              * to check the order */
  592.             z->frames[i].refcount = 1;
  593.             z->frames[i].buddy_order = 0;
  594.             i++;
  595.         }
  596.     }
  597.     /* Add free blocks from the 2 original zones */
  598.     while (zone_can_alloc(z1, 0)) {
  599.         frame_idx = zone_frame_alloc(z1, 0);
  600.         frame = &z->frames[frame_idx];
  601.         frame->refcount = 0;
  602.         buddy_system_free(z->buddy_system, &frame->buddy_link);
  603.     }
  604.     while (zone_can_alloc(z2, 0)) {
  605.         frame_idx = zone_frame_alloc(z2, 0);
  606.         frame = &z->frames[frame_idx + (z2->base-z1->base)];
  607.         frame->refcount = 0;
  608.         buddy_system_free(z->buddy_system, &frame->buddy_link);
  609.     }
  610. }
  611.  
  612. /** Return old configuration frames into the zone
  613.  *
  614.  * We have several cases
  615.  * - the conf. data is outside of zone -> exit, shall we call frame_free??
  616.  * - the conf. data was created by zone_create or
  617.  *   updated with reduce_region -> free every frame
  618.  *
  619.  * @param newzone The actual zone where freeing should occur
  620.  * @param oldzone Pointer to old zone configuration data that should
  621.  *                be freed from new zone
  622.  */
  623. static void return_config_frames(zone_t *newzone, zone_t *oldzone)
  624. {
  625.     pfn_t pfn;
  626.     frame_t *frame;
  627.     count_t cframes;
  628.     unsigned int i;
  629.  
  630.     pfn = ADDR2PFN((uintptr_t)KA2PA(oldzone));
  631.     cframes = SIZE2FRAMES(zone_conf_size(oldzone->count));
  632.    
  633.     if (pfn < newzone->base || pfn >= newzone->base + newzone->count)
  634.         return;
  635.  
  636.     frame = &newzone->frames[pfn - newzone->base];
  637.     ASSERT(!frame->buddy_order);
  638.  
  639.     for (i = 0; i < cframes; i++) {
  640.         newzone->busy_count++;
  641.         zone_frame_free(newzone, pfn+i-newzone->base);
  642.     }
  643. }
  644.  
  645. /** Reduce allocated block to count of order 0 frames
  646.  *
  647.  * The allocated block need 2^order frames of space. Reduce all frames
  648.  * in block to order 0 and free the unneeded frames. This means, that
  649.  * when freeing the previously allocated block starting with frame_idx,
  650.  * you have to free every frame.
  651.  *
  652.  * @param zone
  653.  * @param frame_idx Index to block
  654.  * @param count Allocated space in block
  655.  */
  656. static void zone_reduce_region(zone_t *zone, pfn_t frame_idx, count_t count)
  657. {
  658.     count_t i;
  659.     uint8_t order;
  660.     frame_t *frame;
  661.    
  662.     ASSERT(frame_idx + count < zone->count);
  663.  
  664.     order = zone->frames[frame_idx].buddy_order;
  665.     ASSERT((count_t) (1 << order) >= count);
  666.  
  667.     /* Reduce all blocks to order 0 */
  668.     for (i = 0; i < (count_t) (1 << order); i++) {
  669.         frame = &zone->frames[i + frame_idx];
  670.         frame->buddy_order = 0;
  671.         if (! frame->refcount)
  672.             frame->refcount = 1;
  673.         ASSERT(frame->refcount == 1);
  674.     }
  675.     /* Free unneeded frames */
  676.     for (i = count; i < (count_t) (1 << order); i++) {
  677.         zone_frame_free(zone, i + frame_idx);
  678.     }
  679. }
  680.  
  681. /** Merge zones z1 and z2
  682.  *
  683.  * - the zones must be 2 zones with no zone existing in between,
  684.  *   which means that z2 = z1+1
  685.  *
  686.  * - When you create a new zone, the frame allocator configuration does
  687.  *   not to be 2^order size. Once the allocator is running it is no longer
  688.  *   possible, merged configuration data occupies more space :-/
  689.  */
  690. void zone_merge(unsigned int z1, unsigned int z2)
  691. {
  692.     ipl_t ipl;
  693.     zone_t *zone1, *zone2, *newzone;
  694.     unsigned int cframes;
  695.     uint8_t order;
  696.     unsigned int i;
  697.     pfn_t pfn;
  698.  
  699.     ipl = interrupts_disable();
  700.     spinlock_lock(&zones.lock);
  701.  
  702.     if (z1 < 0 || z1 >= zones.count || z2 < 0 || z2 >= zones.count)
  703.         goto errout;
  704.     /* We can join only 2 zones with none existing inbetween */
  705.     if (z2-z1 != 1)
  706.         goto errout;
  707.  
  708.     zone1 = zones.info[z1];
  709.     zone2 = zones.info[z2];
  710.     spinlock_lock(&zone1->lock);
  711.     spinlock_lock(&zone2->lock);
  712.  
  713.     cframes = SIZE2FRAMES(zone_conf_size(zone2->base+zone2->count-zone1->base));
  714.     if (cframes == 1)
  715.         order = 0;
  716.     else
  717.         order = fnzb(cframes - 1) + 1;
  718.  
  719.     /* Allocate zonedata inside one of the zones */
  720.     if (zone_can_alloc(zone1, order))
  721.         pfn = zone1->base + zone_frame_alloc(zone1, order);
  722.     else if (zone_can_alloc(zone2, order))
  723.         pfn = zone2->base + zone_frame_alloc(zone2, order);
  724.     else
  725.         goto errout2;
  726.  
  727.     newzone = (zone_t *) PA2KA(PFN2ADDR(pfn));
  728.  
  729.     _zone_merge(newzone, zone1, zone2);
  730.  
  731.     /* Free unneeded config frames */
  732.     zone_reduce_region(newzone, pfn - newzone->base,  cframes);
  733.     /* Subtract zone information from busy frames */
  734.     newzone->busy_count -= cframes;
  735.  
  736.     /* Replace existing zones in zoneinfo list */
  737.     zones.info[z1] = newzone;
  738.     for (i = z2 + 1; i < zones.count; i++)
  739.         zones.info[i - 1] = zones.info[i];
  740.     zones.count--;
  741.  
  742.     /* Free old zone information */
  743.     return_config_frames(newzone, zone1);
  744.     return_config_frames(newzone, zone2);
  745. errout2:
  746.     /* Nobody is allowed to enter to zone, so we are safe
  747.      * to touch the spinlocks last time */
  748.     spinlock_unlock(&zone1->lock);
  749.     spinlock_unlock(&zone2->lock);
  750. errout:
  751.     spinlock_unlock(&zones.lock);
  752.     interrupts_restore(ipl);
  753. }
  754.  
  755. /**
  756.  * Merge all zones into one big zone
  757.  *
  758.  * It is reasonable to do this on systems whose bios reports parts in chunks,
  759.  * so that we could have 1 zone (it's faster).
  760.  */
  761. void zone_merge_all(void)
  762. {
  763.     int count = zones.count;
  764.  
  765.     while (zones.count > 1 && --count) {
  766.         zone_merge(0,1);
  767.         break;
  768.     }
  769. }
  770.  
  771. /** Create frame zone
  772.  *
  773.  * Create new frame zone.
  774.  *
  775.  * @param start Physical address of the first frame within the zone.
  776.  * @param count Count of frames in zone
  777.  * @param z Address of configuration information of zone
  778.  * @param flags Zone flags.
  779.  *
  780.  * @return Initialized zone.
  781.  */
  782. static void zone_construct(pfn_t start, count_t count, zone_t *z, int flags)
  783. {
  784.     unsigned int i;
  785.     uint8_t max_order;
  786.  
  787.     spinlock_initialize(&z->lock, "zone_lock");
  788.     z->base = start;
  789.     z->count = count;
  790.     z->flags = flags;
  791.     z->free_count = count;
  792.     z->busy_count = 0;
  793.  
  794.     /*
  795.      * Compute order for buddy system, initialize
  796.      */
  797.     max_order = fnzb(count);
  798.     z->buddy_system = (buddy_system_t *)&z[1];
  799.    
  800.     buddy_system_create(z->buddy_system, max_order,
  801.                 &zone_buddy_system_operations,
  802.                 (void *) z);
  803.    
  804.     /* Allocate frames _after_ the conframe */
  805.     /* Check sizes */
  806.     z->frames = (frame_t *)((uint8_t *) z->buddy_system + buddy_conf_size(max_order));
  807.     for (i = 0; i < count; i++) {
  808.         frame_initialize(&z->frames[i]);
  809.     }
  810.    
  811.     /* Stuffing frames */
  812.     for (i = 0; i < count; i++) {
  813.         z->frames[i].refcount = 0;
  814.         buddy_system_free(z->buddy_system, &z->frames[i].buddy_link);
  815.     }
  816. }
  817.  
  818. /** Compute configuration data size for zone
  819.  *
  820.  * @param count Size of zone in frames
  821.  * @return Size of zone configuration info (in bytes)
  822.  */
  823. uintptr_t zone_conf_size(count_t count)
  824. {
  825.     int size = sizeof(zone_t) + count*sizeof(frame_t);
  826.     int max_order;
  827.  
  828.     max_order = fnzb(count);
  829.     size += buddy_conf_size(max_order);
  830.     return size;
  831. }
  832.  
  833. /** Create and add zone to system
  834.  *
  835.  * @param start First frame number (absolute)
  836.  * @param count Size of zone in frames
  837.  * @param confframe Where configuration frames are supposed to be.
  838.  *                  Automatically checks, that we will not disturb the
  839.  *                  kernel and possibly init.
  840.  *                  If confframe is given _outside_ this zone, it is expected,
  841.  *                  that the area is already marked BUSY and big enough
  842.  *                  to contain zone_conf_size() amount of data.
  843.  *                  If the confframe is inside the area, the zone free frame
  844.  *                  information is modified not to include it.
  845.  *
  846.  * @return Zone number or -1 on error
  847.  */
  848. int zone_create(pfn_t start, count_t count, pfn_t confframe, int flags)
  849. {
  850.     zone_t *z;
  851.     uintptr_t addr;
  852.     count_t confcount;
  853.     unsigned int i;
  854.     int znum;
  855.  
  856.     /* Theoretically we could have here 0, practically make sure
  857.      * nobody tries to do that. If some platform requires, remove
  858.      * the assert
  859.      */
  860.     ASSERT(confframe);
  861.     /* If conframe is supposed to be inside our zone, then make sure
  862.      * it does not span kernel & init
  863.      */
  864.     confcount = SIZE2FRAMES(zone_conf_size(count));
  865.     if (confframe >= start && confframe < start+count) {
  866.         for (;confframe < start + count; confframe++) {
  867.             addr = PFN2ADDR(confframe);
  868.             if (overlaps(addr, PFN2ADDR(confcount), KA2PA(config.base), config.kernel_size))
  869.                 continue;
  870.            
  871.             if (overlaps(addr, PFN2ADDR(confcount), KA2PA(config.stack_base), config.stack_size))
  872.                 continue;
  873.            
  874.             bool overlap = false;
  875.             count_t i;
  876.             for (i = 0; i < init.cnt; i++)
  877.                 if (overlaps(addr, PFN2ADDR(confcount), KA2PA(init.tasks[i].addr), init.tasks[i].size)) {
  878.                     overlap = true;
  879.                     break;
  880.                 }
  881.             if (overlap)
  882.                 continue;
  883.            
  884.             break;
  885.         }
  886.         if (confframe >= start + count)
  887.             panic("Cannot find configuration data for zone.");
  888.     }
  889.  
  890.     z = (zone_t *)PA2KA(PFN2ADDR(confframe));
  891.     zone_construct(start, count, z, flags);
  892.     znum = zones_add_zone(z);
  893.     if (znum == -1)
  894.         return -1;
  895.  
  896.     /* If confdata in zone, mark as unavailable */
  897.     if (confframe >= start && confframe < start + count)
  898.         for (i = confframe; i < confframe + confcount; i++) {
  899.             zone_mark_unavailable(z, i - z->base);
  900.         }
  901.     return znum;
  902. }
  903.  
  904. /***************************************/
  905. /* Frame functions */
  906.  
  907. /** Set parent of frame */
  908. void frame_set_parent(pfn_t pfn, void *data, unsigned int hint)
  909. {
  910.     zone_t *zone = find_zone_and_lock(pfn, &hint);
  911.  
  912.     ASSERT(zone);
  913.  
  914.     zone_get_frame(zone, pfn-zone->base)->parent = data;
  915.     spinlock_unlock(&zone->lock);
  916. }
  917.  
  918. void * frame_get_parent(pfn_t pfn, unsigned int hint)
  919. {
  920.     zone_t *zone = find_zone_and_lock(pfn, &hint);
  921.     void *res;
  922.  
  923.     ASSERT(zone);
  924.     res = zone_get_frame(zone, pfn - zone->base)->parent;
  925.    
  926.     spinlock_unlock(&zone->lock);
  927.     return res;
  928. }
  929.  
  930. /** Allocate power-of-two frames of physical memory.
  931.  *
  932.  * @param order  Allocate exactly 2^order frames.
  933.  * @param flags  Flags for host zone selection and address processing.
  934.  * @param pzone  Preferred zone
  935.  *
  936.  * @return Physical address of the allocated frame.
  937.  *
  938.  */
  939. void * frame_alloc_generic(uint8_t order, int flags, unsigned int *pzone)
  940. {
  941.     ipl_t ipl;
  942.     int freed;
  943.     pfn_t v;
  944.     zone_t *zone;
  945.    
  946. loop:
  947.     ipl = interrupts_disable();
  948.    
  949.     /*
  950.      * First, find suitable frame zone.
  951.      */
  952.     zone = find_free_zone_and_lock(order, pzone);
  953.    
  954.     /* If no memory, reclaim some slab memory,
  955.        if it does not help, reclaim all */
  956.     if (!zone && !(flags & FRAME_NO_RECLAIM)) {
  957.         freed = slab_reclaim(0);
  958.         if (freed)
  959.             zone = find_free_zone_and_lock(order, pzone);
  960.         if (!zone) {
  961.             freed = slab_reclaim(SLAB_RECLAIM_ALL);
  962.             if (freed)
  963.                 zone = find_free_zone_and_lock(order, pzone);
  964.         }
  965.     }
  966.     if (!zone) {
  967.         /*
  968.          * TODO: Sleep until frames are available again.
  969.          */
  970.         interrupts_restore(ipl);
  971.  
  972.         if (flags & FRAME_ATOMIC)
  973.             return 0;
  974.        
  975.         panic("Sleep not implemented.\n");
  976.         goto loop;
  977.     }
  978.    
  979.     v = zone_frame_alloc(zone, order);
  980.     v += zone->base;
  981.  
  982.     spinlock_unlock(&zone->lock);
  983.     interrupts_restore(ipl);
  984.  
  985.     if (flags & FRAME_KA)
  986.         return (void *)PA2KA(PFN2ADDR(v));
  987.     return (void *)PFN2ADDR(v);
  988. }
  989.  
  990. /** Free a frame.
  991.  *
  992.  * Find respective frame structure for supplied physical frame address.
  993.  * Decrement frame reference count.
  994.  * If it drops to zero, move the frame structure to free list.
  995.  *
  996.  * @param Frame Physical Address of of the frame to be freed.
  997.  */
  998. void frame_free(uintptr_t frame)
  999. {
  1000.     ipl_t ipl;
  1001.     zone_t *zone;
  1002.     pfn_t pfn = ADDR2PFN(frame);
  1003.  
  1004.     ipl = interrupts_disable();
  1005.    
  1006.     /*
  1007.      * First, find host frame zone for addr.
  1008.      */
  1009.     zone = find_zone_and_lock(pfn,NULL);
  1010.     ASSERT(zone);
  1011.    
  1012.     zone_frame_free(zone, pfn-zone->base);
  1013.    
  1014.     spinlock_unlock(&zone->lock);
  1015.     interrupts_restore(ipl);
  1016. }
  1017.  
  1018. /** Add reference to frame.
  1019.  *
  1020.  * Find respective frame structure for supplied PFN and
  1021.  * increment frame reference count.
  1022.  *
  1023.  * @param pfn Frame number of the frame to be freed.
  1024.  */
  1025. void frame_reference_add(pfn_t pfn)
  1026. {
  1027.     ipl_t ipl;
  1028.     zone_t *zone;
  1029.     frame_t *frame;
  1030.  
  1031.     ipl = interrupts_disable();
  1032.    
  1033.     /*
  1034.      * First, find host frame zone for addr.
  1035.      */
  1036.     zone = find_zone_and_lock(pfn,NULL);
  1037.     ASSERT(zone);
  1038.    
  1039.     frame = &zone->frames[pfn-zone->base];
  1040.     frame->refcount++;
  1041.    
  1042.     spinlock_unlock(&zone->lock);
  1043.     interrupts_restore(ipl);
  1044. }
  1045.  
  1046. /** Mark given range unavailable in frame zones */
  1047. void frame_mark_unavailable(pfn_t start, count_t count)
  1048. {
  1049.     unsigned int i;
  1050.     zone_t *zone;
  1051.     unsigned int prefzone = 0;
  1052.    
  1053.     for (i = 0; i < count; i++) {
  1054.         zone = find_zone_and_lock(start + i, &prefzone);
  1055.         if (!zone) /* PFN not found */
  1056.             continue;
  1057.         zone_mark_unavailable(zone, start + i - zone->base);
  1058.  
  1059.         spinlock_unlock(&zone->lock);
  1060.     }
  1061. }
  1062.  
  1063. /** Initialize physical memory management
  1064.  *
  1065.  * Initialize physical memory managemnt.
  1066.  */
  1067. void frame_init(void)
  1068. {
  1069.     if (config.cpu_active == 1) {
  1070.         zones.count = 0;
  1071.         spinlock_initialize(&zones.lock, "zones.lock");
  1072.     }
  1073.     /* Tell the architecture to create some memory */
  1074.     frame_arch_init();
  1075.     if (config.cpu_active == 1) {
  1076.         frame_mark_unavailable(ADDR2PFN(KA2PA(config.base)), SIZE2FRAMES(config.kernel_size));
  1077.         frame_mark_unavailable(ADDR2PFN(KA2PA(config.stack_base)), SIZE2FRAMES(config.stack_size));
  1078.        
  1079.         count_t i;
  1080.         for (i = 0; i < init.cnt; i++)
  1081.             frame_mark_unavailable(ADDR2PFN(KA2PA(init.tasks[i].addr)), SIZE2FRAMES(init.tasks[i].size));
  1082.  
  1083.         if (ballocs.size)
  1084.             frame_mark_unavailable(ADDR2PFN(KA2PA(ballocs.base)), SIZE2FRAMES(ballocs.size));
  1085.  
  1086.         /* Black list first frame, as allocating NULL would
  1087.          * fail in some places */
  1088.         frame_mark_unavailable(0, 1);
  1089.     }
  1090. }
  1091.  
  1092.  
  1093.  
  1094. /** Prints list of zones
  1095.  *
  1096.  */
  1097. void zone_print_list(void) {
  1098.     zone_t *zone = NULL;
  1099.     unsigned int i;
  1100.     ipl_t ipl;
  1101.  
  1102.     ipl = interrupts_disable();
  1103.     spinlock_lock(&zones.lock);
  1104.     printf("#  base address free frames  busy frames\n");
  1105.     printf("-- ------------ ------------ ------------\n");
  1106.     for (i = 0; i < zones.count; i++) {
  1107.         zone = zones.info[i];
  1108.         spinlock_lock(&zone->lock);
  1109.         printf("%-2d %12p %12zd %12zd\n", i, PFN2ADDR(zone->base), zone->free_count, zone->busy_count);
  1110.         spinlock_unlock(&zone->lock);
  1111.     }
  1112.     spinlock_unlock(&zones.lock);
  1113.     interrupts_restore(ipl);
  1114. }
  1115.  
  1116. /** Prints zone details.
  1117.  *
  1118.  * @param num Zone base address or zone number.
  1119.  */
  1120. void zone_print_one(unsigned int num) {
  1121.     zone_t *zone = NULL;
  1122.     ipl_t ipl;
  1123.     unsigned int i;
  1124.  
  1125.     ipl = interrupts_disable();
  1126.     spinlock_lock(&zones.lock);
  1127.  
  1128.     for (i = 0; i < zones.count; i++) {
  1129.         if (i == num || PFN2ADDR(zones.info[i]->base) == num) {
  1130.             zone = zones.info[i];
  1131.             break;
  1132.         }
  1133.     }
  1134.     if (!zone) {
  1135.         printf("Zone not found.\n");
  1136.         goto out;
  1137.     }
  1138.    
  1139.     spinlock_lock(&zone->lock);
  1140.     printf("Memory zone information\n");
  1141.     printf("Zone base address: %#.*p\n", sizeof(uintptr_t) * 2, PFN2ADDR(zone->base));
  1142.     printf("Zone size: %zd frames (%zdK)\n", zone->count, ((zone->count) * FRAME_SIZE) >> 10);
  1143.     printf("Allocated space: %zd frames (%zdK)\n", zone->busy_count, (zone->busy_count * FRAME_SIZE) >> 10);
  1144.     printf("Available space: %zd frames (%zdK)\n", zone->free_count, (zone->free_count * FRAME_SIZE) >> 10);
  1145.     buddy_system_structure_print(zone->buddy_system, FRAME_SIZE);
  1146.    
  1147.     spinlock_unlock(&zone->lock);
  1148. out:
  1149.     spinlock_unlock(&zones.lock);
  1150.     interrupts_restore(ipl);
  1151. }
  1152.  
  1153. /** @}
  1154.  */
  1155.