Preventing dynamic memory problems in C

When writing C programs that use structures kept in dynamic memory, there are a few techniques that are useful to prevent problems. The ones I mention here are not new, and well written software (e.g, much of Plan 9 from Bell Labs) use them a lot. This post is mostly for new programmers or not-so-old programmers in the hope that it might help them.

For example, consider a server that allocates/releases some structures to serve clients:
typedef struct MBuf MBuf;
struct MBuf {
uint64_t pc;
MBuf *next; // next in free or used list
MBuf *anext; // next in global allocation list
... the actual data goes here ...
};

It does not matter what this structure is used for. But the code will do many (de)allocations for these. Instead of using malloc/free directly, we keep all allocated structures in a single list linked through the anext field, and all unused structures in a free list, linked through the next field.

For allocation, if there are structures in the free list, we are done. Otherwise we allocate a new one and link it in the global list.

Now, in the allocation, we take the program counter of the caller and store it in the pc field. In deallocation, we set the pc to zero and set most of the structure (but for the pc and the link fields) to a silly value. That is, we poison the data when it is free.

Doing so, makes it quite easy to detect references to free structures. Also, it is easy to write a leak function that, at the end of the program or at any other point, scans the entire global allocation list and prints those program counters that are not zero, so we know the places in the program where we are allocating the structures without actually releasing them.

It's an easy thing to do, it makes the program faster because it avoids extra allocations, and it makes the program safer because it aids in testing and debugging. Hope you enjoy it.

The same thing can be done to structures pre-allocated in arrays, thus, the leaks detected are those that are actually leaks (because the leak tool provided by the OS or the language does not know if something that we allocated is actually a leak or not; it might be a correct pre-allocation that was never used).

For example, this might be the code:

MBuf*

bufalloc(void)

{

MBuf *buf;

buf = freebuf;

if (buf != NULL) {

freebuf = buf->next;

} else {

buf = xmalloc(sizeof(MBuf));

buf->anext = allbufs;

allbufs = buf;

}

CALLERPC(buf->pc); // set buf->pc with the caller pc

return buf;

}

void

buffree(MBuf *buf)

{

MBuf *n;

if (buf != NULL) {

n = buf->anext;

if (buf->pc == 0) {

xfatal("buffree: double free");

}

memset(buf, 3, sizeof(*buf));// poison

buf->anext = n;

buf->pc = 0;

buf->next = freebuf;

freebuf = buf;

}

}

void

bufleaks(void)

{

MBuf *buf;

for (buf = allbufs; buf != NULL; buf = buf->anext) {

if (buf->pc != 0) {

xwarn("bufalloc: leak pc %llx", buf->pc);

xwarn("\tlldb %s", argv0);

xwarn("\tdi -m -s %llx", buf->pc);

}

}

}

Commands and channels in Clive: Sam is gone.

Recently I removed the port of the venerable Sam command language in Clive.
This command language can do things like iterate for all portions of text matching addresses indicated by regular expressions and then, for example, for each portion matching another expression, apply a command or loop in some other way.

As part of the Clive application framework (still WIP), I ported most of the commands to the new standard setup: commands have a series of I/O channels that forward interface{} data. When going outside of the Clive world, only []byte is actually written into off-limits channels.

By convention, commands expect data to be just []byte messages, forwarded through std. IO channels (similar to file descriptors in UNIX, but using -modified- Go channels).

Now, the interesting thing is the result for these conventions:

• All commands forward all messages they don't understand. 
• Commands finding files send not just file contents, but send a zx.Dir for each file found before actually sending the file data to standard output (more on this later in this post).
• Only []byte messages are actually considered data, all other types can be used to let friend commands talk without disrupting others in the command pipeline.

To illustrate the consequences, we can run this pipeline in Clive:

gf /tmp/echo,1 | gx  '(^func[^\n]*\n)' '(^}\n)' | gg Run | 

gp '~m.*&1' | trex -u | pf -ws,

This is just an example, I'll explain the bits and pieces; but the interesting thing is how things can work together so in Clive we can use separate commands to do what in UNIX we would have to do in a single process, or would be a lot harder to split into separate commands.

The first command, gf /tmp/echo,1  issues a Find request to the ZX file system and sends to its std. output channel a stream of data for matching files. In this case, we asked for files under /tmp/echo with depth not greater than 1. Here, filtering of interesting files happens at the file server, which sends to the client machine a stream of directory entries for matching files plus data for each one (after its directory entry).

