nel/src/misc/buf_fifo.cpp

   1 // NeL - MMORPG Framework <http://dev.ryzom.com/projects/nel/>
   2 // Copyright (C) 2010  Winch Gate Property Limited
   3 //
   4 // This source file has been modified by the following contributors:
   5 // Copyright (C) 2016  Jan BOON (Kaetemi) <jan.boon@kaetemi.be>
   6 //
   7 // This program is free software: you can redistribute it and/or modify
   8 // it under the terms of the GNU Affero General Public License as
   9 // published by the Free Software Foundation, either version 3 of the
  10 // License, or (at your option) any later version.
  11 //
  12 // This program is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU Affero General Public License for more details.
  16 //
  17 // You should have received a copy of the GNU Affero General Public License
  18 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  19
  20 #include "stdmisc.h"
  21 #include "nel/misc/time_nl.h"
  22 #include "nel/misc/command.h"
  23 #include "nel/misc/buf_fifo.h"
  24
  25 using namespace std;
  26
  27 #define DEBUG_FIFO 0
  28
  29 // if 0, don't stat the time of different function
  30 #define STAT_FIFO 1
  31
  32 #ifdef DEBUG_NEW
  33         #define new DEBUG_NEW
  34 #endif
  35
  36 namespace NLMISC {
  37
  38 #ifdef BUFFIFO_TRACK_ALL_BUFFERS
  39 CBufFIFO::TAllBuffers           CBufFIFO::_AllBuffers;
  40 #endif
  41
  42
  43 CBufFIFO::CBufFIFO() : _Buffer(NULL), _BufferSize(0), _Empty(true), _Head(NULL), _Tail(NULL), _Rewinder(NULL)
  44 {
  45 #ifdef BUFFIFO_TRACK_ALL_BUFFERS
  46         _AllBuffers.insert(this);
  47 #endif
  48
  49         // reset statistic
  50         _BiggestBlock = 0;
  51         _SmallestBlock = 999999999;
  52         _BiggestBuffer = 0;
  53         _SmallestBuffer = 999999999;
  54         _Pushed = 0;
  55         _Fronted = 0;
  56         _Resized = 0;
  57         _PushedTime = 0;
  58         _FrontedTime = 0;
  59         _ResizedTime = 0;
  60 }
  61
  62 CBufFIFO::~CBufFIFO()
  63 {
  64 #ifdef BUFFIFO_TRACK_ALL_BUFFERS
  65         _AllBuffers.erase(this);
  66 #endif
  67
  68         if (_Buffer != NULL)
  69         {
  70                 delete []_Buffer;
  71 #if DEBUG_FIFO
  72                 nldebug("%p delete", this);
  73 #endif
  74         }
  75 }
  76
  77 void     CBufFIFO::push (const uint8 *buffer, uint32 s)
  78 {
  79         // if the buffer is more than 1 meg, there s surely a problem, no?
  80 //      nlassert( buffer.size() < 1000000 ); // size check in debug mode
  81
  82 #if STAT_FIFO
  83         TTicks before = CTime::getPerformanceTime();
  84 #endif
  85
  86 #if DEBUG_FIFO
  87         nldebug("%p push(%d)", this, s);
  88 #endif
  89
  90         nlassert(s > 0 && s < pow(2.0, static_cast<double>(sizeof(TFifoSize)*8)));
  91
  92         // stat code
  93         if (s > _BiggestBlock) _BiggestBlock = s;
  94         if (s < _SmallestBlock) _SmallestBlock = s;
  95         _Pushed++;
  96
  97         while (!canFit (s + sizeof (TFifoSize)))
  98         {
  99                 resize(_BufferSize * 2);
 100         }
 101
 102         *(TFifoSize *)_Head = s;
 103         _Head += sizeof(TFifoSize);
 104
 105         CFastMem::memcpy(_Head, buffer, s);
 106
 107         _Head += s;
 108
 109         _Empty = false;
 110
 111 #if STAT_FIFO
 112         // stat code
 113         TTicks after = CTime::getPerformanceTime();
 114         _PushedTime += after - before;
 115 #endif
 116
 117 #if DEBUG_FIFO
 118         display ();
 119 #endif
 120 }
 121
 122 void CBufFIFO::push(const std::vector<uint8> &buffer1, const std::vector<uint8> &buffer2)
 123 {
 124 #if STAT_FIFO
 125         TTicks before = CTime::getPerformanceTime();
 126 #endif
 127
 128         TFifoSize s = (TFifoSize)(buffer1.size() + buffer2.size());
 129
 130 #if DEBUG_FIFO
 131         nldebug("%p push2(%d)", this, s);
 132 #endif
 133
 134         nlassert((buffer1.size() + buffer2.size ()) > 0 && (buffer1.size() + buffer2.size ()) < pow(2.0, static_cast<double>(sizeof(TFifoSize)*8)));
 135
 136         // avoid too big fifo
 137         if (this->size() > 10000000)
 138         {
 139                 throw Exception ("CBufFIFO::push(): stack full (more than 10mb)");
 140         }
 141
 142
 143         // stat code
 144         if (s > _BiggestBlock) _BiggestBlock = s;
 145         if (s < _SmallestBlock) _SmallestBlock = s;
 146
 147         _Pushed++;
 148
 149         // resize while the buffer is enough big to accept the block
 150         while (!canFit (s + sizeof (TFifoSize)))
 151         {
 152                 resize(_BufferSize * 2);
 153         }
 154
 155         // store the size of the block
 156         *(TFifoSize *)_Head = s;
 157         _Head += sizeof(TFifoSize);
 158
 159         // store the block itself
 160         CFastMem::memcpy(_Head, &(buffer1[0]), buffer1.size());
 161         CFastMem::memcpy(_Head + buffer1.size(), &(buffer2[0]), buffer2.size());
 162         _Head += s;
 163
 164         _Empty = false;
 165
 166 #if STAT_FIFO
 167         // stat code
 168         TTicks after = CTime::getPerformanceTime();
 169         _PushedTime += after - before;
 170 #endif
 171
 172 #if DEBUG_FIFO
 173         display ();
 174 #endif
 175 }
 176
 177 void CBufFIFO::pop ()
 178 {
 179         if (empty ())
 180         {
 181                 nlwarning("BF: Try to pop an empty fifo!");
 182                 return;
 183         }
 184
 185         if (_Rewinder != NULL && _Tail == _Rewinder)
 186         {
 187 #if DEBUG_FIFO
 188                 nldebug("%p pop rewind!", this);
 189 #endif
 190
 191                 // need to rewind
 192                 _Tail = _Buffer;
 193                 _Rewinder = NULL;
 194         }
 195
 196         TFifoSize s = *(TFifoSize *)_Tail;
 197
 198 #if DEBUG_FIFO
 199         nldebug("%p pop(%d)", this, s);
 200 #endif
 201
 202 #ifdef NL_DEBUG
 203         // clear the message to be sure user doesn't use it anymore
 204         memset (_Tail, '-', s + sizeof (TFifoSize));
 205 #endif
 206
 207         _Tail += s + sizeof (TFifoSize);
 208
 209         if (_Tail == _Head) _Empty = true;
 210
 211 #if DEBUG_FIFO
 212         display ();
 213 #endif
 214 }
 215
 216 uint8 CBufFIFO::frontLast ()
 217 {
 218         uint8   *tail = _Tail;
 219
 220         if (empty ())
 221         {
 222                 nlwarning("BF: Try to get the front of an empty fifo!");
 223                 return 0;
 224         }
 225
 226         if (_Rewinder != NULL && tail == _Rewinder)
 227         {
 228 #if DEBUG_FIFO
 229                 nldebug("%p front rewind!", this);
 230 #endif
 231
 232                 // need to rewind
 233                 tail = _Buffer;
 234         }
 235
 236         TFifoSize s = *(TFifoSize *)tail;
 237
 238 #if DEBUG_FIFO
 239         nldebug("%p frontLast() returns %d ", this, s, *(tail+sizeof(TFifoSize)+size-1));
 240 #endif
 241
 242         return *(tail+sizeof(TFifoSize)+s-1);
 243 }
 244
 245
 246 void CBufFIFO::front (vector<uint8> &buffer)
 247 {
 248         uint8 *tmpbuffer;
 249         uint32 s;
 250
 251         buffer.clear ();
 252
 253         front (tmpbuffer, s);
 254
 255         buffer.resize (s);
 256
 257         CFastMem::memcpy (&(buffer[0]), tmpbuffer, s);
 258
 259 /*      TTicks before = CTime::getPerformanceTime ();
 260
 261         uint8   *tail = _Tail;
 262
 263         buffer.clear ();
 264
 265         if (empty ())
 266         {
 267                 nlwarning("Try to get the front of an empty fifo!");
 268                 return;
 269         }
 270
 271         _Fronted++;
 272
 273         if (_Rewinder != NULL && tail == _Rewinder)
 274         {
 275 #if DEBUG_FIFO
 276                 nldebug("%p front rewind!", this);
 277 #endif
 278
 279                 // need to rewind
 280                 tail = _Buffer;
 281         }
 282
 283         TFifoSize size = *(TFifoSize *)tail;
 284
 285 #if DEBUG_FIFO
 286         nldebug("%p front(%d)", this, size);
 287 #endif
 288
 289         tail += sizeof (TFifoSize);
 290
 291         buffer.resize (size);
 292
 293         CFastMem::memcpy (&(buffer[0]), tail, size);
 294
 295         // stat code
 296         TTicks after = CTime::getPerformanceTime ();
 297         _FrontedTime += after - before;
 298
 299 #if DEBUG_FIFO
 300         display ();
 301 #endif
 302 */}
 303
 304
 305 void CBufFIFO::front (NLMISC::CMemStream &buffer)
 306 {
 307         uint8 *tmpbuffer;
 308         uint32 s;
 309
 310         buffer.clear ();
 311
 312         front (tmpbuffer, s);
 313
 314         buffer.fill (tmpbuffer, s);
 315
 316         /*
 317         TTicks before = CTime::getPerformanceTime ();
 318
 319         uint8   *tail = _Tail;
 320
 321         buffer.clear ();
 322
 323         if (empty ())
 324         {
 325                 nlwarning("Try to get the front of an empty fifo!");
 326                 return;
 327         }
 328
 329         _Fronted++;
 330
 331         if (_Rewinder != NULL && tail == _Rewinder)
 332         {
 333 #if DEBUG_FIFO
 334                 nldebug("%p front rewind!", this);
 335 #endif
 336
 337                 // need to rewind
 338                 tail = _Buffer;
 339         }
 340
 341         TFifoSize size = *(TFifoSize *)tail;
 342
 343 #if DEBUG_FIFO
 344         nldebug("%p front(%d)", this, size);
 345 #endif
 346
 347         tail += sizeof (TFifoSize);
 348
 349         //buffer.resize (size);
 350         //CFastMem::memcpy (&(buffer[0]), tail, size);
 351
 352         buffer.fill (tail, size);
 353
 354         // stat code
 355         TTicks after = CTime::getPerformanceTime ();
 356         _FrontedTime += after - before;
 357
 358 #if DEBUG_FIFO
 359         display ();
 360 #endif*/
 361 }
 362
 363 void CBufFIFO::front (uint8 *&buffer, uint32 &s)
 364 {
 365 #if STAT_FIFO
 366         TTicks before = CTime::getPerformanceTime ();
 367 #endif
 368
 369         uint8   *tail = _Tail;
 370
 371         if (empty ())
 372         {
 373                 nlwarning("BF: Try to get the front of an empty fifo!");
 374                 return;
 375         }
 376
 377         _Fronted++;
 378
 379         if (_Rewinder != NULL && tail == _Rewinder)
 380         {
 381 #if DEBUG_FIFO
 382                 nldebug("%p front rewind!", this);
 383 #endif
 384
 385                 // need to rewind
 386                 tail = _Buffer;
 387         }
 388
 389         s = *(TFifoSize *)tail;
 390
 391 #if DEBUG_FIFO
 392         nldebug("%p front(%d)", this, s);
 393 #endif
 394
 395         tail += sizeof (TFifoSize);
 396
 397 #if STAT_FIFO
 398         // stat code
 399         TTicks after = CTime::getPerformanceTime ();
 400         _FrontedTime += after - before;
 401 #endif
 402
 403 #if DEBUG_FIFO
 404         display ();
 405 #endif
 406
 407         buffer = tail;
 408 }
 409
 410
 411
 412 void CBufFIFO::clear ()
 413 {
 414         _Tail = _Head = _Buffer;
 415         _Rewinder = NULL;
 416         _Empty = true;
 417 }
 418
 419 uint32 CBufFIFO::size ()
 420 {
 421         if (empty ())
 422         {
 423                 return 0;
 424         }
 425         else if (_Head == _Tail)
 426         {
 427                 // buffer is full
 428                 if (_Rewinder == NULL)
 429                         return _BufferSize;
 430                 else
 431                         return (uint32)(_Rewinder - _Buffer);
 432         }
 433         else if (_Head > _Tail)
 434         {
 435                 return (uint32)(_Head - _Tail);
 436         }
 437         else if (_Head < _Tail)
 438         {
 439                 nlassert (_Rewinder != NULL);
 440                 return (uint32)((_Rewinder - _Tail) + (_Head - _Buffer));
 441         }
 442         nlstop;
 443         return 0;
 444 }
 445
 446 void CBufFIFO::resize (uint32 s)
 447 {
 448 #if STAT_FIFO
 449         TTicks before = CTime::getPerformanceTime();
 450 #endif
 451
 452         if (s == 0) s = 100;
 453
 454 #if DEBUG_FIFO
 455         nldebug("%p resize(%d)", this, s);
 456 #endif
 457
 458         if (s > _BiggestBuffer) _BiggestBuffer = s;
 459         if (s < _SmallestBuffer) _SmallestBuffer = s;
 460
 461         _Resized++;
 462
 463         uint32 UsedSize = CBufFIFO::size();
 464
 465         // create a new array and copy the old in the new one
 466         if (s < _BufferSize && UsedSize > s)
 467         {
 468                 // problem, we don't have enough room for putting data => don't do it
 469                 nlwarning("BF: Can't resize the FIFO because there's not enough room in the new wanted buffer (%d bytes needed at least)", UsedSize);
 470                 return;
 471         }
 472
 473         uint8 *NewBuffer = new uint8[s];
 474         if (NewBuffer == NULL)
 475         {
 476                 nlerror("Not enough memory to resize the FIFO to %u bytes", s);
 477         }
 478 #ifdef NL_DEBUG
 479         // clear the message to be sure user doesn't use it anymore
 480         memset (NewBuffer, '-', s);
 481 #endif
 482
 483 #if DEBUG_FIFO
 484         nldebug("%p new %d bytes", this, s);
 485 #endif
 486
 487         // copy the old buffer to the new one
 488         // if _Tail == _Head => empty fifo, don't copy anything
 489         if (!empty())
 490         {
 491                 if (_Tail < _Head)
 492                 {
 493                         CFastMem::memcpy (NewBuffer, _Tail, UsedSize);
 494                 }
 495                 else if (_Tail >= _Head)
 496                 {
 497                         nlassert (_Rewinder != NULL);
 498
 499                         uint size1 = (uint)(_Rewinder - _Tail);
 500                         CFastMem::memcpy (NewBuffer, _Tail, size1);
 501                         uint size2 = (uint)(_Head - _Buffer);
 502                         CFastMem::memcpy (NewBuffer + size1, _Buffer, size2);
 503
 504                         nlassert (size1+size2==UsedSize);
 505                 }
 506         }
 507
 508         // resync the circular pointer
 509         // Warning: don't invert these 2 lines position or it ll not work
 510         _Tail = NewBuffer;
 511         _Head = NewBuffer + UsedSize;
 512         _Rewinder = NULL;
 513
 514         // delete old buffer if needed
 515         if (_Buffer != NULL)
 516         {
 517                 delete []_Buffer;
 518 #if DEBUG_FIFO
 519                 nldebug ("delete", this);
 520 #endif
 521         }
 522
 523         // affect new buffer
 524         _Buffer = NewBuffer;
 525         _BufferSize = s;
 526
 527 #if STAT_FIFO
 528         TTicks after = CTime::getPerformanceTime();
 529         _ResizedTime += after - before;
 530 #endif
 531
 532 #if DEBUG_FIFO
 533         display ();
 534 #endif
 535 }
 536
 537 void CBufFIFO::displayStats (CLog *log)
 538 {
 539         log->displayNL ("%p CurrentQueueSize: %d, TotalQueueSize: %d", this, size(), _BufferSize);
 540         log->displayNL ("%p InQueue: %d", this, _Pushed - _Fronted);
 541
 542         log->displayNL ("%p BiggestBlock: %d, SmallestBlock: %d", this, _BiggestBlock, _SmallestBlock);
 543         log->displayNL ("%p BiggestBuffer: %d, SmallestBuffer: %d", this, _BiggestBuffer, _SmallestBuffer);
 544         log->displayNL ("%p Pushed: %d, PushedTime: total %" NL_I64 "d ticks, mean %f ticks", this, _Pushed, _PushedTime, (_Pushed>0?(double)(sint64)_PushedTime / (double)_Pushed:0.0));
 545         log->displayNL ("%p Fronted: %d, FrontedTime: total %" NL_I64 "d ticks, mean %f ticks", this, _Fronted, _FrontedTime, (_Fronted>0?(double)(sint64)_FrontedTime / (double)_Fronted:0.0));
 546         log->displayNL ("%p Resized: %d, ResizedTime: total %" NL_I64 "d ticks, mean %f ticks", this, _Resized, _ResizedTime, (_Resized>0?(double)(sint64)_ResizedTime / (double)_Resized:0.0));
 547 }
 548
 549 void CBufFIFO::display ()
 550 {
 551         int s = 64;
 552         int gran = s/30;
 553
 554         char str[1024];
 555
 556         smprintf(str, 1024, "%p %p (%5d %5d) %p %p %p ", this, _Buffer, _BufferSize, CBufFIFO::size(), _Rewinder, _Tail, _Head);
 557
 558         int i;
 559         for (i = 0; i < (sint32) _BufferSize; i+= gran)
 560         {
 561                 uint8 *pos = _Buffer + i;
 562                 if (_Tail >= pos && _Tail < pos + gran)
 563                 {
 564                         if (_Head >= pos && _Head < pos + gran)
 565                         {
 566                                 if (_Rewinder != NULL && _Rewinder >= pos && _Rewinder < pos + gran)
 567                                 {
 568                                         strncat (str, "*", 1);
 569                                 }
 570                                 else
 571                                 {
 572                                         strncat (str, "@", 1);
 573                                 }
 574                         }
 575                         else
 576                         {
 577                                 strncat (str, "T", 1);
 578                         }
 579                 }
 580                 else if (_Head >= pos && _Head < pos + gran)
 581                 {
 582                         strncat (str, "H", 1);
 583                 }
 584                 else if (_Rewinder != NULL && _Rewinder >= pos && _Rewinder < pos + gran)
 585                 {
 586                         strncat (str, "R", 1);
 587                 }
 588                 else
 589                 {
 590                         if (strlen(str) < 1023)
 591                         {
 592                                 uint32 p = (uint32)strlen(str);
 593                                 if (isprint(*pos))
 594                                         str[p] = *pos;
 595                                 else
 596                                         str[p] = '$';
 597
 598                                 str[p+1] = '\0';
 599                         }
 600                 }
 601         }
 602
 603         for (; i < s; i+= gran)
 604         {
 605                 strncat (str, " ", 1);
 606         }
 607 #ifdef NL_DEBUG
 608         strncat (str, "\n", 1);
 609 #else
 610         strncat (str, "\r", 1);
 611 #endif
 612         DebugLog->display (str);
 613 }
 614
 615 bool CBufFIFO::canFit (uint32 s)
 616 {
 617         if (_Tail == _Head)
 618         {
 619                 if (empty())
 620                 {
 621                         // is the buffer large enough?
 622                         if (_BufferSize >= s)
 623                         {
 624                                 // reset the pointer
 625 #if DEBUG_FIFO
 626                                 nldebug("%p reset tail and head", this);
 627 #endif
 628                                 _Head = _Tail = _Buffer;
 629                                 return true;
 630                         }
 631                         else
 632                         {
 633                                 // buffer not big enough
 634 #if DEBUG_FIFO
 635                                 nldebug("%p buffer full buffersize<size", this);
 636 #endif
 637                                 return false;
 638                         }
 639                 }
 640                 else
 641                 {
 642                         // buffer full
 643 #if DEBUG_FIFO
 644                         nldebug("%p buffer full h=t", this);
 645 #endif
 646                         return false;
 647                 }
 648         }
 649         else if (_Tail < _Head)
 650         {
 651                 if (_Buffer + _BufferSize - _Head >= (sint32) s)
 652                 {
 653                         // can fit after _Head
 654 #if DEBUG_FIFO
 655                         nldebug("%p fit after", this);
 656 #endif
 657                         return true;
 658                 }
 659                 else if (_Tail - _Buffer >= (sint32) s)
 660                 {
 661                         // can fit at the beginning
 662 #if DEBUG_FIFO
 663                         nldebug("%p fit at beginning", this);
 664 #endif
 665                         _Rewinder = _Head;
 666 #if DEBUG_FIFO
 667                         nldebug("%p set the rewinder", this);
 668 #endif
 669                         _Head = _Buffer;
 670                         return true;
 671                 }
 672                 else
 673                 {
 674                         // can't fit
 675 #if DEBUG_FIFO
 676                         nldebug("%p no room t<h", this);
 677 #endif
 678                         return false;
 679                 }
 680         }
 681         else // the last case is : if (_Tail > _Head)
 682         {
 683                 if (_Tail - _Head >= (sint32) s)
 684                 {
 685 #if DEBUG_FIFO
 686                         nldebug("%p fit t>h", this);
 687 #endif
 688                         return true;
 689                 }
 690                 else
 691                 {
 692 #if DEBUG_FIFO
 693                         nldebug("%p no room t>h", this);
 694 #endif
 695                         return false;
 696                 }
 697         }
 698 }
 699
 700 #ifdef BUFFIFO_TRACK_ALL_BUFFERS
 701 NLMISC_CATEGORISED_COMMAND(misc, dumpAllBuffers, "Dump all the fifo buffer", "no args")
 702 {
 703         log.displayNL("Dumping %u FIFO buffers :", CBufFIFO::_AllBuffers.size());
 704
 705         CBufFIFO::TAllBuffers::iterator first(CBufFIFO::_AllBuffers.begin()), last(CBufFIFO::_AllBuffers.end());
 706         for (; first != last; ++first)
 707         {
 708                 CBufFIFO *buf = *first;
 709
 710                 log.displayNL("Dumping buffer %p:", buf);
 711
 712                 buf->displayStats(&log);
 713         }
 714
 715         return true;
 716 }
 717 #endif
 718
 719
 720 } // NLMISC