From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ej1-x634.google.com (mail-ej1-x634.google.com [IPv6:2a00:1450:4864:20::634]) by sourceware.org (Postfix) with ESMTPS id 4FCA8386181F for ; Thu, 28 Mar 2024 09:23:49 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 4FCA8386181F Authentication-Results: sourceware.org; dmarc=pass (p=quarantine dis=none) header.from=suse.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 4FCA8386181F Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::634 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1711617831; cv=none; b=veR5lyJRs/tuowMo85khWZ4LY1NkHbuYLkT7M1Ld2+LW3e0ifvh3eFG1w4KyRd4mQTqyCpA0iUzQ7ZDsnUZ5qlIXBV7G2g81jp56/XxoqI5ITZ2ImtAHTUvzgtDYpOeHV3mJ+QiE3wtPfGSnkz0EVzUsKezmC/Icd7Zk2gFA6co= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1711617831; c=relaxed/simple; bh=sYzxtzfYcGKMRPtgJ86GfNcgchUmaP2u3hb1eoRiHX0=; h=DKIM-Signature:Message-ID:Date:MIME-Version:Subject:To:From; b=IKI2IoIrXqmsYl8knHdI+ga9zEuPFyG2OBzw//M+6eCSGIoYE0WHFfm/kwcbkIbnU4gOTJBU9iClQZygbJ9JzKaVrB2EL9WKdpW2DfoJ0sO5omOP1gDWB9nhlGiqqN/o8rNZNr97k0WsryRtYkuEh3YhsfgJEZg3fWwsyAJgeQ0= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-ej1-x634.google.com with SMTP id a640c23a62f3a-a4e1742d3a3so78349366b.1 for ; Thu, 28 Mar 2024 02:23:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.com; s=google; t=1711617828; x=1712222628; darn=gcc.gnu.org; h=content-transfer-encoding:in-reply-to:autocrypt:from :content-language:references:cc:to:subject:user-agent:mime-version :date:message-id:from:to:cc:subject:date:message-id:reply-to; bh=ahCIVXLaRoYSoFD60LxXD8IQFEjlCgBGVaOOJCNPxY4=; b=TXfp3lw++aVZX6hqAkb5RkMCFkFj2FfWP4sZizSQh2PZcbJUnW00df3NFYVYljLyzl IenSuALbX25/PTo7U/gbwybe8328HaVWlm1m3K1tg1vOz5qwrvN8++2VUdvKanGzdUii itHp0g36Jx1DUoy6VTi5sdkLVmyNBeTiuNqK2ik1TUBVqniCM1tnwEDnQ+5DNW1z0+fr MaiCf0Heu8dJKUu88Z26HJKu1LBvyhpAKMvEvf9HG6Uo/gSbtvmFERGTJcNLt/sbXFlg qFp7J+0/olq6GBlwIOEc5HmSFS7X8daLn6h/GwgKan/RcNChmXsPWQL/ZH9tOh0ultqn sy4A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1711617828; x=1712222628; h=content-transfer-encoding:in-reply-to:autocrypt:from :content-language:references:cc:to:subject:user-agent:mime-version :date:message-id:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=ahCIVXLaRoYSoFD60LxXD8IQFEjlCgBGVaOOJCNPxY4=; b=gu/sgBaJy0OA3+kNpK1Xk+dutpZQ2RKJ20GXZzvqmm59iS4jYNItUp999HZdYu8NOv QMZf4dhKOqNTtILsgJP0WFHQQpFt9pqxM9CkV3uWc7zXdeoL4rxR0osQQ5VVF1MNJBJT 0gfvauPIvhHBg9AOdPERnrqILfFU2mXiFssA77xQ9Dvdva3pFx/mqP2zBy9KA4lPqfEz 0sTPz5WQAykVW6rWRMOMYzjJeHZdiXOSrQgvDL8daproEbFYiwuIbnAgR6xKojlk7+Lw Mx8+F9Fd5SdTLuMNSKKa4JSVshlVs58b6ZLu5qzDyfNHJ/BSEZBZp7MivFZPEOd/av0q O+ww== X-Forwarded-Encrypted: i=1; AJvYcCXOmv0A7byLlskpTYkpssKA4dz0Xc7UcmEQX11hNxoi1sitZTT6aD+CH+tpXUwHI/CS7LFZwe5BpbQi6U8drig= X-Gm-Message-State: AOJu0YwdiDgdG+RBQDSo8QBbfdRUfdQICEHxi1iEiKGpeBz9yqbzXeV/ uhtiFj3x0P0rS2+XA8EZhs57zN5PN8BCA8cCipU5S1/pEUbtaxP4jX1pqbWedQ== X-Google-Smtp-Source: AGHT+IHVGSnEdP400z21KVHYXXBwMCGZCPKB/pjv8SWbt9Xf+5fS2rkLxL2p+r0dUeLHtSWa49WYTQ== X-Received: by 2002:a17:906:4686:b0:a47:3378:48f4 with SMTP id a6-20020a170906468600b00a47337848f4mr1277410ejr.35.1711617827966; Thu, 28 Mar 2024 02:23:47 -0700 (PDT) Received: from [10.156.60.236] (ip-037-024-206-209.um08.pools.vodafone-ip.de. [37.24.206.209]) by smtp.gmail.com with ESMTPSA id n7-20020a170906840700b00a46caa13e67sm521765ejx.105.2024.03.28.02.23.47 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 28 Mar 2024 02:23:47 -0700 (PDT) Message-ID: Date: Thu, 28 Mar 2024 10:23:46 +0100 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: CREL relocation format for ELF To: Fangrui Song Cc: Cary Coutant , binutils@sourceware.org, gcc@gcc.gnu.org References: Content-Language: en-US From: Jan Beulich Autocrypt: addr=jbeulich@suse.com; keydata= xsDiBFk3nEQRBADAEaSw6zC/EJkiwGPXbWtPxl2xCdSoeepS07jW8UgcHNurfHvUzogEq5xk hu507c3BarVjyWCJOylMNR98Yd8VqD9UfmX0Hb8/BrA+Hl6/DB/eqGptrf4BSRwcZQM32aZK 7Pj2XbGWIUrZrd70x1eAP9QE3P79Y2oLrsCgbZJfEwCgvz9JjGmQqQkRiTVzlZVCJYcyGGsD /0tbFCzD2h20ahe8rC1gbb3K3qk+LpBtvjBu1RY9drYk0NymiGbJWZgab6t1jM7sk2vuf0Py O9Hf9XBmK0uE9IgMaiCpc32XV9oASz6UJebwkX+zF2jG5I1BfnO9g7KlotcA/v5ClMjgo6Gl MDY4HxoSRu3i1cqqSDtVlt+AOVBJBACrZcnHAUSuCXBPy0jOlBhxPqRWv6ND4c9PH1xjQ3NP nxJuMBS8rnNg22uyfAgmBKNLpLgAGVRMZGaGoJObGf72s6TeIqKJo/LtggAS9qAUiuKVnygo 3wjfkS9A3DRO+SpU7JqWdsveeIQyeyEJ/8PTowmSQLakF+3fote9ybzd880fSmFuIEJldWxp Y2ggPGpiZXVsaWNoQHN1c2UuY29tPsJgBBMRAgAgBQJZN5xEAhsDBgsJCAcDAgQVAggDBBYC AwECHgECF4AACgkQoDSui/t3IH4J+wCfQ5jHdEjCRHj23O/5ttg9r9OIruwAn3103WUITZee e7Sbg12UgcQ5lv7SzsFNBFk3nEQQCACCuTjCjFOUdi5Nm244F+78kLghRcin/awv+IrTcIWF hUpSs1Y91iQQ7KItirz5uwCPlwejSJDQJLIS+QtJHaXDXeV6NI0Uef1hP20+y8qydDiVkv6l IreXjTb7DvksRgJNvCkWtYnlS3mYvQ9NzS9PhyALWbXnH6sIJd2O9lKS1Mrfq+y0IXCP10eS FFGg+Av3IQeFatkJAyju0PPthyTqxSI4lZYuJVPknzgaeuJv/2NccrPvmeDg6Coe7ZIeQ8Yj t0ARxu2xytAkkLCel1Lz1WLmwLstV30g80nkgZf/wr+/BXJW/oIvRlonUkxv+IbBM3dX2OV8 AmRv1ySWPTP7AAMFB/9PQK/VtlNUJvg8GXj9ootzrteGfVZVVT4XBJkfwBcpC/XcPzldjv+3 HYudvpdNK3lLujXeA5fLOH+Z/G9WBc5pFVSMocI71I8bT8lIAzreg0WvkWg5V2WZsUMlnDL9 mpwIGFhlbM3gfDMs7MPMu8YQRFVdUvtSpaAs8OFfGQ0ia3LGZcjA6Ik2+xcqscEJzNH+qh8V m5jjp28yZgaqTaRbg3M/+MTbMpicpZuqF4rnB0AQD12/3BNWDR6bmh+EkYSMcEIpQmBM51qM EKYTQGybRCjpnKHGOxG0rfFY1085mBDZCH5Kx0cl0HVJuQKC+dV2ZY5AqjcKwAxpE75MLFkr wkkEGBECAAkFAlk3nEQCGwwACgkQoDSui/t3IH7nnwCfcJWUDUFKdCsBH/E5d+0ZnMQi+G0A nAuWpQkjM1ASeQwSHEeAWPgskBQL In-Reply-To: Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-3024.8 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,KAM_INFOUSMEBIZ,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_NONE,TXREP autolearn=no autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On 28.03.2024 08:43, Fangrui Song wrote: > On Fri, Mar 22, 2024 at 6:51 PM Fangrui Song wrote: >> >> On Thu, Mar 14, 2024 at 5:16 PM Fangrui Song wrote: >>> >>> The relocation formats REL and RELA for ELF are inefficient. In a >>> release build of Clang for x86-64, .rela.* sections consume a >>> significant portion (approximately 20.9%) of the file size. >>> >>> I propose RELLEB, a new format offering significant file size >>> reductions: 17.2% (x86-64), 16.5% (aarch64), and even 32.4% (riscv64)! >>> >>> Your thoughts on RELLEB are welcome! >>> >>> Detailed analysis: >>> https://maskray.me/blog/2024-03-09-a-compact-relocation-format-for-elf >>> generic ABI (ELF specification): >>> https://groups.google.com/g/generic-abi/c/yb0rjw56ORw >>> binutils feature request: https://sourceware.org/bugzilla/show_bug.cgi?id=31475 >>> LLVM: https://discourse.llvm.org/t/rfc-relleb-a-compact-relocation-format-for-elf/77600 >>> >>> Implementation primarily involves binutils changes. Any volunteers? >>> For GCC, a driver option like -mrelleb in my Clang prototype would be >>> needed. The option instructs the assembler to use RELLEB. >> >> The format was tentatively named RELLEB. As I refine the original pure >> LEB-based format, “RELLEB” might not be the most fitting name. >> >> I have switched to SHT_CREL/DT_CREL/.crel and updated >> https://maskray.me/blog/2024-03-09-a-compact-relocation-format-for-elf >> and >> https://groups.google.com/g/generic-abi/c/yb0rjw56ORw/m/eiBcYxSfAQAJ >> >> The new format is simpler and better than RELLEB even in the absence >> of the shifted offset technique. >> >> Dynamic relocations using CREL are even smaller than Android's packed >> relocations. >> >> // encodeULEB128(uint64_t, raw_ostream &os); >> // encodeSLEB128(int64_t, raw_ostream &os); >> >> Elf_Addr offsetMask = 8, offset = 0, addend = 0; >> uint32_t symidx = 0, type = 0; >> for (const Reloc &rel : relocs) >> offsetMask |= crels[i].r_offset; >> int shift = std::countr_zero(offsetMask) >> encodeULEB128(relocs.size() * 4 + shift, os); >> for (const Reloc &rel : relocs) { >> Elf_Addr deltaOffset = (rel.r_offset - offset) >> shift; >> uint8_t b = deltaOffset * 8 + (symidx != rel.r_symidx) + >> (type != rel.r_type ? 2 : 0) + (addend != rel.r_addend ? 4 : 0); >> if (deltaOffset < 0x10) { >> os << char(b); >> } else { >> os << char(b | 0x80); >> encodeULEB128(deltaOffset >> 4, os); >> } >> if (b & 1) { >> encodeSLEB128(static_cast(rel.r_symidx - symidx), os); >> symidx = rel.r_symidx; >> } >> if (b & 2) { >> encodeSLEB128(static_cast(rel.r_type - type), os); >> type = rel.r_type; >> } >> if (b & 4) { >> encodeSLEB128(std::make_signed_t(rel.r_addend - addend), os); >> addend = rel.r_addend; >> } >> } >> >> --- >> >> While alternatives like PrefixVarInt (or a suffix-based variant) might >> excel when encoding larger integers, LEB128 offers advantages when >> most integers fit within one or two bytes, as it avoids the need for >> shift operations in the common one-byte representation. >> >> While we could utilize zigzag encoding (i>>31) ^ (i<<1) to convert >> SLEB128-encoded type/addend to use ULEB128 instead, the generate code >> is inferior to or on par with SLEB128 for one-byte encodings. > > > We can introduce a gas option --crel, then users can specify `gcc > -Wa,--crel a.c` (-flto also gets -Wa, options). > > I propose that we add another gas option --implicit-addends-for-data > (does the name look good?) to allow non-code sections to use implicit > addends to save space > (https://sourceware.org/PR31567). > Using implicit addends primarily benefits debug sections such as > .debug_str_offsets, .debug_names, .debug_addr, .debug_line, but also > data sections such as .eh_frame, .data., .data.rel.ro, .init_array. > > -Wa,--implicit-addends-for-data can be used on its own (6.4% .o > reduction in a clang -g -g0 -gpubnames build) And this option will the switch from RELA to REL relocation sections, effectively in violation of most ABIs I'm aware of? Furthermore, why just data? x86 at least could benefit almost as much for code. Hence maybe better --implicit-addends=data, with an option for architectures to also permit --implicit-addends=text. Jan > or together with > CREL to achieve more incredible size reduction, one single byte for > most .debug_* relocations! > With CREL, concerns of debug section relocations will become a thing > of the past.