Now, gx is mostly a grep command. In this case, it simply sends to its output all text enclosed in text matched by the two given regexps. It can be used in other ways; the one in the example would report as a []byte in the output each function or method defined in the go source.

The funny thing is that gx (as called) also writes unmatched input to the output, but uses a string data type instead. Furthermore, it posts addresses (text lines and rune ranges) to its output, should the user want to print that.

The next command, gg, receives thus the entire text for the files found, but only the portions matched by the previous gx are []byte, and thus all other data is forwarded but otherwise ignored. This command sends to the output those messages containing the given expression. At this point, only functions containing Run are in the output as []byte.

To make the example more fun, gp greps directory entries in the stream and does not forward any file to the output unless its directory entry matches the predicate given. We could have given it to gf instead, but this is more fun. At this point, only functions containing Run in files with names starting with m and with a depth no greater than 1 are in the output. 

To have more fun, trex translates the input text to uppercase. Note that all unmatched data is still forwarded (but not as []byte), because we didn't suppress it from the stream in any of the previous commands.

Finally, pf -ws is a funny command that, one file at a time, reads all the file data into memory and, once the data is completed, writes the data back to the file (using its Dir entry as found in the stream to locate the file to write). We asked it to write the files and to include also data sent for them in string messages (and not just the "official" []byte messages). Thus, this is like a "save the edited files" command in Sam.

All the files processed by previous commands in the stream are written to disk at this point. Because the command buffers in memory the files going through the stream, we don't have the "cat f > f" effect of truncating the files by mistake.

The pipe-line may be silly, but it shows how bits and pieces fit together in Clive. I was not able to do these things in any other system I used before. Clive is fun. Go is fun.

The output of the pipe is also fun (using pf -x instead):

/tmp/echo/mecho.go:#174,#716:

FUNC RUN() {

        X := &XCMD{CTX: APP.APPCTX()}

        X.FLAGS = OPT.NEW("{ARG}")

        X.NEWFLAG("D", "DEBUG", &X.DEBUG)

        X.NEWFLAG("G", "DON'T ADD A FINAL NEWLINE", &X.NFLAG)

        ARGS, ERR := X.PARSE(X.ARGS)

        IF ERR != NIL {

                X.USAGE()

                APP.EXITS("USAGE")

        }

        VAR B BYTES.BUFFER

        FOR I, ARG := RANGE ARGS {

                B.WRITESTRING(ARG)

                IF I < LEN(ARGS)-1 {

                        B.WRITESTRING(" ")

                }

        }

        IF !X.NFLAG {

                B.WRITESTRING("\N")

        }

        OUT := APP.OUT()

        OK := OUT <- B.BYTES()

        IF !OK {

                APP.WARN("STDOUT: %S", CERROR(OUT))

                APP.EXITS(CERROR(OUT))

        }

        APP.EXITS(NIL)

}

 I admit that Clive is even more user-friendly than UNIX ;)

But I also admit I like that...

Limiting the number of concurrent processes

In some cases, a task can be easily split into multiple concurrent child tasks, but it is not a good idea to spawn each of of the child tasks as a concurrent process.

For example, some commands in Clive go through a tree to synchronise it, or to poll each node for changes, etc. At each node in the tree, it is clear that the children can be processed concurrently. This reduces the total latency for the entire process. However, doing it this way would place a high load on the server at the other end of the line, and also on the line itself, and it might not be a good idea.

In Go it is fairly trivial to place a limit on the maximum number of concurrent tasks kept but still exploit concurrency up to that limit. The technique shown here is not new and, in fact, has been in use for decades, even in C for Plan 9, and probably in many other languages and by many other authors. Nevertheless, I think this tiny bit of code might help those that never saw it before.

The idea is to send functions through a channel and keep a fixed set of workers at the other end of the channel. All of them receive a function, call it, and loop again. The number of workers places the limit on the number of concurrent tasks running at the same time.

This creates the pool to run tasks:

func NewPool(n int) *Pool {
p := &Pool{calls: make(chan call)}
for i := 0; i < n; i++ {
go p.worker(i)
}
return p
}

A worker is simply

func (p* Pool) worker(id int) {

for c := range p.calls {

c.fn()

c.donec <- true

}

}

And we can run functions using this method:

func (p *Pool) Go(donec chan bool, fn func()) chan bool {

if donec == nil {

donec = make(chan bool, 1)

}

p.calls <- call{fn: fn, donec: donec}

return donec

}

