Update buffer-handling code to enable expandable buffers.

1 files changed, 138 insertions, 140 deletions

diff --git a/src/core/buffer.c b/src/core/buffer.c
index 81288ff5..be4c6055 100644
--- a/src/core/buffer.c
+++ b/src/core/buffer.c
@@ -1,3 +1,27 @@
+/*
+ * Copyright (C) 2007 Michael Brown <mbrown@fensystems.co.uk>.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+
+#include <stddef.h>
+#include <string.h>
+#include <errno.h>
+#include <assert.h>
+#include <io.h>
+#include <gpxe/buffer.h>
 
 /** @file
  *
@@ -7,27 +31,22 @@
  * which is "filled" and the remainder of which is "free".  The
  * "filled" and "free" spaces are not necessarily contiguous.
  *
- * When a buffer is initialised via init_buffer(), it consists of a
- * single free space.  As data is added to the buffer via
- * fill_buffer(), this free space decreases and can become fragmented.
- *
- * Each free block within a buffer starts with a "tail byte".  If the
- * tail byte is non-zero, this indicates that the free block is the
- * tail of the buffer, i.e. occupies all the remaining space up to the
- * end of the buffer.  When the tail byte is non-zero, it indicates
- * that a descriptor (a @c struct @c buffer_free_block) follows the
- * tail byte.  The descriptor describes the size of the free block and
- * the address of the next free block.
- *
- * We cannot simply always start a free block with a descriptor,
- * because it is conceivable that we will, at some point, encounter a
- * situation in which the final free block of a buffer is too small to
- * contain a descriptor.  Consider a protocol with a blocksize of 512
- * downloading a 1025-byte file into a 1025-byte buffer.  Suppose that
- * the first two blocks are received; we have now filled 1024 of the
- * 1025 bytes in the buffer, and our only free block consists of the
- * 1025th byte.  Using a "tail byte" solves this problem.
- *
+ * At the start of a buffer's life, it consists of a single free
+ * space.  As data is added to the buffer via fill_buffer(), this free
+ * space decreases and can become fragmented.
+ *
+ * Each free block within a buffer (except the last) starts with a @c
+ * struct @c buffer_free_block.  This describes the size of the free
+ * block, and the offset to the next free block.
+ *
+ * We cannot simply start every free block (including the last) with a
+ * descriptor, because it is conceivable that we will, at some point,
+ * encounter a situation in which the final free block of a buffer is
+ * too small to contain a descriptor.  Consider a protocol with a
+ * blocksize of 512 downloading a 1025-byte file into a 1025-byte
+ * buffer.  Suppose that the first two blocks are received; we have
+ * now filled 1024 of the 1025 bytes in the buffer, and our only free
+ * block consists of the 1025th byte.
  * 
  * Note that the rather convoluted way of manipulating the buffer
  * descriptors (using copy_{to,from}_phys rather than straightforward
@@ -38,107 +57,76 @@
  *
  */
 
-#include "stddef.h"
-#include "string.h"
-#include "io.h"
-#include "errno.h"
-#include <assert.h>
-#include <gpxe/buffer.h>
-
 /**
- * Initialise a buffer.
+ * A free block descriptor
  *
- * @v buffer		The buffer to be initialised
- * @ret None		-
- * @err None		-
+ * This is the data structure that is found at the start of a free
+ * block within a data buffer.
+ */
+struct buffer_free_block {
+	/** Starting offset of the free block */
+	size_t start;
+	/** Ending offset of the free block */
+	size_t end;
+	/** Offset of next free block */
+	size_t next;
+};
+
+/**
+ * Get next free block within the buffer
  *
- * Set @c buffer->start and @c buffer->end before calling init_buffer().
- * init_buffer() will initialise the buffer to the state of being
- * empty.
+ * @v buffer		Data buffer
+ * @v block		Previous free block descriptor
+ * @ret block		Next free block descriptor
+ * @ret rc		Return status code
  *
+ * Set @c block->next=buffer->free before first call to
+ * get_next_free_block().
  */
