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 #include <cstdio>
  22
  23 #ifndef PLATFORM_WINDOWS
  24 #include <sys/mman.h>
  25 #endif
  26
  27 #include "pbd/reallocpool.h"
  28
  29 #ifdef RAP_WITH_SEGMENT_STATS
  30 #include <assert.h>
  31 #define STATS_segment collect_segment_stats();
  32 #define ASSERT assert
  33 #else
  34 #define STATS_segment
  35 #define ASSERT
  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         ASSERT (!ptr || oldsize <= _asize (ptr));
 113         oldsize = _asize (ptr); // ignore provided oldsize
 114
 115         if (ptr == 0 && newsize == 0) {
 116                 STATS_inc(_n_noop);
 117                 return NULL;
 118         }
 119
 120         if (ptr == 0) {
 121                 rv = _malloc (newsize);
 122                 STATS_if (!rv, _n_oom);
 123                 STATS_inc(_n_alloc);
 124                 STATS_hist(_hist_alloc, newsize);
 125                 STATS_segment;
 126                 return rv;
 127         }
 128
 129         if (newsize == 0) {
 130                 STATS_hist(_hist_free, _asize(ptr));
 131                 STATS_inc(_n_free);
 132                 STATS_segment;
 133                 _free (ptr);
 134                 return NULL;
 135         }
 136
 137         if (newsize == oldsize) {
 138                 ASSERT (_asize (ptr) <= newsize);
 139                 STATS_inc(_n_noop);
 140                 return ptr;
 141         }
 142
 143         if (newsize > oldsize) {
 144 #ifdef RAP_BLOCKSIZE
 145                 const size_t ns = (newsize + RAP_BLOCKSIZE) & (~RAP_BLOCKSIZE);
 146                 if (ns <= _asize(ptr)) {
 147                         STATS_inc(_n_noop);
 148                         return ptr;
 149                 }
 150 #endif
 151                 if ((rv = _malloc (newsize))) {
 152                         memcpy (rv, ptr, oldsize);
 153                 }
 154                 if (rv) {
 155                         _free (ptr);
 156                 }
 157                 STATS_if(!rv, _n_oom);
 158                 STATS_inc(_n_grow);
 159                 STATS_hist(_hist_grow, newsize);
 160                 STATS_segment;
 161                 return rv;
 162         }
 163
 164         if (newsize < oldsize) {
 165                 ASSERT (_asize (ptr) >= newsize);
 166 #if 0 // re-allocate
 167                 if ((rv = _malloc (newsize))) {
 168                         memccpy (rv, ptr, newsize);
 169                 }
 170                 STATS_if(!rv, _n_oom);
 171                 _free (ptr);
 172 #elif 1 // shrink current segment
 173                 const size_t ns = (newsize + RAP_BLOCKSIZE) & (~RAP_BLOCKSIZE);
 174                 _shrink (ptr, ns);
 175                 rv = ptr;
 176 #else // do nothing
 177                 rv = ptr;
 178 #endif
 179                 STATS_inc(_n_shrink);
 180                 STATS_hist (_hist_shrink, newsize);
 181                 STATS_segment;
 182                 return rv;
 183         }
 184         return NULL; // not reached
 185 }
 186
 187 #define SEGSIZ (*((poolsize_t*) p))
 188
 189 void
 190 ReallocPool::consolidate_ptr (char *p) {
 191         const poolsize_t sop = sizeof(poolsize_t);
 192         if (p - SEGSIZ + sop >= _pool + _poolsize) {
 193                 return; // reached end
 194         }
 195         poolsize_t *next = (poolsize_t*)(p - SEGSIZ + sop);
 196         while (*next < 0) {
 197                 SEGSIZ = SEGSIZ + (*next) - sop;
 198                 if (p - SEGSIZ + sop >= _pool + _poolsize) {
 199                         break;
 200                 }
 201                 next = (poolsize_t*)(p -SEGSIZ + sop);
 202         }
 203         _mru = p;
 204 }
 205
 206 void *
 207 ReallocPool::_malloc (size_t s) {
 208         const poolsize_t sop = sizeof(poolsize_t);
 209         size_t traversed = 0;
 210         char *p = _mru;
 211
 212 #ifdef RAP_BLOCKSIZE
 213         s = (s + RAP_BLOCKSIZE) & (~RAP_BLOCKSIZE); // optional, helps to reduce fragmentation
 214 #endif
 215
 216         while (1) { // iterates at most once over the available pool
 217                 ASSERT (SEGSIZ != 0);
 218                 while (SEGSIZ > 0) {
 219                         traversed += SEGSIZ + sop;
 220                         if (traversed >= _poolsize) {
 221                                 return NULL; // reached last segment. OOM.
 222                         }
 223                         p += SEGSIZ + sop;
 224                         if (p == _pool + _poolsize) {
 225                                 p = _pool;
 226                         }
 227                 }
 228
 229                 // found free segment.
 230                 const poolsize_t avail = -SEGSIZ;
 231                 const poolsize_t sp = (poolsize_t)s;
 232                 const poolsize_t ss = sop + s;
 233
 234                 if (sp == avail) {
 235                         // exact match
 236                         SEGSIZ = -SEGSIZ;
 237                         STATS_used (s);
 238                         return (p + sop);
 239                 }
 240
 241                 if (ss < avail) {
 242                         // segment is larger than required space,
 243                         // (we need to fit data + two non-zero poolsize_t)
 244                         SEGSIZ = sp; // mark area as used.
 245                         *((poolsize_t*)(p + ss)) = ss - avail; // mark free space after.
 246                         consolidate_ptr (p + ss);
 247                         _mru = p + ss;
 248                         STATS_used (s);
 249                         return (p + sop);
 250                 }
 251
 252                 // segment is not large enough
 253                 consolidate_ptr (p); // try to consolidate with next segment (if any)
 254
 255                 // check segment (again) and skip over too small free ones
 256                 while (SEGSIZ < 0 && (-SEGSIZ) <= ss && (-SEGSIZ) != sp) {
 257                         traversed += -SEGSIZ + sop;
 258                         if (traversed >= _poolsize) {
 259                                 return NULL; // reached last segment. OOM.
 260                         }
 261                         p += (-SEGSIZ) + sop;
 262                         if (p >= _pool + _poolsize) {
 263                                 p = _pool;
 264                                 if (SEGSIZ < 0) consolidate_ptr (p);
 265                         }
 266                 }
 267         }
 268 }
 269 #undef SEGSIZ
 270
 271 void
 272 ReallocPool::_free (void *ptr) {
 273         poolsize_t *in = (poolsize_t*) ptr;
 274         --in;
 275         *in = -*in; // mark as free
 276         //_mru = p + ss;
 277         STATS_used (*in);
 278 }
 279
 280 void
 281 ReallocPool::_shrink (void *ptr, size_t newsize) {
 282         poolsize_t *in = (poolsize_t*) ptr;
 283         --in;
 284         const poolsize_t avail = *in;
 285         const poolsize_t ss = newsize + sizeof(poolsize_t);
 286         if (avail <= ss) {
 287                 return; // can't shrink
 288         }
 289         const poolsize_t sp = (poolsize_t)newsize;
 290         STATS_used (newsize - avail);
 291         *in = sp; // set new size
 292         char *p = (char*) in;
 293         *((poolsize_t*)(p + ss)) = ss - avail; // mark free space after.
 294         //_mru = p + ss;
 295 }
 296
 297 size_t
 298 ReallocPool::_asize (void *ptr) {
 299         if (ptr == 0) return 0;
 300         poolsize_t *in = (poolsize_t*) ptr;
 301         --in;
 302         return (*in);
 303 }
 304
 305
 306 /** STATS **/
 307
 308 void
 309 ReallocPool::printstats ()
 310 {
 311 #ifdef RAP_WITH_SEGMENT_STATS
 312         printf ("ReallocPool '%s': used: %ld (%.1f%%) (max: %ld), free: %ld [bytes]\n"
 313                         "|| segments: cur: %ld (max: %ld), largest-used: %ld, largest-free: %ld\n",
 314                         _name.c_str(),
 315                         _cur_allocated, _cur_allocated * 100.f / _poolsize, _max_allocated, _cur_avail,
 316                         _seg_cur_count, _seg_max_count, _seg_max_used, _seg_max_avail);
 317 #elif defined RAP_WITH_CALL_STATS
 318         printf ("ReallocPool '%s':\n", _name.c_str());
 319 #endif
 320 #ifdef RAP_WITH_CALL_STATS
 321                 printf("|| malloc(): %ld, free(): %ld, realloc()+:%ld, realloc()-: %ld NOOP:%ld OOM:%ld\n",
 322                         _n_alloc, _n_free, _n_grow, _n_shrink, _n_noop, _n_oom);
 323                 printf("|| used: %ld / %ld, max: %ld (%.1f%%)\n",
 324                                 _cur_used, _poolsize,
 325                                 _max_used, 100.f *_max_used / _poolsize);
 326 #endif
 327 #ifdef RAP_WITH_HISTOGRAM
 328                 printf("--- malloc()\n");
 329                 print_histogram (_hist_alloc);
 330                 printf("--- realloc()/grow-to\n");
 331                 print_histogram (_hist_grow);
 332                 printf("--- realloc()/shrink-to\n");
 333                 print_histogram (_hist_shrink);
 334                 printf("--- free() histogram\n");
 335                 print_histogram (_hist_free);
 336                 printf("--------------------\n");
 337 #endif
 338 }
 339
 340 void
 341 ReallocPool::dumpsegments ()
 342 {
 343         char *p = _pool;
 344         const poolsize_t sop = sizeof(poolsize_t);
 345         poolsize_t *in = (poolsize_t*) p;
 346         unsigned int traversed = 0;
 347 #ifdef RAP_WITH_CALL_STATS
 348         size_t used = 0;
 349 #endif
 350         printf ("<<<<< %s\n", _name.c_str());
 351         while (1) {
 352                 if ((*in) > 0) {
 353                         printf ("0x%08x used %4d\n", traversed, *in);
 354                         printf ("0x%08x   data %p\n", traversed + sop , p + sop);
 355                         traversed += *in + sop;
 356                         p += *in + sop;
 357 #ifdef RAP_WITH_CALL_STATS
 358                         used += *in;
 359 #endif
 360                 } else if ((*in) < 0) {
 361                         printf ("0x%08x free %4d [+%d]\n", traversed, -*in, sop);
 362                         traversed += -*in + sop;
 363                         p += -*in + sop;
 364                 } else {
 365                         printf ("0x%08x Corrupt!\n", traversed);
 366                         break;
 367                 }
 368                 in = (poolsize_t*) p;
 369                 if (p == _pool + _poolsize) {
 370                         printf ("%08x end\n", traversed);
 371                         break;
 372                 }
 373                 if (p > _pool + _poolsize) {
 374                         printf ("%08x Beyond End!\n", traversed);
 375                         break;
 376                 }
 377         }
 378 #ifdef RAP_WITH_CALL_STATS
 379         ASSERT (_cur_used == used);
 380 #endif
 381         printf (">>>>>\n");
 382 }
 383
 384 #ifdef RAP_WITH_SEGMENT_STATS
 385 void
 386 ReallocPool::collect_segment_stats ()
 387 {
 388         char *p = _pool;
 389         poolsize_t *in = (poolsize_t*) p;
 390
 391         _cur_allocated = _cur_avail = 0;
 392         _seg_cur_count = _seg_max_avail = _seg_max_used = 0;
 393
 394         while (1) {
 395                 ++_seg_cur_count;
 396                 if ((*in) > 0) {
 397                         _cur_allocated += *in;
 398                         p += *in;
 399                         if (*in > (poolsize_t)_seg_max_used) {
 400                                 _seg_max_used = *in;
 401                         }
 402                 } else {
 403                         _cur_avail += -*in;
 404                         p += -*in;
 405                         if (-*in > (poolsize_t)_seg_max_avail) {
 406                                 _seg_max_avail = -*in;
 407                         }
 408                 }
 409                 p += sizeof(poolsize_t);
 410                 in = (poolsize_t*) p;
 411                 if (p == _pool + _poolsize) {
 412                         break;
 413                 }
 414         }
 415         _seg_cur_count = _seg_cur_count;
 416
 417         if (_cur_allocated > _max_allocated) {
 418                 _max_allocated = _cur_allocated;
 419         }
 420         if (_seg_cur_count > _seg_max_count) {
 421                 _seg_max_count = _seg_cur_count;
 422         }
 423 }
 424 #endif
 425
 426 #ifdef RAP_WITH_HISTOGRAM
 427 void
 428 ReallocPool::print_histogram (size_t const * const histogram) const
 429 {
 430         size_t maxhist = 0;
 431         for (int i = 0; i < RAP_WITH_HISTOGRAM; ++i) {
 432                 if (histogram[i] > maxhist) maxhist = histogram[i];
 433         }
 434         const int termwidth = 50;
 435 #ifdef RAP_BLOCKSIZE
 436         const int fact = RAP_BLOCKSIZE + 1;
 437 #endif
 438         if (maxhist > 0) for (int i = 0; i < RAP_WITH_HISTOGRAM; ++i) {
 439                 if (histogram[i] == 0) { continue; }
 440                 if (i == RAP_WITH_HISTOGRAM -1 ) {
 441 #ifdef RAP_BLOCKSIZE
 442                         printf("     > %4d: %7lu ", i * fact, histogram[i]);
 443 #else
 444                         printf(">%4d:%7lu ", i * fact, histogram[i]);
 445 #endif
 446                 } else {
 447 #ifdef RAP_BLOCKSIZE
 448                         printf("%4d .. %4d: %7lu ", i * fact, (i + 1) * fact -1, histogram[i]);
 449 #else
 450                         printf("%4d: %7lu ", i * fact, (i + 1) * fact -1 , histogram[i]);
 451 #endif
 452                 }
 453                 int bar_width = (histogram[i] * termwidth ) / maxhist;
 454                 if (bar_width == 0 && histogram[i] > 0) bar_width = 1;
 455                 for (int j = 0; j < bar_width; ++j) printf("#");
 456                 printf("\n");
 457         }
 458 }
 459
 460 unsigned int
 461 ReallocPool::hist_bin (size_t s) const {
 462 #ifdef RAP_BLOCKSIZE
 463         s = (s + RAP_BLOCKSIZE) & (~RAP_BLOCKSIZE);
 464         s /= (RAP_BLOCKSIZE + 1);
 465 #endif
 466         if (s > RAP_WITH_HISTOGRAM - 1) s = RAP_WITH_HISTOGRAM - 1;
 467         return s;
 468 }
 469 #endif