Saturday, January 10, 2015

151-byte static Linux binary in Rust

Part of the sales pitch for Rust is that it's "as bare metal as C".1 Rust can do anything C can do, run anywhere C can run,2 with code that's just as efficient, and at least as safe (but usually much safer).

I'd say this claim is about 95% true, which is pretty good by the standards of marketing claims. A while back I decided to put it to the test, by making the smallest, most self-contained Rust program possible. After resolving a few issues along the way, I ended up with a 151-byte, statically linked executable for AMD64 Linux. With the release of Rust 1.0-alpha, it's time to show this off.

Here's the Rust code:

#![crate_type="rlib"]
#![allow(unstable)]

#[macro_use] extern crate syscall;

use std::intrinsics;

fn exit(n: usize) -> ! {
    unsafe {
        syscall!(EXIT, n);
        intrinsics::unreachable()
    }
}

fn write(fd: usize, buf: &[u8]) {
    unsafe {
        syscall!(WRITE, fd, buf.as_ptr(), buf.len());
    }
}

#[no_mangle]
pub fn main() {
    write(1, "Hello!\n".as_bytes());
    exit(0);
}

This uses my syscall library, which provides the syscall! macro. We wrap the underlying system calls with Rust functions, each exposing a safe interface to the unsafe syscall! macro. The main function uses these two safe functions and doesn't need its own unsafe annotation. Even in such a small program, Rust allows us to isolate memory unsafety to a subset of the code.

Because of crate_type="rlib", rustc will build this as a static library, from which we extract a single object file tinyrust.o:

$ rustc tinyrust.rs \
    -O -C no-stack-check -C relocation-model=static \
    -L syscall.rs/target
$ ar x libtinyrust.rlib tinyrust.o
$ objdump -dr tinyrust.o
0000000000000000 <main>:
   0:   b8 01 00 00 00          mov    $0x1,%eax
   5:   bf 01 00 00 00          mov    $0x1,%edi
   a:   be 00 00 00 00          mov    $0x0,%esi
                        b: R_X86_64_32  .rodata.str1625
   f:   ba 07 00 00 00          mov    $0x7,%edx
  14:   0f 05                   syscall 
  16:   b8 3c 00 00 00          mov    $0x3c,%eax
  1b:   31 ff                   xor    %edi,%edi
  1d:   0f 05                   syscall 

We disable stack exhaustion checking, as well as position-independent code, in order to slim down the output. After optimization, the only instructions that survive come from inline assembly blocks in the syscall library.

Note that main doesn't end in a ret instruction. The exit function (which gets inlined) is marked with a "return type" of !, meaning "doesn't return". We make good on this by invoking the unreachable intrinsic after syscall!. LLVM will optimize under the assumption that we can never reach this point, making no guarantees about the program behavior if it is reached. This represents the fact that the kernel is actually going to kill the process before syscall!(EXIT, n) can return.

Because we use inline assembly and intrinsics, this code is not going to work on a stable-channel build of Rust 1.0. It will require an alpha or nightly build until such time as inline assembly and intrinsics::unreachable are added to the stable language of Rust 1.x.

Note that I didn't even use #![no_std]! This program is so tiny that everything it pulls from libstd is a type definition, macro, or fully inlined function. As a result there's nothing of libstd left in the compiler output. In a larger program you may need #![no_std], although its role is greatly reduced following the removal of Rust's runtime.

Linking

This is where things get weird.

Whether we compile from C or Rust,3 the standard linker toolchain is going to include a bunch of junk we don't need. So I cooked up my own linker script:

SECTIONS {
    . = 0x400078;
  
    combined . : AT(0x400078) ALIGN(1) SUBALIGN(1) {
        *(.text*)
        *(.data*)
        *(.rodata*)
        *(.bss*)
    }
}

We smash all the sections together, with no alignment padding, then extract that section as a headerless binary blob:

$ ld --gc-sections -e main -T script.ld -o payload tinyrust.o
$ objcopy -j combined -O binary payload payload.bin

Finally we stick this on the end of a custom ELF header. The header is written in NASM syntax but contains no instructions, only data fields. The base address 0x400078 seen above is the end of this header, when the whole file is loaded at 0x400000. There's no guarantee that ld will put main at the beginning of the file, so we need to separately determine the address of main and fill that in as the e_entry field in the ELF file header.

$ ENTRY=$(nm -f posix payload | grep '^main ' | awk '{print $3}')
$ nasm -f bin -o tinyrust -D entry=0x$ENTRY elf.s
$ chmod +x ./tinyrust
$ ./tinyrust
Hello!

