Repository: pion/mediadevices
Pull request #214 (2020-09-13 19:17:45)

Add pull-based Broadcaster
Changes:
* Add generic io.Reader
* Add generic broadcaster
* Add specialize video broadcaster
* Add ring buffer to avoid frames being dropped


lherman-cs: @at-wat would you mind to review it?
at-wat: @lherman-cs sorry for the delay. It might take bit long to fully understand the behavior...
lherman-cs: @at-wat Please take your time! I was only letting you know that the PR is ready 😊 . No rush!
lherman-cs: @at-wat I have rebased with your changes. PTAL.

Patch:
diff --git a/pkg/io/broadcast.go b/pkg/io/broadcast.go
new file mode 100644
index 0000000..86cfcad
--- /dev/null
+++ b/pkg/io/broadcast.go
@@ -0,0 +1,162 @@
+package io
+
+import (
+	"fmt"
+	"sync/atomic"
+	"time"
+)
+
+const (
+	maskReading                = 1 << 63
+	defaultBroadcasterRingSize = 32
+	// TODO: If the data source has fps greater than 30, they'll see some
+	// 			 fps fluctuation. But, 30 fps should be enough for general cases.
+	defaultBroadcasterRingPollDuration = time.Millisecond * 33
+)
+
+var errEmptySource = fmt.Errorf("Source can't be nil")
+
+type broadcasterData struct {
+	data  interface{}
+	count uint32
+	err   error
+}
+
+type broadcasterRing struct {
+	// reading (1 bit) + reserved (31 bits) + data count (32 bits)
+	// IMPORTANT: state has to be the first element in struct, otherwise LoadUint64 will panic in 32 bits systems
+	//            due to unallignment
+	state        uint64
+	buffer       []atomic.Value
+	pollDuration time.Duration
+}
+
+func newBroadcasterRing(size uint, pollDuration time.Duration) *broadcasterRing {
+	return &broadcasterRing{buffer: make([]atomic.Value, size), pollDuration: pollDuration}
+}
+
+func (ring *broadcasterRing) index(count uint32) int {
+	return int(count) % len(ring.buffer)
+}
+
+func (ring *broadcasterRing) acquire(count uint32) func(*broadcasterData) {
+	// Reader has reached the latest data, should read from the source.
+	// Only allow 1 reader to read from the source. When there are more than 1 readers,
+	// the other readers will need to share the same data that the first reader gets from
+	// the source.
+	state := uint64(count)
+	if atomic.CompareAndSwapUint64(&ring.state, state, state|maskReading) {
+		return func(data *broadcasterData) {
+			i := ring.index(count)
+			ring.buffer[i].Store(data)
+			atomic.StoreUint64(&ring.state, uint64(count+1))
+		}
+	}
+
+	return nil
+}
+
+func (ring *broadcasterRing) get(count uint32) *broadcasterData {
+	for {
+		reading := uint64(count) | maskReading
+		// TODO: since it's lockless, it spends a lot of resources in the scheduling.
+		for atomic.LoadUint64(&ring.state) == reading {
+			// Yield current goroutine to let other goroutines to run instead
+			time.Sleep(ring.pollDuration)
+		}
+
+		i := ring.index(count)
+		data := ring.buffer[i].Load().(*broadcasterData)
+		if data.count == count {
+			return data
+		}
+
+		count++
+	}
+}
+
+func (ring *broadcasterRing) lastCount() uint32 {
+	// ring.state always keeps track the next count, so we need to subtract it by 1 to get the
+	// last count
+	return uint32(atomic.LoadUint64(&ring.state)) - 1
+}
+
+// Broadcaster is a generic pull-based broadcaster. Broadcaster is unique in a sense that
+// readers can come and go at anytime, and readers don't need to close or notify broadcaster.
+type Broadcaster struct {
+	source atomic.Value
+	buffer *broadcasterRing
+}
+
+// BroadcasterConfig is a config to control broadcaster behaviour
+type BroadcasterConfig struct {
+	// BufferSize configures the underlying ring buffer size that's being used
+	// to avoid data lost for late readers. The default value is 32.
+	BufferSize uint
+	// PollDuration configures the sleep duration in waiting for new data to come.
+	// The default value is 33 ms.
+	PollDuration time.Duration
+}
+
+// NewBroadcaster creates a new broadcaster. Source is expected to drop frames
+// when any of the readers is slower than the source.
+func NewBroadcaster(source Reader, config *BroadcasterConfig) *Broadcaster {
+	pollDuration := defaultBroadcasterRingPollDuration
+	var bufferSize uint = defaultBroadcasterRingSize
+	if config != nil {
+		if config.PollDuration != 0 {
+			pollDuration = config.PollDuration
+		}
+
+		if config.BufferSize != 0 {
+			bufferSize = config.BufferSize
+		}
+	}
+
+	var broadcaster Broadcaster
+	broadcaster.buffer = newBroadcasterRing(bufferSize, pollDuration)
+	broadcaster.ReplaceSource(source)
+
+	return &broadcaster
+}
+
+// NewReader creates a new reader. Each reader will retrieve the same data from the source.
+// copyFn is used to copy the data from the source to individual readers. Broadcaster uses a small ring
+// buffer, this means that slow readers might miss some data if they're really late and the data is no longer
+// in the ring buffer.
+func (broadcaster *Broadcaster) NewReader(copyFn func(interface{}) interface{}) Reader {
+	currentCount := broadcaster.buffer.lastCount()
+
+	return ReaderFunc(func() (data interface{}, err error) {
+		currentCount++
+		if push := broadcaster.buffer.acquire(currentCount); push != nil {
+			data, err = broadcaster.source.Load().(Reader).Read()
+			push(&broadcasterData{
+				data:  data,
+				err:   err,
+				count: currentCount,
+			})
+		} else {
+			ringData := broadcaster.buffer.get(currentCount)
+			data, err, currentCount = ringData.data, ringData.err, ringData.count
+		}
+
+		data = copyFn(data)
+		return
+	})
+}
+
+// ReplaceSource replaces the underlying source. This operation is thread safe.
+func (broadcaster *Broadcaster) ReplaceSource(source Reader) error {
+	if source == nil {
+		return errEmptySource
+	}
+
+	broadcaster.source.Store(source)
+	return nil
+}
+
+// ReplaceSource retrieves the underlying source. This operation is thread safe.
+func (broadcaster *Broadcaster) Source() Reader {
+	return broadcaster.source.Load().(Reader)
+}
diff --git a/pkg/io/reader.go b/pkg/io/reader.go
new file mode 100644
index 0000000..3bd676a
--- /dev/null
+++ b/pkg/io/reader.go
@@ -0,0 +1,14 @@
+package io
+
+// Reader is a generic data reader. In the future, interface{} should be replaced by a generic type
+// to provide strong type.
+type Reader interface {
+	Read() (interface{}, error)
+}
+
+// ReaderFunc is a proxy type for Reader
+type ReaderFunc func() (interface{}, error)
+
+func (f ReaderFunc) Read() (interface{}, error) {
+	return f()
+}
diff --git a/pkg/io/video/broadcast.go b/pkg/io/video/broadcast.go
new file mode 100644
index 0000000..efe2a0a
--- /dev/null
+++ b/pkg/io/video/broadcast.go
@@ -0,0 +1,76 @@
+package video
+
+import (
+	"fmt"
+	"image"
+
+	"github.com/pion/mediadevices/pkg/io"
+)
+
+var errEmptySource = fmt.Errorf("Source can't be nil")
+
+// Broadcaster is a specialized video broadcaster.
+type Broadcaster struct {
+	ioBroadcaster *io.Broadcaster
+}
+
+type BroadcasterConfig struct {
+	Core *io.BroadcasterConfig
+}
+
+// NewBroadcaster creates a new broadcaster. Source is expected to drop frames
+// when any of the readers is slower than the source.
+func NewBroadcaster(source Reader, config *BroadcasterConfig) *Broadcaster {
+	var coreConfig *io.BroadcasterConfig
+
+	if config != nil {
+		coreConfig = config.Core
+	}
+
+	broadcaster := io.NewBroadcaster(io.ReaderFunc(func() (interface{}, error) {
+		return source.Read()
+	}), coreConfig)
+
+	return &Broadcaster{broadcaster}
+}
+
+// NewReader creates a new reader. Each reader will retrieve the same data from the source.
+// copyFn is used to copy the data from the source to individual readers. Broadcaster uses a small ring
+// buffer, this means that slow readers might miss some data if they're really late and the data is no longer
+// in the ring buffer.
+func (broadcaster *Broadcaster) NewReader(copyFrame bool) Reader {
+	copyFn := func(src interface{}) interface{} { return src }
+
+	if copyFrame {
+		buffer := NewFrameBuffer(0)
+		copyFn = func(src interface{}) interface{} {
+			realSrc, _ := src.(image.Image)
+			buffer.StoreCopy(realSrc)
+			return buffer.Load()
+		}
+	}
+
+	reader := broadcaster.ioBroadcaster.NewReader(copyFn)
+	return ReaderFunc(func() (image.Image, error) {
+		data, err := reader.Read()
+		img, _ := data.(image.Image)
+		return img, err
+	})
+}
+
+// ReplaceSource replaces the underlying source. This operation is thread safe.
+func (broadcaster *Broadcaster) ReplaceSource(source Reader) error {
+	return broadcaster.ioBroadcaster.ReplaceSource(io.ReaderFunc(func() (interface{}, error) {
+		return source.Read()
+	}))
+}
+
+// Source retrieves the underlying source. This operation is thread safe.
+func (broadcaster *Broadcaster) Source() Reader {
+	source := broadcaster.ioBroadcaster.Source()
+	return ReaderFunc(func() (image.Image, error) {
+		data, err := source.Read()
+		img, _ := data.(image.Image)
+		return img, err
+	})
+}


