sal/rtl/alloc_arena.cxx

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