-void init_buffer ( struct buffer *buffer ) {
-	char tail = 1;
-
-	buffer->fill = 0;
-	if ( buffer->end != buffer->start )
-		copy_to_phys ( buffer->start, &tail, sizeof ( tail ) );
+static int get_next_free_block ( struct buffer *buffer,
+				 struct buffer_free_block *block ) {
 
-	DBG ( "BUFFER [%x,%x) initialised\n", buffer->start, buffer->end );
-}
+	/* Check for end of buffer */
+	if ( block->end >= buffer->len )
+		return -ENOENT;
 
-/**
- * Move to the next block in the free list
- *
- * @v block		The current free block
- * @v buffer		The buffer
- * @ret True		Successfully moved to the next free block
- * @ret False		There are no more free blocks
- * @ret block		The next free block
- * @err None		-
- *
- * Move to the next block in the free block list, filling in @c block
- * with the descriptor for this next block.  If the next block is the
- * tail block, @c block will be filled with the values calculated for
- * the tail block, otherwise the descriptor will be read from the free
- * block itself.
- *
- * If there are no more free blocks, next_free_block() returns False
- * and leaves @c block with invalid contents.
- *
- * Set <tt> block->next = buffer->start + buffer->fill </tt> for the
- * first call to next_free_block().
- */
-static inline int next_free_block ( struct buffer_free_block *block,
-				    struct buffer *buffer ) {
 	/* Move to next block */
 	block->start = block->next;
-
-	/* If at end of buffer, return 0 */
-	if ( block->start >= buffer->end )
-		return 0;
-
-	/* Set up ->next and ->end as for a tail block */
-	block->next = block->end = buffer->end;
-
-	/* Read tail marker from block */
-	copy_from_phys ( &block->tail, block->start, sizeof ( block->tail ) );
-
-	/* If not a tail block, read whole block descriptor from block */
-	if ( ! block->tail ) {
-		copy_from_phys ( block, block->start, sizeof ( *block ) );
+	if ( block->start >= buffer->free ) {
+		/* Final block; no in-band descriptor */
+		block->end = buffer->len;
+	} else {
+		/* Retrieve block descriptor */
+		copy_from_phys ( block, ( buffer->addr + block->start ),
+				 sizeof ( *block ) );
 	}
 
-	return 1;
+	return 0;
 }
 
 /**
- * Store a free block descriptor
+ * Write free block descriptor back to buffer
  *
- * @v block		The free block descriptor to store
- * @ret None		-
- * @err None		-
- *
- * Writes a free block descriptor back to a free block.  If the block
- * is a tail block, only the tail marker will be written, otherwise
- * the whole block descriptor will be written.
+ * @v buffer		Data buffer
+ * @v block		Free block descriptor
  */
-static inline void store_free_block ( struct buffer_free_block *block ) {
-	copy_to_phys ( block->start, block,
-		       ( block->tail ?
-			 sizeof ( block->tail ) : sizeof ( *block ) ) );
+static void store_free_block ( struct buffer *buffer,
+			       struct buffer_free_block *block ) {
+	size_t free_block_size = ( block->end - block->start );
+
+	assert ( free_block_size >= sizeof ( *block ) );
+	copy_to_phys ( ( buffer->addr + block->start ), block,
+		       sizeof ( *block ) );
 }
 
 /**
- * Write data into a buffer.
+ * Write data into a buffer
  *
- * @v buffer		The buffer into which to write the data
- * @v data		The data to be written
+ * @v buffer		Data buffer
+ * @v data		Data to be written
  * @v offset		Offset within the buffer at which to write the data
  * @v len		Length of data to be written
- * @ret True		Data was successfully written
- * @ret False		Data was not written
- * @err ENOMEM		Buffer is too small to contain the data
+ * @ret rc		Return status code
  *
  * Writes a block of data into the buffer.  The block need not be
  * aligned to any particular boundary, or be of any particular size,
@@ -166,29 +154,37 @@ static inline void store_free_block ( struct buffer_free_block *block ) {
  *
  */
 int fill_buffer ( struct buffer *buffer, const void *data,
-		  off_t offset, size_t len ) {
+		  size_t offset, size_t len ) {
 	struct buffer_free_block block, before, after;
-	physaddr_t data_start, data_end;
-
-	/* Calculate start and end addresses of data */
-	data_start = buffer->start + offset;
-	data_end = data_start + len;
-	DBG ( "BUFFER [%x,%x) writing portion [%x,%x)\n",
-	      buffer->start, buffer->end, data_start, data_end );
-
-	/* Check buffer bounds */
-	if ( data_end > buffer->end ) {
-		DBG ( "BUFFER [%x,%x) too small for data!\n",
-		      buffer->start, buffer->end );
-		errno = ENOMEM;
-		return 0;
+	size_t data_start = offset;
+	size_t data_end = ( data_start + len );
+	int rc;
+
+	DBGC ( buffer, "BUFFER %p [%lx,%lx) filling portion [%lx,%lx)\n",
+	       buffer, buffer->addr, ( buffer->addr + buffer->len ),
+	       ( buffer->addr + data_start ), ( buffer->addr + data_end ) );
+
+	/* Check that block fits within buffer, expand if necessary */
+	if ( data_end > buffer->len ) {
+		if ( ! buffer->expand ) {
+			DBGC ( buffer, "BUFFER %p not expandable\n", buffer );
+			return -ENOBUFS;
+		}
+		if ( ( rc = buffer->expand ( buffer, data_end ) ) != 0 ) {
+			DBGC ( buffer, "BUFFER %p could not expand :%s\n",
+			       buffer, strerror ( rc ) );
+			return rc;
+		}
+		DBGC ( buffer, "BUFFER %p expanded to [%lx,%lx)\n", buffer,
+		       buffer->addr, ( buffer->addr + buffer->len ) );
+		assert ( buffer->len >= data_end );
 	}
 
 	/* Find 'before' and 'after' blocks, if any */
 	before.start = before.end = 0;
-	after.start = after.end = buffer->end;
-	block.next = buffer->start + buffer->fill;
-	while ( next_free_block ( &block, buffer ) ) {
+	after.start = after.end = buffer->len;
+	block.next = buffer->fill;
+	while ( get_next_free_block ( buffer, &block ) == 0 ) {
 		if ( ( block.start < data_start ) &&
 		     ( block.start >= before.start ) )
 			memcpy ( &before, &block, sizeof ( before ) );
@@ -206,33 +202,35 @@ int fill_buffer ( struct buffer *buffer, const void *data,
 	/* Link 'after' block to 'before' block */
 	before.next = after.start;
 
+	DBGC ( buffer, "BUFFER %p split before [%lx,%lx) after [%lx,%lx)\n",
+	       buffer, ( buffer->addr + before.start ),
+	       ( buffer->addr + before.end ), ( buffer->addr + after.start ),
+	       ( buffer->addr + after.end ) );
+
 	/* Write back 'before' block, if any */
-	if ( before.start ) {
-		before.tail = 0;
-		assert ( ( before.end - before.start ) >=
-			 sizeof ( struct buffer_free_block ) );
-		store_free_block ( &before );
+	if ( before.end == 0 ) {
+		/* No 'before' block: update buffer->fill */
+		buffer->fill = after.start;
+		DBGC ( buffer, "BUFFER %p full up to %lx\n", buffer,
+		       ( buffer->addr + buffer->fill ) );
 	} else {
-		buffer->fill = before.next - buffer->start;
+		/* Write back 'before' block */
+		store_free_block ( buffer, &before );
 	}
 
-	/* Write back 'after' block, if any */
-	if ( after.start < buffer->end ) {
-		assert ( after.tail ||
-			 ( ( after.end - after.start ) >=
-			   sizeof ( struct buffer_free_block ) ) );
-		store_free_block ( &after );
+	/* Write back 'after' block */
+	if ( after.end == buffer->len ) {
+		/* 'After' block is the final block: update buffer->free */
+		buffer->free = after.start;
+		DBGC ( buffer, "BUFFER %p free from %lx onwards\n", buffer,
+		       ( buffer->addr + buffer->free ) );
+	} else {
+		/* Write back 'after' block */
+		store_free_block ( buffer, &after );
 	}
-	
-	DBG ( "BUFFER [%x,%x) before [%x,%x) after [%x,%x)\n",
-	      buffer->start, buffer->end, before.start, before.end,
-	      after.start, after.end );
-	
-	/* Copy data into buffer */
-	copy_to_phys ( data_start, data, len );
 
-	DBG ( "BUFFER [%x,%x) full up to %x\n",
-	      buffer->start, buffer->end, buffer->start + buffer->fill );
+	/* Copy data into buffer */
+	copy_to_phys ( ( buffer->addr + data_start ), data, len );
 
-	return 1;
+	return 0;
 }