1 /*
2 * Copyright © 2009 CNRS
3 * Copyright © 2009-2017 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 hwloc_bitmap_set_range(set, begin, val);
509 begin = -1;
510
511 } else if (*next == '-') {
512 /* starting a new range */
513 if (*(next+1) == '\0') {
514 /* infinite range */
515 hwloc_bitmap_set_range(set, val, -1);
516 break;
517 } else {
518 /* normal range */
519 begin = val;
520 }
521
522 } else if (*next == ',' || *next == ' ' || *next == '\0') {
523 /* single digit */
524 hwloc_bitmap_set(set, val);
525 }
526
527 if (*next == '\0')
528 break;
529 current = next+1;
530 }
531
532 return 0;
533
534 failed:
535 /* failure to parse */
536 hwloc_bitmap_zero(set);
537 return -1;
538 }
539
hwloc_bitmap_taskset_snprintf(char * __hwloc_restrict buf,size_t buflen,const struct hwloc_bitmap_s * __hwloc_restrict set)540 int hwloc_bitmap_taskset_snprintf(char * __hwloc_restrict buf, size_t buflen, const struct hwloc_bitmap_s * __hwloc_restrict set)
541 {
542 ssize_t size = buflen;
543 char *tmp = buf;
544 int res, ret = 0;
545 int started = 0;
546 int i;
547
548 HWLOC__BITMAP_CHECK(set);
549
550 /* mark the end in case we do nothing later */
551 if (buflen > 0)
552 tmp[0] = '\0';
553
554 if (set->infinite) {
555 res = hwloc_snprintf(tmp, size, "0xf...f");
556 started = 1;
557 if (res < 0)
558 return -1;
559 ret += res;
560 if (res >= size)
561 res = size>0 ? (int)size - 1 : 0;
562 tmp += res;
563 size -= res;
564 }
565
566 i=set->ulongs_count-1;
567
568 if (set->infinite) {
569 /* ignore starting FULL since we have 0xf...f already */
570 while (i>=0 && set->ulongs[i] == HWLOC_SUBBITMAP_FULL)
571 i--;
572 } else {
573 /* ignore starting ZERO except the last one */
574 while (i>=1 && set->ulongs[i] == HWLOC_SUBBITMAP_ZERO)
575 i--;
576 }
577
578 while (i>=0) {
579 unsigned long val = set->ulongs[i--];
580 if (started) {
581 /* print the whole subset */
582 #if HWLOC_BITS_PER_LONG == 64
583 res = hwloc_snprintf(tmp, size, "%016lx", val);
584 #else
585 res = hwloc_snprintf(tmp, size, "%08lx", val);
586 #endif
587 } else if (val || i == -1) {
588 res = hwloc_snprintf(tmp, size, "0x%lx", val);
589 started = 1;
590 } else {
591 res = 0;
592 }
593 if (res < 0)
594 return -1;
595 ret += res;
596 if (res >= size)
597 res = size>0 ? (int)size - 1 : 0;
598 tmp += res;
599 size -= res;
600 }
601
602 /* if didn't display anything, display 0x0 */
603 if (!ret) {
604 res = hwloc_snprintf(tmp, size, "0x0");
605 if (res < 0)
606 return -1;
607 ret += res;
608 }
609
610 return ret;
611 }
612
hwloc_bitmap_taskset_asprintf(char ** strp,const struct hwloc_bitmap_s * __hwloc_restrict set)613 int hwloc_bitmap_taskset_asprintf(char ** strp, const struct hwloc_bitmap_s * __hwloc_restrict set)
614 {
615 int len;
616 char *buf;
617
618 HWLOC__BITMAP_CHECK(set);
619
620 len = hwloc_bitmap_taskset_snprintf(NULL, 0, set);
621 buf = malloc(len+1);
622 if (!buf)
623 return -1;
624 *strp = buf;
625 return hwloc_bitmap_taskset_snprintf(buf, len+1, set);
626 }
627
hwloc_bitmap_taskset_sscanf(struct hwloc_bitmap_s * set,const char * __hwloc_restrict string)628 int hwloc_bitmap_taskset_sscanf(struct hwloc_bitmap_s *set, const char * __hwloc_restrict string)
629 {
630 const char * current = string;
631 int chars;
632 int count;
633 int infinite = 0;
634
635 if (!strncmp("0xf...f", current, 7)) {
636 /* infinite bitmap */
637 infinite = 1;
638 current += 7;
639 if (*current == '\0') {
640 /* special case for infinite/full bitmap */
641 hwloc_bitmap_fill(set);
642 return 0;
643 }
644 } else {
645 /* finite bitmap */
646 if (!strncmp("0x", current, 2))
647 current += 2;
648 if (*current == '\0') {
649 /* special case for empty bitmap */
650 hwloc_bitmap_zero(set);
651 return 0;
652 }
653 }
654 /* we know there are other characters now */
655
656 chars = (int)strlen(current);
657 count = (chars * 4 + HWLOC_BITS_PER_LONG - 1) / HWLOC_BITS_PER_LONG;
658
659 if (hwloc_bitmap_reset_by_ulongs(set, count) < 0)
660 return -1;
661 set->infinite = 0;
662
663 while (*current != '\0') {
664 int tmpchars;
665 char ustr[17];
666 unsigned long val;
667 char *next;
668
669 tmpchars = chars % (HWLOC_BITS_PER_LONG/4);
670 if (!tmpchars)
671 tmpchars = (HWLOC_BITS_PER_LONG/4);
672
673 memcpy(ustr, current, tmpchars);
674 ustr[tmpchars] = '\0';
675 val = strtoul(ustr, &next, 16);
676 if (*next != '\0')
677 goto failed;
678
679 set->ulongs[count-1] = val;
680
681 current += tmpchars;
682 chars -= tmpchars;
683 count--;
684 }
685
686 set->infinite = infinite; /* set at the end, to avoid spurious realloc with filled new ulongs */
687
688 return 0;
689
690 failed:
691 /* failure to parse */
692 hwloc_bitmap_zero(set);
693 return -1;
694 }
695
hwloc_bitmap__zero(struct hwloc_bitmap_s * set)696 static void hwloc_bitmap__zero(struct hwloc_bitmap_s *set)
697 {
698 unsigned i;
699 for(i=0; i<set->ulongs_count; i++)
700 set->ulongs[i] = HWLOC_SUBBITMAP_ZERO;
701 set->infinite = 0;
702 }
703
hwloc_bitmap_zero(struct hwloc_bitmap_s * set)704 void hwloc_bitmap_zero(struct hwloc_bitmap_s * set)
705 {
706 HWLOC__BITMAP_CHECK(set);
707
708 HWLOC_BUILD_ASSERT(HWLOC_BITMAP_PREALLOC_ULONGS >= 1);
709 if (hwloc_bitmap_reset_by_ulongs(set, 1) < 0) {
710 /* cannot fail since we preallocate some ulongs.
711 * if we ever preallocate nothing, we'll reset to 0 ulongs.
712 */
713 }
714 hwloc_bitmap__zero(set);
715 }
716
hwloc_bitmap__fill(struct hwloc_bitmap_s * set)717 static void hwloc_bitmap__fill(struct hwloc_bitmap_s * set)
718 {
719 unsigned i;
720 for(i=0; i<set->ulongs_count; i++)
721 set->ulongs[i] = HWLOC_SUBBITMAP_FULL;
722 set->infinite = 1;
723 }
724
hwloc_bitmap_fill(struct hwloc_bitmap_s * set)725 void hwloc_bitmap_fill(struct hwloc_bitmap_s * set)
726 {
727 HWLOC__BITMAP_CHECK(set);
728
729 HWLOC_BUILD_ASSERT(HWLOC_BITMAP_PREALLOC_ULONGS >= 1);
730 if (hwloc_bitmap_reset_by_ulongs(set, 1) < 0) {
731 /* cannot fail since we pre-allocate some ulongs.
732 * if we ever pre-allocate nothing, we'll reset to 0 ulongs.
733 */
734 }
735 hwloc_bitmap__fill(set);
736 }
737
hwloc_bitmap_from_ulong(struct hwloc_bitmap_s * set,unsigned long mask)738 int hwloc_bitmap_from_ulong(struct hwloc_bitmap_s *set, unsigned long mask)
739 {
740 HWLOC__BITMAP_CHECK(set);
741
742 HWLOC_BUILD_ASSERT(HWLOC_BITMAP_PREALLOC_ULONGS >= 1);
743 if (hwloc_bitmap_reset_by_ulongs(set, 1) < 0) {
744 /* cannot fail since we pre-allocate some ulongs.
745 * if ever pre-allocate nothing, we may have to return a failure.
746 */
747 }
748 set->ulongs[0] = mask; /* there's always at least one ulong allocated */
749 set->infinite = 0;
750 return 0;
751 }
752
hwloc_bitmap_from_ith_ulong(struct hwloc_bitmap_s * set,unsigned i,unsigned long mask)753 int hwloc_bitmap_from_ith_ulong(struct hwloc_bitmap_s *set, unsigned i, unsigned long mask)
754 {
755 unsigned j;
756
757 HWLOC__BITMAP_CHECK(set);
758
759 if (hwloc_bitmap_reset_by_ulongs(set, i+1) < 0)
760 return -1;
761
762 set->ulongs[i] = mask;
763 for(j=0; j<i; j++)
764 set->ulongs[j] = HWLOC_SUBBITMAP_ZERO;
765 set->infinite = 0;
766 return 0;
767 }
768
hwloc_bitmap_to_ulong(const struct hwloc_bitmap_s * set)769 unsigned long hwloc_bitmap_to_ulong(const struct hwloc_bitmap_s *set)
770 {
771 HWLOC__BITMAP_CHECK(set);
772
773 return set->ulongs[0]; /* there's always at least one ulong allocated */
774 }
775
hwloc_bitmap_to_ith_ulong(const struct hwloc_bitmap_s * set,unsigned i)776 unsigned long hwloc_bitmap_to_ith_ulong(const struct hwloc_bitmap_s *set, unsigned i)
777 {
778 HWLOC__BITMAP_CHECK(set);
779
780 return HWLOC_SUBBITMAP_READULONG(set, i);
781 }
782
hwloc_bitmap_only(struct hwloc_bitmap_s * set,unsigned cpu)783 int hwloc_bitmap_only(struct hwloc_bitmap_s * set, unsigned cpu)
784 {
785 unsigned index_ = HWLOC_SUBBITMAP_INDEX(cpu);
786
787 HWLOC__BITMAP_CHECK(set);
788
789 if (hwloc_bitmap_reset_by_cpu_index(set, cpu) < 0)
790 return -1;
791
792 hwloc_bitmap__zero(set);
793 set->ulongs[index_] |= HWLOC_SUBBITMAP_CPU(cpu);
794 return 0;
795 }
796
hwloc_bitmap_allbut(struct hwloc_bitmap_s * set,unsigned cpu)797 int hwloc_bitmap_allbut(struct hwloc_bitmap_s * set, unsigned cpu)
798 {
799 unsigned index_ = HWLOC_SUBBITMAP_INDEX(cpu);
800
801 HWLOC__BITMAP_CHECK(set);
802
803 if (hwloc_bitmap_reset_by_cpu_index(set, cpu) < 0)
804 return -1;
805
806 hwloc_bitmap__fill(set);
807 set->ulongs[index_] &= ~HWLOC_SUBBITMAP_CPU(cpu);
808 return 0;
809 }
810
hwloc_bitmap_set(struct hwloc_bitmap_s * set,unsigned cpu)811 int hwloc_bitmap_set(struct hwloc_bitmap_s * set, unsigned cpu)
812 {
813 unsigned index_ = HWLOC_SUBBITMAP_INDEX(cpu);
814
815 HWLOC__BITMAP_CHECK(set);
816
817 /* nothing to do if setting inside the infinite part of the bitmap */
818 if (set->infinite && cpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
819 return 0;
820
821 if (hwloc_bitmap_realloc_by_cpu_index(set, cpu) < 0)
822 return -1;
823
824 set->ulongs[index_] |= HWLOC_SUBBITMAP_CPU(cpu);
825 return 0;
826 }
827
hwloc_bitmap_set_range(struct hwloc_bitmap_s * set,unsigned begincpu,int _endcpu)828 int hwloc_bitmap_set_range(struct hwloc_bitmap_s * set, unsigned begincpu, int _endcpu)
829 {
830 unsigned i;
831 unsigned beginset,endset;
832 unsigned endcpu = (unsigned) _endcpu;
833
834 HWLOC__BITMAP_CHECK(set);
835
836 if (endcpu < begincpu)
837 return 0;
838 if (set->infinite && begincpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
839 /* setting only in the already-set infinite part, nothing to do */
840 return 0;
841
842 if (_endcpu == -1) {
843 /* infinite range */
844
845 /* make sure we can play with the ulong that contains begincpu */
846 if (hwloc_bitmap_realloc_by_cpu_index(set, begincpu) < 0)
847 return -1;
848
849 /* update the ulong that contains begincpu */
850 beginset = HWLOC_SUBBITMAP_INDEX(begincpu);
851 set->ulongs[beginset] |= HWLOC_SUBBITMAP_ULBIT_FROM(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu));
852 /* set ulongs after begincpu if any already allocated */
853 for(i=beginset+1; i<set->ulongs_count; i++)
854 set->ulongs[i] = HWLOC_SUBBITMAP_FULL;
855 /* mark the infinity as set */
856 set->infinite = 1;
857 } else {
858 /* finite range */
859
860 /* ignore the part of the range that overlaps with the already-set infinite part */
861 if (set->infinite && endcpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
862 endcpu = set->ulongs_count * HWLOC_BITS_PER_LONG - 1;
863 /* make sure we can play with the ulongs that contain begincpu and endcpu */
864 if (hwloc_bitmap_realloc_by_cpu_index(set, endcpu) < 0)
865 return -1;
866
867 /* update first and last ulongs */
868 beginset = HWLOC_SUBBITMAP_INDEX(begincpu);
869 endset = HWLOC_SUBBITMAP_INDEX(endcpu);
870 if (beginset == endset) {
871 set->ulongs[beginset] |= HWLOC_SUBBITMAP_ULBIT_FROMTO(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu), HWLOC_SUBBITMAP_CPU_ULBIT(endcpu));
872 } else {
873 set->ulongs[beginset] |= HWLOC_SUBBITMAP_ULBIT_FROM(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu));
874 set->ulongs[endset] |= HWLOC_SUBBITMAP_ULBIT_TO(HWLOC_SUBBITMAP_CPU_ULBIT(endcpu));
875 }
876 /* set ulongs in the middle of the range */
877 for(i=beginset+1; i<endset; i++)
878 set->ulongs[i] = HWLOC_SUBBITMAP_FULL;
879 }
880
881 return 0;
882 }
883
hwloc_bitmap_set_ith_ulong(struct hwloc_bitmap_s * set,unsigned i,unsigned long mask)884 int hwloc_bitmap_set_ith_ulong(struct hwloc_bitmap_s *set, unsigned i, unsigned long mask)
885 {
886 HWLOC__BITMAP_CHECK(set);
887
888 if (hwloc_bitmap_realloc_by_ulongs(set, i+1) < 0)
889 return -1;
890
891 set->ulongs[i] = mask;
892 return 0;
893 }
894
hwloc_bitmap_clr(struct hwloc_bitmap_s * set,unsigned cpu)895 int hwloc_bitmap_clr(struct hwloc_bitmap_s * set, unsigned cpu)
896 {
897 unsigned index_ = HWLOC_SUBBITMAP_INDEX(cpu);
898
899 HWLOC__BITMAP_CHECK(set);
900
901 /* nothing to do if clearing inside the infinitely-unset part of the bitmap */
902 if (!set->infinite && cpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
903 return 0;
904
905 if (hwloc_bitmap_realloc_by_cpu_index(set, cpu) < 0)
906 return -1;
907
908 set->ulongs[index_] &= ~HWLOC_SUBBITMAP_CPU(cpu);
909 return 0;
910 }
911
hwloc_bitmap_clr_range(struct hwloc_bitmap_s * set,unsigned begincpu,int _endcpu)912 int hwloc_bitmap_clr_range(struct hwloc_bitmap_s * set, unsigned begincpu, int _endcpu)
913 {
914 unsigned i;
915 unsigned beginset,endset;
916 unsigned endcpu = (unsigned) _endcpu;
917
918 HWLOC__BITMAP_CHECK(set);
919
920 if (endcpu < begincpu)
921 return 0;
922
923 if (!set->infinite && begincpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
924 /* clearing only in the already-unset infinite part, nothing to do */
925 return 0;
926
927 if (_endcpu == -1) {
928 /* infinite range */
929
930 /* make sure we can play with the ulong that contains begincpu */
931 if (hwloc_bitmap_realloc_by_cpu_index(set, begincpu) < 0)
932 return -1;
933
934 /* update the ulong that contains begincpu */
935 beginset = HWLOC_SUBBITMAP_INDEX(begincpu);
936 set->ulongs[beginset] &= ~HWLOC_SUBBITMAP_ULBIT_FROM(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu));
937 /* clear ulong after begincpu if any already allocated */
938 for(i=beginset+1; i<set->ulongs_count; i++)
939 set->ulongs[i] = HWLOC_SUBBITMAP_ZERO;
940 /* mark the infinity as unset */
941 set->infinite = 0;
942 } else {
943 /* finite range */
944
945 /* ignore the part of the range that overlaps with the already-unset infinite part */
946 if (!set->infinite && endcpu >= set->ulongs_count * HWLOC_BITS_PER_LONG)
947 endcpu = set->ulongs_count * HWLOC_BITS_PER_LONG - 1;
948 /* make sure we can play with the ulongs that contain begincpu and endcpu */
949 if (hwloc_bitmap_realloc_by_cpu_index(set, endcpu) < 0)
950 return -1;
951
952 /* update first and last ulongs */
953 beginset = HWLOC_SUBBITMAP_INDEX(begincpu);
954 endset = HWLOC_SUBBITMAP_INDEX(endcpu);
955 if (beginset == endset) {
956 set->ulongs[beginset] &= ~HWLOC_SUBBITMAP_ULBIT_FROMTO(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu), HWLOC_SUBBITMAP_CPU_ULBIT(endcpu));
957 } else {
958 set->ulongs[beginset] &= ~HWLOC_SUBBITMAP_ULBIT_FROM(HWLOC_SUBBITMAP_CPU_ULBIT(begincpu));
959 set->ulongs[endset] &= ~HWLOC_SUBBITMAP_ULBIT_TO(HWLOC_SUBBITMAP_CPU_ULBIT(endcpu));
960 }
961 /* clear ulongs in the middle of the range */
962 for(i=beginset+1; i<endset; i++)
963 set->ulongs[i] = HWLOC_SUBBITMAP_ZERO;
964 }
965
966 return 0;
967 }
968
hwloc_bitmap_isset(const struct hwloc_bitmap_s * set,unsigned cpu)969 int hwloc_bitmap_isset(const struct hwloc_bitmap_s * set, unsigned cpu)
970 {
971 unsigned index_ = HWLOC_SUBBITMAP_INDEX(cpu);
972
973 HWLOC__BITMAP_CHECK(set);
974
975 return (HWLOC_SUBBITMAP_READULONG(set, index_) & HWLOC_SUBBITMAP_CPU(cpu)) != 0;
976 }
977
hwloc_bitmap_iszero(const struct hwloc_bitmap_s * set)978 int hwloc_bitmap_iszero(const struct hwloc_bitmap_s *set)
979 {
980 unsigned i;
981
982 HWLOC__BITMAP_CHECK(set);
983
984 if (set->infinite)
985 return 0;
986 for(i=0; i<set->ulongs_count; i++)
987 if (set->ulongs[i] != HWLOC_SUBBITMAP_ZERO)
988 return 0;
989 return 1;
990 }
991
hwloc_bitmap_isfull(const struct hwloc_bitmap_s * set)992 int hwloc_bitmap_isfull(const struct hwloc_bitmap_s *set)
993 {
994 unsigned i;
995
996 HWLOC__BITMAP_CHECK(set);
997
998 if (!set->infinite)
999 return 0;
1000 for(i=0; i<set->ulongs_count; i++)
1001 if (set->ulongs[i] != HWLOC_SUBBITMAP_FULL)
1002 return 0;
1003 return 1;
1004 }
1005
hwloc_bitmap_isequal(const struct hwloc_bitmap_s * set1,const struct hwloc_bitmap_s * set2)1006 int hwloc_bitmap_isequal (const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
1007 {
1008 unsigned count1 = set1->ulongs_count;
1009 unsigned count2 = set2->ulongs_count;
1010 unsigned min_count = count1 < count2 ? count1 : count2;
1011 unsigned i;
1012
1013 HWLOC__BITMAP_CHECK(set1);
1014 HWLOC__BITMAP_CHECK(set2);
1015
1016 for(i=0; i<min_count; i++)
1017 if (set1->ulongs[i] != set2->ulongs[i])
1018 return 0;
1019
1020 if (count1 != count2) {
1021 unsigned long w1 = set1->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
1022 unsigned long w2 = set2->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
1023 for(i=min_count; i<count1; i++) {
1024 if (set1->ulongs[i] != w2)
1025 return 0;
1026 }
1027 for(i=min_count; i<count2; i++) {
1028 if (set2->ulongs[i] != w1)
1029 return 0;
1030 }
1031 }
1032
1033 if (set1->infinite != set2->infinite)
1034 return 0;
1035
1036 return 1;
1037 }
1038
hwloc_bitmap_intersects(const struct hwloc_bitmap_s * set1,const struct hwloc_bitmap_s * set2)1039 int hwloc_bitmap_intersects (const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
1040 {
1041 unsigned count1 = set1->ulongs_count;
1042 unsigned count2 = set2->ulongs_count;
1043 unsigned min_count = count1 < count2 ? count1 : count2;
1044 unsigned i;
1045
1046 HWLOC__BITMAP_CHECK(set1);
1047 HWLOC__BITMAP_CHECK(set2);
1048
1049 for(i=0; i<min_count; i++)
1050 if (set1->ulongs[i] & set2->ulongs[i])
1051 return 1;
1052
1053 if (count1 != count2) {
1054 if (set2->infinite) {
1055 for(i=min_count; i<set1->ulongs_count; i++)
1056 if (set1->ulongs[i])
1057 return 1;
1058 }
1059 if (set1->infinite) {
1060 for(i=min_count; i<set2->ulongs_count; i++)
1061 if (set2->ulongs[i])
1062 return 1;
1063 }
1064 }
1065
1066 if (set1->infinite && set2->infinite)
1067 return 1;
1068
1069 return 0;
1070 }
1071
hwloc_bitmap_isincluded(const struct hwloc_bitmap_s * sub_set,const struct hwloc_bitmap_s * super_set)1072 int hwloc_bitmap_isincluded (const struct hwloc_bitmap_s *sub_set, const struct hwloc_bitmap_s *super_set)
1073 {
1074 unsigned super_count = super_set->ulongs_count;
1075 unsigned sub_count = sub_set->ulongs_count;
1076 unsigned min_count = super_count < sub_count ? super_count : sub_count;
1077 unsigned i;
1078
1079 HWLOC__BITMAP_CHECK(sub_set);
1080 HWLOC__BITMAP_CHECK(super_set);
1081
1082 for(i=0; i<min_count; i++)
1083 if (super_set->ulongs[i] != (super_set->ulongs[i] | sub_set->ulongs[i]))
1084 return 0;
1085
1086 if (super_count != sub_count) {
1087 if (!super_set->infinite)
1088 for(i=min_count; i<sub_count; i++)
1089 if (sub_set->ulongs[i])
1090 return 0;
1091 if (sub_set->infinite)
1092 for(i=min_count; i<super_count; i++)
1093 if (super_set->ulongs[i] != HWLOC_SUBBITMAP_FULL)
1094 return 0;
1095 }
1096
1097 if (sub_set->infinite && !super_set->infinite)
1098 return 0;
1099
1100 return 1;
1101 }
1102
hwloc_bitmap_or(struct hwloc_bitmap_s * res,const struct hwloc_bitmap_s * set1,const struct hwloc_bitmap_s * set2)1103 int hwloc_bitmap_or (struct hwloc_bitmap_s *res, const struct hwloc_bitmap_s *set1, const struct hwloc_bitmap_s *set2)
1104 {
1105 /* cache counts so that we can reset res even if it's also set1 or set2 */
1106 unsigned count1 = set1->ulongs_count;
1107 unsigned count2 = set2->ulongs_count;
1108 unsigned max_count = count1 > count2 ? count1 : count2;
1109 unsigned min_count = count1 + count2 - max_count;
1110 unsigned i;
1111
1112 HWLOC__BITMAP_CHECK(res);
1113 HWLOC__BITMAP_CHECK(set1);
1114 HWLOC__BITMAP_CHECK(set2);
1115
1116 if (hwloc_bitmap_reset_by_ulongs(res, max_count) < 0)
1117 return -1;
1118
1119 for(i=0; i<min_count; i++)
1120 res->ulongs[i] = set1->ulongs[i] | set2->ulongs[i];
1121
1122 if (count1 != count2) {
1123 if (min_count < count1) {
1124 if (set2->infinite) {
1125 res->ulongs_count = min_count;
1126 } else {
1127 for(i=min_count; i<max_count; i++)
1128 res->ulongs[i] = set1->ulongs[i];
1129 }
1130 } else {
1131 if (set1->infinite) {
1132 res->ulongs_count = min_count;
1133 } else {
1134 for(i=min_count; i<max_count; i++)
1135 res->ulongs[i] = set2->ulongs[i];
1136 }
1137 }
1138 }
1139
1140 res->infinite = set1->infinite || set2->infinite;
1141 return 0;
1142 }
1143
hwloc_bitmap_and(struct hwloc_bitmap_s * res,const struct hwloc_bitmap_s * set1,const struct hwloc_bitmap_s * set2)1144 int hwloc_bitmap_and (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 for(i=min_count; i<max_count; i++)
1167 res->ulongs[i] = set1->ulongs[i];
1168 } else {
1169 res->ulongs_count = min_count;
1170 }
1171 } else {
1172 if (set1->infinite) {
1173 for(i=min_count; i<max_count; i++)
1174 res->ulongs[i] = set2->ulongs[i];
1175 } else {
1176 res->ulongs_count = min_count;
1177 }
1178 }
1179 }
1180
1181 res->infinite = set1->infinite && set2->infinite;
1182 return 0;
1183 }
1184
hwloc_bitmap_andnot(struct hwloc_bitmap_s * res,const struct hwloc_bitmap_s * set1,const struct hwloc_bitmap_s * set2)1185 int hwloc_bitmap_andnot (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_xor(struct hwloc_bitmap_s * res,const struct hwloc_bitmap_s * set1,const struct hwloc_bitmap_s * set2)1226 int hwloc_bitmap_xor (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 unsigned long w2 = set2->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
1248 for(i=min_count; i<max_count; i++)
1249 res->ulongs[i] = set1->ulongs[i] ^ w2;
1250 } else {
1251 unsigned long w1 = set1->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
1252 for(i=min_count; i<max_count; i++)
1253 res->ulongs[i] = set2->ulongs[i] ^ w1;
1254 }
1255 }
1256
1257 res->infinite = (!set1->infinite) != (!set2->infinite);
1258 return 0;
1259 }
1260
hwloc_bitmap_not(struct hwloc_bitmap_s * res,const struct hwloc_bitmap_s * set)1261 int hwloc_bitmap_not (struct hwloc_bitmap_s *res, const struct hwloc_bitmap_s *set)
1262 {
1263 unsigned count = set->ulongs_count;
1264 unsigned i;
1265
1266 HWLOC__BITMAP_CHECK(res);
1267 HWLOC__BITMAP_CHECK(set);
1268
1269 if (hwloc_bitmap_reset_by_ulongs(res, count) < 0)
1270 return -1;
1271
1272 for(i=0; i<count; i++)
1273 res->ulongs[i] = ~set->ulongs[i];
1274
1275 res->infinite = !set->infinite;
1276 return 0;
1277 }
1278
hwloc_bitmap_first(const struct hwloc_bitmap_s * set)1279 int hwloc_bitmap_first(const struct hwloc_bitmap_s * set)
1280 {
1281 unsigned i;
1282
1283 HWLOC__BITMAP_CHECK(set);
1284
1285 for(i=0; i<set->ulongs_count; i++) {
1286 /* subsets are unsigned longs, use ffsl */
1287 unsigned long w = set->ulongs[i];
1288 if (w)
1289 return hwloc_ffsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
1290 }
1291
1292 if (set->infinite)
1293 return set->ulongs_count * HWLOC_BITS_PER_LONG;
1294
1295 return -1;
1296 }
1297
hwloc_bitmap_first_unset(const struct hwloc_bitmap_s * set)1298 int hwloc_bitmap_first_unset(const struct hwloc_bitmap_s * set)
1299 {
1300 unsigned i;
1301
1302 HWLOC__BITMAP_CHECK(set);
1303
1304 for(i=0; i<set->ulongs_count; i++) {
1305 /* subsets are unsigned longs, use ffsl */
1306 unsigned long w = ~set->ulongs[i];
1307 if (w)
1308 return hwloc_ffsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
1309 }
1310
1311 if (!set->infinite)
1312 return set->ulongs_count * HWLOC_BITS_PER_LONG;
1313
1314 return -1;
1315 }
1316
hwloc_bitmap_last(const struct hwloc_bitmap_s * set)1317 int hwloc_bitmap_last(const struct hwloc_bitmap_s * set)
1318 {
1319 int i;
1320
1321 HWLOC__BITMAP_CHECK(set);
1322
1323 if (set->infinite)
1324 return -1;
1325
1326 for(i=(int)set->ulongs_count-1; i>=0; i--) {
1327 /* subsets are unsigned longs, use flsl */
1328 unsigned long w = set->ulongs[i];
1329 if (w)
1330 return hwloc_flsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
1331 }
1332
1333 return -1;
1334 }
1335
hwloc_bitmap_last_unset(const struct hwloc_bitmap_s * set)1336 int hwloc_bitmap_last_unset(const struct hwloc_bitmap_s * set)
1337 {
1338 int i;
1339
1340 HWLOC__BITMAP_CHECK(set);
1341
1342 if (!set->infinite)
1343 return -1;
1344
1345 for(i=(int)set->ulongs_count-1; i>=0; i--) {
1346 /* subsets are unsigned longs, use flsl */
1347 unsigned long w = ~set->ulongs[i];
1348 if (w)
1349 return hwloc_flsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
1350 }
1351
1352 return -1;
1353 }
1354
hwloc_bitmap_next(const struct hwloc_bitmap_s * set,int prev_cpu)1355 int hwloc_bitmap_next(const struct hwloc_bitmap_s * set, int prev_cpu)
1356 {
1357 unsigned i = HWLOC_SUBBITMAP_INDEX(prev_cpu + 1);
1358
1359 HWLOC__BITMAP_CHECK(set);
1360
1361 if (i >= set->ulongs_count) {
1362 if (set->infinite)
1363 return prev_cpu + 1;
1364 else
1365 return -1;
1366 }
1367
1368 for(; i<set->ulongs_count; i++) {
1369 /* subsets are unsigned longs, use ffsl */
1370 unsigned long w = set->ulongs[i];
1371
1372 /* if the prev cpu is in the same word as the possible next one,
1373 we need to mask out previous cpus */
1374 if (prev_cpu >= 0 && HWLOC_SUBBITMAP_INDEX((unsigned) prev_cpu) == i)
1375 w &= ~HWLOC_SUBBITMAP_ULBIT_TO(HWLOC_SUBBITMAP_CPU_ULBIT(prev_cpu));
1376
1377 if (w)
1378 return hwloc_ffsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
1379 }
1380
1381 if (set->infinite)
1382 return set->ulongs_count * HWLOC_BITS_PER_LONG;
1383
1384 return -1;
1385 }
1386
hwloc_bitmap_next_unset(const struct hwloc_bitmap_s * set,int prev_cpu)1387 int hwloc_bitmap_next_unset(const struct hwloc_bitmap_s * set, int prev_cpu)
1388 {
1389 unsigned i = HWLOC_SUBBITMAP_INDEX(prev_cpu + 1);
1390
1391 HWLOC__BITMAP_CHECK(set);
1392
1393 if (i >= set->ulongs_count) {
1394 if (!set->infinite)
1395 return prev_cpu + 1;
1396 else
1397 return -1;
1398 }
1399
1400 for(; i<set->ulongs_count; i++) {
1401 /* subsets are unsigned longs, use ffsl */
1402 unsigned long w = ~set->ulongs[i];
1403
1404 /* if the prev cpu is in the same word as the possible next one,
1405 we need to mask out previous cpus */
1406 if (prev_cpu >= 0 && HWLOC_SUBBITMAP_INDEX((unsigned) prev_cpu) == i)
1407 w &= ~HWLOC_SUBBITMAP_ULBIT_TO(HWLOC_SUBBITMAP_CPU_ULBIT(prev_cpu));
1408
1409 if (w)
1410 return hwloc_ffsl(w) - 1 + HWLOC_BITS_PER_LONG*i;
1411 }
1412
1413 if (!set->infinite)
1414 return set->ulongs_count * HWLOC_BITS_PER_LONG;
1415
1416 return -1;
1417 }
1418
hwloc_bitmap_singlify(struct hwloc_bitmap_s * set)1419 int hwloc_bitmap_singlify(struct hwloc_bitmap_s * set)
1420 {
1421 unsigned i;
1422 int found = 0;
1423
1424 HWLOC__BITMAP_CHECK(set);
1425
1426 for(i=0; i<set->ulongs_count; i++) {
1427 if (found) {
1428 set->ulongs[i] = HWLOC_SUBBITMAP_ZERO;
1429 continue;
1430 } else {
1431 /* subsets are unsigned longs, use ffsl */
1432 unsigned long w = set->ulongs[i];
1433 if (w) {
1434 int _ffs = hwloc_ffsl(w);
1435 set->ulongs[i] = HWLOC_SUBBITMAP_CPU(_ffs-1);
1436 found = 1;
1437 }
1438 }
1439 }
1440
1441 if (set->infinite) {
1442 if (found) {
1443 set->infinite = 0;
1444 } else {
1445 /* set the first non allocated bit */
1446 unsigned first = set->ulongs_count * HWLOC_BITS_PER_LONG;
1447 set->infinite = 0; /* do not let realloc fill the newly allocated sets */
1448 return hwloc_bitmap_set(set, first);
1449 }
1450 }
1451
1452 return 0;
1453 }
1454
hwloc_bitmap_compare_first(const struct hwloc_bitmap_s * set1,const struct hwloc_bitmap_s * set2)1455 int hwloc_bitmap_compare_first(const struct hwloc_bitmap_s * set1, const struct hwloc_bitmap_s * set2)
1456 {
1457 unsigned count1 = set1->ulongs_count;
1458 unsigned count2 = set2->ulongs_count;
1459 unsigned max_count = count1 > count2 ? count1 : count2;
1460 unsigned min_count = count1 + count2 - max_count;
1461 unsigned i;
1462
1463 HWLOC__BITMAP_CHECK(set1);
1464 HWLOC__BITMAP_CHECK(set2);
1465
1466 for(i=0; i<min_count; i++) {
1467 unsigned long w1 = set1->ulongs[i];
1468 unsigned long w2 = set2->ulongs[i];
1469 if (w1 || w2) {
1470 int _ffs1 = hwloc_ffsl(w1);
1471 int _ffs2 = hwloc_ffsl(w2);
1472 /* if both have a bit set, compare for real */
1473 if (_ffs1 && _ffs2)
1474 return _ffs1-_ffs2;
1475 /* one is empty, and it is considered higher, so reverse-compare them */
1476 return _ffs2-_ffs1;
1477 }
1478 }
1479
1480 if (count1 != count2) {
1481 if (min_count < count2) {
1482 for(i=min_count; i<count2; i++) {
1483 unsigned long w2 = set2->ulongs[i];
1484 if (set1->infinite)
1485 return -!(w2 & 1);
1486 else if (w2)
1487 return 1;
1488 }
1489 } else {
1490 for(i=min_count; i<count1; i++) {
1491 unsigned long w1 = set1->ulongs[i];
1492 if (set2->infinite)
1493 return !(w1 & 1);
1494 else if (w1)
1495 return -1;
1496 }
1497 }
1498 }
1499
1500 return !!set1->infinite - !!set2->infinite;
1501 }
1502
hwloc_bitmap_compare(const struct hwloc_bitmap_s * set1,const struct hwloc_bitmap_s * set2)1503 int hwloc_bitmap_compare(const struct hwloc_bitmap_s * set1, const struct hwloc_bitmap_s * set2)
1504 {
1505 unsigned count1 = set1->ulongs_count;
1506 unsigned count2 = set2->ulongs_count;
1507 unsigned max_count = count1 > count2 ? count1 : count2;
1508 unsigned min_count = count1 + count2 - max_count;
1509 int i;
1510
1511 HWLOC__BITMAP_CHECK(set1);
1512 HWLOC__BITMAP_CHECK(set2);
1513
1514 if ((!set1->infinite) != (!set2->infinite))
1515 return !!set1->infinite - !!set2->infinite;
1516
1517 if (count1 != count2) {
1518 if (min_count < count2) {
1519 unsigned long val1 = set1->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
1520 for(i=(int)max_count-1; i>=(int) min_count; i--) {
1521 unsigned long val2 = set2->ulongs[i];
1522 if (val1 == val2)
1523 continue;
1524 return val1 < val2 ? -1 : 1;
1525 }
1526 } else {
1527 unsigned long val2 = set2->infinite ? HWLOC_SUBBITMAP_FULL : HWLOC_SUBBITMAP_ZERO;
1528 for(i=(int)max_count-1; i>=(int) min_count; i--) {
1529 unsigned long val1 = set1->ulongs[i];
1530 if (val1 == val2)
1531 continue;
1532 return val1 < val2 ? -1 : 1;
1533 }
1534 }
1535 }
1536
1537 for(i=(int)min_count-1; i>=0; i--) {
1538 unsigned long val1 = set1->ulongs[i];
1539 unsigned long val2 = set2->ulongs[i];
1540 if (val1 == val2)
1541 continue;
1542 return val1 < val2 ? -1 : 1;
1543 }
1544
1545 return 0;
1546 }
1547
hwloc_bitmap_weight(const struct hwloc_bitmap_s * set)1548 int hwloc_bitmap_weight(const struct hwloc_bitmap_s * set)
1549 {
1550 int weight = 0;
1551 unsigned i;
1552
1553 HWLOC__BITMAP_CHECK(set);
1554
1555 if (set->infinite)
1556 return -1;
1557
1558 for(i=0; i<set->ulongs_count; i++)
1559 weight += hwloc_weight_long(set->ulongs[i]);
1560 return weight;
1561 }
1562
hwloc_bitmap_compare_inclusion(const struct hwloc_bitmap_s * set1,const struct hwloc_bitmap_s * set2)1563 int hwloc_bitmap_compare_inclusion(const struct hwloc_bitmap_s * set1, const struct hwloc_bitmap_s * set2)
1564 {
1565 unsigned max_count = set1->ulongs_count > set2->ulongs_count ? set1->ulongs_count : set2->ulongs_count;
1566 int result = HWLOC_BITMAP_EQUAL; /* means empty sets return equal */
1567 int empty1 = 1;
1568 int empty2 = 1;
1569 unsigned i;
1570
1571 HWLOC__BITMAP_CHECK(set1);
1572 HWLOC__BITMAP_CHECK(set2);
1573
1574 for(i=0; i<max_count; i++) {
1575 unsigned long val1 = HWLOC_SUBBITMAP_READULONG(set1, (unsigned) i);
1576 unsigned long val2 = HWLOC_SUBBITMAP_READULONG(set2, (unsigned) i);
1577
1578 if (!val1) {
1579 if (!val2)
1580 /* both empty, no change */
1581 continue;
1582
1583 /* val1 empty, val2 not */
1584 if (result == HWLOC_BITMAP_CONTAINS) {
1585 if (!empty2)
1586 return HWLOC_BITMAP_INTERSECTS;
1587 result = HWLOC_BITMAP_DIFFERENT;
1588 } else if (result == HWLOC_BITMAP_EQUAL) {
1589 result = HWLOC_BITMAP_INCLUDED;
1590 }
1591 /* no change otherwise */
1592
1593 } else if (!val2) {
1594 /* val2 empty, val1 not */
1595 if (result == HWLOC_BITMAP_INCLUDED) {
1596 if (!empty1)
1597 return HWLOC_BITMAP_INTERSECTS;
1598 result = HWLOC_BITMAP_DIFFERENT;
1599 } else if (result == HWLOC_BITMAP_EQUAL) {
1600 result = HWLOC_BITMAP_CONTAINS;
1601 }
1602 /* no change otherwise */
1603
1604 } else if (val1 == val2) {
1605 /* equal and not empty */
1606 if (result == HWLOC_BITMAP_DIFFERENT)
1607 return HWLOC_BITMAP_INTERSECTS;
1608 /* equal/contains/included unchanged */
1609
1610 } else if ((val1 & val2) == val1) {
1611 /* included and not empty */
1612 if (result == HWLOC_BITMAP_CONTAINS || result == HWLOC_BITMAP_DIFFERENT)
1613 return HWLOC_BITMAP_INTERSECTS;
1614 /* equal/included unchanged */
1615 result = HWLOC_BITMAP_INCLUDED;
1616
1617 } else if ((val1 & val2) == val2) {
1618 /* contains and not empty */
1619 if (result == HWLOC_BITMAP_INCLUDED || result == HWLOC_BITMAP_DIFFERENT)
1620 return HWLOC_BITMAP_INTERSECTS;
1621 /* equal/contains unchanged */
1622 result = HWLOC_BITMAP_CONTAINS;
1623
1624 } else if ((val1 & val2) != 0) {
1625 /* intersects and not empty */
1626 return HWLOC_BITMAP_INTERSECTS;
1627
1628 } else {
1629 /* different and not empty */
1630
1631 /* equal/included/contains with non-empty sets means intersects */
1632 if (result == HWLOC_BITMAP_EQUAL && !empty1 /* implies !empty2 */)
1633 return HWLOC_BITMAP_INTERSECTS;
1634 if (result == HWLOC_BITMAP_INCLUDED && !empty1)
1635 return HWLOC_BITMAP_INTERSECTS;
1636 if (result == HWLOC_BITMAP_CONTAINS && !empty2)
1637 return HWLOC_BITMAP_INTERSECTS;
1638 /* otherwise means different */
1639 result = HWLOC_BITMAP_DIFFERENT;
1640 }
1641
1642 empty1 &= !val1;
1643 empty2 &= !val2;
1644 }
1645
1646 if (!set1->infinite) {
1647 if (set2->infinite) {
1648 /* set2 infinite only */
1649 if (result == HWLOC_BITMAP_CONTAINS) {
1650 if (!empty2)
1651 return HWLOC_BITMAP_INTERSECTS;
1652 result = HWLOC_BITMAP_DIFFERENT;
1653 } else if (result == HWLOC_BITMAP_EQUAL) {
1654 result = HWLOC_BITMAP_INCLUDED;
1655 }
1656 /* no change otherwise */
1657 }
1658 } else if (!set2->infinite) {
1659 /* set1 infinite only */
1660 if (result == HWLOC_BITMAP_INCLUDED) {
1661 if (!empty1)
1662 return HWLOC_BITMAP_INTERSECTS;
1663 result = HWLOC_BITMAP_DIFFERENT;
1664 } else if (result == HWLOC_BITMAP_EQUAL) {
1665 result = HWLOC_BITMAP_CONTAINS;
1666 }
1667 /* no change otherwise */
1668 } else {
1669 /* both infinite */
1670 if (result == HWLOC_BITMAP_DIFFERENT)
1671 return HWLOC_BITMAP_INTERSECTS;
1672 /* equal/contains/included unchanged */
1673 }
1674
1675 return result;
1676 }
1677