From patchwork Mon Aug 5 17:53:20 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Laurent Pinchart X-Patchwork-Id: 2838872 Return-Path: X-Original-To: patchwork-linux-media@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork1.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.19.201]) by patchwork1.web.kernel.org (Postfix) with ESMTP id B9EFD9F485 for ; Mon, 5 Aug 2013 17:52:51 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id C814320354 for ; Mon, 5 Aug 2013 17:52:50 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 8B7832034A for ; Mon, 5 Aug 2013 17:52:49 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754181Ab3HERwh (ORCPT ); Mon, 5 Aug 2013 13:52:37 -0400 Received: from perceval.ideasonboard.com ([95.142.166.194]:53131 "EHLO perceval.ideasonboard.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753705Ab3HERwg (ORCPT ); Mon, 5 Aug 2013 13:52:36 -0400 Received: from avalon.ideasonboard.com (cpc8-cmbg15-2-0-cust169.5-4.cable.virginmedia.com [86.30.140.170]) by perceval.ideasonboard.com (Postfix) with ESMTPSA id 5E76635A4B; Mon, 5 Aug 2013 19:52:17 +0200 (CEST) From: Laurent Pinchart To: linux-media@vger.kernel.org Cc: linux-sh@vger.kernel.org, Hans Verkuil , Sakari Ailus , Katsuya MATSUBARA , Sylwester Nawrocki Subject: [PATCH v6 01/10] media: Add support for circular graph traversal Date: Mon, 5 Aug 2013 19:53:20 +0200 Message-Id: <1375725209-2674-2-git-send-email-laurent.pinchart+renesas@ideasonboard.com> X-Mailer: git-send-email 1.8.1.5 In-Reply-To: <1375725209-2674-1-git-send-email-laurent.pinchart+renesas@ideasonboard.com> References: <1375725209-2674-1-git-send-email-laurent.pinchart+renesas@ideasonboard.com> Sender: linux-media-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-media@vger.kernel.org X-Spam-Status: No, score=-6.9 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_HI, RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=unavailable version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP The graph traversal API (media_entity_graph_walk_*) doesn't support cyclic graphs and will fail to correctly walk a graph when circular links exist. Support circular graph traversal by checking whether an entity has already been visited before pushing it to the stack. Signed-off-by: Laurent Pinchart Acked-by: Sakari Ailus Acked-by: Hans Verkuil --- drivers/media/media-entity.c | 14 +++++++++++--- include/media/media-entity.h | 4 ++++ 2 files changed, 15 insertions(+), 3 deletions(-) diff --git a/drivers/media/media-entity.c b/drivers/media/media-entity.c index cb30ffb..2c286c3 100644 --- a/drivers/media/media-entity.c +++ b/drivers/media/media-entity.c @@ -20,6 +20,7 @@ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ +#include #include #include #include @@ -121,7 +122,6 @@ static struct media_entity *stack_pop(struct media_entity_graph *graph) return entity; } -#define stack_peek(en) ((en)->stack[(en)->top - 1].entity) #define link_top(en) ((en)->stack[(en)->top].link) #define stack_top(en) ((en)->stack[(en)->top].entity) @@ -140,6 +140,12 @@ void media_entity_graph_walk_start(struct media_entity_graph *graph, { graph->top = 0; graph->stack[graph->top].entity = NULL; + bitmap_zero(graph->entities, MEDIA_ENTITY_ENUM_MAX_ID); + + if (WARN_ON(entity->id >= MEDIA_ENTITY_ENUM_MAX_ID)) + return; + + __set_bit(entity->id, graph->entities); stack_push(graph, entity); } EXPORT_SYMBOL_GPL(media_entity_graph_walk_start); @@ -180,9 +186,11 @@ media_entity_graph_walk_next(struct media_entity_graph *graph) /* Get the entity in the other end of the link . */ next = media_entity_other(entity, link); + if (WARN_ON(next->id >= MEDIA_ENTITY_ENUM_MAX_ID)) + return NULL; - /* Was it the entity we came here from? */ - if (next == stack_peek(graph)) { + /* Has the entity already been visited? */ + if (__test_and_set_bit(next->id, graph->entities)) { link_top(graph)++; continue; } diff --git a/include/media/media-entity.h b/include/media/media-entity.h index 06bacf9..10df551 100644 --- a/include/media/media-entity.h +++ b/include/media/media-entity.h @@ -23,6 +23,7 @@ #ifndef _MEDIA_ENTITY_H #define _MEDIA_ENTITY_H +#include #include #include @@ -113,12 +114,15 @@ static inline u32 media_entity_subtype(struct media_entity *entity) } #define MEDIA_ENTITY_ENUM_MAX_DEPTH 16 +#define MEDIA_ENTITY_ENUM_MAX_ID 64 struct media_entity_graph { struct { struct media_entity *entity; int link; } stack[MEDIA_ENTITY_ENUM_MAX_DEPTH]; + + DECLARE_BITMAP(entities, MEDIA_ENTITY_ENUM_MAX_ID); int top; };