It works! And the size:

$ wc -c < tinyrust
158

Seven bytes too big!

The final trick

To get down to 151 bytes, I took inspiration from this classic article, which observes that padding fields in the ELF header can be used to store other data. Like, say, a string constant. The Rust code changes to access this constant:

use std::{mem, raw};

#[no_mangle]
pub fn main() {
    let message: &'static [u8] = unsafe {
        mem::transmute(raw::Slice {
            data: 0x00400008 as *const u8,
            len: 7,
        })
    };

    write(1, message);
    exit(0);
}

A Rust slice like &[u8] consists of a pointer to some memory, and a length indicating the number of elements that may be found there. The module std::raw exposes this as an ordinary struct that we build, then transmute to the actual slice type. The transmute function generates no code; it just tells the type checker to treat our raw::Slice<u8> as if it were a &[u8]. We return this value out of the unsafe block, taking advantage of the "everything is an expression" syntax, and then print the message as before.

Trying out the new version:

$ rustc tinyrust.rs \
    -O -C no-stack-check -C relocation-model=static \
    -L syscall.rs/target
$ ar x libtinyrust.rlib tinyrust.o
$ objdump -dr tinyrust.o
0000000000000000 <main>:        
   0:   b8 01 00 00 00          mov    $0x1,%eax
   5:   bf 01 00 00 00          mov    $0x1,%edi
   a:   be 08 00 40 00          mov    $0x400008,%esi
   f:   ba 07 00 00 00          mov    $0x7,%edx
  14:   0f 05                   syscall 
  16:   b8 3c 00 00 00          mov    $0x3c,%eax
  1b:   31 ff                   xor    %edi,%edi
  1d:   0f 05                   syscall 

...
$ wc -c < tinyrust
151
$ ./tinyrust
Hello!

The object code is the same as before, except that the relocation for the string constant has become an absolute address. The binary is smaller by 7 bytes (the size of "Hello!\n") and it still works!

You can find the full code on GitHub. The code in this article works on rustc 1.0.0-dev (44a287e6e 2015-01-08). If I update the code on GitHub, I will also update the version number printed by the included build script.

I'd be curious to hear if anyone can make my program smaller!


  1. C is not really "bare metal", but that's another story

  2. From a pure language perspective. If you want to talk about availability of compilers and libraries, then Rust still has a bit of a disadvantage ;) 

  3. In fact, this code grew out of an earlier experiment with really small binaries in C. 

