dutil.h

   1 #ifndef _DUTIL_H_
   2 #define _DUTIL_H_ 1
   3 /*
   4   SPDX-License-Identifier: GPL-2.0-only
   5
   6  * Copyright (C) 2007..2009 Arnaldo Carvalho de Melo <acme@redhat.com>
   7  *
   8  * Some functions came from the Linux Kernel sources, copyrighted by a
   9  * cast of dozens, please see the Linux Kernel git history for details.
  10  */
  11
  12 #include <stdbool.h>
  13 #include <linux/stddef.h>
  14 #include <stddef.h>
  15 #include <string.h>
  16 #include <elf.h>
  17 #include <gelf.h>
  18 #include <asm/bitsperlong.h>
  19 #include "rbtree.h"
  20 #include "list.h"
  21
  22 #define BITS_PER_LONG __BITS_PER_LONG
  23
  24 #ifndef __maybe_unused
  25 #define __maybe_unused __attribute__((__unused__))
  26 #endif
  27
  28 #ifndef __pure
  29 #define __pure __attribute__ ((pure))
  30 #endif
  31
  32 #define roundup(x,y) ((((x) + ((y) - 1)) / (y)) * (y))
  33
  34 #ifndef DW_TAG_LLVM_annotation
  35 #define DW_TAG_LLVM_annotation 0x6000
  36 #endif
  37
  38 static inline __attribute__((const)) bool is_power_of_2(unsigned long n)
  39 {
  40         return (n != 0 && ((n & (n - 1)) == 0));
  41 }
  42
  43 /**
  44  * fls - find last (most-significant) bit set
  45  * @x: the word to search
  46  *
  47  * This is defined the same way as ffs.
  48  * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
  49  */
  50 static __always_inline int fls(int x)
  51 {
  52         return x ? sizeof(x) * 8 - __builtin_clz(x) : 0;
  53 }
  54
  55 /**
  56  * fls64 - find last set bit in a 64-bit word
  57  * @x: the word to search
  58  *
  59  * This is defined in a similar way as the libc and compiler builtin
  60  * ffsll, but returns the position of the most significant set bit.
  61  *
  62  * fls64(value) returns 0 if value is 0 or the position of the last
  63  * set bit if value is nonzero. The last (most significant) bit is
  64  * at position 64.
  65  */
  66 #if BITS_PER_LONG == 32
  67 static __always_inline int fls64(uint64_t x)
  68 {
  69         uint32_t h = x >> 32;
  70         if (h)
  71                 return fls(h) + 32;
  72         return fls(x);
  73 }
  74 #elif BITS_PER_LONG == 64
  75 /**
  76  * __fls - find last (most-significant) set bit in a long word
  77  * @word: the word to search
  78  *
  79  * Undefined if no set bit exists, so code should check against 0 first.
  80  */
  81 static __always_inline unsigned long __fls(unsigned long word)
  82 {
  83         int num = BITS_PER_LONG - 1;
  84
  85 #if BITS_PER_LONG == 64
  86         if (!(word & (~0ul << 32))) {
  87                 num -= 32;
  88                 word <<= 32;
  89         }
  90 #endif
  91         if (!(word & (~0ul << (BITS_PER_LONG-16)))) {
  92                 num -= 16;
  93                 word <<= 16;
  94         }
  95         if (!(word & (~0ul << (BITS_PER_LONG-8)))) {
  96                 num -= 8;
  97                 word <<= 8;
  98         }
  99         if (!(word & (~0ul << (BITS_PER_LONG-4)))) {
 100                 num -= 4;
 101                 word <<= 4;
 102         }
 103         if (!(word & (~0ul << (BITS_PER_LONG-2)))) {
 104                 num -= 2;
 105                 word <<= 2;
 106         }
 107         if (!(word & (~0ul << (BITS_PER_LONG-1))))
 108                 num -= 1;
 109         return num;
 110 }
 111
 112 static __always_inline int fls64(uint64_t x)
 113 {
 114         if (x == 0)
 115                 return 0;
 116         return __fls(x) + 1;
 117 }
 118 #else
 119 #error BITS_PER_LONG not 32 or 64
 120 #endif
 121
 122 static inline unsigned fls_long(unsigned long l)
 123 {
 124         if (sizeof(l) == 4)
 125                 return fls(l);
 126         return fls64(l);
 127 }
 128
 129 /*
 130  * round up to nearest power of two
 131  */
 132 static inline __attribute__((const))
 133 unsigned long __roundup_pow_of_two(unsigned long n)
 134 {
 135         return 1UL << fls_long(n - 1);
 136 }
 137
 138 /*
 139  * non-constant log of base 2 calculators
 140  * - the arch may override these in asm/bitops.h if they can be implemented
 141  *   more efficiently than using fls() and fls64()
 142  * - the arch is not required to handle n==0 if implementing the fallback
 143  */
 144 static inline __attribute__((const))
 145 int __ilog2_u32(uint32_t n)
 146 {
 147         return fls(n) - 1;
 148 }
 149
 150 static inline __attribute__((const))
 151 int __ilog2_u64(uint64_t n)
 152 {
 153         return fls64(n) - 1;
 154 }
 155
 156 /*
 157  * deal with unrepresentable constant logarithms
 158  */
 159 extern __attribute__((const))
 160 int ____ilog2_NaN(void);
 161
 162 /**
 163  * ilog2 - log of base 2 of 32-bit or a 64-bit unsigned value
 164  * @n - parameter
 165  *
 166  * constant-capable log of base 2 calculation
 167  * - this can be used to initialise global variables from constant data, hence
 168  *   the massive ternary operator construction
 169  *
 170  * selects the appropriately-sized optimised version depending on sizeof(n)
 171  */
 172 #define ilog2(n)                                \
 173 (                                               \
 174         __builtin_constant_p(n) ? (             \
 175                 (n) < 1 ? ____ilog2_NaN() :     \
 176                 (n) & (1ULL << 63) ? 63 :       \
 177                 (n) & (1ULL << 62) ? 62 :       \
 178                 (n) & (1ULL << 61) ? 61 :       \
 179                 (n) & (1ULL << 60) ? 60 :       \
 180                 (n) & (1ULL << 59) ? 59 :       \
 181                 (n) & (1ULL << 58) ? 58 :       \
 182                 (n) & (1ULL << 57) ? 57 :       \
 183                 (n) & (1ULL << 56) ? 56 :       \
 184                 (n) & (1ULL << 55) ? 55 :       \
 185                 (n) & (1ULL << 54) ? 54 :       \
 186                 (n) & (1ULL << 53) ? 53 :       \
 187                 (n) & (1ULL << 52) ? 52 :       \
 188                 (n) & (1ULL << 51) ? 51 :       \
 189                 (n) & (1ULL << 50) ? 50 :       \
 190                 (n) & (1ULL << 49) ? 49 :       \
 191                 (n) & (1ULL << 48) ? 48 :       \
 192                 (n) & (1ULL << 47) ? 47 :       \
 193                 (n) & (1ULL << 46) ? 46 :       \
 194                 (n) & (1ULL << 45) ? 45 :       \
 195                 (n) & (1ULL << 44) ? 44 :       \
 196                 (n) & (1ULL << 43) ? 43 :       \
 197                 (n) & (1ULL << 42) ? 42 :       \
 198                 (n) & (1ULL << 41) ? 41 :       \
 199                 (n) & (1ULL << 40) ? 40 :       \
 200                 (n) & (1ULL << 39) ? 39 :       \
 201                 (n) & (1ULL << 38) ? 38 :       \
 202                 (n) & (1ULL << 37) ? 37 :       \
 203                 (n) & (1ULL << 36) ? 36 :       \
 204                 (n) & (1ULL << 35) ? 35 :       \
 205                 (n) & (1ULL << 34) ? 34 :       \
 206                 (n) & (1ULL << 33) ? 33 :       \
 207                 (n) & (1ULL << 32) ? 32 :       \
 208                 (n) & (1ULL << 31) ? 31 :       \
 209                 (n) & (1ULL << 30) ? 30 :       \
 210                 (n) & (1ULL << 29) ? 29 :       \
 211                 (n) & (1ULL << 28) ? 28 :       \
 212                 (n) & (1ULL << 27) ? 27 :       \
 213                 (n) & (1ULL << 26) ? 26 :       \
 214                 (n) & (1ULL << 25) ? 25 :       \
 215                 (n) & (1ULL << 24) ? 24 :       \
 216                 (n) & (1ULL << 23) ? 23 :       \
 217                 (n) & (1ULL << 22) ? 22 :       \
 218                 (n) & (1ULL << 21) ? 21 :       \
 219                 (n) & (1ULL << 20) ? 20 :       \
 220                 (n) & (1ULL << 19) ? 19 :       \
 221                 (n) & (1ULL << 18) ? 18 :       \
 222                 (n) & (1ULL << 17) ? 17 :       \
 223                 (n) & (1ULL << 16) ? 16 :       \
 224                 (n) & (1ULL << 15) ? 15 :       \
 225                 (n) & (1ULL << 14) ? 14 :       \
 226                 (n) & (1ULL << 13) ? 13 :       \
 227                 (n) & (1ULL << 12) ? 12 :       \
 228                 (n) & (1ULL << 11) ? 11 :       \
 229                 (n) & (1ULL << 10) ? 10 :       \
 230                 (n) & (1ULL <<  9) ?  9 :       \
 231                 (n) & (1ULL <<  8) ?  8 :       \
 232                 (n) & (1ULL <<  7) ?  7 :       \
 233                 (n) & (1ULL <<  6) ?  6 :       \
 234                 (n) & (1ULL <<  5) ?  5 :       \
 235                 (n) & (1ULL <<  4) ?  4 :       \
 236                 (n) & (1ULL <<  3) ?  3 :       \
 237                 (n) & (1ULL <<  2) ?  2 :       \
 238                 (n) & (1ULL <<  1) ?  1 :       \
 239                 (n) & (1ULL <<  0) ?  0 :       \
 240                 ____ilog2_NaN()                 \
 241                                    ) :          \
 242         (sizeof(n) <= 4) ?                      \
 243         __ilog2_u32(n) :                        \
 244         __ilog2_u64(n)                          \
 245  )
 246
 247 /**
 248  * roundup_pow_of_two - round the given value up to nearest power of two
 249  * @n - parameter
 250  *
 251  * round the given value up to the nearest power of two
 252  * - the result is undefined when n == 0
 253  * - this can be used to initialise global variables from constant data
 254  */
 255 #define roundup_pow_of_two(n)                   \
 256 (                                               \
 257         __builtin_constant_p(n) ? (             \
 258                 (n == 1) ? 1 :                  \
 259                 (1UL << (ilog2((n) - 1) + 1))   \
 260                                    ) :          \
 261         __roundup_pow_of_two(n)                 \
 262  )
 263
 264 /* We need define two variables, argp_program_version_hook and
 265    argp_program_bug_address, in all programs.  argp.h declares these
 266    variables as non-const (which is correct in general).  But we can
 267    do better, it is not going to change.  So we want to move them into
 268    the .rodata section.  Define macros to do the trick.  */
 269 #define ARGP_PROGRAM_VERSION_HOOK_DEF \
 270         void (*const apvh) (FILE *, struct argp_state *) \
 271         __asm ("argp_program_version_hook")
 272 #define ARGP_PROGRAM_BUG_ADDRESS_DEF \
 273         const char *const apba__ __asm ("argp_program_bug_address")
 274
 275 // Use a list_head so that we keep the original order when iterating in
 276 // the strlist.
 277
 278 struct str_node {
 279         struct rb_node rb_node;
 280         struct list_head node;
 281         const char       *s;
 282         void             *priv;
 283 };
 284
 285 // list_entries to keep the original order as passed, say, in the command line
 286
 287 struct strlist {
 288         struct rb_root entries;
 289         struct list_head list_entries;
 290         bool dupstr;
 291 };
 292
 293 struct strlist *strlist__new(bool dupstr);
 294 void strlist__delete(struct strlist *slist);
 295
 296 void strlist__remove(struct strlist *slist, struct str_node *sn);
 297 int strlist__load(struct strlist *slist, const char *filename);
 298 int strlist__add(struct strlist *slist, const char *str);
 299 int __strlist__add(struct strlist *slist, const char *str, void *priv);
 300
 301 bool strlist__has_entry(struct strlist *slist, const char *entry);
 302
 303 static inline bool strlist__empty(const struct strlist *slist)
 304 {
 305         return rb_first(&slist->entries) == NULL;
 306 }
 307
 308 /**
 309  * strlist__for_each_entry_safe - iterate thru all the strings safe against removal of list entry
 310  * @slist: struct strlist instance to iterate
 311  * @pos: struct str_node iterator
 312  * @n: tmp struct str_node
 313  */
 314 #define strlist__for_each_entry_safe(slist, pos, n) \
 315         list_for_each_entry_safe(pos, n, &(slist)->list_entries, node)
 316
 317 /**
 318  * strstarts - does @str start with @prefix?
 319  * @str: string to examine
 320  * @prefix: prefix to look for.
 321  */
 322 static inline bool strstarts(const char *str, const char *prefix)
 323 {
 324         return strncmp(str, prefix, strlen(prefix)) == 0;
 325 }
 326
 327 void *zalloc(const size_t size);
 328
 329 Elf_Scn *elf_section_by_name(Elf *elf, GElf_Shdr *shp, const char *name, size_t *index);
 330
 331 Elf_Scn *elf_section_by_idx(Elf *elf, GElf_Shdr *shp, int idx);
 332
 333 #ifndef SHT_GNU_ATTRIBUTES
 334 /* Just a way to check if we're using an old elfutils version */
 335 static inline int elf_getshdrstrndx(Elf *elf, size_t *dst)
 336 {
 337         return elf_getshstrndx(elf, dst);
 338 }
 339 #endif
 340
 341 char *strlwr(char *s);
 342
 343 void __zfree(void **ptr);
 344
 345 #define zfree(ptr) __zfree((void **)(ptr))
 346
 347 #ifndef BTF_KIND_ENUM64
 348 #define BTF_KIND_ENUM64 19
 349 #endif
 350
 351 #endif /* _DUTIL_H_ */