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

Subversion Repositories Kolibri OS

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