code.delx.au - pulseaudio/blob - src/pulsecore/memblockq.c

   1 /* $Id$ */
   2
   3 /***
   4   This file is part of PulseAudio.
   5
   6   Copyright 2004-2006 Lennart Poettering
   7
   8   PulseAudio is free software; you can redistribute it and/or modify
   9   it under the terms of the GNU Lesser General Public License as published
  10   by the Free Software Foundation; either version 2 of the License,
  11   or (at your option) any later version.
  12
  13   PulseAudio is distributed in the hope that it will be useful, but
  14   WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16   General Public License for more details.
  17
  18   You should have received a copy of the GNU Lesser General Public License
  19   along with PulseAudio; if not, write to the Free Software
  20   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
  21   USA.
  22 ***/
  23
  24 #ifdef HAVE_CONFIG_H
  25 #include <config.h>
  26 #endif
  27
  28 #include <sys/time.h>
  29 #include <time.h>
  30 #include <stdio.h>
  31 #include <stdlib.h>
  32 #include <string.h>
  33
  34 #include <pulse/xmalloc.h>
  35
  36 #include <pulsecore/log.h>
  37 #include <pulsecore/mcalign.h>
  38 #include <pulsecore/macro.h>
  39 #include <pulsecore/flist.h>
  40
  41 #include "memblockq.h"
  42
  43 struct list_item {
  44     struct list_item *next, *prev;
  45     int64_t index;
  46     pa_memchunk chunk;
  47 };
  48
  49 PA_STATIC_FLIST_DECLARE(list_items, 0, pa_xfree);
  50
  51 struct pa_memblockq {
  52     struct list_item *blocks, *blocks_tail;
  53     unsigned n_blocks;
  54     size_t maxlength, tlength, base, prebuf, minreq;
  55     int64_t read_index, write_index;
  56     pa_bool_t in_prebuf;
  57     pa_memblock *silence;
  58     pa_mcalign *mcalign;
  59     int64_t missing;
  60     size_t requested;
  61 };
  62
  63 pa_memblockq* pa_memblockq_new(
  64         int64_t idx,
  65         size_t maxlength,
  66         size_t tlength,
  67         size_t base,
  68         size_t prebuf,
  69         size_t minreq,
  70         pa_memblock *silence) {
  71
  72     pa_memblockq* bq;
  73
  74     pa_assert(base > 0);
  75     pa_assert(maxlength >= base);
  76
  77     bq = pa_xnew(pa_memblockq, 1);
  78     bq->blocks = bq->blocks_tail = NULL;
  79     bq->n_blocks = 0;
  80
  81     bq->base = base;
  82     bq->read_index = bq->write_index = idx;
  83
  84     pa_log_debug("memblockq requested: maxlength=%lu, tlength=%lu, base=%lu, prebuf=%lu, minreq=%lu",
  85         (unsigned long) maxlength, (unsigned long) tlength, (unsigned long) base, (unsigned long) prebuf, (unsigned long) minreq);
  86
  87     bq->maxlength = ((maxlength+base-1)/base)*base;
  88     pa_assert(bq->maxlength >= base);
  89
  90     bq->tlength = ((tlength+base-1)/base)*base;
  91     if (bq->tlength <= 0 || bq->tlength > bq->maxlength)
  92         bq->tlength = bq->maxlength;
  93
  94     bq->prebuf = (prebuf == (size_t) -1) ? bq->tlength/2 : prebuf;
  95     bq->prebuf = ((bq->prebuf+base-1)/base)*base;
  96     if (bq->prebuf > bq->maxlength)
  97         bq->prebuf = bq->maxlength;
  98
  99     bq->minreq = (minreq/base)*base;
 100
 101     if (bq->minreq > bq->tlength - bq->prebuf)
 102         bq->minreq = bq->tlength - bq->prebuf;
 103
 104     if (!bq->minreq)
 105         bq->minreq = 1;
 106
 107     pa_log_debug("memblockq sanitized: maxlength=%lu, tlength=%lu, base=%lu, prebuf=%lu, minreq=%lu",
 108         (unsigned long)bq->maxlength, (unsigned long)bq->tlength, (unsigned long)bq->base, (unsigned long)bq->prebuf, (unsigned long)bq->minreq);
 109
 110     bq->in_prebuf = bq->prebuf > 0;
 111     bq->silence = silence ? pa_memblock_ref(silence) : NULL;
 112     bq->mcalign = NULL;
 113
 114     bq->missing = bq->tlength;
 115     bq->requested = 0;
 116
 117     return bq;
 118 }
 119
 120 void pa_memblockq_free(pa_memblockq* bq) {
 121     pa_assert(bq);
 122
 123     pa_memblockq_flush(bq);
 124
 125     if (bq->silence)
 126         pa_memblock_unref(bq->silence);
 127
 128     if (bq->mcalign)
 129         pa_mcalign_free(bq->mcalign);
 130
 131     pa_xfree(bq);
 132 }
 133
 134 static void drop_block(pa_memblockq *bq, struct list_item *q) {
 135     pa_assert(bq);
 136     pa_assert(q);
 137
 138     pa_assert(bq->n_blocks >= 1);
 139
 140     if (q->prev)
 141         q->prev->next = q->next;
 142     else
 143         bq->blocks = q->next;
 144
 145     if (q->next)
 146         q->next->prev = q->prev;
 147     else
 148         bq->blocks_tail = q->prev;
 149
 150     pa_memblock_unref(q->chunk.memblock);
 151
 152     if (pa_flist_push(PA_STATIC_FLIST_GET(list_items), q) < 0)
 153         pa_xfree(q);
 154
 155     bq->n_blocks--;
 156 }
 157
 158 static pa_bool_t can_push(pa_memblockq *bq, size_t l) {
 159     int64_t end;
 160
 161     pa_assert(bq);
 162
 163     if (bq->read_index > bq->write_index) {
 164         size_t d =  bq->read_index - bq->write_index;
 165
 166         if (l > d)
 167             l -= d;
 168         else
 169             return TRUE;
 170     }
 171
 172     end = bq->blocks_tail ? bq->blocks_tail->index + bq->blocks_tail->chunk.length : 0;
 173
 174     /* Make sure that the list doesn't get too long */
 175     if (bq->write_index + (int64_t)l > end)
 176         if (bq->write_index + l - bq->read_index > bq->maxlength)
 177             return FALSE;
 178
 179     return TRUE;
 180 }
 181
 182 int pa_memblockq_push(pa_memblockq* bq, const pa_memchunk *uchunk) {
 183     struct list_item *q, *n;
 184     pa_memchunk chunk;
 185     int64_t old, delta;
 186
 187     pa_assert(bq);
 188     pa_assert(uchunk);
 189     pa_assert(uchunk->memblock);
 190     pa_assert(uchunk->length > 0);
 191     pa_assert(uchunk->index + uchunk->length <= pa_memblock_get_length(uchunk->memblock));
 192
 193     if (uchunk->length % bq->base)
 194         return -1;
 195
 196     if (!can_push(bq, uchunk->length))
 197         return -1;
 198
 199     old = bq->write_index;
 200     chunk = *uchunk;
 201
 202     if (bq->read_index > bq->write_index) {
 203
 204         /* We currently have a buffer underflow, we need to drop some
 205          * incoming data */
 206
 207         size_t d = bq->read_index - bq->write_index;
 208
 209         if (chunk.length > d) {
 210             chunk.index += d;
 211             chunk.length -= d;
 212             bq->write_index += d;
 213         } else {
 214             /* We drop the incoming data completely */
 215             bq->write_index += chunk.length;
 216             goto finish;
 217         }
 218     }
 219
 220     /* We go from back to front to look for the right place to add
 221      * this new entry. Drop data we will overwrite on the way */
 222
 223     q = bq->blocks_tail;
 224     while (q) {
 225
 226         if (bq->write_index >= q->index + (int64_t) q->chunk.length)
 227             /* We found the entry where we need to place the new entry immediately after */
 228             break;
 229         else if (bq->write_index + (int64_t) chunk.length <= q->index) {
 230             /* This entry isn't touched at all, let's skip it */
 231             q = q->prev;
 232         } else if (bq->write_index <= q->index &&
 233             bq->write_index + chunk.length >= q->index + q->chunk.length) {
 234
 235             /* This entry is fully replaced by the new entry, so let's drop it */
 236
 237             struct list_item *p;
 238             p = q;
 239             q = q->prev;
 240             drop_block(bq, p);
 241         } else if (bq->write_index >= q->index) {
 242             /* The write index points into this memblock, so let's
 243              * truncate or split it */
 244
 245             if (bq->write_index + chunk.length < q->index + q->chunk.length) {
 246
 247                 /* We need to save the end of this memchunk */
 248                 struct list_item *p;
 249                 size_t d;
 250
 251                 /* Create a new list entry for the end of thie memchunk */
 252                 if (!(p = pa_flist_pop(PA_STATIC_FLIST_GET(list_items))))
 253                     p = pa_xnew(struct list_item, 1);
 254
 255                 p->chunk = q->chunk;
 256                 pa_memblock_ref(p->chunk.memblock);
 257
 258                 /* Calculate offset */
 259                 d = bq->write_index + chunk.length - q->index;
 260                 pa_assert(d > 0);
 261
 262                 /* Drop it from the new entry */
 263                 p->index = q->index + d;
 264                 p->chunk.length -= d;
 265
 266                 /* Add it to the list */
 267                 p->prev = q;
 268                 if ((p->next = q->next))
 269                     q->next->prev = p;
 270                 else
 271                     bq->blocks_tail = p;
 272                 q->next = p;
 273
 274                 bq->n_blocks++;
 275             }
 276
 277             /* Truncate the chunk */
 278             if (!(q->chunk.length = bq->write_index - q->index)) {
 279                 struct list_item *p;
 280                 p = q;
 281                 q = q->prev;
 282                 drop_block(bq, p);
 283             }
 284
 285             /* We had to truncate this block, hence we're now at the right position */
 286             break;
 287         } else {
 288             size_t d;
 289
 290             pa_assert(bq->write_index + (int64_t)chunk.length > q->index &&
 291                    bq->write_index + (int64_t)chunk.length < q->index + (int64_t)q->chunk.length &&
 292                    bq->write_index < q->index);
 293
 294             /* The job overwrites the current entry at the end, so let's drop the beginning of this entry */
 295
 296             d = bq->write_index + chunk.length - q->index;
 297             q->index += d;
 298             q->chunk.index += d;
 299             q->chunk.length -= d;
 300
 301             q = q->prev;
 302         }
 303     }
 304
 305     if (q) {
 306         pa_assert(bq->write_index >=  q->index + (int64_t)q->chunk.length);
 307         pa_assert(!q->next || (bq->write_index + (int64_t)chunk.length <= q->next->index));
 308
 309         /* Try to merge memory blocks */
 310
 311         if (q->chunk.memblock == chunk.memblock &&
 312             q->chunk.index + (int64_t)q->chunk.length == chunk.index &&
 313             bq->write_index == q->index + (int64_t)q->chunk.length) {
 314
 315             q->chunk.length += chunk.length;
 316             bq->write_index += chunk.length;
 317             goto finish;
 318         }
 319     } else
 320         pa_assert(!bq->blocks || (bq->write_index + (int64_t)chunk.length <= bq->blocks->index));
 321
 322     if (!(n = pa_flist_pop(PA_STATIC_FLIST_GET(list_items))))
 323         n = pa_xnew(struct list_item, 1);
 324
 325     n->chunk = chunk;
 326     pa_memblock_ref(n->chunk.memblock);
 327     n->index = bq->write_index;
 328     bq->write_index += n->chunk.length;
 329
 330     n->next = q ? q->next : bq->blocks;
 331     n->prev = q;
 332
 333     if (n->next)
 334         n->next->prev = n;
 335     else
 336         bq->blocks_tail = n;
 337
 338     if (n->prev)
 339         n->prev->next = n;
 340     else
 341         bq->blocks = n;
 342
 343     bq->n_blocks++;
 344
 345 finish:
 346
 347     delta = bq->write_index - old;
 348
 349     if (delta >= bq->requested) {
 350         delta -= bq->requested;
 351         bq->requested = 0;
 352     } else {
 353         bq->requested -= delta;
 354         delta = 0;
 355     }
 356
 357     bq->missing -= delta;
 358
 359     return 0;
 360 }
 361
 362 static pa_bool_t memblockq_check_prebuf(pa_memblockq *bq) {
 363     pa_assert(bq);
 364
 365     if (bq->in_prebuf) {
 366
 367         if (pa_memblockq_get_length(bq) < bq->prebuf)
 368             return TRUE;
 369
 370         bq->in_prebuf = FALSE;
 371         return FALSE;
 372     } else {
 373
 374         if (bq->prebuf > 0 && bq->read_index >= bq->write_index) {
 375             bq->in_prebuf = TRUE;
 376             return TRUE;
 377         }
 378
 379         return FALSE;
 380     }
 381 }
 382
 383 int pa_memblockq_peek(pa_memblockq* bq, pa_memchunk *chunk) {
 384     pa_assert(bq);
 385     pa_assert(chunk);
 386
 387     /* We need to pre-buffer */
 388     if (memblockq_check_prebuf(bq))
 389         return -1;
 390
 391     /* Do we need to spit out silence? */
 392     if (!bq->blocks || bq->blocks->index > bq->read_index) {
 393
 394         size_t length;
 395
 396         /* How much silence shall we return? */
 397         length = bq->blocks ? bq->blocks->index - bq->read_index : 0;
 398
 399         /* We need to return silence, since no data is yet available */
 400         if (bq->silence) {
 401             chunk->memblock = pa_memblock_ref(bq->silence);
 402
 403             if (!length || length > pa_memblock_get_length(chunk->memblock))
 404                 length = pa_memblock_get_length(chunk->memblock);
 405
 406             chunk->length = length;
 407         } else {
 408
 409             /* If the memblockq is empty, return -1, otherwise return
 410              * the time to sleep */
 411             if (!bq->blocks)
 412                 return -1;
 413
 414             chunk->memblock = NULL;
 415             chunk->length = length;
 416         }
 417
 418         chunk->index = 0;
 419         return 0;
 420     }
 421
 422     /* Ok, let's pass real data to the caller */
 423     pa_assert(bq->blocks->index == bq->read_index);
 424
 425     *chunk = bq->blocks->chunk;
 426     pa_memblock_ref(chunk->memblock);
 427
 428     return 0;
 429 }
 430
 431 void pa_memblockq_drop(pa_memblockq *bq, size_t length) {
 432     int64_t old, delta;
 433     pa_assert(bq);
 434     pa_assert(length % bq->base == 0);
 435
 436     old = bq->read_index;
 437
 438     while (length > 0) {
 439
 440         /* Do not drop any data when we are in prebuffering mode */
 441         if (memblockq_check_prebuf(bq))
 442             break;
 443
 444         if (bq->blocks) {
 445             size_t d;
 446
 447             pa_assert(bq->blocks->index >= bq->read_index);
 448
 449             d = (size_t) (bq->blocks->index - bq->read_index);
 450
 451             if (d >= length) {
 452                 /* The first block is too far in the future */
 453
 454                 bq->read_index += length;
 455                 break;
 456             } else {
 457
 458                 length -= d;
 459                 bq->read_index += d;
 460             }
 461
 462             pa_assert(bq->blocks->index == bq->read_index);
 463
 464             if (bq->blocks->chunk.length <= length) {
 465                 /* We need to drop the full block */
 466
 467                 length -= bq->blocks->chunk.length;
 468                 bq->read_index += bq->blocks->chunk.length;
 469
 470                 drop_block(bq, bq->blocks);
 471             } else {
 472                 /* Only the start of this block needs to be dropped */
 473
 474                 bq->blocks->chunk.index += length;
 475                 bq->blocks->chunk.length -= length;
 476                 bq->blocks->index += length;
 477                 bq->read_index += length;
 478                 break;
 479             }
 480
 481         } else {
 482
 483             /* The list is empty, there's nothing we could drop */
 484             bq->read_index += length;
 485             break;
 486         }
 487     }
 488
 489     delta = bq->read_index - old;
 490     bq->missing += delta;
 491 }
 492
 493 int pa_memblockq_is_readable(pa_memblockq *bq) {
 494     pa_assert(bq);
 495
 496     if (memblockq_check_prebuf(bq))
 497         return 0;
 498
 499     if (pa_memblockq_get_length(bq) <= 0)
 500         return 0;
 501
 502     return 1;
 503 }
 504
 505 size_t pa_memblockq_get_length(pa_memblockq *bq) {
 506     pa_assert(bq);
 507
 508     if (bq->write_index <= bq->read_index)
 509         return 0;
 510
 511     return (size_t) (bq->write_index - bq->read_index);
 512 }
 513
 514 size_t pa_memblockq_missing(pa_memblockq *bq) {
 515     size_t l;
 516     pa_assert(bq);
 517
 518     if ((l = pa_memblockq_get_length(bq)) >= bq->tlength)
 519         return 0;
 520
 521     l = bq->tlength - l;
 522
 523     return l >= bq->minreq ? l : 0;
 524 }
 525
 526 size_t pa_memblockq_get_minreq(pa_memblockq *bq) {
 527     pa_assert(bq);
 528
 529     return bq->minreq;
 530 }
 531
 532 void pa_memblockq_seek(pa_memblockq *bq, int64_t offset, pa_seek_mode_t seek) {
 533     int64_t old, delta;
 534     pa_assert(bq);
 535
 536     old = bq->write_index;
 537
 538     switch (seek) {
 539         case PA_SEEK_RELATIVE:
 540             bq->write_index += offset;
 541             break;
 542         case PA_SEEK_ABSOLUTE:
 543             bq->write_index = offset;
 544             break;
 545         case PA_SEEK_RELATIVE_ON_READ:
 546             bq->write_index = bq->read_index + offset;
 547             break;
 548         case PA_SEEK_RELATIVE_END:
 549             bq->write_index = (bq->blocks_tail ? bq->blocks_tail->index + (int64_t) bq->blocks_tail->chunk.length : bq->read_index) + offset;
 550             break;
 551         default:
 552             pa_assert_not_reached();
 553     }
 554
 555     delta = bq->write_index - old;
 556
 557     if (delta >= bq->requested) {
 558         delta -= bq->requested;
 559         bq->requested = 0;
 560     } else if (delta >= 0) {
 561         bq->requested -= delta;
 562         delta = 0;
 563     }
 564
 565     bq->missing -= delta;
 566 }
 567
 568 void pa_memblockq_flush(pa_memblockq *bq) {
 569     int64_t old, delta;
 570     pa_assert(bq);
 571
 572     while (bq->blocks)
 573         drop_block(bq, bq->blocks);
 574
 575     pa_assert(bq->n_blocks == 0);
 576
 577     old = bq->write_index;
 578     bq->write_index = bq->read_index;
 579
 580     pa_memblockq_prebuf_force(bq);
 581
 582     delta = bq->write_index - old;
 583
 584     if (delta > bq->requested) {
 585         delta -= bq->requested;
 586         bq->requested = 0;
 587     } else if (delta >= 0) {
 588         bq->requested -= delta;
 589         delta = 0;
 590     }
 591
 592     bq->missing -= delta;
 593 }
 594
 595 size_t pa_memblockq_get_tlength(pa_memblockq *bq) {
 596     pa_assert(bq);
 597
 598     return bq->tlength;
 599 }
 600
 601 int64_t pa_memblockq_get_read_index(pa_memblockq *bq) {
 602     pa_assert(bq);
 603     return bq->read_index;
 604 }
 605
 606 int64_t pa_memblockq_get_write_index(pa_memblockq *bq) {
 607     pa_assert(bq);
 608     return bq->write_index;
 609 }
 610
 611 int pa_memblockq_push_align(pa_memblockq* bq, const pa_memchunk *chunk) {
 612     pa_memchunk rchunk;
 613
 614     pa_assert(bq);
 615     pa_assert(chunk);
 616
 617     if (bq->base == 1)
 618         return pa_memblockq_push(bq, chunk);
 619
 620     if (!bq->mcalign)
 621         bq->mcalign = pa_mcalign_new(bq->base);
 622
 623     if (!can_push(bq, pa_mcalign_csize(bq->mcalign, chunk->length)))
 624         return -1;
 625
 626     pa_mcalign_push(bq->mcalign, chunk);
 627
 628     while (pa_mcalign_pop(bq->mcalign, &rchunk) >= 0) {
 629         int r;
 630         r = pa_memblockq_push(bq, &rchunk);
 631         pa_memblock_unref(rchunk.memblock);
 632
 633         if (r < 0)
 634             return -1;
 635     }
 636
 637     return 0;
 638 }
 639
 640 void pa_memblockq_shorten(pa_memblockq *bq, size_t length) {
 641     size_t l;
 642     pa_assert(bq);
 643
 644     l = pa_memblockq_get_length(bq);
 645
 646     if (l > length)
 647         pa_memblockq_drop(bq, l - length);
 648 }
 649
 650 void pa_memblockq_prebuf_disable(pa_memblockq *bq) {
 651     pa_assert(bq);
 652
 653     bq->in_prebuf = FALSE;
 654 }
 655
 656 void pa_memblockq_prebuf_force(pa_memblockq *bq) {
 657     pa_assert(bq);
 658
 659     if (!bq->in_prebuf && bq->prebuf > 0)
 660         bq->in_prebuf = TRUE;
 661 }
 662
 663 size_t pa_memblockq_get_maxlength(pa_memblockq *bq) {
 664     pa_assert(bq);
 665
 666     return bq->maxlength;
 667 }
 668
 669 size_t pa_memblockq_get_prebuf(pa_memblockq *bq) {
 670     pa_assert(bq);
 671
 672     return bq->prebuf;
 673 }
 674
 675 size_t pa_memblockq_pop_missing(pa_memblockq *bq) {
 676     size_t l;
 677
 678     pa_assert(bq);
 679
 680 /*     pa_log("pop: %lli", bq->missing); */
 681
 682     if (bq->missing <= 0)
 683         return 0;
 684
 685     l = (size_t) bq->missing;
 686     bq->missing = 0;
 687     bq->requested += l;
 688
 689     return l;
 690 }