[vlc-devel] [PATCH] lib: media: rewrite recursion into list exhaustion
Alexandre Janniaux
ajanni at videolabs.io
Thu Jul 9 18:18:11 CEST 2020
Hi,
> I think we don't really care here, but:
> - with the list, there is 1 additional malloc() per item (in
> wrap_item_in_list())
> - with the vector, there are log(n) malloc() in total
>
> So if this kind of optimization was important here, I would choose a
> vector (even without counting cache locality).
Hmm indeed you're right, it's probably not that easy.
Regards,
--
Alexandre Janniaux
Videolabs
On Thu, Jul 09, 2020 at 05:47:26PM +0200, Romain Vimont wrote:
> On Thu, Jul 09, 2020 at 05:31:11PM +0200, Alexandre Janniaux wrote:
> > Hi,
> >
> > On Thu, Jul 09, 2020 at 05:14:29PM +0200, Romain Vimont wrote:
> > > On Thu, Jul 09, 2020 at 04:23:58PM +0200, Alexandre Janniaux wrote:
> > > > As the comment described it, recursion could lead to a stack overflow
> > > > when parsing very long recursive playlist. Instead, use temporary
> > > > dynamic allocation to chain the addition requests and process them in
> > > > the same order.
> > > >
> > > > The out-of-memory errors are only returned to the user as a log and the
> > > > preparsed playlist item is truncated, which is non-optimal.
> > > > ---
> > > > lib/media.c | 83 ++++++++++++++++++++++++++++++++++++++++++++++-------
> > > > 1 file changed, 72 insertions(+), 11 deletions(-)
> > > >
> > > > diff --git a/lib/media.c b/lib/media.c
> > > > index e25d439a8a7..65a902471a1 100644
> > > > --- a/lib/media.c
> > > > +++ b/lib/media.c
> > > > @@ -181,19 +181,84 @@ static libvlc_media_t *input_item_add_subitem( libvlc_media_t *p_md,
> > > > return p_md_child;
> > > > }
> > > >
> > > > +struct vlc_item_list
> > > > +{
> > > > + struct vlc_list node;
> > > > + input_item_node_t *item;
> > > > + libvlc_media_t *media;
> > > > +};
> > > > +
> > > > +static struct vlc_item_list *
> > > > +wrap_item_in_list( libvlc_media_t *media, input_item_node_t *item )
> > > > +{
> > > > + struct vlc_item_list *node = malloc(sizeof *node);
> > >
> > > NULL-check
> > >
> >
> > Indeed thanks, fixed locally. :)
> >
> > > > + node->item = item;
> > > > + node->media = media;
> > > > + return node;
> > > > +}
> > > > +
> > > > static void input_item_add_subnode( libvlc_media_t *md,
> > > > - input_item_node_t *node )
> > > > + input_item_node_t *root )
> > > > {
> > > > - for( int i = 0; i < node->i_children; i++ )
> > > > + struct vlc_list list;
> > > > + vlc_list_init( &list );
> > > > +
> > > > + /* Retain the media because we don't want the search algorithm to release
> > > > + * it when its subitems get parsed. */
> > > > + libvlc_media_retain(md);
> > > > +
> > > > + struct vlc_item_list *node_root = wrap_item_in_list( md, root );
> > > > + if( node_root == NULL )
> > > > + goto error;
> > > > +
> > > > + /* This is a depth-first search algorithm, so stash the root of the tree
> > > > + * first, then stash its children and loop back on the last item in the
> > > > + * list until the full subtree is parsed, and eventually the full tree is
> > > > + * parsed. */
> > > > + vlc_list_append( &node_root->node, &list );
> > > > +
> > > > + while( !vlc_list_is_empty( &list ) )
> > > > {
> > > > - input_item_node_t *child = node->pp_children[i];
> > > > - libvlc_media_t *md_child = input_item_add_subitem( md, child->p_item );
> > > > + /* Pop last item in the list. */
> > > > + struct vlc_item_list *node =
> > > > + vlc_list_last_entry_or_null( &list, struct vlc_item_list, node );
> > >
> > > (nitpick: if you only append and retrieve the last item, a vector would
> > > be more appropriate I guess. But it's just a small remark, you can keep
> > > the list.)
> >
> > It's a bit more complex to use than list and have an increasing
> > worst-case insertion cost in performance,
>
> I think we don't really care here, but:
> - with the list, there is 1 additional malloc() per item (in
> wrap_item_in_list())
> - with the vector, there are log(n) malloc() in total
>
> So if this kind of optimization was important here, I would choose a
> vector (even without counting cache locality).
>
> > O(1) in access too and have a constant allocation cost in performance,
>
> (a linear allocation cost, since it requires 1 additional malloc() per
> item)
>
> > so I don't think it is worth it.
>
>
>
> >
> > (vlc_list are doubly-linked list).
> >
> > >
> > > > + vlc_list_remove(&node->node);
> > > >
> > > > - if( md_child != NULL )
> > > > + for( int i = 0; i < node->item->i_children; i++ )
> > > > {
> > > > - input_item_add_subnode( md_child, child );
> > > > - libvlc_media_release( md_child );
> > > > + input_item_node_t *child = node->item->pp_children[i];
> > > > +
> > > > + /* The media will be released when its children will be added to
> > > > + * the list. */
> > > > + libvlc_media_t *md_child = input_item_add_subitem( md, child->p_item );
> > > > +
> > > > + if( md_child != NULL )
> > > > + {
> > > > + struct vlc_item_list *submedia =
> > > > + wrap_item_in_list( md_child, child );
> > > > + if (submedia == NULL)
> > > > + goto error;
> > > > +
> > > > + /* Stash a request to parse this subtree. */
> > > > + vlc_list_append( &submedia->node, &list );
> > > > + }
> > > > +
> > > > }
> > > > +
> > > > + libvlc_media_release( node->media );
> > > > + free( node );
> > > > + }
> > > > + return;
> > > > +
> > > > +error:
> > > > + libvlc_printerr( "Not enough memory" );
> > > > +
> > > > + struct vlc_item_list *node;
> > > > + vlc_list_foreach( node, &list, node )
> > > > + {
> > > > + if( node->media != NULL )
> > > > + libvlc_media_release( node->media );
> > > > + free( node );
> > > > }
> > > > }
> > > >
> > > > @@ -212,10 +277,6 @@ static void input_item_subtree_added(input_item_t *item,
> > > >
> > > > void libvlc_media_add_subtree(libvlc_media_t *p_md, input_item_node_t *node)
> > > > {
> > > > - /* FIXME FIXME FIXME
> > > > - * Recursive function calls seem much simpler for this. But playlists are
> > > > - * untrusted and can be arbitrarily deep (e.g. with XSPF). So recursion can
> > > > - * potentially lead to plain old stack overflow. */
> > > > input_item_add_subnode( p_md, node );
> > > >
> > > > /* Construct the event */
> > > > --
> > > > 2.27.0
> > > >
> > > > _______________________________________________
> > > > vlc-devel mailing list
> > > > To unsubscribe or modify your subscription options:
> > > > https://mailman.videolan.org/listinfo/vlc-devel
> > > _______________________________________________
> > > vlc-devel mailing list
> > > To unsubscribe or modify your subscription options:
> > > https://mailman.videolan.org/listinfo/vlc-devel
> > _______________________________________________
> > vlc-devel mailing list
> > To unsubscribe or modify your subscription options:
> > https://mailman.videolan.org/listinfo/vlc-devel
> _______________________________________________
> vlc-devel mailing list
> To unsubscribe or modify your subscription options:
> https://mailman.videolan.org/listinfo/vlc-devel
More information about the vlc-devel
mailing list