Move API docs to buffer.h, implementation to buffer.c.
[people/xl0/gpxe.git] / 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 "stddef.h"
42 #include "string.h"
43 #include "io.h"
44 #include "errno.h"
45 #include "buffer.h"
46
47 /**
48  * Initialise a buffer.
49  *
50  * @v buffer            The buffer to be initialised
51  * @ret None
52  * @err None
53  *
54  * Set @c buffer->start and @c buffer->end before calling init_buffer().
55  * init_buffer() will initialise the buffer to the state of being
56  * empty.
57  *
58  */
59 void init_buffer ( struct buffer *buffer ) {
60         char tail = 1;
61
62         buffer->fill = 0;
63         if ( buffer->end != buffer->start )
64                 copy_to_phys ( buffer->start, &tail, sizeof ( tail ) );
65
66         DBG ( "BUFFER [%x,%x) initialised\n", buffer->start, buffer->end );
67 }
68
69 /**
70  * Split a free block.
71  *
72  * @v desc              A descriptor for the free block
73  * @v block             Start address of the block
74  * @v split             Address at which to split the block
75  * @ret None
76  * @err None
77  *
78  * Split a free block into two separate free blocks.  If the split
79  * point lies outside the block, no action is taken; this is not an
80  * error.
81  *
82  * @b NOTE: It is the reponsibility of the caller to ensure that there
83  * is enough room in each of the two portions for a free block
84  * descriptor (a @c struct @c buffer_free_block, except in the case of
85  * a tail block which requires only a one byte descriptor).  If the
86  * caller fails to do this, data corruption will occur.
87  *
88  * In practice, this means that the granularity at which blocks are
89  * split must be at least @c sizeof(struct @c buffer_free_block).
90  *
91  */
92 static void split_free_block ( struct buffer_free_block *desc,
93                                physaddr_t block, physaddr_t split ) {
94         /* If split point is before start of block, do nothing */
95         if ( split <= block )
96                 return;
97
98         /* If split point is after end of block, do nothing */
99         if ( split >= desc->end )
100                 return;
101
102         DBG ( "BUFFER splitting [%x,%x) -> [%x,%x) [%x,%x)\n",
103               block, desc->end, block, split, split, desc->end );
104
105         /* Create descriptor for new free block */
106         copy_to_phys ( split, &desc->tail, sizeof ( desc->tail ) );
107         if ( ! desc->tail )
108                 copy_to_phys ( split, desc, sizeof ( *desc ) );
109
110         /* Update descriptor for old free block */
111         desc->tail = 0;
112         desc->next_free = split;
113         desc->end = split;
114         copy_to_phys ( block, desc, sizeof ( *desc ) );
115 }
116
117 /**
118  * Mark a free block as used.
119  *
120  * @v buffer            The buffer containing the block
121  * @v desc              A descriptor for the free block
122  * @v prev_block        Address of the previous block
123  * @ret None
124  * @err None
125  *
126  * Marks a free block as used, i.e. removes it from the free list.
127  *
128  */
129 static inline void unfree_block ( struct buffer *buffer,
130                                   struct buffer_free_block *desc,
131                                   physaddr_t prev_block ) {
132         struct buffer_free_block prev_desc;
133         
134         /* If this is the first block, just update buffer->fill */
135         if ( ! prev_block ) {
136                 DBG ( "BUFFER marking [%x,%x) as used\n",
137                       buffer->start + buffer->fill, desc->end );
138                 buffer->fill = desc->next_free - buffer->start;
139                 return;
140         }
141
142         /* Get descriptor for previous block (which cannot be a tail block) */
143         copy_from_phys ( &prev_desc, prev_block, sizeof ( prev_desc ) );
144
145         DBG ( "BUFFER marking [%x,%x) as used\n",
146               prev_desc.next_free, desc->end );
147
148         /* Modify descriptor for previous block and write it back */
149         prev_desc.next_free = desc->next_free;
150         copy_to_phys ( prev_block, &prev_desc, sizeof ( prev_desc ) );
151 }
152
153 /**
154  * Write data into a buffer.
155  *
156  * @v buffer            The buffer into which to write the data
157  * @v data              The data to be written
158  * @v offset            Offset within the buffer at which to write the data
159  * @v len               Length of data to be written
160  * @ret True            Data was successfully written
161  * @ret False           Data was not written
162  * @err ENOMEM          Buffer is too small to contain the data
163  *
164  * Writes a block of data into the buffer.  The block need not be
165  * aligned to any particular boundary, or be of any particular size,
166  * and it may overlap blocks already in the buffer (i.e. duplicate
167  * calls to fill_buffer() are explicitly permitted).
168  *
169  * @c buffer->fill will be updated to indicate the fill level of the
170  * buffer, i.e. the offset to the first gap within the buffer.  If the
171  * filesize is known (e.g. as with the SLAM protocol), you can test
172  * for end-of-file by checking for @c buffer->fill==filesize.  If the
173  * filesize is not known, but there is a well-defined end-of-file test
174  * (e.g. as with the TFTP protocol), you can read @c buffer->fill to
175  * determine the final filesize.  If blocks are known to be delivered
176  * in a strictly sequential order with no packet loss or duplication,
177  * then you can pass in @c offset==buffer->fill.
178  *
179  * @b NOTE: It is the caller's responsibility to ensure that the
180  * boundaries between data blocks are more than @c sizeof(struct @c
181  * buffer_free_block) apart.  If this condition is not satisfied, data
182  * corruption will occur.  (See split_free_block() for details.)
183  *
184  * In practice this is not a problem.  Callers of fill_buffer() will
185  * be download protocols such as TFTP, and very few protocols have a
186  * block size smaller than @c sizeof(struct @c buffer_free_block).
187  *
188  */
189 int fill_buffer ( struct buffer *buffer, const void *data,
190                   off_t offset, size_t len ) {
191         struct buffer_free_block desc;
192         physaddr_t block, prev_block;
193         physaddr_t data_start, data_end;
194
195         /* Calculate start and end addresses of data */
196         data_start = buffer->start + offset;
197         data_end = data_start + len;
198         DBG ( "BUFFER [%x,%x) writing portion [%x,%x)\n",
199               buffer->start, buffer->end, data_start, data_end );
200
201         /* Check buffer bounds */
202         if ( data_end > buffer->end ) {
203                 DBG ( "BUFFER [%x,%x) too small for data!\n",
204                       buffer->start, buffer->end );
205                 errno = ENOMEM;
206                 return 0;
207         }
208
209         /* Iterate through the buffer's free blocks */
210         prev_block = 0;
211         block = buffer->start + buffer->fill;
212         while ( block < buffer->end ) {
213                 /* Read block descriptor */
214                 desc.next_free = buffer->end;
215                 desc.end = buffer->end;
216                 copy_from_phys ( &desc.tail, block, sizeof ( desc.tail ) );
217                 if ( ! desc.tail )
218                         copy_from_phys ( &desc, block, sizeof ( desc ) );
219
220                 /* Split block at data start and end markers */
221                 split_free_block ( &desc, block, data_start );
222                 split_free_block ( &desc, block, data_end );
223
224                 /* Block is now either completely contained by or
225                  * completely outside the data area
226                  */
227                 if ( ( block >= data_start ) && ( block < data_end ) ) {
228                         /* Block is within the data area */
229                         unfree_block ( buffer, &desc, prev_block );
230                         copy_to_phys ( block, data + ( block - data_start ),
231                                        desc.end - block );
232                 } else {
233                         /* Block is outside the data area */
234                         prev_block = block;
235                 }
236
237                 /* Move to next free block */
238                 block = desc.next_free;
239         }
240
241         DBG ( "BUFFER [%x,%x) full up to %x\n",
242               buffer->start, buffer->end, buffer->start + buffer->fill );
243
244         return 1;
245 }