errno.h now required in order to compile.
[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 "errno.h"
97 #include "buffer.h"
98
99 /**
100  * Initialise a buffer.
101  *
102  * @v buffer            The buffer to be initialised
103  * @ret None
104  * @err None
105  *
106  * Set @c buffer->start and @c buffer->end before calling init_buffer().
107  * init_buffer() will initialise the buffer to the state of being
108  * empty.
109  *
110  */
111 void init_buffer ( struct buffer *buffer ) {
112         char tail = 1;
113
114         buffer->fill = 0;
115         if ( buffer->end != buffer->start )
116                 copy_to_phys ( buffer->start, &tail, sizeof ( tail ) );
117
118         DBG ( "BUFFER [%x,%x) initialised\n", buffer->start, buffer->end );
119 }
120
121 /**
122  * Split a free block.
123  *
124  * @v desc              A descriptor for the free block
125  * @v block             Start address of the block
126  * @v split             Address at which to split the block
127  * @ret None
128  * @err None
129  *
130  * Split a free block into two separate free blocks.  If the split
131  * point lies outside the block, no action is taken; this is not an
132  * error.
133  *
134  * @b NOTE: It is the reponsibility of the caller to ensure that there
135  * is enough room in each of the two portions for a free block
136  * descriptor (a @c struct @c buffer_free_block, except in the case of
137  * a tail block which requires only a one byte descriptor).  If the
138  * caller fails to do this, data corruption will occur.
139  *
140  * In practice, this means that the granularity at which blocks are
141  * split must be at least @c sizeof(struct @c buffer_free_block).
142  *
143  */
144 static void split_free_block ( struct buffer_free_block *desc,
145                                physaddr_t block, physaddr_t split ) {
146         /* If split point is before start of block, do nothing */
147         if ( split <= block )
148                 return;
149
150         /* If split point is after end of block, do nothing */
151         if ( split >= desc->end )
152                 return;
153
154         DBG ( "BUFFER splitting [%x,%x) -> [%x,%x) [%x,%x)\n",
155               block, desc->end, block, split, split, desc->end );
156
157         /* Create descriptor for new free block */
158         copy_to_phys ( split, &desc->tail, sizeof ( desc->tail ) );
159         if ( ! desc->tail )
160                 copy_to_phys ( split, desc, sizeof ( *desc ) );
161
162         /* Update descriptor for old free block */
163         desc->tail = 0;
164         desc->next_free = split;
165         desc->end = split;
166         copy_to_phys ( block, desc, sizeof ( *desc ) );
167 }
168
169 /**
170  * Mark a free block as used.
171  *
172  * @v buffer            The buffer containing the block
173  * @v desc              A descriptor for the free block
174  * @v prev_block        Address of the previous block
175  * @ret None
176  * @err None
177  *
178  * Marks a free block as used, i.e. removes it from the free list.
179  *
180  */
181 static inline void unfree_block ( struct buffer *buffer,
182                                   struct buffer_free_block *desc,
183                                   physaddr_t prev_block ) {
184         struct buffer_free_block prev_desc;
185         
186         /* If this is the first block, just update buffer->fill */
187         if ( ! prev_block ) {
188                 DBG ( "BUFFER marking [%x,%x) as used\n",
189                       buffer->start + buffer->fill, desc->end );
190                 buffer->fill = desc->next_free - buffer->start;
191                 return;
192         }
193
194         /* Get descriptor for previous block (which cannot be a tail block) */
195         copy_from_phys ( &prev_desc, prev_block, sizeof ( prev_desc ) );
196
197         DBG ( "BUFFER marking [%x,%x) as used\n",
198               prev_desc.next_free, desc->end );
199
200         /* Modify descriptor for previous block and write it back */
201         prev_desc.next_free = desc->next_free;
202         copy_to_phys ( prev_block, &prev_desc, sizeof ( prev_desc ) );
203 }
204
205 /**
206  * Write data into a buffer.
207  *
208  * @v buffer            The buffer into which to write the data
209  * @v data              The data to be written
210  * @v offset            Offset within the buffer at which to write the data
211  * @v len               Length of data to be written
212  * @ret True            Data was successfully written
213  * @ret False           Data was not written
214  * @err ENOMEM          Buffer is too small to contain the data
215  *
216  * Writes a block of data into the buffer.  The block need not be
217  * aligned to any particular boundary, or be of any particular size,
218  * and it may overlap blocks already in the buffer (i.e. duplicate
219  * calls to fill_buffer() are explicitly permitted).
220  *
221  * @c buffer->fill will be updated to indicate the fill level of the
222  * buffer, i.e. the offset to the first gap within the buffer.  If the
223  * filesize is known (e.g. as with the SLAM protocol), you can test
224  * for end-of-file by checking for @c buffer->fill==filesize.  If the
225  * filesize is not known, but there is a well-defined end-of-file test
226  * (e.g. as with the TFTP protocol), you can read @c buffer->fill to
227  * determine the final filesize.  If blocks are known to be delivered
228  * in a strictly sequential order with no packet loss or duplication,
229  * then you can pass in @c offset==buffer->fill.
230  *
231  * @b NOTE: It is the caller's responsibility to ensure that the
232  * boundaries between data blocks are more than @c sizeof(struct @c
233  * buffer_free_block) apart.  If this condition is not satisfied, data
234  * corruption will occur.  (See split_free_block() for details.)
235  *
236  * In practice this is not a problem.  Callers of fill_buffer() will
237  * be download protocols such as TFTP, and very few protocols have a
238  * block size smaller than @c sizeof(struct @c buffer_free_block).
239  *
240  */
241 int fill_buffer ( struct buffer *buffer, const void *data,
242                   off_t offset, size_t len ) {
243         struct buffer_free_block desc;
244         physaddr_t block, prev_block;
245         physaddr_t data_start, data_end;
246
247         /* Calculate start and end addresses of data */
248         data_start = buffer->start + offset;
249         data_end = data_start + len;
250         DBG ( "BUFFER [%x,%x) writing portion [%x,%x)\n",
251               buffer->start, buffer->end, data_start, data_end );
252
253         /* Check buffer bounds */
254         if ( data_end > buffer->end ) {
255                 DBG ( "BUFFER [%x,%x) too small for data!\n",
256                       buffer->start, buffer->end );
257                 errno = ENOMEM;
258                 return 0;
259         }
260
261         /* Iterate through the buffer's free blocks */
262         prev_block = 0;
263         block = buffer->start + buffer->fill;
264         while ( block < buffer->end ) {
265                 /* Read block descriptor */
266                 desc.next_free = buffer->end;
267                 desc.end = buffer->end;
268                 copy_from_phys ( &desc.tail, block, sizeof ( desc.tail ) );
269                 if ( ! desc.tail )
270                         copy_from_phys ( &desc, block, sizeof ( desc ) );
271
272                 /* Split block at data start and end markers */
273                 split_free_block ( &desc, block, data_start );
274                 split_free_block ( &desc, block, data_end );
275
276                 /* Block is now either completely contained by or
277                  * completely outside the data area
278                  */
279                 if ( ( block >= data_start ) && ( block < data_end ) ) {
280                         /* Block is within the data area */
281                         unfree_block ( buffer, &desc, prev_block );
282                         copy_to_phys ( block, data + ( block - data_start ),
283                                        desc.end - block );
284                 } else {
285                         /* Block is outside the data area */
286                         prev_block = block;
287                 }
288
289                 /* Move to next free block */
290                 block = desc.next_free;
291         }
292
293         DBG ( "BUFFER [%x,%x) full up to %x\n",
294               buffer->start, buffer->end, buffer->start + buffer->fill );
295
296         return 1;
297 }