Octave brainstorm

Questions will appear here!

28/04: spent much time this week struggling to get it to run on Ubuntu 22.04, both on my local machine and in a Dockerfile. I'm very close though, so expect a PR with a working Dockerfile soon. I should report all three existing ones aren't functional though... Well, the Ubuntu one builds nicely, but the allocscc command in the README complains about missing headers unless ran with allocscc -I/usr/local/src/liballocs/include -I/usr/local/src/liballocs/contrib/libsystrap/contrib/librunt/include -I/usr/local/src/liballocs/contrib/liballocstool/include -o test test.c. Also, ELFTIN must be set in the env else allocscc complains, and that one could fallback to a relative path of ../../contrib/elftin/ if the variable isn't in the env.

• all sounds good -- good work!

I've also got a few random potentially useful (but dreadfully boring) notes regarding building like it breaking with more recent versions of OCaml and gcc/g++. More annoyingly, have to remove stream_err and __addrmap_max_stack_size from librunt.c to avoid a conflict with liballocs.c which prevents building otherwise, on Ubuntu 22.04 at least. __attribute__((weak)) would probably work and be cleaner, not sure why it's needed in the first place though. Anyway.

• Hmm, yes. I think __addrmap_max_stack_size should be just in liballocs, but possibly they should each have their own stream_err.

pycallocs code looks nice and hacking-prone since it doesn't seem to be mystical and lacking in comments, so that's great! Can build but not test it yet, since I can't build libcrunch at all and it uses very few features from it. What's this heap_index.h header libcrunch imports but that's nowhere to be found?

• Whoops. That header is now removed from liballocs but I haven't forward-ported libcrunch yet -- my bad. I was forgetting that pycallocs uses it. Most of the stuff is in allocmeta.h or generic_malloc_index.h. The rationale is that each 'heap allocator' is really a distinct allocator that in principle needs its own header.

As for actual (basic so far) liballocs questions:

• why is there a need for allocscc? It's quite complex, there's a lot going on with it. AFAIK it exists to leverage CIL/cilly heavily, but I'm not sure you ever explain why that's the case. Instrumentation as described in Documentation/overview-toolchain.txt, I assume?
  • Yes, I'm currently removing it in favour of something simpler. Something of this kind is needed because we do instrument some C code at source level (e.g. alloca) and alter how it is compiled (e.g. -fno-function-sections) and how it is linked (e.g. to include malloc wrappers) and also the dynamic linking set-up (allocsld.so is the dynamic linker). But I have a new approach (see 'toolsub' repository) that is overall simpler, and some of the work can be done in linker plugins. As well as overview-toolchain.txt, 'malloc-indexing.txt' is worth a look (be prepared for horror).
• how is this instrumentation done in practice, in detail? I assume that's how libsystrap comes into play.
  • Yes although that is the simplest kind of instrumentation, just for system calls. I think this means I should work on the documentation so that it itemises what kinds of instrumentation are done. Basically all syscalls that 'might' be interesting are clobbered into ud2 instructions and run in a SIGILL handler. This is indeed what libsystrap handles. One of my big to-do items is to be more selective about this syscall instrumentation and also cache the instrumentation points in the filesystem, since there is a noticeable startup delay from scanning all instructions as they are loaded. I used to avoid this with mega-hacks (knowing roughly where in libc was important to trap) but that has been invalidated by time, so currently it does the expensive thing.
• curious about fake-libunwind and why it's needed
  • Using 'real' libunwind (which uses DWARF frame information) used to be slower than -fno-omit-frame-pointer and the fake libunwind (which was just a really simple/fast stack walker using frame pointers). There probably still is some time penalty, but I am worrying about it less for the moment. I want to integrate the 'compiled frame information' work from OOPSLA 2019, which will definitely eliminate the problem, but that is not done yet. Basically it would mean generating a further kind of metadata, 'compiled' from the DWARF frame information. Though a modified libunwind is still needed in that case. Probably this should be vendored locally and linked privately into liballocs.

