Subversion Repositories Kolibri OS

Rev

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

  1.  
  2. #include <types.h>
  3. #include <core.h>
  4. #include <spinlock.h>
  5. #include <link.h>
  6. #include <mm.h>
  7.  
  8. extern u32_t pg_balloc;
  9.  
  10. extern u32_t mem_amount;
  11.  
  12. void __fastcall *balloc(u32_t size);
  13.  
  14. zone_t z_core;
  15.  
  16. static inline u32_t save_edx(void)
  17. {
  18.   u32_t val;
  19.   asm volatile ("movl %%edx, %0":"=r"(val));
  20.   return val;
  21. };
  22.  
  23. static inline void restore_edx(u32_t val)
  24. {
  25.   asm volatile (""::"d" (val) );
  26. };
  27.  
  28. static void buddy_system_create(zone_t *z);
  29. static void  __fastcall buddy_system_free(zone_t *z, link_t *block);
  30. static void zone_mark_unavailable(zone_t *zone, index_t frame_idx);
  31.  
  32. static addr_t __fastcall zone_alloc(zone_t *zone, u32_t order);
  33. void __fastcall zone_free(zone_t *zone, pfn_t frame_idx);
  34.  
  35. size_t buddy_conf_size(int max_order);
  36.  
  37. static inline void frame_initialize(frame_t *frame);
  38.  
  39. void init_mm();
  40.  
  41.  
  42. static void zone_create(zone_t *z, pfn_t start, count_t count);
  43. static void zone_reserve(zone_t *z, pfn_t base, count_t count);
  44. static void zone_release(zone_t *z, pfn_t base, count_t count);
  45.  
  46.  
  47. void init_mm()
  48. {
  49.    int i;
  50.  
  51.    u32_t   base;
  52.    u32_t   size;
  53.    count_t pages;
  54.    size_t  conf_size;
  55.    size_t  core_size;
  56.  
  57.    pages = mem_amount >> FRAME_WIDTH;
  58.    DBG("last page = %x total pages =  %x\n",mem_amount, pages);
  59.  
  60.    conf_size = pages*sizeof(frame_t);
  61.    DBG("conf_size = %x  free mem start =%x\n",conf_size, pg_balloc);
  62.  
  63.    zone_create(&z_core, 0, pages);
  64.  
  65.    zone_release(&z_core, 0, pages);
  66.    zone_reserve(&z_core, 0, pg_balloc >> FRAME_WIDTH);
  67.  
  68.  
  69. #if 0
  70.    core_size = (pg_free+conf_size+1024*1024*5)&(-1024*1024*4);
  71. //   printf("core size = %x core heap = %x\n",core_size,core_size-conf_size-pg_free);
  72.  
  73.    u32_t p0, p1;
  74.    u32_t b0, b1;
  75.  
  76.    p0 = core_size>>12;
  77.    p1 = (last_page-core_size)>>12;
  78.  
  79.    b0 = p0*sizeof(frame_t);
  80.    b1 = p1*sizeof(frame_t);
  81.  
  82. //   printf("buddy_0: %x pages  conf_size %x\n", p0, b0);
  83. //   printf("buddy_1: %x pages  conf_size %x\n", p1, b1);
  84.  
  85.    zone_create(&z_core, 0, p0);
  86.    zone_create(&z_user, p0, p1);
  87.  
  88. //   printf("free mem start = %x\n",pg_balloc);
  89.  
  90.    for(i = 0; i < mem_counter; i++)
  91.    {
  92.      u32_t page;
  93.      if( mem_table[i].type != 1)
  94.        continue;
  95.      page = (mem_table[i].base+mem_table[i].size)&(~4095);
  96.      if(page > last_page)
  97.         last_page = page;
  98.  
  99.      zone_release(&z_core,mem_table[i].base>>12, mem_table[i].size>>12);
  100.      zone_release(&z_user,mem_table[i].base>>12, mem_table[i].size>>12);
  101.    };
  102.    zone_reserve(&z_core, 0x100000>>12,(pg_balloc-OS_BASE-0x100000)>>12);
  103. #endif
  104. };
  105.  
  106. static void zone_create(zone_t *z, pfn_t start, count_t count)
  107. {
  108.         unsigned int i;
  109. //  int znum;
  110.  
  111.         /* Theoretically we could have here 0, practically make sure
  112.          * nobody tries to do that. If some platform requires, remove
  113.          * the assert
  114.          */
  115. //  ASSERT(confframe);
  116.         /* If conframe is supposed to be inside our zone, then make sure
  117.          * it does not span kernel & init
  118.          */
  119.  
  120. //  printf("create zone: base %x count %x\n", start, count);
  121.  
  122.   spinlock_initialize(&z->lock);
  123.         z->base = start;
  124.         z->count = count;
  125.         z->free_count = count;
  126.         z->busy_count = 0;
  127.  
  128.   z->max_order = fnzb(count);
  129.  
  130.   ASSERT(z->max_order < BUDDY_SYSTEM_INNER_BLOCK);
  131.  
  132.   for (i = 0; i <= z->max_order; i++)
  133.     list_initialize(&z->order[i]);
  134.  
  135.   z->frames = (frame_t *)balloc(count*sizeof(frame_t));
  136.  
  137.         for (i = 0; i < count; i++) {
  138.                 frame_initialize(&z->frames[i]);
  139.         }
  140. }
  141.  
  142. static void zone_reserve(zone_t *z, pfn_t base, count_t count)
  143. {
  144.   int i;
  145.   pfn_t top = base+count;
  146.  
  147.   if( (base+count < z->base)||(base > z->base+z->count))
  148.     return;
  149.  
  150.   if(base < z->base)
  151.     base = z->base;
  152.  
  153.   if(top > z->base+z->count)
  154.      top = z->base+z->count;
  155.  
  156.   DBG("zone reserve base %x top %x\n", base, top);
  157.  
  158.   for (i = base; i < top; i++)
  159.     zone_mark_unavailable(z, i - z->base);
  160.  
  161. };
  162.  
  163. static void zone_release(zone_t *z, pfn_t base, count_t count)
  164. {
  165.   int i;
  166.   pfn_t top = base+count;
  167.  
  168.   if( (base+count < z->base)||(base > z->base+z->count))
  169.     return;
  170.  
  171.   if(base < z->base)
  172.     base = z->base;
  173.  
  174.   if(top > z->base+z->count)
  175.      top = z->base+z->count;
  176.  
  177.   DBG("zone release base %x top %x\n", base, top);
  178.  
  179.   for (i = base; i < top; i++) {
  180.     z->frames[i-z->base].refcount = 0;
  181.     buddy_system_free(z, &z->frames[i-z->base].buddy_link);
  182.     }
  183. };
  184.  
  185.  
  186. static inline index_t frame_index(zone_t *zone, frame_t *frame)
  187. {
  188.         return (index_t) (frame - zone->frames);
  189. }
  190.  
  191. static inline index_t frame_index_abs(zone_t *zone, frame_t *frame)
  192. {
  193.   return (index_t) (frame - zone->frames);
  194. }
  195.  
  196. static inline int frame_index_valid(zone_t *zone, index_t index)
  197. {
  198.         return (index < zone->count);
  199. }
  200.  
  201. /** Compute pfn_t from frame_t pointer & zone pointer */
  202. static inline index_t make_frame_index(zone_t *zone, frame_t *frame)
  203. {
  204.         return (frame - zone->frames);
  205. }
  206.  
  207. static inline void frame_initialize(frame_t *frame)
  208. {
  209.         frame->refcount = 1;
  210.         frame->buddy_order = 0;
  211. }
  212.  
  213.  
  214. static link_t *buddy_find_block(zone_t *zone, link_t *child,
  215.     u32_t order)
  216. {
  217.         frame_t *frame;
  218.         index_t index;
  219.  
  220.   frame = (frame_t*)child;
  221.  
  222.         index = frame_index(zone, frame);
  223.         do {
  224.                 if (zone->frames[index].buddy_order != order) {
  225.                         return &zone->frames[index].buddy_link;
  226.                 }
  227.         } while(index-- > 0);
  228.         return NULL;
  229. }
  230.  
  231. static inline link_t * buddy_bisect(zone_t *z, link_t *block) {
  232.         frame_t *frame_l, *frame_r;
  233.  
  234.   frame_l = (frame_t*)block;
  235.         frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));
  236.  
  237.         return &frame_r->buddy_link;
  238. }
  239.  
  240. static inline u32_t buddy_get_order(zone_t *z, link_t *block) {
  241.   frame_t *frame = (frame_t*)block;
  242.         return frame->buddy_order;
  243. }
  244.  
  245. static inline void buddy_set_order(zone_t *z, link_t *block,
  246.     u32_t order) {
  247.   frame_t *frame = (frame_t*)block;
  248.         frame->buddy_order = order;
  249. }
  250.  
  251. static link_t *buddy_coalesce(zone_t *z, link_t *block_1,
  252.     link_t *block_2)
  253. {
  254.         frame_t *frame1, *frame2;
  255.  
  256.   frame1 = (frame_t*)block_1;
  257.   frame2 = (frame_t*)block_2;
  258.  
  259.         return frame1 < frame2 ? block_1 : block_2;
  260. }
  261.  
  262. static inline void buddy_mark_busy(zone_t *z, link_t * block) {
  263.   frame_t * frame = (frame_t*)block;
  264.         frame->refcount = 1;
  265. }
  266.  
  267. static inline void buddy_mark_available(zone_t *z, link_t *block) {
  268.   frame_t *frame = (frame_t*)block;
  269.         frame->refcount = 0;
  270. }
  271.  
  272. #define IS_BUDDY_ORDER_OK(index, order)   \
  273.     ((~(((u32_t) -1) << (order)) & (index)) == 0)
  274. #define IS_BUDDY_LEFT_BLOCK_ABS(zone, frame)  \
  275.   (((frame_index_abs((zone), (frame)) >> (frame)->buddy_order) & 0x1) == 0)
  276.  
  277. #define IS_BUDDY_RIGHT_BLOCK_ABS(zone, frame) \
  278.         (((frame_index_abs((zone), (frame)) >> (frame)->buddy_order) & 0x1) == 1)
  279.  
  280. static link_t *find_buddy(zone_t *zone, link_t *block)
  281. {
  282.         frame_t *frame;
  283.         index_t index;
  284.   u32_t is_left, is_right;
  285.  
  286.   frame = (frame_t*)block;
  287.   ASSERT(IS_BUDDY_ORDER_OK(frame_index_abs(zone, frame),frame->buddy_order));
  288.  
  289.         is_left = IS_BUDDY_LEFT_BLOCK_ABS(zone, frame);
  290.         is_right = IS_BUDDY_RIGHT_BLOCK_ABS(zone, frame);
  291.  
  292.   ASSERT(is_left ^ is_right);
  293.         if (is_left) {
  294.                 index = (frame_index(zone, frame)) + (1 << frame->buddy_order);
  295.         } else {        /* if (is_right) */
  296.                 index = (frame_index(zone, frame)) - (1 << frame->buddy_order);
  297.         }
  298.  
  299.         if (frame_index_valid(zone, index)) {
  300.                 if (zone->frames[index].buddy_order == frame->buddy_order &&
  301.                     zone->frames[index].refcount == 0) {
  302.                         return &zone->frames[index].buddy_link;
  303.                 }
  304.         }
  305.  
  306.         return NULL;
  307. }
  308.  
  309. static link_t* __fastcall buddy_system_alloc_block(zone_t *z, link_t *block)
  310. {
  311.         link_t *left,*right, *tmp;
  312.   u32_t order;
  313.  
  314.   left = buddy_find_block(z, block, BUDDY_SYSTEM_INNER_BLOCK);
  315.   ASSERT(left);
  316.         list_remove(left);
  317.         while (1) {
  318.     if (! buddy_get_order(z,left)) {
  319.       buddy_mark_busy(z, left);
  320.                         return left;
  321.                 }
  322.  
  323.     order = buddy_get_order(z, left);
  324.  
  325.     right = buddy_bisect(z, left);
  326.     buddy_set_order(z, left, order-1);
  327.     buddy_set_order(z, right, order-1);
  328.  
  329.     tmp = buddy_find_block(z, block, BUDDY_SYSTEM_INNER_BLOCK);
  330.  
  331.                 if (tmp == right) {
  332.                         right = left;
  333.                         left = tmp;
  334.                 }
  335.     ASSERT(tmp == left);
  336.     buddy_mark_busy(z, left);
  337.     buddy_system_free(z, right);
  338.     buddy_mark_available(z, left);
  339.         }
  340. }
  341.  
  342. static void __fastcall buddy_system_free(zone_t *z, link_t *block)
  343. {
  344.         link_t *buddy, *hlp;
  345.   u8_t i;
  346.  
  347.         /*
  348.          * Determine block's order.
  349.          */
  350.   i = buddy_get_order(z, block);
  351.  
  352.   ASSERT(i <= z->max_order);
  353.  
  354.   if (i != z->max_order) {
  355.                 /*
  356.                  * See if there is any buddy in the list of order i.
  357.                  */
  358.     buddy = find_buddy(z, block);
  359.                 if (buddy) {
  360.  
  361.       ASSERT(buddy_get_order(z, buddy) == i);
  362.                         /*
  363.                          * Remove buddy from the list of order i.
  364.                          */
  365.                         list_remove(buddy);
  366.  
  367.                         /*
  368.                          * Invalidate order of both block and buddy.
  369.                          */
  370.       buddy_set_order(z, block, BUDDY_SYSTEM_INNER_BLOCK);
  371.       buddy_set_order(z, buddy, BUDDY_SYSTEM_INNER_BLOCK);
  372.  
  373.                         /*
  374.                          * Coalesce block and buddy into one block.
  375.                          */
  376.       hlp = buddy_coalesce(z, block, buddy);
  377.  
  378.                         /*
  379.                          * Set order of the coalesced block to i + 1.
  380.                          */
  381.       buddy_set_order(z, hlp, i + 1);
  382.  
  383.                         /*
  384.                          * Recursively add the coalesced block to the list of order i + 1.
  385.                          */
  386.       buddy_system_free(z, hlp);
  387.                         return;
  388.                 }
  389.         }
  390.  
  391.         /*
  392.          * Insert block into the list of order i.
  393.          */
  394.   list_append(block, &z->order[i]);
  395.  
  396. }
  397.  
  398. static inline frame_t * zone_get_frame(zone_t *zone, index_t frame_idx)
  399. {
  400.   ASSERT(frame_idx < zone->count);
  401.         return &zone->frames[frame_idx];
  402. }
  403.  
  404. static void zone_mark_unavailable(zone_t *zone, index_t frame_idx)
  405. {
  406.         frame_t *frame;
  407.         link_t *link;
  408.  
  409.         frame = zone_get_frame(zone, frame_idx);
  410.         if (frame->refcount)
  411.                 return;
  412.   link = buddy_system_alloc_block(zone, &frame->buddy_link);
  413.   ASSERT(link);
  414.         zone->free_count--;
  415. }
  416.  
  417. static link_t* __fastcall buddy_system_alloc(zone_t *z, u32_t i)
  418. {
  419.         link_t *res, *hlp;
  420.  
  421.   ASSERT(i <= z->max_order);
  422.  
  423.         /*
  424.          * If the list of order i is not empty,
  425.          * the request can be immediatelly satisfied.
  426.          */
  427.         if (!list_empty(&z->order[i])) {
  428.                 res = z->order[i].next;
  429.                 list_remove(res);
  430.                 buddy_mark_busy(z, res);
  431.                 return res;
  432.         }
  433.         /*
  434.          * If order i is already the maximal order,
  435.          * the request cannot be satisfied.
  436.          */
  437.         if (i == z->max_order)
  438.                 return NULL;
  439.  
  440.         /*
  441.          * Try to recursively satisfy the request from higher order lists.
  442.          */
  443.         hlp = buddy_system_alloc(z, i + 1);
  444.  
  445.         /*
  446.          * The request could not be satisfied
  447.          * from higher order lists.
  448.          */
  449.         if (!hlp)
  450.                 return NULL;
  451.  
  452.         res = hlp;
  453.  
  454.         /*
  455.          * Bisect the block and set order of both of its parts to i.
  456.          */
  457.         hlp = buddy_bisect(z, res);
  458.         buddy_set_order(z, res, i);
  459.         buddy_set_order(z, hlp, i);
  460.  
  461.         /*
  462.          * Return the other half to buddy system. Mark the first part
  463.          * full, so that it won't coalesce again.
  464.          */
  465.         buddy_mark_busy(z, res);
  466.         buddy_system_free(z, hlp);
  467.  
  468.         return res;
  469.  
  470. }
  471.  
  472.  
  473. static __fastcall pfn_t zone_frame_alloc(zone_t *zone, u32_t order)
  474. {
  475.         pfn_t v;
  476.         link_t *tmp;
  477.         frame_t *frame;
  478.  
  479.  
  480.         /* Allocate frames from zone buddy system */
  481.         tmp = buddy_system_alloc(zone, order);
  482.  
  483.   ASSERT(tmp);
  484.  
  485.         /* Update zone information. */
  486.         zone->free_count -= (1 << order);
  487.         zone->busy_count += (1 << order);
  488.  
  489.         /* Frame will be actually a first frame of the block. */
  490.         frame = (frame_t*)tmp;
  491.  
  492.         /* get frame address */
  493.         v = make_frame_index(zone, frame);
  494.  
  495.         return v;
  496. }
  497.  
  498.  
  499. /** Set parent of frame */
  500. void __fastcall frame_set_parent(pfn_t pfn, void *data)
  501. {
  502. /*  zone_t *zone = find_zone_and_lock(pfn, &hint);
  503.   ASSERT(zone);
  504.  */
  505.  
  506.   spinlock_lock(&z_core.lock);
  507.     zone_get_frame(&z_core, pfn-z_core.base)->parent = data;
  508.   spinlock_unlock(&z_core.lock);
  509. }
  510.  
  511. void* __fastcall frame_get_parent(pfn_t pfn)
  512. {
  513. //      zone_t *zone = find_zone_and_lock(pfn, &hint);
  514.         void *res;
  515.  
  516.   spinlock_lock(&z_core.lock);
  517.     res = zone_get_frame(&z_core, pfn)->parent;
  518.   spinlock_unlock(&z_core.lock);
  519.  
  520.         return res;
  521. }
  522.  
  523. static inline int to_order(count_t arg)
  524. {
  525.   int n;
  526.   asm volatile (
  527.                 "xorl %eax, %eax \n\t"
  528.                 "bsr %edx, %eax \n\t"
  529.                 "incl %eax"
  530.                 :"=a" (n)
  531.                 :"d"(arg)
  532.                 );
  533.         return n;
  534. }
  535.  
  536.  
  537. addr_t __fastcall zone_alloc(zone_t *zone, u32_t order)
  538. {
  539.    eflags_t efl;
  540.    pfn_t v;
  541.  
  542.    efl = safe_cli();
  543.      spinlock_lock(&zone->lock);
  544.        v = zone_frame_alloc(zone, order);
  545.        v += zone->base;
  546.      spinlock_unlock(&zone->lock);
  547.    safe_sti(efl);
  548.  
  549.    return (v << FRAME_WIDTH);
  550. }
  551.  
  552. addr_t  __fastcall core_alloc(u32_t order)
  553. {
  554.    eflags_t efl;
  555.    pfn_t v;
  556.  
  557.    efl = safe_cli();
  558.      spinlock_lock(&z_core.lock);
  559.        v = zone_frame_alloc(&z_core, order);
  560.      spinlock_unlock(&z_core.lock);
  561.    safe_sti(efl);
  562.  
  563.    DBG("core alloc: %x, size %x   remain  %d\n", v << FRAME_WIDTH,
  564.         ((1<<order)<<12), z_core.free_count);
  565.  
  566.    return (v << FRAME_WIDTH);
  567. };
  568.  
  569. void __fastcall core_free(addr_t frame)
  570. {
  571.    eflags_t efl;
  572.  
  573.    efl = safe_cli();
  574.      spinlock_lock(&z_core.lock);
  575.        zone_free(&z_core, frame>>12);
  576.      spinlock_unlock(&z_core.lock);
  577.    safe_sti(efl);
  578.  
  579.    DBG("core free %x  remain %d\n", frame, z_core.free_count);
  580.  
  581. }
  582.  
  583. addr_t alloc_page()                                //obsolete
  584. {
  585.    eflags_t efl;
  586.    u32_t    edx;
  587.    pfn_t v;
  588.  
  589.    edx = save_edx();
  590.    efl = safe_cli();
  591.      spinlock_lock(&z_core.lock);
  592.        v = zone_frame_alloc(&z_core, 0);
  593.      spinlock_unlock(&z_core.lock);
  594.    safe_sti(efl);
  595.  
  596.    DBG("alloc_page: %x   remain  %d\n", v << FRAME_WIDTH, z_core.free_count);
  597.  
  598.    restore_edx(edx);
  599.    return (v << FRAME_WIDTH);
  600. };
  601.  
  602. void __fastcall zone_free(zone_t *zone, pfn_t frame_idx)
  603. {
  604.         frame_t *frame;
  605.   u32_t order;
  606.  
  607.         frame = &zone->frames[frame_idx];
  608.  
  609.         /* remember frame order */
  610.         order = frame->buddy_order;
  611.  
  612.   ASSERT(frame->refcount);
  613.  
  614.     if (!--frame->refcount)
  615.     {
  616.                 buddy_system_free(zone, &frame->buddy_link);
  617.  
  618.                 /* Update zone information. */
  619.                 zone->free_count += (1 << order);
  620.                 zone->busy_count -= (1 << order);
  621.         }
  622. }
  623.  
  624. void frame_free(addr_t frame)           //export
  625. {
  626.    eflags_t efl;
  627.    zone_t *zone;
  628.  
  629.    efl = safe_cli();
  630.      spinlock_lock(&z_core.lock);
  631.        zone_free(&z_core, frame>>12);
  632.      spinlock_unlock(&z_core.lock);
  633.   safe_sti(efl);
  634. }
  635.  
  636. count_t get_free_mem()
  637. {
  638.    return z_core.free_count;
  639. }
  640.  
  641.