src/core/buffer.c

   1 /*
   2  * Copyright (C) 2007 Michael Brown <mbrown@fensystems.co.uk>.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License as
   6  * published by the Free Software Foundation; either version 2 of the
   7  * License, or any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17  */
  18
  19 #include <stddef.h>
  20 #include <string.h>
  21 #include <errno.h>
  22 #include <assert.h>
  23 #include <gpxe/uaccess.h>
  24 #include <gpxe/buffer.h>
  25
  26 /** @file
  27  *
  28  * Buffer internals.
  29  *
  30  * A buffer consists of a single, contiguous area of memory, some of
  31  * which is "filled" and the remainder of which is "free".  The
  32  * "filled" and "free" spaces are not necessarily contiguous.
  33  *
  34  * At the start of a buffer's life, it consists of a single free
  35  * space.  As data is added to the buffer via fill_buffer(), this free
  36  * space decreases and can become fragmented.
  37  *
  38  * Each free block within a buffer (except the last) starts with a @c
  39  * struct @c buffer_free_block.  This describes the size of the free
  40  * block, and the offset to the next free block.
  41  *
  42  * We cannot simply start every free block (including the last) with a
  43  * descriptor, because it is conceivable that we will, at some point,
  44  * encounter a situation in which the final free block of a buffer is
  45  * too small to contain a descriptor.  Consider a protocol with a
  46  * blocksize of 512 downloading a 1025-byte file into a 1025-byte
  47  * buffer.  Suppose that the first two blocks are received; we have
  48  * now filled 1024 of the 1025 bytes in the buffer, and our only free
  49  * block consists of the 1025th byte.
  50  *
  51  * Note that the rather convoluted way of manipulating the buffer
  52  * descriptors (using copy_{to,from}_user rather than straightforward
  53  * pointers) is needed to cope with operation as a PXE stack, when we
  54  * may be running in real mode or 16-bit protected mode, and therefore
  55  * cannot directly access arbitrary areas of memory using simple
  56  * pointers.
  57  *
  58  */
  59
  60 /**
  61  * A free block descriptor
  62  *
  63  * This is the data structure that is found at the start of a free
  64  * block within a data buffer.
  65  */
  66 struct buffer_free_block {
  67         /** Starting offset of the free block */
  68         size_t start;
  69         /** Ending offset of the free block */
  70         size_t end;
  71         /** Offset of next free block */
  72         size_t next;
  73 };
  74
  75 /**
  76  * Get next free block within the buffer
  77  *
  78  * @v buffer            Data buffer
  79  * @v block             Previous free block descriptor
  80  * @ret block           Next free block descriptor
  81  * @ret rc              Return status code
  82  *
  83  * Set @c block->next=buffer->fill before first call to
  84  * get_next_free_block().
  85  */
  86 static int get_next_free_block ( struct buffer *buffer,
  87                                  struct buffer_free_block *block ) {
  88
  89         /* Check for end of buffer */
  90         if ( block->next >= buffer->len )
  91                 return -ENOENT;
  92
  93         /* Move to next block */
  94         block->start = block->next;
  95         if ( block->start >= buffer->free ) {
  96                 /* Final block; no in-band descriptor */
  97                 block->next = block->end = buffer->len;
  98         } else {
  99                 /* Retrieve block descriptor */
 100                 copy_from_user ( block, buffer->addr, block->start,
 101                                  sizeof ( *block ) );
 102         }
 103
 104         return 0;
 105 }
 106
 107 /**
 108  * Write free block descriptor back to buffer
 109  *
 110  * @v buffer            Data buffer
 111  * @v block             Free block descriptor
 112  */
 113 static void store_free_block ( struct buffer *buffer,
 114                                struct buffer_free_block *block ) {
 115         size_t free_block_size = ( block->end - block->start );
 116
 117         assert ( free_block_size >= sizeof ( *block ) );
 118         copy_to_user ( buffer->addr, block->start, block, sizeof ( *block ) );
 119 }
 120
 121 /**
 122  * Write data into a buffer
 123  *
 124  * @v buffer            Data buffer
 125  * @v data              Data to be written
 126  * @v offset            Offset within the buffer at which to write the data
 127  * @v len               Length of data to be written
 128  * @ret rc              Return status code
 129  *
 130  * Writes a block of data into the buffer.  The block need not be
 131  * aligned to any particular boundary, or be of any particular size,
 132  * and it may overlap blocks already in the buffer (i.e. duplicate
 133  * calls to fill_buffer() are explicitly permitted).
 134  *
 135  * @c buffer->fill will be updated to indicate the fill level of the
 136  * buffer, i.e. the offset to the first gap within the buffer.  If the
 137  * filesize is known (e.g. as with the SLAM protocol), you can test
 138  * for end-of-file by checking for @c buffer->fill==filesize.  If the
 139  * filesize is not known, but there is a well-defined end-of-file test
 140  * (e.g. as with the TFTP protocol), you can read @c buffer->fill to
 141  * determine the final filesize.  If blocks are known to be delivered
 142  * in a strictly sequential order with no packet loss or duplication,
 143  * then you can pass in @c offset==buffer->fill.
 144  *
 145  * @b NOTE: It is the caller's responsibility to ensure that the
 146  * boundaries between data blocks are more than @c sizeof(struct @c
 147  * buffer_free_block) apart.  If this condition is not satisfied, data
 148  * corruption will occur.
 149  *
 150  * In practice this is not a problem.  Callers of fill_buffer() will
 151  * be download protocols such as TFTP, and very few protocols have a
 152  * block size smaller than @c sizeof(struct @c buffer_free_block).
 153  *
 154  */
 155 int fill_buffer ( struct buffer *buffer, const void *data,
 156                   size_t offset, size_t len ) {
 157         struct buffer_free_block block, before, after;
 158         size_t data_start = offset;
 159         size_t data_end = ( data_start + len );
 160         int rc;
 161
 162         DBGC2 ( buffer, "BUFFER %p [%lx,%lx) filling portion [%lx,%lx)\n",
 163                 buffer, user_to_phys ( buffer->addr, 0 ),
 164                 user_to_phys ( buffer->addr, buffer->len ),
 165                 user_to_phys ( buffer->addr, data_start ),
 166                 user_to_phys ( buffer->addr, data_end ) );
 167
 168         /* Check that block fits within buffer, expand if necessary */
 169         if ( data_end > buffer->len ) {
 170                 if ( ( rc = expand_buffer ( buffer, data_end ) ) != 0 )
 171                         return rc;
 172                 assert ( buffer->len >= data_end );
 173         }
 174
 175         /* Find 'before' and 'after' blocks, if any */
 176         before.start = before.end = 0;
 177         after.start = after.end = buffer->len;
 178         block.next = buffer->fill;
 179         while ( get_next_free_block ( buffer, &block ) == 0 ) {
 180                 if ( ( block.start < data_start ) &&
 181                      ( block.start >= before.start ) )
 182                         memcpy ( &before, &block, sizeof ( before ) );
 183                 if ( ( block.end > data_end ) &&
 184                      ( block.end <= after.end ) )
 185                         memcpy ( &after, &block, sizeof ( after ) );
 186         }
 187
 188         /* Truncate 'before' and 'after' blocks around data. */
 189         if ( data_start < before.end )
 190                 before.end = data_start;
 191         if ( data_end > after.start )
 192                 after.start = data_end;
 193
 194         /* Link 'after' block to 'before' block */
 195         before.next = after.start;
 196
 197         DBGC2 ( buffer, "BUFFER %p split before [%lx,%lx) after [%lx,%lx)\n",
 198                 buffer, user_to_phys ( buffer->addr, before.start ),
 199                 user_to_phys ( buffer->addr, before.end ),
 200                 user_to_phys ( buffer->addr, after.start ),
 201                 user_to_phys ( buffer->addr, after.end ) );
 202
 203         /* Write back 'before' block, if any */
 204         if ( before.end == 0 ) {
 205                 /* No 'before' block: update buffer->fill */
 206                 buffer->fill = after.start;
 207                 DBGC2 ( buffer, "BUFFER %p full up to %lx\n", buffer,
 208                         user_to_phys ( buffer->addr, buffer->fill ) );
 209         } else {
 210                 /* Write back 'before' block */
 211                 store_free_block ( buffer, &before );
 212         }
 213
 214         /* Write back 'after' block */
 215         if ( after.end == buffer->len ) {
 216                 /* 'After' block is the final block: update buffer->free */
 217                 buffer->free = after.start;
 218                 DBGC2 ( buffer, "BUFFER %p free from %lx onwards\n", buffer,
 219                         user_to_phys ( buffer->addr, buffer->free ) );
 220         } else {
 221                 /* Write back 'after' block */
 222                 store_free_block ( buffer, &after );
 223         }
 224
 225         /* Copy data into buffer */
 226         copy_to_user ( buffer->addr, data_start, data, len );
 227
 228         return 0;
 229 }
 230
 231 /** Expand data buffer
 232  *
 233  * @v buffer            Data buffer
 234  * @v new_len           New length
 235  * @ret rc              Return status code
 236  *
 237  * Expand the data buffer to accommodate more data.  Some buffers may
 238  * not support being expanded.
 239  */
 240 int expand_buffer ( struct buffer *buffer, size_t new_len ) {
 241         int rc;
 242
 243         if ( new_len <= buffer->len )
 244                 return 0;
 245
 246         DBGC ( buffer, "BUFFER %p attempting to expand from length %zx to "
 247                "length %zx\n", buffer, buffer->len, new_len );
 248
 249         if ( ! buffer->expand ) {
 250                 DBGC ( buffer, "BUFFER %p is not expandable\n", buffer );
 251                 return -ENOBUFS;
 252         }
 253
 254         if ( ( rc = buffer->expand ( buffer, new_len ) ) != 0 ) {
 255                 DBGC ( buffer, "BUFFER %p could not expand: %s\n",
 256                        buffer, strerror ( rc ) );
 257                 return rc;
 258         }
 259
 260         DBGC ( buffer, "BUFFER %p expanded to [%lx,%lx)\n", buffer,
 261                user_to_phys ( buffer->addr, 0 ),
 262                user_to_phys ( buffer->addr, buffer->len ) );
 263
 264         return 0;
 265 }