1/*
2 * Copyright 2015 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#include "SkRWBuffer.h"
9
10#include "SkAtomics.h"
11#include "SkMalloc.h"
12#include "SkMakeUnique.h"
13#include "SkStream.h"
14
15// Force small chunks to be a page's worth
16static const size_t kMinAllocSize = 4096;
17
18struct SkBufferBlock {
19    SkBufferBlock*  fNext;      // updated by the writer
20    size_t          fUsed;      // updated by the writer
21    const size_t    fCapacity;
22
23    SkBufferBlock(size_t capacity) : fNext(nullptr), fUsed(0), fCapacity(capacity) {}
24
25    const void* startData() const { return this + 1; }
26
27    size_t avail() const { return fCapacity - fUsed; }
28    void* availData() { return (char*)this->startData() + fUsed; }
29
30    static SkBufferBlock* Alloc(size_t length) {
31        size_t capacity = LengthToCapacity(length);
32        void* buffer = sk_malloc_throw(sizeof(SkBufferBlock) + capacity);
33        return new (buffer) SkBufferBlock(capacity);
34    }
35
36    // Return number of bytes actually appended. Important that we always completely this block
37    // before spilling into the next, since the reader uses fCapacity to know how many it can read.
38    //
39    size_t append(const void* src, size_t length) {
40        this->validate();
41        size_t amount = SkTMin(this->avail(), length);
42        memcpy(this->availData(), src, amount);
43        fUsed += amount;
44        this->validate();
45        return amount;
46    }
47
48    // Do not call in the reader thread, since the writer may be updating fUsed.
49    // (The assertion is still true, but TSAN still may complain about its raciness.)
50    void validate() const {
51#ifdef SK_DEBUG
52        SkASSERT(fCapacity > 0);
53        SkASSERT(fUsed <= fCapacity);
54#endif
55    }
56
57private:
58    static size_t LengthToCapacity(size_t length) {
59        const size_t minSize = kMinAllocSize - sizeof(SkBufferBlock);
60        return SkTMax(length, minSize);
61    }
62};
63
64struct SkBufferHead {
65    mutable int32_t fRefCnt;
66    SkBufferBlock   fBlock;
67
68    SkBufferHead(size_t capacity) : fRefCnt(1), fBlock(capacity) {}
69
70    static size_t LengthToCapacity(size_t length) {
71        const size_t minSize = kMinAllocSize - sizeof(SkBufferHead);
72        return SkTMax(length, minSize);
73    }
74
75    static SkBufferHead* Alloc(size_t length) {
76        size_t capacity = LengthToCapacity(length);
77        size_t size = sizeof(SkBufferHead) + capacity;
78        void* buffer = sk_malloc_throw(size);
79        return new (buffer) SkBufferHead(capacity);
80    }
81
82    void ref() const {
83        SkASSERT(fRefCnt > 0);
84        sk_atomic_inc(&fRefCnt);
85    }
86
87    void unref() const {
88        SkASSERT(fRefCnt > 0);
89        // A release here acts in place of all releases we "should" have been doing in ref().
90        if (1 == sk_atomic_fetch_add(&fRefCnt, -1, sk_memory_order_acq_rel)) {
91            // Like unique(), the acquire is only needed on success.
92            SkBufferBlock* block = fBlock.fNext;
93            sk_free((void*)this);
94            while (block) {
95                SkBufferBlock* next = block->fNext;
96                sk_free(block);
97                block = next;
98            }
99        }
100    }
101
102    void validate(size_t minUsed, const SkBufferBlock* tail = nullptr) const {
103#ifdef SK_DEBUG
104        SkASSERT(fRefCnt > 0);
105        size_t totalUsed = 0;
106        const SkBufferBlock* block = &fBlock;
107        const SkBufferBlock* lastBlock = block;
108        while (block) {
109            block->validate();
110            totalUsed += block->fUsed;
111            lastBlock = block;
112            block = block->fNext;
113        }
114        SkASSERT(minUsed <= totalUsed);
115        if (tail) {
116            SkASSERT(tail == lastBlock);
117        }
118#endif
119    }
120};
121
122///////////////////////////////////////////////////////////////////////////////////////////////////
123// The reader can only access block.fCapacity (which never changes), and cannot access
124// block.fUsed, which may be updated by the writer.
125//
126SkROBuffer::SkROBuffer(const SkBufferHead* head, size_t available, const SkBufferBlock* tail)
127    : fHead(head), fAvailable(available), fTail(tail)
128{
129    if (head) {
130        fHead->ref();
131        SkASSERT(available > 0);
132        head->validate(available, tail);
133    } else {
134        SkASSERT(0 == available);
135        SkASSERT(!tail);
136    }
137}
138
139SkROBuffer::~SkROBuffer() {
140    if (fHead) {
141        fHead->unref();
142    }
143}
144
145SkROBuffer::Iter::Iter(const SkROBuffer* buffer) {
146    this->reset(buffer);
147}
148
149SkROBuffer::Iter::Iter(const sk_sp<SkROBuffer>& buffer) {
150    this->reset(buffer.get());
151}
152
153void SkROBuffer::Iter::reset(const SkROBuffer* buffer) {
154    fBuffer = buffer;
155    if (buffer && buffer->fHead) {
156        fBlock = &buffer->fHead->fBlock;
157        fRemaining = buffer->fAvailable;
158    } else {
159        fBlock = nullptr;
160        fRemaining = 0;
161    }
162}
163
164const void* SkROBuffer::Iter::data() const {
165    return fRemaining ? fBlock->startData() : nullptr;
166}
167
168size_t SkROBuffer::Iter::size() const {
169    if (!fBlock) {
170        return 0;
171    }
172    return SkTMin(fBlock->fCapacity, fRemaining);
173}
174
175bool SkROBuffer::Iter::next() {
176    if (fRemaining) {
177        fRemaining -= this->size();
178        if (fBuffer->fTail == fBlock) {
179            // There are more blocks, but fBuffer does not know about them.
180            SkASSERT(0 == fRemaining);
181            fBlock = nullptr;
182        } else {
183            fBlock = fBlock->fNext;
184        }
185    }
186    return fRemaining != 0;
187}
188
189///////////////////////////////////////////////////////////////////////////////////////////////////
190
191SkRWBuffer::SkRWBuffer(size_t initialCapacity) : fHead(nullptr), fTail(nullptr), fTotalUsed(0) {
192    if (initialCapacity) {
193        fHead = SkBufferHead::Alloc(initialCapacity);
194        fTail = &fHead->fBlock;
195    }
196}
197
198SkRWBuffer::~SkRWBuffer() {
199    this->validate();
200    if (fHead) {
201        fHead->unref();
202    }
203}
204
205// It is important that we always completely fill the current block before spilling over to the
206// next, since our reader will be using fCapacity (min'd against its total available) to know how
207// many bytes to read from a given block.
208//
209void SkRWBuffer::append(const void* src, size_t length, size_t reserve) {
210    this->validate();
211    if (0 == length) {
212        return;
213    }
214
215    fTotalUsed += length;
216
217    if (nullptr == fHead) {
218        fHead = SkBufferHead::Alloc(length + reserve);
219        fTail = &fHead->fBlock;
220    }
221
222    size_t written = fTail->append(src, length);
223    SkASSERT(written <= length);
224    src = (const char*)src + written;
225    length -= written;
226
227    if (length) {
228        SkBufferBlock* block = SkBufferBlock::Alloc(length + reserve);
229        fTail->fNext = block;
230        fTail = block;
231        written = fTail->append(src, length);
232        SkASSERT(written == length);
233    }
234    this->validate();
235}
236
237#ifdef SK_DEBUG
238void SkRWBuffer::validate() const {
239    if (fHead) {
240        fHead->validate(fTotalUsed, fTail);
241    } else {
242        SkASSERT(nullptr == fTail);
243        SkASSERT(0 == fTotalUsed);
244    }
245}
246#endif
247
248///////////////////////////////////////////////////////////////////////////////////////////////////
249
250class SkROBufferStreamAsset : public SkStreamAsset {
251    void validate() const {
252#ifdef SK_DEBUG
253        SkASSERT(fGlobalOffset <= fBuffer->size());
254        SkASSERT(fLocalOffset <= fIter.size());
255        SkASSERT(fLocalOffset <= fGlobalOffset);
256#endif
257    }
258
259#ifdef SK_DEBUG
260    class AutoValidate {
261        SkROBufferStreamAsset* fStream;
262    public:
263        AutoValidate(SkROBufferStreamAsset* stream) : fStream(stream) { stream->validate(); }
264        ~AutoValidate() { fStream->validate(); }
265    };
266    #define AUTO_VALIDATE   AutoValidate av(this);
267#else
268    #define AUTO_VALIDATE
269#endif
270
271public:
272    SkROBufferStreamAsset(sk_sp<SkROBuffer> buffer) : fBuffer(std::move(buffer)), fIter(fBuffer) {
273        fGlobalOffset = fLocalOffset = 0;
274    }
275
276    size_t getLength() const override { return fBuffer->size(); }
277
278    bool rewind() override {
279        AUTO_VALIDATE
280        fIter.reset(fBuffer.get());
281        fGlobalOffset = fLocalOffset = 0;
282        return true;
283    }
284
285    size_t read(void* dst, size_t request) override {
286        AUTO_VALIDATE
287        size_t bytesRead = 0;
288        for (;;) {
289            size_t size = fIter.size();
290            SkASSERT(fLocalOffset <= size);
291            size_t avail = SkTMin(size - fLocalOffset, request - bytesRead);
292            if (dst) {
293                memcpy(dst, (const char*)fIter.data() + fLocalOffset, avail);
294                dst = (char*)dst + avail;
295            }
296            bytesRead += avail;
297            fLocalOffset += avail;
298            SkASSERT(bytesRead <= request);
299            if (bytesRead == request) {
300                break;
301            }
302            // If we get here, we've exhausted the current iter
303            SkASSERT(fLocalOffset == size);
304            fLocalOffset = 0;
305            if (!fIter.next()) {
306                break;   // ran out of data
307            }
308        }
309        fGlobalOffset += bytesRead;
310        SkASSERT(fGlobalOffset <= fBuffer->size());
311        return bytesRead;
312    }
313
314    bool isAtEnd() const override {
315        return fBuffer->size() == fGlobalOffset;
316    }
317
318    SkStreamAsset* duplicate() const override { return new SkROBufferStreamAsset(fBuffer); }
319
320    size_t getPosition() const override {
321        return fGlobalOffset;
322    }
323
324    bool seek(size_t position) override {
325        AUTO_VALIDATE
326        if (position < fGlobalOffset) {
327            this->rewind();
328        }
329        (void)this->skip(position - fGlobalOffset);
330        return true;
331    }
332
333    bool move(long offset)  override{
334        AUTO_VALIDATE
335        offset += fGlobalOffset;
336        if (offset <= 0) {
337            this->rewind();
338        } else {
339            (void)this->seek(SkToSizeT(offset));
340        }
341        return true;
342    }
343
344    SkStreamAsset* fork() const override {
345        SkStreamAsset* clone = this->duplicate();
346        clone->seek(this->getPosition());
347        return clone;
348    }
349
350
351private:
352    sk_sp<SkROBuffer> fBuffer;
353    SkROBuffer::Iter  fIter;
354    size_t            fLocalOffset;
355    size_t            fGlobalOffset;
356};
357
358std::unique_ptr<SkStreamAsset> SkRWBuffer::makeStreamSnapshot() const {
359    return skstd::make_unique<SkROBufferStreamAsset>(this->makeROBufferSnapshot());
360}
361