Introduction to Buckets and Brigades

The basic concepts we are dealing with are the bucket and the brigade. Let us first introduce them, before moving on to why and how to use them.

Buckets

A bucket is a container for data. Buckets can contain any type of data. Although the most common case is a block of memory, a bucket may instead contain a file on disc, or even be fed a data stream from a dynamic source such as a separate program. Different bucket types exist to hold different kinds of data and the methods for handling it. In OOP terms, the apr_bucket is an abstract base class from which actual bucket types are derived.

There are several different types of data bucket, as well as metadata buckets. We will describe these at the end of this article.

Brigades

In normal use, there is no such thing as a freestanding bucket: they are contained in bucket brigades. A brigade is a container that may hold any number of buckets in a ring structure. The brigade serves to enable flexible and efficient manipulation of data, and is the unit that gets passed to and from your filter.

So, why do we need buckets and brigades? Can't we just keep it simple and pass simple blocks of data? Maybe a void* with a length, or a C++ string?

Well, the first part of the answer we've seen already: buckets are more than just data: they are an abstraction that unifies fundamentally different types of data. But even so, how do they justify the additional complexity over simple buffers and ad-hoc use of other data sources in exceptional cases?

The second motivation for buckets and brigades is that they enable efficient manipulation of blocks of memory, typical of many filtering applications. We will demonstrate a simple but typical example of this: a filter to display plain text documents prettified as an HTML page, with header and footer supplied by the webmaster in the manner of a fancy directory listing.

Now, HTML can of course include blocks of plain text, enclosing them in <pre> to preserve spacing and formatting. So the main task of a text->html filter is to pass the text straight through. But certain special characters need to be escaped. To be safe both with the HTML spec and browsers, we will escape the four characters <, >, &, and " as &lt, etc.

Because the replacement &lt; is longer by three bytes than the original, we cannot just replace the character. If we are using a simple buffer, we either have to extend it with realloc() or equivalent, or copy the whole thing interpolating the replacement. Repeat this a few times and it rapidly gets very inefficient. A better solution is a two-pass scan of the buffer: the first pass simply computes the length of the new buffer, after which we allocate the memory and copy the data with the required replacements. But even that is by no means efficient.

By using buckets and brigades in place of a simple buffer, we can simply replace the characters in situ, without allocating or copying any big blocks of memory. Provided the number of characters replaced is small in comparison to the total document size, this is much more efficient. In outline:

1. We encounter a character that needs replacing in the bucket
2. We split the bucket before and after the character. Now we have three buckets: the character itself, and all data before and after it.
3. We drop the character, leaving the before and after buckets.
4. We create a new bucket containing the replacement, and insert it where the character was.

Now instead of moving/copying big blocks of data, we are just manipulating pointers into an existing block. The only actual data to change are the single character removed and the few bytes that replace it.

mod_txt is a simple output filter module to display plain text files as HTML (or XHTML) with a header and footer. When a text file is requested, it escapes the text as required for HTML, and displays it between the header and the footer.

It works by direct manipulation of buckets (the lowest-level API), and demonstrates both insertion of file data and substitution of characters, without any allocation of moving of big blocks.

Firstly we introduce two functions to deal with the data insertions: one for the files, one for the simple entity replacements:

Creating a File bucket requires an open filehandle and a byte range within the file. Since we're transmitting the entire file, we just stat its size to set the byte range. We open it with a shared lock and with sendfile enabled for maximum performance.

static apr_bucket* txt_file_bucket(request_rec* r, const char* fname) {
  apr_file_t* file = NULL ;
  apr_finfo_t finfo ;
  if ( apr_stat(&finfo, fname, APR_FINFO_SIZE, r->pool) != APR_SUCCESS ) {
    return NULL ;
  }
  if ( apr_file_open(&file, fname, APR_READ|APR_SHARELOCK|APR_SENDFILE_ENABLED,
	APR_OS_DEFAULT, r->pool ) != APR_SUCCESS ) {
    return NULL ;
  }
  if ( ! file ) {
    return NULL ;
  }
  return apr_bucket_file_create(file, 0, finfo.size, r->pool,
	r->connection->bucket_alloc) ;
}

Creating the simple text replacements, we can just make a bucket of an inline string. The appropriate bucket type for such data is transient:

static apr_bucket* txt_esc(char c, apr_bucket_alloc_t* alloc ) {
  switch (c) {
    case '<': return apr_bucket_transient_create("&lt;", 4, alloc) ;
    case '>': return apr_bucket_transient_create("&gt;", 4, alloc) ;
    case '&': return apr_bucket_transient_create("&amp;", 5, alloc) ;
    case '"': return apr_bucket_transient_create("&quot;", 6, alloc) ;
    default: return NULL ;	/* shut compilers up */
  }
}

Actually this is not the most efficient way to do this. We will discuss alternative formulations of the above below.

Now the main filter itself is broadly straightforward, but there are a number of interesting and unexpected points to consider. Since this is a little longer than the above utility functions, we'll comment it inline instead. Note that the Header and Footer file buckets are set in a filter_init function (omitted for brevity).

