WebSVN – Kolibri OS – Diff – /kernel/branches/kolibri_pe/core/mm.c


#include 
#include 
#include 
#include 
#include 
 
extern u32_t pg_balloc;
 
extern u32_t mem_amount;
 
void __fastcall *balloc(u32_t size);
 
zone_t z_core;
 
static inline u32_t save_edx(void)
{
  u32_t val;
  asm volatile ("movl %%edx, %0":"=r"(val));
  return val;
};
 
static inline void restore_edx(u32_t val)
{
  asm volatile (""::"d" (val) );
};
 
static void buddy_system_create(zone_t *z);
static void  __fastcall buddy_system_free(zone_t *z, link_t *block);
static void zone_mark_unavailable(zone_t *zone, index_t frame_idx);
 
static addr_t __fastcall zone_alloc(zone_t *zone, u32_t order);
void __fastcall zone_free(zone_t *zone, pfn_t frame_idx);
 
size_t buddy_conf_size(int max_order);
 
static inline void frame_initialize(frame_t *frame);
 
void init_mm();
 
 
static void zone_create(zone_t *z, pfn_t start, count_t count);
static void zone_reserve(zone_t *z, pfn_t base, count_t count);
static void zone_release(zone_t *z, pfn_t base, count_t count);
 
 
void init_mm()
{
   int i;
 
   u32_t   base;
   u32_t   size;
   count_t pages;
   size_t  conf_size;
   size_t  core_size;
 
   pages = mem_amount >> FRAME_WIDTH;
   DBG("last page = %x total pages =  %x\n",mem_amount, pages);
 
   conf_size = pages*sizeof(frame_t);
   DBG("conf_size = %x  free mem start =%x\n",conf_size, pg_balloc);
 
   zone_create(&z_core, 0, pages);
 
   zone_release(&z_core, 0, pages);
   zone_reserve(&z_core, 0, pg_balloc >> FRAME_WIDTH);
 
 
#if 0
   core_size = (pg_free+conf_size+1024*1024*5)&(-1024*1024*4);
//   printf("core size = %x core heap = %x\n",core_size,core_size-conf_size-pg_free);
 
   u32_t p0, p1;
   u32_t b0, b1;
 
   p0 = core_size>>12;
   p1 = (last_page-core_size)>>12;
 
   b0 = p0*sizeof(frame_t);
   b1 = p1*sizeof(frame_t);
 
//   printf("buddy_0: %x pages  conf_size %x\n", p0, b0);
//   printf("buddy_1: %x pages  conf_size %x\n", p1, b1);
 
   zone_create(&z_core, 0, p0);
   zone_create(&z_user, p0, p1);
 
//   printf("free mem start = %x\n",pg_balloc);
 
   for(i = 0; i < mem_counter; i++)
   {
     u32_t page;
     if( mem_table[i].type != 1)
       continue;
     page = (mem_table[i].base+mem_table[i].size)&(~4095);
     if(page > last_page)
        last_page = page;
 
     zone_release(&z_core,mem_table[i].base>>12, mem_table[i].size>>12);
     zone_release(&z_user,mem_table[i].base>>12, mem_table[i].size>>12);
   };
   zone_reserve(&z_core, 0x100000>>12,(pg_balloc-OS_BASE-0x100000)>>12);
#endif
};
 
static void zone_create(zone_t *z, pfn_t start, count_t count)
{
	unsigned int i;
//  int znum;
 
	/* Theoretically we could have here 0, practically make sure
	 * nobody tries to do that. If some platform requires, remove
	 * the assert
	 */
//  ASSERT(confframe);
	/* If conframe is supposed to be inside our zone, then make sure
	 * it does not span kernel & init
	 */
 
//  printf("create zone: base %x count %x\n", start, count);
 
  spinlock_initialize(&z->lock);
	z->base = start;
	z->count = count;
	z->free_count = count;
	z->busy_count = 0;
 
  z->max_order = fnzb(count);
 
  ASSERT(z->max_order < BUDDY_SYSTEM_INNER_BLOCK);
 
  for (i = 0; i <= z->max_order; i++)
    list_initialize(&z->order[i]);
 
  z->frames = (frame_t *)balloc(count*sizeof(frame_t));
 
	for (i = 0; i < count; i++) {
		frame_initialize(&z->frames[i]);
	}
}
 
