From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 92150 invoked by alias); 11 Dec 2017 18:41:14 -0000 Mailing-List: contact gnu-gabi-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Post: List-Help: List-Subscribe: Sender: gnu-gabi-owner@sourceware.org Received: (qmail 92125 invoked by uid 89); 11 Dec 2017 18:41:13 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Checked: by ClamAV 0.99.2 on sourceware.org X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.7 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_NONE,SPF_PASS,T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 spammy=HTo:U*fw, experiments, Hx-languages-length:2293 X-Spam-Status: No, score=-2.7 required=5.0 tests=AWL,BAYES_00,RCVD_IN_DNSWL_NONE,SPF_PASS,T_RP_MATCHES_RCVD autolearn=ham version=3.3.2 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on sourceware.org X-Spam-Level: X-HELO: mail-ua0-f178.google.com Received: from mail-ua0-f178.google.com (HELO mail-ua0-f178.google.com) (209.85.217.178) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 11 Dec 2017 18:41:12 +0000 Received: by mail-ua0-f178.google.com with SMTP id i20so12659406uak.6 for ; Mon, 11 Dec 2017 10:41:11 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=xSwwuX3tOAoicG1oiAY8vFHaQkZ2B2aSddi4TCgs3Uo=; b=rw99cBUUNLGOmcgxkBDNGt2lqEg5yKNsJYt9KmeolEkT+abpUsugVdSDICAy/FBIgO op9bxHS0VnQYrdhrbaVj7izI7PcwniNVx/Vys5/idSg9IIy8TKrr+NgPS1FUP3CHmDck De4JHoIfRLH8VLJTzIkMfYE9dvbjs1Z5xYQTDH52sgKU1V9tCp94ZJfgNphUx7J15Mh7 QQJS6BDaJIR+vL07wkSUwS4uSWdPL5iIOF+nKXESvUxCYArFIPBV2eCpMbkd0se4pI6F qjT9qeyQ+DOtoKnbEXlw++99lkXQ8Hkk0+0w8JExwOacVj20CRJtT+2Lltc6IN3XtvKm iL1A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=xSwwuX3tOAoicG1oiAY8vFHaQkZ2B2aSddi4TCgs3Uo=; b=Jy8eOxmzuQWgfTIv9+D/GfGb2WYjkDL9sv6nQq84pFLi1Sfi0EZnkQYR1mIX7r53pK 9v0Y2WPE9wxgovjipRbGpP4jQd43E7WCImaX6Fk7x1RAI8GUoRJRymIFMi3hLzMCs/qq 1qa8D3D5YPuF7Kbr7uo9qp3aQbhxWMKI1ZRIt5b7F0qNXydfyjT7d7nDT60OOzb4V8Lk x4s6XOHp5n40JLtE8LTHj3z16I3w0u/vBkQZ0MecXLZuXek71J7M2BCwgVu9RK3JKZNV 3aZikyFmIcslsy3IRgK+NYSM8Qr8ZCD096T+10CfYVXmgIcdtlc2ffDsv97GIOU9rIlW aL8A== X-Gm-Message-State: AKGB3mJJ8Nct0eUcbAzoUs3p6wKxz4Vwgo5mTJqMTbduECHrX3c4i0u0 9qGbrlEMyB2DWkPel8Y2vj32w36yuLDbJv7dxscqNA== X-Google-Smtp-Source: ACJfBouZ3kyBa+s+691SZLTqYCfeAzaNhUlkexun5tSxz4qgEJVAWtkHUFQYM4DautMGAUSZjiV6fmtDxs0rDiP2W78= X-Received: by 10.176.17.104 with SMTP id g40mr1517689uac.62.1513017669744; Mon, 11 Dec 2017 10:41:09 -0800 (PST) MIME-Version: 1.0 Received: by 10.31.148.3 with HTTP; Mon, 11 Dec 2017 10:41:08 -0800 (PST) In-Reply-To: <874lozec25.fsf@mid.deneb.enyo.de> References: <8737cosnym.fsf@localhost.localdomain.i-did-not-set--mail-host-address--so-tickle-me> <7e698a5f-32d7-6549-7e23-8850b85e6c10@gmail.com> <874lozec25.fsf@mid.deneb.enyo.de> From: "Sriraman Tallam via gnu-gabi" Reply-To: Sriraman Tallam Date: Sun, 01 Jan 2017 00:00:00 -0000 Message-ID: Subject: Re: Reducing code size of Position Independent Executables (PIE) by shrinking the size of dynamic relocations section To: Florian Weimer Cc: Rahul Chaudhry via gnu-gabi , Rahul Chaudhry , Suprateeka R Hegde , Florian Weimer , David Edelsohn , Rafael Avila de Espindola , Binutils Development , Alan Modra , Cary Coutant , Xinliang David Li , Sterling Augustine , Paul Pluzhnikov , Ian Lance Taylor , "H.J. Lu" , Luis Lozano , Peter Collingbourne , Rui Ueyama , llvm-dev@lists.llvm.org Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-IsSubscribed: yes X-SW-Source: 2017-q4/txt/msg00014.txt.bz2 On Sat, Dec 9, 2017 at 3:06 PM, Florian Weimer wrote: > * Rahul Chaudhry via gnu-gabi: > >> The encoding used is a simple combination of delta-encoding and a >> bitmap of offsets. The section consists of 64-bit entries: higher >> 8-bits contain delta since last offset, and lower 56-bits contain a >> bitmap for which words to apply the relocation to. This is best >> described by showing the code for decoding the section: >> >> typedef struct >> { >> Elf64_Xword r_data; /* jump and bitmap for relative relocations */ >> } Elf64_Relrz; >> >> #define ELF64_R_JUMP(val) ((val) >> 56) >> #define ELF64_R_BITS(val) ((val) & 0xffffffffffffff) >> >> #ifdef DO_RELRZ >> { >> ElfW(Addr) offset =3D 0; >> for (; relative < end; ++relative) >> { >> ElfW(Addr) jump =3D ELFW(R_JUMP) (relative->r_data); >> ElfW(Addr) bits =3D ELFW(R_BITS) (relative->r_data); >> offset +=3D jump * sizeof(ElfW(Addr)); >> if (jump =3D=3D 0) >> { >> ++relative; >> offset =3D relative->r_data; >> } >> ElfW(Addr) r_offset =3D offset; >> for (; bits !=3D 0; bits >>=3D 1) >> { >> if ((bits&1) !=3D 0) >> elf_machine_relrz_relative (l_addr, (void *) (l_addr + r_o= ffset)); >> r_offset +=3D sizeof(ElfW(Addr)); >> } >> } >> } >> #endif > > That data-dependent =E2=80=9Cif ((bits&1) !=3D 0)=E2=80=9D branch looks a= bit nasty. > > Have you investigated whether some sort of RLE-style encoding would be > beneficial? If there are blocks of relative relocations, it might even > be possible to use vector instructions to process them (although more > than four relocations at a time are probably not achievable in a > power-efficient manner on current x86-64). Yes, we originally investigated RLE style encoding but I guess the key insight which led us towards the proposed encoding is the following. The offset addresses which contain the relocations are close but not necessarily contiguous. We experimented with an encoding strategy where we would store the initial offset and the number of words after that which contained dynamic relocations. This gave us good compression numbers but the proposed scheme was way better. I will let Rahul say more as he did quite a bit of experiments with different strategies. Thanks Sri