LGPL
[vlc.git] / src / misc / block.c
1 /*****************************************************************************
2  * block.c: Data blocks management functions
3  *****************************************************************************
4  * Copyright (C) 2003-2004 VLC authors and VideoLAN
5  * Copyright (C) 2007-2009 RĂ©mi Denis-Courmont
6  *
7  * Authors: Laurent Aimar <fenrir@videolan.org>
8  *
9  * This program is free software; you can redistribute it and/or modify it
10  * under the terms of the GNU Lesser General Public License as published by
11  * the Free Software Foundation; either version 2.1 of the License, or
12  * (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  * GNU Lesser General Public License for more details.
18  *
19  * You should have received a copy of the GNU Lesser General Public License
20  * along with this program; if not, write to the Free Software Foundation,
21  * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
22  *****************************************************************************/
23
24 /*****************************************************************************
25  * Preamble
26  *****************************************************************************/
27 #ifdef HAVE_CONFIG_H
28 # include "config.h"
29 #endif
30
31 #include <vlc_common.h>
32 #include <sys/stat.h>
33 #include <assert.h>
34 #include <errno.h>
35 #ifdef HAVE_UNISTD_H
36 # include <unistd.h>
37 #endif
38
39 #include "vlc_block.h"
40
41 /**
42  * @section Block handling functions.
43  */
44
45 /**
46  * Internal state for heap block.
47   */
48 struct block_sys_t
49 {
50     block_t     self;
51     size_t      i_allocated_buffer;
52     uint8_t     p_allocated_buffer[];
53 };
54
55 #ifndef NDEBUG
56 static void BlockNoRelease( block_t *b )
57 {
58     fprintf( stderr, "block %p has no release callback! This is a bug!\n", b );
59     abort();
60 }
61 #endif
62
63 void block_Init( block_t *restrict b, void *buf, size_t size )
64 {
65     /* Fill all fields to their default */
66     b->p_next = NULL;
67     b->p_buffer = buf;
68     b->i_buffer = size;
69     b->i_flags = 0;
70     b->i_nb_samples = 0;
71     b->i_pts =
72     b->i_dts = VLC_TS_INVALID;
73     b->i_length = 0;
74 #ifndef NDEBUG
75     b->pf_release = BlockNoRelease;
76 #endif
77 }
78
79 static void BlockRelease( block_t *p_block )
80 {
81     free( p_block );
82 }
83
84 static void BlockMetaCopy( block_t *restrict out, const block_t *in )
85 {
86     out->p_next    = in->p_next;
87     out->i_nb_samples = in->i_nb_samples;
88     out->i_dts     = in->i_dts;
89     out->i_pts     = in->i_pts;
90     out->i_flags   = in->i_flags;
91     out->i_length  = in->i_length;
92 }
93
94 /* Memory alignment (must be a multiple of sizeof(void*) and a power of two) */
95 #define BLOCK_ALIGN        16
96 /* Initial reserved header and footer size (must be multiple of alignment) */
97 #define BLOCK_PADDING      32
98 /* Maximum size of reserved footer before we release with realloc() */
99 #define BLOCK_WASTE_SIZE   2048
100
101 block_t *block_Alloc( size_t i_size )
102 {
103     /* We do only one malloc
104      * TODO: bench if doing 2 malloc but keeping a pool of buffer is better
105      * 2 * BLOCK_PADDING -> pre + post padding
106      */
107     block_sys_t *p_sys;
108     uint8_t *buf;
109
110 #define ALIGN(x) (((x) + BLOCK_ALIGN - 1) & ~(BLOCK_ALIGN - 1))
111 #if 0 /*def HAVE_POSIX_MEMALIGN */
112     /* posix_memalign(,16,) is much slower than malloc() on glibc.
113      * -- Courmisch, September 2009, glibc 2.5 & 2.9 */
114     const size_t i_alloc = ALIGN(sizeof(*p_sys)) + (2 * BLOCK_PADDING)
115                          + ALIGN(i_size);
116     void *ptr;
117
118     if( posix_memalign( &ptr, BLOCK_ALIGN, i_alloc ) )
119         return NULL;
120
121     p_sys = ptr;
122     buf = p_sys->p_allocated_buffer + (-sizeof(*p_sys) & (BLOCK_ALIGN - 1));
123
124 #else
125     const size_t i_alloc = sizeof(*p_sys) + BLOCK_ALIGN + (2 * BLOCK_PADDING)
126                          + ALIGN(i_size);
127     p_sys = malloc( i_alloc );
128     if( p_sys == NULL )
129         return NULL;
130
131     buf = (void *)ALIGN((uintptr_t)p_sys->p_allocated_buffer);
132
133 #endif
134     buf += BLOCK_PADDING;
135
136     block_Init( &p_sys->self, buf, i_size );
137     p_sys->self.pf_release    = BlockRelease;
138     /* Fill opaque data */
139     p_sys->i_allocated_buffer = i_alloc - sizeof(*p_sys);
140
141     return &p_sys->self;
142 }
143
144 block_t *block_Realloc( block_t *p_block, ssize_t i_prebody, size_t i_body )
145 {
146     size_t requested = i_prebody + i_body;
147
148     /* Corner case: empty block requested */
149     if( i_prebody <= 0 && i_body <= (size_t)(-i_prebody) )
150     {
151         block_Release( p_block );
152         return NULL;
153     }
154
155     if( p_block->pf_release != BlockRelease )
156     {
157         /* Special case when pf_release if overloaded
158          * TODO if used one day, then implement it in a smarter way */
159         block_t *p_dup = block_Duplicate( p_block );
160         block_Release( p_block );
161         if( !p_dup )
162             return NULL;
163
164         p_block = p_dup;
165     }
166
167     block_sys_t *p_sys = (block_sys_t *)p_block;
168     uint8_t *p_start = p_sys->p_allocated_buffer;
169     uint8_t *p_end = p_sys->p_allocated_buffer + p_sys->i_allocated_buffer;
170
171     assert( p_block->p_buffer + p_block->i_buffer <= p_end );
172     assert( p_block->p_buffer >= p_start );
173
174     /* Corner case: the current payload is discarded completely */
175     if( i_prebody <= 0 && p_block->i_buffer <= (size_t)-i_prebody )
176          p_block->i_buffer = 0; /* discard current payload */
177     if( p_block->i_buffer == 0 )
178     {
179         size_t available = p_end - p_start;
180
181         if( requested <= available )
182         {   /* Enough room: recycle buffer */
183             size_t extra = available - requested;
184
185             p_block->p_buffer = p_start + (extra / 2);
186             p_block->i_buffer = requested;
187             return p_block;
188         }
189         /* Not enough room: allocate a new buffer */
190         block_t *p_rea = block_Alloc( requested );
191         if( p_rea )
192             BlockMetaCopy( p_rea, p_block );
193         block_Release( p_block );
194         return p_rea;
195     }
196
197     /* First, shrink payload */
198
199     /* Pull payload start */
200     if( i_prebody < 0 )
201     {
202         assert( p_block->i_buffer >= (size_t)-i_prebody );
203         p_block->p_buffer -= i_prebody;
204         p_block->i_buffer += i_prebody;
205         i_body += i_prebody;
206         i_prebody = 0;
207     }
208
209     /* Trim payload end */
210     if( p_block->i_buffer > i_body )
211         p_block->i_buffer = i_body;
212
213     /* Second, reallocate the buffer if we lack space. This is done now to
214      * minimize the payload size for memory copy. */
215     assert( i_prebody >= 0 );
216     if( (size_t)(p_block->p_buffer - p_start) < (size_t)i_prebody
217      || (size_t)(p_end - p_block->p_buffer) < i_body )
218     {
219         block_t *p_rea = block_Alloc( requested );
220         if( p_rea )
221         {
222             BlockMetaCopy( p_rea, p_block );
223             p_rea->p_buffer += i_prebody;
224             p_rea->i_buffer -= i_prebody;
225             memcpy( p_rea->p_buffer, p_block->p_buffer, p_block->i_buffer );
226         }
227         block_Release( p_block );
228         if( p_rea == NULL )
229             return NULL;
230         p_block = p_rea;
231     }
232     else
233     /* We have a very large reserved footer now? Release some of it.
234      * XXX it might not preserve the alignment of p_buffer */
235     if( p_end - (p_block->p_buffer + i_body) > BLOCK_WASTE_SIZE )
236     {
237         block_t *p_rea = block_Alloc( requested );
238         if( p_rea )
239         {
240             BlockMetaCopy( p_rea, p_block );
241             p_rea->p_buffer += i_prebody;
242             p_rea->i_buffer -= i_prebody;
243             memcpy( p_rea->p_buffer, p_block->p_buffer, p_block->i_buffer );
244             block_Release( p_block );
245             p_block = p_rea;
246         }
247     }
248
249     /* NOTE: p_start and p_end are corrupted from this point */
250
251     /* Third, expand payload */
252
253     /* Push payload start */
254     if( i_prebody > 0 )
255     {
256         p_block->p_buffer -= i_prebody;
257         p_block->i_buffer += i_prebody;
258         i_body += i_prebody;
259         i_prebody = 0;
260     }
261
262     /* Expand payload to requested size */
263     p_block->i_buffer = i_body;
264
265     return p_block;
266 }
267
268
269 typedef struct
270 {
271     block_t  self;
272     void    *mem;
273 } block_heap_t;
274
275 static void block_heap_Release (block_t *self)
276 {
277     block_heap_t *block = (block_heap_t *)self;
278
279     free (block->mem);
280     free (block);
281 }
282
283 /**
284  * Creates a block from a heap allocation.
285  * This is provided by LibVLC so that manually heap-allocated blocks can safely
286  * be deallocated even after the origin plugin has been unloaded from memory.
287  *
288  * When block_Release() is called, VLC will free() the specified pointer.
289  *
290  * @param ptr base address of the heap allocation (will be free()'d)
291  * @param addr base address of the useful buffer data
292  * @param length bytes length of the useful buffer data
293  * @return NULL in case of error (ptr free()'d in that case), or a valid
294  * block_t pointer.
295  */
296 block_t *block_heap_Alloc (void *ptr, void *addr, size_t length)
297 {
298     block_heap_t *block = malloc (sizeof (*block));
299     if (block == NULL)
300     {
301         free (addr);
302         return NULL;
303     }
304
305     block_Init (&block->self, (uint8_t *)addr, length);
306     block->self.pf_release = block_heap_Release;
307     block->mem = ptr;
308     return &block->self;
309 }
310
311 #ifdef HAVE_MMAP
312 # include <sys/mman.h>
313
314 typedef struct block_mmap_t
315 {
316     block_t     self;
317     void       *base_addr;
318     size_t      length;
319 } block_mmap_t;
320
321 static void block_mmap_Release (block_t *block)
322 {
323     block_mmap_t *p_sys = (block_mmap_t *)block;
324
325     munmap (p_sys->base_addr, p_sys->length);
326     free (p_sys);
327 }
328
329 /**
330  * Creates a block from a virtual address memory mapping (mmap).
331  * This is provided by LibVLC so that mmap blocks can safely be deallocated
332  * even after the allocating plugin has been unloaded from memory.
333  *
334  * @param addr base address of the mapping (as returned by mmap)
335  * @param length length (bytes) of the mapping (as passed to mmap)
336  * @return NULL if addr is MAP_FAILED, or an error occurred (in the later
337  * case, munmap(addr, length) is invoked before returning).
338  */
339 block_t *block_mmap_Alloc (void *addr, size_t length)
340 {
341     if (addr == MAP_FAILED)
342         return NULL;
343
344     block_mmap_t *block = malloc (sizeof (*block));
345     if (block == NULL)
346     {
347         munmap (addr, length);
348         return NULL;
349     }
350
351     block_Init (&block->self, (uint8_t *)addr, length);
352     block->self.pf_release = block_mmap_Release;
353     block->base_addr = addr;
354     block->length = length;
355     return &block->self;
356 }
357 #else
358 block_t *block_mmap_Alloc (void *addr, size_t length)
359 {
360     (void)addr; (void)length; return NULL;
361 }
362 #endif
363
364
365 #ifdef WIN32
366 # include <io.h>
367 # ifdef UNDER_CE
368 #  define _get_osfhandle(a) ((long) (a))
369 # endif
370
371 static
372 ssize_t pread (int fd, void *buf, size_t count, off_t offset)
373 {
374     HANDLE handle = (HANDLE)(intptr_t)_get_osfhandle (fd);
375     if (handle == INVALID_HANDLE_VALUE)
376         return -1;
377
378     OVERLAPPED olap; olap.Offset = offset; olap.OffsetHigh = (offset >> 32);
379     DWORD written;
380     /* This braindead API will override the file pointer even if we specify
381      * an explicit read offset... So do not expect this to mix well with
382      * regular read() calls. */
383     if (ReadFile (handle, buf, count, &written, &olap))
384         return written;
385     return -1;
386 }
387 #elif !defined( HAVE_PREAD )
388 static
389 ssize_t pread(int fd, const void * buf, size_t size, off_t offset) {
390     off_t offs0;
391     ssize_t rd;
392     if ((offs0 = lseek(fd, 0, SEEK_CUR)) == (off_t)-1) return -1;
393     if (lseek(fd, offset, SEEK_SET) == (off_t)-1) return -1;
394     rd = read(fd, (void *)buf, size);
395     if (lseek(fd, offs0, SEEK_SET) == (off_t)-1) return -1;
396     return rd;
397 }
398
399 static
400 ssize_t pwrite(int fd, const void * buf, size_t size, off_t offset) {
401     off_t offs0;
402     ssize_t wr;
403     if ((offs0 = lseek(fd, 0, SEEK_CUR)) == (off_t)-1) return -1;
404     if (lseek(fd, offset, SEEK_SET) == (off_t)-1) return -1;
405     wr = write(fd, (void *)buf, size);
406     if (lseek(fd, offs0, SEEK_SET) == (off_t)-1) return -1;
407     return wr;
408 }
409 #endif
410
411 /**
412  * Loads a file into a block of memory. If possible a private file mapping is
413  * created. Otherwise, the file is read normally. On 32-bits platforms, this
414  * function will not work for very large files, due to memory space
415  * constraints. Cancellation point.
416  *
417  * @param fd file descriptor to load from
418  * @return a new block with the file content at p_buffer, and file length at
419  * i_buffer (release it with block_Release()), or NULL upon error (see errno).
420  */
421 block_t *block_File (int fd)
422 {
423     size_t length;
424     struct stat st;
425
426     /* First, get the file size */
427     if (fstat (fd, &st))
428         return NULL;
429
430     /* st_size is meaningful for regular files, shared memory and typed memory.
431      * It's also meaning for symlinks, but that's not possible with fstat().
432      * In other cases, it's undefined, and we should really not go further. */
433 #ifndef S_TYPEISSHM
434 # define S_TYPEISSHM( buf ) (0)
435 #endif
436     if (S_ISDIR (st.st_mode))
437     {
438         errno = EISDIR;
439         return NULL;
440     }
441     if (!S_ISREG (st.st_mode) && !S_TYPEISSHM (&st))
442     {
443         errno = ESPIPE;
444         return NULL;
445     }
446
447     /* Prevent an integer overflow in mmap() and malloc() */
448     if (st.st_size >= SIZE_MAX)
449     {
450         errno = ENOMEM;
451         return NULL;
452     }
453     length = (size_t)st.st_size;
454
455 #ifdef HAVE_MMAP
456     if (length > 0)
457     {
458         void *addr;
459
460         addr = mmap (NULL, length, PROT_READ|PROT_WRITE, MAP_PRIVATE, fd, 0);
461         if (addr != MAP_FAILED)
462             return block_mmap_Alloc (addr, length);
463     }
464 #endif
465
466     /* If mmap() is not implemented by the OS _or_ the filesystem... */
467     block_t *block = block_Alloc (length);
468     if (block == NULL)
469         return NULL;
470     block_cleanup_push (block);
471
472     for (size_t i = 0; i < length;)
473     {
474         ssize_t len = pread (fd, block->p_buffer + i, length - i, i);
475         if (len == -1)
476         {
477             block_Release (block);
478             block = NULL;
479             break;
480         }
481         i += len;
482     }
483     vlc_cleanup_pop ();
484     return block;
485 }
486
487 /**
488  * @section Thread-safe block queue functions
489  */
490
491 /**
492  * Internal state for block queues
493  */
494 struct block_fifo_t
495 {
496     vlc_mutex_t         lock;                         /* fifo data lock */
497     vlc_cond_t          wait;      /**< Wait for data */
498     vlc_cond_t          wait_room; /**< Wait for queue depth to shrink */
499
500     block_t             *p_first;
501     block_t             **pp_last;
502     size_t              i_depth;
503     size_t              i_size;
504     bool          b_force_wake;
505 };
506
507 block_fifo_t *block_FifoNew( void )
508 {
509     block_fifo_t *p_fifo = malloc( sizeof( block_fifo_t ) );
510     if( !p_fifo )
511         return NULL;
512
513     vlc_mutex_init( &p_fifo->lock );
514     vlc_cond_init( &p_fifo->wait );
515     vlc_cond_init( &p_fifo->wait_room );
516     p_fifo->p_first = NULL;
517     p_fifo->pp_last = &p_fifo->p_first;
518     p_fifo->i_depth = p_fifo->i_size = 0;
519     p_fifo->b_force_wake = false;
520
521     return p_fifo;
522 }
523
524 void block_FifoRelease( block_fifo_t *p_fifo )
525 {
526     block_FifoEmpty( p_fifo );
527     vlc_cond_destroy( &p_fifo->wait_room );
528     vlc_cond_destroy( &p_fifo->wait );
529     vlc_mutex_destroy( &p_fifo->lock );
530     free( p_fifo );
531 }
532
533 void block_FifoEmpty( block_fifo_t *p_fifo )
534 {
535     block_t *block;
536
537     vlc_mutex_lock( &p_fifo->lock );
538     block = p_fifo->p_first;
539     if (block != NULL)
540     {
541         p_fifo->i_depth = p_fifo->i_size = 0;
542         p_fifo->p_first = NULL;
543         p_fifo->pp_last = &p_fifo->p_first;
544     }
545     vlc_cond_broadcast( &p_fifo->wait_room );
546     vlc_mutex_unlock( &p_fifo->lock );
547
548     while (block != NULL)
549     {
550         block_t *buf;
551
552         buf = block->p_next;
553         block_Release (block);
554         block = buf;
555     }
556 }
557
558 /**
559  * Wait until the FIFO gets below a certain size (if needed).
560  *
561  * Note that if more than one thread writes to the FIFO, you cannot assume that
562  * the FIFO is actually below the requested size upon return (since another
563  * thread could have refilled it already). This is typically not an issue, as
564  * this function is meant for (relaxed) congestion control.
565  *
566  * This function may be a cancellation point and it is cancel-safe.
567  *
568  * @param fifo queue to wait on
569  * @param max_depth wait until the queue has no more than this many blocks
570  *                  (use SIZE_MAX to ignore this constraint)
571  * @param max_size wait until the queue has no more than this many bytes
572  *                  (use SIZE_MAX to ignore this constraint)
573  * @return nothing.
574  */
575 void block_FifoPace (block_fifo_t *fifo, size_t max_depth, size_t max_size)
576 {
577     vlc_testcancel ();
578
579     vlc_mutex_lock (&fifo->lock);
580     while ((fifo->i_depth > max_depth) || (fifo->i_size > max_size))
581     {
582          mutex_cleanup_push (&fifo->lock);
583          vlc_cond_wait (&fifo->wait_room, &fifo->lock);
584          vlc_cleanup_pop ();
585     }
586     vlc_mutex_unlock (&fifo->lock);
587 }
588
589 /**
590  * Immediately queue one block at the end of a FIFO.
591  * @param fifo queue
592  * @param block head of a block list to queue (may be NULL)
593  * @return total number of bytes appended to the queue
594  */
595 size_t block_FifoPut( block_fifo_t *p_fifo, block_t *p_block )
596 {
597     size_t i_size = 0, i_depth = 0;
598     block_t *p_last;
599
600     if (p_block == NULL)
601         return 0;
602     for (p_last = p_block; ; p_last = p_last->p_next)
603     {
604         i_size += p_last->i_buffer;
605         i_depth++;
606         if (!p_last->p_next)
607             break;
608     }
609
610     vlc_mutex_lock (&p_fifo->lock);
611     *p_fifo->pp_last = p_block;
612     p_fifo->pp_last = &p_last->p_next;
613     p_fifo->i_depth += i_depth;
614     p_fifo->i_size += i_size;
615     /* We queued at least one block: wake up one read-waiting thread */
616     vlc_cond_signal( &p_fifo->wait );
617     vlc_mutex_unlock( &p_fifo->lock );
618
619     return i_size;
620 }
621
622 void block_FifoWake( block_fifo_t *p_fifo )
623 {
624     vlc_mutex_lock( &p_fifo->lock );
625     if( p_fifo->p_first == NULL )
626         p_fifo->b_force_wake = true;
627     vlc_cond_broadcast( &p_fifo->wait );
628     vlc_mutex_unlock( &p_fifo->lock );
629 }
630
631 /**
632  * Dequeue the first block from the FIFO. If necessary, wait until there is
633  * one block in the queue. This function is (always) cancellation point.
634  *
635  * @return a valid block, or NULL if block_FifoWake() was called.
636  */
637 block_t *block_FifoGet( block_fifo_t *p_fifo )
638 {
639     block_t *b;
640
641     vlc_testcancel( );
642
643     vlc_mutex_lock( &p_fifo->lock );
644     mutex_cleanup_push( &p_fifo->lock );
645
646     /* Remember vlc_cond_wait() may cause spurious wakeups
647      * (on both Win32 and POSIX) */
648     while( ( p_fifo->p_first == NULL ) && !p_fifo->b_force_wake )
649         vlc_cond_wait( &p_fifo->wait, &p_fifo->lock );
650
651     vlc_cleanup_pop();
652     b = p_fifo->p_first;
653
654     p_fifo->b_force_wake = false;
655     if( b == NULL )
656     {
657         /* Forced wakeup */
658         vlc_mutex_unlock( &p_fifo->lock );
659         return NULL;
660     }
661
662     p_fifo->p_first = b->p_next;
663     p_fifo->i_depth--;
664     p_fifo->i_size -= b->i_buffer;
665
666     if( p_fifo->p_first == NULL )
667     {
668         p_fifo->pp_last = &p_fifo->p_first;
669     }
670
671     /* We don't know how many threads can queue new packets now. */
672     vlc_cond_broadcast( &p_fifo->wait_room );
673     vlc_mutex_unlock( &p_fifo->lock );
674
675     b->p_next = NULL;
676     return b;
677 }
678
679 /**
680  * Peeks the first block in the FIFO.
681  * If necessary, wait until there is one block.
682  * This function is (always) a cancellation point.
683  *
684  * @warning This function leaves the block in the FIFO.
685  * You need to protect against concurrent threads who could dequeue the block.
686  * Preferrably, there should be only one thread reading from the FIFO.
687  *
688  * @return a valid block.
689  */
690 block_t *block_FifoShow( block_fifo_t *p_fifo )
691 {
692     block_t *b;
693
694     vlc_testcancel( );
695
696     vlc_mutex_lock( &p_fifo->lock );
697     mutex_cleanup_push( &p_fifo->lock );
698
699     while( p_fifo->p_first == NULL )
700         vlc_cond_wait( &p_fifo->wait, &p_fifo->lock );
701
702     b = p_fifo->p_first;
703
704     vlc_cleanup_run ();
705     return b;
706 }
707
708 /* FIXME: not thread-safe */
709 size_t block_FifoSize( const block_fifo_t *p_fifo )
710 {
711     return p_fifo->i_size;
712 }
713
714 /* FIXME: not thread-safe */
715 size_t block_FifoCount( const block_fifo_t *p_fifo )
716 {
717     return p_fifo->i_depth;
718 }