static int txt_filter(ap_filter_t* f, apr_bucket_brigade* bb) {
  apr_bucket* b ;
  txt_ctxt* ctxt = (txt_ctxt*)f->ctx ;

  if ( ctxt == NULL ) {
    txt_filter_init(f) ;
    ctxt = f->ctx ;
  }


Main Loop: This construct is typical for iterating over the incoming data

  for ( b = APR_BRIGADE_FIRST(bb);
	b != APR_BRIGADE_SENTINEL(bb);
	b = APR_BUCKET_NEXT(b) ) {

    const char* buf ;
    size_t bytes ;

As in any filter, we need to check for EOS.  When we encounter it,
we insert the footer in front of it.  We shouldn't get more than
one EOS, but just in case we do we'll note having inserted the
footer.  That means we're being error-tolerant.

    if ( APR_BUCKET_IS_EOS(b) ) {
      /* end of input file - insert footer if any */
      if ( ctxt->foot && ! (ctxt->state & TXT_FOOT ) ) {
	ctxt->state |= TXT_FOOT ;
	APR_BUCKET_INSERT_BEFORE(b, ctxt->foot);
      }

The main case is a bucket containing data,  We can get it as a simple
buffer with its size in bytes:

    } else if ( apr_bucket_read(b, &buf, &bytes, APR_BLOCK_READ)
	== APR_SUCCESS ) {
      /* We have a bucket full of text.  Just escape it where necessary */
      size_t count = 0 ;
      const char* p = buf ;

Now we can search for characters that need replacing, and replace them

      while ( count < bytes ) {
	size_t sz = strcspn(p, "<>&\"") ;
	count += sz ;

Here comes the tricky bit: replacing a single character inline.

	if ( count < bytes ) {
	  apr_bucket_split(b, sz) ;	Split off before buffer
	  b = APR_BUCKET_NEXT(b) ;	Skip over before buffer
	  APR_BUCKET_INSERT_BEFORE(b, txt_esc(p[sz],
		f->r->connection->bucket_alloc)) ;
					Insert the replacement
	  apr_bucket_split(b, 1) ;	Split off the char to remove
	  APR_BUCKET_REMOVE(b) ;	 ... and remove it
	  b = APR_BUCKET_NEXT(b) ;	Move cursor on to what-remains
					so that it stays in sequence with
					our main loop
	  count += 1 ;
	  p += sz + 1 ;
	}
      }
    }
  }

Now we insert the Header if it hasn't already been inserted.
Note:
  (a)	This has to come after the main loop, to avoid the header itself
	getting into the parse.
  (b)	It works because we can insert a bucket anywhere in the brigade,
	and in this case put it at the head.
  (c)	As with the footer, we save state to avoid inserting it more than once.

  if ( ctxt->head && ! (ctxt->state & TXT_HEAD ) ) {
    ctxt->state |= TXT_HEAD ;
    APR_BRIGADE_INSERT_HEAD(bb, ctxt->head);
  }


Now we've finished manipulating data, we just pass it down the filter chain.

  return ap_pass_brigade(f->next, bb) ;
}

Note that we created a new bucket every time we replaced a character. Couldn't we have prepared four buckets in advance - one for each of the characters to be replaced - and then re-used them whenever the character occurred?

The problem here is that each bucket is linked to its neighbours. So if we re-use the same bucket, we lose the links, so that the brigade now jumps over any data between the two instances of it. Hence we do need a new bucket every time. That means this technique becomes inefficient when a high proportion of input data has to be changed. We will show alternative techniques for such cases in other articles.

In the above, we used two data bucket types: file and transient, and the eos metadata bucket type. There are several other bucket types suitable for different kinds of data and metadata.

When we created transient buckets above, we were inserting a chunk of memory in the output stream. But we noted that this bucket was not the most efficient way to escape a character. The reason for this is that the transient memory has to be copied internally to prevent it going out of scope. We could instead have used memory that's guaranteed never to go out of scope, by replacing

    case '<': return apr_bucket_transient_create("&lt;", 4, alloc) ;

with

  static const char* lt = "&lt;" ;
  ...
    case '<': return apr_bucket_immortal_create(lt, 4, alloc) ;

When we create an immortal bucket, we guarantee that the memory won't go out of scope during the lifetime of the bucket, so the APR never needs to copy it internally.

A third variant on the same principle is the pool bucket. This refers to memory allocated on a pool, and will have to be copied internally if and only if the pool is destroyed within the lifetime of the bucket.

The heap bucket is another form of in-memory bucket. But its usage is rather different from any of the above. We rarely if ever need to create a heap bucket explicitly: rather they are managed internally when we use the stdio-like API to write data to the next filter. This API is discussed in other articles.

The File bucket, as we have already seen, enables us to insert a file (or part) file into the data stream. Although we had to stat it to find its length, we didn't have to read it. If sendfile is enabled, the operating system (through the APR) can optimise sending the file.

The mmap bucket type is similar, and is appropriate to mmaped files. APR may convert file buckets to mmap internally if we (or a later filter) read the data.

Two other more unusual bucket types are the pipe and the socket, which enable us to insert data from an external source via IPC.

In addition to data buckets, there are two metadata types. The EOS bucket is crucial: it must be sent at the end of a data stream, and it serves to signal the end of incoming data. The other metadata type is the rarely-user FLUSH bucket, which may occasionally be required, but is not guaranted to be propagated by every filter.

Cliff Woolley gave a talk on buckets and brigades at ApacheCon 2002. His notes are very readable, and go into more depth than this article.