buffering.c

   1 /***************************************************************************
   2  *             __________               __   ___.
   3  *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
   4  *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
   5  *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
   6  *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
   7  *                     \/            \/     \/    \/            \/
   8  * $Id$
   9  *
  10  * Copyright (C) 2007 Nicolas Pennequin
  11  *
  12  * All files in this archive are subject to the GNU General Public License.
  13  * See the file COPYING in the source tree root for full license agreement.
  14  *
  15  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  16  * KIND, either express or implied.
  17  *
  18  ****************************************************************************/
  19
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include <stdbool.h>
  23 #include <string.h>
  24 #include <fcntl.h>
  25 #include <unistd.h>
  26 #include "buffering.h"
  27 #include "helpers.h"
  28
  29 /* Rockbox constants */
  30 #define HZ 1
  31 /* amount of data to read in one read() call */
  32 #define AUDIO_DEFAULT_FILECHUNK      (1024*32)
  33
  34
  35 #define BUFFER_SIZE  (32*1024*1024)
  36 #define GUARD_SIZE   (32*1024)
  37
  38
  39 /* Ring buffer helper macros */
  40 /* Buffer pointer (p) plus value (v), wrapped if necessary */
  41 #define RINGBUF_ADD(p,v) ((p+v)<buffer_len ? p+v : p+v-buffer_len)
  42 /* Buffer pointer (p) minus value (v), wrapped if necessary */
  43 #define RINGBUF_SUB(p,v) ((p>=v) ? p-v : p+buffer_len-v)
  44 /* How far value (v) plus buffer pointer (p1) will cross buffer pointer (p2) */
  45 #define RINGBUF_ADD_CROSS(p1,v,p2) \
  46 ((p1<p2) ? (int)(p1+v)-(int)p2 : (int)(p1+v-p2)-(int)buffer_len)
  47 /* Bytes available in the buffer */
  48 #define BUF_USED RINGBUF_SUB(buf_widx, buf_ridx)
  49
  50 #ifndef MIN
  51 #define MIN(a, b) (((a)<(b))?(a):(b))
  52 #endif
  53
  54
  55 static size_t buffer_len;
  56 static char *buffer;
  57 static char *buffer_end;
  58
  59 static size_t conf_filechunk;
  60
  61 static size_t buf_widx;
  62 static size_t buf_ridx;
  63
  64 /* current memory handle in the linked list. NULL when the list is empty. */
  65 static struct memory_handle *cur_handle;
  66 /* first memory handle in the linked list. NULL when the list is empty. */
  67 static struct memory_handle *first_handle;
  68 static int num_handles;
  69
  70
  71 /* add a new handle to the linked list and return it. It will have become the
  72    new current handle */
  73 static struct memory_handle *add_handle(void)
  74 {
  75     /* this will give each handle a unique id */
  76     static int cur_handle_id = 0;
  77
  78     int data_size = sizeof(struct memory_handle) /*
  79                     + 1024*1024 - sizeof(struct memory_handle) */;
  80
  81     /* check that we actually can add the handle and its data */
  82     if (RINGBUF_ADD_CROSS(buf_widx, data_size, buf_ridx) >= 0) {
  83         return NULL;
  84     }
  85
  86     struct memory_handle *new_handle = (struct memory_handle *)(buffer + buf_widx);
  87     buf_widx = RINGBUF_ADD(buf_widx, data_size);
  88
  89     if (!first_handle) {
  90         /* the new handle is the first one */
  91         first_handle = new_handle;
  92     }
  93
  94     if (cur_handle) {
  95         cur_handle->next = new_handle;
  96     }
  97
  98     cur_handle = new_handle;
  99     cur_handle->id = cur_handle_id++;
 100     cur_handle->next = NULL;
 101     num_handles++;
 102     return cur_handle;
 103 }
 104
 105 /* delete a given memory handle from the linked list
 106    and return true for success. Nothing is actually erased from memory. */
 107 static bool rm_handle(struct memory_handle *h)
 108 {
 109     if (h == first_handle) {
 110         first_handle = h->next;
 111         if (h == cur_handle) {
 112             cur_handle = NULL;
 113         }
 114     } else {
 115         struct memory_handle *m = first_handle;
 116         while (m && m->next != h) {
 117             m = m->next;
 118         }
 119         if (h && m && m->next == h) {
 120             m->next = h->next;
 121             if (h == cur_handle) {
 122                 cur_handle = m;
 123             }
 124         } else {
 125             return false;
 126         }
 127     }
 128     num_handles--;
 129     return true;
 130 }
 131
 132 /* Move a memory handle to newpos */
 133 static struct memory_handle *move_handle(size_t newpos, struct memory_handle *h)
 134 {
 135     struct memory_handle *dest = (struct memory_handle *)(buffer + newpos);
 136
 137     if (h == cur_handle) {
 138         cur_handle = dest;
 139     }
 140
 141     if (h == first_handle) {
 142         first_handle = dest;
 143     } else {
 144         struct memory_handle *m = first_handle;
 145         while (m && m->next != h) {
 146             m = m->next;
 147         }
 148         if (h && m && m->next == h) {
 149             m->next = dest;
 150         } else {
 151             return NULL;
 152         }
 153     }
 154     memmove(dest, h, sizeof(struct memory_handle));
 155     return dest;
 156 }
 157
 158 /* Return a pointer to the memory handle of given ID.
 159    NULL if the handle wasn't found */
 160 static struct memory_handle *find_handle(int handle_id)
 161 {
 162     static int last_handle_id = -1;
 163     static struct memory_handle *last_m = NULL;
 164     struct memory_handle *m = first_handle;
 165     /* simple caching because most of the time the requested handle
 166     will either be the same as the last, or the one after the last */
 167 #if 0
 168     if (last_m)
 169     {
 170         if (last_handle_id == handle_id && last_handle_id == last_m->id)
 171             return last_m;
 172         else if (last_m->next && (last_m->next->id == handle_id))
 173         {
 174             /* JD's quick testing showd this block was only entered
 175                2/1971 calls to find_handle.
 176                8/1971 calls to find_handle resulted in a cache miss */
 177             last_m = last_m->next;
 178             last_handle_id = handle_id;
 179             return last_m;
 180         }
 181     }
 182 #endif
 183     while (m && m->id != handle_id) {
 184         m = m->next;
 185     }
 186     last_handle_id = handle_id;
 187     last_m = m;
 188     return (m && m->id == handle_id) ? m : NULL;
 189 }
 190
 191 /* Buffer data for the given handle. Return the amount of data buffered
 192    or -1 if the handle wasn't found */
 193 static int buffer_handle(int handle_id)
 194 {
 195     struct memory_handle *h = find_handle(handle_id);
 196     //printf("find_handle %d:\nid: %d\npath: %s\n\n", handle_id, h->id, h->path);
 197     if (!h)
 198         return -1;
 199
 200     if (h->filerem == 0) {
 201         /* nothing left to buffer */
 202         return 0;
 203     }
 204
 205     if (h->fd < 0)  /* file closed, reopen */
 206     {
 207         if (*h->path)
 208             h->fd = open(h->path, O_RDONLY);
 209         else
 210             return -1;
 211
 212         if (h->fd < 0)
 213             return -1;
 214
 215         if (h->offset)
 216             lseek(h->fd, h->offset, SEEK_SET);
 217     }
 218
 219     int ret = 0;
 220     while (h->filerem > 0)
 221     {
 222         //printf("h: %d\n", (void *)h - (void *)buffer);
 223         //printf("buf_widx: %ld\n", (long)buf_widx);
 224         /* max amount to copy */
 225         size_t copy_n = MIN(conf_filechunk, buffer_len - buf_widx);
 226
 227         if (RINGBUF_ADD_CROSS(buf_widx, copy_n, buf_ridx) >= 0)
 228             break;
 229
 230         /* rc is the actual amount read */
 231         int rc = read(h->fd, &buffer[buf_widx], copy_n);
 232
 233         if (rc < 0)
 234         {
 235             printf("failed on fd %d at buf_widx = %ld for handle %d\n", h->fd, (long)buf_widx, h->id);
 236             printf("File ended %ld bytes early\n", (long)h->filerem);
 237             h->filesize -= h->filerem;
 238             h->filerem = 0;
 239             break;
 240         }
 241
 242         /* Advance buffer */
 243         buf_widx = RINGBUF_ADD(buf_widx, rc);
 244         h->available += rc;
 245         ret += rc;
 246         h->filerem -= rc;
 247     }
 248
 249     if (h->filerem == 0) {
 250         /* finished buffering the file */
 251         close(h->fd);
 252     }
 253
 254     printf("buffered %d bytes (%d of %d available, remaining: %d)\n",
 255            ret, h->available, h->filesize, h->filerem);
 256     return ret;
 257 }
 258
 259 /* this seems wrong */
 260 static void free_buffer(void)
 261 {
 262     size_t delta = RINGBUF_SUB(first_handle->buf_idx, first_handle->data);
 263     size_t dest = RINGBUF_ADD((void *)first_handle - (void *)buffer, delta);
 264     printf("buf_ridx: %ld, buf_widx: %ld\n", (long)buf_ridx, (long)buf_widx);
 265     printf("dest: %ld, delta: %ld\n", (long)dest, (long)delta);
 266     first_handle = move_handle(dest, first_handle);
 267     first_handle->data = RINGBUF_ADD(first_handle->data, delta);
 268     first_handle->buf_idx = first_handle->data;
 269     buf_ridx = dest;
 270 }
 271
 272 /* Request a file be buffered
 273     filename: name of the file t open
 274     offset:   starting offset to buffer from the file
 275     RETURNS:  <0 if the file cannot be opened, or one file already
 276                 queued to be opened, otherwise the handle for the file in the buffer
 277 */
 278 int bufopen(char *file, size_t offset)
 279 {
 280     /* add the file to the buffering queue. */
 281     /* for now, we'll assume the queue is always empty, so the handle
 282        gets added immediately */
 283
 284     printf("bufopen: %s (offset: %d)\n", file, offset);
 285
 286     int fd = open(file, O_RDONLY);
 287     if (fd < 0)
 288         return -1;
 289
 290     if (offset)
 291         lseek(fd, offset, SEEK_SET);
 292
 293     struct memory_handle *h = add_handle();
 294     if (!h)
 295         return -1;
 296     strncpy(h->path, file, MAX_PATH);
 297     h->fd = fd;
 298     h->filesize = filesize(fd);
 299     h->filerem = h->filesize - offset;
 300     h->offset = offset;
 301     h->buf_idx = buf_widx;
 302     h->data = buf_widx;
 303     h->available = 0;
 304
 305     printf("added handle : %d\n", h->id);
 306     return h->id;
 307 }
 308
 309 /* Close the handle. Return 0 for success and < 0 for failure */
 310 int bufclose(int handle_id)
 311 {
 312     printf("bufclose: %d\n", handle_id);
 313     struct memory_handle *h = find_handle(handle_id);
 314     if (!h)
 315         return -1;
 316
 317     if (num_handles > 1) {
 318         rm_handle(h);
 319         buf_ridx = (size_t)first_handle - (size_t)buffer;
 320     } else {
 321         printf("closing the first and last handle\n");
 322         /* num_handles == 1, therefore h == first_handle */
 323         buf_ridx = buf_widx;
 324         rm_handle(h);
 325     }
 326
 327     return 0;
 328 }
 329
 330 /* Seek in a handle. Return 0 for success and < 0 for failure */
 331 int bufseek(int handle_id, size_t offset)
 332 {
 333     struct memory_handle *h = find_handle(handle_id);
 334     if (!h)
 335         return -1;
 336
 337     h->buf_idx = RINGBUF_ADD(h->data, offset);
 338     return 0;
 339 }
 340
 341 /* Copy data from the given handle to the dest buffer.
 342    Return the number of bytes copied or -1 for failure. */
 343 int bufread(int handle_id, size_t size, char *dest)
 344 {
 345     struct memory_handle *h = find_handle(handle_id);
 346     size_t buffered_data;
 347     if (!h)
 348         return -1;
 349     if (h->available == 0)
 350         return 0;
 351     buffered_data = MIN(size,h->available);
 352
 353     if (h->buf_idx + buffered_data > buffer_len)
 354     {
 355         size_t read = buffer_len - h->buf_idx;
 356         memcpy(dest, &buffer[h->buf_idx], read);
 357         memcpy(dest+read, buffer, buffered_data - read);
 358     }
 359     else memcpy(dest, &buffer[h->buf_idx], buffered_data);
 360
 361     h->buf_idx = RINGBUF_ADD(h->buf_idx, buffered_data);
 362     h->available -= buffered_data;
 363     return buffered_data;
 364 }
 365
 366 bool test_ll(void)
 367 {
 368     struct memory_handle *m1, *m2, *m3, *m4;
 369
 370     if (cur_handle != NULL || first_handle != NULL)
 371         return false;
 372
 373     m1 = add_handle();
 374
 375     if (cur_handle != m1 || first_handle != m1 || m1->next != NULL)
 376         return false;
 377
 378     m2 = add_handle();
 379
 380     if (cur_handle != m2 || first_handle != m1 || m1->next != m2 || m2->next != NULL)
 381         return false;
 382
 383     m3 = add_handle();
 384
 385     if (cur_handle != m3 || first_handle != m1 || m2->next != m3 || m3->next != NULL)
 386         return false;
 387
 388     rm_handle(m2);
 389
 390     if (cur_handle != m3 || first_handle != m1 || m1->next != m3)
 391         return false;
 392
 393     rm_handle(m3);
 394
 395     if (cur_handle != m1 || first_handle != m1 || m1->next != NULL)
 396         return false;
 397
 398     m4 = add_handle();
 399
 400     if (cur_handle != m4 || first_handle != m1 || m1->next != m4 || m4->next != NULL)
 401         return false;
 402
 403     rm_handle(m1);
 404
 405     if (cur_handle != m4 || first_handle != m4)
 406         return false;
 407
 408     rm_handle(m4);
 409
 410     if (cur_handle != NULL || first_handle != NULL)
 411         return false;
 412
 413     m1 = add_handle();
 414     m2 = add_handle();
 415     m3 = add_handle();
 416     m4 = add_handle();
 417
 418     if (cur_handle != m4 || first_handle != m1)
 419         return false;
 420
 421     int m2id = m2->id;
 422     m2 = move_handle(m2->data + 1024*1024, m2);
 423
 424     if (cur_handle != m4 || first_handle != m1 || m1->next != m2 || m2->next != m3 ||
 425         find_handle(m2id) != m2)
 426         return false;
 427
 428     int m1id = m1->id;
 429     m1 = move_handle(m1->data + 1024*1024*3, m1);
 430
 431     if (cur_handle != m4 || first_handle != m1 || m1->next != m2 ||
 432         find_handle(m1id) != m1)
 433         return false;
 434
 435     rm_handle(m1);
 436     rm_handle(m2);
 437     rm_handle(m3);
 438     rm_handle(m4);
 439
 440     if (cur_handle != NULL || first_handle != NULL)
 441         return false;
 442
 443     return true;
 444 }
 445
 446 static void list_handles(void)
 447 {
 448     struct memory_handle *m = first_handle;
 449     while (m) {
 450         printf("%02d - %d\n", m->id, (void *)m-(void *)buffer);
 451         m = m->next;
 452     }
 453 }
 454
 455 /* display a nice graphical view of the ringbuffer. */
 456 static void graph_view(int width)
 457 {
 458     int i, r_pos, w_pos;
 459     r_pos = buf_ridx * width / buffer_len;
 460     w_pos = buf_widx * width / buffer_len;
 461
 462     printf("|");
 463     for (i=0; i <= width; i++)
 464     {
 465         if (i != r_pos && i != w_pos)
 466         {
 467             if (buf_ridx <= buf_widx)
 468             {
 469                 if (i > r_pos && i < w_pos)
 470                     printf(">");
 471                 else
 472                     printf("-");
 473             }
 474             else
 475             {
 476                 if (i > r_pos || i < w_pos)
 477                     printf(">");
 478                 else
 479                     printf("-");
 480             }
 481         }
 482         else
 483         {
 484             if (i == r_pos && i == w_pos)
 485             {
 486                 if (buf_ridx <= buf_widx)
 487                     printf("RW");
 488                 else
 489                     printf("WR");
 490             }
 491             else if (i == r_pos)
 492                 printf("R");
 493             else if (i == w_pos)
 494                 printf("W");
 495         }
 496     }
 497     printf("|");
 498     printf("\n");
 499 }
 500
 501 void buffer_init(void)
 502 {
 503     buffer = (char *)malloc(sizeof(char) * (BUFFER_SIZE + GUARD_SIZE));
 504     if (!buffer)
 505     {
 506         printf("couldn't allocate buffer\n");
 507         exit(1);
 508     }
 509     buffer_len = BUFFER_SIZE;
 510     buffer_end = buffer + BUFFER_SIZE;
 511
 512     buf_widx = 0;
 513     buf_ridx = 0;
 514
 515     first_handle = NULL;
 516     num_handles = 0;
 517
 518     conf_filechunk = AUDIO_DEFAULT_FILECHUNK;
 519 }
 520
 521 /* returns true if the file still has some on disk unread */
 522 bool handle_has_data(int handle)
 523 {
 524     struct memory_handle *m = find_handle(handle);
 525     if (m)
 526     {
 527         return m->filerem != 0;
 528     }
 529     return false;
 530 }
 531
 532 bool need_rebuffer(void)
 533 {
 534     size_t free;
 535     free = BUFFER_SIZE - BUF_USED;
 536     return ((free >= BUFFER_SIZE/4));
 537 }
 538
 539 #define MAX_HANDLES 64
 540 int main(int argc, char *argv[])
 541 {
 542     int next_file = 1;
 543     int last_handle = -1;
 544     int handle_order[MAX_HANDLES];
 545     int reading_handle = 0;
 546     bool done = false;
 547     char read_buffer[GUARD_SIZE];
 548     int fd = -1; /* used to write the files out as they are read */
 549     struct memory_handle *m = NULL;
 550     buffer_init();
 551
 552     if (!test_ll())
 553     {
 554         printf("linked list test failed\n");
 555         exit(1);
 556     }
 557
 558     buffer_init();
 559
 560     while (done == false)
 561     {
 562         printf("buffer usage: %d handles_used: %d\n", BUF_USED,num_handles);
 563         graph_view(100);
 564
 565         /* "Buffering thread" section */
 566         if ((next_file <= argc) && need_rebuffer())
 567         {
 568             if ( !m || ((m->filerem == 0) && (m->next == NULL)))
 569             {
 570                 int h = bufopen(argv[next_file++], 0);
 571                 m = find_handle(h);
 572                 if (h >= 0)
 573                 {
 574                     printf("new handle %d\n",h);
 575                     last_handle++;
 576                     handle_order[last_handle] = h;
 577                     buffer_handle(m->id);
 578                 }
 579             }
 580             else
 581             {
 582                 if (m->filerem == 0)
 583                     m = m->next;
 584                 printf("buffering handle %d\n",m->id);
 585                 buffer_handle(m->id);
 586             }
 587         }
 588         /* "Playback thread" section */
 589         else
 590         {
 591             printf("reading handle: %d\n", handle_order[reading_handle]);
 592             long read;
 593             long total = 0;
 594             char file[MAX_PATH];
 595             if (reading_handle >= last_handle
 596                 && !handle_has_data(handle_order[reading_handle]))
 597                 done = true;
 598
 599             if (fd < 0)
 600             {
 601                 snprintf(file, MAX_PATH, "./file%d.mp3", reading_handle);
 602                 fd = open(file, O_CREAT|O_TRUNC|O_WRONLY, 0770);
 603                 if (fd < 0)
 604                 {
 605                     printf("ERROROROROR\n");
 606                     exit(1);
 607                 }
 608             }
 609             do
 610             {
 611                 read = bufread(handle_order[reading_handle], GUARD_SIZE,read_buffer);
 612                 write(fd, read_buffer, read);
 613                 total += read;
 614             }
 615             while (read > 0);
 616
 617             printf("read %ld bytes from handle %d\n", total, handle_order[reading_handle]);
 618
 619             /* close the fd/handle if there is no more data or an error */
 620             if (read < 0 || handle_has_data(handle_order[reading_handle]) == false)
 621             {
 622                 printf("finished reading %d\n",handle_order[reading_handle]);
 623                 bufclose(handle_order[reading_handle]);
 624                 close(fd);
 625                 reading_handle++;
 626                 fd = -1;
 627             }
 628             else
 629             {
 630                 printf("there is data left to buffer for %d\n", handle_order[reading_handle]);
 631                 free_buffer();
 632             }
 633         }
 634     }
 635
 636     printf("buffer usage: %d handles_used: %d\n", BUF_USED,num_handles);
 637     graph_view(100);
 638
 639     free(buffer);
 640     return 0;
 641 }