92 comments:

  1. Cool, here is an equivalent 71 bytes haskell executable (for comparison):

    #!/usr/local/bin/runhaskell
    module Main where
    main = putStrLn "Hello!"

    ReplyDelete
    Replies
    1. Surely you're trolling, but that's not a stand-alone binary. It would require /usr/local/bin/runhaskell and everything that thing requires...

      Delete
    2. HugoDaniel, very nicely done.

      Delete
  2. @HugoDaniel - That looks like 71 bytes of text but just with a hashbang so bash can execute it. This article is talking about ELF binaries which are directly executable. Your example would require a haskell compiler or interpreter to run.

    ReplyDelete
  3. ...And since I don't know the haskell ecosystem that well, I'd just get the whole dev env. Last time, that weighed in at over a gibibyte, but hey, I'm sure it'll fit on a /modern/ toaster.

    ReplyDelete
  4. Graeme, the shebang is the executable magic number (located in the first 2 bytes of the file) for the os interpreter (following at most 128 bytes for the location of the interpreter). I guess not many people might know this. Shebang is actually and executable format such as AOUT, ELF or gzipped ELF.
    A bit more info: https://en.wikipedia.org/wiki/Shebang_%28Unix%29#Magic_number

    Anders Eurenius, binary size doesn't really matter much since the OS can demand pages as it needs them (the whole thing is not loaded into memory, even in a small static linked binary).
    A bit more info here: https://en.wikipedia.org/wiki/Demand_paging

    ReplyDelete
  5. @HugoDaniel -- the point is that your program requires Haskell runtime to be able to run. The program in this blog post requires only standard libc, so it will run without installing anything.

    ReplyDelete
  6. It doesn't depend on libc, either. Just the syscall ABI that's built in to the kernel.

    ReplyDelete
  7. We should let someone just check the execution times and memory overhead of both the haskell wrapper and the binary code, then the difference might be noticeable even for HD.
    Regarding binary size, try using both implementations on a 8bit microcontroller and see who succeeds.

    ReplyDelete
  8. Running a *nix kernel on a 8-bit microcontroller must be very similar to eating ice-cream with your forehead.

    ReplyDelete
  9. It looks like there's actually a missed optimisation in the LLVM code gen, in the first example it should produce xor %esi,%esi instead of mov $0x0,%esi, that would reduce the code size by 4 bytes and make it run quicker.

    It's probably a bug in the way constants are passed into an inline asm, although I'd have thought the peephole pass would have picked it up.

    ReplyDelete
  10. The article looks out of step with current no_std-wielding Rust. Shall there be "151-byte Rust binary revisited"?

    ReplyDelete
  11. Hanging your eyebrows is a simple surgery. The doctor will remove the skin and fat on the brow. Then advanced, create a new look fit the face. Depending on the situation, the shape of the eyebrow that the method applied to each case will also be different.

    treo chan may bang chi

    treo chan may bao nhieu tien

    treo chan may webtretho

    https://www.youtube.com/watch?v=VokF0FqpLO0

    https://www.dailymotion.com/video/x6sknsq

    ReplyDelete
  12. ------------------------
    https://nsrzhbi.com/%D8%B4%D8%B1%D9%83%D8%A9-%D8%AA%D9%86%D8%B8%D9%8A%D9%81-%D9%83%D9%86%D8%A8-%D8%A8%D8%A7%D9%84%D9%85%D8%AF%D9%8A%D9%86%D8%A9-%D8%A7%D9%84%D9%85%D9%86%D9%88%D8%B1%D8%A9/
    شركة تنظيف كنب بالبخار بالمدينة
    ل تنعم بكنب ذو جودة عالية من ناحية النظافة والتعقيم والرائحة العطرة التي تعطيك الطاقة الإيجابية التي تحتاجها
    متخصصون فى التنظيف بالبخار للمجالس والكنب والستائر والسجاد ومتخصصون فى تنظيف الشقق والفلل والمنازل والبيوت
    شركة غسيل كنب بالمدينة

    ReplyDelete
  13. Nice blog, Get the responsive and creative website designing and Digital Marketing services by ogen infosystem.
    Top 5 Web Development Company in Delhi

    ReplyDelete
  14. Awesome information, visit the Mutual Fund wala for Mutual Fund Distributor, Investment Advisor in Delhi and Mutual Fund Advisor.
    Best Performing Mutual Fund

    ReplyDelete
  15. Get the best vastu consultancy in Delhi with Shriastrologer a leading
    vastu consultant in delhi.

    ReplyDelete
  16. Built your house and business and premises according to vastu shatra. Get the best vastu consultant in gurgaon.

    ReplyDelete
  17. Get the best seo services london with the leading seo cagency in London, UK

    ReplyDelete
  18. If you have any questions regarding canon wireless printer setup
    problem or if you are still experiencing some annoying printer problems then just call us +1 800-684-5649

    ReplyDelete
  19. How Do I Connect My Canon Printer To Wifi? Switching on the network printing can help to get rid of the headache of cables and USB. The only way to do how to connect canon printer to wifi. You can reach out to us at +1 800 684 5649 for help at any time.

    ReplyDelete
  20. This comment has been removed by the author.

    ReplyDelete
  21. اشكال بلاط الحوش تراكوتا من الانواع المميزة
    شركة نقل اثاث بابها
    شركة تنظيف بحفر الباطن

    كم يكلف تبليط الحوش ؟ الحمامات من الاماكن التي يجب ان تكون نظيفة دائماً و احيانا نظافة الحمامات تعتمد علي عدم توازن البلاط و بالتالي تقف المياه ولا تسير في اتجاه الصرف و تلك الاخطاء تكن بسبب الالتوائات الموجودة في البلاط و السبب الاساسي هي الصناعة، يجب ايها الاخ القارئ ان تنفق ما في جيبك من اجل اختيار افضل انواع البلاط من حيث جودة البلاطة الاساسية في الصنع و من حيث الالوان.شركة تسليك مجارى بالمدينة المنورة
    شركة تنظيف بحفر الباطن

    المواصفات التي يمتلكها البلاط و السيراميك الذي يتواجد لدينا

    ReplyDelete
  22. Wow, that’s what I was exploring for, what a data! present here
    at this weblog, thanks admin of this web page.

    shareit for pc
    xender for pc

    ReplyDelete
  23. Do you require HP printer setup for your mac operating system? Is your printer driver not suitable for macOS? Then visit the 123.hp.com/setup to get the software and driver for better functioning of your printer. You can also call our expert HP support team for services.

    ReplyDelete
  24. This is a very informative article. I also agree with the title of your post and you explain well your point of view. I am very happy to see this post. Thank you for sharing with us.
    Maintain and share more related posts.
    tikiqq
    vipbandarq
    walipoker
    wargaqq
    zeuspoker
    zoyaqq
    daftar poker ip pro
    kumpulan situs judi terbaik
    daftar situs judi terpercaya
    daftar poker

    ReplyDelete
  25. I do consider all the ideas you have presented on your post. They're really convincing and will certainly work. Packers And Movers Bangalore

    ReplyDelete
  26. very nice <a href="http://www.motivation456.com/happy-new-year/happy-new-year.html>happy-new-year</a>

    ReplyDelete
  27. Happy New Year 2020

    In this detailed article, the readers will be showered with everything related to the New Year’s Event of 2020 such As New Year Wishes and Greeting to wish their friend and family, New Year Resolution Ideas, New Year Quotes, Pictures, Status, New Year Countdown moment information, and much more.
    Happy New Year Wishes
    Happy New Year Quotes

    ReplyDelete
  28. Free yourself from Happiness and scowl for the New Year has at long last come to town. Have an upbeat and sound New Year! May every one of your desires work out and a cheerful New Year to you! Roses are red, violets are blue, it's gathering time, upbeat New Year to you! Have an incredible Click Here Have an insane, shaking, energizing and mysterious New Year 2020! New love, new do, new handbag, new undertakings, new you. May the coming year be an incredible accomplishment for you. Stunning New Year Wishes , Happy new year 2020 photo download

    ReplyDelete
  29. Great post! I really enjoyed reading it. Keep sharing such articles. Looking forward to learn more from you.
    Mobile app development company in mumbai

    ReplyDelete
  30. nice blog and i want to share one more good blog on happy new year 2020.

    ReplyDelete
  31. The New Year 2020 Animation helps you to share your best wishes to beloved people who are not near to you. You can also share the images in the social network for public greetings, many telecommunication advancements have made it easier to share among families and friends. The wallpapers can be used as PC wallpaper, mobile wallpaper can be sent as attachments. These wallpaper have many formats and dimensions.

    ReplyDelete
  32. That kind of blog people actually need by the way nice and detial guide keep it sharing more PPCexpo Best Reporting tool

    ReplyDelete
  33. Kalakutir has quality services for Play School Cartoon Painting and Van & Trucks Branding Wrap.
    Play School Cartoon Painting Services

    ReplyDelete
  34. Hi, constantly i used to check weblog posts here in the early hours in the morning, because i like to find out more and more. Beyhadh 2 Full Episode

    ReplyDelete
  35. SamsungMobileSpecs
    Samsung is one of the leading brands in the smartphones industry, Samsung mobile specs are providing a complete specification of Samsung phones & Samsung mobile prices with updated specs.

    ReplyDelete
  36. Order fuel online services in Hyderabad We delivery Petrol and diesel for your Cars and Bikes during emergency Hours. Easy Payment Options. Fast Safe and Reliable.Doorstep Delivery
    Petrol home delivery
    Mobile petrol pump
    buy petrol online

    ReplyDelete
  37. Thanks for providing good information. You can explore happy valentines day wishing material.

    Happy Valentine Day Message 2020

    ReplyDelete
  38. Nice article about 151-byte static Linux binary in Rust.

    ReplyDelete
  39. I rarely share my story with people, not only because it put me at the lowest point ever but because it made me a person of ridicule among family and friends. I put all I had into Binary Options ($690,000) after hearing great testimonies about this new investment

     strategy. I was made to believe my investment would triple, it started good and I got returns (not up to what I had invested). Gathered more and involved a couple family members, but I didn't know I was setting myself up for the kill, in less than no time all we had put ($820,000) was gone. It almost seem I had set them up, they came at me strong and hard. After searching and looking for how to make those scums pay back, I got introduced to maryshea03@gmail.com to WhatsApp her +15623847738.who helped recover about 80% of my lost funds within a month.

    ReplyDelete



  40. We are the best home services company in the Kingdom We provide cleaning services of the best equipment and manpower and transport services of the finest packaging and storage and 
    شركة تنظيف بالبخار بجدة"> شركة تنظيف خزانات بجدة
    شركة تنظيف بجدة
    شركة مكافحة حشرات بجدة
    شركة نقل عفش بجدة

    ReplyDelete
  41. Packers and Movers Gurgaon Provide Reliable, Safe and Certified Service Provider list, Get Free ***Best Price Quotaition and Compare Charges. ???Hassle free Household Shifting Services, High Quality packing Material, Office Relocation, Car Transportaion, ###Local and Domestic Shifting Service @
    Packers And Movers Gurgaon

    ReplyDelete
  42. Packers and Movers Ahmedabad - We Provide ***Best Service Providers, Safe, Reliable, Affordable, Trusted ###Movers and Packers in Ahmedabad List, Household Shifting, Office Relocation: Choose Top Verified Packers and Movers Ahmedabad Compare ???Shifting Service Chrages, Price Quotation, Rate List Charts and Save Money and Time @ Packers and Movers Ahmedabad

    ReplyDelete
  43. Get Shifting/Relocation Quotation from ###Packers and Movers Delhi. Packers and Movers Delhi 100% Affordable and Reliable ***Household Shifting Services. Compare Transportation Charges and Save Time, Verified and Trusted Packers and Movers in Delhi, Cheap and Safe Local, Domestic House Shifting @
    Packers And Movers Delhi

    ReplyDelete

  44. Kia Australian Open will be played at Melbourne in Australia, hence domestic viewers as well from All over Australia can watch the Australian Open 2020 TV Coverage on Nine Network.

    ReplyDelete
  45. CROWNQQ I AGEN BANDARQ I BANDARQ ONLINE I ADUQ ONLINE I DOMINOQQ TERBAIK

    Yuk Buruan ikutan bermain di website Agen BandarQ

    Sekarang CROWNQQ Memiliki Game terbaru Dan Ternama loh...

    9 permainan :
    => Poker
    => Bandar Poker
    => Domino99
    => BandarQ
    => AduQ
    => Sakong
    => Capsa Susun
    => Bandar 66
    => Perang Baccarat (NEW GAME)

    => Bonus Refferal 20%
    => Bonus Turn Over 0,5%
    => Minimal Depo 20.000
    => Minimal WD 20.000
    => 100% Member Asli
    => Pelayanan DP & WD 24 jam
    => Livechat Kami 24 Jam Online
    => Bisa Dimainkan Di Hp Android
    => Di Layani Dengan 5 Bank Terbaik
    => 1 User ID 9 Permainan Menarik

    Ayo gabung sekarang juga hanya dengan
    mengklick daftar crownqq

    Link Resmi CrownQQ:
    RATUAJAIB.COM
    RATUAJAIB.NET
    RATUAJAIB.INFO

    BACA JUGA BLOGSPORT KAMI:
    BLOG ARTIKEL
    CROWNWIN
    CERITA DEWASA

    Info Lebih lanjut Kunjungi :
    WHATSAPP : +855882357563
    LINE : CS CROWNQQ
    TELEGRAM : +855882357563

    ReplyDelete
  46. RajaBandarQ
    Adalah website yang paling digemari saat ini oleh para pecinta judi online
    Dengan adanya 8 game terbaik yang disediakan oleh pihak website RajaBandarQ , akan banyak mengundang para pecinta judi poker online untuk bermain diwebsite RajaBandarQ

    9 Game Yang disediakan oleh pihak RajaBandarQ diantaranya adalah :

    * AduQ
    * BandarQ
    * Bandar Poker
    * Bandar 66 ( New Games )
    * Capsa Susun
    * Domino QQ
    * Poker
    * Sakong
    * Perang Baccarat ( New Games )

    Keunggulan jika bergabung di website RajaBandarQ :

    - Proses Deposit dan Withdraw Hanya 2 Menit
    - 100% Mudah Menang & Fairplay Game
    - Minimal Deposit & Withdraw Rp 20.000,-
    - Bonus Rollingan 0.3% (Tanpa Syarat)
    - Bonus Referral 20% (Seumur Hidup)
    - Bonus Extra Refferal
    - Sistem Keamanan Terbaru
    - Support 6 Bank Local ( BCA , BNI , BRI , CIMB NIAGA , DANAMON , MANDIRI )

    Kami Memberikan Bukti Bukan Janji !!!

    Baca Juga Blogger Kami :

    - Blogger : Cerita Dewasa

    - Blogger : Raja Berita889

    - Blogger : Bandar Berita Harian

    - Blogger : Panduan Judi Online

    - Blogger : RajabandarQ

    - Blogger : Berita Online Terapdate

    - Blogger : Berita Kesehatan

    Tunggu apalagi ? Daftarkan diri anda segera juga dan menangkan jackpot jutaan rupiah hanya dengan modal Rp 20.000,-
    Hanya Di RajaBandarQ

    Contact Us:
    Live Chat : RajaBandarQ
    Whatsapp : +855-88-2290-441
    Telegram : +855-88-2290-441
    Line : cs_rajabandarq

    Join : >>DAFTAR RAJABANDARQ<<

    ReplyDelete