src/core/buffer.c

   1
   2 /** @file
   3  *
   4  * Buffer internals.
   5  *
   6  * A buffer consists of a single, contiguous area of memory, some of
   7  * which is "filled" and the remainder of which is "free".  The
   8  * "filled" and "free" spaces are not necessarily contiguous.
   9  *
  10  * When a buffer is initialised via init_buffer(), it consists of a
  11  * single free space.  As data is added to the buffer via
  12  * fill_buffer(), this free space decreases and can become fragmented.
  13  *
  14  * Each free block within a buffer starts with a "tail byte".  If the
  15  * tail byte is non-zero, this indicates that the free block is the
  16  * tail of the buffer, i.e. occupies all the remaining space up to the
  17  * end of the buffer.  When the tail byte is non-zero, it indicates
  18  * that a descriptor (a @c struct @c buffer_free_block) follows the
  19  * tail byte.  The descriptor describes the size of the free block and
  20  * the address of the next free block.
  21  *
  22  * We cannot simply always start a free block with a descriptor,
  23  * because it is conceivable that we will, at some point, encounter a
  24  * situation in which the final free block of a buffer is too small to
  25  * contain a descriptor.  Consider a protocol with a blocksize of 512
  26  * downloading a 1025-byte file into a 1025-byte buffer.  Suppose that
  27  * the first two blocks are received; we have now filled 1024 of the
  28  * 1025 bytes in the buffer, and our only free block consists of the
  29  * 1025th byte.  Using a "tail byte" solves this problem.
  30  *
  31  *
  32  * Note that the rather convoluted way of manipulating the buffer
  33  * descriptors (using copy_{to,from}_phys rather than straightforward
  34  * pointers) is needed to cope with operation as a PXE stack, when we
  35  * may be running in real mode or 16-bit protected mode, and therefore
  36  * cannot directly access arbitrary areas of memory using simple
  37  * pointers.
  38  *
  39  */
  40
  41 #include "stdio.h"
  42 #include "stddef.h"
  43 #include "string.h"
  44 #include "io.h"
  45 #include "errno.h"
  46 #include <assert.h>
  47 #include "buffer.h"
  48
  49 /**
  50  * Initialise a buffer.
  51  *
  52  * @v buffer            The buffer to be initialised
  53  * @ret None            -
  54  * @err None            -
  55  *
  56  * Set @c buffer->start and @c buffer->end before calling init_buffer().
  57  * init_buffer() will initialise the buffer to the state of being
  58  * empty.
  59  *
  60  */
  61 void init_buffer ( struct buffer *buffer ) {
  62         char tail = 1;
  63
  64         buffer->fill = 0;
  65         if ( buffer->end != buffer->start )
  66                 copy_to_phys ( buffer->start, &tail, sizeof ( tail ) );
  67
  68         DBG ( "BUFFER [%x,%x) initialised\n", buffer->start, buffer->end );
  69 }
  70
  71 /**
  72  * Move to the next block in the free list
  73  *
  74  * @v block             The current free block
  75  * @v buffer            The buffer
  76  * @ret True            Successfully moved to the next free block
  77  * @ret False           There are no more free blocks
  78  * @ret block           The next free block
  79  * @err None            -
  80  *
  81  * Move to the next block in the free block list, filling in @c block
  82  * with the descriptor for this next block.  If the next block is the
  83  * tail block, @c block will be filled with the values calculated for
  84  * the tail block, otherwise the descriptor will be read from the free
  85  * block itself.
  86  *
  87  * If there are no more free blocks, next_free_block() returns False
  88  * and leaves @c block with invalid contents.
  89  *
  90  * Set <tt> block->next = buffer->start + buffer->fill </tt> for the
  91  * first call to next_free_block().
  92  */
  93 static inline int next_free_block ( struct buffer_free_block *block,
  94                                     struct buffer *buffer ) {
  95         /* Move to next block */
  96         block->start = block->next;
  97
  98         /* If at end of buffer, return 0 */
  99         if ( block->start >= buffer->end )
 100                 return 0;
 101
 102         /* Set up ->next and ->end as for a tail block */
 103         block->next = block->end = buffer->end;
 104
 105         /* Read tail marker from block */
 106         copy_from_phys ( &block->tail, block->start, sizeof ( block->tail ) );
 107
 108         /* If not a tail block, read whole block descriptor from block */
 109         if ( ! block->tail ) {
 110                 copy_from_phys ( block, block->start, sizeof ( *block ) );
 111         }
 112
 113         return 1;
 114 }
 115
 116 /**
 117  * Store a free block descriptor
 118  *
 119  * @v block             The free block descriptor to store
 120  * @ret None            -
 121  * @err None            -
 122  *
 123  * Writes a free block descriptor back to a free block.  If the block
 124  * is a tail block, only the tail marker will be written, otherwise
 125  * the whole block descriptor will be written.
 126  */
 127 static inline void store_free_block ( struct buffer_free_block *block ) {
 128         copy_to_phys ( block->start, block,
 129                        ( block->tail ?
 130                          sizeof ( block->tail ) : sizeof ( *block ) ) );
 131 }
 132
 133 /**
 134  * Write data into a buffer.
 135  *
 136  * @v buffer            The buffer into which to write the data
 137  * @v data              The data to be written
 138  * @v offset            Offset within the buffer at which to write the data
 139  * @v len               Length of data to be written
 140  * @ret True            Data was successfully written
 141  * @ret False           Data was not written
 142  * @err ENOMEM          Buffer is too small to contain the data
 143  *
 144  * Writes a block of data into the buffer.  The block need not be
 145  * aligned to any particular boundary, or be of any particular size,
 146  * and it may overlap blocks already in the buffer (i.e. duplicate
 147  * calls to fill_buffer() are explicitly permitted).
 148  *
 149  * @c buffer->fill will be updated to indicate the fill level of the
 150  * buffer, i.e. the offset to the first gap within the buffer.  If the
 151  * filesize is known (e.g. as with the SLAM protocol), you can test
 152  * for end-of-file by checking for @c buffer->fill==filesize.  If the
 153  * filesize is not known, but there is a well-defined end-of-file test
 154  * (e.g. as with the TFTP protocol), you can read @c buffer->fill to
 155  * determine the final filesize.  If blocks are known to be delivered
 156  * in a strictly sequential order with no packet loss or duplication,
 157  * then you can pass in @c offset==buffer->fill.
 158  *
 159  * @b NOTE: It is the caller's responsibility to ensure that the
 160  * boundaries between data blocks are more than @c sizeof(struct @c
 161  * buffer_free_block) apart.  If this condition is not satisfied, data
 162  * corruption will occur.
 163  *
 164  * In practice this is not a problem.  Callers of fill_buffer() will
 165  * be download protocols such as TFTP, and very few protocols have a
 166  * block size smaller than @c sizeof(struct @c buffer_free_block).
 167  *
 168  */
 169 int fill_buffer ( struct buffer *buffer, const void *data,
 170                   off_t offset, size_t len ) {
 171         struct buffer_free_block block, before, after;
 172         physaddr_t data_start, data_end;
 173
 174         /* Calculate start and end addresses of data */
 175         data_start = buffer->start + offset;
 176         data_end = data_start + len;
 177         DBG ( "BUFFER [%x,%x) writing portion [%x,%x)\n",
 178               buffer->start, buffer->end, data_start, data_end );
 179
 180         /* Check buffer bounds */
 181         if ( data_end > buffer->end ) {
 182                 DBG ( "BUFFER [%x,%x) too small for data!\n",
 183                       buffer->start, buffer->end );
 184                 errno = ENOMEM;
 185                 return 0;
 186         }
 187
 188         /* Find 'before' and 'after' blocks, if any */
 189         before.start = before.end = 0;
 190         after.start = after.end = buffer->end;
 191         block.next = buffer->start + buffer->fill;
 192         while ( next_free_block ( &block, buffer ) ) {
 193                 if ( ( block.start < data_start ) &&
 194                      ( block.start >= before.start ) )
 195                         memcpy ( &before, &block, sizeof ( before ) );
 196                 if ( ( block.end > data_end ) &&
 197                      ( block.end <= after.end ) )
 198                         memcpy ( &after, &block, sizeof ( after ) );
 199         }
 200
 201         /* Truncate 'before' and 'after' blocks around data. */
 202         if ( data_start < before.end )
 203                 before.end = data_start;
 204         if ( data_end > after.start )
 205                 after.start = data_end;
 206
 207         /* Link 'after' block to 'before' block */
 208         before.next = after.start;
 209
 210         /* Write back 'before' block, if any */
 211         if ( before.start ) {
 212                 before.tail = 0;
 213                 assert ( ( before.end - before.start ) >=
 214                          sizeof ( struct buffer_free_block ) );
 215                 store_free_block ( &before );
 216         } else {
 217                 buffer->fill = before.next - buffer->start;
 218         }
 219
 220         /* Write back 'after' block, if any */
 221         if ( after.start < buffer->end ) {
 222                 assert ( after.tail ||
 223                          ( ( after.end - after.start ) >=
 224                            sizeof ( struct buffer_free_block ) ) );
 225                 store_free_block ( &after );
 226         }
 227
 228         DBG ( "BUFFER [%x,%x) before [%x,%x) after [%x,%x)\n",
 229               buffer->start, buffer->end, before.start, before.end,
 230               after.start, after.end );
 231
 232         /* Copy data into buffer */
 233         copy_to_phys ( data_start, data, len );
 234
 235         DBG ( "BUFFER [%x,%x) full up to %x\n",
 236               buffer->start, buffer->end, buffer->start + buffer->fill );
 237
 238         return 1;
 239 }