1 // Copyright (c) 2012- PPSSPP Project.
2 
3 // This program is free software: you can redistribute it and/or modify
4 // it under the terms of the GNU General Public License as published by
5 // the Free Software Foundation, version 2.0 or later versions.
6 
7 // This program is distributed in the hope that it will be useful,
8 // but WITHOUT ANY WARRANTY; without even the implied warranty of
9 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10 // GNU General Public License 2.0 for more details.
11 
12 // A copy of the GPL 2.0 should have been included with the program.
13 // If not, see http://www.gnu.org/licenses/
14 
15 // Official git repository and contact information can be found at
16 // https://github.com/hrydgard/ppsspp and http://www.ppsspp.org/.
17 
18 #pragma once
19 
20 #include "Core/HLE/sceKernel.h"
21 #include "Common/Serialize/Serializer.h"
22 
23 struct ThreadQueueList {
24 	// Number of queues (number of priority levels starting at 0.)
25 	static const int NUM_QUEUES = 128;
26 	// Initial number of threads a single queue can handle.
27 	static const int INITIAL_CAPACITY = 32;
28 
29 	struct Queue {
30 		// Next ever-been-used queue (worse priority.)
31 		Queue *next;
32 		// First valid item in data.
33 		int first;
34 		// One after last valid item in data.
35 		int end;
36 		// A too-large array with room on the front and end.
37 		SceUID *data;
38 		// Size of data array.
39 		int capacity;
40 
sizeThreadQueueList::Queue41 		inline int size() const {
42 			return end - first;
43 		}
emptyThreadQueueList::Queue44 		inline bool empty() const {
45 			return first == end;
46 		}
fullThreadQueueList::Queue47 		inline int full() const {
48 			return end == capacity;
49 		}
50 	};
51 
ThreadQueueListThreadQueueList52 	ThreadQueueList() {
53 		memset(queues, 0, sizeof(queues));
54 		first = invalid();
55 	}
56 
~ThreadQueueListThreadQueueList57 	~ThreadQueueList() {
58 		clear();
59 	}
60 
61 	// Only for debugging, returns priority level.
containsThreadQueueList62 	int contains(const SceUID uid) {
63 		for (int i = 0; i < NUM_QUEUES; ++i) {
64 			if (queues[i].data == nullptr)
65 				continue;
66 
67 			Queue *cur = &queues[i];
68 			for (int j = cur->first; j < cur->end; ++j) {
69 				if (cur->data[j] == uid)
70 					return i;
71 			}
72 		}
73 
74 		return -1;
75 	}
76 
pop_firstThreadQueueList77 	inline SceUID pop_first() {
78 		Queue *cur = first;
79 		while (cur != invalid()) {
80 			if (cur->size() > 0)
81 				return cur->data[cur->first++];
82 			cur = cur->next;
83 		}
84 
85 		_dbg_assert_msg_(false, "ThreadQueueList should not be empty.");
86 		return 0;
87 	}
88 
pop_first_betterThreadQueueList89 	inline SceUID pop_first_better(u32 priority) {
90 		Queue *cur = first;
91 		// Don't bother looking past (worse than) this priority.
92 		Queue *stop = &queues[priority];
93 		while (cur < stop) {
94 			if (cur->size() > 0)
95 				return cur->data[cur->first++];
96 			cur = cur->next;
97 		}
98 
99 		return 0;
100 	}
101 
peek_firstThreadQueueList102 	inline SceUID peek_first() {
103 		Queue *cur = first;
104 		while (cur != invalid()) {
105 			if (cur->size() > 0)
106 				return cur->data[cur->first];
107 			cur = cur->next;
108 		}
109 
110 		return 0;
111 	}
112 
push_frontThreadQueueList113 	inline void push_front(u32 priority, const SceUID threadID) {
114 		Queue *cur = &queues[priority];
115 		cur->data[--cur->first] = threadID;
116 		// If we ran out of room toward the front, add more room for next time.
117 		if (cur->first == 0)
118 			rebalance(priority);
119 	}
120 
push_backThreadQueueList121 	inline void push_back(u32 priority, const SceUID threadID) {
122 		Queue *cur = &queues[priority];
123 		cur->data[cur->end++] = threadID;
124 		if (cur->full())
125 			rebalance(priority);
126 	}
127 
removeThreadQueueList128 	inline void remove(u32 priority, const SceUID threadID) {
129 		Queue *cur = &queues[priority];
130 		_dbg_assert_msg_(cur->next != nullptr, "ThreadQueueList::Queue should already be linked up.");
131 
132 		for (int i = cur->first; i < cur->end; ++i) {
133 			if (cur->data[i] == threadID) {
134 				// How many more after this one?
135 				int remaining = cur->end - i;
136 				// If there are more, move them into place.
137 				if (remaining > 0)
138 					memmove(&cur->data[i], &cur->data[i + 1], remaining * sizeof(SceUID));
139 
140 				// Now we're one shorter.
141 				--cur->end;
142 				return;
143 			}
144 		}
145 
146 		// Wasn't there.
147 	}
148 
rotateThreadQueueList149 	inline void rotate(u32 priority) {
150 		Queue *cur = &queues[priority];
151 		_dbg_assert_msg_(cur->next != nullptr, "ThreadQueueList::Queue should already be linked up.");
152 
153 		if (cur->size() > 1) {
154 			// Grab the front and push it on the end.
155 			cur->data[cur->end++] = cur->data[cur->first++];
156 			if (cur->full())
157 				rebalance(priority);
158 		}
159 	}
160 
clearThreadQueueList161 	inline void clear() {
162 		for (int i = 0; i < NUM_QUEUES; ++i) {
163 			if (queues[i].data != nullptr)
164 				free(queues[i].data);
165 		}
166 		memset(queues, 0, sizeof(queues));
167 		first = invalid();
168 	}
169 
emptyThreadQueueList170 	inline bool empty(u32 priority) const {
171 		const Queue *cur = &queues[priority];
172 		return cur->empty();
173 	}
174 
prepareThreadQueueList175 	inline void prepare(u32 priority) {
176 		Queue *cur = &queues[priority];
177 		if (cur->next == nullptr)
178 			link(priority, INITIAL_CAPACITY);
179 	}
180 
DoStateThreadQueueList181 	void DoState(PointerWrap &p) {
182 		auto s = p.Section("ThreadQueueList", 1);
183 		if (!s)
184 			return;
185 
186 		int numQueues = NUM_QUEUES;
187 		Do(p, numQueues);
188 		if (numQueues != NUM_QUEUES) {
189 			p.SetError(p.ERROR_FAILURE);
190 			ERROR_LOG(SCEKERNEL, "Savestate loading error: invalid data");
191 			return;
192 		}
193 
194 		if (p.mode == p.MODE_READ)
195 			clear();
196 
197 		for (int i = 0; i < NUM_QUEUES; ++i) {
198 			Queue *cur = &queues[i];
199 			int size = cur->size();
200 			Do(p, size);
201 			int capacity = cur->capacity;
202 			Do(p, capacity);
203 
204 			if (capacity == 0)
205 				continue;
206 
207 			if (p.mode == p.MODE_READ) {
208 				link(i, capacity);
209 				cur->first = (cur->capacity - size) / 2;
210 				cur->end = cur->first + size;
211 			}
212 
213 			if (size != 0)
214 				DoArray(p, &cur->data[cur->first], size);
215 		}
216 	}
217 
218 private:
invalidThreadQueueList219 	Queue *invalid() const {
220 		return (Queue *)-1;
221 	}
222 
223 	// Initialize a priority level and link to other queues.
linkThreadQueueList224 	void link(u32 priority, int size) {
225 		_dbg_assert_msg_(queues[priority].data == nullptr, "ThreadQueueList::Queue should only be initialized once.");
226 
227 		// Make sure we stay a multiple of INITIAL_CAPACITY.
228 		if (size <= INITIAL_CAPACITY)
229 			size = INITIAL_CAPACITY;
230 		else {
231 			int goal = size;
232 			size = INITIAL_CAPACITY;
233 			while (size < goal)
234 				size *= 2;
235 		}
236 
237 		// Allocate the queue.
238 		Queue *cur = &queues[priority];
239 		cur->data = (SceUID *)malloc(sizeof(SceUID) * size);
240 		cur->capacity = size;
241 		// Start smack in the middle so it can move both directions.
242 		cur->first = size / 2;
243 		cur->end = size / 2;
244 
245 		for (int i = (int)priority - 1; i >= 0; --i) {
246 			// This queue is before ours, and points past us.
247 			// We'll have it point to our new queue, inserting into the chain.
248 			if (queues[i].next != nullptr) {
249 				cur->next = queues[i].next;
250 				queues[i].next = cur;
251 				return;
252 			}
253 		}
254 
255 		// Never found above - that means there's no better queue yet.
256 		// The new one is now first, and whoever was first is after it.
257 		cur->next = first;
258 		first = cur;
259 	}
260 
261 	// Move or allocate as necessary to maintain free space on both sides.
rebalanceThreadQueueList262 	void rebalance(u32 priority) {
263 		Queue *cur = &queues[priority];
264 		int size = cur->size();
265 		// Basically full.  Time for a larger queue?
266 		if (size >= cur->capacity - 2) {
267 			int new_capacity = cur->capacity * 2;
268 			SceUID *new_data = (SceUID *)realloc(cur->data, new_capacity * sizeof(SceUID));
269 			if (new_data != nullptr) {
270 				// Success, it's bigger now.
271 				cur->capacity = new_capacity;
272 				cur->data = new_data;
273 			}
274 		}
275 
276 		// If we center all the items, it should start here.
277 		int newFirst = (cur->capacity - size) / 2;
278 		if (newFirst != cur->first) {
279 			memmove(&cur->data[newFirst], &cur->data[cur->first], size * sizeof(SceUID));
280 			cur->first = newFirst;
281 			cur->end = newFirst + size;
282 		}
283 	}
284 
285 	// The first queue that's ever been used.
286 	Queue *first;
287 	// The priority level queues of thread ids.
288 	Queue queues[NUM_QUEUES];
289 };
290