GCC Code Coverage Report

Directory: src/
File: src/support/queues.c
Date: 2024-11-22 17:07:10
Exec Total Coverage
Lines: 151 160 94.4%
Functions: 20 21 95.2%
Branches: 98 112 87.5%
Line Branch Exec Source
1 /*********************************************************************************/
2 /* Copyright 2009-2021 Barcelona Supercomputing Center */
3 /* */
4 /* This file is part of the DLB library. */
5 /* */
6 /* DLB is free software: you can redistribute it and/or modify */
7 /* it under the terms of the GNU Lesser General Public License as published by */
8 /* the Free Software Foundation, either version 3 of the License, or */
9 /* (at your option) any later version. */
10 /* */
11 /* DLB is distributed in the hope that it will be useful, */
12 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
13 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
14 /* GNU Lesser General Public License for more details. */
15 /* */
16 /* You should have received a copy of the GNU Lesser General Public License */
17 /* along with DLB. If not, see <https://www.gnu.org/licenses/>. */
18 /*********************************************************************************/
19
20 #ifdef HAVE_CONFIG_H
21 #include <config.h>
22 #endif
23
24 #include "support/queues.h"
25
26 #include "support/debug.h"
27 #include "apis/dlb_errors.h"
28
29 #include <string.h>
30
31 enum { NOBODY = 0 };
32
33 /*** queue_lewi_reqs_t ***********************************************************/
34
35 12 void queue_lewi_reqs_init(queue_lewi_reqs_t *queue) {
36 12 memset(queue, 0, sizeof(*queue));
37 12 }
38
39 1206 unsigned int queue_lewi_reqs_size(const queue_lewi_reqs_t *queue) {
40 1206 return queue->head;
41 }
42
43 /* Remove entry with given <pid> and pack list, return previous value if exists */
44 378 unsigned int queue_lewi_reqs_remove(queue_lewi_reqs_t *queue, pid_t pid) {
45
46
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 377 times.
 378 if (unlikely(pid == 0)) return 0;
47
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 341 times.
 377 if (queue->head == 0) return 0;
48
49 /* The queue does not need to be ordered. Find element to remove and swap
50 * last position */
51
2/2
✓ Branch 0 taken 12702 times.
✓ Branch 1 taken 43 times.
 12745 for (unsigned int i=0; i < queue->head; ++i) {
52 12702 lewi_request_t *request = &queue->queue[i];
53
2/2
✓ Branch 0 taken 298 times.
✓ Branch 1 taken 12404 times.
 12702 if (request->pid == pid) {
54 // return value
55 298 int howmany = request->howmany;
56
57
2/2
✓ Branch 0 taken 204 times.
✓ Branch 1 taken 94 times.
 298 if (i+1 < queue->head) {
58 // this is not the last element, copy last one here
59 204 *request = queue->queue[queue->head-1];
60 }
61 298 --queue->head;
62
63 298 return howmany;
64 }
65 }
66
67 43 return 0;
68 }
69
70 /* Push entry with given <pid>, add value if already present */
71 924 int queue_lewi_reqs_push(queue_lewi_reqs_t *queue, pid_t pid, unsigned int howmany) {
72
73
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 923 times.
 924 if (unlikely(pid == 0)) return DLB_NOUPDT;
74
75 /* Remove entry if value is reset to 0 */
76
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 922 times.
 923 if (howmany == 0) {
77 1 queue_lewi_reqs_remove(queue, pid);
78 1 return DLB_SUCCESS;
79 }
80
81 /* Find entry, if exists */
82 unsigned int i;
83
2/2
✓ Branch 0 taken 33242 times.
✓ Branch 1 taken 367 times.
 33609 for (i=0; i<queue->head; ++i) {
84
2/2
✓ Branch 0 taken 555 times.
✓ Branch 1 taken 32687 times.
 33242 if (queue->queue[i].pid == pid) {
85 /* Found, just update value */
86 555 queue->queue[i].howmany += howmany;
87 555 return DLB_SUCCESS;
88 }
89 }
90
91 /* No existing entry and 'head' points to the last position, which is reserved */
92
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 366 times.
 367 if (queue->head == QUEUE_LEWI_REQS_SIZE-1) {
93 1 return DLB_ERR_REQST;
94 }
95
96 /* 'i' (and 'head') points the new spot. Add entry. */
97 366 queue->queue[i] = (const lewi_request_t) {
98 .pid = pid,
99 .howmany = howmany,
100 };
101 366 ++queue->head;
102 366 return DLB_SUCCESS;
103 }
104
105 /* Remove entries with no values (howmany == 0) */
106 100 static void queue_lewi_reqs_pack(queue_lewi_reqs_t *queue) {
107 unsigned int i, i_write;
108
2/2
✓ Branch 0 taken 119 times.
✓ Branch 1 taken 100 times.
 219 for (i=0, i_write=0; i<queue->head; ++i) {
109
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 31 times.
 119 if (queue->queue[i].howmany > 0) {
110
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 87 times.
 88 if (i != i_write) {
111 1 queue->queue[i_write] = queue->queue[i];
112 }
113 88 ++i_write;
114 }
115 }
116 100 queue->head = i_write;
117 100 }
118
119 /* Sort in descending order by number of requests */
120 22 static int sort_queue_lewi_reqs(const void *elem1, const void *elem2) {
121 22 return ((lewi_request_t*)elem2)->howmany - ((lewi_request_t*)elem1)->howmany;
122 }
123
124 /* Pop ncpus from the queue in an equal distribution, return array of accepted requests
125 * by argument, and number of CPUs not assigned */
126 101 unsigned int queue_lewi_reqs_pop_ncpus(queue_lewi_reqs_t *queue, unsigned int ncpus,
127 lewi_request_t *requests, unsigned int *nreqs, unsigned int maxreqs) {
128
129 101 unsigned int queue_size = queue_lewi_reqs_size(queue);
130
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 100 times.
 101 if (queue_size == 0) {
131 1 *nreqs = 0;
132 1 return ncpus;
133 }
134
135 /* For evenly distribute CPU removal, we need to sort the queue by number
136 * of requests per process */
137 100 qsort(queue->queue, queue_size, sizeof(queue->queue[0]), sort_queue_lewi_reqs);
138
139
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 100 times.
 100 ensure(queue->queue[queue->head-1].howmany > 0, "Empty spots in the queue");
140
141 unsigned int i, j;
142
4/6
✓ Branch 0 taken 119 times.
✓ Branch 1 taken 100 times.
✓ Branch 2 taken 119 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 119 times.
✗ Branch 5 not taken.
 219 for (i = queue->head, j = 0; i-- > 0 && ncpus > 0 && j < maxreqs; ) {
143 119 lewi_request_t *request = &queue->queue[i];
144 /* For every iteration, we compute the CPUs to be popped by computing
145 * the minimum between an even distribution and the current request
146 * value. */
147 119 unsigned int ncpus_popped = min_uint(ncpus/(i+1), request->howmany);
148
2/2
✓ Branch 0 taken 117 times.
✓ Branch 1 taken 2 times.
 119 if (ncpus_popped > 0) {
149 /* Assign number of CPUs to output array */
150 117 requests[j++] = (const lewi_request_t) {
151 117 .pid = request->pid,
152 .howmany = ncpus_popped,
153 };
154
155 /* Remove the CPUs from the queue */
156 117 request->howmany -= ncpus_popped;
157
158 /* Update number of CPUs to be popped */
159 117 ncpus -= ncpus_popped;
160 }
161 }
162
163 /* Update output array size */
164 100 *nreqs = j;
165
166 /* Pack queue, remove elements if howmany reached 0 */
167 100 queue_lewi_reqs_pack(queue);
168
169 100 return ncpus;
170 }
171
172 /* Return the value of requests of the given pid */
173 313 unsigned int queue_lewi_reqs_get(queue_lewi_reqs_t *queue, pid_t pid) {
174
175
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 313 times.
 313 if (unlikely(pid == 0)) return 0;
176
177
2/2
✓ Branch 0 taken 32725 times.
✓ Branch 1 taken 22 times.
 32747 for (unsigned int i = 0; i < queue->head; ++i) {
178
2/2
✓ Branch 0 taken 291 times.
✓ Branch 1 taken 32434 times.
 32725 if (queue->queue[i].pid == pid) {
179 291 return queue->queue[i].howmany;
180 }
181 }
182
183 22 return 0;
184 }
185
186
187 /*** queue_proc_reqs_t ***********************************************************/
188
189 3 void queue_proc_reqs_init(queue_proc_reqs_t *queue) {
190 3 memset(queue, 0, sizeof(*queue));
191 3 }
192
193 16406 unsigned int queue_proc_reqs_size(const queue_proc_reqs_t *queue) {
194 16406 return queue->head >= queue->tail
195 8208 ? queue->head - queue->tail
196
2/2
✓ Branch 0 taken 8208 times.
✓ Branch 1 taken 8198 times.
 16406 : QUEUE_PROC_REQS_SIZE - queue->tail + queue->head;
197 }
198
199 8192 process_request_t* queue_proc_reqs_front(queue_proc_reqs_t *queue) {
200 8192 return &queue->queue[queue->tail];
201 }
202
203 12297 process_request_t* queue_proc_reqs_back(queue_proc_reqs_t *queue) {
204
2/2
✓ Branch 0 taken 4102 times.
✓ Branch 1 taken 8195 times.
 12297 unsigned int prev_head = queue->head > 0 ? queue->head-1 : QUEUE_PROC_REQS_SIZE-1;
205 12297 return &queue->queue[prev_head];
206 }
207
208 3 void queue_proc_reqs_remove(queue_proc_reqs_t *queue, pid_t pid) {
209
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 if (unlikely(!pid)) return;
210
211 unsigned int i;
212
2/2
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 3 times.
 14 for (i=queue->tail; i!=queue->head; i=(i+1)%QUEUE_PROC_REQS_SIZE) {
213
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 7 times.
 11 if (queue->queue[i].pid == pid) {
214 /* Clear request */
215 4 memset(&queue->queue[i], 0, sizeof(process_request_t));
216 }
217 /* Advance tail if it points to invalid elements */
218
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 6 times.
 11 if (queue->queue[i].pid == NOBODY
219
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 4 times.
 5 && i == queue->tail) {
220 1 queue->tail = (queue->tail+1) % QUEUE_PROC_REQS_SIZE;
221 }
222 }
223 }
224
225 12298 int queue_proc_reqs_push(queue_proc_reqs_t *queue, pid_t pid,
226 unsigned int howmany, const cpu_set_t *allowed) {
227 /* Remove entry if value is reset to 0 */
228
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 12297 times.
 12298 if (howmany == 0) {
229 1 queue_proc_reqs_remove(queue, pid);
230 1 return DLB_SUCCESS;
231 }
232
233 /* If the last request belongs to the same pid, just increment value */
234 12297 process_request_t *last_req = queue_proc_reqs_back(queue);
235
2/2
✓ Branch 0 taken 8191 times.
✓ Branch 1 taken 4106 times.
 12297 if (last_req->pid == pid) {
236 8191 last_req->howmany += howmany;
237 8191 return DLB_NOTED;
238 }
239
240 /* If the queue is full, return error code */
241 4106 unsigned int next_head = (queue->head + 1) % QUEUE_PROC_REQS_SIZE;
242
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 4105 times.
 4106 if (__builtin_expect((next_head == queue->tail), 0)) {
243 1 return DLB_ERR_REQST;
244 }
245
246 /* Otherwise, push new entry */
247 4105 queue->queue[queue->head].pid = pid;
248 4105 queue->queue[queue->head].howmany = howmany;
249
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4101 times.
 4105 if (allowed) {
250 4 memcpy(&queue->queue[queue->head].allowed, allowed, sizeof(*allowed));
251 } else {
252 4101 memset(&queue->queue[queue->head].allowed,0xff, sizeof(*allowed));
253 }
254 4105 queue->head = next_head;
255
256 4105 return DLB_NOTED;
257 }
258
259 ✗ void queue_proc_reqs_pop(queue_proc_reqs_t *queue, process_request_t *request) {
260 /* If front is valid, extract request */
261 ✗ process_request_t *front = queue_proc_reqs_front(queue);
262 ✗ if (front->pid != NOBODY) {
263 ✗ if (request != NULL) {
264 /* Copy request if argument is valid */
265 ✗ memcpy(request, front, sizeof(process_request_t));
266 }
267 /* Clear request */
268 ✗ memset(front, 0, sizeof(process_request_t));
269 }
270
271 /* Advance tail as long as it points to invalid elements */
272 ✗ while(queue->head != queue->tail
273 ✗ && queue->queue[queue->tail].pid == NOBODY) {
274 ✗ queue->tail = (queue->tail + 1) % QUEUE_PROC_REQS_SIZE;
275 }
276 }
277
278 45166 void queue_proc_reqs_get(queue_proc_reqs_t *queue, pid_t *pid, int cpuid) {
279 45166 *pid = NOBODY;
280 45166 unsigned int pointer = queue->tail;
281
4/4
✓ Branch 0 taken 90226 times.
✓ Branch 1 taken 109 times.
✓ Branch 2 taken 45169 times.
✓ Branch 3 taken 45057 times.
 90335 while(pointer != queue->head && *pid == NOBODY) {
282 45169 process_request_t *request = &queue->queue[pointer];
283
2/2
✓ Branch 0 taken 45166 times.
✓ Branch 1 taken 3 times.
 45169 if (request->pid != NOBODY
284
5/6
✓ Branch 0 taken 45166 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 45162 times.
✓ Branch 3 taken 4 times.
✓ Branch 4 taken 45162 times.
✓ Branch 5 taken 4 times.
 45166 && CPU_ISSET(cpuid, &request->allowed)) {
285 /* request is valid */
286 45162 *pid = request->pid;
287
2/2
✓ Branch 0 taken 4101 times.
✓ Branch 1 taken 41061 times.
 45162 if (--request->howmany == 0) {
288 4101 request->pid = NOBODY;
289 4101 CPU_ZERO(&request->allowed);
290 }
291 }
292
293 /* Advance tail if possible */
294
2/2
✓ Branch 0 taken 45164 times.
✓ Branch 1 taken 5 times.
 45169 if (pointer == queue->tail
295
2/2
✓ Branch 0 taken 4099 times.
✓ Branch 1 taken 41065 times.
 45164 && request->pid == NOBODY) {
296 4099 queue->tail = (queue->tail + 1) % QUEUE_PROC_REQS_SIZE;
297 }
298
299 /* Advance pointer */
300 45169 pointer = (pointer + 1) % QUEUE_PROC_REQS_SIZE;
301 }
302
303 /* Advance tail as long as it points to invalid elements */
304 45166 while(queue->head != queue->tail
305
4/4
✓ Branch 0 taken 45165 times.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 5 times.
✓ Branch 3 taken 45160 times.
 45171 && queue->queue[queue->tail].pid == NOBODY) {
306 5 queue->tail = (queue->tail + 1) % QUEUE_PROC_REQS_SIZE;
307 }
308 45166 }
309
310 /*********************************************************************************/
311
312 /*** queue_pids_t ****************************************************************/
313
314 1 void queue_pids_init(queue_pids_t *queue) {
315 1 memset(queue, 0, sizeof(*queue));
316 1 }
317
318 26 unsigned int queue_pids_size(const queue_pids_t *queue) {
319 26 return queue->head >= queue->tail
320 20 ? queue->head - queue->tail
321
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 6 times.
 26 : QUEUE_PIDS_SIZE - queue->tail + queue->head;
322 }
323
324 5 void queue_pids_remove(queue_pids_t *queue, pid_t pid) {
325 unsigned int i;
326
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 5 times.
 25 for (i=queue->tail; i!=queue->head; i=(i+1)%QUEUE_PIDS_SIZE) {
327
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 11 times.
 20 if (queue->queue[i] == pid) {
328 9 queue->queue[i] = NOBODY;
329 }
330 /* Advance tail if it points to invalid elements */
331
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 8 times.
 20 if (queue->queue[i] == NOBODY
332
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 3 times.
 12 && i == queue->tail) {
333 9 queue->tail = (queue->tail+1) % QUEUE_PIDS_SIZE;
334 }
335 }
336 5 }
337
338 13 int queue_pids_push(queue_pids_t *queue, pid_t pid) {
339 13 unsigned int next_head = (queue->head + 1) % QUEUE_PIDS_SIZE;
340
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 12 times.
 13 if (__builtin_expect((next_head == queue->tail), 0)) {
341 1 return DLB_ERR_REQST;
342 }
343 12 queue->queue[queue->head] = pid;
344 12 queue->head = next_head;
345 12 return DLB_NOTED;
346 }
347
348 7 void queue_pids_pop(queue_pids_t *queue, pid_t *pid) {
349 7 *pid = NOBODY;
350
4/4
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 7 times.
✓ Branch 3 taken 6 times.
 14 while(queue->head != queue->tail && *pid == NOBODY) {
351 7 *pid = queue->queue[queue->tail];
352 7 queue->queue[queue->tail] = NOBODY;
353 7 queue->tail = (queue->tail + 1) % QUEUE_PIDS_SIZE;
354 }
355 7 }
356 /*********************************************************************************/
357