This article describes an interesting overflow bug in the ELF hashfunction.The System V Application Binary Interface (generic ABI) specifies theELF object file format. When producing an executable or shared objectfile needing a dynamic symbol table (.dynsym), a linkergenerates a.hashsection with typeSHT_HASHto hold a symbolhash table. ADT_HASHtag is produced to hold theaddress of.hash.The hash table is used by a dynamic loader to perform symbol lookup(for dynamic relocations anddlsymfamily functions). Adetailed description of the format can be found in ELF: symbol lookup viaDT_HASH.Other use c ...继续阅读 (82)

This article describes an interesting overflow bug in the ELF hashfunction.The System V Application Binary Interface (generic ABI) specifies theELF object file format. When producing an output executable or sharedobject needing a dynamic symbol table (.dynsym), a linkergenerates a.hashsection with typeSHT_HASHto hold a symbolhash table. ADT_HASHtag is produced to hold theaddress of.hash.DT_HASHis used by a dynamic loader to perform symbollookup (for dynamic relocations anddlsymfamilyfunctions). A detailed description of the format can be found in ELF: symbol lookup viaDT_HASH.Other use casesIn ...继续阅读 (79)

A control-flow graph (CFG) is a graph representation of all pathsthat might be traversed through a program during its execution.Control-flow integrity (CFI) refers to security policy dictating thatprogram execution must follow a control-flow graph. This articledescribes some features that compilers and hardware can use to enforceCFI, with a focus on llvm-project implementations.CFI schemes are typically divided into forward-edge (e.g. indirectcalls) and backward-edge (mainly function returns). It should be notedthat exception handling and symbol interposition are not included inthese categorie ...继续阅读 (92)

UndefinedBehaviorSanitizer(UBSan) is an undefined behavior detector for C/C++. It consists of codeinstrumentation and a runtime. Both components have multiple independentimplementations.Clang implementedthe first few checks in 2009-12, initially named-fcatch-undefined-behavior. In 2012-fsanitize=undefinedwas added and-fcatch-undefined-behaviorwas removed.GCC 4.9 implemented-fsanitize=undefinedin 2013-08.The runtime used by Clang lives inllvm-project/compiler-rt/lib/ubsan. GCC from time to timesyncs its downstream fork of the sanitizers part of compiler-rt(libsanitizer). The end of the article ...继续阅读 (91)

llvm-project 16 was just released. I added some lld/ELF notes to https://github.com/llvm/llvm-project/blob/release/16.x/lld/docs/ReleaseNotes.rst.Here I will elaborate on some changes.Link speed improved greatly compared with lld 15.0. Notably inputsection initialization and relocation scanning are now parallel. (D130810) (D133003)ELFCOMPRESS_ZSTDcompressed input sections are nowsupported. (D129406)--compress-debug-sections=zstdis now available tocompress debug sections with zstd (ELFCOMPRESS_ZSTD). (D133548)--no-warnings/-wis now available tosuppress warnings. (D136569)DT_RISCV_VARIANT_CCis n ...继续阅读 (87)

llvm-project 16 was just released. I added some lld/ELF notes to https://github.com/llvm/llvm-project/blob/release/16.x/lld/docs/ReleaseNotes.rst.Here I will elaborate on some changes.Link speed improved greatly compared with lld 15.0. Notably inputsection initialization and relocation scanning are now parallel. (D130810) (D133003)ELFCOMPRESS_ZSTDcompressed input sections are nowsupported. (D129406)--compress-debug-sections=zstdis now available tocompress debug sections with zstd (ELFCOMPRESS_ZSTD). (D133548)--no-warnings/-wis now available tosuppress warnings. (D136569)DT_RISCV_VARIANT_CCis n ...继续阅读 (80)

This article describes target-specific details about x86 in ELFlinkers. I will use "x86" to refer to both x86-32 and x86-64.Global Offset TableThe Global Offset Table consists of two sections:.got.pltholds code addresses for PLT..gotholds other addresses and offsets.The symbol_GLOBAL_OFFSET_TABLE_is defined at thebeginning of the.got.pltsection..got.plthas 3 reserved entries..got.plt[0]holds the link-time address of_DYNAMICfor a legacy reason. Versions of glibc prior to2.35 have the_DYNAMICrequirement. See Allabout Global Offset Table..got.plt[1]and.got.plt[2]are for lazybinding PLT. Linkers c ...继续阅读 (82)