Now the thing is fairly easy to use. Go closures make the interface of the previous method powerful enough to do anything and accept/return any input/output values.

For example:

// Create a pool of 5 workers

p := NewPool(5) 

// Run 20 functions in the pool

dc := make(chan bool, 20)

for i := 0; i < 20; i++ {

p.Go(dc, func() {

dprintf("running this...\n")

})

}

// Wait until all of them are done

for i := 0; i < 20; i++ {

<-dc

}

The testing code in this package plots a nice diagram of the execution, as a side effect of testing.

This is one such plot, time on the X axis and each task on the Y axis. 

trace: abcdeAfBCDEghijFkGHIJlmnoKpLMNOqrstPQRST

+----+                                  

 +-----+                                

  +-----+                               

   +-----+                              

    +-----+                             

      +--------+                        

           +-----+                      

            +-----+                     

             +-----+                    

              +-----+                   

                +--------+              

                     +-----+            

                      +-----+           

                       +-----+          

                        +-----+         

                          +--------+    

                               +----+   

                                +----+  

                                 +----+ 

                                  +----+

The tests run fake jobs like this one:

func fakefn(r rune, t time.Duration) {

n := atomic.AddInt32(&ncalls, 1)

calls[n-1] = r

dprintf("fake call %c\n", r)

time.Sleep(t)

r = unicode.ToUpper(r)

n = atomic.AddInt32(&ncalls, 1)

calls[n-1] = r

}

They record a trace of the sequence of calls in a string like

abcdeAfBCDEghijFkGHIJlmnoKpLMNOqrstPQRST

where lower-case indicate the start of a task and upper-case its end.

Thus, checking that the scheduling is as expected for the test is easy as is producing a plot for fun.

func plot(trz string, ncalls int) {

c := 'a'

dprintf("trace: %s\n", trz)

ch := map[bool]string{true: "-", false: " "}

for i := 0; i < ncalls; i++ {

st := c+rune(i)

end := unicode.ToUpper(st)

sted := false

for _, ev := range trz {

switch ev {

case st, end:

dprintf("+")

sted = !sted

default:

dprintf(ch[sted])

}

}

dprintf("\n")

}

}

Conventions can do more with less: Clive options continued.

In a previous post I discussed a new package in Clive, opt, which deals with command arguments.
The package turned to be very easy to use and has unified how clive commands are used beyond understanding a common option syntax.

When defining new options, the user gives a pointer to a Go value, a name, and a help string:

func (f *Flags) NewFlag(name, help string, vp interface{})

The help string follows the convention that

• for options with no arguments, it simply describes the option.
• for options with arguments, it starts with  "argument name:" followed by the description of the option.

This allows the usage method to exploit this convention to build a usage string more descriptive than the ones in other Go programs. For example, compare the old

usage: flds -options [file...]

with the new

usage: flds [-1D] [-F sep] [-o sep] {-r range} [file...]

The method writing the usage description scans the defined flags for those that have a single rune as a name, and no argument, and combines them like in "-1D" above. Then it goes over flags that have longer names, or have arguments, and adds the usage for each one in the same line. The name of the argument is taken from the start of the help string (if found, or a generic name for the type of argument [in Go] is used). When arguments may be used more than once, curly brackets are printed instead of square ones. The method knows this because the value pointer given to NewFlag is a pointer to a slice of values.

Thus, there is no need to keep the usage summary synchronised with the source, it is always in sync.

But this convention has done even more work for Clive. Manual pages in clive (for all sections but the go packages section) are written in wr(1). Recently we have

• added a feature to the opt package so that "-?" can never be a valid flag, which makes all programs inform of their usage when called with this flag.
• replaced all the "synopsis" subsections in all command man pages with a new "usage" one.

The new manual pages start with something like:

_ LNS(1): print lines

* USAGE

[sh

lns -? >[2=1] | lns -r 1,-2

]

...

Here, a shell escape runs the command to make it inform about its usage, and all the output lines but for the last one (which is an exit status in clive) are inserted into the manual.

After doing so, we could remove most option description lists from manual pages, and we no longer have to document the usage of a command anymore. Plus, we are sure that the usage matches the binary installed in the system. For example, the manual for lns looks like:

LNS(1): PRINT LINES

USAGE

    usage: lns [-Dn] {-r range} [file...]

    -D: debug

    -n: print line numbers

    -r range: print this range

    range is addr,addr or addr

    addr is linenb, or +linenb, or -linenb

    

DESCRIPTION

...

Once again, we could do more by actually doing less.