From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 42111 invoked by alias); 26 Apr 2017 16:04:17 -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 42071 invoked by uid 89); 26 Apr 2017 16:04:16 -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.3 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,RCVD_IN_SORBS_SPAM,SPF_PASS autolearn=ham version=3.3.2 spammy=sk:ccoutan, ccoutantgmailcom, U*ccoutant, ccoutant@gmail.com X-Spam-Status: No, score=-2.3 required=5.0 tests=AWL,BAYES_00,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,RCVD_IN_SORBS_SPAM,SPF_PASS autolearn=ham version=3.3.2 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on sourceware.org X-Spam-Level: X-Spam-User: qpsmtpd, 2 recipients X-HELO: mail-qt0-f180.google.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=I/kioJ4qQW/pTYsqjVLl1hoRuB0LeAP0pB3LNAYiViM=; b=T2HZD6e47i3Op6+CId4h6TxNcPYNOP8IHCEtNtA7++yd57LX2xKKeq+Q0EIG/dvg7m Aw/BwnEr/fay7P8VztZqLNoYcfqHZUuRURJlcj4QWSgTTDhYedcP6WU5YAdbbh1R0JdQ AmdcZ/XV43dOROQjUXQgsD3Sm92HCI5Dde0vNenU/ErET7XhiN4C2WaoL6vyVB8VVm6/ PaA1pa1H0GWIDGfDT8wK4uXjj9RdOcX04JzI6paYT+la48UOP91rnOYFBkuhZYgamGaQ eZhzDunECSmt1vHyCNrb5apYyc7bTA90F4v1hZEagEz3Dxmbiu3rhqohn+2pkLAGHplQ LRTQ== 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; bh=I/kioJ4qQW/pTYsqjVLl1hoRuB0LeAP0pB3LNAYiViM=; b=plwYjlwO23S82O0zt3WdB0WbAKNHRPodM3bjVywBpaqIjC6SQcccKvcBb6nbRHVTY8 ltWEJL0uJq/DPyvE60K8RTT/LDv4BPZ9crEPDtGOI8Ddf4NTT7udkm7m1f2mUFtczGy6 GYundxRm9i3U/85vmWLHUSYKkXBbjo7ZeDPkoL7RWQnfbLLmMdRu6aeZa5ebIJ9rD/RE /GOPoh8vKySH+SwF/di39PqqWRD6Qyj0jqQhAHSdzJ+O/Kxqz8Js93VkT9dFtCSNtkXM Bo0tQtP1vYE+mR4vtYOMtJ8MK7Iw4Egj/5proAnIDbujWm8+Rq9zcrwtdjjLgv9jzRf6 H0/A== X-Gm-Message-State: AN3rC/6vLDoNNdrfUMgpvkqSIZr/RCf8GH5JqtSPMIPyNM1oItzut8Fy tdDiWgsHMHG0rkRTpAqDJ6/q+S3V4w== X-Received: by 10.237.50.197 with SMTP id z63mr575457qtd.48.1493222650109; Wed, 26 Apr 2017 09:04:10 -0700 (PDT) MIME-Version: 1.0 In-Reply-To: References: From: "H.J. Lu" 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: Cary Coutant Cc: Sriraman Tallam , gnu-gabi@sourceware.org, binutils , Xinliang David Li , Sterling Augustine , Paul Pluzhnikov , Ian Lance Taylor , Rahul Chaudhry , Luis Lozano , =?UTF-8?Q?Rafael_Esp=C3=ADndola?= , Peter Collingbourne , Rui Ueyama Content-Type: text/plain; charset=UTF-8 X-SW-Source: 2017-q2/txt/msg00005.txt.bz2 On Tue, Apr 25, 2017 at 9:06 PM, Cary Coutant wrote: >> Idea A: Shrinking the size of the dynamic relocations > > 4. Evaluate some alternate representations to improve upon the simple > list of addresses. An idea I've been considering is emitting a bitmap > -- an alternating series of pairs (starting address, bits), where > "bits" is just a fixed-size bit vector describing each word starting > at the given starting address. The "bits" field could be, say, 128 or > 256 bits in length, or could begin with a byte that defines its > length. I think this would work well, as the relocations are often > clustered, but haven't yet done any testing of that hypothesis. A > simple run-length encoding, as previously suggested, would also work, > of course. I'm not in favor of using a general-purpose compression > algorithm on the relocations. > On x86, the last 2/3 bits are always zero. We can use it to encode the next value. Offsets are represented by 1. A base offset and followed by consecutive deltas. 2. Encode the size of next delta in the unused bits. static size_t encode_offsets (uintptr_t *original, char *encoded, size_t n) { size_t i; int current_bytes, next_bytes; size_t encoded_size; uintptr_t offset, next, current; offset = original[0]; if ((offset & (sizeof (uintptr_t) - 1)) != 0) abort (); next = original[1] - offset; if (next == 0) abort (); next_bytes = sizeof (uintptr_t) - __builtin_clzl (next) / 8; if (next_bytes > sizeof (uintptr_t)) abort (); /* Encode number of bytes of the next delta in the unused bits. */ offset |= next_bytes - 1; memcpy (encoded, &offset, sizeof (uintptr_t)); encoded_size = sizeof (uintptr_t); encoded += encoded_size; for (i = 1; i < n; i++) { current = next; current_bytes = next_bytes; if ((i + 1) < n) { offset = original[i]; if ((offset & (sizeof (uintptr_t) - 1)) != 0) abort (); next = original[i + 1] - offset; if (next == 0) abort (); next_bytes = sizeof (uintptr_t) - __builtin_clzl (next) / 8; if (next_bytes > sizeof (uintptr_t)) abort (); /* Encode number of bytes of the next delta in the unused bits. */ current |= next_bytes - 1; } /* FIXME: Only works for little endian. */ memcpy (encoded, ¤t, current_bytes); encoded_size += current_bytes; encoded += current_bytes; } return encoded_size; } On x86-64, I got Total : 1471 offsets Before: 11768 bytes After : 1479 bytes -- H.J.