1/*
2 * Copyright 2014 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#if SK_SUPPORT_GPU
9
10#include "gl/GrGLNameAllocator.h"
11#include "Test.h"
12
13////////////////////////////////////////////////////////////////////////////////
14
15class NameLeakTest {
16    static const GrGLuint kFirstName = 101;
17    static const GrGLuint kRange = 1013;
18
19public:
20    NameLeakTest(skiatest::Reporter* reporter)
21        : fReporter(reporter),
22          fAllocator(kFirstName, kFirstName + kRange),
23          fAllocatedCount(0),
24          fRandomName(kFirstName + 4 * kRange / 7) {
25        memset(fAllocatedNames, 0, sizeof(fAllocatedNames));
26    }
27
28    bool run() {
29        if (!this->allocateAllRemaining()) {
30            return false;
31        }
32
33        for (GrGLuint freeCount = 1; freeCount <= kRange; ++freeCount) {
34            if (!this->freeRandomNames(freeCount)) {
35                return false;
36            }
37            if (!this->allocateAllRemaining()) {
38                return false;
39            }
40        }
41
42        return true;
43    }
44
45private:
46    bool isAllocated(GrGLuint name) const {
47        return fAllocatedNames[name - kFirstName];
48    }
49
50    void setAllocated(GrGLuint name, bool allocated) {
51        fAllocatedNames[name - kFirstName] = allocated;
52    }
53
54    bool allocateAllRemaining() {
55        for (; fAllocatedCount < kRange; ++fAllocatedCount) {
56            GrGLuint name = fAllocator.allocateName();
57            if (0 == name) {
58                ERRORF(fReporter,
59                       "Name allocate failed, but there should still be %u free names",
60                       kRange - fAllocatedCount);
61                return false;
62            }
63            if (name < kFirstName || name >= kFirstName + kRange) {
64                ERRORF(fReporter,
65                       "Name allocate returned name %u outside its bounds [%u, %u)",
66                       name, kFirstName, kFirstName + kRange);
67                return false;
68            }
69            if (this->isAllocated(name)) {
70                ERRORF(fReporter, "Name allocate returned name that is already allocated");
71                return false;
72            }
73
74            this->setAllocated(name, true);
75        }
76
77        // Ensure it returns 0 once all the names are allocated.
78        GrGLuint name = fAllocator.allocateName();
79        if (0 != name) {
80            ERRORF(fReporter,
81                   "Name allocate did not fail when all names were already in use");
82            return false;
83        }
84
85        // Ensure every unique name is allocated.
86        for (GrGLuint i = 0; i < kRange; ++i) {
87            if (!this->isAllocated(kFirstName + i)) {
88                ERRORF(fReporter, "Not all unique names are allocated after allocateAllRemaining()");
89                return false;
90            }
91        }
92
93        return true;
94    }
95
96    bool freeRandomNames(GrGLuint count) {
97        // The values a and c make up an LCG (pseudo-random generator). These
98        // values must satisfy the Hull-Dobell Theorem (with m=kRange):
99        // http://en.wikipedia.org/wiki/Linear_congruential_generator
100        // We use our own generator to guarantee it hits each unique value
101        // within kRange exactly once before repeating.
102        const GrGLuint seed = (count + fRandomName) / 2;
103        const GrGLuint a = seed * kRange + 1;
104        const GrGLuint c = (seed * 743) % kRange;
105
106        for (GrGLuint i = 0; i < count; ++i) {
107            fRandomName = (a * fRandomName + c) % kRange;
108            const GrGLuint name = kFirstName + fRandomName;
109            if (!this->isAllocated(name)) {
110                ERRORF(fReporter, "Test bug: Should not free a not-allocated name at this point (%u)", i);
111                return false;
112            }
113
114            fAllocator.free(name);
115            this->setAllocated(name, false);
116            --fAllocatedCount;
117        }
118
119        return true;
120    }
121
122    skiatest::Reporter* fReporter;
123    GrGLNameAllocator fAllocator;
124    bool fAllocatedNames[kRange];
125    GrGLuint fAllocatedCount;
126    GrGLuint fRandomName;
127};
128
129DEF_GPUTEST(NameAllocator, reporter, factory) {
130    // Ensure no names are leaked or double-allocated during heavy usage.
131    {
132        NameLeakTest nameLeakTest(reporter);
133        nameLeakTest.run();
134    }
135
136    static const GrGLuint range = 32;
137    GrGLNameAllocator allocator(1, 1 + range);
138    for (GrGLuint i = 1; i <= range; ++i) {
139        allocator.allocateName();
140    }
141    REPORTER_ASSERT(reporter, 0 == allocator.allocateName());
142
143    // Test freeing names out of range.
144    allocator.free(allocator.firstName() - 1);
145    allocator.free(allocator.endName());
146    REPORTER_ASSERT(reporter, 0 == allocator.allocateName());
147
148    // Test freeing not-allocated names.
149    for (GrGLuint i = 1; i <= range/2; i += 2) {
150        allocator.free(i);
151    }
152    for (GrGLuint i = 1; i <= range/2; i += 2) {
153        // None of these names will be allocated.
154        allocator.free(i);
155    }
156    for (GrGLuint i = 1; i <= range/2; ++i) {
157        // Every other name will not be be allocated.
158        allocator.free(i);
159    }
160    for (GrGLuint i = 1; i <= range/2; ++i) {
161        if (0 == allocator.allocateName()) {
162            ERRORF(reporter, "Name allocate failed when there should be free names");
163            break;
164        }
165    }
166    REPORTER_ASSERT(reporter, 0 == allocator.allocateName());
167}
168
169#endif
170