Wandering Thoughts

2022-09-15

The C free() API gives libraries and functions useful freedom

A while back I wrote about how free()s API means that (C) memory allocation has to save some metadata, either explicitly or implicitly, because you don't pass in the size of what you're freeing. I happen to feel that this is still a decent API for C, but beyond that there's another little advantage to this API, which is that no one needs to know how big an allocated object is. There are at least three uses for this.

The first use is the one traditionally used by advanced C memory allocation systems. Many allocations (especially for small sizes) will have their size rounded up a bit, leaving extra unused space behind the returned object. If this object is then passed to realloc(), it's possible for it to be reallocated larger in place, without any memory copying having to be done. The realloc() API specifically allows this behavior, and doesn't require that a different pointer be returned than was passed in.

(Realloc can also be used to shrink the allocation, which can easily be done in place, although I think that usage is a lot less common.)

The second use is that a library can (theoretically) transparently expand the size of an object that it returns and that you free later yourself, especially if the object and its size is completely opaque. Similarly, a library can actually return several differently sized objects that you treat uniformly; as far as you're concerned they're a black box that you eventually call free() on. There are some cautions in practice, since C programmers have traditionally been very ingenious about finding ways to actually depend on the size of the thing you return.

(C strings are kind of this; things that return dynamically allocated strings generally don't promise that they'll be any specific size.)

The third use is what some people proposed as the solution to how malloc() and free() affect C APIs in the case of gethostbyname(). Although a 'struct hostent' contains pointers to various other things, you can pack all of those things together into a single memory allocation that has the 'struct hostent' at the start (effectively you allocate a little arena and then manually manage it). Because this is a single memory allocation, you can return a single pointer to it and the caller can still free everything with a single call to free(). I'm not convinced that this is a good API, but it's certainly one that free()'s API makes possible.

CFreeGivesReturnFreedom written at 22:17:15; Add Comment

2022-09-10

C's malloc() and free() APIs are reasonable APIs for C

I've written about how the free() API means that C memory allocation needs to save some metadata, and before that about the effects of malloc() and free() on C APIs. However, despite these issues I think that C's malloc() and free() APIs are reasonable ones for C to have, and probably that they've helped C remain relevant over the years.

To start with, both malloc() and free() have what I could call a minimal API, where they take only the arguments that are really needed; in the case of both, this is one argument each. You can't allocate memory without saying how much in some way, and you can't free memory without saying what to free, so it's hard to get a smaller API without some form of automatic handling of memory (including Rust's automatic lifetime management). Having memory allocation as an explicit API has also meant that you can readily write C code that doesn't allocate memory (except on the stack), or use entirely different allocation functions that you built yourself. Both OS kernels and embedded code tend to use something completely different from malloc() and free().

That you don't have to pass a length (or any other qualifier) to free() is also a good fit with C's approach to strings, which don't have an explicit length field. Certain sorts of C code frequently deal with allocated strings of uncertain length and wind up freeing them; if free() required an explicit length, there would be a lot of additional strlen() calls. I think that the C malloc() and free() API (and realloc()) is a quite good fit as a simple string-focused memory allocator.

That C's memory allocation APIs are so minimal has allowed for a lot of experimentation with some approaches to memory allocation. There are a lot of more complicated allocators that can be hid behind the C API, for things like size class based allocation and so on. A more feature-rich API (for example, one that had an explicit idea of 'arenas') might have foreclosed certain sorts of internal implementations, or at least made them more complicated.

