WebSVN – Kolibri OS – Blame – /kernel/branches/kolibri_pe/core/heap.c

Rev	Author	Line No.	Line
859	serge	1
		2	#include
		3	#include
		4	#include
		5	#include
		6	#include
		7
		8
888	serge	9
		10
859	serge	11
889	serge	12	#define MD_USED 2
		13
886	serge	14
859	serge	15	u32_t av_mapped;
888	serge	16	u32_t av_unmapped;
		17
859	serge	18
888	serge	19	link_t unmapped[32];
		20
886	serge	21
		22
888	serge	23
		24	}heap_t;
859	serge	25
		26
886	serge	27
859	serge	28	slab_cache_t *phm_slab;
		29
		30
		31
886	serge	32	heap_t sheap;
		33
		34
		35
888	serge	36	{ asm volatile ("bts %0, _lheap+4"::"r"(idx):"cc"); }
		37
886	serge	38
888	serge	39	{ asm volatile ("btr %0, _lheap+4"::"r"(idx):"cc"); }
		40
859	serge	41
888	serge	42	{ asm volatile ("bts %0, _sheap"::"r"(idx):"cc"); }
886	serge	43
859	serge	44
888	serge	45	{ asm volatile ("btr %0, _sheap"::"r"(idx):"cc"); }
886	serge	46
859	serge	47
888	serge	48	{ asm volatile ("bts %0, _sheap+4"::"r"(idx):"cc"); }
		49
859	serge	50
888	serge	51	{ asm volatile ("btr %0, _sheap+4"::"r"(idx):"cc"); }
		52
		53
		54
