Context Navigation

source: branches/stable/ARBDB/admalloc.cxx

Visit:

Last change on this file was 18665, checked in by westram, 3 years ago
change many WARN_TODO triggered warnings into todo markers.
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 19.4 KB

Line
1	// =============================================================== //
2	// //
3	// File : admalloc.cxx //
4	// Purpose : //
5	// //
6	// Institute of Microbiology (Technical University Munich) //
7	// http://www.arb-home.de/ //
8	// //
9	// =============================================================== //
10
11	#include <unistd.h>
12	#include <climits>
13	#include <set>
14
15	#include <arb_backtrace.h>
16	#include "gb_storage.h"
17
18	// #define DUMP_MEMBLKS
19	// #define DUMP_MEMBLKS_AT_EXIT
20
21	#ifdef DEBUG
22	// #define TEST_MEMBLKS
23	// #define TRACE_ALLOCS
24
25	// @@@ unit tests fail when TRACE_ALLOCS is defined (due to wrong sized block during load(?). cant fix atm. see [6672])
26	#endif
27
28	#define GBM_MAGIC 0x74732876
29
30	#define GBM_SYSTEM_PAGE_SIZE 4096 // 4k Tables
31	#define GBM_MALLOC_OVERHEAD 32 // pointer for alloc
32	#define GBM_TABLE_SIZE (GBM_SYSTEM_PAGE_SIZE-GBM_MALLOC_OVERHEAD) // usable size of table
33
34	#define GBM_ALIGNED 8
35	#define GBM_LD_ALIGNED 3
36
37	#define GBM_MAX_TABLES 16 // n different sizes -> max = GBM_MAX_TABLES * GBM_ALIGNED
38	#define GBM_MAX_SIZE (GBM_MAX_TABLES*GBM_ALIGNED)
39	#define GBM_MAX_INDEX 256 // has to be 2 ^ x (with x = GBM_MAX_TABLES ? )
40
41
42	struct gbm_data {
43	long magic; // indicates free element
44	gbm_data *next; // next free element
45	};
46
47	struct gbm_table { // a block containing data
48	gbm_table *next;
49	gbm_data data[1];
50	};
51
52	static struct gbm_pool { // one pool for each memory index
53	gbm_data *gds; // free data area
54	size_t size; // free size of current table
55	size_t allsize; // full size of all tables
56	gbm_table *first; // link list of tables
57	gbm_data *tables[GBM_MAX_TABLES+1]; // free entries
58	long tablecnt[GBM_MAX_TABLES+1]; // number of free entries
59	long useditems[GBM_MAX_TABLES+1]; // number of used items (everything)
60	size_t extern_data_size; // not handled by this routine
61	long extern_data_items;
62	} gbm_pool4idx[GBM_MAX_INDEX];
63
64	static struct {
65	char *old_sbrk;
66	} gbm_global;
67
68
69	#define GBB_INCR 11 // memsize increment in percent between adjacent clusters
70	#define GBB_CLUSTERS 64 // # of different clusters
71	#define GBB_ALIGN GBM_LD_ALIGNED // align memsize of clusters (# of bits)
72	#define GBB_MINSIZE GBM_MAX_SIZE // minimal size of allocated big block
73	#define GBB_MAX_TRIALS 4 // maximal number of clusters to search for an unused block
74	#define GBB_MAGIC 0x67823747
75
76	struct gbb_data;
77
78	struct gbb_freedata { // part of gbb_data if it`s a free block
79	// cppcheck-suppress unusedStructMember
80	long magic;
81	gbb_data *next; // next unused memblock
82	};
83
84	struct gbb_data {
85	size_t size; // real size of memblock (from `content` to end of block)
86	long allocFromSystem; // ==0 -> it`s a block imported by gbm_put_mem
87	gbb_freedata content; // startposition of block returned to user or chain info for free blocks
88	};
89
90	#define GBB_HEADER_SIZE (sizeof(gbb_data)-sizeof(gbb_freedata))
91
92	static struct gbb_Cluster {
93	size_t size; // minimum size of memblocks in this cluster
94	gbb_data *first; // first free block
95
96	} gbb_cluster[GBB_CLUSTERS+1];
97
98
99	#ifdef TRACE_ALLOCS
100
101	class AllocLogEntry {
102	void *block;
103	size_t size;
104	long index;
105
106	mutable BackTraceInfo *trace;
107
108	public:
109	AllocLogEntry(void *block_, size_t size_, long index_, bool do_trace) :
110	block(block_),
111	size(size_),
112	index(index_),
113	trace(do_trace ? GBK_get_backtrace(5) : NULp)
114	{ }
115	AllocLogEntry(const AllocLogEntry& other) :
116	block(other.block),
117	size(other.size),
118	index(other.index),
119	trace(other.trace)
120	{
121	other.trace = NULp;
122	}
123	~AllocLogEntry() { if (trace) GBK_free_backtrace(trace); }
124
125	size_t get_size() const { return size; }
126	long get_index() const { return index; }
127
128	bool operator<(const AllocLogEntry& other) const { return block < other.block; }
129	void dump(FILE *out, GB_CSTR message) const { GBK_dump_former_backtrace(trace, out, message); }
130	};
131
132	typedef std::set<AllocLogEntry> AllocLogEntries;
133
134	class AllocLogger {
135	AllocLogEntries entries;
136
137	const AllocLogEntry existingEntry(void block) {
138	AllocLogEntries::const_iterator found = entries.find(AllocLogEntry(block, 0, 0, false));
139
140	return found == entries.end() ? NULp : &*found;
141	}
142
143	public:
144	AllocLogger() {
145	}
146	~AllocLogger() {
147	size_t count = entries.size();
148	if (count) {
149	fprintf(stderr, "%zu non-freed blocks:\n", count);
150	AllocLogEntries::const_iterator end = entries.end();
151	for (AllocLogEntries::const_iterator entry = entries.begin(); entry != end; ++entry) {
152	entry->dump(stderr, "block was allocated from here");
153	}
154	}
155	}
156
157	void allocated(void *block, size_t size, long index) {
158	const AllocLogEntry *exists = existingEntry(block);
159	if (exists) {
160	GBK_dump_backtrace(stderr, "Block allocated again");
161	exists->dump(stderr, "Already allocated from here");
162	}
163	else {
164	entries.insert(AllocLogEntry(block, size, index, true));
165	}
166	}
167	void freed(void *block, size_t size, long index) {
168	const AllocLogEntry *exists = existingEntry(block);
169	if (!exists) {
170	if (!gb_isMappedMemory(block)) {
171	gb_assert(0);
172	// GBK_dump_backtrace(stderr, "Tried to free unallocated block");
173	}
174	}
175	else {
176	gb_assert(exists->get_size() == size);
177	gb_assert(exists->get_index() == index);
178	entries.erase(*exists);
179	}
180	}
181	};
182
183	static AllocLogger allocLogger;
184
185	#endif
186
187	inline void free_gbm_table(gbm_table *table) {
188	while (table) {
189	gbm_table *next = table->next;
190
191	free(table);
192	table = next;
193	}
194	}
195
196	static bool gbm_mem_initialized = false;
197
198	void gbm_flush_mem() {
199	gb_assert(gbm_mem_initialized);
200
201	for (int i = 0; i<GBM_MAX_INDEX; ++i) {
202	gbm_pool& gbm = gbm_pool4idx[i];
203	bool have_used_items = false;
204
205	for (int t = 0; t < GBM_MAX_TABLES; t++) {
206	if (gbm.useditems[t]) {
207	have_used_items = true;
208	break;
209	}
210	}
211
212	if (!have_used_items) {
213	free_gbm_table(gbm.first);
214	memset((char*)&gbm, 0, sizeof(gbm));
215	}
216	}
217	}
218
219	void gbm_init_mem() {
220	if (!gbm_mem_initialized) {
221	for (int i = 0; i<GBM_MAX_INDEX; ++i) {
222	memset((char *)&gbm_pool4idx[i], 0, sizeof(gbm_pool));
223	gbm_pool4idx[i].tables[0] = NULp; // CORE zero get mem
224	}
225	gbm_global.old_sbrk = (char *)sbrk(0);
226
227	/* init GBB:
228	* --------- */
229
230	gbb_cluster[0].size = GBB_MINSIZE;
231	gbb_cluster[0].first = NULp;
232
233	for (int i = 1; i<GBB_CLUSTERS; ++i) {
234	long nextSize = gbb_cluster[i-1].size * (100+GBB_INCR);
235
236	nextSize /= 100;
237	nextSize >>= GBB_ALIGN;
238	nextSize ++;
239	nextSize <<= GBB_ALIGN;
240
241	gbb_cluster[i].size = nextSize;
242	gbb_cluster[i].first = NULp;
243	}
244
245	// last cluster contains ALL bigger blocks
246
247	gbb_cluster[GBB_CLUSTERS].size = INT_MAX;
248	gbb_cluster[GBB_CLUSTERS].first = NULp;
249
250	gbm_mem_initialized = true;
251	}
252	}
253
254	struct ARBDB_memory_manager {
255	ARBDB_memory_manager() {
256	gb_assert(!gbm_mem_initialized); // there may be only one instance!
257	gbm_init_mem();
258	}
259	~ARBDB_memory_manager() {
260	#if defined(DUMP_MEMBLKS_AT_EXIT)
261	printf("memory at exit:\n");
262	gbm_debug_mem();
263	#endif // DUMP_MEMBLKS_AT_EXIT
264	gbm_flush_mem();
265	#if defined(DUMP_MEMBLKS_AT_EXIT)
266	printf("memory at exit (after flush):\n");
267	gbm_debug_mem();
268	#endif // DUMP_MEMBLKS_AT_EXIT
269	}
270	};
271	static ARBDB_memory_manager memman;
272
273	#ifdef TEST_MEMBLKS
274
275	#define TEST() testMemblocks(__FILE__, __LINE__)
276
277	void testMemblocks(const char *file, int line) {
278	int idx;
279
280	for (idx=0; idx<GBB_CLUSTERS; idx++) {
281	struct gbb_Cluster *cl = &(gbb_cluster[idx]);
282	gbb_data *blk = cl->first;
283
284	while (blk) {
285	if (blk->size<cl->size) {
286	fprintf(stderr, "Illegal block (size=%zu) in cluster %i (size=%zu) (%s,%i)\n", blk->size, idx, cl->size, file, line);
287	gb_assert(0);
288	}
289	blk = blk->content.next;
290	}
291	}
292	}
293
294	#else
295	# define TEST()
296	#endif
297
298
299	#if (MEMORY_TEST==0)
300
301	static void imemerr(const char *why) {
302	GB_internal_errorf("Dangerous internal error: '%s'\n"
303	"Inconsistent database: Do not overwrite old files with this database", why);
304	}
305
306	static int getClusterIndex(size_t size) {
307	// searches the index of the lowest cluster for that: size <= cluster->size
308	int l, m, h;
309
310	if (size<GBB_MINSIZE) return 0;
311
312	l = 1;
313	h = GBB_CLUSTERS;
314
315	while (l!=h) {
316	m = (l+h)/2;
317	if (gbb_cluster[m].size < size) l = m+1;
318	else h = m;
319	}
320
321	gb_assert(l<=GBB_CLUSTERS);
322
323	return l;
324	}
325
326	static void gbm_put_memblk(char *memblk, size_t size) {
327	/* gives any memory block (allocated or not)
328	into the responsibility of this module;
329	the block has to be aligned!!! */
330
331	gbb_data *block;
332	int idx;
333
334	TEST();
335
336	#ifdef DUMP_MEMBLKS
337	printf("put %p (%li bytes)\n", memblk, size);
338	#endif
339
340	if (size<(GBB_HEADER_SIZE+GBB_MINSIZE)) {
341	GB_internal_errorf("gmb_put_memblk() called with size below %zu bytes",
342	GBB_HEADER_SIZE+GBB_MINSIZE);
343	return;
344	}
345
346	block = (gbb_data *)memblk;
347	block->size = size-GBB_HEADER_SIZE;
348	block->allocFromSystem = 0;
349
350	idx = getClusterIndex(block->size)-1;
351	if (idx<0) { // (silences warning in NDEBUG mode)
352	gb_assert(0); // should be impossible
353	return;
354	}
355
356	block->content.next = gbb_cluster[idx].first;
357	block->content.magic = GBB_MAGIC;
358	gbb_cluster[idx].first = block;
359
360	gb_assert(idx==GBB_CLUSTERS \|\| block->size>=gbb_cluster[idx].size);
361	TEST();
362	}
363
364	static char *gbm_get_memblk(size_t size) {
365	gbb_data *block = NULp;
366	int trials = GBB_MAX_TRIALS;
367	int idx;
368
369	TEST();
370
371	idx = getClusterIndex(size);
372	gb_assert(gbb_cluster[idx].size>=size);
373
374	while (trials--) { // search a cluster containing a block
375	if ((block = gbb_cluster[idx].first)) break; // found!
376	if (idx==GBB_CLUSTERS) break; // last cluster!
377	idx++;
378	}
379
380	if (!block) { // if no unused block -> allocate from system
381	int allocationSize;
382
383	allocFromSys :
384
385	allocationSize = (idx==GBB_CLUSTERS
386	? (size_t)size
387	: (size_t)(gbb_cluster[idx].size)) + GBB_HEADER_SIZE;
388
389	block = (gbb_data *)ARB_calloc<char>(allocationSize);
390
391	block->size = allocationSize-GBB_HEADER_SIZE;
392	block->allocFromSystem = 1;
393
394	gb_assert(block->size>=size);
395
396	#ifdef DUMP_MEMBLKS
397	printf("allocated %li bytes\n", size);
398	#endif
399	}
400	else {
401	gbb_data **blockPtr = &(gbb_cluster[idx].first);
402
403	if (idx==GBB_CLUSTERS) { // last cluster (test for block size necessary)
404	while ((block=*blockPtr) && block->size<size)
405	blockPtr = &(block->content.next);
406
407	if (!block) goto allocFromSys;
408	gb_assert(block->size>=size);
409	}
410
411	if (block->content.magic!=GBB_MAGIC) { imemerr("bad magic number if free block"); return NULp; }
412	*blockPtr = block->content.next;
413	memset((char*)&(block->content), 0, size); // act like calloc
414
415	#ifdef DUMP_MEMBLKS
416	printf("using unused block "
417	"(add=%p,size=%li, block->size=%li,cluster->size=%li)\n",
418	block, size, block->size, gbb_cluster[idx].size);
419	#endif
420
421	gb_assert(block->size>=size);
422	}
423
424	gb_assert(block->size>=size);
425
426	TEST();
427
428	return (char*)&(block->content);
429	}
430
431	void *gbmGetMemImpl(size_t size, long index) {
432	if (size < sizeof(gbm_data)) size = sizeof(gbm_data);
433	index &= GBM_MAX_INDEX-1;
434
435	gbm_pool *ggi = &gbm_pool4idx[index];
436	unsigned long nsize = (size + (GBM_ALIGNED - 1)) & (-GBM_ALIGNED);
437
438	char *result;
439	if (nsize > GBM_MAX_SIZE) {
440	ggi->extern_data_size += nsize;
441	ggi->extern_data_items++;
442
443	result = gbm_get_memblk((size_t)nsize);
444	}
445	else {
446	unsigned long pos = nsize >> GBM_LD_ALIGNED;
447	gbm_data *gds = ggi->tables[pos];
448	if (gds) {
449	ggi->tablecnt[pos]--;
450	result = (char *)gds;
451	if (gds->magic != GBM_MAGIC) {
452	printf("%lX!= %lX\n", gds->magic, (long)GBM_MAGIC);
453	GB_internal_error("Dangerous internal error: Inconsistent database: "
454	"Do not overwrite old files with this database");
455	}
456	ggi->tables[pos] = ggi->tables[pos]->next;
457	}
458	else {
459	if (ggi->size < nsize) {
460	gbm_table *gts;
461	arb_mem::alloc_aligned((void**)(&gts), GBM_SYSTEM_PAGE_SIZE, GBM_TABLE_SIZE);
462
463	memset((char *)gts, 0, GBM_TABLE_SIZE);
464	ggi->gds = &gts->data[0];
465	gts->next = ggi->first; // link tables
466	ggi->first = gts;
467	ggi->size = GBM_TABLE_SIZE - sizeof(void *);
468	ggi->allsize += GBM_TABLE_SIZE;
469	}
470	result = (char *)ggi->gds;
471	ggi->gds = (gbm_data )(((char )ggi->gds) + nsize);
472	ggi->size -= (size_t)nsize;
473	}
474
475	ggi->useditems[pos]++;
476	memset(result, 0, nsize); // act like calloc()
477	}
478
479	#ifdef TRACE_ALLOCS
480	allocLogger.allocated(erg, size, index);
481	#endif
482	return result;
483	}
484
485	void gbmFreeMemImpl(void *data, size_t size, long index) {
486	if (size < sizeof(gbm_data)) size = sizeof(gbm_data);
487	index &= GBM_MAX_INDEX-1;
488
489	gbm_pool *ggi = &gbm_pool4idx[index];
490	long nsize = (size + (GBM_ALIGNED - 1)) & (-GBM_ALIGNED);
491
492	#ifdef TRACE_ALLOCS
493	allocLogger.freed(data, size, index);
494	#endif
495
496	if (nsize > GBM_MAX_SIZE) {
497	gbb_data *block;
498
499	if (gb_isMappedMemory(data)) {
500	block = (gbb_data *)data;
501
502	block->size = size-GBB_HEADER_SIZE;
503	block->allocFromSystem = 0;
504
505	if (size>=(GBB_HEADER_SIZE+GBB_MINSIZE)) {
506	gbm_put_memblk((char*)block, size);
507	}
508	}
509	else {
510	block = (gbb_data )((char)data-GBB_HEADER_SIZE);
511
512	ggi->extern_data_size -= (size_t)nsize;
513	ggi->extern_data_items--;
514
515	if (block->size<size) { imemerr("block size does not match"); return; }
516
517	if (block->allocFromSystem) {
518	free(block);
519	}
520	else {
521	/* printf("put unused block (size=%li block->size=%li)\n",
522	size,block->size); */
523	gbm_put_memblk((char*)block, block->size + GBB_HEADER_SIZE);
524	}
525	}
526	}
527	else {
528	if (gb_isMappedMemory(data)) return; // @@@ reason: size may be shorter
529
530	gbm_data gdata = (gbm_data)data;
531
532	if (gdata->magic == GBM_MAGIC) {
533	imemerr("double free");
534	return;
535	}
536
537	long pos = nsize >> GBM_LD_ALIGNED;
538
539	gdata->next = ggi->tables[pos];
540	gdata->magic = GBM_MAGIC;
541	ggi->tables[pos] = gdata;
542	ggi->tablecnt[pos]++;
543	ggi->useditems[pos]--;
544	}
545	}
546
547	#endif // MEMORY_TEST==0
548
549	void gbm_debug_mem() {
550	int i;
551	int index;
552	long total = 0;
553	long index_total;
554	gbm_pool *ggi;
555
556	printf("Memory Debug Information:\n");
557	for (index = 0; index < GBM_MAX_INDEX; index++) {
558	index_total = 0;
559	ggi = &gbm_pool4idx[index];
560	for (i = 0; i < GBM_MAX_TABLES; i++) {
561	index_total += i * GBM_ALIGNED * (int) ggi->useditems[i];
562	total += i * GBM_ALIGNED * (int) ggi->useditems[i];
563
564	if (ggi->useditems[i] \|\| ggi->tablecnt[i]) {
565	printf("\t'I=%3i' 'Size=%3i' * 'Items %4i' = 'size %7i' 'sum=%7li' 'totalsum=%7li' : Free %3i\n",
566	index,
567	i * GBM_ALIGNED,
568	(int) ggi->useditems[i],
569	i * GBM_ALIGNED * (int) ggi->useditems[i],
570	index_total,
571	total,
572	(int) ggi->tablecnt[i]);
573	}
574	}
575	if (ggi->extern_data_size) {
576	index_total += ggi->extern_data_size;
577	total += ggi->extern_data_size;
578	printf("\t'I=%3i' External Data Items=%3li = Sum=%3li 'sum=%7li' 'total=%7li\n",
579	index,
580	ggi->extern_data_items,
581	(long)ggi->extern_data_size,
582	index_total,
583	total);
584	}
585	}
586
587	{
588	char topofmem = (char )sbrk(0);
589	printf("spbrk %lx old %lx size %ti\n",
590	(long)topofmem,
591	(long)gbm_global.old_sbrk,
592	topofmem-gbm_global.old_sbrk);
593	}
594	}
595
596	// --------------------------------------------------------------------------------
597
598	#if defined(UNIT_TESTS) && 0
599
600	#include <test_unit.h>
601
602	void TEST_ARBDB_memory() { // not a real unit test - just was used for debugging
603	#define ALLOCS 69
604	long *blocks[ALLOCS];
605
606	#if (MEMORY_TEST == 0)
607	printf("Before allocations:\n");
608	gbm_debug_mem();
609
610	#if 1
611	static int16_t non_alloc[75]; // 150 byte
612	gbm_put_memblk((char*)non_alloc, sizeof(non_alloc));
613
614	printf("Added one non-allocated block:\n");
615	gbm_debug_mem();
616	#endif
617	#endif
618
619	for (int pass = 1; pass <= 2; ++pass) {
620	long allocs = 0;
621
622	for (size_t size = 10; size<5000; size += size/3) {
623	for (long index = 0; index<3; ++index) {
624	if (pass == 1) {
625	long block = (long)gbm_get_mem(size, index);
626
627	block[0] = size;
628	block[1] = index;
629
630	blocks[allocs++] = block;
631	}
632	else {
633	long *block = blocks[allocs++];
634	gbm_free_mem(block, (size_t)block[0], block[1]);
635	}
636	}
637	}
638
639	#if (MEMORY_TEST == 0)
640	if (pass == 1) {
641	printf("%li memory blocks allocated:\n", allocs);
642	gbm_debug_mem();
643	}
644	else {
645	printf("Memory freed:\n");
646	gbm_debug_mem();
647	}
648	printf("Memory flushed:\n");
649	gbm_flush_mem();
650	gbm_debug_mem();
651	#endif
652
653	gb_assert(allocs == ALLOCS);
654	}
655
656	GBK_dump_backtrace(stderr, "test");
657	}
658
659
660	#endif // UNIT_TESTS

Note: See TracBrowser for help on using the repository browser.

Download in other formats: