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