(It's worth noting at this point that on most Unixes, the internals of C memory allocation were completely changed over the course of time, from sbrk() to mmap(). Nothing really noticed.)

Within the constraints of being a simple and general API and allowing relatively simple and efficient implementation on small systems (which is what Unix and C started on), I think that malloc(), free(), and their friends are at least a decent API. They've certainly proven to be remarkably durable and functional; although there are alternate implementations (and modern C libraries generally use much more complicated approaches), no alternate API has really caught on.

(Well, at least on Unix. My knowledge of Windows, macOS, and mobile environments is limited.)

CMallocFreeDecentAPI written at 22:09:13; Add Comment

2022-09-01

Go 1.19 added an atomic.Pointer type that's a generic type

In Go 1.18, the Go developers were careful to keep generic types out of the standard library, to the point where they decided not to have a 'constraints' package of generics helpers in the standard library, never mind generic versions of slices and maps. As the Go 1.18 release notes say, all three packages were instead put under golang.org/x/exp. However, Go 1.19 turns out to have somewhat quietly changed that, adding the standard library's first public generic type in sync/atomic's new atomic.Pointer[T any] type.

The atomic.Pointer type is a type-safe atomic pointer to a *T, with the type safety assured at compile time. You could previously do atomic pointers through atomic.Value, but that was only type safe at runtime and might panic if you violated type safety (and storing a nil in one was complex (but possible)). The appeal of atomic.Pointer as a generic type is pretty obvious and it also seems unlikely that you could design a better generic type or a better API than the one it uses (which atomic.Value had from Go 1.4 and Go 1.17 (for .CompareAndSwap())). I suspect that all of this adds up to why it was considered safe to add to the standard library in Go 1.19, and thus commit Go to having it there as part of the compatibility guarantee.

The background and discussion for this is in issue $47141, Updating the Go memory model and issue 50860, sync/atomic: add typed atomic values. Also, the commit message has some interesting additional details. Apparently using these new atomic types, including atomic.Pointer[T], will generally compile down to the relevant assembly level atomic instructions.

I'm not sure why I overlooked that this was added in Go 1.19 until now; I would have thought I'd pay more attention to the first generic type in the standard library. The Go 1.19 release notes mention it vaguely in New atomic types but don't specifically call out that it's a generic type; however, the Go 1.19 release announcement does specially talk about atomic.Pointer[T], making it pretty clear that this is a generic type.

Sidebar: Storing a nil in an atomic.Value

As the documentation says, atomic.Value will panic if you call .Store(nil). However, Store takes an 'interface{}' (now called 'any'), which means that you can pass it a concretely typed nil and it will accept it:

var i int
var p *int
var m atomic.Value

m.Store(&i)
// Both of these are accepted
m.Store(p)
m.Store((*int)(nil))

If you look at it from the right direction, this is part of how nil is typed in theory but not always in practice. One way to put it is that if atomic.Value is handed a pure nil, the nil is functionally untyped, which means that atomic.Value can't verify that it's the 'right' type of value (or use it to establish the type).

GoSyncAtomicPointerGeneric written at 22:48:40; Add Comment

2022-08-17

Some resources for looking at the current development version of Go

Go is under more or less continuous development (although the pace and nature of changes is different near releases). The Go website, Go playgroup, and other resources are what you want if you're interested in the latest released version of Go, as most people are, but there are also some resources if you want to look at the latest development version, what is generally called the tip.

The official source code is at go.googlesource.com. Typically you'll want to look at the tree view of the main branch. There's also the Github mirror of Go, which is where the issues are and which may be more convenient to navigate. Getting your own local copy is straightforward, as is building Go from source.

Tip.golang.org is more or less what it sounds like. Generally I'll want the Go documentation, especially the Go language specification. Tip.golang.org has a link for the latest standard library documentation, which goes to pkg.go.dev/std@master. You can also directly look at the specification from your local source tree, in doc/go_spec.html, but it probably won't have formatting that's as nice. At the moment, godoc can be used to run a local web server to view the standard library documentation for a Go source tree (or perhaps only the source tree that it was built from, in which case you'll want to build the latest Go development version yourself).

(You can also use pkg.go.dev to get access to all tagged versions of the Go standard library documentation, which includes betas and release candidates as well as actual released versions.)

Famously and usefully, Go has the online Go playground. As I write this there are two ways to get a playground with the Go tip version. First, you can pick 'Go dev branch' from the version dropdown on the normal playground. Second, you can use gotipplay.golang.org. I believe the two are functionally equivalent, but the latter specifically tells you what development version it's using and also runs 'go vet' on your code as part of submission.