GCC supports some function attributes for function multi-versioning:a way for a function to have multiple implementations, each using adifferent set of ISA extensions. A function attribute specifiesdifferent requirements of ISA extensions. The generated program decodesthe CPU model and features at run-time, and picks the most restrictiveimplementation that is satisfied by the CPU, assuming that the mostrestrictive implementation has the best performance.__attribute__((target(...)))__attribute__((target(...)))has been available for along time, even before attributes for function multi-versionin ...继续阅读 (73)

This article describes target-specific details about Power ISA in ELFlinkers. Initially there was IBM POWER. The 1991 Apple–IBM–Motorolaalliance created PowerPC. In 2006, the architecture was rebranded asPower ISA. According to the ISA manual, "In 2006, Freescale and IBMcollaborated on the creation of the Power ISA Version 2.03, whichrepresented the reunification of the architecture by combining Book Econtent with the more general purpose PowerPC Version 2.02."The terms "PowerPC" and "powerpc" remain popular in numerous places,including thepowerpc-*-*-*andpowerpc64-*-*-*in official target trip ...继续阅读 (73)

This article describes target-specific details about AArch64 in ELFlinkers. AArch64 is the 64-bit execution environment for the Armarchitecture.ABI documentsELFfor the Arm® 64-bit Architecture (AArch64)SystemV ABI for the Arm® 64-bit Architecture (AArch64)Global Offset TableThe Global Offset Table consists of two sections:.got.pltholds code addresses for PLT..gotholds other addresses and offsets.The symbol_GLOBAL_OFFSET_TABLE_is defined at thebeginning of the.gotsection. GNU ld reserves a singleentry for.gotand.got[0]holds the link-timeaddress of_DYNAMICfor a legacy reason Versions of glibcpri ...继续阅读 (76)

UNDER CONSTRUCTIONThis article describes target-specific things about Power ISA in ELFlinkers. The architecture was originally named "PowerPC". In 2016 thearchitecture was rebranded as "Power ISA". The ISA manual says: "In2006, Freescale and IBM collaborated on the creation of the Power ISAVersion 2.03, which represented the reunification of the architecture bycombining Book E content with the more general purpose PowerPC Version2.02."The terms "PowerPC" and "powerpc" remain popular in numerous places,including thepowerpc-*-*-*andpowerpc64-*-*-*in official target triple names. Theabbreviation ...继续阅读 (79)

This article describes target-specific things about x86 in ELFlinkers. I will use "x86" to refer to both x86-32 and x86-64.Global Offset Table_GLOBAL_OFFSET_TABLE_is defined at the start of thesection.got.plt..got.plthas 3 reservedentries._GLOBAL_OFFSET_TABLE_[0]stores the link-time address of_DYNAMICfor a legacy reason. It's unused now. See Allabout Global Offset Table._GLOBAL_OFFSET_TABLE_[1]and_GLOBAL_OFFSET_TABLE_[2]are for lazy binding PLT.GOT optimizationSee Allabout Global Offset Table#GOT optimization.Procedure Linkage TableRetpoline and IndirectBranch Trackingld.lld supports-z retpoli ...继续阅读 (76)

Clang andGCC 4.9implemented LeakSanitizer in 2013. LeakSanitizer(LSan) is a memory leak detector. It intercepts memory allocationfunctions and by default detects memory leaks atatexittime. The implementation is purely in the runtime(compiler-rt/lib/lsan) and no instrumentation isneeded.LSan has very little architecture-specific code and supports many64-bit targets. Some 32-bit targets (e.g. Linux arm/x86-32) aresupported as well, but there may be high false negatives becausepointers with fewer bits are more easily confused with integers/floatingpoints/other data of a similar pattern. Every sup ...继续阅读 (74)