static void zone_reserve(zone_t *z, pfn_t base, count_t count)
{
  int i;
  pfn_t top = base+count;
 
  if( (base+count < z->base)||(base > z->base+z->count))
    return;
 
  if(base < z->base)
    base = z->base;
 
  if(top > z->base+z->count)
     top = z->base+z->count;
 
  DBG("zone reserve base %x top %x\n", base, top);
 
  for (i = base; i < top; i++)
    zone_mark_unavailable(z, i - z->base);
 
};
 
static void zone_release(zone_t *z, pfn_t base, count_t count)
{
  int i;
  pfn_t top = base+count;
 
  if( (base+count < z->base)||(base > z->base+z->count))
    return;
 
  if(base < z->base)
    base = z->base;
 
  if(top > z->base+z->count)
     top = z->base+z->count;
 
  DBG("zone release base %x top %x\n", base, top);
 
  for (i = base; i < top; i++) {
    z->frames[i-z->base].refcount = 0;
    buddy_system_free(z, &z->frames[i-z->base].buddy_link);
    }
};
 
 
static inline index_t frame_index(zone_t *zone, frame_t *frame)
{
	return (index_t) (frame - zone->frames);
}
 
static inline index_t frame_index_abs(zone_t *zone, frame_t *frame)
{
  return (index_t) (frame - zone->frames);
}
 
static inline int frame_index_valid(zone_t *zone, index_t index)
{
	return (index < zone->count);
}
 
/** Compute pfn_t from frame_t pointer & zone pointer */
static inline index_t make_frame_index(zone_t *zone, frame_t *frame)
{
	return (frame - zone->frames);
}
 
static inline void frame_initialize(frame_t *frame)
{
	frame->refcount = 1;
	frame->buddy_order = 0;
}
 
 
static link_t *buddy_find_block(zone_t *zone, link_t *child,
    u32_t order)
{
	frame_t *frame;
	index_t index;
 
  frame = (frame_t*)child;
 
	index = frame_index(zone, frame);
	do {
		if (zone->frames[index].buddy_order != order) {
			return &zone->frames[index].buddy_link;
		}
	} while(index-- > 0);
	return NULL;
}
 
static inline link_t * buddy_bisect(zone_t *z, link_t *block) {
	frame_t *frame_l, *frame_r;
 
  frame_l = (frame_t*)block;
	frame_r = (frame_l + (1 << (frame_l->buddy_order - 1)));
 
	return &frame_r->buddy_link;
}
 
static inline u32_t buddy_get_order(zone_t *z, link_t *block) {
  frame_t *frame = (frame_t*)block;
	return frame->buddy_order;
}
 
static inline void buddy_set_order(zone_t *z, link_t *block,
    u32_t order) {
  frame_t *frame = (frame_t*)block;
	frame->buddy_order = order;
}
 
static link_t *buddy_coalesce(zone_t *z, link_t *block_1,
    link_t *block_2)
{
	frame_t *frame1, *frame2;
 
  frame1 = (frame_t*)block_1;
  frame2 = (frame_t*)block_2;
 
	return frame1 < frame2 ? block_1 : block_2;
}
 
static inline void buddy_mark_busy(zone_t *z, link_t * block) {
  frame_t * frame = (frame_t*)block;
	frame->refcount = 1;
}
 
static inline void buddy_mark_available(zone_t *z, link_t *block) {
  frame_t *frame = (frame_t*)block;
	frame->refcount = 0;
}
 
#define IS_BUDDY_ORDER_OK(index, order)   \
    ((~(((u32_t) -1) << (order)) & (index)) == 0)
#define IS_BUDDY_LEFT_BLOCK_ABS(zone, frame)  \
  (((frame_index_abs((zone), (frame)) >> (frame)->buddy_order) & 0x1) == 0)
 
#define IS_BUDDY_RIGHT_BLOCK_ABS(zone, frame) \
	(((frame_index_abs((zone), (frame)) >> (frame)->buddy_order) & 0x1) == 1)
 
static link_t *find_buddy(zone_t *zone, link_t *block)
{
	frame_t *frame;
	index_t index;
  u32_t is_left, is_right;
 
  frame = (frame_t*)block;
  ASSERT(IS_BUDDY_ORDER_OK(frame_index_abs(zone, frame),frame->buddy_order));
 
	is_left = IS_BUDDY_LEFT_BLOCK_ABS(zone, frame);
	is_right = IS_BUDDY_RIGHT_BLOCK_ABS(zone, frame);
 
  ASSERT(is_left ^ is_right);
	if (is_left) {
		index = (frame_index(zone, frame)) + (1 << frame->buddy_order);
	} else { 	/* if (is_right) */
		index = (frame_index(zone, frame)) - (1 << frame->buddy_order);
	}
 
	if (frame_index_valid(zone, index)) {
		if (zone->frames[index].buddy_order == frame->buddy_order &&
		    zone->frames[index].refcount == 0) {
			return &zone->frames[index].buddy_link;
		}
	}
 
	return NULL;
}
 