(The normal playground will also let you use the two currently supported Go versions to try things with, which is currently Go 1.18 and Go 1.19.)

If you want to look at the generated assembly code for something, the Godbolt Compiler Explorer is what you want. There are two ways to get the Go version; you can select 'Go' from the language dropdown on the main page, or go straight to go.godbolt.org. To get the development version of Go you need to select eg 'amd64 gc (tip)'; 'gc' is what the Compiler Explorer calls the usual Go toolchain, as opposed to gccgo.

If you want to use, try, or test with the latest Go development version, you may be interested in the gotip command. An interesting feature of gotip that's not available by just cloning the source repository and building locally is that it can build Go with a specific CL (what Go calls its pending changes). This may be useful if a Go bug report says that a specific CL may fix an issue you're seeing; you can (in theory) use gotip to build that CL and then use it to try your code.

I believe that the Go team is in the process of moving away from golang.org in favour of go.dev, so at some point the golang.org URLs here may stop working. Hopefully there will be go.dev equivalents of them, ideally with redirections from eg tip.golang.org to the new go.dev version.

(This is the kind of thing I write down for myself so I can find it again later.)

GoDevelopmentTipResources written at 21:30:14; Add Comment

2022-08-13

The C free() API means memory allocation must save some metadata

Here's something that I hadn't really thought about until I was thinking about the effects of malloc() and free() on C APIs: the API of free() in specific more or less requires a conventional C memory allocator to save some metadata about each allocation. This is because free() isn't passed an explicit size of what to free, which implies that it must get this information from elsewhere. The traditional way the C memory allocator does this is to put information about the size of the allocation in a hidden area either before or after the memory it returns (often before, because it's less likely to get accidentally overwritten there).

(That C memory allocators store the size of allocations they've handed out is clear to anyone who's read through the small malloc() implementation in K&R.)

This free() API isn't the only way it could be; a less convenient version would be to pass in an explicit size. But this would be a pain, because in practice a lot of C allocations are variable-sized ones for things like (C) strings. The C free() API is in a sense optimized for blind allocations of variable sized objects. It also allows for a more straightforward optimization in realloc(), where malloc() can round up the size you requested, save that size as the metadata, and then realloc() can expand your nominal allocation into any remaining free space if possible. So there's pretty strong reasons for free() to not require a size even if it normally requires some extra allocator overhead.

Of course you can build C memory allocators that avoid or amortize this overhead, mostly obviously by having free() never do anything (some programs will be perfectly fine with this and it's very fast). A slab allocator that uses size classes doesn't need size metadata for individual allocations that fall into size classes, because the size of an individual allocation is implicit in being allocated in a particular size class's arena. More broadly you can have an allocator interface where programs can set all future memory allocations to come from a particular arena, and then promise to de-allocate the arena all at once and not care about free() otherwise (letting you make free() a no-op while there's an active arena).

(Talloc is an explicit arena setup, as opposed to the implicit one I described, but of course this is an option too.)

CFreeRequiresMetadata written at 21:16:53; Add Comment

2022-08-06

The pervasive effects of C's malloc() and free() on C APIs

In my entry on the history of looking up host addresses in Unix, I touched on how from the beginning gethostbyname() had an issue in its API, one that the BSD Unix people specifically called out in its manual page's BUGS section:

All information is contained in a static area so it must be copied if it is to be saved. [...]

