<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Yonatan Goldschmidt on Medium]]></title>
        <description><![CDATA[Stories by Yonatan Goldschmidt on Medium]]></description>
        <link>https://medium.com/@yon.goldschmidt?source=rss-15275be2a0a0------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*C3rgW3kzCvIsw_Dq.jpg</url>
            <title>Stories by Yonatan Goldschmidt on Medium</title>
            <link>https://medium.com/@yon.goldschmidt?source=rss-15275be2a0a0------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 04:55:15 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@yon.goldschmidt/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Dynamic ftrace filtering]]></title>
            <link>https://medium.com/granulate/dynamic-ftrace-filtering-dececfc3eced?source=rss-15275be2a0a0------2</link>
            <guid isPermaLink="false">https://medium.com/p/dececfc3eced</guid>
            <category><![CDATA[linux]]></category>
            <category><![CDATA[linux-commands]]></category>
            <category><![CDATA[linux-kernel]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[linux-tutorial]]></category>
            <dc:creator><![CDATA[Yonatan Goldschmidt]]></dc:creator>
            <pubDate>Tue, 22 Sep 2020 08:41:40 GMT</pubDate>
            <atom:updated>2020-09-22T08:41:40.218Z</atom:updated>
            <content:encoded><![CDATA[<h4>If you’ve ever inspected a running Linux kernel, you probably heard of ftrace. It’s an amazing tool for tracing flows and events in the kernel, and it is very versatile — but what if it doesn’t support your use-case?</h4><h4>By: Yonatan Goldschmidt</h4><p>Recently, while conducting research, I wanted to follow a specific kernel code flow: I was about to modify the behavior of an existing kernel mechanism, and I needed to understand the flow of data between different functions.</p><p>As with any open source project you’re trying to analyze, your go-to assistant is the source code. Linux, besides being open source, provides tons of <em>dynamic</em> tools for debugging, and they are a great supplement to static reading of the code. In this post, I’ll focus on one of these tools, <em>ftrace</em>, and present a modification I made to make its filtering capabilities more versatile.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*snnZLZ_ocZqXtSTnxxrB1A.png" /></figure><h4>ftrace</h4><p>At its base, ftrace (Function Tracer) is a <em>dynamic function instrumentation infrastructure.</em> It can be used to set dynamic traces on virtually all kernel functions, and also supports a large set of static tracepoints, used to record core kernel events. It is available in most modern Linux distributions.</p><p>It’s a powerful tool for tracing flows and events in the kernel. Providing both in-kernel API and usermode control interface via tracefs, it’s arguably one of the most comprehensive tracing tools in Linux.</p><p>ftrace has many modes of operation, in this post I’ll focus on the function_graph mode: It allows you to record the call graph originating from a given function, recursively.</p><p>In case you’ve never used it (or just as a slight reminder) — here’s how it looks when tracing the kernel path for a vfs_read call on /proc/version:</p><pre>  8)               |  vfs_read() {<br>  8)               |    rw_verify_area() {<br>  8)               |      security_file_permission() {<br>  8)               |        apparmor_file_permission() {<br>  8)               |          common_file_perm() {<br>  8)   0.110 us    |            aa_file_perm();<br>  8)   0.322 us    |          }<br>  8)   0.483 us    |        }<br>  8)   0.079 us    |        __fsnotify_parent();<br>  8)   0.082 us    |        fsnotify();<br>  8)   1.004 us    |      }<br>  8)   1.180 us    |    }<br>  8)               |    __vfs_read() {<br>  8)               |      proc_reg_read() {<br>  8)               |        seq_read() {<br>  8)   0.106 us    |          rcu_all_qs();<br>  8)               |          kvmalloc_node() {<br>  8)               |            __kmalloc_node() {<br>  8)   0.099 us    |              kmalloc_slab();<br>  8)   0.086 us    |              rcu_all_qs();<br>  8)   0.098 us    |              should_failslab();<br>  8)   0.128 us    |              memcg_kmem_get_cache();<br>  8)   0.092 us    |              memcg_kmem_put_cache();<br>  8)   1.562 us    |            }<br>  8)   1.743 us    |          }<br>  8)   0.089 us    |          single_start();<br>  8)               |          <strong>version_proc_show</strong>() {<br>  8)               |            seq_printf() {<br>  8)   0.836 us    |              seq_vprintf();<br>  8)   1.004 us    |            }<br>  8)   1.158 us    |          }<br>....</pre><p>That call graph can provide great aid in understanding flow, alongside reading the code.</p><p><em>This isn’t a starters guide for ftrace, so I will assume you know its basics from this point onward. If you want a longer introduction on ftrace and its additional modes, I recommend reading the articles in [1], [2] and [3].</em></p><p>Back here, I was trying to understand the receive flow of a specific TCP packet (which functions does it go through).</p><p>The TCP receive entry-point function is <a href="https://elixir.bootlin.com/linux/v5.0/source/net/ipv4/tcp_ipv4.c#L1781">tcp_v4_rcv</a>. We can function_graph it, but we’ll soon encounter a problem — there are <strong>heaps</strong> of data generated by graph-tracing this function: On my desktop, under a not-so-heavy network load, I was getting a 5MB/s trace file! That’s a lot of data.</p><p>There are 2 limitations pointed out here:</p><ol><li>The calls didn’t undergo any filtering — all calls were written to the trace file. I wanted to see the graph of tcp_v4_rcv on a specific packet, not on all TCP packets processed by the system.</li><li>There’s no information attached to the calls (for example, function arguments). Take a look on the sample graph above — there are only function names and durations. How can we differentiate the “interesting” calls?</li></ol><h4>Existing filters?</h4><p>Let’s seek help from existing ftrace features. For this purpose, we can start with the <a href="https://www.kernel.org/doc/Documentation/trace/ftrace.txt">very long documentation</a>.</p><p>ftrace can record the current PID/TGID and the command (/proc/pid/comm), and report them in the trace file. As far as I can tell, no more specific details are available to be recorded on each entry.</p><p>ftrace also supports <strong>filtering</strong> by PID: Using the set_ftrace_pid file, we can limit the traced calls to specific processes. For example, this will limit traces to the init process:</p><pre># cd /sys/kernel/tracing<br># echo 1 &gt; set_ftrace_pid</pre><p>Sounds nice, eh? For many filtering use-cases, this is just enough: A simple program that writes its PID to set_ftrace_pid and then invokes some kernel code you wish to trace.</p><p>In the network RX case, it’s impossible⁴: Network packets are processed in <em>software interrupts⁵</em> running possibly on any CPU, in the context of virtually any thread of the system. There goes filtering by PID…</p><p>I’m not aware of any other sophisticated filters allowed by ftrace. We can try to filter out the events externally (e.g in the case of network RX — filter away unwanted packets with iptables, this way they won’t end up in tcp_v4_rcv)…</p><p>… or, we can tweak ftrace to provide the filtering we need!</p><h4>Tweaking ftrace’s filtering</h4><p><em>All following Linux references are based on kernel 5.0+.</em></p><p>What I had in mind: ftrace has its PID-based filtering. I can provide external filtering, and after a call, I wish to trace passes my filter, the PID of the currently running process can be “added” to set_ftrace_filter, effectively making the process traced (and I’ll get the call graph I desired)</p><p>What happens when you write to set_ftrace_pid? A quick search of this string yields <a href="https://elixir.bootlin.com/linux/v5.0/source/kernel/trace/ftrace.c#L6593">ftrace_init_tracefs</a> which registers the tracefs file; And <a href="https://elixir.bootlin.com/linux/v5.0/source/kernel/trace/ftrace.c#L6526">ftrace_pid_write</a> actually implements the write.</p><p>ftrace_pid_write is rather long for its seemingly simple purpose. Summing it up, this function does 3 things:</p><ol><li>Creates a trace_pid_list struct from the input PIDs (you can write multiple PIDs for tracing), and stores it for later use.</li><li>Registers a sched_switch event handler called <a href="https://elixir.bootlin.com/linux/v5.0/source/kernel/trace/ftrace.c#L6336">ftrace_filter_pid_sched_switch_probe</a>.</li><li>Updates tracers that use PID filtering to have <a href="https://elixir.bootlin.com/linux/v5.0/source/kernel/trace/ftrace.c#L146">ftrace_pid_func</a> as their tracing handler.</li></ol><p>Effectively, the 3rd step enables filtering. ftrace_pid_func is very simple: It is called instead of the original tracing handler and checks whether the current task should be traced or not, by reading tr-&gt;trace_buffer.data-&gt;ftrace_ignore_pid. If (and only if) tracing should be performed, it calls the original handler.</p><p>Let’s see where this field is updated. ftrace_pid_write has previously registered ftrace_filter_pid_sched_switch_probe for the sched_switch event. This handler will be called <em>for each task switch in the system.</em> It knows which is the next task to run.</p><pre>static void<br>ftrace_filter_pid_sched_switch_probe(void *data, bool preempt,<br>                                     struct task_struct *prev, struct task_struct *next)<br>{<br>    struct trace_array *tr = data;<br>    struct trace_pid_list *pid_list;</pre><pre>    pid_list = rcu_dereference_sched(tr-&gt;function_pids);</pre><pre>    this_cpu_write(tr-&gt;trace_buffer.data-&gt;ftrace_ignore_pid,<br>            trace_ignore_this_task(pid_list, next));<br>}</pre><p>It calls <a href="https://elixir.bootlin.com/linux/v5.0/source/kernel/trace/trace.c#L354">trace_ignore_this_task</a> to see whether the new task’s PID was marked for tracing:</p><pre>bool<br>trace_ignore_this_task(struct trace_pid_list *filtered_pids, struct task_struct *task)<br>{<br>   /*<br>    * Return false, because if filtered_pids does not exist,<br>    * all pids are good to trace.<br>    */<br>    if (!filtered_pids)<br>        return false;</pre><pre>    return !trace_find_filtered_pid(filtered_pids, task-&gt;pid);<br>}</pre><p>The result is written into the ftrace_ignore_pid field, itself a percpu⁶ variable. This is a caching optimization: instead of filtering PIDs through the list whenever a task hits a traced function, the check of a PID is done <strong>once</strong> on task switch, and later the tracing decision is a mere cache read of this single boolean. Neat, and a very nice use of percpu as well! The result will be automatically invalidated upon the next call to ftrace_filter_pid_sched_switch_probe, which will write a new value for the next task.</p><p>I think we know enough. If we can update the percpu ftrace_ignore_pid, we can control whether tracing is enabled for the current CPU. If we can set it once we want to start tracing and unset it once we want to stop, we can use it to limit filtering at will.</p><p>So, I started writing a kernel module to work this out on my test machine. Shortly enough, I recalled I worked on a MicroPython port for the Linux kernel⁷ just for such occasions! Using it, we can quickly define a few hooks that’ll do the job.</p><p>Our goal: given an input TCP packet that matches a precondition (say, destination port is 9000) we’d like to get its ftrace call-graph of tcp_v4_rcv.</p><p>We’ll start with a hook that’ll do the actual filtering on the packets. It has to be called <em>before </em>ftrace-graph, otherwise, we won’t be able to control the filtering! If I hook tcp_v4_rcv itself with ftrace, it runs after the ftrace-graph filtering decision, which is too late for us. I’m sure there’s a way around it, but I didn’t bother checking — instead, I hooked the tcp_protocol-&gt;handler pointer, which is used to call tcp_v4_rcv. This way, we’re surely called before it.</p><pre>def my_pre_tcp_v4_rcv(skb):<br>    # TODO: do the filtering stuff...<br>    return tcp_v4_rcv(skb)</pre><pre>cb = callback(my_pre_tcp_v4_rcv)<br>net_protocol_s = partial_struct(&quot;net_protocol&quot;)<br>net_protocol_s(tcp_protocol).handler = cb.ptr()</pre><p>At this point, we have the sk_buff and we can make the tracing decision. If we wish to trace, we can write to tr-&gt;trace_buffer.data-&gt;ftrace_ignore_pid… Which is not in the exported headers, sadly.</p><p>I wanted this to be fully compatible with standard kernel headers, so accessing unexported structs is a bad idea. A workaround is to hook trace_ignore_this_task with a simple handler that returns 1 only for our traced task. Then we can call ftrace_filter_pid_sched_switch_probe, as if a scheduler switch has happened. It will update the tracing status for the current task — and since we forced trace_ignore_this_task() to return 1, the current task will be marked for tracing.</p><pre>traced_task = None</pre><pre>def my_trace_ignore_this_task(orig, filtered_pids, task):<br>    return 0 if task == trace_task else 1</pre><pre>kp = kprobe(&quot;trace_ignore_this_task&quot;, KP_ARGS_MODIFY, my_trace_ignore_this_task)</pre><pre>def my_pre_tcp_v4_rcv(skb):<br>    global trace_task<br>    # insert filtering here ...<br>    # to enable tracing:<br>    trace_task = current()<br>    ftrace_filter_pid_sched_switch_probe(global_trace, False, None, current())<br>    return tcp_v4_rcv(skb)</pre><p>Funny anecdote: ftrace won’t allow placing hooks on ftrace own code (such as trace_ignore_this_task). But you <em>can</em> place kprobe hooks, which are sometimes backed by ftrace, but in this case, it’s useful they are not :)</p><p>Using these 2 hooks, I can enable filtering based on the input sk_buff. The final snippet is available here:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/48df1284d15a87bb00aaf13e645047f4/href">https://medium.com/media/48df1284d15a87bb00aaf13e645047f4/href</a></iframe><p>It can be pasted into the Python shell (in paste mode) to enable the hooks. Finally, to start tracing we’ll do the following:</p><pre># cd /sys/kernel/tracing<br># echo 2 &gt; set_ftrace_pid<br># echo tcp_v4_rcv &gt; set_graph_function<br># echo function_graph &gt; current_tracer</pre><p>2 is the PID of kthreadd — we need to write <em>something</em> into set_ftrace_pid, so PID-based filtering is enabled. This kernel thread is mostly asleep (it’s the thread from which new kernel threads are forked. As it isn’t scheduled in often, the chances it’ll handle any software interrupts are rare).</p><p>That’s it! After enabling ftrace and sending the to-be-filtered packet, I received exactly one trace in the trace buffer! It took some time, but this trace sure was helpful in helping me understand the relevant flow.</p><p>What we can take from here, besides the new ability of dynamic filtering, is this: As long as you know exactly what you seek, you <strong>can</strong> do it in Linux, even if it’s not supported in the code. All it takes is a bit of digging in the code, and perhaps adding a tiny patch here and there…</p><p><em>Note: The idea presented here — and the kernel Python itself — are both experimental. Do NOT try them on a production system. They are given as research &amp; debugging tools for use on test machines only!</em></p><p>[1] Debugging the kernel using Ftrace — <a href="https://lwn.net/Articles/365835/">https://lwn.net/Articles/365835/</a></p><p><em>[2] Ftrace: The hidden light switch — </em><a href="https://lwn.net/Articles/608497/">https://lwn.net/Articles/608497/</a></p><p><em>[3] ftrace: trace your kernel functions! — </em><a href="https://jvns.ca/blog/2017/03/19/getting-started-with-ftrace/">https://jvns.ca/blog/2017/03/19/getting-started-with-ftrace/</a></p><p>[4] Strictly speaking, this can be implemented by pinning a RX flow to a specific CPU (and its ksoftirqd/<em>cpu</em> thread). But I wanted a more generic solution.</p><p>[5] In Linux, software interrupts are a set of common, high priority jobs executed regularly in response to certain kernel/hardware events. Sometimes they complete work deferred from a hardware interrupt, but not necessarily. You can read more about them here: <a href="https://lwn.net/Articles/520076/">https://lwn.net/Articles/520076/</a>.</p><p>[6] Per-CPU variables are variables that have multiple copies, one for each CPU of the system. Kernel code can easily access the percpu instance for currently executing CPU. If an object can be logically bound to a CPU, then defining it as a percpu variable will remove all locking needs, because each CPU has its own copy. This has many other uses, and you can read about its kernel implementation here: <a href="https://0xax.gitbooks.io/linux-insides/content/Concepts/linux-cpu-1.html">https://0xax.gitbooks.io/linux-insides/content/Concepts/linux-cpu-1.html</a>.</p><p>[7] <a href="https://github.com/micropython/micropython/pull/5482">https://github.com/micropython/micropython/pull/5482</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dececfc3eced" width="1" height="1" alt=""><hr><p><a href="https://medium.com/granulate/dynamic-ftrace-filtering-dececfc3eced">Dynamic ftrace filtering</a> was originally published in <a href="https://medium.com/granulate">Granulate</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Running Python in the Linux Kernel]]></title>
            <link>https://medium.com/@yon.goldschmidt/running-python-in-the-linux-kernel-7cbcbd44503c?source=rss-15275be2a0a0------2</link>
            <guid isPermaLink="false">https://medium.com/p/7cbcbd44503c</guid>
            <category><![CDATA[linux]]></category>
            <category><![CDATA[linux-kernel]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[Yonatan Goldschmidt]]></dc:creator>
            <pubDate>Tue, 31 Dec 2019 16:23:37 GMT</pubDate>
            <atom:updated>2019-12-31T16:23:37.464Z</atom:updated>
            <content:encoded><![CDATA[<p>This article will talk about a cool project I’ve worked on recently — a full Python interpreter running inside the Linux kernel, allowing:</p><ul><li>Seamless kernel APIs calls</li><li>Global variables access</li><li>Python syntax sugar for reading &amp; writing kernel structures</li><li>Kernel-core-into-Python callbacks (“Python function pointers”)</li><li>Kernel function hooking (via kprobes &amp; ftrace)</li><li>Python-based kernel threads</li></ul><p>And everything’s dynamic, with a REPL running in the kernel.</p><p>If you just wanna try it, then you can jump to the end of the article for usage instructions. In the rest of this post I’ll share how this idea came about, what were the challenges building it, etc.</p><p>But first, I’ll give you a few examples of what it’s capable of.</p><pre>&gt;&gt;&gt; printk(&quot;so.. %s %d %d %d\n&quot;, &quot;hello&quot;, 123, None, True)<br>18<br>&gt;&gt;&gt; # in dmesg: &quot;so.. hello 123 0 1&quot;</pre><p>This small snippet will print all files opened on the system (by all processes and by the kernel itself):</p><pre># kernel_ffi has functions to interop with the kernel<br>from kernel_ffi import ftrace, str as s</pre><pre># filename_s is now a function that &quot;casts&quot; pointers to the kernel&#39;s &quot;struct filename&quot;<br>filename_s = partial_struct(&quot;filename&quot;)</pre><pre># &quot;orig&quot; is a callable pointer, to call the real do_filp_open.<br>def do_filp_open_hook(orig, dfd, pathname, op):<br>    fn = filename_s(pathname)<br>    # fn is a &quot;struct filename&quot; object, and we can access its fields<br>    # use &quot;s&quot; to read the name pointer to a Python string<br>    fn_str = s(int(fn.name))<br>    print(&quot;do_filp_open on {!r}&quot;.format(fn_str))<br>    # finally, call the original with the same arguments. we<br>    # could modify them if we wanted.<br>    return orig(dfd, pathname, op)</pre><pre>ft = ftrace(&quot;do_filp_open&quot;, do_filp_open_hook)</pre><pre># remove when you&#39;re done. if you forget, it&#39;ll be removed when the <br># object is garbage-collected.<br>ft.rm()</pre><p>This snippet will “change” the contents of /dev/null :</p><pre>file_operations = partial_struct(&quot;file_operations&quot;)<br># I can reference null_fops without previously defining it -<br># all missing globals are resolved using the kernel symbols.<br>null_fops = file_operations(null_fops)</pre><pre>from kernel_ffi import callback</pre><pre>def my_read_null(file, buf, count, ppos):<br>    pos = p64(ppos)<br>    b = b&quot;who said /dev/null must be empty?\n&quot;[pos:]<br>    l = min(len(b), count)<br>    memcpy(buf, b, l)<br>    p64(ppos, pos + l)<br>    return l</pre><pre>c = callback(my_read_null)<br># calls to null_fops.read will call our callback instead.<br>null_fops.read = c.ptr()</pre><h3>Why?</h3><p>I’ve had experience developing both user-mode and kernel-mode software. User-mode environments have a great advantage when we talk about the ease of development; The development community is huge, we have tons of examples online, and many dev tools are ready at hand. You also have many tools and scripting languages to help you with prototyping. Even when your code-base is written in a low level language like C, you can experiment with user-mode ideas in a faster prototyping environment, like Python.</p><p>You don’t get that in kernel development. There are tons of APIs, much less documentation and no feasible way of prototyping besides recompiling your code, reloading it and trying to measure (let’s face it, we all just printk) the differences. Needless to say that you pay badly for mistaking, since many of them will crash your kernel.</p><p>I got the idea that being able to <em>easily </em>prototype API calls, access variables and monitor kernel functions behavior, might be useful. A more dynamic language will do well, and a REPL will be very nice.</p><p>There are tons¹ of dynamic-patching kernel tools, but I didn’t know of one providing a dynamic REPL, and in a convenient manner. And what would be more convenient than Python?</p><p>Basically what I had in mind is a fusion of <a href="https://frida.re/">Frida</a> (providing hooks, because I realized hooks will also be useful) and a Python REPL (providing easy inspection and interaction with objects and functions).</p><p>Here’s a real-life example from this week, showing this need of a REPL: I wrote something based on the kernel’s rw_semaphore , in one function I had the read lock taken and I needed to write. The concept of “upgradable RW locks” — <em>atomically converting a read lock to a writer lock — </em>is well known, so I thought a quick search online would yield a result as for whether it’s possible or not. I couldn’t find anything, neither in the docs (the .h file).</p><p>A quick check in the REPL would be enough! So I headed to the terminal tab I keep open with a REPL on some QEMU VM, and typed the following:</p><pre>&gt;&gt;&gt; from kernel_ffi import kmalloc<br>&gt;&gt;&gt; from struct_access import sizeof<br>&gt;&gt;&gt;<br>&gt;&gt;&gt; p = kmalloc(sizeof(&quot;rw_semaphore&quot;))<br>&gt;&gt;&gt; __init_rwsem(p)<br>&gt;&gt;&gt;<br>&gt;&gt;&gt; down_read(p)<br>&gt;&gt;&gt; # yeah, can lock twice<br>&gt;&gt;&gt; down_read(p)<br>&gt;&gt;&gt;<br>&gt;&gt;&gt; down_write_trylock(p)<br>0  # makes sense, i guess<br>&gt;&gt;&gt; down_write(p)<br># hangs forever!</pre><p>Back to the story. I’ve had some experience with <a href="http://micropython.org/">MicroPython</a>, which is a complete Python 3 interpreter intended for microcontrollers. I’ve been using it on various chips like the ESP32 and ESP8266 for a while, and I decided it won’t be too troublesome to port it to the Linux kernel, since unlike CPython, MicroPython wasn’t designed to be run (only) in usermode. It wasn’t designed to run in the Linux kernel either, but it makes much less assumptions about its environment, and that’s why it is easier to get it running on a new “platform”.</p><h3>Some challenges</h3><p>Some issues and designs I have encountered during development.</p><h4>Struct Access</h4><p>The kernel code defines and uses thousands of complex structures. I wanted this tool to provide human-friendly struct accessing, not address-based like “read an integer at address XX”, “write a byte at address YY”.</p><p>So, for a struct like struct net_device *dev, what’s required to provide accessors like dev-&gt;stats.rx_dropped?</p><p>The first thing is some Python syntax magic for the dereferences, array accesses, etc. It’s quite cool behind the scenes, but I won’t talk about that.</p><p><em>The second thing, and the more interesting one, is how does the Python get to know the structure layout?</em></p><p>When compiling a kernel module (that uses structures), you are required to have the kernel headers and configuration. The compiler reads the definitions from them. Can we parse those headers and extract structure definitions as well?</p><p>There are a few C structure parsing libraries in Python, for example <a href="https://github.com/andreax79/python-cstruct">cstruct</a> and <a href="https://github.com/fox-it/dissect.cstruct">dissect.cstruct</a>. But if you have had a look at a complex kernel structure, you’d know these approaches won’t “just work” — the struct definitions make very extensive use of #ifdefs based on configurations, specific alignment requirements like __cacheline_aligned_in_smp,² not to mention __randomize_layout …³ My point is, it will be very hard to parse it correctly for someone who’s not the compiler actually building it.</p><p>Who’s else doing it, though? Debuggers. GDB allows you to print structs and access structs field. How do debuggers do it?</p><p>The DWARF debugging format (embedded in ELF files when you compile with -g) can encode struct definitions. That’s what debuggers use, and also how the useful <a href="https://lwn.net/Articles/335942/">pahole</a> tool does its tricks. There’s even also <a href="https://github.com/arvidn/struct_layout">a Python</a> implementation that does more or less the same.</p><p><em>At this point, I thought that relying of DWARF requires the target </em><strong><em>code</em></strong><em> to be recompiled with debug info. Now I can say it’s true. Anyway, I went ahead with the solution I had mind…</em></p><p>I decided I had to follow the way GCC extracts structs, and what’s the best way to do so if not from the inside of GCC itself? Time to write a GCC plugin.</p><p>So I found a <a href="https://rwmj.wordpress.com/2016/02/24/playing-with-gcc-plugins/">simple example of a GCC plugin</a> and did<em> what developers do the best </em>— take existing code they don’t fully understand, run it, modify it a little, run it again and learn from what’s changed. Shortly after I had a fully functioning plugin that you can load during your compilation, and it’ll dump all defined structs in as nice Pythonic objects. I named it struct_layout (just like the DRAWF parsing Python project I mentioned earlier) and you can find it <a href="https://github.com/Jongy/struct_layout">on github</a>.</p><p>So all you have to do is to include the headers you want into an empty C file, and compile with the plugin.</p><p><em>In hindsight, I could do similarly with DWARF… ;) Just compile an empty C file including the relevant headers, and read the dwarf output in the </em><em>.o file.</em></p><p><em>But I’m happy with my choice. Writing a GCC plugin was a great experience I encourage all developers to take on themselves. It was sure more fun than parsing the DWARF section.</em></p><p>The rest was simple. As I said earlier, with a bit of Python magic you can easily wrap those definitions with objects that’ll allow the nice syntax sugar mimicking how it looks in C code.</p><pre>&gt;&gt;&gt; d = net_device(dev_get_by_name(init_net, &quot;eth0&quot;))<br>&gt;&gt;&gt; # so this accesses the net_device&#39;s<br>&gt;&gt;&gt; # &quot;struct net_device_stats stats&quot; field, and<br>&gt;&gt;&gt; # then accesses &quot;unsigned long rx_bytes&quot;<br>&gt;&gt;&gt; d.stats.rx_bytes<br>15158</pre><p>And since it’s Python and everything’s dynamic, it also comes with a few cool features, like tab completion for fields and basic protection from NULL dereferences, array out-of-bounds access, unsigned/signed overflow detection and more. Neat!</p><h4>Multi-threading</h4><p>MicroPython supports multi-threading out-of-the-box, you just have to give it some basic primitives (like locks) and a TLS (thread-local storage), and you need to hack a GC implementation that takes all threads into account.</p><p>TLS implementations in usermode vary. For x86, for example, you can clone a new thread with CLONE_SETTLS and the kernel will make sure that whenever your thread runs, it’ll have the fs register pointing to your specified data structure. Other basic possible implementation can be to use the bottom/top of the stack for storage. That’s the kernel implementation for current_thread_info in many architectures — for example, for ARM:</p><pre>static inline struct thread_info *current_thread_info(void)<br>{<br>    return (struct thread_info *) (current_stack_pointer &amp; ~(THREAD_SIZE - 1));<br>}</pre><p>These methods are useful when you control the thread — that is, you create it, you control the entry point, and so on. But what if you’re a callback in another thread, or just hooking onto some code which is to be run by threads you don’t control? You can’t use these tricks — you might interfere with the owner of the thread who’s using the same method.</p><p>So, you can just select one of the unused methods (x86 doesn’t use the top of the stack — or the bottom, I can’t recall — so it’s free for your use) but since I needed to maintain the list of threads currently executing Python (we’ll see later why) I went with a more naive implementation — making use of the existing thread-based struct current, I keep a list of task_struct s to their TLS info. Then you can always get the TLS for current.</p><p>The next major component that needs special treatment when multi-threading is the garbage collector— MicroPython uses a mark &amp; sweep garbage collector:</p><p><em>In mark &amp; sweep, no object references are maintained, and when the GC runs it needs to scan the entire program memory (or, at least the relevant areas) for pointers into the heap. Heap blocks that are referenced are marked, and are added to the scan queue, recursively. All blocks still unmarked when the scan queue is empty are considered garbage and are freed.</em></p><p>Mark &amp; sweep has the advantage of simpler code (no reference counting, no freeing, you just malloc stuff and everything works). But the requirement to “scan the entire program memory” is… impossible in the kernel. For example, the Python makes partial of the kernel heap. Do we need to scan the heap as well? It might be huge!</p><p>But we just need to make sure all the pointers into the heap are scanned… If we never place root pointers — pointers that no other object refers to — globally, but only on stacks of threads executing Python, then this scan can be narrowed down to the stacks of these threads, which is simple enough to do.</p><p>Using the list of threads we kept for TLS, we can get the stack start &amp; end pointers of the relevant threads. The stack start can be narrowed to the “stack start when Python started” — if there’s a kernel stack containing 10 frames, and then a Python hook was called, we don’t need to scan those 10 previous frames. Care must be taken to use the right stack start, even for a thread with nested Python calls (that is, a Python hook calling kernel code that’s again hooked by Python). And since there’s no feasible way to get the current stack pointer for a thread currently running on another CPU, we’ll just use the real stack end.</p><p>Combining these, the GC is deterministic enough and safe enough to run, even from kernel hooks, which is quite cool.</p><p>Threading support is not complete and I still get crashes from time to time, but it’s not something that can’t be debugged and eliminated.</p><p>And’s that’s enough talking for this post. Onward to the real thing!</p><h3>MicroPython for the Linux Kernel</h3><p><strong><em>Use it on your own risk!</em></strong><em> This is definitely not production ready. Whatever you try using it should be tried using a VM beforehand. And if you need such a dynamic tool for production use, I suggest you to use one of the tools mentioned in the footnotes¹.</em></p><p><em>(Though it mostly works and I managed to happily run it on my physical PC… :))</em></p><h4>Compiling</h4><pre>$ # point KDIR to the kernel headers you&#39;re compiling for.<br>$ # if building for the locally running kernel, you can skip this step.<br>$ export KDIR=/path/to/the/kernel/<br>$ # get structs_layout, it&#39;ll be built as a part of micropython.<br>$ git clone <a href="https://github.com/Jongy/struct_layout.git">https://github.com/Jongy/struct_layout.git</a><br>$ # build python:<br>$ <a href="https://github.com/Jongy/micropython.git">g</a>it clone --depth 1 -b linux-kernel <a href="https://github.com/Jongy/micropython.git">https://github.com/Jongy/micropython.git</a><br>$ cd micropython<br>$ make -C mpy-cross<br>$ make -C ports/linux-kernel STRUCT_LAYOUT=1</pre><p>The resulting module ports/linux-kernel/build/mpy.ko can be loaded with a plain insmod / modprobe .</p><p>You can get a REPL with socat file:`tty`,raw,echo=0,escape=0xc tcp:&lt;IP&gt;:9999 (use Ctrl+D/Ctrl+L to break out from this shell).</p><p>For more examples and general help, you can refer to the <a href="https://github.com/Jongy/micropython/blob/linux-kernel/ports/linux-kernel/README.rst">README</a>.</p><p>I’ve tested it on QEMU+KVM with kernels 4.4, 5.0, 5.2. 5.3, 5.4. I’ve also tested it on my physical laptop (Ubuntu 18.04, kernel 5.0) and my Arch Linux (kernel 5.4).</p><p>That’s all. I hope you enjoyed the reading, and that you find this tool useful :)</p><p>[1]: To name a few: SystemTap, eBPF, perf, kprobe events, ftrace, kplugs (which is somewhat similar to this project…)</p><p>[2]: __cacheline_aligned attributes ensure data items are aligned to the size of a cacheline. This is usually used when different items in a struct tend to be written concurrently by different CPUs. By ensuring “items of different CPUs” don’t cross into the same cacheline, cache flushes can be avoided. A classic example is the <a href="https://elixir.bootlin.com/linux/v4.8/source/include/linux/ptr_ring.h#L34">ptr_ring</a> struct which has separate cachelines for “producer” items, “consumer” items and shared items.</p><p>[3]:__randomize_layout attributes marks a struct definition as applicable for struct layout randomization, which is a very cool obfuscation technique employed to make kernel exploits harder. Read this <a href="https://lwn.net/Articles/722293/">lwn article</a> to learn more about it.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7cbcbd44503c" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Low Level Code-Size Optimizations in C]]></title>
            <link>https://medium.com/@yon.goldschmidt/low-level-code-size-optimizations-in-c-5b9e17d288ce?source=rss-15275be2a0a0------2</link>
            <guid isPermaLink="false">https://medium.com/p/5b9e17d288ce</guid>
            <category><![CDATA[c]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Yonatan Goldschmidt]]></dc:creator>
            <pubDate>Thu, 21 Nov 2019 13:37:57 GMT</pubDate>
            <atom:updated>2019-12-23T00:10:23.330Z</atom:updated>
            <content:encoded><![CDATA[<p>While performance optimization is something often talked and written about, code size improvements are less often sought after. In this article, we’ll talk about the latter.</p><h4>Why should we optimize for smaller code size, anyway?</h4><p>One reason (which is also why I’d gotten into this subject) is that in particular scenarios and devices, your code size is actually limited. It might be unbelievable, but even in this era — when it’s legit to <a href="https://github.com/crosswalk-project">embed a full Chrome web engine</a> in your Android application — 10KBs here and there might make the difference.</p><p>Now, I must admit that after a while having size optimizations in mind, it actually became quite fun to fight with GCC in an attempt to make certain functions / snippets produce better machine code.</p><p>If this foreword has got you interested, or if you’re just wondering what more can be done besides using the helpful GCC flags-Os -ffunction-section -fdata-section -Wl,--gc-sections -flto — then I invite you to read onward.</p><p><em>A slight disclaimer: I won’t be diving deep into all subjects mentioned here. I’ll try to briefly explain every matter though, so don’t be intimidated if you didn’t understand every bit (like those flags I mentioned above).</em></p><p>I’ll be talking about RISC architectures, where it’s easier to understand which machine code the compiler may produce, and why some results are better than others. It’s harder to be done on complex architectures like x86, where code size improvements are, in my opinion, less relevant as well.</p><h4>Project-wide optimizations</h4><p>We’ll work on <a href="http://micropython.org/">MicroPython</a>. In case you’ve never heard of this project, then shortly:</p><blockquote>MicroPython is a lean and efficient implementation of Python 3.</blockquote><p>It’s a very cool project, and it’s an interesting target for size optimizations because it’s already damn good at it. You won’t find any low-hanging fruits here. This codebase is routinely optimized for size, with new changes and improvements in every part of it.</p><p>When optimizing, you can focus on a module, a function, a small code snippet… Or, you can work on changes that have a project-wide effect — that’s what the focus will be on today.</p><p><em>We’ll be working with the </em><em>qemu-arm port of MicroPython, since it is an ARM build that doesn’t require any special hardware — it is emulated on QEMU.</em></p><h3>Code &amp; Data references</h3><p>In a big project composed of many files and modules, there are tons of functions and data items involved.</p><p>Many ISAs (<em>Instruction Set Architectures), </em>ARM included, have multiple instructions for accessing data. Apparently, those instructions may occupy quite a bit of the total code size.</p><p>For example, given this C code:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/33607b0129a7a13ca984dfdcd5a938d8/href">https://medium.com/media/33607b0129a7a13ca984dfdcd5a938d8/href</a></iframe><p>There are multiple ways to turn global variable access into ARM code. The compilers will usually use the following one:</p><pre>00000000 &lt;mul_by_global&gt;:<br>   0: e59f3008  ldr r3, [pc, #8] ; 10 &lt;mul_by_global+0x10&gt;<br>   4: e5933000  ldr r3, [r3]<br>   8: e0000093  mul r0, r3, r0<br>   c: e12fff1e  bx lr<br>  10: 00000000  .word 0x00000000</pre><p>After the function’s epilogue, the compiler has placed a single data word, which will contains the address of my_global_int. The function loads that address into a register, then dereferences the address itself. This procedure is required because ARM doesn’t have a general “read word from 32-bit address into register” (like the one x86 has), and the compiler <em>doesn’t</em> know where my_global_int will eventually be placed, so it has to prepare for the worst and generate code that will work with any address.</p><p>That’s 12 bytes, or the equivalent of 3 opcodes, to load a single word from memory. Not too good.</p><p>In Thumb (basically 16-bit ARM mode) it’s even worse: Since most opcodes are 16-bit, and the loaded data word must be aligned to 4 bytes for ldr, then if the function doesn’t have a 4 bytes alignment, a padding nop must be added! (That’s the nop in address 0x16. It never runs, but it occupies program space)</p><pre>0000000c &lt;mul_by_global_plus_one&gt;:<br>   c: 4b02       ldr r3, [pc, #8] ; (18 &lt;mul_by_global_plus_one+0xc&gt;)<br>   e: 681b       ldr r3, [r3, #0]<br>  10: 4358       muls r0, r3<br>  12: 3001       adds r0, #1<br>  14: 4770       bx lr<br>  16: 46c0       nop   ; (mov r8, r8)<br>  18: 00000000  .word 0x00000000</pre><p>10 bytes are used to load the value. That’s 5 general opcodes.</p><h4>Can we make it any better?</h4><p>Yes, there are tricks.</p><p>One common approach is to place certain items in a different, smaller segment which will allow using shorter instructions when accessing them This “smaller” section is called <em>sdata</em> or <em>sbss (small-data, small-bss)</em></p><p>But why does it have to be small? Why can’t we place there <em>all</em> data and enjoy better access instructions? Well, it depends on the platform / architecture, but in many of them the implementation of the small data section is to set one of the general purpose registers to <em>always</em> point to that section. Then items can be accessed via this register, which evidently results in better instructions. The offset of the data from the register is limited, hence the limit of the section size. For example, in ARM’s ldr the offset has signed 13 bits, so about 8192 bytes.</p><p>We’ll see how we can combine the <em>sdata </em>concept with smaller data access instructions.</p><h4>Which items should be improved?</h4><p>Each program has the data items &amp; functions that are most commonly referenced. If we have to choose which accesses are to be improved, we better pick data items that are referenced many times throughout the code.</p><p>A big project like MicroPython surely has such commonly-referenced items. So, how do we find them? Counting references in the source code is a hassle, and not too accurate anyway: in a highly optimized project, there may be great distinctions between what we see in the input sources and what’s left in the output binary.</p><p>We’ll extract this information from the final binary itself, and use the <em>relocations section </em>for aid.</p><p><em>Relocations, in short, is all information about what needs to be fixed in a program when assigning it to a different location in memory (usually, prior to execution).</em></p><p><em>For example, accessing data via an absolute address will require a relocation entry, in case that absolute address is changed. We can count those entries, and it will tell us the number of references to an item.</em></p><p>I wrote a helper script, <a href="https://github.com/Jongy/devscripts/blob/master/count_references.py">count_references.py</a>, that lists all data items referenced in an ELF, ordered by the number of references they have.</p><p>Now, let’s get to business. Grab the MicroPython sources, set up some ARM toolchain and compile the qemu-arm port.</p><pre>$ git clone <a href="https://github.com/micropython/micropython.git">https://github.com/micropython/micropython.git</a><br>$ # on arch<br>$ pacman -S arm-none-eabi-gcc<br>$ # on ubuntu<br>$ apt install gcc-arm-none-eabi<br>$ make -C ports/qemu-arm</pre><p>We get this final ELF:</p><pre>$ arm-none-eabi-size ports/qemu-arm/build/firmware.elf<br>   text    data     bss     dec     hex filename<br> 151624      12     448  152084   25214 ports/qemu-arm/build/firmware.elf</pre><p>Let’s use the count_references.py script and check for candidates.</p><pre>$ python count_references.py ports/qemu-arm/build/firmware.elf<br>$ # what? no output?</pre><p>Final linking of ELFs may strip away the relocations info (If a program is to be loaded to a known, constant address, why is the relocation info required?)</p><p>You can tell ld to keep this information using --emit-relocs. Add this to the LDFLAGS in ports/qemu-arm/Makefile, then re-link and try count_references.py again.</p><pre>: 1377<br>        R_ARM_ABS32: 1377<br>__aeabi_fmul: 199<br>        R_ARM_THM_CALL: 199<br>__aeabi_fsub: 139<br>        R_ARM_THM_CALL: 139<br>__aeabi_fadd: 130<br>        R_ARM_THM_CALL: 130<br>compile_node: 99<br>        R_ARM_THM_CALL: 95<br>        R_ARM_THM_JUMP24: 4<br>.....</pre><p>The top of the list has a blank symbol name. Those are nameless data items (string literals and other unnamed consts) so grouping by symbol name doesn’t work with them. Skip those.</p><p>The next few are split between relocation type. All items with R_ARM_THM_CALL are functions (that’s the relocation type for bl), and while calls can also be optimized, that’s the subject for another post.</p><p>So, we’re left with a few leaders having R_ARM_ABS32. This relocation is performed by writing the absolute address of the data item being relocated — it’s the one used by those pesky ldrs we’ve seen (and it has other uses as well, e.g function pointers in a struct).</p><p>Let’s start with mp_const_none_obj. It is a tiny object — just the size of a pointer (4 bytes for us), and it has almost a 100 accesses, many of them are of the ldr type I’ve presented earlier. For example:</p><pre>0001c6ec &lt;mp_builtin_open&gt;:<br>   1c6ec:   4800       ldr r0, [pc, #0]  ; (1c6f0 &lt;mp_builtin_open+0x4&gt;)<br>   1c6ee:   4770       bx  lr<br>   1c6f0:   00022144   .word   0x00022144</pre><p>This function is a mere return mp_const_none; (mp_const_none is a macro referring to the address of mp_const_none_obj).</p><h4>Moving objects around</h4><p>What if those 4 poor bytes can be shoved somewhere else? Recalling the sdata possible implementation with a register — that’d work, but it seemed too big of a change. I kept searching for something else.</p><p>When thinking of the memory addresses used in your program, it’s a good idea to know how it’s laid out. The qemu-arm port has a linker script describing the output memory sections (ports/qemu-arm/stm32.ld).</p><p><em>The linker script dictates how functions and data objects are to be placed, and it gives great freedom on other output settings, among them the addresses of output sections.</em></p><p>The script tells the linker that the read-only memory of the program resides at address 0x0.</p><pre>MEMORY<br>{<br>    ROM : ORIGIN = 0x00000000, LENGTH = 1M<br>    RAM : ORIGIN = 0x20000000, LENGTH = 128K<br>}</pre><p>Hmm.. Interesting. We can exploit this fact.</p><p>Most ISAs have instructions that deal with small immediates, without requiring extra loads of memory. In the case of <a href="https://ece.uwaterloo.ca/~ece222/ARM/ARM7-TDMI-manual-pt3.pdf">Thumb</a>, there’s a mov rd, #imm instruction, accepting an 8-bit unsigned immediate. An object stored around address 0x0 can be referenced with an 8-bit number, can’t it?</p><p>Furthermore, there’s even a cmp rd, #imm with 8-bit immediates, so all comparisons with mp_const_none won’t even require an extra register load. There are many such comparisons.</p><h4>So… How do we actually do it?</h4><p>Easy! Remember the linker script? It was <em>meant </em>for this kind of stuff.</p><pre>SECTIONS<br>{<br>    .text : {<br>        . = ALIGN(4);<br>        KEEP(*(.isr_vector))<br>        *(.text*)<br>        *(.rodata*)<br>        . = ALIGN(4);<br>        _etext = .;<br>        _sidata = _etext;<br>    } &gt; ROM<br>....<br>}</pre><p>This snippet from stm32.ld defines an output section named .text, that will be placed in the read-only memory. It will take<em> </em>the input sections given in the object files: all .isr_vector sections, then all .text.* sections, and so on, in the order they appeared in the script.</p><p>We can have mp_const_none_obj be placed in its own, private section, and that section could be placed first in the output .text!</p><p>Well, not first, actually, since the .isr_vector really has to come before due to reasons we won’t get into. Luckily, this first one is only 0x40 bytes, sparing us the remaining space in the 8-bit region around 0x0.</p><p>We’ll add __attribute__((section(&quot;.rodata.mp_const_none_obj&quot;))) to the definition of the object in objnone.c, and then add KEEP(*(.rodata.mp_const_none_obj)) in the linker script.</p><p>Re-link, and….</p><p>Nothing has changed!</p><pre>$ arm-none-eabi-size ports/qemu-arm/build/firmware.elf<br>   text    data     bss     dec     hex filename<br> 151624      12     448  152084   25214 build/firmware.elf</pre><p>Well, not the size, if anything. That’s exactly the same result! How come? Did the linker disobey our new command?</p><pre>$ arm-none-eabi-objdump -dz ports/qemu-arm/build/firmware.elf<br>ports/qemu-arm/build/firmware.elf:     file format elf32-littlearm</pre><pre>Disassembly of section .text:</pre><pre>00000000 &lt;isr_vector&gt;:<br>     0:       00 00 02 20 95 a5 01 00 69 a5 01 00 69 a5 01 00     ... ....i...i...<br>    10:       69 a5 01 00 69 a5 01 00 69 a5 01 00 00 00 00 00     i...i...i.......<br>    20:       00 00 00 00 00 00 00 00 00 00 00 00 69 a5 01 00     ............i...<br>    30:       69 a5 01 00 00 00 00 00 69 a5 01 00 69 a5 01 00     i.......i...i...</pre><pre>00000040 &lt;mp_const_none_obj&gt;:<br>    40:       48 21 02 00                                         H!......</pre><p>No, it didn’t. mp_const_none_obj is placed exactly where we wanted it to be.</p><p>Let’s check mp_builtin_open again:</p><pre>0001c6f0 &lt;mp_builtin_open&gt;:<br>   1c6f0: 4800       ldr r0, [pc, #0] ; (1c6f4 &lt;mp_builtin_open+0x4&gt;)<br>   1c6f2: 4770       bx lr<br>   1c6f4: 00000040  .word 0x00000040</pre><p>What happened, then? A full word is used to load the poor 0x40 value.</p><p>Problem is, the linker is the guy knowing that mp_const_none_obj will be available at 0x40. The compiler, which is responsible for emitting the instructions, didn’t know that &amp;mp_const_none_obj is an expression that can fit within a mov rd, #imm instruction. So, like I mentioned earlier, it prepares for the worst and emits instructions that’ll work with with any 32-bit value.</p><p><em>Previous paragraph is a bit inaccurate when LTO (Link-time Optimization) is active. Check out the bottom for a few notes about LTO.</em></p><p>How can you tell the compiler it can use a different instruction? In the case of function calls, for example, many architectures differentiate between <em>short calls</em> and <em>long calls</em>. You can tell the compiler which mode should be used via a global command-line switch, and even on the function level by adding e.g <a href="https://gcc.gnu.org/onlinedocs/gcc-9.2.0/gcc/ARM-Function-Attributes.html">__attribute__((long_call))</a> on a function declaration. Across different architectures, short/long calls are implemented using different instructions, while short calls are the better half, requiring less instruction bytes (and usually less instructions)</p><p>I’m not aware of any <em>short access</em> attributes, however.</p><p>As a general rule, the compiler will optimize whatever it knows during <em>compile time</em>. If we can force the compiler to directly access address 0x40 instead, things might change. It feels hacky, but let’s try the following:</p><pre>// replace this line in obj.h<br>#define mp_const_none (MP_OBJ_FROM_PTR(&amp;mp_const_none_obj))<br>// with this one<br>#define mp_const_none (MP_OBJ_FROM_PTR((void*)0x40))</pre><p>Recompile, and…</p><pre>$ arm-none-eabi-size ports/qemu-arm/build/firmware.elf<br>   text    data     bss     dec     hex filename<br> 151344      12     448  151804   250fc ports/qemu-arm/build/firmware.elf</pre><p>Woohoo! It worked. Size decreased by about 300 bytes. Let’s move more relevant objects close to our address 0x40: I have chose mp_const_true, mp_const_false, mp_type_type. They all scored high in the script’s output.</p><p>After undergoing the same procedure with those 3:</p><pre>$ arm-none-eabi-size ports/qemu-arm/build/firmware.elf<br>   text    data     bss     dec     hex filename<br> 150512      12     448  150972   24dbc ports/qemu-arm/build/firmware.elf</pre><p>Voila! Size improvement: 1KB. Quite cool.</p><p>You can also run the tests to make sure nothing was broken.</p><pre>$ make -C ports/qemu-arm -f Makefile.test test</pre><h3>Afterword</h3><p>Does it actually help? qemu-arm by itself is an experimental port used for emulation and testing. And it’s just 1KB, isn’t it?</p><p>Well, I have tried this trick in a few other ports of MicroPython, but their memory map was too different for it to work out-of-the-box. It might be useful on some other, specific ARM builds. You can see my progress in <a href="https://github.com/micropython/micropython/pull/5320">this pull request</a> on GitHub.</p><p>Edit 18.12.2019: About a month after this writing, Damien (the MicroPython project maintainer) <a href="https://github.com/micropython/micropython/pull/5429">took this basic idea even further:</a> By manipulating the way Python objects are represented natively, he let the common constants (as mp_const_none and others) be represented with very few, low bits. On most architectures these bits can be loaded simple, small instructions since they fit in a byte. Those “numbers” are not real objects anymore (not pointing to any struct), so this can be applied in all architectures and builds, without imposing anything on the address space layout (unlike the idea presented in this article). A very neat trick!</p><p>Sometimes with a bit of thought you can greatly improve your output code. Optimization possibilities are endless. Compilers can do most of the obvious, local tricks, but (<em>meanwhile</em>) it’s us who can think of the more complex, wider and creative changes that’ll improve our programs even more.</p><p>Anyway, it sure was fun, and 1KB is a significant decrease in the world of “micro size optimizations” I’m dealing with here.</p><p>That’s it! It was my first technical writing (or, my first writing at all) and I really enjoyed it. I hope you have enjoyed the reading :)</p><h4>Similar tricks in other projects?</h4><p>The first example that pops into my mind is the current (or current_thread_info) pointer in the Linux kernel. current allows quick access to the data structure of the currently executing task/thread. It is used extensively.</p><p>Its implementation is different between architectures, but it is generally divided between the two:</p><ul><li>Dedicate a register that’ll always point to the struct. When the current task changes, the register set changes as well and so the pointer is updated for the new task.</li><li>Store the struct in the lower end of the stack, then a simple and operation to remove the few low bits of the <em>current </em>stack pointer will give you… the current struct. In pseudo assembly: and r0, sp, 0xffffe000 for 32-bit kernel with stack size 8192.</li></ul><p>I like these, because they kill two birds with one stone: implementing a thread-local storage and allowing access to it in the easiest manner possible. 10/10 for creativity with the stack pointer trick.</p><h4>A note about LTO…</h4><p><em>Link-time optimization 101:</em> Standard compilation process takes each source file (or translation unit, if you may) and generates the machine code for it into an object file, then lets the linker merge all those files into the final target <em>without</em> changing any of machine code.</p><p>With LTO, the generation of machine code is delayed until all object files are given to the linker, which then generates machine code for the entire program at once.</p><p>What you actually have inside those semi-object files varies between different compilers, but the point is — it’s <em>supposedly </em>enough data to allow the linker to perform virtually any optimization the compiler could have conducted itself, had it received the entire program as a single source file.</p><p><em>In short, LTO is awesome.</em></p><p>Nonetheless, I couldn’t get LTO to make this optimization by itself :( A bit disappointing, to say the least.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5b9e17d288ce" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>