static link_t* __fastcall buddy_system_alloc_block(zone_t *z, link_t *block)
{
	link_t *left,*right, *tmp;
  u32_t order;
 
  left = buddy_find_block(z, block, BUDDY_SYSTEM_INNER_BLOCK);
  ASSERT(left);
	list_remove(left);
	while (1) {
    if (! buddy_get_order(z,left)) {
      buddy_mark_busy(z, left);
			return left;
		}
 
    order = buddy_get_order(z, left);
 
    right = buddy_bisect(z, left);
    buddy_set_order(z, left, order-1);
    buddy_set_order(z, right, order-1);
 
    tmp = buddy_find_block(z, block, BUDDY_SYSTEM_INNER_BLOCK);
 
		if (tmp == right) {
			right = left;
			left = tmp;
		}
    ASSERT(tmp == left);
    buddy_mark_busy(z, left);
    buddy_system_free(z, right);
    buddy_mark_available(z, left);
	}
}
 
static void __fastcall buddy_system_free(zone_t *z, link_t *block)
{
	link_t *buddy, *hlp;
  u8_t i;
 
	/*
	 * Determine block's order.
	 */
  i = buddy_get_order(z, block);
 
  ASSERT(i <= z->max_order);
 
  if (i != z->max_order) {
		/*
		 * See if there is any buddy in the list of order i.
		 */
    buddy = find_buddy(z, block);
		if (buddy) {
 
      ASSERT(buddy_get_order(z, buddy) == i);
			/*
			 * Remove buddy from the list of order i.
			 */
			list_remove(buddy);
 
			/*
			 * Invalidate order of both block and buddy.
			 */
      buddy_set_order(z, block, BUDDY_SYSTEM_INNER_BLOCK);
      buddy_set_order(z, buddy, BUDDY_SYSTEM_INNER_BLOCK);
 
			/*
			 * Coalesce block and buddy into one block.
			 */
      hlp = buddy_coalesce(z, block, buddy);
 
			/*
			 * Set order of the coalesced block to i + 1.
			 */
      buddy_set_order(z, hlp, i + 1);
 
			/*
			 * Recursively add the coalesced block to the list of order i + 1.
			 */
      buddy_system_free(z, hlp);
			return;
		}
	}
 
	/*
	 * Insert block into the list of order i.
	 */
  list_append(block, &z->order[i]);
 
}
 
static inline frame_t * zone_get_frame(zone_t *zone, index_t frame_idx)
{
  ASSERT(frame_idx < zone->count);
	return &zone->frames[frame_idx];
}
 
static void zone_mark_unavailable(zone_t *zone, index_t frame_idx)
{
	frame_t *frame;
	link_t *link;
 
	frame = zone_get_frame(zone, frame_idx);
	if (frame->refcount)
		return;
  link = buddy_system_alloc_block(zone, &frame->buddy_link);
  ASSERT(link);
	zone->free_count--;
}
 
static link_t* __fastcall buddy_system_alloc(zone_t *z, u32_t i)
{
	link_t *res, *hlp;
 
  ASSERT(i <= z->max_order);
 
	/*
	 * If the list of order i is not empty,
	 * the request can be immediatelly satisfied.
	 */
	if (!list_empty(&z->order[i])) {
		res = z->order[i].next;
		list_remove(res);
		buddy_mark_busy(z, res);
		return res;
	}
	/*
	 * If order i is already the maximal order,
	 * the request cannot be satisfied.
	 */
	if (i == z->max_order)
		return NULL;
 
	/*
	 * Try to recursively satisfy the request from higher order lists.
	 */
	hlp = buddy_system_alloc(z, i + 1);
 
	/*
	 * The request could not be satisfied
	 * from higher order lists.
	 */
	if (!hlp)
		return NULL;
 
	res = hlp;
 
	/*
	 * Bisect the block and set order of both of its parts to i.
	 */
	hlp = buddy_bisect(z, res);
	buddy_set_order(z, res, i);
	buddy_set_order(z, hlp, i);
 
	/*
	 * Return the other half to buddy system. Mark the first part
	 * full, so that it won't coalesce again.
	 */
	buddy_mark_busy(z, res);
	buddy_system_free(z, hlp);
 
	return res;
 
}
 
 
static __fastcall pfn_t zone_frame_alloc(zone_t *zone, u32_t order)
{
	pfn_t v;
	link_t *tmp;
	frame_t *frame;
 
 
	/* Allocate frames from zone buddy system */
	tmp = buddy_system_alloc(zone, order);
 
  ASSERT(tmp);
 
	/* Update zone information. */
	zone->free_count -= (1 << order);
	zone->busy_count += (1 << order);
 
	/* Frame will be actually a first frame of the block. */
	frame = (frame_t*)tmp;
 
	/* get frame address */
	v = make_frame_index(zone, frame);
 
	return v;
}
 
 
/** Set parent of frame */
void __fastcall frame_set_parent(pfn_t pfn, void *data)
{
/*  zone_t *zone = find_zone_and_lock(pfn, &hint);
  ASSERT(zone);
 */
 
  spinlock_lock(&z_core.lock);
    zone_get_frame(&z_core, pfn-z_core.base)->parent = data;
  spinlock_unlock(&z_core.lock);
}
 