This became a serious issue when Unix added threads (this static area isn't thread safe), but was seen as a problem from the very beginning. Given that the static return area was known as an issue, why was the API written this way?

While I don't know for sure, I think we can point fingers at the hassles that dynamic memory allocation brings you in a C API. The gethostbyname() API returns a pointer to a 'struct hostent', which is (from 4.3 BSD onward):

struct  hostent {
   char  *h_name;     /* official name of host */
   char **h_aliases;  /* alias list */
   int    h_addrtype; /* address type */
   int    h_length;   /* length of address */
   char **h_addrs;    /* list of addresses */
};

If this structure is dynamically allocated by gethostbyname() and returned to the caller, either you need an additional API function to free it or you have to commit to what fields in the structure have to be freed separately, and how (ie, this is part of the API). Having the caller free things is also not all that simple. Since this structure contains embedded pointers (including two that point to arrays of pointers), there could be quite a lot of things for the caller to call free() on (and in the right order).

This issue isn't unique to gethostbyname(); it affects any C API that wants to return (in a conceptual sense) anything more complicated than a basic type or a simple structure (even in old C, simple structures can be 'returned' by passing a pointer to the structure to the function, as is done in stat()). C offers no good solution to the problem; either you add one or more 'free' functions to your API (one per dynamically allocated structure you're returning), or you document and thus freeze the process for freeing what you return, or you do what BSD opted to in gethostbyname() and return a pointer to something static.

(Documenting what callers have to free implies that you can't later add extra fields to what you return unless they don't have to be freed separately.)

In POSIX, this API issue was eventually worked around with the first approach, when they added a freeaddrinfo() function to go with the new getaddrinfo(). This is the only particularly good solution, but it does mean that you get an increasing profusion of 'free something' functions, which serves as a disincentive to add APIs which would return something where you'd need such a function.

CAPIsEffectsOfMalloc written at 21:41:36; Add Comment

2022-07-28

Print based debugging and infrequent developers

I've long been an enthusiastic user of print based debugging, although I did eventually realize that I reach for a debugger when dealing with certain sorts of bugs. But print based debugging is eternally controversial, with any number of people ready to tell you that you should use a debugger instead and that you're missing out by not doing so. Recently I had a thought about that and how it interacts with how much programming people do.

I have in the past written about the division between frequent developers and infrequent developers. Frequent developers (in a particular language, IDE, or whatever) are people who routinely program in that environment and spend a lot of time on it. Infrequent developers in something only dip into it every so often. This division matters because of the famous XKCD 'is it worth the time table'; frequent developers are clearly in an entirely different area of the table than infrequent ones.

One of the great advantages of print based debugging for the infrequent developer is that it requires essentially no extra knowledge. We almost always know how to print things in the language, and we have to know how to build and run the software in order to work on it. The extra learning required to do print based debugging is basically nil. This is not the case for debuggers; even the best debugger, one that sticks as close as possible to the language's syntax, has some extra things we need to learn and then to try to remember over time.

For a frequent developer the tradeoffs are much different (as they are with any specialized support tool). They'll use the debugger frequently enough (and often enough) that it will both save them significant time (if it's a good debugger) and stick in their memory so they don't have to keep re-learning it periodically. Spending the up-front time to learn the debugger is an investment that will easily pay itself back.

(There are frequent developers that still prefer print based debugging, but I think they have different reasons than infrequent developers for this.)

Now that I've had this thought, I also suspect that conversations between infrequent and frequent developers about print based debugging and debuggers are likely to be like ships passing each other in the night. I doubt it's the entire story of the disagreement over how to debug programs, though, and certainly I still suspect that it has a lot to do with the sort of bugs you deal with.

(But now I'm not going to feel so annoyed at myself at 'being lazy' about learning some debugger. I'm an infrequent developer these days, so the time tradeoffs are mostly not worth it unless it's very easy to start up the debugger and be productive with it.)

PrintDebuggingAndInfrequentDevs written at 22:27:25; Add Comment

2022-07-16

How to get (or recognize) a common Unix log timestamp format in things

One common form for timestamps in Unix log files is timestamps that come out looking like '2022-07-16 20:50:35', which is to say the date (in a sensible order) and then the time, with no timezone. Unless the program writing the logs is perverse, the timestamp is in the system's local time (whatever that is), not something fixed like UTC (of course the system's local timezone may be UTC). On a casual look around our systems, this is the timestamp format used by Exim and rspamd.

