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
  40 #include "memblockq.h"
  41
  42 struct memblock_list {
  43     struct memblock_list *next, *prev;
  44     int64_t index;
  45     pa_memchunk chunk;
  46 };
  47
  48 struct pa_memblockq {
  49     struct memblock_list *blocks, *blocks_tail;
  50     unsigned n_blocks;
  51     size_t maxlength, tlength, base, prebuf, minreq;
  52     int64_t read_index, write_index;
  53     enum { PREBUF, RUNNING } state;
  54     pa_memblock *silence;
  55     pa_mcalign *mcalign;
  56 };
  57
  58 pa_memblockq* pa_memblockq_new(
  59         int64_t idx,
  60         size_t maxlength,
  61         size_t tlength,
  62         size_t base,
  63         size_t prebuf,
  64         size_t minreq,
  65         pa_memblock *silence) {
  66
  67     pa_memblockq* bq;
  68
  69     pa_assert(base > 0);
  70     pa_assert(maxlength >= base);
  71
  72     bq = pa_xnew(pa_memblockq, 1);
  73     bq->blocks = bq->blocks_tail = NULL;
  74     bq->n_blocks = 0;
  75
  76     bq->base = base;
  77     bq->read_index = bq->write_index = idx;
  78
  79     pa_log_debug("memblockq requested: maxlength=%lu, tlength=%lu, base=%lu, prebuf=%lu, minreq=%lu",
  80         (unsigned long)maxlength, (unsigned long)tlength, (unsigned long)base, (unsigned long)prebuf, (unsigned long)minreq);
  81
  82     bq->maxlength = ((maxlength+base-1)/base)*base;
  83     pa_assert(bq->maxlength >= base);
  84
  85     bq->tlength = ((tlength+base-1)/base)*base;
  86     if (!bq->tlength || bq->tlength >= bq->maxlength)
  87         bq->tlength = bq->maxlength;
  88
  89     bq->prebuf = (prebuf == (size_t) -1) ? bq->tlength/2 : prebuf;
  90     bq->prebuf = ((bq->prebuf+base-1)/base)*base;
  91     if (bq->prebuf > bq->maxlength)
  92         bq->prebuf = bq->maxlength;
  93
  94     bq->minreq = (minreq/base)*base;
  95
  96     if (bq->minreq > bq->tlength - bq->prebuf)
  97         bq->minreq = bq->tlength - bq->prebuf;
  98
  99     if (!bq->minreq)
 100         bq->minreq = 1;
 101
 102     pa_log_debug("memblockq sanitized: maxlength=%lu, tlength=%lu, base=%lu, prebuf=%lu, minreq=%lu",
 103         (unsigned long)bq->maxlength, (unsigned long)bq->tlength, (unsigned long)bq->base, (unsigned long)bq->prebuf, (unsigned long)bq->minreq);
 104
 105     bq->state = bq->prebuf ? PREBUF : RUNNING;
 106     bq->silence = silence ? pa_memblock_ref(silence) : NULL;
 107     bq->mcalign = NULL;
 108
 109     return bq;
 110 }
 111
 112 void pa_memblockq_free(pa_memblockq* bq) {
 113     pa_assert(bq);
 114
 115     pa_memblockq_flush(bq);
 116
 117     if (bq->silence)
 118         pa_memblock_unref(bq->silence);
 119
 120     if (bq->mcalign)
 121         pa_mcalign_free(bq->mcalign);
 122
 123     pa_xfree(bq);
 124 }
 125
 126 static void drop_block(pa_memblockq *bq, struct memblock_list *q) {
 127     pa_assert(bq);
 128     pa_assert(q);
 129
 130     pa_assert(bq->n_blocks >= 1);
 131
 132     if (q->prev)
 133         q->prev->next = q->next;
 134     else
 135         bq->blocks = q->next;
 136
 137     if (q->next)
 138         q->next->prev = q->prev;
 139     else
 140         bq->blocks_tail = q->prev;
 141
 142     pa_memblock_unref(q->chunk.memblock);
 143     pa_xfree(q);
 144
 145     bq->n_blocks--;
 146 }
 147
 148 static int can_push(pa_memblockq *bq, size_t l) {
 149     int64_t end;
 150
 151     pa_assert(bq);
 152
 153     if (bq->read_index > bq->write_index) {
 154         size_t d =  bq->read_index - bq->write_index;
 155
 156         if (l > d)
 157             l -= d;
 158         else
 159             return 1;
 160     }
 161
 162     end = bq->blocks_tail ? bq->blocks_tail->index + bq->blocks_tail->chunk.length : 0;
 163
 164     /* Make sure that the list doesn't get too long */
 165     if (bq->write_index + (int64_t)l > end)
 166         if (bq->write_index + l - bq->read_index > bq->maxlength)
 167             return 0;
 168
 169     return 1;
 170 }
 171
 172 int pa_memblockq_push(pa_memblockq* bq, const pa_memchunk *uchunk) {
 173
 174     struct memblock_list *q, *n;
 175     pa_memchunk chunk;
 176
 177     pa_assert(bq);
 178     pa_assert(uchunk);
 179     pa_assert(uchunk->memblock);
 180     pa_assert(uchunk->length > 0);
 181     pa_assert(uchunk->index + uchunk->length <= pa_memblock_get_length(uchunk->memblock));
 182
 183     if (uchunk->length % bq->base)
 184         return -1;
 185
 186     if (!can_push(bq, uchunk->length))
 187         return -1;
 188
 189     chunk = *uchunk;
 190
 191     if (bq->read_index > bq->write_index) {
 192
 193         /* We currently have a buffer underflow, we need to drop some
 194          * incoming data */
 195
 196         size_t d = bq->read_index - bq->write_index;
 197
 198         if (chunk.length > d) {
 199             chunk.index += d;
 200             chunk.length -= d;
 201             bq->write_index = bq->read_index;
 202         } else {
 203             /* We drop the incoming data completely */
 204             bq->write_index += chunk.length;
 205             return 0;
 206         }
 207     }
 208
 209     /* We go from back to front to look for the right place to add
 210      * this new entry. Drop data we will overwrite on the way */
 211
 212     q = bq->blocks_tail;
 213     while (q) {
 214
 215         if (bq->write_index >= q->index + (int64_t)q->chunk.length)
 216             /* We found the entry where we need to place the new entry immediately after */
 217             break;
 218         else if (bq->write_index + (int64_t)chunk.length <= q->index) {
 219             /* This entry isn't touched at all, let's skip it */
 220             q = q->prev;
 221         } else if (bq->write_index <= q->index &&
 222             bq->write_index + chunk.length >= q->index + q->chunk.length) {
 223
 224             /* This entry is fully replaced by the new entry, so let's drop it */
 225
 226             struct memblock_list *p;
 227             p = q;
 228             q = q->prev;
 229             drop_block(bq, p);
 230         } else if (bq->write_index >= q->index) {
 231             /* The write index points into this memblock, so let's
 232              * truncate or split it */
 233
 234             if (bq->write_index + chunk.length < q->index + q->chunk.length) {
 235
 236                 /* We need to save the end of this memchunk */
 237                 struct memblock_list *p;
 238                 size_t d;
 239
 240                 /* Create a new list entry for the end of thie memchunk */
 241                 p = pa_xnew(struct memblock_list, 1);
 242                 p->chunk = q->chunk;
 243                 pa_memblock_ref(p->chunk.memblock);
 244
 245                 /* Calculate offset */
 246                 d = bq->write_index + chunk.length - q->index;
 247                 pa_assert(d > 0);
 248
 249                 /* Drop it from the new entry */
 250                 p->index = q->index + d;
 251                 p->chunk.length -= d;
 252
 253                 /* Add it to the list */
 254                 p->prev = q;
 255                 if ((p->next = q->next))
 256                     q->next->prev = p;
 257                 else
 258                     bq->blocks_tail = p;
 259                 q->next = p;
 260
 261                 bq->n_blocks++;
 262             }
 263
 264             /* Truncate the chunk */
 265             if (!(q->chunk.length = bq->write_index - q->index)) {
 266                 struct memblock_list *p;
 267                 p = q;
 268                 q = q->prev;
 269                 drop_block(bq, p);
 270             }
 271
 272             /* We had to truncate this block, hence we're now at the right position */
 273             break;
 274         } else {
 275             size_t d;
 276
 277             pa_assert(bq->write_index + (int64_t)chunk.length > q->index &&
 278                    bq->write_index + (int64_t)chunk.length < q->index + (int64_t)q->chunk.length &&
 279                    bq->write_index < q->index);
 280
 281             /* The job overwrites the current entry at the end, so let's drop the beginning of this entry */
 282
 283             d = bq->write_index + chunk.length - q->index;
 284             q->index += d;
 285             q->chunk.index += d;
 286             q->chunk.length -= d;
 287
 288             q = q->prev;
 289         }
 290
 291     }
 292
 293     if (q) {
 294         pa_assert(bq->write_index >=  q->index + (int64_t)q->chunk.length);
 295         pa_assert(!q->next || (bq->write_index + (int64_t)chunk.length <= q->next->index));
 296
 297         /* Try to merge memory blocks */
 298
 299         if (q->chunk.memblock == chunk.memblock &&
 300             q->chunk.index + (int64_t)q->chunk.length == chunk.index &&
 301             bq->write_index == q->index + (int64_t)q->chunk.length) {
 302
 303             q->chunk.length += chunk.length;
 304             bq->write_index += chunk.length;
 305             return 0;
 306         }
 307     } else
 308         pa_assert(!bq->blocks || (bq->write_index + (int64_t)chunk.length <= bq->blocks->index));
 309
 310
 311     n = pa_xnew(struct memblock_list, 1);
 312     n->chunk = chunk;
 313     pa_memblock_ref(n->chunk.memblock);
 314     n->index = bq->write_index;
 315     bq->write_index += n->chunk.length;
 316
 317     n->next = q ? q->next : bq->blocks;
 318     n->prev = q;
 319
 320     if (n->next)
 321         n->next->prev = n;
 322     else
 323         bq->blocks_tail = n;
 324
 325     if (n->prev)
 326         n->prev->next = n;
 327     else
 328         bq->blocks = n;
 329
 330     bq->n_blocks++;
 331     return 0;
 332 }
 333
 334 int pa_memblockq_peek(pa_memblockq* bq, pa_memchunk *chunk) {
 335     pa_assert(bq);
 336     pa_assert(chunk);
 337
 338     if (bq->state == PREBUF) {
 339
 340         /* We need to pre-buffer */
 341         if (pa_memblockq_get_length(bq) < bq->prebuf)
 342             return -1;
 343
 344         bq->state = RUNNING;
 345
 346     } else if (bq->prebuf > 0 && bq->read_index >= bq->write_index) {
 347
 348         /* Buffer underflow protection */
 349         bq->state = PREBUF;
 350         return -1;
 351     }
 352
 353     /* Do we need to spit out silence? */
 354     if (!bq->blocks || bq->blocks->index > bq->read_index) {
 355
 356         size_t length;
 357
 358         /* How much silence shall we return? */
 359         length = bq->blocks ? bq->blocks->index - bq->read_index : 0;
 360
 361         /* We need to return silence, since no data is yet available */
 362         if (bq->silence) {
 363             chunk->memblock = pa_memblock_ref(bq->silence);
 364
 365             if (!length || length > pa_memblock_get_length(chunk->memblock))
 366                 length = pa_memblock_get_length(chunk->memblock);
 367
 368             chunk->length = length;
 369         } else {
 370
 371             /* If the memblockq is empty, return -1, otherwise return
 372              * the time to sleep */
 373             if (!bq->blocks)
 374                 return -1;
 375
 376             chunk->memblock = NULL;
 377             chunk->length = length;
 378         }
 379
 380         chunk->index = 0;
 381         return 0;
 382     }
 383
 384     /* Ok, let's pass real data to the caller */
 385     pa_assert(bq->blocks->index == bq->read_index);
 386
 387     *chunk = bq->blocks->chunk;
 388     pa_memblock_ref(chunk->memblock);
 389
 390     return 0;
 391 }
 392
 393 void pa_memblockq_drop(pa_memblockq *bq, const pa_memchunk *chunk, size_t length) {
 394     pa_assert(bq);
 395     pa_assert(length % bq->base == 0);
 396     pa_assert(!chunk || length <= chunk->length);
 397
 398     if (chunk) {
 399
 400         if (bq->blocks && bq->blocks->index == bq->read_index) {
 401             /* The first item in queue is valid */
 402
 403             /* Does the chunk match with what the user supplied us? */
 404             if (memcmp(chunk, &bq->blocks->chunk, sizeof(pa_memchunk)) != 0)
 405                 return;
 406
 407         } else {
 408             size_t l;
 409
 410             /* The first item in the queue is not yet relevant */
 411
 412             pa_assert(!bq->blocks || bq->blocks->index > bq->read_index);
 413             l = bq->blocks ? bq->blocks->index - bq->read_index : 0;
 414
 415             if (bq->silence) {
 416
 417                 if (!l || l > pa_memblock_get_length(bq->silence))
 418                     l = pa_memblock_get_length(bq->silence);
 419
 420             }
 421
 422             /* Do the entries still match? */
 423             if (chunk->index != 0 || chunk->length != l || chunk->memblock != bq->silence)
 424                 return;
 425         }
 426     }
 427
 428     while (length > 0) {
 429
 430         if (bq->blocks) {
 431             size_t d;
 432
 433             pa_assert(bq->blocks->index >= bq->read_index);
 434
 435             d = (size_t) (bq->blocks->index - bq->read_index);
 436
 437             if (d >= length) {
 438                 /* The first block is too far in the future */
 439
 440                 bq->read_index += length;
 441                 break;
 442             } else {
 443
 444                 length -= d;
 445                 bq->read_index += d;
 446             }
 447
 448             pa_assert(bq->blocks->index == bq->read_index);
 449
 450             if (bq->blocks->chunk.length <= length) {
 451                 /* We need to drop the full block */
 452
 453                 length -= bq->blocks->chunk.length;
 454                 bq->read_index += bq->blocks->chunk.length;
 455
 456                 drop_block(bq, bq->blocks);
 457             } else {
 458                 /* Only the start of this block needs to be dropped */
 459
 460                 bq->blocks->chunk.index += length;
 461                 bq->blocks->chunk.length -= length;
 462                 bq->blocks->index += length;
 463                 bq->read_index += length;
 464                 break;
 465             }
 466
 467         } else {
 468
 469             /* The list is empty, there's nothing we could drop */
 470             bq->read_index += length;
 471             break;
 472         }
 473     }
 474 }
 475
 476 int pa_memblockq_is_readable(pa_memblockq *bq) {
 477     pa_assert(bq);
 478
 479     if (bq->prebuf > 0) {
 480         size_t l = pa_memblockq_get_length(bq);
 481
 482         if (bq->state == PREBUF && l < bq->prebuf)
 483             return 0;
 484
 485         if (l <= 0)
 486             return 0;
 487     }
 488
 489     return 1;
 490 }
 491
 492 size_t pa_memblockq_get_length(pa_memblockq *bq) {
 493     pa_assert(bq);
 494
 495     if (bq->write_index <= bq->read_index)
 496         return 0;
 497
 498     return (size_t) (bq->write_index - bq->read_index);
 499 }
 500
 501 size_t pa_memblockq_missing(pa_memblockq *bq) {
 502     size_t l;
 503     pa_assert(bq);
 504
 505     if ((l = pa_memblockq_get_length(bq)) >= bq->tlength)
 506         return 0;
 507
 508     l = bq->tlength - l;
 509     return (l >= bq->minreq) ? l : 0;
 510 }
 511
 512 size_t pa_memblockq_get_minreq(pa_memblockq *bq) {
 513     pa_assert(bq);
 514
 515     return bq->minreq;
 516 }
 517
 518 void pa_memblockq_seek(pa_memblockq *bq, int64_t offset, pa_seek_mode_t seek) {
 519     pa_assert(bq);
 520
 521     switch (seek) {
 522         case PA_SEEK_RELATIVE:
 523             bq->write_index += offset;
 524             return;
 525         case PA_SEEK_ABSOLUTE:
 526             bq->write_index = offset;
 527             return;
 528         case PA_SEEK_RELATIVE_ON_READ:
 529             bq->write_index = bq->read_index + offset;
 530             return;
 531         case PA_SEEK_RELATIVE_END:
 532             bq->write_index = (bq->blocks_tail ? bq->blocks_tail->index + (int64_t)bq->blocks_tail->chunk.length : bq->read_index) + offset;
 533             return;
 534     }
 535
 536     pa_assert_not_reached();
 537 }
 538
 539 void pa_memblockq_flush(pa_memblockq *bq) {
 540     pa_assert(bq);
 541
 542     while (bq->blocks)
 543         drop_block(bq, bq->blocks);
 544
 545     pa_assert(bq->n_blocks == 0);
 546
 547     bq->write_index = bq->read_index;
 548
 549     pa_memblockq_prebuf_force(bq);
 550 }
 551
 552 size_t pa_memblockq_get_tlength(pa_memblockq *bq) {
 553     pa_assert(bq);
 554
 555     return bq->tlength;
 556 }
 557
 558 int64_t pa_memblockq_get_read_index(pa_memblockq *bq) {
 559     pa_assert(bq);
 560     return bq->read_index;
 561 }
 562
 563 int64_t pa_memblockq_get_write_index(pa_memblockq *bq) {
 564     pa_assert(bq);
 565     return bq->write_index;
 566 }
 567
 568 int pa_memblockq_push_align(pa_memblockq* bq, const pa_memchunk *chunk) {
 569     pa_memchunk rchunk;
 570
 571     pa_assert(bq);
 572     pa_assert(chunk && bq->base);
 573
 574     if (bq->base == 1)
 575         return pa_memblockq_push(bq, chunk);
 576
 577     if (!bq->mcalign)
 578         bq->mcalign = pa_mcalign_new(bq->base);
 579
 580     if (!can_push(bq, pa_mcalign_csize(bq->mcalign, chunk->length)))
 581         return -1;
 582
 583     pa_mcalign_push(bq->mcalign, chunk);
 584
 585     while (pa_mcalign_pop(bq->mcalign, &rchunk) >= 0) {
 586         int r;
 587         r = pa_memblockq_push(bq, &rchunk);
 588         pa_memblock_unref(rchunk.memblock);
 589
 590         if (r < 0)
 591             return -1;
 592     }
 593
 594     return 0;
 595 }
 596
 597 void pa_memblockq_shorten(pa_memblockq *bq, size_t length) {
 598     size_t l;
 599     pa_assert(bq);
 600
 601     l = pa_memblockq_get_length(bq);
 602
 603     if (l > length)
 604         pa_memblockq_drop(bq, NULL, l - length);
 605 }
 606
 607 void pa_memblockq_prebuf_disable(pa_memblockq *bq) {
 608     pa_assert(bq);
 609
 610     if (bq->state == PREBUF)
 611         bq->state = RUNNING;
 612 }
 613
 614 void pa_memblockq_prebuf_force(pa_memblockq *bq) {
 615     pa_assert(bq);
 616
 617     if (bq->state == RUNNING && bq->prebuf > 0)
 618         bq->state = PREBUF;
 619 }
 620
 621 size_t pa_memblockq_get_maxlength(pa_memblockq *bq) {
 622     pa_assert(bq);
 623
 624     return bq->maxlength;
 625 }
 626
 627 size_t pa_memblockq_get_prebuf(pa_memblockq *bq) {
 628     pa_assert(bq);
 629
 630     return bq->prebuf;
 631 }