?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
update credits
[LibreOffice.git] / sal / rtl / alloc_arena.cxx
blob329d013dfafbe5903ea1bdf799908327c670d0dc
1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*
3 * This file is part of the LibreOffice project.
4 *
5 * This Source Code Form is subject to the terms of the Mozilla Public
6 * License, v. 2.0. If a copy of the MPL was not distributed with this
7 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 *
9 * This file incorporates work covered by the following license notice:
10 *
11 * Licensed to the Apache Software Foundation (ASF) under one or more
12 * contributor license agreements. See the NOTICE file distributed
13 * with this work for additional information regarding copyright
14 * ownership. The ASF licenses this file to you under the Apache
15 * License, Version 2.0 (the "License"); you may not use this file
16 * except in compliance with the License. You may obtain a copy of
17 * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18 */
19
20 #include "alloc_arena.hxx"
21
22 #include "alloc_impl.hxx"
23 #include "internal/rtllifecycle.h"
24 #include "sal/macros.h"
25 #include "osl/diagnose.h"
26
27 #include <cassert>
28 #include <string.h>
29 #include <stdio.h>
30
31 /* ================================================================= *
32 *
33 * arena internals.
34 *
35 * ================================================================= */
36
37 /** g_arena_list
38 * @internal
39 */
40 struct rtl_arena_list_st
41 {
42 rtl_memory_lock_type m_lock;
43 rtl_arena_type m_arena_head;
44 };
45
46 static rtl_arena_list_st g_arena_list;
47
48 /** gp_arena_arena
49 * provided for arena_type allocations, and hash_table resizing.
50 *
51 * @internal
52 */
53 static rtl_arena_type * gp_arena_arena = 0;
54
55 /** gp_machdep_arena
56 *
57 * Low level virtual memory (pseudo) arena
58 * (platform dependent implementation)
59 *
60 * @internal
61 */
62 static rtl_arena_type * gp_machdep_arena = 0;
63
64 /** gp_default_arena
65 */
66 rtl_arena_type * gp_default_arena = 0;
67
68 namespace
69 {
70
71 void *
72 SAL_CALL rtl_machdep_alloc (
73 rtl_arena_type * pArena,
74 sal_Size * pSize
75 );
76
77 void
78 SAL_CALL rtl_machdep_free (
79 rtl_arena_type * pArena,
80 void * pAddr,
81 sal_Size nSize
82 );
83
84 sal_Size
85 rtl_machdep_pagesize();
86
87 /* ================================================================= */
88
89 /** rtl_arena_segment_constructor()
90 */
91 int
92 rtl_arena_segment_constructor (void * obj)
93 {
94 rtl_arena_segment_type * segment = static_cast<rtl_arena_segment_type*>(obj);
95
96 QUEUE_START_NAMED(segment, s);
97 QUEUE_START_NAMED(segment, f);
98
99 return 1;
100 }
101
102 /** rtl_arena_segment_destructor()
103 */
104 void
105 rtl_arena_segment_destructor (void * obj)
106 {
107 rtl_arena_segment_type * segment = static_cast< rtl_arena_segment_type * >(
108 obj);
109 assert(QUEUE_STARTED_NAMED(segment, s));
110 assert(QUEUE_STARTED_NAMED(segment, f));
111 (void) segment; // avoid warnings
112 }
113
114 /* ================================================================= */
115
116 /** rtl_arena_segment_populate()
117 *
118 * @precond arena->m_lock acquired.
119 */
120 bool
121 rtl_arena_segment_populate (
122 rtl_arena_type * arena
123 )
124 {
125 rtl_arena_segment_type *span;
126 sal_Size size = rtl_machdep_pagesize();
127
128 span = static_cast< rtl_arena_segment_type * >(
129 rtl_machdep_alloc(gp_machdep_arena, &size));
130 if (span != 0)
131 {
132 rtl_arena_segment_type *first, *last, *head;
133 sal_Size count = size / sizeof(rtl_arena_segment_type);
134
135 /* insert onto reserve span list */
136 QUEUE_INSERT_TAIL_NAMED(&(arena->m_segment_reserve_span_head), span, s);
137 QUEUE_START_NAMED(span, f);
138 span->m_addr = reinterpret_cast<sal_uIntPtr>(span);
139 span->m_size = size;
140 span->m_type = RTL_ARENA_SEGMENT_TYPE_SPAN;
141
142 /* insert onto reserve list */
143 head = &(arena->m_segment_reserve_head);
144 for (first = span + 1, last = span + count; first < last; ++first)
145 {
146 QUEUE_INSERT_TAIL_NAMED(head, first, s);
147 QUEUE_START_NAMED(first, f);
148 first->m_addr = 0;
149 first->m_size = 0;
150 first->m_type = 0;
151 }
152 }
153 return (span != 0);
154 }
155
156 /** rtl_arena_segment_get()
157 *
158 * @precond arena->m_lock acquired.
159 * @precond (*ppSegment == 0)
160 */
161 inline void
162 rtl_arena_segment_get (
163 rtl_arena_type * arena,
164 rtl_arena_segment_type ** ppSegment
165 )
166 {
167 rtl_arena_segment_type * head;
168
169 assert(*ppSegment == 0);
170
171 head = &(arena->m_segment_reserve_head);
172 if ((head->m_snext != head) || rtl_arena_segment_populate (arena))
173 {
174 (*ppSegment) = head->m_snext;
175 QUEUE_REMOVE_NAMED((*ppSegment), s);
176 }
177 }
178
179 /** rtl_arena_segment_put()
180 *
181 * @precond arena->m_lock acquired.
182 * @postcond (*ppSegment == 0)
183 */
184 inline void
185 rtl_arena_segment_put (
186 rtl_arena_type * arena,
187 rtl_arena_segment_type ** ppSegment
188 )
189 {
190 rtl_arena_segment_type * head;
191
192 assert(QUEUE_STARTED_NAMED((*ppSegment), s));
193 assert(QUEUE_STARTED_NAMED((*ppSegment), f));
194
195 (*ppSegment)->m_addr = 0;
196 (*ppSegment)->m_size = 0;
197
198 assert((*ppSegment)->m_type != RTL_ARENA_SEGMENT_TYPE_HEAD);
199 (*ppSegment)->m_type = 0;
200
201 /* keep as reserve */
202 head = &(arena->m_segment_reserve_head);
203 QUEUE_INSERT_HEAD_NAMED(head, (*ppSegment), s);
204
205 /* clear */
206 (*ppSegment) = 0;
207 }
208
209 /** rtl_arena_freelist_insert()
210 *
211 * @precond arena->m_lock acquired.
212 */
213 inline void
214 rtl_arena_freelist_insert (
215 rtl_arena_type * arena,
216 rtl_arena_segment_type * segment
217 )
218 {
219 rtl_arena_segment_type * head;
220
221 head = &(arena->m_freelist_head[highbit(segment->m_size) - 1]);
222 QUEUE_INSERT_TAIL_NAMED(head, segment, f);
223
224 arena->m_freelist_bitmap |= head->m_size;
225 }
226
227 /** rtl_arena_freelist_remove()
228 *
229 * @precond arena->m_lock acquired.
230 */
231 inline void
232 rtl_arena_freelist_remove (
233 rtl_arena_type * arena,
234 rtl_arena_segment_type * segment
235 )
236 {
237 if ((segment->m_fnext->m_type == RTL_ARENA_SEGMENT_TYPE_HEAD) &&
238 (segment->m_fprev->m_type == RTL_ARENA_SEGMENT_TYPE_HEAD) )
239 {
240 rtl_arena_segment_type * head;
241
242 head = segment->m_fprev;
243 assert(arena->m_freelist_bitmap & head->m_size);
244 arena->m_freelist_bitmap ^= head->m_size;
245 }
246 QUEUE_REMOVE_NAMED(segment, f);
247 }
248
249 /* ================================================================= */
250
251 /** RTL_ARENA_HASH_INDEX()
252 */
253 #define RTL_ARENA_HASH_INDEX_IMPL(a, s, q, m) \
254 ((((a) + ((a) >> (s)) + ((a) >> ((s) << 1))) >> (q)) & (m))
255
256 #define RTL_ARENA_HASH_INDEX(arena, addr) \
257 RTL_ARENA_HASH_INDEX_IMPL((addr), (arena)->m_hash_shift, (arena)->m_quantum_shift, ((arena)->m_hash_size - 1))
258
259 /** rtl_arena_hash_rescale()
260 *
261 * @precond arena->m_lock released.
262 */
263 void
264 rtl_arena_hash_rescale (
265 rtl_arena_type * arena,
266 sal_Size new_size
267 )
268 {
269 assert(new_size != 0);
270
271 rtl_arena_segment_type ** new_table;
272 sal_Size new_bytes;
273
274 new_bytes = new_size * sizeof(rtl_arena_segment_type*);
275 new_table = static_cast<rtl_arena_segment_type **>(rtl_arena_alloc (gp_arena_arena, &new_bytes));
276
277 if (new_table != 0)
278 {
279 rtl_arena_segment_type ** old_table;
280 sal_Size old_size, i;
281
282 memset (new_table, 0, new_bytes);
283
284 RTL_MEMORY_LOCK_ACQUIRE(&(arena->m_lock));
285
286 old_table = arena->m_hash_table;
287 old_size = arena->m_hash_size;
288
289 // SAL_INFO(
290 // "sal.rtl",
291 // "rtl_arena_hash_rescale(" << arena->m_name << "): nseg: "
292 // << (arena->m_stats.m_alloc - arena->m_stats.m_free) << " (ave: "
293 // << ((arena->m_stats.m_alloc - arena->m_stats.m_free)
294 // >> arena->m_hash_shift)
295 // << "), frees: " << arena->m_stats.m_free << " [old_size: "
296 // << old_size << ", new_size: " << new_size << ']');
297
298 arena->m_hash_table = new_table;
299 arena->m_hash_size = new_size;
300 arena->m_hash_shift = highbit(arena->m_hash_size) - 1;
301
302 for (i = 0; i < old_size; i++)
303 {
304 rtl_arena_segment_type * curr = old_table[i];
305 while (curr != 0)
306 {
307 rtl_arena_segment_type * next = curr->m_fnext;
308 rtl_arena_segment_type ** head;
309
310 // coverity[negative_shift]
311 head = &(arena->m_hash_table[RTL_ARENA_HASH_INDEX(arena, curr->m_addr)]);
312 curr->m_fnext = (*head);
313 (*head) = curr;
314
315 curr = next;
316 }
317 old_table[i] = 0;
318 }
319
320 RTL_MEMORY_LOCK_RELEASE(&(arena->m_lock));
321
322 if (old_table != arena->m_hash_table_0)
323 {
324 sal_Size old_bytes = old_size * sizeof(rtl_arena_segment_type*);
325 rtl_arena_free (gp_arena_arena, old_table, old_bytes);
326 }
327 }
328 }
329
330 /** rtl_arena_hash_insert()
331 * ...and update stats.
332 */
333 inline void
334 rtl_arena_hash_insert (
335 rtl_arena_type * arena,
336 rtl_arena_segment_type * segment
337 )
338 {
339 rtl_arena_segment_type ** ppSegment;
340
341 ppSegment = &(arena->m_hash_table[RTL_ARENA_HASH_INDEX(arena, segment->m_addr)]);
342
343 segment->m_fnext = (*ppSegment);
344 (*ppSegment) = segment;
345
346 arena->m_stats.m_alloc += 1;
347 arena->m_stats.m_mem_alloc += segment->m_size;
348 }
349
350 /** rtl_arena_hash_remove()
351 * ...and update stats.
352 */
353 rtl_arena_segment_type *
354 rtl_arena_hash_remove (
355 rtl_arena_type * arena,
356 sal_uIntPtr addr,
357 sal_Size size
358 )
359 {
360 rtl_arena_segment_type *segment, **segpp;
361 sal_Size lookups = 0;
362
363 segpp = &(arena->m_hash_table[RTL_ARENA_HASH_INDEX(arena, addr)]);
364 while ((segment = *segpp) != 0)
365 {
366 if (segment->m_addr == addr)
367 {
368 *segpp = segment->m_fnext, segment->m_fnext = segment->m_fprev = segment;
369 break;
370 }
371
372 /* update lookup miss stats */
373 lookups += 1;
374 segpp = &(segment->m_fnext);
375 }
376
377 assert(segment != 0); // bad free
378 if (segment != 0)
379 {
380 assert(segment->m_size == size);
381 (void) size; // avoid warnings
382
383 arena->m_stats.m_free += 1;
384 arena->m_stats.m_mem_alloc -= segment->m_size;
385
386 if (lookups > 1)
387 {
388 sal_Size nseg = (sal_Size)(arena->m_stats.m_alloc - arena->m_stats.m_free);
389 if (nseg > 4 * arena->m_hash_size)
390 {
391 if (!(arena->m_flags & RTL_ARENA_FLAG_RESCALE))
392 {
393 sal_Size ave = nseg >> arena->m_hash_shift;
394 assert(ave != 0);
395 sal_Size new_size = arena->m_hash_size << (highbit(ave) - 1);
396
397 arena->m_flags |= RTL_ARENA_FLAG_RESCALE;
398 RTL_MEMORY_LOCK_RELEASE(&(arena->m_lock));
399 rtl_arena_hash_rescale (arena, new_size);
400 RTL_MEMORY_LOCK_ACQUIRE(&(arena->m_lock));
401 arena->m_flags &= ~RTL_ARENA_FLAG_RESCALE;
402 }
403 }
404 }
405 }
406
407 return segment;
408 }
409
410 /* ================================================================= */
411
412 /** rtl_arena_segment_alloc()
413 * allocate (and remove) segment from freelist
414 *
415 * @precond arena->m_lock acquired
416 * @precond (*ppSegment == 0)
417 */
418 bool
419 rtl_arena_segment_alloc (
420 rtl_arena_type * arena,
421 sal_Size size,
422 rtl_arena_segment_type ** ppSegment
423 )
424 {
425 int index = 0;
426
427 assert(*ppSegment == 0);
428 if (!RTL_MEMORY_ISP2(size))
429 {
430 int msb = highbit(size);
431 if (RTL_ARENA_FREELIST_SIZE == sal::static_int_cast< size_t >(msb))
432 {
433 /* highest possible freelist: fall back to first fit */
434 rtl_arena_segment_type *head, *segment;
435
436 head = &(arena->m_freelist_head[msb - 1]);
437 for (segment = head->m_fnext; segment != head; segment = segment->m_fnext)
438 {
439 if (segment->m_size >= size)
440 {
441 /* allocate first fit segment */
442 (*ppSegment) = segment;
443 break;
444 }
445 }
446 goto dequeue_and_leave;
447 }
448
449 /* roundup to next power of 2 */
450 size = (((sal_Size)1) << msb);
451 }
452
453 index = lowbit(RTL_MEMORY_P2ALIGN(arena->m_freelist_bitmap, size));
454 if (index > 0)
455 {
456 /* instant fit: allocate first free segment */
457 rtl_arena_segment_type *head;
458
459 head = &(arena->m_freelist_head[index - 1]);
460 (*ppSegment) = head->m_fnext;
461 assert((*ppSegment) != head);
462 }
463
464 dequeue_and_leave:
465 if (*ppSegment != 0)
466 {
467 /* remove from freelist */
468 rtl_arena_freelist_remove (arena, (*ppSegment));
469 }
470 return (*ppSegment != 0);
471 }
472
473 /** rtl_arena_segment_create()
474 * import new (span) segment from source arena
475 *
476 * @precond arena->m_lock acquired
477 * @precond (*ppSegment == 0)
478 */
479 int
480 rtl_arena_segment_create (
481 rtl_arena_type * arena,
482 sal_Size size,
483 rtl_arena_segment_type ** ppSegment
484 )
485 {
486 assert((*ppSegment) == 0);
487 if (arena->m_source_alloc != 0)
488 {
489 rtl_arena_segment_get (arena, ppSegment);
490 if (*ppSegment != 0)
491 {
492 rtl_arena_segment_type * span = 0;
493 rtl_arena_segment_get (arena, &span);
494 if (span != 0)
495 {
496 /* import new span from source arena */
497 RTL_MEMORY_LOCK_RELEASE(&(arena->m_lock));
498
499 span->m_size = size;
500 span->m_addr = reinterpret_cast<sal_uIntPtr>(
501 (arena->m_source_alloc)(
502 arena->m_source_arena, &(span->m_size)));
503
504 RTL_MEMORY_LOCK_ACQUIRE(&(arena->m_lock));
505 if (span->m_addr != 0)
506 {
507 /* insert onto segment list, update stats */
508 span->m_type = RTL_ARENA_SEGMENT_TYPE_SPAN;
509 QUEUE_INSERT_HEAD_NAMED(&(arena->m_segment_head), span, s);
510 arena->m_stats.m_mem_total += span->m_size;
511
512 (*ppSegment)->m_addr = span->m_addr;
513 (*ppSegment)->m_size = span->m_size;
514 (*ppSegment)->m_type = RTL_ARENA_SEGMENT_TYPE_FREE;
515 QUEUE_INSERT_HEAD_NAMED(span, (*ppSegment), s);
516
517 /* report success */
518 return 1;
519 }
520 rtl_arena_segment_put (arena, &span);
521 }
522 rtl_arena_segment_put (arena, ppSegment);
523 }
524 }
525 return 0;
526 }
527
528 /** rtl_arena_segment_coalesce()
529 * mark as free and join with adjacent free segment(s)
530 *
531 * @precond arena->m_lock acquired
532 * @precond segment marked 'used'
533 */
534 void
535 rtl_arena_segment_coalesce (
536 rtl_arena_type * arena,
537 rtl_arena_segment_type * segment
538 )
539 {
540 rtl_arena_segment_type *next, *prev;
541
542 /* mark segment free */
543 assert(segment->m_type == RTL_ARENA_SEGMENT_TYPE_USED);
544 segment->m_type = RTL_ARENA_SEGMENT_TYPE_FREE;
545
546 /* try to merge w/ next segment */
547 next = segment->m_snext;
548 if (next->m_type == RTL_ARENA_SEGMENT_TYPE_FREE)
549 {
550 assert(segment->m_addr + segment->m_size == next->m_addr);
551 segment->m_size += next->m_size;
552
553 /* remove from freelist */
554 rtl_arena_freelist_remove (arena, next);
555
556 /* remove from segment list */
557 QUEUE_REMOVE_NAMED(next, s);
558
559 /* release segment descriptor */
560 rtl_arena_segment_put (arena, &next);
561 }
562
563 /* try to merge w/ prev segment */
564 prev = segment->m_sprev;
565 if (prev->m_type == RTL_ARENA_SEGMENT_TYPE_FREE)
566 {
567 assert(prev->m_addr + prev->m_size == segment->m_addr);
568 segment->m_addr = prev->m_addr;
569 segment->m_size += prev->m_size;
570
571 /* remove from freelist */
572 rtl_arena_freelist_remove (arena, prev);
573
574 /* remove from segment list */
575 QUEUE_REMOVE_NAMED(prev, s);
576
577 /* release segment descriptor */
578 rtl_arena_segment_put (arena, &prev);
579 }
580 }
581
582 /* ================================================================= */
583
584 /** rtl_arena_constructor()
585 */
586 void
587 rtl_arena_constructor (void * obj)
588 {
589 rtl_arena_type * arena = static_cast<rtl_arena_type*>(obj);
590 rtl_arena_segment_type * head;
591 size_t i;
592
593 memset (arena, 0, sizeof(rtl_arena_type));
594
595 QUEUE_START_NAMED(arena, arena_);
596
597 (void) RTL_MEMORY_LOCK_INIT(&(arena->m_lock));
598
599 head = &(arena->m_segment_reserve_span_head);
600 rtl_arena_segment_constructor (head);
601 head->m_type = RTL_ARENA_SEGMENT_TYPE_HEAD;
602
603 head = &(arena->m_segment_reserve_head);
604 rtl_arena_segment_constructor (head);
605 head->m_type = RTL_ARENA_SEGMENT_TYPE_HEAD;
606
607 head = &(arena->m_segment_head);
608 rtl_arena_segment_constructor (head);
609 head->m_type = RTL_ARENA_SEGMENT_TYPE_HEAD;
610
611 for (i = 0; i < RTL_ARENA_FREELIST_SIZE; i++)
612 {
613 head = &(arena->m_freelist_head[i]);
614 rtl_arena_segment_constructor (head);
615
616 head->m_size = (((sal_Size)1) << i);
617 head->m_type = RTL_ARENA_SEGMENT_TYPE_HEAD;
618 }
619
620 arena->m_hash_table = arena->m_hash_table_0;
621 arena->m_hash_size = RTL_ARENA_HASH_SIZE;
622 arena->m_hash_shift = highbit(arena->m_hash_size) - 1;
623 }
624
625 /** rtl_arena_destructor()
626 */
627 void
628 rtl_arena_destructor (void * obj)
629 {
630 rtl_arena_type * arena = static_cast<rtl_arena_type*>(obj);
631 rtl_arena_segment_type * head;
632 size_t i;
633
634 assert(QUEUE_STARTED_NAMED(arena, arena_));
635
636 RTL_MEMORY_LOCK_DESTROY(&(arena->m_lock));
637
638 head = &(arena->m_segment_reserve_span_head);
639 assert(head->m_type == RTL_ARENA_SEGMENT_TYPE_HEAD);
640 rtl_arena_segment_destructor (head);
641
642 head = &(arena->m_segment_reserve_head);
643 assert(head->m_type == RTL_ARENA_SEGMENT_TYPE_HEAD);
644 rtl_arena_segment_destructor (head);
645
646 head = &(arena->m_segment_head);
647 assert(head->m_type == RTL_ARENA_SEGMENT_TYPE_HEAD);
648 rtl_arena_segment_destructor (head);
649
650 for (i = 0; i < RTL_ARENA_FREELIST_SIZE; i++)
651 {
652 head = &(arena->m_freelist_head[i]);
653
654 assert(head->m_size == (((sal_Size)1) << i));
655 assert(head->m_type == RTL_ARENA_SEGMENT_TYPE_HEAD);
656
657 rtl_arena_segment_destructor (head);
658 }
659
660 assert(arena->m_hash_table == arena->m_hash_table_0);
661 assert(arena->m_hash_size == RTL_ARENA_HASH_SIZE);
662 assert(
663 arena->m_hash_shift ==
664 sal::static_int_cast< unsigned >(highbit(arena->m_hash_size) - 1));
665 }
666
667 /* ================================================================= */
668
669 /** rtl_arena_activate()
670 */
671 rtl_arena_type *
672 rtl_arena_activate (
673 rtl_arena_type * arena,
674 const char * name,
675 sal_Size quantum,
676 sal_Size quantum_cache_max,
677 rtl_arena_type * source_arena,
678 void * (SAL_CALL * source_alloc)(rtl_arena_type *, sal_Size *),
679 void (SAL_CALL * source_free) (rtl_arena_type *, void *, sal_Size)
680 )
681 {
682 assert(arena != 0);
683 if (arena != 0)
684 {
685 (void) snprintf (arena->m_name, sizeof(arena->m_name), "%s", name);
686
687 if (!RTL_MEMORY_ISP2(quantum))
688 {
689 /* roundup to next power of 2 */
690 quantum = (((sal_Size)1) << highbit(quantum));
691 }
692 quantum_cache_max = RTL_MEMORY_P2ROUNDUP(quantum_cache_max, quantum);
693
694 arena->m_quantum = quantum;
695 arena->m_quantum_shift = highbit(arena->m_quantum) - 1;
696 arena->m_qcache_max = quantum_cache_max;
697
698 arena->m_source_arena = source_arena;
699 arena->m_source_alloc = source_alloc;
700 arena->m_source_free = source_free;
701
702 if (arena->m_qcache_max > 0)
703 {
704 char namebuf[RTL_ARENA_NAME_LENGTH + 1];
705 int i, n = (arena->m_qcache_max >> arena->m_quantum_shift);
706
707 sal_Size size = n * sizeof(rtl_cache_type*);
708 arena->m_qcache_ptr = static_cast<rtl_cache_type**>(rtl_arena_alloc (gp_arena_arena, &size));
709 if (!(arena->m_qcache_ptr))
710 {
711 /* out of memory */
712 return 0;
713 }
714 for (i = 1; i <= n; i++)
715 {
716 size = i * arena->m_quantum;
717 (void) snprintf (namebuf, sizeof(namebuf), "%s_%" SAL_PRIuUINTPTR, arena->m_name, size);
718 arena->m_qcache_ptr[i - 1] = rtl_cache_create(namebuf, size, 0, NULL, NULL, NULL, NULL, arena, RTL_CACHE_FLAG_QUANTUMCACHE);
719 }
720 }
721
722 /* insert into arena list */
723 RTL_MEMORY_LOCK_ACQUIRE(&(g_arena_list.m_lock));
724 QUEUE_INSERT_TAIL_NAMED(&(g_arena_list.m_arena_head), arena, arena_);
725 RTL_MEMORY_LOCK_RELEASE(&(g_arena_list.m_lock));
726 }
727 return arena;
728 }
729
730 /** rtl_arena_deactivate()
731 */
732 void
733 rtl_arena_deactivate (
734 rtl_arena_type * arena
735 )
736 {
737 rtl_arena_segment_type * head, * segment;
738
739 /* remove from arena list */
740 RTL_MEMORY_LOCK_ACQUIRE(&(g_arena_list.m_lock));
741 QUEUE_REMOVE_NAMED(arena, arena_);
742 RTL_MEMORY_LOCK_RELEASE(&(g_arena_list.m_lock));
743
744 /* cleanup quantum cache(s) */
745 if ((arena->m_qcache_max > 0) && (arena->m_qcache_ptr != 0))
746 {
747 int i, n = (arena->m_qcache_max >> arena->m_quantum_shift);
748 for (i = 1; i <= n; i++)
749 {
750 if (arena->m_qcache_ptr[i - 1] != 0)
751 {
752 rtl_cache_destroy (arena->m_qcache_ptr[i - 1]);
753 arena->m_qcache_ptr[i - 1] = 0;
754 }
755 }
756 rtl_arena_free (
757 gp_arena_arena,
758 arena->m_qcache_ptr,
759 n * sizeof(rtl_cache_type*));
760
761 arena->m_qcache_ptr = 0;
762 }
763
764 /* check for leaked segments */
765 // SAL_INFO(
766 // "sal.rtl",
767 // "rtl_arena_deactivate(" << arena->m_name << "): allocs: "
768 // << arena->m_stats.m_alloc << ", frees: " << arena->m_stats.m_free
769 // << "; total: " << arena->m_stats.m_mem_total << ", used: "
770 // << arena->m_stats.m_mem_alloc);
771 if (arena->m_stats.m_alloc > arena->m_stats.m_free)
772 {
773 sal_Size i, n;
774
775 // SAL_INFO(
776 // "sal.rtl",
777 // "rtl_arena_deactivate(" << arena->m_name << "): cleaning up "
778 // << (arena->m_stats.m_alloc - arena->m_stats.m_free)
779 // << " leaked segment(s) [" << arena->m_stats.m_mem_alloc
780 // << " bytes]");
781
782 /* cleanup still used segment(s) */
783 for (i = 0, n = arena->m_hash_size; i < n; i++)
784 {
785 while ((segment = arena->m_hash_table[i]) != 0)
786 {
787 /* pop from hash table */
788 arena->m_hash_table[i] = segment->m_fnext, segment->m_fnext = segment->m_fprev = segment;
789
790 /* coalesce w/ adjacent free segment(s) */
791 rtl_arena_segment_coalesce (arena, segment);
792
793 /* insert onto freelist */
794 rtl_arena_freelist_insert (arena, segment);
795 }
796 }
797 }
798
799 /* cleanup hash table */
800 if (arena->m_hash_table != arena->m_hash_table_0)
801 {
802 rtl_arena_free (
803 gp_arena_arena,
804 arena->m_hash_table,
805 arena->m_hash_size * sizeof(rtl_arena_segment_type*));
806
807 arena->m_hash_table = arena->m_hash_table_0;
808 arena->m_hash_size = RTL_ARENA_HASH_SIZE;
809 arena->m_hash_shift = highbit(arena->m_hash_size) - 1;
810 }
811
812 /* cleanup segment list */
813 head = &(arena->m_segment_head);
814 for (segment = head->m_snext; segment != head; segment = head->m_snext)
815 {
816 if (segment->m_type == RTL_ARENA_SEGMENT_TYPE_FREE)
817 {
818 /* remove from freelist */
819 rtl_arena_freelist_remove (arena, segment);
820 }
821 else
822 {
823 /* can have only free and span segments here */
824 assert(segment->m_type == RTL_ARENA_SEGMENT_TYPE_SPAN);
825 }
826
827 /* remove from segment list */
828 QUEUE_REMOVE_NAMED(segment, s);
829
830 /* release segment descriptor */
831 rtl_arena_segment_put (arena, &segment);
832 }
833
834 /* cleanup segment reserve list */
835 head = &(arena->m_segment_reserve_head);
836 for (segment = head->m_snext; segment != head; segment = head->m_snext)
837 {
838 /* remove from segment list */
839 QUEUE_REMOVE_NAMED(segment, s);
840 }
841
842 /* cleanup segment reserve span(s) */
843 head = &(arena->m_segment_reserve_span_head);
844 for (segment = head->m_snext; segment != head; segment = head->m_snext)
845 {
846 /* can have only span segments here */
847 assert(segment->m_type == RTL_ARENA_SEGMENT_TYPE_SPAN);
848
849 /* remove from segment list */
850 QUEUE_REMOVE_NAMED(segment, s);
851
852 /* return span to g_machdep_arena */
853 rtl_machdep_free (gp_machdep_arena, reinterpret_cast<void*>(segment->m_addr), segment->m_size);
854 }
855 }
856
857 } //namespace
858 /* ================================================================= *
859 *
860 * arena implementation.
861 *
862 * ================================================================= */
863
864 /** rtl_arena_create()
865 */
866 rtl_arena_type *
867 SAL_CALL rtl_arena_create (
868 const char * name,
869 sal_Size quantum,
870 sal_Size quantum_cache_max,
871 rtl_arena_type * source_arena,
872 void * (SAL_CALL * source_alloc)(rtl_arena_type *, sal_Size *),
873 void (SAL_CALL * source_free) (rtl_arena_type *, void *, sal_Size),
874 SAL_UNUSED_PARAMETER int
875 ) SAL_THROW_EXTERN_C()
876 {
877 rtl_arena_type * result = 0;
878 sal_Size size = sizeof(rtl_arena_type);
879
880 try_alloc:
881 result = static_cast<rtl_arena_type*>(rtl_arena_alloc (gp_arena_arena, &size));
882 if (result != 0)
883 {
884 rtl_arena_type * arena = result;
885 rtl_arena_constructor (arena);
886
887 if (!source_arena)
888 {
889 assert(gp_default_arena != 0);
890 source_arena = gp_default_arena;
891 }
892
893 result = rtl_arena_activate (
894 arena,
895 name,
896 quantum,
897 quantum_cache_max,
898 source_arena,
899 source_alloc,
900 source_free
901 );
902
903 if (result == 0)
904 {
905 rtl_arena_deactivate (arena);
906 rtl_arena_destructor (arena);
907 rtl_arena_free (gp_arena_arena, arena, size);
908 }
909 }
910 else if (gp_arena_arena == 0)
911 {
912 ensureArenaSingleton();
913 if (gp_arena_arena)
914 {
915 /* try again */
916 goto try_alloc;
917 }
918 }
919 return result;
920 }
921
922 /** rtl_arena_destroy()
923 */
924 void
925 SAL_CALL rtl_arena_destroy (
926 rtl_arena_type * arena
927 ) SAL_THROW_EXTERN_C()
928 {
929 if (arena != 0)
930 {
931 rtl_arena_deactivate (arena);
932 rtl_arena_destructor (arena);
933 rtl_arena_free (gp_arena_arena, arena, sizeof(rtl_arena_type));
934 }
935 }
936
937 /** rtl_arena_alloc()
938 */
939 void *
940 SAL_CALL rtl_arena_alloc (
941 rtl_arena_type * arena,
942 sal_Size * pSize
943 ) SAL_THROW_EXTERN_C()
944 {
945 void * addr = 0;
946
947 if ((arena != 0) && (pSize != 0))
948 {
949 sal_Size size;
950
951 size = RTL_MEMORY_ALIGN((*pSize), arena->m_quantum);
952 if (size > arena->m_qcache_max)
953 {
954 /* allocate from segment list */
955 rtl_arena_segment_type *segment = 0;
956
957 RTL_MEMORY_LOCK_ACQUIRE(&(arena->m_lock));
958 if (rtl_arena_segment_alloc (arena, size, &segment) ||
959 rtl_arena_segment_create(arena, size, &segment) )
960 {
961 /* shrink to fit */
962 sal_Size oversize;
963
964 /* mark segment used */
965 assert(segment->m_type == RTL_ARENA_SEGMENT_TYPE_FREE);
966 segment->m_type = RTL_ARENA_SEGMENT_TYPE_USED;
967
968 /* resize */
969 assert(segment->m_size >= size);
970 oversize = segment->m_size - size;
971 if ((oversize >= arena->m_quantum) && (oversize >= arena->m_qcache_max))
972 {
973 rtl_arena_segment_type * remainder = 0;
974 rtl_arena_segment_get (arena, &remainder);
975 if (remainder != 0)
976 {
977 segment->m_size = size;
978
979 remainder->m_addr = segment->m_addr + segment->m_size;
980 remainder->m_size = oversize;
981 remainder->m_type = RTL_ARENA_SEGMENT_TYPE_FREE;
982 QUEUE_INSERT_HEAD_NAMED(segment, remainder, s);
983
984 rtl_arena_freelist_insert (arena, remainder);
985 }
986 }
987
988 rtl_arena_hash_insert (arena, segment);
989
990 (*pSize) = segment->m_size;
991 addr = reinterpret_cast<void*>(segment->m_addr);
992 }
993 RTL_MEMORY_LOCK_RELEASE(&(arena->m_lock));
994 }
995 else if (size > 0)
996 {
997 /* allocate from quantum cache(s) */
998 int index = (size >> arena->m_quantum_shift) - 1;
999 assert(arena->m_qcache_ptr[index] != 0);
1000
1001 addr = rtl_cache_alloc (arena->m_qcache_ptr[index]);
1002 if (addr != 0)
1003 (*pSize) = size;
1004 }
1005 }
1006 return addr;
1007 }
1008
1009 /** rtl_arena_free()
1010 */
1011 void
1012 SAL_CALL rtl_arena_free (
1013 rtl_arena_type * arena,
1014 void * addr,
1015 sal_Size size
1016 ) SAL_THROW_EXTERN_C()
1017 {
1018 if (arena != 0)
1019 {
1020 size = RTL_MEMORY_ALIGN(size, arena->m_quantum);
1021 if (size > arena->m_qcache_max)
1022 {
1023 /* free to segment list */
1024 rtl_arena_segment_type * segment;
1025
1026 RTL_MEMORY_LOCK_ACQUIRE(&(arena->m_lock));
1027
1028 segment = rtl_arena_hash_remove (arena, reinterpret_cast<sal_uIntPtr>(addr), size);
1029 if (segment != 0)
1030 {
1031 rtl_arena_segment_type *next, *prev;
1032
1033 /* coalesce w/ adjacent free segment(s) */
1034 rtl_arena_segment_coalesce (arena, segment);
1035
1036 /* determine (new) next and prev segment */
1037 next = segment->m_snext, prev = segment->m_sprev;
1038
1039 /* entire span free when prev is a span, and next is either a span or a list head */
1040 if (((prev->m_type == RTL_ARENA_SEGMENT_TYPE_SPAN)) &&
1041 ((next->m_type == RTL_ARENA_SEGMENT_TYPE_SPAN) ||
1042 (next->m_type == RTL_ARENA_SEGMENT_TYPE_HEAD)) )
1043 {
1044 assert(
1045 prev->m_addr == segment->m_addr
1046 && prev->m_size == segment->m_size);
1047
1048 if (arena->m_source_free)
1049 {
1050 addr = reinterpret_cast<void*>(prev->m_addr);
1051 size = prev->m_size;
1052
1053 /* remove from segment list */
1054 QUEUE_REMOVE_NAMED(segment, s);
1055
1056 /* release segment descriptor */
1057 rtl_arena_segment_put (arena, &segment);
1058
1059 /* remove from segment list */
1060 QUEUE_REMOVE_NAMED(prev, s);
1061
1062 /* release (span) segment descriptor */
1063 rtl_arena_segment_put (arena, &prev);
1064
1065 /* update stats, return span to source arena */
1066 arena->m_stats.m_mem_total -= size;
1067 RTL_MEMORY_LOCK_RELEASE(&(arena->m_lock));
1068
1069 (arena->m_source_free)(arena->m_source_arena, addr, size);
1070 return;
1071 }
1072 }
1073
1074 /* insert onto freelist */
1075 rtl_arena_freelist_insert (arena, segment);
1076 }
1077
1078 RTL_MEMORY_LOCK_RELEASE(&(arena->m_lock));
1079 }
1080 else if (size > 0)
1081 {
1082 /* free to quantum cache(s) */
1083 int index = (size >> arena->m_quantum_shift) - 1;
1084 assert(arena->m_qcache_ptr[index] != 0);
1085
1086 rtl_cache_free (arena->m_qcache_ptr[index], addr);
1087 }
1088 }
1089 }
1090
1091 /* ================================================================= *
1092 *
1093 * machdep internals.
1094 *
1095 * ================================================================= */
1096
1097 #if defined(SAL_UNX)
1098 #include <sys/mman.h>
1099 #elif defined(SAL_W32)
1100 #define MAP_FAILED 0
1101 #endif /* SAL_UNX || SAL_W32 */
1102
1103 namespace
1104 {
1105
1106 /** rtl_machdep_alloc()
1107 */
1108 void *
1109 SAL_CALL rtl_machdep_alloc (
1110 rtl_arena_type * pArena,
1111 sal_Size * pSize
1112 )
1113 {
1114 void * addr;
1115 sal_Size size = (*pSize);
1116
1117 assert(pArena == gp_machdep_arena);
1118
1119 #if defined(SOLARIS) && defined(SPARC)
1120 /* see @ mmap(2) man pages */
1121 size += (pArena->m_quantum + pArena->m_quantum); /* "red-zone" pages */
1122 if (size > (4 << 20))
1123 size = RTL_MEMORY_P2ROUNDUP(size, (4 << 20));
1124 else if (size > (512 << 10))
1125 size = RTL_MEMORY_P2ROUNDUP(size, (512 << 10));
1126 else
1127 size = RTL_MEMORY_P2ROUNDUP(size, (64 << 10));
1128 size -= (pArena->m_quantum + pArena->m_quantum); /* "red-zone" pages */
1129 #else
1130 /* default allocation granularity */
1131 if(pArena->m_quantum < (64 << 10))
1132 {
1133 size = RTL_MEMORY_P2ROUNDUP(size, (64 << 10));
1134 }
1135 else
1136 {
1137 size = RTL_MEMORY_P2ROUNDUP(size, pArena->m_quantum);
1138 }
1139 #endif
1140
1141 #if defined(SAL_UNX)
1142 addr = mmap (NULL, (size_t)(size), PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0);
1143 #elif defined(SAL_W32)
1144 addr = VirtualAlloc (NULL, (SIZE_T)(size), MEM_COMMIT, PAGE_READWRITE);
1145 #endif /* (SAL_UNX || SAL_W32) */
1146
1147 if (addr != MAP_FAILED)
1148 {
1149 pArena->m_stats.m_alloc += 1;
1150 pArena->m_stats.m_mem_total += size;
1151 pArena->m_stats.m_mem_alloc += size;
1152
1153 (*pSize) = size;
1154 return addr;
1155 }
1156 return NULL;
1157 }
1158
1159 /** rtl_machdep_free()
1160 */
1161 void
1162 SAL_CALL rtl_machdep_free (
1163 rtl_arena_type * pArena,
1164 void * pAddr,
1165 sal_Size nSize
1166 )
1167 {
1168 assert(pArena == gp_machdep_arena);
1169
1170 pArena->m_stats.m_free += 1;
1171 pArena->m_stats.m_mem_total -= nSize;
1172 pArena->m_stats.m_mem_alloc -= nSize;
1173
1174 #if defined(SAL_UNX)
1175 (void) munmap(pAddr, nSize);
1176 #elif defined(SAL_W32)
1177 (void) VirtualFree ((LPVOID)(pAddr), (SIZE_T)(0), MEM_RELEASE);
1178 #endif /* (SAL_UNX || SAL_W32) */
1179 }
1180
1181 sal_Size
1182 rtl_machdep_pagesize()
1183 {
1184 #if defined(SAL_UNX)
1185 #if defined(FREEBSD) || defined(NETBSD) || defined(DRAGONFLY)
1186 return (sal_Size)getpagesize();
1187 #else /* POSIX */
1188 return (sal_Size)sysconf(_SC_PAGESIZE);
1189 #endif /* xBSD || POSIX */
1190 #elif defined(SAL_W32)
1191 SYSTEM_INFO info;
1192 GetSystemInfo (&info);
1193 return (sal_Size)info.dwPageSize;
1194 #endif /* (SAL_UNX || SAL_W32) */
1195 }
1196
1197 } //namespace
1198
1199 /* ================================================================= *
1200 *
1201 * arena initialization.
1202 *
1203 * ================================================================= */
1204
1205 void
1206 rtl_arena_init()
1207 {
1208 {
1209 /* list of arenas */
1210 RTL_MEMORY_LOCK_INIT(&(g_arena_list.m_lock));
1211 rtl_arena_constructor (&(g_arena_list.m_arena_head));
1212 }
1213 {
1214 /* machdep (pseudo) arena */
1215 static rtl_arena_type g_machdep_arena;
1216
1217 assert(gp_machdep_arena == 0);
1218 rtl_arena_constructor (&g_machdep_arena);
1219
1220 gp_machdep_arena = rtl_arena_activate (
1221 &g_machdep_arena,
1222 "rtl_machdep_arena",
1223 rtl_machdep_pagesize(),
1224 0, /* no quantum caching */
1225 0, 0, 0 /* no source */
1226 );
1227 assert(gp_machdep_arena != 0);
1228 }
1229 {
1230 /* default arena */
1231 static rtl_arena_type g_default_arena;
1232
1233 assert(gp_default_arena == 0);
1234 rtl_arena_constructor (&g_default_arena);
1235
1236 gp_default_arena = rtl_arena_activate (
1237 &g_default_arena,
1238 "rtl_default_arena",
1239 rtl_machdep_pagesize(),
1240 0, /* no quantum caching */
1241 gp_machdep_arena, /* source */
1242 rtl_machdep_alloc,
1243 rtl_machdep_free
1244 );
1245 assert(gp_default_arena != 0);
1246 }
1247 {
1248 /* arena internal arena */
1249 static rtl_arena_type g_arena_arena;
1250
1251 assert(gp_arena_arena == 0);
1252 rtl_arena_constructor (&g_arena_arena);
1253
1254 gp_arena_arena = rtl_arena_activate (
1255 &g_arena_arena,
1256 "rtl_arena_internal_arena",
1257 64, /* quantum */
1258 0, /* no quantum caching */
1259 gp_default_arena, /* source */
1260 rtl_arena_alloc,
1261 rtl_arena_free
1262 );
1263 assert(gp_arena_arena != 0);
1264 }
1265 // SAL_INFO("sal.rtl", "rtl_arena_init completed");
1266 }
1267
1268 /* ================================================================= */
1269
1270 void
1271 rtl_arena_fini()
1272 {
1273 if (gp_arena_arena != 0)
1274 {
1275 rtl_arena_type * arena, * head;
1276
1277 RTL_MEMORY_LOCK_ACQUIRE(&(g_arena_list.m_lock));
1278 head = &(g_arena_list.m_arena_head);
1279
1280 for (arena = head->m_arena_next; arena != head; arena = arena->m_arena_next)
1281 {
1282 // SAL_INFO(
1283 // "sal.rtl",
1284 // "rtl_arena_fini(" << arena->m_name << "): allocs: "
1285 // << arena->m_stats.m_alloc << ", frees: "
1286 // << arena->m_stats.m_free << "; total: "
1287 // << arena->m_stats.m_mem_total << ", used: "
1288 // << arena->m_stats.m_mem_alloc);
1289 }
1290 RTL_MEMORY_LOCK_RELEASE(&(g_arena_list.m_lock));
1291 }
1292 // SAL_INFO("sal.rtl", "rtl_arena_fini completed");
1293 }
1294
1295 /* ================================================================= */
1296
1297 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
FREE OFFICE SUITE