859	serge	55	{
		56	md_t *md;
889	serge	57	u32_t i;
		58
859	serge	59
889	serge	60	ASSERT(size != 0)
		61	ASSERT((base & 0x3FFFFF) == 0);
		62	ASSERT((size & 0x3FFFFF) == 0);
		63
859	serge	64
889	serge	65	{
		66	list_initialize(&lheap.mapped[i]);
888	serge	67	list_initialize(&lheap.unmapped[i]);
		68
		69
		70	list_initialize(&sheap.unmapped[i]);
		71	};
889	serge	72
859	serge	73
889	serge	74	list_initialize(&sheap.used);
		75
886	serge	76
889	serge	77
886	serge	78
889	serge	79
859	serge	80
889	serge	81	md->base = base;
		82	md->size = size;
		83	md->parent = NULL;
		84	md->state = MD_FREE;
		85
859	serge	86
888	serge	87	lheap.av_mapped = 0x00000000;
		88	lheap.av_unmapped = 0x80000000;
		89	sheap.av_mapped = 0x00000000;
		90	sheap.av_unmapped = 0x00000000;
		91
859	serge	92
889	serge	93	};
859	serge	94
		95
		96	{
		97	md_t *md = NULL;
889	serge	98
859	serge	99
889	serge	100	u32_t mask;
		101
859	serge	102
889	serge	103
859	serge	104
889	serge	105	mask = lheap.av_unmapped & ( -1<
888	serge	106
859	serge	107
889	serge	108	{
		109	if(idx0 == 31)
		110	{
		111	md_t tmp = (md_t)lheap.unmapped[31].next;
888	serge	112	while((link_t*)tmp != &lheap.unmapped[31])
		113	{
889	serge	114	if(tmp->size >= size)
		115	{
		116	DBG("remove large tmp %x\n", tmp);
		117
		118
		119	break;
		120	};
		121	};
		122	tmp = (md_t*)tmp->link.next;
		123	}
		124	else
		125	{
862	serge	126	idx0 = _bsf(mask);
889	serge	127
859	serge	128
888	serge	129
862	serge	130
888	serge	131	};
889	serge	132	}
		133	else
		134	return NULL;
		135
859	serge	136
889	serge	137
886	serge	138
889	serge	139	if(list_empty(&lheap.unmapped[idx0]))
888	serge	140	_reset_lavu(idx0);
		141
859	serge	142
889	serge	143	{
		144	count_t idx1;
		145	md_t new_md = (md_t)slab_alloc(md_slab,0); /* FIXME check */
		146
859	serge	147
889	serge	148	list_insert(&new_md->adj, &md->adj);
		149
859	serge	150
889	serge	151	new_md->size = size;
		152	new_md->parent = NULL;
888	serge	153	new_md->state = MD_USED;
889	serge	154
859	serge	155
889	serge	156	md->size-= size;
		157
859	serge	158
889	serge	159
859	serge	160
888	serge	161	_set_lavu(idx1);
		162
859	serge	163
889	serge	164	};
		165	md->state = MD_USED;
		166
886	serge	167
889	serge	168	}
859	serge	169
		170
888	serge	171	{
859	serge	172	eflags_t efl;
886	serge	173
859	serge	174
886	serge	175
859	serge	176
886	serge	177	u32_t mask;
		178
859	serge	179
886	serge	180
859	serge	181
886	serge	182
859	serge	183
886	serge	184	mask = sheap.av_unmapped & ( -1<
888	serge	185
859	serge	186
888	serge	187
861	serge	188
886	serge	189	{
		190	if(idx0 == 31)
		191	{
862	serge	192	ASSERT( !list_empty(&sheap.unmapped[31]));
888	serge	193
886	serge	194
888	serge	195	while((link_t*)tmp != &sheap.unmapped[31])
		196	{
886	serge	197	if(tmp->size >= size)
		198	{
		199	md = tmp;
		200	break;
		201	};
		202	tmp = (md_t*)tmp->link.next;
		203	};
		204	}
		205	else
		206	{
		207	idx0 = _bsf(mask);
		208
		209
888	serge	210
886	serge	211
888	serge	212	}
886	serge	213	};
		214
		215
		216	{
		217	DBG("remove md %x\n", md);
		218
		219
		220	ASSERT(md->parent != NULL);
888	serge	221
886	serge	222
		223	if(list_empty(&sheap.unmapped[idx0]))
888	serge	224	_reset_savu(idx0);
		225	}
886	serge	226	else
		227	{
		228	md_t *lmd;
		229	lmd = find_large_md((size+0x3FFFFF)&~0x3FFFFF);
		230
		231
		232
		233
		234	{
		235	safe_sti(efl);
		236	return NULL;
		237	};
862	serge	238
861	serge	239
888	serge	240	ASSERT(lmd->base != 0);
		241	ASSERT((lmd->base & 0x3FFFFF) == 0);
		242	ASSERT(lmd->parent == NULL);
		243
		244
886	serge	245
862	serge	246
886	serge	247	list_initialize(&md->adj);
		248	md->base = lmd->base;
		249	md->size = lmd->size;
		250	md->parent = lmd;
		251	md->state = MD_USED;
		252	};
		253
862	serge	254
886	serge	255	{
		256	count_t idx1;
		257	md_t new_md = (md_t)slab_alloc(md_slab,0); /* FIXME check */
		258
862	serge	259
886	serge	260	list_insert(&new_md->adj, &md->adj);
		261
859	serge	262
886	serge	263	new_md->size = size;
		264	new_md->parent = md->parent;
		265	new_md->state = MD_USED;
		266
859	serge	267
886	serge	268	md->size-= size;
		269	md->state = MD_FREE;
		270
859	serge	271
886	serge	272
859	serge	273
886	serge	274
859	serge	275
886	serge	276	list_prepend(&md->link, &sheap.unmapped[idx1]);
888	serge	277	else
886	serge	278	{
		279	if( list_empty(&sheap.unmapped[31]))
888	serge	280	list_prepend(&md->link, &sheap.unmapped[31]);
		281	else
886	serge	282	{
		283	md_t tmp = (md_t)sheap.unmapped[31].next;
888	serge	284
859	serge	285
888	serge	286	{
886	serge	287	if(md->base < tmp->base)
		288	break;
		289	tmp = (md_t*)tmp->link.next;
		290	}
		291	list_insert(&md->link, &tmp->link);
		292	};
		293	};
		294
859	serge	295
888	serge	296
861	serge	297
886	serge	298
861	serge	299
886	serge	300	};
		301
861	serge	302
886	serge	303
859	serge	304
886	serge	305
859	serge	306
886	serge	307	}
859	serge	308
		309
888	serge	310	{
886	serge	311	eflags_t efl;
888	serge	312
		313
		314
		315
		316	u32_t mask;
		317
		318
		319
		320
		321
		322
		323	mask = sheap.av_mapped & ( -1<
		324
		325
		326	idx0, mask);
		327
		328
		329	{
		330	if(idx0 == 31)
		331	{
		332	ASSERT( !list_empty(&sheap.mapped[31]));
		333
		334
		335	while((link_t*)tmp != &sheap.mapped[31])
		336	{
		337	if(tmp->size >= size)
		338	{
		339	md = tmp;
		340	break;
		341	};
		342	tmp = (md_t*)tmp->link.next;
		343	};
		344	}
		345	else
		346	{
		347	idx0 = _bsf(mask);
		348
		349
		350
		351
		352	}
		353	};
		354
		355
		356	{
		357	DBG("remove md %x\n", md);
		358
		359
		360
		361
		362	if(list_empty(&sheap.mapped[idx0]))
		363	_reset_savm(idx0);
		364	}
		365	else
		366	{
		367	md_t *lmd;
		368	addr_t frame;
		369	addr_t *pte;
		370	int i;
		371
		372
		373
		374
		375
		376
		377	{
		378	safe_sti(efl);
		379	return NULL;
		380	};
		381
		382
		383	ASSERT(lmd->base != 0);
		384	ASSERT((lmd->base & 0x3FFFFF) == 0);
		385	ASSERT(lmd->parent == NULL);
		386
		387
		388
		389
		390
		391
		392
		393
		394	{
		395	*pte++ = frame;
		396	frame+= 4096;
		397	}
		398
		399
		400
		401
		402	list_initialize(&md->adj);
		403	md->base = lmd->base;
		404	md->size = lmd->size;
		405	md->parent = lmd;
		406	md->state = MD_USED;
		407	};
		408
		409
		410	{
		411	count_t idx1;
		412	md_t new_md = (md_t)slab_alloc(md_slab,0); /* FIXME check */
		413
		414
		415	list_insert(&new_md->adj, &md->adj);
		416
		417
		418	new_md->size = size;
		419	new_md->parent = md->parent;
		420
		421
		422	md->size-= size;
		423	md->state = MD_FREE;
		424
		425
		426
		427
		428
		429
		430	list_prepend(&md->link, &sheap.mapped[idx1]);
		431	else
		432	{
		433	if( list_empty(&sheap.mapped[31]))
		434	list_prepend(&md->link, &sheap.mapped[31]);
		435	else
		436	{
		437	md_t tmp = (md_t)sheap.mapped[31].next;
		438
		439
		440	{
		441	if(md->base < tmp->base)
		442	break;
		443	tmp = (md_t*)tmp->link.next;
		444	}
		445	list_insert(&md->link, &tmp->link);
		446	};
		447	};
		448
		449
		450
		451
		452	};
		453
		454
		455
		456
		457
		458
		459	}
		460
		461
		462	{
		463	eflags_t efl ;
886	serge	464	md_t *fd;
		465	md_t *bk;
		466	count_t idx;
		467
		468
888	serge	469
		470
886	serge	471	spinlock_lock(&sheap.lock);
		472
		473
		474	{
		475	bk = (md_t*)md->adj.prev;
		476	fd = (md_t*)md->adj.next;
		477
		478
		479	{
		480	idx = (fd->size>>12) - 1 < 32 ? (fd->size>>12) - 1 : 31;
		481
		482
		483	if(list_empty(&sheap.unmapped[idx]))
888	serge	484	_reset_savu(idx);
		485
886	serge	486
		487	md->adj.next = fd->adj.next;
		488	md->adj.next->prev = (link_t*)md;
		489	slab_free(md_slab, fd);
		490	};
		491	if(bk->state == MD_FREE)
		492	{
		493	idx = (bk->size>>12) - 1 < 32 ? (bk->size>>12) - 1 : 31;
		494
		495
		496	if(list_empty(&sheap.unmapped[idx]))
888	serge	497	_reset_savu(idx);
		498
886	serge	499
		500	bk->adj.next = md->adj.next;
		501	bk->adj.next->prev = (link_t*)bk;
		502	slab_free(md_slab, md);
		503	md = fd;
		504	};
		505	};
		506
		507
		508
		509
		510
		511
888	serge	512
886	serge	513
		514	list_prepend(&md->link, &sheap.unmapped[idx]);
888	serge	515	else
886	serge	516	{
		517	if( list_empty(&sheap.unmapped[31]))
888	serge	518	list_prepend(&md->link, &sheap.unmapped[31]);
		519	else
886	serge	520	{
		521	md_t tmp = (md_t)sheap.unmapped[31].next;
888	serge	522
886	serge	523
888	serge	524	{
886	serge	525	if(md->base < tmp->base)
		526	break;
		527	tmp = (md_t*)tmp->link.next;
		528	}
		529	list_insert(&md->link, &tmp->link);
		530	};
		531	};
		532	spinlock_unlock(&sheap.lock);
		533	safe_sti(efl);
		534
		535
		536
		537
888	serge	538	{
		539	eflags_t efl ;
		540	md_t *fd;
		541	md_t *bk;
		542	count_t idx;
		543
886	serge	544
888	serge	545	ASSERT( ((md_t*)(md->parent))->parent != NULL);
		546
886	serge	547
888	serge	548	spinlock_lock(&sheap.lock);
		549
859	serge	550
888	serge	551	{
		552	bk = (md_t*)md->adj.prev;
		553	fd = (md_t*)md->adj.next;
		554
		555
		556	{
889	serge	557	idx = (fd->size>>12) - 1 < 32 ? (fd->size>>12) - 1 : 31;
888	serge	558
859	serge	559
888	serge	560	if(list_empty(&sheap.mapped[idx]))
		561	_reset_savm(idx);
		562
859	serge	563
888	serge	564	md->adj.next = fd->adj.next;
		565	md->adj.next->prev = (link_t*)md;
		566	slab_free(md_slab, fd);
		567	};
		568	if(bk->state == MD_FREE)
		569	{
		570	idx = (bk->size>>12) - 1 < 32 ? (bk->size>>12) - 1 : 31;
		571
859	serge	572
888	serge	573	if(list_empty(&sheap.mapped[idx]))
		574	_reset_savm(idx);
		575
		576
		577	bk->adj.next = md->adj.next;
		578	bk->adj.next->prev = (link_t*)bk;
		579	slab_free(md_slab, md);
		580	md = fd;
		581	};
		582	};
889	serge	583
859	serge	584
888	serge	585
859	serge	586
888	serge	587
859	serge	588
888	serge	589
859	serge	590
888	serge	591	list_prepend(&md->link, &sheap.mapped[idx]);
		592	else
		593	{
		594	if( list_empty(&sheap.mapped[31]))
		595	list_prepend(&md->link, &sheap.mapped[31]);
		596	else
		597	{
889	serge	598	md_t tmp = (md_t)sheap.mapped[31].next;
888	serge	599
859	serge	600
888	serge	601	{
889	serge	602	if(md->base < tmp->base)
888	serge	603	break;
		604	tmp = (md_t*)tmp->link.next;
		605	}
889	serge	606	list_insert(&md->link, &tmp->link);
888	serge	607	};
		608	};
		609	spinlock_unlock(&sheap.lock);
		610	safe_sti(efl);
		611	};
859	serge	612
		613
888	serge	614
889	serge	615	{
859	serge	616	eflags_t efl;
886	serge	617
859	serge	618
886	serge	619
859	serge	620
886	serge	621
		622
888	serge	623	{
886	serge	624	md = find_mapped_md(size);
888	serge	625
886	serge	626
888	serge	627	return NULL;
		628
886	serge	629
889	serge	630	ASSERT(md->parent != NULL);
		631
		632
888	serge	633
886	serge	634
888	serge	635	ASSERT( lmd->parent != NULL);
		636
886	serge	637
888	serge	638	(flags & 0xFFF);
		639	DBG("frame %x\n", frame);
		640	ASSERT(frame != 0);
		641
886	serge	642
888	serge	643	addr_t pte = &((addr_t)page_tabs)[md->base>>12];
		644
		645
		646	{
889	serge	647	*pte++ = frame;
		648	frame+= 4096;
		649	};
		650	}
888	serge	651	else
		652	{
889	serge	653	md = find_unmapped_md(size);
888	serge	654	if( !md )
889	serge	655	return NULL;
		656
886	serge	657
889	serge	658	ASSERT(md->state == MD_USED);
		659	}
		660
		661
		662	};
		663
		664
		665
		666	{
		667	eflags_t efl;
		668
		669
		670
		671
		672
		673
		674
		675
		676
		677
888	serge	678	return NULL;
		679
		680
889	serge	681	spinlock_lock(&sheap.lock);
		682
888	serge	683
889	serge	684	list_prepend(&md->link, &sheap.used);
		685	else
		686	{
		687	md_t tmp = (md_t)sheap.used.next;
		688
888	serge	689
889	serge	690	{
886	serge	691	if(md->base < tmp->base)
889	serge	692	break;
		693	tmp = (md_t*)tmp->link.next;
		694	}
		695	list_insert(&md->link, &tmp->link);
		696	};
		697
886	serge	698
889	serge	699	safe_sti(efl);
		700
886	serge	701
889	serge	702	return (void*)md->base;
		703	};
859	serge	704
		705
886	serge	706	{
859	serge	707	eflags_t efl;
886	serge	708
859	serge	709
886	serge	710	md_t *md = NULL;
		711
859	serge	712
886	serge	713
861	serge	714
886	serge	715	ASSERT( ((addr_t)mem & 0xFFF) == 0 );
		716	ASSERT( ! list_empty(&sheap.used));
		717
862	serge	718
886	serge	719
864	serge	720
886	serge	721
864	serge	722
886	serge	723	{
		724	if( tmp->base == (addr_t)mem )
		725	{
		726	md = tmp;
		727	break;
		728	};
		729	tmp = (md_t*)tmp->link.next;
		730	}
		731
864	serge	732
886	serge	733	{
		734	md_t *lmd;
888	serge	735
		736
886	serge	737
859	serge	738
886	serge	739
864	serge	740
888	serge	741
		742
		743
		744
		745
		746
		747	{
		748	count_t tmp = md->size >> 12;
889	serge	749	addr_t pte = &((addr_t)page_tabs)[md->base>>12];
		750
886	serge	751
889	serge	752	{
		753	*pte++ = 0;
		754	asm volatile (
		755	"invlpg (%0)"
		756	::"r" (mem) );
888	serge	757	mem+= 4096;
889	serge	758	};
		759
888	serge	760
		761	}
		762	else
		763	free_unmapped_md( md );
		764	}
886	serge	765	else
		766	DBG("\tERROR: invalid base address: %x\n", mem);
		767
		768
		769	};
		770

Subversion Repositories Kolibri OS

(root)/kernel/branches/kolibri_pe/core/heap.c – Rev 889