Go famously has a somewhat obscure approach to formatting and parsing timestamps, which pre-defines a number of common timestamp formats. However, this one is not one of them, and for reasons beyond the scope of this entry I recently wanted to recognize timestamps in this format in Go (more or less). To save myself looking this up in the future, the Go timestamp format for this is:

2006-01-02 15:04:05

(Since this timestamp doesn't have an explicit time zone, you'll probably want to specify one somehow so that your time.Time values get the right Location.)

A number of languages print and parse timestamps using a format based on the C strftime() and strptime() functions and their formatting (although the languages may not literally be using your C library functions for this). One example is Python's time.strftime. In strftime() formatting, this timestamp is:

%Y-%m-%d %H:%M:%S

Unsurprisingly, GNU Date accepts this as a date format in case you need to produce it in shell scripts. I believe that GNU Date will also automatically recognize it as an input time format for 'date -d ...'.

(My feeling is that this is a perfectly okay timestamp format. Yes, it omits the time zone, but I feel this is a sensible thing for logs written by a program in what is most likely a fixed time zone. One of our servers is pretty much guaranteed to never change its local time zone, and that local time zone is America/Toronto.)

PS: This is far from the only timestamp format found in the log files written out by various programs that don't send things to syslog, but it's the one I needed to deal with today and I lack the energy to inventory the time strings for all of them, even just in Go.

UnixLogTimestampsInThings written at 21:32:09; Add Comment

2022-06-25

A limitation on what 'go install' can install (as of Go 1.18)

As all people dealing with Go programs know or are learning, now that Go is module-only, the way you install third party Go programs from source is now 'go install <name>@latest', not the old way of 'go get <name>'. However, this is not always a completely smooth process that just works, because it's possible to have Go programs in a state where they won't install this way. Here's an illustration:

$ go install github.com/monsterxx03/gospy@latest
go: downloading github.com/monsterxx03/gospy v0.5.0
go: github.com/monsterxx03/gospy@latest (in github.com/monsterxx03/gospy@v0.5.0):
    The go.mod file for the module providing named packages contains one or
    more replace directives. It must not contain directives that would cause
    it to be interpreted differently than if it were the main module.

What is happening here is that internally, gospy uses packages from its own repository (module) and one of them, github.com/monsterxx03/gospy/pkg/term, in turn uses github.com/gizak/termui/v3. However, the github.com/monsterxx03/gospy module has a replace directive for this termui module that changes it to github.com/monsterxx03/termui/v3.

If you clone the repository and run 'go install' inside it, everything works and you wind up with a gospy binary in your $HOME/go/bin. However, as we see here 'go install ...@latest' works differently enough that the replace directive causes this error. To fix the problem (ie, to build gospy or any program like it), you must clone the repository and run 'go install' in the right place inside the repository.

(Alternately you can file bugs with the upstream to get them to fix this, for example by dropping the replace directive and directly using the replacement in their code. But if the upstream is neglected, this may not work very well.)

Unsurprisingly, there is a long standing but closed Go issue on this 'go install' behavior, cmd/go: go install cmd@version errors out when module with main package has replace directive #44840. This was closed more than a year ago in 2021 with a 'working as designed', and indeed the help for 'go install' explicitly says about this mode:

No module is considered the "main" module. If the module containing packages named on the command line has a go.mod file, it must not contain directives (replace and exclude) that would cause it to be interpreted differently than if it were the main module. The module must not require a higher version of itself.