03/05: More build related questions, since I'm running out of time and I don't quite have everything running like I want it to, even now :(

For running with the latest liballocs version (within the latest Docker container): I can build it, as described previously, but no dice for libcrunch. A make fails at the end, spending ages and much CPU effort on allocsld: jumping to system ld.so entry point 0x555555557090 with rsp 0x7fff73e964b0 before segfaulting. See trace

LD_PRELOAD="/home/user/libcrunch/src/libcrunch_preload.so" ./hello
Hello from allocsld!
We think we are not the program
AT_PHDR is 0x5615b2a00040
AT_PHENT is 0x38
AT_PHNUM is 0x7
AT_BASE is 0x555555556000
AT_ENTRY is 0x5615b2a00db0
AT_EXECFN is 0x7fff73e97ff0 (./hello)
allocsld: jumping to system ld.so entry point 0x555555557090 with rsp 0x7fff73e964b0
Segmentation fault (core dumped)

Only diff with master is

+//#include "heap_index.h"
+#include "generic_malloc_index.h" 

as discussed, and I suppose this in the frontend/c Makefile if you care

-OCAMLFLAGS += -I $(dir $(THIS_MAKEFILE))/lib -I $(LIBALLOCS_BASE)/tools/lang/c/cilallocs #-I $(dir $(wildcard $(shell which $(CILLY))/../lib/ocaml/*/cil))
+OCAMLFLAGS += -I $(dir $(THIS_MAKEFILE))/lib -I $(LIBALLOCS_BASE)/tools/lang/c/cilallocs -I /usr/local/src/liballocs/contrib/cil/lib/cil/

Can't run pycallocs without a working libcrunch_preload.so, I'm afraid.

• Yes. This isn't going to work on current liballocs until I forward-port libcrunch. I had forgotten that pycallocs uses libcrunch at all. It may be best to eliminate that dependency but again that is one for me.
  • understandable, libcrunch is barely used in it. Its only use is when getting the initial length of an address proxy (https://github.com/Sakarah/pycallocs/blob/master/address_proxy.c#L218)
    • OK, good find. In that case you could investigate copying across the code for those two libcrunch calls (it probably still works with no or minimal changes), up to you.
      • I remember considering that and thinking it would be harder than it looked, but I can't recall why. I'll give it a try

For running with an older liballocs version (90b819a6b04be18977772294c502fbcbc3a1675a):

Tried building liballocs with a version from 2019 which I assumed may work better. Here's a Dockerfile patch for it (the sed shenanigans are because git config --global url."https://".insteadOf git:// never worked for some reason)

• yes, GitHub-side changes mean that 'git://' no longer works
  • yeah, but neither does the git config command, which would have saved me some .gitmodules hacking. I think git config --global isn't very compatible with Dockerfiles, maybe.
    • Ah, silly me -- understood.

diff --git a/buildtest/ubuntu-18.04/Dockerfile b/buildtest/ubuntu-18.04/Dockerfile
index b1d5499..2bcb394 100644
--- a/buildtest/ubuntu-18.04/Dockerfile
+++ b/buildtest/ubuntu-18.04/Dockerfile
@@ -1,7 +1,7 @@
 FROM ubuntu:18.04
 
 ARG user
-RUN apt-get update && apt-get install -y sudo
+RUN apt-get update && apt update && apt-get install -y sudo
 RUN adduser ${user:-user} && \
     echo "${user:-user} ALL=(root) NOPASSWD:ALL" > /etc/sudoers && \
     chmod 0440 /etc/sudoers
@@ -26,6 +26,11 @@ RUN sudo apt-get install -y libelf-dev libdw-dev \
        libunwind-dev libc6-dev-i386 zlib1g-dev libc6-dbg \
        libboost-iostreams-dev libboost-regex-dev libboost-serialization-dev libboost-filesystem-dev
 RUN cd /usr/local/src && git clone https://github.com/stephenrkell/liballocs.git
+RUN cd /usr/local/src/liballocs && git checkout 90b819a6b04be18977772294c502fbcbc3a1675a
+RUN cd /usr/local/src/liballocs &&  \
+    sed -i 's/git:\/\//https:\/\//g' .gitmodules && \
+    git submodule update --init && \
+    find . -name ".gitmodules" -type f -exec sed -i 's/git:\/\//https:\/\//g' {} \;
 RUN cd /usr/local/src/liballocs && \
    git submodule update --init --recursive && \
    make -C contrib -j4

...however, this command (also in the Dockerfile) fails: make -f tools/Makefile.meta /usr/lib/meta/lib/x86_64-linux-gnu/libc-2.27.so-meta.c. Quite a bit going on in that Makefile and related scripts, so not confident I can debug it efficiently. Far as I can tell, it could all be caused by the file /lib/x86_64-linux-gnu/.debug/libc-2.27.so not being properly created. Anyway, if you have any idea why it'd not be functional, that'd be great. Alternatively, if you have a docker image laying around with a working libcrunch, that could work too.

• OK, this is quite a lot easier to fix. The file you mentioned should be in the libc6-dbg package from Ubuntu. Can you get a shell on the Docker image and investigate what's in that package? Basically for every executable file /path/to/F, tools/Makefile.meta knows how to build a file /usr/lib/meta/path/to/F-meta.so and this is where its metadata (type information, allocation site information, etc) resides. The main thing needed is the DWARF information for the original file, here /lib/x86_64-linux-gnu/libc-2.27.so. The scripts seem to think it is in /lib/x86_64-linux-gnu/.debug/libc-2.27.so but perhaps that is not the case in later versions of Ubuntu 18.04 (sadly not a 100% stable target).
  • oh, it'd be that simple? I thought it was going to be more complex since I assumed /lib/x86_64-linux-gnu/.debug/libc-2.27.so was meant to be a metadata-related file generated by liballocs, hence the .debug. If it's just failing to find libc (which is in /lib/x86_64-linux-gnu/libc-2.27.so, if I recall correctly) that's much easier. Will give it a shot shortly or tomorrow.
    • Be aware of the "split debug info" set-up: it's not the glibc binary file that is needed, but the "separate debug info" file for it. There are a few different conventions for locating a separate debug info file for a given base file, one of them being the '.debug' path component... I have coded these up in liballocs/tools/debug-funcs.sh and liballocstool/src/stickyroot.cpp (try searching for the string '.debug' in these). Perhaps backporting a fix from latest liballocs will get the older liballocs working here. E.g. it may be that Ubuntu switched to the 'build ID' method... though I had thought even fairly old liballocs tools should be able to cope with that. I often use a command like . /path/to/liballocs/tools/debug-funcs.sh && read_build_id $file when investigating stuff like this. Under /usr/lib/debug the first two characters of the build ID name a subdirectory, and the rest are in the filename.
      • problem seems fixed, it was not using the right build id for some reason. Thanks for the resources, the file that I had to ugly-patch was pretty much the old version of liballocstool/src/stickyroot.cpp. The test.c example segfaults though, so this version doesn't seem to work, will need to try with another
        • Getting to a segfaulting client binary is 90% of the way there! Can we debug this problem? Attaching gdb at startup often doesn't work, but if you set LIBALLOCS_DELAY_STARTUP=1 and then use gdb -p $(pidof test) you have a good chance of attaching. If you can get a backtrace then I can probably help fix this.
          • Will gladly take the help! However, no guarantee that this version will work with pycallocs in the first place, so that might be a bit of a waste of time. Since we're meeting next Monday, I'll probably focus on getting the latest version of liballocs to report macros and their values somehow, to make some tangible progress on the pycallocs macros idea even if I can't get a working build of pycallocs in time (realistically, that sounds likely). If I don't get back to you by Monday on that bit, we can take a look at that segfault during the call, maybe.

As for actual liballocs questions:

• pageindex.c is for the allocator tree, I assume? It's hard to parse since it's quite long, but the term "bigalloc/bigallocation" stands out to me. What is that referring to in this context?
  • The tree really consists of allocations, not allocators, although some of my writing is guilty of not being accurate about this since it eases exposition. A big_allocation means an allocation that is explicitly represented in the tree. All but the very deepest-level (smallest) allocations have a bigalloc record, and these are linked together into a tree. For example, given a bunch of malloc chunks, there is a big_allocation representing the malloc arena. There is no big_allocation for the chunks themselves because we rely on the allocator being able (or being instrumented) to identify its own 'small' chunks. Above the arena in the tree, there is another bigalloc for the memory mapping that holds the arena. The pageindex is a structure for shortcutting the lookup through the tree: it points to the deepest bigalloc that fully spans any page-sized region of the address space.
    • oh, it is clear that it consists of allocations, don't worry. You do call it an allocator tree in your paper, though, now that you mention it. Is it fair to view a big allocation as a page or any allocation bigger than a page, then?
      • Almost but not quite! The invariant is not quite that tight. Consider a malloc chunk that happens to be 4096 bytes or more. It is not necessarily promoted to a bigalloc. Promotion is only necessary if there need to be additional allocations hanging beneath it in the tree. So, if you did a big malloc and then used that chunk as the arena for another (nested) allocator, we would need a bigalloc record for the big chunk
        • makes sense!

---

Hey Stephen, I believe you explained it in a previous call, but I'm confused about why liballocs.so is needed in the first place. An implicit linker script that essentially just exists to force the linker to always get the symbols in liballocs_dummyweaks.so as opposed to... well, elsewhere? In my case, the CPython extension relies on liballocs.so, so why can't liballocs_dummyweaks.so be relied upon instead? (or liballocs.a, for that matter, which it doesn't seem to like) As odd as it feels to try to rely on the dummyweaks stubs instead, isn't that essentially what liballocs.so is doing? I'm misunderstanding a basic, but seemingly interesting (and seemingly evil) feature here. (minor edit 2 on top of the further one: another case of me answering my own questions. It can actually be built with liballocs_dummyweaks.so instead of liballocs.so, although I'm not sure it can be ran with it. And it doesn't like liballocs.a because of missing symbols not included in that static lib. Which does beg the question though, could it potentially be built with liballocs.a instead of liballocs.so? Which boils down to asking once again what liballocs.so is for. Which you have explained, and I should have taken notes)

This is also relevant since I need to rely on the lifetime policies code for pycallocs to have access to it (else we get undefined symbol: __liballocs_detach_lifetime_policy), and I'm struggling to modify the build pipeline so that it can indeed access them. Or rather I feel my changes should guarantee it finds those symbols, but it doesn't, so my understanding of how the libs/build targets all work is lacking in some way. (ooh nevermind, I see the issue. I was building without preloading liballocs, missing the fact that I removed it preloading with libcrunch, AND that libcrunch encapsulated the liballocs code as indicated in the liballocs/src Makefile by it needing a static lib liballocs.a. It now builds! And segfaults unsurprisingly. So that question doesn't need answers anymore, I understand now why my changes had no impact)

Also, not directly relevant to liballocs but while I'm at it, cilly seems to dislike the -g3 flag, as it omits my user-defined macros (think #define ABC "test macro") from the final code, while gcc works just fine. I'll take a deeper look once I fix the previous issue, but maybe you'll have some idea why that is. (later note to self: probably just cilly instrumenting the file and so discarding dummy macros)

22/05: Possible liballocs bug report:

$ LD_PRELOAD=/usr/local/src/liballocs/lib/liballocs_preload.so ls
ls: Saw ld.so with a hole in... checking the middle chunk is free
ls: Saw ld.so with a hole in... mapping the middle chunk
Segmentation fault

Even if ls wasn't compiled with allocscc, this shouldn't segfault, should it? No such segfault with echo "hi" but I assume that does not even need to perform an allocation, so it's no wonder. Will open an issue if this doesn't seem normal. Relevant since I rely on liballocs_preload.so with pycallocs, and I call it as such: LD_PRELOAD=/usr/local/src/liballocs/lib/liballocs_preload.so ../venv/bin/python3 $*; which, as mentioned, crashes. Based on the original pycallocs command which was the exact same, except that it relied on libcrunch_preload.so.