Clang andGCC 4.9implemented LeakSanitizer in 2013. LeakSanitizer(LSan) is a memory leak detector. It intercepts memory allocationfunctions and by default detects memory leaks atatexittime. The implementation is purely in the runtime(compiler-rt/lib/lsan) and no instrumentation isneeded.LSan has very little architecture-specific code and supports many64-bit targets. Some 32-bit targets (e.g. Linux arm/x86-32) aresupported as well, but there may be high false negatives because of thesmall pointer size. Every supported operating system needs to providesome way to "stop the world".UsageLSan can be ...继续阅读 (71)

Many sanitizers want to know every function in the program. Userfunctions are instrumented and therefore known by the sanitizer runtime.For library functions, some (e.g. mmap, munmap, memoryallocation/deallocation functions, longjmp, vfork) need specialtreatment. Sanitizers leverage symbol interposition to redirect suchfunction calls to its own implementation: interceptors. Other libraryfunctions can be treated as normal user code. Either instrumenting thefunction or providing an interceptor is fine.In some cases instrumenting is infeasible:Assembly source files usually do not (or are inconven ...继续阅读 (78)

GCC supports some function attributes for function multi-versioning:a way for a function to have multiple implementations, each using adifferent set of ISA extensions. A function attribute specifiesdifferent requirements of ISA extensions. The generated program decodesthe CPU model and features at run-time, and picks the most restrictiveimplementation which is satisfied by the CPU, assuming that the mostrestrictive implementation has the best performance.__attribute__((target(...)))__attribute__((target(...)))has been available for along time, even before attributes for function multi-versioni ...继续阅读 (75)

UndefinedBehaviorSanitizer(UBSan) is a undefined behavior detector for C/C++. It consists of acode instrumentation and a runtime (inllvm-project/compiler-rt).Clang and GCC have independent implementations. Clang implementedthe instrumentation first in 2009-12, initially named-fcatch-undefined-behavior. GCC 4.9 implemented-fsanitize=undefinedin 2013-08.Available checksThere are many undefined behavior checkswhich can be detected. One may specify-fsanitize=xxxwherexxx is the name of the check individually, or more commonly, specify-fsanitize=undefinedto enable all of them.Some checks are not und ...继续阅读 (70)

Many sanitizers want to know every function in the program. User functions are instrumented and therefore known by the sanitizer runtime. For library functions, some (e.g. mmap, munmap, memory allocation/deallocation functions, longjmp, vfork) need special treatment. Sanitizers leverage symbol interposition to redirect such function calls to its own implementation: interceptors. Other library functions can be treated as normal user code. Either instrumenting the function or providing an interceptor is fine. In some cases instrumenting is infeasible (e.g.When can glibc be built with Clang?) or ...继续阅读 (78)

一如既往，主要在工具链领域耕耘。给这些high-profileOSS贡献的时候，希望透过这个微小的角度改变世界。HighlightsRELR relative relocation format (glibc, musl, DynamoRIO)zstd compressed debug sections (binutils, gdb, clang, lld/ELF,lldb)lld/ELF (huge performance improvement, RISC-V linker relaxation,SHT_RISCV_ATTRIBUTES)Clang built glibc (get the ball rolling)Make protected symbols work in binutils/glibcInvolved in sanitizers, ThinLTO, AArch64/x86 hardening features,AArch64 Memtag ABI, RISC-V psABI, etcRELR relative relocationformat(In 2021-10, upstreamedDT_RELRpatch to FreeBSDrtld-elf)In April, upstreamedDT_RELRpatch to glibc(highlighted f ...继续阅读 (76)

一如既往，主要在工具链领域耕耘。HighlightsRELR relative relocation format (glibc, musl, DynamoRIO)zstd compressed debug sections (binutils, gdb, clang, lld/ELF, lldb)lld/ELF (huge performance improvement, RISC-V linker relaxation,SHT_RISCV_ATTRIBUTES)Clang built glibc (get the ball rolling)Make protected symbols work in binutils/glibcInvolved in sanitizers, ThinLTO, AArch64/x86 hardening features, AArch64 Memtag ABI, RISC-V psABI, etcRELR relative relocation format(In 2021-10, upstreamedDT_RELRpatch to FreeBSD rtld-elf)In April, upstreamedDT_RELRpatch to glibc (highlighted feature for the 2.36 release)In Augu ...继续阅读 (70)

本文总结经典的区间第k小值数据结构题。给定一个长为n的数组，元素为范围为[0,σ)的整数。有m个询问：求区间[l,r)中第k小的元素。一些方法支持扩展问题：有m个操作，或者修改某个位置上的元素，或者询问区间[l,r)中第k小的元素。描述位置区间的线段树/Fenwicktree归并树(merge sorttree)用O(n*log(n))时间构建线段树，每个节点描述一个位置区间。一个节点存储对应区间的有序数组。对于一个询问，二分搜索答案ans转化为计数问题：区间[l,r)内小于ans的元素个数是否大于等于k。对于这个计数问题，把区间[l,r)解构为不超过log(n)个线段树节点。对于每个节点，二分查找这个节点存储的有序数组里小于ans的元素数。区间计数支持区间减法，因此外层的线段树也可改成Fenwicktree，减少一半节点。 外层线段树还可以改成块状链表(unrolled linkedlist)，但只在增删元素的扩展问题上才有用(如洛谷P4278带插入区间K小值)。二分搜索答案需要在每个解构的线段树/Fenwicktree区间上进行。查询一个区间的二分搜索无法加速查询下一个区间，因而影响了时间复杂度。static:O(n*log(n)+m*log(n)^2*log(σ)), spacecomplexity:O(n*log(n)), not recommended如果所有Fenwic ...继续阅读 (69)

UNDER CONSTRUCTION.本文总结经典的区间第k小值数据结构题。 给定一个长为n的数组。有m个询问：求区间[l,r)中第k小的元素。一些方法支持扩展问题：有m个操作，或者修改某个位置上的元素，或者询问区间[l,r)中第k小的元素。归并树(merge sort tree)用O(n*log(n))时间构建线段树，每个节点存储对应区间的有序数组。 对于一个询问，二分搜索答案ans转化为计数问题：区间[l,r)内小于ans的元素个数是否大于等于k。 对于这个计数问题，把区间[l,r)解构为不超过log(n)个线段树节点。对于每个节点，二分查找这个节点存储的有序数组里小于ans的元素数。static:O(n*log(n)+m*log(n)^3), space complexity:O(n*log(n)), not recommended若要支持修改元素，把每个节点存储的有序数组改成一棵binary search tree，这种嵌套树形解构俗称树套树。描述值域的线段树用O(n*log(n))时间构建一棵线段树，每个节点描述一个值域区间，存储出现的元素的位置序列。 对于静态问题，位置序列可以是一个有序数组。若要支持修改元素，位置序列得是线段树或binary search tree。询问使用的区间查询支持区间减法，因此外层的线段树也可改成Fenwick tree，减少一半节点。stat ...继续阅读 (72)

UNDER CONSTRUCTION.本文总结经典的区间第k小值数据结构题。 给定一个长为n的数组。有m个询问：求区间[l,r)中第k小的元素。一些方法支持扩展问题：有m个操作，或者修改某个位置上的元素，或者询问区间[l,r)中第k小的元素。归并树(merge sort tree)用O(n*log(n))时间构建线段树，每个节点存储对应区间的有序数组。 对于一个询问，二分搜索答案ans转化为计数问题：区间[l,r)内小于ans的元素个数是否大于等于k。 对于这个计数问题，把区间[l,r)解构为不超过log(n)个线段树节点。对于每个节点，二分查找这个节点存储的有序数组里小于ans的元素数。static:O(n*log(n)+m*log(n)^3), space complexity:O(n*log(n)), not recommended若要支持修改元素，把每个节点存储的有序数组改成一棵binary search tree，这种嵌套树形解构俗称树套树。描述值域的线段树用O(n*log(n))时间构建一棵线段树，每个节点描述一个值域区间，存储出现的元素的位置序列。 对于静态问题，位置序列可以是一个有序数组。若要支持修改元素，位置序列得是线段树或binary search tree。static:O(n*log(n)+m*log(n)^2), space complexity:O(n* ...继续阅读 (79)

UNDER CONSTRUCTIONControl-flow integrity (CFI) refers to techniques which prevent control-flow hijacking attacks. This article describes some compiler/hardware features with a focus on llvm-project implementations.CFI commonly divided into forward-edge CFI (e.g. indirect calls) and backward-edge CFI (e.g. function returns). AIUI exception handling and symbol interposition are not categorized.Let's start with backward-edge CFI. Fine-grained technologies check that a return address refers to a possible caller. This is unimplemented and the additional guarantee is possibly less useful.Coarse tech ...继续阅读 (73)

UNDER CONSTRUCTIONRepository:https://sourceware.org/git/gitweb.cgi?p=glibc.gitWiki:https://sourceware.org/glibc/wiki/Bugzilla:https://sourceware.org/bugzilla/Mailing lists:{libc-announce,libc-alpha,libc-locale,libc-stable,libc-help}@sourceware.orgPatchwork:https://patchwork.sourceware.org/project/glibc/list/Patch Review WorkflowContribution Checklist:https://sourceware.org/glibc/wiki/Contribution%20checklistBuild bots:https://builder.sourceware.org/buildbot/#/builders, search "glibc"public inbox:https://inbox.sourceware.org/libc-alpha/glibc is an implementation of the user-space side ...继续阅读 (70)

UNDER CONSTRUCTIONRepository:https://sourceware.org/git/gitweb.cgi?p=glibc.gitWiki:https://sourceware.org/glibc/wiki/Bugzilla:https://sourceware.org/bugzilla/Mailing lists:{libc-announce,libc-alpha,libc-locale,libc-stable,libc-help}@sourceware.orgPatchwork:https://patchwork.sourceware.org/project/glibc/list/Patch Review WorkflowContribution Checklist:https://sourceware.org/glibc/wiki/Contribution%20checklistBuild bots:https://builder.sourceware.org/buildbot/#/builders, search "glibc"public inbox:https://inbox.sourceware.org/libc-alpha/glibc is an implementation of the user-space side ...继续阅读 (72)

In GNU ld,-rproduces a relocatable object file. This is known as relocatable linking or partial linking. This mode suppresses many passes done for an executable or shared object output (in-no-pie/-pie/-sharedmodes).-r,-no-pie,-pie, and-sharedspecify 4 different modes. The 4 options are mutually exclusive.The relocatable output can be used for analysis and binary manipulation. Then, the output can be used to link the final executable or shared object.123456clang -pie a.o b.o# ==>clang -r a.o b.o -o r.oclang -pie r.oLet's go through various linker passes and see how relocatable linking changes t ...继续阅读 (71)

In GNU ld,-rproduces a relocatable object file. This is known as relocatable linking or partial linking. This mode suppresses many passes done for an executable or shared object output (in-no-pie/-pie/-sharedmodes).-r,-no-pie,-pie, and-sharedspecify 4 different modes. The 4 options are mutually exclusive.The relocatable output can be used for analysis and binary manipulation. Then, the output can be used to link the final executable or shared object.123456clang -pie a.o b.o# ==>clang -r a.o b.o -o r.oclang -pie r.oLet's go through various linker passes and see how relocatable linking changes t ...继续阅读 (70)

This article describes someClang header modulesfeatures which apply to#include. They enforce a more explicit dependency graph. Strict dependency information provides documentation purposes and makes refactoring convenient.Include What You Usedescribes the benefits of clean header inclusions well, so I will not repeat it here.When C++20 modules are used, the features apply to#includein a global module fragment (module;) but have no effect for import declarations.Layering check-fmodules-decluseFor a#includedirective, this option emits an error if the following conditions are satisfied (seeclang/ ...继续阅读 (76)

This article describes someClang header modulesfeatures which apply to#include. They enforce a more explicit dependency graph. Strict dependency information provides documentation purposes and makes refactoring convenient.Include What You Usedescribes the benefits of clean header inclusions well, so I will not repeat it here.When C++20 modules are used, the features apply to#includein a global module fragment (module;) but have no effect for import declarations.Layering check-fmodules-decluseFor a#includedirective, this option emits an error if the following conditions are satisfied (seeclang/ ...继续阅读 (73)