(The apparent Go reference for why this exists is issue #40276, which I haven't tried to read through because I'm not that interested.)

Possible this will be changed someday, especially since it seems to keep coming up over and over again; issue #44840 contains quite the laundry list of projects that have hit this issue. Amusingly, one of the gopls releases hit this issue.

For now, if you're developing a Go program and you need to use replace directives in your go.mod during development, you'll have to do some extra work. One option is to strip the replace directives out for releases (and you need to make releases, because 'go install ...@master' won't work because of your replace directives). Another option is to switch to using Go workspaces for local development and drop the go.mod replace directives entirely. If you need to actually release a version of your program that uses the replacement module, well, you're out of luck; you need to actually change your code to explicitly use the replacement module and drop the replace directive.

GoInstallLimitation written at 22:25:17; Add Comment

2022-06-14

Go programs and Linux glibc versioning

Suppose that you build a Go program on one Linux machine, copy it to a second one, run it on that second machine, and get an error message like this:

./dlv: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.32' not found (required by ./dlv)
./dlv: /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.34' not found (required by ./dlv)

You might be puzzled. The direct explanation of what's going on is that you've built this Go program on a machine with a newer version of the GNU C library (glibc) than the second machine (for example, you built this program on a fast Ubuntu 22.04 compute server and tried to run it on an old Ubuntu 18.04 server, as I did here). For programs affected by this, the general rule of thumb is to build them on the oldest Linux distribution version that you expect to run them on.

At this point you might be confused; after all, Go programs are famous for being self-contained and statically linked. Well, usually they are but there are a surprising number of things that can make Go programs be dynamically linked. However this problem doesn't happen to all dynamically linked programs, just some of them. One answer for why is that it depends on what C library functions you use. Delve happens to indirectly use pthreads functions (somehow, I'm not sure exactly how), and these are the functions triggering this glibc versioning issue.

The more interesting and complex answer is that the GNU C Library has a complex system of symbol versioning for backward compatibility, known as 'compat symbols'. That's why there's two glibc versions being mentioned here instead of just one; Delve uses pthreads things that are at two different version levels in the system it was built on (Ubuntu 22.04 in this case). We can use the 'readelf' command line from that article to see what symbols Delve is depending on at each version level:

; readelf --dyn-syms -W dlv | fgrep GLIBC_2.32
27: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND pthread_sigmask@GLIBC_2.32 (7)
; readelf --dyn-syms -W dlv | fgrep GLIBC_2.34
 3: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND __libc_start_main@GLIBC_2.34 (4)
26: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND pthread_detach@GLIBC_2.34 (4)
34: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND pthread_create@GLIBC_2.34 (4)
50: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND pthread_attr_getstacksize@GLIBC_2.34 (4)

As we see here, even the libc start function is versioned. However and fortunately, you don't necessarily get the most recent version of it when you link a program. For example, another Go program compiled on the same Ubuntu 22.04 machine as dlv has:

; readelf --dyn-syms -W gocritic | fgrep __libc_start_main
43: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND __libc_start_main@GLIBC_2.2.5 (3)

This Go binary will run fine on our Ubuntu 18.04 machines, unlike the Delve binary. And of course a lot of Go binaries will be statically linked.

If you want to increase the number of your Go binaries that are statically linked, there are two options. The large scale and potentially damaging option is to build with 'CGO_ENABLED=0'. The problem with this is that some programs may not build or work well, or they may be missing features. In Delve's case, I believe that cgo is required for dlv trace's experimental ebpf support.

(Just turning off cgo apparently won't guarantee static binaries. If you want to build static binaries no matter what, see this 2020 comment and Go issue #26492.)

The more limited and flexible option is to eliminate the two most common causes of dynamic linking. This is done by using 'go install -tags osusergo,netgo ...', as covered in places like Martin Tournoij's Statically compiling Go programs. As far as I know there's no central Go reference for these build tags to avoid dynamic linking in various situations; instead, you need to read the os/user and net package documentation. Building this way will make a lot of programs into statically linked ones while still letting programs that really want to be dynamically linked for some reason do so.

(As of Go 1.18 I don't believe there are any other such 'use pure Go' build tags for standard packages.)

PS: Some of Delve's calls to versioned pthreads functions appear to come from runtime/cgo. See for example gcc_libinit.c and gcc_linux_amd64.c. I'm not sure why Delve is the only program affected by this out of everything I build.

GoAndGlibcVersioning written at 22:36:29; Add Comment

(Previous 10 or go back to May 2022 at 2022/05/25)

Page tools: See As Normal.
Search:
Login: Password:
Atom Syndication: Recent Pages, Recent Comments.

This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.