1 /*
2 * Copyright © 2009 CNRS
3 * Copyright © 2009-2020 Inria. All rights reserved.
4 * Copyright © 2009-2011 Université Bordeaux
5 * Copyright © 2009-2011 Cisco Systems, Inc. All rights reserved.
6 * See COPYING in top-level directory.
7 */
8
9 #include "private/autogen/config.h"
10 #include "hwloc/autogen/config.h"
11 #include "hwloc.h"
12 #include "private/misc.h"
13 #include "private/private.h"
14 #include "private/debug.h"
15 #include "hwloc/bitmap.h"
16
17 #include <stdarg.h>
18 #include <stdio.h>
19 #include <assert.h>
20 #include <errno.h>
21 #include <ctype.h>
22
23 /*
24 * possible improvements:
25 * - have a way to change the initial allocation size:
26 * add hwloc_bitmap_set_foo() to changes a global here,
27 * and make the hwloc core call based on the early number of PUs
28 * - make HWLOC_BITMAP_PREALLOC_BITS configurable, and detectable
29 * by parsing /proc/cpuinfo during configure on Linux.
30 * - preallocate inside the bitmap structure (so that the whole structure is a cacheline for instance)
31 * and allocate a dedicated array only later when reallocating larger
32 * - add a bitmap->ulongs_empty_first which guarantees that some first ulongs are empty,
33 * making tests much faster for big bitmaps since there's no need to look at first ulongs.
34 * no need for ulongs_empty_first to be exactly the max number of empty ulongs,
35 * clearing bits that were set earlier isn't very common.
36 */
37
38 /* magic number */
39 #define HWLOC_BITMAP_MAGIC 0x20091007
40
41 /* preallocated bits in every bitmap */
42 #define HWLOC_BITMAP_PREALLOC_BITS 512
43 #define HWLOC_BITMAP_PREALLOC_ULONGS (HWLOC_BITMAP_PREALLOC_BITS/HWLOC_BITS_PER_LONG)
44
45 /* actual opaque type internals */
46 struct hwloc_bitmap_s {
47 unsigned ulongs_count; /* how many ulong bitmasks are valid, >= 1 */
48 unsigned ulongs_allocated; /* how many ulong bitmasks are allocated, >= ulongs_count */
49 unsigned long *ulongs;
50 int infinite; /* set to 1 if all bits beyond ulongs are set */
51 #ifdef HWLOC_DEBUG
52 int magic;
53 #endif
54 };
55
56 /* overzealous check in debug-mode, not as powerful as valgrind but still useful */
57 #ifdef HWLOC_DEBUG
58 #define HWLOC__BITMAP_CHECK(set) do { \
59 assert((set)->magic == HWLOC_BITMAP_MAGIC); \
60 assert((set)->ulongs_count >= 1); \
61 assert((set)->ulongs_allocated >= (set)->ulongs_count); \
62 } while (0)
63 #else
64 #define HWLOC__BITMAP_CHECK(set)
65 #endif
66
67 /* extract a subset from a set using an index or a cpu */
68 #define HWLOC_SUBBITMAP_INDEX(cpu) ((cpu)/(HWLOC_BITS_PER_LONG))
69 #define HWLOC_SUBBITMAP_CPU_ULBIT(cpu) ((cpu)%(HWLOC_BITS_PER_LONG))
70 /* Read from a bitmap ulong without knowing whether x is valid.
71 * Writers should make sure that x is valid and modify set->ulongs[x] directly.
72 */
73 #define HWLOC_SUBBITMAP_READULONG(set,x) ((x) < (set)->ulongs_count ? (set)->ulongs[x] : (set)->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO)
74
75 /* predefined subset values */
76 #define HWLOC_SUBBITMAP_ZERO 0UL
77 #define HWLOC_SUBBITMAP_FULL (~0UL)
78 #define HWLOC_SUBBITMAP_ULBIT(bit) (1UL<<(bit))
79 #define HWLOC_SUBBITMAP_CPU(cpu) HWLOC_SUBBITMAP_ULBIT(HWLOC_SUBBITMAP_CPU_ULBIT(cpu))
80 #define HWLOC_SUBBITMAP_ULBIT_TO(bit) (HWLOC_SUBBITMAP_FULL>>(HWLOC_BITS_PER_LONG-1-(bit)))
81 #define HWLOC_SUBBITMAP_ULBIT_FROM(bit) (HWLOC_SUBBITMAP_FULL<<(bit))
82 #define HWLOC_SUBBITMAP_ULBIT_FROMTO(begin,end) (HWLOC_SUBBITMAP_ULBIT_TO(end) & HWLOC_SUBBITMAP_ULBIT_FROM(begin))
83
hwloc_bitmap_alloc(void)84 struct hwloc_bitmap_s * hwloc_bitmap_alloc(void)
85 {
86 struct hwloc_bitmap_s * set;
87
88 set = malloc(sizeof(struct hwloc_bitmap_s));
89 if (!set)
90 return NULL;
91
92 set->ulongs_count = 1;
93 set->ulongs_allocated = HWLOC_BITMAP_PREALLOC_ULONGS;
94 set->ulongs = malloc(HWLOC_BITMAP_PREALLOC_ULONGS * sizeof(unsigned long));
95 if (!set->ulongs) {
96 free(set);
97 return NULL;
98 }
99
100 set->ulongs[0] = HWLOC_SUBBITMAP_ZERO;
101 set->infinite = 0;
102 #ifdef HWLOC_DEBUG
103 set->magic = HWLOC_BITMAP_MAGIC;
104 #endif
105 return set;
106 }
107
hwloc_bitmap_alloc_full(void)108 struct hwloc_bitmap_s * hwloc_bitmap_alloc_full(void)
109 {
110 struct hwloc_bitmap_s * set = hwloc_bitmap_alloc();
111 if (set) {
112 set->infinite = 1;
113 set->ulongs[0] = HWLOC_SUBBITMAP_FULL;
114 }
115 return set;
116 }
117
hwloc_bitmap_free(struct hwloc_bitmap_s * set)118 void hwloc_bitmap_free(struct hwloc_bitmap_s * set)
119 {
120 if (!set)
121 return;
122
123 HWLOC__BITMAP_CHECK(set);
124 #ifdef HWLOC_DEBUG
125 set->magic = 0;
126 #endif
127
128 free(set->ulongs);
129 free(set);
130 }
131
132 /* enlarge until it contains at least needed_count ulongs.
133 */
134 static int
135 hwloc_bitmap_enlarge_by_ulongs(struct hwloc_bitmap_s * set, unsigned needed_count) __hwloc_attribute_warn_unused_result;
136 static int
hwloc_bitmap_enlarge_by_ulongs(struct hwloc_bitmap_s * set,unsigned needed_count)137 hwloc_bitmap_enlarge_by_ulongs(struct hwloc_bitmap_s * set, unsigned needed_count)
138 {
139 unsigned tmp = 1U << hwloc_flsl((unsigned long) needed_count - 1);
140 if (tmp > set->ulongs_allocated) {
141 unsigned long *tmpulongs;
142 tmpulongs = realloc(set->ulongs, tmp * sizeof(unsigned long));
143 if (!tmpulongs)
144 return -1;
145 set->ulongs = tmpulongs;
146 set->ulongs_allocated = tmp;
147 }
148 return 0;
149 }
150
151 /* enlarge until it contains at least needed_count ulongs,
152 * and update new ulongs according to the infinite field.
153 */
154 static int
155 hwloc_bitmap_realloc_by_ulongs(struct hwloc_bitmap_s * set, unsigned needed_count) __hwloc_attribute_warn_unused_result;
156 static int
hwloc_bitmap_realloc_by_ulongs(struct hwloc_bitmap_s * set,unsigned needed_count)157 hwloc_bitmap_realloc_by_ulongs(struct hwloc_bitmap_s * set, unsigned needed_count)
158 {
159 unsigned i;
160
161 HWLOC__BITMAP_CHECK(set);
162
163 if (needed_count <= set->ulongs_count)
164 return 0;
165
166 /* realloc larger if needed */
167 if (hwloc_bitmap_enlarge_by_ulongs(set, needed_count) < 0)
168 return -1;
169
170 /* fill the newly allocated subset depending on the infinite flag */
171 for(i=set->ulongs_count; i<needed_count; i++)
172 set->ulongs[i] = set->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
173 set->ulongs_count = needed_count;
174 return 0;
175 }
176
177 /* realloc until it contains at least cpu+1 bits */
178 #define hwloc_bitmap_realloc_by_cpu_index(set, cpu) hwloc_bitmap_realloc_by_ulongs(set, ((cpu)/HWLOC_BITS_PER_LONG)+1)
179
180 /* reset a bitmap to exactely the needed size.
181 * the caller must reinitialize all ulongs and the infinite flag later.
182 */
183 static int
184 hwloc_bitmap_reset_by_ulongs(struct hwloc_bitmap_s * set, unsigned needed_count) __hwloc_attribute_warn_unused_result;
185 static int
hwloc_bitmap_reset_by_ulongs(struct hwloc_bitmap_s * set,unsigned needed_count)186 hwloc_bitmap_reset_by_ulongs(struct hwloc_bitmap_s * set, unsigned needed_count)
187 {
188 if (hwloc_bitmap_enlarge_by_ulongs(set, needed_count))
189 return -1;
190 set->ulongs_count = needed_count;
191 return 0;
192 }
193
194 /* reset until it contains exactly cpu+1 bits (roundup to a ulong).
195 * the caller must reinitialize all ulongs and the infinite flag later.
196 */
197 #define hwloc_bitmap_reset_by_cpu_index(set, cpu) hwloc_bitmap_reset_by_ulongs(set, ((cpu)/HWLOC_BITS_PER_LONG)+1)
198
hwloc_bitmap_tma_dup(struct hwloc_tma * tma,const struct hwloc_bitmap_s * old)199 struct hwloc_bitmap_s * hwloc_bitmap_tma_dup(struct hwloc_tma *tma, const struct hwloc_bitmap_s * old)
200 {
201 struct hwloc_bitmap_s * new;
202
203 if (!old)
204 return NULL;
205
206 HWLOC__BITMAP_CHECK(old);
207
208 new = hwloc_tma_malloc(tma, sizeof(struct hwloc_bitmap_s));
209 if (!new)
210 return NULL;
211
212 new->ulongs = hwloc_tma_malloc(tma, old->ulongs_allocated * sizeof(unsigned long));
213 if (!new->ulongs) {
214 free(new);
215 return NULL;
216 }
217 new->ulongs_allocated = old->ulongs_allocated;
218 new->ulongs_count = old->ulongs_count;
219 memcpy(new->ulongs, old->ulongs, new->ulongs_count * sizeof(unsigned long));
220 new->infinite = old->infinite;
221 #ifdef HWLOC_DEBUG
222 new->magic = HWLOC_BITMAP_MAGIC;
223 #endif
224 return new;
225 }
226
hwloc_bitmap_dup(const struct hwloc_bitmap_s * old)227 struct hwloc_bitmap_s * hwloc_bitmap_dup(const struct hwloc_bitmap_s * old)
228 {
229 return hwloc_bitmap_tma_dup(NULL, old);
230 }
231
hwloc_bitmap_copy(struct hwloc_bitmap_s * dst,const struct hwloc_bitmap_s * src)232 int hwloc_bitmap_copy(struct hwloc_bitmap_s * dst, const struct hwloc_bitmap_s * src)
233 {
234 HWLOC__BITMAP_CHECK(dst);
235 HWLOC__BITMAP_CHECK(src);
236
237 if (hwloc_bitmap_reset_by_ulongs(dst, src->ulongs_count) < 0)
238 return -1;
239
240 memcpy(dst->ulongs, src->ulongs, src->ulongs_count * sizeof(unsigned long));
241 dst->infinite = src->infinite;
242 return 0;
243 }
244
245 /* Strings always use 32bit groups */
246 #define HWLOC_PRIxSUBBITMAP "%08lx"
247 #define HWLOC_BITMAP_SUBSTRING_SIZE 32
248 #define HWLOC_BITMAP_SUBSTRING_LENGTH (HWLOC_BITMAP_SUBSTRING_SIZE/4)
249 #define HWLOC_BITMAP_STRING_PER_LONG (HWLOC_BITS_PER_LONG/HWLOC_BITMAP_SUBSTRING_SIZE)
250
hwloc_bitmap_snprintf(char * __hwloc_restrict buf,size_t buflen,const struct hwloc_bitmap_s * __hwloc_restrict set)251 int hwloc_bitmap_snprintf(char * __hwloc_restrict buf, size_t buflen, const struct hwloc_bitmap_s * __hwloc_restrict set)
252 {
253 ssize_t size = buflen;
254 char *tmp = buf;
255 int res, ret = 0;
256 int needcomma = 0;
257 int i;
258 unsigned long accum = 0;
259 int accumed = 0;
260 #if HWLOC_BITS_PER_LONG == HWLOC_BITMAP_SUBSTRING_SIZE
261 const unsigned long accum_mask = ~0UL;
262 #else /* HWLOC_BITS_PER_LONG != HWLOC_BITMAP_SUBSTRING_SIZE */
263 const unsigned long accum_mask = ((1UL << HWLOC_BITMAP_SUBSTRING_SIZE) - 1) << (HWLOC_BITS_PER_LONG - HWLOC_BITMAP_SUBSTRING_SIZE);
264 #endif /* HWLOC_BITS_PER_LONG != HWLOC_BITMAP_SUBSTRING_SIZE */
265
266 HWLOC__BITMAP_CHECK(set);
267
268 /* mark the end in case we do nothing later */
269 if (buflen > 0)
270 tmp[0] = '\0';
271
272 if (set->infinite) {
273 res = hwloc_snprintf(tmp, size, "0xf...f");
274 needcomma = 1;
275 if (res < 0)
276 return -1;
277 ret += res;
278 if (res >= size)
279 res = size>0 ? (int)size - 1 : 0;
280 tmp += res;
281 size -= res;
282 }
283
284 i=(int) set->ulongs_count-1;
285
286 if (set->infinite) {
287 /* ignore starting FULL since we have 0xf...f already */
288 while (i>=0 && set->ulongs[i] == HWLOC_SUBBITMAP_FULL)
289 i--;
290 } else {
291 /* ignore starting ZERO except the last one */
292 while (i>=0 && set->ulongs[i] == HWLOC_SUBBITMAP_ZERO)
293 i--;
294 }
295
296 while (i>=0 || accumed) {
297 /* Refill accumulator */
298 if (!accumed) {
299 accum = set->ulongs[i--];
300 accumed = HWLOC_BITS_PER_LONG;
301 }
302
303 if (accum & accum_mask) {
304 /* print the whole subset if not empty */
305 res = hwloc_snprintf(tmp, size, needcomma ? ",0x" HWLOC_PRIxSUBBITMAP : "0x" HWLOC_PRIxSUBBITMAP,
306 (accum & accum_mask) >> (HWLOC_BITS_PER_LONG - HWLOC_BITMAP_SUBSTRING_SIZE));
307 needcomma = 1;
308 } else if (i == -1 && accumed == HWLOC_BITMAP_SUBSTRING_SIZE) {
309 /* print a single 0 to mark the last subset */
310 res = hwloc_snprintf(tmp, size, needcomma ? ",0x0" : "0x0");
311 } else if (needcomma) {
312 res = hwloc_snprintf(tmp, size, ",");
313 } else {
314 res = 0;
315 }
316 if (res < 0)
317 return -1;
318 ret += res;
319
320 #if HWLOC_BITS_PER_LONG == HWLOC_BITMAP_SUBSTRING_SIZE
321 accum = 0;
322 accumed = 0;
323 #else
324 accum <<= HWLOC_BITMAP_SUBSTRING_SIZE;
325 accumed -= HWLOC_BITMAP_SUBSTRING_SIZE;
326 #endif
327
328 if (res >= size)
329 res = size>0 ? (int)size - 1 : 0;
330
331 tmp += res;
332 size -= res;
333 }
334
335 /* if didn't display anything, display 0x0 */
336 if (!ret) {
337 res = hwloc_snprintf(tmp, size, "0x0");
338 if (res < 0)
339 return -1;
340 ret += res;
341 }
342
343 return ret;
344 }
345
hwloc_bitmap_asprintf(char ** strp,const struct hwloc_bitmap_s * __hwloc_restrict set)346 int hwloc_bitmap_asprintf(char ** strp, const struct hwloc_bitmap_s * __hwloc_restrict set)
347 {
348 int len;
349 char *buf;
350
351 HWLOC__BITMAP_CHECK(set);
352
353 len = hwloc_bitmap_snprintf(NULL, 0, set);
354 buf = malloc(len+1);
355 if (!buf)
356 return -1;
357 *strp = buf;
358 return hwloc_bitmap_snprintf(buf, len+1, set);
359 }
360
hwloc_bitmap_sscanf(struct hwloc_bitmap_s * set,const char * __hwloc_restrict string)361 int hwloc_bitmap_sscanf(struct hwloc_bitmap_s *set, const char * __hwloc_restrict string)
362 {
363 const char * current = string;
364 unsigned long accum = 0;
365 int count=0;
366 int infinite = 0;
367
368 /* count how many substrings there are */
369 count++;
370 while ((current = strchr(current+1, ',')) != NULL)
371 count++;
372
373 current = string;
374 if (!strncmp("0xf...f", current, 7)) {
375 current += 7;
376 if (*current != ',') {
377 /* special case for infinite/full bitmap */
378 hwloc_bitmap_fill(set);
379 return 0;
380 }
381 current++;
382 infinite = 1;
383 count--;
384 }
385
386 if (hwloc_bitmap_reset_by_ulongs(set, (count + HWLOC_BITMAP_STRING_PER_LONG - 1) / HWLOC_BITMAP_STRING_PER_LONG) < 0)
387 return -1;
388 set->infinite = 0;
389
390 while (*current != '\0') {
391 unsigned long val;
392 char *next;
393 val = strtoul(current, &next, 16);
394
395 assert(count > 0);
396 count--;
397
398 accum |= (val << ((count * HWLOC_BITMAP_SUBSTRING_SIZE) % HWLOC_BITS_PER_LONG));
399 if (!(count % HWLOC_BITMAP_STRING_PER_LONG)) {
400 set->ulongs[count / HWLOC_BITMAP_STRING_PER_LONG] = accum;
401 accum = 0;
402 }
403
404 if (*next != ',') {
405 if (*next || count > 0)
406 goto failed;
407 else
408 break;
409 }
410 current = (const char*) next+1;
411 }
412
413 set->infinite = infinite; /* set at the end, to avoid spurious realloc with filled new ulongs */
414
415 return 0;
416
417 failed:
418 /* failure to parse */
419 hwloc_bitmap_zero(set);
420 return -1;
421 }
422
hwloc_bitmap_list_snprintf(char * __hwloc_restrict buf,size_t buflen,const struct hwloc_bitmap_s * __hwloc_restrict set)423 int hwloc_bitmap_list_snprintf(char * __hwloc_restrict buf, size_t buflen, const struct hwloc_bitmap_s * __hwloc_restrict set)
424 {
425 int prev = -1;
426 ssize_t size = buflen;
427 char *tmp = buf;
428 int res, ret = 0;
429 int needcomma = 0;
430
431 HWLOC__BITMAP_CHECK(set);
432
433 /* mark the end in case we do nothing later */
434 if (buflen > 0)
435 tmp[0] = '\0';
436
437 while (1) {
438 int begin, end;
439
440 begin = hwloc_bitmap_next(set, prev);
441 if (begin == -1)
442 break;
443 end = hwloc_bitmap_next_unset(set, begin);
444
445 if (end == begin+1) {
446 res = hwloc_snprintf(tmp, size, needcomma ? ",%d" : "%d", begin);
447 } else if (end == -1) {
448 res = hwloc_snprintf(tmp, size, needcomma ? ",%d-" : "%d-", begin);
449 } else {
450 res = hwloc_snprintf(tmp, size, needcomma ? ",%d-%d" : "%d-%d", begin, end-1);
451 }
452 if (res < 0)
453 return -1;
454 ret += res;
455
456 if (res >= size)
457 res = size>0 ? (int)size - 1 : 0;
458
459 tmp += res;
460 size -= res;
461 needcomma = 1;
462
463 if (end == -1)
464 break;
465 else
466 prev = end - 1;
467 }
468
469 return ret;
470 }
471
hwloc_bitmap_list_asprintf(char ** strp,const struct hwloc_bitmap_s * __hwloc_restrict set)472 int hwloc_bitmap_list_asprintf(char ** strp, const struct hwloc_bitmap_s * __hwloc_restrict set)
473 {
474 int len;
475 char *buf;
476
477 HWLOC__BITMAP_CHECK(set);
478
479 len = hwloc_bitmap_list_snprintf(NULL, 0, set);
480 buf = malloc(len+1);
481 if (!buf)
482 return -1;
483 *strp = buf;
484 return hwloc_bitmap_list_snprintf(buf, len+1, set);
485 }
486
hwloc_bitmap_list_sscanf(struct hwloc_bitmap_s * set,const char * __hwloc_restrict string)487 int hwloc_bitmap_list_sscanf(struct hwloc_bitmap_s *set, const char * __hwloc_restrict string)
488 {
489 const char * current = string;
490 char *next;
491 long begin = -1, val;
492
493 hwloc_bitmap_zero(set);
494
495 while (*current != '\0') {
496
497 /* ignore empty ranges */
498 while (*current == ',' || *current == ' ')
499 current++;
500
501 val = strtoul(current, &next, 0);
502 /* make sure we got at least one digit */
503 if (next == current)
504 goto failed;
505
506 if (begin != -1) {
507 /* finishing a range */
508 if (hwloc_bitmap_set_range(set, begin, val) < 0)
509 goto failed;
510 begin = -1;
511
512 } else if (*next == '-') {
513 /* starting a new range */
514 if (*(next+1) == '\0') {
515 /* infinite range */
516 if (hwloc_bitmap_set_range(set, val, -1) < 0)
517 goto failed;
518 break;
519 } else {
520 /* normal range */
521 begin = val;
522 }
523
524 } else if (*next == ',' || *next == ' ' || *next == '\0') {
525 /* single digit */
526 hwloc_bitmap_set(set, val);
527 }
528
529 if (*next == '\0')
530 break;
531 current = next+1;
532 }
533
534 return 0;
535
536 failed:
537 /* failure to parse */
538 hwloc_bitmap_zero(set);
539 return -1;
540 }
541
hwloc_bitmap_taskset_snprintf(char * __hwloc_restrict buf,size_t buflen,const struct hwloc_bitmap_s * __hwloc_restrict set)542 int hwloc_bitmap_taskset_snprintf(char * __hwloc_restrict buf, size_t buflen, const struct hwloc_bitmap_s * __hwloc_restrict set)
543 {
544 ssize_t size = buflen;
545 char *tmp = buf;
546 int res, ret = 0;
547 int started = 0;
548 int i;
549
550 HWLOC__BITMAP_CHECK(set);
551
552 /* mark the end in case we do nothing later */
553 if (buflen > 0)
554 tmp[0] = '\0';
555
556 if (set->infinite) {
557 res = hwloc_snprintf(tmp, size, "0xf...f");
558 started = 1;
559 if (res < 0)
560 return -1;
561 ret += res;
562 if (res >= size)
563 res = size>0 ? (int)size - 1 : 0;
564 tmp += res;
565 size -= res;
566 }
567
568 i=set->ulongs_count-1;
569
570 if (set->infinite) {
571 /* ignore starting FULL since we have 0xf...f already */
572 while (i>=0 && set->ulongs[i] == HWLOC_SUBBITMAP_FULL)
573 i--;
574 } else {
575 /* ignore starting ZERO except the last one */
576 while (i>=1 && set->ulongs[i] == HWLOC_SUBBITMAP_ZERO)
577 i--;
578 }
579
580 while (i>=0) {
581 unsigned long val = set->ulongs[i--];
582 if (started) {
583 /* print the whole subset */
584 #if HWLOC_BITS_PER_LONG == 64
585 res = hwloc_snprintf(tmp, size, "%016lx", val);
586 #else
587 res = hwloc_snprintf(tmp, size, "%08lx", val);
588 #endif
589 } else if (val || i == -1) {
590 res = hwloc_snprintf(tmp, size, "0x%lx", val);
591 started = 1;
592 } else {
593 res = 0;
594 }
595 if (res < 0)
596 return -1;
597 ret += res;
598 if (res >= size)
599 res = size>0 ? (int)size - 1 : 0;
600 tmp += res;
601 size -= res;
602 }
603
604 /* if didn't display anything, display 0x0 */
605 if (!ret) {
606 res = hwloc_snprintf(tmp, size, "0x0");
607 if (res < 0)
608 return -1;
609 ret += res;
610 }
611
612 return ret;
613 }
614
hwloc_bitmap_taskset_asprintf(char ** strp,const struct hwloc_bitmap_s * __hwloc_restrict set)615 int hwloc_bitmap_taskset_asprintf(char ** strp, const struct hwloc_bitmap_s * __hwloc_restrict set)
616 {
617 int len;
618 char *buf;
619
620 HWLOC__BITMAP_CHECK(set);
621
622 len = hwloc_bitmap_taskset_snprintf(NULL, 0, set);
623 buf = malloc(len+1);
624 if (!buf)
625 return -1;
626 *strp = buf;
627 return hwloc_bitmap_taskset_snprintf(buf, len+1, set);
628 }
629
hwloc_bitmap_taskset_sscanf(struct hwloc_bitmap_s * set,const char * __hwloc_restrict string)630 int hwloc_bitmap_taskset_sscanf(struct hwloc_bitmap_s *set, const char * __hwloc_restrict string)
631 {
632 const char * current = string;
633 int chars;
634 int count;
635 int infinite = 0;
636
637 if (!strncmp("0xf...f", current, 7)) {
638 /* infinite bitmap */
639 infinite = 1;
640 current += 7;
641 if (*current == '\0') {
642 /* special case for infinite/full bitmap */
643 hwloc_bitmap_fill(set);
644 return 0;
645 }
646 } else {
647 /* finite bitmap */
648 if (!strncmp("0x", current, 2))
649 current += 2;
650 if (*current == '\0') {
651 /* special case for empty bitmap */
652 hwloc_bitmap_zero(set);
653 return 0;
654 }
655 }
656 /* we know there are other characters now */
657
658 chars = (int)strlen(current);
659 count = (chars * 4 + HWLOC_BITS_PER_LONG - 1) / HWLOC_BITS_PER_LONG;
660
661 if (hwloc_bitmap_reset_by_ulongs(set, count) < 0)
662 return -1;
663 set->infinite = 0;
664
665 while (*current != '\0') {
666 int tmpchars;
667 char ustr[17];
668 unsigned long val;
669 char *next;
670
671 tmpchars = chars % (HWLOC_BITS_PER_LONG/4);
672 if (!tmpchars)
673 tmpchars = (HWLOC_BITS_PER_LONG/4);
674
675 memcpy(ustr, current, tmpchars);
676 ustr[tmpchars] = '\0';
677 val = strtoul(ustr, &next, 16);
678 if (*next != '\0')
679 goto failed;
680
681 set->ulongs[count-1] = val;
682
683 current += tmpchars;
684 chars -= tmpchars;
685 count--;
686 }
687
688 set->infinite = infinite; /* set at the end, to avoid spurious realloc with filled new ulongs */
689
690 return 0;
691
692 failed:
693 /* failure to parse */
694 hwloc_bitmap_zero(set);
695 return -1;
696 }
697
hwloc_bitmap__zero(struct hwloc_bitmap_s * set)698 static void hwloc_bitmap__zero(struct hwloc_bitmap_s *set)
699 {
700 unsigned i;
701 for(i=0; i<set->ulongs_count; i++)
702 set->ulongs[i] = HWLOC_SUBBITMAP_ZERO;
703 set->infinite = 0;
704 }
705
hwloc_bitmap_zero(struct hwloc_bitmap_s * set)706 void hwloc_bitmap_zero(struct hwloc_bitmap_s * set)
707 {
708 HWLOC__BITMAP_CHECK(set);
709
710 HWLOC_BUILD_ASSERT(HWLOC_BITMAP_PREALLOC_ULONGS >= 1);
711 if (hwloc_bitmap_reset_by_ulongs(set, 1) < 0) {
712 /* cannot fail since we preallocate some ulongs.
713 * if we ever preallocate nothing, we'll reset to 0 ulongs.
714 */
715 }
716 hwloc_bitmap__zero(set);
717 }
718
hwloc_bitmap__fill(struct hwloc_bitmap_s * set)719 static void hwloc_bitmap__fill(struct hwloc_bitmap_s * set)
720 {
721 unsigned i;
722 for(i=0; i<set->ulongs_count; i++)
723 set->ulongs[i] = HWLOC_SUBBITMAP_FULL;
724 set->infinite = 1;
725 }
726
hwloc_bitmap_fill(struct hwloc_bitmap_s * set)727 void hwloc_bitmap_fill(struct hwloc_bitmap_s * set)
728 {
729 HWLOC__BITMAP_CHECK(set);
730
731 HWLOC_BUILD_ASSERT(HWLOC_BITMAP_PREALLOC_ULONGS >= 1);
732 if (hwloc_bitmap_reset_by_ulongs(set, 1) < 0) {
733 /* cannot fail since we pre-allocate some ulongs.
734 * if we ever pre-allocate nothing, we'll reset to 0 ulongs.
735 */
736 }
737 hwloc_bitmap__fill(set);
738 }
739
hwloc_bitmap_from_ulong(struct hwloc_bitmap_s * set,unsigned long mask)740 int hwloc_bitmap_from_ulong(struct hwloc_bitmap_s *set, unsigned long mask)
741 {
742 HWLOC__BITMAP_CHECK(set);
743
744 HWLOC_BUILD_ASSERT(HWLOC_BITMAP_PREALLOC_ULONGS >= 1);
745 if (hwloc_bitmap_reset_by_ulongs(set, 1) < 0) {
746 /* cannot fail since we pre-allocate some ulongs.
747 * if ever pre-allocate nothing, we may have to return a failure.
748 */
749 }
750 set->ulongs[0] = mask; /* there's always at least one ulong allocated */
751 set->infinite = 0;
752 return 0;
753 }
754
hwloc_bitmap_from_ith_ulong(struct hwloc_bitmap_s * set,unsigned i,unsigned long mask)755 int hwloc_bitmap_from_ith_ulong(struct hwloc_bitmap_s *set, unsigned i, unsigned long mask)
756 {
757 unsigned j;
758
759 HWLOC__BITMAP_CHECK(set);
760
761 if (hwloc_bitmap_reset_by_ulongs(set, i+1) < 0)
762 return -1;
763
764 set->ulongs[i] = mask;
765 for(j=0; j<i; j++)
766 set->ulongs[j] = HWLOC_SUBBITMAP_ZERO;
767 set->infinite = 0;
768 return 0;
769 }
770
hwloc_bitmap_from_ulongs(struct hwloc_bitmap_s * set,unsigned nr,const unsigned long * masks)771 int hwloc_bitmap_from_ulongs(struct hwloc_bitmap_s *set, unsigned nr, const unsigned long *masks)
772 {
773 unsigned j;
774
775 HWLOC__BITMAP_CHECK(set);
776
777 if (hwloc_bitmap_reset_by_ulongs(set, nr) < 0)
778 return -1;
779
780 for(j=0; j<nr; j++)
781 set->ulongs[j] = masks[j];
782 set->infinite = 0;
783 return 0;
784 }
785
hwloc_bitmap_to_ulong(const struct hwloc_bitmap_s * set)786 unsigned long hwloc_bitmap_to_ulong(const struct hwloc_bitmap_s *set)
787 {
788 HWLOC__BITMAP_CHECK(set);
789
790 return set->ulongs[0]; /* there's always at least one ulong allocated */
791 }
792
hwloc_bitmap_to_ith_ulong(const struct hwloc_bitmap_s * set,unsigned i)793 unsigned long hwloc_bitmap_to_ith_ulong(const struct hwloc_bitmap_s *set, unsigned i)
794 {
795 HWLOC__BITMAP_CHECK(set);
796
797 return HWLOC_SUBBITMAP_READULONG(set, i);
798 }
799
hwloc_bitmap_to_ulongs(const struct hwloc_bitmap_s * set,unsigned nr,unsigned long * masks)800 int hwloc_bitmap_to_ulongs(const struct hwloc_bitmap_s *set, unsigned nr, unsigned long *masks)
801 {
802 unsigned j;
803
804 HWLOC__BITMAP_CHECK(set);
805
806 for(j=0; j<nr; j++)
807 masks[j] = HWLOC_SUBBITMAP_READULONG(set, j);
808 return 0;
809 }
810
hwloc_bitmap_nr_ulongs(const struct hwloc_bitmap_s * set)811 int hwloc_bitmap_nr_ulongs(const struct hwloc_bitmap_s *set)
812 {
813 unsigned last;
814
815 HWLOC__BITMAP_CHECK(set);
816
817 if (set->infinite)
818 return -1;
819
820 last = hwloc_bitmap_last(set);
821 return (last + HWLOC_BITS_PER_LONG)/HWLOC_BITS_PER_LONG;
822 }
823
hwloc_bitmap_only(struct hwloc_bitmap_s * set,unsigned cpu)824 int hwloc_bitmap_only(struct hwloc_bitmap_s * set, unsigned cpu)
825 {
826 unsigned index_ = HWLOC_SUBBITMAP_INDEX(cpu);
827
828 HWLOC__BITMAP_CHECK(set);
829
830 if (hwloc_bitmap_reset_by_cpu_index(set, cpu) < 0)
831 return -1;
832
833 hwloc_bitmap__zero(set);
834 set->ulongs[index_] |= HWLOC_SUBBITMAP_CPU(cpu);
835 return 0;
836 }
837
hwloc_bitmap_allbut(struct hwloc_bitmap_s * set,unsigned cpu)838 int hwloc_bitmap_allbut(struct hwloc_bitmap_s * set, unsigned cpu)
839 {
840 unsigned index_ = HWLOC_SUBBITMAP_INDEX(cpu);
841
842 HWLOC__BITMAP_CHECK(set);
843
844 if (hwloc_bitmap_reset_by_cpu_index(set, cpu) < 0)
845 return -1;
846
847 hwloc_bitmap__fill(set);
848 set->ulongs[index_] &= ~HWLOC_SUBBITMAP_CPU(cpu);
849 return 0;
850 }
851
hwloc_bitmap_set(struct hwloc_bitmap_s * set,unsigned cpu)852 int hwloc_bitmap_set(struct hwloc_bitmap_s * set, unsigned cpu)
853 {
854 unsigned index_ = HWLOC_SUBBITMAP_INDEX(cpu);
855
856 HWLOC__BITMAP_CHECK(set);
857
858 /* nothing to do if setting inside the infinite part of the bitmap */
859 if (set->infinite && cpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
860 return 0;
861
862 if (hwloc_bitmap_realloc_by_cpu_index(set, cpu) < 0)
863 return -1;
864
865 set->ulongs[index_] |= HWLOC_SUBBITMAP_CPU(cpu);
866 return 0;
867 }
868
hwloc_bitmap_set_range(struct hwloc_bitmap_s * set,unsigned begincpu,int _endcpu)869 int hwloc_bitmap_set_range(struct hwloc_bitmap_s * set, unsigned begincpu, int _endcpu)
870 {
871 unsigned i;
872 unsigned beginset,endset;
873 unsigned endcpu = (unsigned) _endcpu;
874
875 HWLOC__BITMAP_CHECK(set);
876
877 if (endcpu < begincpu)
878 return 0;
879 if (set->infinite && begincpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
880 /* setting only in the already-set infinite part, nothing to do */
881 return 0;
882
883 if (_endcpu == -1) {
884 /* infinite range */
885
886 /* make sure we can play with the ulong that contains begincpu */
887 if (hwloc_bitmap_realloc_by_cpu_index(set, begincpu) < 0)
888 return -1;
889
890 /* update the ulong that contains begincpu */
891 beginset = HWLOC_SUBBITMAP_INDEX(begincpu);
892 set->ulongs[beginset] |= HWLOC_SUBBITMAP_ULBIT_FROM(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu));
893 /* set ulongs after begincpu if any already allocated */
894 for(i=beginset+1; i<set->ulongs_count; i++)
895 set->ulongs[i] = HWLOC_SUBBITMAP_FULL;
896 /* mark the infinity as set */
897 set->infinite = 1;
898 } else {
899 /* finite range */
900
901 /* ignore the part of the range that overlaps with the already-set infinite part */
902 if (set->infinite && endcpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
903 endcpu = set->ulongs_count * HWLOC_BITS_PER_LONG - 1;
904 /* make sure we can play with the ulongs that contain begincpu and endcpu */
905 if (hwloc_bitmap_realloc_by_cpu_index(set, endcpu) < 0)
906 return -1;
907
908 /* update first and last ulongs */
909 beginset = HWLOC_SUBBITMAP_INDEX(begincpu);
910 endset = HWLOC_SUBBITMAP_INDEX(endcpu);
911 if (beginset == endset) {
912 set->ulongs[beginset] |= HWLOC_SUBBITMAP_ULBIT_FROMTO(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu), HWLOC_SUBBITMAP_CPU_ULBIT(endcpu));
913 } else {
914 set->ulongs[beginset] |= HWLOC_SUBBITMAP_ULBIT_FROM(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu));
915 set->ulongs[endset] |= HWLOC_SUBBITMAP_ULBIT_TO(HWLOC_SUBBITMAP_CPU_ULBIT(endcpu));
916 }
917 /* set ulongs in the middle of the range */
918 for(i=beginset+1; i<endset; i++)
919 set->ulongs[i] = HWLOC_SUBBITMAP_FULL;
920 }
921
922 return 0;
923 }
924
hwloc_bitmap_set_ith_ulong(struct hwloc_bitmap_s * set,unsigned i,unsigned long mask)925 int hwloc_bitmap_set_ith_ulong(struct hwloc_bitmap_s *set, unsigned i, unsigned long mask)
926 {
927 HWLOC__BITMAP_CHECK(set);
928
929 if (hwloc_bitmap_realloc_by_ulongs(set, i+1) < 0)
930 return -1;
931
932 set->ulongs[i] = mask;
933 return 0;
934 }
935
hwloc_bitmap_clr(struct hwloc_bitmap_s * set,unsigned cpu)936 int hwloc_bitmap_clr(struct hwloc_bitmap_s * set, unsigned cpu)
937 {
938 unsigned index_ = HWLOC_SUBBITMAP_INDEX(cpu);
939
940 HWLOC__BITMAP_CHECK(set);
941
942 /* nothing to do if clearing inside the infinitely-unset part of the bitmap */
943 if (!set->infinite && cpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
944 return 0;
945
946 if (hwloc_bitmap_realloc_by_cpu_index(set, cpu) < 0)
947 return -1;
948
949 set->ulongs[index_] &= ~HWLOC_SUBBITMAP_CPU(cpu);
950 return 0;
951 }
952
hwloc_bitmap_clr_range(struct hwloc_bitmap_s * set,unsigned begincpu,int _endcpu)953 int hwloc_bitmap_clr_range(struct hwloc_bitmap_s * set, unsigned begincpu, int _endcpu)
954 {
955 unsigned i;
956 unsigned beginset,endset;
957 unsigned endcpu = (unsigned) _endcpu;
958
959 HWLOC__BITMAP_CHECK(set);
960
961 if (endcpu < begincpu)
962 return 0;
963
964 if (!set->infinite && begincpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
965 /* clearing only in the already-unset infinite part, nothing to do */
966 return 0;
967
968 if (_endcpu == -1) {
969 /* infinite range */
970
971 /* make sure we can play with the ulong that contains begincpu */
972 if (hwloc_bitmap_realloc_by_cpu_index(set, begincpu) < 0)
973 return -1;
974
975 /* update the ulong that contains begincpu */
976 beginset = HWLOC_SUBBITMAP_INDEX(begincpu);
977 set->ulongs[beginset] &= ~HWLOC_SUBBITMAP_ULBIT_FROM(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu));
978 /* clear ulong after begincpu if any already allocated */
979 for(i=beginset+1; i<set->ulongs_count; i++)
980 set->ulongs[i] = HWLOC_SUBBITMAP_ZERO;
981 /* mark the infinity as unset */
982 set->infinite = 0;
983 } else {
984 /* finite range */
985
986 /* ignore the part of the range that overlaps with the already-unset infinite part */
987 if (!set->infinite && endcpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
988 endcpu = set->ulongs_count * HWLOC_BITS_PER_LONG - 1;
989 /* make sure we can play with the ulongs that contain begincpu and endcpu */
990 if (hwloc_bitmap_realloc_by_cpu_index(set, endcpu) < 0)
991 return -1;
992
993 /* update first and last ulongs */
994 beginset = HWLOC_SUBBITMAP_INDEX(begincpu);
995 endset = HWLOC_SUBBITMAP_INDEX(endcpu);
996 if (beginset == endset) {
997 set->ulongs[beginset] &= ~HWLOC_SUBBITMAP_ULBIT_FROMTO(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu), HWLOC_SUBBITMAP_CPU_ULBIT(endcpu));
998 } else {
999 set->ulongs[beginset] &= ~HWLOC_SUBBITMAP_ULBIT_FROM(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu));
1000 set->ulongs[endset] &= ~HWLOC_SUBBITMAP_ULBIT_TO(HWLOC_SUBBITMAP_CPU_ULBIT(endcpu));
1001 }
1002 /* clear ulongs in the middle of the range */
1003 for(i=beginset+1; i<endset; i++)
1004 set->ulongs[i] = HWLOC_SUBBITMAP_ZERO;
1005 }
1006
1007 return 0;
1008 }
1009
hwloc_bitmap_isset(const struct hwloc_bitmap_s * set,unsigned cpu)1010 int hwloc_bitmap_isset(const struct hwloc_bitmap_s * set, unsigned cpu)
1011 {
1012 unsigned index_ = HWLOC_SUBBITMAP_INDEX(cpu);
1013
1014 HWLOC__BITMAP_CHECK(set);
1015
1016 return (HWLOC_SUBBITMAP_READULONG(set, index_) & HWLOC_SUBBITMAP_CPU(cpu)) != 0;
1017 }
1018
hwloc_bitmap_iszero(const struct hwloc_bitmap_s * set)1019 int hwloc_bitmap_iszero(const struct hwloc_bitmap_s *set)
1020 {
1021 unsigned i;
1022
1023 HWLOC__BITMAP_CHECK(set);
1024
1025 if (set->infinite)
1026 return 0;
1027 for(i=0; i<set->ulongs_count; i++)
1028 if (set->ulongs[i] != HWLOC_SUBBITMAP_ZERO)
1029 return 0;
1030 return 1;
1031 }
1032
hwloc_bitmap_isfull(const struct hwloc_bitmap_s * set)1033 int hwloc_bitmap_isfull(const struct hwloc_bitmap_s *set)
1034 {
1035 unsigned i;
1036
1037 HWLOC__BITMAP_CHECK(set);
1038
1039 if (!set->infinite)
1040 return 0;
1041 for(i=0; i<set->ulongs_count; i++)
1042 if (set->ulongs[i] != HWLOC_SUBBITMAP_FULL)
1043 return 0;
1044 return 1;
1045 }
1046
hwloc_bitmap_isequal(const struct hwloc_bitmap_s * set1,const struct hwloc_bitmap_s * set2)1047 int hwloc_bitmap_isequal (const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
1048 {
1049 unsigned count1 = set1->ulongs_count;
1050 unsigned count2 = set2->ulongs_count;
1051 unsigned min_count = count1 < count2 ? count1 : count2;
1052 unsigned i;
1053
1054 HWLOC__BITMAP_CHECK(set1);
1055 HWLOC__BITMAP_CHECK(set2);
1056
1057 for(i=0; i<min_count; i++)
1058 if (set1->ulongs[i] != set2->ulongs[i])
1059 return 0;
1060
1061 if (count1 != count2) {
1062 unsigned long w1 = set1->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
1063 unsigned long w2 = set2->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
1064 for(i=min_count; i<count1; i++) {
1065 if (set1->ulongs[i] != w2)
1066 return 0;
1067 }
1068 for(i=min_count; i<count2; i++) {
1069 if (set2->ulongs[i] != w1)
1070 return 0;
1071 }
1072 }
1073
1074 if (set1->infinite != set2->infinite)
1075 return 0;
1076
1077 return 1;
1078 }
1079
hwloc_bitmap_intersects(const struct hwloc_bitmap_s * set1,const struct hwloc_bitmap_s * set2)1080 int hwloc_bitmap_intersects (const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
1081 {
1082 unsigned count1 = set1->ulongs_count;
1083 unsigned count2 = set2->ulongs_count;
1084 unsigned min_count = count1 < count2 ? count1 : count2;
1085 unsigned i;
1086
1087 HWLOC__BITMAP_CHECK(set1);
1088 HWLOC__BITMAP_CHECK(set2);
1089
1090 for(i=0; i<min_count; i++)
1091 if (set1->ulongs[i] & set2->ulongs[i])
1092 return 1;
1093
1094 if (count1 != count2) {
1095 if (set2->infinite) {
1096 for(i=min_count; i<set1->ulongs_count; i++)
1097 if (set1->ulongs[i])
1098 return 1;
1099 }
1100 if (set1->infinite) {
1101 for(i=min_count; i<set2->ulongs_count; i++)
1102 if (set2->ulongs[i])
1103 return 1;
1104 }
1105 }
1106
1107 if (set1->infinite && set2->infinite)
1108 return 1;
1109
1110 return 0;
1111 }
1112
hwloc_bitmap_isincluded(const struct hwloc_bitmap_s * sub_set,const struct hwloc_bitmap_s * super_set)1113 int hwloc_bitmap_isincluded (const struct hwloc_bitmap_s *sub_set, const struct hwloc_bitmap_s *super_set)
1114 {
1115 unsigned super_count = super_set->ulongs_count;
1116 unsigned sub_count = sub_set->ulongs_count;
1117 unsigned min_count = super_count < sub_count ? super_count : sub_count;
1118 unsigned i;
1119
1120 HWLOC__BITMAP_CHECK(sub_set);
1121 HWLOC__BITMAP_CHECK(super_set);
1122
1123 for(i=0; i<min_count; i++)
1124 if (super_set->ulongs[i] != (super_set->ulongs[i] | sub_set->ulongs[i]))
1125 return 0;
1126
1127 if (super_count != sub_count) {
1128 if (!super_set->infinite)
1129 for(i=min_count; i<sub_count; i++)
1130 if (sub_set->ulongs[i])
1131 return 0;
1132 if (sub_set->infinite)
1133 for(i=min_count; i<super_count; i++)
1134 if (super_set->ulongs[i] != HWLOC_SUBBITMAP_FULL)
1135 return 0;
1136 }
1137
1138 if (sub_set->infinite && !super_set->infinite)
1139 return 0;
1140
1141 return 1;
1142 }
1143
hwloc_bitmap_or(struct hwloc_bitmap_s * res,const struct hwloc_bitmap_s * set1,const struct hwloc_bitmap_s * set2)1144 int hwloc_bitmap_or (struct hwloc_bitmap_s *res, const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
1145 {
1146 /* cache counts so that we can reset res even if it's also set1 or set2 */
1147 unsigned count1 = set1->ulongs_count;
1148 unsigned count2 = set2->ulongs_count;
1149 unsigned max_count = count1 > count2 ? count1 : count2;
1150 unsigned min_count = count1 + count2 - max_count;
1151 unsigned i;
1152
1153 HWLOC__BITMAP_CHECK(res);
1154 HWLOC__BITMAP_CHECK(set1);
1155 HWLOC__BITMAP_CHECK(set2);
1156
1157 if (hwloc_bitmap_reset_by_ulongs(res, max_count) < 0)
1158 return -1;
1159
1160 for(i=0; i<min_count; i++)
1161 res->ulongs[i] = set1->ulongs[i] | set2->ulongs[i];
1162
1163 if (count1 != count2) {
1164 if (min_count < count1) {
1165 if (set2->infinite) {
1166 res->ulongs_count = min_count;
1167 } else {
1168 for(i=min_count; i<max_count; i++)
1169 res->ulongs[i] = set1->ulongs[i];
1170 }
1171 } else {
1172 if (set1->infinite) {
1173 res->ulongs_count = min_count;
1174 } else {
1175 for(i=min_count; i<max_count; i++)
1176 res->ulongs[i] = set2->ulongs[i];
1177 }
1178 }
1179 }
1180
1181 res->infinite = set1->infinite || set2->infinite;
1182 return 0;
1183 }
1184
hwloc_bitmap_and(struct hwloc_bitmap_s * res,const struct hwloc_bitmap_s * set1,const struct hwloc_bitmap_s * set2)1185 int hwloc_bitmap_and (struct hwloc_bitmap_s *res, const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
1186 {
1187 /* cache counts so that we can reset res even if it's also set1 or set2 */
1188 unsigned count1 = set1->ulongs_count;
1189 unsigned count2 = set2->ulongs_count;
1190 unsigned max_count = count1 > count2 ? count1 : count2;
1191 unsigned min_count = count1 + count2 - max_count;
1192 unsigned i;
1193
1194 HWLOC__BITMAP_CHECK(res);
1195 HWLOC__BITMAP_CHECK(set1);
1196 HWLOC__BITMAP_CHECK(set2);
1197
1198 if (hwloc_bitmap_reset_by_ulongs(res, max_count) < 0)
1199 return -1;
1200
1201 for(i=0; i<min_count; i++)
1202 res->ulongs[i] = set1->ulongs[i] & set2->ulongs[i];
1203
1204 if (count1 != count2) {
1205 if (min_count < count1) {
1206 if (set2->infinite) {
1207 for(i=min_count; i<max_count; i++)
1208 res->ulongs[i] = set1->ulongs[i];
1209 } else {
1210 res->ulongs_count = min_count;
1211 }
1212 } else {
1213 if (set1->infinite) {
1214 for(i=min_count; i<max_count; i++)
1215 res->ulongs[i] = set2->ulongs[i];
1216 } else {
1217 res->ulongs_count = min_count;
1218 }
1219 }
1220 }
1221
1222 res->infinite = set1->infinite && set2->infinite;
1223 return 0;
1224 }
1225
hwloc_bitmap_andnot(struct hwloc_bitmap_s * res,const struct hwloc_bitmap_s * set1,const struct hwloc_bitmap_s * set2)1226 int hwloc_bitmap_andnot (struct hwloc_bitmap_s *res, const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
1227 {
1228 /* cache counts so that we can reset res even if it's also set1 or set2 */
1229 unsigned count1 = set1->ulongs_count;
1230 unsigned count2 = set2->ulongs_count;
1231 unsigned max_count = count1 > count2 ? count1 : count2;
1232 unsigned min_count = count1 + count2 - max_count;
1233 unsigned i;
1234
1235 HWLOC__BITMAP_CHECK(res);
1236 HWLOC__BITMAP_CHECK(set1);
1237 HWLOC__BITMAP_CHECK(set2);
1238
1239 if (hwloc_bitmap_reset_by_ulongs(res, max_count) < 0)
1240 return -1;
1241
1242 for(i=0; i<min_count; i++)
1243 res->ulongs[i] = set1->ulongs[i] & ~set2->ulongs[i];
1244
1245 if (count1 != count2) {
1246 if (min_count < count1) {
1247 if (!set2->infinite) {
1248 for(i=min_count; i<max_count; i++)
1249 res->ulongs[i] = set1->ulongs[i];
1250 } else {
1251 res->ulongs_count = min_count;
1252 }
1253 } else {
1254 if (set1->infinite) {
1255 for(i=min_count; i<max_count; i++)
1256 res->ulongs[i] = ~set2->ulongs[i];
1257 } else {
1258 res->ulongs_count = min_count;
1259 }
1260 }
1261 }
1262
1263 res->infinite = set1->infinite && !set2->infinite;
1264 return 0;
1265 }
1266
hwloc_bitmap_xor(struct hwloc_bitmap_s * res,const struct hwloc_bitmap_s * set1,const struct hwloc_bitmap_s * set2)1267 int hwloc_bitmap_xor (struct hwloc_bitmap_s *res, const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
1268 {
1269 /* cache counts so that we can reset res even if it's also set1 or set2 */
1270 unsigned count1 = set1->ulongs_count;
1271 unsigned count2 = set2->ulongs_count;
1272 unsigned max_count = count1 > count2 ? count1 : count2;
1273 unsigned min_count = count1 + count2 - max_count;
1274 unsigned i;
1275
1276 HWLOC__BITMAP_CHECK(res);
1277 HWLOC__BITMAP_CHECK(set1);
1278 HWLOC__BITMAP_CHECK(set2);
1279
1280 if (hwloc_bitmap_reset_by_ulongs(res, max_count) < 0)
1281 return -1;
1282
1283 for(i=0; i<min_count; i++)
1284 res->ulongs[i] = set1->ulongs[i] ^ set2->ulongs[i];
1285
1286 if (count1 != count2) {
1287 if (min_count < count1) {
1288 unsigned long w2 = set2->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
1289 for(i=min_count; i<max_count; i++)
1290 res->ulongs[i] = set1->ulongs[i] ^ w2;
1291 } else {
1292 unsigned long w1 = set1->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
1293 for(i=min_count; i<max_count; i++)
1294 res->ulongs[i] = set2->ulongs[i] ^ w1;
1295 }
1296 }
1297
1298 res->infinite = (!set1->infinite) != (!set2->infinite);
1299 return 0;
1300 }
1301
hwloc_bitmap_not(struct hwloc_bitmap_s * res,const struct hwloc_bitmap_s * set)1302 int hwloc_bitmap_not (struct hwloc_bitmap_s *res, const struct hwloc_bitmap_s *set)
1303 {
1304 unsigned count = set->ulongs_count;
1305 unsigned i;
1306
1307 HWLOC__BITMAP_CHECK(res);
1308 HWLOC__BITMAP_CHECK(set);
1309
1310 if (hwloc_bitmap_reset_by_ulongs(res, count) < 0)
1311 return -1;
1312
1313 for(i=0; i<count; i++)
1314 res->ulongs[i] = ~set->ulongs[i];
1315
1316 res->infinite = !set->infinite;
1317 return 0;
1318 }
1319
hwloc_bitmap_first(const struct hwloc_bitmap_s * set)1320 int hwloc_bitmap_first(const struct hwloc_bitmap_s * set)
1321 {
1322 unsigned i;
1323
1324 HWLOC__BITMAP_CHECK(set);
1325
1326 for(i=0; i<set->ulongs_count; i++) {
1327 /* subsets are unsigned longs, use ffsl */
1328 unsigned long w = set->ulongs[i];
1329 if (w)
1330 return hwloc_ffsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
1331 }
1332
1333 if (set->infinite)
1334 return set->ulongs_count * HWLOC_BITS_PER_LONG;
1335
1336 return -1;
1337 }
1338
hwloc_bitmap_first_unset(const struct hwloc_bitmap_s * set)1339 int hwloc_bitmap_first_unset(const struct hwloc_bitmap_s * set)
1340 {
1341 unsigned i;
1342
1343 HWLOC__BITMAP_CHECK(set);
1344
1345 for(i=0; i<set->ulongs_count; i++) {
1346 /* subsets are unsigned longs, use ffsl */
1347 unsigned long w = ~set->ulongs[i];
1348 if (w)
1349 return hwloc_ffsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
1350 }
1351
1352 if (!set->infinite)
1353 return set->ulongs_count * HWLOC_BITS_PER_LONG;
1354
1355 return -1;
1356 }
1357
hwloc_bitmap_last(const struct hwloc_bitmap_s * set)1358 int hwloc_bitmap_last(const struct hwloc_bitmap_s * set)
1359 {
1360 int i;
1361
1362 HWLOC__BITMAP_CHECK(set);
1363
1364 if (set->infinite)
1365 return -1;
1366
1367 for(i=(int)set->ulongs_count-1; i>=0; i--) {
1368 /* subsets are unsigned longs, use flsl */
1369 unsigned long w = set->ulongs[i];
1370 if (w)
1371 return hwloc_flsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
1372 }
1373
1374 return -1;
1375 }
1376
hwloc_bitmap_last_unset(const struct hwloc_bitmap_s * set)1377 int hwloc_bitmap_last_unset(const struct hwloc_bitmap_s * set)
1378 {
1379 int i;
1380
1381 HWLOC__BITMAP_CHECK(set);
1382
1383 if (!set->infinite)
1384 return -1;
1385
1386 for(i=(int)set->ulongs_count-1; i>=0; i--) {
1387 /* subsets are unsigned longs, use flsl */
1388 unsigned long w = ~set->ulongs[i];
1389 if (w)
1390 return hwloc_flsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
1391 }
1392
1393 return -1;
1394 }
1395
hwloc_bitmap_next(const struct hwloc_bitmap_s * set,int prev_cpu)1396 int hwloc_bitmap_next(const struct hwloc_bitmap_s * set, int prev_cpu)
1397 {
1398 unsigned i = HWLOC_SUBBITMAP_INDEX(prev_cpu + 1);
1399
1400 HWLOC__BITMAP_CHECK(set);
1401
1402 if (i >= set->ulongs_count) {
1403 if (set->infinite)
1404 return prev_cpu + 1;
1405 else
1406 return -1;
1407 }
1408
1409 for(; i<set->ulongs_count; i++) {
1410 /* subsets are unsigned longs, use ffsl */
1411 unsigned long w = set->ulongs[i];
1412
1413 /* if the prev cpu is in the same word as the possible next one,
1414 we need to mask out previous cpus */
1415 if (prev_cpu >= 0 && HWLOC_SUBBITMAP_INDEX((unsigned) prev_cpu) == i)
1416 w &= ~HWLOC_SUBBITMAP_ULBIT_TO(HWLOC_SUBBITMAP_CPU_ULBIT(prev_cpu));
1417
1418 if (w)
1419 return hwloc_ffsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
1420 }
1421
1422 if (set->infinite)
1423 return set->ulongs_count * HWLOC_BITS_PER_LONG;
1424
1425 return -1;
1426 }
1427
hwloc_bitmap_next_unset(const struct hwloc_bitmap_s * set,int prev_cpu)1428 int hwloc_bitmap_next_unset(const struct hwloc_bitmap_s * set, int prev_cpu)
1429 {
1430 unsigned i = HWLOC_SUBBITMAP_INDEX(prev_cpu + 1);
1431
1432 HWLOC__BITMAP_CHECK(set);
1433
1434 if (i >= set->ulongs_count) {
1435 if (!set->infinite)
1436 return prev_cpu + 1;
1437 else
1438 return -1;
1439 }
1440
1441 for(; i<set->ulongs_count; i++) {
1442 /* subsets are unsigned longs, use ffsl */
1443 unsigned long w = ~set->ulongs[i];
1444
1445 /* if the prev cpu is in the same word as the possible next one,
1446 we need to mask out previous cpus */
1447 if (prev_cpu >= 0 && HWLOC_SUBBITMAP_INDEX((unsigned) prev_cpu) == i)
1448 w &= ~HWLOC_SUBBITMAP_ULBIT_TO(HWLOC_SUBBITMAP_CPU_ULBIT(prev_cpu));
1449
1450 if (w)
1451 return hwloc_ffsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
1452 }
1453
1454 if (!set->infinite)
1455 return set->ulongs_count * HWLOC_BITS_PER_LONG;
1456
1457 return -1;
1458 }
1459
hwloc_bitmap_singlify(struct hwloc_bitmap_s * set)1460 int hwloc_bitmap_singlify(struct hwloc_bitmap_s * set)
1461 {
1462 unsigned i;
1463 int found = 0;
1464
1465 HWLOC__BITMAP_CHECK(set);
1466
1467 for(i=0; i<set->ulongs_count; i++) {
1468 if (found) {
1469 set->ulongs[i] = HWLOC_SUBBITMAP_ZERO;
1470 continue;
1471 } else {
1472 /* subsets are unsigned longs, use ffsl */
1473 unsigned long w = set->ulongs[i];
1474 if (w) {
1475 int _ffs = hwloc_ffsl(w);
1476 set->ulongs[i] = HWLOC_SUBBITMAP_CPU(_ffs-1);
1477 found = 1;
1478 }
1479 }
1480 }
1481
1482 if (set->infinite) {
1483 if (found) {
1484 set->infinite = 0;
1485 } else {
1486 /* set the first non allocated bit */
1487 unsigned first = set->ulongs_count * HWLOC_BITS_PER_LONG;
1488 set->infinite = 0; /* do not let realloc fill the newly allocated sets */
1489 return hwloc_bitmap_set(set, first);
1490 }
1491 }
1492
1493 return 0;
1494 }
1495
hwloc_bitmap_compare_first(const struct hwloc_bitmap_s * set1,const struct hwloc_bitmap_s * set2)1496 int hwloc_bitmap_compare_first(const struct hwloc_bitmap_s * set1, const struct hwloc_bitmap_s * set2)
1497 {
1498 unsigned count1 = set1->ulongs_count;
1499 unsigned count2 = set2->ulongs_count;
1500 unsigned max_count = count1 > count2 ? count1 : count2;
1501 unsigned min_count = count1 + count2 - max_count;
1502 unsigned i;
1503
1504 HWLOC__BITMAP_CHECK(set1);
1505 HWLOC__BITMAP_CHECK(set2);
1506
1507 for(i=0; i<min_count; i++) {
1508 unsigned long w1 = set1->ulongs[i];
1509 unsigned long w2 = set2->ulongs[i];
1510 if (w1 || w2) {
1511 int _ffs1 = hwloc_ffsl(w1);
1512 int _ffs2 = hwloc_ffsl(w2);
1513 /* if both have a bit set, compare for real */
1514 if (_ffs1 && _ffs2)
1515 return _ffs1-_ffs2;
1516 /* one is empty, and it is considered higher, so reverse-compare them */
1517 return _ffs2-_ffs1;
1518 }
1519 }
1520
1521 if (count1 != count2) {
1522 if (min_count < count2) {
1523 for(i=min_count; i<count2; i++) {
1524 unsigned long w2 = set2->ulongs[i];
1525 if (set1->infinite)
1526 return -!(w2 & 1);
1527 else if (w2)
1528 return 1;
1529 }
1530 } else {
1531 for(i=min_count; i<count1; i++) {
1532 unsigned long w1 = set1->ulongs[i];
1533 if (set2->infinite)
1534 return !(w1 & 1);
1535 else if (w1)
1536 return -1;
1537 }
1538 }
1539 }
1540
1541 return !!set1->infinite - !!set2->infinite;
1542 }
1543
hwloc_bitmap_compare(const struct hwloc_bitmap_s * set1,const struct hwloc_bitmap_s * set2)1544 int hwloc_bitmap_compare(const struct hwloc_bitmap_s * set1, const struct hwloc_bitmap_s * set2)
1545 {
1546 unsigned count1 = set1->ulongs_count;
1547 unsigned count2 = set2->ulongs_count;
1548 unsigned max_count = count1 > count2 ? count1 : count2;
1549 unsigned min_count = count1 + count2 - max_count;
1550 int i;
1551
1552 HWLOC__BITMAP_CHECK(set1);
1553 HWLOC__BITMAP_CHECK(set2);
1554
1555 if ((!set1->infinite) != (!set2->infinite))
1556 return !!set1->infinite - !!set2->infinite;
1557
1558 if (count1 != count2) {
1559 if (min_count < count2) {
1560 unsigned long val1 = set1->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
1561 for(i=(int)max_count-1; i>=(int) min_count; i--) {
1562 unsigned long val2 = set2->ulongs[i];
1563 if (val1 == val2)
1564 continue;
1565 return val1 < val2 ? -1 : 1;
1566 }
1567 } else {
1568 unsigned long val2 = set2->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
1569 for(i=(int)max_count-1; i>=(int) min_count; i--) {
1570 unsigned long val1 = set1->ulongs[i];
1571 if (val1 == val2)
1572 continue;
1573 return val1 < val2 ? -1 : 1;
1574 }
1575 }
1576 }
1577
1578 for(i=(int)min_count-1; i>=0; i--) {
1579 unsigned long val1 = set1->ulongs[i];
1580 unsigned long val2 = set2->ulongs[i];
1581 if (val1 == val2)
1582 continue;
1583 return val1 < val2 ? -1 : 1;
1584 }
1585
1586 return 0;
1587 }
1588
hwloc_bitmap_weight(const struct hwloc_bitmap_s * set)1589 int hwloc_bitmap_weight(const struct hwloc_bitmap_s * set)
1590 {
1591 int weight = 0;
1592 unsigned i;
1593
1594 HWLOC__BITMAP_CHECK(set);
1595
1596 if (set->infinite)
1597 return -1;
1598
1599 for(i=0; i<set->ulongs_count; i++)
1600 weight += hwloc_weight_long(set->ulongs[i]);
1601 return weight;
1602 }
1603
hwloc_bitmap_compare_inclusion(const struct hwloc_bitmap_s * set1,const struct hwloc_bitmap_s * set2)1604 int hwloc_bitmap_compare_inclusion(const struct hwloc_bitmap_s * set1, const struct hwloc_bitmap_s * set2)
1605 {
1606 unsigned max_count = set1->ulongs_count > set2->ulongs_count ? set1->ulongs_count : set2->ulongs_count;
1607 int result = HWLOC_BITMAP_EQUAL; /* means empty sets return equal */
1608 int empty1 = 1;
1609 int empty2 = 1;
1610 unsigned i;
1611
1612 HWLOC__BITMAP_CHECK(set1);
1613 HWLOC__BITMAP_CHECK(set2);
1614
1615 for(i=0; i<max_count; i++) {
1616 unsigned long val1 = HWLOC_SUBBITMAP_READULONG(set1, (unsigned) i);
1617 unsigned long val2 = HWLOC_SUBBITMAP_READULONG(set2, (unsigned) i);
1618
1619 if (!val1) {
1620 if (!val2)
1621 /* both empty, no change */
1622 continue;
1623
1624 /* val1 empty, val2 not */
1625 if (result == HWLOC_BITMAP_CONTAINS) {
1626 if (!empty2)
1627 return HWLOC_BITMAP_INTERSECTS;
1628 result = HWLOC_BITMAP_DIFFERENT;
1629 } else if (result == HWLOC_BITMAP_EQUAL) {
1630 result = HWLOC_BITMAP_INCLUDED;
1631 }
1632 /* no change otherwise */
1633
1634 } else if (!val2) {
1635 /* val2 empty, val1 not */
1636 if (result == HWLOC_BITMAP_INCLUDED) {
1637 if (!empty1)
1638 return HWLOC_BITMAP_INTERSECTS;
1639 result = HWLOC_BITMAP_DIFFERENT;
1640 } else if (result == HWLOC_BITMAP_EQUAL) {
1641 result = HWLOC_BITMAP_CONTAINS;
1642 }
1643 /* no change otherwise */
1644
1645 } else if (val1 == val2) {
1646 /* equal and not empty */
1647 if (result == HWLOC_BITMAP_DIFFERENT)
1648 return HWLOC_BITMAP_INTERSECTS;
1649 /* equal/contains/included unchanged */
1650
1651 } else if ((val1 & val2) == val1) {
1652 /* included and not empty */
1653 if (result == HWLOC_BITMAP_CONTAINS || result == HWLOC_BITMAP_DIFFERENT)
1654 return HWLOC_BITMAP_INTERSECTS;
1655 /* equal/included unchanged */
1656 result = HWLOC_BITMAP_INCLUDED;
1657
1658 } else if ((val1 & val2) == val2) {
1659 /* contains and not empty */
1660 if (result == HWLOC_BITMAP_INCLUDED || result == HWLOC_BITMAP_DIFFERENT)
1661 return HWLOC_BITMAP_INTERSECTS;
1662 /* equal/contains unchanged */
1663 result = HWLOC_BITMAP_CONTAINS;
1664
1665 } else if ((val1 & val2) != 0) {
1666 /* intersects and not empty */
1667 return HWLOC_BITMAP_INTERSECTS;
1668
1669 } else {
1670 /* different and not empty */
1671
1672 /* equal/included/contains with non-empty sets means intersects */
1673 if (result == HWLOC_BITMAP_EQUAL && !empty1 /* implies !empty2 */)
1674 return HWLOC_BITMAP_INTERSECTS;
1675 if (result == HWLOC_BITMAP_INCLUDED && !empty1)
1676 return HWLOC_BITMAP_INTERSECTS;
1677 if (result == HWLOC_BITMAP_CONTAINS && !empty2)
1678 return HWLOC_BITMAP_INTERSECTS;
1679 /* otherwise means different */
1680 result = HWLOC_BITMAP_DIFFERENT;
1681 }
1682
1683 empty1 &= !val1;
1684 empty2 &= !val2;
1685 }
1686
1687 if (!set1->infinite) {
1688 if (set2->infinite) {
1689 /* set2 infinite only */
1690 if (result == HWLOC_BITMAP_CONTAINS) {
1691 if (!empty2)
1692 return HWLOC_BITMAP_INTERSECTS;
1693 result = HWLOC_BITMAP_DIFFERENT;
1694 } else if (result == HWLOC_BITMAP_EQUAL) {
1695 result = HWLOC_BITMAP_INCLUDED;
1696 }
1697 /* no change otherwise */
1698 }
1699 } else if (!set2->infinite) {
1700 /* set1 infinite only */
1701 if (result == HWLOC_BITMAP_INCLUDED) {
1702 if (!empty1)
1703 return HWLOC_BITMAP_INTERSECTS;
1704 result = HWLOC_BITMAP_DIFFERENT;
1705 } else if (result == HWLOC_BITMAP_EQUAL) {
1706 result = HWLOC_BITMAP_CONTAINS;
1707 }
1708 /* no change otherwise */
1709 } else {
1710 /* both infinite */
1711 if (result == HWLOC_BITMAP_DIFFERENT)
1712 return HWLOC_BITMAP_INTERSECTS;
1713 /* equal/contains/included unchanged */
1714 }
1715
1716 return result;
1717 }
1718