Test patch:
diff --git a/pkg/io/video/broadcast_test.go b/pkg/io/video/broadcast_test.go
new file mode 100644
index 0000000..e318be2
--- /dev/null
+++ b/pkg/io/video/broadcast_test.go
@@ -0,0 +1,187 @@
+package video
+
+import (
+	"fmt"
+	"image"
+	"runtime"
+	"sync"
+	"sync/atomic"
+	"testing"
+	"time"
+)
+
+func BenchmarkBroadcast(b *testing.B) {
+	var src Reader
+	img := image.NewRGBA(image.Rect(0, 0, 1920, 1080))
+	interval := time.NewTicker(time.Millisecond * 33) // 30 fps
+	defer interval.Stop()
+	src = ReaderFunc(func() (image.Image, error) {
+		<-interval.C
+		return img, nil
+	})
+
+	for n := 1; n <= 4096; n *= 16 {
+		n := n
+
+		b.Run(fmt.Sprintf("Readers-%d", n), func(b *testing.B) {
+			b.SetParallelism(n)
+			broadcaster := NewBroadcaster(src, nil)
+			b.RunParallel(func(pb *testing.PB) {
+				reader := broadcaster.NewReader(false)
+				for pb.Next() {
+					reader.Read()
+				}
+			})
+		})
+	}
+}
+
+func TestBroadcast(t *testing.T) {
+	// https://github.com/pion/mediadevices/issues/198
+	if runtime.GOOS == "darwin" {
+		t.Skip("Skipping because Darwin CI is not reliable for timing related tests.")
+	}
+	frames := make([]image.Image, 5*30) // 5 seconds worth of frames
+	resolution := image.Rect(0, 0, 1920, 1080)
+	for i := range frames {
+		rgba := image.NewRGBA(resolution)
+		rgba.Pix[0] = uint8(i >> 24)
+		rgba.Pix[1] = uint8(i >> 16)
+		rgba.Pix[2] = uint8(i >> 8)
+		rgba.Pix[3] = uint8(i)
+		frames[i] = rgba
+	}
+
+	routinePauseConds := []struct {
+		src          bool
+		dst          bool
+		expectedFPS  float64
+		expectedDrop float64
+	}{
+		{
+			src:         false,
+			dst:         false,
+			expectedFPS: 30,
+		},
+		{
+			src:          true,
+			dst:          false,
+			expectedFPS:  20,
+			expectedDrop: 10,
+		},
+		{
+			src:          false,
+			dst:          true,
+			expectedFPS:  20,
+			expectedDrop: 10,
+		},
+	}
+
+	for _, pauseCond := range routinePauseConds {
+		pauseCond := pauseCond
+		t.Run(fmt.Sprintf("SrcPause-%v/DstPause-%v", pauseCond.src, pauseCond.dst), func(t *testing.T) {
+			for n := 1; n <= 256; n *= 16 {
+				n := n
+
+				t.Run(fmt.Sprintf("Readers-%d", n), func(t *testing.T) {
+					var src Reader
+					interval := time.NewTicker(time.Millisecond * 33) // 30 fps
+					defer interval.Stop()
+					frameCount := 0
+					frameSent := 0
+					lastSend := time.Now()
+					src = ReaderFunc(func() (image.Image, error) {
+						if pauseCond.src && frameSent == 30 {
+							time.Sleep(time.Second)
+						}
+						<-interval.C
+
+						now := time.Now()
+						if interval := now.Sub(lastSend); interval > time.Millisecond*33*3/2 {
+							// Source reader should drop frames to catch up the latest frame.
+							drop := int(interval/(time.Millisecond*33)) - 1
+							frameCount += drop
+							t.Logf("Skipped %d frames", drop)
+						}
+						lastSend = now
+						frame := frames[frameCount]
+						frameCount++
+						frameSent++
+						return frame, nil
+					})
+					broadcaster := NewBroadcaster(src, nil)
+					var done uint32
+					duration := time.Second * 3
+					fpsChan := make(chan []float64)
+
+					var wg sync.WaitGroup
+					wg.Add(n)
+					for i := 0; i < n; i++ {
+						go func() {
+							reader := broadcaster.NewReader(false)
+							count := 0
+							lastFrameCount := -1
+							droppedFrames := 0
+							wg.Done()
+							wg.Wait()
+							for atomic.LoadUint32(&done) == 0 {
+								if pauseCond.dst && count == 30 {
+									time.Sleep(time.Second)
+								}
+								frame, err := reader.Read()
+								if err != nil {
+									t.Error(err)
+								}
+								rgba := frame.(*image.RGBA)
+								var frameCount int
+								frameCount |= int(rgba.Pix[0]) << 24
+								frameCount |= int(rgba.Pix[1]) << 16
+								frameCount |= int(rgba.Pix[2]) << 8
+								frameCount |= int(rgba.Pix[3])
+
+								droppedFrames += (frameCount - lastFrameCount - 1)
+								lastFrameCount = frameCount
+								count++
+							}
+
+							fps := float64(count) / duration.Seconds()
+							if fps < pauseCond.expectedFPS-2 || fps > pauseCond.expectedFPS+2 {
+								t.Fatal("Unexpected average FPS")
+							}
+
+							droppedFramesPerSecond := float64(droppedFrames) / duration.Seconds()
+							if droppedFramesPerSecond < pauseCond.expectedDrop-2 || droppedFramesPerSecond > pauseCond.expectedDrop+2 {
+								t.Fatal("Unexpected drop count")
+							}
+
+							fpsChan <- []float64{fps, droppedFramesPerSecond, float64(lastFrameCount)}
+						}()
+					}
+
+					time.Sleep(duration)
+					atomic.StoreUint32(&done, 1)
+
+					var fpsAvg float64
+					var droppedFramesPerSecondAvg float64
+					var lastFrameCountAvg float64
+					var count int
+					for metric := range fpsChan {
+						fps, droppedFramesPerSecond, lastFrameCount := metric[0], metric[1], metric[2]
+						fpsAvg += fps
+						droppedFramesPerSecondAvg += droppedFramesPerSecond
+						lastFrameCountAvg += lastFrameCount
+						count++
+						if count == n {
+							break
+						}
+					}
+
+					t.Log("Average FPS                      :", fpsAvg/float64(n))
+					t.Log("Average dropped frames per second:", droppedFramesPerSecondAvg/float64(n))
+					t.Log("Last frame count (src)           :", frameCount)
+					t.Log("Average last frame count (dst)   :", lastFrameCountAvg/float64(n))
+				})
+			}
+		})
+	}
+}