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