<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="X-UA-Compatible" content="IE=Edge" />
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>Type Metadata — LLVM 8 documentation</title>
<link rel="stylesheet" href="_static/llvm-theme.css" type="text/css" />
<link rel="stylesheet" href="_static/pygments.css" type="text/css" />
<script type="text/javascript" id="documentation_options" data-url_root="./" src="_static/documentation_options.js"></script>
<script type="text/javascript" src="_static/jquery.js"></script>
<script type="text/javascript" src="_static/underscore.js"></script>
<script type="text/javascript" src="_static/doctools.js"></script>
<script type="text/javascript" src="_static/language_data.js"></script>
<link rel="index" title="Index" href="genindex.html" />
<link rel="search" title="Search" href="search.html" />
<link rel="next" title="Code Transformation Metadata" href="TransformMetadata.html" />
<link rel="prev" title="MergeFunctions pass, how it works" href="MergeFunctions.html" />
<style type="text/css">
table.right { float: right; margin-left: 20px; }
table.right td { border: 1px solid #ccc; }
</style>
</head><body>
<div class="logo">
<a href="index.html">
<img src="_static/logo.png"
alt="LLVM Logo" width="250" height="88"/></a>
</div>
<div class="related" role="navigation" aria-label="related navigation">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="genindex.html" title="General Index"
accesskey="I">index</a></li>
<li class="right" >
<a href="TransformMetadata.html" title="Code Transformation Metadata"
accesskey="N">next</a> |</li>
<li class="right" >
<a href="MergeFunctions.html" title="MergeFunctions pass, how it works"
accesskey="P">previous</a> |</li>
<li><a href="http://llvm.org/">LLVM Home</a> | </li>
<li><a href="index.html">Documentation</a>»</li>
</ul>
</div>
<div class="document">
<div class="documentwrapper">
<div class="body" role="main">
<div class="section" id="type-metadata">
<h1>Type Metadata<a class="headerlink" href="#type-metadata" title="Permalink to this headline">¶</a></h1>
<p>Type metadata is a mechanism that allows IR modules to co-operatively build
pointer sets corresponding to addresses within a given set of globals. LLVM’s
<a class="reference external" href="http://clang.llvm.org/docs/ControlFlowIntegrity.html">control flow integrity</a> implementation uses this metadata to efficiently
check (at each call site) that a given address corresponds to either a
valid vtable or function pointer for a given class or function type, and its
whole-program devirtualization pass uses the metadata to identify potential
callees for a given virtual call.</p>
<p>To use the mechanism, a client creates metadata nodes with two elements:</p>
<ol class="arabic simple">
<li>a byte offset into the global (generally zero for functions)</li>
<li>a metadata object representing an identifier for the type</li>
</ol>
<p>These metadata nodes are associated with globals by using global object
metadata attachments with the <code class="docutils literal notranslate"><span class="pre">!type</span></code> metadata kind.</p>
<p>Each type identifier must exclusively identify either global variables
or functions.</p>
<div class="admonition-limitation admonition">
<p class="first admonition-title">Limitation</p>
<p class="last">The current implementation only supports attaching metadata to functions on
the x86-32 and x86-64 architectures.</p>
</div>
<p>An intrinsic, <a class="reference internal" href="LangRef.html#type-test"><span class="std std-ref">llvm.type.test</span></a>, is used to test whether a
given pointer is associated with a type identifier.</p>
<div class="section" id="representing-type-information-using-type-metadata">
<h2>Representing Type Information using Type Metadata<a class="headerlink" href="#representing-type-information-using-type-metadata" title="Permalink to this headline">¶</a></h2>
<p>This section describes how Clang represents C++ type information associated with
virtual tables using type metadata.</p>
<p>Consider the following inheritance hierarchy:</p>
<div class="highlight-c++ notranslate"><div class="highlight"><pre><span></span><span class="k">struct</span> <span class="n">A</span> <span class="p">{</span>
<span class="k">virtual</span> <span class="kt">void</span> <span class="n">f</span><span class="p">();</span>
<span class="p">};</span>
<span class="k">struct</span> <span class="nl">B</span> <span class="p">:</span> <span class="n">A</span> <span class="p">{</span>
<span class="k">virtual</span> <span class="kt">void</span> <span class="n">f</span><span class="p">();</span>
<span class="k">virtual</span> <span class="kt">void</span> <span class="nf">g</span><span class="p">();</span>
<span class="p">};</span>
<span class="k">struct</span> <span class="n">C</span> <span class="p">{</span>
<span class="k">virtual</span> <span class="kt">void</span> <span class="n">h</span><span class="p">();</span>
<span class="p">};</span>
<span class="k">struct</span> <span class="nl">D</span> <span class="p">:</span> <span class="n">A</span><span class="p">,</span> <span class="n">C</span> <span class="p">{</span>
<span class="k">virtual</span> <span class="kt">void</span> <span class="n">f</span><span class="p">();</span>
<span class="k">virtual</span> <span class="kt">void</span> <span class="nf">h</span><span class="p">();</span>
<span class="p">};</span>
</pre></div>
</div>
<p>The virtual table objects for A, B, C and D look like this (under the Itanium ABI):</p>
<table border="1" class="docutils" id="id1">
<caption><span class="caption-text">Virtual Table Layout for A, B, C, D</span><a class="headerlink" href="#id1" title="Permalink to this table">¶</a></caption>
<colgroup>
<col width="13%" />
<col width="13%" />
<col width="13%" />
<col width="13%" />
<col width="13%" />
<col width="13%" />
<col width="13%" />
<col width="13%" />
</colgroup>
<thead valign="bottom">
<tr class="row-odd"><th class="head">Class</th>
<th class="head">0</th>
<th class="head">1</th>
<th class="head">2</th>
<th class="head">3</th>
<th class="head">4</th>
<th class="head">5</th>
<th class="head">6</th>
</tr>
</thead>
<tbody valign="top">
<tr class="row-even"><td>A</td>
<td>A::offset-to-top</td>
<td>&A::rtti</td>
<td>&A::f</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr class="row-odd"><td>B</td>
<td>B::offset-to-top</td>
<td>&B::rtti</td>
<td>&B::f</td>
<td>&B::g</td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr class="row-even"><td>C</td>
<td>C::offset-to-top</td>
<td>&C::rtti</td>
<td>&C::h</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
<tr class="row-odd"><td>D</td>
<td>D::offset-to-top</td>
<td>&D::rtti</td>
<td>&D::f</td>
<td>&D::h</td>
<td>D::offset-to-top</td>
<td>&D::rtti</td>
<td>thunk for &D::h</td>
</tr>
</tbody>
</table>
<p>When an object of type A is constructed, the address of <code class="docutils literal notranslate"><span class="pre">&A::f</span></code> in A’s
virtual table object is stored in the object’s vtable pointer. In ABI parlance
this address is known as an <a class="reference external" href="https://itanium-cxx-abi.github.io/cxx-abi/abi.html#vtable-general">address point</a>. Similarly, when an object of type
B is constructed, the address of <code class="docutils literal notranslate"><span class="pre">&B::f</span></code> is stored in the vtable pointer. In
this way, the vtable in B’s virtual table object is compatible with A’s vtable.</p>
<p>D is a little more complicated, due to the use of multiple inheritance. Its
virtual table object contains two vtables, one compatible with A’s vtable and
the other compatible with C’s vtable. Objects of type D contain two virtual
pointers, one belonging to the A subobject and containing the address of
the vtable compatible with A’s vtable, and the other belonging to the C
subobject and containing the address of the vtable compatible with C’s vtable.</p>
<p>The full set of compatibility information for the above class hierarchy is
shown below. The following table shows the name of a class, the offset of an
address point within that class’s vtable and the name of one of the classes
with which that address point is compatible.</p>
<table border="1" class="docutils" id="id2">
<caption><span class="caption-text">Type Offsets for A, B, C, D</span><a class="headerlink" href="#id2" title="Permalink to this table">¶</a></caption>
<colgroup>
<col width="33%" />
<col width="33%" />
<col width="33%" />
</colgroup>
<thead valign="bottom">
<tr class="row-odd"><th class="head">VTable for</th>
<th class="head">Offset</th>
<th class="head">Compatible Class</th>
</tr>
</thead>
<tbody valign="top">
<tr class="row-even"><td>A</td>
<td>16</td>
<td>A</td>
</tr>
<tr class="row-odd"><td>B</td>
<td>16</td>
<td>A</td>
</tr>
<tr class="row-even"><td> </td>
<td> </td>
<td>B</td>
</tr>
<tr class="row-odd"><td>C</td>
<td>16</td>
<td>C</td>
</tr>
<tr class="row-even"><td>D</td>
<td>16</td>
<td>A</td>
</tr>
<tr class="row-odd"><td> </td>
<td> </td>
<td>D</td>
</tr>
<tr class="row-even"><td> </td>
<td>48</td>
<td>C</td>
</tr>
</tbody>
</table>
<p>The next step is to encode this compatibility information into the IR. The way
this is done is to create type metadata named after each of the compatible
classes, with which we associate each of the compatible address points in
each vtable. For example, these type metadata entries encode the compatibility
information for the above hierarchy:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>@_ZTV1A = constant [...], !type !0
@_ZTV1B = constant [...], !type !0, !type !1
@_ZTV1C = constant [...], !type !2
@_ZTV1D = constant [...], !type !0, !type !3, !type !4
!0 = !{i64 16, !"_ZTS1A"}
!1 = !{i64 16, !"_ZTS1B"}
!2 = !{i64 16, !"_ZTS1C"}
!3 = !{i64 16, !"_ZTS1D"}
!4 = !{i64 48, !"_ZTS1C"}
</pre></div>
</div>
<p>With this type metadata, we can now use the <code class="docutils literal notranslate"><span class="pre">llvm.type.test</span></code> intrinsic to
test whether a given pointer is compatible with a type identifier. Working
backwards, if <code class="docutils literal notranslate"><span class="pre">llvm.type.test</span></code> returns true for a particular pointer,
we can also statically determine the identities of the virtual functions
that a particular virtual call may call. For example, if a program assumes
a pointer to be a member of <code class="docutils literal notranslate"><span class="pre">!"_ZST1A"</span></code>, we know that the address can
be only be one of <code class="docutils literal notranslate"><span class="pre">_ZTV1A+16</span></code>, <code class="docutils literal notranslate"><span class="pre">_ZTV1B+16</span></code> or <code class="docutils literal notranslate"><span class="pre">_ZTV1D+16</span></code> (i.e. the
address points of the vtables of A, B and D respectively). If we then load
an address from that pointer, we know that the address can only be one of
<code class="docutils literal notranslate"><span class="pre">&A::f</span></code>, <code class="docutils literal notranslate"><span class="pre">&B::f</span></code> or <code class="docutils literal notranslate"><span class="pre">&D::f</span></code>.</p>
</div>
<div class="section" id="testing-addresses-for-type-membership">
<h2>Testing Addresses For Type Membership<a class="headerlink" href="#testing-addresses-for-type-membership" title="Permalink to this headline">¶</a></h2>
<p>If a program tests an address using <code class="docutils literal notranslate"><span class="pre">llvm.type.test</span></code>, this will cause
a link-time optimization pass, <code class="docutils literal notranslate"><span class="pre">LowerTypeTests</span></code>, to replace calls to this
intrinsic with efficient code to perform type member tests. At a high level,
the pass will lay out referenced globals in a consecutive memory region in
the object file, construct bit vectors that map onto that memory region,
and generate code at each of the <code class="docutils literal notranslate"><span class="pre">llvm.type.test</span></code> call sites to test
pointers against those bit vectors. Because of the layout manipulation, the
globals’ definitions must be available at LTO time. For more information,
see the <a class="reference external" href="http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html">control flow integrity design document</a>.</p>
<p>A type identifier that identifies functions is transformed into a jump table,
which is a block of code consisting of one branch instruction for each
of the functions associated with the type identifier that branches to the
target function. The pass will redirect any taken function addresses to the
corresponding jump table entry. In the object file’s symbol table, the jump
table entries take the identities of the original functions, so that addresses
taken outside the module will pass any verification done inside the module.</p>
<p>Jump tables may call external functions, so their definitions need not
be available at LTO time. Note that if an externally defined function is
associated with a type identifier, there is no guarantee that its identity
within the module will be the same as its identity outside of the module,
as the former will be the jump table entry if a jump table is necessary.</p>
<p>The <a class="reference external" href="https://github.com/llvm/llvm-project/blob/master/llvm/include/llvm/Transforms/IPO/LowerTypeTests.h">GlobalLayoutBuilder</a> class is responsible for laying out the globals
efficiently to minimize the sizes of the underlying bitsets.</p>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field-odd field"><th class="field-name">Example:</th><td class="field-body"></td>
</tr>
</tbody>
</table>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>target datalayout = "e-p:32:32"
@a = internal global i32 0, !type !0
@b = internal global i32 0, !type !0, !type !1
@c = internal global i32 0, !type !1
@d = internal global [2 x i32] [i32 0, i32 0], !type !2
define void @e() !type !3 {
ret void
}
define void @f() {
ret void
}
declare void @g() !type !3
!0 = !{i32 0, !"typeid1"}
!1 = !{i32 0, !"typeid2"}
!2 = !{i32 4, !"typeid2"}
!3 = !{i32 0, !"typeid3"}
declare i1 @llvm.type.test(i8* %ptr, metadata %typeid) nounwind readnone
define i1 @foo(i32* %p) {
%pi8 = bitcast i32* %p to i8*
%x = call i1 @llvm.type.test(i8* %pi8, metadata !"typeid1")
ret i1 %x
}
define i1 @bar(i32* %p) {
%pi8 = bitcast i32* %p to i8*
%x = call i1 @llvm.type.test(i8* %pi8, metadata !"typeid2")
ret i1 %x
}
define i1 @baz(void ()* %p) {
%pi8 = bitcast void ()* %p to i8*
%x = call i1 @llvm.type.test(i8* %pi8, metadata !"typeid3")
ret i1 %x
}
define void @main() {
%a1 = call i1 @foo(i32* @a) ; returns 1
%b1 = call i1 @foo(i32* @b) ; returns 1
%c1 = call i1 @foo(i32* @c) ; returns 0
%a2 = call i1 @bar(i32* @a) ; returns 0
%b2 = call i1 @bar(i32* @b) ; returns 1
%c2 = call i1 @bar(i32* @c) ; returns 1
%d02 = call i1 @bar(i32* getelementptr ([2 x i32]* @d, i32 0, i32 0)) ; returns 0
%d12 = call i1 @bar(i32* getelementptr ([2 x i32]* @d, i32 0, i32 1)) ; returns 1
%e = call i1 @baz(void ()* @e) ; returns 1
%f = call i1 @baz(void ()* @f) ; returns 0
%g = call i1 @baz(void ()* @g) ; returns 1
ret void
}
</pre></div>
</div>
</div>
</div>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="related" role="navigation" aria-label="related navigation">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="genindex.html" title="General Index"
>index</a></li>
<li class="right" >
<a href="TransformMetadata.html" title="Code Transformation Metadata"
>next</a> |</li>
<li class="right" >
<a href="MergeFunctions.html" title="MergeFunctions pass, how it works"
>previous</a> |</li>
<li><a href="http://llvm.org/">LLVM Home</a> | </li>
<li><a href="index.html">Documentation</a>»</li>
</ul>
</div>
<div class="footer" role="contentinfo">
© Copyright 2003-2020, LLVM Project.
Last updated on 2020-09-07.
Created using <a href="http://sphinx-doc.org/">Sphinx</a> 1.8.4.
</div>
</body>
</html>
distrib
>
Mageia
>
7
>
i586
>
media
>
core-updates
>
by-pkgid
>
d635a8cd705396ade48f1d2b830a115d
>
files
>
2084
