More documentation
[people/lynusvaz/gpxe.git] / src / core / buffer.c
1 /** @file
2  *
3  * Buffers for loading files.
4  *
5  * This file provides routines for filling a buffer with data received
6  * piecemeal, where the size of the data is not necessarily known in
7  * advance.
8  *
9  * Some protocols do not provide a mechanism for us to know the size
10  * of the file before we happen to receive a particular block
11  * (e.g. the final block in an MTFTP transfer).  In addition, some
12  * protocols (all the multicast protocols plus any TCP-based protocol)
13  * can, in theory, provide the data in any order.
14  *
15  * Rather than requiring each protocol to implement its own equivalent
16  * of "dd" to arrange the data into well-sized pieces before handing
17  * off to the image loader, we provide these generic buffer functions
18  * which assemble a file into a single contiguous block.  The whole
19  * block is then passed to the image loader.
20  *
21  * Example usage:
22  *
23  * @code
24  *
25  *   struct buffer my_buffer;
26  *   void *data;
27  *   off_t offset;
28  *   size_t len;
29  *   
30  *   // We have an area of memory [buf_start,buf_end) into which we want
31  *   // to load a file, where buf_start and buf_end are physical addresses.
32  *   buffer->start = buf_start;
33  *   buffer->end = buf_end;
34  *   init_buffer ( &buffer );
35  *   ...
36  *   while ( get_file_block ( ... ) ) {
37  *     // Downloaded block is stored in [data,data+len), and represents 
38  *     // the portion of the file at offsets [offset,offset+len)
39  *     if ( ! fill_buffer ( &buffer, data, offset, len ) ) {
40  *       // An error occurred
41  *       return 0;
42  *     }
43  *     ...
44  *   }
45  *   ...
46  *   // The whole file is now present at [buf_start,buf_start+filesize),
47  *   // where buf_start is a physical address.  The struct buffer can simply
48  *   // be discarded; there is no done_buffer() call.
49  *
50  * @endcode
51  *
52  * For a description of the internal operation, see \ref buffer_int.
53  *
54  */
55
56 /** @page buffer_int Buffer internals
57  *
58  * A buffer consists of a single, contiguous area of memory, some of
59  * which is "filled" and the remainder of which is "free".  The
60  * "filled" and "free" spaces are not necessarily contiguous.
61  *
62  * When a buffer is initialised via init_buffer(), it consists of a
63  * single free space.  As data is added to the buffer via
64  * fill_buffer(), this free space decreases and can become fragmented.
65  *
66  * Each free block within a buffer starts with a "tail byte".  If the
67  * tail byte is non-zero, this indicates that the free block is the
68  * tail of the buffer, i.e. occupies all the remaining space up to the
69  * end of the buffer.  When the tail byte is non-zero, it indicates
70  * that a descriptor (a @c struct @c buffer_free_block) follows the
71  * tail byte.  The descriptor describes the size of the free block and
72  * the address of the next free block.
73  *
74  * We cannot simply always start a free block with a descriptor,
75  * because it is conceivable that we will, at some point, encounter a
76  * situation in which the final free block of a buffer is too small to
77  * contain a descriptor.  Consider a protocol with a blocksize of 512
78  * downloading a 1025-byte file into a 1025-byte buffer.  Suppose that
79  * the first two blocks are received; we have now filled 1024 of the
80  * 1025 bytes in the buffer, and our only free block consists of the
81  * 1025th byte.  Using a "tail byte" solves this problem.
82  *
83  * 
84  * Note that the rather convoluted way of manipulating the buffer
85  * descriptors (using copy_{to,from}_phys rather than straightforward
86  * pointers) is needed to cope with operation as a PXE stack, when we
87  * may be running in real mode or 16-bit protected mode, and therefore
88  * cannot directly access arbitrary areas of memory using simple
89  * pointers.
90  *
91  */
92
93 #include "stddef.h"
94 #include "string.h"
95 #include "io.h"
96 #include "buffer.h"
97
98 /**
99  * Initialise a buffer.
100  *
101  * @v buffer            The buffer to be initialised
102  * @ret None
103  * @err None
104  *
105  * Set @c buffer->start and @c buffer->end before calling init_buffer().
106  * init_buffer() will initialise the buffer to the state of being
107  * empty.
108  *
109  */
110 void init_buffer ( struct buffer *buffer ) {
111         char tail = 1;
112
113         buffer->fill = 0;
114         if ( buffer->end != buffer->start )
115                 copy_to_phys ( buffer->start, &tail, sizeof ( tail ) );
116
117         DBG ( "BUFFER [%x,%x) initialised\n", buffer->start, buffer->end );
118 }
119
120 /**
121  * Split a free block.
122  *
123  * @v desc              A descriptor for the free block
124  * @v block             Start address of the block
125  * @v split             Address at which to split the block
126  * @ret None
127  * @err None
128  *
129  * Split a free block into two separate free blocks.  If the split
130  * point lies outside the block, no action is taken; this is not an
131  * error.
132  *
133  * @b NOTE: It is the reponsibility of the caller to ensure that there
134  * is enough room in each of the two portions for a free block
135  * descriptor (a @c struct @c buffer_free_block, except in the case of
136  * a tail block which requires only a one byte descriptor).  If the
137  * caller fails to do this, data corruption will occur.
138  *
139  * In practice, this means that the granularity at which blocks are
140  * split must be at least @c sizeof(struct @c buffer_free_block).
141  *
142  */
143 static void split_free_block ( struct buffer_free_block *desc,
144                                physaddr_t block, physaddr_t split ) {
145         /* If split point is before start of block, do nothing */
146         if ( split <= block )
147                 return;
148
149         /* If split point is after end of block, do nothing */
150         if ( split >= desc->end )
151                 return;
152
153         DBG ( "BUFFER splitting [%x,%x) -> [%x,%x) [%x,%x)\n",
154               block, desc->end, block, split, split, desc->end );
155
156         /* Create descriptor for new free block */
157         copy_to_phys ( split, &desc->tail, sizeof ( desc->tail ) );
158         if ( ! desc->tail )
159                 copy_to_phys ( split, desc, sizeof ( *desc ) );
160
161         /* Update descriptor for old free block */
162         desc->tail = 0;
163         desc->next_free = split;
164         desc->end = split;
165         copy_to_phys ( block, desc, sizeof ( *desc ) );
166 }
167
168 /**
169  * Mark a free block as used.
170  *
171  * @v buffer            The buffer containing the block
172  * @v desc              A descriptor for the free block
173  * @v prev_block        Address of the previous block
174  * @ret None
175  * @err None
176  *
177  * Marks a free block as used, i.e. removes it from the free list.
178  *
179  */
180 static inline void unfree_block ( struct buffer *buffer,
181                                   struct buffer_free_block *desc,
182                                   physaddr_t prev_block ) {
183         struct buffer_free_block prev_desc;
184         
185         /* If this is the first block, just update buffer->fill */
186         if ( ! prev_block ) {
187                 DBG ( "BUFFER marking [%x,%x) as used\n",
188                       buffer->start + buffer->fill, desc->end );
189                 buffer->fill = desc->next_free - buffer->start;
190                 return;
191         }
192
193         /* Get descriptor for previous block (which cannot be a tail block) */
194         copy_from_phys ( &prev_desc, prev_block, sizeof ( prev_desc ) );
195
196         DBG ( "BUFFER marking [%x,%x) as used\n",
197               prev_desc.next_free, desc->end );
198
199         /* Modify descriptor for previous block and write it back */
200         prev_desc.next_free = desc->next_free;
201         copy_to_phys ( prev_block, &prev_desc, sizeof ( prev_desc ) );
202 }
203
204 /**
205  * Write data into a buffer.
206  *
207  * @v buffer            The buffer into which to write the data
208  * @v data              The data to be written
209  * @v offset            Offset within the buffer at which to write the data
210  * @v len               Length of data to be written
211  * @ret True            Data was successfully written
212  * @ret False           Data was not written
213  * @err ENOMEM          Buffer is too small to contain the data
214  *
215  * Writes a block of data into the buffer.  The block need not be
216  * aligned to any particular boundary, or be of any particular size,
217  * and it may overlap blocks already in the buffer (i.e. duplicate
218  * calls to fill_buffer() are explicitly permitted).
219  *
220  * @c buffer->fill will be updated to indicate the fill level of the
221  * buffer, i.e. the offset to the first gap within the buffer.  If the
222  * filesize is known (e.g. as with the SLAM protocol), you can test
223  * for end-of-file by checking for @c buffer->fill==filesize.  If the
224  * filesize is not known, but there is a well-defined end-of-file test
225  * (e.g. as with the TFTP protocol), you can read @c buffer->fill to
226  * determine the final filesize.  If blocks are known to be delivered
227  * in a strictly sequential order with no packet loss or duplication,
228  * then you can pass in @c offset==buffer->fill.
229  *
230  * @b NOTE: It is the caller's responsibility to ensure that the
231  * boundaries between data blocks are more than @c sizeof(struct @c
232  * buffer_free_block) apart.  If this condition is not satisfied, data
233  * corruption will occur.  (See split_free_block() for details.)
234  *
235  * In practice this is not a problem.  Callers of fill_buffer() will
236  * be download protocols such as TFTP, and very few protocols have a
237  * block size smaller than @c sizeof(struct @c buffer_free_block).
238  *
239  */
240 int fill_buffer ( struct buffer *buffer, const void *data,
241                   off_t offset, size_t len ) {
242         struct buffer_free_block desc;
243         physaddr_t block, prev_block;
244         physaddr_t data_start, data_end;
245
246         /* Calculate start and end addresses of data */
247         data_start = buffer->start + offset;
248         data_end = data_start + len;
249         DBG ( "BUFFER [%x,%x) writing portion [%x,%x)\n",
250               buffer->start, buffer->end, data_start, data_end );
251
252         /* Check buffer bounds */
253         if ( data_end > buffer->end ) {
254                 DBG ( "BUFFER [%x,%x) too small for data!\n",
255                       buffer->start, buffer->end );
256                 errno = ENOMEM;
257                 return 0;
258         }
259
260         /* Iterate through the buffer's free blocks */
261         prev_block = 0;
262         block = buffer->start + buffer->fill;
263         while ( block < buffer->end ) {
264                 /* Read block descriptor */
265                 desc.next_free = buffer->end;
266                 desc.end = buffer->end;
267                 copy_from_phys ( &desc.tail, block, sizeof ( desc.tail ) );
268                 if ( ! desc.tail )
269                         copy_from_phys ( &desc, block, sizeof ( desc ) );
270
271                 /* Split block at data start and end markers */
272                 split_free_block ( &desc, block, data_start );
273                 split_free_block ( &desc, block, data_end );
274
275                 /* Block is now either completely contained by or
276                  * completely outside the data area
277                  */
278                 if ( ( block >= data_start ) && ( block < data_end ) ) {
279                         /* Block is within the data area */
280                         unfree_block ( buffer, &desc, prev_block );
281                         copy_to_phys ( block, data + ( block - data_start ),
282                                        desc.end - block );
283                 } else {
284                         /* Block is outside the data area */
285                         prev_block = block;
286                 }
287
288                 /* Move to next free block */
289                 block = desc.next_free;
290         }
291
292         DBG ( "BUFFER [%x,%x) full up to %x\n",
293               buffer->start, buffer->end, buffer->start + buffer->fill );
294
295         return 1;
296 }