1 #ifndef JEMALLOC_INTERNAL_RTREE_STRUCTS_H
2 #define JEMALLOC_INTERNAL_RTREE_STRUCTS_H
3 
4 struct rtree_elm_s {
5 	union {
6 		void		*pun;
7 		rtree_elm_t	*child;
8 		extent_t	*extent;
9 	};
10 };
11 
12 struct rtree_elm_witness_s {
13 	const rtree_elm_t	*elm;
14 	witness_t		witness;
15 };
16 
17 struct rtree_elm_witness_tsd_s {
18 	rtree_elm_witness_t	witnesses[RTREE_ELM_ACQUIRE_MAX];
19 };
20 
21 struct rtree_level_s {
22 	/*
23 	 * A non-NULL subtree points to a subtree rooted along the hypothetical
24 	 * path to the leaf node corresponding to key 0.  Depending on what keys
25 	 * have been used to store to the tree, an arbitrary combination of
26 	 * subtree pointers may remain NULL.
27 	 *
28 	 * Suppose keys comprise 48 bits, and LG_RTREE_BITS_PER_LEVEL is 4.
29 	 * This results in a 3-level tree, and the leftmost leaf can be directly
30 	 * accessed via levels[2], the subtree prefixed by 0x0000 (excluding
31 	 * 0x00000000) can be accessed via levels[1], and the remainder of the
32 	 * tree can be accessed via levels[0].
33 	 *
34 	 *   levels[0] : [<unused> | 0x0001******** | 0x0002******** | ...]
35 	 *
36 	 *   levels[1] : [<unused> | 0x00000001**** | 0x00000002**** | ... ]
37 	 *
38 	 *   levels[2] : [extent(0x000000000000) | extent(0x000000000001) | ...]
39 	 *
40 	 * This has practical implications on x64, which currently uses only the
41 	 * lower 47 bits of virtual address space in userland, thus leaving
42 	 * levels[0] unused and avoiding a level of tree traversal.
43 	 */
44 	union {
45 		void		*subtree_pun;
46 		rtree_elm_t	*subtree;
47 	};
48 	/* Number of key bits distinguished by this level. */
49 	unsigned		bits;
50 	/*
51 	 * Cumulative number of key bits distinguished by traversing to
52 	 * corresponding tree level.
53 	 */
54 	unsigned		cumbits;
55 };
56 
57 struct rtree_ctx_s {
58 	/* If false, key/elms have not yet been initialized by a lookup. */
59 	bool		valid;
60 	/* Key that corresponds to the tree path recorded in elms. */
61 	uintptr_t	key;
62 	/* Memoized rtree_start_level(key). */
63 	unsigned	start_level;
64 	/*
65 	 * A path through rtree, driven by key.  Only elements that could
66 	 * actually be used for subsequent lookups are initialized, i.e. if
67 	 * start_level = rtree_start_level(key) is non-zero, the first
68 	 * start_level elements are uninitialized.  The last element contains a
69 	 * pointer to the leaf node element that corresponds to key, so that
70 	 * exact matches require no tree node offset computation.
71 	 */
72 	rtree_elm_t	*elms[RTREE_HEIGHT_MAX + 1];
73 };
74 
75 struct rtree_s {
76 	unsigned		height;
77 	/*
78 	 * Precomputed table used to convert from the number of leading 0 key
79 	 * bits to which subtree level to start at.
80 	 */
81 	unsigned		start_level[RTREE_HEIGHT_MAX + 1];
82 	rtree_level_t		levels[RTREE_HEIGHT_MAX];
83 	malloc_mutex_t		init_lock;
84 };
85 
86 #endif /* JEMALLOC_INTERNAL_RTREE_STRUCTS_H */
87