[libcamera-devel] [RFC v1 1/2] libcamera: media_device: Add enumerateMediaWalks() helper

[Naushir Patuck]

Add a new helper function to the MediaDevice class which returns a vector of
all possible media device topologies starting at the sensor entity and walking
to an endpoint for the media device. Each of these topologies is called a
MediaWalk. For each entity in a MediaWalk, we store a MediaEntity pointer
together with the source and sink MediaLink pointers.

As an example, consider the media graph below:

+----------+
|   CSI2   |
 +-----^----+
       |
   +---+---+
   |  Mux1 <-------+
   +--^----+       |
      |            |
+-----+---+    +---+---+
| Sensor1 |    |  Mux2 |<--+
+---------+    +-^-----+   |
                 |         |
         +-------+-+   +---+-----+
         | Sensor2 |   | Sensor3 |
         +---------+   +---------+

This would return three MediaDevice::MediaWalk structures looking like:

1)
+----------+
|   CSI2   |
+-----^----+
      |
+-----+----+
|   Mux1   |
+-----^----+
      |
+-----+----+
| Sensor1  |
+----------+

2)
+----------+
|   CSI2   |
+-----^----+
      |
+-----+----+
|   Mux1   |
+-----^----+
      |
+-----+----+
|   Mux2   |
+-----^----+
      |
+-----+----+
| Sensor2  |
+----------+

3)
+----------+
|   CSI2   |
+-----^----+
      |
+-----+----+
|   Mux1   |
+-----^----+
      |
+-----+----+
|   Mux2   |
+-----^----+
      |
+-----+----+
| Sensor3  |
+----------+

Signed-off-by: Naushir Patuck <naush at raspberrypi.com>
---
 include/libcamera/internal/media_device.h |  12 ++
 src/libcamera/media_device.cpp            | 135 ++++++++++++++++++++++
 2 files changed, 147 insertions(+)

