[mirror_frr.git] / lib / xref.h

// SPDX-License-Identifier: ISC
/*
 * Copyright (c) 2017-20  David Lamparter, for NetDEF, Inc.
 */

#ifndef _FRR_XREF_H
#define _FRR_XREF_H

#include <stdint.h>
#include <stdlib.h>
#include <limits.h>
#include <errno.h>
#include "compiler.h"
#include "typesafe.h"

#ifdef __cplusplus
extern "C" {
#endif

enum xref_type {
	XREFT_NONE = 0,

	XREFT_THREADSCHED = 0x100,

	XREFT_LOGMSG = 0x200,
	XREFT_ASSERT = 0x280,

	XREFT_DEFUN = 0x300,
	XREFT_INSTALL_ELEMENT = 0x301,
};

/* struct xref is the "const" part;  struct xrefdata is the writable part. */
struct xref;
struct xrefdata;

struct xref {
	/* this may be NULL, depending on the type of the xref.
	 * if it is NULL, the xref has no unique ID and cannot be accessed
	 * through that mechanism.
	 */
	struct xrefdata *xrefdata;

	/* type isn't generally needed at runtime */
	enum xref_type type;

	/* code location */
	int line;
	const char *file;
	const char *func;

	/* -- 32 bytes (on 64bit) -- */

	/* type-specific bits appended by embedding this struct */
};

PREDECL_RBTREE_UNIQ(xrefdata_uid);

struct xrefdata {
	/* pointer back to the const part;  this will be initialized at
	 * program startup by xref_block_add().  (Creating structs with
	 * cyclic pointers to each other is not easily possible for
	 * function-scoped static variables.)
	 *
	 * There is no xrefdata w/o xref, but there are xref w/o xrefdata.
	 */
	const struct xref *xref;

	/* base32(crockford) of unique ID.  not all bytes are used, but
	 * let's pad to 16 for simplicity
	 */
	char uid[16];

	/* hash/uid input
	 * if hashstr is NULL, no UID is assigned/calculated.  Use macro
	 * string concatenation if multiple values need to be fed in.
	 * (This is here to not make the UID calculation independent of
	 * xref type.)
	 */
	const char *hashstr;
	uint32_t hashu32[2];

	/* -- 32 bytes (on 64bit) -- */
	struct xrefdata_uid_item xui;
};

static inline int xrefdata_uid_cmp(const struct xrefdata *a,
				   const struct xrefdata *b)
{
	return strcmp(a->uid, b->uid);
}

DECLARE_RBTREE_UNIQ(xrefdata_uid, struct xrefdata, xui, xrefdata_uid_cmp);
extern struct xrefdata_uid_head xrefdata_uid;

/* linker "magic" is used to create an array of pointers to struct xref.
 * the result is a contiguous block of pointers, each pointing to an xref
 * somewhere in the code.  The linker gives us start and end pointers, we
 * stuff those into the struct below and hook up a constructor to run at
 * program startup with the struct passed.
 *
 * Placing the xrefs themselves into an array doesn't work because they'd
 * need to be constant size, but we're embedding struct xref into other
 * container structs with extra data.  Also this means that external code
 * (like the python xref dumper) can safely ignore extra data at the end of
 * xrefs without needing to account for size in iterating the array.
 *
 * If you're curious, this is also how __attribute__((constructor)) (and
 * destructor) are implemented - there are 2 arrays, ".init_array" and
 * ".fini_array", containing function pointers.  The magic turns out to be
 * quite mundane, actually ;)
 *
 * The slightly tricky bit is that this is a per-object (i.e. per shared
 * library & daemon) thing and we need a bit of help (in XREF_SETUP) to
 * initialize correctly.
 */

struct xref_block {
	struct xref_block *next;
	const struct xref * const *start;
	const struct xref * const *stop;
};

extern struct xref_block *xref_blocks;
extern void xref_block_add(struct xref_block *block);
extern void xref_gcc_workaround(const struct xref *xref);

#ifndef HAVE_SECTION_SYMS
/* we have a build system patch to use GNU ld on Solaris;  if that doesn't
 * work we end up on Solaris ld which doesn't support the section start/end
 * symbols.
 */
#define XREF_SETUP() \
	CPP_NOTICE("Missing linker support for section arrays.  Solaris ld?")
#else
/* the actual symbols that the linker provides for us.  Note these are
 * _symbols_ referring to the actual section start/end, i.e. they are very
 * much NOT _pointers_, rather the symbol *value* is the pointer.  Declaring
 * them as size-1 arrays is the "best" / "right" thing.
 */
extern const struct xref * const __start_xref_array[1] DSO_LOCAL;
extern const struct xref * const __stop_xref_array[1] DSO_LOCAL;

#if defined(__has_feature)
#if __has_feature(address_sanitizer)
/* no redzone around each of the xref_p please, we're building an array out
 * of variables here.  kinda breaks things if there's redzones between each
 * array item.
 */
#define xref_array_attr used, section("xref_array"), no_sanitize("address")
#endif
#endif
#ifndef xref_array_attr
#define xref_array_attr used, section("xref_array")
#endif

/* this macro is invoked once for each standalone DSO through
 *   FRR_MODULE_SETUP  \
 *                      }-> FRR_COREMOD_SETUP -> XREF_SETUP
 *   FRR_DAEMON_INFO   /
 */
#define XREF_SETUP()                                                           \
	static const struct xref _dummy_xref = {                               \
			/* .xrefdata = */ NULL,                                \
			/* .type = */ XREFT_NONE,                              \
			/* .line = */ __LINE__,                                \
			/* .file = */ __FILE__,                                \
			/* .func = */ "dummy",                                 \
	};                                                                     \
	static const struct xref * const _dummy_xref_p                         \
			__attribute__((xref_array_attr)) = &_dummy_xref;       \
	static void __attribute__((used, _CONSTRUCTOR(1100)))                  \
			_xref_init(void) {                                     \
		static struct xref_block _xref_block = {                       \
			.next = NULL,                                          \
			.start = __start_xref_array,                           \
			.stop = __stop_xref_array,                             \
		};                                                             \
		xref_block_add(&_xref_block);                                  \
	}                                                                      \
	asm(XREF_NOTE);                                                        \
	MACRO_REQUIRE_SEMICOLON() /* end */

/* the following blurb emits an ELF note indicating start and end of the xref
 * array in the binary.  This is technically the "correct" entry point for
 * external tools reading xrefs out of an ELF shared library or executable.
 *
 * right now, the extraction tools use the section header for "xref_array"
 * instead; however, section headers are technically not necessarily preserved
 * for fully linked libraries or executables.  (In practice they are only
 * stripped by obfuscation tools.)
 *
 * conversely, for reading xrefs out of a single relocatable object file (e.g.
 * bar.o), section headers are the right thing to look at since the note is
 * only emitted for the final binary once.
 *
 * FRR itself does not need this note to operate correctly, so if you have
 * some build issue with it just add -DFRR_XREF_NO_NOTE to your build flags
 * to disable it.
 */
#if defined(FRR_XREF_NO_NOTE) || defined(__mips64)
#define XREF_NOTE ""

/* mips64 note:  MIPS64 (regardless of endianness, both mips64 & mips64el)
 * does not have a 64-bit PC-relative relocation type.  Unfortunately, a
 * 64-bit PC-relative relocation is exactly what the below asm magic emits.
 * Therefore, the xref ELF note is permanently disabled on MIPS64.
 *
 * For some context, refer to https://reviews.llvm.org/D80390
 *
 * As noted above, xref extraction still works through the section header
 * path, so no functionality is lost.
 */
#else

#if __SIZEOF_POINTER__ == 4
#define _NOTE_2PTRSIZE	"8"
#define _NOTE_PTR	".long"
#elif __SIZEOF_POINTER__ == 8
#define _NOTE_2PTRSIZE	"16"
#define _NOTE_PTR	".quad"
#else
#error unsupported pointer size
#endif

#ifdef __arm__
# define asmspecial "%"
#else
# define asmspecial "@"
#endif

#define XREF_NOTE                                                              \
	""                                                                 "\n"\
	"	.type _frr_xref_note," asmspecial "object"                 "\n"\
	"	.pushsection .note.FRR,\"a\"," asmspecial "note"           "\n"\
	"	.p2align 2"                                                "\n"\
	"_frr_xref_note:"                                                  "\n"\
	"	.long	9"                                                 "\n"\
	"	.long	" _NOTE_2PTRSIZE                                   "\n"\
	"	.ascii	\"XREF\""                                          "\n"\
	"	.ascii	\"FRRouting\\0\\0\\0\""                            "\n"\
	"	" _NOTE_PTR "	__start_xref_array-."                      "\n"\
	"	" _NOTE_PTR "	__stop_xref_array-."                       "\n"\
	"	.size _frr_xref_note, .-_frr_xref_note"                    "\n"\
	"	.popsection"                                               "\n"\
	""                                                                 "\n"\
	/* end */
#endif

#endif /* HAVE_SECTION_SYMS */

/* emit the array entry / pointer to xref */
#if defined(__clang__) || !defined(__cplusplus)
#define XREF_LINK(dst)                                                         \
	static const struct xref * const NAMECTR(xref_p_)                      \
			__attribute__((xref_array_attr))                       \
		= &(dst)                                                       \
	/* end */

#else /* GCC && C++ */
/* workaround for GCC bug 41091 (dated 2009), added in 2021...
 *
 * this breaks extraction of xrefs with xrelfo.py (because the xref_array
 * entry will be missing), but provides full runtime functionality.  To get
 * the proper list of xrefs from C++ code, build with clang...
 */
struct _xref_p {
	const struct xref * const ptr;

	_xref_p(const struct xref *_ptr) : ptr(_ptr)
	{
		xref_gcc_workaround(_ptr);
	}
};

#define XREF_LINK(dst)                                                         \
	static const struct _xref_p __attribute__((used))                      \
			NAMECTR(xref_p_)(&(dst))                               \
	/* end */
#endif

/* initializer for a "struct xref" */
#define XREF_INIT(type_, xrefdata_, func_)                                     \
	{                                                                      \
		/* .xrefdata = */ (xrefdata_),                                 \
		/* .type = */ (type_),                                         \
		/* .line = */ __LINE__,                                        \
		/* .file = */ __FILE__,                                        \
		/* .func = */ func_,                                           \
	}                                                                      \
	/* end */

/* use with XREF_INIT when outside of a function, i.e. no __func__ */
#define XREF_NO_FUNC	"<global>"

#ifdef __cplusplus
}
#endif

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