[vlc-devel] [PATCH] lib: media: rewrite recursion into list exhaustion

[Alexandre Janniaux]

Hi,

I forgot to add the -v2 but I basically change:
 - null check in wrap_item_in_list
 - libvlc_media_release when failure while the item
   is not in the list yet.
 - input_item_add_subitem is now called with node->media
   instead for md.

I considered it probably needed an additional review,
thank you for your time.

Regards,
--
Alexandre Janniaux
Videolabs

On Tue, Jul 14, 2020 at 10:18:05PM +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 | 89 ++++++++++++++++++++++++++++++++++++++++++++++-------
>  1 file changed, 78 insertions(+), 11 deletions(-)
>
> diff --git a/lib/media.c b/lib/media.c
> index 55f30246229..8dee1ca50cb 100644
> --- a/lib/media.c
> +++ b/lib/media.c
> @@ -181,19 +181,90 @@ 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 );
> +    if( node == NULL )
> +        return NULL;
> +    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 )
> +    {
> +        libvlc_media_release(md);
> +        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 );
> +        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( node->media, child->p_item );
> +            if( md_child == NULL )
> +                goto error;
> +
> +            struct vlc_item_list *submedia =
> +                wrap_item_in_list( md_child, child );
> +            if (submedia == NULL)
> +            {
> +                libvlc_media_release( md_child );
> +                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 +283,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
>