From: "Rahul Chaudhry via binutils" <binutils@sourceware.org>
To: Cary Coutant <ccoutant@gmail.com>
Cc: Roland McGrath <roland@hack.frob.com>,
Sriraman Tallam <tmsriram@google.com>,
Florian Weimer <fw@deneb.enyo.de>,
Rahul Chaudhry via gnu-gabi <gnu-gabi@sourceware.org>,
Suprateeka R Hegde <hegdesmailbox@gmail.com>,
Florian Weimer <fweimer@redhat.com>,
David Edelsohn <dje.gcc@gmail.com>,
Rafael Avila de Espindola <rafael.espindola@gmail.com>,
Binutils Development <binutils@sourceware.org>,
Alan Modra <amodra@gmail.com>,
Xinliang David Li <davidxl@google.com>,
Sterling Augustine <saugustine@google.com>,
Paul Pluzhnikov <ppluzhnikov@google.com>,
Ian Lance Taylor <iant@google.com>,
"H.J. Lu" <hjl.tools@gmail.com>,
Luis Lozano <llozano@google.com>,
Peter Collingbourne <pcc@google.com>,
Rui Ueyama <ruiu@google.com>,
llvm-dev@lists.llvm.org
Subject: Re: Reducing code size of Position Independent Executables (PIE) by shrinking the size of dynamic relocations section
Date: Fri, 15 Dec 2017 20:23:00 -0000 [thread overview]
Message-ID: <CAJRD=oodUsXaRf6trNnN7-=9TFrqQFjeM_TviPPfFWoMPkzmGA@mail.gmail.com> (raw)
In-Reply-To: <CAJimCsHJ9H0uhMbrAZm-BS_VpYggv21ENJm7Q56LTOqC4scYnQ@mail.gmail.com>
On Thu, Dec 14, 2017 at 12:11 AM, Cary Coutant <ccoutant@gmail.com> wrote:
>> While adding a 'stride' field is definitely an improvement over simple
>> delta+count encoding, it doesn't compare well against the bitmap based
>> encoding.
>>
>> I took a look inside the encoding for the Vim binary. There are some instances
>> in the bitmap based encoding like
>> [0x3855555555555555 0x3855555555555555 0x3855555555555555 ...]
>> that encode sequences of relocations applying to alternate words. The stride
>> based encoding works very well on these and turns it into much more compact
>> [0x0ff010ff 0x0ff010ff 0x0ff010ff ...]
>> using stride==0x10 and count==0xff.
>
> Have you looked much at where the RELATIVE relocations are coming from?
>
> I've looked at a PIE build of gold, and they're almost all for
> vtables, which mostly have consecutive entries with 8-byte strides.
> There are a few for the GOT, a few for static constructors (in
> .init_array), and a few for other initialized data, but vtables seem
> to account for the vast majority. (Gold has almost 19,000 RELATIVE
> dynamic relocs, and only about 500 non-RELATIVE dynamic relocs.)
>
> Where do the 16-byte strides come from? Vim is plain C, right? I'm
> guessing its RELATIVE relocation count is fairly low compared to big
> C++ apps. I'm also guessing that the pattern comes from some large
> structure or structures in the source code where initialized pointers
> alternate with non-pointer values. I'm also curious about Roland's
> app.
I took a look inside vim for the source of the ..5555.. pattern (relative
relocations applying to alternate words). One of the sources is the
"builtin_termcaps" symbol, which is an array of "struct builtin_term":
struct builtin_term
{
int bt_entry;
char *bt_string;
};
So the pattern makes sense. An encoding using strides will work really well
here with stride == 0x10.
There is another repeating pattern I noticed in vim ..9999... One of the
sources behind this pattern is the "cmdnames" symbol, which is an array of
"struct cmdname":
struct cmdname
{
char_u *cmd_name; /* name of the command */
ex_func_T cmd_func; /* function for this command */
long_u cmd_argt; /* flags declared above */
int cmd_addr_type; /* flag for address type */
};
In this struct, the first two fields are pointers, and the next two are
scalars. This explains the ..9999.. pattern for relative relocations. This is
an example where a stride based encoding does not work well, simply because
there is no single stride. The deltas are 8,24,8,24,8,24,...
I think these two examples demonstrate the main weakness of using a simple
stride based encoding: it is too sensitive to how the data structures are laid
out in the program source.
Rahul
next prev parent reply other threads:[~2017-12-15 20:23 UTC|newest]
Thread overview: 34+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-04-30 14:10 David Edelsohn
2017-05-01 13:31 ` Rafael Avila de Espindola
2017-05-01 14:13 ` David Edelsohn
2017-05-01 18:28 ` Suprateeka R Hegde
2017-05-01 18:36 ` Florian Weimer
2017-05-02 17:17 ` Suprateeka R Hegde
2017-05-08 20:55 ` Sriraman Tallam via binutils
2017-12-07 22:51 ` Rahul Chaudhry via binutils
2017-12-07 23:37 ` Ian Lance Taylor via binutils
2017-12-09 6:36 ` Cary Coutant
2017-12-12 0:05 ` Rahul Chaudhry via binutils
2017-12-19 19:41 ` Rahul Chaudhry via binutils
2017-12-09 23:06 ` Florian Weimer
2017-12-11 18:41 ` Sriraman Tallam via binutils
[not found] ` <CAJRD=opP96vFuSKK-1d1jw3nOKeTDE1T_E5hDwj3Zy-VUeAnRA@mail.gmail.com>
[not found] ` <CAORpzuMftCGpXUObOyoFY0=jorMBDWEDbQJ23DifTNW3v-WA6Q@mail.gmail.com>
2017-12-13 0:53 ` Rahul Chaudhry via binutils
2017-12-14 8:11 ` Cary Coutant
2017-12-15 20:23 ` Rahul Chaudhry via binutils [this message]
[not found] ` <CAORpzuPYsSBJtypm3NDcfcgRzos3WO4JjkvgiqpyBYBhoqLVFA@mail.gmail.com>
2018-01-07 10:31 ` Florian Weimer
-- strict thread matches above, loose matches on Subject: below --
2017-04-25 17:12 Sriraman Tallam via binutils
2017-04-25 18:02 ` H.J. Lu
2017-04-25 18:30 ` Sriraman Tallam via binutils
2017-04-26 4:07 ` Cary Coutant
2017-04-26 5:47 ` Markus Trippelsdorf
2017-04-26 16:04 ` H.J. Lu
2017-04-26 17:34 ` Sriraman Tallam via binutils
2017-04-28 6:25 ` Florian Weimer
2017-04-28 8:36 ` Alan Modra
2017-04-27 20:04 ` Rafael Espíndola
2017-04-27 21:21 ` Sriraman Tallam via binutils
2017-04-25 0:22 Sriraman Tallam via binutils
2017-04-25 1:31 ` Peter Collingbourne via binutils
2017-04-25 2:18 ` Rui Ueyama via binutils
2017-04-25 15:12 ` H.J. Lu
2017-04-26 12:11 ` Alan Modra
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAJRD=oodUsXaRf6trNnN7-=9TFrqQFjeM_TviPPfFWoMPkzmGA@mail.gmail.com' \
--to=binutils@sourceware.org \
--cc=amodra@gmail.com \
--cc=ccoutant@gmail.com \
--cc=davidxl@google.com \
--cc=dje.gcc@gmail.com \
--cc=fw@deneb.enyo.de \
--cc=fweimer@redhat.com \
--cc=gnu-gabi@sourceware.org \
--cc=hegdesmailbox@gmail.com \
--cc=hjl.tools@gmail.com \
--cc=iant@google.com \
--cc=llozano@google.com \
--cc=llvm-dev@lists.llvm.org \
--cc=pcc@google.com \
--cc=ppluzhnikov@google.com \
--cc=rafael.espindola@gmail.com \
--cc=rahulchaudhry@google.com \
--cc=roland@hack.frob.com \
--cc=ruiu@google.com \
--cc=saugustine@google.com \
--cc=tmsriram@google.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).