libs/pbd/reallocpool.cc

   1 /*
   2  * Copyright (C) 2016 Robin Gareus <robin@gareus.org>
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  17  */
  18
  19 #include <stdlib.h>
  20 #include <string.h>
  21
  22 #ifndef PLATFORM_WINDOWS
  23 #include <sys/mman.h>
  24 #endif
  25
  26 #include "pbd/reallocpool.h"
  27
  28 #if defined RAP_WITH_SEGMENT_STATS || defined RAP_WITH_CALL_STATS
  29 #include <cstdio>
  30 #endif
  31
  32 #ifdef RAP_WITH_SEGMENT_STATS
  33 #define STATS_segment collect_segment_stats();
  34 #else
  35 #define STATS_segment
  36 #endif
  37
  38 #ifdef RAP_WITH_CALL_STATS
  39 #define STATS_inc(VAR) ++VAR;
  40 #define STATS_if(COND, VAR) if (COND) {++VAR;}
  41 #define STATS_used(DELTA) { _cur_used += (DELTA); if (_cur_used > _max_used) { _max_used = _cur_used; } }
  42 #else
  43 #define STATS_inc(VAR)
  44 #define STATS_if(COND, VAR)
  45 #define STATS_used(DELTA)
  46 #endif
  47
  48 #ifdef RAP_WITH_HISTOGRAM
  49 #define STATS_hist(VAR, SIZE) ++VAR[hist_bin(SIZE)];
  50 #else
  51 #define STATS_hist(VAR, SIZE)
  52 #endif
  53
  54 using namespace PBD;
  55
  56 typedef int poolsize_t;
  57
  58 ReallocPool::ReallocPool (std::string name, size_t bytes)
  59         : _name (name)
  60         , _poolsize (bytes)
  61         , _pool (0)
  62 #ifdef RAP_WITH_SEGMENT_STATS
  63         , _cur_avail (0)
  64         , _cur_allocated (0)
  65         , _max_allocated (0)
  66         , _seg_cur_count (0)
  67         , _seg_max_count (0)
  68         , _seg_max_used (0)
  69         , _seg_max_avail (0)
  70 #endif
  71 #ifdef RAP_WITH_CALL_STATS
  72         , _n_alloc (0)
  73         , _n_grow (0)
  74         , _n_shrink (0)
  75         , _n_free (0)
  76         , _n_noop (0)
  77         , _n_oom (0)
  78         , _cur_used (0)
  79         , _max_used (0)
  80 #endif
  81 {
  82         _pool = (char*) ::malloc (bytes);
  83
  84         memset (_pool, 0, bytes); // make resident
  85 #ifndef PLATFORM_WINDOWS
  86         mlock (_pool, bytes);
  87 #endif
  88
  89         poolsize_t *in = (poolsize_t*) _pool;
  90         *in = - (bytes - sizeof (poolsize_t));
  91         _mru = _pool;
  92
  93 #ifdef RAP_WITH_HISTOGRAM
  94         for (int i = 0; i < RAP_WITH_HISTOGRAM; ++i) {
  95                 _hist_alloc[i] = _hist_free[i] = _hist_grow[i] = _hist_shrink[i] = 0;
  96         }
  97 #endif
  98 }
  99
 100 ReallocPool::~ReallocPool ()
 101 {
 102         STATS_segment;
 103         printstats ();
 104         ::free (_pool);
 105         _pool = NULL;
 106 }
 107
 108 // realloc() does it all, malloc(), realloc() and free()
 109 void *
 110 ReallocPool::_realloc (void *ptr, size_t oldsize, size_t newsize) {
 111         void *rv = NULL;
 112
 113         if (ptr == 0 && newsize == 0) {
 114                 STATS_inc(_n_noop);
 115                 return NULL;
 116         }
 117
 118         if (ptr == 0) {
 119                 rv = _malloc (newsize);
 120                 STATS_if (!rv, _n_oom);
 121                 STATS_inc(_n_alloc);
 122                 STATS_hist(_hist_alloc, newsize);
 123                 STATS_segment;
 124                 return rv;
 125         }
 126
 127         if (newsize == 0) {
 128                 STATS_hist(_hist_free, _asize(ptr));
 129                 STATS_inc(_n_free);
 130                 STATS_segment;
 131                 _free (ptr);
 132                 return NULL;
 133         }
 134
 135         if (newsize == oldsize) {
 136                 STATS_inc(_n_noop);
 137                 return ptr;
 138         }
 139
 140         if (newsize > oldsize) {
 141 #ifdef RAP_BLOCKSIZE
 142                 const size_t ns = (newsize + RAP_BLOCKSIZE) & (~RAP_BLOCKSIZE);
 143                 if (ns <= _asize(ptr)) {
 144                         STATS_inc(_n_noop);
 145                         return ptr;
 146                 }
 147 #endif
 148                 if ((rv = _malloc (newsize))) {
 149                         memcpy (rv, ptr, oldsize);
 150                 }
 151                 _free (ptr);
 152                 STATS_if(!rv, _n_oom);
 153                 STATS_inc(_n_grow);
 154                 STATS_hist(_hist_grow, newsize);
 155                 STATS_segment;
 156                 return rv;
 157         }
 158
 159         if (newsize < oldsize) {
 160 #if 0 // re-allocate
 161                 if ((rv = _malloc (newsize))) {
 162                         memccpy (rv, ptr, newsize);
 163                 }
 164                 STATS_if(!rv, _n_oom);
 165                 _free (ptr);
 166 #elif 1 // shrink current segment
 167                 const size_t ns = (newsize + RAP_BLOCKSIZE) & (~RAP_BLOCKSIZE);
 168                 _shrink (ptr, ns);
 169                 rv = ptr;
 170 #else // do nothing
 171                 rv = ptr;
 172 #endif
 173                 STATS_inc(_n_shrink);
 174                 STATS_hist (_hist_shrink, newsize);
 175                 STATS_segment;
 176                 return rv;
 177         }
 178         return NULL; // not reached
 179 }
 180
 181 #define SEGSIZ (*((poolsize_t*) p))
 182
 183 void
 184 ReallocPool::consolidate_ptr (char *p) {
 185         const poolsize_t sop = sizeof(poolsize_t);
 186         if (p - SEGSIZ + sop >= _pool + _poolsize) {
 187                 return; // reached end
 188         }
 189         poolsize_t *next = (poolsize_t*)(p - SEGSIZ + sop);
 190         while (*next < 0) {
 191                 SEGSIZ = SEGSIZ + (*next) - sop;
 192                 if (p - SEGSIZ + sop >= _pool + _poolsize) {
 193                         break;
 194                 }
 195                 next = (poolsize_t*)(p -SEGSIZ + sop);
 196         }
 197         _mru = p;
 198 }
 199
 200 void *
 201 ReallocPool::_malloc (size_t s) {
 202         const poolsize_t sop = sizeof(poolsize_t);
 203         size_t traversed = 0;
 204         char *p = _mru;
 205
 206 #ifdef RAP_BLOCKSIZE
 207         s = (s + RAP_BLOCKSIZE) & (~RAP_BLOCKSIZE); // optional, helps to reduce fragmentation
 208 #endif
 209
 210         while (1) { // iterates at most once over the available pool
 211                 while (SEGSIZ > 0) {
 212                         traversed += SEGSIZ + sop;
 213                         if (traversed >= _poolsize) {
 214                                 return NULL; // reached last segment. OOM.
 215                         }
 216                         p += SEGSIZ + sop;
 217                         if (p == _pool + _poolsize) {
 218                                 p = _pool;
 219                         }
 220                 }
 221
 222                 // found free segment.
 223                 const poolsize_t avail = -SEGSIZ;
 224                 const poolsize_t sp = (poolsize_t)s;
 225                 const poolsize_t ss = sop + s;
 226
 227                 if (sp == avail) {
 228                         // exact match
 229                         SEGSIZ = -SEGSIZ;
 230                         STATS_used (s);
 231                         return (p + sop);
 232                 }
 233
 234                 if (ss < avail) {
 235                         // segment is larger than required space,
 236                         // (we need to fit data + two non-zero poolsize_t)
 237                         SEGSIZ = sp; // mark area as used.
 238                         *((poolsize_t*)(p + ss)) = ss - avail; // mark free space after.
 239                         consolidate_ptr (p + ss);
 240                         _mru = p + ss;
 241                         STATS_used (s);
 242                         return (p + sop);
 243                 }
 244
 245                 // segment is not large enough
 246                 consolidate_ptr (p); // try to consolidate with next segment (if any)
 247
 248                 // check segment (again) and skip over too small free ones
 249                 while (SEGSIZ < 0 && (-SEGSIZ) <= ss && (-SEGSIZ) != sp) {
 250                         traversed += -SEGSIZ + sop;
 251                         if (traversed >= _poolsize) {
 252                                 return NULL; // reached last segment. OOM.
 253                         }
 254                         p += (-SEGSIZ) + sop;
 255                         if (p >= _pool + _poolsize) {
 256                                 p = _pool;
 257                                 if (SEGSIZ < 0) consolidate_ptr (p);
 258                         }
 259                 }
 260         }
 261 }
 262 #undef SEGSIZ
 263
 264 void
 265 ReallocPool::_free (void *ptr) {
 266         poolsize_t *in = (poolsize_t*) ptr;
 267         --in;
 268         *in = -*in; // mark as free
 269         //_mru = p + ss;
 270         STATS_used (*in);
 271 }
 272
 273 void
 274 ReallocPool::_shrink (void *ptr, size_t newsize) {
 275         poolsize_t *in = (poolsize_t*) ptr;
 276         --in;
 277         const poolsize_t avail = *in;
 278         const poolsize_t ss = newsize + sizeof(poolsize_t);
 279         if (avail <= ss) {
 280                 return; // can't shrink
 281         }
 282         const poolsize_t sp = (poolsize_t)newsize;
 283         STATS_used (newsize - avail);
 284         *in = sp; // set new size
 285         char *p = (char*) in;
 286         *((poolsize_t*)(p + ss)) = ss - avail; // mark free space after.
 287         //_mru = p + ss;
 288 }
 289
 290 size_t
 291 ReallocPool::_asize (void *ptr) {
 292         if (ptr == 0) return 0;
 293         poolsize_t *in = (poolsize_t*) ptr;
 294         --in;
 295         return (*in);
 296 }
 297
 298
 299 /** STATS **/
 300
 301 void
 302 ReallocPool::printstats ()
 303 {
 304 #ifdef RAP_WITH_SEGMENT_STATS
 305         printf ("ReallocPool '%s': used: %ld (%.1f%%) (max: %ld), free: %ld [bytes]\n"
 306                         "|| segments: cur: %ld (max: %ld), largest-used: %ld, largest-free: %ld\n",
 307                         _name.c_str(),
 308                         _cur_allocated, _cur_allocated * 100.f / _poolsize, _max_allocated, _cur_avail,
 309                         _seg_cur_count, _seg_max_count, _seg_max_used, _seg_max_avail);
 310 #elif defined RAP_WITH_CALL_STATS
 311         printf ("ReallocPool '%s':\n", _name.c_str());
 312 #endif
 313 #ifdef RAP_WITH_CALL_STATS
 314                 printf("|| malloc(): %ld, free(): %ld, realloc()+:%ld, realloc()-: %ld NOOP:%ld OOM:%ld\n",
 315                         _n_alloc, _n_free, _n_grow, _n_shrink, _n_noop, _n_oom);
 316                 printf("|| used: %ld / %ld, max: %ld (%.1f%%)\n",
 317                                 _cur_used, _poolsize,
 318                                 _max_used, 100.f *_max_used / _poolsize);
 319 #endif
 320 #ifdef RAP_WITH_HISTOGRAM
 321                 printf("--- malloc()\n");
 322                 print_histogram (_hist_alloc);
 323                 printf("--- realloc()/grow-to\n");
 324                 print_histogram (_hist_grow);
 325                 printf("--- realloc()/shrink-to\n");
 326                 print_histogram (_hist_shrink);
 327                 printf("--- free() histogram\n");
 328                 print_histogram (_hist_free);
 329                 printf("--------------------\n");
 330 #endif
 331 }
 332
 333 void
 334 ReallocPool::dumpsegments ()
 335 {
 336         char *p = _pool;
 337         const poolsize_t sop = sizeof(poolsize_t);
 338         poolsize_t *in = (poolsize_t*) p;
 339         unsigned int traversed = 0;
 340         printf ("<<<<< %s\n", _name.c_str());
 341         while (1) {
 342                 if ((*in) > 0) {
 343                         printf ("0x%08x used %4d\n", traversed, *in);
 344                         printf ("0x%08x   data %p\n", traversed + sop , p + sop);
 345                         traversed += *in + sop;
 346                         p += *in + sop;
 347                 } else if ((*in) < 0) {
 348                         printf ("0x%08x free %4d [+%d]\n", traversed, -*in, sop);
 349                         traversed += -*in + sop;
 350                         p += -*in + sop;
 351                 } else {
 352                         printf ("0x%08x Corrupt!\n", traversed);
 353                         break;
 354                 }
 355                 in = (poolsize_t*) p;
 356                 if (p == _pool + _poolsize) {
 357                         printf ("%08x end\n", traversed);
 358                         break;
 359                 }
 360                 if (p > _pool + _poolsize) {
 361                         printf ("%08x Beyond End!\n", traversed);
 362                         break;
 363                 }
 364         }
 365         printf (">>>>>\n");
 366 }
 367
 368 #ifdef RAP_WITH_SEGMENT_STATS
 369 void
 370 ReallocPool::collect_segment_stats ()
 371 {
 372         char *p = _pool;
 373         poolsize_t *in = (poolsize_t*) p;
 374
 375         _cur_allocated = _cur_avail = 0;
 376         _seg_cur_count = _seg_max_avail = _seg_max_used = 0;
 377
 378         while (1) {
 379                 ++_seg_cur_count;
 380                 if ((*in) > 0) {
 381                         _cur_allocated += *in;
 382                         p += *in;
 383                         if (*in > (poolsize_t)_seg_max_used) {
 384                                 _seg_max_used = *in;
 385                         }
 386                 } else {
 387                         _cur_avail += -*in;
 388                         p += -*in;
 389                         if (-*in > (poolsize_t)_seg_max_avail) {
 390                                 _seg_max_avail = -*in;
 391                         }
 392                 }
 393                 p += sizeof(poolsize_t);
 394                 in = (poolsize_t*) p;
 395                 if (p == _pool + _poolsize) {
 396                         break;
 397                 }
 398         }
 399         _seg_cur_count = _seg_cur_count;
 400
 401         if (_cur_allocated > _max_allocated) {
 402                 _max_allocated = _cur_allocated;
 403         }
 404         if (_seg_cur_count > _seg_max_count) {
 405                 _seg_max_count = _seg_cur_count;
 406         }
 407 }
 408 #endif
 409
 410 #ifdef RAP_WITH_HISTOGRAM
 411 void
 412 ReallocPool::print_histogram (size_t const * const histogram) const
 413 {
 414         size_t maxhist = 0;
 415         for (int i = 0; i < RAP_WITH_HISTOGRAM; ++i) {
 416                 if (histogram[i] > maxhist) maxhist = histogram[i];
 417         }
 418         const int termwidth = 50;
 419 #ifdef RAP_BLOCKSIZE
 420         const int fact = RAP_BLOCKSIZE + 1;
 421 #endif
 422         if (maxhist > 0) for (int i = 0; i < RAP_WITH_HISTOGRAM; ++i) {
 423                 if (histogram[i] == 0) { continue; }
 424                 if (i == RAP_WITH_HISTOGRAM -1 ) {
 425 #ifdef RAP_BLOCKSIZE
 426                         printf("     > %4d: %7lu ", i * fact, histogram[i]);
 427 #else
 428                         printf(">%4d:%7lu ", i * fact, histogram[i]);
 429 #endif
 430                 } else {
 431 #ifdef RAP_BLOCKSIZE
 432                         printf("%4d .. %4d: %7lu ", i * fact, (i + 1) * fact -1, histogram[i]);
 433 #else
 434                         printf("%4d: %7lu ", i * fact, (i + 1) * fact -1 , histogram[i]);
 435 #endif
 436                 }
 437                 int bar_width = (histogram[i] * termwidth ) / maxhist;
 438                 if (bar_width == 0 && histogram[i] > 0) bar_width = 1;
 439                 for (int j = 0; j < bar_width; ++j) printf("#");
 440                 printf("\n");
 441         }
 442 }
 443
 444 unsigned int
 445 ReallocPool::hist_bin (size_t s) const {
 446 #ifdef RAP_BLOCKSIZE
 447         s = (s + RAP_BLOCKSIZE) & (~RAP_BLOCKSIZE);
 448         s /= (RAP_BLOCKSIZE + 1);
 449 #endif
 450         if (s > RAP_WITH_HISTOGRAM - 1) s = RAP_WITH_HISTOGRAM - 1;
 451         return s;
 452 }
 453 #endif