diff --git a/include/libcamera/internal/media_device.h b/include/libcamera/internal/media_device.h
index 6e2a63f38229..63fcbe423eb9 100644
--- a/include/libcamera/internal/media_device.h
+++ b/include/libcamera/internal/media_device.h
@@ -25,6 +25,13 @@ namespace libcamera {
 class MediaDevice : protected Loggable
 {
 public:
+	struct EntityParams {
+		MediaEntity *entity;
+		MediaLink *sinkLink;
+		MediaLink *sourceLink;
+	};
+	using MediaWalk = std::vector<EntityParams>;
+
 	MediaDevice(const std::string &deviceNode);
 	~MediaDevice();
 
@@ -47,6 +54,8 @@ public:
 	const std::vector<MediaEntity *> &entities() const { return entities_; }
 	MediaEntity *getEntityByName(const std::string &name) const;
 
+	std::vector<MediaWalk> enumerateMediaWalks() const;
+
 	MediaLink *link(const std::string &sourceName, unsigned int sourceIdx,
 			const std::string &sinkName, unsigned int sinkIdx);
 	MediaLink *link(const MediaEntity *source, unsigned int sourceIdx,
@@ -77,6 +86,9 @@ private:
 	friend int MediaLink::setEnabled(bool enable);
 	int setupLink(const MediaLink *link, unsigned int flags);
 
+	void walkGraph(std::vector<MediaWalk> *mediaWalks, MediaWalk *walk,
+		       MediaEntity *entity, MediaLink *sinkLink) const;
+
 	std::string driver_;
 	std::string deviceNode_;
 	std::string model_;
diff --git a/src/libcamera/media_device.cpp b/src/libcamera/media_device.cpp
index 941f86c25f66..60b397e205a2 100644
--- a/src/libcamera/media_device.cpp
+++ b/src/libcamera/media_device.cpp
@@ -340,6 +340,105 @@ MediaEntity *MediaDevice::getEntityByName(const std::string &name) const
 	return nullptr;
 }
 
+/**
+ * \fn MediaDevice::enumerateMediaWalks()
+ * \brief Retrieve the list of all possible MediaWalks available to this device
+ *
+ * Enumerate the media graph and return all possible permutations of unique
+ * sub-graphs where the first entity is a sensor device. These sub-graphs are
+ * stored as a \a MediaDevice::MediaWalk structure, where each element gives the
+ * device entity and associated sink pad link. The first entity in this structure
+ * is asensor device, with the sink pad link set to a nullptr.
+ *
+ * As an example, consider the media graph below:
+ *
+ *  +----------+
+ *  |   CSI2   |
+ *  +-----^----+
+ *        |
+ *    +---+---+
+ *    |  Mux1 <-------+
+ *    +--^----+       |
+ *       |            |
+ * +-----+---+    +---+---+
+ * | Sensor1 |    |  Mux2 |<--+
+ * +---------+    +-^-----+   |
+ *                  |         |
+ *          +-------+-+   +---+-----+
+ *          | Sensor2 |   | Sensor3 |
+ *          +---------+   +---------+
+ *
+ * This would return three \a MediaDevice::MediaWalk structures looking like:
+ *
+ * 1)
+ * +----------+
+ * |   CSI2   |
+ * +-----^----+
+ *       |
+ * +-----+----+
+ * |   Mux1   |
+ * +-----^----+
+ *       |
+ * +-----+----+
+ * | Sensor1  |
+ * +----------+
+ *
+ * 2)
+ * +----------+
+ * |   CSI2   |
+ * +-----^----+
+ *       |
+ * +-----+----+
+ * |   Mux1   |
+ * +-----^----+
+ *       |
+ * +-----+----+
+ * |   Mux2   |
+ * +-----^----+
+ *       |
+ * +-----+----+
+ * | Sensor2  |
+ * +----------+
+ *
+ * 3)
+ * +----------+
+ * |   CSI2   |
+ * +-----^----+
+ *       |
+ * +-----+----+
+ * |   Mux1   |
+ * +-----^----+
+ *       |
+ * +-----+----+
+ * |   Mux2   |
+ * +-----^----+
+ *       |
+ * +-----+----+
+ * | Sensor3  |
+ * +----------+
+ *
+ * \return A vector of MediaWalk structures available
+ */
+std::vector<MediaDevice::MediaWalk> MediaDevice::enumerateMediaWalks() const
+{
+	std::vector<MediaWalk> mediaWalks;
+
+	for (MediaEntity *entity : entities_) {
+		/* Only perform enumeration starting with sensor entities */
+		if (entity->function() != MEDIA_ENT_F_CAM_SENSOR)
+			continue;
+		/*
+		 * Start with an empty MediaWalk structure, and walk the graph
+		 * with the sensor entity at the top, and a nullptr as the sink
+		 * pad link.
+		 */
+		mediaWalks.push_back({});
+		walkGraph(&mediaWalks, &mediaWalks.back(), entity, nullptr);
+	}
+
+	return mediaWalks;
+}
+
 /**
  * \brief Retrieve the MediaLink connecting two pads, identified by entity
  * names and pad indexes
@@ -800,4 +899,40 @@ int MediaDevice::setupLink(const MediaLink *link, unsigned int flags)
 	return 0;
 }
 
+void MediaDevice::walkGraph(std::vector<MediaWalk> *mediaWalks, MediaWalk *walk,
+			    MediaEntity *entity, MediaLink *sinkLink) const
+{
+	bool newWalk = false;
+
+	walk->push_back({ entity, sinkLink, nullptr });
+
+	for (const MediaPad *pad : entity->pads()) {
+		/* We only walk down the graph, so ignore any sink pads */
+		if (pad->flags() & MEDIA_PAD_FL_SINK)
+			continue;
+
+		for (MediaLink *nextLink : pad->links()) {
+			MediaDevice::MediaWalk *nextWalk = walk;
+			/*
+			 * If this is a new branch in the graph, create a new
+			 * MediaWalk structure in our list, and populate it with
+			 * a copy of the curret MediaWalk. Any subsequent recursion
+			 * into this graph branch will cause it to diverge.
+			 */
+			if (newWalk) {
+				mediaWalks->push_back(*walk);
+				nextWalk = &mediaWalks->back();
+			}
+
+			/* Record the source pad link for the current entity */
+			walk->back().sourceLink = nextLink;
+
+			/* Recurse into the next entity for this source pad link */
+			MediaEntity *nextEntity = nextLink->sink()->entity();
+			walkGraph(mediaWalks, nextWalk, nextEntity, nextLink);
+			newWalk = true;
+		}
+	}
+}
+
 } /* namespace libcamera */
-- 
2.25.1