lib/xref.h

   1 /*
   2  * Copyright (c) 2017-20  David Lamparter, for NetDEF, Inc.
   3  *
   4  * Permission to use, copy, modify, and distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15  */
  16
  17 #ifndef _FRR_XREF_H
  18 #define _FRR_XREF_H
  19
  20 #include <stdint.h>
  21 #include <stdlib.h>
  22 #include <limits.h>
  23 #include <errno.h>
  24 #include "compiler.h"
  25 #include "typesafe.h"
  26
  27 #ifdef __cplusplus
  28 extern "C" {
  29 #endif
  30
  31 enum xref_type {
  32         XREFT_NONE = 0,
  33
  34         XREFT_THREADSCHED = 0x100,
  35
  36         XREFT_LOGMSG = 0x200,
  37         XREFT_ASSERT = 0x280,
  38
  39         XREFT_DEFUN = 0x300,
  40         XREFT_INSTALL_ELEMENT = 0x301,
  41 };
  42
  43 /* struct xref is the "const" part;  struct xrefdata is the writable part. */
  44 struct xref;
  45 struct xrefdata;
  46
  47 struct xref {
  48         /* this may be NULL, depending on the type of the xref.
  49          * if it is NULL, the xref has no unique ID and cannot be accessed
  50          * through that mechanism.
  51          */
  52         struct xrefdata *xrefdata;
  53
  54         /* type isn't generally needed at runtime */
  55         enum xref_type type;
  56
  57         /* code location */
  58         int line;
  59         const char *file;
  60         const char *func;
  61
  62         /* -- 32 bytes (on 64bit) -- */
  63
  64         /* type-specific bits appended by embedding this struct */
  65 };
  66
  67 PREDECL_RBTREE_UNIQ(xrefdata_uid);
  68
  69 struct xrefdata {
  70         /* pointer back to the const part;  this will be initialized at
  71          * program startup by xref_block_add().  (Creating structs with
  72          * cyclic pointers to each other is not easily possible for
  73          * function-scoped static variables.)
  74          *
  75          * There is no xrefdata w/o xref, but there are xref w/o xrefdata.
  76          */
  77         const struct xref *xref;
  78
  79         /* base32(crockford) of unique ID.  not all bytes are used, but
  80          * let's pad to 16 for simplicity
  81          */
  82         char uid[16];
  83
  84         /* hash/uid input
  85          * if hashstr is NULL, no UID is assigned/calculated.  Use macro
  86          * string concatenation if multiple values need to be fed in.
  87          * (This is here to not make the UID calculation independent of
  88          * xref type.)
  89          */
  90         const char *hashstr;
  91         uint32_t hashu32[2];
  92
  93         /* -- 32 bytes (on 64bit) -- */
  94         struct xrefdata_uid_item xui;
  95 };
  96
  97 static inline int xrefdata_uid_cmp(const struct xrefdata *a,
  98                                    const struct xrefdata *b)
  99 {
 100         return strcmp(a->uid, b->uid);
 101 }
 102
 103 DECLARE_RBTREE_UNIQ(xrefdata_uid, struct xrefdata, xui, xrefdata_uid_cmp);
 104 extern struct xrefdata_uid_head xrefdata_uid;
 105
 106 /* linker "magic" is used to create an array of pointers to struct xref.
 107  * the result is a contiguous block of pointers, each pointing to an xref
 108  * somewhere in the code.  The linker gives us start and end pointers, we
 109  * stuff those into the struct below and hook up a constructor to run at
 110  * program startup with the struct passed.
 111  *
 112  * Placing the xrefs themselves into an array doesn't work because they'd
 113  * need to be constant size, but we're embedding struct xref into other
 114  * container structs with extra data.  Also this means that external code
 115  * (like the python xref dumper) can safely ignore extra data at the end of
 116  * xrefs without needing to account for size in iterating the array.
 117  *
 118  * If you're curious, this is also how __attribute__((constructor)) (and
 119  * destructor) are implemented - there are 2 arrays, ".init_array" and
 120  * ".fini_array", containing function pointers.  The magic turns out to be
 121  * quite mundane, actually ;)
 122  *
 123  * The slightly tricky bit is that this is a per-object (i.e. per shared
 124  * library & daemon) thing and we need a bit of help (in XREF_SETUP) to
 125  * initialize correctly.
 126  */
 127
 128 struct xref_block {
 129         struct xref_block *next;
 130         const struct xref * const *start;
 131         const struct xref * const *stop;
 132 };
 133
 134 extern struct xref_block *xref_blocks;
 135 extern void xref_block_add(struct xref_block *block);
 136 extern void xref_gcc_workaround(const struct xref *xref);
 137
 138 #ifndef HAVE_SECTION_SYMS
 139 /* we have a build system patch to use GNU ld on Solaris;  if that doesn't
 140  * work we end up on Solaris ld which doesn't support the section start/end
 141  * symbols.
 142  */
 143 #define XREF_SETUP() \
 144         CPP_NOTICE("Missing linker support for section arrays.  Solaris ld?")
 145 #else
 146 /* the actual symbols that the linker provides for us.  Note these are
 147  * _symbols_ referring to the actual section start/end, i.e. they are very
 148  * much NOT _pointers_, rather the symbol *value* is the pointer.  Declaring
 149  * them as size-1 arrays is the "best" / "right" thing.
 150  */
 151 extern const struct xref * const __start_xref_array[1] DSO_LOCAL;
 152 extern const struct xref * const __stop_xref_array[1] DSO_LOCAL;
 153
 154 #if defined(__has_feature)
 155 #if __has_feature(address_sanitizer)
 156 /* no redzone around each of the xref_p please, we're building an array out
 157  * of variables here.  kinda breaks things if there's redzones between each
 158  * array item.
 159  */
 160 #define xref_array_attr used, section("xref_array"), no_sanitize("address")
 161 #endif
 162 #endif
 163 #ifndef xref_array_attr
 164 #define xref_array_attr used, section("xref_array")
 165 #endif
 166
 167 /* this macro is invoked once for each standalone DSO through
 168  *   FRR_MODULE_SETUP  \
 169  *                      }-> FRR_COREMOD_SETUP -> XREF_SETUP
 170  *   FRR_DAEMON_INFO   /
 171  */
 172 #define XREF_SETUP()                                                           \
 173         static const struct xref _dummy_xref = {                               \
 174                         /* .xrefdata = */ NULL,                                \
 175                         /* .type = */ XREFT_NONE,                              \
 176                         /* .line = */ __LINE__,                                \
 177                         /* .file = */ __FILE__,                                \
 178                         /* .func = */ "dummy",                                 \
 179         };                                                                     \
 180         static const struct xref * const _dummy_xref_p                         \
 181                         __attribute__((xref_array_attr)) = &_dummy_xref;       \
 182         static void __attribute__((used, _CONSTRUCTOR(1100)))                  \
 183                         _xref_init(void) {                                     \
 184                 static struct xref_block _xref_block = {                       \
 185                         .next = NULL,                                          \
 186                         .start = __start_xref_array,                           \
 187                         .stop = __stop_xref_array,                             \
 188                 };                                                             \
 189                 xref_block_add(&_xref_block);                                  \
 190         }                                                                      \
 191         asm(XREF_NOTE);                                                        \
 192         MACRO_REQUIRE_SEMICOLON() /* end */
 193
 194 /* the following blurb emits an ELF note indicating start and end of the xref
 195  * array in the binary.  This is technically the "correct" entry point for
 196  * external tools reading xrefs out of an ELF shared library or executable.
 197  *
 198  * right now, the extraction tools use the section header for "xref_array"
 199  * instead; however, section headers are technically not necessarily preserved
 200  * for fully linked libraries or executables.  (In practice they are only
 201  * stripped by obfuscation tools.)
 202  *
 203  * conversely, for reading xrefs out of a single relocatable object file (e.g.
 204  * bar.o), section headers are the right thing to look at since the note is
 205  * only emitted for the final binary once.
 206  *
 207  * FRR itself does not need this note to operate correctly, so if you have
 208  * some build issue with it just add -DFRR_XREF_NO_NOTE to your build flags
 209  * to disable it.
 210  */
 211 #if defined(FRR_XREF_NO_NOTE) || defined(__mips64)
 212 #define XREF_NOTE ""
 213
 214 /* mips64 note:  MIPS64 (regardless of endianness, both mips64 & mips64el)
 215  * does not have a 64-bit PC-relative relocation type.  Unfortunately, a
 216  * 64-bit PC-relative relocation is exactly what the below asm magic emits.
 217  * Therefore, the xref ELF note is permanently disabled on MIPS64.
 218  *
 219  * For some context, refer to https://reviews.llvm.org/D80390
 220  *
 221  * As noted above, xref extraction still works through the section header
 222  * path, so no functionality is lost.
 223  */
 224 #else
 225
 226 #if __SIZEOF_POINTER__ == 4
 227 #define _NOTE_2PTRSIZE  "8"
 228 #define _NOTE_PTR       ".long"
 229 #elif __SIZEOF_POINTER__ == 8
 230 #define _NOTE_2PTRSIZE  "16"
 231 #define _NOTE_PTR       ".quad"
 232 #else
 233 #error unsupported pointer size
 234 #endif
 235
 236 #ifdef __arm__
 237 # define asmspecial "%"
 238 #else
 239 # define asmspecial "@"
 240 #endif
 241
 242 #define XREF_NOTE                                                              \
 243         ""                                                                 "\n"\
 244         "       .type _frr_xref_note," asmspecial "object"                 "\n"\
 245         "       .pushsection .note.FRR,\"a\"," asmspecial "note"           "\n"\
 246         "       .p2align 2"                                                "\n"\
 247         "_frr_xref_note:"                                                  "\n"\
 248         "       .long   9"                                                 "\n"\
 249         "       .long   " _NOTE_2PTRSIZE                                   "\n"\
 250         "       .ascii  \"XREF\""                                          "\n"\
 251         "       .ascii  \"FRRouting\\0\\0\\0\""                            "\n"\
 252         "       " _NOTE_PTR "   __start_xref_array-."                      "\n"\
 253         "       " _NOTE_PTR "   __stop_xref_array-."                       "\n"\
 254         "       .size _frr_xref_note, .-_frr_xref_note"                    "\n"\
 255         "       .popsection"                                               "\n"\
 256         ""                                                                 "\n"\
 257         /* end */
 258 #endif
 259
 260 #endif /* HAVE_SECTION_SYMS */
 261
 262 /* emit the array entry / pointer to xref */
 263 #if defined(__clang__) || !defined(__cplusplus)
 264 #define XREF_LINK(dst)                                                         \
 265         static const struct xref * const NAMECTR(xref_p_)                      \
 266                         __attribute__((xref_array_attr))                       \
 267                 = &(dst)                                                       \
 268         /* end */
 269
 270 #else /* GCC && C++ */
 271 /* workaround for GCC bug 41091 (dated 2009), added in 2021...
 272  *
 273  * this breaks extraction of xrefs with xrelfo.py (because the xref_array
 274  * entry will be missing), but provides full runtime functionality.  To get
 275  * the proper list of xrefs from C++ code, build with clang...
 276  */
 277 struct _xref_p {
 278         const struct xref * const ptr;
 279
 280         _xref_p(const struct xref *_ptr) : ptr(_ptr)
 281         {
 282                 xref_gcc_workaround(_ptr);
 283         }
 284 };
 285
 286 #define XREF_LINK(dst)                                                         \
 287         static const struct _xref_p __attribute__((used))                      \
 288                         NAMECTR(xref_p_)(&(dst))                               \
 289         /* end */
 290 #endif
 291
 292 /* initializer for a "struct xref" */
 293 #define XREF_INIT(type_, xrefdata_, func_)                                     \
 294         {                                                                      \
 295                 /* .xrefdata = */ (xrefdata_),                                 \
 296                 /* .type = */ (type_),                                         \
 297                 /* .line = */ __LINE__,                                        \
 298                 /* .file = */ __FILE__,                                        \
 299                 /* .func = */ func_,                                           \
 300         }                                                                      \
 301         /* end */
 302
 303 /* use with XREF_INIT when outside of a function, i.e. no __func__ */
 304 #define XREF_NO_FUNC    "<global>"
 305
 306 #ifdef __cplusplus
 307 }
 308 #endif
 309
 310 #endif /* _FRR_XREF_H */