void* __fastcall frame_get_parent(pfn_t pfn)
{
//	zone_t *zone = find_zone_and_lock(pfn, &hint);
	void *res;
 
  spinlock_lock(&z_core.lock);
    res = zone_get_frame(&z_core, pfn)->parent;
  spinlock_unlock(&z_core.lock);
 
	return res;
}
 
static inline int to_order(count_t arg)
{
  int n;
  asm volatile (
                "xorl %eax, %eax \n\t"
                "bsr %edx, %eax \n\t"
                "incl %eax"
                :"=a" (n)
                :"d"(arg)
                );
	return n;
}
 
 
addr_t __fastcall zone_alloc(zone_t *zone, u32_t order)
{
   eflags_t efl;
   pfn_t v;
 
   efl = safe_cli();
     spinlock_lock(&zone->lock);
       v = zone_frame_alloc(zone, order);
       v += zone->base;
     spinlock_unlock(&zone->lock);
   safe_sti(efl);
 
   return (v << FRAME_WIDTH);
}
 
addr_t  __fastcall core_alloc(u32_t order)        //export
{
   eflags_t efl;
   pfn_t v;
 
   efl = safe_cli();
     spinlock_lock(&z_core.lock);
       v = zone_frame_alloc(&z_core, order);
     spinlock_unlock(&z_core.lock);
   safe_sti(efl);
   DBG("core alloc: %x, size %x\n", v << FRAME_WIDTH, (1<
   return (v << FRAME_WIDTH);
};
 
void __fastcall core_free(addr_t frame)            //export
{
   eflags_t efl;
 
   efl = safe_cli();
     spinlock_lock(&z_core.lock);
       zone_free(&z_core, frame>>12);
     spinlock_unlock(&z_core.lock);
   safe_sti(efl);
}
 
addr_t alloc_page()                                //obsolete
{
   eflags_t efl;
   u32_t    edx;
   pfn_t v;
 
   edx = save_edx();
   efl = safe_cli();
     spinlock_lock(&z_core.lock);
       v = zone_frame_alloc(&z_core, 0);
     spinlock_unlock(&z_core.lock);
   safe_sti(efl);
 
   DBG("alloc_page: %x\n", v << FRAME_WIDTH);
 
   restore_edx(edx);
   return (v << FRAME_WIDTH);
};
 
void __fastcall zone_free(zone_t *zone, pfn_t frame_idx)
{
	frame_t *frame;
  u32_t order;
 
	frame = &zone->frames[frame_idx];
 
	/* remember frame order */
	order = frame->buddy_order;
 
  ASSERT(frame->refcount);
 
	if (!--frame->refcount) {
		buddy_system_free(zone, &frame->buddy_link);
 
		/* Update zone information. */
		zone->free_count += (1 << order);
		zone->busy_count -= (1 << order);
	}
}
 
void frame_free(addr_t frame)           //export
{
   eflags_t efl;
   zone_t *zone;
 
   efl = safe_cli();
     spinlock_lock(&z_core.lock);
       zone_free(&z_core, frame>>12);
     spinlock_unlock(&z_core.lock);
  safe_sti(efl);
}
 
count_t get_free_mem()
{
   return z_core.free_count;
}
>
>
>
>

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

Subversion Repositories Kolibri OS

(root)/kernel/branches/kolibri_pe/core/mm.c – Rev 864 → 886